運動視頻場景中目標檢測與跟蹤技術(shù)應用研究

運動視頻場景中目標檢測與跟蹤技術(shù)應用研究第一頁，共62頁。相對于靜止場景，所謂運動場景中的目標檢測與跟蹤，是指在目標運動的同時，攝像機也由于運載平臺的姿態(tài)或位置改變而發(fā)生運動，構(gòu)成目標與背景共同變化下的目標檢測與跟蹤。運動場景中目標檢測與跟蹤技術(shù)的目的在于準確地探測目標、合理地提取目標特征、精確地跟蹤目標，同時要考慮算法的實時可操作性。由于該技術(shù)在軍事、交通、工業(yè)以及生物醫(yī)學等領(lǐng)域具有廣泛的應用前景，從而激發(fā)了國內(nèi)外廣大科研工作者的濃厚興趣，成為計算機視覺領(lǐng)域的一個熱點。

第二頁，共62頁。第三頁，共62頁。研究現(xiàn)狀

Collins,Lipton,Kanade,Fujiyoshi,Duggins,Tsin,Tolliver,Enomoto,Hasegawa,“ASystemforVideoSurveillanceandMonitoring:VSAMFinalReport"TechnicalreportCMU-RI-TR-00-12,RoboticsInstitute,CarnegieMellonUniversity,May,2000.1997年，美國國防高級研究項目署設(shè)立了以卡內(nèi)基梅隆大學牽頭，麻省理工學院等高校參與的視覺監(jiān)控重大項目VSAM，主要研究用于戰(zhàn)場及普通民用場景監(jiān)控的自動視頻理解技術(shù)美國康奈爾大學計算機系設(shè)計了一套航拍視頻檢測與持續(xù)跟蹤系統(tǒng)，該系統(tǒng)能夠?qū)Χ噙\動目標實現(xiàn)長時間的準確跟蹤，即使發(fā)生短時間內(nèi)目標被遮擋或目標時靜時動的情況2005年，美國中央佛羅里達大學計算機視覺實驗室開發(fā)出了基于MATLAB的COCOA系統(tǒng)，用于無人機低空航拍視頻圖像的目標檢測與跟蹤處理BellW,FelzenszwalbP,HuttenlocherD,“DetectionandLongTermTrackingofMovingObjectinAerialVideo”,1999.03.26.SaadAli,MubarakShah,“COCOA-TrackinginAerialImagery”SPIEAirborneIntelligence,Surveillance,Reconnaissance(ISR)SystemsandApplications,Orlando,2006,COCOAHomepage

第四頁，共62頁。IsmailHaritaoglu,DavidHarwood,LarryS.Davis,“ActiveOutdoorSurveillance”ICIAP1999:1096-1099（ComputerVisionLab,MarylandUniversity）I.Cohen,G.Medioni,“DetectingandTrackingMovingObjectsinVideofromandAirborneObserver”Proc.IEEEImageUnderstandingWorkshop,pp.217-222,1998（UniversityofSouthernCaliforniaInstituteforRoboticsandIntelligentSystems）RonaldJones,DavidM.Booth,NicholasJ.Redding,“VideoMovingTargetIndicationintheAnalysts’DetectionSupportSystem”May,2006（DefenseScienceandTechnologyOrganization,Australia）KhaledKaaniche,BenjaminChampion,ClaudePégard,PascalVasseur“AVisionAlgorithmforDynamicDetectionofMovingVehicleswithaUAV”

IEEEInternationalConferenceonRoboticsandAutomation2005(ICRA’05),April2005,Barcelone（UniversityofPicardieAmiensFrance）HaritaogluI,HarwoodD,DavisL,“W4:Real-timeSurveillanceofPeopleandTheirActivities”IEEETransPatternAnalysisandMachineIntelligence,2000,22(8):809-830（IBMandComputerVisionLab,MarylandUniversity）研究現(xiàn)狀

第五頁，共62頁。VSAM

