Autor Beitrag
IsNull
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 31.07.10 15:01 
Tönt ganz einfach, scheint es aber nicht zu sein.

Ich will Bilder vergleichen, dazu benötige ich einen byte Buffer der zu vergleichenden Bilder. (Daraus wird dann ein Hash gebildet und diese dann verglichen)
Ich scheitere jedoch schon daran, die Byte-Buffer zu generieren.

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
        public void DebugMethod(Bitmap uNeedleImage) {

            var NeedleBuf = BufferFromImage(uNeedleImage); //Erstellen des ByteBuffers

            var ImgCopy = new Bitmap(uNeedleImage); //Klonen des Bildes
            var NeedleBuf2 = BufferFromImage(ImgCopy); 
            //Eigentlich sollten die beiden Buffer "NeedleBuf" und NeedleBuf2 gleich sein. Die haben aber nicht mal die gleiche Länge... 

        }

        private byte[] BufferFromImage(Image img) {
            ImageConverter converter = new ImageConverter();
            return (byte[])converter.ConvertTo(img, typeof(byte[]));
        }

Da schon obiges Test Dingens nicht funktioniert, bin ich ziemlich ratlos.

Ich habe bei den Bitmaps verschiedene Eigenschaften, z.B. Horizontal Res ist unterschiedlich...



Konkret brauche ich das in folgender Funktion:
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
        private Bitmap Copy(Bitmap srcBitmap, Rectangle section) {

            Bitmap bmp = new Bitmap(section.Width, section.Height, Graphics.FromImage(NeedleImage));
            Graphics g = Graphics.FromImage(bmp);
            g.DrawImage(srcBitmap, 00, section, GraphicsUnit.Pixel);
            g.Dispose();
            return bmp;
        }

Die ist ironischerweise von MS selber, aber das liefert ein Bild mit komplett anderen Eigenschaften zurück :/ Und wenn die Eigenschaften unterschiedlich sind, dann ist es ja irgendwie verständlich, dass die Raw Bytes dies auch sind :)


Any idea?


Zuletzt bearbeitet von IsNull am Sa 31.07.10 18:30, insgesamt 1-mal bearbeitet
Christian S.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 20451
Erhaltene Danke: 2264

Win 10
C# (VS 2019)
BeitragVerfasst: Sa 31.07.10 15:44 
Hallo!

An die Bytes eines Bitmaps kommt am schnellsten so:
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
byte[] bytes;

var bmp = new Bitmap(@"d:\foo.bmp");
var bmpData = bmp.LockBits(new Rectangle(00, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, bmp.PixelFormat);
try
{
  bytes = new Byte[bmpData.Stride * bmp.Height];
  Marshal.Copy(bmpData.Scan0, bytes, 0, bytes.Length);
}
finally
{
  bmp.UnlockBits(bmpData);
}


Grüße
Christian

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 31.07.10 16:42 
Hi Christian,

Danke für deine Antwort, leider liefert deine Methode das gleiche Ergebnis wie die meine (Ich hab es btw. absichtlich nicht über InterOp gemacht), aber das ist unwichtig.

Vielleicht hilft dir der Debug-Snapshot hier mich besser zu verstehen:
[url=img339.imageshack.us...esearcherbuffer.png]user defined image[/URL]

Die beiden Buffer sind nicht mal gleich lang (das hier wurde mit deiner Methode gemacht)

Weiter sind auch die Unterschiede der beiden Bitmpas zu beachten, wo es sich doch eigentlich um Klone handeln sollte :(


ps: Das nochmalige zeichnen DrawImage(...) ist lediglich zu Testzwecken. Sollte ja nichts am verhalten ändern...

EDIT: Ich kann auch gerne das Test-Projekt hier hochladen, wenn es jemandem helfen sollte. Der Code ist anyway OpenSource.
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 31.07.10 16:55 
Christian meinte wahrscheinlich, dass du den Hash direkt nur aus den Pixelwerten berechnest[*]. Oder sind die anderen Eigenschaften auch wichtig?
Und wozu du für dein Problem überhaupt Bitmaps klonen musst, habe ich noch nicht verstanden.

[*]Edit: Dann aber am besten mit konstantem PixelFormat :) .

_________________
>λ=
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 31.07.10 17:03 
Hey Kha,

Es geht um folgendes:

In einem grossen Bild soll ein kleiners Bild gesucht werden. Die suche kann man nun Pixel für Pixel machen - das funktioniert und ist wahrscheinlich auch nicht anders möglich, wenn eine gewisse Variation der einzelnen Pixel erlaubt sein soll.

Ist die Variation aber = 0, dann sollte ein Vergleich mit Hashs viel Performance bringen. Falls da jemand bessere Ideen hat, nur her damit :)


