基于卡爾曼預測的序列圖像橢圓檢測算法

趙江濤，張東亮，張鎖平，齊占輝

（國家海洋技術中心 天津 300112）

圖像平面上點、直線以及二次曲線的檢測是圖像處理、模式識別及機器視覺等領域的重要研究內容。圓形目標是現實生活中極為常見的目標，由于透視投影變換圓在圖像坐標系蛻變為橢圓，快速魯棒的橢圓曲線提取有重要的意義。尋找一種快速、魯棒、精確的橢圓檢測算法一直是相關領域研究熱點。目前常用的橢圓檢測算法主要有最小二乘擬合法[1]、Hough變換法[2]以及基于橢圓幾何特征的算法[3]等。最小二乘擬合方法是橢圓擬合中最為常用的方法，該方法直觀、簡單、實時性好并且可以達到較高的擬合精度，能夠應用于各種復雜的對象模型。目前大多數的橢圓檢測算法所針對的是靜態圖像，對序列圖像中動態橢圓目標的實時檢測研究較少。在筆者所研究的計算機視覺測量系統中，需要對序列圖像中的橢圓目標予以檢測及識別，通過分析各幀圖像中橢圓目標的中心位置、長短軸等參數對目標的運動參數（位置、速度、姿態）予以估計。實驗證明：本方法可以實現序列圖像中橢圓目標的快速、魯棒檢測。

1 序列圖像中橢圓檢測算法

在二維平面上，橢圓和其他二次曲線方的一般形式可以描述為：

當上式中的參數滿A2－4B<0時，該方程表示的是橢圓方程。另一種更直觀的橢圓表示方式是橢圓幾何參數法，假設橢圓的中心為（uc，vc），長軸和短軸分別為（2a 2b），橢圓長軸與坐標系橫軸的夾角為θ，可以利用式（2）～（6）將橢圓的一般式轉換成幾何參數表示形式。

隨機抽樣一致性算法[4]RANSAC（RANdom SAmple Consensus）是一種魯棒性的模型估計算法，基于RANSAC的改進的最小二乘橢圓擬合算法[5]能有效剔除錯誤樣本點的影響。對于序列圖像中的單幀圖像經邊緣檢測后，邊緣二值圖像除包含待檢測橢圓的邊緣信息之外還包含大量的偽邊緣及其他干擾信息，分別對邊緣擬合之后會得到多個橢圓目標，有必要利用先驗知識對擬合得到的橢圓進行篩選。用以下步驟對序列圖像中的橢圓目標予以檢測，算法流程如圖1所示。

1）根據上一幀圖像中卡爾曼預測的結果設置本幀圖像中橢圓待檢測區域，使用Canny算子得到待檢測區域的邊緣點集；

2）利用邊緣特征點的連通性將圖像邊緣分為不同的輪廓，選取輪廓，若輪廓點的個數大于，則使用基于RANSAC的改進最小二乘法擬合橢圓。否則，重新選取輪廓；

3）計算所擬合橢圓的橢圓率、擬合率以及面積，如果三者都滿足閾值條件，則將擬合的橢圓記為本幀圖像中的目標橢圓。否則，返回步驟2）重新選擇輪廓；

4）返回步驟1）檢測下一幀圖像中的橢圓目標。

其中，卡爾曼濾波預測的相關內容在本文第二節予以介紹。橢圓率定義為λ=b/a，b為橢圓的短半軸，a為橢圓的長半軸，橢圓率描述了橢圓接近于圓的程度。擬合率定義為p=m/n，其中n為擬合橢圓所用輪廓邊界的總點數，m為該邊界上的點到擬合橢圓距離小于設定閾值的點集，擬合率描述了擬合橢圓所用輪廓與所得到橢圓之間的擬合程度。橢圓面積S=πab。可以根據先驗知識及前期實驗設定待檢測橢圓的面積、橢圓率以及擬合率的閾值范圍。

圖1 橢圓檢測流程Fig.1 Flow of ellipse detection

2 卡爾曼濾波預測橢圓搜索區域

對整幅圖像進行橢圓檢測需要較多的時間，如果能夠對下一幀圖像中橢圓的位置有預先粗略的估計，將橢圓的待檢測區域限定在一個較小的范圍內，可以減少算法所需要的存儲空間和運行時間。另外，在全局范圍內搜索橢圓目標使得算法的抗干擾能力也不理想。利用卡爾曼濾波器的預測功能來預測下一幀圖像中待檢測橢圓目標中心的位置，并設置下一幀圖像中橢圓目標的大致搜索范圍。通過這種方法大大減小了算法的運算量，保證了系統的實時性及魯棒性。

