C# Image Objekte vergleichen

[Backslash]

Interessant was ich da gepostet habe, hat mich selbst gerade etwas gewundert

Wenn du die Höhe oder Breite weißt kannst du natürlich per Modulo wieder die Koordinaten ausrechnen:
X = i mod Width
Y = floor(i / Width)

 

[Zhen]

Also ich glaub irgendwas mache ich falsch xD

Ich mach einen Screenshot, mache den zweiten... rechne mir die pixel aus (width * height) und gehe wie beschrieben mit den Zeigern durch (pic1ptr != pic2ptr => punkt1 = i, break), danach rechne ichs mir wie oben beschrieben aus (x1 = punkt1 % width, y1 = floor(punkt1 / width), aber ich bekomme stets das selbe ergebnis bei x und y!! bzw. beim ersten punkt ja nicht, aber beim zweiten schon.

wie auch immer ich post mal den code =D

for (int i = 0; i < pixelCount; i += 3) {
	if (pic1Ptr[i] != pic2Ptr[i]) {
		scanO = i;
		break;
	}
}

for (int i = pixelCount - 1; i > 0; i -= 3) {
	if (pic1Ptr[i] != pic2Ptr[i]) {
		scanX = i;
		break;
	}
}

x_1 = scanO % newBMP.Width;
y_1 = (int)Math.Floor((decimal)(scanO / newBMP.Height));

x_2 = scanX % newBMP.Width;
y_2 = (int)Math.Floor((decimal)(scanX / newBMP.Height));

das mit i-=3 ist nur pobeweise ob das dann schneller läuft =D
aber irgendwie brauche ich auf diese art und weise sogar noch länger zum prüfen als bei meiner ersten variante und die erste liefert immerhin ein richtiges ergebnis, aber das hier ist komplett fail xDDD

 

[Rossibaer]

Hallo Zhen,

ich habe mir sicher eine halbe Stunde den Code angeschaut und überlegt was genau du da machen willst. Ich verstehe nicht den Zusammenhang zwischen deinen Variablen left, right, top und bottom. Wäre gut wenn du mal die komplette Methode von deinem 1. Codebeispiel posten könntest. Ich wäre so naiv und würde einfach die Bytes, Pixel oder sonstwas als long Array betrachten und dann einfach solange durchlaufen lassen bis ein long nicht mehr mit dem Gegenstück des 2. Bildes übereinstimmt. Das Ganze in einer einzigen Schleife (keine Schachtelung von mehreren Schleifen) und schon sollte es funktionieren. Da ich aber mir nun beim besten Willen keinen Reim drauf machen kann was du mit den o.g. Variablen willst, wäre es gut mal die ganze Methode zu sehen und evtl. noch paar Infos zu bekommen wie du sie aufrufst.

Viele Grüße
Rossibaer

EDIT:
Meine kleinen Grauen Zellen arbeiten schon weiter, kann es sein, dass du nur den Teil verschicken willst der auch tatsächlich geändert wurde und deshalb den Anfang und das Ende in Form von Pixelkoordinaten suchst (also von oben nach unten und danach von unten nach oben)?

 

[Backslash]

Übrigens stimmt der alte Code wie ich gerade feststelle nicht, da ja von einem Format ausgegangen wird, welches 3 bytes (24bit) pro Pixel verwendet.

Also:

Bitmap pic1 = new Bitmap("D:\\bild1.jpg");
Bitmap pic2 = new Bitmap("D:\\bild2.jpg");

Rectangle imgSize = new Rectangle(0, 0, pic1.Width, pic1.Height);
BitmapData pic1Data = pic1.LockBits(imgSize, ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);
BitmapData pic2Data = pic2.LockBits(imgSize, ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);

int byteCount = pic1.Width * pic1.Height * 3;

DateTime start = DateTime.Now;
unsafe
{
  byte* pic1ptr = (byte*)pic1Data.Scan0;
  byte* pic2ptr = (byte*)pic2Data.Scan0;
  for (int i = 0; i < byteCount; i++)
    if (pic1ptr[i] != pic2ptr[i])
    {
      Console.WriteLine("ungleich bei {0} => {1},{2}", i, (i/3) % pic1.Width, (i/3) / pic1.Width);
      break;
    }
}
DateTime end = DateTime.Now;

pic1.UnlockBits(pic1Data);
pic2.UnlockBits(pic2Data);

TimeSpan dauer = end - start;

Console.WriteLine("fertig nach {0} -> {1}s {2}ms", dauer.ToString(), dauer.Seconds, dauer.Milliseconds);
Console.ReadLine();

Was bei mir auch funktioniert.

/edit: Math.Floor kann man sich sparen, da die Nachkommastellen einfach abgeschnitten werden, was dem ja entspricht.

 

[Rossibaer]

Hallo Zhen, ich habe jetzt mal mit Pointern ein wenig rumgespielt und komme auf ca 60ms für den Vergleich von 2 Bildern. Mein Rechner ist nicht der Schnellste, evtl. könnts bei dir schneller laufen:

Anhang anzeigen ScreenCapture.zip

Die eigentliche Klasse heißt "ScreenCapture" und die Methode wäre dann "AreScreensDifferent".

Ansonsten gehe ich da einen anderen Weg als du. Ich verwende kein LockBits, was evtl. schneller gehen könnte, da ich direkt den Speicher allokiere und zugreife ohne vorher das Bitmap zu locken. Schaus dir einfach mal an.

Viel Spaß
Rossibaer

PS: Der Rest ist nur Beiwerk, z.B. meine Klasse um Messungen durchzuführen...

Edit:

    unsafe public bool AreScreensDifferent(
      int* prev_screen, /* vorhergehender Screenshot (32 Bit Farbtiefe) */
      int* next_screen, /* nächster Screenshot mit (32 Bit Farbtiefe) */
      int pixel_count,  /* Anzahl der Pixel der Screenshots, einfach Höhe X Breite ausrechnen */
      int width,        /* Anzahl der Pixel einer Zeile, entspricht Breite der Screenshots */
      out int x1,       /* linke x-Koordinate des Ausschnitts */
      out int x2,       /* rechte x-Koordinate des Ausschnitts */
      out int y1,       /* obere y-Koordinate des Ausschnitts */
      out int y2)       /* untere y-Koordinate des Ausschnitts*/
    {
      x1 = int.MaxValue;
      x2 = int.MinValue;
      y1 = int.MaxValue;
      y2 = int.MinValue;
      int indx = 0;

      do
      {
        bool bPixelChanged = (*(prev_screen++) != *(next_screen++));
        int x = indx % width;
        int y = indx / width;
        x1 = ((bPixelChanged && x < x1) ? x : x1);
        x2 = ((bPixelChanged && x > x2) ? x + 1 : x2);
        y1 = ((bPixelChanged && y < y1) ? y : y1);
        y2 = ((bPixelChanged && y > y2) ? y + 1 : y2);
      } while (++indx < pixel_count);
      
      return x1 < int.MaxValue;
    }

 

[voodoo44]

Warum probierst du es nicht einfach mit nem MD5-Hash? Wenn sich IRGENDWAS geändert hat, dann siehst du das daran doch am schnellsten?

http://dotnet-snippets.de/dns/md5-hash-von-dateien-ermitteln-SID66.aspx

 

[Backslash]

Der Hash wird auch nicht schneller als O(n) berechnet.

 

[voodoo44]

Ist schön, dass das Errechnen des Hashs bei doppelter Bildgröße doppelt so lange braucht ...
Das sagt doch aber absolut NICHTS zur konkreten Zeit der Hasherzeugung aus.

 

[Backslash]

Stimmt. O-Notation ist unangebracht, da das Hashen (zumindest scheint es mir auf den ersten Blick so) auch in O(n) liegt.

Trotzdem macht das Hashen mehr als nur einmal alles zu lesen und zu vergleichen.

Habs mal mit einer 500MB Datei getestet, 2.0s mit direktem Vergleich, 2.5s mit MD5.

Nochmal theoretische Überlegungen:
Sind die Dateien unterschiedlich groß, was bei Bildern so gut wie immer der Fall sein wird, geht es natürlich noch viel schneller, unabhängig vom Vergleichsverfahren, da der Inhalt dann nicht gebraucht wird.
Sind die Dateien gleich groß aber unterscheiden sich ist das direkte Vergleichen auch deutlich schneller, da beim ersten Unterschied abgebrochen werden kann.

Der einzige Fall in dem Hashen Sinn machen würde wäre, wenn sich die Datei nur selten ändert, sehr groß, aber gleich lang ist. (Bei Bildern sehr unwahrscheinlich)

 

[voodoo44]

Das heißt, dass das hashen EINES Bildes 1.25s dauert?
Beim vergleichen müsstest du ja 2 Hashs erstellt haben ...

 

[Backslash]

Ok für große Dateien die sich in der Größe nicht unterscheiden hast du recht. (Hatte ich aber vorher schon gesagt)

Aber nochmal einige Überlegungen:
Die Dateigröße wird sich in den allermeisten Fällen sowieso unterscheiden was das Verfahren zum Vergleichen irrelevant macht. Das spielt hier trotzdem eine Rolle, da man sich nämlich dann auch die Hashberechnung spart. Dann muss man aber, sollte doch mal wieder die Dateigröße gleich sein, wieder zwei Hashes berechnen, was länger dauert als der direkte Vergleich.

Außerdem geht es ja immernoch um Bilder, man verliert also zusätzlich durch das Hashen noch die Möglichkeit die Stelle im Bild zu finden, an der der Unterschied auftritt.

Mein (bisheriges) Fazit: Für große Dateien, die sich in der Dateigröße nicht unterscheiden, weshalb man jeden Hash berechnet und deshalb pro neuer Datei nur noch einen Hash berechnen muss und der Vergleich deshalb schneller geht lohnt sich dein Vorschlag.
Für den hier verlangten Anwendungszweck mit Bildern hat jedoch der direkte Vergleich der Daten mehr Vorteile (Position) und ist in den meisten Fällen schneller (da nur selten überhaupt der Inhalt verglichen wird).

Und dann gibts noch Hashkollisionen, die sind aber zugegebenermaßen unwahrscheinlich genug.


/edit: Nochmal nachgedacht, es kommt wirklich auf den genauen Verwendungszweck an.
Werden sehr oft Screenshots gemacht (Änderungen seltener pro Bild) und liegen diese Daten direkt als Byte-Array (und unkomprimiert) vor, dann ist Hashen vermutlich schneller. Werden die Screenshots so selten gemacht, dass fast immer eine Änderung da ist, liegt diese vermutlich relativ oft in bestimmten Bildbereichen, wodurch man wieder mit direkten Vergleichen gewinnen könnte. (Und immernoch: man erfährt zusätzlich die Position der Änderung, also wichtig ob man diese braucht.)

 

[voodoo44]

Er schrieb aber nichts von "erkennen, WO sich was geändert hat" - er wollte einfach nur wissen, OB sich was geändert hat. Da sollte hashen deutlich schneller gehen. (in deinem Fall: 1.25s vs 2.0s)

 

[Backslash]

Wieso fragt er dann wie man aus dem Index die Koordinaten im Bild berechnet?

 

[voodoo44]

Ich weiß nicht mal, was er mit der Frage bezwecken will ...

 

[Rossibaer]

@voodoo44: Stell dir vor er will eine Software zur Fernsteuerung eines PC übers Netz realisieren, so ala VNC, Teamviewer etc.. Nun hat er das Problem, dass bei jedem Screenshot viel zu viele Daten anfallen, die über das Netz geschickt werden sollen. Also reduziert er die Übertragung der Screenshots nur auf das, was sich auch geändert hat, d.h. er schickt nur die Bildteile die sich ändern und übernimmt den Rest des Bildes aus dem vorhergehenden Screenshot. Um das zu machen, braucht er 1. den Teil der sich änderte als Ausschnitt und 2. die Position. Mit einem Hash ist das nunmal nicht möglich, da hier nur ermittelt wird, dass sich was änderte, aber nicht genau wo. Also bleibt da nur noch der direkte Vergleich um die erforderlichen Daten zu ermitteln.

Edit: Gerade eben fällt mir ein, das man auch die beiden Byte Array vergleicht, den Index einer Änderung einfach merken, Länge bestimmen und nur diese Bytes vom 2. Screenshot senden. Somit würde sich der zu übertragende Bildinhalt noch weiter reduzieren. Dürfte auch nicht unbedingt langsamer werden, da hier die Arrays nur einmal durchlaufen werden müssten. Die zu sendende Struktur bestünde dann aus Index, Länge und den Byte Daten, die definitiv kleiner sind als das ganze Rechteck eines Ausschnitts. Die Ermittlung der Koordinaten für x, y, Länge und Breite würden entfallen.

Edit: Wenn du die Bildarrays, statt als (byte*) dann noch als (long*) interpretierst werden in einem Vergleich dann 8 Byte auf einmal verglichen, was dem Ganzen nochmal einen Schub bzgl. Geschwindigkeit geben würde.

 

[Zhen]

1. tut mir leid, dass ich mich übers WE nicht melden konnte. Mein I-net Anschluss kommt erst in knappen zwei wochen

@Rossibaer: du hast es genau erkannt. Das ganze dient tatsächlich einer Fernsteuerungssoftware.

Genau deswegen muss auch alles schnell ablaufen und der Traffic darf nicht zu hoch anfallen. Das mit dem Byte-Array (bzw. long) ist echt ne super Idee. Werd mich mal damit spielen, mal schauen ob und wie ichs hinkriege =)

