张量投票在边界提取中的应用

Application of Tensor Voting in Edge Detection

摘要: 边界提取是图像处理中的基本问题之一。在分类总结相关工作的基础上，介绍了张量投票方法在边界提取中的应用，并通过实验展示了该方法的边界修复特性。

Abstract: Edge detection is a basic problem in image processing. This paper presents a summary of related works and introduces how to apply the tensor voting method in edge detection. The algorithm’s flowchart and typical experimental result are demonstrated to show the completion characteristics of the algorithm.

1. 引言

在图像中，相邻的两个类型区域的分界线称为边界，边界表明一个类型区域的终结和另一个类型区域的开始，即是说，边界所分的区域其内部特征或属性是一致的或相近的，而相邻的两个区域内部的特征或属性彼此是不同的，图像中相邻两个区域的特征差异正是发生在边界处。经验指出，图像区域边界往往对应景物对象的边缘。图像上的边界点或边界线是因不同的反射或透射引起的，它们可能对应下述物理原因：

1) 物体的棱线、物体间的界限、物体边缘线；

2) 物体表面不同的颜色或不同的材料；

3) 空间曲线或曲面的不连续点；

4) 物体的阴影会产生边界。

边界在图像中所占比例较小，是图像的重要特征之一。由于模糊和噪声的存在，某些算法所检测到的边界可能展宽或间断，因此，边界检测(Boundary Detection)包括两个基本内容：提取边界点集，剔除某些边界点或填补边界间断点。边界检测技术可广泛应用于工业设计、医学图像三维重建、虚拟视景生成、图像识别等方面，多年以来，一直吸引着许多不同领域的研究人员 [1] 。

张量投票 [2] 可以应用于边界检测是很自然的，既然张量投票方法最初的设计是为了提取曲线，那么，如果能把形成目标边界的曲线完整地检测出来，就完成了边界提取的任务。同时，由于张量投票域能扩展图像中目标象素点的作用范围，这一方法还能在一定程度上修复缺失的边界。

2. 相关工作

为了提取区域边界，可以对图像直接运用一阶微商算子或二阶微商算子，然后根据各像素点处的微商幅值及其他附加条件判定其是否为边界点。如果图像中含有较强噪声，此时，若直接进行微商运算，将会出现许多虚假边界点，因此，可以首先采用曲面拟合方法用一个曲面拟合数字图像中要检测点的邻域各像素的灰度，然后再对拟合曲面运用微商算子，或用一个阶跃曲面拟合数字图像，根据其阶跃幅值判断其是否为边界点，还可以首先用一个函数与图像卷积平滑噪声然后再对卷积结果运用微商方法提取边界点集。用于平滑噪声的函数通常称为平噪或平滑函数。Canny提出了评价边界检测算法性能优良的三个指标：①高的信噪比；②精确的定位性能；③对单一边界响应是唯一的。上述的微商思想、平滑思想、准则函数确定边界提取思想等基本技术的不同“组合”便产生了不同边界提取算法。例如匹配滤波器也可以看作这些方法的特殊情况，用一个函数与原图像进行卷积，且用Canny提出的标准①去确定这个函数。

最简单的边界提取方法是直接对图像运用导数算子，灰度变化较大的点处算得的值较大，所以导数算子可以作为边界检测算子，并通常将这些导数值作为相应点的“边界强度”，然后采用设置门限的方法，提取边界点集。用于边界提取的微分算子 [1] 有简单微分算子、罗伯茨梯度算子、Prewitt算子、Sobel算子、Kirsch算子、Rosenfeld算子、Wallis 算子、拉氏算子、L-G算子(LOG算子，Marr算子)、Canny算子等；也可用曲面拟合后求导提取边界，这里的曲面可以是一次、二次或三次曲面，曲面拟合提取边界的另一个方法是用一个阶跃曲面与图像子域的灰度进行拟合。

