[C#] Bilder vergleichen

[doromoro]

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

[8lol823]

Koordinate = Pfad?

Welche Sprache?

[doromoro]

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

[.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)

[qqdev]

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.

[.SkyneT.]

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:

noch einmal zu implementieren

[qqdev]

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

[Daifoku]

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.

[qqdev]

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

[Daifoku]

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

[qqdev]

Würde ich persönlich nicht nehmen. Sieht deutlich komplizierter aus als die gängigen Verfahren. Trotzdem danke

[Daifoku]

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

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

#include "stdafx.h"
#include "daiBot.h"
#include <iostream>  //std::cout | std::cin in main()
#pragma comment(lib,"daiBot")

int main()
{
	//Declarations
	HDC cDC, hDC;
	BYTE* pixels = NULL; //holds the pixels

	//Get a Handle
	//use bitmap::getHandle(NULL) to get the DesktopWindow
	HWND windowHandle = daiBot::getHandle(L"BlueStacks App Player");
	
	//Get the bitmap corresponding to @windowHandle
	BITMAPINFO * bmi = daiBot::initDeviceContext(windowHandle, hDC, cDC, (LPVOID*) &pixels);
	
	//loading the bitmap into the context 
	//(Not needed here, because initDeviceContext already loads the image into the context)
	//But if you want to reload the image to a different time, you have to call it like this.
	daiBot::loadBitmap(*bmi, hDC, cDC); // 2.3 ms per run

	//Analyze pixels here...
	//color at position x=120,y=954
	int myPix = daiBot::getPixel(*bmi, pixels, 120, 954); // 0.0 ms per run (instant)
	std::cout << myPix;
	std::cin.get();

	//Saving the image. 
	//you might want to manipulate the pixels before saving
	daiBot::saveBitmap(*bmi, "image.bmp", (char*)pixels);
    return 0;
}

weitere Funktionen folgen noch

[qqdev]

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:

noch einmal zu implementieren

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

Cool

[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.

[qqdev]

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?