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

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

0 引言

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

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

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

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

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

1 最小外接矩形模型

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

　　1.1 獲取目標的邊界

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

　　1.2 計算邊界的中心

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

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

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

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

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

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

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

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

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

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

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

　　經(jīng)過最上面的點的直線方程可以表示為：

　?。▂-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 計算直線交點，所得的矩形框即為最佳外接矩形

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

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

　　1.7 最小外接橢圓

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

　　則矩形的內(nèi)切橢圓即可通過參數(shù)方程表示為：

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

2 實驗結(jié)果及分析

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

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

　　從圖2中可以看出，（d）圖中只有很少的點在橢圓外部，而橢圓內(nèi)部的背景成分相比圖（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。

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

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

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

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

3 結(jié)論

　　本文提出了一種基于最小外包矩形的快速橢圓擬合方法，該方法可以用于視頻跟蹤中運動目標的擬合。本算法利用最小二乘法求取運動目標的長、短軸及傾斜方向，并求取目標的最小外包矩形，截取矩形的內(nèi)切橢圓即為目標的擬合橢圓。這種橢圓表示方法應用簡單，不需要迭代，橢圓面積接近運動目標的實際面積，減少了擬合框中背景像素點的比例，能夠避免多個運動目標在距離較近時發(fā)生的重疊問題?；谧钚⊥獍匦蔚目焖贆E圓擬合方法能夠快速擬合存在于二維圖像里的運動目標，在以后的研究中，還可以探索在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.