OCR Erkennungsprogramm für Baumstrukturen

Du hast eine Idee für ein Projekt?
Antworten
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Freitag 11. Januar 2008, 20:36

Hallo Freunde der Schlange

Ich habe mir gerade eine Idee in den Kopf gesetzt, die ich gerne umsetzen würde. Mein Ziel ist es, ein Programm zu entwickeln, bei dem man mit der Maus (oder einem Stift, wenn man was passendes hat), einen Binärbaum zeichnet und dieser Baum vom Programm erkannt wird, so dass man ein paar Knoten zeichnet, und dann z.B. den Befehl geben kann, das ein bestimmter Knoten entfernt wird, was dann mit einer schönen Animation gelöst wird.
Das Ganze könnte man dann schön in den Info-Vorlesungen nutzen. (Da werde ich nächstes Semester wohl Tutor machen, so dass die Möglichkeit besteht, das Programm wirklich mal in einer Vorlesung am Laufen zu haben.)
Unterstützt werden sollten Binärbäume, AVL-Bäume, BruderBäume,... vll auch Heaps (Fibonacci-Heaps, wenns ganz extrem werden soll.

Am interessantesten finde ich die Schrifterkennung. Als Objektklassen schweben mir da Gerade, Kreise und Quadrate (Rechtecke) ein, damit sollte alles wichtige zu zeichnen sein. (Kanten, Knoten, Blätter).

Die Erkennung soll so funktionieren, dass während des Zeichnens eines Objekts (aus den Klassen), alle paar ms die Mausposition aufgezeichnet wird, und man damit ein Polygon erhält. Auf diese Weise kann man sich die ganze Konturerkennung sparen, es ist aber auch nicht möglich, im Nachhinein gezeichnete Strukturen zu erkennen.
Die Geraden will ich von den anderen Klassen durch eine lineare Regression unterscheiden. Wenn die Standardabweichung klein ist, habe ich eine Gerade, sonst etwas anderes. (klappt ganz gut, der Unterschied liegt bei einem Faktor von 10-100)

Wie ich Kreise von Rechtecken unterscheide, weiss ich noch nicht exakt.
Ein Ansatz wäre dafür zu sorgen, dass man eine geschlossene Kontur hat, eine Fourrieranalyse zu machen und dann versucht, aus den Koeffizienten zu lesen, ob man ein 4-symmetrisches Quadrat oder einen Kreis hat, bei dem nur der erste Koeffizient groß sein soll.

Das Projekt könnte man recht gut zerteilen, vielleicht grob in die Gruppen:
- GUI und Einlesen der Polygone
- Erkennung der Klassen mit Hilfe der Polygonen
- Implementierung der Funktionen auf den Bäumen
- Zeichnen der Bäume (und Heaps)
- Implementierung der Animationen

Wie man sieht, ist da eigentlich für jeden was zu tun, das OCR ist recht mathmatisch, für GUIFreaks gibts Animationen und wer mal vor hat, Info zu studieren, hat dann einen großen Vorteil, wenn er mal mit den Datenstrukturen gearbeitet hat.

Wer also Lust hat, an einem wirklich interessanten und nützlichen Programm zu arbeiten, dass mit etwas Glück auch von ein paar Leuten benutzt wird, sollte sich hier melden :lol:
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Benutzeravatar
mkesper
User
Beiträge: 919
Registriert: Montag 20. November 2006, 15:48
Wohnort: formerly known as mkallas
Kontaktdaten:

Montag 14. Januar 2008, 14:06

Ein OCR, welches gut funktionieren soll, ist tesseract.
Von Python aus sollte sich das per pytesser ansprechen lassen.
Ich denke, das ist sinnvoller, als alles (low-level) neu machen zu wollen.
Nikolas
User
Beiträge: 102
Registriert: Dienstag 25. Dezember 2007, 22:53
Wohnort: Freiburg im Breisgau

Mittwoch 16. Januar 2008, 13:30

Das ist doch langweilig. Ich will doch wissen, warum es funktioniert. btw:
Es funktioniert!

Ich habe eine sehr gute Quote für Striche, Kreise und Dreiecke erreicht.
Die Erkennung der Eingabe ist somit kein Problem mehr :)

Wenn noch jemand einsteigen will, als nächstes werde ich mich daransetzen, Komponenten für die Darstellung der BaumKomponenten zu erstellen und das Zeichnen zu schreiben.
Erwarte das Beste und sei auf das Schlimmste vorbereitet.
Antworten