1、運動場景中目的檢測與跟蹤技術研討 劉振華2006年11月 相對于靜止場景，所謂運動場景中的目的檢測與跟蹤，是指在目的運動的同時，攝像機也由于運載平臺的姿態或位置改動而發生運動，構成目的與背景共同變化下的目的檢測與跟蹤。 運動場景中目的檢測與跟蹤技術的目的在于準確地探測目的、合理地提取目的特征、準確地跟蹤目的，同時要思索算法的實時可操作性。 由于該技術在軍事、交通、工業以及生物醫學等領域具有廣泛的運用前景，從而激發了國內外寬廣科研任務者的濃重興趣，成為計算機視覺領域的一個熱點。 研討現狀 Collins, Lipton, Kanade, Fujiyoshi, Duggins, Tsin, Tol

2、liver, Enomoto, Hasegawa, “A System for Video Surveillance and Monitoring: VSAM Final Report Technical report CMU-RI-TR-00-12, Robotics Institute, Carnegie Mellon University, May, 2000.1997年，美國國防高級研討工程署設立了以卡內基梅隆大學牽頭，麻省理工學院等高校參與的視覺監控艱苦工程VSAM，主要研討用于戰場及普通民用場景監控的自動視頻了解技術美國康奈爾大學計算機系設計了一套航拍視頻檢測與繼續跟蹤系統，該系統

3、可以對多運動目的實現長時間的準確跟蹤，即使發生短時間內目的被遮擋或目的時靜時動的情況 2005年，美國中央佛羅里達大學計算機視覺實驗室開發出了基于MATLAB的COCOA系統，用于無人機低空航拍視頻圖像的目的檢測與跟蹤處置Bell W, Felzenszwalb P, Huttenlocher D, “Detection and Long Term Tracking of Moving Object in Aerial Video /vision/wbell/identtracker, 1999.03.26. Saad Ali, Mubarak Shah, “COC

4、OA - Tracking in Aerial Imagery SPIE Airborne Intelligence, Surveillance, Reconnaissance (ISR) Systems and Applications, Orlando, 2006, COCOA Homepage Ismail Haritaoglu, David Harwood, Larry S. Davis, “Active Outdoor Surveillance ICIAP 1999: 1096-1099Computer Vision Lab, Maryland University I. Cohen

5、, G. Medioni, “Detecting and Tracking Moving Objects in Video from and Airborne Observer Proc. IEEE Image Understanding Workshop, pp. 217-222, 1998 University of Southern California Institute for Robotics and Intelligent SystemsRonald Jones, David M. Booth, Nicholas J. Redding, “Video Moving Target

6、Indication in the Analysts Detection Support System May, 2006 Defense Science and Technology Organization, AustraliaKhaled Kaniche, Benjamin Champion, Claude Pgard, Pascal Vasseur “A Vision Algorithm for Dynamic Detection of Moving Vehicles with a UAV IEEE International Conference on Robotics and Au

7、tomation 2005 (ICRA05), April 2005, Barcelone University of Picardie Amiens FranceHaritaoglu I, Harwood D, Davis L, “W4: Real-time Surveillance of People and Their Activities IEEE Trans Pattern Analysis and Machine Intelligence, 2000, 22(8):809-830 IBM and Computer Vision Lab, Maryland University 研討

8、現狀 VSAM VSAM系統是在1997年至1999年間，美國國防高級研討方案局資助卡內基梅隆大學和薩爾諾夫戴維研討中心等著名大學和公司協作結合研制的視頻監視與監控系統。目的是開發自動視頻了解技術，并用于實現未來戰爭、人力費用昂貴、非常危險或者人力無法實現等場所的監控。該系統交融了數字攝像機、音頻采集頭、紅外和微波報警探測器、溫度探測器等多種類型的傳感器，可以對監控地域進展全方位的晝夜監控。運用了地理信息和三維建模技術，提供可視化圖形操作界面，當視頻分析處置器報告了運動對象、對象類別及位置之后，操作員不僅可以在地理信息界面上進展虛擬對象標志，而且還能在輔助窗口察看對象的真實活動情況。在機載航空

