解釋這一算法（比較SURF算法分）

我需要知道，如果這個算法是一個已知的一個：解釋這一算法（比較SURF算法分）

void getMatches(IpVec &ipts1, IpVec &ipts2, IpPairVec &matches, float ratio) { 
    float dist, d1, d2; 
    Ipoint *match; 

    matches.clear(); 

    for (unsigned int i = 0; i < ipts1.size(); i++) { 
     d1 = d2 = FLT_MAX; 

     for (unsigned int j = 0; j < ipts2.size(); j++) { 
      dist = ipts1[i] - ipts2[j]; 

      if (dist < d1) // if this feature matches better than current best 
      { 
       d2 = d1; 
       d1 = dist; 
       match = &ipts2[j]; 
      } else if (dist < d2) // this feature matches better than second best 
      { 
       d2 = dist; 
      } 
     } 

     // If match has a d1:d2 ratio < 0.65 ipoints are a match 
     if (d1/d2 < ratio) { 
      // Store the change in position 
      ipts1[i].dx = match->x - ipts1[i].x; 
      ipts1[i].dy = match->y - ipts1[i].y; 
      matches.push_back(std::make_pair(ipts1[i], *match)); 
     } 
    } 
}

class Ipoint { 
public: 

    //! Destructor 

    ~Ipoint() { 
    }; 

    //! Constructor 

    Ipoint() : orientation(0) { 
    }; 

    //! Gets the distance in descriptor space between Ipoints 

    float operator-(const Ipoint &rhs) { 
     float sum = 0.f; 
     for (int i = 0; i < 64; ++i) { 
      //std::cout << i << "\n"; 
      try { 
       sum += (this->descriptor[i] - rhs.descriptor[i])*(this->descriptor[i] - rhs.descriptor[i]); 
      } catch (char *str) { 
       std::cout << "Caught some other exception: " << str << "\n"; 
      } 

     } 
     return sqrt(sum); 
    }; 

    //! Coordinates of the detected interest point 
    float x, y; 

    //! Detected scale 
    float scale; 

    //! Orientation measured anti-clockwise from +ve x-axis 
    float orientation; 

    //! Sign of laplacian for fast matching purposes 
    int laplacian; 

    //! Vector of descriptor components 
    float descriptor[64]; 

    //! Placeholds for point motion (can be used for frame to frame motion analysis) 
    float dx, dy; 

    //! Used to store cluster index 
    int clusterIndex; 
};

這SURF算法的結果進行比較。

這是最近鄰居算法嗎？看起來func正在搜索每個點的最近點。
我可以使用Quadtree或kd-tree來做同樣的事嗎？
有一個更好的算法來比較圖像點，並知道它們是否相同或相似？
優先我想將它們存儲到mysql中，並構建一個kd-tree來比較所有圖像中的1張圖像，這可能嗎？
RANSAC對於此任務中的任何內容都很有用？
有什麼方法可以捕獲誤報？

來源

2011-08-05 Wiliam

我投票給您最後的評論，沒有必要和時間回答。 – Wiliam

http://stackoverflow.com/questions/5962131/c-application-collapsing-after-some-hours需要你跟進。 –

你問了很多問題，我不認爲我可以回答所有問題，但這裏有儘可能多的問題的答案。

這肯定是一個最近鄰算法，其目的是要找到兩個最接近的點在第一向量中的每個點，然後檢查他們的距離之比是否小於一定的臨界值。
您可以與四叉樹或KD樹這樣做，而是因爲你的觀點都是一維的值，你可以做的更好的利用平衡二叉搜索樹。給定這樣一棵樹，如果你通過節點對一個鏈表進行線程化，你可以在二叉搜索樹中查找最接近的元素p，然後在每個步驟中遍歷（k + 1）個步驟，找到某個測試點p的k個最近鄰居方向，並採取你找到的k個最接近的點。這在時間O（lg n + k）中運行，其中n是點數並且k如上所述。這比現在更有效，每次查找需要O（n）個時間。

如果您的特徵向量的維數大於1但小於20，那麼使用kd-trees將是非常有效的度量。

對於更高的維度，您可能希望在應用kd樹之前使用PCA減少維數，或者使用更具可擴展性的ANN結構（如局部敏感散列）。
SURF最適合場景和物體檢測。如果您需要查明兩幅圖像是否相同，則使用全局描述符算法（如GIST）會更好。使用全局描述符的優點是，您可以獲得整個圖像的單個矢量，並使用簡單的Eucledian距離執行圖像比較。
你絕對可以使用MySQL來做這件事，因爲你不需要kd-tree。一個簡單的平衡二叉樹應該就足夠了。
RANSAC是一種估計對異常值有效的模型參數的方法。使用SURF功能將多張照片組合成3D場景非常有用。
檢查誤報肯定是一個機器學習練習，我在這方面沒有很好的訓練。你可能可以使用監督學習算法（如SVM，增強型決策樹或神經網絡）來做到這一點，但我不知道這方面的建議。

希望這有助於！

來源

2011-08-05 01:28:55 templatetypedef

對不起，我忘了告訴你點的課程，我認爲我需要64/128尺寸，所以也許對於100萬張圖片，我需要一個隨機kd-tree。我一直在閱讀關於GIST的內容，現在我正在使用SURF，並且我擁有本地特性，全局特性的概念對我來說是新的，我會尋找更多信息。如果我使用kd-tree，關於MySQL我必須先構建樹。謝謝。 – Wiliam

@Wiliam：當維數低於20時，kd-tree的性能最好。對於你的問題，你可能想要先使用類似PCA的東西來降低維度，或者使用更具可伸縮性的ANN結構，比如局部敏感散列。 –

@templatetypedef，uf，我不知道這是否是更好的解決方案。我在一些論文中使用過他們使用隨機kd-tree來存儲這些特徵，但是我不知道更多的細節...... – Wiliam

我只會回答5，因爲templatetypedef解決了其餘問題。 RANSAC是一種參數估計方法（有點像找到最適合一組數據點的線）。所以它在最近的鄰居搜索中並不直接有用。

來源

2011-08-05 02:40:21

謝謝，我已經在互聯網中用於加入圖像。 – Wiliam

解釋這一算法（比較SURF算法分）

回答

相關問題