OpenCV源码解析之findContours

待我称王封你为后i 2022-04-05 12:25 423阅读 0赞

说明：openCv的contours是分级的，其寻边理论依据（方式）参考suzuki的论文《Topological structural analysis of digitized binary images by border following》。

## Contour 的寻边模式 Mode ##

openCV通过一个矩阵来管理等级，矩阵的元素表示方法是：**\[Next, Previous, First\_Child, Parent\]**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70][]**

**RETR\_LIST**：列出所有的边，没有父子层级之分（全部边缘都为１级）。  
在这种模式下，这８条边建立的等级关系为  
\[ 1, -1, -1, -1\],　\[ 2, 0, -1, -1\],　　\[ 3, 1, -1, -1\],　　\[ 4, 2, -1, -1\],　　  
\[ 5, 3, -1, -1\],　\[ 6, 4, -1, -1\],　\[ 7, 5, -1, -1\],　\[-1, 6, -1, -1\]  
例如边“０”，其同等级的Next是边“１”，前一个不存在(-1)，没有First\_Child, Parent，这两个参数也都设为-1，所以第０个元素是  
\[1,-1,-1,-1\]；边“１”，其同等级的Next是边“２”，前一个边是“０”，没有First\_Child, Parent，两个-1，所以第１个元素是\[２,0,-1,-1\]；依次类推。

**RETR\_EXTERNAL**：列出最外面的边（如物体的外边框），不管被包围的内环或边（如物体的孔洞）。

**RETR\_CCOMP**：只取２个层级的边，如下图，只把边（粉红色）分为两个层（绿色），标记为绿色的(1)顶层和(2)次层。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70 1][]

上面图中，这９条边建立的等级关系为  
\[ 3, -1, 1, -1\],    \[ 2, -1, -1, 0\],    \[-1, 1, -1, 0\],    \[ 5, 0, 4, -1\],    \[-1, -1, -1, 3\],  
\[ 7, 3, 6, -1\],    \[-1, -1, -1, 5\],    \[ 8, 5, -1, -1\],    \[-1, 7, -1, -1\]  
例如第"0"边，其相邻的Next是边"3", Previous不存在(-1)，First-child=边"1"，Parent不存在(-1)，所以其相应的元素为  
\[3, -1, 1, -1\]，其余元素依此规则类推。

**RETR\_TREE**：返回所有的边及层级关系，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70 2][]

这９条边建立的等级关系为  
\[ 7, -1, 1, -1\],    \[-1, -1, 2, 0\],    \[-1, -1, 3, 1\],    \[-1, -1, 4, 2\],    \[-1, -1, 5, 3\],  
\[ 6, -1, -1, 4\],    \[-1, 5, -1, 4\],    \[ 8, 0, -1, -1\],   \[-1, 7, -1, -1\]

**注意cvDrawContours**

findContours往往和drawContours配合使用，  
cvDrawContours 函数第5个参数为 max\_level，等级的含义，从前面可以知道，只有提取有等级的轮廓时候（提取模式设为 CV\_RETR\_CCOMP或CV\_RETR\_TREE）这个参数才有意义。

**MAX\_SIZE**   
staticconstint MAX\_SIZE = 16;  
MAX\_SIZE=16是为了节省计算量。因为在最差的情况下，向左或向右旋转遍历(x,y)周边的８个像素时（如下图所示），８连通需要计算８次，如果采用最大值是８，则每次都要采用计算更大的越界检查来判断序号是否在0~7之间。

**CV\_INIT\_3X3\_DELTAS**  
/\* initializes 8-element array for fast access to 3x3 neighborhood of a pixel \*/  
\#defineCV\_INIT\_3X3\_DELTAS( deltas, step, nch ) \\  
((deltas)\[0\] = (nch), (deltas)\[1\] = -(step) + (nch), \\  
(deltas)\[2\] = -(step), (deltas)\[3\] = -(step) - (nch), \\  
(deltas)\[4\] = -(nch), (deltas)\[5\] = (step) - (nch), \\  
(deltas)\[6\] = (step), (deltas)\[7\] = (step) + (nch))  
CV\_INIT\_3X3\_DELTAS是完成下面这个偏移量计算的，比如点a(x,y)到b(x+1,y)，此时对应deltas(0)，即在内存中，假设已经知道了a点的位置，直接使用b=a+deltas(0)即可得到b点的序号。nch是偏移步进距离，这里是１，如果是２就会对应更外面一层，如图中黄色层。

![20181212161126161.png][]

**icvCodeDeltas**  
staticconstCvPoint icvCodeDeltas\[8\] =  
\{ CvPoint(1, 0), CvPoint(1, -1), CvPoint(0, -1), CvPoint(-1, -1), CvPoint(-1, 0), CvPoint(-1, 1), CvPoint(0, 1), CvPoint(1, 1) \};  
icvCodeDeltas 描述的是下面这个关系，对照上图序号，比如icvCodeDeltas(序号0).x = 1, icvCodeDeltas(序号0).y = 0,　表示在图片中序号为０的像素相对于中心像素（x,y）的相对位置偏移量为(1,0)。

![20181212161300673.png][]

