无粗定位亚像素边缘检测算法研究

夏阳阳, 林　菁

(上海师范大学 信息与机电工程学院,上海 200234)



无粗定位亚像素边缘检测算法研究

夏阳阳, 林菁

(上海师范大学 信息与机电工程学院,上海 200234)

针对传统的亚像素边缘检测技术需要先进行粗定位,然后再进行精确定位的问题,提出无粗定位亚像素边缘检测算法.针对彩色图像降低维度边缘信息损失的问题,提出主轴分析法来保存图像的边缘信息.针对滤波后图像边缘特征模糊的问题,提出基于二分K均值的中值滤波算法,在滤除噪声的同时,增强图像的边缘.最后从检测精度、检测效率和可靠性3个方面验证算法的有效性.

边缘检测; 亚像素; 粗定位; 主轴分析法; 二分K均值

0　引　言

基于图像的检测技术具有低成本、高效率等优点,所以应用十分广泛.然而,传统算法的定位精度只能达到像素级,已经不能满足当下高精度检测的需求.因此,亚像素检测的需求相当迫切.常见的CCD器件的像元大小可达到5 μm,经过亚像素定位,检测精度可达0.01个像素级,即测量精度可达0.1 μm,该精度已然能满足几乎所有的工业生产需求.

人类视觉系统接收到的图像是彩色的,人脑处理的图像信息也是彩色的,显然彩色图像更加符合人类的视觉感知,但是彩色图像复杂的结构以及庞大的数据量,导致图像处理过程中遇到很多困难,因此必须对彩色图像进行降维.这里采用主轴分析法,在降低图像维度的同时,又完整保留了图像的边缘信息,为后续的检测奠定良好的基础.

滤波是图像处理的重要过程,因为要进行边缘提取,所以选择一种适合边缘提取的去噪方法就尤为重要.本文作者提出了一种基于二分K均值的中值滤波算法,在图像平滑前先对某领域范围内的像素点进行聚类,然后根据聚类的结果判断该范围内是否存在边缘点和噪声,最后根据判断结果的不同采取不同的滤波策略,这样就能够有效地避免边缘的模糊.

传统的亚像素边缘检测算法可以分为插值法、拟合法和矩方法3种.这些算法的使用都有一个前提——已知目标像素级的边缘.这就会导致一个问题——如果粗定位定位得不够准确,那么精确定位就变得没有意义.本算法摆脱了对粗定位的依赖,直接对边缘进行亚像素检测.

1　彩色图像降维

将RGB图像转化为灰度图像的表达式近似为Gray=0.3R+0.6G+0.1B,假设存在这样一幅图像——左侧R=200,G=0,B=0,右侧R=0,G=100,B=0,计算可得左右两侧的灰度都是60,即不存在边缘,但显然边缘是存在的,这就是边缘信息的损失.利用彩色信息的丰富性可以有效解决这一问题.

彩色图像的边缘检测算法可分为输出融合法和向量法,输出融合法没有考虑颜色分量间的相互关系且对颜色模型较为依赖.向量法运算复杂,如果直接运用于亚像素边缘检测,那么算法的实时性将得不到保证,所以必须要对彩色图像进行降维.

彩色图像处理有三大难点——存储量大、运算量大、冗余度高.R、G、B3个分量包含的特征信息大部分是相同的,所以数据分析前要进行预处理,消除冗余变量,使数据分析能够高效地进行.主轴分析法[1-4]就是能够实现该功能的方法之一.令x=(X1,X2,…Xn)T为维变量,对其采用线性变换:

(1)

由线性正交变换原理可得:正交变换后,可以用较少的分量表示多个分量,同时仍然保留分量的特征信息.对比度大小是正交变换在图像处理中的表现形式,可通过惯性矩的大小来表示,值越小,特征信息保留的就越多.当惯性矩取值最小时,可得图像颜色空间的主轴,将彩色图像通过该主轴投影转化为灰度图像时,图像的特征信息保留得最为完整,边缘信息的损失最小.

