Bilder vergleichen

Page 1 of 2

10/11/2015 19:25 doromoro#1

Hi,

da ich im Internet nichts passendes finden konnte, muss ich nun doch einen Thread erstellen.

Wie kann ich meinem Programm sagen, dass er auf meinem Bildschirm(wenn m�glich auch in einem bestimmten bereich) nach einem Bild(welches auf meiner Festplatte liegt) suchen soll und wenn er dieses Bild gefunden hat, dann soll er mir die Koordinaten vom gesuchten Bild ausgeben.

Sorry wenn diese Frage auf epvp schon beantwortet wurde und ich den Thread nicht finden konnte.

Ich hoffe mir kann einer helfen.
Danke und Gr��e

10/11/2015 19:27 8lol823#2

Koordinate = Pfad?

Welche Sprache?

10/11/2015 20:06 doromoro#3

C#.
Dort wo sich das Bild auf meinem Bildschirm befindet, z.B. x=620, y=420

10/11/2015 20:17 .SkyneT.#4

Du k�nntest das ganz einfach selber programmieren indem du jeden Pixel der beiden Bilder vergleichst, jedoch ist das extrem langsam, desswegen w�rde ich in dem Fall einfach zu OpenCV (bzw. in c# emgu cv) greifen. Dort gibt es die MatchTemplate() Funktion welche ein Bild in einem anderen sucht.
(Bisschen googeln, dann findest du sicher ein paar Beispiele daf�r)

10/11/2015 20:44 qqdev#5

Quote:

Originally Posted by .SkyneT.

Du k�nntest das ganz einfach selber programmieren indem du jeden Pixel der beiden Bilder vergleichst, jedoch ist das extrem langsam, desswegen w�rde ich in dem Fall einfach zu OpenCV (bzw. in c# emgu cv) greifen. Dort gibt es die MatchTemplate() Funktion welche ein Bild in einem anderen sucht.
(Bisschen googeln, dann findest du sicher ein paar Beispiele daf�r)

Die wird nicht viel schneller sein, wenn man es nicht naiv implementiert. Template-Matching Algorithmen sind nicht schwer zu implementieren, wenn man sich damit auseinandergesetzt hat. Aber zu einer fertigen Bibliothek zu raten, ist sicherlich keine schlechte Idee.

10/11/2015 21:11 .SkyneT.#6

Quote:

Originally Posted by qqdev

Die wird nicht viel schneller sein, wenn man es nicht naiv implementiert. Template-Matching Algorithmen sind nicht schwer zu implementieren, wenn man sich damit auseinandergesetzt hat. Aber zu einer fertigen Bibliothek zu raten, ist sicherlich keine schlechte Idee.

Nat�rlich kann man das auch selber schreiben, es ist auch nicht unbedingt "schwer" und bestimmt eine gute �bung, wenn man jedoch vorankommen will, kann ich es mir sparen das alles hier:
[Only registered and activated users can see links. Click Here To Register...]
noch einmal zu implementieren :)

10/11/2015 21:22 qqdev#7

Mir ging es nur um das "extrem langsam". Das ist n�mlich falsch gewesen :D

10/11/2015 22:48 Daifoku#8

Auch hier kann ich den Boyer-Moore Algorithmus empfehlen... irgendwie kann man den f�r ne ganze Menge an Problemen nutzen.

Das Alphabet ist hier 0x00 bis 0xFF
Ben�tigt werden also zwei Arrays mit einer Gr��e von jeweils 255 (0xFF)
Der eine Array ist f�r die good-suffix Strategie, der andere f�r die bad-prefix Strategie
Verglichen werden die Hex-Werte von hinten nach vorne.
Wenn das aktuelle Zeichen c zu keinem Match f�hrt, wird die maximale Distanz MAX(goodSuffix[c],badPrefix[c]) �bersprungen und der Match-Vorgang beginnt von vorne.

10/11/2015 23:53 qqdev#9

^ Das musst du nochmal genauer erkl�ren. Was ist ein Match? Wie kommst du an die Koordinaten?

10/12/2015 00:18 Daifoku#10

Quote:

Algorithmus[Bearbeiten]
Das Muster wird am Anfang linksb�ndig unter den Text geschrieben und dann von rechts nach links Zeichen f�r Zeichen mit dem Text verglichen. Sobald ein Mismatch auftritt, berechnen zwei Heuristiken, wie weit das Suchmuster nach rechts verschoben werden kann.

Bad-Character-Heuristik
Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Zeichen des Musters nicht mit dem Zeichen des Textes �berein („Bad-Character“), wird im Muster nach dem letzten Vorkommen dieses Bad-Characters gesucht und das Muster soweit verschoben, bis beide Buchstaben �bereinander liegen. Existiert dieser Bad-Character nicht im Muster, wird das Muster um seine volle L�nge nach rechts verschoben. Es kann vorkommen, dass die Bad-Character-Heuristik eine Verschiebung des Musters nach links vorschl�gt. In diesem Fall wird um eine Position nach rechts geschoben.
Good-Suffix-Heuristik
Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Suffix des Musters mit dem Text �berein und tritt danach aber ein Mismatch auf, wird das Muster soweit nach rechts geschoben, bis ein Teilwort des Musters wieder auf das Suffix passt. Existiert das Suffix kein zweites Mal im Muster, wird das Muster um seine volle L�nge nach rechts verschoben.
Es kommt vor, dass die beiden Heuristiken unterschiedliche Verschiebungen berechnen. Der Algorithmus w�hlt immer das Maximum der beiden Vorschl�ge, um das Muster nach rechts zu verschieben.

Um das Vorgehen effizient zu gestalten, wird f�r beide Heuristiken in einem Vorverarbeitungsschritt jeweils eine Sprungtabelle errechnet. Die Sprungtabelle f�r die Bad-Character-Heuristik enth�lt f�r jedes im Suchmuster vorkommende Zeichen den Abstand von der Position des letzten Vorkommens im Suchmuster bis zum Ende des Suchmusters. Die Tabelle f�r die Good-Suffix-Heuristik enth�lt f�r jedes Teilmuster (von hinten aus gesehen) den Abstand vom Ende des Musters, ab dem es wieder im Muster vorkommt. Eine detailliertere Beschreibung des Algorithmus findet sich im entsprechenden Artikel in der englischen Wikipedia.

https://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus

Die Koordinaten kann man einfach zur�ckrechnen.
Ich gehe davon aus, dass hier der DeviceContext(getDC) genutzt wird um eine DI_RGB/DIB_RGB_COLORS Bitmap (24 oder 32 Bit) zu erhalten. Dies ist zumindest der schnellste Weg ein Bild zu erhalten.

die Bitmap ist im Format BGRBGRBGR... gespeichert. BGR ! nicht RGB ! Die Bitmap, die man �ber Bitblt(SRCCOPY) erh�lt, gibt die Farbwerte R�ckw�rts aus.
Zudem wird bei positiver h�he das Bild "auf dem Kopf" generiert..
W�hle eine Negative H�he um das Bild "richtig herum" im Speicher abzulegen.
Ausgehend davon erhalten wir ein pixel an der Position x,y durch die Formel:
(y* HaystackBreite + x )* Bittiefe / 8
HaystackBreite sei hier die Breite des gro�en Bildes.. also vermutlich die Desktopbreite.
Diese Gleichung kann man einfach Umstellen um das gew�nschte Ergebnis zu erhalten

10/12/2015 16:41 qqdev#11

W�rde ich pers�nlich nicht nehmen. Sieht deutlich komplizierter aus als die g�ngigen Verfahren. Trotzdem danke :)