2.1 卡爾曼預測器

卡爾曼預測器[6]實質上是一種遞歸預測算法，根據誤差無偏最小方差原則預測目標下一時刻的運動狀態。卡爾曼濾波可以劃分為兩個過程：時間更新和測量更新。時間更新方程用于向前預測下一時刻狀態X （k）-及計算預測協方差P（k）-。測量更新方程用于估計當前時刻狀態的最優值X（k），計算卡爾曼增益Kg（k）并更新最優值的協方差P（k）。在卡爾曼濾波器初始化后，通過圖2中卡爾曼濾波的5個基本方程就可以保證算法自回歸的運行下去。在利用卡爾曼濾波的預測功能時系統所輸入的是k-1時刻系統狀態的測量值Z（k-1），輸出的是k時刻系統的預測值X（k）-。在沒有控制輸入的情況下Kalman濾波的遞歸運算過程如圖2所示。

圖2 卡爾曼濾波預測流程Fig.2 Flow of Kalman filter prediction

2.2 橢圓檢測區域預測算法實現

考慮運動速度、加速度對橢圓中心位置預測的影響，使用三階向量卡爾曼預測器對下一幀圖像中的橢圓中心位置進行預測。為保證算法的實時性，設計了兩個卡爾曼預測器分別跟蹤橢圓中心在圖像坐標系橫軸和縱軸方向，將一個二維預測降為兩個一維預測[7]，提高了算法的運行速率。假設目標物體運動的軌跡投影在一定時間間隔T內的加速度是常量，則：

上式中，yk-1、vk-1、ak-1分別表示 t=k-1時刻橢圓中心在圖像坐標系縱軸方向上的位置、速度及加速度，T為兩幀圖像間的時間間隔。用示t=k時刻單個預測器的狀態向量，則橢圓中心運動狀態的系統方程可以寫為：

系統量測方程為

上式中，C=[1 0 0]為量測矩陣，Z（k）為 t=k時刻所測量得到的橢圓中心在圖像坐標系中縱軸方向的坐標，V（k）為測量噪聲，其協方差矩陣為R。將基于卡爾曼濾波的橢圓中心位置預測算法描述為：

1）初始化卡爾曼濾波器，設置卡爾曼預測器的噪聲方差Q和R，并給定狀態初始值X（0）和對應協方差矩陣初始值 P（0）；

2）由時間更新方程并根據k-1時刻的最優估計值X（k-1）預測k時刻系統狀態X（k）-，同時更新k時刻狀態預測值的協方差 P（k）-，并將預測值 X（k）-作為系統的輸出；

3）根據測量更新方程可以計算得到k時刻的卡爾曼增益Kg（k），輸入k時刻的狀態測量值Z（k）并結合k時刻狀態預測值X（k）-可以得到 k時刻的最優估計值X（k）。計算k時刻最優估計值的協方差P（k），并返回步驟2）使算法自回歸的運行下去。

假設由第k-1幀圖像預測的第k幀圖像中橢圓的中心坐標為（uc，vc），在 k-1幀計算的橢圓的長軸為 r，則將第 k幀圖像中橢圓的待檢測區域設置為以（uc，vc）為中心，以2（r-Tr）為邊長的矩形區域[8]。圖3中實線框為由卡爾曼濾波預測的下一幀圖像中橢圓的待檢測區域。其中，閾值可以根據目標橢圓運動情況進行調整，對于運動變化較快的目標可以適當增大，此時橢圓檢測范圍增大Tr，穩定性提高。由卡爾曼濾波的性質可知，濾波器初始化后的前幾次預測并不可靠，此時應適當增大Tr保證算法的穩定性，經過若干幀跟蹤之后，以較小的Tr即可保證待檢測橢圓位于預測的檢測區域內。

圖3 卡爾曼預測橢圓區域Fig.3 Ellipse location prediction with kalman predictor

3 實驗與分析

3.1 仿真實驗

利用MATLAB生成含有噪聲的標準橢圓邊界點并添加部分錯誤點，分別利用最小二乘法和改進的方法擬合橢圓，兩者檢測結果如圖4所示。由圖可以看出由于樣本點中含有一定比例的不屬于待擬合橢圓邊界的點集，最小二乘法所擬合橢圓并不準確，而基于RANSAC方法能排除這些錯誤點的干擾，準確的擬合出目標橢圓。

3.2 實際圖像檢測結果

圖4 橢圓擬合結果Fig.4 Result of ellipse fitting

