运动视频场景中目标检测与跟踪技术应用研究

运动视频场景中目标检测与跟踪技术应用研究第一页，共62页。相对于静止场景，所谓运动场景中的目标检测与跟踪，是指在目标运动的同时，摄像机也由于运载平台的姿态或位置改变而发生运动，构成目标与背景共同变化下的目标检测与跟踪。运动场景中目标检测与跟踪技术的目的在于准确地探测目标、合理地提取目标特征、精确地跟踪目标，同时要考虑算法的实时可操作性。由于该技术在军事、交通、工业以及生物医学等领域具有广泛的应用前景，从而激发了国内外广大科研工作者的浓厚兴趣，成为计算机视觉领域的一个热点。

第二页，共62页。第三页，共62页。研究现状

Collins,Lipton,Kanade,Fujiyoshi,Duggins,Tsin,Tolliver,Enomoto,Hasegawa,“ASystemforVideoSurveillanceandMonitoring:VSAMFinalReport"TechnicalreportCMU-RI-TR-00-12,RoboticsInstitute,CarnegieMellonUniversity,May,2000.1997年，美国国防高级研究项目署设立了以卡内基梅隆大学牵头，麻省理工学院等高校参与的视觉监控重大项目VSAM，主要研究用于战场及普通民用场景监控的自动视频理解技术美国康奈尔大学计算机系设计了一套航拍视频检测与持续跟踪系统，该系统能够对多运动目标实现长时间的准确跟踪，即使发生短时间内目标被遮挡或目标时静时动的情况2005年，美国中央佛罗里达大学计算机视觉实验室开发出了基于MATLAB的COCOA系统，用于无人机低空航拍视频图像的目标检测与跟踪处理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）KhaledKaâniche,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）研究现状

第五页，共62页。VSAM

VSAM系统是在1997年至1999年间，美国国防高级研究计划局资助卡内基梅隆大学和萨尔诺夫戴维研究中心等著名大学和公司合作联合研制的视频监视与监控系统。目标是开发自动视频理解技术，并用于实现未来战争、人力费用昂贵、非常危险或者人力无法实现等场合的监控。该系统融合了数字摄像机、音频采集头、红外和微波报警探测器、温度探测器等多种类型的传感器，可以对监控地区进行全方位的昼夜监控。使用了地理信息和三维建模技术，提供可视化图形操作界面，当视频分析处理器报告了运动对象、对象类别及位置之后，操作员不仅可以在地理信息界面上进行虚拟对象标记，而且还能在辅助窗口观察对象的真实活动情况。在机载航空摄像机方面，不需要经常性的人工操纵，就能自动对准地面监视目标，实现对重要目标的长时间监视。第六页，共62页。VSAM使用架设在高处多方位旋转云台上的单个摄像机，可以全方位地实施视频监控。系统首先有规律地初始化一系列背景图像，然后利用基于特征区域的方法将实际摄录的视频图与相应的背景图作匹配，再利用背景减除法检测运动目标。第七页，共62页。VSAM由于传统的卡尔曼滤波方法只能处理单峰问题，该系统对传统的卡尔曼滤波思想进行了扩展，并使用了带目标模板更新的相关匹配算法实现了多目标的跟踪。

第八页，共62页。VSAM针对机载航空摄像机所拍摄的视频图像，萨尔诺夫戴维研究中心研发了检测和跟踪独立地面车辆目标的视频图像理解技术。该技术的关键在于对航空摄像机的自运动补偿，对经过补偿的图像，利用三帧差减的方法检测目标。第九页，共62页。美国康奈尔大学计算机系设计的航拍视频图像目标检测与持续跟踪系统的特色在于，能够对多运动目标实现较长时间的准确跟踪，即使在短时间内目标被遮挡或移出视场以及目标时静时动。