对于任意一幅图像,主轴的原点为彩色空间的质心:

(2)

其中,ri、gi、bi表示彩色图像中第i个像素对应的3个颜色分量的值,N表示图像中像素的总数,图像中所有像素点的惯性矩为:

(3)

其中α、β、γ表示主轴与r、g、b分量的夹角,从RGB模型可知,r、g、b3个分量两两正交,可得 cos2α+ cos2β+ cos2γ=1.主轴方向惯性矩最小,则bcosβ-gcosγ=0,bcosα-rcosγ=0,gcosα-rcosβ=0,计算即得α、β、γ值.为了减少运算复杂度,将三维矩ms,t,u定义为:

(4)

根据惯性矩性质可知,cosα、cosβ、cosγ服从如下关系:

(5)

解之,可得:

(6)

用k1、k2表示cosα、cosβ、cosγ即得:

(7)

Gray=r×Wr+g×Wg+b×Wb.

(8)

对Lena图采用不同降维方法进行对比,效果如下:

图1　降维算法对比图

图1(c)的权值比较符合人类的视觉感受,所以看似比较清晰,但是仔细观察就可以发现,图像的边缘存在模糊,眼角部位尤其明显;而图1(b)的边缘则明显比较清晰,虽然整体图像看起来没有图1(c)舒服,但是图像的边缘信息保留得十分完整.

2　图像滤波

图像采集过程通中不可避免地会混入噪声,找到一种适合亚像素边缘检测滤波算法是准确定位的前提.中值滤波在保存图像边缘信息方面有着不错的表现,因此基于中值滤波提出基于二分K均值的中值滤波法[5-9].该算法的流程为:

(1) 对某领域范围内的像素点Ai进行排序运算,排序可以使聚类的运算量大大减少.

(2) 将Ai聚集成三类——普通点、边缘点和噪声.这里采用运算效率比较高的二分K均值进行聚类运算.二分K均值算法克服了K均值算法对初始中心点的选择较为依赖的问题,其主要思想为:首先将所有待聚类的点分为两个簇,然后对聚类效果最差的簇再次聚类,以此类推,直到簇的数目等于用户给定的数目为止.采用该算法得到的结果不依赖于初始中心点的选择,误差平方和小,聚类性能优越.

图2　滤波结果对比图

图2(a)为加上椒盐噪声后的图像,图2(b)为本文作者提出的滤波方法滤波后的图像,图2(c)为中值滤波后的图像.对比可得,基于K均值的中值滤波法在滤除高频噪声的同时,不但可以保证图像细节和边缘信息的完整,还能增强图像的边缘,为后续的处理打下良好的基础.

3　亚像素边缘检测

3.1无粗定位的亚像素边缘检测算法

传统的亚像素边缘检测算法都需要进行粗定位[10-12],如果粗定位得不够准确,最后的亚像素检测结果与实际结果将会有1个像素以上的偏差,作者将摆脱对粗定位的依赖,直接进行亚像素检测,大大提高检测结果的可靠性.

3.2高斯曲线拟合算法

通过对梯度图像进行观察可以发现,边缘附近梯度值的变化趋势化较接近于高斯曲线,所以采用边缘附近的高斯拟合来求亚像素坐标.高斯曲线的表达式为:

(9)

其中μ为均值,也是高斯曲线的对称轴,即亚像素的位置.由于高斯曲线表达式比较复杂,直接拟合比较困难,为了找出μ的位置同时简化运算,对等式两边取对数:

(10)

即可得到形如y=ax2+bx+c的表达式,即典型的抛物线,这样就可以使得运算的过程大大简化.

3.3拟合点的选取

