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"
31 static void dump_edges_info(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, const char *filename
){
32 GST_DEBUG("about to save to %s\n", filename
);
33 FILE *f
= fopen(filename
, "w");
34 sparrow_fl_condensed_t condensed
;
35 condensed
.n_vlines
= fl
->n_vlines
;
36 condensed
.n_hlines
= fl
->n_hlines
;
38 /* simply write fl, map, clusters and mesh in sequence */
39 GST_DEBUG("fl is %p, file is %p\n", fl
, f
);
40 GST_DEBUG("fl: %d x %d\n", sizeof(sparrow_find_lines_t
), 1);
41 fwrite(&condensed
, sizeof(sparrow_fl_condensed_t
), 1, f
);
42 GST_DEBUG("fl->map %d x %d\n", sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
);
43 fwrite(fl
->map
, sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
, f
);
44 GST_DEBUG("fl->clusters %d x %d\n", sizeof(sparrow_cluster_t
), fl
->n_hlines
* fl
->n_vlines
);
45 fwrite(fl
->clusters
, sizeof(sparrow_cluster_t
), fl
->n_hlines
* fl
->n_vlines
, f
);
46 GST_DEBUG("fl->mesh %d x %d\n", sizeof(sparrow_corner_t
), fl
->n_hlines
* fl
->n_vlines
);
47 fwrite(fl
->mesh
, sizeof(sparrow_corner_t
), fl
->n_hlines
* fl
->n_vlines
, f
);
48 /*and write the mask too */
49 GST_DEBUG("sparrow->screenmask\n");
50 fwrite(sparrow
->screenmask
, 1, sparrow
->out
.pixcount
, f
);
54 static void read_edges_info(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, const char *filename
){
55 FILE *f
= fopen(filename
, "r");
56 sparrow_fl_condensed_t condensed
;
57 size_t read
= fread(&condensed
, sizeof(sparrow_fl_condensed_t
), 1, f
);
58 assert(condensed
.n_hlines
== fl
->n_hlines
);
59 assert(condensed
.n_vlines
== fl
->n_vlines
);
61 guint n_corners
= fl
->n_hlines
* fl
->n_vlines
;
62 read
+= fread(fl
->map
, sizeof(sparrow_intersect_t
), sparrow
->in
.pixcount
, f
);
63 read
+= fread(fl
->clusters
, sizeof(sparrow_cluster_t
), n_corners
, f
);
64 read
+= fread(fl
->mesh
, sizeof(sparrow_corner_t
), n_corners
, f
);
65 read
+= fread(sparrow
->screenmask
, 1, sparrow
->out
.pixcount
, f
);
72 debug_lut(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
75 #define OFFSET(x, y, w)((((y) * (w)) >> SPARROW_FIXED_POINT) + ((x) >> SPARROW_FIXED_POINT))
77 #define QUANTISE_DELTA(d)(((d) + LINE_PERIOD / 2) / LINE_PERIOD)
79 /*tolerate up to 1/8 of a pixel drift */
80 #define MAX_DRIFT (1 << (SPARROW_FIXED_POINT - 3))
83 static inline sparrow_map_path_t
*
84 possibly_new_point(sparrow_map_path_t
*p
, int dx
, int dy
){
85 if (dx
!= p
->dx
&& dy
!= p
->dy
){
94 static void corners_to_lut(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
95 //DEBUG_FIND_LINES(fl);
96 sparrow_map_t
*map
= &sparrow
->map
; /*rows in sparrow->out */
97 guint8
*mask
= sparrow
->screenmask
; /*mask in sparrow->in */
98 sparrow_corner_t
*mesh
= fl
->mesh
; /*maps regular points in ->out to points in ->in */
99 int mesh_w
= fl
->n_vlines
;
100 int mesh_h
= fl
->n_hlines
;
101 int in_w
= sparrow
->in
.width
;
102 int mcy
, mmy
, mcx
; /*Mesh Corner|Modulus X|Y*/
105 sparrow_corner_t
*mesh_row
= mesh
;
107 for (y
= 0; y
< H_LINE_OFFSET
; y
++){
108 map
->rows
[y
].start
= 0;
109 map
->rows
[y
].end
= 0;
110 map
->rows
[y
].points
= NULL
;
113 sparrow_map_row_t
*row
= map
->rows
+ H_LINE_OFFSET
;
114 row
->points
= map
->point_mem
;
115 sparrow_map_path_t
*p
= row
->points
;
117 for(mcy
= 0; mcy
< mesh_h
- 1; mcy
++){ /* for each mesh row */
118 for (mmy
= 0; mmy
< LINE_PERIOD
; mmy
++){ /* for each output line */
119 int ix
, iy
; /* input x, y at mesh points, interpolated vertically */
120 int rx
, ry
; /* running x, y; approximates ix, iy */
123 sparrow_corner_t
*mesh_square
= mesh_row
;
124 GST_DEBUG("row %p, y %d, row offset %d\n", row
, y
, row
- map
->rows
);
129 for(mcx
= 0; mcx
< mesh_w
- 1; mcx
++){
130 /*for each mesh block except the last, which has no dx,dy.
131 Thus the mesh blocks are referenced in LINE_PERIOD passes.*/
132 if (mesh_square
->status
== CORNER_UNUSED
){
137 /*lordy! continue with previous deltas*/
142 /* starting point for this row in this block. */
143 iy
= mesh_square
->in_y
+ mmy
* (mesh_square
->dyd
/ 1);
144 ix
= mesh_square
->in_x
+ mmy
* (mesh_square
->dxd
/ 1);
145 /*incremental delta going left to right in this block */
146 dy
= (mesh_square
->dyr
/ 1);
147 dx
= (mesh_square
->dxr
/ 1);
150 /*index of the last point in this block
151 NB: calculating from ix, iy, which may differ slightly from rx, ry*/
153 ix
+ (LINE_PERIOD
- 1) * dx
,
154 iy
+ (LINE_PERIOD
- 1) * dy
,
156 //GST_DEBUG("lasti is %d, ix %d, iy %d\n", lasti, ix, iy);
159 /*it doesn't turn on within this block (or it is of ignorably
164 /*it does turn on. so step through and find it. This happens once
169 for (j
= 0; j
< LINE_PERIOD
; j
++){
170 if (mask
[OFFSET(rx
, ry
, in_w
)]){
176 row
->start
= mcx
* LINE_PERIOD
+ j
;
179 p
= possibly_new_point(p
, dx
, dy
);
181 p
->n
= LINE_PERIOD
- j
;
187 /*maybe rx, ry are drifting badly, in which case, we need to recalculate dx, dy*/
188 if (abs(rx
- ix
) > MAX_DRIFT
||
189 abs(ry
- iy
) > MAX_DRIFT
){
190 int y
= mcy
* LINE_PERIOD
+ mmy
;
191 int x
= mcx
* LINE_PERIOD
;
192 GST_DEBUG("output point %d %d, rx, ry %d, %d have got %d, %d away from target %d, %d."
193 " dx, dy is %d, %d\n",
194 x
, y
, rx
, ry
, rx
- ix
, ry
- iy
, ix
, iy
, dx
, dy
);
195 sparrow_corner_t
*next
= mesh_square
+ 1;
196 if(next
->status
!= CORNER_UNUSED
){
197 int niy
= next
->in_y
+ mmy
* (next
->dyd
/ 1);
198 int nix
= next
->in_x
+ mmy
* (next
->dxd
/ 1);
199 dx
= QUANTISE_DELTA(nix
- ix
);
200 dy
= QUANTISE_DELTA(niy
- iy
);
201 GST_DEBUG("new dx, dy is %d, %d\n", dx
, dy
);
204 GST_DEBUG("next corner is UNUSED. dx, dy unchanged\n");
208 /*Probably dx/dy are different, so we need a new point */
209 p
= possibly_new_point(p
, dx
, dy
);
211 /*does it end it this one? */
214 for (j
= 0; j
< LINE_PERIOD
; j
++){
215 if (! mask
[OFFSET(rx
, ry
, in_w
)]){
222 row
->end
= mcx
* LINE_PERIOD
+ j
;
223 /*this row is done! */
227 rx
+= LINE_PERIOD
* dx
;
228 ry
+= LINE_PERIOD
* dy
;
236 /*blank lines for the last few */
237 for (y
= sparrow
->out
.height
- H_LINE_OFFSET
; y
< sparrow
->out
.height
; y
++){
238 map
->rows
[y
].start
= 0;
239 map
->rows
[y
].end
= 0;
240 map
->rows
[y
].points
= NULL
;
243 debug_lut(sparrow
, fl
);
247 corners_to_full_lut(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
248 DEBUG_FIND_LINES(fl
);
249 sparrow_corner_t
*mesh
= fl
->mesh
; /*maps regular points in ->out to points in ->in */
250 sparrow_map_lut_t
*map_lut
= sparrow
->map_lut
;
251 int mesh_w
= fl
->n_vlines
;
252 int mesh_h
= fl
->n_hlines
;
253 int mcy
, mmy
, mcx
, mmx
; /*Mesh Corner|Modulus X|Y*/
254 int y
= H_LINE_OFFSET
;
255 sparrow_corner_t
*mesh_row
= mesh
;
256 for(mcy
= 0; mcy
< mesh_h
; mcy
++){
257 for (mmy
= 0; mmy
< LINE_PERIOD
; mmy
++, y
++){
258 sparrow_corner_t
*mesh_square
= mesh_row
;
259 int i
= y
* sparrow
->out
.width
+ V_LINE_OFFSET
;
260 for(mcx
= 0; mcx
< mesh_w
; mcx
++){
261 int iy
= mesh_square
->in_y
+ mmy
* mesh_square
->dyd
;
262 int ix
= mesh_square
->in_x
+ mmy
* mesh_square
->dxd
;
263 for (mmx
= 0; mmx
< LINE_PERIOD
; mmx
++, i
++){
264 map_lut
[i
].x
= MAX(ix
>> SPARROW_FP_2_LUT
, 0);
265 map_lut
[i
].y
= MAX(iy
>> SPARROW_FP_2_LUT
, 0);
266 //GST_DEBUG("ix, iy %d, %d x, y %d, %d\n", ix, iy,
267 // map_lut[i].x, map_lut[i].y);
269 ix
+= mesh_square
->dxr
;
270 iy
+= mesh_square
->dyr
;
277 sparrow
->map_lut
= map_lut
;
280 #define INTXY(x)((x) / (1 << SPARROW_FIXED_POINT))
281 #define FLOATXY(x)(((double)(x)) / (1 << SPARROW_FIXED_POINT))
283 debug_corners_image(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
284 sparrow_corner_t
*mesh
= fl
->mesh
;
285 guint32
*data
= (guint32
*)fl
->debug
->imageData
;
286 guint w
= fl
->debug
->width
;
287 memset(data
, 0, sparrow
->in
.size
);
288 guint32 colours
[4] = {0xff0000ff, 0x00ff0000, 0x0000ff00, 0xcccccccc};
289 for (int i
= 0; i
< fl
->n_vlines
* fl
->n_hlines
; i
++){
290 sparrow_corner_t
*c
= &mesh
[i
];
293 GST_DEBUG("i %d status %d x: %f, y: %f dxr %f dyr %f dxd %f dyd %f\n"
294 "int x, y %d,%d (raw %d,%d) data %p\n",
295 i
, c
->status
, FLOATXY(x
), FLOATXY(y
),
296 FLOATXY(c
->dxr
), FLOATXY(c
->dyr
), FLOATXY(c
->dxd
), FLOATXY(c
->dyd
),
297 INTXY(x
), INTXY(y
), x
, y
, data
);
302 for (int j
= 1; j
< LINE_PERIOD
; j
+= 2){
307 data
[INTXY(tyr
) * w
+ INTXY(txr
)] = 0x000088;
308 data
[INTXY(tyd
) * w
+ INTXY(txd
)] = 0x663300;
310 data
[INTXY(y
) * w
+ INTXY(x
)] = colours
[c
->status
];
312 MAYBE_DEBUG_IPL(fl
->debug
);
317 debug_clusters(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
318 guint32
*data
= (guint32
*)fl
->debug
->imageData
;
319 memset(data
, 0, sparrow
->in
.size
);
320 int width
= fl
->n_vlines
;
321 int height
= fl
->n_hlines
;
322 sparrow_cluster_t
*clusters
= fl
->clusters
;
325 guint32 colours
[4] = {0xff0000ff, 0x0000ff00, 0x00ff0000,
327 for (i
= 0; i
< width
* height
; i
++){
328 colour
= colours
[i
% 5];
329 sparrow_voter_t
*v
= clusters
[i
].voters
;
330 for (j
= 0; j
< clusters
[i
].n
; j
++){
331 data
[v
[j
].y
* sparrow
->in
.width
+
332 v
[j
].x
] = (colour
* (v
[j
].signal
/ 2)) / 256;
335 MAYBE_DEBUG_IPL(fl
->debug
);
339 #define SIGNAL_QUANT 1
341 /*maximum number of pixels in a cluster */
342 #define CLUSTER_SIZE 8
347 make_clusters(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
348 sparrow_cluster_t
*clusters
= fl
->clusters
;
350 /*special case: spurious values collect up at 0,0 */
351 fl
->map
[0].signal
[SPARROW_VERTICAL
] = 0;
352 fl
->map
[0].signal
[SPARROW_HORIZONTAL
] = 0;
353 /*each point in fl->map is in a vertical line, a horizontal line, both, or
354 neither. Only the "both" case matters. */
355 for (y
= 0; y
< sparrow
->in
.height
; y
++){
356 for (x
= 0; x
< sparrow
->in
.width
; x
++){
357 sparrow_intersect_t
*p
= &fl
->map
[y
* sparrow
->in
.width
+ x
];
358 guint vsig
= p
->signal
[SPARROW_VERTICAL
];
359 guint hsig
= p
->signal
[SPARROW_HORIZONTAL
];
360 /*remembering that 0 is valid as a line number, but not as a signal */
361 if (! (vsig
&& hsig
)){
364 /*This one is lobbying for the position of a corner.*/
365 int vline
= p
->lines
[SPARROW_VERTICAL
];
366 int hline
= p
->lines
[SPARROW_HORIZONTAL
];
367 if (vline
== BAD_PIXEL
|| hline
== BAD_PIXEL
){
368 GST_DEBUG("ignoring bad pixel %d, %d\n", x
, y
);
371 sparrow_cluster_t
*cluster
= &clusters
[hline
* fl
->n_vlines
+ vline
];
372 sparrow_voter_t
*voters
= cluster
->voters
;
374 guint signal
= (vsig
* hsig
) / SIGNAL_QUANT
;
375 GST_DEBUG("signal at %p (%d, %d): %dv %dh, product %u, lines: %dv %dh\n"
376 "cluster is %p, n is %d\n", p
, x
, y
,
377 vsig
, hsig
, signal
, vline
, hline
, cluster
, n
);
379 GST_WARNING("signal at %p (%d, %d) is %d following quantisation!\n",
383 if (n
< CLUSTER_SIZE
){
386 voters
[n
].signal
= signal
;
390 /*duplicate x, y, signal, so they aren't mucked up */
394 /*replaced one ends up here */
398 for (int j
= 0; j
< CLUSTER_SIZE
; j
++){
399 if (voters
[j
].signal
< ts
){
400 ts2
= voters
[j
].signal
;
403 voters
[j
].signal
= ts
;
411 GST_DEBUG("more than %d pixels at cluster for corner %d, %d."
412 "Dropped %u for %u\n",
413 CLUSTER_SIZE
, vline
, hline
, ts2
, signal
);
418 debug_clusters(sparrow
, fl
);
424 drop_cluster_voter(sparrow_cluster_t
*cluster
, int n
)
427 for (int i
= n
; i
< cluster
->n
- 1; i
++){
428 cluster
->voters
[i
] = cluster
->voters
[i
+ 1];
434 static inline int sort_median(int *a
, guint n
)
437 /*stupid sort, but n is very small*/
438 for (i
= 0; i
< n
; i
++){
439 for (j
= i
+ 1; j
< n
; j
++){
447 guint middle
= n
/ 2;
448 int answer
= a
[middle
];
451 answer
+= a
[middle
- 1];
457 #define EUCLIDEAN_D2(ax, ay, bx, by)((ax - bx) * (ax - bx) + (ay - by) * (ay - by))
458 #define NEIGHBOURLY_THRESHOLD (LINE_PERIOD * 4)
461 neighbourly_discard_cluster_outliers(GstSparrow
*sparrow
, sparrow_cluster_t
*cluster
,
462 sparrow_corner_t
*neighbour
)
464 /* assuming the output mesh entirely fits in the input window (which is
465 required for sparrow to work) the neighbours should be at most
466 LINE_PERIOD * input resolution / output resolution apart. But set the
467 threshold higher, just in case. */
468 const int threshold
= NEIGHBOURLY_THRESHOLD
* sparrow
->in
.height
/ sparrow
->out
.height
;
470 int neighbour_d
[CLUSTER_SIZE
];
472 for (i
= 0; i
< cluster
->n
; i
++){
473 int d
= EUCLIDEAN_D2(neighbour
->in_x
, neighbour
->in_y
,
474 cluster
->voters
[i
].x
, cluster
->voters
[i
].y
);
475 int pass
= d
> threshold
;
476 neighbour_d
[i
] = pass
;
478 GST_DEBUG("failing point %d, distance sq %d, threshold %d\n", i
, d
, threshold
);
481 for (i
= 0; i
< cluster
->n
; i
++){
482 if (! neighbour_d
[i
]){
483 drop_cluster_voter(cluster
, i
);
490 median_discard_cluster_outliers(sparrow_cluster_t
*cluster
)
492 int xvals
[CLUSTER_SIZE
];
493 int yvals
[CLUSTER_SIZE
];
495 for (i
= 0; i
< cluster
->n
; i
++){
496 /*XXX could sort here*/
497 xvals
[i
] = cluster
->voters
[i
].x
;
498 yvals
[i
] = cluster
->voters
[i
].y
;
500 const int xmed
= sort_median(xvals
, cluster
->n
);
501 const int ymed
= sort_median(yvals
, cluster
->n
);
503 for (i
= 0; i
< cluster
->n
; i
++){
504 int dx
= cluster
->voters
[i
].x
- xmed
;
505 int dy
= cluster
->voters
[i
].y
- ymed
;
506 if (dx
* dx
+ dy
* dy
> OUTLIER_THRESHOLD
){
507 drop_cluster_voter(cluster
, i
);
514 make_corners(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
515 //DEBUG_FIND_LINES(fl);
516 int width
= fl
->n_vlines
;
517 int height
= fl
->n_hlines
;
518 sparrow_cluster_t
*clusters
= fl
->clusters
;
519 sparrow_corner_t
*mesh
= fl
->mesh
;
523 for (y
= 0; y
< height
; y
++){
524 for (x
= 0; x
< width
; x
++, i
++){
525 sparrow_cluster_t
*cluster
= clusters
+ i
;
526 if (cluster
->n
== 0){
530 /*the good points should all be adjacent; distant ones are spurious, so
533 This fails if all the cluster are way off. Obviously it would be good
534 to include information about the grid in the decision, but that is not
535 there yet. (needs iteration, really).
537 Here's a slight attempt:*/
539 sparrow_corner_t
*neighbour
;
541 neighbour
= &mesh
[i
- 1];
542 neighbourly_discard_cluster_outliers(sparrow
, cluster
, neighbour
);
545 neighbour
= &mesh
[i
- width
];
546 neighbourly_discard_cluster_outliers(sparrow
, cluster
, neighbour
);
549 median_discard_cluster_outliers(cluster
);
551 /* now find a weighted average position */
552 /*64 bit to avoid overflow -- should probably just use floating point
561 for (j
= 0; j
< cluster
->n
; j
++){
562 votes
+= cluster
->voters
[j
].signal
;
563 ysum
+= cluster
->voters
[j
].y
* cluster
->voters
[j
].signal
;
564 xsum
+= cluster
->voters
[j
].x
* cluster
->voters
[j
].signal
;
567 xmean
= (xsum
<< SPARROW_FIXED_POINT
) / votes
;
568 ymean
= (ysum
<< SPARROW_FIXED_POINT
) / votes
;
571 GST_WARNING("corner %d, %d voters, sum %d,%d, somehow has no votes\n",
572 i
, cluster
->n
, xsum
, ysum
);
575 GST_DEBUG("corner %d: %d voters, %d votes, sum %d,%d, mean %d,%d\n",
576 i
, cluster
->n
, votes
, xsum
, ysum
, xmean
, ymean
);
578 mesh
[i
].in_x
= xmean
;
579 mesh
[i
].in_y
= ymean
;
580 mesh
[i
].status
= CORNER_EXACT
;
581 GST_DEBUG("found corner %d at (%3f, %3f)\n",
582 i
, FLOATXY(xmean
), FLOATXY(ymean
));
589 make_map(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
591 int width
= fl
->n_vlines
;
592 int height
= fl
->n_hlines
;
593 sparrow_corner_t
*mesh
= fl
->mesh
;
596 //DEBUG_FIND_LINES(fl);
597 /* calculate deltas toward adjacent corners */
598 /* try to extrapolate left and up, if possible, so need to go backwards. */
599 i
= width
* height
- 1;
600 for (y
= height
- 1; y
>= 0; y
--){
601 for (x
= width
- 1; x
>= 0; x
--, i
--){
602 sparrow_corner_t
*corner
= &mesh
[i
];
603 /* calculate the delta to next corner. If this corner is on edge, delta is
604 0 and next is this.*/
605 sparrow_corner_t
*right
= (x
== width
- 1) ? corner
: corner
+ 1;
606 sparrow_corner_t
*down
= (y
== height
- 1) ? corner
: corner
+ width
;
607 GST_DEBUG("i %d xy %d,%d width %d. in_xy %d,%d; down in_xy %d,%d; right in_xy %d,%d\n",
608 i
, x
, y
, width
, corner
->in_x
, corner
->in_y
, down
->in_x
,
609 down
->in_y
, right
->in_x
, right
->in_y
);
610 if (corner
->status
!= CORNER_UNUSED
){
611 corner
->dxr
= (right
->in_x
- corner
->in_x
);
612 corner
->dyr
= (right
->in_y
- corner
->in_y
);
613 corner
->dxd
= (down
->in_x
- corner
->in_x
);
614 corner
->dyd
= (down
->in_y
- corner
->in_y
);
617 /*copy from both right and down, if they both exist. */
623 } dividends
= {0, 0, 0, 0};
629 if (right
!= corner
){
630 if (right
->dxr
|| right
->dyr
){
631 dividends
.dxr
+= right
->dxr
;
632 dividends
.dyr
+= right
->dyr
;
635 if (right
->dxd
|| right
->dyd
){
636 dividends
.dxd
+= right
->dxd
;
637 dividends
.dyd
+= right
->dyd
;
642 if (down
->dxr
|| down
->dyr
){
643 dividends
.dxr
+= down
->dxr
;
644 dividends
.dyr
+= down
->dyr
;
647 if (down
->dxd
|| down
->dyd
){
648 dividends
.dxd
+= down
->dxd
;
649 dividends
.dyd
+= down
->dyd
;
653 corner
->dxr
= divisors
.r
? dividends
.dxr
/ divisors
.r
: 0;
654 corner
->dyr
= divisors
.r
? dividends
.dyr
/ divisors
.r
: 0;
655 corner
->dxd
= divisors
.d
? dividends
.dxd
/ divisors
.d
: 0;
656 corner
->dyd
= divisors
.d
? dividends
.dyd
/ divisors
.d
: 0;
658 /*now extrapolate position, preferably from both left and right */
659 if (right
== corner
){
660 if (down
!= corner
){ /*use down only */
661 corner
->in_x
= down
->in_x
- corner
->dxd
;
662 corner
->in_y
= down
->in_y
- corner
->dyd
;
665 GST_DEBUG("can't reconstruct corner %d, %d: no useable neighbours\n", x
, y
);
666 /*it would be easy enough to look further, but hopefully of no
670 else if (down
== corner
){ /*use right only */
671 corner
->in_x
= right
->in_x
- corner
->dxr
;
672 corner
->in_y
= right
->in_y
- corner
->dyr
;
674 else { /* use both */
675 corner
->in_x
= right
->in_x
- corner
->dxr
;
676 corner
->in_y
= right
->in_y
- corner
->dyr
;
677 corner
->in_x
+= down
->in_x
- corner
->dxd
;
678 corner
->in_y
+= down
->in_y
- corner
->dyd
;
682 corner
->status
= CORNER_PROJECTED
;
686 /*now quantise delta values. It would be wrong to do it earlier, when they
687 are being used to calculate whole mesh jumps, but from now they are
688 primarily going to used for pixel (mesh / LINE_PERIOD) jumps. To do this in
689 corners_to_lut puts a whole lot of division in a tight loop.*/
690 for (i
= 0; i
< width
* height
; i
++){
691 sparrow_corner_t
*corner
= &mesh
[i
];
692 corner
->dxr
= QUANTISE_DELTA(corner
->dxr
);
693 corner
->dyr
= QUANTISE_DELTA(corner
->dyr
);
694 corner
->dxd
= QUANTISE_DELTA(corner
->dxd
);
695 corner
->dyd
= QUANTISE_DELTA(corner
->dyd
);
698 DEBUG_FIND_LINES(fl
);
699 debug_corners_image(sparrow
, fl
);
706 look_for_line(GstSparrow
*sparrow
, guint8
*in
, sparrow_find_lines_t
*fl
,
707 sparrow_line_t
*line
){
710 guint32 cmask
= sparrow
->out
.colours
[sparrow
->colour
];
713 /* subtract background noise */
714 fl
->input
->imageData
= (char *)in
;
715 cvSub(fl
->input
, fl
->threshold
, fl
->working
, NULL
);
716 guint32
*in32
= (guint32
*)fl
->working
->imageData
;
718 for (i
= 0; i
< sparrow
->in
.pixcount
; i
++){
719 colour
= in32
[i
] & cmask
;
720 signal
= (((colour
>> fl
->shift1
) +
721 (colour
>> fl
->shift2
))) & 0xff;
723 if (fl
->map
[i
].lines
[line
->dir
]){
724 /*assume the pixel is on for everyone and will just confuse
727 XXX maybe threshold, so if signal is hugely bigger in one, don't ban it.
729 GST_DEBUG("HEY, expected point %d to be in line %d (dir %d)"
730 "and thus empty, but it is also in line %d\n"
731 "old signal %d, new signal %d, marking as BAD\n",
732 i
, line
->index
, line
->dir
, fl
->map
[i
].lines
[line
->dir
],
733 fl
->map
[i
].signal
[line
->dir
], signal
);
734 fl
->map
[i
].lines
[line
->dir
] = BAD_PIXEL
;
735 fl
->map
[i
].signal
[line
->dir
] = 0;
738 fl
->map
[i
].lines
[line
->dir
] = line
->index
;
739 fl
->map
[i
].signal
[line
->dir
] = signal
;
746 debug_map_image(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
747 guint32
*data
= (guint32
*)fl
->debug
->imageData
;
748 memset(data
, 0, sparrow
->in
.size
);
749 for (guint i
= 0; i
< sparrow
->in
.pixcount
; i
++){
750 data
[i
] |= fl
->map
[i
].signal
[SPARROW_HORIZONTAL
] << sparrow
->in
.gshift
;
751 data
[i
] |= fl
->map
[i
].signal
[SPARROW_VERTICAL
] << sparrow
->in
.rshift
;
753 MAYBE_DEBUG_IPL(fl
->debug
);
756 /* draw the line (in sparrow->colour) */
758 draw_line(GstSparrow
* sparrow
, sparrow_line_t
*line
, guint8
*out
){
759 guint32
*p
= (guint32
*)out
;
760 guint32 colour
= sparrow
->out
.colours
[sparrow
->colour
];
762 if (line
->dir
== SPARROW_HORIZONTAL
){
763 p
+= line
->offset
* sparrow
->out
.width
;
764 for (i
= 0; i
< sparrow
->out
.width
; i
++){
769 guint32
*p
= (guint32
*)out
;
771 for(i
= 0; i
< sparrow
->out
.height
; i
++){
773 p
+= sparrow
->out
.width
;
779 jump_state(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, edges_state_t state
){
780 if (state
== EDGES_NEXT_STATE
){
787 case EDGES_FIND_NOISE
:
788 sparrow
->countdown
= MAX(sparrow
->lag
, 1) + 2;
790 case EDGES_FIND_LINES
:
791 sparrow
->countdown
= MAX(sparrow
->lag
, 1) + 2;
793 case EDGES_FIND_CORNERS
:
794 sparrow
->countdown
= 4;
796 GST_DEBUG("jumped to non-existent state %d\n", fl
->state
);
801 /* show each line for 2 frames, then wait sparrow->lag frames, leaving line on
805 draw_lines(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, guint8
*in
, guint8
*out
)
807 sparrow_line_t
*line
= fl
->shuffled_lines
[fl
->current
];
808 sparrow
->countdown
--;
809 memset(out
, 0, sparrow
->out
.size
);
810 if (sparrow
->countdown
){
811 draw_line(sparrow
, line
, out
);
814 /*show nothing, look for result */
815 look_for_line(sparrow
, in
, fl
, line
);
817 debug_map_image(sparrow
, fl
);
820 if (fl
->current
== fl
->n_lines
){
821 jump_state(sparrow
, fl
, EDGES_NEXT_STATE
);
824 sparrow
->countdown
= MAX(sparrow
->lag
, 1) + 2;
829 #define LINE_THRESHOLD 32
832 find_threshold(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
, guint8
*in
, guint8
*out
)
834 memset(out
, 0, sparrow
->out
.size
);
835 /*XXX should average/median over a range of frames */
836 if (sparrow
->countdown
== 0){
837 memcpy(fl
->threshold
->imageData
, in
, sparrow
->in
.size
);
838 /*add a constant, and smooth */
839 cvAddS(fl
->threshold
, cvScalarAll(LINE_THRESHOLD
), fl
->working
, NULL
);
840 cvSmooth(fl
->working
, fl
->threshold
, CV_GAUSSIAN
, 3, 0, 0, 0);
841 //cvSmooth(fl->working, fl->threshold, CV_MEDIAN, 3, 0, 0, 0);
842 jump_state(sparrow
, fl
, EDGES_NEXT_STATE
);
844 sparrow
->countdown
--;
847 /*match up lines and find corners */
849 find_corners(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
)
851 sparrow
->countdown
--;
852 switch(sparrow
->countdown
){
854 make_clusters(sparrow
, fl
);
857 make_corners(sparrow
, fl
);
860 make_map(sparrow
, fl
);
864 corners_to_full_lut(sparrow
, fl
);
866 corners_to_lut(sparrow
, fl
);
870 GST_DEBUG("how did sparrow->countdown get to be %d?", sparrow
->countdown
);
871 sparrow
->countdown
= 4;
873 return sparrow
->countdown
;
877 INVISIBLE sparrow_state
878 mode_find_edges(GstSparrow
*sparrow
, guint8
*in
, guint8
*out
){
879 sparrow_find_lines_t
*fl
= (sparrow_find_lines_t
*)sparrow
->helper_struct
;
881 case EDGES_FIND_NOISE
:
882 find_threshold(sparrow
, fl
, in
, out
);
884 case EDGES_FIND_LINES
:
885 draw_lines(sparrow
, fl
, in
, out
);
887 case EDGES_FIND_CORNERS
:
888 if (find_corners(sparrow
, fl
))
890 return SPARROW_NEXT_STATE
;
891 case EDGES_NEXT_STATE
:
892 break; /*shush gcc */
894 return SPARROW_STATUS_QUO
;
898 finalise_find_edges(GstSparrow
*sparrow
){
899 sparrow_find_lines_t
*fl
= (sparrow_find_lines_t
*)sparrow
->helper_struct
;
900 //DEBUG_FIND_LINES(fl);
901 if (sparrow
->save
&& *(sparrow
->save
)){
902 GST_DEBUG("about to save to %s\n", sparrow
->save
);
903 dump_edges_info(sparrow
, fl
, sparrow
->save
);
906 cvReleaseImage(&fl
->debug
);
909 free(fl
->shuffled_lines
);
913 cvReleaseImage(&fl
->threshold
);
914 cvReleaseImage(&fl
->working
);
915 cvReleaseImageHeader(&fl
->input
);
917 sparrow
->helper_struct
= NULL
;
920 /*reduce the signal a little bit more, avoiding overflow later */
921 #define COLOUR_QUANT 1
924 setup_colour_shifts(GstSparrow
*sparrow
, sparrow_find_lines_t
*fl
){
925 switch (sparrow
->colour
){
928 fl
->shift1
= sparrow
->in
.gshift
+ COLOUR_QUANT
;
929 fl
->shift2
= sparrow
->in
.gshift
+ COLOUR_QUANT
;
931 case SPARROW_MAGENTA
:
932 fl
->shift1
= sparrow
->in
.rshift
+ COLOUR_QUANT
;
933 fl
->shift2
= sparrow
->in
.bshift
+ COLOUR_QUANT
;
939 init_find_edges(GstSparrow
*sparrow
){
940 gint32 w
= sparrow
->out
.width
;
941 gint32 h
= sparrow
->out
.height
;
943 sparrow_find_lines_t
*fl
= zalloc_aligned_or_die(sizeof(sparrow_find_lines_t
));
944 sparrow
->helper_struct
= (void *)fl
;
946 gint h_lines
= (h
+ LINE_PERIOD
- 1) / LINE_PERIOD
;
947 gint v_lines
= (w
+ LINE_PERIOD
- 1) / LINE_PERIOD
;
948 gint n_lines
= (h_lines
+ v_lines
);
949 gint n_corners
= (h_lines
* v_lines
);
950 fl
->n_hlines
= h_lines
;
951 fl
->n_vlines
= v_lines
;
952 fl
->n_lines
= n_lines
;
954 fl
->h_lines
= malloc_aligned_or_die(sizeof(sparrow_line_t
) * n_lines
);
955 fl
->shuffled_lines
= malloc_aligned_or_die(sizeof(sparrow_line_t
*) * n_lines
);
956 GST_DEBUG("shuffled lines, malloced %p\n", fl
->shuffled_lines
);
958 fl
->map
= zalloc_aligned_or_die(sizeof(sparrow_intersect_t
) * sparrow
->in
.pixcount
);
959 fl
->clusters
= zalloc_or_die(n_corners
* sizeof(sparrow_cluster_t
));
960 fl
->mesh
= zalloc_aligned_or_die(n_corners
* sizeof(sparrow_corner_t
));
962 sparrow_line_t
*line
= fl
->h_lines
;
963 sparrow_line_t
**sline
= fl
->shuffled_lines
;
966 for (i
= 0, offset
= H_LINE_OFFSET
; offset
< h
;
967 i
++, offset
+= LINE_PERIOD
){
968 line
->offset
= offset
;
969 line
->dir
= SPARROW_HORIZONTAL
;
976 /*now add the vertical lines */
978 for (i
= 0, offset
= V_LINE_OFFSET
; offset
< w
;
979 i
++, offset
+= LINE_PERIOD
){
980 line
->offset
= offset
;
981 line
->dir
= SPARROW_VERTICAL
;
987 //DEBUG_FIND_LINES(fl);
989 GST_DEBUG("allocated %d lines, status %d\n", n_lines
, line
- fl
->h_lines
);
992 for (i
= 0; i
< n_lines
; i
++){
993 int j
= RANDINT(sparrow
, 0, n_lines
);
994 sparrow_line_t
*tmp
= fl
->shuffled_lines
[j
];
995 fl
->shuffled_lines
[j
] = fl
->shuffled_lines
[i
];
996 fl
->shuffled_lines
[i
] = tmp
;
999 setup_colour_shifts(sparrow
, fl
);
1001 if (sparrow
->reload
){
1002 if (access(sparrow
->reload
, R_OK
)){
1003 GST_DEBUG("sparrow>reload is '%s' and it is UNREADABLE\n", sparrow
->reload
);
1006 read_edges_info(sparrow
, fl
, sparrow
->reload
);
1007 memset(fl
->map
, 0, sizeof(sparrow_intersect_t
) * sparrow
->in
.pixcount
);
1008 //memset(fl->clusters, 0, n_corners * sizeof(sparrow_cluster_t));
1009 memset(fl
->mesh
, 0, n_corners
* sizeof(sparrow_corner_t
));
1010 jump_state(sparrow
, fl
, EDGES_FIND_CORNERS
);
1013 jump_state(sparrow
, fl
, EDGES_FIND_NOISE
);
1015 /* opencv images for threshold finding */
1016 CvSize size
= {sparrow
->in
.width
, sparrow
->in
.height
};
1017 fl
->working
= cvCreateImage(size
, IPL_DEPTH_8U
, PIXSIZE
);
1018 fl
->threshold
= cvCreateImage(size
, IPL_DEPTH_8U
, PIXSIZE
);
1020 /*input has no data allocated -- it uses latest frame*/
1021 fl
->input
= init_ipl_image(&sparrow
->in
, PIXSIZE
);
1023 //DEBUG_FIND_LINES(fl);
1024 if (sparrow
->debug
){
1025 fl
->debug
= cvCreateImage(size
, IPL_DEPTH_8U
, PIXSIZE
);