夏陽陽, 林　菁

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

?

無粗定位亞像素邊緣檢測(cè)算法研究

夏陽陽, 林菁

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

針對(duì)傳統(tǒng)的亞像素邊緣檢測(cè)技術(shù)需要先進(jìn)行粗定位,然后再進(jìn)行精確定位的問題,提出無粗定位亞像素邊緣檢測(cè)算法.針對(duì)彩色圖像降低維度邊緣信息損失的問題,提出主軸分析法來保存圖像的邊緣信息.針對(duì)濾波后圖像邊緣特征模糊的問題,提出基于二分K均值的中值濾波算法,在濾除噪聲的同時(shí),增強(qiáng)圖像的邊緣.最后從檢測(cè)精度、檢測(cè)效率和可靠性3個(gè)方面驗(yàn)證算法的有效性.

邊緣檢測(cè); 亞像素; 粗定位; 主軸分析法; 二分K均值

0　引　言

基于圖像的檢測(cè)技術(shù)具有低成本、高效率等優(yōu)點(diǎn),所以應(yīng)用十分廣泛.然而,傳統(tǒng)算法的定位精度只能達(dá)到像素級(jí),已經(jīng)不能滿足當(dāng)下高精度檢測(cè)的需求.因此,亞像素檢測(cè)的需求相當(dāng)迫切.常見的CCD器件的像元大小可達(dá)到5 μm,經(jīng)過亞像素定位,檢測(cè)精度可達(dá)0.01個(gè)像素級(jí),即測(cè)量精度可達(dá)0.1 μm,該精度已然能滿足幾乎所有的工業(yè)生產(chǎn)需求.

人類視覺系統(tǒng)接收到的圖像是彩色的,人腦處理的圖像信息也是彩色的,顯然彩色圖像更加符合人類的視覺感知,但是彩色圖像復(fù)雜的結(jié)構(gòu)以及龐大的數(shù)據(jù)量,導(dǎo)致圖像處理過程中遇到很多困難,因此必須對(duì)彩色圖像進(jìn)行降維.這里采用主軸分析法,在降低圖像維度的同時(shí),又完整保留了圖像的邊緣信息,為后續(xù)的檢測(cè)奠定良好的基礎(chǔ).

濾波是圖像處理的重要過程,因?yàn)橐M(jìn)行邊緣提取,所以選擇一種適合邊緣提取的去噪方法就尤為重要.本文作者提出了一種基于二分K均值的中值濾波算法,在圖像平滑前先對(duì)某領(lǐng)域范圍內(nèi)的像素點(diǎn)進(jìn)行聚類,然后根據(jù)聚類的結(jié)果判斷該范圍內(nèi)是否存在邊緣點(diǎn)和噪聲,最后根據(jù)判斷結(jié)果的不同采取不同的濾波策略,這樣就能夠有效地避免邊緣的模糊.

傳統(tǒng)的亞像素邊緣檢測(cè)算法可以分為插值法、擬合法和矩方法3種.這些算法的使用都有一個(gè)前提——已知目標(biāo)像素級(jí)的邊緣.這就會(huì)導(dǎo)致一個(gè)問題——如果粗定位定位得不夠準(zhǔn)確,那么精確定位就變得沒有意義.本算法擺脫了對(duì)粗定位的依賴,直接對(duì)邊緣進(jìn)行亞像素檢測(cè).

1　彩色圖像降維

將RGB圖像轉(zhuǎn)化為灰度圖像的表達(dá)式近似為Gray=0.3R+0.6G+0.1B,假設(shè)存在這樣一幅圖像——左側(cè)R=200,G=0,B=0,右側(cè)R=0,G=100,B=0,計(jì)算可得左右兩側(cè)的灰度都是60,即不存在邊緣,但顯然邊緣是存在的,這就是邊緣信息的損失.利用彩色信息的豐富性可以有效解決這一問題.

彩色圖像的邊緣檢測(cè)算法可分為輸出融合法和向量法,輸出融合法沒有考慮顏色分量間的相互關(guān)系且對(duì)顏色模型較為依賴.向量法運(yùn)算復(fù)雜,如果直接運(yùn)用于亞像素邊緣檢測(cè),那么算法的實(shí)時(shí)性將得不到保證,所以必須要對(duì)彩色圖像進(jìn)行降維.

