C# Image Objekte vergleichen

[NetCrack]

Hi liebe Coderfreunde,
ich habe folgendes Problem: ich hab ein kleines Programm mit einer Funktion mit der ich Bilder (Instanzierte Image Objekte) vergleichen kann. Ursprünglich bin ich die Pixel durchgegangen und hab diese verglichen - dass funktioniert gut, kommt aber aus Performancegründen nicht in Frage. Dann hab ich die zu vergleichenden Objekte in ByteArrays zerlegt und den SHA256 Hash darüber verglichen. Das funktioniert schnell und gut, jedenfalls solange man das Bild nicht serialisiert. Ich habe die Bilder quasi in ner Art Containerobjektklasse, die ich komplett zu byte serialisiere. Beim deserialisieren ändert sich allerdings das Bytearray des Image Objektes so dass auch der Hash sich ändert und das geladene Bild vom System für ein neues gehalten wird.
Hat also jemand einen Vorschlag für eine Bildervergleichsmethode, die performant, serialisierungssicher und nicht alszu kompliziert zu implementieren ist?

Viele Grüße
netcrack

 

[andr_gin]

Wie hast du denn die Pixel verglichen? GetPixel ist hier ziemlich langsam. Ich würde hier eher mit Lockbits arbeiten. Das hat aber das Problem, dass es mit einem Indexed PixelFormat nicht zurecht kommt.

 

[NetCrack]

Danke für die schnelle Antwort. Jo genau halt mit zwei for-schleifen jeweils GetPixel nach x und y durchgeloopt und verglichen. Mit Lockbits hab ich noch net gearbeitet, haste da n Tutorial o.ä. zur Hand?

 

[GuardianAngel]

vllt hilft dir das:

http://www.codeproject.com/KB/graphics/cbir.aspx

von http://www.mycsharp.de/wbb2/thread.php?postid=278832

 

[NetCrack]

Die FFT zum vergleichen heranzuziehen is in der Tat keine blöde idee . Das werd ich nachher ma ausprobieren, aber wenn sonst noch Vorschläge sind gerne immer her damit.

 

[Gluehwurm]

Dumm nur, dass die FFT den Aufwand O(n log(n)) hat, die Traversierung eines Bildes aber O(n). Ehrlich gesagt, verstehe ich auch nicht, warum eine Hash-Berechnung performanter sein soll als das simple Traversieren des Bildes (es sei denn, es existiert eine Hardwareunterstützung für die Hashberechnung). Ich denke du verwendest ganz einfach eine unperformante Methode um an die Pixeldaten zu kommen. Idealerweise sind die Daten sequentiell in einem Array abgelegt. Das Durchlaufen dieses Arrays ist dann imho die schnellste Möglichkeit (Boundary-Checks müssen natürlich aus sein) Bilder zu vergleichen. Durch die Verwendung von statistischen Verfahren kann man sich vll. ein paar Pixel sparen, aber um eine 100%ige Aussage zur Gleichheit von Bildern zu treffen muss man leider alle Pixel durchgehen.

Also bleib bei deinem ersten Ansatz (alle Pixel durchgehen), alles andere ist imho Quatsch. Ich lass mich aber gerne korrigieren.

 

[InkognitoGER]

Hi,

mein erster Einfall wäre folgende Methode.

private Boolean AreBitmapEqual(Bitmap pictureOne, Bitmap pictureTwo)
{
if (Bitmap.ReferenceEquals(pictureOne, pictureTwo)) return true;
if (!pictureOne.Width.Equals(pictureTwo.Width))return false;
if (!pictureOne.Height.Equals(pictureTwo.Height))return false;
if (!pictureOne.PixelFormat.Equals(pictureTwo.PixelFormat) )return false;

try
{
ImageConverter converter = new ImageConverter();
Byte[] imageBytesOne = new Byte[1];
Byte[] imageBytesTwo = new Byte[1];

imageBytesOne = (Byte[])converter.ConvertTo(pictureOne, imageBytesOne.GetType());
imageBytesTwo = (Byte[])converter.ConvertTo(pictureTwo, imageBytesTwo.GetType());

SHA256Managed sha = new SHA256Managed();
Byte[] imageHashOne = sha.ComputeHash(imageBytesOne);
Byte[] imageHashTwo = sha.ComputeHash(imageBytesTwo);

for (int i = 0; i < imageHashOne.Length && i < imageHashTwo.Length; i++)
{
if (!imageBytesOne.Equals(imageBytesTwo))
return false;
}

return true;
}
catch (Exception ex)
{
MessageBox.Show(ex.Message);
return false;
}
}

 

