基于角度搜索和距离判定的边缘检测算法

刘 锂，段芃芃

(成都理工大学 工程技术学院，四川 乐山 614007)

0 引 言

边缘检测算法在模式识别、图像处理、遥感应用、人工智能以及聚类数据的处理中有着广泛的应用。基本的边缘检测算法包括凸壳算法[1-3]和凹包算法。

凸壳算法的研究有卷包裹法、格雷厄姆方法、分治算法、图像目标外接多边形及凸壳的一种构造方法[4]、平面海量散乱点集凸壳算法[5]和坐标排序的离散点凸包生成算法[6]等。凸壳是几何图形的一种基本结构，凸壳算法在实现边界检测和数据分析中有着重要的作用，凸壳求取的是覆盖所有点的凸多边形，由于限定了一定是凸多边形，适用于点群全局结构的描述，可以很好地描述点群的作用边界，但是很难准确地体现出凹多边形的点群作用区域的边界。

凹包算法可以准确地反映多边形的点群作用区域的边界。对于凹包(concave hull)来说，与凸壳的区别是，凸壳是明确定义了几何形状为凸多边形，而凹包没有明确的几何定义，针对的是不规则的点集，可以有各种各样的凹包，也可以看成是一种广义的参数化的凸包。目前凹包算法的研究有Alpha shape算法[7-8]、基于Delaunay三角化算法[9]、滚边算法(edge pivoting)和滚球法(ball pivoting)。凹包算法能准确地实现离散点群的边界检测，但是具有较大的局限性，在数据量不大的情况下有较好的实现效果，离线点的几何距离也有一定的限制。为此李雯静等研究了《凸壳内缩法进行多密度离散点群边界检测》[10]，采用该方法可以突破以上的限制，该方法利用角度进行凸壳内缩，较好地实现了离散点的边缘检测[11-15]，但是只针对高密的点群数据，没有考虑到出现离散点内存在距离较大跨度时的情况。文中提出一种基于角度搜索和距离判定的凸壳内缩算法，解决了上述问题，较好地实现了离散点群边缘检测。

1 算法思想

1.1 建立凸壳

设离散点群为N，建立边界数组S，以离散点群的上、右、下、左4个点为边界顶点建立离散点群凸壳，如图1所示，并将这4个点依次添加到边界数组中。具体公式如下：

S=[S上,S右,S下,S左]

(1)

其中，S上代表离散点群N中y坐标最大的点，S右代表离散点群N中x坐标最大的点，S下代表离散点群N中y坐标最小的点，S左代表离散点群N中x坐标最小的点。即：

S上=(x,ymax)

(2)

S右=(xmax,y)

(3)

S下=(x,ymin)

(4)

S左=(xmin,y)

(5)

图1 离散点群凸壳

1.2 角度搜索凸壳内缩

角度搜索就是设置一个最佳阈值角度，根据角度进行判断，内缩方法求凹多边形的顶点，根据凹包的几何特性，通常情况下阈值角度值的范围在[0.5π，π)之间。依次取出边界数组中两个相邻边界点a、b，若点群中某点O与a、b所成角度大于阈值角度α(经过文中数据验证的最佳阈值角度α=0.575π)，并且该点的角度是其他所有点与a、b所成角度中最大的一个，如图2(a)所示。则该点为a、b的中间边界点，该点为内缩凹多边形的顶点，如图2(b)所示。并将该点添加到边界数组S中，依次循环边界数组S直到不存在O点为止，找到了所有的离散边界点，如图2(c)所示。

图2 角度法凸壳内缩过程

为角度检验设置固定的阈值的原因在于，如不设置阈值，任意两点a、b都会存在一个点O与a、b两点所成角度是所有点中的最大值，因此在实际的运算中会出现无限死循环的情况。

具体的计算公式如下：

(6)

(7)

(8)

(9)

其中，ab为点a、b间的距离，ob为点o、b间的距离，oa为点o、a间的距离；(xa,ya)代表a点坐标，(xb,yb)代表b点坐标，(xo,yo)代表o点坐标；cosaob为点a、o、b之间的夹角余弦值。

a、o、b之间的夹角计算公式为：

α=arccosaob

(10)

边界点角度判定条件为：

α>0.575π&&α>αmax

(11)

其中，αmax表示其他所有点与a、b所成角度的最大值。

1.3 距离判断检验二次内缩

文中采用的实验数据是针对乐山市市中区商业中心聚类分析的离散点数据，由于研究的是整个城市区域，出现了离散数据之间大距离跨度的问题，采用角度法凸壳内缩，实现的边缘检测效果如图3所示。

