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

夏陽陽, 林　菁

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

?

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

夏陽陽, 林菁

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

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

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

0　引　言

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

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

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

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

1　彩色圖像降維

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

根據慣性矩性質可知,cosα、cosβ、cosγ服從如下關系:

(5)

解之,可得:

(6)

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

(7)

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

(8)

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

圖1　降維算法對比圖

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

2　圖像濾波

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

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

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

圖2　濾波結果對比圖

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

3　亞像素邊緣檢測

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

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

3.2高斯曲線擬合算法

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

(9)

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

(10)

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

3.3擬合點的選取

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

圖3　未篩選擬合曲線圖

圖4　準確篩選擬合曲線圖

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

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

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

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

3.4方向不變性

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

圖5　3個方向的梯度曲線

4　結果分析

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

4.1運算效率

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

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

4.2準確性

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

表1　運算結果對比表

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

4.3可靠性

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

本文作者提出的算法則是基于邊緣點附近梯度曲線的特性來對邊緣進行定位,掌握的邊緣信息較為全面,所以不會出現由于粗定位的不準確而導致定位的像素級的偏差,因此可靠性也優于傳統算法.

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

(責任編輯：包震宇)

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

林菁,中國上海市徐匯區桂林路100號,上海師范大學信息與機電工程學院,郵編:200234,E-mail:lingjing@shnu.edu.cn

TG 806

A

1000-5137(2016)04-0434-07