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 /*
  30 */
  31
  32 #define SIG_WEIGHT 2
  33
  34 /*3 pixels manhatten distance makes you an outlier */
  35 #define OUTLIER_THRESHOLD 3 << (SPARROW_FIXED_POINT)
  36 #define OUTLIER_PENALTY 8
  37
  38 /*
  39 */
  40
  41 #define SPARROW_MAP_LUT_SHIFT 1
  42 #define SPARROW_FP_2_LUT (SPARROW_FIXED_POINT - SPARROW_MAP_LUT_SHIFT)
  43
  44 #define OFFSET(x, y, w)((((y) * (w)) >> SPARROW_FIXED_POINT) + ((x) >> SPARROW_FIXED_POINT))
  45
  46
  47 #define FL_DUMPFILE "/tmp/edges.dump"
  48
  49 static void dump_edges_info(GstSparrow *sparrow, sparrow_find_lines_t *fl, const char *filename){
  50   GST_DEBUG("about to save to %s\n", filename);
  51   FILE *f = fopen(filename, "w");
  52   /* simply write fl, map, clusters and mesh in sequence */
  53   GST_DEBUG("fl is %p, file is %p\n", fl, f);
  54   GST_DEBUG("fl: %d x %d\n", sizeof(sparrow_find_lines_t), 1);
  55   fwrite(fl, sizeof(sparrow_find_lines_t), 1, f);
  56   GST_DEBUG("fl->map %d x %d\n", sizeof(sparrow_intersect_t), sparrow->in.pixcount);
  57   fwrite(fl->map, sizeof(sparrow_intersect_t), sparrow->in.pixcount, f);
  58   GST_DEBUG("fl->clusters  %d x %d\n", sizeof(sparrow_cluster_t), fl->n_hlines * fl->n_vlines);
  59   fwrite(fl->clusters, sizeof(sparrow_cluster_t), fl->n_hlines * fl->n_vlines, f);
  60   GST_DEBUG("fl->mesh  %d x %d\n", sizeof(sparrow_corner_t), fl->n_hlines * fl->n_vlines);
  61   fwrite(fl->mesh, sizeof(sparrow_corner_t), fl->n_hlines * fl->n_vlines, f);
  62   fclose(f);
  63 }
  64
  65 static void read_edges_info(GstSparrow *sparrow, sparrow_find_lines_t *fl, const char *filename){
  66   FILE *f = fopen(filename, "r");
  67   sparrow_find_lines_t fl2;
  68   size_t read = fread(&fl2, sizeof(sparrow_find_lines_t), 1, f);
  69   assert(fl2.n_hlines == fl->n_hlines);
  70   assert(fl2.n_vlines == fl->n_vlines);
  71
  72   guint n_corners = fl->n_hlines * fl->n_vlines;
  73   read += fread(fl->map, sizeof(sparrow_intersect_t), sparrow->in.pixcount, f);
  74   read += fread(fl->clusters, sizeof(sparrow_cluster_t), n_corners, f);
  75   read += fread(fl->mesh, sizeof(sparrow_corner_t), n_corners, f);
  76   fclose(f);
  77 }
  78
  79
  80 int sort_median(int *a, guint n)
  81 {
  82   guint i, j;
  83   /*stupid sort, but n is very small*/
  84   for (i = 0; i <  n; i++){
  85     for (j = i + 1; j < n; j++){
  86       if (a[i] > a[j]){
  87         int tmp = a[j];
  88         a[j] = a[i];
  89         a[i] = tmp;
  90       }
  91     }
  92   }
  93   guint middle = n / 2;
  94   int answer = a[middle];
  95
  96   if ((n & 1) == 0){
  97     answer += a[middle - 1];
  98     answer /= 2;
  99   }
 100   return answer;
 101 }
 102
 103
 104
 105
 106
 107 static void corners_to_lut(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 108   //DEBUG_FIND_LINES(fl);
 109   sparrow_map_t *map = &sparrow->map; /*rows in sparrow->out */
 110   guint8 *mask = sparrow->screenmask; /*mask in sparrow->in */
 111   sparrow_corner_t *mesh = fl->mesh;   /*maps regular points in ->out to points in ->in */
 112
 113   int mesh_w = fl->n_vlines;
 114   int mesh_h = fl->n_hlines;
 115   int in_w = sparrow->in.width;
 116   int mcy, mmy, mcx; /*Mesh Corner|Modulus X|Y*/
 117
 118   int x;
 119   sparrow_map_row_t *row = map->rows;
 120   sparrow_map_point_t *p = map->point_mem;
 121   sparrow_corner_t *mesh_row = mesh;
 122   for(mcy = 0; mcy < mesh_h; mcy++){
 123     for (mmy = 0; mmy < LINE_PERIOD; mmy++){
 124       sparrow_corner_t *mesh_square = mesh_row;
 125       row->points = p;
 126       row->start = 0;
 127       row->end = 0;
 128       for(mcx = 0; mcx < mesh_w; mcx++){
 129         if (mesh_square->used){
 130           int iy = mesh_square->in_y + mmy * mesh_square->dyd;
 131           int ix = mesh_square->in_x + mmy * mesh_square->dxd;
 132           int ii = OFFSET(ix, iy, in_w);
 133           int ii_end = OFFSET(ix + (LINE_PERIOD - 1) * mesh_square->dxr,
 134               iy + (LINE_PERIOD - 1) * mesh_square->dyr, in_w);
 135           int start_on = mask[ii];
 136           int end_on = mask[ii_end];
 137           if(start_on && end_on){
 138             /*add the point, maybe switch on */
 139             if (row->start == row->end){/* if both are 0 */
 140               row->start = mcx * LINE_PERIOD;
 141             }
 142             p->x = ix;
 143             p->y = iy;
 144             p->dx = mesh_square->dxr;
 145             p->dy = mesh_square->dyr;
 146             p++;
 147           }
 148           else if (start_on){
 149             /*add the point, switch off somewhere in the middle*/
 150             for (x = 1; x < LINE_PERIOD; x++){
 151               iy += mesh_square->dyr;
 152               ix += mesh_square->dxr;
 153               ii = OFFSET(ix, iy, in_w);
 154               if (mask[ii]){
 155                 /*point is not in the same column with the others,
 156                   but sparrow knows this because the row->start says so */
 157                 row->start = mcx + x;
 158                 p->x = ix;
 159                 p->y = iy;
 160                 p->dx = mesh_square->dxr;
 161                 p->dy = mesh_square->dyr;
 162                 p++;
 163                 break;
 164               }
 165             }
 166           }
 167           else if (end_on){
 168             /* add some, switch off */
 169             for (x = 1; x < LINE_PERIOD; x++){
 170               iy += mesh_square->dyr;
 171               ix += mesh_square->dxr;
 172               ii = OFFSET(ix, iy, in_w);
 173               if (! mask[ii]){
 174                 row->end = mcx + x;
 175                 break;
 176               }
 177             }
 178           }
 179           else {
 180             /*3 cases:
 181               start > end: this is first off pixel.
 182               start == end: row hasn't started (both 0)
 183               start < end: both are set -- row is done
 184             */
 185             if (row->start > row->end){
 186               row->end = mcx * LINE_PERIOD;
 187             }
 188             else if (row->start < row->end){
 189               break;
 190             }
 191           }
 192         }
 193         mesh_square++;
 194       }
 195       row++;
 196     }
 197     mesh_row += mesh_w;
 198   }
 199 }
 200
 201 UNUSED static void
 202 corners_to_full_lut(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 203   //DEBUG_FIND_LINES(fl);
 204   sparrow_corner_t *mesh = fl->mesh;   /*maps regular points in ->out to points in ->in */
 205   sparrow_map_lut_t *map_lut = sparrow->map_lut;
 206   int mesh_w = fl->n_vlines;
 207   int mesh_h = fl->n_hlines;
 208   int mcy, mmy, mcx, mmx; /*Mesh Corner|Modulus X|Y*/
 209   int i = 0;
 210   sparrow_corner_t *mesh_row = mesh;
 211   for(mcy = 0; mcy < mesh_h; mcy++){
 212     for (mmy = 0; mmy < LINE_PERIOD; mmy++){
 213       sparrow_corner_t *mesh_square = mesh_row;
 214       for(mcx = 0; mcx < mesh_w; mcx++){
 215         int iy = mesh_square->in_y + mmy * mesh_square->dyd;
 216         int ix = mesh_square->in_x + mmy * mesh_square->dxd;
 217         for (mmx = 0; mmx < LINE_PERIOD; mmx++, i++){
 218           map_lut[i].x = ix >> SPARROW_FP_2_LUT;
 219           map_lut[i].y = iy >> SPARROW_FP_2_LUT;
 220           ix += mesh_square->dxr;
 221           iy += mesh_square->dyr;
 222         }
 223         mesh_square++;
 224       }
 225     }
 226     mesh_row += mesh_w;
 227   }
 228   sparrow->map_lut = map_lut;
 229 }
 230
 231 #define DIV ((double)(1 << SPARROW_FIXED_POINT))
 232 #define INTXY(x)((x) / (1 << SPARROW_FIXED_POINT))
 233 #define FLOATXY(x)(((double)(x)) / (1 << SPARROW_FIXED_POINT))
 234 static void
 235 debug_corners_image(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 236   sparrow_corner_t *mesh = fl->mesh;
 237   guint32 *data = (guint32*)fl->debug->imageData;
 238   guint w = fl->debug->width;
 239   memset(data, 0, sparrow->in.size);
 240   guint32 colours[4] = {0xff0000ff, 0x0000ff00, 0x00ff0000, 0xcccccccc};
 241   for (int i = 0; i < fl->n_vlines * fl->n_hlines; i++){
 242     sparrow_corner_t *c = &mesh[i];
 243     int x = c->in_x;
 244     int y = c->in_y;
 245     GST_DEBUG("i %d used %d x: %f, y: %f  dxr %f dyr %f dxd %f dyd %f\n"
 246         "int x, y %d,%d (raw %d,%d) data %p\n",
 247         i, c->used, FLOATXY(x), FLOATXY(y),
 248         FLOATXY(c->dxr), FLOATXY(c->dyr), FLOATXY(c->dxd), FLOATXY(c->dyd),
 249         INTXY(x), INTXY(y), x, y, data);
 250     int txr = x;
 251     int txd = x;
 252     int tyr = y;
 253     int tyd = y;
 254     for (int j = 1; j < LINE_PERIOD; j++){
 255       txr += c->dxr;
 256       txd += c->dxd;
 257       tyr += c->dyr;
 258       tyd += c->dyd;
 259       data[INTXY(tyr) * w + INTXY(txr)] = 0x000088;
 260       data[INTXY(tyd) * w + INTXY(txd)] = 0x663300;
 261     }
 262 #if 0
 263 #define LP8 (LINE_PERIOD / 8)
 264 #define LP4 (LINE_PERIOD / 4)
 265 #define LP2 (LINE_PERIOD / 2)
 266     data[INTXY(y + c->dyr * LP8) * w + INTXY(x + c->dxr * LP8)] = 0xbbbbbbbb;
 267     data[INTXY(y + c->dyr * LP4) * w + INTXY(x + c->dxr * LP4)] = 0xaaaaaaaa;
 268     data[INTXY(y + c->dyr * LP2) * w + INTXY(x + c->dxr * LP2)] = 0x99999999;
 269     data[INTXY(y + c->dyd * LP8) * w + INTXY(x + c->dxd * LP8)] = 0xbb6666bb;
 270     data[INTXY(y + c->dyd * LP4) * w + INTXY(x + c->dxd * LP4)] = 0xaa5555aa;
 271     data[INTXY(y + c->dyd * LP2) * w + INTXY(x + c->dxd * LP2)] = 0x99444499;
 272 #endif
 273     data[INTXY(y) * w + INTXY(x)] = colours[MIN(c->used, 2)];
 274   }
 275   MAYBE_DEBUG_IPL(fl->debug);
 276 }
 277
 278
 279 static void
 280 debug_clusters(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 281   //sparrow_cluster_t *clusters = fl->clusters;
 282 }
 283
 284 /*signal product is close to 18 bits. reduce to 4 */
 285 #define SIGNAL_QUANT (1 << 14)
 286
 287 /*maximum number of pixels in a cluster */
 288 #define CLUSTER_SIZE 8
 289
 290
 291 /*create the mesh */
 292 static void
 293 make_clusters(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 294   sparrow_cluster_t *clusters = fl->clusters;
 295   int x, y;
 296   /*each point in fl->map is in a vertical line, a horizontal line, both, or
 297     neither.  Only the "both" case matters. */
 298   for (y = 0; y < sparrow->in.height; y++){
 299     for (x = 0; x < sparrow->in.width; x++){
 300       sparrow_intersect_t *p = &fl->map[y * sparrow->in.width + x];
 301       guint vsig = p->signal[SPARROW_VERTICAL];
 302       guint hsig = p->signal[SPARROW_HORIZONTAL];
 303       /*remembering that 0 is valid as a line number, but not as a signal */
 304       if (! (vsig && hsig)){
 305         continue;
 306       }
 307       /*This one is lobbying for the position of a corner.*/
 308       int vline = p->lines[SPARROW_VERTICAL];
 309       int hline = p->lines[SPARROW_HORIZONTAL];
 310
 311       sparrow_cluster_t *cluster = &clusters[hline * fl->n_vlines + vline];
 312       sparrow_voter_t *voters = cluster->voters;
 313       int n = cluster->n;
 314       guint signal = (vsig * hsig) / SIGNAL_QUANT;
 315       int xfp = x << SPARROW_FIXED_POINT;
 316       int yfp = y << SPARROW_FIXED_POINT;
 317
 318       GST_DEBUG("signal at %p (%d, %d): %dv %dh, product %u, lines: %dv %dh\n"
 319           "cluster is %p, n is %d\n", p, x, y,
 320           vsig, hsig, signal, vline, hline, cluster, n);
 321
 322       if (n < CLUSTER_SIZE){
 323         voters[n].x = xfp;
 324         voters[n].y = yfp;
 325         voters[n].signal = signal;
 326         cluster->n++;
 327       }
 328       else {
 329         for (int j = 0; j < CLUSTER_SIZE; j++){
 330           if (voters[j].signal < signal){
 331             guint tmp_s = voters[j].signal;
 332             int tmp_x = voters[j].x;
 333             int tmp_y = voters[j].y;
 334             voters[j].signal = signal;
 335             voters[j].x = xfp;
 336             voters[j].y = yfp;
 337             signal = tmp_s;
 338             xfp = tmp_x;
 339             yfp = tmp_y;
 340             GST_DEBUG("more than %d pixels at cluster for corner %d, %d.\n",
 341                 CLUSTER_SIZE, vline, hline);
 342           }
 343         }
 344       }
 345     }
 346   }
 347 }
 348
 349 /* look for connected group. if there is more than one connected group,
 350  despair.*/
 351
 352 static inline void
 353 discard_cluster_outliers(sparrow_cluster_t *cluster)
 354 {}
 355
 356
 357 static inline void
 358 x_discard_cluster_outliers(sparrow_cluster_t *cluster)
 359 {
 360   sparrow_voter_t *v = cluster->voters;
 361   int i, j;
 362
 363   guint32 touch[CLUSTER_SIZE];
 364
 365   while (cluster->n){
 366     guint32 all = (1 << cluster->n) - 1;
 367     for (i = 0; i < cluster->n; i++){
 368       touch[i] = 1 << i;
 369     }
 370
 371     for (i = 0; i <  cluster->n - 1; i++){
 372       for (j = i + 1; j < cluster->n; j++){
 373         if (((abs(v[i].x - v[j].x) <= 2) && (abs(v[i].y - v[j].y) <= 2)) ||
 374             (touch[i] & touch[j])){
 375           touch[i] |= touch[j];
 376           touch[j] = touch[i];
 377         }
 378       }
 379     }
 380     if (touch[cluster->n - 1] == all){
 381       break;
 382     }
 383     /* something is wrong! somebody is disconnected!  expel them!?
 384        backpropagate connectedness, find the maximum popcount, discard the
 385        others. */
 386     int bcount = 0;
 387     guint bmask = 0;
 388
 389     for (i = cluster->n - 1; i >= 0; i++){
 390       if (bmask != touch[i] &&
 391           bcount < (int)popcount32(touch[i])){
 392         bmask = touch[i];
 393         bcount = popcount32(touch[i]);
 394       }
 395       for (j = 0; j < i; j++){
 396         touch[j] = (touch[j] & touch[i]) ? touch[i] : touch[j];
 397       }
 398     }
 399     if (bcount > cluster->n / 2){
 400       j = 0;
 401       for (i = 0; i < cluster->n; i++){
 402         if (touch[i] == bmask){
 403           v[j] = v[i];
 404           j++;
 405         }
 406       }
 407       cluster->n = j;
 408     }
 409   }
 410 }
 411
 412
 413
 414 /*create the mesh */
 415 static inline void
 416 make_corners(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 417   //DEBUG_FIND_LINES(fl);
 418   int width = fl->n_vlines;
 419   int height = fl->n_hlines;
 420   sparrow_cluster_t *clusters = fl->clusters;
 421   sparrow_corner_t *mesh = fl->mesh;
 422   int x, y, i;
 423
 424   i = 0;
 425   for (y = 0; y < height; y++){
 426     for (x = 0; x < width; x++, i++){
 427       /* how to do this?
 428          1. centre of gravity (x,y, weighted average)
 429          2. discard outliers? look for connectedness? but if 2 are outliers?
 430       */
 431       sparrow_cluster_t *cluster = clusters + i;
 432       if (cluster->n == 0){
 433         continue;
 434       }
 435
 436       discard_cluster_outliers(cluster);
 437
 438       int xsum, ysum;
 439       int xmean, ymean;
 440       int votes;
 441       int j;
 442       xsum = 0;
 443       ysum = 0;
 444       votes = 0;
 445       for (j = 0; j < cluster->n; j++){
 446         votes += cluster->voters[j].signal;
 447         ysum += cluster->voters[j].y * cluster->voters[j].signal;
 448         xsum += cluster->voters[j].x * cluster->voters[j].signal;
 449       }
 450       if (votes){
 451         xmean = xsum / votes;
 452         ymean = ysum / votes;
 453       }
 454       else {
 455         GST_DEBUG("corner %d, %d voters, sum %d,%d, somehow has no votes\n",
 456             i, cluster->n, xsum, ysum);
 457       }
 458
 459       GST_DEBUG("corner %d: %d voters, %d votes, sum %d,%d, mean %d,%d\n",
 460           i, cluster->n, votes, xsum, ysum, xmean, ymean);
 461
 462       mesh[i].in_x = xmean;
 463       mesh[i].in_y = ymean;
 464       mesh[i].used = TRUE;
 465       GST_DEBUG("found corner %d at (%3f, %3f)\n",
 466           i, FLOATXY(xmean), FLOATXY(ymean));
 467     }
 468   }
 469 }
 470
 471 static inline void
 472 make_map(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 473   int i;
 474   int width = fl->n_vlines;
 475   int height = fl->n_hlines;
 476   sparrow_corner_t *mesh = fl->mesh;
 477   gint x, y;
 478
 479   //DEBUG_FIND_LINES(fl);
 480   /* calculate deltas toward adjacent corners */
 481   /* try to extrapolate left and up, if possible, so need to go backwards. */
 482   i = width * height - 1;
 483   for (y = height - 1; y >= 0; y--){
 484     for (x = width - 1; x >= 0; x--, i--){
 485       sparrow_corner_t *corner = &mesh[i];
 486       /* edge deltas will always come out as zero */
 487       sparrow_corner_t *right = (x >= width - 1) ? corner : corner + 1;
 488       sparrow_corner_t *down =  (y >= height - 1) ? corner : corner + width;
 489       GST_DEBUG("i %d xy %d,%d width %d. in_xy %d,%d; down in_xy %d,%d; right in_xy %d,%d\n",
 490           i, x, y, width, corner->in_x, corner->in_y, down->in_x,
 491           down->in_y, right->in_x,  right->in_y);
 492       if (corner->used){
 493         corner->dxr = (right->in_x - corner->in_x) / LINE_PERIOD;
 494         corner->dyr = (right->in_y - corner->in_y) / LINE_PERIOD;
 495         corner->dxd = (down->in_x -  corner->in_x) / LINE_PERIOD;
 496         corner->dyd = (down->in_y -  corner->in_y) / LINE_PERIOD;
 497       }
 498       else {
 499           /*prefer copy from left unless it is itself reconstructed (for no
 500             great reason), or it has no dx/dy because it is an edge piece.
 501             A mixed copy would be possible and better */
 502         sparrow_corner_t *rsrc = (right->used &&
 503                 (right->used <= down->used) &&
 504                 (right != corner)) ? right : down;
 505         sparrow_corner_t *dsrc = (down->used &&
 506                 (right->used >= down->used) &&
 507                 (down != corner)) ? down : right;
 508           corner->dxr = rsrc->dxr;
 509           corner->dyr = rsrc->dyr;
 510           corner->dxd = dsrc->dxd;
 511           corner->dyd = dsrc->dyd;
 512           /*now extrapolate position, preferably from both left and right */
 513           int cx = 0, cy = 0, cc = 0;
 514           if (right != corner){
 515             cc = 1;
 516             cx = right->in_x - corner->dxr * LINE_PERIOD;
 517             cy = right->in_y - corner->dyr * LINE_PERIOD;
 518           }
 519           if (down != corner){
 520             cx += down->in_x - corner->dxd * LINE_PERIOD;
 521             cy += down->in_y - corner->dyd * LINE_PERIOD;
 522             cx >>= cc;
 523             cy >>= cc;
 524           }
 525           /* if neither right nor down are there, this
 526              corner can't be placed */
 527           corner->in_x = cx;
 528           corner->in_y = cy;
 529           corner->used = MAX(right->used, down->used) + 1;
 530       }
 531     }
 532   }
 533   if (sparrow->debug){
 534     DEBUG_FIND_LINES(fl);
 535     debug_corners_image(sparrow, fl);
 536   }
 537 }
 538
 539
 540 /* With no line drawn (in our colour) look at the background noise.  Any real
 541    signal has to be stringer than this.
 542
 543    XXX looking for simple maximum -- maybe heap or histogram might be better,
 544    so as to be less susceptible to wierd outliers (e.g., bad pixels).  */
 545 static void
 546 look_for_threshold(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl){
 547   //DEBUG_FIND_LINES(fl);
 548   int i;
 549   guint32 colour;
 550   guint32 cmask = sparrow->out.colours[sparrow->colour];
 551   guint32 signal;
 552   guint32 *in32 = (guint32 *)in;
 553   guint32 highest = 0;
 554   for (i = 0;  i < (int)sparrow->in.pixcount; i++){
 555     colour = in32[i] & cmask;
 556     signal = ((colour >> fl->shift1) +
 557         (colour >> fl->shift2)) & 0x1ff;
 558     if (signal > highest){
 559       highest = signal;
 560     }
 561   }
 562   fl->threshold = highest + 1;
 563   GST_DEBUG("found maximum noise of %d, using threshold %d\n", highest, fl->threshold);
 564 }
 565
 566
 567 static void
 568 look_for_line(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl,
 569     sparrow_line_t *line){
 570   guint i;
 571   guint32 colour;
 572   guint32 cmask = sparrow->out.colours[sparrow->colour];
 573   int signal;
 574   guint32 *in32 = (guint32 *)in;
 575   for (i = 0; i < sparrow->in.pixcount; i++){
 576     colour = in32[i] & cmask;
 577     signal = ((colour >> fl->shift1) +
 578         (colour >> fl->shift2)) & 0x1ff;
 579     if (signal > fl->threshold){
 580       if (fl->map[i].lines[line->dir]){
 581         GST_DEBUG("HEY, expected point %d to be in line %d (dir %d)"
 582             "and thus empty, but it is also in line %d\n",
 583             i, line->index, line->dir, fl->map[i].lines[line->dir]);
 584       }
 585       fl->map[i].lines[line->dir] = line->index;
 586       fl->map[i].signal[line->dir] = signal;
 587     }
 588   }
 589 }
 590
 591 static void
 592 debug_map_image(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 593   guint32 *data = (guint32*)fl->debug->imageData;
 594   memset(data, 0, sparrow->in.size);
 595   for (guint i = 0; i < sparrow->in.pixcount; i++){
 596     data[i] |= (fl->map[i].signal[SPARROW_HORIZONTAL] >> 1) << sparrow->in.gshift;
 597     data[i] |= (fl->map[i].signal[SPARROW_VERTICAL] >> 1) << sparrow->in.rshift;
 598   }
 599   MAYBE_DEBUG_IPL(fl->debug);
 600 }
 601
 602 /* draw the line (in sparrow->colour) */
 603 static inline void
 604 draw_line(GstSparrow * sparrow, sparrow_line_t *line, guint8 *out){
 605   guint32 *p = (guint32 *)out;
 606   guint32 colour = sparrow->out.colours[sparrow->colour];
 607   int i;
 608   if (line->dir == SPARROW_HORIZONTAL){
 609     p += line->offset * sparrow->out.width;
 610     for (i = 0; i < sparrow->out.width; i++){
 611       p[i] = colour;
 612     }
 613   }
 614   else {
 615     guint32 *p = (guint32 *)out;
 616     p += line->offset;
 617     for(i = 0; i < sparrow->out.height; i++){
 618       *p = colour;
 619       p += sparrow->out.width;
 620     }
 621   }
 622 }
 623
 624
 625 /* show each line for 2 frames, then wait sparrow->lag frames, leaving line on
 626    until last one.
 627  */
 628 static inline void
 629 draw_lines(GstSparrow *sparrow, sparrow_find_lines_t *fl, guint8 *in, guint8 *out)
 630 {
 631   sparrow_line_t *line = fl->shuffled_lines[fl->current];
 632   sparrow->countdown--;
 633   memset(out, 0, sparrow->out.size);
 634   if (sparrow->countdown){
 635     /* show the line except on the first round, when we find a threshold*/
 636     if (fl->threshold){
 637       GST_DEBUG("current %d line %p\n", fl->current, line);
 638       draw_line(sparrow, line, out);
 639     }
 640   }
 641   else{
 642       /*show nothing, look for result */
 643     if (fl->threshold){
 644       look_for_line(sparrow, in, fl, line);
 645       fl->current++;
 646     }
 647     else {
 648       look_for_threshold(sparrow, in, fl);
 649     }
 650     sparrow->countdown = sparrow->lag + 2;
 651   }
 652   if (sparrow->debug){
 653     debug_map_image(sparrow, fl);
 654   }
 655 }
 656
 657 INVISIBLE sparrow_state
 658 mode_find_edges(GstSparrow *sparrow, guint8 *in, guint8 *out){
 659   sparrow_find_lines_t *fl = (sparrow_find_lines_t *)sparrow->helper_struct;
 660   //DEBUG_FIND_LINES(fl);
 661   if (fl->current < fl->n_lines){
 662     draw_lines(sparrow, fl, in, out);
 663     return SPARROW_STATUS_QUO;
 664   }
 665
 666   /*match up lines and find corners */
 667   switch(fl->counter){
 668   case 0:
 669     make_clusters(sparrow, fl);
 670     break;
 671   case 1:
 672     make_corners(sparrow, fl);
 673     break;
 674   case 2:
 675     make_map(sparrow, fl);
 676     break;
 677   case 3:
 678     corners_to_lut(sparrow, fl);
 679     return SPARROW_NEXT_STATE;
 680   }
 681   fl->counter++;
 682   return SPARROW_STATUS_QUO;
 683 }
 684
 685
 686 INVISIBLE void
 687 finalise_find_edges(GstSparrow *sparrow){
 688   sparrow_find_lines_t *fl = (sparrow_find_lines_t *)sparrow->helper_struct;
 689   //DEBUG_FIND_LINES(fl);
 690   if (sparrow->save && *(sparrow->save)){
 691     GST_DEBUG("about to save to %s\n", sparrow->save);
 692     dump_edges_info(sparrow, fl, sparrow->save);
 693   }
 694   if (sparrow->debug){
 695     cvReleaseImage(&fl->debug);
 696   }
 697   free(fl->h_lines);
 698   free(fl->shuffled_lines);
 699   free(fl->map);
 700   free(fl->mesh);
 701   free(fl->clusters);
 702   free(fl);
 703   sparrow->helper_struct = NULL;
 704 }
 705
 706
 707 static void
 708 setup_colour_shifts(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 709   switch (sparrow->colour){
 710   case SPARROW_WHITE:
 711   case SPARROW_GREEN:
 712     fl->shift1 = sparrow->in.gshift;
 713     fl->shift2 = sparrow->in.gshift;
 714     break;
 715   case SPARROW_MAGENTA:
 716     fl->shift1 = sparrow->in.rshift;
 717     fl->shift2 = sparrow->in.bshift;
 718     break;
 719   }
 720 }
 721
 722 INVISIBLE void
 723 init_find_edges(GstSparrow *sparrow){
 724   gint32 w = sparrow->out.width;
 725   gint32 h = sparrow->out.height;
 726   gint i;
 727   sparrow_find_lines_t *fl = zalloc_aligned_or_die(sizeof(sparrow_find_lines_t));
 728   sparrow->helper_struct = (void *)fl;
 729
 730   gint h_lines = (h + LINE_PERIOD - 1) / LINE_PERIOD;
 731   gint v_lines = (w + LINE_PERIOD - 1) / LINE_PERIOD;
 732   gint n_lines = (h_lines + v_lines);
 733   gint n_corners = (h_lines * v_lines);
 734   fl->n_hlines = h_lines;
 735   fl->n_vlines = v_lines;
 736   fl->n_lines = n_lines;
 737
 738   fl->h_lines = malloc_aligned_or_die(sizeof(sparrow_line_t) * n_lines);
 739   fl->shuffled_lines = malloc_aligned_or_die(sizeof(sparrow_line_t*) * n_lines);
 740   GST_DEBUG("shuffled lines, malloced %p\n", fl->shuffled_lines);
 741
 742   fl->map = zalloc_aligned_or_die(sizeof(sparrow_intersect_t) * sparrow->in.pixcount);
 743   fl->clusters = zalloc_or_die(n_corners * sizeof(sparrow_cluster_t));
 744   fl->mesh = zalloc_aligned_or_die(n_corners * sizeof(sparrow_corner_t));
 745
 746   sparrow_line_t *line = fl->h_lines;
 747   sparrow_line_t **sline = fl->shuffled_lines;
 748   int offset = LINE_PERIOD / 2;
 749
 750   for (i = 0, offset = LINE_PERIOD / 2; offset < h;
 751        i++, offset += LINE_PERIOD){
 752     line->offset = offset;
 753     line->dir = SPARROW_HORIZONTAL;
 754     line->index = i;
 755     *sline = line;
 756     line++;
 757     sline++;
 758   }
 759
 760   /*now add the vertical lines */
 761   fl->v_lines = line;
 762   for (i = 0, offset = LINE_PERIOD / 2; offset < w;
 763        i++, offset += LINE_PERIOD){
 764     line->offset = offset;
 765     line->dir = SPARROW_VERTICAL;
 766     line->index = i;
 767     *sline = line;
 768     line++;
 769     sline++;
 770   }
 771   //DEBUG_FIND_LINES(fl);
 772
 773   GST_DEBUG("allocated %d lines, used %d\n", n_lines, line - fl->h_lines);
 774
 775   /*now shuffle */
 776   for (i = 0; i < n_lines - 1; i++){
 777     int j = RANDINT(sparrow, 0, n_lines);
 778     sparrow_line_t *tmp = fl->shuffled_lines[j];
 779     fl->shuffled_lines[j] = fl->shuffled_lines[i];
 780     fl->shuffled_lines[i] = tmp;
 781   }
 782
 783   setup_colour_shifts(sparrow, fl);
 784
 785   if (sparrow->reload && *(sparrow->reload)){
 786     GST_DEBUG("sparrow>reload is %s\n", sparrow->reload);
 787     read_edges_info(sparrow, fl, sparrow->reload);
 788     fl->current = fl->n_lines;
 789     fl->counter = 0;
 790   }
 791   else {
 792     sparrow->countdown = sparrow->lag + 2;
 793   }
 794
 795   //DEBUG_FIND_LINES(fl);
 796   if (sparrow->debug){
 797     CvSize size = {sparrow->in.width, sparrow->in.height};
 798     fl->debug = cvCreateImage(size, IPL_DEPTH_8U, PIXSIZE);
 799   }
 800 }
 801