Meine derzeitige Funktion für das Übermitteln der Änderung benötigt zwischen 120 ms und (hin und wieder sogar) 400/500 ms. Im Schnitt dürfte es jedoch bei etwa 150-200 ms sein. Hab jetzt jedoch herausgefunden dass allein schon die Funktion für den Screenshot 70-90 ms benötigt.

Daher gehe ich mal davon aus, dass die Funktion für das Ermitteln der Änderungen (und anschließendes versenden) mit seinen 50 ms sogar noch relativ gut dabei ist =D

Die Methode mit dem Long-Array werd ich aber wirklich mal ausprobieren. Hoffentlich bringt es wirklich nen Vorteil was die Geschwindigkeit und den Traffic angeht.

PS: mein Prozessor ist auch extrem lahm die Kiste hat schon einiges auf dem Buckel. AMD Athlon XP 2600+ mit gerade mal 1,91 Ghz.


Edit: Also irgendwie raff ich den Fehler in diesem Code nicht. Ich hab alles genauso wie bei Backslash, aber er spuckt mir trotzdem stets ne Exception aus ("Es wurde versucht im geschützten Speicher zu lesen oder zu schreiben...")

BitmapData pic1Data = newBMP.LockBits(new Rectangle(0, 0, newBMP.Width,
	newBMP.Height), ImageLockMode.ReadOnly, newBMP.PixelFormat);
