結(jié)合PCA與HEIV的橢圓目標(biāo)檢測算法

韓建棟，溫 靜

HAN Jiandong,WEN Jing

山西大學(xué) 計算機(jī)與信息技術(shù)學(xué)院，計算智能與中文信息處理教育部重點實驗室，太原 030006

School of Computer and Information Technology,Key Laboratory of Ministry of Education for Computational Intelligence and Chinese Information Processing,Shanxi University,Taiyuan 030006,China

橢圓是計算機(jī)視覺中常見的圖像特征，在眾多計算機(jī)視覺應(yīng)用中，都需要對橢圓進(jìn)行檢測，如生物醫(yī)學(xué)中細(xì)胞顯微圖像的自動判讀、工業(yè)生產(chǎn)中圓形產(chǎn)品自動檢測、視覺測量中人造圓形標(biāo)志點的精確定位等。因此，橢圓檢測在基于圖像的識別與測量領(lǐng)域中具有非常重要的意義。

任意橢圓具有5個參數(shù)，橢圓檢測就是對橢圓進(jìn)行識別并確定橢圓的5個參數(shù)。目前常見的橢圓檢測算法主要有：Hough變換法與曲線擬合法。傳統(tǒng)的Hough變換[1]將圖像空間映射到五維參數(shù)空間進(jìn)行統(tǒng)計，計算效率很低。為此，Xu等[2]提出了隨機(jī)Hough變換法，通過隨機(jī)抽取5個點計算橢圓參數(shù)，降低了計算量，但是當(dāng)邊緣點數(shù)較大時，該方法由于無目標(biāo)地隨機(jī)采樣會引入大量的無效計算，導(dǎo)致算法性能降低[3]，為了進(jìn)一步克服Hough變換對時空需求高的缺點，提出各種一維Hough的橢圓檢測算法[4-8]，如Xie[4]等提出利用橢圓長軸的兩個頂點與橢圓上另外一點來確定橢圓參數(shù)的方法，該方法僅需要一個一維累加器來統(tǒng)計短軸長度信息，降低了檢測的復(fù)雜度，但是檢測精度較低。曲線擬合法是事先知道待測目標(biāo)為橢圓的前提下，根據(jù)測量得到的邊緣點坐標(biāo)估計橢圓的參數(shù)，如最小二乘擬合法[9-11]、基于RANSAC的橢圓檢測法[12-13]等。

在機(jī)器視覺測量中，常常需要對自然場景中的人造橢圓目標(biāo)進(jìn)行識別與精確定位，而自然場景中往往存在眾多干擾目標(biāo)。因此，在采用橢圓定位之前有必要剔除場景中的非橢圓及近似橢圓目標(biāo)。考慮到橢圓長軸對應(yīng)于橢圓主元方向的特點，本文提出一種基于主元變換法的橢圓自動識別方法，利用主元變換將任意橢圓轉(zhuǎn)化為標(biāo)準(zhǔn)型橢圓，將橢圓輪廓度誤差作為識別橢圓的評價依據(jù)，并考慮數(shù)據(jù)的異方差性，實現(xiàn)橢圓目標(biāo)的精確定位，該方法簡化了橢圓檢測過程，且具有較高的定位精度。

1 主元變換及其特點

主元變換法[14]（Principal Components Transform）是一種基于圖像統(tǒng)計特性的變換，又稱特征值變換或離散KL變換。

由圖像樣值序列組成的N個隨機(jī)采樣矢量 X=[x1，x2，…，xN]T，其均值矢量與協(xié)方差矩陣可以近似表示為：

其中，協(xié)方差矩陣Cx是一個實對稱矩陣，總能找到一組（N個）正交特征矢量 ei與特征值λi(i=1，2，…，N)，由降序排列的特征值所對應(yīng)的特征矢量組成正交變換矩陣A。將隨機(jī)采樣數(shù)據(jù)X經(jīng)過變換A轉(zhuǎn)換為序列矢量Y：

