はこのアルゴリズム（SURFアルゴリズムでポイントを比較）

Question

を説明し、私はこのアルゴリズムが知られているものであるかどうかを知る必要があります。

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アルゴリズムの結果を比較します。

1. これは最近傍アルゴリズムですか。それは、関数がすべての点の最も近い点を探索しているように見えます。
2. Quadtreeまたはkd-treeを使用して同じことを実行できますか？
3. イメージポイントと比較して、それらが同じか類似しているかどうかを確認するアルゴリズムがありますか？
4. 私はそれらをmysqlに保存し、すべての画像を通して1つの画像を比較するkdツリーを構築したいと思いますか？
5. RANSACはこのタスクの何かに役に立ちますか？
6. 偽陽性を検出する方法はありますか？

Answer 1

あなたは多くの質問をしましたが、私はそれらのすべてに答えることはできませんが、できる限り多くの質問に対する回答があります。

1. これは最も確かに目標は最初のベクトル内の各点に最も近い二つのポイントを検索し、それらの距離の比は、いくつかのカットオフ値未満であるかどうかをチェックすることで、最近傍アルゴリズムです。

2. あなたは四分木やKD-ツリーでこれを行うことができますが、あなたのポイントは、あなたがバランスの取れた、バイナリ検索ツリーを使用してより良い行うことができ、すべての1次元の値であるため。このようなツリーが与えられた場合、ノードを介してリンクリストをスレッド化すると、バイナリ検索ツリー内の最も近い要素pを検索し、それぞれの（k + 1）ステップをトラバースすることによって、あるテストポイントpまでのk個の最近隣を見つけることができますあなたが見つけたもののk最近点を取る。これは時間O（lg n + k）で実行され、ここでnは点の数であり、kは上と同じです。これは、あなたが現在行っているものよりも実質的に効率的です。これは、ルックアップごとにO（n）時間がかかります。

   特徴ベクトルの次元数が1より大きく20より小さい場合は、kdツリーを使用することが非常に効果的です。

   高次元の場合は、kdツリーを適用する前にPCAを使用してディメンションの数を減らすか、ローカリティセンシティブハッシュなどのよりスケーラブルなANN構造を使用することができます。

3. SURFは、シーンとオブジェクトの検出に最適です。 2つの画像が同じであるかどうかを調べる必要がある場合は、GISTなどのグローバル記述子アルゴリズムを使用すると効果的です。グローバル記述子を使用する利点は、イメージ全体に対して単一のベクトルを取得し、単純なEucledian距離でイメージの比較を実行することです。

4. あなたはkdツリーが不要なので、MySQLを使って間違いなくこれを行うことができます。単純な平衡二分木で十分であるはずです。

5. RANSACは、外れ値に対してロバストなモデルパラメータを推定する方法です。これは、複数の写真を3Dシーンに結合するためにSURF機能を使用する場合に便利です。

6. 偽陽性を確認することは間違いなく機械学習の練習であり、私はその分野で十分に訓練されていません。おそらく、教師付き学習アルゴリズム（SVM、ブーストされた決定木、ニューラルネットワークなど）を使ってこれを行うことができますが、これについて助言するのに十分なものはありません。

希望します。

Answer 2

templatetypedefが残りの部分に対処しているので、私はちょうど5に答えます。 RANSACはパラメータ推定方法です（データポイントのセットに最適な線を見つけるのと同じように）。したがって、最近隣の検索では直接役に立ちません。