OpenCV中轮廓提取函数findContours()实现的是这篇论文的算法：

论文解决的是对于二值图像的轮廓提取，本人读了一下论文，整理了一下算法思路，如有错误恳请指正。

frame（框架）：一张图片的最上行，最下行，最左列，最右列组成了这张图片的frame（框架）。例如一张图片宽为640，高为480，则这张图片的frame为第0行像素，第479行像素，第0列像素，第639列像素组成了这张图片的frame。

灰度值为0和1的像素分别称为0-pixel（0像素）和1-pixel（1像素）。论文假设frame是由0像素填充的。

(i,j) 表示图片中第i行，第j列的像素点。

f_{ij} 表示像素点(i,j)的灰度值。则一张图片可以表示为 F=\left\{ f_{ij} \right\} 。

由1像素组成的连通域称为1-component（1连通域），由0像素组成的连通域称为0-component（0连通域）。如果0连通域S包含了frame，那么S称为background（背景），否则称为孔洞。

4（8）连通场景：1像素是4（8）连通，0像素是8（4）连通。

4连通：两个像素p和q，如果q在p的4邻域中，称这两个像素是4连通

8连通：两个像素p和q，如果q在p的8邻域中，称这两个像素是8连通

border point(边界点)：在4（8）连通场景中，如果一个1像素(i,j)在它的8（4）连通域中有0像素(p,q)存在，那么这个1像素(i,j)就是一个border point。边界由许多个边界点构成。

surroundness among connected components（环绕连通域）：在一幅二值图像中有两个连通域S1和S2，如果S1中任何一个像素点从任何一个方向（4个方向）到达frame的路径上都存在S2的像素点，我们称S2环绕S1。如果S2环绕S1且S2和S1之间存在border point，那么我们称S2直接环绕S1。

outer border and hole border（外边界和孔边界）：假设现有1连通域S1,0连通域S2。如果S2直接环绕S1，则S2和S1之间的边界称为外边界；如果S1直接环绕S2，则S2和S1之间的边缘称为孔边界。注意不管是外边界还是孔边界都是由1像素组成。

parent border（父边界）：假设现有1连通域S1和S3,0连通域S2，S2直接环绕S1，S3直接环绕S2，S1与S2之间的边界为B1，S2与S3之间的边界为B2，则B2为B1的父边界。如果S2是background，那么B1的父边界是frame。

surroundness among borders（环绕边界）：给定两个边界 B_{0} 和B_{n}，如果存在一个边界序列B_{0},B_{1},...,B_{n}，其中B_{k}是B_{k-1}的父边界，那么我们称B_{n}环绕B_{0}。

通过以上定义，一幅图片中的边界和连通域可以构成拓扑关系。如下图所示：

光栅扫描(RasterScan)：是指从左往右，由上往下，先扫描完一行，再移至下一行起始位置继续扫描。

边界开始点（starting point）：边界开始点分为外边界开始点（Fig.2a）和孔边界开始点（Fig.2b）。如果点\left( i,j \right)既满足(a)又满足(b)，则把\left( i,j \right)视为外边界开始点。

NBD：从边界开始点\left( i,j \right)以边界跟踪算法可以得到一条边界，为每条新找到的边界B赋予一个新的唯一的编号，NBD表示当前跟踪的边界的编号。

LNBD：在光栅扫描的过程中，我们也保存最近遇到（上一个）的边界B'的编号，记为LNBD。

假设输入图像为 F=\left\{ f_{ij} \right\} ，将初始NBD设为1（把F的frame看成第一个边界）。使用光栅扫描法扫描图像F，当扫描到某个像素点\left( i,j \right)的灰度值 f_{ij}\ne0 时执行下面的步骤。每次当我们扫描到图片的新行的起始位置时，将LNBD重置为1。

（1）从下列情况选一种：

（a）如果 f_{ij}=1并且 f_{i,j-1}=0 ，即Fig.2a所描述情况，则\left( i,j \right)是外边界开始点，NBD+=1，\left( i_{2},j_{2} \right)\leftarrow\left( i,j-1 \right)。