9、攝像機方面，不需求經常性的人工支配，就能自動對準地面監視目的，實現對重要目的的長時間監視。VSAM運用架設在高處多方位旋轉云臺上的單個攝像機，可以全方位地實施視頻監控。系統首先有規律地初始化一系列背景圖像，然后利用基于特征區域的方法將實踐攝錄的視頻圖與相應的背景圖作匹配，再利用背景減除法檢測運動目的。 VSAM由于傳統的卡爾曼濾波方法只能處置單峰問題，該系統對傳統的卡爾曼濾波思想進展了擴展，并運用了帶目的模板更新的相關匹配算法實現了多目的的跟蹤。 VSAM針對機載航空攝像機所拍攝的視頻圖像，薩爾諾夫戴維研討中心研發了檢測和跟蹤獨立地面車輛目的的視頻圖像了解技術。該技術的關鍵在于對航空攝像機的自

10、運動補償，對經過補償的圖像，利用三幀差減的方法檢測目的。 美國康奈爾大學計算機系設計的航拍視頻圖像目的檢測與繼續跟蹤系統的特征在于，可以對多運動目的實現較長時間的準確跟蹤，即使在短時間內目的被遮擋或移出視場以及目的時靜時動。該系統在運動背景估計與補償中所涉及的主要技術是基于Kanade-Lucas-Tomasi算法的特征點跟蹤和基于M估計的魯棒性仿射參數估計。然后利用三幀差減的方法檢測目的運動，利用形狀學操作分割圖像并定位運動目的。對多目的進展標志之后，利用Hausdorff間隔匹配和模板更新的方法對目的進展長時間的跟蹤。4576102123152159253298COCOACOCOA系統是一

11、種無人機航拍圖像目的跟蹤系統。該系統針對一段視頻圖像序列，經過三大技術環節，即背景運動補償、運動檢測與目的跟蹤，來完成對目的的檢測與跟蹤。該系統基于MATLAB平臺，可以適用于不同的光傳感器可見光或紅外，最小的可跟蹤目的約為100象素大小。該系統對機載光電傳感器或紅外傳感器所攝視頻圖像進展魯棒性背景運動補償，并可生成全景圖，利于更高層次的運用。對圖像中多種運動目的如汽車、坦克、摩托車等進展可靠性檢測并進展耐久地跟蹤。COCOA在背景運動補償方面，利用Harris角點檢測算法分別提取相鄰兩幀圖像的特征點，對每一特征點先進展簡單的粗匹配，而后利用RANSAC魯棒估計算法完成特征點的挑選，經過挑選后

12、的特征點的運動矢量集合來估計全局運動矢量。在運動檢測方面，經過累積幀差法對汽車、卡車、坦克、摩托車等獨立運動進展檢測，再利用數字圖像形狀學操作去除噪聲、捕捉大致的目的區域，再利用幾何活動輪廓的程度集方法提取目的輪廓，最后利用基于核函數的方法如Mean Shift方法與模板更新實現目的跟蹤。COCOA背景運動補償基于特征 + 基于灰度梯度運動檢測累積幀差法 + 形狀學操作目的跟蹤Level Set方法 + Mean Shift方法視頻序列COCOA系統的根本技術環節 歸納起來，運動場景中目的檢測與跟蹤技術主要包括以下三個關鍵技術： 背景補償與圖像預處置：消除背景運動、隨機噪聲對目的檢測與跟蹤的影

13、響。 圖像分割與目的檢測：利用圖像分割技術從圖像中檢測出能夠的運動目的。 特征提取和目的跟蹤：對檢測出的目的提取可識別的特征，根據這些特征在后續的視頻圖像序列中對目的進展跟蹤。針對視頻圖像目的檢測與跟蹤技術，根據三維場景中目的間隔成像傳感器的探測間隔，可劃分為三種情況：微弱點狀目的的檢測，即當目的間隔成像傳感器很遠時，目的在圖像平面上只占幾個像素，呈現為微弱點狀目的，信噪比較低；擴展目的的檢測，即當目的間隔成像傳感器較近時，目的在圖像平面上表現為擴展目的，普通其為在視場中覆蓋100100像素以上，占視場比例較大的大型目的；介于上述兩種情況之間，此時目的在圖像平面上普通不超越100100個像素，

