Bildunterschiede feststellen

MaxMustermann

Momentan habe ich ein hbitmap ...komprimiere es in PNG und vergleiche zuerst mit der Größe des Vorgängers. Sofern diese gleich ist, zusätzlich noch ein paar zufällige Bits im Bytestrom um einigermaßen sicher zu sein. Da alles sehr zeitintensiv ist, wäre es natürlich wirklich gut, wenn ich schon das hbitmap effektiv zum Vorgänger prüfen könnte. Hatte es mal mit ner crc32 Routine probiert aber das ging zeitlich in den Keller, da ich dies schon jede Menge Zeit verbraten hat und ich bei einem Unterschied noch komprimieren muss.
Kennt jemand einen effektiven Weg? Vielleicht auch ne tolle und sehr schnelle Hashroutine.

Gruß

Max

rapso

deine beschreibung, besonders mit crc32 und keller sind irgendwie ein wenig undurchschauber, kannst du das genauer ausfuehren bitte?
ich haette es naemlich genau so gemacht.

MaxMustermann

um es mal etwas anders darzustellen:

jetzt:
hbitmap -> PNG -> Überprüfung der Größe (->) Überprüfung verschiedener Bits -->> Unterschied festgestellt
Nachteil: Ich komprimiere immer

schon probiert:
hbitmap -> CRC32 Hash erstellen -->> Unterschied festgestellt
Nachteil: Bei Unterschied habe ich schon zuviel Zeit für den Hash verbraucht. Generierung des Hash's + Komprimieren in PNG sprengt meinen Zeitrahmen.

Gesucht:
Etwas anderes als CRC32 Hash. Vielleicht irgendwelche eindeutigen Bildinformationen. Oder ein wesentlich schnellerer Algo der einigermaßen zuverlässig ist.

rapso

wie gross ist das ration von veraenderten zu unveraenderten bildern.

und wie lange brauchst du fuer dein crc32 und wie lange fuers png packen.

hustbaer

PNG packen ist so langsam dass es IMO keine Rolle spielen kann ob man vorher noch ne CRC32 rechnet oder nicht.

Und: wie hast du das "andere" Bild denn vorliegen? Nur komprimiert, oder auch als Rohdaten, oder garnicht oder ... blubb?

ip

Folgender Gedanke:

PNG und Bitmaps binär byteweise zu vergleichen funktioniert natürlich nicht, da PNG Farbpaletten benutzt und 24-Bit Bitmaps eben Farbwerte für jeden Pixel einzeln speichern.
Trotzdem solltest du, je nachdem welche Library du verwendest, auf eine geladene PNG ähnlich wie auf eine Bitmap zugreifen können. Also zB PNGImage.getPixel(x,y): RGBA;
Du solltest also auf dieser Basis die Farbwerte eines jeden Pixels vergleichen können um 100% sicher zu sein, dass die beiden Bilder gleich sind. Sollte dir jeder Pixel zu lange dauern sollte auch jeder 2te genügen um ein recht hohe Sicherheit zu erhalten.

Du solltest allerdings wissen, dass, und ich gehe eigentlich davon aus, dass du das weißt, eine Konvertierung von einem zu einem anderen Format zu Informationsverlust führen kann - vor allem wenn es um Komprimierte Dateiformate geht. Dh wenn du eine Bitmap hast und diese in ein PNG umwandelst ist die Wahrscheinlichkeit gegeben, je nach (Farb-) Komplexität der Bitmap, dass es zu Informations- bzw Farbverlusten kommt und deine neue PNG bei einem Pixel-für-Pixel vergleich als unterschiedlich eingestuft wird - auch wenn dies vielleicht garnicht optisch zu erkennen ist.

PS: Ansonsten gibt es auch noch die Möglichkeit die Vergleichs PNG zu einer Bitmap umzuwandeln und dann einen CRC32 Vergleich zu machen. Das sollte deutlich schneller gehen als die Bitmap in eine PNG umzuwandeln (im Endeffekt sollte es nur eine Füllung der Pixel mit den Werten aus der Palette sein).

mad_martin

ip schrieb:

FDu solltest allerdings wissen, dass, und ich gehe eigentlich davon aus, dass du das weißt, eine Konvertierung von einem zu einem anderen Format zu Informationsverlust führen kann - vor allem wenn es um Komprimierte Dateiformate geht. Dh wenn du eine Bitmap hast und diese in ein PNG umwandelst ist die Wahrscheinlichkeit gegeben, je nach (Farb-) Komplexität der Bitmap, dass es zu Informations- bzw Farbverlusten kommt und deine neue PNG bei einem Pixel-für-Pixel vergleich als unterschiedlich eingestuft wird - auch wenn dies vielleicht garnicht optisch zu erkennen ist.

Bei einem verlustfreien Format? Ganz sicher?

MaxMustermann

Was die Gewschwindikeit betrifft, brauche ich auf der Testmaschine für ein 1680x1050px großes Bild:

HBITMAP->PNG: 96-99ms / ca.150kb
HBITMAP->JPEG(100%): 105ms / ca.205kb

Soviel zum Thema ....PNG ist lahm

Was den Vergleich betrifft (wieder 1680x1050px Bitmap ...ca.6,9MB ):
crc32: 31-33ms
adler32: 22ms
memcmp: 7-8ms (hätte aber gern eine checksumme)

Bin auf Adler32 aufmerksam geworden und dieser macht mich schon fast glücklich.
Problem hierbei ist, dass ich aus irgendwelchen Gründen nicht direkt auf das hbitmap zugreifen kann, sondern es vorher mit GetBitmapBits() als richtiges Bitmap mir holen muss. Diese Umwandlung kostet mich wiederum 16ms. Wenn ich das hbitmap durch den crc-check jagen möchte, bekomme ich ein Speicherfehler. Kann es daran liegen, dass ich die Größe des Hbitmaps falsch ermittle?! Für ein normales Bitmap scheint das unten aufgeführte jedenfalls die richtige Größe zu ermitteln.

BITMAP bm;
	GetObject(hbitmap, sizeof(bm), &bm); 
	long size = bm.bmHeight*bm.bmWidth*bm.bmBitsPixel/8;

@IP ich versuche nicht den Unterschied zwischen einem hbitmap und einem PNG zu ermitteln sondern lediglich zum jeweiligen Vorgänger. (z.B.:PNG vor 5 Sek. vs. PNG jetzt oder natürlich hbitmap vor 5 Sek. vs. hbitmap jetzt)

hustbaer

Naja, kommt drauf an wie du die Bitmap angelegt hast:

MSDN schrieb:

If hgdiobj identifies a bitmap created by calling CreateDIBSection, and the specified buffer is large enough, the GetObject function returns a DIBSECTION structure. In addition, the bmBits member of the BITMAP structure contained within the DIBSECTION structure will contain a pointer to the bitmap's bit values.

If hgdiobj identifies a bitmap created by any other means, GetObject returns only the width, height, and color format information of the bitmap and the pointer to the bitmap's bit values will be NULL. You can only access the bitmap's bits if they are in a device-independent bitmap.

(Und selbst wenn es eine DIB ist liest sich das für mich so dass du nen Zeiger auf ein DIBSECTION Objekt übergeben musst damit GetObject den bmBits Zeiger richtig setzt. Kann aber auch nur verwirrend geschrieben sein.)

----

Die Zeiten die du da rausbekommst wundern mich allerdins etwas. Bei mir braucht memcmp ~4ms und alder32 nur etwa 6.5ms, also nichtmal das doppelte (bei 7MB daten auf einem core2 mit 4MB cache) -- wobei es bei dir ja eher Faktor 3 ist.

Versuch mal die Adler32-Implementierung auf Wikipedia: http://en.wikipedia.org/wiki/Adler-32 (mit hab ich's versucht).

Ansonsten... wenn die Bitmap keine DIB ist, dann müssen die Daten sowieso irgendwann mit GetBitmapBits geholt werden (zumindest kenne ich keinen schnelleren Weg). Wenn das der Fall ist könntest du die Daten ja gleich so an die PNG-Library weiterreichen dass diese sich die nicht nochmals mit GetBitmapBits holen muss - dann hättest du zumindest keinen Nachteil durch das GetBitmapBits mehr.

EDIT: Nochwas: was stört dich eigentlich an memcmp?

rapso

ich finde die timmings auch recht langsam, irgendwie.

aber naja, ich wuerde denken, dass die checksum nicht so dramatisch wichtig ist und lediglich zum vergleich dient und bei nem fehler kein weltuntergang waere, oder?

von daher wuerde ich was ziemlich simples nutzen. in etwa

uint32_t CheckSum(const uint32_t* pData,const size_t PixelCount)
{
  uint32_t CheckSum=*pData;
  for(size_t a=0;a<PixelCount;a++)
  {
    const size_t Rot=a&31;
    const uint32_t V=pData[a];
    CheckSum^=(V<<Rot)|(V>>Rot);
  }
  return CheckSum;
}

weil das kein modulo usw. hat, ist es vermutlich recht fix.

MaxMustermann

Das Posting der Timings soll kein Anreiz darstellen, diesen zu übertreffen, sondern lediglich den Faktor gegenüberstellen.

Was memcmp betrifft, so gibt es mir nicht sonderlich viel zurück. Eine Checksumme wäre schon recht nett, möchte mir eventuell die Option offen halten, schnell mal die letzten x Bilder durchzukämmen, ob hier womöglich ein Treffer ist.

Ich habe übrigens die Adler32 Implementierung aus zlib genommen.

@rapso
Du liegst richtig mit der Annahme, dass ich die Genauigkeit hintenanstelle. Ich schau mal ob die Genauigkeit für meine Belange ausreicht.

Irgendwie krieg ich es nicht gebacken die richtige Größe des hbitmaps oder des memory-dc's zu ermitteln. Habe das Gefühl ich stelle mich irgendwie bekloppt an