式（2）稱為主元變換。從幾何觀點來看，主元變換其實質(zhì)是提取協(xié)方差矩陣的特征矢量作為主元方向，建立一個以圖像坐標(biāo)原點為原點，主元方向為坐標(biāo)軸的主軸坐標(biāo)系，將數(shù)據(jù)X進(jìn)行旋轉(zhuǎn)變換，將其主軸沿著主元方向?qū)R。

由于橢圓的長軸方向?qū)?yīng)于橢圓的主元方向，因此，對橢圓的邊緣數(shù)據(jù)經(jīng)過主元變換，可以將任意方向的橢圓轉(zhuǎn)化為標(biāo)準(zhǔn)型橢圓，有利于橢圓目標(biāo)的識別與定位。如圖1所示，其中，x-y為原圖像坐標(biāo)系，e1-e2為變換后的主軸坐標(biāo)系。

圖1 主元變換示意圖

2 基于主元變換的橢圓檢測方法

2.1 圖像預(yù)處理

眾多邊緣檢測的方法中，坎尼算子[15]具有低誤碼率、高定位精度和抑制虛假邊緣等優(yōu)點。其基本思想是：選擇高斯濾波器對圖像進(jìn)行平滑濾波，采用“非極值抑制”方法對平滑后的圖像進(jìn)行處理，通過雙閾值門限法得到所需要的單像素邊緣圖像。

為了對目標(biāo)進(jìn)行形狀分析，還需要采用輪廓跟蹤技術(shù)尋找目標(biāo)邊緣點，將目標(biāo)邊緣點連成一條連續(xù)的邊界。

2.2 橢圓識別方法

基于主元變換的橢圓識別法步驟為：

（1）計算目標(biāo)邊緣點集X的均值矢量mx與協(xié)方差矩陣Cx。

（2）對協(xié)方差矩陣Cx進(jìn)行奇異值分解，將特征值按降序排列，對應(yīng)的特征矢量ei作為變換矩陣A的行向量。

（3）按照式（2）將邊緣點集 X轉(zhuǎn)換到主軸坐標(biāo)系，生成新的邊緣點集Y。若該點集是橢圓目標(biāo)的邊緣，在理想情況下，Y應(yīng)為標(biāo)準(zhǔn)型橢圓邊緣數(shù)據(jù)：

其中，(x，y)為點集Y 中的邊緣點坐標(biāo)，參數(shù) (x0，y0，a，b)分別為橢圓中心坐標(biāo)、長半軸與短半軸，可以通過求取點集Y中水平軸與垂直軸取值范圍來獲取：

（4）由于圖像的數(shù)字化處理，橢圓邊緣點集Y并不完全滿足標(biāo)準(zhǔn)型方程，定義點集Y中數(shù)據(jù)點與標(biāo)準(zhǔn)橢圓輪廓Y′的平均最短距離作為橢圓輪廓度誤差判據(jù)：

利用式（5）計算任意點距離標(biāo)準(zhǔn)橢圓輪廓的最短距離時，需要進(jìn)行局部尋找[16]，當(dāng)邊緣點數(shù)較大時計算量較大。若將標(biāo)準(zhǔn)橢圓看作是由標(biāo)準(zhǔn)圓（中心坐標(biāo)（0，0），半徑為b）經(jīng)過中心投影得到的，將數(shù)據(jù)點集Y進(jìn)行變換：

其中：

則數(shù)據(jù)點集Z與標(biāo)準(zhǔn)圓輪廓的接近程度可以表征數(shù)據(jù)Y與標(biāo)準(zhǔn)橢圓輪廓的接近程度。計算點集Z中任意點(z1，z2)距離標(biāo)準(zhǔn)圓輪廓的最短距離，重新定義橢圓輪廓度誤差函數(shù)：

（5）設(shè)定閾值T，滿足J2＜T的點集Y（或?qū)?yīng)的 X）為橢圓目標(biāo)邊界。通常，閾值T取0.5＜T＜1。