14、具有一定的可視對比度。這三種情況下的目的檢測與跟蹤各有其特點，處置方法差別很大。本文的研討任務屬于第三種情況，它是運用最廣泛的一種情況，對于它的研討具有重要的意義。背景運動補償技術 在視頻運動目的檢測過程中，由于攝像機的運動，導致圖像序列中運動目的和背景的相應運動。當目的與背景一同變化時，將使得目的檢測變得復雜起來。為了從動態場景中檢測出運動目的，通常需求對背景運動進展補償。背景運動補償技術的中心問題是背景運動矢量的估計。傳統的運動估計采用平動來建模運動場效果差 目前，常采器具有豐富描畫參數的仿射變換和透射變換來建模運動場 背景運動補償技術仿射模型攝像機的參數模型 基于平行投影的六參數仿射模型

15、 利用當前幀和前一幀的圖像對參數進展估計，就可以得到圖像的運動參數。 背景運動補償技術運動矢量估計運動矢量估計技術的研討總是圍繞著計算復雜度和檢測精度這對矛盾進展的。目前，運動矢量估計的算法主要包括灰度投影法、光流場法、圖像塊匹配法、特征匹配法和相位法等。傳統的灰度投影法雖然該方法實現簡單，但只能處理平移運動的問題，雖然后來有學者進展了改良，但也只能處理很有限的旋轉運動的問題。光流場法的計算精度很高，但涉及到變分運算，計算較復雜，而且對噪聲極為敏感。基于傅氏變換的方法雖然計算精度也很高，但采用了傅氏變換、相關運算或者極坐標變換，計算復雜度同樣很高。目前較為常用的方法是圖像塊匹配法和特征匹配法。

16、針對所研討的對象，本文采用基于特征點匹配的運動估計算法。特征點匹配的關鍵在于特征點的選擇和匹配戰略的選擇。背景運動補償技術特征點的選擇 圖像中的特征點也稱為角點沒有明確的數學定義，但人們普遍以為特征點是二維圖像亮度變化猛烈的點或圖像邊緣曲線的曲率極大值的點，這些點表達了圖像圖形的重要特征。相比于塊匹配法，利用這些特征點來估計運動矢量可以有效地減少數據量，提高計算的速度，且有利于圖像的可靠匹配。 有關于角點檢測的研討開場于二十世紀七十年代，到目前為止，學者們曾經提出了很多的算法，比較經典的算法有：Moravec算法、Harris算法、MIC 算法、SUSAN算法等。理想的角點、邊緣和平坦地域例如

17、：背景運動補償技術特征點的選擇Moravec算法 Moravec于1977年提出了利用灰度方差提取點特征的算子。該算法的思想非常簡單，后來的很多算法都是基于該算子改良的。Moravec角點檢測算法的詳細步驟是：計算每個像素的興趣值(interest value), 即以該像素為中心, 取一個nn的窗口, 計算0度, 45度, 90度, 度四個方向的灰度差平方和, 取其中的最小值為該像素的興趣值。根據實踐圖像設定一個閾值, 遍歷整個圖像，以興趣值大于該閾值的點為候選點。閾值得選擇應以候選點中包括需求的特征點，而又不含過多的非特征點。再選一個一定大小的窗口, 以該窗口遍歷灰度圖像, 在此過程中取窗

18、口中興趣值最大的候選點為特征點。 綜上所述，Moravec算子是在四個主要方向上，選擇具有極大極小灰度方差的點作為特征點。 H. P. Moravec, “Towards Automatic Visual Obstacle Avoidance Proc. 5th International Joint Conference on Artificial Intelligence, pp. 584, 1977背景運動補償技術特征點的選擇Moravec算法以3x3窗口計算右上角的灰度變化舉例背景運動補償技術特征點的選擇Moravec算法根據Moravec角點檢測算法，可以提出進一步的簡化算法。設F(

19、i,j)表示基準圖像,選取一個33的活動窗口，對于每一象素點(i,j)，分別計算其在程度、垂直、左對角線和右對角線方向上與相鄰象素灰度值的差的平方和，并把其中最小值的稱為該象素點的灰度變化特征值，記為O(i,j)。 再將圖像劃分為互不重疊的網格狀區域，在每一個區域中搜索出灰度變化特征值最大的點即為所要提取的特征點。背景運動補償技術特征點的選擇Harris算法 C.Harris和M.J.Stephens采用了一樣的思想對Moravec算子進展改良,提出了著名的Harris角點檢測算子也被稱為Plessev算子。其后,又有很多學者對該算法進展改良以順應不同的運用目的。Harris算子具有計算簡單、