VSAM系統(tǒng)是在1997年至1999年間，美國國防高級研究計劃局資助卡內(nèi)基梅隆大學和薩爾諾夫戴維研究中心等著名大學和公司合作聯(lián)合研制的視頻監(jiān)視與監(jiān)控系統(tǒng)。目標是開發(fā)自動視頻理解技術(shù)，并用于實現(xiàn)未來戰(zhàn)爭、人力費用昂貴、非常危險或者人力無法實現(xiàn)等場合的監(jiān)控。該系統(tǒng)融合了數(shù)字攝像機、音頻采集頭、紅外和微波報警探測器、溫度探測器等多種類型的傳感器，可以對監(jiān)控地區(qū)進行全方位的晝夜監(jiān)控。使用了地理信息和三維建模技術(shù)，提供可視化圖形操作界面，當視頻分析處理器報告了運動對象、對象類別及位置之后，操作員不僅可以在地理信息界面上進行虛擬對象標記，而且還能在輔助窗口觀察對象的真實活動情況。在機載航空攝像機方面，不需要經(jīng)常性的人工操縱，就能自動對準地面監(jiān)視目標，實現(xiàn)對重要目標的長時間監(jiān)視。第六頁，共62頁。VSAM使用架設(shè)在高處多方位旋轉(zhuǎn)云臺上的單個攝像機，可以全方位地實施視頻監(jiān)控。系統(tǒng)首先有規(guī)律地初始化一系列背景圖像，然后利用基于特征區(qū)域的方法將實際攝錄的視頻圖與相應的背景圖作匹配，再利用背景減除法檢測運動目標。第七頁，共62頁。VSAM由于傳統(tǒng)的卡爾曼濾波方法只能處理單峰問題，該系統(tǒng)對傳統(tǒng)的卡爾曼濾波思想進行了擴展，并使用了帶目標模板更新的相關(guān)匹配算法實現(xiàn)了多目標的跟蹤。

第八頁，共62頁。VSAM針對機載航空攝像機所拍攝的視頻圖像，薩爾諾夫戴維研究中心研發(fā)了檢測和跟蹤獨立地面車輛目標的視頻圖像理解技術(shù)。該技術(shù)的關(guān)鍵在于對航空攝像機的自運動補償，對經(jīng)過補償?shù)膱D像，利用三幀差減的方法檢測目標。第九頁，共62頁。美國康奈爾大學計算機系設(shè)計的航拍視頻圖像目標檢測與持續(xù)跟蹤系統(tǒng)的特色在于，能夠?qū)Χ噙\動目標實現(xiàn)較長時間的準確跟蹤，即使在短時間內(nèi)目標被遮擋或移出視場以及目標時靜時動。

該系統(tǒng)在運動背景估計與補償中所涉及的主要技術(shù)是基于Kanade-Lucas-Tomasi算法的特征點跟蹤和基于M估計的魯棒性仿射參數(shù)估計。然后利用三幀差減的方法檢測目標運動，利用形態(tài)學操作分割圖像并定位運動目標。對多目標進行標記之后，利用Hausdorff距離匹配和模板更新的方法對目標進行長時間的跟蹤。4576102123152159253298第十頁，共62頁。COCOACOCOA系統(tǒng)是一種無人機航拍圖像目標跟蹤系統(tǒng)。該系統(tǒng)針對一段視頻圖像序列，通過三大技術(shù)環(huán)節(jié)，即背景運動補償、運動檢測與目標跟蹤，來完成對目標的檢測與跟蹤。該系統(tǒng)基于MATLAB平臺，可以適用于不同的光傳感器（可見光或紅外），最小的可跟蹤目標約為100象素大小。該系統(tǒng)對機載光電傳感器或紅外傳感器所攝視頻圖像進行魯棒性背景運動補償，并可生成全景圖，利于更高層次的應用。對圖像中多種運動目標（如汽車、坦克、摩托車等）進行可靠性檢測并進行持久地跟蹤。第十一頁，共62頁。COCOA在背景運動補償方面，利用Harris角點檢測算法分別提取相鄰兩幀圖像的特征點，對每一特征點先進行簡單的粗匹配，而后利用RANSAC魯棒估計算法完成特征點的篩選，通過篩選后的特征點的運動矢量集合來估計全局運動矢量。在運動檢測方面，通過累積幀差法對汽車、卡車、坦克、摩托車等獨立運動進行檢測，再利用數(shù)字圖像形態(tài)學操作去除噪聲、捕捉大致的目標區(qū)域，再利用幾何活動輪廓的水平集方法提取目標輪廓，最后利用基于核函數(shù)的方法（如MeanShift方法）與模板更新實現(xiàn)目標跟蹤。第十二頁，共62頁。COCOA背景運動補償基于特征+基于灰度梯度運動檢測累積幀差法+形態(tài)學操作目標跟蹤LevelSet方法+MeanShift方法視頻序列COCOA系統(tǒng)的基本技術(shù)環(huán)節(jié)第十三頁，共62頁。歸納起來，運動場景中目標檢測與跟蹤技術(shù)主要包括以下三個關(guān)鍵技術(shù)：背景補償與圖像預處理：消除背景運動、隨機噪聲對目標檢測與跟蹤的影響。圖像分割與目標檢測：利用圖像分割技術(shù)從圖像中檢測出可能的運動目標。特征提取和目標跟蹤：對檢測出的目標提取可識別的特征，依據(jù)這些特征在后續(xù)的視頻圖像序列中對目標進行跟蹤。第十四頁，共62頁。針對視頻圖像目標檢測與跟蹤技術(shù)，根據(jù)三維場景中目標距離成像傳感器的探測距離，可劃分為三種情況：①微弱點狀目標的檢測，即當目標距離成像傳感器很遠時，目標在圖像平面上只占幾個像素，呈現(xiàn)為微弱點狀目標，信噪比較低；②擴展目標的檢測，即當目標距離成像傳感器較近時，目標在圖像平面上表現(xiàn)為擴展目標，一般其為在視場中覆蓋100×100像素以上，占視場比例較大的大型目標；③介于上述兩種情況之間，此時目標在圖像平面上一般不超過100×100個像素，具有一定的可視對比度。這三種情況下的目標檢測與跟蹤各有其特點，處理方法差異很大。本文的研究工作屬于第三種情況，它是應用最廣泛的一種情況，對于它的研究具有重要的意義。第十五頁，共62頁。背景運動補償技術(shù)