从图3中可看出，乐山市区的城市建设都是围绕着绿心公园进行的，直接导致了乐山市区的整体分布呈现整体内凹的特点。整体内凹是相对于局部内凹而言的，所谓整体内凹是数据的总体分布是呈现向内凹陷的特点，局部内凹则是在某一小区域呈现向内凹陷。在采用角度法进行内缩之后会出现图3所示的情况。因此，对应用角度法产生的边界提出了二次距离检验即边长检验。对图3进行分析可以发现，异常边ab的长度远远大于其他正常边的长度，并且其他所有点与a、b所成角度最大的点O'点的角度αmax小于角度判定阈值0.575π，因此，这两点之间实际上并不存在一个O点(O点与a、b两点所成的角度大于0.575π，且是其他所有点与ab所成角度的最大值)。造成这种现象的原因在于分析数据呈现整体内凹的特点，而a、b两点又刚好存在于内缩部分的两个顶点位置，这就使得所有数据都呈现出了一种远离a、b两点的趋势。而当两点固定第三点未知的情况下的时候，第三点与a、b两点的距离远会造成a、b两点与第三点所成角度也会存在变小的趋势。

图3 角度法凸壳内缩边界

针对以上问题，提出了边长检验二次内缩。当ab间距离大于给定的距离阈值时，边界判定条件为，依次取出边界数组中两个相邻边界点a、b，若点群中某点O与a、b所成角是其他所有点与a、b所成角度中最大的一个。具体的公式如下：

当Lab>M时，边界点角度判定条件为：

α'>αmax

(12)

其中，αmax表示其他所有点与a、b所成角度的最大值。

M为存在较大距离跨度值中的最小值。

M=Min{L1,L2,…,Ln}

采用SPSS 21.0软件对数据进行分析处理，两组患者的AST、ALT、ALB、AKP、Cr、BUN、DBIL、TBIL水平等计量资料用（均数±标准差）表示，用t检验，检验水准α=0.05，以P＜0.05表示差异具有统计学意义。

(13)

其中，Ln为较大跨度的距离。

2 算法实现

(1)获取数据：获取已知聚类分析数据的离散点，并将其保存在数组N中。

(2)建立凸壳，对数组N进行循环，通过式(2)～式(5)计算上、右、下、左四个顶点坐标，建立初始的凸壳，并将四个顶点坐标值保存在边界数组S。

(3)内缩算法实现：

①循环边界数组S。

②取出相邻的两个点a、b。

④找出a、b间的一点o，通过式(6)～式(10)计算出ab和α，根据式(11)进行角度判定，若找到满足角度的点，替换αmax，记录该点下标。若找不到满足角度的点，则进行边长的二次验证，根据式(11)、式(12)进行判断，若满足条件，替换αmax，记录该点下标。

⑤进入下一次离散点集合数组N循环。

⑥离散点集合数组N循环结束，将αmax对应点加入到边界数据S中的a、b之间。

⑦进入下一次边界数组S循环。

⑧边界数组S循环结束，即找到了所有的边界点数据，绘制边界线，进行成果显示。

(4)成果显示，循环边界数组S，绘制边界线，进行成果展示。

3 实验分析

以乐山市市中区156平方公里为研究对象区域，研究数据共有12类不同的要素的属性数据，数据信息近12余万条，要素信息有商业区、行政单位、住宿小区、医院、加油站、街道、公交路线、学校、大型购物中心、车站、城市绿地、酒店等。测试数据为对研究对象进行商业聚类分析的离散数据，采用文中方法对聚类分析的数据进行边缘的检测和边界的描绘。具体的数据分析如表1所示。

表1 数据分析

由表1数据可以看出，当判定阈值增大时，边界点的数量减少且绘制的实际边界图的边界也变得更加的“粗糙”。如图4(a)，当边界判定阈值为0.5π时，实现的边界效果较好，但是边界过于锐利不能很好地反映离散数据的实际边界情况；当边界判定阈值大于0.6π时，如图4(d)所示，边界又过于粗糙，并且随着判定阈值的增加粗糙程度还在不断增加。图4(b)和图4(c)当判定阈值为0.55π和0.575π时，边界数据相对较好，在绘制的数据边界相对圆滑，也能较好地反映聚类数据的边界。因此，文中将0.575π作为最终的判定阈值。

图4 不同角度的边界效果

4 结束语

提出的基于角度搜索和距离判定的凸壳内缩算法，考虑了不同程度离散数据的情况，同时也考虑了存在距离跨度较大的情况，针对距离跨度较大导致角度法内缩失效的情况，进行了数据的分析和研究，通过设定距离的阈值对距离验证和判断进行了二次内缩，较好地实现了离散数据的边界检测。通过具体的实验数据验证，采用该方法实现的效果较好，绘出的边界数据精准度较高。在该算法中，根据凹边形的几何特性，采用角度法和边长的二次验证进行边界的判断，简化了凹包算法的复杂度，算法简洁高效，便于实现。通过实际的数据证明，该算法在不同程度的离散数据的情况下，边界数据检测精度高，异常数据小，边界间区别明显，能够准确甄别出区域边界；在出现较大跨度的离散数据的情况下，该算法能够适应存在较大距离跨度的空间分布的特点，并能得到准确的边界精度。但是在执行该算法时，还存在一些问题，对判断的阈值角度和判定的边长距离需要进行多次试验才能求出最佳值，因此下一步将重点研究阈值角度和判定的边长距离的最优解方法，以进一步简化数据实验的过程。