Skip to content

Vergleich der Ähnlichkeit von Bildern mit OpenCV mit Python

Arturo, ein Mitglied dieses Arbeitsteams, hat uns den Gefallen getan, diesen Artikel zu schreiben, da er sich mit diesem Thema bestens auskennt.

Lösung:

Ich schlage vor, dass Sie einen Blick auf die Earth Mover's Distance (EMD) zwischen den Bildern werfen.
Diese Metrik gibt ein Gefühl dafür, wie schwer es ist, ein normalisiertes Graustufenbild in ein anderes umzuwandeln, kann aber auch für Farbbilder verallgemeinert werden. Eine sehr gute Analyse dieser Methode findet sich in der folgenden Arbeit:

robotics.stanford.edu/~rubner/papers/rubnerIjcv00.pdf

Es kann sowohl auf das ganze Bild als auch auf das Histogramm angewendet werden (was wirklich schneller ist als die Methode für das ganze Bild). Ich bin mir nicht sicher, welche Methode einen Vergleich des gesamten Bildes erlaubt, aber für den Vergleich des Histogramms kann man die cv.CalcEMD2 Funktion verwenden.

Das Problem ist nur, dass diese Methode keinen prozentualen Ähnlichkeitsgrad definiert, sondern einen Abstand, nach dem man filtern kann.

Ich weiß, dass dies kein voll funktionsfähiger Algorithmus ist, aber es ist dennoch eine Basis dafür, und ich hoffe, es hilft.

EDIT:

Hier ist ein Spoof, wie die EMD im Prinzip funktioniert. Die Hauptidee ist, zwei normalisierte Matrizen zu haben (zwei Graustufenbilder geteilt durch ihre Summe) und eine Flussmatrix zu definieren, die beschreibt, wie man das Grau von einem Pixel zum anderen des ersten Bildes verschiebt, um das zweite zu erhalten (sie kann auch für nicht normalisierte Bilder definiert werden, ist aber schwieriger).

Mathematisch gesehen ist die Flussmatrix eigentlich ein vierdimensionaler Tensor, der den Fluss vom Punkt (i,j) des alten Bildes zum Punkt (k,l) des neuen Bildes angibt, aber wenn man die Bilder abflacht, kann man sie in eine normale Matrix umwandeln, die nur etwas schwerer zu lesen ist.

Diese Flow-Matrix hat drei Einschränkungen: jeder Term sollte positiv sein, die Summe jeder Zeile sollte den gleichen Wert des Zielpixels ergeben und die Summe jeder Spalte sollte den Wert des Startpixels ergeben.

In diesem Fall muss man die Kosten der Transformation minimieren, die durch die Summe der Produkte der einzelnen Ströme von (i,j) nach (k,l) für die Entfernung zwischen (i,j) und (k,l) gegeben sind.

Das sieht in Worten ein wenig kompliziert aus, deshalb hier der Testcode. Die Logik ist korrekt, ich bin mir nicht sicher, warum sich der Scipy-Solver darüber beschwert (man sollte vielleicht nach openOpt oder etwas ähnlichem schauen):

#original data, two 2x2 images, normalized
x = rand(2,2)
x/=sum(x)
y = rand(2,2)
y/=sum(y)

#initial guess of the flux matrix
# just the product of the image x as row for the image y as column
#This is a working flux, but is not an optimal one
F = (y.flatten()*x.flatten().reshape((y.size,-1))).flatten()

#distance matrix, based on euclidean distance
row_x,col_x = meshgrid(range(x.shape[0]),range(x.shape[1]))
row_y,col_y = meshgrid(range(y.shape[0]),range(y.shape[1]))
rows = ((row_x.flatten().reshape((row_x.size,-1)) - row_y.flatten().reshape((-1,row_x.size)))**2)
cols = ((col_x.flatten().reshape((row_x.size,-1)) - col_y.flatten().reshape((-1,row_x.size)))**2)
D = np.sqrt(rows+cols)

D = D.flatten()
x = x.flatten()
y = y.flatten()
#COST=sum(F*D)

#cost function
fun = lambda F: sum(F*D)
jac = lambda F: D
#array of constraint
#the constraint of sum one is implicit given the later constraints
cons  = []
#each row and columns should sum to the value of the start and destination array
cons += [ {'type': 'eq', 'fun': lambda F:  sum(F.reshape((x.size,y.size))[i,:])-x[i]}     for i in range(x.size) ]
cons += [ {'type': 'eq', 'fun': lambda F:  sum(F.reshape((x.size,y.size))[:,i])-y[i]} for i in range(y.size) ]
#the values of F should be positive
bnds = (0, None)*F.size

from scipy.optimize import minimize
res = minimize(fun=fun, x0=F, method='SLSQP', jac=jac, bounds=bnds, constraints=cons)

die Variable res enthält das Ergebnis der Minimierung...aber wie gesagt, ich bin mir nicht sicher, warum er sich über eine singuläre Matrix beschwert.

