[科普中国]-边缘搜索

简介边缘搜索

在数字图象处理和分析中，经常涉及到图象中物体边缘的提取。一般情况下均假设图象为二值图象，即背景的颜色标号0，前景(物体)的颜色标号为1。

传统的图象边缘搜索是按最左搜索进行的，即:先找到物体的一个边缘点，然后按顺时针方向搜索它的8个邻点得到下一个边缘点，如此搜索下去，得到一个闭合的点序列，即物体的边缘。在搜索的过程中，还要判断一个前景颜色的点是物体的边缘点还是内点，这可以通过分析边缘点的特征来实现。1

边缘极点的判断在边缘搜索的过程中，对于前景颜色的点，需要判断它是某个物体的内点还是另一个物体的边缘点。可以通过区分物体边缘点的类型来判断。

如图所示，其中的虚线为两个扫描线，P0，P1，P2，P3为扫描到的物体边缘点。其中，P0为真正的边缘点，扫描时经过这样的点则进入或离开物体:P3为边缘极点，扫描时经过这样的点可以跳过不作处理:对于P1和P2，情况要复杂一些。如果忽略水平方向上P1和P2之间的点，使P1和P2相重合则可以表示一个边缘点:故可以认为P1以及P1到P2之间的点为边缘极点，而P2为边缘点。

在图4中，P1和P2以及P1和P2之间的点都是边缘极点。总之，声遇到这种情况时，要将其中水平线段上的边缘点标记为边缘极点，再根据两个端点的情况标记端点;主要是根据其周围同色的点的方向标号进行判断。1

边缘搜索算法图象的拓宽在对二维数字图象进行逐点处理时，经常需要判断某个点是否为此幅图象的边界点。由于图象边界点的邻点的个数与内部点是不同的，所以在边缘搜索算法中，往往还要进行一些特殊的处理。为了避免这一点，我们将图象的边界各展宽一个象素，新的边界点的颜色设为背景色。假设原图象的大小为Widhth*Height，拓宽后的大小为（Widhth+2)*(Height+2)，新的边界点颜色设为0，如图所示。

这样，在遍历图象时，就不必对原图象的边界点进行特殊的判断和处理。

算法描述下面给出图象边缘搜索算法的描述:

0)置当前颜色Color为背景色0，将Color压入堆栈:

1)从上到下，从左到右遍历图象(包括拓宽后的边界);

2)若当前点P是未搜索过的前景点，则:

2.1)若P点的颜色等于当前颜色Color，则跳过;

2.2)否则以P点为起始点，搜索并标记一个物体的边缘;

3)若当前点P为己搜索过的前景点，且不是边缘极点，则:

3.1)若P点的颜色和栈顶的颜色相同，则弹出栈顶的颜色:然后再弹出栈顶的颜色到Color中:

3.2)若P点的颜色和栈顶的颜色不同，则将P点的颜色压入堆栈，并置当前颜色Color为P点的颜色:

4)若当前点P为已搜索过的前景点，且是孤立点，则跳过;

5)若当前点P为己搜索过的前景点，且是边缘极点，则跳过:

6)若当前点P为背景点，则跳过。

其中，步骤2.2)的算法为:

2.1)以当前点P作为起始点，根据方向标号为0，1，2，3的4个邻点的颜色确定P点的类型并做标记:取和P点同色的下一个边缘点作为当前点，其方向记为Dir:

2.2)扫描方向标号Dir2为6+Dir，7+Dir，Dir，Dir+1，Dir+2(mod8)的点，寻找下一个边缘点:根据Dir和Dir2标记当前点的类型:置Dir为Dir2;

2.3)重复2.2)直到当前点的坐标Pos等于起始点P的坐标。1

小角度边缘搜索固然，在运动自适应的去隔行算法中，正确的区分静止和运动很重要。但是，对于运动图像中边缘信息的准确检测，并在空间插值滤波器中合理应用边缘信息对提高图像质量也相当关键。

基于边缘的行平均(ELA)算法在去隔行中得到广泛应用，但是，它的致命缺陷是对水平边缘的检测能力很弱，只能检测45°、90°和135°边缘，对于小角度边缘则无能为力。为提高水平边缘的检测能力，小角度边缘搜索改进算法主要包括两个方面:(1)增大搜索范围(半径)，左右最大各搜索8个点，并且采用自适应搜索的设计方法，从而减小硬件的复杂度;(2)增加对边缘方向上相邻像素的考虑，实现半像素精度，提高边缘检测的精度。

边缘搜索示意如图所示，其中黑点代表待插补的像素x(i，j)，上下两行的像素点的对角线方向代表可能的边缘方向。

其基本原理是:通过比较对角线上的像素绝对差值判断对角线对应像素与待插补像素的相关性，绝对差值越小相关性越大，最小差值对应的方向就是边缘方向。在计算中采用并行处理架构，将上下行的对角像素分为3部分:

(1)中间部分，只有90°一个方向的两个像素x(i，j-1)，x(i，j+1);

(2)向左搜索部分，包括j-1行上x(i，j-1)右边的像素和j+1行上x(i，j+1)左边的像素;

(3)向右搜索部分，包括j-1行上x(i，j-1)左边的像素和j+1行上x(i，j+1)右边的像素.同时计算这三部分对角像素的绝对差值，分别得到中间部分绝对差值Dm、左边部分绝对差值L1，L2，…，L8和右边部分绝对差值R1，R2，…，R8。即

其中，Y(i，j)表示像素x(i，j)的亮度分量值，其它同义。

在小角度边缘搜索中，为减少计算量和硬件资源的消耗，采取自适应搜索半径的检测方法，在进行向左或向右顺序搜索的过程中每一级计算结束后都要将差值与上一级进行比较(第一级的差值与Dm进行比较)，如果绝对差值一直保持减小趋势则继续进行搜索，直到tap=8，如果出现相反的变化趋势，则停止搜索.然后比较这些差值选择出最小的绝对差值D，此最小差值对应的对角方向就是大致的边缘方向.D=min(Dm，L1，…，Ln，R1，…，Rn)。2