该系统在运动背景估计与补偿中所涉及的主要技术是基于Kanade-Lucas-Tomasi算法的特征点跟踪和基于M估计的鲁棒性仿射参数估计。然后利用三帧差减的方法检测目标运动，利用形态学操作分割图像并定位运动目标。对多目标进行标记之后，利用Hausdorff距离匹配和模板更新的方法对目标进行长时间的跟踪。4576102123152159253298第十页，共62页。COCOACOCOA系统是一种无人机航拍图像目标跟踪系统。该系统针对一段视频图像序列，通过三大技术环节，即背景运动补偿、运动检测与目标跟踪，来完成对目标的检测与跟踪。该系统基于MATLAB平台，可以适用于不同的光传感器（可见光或红外），最小的可跟踪目标约为100象素大小。该系统对机载光电传感器或红外传感器所摄视频图像进行鲁棒性背景运动补偿，并可生成全景图，利于更高层次的应用。对图像中多种运动目标（如汽车、坦克、摩托车等）进行可靠性检测并进行持久地跟踪。第十一页，共62页。COCOA在背景运动补偿方面，利用Harris角点检测算法分别提取相邻两帧图像的特征点，对每一特征点先进行简单的粗匹配，而后利用RANSAC鲁棒估计算法完成特征点的筛选，通过筛选后的特征点的运动矢量集合来估计全局运动矢量。在运动检测方面，通过累积帧差法对汽车、卡车、坦克、摩托车等独立运动进行检测，再利用数字图像形态学操作去除噪声、捕捉大致的目标区域，再利用几何活动轮廓的水平集方法提取目标轮廓，最后利用基于核函数的方法（如MeanShift方法）与模板更新实现目标跟踪。第十二页，共62页。COCOA背景运动补偿基于特征+基于灰度梯度运动检测累积帧差法+形态学操作目标跟踪LevelSet方法+MeanShift方法视频序列COCOA系统的基本技术环节第十三页，共62页。归纳起来，运动场景中目标检测与跟踪技术主要包括以下三个关键技术：背景补偿与图像预处理：消除背景运动、随机噪声对目标检测与跟踪的影响。图像分割与目标检测：利用图像分割技术从图像中检测出可能的运动目标。特征提取和目标跟踪：对检测出的目标提取可识别的特征，依据这些特征在后续的视频图像序列中对目标进行跟踪。第十四页，共62页。针对视频图像目标检测与跟踪技术，根据三维场景中目标距离成像传感器的探测距离，可划分为三种情况：①微弱点状目标的检测，即当目标距离成像传感器很远时，目标在图像平面上只占几个像素，呈现为微弱点状目标，信噪比较低；②扩展目标的检测，即当目标距离成像传感器较近时，目标在图像平面上表现为扩展目标，一般其为在视场中覆盖100×100像素以上，占视场比例较大的大型目标；③介于上述两种情况之间，此时目标在图像平面上一般不超过100×100个像素，具有一定的可视对比度。这三种情况下的目标检测与跟踪各有其特点，处理方法差异很大。本文的研究工作属于第三种情况，它是应用最广泛的一种情况，对于它的研究具有重要的意义。第十五页，共62页。背景运动补偿技术

在视频运动目标检测过程中，由于摄像机的运动，导致图像序列中运动目标和背景的相应运动。当目标与背景一起变化时，将使得目标检测变得复杂起来。为了从动态场景中检测出运动目标，通常需要对背景运动进行补偿。背景运动补偿技术的核心问题是背景运动矢量的估计。传统的运动估计采用平动来建模运动场（效果差）目前，常采用具有丰富描述参数的仿射变换和透射变换来建模运动场

第十六页，共62页。背景运动补偿技术－仿射模型摄像机的参数模型

基于平行投影的六参数仿射模型

利用当前帧和前一帧的图像对参数进行估计，就可以得到图像的运动参数。

第十七页，共62页。背景运动补偿技术－运动矢量估计运动矢量估计技术的研究总是围绕着计算复杂度和检测精度这对矛盾进行的。目前，运动矢量估计的算法主要包括灰度投影法、光流场法、图像块匹配法、特征匹配法和相位法等。传统的灰度投影法尽管该方法实现简单，但只能解决平移运动的问题，虽然后来有学者进行了改进，但也只能解决很有限的旋转运动的问题。

光流场法的计算精度很高，但涉及到变分运算，计算较复杂，而且对噪声极为敏感。

