一种新的亚像素边缘检测误差校正算法

邱运春,范 勇,肖德成,高 琳,陈念年,段晶晶

(西南科技大学计算机科学与技术学院,四川绵阳621010)

一种新的亚像素边缘检测误差校正算法

邱运春,范 勇,肖德成,高 琳,陈念年,段晶晶

(西南科技大学计算机科学与技术学院,四川绵阳621010)

矩方法采用二维理想边缘模型描述亚像素边缘,实际图像在边缘处存在一个渐变的过渡阶段,而二维理想边缘模型不能精确描述边缘,导致原理误差的产生。为此,提出一种采用误差校正表的算法,用于降低二维理想边缘模型引入的原理误差,提高亚像素边缘检测精度。通过方形采样定理模拟生成已知边缘的理想图像,用矩方法检测理想图像的亚像素边缘,构造二维误差校正表。使用查询误差校正表并结合双线性插值求出误差后进行误差校正。以灰度矩和Zernike矩为例进行对比实验,结果表明,该算法亚像素检测精度比校正前提高了一个数量级。校正算法主要计算量是双线性插值,能保持亚像素边缘检测的实时性。

亚像素;边缘检测;矩;理想边缘模型;误差校正表;双线性插值

1 概述

边缘是图像基本而重要的特征之一,高精度的边缘检测在图像处理和机器视觉中起着越来越重要的作用。亚像素边缘检测主要分为3类算法:基于拟合[1-2]的方法,基于插值[3-4]的方法和基于矩[5-7]的方法。其中,基于矩的亚像素边缘检测算法具有检测精度高、对噪声不敏感的优点,广泛应用于实际测量[8-9]中,并取得了很好的效果。

基于矩的亚像素边缘检测算法具有检测精度高、抗噪能力强的特点,被广泛应用到测量精度要求高的特征检测和视觉测量等。文献[5]提出基于矩的亚像素边缘检测算法。通过确定图像的前三阶灰度矩并利用矩不变性来估计图像边缘,最终准确地估计边缘模型的4个参数,还发现边缘位置与克里斯托夫数有关系。文献[6]提出了空间矩的概念,使用6个模板做卷积计算6阶空间矩,计算出边缘阶跃参数。文献[7]将Zernike矩应用于边缘检测,Zernike矩具有正交性和旋转不变性,所以检测中对噪声不敏感,仅使用3个模板做卷积,算法效率高于灰度矩和空间矩。

矩方法采用二维理想边缘模型,该模型认为像素在边缘附近灰度值直接发生突变,模型的参数相对较少,参数计算简单。但是实际图像边缘附近存在一个渐变的过渡阶段,而二维理想边缘模型并未考虑,导致二维理想边缘模型不能精确描述边缘,引入了原理误差。在空间矩中指出采用三级边缘模型,该模型会导致边缘参数计算非常复杂,边缘参数理论上可推导,但实际不行。最后通过建立误差校正表来降低空间矩的原理误差。

灰度矩和Zernike矩是建立在理想二维边缘模型上,同样存在原理误差。为此,本文提出用误差校正表校正误差的方法来校正灰度矩和Zernike矩亚像素边缘检测。

2 误差校正

2.1 误差来源

图1为矩方法采用的二维理想边缘阶跃模型。其中,亚像素边缘由4个参数表示,分别为背景灰度值h、阶跃值k、边缘直线到圆心距离l、边缘直线的法线与x轴正方向夹角φ,边缘模型建立在单位圆上。

图1 理想边缘模型

利用上述理想模型求解边缘参数,使得公式推导和参数计算相对简单,但是由于实际亚像素边缘不可能完全满足理想阶跃模型。也就是说在实际图像中,边缘附近的像素不可能直接发生突变,而是存在一个渐变的过程,二维理想边缘模型未考虑边缘附近的渐变,因此采用二维理想边缘模型的亚像素边缘检测算法都存在原理误差。

