無粗定位亞像素邊緣檢測算法研究

夏陽陽, 林　菁

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

?

無粗定位亞像素邊緣檢測算法研究

夏陽陽, 林菁

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

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

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

0　引　言

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

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

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

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

1　彩色圖像降維

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

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

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

(1)

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

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

(2)

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

(3)

其中α、β、γ表示主軸與r、g、b分量的夾角,從RGB模型可知,r、g、b3個分量兩兩正交,可得 cos2α+ cos2β+ cos2γ=1.主軸方向慣性矩最小,則bcosβ-gcosγ=0,bcosα-rcosγ=0,gcosα-rcosβ=0,計算即得α、β、γ值.為了減少運算復(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)

對Lena圖采用不同降維方法進行對比,效果如下:

圖1　降維算法對比圖

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

2　圖像濾波

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

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

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

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

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

3　亞像素邊緣檢測

3.1無粗定位的亞像素邊緣檢測算法

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

3.2高斯曲線擬合算法

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

(9)

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

(10)

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

3.3擬合點的選取

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

圖3　未篩選擬合曲線圖

圖4　準確篩選擬合曲線圖

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

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

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

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

3.4方向不變性

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

圖5　3個方向的梯度曲線

4　結(jié)果分析

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

4.1運算效率

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

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

4.2準確性

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

表1　運算結(jié)果對比表

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

4.3可靠性

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

本文作者提出的算法則是基于邊緣點附近梯度曲線的特性來對邊緣進行定位,掌握的邊緣信息較為全面,所以不會出現(xiàn)由于粗定位的不準確而導(dǎo)致定位的像素級的偏差,因此可靠性也優(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號,上海師范大學(xué)信息與機電工程學(xué)院,郵編:200234,E-mail:lingjing@shnu.edu.cn

TG 806

A

1000-5137(2016)04-0434-07