[NetCrack]

@Glühwurm, warum die Hashberechnung im einzelnen Schneller ist kann ich dir auch nicht sagen, allerdings hab ich das getestet und rausgekommen ist dass die Hashes um den faktor 5-8 schneller berechnet werden als die Pixel durchzugehen. Die Pixel hab ich .NET-nativ über Bitmap.GetPixel() rangeholt (gibt glaub ARGBColor zurück.) Wie würdest du sie denn ranholen? Die Bilder in nen sequentielles Array zu packen würde ja bedeuten sie in Byte umzuwandeln, das is aber zum vergleichen nicht zweckdienlich da sich das entsprechende byte array wie gesagt bei serialisierung und deserialisierung ändert, warum weiß ich nicht.
@Ingoknito Ja ziemlich genau so sieht meine Funktion auch aus, leider besteht da dass Problem, dass sich das Byte Array, aus gründen die sich mir nicht erschließen, nach Byte-Serialisierung ein andere ist als zuvor, es ist aber zwingend erforderlich dass ich die Image Objekte ex/importieren kann, daher ist die Methode leider nicht zweckdienlich, es sei denn jemand erklärt mir wie ich die dinger serialisiere ohne dass sich das entsprechende ByteArray ändert (das Bild sieht auch deserialisiert genau noch so aus wie vorher).

 

[Gluehwurm]

Die Bilddaten liegen bereits in einem linearen Array vor. Schau dir mal das hier an

http://www.bobpowell.net/lockingbits.htm

Viele Bildbiliotheken (oder auch .NET) stellen eine Methode wie GetPixel(int i, int j) zur Verfügung. Aus diesen Indizes muss nun die Position im Array berechnet werden. Das geschieht z.B. durch die Formel

Pos = j*SIZE_Y + i

wenn der erste Bildpunkt den Index (0,0) hat. Diese Berechnung beinhaltet also eine Multiplikation und eine Addition. Und das kann durchaus kosten. Hinzukommt, dass ein Methodenaufruf aus Betriebssystem-technischer Sicht auch Overhead verursachen kann. Wie das jetzt in C# für GetPixel() aussieht kann ich auf Anhieb nicht sagen.
Also solche Methoden wirklich NUR in absoluten Ausnahmefällen verwenden wenn sich der direkte Zugriff auf den Array nicht verwirklichen lässt.

\edit
Ach ja, ich trau mich fast wetten, dass die Hashberechnung auf dem Array erfolgt

 

[NetCrack]

Ne die Hashberechnung erfolgt wie oben von InkognitoGER beschrieben über byte arrays aus dem ImageConverter. Danke für den Tip, aber irgendwie will die Variante mit den lockingbits bei mir net so richtig, ich bekomm Programmabstürze ohne Exception. Ich werd mich wohl für ne wahrscheinlichkeitsbasierte Variante entscheiden. Ich hab festgestellt dass die Abweichung zwischen originalen und deserialisierten Images maximal 5% beträgt über das Byte Array betrachtet. Der Vergleich ist mit etwa 3ms pro Operation zwar doch etwas langsamer als SHA256 Vergleich (1ms) aber immer noch bedeudent schneller als vergleich mit GetPixel() (~25ms). Ma gucken ob sich das praktisch durchsetzt.

 

[Gluehwurm]

Ne die Hashberechnung erfolgt wie oben von InkognitoGER beschrieben über byte arrays aus dem ImageConverte

