From 5689b161a8a1b8abd5623a0c863ec5765c0ba452 Mon Sep 17 00:00:00 2001
From: Douglas Bagnall <douglas@paradise.net.nz>
Date: Tue, 25 May 2010 01:43:41 +1200
Subject: [PATCH] try to discard unconnected points.

finding the median might be easier and better after all.
---
 edges.c   | 59 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sparrow.h | 11 +++++++++++
 2 files changed, 70 insertions(+)

diff --git a/edges.c b/edges.c
index eea0e37..4d5210c 100644
--- a/edges.c
+++ b/edges.c
@@ -312,7 +312,64 @@ find_corners_make_clusters(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t
     }
   }
 }
+
+/* look for connected group. if there is more than one connected group,
+ despair.*/
+
+static inline void
+discard_cluster_outliers(sparrow_cluster_t *cluster)
+{
+  sparrow_voter_t *v = cluster->voters;
+  int i, j;
+
+  guint32 touch[CLUSTER_SIZE];
+
+  while (cluster->n){
+    guint32 all = (1 << cluster->n) - 1;
+    for (i = 0; i < cluster->n; i++){
+      touch[i] = 1 << i;
+    }
+
+    for (i = 0; i <  cluster->n - 1; i++){
+      for (j = i + 1; j < cluster->n; j++){
+        if (((abs(v[i].x - v[j].x) <= 2) && (abs(v[i].y - v[j].y) <= 2)) ||
+            (touch[i] & touch[j])){
+          touch[i] |= touch[j];
+          touch[j] = touch[i];
+        }
+      }
+    }
+    if (touch[cluster->n - 1] == all){
+      break;
+    }
+    /* something is wrong! somebody is disconnected!  expel them!?
+       backpropagate connectedness, find the maximum popcount, discard the
+       others. */
+    int bcount = 0;
+    guint bmask = 0;
+
+    for (i = cluster->n - 1; i >= 0; i++){
+      if (bmask != touch[i] &&
+          bcount < (int)popcount32(touch[i])){
+        bmask = touch[i];
+        bcount = popcount32(touch[i]);
+      }
+      for (j = 0; j < i; j++){
+        touch[j] = (touch[j] & touch[i]) ? touch[i] : touch[j];
+      }
+    }
+    if (bcount > cluster->n / 2){
+      j = 0;
+      for (i = 0; i < cluster->n; i++){
+        if (touch[i] == bmask){
+          v[j] = v[i];
+          j++;
+        }
+      }
+      cluster->n = j;
+    }
   }
+}
 
 
 
@@ -338,6 +395,8 @@ find_corners_make_corners(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t
         continue;
       }
 
+      discard_cluster_outliers(sparrow_cluster_t *cluster);
+
       int xsum, ysum;
       int xmean, ymean;
       int votes;
diff --git a/sparrow.h b/sparrow.h
index 42325ca..0946271 100644
--- a/sparrow.h
+++ b/sparrow.h
@@ -127,8 +127,19 @@ rng_uniform_double(GstSparrow *sparrow, double limit){
 
 #define DISASTEROUS_CRASH(msg) GST_ERROR("DISASTER: %s\n%-25s  line %4d \n", (msg), __func__, __LINE__);
 
+static inline guint32
+popcount32(guint32 x)
+{
+  x = x - ((x >> 1) & 0x55555555);
+  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+  x = (x + (x >> 4)) & 0x0F0F0F0F;
+  x = x + (x >> 8);
+  x = x + (x >> 16);
+  return x & 0x000000FF;
+}
 
 
+/*XXX optimised for 32 bit!*/
 static inline guint32
 popcount64(guint64 x64)
 {
-- 
2.11.4.GIT