在序列圖像動態橢圓目標檢測實驗中，對自由下落并反彈的球體的投影圖像進行橢圓檢測。所錄制視頻圖像分辨率為320*240，幀頻為20 frame/s，并設置待檢測區域閾值Tr=30。圖5為從該段序列圖像中所截取的幾幀圖像，圖像中的方形區域為通過卡爾曼濾波器所預測的橢圓待檢測區域。各幀圖像中所預測的方形區域邊長最大不超過50像素，待檢測區域的面積僅僅是全局圖像面積的1/30，大大減小了下一幀圖像中橢圓的搜索區域。在不同的實驗狀況下，可以根據目標運動的劇烈情況設置不同的Tr來保證橢圓目標位于待檢測區域內。圖5中的橢圓為按本文方法所擬合的橢圓曲線與原二值邊緣圖像疊加的結果。

圖6為橫向和縱向的卡爾曼預測結果及誤差，從圖6（a）和圖6（c）可以看出經過幾次迭代之后，卡爾曼濾波器在兩個方向上都可以準確預測出下一幀圖像中橢圓中心的實際位置。圖6（b）和圖6（d）也表明濾波器可以較為準確的預測出下一幀圖像中橢圓目標的中心位置，最大預測誤差在20個像素之內。通過卡爾曼濾波預測可以較為準確的預測下一幀圖像中橢圓目標的待檢測區域。

4 結 論

為實現對序列圖像中的動態橢圓實時檢測，結合RANSAC算法和最小二乘法設計了魯棒性的橢圓檢測流程，能有效剔除橢圓擬合過程中干擾邊緣和噪聲點的影響。序列圖像中橢圓目標的檢測對系統的運算速度要求較高，采用卡爾曼濾波預測能夠充分的利用歷史信息，縮小下一幀圖像中對待檢測橢圓目標的搜索區域，提高了系統的運算速度和穩定性。此外，當在某一幀圖像中未能檢測出橢圓目標時可以根據預測結果繼續對下一幀圖像中的橢圓進行檢測，提高了系統的可靠性。目前已成功將該算法應用于所開發的水下目標運動參數視覺測量系統中，取得了令人滿意的效果。

[1]鄒益民，汪渤.一種基于最小二乘的不完整橢圓擬合算法[J].儀器儀表學報，2006，27（7）:809-810.ZOU Yi-min，WAN Bo.Fragmental ellipse fitting based on least square algorithm[J].Chinese Journal of Scientific Instrument，2006，27（7）:809-810.

[2]袁立，葉露，賈建祿.基于Hough變換的橢圓檢測算法[J].中國光學與應用光學，2010，3（4）:380-382.YUAN Li，YE Lu，JIA Jian-lu.Ellipse detection algorithm based on hough transform[J].Chinese Journal of Optics and Applied Optics，2010，3（4）:380-382.

[3]于海濱，劉濟林.基于中心提取的RHT在橢圓檢測中的應用[J].計算機輔助設計與圖形學學報，2007，19（9）:1108-1112.YU Hai-bin，LIU Ji-lin.Ellipse detection by the RHT based on center extraction[J].Hournal of Computer-Aided Desigh&Computer Graphics，2007，19（9）:1108-1112.

[4]Fischler M A，Bolles R C.Random sample consensus:a paradigm for model fitting with applications to image analysis and automated cartography[J].Graphics and Image Processing，1981，24（6）:381-383.

[5]閆蓓，王斌，李媛.基于最小二乘法的橢圓擬合改進算法[J].北京航空航天大學學報，2008，34（3）:295-298.YAN Pei，WANG Bin，LI Yuan.Optimal ellipse fitting method based on least-square principle[J].Journal of Beijing University of Aeronautics and Astronautics，2008，34 （3）:295-298.

[6]郝利云，吳玲達.基于卡爾曼預測器的數據預取方法[J].計算機仿真，2012，29（10）:10-12.HAO Li-yun，WU Ling-da.Kalman predictor based data perfecting method[J].Computer Simulation，2012，29（10）:10-12.

[7] 姚紅閣，耿軍雪. 基于卡爾曼預測的視頻目標實時跟蹤[J].西安工業大學學報，2007，27（2）:174.YAO Hong-ge，GENG Jun-xue. A real-time tracking for videotarget based on kalman prediction[J]. Journal of Xi’an TechnoloficalUniversity，2007，27（2）:174.

[8] 王忠立，高文. 基于最小二乘預測的動態快速橢圓檢測[J].信息與控制，2003，32（7）:732.WANG Zhong-li，GAO Wen. Dynamic fast ellipse detectionbased on location prediction with least square[J]. Informationand Control，2003，32（7）:732.