Camera tracking integration

===========================

Some improvements for feature detectors:

- Sort features by score when filtering features by
  distance using FAST library.
- Added option to place markers only in areas outlined
  by grease pencil.

2 files changed, 89 insertions, 29 deletions

diff --git a/extern/libmv/libmv/simple_pipeline/detect.cc b/extern/libmv/libmv/simple_pipeline/detect.cc
index b316f427649..8ac42ab0aba 100644
--- a/extern/libmv/libmv/simple_pipeline/detect.cc
+++ b/extern/libmv/libmv/simple_pipeline/detect.cc
@@ -35,6 +35,14 @@ namespace libmv {
 
 typedef unsigned int uint;
 
+int featurecmp(const void *a_v, const void *b_v)
+{
+  Feature *a = (Feature*)a_v;
+  Feature *b = (Feature*)b_v;
+
+  return b->score - a->score;
+}
+
 std::vector<Feature> DetectFAST(const unsigned char* data, int width, int height, int stride,
                            int min_trackness, int min_distance) {
   std::vector<Feature> features;
@@ -54,21 +62,43 @@ std::vector<Feature> DetectFAST(const unsigned char* data, int width, int height
   // TODO(MatthiasF): A resolution independent parameter would be better than distance
   // e.g. a coefficient going from 0 (no minimal distance) to 1 (optimal circle packing)
   // FIXME(MatthiasF): this method will not necessarily give all maximum markers
-  if(num_features) features.reserve(num_features);
-  for(int i = 0; i < num_features; ++i) {
-    xy xy = nonmax[i];
-    Feature a = { xy.x, xy.y, scores[i], 7 };
-    // compare each feature against filtered set
-    for(int j = 0; j < features.size(); j++) {
-      Feature& b = features[j];
-      if ( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) < min_distance*min_distance ) {
-        // already a nearby feature
-        goto skip;
+  if(num_features) {
+    Feature *all_features = new Feature[num_features];
+
+    for(int i = 0; i < num_features; ++i) {
+      Feature a = { nonmax[i].x, nonmax[i].y, scores[i], 0 };
+      all_features[i] = a;
+    }
+
+    qsort((void *)all_features, num_features, sizeof(Feature), featurecmp);
+
+    features.reserve(num_features);
+
+    int prev_score = all_features[0].score;
+    for(int i = 0; i < num_features; ++i) {
+      bool ok = true;
+      Feature a = all_features[i];
+      if(a.score>prev_score)
+        abort();
+      prev_score = a.score;
+
+      // compare each feature against filtered set
+      for(int j = 0; j < features.size(); j++) {
+        Feature& b = features[j];
+        if ( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) < min_distance*min_distance ) {
+          // already a nearby feature
+          ok = false;
+          break;
+        }
+      }
+
+      if(ok) {
+        // add the new feature
+        features.push_back(a);
       }
     }
-    // otherwise add the new feature
-    features.push_back(a);
-    skip: ;
+
+    delete [] all_features;
   }
   free(scores);
   free(nonmax);
diff --git a/extern/libmv/patches/detect.patch b/extern/libmv/patches/detect.patch
index 0d9b88faa96..36fea8427db 100644
--- a/extern/libmv/patches/detect.patch
+++ b/extern/libmv/patches/detect.patch
@@ -1,8 +1,8 @@
 diff --git a/src/libmv/simple_pipeline/detect.cc b/src/libmv/simple_pipeline/detect.cc
-index 6fc0cdd..b316f42 100644
+index 6fc0cdd..8ac42ab 100644
 --- a/src/libmv/simple_pipeline/detect.cc
 +++ b/src/libmv/simple_pipeline/detect.cc
-@@ -23,15 +23,59 @@
+@@ -23,15 +23,89 @@
  ****************************************************************************/
  
  #include "libmv/simple_pipeline/detect.h"
@@ -19,6 +19,14 @@ index 6fc0cdd..b316f42 100644
  
  typedef unsigned int uint;
  
++int featurecmp(const void *a_v, const void *b_v)
++{
++  Feature *a = (Feature*)a_v;
++  Feature *b = (Feature*)b_v;
++
++  return b->score - a->score;
++}
++
 +std::vector<Feature> DetectFAST(const unsigned char* data, int width, int height, int stride,
 +                           int min_trackness, int min_distance) {
 +  std::vector<Feature> features;
@@ -38,21 +46,43 @@ index 6fc0cdd..b316f42 100644
 +  // TODO(MatthiasF): A resolution independent parameter would be better than distance
 +  // e.g. a coefficient going from 0 (no minimal distance) to 1 (optimal circle packing)
 +  // FIXME(MatthiasF): this method will not necessarily give all maximum markers
-+  if(num_features) features.reserve(num_features);
-+  for(int i = 0; i < num_features; ++i) {
-+    xy xy = nonmax[i];
-+    Feature a = { xy.x, xy.y, scores[i], 7 };
-+    // compare each feature against filtered set
-+    for(int j = 0; j < features.size(); j++) {
-+      Feature& b = features[j];
-+      if ( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) < min_distance*min_distance ) {
-+        // already a nearby feature
-+        goto skip;
++  if(num_features) {
++    Feature *all_features = new Feature[num_features];
++
++    for(int i = 0; i < num_features; ++i) {
++      Feature a = { nonmax[i].x, nonmax[i].y, scores[i], 0 };
++      all_features[i] = a;
++    }
++
++    qsort((void *)all_features, num_features, sizeof(Feature), featurecmp);
++
++    features.reserve(num_features);
++
++    int prev_score = all_features[0].score;
++    for(int i = 0; i < num_features; ++i) {
++      bool ok = true;
++      Feature a = all_features[i];
++      if(a.score>prev_score)
++        abort();
++      prev_score = a.score;
++
++      // compare each feature against filtered set
++      for(int j = 0; j < features.size(); j++) {
++        Feature& b = features[j];
++        if ( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) < min_distance*min_distance ) {
++          // already a nearby feature
++          ok = false;
++          break;
++        }
++      }
++
++      if(ok) {
++        // add the new feature
++        features.push_back(a);
 +      }
 +    }
-+    // otherwise add the new feature
-+    features.push_back(a);
-+    skip: ;
++
++    delete [] all_features;
 +  }
 +  free(scores);
 +  free(nonmax);
@@ -64,7 +94,7 @@ index 6fc0cdd..b316f42 100644
  static uint SAD(const ubyte* imageA, const ubyte* imageB, int strideA, int strideB) {
    __m128i a = _mm_setzero_si128();
    for(int i = 0; i < 16; i++) {
-@@ -52,7 +96,7 @@ static uint SAD(const ubyte* imageA, const ubyte* imageB, int strideA, int strid
+@@ -52,7 +126,7 @@ static uint SAD(const ubyte* imageA, const ubyte* imageB, int strideA, int strid
  }
  #endif