Und warum nun klonen? Eigentlich muss ich nicht klonen, sondern aus dem grossen Bild kleine Bitmaps ausschneiden (siehe private Bitmap Copy(Bitmap srcBitmap, Rectangle section) Methode oben), welche die gleiche Grösse haben wie das NeedleImage.

Hier hab ich die gesammte bestehende Klasse hochgeladen:
pastebin.com/bA6xPeXt

Sry falls ich mich zu undeutlich ausdrücke, habe das Gefühl wir reden aneinander vorbei :D

lg
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 31.07.10 18:15 
Gut, so langsam wird die Sache klarer.

user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Ist die Variation aber = 0, dann sollte ein Vergleich mit Hashs viel Performance bringen.
Inwiefern? Du willst also einmal den Hash des Needle-Images berechnen und dann für jede mögliche Position mit dem Hash des entsprechenden Source-Ausschnitts vergleichen? Ich kann mir nicht vorstellen, wie das schneller als ein 1:1-Vergleich der Pixel sein soll.

user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Eigentlich muss ich nicht klonen, sondern aus dem grossen Bild kleine Bitmaps ausschneiden (siehe private Bitmap Copy(Bitmap srcBitmap, Rectangle section) Methode oben), welche die gleiche Grösse haben wie das NeedleImage.
Ausschneiden? Ich dachte, es ginge um Performance :D . Beim Vergleich einfach den Offset mit zu berücksichtigen dürfte wohl _etwas_ sparsamer sein.

_________________
>λ=
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 31.07.10 18:28 
Zitat:

Ich kann mir nicht vorstellen, wie das schneller als ein 1:1-Vergleich der Pixel sein soll.

Ich hab bei CodeProject einen Artikel gefunden (jetzt will ich ihn ums verrecken nicht mehr finden o.0), wo damit deutlich Performance gewonnen wurde.
Wird wohl damit zu tun haben, dass bei einem einzigen Pixel unterschied (was auch das letzte des Vergleiches sein kann) sich der Hash total ändert -> Im besten Fall ist dann schon das erste Zeichen der Hashe unterschiedlich, und damit viel schneller, als wenn alle Pixel durchgegangen werden, nur um beim letzten dann feststellen zu dürfen, dass dies doch verschieden ist. (Wenn ich ne CPU wär, würde mich sowas ja nerven, hehe :D)
Diese Überlegung setzt natürlich voraus, dass die Hash-Berechnung optimiert und sehr schnell abläuft, wovon ich jetzt einfach mal ausgehe.



Ich habe es jetzt mal über die Pixel-Werte probiert, was funktioniert, aber noch langsamer ist:
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
        private byte[] HashFromImage(Bitmap bmp) {
            int i = -1;
            byte[] ImagePixelBuffer = new byte[bmp.Size.Height * bmp.Size.Width * 3];

            Color Pix;
            for(int row = 0; row < bmp.Size.Height; row++)
                for(int col = 0; col < bmp.Size.Width; col++) {
                    Pix = bmp.GetPixel(col, row);
                    ImagePixelBuffer[++i] = Pix.R;
                    ImagePixelBuffer[++i] = Pix.G;
                    ImagePixelBuffer[++i] = Pix.B;
                    // evtl. Alpha Kanal auch noch beachten...
                }
            return HashFromBuffer(ImagePixelBuffer);
        }


Ich werde mal schauen, dass ich diese Geschichte nur einmal mit dem Source-Image machen muss, um dann über nen Index auf die Byte Arrays zuzugreifen. Ich passe mal den Thread-Titel an, ich glaube, Images vergleichen/ suchen trifft es besser.

gruss
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 31.07.10 19:28 
Du gehst also davon aus, dass zwei Array-Zugriffe langsamer sind als ein Array-Zugriff + Block Cipher der Hashfunktion. Na da bin ich mal gespannt :gruebel: .



