title: C++ - Finding nearest neighbor using opencv flann
body: <p>I have two set of points (cv::Point2f): setA and setB. For each point in setA, I want to find its nearest neighbor in setB. So, I have tried two methods:</p>
  
  <ol>
  <li><p>Linear search: for each point in setA, just simply scan through all points in setB to find nearest one.</p></li>
  <li><p>Using opencv kd-tree:</p>
  
  <p>_ First I built a kd-tree for setB using opencv flann:</p>
  
  <pre><code>cv::flann::KDTreeIndexParams indexParams;
  cv::flann::Index kdTree(cv::Mat(setB).reshape(1), indexParams);
  </code></pre>
  
  <p>_ Then, for each point in setA I do query to find nearest neighbor:</p>
  
  <pre><code>kdTree.knnSearch(point_in_setA, indices, dists, maxPoints);
  </code></pre></li>
  </ol>
  
  <p>Note: I set maxPoints to 1, cause I only need the nearest one.</p>
  
  <p>I do a bit study, and come out with some time complexity for each case:</p>
  
  <ol>
  <li><p>Linear search: O(M*N)</p></li>
  <li><p>Kd-Tree: NlogN + MlogN => first term for building kd-tree, second term is for querying</p></li>
  </ol>
  
  <p>Where M is number of points in setA, and N is for setB. And range of N: 100~1000, range of M: 10000~100000.</p>
  
  <p>So, the kd-tree is supposed to run much faster than the linear search method. However, when I run the real test on my laptop, the result is kd-tree method is slower than linear search (0.02~0.03s vs 0.4~0.5s).</p>
  
  <p>When I do profiling, I got hot spot at knnSearch() function, it takes 20.3% CPU time compares to 7.9% of linear search. </p>
  
  <p>Uhm, I read some online articles, they said to query kd-tree it usually take logN. But I am not sure about how opencv implement it.</p>
  
  <p>Anyone knows what's wrong here? Is there any parameter I should adjust in kd-tree or did I make mistake somewhere in the code or computation?</p>