BitmapData pic2Data = prevBMP.LockBits(new Rectangle(0, 0, prevBMP.Width,
	prevBMP.Height), ImageLockMode.ReadOnly, prevBMP.PixelFormat);

int X1 = 0;
int X2 = 0;
int Y1 = 0;
int Y2 = 0;
int breite = 0;
int hoehe = 0;

int pixelCount = newBMP.Width * newBMP.Height * 4;

unsafe {
	byte* pic1Ptr = (byte*)pic1Data.Scan0;
	byte* pic2Ptr = (byte*)pic2Data.Scan0;

	for (int i = 0; i < pixelCount; i++) {
		if (pic1Ptr[i] != pic2Ptr[i]) {
			X1 = (i / 4) % newBMP.Width;
			Y1 = (i / 4) / newBMP.Width;
			break;
		}
	}

	for (int i = pixelCount-1; i > 0; i--) {
		if (pic1Ptr[i] != pic2Ptr[i]) {
			X2 = (i / 4) % newBMP.Width;
			Y2 = (i / 4) / newBMP.Width;
			break;
		}
	}

	breite = X2 - X1;
	hoehe = Y2 - Y1;
}

Er spuckt mir die Exception übrigens bei der ersten If-Anweisung aus. Hat jemand ne Idee wieso? Mir gehts grad einfach darum, dass ich versteh worin da der Fehler liegt, weil ich zur Zeit wirklich keinen sehe

 

[Backslash]

Wieso int pixelCount = newBMP.Width * newBMP.Height * 4; ?

 

[Zhen]

na weil ich ja kein 24 bit sondern ein 32 bit screenshot hab.
bei 24 bit nimmst du es ja mal 3 also sollte es bei meinem fall ja mal 4 sein oder verstehe ich da grad was falsch?

 

[Backslash]

Hmm sollte passen. Wundert mich aber trotzdem. Wie genau machst du den Screenshot?

 

[Zhen]

Also um den Screenshot zu machen benutze ich die Lib von Codeproject (http://www.codeproject.com/KB/cs/DesktopCaptureWithMouse.aspx). Ist eigentlich auch nichts anderes als ein Wrapper auf die WinAPI. Das Ergebnis weise ich ner Bitmap zu:

Bitmap newBMP = ScreenCapture.CaptureDesktop();
//weiterer Code
prevBMP = newBMP;