Das einzige Problem bei diesem Algorithmus ist, dass er nicht sehr schnell ist, so dass es nicht möglich ist, ihn bei Bedarf auszuführen, sondern man muss ihn mit Geduld bei der Erstellung des Datensatzes durchführen und die Ergebnisse irgendwo speichern

Sie haben sich auf ein gewaltiges Problem eingelassen, das als "Content Based Image Retrieval" oder CBIR bezeichnet wird. Es ist ein umfangreiches und aktives Gebiet. Es gibt noch keine fertigen Algorithmen oder Standardansätze, obwohl es eine Menge Techniken gibt, die alle unterschiedlich erfolgreich sind.

Selbst die Google-Bildersuche macht das (noch) nicht - sie macht eine textbasierte Bildersuche - z.B. die Suche nach Text auf einer Seite, die dem gesuchten Text ähnelt. (Und ich bin sicher, dass sie daran arbeiten, CBIR zu verwenden; das ist der heilige Gral für viele Bildverarbeitungsforscher)

Wenn Sie eine knappe Deadline haben oder das schnell erledigen müssen... huch.

Hier gibt es eine ganze Reihe von Arbeiten zu diesem Thema:

http://scholar.google.com/scholar?q=content+basiert+Bild+Wiederherstellung

Im Allgemeinen müssen Sie ein paar Dinge tun:

  1. Extrahieren von Merkmalen (entweder an lokalen Interessenpunkten, oder global, oder irgendwie, SIFT, SURF, Histogramme, usw.)
  2. Clustern / ein Modell der Bildverteilungen erstellen

Dies kann Merkmalsdeskriptoren, Bildlisten, Lernen mit mehreren Instanzen usw. umfassen.

Ich habe vor etwa 2 Jahren ein Programm geschrieben, das etwas sehr Ähnliches mit Python/Cython macht. Später habe ich es in Go umgeschrieben, um eine bessere Leistung zu erzielen. Die Grundidee stammt von findimagedupes IIRC.

Es berechnet im Grunde einen "Fingerabdruck" für jedes Bild und vergleicht dann diese Fingerabdrücke, um ähnliche Bilder zu finden.

Der Fingerabdruck wird erzeugt, indem man das Bild auf 160x160 verkleinert, in Graustufen umwandelt, etwas Unschärfe hinzufügt, es normalisiert und dann auf 16x16 monochrom verkleinert. Am Ende haben Sie eine Ausgabe von 256 Bit: das ist Ihr Fingerabdruck. Dies ist sehr einfach zu bewerkstelligen mit convert:

convert path[0] -sample 160x160! -modulate 100,0 -blur 3x99 
    -normalize -equalize -sample 16x16 -threshold 50% -monochrome mono:-

(Die [0] in path[0] wird verwendet, um nur das erste Bild von animierten GIFs zu extrahieren; wenn Sie nicht an solchen Bildern interessiert sind, können Sie es einfach entfernen).

Nachdem Sie dies auf 2 Bilder angewendet haben, erhalten Sie 2 (256-Bit) Fingerabdrücke, fp1 und fp2.

Der Ähnlichkeitswert dieser beiden Bilder wird dann durch XOR-Verknüpfung dieser beiden Werte und Zählung der auf 1 gesetzten Bits berechnet. Um diese Bit-Zählung durchzuführen, können Sie die bitsoncount() Funktion aus dieser Antwort verwenden:

# fp1 and fp2 are stored as lists of 8 (32-bit) integers
score = 0
for n in range(8):
    score += bitsoncount(fp1[n] ^ fp2[n])

score ist eine Zahl zwischen 0 und 256, die angibt, wie ähnlich Ihre Bilder sind. In meiner Anwendung teile ich den Wert durch 2,56 (Normalisierung auf 0-100) und habe festgestellt, dass Bilder mit einem normalisierten Wert von 20 oder weniger oft identisch sind.

Wenn Sie diese Methode implementieren und für den Vergleich vieler Bilder verwenden möchten, empfehle ich dringend empfehlen, Cython (oder einfach nur C) so oft wie möglich zu verwenden: XORing und Bit-Zählen ist mit reinen Python-Ganzzahlen sehr langsam.

Es tut mir wirklich leid, aber ich kann meinen Python-Code nicht mehr finden. Im Moment habe ich nur eine Go-Version, aber ich fürchte, ich kann sie hier nicht posten (eng in anderen Code integriert und wahrscheinlich ein wenig hässlich, da es mein erstes ernsthaftes Programm in Go war...).

Es gibt auch eine sehr gute "Find by similarity"-Funktion in GQView/Geeqie; Der Quelltext ist hier.

Sie können unsere Arbeit sponsern, indem Sie einen Kommentar zeigen und ihn bewerten, wir danken Ihnen.



Nutzen Sie unsere Suchmaschine

Suche
Generic filters

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.