Grafiken erkennen. Library ?

[stiftII]

Hallo,

ich müsste für ein Projekt Grafiken erkennen.

Das soll so funktionieren, dass die zu erkennende Grafik als .bmp eingelesen wird, und diese Grafik soll in einer anderen Grafik (zB auf dem Desktop) erkannt werden.

Das ganze soll auch funktionieren, wenn sich die Größe der gesuchten Grafik verändert.

Gibt es für diese Aufgabe irgendwelchen libs ?

Wie kann man so eine optische Erkennung am besten umsetzen.. TBitmap ist ja auch nicht alzu flexibel... und jeden Pixel einzeln auszulesen macht jetzt auch nicht viel Sinn und ist auch recht langsam !?

~stiftII

PS: Arbeite mit Lazarus

[Jens01]

Zitat:

Gibt es für diese Aufgabe irgendwelchen libs ?

Also Graphics32 hat viele Tools, die Du gebrauchen kannst. Eine direkte Lösung wird das aber nicht sein.

Ansonsten finde ich oft hier was für solche Graphik-Sachen.

Zitat:

und jeden Pixel einzeln auszulesen macht jetzt auch nicht viel Sinn und ist auch recht langsam

Warum nicht?

[freeway]

man kann jedes Pixel auslesen, man kann aber auch scanline verwenden (schneller)

[shmia]

Zitat von freeway:

man kann jedes Pixel auslesen, man kann aber auch scanline verwenden (schneller)

Kommt drauf an, ob der Algorithmus es erlaubt sich im Bitmap horizontal zu bewegen.

Auf jeden Fall ist Pattern Matching sehr anspruchsvoll und übersteigt die Fähigkeiten eines "normalen Programmierers".

[Codewalker]

Es muss nicht direkt pattern matching sein, es reicht ja eine Ähnlichkeitssuche. Das Schlagwort hier wäre "Korrelationsfunktion" (nicht die aus der Statistik, sondern die Umkehrung zur Convolution/Faltung in der Bildverarbeitung).
Leichte Kost ist das auch nicht gerade. Man sollte in der Lage sein, ein Bild per Fourier-Transformation (FFT) in den Frequenzraum zu transformieren (und wieder zurück) und auch komplexe Zahlen sollte einem nicht fremd sein. Zur Belohnung kann man dann ein kleineres Bild in einem größeren suchen und bekommt X- und Y-Koordinaten am Ende raus (als Maxima der Funktion, die die Ähnlichkeit der Bilder darstellt).
Zum schnellen Testen, kann man MatLab hernehmen:

Code:

functiong = dftcorr(f,w)
[M,N] = size(f);
F = fft2(f);
G = conj(fft2(w,M,N));
g = real(ifft2(G.*F));
gs= im2uint8(mat2gray(g));
figure; imtool(gs);
[I,J]= find(g == max(g(:)))

wobei hier w das gesuchte Muster und f das Gesamtbild ist. In I und J stehen dann nachher die Koordinaten (I=Y, J=X, weil Matlab spaltenweise arbeitet).
Das ganze in fertiger Form für Delphi kenne ich leider nicht, aber wenn dich das bisher nicht abgeschreckt hat: Zumindest zur Theorie dahinter hab ich noch ein wenig rumfliegen.

[fkerber]

Hi,

die eierlegende Wollmilchsau zum Thema Bilderkennung etc. dürft vermutlich OpenCV sein...

LG, Frederic

[stiftII]

Zitat von Codewalker:

Es muss nicht direkt pattern matching sein, es reicht ja eine Ähnlichkeitssuche. Das Schlagwort hier wäre "Korrelationsfunktion" (nicht die aus der Statistik, sondern die Umkehrung zur Convolution/Faltung in der Bildverarbeitung).
Leichte Kost ist das auch nicht gerade. Man sollte in der Lage sein, ein Bild per Fourier-Transformation (FFT) in den Frequenzraum zu transformieren (und wieder zurück) und auch komplexe Zahlen sollte einem nicht fremd sein. Zur Belohnung kann man dann ein kleineres Bild in einem größeren suchen und bekommt X- und Y-Koordinaten am Ende raus (als Maxima der Funktion, die die Ähnlichkeit der Bilder darstellt).
Zum schnellen Testen, kann man MatLab hernehmen:

Code:

functiong = dftcorr(f,w)
[M,N] = size(f);
F = fft2(f);
G = conj(fft2(w,M,N));
g = real(ifft2(G.*F));
gs= im2uint8(mat2gray(g));
figure; imtool(gs);
[I,J]= find(g == max(g(:)))

wobei hier w das gesuchte Muster und f das Gesamtbild ist. In I und J stehen dann nachher die Koordinaten (I=Y, J=X, weil Matlab spaltenweise arbeitet).
Das ganze in fertiger Form für Delphi kenne ich leider nicht, aber wenn dich das bisher nicht abgeschreckt hat: Zumindest zur Theorie dahinter hab ich noch ein wenig rumfliegen.

Das klingt ja schonmal genial ...

Würde mich interessieren, was du noch so zum Thema hast. Und vllt kannste ja sogar eine Beispielfunktion in FPC basteln ??

Und was macht diese "Ähnlichkeitssuche" genau ?. Wandelt sie das Bild in ein verainfachtes Format um, und vergleicht gefundene Muster und formen ? Oder geht die im Endeffekte jeden Pixel durch und vergleicht ?

Danke schonmal.

~stiftII

[himitsu]

Zitat von shmia:

Zitat von freeway:

man kann jedes Pixel auslesen, man kann aber auch scanline verwenden (schneller)

Kommt drauf an, ob der Algorithmus es erlaubt sich im Bitmap horizontal zu bewegen.

Auch bei Scanline kann man ist man nicht auf eine horizontale Bearbeitung beschränkt.

- vorher in einem Pointer-Array alle Scanlines zwischenspeichern und schon hat man eine Art zweidimensionales Array

- sich den Zeiger auf die letzte Scanline holen (diese Bitmaps werden von unten nach oben gespeichert) und schon kann man über eine Art eindimensionales Array drauf zugreifen (alle Zeilen hintereinander)

[Aphton]

xD
Genau dies habe ich implementiert und warte nun auf seine Antwort auf meine letzte Frage ^^ (+SAD, einfach und langsam)

[bernhard_LA]

der Algorithmus zum Finden eines Suchbildes in einer großen Vorlage ist :
NORMALIZED CROSS CORRELATION - BZW. FAST NCC

unter http://sourceforge.net/projects/nccfastncc/ gibt eine Demo Application dazu in DELPHI.
Für unser Testbild benötigt die Version auf Source forge ~ 30 sec auf meinem Laptop, aktuell haben wir eine optimierte Version von FAST NCC entwickelt, die Suche
geht ca. 500 x schneller, dh. ist aber aktuell kein Open Source code. Falls Di ein Suchprojekt bearbeitest reicht Dir event. die Public Version des Algorithmuses.