1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
8 //
9 //
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
15 //
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
18 //
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
21 //
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
25 //
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
28 //
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
39 //
40 //M*/
41
42 #include "_cvaux.h"
43
44 typedef struct Seg
45 {
46 ushort y;
47 ushort l;
48 ushort r;
49 ushort Prevl;
50 ushort Prevr;
51 short fl;
52 }
53 Seg;
54
55 #define UP 1
56 #define DOWN -1
57
58 #define PUSH(Y,IL,IR,IPL,IPR,FL) { stack[StIn].y=(ushort)(Y); \
59 stack[StIn].l=(ushort)(IL); \
60 stack[StIn].r=(ushort)(IR); \
61 stack[StIn].Prevl=(ushort)(IPL); \
62 stack[StIn].Prevr=(ushort)(IPR); \
63 stack[StIn].fl=(short)(FL); \
64 StIn++; }
65
66 #define POP(Y,IL,IR,IPL,IPR,FL) { StIn--; \
67 Y=stack[StIn].y; \
68 IL=stack[StIn].l; \
69 IR=stack[StIn].r;\
70 IPL=stack[StIn].Prevl; \
71 IPR=stack[StIn].Prevr; \
72 FL=stack[StIn].fl; }
73
74
75 #define DIFF(p1,p2) ((unsigned)((p1)[0] - (p2)[0] + d_lw)<=Interval && \
76 (unsigned)((p1)[1] - (p2)[1] + d_lw)<=Interval && \
77 (unsigned)((p1)[2] - (p2)[2] + d_lw)<=Interval)
78
79 /*#define DIFF(p1,p2) (CV_IABS((p1)[0] - (p2)[0]) + \
80 CV_IABS((p1)[1] - (p2)[1]) + \
81 CV_IABS((p1)[2] - (p2)[2]) <=Interval )*/
82
83 static CvStatus
icvSegmFloodFill_Stage1(uchar * pImage,int step,uchar * pMask,int maskStep,CvSize,CvPoint seed,int * newVal,int d_lw,int d_up,CvConnectedComp * region,void * pStack)84 icvSegmFloodFill_Stage1( uchar* pImage, int step,
85 uchar* pMask, int maskStep,
86 CvSize /*roi*/, CvPoint seed,
87 int* newVal, int d_lw, int d_up,
88 CvConnectedComp * region,
89 void *pStack )
90 {
91 uchar* img = pImage + step * seed.y;
92 uchar* mask = pMask + maskStep * (seed.y + 1);
93 unsigned Interval = (unsigned) (d_up + d_lw);
94 Seg *stack = (Seg*)pStack;
95 int StIn = 0;
96 int i, L, R;
97 int area = 0;
98 int sum[] = { 0, 0, 0 };
99 int XMin, XMax, YMin = seed.y, YMax = seed.y;
100 int val0[3];
101
102 L = R = seed.x;
103 img = pImage + seed.y*step;
104 mask = pMask + seed.y*maskStep;
105 mask[L] = 1;
106
107 val0[0] = img[seed.x*3];
108 val0[1] = img[seed.x*3 + 1];
109 val0[2] = img[seed.x*3 + 2];
110
111 while( DIFF( img + (R+1)*3, /*img + R*3*/val0 ) && !mask[R + 1] )
112 mask[++R] = 2;
113
114 while( DIFF( img + (L-1)*3, /*img + L*3*/val0 ) && !mask[L - 1] )
115 mask[--L] = 2;
116
117 XMax = R;
118 XMin = L;
119 PUSH( seed.y, L, R, R + 1, R, UP );
120
121 while( StIn )
122 {
123 int k, YC, PL, PR, flag/*, curstep*/;
124
125 POP( YC, L, R, PL, PR, flag );
126
127 int data[][3] = { {-flag, L, R}, {flag, L, PL-1}, {flag,PR+1,R}};
128
129 if( XMax < R )
130 XMax = R;
131
132 if( XMin > L )
133 XMin = L;
134
135 if( YMax < YC )
136 YMax = YC;
137
138 if( YMin > YC )
139 YMin = YC;
140
141 for( k = 0; k < 3; k++ )
142 {
143 flag = data[k][0];
144 /*curstep = flag * step;*/
145 img = pImage + (YC + flag) * step;
146 mask = pMask + (YC + flag) * maskStep;
147 int left = data[k][1];
148 int right = data[k][2];
149
150 for( i = left; i <= right; i++ )
151 {
152 if( !mask[i] && DIFF( img + i*3, /*img - curstep + i*3*/val0 ))
153 {
154 int j = i;
155 mask[i] = 2;
156 while( !mask[j - 1] && DIFF( img + (j - 1)*3, /*img + j*3*/val0 ))
157 mask[--j] = 2;
158
159 while( !mask[i + 1] &&
160 (DIFF( img + (i+1)*3, /*img + i*3*/val0 ) ||
161 (DIFF( img + (i+1)*3, /*img + (i+1)*3 - curstep*/val0) && i < R)))
162 mask[++i] = 2;
163
164 PUSH( YC + flag, j, i, L, R, -flag );
165 i++;
166 }
167 }
168 }
169
170 img = pImage + YC * step;
171
172 for( i = L; i <= R; i++ )
173 {
174 sum[0] += img[i*3];
175 sum[1] += img[i*3 + 1];
176 sum[2] += img[i*3 + 2];
177 }
178
179 area += R - L + 1;
180 }
181
182 region->area = area;
183 region->rect.x = XMin;
184 region->rect.y = YMin;
185 region->rect.width = XMax - XMin + 1;
186 region->rect.height = YMax - YMin + 1;
187 region->value = cvScalarAll(0);
188
189 {
190 double inv_area = area ? 1./area : 0;
191 newVal[0] = cvRound( sum[0] * inv_area );
192 newVal[1] = cvRound( sum[1] * inv_area );
193 newVal[2] = cvRound( sum[2] * inv_area );
194 }
195
196 return CV_NO_ERR;
197 }
198
199
200 #undef PUSH
201 #undef POP
202 #undef DIFF
203
204
205 static CvStatus
icvSegmFloodFill_Stage2(uchar * pImage,int step,uchar * pMask,int maskStep,CvSize,int * newVal,CvRect rect)206 icvSegmFloodFill_Stage2( uchar* pImage, int step,
207 uchar* pMask, int maskStep,
208 CvSize /*roi*/, int* newVal,
209 CvRect rect )
210 {
211 uchar* img = pImage + step * rect.y + rect.x * 3;
212 uchar* mask = pMask + maskStep * rect.y + rect.x;
213 uchar uv[] = { (uchar)newVal[0], (uchar)newVal[1], (uchar)newVal[2] };
214 int x, y;
215
216 for( y = 0; y < rect.height; y++, img += step, mask += maskStep )
217 for( x = 0; x < rect.width; x++ )
218 if( mask[x] == 2 )
219 {
220 mask[x] = 1;
221 img[x*3] = uv[0];
222 img[x*3+1] = uv[1];
223 img[x*3+2] = uv[2];
224 }
225
226 return CV_OK;
227 }
228
229 #if 0
230 static void color_derv( const CvArr* srcArr, CvArr* dstArr, int thresh )
231 {
232 static int tab[] = { 0, 2, 2, 1 };
233
234 uchar *src = 0, *dst = 0;
235 int dst_step, src_step;
236 int x, y;
237 CvSize size;
238
239 cvGetRawData( srcArr, (uchar**)&src, &src_step, &size );
240 cvGetRawData( dstArr, (uchar**)&dst, &dst_step, 0 );
241
242 memset( dst, 0, size.width*sizeof(dst[0]));
243 memset( (uchar*)dst + dst_step*(size.height-1), 0, size.width*sizeof(dst[0]));
244 src += 3;
245
246 #define CV_IABS(a) (((a) ^ ((a) < 0 ? -1 : 0)) - ((a) < 0 ? -1 : 0))
247
248 for( y = 1; y < size.height - 1; y++ )
249 {
250 src += src_step;
251 dst += dst_step;
252 uchar* src0 = src;
253
254 dst[0] = dst[size.width - 1] = 0;
255
256 for( x = 1; x < size.width - 1; x++, src += 3 )
257 {
258 /*int d[3];
259 int ad[3];
260 int f0, f1;
261 int val;*/
262 int m[3];
263 double val;
264 //double xx, yy;
265 int dh[3];
266 int dv[3];
267 dh[0] = src[0] - src[-3];
268 dv[0] = src[0] - src[-src_step];
269 dh[1] = src[1] - src[-2];
270 dv[1] = src[1] - src[1-src_step];
271 dh[2] = src[2] - src[-1];
272 dv[2] = src[2] - src[2-src_step];
273
274 m[0] = dh[0]*dh[0] + dh[1]*dh[1] + dh[2]*dh[2];
275 m[2] = dh[0]*dv[0] + dh[1]*dv[1] + dh[2]*dv[2];
276 m[1] = dv[0]*dv[0] + dv[1]*dv[1] + dh[2]*dh[2];
277
278 val = (m[0] + m[2]) +
279 sqrt(((double)((double)m[0] - m[2]))*(m[0] - m[2]) + (4.*m[1])*m[1]);
280
281 /*
282
283 xx = m[1];
284 yy = v - m[0];
285 v /= sqrt(xx*xx + yy*yy) + 1e-7;
286 xx *= v;
287 yy *= v;
288
289 dx[x] = (short)cvRound(xx);
290 dy[x] = (short)cvRound(yy);
291
292 //dx[x] = (short)cvRound(v);
293
294 //dx[x] = dy[x] = (short)v;
295 d[0] = src[0] - src[-3];
296 ad[0] = CV_IABS(d[0]);
297
298 d[1] = src[1] - src[-2];
299 ad[1] = CV_IABS(d[1]);
300
301 d[2] = src[2] - src[-1];
302 ad[2] = CV_IABS(d[2]);
303
304 f0 = ad[1] > ad[0];
305 f1 = ad[2] > ad[f0];
306
307 val = d[tab[f0*2 + f1]];
308
309 d[0] = src[0] - src[-src_step];
310 ad[0] = CV_IABS(d[0]);
311
312 d[1] = src[1] - src[1-src_step];
313 ad[1] = CV_IABS(d[1]);
314
315 d[2] = src[2] - src[2-src_step];
316 ad[2] = CV_IABS(d[2]);
317
318 f0 = ad[1] > ad[0];
319 f1 = ad[2] > ad[f0];
320
321 dst[x] = (uchar)(val + d[tab[f0*2 + f1]] > thresh ? 255 : 0);*/
322 dst[x] = (uchar)(val > thresh);
323 }
324
325 src = src0;
326 }
327
328 }
329 #endif
330
331 const CvPoint icvCodeDeltas[8] =
332 { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };
333
334 static CvSeq*
icvGetComponent(uchar * img,int step,CvRect rect,CvMemStorage * storage)335 icvGetComponent( uchar* img, int step, CvRect rect,
336 CvMemStorage* storage )
337 {
338 const char nbd = 4;
339 int deltas[16];
340 int x, y;
341 CvSeq* exterior = 0;
342 char* ptr;
343
344 /* initialize local state */
345 CV_INIT_3X3_DELTAS( deltas, step, 1 );
346 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
347
348 ptr = (char*)(img + step*rect.y);
349 rect.width += rect.x;
350 rect.height += rect.y;
351
352 for( y = rect.y; y < rect.height; y++, ptr += step )
353 {
354 int prev = ptr[rect.x - 1] & -2;
355
356 for( x = rect.x; x < rect.width; x++ )
357 {
358 int p = ptr[x] & -2;
359
360 //assert( exterior || ((p | prev) & -4) == 0 );
361
362 if( p != prev )
363 {
364 CvSeq *seq = 0;
365 int is_hole = 0;
366 CvSeqWriter writer;
367 char *i0, *i1, *i3, *i4 = 0;
368 int prev_s = -1, s, s_end;
369 CvPoint pt = { x, y };
370
371 if( !(prev == 0 && p == 2) ) /* if not external contour */
372 {
373 /* check hole */
374 if( p != 0 || prev < 1 )
375 {
376 prev = p;
377 continue;
378 }
379
380 is_hole = 1;
381 if( !exterior )
382 {
383 assert(0);
384 return 0;
385 }
386 }
387
388 cvStartWriteSeq( CV_SEQ_CONTOUR | (is_hole ? CV_SEQ_FLAG_HOLE : 0),
389 sizeof(CvContour), sizeof(CvPoint), storage, &writer );
390 s_end = s = is_hole ? 0 : 4;
391 i0 = ptr + x - is_hole;
392
393 do
394 {
395 s = (s - 1) & 7;
396 i1 = i0 + deltas[s];
397 if( (*i1 & -2) != 0 )
398 break;
399 }
400 while( s != s_end );
401
402 if( s == s_end ) /* single pixel domain */
403 {
404 *i0 = (char) (nbd | -128);
405 CV_WRITE_SEQ_ELEM( pt, writer );
406 }
407 else
408 {
409 i3 = i0;
410 prev_s = s ^ 4;
411
412 /* follow border */
413 for( ;; )
414 {
415 s_end = s;
416
417 for( ;; )
418 {
419 i4 = i3 + deltas[++s];
420 if( (*i4 & -2) != 0 )
421 break;
422 }
423 s &= 7;
424
425 /* check "right" bound */
426 if( (unsigned) (s - 1) < (unsigned) s_end )
427 {
428 *i3 = (char) (nbd | -128);
429 }
430 else if( *i3 > 0 )
431 {
432 *i3 = nbd;
433 }
434
435 if( s != prev_s )
436 {
437 CV_WRITE_SEQ_ELEM( pt, writer );
438 prev_s = s;
439 }
440
441 pt.x += icvCodeDeltas[s].x;
442 pt.y += icvCodeDeltas[s].y;
443
444 if( i4 == i0 && i3 == i1 )
445 break;
446
447 i3 = i4;
448 s = (s + 4) & 7;
449 } /* end of border following loop */
450 }
451
452 seq = cvEndWriteSeq( &writer );
453 cvContourBoundingRect( seq, 1 );
454
455 if( !is_hole )
456 exterior = seq;
457 else
458 {
459 seq->v_prev = exterior;
460 seq->h_next = exterior->v_next;
461 if( seq->h_next )
462 seq->h_next->h_prev = seq;
463 exterior->v_next = seq;
464 }
465
466 prev = ptr[x] & -2;
467 }
468 }
469 }
470
471 return exterior;
472 }
473
474
475
476 CV_IMPL CvSeq*
cvSegmentImage(const CvArr * srcarr,CvArr * dstarr,double canny_threshold,double ffill_threshold,CvMemStorage * storage)477 cvSegmentImage( const CvArr* srcarr, CvArr* dstarr,
478 double canny_threshold,
479 double ffill_threshold,
480 CvMemStorage* storage )
481 {
482 CvSeq* root = 0;
483 CvMat* gray = 0;
484 CvMat* canny = 0;
485 //CvMat* temp = 0;
486 void* stack = 0;
487
488 CV_FUNCNAME( "cvSegmentImage" );
489
490 __BEGIN__;
491
492 CvMat srcstub, *src;
493 CvMat dststub, *dst;
494 CvMat* mask;
495 CvSize size;
496 CvPoint pt;
497 int ffill_lw_up = cvRound( fabs(ffill_threshold) );
498 CvSeq* prev_seq = 0;
499
500 CV_CALL( src = cvGetMat( srcarr, &srcstub ));
501 CV_CALL( dst = cvGetMat( dstarr, &dststub ));
502
503 size = cvGetSize( src );
504
505 CV_CALL( gray = cvCreateMat( size.height, size.width, CV_8UC1 ));
506 CV_CALL( canny = cvCreateMat( size.height, size.width, CV_8UC1 ));
507 //CV_CALL( temp = cvCreateMat( size.height/2, size.width/2, CV_8UC3 ));
508
509 CV_CALL( stack = cvAlloc( size.width * size.height * sizeof(Seg)));
510
511 cvCvtColor( src, gray, CV_BGR2GRAY );
512 cvCanny( gray, canny, 0/*canny_threshold*0.4*/, canny_threshold, 3 );
513 cvThreshold( canny, canny, 1, 1, CV_THRESH_BINARY );
514 //cvZero( canny );
515 //color_derv( src, canny, canny_threshold );
516
517 //cvPyrDown( src, temp );
518 //cvPyrUp( temp, dst );
519
520 //src = dst;
521 mask = canny; // a new name for new role
522
523 // make a non-zero border.
524 cvRectangle( mask, cvPoint(0,0), cvPoint(size.width-1,size.height-1), cvScalarAll(1), 1 );
525
526 for( pt.y = 0; pt.y < size.height; pt.y++ )
527 {
528 for( pt.x = 0; pt.x < size.width; pt.x++ )
529 {
530 if( mask->data.ptr[mask->step*pt.y + pt.x] == 0 )
531 {
532 CvConnectedComp region;
533 int avgVal[3] = { 0, 0, 0 };
534
535 icvSegmFloodFill_Stage1( src->data.ptr, src->step,
536 mask->data.ptr, mask->step,
537 size, pt, avgVal,
538 ffill_lw_up, ffill_lw_up,
539 ®ion, stack );
540
541 /*avgVal[0] = (avgVal[0] + 15) & -32;
542 if( avgVal[0] > 255 )
543 avgVal[0] = 255;
544 avgVal[1] = (avgVal[1] + 15) & -32;
545 if( avgVal[1] > 255 )
546 avgVal[1] = 255;
547 avgVal[2] = (avgVal[2] + 15) & -32;
548 if( avgVal[2] > 255 )
549 avgVal[2] = 255;*/
550
551 if( storage )
552 {
553 CvSeq* tmpseq = icvGetComponent( mask->data.ptr, mask->step,
554 region.rect, storage );
555 if( tmpseq != 0 )
556 {
557 ((CvContour*)tmpseq)->color = avgVal[0] + (avgVal[1] << 8) + (avgVal[2] << 16);
558 tmpseq->h_prev = prev_seq;
559 if( prev_seq )
560 prev_seq->h_next = tmpseq;
561 else
562 root = tmpseq;
563 prev_seq = tmpseq;
564 }
565 }
566
567 icvSegmFloodFill_Stage2( dst->data.ptr, dst->step,
568 mask->data.ptr, mask->step,
569 size, avgVal,
570 region.rect );
571 }
572 }
573 }
574
575 __END__;
576
577 //cvReleaseMat( &temp );
578 cvReleaseMat( &gray );
579 cvReleaseMat( &canny );
580 cvFree( &stack );
581
582 return root;
583 }
584
585 /* End of file. */
586