1 /* Copyright (C) <2010> Douglas Bagnall <douglas@halo.gen.nz>
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.
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.
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.
21 #include "gstsparrow.h"
30 static int global_number_of_edge_finders
= 0;
32 static void dump_edges_info(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, const char *filename
){
33 GST_DEBUG("about to save to %s\n", filename
);
34 FILE *f
= fopen(filename
, "w");
35 sparrow_fl_condensed_t condensed
;
36 condensed
.n_vlines
= fl
->n_vlines
;
37 condensed
.n_hlines
= fl
->n_hlines
;
39 /* simply write fl, map, clusters and mesh in sequence */
40 GST_DEBUG("fl is %p, file is %p\n", fl
, f
);
41 GST_DEBUG("fl: %d x %d\n", sizeof(sparrow_find_lines_t
), 1);
42 fwrite(&condensed
, sizeof(sparrow_fl_condensed_t
), 1, f
);
43 GST_DEBUG("fl->map %d x %d\n", sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
);
44 fwrite(fl
->map
, sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
, f
);
45 GST_DEBUG("fl->clusters %d x %d\n", sizeof(sparrow_cluster_t
), fl
->n_hlines
* fl
->n_vlines
);
46 fwrite(fl
->clusters
, sizeof(sparrow_cluster_t
), fl
->n_hlines
* fl
->n_vlines
, f
);
47 GST_DEBUG("fl->mesh %d x %d\n", sizeof(sparrow_corner_t
), fl
->n_hlines
* fl
->n_vlines
);
48 fwrite(fl
->mesh
, sizeof(sparrow_corner_t
), fl
->n_hlines
* fl
->n_vlines
, f
);
49 /*and write the mask too */
50 GST_DEBUG("sparrow->screenmask\n");
51 fwrite(sparrow
->screenmask
, 1, sparrow
->in
.pixcount
, f
);
55 static void read_edges_info(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, const char *filename
){
56 FILE *f
= fopen(filename
, "r");
57 sparrow_fl_condensed_t condensed
;
58 size_t read
= fread(&condensed
, sizeof(sparrow_fl_condensed_t
), 1, f
);
59 assert(condensed
.n_hlines
== fl
->n_hlines
);
60 assert(condensed
.n_vlines
== fl
->n_vlines
);
62 guint n_corners
= fl
->n_hlines
* fl
->n_vlines
;
63 read
+= fread(fl
->map
, sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
, f
);
64 read
+= fread(fl
->clusters
, sizeof(sparrow_cluster_t
), n_corners
, f
);
65 read
+= fread(fl
->mesh
, sizeof(sparrow_corner_t
), n_corners
, f
);
66 read
+= fread(sparrow
->screenmask
, 1, sparrow
->in
.pixcount
, f
);
71 debug_map_lut(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
72 sparrow_map_lut_t
*map_lut
= sparrow
->map_lut
;
74 debug_frame(sparrow
, (guint8
*)map_lut
, sparrow
->out
.width
, sparrow
->out
.height
, PIXSIZE
);
80 corners_to_full_lut(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
82 sparrow_corner_t
*mesh
= fl
->mesh
; /*maps regular points in ->out to points in ->in */
83 sparrow_map_lut_t
*map_lut
= sparrow
->map_lut
;
84 int mesh_w
= fl
->n_vlines
;
85 int mesh_h
= fl
->n_hlines
;
86 int mcy
, mmy
, mcx
, mmx
; /*Mesh Corner|Modulus X|Y*/
87 int y
= H_LINE_OFFSET
;
88 sparrow_corner_t
*mesh_row
= mesh
;
89 int max_x
= sparrow
->in
.width
- 1;
90 int max_y
= sparrow
->in
.height
- 1;
92 for(mcy
= 0; mcy
< mesh_h
- 1; mcy
++){
93 for (mmy
= 0; mmy
< LINE_PERIOD
; mmy
++, y
++){
94 sparrow_corner_t
*mesh_square
= mesh_row
;
95 int i
= y
* sparrow
->out
.width
+ V_LINE_OFFSET
;
96 for(mcx
= 0; mcx
< mesh_w
- 1; mcx
++){
97 int iy
= mesh_square
->in_y
+ mmy
* mesh_square
->dyd
;
98 int ix
= mesh_square
->in_x
+ mmy
* mesh_square
->dxd
;
99 for (mmx
= 0; mmx
< LINE_PERIOD
; mmx
++, i
++){
100 int ixx
= CLAMP(ix
>> SPARROW_FIXED_POINT
, 0, max_x
);
101 int iyy
= CLAMP(iy
>> SPARROW_FIXED_POINT
, 0, max_y
);
102 if(sparrow
->screenmask
[iyy
* sparrow
->in
.width
+ ixx
]){
106 ix
+= mesh_square
->dxr
;
107 iy
+= mesh_square
->dyr
;
114 sparrow
->map_lut
= map_lut
;
115 debug_map_lut(sparrow
, fl
);
118 #define INTXY(x)((x) / (1 << SPARROW_FIXED_POINT))
119 #define FLOATXY(x)(((double)(x)) / (1 << SPARROW_FIXED_POINT))
122 clamp_intxy(int x
, const int max_plus_one
){
125 x
>>= SPARROW_FIXED_POINT
;
126 if (x
>= max_plus_one
)
127 return max_plus_one
- 1;
132 debug_corners_image(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
133 sparrow_corner_t
*mesh
= fl
->mesh
;
134 guint32
*data
= (guint32
*)fl
->debug
->imageData
;
135 guint w
= fl
->debug
->width
;
136 guint h
= fl
->debug
->height
;
137 memset(data
, 0, sparrow
->in
.size
);
138 guint32 colours
[4] = {0xff0000ff, 0x00ff0000, 0x0000ff00, 0xcccccccc};
139 for (int i
= 0; i
< fl
->n_vlines
* fl
->n_hlines
; i
++){
140 sparrow_corner_t
*c
= &mesh
[i
];
144 GST_DEBUG("i %d status %d x: %f, y: %f dxr %f dyr %f dxd %f dyd %f\n"
145 "int x, y %d,%d (raw %d,%d) data %p\n",
146 i, c->status, FLOATXY(x), FLOATXY(y),
147 FLOATXY(c->dxr), FLOATXY(c->dyr), FLOATXY(c->dxd), FLOATXY(c->dyd),
148 INTXY(x), INTXY(y), x, y, data);
154 for (int j
= 1; j
< LINE_PERIOD
; j
+= 2){
159 guint hl
= clamp_intxy(tyr
, h
) * w
+ clamp_intxy(txr
, w
);
160 if (hl
< sparrow
->in
.pixcount
){
161 data
[hl
] = 0x88000088;
164 GST_WARNING("overflow in debug_corners: hl %d, txr %d tyr %d",
167 guint vl
= clamp_intxy(tyd
, h
) * w
+ clamp_intxy(txd
, w
);
168 if (vl
< sparrow
->in
.pixcount
){
169 data
[vl
] = 0x00663300;
172 GST_WARNING("overflow in debug_corners: vl %d, txd %d tyd %d",
176 data
[clamp_intxy(y
, h
) * w
+ clamp_intxy(x
, w
)] = colours
[c
->status
];
178 MAYBE_DEBUG_IPL(fl
->debug
);
183 debug_clusters(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
184 guint32
*data
= (guint32
*)fl
->debug
->imageData
;
185 memset(data
, 0, sparrow
->in
.size
);
186 int width
= fl
->n_vlines
;
187 int height
= fl
->n_hlines
;
188 sparrow_cluster_t
*clusters
= fl
->clusters
;
191 guint32 colours
[4] = {0xff0000ff, 0x0000ff00, 0x00ff0000,
193 for (i
= 0; i
< width
* height
; i
++){
194 colour
= colours
[i
% 5];
195 sparrow_voter_t
*v
= clusters
[i
].voters
;
196 for (j
= 0; j
< clusters
[i
].n
; j
++){
197 data
[v
[j
].y
* sparrow
->in
.width
+
198 v
[j
].x
] = (colour
* (v
[j
].signal
/ 2)) / 256;
201 MAYBE_DEBUG_IPL(fl
->debug
);
205 #define SIGNAL_QUANT 1
207 /*maximum number of pixels in a cluster */
208 #define CLUSTER_SIZE 8
213 make_clusters(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
214 sparrow_cluster_t
*clusters
= fl
->clusters
;
216 /*special case: spurious values collect up at 0,0 */
217 fl
->map
[0].signal
[SPARROW_VERTICAL
] = 0;
218 fl
->map
[0].signal
[SPARROW_HORIZONTAL
] = 0;
219 /*each point in fl->map is in a vertical line, a horizontal line, both, or
220 neither. Only the "both" case matters. */
221 for (y
= 0; y
< sparrow
->in
.height
; y
++){
222 for (x
= 0; x
< sparrow
->in
.width
; x
++){
223 sparrow_intersect_t
*p
= &fl
->map
[y
* sparrow
->in
.width
+ x
];
224 guint vsig
= p
->signal
[SPARROW_VERTICAL
];
225 guint hsig
= p
->signal
[SPARROW_HORIZONTAL
];
226 /*remembering that 0 is valid as a line number, but not as a signal */
227 if (! (vsig
&& hsig
)){
230 /*This one is lobbying for the position of a corner.*/
231 int vline
= p
->lines
[SPARROW_VERTICAL
];
232 int hline
= p
->lines
[SPARROW_HORIZONTAL
];
233 if (vline
== BAD_PIXEL
|| hline
== BAD_PIXEL
){
234 GST_DEBUG("ignoring bad pixel %d, %d\n", x
, y
);
237 sparrow_cluster_t
*cluster
= &clusters
[hline
* fl
->n_vlines
+ vline
];
238 sparrow_voter_t
*voters
= cluster
->voters
;
240 guint signal
= (vsig
* hsig
) / SIGNAL_QUANT
;
241 GST_DEBUG("signal at %p (%d, %d): %dv %dh, product %u, lines: %dv %dh\n"
242 "cluster is %p, n is %d\n", p
, x
, y
,
243 vsig
, hsig
, signal
, vline
, hline
, cluster
, n
);
245 GST_WARNING("signal at %p (%d, %d) is %d following quantisation!\n",
249 if (n
< CLUSTER_SIZE
){
252 voters
[n
].signal
= signal
;
256 /*duplicate x, y, signal, so they aren't mucked up */
260 /*replaced one ends up here */
264 for (int j
= 0; j
< CLUSTER_SIZE
; j
++){
265 if (voters
[j
].signal
< ts
){
266 ts2
= voters
[j
].signal
;
269 voters
[j
].signal
= ts
;
277 GST_DEBUG("more than %d pixels at cluster for corner %d, %d."
278 "Dropped %u for %u\n",
279 CLUSTER_SIZE
, vline
, hline
, ts2
, signal
);
284 debug_clusters(sparrow
, fl
);
290 drop_cluster_voter(sparrow_cluster_t
*cluster
, int n
)
293 for (int i
= n
; i
< cluster
->n
- 1; i
++){
294 cluster
->voters
[i
] = cluster
->voters
[i
+ 1];
300 static inline int sort_median(int *a
, guint n
)
303 /*stupid sort, but n is very small*/
304 for (i
= 0; i
< n
; i
++){
305 for (j
= i
+ 1; j
< n
; j
++){
313 guint middle
= n
/ 2;
314 int answer
= a
[middle
];
317 answer
+= a
[middle
- 1];
323 #define EUCLIDEAN_D2(ax, ay, bx, by)((ax - bx) * (ax - bx) + (ay - by) * (ay - by))
324 #define EUCLIDEAN_THRESHOLD 9
327 euclidean_discard_cluster_outliers(sparrow_cluster_t
*cluster
)
329 /* Calculate distance between each pair. Discard points with maximum sum,
330 then recalculate until all are within threshold.
333 int dsums
[CLUSTER_SIZE
] = {0};
334 for (i
= 0; i
< cluster
->n
; i
++){
335 for (j
= i
+ 1; j
< cluster
->n
; i
++){
336 int d
= EUCLIDEAN_D2(cluster
->voters
[i
].x
, cluster
->voters
[i
].y
,
337 cluster
->voters
[j
].x
, cluster
->voters
[j
].y
);
343 int worst_d
, worst_i
, threshold
;
345 threshold
= EUCLIDEAN_THRESHOLD
* cluster
->n
;
348 for (i
= 0; i
< cluster
->n
; i
++){
349 if (dsums
[i
] > worst_d
){
354 if (worst_d
> threshold
){
355 GST_DEBUG("failing point %d, distance sq %d, threshold %d\n",
356 worst_i
, worst_d
, threshold
);
357 drop_cluster_voter(cluster
, worst_i
);
359 } while(worst_d
> threshold
&& cluster
->n
);
363 median_discard_cluster_outliers(sparrow_cluster_t
*cluster
)
365 int xvals
[CLUSTER_SIZE
];
366 int yvals
[CLUSTER_SIZE
];
368 for (i
= 0; i
< cluster
->n
; i
++){
369 /*XXX could sort here*/
370 xvals
[i
] = cluster
->voters
[i
].x
;
371 yvals
[i
] = cluster
->voters
[i
].y
;
373 const int xmed
= sort_median(xvals
, cluster
->n
);
374 const int ymed
= sort_median(yvals
, cluster
->n
);
376 for (i
= 0; i
< cluster
->n
; i
++){
377 int dx
= cluster
->voters
[i
].x
- xmed
;
378 int dy
= cluster
->voters
[i
].y
- ymed
;
379 if (dx
* dx
+ dy
* dy
> OUTLIER_THRESHOLD
){
380 drop_cluster_voter(cluster
, i
);
387 make_corners(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
388 //DEBUG_FIND_LINES(fl);
389 int width
= fl
->n_vlines
;
390 int height
= fl
->n_hlines
;
391 sparrow_cluster_t
*clusters
= fl
->clusters
;
392 sparrow_corner_t
*mesh
= fl
->mesh
;
396 for (y
= 0; y
< height
; y
++){
397 for (x
= 0; x
< width
; x
++, i
++){
398 sparrow_cluster_t
*cluster
= clusters
+ i
;
399 if (cluster
->n
== 0){
403 /*discard outliers based on sum of squared distances: good points should
404 be in a cluster, and have lowest sum*/
405 euclidean_discard_cluster_outliers(cluster
);
407 /*discard values away from median x, y values.
408 (each dimension is calculated independently)*/
409 median_discard_cluster_outliers(cluster
);
411 /* now find a weighted average position */
412 /*64 bit to avoid overflow -- should probably just use floating point
421 for (j
= 0; j
< cluster
->n
; j
++){
422 votes
+= cluster
->voters
[j
].signal
;
423 ysum
+= cluster
->voters
[j
].y
* cluster
->voters
[j
].signal
;
424 xsum
+= cluster
->voters
[j
].x
* cluster
->voters
[j
].signal
;
427 xmean
= (xsum
<< SPARROW_FIXED_POINT
) / votes
;
428 ymean
= (ysum
<< SPARROW_FIXED_POINT
) / votes
;
431 GST_WARNING("corner %d, %d voters, sum %d,%d, somehow has no votes\n",
432 i
, cluster
->n
, xsum
, ysum
);
435 GST_DEBUG("corner %d: %d voters, %d votes, sum %d,%d, mean %d,%d\n",
436 i
, cluster
->n
, votes
, xsum
, ysum
, xmean
, ymean
);
438 mesh
[i
].in_x
= xmean
;
439 mesh
[i
].in_y
= ymean
;
440 mesh
[i
].status
= CORNER_EXACT
;
441 GST_DEBUG("found corner %d at (%3f, %3f)\n",
442 i
, FLOATXY(xmean
), FLOATXY(ymean
));
449 make_map(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
451 int width
= fl
->n_vlines
;
452 int height
= fl
->n_hlines
;
453 sparrow_corner_t
*mesh
= fl
->mesh
;
456 DEBUG_FIND_LINES(fl
);
457 /* calculate deltas toward adjacent corners */
458 /* try to extrapolate left and up, if possible, so need to go backwards. */
459 i
= width
* height
- 1;
460 for (y
= height
- 1; y
>= 0; y
--){
461 for (x
= width
- 1; x
>= 0; x
--, i
--){
462 sparrow_corner_t
*corner
= &mesh
[i
];
463 /* calculate the delta to next corner. If this corner is on edge, delta is
464 0 and next is this.*/
465 sparrow_corner_t
*right
= (x
== width
- 1) ? corner
: corner
+ 1;
466 sparrow_corner_t
*down
= (y
== height
- 1) ? corner
: corner
+ width
;
467 GST_DEBUG("i %d xy %d,%d width %d. in_xy %d,%d; down in_xy %d,%d; right in_xy %d,%d\n",
468 i
, x
, y
, width
, corner
->in_x
, corner
->in_y
, down
->in_x
,
469 down
->in_y
, right
->in_x
, right
->in_y
);
470 if (corner
->status
!= CORNER_UNUSED
){
471 corner
->dxr
= (right
->in_x
- corner
->in_x
);
472 corner
->dyr
= (right
->in_y
- corner
->in_y
);
473 corner
->dxd
= (down
->in_x
- corner
->in_x
);
474 corner
->dyd
= (down
->in_y
- corner
->in_y
);
477 /*copy from both right and down, if they both exist. */
483 } dividends
= {0, 0, 0, 0};
489 if (right
!= corner
){
490 if (right
->dxr
|| right
->dyr
){
491 dividends
.dxr
+= right
->dxr
;
492 dividends
.dyr
+= right
->dyr
;
495 if (right
->dxd
|| right
->dyd
){
496 dividends
.dxd
+= right
->dxd
;
497 dividends
.dyd
+= right
->dyd
;
502 if (down
->dxr
|| down
->dyr
){
503 dividends
.dxr
+= down
->dxr
;
504 dividends
.dyr
+= down
->dyr
;
507 if (down
->dxd
|| down
->dyd
){
508 dividends
.dxd
+= down
->dxd
;
509 dividends
.dyd
+= down
->dyd
;
513 corner
->dxr
= divisors
.r
? dividends
.dxr
/ divisors
.r
: 0;
514 corner
->dyr
= divisors
.r
? dividends
.dyr
/ divisors
.r
: 0;
515 corner
->dxd
= divisors
.d
? dividends
.dxd
/ divisors
.d
: 0;
516 corner
->dyd
= divisors
.d
? dividends
.dyd
/ divisors
.d
: 0;
518 /*now extrapolate position, preferably from both left and right */
519 if (right
== corner
){
520 if (down
!= corner
){ /*use down only */
521 corner
->in_x
= down
->in_x
- corner
->dxd
;
522 corner
->in_y
= down
->in_y
- corner
->dyd
;
525 GST_DEBUG("can't reconstruct corner %d, %d: no useable neighbours\n", x
, y
);
526 /*it would be easy enough to look further, but hopefully of no
530 else if (down
== corner
){ /*use right only */
531 corner
->in_x
= right
->in_x
- corner
->dxr
;
532 corner
->in_y
= right
->in_y
- corner
->dyr
;
534 else { /* use both */
535 corner
->in_x
= right
->in_x
- corner
->dxr
;
536 corner
->in_y
= right
->in_y
- corner
->dyr
;
537 corner
->in_x
+= down
->in_x
- corner
->dxd
;
538 corner
->in_y
+= down
->in_y
- corner
->dyd
;
542 corner
->status
= CORNER_PROJECTED
;
546 /*now quantise delta values. It would be wrong to do it earlier, when they
547 are being used to calculate whole mesh jumps, but from now they are
548 primarily going to used for pixel (mesh / LINE_PERIOD) jumps. To do this in
549 corners_to_lut puts a whole lot of division in a tight loop.*/
550 for (i
= 0; i
< width
* height
; i
++){
551 sparrow_corner_t
*corner
= &mesh
[i
];
552 corner
->dxr
= QUANTISE_DELTA(corner
->dxr
);
553 corner
->dyr
= QUANTISE_DELTA(corner
->dyr
);
554 corner
->dxd
= QUANTISE_DELTA(corner
->dxd
);
555 corner
->dyd
= QUANTISE_DELTA(corner
->dyd
);
557 DEBUG_FIND_LINES(fl
);
559 debug_corners_image(sparrow
, fl
);
566 look_for_line(GstSparrow
*sparrow
, guint8
*in
, sparrow_find_lines_t
*fl
,
567 sparrow_line_t
*line
){
570 guint32 cmask
= sparrow
->out
.colours
[sparrow
->colour
];
573 /* subtract background noise */
574 fl
->input
->imageData
= (char *)in
;
575 cvSub(fl
->input
, fl
->threshold
, fl
->working
, NULL
);
576 guint32
*in32
= (guint32
*)fl
->working
->imageData
;
578 for (i
= 0; i
< sparrow
->in
.pixcount
; i
++){
579 colour
= in32
[i
] & cmask
;
580 signal
= (((colour
>> fl
->shift1
) & COLOUR_MASK
) +
581 ((colour
>> fl
->shift2
) & COLOUR_MASK
));
583 if (fl
->map
[i
].lines
[line
->dir
]){
584 /*assume the pixel is on for everyone and will just confuse
588 if (fl
->map
[i
].lines
[line
->dir
] != BAD_PIXEL
){
590 GST_DEBUG("HEY, expected point %d to be in line %d (dir %d) "
591 "and thus empty, but it is also in line %d\n"
592 "old signal %d, new signal %d, marking as BAD\n",
593 i, line->index, line->dir, fl->map[i].lines[line->dir],
594 fl->map[i].signal[line->dir], signal);
596 fl
->map
[i
].lines
[line
->dir
] = BAD_PIXEL
;
597 fl
->map
[i
].signal
[line
->dir
] = 0;
601 fl
->map
[i
].lines
[line
->dir
] = line
->index
;
602 fl
->map
[i
].signal
[line
->dir
] = signal
;
609 debug_map_image(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
610 guint32
*data
= (guint32
*)fl
->debug
->imageData
;
611 memset(data
, 0, sparrow
->in
.size
);
612 for (guint i
= 0; i
< sparrow
->in
.pixcount
; i
++){
613 data
[i
] |= fl
->map
[i
].signal
[SPARROW_HORIZONTAL
] << sparrow
->in
.gshift
;
614 data
[i
] |= fl
->map
[i
].signal
[SPARROW_VERTICAL
] << sparrow
->in
.rshift
;
615 data
[i
] |= ((fl
->map
[i
].lines
[SPARROW_VERTICAL
] == BAD_PIXEL
) ||
616 (fl
->map
[i
].lines
[SPARROW_HORIZONTAL
] == BAD_PIXEL
)) ? 255 << sparrow
->in
.bshift
: 0;
618 MAYBE_DEBUG_IPL(fl
->debug
);
621 /* draw the line (in sparrow->colour) */
623 draw_line(GstSparrow
* sparrow
, sparrow_line_t
*line
, guint8
*out
){
624 guint32
*p
= (guint32
*)out
;
625 guint32 colour
= sparrow
->out
.colours
[sparrow
->colour
];
627 if (line
->dir
== SPARROW_HORIZONTAL
){
628 p
+= line
->offset
* sparrow
->out
.width
;
629 for (i
= 0; i
< sparrow
->out
.width
; i
++){
634 guint32
*p
= (guint32
*)out
;
636 for(i
= 0; i
< sparrow
->out
.height
; i
++){
638 p
+= sparrow
->out
.width
;
644 jump_state(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, edges_state_t state
){
645 if (state
== EDGES_NEXT_STATE
){
652 case EDGES_FIND_NOISE
:
653 sparrow
->countdown
= MAX(sparrow
->lag
, 1) + SAFETY_LAG
;
655 case EDGES_FIND_LINES
:
656 sparrow
->countdown
= MAX(sparrow
->lag
, 1) + SAFETY_LAG
;
658 case EDGES_FIND_CORNERS
:
659 sparrow
->countdown
= 4;
661 case EDGES_WAIT_FOR_PLAY
:
662 global_number_of_edge_finders
--;
663 sparrow
->countdown
= 300;
666 GST_DEBUG("jumped to non-existent state %d\n", fl
->state
);
671 /* show each line for 2 frames, then wait sparrow->lag frames, leaving line on
675 draw_lines(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, guint8
*in
, guint8
*out
)
677 sparrow_line_t
*line
= fl
->shuffled_lines
[fl
->current
];
678 sparrow
->countdown
--;
679 memset(out
, 0, sparrow
->out
.size
);
680 if (sparrow
->countdown
){
681 draw_line(sparrow
, line
, out
);
684 /*show nothing, look for result */
685 look_for_line(sparrow
, in
, fl
, line
);
687 debug_map_image(sparrow
, fl
);
690 if (fl
->current
== fl
->n_lines
){
691 jump_state(sparrow
, fl
, EDGES_NEXT_STATE
);
694 sparrow
->countdown
= MAX(sparrow
->lag
, 1) + SAFETY_LAG
;
699 #define LINE_THRESHOLD 32
702 find_threshold(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, guint8
*in
, guint8
*out
)
704 memset(out
, 0, sparrow
->out
.size
);
705 /*XXX should average/median over a range of frames */
706 if (sparrow
->countdown
== 0){
707 memcpy(fl
->threshold
->imageData
, in
, sparrow
->in
.size
);
708 /*add a constant, and smooth */
709 cvAddS(fl
->threshold
, cvScalarAll(LINE_THRESHOLD
), fl
->working
, NULL
);
710 cvSmooth(fl
->working
, fl
->threshold
, CV_GAUSSIAN
, 3, 0, 0, 0);
711 //cvSmooth(fl->working, fl->threshold, CV_MEDIAN, 3, 0, 0, 0);
712 jump_state(sparrow
, fl
, EDGES_NEXT_STATE
);
714 sparrow
->countdown
--;
717 /*match up lines and find corners */
719 find_corners(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
)
721 sparrow
->countdown
--;
722 switch(sparrow
->countdown
){
724 make_clusters(sparrow
, fl
);
727 make_corners(sparrow
, fl
);
730 make_map(sparrow
, fl
);
734 corners_to_full_lut(sparrow
, fl
);
736 corners_to_lut(sparrow
, fl
);
738 jump_state(sparrow
, fl
, EDGES_NEXT_STATE
);
741 GST_DEBUG("how did sparrow->countdown get to be %d?", sparrow
->countdown
);
742 sparrow
->countdown
= 4;
744 return sparrow
->countdown
;
747 /*use a dirty shared variable*/
749 wait_for_play(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
750 if (global_number_of_edge_finders
== 0 ||
751 sparrow
->countdown
== 0){
754 sparrow
->countdown
--;
758 INVISIBLE sparrow_state
759 mode_find_edges(GstSparrow
*sparrow
, guint8
*in
, guint8
*out
){
760 sparrow_find_lines_t
*fl
= (sparrow_find_lines_t
*)sparrow
->helper_struct
;
762 case EDGES_FIND_NOISE
:
763 find_threshold(sparrow
, fl
, in
, out
);
765 case EDGES_FIND_LINES
:
766 draw_lines(sparrow
, fl
, in
, out
);
768 case EDGES_FIND_CORNERS
:
769 memset(out
, 0, sparrow
->out
.size
);
770 find_corners(sparrow
, fl
);
772 case EDGES_WAIT_FOR_PLAY
:
773 memset(out
, 0, sparrow
->out
.size
);
774 if (wait_for_play(sparrow
, fl
)){
775 return SPARROW_NEXT_STATE
;
778 case EDGES_NEXT_STATE
:
779 break; /*shush gcc */
781 return SPARROW_STATUS_QUO
;
785 finalise_find_edges(GstSparrow
*sparrow
){
786 sparrow_find_lines_t
*fl
= (sparrow_find_lines_t
*)sparrow
->helper_struct
;
787 //DEBUG_FIND_LINES(fl);
788 if (sparrow
->save
&& *(sparrow
->save
)){
789 GST_DEBUG("about to save to %s\n", sparrow
->save
);
790 dump_edges_info(sparrow
, fl
, sparrow
->save
);
793 cvReleaseImage(&fl
->debug
);
796 free(fl
->shuffled_lines
);
800 cvReleaseImage(&fl
->threshold
);
801 cvReleaseImage(&fl
->working
);
802 cvReleaseImageHeader(&fl
->input
);
804 GST_DEBUG("freed everything\n");
805 sparrow
->helper_struct
= NULL
;
809 setup_colour_shifts(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
810 /*COLOUR_QUANT reduces the signal a little bit more, avoiding overflow
812 switch (sparrow
->colour
){
815 fl
->shift1
= sparrow
->in
.gshift
+ COLOUR_QUANT
;
816 fl
->shift2
= sparrow
->in
.gshift
+ COLOUR_QUANT
;
818 case SPARROW_MAGENTA
:
819 fl
->shift1
= sparrow
->in
.rshift
+ COLOUR_QUANT
;
820 fl
->shift2
= sparrow
->in
.bshift
+ COLOUR_QUANT
;
826 init_find_edges(GstSparrow
*sparrow
){
828 sparrow_find_lines_t
*fl
= zalloc_aligned_or_die(sizeof(sparrow_find_lines_t
));
829 sparrow
->helper_struct
= (void *)fl
;
831 gint h_lines
= (sparrow
->out
.height
+ LINE_PERIOD
- 1) / LINE_PERIOD
;
832 gint v_lines
= (sparrow
->out
.width
+ LINE_PERIOD
- 1) / LINE_PERIOD
;
833 gint n_lines_max
= (h_lines
+ v_lines
);
834 gint n_corners
= (h_lines
* v_lines
);
835 fl
->n_hlines
= h_lines
;
836 fl
->n_vlines
= v_lines
;
838 fl
->h_lines
= malloc_aligned_or_die(sizeof(sparrow_line_t
) * n_lines_max
);
839 fl
->shuffled_lines
= malloc_aligned_or_die(sizeof(sparrow_line_t
*) * n_lines_max
);
840 GST_DEBUG("shuffled lines, malloced %p\n", fl
->shuffled_lines
);
842 GST_DEBUG("map is going to be %d * %d \n", sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
);
843 fl
->map
= zalloc_aligned_or_die(sizeof(sparrow_intersect_t
) * sparrow
->in
.pixcount
);
844 fl
->clusters
= zalloc_or_die(n_corners
* sizeof(sparrow_cluster_t
));
845 fl
->mesh
= zalloc_aligned_or_die(n_corners
* sizeof(sparrow_corner_t
));
847 sparrow_line_t
*line
= fl
->h_lines
;
848 sparrow_line_t
**sline
= fl
->shuffled_lines
;
851 for (i
= 0, offset
= H_LINE_OFFSET
; offset
< sparrow
->out
.height
;
852 i
++, offset
+= LINE_PERIOD
){
853 line
->offset
= offset
;
854 line
->dir
= SPARROW_HORIZONTAL
;
859 //GST_DEBUG("line %d h has offset %d\n", i, offset);
862 /*now add the vertical lines */
864 for (i
= 0, offset
= V_LINE_OFFSET
; offset
< sparrow
->out
.width
;
865 i
++, offset
+= LINE_PERIOD
){
866 line
->offset
= offset
;
867 line
->dir
= SPARROW_VERTICAL
;
872 //GST_DEBUG("line %d v has offset %d\n", i, offset);
874 //DEBUG_FIND_LINES(fl);
875 fl
->n_lines
= line
- fl
->h_lines
;
876 GST_DEBUG("allocated %d lines, made %d\n", n_lines_max
, fl
->n_lines
);
879 for (i
= 0; i
< fl
->n_lines
; i
++){
880 int j
= RANDINT(sparrow
, 0, fl
->n_lines
);
881 sparrow_line_t
*tmp
= fl
->shuffled_lines
[j
];
882 fl
->shuffled_lines
[j
] = fl
->shuffled_lines
[i
];
883 fl
->shuffled_lines
[i
] = tmp
;
886 setup_colour_shifts(sparrow
, fl
);
888 if (sparrow
->reload
){
889 if (access(sparrow
->reload
, R_OK
)){
890 GST_DEBUG("sparrow>reload is '%s' and it is UNREADABLE\n", sparrow
->reload
);
893 read_edges_info(sparrow
, fl
, sparrow
->reload
);
894 memset(fl
->map
, 0, sizeof(sparrow_intersect_t
) * sparrow
->in
.pixcount
);
895 //memset(fl->clusters, 0, n_corners * sizeof(sparrow_cluster_t));
896 memset(fl
->mesh
, 0, n_corners
* sizeof(sparrow_corner_t
));
897 jump_state(sparrow
, fl
, EDGES_FIND_CORNERS
);
900 jump_state(sparrow
, fl
, EDGES_FIND_NOISE
);
902 /* opencv images for threshold finding */
903 CvSize size
= {sparrow
->in
.width
, sparrow
->in
.height
};
904 fl
->working
= cvCreateImage(size
, IPL_DEPTH_8U
, PIXSIZE
);
905 fl
->threshold
= cvCreateImage(size
, IPL_DEPTH_8U
, PIXSIZE
);
907 /*input has no data allocated -- it uses latest frame*/
908 fl
->input
= init_ipl_image(&sparrow
->in
, PIXSIZE
);
910 //DEBUG_FIND_LINES(fl);
912 fl
->debug
= cvCreateImage(size
, IPL_DEPTH_8U
, PIXSIZE
);
915 global_number_of_edge_finders
++;