除了上述基本方法之外，还有一些比较有特色的方法：1) 统计判决法 [1] ，这一方法假定相邻像素灰度取值是独立的，根据目标点和背景点灰度的概率分布密度函数设定最小误判概率准则判决提取边界；2) 形态学方法 [1] ，即通过取一个3 × 3的结构元素，然后用该结构元素对图像进行腐蚀，接着用原图像减去腐蚀结果便可得到图像的边界；3) 随机启发式搜索算法 [3] ，该方法随机地选取起始点，并依照引导度量的概率反复地进行随机搜索获得各种可能的边界轨迹，然后对搜索到的轨迹进行累积，达到自增强的效果，最后根据自增强统计结果获得边界；4) “边缘流”法 [4] ，这一方法首先在一定尺度上检测每一图像元素颜色和纹理变化的方向，构建一个“边缘流”矢量，当出现两个相反方向的边缘流矢量的时候就表明边界的存在；5) 基于灰度梯度的边界检测优化算法 [5] ，该方法在梯度计算的基础上，根据最小方向性和最小偏离近似误差两项优化准则得到两种梯度近似的优化算法；6) 几何模型法，这类方法包括Snake模型 [7] 、Geodesic Active Contour 模型 [8] 、Mumford-Shah 模型 [6] 和Chan-Vese模型 [9] 等，这类方法通过能量最小化方法演化活动轮廓曲线来逼近目标边界，其中Chan-Vese模型在Mumford–Shah模型基础上，结合了level set 方法，在理论和算法上非常完善，而且不依赖于边缘检测结果，比显式的snake模型对拓扑关系处理得更好；7) 基于有向滤波的方法 [10] [11] ，使用一系列有向滤波器合成图像像素的边界响应值；8) Martin等研究者 [12] [13] 将颜色和纹理信息也考虑进来,并应用机器学习方法融合各种线索，X. Ren等在此基础上加入了多尺度分析 [14] ，Zhu Q.等根据Martin等的计算结果生成边缘的加权图以判别相邻边缘之间的共线关系，他们还建议依据复杂的正交化随机步进矩阵(normalized random walk matrix)的特征值检测图中的环来提取封闭曲线 [15] ；9) 加入全局约束(如平滑性、封闭性)的方法，其中文献 [16] [17] [18] 等方法可在边缘检测的基础上根据共线关系进行连接，X. Ren等 [19] 提出了基于条件随机场(Conditional Random Fields)的方法，计算各边缘的约束Delaunay三角化结果并进行边界修复；10) 信息融合法(全局Pb算子) [20] ，该方法先计算多尺度下各点的亮度、颜色和纹理的有向梯度，并以直方图的形式进行局部的信息合成，然后采用谱聚类(spectral clustering)的方法进行全局的信息融合完成边界轮廓检测，进一步可通过有向分水岭变换(Oriented Watershed Transform)和轮廓图(Ultrametric Contour Map)完成图像分割，文献 [22] 用类似的方法获取边界检测的局部线索和全局线索并进行了加权组合；11) 稀疏编码梯度法(Sparse Code Gradients) [21] ，该方法采用K-SVD方法完成字典学习(dictionary learning)过程，应用正交匹配(Orthogonal Matching Pursuit)算法 [23] 完成稀疏编码的计算，并融合了多尺度分析等过程，最后通过线性支持矢量机完成分类识别过程，提取出边界。

3. 方法描述

张量投票方法既可以在边缘检测的基础上进行边界检测，也可以在灰度图像上直接用二维圆形投票域进行张量投票过程，然后进行投票解释，并根据边界特征的显著性提取边界，其原理如图1所示，即利用边界点被投票之后叠加的矢量和大于区域内部点这一特征来检测边界。

Figure 1. The basic theory for tensor voting to extract the boundary

图1. 张量投票提取边界的原理示意图