降低甚至避免原理误差对亚像素边缘检测的影响,可以提高实际测量中的检测精度。针对基于矩的亚像素边缘检测算法的精度提升有2种常用方法:(1)采用更加接近现实的模型三级灰度来描述边缘,即增加一个参数∂k来描述过渡阶段灰度值。三级边缘模型能更加真实地反映亚像素边缘特征,但是采用三级边缘模型一共有5个边缘参数需要计算,实际推导中发现采用三级边缘模型计算边缘参数非常复杂,很难推导出参数。(2)推导理想边缘模型下的误差函数[10]来进行误差补偿。实际中推导误差函数的方法同样是很困难的。因此,本文采用误差校正表的方法校正误差,结合双线性插值可以近似得到误差函数。

2.2 理想测试数据

构造误差校正表首先需要生成已知边缘距离l和边缘角度φ的理想测试数据,边缘模型建立在单位圆上,故l∈[-1,1],φ∈[0°,180°)。由于|l|＞0.6时亚像素边缘检测误差大,在生成理想测试数据和亚像素边缘检测时只考虑|l|≤0.6的情况,即生成理想测试数据范围为l∈[-0.6,0.6],φ∈[0°, 180°),本文以生成5×5大小理想测试数据为例说明构造方法。

为了获得理想测试数据,需要采用方形采样定理[11-12],即理想边缘是通过计算像素在一个方形的采样区域内的平均值得到,其采样结果就是离散矩阵灰度值。根据方形采样定理,CCD在固定面积和固定的时间间隔内对投射在它感光面上的光强进行积分,输出的结果就是图像的灰度值。由于CCD的积分面积和积分时间是固定的,因此它的输出灰度值只与它的感光面上的光强分布有关。对于某一个像素的灰度值输出可以表示为:

其中,f(i,j)为像素输出值,也就是灰度值;g(x,y)是连续图像的光强分布。由以上分析可以看出,像素的输出值是像素感光面上各部分光强综合作用的结果。

如图2中5×5的方格与一条直线相交,其中每个方格代表一个像素,为描述方便将方格从0开始编号,图中的直线代表边缘直线。

图2 5×5方格

每个像素的灰度值根据对应方格与边缘直线的位置关系来确定。如果某方格和边缘直线无交点,则分2种情况:如果方格在直线上方,那么此点的值就为h,如第0方格;否则在直线下方此点的值为h+k,如第24方格。如果方格和边缘直线有交点,根据方形采样定理,像素的值由背景灰度和阶跃后的灰度值共同决定,满足如下关系式:

图3 直线与方格相交

图4 直线与方格相交的3种情况

因为已知标准l和φ,所以可以得出边缘所在直线的方程式:y=ax+b,背景灰度k和阶跃后的灰度值h+k都已知,根据理想测试数据生成算法可生成已知l和φ的测试数据。

在实际产生理想测试数据时需要根据边缘角度φ的范围分别讨论:(1)φ=0°;(2)0°＜φ≤45°; (3)45°＜φ＜90°;(4)φ=90°;(5)90°＜φ≤135°;(6) 135°＜φ＜180°。上述6种情况的面积计算公式各不相同,需要分情况讨论,并结合直线与方格相交的3种情况逐一讨论即可求出所有的理想测试数据。

图5给出4组理想测试数据,其中,背景灰度h=100,阶跃值k=100。图5(a)中,l=0,theta=30;图5(b)中,l=0.15,theta=0;图5(c)中,l=0.3,theta=10;图5(d)中,l=0.35,theta=20。

图5 理想测试数据

2.3 误差校正表

令error(l,φ)为当边缘距离为l,边缘角度为φ时对应矩方法产生的误差。由误差定义可知:

其中,ld为矩方法计算出带有误差的边缘距离。生成l间隔0.05像素,φ间隔1°的理想测试数据,并分别用矩方法计算出ld,根据式(3)即可构造出误差校正表。

误差函数具有2个重要的对称性,利用对称性可以降低误差校正表存储空间:

(1)误差函数关于kπ/4对称,即:

所以在实际构造误差校正表时φ∈[0°,45°]。

(2)误差函数关于l=0的奇函数,即:所以误差校正表只需要构造l∈[0,0.6]。

综上所述,实际构造误差校正表时只需生成l间隔0.05像素,φ间隔1°且l∈[0,0.6],φ∈[0°,45°]的二维误差校正表,根据误差函数的对称性质即可求出其余的误差值。

2.4 误差校正公式及步骤