在視頻運動目標檢測過程中，由于攝像機的運動，導致圖像序列中運動目標和背景的相應運動。當目標與背景一起變化時，將使得目標檢測變得復雜起來。為了從動態(tài)場景中檢測出運動目標，通常需要對背景運動進行補償。背景運動補償技術(shù)的核心問題是背景運動矢量的估計。傳統(tǒng)的運動估計采用平動來建模運動場（效果差）目前，常采用具有豐富描述參數(shù)的仿射變換和透射變換來建模運動場

第十六頁，共62頁。背景運動補償技術(shù)－仿射模型攝像機的參數(shù)模型

基于平行投影的六參數(shù)仿射模型

利用當前幀和前一幀的圖像對參數(shù)進行估計，就可以得到圖像的運動參數(shù)。

第十七頁，共62頁。背景運動補償技術(shù)－運動矢量估計運動矢量估計技術(shù)的研究總是圍繞著計算復雜度和檢測精度這對矛盾進行的。目前，運動矢量估計的算法主要包括灰度投影法、光流場法、圖像塊匹配法、特征匹配法和相位法等。傳統(tǒng)的灰度投影法盡管該方法實現(xiàn)簡單，但只能解決平移運動的問題，雖然后來有學者進行了改進，但也只能解決很有限的旋轉(zhuǎn)運動的問題。

光流場法的計算精度很高，但涉及到變分運算，計算較復雜，而且對噪聲極為敏感。

基于傅氏變換的方法雖然計算精度也很高，但采用了傅氏變換、相關(guān)運算或者極坐標變換，計算復雜度同樣很高。

目前較為常用的方法是圖像塊匹配法和特征匹配法。針對所研究的對象，本文采用基于特征點匹配的運動估計算法。特征點匹配的關(guān)鍵在于特征點的選擇和匹配策略的選擇。第十八頁，共62頁。背景運動補償技術(shù)－特征點的選擇圖像中的特征點（也稱為角點）沒有明確的數(shù)學定義，但人們普遍認為特征點是二維圖像亮度變化劇烈的點或圖像邊緣曲線的曲率極大值的點，這些點體現(xiàn)了圖像圖形的重要特征。相比于塊匹配法，利用這些特征點來估計運動矢量可以有效地減少數(shù)據(jù)量，提高計算的速度，且有利于圖像的可靠匹配。有關(guān)于角點檢測的研究開始于二十世紀七十年代，到目前為止，學者們已經(jīng)提出了很多的算法，比較經(jīng)典的算法有：Moravec算法、Harris算法、MIC算法、SUSAN算法等。理想的角點、邊緣和平坦地區(qū)示例：第十九頁，共62頁。背景運動補償技術(shù)－特征點的選擇－Moravec算法

