摘  要： 提出一種基于最小外包矩形的快速橢圓擬合方法，該方法利用最小二乘法獲得目標的最小外包矩形框，再求取外包矩形框的內切橢圓，該橢圓能有效反映目標的大部分運動信息。本文對該方法進行了目標擬合的有效性和實效性實驗分析。分析表明，本算法得到的擬合橢圓內背景像素比例（Background Pixel Raito，BPR）相比于傳統的矩形框和經典的Khachiyan橢圓擬合方法有了顯著的下降，且擬合方法無需迭代運算，擬合速度僅次于傳統的矩形框，比經典的Khachiyan橢圓擬合方法快3倍。本算法對于實時目標跟蹤應用具有很好的應用價值。

　　關鍵詞： 目標跟蹤；橢圓擬合；最小二乘法；Khachiyan算法；矩形擬合框

0 引言

　　幾何形狀是一種常見的目標表示方法，如橢圓、矩形等[1-2]。在跟蹤過程中，擬合的幾何框面積越接近真實的運動目標，就越能真實地反應運動目標的各項參數。因此，目標的擬合率是目標檢測與跟蹤的一個重要指標[3]。特別是在多目標跟蹤應用中，若運動目標的擬合幾何框偏大，可能會導致兩個運動目標的擬合框有一定程度的重合，兩個擬合框之間相互影響，造成獲取的目標特征不夠準確。反之，若擬合幾何框偏小，計算出的目標特征不夠完整，也會影響跟蹤效果[4]。

　　在目前的視頻跟蹤算法及應用中，矩形框是一種使用最多的目標表示方法，該方法利用目標四個方向最遠邊界點得到的矩形框來表示跟蹤目標。這種矩形框雖然能夠包含所有的目標信息點，但是往往包含較多的背景信息，因此可能造成遮擋、多目標重疊等問題[5]。針對此問題，國內外一些學者開始關注其他幾何形狀目標表示方法。其中，用最小面積的閉包橢圓來表示運動目標的方法受到了最多關注[6]。其原因是橢圓在很多目標表示方面（如人體、小汽車等）有著形狀上的優勢，不僅可以用更少的面積表示目標，而且橢圓的方向角度變化還能反映目標的一些行為動作[7]。

　　最小體積的閉合橢球模型（Minimum Volume Enclosing Ellipsoids，MVEE）是求解散點的最小閉包球的一種經典模型，許多學者提出了相關的求解方法，如Khachiyan算法[8]、KY算法[9]，Todd M.J.等人提出了相關的改進方法[10]，用于降低算法的復雜度和迭代次數。

　　Chaudhuri.D提出了一種閉合區域的最小邊界框擬合方法，實現了對閉合區域的目標擬合最小的邊界矩形框[11]。通過這種方法擬合出的矩形框可認為是目標的最小邊界矩形框，不管從實際圖像還是仿真圖像的處理結果來看，該方法既精準又高效。

　　基于以上分析，本文根據最小二乘法求得目標的最佳外接矩形框，提出了一種基于外接矩形的橢圓擬合方法，該方法針對連續的前景目標擬合不需要迭代，速度快，效率高，擬合的橢圓面積與目標本身的面積接近，且橢圓中背景像素也相對較少。因此，該方法可以很好地近似表達視頻中的運動目標，并解決多目標的重合問題，對噪聲點有較好的魯棒性。

1 最小外接矩形模型

　　最小外接矩形不同于常見的垂直矩形擬合框，最小外接矩形擬合過程如圖1所示。具體步驟是：提取目標邊界，計算目標中心，計算長短軸，尋找四個方向的最遠邊界點，計算出經過最遠點的矩形框。

　　1.1 獲取目標的邊界

　　Sobel邊緣檢測器是一種常見的邊緣提取工具，Sobel邊緣檢測器是利用特定的數字掩模圖像進行濾波運算，Sobel邊緣檢測具有提取速度快的特點，本文利用Sobel算子提取目標的邊界信息。

　　1.2 計算邊界的中心

　　對于二維圖像A，提取目標邊界（xi，yi）（i=1，2…n）的中心坐標，通過以下公式計算得到：

　　1.3 利用最小二乘法計算長短軸

　　根據1.1，設經過目標中心的直線的傾斜角度為，則該直線的方程為：

　　目標邊界點（xi，yi）（i=1，2…n）到該直線的距離為：

