Bag of Feature: Wie erstellt man das Abfrage-Histogramm?

Question

Ich versuche, das Bag of Features-Modell zu implementieren.

Gegeben ein Deskriptor-Matrixobjekt (das ein Bild darstellt), das zu dem ursprünglichen Datensatz gehört, berechnen Sie sein Histogramm einfach, da wir bereits wissen, zu welchem ​​Cluster jeder Deskriptorvektor von k-means gehört.

Aber was ist, wenn wir das Histogramm einer Abfrage-Matrix berechnen wollen? Die einzige Lösung, die mir in den Sinn kommt, ist die Berechnung der Entfernung zwischen jedem Vektordeskriptor zu jedem der k Clusterschwerpunkte.

Dies kann ineffizient sein: unter der Annahme, k=100 (also 100 Zentroide), dann haben wir ein Anfrage Bild durch 1000 SIFT-Deskriptoren, so eine Matrix 1000x100 dargestellt.

Was wir jetzt tun müssen, ist 1000 * 100 eucledian Entfernungen in 128 Dimensionen zu berechnen. Das scheint wirklich ineffizient zu sein.

Wie löst man dieses Problem?

HINWEIS: können Sie mir einige Implementierungen vorschlagen, in denen dieser Punkt erklärt wird?

HINWEIS: Ich weiß, LSH ist eine Lösung (da wir High-Dim-Vektoren verwenden), aber ich glaube nicht, dass die tatsächlichen Implementierungen es verwenden.

UPDATE:

Ich war mit einem Kollegen von mir sprechen: einen hierarchischen Cluster-Ansatz anstelle von klassischen k-Mitteln sollten so viel den Prozess beschleunigen! Ist es richtig zu sagen, dass, wenn wir k Zentroide haben, mit einem hierarchischen Cluster müssen wir nur log(k) Vergleiche zu tun, um den nächsten Schwerpunkt statt k Vergleiche zu finden?

Answer 1

Für eine Tasche von Features Ansatz müssen Sie tatsächlich die Deskriptoren quantisieren. Ja, wenn Sie 10000 Features und 100 Features 10000 * 100 Distanzen haben (es sei denn, Sie verwenden hier einen Index). Vergleichen Sie dies, um jedes der 10000 Features mit jedem der 10000 Features jedes Bildes in Ihrer Datenbank zu vergleichen. Klingt es immer noch so schlecht?