Moravec于1977年提出了利用灰度方差提取點特征的算子。該算法的思想非常簡單，后來的很多算法都是基于該算子改進的。Moravec角點檢測算法的具體步驟是：計算每個像素的興趣值(interestvalue),即以該像素為中心,取一個n×n的窗口,計算0度,45度,90度,135度四個方向的灰度差平方和,取其中的最小值為該像素的興趣值。根據(jù)實際圖像設(shè)定一個閾值,遍歷整個圖像，以興趣值大于該閾值的點為候選點。閾值得選擇應以候選點中包括需要的特征點，而又不含過多的非特征點。再選一個一定大小的窗口,以該窗口遍歷灰度圖像,在此過程中取窗口中興趣值最大的候選點為特征點。綜上所述，Moravec算子是在四個主要方向上，選擇具有極大極小灰度方差的點作為特征點。H.P.Moravec,“TowardsAutomaticVisualObstacleAvoidance”Proc.5thInternationalJointConferenceonArtificialIntelligence,pp.584,1977第二十頁，共62頁。背景運動補償技術(shù)－特征點的選擇－Moravec算法以3x3窗口計算右上角的灰度變化舉例第二十一頁，共62頁。背景運動補償技術(shù)－特征點的選擇－Moravec算法

根據(jù)Moravec角點檢測算法，可以提出進一步的簡化算法。設(shè)F(i,j)表示基準圖像,選取一個3×3的活動窗口，對于每一象素點(i,j)，分別計算其在水平、垂直、左對角線和右對角線方向上與相鄰象素灰度值的差的平方和，并把其中最小值的稱為該象素點的灰度變化特征值，記為O(i,j)。

再將圖像劃分為互不重疊的網(wǎng)格狀區(qū)域，在每一個區(qū)域中搜索出灰度變化特征值最大的點即為所要提取的特征點。第二十二頁，共62頁。背景運動補償技術(shù)－特征點的選擇－Harris算法C.Harris和M.J.Stephens采用了相同的思想對Moravec算子進行改進,提出了著名的Harris角點檢測算子（也被稱為Plessev算子）。其后,又有很多學者對該算法進行改進以適應不同的應用目的。Harris算子具有計算簡單、提取的角點特征均勻合理、可以定量提取特征點以及算子穩(wěn)定的特點。其中，gx為x方向的梯度，gy為y方向的梯度，G(s)為高斯平滑模板，det為矩陣的行列式，tr為矩陣的跡，k為默認常數(shù)。矩陣I中每一點的元素值對應于原圖相應點的興趣值。Harris和Stephens認為，在平坦區(qū)域中(區(qū)域的各點灰度值近乎相等)，象素點的自相關(guān)矩陣M的兩個特征值相對較?。辉谶吘壧?，某一個特征值較大，而另一個特征值近乎為零；在角點處，兩個特征值相對較大。因此在每個像素點計算2×2自相關(guān)矩陣M，假如這個矩陣的兩個特征值足夠大，就把該像素檢測為角點。為了避免M矩陣特征值的分解，定義了角點響應函數(shù)I。當I值為正時，檢測為角點；當I值為負時，檢測為邊緣；當I值接近零時，檢測為平坦區(qū)域。

第二十三頁，共62頁。C.Harris,M.Stephens,“ACombinedCornerandEdgeDetector”Proc.AlveyVisionConf.,Univ.Manchester,pp.147-151,1988第二十四頁，共62頁。背景運動補償技術(shù)－特征點的選擇－SUSAN

Smith等提出了一種全新而且直觀的新方法——低層次圖像處理小核值相似區(qū)方法(即smallunivaluesegmentassimilatingnucleus，簡稱SUSAN算法)。

S.M.Smith,M.Brady,“SUSAN-ANewApproachtoLowLevelImageProcessing”InternationalJournalofComputerVision,Vol.23(1),pp.45-78,1997第二十五頁，共62頁。背景運動補償技術(shù)－特征點的選擇－SUSAN圓形模板可以選用簡單的3×3像素窗口的模板,但為了準確、穩(wěn)定和有效地判定角點,圓形模板一般選用7×7像素窗口的模板。該模板包含關(guān)于中心對稱的37個像素g一般取Tem(r0)/2，取邊緣的g值要大一些，一般最大為3Tem(r0)/4

或者：第二十六頁，共62頁。背景運動補償技術(shù)－特征點的選擇－MIC算法

最小亮度變化(MinimumIntensityChange,MIC)算法，是Trajkovic等提出的一種快速角點檢測算法。該算法借鑒了SUSAN算法中USAN的圓形模板，同時定義了一個角點響應函數(shù)，利用多格算法來檢測特征點。CRF的計算分為兩步，首先計算水平和豎直方向的灰度變化：則反應函數(shù)值為：第二十七頁，共62頁。背景運動補償技術(shù)－特征點的選擇－MIC算法若R小于一個預先設(shè)定的門限值，則此時的中心點不是角點，如果大于該門限值，則利用插值方法計算在對角方向的灰度變化，此時的CRF為：