Naja, der ImageConverter wird den Byte-Array aus dem Datan-Array des Bitmaps "berechnen" und nicht über die GetPixel() Methode.
Auf jeden Fall werden die Bilddaten im Speicher als eine Folge von Bytes (wer hier Bits will: OK, ändert aber nix an der eigentlichen Sache) abgelegt. Und um Festzustellen, ob 2 Bilder den identischen Inhalt haben muss man einfach ALLE Bytes auf Gleichheit überprüfen. Schluss aus. Einen Umweg über Hashes oder sonstwas brauchts da nicht, denn da sind zusätzliche Berechnungsschritte notwendig und die Performance geht in den Keller (mit der Prämisse, dass keine Hardwareunterstützung für diese Berechnungsschritte verfügbar ist) und es müssen trotzdem ALLE Bytes untersucht werden.
Wie du die Byte-weise Überprüfung auf Gleichheit ausführst ist dir überlassen, ein logisches AND würde sich da anbieten.

Ich werd mich wohl für ne wahrscheinlichkeitsbasierte Variante entscheiden. Ich hab festgestellt dass die Abweichung zwischen originalen und deserialisierten Images maximal 5% beträgt über das Byte Array betrachtet

Ähhm, was? Ich dachte du bist an der "GLEICHHEIT" von 2 Bildern interessiert (jeder Pixel in Bild1 entspricht EXAKT dem korrespondierenden Pixel in Bild2). Oder verstehe ich dich hier komplett falsch? Wenn du an der "ÄHNLICHKEIT" von 2 Bildern interessiert bist ist die Problemstellung eine komplett andere.

 

[NetCrack]

Probier's aus - die Berechnung über die Hashes ist schneller als das durchloopen durch die Arrays und das vergleichen der einzelnen Elemente. Frag mich nicht warum, aber es ist so.
Die Bilder sind absolut Gleich (laut GetPixel() Methode), die Abweichung ist anscheinend in den Metadaten, insofern passt das schon.

 

[Gluehwurm]

Probier's aus - die Berechnung über die Hashes ist schneller als das durchloopen durch die Arrays und das vergleichen der einzelnen Elemente.

Wie vergleichst du die einzelnen Elemente? Über RGBA oder Byte(Bit)-weise? Ich vermute noch immer das 1te bzw. keinen AND operator.

Die Bilder sind absolut Gleich (laut GetPixel() Methode), die Abweichung ist anscheinend in den Metadaten, insofern passt das schon.

Ich denke, dass diese Metadaten nichts mit dem eingentlichen Bildinhalt zu tun haben, sondern mit dem C# Bildobjekt (oder einer Instanz davon wenn man das so nennen will).

Ich weiss nicht ob ich mich klar genug ausgedrückt habe: Suche/implentiere Methoden um zwei Byte-Arrays auf Gleichheit zu überprüfen, und das performant.

 

[NetCrack]

Wie bereits beschrieben, es werden die Byte Arrays verglichen und nicht die ARGB werte ...

ImageConverter ic = new ImageConverter();
            byte[] btImage1 = new byte[1];
            btImage1 = (byte[])ic.ConvertTo(img1, btImage1.GetType());
            byte[] btImage2 = new byte[1];
            btImage2 = (byte[])ic.ConvertTo(img2, btImage2.GetType());
            int matches = 0, pixels = 0;

            if(btImage1.Length != btImage2.Length)
                return false;

            for (int i = 0; i < btImage1.Length; i++ )
            {
                if (btImage1[i] == btImage2[i]) matches++;
                pixels++;
            }

            double rate = matches/(double)pixels;
            if (rate < 0.95) return false;

            return true;

Die Alternative, die zwar schneller ist aber leider wie gesagt nicht für deserialisierte Bilder funktioniert ist:

            ImageConverter ic = new ImageConverter();
            byte[] btImage1 = new byte[1];
            btImage1 = (byte[])ic.ConvertTo(img1, btImage1.GetType());
            byte[] btImage2 = new byte[1];
            btImage2 = (byte[])ic.ConvertTo(img2, btImage2.GetType());
            int matches = 0, pixels = 0;

            if(btImage1.Length != btImage2.Length)
                return false;

            SHA256Managed shaM = new SHA256Managed();
            byte[] hash1 = shaM.ComputeHash(btImage1);
            byte[] hash2 = shaM.ComputeHash(btImage2);

            for (int i = 0; i < hash1.Length && i < hash2.Length; i++)
                if (hash1[i] != hash2[i])
                    return false;