**参数**  
\- nbd, number of border

**源码**

static void
    icvFetchContourEx( schar*               ptr,
                       int                  step,
                       CvPoint              pt,
                       CvSeq*               contour,
                       int  _method,
                       int                  nbd,
                       CvRect*              _rect )
    {
        int         deltas[MAX_SIZE];
        CvSeqWriter writer;
        schar        *i0 = ptr, *i1, *i3, *i4 = NULL;
        CvRect      rect;
        int         prev_s = -1, s, s_end;
        int         method = _method - 1;
    
        CV_DbgAssert( (unsigned) _method <= CV_CHAIN_APPROX_SIMPLE );
        CV_DbgAssert( 1 < nbd && nbd < 128 );
    
        /* initialize local state */
        CV_INIT_3X3_DELTAS( deltas, step, 1 );
        memcpy( deltas + 8, deltas, 8 * sizeof( deltas[0] ));
    
        /* initialize writer */
        cvStartAppendToSeq( contour, &writer );
    
        if( method < 0 )
            ((CvChain *)contour)->origin = pt;
    
        rect.x = rect.width = pt.x;
        rect.y = rect.height = pt.y;
    
        s_end = s = CV_IS_SEQ_HOLE( contour ) ? 0 : 4;  // hole从quad ０开始，外边界从quad ４开始
    
        do
        {
            s = (s - 1) & 7;
            i1 = i0 + deltas[s];
        }
        while( *i1 == 0 && s != s_end );
    
        if( s == s_end )            /* single pixel domain */
        {
            *i0 = (schar) (nbd | 0x80);
            if( method >= 0 )
            {
                CV_WRITE_SEQ_ELEM( pt, writer );
            }
        }
        else
        {
            i3 = i0;
    
            prev_s = s ^ 4;
    
            /* follow border */
            for( ;; )
            {
                CV_Assert(i3 != NULL);
                s_end = s;
                s = std::min(s, MAX_SIZE - 1);
    
                while( s < MAX_SIZE - 1 )
                {
                    i4 = i3 + deltas[++s];
                    CV_Assert(i4 != NULL);
                    if( *i4 != 0 )
                        break;
                }
                s &= 7;
    
                /* check "right" bound */
                if( (unsigned) (s - 1) < (unsigned) s_end ) // 该条件表示，外轮廓最右边的标记改为NBD的负值。
                {　// 这个条件是为了避免轮廓右边的部分被再次当做初始点。遇到负值的像素点是不判断它是否为一个新轮廓的起始点的，确保一个轮廓只扫描一次。
                    *i3 = (schar) (nbd | 0x80);
                }
                else if( *i3 == 1 )
                {
                    *i3 = (schar) nbd;
                }
    
                if( method < 0 )
                {
                    schar _s = (schar) s;
                    CV_WRITE_SEQ_ELEM( _s, writer );
                }
                else if( s != prev_s || method == 0 )
                {
                    CV_WRITE_SEQ_ELEM( pt, writer );
                }
    
                if( s != prev_s )
                {
                    /* update bounds */
                    if( pt.x < rect.x )
                        rect.x = pt.x;
                    else if( pt.x > rect.width )
                        rect.width = pt.x;
    
                    if( pt.y < rect.y )
                        rect.y = pt.y;
                    else if( pt.y > rect.height )
                        rect.height = pt.y;
                }
    
                prev_s = s;
                pt.x += icvCodeDeltas[s].x;
                pt.y += icvCodeDeltas[s].y;
    
                if( i4 == i0 && i3 == i1 )  break;
    
                i3 = i4;
                s = (s + 4) & 7;
            }                       /* end of border following loop */
        }
    
        rect.width -= rect.x - 1;
        rect.height -= rect.y - 1;
    
        cvEndWriteSeq( &writer );
    
        if( _method != CV_CHAIN_CODE )
            ((CvContour*)contour)->rect = rect;
    
        CV_DbgAssert( (writer.seq->total == 0 && writer.seq->first == 0) ||
                writer.seq->total > writer.seq->first->count ||
                (writer.seq->first->prev == writer.seq->first &&
                 writer.seq->first->next == writer.seq->first) );
    
        if( _rect )  *_rect = rect;
    }

未完待续……

参考  
\[１\]　[https://docs.opencv.org/trunk/d9/d8b/tutorial\_py\_contours\_hierarchy.html][https_docs.opencv.org_trunk_d9_d8b_tutorial_py_contours_hierarchy.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70]: /images/20220405/90e190259a9c42a291d68c11b4db1f54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70 1]: /images/20220405/bd880e7233ea46ab9b24ce8301572d14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhbm14MjE5_size_16_color_FFFFFF_t_70 2]: /images/20220405/ca9b1a7b12e540adaca75978e653fb73.png
[20181212161126161.png]: /images/20220405/a353f2ab5e514f78a946a9e4dce298fa.png
[20181212161300673.png]: /images/20220405/feeb1d74f957437db08df9673b24b9d3.png
[https_docs.opencv.org_trunk_d9_d8b_tutorial_py_contours_hierarchy.html]: https://docs.opencv.org/trunk/d9/d8b/tutorial_py_contours_hierarchy.html