第二十八頁，共62頁。背景運動補償技術(shù)－特征點的選擇－MIC算法要使二次函數(shù)有最小值，則必須A>0，同時反應函數(shù)在正方形上有最小值，即x的極大點必須在（0，1）范圍內(nèi)，則必須保證0<-B/A<1。化簡得到B<0且A+B>0,則令CRF值為：

若不滿足B<0并且A+B>0的條件，則M.Trajkovic,M.Hedley,“FastCornerDetection”ImageandVisionComputing,Vol.16(2),pp.75-87,1998第二十九頁，共62頁。背景運動補償技術(shù)－特征點的選擇－MIC算法最后，多格算法用于MIC中來找到角點的步驟為：

在一個低分辨率的圖像的每個像素點處利用計算簡單的CRF，把CRF大于門限T1的像素點標志為候選角點。

在高分辨率的圖像中，對每個候選角點：利用計算CRF，假如響應低于門限T2，那么該像素點認為不是角點；若a)中的響應值大于門限T2，則進一步使用在MIC中介紹過的插值方法來得到一個新的CRF，如果小于門限T2，那么像素點不是角點。

采用NMS（non-maximumsuppression）方法來找到具有局部最大的CRF的像素點，并把它們標志為角點。

第三十頁，共62頁。背景運動補償技術(shù)－特征點的選擇－改進的MIC算法AA’BB’PP’QQ’α十字模版圓周插值C首先，利用十字模板求得四鄰域的象素均值A(chǔ)、A’、B、B’；然后，利用圓周插值計算角點響應函數(shù)；最后，利用多格算法找到角點。第三十一頁，共62頁。背景運動補償技術(shù)－特征點的選擇－改進的MIC算法第三十二頁，共62頁。背景運動補償技術(shù)－特征點的選擇－改進的MIC算法第三十三頁，共62頁。線性插值MIC圓周插值十字模板MIC第三十四頁，共62頁。線性插值MIC（加椒鹽噪聲）圓周插值十字模板MIC（加椒鹽噪聲）第三十五頁，共62頁。背景運動補償技術(shù)－特征點匹配

所謂特征點的匹配，就是在待匹配圖像中找到基準圖像中的每一特征點的唯一匹配點。通過兩幀之間特征點的位置變化，可以求出該特征點的局部運動矢量，而將所有特征點在兩幀之間的位置變化信息代入運動模型，即可求出背景的全局運動矢量。因此，所有的特征點能否精確匹配的關(guān)鍵在于所選用的匹配準則和搜索策略。以基準圖像的特征點為中心，構(gòu)造了一定大小的MxM（5x5或7x7）的圖像塊，利用這些圖像塊，在待匹配圖像的一定范圍內(nèi)進行搜索，來完成待匹配圖像中的匹配特征點的獲取。需要指出的是，全部特征點中，只有部分能得到正確的匹配。這是因為匹配算法本身的缺陷或特征點由于其它的原因而消失，如被遮擋或移出視野等。第三十六頁，共62頁。背景運動補償技術(shù)－特征點匹配準則最小均方差準則(meansquareerror，MSE)最小平均絕對差準則(meanabsolutedifference，MAD)

最大匹配像素數(shù)量準則(matchingpixelcount，MPC)

第三十七頁，共62頁。背景運動補償技術(shù)－搜索策略

為了求得最佳運動矢量，需要計算所有可能的運動矢量對應的匹配誤差，然后選擇最小匹配誤差對應的矢量就是最佳位移估計值，這就是全搜索策略（ExhaustiveSearch(ES)）。這種策略的最大優(yōu)點是可以找到全局最優(yōu)值，但十分浪費時間，因此，人們提出了各種各樣的快速搜索策略。盡管快速搜索策略得到的可能是局部最優(yōu)值，但由于其快速計算的實用性，在實際中得到了廣泛的應用。目前，較為常用的快速搜索策略有：三步搜索法（ThreeStepSearch(TSS)）,新三步搜索法（NewThreeStepSearch(NTSS)）,四步搜索法（FourStepSearch(4SS)）,菱形搜索法（DiamondSearch(DS)）和自適應十字模板搜索法（AdaptiveRoodPatternSearch(ARPS)）等。第三十八頁，共62頁。背景運動補償技術(shù)－搜索策略

