Algorithmus für die visuelle Ähnlichkeitssuche

Question

Ich versuche, ein Dienstprogramm wie dieses zu erstellen http://labs.ideeinc.com/multicolr , aber ich weiß nicht, welchen Algorithmus sie verwenden. Weiß das jemand?

Answer 1

Sie gleichen lediglich Histogramme ab.

Erstellen Sie also ein Histogramm für Ihre Bilder. Normalisieren Sie die Histogramme nach der Größe des Bildes. A Histogramm ist ein Vektor mit so vielen Elementen wie Farben. Sie brauchen keine 32, 24 und vielleicht nicht einmal 16 Bits Genauigkeit und das wird Sie nur verlangsamen. Aus Leistungsgründen würde ich die Histogramme auf 4, 8 und 10-12 Bits herunterrechnen.

• Unscharf machen least distance compare zwischen allen 4-Bit-Histogrammen und Ihren Beispielfarben.
• Dann nehmen Sie diesen Satz und führen den 8-Bit-Histogrammvergleich durch.
• Gehen Sie dann vielleicht zu einem 10- oder 12-Bit-Histogramm über und vergleichen Sie es mit dem verbleibenden Satz. Dies ist die leistungsfähigste Suche, da Sie die gesamte Menge mit einer sehr kleinen Anzahl von Berechnungen vergleichen, um eine kleine Teilmenge zu finden.
• Dann bearbeiten Sie die kleine Teilmenge mit einer höheren Anzahl von Berechnungen usw.

Der eigentliche Trick besteht darin, den besten Algorithmus für den Abgleich ähnlicher Histogramme zu finden.

• Beginnen Sie mit der Entfernungsberechnung. In 3 Dimensionen, glaube ich, war es:

  SQRT((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2)

Ich tue dies aus dem Gedächtnis, also schlagen Sie es nach, um sicherzugehen.

• Für Ihre Zwecke werden Sie mehr als 3 Dimensionen haben, also werden Sie mehr Begriffe haben. Ein 4-Bit-Histogramm hätte 16 Terme, ein 8-Bit-Histogramm hätte 256 Terme usw. Denken Sie daran, dass diese Art von Mathematik langsam ist, führen Sie also nicht die SQRT Teil. Wenn Sie die Größe Ihrer Bilder klein genug machen, z. B. auf 10.000 Pixel, dann wissen Sie, dass Sie nur noch die folgenden Schritte durchführen müssen x^2 für die Werte 0..10,0000. Vorberechnung einer Nachschlagetabelle von x^2 wobei x von 0 10.000 geht. Dann werden Ihre Berechnungen schnell gehen.

• Wenn Sie eine Farbe aus der Palette auswählen, erstellen Sie einfach ein Histogramm mit dieser Farbe = 10.0000. Wenn Sie 2 auswählen, erstellen Sie ein Histogramm mit Farbe1=5000, Farbe2=5000 usw.

• Letztendlich müssen Sie noch weitere Faktoren hinzufügen, um die Anwendung an die reale Welt anzupassen, aber diese werden Sie durch Tests herausfinden.

Answer 2

Ich würde vorschlagen, dass Sie eine Art Clustering der Farben in den Bildern in Ihrer Datenbank durchführen. Ich meine, für jedes Bild in Ihrer Datenbank:

• die Farben jedes Pixels im Bild sammeln
• Clustering (z. B. k-mean Clustering mit 5 Clustern) auf den gesammelten Farben durchführen
• Speichern der geclusterten Farben als repräsentativen Deskriptor des Bildes

Wenn der Benutzer einen Satz von einer oder mehreren Abfragefarben angibt, führen Sie eine Art "Greedy Matching" durch, bei dem Sie die beste Übereinstimmung zwischen den angegebenen Farben und dem Farbdeskriptor (die 5 repräsentativen Farben) jedes Bildes in Ihrer Datenbank auswählen.

Wie groß ist Ihre Bildersammlung, denn je nach Größe kann die Indexierung der Suche ein größeres Problem darstellen als der Algorithmus selbst?

Answer 3

Wahrscheinlich wird einfach ein Histogramm der in den Bildern verwendeten Farben erstellt und dann eine optimale Anpassung an die vom Benutzer ausgewählten Farben vorgenommen.