Lösen eines Sudokus durch Bildverarbeitung und Klassifizierung

Abstract

Für diese Arbeit wurde eine Android Anwendung geschrieben, welche ein Bild von einem Sudoku lösen kann. Hierfür wurde Bildverarbeitung genutzt, um zum einen das Sudokugitter zu extrahieren und zum anderen die einzelnen Ziffern in den Zellen zu isolieren. Die Ziffern werden durch ein Convolutional Neural Network klassifiziert, welches auf Basis eines erweiterten MNIST Datensatzes trainiert wurde. Schlussendlich kann das übertragene Sudoku durch einen rekursiven Backtracking Algorithmus gelöst werden. Die Leistung der Anwendung wurde mit 100 Testbildern ausgewertet. Der Datensatz umfasst Bilder mit unterschiedlichen Qualitäten und potentiellen Störfaktoren. Die Anwendung konnte 94,6 Prozent aller Zellen in dem Testdatensatz korrekt klassifizieren. Limitierung traten vor allem in der Extraktion von zu stark gekrümmten Sudokugittern auf. Die Klassifizierung der Ziffern hatte einige Probleme mit der Erkennung einzelner Zahlen, wobei sich die Fehlerkennung auf unter 10 Prozent beschränkt.