1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
41 #include "precomp.hpp"
43 typedef struct _CvRGBf
50 typedef struct _CvRect16u
52 ushort x1, y1, x2, y2;
56 typedef struct _CvPyramid
61 _CvRect16u rect; /* ROI for the connected component */
64 /* element of base layer */
65 typedef struct _CvPyramidBase
72 typedef struct _CvPyramidC3
75 struct _CvPyramidC3 *p;
77 _CvRect16u rect; /* ROI for the connected component */
80 /* element of base layer */
81 typedef struct _CvPyramidBaseC3
84 struct _CvPyramidC3 *p;
88 typedef struct _CvListNode
90 struct _CvListNode* next;
96 static CvStatus icvSegmentClusterC1( CvSeq* cmp_seq, CvSeq* res_seq,
98 _CvPyramid* first_level_end,
99 CvSize first_level_size );
101 static CvStatus icvSegmentClusterC3( CvSeq* cmp_seq, CvSeq* res_seq,
103 _CvPyramidC3* first_level_end,
104 CvSize first_level_size );
106 typedef void (CV_CDECL * CvWriteNodeFunction)(void* seq,void* node);
108 static CvStatus icvUpdatePyrLinks_8u_C1
109 (int layer, void *layer_data, CvSize size, void *parent_layer,
110 void *_writer, float threshold, int is_last_iter, void *_stub, CvWriteNodeFunction /*func*/);
112 static CvStatus icvUpdatePyrLinks_8u_C3
113 (int layer, void *layer_data, CvSize size, void *parent_layer,
114 void *_writer, float threshold, int is_last_iter, void *_stub, CvWriteNodeFunction /*func*/);
116 static void icvMaxRoi( _CvRect16u *max_rect, _CvRect16u* cur_rect );
117 static void icvMaxRoi1( _CvRect16u *max_rect, int x, int y );
120 #define _CV_CHECK( icvFun ) \
122 if( icvFun != CV_OK ) \
127 #define _CV_MAX3( a, b, c) ((a)>(b) ? ((a)>(c) ? (a) : (c)) : ((b)>(c) ? (b) : (c)))
129 /*#define _CV_RGB_DIST(a, b) _CV_MAX3((float)fabs((a).red - (b).red), \
130 (float)fabs((a).green - (b).green), \
131 (float)fabs((a).blue - (b).blue))*/
133 #define _CV_NEXT_BASE_C1(p,n) (_CvPyramid*)((char*)(p) + (n)*sizeof(_CvPyramidBase))
134 #define _CV_NEXT_BASE_C3(p,n) (_CvPyramidC3*)((char*)(p) + (n)*sizeof(_CvPyramidBaseC3))
137 CV_INLINE float icvRGBDist_Max( const _CvRGBf& a, const _CvRGBf& b )
139 float tr = (float)fabs(a.red - b.red);
140 float tg = (float)fabs(a.green - b.green);
141 float tb = (float)fabs(a.blue - b.blue);
143 return _CV_MAX3( tr, tg, tb );
146 CV_INLINE float icvRGBDist_Sum( const _CvRGBf& a, const _CvRGBf& b )
148 float tr = (float)fabs(a.red - b.red);
149 float tg = (float)fabs(a.green - b.green);
150 float tb = (float)fabs(a.blue - b.blue);
152 return (tr + tg + tb);
156 #define _CV_RGB_DIST icvRGBDist_Max
157 #define _CV_RGB_THRESH_SCALE 1
159 #define _CV_RGB_DIST icvRGBDist_Sum
160 #define _CV_RGB_THRESH_SCALE 3
163 #define _CV_INV_TAB_SIZE 32
165 static const float icvInvTab[ /*_CV_INV_TAB_SIZE*/ ] =
167 1.00000000f, 0.50000000f, 0.33333333f, 0.25000000f, 0.20000000f, 0.16666667f,
168 0.14285714f, 0.12500000f, 0.11111111f, 0.10000000f, 0.09090909f, 0.08333333f,
169 0.07692308f, 0.07142857f, 0.06666667f, 0.06250000f, 0.05882353f, 0.05555556f,
170 0.05263158f, 0.05000000f, 0.04761905f, 0.04545455f, 0.04347826f, 0.04166667f,
171 0.04000000f, 0.03846154f, 0.03703704f, 0.03571429f, 0.03448276f, 0.03333333f,
172 0.03225806f, 0.03125000f
176 icvWritePyrNode( void *elem, void *writer )
178 CV_WRITE_SEQ_ELEM( *(_CvListNode *) elem, *(CvSeqWriter *) writer );
183 icvPyrSegmentation8uC1R( uchar * src_image, int src_step,
184 uchar * dst_image, int dst_step,
185 CvSize roi, int filter,
186 CvSeq ** dst_comp, CvMemStorage * storage,
187 int level, int threshold1, int threshold2 )
191 const int max_iter = 3; /* maximum number of iterations */
192 int cur_iter = 0; /* current iteration */
194 _CvPyramid *pyram[16]; /* pointers to the pyramid down up to level */
200 _CvPyramidBase *p_base;
201 _CvListNode cmp_node;
205 CvMemStorage *temp_storage = 0;
215 /* clear pointer to resultant sequence */
220 if( !src_image || !dst_image || !storage || !dst_comp )
221 return CV_NULLPTR_ERR;
222 if( roi.width <= 0 || roi.height <= 0 || src_step < roi.width || dst_step < roi.width )
223 return CV_BADSIZE_ERR;
224 if( filter != CV_GAUSSIAN_5x5 )
225 return CV_BADRANGE_ERR;
226 if( threshold1 < 0 || threshold2 < 0 )
227 return CV_BADRANGE_ERR;
229 return CV_BADRANGE_ERR;
231 if( ((roi.width | roi.height) & ((1 << level) - 1)) != 0 )
232 return CV_BADCOEF_ERR;
234 temp_storage = cvCreateChildMemStorage( storage );
236 /* sequence for temporary components */
237 cmp_seq = cvCreateSeq( 0, sizeof( CvSeq ), sizeof( _CvListNode ), temp_storage );
238 assert( cmp_seq != 0 );
240 res_seq = cvCreateSeq( CV_SEQ_CONNECTED_COMP, sizeof( CvSeq ),
241 sizeof( CvConnectedComp ), storage );
242 assert( res_seq != 0 );
244 /* calculate buffer size */
245 buffer_size = roi.width * roi.height * (sizeof( float ) + sizeof( _CvPyramidBase ));
247 for( l = 1; l <= level; l++ )
248 buffer_size += ((roi.width >> l) + 1) * ((roi.height >> l) + 1) * sizeof(_CvPyramid);
250 /* allocate buffer */
251 buffer = (char *) cvAlloc( buffer_size );
254 status = CV_OUTOFMEM_ERR;
258 pyramida = (float *) buffer;
260 /* initialization pyramid-linking properties down up to level */
261 step = roi.width * sizeof( float );
266 cvInitMatHeader( &_src, roi.height, roi.width, CV_8UC1, src_image, src_step );
267 cvInitMatHeader( &_pyramida, roi.height, roi.width, CV_32FC1, pyramida, step );
268 cvConvert( &_src, &_pyramida );
269 /*_CV_CHECK( icvCvtTo_32f_C1R( src_image, src_step, pyramida, step, roi, CV_8UC1 ));*/
271 p_base = (_CvPyramidBase *) (buffer + step * roi.height);
272 pyram[0] = (_CvPyramid *) p_base;
274 /* fill base level of pyramid */
275 for( i = 0; i < roi.height; i++ )
277 for( j = 0; j < roi.width; j++, p_base++ )
279 p_base->c = pyramida[i * roi.width + j];
284 p_cur = (_CvPyramid *) p_base;
287 /* calculate initial pyramid */
288 for( l = 1; l <= level; l++ )
290 CvSize dst_size(size.width/2+1, size.height/2+1);
291 CvMat prev_level = cvMat( size.height, size.width, CV_32FC1 );
292 CvMat next_level = cvMat( dst_size.height, dst_size.width, CV_32FC1 );
294 cvSetData( &prev_level, pyramida, step );
295 cvSetData( &next_level, pyramida, step );
296 cvPyrDown( &prev_level, &next_level );
298 //_CV_CHECK( icvPyrDown_Gauss5x5_32f_C1R( pyramida, step, pyramida, step, size, buff ));
299 //_CV_CHECK( icvPyrDownBorder_32f_CnR( pyramida, step, size, pyramida, step, dst_size, 1 ));
302 size.width = dst_size.width - 1;
303 size.height = dst_size.height - 1;
306 for( i = 0; i <= size.height; i++ )
308 for( j = 0; j <= size.width; j++, p_cur++ )
310 p_cur->c = pyramida[i * roi.width + j];
318 cvStartAppendToSeq( cmp_seq, &writer );
320 /* do several iterations to determine son-father links */
321 for( cur_iter = 0; cur_iter < max_iter; cur_iter++ )
323 int is_last_iter = cur_iter == max_iter - 1;
327 /* build son-father links down up to level */
328 for( l = 0; l < level; l++ )
330 icvUpdatePyrLinks_8u_C1( l, pyram[l], size, pyram[l + 1], &writer,
331 (float) threshold1, is_last_iter, &stub,
334 /* clear last border row */
337 p_cur = pyram[l] + (size.width + 1) * size.height;
338 for( j = 0; j <= size.width; j++ )
346 /* clear the old c value for the last level */
347 p_cur = pyram[level];
348 for( i = 0; i <= size.height; i++, p_cur += size.width + 1 )
349 for( j = 0; j <= size.width; j++ )
355 /* calculate average c value for the 0 < l <=level */
356 for( l = 0; l < level; l++, step = (step >> 1) + 1 )
358 _CvPyramid *p_prev, *p_row_prev;
362 /* calculate average c value for the next level */
365 p_base = (_CvPyramidBase *) pyram[0];
366 for( i = 0; i < roi.height; i++, p_base += size.width )
368 for( j = 0; j < size.width; j += 2 )
370 _CvPyramid *p1 = p_base[j].p;
371 _CvPyramid *p2 = p_base[j + 1].p;
373 p1->c += p_base[j].c;
374 p2->c += p_base[j + 1].c;
381 for( i = 0; i < size.height; i++, p_cur += size.width + 1 )
383 for( j = 0; j < size.width; j += 2 )
385 _CvPyramid *p1 = p_cur[j].p;
386 _CvPyramid *p2 = p_cur[j + 1].p;
388 float t0 = (float) p_cur[j].a * p_cur[j].c;
389 float t1 = (float) p_cur[j + 1].a * p_cur[j + 1].c;
395 p_cur[j].a = p_cur[j + 1].a = 0;
398 p_cur[size.width].a = 0;
402 for( j = 0; j <= size.width; j++ )
409 /* assign random values of the next level null c */
410 p_cur = pyram[l + 1];
411 p_row_prev = p_prev = pyram[l];
416 for( i = 0; i <= size.height; i++, p_cur += size.width + 1 )
418 if( i < size.height || !is_last_iter )
420 for( j = 0; j < size.width; j++ )
426 if( a <= _CV_INV_TAB_SIZE )
428 p_cur[j].c *= icvInvTab[a - 1];
437 p_cur[j].c = p_prev->c;
441 p_prev = _CV_NEXT_BASE_C1(p_prev,2);
446 if( p_cur[size.width].a == 0 )
448 p_cur[size.width].c = p_prev[(l != 0) - 1].c;
452 p_cur[size.width].c /= p_cur[size.width].a;
455 cmp_node.data = p_cur + size.width;
456 CV_WRITE_SEQ_ELEM( cmp_node, writer );
462 for( j = 0; j <= size.width; j++ )
468 if( a <= _CV_INV_TAB_SIZE )
470 p_cur[j].c *= icvInvTab[a - 1];
477 cmp_node.data = p_cur + j;
478 CV_WRITE_SEQ_ELEM( cmp_node, writer );
482 p_cur[j].c = p_prev->c;
487 p_prev = _CV_NEXT_BASE_C1(p_prev, (j * 2 < step - 2 ? 2 : 1));
496 if( l + 1 == level && !is_last_iter )
497 for( j = 0; j <= size.width; j++ )
506 p_prev = (_CvPyramid*)((char*)p_row_prev + step *
507 (l == 0 ? sizeof(_CvPyramidBase) : sizeof(_CvPyramid)));
511 } /* end of the iteration process */
513 /* construct a connected components */
514 size.width = roi.width >> level;
515 size.height = roi.height >> level;
517 p_cur = pyram[level];
519 for( i = 0; i < size.height; i++, p_cur += size.width + 1 )
521 for( j = 0; j < size.width; j++ )
523 if( p_cur[j].a != 0 )
525 cmp_node.data = p_cur + j;
526 CV_WRITE_SEQ_ELEM( cmp_node, writer );
531 cvEndWriteSeq( &writer );
533 /* clusterization segmented components and construction
534 output connected components */
535 icvSegmentClusterC1( cmp_seq, res_seq, threshold2, pyram[1], roi );
537 /* convert (inplace) resultant segment values to int (top level) */
539 /* propagate segment values top down */
540 for( l = level - 1; l >= 0; l-- )
553 for( i = 0; i <= size.height; i++ )
555 for( j = 0; j <= size.width; j++ )
557 _CvPyramid *p = p_cur->p;
566 /* copy the segmented values to destination image */
567 _c.f = p_cur->c; dst_image[j] = (uchar)_c.i;
568 p_cur = _CV_NEXT_BASE_C1(p_cur, 1);
576 dst_image += dst_step;
582 cvReleaseMemStorage( &temp_storage );
584 if( status == CV_OK )
592 /****************************************************************************************\
593 color!!! image segmentation by pyramid-linking
594 \****************************************************************************************/
596 icvPyrSegmentation8uC3R( uchar * src_image, int src_step,
597 uchar * dst_image, int dst_step,
598 CvSize roi, int filter,
599 CvSeq ** dst_comp, CvMemStorage * storage,
600 int level, int threshold1, int threshold2 )
605 const int max_iter = 3; /* maximum number of iterations */
606 int cur_iter = 0; /* current iteration */
608 _CvPyramidC3 *pyram[16]; /* pointers to the pyramid down up to level */
614 _CvPyramidBaseC3 *p_base;
615 _CvListNode cmp_node;
619 CvMemStorage *temp_storage = 0;
629 threshold1 *= _CV_RGB_THRESH_SCALE;
630 threshold2 *= _CV_RGB_THRESH_SCALE;
632 /* clear pointer to resultant sequence */
637 if( !src_image || !dst_image || !storage || !dst_comp )
638 return CV_NULLPTR_ERR;
639 if( roi.width <= 0 || roi.height <= 0 ||
640 src_step < roi.width * 3 || dst_step < roi.width * 3 ) return CV_BADSIZE_ERR;
641 if( filter != CV_GAUSSIAN_5x5 )
642 return CV_BADRANGE_ERR;
643 if( threshold1 < 0 || threshold2 < 0 )
644 return CV_BADRANGE_ERR;
646 return CV_BADRANGE_ERR;
648 if( ((roi.width | roi.height) & ((1 << level) - 1)) != 0 )
649 return CV_BADCOEF_ERR;
651 temp_storage = cvCreateChildMemStorage( storage );
653 /* sequence for temporary components */
654 cmp_seq = cvCreateSeq( 0, sizeof( CvSeq ), sizeof( _CvListNode ), temp_storage );
655 assert( cmp_seq != 0 );
657 res_seq = cvCreateSeq( CV_SEQ_CONNECTED_COMP, sizeof( CvSeq ),
658 sizeof( CvConnectedComp ), storage );
659 assert( res_seq != 0 );
661 /* calculate buffer size */
662 buffer_size = roi.width * roi.height * (sizeof( _CvRGBf ) + sizeof( _CvPyramidBaseC3 ));
664 for( l = 1; l <= level; l++ )
665 buffer_size += ((roi.width >> l) + 1) * ((roi.height >> l) + 1) * sizeof(_CvPyramidC3);
667 /* allocate buffer */
668 buffer = (char *) cvAlloc( buffer_size );
671 status = CV_OUTOFMEM_ERR;
675 pyramida = (float *) buffer;
677 /* initialization pyramid-linking properties down up to level */
678 step = roi.width * sizeof( _CvRGBf );
683 cvInitMatHeader( &_src, roi.height, roi.width, CV_8UC3, src_image, src_step );
684 cvInitMatHeader( &_pyramida, roi.height, roi.width, CV_32FC3, pyramida, step );
685 cvConvert( &_src, &_pyramida );
686 /*_CV_CHECK( icvCvtTo_32f_C1R( src_image, src_step, pyramida, step,
687 cvSize( roi.width * 3, roi.height ), CV_8UC1 ));*/
690 p_base = (_CvPyramidBaseC3 *) (buffer + step * roi.height);
691 pyram[0] = (_CvPyramidC3 *) p_base;
693 /* fill base level of pyramid */
694 for( i = 0; i < roi.height; i++ )
696 for( j = 0; j < roi.width; j++, p_base++ )
698 p_base->c = ((_CvRGBf *) pyramida)[i * roi.width + j];
703 p_cur = (_CvPyramidC3 *) p_base;
706 /* calculate initial pyramid */
707 for( l = 1; l <= level; l++ )
709 CvSize dst_size(size.width/2 + 1, size.height/2 + 1);
710 CvMat prev_level = cvMat( size.height, size.width, CV_32FC3 );
711 CvMat next_level = cvMat( dst_size.height, dst_size.width, CV_32FC3 );
713 cvSetData( &prev_level, pyramida, step );
714 cvSetData( &next_level, pyramida, step );
715 cvPyrDown( &prev_level, &next_level );
717 //_CV_CHECK( icvPyrDown_Gauss5x5_32f_C3R( pyramida, step, pyramida, step, size, buff ));
718 //_CV_CHECK( icvPyrDownBorder_32f_CnR( pyramida, step, size, pyramida, step, dst_size, 3 ));
721 size.width = dst_size.width - 1;
722 size.height = dst_size.height - 1;
725 for( i = 0; i <= size.height; i++ )
727 assert( (char*)p_cur - buffer < buffer_size );
728 for( j = 0; j <= size.width; j++, p_cur++ )
730 p_cur->c = ((_CvRGBf *) pyramida)[i * roi.width + j];
738 cvStartAppendToSeq( cmp_seq, &writer );
740 /* do several iterations to determine son-father links */
741 for( cur_iter = 0; cur_iter < max_iter; cur_iter++ )
743 int is_last_iter = cur_iter == max_iter - 1;
747 /* build son-father links down up to level */
748 for( l = 0; l < level; l++ )
750 icvUpdatePyrLinks_8u_C3( l, pyram[l], size, pyram[l + 1], &writer,
751 (float) threshold1, is_last_iter, &stub,
754 /* clear last border row */
757 p_cur = pyram[l] + (size.width + 1) * size.height;
758 for( j = 0; j <= size.width; j++ )
759 p_cur[j].c.blue = p_cur[j].c.green = p_cur[j].c.red = 0;
766 /* clear the old c value for the last level */
767 p_cur = pyram[level];
768 for( i = 0; i <= size.height; i++, p_cur += size.width + 1 )
769 for( j = 0; j <= size.width; j++ )
770 p_cur[j].c.blue = p_cur[j].c.green = p_cur[j].c.red = 0;
775 /* calculate average c value for the 0 < l <=level */
776 for( l = 0; l < level; l++, step = (step >> 1) + 1 )
778 _CvPyramidC3 *p_prev, *p_row_prev;
780 stub.c.blue = stub.c.green = stub.c.red = 0;
782 /* calculate average c value for the next level */
785 p_base = (_CvPyramidBaseC3 *) pyram[0];
786 for( i = 0; i < roi.height; i++, p_base += size.width )
788 for( j = 0; j < size.width; j++ )
790 _CvPyramidC3 *p = p_base[j].p;
792 p->c.blue += p_base[j].c.blue;
793 p->c.green += p_base[j].c.green;
794 p->c.red += p_base[j].c.red;
801 for( i = 0; i < size.height; i++, p_cur += size.width + 1 )
803 for( j = 0; j < size.width; j++ )
805 _CvPyramidC3 *p = p_cur[j].p;
806 float a = (float) p_cur[j].a;
808 p->c.blue += a * p_cur[j].c.blue;
809 p->c.green += a * p_cur[j].c.green;
810 p->c.red += a * p_cur[j].c.red;
816 p_cur[size.width].a = 0;
820 for( j = 0; j <= size.width; j++ )
827 /* assign random values of the next level null c */
828 p_cur = pyram[l + 1];
829 p_row_prev = p_prev = pyram[l];
834 for( i = 0; i <= size.height; i++, p_cur += size.width + 1 )
836 if( i < size.height || !is_last_iter )
838 for( j = 0; j < size.width; j++ )
846 if( a <= _CV_INV_TAB_SIZE )
848 inv_a = icvInvTab[a - 1];
854 p_cur[j].c.blue *= inv_a;
855 p_cur[j].c.green *= inv_a;
856 p_cur[j].c.red *= inv_a;
860 p_cur[j].c = p_prev->c;
864 p_prev = _CV_NEXT_BASE_C3( p_prev, 2 );
869 if( p_cur[size.width].a == 0 )
871 p_cur[size.width].c = p_prev[(l != 0) - 1].c;
875 p_cur[size.width].c.blue /= p_cur[size.width].a;
876 p_cur[size.width].c.green /= p_cur[size.width].a;
877 p_cur[size.width].c.red /= p_cur[size.width].a;
880 cmp_node.data = p_cur + size.width;
881 CV_WRITE_SEQ_ELEM( cmp_node, writer );
887 for( j = 0; j <= size.width; j++ )
895 if( a <= _CV_INV_TAB_SIZE )
897 inv_a = icvInvTab[a - 1];
903 p_cur[j].c.blue *= inv_a;
904 p_cur[j].c.green *= inv_a;
905 p_cur[j].c.red *= inv_a;
907 cmp_node.data = p_cur + j;
908 CV_WRITE_SEQ_ELEM( cmp_node, writer );
912 p_cur[j].c = p_prev->c;
917 p_prev = _CV_NEXT_BASE_C3( p_prev, (j * 2 < step - 2 ? 2 : 1));
926 if( l + 1 == level && !is_last_iter )
927 for( j = 0; j <= size.width; j++ )
936 p_prev = (_CvPyramidC3*)((char*)p_row_prev + step *
937 (l == 0 ? sizeof( _CvPyramidBaseC3 ) : sizeof( _CvPyramidC3 )));
941 } /* end of the iteration process */
943 /* construct a connected components */
944 size.width = roi.width >> level;
945 size.height = roi.height >> level;
947 p_cur = pyram[level];
949 for( i = 0; i < size.height; i++, p_cur += size.width + 1 )
951 for( j = 0; j < size.width; j++ )
953 if( p_cur[j].a != 0 )
955 cmp_node.data = p_cur + j;
956 CV_WRITE_SEQ_ELEM( cmp_node, writer );
961 cvEndWriteSeq( &writer );
963 /* clusterization segmented components and construction
964 output connected components */
965 icvSegmentClusterC3( cmp_seq, res_seq, threshold2, pyram[1], roi );
967 /* convert (inplace) resultant segment values to int (top level) */
969 /* propagate segment values top down */
970 for( l = level - 1; l >= 0; l-- )
983 for( i = 0; i <= size.height; i++ )
985 for( j = 0; j <= size.width; j++ )
987 _CvPyramidC3 *p = p_cur->p;
998 /* copy the segmented values to destination image */
999 _c.f = p_cur->c.blue; dst_image[j*3] = (uchar)_c.i;
1000 _c.f = p_cur->c.green; dst_image[j*3+1] = (uchar)_c.i;
1001 _c.f = p_cur->c.red; dst_image[j*3+2] = (uchar)_c.i;
1002 p_cur = _CV_NEXT_BASE_C3(p_cur,1);
1010 dst_image += dst_step;
1017 cvReleaseMemStorage( &temp_storage );
1019 if( status == CV_OK )
1020 *dst_comp = res_seq;
1026 static CvStatus icvUpdatePyrLinks_8u_C1
1027 (int layer, void *layer_data, CvSize size, void *parent_layer,
1028 void *_writer, float threshold, int is_last_iter, void *_stub, CvWriteNodeFunction /*func*/)
1031 _CvListNode cmp_node;
1033 _CvPyramid *stub = (_CvPyramid *) _stub;
1034 _CvPyramid *p_cur = (_CvPyramid *) layer_data;
1035 _CvPyramid *p_next1 = (_CvPyramid *) parent_layer;
1036 _CvPyramid *p_next3 = p_next1 + (size.width >> 1) + 1;
1038 CvSeqWriter & writer = *(CvSeqWriter *) _writer;
1040 for( i = 0; i < size.height; i++ )
1042 for( j = 0; j < size.width; j += 2 )
1044 float c0, c1, c2, c3, c4;
1047 /* son-father threshold linking for the current node establish */
1050 /* find pointer for the first pixel */
1051 c1 = (float) fabs( c0 - p_next1[0].c );
1052 c2 = (float) fabs( c0 - p_next1[1].c );
1053 c3 = (float) fabs( c0 - p_next3[0].c );
1054 c4 = (float) fabs( c0 - p_next3[1].c );
1074 if( c1 <= threshold )
1081 p_cur = (_CvPyramid*)((char*)p_cur + sizeof(_CvPyramidBase));
1083 icvMaxRoi1( &(p->rect), j, i );
1092 if( is_last_iter && a != 0 )
1093 icvMaxRoi( &(p->rect), &(p_cur[-1].rect) );
1101 cmp_node.data = p_cur;
1102 CV_WRITE_SEQ_ELEM( cmp_node, writer );
1106 p_cur = _CV_NEXT_BASE_C1(p_cur,1);
1115 /* find pointer for the second pixel */
1118 c1 = (float) fabs( c0 - p_next1[0].c );
1119 c2 = (float) fabs( c0 - p_next1[1].c );
1120 c3 = (float) fabs( c0 - p_next3[0].c );
1121 c4 = (float) fabs( c0 - p_next3[1].c );
1144 if( c1 <= threshold )
1151 p_cur = _CV_NEXT_BASE_C1(p_cur,1);
1153 icvMaxRoi1( &(p->rect), j + 1, i );
1162 if( is_last_iter && a != 0 )
1163 icvMaxRoi( &(p->rect), &(p_cur[-1].rect) );
1171 cmp_node.data = p_cur;
1172 CV_WRITE_SEQ_ELEM( cmp_node, writer );
1176 p_cur = _CV_NEXT_BASE_C1(p_cur,1);
1195 p_next1 -= size.width >> 1;
1196 p_next3 -= size.width >> 1;
1209 static CvStatus icvUpdatePyrLinks_8u_C3
1210 (int layer, void *layer_data, CvSize size, void *parent_layer,
1211 void *_writer, float threshold, int is_last_iter, void *_stub, CvWriteNodeFunction /*func*/)
1214 _CvListNode cmp_node;
1216 _CvPyramidC3 *stub = (_CvPyramidC3 *) _stub;
1217 _CvPyramidC3 *p_cur = (_CvPyramidC3 *) layer_data;
1218 _CvPyramidC3 *p_next1 = (_CvPyramidC3 *) parent_layer;
1219 _CvPyramidC3 *p_next3 = p_next1 + (size.width >> 1) + 1;
1221 CvSeqWriter & writer = *(CvSeqWriter *) _writer;
1223 for( i = 0; i < size.height; i++ )
1225 for( j = 0; j < size.width; j += 2 )
1227 float c1, c2, c3, c4;
1230 /* find pointer for the first pixel */
1231 c1 = _CV_RGB_DIST( p_cur->c, p_next1[0].c );
1232 c2 = _CV_RGB_DIST( p_cur->c, p_next1[1].c );
1233 c3 = _CV_RGB_DIST( p_cur->c, p_next3[0].c );
1234 c4 = _CV_RGB_DIST( p_cur->c, p_next3[1].c );
1254 if( c1 < threshold )
1261 p_cur = _CV_NEXT_BASE_C3(p_cur,1);
1263 icvMaxRoi1( &(p->rect), j, i );
1270 p_cur->c.blue = p_cur->c.green = p_cur->c.red = 0;
1272 if( is_last_iter && a != 0 )
1273 icvMaxRoi( &(p->rect), &(p_cur[-1].rect) );
1279 if( is_last_iter /* && ( == 0 || p_cur->a != 0) */ )
1281 cmp_node.data = p_cur;
1282 CV_WRITE_SEQ_ELEM( cmp_node, writer );
1287 p_cur = _CV_NEXT_BASE_C3(p_cur,1);
1291 p_cur->c.blue = p_cur->c.green = p_cur->c.red = 0;
1296 /* find pointer for the second pixel */
1297 c1 = _CV_RGB_DIST( p_cur->c, p_next1[0].c );
1298 c2 = _CV_RGB_DIST( p_cur->c, p_next1[1].c );
1299 c3 = _CV_RGB_DIST( p_cur->c, p_next3[0].c );
1300 c4 = _CV_RGB_DIST( p_cur->c, p_next3[1].c );
1323 if( c1 < threshold )
1330 p_cur = _CV_NEXT_BASE_C3(p_cur,1);
1332 icvMaxRoi1( &(p->rect), j + 1, i );
1339 p_cur->c.blue = p_cur->c.green = p_cur->c.red = 0;
1341 if( is_last_iter && a != 0 )
1342 icvMaxRoi( &(p->rect), &(p_cur[-1].rect) );
1348 if( is_last_iter /* && ( == 0 || p_cur->a != 0) */ )
1350 cmp_node.data = p_cur;
1351 CV_WRITE_SEQ_ELEM( cmp_node, writer );
1355 p_cur = _CV_NEXT_BASE_C3(p_cur,1);
1359 p_cur->c.blue = p_cur->c.green = p_cur->c.red = 0;
1368 p_cur->c.blue = p_cur->c.green = p_cur->c.red = 0;
1374 p_next1 -= size.width >> 1;
1375 p_next3 -= size.width >> 1;
1389 /****************************************************************************************\
1391 clusterization segmented components
1393 \****************************************************************************************/
1395 icvExpandBaseLevelC1( _CvPyramid * base_p, _CvPyramid * p, _CvPyramidBase * start, int width )
1397 int x = (int)((_CvPyramidBase *) base_p - start);
1402 p->rect.x1 = (ushort) x;
1403 p->rect.y1 = (ushort) y;
1404 p->rect.x2 = (ushort) (x + 1);
1405 p->rect.y2 = (ushort) (y + 1);
1410 icvSegmentClusterC1( CvSeq * cmp_seq, CvSeq * res_seq,
1411 double threshold, _CvPyramid * first_level_end, CvSize first_level_size )
1413 const double eps = 1.;
1416 _CvPyramid temp_cmp;
1417 _CvPyramidBase *first_level_start = (_CvPyramidBase *) first_level_end -
1418 first_level_size.width * first_level_size.height;
1419 int c, i, count = cmp_seq->total;
1421 cvStartReadSeq( cmp_seq, &reader, 0 );
1422 cvStartAppendToSeq( res_seq, &writer );
1424 if( threshold < eps )
1426 /* if threshold is too small then simply copy all
1427 the components to the output sequence */
1428 for( i = 0; i < count; i++ )
1430 CvConnectedComp comp;
1431 _CvPyramid *cmp = (_CvPyramid *) (((_CvListNode *) reader.ptr)->data);
1434 if( cmp < first_level_end )
1436 icvExpandBaseLevelC1( cmp, &temp_cmp, first_level_start,
1437 first_level_size.width );
1441 _c.i = cvRound( cmp->c );
1443 comp.value = cvRealScalar(_c.i);
1445 comp.rect.x = cmp->rect.x1;
1446 comp.rect.y = cmp->rect.y1;
1447 comp.rect.width = cmp->rect.x2 - cmp->rect.x1;
1448 comp.rect.height = cmp->rect.y2 - cmp->rect.y1;
1451 CV_WRITE_SEQ_ELEM( comp, writer );
1452 CV_NEXT_SEQ_ELEM( sizeof( _CvListNode ), reader );
1457 _CvListNode stub_node;
1458 _CvListNode *prev = &stub_node;
1462 for( i = 0; i < count; i++ )
1464 _CvListNode *node = (_CvListNode *) reader.ptr;
1468 CV_NEXT_SEQ_ELEM( sizeof( _CvListNode ), reader );
1471 prev = stub_node.next;
1475 _CvListNode *node = prev->next;
1476 _CvListNode *acc = prev;
1477 _CvPyramid *cmp = (_CvPyramid *) (acc->data);
1478 CvConnectedComp comp;
1481 if( cmp < first_level_end )
1483 icvExpandBaseLevelC1( cmp, &temp_cmp, first_level_start,
1484 first_level_size.width );
1489 temp_cmp.c *= temp_cmp.a;
1498 cmp = (_CvPyramid *) (node->data);
1499 if( fabs( c0 - cmp->c ) < threshold )
1503 /* exclude from global list and add to list of joint component */
1504 prev->next = node->next;
1508 if( cmp < first_level_end )
1510 icvExpandBaseLevelC1( cmp, &temp, first_level_start,
1511 first_level_size.width );
1515 temp_cmp.a += cmp->a;
1516 temp_cmp.c += cmp->c * cmp->a;
1517 icvMaxRoi( &(temp_cmp.rect), &(cmp->rect) );
1521 if( prev == &stub_node )
1523 stub_node.next = node;
1530 if( temp_cmp.a != 0 )
1532 c = cvRound( temp_cmp.c / temp_cmp.a );
1543 cmp = (_CvPyramid *) (node->data);
1544 _c.i = c; cmp->c = _c.f;
1548 comp.value = cvRealScalar(c);
1549 comp.area = temp_cmp.a;
1550 comp.rect.x = temp_cmp.rect.x1;
1551 comp.rect.y = temp_cmp.rect.y1;
1552 comp.rect.width = temp_cmp.rect.x2 - temp_cmp.rect.x1;
1553 comp.rect.height = temp_cmp.rect.y2 - temp_cmp.rect.y1;
1556 CV_WRITE_SEQ_ELEM( comp, writer );
1557 prev = stub_node.next;
1561 cvEndWriteSeq( &writer );
1565 /****************************************************************************************\
1567 clusterization segmented components
1569 \****************************************************************************************/
1571 icvExpandBaseLevelC3( _CvPyramidC3 * base_p, _CvPyramidC3 * p,
1572 _CvPyramidBaseC3 * start, int width )
1574 int x = (int)((_CvPyramidBaseC3 *) base_p - start);
1579 p->rect.x1 = (ushort) x;
1580 p->rect.y1 = (ushort) y;
1581 p->rect.x2 = (ushort) (x + 1);
1582 p->rect.y2 = (ushort) (y + 1);
1587 icvSegmentClusterC3( CvSeq * cmp_seq, CvSeq * res_seq,
1589 _CvPyramidC3 * first_level_end, CvSize first_level_size )
1591 const double eps = 1.;
1594 _CvPyramidC3 temp_cmp;
1595 _CvPyramidBaseC3 *first_level_start = (_CvPyramidBaseC3 *) first_level_end -
1596 first_level_size.width * first_level_size.height;
1597 int i, count = cmp_seq->total;
1598 int c_blue, c_green, c_red;
1600 cvStartReadSeq( cmp_seq, &reader, 0 );
1601 cvStartAppendToSeq( res_seq, &writer );
1603 if( threshold < eps )
1605 /* if threshold is too small then simply copy all
1606 the components to the output sequence */
1607 for( i = 0; i < count; i++ )
1609 CvConnectedComp comp;
1610 _CvPyramidC3 *cmp = (_CvPyramidC3 *) (((_CvListNode *) reader.ptr)->data);
1613 if( cmp < first_level_end )
1615 icvExpandBaseLevelC3( cmp, &temp_cmp, first_level_start,
1616 first_level_size.width );
1620 c_blue = cvRound( cmp->c.blue );
1621 c_green = cvRound( cmp->c.green );
1622 c_red = cvRound( cmp->c.red );
1623 _c.i = c_blue; cmp->c.blue = _c.f;
1624 _c.i = c_green; cmp->c.green = _c.f;
1625 _c.i = c_red; cmp->c.red = _c.f;
1626 comp.value = cvScalar( c_blue, c_green, c_red );
1628 comp.rect.x = cmp->rect.x1;
1629 comp.rect.y = cmp->rect.y1;
1630 comp.rect.width = cmp->rect.x2 - cmp->rect.x1;
1631 comp.rect.height = cmp->rect.y2 - cmp->rect.y1;
1634 CV_WRITE_SEQ_ELEM( comp, writer );
1635 CV_NEXT_SEQ_ELEM( sizeof( _CvListNode ), reader );
1640 _CvListNode stub_node;
1641 _CvListNode *prev = &stub_node;
1645 for( i = 0; i < count; i++ )
1647 _CvListNode *node = (_CvListNode *) reader.ptr;
1651 CV_NEXT_SEQ_ELEM( sizeof( _CvListNode ), reader );
1654 prev = stub_node.next;
1658 _CvListNode *node = prev->next;
1659 _CvListNode *acc = prev;
1660 _CvPyramidC3 *cmp = (_CvPyramidC3 *) (acc->data);
1661 CvConnectedComp comp;
1662 _CvRGBf c0 = cmp->c;
1664 if( cmp < first_level_end )
1666 icvExpandBaseLevelC3( cmp, &temp_cmp, first_level_start,
1667 first_level_size.width );
1672 temp_cmp.c.blue *= temp_cmp.a;
1673 temp_cmp.c.green *= temp_cmp.a;
1674 temp_cmp.c.red *= temp_cmp.a;
1683 cmp = (_CvPyramidC3 *) (node->data);
1684 if( _CV_RGB_DIST( c0, cmp->c ) < threshold )
1688 /* exclude from global list and add to list of joint component */
1689 prev->next = node->next;
1693 if( cmp < first_level_end )
1695 icvExpandBaseLevelC3( cmp, &temp, first_level_start,
1696 first_level_size.width );
1700 temp_cmp.a += cmp->a;
1701 temp_cmp.c.blue += cmp->c.blue * cmp->a;
1702 temp_cmp.c.green += cmp->c.green * cmp->a;
1703 temp_cmp.c.red += cmp->c.red * cmp->a;
1704 icvMaxRoi( &(temp_cmp.rect), &(cmp->rect) );
1708 if( prev == &stub_node )
1710 stub_node.next = node;
1717 if( temp_cmp.a != 0 )
1719 c_blue = cvRound( temp_cmp.c.blue / temp_cmp.a );
1720 c_green = cvRound( temp_cmp.c.green / temp_cmp.a );
1721 c_red = cvRound( temp_cmp.c.red / temp_cmp.a );
1725 c_blue = cvRound( c0.blue );
1726 c_green = cvRound( c0.green );
1727 c_red = cvRound( c0.red );
1734 cmp = (_CvPyramidC3 *) (node->data);
1735 _c.i = c_blue; cmp->c.blue = _c.f;
1736 _c.i = c_green; cmp->c.green = _c.f;
1737 _c.i = c_red; cmp->c.red = _c.f;
1741 comp.value = cvScalar( c_blue, c_green, c_red );
1742 comp.area = temp_cmp.a;
1743 comp.rect.x = temp_cmp.rect.x1;
1744 comp.rect.y = temp_cmp.rect.y1;
1745 comp.rect.width = temp_cmp.rect.x2 - temp_cmp.rect.x1;
1746 comp.rect.height = temp_cmp.rect.y2 - temp_cmp.rect.y1;
1749 CV_WRITE_SEQ_ELEM( comp, writer );
1750 prev = stub_node.next;
1754 cvEndWriteSeq( &writer );
1758 /****************************************************************************************\
1760 definition of the maximum roi size
1762 \****************************************************************************************/
1764 icvMaxRoi( _CvRect16u * max_rect, _CvRect16u * cur_rect )
1766 if( max_rect->x2 == 0 )
1767 *max_rect = *cur_rect;
1770 if( max_rect->x1 > cur_rect->x1 )
1771 max_rect->x1 = cur_rect->x1;
1772 if( max_rect->y1 > cur_rect->y1 )
1773 max_rect->y1 = cur_rect->y1;
1775 if( max_rect->x2 < cur_rect->x2 )
1776 max_rect->x2 = cur_rect->x2;
1777 if( max_rect->y2 < cur_rect->y2 )
1778 max_rect->y2 = cur_rect->y2;
1783 icvMaxRoi1( _CvRect16u * max_rect, int x, int y )
1785 if( max_rect->x2 == 0 )
1787 max_rect->x1 = (ushort) x;
1788 max_rect->y1 = (ushort) y;
1793 max_rect->x2 = (ushort) x;
1794 max_rect->y2 = (ushort) y;
1798 if( max_rect->x1 > x )
1799 max_rect->x1 = (ushort) x;
1800 if( max_rect->y1 > y )
1801 max_rect->y1 = (ushort) y;
1806 if( max_rect->x2 < x )
1807 max_rect->x2 = (ushort) x;
1808 if( max_rect->y2 < y )
1809 max_rect->y2 = (ushort) y;
1814 /*F///////////////////////////////////////////////////////////////////////////////////////
1815 // Name: cvPyrSegmentation
1817 // segments an image using pyramid-linking technique
1820 // src - source image
1821 // dst - destination image
1822 // comp - pointer to returned connected component sequence
1823 // storage - where the sequence is stored
1824 // level - maximal pyramid level
1825 // threshold1 - first threshold, affecting on detalization level when pyramid
1827 // threshold2 - second threshold - affects on final components merging.
1830 // Source and destination image must be equal types and channels
1833 cvPyrSegmentation( IplImage * src,
1835 CvMemStorage * storage,
1836 CvSeq ** comp, int level, double threshold1, double threshold2 )
1838 CvSize src_size, dst_size;
1839 uchar *src_data = 0;
1840 uchar *dst_data = 0;
1841 int src_step = 0, dst_step = 0;
1842 int thresh1 = cvRound( threshold1 );
1843 int thresh2 = cvRound( threshold2 );
1845 if( src->depth != IPL_DEPTH_8U )
1846 CV_Error( CV_BadDepth, "Unsupported format" );
1848 if( src->depth != dst->depth || src->nChannels != dst->nChannels )
1849 CV_Error( CV_StsBadArg, "src and dst have different formats" );
1851 cvGetRawData( src, &src_data, &src_step, &src_size );
1852 cvGetRawData( dst, &dst_data, &dst_step, &dst_size );
1854 if( src_size.width != dst_size.width ||
1855 src_size.height != dst_size.height )
1856 CV_Error( CV_StsBadArg, "src and dst have different ROIs" );
1858 switch (src->nChannels)
1861 IPPI_CALL( icvPyrSegmentation8uC1R( src_data, src_step,
1865 comp, storage, level, thresh1, thresh2 ));
1868 IPPI_CALL( icvPyrSegmentation8uC3R( src_data, src_step,
1872 comp, storage, level, thresh1, thresh2 ));
1875 CV_Error( CV_BadNumChannels, "Unsupported format" );