运动场景中目标检测与跟踪技术研究ppt课件

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算法的思想简单而巧妙：首先随机地选择两个点，这两个点确定了一条直线。我们称直线的支撑为在这条直线的一定间隔范围内的点的数目。这样的随机选择反复数次，然后具有最大支撑的直线被确以为是点集的拟合。在拟合的误差间隔范围内的点被以为是有效点，它们构成所谓的一致集，反之