Willkommen in unserer Werkstatt. Wir berichten hier von eigenen Projekten und unter dem Titel Beautiful Data teilen wir Projekte anderer, die wir entweder aufgrund der gewählten Darstellung oder wegen ihres Inhalts inspirierend finden.

  • Sudoku Solver

    Sudoku Solver

    Sudoku Solver

    Wir haben einen «Sudoku-Löser» programmiert, der anhand eines Fotos eines Sudoku-Feldes die eingegebenen Zahlen erkennt und dann das Sudoku löst.

    Für diese Anwendung haben wir die Aufgaben in vier Teilbereiche aufgeteilt:

    • Sudoku und Zahlen mit Bildverarbeitungsmethoden erkennen
    • Erkennen von Zahlen mit Hilfe eines KI-Modells
    • Lösen von Sudoku mittels Backtracking-Algorithmus
    • Implementierung einer Webanwendung mit Microsoft Azure

    Im Folgenden werden die vier Teilbereiche näher beschrieben.

    mehr anzeigen

    Computer Vision

    Mit Hilfe der Softwarebibliothek OpenCV führen wir verschiedene Schritte durch, um das Sudoku-Feld zu finden. Zuerst werden typische Vorverarbeitungsschritte (Graubild, Gaußscher Filter) am Bild durchgeführt und nach Kanten gesucht. Anschließend wird im Kantenbild nach zusammenhängenden Konturen gesucht. Die größte viereckige Kontur wird als Sudoku-Feld ausgewählt.

    Nachdem das Viereck in ein Quadrat transformiert wurde, wird in diesem nach zusammenhängenden Komponenten gesucht. Diejenigen Komponenten, die bestimmte geometrische Bedingungen erfüllen, werden als Zahlenkandidaten ausgewählt. Für jeden solchen Kandidaten wird ein quadratisches Bild ausgeschnitten, das dem Zahlenklassifikator übergeben wird.

    Klassifikator

    Als Klassifikator haben wir ein Convolutional Neural Network (CNN), also ein neuronales Netz, trainiert. Diese finden Anwendung in vielen Bildverarbeitungsproblemen und haben sich auch bei der Erkennung von computer- oder handgeschriebenen Symbolen bewährt. Wir haben unser CNN mit dem bekannten MNIST-Datensatz und einem zusätzlichen Satz von Zahlen trainiert. Das zusätzliche Datenset besteht aus handgeschriebenen Ziffern der europäischen Schrift, die sich insbesondere bei den Ziffern 1 und 7 von der angelsächsischen Schrift unterscheidet.

    Allerdings war die Fehlklassifikationsrate von Ziffern in einem begonnenen Sudoku (Kombination von computer- und handgeschriebenen Symbolen) so hoch, dass wir unser eigenes Modell nicht weiter verwenden wollten. Daher haben wir auf ein vortrainiertes Modell zurückgegriffen.

    Backtracking Algorithmus

    Es gibt verschiedene Möglichkeiten, ein Sudoku zu lösen. Wir haben uns für einen Backtracking-Algorithmus entschieden. Dieser Algorithmus ist in der Lage, alle zulässigen Lösungen eines Sudokus zu finden. Der Backtracking-Algorithmus ist ein Brut-Force-Algorithmus und hat daher eine hohe Laufzeit. Für die meisten praktischen Fälle, die wir getestet haben, ist er jedoch ausreichend.

    Der Backtracking-Algorithmus kann in wenigen Zeilen implementiert werden, aber es gibt andere Sudoku-Algorithmen, die die Struktur des Spiels besser ausnutzen und das Problem schneller lösen.

    Webapplikation

    Um die gesamte Logik für den Benutzer zugänglich zu machen, haben wir eine Single Page Application (SPA) mit React geschrieben und auf der Azure Cloud gehostet.

    sudokusolver.ch

    Sudoku Solver Preview

Open Data Hack St. Gallen 2021

Beförderte Personen pro Streckenabschnitt und Linie

Die Koordinationsstelle Open Government Data St. Gallen hat Anfang November einen Hackathlon veranstaltet.

Wir haben mit den auf daten.sg.ch frei verfügbaren ÖV Daten, einen neuen Datensatz generiert und visualisert. Zusätzlich haben wir eine Möglichkeit geschaffen, die Frequentierung von Korridoren zu messen.

Unser Beitrag: https://devpost.com/software/offentlicher-verkehr-personenstrome-in-st-gallen

Interaktive Karte: https://flowmap.blue

Beautiful Data

Pro Kopf Ausstoss in St. Gallen

Pro-Kopf Ausstoss von Treibhausgasemissionen (CO₂-​Äquivalente) der Stadt St. Gallen 2018.

Bild: https://www.stadt.sg.ch

Diagramm Pro Kopf Ausstoss Treibhausgase St.Gallen

Beautiful Data

Bio- und künstliche Masse

Vergleich zwischen Biomasse von Tieren und Pflanzen und menschengemachter Masse wie Plastik und Beton.

Bild: https://www.somethingshappening.co.uk/

passender Text: https://www.spektrum.de/

Vergleich Bio- und künstliche Masse