　　所有邊界點到直線的距離平方和為：

　　為了計算傾斜角度，令距離平方和P最小情況下的即為所求，此時對方程（4）求偏導數，當時可以取得最優解，有：

　　先計算出最優解下的直線傾斜角度，將代入式（2），所得的直線就是經過目標A中心的最佳擬合直線，且代表目標A的長軸傾斜方向，而目標的短軸，則是經過目標A的中心且垂直于長軸的直線。

　　1.4 分別找出上下左右四個方向距離長、短軸的最遠點

　　由式（3）、（5），令函數f（x，y）=0，將目標A的邊界點（xi，yi）（i=1，2…n）分別代入到長軸、短軸直線方程，有：

　　當f（a，b）>0時，該點位于長軸的上方；當f（a，b）<0時，該點位于長軸的下方；當f（a，b）=0時，該點剛好經過長軸直線。通過比較f（a，b）的值，可以區分開長短軸上面、下面的邊界點，并找出f（a，b）的最大值和最小值，對應的點分別是pt（x1，y1），pb（x2，y2），pl（x3，y3），   pr（x4，y4）。

　　1.5 計算經過最遠點且平行于矩陣軸線的直線方程

　　經過最上面的點的直線方程可以表示為：

　　（y-y1）-tan（x-x1）=0（6）

　　此直線即為目標的上邊界外接矩形框直線，同理可以計算另外三條邊的外界矩形框直線方程：

　　（y-y2）-tan（x-x2）=0（7）

　?。▂-y3）+cot（x-x3）=0（8）

　?。▂-y4）+cot（x-x4）=0（9）

　　1.6 計算直線交點，所得的矩形框即為最佳外接矩形

　　通過聯立兩條直線的方程，可以求出外接矩形框的頂點，聯立式（6）、（8），可以求得矩形的左上交點坐標：

　　連接外接矩形四個頂點，即可得到目標的最佳外接矩形。

　　1.7 最小外接橢圓

　　求取最佳外接矩形時，可以求取目標的外接矩形的最大內切橢圓，該橢圓圓心即為外接矩形中心，長軸剛好等于外接矩形的長，短軸則等于外接矩形的寬，引入坐標旋轉公式：

　　則矩形的內切橢圓即可通過參數方程表示為：

　　其中，a為橢圓的長軸，b為橢圓的短軸，為橢圓長軸的傾斜角度。

2 實驗結果及分析

　　本實驗運行平臺：Intel酷睿（i5 3470）四核處理器、8 GB內存的個人PC，計算仿真環境是MATLAB 2011a。在實驗中，通過模擬多目標及實際視頻序列兩種輸入分別比較了傳統的矩形擬合框、質心法、VMEE模型中的Khachiyan算法與本文算法的擬合結果，選取橢圓大小及背景像素比例作為參考指標，分別計算了四種方法的執行效率。

　　圖2（a）是一幅模擬二值圖像，圖像中包含了部分常見的幾何形狀，分別統計各個目標的像素個數，并計算擬合時間以及背景像素比例。

　　從圖2中可以看出，（d）圖中只有很少的點在橢圓外部，而橢圓內部的背景成分相比圖（b）減少了很多。以目標3為例，通過計算可知，目標3的實際面積為  7 323個像素點，圖2（b）中目標3橢圓的面積為9 583個像素點，背景像素的比例為0.26，擬合時間為2.25 s；圖2（c）中橢圓的面積為10 261，背景的比例為0.32，擬合時間為0.33 s，圖2（d）中橢圓面積為8 913，背景比例則降為0.19，擬合時間為0.07 s。

　　對視頻序列進行目標擬合時，首先采用高斯混合模型對監控視頻做前景檢測，檢測出運動目標后，對運動目標的擬合方法進行了對比分析：（1）傳統矩形框擬合方法；（2）Khachiyan目標擬合方法；（3）基于質心的快速橢圓擬合方法；（4）本文算法。如圖3所示。