基于傅氏变换的方法虽然计算精度也很高，但采用了傅氏变换、相关运算或者极坐标变换，计算复杂度同样很高。

目前较为常用的方法是图像块匹配法和特征匹配法。针对所研究的对象，本文采用基于特征点匹配的运动估计算法。特征点匹配的关键在于特征点的选择和匹配策略的选择。第十八页，共62页。背景运动补偿技术－特征点的选择图像中的特征点（也称为角点）没有明确的数学定义，但人们普遍认为特征点是二维图像亮度变化剧烈的点或图像边缘曲线的曲率极大值的点，这些点体现了图像图形的重要特征。相比于块匹配法，利用这些特征点来估计运动矢量可以有效地减少数据量，提高计算的速度，且有利于图像的可靠匹配。有关于角点检测的研究开始于二十世纪七十年代，到目前为止，学者们已经提出了很多的算法，比较经典的算法有：Moravec算法、Harris算法、MIC算法、SUSAN算法等。理想的角点、边缘和平坦地区示例：第十九页，共62页。背景运动补偿技术－特征点的选择－Moravec算法

Moravec于1977年提出了利用灰度方差提取点特征的算子。该算法的思想非常简单，后来的很多算法都是基于该算子改进的。Moravec角点检测算法的具体步骤是：计算每个像素的兴趣值(interestvalue),即以该像素为中心,取一个n×n的窗口,计算0度,45度,90度,135度四个方向的灰度差平方和,取其中的最小值为该像素的兴趣值。根据实际图像设定一个阈值,遍历整个图像，以兴趣值大于该阈值的点为候选点。阈值得选择应以候选点中包括需要的特征点，而又不含过多的非特征点。再选一个一定大小的窗口,以该窗口遍历灰度图像,在此过程中取窗口中兴趣值最大的候选点为特征点。综上所述，Moravec算子是在四个主要方向上，选择具有极大极小灰度方差的点作为特征点。H.P.Moravec,“TowardsAutomaticVisualObstacleAvoidance”Proc.5thInternationalJointConferenceonArtificialIntelligence,pp.584,1977第二十页，共62页。背景运动补偿技术－特征点的选择－Moravec算法以3x3窗口计算右上角的灰度变化举例第二十一页，共62页。背景运动补偿技术－特征点的选择－Moravec算法

根据Moravec角点检测算法，可以提出进一步的简化算法。设F(i,j)表示基准图像,选取一个3×3的活动窗口，对于每一象素点(i,j)，分别计算其在水平、垂直、左对角线和右对角线方向上与相邻象素灰度值的差的平方和，并把其中最小值的称为该象素点的灰度变化特征值，记为O(i,j)。

再将图像划分为互不重叠的网格状区域，在每一个区域中搜索出灰度变化特征值最大的点即为所要提取的特征点。第二十二页，共62页。背景运动补偿技术－特征点的选择－Harris算法C.Harris和M.J.Stephens采用了相同的思想对Moravec算子进行改进,提出了著名的Harris角点检测算子（也被称为Plessev算子）。其后,又有很多学者对该算法进行改进以适应不同的应用目的。Harris算子具有计算简单、提取的角点特征均匀合理、可以定量提取特征点以及算子稳定的特点。其中，gx为x方向的梯度，gy为y方向的梯度，G(s)为高斯平滑模板，det为矩阵的行列式，tr为矩阵的迹，k为默认常数。矩阵I中每一点的元素值对应于原图相应点的兴趣值。Harris和Stephens认为，在平坦区域中(区域的各点灰度值近乎相等)，象素点的自相关矩阵M的两个特征值相对较小；在边缘处，某一个特征值较大，而另一个特征值近乎为零；在角点处，两个特征值相对较大。因此在每个像素点计算2×2自相关矩阵M，假如这个矩阵的两个特征值足够大，就把该像素检测为角点。为了避免M矩阵特征值的分解，定义了角点响应函数I。当I值为正时，检测为角点；当I值为负时，检测为边缘；当I值接近零时，检测为平坦区域。

第二十三页，共62页。C.Harris,M.Stephens,“ACombinedCornerandEdgeDetector”Proc.AlveyVisionConf.,Univ.Manchester,pp.147-151,1988第二十四页，共62页。背景运动补偿技术－特征点的选择－SUSAN