（b）如果 f_{ij}\geq1并且 f_{i,j+1}=0 ，即Fig.2b所描述情况，则\left( i,j \right)是孔边界开始点，NBD+=1，\left( i_{2},j_{2} \right)\leftarrow\left( i,j+1 \right)。如果 f_{ij}>1，则 LNBD\leftarrow f_{ij} 。

（c）其他情况，到第（4）步

（2）根据上一个边界B'和当前新遇到边界B的类型，我们可以从表1得到当前边界B的父边界。

（3）从边界开始点 (i,j) 开始按(3.1)到(3.5)进行边界跟踪。

（3.1）以(i,j)为中心， (i_{2},j_{2}) 为起始点，按顺时针方向查找(i,j)的4（8）邻域是否存在非0像素点。若找到非0像素点，则令(i_{1},j_{1})是顺时针方向的第一个非0像素点；否则令 f_{ij}=-NBD ，转到（4）。

（3.2）\left( i_{2},j_{2} \right)\leftarrow\left(i_{1},j_{1} \right)， (i_{3},j_{3})\leftarrow(i,j)

（3.3）以 (i_{3},j_{3}) 为中心，按逆时针方向，(i_{2},j_{2})的下一个点为起始点查找(i_{3},j_{3})的4（8）邻域是否存在非0像素点，令(i_{4},j_{4})是逆时针方向的第一个非0像素点。

（3.4）

（a）如果(i_{3},j_{3}+1)是(3.3)中已经检查过的像素点且是0像素点，则 f_{i_{3},j_{3}}\leftarrow-NBD 。

（b）如果(i_{3},j_{3}+1)不是(3.3)中已经检查过的0像素点，并且 f_{i_{3},j_{3}}=1 ，则 f_{i_{3},j_{3}}\leftarrow NBD 。

（c）其他情况，不改变 f_{i_{3},j_{3}} 。

（3.5）如果(i_{4},j_{4})=(i,j)且 (i_{3},j_{3})=(i_{1},j_{1}) （回到了边界开始点），则转到(4)；否则令(i_{2},j_{2})\leftarrow(i_{3},j_{3})，(i_{3},j_{3})\leftarrow(i_{4},j_{4})，转到(3.3)

（4）如果 f_{ij}\ne1，则 LNBD\leftarrow\left| f_{ij} \right| ,从点 (i,j+1) 继续光栅扫描。当扫描到图片的右下角顶点时结束。

例子来源于原论文，如下图Fig.3所示：

光栅扫描遇到的第一个非0像素点是FiG.3(a)中画圆圈的1，如下图中红色的1。

（1）(i,j)=(1,2)，满足算法步骤(1)的(a)，所以当前边界B是外边界，NBD=2， \left( i_{2},j_{2} \right)=(1,1) 。

（2）上一个边界B'是frame（孔边界），从table1可知当前边界B的父边界为B'（frame）。

（3.1）以(i,j)=(1,2)为中心， (i_{2},j_{2})=(1,1) 为起始点，按顺时针查找到第一个非0像素点(i_{1},j_{1})=(1,3)。

（3.2）\left( i_{2},j_{2} \right) =\left(i_{1},j_{1} \right)=(1,3)，(i_{3},j_{3})=(i,j)=(1,2)

（3.3）以 (i_{3},j_{3})=(1,2) 为中心，按逆时针方向，(i_{2},j_{2})=(1,3)的下一个点(0,2)为起始点查找(i_{3},j_{3})的4邻域第一个非0像素点为(2,2)，则(i_{4},j_{4})=(2,2)。

（3.4）(i_{3},j_{3}+1)=(1,3)不是(3.3)中已经检查过的0像素点，并且f_{i_{3},j_{3}}=1 ，则 f_{i_{3},j_{3}}= NBD=2 。

（3.5）(i_{2},j_{2})=(i_{3},j_{3})=(1,2)，(i_{3},j_{3})=(i_{4},j_{4})=(2,2)，转到(3.3)

下面就是算法的循环步骤，判断方式与上述差不多，在此本人不再多加赘述。

函数的hierarchy用来保存上述算法中得到的边界的拓扑序列，如FiG3的右边结构。contours则是提取到的轮廓，mode可以用来指定只提取外轮廓或提取全部轮廓，method指定轮廓近似方式（用哪些方向的线条近似）。