20、提取的角點特征均勻合理、可以定量提取特征點以及算子穩定的特點。其中，gx為x方向的梯度，gy為y方向的梯度，G(s)為高斯平滑模板，det為矩陣的行列式，tr為矩陣的跡，k為默許常數。矩陣I中每一點的元素值對應于原圖相應點的興趣值。 Harris和Stephens以為，在平坦區域中(區域的各點灰度值近乎相等)，象素點的自相關矩陣M的兩個特征值相對較小；在邊緣處，某一個特征值較大，而另一個特征值近乎為零；在角點處，兩個特征值相對較大。因此在每個像素點計算22自相關矩陣M，假設這個矩陣的兩個特征值足夠大，就把該像素檢測為角點。為了防止M矩陣特征值的分解，定義了角點呼應函數I。當I值為正時，檢測為角

21、點；當I值為負時，檢測為邊緣；當I值接近零時，檢測為平坦區域。 C. Harris, M. Stephens, “A Combined Corner and Edge Detector Proc. Alvey Vision Conf., Univ. Manchester, pp. 147-151, 1988背景運動補償技術特征點的選擇SUSAN Smith等提出了一種全新而且直觀的新方法低層次圖像處置小核值類似區方法(即small univalue segment assimilating nucleus，簡稱SUSAN 算法)。 S.M. Smith, M. Brady, “SUSAN -

22、A New Approach to Low Level Image Processing International Journal of Computer Vision, Vol. 23(1), pp. 45-78, 1997背景運動補償技術特征點的選擇SUSAN 圓形模板可以選用簡單的33像素窗口的模板,但為了準確、穩定和有效地斷定角點,圓形模板普通選用77像素窗口的模板。該模板包含關于中心對稱的37個像素 g普通取Tem(r0)/2，取邊緣的g值要大一些，普通最大為3Tem(r0)/4 或者：背景運動補償技術特征點的選擇MIC 算法 最小亮度變化(Minimum Intensity Ch

23、ange, MIC)算法，是Trajkovic 等提出的一種快速角點檢測算法。該算法自創了SUSAN算法中USAN的圓形模板，同時定義了一個角點呼應函數，利用多格算法來檢測特征點。 CRF的計算分為兩步，首先計算程度和豎直方向的灰度變化：那么反響函數值為：背景運動補償技術特征點的選擇MIC 算法 假設R小于一個預先設定的門限值，那么此時的中心點不是角點，假設大于該門限值，那么利用插值方法計算在對角方向的灰度變化，此時的CRF為： 背景運動補償技術特征點的選擇MIC 算法要使二次函數有最小值，那么必需A0，同時反響函數在正方形上有最小值，即x的極大點必需在0，1范圍內，那么必需保證0-B/A1。

24、化簡得到B0,那么令CRF值為： 假設不滿足B0的條件，那么M. Trajkovic, M. Hedley, “Fast Corner Detection Image and Vision Computing, Vol. 16(2), pp. 75-87, 1998背景運動補償技術特征點的選擇MIC 算法最后，多格算法用于MIC中來找到角點的步驟為：在一個低分辨率的圖像的每個像素點處利用計算簡單的CRF，把CRF大于門限T1的像素點標志為候選角點。在高分辨率的圖像中，對每個候選角點：利用計算CRF，假設呼應低于門限T2，那么該像素點以為不是角點；假設a)中的呼應值大于門限T2，那么進一步運用在

25、MIC 中引見過的插值方法來得到一個新的CRF，假設小于門限T2，那么像素點不是角點。采用NMSnon-maximum suppression方法來找到具有部分最大的CRF的像素點，并把它們標志為角點。背景運動補償技術特征點的選擇改良的MIC 算法AABBPPQQ十字模版圓周插值C首先，利用十字模板求得四鄰域的象素均值A、A、B、B；然后，利用圓周插值計算角點呼應函數；最后，利用多格算法找到角點。背景運動補償技術特征點的選擇改良的MIC 算法背景運動補償技術特征點的選擇改良的MIC 算法線性插值MIC圓周插值十字模板 MIC線性插值MIC加椒鹽噪聲圓周插值十字模板 MIC加椒鹽噪聲背景運動補償

