In diesem Forum haben Sie die Möglichkeit Kommentare, Fragen und Verbesserungsvorschläge zu den im vb@rchiv gelisteten Tipps und Workshops zu posten. Hinweis: Ein neues Thema kann immer nur über die jeweilige Tipps & Tricks bzw. Workshop Seite eröffnet werden!

Sie sind aktuell nicht angemeldet.

Funktionen: Einloggen  |  Neu registrieren  |  Suchen

Tipp 2096: Prüfen, ob zwei Bilder identisch sind
Autor: Master of VDL
Tipp anzeigenDatum: 06.11.09 10:18
Pixelvergleich ist die einzige sichere Methode, um den Inhalt zweier Bilder (oder alternativ Byte-Vergleich bei Dateien) zu vergleichen. Ein Hashen ist auf jeden Fall performanter, wenn ein Bild/eine Datei mit mehreren anderen verglichen werden soll. Das direkte vergleichen der beiden Byte-Arrays, die man aus den Bildern gezogen hat ist aber nicht performanter als das vergleichen per Hash, denn das Hashen muss auch einmal über alle Bytes wandern - hat also auch eine asymptotische Laufzeit von O(Anzahl Bytes) - genau wie das direkte Vergleichen der Bytes. Sobald man aber aus mehreren Bildern (oder auch Dateien) Doppelte herausfinden will, muss man jede bisher geprüfte Datei mit der neuen vergleichen. Hier bieten sich sofort Hashes an, da man dadurch jedes Bild nur einmal Hashen muss, das Einlesen der Bilder ist also O(Anzahl Bytes pro Bild * Anzahl Bilder) oder O(Anzahl Gesamtbytes) während es O(Anzahl Gesamtbytes!) wäre, wenn man jedes mal neu alle Bilder einliest. Beim Hashen muss man aber immer beachten, dass es Hash collissions gibt. Das bedeutet, dass zwei Quelldaten (hier Bilder) den gleichen Hash haben können. Bei SHA1 ist die Warscheinlichkeit dafür sehr gering, aber bei ausreichend großer Anzahl der zu hashenden Bilder wird es immer Warscheinlicher. Mir selbst ist es beim suchen von doppelten Dateien passiert, als ich ein Bildarchiv von mehreren tausend Dateien auf Doppelte untersucht hatte. Also bei solchen Anwendungen bietet sich an, mehrere Hashes gleichzeitig zu nutzen (die Laufzeit des Hashens multipliziert sich hier zwar mit der Anzahl der Hashes, da die aber von euch Konstant in den Code eingebaut ist, bleibt die asymptotische gleich bei O(Anzahl Gesamtbytes).

Re: Prüfen, ob zwei Bilder identisch sind
Autor: Snof
Datum: 06.11.09 18:01
Hallo Zitat: Sobald man aber aus mehreren Bildern (oder auch Dateien) Doppelte herausfinden will, muss man jede bisher geprüfte Datei mit der neuen vergleichen. Hier bieten sich sofort Hashes an, da man dadurch jedes Bild nur einmal Hashen muss, das Einlesen der Bilder ist also O(Anzahl Bytes pro Bild * Anzahl Bilder) oder O(Anzahl Gesamtbytes) während es O(Anzahl Gesamtbytes!) wäre, wenn man jedes mal neu alle Bilder einliest. Ich seh das etwas anders. Ob das Hashen etwas bringt hängt davon ab, wie aufwendig das Vergleichen der Hashwerte ist. Szenario 1: Es sind bereits m Bilder der Länge n bekannt (inklusive der Hashwert). Es soll überprüft werden, ob ein gegebenes Bild bereits bekannt ist. Die Zeit für das Vergleichen der Hashwerte ist h(n). Das Überprüfen hat ohne Hashen einen Aufwand von O(n * log m). Mit Hashen dauert es O(n + h * log m). Szenario 2: Es sind m Bilder der Länge n (ohne Hashwert) gegeben und es sollen Doppelte gefunden werden. Der Aufwand ohne Hashen: O(n * m * log m) Mit Hashen: O(n * m + h * m * log m) Sollte nun h(n) in O(n) liegen, bringt das Hashen in Bezug auf die Komplexität nichts. Im Idealfall ist h(n) natürlich in O(1). Die ganze Überlegung setzt vorraus, dass das Hashen in O(n) geschiet und Kollisionen nicht von Relevanz sind. Im Endeffekt ist die ganze Sache mit dem Hashen reiner Pragmatismus. Das Vergleichen geht halt schneller, auch wenn es nur ein konstanter Faktor ist. Die Einspaarung dadurch ist größer als der Mehraufwand bei Kollision, die diese nur sehr selten auftritt. Für die Komplexität spielt es ganz streng genommen keine Rolle, denn im schlimmsten Fall haben alle Bilder den selben Hashwert. PS: Also die naive Implementierung zum suchen von Doppelten geht in O(n * m^2). Wie bist du auf O((n * m)!) gekommen?

Re: Prüfen, ob zwei Bilder identisch sind
Autor: Master of VDL
Datum: 06.11.09 18:21
Argh - du hast recht mit O(n*m^2) - ich weiß auch nicht genau, wie ich auf O((n*m)!) gekommen bin. Ich habe hier darstellen wollen, dass das Hashen für diese Anwendung keinen Sinn macht, da man in beiden Fällen jedes Byte der beiden Bilder (m ist konstant bei 2) einmal einliest - nämlich entweder direkt beim Vergleich der Byte-Daten der Bilder oder beim erzeugen der Hashes der beiden Bilder. Im letzeren Fall packe ich ja noch (ein paar wenige) mehr Bytes an als im ersten - nämlich die (paar) Bytes der Hashes, die ich dann vergleiche. Diese Bytes kosten mich aber im Endeffekt extra Zeit. Sinnvoll ist das Hashen erst, wenn das erzeugen eines Hashes kürzer als O(n) ist - das würde aber theoretisch bedeuten, dass der Hash nicht alle Bytes der Daten einliest und verarbeitet, was seine Unsicherheit wieder erhöht... Das Suchen von Doppelten sollte ein Beispiel für einen Fall sein, in dem das Hashen sinnvoller ist als in dem Tipp, aber auch zeigen, dass Collissions schnell vorkommen können. Daher habe ich scheinbar bei der Angabe der Laufzeit für die naive Implementierung zur Suche von Doppelten etwas verwirrtes hingeschrieben: Ich habe nicht an die Summe 1+2+3+4+... gedacht (vergleiche bild 2 mit bild 1, bild 3 mit bildern 1 und 2, ...) sondern irgendwie an eine Multiplikation 1*2*3*4*... - weiß auch nicht warum... Danke, dass du es bemerkt und angemerkt hast.

Sie sind nicht angemeldet! Um einen neuen Beitrag schreiben zu können, müssen Sie sich zunächst anmelden. Einloggen  |  Neu registrieren

Funktionen:  Zum Thema  |  Gesamtübersicht

Suchen