edges.c

   1 /* Copyright (C) <2010> Douglas Bagnall <douglas@halo.gen.nz>
   2  *
   3  * This library is free software; you can redistribute it and/or
   4  * modify it under the terms of the GNU Library General Public
   5  * License as published by the Free Software Foundation; either
   6  * version 2 of the License, or (at your option) any later version.
   7  *
   8  * This library is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * Library General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Library General Public
  14  * License along with this library; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 02111-1307, USA.
  17  */
  18
  19
  20 #include "sparrow.h"
  21 #include "gstsparrow.h"
  22 #include "edges.h"
  23
  24 #include <string.h>
  25 #include <math.h>
  26
  27 #include "cv.h"
  28
  29 /* draw the line (in sparrow->colour) */
  30 static inline void
  31 draw_line(GstSparrow * sparrow, sparrow_line_t *line, guint8 *out){
  32   guint32 *p = (guint32 *)out;
  33   int i;
  34   if (line->dir == SPARROW_HORIZONTAL){
  35     p += line->offset * sparrow->out.width;
  36     for (i = 0; i < sparrow->out.width; i++){
  37       p[i] = sparrow->colour;
  38     }
  39   }
  40   else {
  41     guint32 *p = (guint32 *)out;
  42     p += line->offset;
  43     for(i = 0; i < sparrow->out.height; i++){
  44       *p = sparrow->colour;
  45       p += sparrow->out.width;
  46     }
  47   }
  48 }
  49
  50 /*
  51 */
  52
  53 #define SIG_WEIGHT 5
  54
  55 /*3 pixels manhatten distance makes you an outlier */
  56 #define OUTLIER_THRESHOLD 3 << (SPARROW_FIXED_POINT)
  57 #define OUTLIER_PENALTY 8
  58
  59 #define SIGNAL(c)((c).signal[SPARROW_HORIZONTAL] + (c).signal[SPARROW_VERTICAL])
  60
  61 static void
  62 find_corners(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl){
  63   int i;
  64   sparrow_cluster_t *clusters = malloc_or_die(fl->n_hlines * fl->n_vlines * sizeof(sparrow_cluster_t));
  65   gint x, y;
  66
  67   for (y = 0; y < sparrow->in.height; y++){
  68     for (x = 0; x < sparrow->in.width; x++){
  69       sparrow_intersect_t *p = &fl->map[y * sparrow->in.width + x];
  70       /*remembering that 0 is valid as a line no, but not as a signal */
  71       if (! p->signal[SPARROW_HORIZONTAL] ||
  72           ! p->signal[SPARROW_VERTICAL]){
  73         continue;
  74       }
  75       /*This one is lobbying for the position of the corner.*/
  76
  77       /*XXX what to do in the case that there is no intersection?  often cases
  78         this will happen in the dark bits and be OK. But if it happens in the
  79         light?*/
  80       /*linearise the xy coordinates*/
  81       int vline = p->lines[SPARROW_VERTICAL];
  82       int hline = p->lines[SPARROW_HORIZONTAL];
  83       sparrow_cluster_t *cluster = &clusters[vline * fl->n_hlines + hline];
  84       int n = cluster->n;
  85       if (n < 8){
  86         cluster->voters[n].x = x << SPARROW_FIXED_POINT;
  87         cluster->voters[n].y = y << SPARROW_FIXED_POINT;
  88         cluster->voters[n].signal = (SIG_WEIGHT + p->signal[SPARROW_HORIZONTAL]) *
  89           (SIG_WEIGHT + p->signal[SPARROW_VERTICAL]);
  90         cluster->n++;
  91       }
  92       else {
  93         GST_DEBUG("more than 8 pixels at cluster for corner %d, %d\n",
  94             vline, hline);
  95         /*if this message ever turns up, replace the weakest signals or add
  96           more slots.*/
  97       }
  98     }
  99   }
 100
 101   for (i = 0; i < fl->n_hlines * fl->n_vlines; i++){
 102     /* how to do this?
 103        1. centre of gravity (x,y, weighted average)
 104        2. discard outliers? look for connectedness? but if 2 are outliers?
 105      */
 106     sparrow_cluster_t *cluster = clusters + i;
 107     int xsum, ysum;
 108     int xmean, ymean;
 109     int votes = 1;
 110     while(votes) { /* don't diminish signal altogether */
 111       int j;
 112       xsum = 0;
 113       ysum = 0;
 114       votes = 0;
 115       for (j = 0; j < cluster->n; j++){
 116         votes += cluster->voters[j].signal;
 117         ysum += cluster->voters[j].y * cluster->voters[j].signal;
 118         xsum += cluster->voters[j].x * cluster->voters[j].signal;
 119       }
 120       xmean = xsum / votes;
 121       ymean = ysum / votes;
 122       int worst = -1;
 123       int worstn;
 124       int devsum = 0;
 125       for (j = 0; j < cluster->n; j++){
 126         int xdiff = abs(cluster->voters[j].x - xmean);
 127         int ydiff = abs(cluster->voters[j].y - ymean);
 128         devsum += xdiff + ydiff;
 129         if (xdiff + ydiff > worst){
 130           worst = xdiff + ydiff;
 131           worstn = j;
 132         }
 133       }
 134       /*a bad outlier has significantly greater than average deviation
 135         (but how much is bad? median deviation would be more useful)*/
 136       if (worst > 3 * devsum / cluster->n){
 137         /* reduce the worst ones weight. it is a silly aberration. */
 138         cluster->voters[worstn].signal /= OUTLIER_PENALTY;
 139         GST_DEBUG("dropping outlier at %s,%s (mean %s,%s)\n",
 140             cluster->voters[worstn].x, cluster->voters[worstn].y, xmean, ymean);
 141         continue;
 142       }
 143       break;
 144     }
 145     GST_DEBUG("found corner at (%3f, %3f)\n", xmean / 256.0, ymean / 256.0);
 146
 147     /*XXXX Now:
 148       1. calculate deltas toward adjacent corners.
 149       2. record the corners in sparrow object
 150     */
 151
 152   }
 153 }
 154
 155
 156 /* With no line drawn (in our colour) look at the background noise.  Any real
 157    signal has to be stringer than this.
 158
 159    XXX looking for simple maximum -- maybe heap or histogram might be better,
 160    so as to be less susceptible to wierd outliers (e.g., bad pixels).  */
 161 static void
 162 look_for_threshold(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl){
 163   int i;
 164   guint32 colour;
 165   guint32 signal;
 166   guint32 *in32 = (guint32 *)in;
 167   guint32 highest = 0;
 168   for (i = 0;  i < (int)sparrow->in.size; i++){
 169     colour = in32[i] & sparrow->colour;
 170     signal = ((colour >> fl->shift1) +
 171         (colour >> fl->shift2)) & 0x1ff;
 172     if (signal > highest){
 173       highest = signal;
 174     }
 175   }
 176   fl->threshold = highest + 10;
 177   GST_DEBUG("found maximum noise of %s, using threshold %s\n", highest, fl->threshold);
 178 }
 179
 180
 181 static void
 182 look_for_line(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl,
 183     sparrow_line_t *line){
 184   guint i;
 185   guint32 colour;
 186   int signal;
 187   guint32 *in32 = (guint32 *)in;
 188   for (i = 0; i < sparrow->in.size; i++){
 189     colour = in32[i] & sparrow->colour;
 190     signal = ((colour >> fl->shift1) +
 191         (colour >> fl->shift2)) & 0x1ff;
 192     if (signal > fl->threshold){
 193       if (fl->map[i].lines[line->dir]){
 194         GST_DEBUG("HEY, expected point %d to be in line %d (dir %d)"
 195             "and thus empty, but it is also in line %d\n",
 196             i, line->index, line->dir, fl->map[i].lines[line->dir]);
 197       }
 198       fl->map[i].lines[line->dir] = line->index;
 199       fl->map[i].signal[line->dir] = signal;
 200     }
 201   }
 202 }
 203
 204
 205 /* show each line for 2 frames, then wait sparrow->lag frames, leaving line on
 206    until last one.
 207  */
 208
 209 INVISIBLE sparrow_state
 210 mode_find_edges(GstSparrow *sparrow, guint8 *in, guint8 *out){
 211   sparrow_find_lines_t *fl = (sparrow_find_lines_t *)&sparrow->helper_struct;
 212   sparrow_line_t *line = fl->shuffled_lines[fl->current];
 213   sparrow->countdown--;
 214   memset(out, 0, sparrow->out.size);
 215   if (sparrow->countdown){
 216     /* show the line except on the first round, when we find a threshold*/
 217     if (fl->threshold){
 218       draw_line(sparrow, line, out);
 219     }
 220   }
 221   else{
 222       /*show nothing, look for result */
 223     if (fl->threshold){
 224       if (fl->current == fl->n_lines){
 225         goto done;
 226       }
 227       look_for_line(sparrow, in, fl, line);
 228       fl->current++;
 229     }
 230     else {
 231       look_for_threshold(sparrow, in, fl);
 232     }
 233     sparrow->countdown = sparrow->lag + 2;
 234   }
 235   return SPARROW_STATUS_QUO;
 236  done:
 237   /*match up lines and find corners */
 238   find_corners(sparrow, in, fl);
 239
 240
 241   /*free stuff!, including fl, and reset pointer to NULL*/
 242
 243   return SPARROW_NEXT_STATE;
 244 }
 245
 246
 247 static void
 248 setup_colour_shifts(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 249   switch (sparrow->colour){
 250   case SPARROW_WHITE:
 251   case SPARROW_GREEN:
 252     fl->shift1 = sparrow->in.gshift;
 253     fl->shift2 = sparrow->in.gshift;
 254     break;
 255   case SPARROW_MAGENTA:
 256     fl->shift1 = sparrow->in.rshift;
 257     fl->shift2 = sparrow->in.bshift;
 258     break;
 259   }
 260 }
 261
 262 INVISIBLE void
 263 init_find_edges(GstSparrow *sparrow){
 264   gint32 w = sparrow->out.width;
 265   gint32 h = sparrow->out.height;
 266   gint i;
 267   sparrow_find_lines_t *fl = zalloc_aligned_or_die(sizeof(sparrow_find_lines_t));
 268   sparrow->helper_struct = (void *)fl;
 269
 270   gint h_lines = (h + LINE_PERIOD - 1) / LINE_PERIOD;
 271   gint v_lines = (w + LINE_PERIOD - 1) / LINE_PERIOD;
 272   gint n_lines = (h_lines + v_lines);
 273   fl->n_hlines = h_lines;
 274   fl->n_vlines = v_lines;
 275   fl->n_lines = n_lines;
 276
 277   fl->h_lines = malloc_aligned_or_die(sizeof(sparrow_line_t) * n_lines);
 278   fl->shuffled_lines = malloc_aligned_or_die(sizeof(sparrow_line_t*) * n_lines);
 279   fl->map = zalloc_aligned_or_die(sizeof(sparrow_intersect_t) * sparrow->in.pixcount);
 280
 281   sparrow_line_t *line = fl->h_lines;
 282   sparrow_line_t **sline = fl->shuffled_lines;
 283   int offset = LINE_PERIOD / 2;
 284
 285   for (i = 0, offset = LINE_PERIOD / 2; offset < h;
 286        i++, offset += LINE_PERIOD){
 287     line->offset = offset;
 288     line->dir = SPARROW_HORIZONTAL;
 289     line->index = i;
 290     *sline = line;
 291     line++;
 292     sline++;
 293   }
 294
 295   /*now add the vertical lines */
 296   fl->v_lines = line;
 297   for (i = 0, offset = LINE_PERIOD / 2; offset < w;
 298        i++, offset += LINE_PERIOD){
 299     line->offset = offset;
 300     line->dir = SPARROW_VERTICAL;
 301     line->index = i;
 302     *sline = line;
 303     line++;
 304     sline++;
 305   }
 306
 307   GST_DEBUG("allocated %s lines, used %s\n", n_lines, line - fl->h_lines);
 308
 309   /*now shuffle (triangluar, to no particular advantage) */
 310   for (i = 0; i < n_lines - 1; i++){
 311     int j = RANDINT(sparrow, i + 1, n_lines);
 312     sparrow_line_t *tmp = fl->shuffled_lines[j];
 313     fl->shuffled_lines[j] = fl->shuffled_lines[i];
 314     fl->shuffled_lines[i] = tmp;
 315   }
 316
 317   setup_colour_shifts(sparrow, fl);
 318   sparrow->countdown = sparrow->lag + 2;
 319
 320   sparrow->mesh = malloc_aligned_or_die(sizeof(sparrow_corner_t) * h_lines * v_lines);
 321 }