邱運(yùn)春,范 勇,肖德成,高 琳,陳念年,段晶晶

(西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,四川綿陽621010)

一種新的亞像素邊緣檢測誤差校正算法

邱運(yùn)春,范 勇,肖德成,高 琳,陳念年,段晶晶

(西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,四川綿陽621010)

矩方法采用二維理想邊緣模型描述亞像素邊緣,實(shí)際圖像在邊緣處存在一個漸變的過渡階段,而二維理想邊緣模型不能精確描述邊緣,導(dǎo)致原理誤差的產(chǎn)生。為此,提出一種采用誤差校正表的算法,用于降低二維理想邊緣模型引入的原理誤差,提高亞像素邊緣檢測精度。通過方形采樣定理模擬生成已知邊緣的理想圖像,用矩方法檢測理想圖像的亞像素邊緣,構(gòu)造二維誤差校正表。使用查詢誤差校正表并結(jié)合雙線性插值求出誤差后進(jìn)行誤差校正。以灰度矩和Zernike矩為例進(jìn)行對比實(shí)驗(yàn),結(jié)果表明,該算法亞像素檢測精度比校正前提高了一個數(shù)量級。校正算法主要計(jì)算量是雙線性插值,能保持亞像素邊緣檢測的實(shí)時性。

亞像素;邊緣檢測;矩;理想邊緣模型;誤差校正表;雙線性插值

1 概述

邊緣是圖像基本而重要的特征之一,高精度的邊緣檢測在圖像處理和機(jī)器視覺中起著越來越重要的作用。亞像素邊緣檢測主要分為3類算法:基于擬合[1-2]的方法,基于插值[3-4]的方法和基于矩[5-7]的方法。其中,基于矩的亞像素邊緣檢測算法具有檢測精度高、對噪聲不敏感的優(yōu)點(diǎn),廣泛應(yīng)用于實(shí)際測量[8-9]中,并取得了很好的效果。

基于矩的亞像素邊緣檢測算法具有檢測精度高、抗噪能力強(qiáng)的特點(diǎn),被廣泛應(yīng)用到測量精度要求高的特征檢測和視覺測量等。文獻(xiàn)[5]提出基于矩的亞像素邊緣檢測算法。通過確定圖像的前三階灰度矩并利用矩不變性來估計(jì)圖像邊緣,最終準(zhǔn)確地估計(jì)邊緣模型的4個參數(shù),還發(fā)現(xiàn)邊緣位置與克里斯托夫數(shù)有關(guān)系。文獻(xiàn)[6]提出了空間矩的概念,使用6個模板做卷積計(jì)算6階空間矩,計(jì)算出邊緣階躍參數(shù)。文獻(xiàn)[7]將Zernike矩應(yīng)用于邊緣檢測,Zernike矩具有正交性和旋轉(zhuǎn)不變性,所以檢測中對噪聲不敏感,僅使用3個模板做卷積,算法效率高于灰度矩和空間矩。

矩方法采用二維理想邊緣模型,該模型認(rèn)為像素在邊緣附近灰度值直接發(fā)生突變,模型的參數(shù)相對較少,參數(shù)計(jì)算簡單。但是實(shí)際圖像邊緣附近存在一個漸變的過渡階段,而二維理想邊緣模型并未考慮,導(dǎo)致二維理想邊緣模型不能精確描述邊緣,引入了原理誤差。在空間矩中指出采用三級邊緣模型,該模型會導(dǎo)致邊緣參數(shù)計(jì)算非常復(fù)雜,邊緣參數(shù)理論上可推導(dǎo),但實(shí)際不行。最后通過建立誤差校正表來降低空間矩的原理誤差。

灰度矩和Zernike矩是建立在理想二維邊緣模型上,同樣存在原理誤差。為此,本文提出用誤差校正表校正誤差的方法來校正灰度矩和Zernike矩亞像素邊緣檢測。

2 誤差校正

2.1 誤差來源

圖1為矩方法采用的二維理想邊緣階躍模型。其中,亞像素邊緣由4個參數(shù)表示,分別為背景灰度值h、階躍值k、邊緣直線到圓心距離l、邊緣直線的法線與x軸正方向夾角φ,邊緣模型建立在單位圓上。

圖1 理想邊緣模型