2.3 橢圓中心定位

在現(xiàn)代工業(yè)測量領(lǐng)域，要求具有高精度亞像素級的定位精度，由式（4）得到的橢圓參數(shù)不能滿足精度要求。為了進(jìn)一步提高定位精度，采用異方差的變量含誤差模型進(jìn)行橢圓擬合。

橢圓曲線一般方程為：

令 x=(x，y)，Z(x)=[x2，xy，y2，x，y]，α=F，β=[A，B，C，D，E]，式（8）可表示為：

考慮二階近似，得到數(shù)據(jù) Z(xi)的噪聲δZi的均值與協(xié)方差矩陣為[17-18]：

從上式可知，噪聲δZi不是獨立同分布的，將噪聲數(shù)據(jù)Zi與真值數(shù)據(jù)Zio之間的馬氏距離作為價值函數(shù)：

令 ?J1/?s=0 ，s=α，β，Zi，將問題轉(zhuǎn)化為求解廣義特征向量（GSVD）問題[18]，通過迭代進(jìn)行求解。至此，橢圓的5個參數(shù)完全確定。

3 實驗

對本文提出的基于PCA變換的橢圓識別算法進(jìn)行數(shù)字仿真，并通過拍攝實際場景圖像來驗證本文算法的有效性。

3.1 橢圓識別仿真實驗

對橢圓識別算法進(jìn)行計算機(jī)仿真，如圖2所示，圖2（a）為待檢測的圖像，圖2（b）為提取的邊緣圖像，對每組邊緣數(shù)據(jù)進(jìn)行主元變換，結(jié)果如圖2（c）所示。從圖可知，主元變換將任意橢圓轉(zhuǎn)化為標(biāo)準(zhǔn)橢圓。計算各種圖形的橢圓輪廓度誤差，分別為（0.2749，0.2888，0.1929，6.9435，2.7926，2.1022），設(shè)定閾值 T=1，很容易識別出橢圓目標(biāo)。

圖2 橢圓識別仿真圖像

3.2 實際場景的橢圓識別與定位實驗

實驗中，采用尼康D100單反相機(jī)拍攝一幅航天器薄膜充氣可展開天線圖像，圖像分辨率為3008 pixel×2000 pixel，包含約140個待求目標(biāo)點，如圖3所示。由于天線表面對攝像機(jī)閃光燈光源的反射以及拍攝角度的原因，所采集的圖像中既包含大片形狀不規(guī)則的亮斑，又有極小的亮點，甚至?xí)幸恍┓菣E圓目標(biāo)存在，利用面積閾值可以很容易剔除極小亮點。而對于一些形狀不規(guī)則的非橢圓目標(biāo)，若不事先進(jìn)行橢圓識別，必然對天線面型擬合造成很大的誤差，而采用本文提出的基于PCA變換的橢圓識別算法，通過求取橢圓輪廓度誤差可以很方便剔除非橢圓目標(biāo)，如圖3所示，檢測出的非橢圓目標(biāo)已用矩形框標(biāo)注。

圖3 薄膜充氣式可展開天線試驗場

對實際拍攝的另一幅試驗場圖像進(jìn)行橢圓檢測，如圖4所示，試驗場布置了25個具有回光反射標(biāo)志的圓形標(biāo)志點，攝像機(jī)從某一站位進(jìn)行拍攝，截取部分圖像，大小為695 pixel×554 pixel，所有目標(biāo)邊緣點數(shù)在40～50個像素之間。采用本文方法與最小二乘擬合法進(jìn)行橢圓檢測，表1列出了部分橢圓目標(biāo)的橢圓輪廓度誤差以及中心坐標(biāo)（保留兩位有效數(shù)字）。所有橢圓目標(biāo)的橢圓輪廓度誤差均位于0.4 pixel以下，比較兩種方法定位中心的偏差，本次實驗中，最大偏差為0.108 pixel，偏差均值為0.056 pixel。

