FourierKoeffizienten eines Polygons + Mustererkennung

[Nikolas]

Hallo

Wie letztens geschrieben, sitze ich gerade an einem Programm, das gezeichnete Nutzereingaben erkennen soll.
Sinn dahinter ist einfach eine Proof-of-Concept Implementierung der Inhalte aus der MustererkennnungsVorlesung, die ich gerade höre.


Ich bin jetzt so weit fertig, dass man über die Maus ein Polygon zeichnen kann und dieses weiterverarbeitet wird.
Zunächst wird das Polygon über einen recht naiven, aber recht wirkungsvollen Algorithmus geschlossen, dann werden die Fourerkoeffizienten berechnet. Aus diesen Koeffizienten lässt sich dann entscheiden, ob der Nutzer einen Strick, einen Kreis, oder ein Dreieck gezeichnet hat.
Mit etwas Aufwand kann man das sicher auch noch auf andere Formen verallgemeinern.
Man könnte so was auch im Hintergrund als Dämon laufen lassen und dem Nutzer z.B. die Möglichkeit geben, eine Datei einfach durchzustreichen und diese dann automatisch in den Papierkorb verschieben

Die Dateien habe ich mangels Anhangsfunktion im Forum auf meinen Uni-accountgelegt. (Hier sind alle Dateien in einer kleinen .zip Datei)

Als kleine Demo kann man sich FreiesZeichnen.py anschauen, in Koeffizienten.py werden zu verschiedenen Polygonen auch die FourierKoeffizienten angezeit, so dass man ein Gefühl dafür bekommt, wie man die einzelnen Objekte an ihren Koeffizienten unterscheiden kann.

Die Funktionen darf jeder frei benutzen und in eigene Programme integrieren, ich will nur wissen, wer es einsetzt und wie das Projekt aussieht.

Was meint ihr dazu?

[HWK]

Ich habe mir den Code nicht angesehen, sondern nur 'FreiesZeichnen.py' gestartet. Es lief wegen eines Syntaxfehlers (class Polygon()) aber erst nicht. Dann störte mich, dass die Kurve erst nach Loslassen der Maustaste angezeigt wird. Das erschwert doch erheblich die Rückkopplung, was ich gerade gezeichnet habe. Weiterhin wird ein Dreieck sehr häufig als Kreis erkannt. Ansonsten ist die Idee aber sehr interessant.
MfG
HWK

[Nikolas]

Ok. ich habe es nochmal überarbeitet. Jetzt sieht man, was man zeichnet und es werden gleich die Koeffizienten angezeigt.

Der TrennAlgorithmus zwischen Kreis und Dreieck besteht darin den zweiten Koeffizienten mit den anderen zu vergleichen (die Koeffizienten -1,0,1 werden nicht betrachtet).
Wenn man etwas rumspielt, sieht man, das bei Dreiecken der 2.Koeffizient (c2) die anderen stark dominiert.
Ich zähle also, wie viele andere Koeffizienten größer als grob 20% des c2 sind und entscheide darüber, was erkannt wird.
Interessant ist jetzt, wie viele Koeffizienten insgesamt berechnet werden und wie hoch die Schranke im Vergleich zu c2 ist (z.B. 20%) und wie viele Koeffizienten diese Schranke durchbrechen müssen, bis ein Kreis erkannt werden soll.

In FreiesZeichnen.py kann man die KoeffizientenAnzahl einstellen, in Fourier.py die anderen Parameter. Wenn man die Schranke erhöht, werden eher mehr Dreiecke erkannt, bei der erlaubtenAnzahl an Koeffizienten über der Schranke genauso.

Zusätzlich zu der KoeffizientenAusgabe habe ich noch ein TextWidget unterbracht, in das die Standardausgabe geleitet wird. Nachdem man ein Objekt gezeichnet hat, wird hier die Anzahl der Koeffiizienten angezeigt, die oberhalb der Schranke sind (also bei Standardeinstellung größer als 20% von c2 sind).

[HWK]

Bei mir läuft es leider nicht. Erst mal ist wieder der o.g. Syntaxfehler in Polygon.py. Dann erscheint nur das Bild, das von diesem Python-Script als ocr.jpg erzeugt wird. In dem kann man aber nichts zeichnen.
MfG
HWK

[BlackJack]

Hey manchmal muss man auch Regulars mal sagen dass man Fehlermeldungen wörtlich wiedergeben sollte:

Ich vermute mal stark es sind die leeren Klammern am Ende der ``class``-Definition, die ab Python 2.5 *kein* SyntaxError mehr sind. Ohne diese Info hat Nikolas wahrscheinlich keine Chance das Problem zu beseitigen, weil's bei ihm problemlos funktioniert.