26、技術特征點匹配所謂特征點的匹配，就是在待匹配圖像中找到基準圖像中的每一特征點的獨一匹配點。經過兩幀之間特征點的位置變化，可以求出該特征點的部分運動矢量，而將一切特征點在兩幀之間的位置變化信息代入運動模型，即可求出背景的全局運動矢量。因此，一切的特征點能否準確匹配的關鍵在于所選用的匹配準那么和搜索戰略。以基準圖像的特征點為中心，構造了一定大小的MxM5x5或7x7的圖像塊，利用這些圖像塊，在待匹配圖像的一定范圍內進展搜索，來完成待匹配圖像中的匹配特征點的獲取。需求指出的是，全部特征點中，只需部分能得到正確的匹配。這是由于匹配算法本身的缺陷或特征點由于其它的緣由而消逝，如被遮擋或移出視野等。背景運

27、動補償技術特征點匹配準那么最小均方差準那么(mean square error，MSE) 最小平均絕對差準那么(mean absolute difference，MAD) 最大匹配像素數量準那么(matching pixel count，MPC) 背景運動補償技術搜索戰略為了求得最正確運動矢量，需求計算一切能夠的運動矢量對應的匹配誤差，然后選擇最小匹配誤差對應的矢量就是最正確位移估計值，這就是全搜索戰略Exhaustive Search (ES)。這種戰略的最大優點是可以找到全局最優值，但非常浪費時間，因此，人們提出了各種各樣的快速搜索戰略。雖然快速搜索戰略得到的能夠是部分最優值，但由于其快速

28、計算的適用性，在實踐中得到了廣泛的運用。目前，較為常用的快速搜索戰略有：三步搜索法Three Step Search (TSS), 新三步搜索法New Three Step Search (NTSS), 四步搜索法Four Step Search (4SS), 菱形搜索法Diamond Search (DS)和自順應十字模板搜索法Adaptive Rood Pattern Search (ARPS)等。背景運動補償技術搜索戰略三步搜索法TSS是最早的一種快速搜索算法。該算法思緒簡單，是很流行的搜索戰略，特別適宜低碼率視頻運用，如視頻會議和視頻。三步搜索法的思緒是：首先搜索步長等于或略大于最大搜

29、索范圍的一半。每一步比較9個搜索點：方型的中心點和8個位于搜索區域邊境的點。以后，搜索步長每步減半，直至步長為1時終了搜索。每步的中心移到當前步的最好的匹配點。背景運動補償技術搜索戰略新三步搜索法NTSS是對三步搜索法的改良，在MPEG1、H.261等規范中被廣泛采用。人們發現，真實的視頻序列中，運動向量普通是中心偏置的。為了開發這種特性，NTSS 修正了TSS第一步的檢查點方式，搜索額外的8個點，即中心點的八個鄰域點。同時運用了半路停頓技術halfway- stop加速靜止塊的搜索。該方法堅持了TSS 算法的簡單、規整性，運動補償誤差和魯棒性比TSS更好。背景運動補償技術搜索戰略另一種運用中

30、心偏置的搜索方式的搜索戰略是四步搜索4SS，它在第一步搜索中采用一個較小的5x5 網格，結果該方法對于搜索窗口為7的只需求4步就可到達邊境檢查點。搜索過程根本上和TSS 一樣。4SS相比NTSS 需求更少的搜索點。背景運動補償技術搜索戰略在視頻圖像緊縮協議(如MPEG, H.261, H.263) 中,菱形搜索戰略DS因可以提高編解碼效率而被廣泛運用。其實DS與4SS的搜索思緒很類似，DS主要的特點是采用了菱型搜索模板一個大菱形搜索模版LDSP和一個小菱形搜索模版SDSP。相比較其他運動估計方法,它具有平均搜索點少的優勢,這是由于搜索最正確運動向量時,在3x3鉆石外形的區域內搜索點比3x3正方

31、外形的區域內搜索點要少一半。在DS中,先反復運用LDSP進展搜索,直到本次搜索誤差最小的那個點出如今模板的中心,接著再以這個最小誤差點為中心,以SDSP為新的搜索模板進展搜索,最后將這一搜索中誤差最小的那個點作為最正確匹配點。背景運動補償技術搜索戰略前面提到的一系列搜索戰略都是針對各個特征塊進展各自獨立的匹配搜索，即不同塊之間的搜索過程是相互獨立的。而實踐中，當前塊與其相鄰塊的運動矢量有很強的相關性，利用這一特點，引見一種基于運動矢量預測的搜索戰略，即自順應十字模板搜索Adaptive Rood Pattern Search, ARPS。自順應十字模板搜索(ARPS)包括兩個步驟：初步搜索和準

