Maß für Bildähnlichkeit gesucht

[Medium]

Moinmoin!

Wie der Titel schon so promisk offen legt, bin ich im Moment dabei ein geeignetes Maß für die Ähnlichkeit von Bildern zu finden. Jetzt mag der eine oder andere gleich denken: "Jau! Farbdifferenzquadratsummen!", aber da war ich schon .
Das Ding ist, dass ich zwei Kompressionsmethoden bezüglich ihres Verhältnisses von Qualität zu Kompressionsrate vergleichen muss, wobei die beiden Verfahren gänzlich unterschiedlich arbeiten: Das eine ist JPEG, welches im Wesentlichen geometrietreu ist, und seine Kompression aus Toleranz zu Farbungenauigkeiten zieht (im Wesentlichen halt). Das andere ist eines, dass zwar auch Farbungenau ist, jedoch maßgeblich durch Zulassen geometrischer Ungenauigkeiten komprimiert.

Der Effekt der dabei stört: Kanten sind beim 2. Verfahren potentiell um so grob 1-3 Pixel ungenau, und gerade leicht verschobene Kanten führen zu extrem hohen Farbdifferenzquadraten - jedoch ist der subjektive Bildeindruck davon kaum beeinträchtigt!
Und das ist der Knackpunkt: Ich brauche ein Verfahren, dass "Bildeindruck" modelliert. Mit dem an und für sich statistisch korrekten Mittel der Differenzenquadrate komme ich da leider nicht wirklich bei. Das ganze darf auch gerne rechenaufwendig sein, sprich ein paar Sekunden/Minuten pro Bild dauern. Ich hatte schon an das nächst offensichtlichere gedacht: FFT Analyse. Allerdings treten auch hier teilweise extreme Unterschiede im Frequenz- und vor allem Phasenraum auf, wo die Bilder an sich subjektiv fast identisch sind.

Um mal so ein Vergleich zu haben: Man nehme sich einfach mal 2 aufeinanderfolgende Bilder eines Videos, wo gerade eher langsame Action passiert. In etwa solche Differenzen muss ich als "praktisch identisch" erkennen können, auch wenn sich die Objekte innerhalb des Bildes beliebig zueinander verschieben können - aber eben nicht sehr weit.

Mag mir wer helfen diesen Hirnknoten zu lockern?


Verregnete Grüße,
Medium

Edit: Crosspost auf GameDev.net

[Phoenix]

Boah.. ich hatte das im Studium. Blöderweise weiss ich nicht mehr genau, wo ich die ganzen Algorithmen aus meinem C-Test/Beispiel/Übungs/Probierprogramm habe. Ich befürchte aber, das wird ne Weile dauern bis ich die wieder gefunden habe. Zumal die ganzen Unterlagen gerade nicht vor Ort sind.

Im Prinzip gibt es aber Algorithmen die z.B. Kanten erkennen können. Auch Flächen kann man relativ einfach ermitteln.

Du kannst nun Flächen und Kanten für beide Bilder berechnen und mit einem Toleranzwert belegen (z.B. bei einer Kante Start und Endkoordinate plus/minus N Pixel). Innerhalb dieser Toleranzbereiche werden dann im anderen Bild entsprechende Kanten bzw. Flächen gesucht. Für Abweichungen bei Kanten werden dann Punkte vergeben (geringe Abweichung z.B. 1 Punkt, große Abweichung z.B. 5 Punkte). Das gleiche machst Du bei Farbflächen, wobei hier neben der Position und Form (also grob Koordinaten) der Farbwert auch noch mit einfliesst.

Die Bilder sind ähnlicher, je geringer die Punktzahl ist. Dann müsstest Du nur noch mit genügend Testbildern einen Grenzwert ermitteln, über dem die Bilder als nicht mehr ähnlich gelten.

[helgew]

also mir fällt dazu vollgendes ein (spannendes Thema übrigens, das du da eröffnet hast):

- wende einen Kantenoperator auf beide Bilder an (difference of gaussians)
- unterteile das Bild in Blöcke, 16x16 Pixel dürften ein Anfang sein
- verwerfe Blöcke ohne Kantenanteil
- suche die korrespondierenden Koordinaten durch Kreuzkorrelation
- bilde die Varianzen der einzelnen Farbkanäle

hm... naja, so in etwa könnte es u.U. schonmal Ergebnisse liefern, hoffe ich

[Medium]

Hmmtjahmmm! An und für sich keine schlechte Idee. Ich hätte aber vermutlich erwähnen sollen, dass das 2. Verfahren eben genau auf Kantenerkennung basiert, und eine Rekonstruktion aus einem Kantenbild ist . Wenn ich nun mit dem selben Mittel da dran gehe um die Qualität zu messen, würde Verfahren 2 vermutlich immer nahe 100% haben

Worüber ich noch nachdenken könnte, wäre quasi eine Blob-Detection mittels Waterfilling-Algo, da müsste mir nur etwas einfallen das ganze etwas stabiler zu bekommen. (Ich hatte Waterfilling mal als Kantendetektor implementiert, Canny hat jedoch erheblich passendere Ergebnisse geliefert. Dabei fiel mir auf, dass selbst kleinste Änderungen in regional völlig anderer Fragmentierung resultieren können - das wäre ja fatal hierbei.)

Kreuzkorrelation scheint mir aber in völlig anderer Hinsicht noch nutzen zu können - aber ganz andere Baustelle. Danke

In meinem Thread bei GameDev kam auch noch eine sehr interessante Idee. Eventuell lohnt es sich eher in diese Richtung zu denken, da eben wie gesagt Kantenerkennung bereits Kern der Kompression Nr.2 ist - noch Mal sorry dass ich das so nicht direkt erwähnt hatte.

[alzaimar]

Das Siox-Verfahren zur Imagesegmentierung (Herausrechnen eines Hintergrundes) arbeitet mit Entropieübergängen und Energiedichtefunktionen, die nach meinem Verständnis verwendet werden könnten, um zwei Bilder miteinander zu vergleichen. Man dürfte fast identische Funktionsverläufe in fast identischen Bildern erwarten. Die Funktionen wären jedoch viel leichter zu handhaben.

Fragt sich nur, ob das nicht ein wenig zu grob ist.

[Medium]

Nicht, dass das höchst spannend ausschaut, aber uff! Da wäre der Implementierungsaufwand für den Vergleich fast schon größer als der für das Kompressionsverfahren . Die Ergebnisse davon schauen aber dermaßen überzeugend aus, dass ich fast schon geneigt bin das auch unabhängig von dem Thema hier mal zu basteln =)

Was den Vergleich angeht, so habe ich mal den Tipp auf GameDev aufgegriffen und gedanklich verfeinert. Dort (Link im ersten Beitrag) hab ich mal den Code (C#) dazu geposted, und es scheint zumindest nicht völlig abwegig zu sein. Um das Bewertungsverfahren aber richtig bewerten zu können, muss ich wohl noch ein paar mehr Testreihen anwerfen