Smith等提出了一种全新而且直观的新方法——低层次图像处理小核值相似区方法(即smallunivaluesegmentassimilatingnucleus，简称SUSAN算法)。

S.M.Smith,M.Brady,“SUSAN-ANewApproachtoLowLevelImageProcessing”InternationalJournalofComputerVision,Vol.23(1),pp.45-78,1997第二十五页，共62页。背景运动补偿技术－特征点的选择－SUSAN圆形模板可以选用简单的3×3像素窗口的模板,但为了准确、稳定和有效地判定角点,圆形模板一般选用7×7像素窗口的模板。该模板包含关于中心对称的37个像素g一般取Tem(r0)/2，取边缘的g值要大一些，一般最大为3Tem(r0)/4

或者：第二十六页，共62页。背景运动补偿技术－特征点的选择－MIC算法

最小亮度变化(MinimumIntensityChange,MIC)算法，是Trajkovic等提出的一种快速角点检测算法。该算法借鉴了SUSAN算法中USAN的圆形模板，同时定义了一个角点响应函数，利用多格算法来检测特征点。CRF的计算分为两步，首先计算水平和竖直方向的灰度变化：则反应函数值为：第二十七页，共62页。背景运动补偿技术－特征点的选择－MIC算法若R小于一个预先设定的门限值，则此时的中心点不是角点，如果大于该门限值，则利用插值方法计算在对角方向的灰度变化，此时的CRF为：

第二十八页，共62页。背景运动补偿技术－特征点的选择－MIC算法要使二次函数有最小值，则必须A>0，同时反应函数在正方形上有最小值，即x的极大点必须在（0，1）范围内，则必须保证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页。背景运动补偿技术－特征点的选择－MIC算法最后，多格算法用于MIC中来找到角点的步骤为：

在一个低分辨率的图像的每个像素点处利用计算简单的CRF，把CRF大于门限T1的像素点标志为候选角点。

在高分辨率的图像中，对每个候选角点：利用计算CRF，假如响应低于门限T2，那么该像素点认为不是角点；若a)中的响应值大于门限T2，则进一步使用在MIC中介绍过的插值方法来得到一个新的CRF，如果小于门限T2，那么像素点不是角点。

采用NMS（non-maximumsuppression）方法来找到具有局部最大的CRF的像素点，并把它们标志为角点。

第三十页，共62页。背景运动补偿技术－特征点的选择－改进的MIC算法AA’BB’PP’QQ’α十字模版圆周插值C首先，利用十字模板求得四邻域的象素均值A、A’、B、B’；然后，利用圆周插值计算角点响应函数；最后，利用多格算法找到角点。第三十一页，共62页。背景运动补偿技术－特征点的选择－改进的MIC算法第三十二页，共62页。背景运动补偿技术－特征点的选择－改进的MIC算法第三十三页，共62页。线性插值MIC圆周插值十字模板MIC第三十四页，共62页。线性插值MIC（加椒盐噪声）圆周插值十字模板MIC（加椒盐噪声）第三十五页，共62页。背景运动补偿技术－特征点匹配

所谓特征点的匹配，就是在待匹配图像中找到基准图像中的每一特征点的唯一匹配点。通过两帧之间特征点的位置变化，可以求出该特征点的局部运动矢量，而将所有特征点在两帧之间的位置变化信息代入运动模型，即可求出背景的全局运动矢量。因此，所有的特征点能否精确匹配的关键在于所选用的匹配准则和搜索策略。以基准图像的特征点为中心，构造了一定大小的MxM（5x5或7x7）的图像块，利用这些图像块，在待匹配图像的一定范围内进行搜索，来完成待匹配图像中的匹配特征点的获取。需要指出的是，全部特征点中，只有部分能得到正确的匹配。这是因为匹配算法本身的缺陷或特征点由于其它的原因而消失，如被遮挡或移出视野等。第三十六页，共62页。背景运动补偿技术－特征点匹配准则最小均方差准则(meansquareerror，MSE)最小平均绝对差准则(meanabsolutedifference，MAD)