10/12/2015 21:26 Daifoku#12

Naja, eigentlich ist das ein sehr einfacher Algorithmus... Da gibt es weitaus schwierigere.
Zudem sind die Zeiten, die der Algorithmus braucht, unschlagbar.
Was sind denn die g�ngigen Verfahren ? ...

Ich schreib grad ne DLL...
Werde die sp�ter hier ver�ffentlichen und n kleines tut schreiben.
Aktueller Progress:

header

Spoiler

Code:

class daiBot {
	/**
	Timing-Stats (@time)
	> bitmap-size: 640x1080
	> cycles: 1.000.000
	> CPU: 8 x 5.3GhZ  (4 modules with 2 cores each)
	> used clock_t to determine the elapsed milliseconds
	*/
public:
	/**
	*	Receives the HWND of @lpWindowName

	@author Daifoku
	@param lpWindowName The window name (the window's title). If this parameter is NULL, getHandle returns the desktop handle.
	@return	If the function succeeds, the return value is a handle to the window that has the specified window name.
	If the function fails, the return value is NULL
	*/

	static DAIBMDLL_API HWND getHandle(const wchar_t * lpWindowName);
	/**
	Creates the Bitmap structure
	cDC, hDC, BITMAPINFO
	uses CreateDIBSection

	@author Daifoku
	@example
	BYTE* pixels = NULL;
	BITMAPINFO * bmi = bitmap::initDeviceContext(windowHandle, hDC, cDC, (LPVOID*) &pixels);

	@param handle Handle to a window
	@param cDC initDeviceContext saves the compatible DC to cDC
	@param hDC initDeviceContext saves the DC to hDC
	@param pixels pointer to a pointer where all the pixels should be stored.

	@return BITMAPINFO
	*/