Die Metadaten haben auch nichts mit dem Bildinhalt zu tun, das ist genau der Grund warum die GetPixel Methode bei frisch geladenen und deserialisierten Bildern Gleichheit zurückgibt, der SHA256 Hash aber ein anderer ist. Du hast recht, die Methode mit dem Bytearrayvergleich ist durchaus performant, allerdings besteht da wie gesagt das Problem dass es zu ner Abweichung von bis zu 5% kommt wenn ich ein frisch geladenes mit einem deserialisierten Bild vergleiche.

 

[Backslash]

Willst du nun wissen ob die Bilder genau gleich sind oder Änhlichkeiten finden?

In ersterem Fall dürfte die schon genannte Methode mit LockBits und dem einfachen durchgehen gut und schnell funktionieren.

Bei mir dauert z.B. das komplette Durchlaufen eines Bildes mit 4752x3168px 80ms.

/edit 02.09.2011: Code war falsch, siehe unten.

 

[NetCrack]

Hey Backslash,
danke für den Hinweis, das funktioniert ganz gut, scheint allerdings nicht Threadsicher zu sein. Es müssen in schneller Abfolge etwa n dutzend kleine Bilder mit mehreren dutzend anderer kleiner Bilder verglichen werden, da kommt er ab nem gewissen Grad durcheinander und rennt in's lock.

 

[kuddlmuddl]

Geht es bei wirklich um 100% identische Bilder? Also wo jedes Bit des Farbwertes für jeden Pixel exakt übereinstimmt?

Ich würde um Geschwindigkeit zu gewinne auf jeden Fall garnicht erst alle Pixel durchlaufen.

Zb könntest du direkt sagen, dass 2 Bilder ungleich sind, wenn sie nicht die gleiche Breite und Höhe haben.
Oder wenn das bei dir immer gegeben ist, könntest du vorerst nur die Bilddiagonale Vergleichen.
Erst wenn die Diaginale von Bild1 mit der von Bild2 übereinstimmt kommt insgesamt Gleichheit in Frage und es werden weitere Pixel angeguckt.

Evtl. ist der Zugriff auf aufeinanderfolgende Pixel schneller als "willkürlicher" Zugriff bei der Diagonalen. Dann kann es sinnvoller sein, die erste Bildzeile / Spalte anzuschauen.
(Wenn du aber immer nen gleichen Bildhintergrund hast, wird diese evtl immer gleich sein. Daher zB die mittlere Zeile statt der ersten wählen fürs erste schnelle vergleichen)

Es gibt auch Bildverarbeitungsbibliotheken, die Daten Spaltenweise und nicht Zeilenweise intern verwalten. Dann wäre ein Zugriff auf aufeinanderfolgende Pixel der selben Spalte evtl schneller. Ka wie das in C# ist.

Sowas bringt viel viel mehr als der Gewinn durch Threads - vor allem weil wahrscheinlich bei größeren Datenmengen nicht die CPU-Leistung die Engstelle ist, sondern SpeicherIO-Geschwindigkeit.

Sonst sag doch bischen was zur Anwendung? Bestimmt lassen sich dann noch andere sinnvolle Tipps / Heuristiken finden

Ähnlich wie bei der obigen Idee könntest du nämlich auch zufällig zB 10% der Pixel auswählen und vergleichen. Und nur wenn die übereinstimmen die nächsten 10%... sofern es echt um Geschwindigkeit geht?
Welche 10% genommen werden (die Zufallszahlen) kann man ja im voraus generieren.

 

[Backslash]