张量投票依据图1所示原理进行边界检测的流程图如图2所示。其中，圆形投票域的计算如式(1)所示，式中，表示距离，为所选的尺度参数；投票之后即形成边界的显著度图；在此基础上，投票解释对投票结果进行矢量叠加，根据各点矢量和的大小检测边界。

(1)

4. 实验结果示例

张量投票进行边界提取的示例如图3和图4所示。图3中，图(a)为原始输入图像；图(b)为张量投票之后获取的区域边界显著度图；图(c)为边界检测结果。从图中可以看出，通过投票过程，区域中的点得到不同方向投票而矢量相消，边界点由于只得到某一侧的投票而得到增强，最后通过投票解释过程即可获取区域的边界。图3和图4说明算法对噪声具有一定鲁棒性。

应用张量投票方法在提取边界的过程中，由于投票域的作用扩展了图像中数据点的作用范围，还可以修复部分缺失的边界。图3和图4给出两个示例。图3是在噪声点中提取了一个圆形边界，并将不连续的边界点连接了起来；图4是针对典型的主观轮廓图形之一——Kanizsa矩形所作的试验，可以看到缺失的边界得到了修复。

Figure 2. The flowchart for tensor voting to extract the boundary

图2. 张量投票提取边界的计算流程图

(a) (b) (c)

Figure 3. Example 1 for boundary completion. (a) Edge elements and noise; (b) Saliency map of the boundary; (c) Detection results

图3. 边界修复示例一。(a) 边缘片段及噪声；(b) 增强边界显著度图；(c) 边界检测结果

(a) (b)

Figure 4. Example 2 for boundary completion. (a) Kanizsa rectangle; (b) Saliency map of the subjective contour

图4. 边界修复示例二。(a) Kanizsa矩形；(b) 主观轮廓修复结果

前面描述的是张量投票方法直接提取边界的解决思路，除此以外，张量投票还可以与其他方法结合完成边界检测。比如，张量投票方法可与Snake模型结合，Snake模型由Kass和Witkin等 [7] 首先提出，后由Caselles [8] 进行了改进，成为边界活动模型。张量投票与Snake模型的结合主要是改进了停止函数，使其在对比度较低图像的分割上更加有效。

原方法的停止函数计算公式为 [7] ：

(2)

经Caselles [8] 改进后算法的停止函数更新为：

(3)

式中，为尺度为的高斯核，为初始图像，为加权常数。

在实际应用中值很难选取，如果取得过大，迭代次数会很大，而且影响结果的正确性；如果取的过小，处理对比度低的图像效果不好。于是，王伟等 [24] 结合张量投票算法将停止函数改进为：

(4)

其中，，而为处根据张量投票结果计算的曲线显著度函数，计算公式如式(5)所示；一般根据经验值取100。

(5)

式(5)中，和为该处投票后张量矩阵的最大特征值和最小特征值，取值在(0,1] 区间，取值越大，说明该点为边缘或在曲线上的可能性越大。实验表明：(1) 对血管图的处理，原模型，迭代200次；改进后，迭代600次，但处理效果明显增强；(2) 改进后的方法对边缘较模糊的图像效果更佳，参数一般不需要改变，但迭代次数一般是原始算法的3倍 [24] 。

5. 结束语

本文对边界提取的相关工作进行了较为全面的总结，继而介绍了张量投票方法在边界提取中的应用，给出了算法的原理、流程和实验结果示例。与其他相关工作相比，张量投票方法的优越性主要体现在三个方面：一是计算复杂度低，如图像大小为k，取投票域大小为n，投票过程计算复杂度为o(kn)，再令s为投票解释需处理的像素数，则投票解释需处理的计算复杂度为o(s)，总的计算复杂度为o(kn + s)；二是强大的修复特性，如实验结果所示，当轮廓边界有缺失部分时，张量投票可以自动修复一些缺口；三是可以与其他方法结合。我们下一步将继续研究如何自适应地调整张量投票的参数以更好地发挥其对缺失边缘的修复作用。