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 44typedef struct Seg 45{ 46 ushort y; 47 ushort l; 48 ushort r; 49 ushort Prevl; 50 ushort Prevr; 51 short fl; 52} 53Seg; 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 83static CvStatus 84icvSegmFloodFill_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 205static CvStatus 206icvSegmFloodFill_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 230static 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 331const CvPoint icvCodeDeltas[8] = 332 { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} }; 333 334static CvSeq* 335icvGetComponent( 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 476CV_IMPL CvSeq* 477cvSegmentImage( 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