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 find_corners_make_clusters(GstSparrow *sparrow, guint8 *in, 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 find_corners_make_corners(GstSparrow *sparrow, guint8 *in, 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       xmean = xsum / votes;
 451       ymean = ysum / votes;
 452       GST_DEBUG("corner %d: %d voters, %d votes, sum %d,%d, mean %d,%d\n",
 453           i, cluster->n, votes, xsum, ysum, xmean, ymean);
 454
 455       mesh[i].in_x = xmean;
 456       mesh[i].in_y = ymean;
 457       mesh[i].used = TRUE;
 458       GST_DEBUG("found corner %d at (%3f, %3f)\n",
 459           i, FLOATXY(xmean), FLOATXY(ymean));
 460     }
 461   }
 462 }
 463
 464 static inline void
 465 find_corners_make_map(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl){
 466   int i;
 467   int width = fl->n_vlines;
 468   int height = fl->n_hlines;
 469   sparrow_corner_t *mesh = fl->mesh;
 470   gint x, y;
 471
 472   //DEBUG_FIND_LINES(fl);
 473   /* calculate deltas toward adjacent corners */
 474   /* try to extrapolate left and up, if possible, so need to go backwards. */
 475   i = width * height - 1;
 476   for (y = height - 1; y >= 0; y--){
 477     for (x = width - 1; x >= 0; x--, i--){
 478       sparrow_corner_t *corner = &mesh[i];
 479       /* edge deltas will always come out as zero */
 480       sparrow_corner_t *right = (x >= width - 1) ? corner : corner + 1;
 481       sparrow_corner_t *down =  (y >= height - 1) ? corner : corner + width;
 482       GST_DEBUG("i %d xy %d,%d width %d. in_xy %d,%d; down in_xy %d,%d; right in_xy %d,%d\n",
 483           i, x, y, width, corner->in_x, corner->in_y, down->in_x,
 484           down->in_y, right->in_x,  right->in_y);
 485       if (corner->used){
 486         corner->dxr = (right->in_x - corner->in_x) / LINE_PERIOD;
 487         corner->dyr = (right->in_y - corner->in_y) / LINE_PERIOD;
 488         corner->dxd = (down->in_x -  corner->in_x) / LINE_PERIOD;
 489         corner->dyd = (down->in_y -  corner->in_y) / LINE_PERIOD;
 490       }
 491       else {
 492           /*prefer copy from left unless it is itself reconstructed (for no
 493             great reason), or it has no dx/dy because it is an edge piece.
 494             A mixed copy would be possible and better */
 495         sparrow_corner_t *rsrc = (right->used &&
 496                 (right->used <= down->used) &&
 497                 (right != corner)) ? right : down;
 498         sparrow_corner_t *dsrc = (down->used &&
 499                 (right->used >= down->used) &&
 500                 (down != corner)) ? down : right;
 501           corner->dxr = rsrc->dxr;
 502           corner->dyr = rsrc->dyr;
 503           corner->dxd = dsrc->dxd;
 504           corner->dyd = dsrc->dyd;
 505           /*now extrapolate position, preferably from both left and right */
 506           int cx = 0, cy = 0, cc = 0;
 507           if (right != corner){
 508             cc = 1;
 509             cx = right->in_x - corner->dxr * LINE_PERIOD;
 510             cy = right->in_y - corner->dyr * LINE_PERIOD;
 511           }
 512           if (down != corner){
 513             cx += down->in_x - corner->dxd * LINE_PERIOD;
 514             cy += down->in_y - corner->dyd * LINE_PERIOD;
 515             cx >>= cc;
 516             cy >>= cc;
 517           }
 518           /* if neither right nor down are there, this
 519              corner can't be placed */
 520           corner->in_x = cx;
 521           corner->in_y = cy;
 522           corner->used = MAX(right->used, down->used) + 1;
 523       }
 524     }
 525   }
 526 }
 527
 528 static void
 529 find_corners(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl){
 530   find_corners_make_clusters(sparrow, in, fl);
 531   if (sparrow->debug){
 532     debug_clusters(sparrow, fl);
 533   }
 534   find_corners_make_corners(sparrow, in, fl);
 535   find_corners_make_map(sparrow, in, fl);
 536   if (sparrow->debug){
 537     DEBUG_FIND_LINES(fl);
 538     debug_corners_image(sparrow, fl);
 539   }
 540 }
 541
 542
 543 /* With no line drawn (in our colour) look at the background noise.  Any real
 544    signal has to be stringer than this.
 545
 546    XXX looking for simple maximum -- maybe heap or histogram might be better,
 547    so as to be less susceptible to wierd outliers (e.g., bad pixels).  */
 548 static void
 549 look_for_threshold(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl){
 550   //DEBUG_FIND_LINES(fl);
 551   int i;
 552   guint32 colour;
 553   guint32 cmask = sparrow->out.colours[sparrow->colour];
 554   guint32 signal;
 555   guint32 *in32 = (guint32 *)in;
 556   guint32 highest = 0;
 557   for (i = 0;  i < (int)sparrow->in.pixcount; i++){
 558     colour = in32[i] & cmask;
 559     signal = ((colour >> fl->shift1) +
 560         (colour >> fl->shift2)) & 0x1ff;
 561     if (signal > highest){
 562       highest = signal;
 563     }
 564   }
 565   fl->threshold = highest + 1;
 566   GST_DEBUG("found maximum noise of %d, using threshold %d\n", highest, fl->threshold);
 567 }
 568
 569
 570 static void
 571 look_for_line(GstSparrow *sparrow, guint8 *in, sparrow_find_lines_t *fl,
 572     sparrow_line_t *line){
 573   guint i;
 574   guint32 colour;
 575   guint32 cmask = sparrow->out.colours[sparrow->colour];
 576   int signal;
 577   guint32 *in32 = (guint32 *)in;
 578   for (i = 0; i < sparrow->in.pixcount; i++){
 579     colour = in32[i] & cmask;
 580     signal = ((colour >> fl->shift1) +
 581         (colour >> fl->shift2)) & 0x1ff;
 582     if (signal > fl->threshold){
 583       if (fl->map[i].lines[line->dir]){
 584         GST_DEBUG("HEY, expected point %d to be in line %d (dir %d)"
 585             "and thus empty, but it is also in line %d\n",
 586             i, line->index, line->dir, fl->map[i].lines[line->dir]);
 587       }
 588       fl->map[i].lines[line->dir] = line->index;
 589       fl->map[i].signal[line->dir] = signal;
 590     }
 591   }
 592 }
 593
 594 static void
 595 debug_map_image(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 596   guint32 *data = (guint32*)fl->debug->imageData;
 597   memset(data, 0, sparrow->in.size);
 598   for (guint i = 0; i < sparrow->in.pixcount; i++){
 599     data[i] |= fl->map[i].signal[SPARROW_HORIZONTAL] << sparrow->in.gshift;
 600     data[i] |= fl->map[i].signal[SPARROW_VERTICAL] << sparrow->in.rshift;
 601   }
 602   MAYBE_DEBUG_IPL(fl->debug);
 603 }
 604
 605 /* draw the line (in sparrow->colour) */
 606 static inline void
 607 draw_line(GstSparrow * sparrow, sparrow_line_t *line, guint8 *out){
 608   guint32 *p = (guint32 *)out;
 609   guint32 colour = sparrow->out.colours[sparrow->colour];
 610   int i;
 611   if (line->dir == SPARROW_HORIZONTAL){
 612     p += line->offset * sparrow->out.width;
 613     for (i = 0; i < sparrow->out.width; i++){
 614       p[i] = colour;
 615     }
 616   }
 617   else {
 618     guint32 *p = (guint32 *)out;
 619     p += line->offset;
 620     for(i = 0; i < sparrow->out.height; i++){
 621       *p = colour;
 622       p += sparrow->out.width;
 623     }
 624   }
 625 }
 626
 627
 628 /* show each line for 2 frames, then wait sparrow->lag frames, leaving line on
 629    until last one.
 630  */
 631
 632 INVISIBLE sparrow_state
 633 mode_find_edges(GstSparrow *sparrow, guint8 *in, guint8 *out){
 634   sparrow_find_lines_t *fl = (sparrow_find_lines_t *)sparrow->helper_struct;
 635   //DEBUG_FIND_LINES(fl);
 636   if (fl->current == fl->n_lines){
 637     goto done;
 638   }
 639   sparrow_line_t *line = fl->shuffled_lines[fl->current];
 640
 641   sparrow->countdown--;
 642   memset(out, 0, sparrow->out.size);
 643   if (sparrow->countdown){
 644     /* show the line except on the first round, when we find a threshold*/
 645     if (fl->threshold){
 646       GST_DEBUG("current %d line %p\n", fl->current, line);
 647       draw_line(sparrow, line, out);
 648     }
 649   }
 650   else{
 651       /*show nothing, look for result */
 652     if (fl->threshold){
 653       look_for_line(sparrow, in, fl, line);
 654       fl->current++;
 655     }
 656     else {
 657       look_for_threshold(sparrow, in, fl);
 658     }
 659     sparrow->countdown = sparrow->lag + 2;
 660   }
 661   if (sparrow->debug){
 662     debug_map_image(sparrow, fl);
 663   }
 664   return SPARROW_STATUS_QUO;
 665  done:
 666   /*match up lines and find corners */
 667   find_corners(sparrow, in, fl);
 668   corners_to_lut(sparrow, fl);
 669   return SPARROW_NEXT_STATE;
 670 }
 671
 672
 673 INVISIBLE void
 674 finalise_find_edges(GstSparrow *sparrow){
 675   sparrow_find_lines_t *fl = (sparrow_find_lines_t *)sparrow->helper_struct;
 676   //DEBUG_FIND_LINES(fl);
 677   if (sparrow->save && *(sparrow->save)){
 678     GST_DEBUG("about to save to %s\n", sparrow->save);
 679     dump_edges_info(sparrow, fl, sparrow->save);
 680   }
 681   if (sparrow->debug){
 682     cvReleaseImage(&fl->debug);
 683   }
 684   free(fl->h_lines);
 685   free(fl->shuffled_lines);
 686   free(fl->map);
 687   free(fl->mesh);
 688   free(fl->clusters);
 689   free(fl);
 690   sparrow->helper_struct = NULL;
 691 }
 692
 693
 694 static void
 695 setup_colour_shifts(GstSparrow *sparrow, sparrow_find_lines_t *fl){
 696   switch (sparrow->colour){
 697   case SPARROW_WHITE:
 698   case SPARROW_GREEN:
 699     fl->shift1 = sparrow->in.gshift;
 700     fl->shift2 = sparrow->in.gshift;
 701     break;
 702   case SPARROW_MAGENTA:
 703     fl->shift1 = sparrow->in.rshift;
 704     fl->shift2 = sparrow->in.bshift;
 705     break;
 706   }
 707 }
 708
 709 INVISIBLE void
 710 init_find_edges(GstSparrow *sparrow){
 711   gint32 w = sparrow->out.width;
 712   gint32 h = sparrow->out.height;
 713   gint i;
 714   sparrow_find_lines_t *fl = zalloc_aligned_or_die(sizeof(sparrow_find_lines_t));
 715   sparrow->helper_struct = (void *)fl;
 716
 717   gint h_lines = (h + LINE_PERIOD - 1) / LINE_PERIOD;
 718   gint v_lines = (w + LINE_PERIOD - 1) / LINE_PERIOD;
 719   gint n_lines = (h_lines + v_lines);
 720   gint n_corners = (h_lines * v_lines);
 721   fl->n_hlines = h_lines;
 722   fl->n_vlines = v_lines;
 723   fl->n_lines = n_lines;
 724
 725   fl->h_lines = malloc_aligned_or_die(sizeof(sparrow_line_t) * n_lines);
 726   fl->shuffled_lines = malloc_aligned_or_die(sizeof(sparrow_line_t*) * n_lines);
 727   GST_DEBUG("shuffled lines, malloced %p\n", fl->shuffled_lines);
 728
 729   fl->map = zalloc_aligned_or_die(sizeof(sparrow_intersect_t) * sparrow->in.pixcount);
 730   fl->clusters = zalloc_or_die(n_corners * sizeof(sparrow_cluster_t));
 731   fl->mesh = zalloc_aligned_or_die(n_corners * sizeof(sparrow_corner_t));
 732
 733   sparrow_line_t *line = fl->h_lines;
 734   sparrow_line_t **sline = fl->shuffled_lines;
 735   int offset = LINE_PERIOD / 2;
 736
 737   for (i = 0, offset = LINE_PERIOD / 2; offset < h;
 738        i++, offset += LINE_PERIOD){
 739     line->offset = offset;
 740     line->dir = SPARROW_HORIZONTAL;
 741     line->index = i;
 742     *sline = line;
 743     line++;
 744     sline++;
 745   }
 746
 747   /*now add the vertical lines */
 748   fl->v_lines = line;
 749   for (i = 0, offset = LINE_PERIOD / 2; offset < w;
 750        i++, offset += LINE_PERIOD){
 751     line->offset = offset;
 752     line->dir = SPARROW_VERTICAL;
 753     line->index = i;
 754     *sline = line;
 755     line++;
 756     sline++;
 757   }
 758   //DEBUG_FIND_LINES(fl);
 759
 760   GST_DEBUG("allocated %d lines, used %d\n", n_lines, line - fl->h_lines);
 761
 762   /*now shuffle */
 763   for (i = 0; i < n_lines - 1; i++){
 764     int j = RANDINT(sparrow, 0, n_lines);
 765     sparrow_line_t *tmp = fl->shuffled_lines[j];
 766     fl->shuffled_lines[j] = fl->shuffled_lines[i];
 767     fl->shuffled_lines[i] = tmp;
 768   }
 769
 770   setup_colour_shifts(sparrow, fl);
 771
 772   if (sparrow->reload && *(sparrow->reload)){
 773     read_edges_info(sparrow, fl, sparrow->reload);
 774     sparrow->countdown = 2;
 775   }
 776   else {
 777     sparrow->countdown = sparrow->lag + 2;
 778   }
 779
 780   //DEBUG_FIND_LINES(fl);
 781   if (sparrow->debug){
 782     CvSize size = {sparrow->in.width, sparrow->in.height};
 783     fl->debug = cvCreateImage(size, IPL_DEPTH_8U, PIXSIZE);
 784   }
 785 }
 786