轮廓跟踪

轮廓跟踪
2010年07月23日
　　在识别图象中的目标时，往往需要对目标边缘作跟踪处理，也叫轮廓跟踪。顾名思义，轮廓跟踪就是通过顺序找出边缘点来跟踪边界的。若图象是二值图象或图象中不同区域具有不同的象素值，但每个区域内的象素值是相同的，则如下算法可完成基于4连通或8连通区域的轮廓跟踪。
　　步骤1：首先按从上到下，从左到右的顺序扫描图象，寻找没有标记跟踪结束记号的第一个边界起始点A0，A0是具有最小行和列值的边界点。定义一个扫描方向变量dir,该变量用于记录上一步中沿着前一个边界点到当前边界点的移动方向，其初始化取值为
　　（1）对4连通区域取dir=3；
　　（2）对8连通区域取dir=7；
　　步骤2：按逆时针方向搜索当前象素的3*3邻域，其起始搜索方向设定如下：
　　（1）对4连通区域取（dir+3）mod 4；
　　（2）对8连通区域，若dir为奇数取（dir+7）mod 8；若dir为偶数去（dir+6）mod 8；
　　在3*3邻域中搜索到的第一个与当前像素值相同的像素便为新的边界点An,同时更新变量dir为新的方向值。
　　步骤3：如果An等于第二个边界点A1且前一个边界点An-1等于第一个边界点A0，则停止搜索，结束跟踪，否则重复步骤2继续搜索。
　　步骤4：由边界点A0、A1、A2、……、An-2构成的边界便为要跟踪的边界。
　　上述算法是图象轮廓跟踪最基本的算法，它只能跟踪目标图象的内边界（边界包含在目标点集内），另外，它也无法处理图象的孔和洞。
　　边界跟踪
　　　　假定我们从一个梯度幅值图像着手进行处理，这个图像是从一幅处于和物体具有反差的背景中的单一物体的图像进行计算得来的。因为灰度级最高的点（即在原始图像中梯度值最高的点）必然在边界上，所以我们可以把这一点作为边界跟踪过程的起始点。如果有几个点都具有最高灰度级，我们可以任选一个。
　　　　接着，搜索以边界起始点为中心的  邻域，找出具有最大灰度级的邻域点作为第2个边界点。如果有两个邻域点具有相同的最大灰度级，就任选一个。从这一点开始，我们起动了一个在给定当前和前一个边界点的条件下寻找下一个边界点的迭代过程。在以当前边界点为中心的  邻域内，我们考察前一个边界点位置相对的邻点和这个邻点两旁的两个点（图8-4-1）。下一个边界点就是上述三点中具有最高灰度级的那个点。如果所有三个或两个相邻边界点具有同样的最高灰度级，我们就选择中间的那个点。如果两个非邻接点具有同样的最高灰度级，我们可以任选其一。
　　　　在一个无噪声的单调点状物图像中，这个算法将描画出最大梯度边界；但是，即使少量的噪声也可能使跟踪暂时或永远偏离边界、噪声的影响可以通过跟踪前对梯度图像进行平滑或采用“跟踪虫”（tracking bug）的方法来降低。即使这样，边界跟踪也不能保证产生闭合的边界，并且算法也可能失控并走到图像边界外面。
　　　　跟踪虫是一种按下述方式工作的算法“昆虫”。首先我们定义一个矩形平均窗n（“虫”），通常整个窗口具有相同的权值（图8-4-1）。最近两个或几个边界点定义了当前的边界方向。虫的背部则以当前边界为中心，以当前的边界方向为轴。随后跟踪虫可向任一边转一个角。
　　图 8-4-1　边界跟踪
　　
　　
　　
　　图 8-4-2　边界跟踪虫
　　
　　
　　
　　　　在虫的每一个位置，对虫覆盖的区域的平均梯度进行计算。当虫位于最高平均梯度位置时，可以从虫的前部选择一个点作为下一个边界点。显然，跟踪虫是在一个更大的空间执行先前描述过的边界跟踪过程、大尺寸的跟踪虫可以完成梯度图像的平滑，从而降低了它对噪声的敏感化 它也限制了边界方向的急剧改变。
　　　　虫的大小和形状也可以改变以求达到最佳性能。可通过减小旁视角增大虫的“惯性”。实际上，虫的确切形状对其性能影响似乎并不明显。梯度跟踪虫通常在噪声很低的图像或人工干预能防止灾难性的偏差的情况下才有用。
　　　　二、梯度图像阈值化
　　　　如果用适中的阈值对一幅梯度图像进行二值化，那么，我们将发现物体和背景内部的点低于阈值而大多数边缘点高于它。Kirsch的分割法利用了这种现象。这种技术首先用一个中偏低的灰度阈值对梯度图像进行二值化从而检测出物体和背景，物体与背景被处于阈值之上的边界点带分开。随着阈值逐渐提高，就引起物体和背景的同时增长。当它们接触上而又不至于合并时，可用接触点来定义边界。这是分水岭算法在梯度图像中的应用。
　　图 8-4-3　Kirsch的分割算法
　　
　　
　　
　　　　虽然KirsCh方法比二值化的计算开销大，但它可以产生最大梯度边界，并且避免了使用只有梯度跟踪虫时存在的许多麻烦。对包含多个物体的图像来说，在初始二值化步骤中分割正确的情况下，才能保证该分割的正确。预先对梯度图像进行平滑会产生较平滑的边界。
　　　　三、拉普拉斯边缘检测
　　　　拉普拉斯算子是对二维函数进行运算的二阶导数标量算子。它定义为
　　　　
　　　　它通常可以以数字化方式用图8-4-4中所示的卷积核之一来实现
　　图 8-4-4　拉普拉斯卷积核
　　
　　
　　
　　
　　
　　
　　　　由于拉普拉斯算子是一个二阶导致，它将在边缘处产生一个陡峭的零交叉。拉普拉斯算子是一个线性的、移不变算子，它的传递函数在频域空间的原点为零。因此，一个经拉普拉斯滤波过的图像具有零平均灰度。
　　　　如果一个无噪声图像具有陡峭的边缘，可用拉普拉斯算子将它们找出来。对经拉普拉斯算子滤波后的图像用零灰度值进行二值化会产生闭合的、连通的轮廓并消除了所有的内部点。但是由于噪声的存在，在运用拉普拉斯算子之前需要先进行低通滤波.选用高斯低通滤波器进行预先平滑是很合适的。由卷积的结合律可以将拉普拉斯算子和高斯脉冲响应组合成一个单一的高斯拉普拉斯核：
　　　　
　　　　这个脉冲响应对  和  是可分离的，因此可以有效地加以实现。它与第十一章中的讨论过的一般的带通滤波器的脉冲响应具有相同的形状，即一个负的凹谷中有一正向尖峰。参数  控制该中心峰的宽度，因此也控制了平滑的程度。
　　图 8-4-5　高斯拉普拉斯卷积
　　
　　
　　
　　边缘检测    
　　确定图像中的物体边界的另一种方法是检测每个像素和其直接邻域的状态，以决定该像素是否确实处于一个物体的边界上。具有所需样收的像素被标为边缘点、当图像中各个像素的灰度级用来反映各像素符合边缘像素要求的程度时，这种图像被称为边缘图像或边缘图。它也可以用仅表示了边缘点的位置而没有强弱程度的二值图像来表示对边缘方向而不是（或附加于）幅度进行编码的图像叫做含方向边缘图。
　　　　一幅边缘图通常用边缘点勾画出各个物体的轮廓，但很少能形成图像分割所需要的闭合且连通的边界。因此需要另一个步骤才能完成物体的检测过程。边缘点连接就是一个将邻近的边缘点连接起来从而产生一条闭合的连通边界的过程。这个过程填补厂因为噪声和阴影的影响所产生的间隙。
　　　　一、边缘检测
　　　　如果一个像素落在图像中某一个物体的边界上，那么它的邻域将成为一个灰度级变化的带。对这种变化最有用的两个特征是灰度的变化率和方向，它们分别以梯度向量的幅度和方向来表示。
　　　　边缘检测算子检查每个像素的邻域井对灰度变化率进行量化，通常也包括方向的确定．有若干种方法可以使用，其中大多数是基于方向导数掩模求卷积的方法。
　　　　Robe外边缘算子Roberts边缘检测算子是一种利用局部差分算子寻找边缘的算子。它由下式给出：
　　　　 
　　　　其中  是具有整数像素坐标的输入图像。其中的平方根运算使该处理类似于人类视觉系统中发生的过程。
　　　　Sobel边缘算子
　　　　下图所示的两个卷积核形成了Sobel边缘算子。图像中的每个点都用这两个核做卷积。一个核对通常的垂直边缘响应最大而另一个对水平边缘响应最大。两个卷积的最大值作为该点的输出值、运算结果是一幅边缘幅度图像。
　　图 8-5-1　Sobel边缘算子
　　
　　
　　
　　　　Prewitt边缘算子
　　　　下图所示的两个卷积核形成了 Prewitt边缘算子。 与使用Sobel算子的方法一样，图像中的每个点都用这两个核进行卷积，取最大值作为输出。PreWitt 算子也产生一幅边缘幅度图像。
　　图 8-5-2　Prewitt边缘算子
　　
　　
　　
　　　　Kirsch边缘算子
　　　　图8-5-3所示的8个卷积核组成了 Kirsch边缘算子口。图像中的每个点都用8个掩模进行卷积，每个掩模对某个特定边缘方向作出最大响应。所有8个方向中的最大值作为边缘幅度图像的输出。最大响应掩模的序号构成了对边缘方向的编码。
　　　　边缘检测器性能
　　　　由上述边缘算子产生的边缘图像看来很相似。它们看起来像一个绘画者从图片中作出的线条画。Robert算子是  算子，对具有陡峭的低噪声图像响应最好。其它三个算子，都是  算子，对灰度渐变和噪声较多的图像处理得较好。
　　　　使用两个掩模板组成边缘检测器时，通常取较大得幅度作为输出值。这使得它们对边缘的走向有些敏感。取它们的平方和的开方可以获得性能更一致的全方位响应。这与真实的梯度值更接近。
　　　　值得注意的是，  的 Sobel和Prewitt边缘算子可扩展成八个方向，并且可以像使用Kirsch算子一样获得边缘方向图。
　　图 8-5-3　Kirsch算子
　　
　　
　　
　　边缘连接
　　以下连接间断点的算法：
　　1．“非最大”抑制。在沿边缘方向追踪边缘点时，不被看作边缘点要进行抑制（设为0），这样最后输出的图像边缘比较细，具体操作时可使用形态学算法进行细化处理。
　　2．“滞后”处理。若使用单阈值 ，假定轮廓的平均灰度等于T ，由于噪声影响，轮廓上的有些点的灰度会小于T ，同样，有些点的灰度会高于T ，必然会造成轮廓的中断。为了避免这种情况出现，“滞后”处理使用一高一低两个阈值。图像中任意一点，只要其梯度大于T1 ，都被假定为边缘点，并立即标记，和该点相连的任意点只要其梯度大于T2 ，也被作为边缘点进行标记。因此，跟踪一个边缘，首先应该以梯度大于T1 的点开始，在遇到梯度小于T2的点前不要停止，这一跟踪过程称为“滞后”处理。
　　轮廓跟踪好像和边缘连接属于不同的边缘提取算法
　　对于一个图像来说，轮廓跟踪有边缘检测的效果，但是对于对比度低的图像效果并不是很好.对于已经提取出来的边缘，轮廓跟踪是没有作用的，必须要用边缘连接算法来完成边缘的提取.
　　融合算法步骤
　　①  Sobel算子与图像卷积经典的Sobel算子只有水平和垂直两个方向的
　　模板，本文采用8个方向的模板（见图2）。图像中的每一点与这8个模板分别卷积，所得的最大值作为Sobel算子与图像卷积的输出，并记录相应的模板方向为该点的方向
　　②确定高低门限得到Sobel边缘图1，Soble边缘图2
　　③用Canny最佳边缘检测算子得到Canny边缘图
　　④Canny边缘图与Sobel边缘图1相与，得到初始边缘图
　　⑤在初始边缘图上寻找每一边缘线的端点或孤立点，标记这些点作为修补弱边缘的初始点
　　⑥采用轮廓跟踪的思想进行边缘修补，具体算法如下：
　　a.  确定孤立点或端点P的边缘方向（由①步Sobel算子计算得到）。
　　b.  在Sobel边缘图2上寻找P点边缘方向上的点P