Renesas GR-PEACH OpenCV Development
/
gr-peach-opencv-project-sd-card_update
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Fork of
gr-peach-opencv-project-sd-card
by 
the do
Embed:
(wiki syntax)
Show/hide line numbers
contours.cpp
00001 /*M/////////////////////////////////////////////////////////////////////////////////////// 00002 // 00003 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 00004 // 00005 // By downloading, copying, installing or using the software you agree to this license. 00006 // If you do not agree to this license, do not download, install, 00007 // copy or use the software. 00008 // 00009 // 00010 // Intel License Agreement 00011 // For Open Source Computer Vision Library 00012 // 00013 // Copyright (C) 2000, Intel Corporation, all rights reserved. 00014 // Third party copyrights are property of their respective owners. 00015 // 00016 // Redistribution and use in source and binary forms, with or without modification, 00017 // are permitted provided that the following conditions are met: 00018 // 00019 // * Redistribution's of source code must retain the above copyright notice, 00020 // this list of conditions and the following disclaimer. 00021 // 00022 // * Redistribution's in binary form must reproduce the above copyright notice, 00023 // this list of conditions and the following disclaimer in the documentation 00024 // and/or other materials provided with the distribution. 00025 // 00026 // * The name of Intel Corporation may not be used to endorse or promote products 00027 // derived from this software without specific prior written permission. 00028 // 00029 // This software is provided by the copyright holders and contributors "as is" and 00030 // any express or implied warranties, including, but not limited to, the implied 00031 // warranties of merchantability and fitness for a particular purpose are disclaimed. 00032 // In no event shall the Intel Corporation or contributors be liable for any direct, 00033 // indirect, incidental, special, exemplary, or consequential damages 00034 // (including, but not limited to, procurement of substitute goods or services; 00035 // loss of use, data, or profits; or business interruption) however caused 00036 // and on any theory of liability, whether in contract, strict liability, 00037 // or tort (including negligence or otherwise) arising in any way out of 00038 // the use of this software, even if advised of the possibility of such damage. 00039 // 00040 //M*/ 00041 #include "precomp.hpp" 00042 00043 /* initializes 8-element array for fast access to 3x3 neighborhood of a pixel */ 00044 #define CV_INIT_3X3_DELTAS( deltas, step, nch ) \ 00045 ((deltas)[0] = (nch), (deltas)[1] = -(step) + (nch), \ 00046 (deltas)[2] = -(step), (deltas)[3] = -(step) - (nch), \ 00047 (deltas)[4] = -(nch), (deltas)[5] = (step) - (nch), \ 00048 (deltas)[6] = (step), (deltas)[7] = (step) + (nch)) 00049 00050 static const CvPoint icvCodeDeltas[8] = 00051 { CvPoint(1, 0), CvPoint(1, -1), CvPoint(0, -1), CvPoint(-1, -1), CvPoint(-1, 0), CvPoint(-1, 1), CvPoint(0, 1), CvPoint(1, 1) }; 00052 00053 CV_IMPL void 00054 cvStartReadChainPoints( CvChain * chain, CvChainPtReader * reader ) 00055 { 00056 int i; 00057 00058 if( !chain || !reader ) 00059 CV_Error( CV_StsNullPtr, "" ); 00060 00061 if( chain->elem_size != 1 || chain->header_size < (int)sizeof(CvChain)) 00062 CV_Error( CV_StsBadSize, "" ); 00063 00064 cvStartReadSeq( (CvSeq *) chain, (CvSeqReader *) reader, 0 ); 00065 00066 reader->pt = chain->origin; 00067 for( i = 0; i < 8; i++ ) 00068 { 00069 reader->deltas[i][0] = (schar) icvCodeDeltas[i].x; 00070 reader->deltas[i][1] = (schar) icvCodeDeltas[i].y; 00071 } 00072 } 00073 00074 00075 /* retrieves next point of the chain curve and updates reader */ 00076 CV_IMPL CvPoint 00077 cvReadChainPoint( CvChainPtReader * reader ) 00078 { 00079 schar *ptr; 00080 int code; 00081 CvPoint pt; 00082 00083 if( !reader ) 00084 CV_Error( CV_StsNullPtr, "" ); 00085 00086 pt = reader->pt; 00087 00088 ptr = reader->ptr; 00089 if( ptr ) 00090 { 00091 code = *ptr++; 00092 00093 if( ptr >= reader->block_max ) 00094 { 00095 cvChangeSeqBlock( (CvSeqReader *) reader, 1 ); 00096 ptr = reader->ptr; 00097 } 00098 00099 reader->ptr = ptr; 00100 reader->code = (schar)code; 00101 assert( (code & ~7) == 0 ); 00102 reader->pt.x = pt.x + icvCodeDeltas[code].x; 00103 reader->pt.y = pt.y + icvCodeDeltas[code].y; 00104 } 00105 00106 return pt; 00107 } 00108 00109 00110 /****************************************************************************************\ 00111 * Raster->Chain Tree (Suzuki algorithms) * 00112 \****************************************************************************************/ 00113 00114 typedef struct _CvContourInfo 00115 { 00116 int flags; 00117 struct _CvContourInfo *next; /* next contour with the same mark value */ 00118 struct _CvContourInfo *parent; /* information about parent contour */ 00119 CvSeq *contour; /* corresponding contour (may be 0, if rejected) */ 00120 CvRect rect; /* bounding rectangle */ 00121 CvPoint origin; /* origin point (where the contour was traced from) */ 00122 int is_hole; /* hole flag */ 00123 } 00124 _CvContourInfo; 00125 00126 00127 /* 00128 Structure that is used for sequential retrieving contours from the image. 00129 It supports both hierarchical and plane variants of Suzuki algorithm. 00130 */ 00131 typedef struct _CvContourScanner 00132 { 00133 CvMemStorage *storage1; /* contains fetched contours */ 00134 CvMemStorage *storage2; /* contains approximated contours 00135 (!=storage1 if approx_method2 != approx_method1) */ 00136 CvMemStorage *cinfo_storage; /* contains _CvContourInfo nodes */ 00137 CvSet *cinfo_set; /* set of _CvContourInfo nodes */ 00138 CvMemStoragePos initial_pos; /* starting storage pos */ 00139 CvMemStoragePos backup_pos; /* beginning of the latest approx. contour */ 00140 CvMemStoragePos backup_pos2; /* ending of the latest approx. contour */ 00141 schar *img0; /* image origin */ 00142 schar *img; /* current image row */ 00143 int img_step; /* image step */ 00144 CvSize img_size; /* ROI size */ 00145 CvPoint offset; /* ROI offset: coordinates, added to each contour point */ 00146 CvPoint pt; /* current scanner position */ 00147 CvPoint lnbd; /* position of the last met contour */ 00148 int nbd; /* current mark val */ 00149 _CvContourInfo *l_cinfo; /* information about latest approx. contour */ 00150 _CvContourInfo cinfo_temp; /* temporary var which is used in simple modes */ 00151 _CvContourInfo frame_info; /* information about frame */ 00152 CvSeq frame; /* frame itself */ 00153 int approx_method1; /* approx method when tracing */ 00154 int approx_method2; /* final approx method */ 00155 int mode; /* contour scanning mode: 00156 0 - external only 00157 1 - all the contours w/o any hierarchy 00158 2 - connected components (i.e. two-level structure - 00159 external contours and holes), 00160 3 - full hierarchy; 00161 4 - connected components of a multi-level image 00162 */ 00163 int subst_flag; 00164 int seq_type1; /* type of fetched contours */ 00165 int header_size1; /* hdr size of fetched contours */ 00166 int elem_size1; /* elem size of fetched contours */ 00167 int seq_type2; /* */ 00168 int header_size2; /* the same for approx. contours */ 00169 int elem_size2; /* */ 00170 _CvContourInfo *cinfo_table[128]; 00171 } 00172 _CvContourScanner; 00173 00174 #define _CV_FIND_CONTOURS_FLAGS_EXTERNAL_ONLY 1 00175 #define _CV_FIND_CONTOURS_FLAGS_HIERARCHIC 2 00176 00177 /* 00178 Initializes scanner structure. 00179 Prepare image for scanning ( clear borders and convert all pixels to 0-1. 00180 */ 00181 CV_IMPL CvContourScanner 00182 cvStartFindContours( void* _img, CvMemStorage* storage, 00183 int header_size, int mode, 00184 int method, CvPoint offset ) 00185 { 00186 if( !storage ) 00187 CV_Error( CV_StsNullPtr, "" ); 00188 00189 CvMat stub, *mat = cvGetMat( _img, &stub ); 00190 00191 if( CV_MAT_TYPE(mat->type) == CV_32SC1 && mode == CV_RETR_CCOMP ) 00192 mode = CV_RETR_FLOODFILL; 00193 00194 if( !((CV_IS_MASK_ARR( mat ) && mode < CV_RETR_FLOODFILL) || 00195 (CV_MAT_TYPE(mat->type) == CV_32SC1 && mode == CV_RETR_FLOODFILL)) ) 00196 CV_Error( CV_StsUnsupportedFormat, 00197 "[Start]FindContours supports only CV_8UC1 images when mode != CV_RETR_FLOODFILL " 00198 "otherwise supports CV_32SC1 images only" ); 00199 00200 CvSize size = cvSize( mat->width, mat->height ); 00201 int step = mat->step; 00202 uchar* img = (uchar*)(mat->data.ptr); 00203 00204 if( method < 0 || method > CV_CHAIN_APPROX_TC89_KCOS ) 00205 CV_Error( CV_StsOutOfRange, "" ); 00206 00207 if( header_size < (int) (method == CV_CHAIN_CODE ? sizeof( CvChain ) : sizeof( CvContour ))) 00208 CV_Error( CV_StsBadSize, "" ); 00209 00210 CvContourScanner scanner = (CvContourScanner)cvAlloc( sizeof( *scanner )); 00211 memset( scanner, 0, sizeof(*scanner) ); 00212 00213 scanner->storage1 = scanner->storage2 = storage; 00214 scanner->img0 = (schar *) img; 00215 scanner->img = (schar *) (img + step); 00216 scanner->img_step = step; 00217 scanner->img_size.width = size.width - 1; /* exclude rightest column */ 00218 scanner->img_size.height = size.height - 1; /* exclude bottomost row */ 00219 scanner->mode = mode; 00220 scanner->offset = offset; 00221 scanner->pt.x = scanner->pt.y = 1; 00222 scanner->lnbd.x = 0; 00223 scanner->lnbd.y = 1; 00224 scanner->nbd = 2; 00225 scanner->frame_info.contour = &(scanner->frame); 00226 scanner->frame_info.is_hole = 1; 00227 scanner->frame_info.next = 0; 00228 scanner->frame_info.parent = 0; 00229 scanner->frame_info.rect = cvRect( 0, 0, size.width, size.height ); 00230 scanner->l_cinfo = 0; 00231 scanner->subst_flag = 0; 00232 00233 scanner->frame.flags = CV_SEQ_FLAG_HOLE; 00234 00235 scanner->approx_method2 = scanner->approx_method1 = method; 00236 00237 if( method == CV_CHAIN_APPROX_TC89_L1 || method == CV_CHAIN_APPROX_TC89_KCOS ) 00238 scanner->approx_method1 = CV_CHAIN_CODE; 00239 00240 if( scanner->approx_method1 == CV_CHAIN_CODE ) 00241 { 00242 scanner->seq_type1 = CV_SEQ_CHAIN_CONTOUR; 00243 scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ? 00244 header_size : sizeof( CvChain ); 00245 scanner->elem_size1 = sizeof( char ); 00246 } 00247 else 00248 { 00249 scanner->seq_type1 = CV_SEQ_POLYGON; 00250 scanner->header_size1 = scanner->approx_method1 == scanner->approx_method2 ? 00251 header_size : sizeof( CvContour ); 00252 scanner->elem_size1 = sizeof( CvPoint ); 00253 } 00254 00255 scanner->header_size2 = header_size; 00256 00257 if( scanner->approx_method2 == CV_CHAIN_CODE ) 00258 { 00259 scanner->seq_type2 = scanner->seq_type1; 00260 scanner->elem_size2 = scanner->elem_size1; 00261 } 00262 else 00263 { 00264 scanner->seq_type2 = CV_SEQ_POLYGON; 00265 scanner->elem_size2 = sizeof( CvPoint ); 00266 } 00267 00268 scanner->seq_type1 = scanner->approx_method1 == CV_CHAIN_CODE ? 00269 CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON; 00270 00271 scanner->seq_type2 = scanner->approx_method2 == CV_CHAIN_CODE ? 00272 CV_SEQ_CHAIN_CONTOUR : CV_SEQ_POLYGON; 00273 00274 cvSaveMemStoragePos( storage, &(scanner->initial_pos) ); 00275 00276 if( method > CV_CHAIN_APPROX_SIMPLE ) 00277 { 00278 scanner->storage1 = cvCreateChildMemStorage( scanner->storage2 ); 00279 } 00280 00281 if( mode > CV_RETR_LIST ) 00282 { 00283 scanner->cinfo_storage = cvCreateChildMemStorage( scanner->storage2 ); 00284 scanner->cinfo_set = cvCreateSet( 0, sizeof( CvSet ), sizeof( _CvContourInfo ), 00285 scanner->cinfo_storage ); 00286 } 00287 00288 /* make zero borders */ 00289 int esz = CV_ELEM_SIZE(mat->type); 00290 memset( img, 0, size.width*esz ); 00291 memset( img + step * (size.height - 1), 0, size.width*esz ); 00292 00293 img += step; 00294 for( int y = 1; y < size.height - 1; y++, img += step ) 00295 { 00296 for( int k = 0; k < esz; k++ ) 00297 img[k] = img[(size.width - 1)*esz + k] = (schar)0; 00298 } 00299 00300 /* converts all pixels to 0 or 1 */ 00301 if( CV_MAT_TYPE(mat->type) != CV_32S ) 00302 cvThreshold( mat, mat, 0, 1, CV_THRESH_BINARY ); 00303 00304 return scanner; 00305 } 00306 00307 /* 00308 Final stage of contour processing. 00309 Three variants possible: 00310 1. Contour, which was retrieved using border following, is added to 00311 the contour tree. It is the case when the icvSubstituteContour function 00312 was not called after retrieving the contour. 00313 00314 2. New contour, assigned by icvSubstituteContour function, is added to the 00315 tree. The retrieved contour itself is removed from the storage. 00316 Here two cases are possible: 00317 2a. If one deals with plane variant of algorithm 00318 (hierarchical structure is not reconstructed), 00319 the contour is removed completely. 00320 2b. In hierarchical case, the header of the contour is not removed. 00321 It's marked as "link to contour" and h_next pointer of it is set to 00322 new, substituting contour. 00323 00324 3. The similar to 2, but when NULL pointer was assigned by 00325 icvSubstituteContour function. In this case, the function removes 00326 retrieved contour completely if plane case and 00327 leaves header if hierarchical (but doesn't mark header as "link"). 00328 ------------------------------------------------------------------------ 00329 The 1st variant can be used to retrieve and store all the contours from the image 00330 (with optional conversion from chains to contours using some approximation from 00331 restricted set of methods). Some characteristics of contour can be computed in the 00332 same pass. 00333 00334 The usage scheme can look like: 00335 00336 icvContourScanner scanner; 00337 CvMemStorage* contour_storage; 00338 CvSeq* first_contour; 00339 CvStatus result; 00340 00341 ... 00342 00343 icvCreateMemStorage( &contour_storage, block_size/0 ); 00344 00345 ... 00346 00347 cvStartFindContours 00348 ( img, contour_storage, 00349 header_size, approx_method, 00350 [external_only,] 00351 &scanner ); 00352 00353 for(;;) 00354 { 00355 [CvSeq* contour;] 00356 result = icvFindNextContour( &scanner, &contour/0 ); 00357 00358 if( result != CV_OK ) break; 00359 00360 // calculate some characteristics 00361 ... 00362 } 00363 00364 if( result < 0 ) goto error_processing; 00365 00366 cvEndFindContours( &scanner, &first_contour ); 00367 ... 00368 00369 ----------------------------------------------------------------- 00370 00371 Second variant is more complex and can be used when someone wants store not 00372 the retrieved contours but transformed ones. (e.g. approximated with some 00373 non-default algorithm ). 00374 00375 The scheme can be the as following: 00376 00377 icvContourScanner scanner; 00378 CvMemStorage* contour_storage; 00379 CvMemStorage* temp_storage; 00380 CvSeq* first_contour; 00381 CvStatus result; 00382 00383 ... 00384 00385 icvCreateMemStorage( &contour_storage, block_size/0 ); 00386 icvCreateMemStorage( &temp_storage, block_size/0 ); 00387 00388 ... 00389 00390 icvStartFindContours8uC1R 00391 ( <img_params>, temp_storage, 00392 header_size, approx_method, 00393 [retrival_mode], 00394 &scanner ); 00395 00396 for(;;) 00397 { 00398 CvSeq* temp_contour; 00399 CvSeq* new_contour; 00400 result = icvFindNextContour( scanner, &temp_contour ); 00401 00402 if( result != CV_OK ) break; 00403 00404 <approximation_function>( temp_contour, contour_storage, 00405 &new_contour, <parameters...> ); 00406 00407 icvSubstituteContour( scanner, new_contour ); 00408 ... 00409 } 00410 00411 if( result < 0 ) goto error_processing; 00412 00413 cvEndFindContours( &scanner, &first_contour ); 00414 ... 00415 00416 ---------------------------------------------------------------------------- 00417 Third method to retrieve contours may be applied if contours are irrelevant 00418 themselves but some characteristics of them are used only. 00419 The usage is similar to second except slightly different internal loop 00420 00421 for(;;) 00422 { 00423 CvSeq* temp_contour; 00424 result = icvFindNextContour( &scanner, &temp_contour ); 00425 00426 if( result != CV_OK ) break; 00427 00428 // calculate some characteristics of temp_contour 00429 00430 icvSubstituteContour( scanner, 0 ); 00431 ... 00432 } 00433 00434 new_storage variable is not needed here. 00435 00436 Note, that the second and the third methods can interleave. I.e. it is possible to 00437 retain contours that satisfy with some criteria and reject others. 00438 In hierarchic case the resulting tree is the part of original tree with 00439 some nodes absent. But in the resulting tree the contour1 is a child 00440 (may be indirect) of contour2 iff in the original tree the contour1 00441 is a child (may be indirect) of contour2. 00442 */ 00443 static void 00444 icvEndProcessContour( CvContourScanner scanner ) 00445 { 00446 _CvContourInfo *l_cinfo = scanner->l_cinfo; 00447 00448 if( l_cinfo ) 00449 { 00450 if( scanner->subst_flag ) 00451 { 00452 CvMemStoragePos temp; 00453 00454 cvSaveMemStoragePos( scanner->storage2, &temp ); 00455 00456 if( temp.top == scanner->backup_pos2.top && 00457 temp.free_space == scanner->backup_pos2.free_space ) 00458 { 00459 cvRestoreMemStoragePos( scanner->storage2, &scanner->backup_pos ); 00460 } 00461 scanner->subst_flag = 0; 00462 } 00463 00464 if( l_cinfo->contour ) 00465 { 00466 cvInsertNodeIntoTree( l_cinfo->contour, l_cinfo->parent->contour, 00467 &(scanner->frame) ); 00468 } 00469 scanner->l_cinfo = 0; 00470 } 00471 } 00472 00473 /* replaces one contour with another */ 00474 CV_IMPL void 00475 cvSubstituteContour( CvContourScanner scanner, CvSeq * new_contour ) 00476 { 00477 _CvContourInfo *l_cinfo; 00478 00479 if( !scanner ) 00480 CV_Error( CV_StsNullPtr, "" ); 00481 00482 l_cinfo = scanner->l_cinfo; 00483 if( l_cinfo && l_cinfo->contour && l_cinfo->contour != new_contour ) 00484 { 00485 l_cinfo->contour = new_contour; 00486 scanner->subst_flag = 1; 00487 } 00488 } 00489 00490 00491 /* 00492 marks domain border with +/-<constant> and stores the contour into CvSeq. 00493 method: 00494 <0 - chain 00495 ==0 - direct 00496 >0 - simple approximation 00497 */ 00498 static void 00499 icvFetchContour( schar *ptr, 00500 int step, 00501 CvPoint pt, 00502 CvSeq* contour, 00503 int _method ) 00504 { 00505 const schar nbd = 2; 00506 int deltas[16]; 00507 CvSeqWriter writer; 00508 schar *i0 = ptr, *i1, *i3, *i4 = 0; 00509 int prev_s = -1, s, s_end; 00510 int method = _method - 1; 00511 00512 assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE ); 00513 00514 /* initialize local state */ 00515 CV_INIT_3X3_DELTAS( deltas, step, 1 ); 00516 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] )); 00517 00518 /* initialize writer */ 00519 cvStartAppendToSeq( contour, &writer ); 00520 00521 if( method < 0 ) 00522 ((CvChain *) contour)->origin = pt; 00523 00524 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4; 00525 00526 do 00527 { 00528 s = (s - 1) & 7; 00529 i1 = i0 + deltas[s]; 00530 if( *i1 != 0 ) 00531 break; 00532 } 00533 while( s != s_end ); 00534 00535 if( s == s_end ) /* single pixel domain */ 00536 { 00537 *i0 = (schar) (nbd | -128); 00538 if( method >= 0 ) 00539 { 00540 CV_WRITE_SEQ_ELEM( pt, writer ); 00541 } 00542 } 00543 else 00544 { 00545 i3 = i0; 00546 prev_s = s ^ 4; 00547 00548 /* follow border */ 00549 for( ;; ) 00550 { 00551 s_end = s; 00552 00553 for( ;; ) 00554 { 00555 i4 = i3 + deltas[++s]; 00556 if( *i4 != 0 ) 00557 break; 00558 } 00559 s &= 7; 00560 00561 /* check "right" bound */ 00562 if( (unsigned) (s - 1) < (unsigned) s_end ) 00563 { 00564 *i3 = (schar) (nbd | -128); 00565 } 00566 else if( *i3 == 1 ) 00567 { 00568 *i3 = nbd; 00569 } 00570 00571 if( method < 0 ) 00572 { 00573 schar _s = (schar) s; 00574 00575 CV_WRITE_SEQ_ELEM( _s, writer ); 00576 } 00577 else 00578 { 00579 if( s != prev_s || method == 0 ) 00580 { 00581 CV_WRITE_SEQ_ELEM( pt, writer ); 00582 prev_s = s; 00583 } 00584 00585 pt.x += icvCodeDeltas[s].x; 00586 pt.y += icvCodeDeltas[s].y; 00587 00588 } 00589 00590 if( i4 == i0 && i3 == i1 ) 00591 break; 00592 00593 i3 = i4; 00594 s = (s + 4) & 7; 00595 } /* end of border following loop */ 00596 } 00597 00598 cvEndWriteSeq( &writer ); 00599 00600 if( _method != CV_CHAIN_CODE ) 00601 cvBoundingRect( contour, 1 ); 00602 00603 assert( (writer.seq->total == 0 && writer.seq->first == 0) || 00604 writer.seq->total > writer.seq->first->count || 00605 (writer.seq->first->prev == writer.seq->first && 00606 writer.seq->first->next == writer.seq->first) ); 00607 } 00608 00609 00610 00611 /* 00612 trace contour until certain point is met. 00613 returns 1 if met, 0 else. 00614 */ 00615 static int 00616 icvTraceContour( schar *ptr, int step, schar *stop_ptr, int is_hole ) 00617 { 00618 int deltas[16]; 00619 schar *i0 = ptr, *i1, *i3, *i4; 00620 int s, s_end; 00621 00622 /* initialize local state */ 00623 CV_INIT_3X3_DELTAS( deltas, step, 1 ); 00624 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] )); 00625 00626 assert( (*i0 & -2) != 0 ); 00627 00628 s_end = s = is_hole ? 0 : 4; 00629 00630 do 00631 { 00632 s = (s - 1) & 7; 00633 i1 = i0 + deltas[s]; 00634 if( *i1 != 0 ) 00635 break; 00636 } 00637 while( s != s_end ); 00638 00639 i3 = i0; 00640 00641 /* check single pixel domain */ 00642 if( s != s_end ) 00643 { 00644 /* follow border */ 00645 for( ;; ) 00646 { 00647 s_end = s; 00648 00649 for( ;; ) 00650 { 00651 i4 = i3 + deltas[++s]; 00652 if( *i4 != 0 ) 00653 break; 00654 } 00655 00656 if( i3 == stop_ptr || (i4 == i0 && i3 == i1) ) 00657 break; 00658 00659 i3 = i4; 00660 s = (s + 4) & 7; 00661 } /* end of border following loop */ 00662 } 00663 return i3 == stop_ptr; 00664 } 00665 00666 00667 static void 00668 icvFetchContourEx( schar* ptr, 00669 int step, 00670 CvPoint pt, 00671 CvSeq* contour, 00672 int _method, 00673 int nbd, 00674 CvRect * _rect ) 00675 { 00676 int deltas[16]; 00677 CvSeqWriter writer; 00678 schar *i0 = ptr, *i1, *i3, *i4; 00679 CvRect rect; 00680 int prev_s = -1, s, s_end; 00681 int method = _method - 1; 00682 00683 assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE ); 00684 assert( 1 < nbd && nbd < 128 ); 00685 00686 /* initialize local state */ 00687 CV_INIT_3X3_DELTAS( deltas, step, 1 ); 00688 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] )); 00689 00690 /* initialize writer */ 00691 cvStartAppendToSeq( contour, &writer ); 00692 00693 if( method < 0 ) 00694 ((CvChain *)contour)->origin = pt; 00695 00696 rect.x = rect.width = pt.x; 00697 rect.y = rect.height = pt.y; 00698 00699 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4; 00700 00701 do 00702 { 00703 s = (s - 1) & 7; 00704 i1 = i0 + deltas[s]; 00705 if( *i1 != 0 ) 00706 break; 00707 } 00708 while( s != s_end ); 00709 00710 if( s == s_end ) /* single pixel domain */ 00711 { 00712 *i0 = (schar) (nbd | 0x80); 00713 if( method >= 0 ) 00714 { 00715 CV_WRITE_SEQ_ELEM( pt, writer ); 00716 } 00717 } 00718 else 00719 { 00720 i3 = i0; 00721 00722 prev_s = s ^ 4; 00723 00724 /* follow border */ 00725 for( ;; ) 00726 { 00727 s_end = s; 00728 00729 for( ;; ) 00730 { 00731 i4 = i3 + deltas[++s]; 00732 if( *i4 != 0 ) 00733 break; 00734 } 00735 s &= 7; 00736 00737 /* check "right" bound */ 00738 if( (unsigned) (s - 1) < (unsigned) s_end ) 00739 { 00740 *i3 = (schar) (nbd | 0x80); 00741 } 00742 else if( *i3 == 1 ) 00743 { 00744 *i3 = (schar) nbd; 00745 } 00746 00747 if( method < 0 ) 00748 { 00749 schar _s = (schar) s; 00750 CV_WRITE_SEQ_ELEM( _s, writer ); 00751 } 00752 else if( s != prev_s || method == 0 ) 00753 { 00754 CV_WRITE_SEQ_ELEM( pt, writer ); 00755 } 00756 00757 if( s != prev_s ) 00758 { 00759 /* update bounds */ 00760 if( pt.x < rect.x ) 00761 rect.x = pt.x; 00762 else if( pt.x > rect.width ) 00763 rect.width = pt.x; 00764 00765 if( pt.y < rect.y ) 00766 rect.y = pt.y; 00767 else if( pt.y > rect.height ) 00768 rect.height = pt.y; 00769 } 00770 00771 prev_s = s; 00772 pt.x += icvCodeDeltas[s].x; 00773 pt.y += icvCodeDeltas[s].y; 00774 00775 if( i4 == i0 && i3 == i1 ) break; 00776 00777 i3 = i4; 00778 s = (s + 4) & 7; 00779 } /* end of border following loop */ 00780 } 00781 00782 rect.width -= rect.x - 1; 00783 rect.height -= rect.y - 1; 00784 00785 cvEndWriteSeq( &writer ); 00786 00787 if( _method != CV_CHAIN_CODE ) 00788 ((CvContour*)contour)->rect = rect; 00789 00790 assert( (writer.seq->total == 0 && writer.seq->first == 0) || 00791 writer.seq->total > writer.seq->first->count || 00792 (writer.seq->first->prev == writer.seq->first && 00793 writer.seq->first->next == writer.seq->first) ); 00794 00795 if( _rect ) *_rect = rect; 00796 } 00797 00798 00799 static int 00800 icvTraceContour_32s( int *ptr, int step, int *stop_ptr, int is_hole ) 00801 { 00802 int deltas[16]; 00803 int *i0 = ptr, *i1, *i3, *i4; 00804 int s, s_end; 00805 const int right_flag = INT_MIN; 00806 const int new_flag = (int)((unsigned)INT_MIN >> 1); 00807 const int value_mask = ~(right_flag | new_flag); 00808 const int ccomp_val = *i0 & value_mask; 00809 00810 /* initialize local state */ 00811 CV_INIT_3X3_DELTAS( deltas, step, 1 ); 00812 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] )); 00813 00814 s_end = s = is_hole ? 0 : 4; 00815 00816 do 00817 { 00818 s = (s - 1) & 7; 00819 i1 = i0 + deltas[s]; 00820 if( (*i1 & value_mask) == ccomp_val ) 00821 break; 00822 } 00823 while( s != s_end ); 00824 00825 i3 = i0; 00826 00827 /* check single pixel domain */ 00828 if( s != s_end ) 00829 { 00830 /* follow border */ 00831 for( ;; ) 00832 { 00833 s_end = s; 00834 00835 for( ;; ) 00836 { 00837 i4 = i3 + deltas[++s]; 00838 if( (*i4 & value_mask) == ccomp_val ) 00839 break; 00840 } 00841 00842 if( i3 == stop_ptr || (i4 == i0 && i3 == i1) ) 00843 break; 00844 00845 i3 = i4; 00846 s = (s + 4) & 7; 00847 } /* end of border following loop */ 00848 } 00849 return i3 == stop_ptr; 00850 } 00851 00852 00853 static void 00854 icvFetchContourEx_32s( int* ptr, 00855 int step, 00856 CvPoint pt, 00857 CvSeq* contour, 00858 int _method, 00859 CvRect * _rect ) 00860 { 00861 int deltas[16]; 00862 CvSeqWriter writer; 00863 int *i0 = ptr, *i1, *i3, *i4; 00864 CvRect rect; 00865 int prev_s = -1, s, s_end; 00866 int method = _method - 1; 00867 const int right_flag = INT_MIN; 00868 const int new_flag = (int)((unsigned)INT_MIN >> 1); 00869 const int value_mask = ~(right_flag | new_flag); 00870 const int ccomp_val = *i0 & value_mask; 00871 const int nbd0 = ccomp_val | new_flag; 00872 const int nbd1 = nbd0 | right_flag; 00873 00874 assert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE ); 00875 00876 /* initialize local state */ 00877 CV_INIT_3X3_DELTAS( deltas, step, 1 ); 00878 memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] )); 00879 00880 /* initialize writer */ 00881 cvStartAppendToSeq( contour, &writer ); 00882 00883 if( method < 0 ) 00884 ((CvChain *)contour)->origin = pt; 00885 00886 rect.x = rect.width = pt.x; 00887 rect.y = rect.height = pt.y; 00888 00889 s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4; 00890 00891 do 00892 { 00893 s = (s - 1) & 7; 00894 i1 = i0 + deltas[s]; 00895 if( (*i1 & value_mask) == ccomp_val ) 00896 break; 00897 } 00898 while( s != s_end ); 00899 00900 if( s == s_end ) /* single pixel domain */ 00901 { 00902 *i0 = nbd1; 00903 if( method >= 0 ) 00904 { 00905 CV_WRITE_SEQ_ELEM( pt, writer ); 00906 } 00907 } 00908 else 00909 { 00910 i3 = i0; 00911 prev_s = s ^ 4; 00912 00913 /* follow border */ 00914 for( ;; ) 00915 { 00916 s_end = s; 00917 00918 for( ;; ) 00919 { 00920 i4 = i3 + deltas[++s]; 00921 if( (*i4 & value_mask) == ccomp_val ) 00922 break; 00923 } 00924 s &= 7; 00925 00926 /* check "right" bound */ 00927 if( (unsigned) (s - 1) < (unsigned) s_end ) 00928 { 00929 *i3 = nbd1; 00930 } 00931 else if( *i3 == ccomp_val ) 00932 { 00933 *i3 = nbd0; 00934 } 00935 00936 if( method < 0 ) 00937 { 00938 schar _s = (schar) s; 00939 CV_WRITE_SEQ_ELEM( _s, writer ); 00940 } 00941 else if( s != prev_s || method == 0 ) 00942 { 00943 CV_WRITE_SEQ_ELEM( pt, writer ); 00944 } 00945 00946 if( s != prev_s ) 00947 { 00948 /* update bounds */ 00949 if( pt.x < rect.x ) 00950 rect.x = pt.x; 00951 else if( pt.x > rect.width ) 00952 rect.width = pt.x; 00953 00954 if( pt.y < rect.y ) 00955 rect.y = pt.y; 00956 else if( pt.y > rect.height ) 00957 rect.height = pt.y; 00958 } 00959 00960 prev_s = s; 00961 pt.x += icvCodeDeltas[s].x; 00962 pt.y += icvCodeDeltas[s].y; 00963 00964 if( i4 == i0 && i3 == i1 ) break; 00965 00966 i3 = i4; 00967 s = (s + 4) & 7; 00968 } /* end of border following loop */ 00969 } 00970 00971 rect.width -= rect.x - 1; 00972 rect.height -= rect.y - 1; 00973 00974 cvEndWriteSeq( &writer ); 00975 00976 if( _method != CV_CHAIN_CODE ) 00977 ((CvContour*)contour)->rect = rect; 00978 00979 assert( (writer.seq->total == 0 && writer.seq->first == 0) || 00980 writer.seq->total > writer.seq->first->count || 00981 (writer.seq->first->prev == writer.seq->first && 00982 writer.seq->first->next == writer.seq->first) ); 00983 00984 if( _rect ) *_rect = rect; 00985 } 00986 00987 00988 CvSeq * 00989 cvFindNextContour( CvContourScanner scanner ) 00990 { 00991 if( !scanner ) 00992 CV_Error( CV_StsNullPtr, "" ); 00993 icvEndProcessContour( scanner ); 00994 00995 /* initialize local state */ 00996 schar* img0 = scanner->img0; 00997 schar* img = scanner->img; 00998 int step = scanner->img_step; 00999 int step_i = step / sizeof(int); 01000 int x = scanner->pt.x; 01001 int y = scanner->pt.y; 01002 int width = scanner->img_size.width; 01003 int height = scanner->img_size.height; 01004 int mode = scanner->mode; 01005 CvPoint lnbd = scanner->lnbd; 01006 int nbd = scanner->nbd; 01007 int prev = img[x - 1]; 01008 int new_mask = -2; 01009 01010 if( mode == CV_RETR_FLOODFILL ) 01011 { 01012 prev = ((int*)img)[x - 1]; 01013 new_mask = INT_MIN / 2; 01014 } 01015 01016 for( ; y < height; y++, img += step ) 01017 { 01018 int* img0_i = 0; 01019 int* img_i = 0; 01020 int p = 0; 01021 01022 if( mode == CV_RETR_FLOODFILL ) 01023 { 01024 img0_i = (int*)img0; 01025 img_i = (int*)img; 01026 } 01027 01028 for( ; x < width; x++ ) 01029 { 01030 if( img_i ) 01031 { 01032 for( ; x < width && ((p = img_i[x]) == prev || (p & ~new_mask) == (prev & ~new_mask)); x++ ) 01033 prev = p; 01034 } 01035 else 01036 { 01037 for( ; x < width && (p = img[x]) == prev; x++ ) 01038 ; 01039 } 01040 01041 if( x >= width ) 01042 break; 01043 01044 { 01045 _CvContourInfo *par_info = 0; 01046 _CvContourInfo *l_cinfo = 0; 01047 CvSeq *seq = 0; 01048 int is_hole = 0; 01049 CvPoint origin; 01050 01051 /* if not external contour */ 01052 if( (!img_i && !(prev == 0 && p == 1)) || 01053 (img_i && !(((prev & new_mask) != 0 || prev == 0) && (p & new_mask) == 0)) ) 01054 { 01055 /* check hole */ 01056 if( (!img_i && (p != 0 || prev < 1)) || 01057 (img_i && ((prev & new_mask) != 0 || (p & new_mask) != 0))) 01058 goto resume_scan; 01059 01060 if( prev & new_mask ) 01061 { 01062 lnbd.x = x - 1; 01063 } 01064 is_hole = 1; 01065 } 01066 01067 if( mode == 0 && (is_hole || img0[lnbd.y * step + lnbd.x] > 0) ) 01068 goto resume_scan; 01069 01070 origin.y = y; 01071 origin.x = x - is_hole; 01072 01073 /* find contour parent */ 01074 if( mode <= 1 || (!is_hole && (mode == CV_RETR_CCOMP || mode == CV_RETR_FLOODFILL)) || lnbd.x <= 0 ) 01075 { 01076 par_info = &(scanner->frame_info); 01077 } 01078 else 01079 { 01080 int lval = (img0_i ? 01081 img0_i[lnbd.y * step_i + lnbd.x] : 01082 (int)img0[lnbd.y * step + lnbd.x]) & 0x7f; 01083 _CvContourInfo *cur = scanner->cinfo_table[lval]; 01084 01085 /* find the first bounding contour */ 01086 while( cur ) 01087 { 01088 if( (unsigned) (lnbd.x - cur->rect.x) < (unsigned) cur->rect.width && 01089 (unsigned) (lnbd.y - cur->rect.y) < (unsigned) cur->rect.height ) 01090 { 01091 if( par_info ) 01092 { 01093 if( (img0_i && 01094 icvTraceContour_32s( img0_i + par_info->origin.y * step_i + 01095 par_info->origin.x, step_i, img_i + lnbd.x, 01096 par_info->is_hole ) > 0) || 01097 (!img0_i && 01098 icvTraceContour( img0 + par_info->origin.y * step + 01099 par_info->origin.x, step, img + lnbd.x, 01100 par_info->is_hole ) > 0) ) 01101 break; 01102 } 01103 par_info = cur; 01104 } 01105 cur = cur->next; 01106 } 01107 01108 assert( par_info != 0 ); 01109 01110 /* if current contour is a hole and previous contour is a hole or 01111 current contour is external and previous contour is external then 01112 the parent of the contour is the parent of the previous contour else 01113 the parent is the previous contour itself. */ 01114 if( par_info->is_hole == is_hole ) 01115 { 01116 par_info = par_info->parent; 01117 /* every contour must have a parent 01118 (at least, the frame of the image) */ 01119 if( !par_info ) 01120 par_info = &(scanner->frame_info); 01121 } 01122 01123 /* hole flag of the parent must differ from the flag of the contour */ 01124 assert( par_info->is_hole != is_hole ); 01125 if( par_info->contour == 0 ) /* removed contour */ 01126 goto resume_scan; 01127 } 01128 01129 lnbd.x = x - is_hole; 01130 01131 cvSaveMemStoragePos( scanner->storage2, &(scanner->backup_pos) ); 01132 01133 seq = cvCreateSeq( scanner->seq_type1, scanner->header_size1, 01134 scanner->elem_size1, scanner->storage1 ); 01135 seq->flags |= is_hole ? CV_SEQ_FLAG_HOLE : 0; 01136 01137 /* initialize header */ 01138 if( mode <= 1 ) 01139 { 01140 l_cinfo = &(scanner->cinfo_temp); 01141 icvFetchContour( img + x - is_hole, step, 01142 cvPoint( origin.x + scanner->offset.x, 01143 origin.y + scanner->offset.y), 01144 seq, scanner->approx_method1 ); 01145 } 01146 else 01147 { 01148 union { _CvContourInfo* ci; CvSetElem* se; } v; 01149 v.ci = l_cinfo; 01150 cvSetAdd( scanner->cinfo_set, 0, &v.se ); 01151 l_cinfo = v.ci; 01152 int lval; 01153 01154 if( img_i ) 01155 { 01156 lval = img_i[x - is_hole] & 127; 01157 icvFetchContourEx_32s(img_i + x - is_hole, step_i, 01158 cvPoint( origin.x + scanner->offset.x, 01159 origin.y + scanner->offset.y), 01160 seq, scanner->approx_method1, 01161 &(l_cinfo->rect) ); 01162 } 01163 else 01164 { 01165 lval = nbd; 01166 // change nbd 01167 nbd = (nbd + 1) & 127; 01168 nbd += nbd == 0 ? 3 : 0; 01169 icvFetchContourEx( img + x - is_hole, step, 01170 cvPoint( origin.x + scanner->offset.x, 01171 origin.y + scanner->offset.y), 01172 seq, scanner->approx_method1, 01173 lval, &(l_cinfo->rect) ); 01174 } 01175 l_cinfo->rect.x -= scanner->offset.x; 01176 l_cinfo->rect.y -= scanner->offset.y; 01177 01178 l_cinfo->next = scanner->cinfo_table[lval]; 01179 scanner->cinfo_table[lval] = l_cinfo; 01180 } 01181 01182 l_cinfo->is_hole = is_hole; 01183 l_cinfo->contour = seq; 01184 l_cinfo->origin = origin; 01185 l_cinfo->parent = par_info; 01186 01187 if( scanner->approx_method1 != scanner->approx_method2 ) 01188 { 01189 l_cinfo->contour = icvApproximateChainTC89( (CvChain *) seq, 01190 scanner->header_size2, 01191 scanner->storage2, 01192 scanner->approx_method2 ); 01193 cvClearMemStorage( scanner->storage1 ); 01194 } 01195 01196 l_cinfo->contour->v_prev = l_cinfo->parent->contour; 01197 01198 if( par_info->contour == 0 ) 01199 { 01200 l_cinfo->contour = 0; 01201 if( scanner->storage1 == scanner->storage2 ) 01202 { 01203 cvRestoreMemStoragePos( scanner->storage1, &(scanner->backup_pos) ); 01204 } 01205 else 01206 { 01207 cvClearMemStorage( scanner->storage1 ); 01208 } 01209 p = img[x]; 01210 goto resume_scan; 01211 } 01212 01213 cvSaveMemStoragePos( scanner->storage2, &(scanner->backup_pos2) ); 01214 scanner->l_cinfo = l_cinfo; 01215 scanner->pt.x = !img_i ? x + 1 : x + 1 - is_hole; 01216 scanner->pt.y = y; 01217 scanner->lnbd = lnbd; 01218 scanner->img = (schar *) img; 01219 scanner->nbd = nbd; 01220 return l_cinfo->contour; 01221 01222 resume_scan: 01223 01224 prev = p; 01225 /* update lnbd */ 01226 if( prev & -2 ) 01227 { 01228 lnbd.x = x; 01229 } 01230 } /* end of prev != p */ 01231 } /* end of loop on x */ 01232 01233 lnbd.x = 0; 01234 lnbd.y = y + 1; 01235 x = 1; 01236 prev = 0; 01237 } /* end of loop on y */ 01238 01239 return 0; 01240 } 01241 01242 01243 /* 01244 The function add to tree the last retrieved/substituted contour, 01245 releases temp_storage, restores state of dst_storage (if needed), and 01246 returns pointer to root of the contour tree */ 01247 CV_IMPL CvSeq * 01248 cvEndFindContours( CvContourScanner * _scanner ) 01249 { 01250 CvContourScanner scanner; 01251 CvSeq *first = 0; 01252 01253 if( !_scanner ) 01254 CV_Error( CV_StsNullPtr, "" ); 01255 scanner = *_scanner; 01256 01257 if( scanner ) 01258 { 01259 icvEndProcessContour( scanner ); 01260 01261 if( scanner->storage1 != scanner->storage2 ) 01262 cvReleaseMemStorage( &(scanner->storage1) ); 01263 01264 if( scanner->cinfo_storage ) 01265 cvReleaseMemStorage( &(scanner->cinfo_storage) ); 01266 01267 first = scanner->frame.v_next; 01268 cvFree( _scanner ); 01269 } 01270 01271 return first; 01272 } 01273 01274 01275 #define ICV_SINGLE 0 01276 #define ICV_CONNECTING_ABOVE 1 01277 #define ICV_CONNECTING_BELOW -1 01278 #define ICV_IS_COMPONENT_POINT(val) ((val) != 0) 01279 01280 #define CV_GET_WRITTEN_ELEM( writer ) ((writer).ptr - (writer).seq->elem_size) 01281 01282 typedef struct CvLinkedRunPoint 01283 { 01284 struct CvLinkedRunPoint* link; 01285 struct CvLinkedRunPoint* next; 01286 CvPoint pt; 01287 } 01288 CvLinkedRunPoint; 01289 01290 01291 static int 01292 icvFindContoursInInterval( const CvArr* src, 01293 /*int minValue, int maxValue,*/ 01294 CvMemStorage* storage, 01295 CvSeq** result, 01296 int contourHeaderSize ) 01297 { 01298 int count = 0; 01299 cv::Ptr<CvMemStorage> storage00; 01300 cv::Ptr<CvMemStorage> storage01; 01301 CvSeq* first = 0; 01302 01303 int i, j, k, n; 01304 01305 uchar* src_data = 0; 01306 int img_step = 0; 01307 CvSize img_size; 01308 01309 int connect_flag; 01310 int lower_total; 01311 int upper_total; 01312 int all_total; 01313 01314 CvSeq* runs; 01315 CvLinkedRunPoint tmp; 01316 CvLinkedRunPoint* tmp_prev; 01317 CvLinkedRunPoint* upper_line = 0; 01318 CvLinkedRunPoint* lower_line = 0; 01319 CvLinkedRunPoint* last_elem; 01320 01321 CvLinkedRunPoint* upper_run = 0; 01322 CvLinkedRunPoint* lower_run = 0; 01323 CvLinkedRunPoint* prev_point = 0; 01324 01325 CvSeqWriter writer_ext; 01326 CvSeqWriter writer_int; 01327 CvSeqWriter writer; 01328 CvSeqReader reader; 01329 01330 CvSeq* external_contours; 01331 CvSeq* internal_contours; 01332 CvSeq* prev = 0; 01333 01334 if( !storage ) 01335 CV_Error( CV_StsNullPtr, "NULL storage pointer" ); 01336 01337 if( !result ) 01338 CV_Error( CV_StsNullPtr, "NULL double CvSeq pointer" ); 01339 01340 if( contourHeaderSize < (int)sizeof(CvContour)) 01341 CV_Error( CV_StsBadSize, "Contour header size must be >= sizeof(CvContour)" ); 01342 01343 storage00.reset(cvCreateChildMemStorage(storage)); 01344 storage01.reset(cvCreateChildMemStorage(storage)); 01345 01346 CvMat stub, *mat; 01347 01348 mat = cvGetMat( src, &stub ); 01349 if( !CV_IS_MASK_ARR(mat)) 01350 CV_Error( CV_StsBadArg, "Input array must be 8uC1 or 8sC1" ); 01351 src_data = mat->data.ptr; 01352 img_step = mat->step; 01353 img_size = cvGetMatSize( mat ); 01354 01355 // Create temporary sequences 01356 runs = cvCreateSeq(0, sizeof(CvSeq), sizeof(CvLinkedRunPoint), storage00 ); 01357 cvStartAppendToSeq( runs, &writer ); 01358 01359 cvStartWriteSeq( 0, sizeof(CvSeq), sizeof(CvLinkedRunPoint*), storage01, &writer_ext ); 01360 cvStartWriteSeq( 0, sizeof(CvSeq), sizeof(CvLinkedRunPoint*), storage01, &writer_int ); 01361 01362 tmp_prev = &(tmp); 01363 tmp_prev->next = 0; 01364 tmp_prev->link = 0; 01365 01366 // First line. None of runs is binded 01367 tmp.pt.y = 0; 01368 i = 0; 01369 CV_WRITE_SEQ_ELEM( tmp, writer ); 01370 upper_line = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer ); 01371 01372 tmp_prev = upper_line; 01373 for( j = 0; j < img_size.width; ) 01374 { 01375 for( ; j < img_size.width && !ICV_IS_COMPONENT_POINT(src_data[j]); j++ ) 01376 ; 01377 if( j == img_size.width ) 01378 break; 01379 01380 tmp.pt.x = j; 01381 CV_WRITE_SEQ_ELEM( tmp, writer ); 01382 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer ); 01383 tmp_prev = tmp_prev->next; 01384 01385 for( ; j < img_size.width && ICV_IS_COMPONENT_POINT(src_data[j]); j++ ) 01386 ; 01387 01388 tmp.pt.x = j-1; 01389 CV_WRITE_SEQ_ELEM( tmp, writer ); 01390 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer ); 01391 tmp_prev->link = tmp_prev->next; 01392 // First point of contour 01393 CV_WRITE_SEQ_ELEM( tmp_prev, writer_ext ); 01394 tmp_prev = tmp_prev->next; 01395 } 01396 cvFlushSeqWriter( &writer ); 01397 upper_line = upper_line->next; 01398 upper_total = runs->total - 1; 01399 last_elem = tmp_prev; 01400 tmp_prev->next = 0; 01401 01402 for( i = 1; i < img_size.height; i++ ) 01403 { 01404 //------// Find runs in next line 01405 src_data += img_step; 01406 tmp.pt.y = i; 01407 all_total = runs->total; 01408 for( j = 0; j < img_size.width; ) 01409 { 01410 for( ; j < img_size.width && !ICV_IS_COMPONENT_POINT(src_data[j]); j++ ) 01411 ; 01412 if( j == img_size.width ) break; 01413 01414 tmp.pt.x = j; 01415 CV_WRITE_SEQ_ELEM( tmp, writer ); 01416 tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer ); 01417 tmp_prev = tmp_prev->next; 01418 01419 for( ; j < img_size.width && ICV_IS_COMPONENT_POINT(src_data[j]); j++ ) 01420 ; 01421 01422 tmp.pt.x = j-1; 01423 CV_WRITE_SEQ_ELEM( tmp, writer ); 01424 tmp_prev = tmp_prev->next = (CvLinkedRunPoint*)CV_GET_WRITTEN_ELEM( writer ); 01425 }//j 01426 cvFlushSeqWriter( &writer ); 01427 lower_line = last_elem->next; 01428 lower_total = runs->total - all_total; 01429 last_elem = tmp_prev; 01430 tmp_prev->next = 0; 01431 //------// 01432 //------// Find links between runs of lower_line and upper_line 01433 upper_run = upper_line; 01434 lower_run = lower_line; 01435 connect_flag = ICV_SINGLE; 01436 01437 for( k = 0, n = 0; k < upper_total/2 && n < lower_total/2; ) 01438 { 01439 switch( connect_flag ) 01440 { 01441 case ICV_SINGLE: 01442 if( upper_run->next->pt.x < lower_run->next->pt.x ) 01443 { 01444 if( upper_run->next->pt.x >= lower_run->pt.x -1 ) 01445 { 01446 lower_run->link = upper_run; 01447 connect_flag = ICV_CONNECTING_ABOVE; 01448 prev_point = upper_run->next; 01449 } 01450 else 01451 upper_run->next->link = upper_run; 01452 k++; 01453 upper_run = upper_run->next->next; 01454 } 01455 else 01456 { 01457 if( upper_run->pt.x <= lower_run->next->pt.x +1 ) 01458 { 01459 lower_run->link = upper_run; 01460 connect_flag = ICV_CONNECTING_BELOW; 01461 prev_point = lower_run->next; 01462 } 01463 else 01464 { 01465 lower_run->link = lower_run->next; 01466 // First point of contour 01467 CV_WRITE_SEQ_ELEM( lower_run, writer_ext ); 01468 } 01469 n++; 01470 lower_run = lower_run->next->next; 01471 } 01472 break; 01473 case ICV_CONNECTING_ABOVE: 01474 if( upper_run->pt.x > lower_run->next->pt.x +1 ) 01475 { 01476 prev_point->link = lower_run->next; 01477 connect_flag = ICV_SINGLE; 01478 n++; 01479 lower_run = lower_run->next->next; 01480 } 01481 else 01482 { 01483 prev_point->link = upper_run; 01484 if( upper_run->next->pt.x < lower_run->next->pt.x ) 01485 { 01486 k++; 01487 prev_point = upper_run->next; 01488 upper_run = upper_run->next->next; 01489 } 01490 else 01491 { 01492 connect_flag = ICV_CONNECTING_BELOW; 01493 prev_point = lower_run->next; 01494 n++; 01495 lower_run = lower_run->next->next; 01496 } 01497 } 01498 break; 01499 case ICV_CONNECTING_BELOW: 01500 if( lower_run->pt.x > upper_run->next->pt.x +1 ) 01501 { 01502 upper_run->next->link = prev_point; 01503 connect_flag = ICV_SINGLE; 01504 k++; 01505 upper_run = upper_run->next->next; 01506 } 01507 else 01508 { 01509 // First point of contour 01510 CV_WRITE_SEQ_ELEM( lower_run, writer_int ); 01511 01512 lower_run->link = prev_point; 01513 if( lower_run->next->pt.x < upper_run->next->pt.x ) 01514 { 01515 n++; 01516 prev_point = lower_run->next; 01517 lower_run = lower_run->next->next; 01518 } 01519 else 01520 { 01521 connect_flag = ICV_CONNECTING_ABOVE; 01522 k++; 01523 prev_point = upper_run->next; 01524 upper_run = upper_run->next->next; 01525 } 01526 } 01527 break; 01528 } 01529 }// k, n 01530 01531 for( ; n < lower_total/2; n++ ) 01532 { 01533 if( connect_flag != ICV_SINGLE ) 01534 { 01535 prev_point->link = lower_run->next; 01536 connect_flag = ICV_SINGLE; 01537 lower_run = lower_run->next->next; 01538 continue; 01539 } 01540 lower_run->link = lower_run->next; 01541 01542 //First point of contour 01543 CV_WRITE_SEQ_ELEM( lower_run, writer_ext ); 01544 01545 lower_run = lower_run->next->next; 01546 } 01547 01548 for( ; k < upper_total/2; k++ ) 01549 { 01550 if( connect_flag != ICV_SINGLE ) 01551 { 01552 upper_run->next->link = prev_point; 01553 connect_flag = ICV_SINGLE; 01554 upper_run = upper_run->next->next; 01555 continue; 01556 } 01557 upper_run->next->link = upper_run; 01558 upper_run = upper_run->next->next; 01559 } 01560 upper_line = lower_line; 01561 upper_total = lower_total; 01562 }//i 01563 01564 upper_run = upper_line; 01565 01566 //the last line of image 01567 for( k = 0; k < upper_total/2; k++ ) 01568 { 01569 upper_run->next->link = upper_run; 01570 upper_run = upper_run->next->next; 01571 } 01572 01573 //------// 01574 //------//Find end read contours 01575 external_contours = cvEndWriteSeq( &writer_ext ); 01576 internal_contours = cvEndWriteSeq( &writer_int ); 01577 01578 for( k = 0; k < 2; k++ ) 01579 { 01580 CvSeq* contours = k == 0 ? external_contours : internal_contours; 01581 01582 cvStartReadSeq( contours, &reader ); 01583 01584 for( j = 0; j < contours->total; j++, count++ ) 01585 { 01586 CvLinkedRunPoint* p_temp; 01587 CvLinkedRunPoint* p00; 01588 CvLinkedRunPoint* p01; 01589 CvSeq* contour; 01590 01591 CV_READ_SEQ_ELEM( p00, reader ); 01592 p01 = p00; 01593 01594 if( !p00->link ) 01595 continue; 01596 01597 cvStartWriteSeq( CV_SEQ_ELTYPE_POINT | CV_SEQ_POLYLINE | CV_SEQ_FLAG_CLOSED, 01598 contourHeaderSize, sizeof(CvPoint), storage, &writer ); 01599 do 01600 { 01601 CV_WRITE_SEQ_ELEM( p00->pt, writer ); 01602 p_temp = p00; 01603 p00 = p00->link; 01604 p_temp->link = 0; 01605 } 01606 while( p00 != p01 ); 01607 01608 contour = cvEndWriteSeq( &writer ); 01609 cvBoundingRect( contour, 1 ); 01610 01611 if( k != 0 ) 01612 contour->flags |= CV_SEQ_FLAG_HOLE; 01613 01614 if( !first ) 01615 prev = first = contour; 01616 else 01617 { 01618 contour->h_prev = prev; 01619 prev = prev->h_next = contour; 01620 } 01621 } 01622 } 01623 01624 if( !first ) 01625 count = -1; 01626 01627 if( result ) 01628 *result = first; 01629 01630 return count; 01631 } 01632 01633 01634 01635 /*F/////////////////////////////////////////////////////////////////////////////////////// 01636 // Name: cvFindContours 01637 // Purpose: 01638 // Finds all the contours on the bi-level image. 01639 // Context: 01640 // Parameters: 01641 // img - source image. 01642 // Non-zero pixels are considered as 1-pixels 01643 // and zero pixels as 0-pixels. 01644 // step - full width of source image in bytes. 01645 // size - width and height of the image in pixels 01646 // storage - pointer to storage where will the output contours be placed. 01647 // header_size - header size of resulting contours 01648 // mode - mode of contour retrieval. 01649 // method - method of approximation that is applied to contours 01650 // first_contour - pointer to first contour pointer 01651 // Returns: 01652 // CV_OK or error code 01653 // Notes: 01654 //F*/ 01655 CV_IMPL int 01656 cvFindContours( void* img, CvMemStorage* storage, 01657 CvSeq** firstContour, int cntHeaderSize, 01658 int mode, 01659 int method, CvPoint offset ) 01660 { 01661 CvContourScanner scanner = 0; 01662 CvSeq *contour = 0; 01663 int count = -1; 01664 01665 if( !firstContour ) 01666 CV_Error( CV_StsNullPtr, "NULL double CvSeq pointer" ); 01667 01668 *firstContour = 0; 01669 01670 if( method == CV_LINK_RUNS ) 01671 { 01672 if( offset.x != 0 || offset.y != 0 ) 01673 CV_Error( CV_StsOutOfRange, 01674 "Nonzero offset is not supported in CV_LINK_RUNS yet" ); 01675 01676 count = icvFindContoursInInterval( img, storage, firstContour, cntHeaderSize ); 01677 } 01678 else 01679 { 01680 //try 01681 // { 01682 scanner = cvStartFindContours( img, storage, cntHeaderSize, mode, method, offset ); 01683 01684 do 01685 { 01686 count++; 01687 contour = cvFindNextContour( scanner ); 01688 } 01689 while( contour != 0 ); 01690 //} 01691 // catch(...) 01692 // { 01693 // if( scanner ) 01694 // cvEndFindContours(&scanner); 01695 // return -1; 01696 // } 01697 01698 *firstContour = cvEndFindContours( &scanner ); 01699 } 01700 01701 return count; 01702 } 01703 01704 void cv::findContours( InputOutputArray _image, OutputArrayOfArrays _contours, 01705 OutputArray _hierarchy, int mode, int method, Point offset ) 01706 { 01707 // Sanity check: output must be of type vector<vector<Point>> 01708 CV_Assert((_contours.kind() == _InputArray::STD_VECTOR_VECTOR || _contours.kind() == _InputArray::STD_VECTOR_MAT || 01709 _contours.kind() == _InputArray::STD_VECTOR_UMAT)); 01710 01711 CV_Assert(_contours.empty() || (_contours.channels() == 2 && _contours.depth() == CV_32S)); 01712 01713 Mat image = _image.getMat(); 01714 MemStorage storage(cvCreateMemStorage()); 01715 CvMat _cimage = image; 01716 CvSeq* _ccontours = 0; 01717 if( _hierarchy.needed() ) 01718 _hierarchy.clear(); 01719 cvFindContours(&_cimage, storage, &_ccontours, sizeof(CvContour), mode, method, offset); 01720 if( !_ccontours ) 01721 { 01722 _contours.clear(); 01723 return; 01724 } 01725 Seq<CvSeq*> all_contours(cvTreeToNodeSeq( _ccontours, sizeof(CvSeq), storage )); 01726 int i, total = (int)all_contours.size(); 01727 _contours.create(total, 1, 0, -1, true); 01728 SeqIterator<CvSeq*> it = all_contours.begin(); 01729 for( i = 0; i < total; i++, ++it ) 01730 { 01731 CvSeq* c = *it; 01732 ((CvContour*)c)->color = (int)i; 01733 _contours.create((int)c->total, 1, CV_32SC2, i, true); 01734 Mat ci = _contours.getMat(i); 01735 CV_Assert( ci.isContinuous() ); 01736 cvCvtSeqToArray(c, ci.ptr()); 01737 } 01738 01739 if( _hierarchy.needed() ) 01740 { 01741 _hierarchy.create(1, total, CV_32SC4, -1, true); 01742 Vec4i * hierarchy = _hierarchy.getMat().ptr<Vec4i >(); 01743 01744 it = all_contours.begin(); 01745 for( i = 0; i < total; i++, ++it ) 01746 { 01747 CvSeq* c = *it; 01748 int h_next = c->h_next ? ((CvContour*)c->h_next)->color : -1; 01749 int h_prev = c->h_prev ? ((CvContour*)c->h_prev)->color : -1; 01750 int v_next = c->v_next ? ((CvContour*)c->v_next)->color : -1; 01751 int v_prev = c->v_prev ? ((CvContour*)c->v_prev)->color : -1; 01752 hierarchy[i] = Vec4i (h_next, h_prev, v_next, v_prev); 01753 } 01754 } 01755 } 01756 01757 void cv::findContours( InputOutputArray _image, OutputArrayOfArrays _contours, 01758 int mode, int method, Point offset) 01759 { 01760 findContours(_image, _contours, noArray(), mode, method, offset); 01761 } 01762 01763 /* End of file. */ 01764
Generated on Tue Jul 12 2022 14:46:26 by
1.7.2