將特徵匹配到數據庫的快速（er）方式

Question

我正在研究一個項目，其中我在圖像中描述了一組X & Y座標（每個要素5-10個點）特徵。我也有一個數以千計的功能的數據庫，每個功能都有相同類型的描述符。結果如下所示：

myFeature: (x1,y1), (x2,y2), (x3,y3)... 

myDatabase: Feature1: (x1,y1), (x2,y2), (x3,y3)... 
      Feature2: (x1,y1), (x2,y2), (x3,y3)... 
      Feature3: (x1,y1), (x2,y2), (x3,y3)... 
      ... 

我想在myDatabase中的功能中找到myFeature的最佳匹配。

什麼是匹配這些功能的最快方法？目前，我踩着雖然數據庫中的每個功能和比較每一個人的一點：

bestScore = 0 
for each feature in myDatabase: 
    score = 0 
    for each point descriptor in MyFeature: 
     find minimum distance from the current point to the... 
      points describing the current feature in the database 
     if the distance < threshold: 
      there is a match to the current point in the target feature 
      score += 1 

    if score > bestScore: 
     save feature as new best match 

這個搜索工作，但顯然它得到大型數據庫十分緩慢。有沒有人知道更快的方法來做這種類型的搜索，或者至少如果有一種方法可以快速排除明顯不符合描述符的功能？

Answer 1

從每個功能創建一個bitset（1和0的數組）。

爲您的搜索條件創建一個位掩碼，然後使用按位進行比較，並將搜索掩碼與您的功能進行比較。

通過這種方法，您可以將大部分工作轉移到負責保存東西的例程。而且，創建位掩碼不應該是計算密集型的。

如果你只是想排除絕對不能匹配的功能，那麼你的掩碼創建算法應該照顧它，並創建位掩碼有點模糊。

創建此類遮罩的最簡單方法可能是創建一個與您的要素矩陣一樣大的矩陣，並在爲該要素設置的每個座標中放置一個矩陣，並在每個不是的座標中放置一個零。然後將該矩陣轉換爲一維行。然後比較功能行然後按位搜索掩碼。

這與位圖索引在大型數據庫（例如oracle）上的工作方式類似，但具有不同的意圖，並且沒有內存中所有數據庫行的完整位圖圖像。

這是在按位比較的權力。

在32位機器上，如果您只需在點比較中使用整數進行比較，則可以對每條指令執行32次比較。根據架構的不同，它爲浮點運算提供更高的優勢。

Answer 2

這通常看起來像一個空間索引問題。這不是我的領域，但您可能需要構建一種樹狀索引，例如四叉樹，您可以使用它來輕鬆搜索功能。您可以從以下維基百科文章中找到一些鏈接：http://en.wikipedia.org/wiki/Spatial_index

這可能是一個問題，您可以輕鬆地在現有的空間數據庫中實現。它的描述非常類似於GIS。

你可以做的一件事是計算每個特徵的重力點，並用它來縮小搜索空間（一維搜索比構建索引更容易），但是它的缺點是隻是一種啓發式（取決於你的特徵的形狀，重力點可能最終在奇怪的地方）。