通常在拟合前,要对拟合点进行筛选.由于干扰和噪声的存在,边缘附近像素点的梯度值并不是完全符合高斯曲线变化趋势的,所以要对梯度值进行筛选.如果不经筛选直接选择固定数量的点来进行拟合,就会导致拟合出的曲线偏离实际曲线,如图3所示.

图3　未筛选拟合曲线图

图4　准确筛选拟合曲线图

图3中实线为实际边缘曲线,虚线为拟合的曲线,显然两者的对称轴并不位于同一像素内.根据抛物线原理,三点就可以完全确定一条抛物线,因此如果拟合点选择得过少,就会导致拟合曲线完全取决于所选择的拟合点,曲线的边缘信息也会因为损耗而变得不完整.综上,采用如下算法来选取拟合点:

(1) 找到梯度值最大的点:如果某点的梯度值大于其左右3点的梯度值,则认为该点为梯度值局部最大点,如图3中的第6点;

(2) 沿着梯度值最的大点依次向左和向右寻找梯度值递减的点,最左边的点作为起始点,最右边的点作为终点:图3中第5点为起始点,第8点为终点,如果直接选择第5点到第8点进行拟合,则会因为选取的点过少而导致拟合结果的偏差;

此算法的目的是为了防止拟合点中存在某一个不符合高斯曲线变化规律的点,从而导致符合规律的点的漏取,同时也可以防止边缘信息的损失.经过改进的拟合点选取算法选择出的拟合点拟合出的曲线图4所示.其中,实线为实际梯度曲线,虚线为拟合曲线,两者的对称轴几乎一致.另外对梯度值进行筛选后,由于拟合点的减少,高斯-牛顿拟合法的运算量也大大降低,拟合效率也变得更高.

3.4方向不变性

梯度是具有方向性的,在求图像的梯度时,通常认为梯度向量的模就是梯度的大小,梯度的方向也是各不相同.采取新的思路——沿某一直线方向上求图像的梯度值,这样,像素点的梯度在方向上就是一致的.过某一边缘点,求3个方向的梯度值,其梯度曲线如图5所示.

图5　3个方向的梯度曲线

4　结果分析

采用VS2010编程软件进行仿真,从运算速度,运算的准确性和可靠性3个方面来分别讨论本算法与传统算法的优劣:

4.1运算效率

传统算法首先要进行粗定位,然后进行亚像素边缘检测,以canny算子为例,主要的运算流程如下:(1)采用Canny算子计算梯度大小和方向;(2)采取非极大值抑制;(3)亚像素检测.而本算法流程如下:(1)求出整幅图像的梯度值;(2)找到水平方向上符合拟合要求的梯度值的点,进行拟合.

通过对比可得,本算法不需要计算梯度的方向,不需要进行非极大值抑制,且梯度值计算相对简单,但是拟合运算较传统算法相对复杂.下面将通过仿真比较两种算法的运算时间.传统算法运算中,先通过传统算法计算出整幅图像梯度值,然后在边缘附近某一小范围内计算梯度方向确定边缘,最后根据确定的边缘通过传统的拟合法计算亚像素坐标.本算法运算中,先计算出整幅图像的梯度值,然后需找符合拟合要求的点,进行高斯拟合,从而确定亚像素位置.实际运算中,传统算法的运算时间为672 ms,而新算法的运算时间为438 ms,可见运算时间减少了,运算效率提高了.

4.2准确性

在实际运算之前,对图像进行了计算与分析,可以确定点(197,25)点为边缘点,下面通过两种方法确定该点的亚像素位置,结果如表1所示.

表1　运算结果对比表

表1中小数点后两位的值是完全一致的(多次仿真小数点后两位的值完全一致),即定位精度达到了0.01个像素级,工业CCD器件的像元大小可达到5 μm,经过亚像素定位,检测精度可达0.1 μm,因此本算法的精度可准确性都符合要求.

4.3可靠性