32、確部分搜索。對于每一個特征塊，初步搜索僅執行一次，為以后的準確搜索找到一個好的起始點。經過這個步驟，不用要的中間搜索和墮入部分最小點的情況將減少。在初始搜索步驟中，運用了自順應十字模板(ARP)，ARP的大小由每個特征塊自動決議。在準確部分搜索階段，那么運用一個固定大小的十字模板，直到搜索到最后的運動矢量MV。 Yao NIE, Kai-Kuang MA, “Adaptive Rood Pattern Search for Fast Block-matching Motion Estimation IEEE transactions on image processing 11:1212, 1

33、442-1449, Institute of Electrical and Electronics Engineers, 2002背景運動補償技術搜索戰略自順應搜索方式用于初始搜索。十字模型的外形是對稱的，4個搜索點分別位于4個頂點上，ARP的主要構造是一個十字外形，它的尺寸指的是從一個頂點到中心點之間的間隔。十字外形的選擇是基于對實踐視頻序列的運動特征的察看。MV在程度和垂直方向上的分布比在其他方向上的分布概率要高，這是由于相機的運動大部分是在這些方向上。而且，任何一個MV都可以分解為程度分量和垂直分量，對于一個有恣意方向MV的運動對象，十字外形方式至少可以檢測到運動對象的主要趨向，這就是初

34、始搜索步驟想要到達的目的。另外，除了這4個頂點外，在ARP中還參與了預測MV，由于它極能夠與目的MV類似。這樣，在初始步驟中檢測到準確的運動的概率將添加。當預測MV在程度或者垂直方向上時，能夠與4個指向頂點的MV中的一個相重疊。在決議 ARP的尺寸時，初始想法是讓它等于預測MV的長度，也就是下式： 這里是ARP的大小，Round是舍入取整。MVpredict(x)和MVpredict(y)分別是預測MV的程度和垂直分量。背景運動補償技術搜索戰略為了簡化處置，我們運用下式來決議ARP的大小：總之，自順應方式包括一個十字方式，并且計入了預測MV代表的那個點，所以，在初始搜索階段，假設預測MV不為零

35、，那么有5個或者4個(有重疊)搜索點需求檢測，假設MV為零，那么僅有一個點需求檢測。經過初步搜索以后，新的搜索中心位于整體最小BDM最能夠存在的區域，減少了中間不用要的搜索途徑。而且，錯誤曲面單峰的假設在這個區域將堅持有效。所以，可以運用一個固定、簡單且尺寸小的搜索方式來完成部分準確搜索。思索運用兩種最簡單的方式，一個是單位五點十字方式，這與DS中運用的SDSP一樣；另一個是3X3正方形方式。后一種方式需求的檢測點要多，所以普通選用前一種方式。 背景運動補償技術全局運動參數的魯棒估計 在特征點匹配的根底之上，可以利用特征點之間一一對應的位置關系來估計全局運動參數，即仿射變換模型參數。設時辰tk

36、的某一特征點坐標為(X, Y)，其在時辰tk+1的坐標為(X, Y)。假設以二維仿射變換描畫特征點的運動，兩個特征點間的關系可以表示為：二維仿射變換有六個參數，需求三個不共線的特征點及其匹配點才干求得獨一解。僅僅由三對特征點估算全局的二維仿射變換參數并不合理，由于假設一個特征點的位置有較大的誤差，或者錯誤的匹配都會給最終的計算結果帶來很大的偏向。為此可以采用最小二乘法，用一切知的特征點來求解變換參數。背景運動補償技術全局運動參數的魯棒估計最小二乘估計算法存在一個內在的缺陷，即無法分辨和排除錯誤的特征點匹配。特征點的匹配是特征點跟蹤的瓶頸問題，現有方法的匹配結果通常會帶有一些錯誤的匹配，前文所運

37、用的方法也不例外。假設將這些錯誤的對應特征點代入最小二乘估計中，勢必呵斥很大的偏向。 魯棒參數估計(robust estimation)研討在觀測值出現粗差(gross error，即錯誤和異常)的情況下，如何求得最優的參數估計。魯棒估計既可以抑制野點數據的影響，又具備普通估計方法的統計特性，是更廣義的最優估計。在圖像處置和機器視覺領域，M估計(M-estimator)和最小平方中值(Least Median of SquaresLMS)都是常用的魯棒估計方法。C.V. Stewart, “Robust Parameter Estimation in Computer Vision SIAM