最大匹配像素数量准则(matchingpixelcount，MPC)

第三十七页，共62页。背景运动补偿技术－搜索策略

为了求得最佳运动矢量，需要计算所有可能的运动矢量对应的匹配误差，然后选择最小匹配误差对应的矢量就是最佳位移估计值，这就是全搜索策略（ExhaustiveSearch(ES)）。这种策略的最大优点是可以找到全局最优值，但十分浪费时间，因此，人们提出了各种各样的快速搜索策略。尽管快速搜索策略得到的可能是局部最优值，但由于其快速计算的实用性，在实际中得到了广泛的应用。目前，较为常用的快速搜索策略有：三步搜索法（ThreeStepSearch(TSS)）,新三步搜索法（NewThreeStepSearch(NTSS)）,四步搜索法（FourStepSearch(4SS)）,菱形搜索法（DiamondSearch(DS)）和自适应十字模板搜索法（AdaptiveRoodPatternSearch(ARPS)）等。第三十八页，共62页。背景运动补偿技术－搜索策略

三步搜索法（TSS）是最早的一种快速搜索算法。该算法思路简单，是很流行的搜索策略，特别适合低码率视频应用，如视频会议和视频电话。三步搜索法的思路是：首先搜索步长等于或略大于最大搜索范围的一半。每一步比较9个搜索点：方型的中心点和8个位于搜索区域边界的点。此后，搜索步长每步减半，直至步长为1时结束搜索。每步的中心移到当前步的最好的匹配点。第三十九页，共62页。背景运动补偿技术－搜索策略

新三步搜索法（NTSS）是对三步搜索法的改进，在MPEG1、H.261等标准中被广泛采用。人们发现，真实的视频序列中，运动向量一般是中心偏置的。为了开发这种特性，NTSS修改了TSS第一步的检查点模式，搜索额外的8个点，即中心点的八个邻域点。同时使用了半路停止技术（halfway-stop）加速静止块的搜索。该方法保持了TSS算法的简单、规整性，运动补偿误差和鲁棒性比TSS更好。第四十页，共62页。背景运动补偿技术－搜索策略

另一种使用中心偏置的搜索模式的搜索策略是四步搜索（4SS），它在第一步搜索中采用一个较小的5x5网格，结果该方法对于搜索窗口为7的只需要4步就可到达边界检查点。搜索过程基本上和TSS相同。4SS相比NTSS需要更少的搜索点。第四十一页，共62页。背景运动补偿技术－搜索策略

