韓建棟，溫 靜

HAN Jiandong,WEN Jing

山西大學 計算機與信息技術學院，計算智能與中文信息處理教育部重點實驗室，太原 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

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

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

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

1 主元變換及其特點

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

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

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

式（2）稱為主元變換。從幾何觀點來看，主元變換其實質是提取協方差矩陣的特征矢量作為主元方向，建立一個以圖像坐標原點為原點，主元方向為坐標軸的主軸坐標系，將數據X進行旋轉變換，將其主軸沿著主元方向對齊。

由于橢圓的長軸方向對應于橢圓的主元方向，因此，對橢圓的邊緣數據經過主元變換，可以將任意方向的橢圓轉化為標準型橢圓，有利于橢圓目標的識別與定位。如圖1所示，其中，x-y為原圖像坐標系，e1-e2為變換后的主軸坐標系。

圖1 主元變換示意圖

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

2.1 圖像預處理

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

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

2.2 橢圓識別方法

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

（1）計算目標邊緣點集X的均值矢量mx與協方差矩陣Cx。

（2）對協方差矩陣Cx進行奇異值分解，將特征值按降序排列，對應的特征矢量ei作為變換矩陣A的行向量。

（3）按照式（2）將邊緣點集 X轉換到主軸坐標系，生成新的邊緣點集Y。若該點集是橢圓目標的邊緣，在理想情況下，Y應為標準型橢圓邊緣數據：

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

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

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

其中：

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

（5）設定閾值T，滿足J2＜T的點集Y（或對應的 X）為橢圓目標邊界。通常，閾值T取0.5＜T＜1。

2.3 橢圓中心定位

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

橢圓曲線一般方程為：

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

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

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

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

3 實驗

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

3.1 橢圓識別仿真實驗

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

圖2 橢圓識別仿真圖像

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

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

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

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

圖4 試驗場圖像

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

4 結束語

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

[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]于海濱，劉濟林.基于中心提取的RHT在橢圓檢測中的應用[J].計算機輔助設計與圖形學學報，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].計算機工程與應用，2008，44（4）：65-67.

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

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

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

[9]Halí? R，Flusser 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].計算機工程與應用，2009，45（18）：188-190.

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

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

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

[14]章毓晉.圖像處理[M].2版.北京：清華大學出版社，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]黃鳳山，王春梅.光筆式視覺坐標測量中控制點光斑圖像的識別[J].光學精密工程，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.