彩色圖像處理有三大難點(diǎn)——存儲(chǔ)量大、運(yùn)算量大、冗余度高.R、G、B3個(gè)分量包含的特征信息大部分是相同的,所以數(shù)據(jù)分析前要進(jìn)行預(yù)處理,消除冗余變量,使數(shù)據(jù)分析能夠高效地進(jìn)行.主軸分析法[1-4]就是能夠?qū)崿F(xiàn)該功能的方法之一.令x=(X1,X2,…Xn)T為維變量,對(duì)其采用線性變換:

(1)

由線性正交變換原理可得:正交變換后,可以用較少的分量表示多個(gè)分量,同時(shí)仍然保留分量的特征信息.對(duì)比度大小是正交變換在圖像處理中的表現(xiàn)形式,可通過慣性矩的大小來表示,值越小,特征信息保留的就越多.當(dāng)慣性矩取值最小時(shí),可得圖像顏色空間的主軸,將彩色圖像通過該主軸投影轉(zhuǎn)化為灰度圖像時(shí),圖像的特征信息保留得最為完整,邊緣信息的損失最小.

對(duì)于任意一幅圖像,主軸的原點(diǎn)為彩色空間的質(zhì)心:

(2)

其中,ri、gi、bi表示彩色圖像中第i個(gè)像素對(duì)應(yīng)的3個(gè)顏色分量的值,N表示圖像中像素的總數(shù),圖像中所有像素點(diǎn)的慣性矩為:

(3)

其中α、β、γ表示主軸與r、g、b分量的夾角,從RGB模型可知,r、g、b3個(gè)分量?jī)蓛烧?可得 cos2α+ cos2β+ cos2γ=1.主軸方向慣性矩最小,則bcosβ-gcosγ=0,bcosα-rcosγ=0,gcosα-rcosβ=0,計(jì)算即得α、β、γ值.為了減少運(yùn)算復(fù)雜度,將三維矩ms,t,u定義為:

(4)

根據(jù)慣性矩性質(zhì)可知,cosα、cosβ、cosγ服從如下關(guān)系:

(5)

解之,可得:

(6)

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

(7)

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

(8)

對(duì)Lena圖采用不同降維方法進(jìn)行對(duì)比,效果如下:

圖1　降維算法對(duì)比圖

圖1(c)的權(quán)值比較符合人類的視覺感受,所以看似比較清晰,但是仔細(xì)觀察就可以發(fā)現(xiàn),圖像的邊緣存在模糊,眼角部位尤其明顯;而圖1(b)的邊緣則明顯比較清晰,雖然整體圖像看起來沒有圖1(c)舒服,但是圖像的邊緣信息保留得十分完整.

2　圖像濾波

圖像采集過程通中不可避免地會(huì)混入噪聲,找到一種適合亞像素邊緣檢測(cè)濾波算法是準(zhǔn)確定位的前提.中值濾波在保存圖像邊緣信息方面有著不錯(cuò)的表現(xiàn),因此基于中值濾波提出基于二分K均值的中值濾波法[5-9].該算法的流程為:

(1) 對(duì)某領(lǐng)域范圍內(nèi)的像素點(diǎn)Ai進(jìn)行排序運(yùn)算,排序可以使聚類的運(yùn)算量大大減少.

(2) 將Ai聚集成三類——普通點(diǎn)、邊緣點(diǎn)和噪聲.這里采用運(yùn)算效率比較高的二分K均值進(jìn)行聚類運(yùn)算.二分K均值算法克服了K均值算法對(duì)初始中心點(diǎn)的選擇較為依賴的問題,其主要思想為:首先將所有待聚類的點(diǎn)分為兩個(gè)簇,然后對(duì)聚類效果最差的簇再次聚類,以此類推,直到簇的數(shù)目等于用戶給定的數(shù)目為止.采用該算法得到的結(jié)果不依賴于初始中心點(diǎn)的選擇,誤差平方和小,聚類性能優(yōu)越.

圖2　濾波結(jié)果對(duì)比圖

圖2(a)為加上椒鹽噪聲后的圖像,圖2(b)為本文作者提出的濾波方法濾波后的圖像,圖2(c)為中值濾波后的圖像.對(duì)比可得,基于K均值的中值濾波法在濾除高頻噪聲的同時(shí),不但可以保證圖像細(xì)節(jié)和邊緣信息的完整,還能增強(qiáng)圖像的邊緣,為后續(xù)的處理打下良好的基礎(chǔ).

