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

邱運春,范 勇,肖德成,高 琳,陳念年,段晶晶

(西南科技大學計算機科學與技術學院,四川綿陽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.