Feature Vector Partioning

Question

我在閱讀關於圖像搜索的內容，並且我已經到了對特徵向量有基本理解的地方，並且對旋轉不變和尺度不變特徵有一個非常基本的（完全不完整的）理解。如何查看多采樣圖像的尺度不變性以及旋轉不變性的角點。

要搜索十億張圖像，儘管您無法進行線性搜索。我讀的大部分內容似乎都意味着K-d樹被用作分區數據結構來改善查找時間。

K-d樹分裂的是什麼度量？如果使用SIFT，SURF或ORB等描述符，則不能保證類似的關鍵點在特徵向量中排列，所以我很困惑如何確定'左'或'右'，因爲使用這樣的功能時，需要分割基於相似性。我的猜測是距離'標準'的歐式距離，然後你做一個可靠的最近鄰居搜索，但是想知道如何在最近鄰居搜索之前處理KD樹中的初始查詢。我認爲KD樹需要在每個維度上比較相似的特徵，但我不知道在許多關鍵點上會發生什麼。

我可以找到很多有關最近鄰居搜索的論文，但大多數人似乎都假設你知道這是如何處理的，所以我在這裏錯過了一些東西。

Answer 1

這很簡單。所有那些特徵描述符都將圖像作爲多維空間中的一個點。只是爲了簡單起見，我們假設您的描述符維度爲2.比您所有的圖像將被映射到兩個維度平面上。然後，kd-tree將這個平面分割成矩形區域。任何屬於同一區域的圖像都將被視爲相似。

這意味着，順便說一句，兩個圖像真的很接近，但在不同的區域（kd樹的葉子）不會被認爲是相似的。 爲了克服這個問題，餘弦相似性可以用來代替歐幾里德距離。您可以在wiki中閱讀有關該主題的更多信息。