	static DAIBMDLL_API BITMAPINFO * initDeviceContext(const HWND & handle, HDC & hDC, HDC & cDC, void** pixels);
	/**
	Load all pixels into the hDC
	uses BitBlt to SRCCOPY all bits

	@author Daifoku
	@param bmi Bitmapinfo
	@param cDC compatible Device Context
	@param hDC Device Context
	*/
	static DAIBMDLL_API void loadBitmap(const BITMAPINFO & bmi, const HDC &hDC, const HDC &cDC);

	/**
	Saves @pixels into a bitmap

	@author Daifoku
	@time 2.3ms
	@param bmi Bitmapinfo
	@param filePath relative or absolute path, e.g. "image.bmp"
	@param pixels pixels to save
	*/
	static DAIBMDLL_API void saveBitmap(const BITMAPINFO &bmi, const char * filePath, const char* pixels);

	/**
	Gets the color of the pixel @x,@y

	@author Daifoku
	@time 0ms
	@param bmi Bitmapinfo
	@param pixels pixels to save
	@param x x-position of the pixel
	@param y y-position of the pixel
	*/
	static DAIBMDLL_API int getPixel(const BITMAPINFO &bmi, BYTE * pixels, const int x, const int y);
};

Anwendungsbeispiel

Spoiler

weitere Funktionen folgen noch

10/12/2015 22:47 qqdev#13

Quote:

Originally Posted by .SkyneT.

Nat�rlich kann man das auch selber schreiben, es ist auch nicht unbedingt "schwer" und bestimmt eine gute �bung, wenn man jedoch vorankommen will, kann ich es mir sparen das alles hier:
[Only registered and activated users can see links. Click Here To Register...]
noch einmal zu implementieren :)

Geh auf den Link von .SkyneT. und dann schau bei "Which are the matching methods available in OpenCV?"

Cool :)

10/12/2015 23:28 Daifoku#14

Da wird jedem Pixel ein normierter Werte �ber alle Pixel x', y' zugewiesen.
D.h. es werden (Breite * H�he)^2 Operationen verwendet. Riesen Ressourcenverschwendung f�r eine exact-match-suche.

openCV braucht also polynomielle Zeit.
Boyer Moore ist in linearer Zeit fertig.

Angenommen wir suchen keine 1:1 Kopie und es gibt Shader Variationen, dann kann man die Suche trotzdem noch in linearer Zeit implementieren, indem man jeden Pixel in einen Lab Farbwert konvertiert (das sind zwei Schritte. Umwandeln in XYZ(Multiplikation mit einer Konstante) und dann in Lab (Wieder eine Multiplikation))

Anschlie�end nutzen wir die Euklidsche Norm und vergleichen unser template (Ich �bernehme hier einfach mal die Bezeichnug von openCV, damit wir nicht durcheinander kommen) mit dem originalbild und verfahren mit BoyerMoore weiter.

Damit k�nnen wir identische, aber nicht zwangsweise gleiche Bilder, in linearer Zeit finden.

10/16/2015 18:19 qqdev#15

Quote:

Originally Posted by Daifoku

Da wird jedem Pixel ein normierter Werte �ber alle Pixel x', y' zugewiesen.
D.h. es werden (Breite * H�he)^2 Operationen verwendet. Riesen Ressourcenverschwendung f�r eine exact-match-suche.

openCV braucht also polynomielle Zeit.
Boyer Moore ist in linearer Zeit fertig.

Angenommen wir suchen keine 1:1 Kopie und es gibt Shader Variationen, dann kann man die Suche trotzdem noch in linearer Zeit implementieren, indem man jeden Pixel in einen Lab Farbwert konvertiert (das sind zwei Schritte. Umwandeln in XYZ(Multiplikation mit einer Konstante) und dann in Lab (Wieder eine Multiplikation))

Anschlie�end nutzen wir die Euklidsche Norm und vergleichen unser template (Ich �bernehme hier einfach mal die Bezeichnug von openCV, damit wir nicht durcheinander kommen) mit dem originalbild und verfahren mit BoyerMoore weiter.

Damit k�nnen wir identische, aber nicht zwangsweise gleiche Bilder, in linearer Zeit finden.

Wieso?

Page 1 of 2