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).

Tipp 2096: Prüfen, ob zwei Bilder identisch sind	4.251	Master of VDL	06.11.09 10:18
Re: Prüfen, ob zwei Bilder identisch sind	1.628	Snof	06.11.09 18:01
Re: Prüfen, ob zwei Bilder identisch sind	1.559	Master of VDL	06.11.09 18:21

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