user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Ich hab bei CodeProject einen Artikel gefunden (jetzt will ich ihn ums verrecken nicht mehr finden o.0), wo damit deutlich Performance gewonnen wurde.
Aber nicht der hier, oder? www.codeproject.com/...comparingimages.aspx

_________________
>λ=
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 31.07.10 20:08 
Ja der war es.

Zitat:

Du gehst also davon aus, dass zwei Array-Zugriffe langsamer sind als ein Array-Zugriff + Block Cipher der Hashfunktion. Na da bin ich mal gespannt .

Ich bin davon ausgegangen, weil ich mir vorstellen könnte, dass der CLI Ablauf (wenn man die Array-Zugriffe selber ausprogrammiert) langsamer ist als ein (etwaiger) nativer Aufruf der Hash Funktionen. Weiter auch aus dem vorhergenannten Grund, dass das eigentliche Vergleichen schneller ist, da sich die Hashe unabhängig von der Ähnlichkeit zweier Buffer bilden, und bei sehr ähnlichen so einen vorteil bringen mögen. Aber das waren schlicht (falsche) Annahmen, um mir den CodeProject Beitrag erklären zu können *g

Wenn dem nicht so ist, dann ist der erwähnte Beitrag auf CodeProject also falsch? Ich bin dankbar für jegliche Aufklärung :)

Siehst du mögliche Optimierung für eine suche abgesehen von der Pixel-für-Pixel Variante?
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 31.07.10 23:55 
user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Ich bin davon ausgegangen, weil ich mir vorstellen könnte, dass der CLI Ablauf (wenn man die Array-Zugriffe selber ausprogrammiert) langsamer ist als ein (etwaiger) nativer Aufruf der Hash Funktionen.
Naja, was ist schon ein Array-Zugriff, trotz CLR? Ein ">0"-Check, ein Upper-Bound-Check, Pointer addieren und dereferenzieren? Ich glaube, damit kann nicht einmal Adler-32 konkurrieren ;) . Und im Zweifelsfalle gäbe es ja immer noch echten Unsafe Code...

user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Wenn dem nicht so ist, dann ist der erwähnte Beitrag auf CodeProject also falsch?
Ja, komplett. Wie der erste Kommentar dort sagt, ist der Hash-Vergleich komplett überflüssig (im Gegensatz zu deinem Szenario, wo theoretisch ja etwas hätte bewirken können). Das ist letzten Endes nur ein wenig verblüfender Vergleich von GetPixel und ImageConverter - und da würde ich mein Geld weiterhin auf LockBits setzen ;) .

user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Siehst du mögliche Optimierung für eine suche abgesehen von der Pixel-für-Pixel Variante?
Hu, nicht gerade mein Fachgebiet. Algorithmen für so eine 2D-Suche kenne ich nicht, aber zumindest für die erste Zeile könnte vielleicht Knuth-Morris-Pratt helfen. Und je nach Art dieser Bilder haben die Object-Recognition-Leute sicher auch noch ein paar Tricks auf Lager.

_________________
>λ=
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: So 01.08.10 12:36 
Naja, mein Szenario ist in erster Linie sehr Dynamisch. Es wird ein beliebiges Bild auf dem Screen gesucht - das ist alles.
Das hier sind die Vorgaben: www.autohotkey.com/d...ands/ImageSearch.htm

Ich habe mir nun den Original C++ Source zu Gemüte geführt, aber der zaubert leider auch nicht - ist einfach schneller da nativ, wie es ausschaut.

EDIT: Naja, zumindest Multi-Threaded werde ich es machen, um auf aktuelleren Maschinen ein gutes Ergebnis zu erzielen.
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 07.08.10 11:22 
Meine aktuelle Implementation sieht so aus - falls es jemanden interessieren sollte, der ein ähnliches Problem lösen muss:

gitorious.org/~isnul...Extras/ImageSearcher

Sie nutzt Multi-Threading um Maximale Performance zu erreichen. Sollte jemande Kritik zum SuchAlgo oder zum Multithreading (Ist unter .NET Neulad für mich) haben wäre ich um eine kurze Nachricht dankbar, ich bin daran interessiert es möglichst perfekt zu machen :)
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 07.08.10 11:59 
Dein lock greift ins Leere, da durch die lokale Variable jeder Thread sein eigenes locker-Objekt besitzt. Aber wenn nicht unbedingt immer der erste Fund zurückgegeben werden muss, würde eine Race Condition an dieser Stelle doch eigentlich gar kein Problem darstellen.