在视频图像压缩协议(如MPEG,H.261,H.263)中,菱形搜索策略（DS）因可以提高编解码效率而被广泛应用。其实DS与4SS的搜索思路很相似，DS主要的特点是采用了菱型搜索模板（一个大菱形搜索模版（LDSP）和一个小菱形搜索模版（SDSP））。相比较其他运动估计方法,它具有平均搜索点少的优势,这是因为搜索最佳运动向量时,在3x3钻石形状的区域内搜索点比3x3正方形状的区域内搜索点要少一半。在DS中,先反复使用LDSP进行搜索,直到本次搜索误差最小的那个点出现在模板的中心,接着再以这个最小误差点为中心,以SDSP为新的搜索模板进行搜索,最后将这一搜索中误差最小的那个点作为最佳匹配点。第四十二页，共62页。背景运动补偿技术－搜索策略前面提到的一系列搜索策略都是针对各个特征块进行各自独立的匹配搜索，即不同块之间的搜索过程是相互独立的。而实际中，当前块与其相邻块的运动矢量有很强的相关性，利用这一特点，介绍一种基于运动矢量预测的搜索策略，即自适应十字模板搜索（AdaptiveRoodPatternSearch,ARPS）。自适应十字模板搜索(ARPS)包括两个步骤：初步搜索和精确局部搜索。对于每一个特征块，初步搜索仅执行一次，为以后的精确搜索找到一个好的起始点。通过这个步骤，不必要的中间搜索和陷入局部最小点的情况将减少。在初始搜索步骤中，使用了自适应十字模板(ARP)，ARP的大小由每个特征块自动决定。在精确局部搜索阶段，则使用一个固定大小的十字模板，直到搜索到最后的运动矢量（MV）。YaoNIE,Kai-KuangMA,“AdaptiveRoodPatternSearchforFastBlock-matchingMotionEstimation”IEEEtransactionsonimageprocessing11:1212,1442-1449,InstituteofElectricalandElectronicsEngineers,2002第四十三页，共62页。背景运动补偿技术－搜索策略自适应搜索模式用于初始搜索。十字模型的形状是对称的，4个搜索点分别位于4个顶点上，ARP的主要结构是一个十字形状，它的尺寸指的是从一个顶点到中心点之间的距离。十字形状的选择是基于对实际视频序列的运动特征的观察。MV在水平和垂直方向上的分布比在其他方向上的分布概率要高，这是因为相机的运动大部分是在这些方向上。而且，任何一个MV都可以分解为水平分量和垂直分量，对于一个有任意方向MV的运动对象，十字形状模式至少可以检测到运动对象的主要趋向，这就是初始搜索步骤想要达到的目的。另外，除了这4个顶点外，在ARP中还加入了预测MV，因为它极可能与目标MV相似。这样，在初始步骤中检测到准确的运动的概率将增加。当预测MV在水平或者垂直方向上时，可能与4个指向顶点的MV中的一个相重叠。在决定ARP的尺寸时，初始想法是让它等于预测MV的长度，也就是下式：这里Γ是ARP的大小，Round是舍入取整。MVpredict(x)和MVpredict(y)分别是预测MV的水平和垂直分量。第四十四页，共62页。背景运动补偿技术－搜索策略为了简化处理，我们使用下式来决定ARP的大小：

总之，自适应模式包括一个十字模式，并且计入了预测MV代表的那个点，所以，在初始搜索阶段，如果预测MV不为零，那么有5个或者4个(有重叠)搜索点需要检测，如果MV为零，那么仅有一个点需要检测。经过初步搜索以后，新的搜索中心位于整体最小BDM最可能存在的区域，减少了中间不必要的搜索路径。而且，错误曲面单峰的假设在这个区域将保持有效。所以，可以使用一个固定、简单且尺寸小的搜索模式来完成局部精确搜索。考虑使用两种最简单的模式，一个是单位五点十字模式，这与DS中使用的SDSP一样；另一个是3X3正方形模式。后一种模式需要的检测点要多，所以一般选用前一种模式。

第四十五页，共62页。背景运动补偿技术－全局运动参数的鲁棒估计

在特征点匹配的基础之上，可以利用特征点之间一一对应的位置关系来估计全局运动参数，即仿射变换模型参数。设时刻tk的某一特征点坐标为(X,Y)，其在时刻tk+1的坐标为(X’,Y’)。如果以二维仿射变换描述特征点的运动，两个特征点间的关系可以表示为：二维仿射变换有六个参数，需要三个不共线的特征点及其匹配点才能求得唯一解。仅仅由三对特征点估算全局的二维仿射变换参数并不合理，因为如果一个特征点的位置有较大的误差，或者错误的匹配都会给最终的计算结果带来很大的偏差。为此可以采用最小二乘法，用所有已知的特征点来求解变换参数。第四十六页，共62页。背景运动补偿技术－全局运动参数的鲁棒估计最小二乘估计算法存在一个内在的缺陷，即无法分辨和排除错误的特征点匹配。特征点的匹配是特征点跟踪的瓶颈问题，现有方法的匹配结果通常会带有一些错误的匹配，前文所使用的方法也不例外。如果将这些错误的对应特征点代入最小二乘估计中，势必造成很大的偏差。鲁棒参数估计(robustestimation)研究在观测值出现粗差(grosserror，即错误和异常)的情况下，如何求得最优的参数估计。鲁棒估计既可以克服野点数据的影响，又具备一般估计方法的统计特性，是更广义的最优估计。在图像处理和机器视觉领域，M估计(M-estimator)和最小平方中值(LeastMedianofSquares——LMS)都是常用的鲁棒估计方法。C.V.Stewart,“RobustParameterEstimationinComputerVision”SIAMRev.,vol.41,no.3,pp.513-537,1999第四十七页，共62页。背景运动补偿技术－M估计M估计是一种广义的最大似然估计方法。参数a的M估计定义为：、是一个鲁棒损失函数（robustlossfunction），且是一个关于|u|的单调非减函数，常用的函数有Tukey,Cauchy,Huber函数等。ri,a是第i个数据相对于估计值a的偏差。本文在对应特征点仿射变换参数的估算中，将其定义为特征点经参数变换后的值与匹配点的距离，σi为ri,a的标准方差。对上式求解可得：第四十八页，共62页。背景运动补偿技术－M估计若引入权重函数：