三步搜索法（TSS）是最早的一種快速搜索算法。該算法思路簡單，是很流行的搜索策略，特別適合低碼率視頻應用，如視頻會議和視頻電話。三步搜索法的思路是：首先搜索步長等于或略大于最大搜索范圍的一半。每一步比較9個搜索點：方型的中心點和8個位于搜索區(qū)域邊界的點。此后，搜索步長每步減半，直至步長為1時結(jié)束搜索。每步的中心移到當前步的最好的匹配點。第三十九頁，共62頁。背景運動補償技術(shù)－搜索策略

新三步搜索法（NTSS）是對三步搜索法的改進，在MPEG1、H.261等標準中被廣泛采用。人們發(fā)現(xiàn)，真實的視頻序列中，運動向量一般是中心偏置的。為了開發(fā)這種特性，NTSS修改了TSS第一步的檢查點模式，搜索額外的8個點，即中心點的八個鄰域點。同時使用了半路停止技術(shù)（halfway-stop）加速靜止塊的搜索。該方法保持了TSS算法的簡單、規(guī)整性，運動補償誤差和魯棒性比TSS更好。第四十頁，共62頁。背景運動補償技術(shù)－搜索策略

另一種使用中心偏置的搜索模式的搜索策略是四步搜索（4SS），它在第一步搜索中采用一個較小的5x5網(wǎng)格，結(jié)果該方法對于搜索窗口為7的只需要4步就可到達邊界檢查點。搜索過程基本上和TSS相同。4SS相比NTSS需要更少的搜索點。第四十一頁，共62頁。背景運動補償技術(shù)－搜索策略

在視頻圖像壓縮協(xié)議(如MPEG,H.261,H.263)中,菱形搜索策略（DS）因可以提高編解碼效率而被廣泛應用。其實DS與4SS的搜索思路很相似，DS主要的特點是采用了菱型搜索模板（一個大菱形搜索模版（LDSP）和一個小菱形搜索模版（SDSP））。相比較其他運動估計方法,它具有平均搜索點少的優(yōu)勢,這是因為搜索最佳運動向量時,在3x3鉆石形狀的區(qū)域內(nèi)搜索點比3x3正方形狀的區(qū)域內(nèi)搜索點要少一半。在DS中,先反復使用LDSP進行搜索,直到本次搜索誤差最小的那個點出現(xiàn)在模板的中心,接著再以這個最小誤差點為中心,以SDSP為新的搜索模板進行搜索,最后將這一搜索中誤差最小的那個點作為最佳匹配點。第四十二頁，共62頁。背景運動補償技術(shù)－搜索策略前面提到的一系列搜索策略都是針對各個特征塊進行各自獨立的匹配搜索，即不同塊之間的搜索過程是相互獨立的。而實際中，當前塊與其相鄰塊的運動矢量有很強的相關(guān)性，利用這一特點，介紹一種基于運動矢量預測的搜索策略，即自適應十字模板搜索（AdaptiveRoodPatternSearch,ARPS）。自適應十字模板搜索(ARPS)包括兩個步驟：初步搜索和精確局部搜索。對于每一個特征塊，初步搜索僅執(zhí)行一次，為以后的精確搜索找到一個好的起始點。通過這個步驟，不必要的中間搜索和陷入局部最小點的情況將減少。在初始搜索步驟中，使用了自適應十字模板(ARP)，ARP的大小由每個特征塊自動決定。在精確局部搜索階段，則使用一個固定大小的十字模板，直到搜索到最后的運動矢量（MV）。YaoNIE,Kai-KuangMA,“AdaptiveRoodPatternSearchforFastBlock-matchingMotionEstimation”IEEEtransactionsonimageprocessing11:1212,1442-1449,InstituteofElectricalandElectronicsEngineers,2002第四十三頁，共62頁。背景運動補償技術(shù)－搜索策略自適應搜索模式用于初始搜索。十字模型的形狀是對稱的，4個搜索點分別位于4個頂點上，ARP的主要結(jié)構(gòu)是一個十字形狀，它的尺寸指的是從一個頂點到中心點之間的距離。十字形狀的選擇是基于對實際視頻序列的運動特征的觀察。MV在水平和垂直方向上的分布比在其他方向上的分布概率要高，這是因為相機的運動大部分是在這些方向上。而且，任何一個MV都可以分解為水平分量和垂直分量，對于一個有任意方向MV的運動對象，十字形狀模式至少可以檢測到運動對象的主要趨向，這就是初始搜索步驟想要達到的目的。另外，除了這4個頂點外，在ARP中還加入了預測MV，因為它極可能與目標MV相似。這樣，在初始步驟中檢測到準確的運動的概率將增加。當預測MV在水平或者垂直方向上時，可能與4個指向頂點的MV中的一個相重疊。在決定ARP的尺寸時，初始想法是讓它等于預測MV的長度，也就是下式：這里Γ是ARP的大小，Round是舍入取整。MVpredict(x)和MVpredict(y)分別是預測MV的水平和垂直分量。第四十四頁，共62頁。背景運動補償技術(shù)－搜索策略為了簡化處理，我們使用下式來決定ARP的大?。?/p>