利用上述理想模型求解邊緣參數(shù),使得公式推導(dǎo)和參數(shù)計(jì)算相對簡單,但是由于實(shí)際亞像素邊緣不可能完全滿足理想階躍模型。也就是說在實(shí)際圖像中,邊緣附近的像素不可能直接發(fā)生突變,而是存在一個漸變的過程,二維理想邊緣模型未考慮邊緣附近的漸變,因此采用二維理想邊緣模型的亞像素邊緣檢測算法都存在原理誤差。

降低甚至避免原理誤差對亞像素邊緣檢測的影響,可以提高實(shí)際測量中的檢測精度。針對基于矩的亞像素邊緣檢測算法的精度提升有2種常用方法:(1)采用更加接近現(xiàn)實(shí)的模型三級灰度來描述邊緣,即增加一個參數(shù)?k來描述過渡階段灰度值。三級邊緣模型能更加真實(shí)地反映亞像素邊緣特征,但是采用三級邊緣模型一共有5個邊緣參數(shù)需要計(jì)算,實(shí)際推導(dǎo)中發(fā)現(xiàn)采用三級邊緣模型計(jì)算邊緣參數(shù)非常復(fù)雜,很難推導(dǎo)出參數(shù)。(2)推導(dǎo)理想邊緣模型下的誤差函數(shù)[10]來進(jìn)行誤差補(bǔ)償。實(shí)際中推導(dǎo)誤差函數(shù)的方法同樣是很困難的。因此,本文采用誤差校正表的方法校正誤差,結(jié)合雙線性插值可以近似得到誤差函數(shù)。

2.2 理想測試數(shù)據(jù)

構(gòu)造誤差校正表首先需要生成已知邊緣距離l和邊緣角度φ的理想測試數(shù)據(jù),邊緣模型建立在單位圓上,故l∈[-1,1],φ∈[0°,180°)。由于|l|＞0.6時亞像素邊緣檢測誤差大,在生成理想測試數(shù)據(jù)和亞像素邊緣檢測時只考慮|l|≤0.6的情況,即生成理想測試數(shù)據(jù)范圍為l∈[-0.6,0.6],φ∈[0°, 180°),本文以生成5×5大小理想測試數(shù)據(jù)為例說明構(gòu)造方法。

為了獲得理想測試數(shù)據(jù),需要采用方形采樣定理[11-12],即理想邊緣是通過計(jì)算像素在一個方形的采樣區(qū)域內(nèi)的平均值得到,其采樣結(jié)果就是離散矩陣灰度值。根據(jù)方形采樣定理,CCD在固定面積和固定的時間間隔內(nèi)對投射在它感光面上的光強(qiáng)進(jìn)行積分,輸出的結(jié)果就是圖像的灰度值。由于CCD的積分面積和積分時間是固定的,因此它的輸出灰度值只與它的感光面上的光強(qiáng)分布有關(guān)。對于某一個像素的灰度值輸出可以表示為:

其中,f(i,j)為像素輸出值,也就是灰度值;g(x,y)是連續(xù)圖像的光強(qiáng)分布。由以上分析可以看出,像素的輸出值是像素感光面上各部分光強(qiáng)綜合作用的結(jié)果。

如圖2中5×5的方格與一條直線相交,其中每個方格代表一個像素,為描述方便將方格從0開始編號,圖中的直線代表邊緣直線。

圖2 5×5方格

每個像素的灰度值根據(jù)對應(yīng)方格與邊緣直線的位置關(guān)系來確定。如果某方格和邊緣直線無交點(diǎn),則分2種情況:如果方格在直線上方,那么此點(diǎn)的值就為h,如第0方格;否則在直線下方此點(diǎn)的值為h+k,如第24方格。如果方格和邊緣直線有交點(diǎn),根據(jù)方形采樣定理,像素的值由背景灰度和階躍后的灰度值共同決定,滿足如下關(guān)系式:

圖3 直線與方格相交

圖4 直線與方格相交的3種情況

因?yàn)橐阎獦?biāo)準(zhǔn)l和φ,所以可以得出邊緣所在直線的方程式:y=ax+b,背景灰度k和階躍后的灰度值h+k都已知,根據(jù)理想測試數(shù)據(jù)生成算法可生成已知l和φ的測試數(shù)據(jù)。

在實(shí)際產(chǎn)生理想測試數(shù)據(jù)時需要根據(jù)邊緣角度φ的范圍分別討論:(1)φ=0°;(2)0°＜φ≤45°; (3)45°＜φ＜90°;(4)φ=90°;(5)90°＜φ≤135°;(6) 135°＜φ＜180°。上述6種情況的面積計(jì)算公式各不相同,需要分情況討論,并結(jié)合直線與方格相交的3種情況逐一討論即可求出所有的理想測試數(shù)據(jù)。