根据式(3)得到误差校正公式:

其中,ld是矩方法计算出的带有误差的边缘距离;error(l,φ)是对应的误差;l为校正后的误差。由于误差校正表是离散的二维表,校正时l,φ可能位于表格之间,此时误差校正表中没有对应值。为了使误差校正依然能运行,利用双线性插值对位于表格之间的误差求近似值,再利用式(6)进行误差校正。如图6所示,已知误差函数在Q11,Q12,Q21,Q22的值,需要得到误差函数在点p的值。

图6 p点的误差估计

记error(p)为误差函数在p点的函数值。首先进行φ方向的线性插值,得到函数在R1,R2点的估计值:

然后进行l方向的插值,就得到函数在p点的估计值:

综上所述,二维矩方法误差校正步骤如下: (1)生成l间隔0.05像素,φ间隔1°的理想测试数据。(2)利用矩方法求出ld,并构造误差校正表。(3)利用双线性插值估计误差error。(4)利用式(6)完成误差校正。

3 实验结果与分析

本文实验是在PC机(CPU为双核1.8 GHz,2 GB内存)上进行,通过VS2008开发平台编写代码并加载OpenCV函数库来实现误差校正算法。实验数据的分析和统计以及误差函数图像的可视化均采用Matalb2010实现。在实验中生成l间隔0.05像素,φ间隔1°的理想测试数据。用矩方法检测理想数据的边缘,并求出与真实边缘距离的误差值。图7～图9分别为灰度矩、空间矩、Zernike矩校正前后的三维误差图。所有坐标轴范围都一致。由图中可以看出,校正后的误差明显低于校正前的误差。

图7 灰度矩校正前后误差

图8 空间矩校正前后误差

图9 Zernike矩校正前后误差

利用Matalab统计校正前后误差的期望、方差、最大误差、最小误差。由于误差函数中存在负数,直接统计期望等会出现正负数抵消导致不能正确地反映检测的精度。误差的正负不反映误差的大小,在统计时将所有误差取绝对值统计。表1为矩方法校正前的误差。表2为校正后的误差数据统计。

表1 校正前的误差

表2 校正后的误差

由表1、表2的数据统计看出,校正后的边缘检测精度比校正前提高了一个数量级,将误差校正表方法用于灰度矩和 Zernike边缘检测同样有效。

为验证不同阶跃值k产生的理想测试数据对矩方法误差校正前后的影响,产生理想测试数据时固定背景灰度h=0,阶跃值k从1～255依次变化生成理想测试数据。用灰度矩、空间矩、Zernike矩对生成的理想测试数据求出误差值,并统计各个组误差的期望,如图10、图11分别为3种方法误差校正前后不同k值对误差影响的曲线。

图10 3种方法校正前不同k值对误差的影响

图11 3种方法校正后不同k值对误差的影响

由图10、图11可以看出当k＜15时,3种方法误差曲线变化较大。由于理想测试数据中与边缘直线相交的像素值由背景灰度和阶跃后灰度共同决定,当k值较小时像素值的舍入误差较大,导致理想测试数据精确度不高,使得亚像素边缘检测误差较大;当k≥15时,检测误差的期望趋于平稳,误差期望近似于表1、表2中的期望。

图12为90×221像素的灰度图,图13～图15分别为灰度矩、空间矩形和Zernike矩误差校正前后的边缘检测结果对比,本文实验中边缘阈值为50。

图12 实际图片

图13 灰度矩校正前后对比

图14 空间矩校正前后对比

图15 Zernike矩校正前后对比

从图14、图15中可以看出,空间矩和Zernike矩校正后算法检测的边缘信息明显比校正前丰富。而灰度矩校正前后效果不明显,笔者认为实际图像存在较大的噪声,而灰度矩对噪声敏感,导致校正效果不明显。

4 结束语

本文针对矩方法边缘检测存在的原理误差,采用误差校正表校正误差,通过构造理想测试图片生成误差校正表,并利用误差校正表的对称性减小校正表规模。实验结果表明,校正后比校正前检测精度提高了一个数量级。由于校正算法仅进行双线性插值,因此本文算法能够达到实时检测。本文算法仅考虑边缘距离的误差,而并未考虑误差较小的边缘角度误差,因此,针对边缘角度误差的校正算法将是下一步的研究内容。