传统边缘算法的粗定位环节都需要根据选定的阈值T判断该点是否为边缘点.T值的选择具有不确定性,过大则会导致边缘点的漏取,造成边缘曲线的不封闭,过小则会导致边缘点的误取,造成粗定位像素级的偏差.虽然双阈值法可缓解该问题,但并不能完全解决该问题.

本文作者提出的算法则是基于边缘点附近梯度曲线的特性来对边缘进行定位,掌握的边缘信息较为全面,所以不会出现由于粗定位的不准确而导致定位的像素级的偏差,因此可靠性也优于传统算法.

[1]Cheng S C,Wu T L.Sub-pixel edge detection of color images by principal axis analysis and moment-preserving principle [J].Pattern Recognition,2005,38:527-537.

[2]Cheng S C,Wu T L.Fast indexing method for image retrieval using K neighbors searches by principal axis analysis [J].Journal of Visual Communication and Image Representation,2006,17(1):42-56.

[3]Xu S H,Liu J P,Wang Y,et al.Sub-Pixel edge detection of color image based on principal axis analysis and EDISON-Zernike moment [J].Chinese Journal of Scientific Instrument,2008,29(11):2272-2277.

[4]Xu S H,Liu J P,Hu M Y,et al.Color image edge detection based on principal axis analysis and embedded confidence [J].Computer Engineering and Applications,2007,43(36):34-36.

[5]Xiao J,Song S P,Ding L J.Research on the fast algorithm of spatial homomorphic filtering [J].Journal of Image and Graphics,2008,13(12):2302-2306.

[6]Liu X Z,Feng G C.Kernel bisecting K-means clustering for SVM training sample reduction [C]//IEEE.Proc of the 19th International Conference on Pattern Recognition.Tampa:IEEE,2008.

[7]Wang W Z,Qiu G Y,Zhang B Q.Adaptive clustering method based on linear discriminant analysis and bisecting K-means for high dimensional data [J].Journal of Zhengzhou University of Lightindustry,2011,26(2):106-110.

[8]Xie J Y,Guo W J,Xie W X,et al.K-means clustering algorithm based on optimal initial centers related to pattern distribution of samples in space [J].Application Research of Computers,2012,29(3):888-892

[9]Kanungo T,Mount D M,Netanyahu N S.An efficient K-means clustering algorithm:analysis and implementation [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(7):881-892.

[10]Broadwater J,Chellappa R.Hybrid detectors for subpixel targets [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(11):1891-1903.

[11]Zhu H,Zeng X J.Sub-pixel edge detection algorithm of Zernike moments and least-squares ellipse fitting [J].Computer Engineering and Applications,201l,47(17):148-150.

[12]Lyvers E P,Mitchell O R.Sub-pixel measurements using a moment-based edge operator [J].IEEE Trans on Pattern Analysis and Machine Intelligence,1989,11(12):1293-1309.

(责任编辑：包震宇)

Research on the algorithm of sub-pixel edge detectionwithout rough localization

XIA Yangyang, LIN Jing

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234)

Concerning the traditional sub-pixel edge detection techniques need to use the traditional edge detection algorithms for coarse positioning before precision positioning the algorithm of sub-pixel edge detection without rough localization was proposed.Concerning the edge information loss of color image principal axis analysis method was proposed to preserve the edge information.Concerning image edge feature gets blurred after filtering a median filter algorithm based on bisecting K-means was proposed.Bisecting K-means median filter algorithm can enhance the image edges when filtering out the noise.At the end by comparing the result at the aspects of detection accuracy,efficiency and reliability the validity of the algorithm proposed can be proved.

edge detection; sub-pixel; rough localization; principal axis analysis method; bisecting K-means

10.3969/J.ISSN.1000-5137.2016.04.008

2015-03-19

林菁,中国上海市徐汇区桂林路100号,上海师范大学信息与机电工程学院,邮编:200234,E-mail:lingjing@shnu.edu.cn

TG 806

A

1000-5137(2016)04-0434-07