圖5給出4組理想測試數(shù)據(jù),其中,背景灰度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 理想測試數(shù)據(jù)

2.3 誤差校正表

令error(l,φ)為當(dāng)邊緣距離為l,邊緣角度為φ時對應(yīng)矩方法產(chǎn)生的誤差。由誤差定義可知:

其中,ld為矩方法計(jì)算出帶有誤差的邊緣距離。生成l間隔0.05像素,φ間隔1°的理想測試數(shù)據(jù),并分別用矩方法計(jì)算出ld,根據(jù)式(3)即可構(gòu)造出誤差校正表。

誤差函數(shù)具有2個重要的對稱性,利用對稱性可以降低誤差校正表存儲空間:

(1)誤差函數(shù)關(guān)于kπ/4對稱,即:

所以在實(shí)際構(gòu)造誤差校正表時φ∈[0°,45°]。

(2)誤差函數(shù)關(guān)于l=0的奇函數(shù),即:所以誤差校正表只需要構(gòu)造l∈[0,0.6]。

綜上所述,實(shí)際構(gòu)造誤差校正表時只需生成l間隔0.05像素,φ間隔1°且l∈[0,0.6],φ∈[0°,45°]的二維誤差校正表,根據(jù)誤差函數(shù)的對稱性質(zhì)即可求出其余的誤差值。

2.4 誤差校正公式及步驟

根據(jù)式(3)得到誤差校正公式:

其中,ld是矩方法計(jì)算出的帶有誤差的邊緣距離;error(l,φ)是對應(yīng)的誤差;l為校正后的誤差。由于誤差校正表是離散的二維表,校正時l,φ可能位于表格之間,此時誤差校正表中沒有對應(yīng)值。為了使誤差校正依然能運(yùn)行,利用雙線性插值對位于表格之間的誤差求近似值,再利用式(6)進(jìn)行誤差校正。如圖6所示,已知誤差函數(shù)在Q11,Q12,Q21,Q22的值,需要得到誤差函數(shù)在點(diǎn)p的值。

圖6 p點(diǎn)的誤差估計(jì)

記error(p)為誤差函數(shù)在p點(diǎn)的函數(shù)值。首先進(jìn)行φ方向的線性插值,得到函數(shù)在R1,R2點(diǎn)的估計(jì)值:

然后進(jìn)行l(wèi)方向的插值,就得到函數(shù)在p點(diǎn)的估計(jì)值:

綜上所述,二維矩方法誤差校正步驟如下: (1)生成l間隔0.05像素,φ間隔1°的理想測試數(shù)據(jù)。(2)利用矩方法求出ld,并構(gòu)造誤差校正表。(3)利用雙線性插值估計(jì)誤差error。(4)利用式(6)完成誤差校正。

3 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)是在PC機(jī)(CPU為雙核1.8 GHz,2 GB內(nèi)存)上進(jìn)行,通過VS2008開發(fā)平臺編寫代碼并加載OpenCV函數(shù)庫來實(shí)現(xiàn)誤差校正算法。實(shí)驗(yàn)數(shù)據(jù)的分析和統(tǒng)計(jì)以及誤差函數(shù)圖像的可視化均采用Matalb2010實(shí)現(xiàn)。在實(shí)驗(yàn)中生成l間隔0.05像素,φ間隔1°的理想測試數(shù)據(jù)。用矩方法檢測理想數(shù)據(jù)的邊緣,并求出與真實(shí)邊緣距離的誤差值。圖7～圖9分別為灰度矩、空間矩、Zernike矩校正前后的三維誤差圖。所有坐標(biāo)軸范圍都一致。由圖中可以看出,校正后的誤差明顯低于校正前的誤差。

圖7 灰度矩校正前后誤差

圖8 空間矩校正前后誤差

圖9 Zernike矩校正前后誤差

利用Matalab統(tǒng)計(jì)校正前后誤差的期望、方差、最大誤差、最小誤差。由于誤差函數(shù)中存在負(fù)數(shù),直接統(tǒng)計(jì)期望等會出現(xiàn)正負(fù)數(shù)抵消導(dǎo)致不能正確地反映檢測的精度。誤差的正負(fù)不反映誤差的大小,在統(tǒng)計(jì)時將所有誤差取絕對值統(tǒng)計(jì)。表1為矩方法校正前的誤差。表2為校正后的誤差數(shù)據(jù)統(tǒng)計(jì)。