[1] Hueckel M H.An Operator Which Locates Edges in Digitized Pictures[J].Journal of the ACM,1971,18 (1):113-125.

[2] 尚雅层,陈 静,田军委.高斯拟合亚像素边缘检测算法[J].计算机应用,2011,31(1):179-181.

[3] Haralick R M.Digital Step Edges from Zero Crossing of Second Directional Derivatives[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1984,6 (1):58-68.

[4] Zhao Ping,Zhao Wenzhen,Duan Zhenyun,etal. Subpixel-precise Edge Extraction Algorithm Based on FacetModel[C]//Proc.ofthe 4th International Conference on Computational and Information Sciences. [S.l.]:IEEE Press,2012:86-88.

[5] Tabatabai A J,Mitchell O R,Edge Location to Subpixel Values in Digital Imagery[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1984,6(2): 188-201.

[6] Lyvers E P.Subpixel Measurements Using a Moment-based Edge Operator[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1989,11(12):1293-1309.

[7] Ghosal S,Mehrotra R.Orthogonal Moment Operators for Subpixel Edge Detection[J].Pattern Recognition,1993, 26(2):295-306.

[8] 朱遵尚,刘肖琳.基于GPU的实时亚像素Harris角点检测[J].计算机工程,2010,36(12):213-215.

[9] 刘 倩,闫宇壮,黄新生.基于边缘特征的亚像素相关匹配跟踪算法[J].计算机工程,2011,37(8):201-203.

[10] 刘亚威.空间矩亚像素图像测量算法的研究[D].重庆:重庆大学,2003.

[11] Lyvers E P,Mitchell O R.Precision Edge Contrast and Orientation Estimation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(6):927-937.

[12] 贺忠海,廖怡白.理想边缘产生方法的研究[J].光学精密工程,2002,10(1):89-93.

编辑 顾逸斐

A New Error Correction Algorithm for Sub-pixel Edge Detection

QIU Yun-chun,FAN Yong,XIAO De-cheng,GAO Lin,CHEN Nian-nian,DUAN Jing-jing
(College of Computer Science&Technology,Southwest University of Science&Technology,Mianyang 621010,China)

Method of Moments uses two-dimensional ideal edge model to describe sub-pixel edge,but the actual image exists a gradual change on the edge.Thus leads to a principle error that the two-dimensional ideal edge model cannot accurately describe the edge.This paper presents an algorithm which uses an error correction table to regulate error.This algorithm can reduce the principle error from the two-dimensional ideal edge model.And it improves the accuracy of subpixel edge detection.A two-dimensional error correction table is constructed after detecting an ideal image’s sub-pixel edge by method of moments,and simulating the known edge of an ideal image by square sampling theorem.Error correction can be completed after computing the error by querying the error correction table combined with a bilinear interpolation.In a comparison test of gray moments and Zernike moments,experimental results show that compared with methods without regulation this method can effectively improve the accuracy of sub-pixel detection.For the main computational correction algorithm is bilinear interpolation,this method can maintain the real-time sub-pixel edge detection.

sub-pixel;edge detection;moment;ideal edge model;error correction table;bilinear interpolation

1000-3428(2014)10-0175-06

A

TP301.6

10.3969/j.issn.1000-3428.2014.10.033

省部共建先进制造技术联合实验室基金资助项目(12zxzk6);四川省科技创新苗子工程基金资助项目(2012ZZ070)。

邱运春(1990-),男,硕士研究生,主研方向:计算机视觉;范 勇,教授、博士;肖德成,讲师、硕士;高 琳(通讯作者),讲师、博士;陈念年,副教授、硕士;段晶晶,硕士研究生。

2013-09-03

2013-11-14E-mail:gaolinscu@163.com

中文引用格式:邱运春,范 勇,肖德成,等.一种新的亚像素边缘检测误差校正算法[J].计算机工程,2014, 40(10):175-180.

英文引用格式:Qiu Yunchun,Fan Yong,Xiao Decheng,et al.A New Error Correction Algorithm for Sub-pixel Edge Detection[J].Computer Engineering,2014,40(10):175-180.