38、Rev., vol.41, no. 3, pp.513-537, 1999背景運動補償技術M估計M估計是一種廣義的最大似然估計方法。參數a的M估計定義為：、是一個魯棒損失函數robust loss function，且是一個關于|u|的單調非減函數，常用的函數有Tukey, Cauchy, Huber函數等。ri,a是第i個數據相對于估計值a的偏向。本文在對應特征點仿射變換參數的估算中，將其定義為特征點經參數變換后的值與匹配點的間隔，i為ri,a的規范方差。對上式求解可得：背景運動補償技術 M估計假設引入權重函數： ，那么有：其實該式表示的就是迭代加權最小二乘法(Iterative Re-we

39、ighted Least Squares, IRLS)該方法在每一步迭代中，根據相對于當前估計值a的偏向和方差，求每個數據的權重，進而在下一步迭代中，利用剛剛求得的權重值，運用加權最小二乘法(Weighted Least Squares)得到一個新的估計值a，以及每個數據的偏向和方差。照此循環，假設干次迭代后IRLS收斂到最終的估計值a。a的初始值通常由最小二乘法估算。LSM-estimator (IRLS)M-estimator (Cauchy)M-estimator (Huber)背景運動補償技術最小平方中值LMS最小平方中值法計算一切數據點相對于估計值a的偏向的平方，將它們排序，取中值。

40、最小中值對應的估計值a可以作為最終估計，可以記為：實際上LMS的野點所占比例最多可以到達50%，即對于野點數量不超越一半的數據點集，LMS都可以求得魯棒的結果。上式是不可微的，通常運用隨機采樣的方法求解。從全部N個數據中隨機選取S個子集，每個子集有k個數據，k通常是估計a所需的最少數據個數。每個子集都可以求出一個估計值和偏向的平方，最后從中選擇一個最優估計。這里要求子集的數量S必需足夠大，以使得可以致少得到一個子集S的每一數據都不是野點，即至少有一個子集的一切數據都是可用的，才可以得到一個準確的估計值。假設數據集中內點即可靠點的概率是p，那么抽取到一個沒有野點的子集的概率是pk，S個子集，至少

41、有一個子集的數據都是內點的概率為：背景運動補償技術最小平方中值LMS推算得到S的值為：只需給出Pg的值，就可以估算S，普通地，Pg=0.99。假設k=3，p=0.7，那么樣本子集數量S=11。假設k=2，p=0.5，那么S=16。此外，還有許多擴展LMS的魯棒估計方法，如MUSE，MINPRAN，它們的抗噪聲才干更強，失效點可以高于0.5，還可以得到多個估計值。背景運動補償技術RANSAC算法RANSAC算法即隨機樣本一致算法(Random Sample Consensus algorithm)，也可以處置含有很大比例野點的情形。與LMS類似，RANSAC也是經過隨機選取一定量的樣本，分別估計

42、a，再從中選取一個最優的作為最終的估計值。不同的是評價估計值a的方法。RANSAC用內點個數來量化a的質量。 為了清楚解釋RANSAC算法的過程，思索一個經典的數值分析的例子：尋覓一條直線，使得它可以擬合一個2維的點集。這可以進一步表達成：尋覓一個1維仿射變換y=ax+b，擬合一組2維平面中的點。這實踐上有兩個問題：1.一條擬合數據的直線；2.對有效點和無效點的分類。可以處理這個問題的魯棒的算法有很多，但是它們各自有不同的順應情況，運用哪一種依賴于無效點的比例。比如，假設知道只需一個無效點，那么可以經過輪番刪除一個點并對剩余的點進展最優直線估計。假設無效點的比例很大，這樣的方法就不適用了，這時

43、候我們需求一個在無效點比例較大的情況下依然有效的估計算法，這就是RANSAC算法。M. A. Fischler, R. C. Bolles, “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography Comm. of the ACM, Vol 24, pp 381-395, 1981Task:Estimate best lineRANSAC算法的思想簡單而巧妙：首先隨機地選擇兩個點，這兩個點確定了一條直線。我們稱直線的支撐為在這條直線的一定間隔范圍內的點的數目。這樣的隨機選擇反復數次，然后具有最大支撐的直線被確以為是點集的擬合。在擬合的誤差間隔范圍內的點被以為是有效點，它們構成所謂的一致集，反之