表1 校正前的誤差

表2 校正后的誤差

由表1、表2的數(shù)據(jù)統(tǒng)計(jì)看出,校正后的邊緣檢測精度比校正前提高了一個數(shù)量級,將誤差校正表方法用于灰度矩和 Zernike邊緣檢測同樣有效。

為驗(yàn)證不同階躍值k產(chǎn)生的理想測試數(shù)據(jù)對矩方法誤差校正前后的影響,產(chǎn)生理想測試數(shù)據(jù)時固定背景灰度h=0,階躍值k從1～255依次變化生成理想測試數(shù)據(jù)。用灰度矩、空間矩、Zernike矩對生成的理想測試數(shù)據(jù)求出誤差值,并統(tǒng)計(jì)各個組誤差的期望,如圖10、圖11分別為3種方法誤差校正前后不同k值對誤差影響的曲線。

圖10 3種方法校正前不同k值對誤差的影響

圖11 3種方法校正后不同k值對誤差的影響

由圖10、圖11可以看出當(dāng)k＜15時,3種方法誤差曲線變化較大。由于理想測試數(shù)據(jù)中與邊緣直線相交的像素值由背景灰度和階躍后灰度共同決定,當(dāng)k值較小時像素值的舍入誤差較大,導(dǎo)致理想測試數(shù)據(jù)精確度不高,使得亞像素邊緣檢測誤差較大;當(dāng)k≥15時,檢測誤差的期望趨于平穩(wěn),誤差期望近似于表1、表2中的期望。

圖12為90×221像素的灰度圖,圖13～圖15分別為灰度矩、空間矩形和Zernike矩誤差校正前后的邊緣檢測結(jié)果對比,本文實(shí)驗(yàn)中邊緣閾值為50。

圖12 實(shí)際圖片

圖13 灰度矩校正前后對比

圖14 空間矩校正前后對比

圖15 Zernike矩校正前后對比

從圖14、圖15中可以看出,空間矩和Zernike矩校正后算法檢測的邊緣信息明顯比校正前豐富。而灰度矩校正前后效果不明顯,筆者認(rèn)為實(shí)際圖像存在較大的噪聲,而灰度矩對噪聲敏感,導(dǎo)致校正效果不明顯。

4 結(jié)束語

本文針對矩方法邊緣檢測存在的原理誤差,采用誤差校正表校正誤差,通過構(gòu)造理想測試圖片生成誤差校正表,并利用誤差校正表的對稱性減小校正表規(guī)模。實(shí)驗(yàn)結(jié)果表明,校正后比校正前檢測精度提高了一個數(shù)量級。由于校正算法僅進(jìn)行雙線性插值,因此本文算法能夠達(dá)到實(shí)時檢測。本文算法僅考慮邊緣距離的誤差,而并未考慮誤差較小的邊緣角度誤差,因此,針對邊緣角度誤差的校正算法將是下一步的研究內(nèi)容。

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

[2] 尚雅層,陳 靜,田軍委.高斯擬合亞像素邊緣檢測算法[J].計(jì)算機(jī)應(yīng)用,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的實(shí)時亞像素Harris角點(diǎn)檢測[J].計(jì)算機(jī)工程,2010,36(12):213-215.

[9] 劉 倩,閆宇壯,黃新生.基于邊緣特征的亞像素相關(guān)匹配跟蹤算法[J].計(jì)算機(jī)工程,2011,37(8):201-203.

[10] 劉亞威.空間矩亞像素圖像測量算法的研究[D].重慶:重慶大學(xué),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] 賀忠海,廖怡白.理想邊緣產(chǎn)生方法的研究[J].光學(xué)精密工程,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

省部共建先進(jìn)制造技術(shù)聯(lián)合實(shí)驗(yàn)室基金資助項(xiàng)目(12zxzk6);四川省科技創(chuàng)新苗子工程基金資助項(xiàng)目(2012ZZ070)。

邱運(yùn)春(1990-),男,碩士研究生,主研方向:計(jì)算機(jī)視覺;范 勇,教授、博士;肖德成,講師、碩士;高 琳(通訊作者),講師、博士;陳念年,副教授、碩士;段晶晶,碩士研究生。

2013-09-03

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

中文引用格式:邱運(yùn)春,范 勇,肖德成,等.一種新的亞像素邊緣檢測誤差校正算法[J].計(jì)算機(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.