Wo du bis jetzt aber eine riesige Race-Condition-Lücke aufhältst, ist der Aufruf von Provider.Next. Den zu synchronisieren dürfte aber zu viel Overhead erzeugen; statt einem pixelweisen Arbeitsschritt würde ich jeden Worker eher eine ganze Zeile auf einmal abarbeiten lassen. Mit Parallel.For wäre das Problem schon gelöst, aber falls ihr bei 2.0 bleiben wollt, sollte es auch Interlocked.Increment tun.

_________________
>λ=

Für diesen Beitrag haben gedankt: IsNull
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 07.08.10 12:30 
Danke für deine rasche Antwort.

Ich habe es ja schon fast befürchtet, dass ich im Threading nicht nicht all zuviel weis, daher bin ich umsomehr dankbar für dein Prüfendes Auge. :)
Ich habe mir den aktuellsten Stand im Bereich Threading schon angesehen und bin über Task gestolpert, was ich für passend hielt, aber aktuell kann ich nicht aus dem 2.0 ausbrechen.

Um das locker Problem zu lösen (typisch - das mit dem locker Objekt ist nämlich genau das was ich nicht so richtig begriffen hatte) muss das Locker-Object also global für alle Threads sichtbar sein - und demnach auch nur einmal auf Klassenebene instanziert werden, richtig?

Ich werde das mal mit deinen Tipps überarbeiten und mich wieder melden :)


EDIT:
Ist das so korrekt: (Locker ist ein privates Klassen Field und die klasse ist nur einmal instanziert)
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
        public Point? Next() {
            if(mDone)
                return null;
            Interlocked.Increment(ref mCurrent_X); // mCurrent.X++;

            if(mCurrent_X > mMaxMovement.Width) {
                lock(Locker) {
                    mCurrent_X = 0;
                }
                Interlocked.Increment(ref mCurrent_Y); //mCurrent.Y++;
                if(mCurrent_Y > mMaxMovement.Height) {
                    lock(Locker) {
                        mDone = true;
                    }
                    return null;
                }
            }
            return new Point(mCurrent_X, mCurrent_Y);
        }
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 07.08.10 12:53 
user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Um das locker Problem zu lösen (typisch - das mit dem locker Objekt ist nämlich genau das was ich nicht so richtig begriffen hatte) muss das Locker-Object also global für alle Threads sichtbar sein - und demnach auch nur einmal auf Klassenebene instanziert werden, richtig?
Exakt :) . Aber wie gesagt, wenn in FoundLocation selten auch mal das 2. oder 4. Ergebnis landen darf, wäre dort ein Lock nicht unbedingt nötig.

/add:



user profile iconIsNull hat folgendes geschrieben Zum zitierten Posting springen:
Ist das so korrekt: (Locker ist ein privates Klassen Field und die klasse ist nur einmal instanziert)
Nein, die gesamte Methode muss atomic sein. Wenn Code nur aus einer einzigen Operation besteht (wie bei meinem zeilenweisen Beispiel), kommt man über Interlocked oft um echte Locks herum. Bei deinem Code brauchst du aber einen Lock um den gesamten Methodenkörper, sonst können ungültige Zwischenzustände von außen beobachtet werden - und zum Beispiel Pixel übersprungen werden, weil zwischen Increment und return schon ein zweites Increment ausgeführt sein könnte.

_________________
>λ=
IsNull Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 97
Erhaltene Danke: 11


VS 2010, C#, AHK
BeitragVerfasst: Sa 07.08.10 13:14 
Hm stimmt auch wieder.
Dann werde ich es mal mit einem Lock machen. Deiner Meinung nach ist das Lock aber schlecht für die Performance, und ich sollte eher ganze Worker-Blöcke generieren, um möglichst wenig Overhead zu haben?
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Sa 07.08.10 13:32 
Auf meine Meinung würde ich da nicht groß achten, miss lieber selbst nach :) (deswegen auch die Frage nach dem Speedup).

_________________
>λ=