3　亞像素邊緣檢測(cè)

3.1無粗定位的亞像素邊緣檢測(cè)算法

傳統(tǒng)的亞像素邊緣檢測(cè)算法都需要進(jìn)行粗定位[10-12],如果粗定位得不夠準(zhǔn)確,最后的亞像素檢測(cè)結(jié)果與實(shí)際結(jié)果將會(huì)有1個(gè)像素以上的偏差,作者將擺脫對(duì)粗定位的依賴,直接進(jìn)行亞像素檢測(cè),大大提高檢測(cè)結(jié)果的可靠性.

3.2高斯曲線擬合算法

通過對(duì)梯度圖像進(jìn)行觀察可以發(fā)現(xiàn),邊緣附近梯度值的變化趨勢(shì)化較接近于高斯曲線,所以采用邊緣附近的高斯擬合來求亞像素坐標(biāo).高斯曲線的表達(dá)式為:

(9)

其中μ為均值,也是高斯曲線的對(duì)稱軸,即亞像素的位置.由于高斯曲線表達(dá)式比較復(fù)雜,直接擬合比較困難,為了找出μ的位置同時(shí)簡(jiǎn)化運(yùn)算,對(duì)等式兩邊取對(duì)數(shù):

(10)

即可得到形如y=ax2+bx+c的表達(dá)式,即典型的拋物線,這樣就可以使得運(yùn)算的過程大大簡(jiǎn)化.

3.3擬合點(diǎn)的選取

通常在擬合前,要對(duì)擬合點(diǎn)進(jìn)行篩選.由于干擾和噪聲的存在,邊緣附近像素點(diǎn)的梯度值并不是完全符合高斯曲線變化趨勢(shì)的,所以要對(duì)梯度值進(jìn)行篩選.如果不經(jīng)篩選直接選擇固定數(shù)量的點(diǎn)來進(jìn)行擬合,就會(huì)導(dǎo)致擬合出的曲線偏離實(shí)際曲線,如圖3所示.

圖3　未篩選擬合曲線圖

圖4　準(zhǔn)確篩選擬合曲線圖

圖3中實(shí)線為實(shí)際邊緣曲線,虛線為擬合的曲線,顯然兩者的對(duì)稱軸并不位于同一像素內(nèi).根據(jù)拋物線原理,三點(diǎn)就可以完全確定一條拋物線,因此如果擬合點(diǎn)選擇得過少,就會(huì)導(dǎo)致擬合曲線完全取決于所選擇的擬合點(diǎn),曲線的邊緣信息也會(huì)因?yàn)閾p耗而變得不完整.綜上,采用如下算法來選取擬合點(diǎn):

(1) 找到梯度值最大的點(diǎn):如果某點(diǎn)的梯度值大于其左右3點(diǎn)的梯度值,則認(rèn)為該點(diǎn)為梯度值局部最大點(diǎn),如圖3中的第6點(diǎn);

(2) 沿著梯度值最的大點(diǎn)依次向左和向右尋找梯度值遞減的點(diǎn),最左邊的點(diǎn)作為起始點(diǎn),最右邊的點(diǎn)作為終點(diǎn):圖3中第5點(diǎn)為起始點(diǎn),第8點(diǎn)為終點(diǎn),如果直接選擇第5點(diǎn)到第8點(diǎn)進(jìn)行擬合,則會(huì)因?yàn)檫x取的點(diǎn)過少而導(dǎo)致擬合結(jié)果的偏差;

此算法的目的是為了防止擬合點(diǎn)中存在某一個(gè)不符合高斯曲線變化規(guī)律的點(diǎn),從而導(dǎo)致符合規(guī)律的點(diǎn)的漏取,同時(shí)也可以防止邊緣信息的損失.經(jīng)過改進(jìn)的擬合點(diǎn)選取算法選擇出的擬合點(diǎn)擬合出的曲線圖4所示.其中,實(shí)線為實(shí)際梯度曲線,虛線為擬合曲線,兩者的對(duì)稱軸幾乎一致.另外對(duì)梯度值進(jìn)行篩選后,由于擬合點(diǎn)的減少,高斯-牛頓擬合法的運(yùn)算量也大大降低,擬合效率也變得更高.

3.4方向不變性