，则有：其实该式表示的就是迭代加权最小二乘法(IterativeRe-weightedLeastSquares,IRLS)该方法在每一步迭代中，根据相对于当前估计值a的偏差和方差，求每个数据的权重，进而在下一步迭代中，利用刚刚求得的权重值，使用加权最小二乘法(WeightedLeastSquares)得到一个新的估计值a，以及每个数据的偏差和方差。照此循环，若干次迭代后IRLS收敛到最终的估计值a。a的初始值通常由最小二乘法估算。第四十九页，共62页。LSM-estimator(IRLS)M-estimator(Cauchy)M-estimator(Huber)第五十页，共62页。背景运动补偿技术－最小平方中值（LMS）

最小平方中值法计算所有数据点相对于估计值a的偏差的平方，将它们排序，取中值。最小中值对应的估计值a可以作为最终估计，可以记为：理论上LMS的野点所占比例最多可以达到50%，即对于野点数量不超过一半的数据点集，LMS都可以求得鲁棒的结果。上式是不可微的，通常使用随机采样的方法求解。从全部N个数据中随机选取S个子集，每个子集有k个数据，k通常是估计a所需的最少数据个数。每个子集都可以求出一个估计值和偏差的平方，最后从中选择一个最优估计。这里要求子集的数量S必须足够大，以使得能够至少得到一个子集S的每一数据都不是野点，即至少有一个子集的所有数据都是可用的，才可以得到一个准确的估计值。假设数据集中内点（即可靠点）的概率是p，则抽取到一个没有野点的子集的概率是pk，S个子集，至少有一个子集的数据都是内点的概率为：第五十一页，共62页。背景运动补偿技术－最小平方中值（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，还可以得到多个估计值。第五十二页，共62页。背景运动补偿技术－RANSAC算法

RANSAC算法即随机样本一致算法(RandomSampleConsensusalgorithm)，也可以处理含有很大比例野点的情形。与LMS类似，RANSAC也是通过随机选取一定量的样本，分别估计a，再从中选取一个最优的作为最终的估计值。不同的是评价估计值a的方法。RANSAC用内点个数来量化a的质量。为了清楚解释RANSAC算法的过程，考虑一个经典的数值分析的例子：寻找一条直线，使得它可以拟合一个2维的点集。这可以进一步叙述成：寻找一个1维仿射变换y=ax+b，拟合一组2维平面中的点。这实际上有两个问题：1.一条拟合数据的直线；2.对有效点和无效点的分类。可以解决这个问题的鲁棒的算法有很多，但是它们各自有不同的适应情况，使用哪一种依赖于无效点的比例。比如，如果知道只有一个无效点，那么可以通过轮流删除一个点并对剩余的点进行最优直线估计。如果无效点的比例很大，这样的方法就不适用了，这时候我们需要一个在无效点比例较大的情况下仍然有效的估计算法，这就是RANSAC算法。M.A.Fischler,R.C.Bolles,“RandomSampleConsensus:AParadigmforModelFittingwithApplicationstoImageAnalysisandAutomatedCartography”Comm.oftheACM,Vol24,pp381-395,1981第五十三页，共62页。Task:EstimatebestlineRANSAC算法的思想简单而巧妙：首先随机地选择两个点，这两个点确定了一条直线。我们称直线的支撑为在这条直线的一定距离范围内的点的数目。这样的随机选择重复数次，然后具有最大支撑的直线被确认为是点集的拟合。在拟合的误差距离范围内的点被认为是有效点，它们构成所谓的一