總之，自適應模式包括一個十字模式，并且計入了預測MV代表的那個點，所以，在初始搜索階段，如果預測MV不為零，那么有5個或者4個(有重疊)搜索點需要檢測，如果MV為零，那么僅有一個點需要檢測。經(jīng)過初步搜索以后，新的搜索中心位于整體最小BDM最可能存在的區(qū)域，減少了中間不必要的搜索路徑。而且，錯誤曲面單峰的假設(shè)在這個區(qū)域?qū)⒈３钟行?。所以，可以使用一個固定、簡單且尺寸小的搜索模式來完成局部精確搜索?？紤]使用兩種最簡單的模式，一個是單位五點十字模式，這與DS中使用的SDSP一樣；另一個是3X3正方形模式。后一種模式需要的檢測點要多，所以一般選用前一種模式。

第四十五頁，共62頁。背景運動補償技術(shù)－全局運動參數(shù)的魯棒估計

在特征點匹配的基礎(chǔ)之上，可以利用特征點之間一一對應的位置關(guān)系來估計全局運動參數(shù)，即仿射變換模型參數(shù)。設(shè)時刻tk的某一特征點坐標為(X,Y)，其在時刻tk+1的坐標為(X’,Y’)。如果以二維仿射變換描述特征點的運動，兩個特征點間的關(guān)系可以表示為：二維仿射變換有六個參數(shù)，需要三個不共線的特征點及其匹配點才能求得唯一解。僅僅由三對特征點估算全局的二維仿射變換參數(shù)并不合理，因為如果一個特征點的位置有較大的誤差，或者錯誤的匹配都會給最終的計算結(jié)果帶來很大的偏差。為此可以采用最小二乘法，用所有已知的特征點來求解變換參數(shù)。第四十六頁，共62頁。背景運動補償技術(shù)－全局運動參數(shù)的魯棒估計最小二乘估計算法存在一個內(nèi)在的缺陷，即無法分辨和排除錯誤的特征點匹配。特征點的匹配是特征點跟蹤的瓶頸問題，現(xiàn)有方法的匹配結(jié)果通常會帶有一些錯誤的匹配，前文所使用的方法也不例外。如果將這些錯誤的對應特征點代入最小二乘估計中，勢必造成很大的偏差。魯棒參數(shù)估計(robustestimation)研究在觀測值出現(xiàn)粗差(grosserror，即錯誤和異常)的情況下，如何求得最優(yōu)的參數(shù)估計。魯棒估計既可以克服野點數(shù)據(jù)的影響，又具備一般估計方法的統(tǒng)計特性，是更廣義的最優(yōu)估計。在圖像處理和機器視覺領(lǐng)域，M估計(M-estimator)和最小平方中值(LeastMedianofSquares——LMS)都是常用的魯棒估計方法。C.V.Stewart,“RobustParameterEstimationinComputerVision”SIAMRev.,vol.41,no.3,pp.513-537,1999第四十七頁，共62頁。背景運動補償技術(shù)－M估計M估計是一種廣義的最大似然估計方法。參數(shù)a的M估計定義為：、是一個魯棒損失函數(shù)（robustlossfunction），且是一個關(guān)于|u|的單調(diào)非減函數(shù)，常用的函數(shù)有Tukey,Cauchy,Huber函數(shù)等。ri,a是第i個數(shù)據(jù)相對于估計值a的偏差。本文在對應特征點仿射變換參數(shù)的估算中，將其定義為特征點經(jīng)參數(shù)變換后的值與匹配點的距離，σi為ri,a的標準方差。對上式求解可得：第四十八頁，共62頁。背景運動補償技術(shù)－M估計若引入權(quán)重函數(shù)：