梯度是具有方向性的,在求圖像的梯度時(shí),通常認(rèn)為梯度向量的模就是梯度的大小,梯度的方向也是各不相同.采取新的思路——沿某一直線方向上求圖像的梯度值,這樣,像素點(diǎn)的梯度在方向上就是一致的.過某一邊緣點(diǎn),求3個(gè)方向的梯度值,其梯度曲線如圖5所示.

圖5　3個(gè)方向的梯度曲線

4　結(jié)果分析

采用VS2010編程軟件進(jìn)行仿真,從運(yùn)算速度,運(yùn)算的準(zhǔn)確性和可靠性3個(gè)方面來分別討論本算法與傳統(tǒng)算法的優(yōu)劣:

4.1運(yùn)算效率

傳統(tǒng)算法首先要進(jìn)行粗定位,然后進(jìn)行亞像素邊緣檢測(cè),以canny算子為例,主要的運(yùn)算流程如下:(1)采用Canny算子計(jì)算梯度大小和方向;(2)采取非極大值抑制;(3)亞像素檢測(cè).而本算法流程如下:(1)求出整幅圖像的梯度值;(2)找到水平方向上符合擬合要求的梯度值的點(diǎn),進(jìn)行擬合.

通過對(duì)比可得,本算法不需要計(jì)算梯度的方向,不需要進(jìn)行非極大值抑制,且梯度值計(jì)算相對(duì)簡(jiǎn)單,但是擬合運(yùn)算較傳統(tǒng)算法相對(duì)復(fù)雜.下面將通過仿真比較兩種算法的運(yùn)算時(shí)間.傳統(tǒng)算法運(yùn)算中,先通過傳統(tǒng)算法計(jì)算出整幅圖像梯度值,然后在邊緣附近某一小范圍內(nèi)計(jì)算梯度方向確定邊緣,最后根據(jù)確定的邊緣通過傳統(tǒng)的擬合法計(jì)算亞像素坐標(biāo).本算法運(yùn)算中,先計(jì)算出整幅圖像的梯度值,然后需找符合擬合要求的點(diǎn),進(jìn)行高斯擬合,從而確定亞像素位置.實(shí)際運(yùn)算中,傳統(tǒng)算法的運(yùn)算時(shí)間為672 ms,而新算法的運(yùn)算時(shí)間為438 ms,可見運(yùn)算時(shí)間減少了,運(yùn)算效率提高了.

4.2準(zhǔn)確性

在實(shí)際運(yùn)算之前,對(duì)圖像進(jìn)行了計(jì)算與分析,可以確定點(diǎn)(197,25)點(diǎn)為邊緣點(diǎn),下面通過兩種方法確定該點(diǎn)的亞像素位置,結(jié)果如表1所示.

表1　運(yùn)算結(jié)果對(duì)比表

表1中小數(shù)點(diǎn)后兩位的值是完全一致的(多次仿真小數(shù)點(diǎn)后兩位的值完全一致),即定位精度達(dá)到了0.01個(gè)像素級(jí),工業(yè)CCD器件的像元大小可達(dá)到5 μm,經(jīng)過亞像素定位,檢測(cè)精度可達(dá)0.1 μm,因此本算法的精度可準(zhǔn)確性都符合要求.

4.3可靠性

傳統(tǒng)邊緣算法的粗定位環(huán)節(jié)都需要根據(jù)選定的閾值T判斷該點(diǎn)是否為邊緣點(diǎn).T值的選擇具有不確定性,過大則會(huì)導(dǎo)致邊緣點(diǎn)的漏取,造成邊緣曲線的不封閉,過小則會(huì)導(dǎo)致邊緣點(diǎn)的誤取,造成粗定位像素級(jí)的偏差.雖然雙閾值法可緩解該問題,但并不能完全解決該問題.

本文作者提出的算法則是基于邊緣點(diǎn)附近梯度曲線的特性來對(duì)邊緣進(jìn)行定位,掌握的邊緣信息較為全面,所以不會(huì)出現(xiàn)由于粗定位的不準(zhǔn)確而導(dǎo)致定位的像素級(jí)的偏差,因此可靠性也優(yōu)于傳統(tǒng)算法.

[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.

(責(zé)任編輯：包震宇)

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

林菁,中國上海市徐匯區(qū)桂林路100號(hào),上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:lingjing@shnu.edu.cn

TG 806

A

1000-5137(2016)04-0434-07