Code: Alles auswählen

Python 2.4.4 (#2, Apr 12 2007, 21:03:11)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> class A():
  File "<stdin>", line 1
    class A():
            ^
SyntaxError: invalid syntax
>>>

Code: Alles auswählen

Python 2.5.1 (r251:54863, May  2 2007, 16:56:35)
[GCC 4.1.2 (Ubuntu 4.1.2-0ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> class A():
...     pass
...
>>>

[HWK]

Ich vermute mal stark es sind die leeren Klammern am Ende der ``class``-Definition, die ab Python 2.5 *kein* SyntaxError mehr sind. Ohne diese Info hat Nikolas wahrscheinlich keine Chance das Problem zu beseitigen, weil's bei ihm problemlos funktioniert.

Da hast Du vollkommen recht. Aber für mich war der Fehler so offensichtlich und da ich noch mit 2.4 arbeite, wusste ich auch nicht, dass es unter 2.5 kein Syntax-Fehler mehr ist. Deshalb habe ich die Fehlermeldung nicht wörtlich angegeben.

Übrigens meine Umgebung:
Windows XP SP 2
Python 2.4.4
tk/tcl 8.4

MfG
HWK

[tabellar]

Hi Nikolas,

ich finde Deinen Mustererkennungsansatz mit den Fourierkoeffizienten sehr
interessant! Bisher habe ich die Mustererkennung immer ausschliesslich den
künstlichen neuronalen Netzen (KNN) zugeordnet.

Ich hab gerade etwas mit dem verarbeiten von digitalen Messdaten zu
tun und komme so auch der FFT etwas näher. Aus diesem Grunde kann
ich den Ansatz von Dir mit dem "mitschneiden" von Mauspositionen des
Benutzers und dem anschliessenden Auswerten ganz gut nachvollziehen.

Geht es Dir generell eher um die Mustererkennung (OCR) oder eher um
den Fourierkoeffizienten Ansatz?

Grüsse
tabellar

PS:
Kennst Du im Netz vernünftige Literaturquellen, die einem die FFT und
Fourierkoeffizienten etwas "verdaulicher" näherbringen? Ich versuche
das nämlich gerade mit Numpy zu bewerkstelligen, aber leider fehlen
mit die entsprechenden FFT Grundlagen dazu...

[HWK]

Es läuft jetzt doch. Aber: Wenn ich nach einer Auswertung nur einmal in das Canvas klicke erscheint folgende Fehlermeldung:

Code: Alles auswählen

Exception in Tkinter callback
Traceback (most recent call last):
  File "C:\Programme\Python24\lib\lib-tk\Tkinter.py", line 1345, in __call__
    return self.func(*args)
  File "C:\Download\OCR\FreiesZeichnen.py", line 52, in handlerRelease
    ID = canvas.create_line(tuppel2List(L),width=2,fill="blue")
  File "C:\Programme\Python24\lib\lib-tk\Tkinter.py", line 2090, in create_line
    return self._create('line', args, kw)
  File "C:\Programme\Python24\lib\lib-tk\Tkinter.py", line 2071, in _create
    cnf = args[-1]
IndexError: tuple index out of range

MfG
HWK

[Nikolas]

stimmt. da fehlt noch ein

Code: Alles auswählen

if len(L)<2: return 

Im Code für den Buttonrelease.
Danke für deine Fehlermeldungen, jetzt sollte es benutzbar sein

@tabelar:
Das mit den NN stimmt schon, nur muss man die Inputdaten doch etwas reduzieren, bevor man sie dem Netz füttern kann. Ich habe mal versucht, die Fourierkoeffizienten (besser gesagt nur ihre Beträge) einem Netz zu füttern, aber das hat nicht so funtioniert.
Die Fourierkoeffizienten sind damit eine gute Vorstufe für ein Netz, dass dann nur noch 10-15 InputNeuronen nötig sind.

Ich wollte einfach mal was interessantes in Python schreiben und rausfinden, ob das, was theoretisch in der Vorlesung erzählt wird, auch wirklich in freier Wildbahn funktioniert.

Vielleicht findest du hier bei bei den Skripten was passendes.

Bei FFT kenne ich mich nicht aus, aber da gibts doch sicher schon fertige Komponenten.

[tabellar]

Hi Nikolas,

gefällt mir richtig gut Dein Programm. Auch das
bar-chart mit den Fourierkoeffizienten visualisiert
das ganz sehr schön. Ich muss mich mal mit der
Theorie mehr befassen.

Gruss
Tabellar