Bild in Bild suche
-
P.S.: Was mir grad so auffällt ein Haufen dieser Klammern sind natürlich überflüssig. Aber für stilistisches wie Klammer und Variablennamen ist es Heute schon zu spät.
-
Hi.
Das kannst Du enorm beschleunigen. Arbeite mal etwas dran. ...vielleicht kriegst Du nen Faktor 100 raus.
-
if (a.GetPixel(xg, yg) == b.GetPixel(1, 1)) { //Bild vergleichen for (int x = 1; x < b.Width; x++) { for (int y = 1; y < b.Height; y++) { if (a.GetPixel(x + xg, y + yg) != b.GetPixel(x, y)) found = false; } } if (found == true) { return true; } }hier kannst du irgendwo ein break einbauen, dann geht das schonmal wesentlich schneller
-
GetPixel ist langsam - mach Lock Unlock und mach gebrauch von unsafe und Zeigern.... (dazu gibt es einige Tutorials zu finden)
-
...danke erst mal für eure Anregungen.
Ich hab jetzt mal zwei Sachen gemacht. Zum einen wie vorgeschlagen
breakseingebaut. beschleunigt die Sache natürlich enorn.
Zum anderen das auch mal auf MFC/ATL Basis gebaut. Was die Sache ein ganzes Stück schneller macht. Faktor 10.
Was natürlich noch interessant wäre direkt über
#include "gdiplus.h"mit der GDI zu sprechen ohne wie bei MFC/ATL erst mal riesen Objekte aufzuziehen. Das sollte auch schlanker sein. Aber ich check das mir hdc und HBitmap net so ganz.
Die Thematik Zeiger ist natürlich interessant um das GetPixel zu umgehen. Bin mir aber ehrlich gesagt nicht ganz im klaren wie das im Quellcode dann laufen soll.
Meld mich wieder und bin für Anregungen/Kritik immer offen.
Will den Code natürlich nicht schuldig bleiben, damit vielleicht auch jemand in der Zukunft eine Anregung hat.
Code C#:
using System; using System.Collections.Generic; using System.Text; using System.Diagnostics; using System.Drawing; namespace netgdi { class Program { static bool PictureSearch(String DatNameGroß, String DatNameKlein) { bool found = true; Bitmap a = new Bitmap(DatNameGroß); Bitmap b = new Bitmap(DatNameKlein); if (a.Height > 2147483647 || b.Height > 2147483647 || a.Width > 2147483647 || b.Width > 2147483647) { Console.WriteLine("Mindestens eines der Bilder überschreitet die zulässige Kantenlänge von 2147483648 Pixel"); return false; } //Das kleine Bild durchs große schieben. for (int xg = 1; xg < a.Width - b.Width; xg++) { for (int yg = 1; yg < a.Height - b.Height; yg++) { found = true; //Wenn erstes Pixel übereinstimmt if (a.GetPixel(xg, yg) == b.GetPixel(1, 1)) { //Bild vergleichen for (int x = 1; x < b.Width; x++) { if (!found) break; for (int y = 1; y < b.Height; y++) { if (a.GetPixel(x + xg, y + yg) != b.GetPixel(x, y)) { found = false; break; } } } if (found) return true; } } } return false; } static void Main(string[] args) { Stopwatch g = new Stopwatch(); g.Reset(); g.Start(); bool found; found = PictureSearch("C:\\g.bmp", "C:\\h.bmp"); g.Stop(); Console.WriteLine("found: " + found.ToString()); Console.WriteLine(g.Elapsed.ToString()); Console.ReadLine(); //Performance Messungen: Zeit: //Bild und Code wie im Forum 45,9976860 sec. //Breaks eingebaut 16,9239073 sec. //Release Version 16,8552746 sec. //Dotfuscated 16,6906531 sec. } } }Code MFC/ATL:
#include "stdafx.h" #include <time.h> #include <winerror.h> #include <afxwin.h> #include <atlimage.h> int _tmain(int argc, _TCHAR* argv[]) { double time1, tstart; tstart = clock(); printf_s("Start der Anwendung...\n"); CImage a; CString FNG = _T("C:\\g.bmp"); if(a.Load(FNG) == S_FALSE) printf_s("Bild konnt nicht geladenwerden\n"); CImage b; CString FNH = _T("C:\\h.bmp"); if(b.Load(FNH) == S_FALSE) printf_s("Bild konnt nicht geladenwerden\n"); bool found; bool found2 = false; //printf_s("%i",a.GetHeight()); for (int xg = 1; xg < a.GetWidth() - b.GetWidth(); xg++) { for (int yg = 1; yg < a.GetHeight() - b.GetHeight(); yg++) { found = true; //Wenn erstes Pixel übereinstimmt if (a.GetPixel(xg, yg) == b.GetPixel(1, 1)) { //Bild vergleichen for (int x = 1; x < b.GetWidth(); x++) { if (!found) break; for (int y = 1; y < b.GetHeight(); y++) { if (a.GetPixel(x + xg, y + yg) != b.GetPixel(x, y)) { found = false; break; } } } if (found) found2=true;; break; } } } time1 = clock() - tstart; time1 = time1/CLOCKS_PER_SEC; printf_s("%f\n", time1); printf_s("Ende der Anwendung...\n"); printf_s("%i\n",found2); return 0; } //Dauer ca. 2 sek.
-
Hallo hatte das slebe Problem und konnte auch kein besseres ergebniss mit C# erzielen.
wie kann man denn eigentlich mit der GPU Programmieren ?
kann ja nicht sein dass unsere Rechner gigantische Leistungen erziehlen und bei so einer Aufgabe scheitern ???werdenachher mal kontrollieren ob meine Lösung langsamer oder schneller ist.
Habe anstatt die vielen GetPixel aufrufe zwei int[,] gemacht,
das File in einem Memory Stream eingelesen, über jede Koordinate gelooped, und mir die dazu passenden bytes aus dem Stream gesucht.Allerdings braucht die ganze Prozedur ~9 sekdunden bei einem 800 * 600 er File -
für die SUche brauch ich dann ~ satte 22 sekunden
-
Hmm, ist dafür die GPU tatsächlich geeignet?
Irgendwie sieht der Algorithmus für mich nicht so richtig parallelisierbar aus. Das einzige, was man vielleicht per Shader machen kann wäre der Vergleich der Kanditaten.
Für Bilder mit großen, abstrakten Objekten (und wenn es unscharf sein darf) ist man wahrscheinlich am Besten dran, wenn man beide Bilder vektorisiert und dann vergleicht. Das verringert doch die Datenmenge erheblich.
-
Schön das sich noch jemand zu dem Thema eingefunden hat. Ich konnte das die letzten Tage leider nicht verfolgen.
Die Parallelisierbarkeit sehe ich bei den Schleifen.
Das durch die GPU rechnen zu lassen ist natürlich ein interessanter Aspekt. Ein Ansatz wäre dann OpenGL bzw. DirectX. Ist eine Grafikarte dafür überhaupt Leistungsfähig genug?
P.S.: Ich hab mir das mit Lock/Kopieren/Zeiger schon mal Literaturmäßig reingezogen und werd' das die nächsten Tage umsetzen und posten.
-
Drei Sachen versteh ich hieran nicht:
for (int xg = 1; xg < a.GetWidth() - b.GetWidth(); xg++) { for (int yg = 1; yg < a.GetHeight() - b.GetHeight(); yg++) { found = true; //Wenn erstes Pixel übereinstimmt if (a.GetPixel(xg, yg) == b.GetPixel(1, 1)) { //Bild vergleichen for (int x = 1; x < b.GetWidth(); x++) { if (!found) break; for (int y = 1; y < b.GetHeight(); y++) { if (a.GetPixel(x + xg, y + yg) != b.GetPixel(x, y)) { found = false; break; } } } if (found) found2=true;; break; } } }1. Das letzte break gilt immer
2. Warum fängst du immer bei 1 an
3. Aus der äußersten Schleife springst du beim finden nicht raus.. Hast du das überhaupt getestet?
-
1: Parallisierung:
Parallelisieren lässt sich sowas auf jeden fall,
Bei einer 4 Core maschine könnte jeder Core 1/4 des Großen bildes analysieren.
Denke Theoretisch könnte man die Aufgabe auf extrem viele Threads aufteilen - aber bleiben wir mal realistisch - mehr als 16 Cores hat eh keiner.2: Grafikkarte
Ich hab keine ahnung ob und wie man eine GPU Programmieren kann ??
nur über shader ?? oder schreibt man da ein DirectX Modul ?
wie funktioniert denn die GDI Funktion BitBlt ? nutzt die nicht bereits eh die Grafikkarte?
hab in der GDI schon gesucht aber leider nichts von such oder bildvergleichsfunktionen gefunden.
Ich denke an Leistung mangelt es unseren Grafikkarten bestimmt nicht - wenn man an die aufwendigen Effekten aus den aktuellen Games denkt.
Ich versteh allerdings das grundlegende Konzept einer 3D-Karte nicht also kann ich wohl kaum mitreden.3: 64Bit
der dritte optimierungsansatz der mir einfällt wäre 64Bit Pozzis zu nehmen und
gleich mehrere Farben auf einmal zu vergleichen ( 2 + 2/3 Colors ?)
aber ich denke dass das wenig bringt da dieser vergleich ja nur einen kleinen Teil ausmacht und der große performancekiller dürfte wohl eher das Loopen über die x und y schleife sein.
Beim Check auf die Farben dürfte es ohnehin eher selten passieren dass er über mehr als 1 pixel looped.
Hier spielt die Tatsache wieviele Farben tatsächlich benutzt werden eine große rolle.Bei deinem Bild wo 2 Farben bentutzt werden wird der Check in den inneren Schleifen wohl sehr oft aufgehen.
Bei einem Foto mit Gesichtserkennung wird der Check wohl eher selten aufgehen.4: Farbtiefe runterschrauben.
Man beachte hierbei Punkt 3
wenn man ein Bild hat wo ohnehin nur der 16Bit farbraum (welche Variante des 16 Bit farbraums auch immer) genutzt wird kann man noch mehrere pixies auf einen schlag vergleichen. da gehen bei 64bittern schon 4 Pixels.
Bei monochrom gehen dann tatsächlich 64 Bit auf einen schlag!5:
Aus Strategie "Farbtiefe runterschrauben" resultiert folgender neuer Gedanke:
wenn man die Farbtiefe runterrechnet auf 8 bzw 1 Bit dann kann man mit 64 Bittern sehr viele Checks auf einen schlag machen.
Natürlich werden dann auch Grafiken matchen die dann bei genauerem hinschaun (Das Rot ist ja gar kein Rot sondern Rosa) dann nicht mehr matchen.In einem Scenario in dem man viele kleine Objekte im großen Bild sucht könnte der Rechenaufwand für das Runterrechnen, das grobe matchen und danach das matchen im originalfabraum eventuell tatsächlich ein Plus an Rechenzeit ergeben.
das Punkt 5 tatsächlich was bringt halte ich aber für sehr unwahrscheinlich.
Soviel zum Thema: "Primitives Problem"
Mir ist nun mittlerweile auch klar warum dieser
"Wenn du dich im Forum registrieren willst dann musst du die Buchstaben vom Bild abschreiben" - Schutz für Bots so schwer zu überwinden ist.
-
Wie ichs mir gedacht hab, ist die Klasse CImage mit den GetPixel-Aufrufen der Flaschenhals.
class ImageBitAccess { public: ImageBitAccess( const CImage& image ) : top_up(true) { bytes_per_pixel = image.GetBPP() / 8; width_in_pixel = bytes_per_pixel * image.GetWidth(); if ( (pitch = image.GetPitch()) < 0 ) { pitch = -pitch; top_up = false; } bits = (const char*)image.GetBits(); } const char* GetLine( int line ) { if ( top_up ) return bits + line*pitch; else return bits - line*pitch; } inline const char* GetPixelPtr( int line, int pixel ) { if ( top_up ) return bits + line*pitch + pixel*bytes_per_pixel; else return bits - line*pitch + pixel*bytes_per_pixel; } inline int GetWidthInBytes() { return width_in_pixel; } private: bool top_up; int width_in_pixel; int bytes_per_pixel; int pitch; const char* bits; }; int main() { double time1, tstart; tstart = clock(); printf("Start der Anwendung...\n"); CImage orig; CString FNG = _T("C:\\b.png"); if(orig.Load(FNG) == S_FALSE) printf("Bild konnt nicht geladenwerden\n"); CImage tofind; CString FNH = _T("C:\\a.png"); if(tofind.Load(FNH) == S_FALSE) printf("Bild konnt nicht geladenwerden\n"); bool found = false; // Sonst müssen wir so schräg mit halben Bits rumhantieren, hab ich // grad keine Lust zu :clown: // Zu beachten ist noch, dass bei 32 bpp die Alpha-Werte berücksichtigt werden if ( orig.GetBPP()<8 || tofind.GetBPP()<8 ) printf( "Format not supported!\n" ); else if ( orig.GetBpp() != tofind.GetBPP() ) printf( "Both pictures must have the same bpp-rate!\n" ); else { ImageBitAccess orig_img( orig ); ImageBitAccess find_img( tofind ); // Mit dem <= bin ich mir grad nicht sicher, vielleicht auch nur < for ( int yg=0; yg<=orig.GetHeight()-tofind.GetHeight() && !found; yg++ ) { for ( int xg=0; xg<=orig.GetWidth()-tofind.GetWidth(); xg++ ) { if ( *orig_img.GetPixelPtr(yg,xg) == *find_img.GetPixelPtr(0,0) ) { bool discarded = false; for ( int y=0; y<tofind.GetHeight(); y++ ) { if ( 0 != memcmp( orig_img.GetPixelPtr(yg+y,xg), find_img.GetPixelPtr(y,0), find_img.GetWidthInBytes()) ) { discarded = true; break; } } if ( ! discarded ) { printf( "Found at %i/%i\n", xg, yg ); found = true; break; } } } } } time1 = clock() - tstart; time1 = time1/CLOCKS_PER_SEC; printf("%f\n", time1); printf("%i\n",found); return 0; }So dauerts bei mir jedenfalls 0,1 statt 43 Sekunden
Ok, das hat ein paar Einschränkungen, z.B. müssen beide Bilder die gleiche Bpp-Rate haben. Da die meisten aber eh mit 24 daherkommen, soll das hier erstmal egal sein. Bzw sonst kann man ja immer noch auf die anderen Methode ausweichen
edit2: Wenn ich die Bilder vervierfache (von 242x205 auf 1210x1025 bzw von 92x61 auf 460x305), brauchts aber wieder 22 Sekunden. Wahrscheinlich müsste man für große Bilder Muster-Erkennung oder so einbauen
-
ich hab schon weit aus komplexere dinge auf nem pentiumMMX mit 233MHz schneller gesehen. da kann ich mal wieder meinen satz sagen: tauscht eure kristalkugeln gegen einen profiler ein, ansonsten koennt ihr 1024cpus nutzen und werdet weiterhin ewigkeiten fuer etwas benoetigen was andere software in echtzeit macht.