软件工程毕业设计（论文）-运动相机下的移动物体分割算法研究 53页

毕业设计（论文）说明书学院软件学院专业软件工程年级2007姓名指导教师2011年6月22日\n毕业设计（论文）任务书题目：运动相机下的移动物体分割算法研究学生姓名学院名称软件学院专业软件工程学号指导教师职称讲师\n一、原始依据（包括设计或论文的工作基础、研究条件、应用环境、工作目的等。）视频中的移动目标提取与分割是视频监控以及物体跟踪等应用中用途十分广泛的一项技术。在摄像机固定的情况下，已知背景信息，当图像变化的时候，帧间差就是变化的部分。然而，随着移动拍摄设备的应用和普及，越来越多的视频已经打破之前相机位置固定的假设，因此没有办法通过简单的帧间差来得到视频变化的部分。国内外很多大学和研究机构在这一难题上做出了不少探索和贡献。卡耐基梅隆大学的舍赫教授提出运用视频追踪点轨迹矩阵的秩约束来对运动中摄像机视频的前、背景模型进行稀疏建模，再通过该稀疏模型对整帧图像利用图分割算法和马尔科夫链进行0-1标记来获得移动物体的分割的算法。这个算法很好的解决了运动中摄像机视频中的移动目标提取的问题，而且避免了使用耗费时间和资源的三维建模。本次设计基于舍赫教授的论文，对该算法进行实现和研究，从而能够对移动摄像机视频下的目标提取算法和技术进行应用和开发，为相关需要视频监控的行业和领域提供必要的理论依据和技术支持。二、参考文献[1]Y.Sheikh,O.JavedandT.Kanade.Backgroundsubtractionforfreelymovingcameras[A].In:ProceedingsofIEEE12thInternationalConferenceonComputerVision[C].IEEE:2010.1219-1225.[2]P.SandandS.Teller.ParticleVideo:Long-rangemotionestimationusingpointtrajectories[J].InternationalJournalofComputerVision,2008,80(1):72-91.[3]G.BradskiandA.Kaehler.LearningOpenCV:ComputerVisionwiththeOpenCVlibrary[M].O’ReillyMedia,2008.[4]W.Zhang,X.Cao,Y.Houetal.Detectingandextractingthephotocompositesusingplanarhomographyandgraphcut[J].IEEETransactionsonInformationForensicsandSecurity,2010,5(3):544-555.[5]C.Zhang,X.GuoandX.Cao.DuplicationLocalizationandSegmentation[A].In:ProceedingsofPacific-RimConferenceonMultimedia[C].Springer:2010.578-589.[6]M.Cho,Y.Shin,andK.Lee.Unsuperviseddetectionandsegmentationofidenticalobjects[A].In:ProceedingsofIEEEConferenceonComputerVision\nandPatternRecognition[C].IEEE:2010.1617–1624.[7]D.Lowe.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,2004,60(2):91–110.[8]C.H.Lampert,M.B.Blaschko,andT.Hofmann.Beyondslidingwindows:Objectlocalizationbyefficientsubwindowsearch[A].In:ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition[C].IEEE:2008.1–8.[9]R.HartleyandA.Zisserman.Multipleviewgeometryincomputervision[M].CambridgeUniv.Press,2004.[10]C.Wren,A.Azarbayejani,T.Darrelletal.Realtimetrackingofthehumanbody[J].IEEETPAMI,1997.[11]D.HochbaumandV.Singh.Anefficientalgorithmforcosegmentation[A].In:ProceedingsofIEEEInternationalConferenceonComputerVision[C].IEEE:2009.269–276.[12]W.HardleandL.Simar.Appliedmultivariatestatisticalanalysis[M].SpringerVerlag,2007.[13]C.Bishop.Patternrecognitionandmachinelearning[M].Springer,2006(4).[14]A.Elgammal,R.Duraiswami,D.Harwoodetal.Backgroundandforegroundmodelingusingnonparametrickerneldensityestimationforvisualsurveillance[A].In:ProceedingsoftheIEEE[C].IEEE,2002.[15]N.FriedmanandS.Russell.Imagesegmentationinvideosequences:Aprobabilisticapproach[A].In:ProceedingsofConf.UncertaintyinArtificialIntelligence[C].2000.[16]I.Haritaogolu,D.Harwood,andL.Davis.W4:Real-timesurveillanceofpeopleandtheiractivities[J].IEEETPAMI.2000.[17]R.JainandH.Nagel.Ontheanalysisofaccumulativedifferencepicturesfromimagesequencesofrealworldscenes[J].IEEETPAMI.1979.[18]O.Javed,K.Shafique,andM.Shah.Ahierarchicalapproachtorobustbackgroundsubtractionusingcolorandgradientinformation[A].In:ProceedingsofIEEEWorkshoponMotionandVideoComputing[C].IEEE:2002.[19]Y.SheikhandM.Shah.Bayesianobjectdetectionindynamicscenes[J].IEEETPAMI,2005.[20]C.StaufferandE.Grimson.Learningpatternsofactivityusingrealtimetracking[J].IEEETPAMI.2001.\n三、设计（研究）内容和要求（包括设计或研究内容、主要指标与技术参数，并根据课题性质对学生提出具体要求。）本次毕业设计着重于视频的数据提取和分割算法的实现。视频数据提取方面，参考桑德教授的微粒视频一文，运用光流和特征追踪相结合的方法在给定视频中提取追踪点轨迹，再根据舍赫教授的论文讲述的算法，通过运用RANSAC算法对追踪点轨迹进行秩约束，实现稀疏模型的建立。通过稀疏模型，运用马尔科夫链和图分割算法对视频帧进行0-1标记，最后得到目标提取和分割结果。数据提取方面，要注意阅读桑德教授主页关于微粒视频的说明和数据说明。下载代码并阅读理解，认清其实现原理。另外，桑德教授的主页上有充足的测试视频和源数据，可以用来做测试和实验。算法实现方面，需要了解和实现RANSAC、马尔科夫链和图分割算法。数学方面，要求阅读和理解仿射变换矩阵的秩约束原理和贝叶斯概率公式。衡量实验效果的主要指标是分割结果的准确率和查全率，如果运用桑德教授的数据的话，可以直接使用对应视频的基准值。指导教师（签字）年月日审题小组组长（签字）年月日\n天津大学本科生毕业设计（论文）开题报告课题名称运动相机下的移动物体分割算法研究学院名称软件学院专业名称软件工程学生姓名指导教师（内容包括：课题的来源及意义，国内外发展状况，本课题的研究目标、研究内容、研究方法、研究手段和进度安排，实验方案的可行性分析和已具备的实验条件以及主要参考文献等。）1.课题来源及意义随着摄像技术的应用和普及，越来越多的摄像装置被应用到日常生活和生产当中。其中视频监控和物体识别和追踪是最为热门的一个领域。但是，随着应用的推广和普及，视频数据量的不断扩大，单纯的视频采集系统已经不能满足日益增长的视频监控需求。对于视频的理解和分析等智能功能则占据了更为重要的需求地位。由于数据规模的庞大和人力资源的昂贵，计算机视觉算法和技术应运而生。模式识别与机器学习知识被广泛的应用于视频监控和物体识别和追踪的领域。在摄像装置拍摄的视频中，固定相机位置作为长久以来的假设和技术瓶颈正在被打破，由于背景的移动，前景移动物体的提取和分割已经不能运用于非位置固定的相机的算法。所以，本设计希望能够实现移动摄像装置视频中提取移动物体的算法并且研究之。2国内外发展状况无论在国内还是国外，运动中相机的移动目标检测都是一个技术难题。一般相机位置固定的情况下，背景相减的算法，即帧间差，能够很好的提取运动目标。早在70年代，背景相减和运动分割算法就被提了出来，基于的假设是相机静止。当相机位置静止这个假设被打破之后，比如手持摄像机或者搭载在交通工具上的摄像机，由于背景相对于画面也在运动，所以单纯运用帧间差不能提取运动的目标。该项技术如果能够得到实现和普及，那么它将大大推动视频监控的应用范围，比如智能汽车上的路况判断和标志牌识别。我国在视频监控已经颇为成熟并且应用广泛，智能车的发展和应用也是未来的热门研究方向之一，比如每年的本田智能车大赛，都吸引了很多高校的参与和竞争，创意和新技术也层出不穷。这都为移动相机的视频监控提供了很好的研究前景和应用方向。\n3研究目标本设计旨在实现舍赫教授于2010年发表的“自由移动相机中的背景减算法”一文中的运动目标提取算法。通过实现这个算法，掌握其中的技术要领，发现其中的潜在问题，从而为以后的研究找到目标和技术方向。4研究内容首先，本设计着手于研究微粒视频算法。该算法是通过合成光流和特征点跟踪来得到追踪点轨迹的。因为光流是较密集但是没有长期信息，特征点追踪则是较长期但是很稀疏。通过合成这两个技术，微粒视频将会得到一个折衷的方案，即较为密集同时比较长期的追踪点轨迹。其次，对于微粒视频算法所得到的数据进行分析，判断如何处理这些轨迹点才能为以后的算法所用。再次，对于计算机视觉当中的仿射、透视几何变换进行学习和研究，明白该算法所基于的秩约束的原理。接下来，研究0-1标记使用的算法，弄清其原理并且能够清楚明白马尔科夫链和图分割算法在该体系框架内实现的技术细节。最后，探索该方法的局限性，探讨改进算法的可能性。试图为解决该方法的局限性打下基础。5研究方法一，进行移动中相机的视频采集；二，对视频进行微粒视频算法处理生成追踪点轨迹；三，对追踪点轨迹进行分析和筛选，得到可供算法使用的追踪点轨迹矩阵；四，使用RANSAC算法，估计符合仿射矩阵秩约束的最大子矩阵，通过子矩阵建立背景的稀疏模型，剩余的点用来建立前景的稀疏模型；五，计算0-1标记的后验概率，其中，似然函数由标记像素和前、背景稀疏模型的相似度进行确定，并用图分割算法进行解空间的探索；利用马尔科夫链算法计算标记向量的先验概率。从而得出最优标记向量。实验评价部分，通过对查全率和查准率的计算，得到实验的效果。再此基础上与其他方法比较衡量，分析该算法的不足和缺陷，同时对不同参数下的算法效果进行统计和分析。6研究手段对于微粒视频的算法，使用C++和OpenCV库函数实现。对于运动物体的检测，也用C++和OpenCV进行实现。在实验数据处理方面，利用Matlab进行分析和处理。7进度安排2010.11学习光流、特征点追踪、仿射变换、贝叶斯理论、马尔科夫链和图分割。2010.12学习使用OpenCV。2011.01阅读文献，确定技术方案。2011.02下载实验数据和相关算法的实现代码，弄清技术细节。\n2011.03编程实现算法。2011.04编程实现算法并进行实验。2011.05对实验结果进行分析，运用评价体系衡量实验结果。2011.06撰写毕业设计报告，通过答辩。8实验可行性分析和已具备的实验条件微粒视频的实现可以从作者的主页上找到。同时，测试用例也可以找到。对于跟踪点的处理，可以通过简单的筛选处理来实现，较为简单。RANSAC算法较为成熟，运用秩约束的估计可以通过计算放射变换的误差来实现。这个部分虽然没有现成的代码，但是通过伪代码来写实现并不难。至于标记时采用的一系列算法，都是较为经典和成熟的，实现起来虽然不简单但是是可行的。总而言之，该实验方案是可行的。9主要参考文献[1]Y.Sheikh,O.JavedandT.Kanade.Backgroundsubtractionforfreelymovingcameras[A].In:ProceedingsofIEEE12thInternationalConferenceonComputerVision[C].IEEE:2010.1219-1225.[2]P.SandandS.Teller.ParticleVideo:Long-rangemotionestimationusingpointtrajectories[J].InternationalJournalofComputerVision,2008,80(1):72-91.[3]G.BradskiandA.Kaehler.LearningOpenCV:ComputerVisionwiththeOpenCVlibrary[M].O’ReillyMedia,2008.[4]W.Zhang,X.Cao,Y.Houetal.Detectingandextractingthephotocompositesusingplanarhomographyandgraphcut[J].IEEETransactionsonInformationForensicsandSecurity,2010,5(3):544-555.[5]C.Zhang,X.GuoandX.Cao.DuplicationLocalizationandSegmentation[A].In:ProceedingsofPacific-RimConferenceonMultimedia[C].Springer:2010.578-589.选题是否合适：是□否□课题能否实现：能□不能□指导教师（签字）年月日选题是否合适：是□否□课题能否实现：能□不能□审题小组组长（签字）年月日\n摘要移动相机下的移动目标提取已经成为计算机视觉领域中十分热门的一个话题，同时，也有很多的人力物力被投入到这个议题的研究实现以及改进当中来。传统上，背景减算法是被用来做目标提取的最流行的算法，因为传统上的监视系统中的相机摄像装置都是被固定安装的，这样的话，背景就是不变的而前景物体通常是动着的。然而，随着移动电话、手持摄像装置的不断普及和发展，越来越多的视频序列是被移动着的相机所拍摄的，在这些视频当中，已有的算法显然已经不适用了。自然而然的，对那些在移动视频中提取前景目标的算法的市场需求就显得十分迫切。本毕业设计提供了卡内基梅隆大学的舍赫教授在2009年提出的移动相机下的背景减算法的一种实现。基本上本论文的实现是基于该篇论文的，但是本毕业设计在此基础上也加入了一些别的算法和策略，并做了一些修改。实验结果证明本毕业设计的方法是行得通的。首先，SIFT特征点被从每一帧中提取出来，并且基于此，两个匹配矩阵被建立出来，而后初始的轨迹序列被通过合并这两个匹配矩阵建立出来。接下来，马萨诸塞理工学院的桑德博士提出的微粒视频技术也被加入进来用来提高轨迹的密度。接下来就是通过随即一致性算法和神经网络技术分别建立系数模型和二值标记。另外的，框级定位结果被通过稀疏模型建立出来。关键词：目标提取；计算机视觉；背景减算法；移动相机\nABSTRACTObjectdetectionandsegmentationhaslongbeenahottopicintheareaofComputerVision.Therehasbeenalargeamountofeffortundertookinthisproblem.Traditionally,backgroundsubtractionwasthemostpopularmethodtodothisjob,basicallybecauseintraditionalsupervisesystem,thecameraswerealwaysstatic;thus,therewasanassumptionintraditionalalgorithmsinsuchobjectdetectionproblem:thebackgroundisatstaticandtheforegroundismoving.However,asthedevelopingofmobilephonesaswellasdigitalvideocapturedevices,there’sagrowingnumberofvideosequencesaretakenbysuchmobiledevices,whicholdalgorithmscannothandlewith.Consequently,themarketneedofalgorithmstosolvetheobjectdetectionproblemisalsogrowingatanamazingspeedduetoexistedalgorithmcannothandlethoseproblemsinmovingcameras.Weproposeanimplementationofanovelalgorithmaboutbackgroundsubtractionandobjectdetectioninmovingcamerasettings.Basically,ourmethodisaccordingtoapreviousworkofProf.SheikhfromCarnegieMellonUniversity.Also,wedosomemodificationandaddsomenewprocessinthisframework.Theexperimentalresultsshowthatourmethodworkswell.Firstly,outmethoduseSIFTtoextractfeaturepointsfromeachframeofgivenvideosequenceandmatchthemframe-by-frame.Secondly,thetwomatchmatricesarecombinedtogethertoformainitialtrajectorymatrix.ParticleVideotechnique,proposedbyDr.SandfromMassachusettsInstituteofTechnology,isalsoincludedtoobtainmoredensetrajectories.ThensparselabelingoftrajectoriesisaccomplishedbyRandomSampleConsensusanddenselabelingisaccomplishedbyArtificialNeuralNetwork.Abox-levelboundingresultisalsoobtainedbyEfficientSub-windowSearchaccordingtothesparsemodel.Keywords:objectdetection;computervision;backgroundsubtraction;mobilecamera.\n目录第一章绪论131.1选题背景131.2当前技术现状14第二章背景技术162.1特征点以及SIFT提取和匹配162.2多视角几何背景17第三章程序实现193.1问题的提出及其现实意义193.2算法流程203.3特征点的提取223.4特征点的匹配233.5轨迹的提取253.6轨迹矩阵的多视角设定以及秩约束273.7利用RANSAC建立稀疏模型273.8运用ESS实现框定位313.9二值标记算法的实现34第四章实验结果及讨论364.1数据集来源和描述364.2实验结果以及讨论374.2.1从算法的各个步骤分析38\n4.2.2从不同数据集的角度分析40第五章总结和展望425.1算法实现的总结425.1.1特征点的提取和轨迹矩阵的建立425.1.2稀疏模型的实现425.1.3框定位算法的实现435.1.4像素级标定的实现435.2过程中遇到的问题以及解决43参考文献45外文资料47中文译文48致谢53\n第一章绪论1.1选题背景计算机视觉，作为近20年从出生到发展的一门新兴学科，在包括从军用到民用的诸多领域都有着卓越的贡献和长足的发展潜力。它是一门研究如何使机器“看”的科学，更进一步的说，就是指用摄影机和电脑代替人眼对目标进行识别、跟踪和测量等机器视觉，并进一步做图像处理，用电脑处理成为更适合人眼观察或传送给仪器检测的图像。考虑到人类已经进入信息时代，计算机将越来越广泛地进入几乎所有领域。一方面是更多未经计算机专业训练的人也需要应用计算机，而另一方面是计算机的功能越来越强，使用方法越来越复杂。从另一个方面讲，它同样可以被看作是生物视觉的一个补充。在生物视觉领域中，人类和各种动物的视觉都得到了研究，从而建立了这些视觉系统感知信息过程中所使用的物理模型。另一方面，在计算机视觉中，靠软件和硬件实现的人工智能系统得到了研究与描述。生物视觉与计算机视觉进行的学科间交流为彼此都带来了巨大价值。智能计算机的其中一项要求，就是能够使得计算机能够像人类一样，理解周围的信息，包括视觉信息，声音信息，还有温度信息等。计算机视觉，脱胎于传统图像处理，更着重于解决计算机如何学习人类的思考和理解模式，将视觉信息（瞬间的视觉图像，也可以是一系列的图像序列）转化为有意义的，较为简化的数字信息。因为能够将人从繁重并且重复的工作中解脱出来而去从事更有创造性的工作，计算机视觉于是有着它广阔的应用前景。视频监控和追踪从计算机视觉的应用诞生的年代起，就一直是热门的应用领域。随着城市以及各种场所对安全等要求的逐渐提高，越来越多的人力和物力被投入到视频监控项目的开发和运作当中。视频监控是安全防范系统的重要组成部分，它是一种防范能力较强的综合系统。视频监控以其直观、准确、及时和信息内容丰富而广泛应用于许多场合。近年来，随着计算机、网络以及图像处理、传输技术的飞速发展，视频监控技术也有了长足的发展。我国的“天网”计划就是一个明证。视频监控系统的发展大致经历了三个阶段。在90年代初以前，主要是以模拟设备为主的闭路电视监控系统，称为第一代模拟监控系统。90年代中期，随着计算机处理能力的提高和视频技术的发展，人们利用计算机的高速数据处理能力进行视频的采集和处理，利用显示器的高分辨率实现图像的多画面显示，从而大大提高了图像质量，这种基于PC机的多媒体主控台系统称为第二代数字化本地视频监控系统。九十年代末，随着网络带宽、计算机处理能力和存储容量的快速提高，以及各种实用视频处理技术的出现，视频监控步入了全数字化的网络时代，称为第三代远程视频监控系统。第三代视频监控系统以网络为依托，以数字视频的压缩、传输、存储和播放为核心，以智能实用的图像分析为特色，引发了视频监控行业的技术革命。\n然而，视频监控还是处于需要大量人力投入其中，究其原因，就是计算机对于视频的理解还不能达到人类大脑的水平，物体的辨识、提取，人物的动作识别等等问题，在当今的计算机视觉领域仍然是个热点。随着计算机视觉算法的不断完善，视频监控所需要的人力将会大大减少，从而显著地降低成本，这也是民用计算机视觉的市场价值所在。在视频监控应用当中，如何提取目标物体是很重要的研究方向。比如在路口的交通监控当中，如何自动地提取车辆和行人。传统上，这样的算法都借助比对相邻的两帧来实现。这样做的原因是传统上大多数摄像装置都是固定安装在一个固定的位置上的，比如路口的电线杆上，楼层的墙角落里。或者，有些可以旋转的摄像头，在短时间内可以看作是静止的。也就是说，摄像头所拍摄的场景相对于摄像头本身是不运动的。这样一个假设所带来的效果是在短时间内如果不出现我们感兴趣的物体（如运动着的车辆和行人）的话，摄像装置所拍摄的视频应该是相同的，如果相邻两帧或几帧出现了较大的不同，那么很可能的原因就是出现了运动着的物体，而这个物体很可能就是视频监控中感兴趣的前景物体。然而，随着全球技术和经济的不断发展，便捷随身的通讯设备逐渐进入了生活的主流。手机的拍摄装置和不断便捷的摄像装置的发展也是一日千里，由移动设备拍摄的视频信息的数量已经远远超过了不容忽视的程度。如何在移动设备所拍摄的视频中应用已有的各种监控算法，也成为一个必须要解决的问题。所以本论文将集中讨论如何在移动相机所拍摄的视频中进行前景物体的提取。移动相机所拍摄的视频与传统的视频最大的不同就是，在移动相机所拍摄的视频当中，由于相机本身是运动的，那么背景相对于相机也是运动的。这样一来，通过比对相邻两帧的差别来辨别前景物体的方法将不再适用。本论文的目的就是探讨一种能够在前景和背景都在变化的情况下能将两者较为完美的区分并且分割出来的算法并且予以实现。本文的工作将为以后后续的有关移动相机视频处理的应用和讨论提供支持和话题。1.2当前技术现状移动视频当中的目标提取在目前的应用当中，很大一部分是依靠传感器的精确性来实现的。光电传感器通过被安装在多种移动平台上用于执行安全及监察任务。如安装用于执行警务的巡逻直升机上，监视边界及更为普遍的探测可能的动态场景变化。在不同的监察和监视任务中使用无人驾驶和其他机上平台，成像传感器同样被应用于多种地面运动车辆上。但是无论怎样，即使是固定平台也总不是防震的(如支架摇摆等)。在这些情况下，保证足够的精度及可靠性来探测场景的动态对人工的操作员们是一项巨大的挑战。运动目标很快被漏掉，且已探测到的目标很容易丢失。更具挑战性的由传感器运动、运动的传感器平台以及光学参数变化导致的动态性问题也需待解决。因此，很有必要为操作人员提供必需的功能性支持。现有系统的能力到目前为止都具有相当的局限性，其需要关于飞行及记录参数的高精度数据，待观测的背景信息等，否则就只能对相对运动做出粗略的评估。、与硬件方法不同，视觉的算法虽然精度有所下降，但是更具有鲁棒性。移动相机的目标提取在近几年在计算机视觉里面一直是一个热门题目。\n最初，为了解除相机移动所带来的误差，一些方法采取了自运动估计补偿的策略，企图通过计算相机自身在三维世界中的运动方向、速度来还原图像，通过给图像中的像素一个补偿的运动向量来完成。这样做的好处是通过建模相机所处场景的三维模型并且估计相机自身的运动方向和速度，能够完美地还原相机场景当中的具体位置。这样做的缺点就是对整个附近场景建模所需要的数据量比较巨大，不利于实时实现。更严重的是，由于这些方法本身数学模型是建立在放射几何投影的条件下的，所以它要求的极为苛刻。这个方法假设是背景的运动必须能够被归纳到一个平面当中，或者围绕固定轴旋转。这样的话，最普遍意义下的手持摄像装置的运动方式将毫无疑问地被排除在外。这是自运动估计方法的最大的不足。除此之外，还有一些别的技术和方法也被运用到了这个问题当中来，比如将整个场景分成多个片，每一个片用一个近似的小平面来估计，然后再估计每一个小平面的运动状态，再通过还原每一个小平面的运动来还原整个场景。以上的各种方法，基于的都是相机稳定和自运动估计的技术，对于过于随意且无法平面近似的运动都无能为力。这也是之后的各种方法所着重要解决的问题。本论文所实现的算法，不存在任何的类似于上述的假设，纯粹是根据图像中的跟踪点轨迹，通过仿射矩阵的秩约束来对图像的像素进行粗分类，然后才是像素级别的细分类，这个方法将完全使用于手持移动摄像装置的应用范畴。如果追踪点足够多而且足够准确的话，本论文实现的方法的效果将会是极为精确的。\n第二章背景技术2.1特征点以及SIFT提取和匹配图2-1SIFT特征点提取的步骤SIFT(ScaleInvariantFeatureTransform)算法[7]是一种提取图像局部特征、用于表达整幅图像的方法,其目的是在尺度空间寻找极值点,提取特征点位置、尺度及旋转不变量.（2）该算法的实现包括两个阶段,第一阶段是SIFT特征的生成,第二阶段是构造特征描述符,以实现不同图像的特征点匹配.（3）采用SIFT算法,可以更加准确地提取出图像的特征,利用先验条件和RANSAC算法,能进一步去除误匹配,使得所提取的特征点得到了更好地匹配。SIFT方法包括基于高斯差分尺度空间的特征点检测和特征点的描述与匹配。特征点检测分为三步：（1）建立高斯差分尺度空间（2）极值点检测（3）边缘像素剔除。SIFT算法的主要步骤如下：1）DOG尺度空间的构建：为了有效地在尺度空间检测到稳定的关键点，Lowe提出了高斯差分尺度空间(DOGscalespace)，利用不同尺度的高斯差分核与图像卷积生成。DOG算子计算简单，是归一化LoG(Laplacian-of-Gaussian)算子的近似。2）尺度空间极值点检测：对于图像上的点，计算其在每一尺度下DOG算子的响应值。为了寻找尺度空间上的极值点，每个检测点要和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。3）精确确定极值点位置：通过拟和三维二次函数以精确确定关键点的位置。所用的拟合函数为DOG算子的二阶泰勒展开式。并通过检测高斯差分算子的主曲率来滤除边缘响应。4）关键点方向分配：利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。5）特征点描述符生成：实际计算过程中，为了增强匹配的稳定性，Lowe建议对每个关键点使用4×4邻域内共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的Sift特征向量。\n图2-2高斯差分金字塔示意图图2-3特征描述符示意图当两幅影像的SIFT特征向量生成以后,就要采用一种相似性准则来寻找最佳匹配的位置。SIFT算法采用欧氏距离对特征向量进行评价,当欧氏距离最近两个点的比值小于阈值时接受此匹配点。一般该点为其最近邻。2.2多视角几何背景单应性是几何[9]中的一个概念。单应性是一个从实射影平面到射影平面的可逆变换，直线在该变换下仍映射为直线。具有相同意义的词还包括直射变换、射影变换和射影性等，不过“直射变换”也在更广义的范围内使用。形式化地说，射影变换是一种在射影几何中使用的变换：它是一对透视投影的组合。它描述了当观察者视角改变时，被观察物体的感知位置会发生何种变化。射影变换并不保持大小和角度，但会保持重合关系和交比——两个在射影几何中很重要的性质。射影变换形成了一个群。对于更广义的射影空间——具有不同维度或不同的域——来说，“单应性”代表射影线性变换（由其相关的向量空间的线性变换导出的可逆变换），而“直射变换”（意为“把直线映射为直线”）更为广义，它既包含了单应性，也包含了自同构直射变换（由域自同构导出的直射变换），或者是这两者的组合。\n图2-4相机在观察某一平面的示意图齐次坐标以矩阵乘的方式来表示射影变换，因为使用笛卡儿坐标的话，矩阵乘无法执行透视射影所必需的除法运算。换句话说，透视射影在笛卡儿坐标下不是线性变换。如图2-5所示：图3-5Hab就是齐次坐标形式下的单应性矩阵\n第三章程序实现3.1问题的提出及其现实意义本文着重于实现一套算法，能够将手持摄像机所拍摄的视频中的移动物体在像素级别提取出来。具体效果如图2-1所示。图3-1前景目标提取效果示意图一般而言，在相机固定的视频中，背景在前后两帧中是没有差别的。如果帧间差出现非零区域（如图3-2的白色部分），那么移动（变化）的区域最有可能出现在这里，而这些区域就是前景物体最可能存在的地方。但是在移动相机所拍摄的视频里，变化的则不一定是前景，如图3-2所示，在移动相机的帧间差图像当中，几乎所有的区域都存在非零的部分。这样一来，就为算法提取前景物体（图3-1、图3-2当中的汽车）增加了难度。本论文就是为了解决这一问题，从特征点追踪的角度出发，将视频通过稀疏建模和像素级标定来得到如图3-1中右侧的效果，提取在实际场景中运动着的物体。\n图3-2移动相机的帧间差图像该问题具有很强的应用性，传统上很多的与视频内容理解有关的计算机视觉算法都需要目标提取，目标提取是很多算法的第一步。而这些算法所运用的范围仅仅是静止地摄像机或者短时静止的摄像机。而随着手机和便携式摄像装置的惯犯普及，拍摄的视频中，背景随着相机的运动而运动的情况越来越多。我们如果要在一辆持续行驶的汽车上安装一个摄像机，并且用来追踪范围内的移动物体（比如另一辆汽车），那么已有的算法就不能适用了。所以，本方法在应用到相机位置时刻在变化的视频中是十分恰当的，能够很好的解决这种问题，使得别的一些算法也能在移动相机所拍摄的视频当中运用。3.2算法流程\n图3-3本算法的流程示意图本算法的流程如图3-3所示：1）首先，源视频的每一帧通过SIFT算法提取特征点；2）然后，相邻两帧之间运用最近邻算法求出特征点的匹配关系，这样，就得出F-1(F为帧数)个匹配数组，得到匹配矩阵M；\n3）因为相邻两帧之间可能由于种种误差而使得从第一帧开始的轨迹不完整，本方法又在帧间匹配的基础上增加了首帧和后续帧之间的依次匹配，得到匹配矩阵N；4）融合匹配矩阵M和N得到追踪特征点的轨迹序列W。5）对于W的各列（即为一个轨迹序列）使用RANSAC算法，挑选出3个基，根据基得到稀疏模型。6）对于稀疏模型运用快速子窗口搜索（EfficientSub-windowSearch,ESS）算法进行框定位，这是本算法的输出结果之一；7）对于稀疏模型进行像素级别的标定，得到像素级别的分割结果，这是本算法的输出结果之二。综上，本算法的输入是手持摄像装置拍摄的一段视频，输出是对应移动物体的的像素级别的分割和框级别的定位结果。本算法的总体思想脱胎于舍赫教授的论文[1]，但又不完全相同。3.3特征点的提取首先，本方法将在视频的每一帧中提取显著的特征点，而后借助追踪这些显著的特征点在视频中的运动轨迹达到估计相机运动的目的。如图3-5，每一帧都能够通过SIFT算法提取到一些特征点，在图中用红色的点表示。然而，特征点的追踪也有其不足之处。首先，当前帧显著的特征点，在下一帧不一定显著；其次，帧间匹配的时候会有噪音，不一定所有的点都有匹配点。这就造成由追踪特征点链接而成的轨迹比较稀疏，对本文后续的步骤有不利影响。（如图3-6左一）。图3-5视频中某一帧的SIFT特征点（红色）所以，本方法在提取SIFT特征点的基础上，借鉴了视频粒子算法[2]（如图3-6所示）。这是一种融合了特征点追踪和光流的显著点追踪算法，用来完成视频各帧之间的运动估计。\n该算法用诸多视频微粒来计算视频的运动，每一个微粒代表在视频中一个较长时期的追踪点轨迹。为了密集地表示，每一点都被和下一帧中的像素点作比较，从已知的光流和特征提取的结果中综合的找出最优的匹配点，从而优化每一个微粒。特征提取的优点是持续性较好，能够在很多帧中追踪到微粒的踪迹；它的缺点就是过于稀疏，不利于像素级的标记（这一点将在后面的章节再做比较）。而光流的特点（如图3-6的中图）是密集，缺点是持续时期较短（一般是一帧）。视频粒子结合了特征提取追踪和光流两个方法的优点，克服了两个方法的缺点，得出一系列即密集，又长期的显著点追踪微粒来，为本文后续的处理提供了便利。图3-6结合了特征点追踪和光流的视频粒子追踪3.4特征点的匹配在提取特征点完成之后，接下来的工作就是匹配。本方法采用的匹配算法是最近邻算法，即计算代表每一个特征点的向量之间的相似度，然后取向量夹角最小的那一个特征点来当作该特征点的匹配。该算法的具体实现如图3-7所示。需要指出的是，为了避免过多的噪音干扰，只有当两个向量（最近的和次近的）的夹角大于一定的度数时，最近的向量才会被选中。如图3-7，这通过计算向量夹角的余弦值来实现。\n图3-7特征点匹配的最近邻算法的实现为了进一步去除噪声，一些“长度”过长（即匹配点之间的几何距离）的匹配将被去除，这是因为在本论文的假设中，每一帧和每一帧之间对应像素的位移应该是显著但是不超过正常水平的（在实验数据中，一般不超过200pix），如果某一匹配对应的位移明显超过这一阈值，那么这个匹配将被废弃。两帧图像之间的匹配如上所述。本文为了将匹配成功的特征点链接起来形成长时间的轨迹，采取了一种合成匹配的方法，通过建立两个匹配矩阵（一个“流”状矩阵，一个“羽”状矩阵）然后合成两个矩阵提取得到轨迹（在3.5节将会提到）。\n图3-8(a)流状示意图以及匹配矩阵与(b)羽状示意图以及匹配矩阵以及如何通过两者的合成填补断裂的轨迹。其中，Fi代表第F帧，纵列的序号代表该帧的第几个特征点。在流状矩阵中，Mij代表在第i帧中的第j个特征点与第i+1帧中的哪个特征点相匹配；在羽状匹配矩阵中，Nij代表在第1帧中第j个特征点与第i帧（i>1）中的哪个特征点相匹配，0代表无匹配。“流”状矩阵就是相邻两帧之间的特征点匹配矩，如图3-8中(a)所示；“羽”状匹配矩阵就是第一帧与接下来后继帧之间的匹配矩阵，如图3-8中(b)所示。3.5轨迹的提取有了匹配好的特征点矩阵M和N，本论文将用两个匹配矩阵合成最终的轨迹矩阵W。具体的合成步骤如下：从M的第一列开始，对于该列当中的每一点，顺序地找到它的后继匹配点，并将对应的坐标（x，y）写入W的对应位置。由于可能存在如图3-8中的那种情况，M中某一帧出现断帧（特征点存在于该帧但是并未匹配上），则通过N中对应的位置找到应该匹配的特征点，从而将断链“焊接”起来。具体的例子如图3-8所示，M(4,3)出现了0，意味着在第三帧和第四帧之间，第四个特征点没有得到匹配。但是根据N（图3-8之（b）），第三帧的第四个特征点与第一帧的第四个特征点相匹配（N(4,3)=4）\n，而第一帧的第四个特征点与第四帧的第四个特征点相匹配（N(4,4)=4），那么显而易见，第三帧的第四个特征点与第四帧的第四个特征点相匹配（M(4,3)被赋值为4）。在后续的实验中，这样一个“焊接”的策略效果较为明显，如图3-9所示。图3-9“焊接”策略的效果。其中蓝色的曲线代表“焊接”前每一帧当中能与下一帧匹配的特征点的数量（即M矩阵中每一列的非零元素数目），红线代表“焊接”后的匹配特征点数量。横轴是帧序号。由图3-9可知，本文采取的策略对于提升匹配点数的效果是明显的，而提升匹配点数对于后续的处理步骤都是有用的。图3-10展示了视频中某30帧的追踪点轨迹。图3-10一则提取好的追踪点轨迹（30帧）\n3.6轨迹矩阵的多视角设定以及秩约束图3-11轨迹矩阵W的结构和设定从之前步骤得出的轨迹矩阵W可以被整理成如图3-11中所示的形式。其中,[u,v]代表一个点的[x,y]坐标，F是帧数，P是追踪的轨迹点的数目。为了实验的方便，也为了进一步避免噪音的介入，F在这里去30，也就是视频被分为30帧一个的窗口，因为这样一是可以降低计算量和存储器的使用数量，二是完整（从第一帧到最后一帧）的轨迹数量实在有限。本文中的相机投影设定遵循正交仿射投影。投影线垂直于投影面的投影属于正交投影，也称为平行投影。仿射变换，就是几何中两个向量空间之间的一个一个线性变换接上一个平移组成。它的特点是平行依旧平行。根据仿射投影的性质，轨迹矩阵W可以如图3-12，被分解为两个矩阵，一个是2F乘3，一个是3乘P，前一个是三位点结构矩阵，后一个是正交投影矩阵。根据本文的设定，追踪点或者像素在视频内运动主要有两个运动构成，一个是因为相机运动而引起的，另一个是因为物体本身运动而引起的。图3-12轨迹矩阵W的分解以上讨论的是假如所有的追踪点都只包含上述的第一种运动，那么根据本论文讨论的正交投影设定，这些追踪点所构成的轨迹矩阵将会满足如图3-12所示的分解。换言之，这样的矩阵的秩是三。以上就是矩阵轨迹的秩约束。3.7利用RANSAC建立稀疏模型\n图3-13由三个基能够展成的轨迹向量空间在以上章节探讨过了，如果所有的追踪点轨迹构成的矩阵W符合秩约束为三的限制和制约，那么这些追踪点理论上都是属于背景的，因为它们所有的运动都是一致的，是由相机运动引入的。如图3-13，(a)表示了三个基轨迹以及他们的线性组合；(b)表示了所有这些线性组合能够代表的所有轨迹；(c)展示了一些例外的轨迹，即无法用(a)中的三个基轨迹所线性表示。事实上，在本实验中，由于有移动的物体，所以不可能所有的追踪点轨迹都符合上述的约束，一些位于移动的物体上的追踪点上的轨迹由于涵盖了上述两种的运动引入方式，所以无法由三个在背景上的基轨迹来线性表示。RANSAC是“RANdomSAmpleConsensus（随机抽样一致）”的缩写。它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法——它有一定的概率得出一个合理的结果；为了提高概率必须提高迭代次数。该算法最早由Fischler和Bolles于1981年提出。RANSAC的基本假设是：（1）数据由“局内点”组成，例如：数据的分布可以用一些模型参数来解释；（2）“局外点”是不能适应该模型的数据；（3）除此之外的数据属于噪声。局外点产生的原因有：噪声的极值；错误的测量方法；对数据的错误假设。RANSAC也做了以下假设：给定一组（通常很小的）局内点，存在一个可以估计模型参数的过程；而该模型能够解释或者适用于局内点。\nRANSAC算法的输入是一组观测数据，一个可以解释或者适应于观测数据的参数化模型，一些可信的参数。RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：1.有一个模型适应于假设的局内点，即所有的未知参数都能从假设的局内点计算得出。2.用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点。3.如果有足够多的点被归类为假设的局内点，那么估计的模型就足够合理。4.然后，用所有假设的局内点去重新估计模型，因为它仅仅被初始的假设局内点估计过。5.最后，通过估计局内点与模型的错误率来评估模型。这个过程被重复执行固定的次数，每次产生的模型要么因为局内点太少而被舍弃，要么因为比现有的模型更好而被选用。于是，本文运用RANSAC算法来鲁棒地选择三个符合上述规则的轨迹基，从而将这些轨迹分为两类：一类为前景，一类为背景。RANSAC算法的实现如图3-14所示：图3-14本论文中的RANSAC算法实现具体操作上，首先随机选择三个不同的轨迹，计算由他们展成的子空间是否能够满足分类。下面的部分讲能否满足分类的判断依据。如图3-15所示，选择一些基能够使分类显著（错误函数的值两极分化明显），而另一些则不能（错误函数分布比较无规律）。\n图3-15(a)显著的RANSAC分类与(b)不显著的RANSAC分类错误函数如图3-16，P为投影矩阵，W3是由三个轨迹基组成的矩阵。如果符合W3空间的轨迹wi，P左乘以wi得到的还是wi，否则出入较大。通过这个错误函数计算法则，轨迹矩阵能够被稳定地分成两类（如图3-15(a)所示）。图3-16投影矩阵与错误函数的计算经过RANSAC算法处理后，稀疏模型被建立出来，如图3-17和图3-18所示。\n图3-17稀疏模型在某一帧的投影，其中，白点是前景，黑点是背景，红点是挑选出来的轨迹基的位置。图3-18长度为30帧的稀疏模型（参照图3-10），红色的轨迹是前景轨迹3.8运用ESS实现框定位ESS[8]是一种快速的基于滑窗搜索定位的图像定位方法。它基于的思想是分支限界。分枝界限法是由三栖学者查理德·卡普（RichardM.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”\n把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。图3-19ESS的框架和算法流程\n图3-20ESS的定位效果图3-21ESS实现的关键代码。(a)分支定界的实现代码；(b)主函数中的初始化和调用分支定界。ESS的原理如图3-19，解空间一次被分解为两部分（分支），一部分是由外界内缩而成，另一部分是由内界扩张而成。而后每一分支的最大可能分数被计算出来（限界）。然后两个分支都被送入优先队列排序。每次从优先队列中弹出最优（拥有最大分数）的状态，并且将它继续细分。直到最优的状态的外边界和内边界接触时，即最优解空间中只包含一个矩形时算法停止。在实际的实现中，因为目的是用矩形定位前景点，所以本方法将之前方法得出的稀疏模型中的前景点给予一个正分，背景点给予一个负分，然后用ESS定位，得到的结果如图3-20所示。\n在本论文中，ESS使用C++实现并在MATLAB下调用，关键代码如图3-21所示。3.9二值标记算法的实现除了框定位的结果，本算法的第二个结果是如图3-22所示的二值标记的分割结果。为了达到分割的结果，本论文采用了监督学习的方法，使用神经网络对每一个像素进行标记。图3-22二值标记的结果人工神经网络[1213]（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionistModel），它是一种模范动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的。训练用的数据是基于稀疏模型的。在稀疏模型的每一点，一个5维的向量被提取出来[x,y,v,a,b]。其中，[x,y]是稀疏模型训练点的坐标，v是该点的灰度值，a和b分别是该点周围5乘5范围内前景点的个数和背景点的个数。除了引入x,y,v等位置和表征信息之外，因为在图像上每一点周围的稀疏模型的分布密度是不同的，但是对该点的分类很有用，所以a,b被引入作为分类训练的数据。本实验实现的神经网络所做的工作实际上就是在一些给定标记的数据下做训练，然后在用所有的像素做测试，得到分类结果。相当于在五维的向量空间中的点做聚类。\n图3-23本论文中神经网络的训练过程，右图为错误函数随着迭代次数的走势\n第四章实验结果及讨论4.1数据集来源和描述在本次毕业设计论文的实验部分，使用的计算机参数如下：表4-1实验使用的计算机描述机型DellStudioE7500CPUIntel(R)Core(TM)2Duo2.93\2.94GHz内存4.00GB系统类型32位本次毕业设计的实验所用的数据集包含以下几个方面：1）30帧的测试视频片断三个，分别包括车辆（多于一个）通过交通路口，一只手在屏幕中运动，一个人通过一个公告板。2）还有通过ParticleVideo得到的追踪点数据（测试用）的纯文本文件。以上数据来自于Dr.PeterSand的主页：http://rvsn.csail.mit.edu/pv/。图4-1展示了一些来自于实验测试的视频中的图像。这些视频均来自于Dr.PeterSand的主页。这些视频都是由手持摄像机所拍摄的，他们的平均位移是150pixel，所用的解码器是hyffyuv，版本是2.1.1。本论文使用上述视频作为测试算法有效性的数据。由于输入纯粹是手持摄像机所拍摄的移动相机视频，没有任何的辅助信息（即前景的颜色值、位置等献演知识），所以本算法如果能够以该视频作为输入，输出一个视频，将原视频当中的移动物体（前景）提取出来的话，那么，本算法的可行性就被证明了。\n图4-1本实验中所使用的实验视频中的截图，从上到下依次是汽车、手和人4.2实验结果以及讨论\n图4-2实验结果的示意图，从上到下依次是车、手和行人。(a)列是稀疏模型，即追踪点经过随机一致性分类的的分类结果，黑色点是背景点，白色点是前景点。(b)列是经过神经网络计算了一步以后的结果。(c)列是最终的结果。本论文的实验部分结果的截图如图4-2所示，主要展示了本算法的二值分割效果。整体上讲，本算法达到了预期的效果和目标，即从移动相机所拍摄的视频当中分割出移动的前景物体来，从图4-2中可以看出，三辆车和一只手还有一个人都被分割了出来。下面，本论文将从两个方面对实验结果进行分析和评价。4.2.1从算法的各个步骤分析首先，本文从不同的角度出发，分析本算法在整个流程的不同步骤的表现和最后的分割结果之间的关系。1)特征点的以及追踪点轨迹的提取和建立在本论文中，特征点的提取是通过SIFT算法实现的，通过两趟的匹配以及匹配矩阵的建立和融合得到追踪点的轨迹矩阵。在实验的过程中，发现两个参数或变量容易引起结果的变好或者变坏：轨迹点的数量和轨迹点的匹配数量。无论是轨迹点本身的数量还是其匹配的数量，都会制约最终的轨迹数量。而理想的状况是轨迹点的分布均匀，数量充足。\n然而，由于SIFT特征点本身的提取特性，特征点的分布呈区域式密集，有些细节充足的部分（比如贴满论文的墙上）的特征点密度就很大，而另外一些细节比较匮乏的区域（比如天空和柏油路面），特征点就很稀疏甚至及其匮乏。然而，这个现象带来的影响却是两方面的：首先，加入无特征区域是路面、墙壁等近景的话，缺乏取样点带来的影响是负面的，这一点显而易见，因为在模型中应该被估计为背景的区域缺乏足够的“支撑”，会导致原来是背景的区域在分类中不那么容易被分到背景中。其次，像天空等区域，特征点缺乏有时候带来的影响却不那么严重，因为天空距离摄像机镜头太远了，成像也不符合本文仿射的设定。综上，这一步骤的影响是多方面的。所以，本论文在运用自己的方法（SIFT提取+匹配+焊接）的基础上，又使用了Dr.PeterSand再网站上提供的纯文本追踪点轨迹文件，用来补充本文中的轨迹矩阵，使之更丰满，分布更均匀。实验证明，这样的策略很成功，能够帮助之后的随机一致性算法的实现和后续的处理。最终轨迹的格式（未归一成矩阵）如下所示：18678121254.8.1255.8.121281.8.1282.8.121296.8.1297.8.121323.8.1324.8.221351.8.221378.8.221405.8.121425.8.1425.8.1511452.8.1452.8.…1511479.8.1479.8.…1511506.8.1506.8.…1511521.8.1521.8.……第一行的数字（18678）代表的是以下内容的行数，即追踪轨迹的个数（在本例中代表接下来的18678行，每一行代表一个追踪点的轨迹）。接下来的每一行，开始两个数字（1和2）代表该行所代表的轨迹的起始帧（1）和结束帧（2），随后的若干列数据分为若干组（2-1=1），即在每一帧中该点是否存在以及如果存在的情况下该追踪点的坐标（1254.8.代表在该帧此点存在并且坐标为x:254.y:8.）。经过读入处理后，轨迹矩阵的格式如图3-12所示。1)随机一致性算法的实现随机一致性算法（RANSAC）的实现在本算法中占据着很重要的地位。一般而言，随机一致性算法的实现包括以下三部分：a）随机挑选基点。这一步的目的是从给定的点集中，挑选出给定数量的基点来，这些基点将被通过事先给定的不变量计算方法给出一个分类方案，将剩余的点分类成符合给定不变量的和不符合给定不变量的两个部分。b）\n根据随机挑选的基点计算剩余点的估计误差。在本文中，这个估计误差就是投影误差，即对应点右乘以投影矩阵后和该点的欧式距离（如图3-16所示）。c）一致性衡量。这一点尤为重要，因为随机挑选的点可能都在背景上，也有可能不在背景上，也就是不具有展开成子空间的代表性。如图3-15，不具有代表性的随机取样点所展开的子空间同样不具有代表性，无法显著地将待分类的点分类，具体表现为入图3-15(b)所示，除了被选为基的点之外，其余点的误差都很大，而且误差之间差距不大。如果选取的基点得当的话，效果如图3-15(a)所示，其余点要么误差很小（inlier）要么误差很大（outlier），例外没有或者很少。具体实现上，本文采取选两个阈值（Tl和Th），计算投影误差在阈值Tl以下的点的个数（inlier）和在Th以上的点的个数（outlier），归一化后，实验采取的Tl值为0.1，Th为0.9，并且计算是否两者的和超过总点数的99%，否则进行下一轮的随机点选取。选取的轮数上限为1000。1)框级定位除了这部分之外的部分，本实验采取的是matlab实现，唯独ESS算法是采取的C++实现，而后编译成为可供matlab程序调用的mex32文件。其原因是ESS实现上需要的循环次数和层数比较大，复杂度较高，不适合用matlab实现。在本实验中，ESS算法完全由自己实现，并且得到的效果较好。影响框定位效果的主要是点的密度。由于前景点和背景点的分布比较密集，本算法采用了将前景点给与一个正分，背景点给与一个负分的策略，根据ESS的原理，最终给出的框定位的矩形框将是全局最优的矩形框。2)二值标记在二值标记这一步中，一开始拟采用的策略是分类一个五维的向量[r,g,b,x,y]，即用图像中前、背景的颜色信息和位置信息区分轨迹的归类。然而，在实验中发现，这样的信息往往是会造成分类结果恶化的原因，究其原因就是在食品当中，前景和背景的颜色通常差异性不是那么明显，而且前景点和背景点的位置信息不足以区分前背景因为前背景的追踪点分布有时候是较杂乱无章的。因为以上的原因，本实验将原来的[r,g,b]缩减为v，即用灰度信息取代颜色信息，几何信息依然保留。通过实验，可以发现点周围的点的种类和数目通常也对该点的分类有很大的影响，所以[a,b]向量被合成到[x,y,v]中，构成一个新的五维向量。之后再此五维向量空间中，通过用已标记的稀疏模型训练一个神经网络然后用此神经网络对每一个像素进行标记，通过代表该像素的五维向量。4.2.2从不同数据集的角度分析在这个小节中，本文将从不同测试数据集的差异性和共性的角度出发，分析不同数据集间实验结果的相同和不同，并从这个角度评价算法的实现。1）汽车在汽车（CARS）的测试视频中，可以从图4-2中看出，二值标记的结果很好，这主要是因为首先，在汽车的测试视频的相机运动（相对于其他两个测试视频）不适那么剧烈，从而可以追踪到的特征点都较为稳定、密集而且分布明显。与此同时，可以观察到第三辆车的分割效果及其好，而在原视频种虽然能看到该车移动，但是移动十分缓慢，这从另一个侧面证明了本算法在移动相机视频中提取移动目标的准确性。\n另外，由于汽车是刚体，所以追踪点轨迹较为稳定，这也是分割出好的效果的一个重要因素。1）手在手（HAND）的测试视频中，效果一般。可以较为明显的看出，一只手被提取了出来，但是效果没有汽车那么好。这个原因有两方面，其一是手本身不是刚体，自身的相对运动很强烈，导致特征点的提取不稳定。其二是手本身特征不够显著，导致特征点比较稀疏，对分类造成了困难因素。2）人在人（PERSON）的测试视频中，可以看到效果不是很理想，查全率比较低。这主要是因为人的衣服较之手更为“非刚性”且不显著，这加剧了特征点的密度下降和噪音的增加。综上，实验证明了本算法的正确性和有效性，证明了本算法的实现在移动相机视频的目标提取这个问题上有着较好的表现。同时，证明了本章一开始的猜想，那就是一个好的分割效果是和稳定的追踪点轨迹和轨迹的分布以及密度是分不开的。\n第五章总结和展望5.1算法实现的总结本次毕业设计的整体算法思路都是在研读舍赫教授的论文之后确定的，其中，也多次与舍赫教授通邮件询问实现的细节。由舍赫教授无法提供源程序和代码，本论文中的主要部分代码都是通过研读论文当中的描述自己独立实现的。最后的实验结果表明，本算法的实现是成功的以及正确的。由于实验环境以及其他一些客观条件和论文中所描述的不尽相同，所以实现细节上可能与论文中描述的不一样，用的方法和模型也存在一定的出入。以下将分步总结每个步骤实现的细节。5.1.1特征点的提取和轨迹矩阵的建立SIFT特征点的提取采用的是matlab的实现版本。SIFT的代码在网上有很多很成熟的实现方案，所以在本文中就没有必要再实现一遍。特征点匹配算法使用的是最近邻算法，如图3-7所示。最近邻算法的实现是使用的matlab，事实证明，虽然使用了一系列的matlab中自带的矩阵操作简化了计算过程，这一步通常还是很慢的。在匹配完毕后，在后续步骤中本文使用了两个限制条件用来纯化匹配点阵，其一是限制相距过紧密的比配点（比如0.5个pixel，因为SIFT给出的点的坐标是精确到小数位的）；其二，限制了一些距离过大的匹配点（阈值的设置如下：匹配的纵向间距不得超过屏幕高度的一半，匹配的横向间距不得超过屏幕宽度的一半），因为视频虽然在抖动，但是帧间是连续的，所以相距太远的匹配应该是错误的。“焊接”策略完全是独立设计并实现的，具体的操作和结果如图3-8和3-9所示，作用还是比较明显的。另外，追踪轨迹矩阵的建立主要还是依靠了MIT的Dr.PeterSand的微粒视频的算法。该算法的实现代码是开源的C++代码，输入时视频序列和帧数，输出就是轨迹序列，如前一章所示。由于微粒视频的计算特别复杂和缓慢，所以对于一个视频测试序列，本文中只取了前25~30帧。5.1.2稀疏模型的实现在提取追踪点轨迹序列之后，轨迹点序列被整理在一个2FxP的矩阵里，矩阵形式已经在以前的章节中讨论过了。在实际的实现当中，提取出来的\n轨迹矩阵不能立刻当作建立稀疏模型的输入来处理，因为由于遮挡、噪音还有一些其他的因素，有很大比例的轨迹无法被用来处理，而在计算稀疏模型之前，要先将满足需要的轨迹挑选出来。挑选出来的轨迹只要满足一个要求：轨迹能够充满一个窗口（在本论文的实现当中，这个窗口的长度是30帧）。在实验中经过验证，我们发现有用的轨迹占整个轨迹数量的百分之五十到百分之八十，这说明上述的过滤手段是很必要的。RANSAC的实现如图3-14所示，这里就不再赘述。要强调的一点是，在RANSAC的实现中，阈值等参数的选择对实验结果有很大的影响，在实验计划当中，希望找到一个自适应性的函数能够动态地解决这个参数的选择问题，可惜的是由于时间紧迫等原因，这个设想很遗憾地没有得到验证和实现，在实验中，本文采取了设置固定值的方法，虽然不甚智能，但是效果还不错。最后的标定结果中如图3-18中所示，其实这时的结果就已经较为明显了，后续步骤只不过是根据这个结果再进行下一步的处理。噪音的影响还是有的，不过对于刚体的前景，这个影响会小一些。5.1.3框定位算法的实现框定位的实现主要是依托于ESS（快速子窗口定位）技术。这个程序的实现是在C++下实现的，也是完全独立实现的。在实现中发现前一步中的稀疏模型的结构和密度分步对这一步有很大的影响，所以在这一步里，面临的问题和上一部分是一样的，即参数如何选定。前景点的分值太高的话，容易造成为了将错误前景噪音(falsepositive)纳入而定位的过大，若前景点的分值过低，则会造成错误背景(falsenegative)的影响太大，导致定位框定位不完全。实验经验表明，前景点的分数时背景点分数绝对值得1.5倍时，效果比较好。5.1.4像素级标定的实现像素级标定这个任务在本论文中是以神经网络的方式实现的。一开始做的时候，有两个备选方案，一个是使用固定带宽的掩模，计算每个像素最可能属于哪个类，这是由掩模内各种点的数量决定的；第二个方案是用该点的表征信息（颜色、位置等等）作为点分类的信息，在五维空间中找到一个分割平面。但是在实验中发现，第一个方案虽然简单，但是比第二个方案效果好很多。原因在于实验中的视频，前景点的颜色信息不一定一致，而且和背景的区别不一定很显著。最后本文采取一个折中的方案，如3.9节所说的那样。实验证明这个策略是成功的。5.2过程中遇到的问题以及解决在本次毕业设计当中，由于事先做的准备工作比较充分，所选题目虽然是个新题目，视频和前景提取这个方向的项目之前并没有做过，但是计算机视觉和图像处理方面的项目和知识还是做过一些，了解过一些的。所以前期的方案和技术路线制定的还算明确。\n然而，随着实验的不断深入，有些问题不断地被暴露出来。第一个就是特征点不足的问题。由于开始制定试验计划的时候，没有意识到SIFT特征点的稀疏性，而这种稀疏性在后来的二值标定当中，很有可能是致命的。后来，在陈锦言老师的指导下和不断的查阅资料、和原文作者交流，发现微粒视频的程序是开源的并且可以使用，再加上自己思考通过“焊接”匹配矩阵增加追踪点的数目，这个问题最后终于被成功解决了。接下来的问题主要是在各种需要给定参数的函数当中取得一个经验值。经过数周的试验和修改，最终试验的经验值被确定下来，并且达到一个较好的结果。最后，就是本试验属于Matlab与C++混合编程，在matlab中调用C++写好的函数，这是一个挺新颖有趣的技术，经过学习和实践过后，这个问题也解决了。\n参考文献[1]Y.Sheikh,O.JavedandT.Kanade.Backgroundsubtractionforfreelymovingcameras[A].In:ProceedingsofIEEE12thInternationalConferenceonComputerVision[C].IEEE:2010.1219-1225.[2]P.SandandS.Teller.ParticleVideo:Long-rangemotionestimationusingpointtrajectories[J].InternationalJournalofComputerVision,2008,80(1):72-91.[3]G.BradskiandA.Kaehler.LearningOpenCV:ComputerVisionwiththeOpenCVlibrary[M].O’ReillyMedia,2008.[4]W.Zhang,X.Cao,Y.Houetal.Detectingandextractingthephotocompositesusingplanarhomographyandgraphcut[J].IEEETransactionsonInformationForensicsandSecurity,2010,5(3):544-555.[5]C.Zhang,X.GuoandX.Cao.DuplicationLocalizationandSegmentation[A].In:ProceedingsofPacific-RimConferenceonMultimedia[C].Springer:2010.578-589.[6]M.Cho,Y.Shin,andK.Lee.Unsuperviseddetectionandsegmentationofidenticalobjects[A].In:ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition[C].IEEE:2010.1617–1624.[7]D.Lowe.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,2004,60(2):91–110.[8]C.H.Lampert,M.B.Blaschko,andT.Hofmann.Beyondslidingwindows:Objectlocalizationbyefficientsubwindowsearch[A].In:ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition[C].IEEE:2008.1–8.[9]R.HartleyandA.Zisserman.Multipleviewgeometryincomputervision[M].CambridgeUniv.Press,2004.[10]C.Wren,A.Azarbayejani,T.Darrelletal.Realtimetrackingofthehumanbody[J].IEEETPAMI,1997.[11]D.HochbaumandV.Singh.Anefficientalgorithmforcosegmentation[A].In:ProceedingsofIEEEInternationalConferenceonComputerVision[C].IEEE:2009.269–276.[12]W.HardleandL.Simar.Appliedmultivariatestatisticalanalysis[M].SpringerVerlag,2007.\n[13]C.Bishop.Patternrecognitionandmachinelearning[M].Springer,2006(4).[14]A.Elgammal,R.Duraiswami,D.Harwoodetal.Backgroundandforegroundmodelingusingnonparametrickerneldensityestimationforvisualsurveillance[A].In:ProceedingsoftheIEEE[C].IEEE,2002.[15]N.FriedmanandS.Russell.Imagesegmentationinvideosequences:Aprobabilisticapproach[A].In:ProceedingsofConf.UncertaintyinArtificialIntelligence[C].2000.[16]I.Haritaogolu,D.Harwood,andL.Davis.W4:Real-timesurveillanceofpeopleandtheiractivities[J].IEEETPAMI.2000.[17]R.JainandH.Nagel.Ontheanalysisofaccumulativedifferencepicturesfromimagesequencesofrealworldscenes[J].IEEETPAMI.1979.[18]O.Javed,K.Shafique,andM.Shah.Ahierarchicalapproachtorobustbackgroundsubtractionusingcolorandgradientinformation[A].In:ProceedingsofIEEEWorkshoponMotionandVideoComputing[C].IEEE:2002.[19]Y.SheikhandM.Shah.Bayesianobjectdetectionindynamicscenes[J].IEEETPAMI,2005.[20]C.StaufferandE.Grimson.Learningpatternsofactivityusingrealtimetracking[J].IEEETPAMI.2001.\n外文资料\n中文译文自由运动镜头的背景相减算法亚瑟舍赫卡内基梅隆大学匹兹堡美国欧迈杰夫ObjectVideo公司来斯顿美国金出武雄卡内基梅隆大学匹兹堡美国摘要背景相减算法主要目的在于定义一个镜头中那些部分是静止的。传统上这些算法基于一个假设，那就是镜头本身是静止不动的。这些算法找出通过观察视频的哪些部分随着时间变化而变化来找出云的那个的物体。在这篇论文中，我们将“相减得出静止的部分”这个概念扩展到适用于那些用自由移动的镜头所拍摄的视频当中。我们不需要假设背景是大致可以被粗略估计成一个平面或者相机中心在运动中保持静止。本方法运作完全运用二维的图像估计方法而没有一个镜头的精确的三维重建模型。首先，我们通过跟踪一些在视频中显著的特征点来得到一整套轨迹基然后运用这些轨迹鲁棒地估计出一个稀疏的背景模型。而后背景相减算法被“减”出来，运用去除不符合该轨迹基所展出的解空间。前景和背景的表征模型被建造出来，基于最优化的像素级别的前景/背景标记，运用有效地最大化一个后验概率方程。引言从本质上讲，背景相减的算法旨在从镜头的顺序分析中分辨感兴趣的区域。“感兴趣的”这个词本身有一个很直接有力的定义：在景物中运动着（或者变化着的）的物体（或者区域）。分割这些物体（或者区域）的最有效的方法就是保证，在该镜头或者情景当中的物体运动能够排他地转换为视屏数据当中的运动（即计算机能够理解的明显的变化）。这一目地已经在目前流行的视频监控运用中被实现了很多次，并且大家的方法中都无所不在地基于一个假设：相机本身是静止的（这个假设不一定正确但在一定条件下是普遍成立的）。这些算法的成功导致了工业界的可视化监控产业的成长，构成跟踪、物体识别、姿势重建和动作识别的基础。这个相机静止的假设，然而，严重地限制了计算机视觉相关算法的应用——而这一限制正在随着运动相机平台的普及儿变得越来越严重，例如手机，车辆和机器人。随着越来越多的视屏内容被移动相机所产生，对于在这样的视屏中提取感兴趣区域的基础算法的需求也就越来越迫切了。在本论文中，我们提出了一个算法，沿用了“感兴趣的”是“在三维世界中运动着的”的定义并且将其扩展到一个可自由移动的镜头中。这个算法的输入是移动相机所拍摄的视频，输出是运动物体的二值图像，在每一帧当中。\n就像帕尔默说的那样，图像的运动由三者引入：相机的移动、独立物体的移动以及景观的三维结构。本文主要解决了由相机动作而引入的图像运动和由物体运动而引入的图像运动之间的二义性。本算法主要基于的直觉是可以运用几何的限制去在稀疏的位置进行可靠地区分像素点的运动，比如正交投影的秩约束和投影相机里的极几何约束。这些稀疏的位置然后可以被用来建立前景背景的表征模型，反回来被用来分割独立运动的物体。相关工作于背景相减和运动相关的文献有很多，我们在这里只回顾那些主要的主题。最早的背景相减算法是在70年代，Jain和Nagel，他们用帧间差去寻找运动的物体。接下来，一些方法提出用概率模型的级数来解决背景表征的不确定性，比如Wren等人提出的像素级的背景表征高斯模型。Kalman过滤器被用来更新像素的颜色，高斯混合模型，无参数的核密度估计，以及联合空间-颜色模型。在这些方法中，统一的概念主题是背景的定义：景物当中静止的那部分。对于这个定义的一个重要的变种是北京当中的结构化动态因子（比如水波纹，风中的枝叶，以及有名无实的相机运动），在这些当中，不同的概率模型被提出来。这个对背景“静止”的定义导致了一个普遍的前提，那就是相机必须在整个拍摄过程中保持静止。放宽这个限制的研究很大程度上依赖于自运动补偿。单应和二维仿射变换被用来补偿运动，传统的背景相减算法中的很多的想法被应用于检测前景区域。这些方法的局限性在于他们的背景必须被很好的近似成文一个平面或者相机运动必须被限制为平面运动，倾斜和放缩，即相机中心不运动。对于那些相机中心可能旋转或偏移的例子，有一些奇技淫巧被提出来。在平面+平行的框架中，单应性首先被顺序的在两帧之间计算出来。登记从操作将相机旋转、放缩和校正的影响消除。剩下的像素，要么属于景深很深的三维刚性结构或者前景物体。为了计算单应性，这些方法假设了一个景象的主平面，并且成功被运用于空中的物体的检测，因为在空中这个假设通常会成立。基于层的方法将景物家末尾一片一片的平面景物，这些簇状的分段基于运动的连续性。Yuxin等人单纯运用了基于层的方法去做移动相机的背景剪除算法，却得到了很不好的效果。最后，运动分割方法稀疏地分割了点轨迹，基于运动的几何连续性。和以上方法都不同，我们方法的目的是将传统的背景（不动的区域）定义扩展到移动相机并且处理1）不同尺寸的前景物体；2）刚性和非刚性的前景物体；3）全三维的背景。我们的方法提供了像素级的前背景标记在富有挑战性的手持相机所拍摄的视频序列中。背景的秩约束在静止的环境当中，被引入到视频当中的运动仅仅是通过场景的三维结构以及相机自身的运动。这样的图像运动必然满足的几何约束是很好懂的。如果P个稳定的检测点被在一系列的帧间跟踪的话，那么第i个点的轨迹就可以被建模为wi=[x1iT…xFiT]这样一个1X2F的向量。而所有的轨迹则可以被整合成一个2FxP的矩阵。\n在无噪声的情况下，并且在正交投影的假设下，这样一个轨迹矩阵是秩为三的。这样的一个矩阵的秩约束是基于这样的一个事实：这个矩阵可以被分解成为三维点的3xP的结构矩阵，和一个2Fx3的正交矩阵。一个方便的对于这个秩约束的看法可以这样：所有的静止场景当中的二维轨迹都是存在与由三个轨迹基所展开的子空间的。如果有在场景当中独立运动的物体，那么，轨迹矩阵的秩一般而言会超过3.我们放宽这个限制去找到那些列所组成的子矩阵，而这个子矩阵能够满足秩为三的约束。那么我们就认为这样的一个子矩阵所代表的轨迹点都在精致的背景之上——即背景上。RANSAC算法被用来鲁棒地计算最好的三维矩阵子空间，并且用来鉴别哪些轨迹属于背景。在RANSAC的过程中，一组三个的轨迹被随机地挑选出来。一个拟合的函数被用来建立一致性地测试由三维展开子空间的投影错误。由三个轨迹基所构成的矩阵被用来计算投影矩阵。投影矩阵被用来衡量一个给出的轨迹wi是否属于背景，通过计算他的投影误差。如果有足够的数据一致性通过一组被选出的轨迹基，这个进程就终止了吧。否则，另外一组基将被挑选出来，然后，上述的操作将继续进行直到一个一致性的集合被满足。这个进程提供了一个背景轨迹的三维子空间，一个由n个轨迹构成的内层集合代表背景；由m个轨迹构成的例外对应代表了前景。由于遮挡，噪音和各种各样的相机运动，估计出来的轨迹长度通常在长度上变化显著。提出方法的一个特色是我们不要求分解算法，比如说SVD分解（不能处理失去的数据），为了持续稳定地在长视频中标记，我们运用一个滑窗的算法，即标记每一帧的时候，我们只取它前后的30帧。在这个窗口中的轨迹则被用来计算轨迹基。这样的一个策略保证了错误的轨迹不至于毁了整个视频。构建前景\背景模型这个算法的目的是对图像中的N个像素构建一个二值标记。给定背景和前景轨迹，我们希望计算一个标记组合能够够最大化一个后验概率。应用贝叶斯理论并且假设条件独立，我们可以将这个后验概率建模成两项。似然函数可以是两项的乘积，一项代表是该像素属于背景的概率，另一项表示该像素属于前景的概率。我们运用背景轨迹和前景轨迹去创建背景表征模型和前景表征模型。对于某一帧来说，背景的轨迹点在当前帧被用来建模背景模型，对于每一个点有五个参数，分别为x坐标，y坐标，r值，g值，b值。一个候选的像素属于前景还是背景的概率运用和密度方法进行估计。通常上带宽矩阵是自适应性地被估计的，即在不同的地方有不同的值。运用自适应性的带宽估计子的好处就是它将手动调整带宽参数的需要消除了。更进一步，带宽参数在不同的空间区域取决于不同地方的点的密度。这个策略典型地导致了分类准确率的上升，这一点也被实现证明了，主要是因为视频各个地方的可追踪点的密度是有很大差异的。相似的，前景轨迹点被用来建立前景表征模型。一个成对的马尔科夫随机场被用来加强标记的平滑性。整个解空间的规模非常巨大，所以不能用穷举法解决。全局的搜索可以被有效地利用图分割算法来解决。结果\n我们的算法在一系列不同的手持相机所拍摄的视频上进行了测试，包括室内和室外的，也包括不同的非刚性的物体，比如说手，脸和身体。这些视频序列是高分辨率的而且在帧间的动作都比较显著。在这些视频序列中，有一些很显著的3D结构引入的变化，儿渲染的自运动补偿方法或者邻居模型不能够解决这个问题。本实验中的参数如下：RANSAC的阈值t,RANSAC的次数T，时间的窗口s和平滑参数lamda。他们的值在整个试验中都是固定的，分别如下：t=0.01,T=1000,s=30,lamda=30.似然率阈值用来产生最后的结果是L。轨迹点在这些视频序列中是通过粒子视屏追踪（Sand和Teller）完成的。目前这一顶尖的算法能够提供高密度高质量的轨迹点序列。我们通过对HAND,PERSON和CARS自己创建基准真值分割结果密集地测试了我们的方法。我们对比了四种条件下的查全率和查准率：1）基于似然率阈值的标记，并且用一个固定的带宽矩阵，其参数是手工选定的；2）最大化一个后验概率（同一个马尔科夫随机场的先验概率）标记，并且运用一个固定的带宽矩阵，其参数是手工选定的；3）基于似然率阈值的标记，并且用一个自适应的带宽矩阵，其参数是自动选择的；4）最大化一个后验概率（同一个马尔科夫随机场的先验概率）标记，并且运用一个自适应带宽矩阵，其参数是自动选择的。我们的结果表明了很重要的两点：其一是，当所有点的分布并不是统一的时，选定一个统一的核带宽矩阵是不合适的。经验证明并且验证了，对于特定的前景区域，追踪点的分布可以是很不同的，区域和区域之间的差异也同样很显著。自适应性的带宽矩阵方法有一个附加的好处，那就是它是完全自动的并且不需要带宽的选择和测试。在我们的实验当中，带宽是通过一个似然函数的交叉验证方法估计的，其权重比是通过K个最近邻获得的。其二是马尔科夫随机场的先验概率提升了结果，不仅仅是查全率，查准率也上升了，因为孤立的像素点也被消除了，而且经验上查全率和查准率的上升是同步的。总结和讨论在本篇论文当中，我们解决了这样一个问题：如何在移动的相机拍摄的视频当中区分背景和前景，即在景物中的那些部分是静止不动的，我们将这些部分分割出来。并且，我们发现了一个事实，那就是所有的对应着静止区域的追踪点的轨迹实际上是存在与一个三维的展开向量空间的能讲前景还是背景区分开的。RANSAC被用来鲁棒地运用秩约束估计背景的轨迹基矩阵，并且用来区分一个给定的轨迹序列向量是例内项（背景）还是例外项（前景）。一旦被分类了，这些轨迹会提供一个稀疏的对视频的标记，而后这儿标记会被用来建立前景和背景的表征模型。这些模型会通过结合一个马尔科夫随机场的先验函数去估计最大话的一个后验概率，关于像素级的标定，通过寻找一个流量图的最小割。整个算法被通过基于二维的场景中执行，尽管所有的几何约束都是基于完全的三维下，并且丝毫没有必要去清晰地详尽地重建一个三维的场景。一共有两个概念性的假设在这篇论文中被使用：1）正交的相机模型被使用，2）背景在空间意义上是刚性的物体在图像中。\n我们方法的主要限制在于使用的相机模型是仿射模型。然而，现实世界中的视频或者图像，更为接近的是透视的相机模型。我们之所以使用仿射的模型，原因在于对于透视的模型，没有一个有用的超过3帧的普适的几何约束存在。换言之，由于在衡量矩阵的秩约束时，我们必须同时地从多帧里找到这个约束，而在透射的相机模型中，并没有能够找到这样合适的（如同在仿射模型下的）的秩约束。这一点在实践中很重要，因为没有任何保证对于相机在两到三帧之内必须运动，或者物体在帧间必须足够地显著地运动（在图像上移动足够的像素数目）。所以，为了平衡起见，我们选择了多帧的仿射方法，而不是二帧或者三帧的透视方法。一个对该模型的效率有说服力的证明就是我们的结果在一些我们在实际的视频上的结果（这些视频所以是透视的）。而这些镜头中，三维的各种变化，平行和典型地手持视频中的一些室外的和城市中的景物。在未来的工作当中，我们将会仔细调查那些能够提升相机模型到全透视的方法。而这个方法希望是能够保持一个多帧的限制不变性，就像我们本文中的正交投影那样的。辨别移动物体（变化区域）的能力将会将相关的研究提升到一个新的高度，更会促进其他的研究领域比如动作识别和景物理解，尤其是对于那些手持相机所拍摄的视频。\n致谢经过半年多的努力，终于在毕业即将到来之际完成了本科毕业设计。这是一次对大学四年学习成绩的检验，也是对自己四年来学习的肯定，完成了这份工作，心里有一种自豪感，也明白了过去的汗水没有白费，自己新的人生将以此为转折。本次毕业设计，是我所做的第一个和视频内容提取和理解相关的题目，在这里，我深深感谢陈锦言老师，操晓春老师等在毕业设计和研究中给予我无私关怀和真诚帮助的人。在选题的时候，陈老师主动耐心地结合我之前的工作经验，给我指导安排了这个和我之前研究方向很匹配的题目，并且在安排实验和学习进度的时候，多次给予我宝贵的指导意见，能够让我在这几个月里顺利地完成毕业设计的实现和毕业论文的撰写。更重要的是，在陈老师的帮助下，我对计算机视觉和图像处理方面的理解又加深了一层，巩固了基本概念，提高了实验技能，开拓了研究视野。其次，我要感谢和我一起努力并且帮助过我的同学们，我们在毕业设计中一起讨论，相互交流，彼此帮助。我们学到了彼此的长处，也因相互的提醒避免了自己的不足。我们不仅收获了知识，也因此结下了深厚的友谊，这也是我在天大收获的一笔很大的，受用终身的财富。最后，我要感谢四年来教过我们的专业课老师，是他们让我们从无知走进软件工程的世界，让我们从懵懂走向了成熟。他们不仅教给我们基础知识，同时也教给我们人生的哲理，师生情，永难忘。再次感谢陈老师以及其他给予我指导和帮助的老师、同学，你们教会我太多太多，你们的一言一行，都将知道我在以后的工作学习中勇往直前。感谢天大，我人生最美好的时光在这里度过，我人生最宝贵的财富在这里拥有，我人生最难忘的画面在这里定格。走出天大，我将拥有美好的明天。