　　圖3是選取停車場監控畫面的某一幀，對已經檢測出的運動目標運用以上算法分別進行擬合運算。畫面運動目標有兩個，由于兩個運動目標的距離較近，圖3（a）中的矩形框幾乎要重疊，且包含了大量的背景像素；圖3（b）中的兩個橢圓已經相交，多個運動目標的擬合框若相互交疊，在跟蹤過程中，兩個框內的特征會相互影響，導致跟蹤時不能很好地區分當前像素屬于哪一個目標；而圖3（c）橢圓主軸方向與目標主軸方向不一致，而且兩個擬合橢圓也已經相切，并沒有有效地把兩個目標區分開來；圖3（d）中，目標信息全部包含在橢圓之內，而且擬合橢圓相互獨立，能夠更有效地還原真實目標運動情況。

　　表1給出了圖3中運動目標的面積、各個擬合框的面積、運算時間以及本文算法中橢圓內特征點的比例。由于運動目標是不規則的，因此把運動目標的像素點數作為它的面積。其中，s0為運動目標的面積；s為擬合框的面積；r為框內運動目標點的個數占總像素數的比例；t為程序運行時間。

　　從表1中可以看出，在停車場的監控畫面中，無論從面積還是時間的角度考慮，傳統矩形擬合方法都要優于Khachiyan算法，但是，這兩種擬合框的面積也都遠大于運動目標的面積。質心法雖然能獲得最小的擬合橢圓，但是，其擬合率較低，損失了一部分重要信息。因此，本文提出的跟蹤目標表示法在擬合框面積、運行時間以及框內目標點的比例三方面做到了較好的折中，擬合時間僅次于傳統矩形擬合框，橢圓傾斜方向與目標方向一致，該方法還能解決多個運動目標因距離太近造成邊界框交疊的問題。

3 結論

　　本文提出了一種基于最小外包矩形的快速橢圓擬合方法，該方法可以用于視頻跟蹤中運動目標的擬合。本算法利用最小二乘法求取運動目標的長、短軸及傾斜方向，并求取目標的最小外包矩形，截取矩形的內切橢圓即為目標的擬合橢圓。這種橢圓表示方法應用簡單，不需要迭代，橢圓面積接近運動目標的實際面積，減少了擬合框中背景像素點的比例，能夠避免多個運動目標在距離較近時發生的重疊問題。基于最小外包矩形的快速橢圓擬合方法能夠快速擬合存在于二維圖像里的運動目標，在以后的研究中，還可以探索在3D空間的目標擬合，以及存在于3D空間的散點集的擬合橢球模型。三維空間的目標擬合在三維重建領域具有十分積極的研究意義。

　　參考文獻

　　[1] FIEGUTH P， TERZOPOULOS D. Color-based tracking of heads and other mobile objects at video frame rates[C]. In  IEEE Conference on Computer Vision and Pattern Recognition （CVPR）， 1997：21-27.

　　[2] COMANICIU D， RAMESH V， MEER P. Kernel-based object tracking[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25（4）：564-575.

　　[3] YILMAZ A， JAVED O， SHAH M. Object tracking： a survey[J]. ACM Computing Surveys， 2006，38（4）：13-18.

　　[4] GLINEUR F. Pattern separation via ellipsoids and conic programming[M]. Belgium： Msthesis， Faculte Polythechnique de Mons， 1998.

　　[5] OLIVIER BARNICH， MARC VAN DROOGENBROECK. ViBe： a universal background substraction algorithm for video sequences[C]， IEEE Transaction on Image Processing， 2011：1709-1724.

　　[6] ZIVKOVIC Z， KROSE B. An EM-like algorithm for color-histogram-based object tracking[C]. IEEE Conference on Computer Vision and Pattern Recognition， 2004：798-803.

　　[7] JEPSON A， FLEET D，  ELMARAGHI T. Robust online appearance models for visual tracking[C]. IEEE Transaction on Pattern Analysis and Machine Intelligence， 2003， 25（10）： 1296-1311.

　　[8] KHACHIYAN L G. Rounding of polytopes in the real number model of computation[C]， Mathematics of Operations Research， 1996：307-320，

　　[9] KUMAR P， YILDIRIM， E A. Minimum volume enclosing ellipsoids and core sets[J]. Optimization Theory and Application， 2005，126（1）：1-21.

　　[10] TODD M J， YILDIRIM E A. On Khachiyan′s algorithm for the computation of minimum volume enclosing ellipsoids[J]. Discrete Application， 2007，155（13）：1731-1744.

　　[11] CHAUDHURI， D， SAMAL， A. A simple method for fitting of bounding rectangle to closed regions[C]. Pattern Recognit， 2007：1981-1989.