圖4 試驗場圖像

表1 試驗場部分橢圓中心檢測結(jié)果 pixel

4 結(jié)束語

橢圓識別與定位是計算機(jī)視覺中關(guān)鍵技術(shù)之一。將主元變換法應(yīng)用于橢圓檢測，給出一種新的橢圓輪廓度誤差評價方法。首先提取邊緣數(shù)據(jù)的主元方向，將任意橢圓轉(zhuǎn)換為標(biāo)準(zhǔn)型橢圓，利用橢圓輪廓度誤差進(jìn)行橢圓識別，并考慮數(shù)據(jù)的異方差特性，采用異方差的變量含誤差模型實現(xiàn)橢圓目標(biāo)的精確定位。實驗證明，該方法可實現(xiàn)橢圓目標(biāo)的自動識別，在噪聲方差為σ2=0.05情況下，定位精度小于0.04 pixel，在橢圓目標(biāo)識別及視覺測量領(lǐng)域具有廣泛的應(yīng)用前景。

[1]Hough P V C.Method and means for recognizing complex patterns：USA，3069654[P].1962.

[2]Xu L，Oja E，Kultaned P.A new curve detection method：Randomized Hough Transform（RHT）[J].Pattern Recognition Letter，1990，11（5）：33l-338.

[3]于海濱，劉濟(jì)林.基于中心提取的RHT在橢圓檢測中的應(yīng)用[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2007，19（9）：1107-1113.

[4]Xie Y H，Ji Q.A new efficient ellipse detection method[C]//16th International Conference on Pattern Recognition，Los Alamitos，2002：957-960.

[5]祝建中.基于中心估計的橢圓檢測[J].計算機(jī)工程與應(yīng)用，2008，44（4）：65-67.

[6]于海濱，劉敬彪，劉圓圓.基于對稱點搜索的一維RHT在橢圓檢測中的應(yīng)用[J].電子與信息學(xué)報，2009，31（8）：1830-1834.

[7]霍天歡，陳臨強(qiáng).基于一維Hough變換的橢圓檢測改進(jìn)算法[J].杭州電子科技大學(xué)學(xué)報，2011，31（2）：54-57.

[8]王長元，張景，李京京.瞳孔中心快速定位方法研究[J].計算機(jī)工程與應(yīng)用，2011，47（24）：196-198.

[9]Halí? R，F(xiàn)lusser J.Numerically stable direct least squares fitting of the ellipses[C]//Processings of the 6th International Conference in Central Europe on Computer Graphics，Visualization and Interactive Digital Media，1998：125-132.

[10]安新源，周宗潭，胡德文.橢圓擬合的非線性最小二乘方法[J].計算機(jī)工程與應(yīng)用，2009，45（18）：188-190.

[11]鄒益民，汪渤.一種基于最小二乘的不完整橢圓擬合算法[J].儀器儀表學(xué)報，2006，27（7）：808-812.

[12]張文聰，李斌，鄧宏平，等.視線跟蹤過程中變形瞳孔的定位[J].電子與信息學(xué)報，2010（2）：416-421.

[13]魏凌，曾滔，陸艷華，等.一種用于光焦度計的橢圓中心快速計算方法[J].光電工程，2012（12）：26-31.

[14]章毓晉.圖像處理[M].2版.北京：清華大學(xué)出版社，2006：265-267.

[15]Canny J.A computational approach to edge detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1986，PAMI-8（6）：679-698.

[16]黃鳳山，王春梅.光筆式視覺坐標(biāo)測量中控制點光斑圖像的識別[J].光學(xué)精密工程，2007，15（4）：587-591.

[17]Matei B，Meer P.A general method for errors-in-variables problems in computer vision[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR’00），2000，2：18-25.

[18]Matei B.Heteroscedastic Error-in-Variables models in computer vision[D].Department of Electrical and Computer Engineering，Rutgers University，2001.