，則有：其實該式表示的就是迭代加權(quán)最小二乘法(IterativeRe-weightedLeastSquares,IRLS)該方法在每一步迭代中，根據(jù)相對于當前估計值a的偏差和方差，求每個數(shù)據(jù)的權(quán)重，進而在下一步迭代中，利用剛剛求得的權(quán)重值，使用加權(quán)最小二乘法(WeightedLeastSquares)得到一個新的估計值a，以及每個數(shù)據(jù)的偏差和方差。照此循環(huán)，若干次迭代后IRLS收斂到最終的估計值a。a的初始值通常由最小二乘法估算。第四十九頁，共62頁。LSM-estimator(IRLS)M-estimator(Cauchy)M-estimator(Huber)第五十頁，共62頁。背景運動補償技術(shù)－最小平方中值（LMS）

最小平方中值法計算所有數(shù)據(jù)點相對于估計值a的偏差的平方，將它們排序，取中值。最小中值對應的估計值a可以作為最終估計，可以記為：理論上LMS的野點所占比例最多可以達到50%，即對于野點數(shù)量不超過一半的數(shù)據(jù)點集，LMS都可以求得魯棒的結(jié)果。上式是不可微的，通常使用隨機采樣的方法求解。從全部N個數(shù)據(jù)中隨機選取S個子集，每個子集有k個數(shù)據(jù)，k通常是估計a所需的最少數(shù)據(jù)個數(shù)。每個子集都可以求出一個估計值和偏差的平方，最后從中選擇一個最優(yōu)估計。這里要求子集的數(shù)量S必須足夠大，以使得能夠至少得到一個子集S的每一數(shù)據(jù)都不是野點，即至少有一個子集的所有數(shù)據(jù)都是可用的，才可以得到一個準確的估計值。假設(shè)數(shù)據(jù)集中內(nèi)點（即可靠點）的概率是p，則抽取到一個沒有野點的子集的概率是pk，S個子集，至少有一個子集的數(shù)據(jù)都是內(nèi)點的概率為：第五十一頁，共62頁。背景運動補償技術(shù)－最小平方中值（LMS）推算得到S的值為：只要給出Pg的值，就可以估算S，一般地，Pg=0.99。如果k=3，p=0.7，則樣本子集數(shù)量S=11。如果k=2，p=0.5，則S=16。此外，還有許多擴展LMS的魯棒估計方法，如MUSE，MINPRAN，它們的抗噪聲能力更強，失效點可以高于0.5，還可以得到多個估計值。第五十二頁，共62頁。背景運動補償技術(shù)－RANSAC算法

RANSAC算法即隨機樣本一致算法(RandomSampleConsensusalgorithm)，也可以處理含有很大比例野點的情形。與LMS類似，RANSAC也是通過隨機選取一定量的樣本，分別估計a，再從中選取一個最優(yōu)的作為最終的估計值。不同的是評價估計值a的方法。RANSAC用內(nèi)點個數(shù)來量化a的質(zhì)量。為了清楚解釋RANSAC算法的過程，考慮一個經(jīng)典的數(shù)值分析的例子：尋找一條直線，使得它可以擬合一個2維的點集。這可以進一步敘述成：尋找一個1維仿射變換y=ax+b，擬合一組2維平面中的點。這實際上有兩個問題：1.一條擬合數(shù)據(jù)的直線；2.對有效點和無效點的分類?？梢越鉀Q這個問題的魯棒的算法有很多，但是它們各自有不同的適應情況，使用哪一種依賴于無效點的比例。比如，如果知道只有一個無效點，那么可以通過輪流刪除一個點并對剩余的點進行最優(yōu)直線估計。如果無效點的比例很大，這樣的方法就不適用了，這時候我們需要一個在無效點比例較大的情況下仍然有效的估計算法，這就是RANSAC算法。M.A.Fischler,R.C.Bolles,“RandomSampleConsensus:AParadigmforModelFittingwithApplicationstoImageAnalysisandAutomatedCartography”Comm.oftheACM,Vol24,pp381-395,1981第五十三頁，共62頁。Task:EstimatebestlineRANSAC算法的思想簡單而巧妙：首先隨機地選擇兩個點，這兩個點確定了一條直線。我們稱直線的支撐為在這條直線的一定距離范圍內(nèi)的點的數(shù)目。這樣的隨機選擇重復數(shù)次，然后具有最大支撐的直線被確認為是點集的擬合。在擬合的誤差距離范圍內(nèi)的點被認為是有效點，它們構(gòu)成所謂的一