Das Thread-Problem ist ein allgemeines mit GDI+, du müsstest also selbst für Threadsicherheit sorgen.
Würde in diesem Fall aber auch auf Threading verzichten, da wie kuddlmuddl schon sagt der Prozessor die Geschwindigkeit des Vorgangs nicht limitiert.

Je nach Beschaffenheit der Bilder machen natürlich auch die anderen Ansätze Sinn, wenn die Bilder allerdings sowieso klein sind wäre der Gewinn dadurch vermutlich nicht allzu groß.
Was natürlich auf jeden Fall sein muss ist gewisse Dinge wie die Bildgröße vor dem Vergleich zu prüfen, einerseits wegen der Geschwindigkeit und andererseits um Fehler (im Sinne von Ausnahmen) zu vermeiden.

 

[Sardellenpizza]

Bestimmt lassen sich dann noch andere sinnvolle Tipps / Heuristiken finden
Ähnlich wie bei der obigen Idee könntest du nämlich auch zufällig zB 10% der Pixel auswählen und vergleichen. Und nur wenn die übereinstimmen die nächsten 10%... sofern es echt um Geschwindigkeit geht?
Welche 10% genommen werden (die Zufallszahlen) kann man ja im voraus generieren.

Das ist schonmal die richtige Idee.
Google mal nach "compressive sampling"
Das auf die Bilder angewendet sollte schnell gehen und gleichzeitig bist Du mathematisch/statistisch gesehen auf der sicheren Seite.

 

[Zhen]

Hallo Leute,
wollte jetzt nicht extra nen neuen Thread erstellen zu dem Thema, wenns doch eh schon einen gibt. Deswegen grabe ich den hier jetzt mal rauß. ^^

Was für einen Algorithmus würdet ihr den bei nem Remote-Tool ala TeamViewer empfehlen?

Bzw. ich habe bereits einen jedoch finde ich den nicht wirklich effizient genug für sowas. Zudem... bin ich auch kein Mathematiker sondern Azubi für Anwendungsentwicklung daher bräuchte ich in dem Gebiet auch etwas Hilfe um auf die Sprünge zu kommen

naja... also folgendes...

Ich mache einen Screen verschicke diesen und speichere den in einer 2. Variablen (z.B. prevScreen). Nächster Screen da wird geprüft ob es Veränderungen gibt. Das ganze mache ich mit der LockBits Methode und Zeigern.

Hier ein kleiner Beispiel-Code:

for (int y = 0; y < _curScreen.Height; ++y) {
	// For pixels up to the current bound (left to right)
	for (int x = 0; x < left; ++x) {
		// Use pointer arithmetic to index the
		//	next pixel in this row.
		if ((unsafeCur + x)[0] != (unsafePrev + x)[0]) {
			// Found a change.
			if (x < left) {
				left = x;
			}
			if (x > right) {
				right = x;
			}
			if (y < top) {
				top = y;
			}
			if (y > bottom) {
				bottom = y;
			}
		}
	}
	// Move the pointers to the next row.
	unsafeCur += strideNew;
	unsafePrev += stridePrev;
}

Wenn die Variable "left" nicht der Breite des Bildes entspricht, dann das selbe Spiel nochmal, aber von Unten nach Oben diesmal.

Jetzt ist aber das Problem eben das, dass dieser Algorithmus viel zu lange braucht. Außerdem soll ja nichts verschickt werden, wenn es keine Änderung gibt, aber er verschickt trotzdem ein Byte-Array mit der Größe von 700 bis 900 Bytes.


Mit diesem Algorithmus brauche ich 120 bis 700 ms für einen Vergleich. Geht das ganze nicht schneller?

Ergänzung (2. September 2011)

PS: der Code von Backslash funzt bei mir auch irgendwie nicht (habs probeweise mal ausprobiert). Beim Vergleich von den Pointern kommt irgendwann eine Exception "Es wurde versucht im Speicher zu schreiben..."

Ergänzung (2. September 2011)

Ok den Code von Backslash hab ich zum laufen gebracht, aber gibt es eigentlich ne Möglichkeit aus den gesamtpixeln wieder die Koordinaten auszurechnen?