基于Tango手机系统的3D扫描系统设计和实现电子信息工程专业.docx

摘要1Abstract2第一章绪论41.13D扫描系统的研究背景与意义41.2国内外研究现状51.2.1三维重建研究现状5L2.2基于视觉的SLAM技术5L3本设计内容及结构安排7第二章数据信息采集与处理82.1Tango手机的硬件构成82.2利用Tango手机采集数据82.3标定与滤波处理102.4本章小结12第三章基于特征点的视觉里程计133.1视觉里程计133.1.1特征点提取133.1.2ORB特征提取算法143.2特征点匹配163. 3本章小结18第四章闭环检测与非线性优化194. 1闭环检测194.1.1闭环检测的意义194.1.2词袋模型204.2非线性优化214. 2.1非线性系统的状态估计215. 2.2图优化与g2o框架224. 3本章小结23第五章实验验证分析244.1 实验设备环境及操作方法244.2 实验操作与结果分析245. 2.1信息采集与处理实验245. 2.2视觉里程计模块实验256. 2.3闭环检测与非线性优化实验265. 2.4场景重建实验285. 3本章小结30第六章总结与展望316. 1全文总结316.2工作展望31参考文献33致谢错误!未定义书签。基于Tango手机系统的3D扫描系统设计摘要在人工智能和计算机视觉快速发展的时代背景下，设计3D扫描系统对场景进行三维重建是前沿和热点问题之一。目前的三维重建技术根据传感器不同，主要分为基于激光雷达设备的建模和基于视觉的相机建模。激光雷达设备具有高精度，高实时性的特点，但其价格昂贵，成本太高，且适用环境受到限制，在空中或水下的建模效果差；基于视觉的三维重建设备代表之一是微软公司推出的KineCt相机，其可以捕捉RGB图像和深度图像中的信息从而实现场景的三维重建，成本低廉，但存在精确度较低，重建操作复杂，不易携带等缺陷。针对此问题，本设计提出基于Tango手机的3D扫描系统。利用联想公司推出的Tango嵌入式手机，实现对场景的实时三维重建，在保证重建精度的基础上，降低了硬件成本，简化了重建操作，同时便于携带，具有广泛而深远的发展前景。本文介绍TTango手机平台的硬件结构以及利用RGB-DSLAM技术采集数据信息的原理；使用张正友标定法和高斯滤波对数据进行预处理从而减小系统误差和噪声对重建效果的影响；通过比较多种特征点的提取和匹配算法，最终确定采用改进的ORB特征提取算法配上BRIEF描述子和K-D树搜索算法来实现；基于视觉内容搭建词袋模型，利用闭环检测解决场景模型的累积漂移问题；最后采用g2o框架进行图优化，解决非线性系统的位姿状态估计问题。通过实验对本设计进行验证，利用Tango手机开发平台对多个室内场景三维重建，并对比KineCt的扫描系统，操作简单，重建速度较快，具有相对的高实时性，同时重建模型精度满足任务要求，总体达到了预期目标。关键词：Tango；RGB-DSLAM；ORB算法；闭环检测；图优化AbstractUnderthebackgroundoftherapiddevelopmentofartificialintelligenceandcomputervision,designing3Dscanningsystemstoperform3Dreconstructionofscenesisoneofthefrontierandhotissues.Thecurrentthree-dimensionalreconstructiontechnologyisbasedondifferentsensorsandismainlydividedintotwotypes:Lidar-basedmodelingandvisionbasedcameramodeling.Laserradarequipmenthasthecharacteristicsofhighprecisionandhighreal-timeperformance,butitspriceishigh,theapplicableenvironmentislimited,andthemodelingeffectintheairorunderwaterispoor;oneoftherepresentativesofvisualbased3DreconstructionequipmentistheKinectcameralaunchedbyMicrosoftCorporation,whichcancapturetheinformationintheRGBimageanddepthimagetoachievethethree-dimensionalreconstructionofthescene.Thecostislow,butthereisaloweraccuracy,complexreconstructionoperations,noteasytocarryandotherdefects.Tosolvethisproblem,thisdesignproposesa3DscanningsystembasedonTangomobilephones.UsingtheTangoembeddedmobilephoneintroducedbyLenovo,therealtime3Dreconstructionofthesceneisrealized.Onthebasisofensuringthereconstructionaccuracy,thehardwarecostisreducedandthereconstructionoperationissimplified.Itisconvenienttocarryandhasextensiveandfar-reachingdevelopmentprospects.ThisarticleintroducesthehardwarestructureoftheTangomobilephoneplatformandtheprincipleofusingRGB-DSLAMtechnologytocollectdatainformation.ItusesZhengyouZhangcalibrationmethodandGaussianfiltertopreprocessthedatatoreducetheinfluenceofsystemerrorandnoiseonthereconstructioneffect;Bycomparingtheextractionandmatchingalgorithmsofmultiplefeaturepoints,theORBfeatureextractionalgorithmisfinallydeterminedtomatchtheBRIEFdescriptorandtheK-Dtreesearchalgorithm;Basedonthevisualcontent,abagmodelisbuilttosolvetheproblemofcumulativedriftofthescenemodelbyusingclosed-loopdetection.Finally,thegraphisoptimizedbyusingtheg2oframeworktosolvetheposestateestimationproblemofthenonlinearsystem.Theexperimentwasusedtoverifythedesign,usingtheTangomobilephonedevelopmentplatformtoperform3DreconstructionofmultipleindoorscenesandtocomparethescanningsystemofKinect.Theoperationissimple,therebuildingspeedisfast,andithasrelativelyhighreal-timeperformance.Atthesametime,theaccuracyofthereconstructionmodelmeetstherequirementsofthetask,andtheoverallgoalisachieved.Keywords:Tango;RGB-DSLAM;ORBalgorithm;closed-loopdetection;graphoptimization第一章绪论1.1 3D扫描系统的研究背景与意义人工智能（ArtifiCiallmelligenCe）是二十世纪五十年代的产物，发展至今，已成为二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。人工智能近三十年里的进步飞速，在涉及到的很多科学领域内都取得了丰硕的成果。其中，计算机视觉是人工智能的重要分支，利用传感器代替人眼，通过计算机进行信息处理后，可以对目标进行识别、跟踪和分析，使计算机能够像人那样通过视觉观察和分析，获得自主适应环境的能力。本文研究的3D扫描系统设计，旨在通过摄像机采集数据并通过一系列处理方式，达到实时地构建出场景的三维模型。三维重建技术的应用方向极为广泛，在机器人自主导航、无人汽车、无人机航拍、教育、3D打印、医疗影像、虚拟现实游戏及电影等领域，是未来不可或缺的一项技术，具有着广阔的发展前景。三维重建技术的发展之初是利用机器人携带相机对场景进行拍摄或扫描，结束之后将获得的视频或照片在具有强大功能的计算机上处理，以此完成对场景的三维重建。但这种方法存在一个明显的缺陷：非实时性。一旦场景发生变化，重建的价值也会大打折扣。为解决这个问题，研究人员提出了以视觉传感器为中心的视觉SLAM网（SimultaneousLocalizationandMapping,同时定位与地图构建）技术，涉及数学、物理学、几何学、图像处理、机器人、仪器科学等多门学科。它是指携传感器的主体，在没有环境这类先验信息的情况下，通过运动过程中获取的信息，建立周围环境的模型，同时估计自己的运动轨迹。利用视觉SLAM技术进行场景三维重建的代表之一就是手持扫描仪KinectFusiono用户手持Kinec*相机，缓慢移动，将采集到的数据直接反馈给具有强大处理能力的GPU和CUP计算机，再经过一个优化的过程，即可在计算机上实时观测到高质量，几何精确的场景三维模型。不同于PC端的实时三维重建，本文的研究方向是基于嵌入式设备的实时三维重建，将PC端上操作复杂的重建系统简化到一个嵌入式设备上，在尽量不牺牲重建精确性的基础上，实现操作简单，携带方便的3D扫描系统设备。主要利用了联想公司推出的Tango手机设备和RGBD-SLAM技术以达到预期目标。1.2 国内外研究现状1.2.1 三维重建研究现状三维重建技术按实时性分为非实时性重建和实时性重建，按传感器种类分为激光雷达设备和视觉传感器设备，按实现平台分为PC端和手机端。随着计算机视觉领域的不断扩大，SLMA技术也被用于解决在未知环境中机器人的定位和构建地图问题。基于此的视觉SLAM在三维重建领域带来了转变和突破。目前，主流的重建方式是基于激光雷达的PC端三维重建，用于满足工业上的需求，其高精确度是其他重建方式不可比拟的，但由于设备的高额成本，无法实现在日常生活中的普及。另一类重建方式是利用最普遍的传感器一相机采集视觉数据，降低了成本，但精确度下降，如微软公司的Kinect和GOogle公司的Tango平台。此类的研究方向大多是利用Kinect相机的特有结构进行场景重建，要想取得较好的模型需要改进各个模块算法或利用GPU加速实现。基于KineCt的PC端三维重建技术基本成熟，甚至可以做到实时三维重建，但其在面对用户方面显得比较笨重复杂，不具有便携性。在嵌入式设备Tango手机上进行三维重建的研究正在发展阶段，随着重建技术的逐步完善，该类重建技术具有的应用前景和市场也是可观的。1.2.2 基于视觉的SLAM技术按测量深度信息的方式不同，视觉SLAM使用的相机可分为单目相机(Monocular)、双目相机(Stereo)和深度相机(RGB-D)三类。单目相机只有一个摄像头，通过采集彩色图像获取RGB信息，再利用相机移动时产生的视差计算物体的远近，但该方法存在尺度不确定性，无法确定真实尺度；双目相机有两个相机，除了可以获取RGB信息外，也可以利用两个相机之间的基线确定深度(三角法测量),但其缺陷是计算量大,不利于重建的实时性;深度相机克服了前两种相机存在的缺陷，既可以通过彩色图像采集到RGB信息，还可以通过飞行时间法(Time-OfFlight)或红外结构光来获取深度信息。飞行时间法获取深度信息的原理是利用红外发射器发射一束近红外光，根据反射时间差或相位差换算出物体与相机间的距离。利用这种方法获取深度信息的缺点是分辨率较低且成本较高。红外结构光法是一种主动式测量方式，发射一束红外激光束经衍射光栅分解投影到目标上，然后根据目标平面与参考平面的距离和光斑偏移之间的约束关系，测量光斑的偏移即可转换出目标物体与相机间的距离，计算简单，价格便宜。但红外结构光法获取的深度信息容易受到日光或其他传感器发出的红外光的干扰,因此仅适于在室内使用。图1-1单目相机图1-2双目相机经过过去十几年的研究，视觉SLAM己经形成了经典的框架，如图1-4：图1-4经典视觉SLAM框架图本框架通过传感器采集数据，这些传感器多种多样，包括相机、激光、编码器、陀螺仪、加速度计、IMU(惯性测量原件)等。将采集到的数送给视觉里程计(ViSUalOdometry)估算相邻图像间相机的运动，同时用闭环检测判断是否回到了之前到过的位置。后端对接收到的相机位姿和闭环检测信息优化，得到全局一致的地图和轨迹，最后根据估计的轨迹构建与任务要求相符合的地图。1.3本设计内容及结构安排本文将对利用Tango手机进行三维重建系统设计，各章节主要内容如下：第一章为绪论，首先介绍了三维重建技术的研究背景和长远发展前景，然后根据研究现状并按照重建技术不同将三维重建系统分类。最后是本文主要的研究内容和文章的结构安排。第二章介绍了嵌入式设备TangO手机的硬件构成和获取深度信息的原理，然后使用标定和滤波方法减小系统误差和噪声影响。第三章为基于特征点法的视觉里程计，该部分模块负责计算相机的运动和特征点的位置。特征点的提取算法是通过比较后选取效果最好的ORB提取算法，而后基于ORB特征提取算法配合BRIEF描述子和K-D树搜索算法实现特征点的匹配。第四章为后端非线性优化环节和闭环检测模块。针对非线性系统的状态估计问题,通过参考文献，选用g2o框架的图优化求解相机位姿的状态。使用词袋模型的闭环检测解决累积漂移带来的重建失败，最终构建具有全局一致性的轨迹和地图。第五章为实验验证与分析。通过Tango手机重建的结果分析本系统的可靠性和重建效率，是否能满足任务要求。第六章为全文总结，并对利用嵌入式设备进行场景三维重建的未来工作和发展方向进行展望。第二章数据信息采集与处理2.1 Tango手机的硬件构成本设计的任务是在嵌入式设备上实现三维重建，鉴于深度相机获取深度信息的便捷性，选择了Tango手机（如图21）作为本设计的硬件基础设备。1600万像素PDAF摄像头深度感知摄像头（红外线 发射+接收器）运动追踪摄像头（鱼眼）图2-1Tango手机示意图上图是联想公司联合谷歌、高通打造的国内第一款TangoAR手机。使用QualcommSnapdragon6528核处理器，系统内存4GB,存储容量64GB,Android6.0系统，拥有前置800万像素摄像头，后置1600万像素摄像头，深度感知摄像头，支持RGB和红外线探测功能，运动追踪摄像头，重力传感器，亲近感应器，光线感应器，加速计，陀螺仪等，其中深度感知摄像头由红外发射器和红外接收器组成。该手机具有特有相机结构和传感器可以实现对物体的测绘和追踪，实时显示立体室内方位,虚拟和现实的交互等强大的AR体验。2.2 利用Tango手机采集数据三维重建设计的第一步就是要采集数据，本文需要使用Tango手机获取RGB信息和深度信息。RGB信息可以利用1600万像素的PDAF相机获取，而深度信息需要利用深度感知摄像头获取。该深度摄像头采用的是红外结构光法测深度信息，由一个红外发射器和一个红外接收器组成。红外结构光法是一种主动式测量方式，发射一束红外激光束经衍射光栅分解投影到目标上，然后根据目标平面与参考平面的距离和光斑偏移之间的约束关系（如图2-2）,测量光斑的偏移即可转换出目标物体与相机间的距离Zo由三角形相似原理，得:(2-1)(2-2)dp_D°-Db=T图22中/为相机焦距，P为目标物体，P所在平面为目标平面，O为参考平面上的点，。为目标平面和参考平面间的距离，坊为相机平面和参考平面间的距离，b为相机基线长度，d为像素偏移。联立式（21）和式（2-2）,可得：(2-3)D0Z=D0-D=D01÷jDO,dZ即为此时的目标物体深度信息UoL2.3 标定与滤波处理采集到的Z是相机坐标系下空间点P在Z轴上的投影坐标，要想获得P在空间坐标系下的坐标，还需要求解相机的内参、外参和畸变系数。图2.3相机成像模型图如图2-3为相机成像模型，空间点尸在相机坐标系下的坐标为X,匕Zt经小孔成像后在物理成像平面的坐标为P=X=Yf由三角形相似关系式2-4可以求出物理成像平面上的坐标。(2-5),X,YX'=%，Y,=fyLLa在物理成像平面上，为了实现对像素的采样和量化，建立像素平面坐标系，经缩放和平移后，F在像素平面坐标为，vT，轴缩放。倍，U轴缩放£倍，原点平移a,CJ即式26,将式2-5代入式2-6并简化可得式2-7：（uaX,+cxQvr（2-6）（V=Y+Cy（XP=A7+cJ（2-7）把式2-7写成式2-8的矩阵形式:fxO. 0X1r JKPLjLZJ(2-8)将Z移到左边得:fx0-00fy0X Y Z.(2-9)该式中P为目标空间点在相机坐标系下的坐标,K为要求的相机内参矩阵，求取内参矩阵K的过程即为标定W1过程。利用内参矩阵K,可以将目标物体的像素坐标转换为该点在相机坐标系下的坐标。为了获取较好的成像效果，相机前方通常要加上透镜，但由于透镜对光线的传播有影响，使成像位置发生变化，将这种位置的变化称为畸变。其中，由于透镜的存在将空间直线变为曲线的畸变叫做径向畸变(图2-4)；由于安装过程存在的误差，使成像平面和透镜平面不平行产生的畸变称为切向畸变(图2-5)。图2-4径向畸变图对于径向畸变，使用一对与中心距离相关的二次及高次多项式(2-10)纠正；对于切向畸变，使用另一对包含PI和p2两个参数的多项式(2-11)纠正。通过kl,k2,k3,pl,p2这5个畸变系数，可以求取像素点在相机坐标系下的实际坐标P。“ correct = "(1 + k/ + k?T +)y' correct = y(1 + 七八 + k2r4 + k3r6)X correct = % + 2p%y + P2(2 + 2x2)y correct = Y÷p1(r2 + 2y2) + 2p2xy =fXaV = fyyaorrect(2-10)(2-11)(2-12),orrect由于相机一直处于运动过程，所以相机坐标系也在不断变换，同一个空间点PW在不同相机坐标系下的坐标也随着相机坐标系的变换而变换。相机的运动包括旋转和平移，可以用矩阵表示为旋转矩阵R和平移向量八将RPM记为T,称为相机的外参数。TPw=P,所以可以由外参矩阵和目标点在相机坐标系下的坐标求得目标点在空间坐标系下的坐标Pw。本实验中，使用棋盘格进行标定，同时使用高斯滤波，用一个模板扫描图像中的每一个像素，模板中心像素点的灰度值用模板内像素的加权平均值替代，平滑滤波，消除高斯噪声，减小深度信息的误差，最后利用重投影方法计算误差。2.4 本章小结本章介绍了Tango手机采集图像RGB和深度信息的原理；根据相机成像原理，利用空间目标点P在空间坐标系、相机坐标系、物理成像平面和像素平面之间坐标的变化求取空间点坐标。其中，为消除透镜带来的成像畸变影响，通过5个畸变系数进行矫正，减小系统误差，同时通过高斯滤波减小随机误差。第三章基于特征点的视觉里程计3.1 视觉里程计视觉里程计Q属于三维重建框架的前端，可根据相邻图像的约束关系粗略估计出相机运动。其实现方法可分为直接法和特征点法。在计算机视觉领域，图像是被当作矩阵处理，若直接利用该矩阵求解位姿变化，计算量过大，难以实现实时性。若将图像中相似的点删除，挑选出具有代表性的点（即特征点），在这些点的基础上进行位姿求解则会大大减少运行时间。鉴于基于特征点法的视觉里程计模块运行稳定，对动态物体和光照不敏感，且方案比较成熟，符合任务要求，本设计选取基于特征点的视觉里程计作为前端实现方法。3.1.1 特征点提取特征点由关键点和描述子构成。关键点是该特征点在图像中的位置，描述子则是一个向量，包含关键点周围像素的信息。目前，基于视觉的RGB-DSLAM技术利用的特征提取算法主要有HarriS角点检测、SIFT（尺度不变特征变换）、SURF（加速鲁棒性特征）、ORB等。其中HaITiS角点检测是在某个点的邻近区域内平滑移动一个窗，在各个方向上求一阶偏导，灰度值变化剧烈的就是角点；SIFTU8特征点提取算法利用尺度空间图像梯度分布特性构建特征描述，由差分高斯查找满足不同尺度下都存在的特征点并通过拟合三维二次函数确定关键点位置；SIFT描述子通过选取以关键点为中心的8*8窗口，再将其划分成4个4*4小窗口，对每个小窗口内的像素梯度值加权处理，由于每个梯度包含8个方向，所以形成4个128维（4*4*8）向量，并选出最大值，使每个关键点对应一个128维的特征向量作为描述子，如图3.1所示。图3-1SIFT特征提取图SIFT特征点提取算法考虑了光照、旋转、尺度等变化，虽然定位准确但带来了极大的计算量，一般仅用于拥有GPU加速的PC端三维重建模式，要想在手机端使用SIFT特征提取算法进行实时三维重建目前不易实现；SUFT特征提取算法是在SIFT算法基础上改进得到的，利用HeSSian行列式金字塔选取极值点作为关键点，通过积分图像和harr特征计算图像卷积，简化对关键点的描述。SUFT算法对噪声和光学畸变有更好的鲁棒性，大大缩减了运行时间。ORB算法是基于FAST角点提取算法和BRIEF特征描述算法改进得到，利用机器学习的三叉树排除伪角点，设定阈值筛选角点，特征点提取速度非常快，但缺乏描述子，因而采用速度极快的BRIEF二进制描述子，ORB算法使整个图像特征提取环节时间大大缩减。相较于SUFT特征提取算法，ORB特征提取算法虽然提取的精度有所下降，但是提取的效率也得到了提高，且对于特征点的匹配来说也更加方便。3.1.2 ORB特征提取算法ORB特征是目前实时性最好的特征，虽然精度上比不上SlFT和SUFT特征，但考虑到手机上的三维重建，可以牺牲部分精度换取高实时性，本设计的特征提取就是采用ORB特征。ORB特征也是由关键点和描述子构成，关键点的选择是通过改进过后的FAST角点法，对关键点的描述则采用BRIEF描述子"。关键点提取过程:从图片中选取一个像素P并设定一个灰度阈值t和数量阈值n,以该像素为中心，半径为3像素，形成一个圆，圆边上覆盖16个像素如图32所示。若这16个像素里有至少n个像素超过了灰度阈值t,则判定该像素点P为关键点。遍历过程利用机器学习的三叉树法快速排除伪角点。对于像素点P,按周边16个像素灰度A与阈值t的关系，将像素分成三类，如式31SP(3-1)d,Ii<Ipt(darker)stIp-tIiIp+t(similar)dtIp+1<Ii(brighter)在用三叉树排除伪角点时，首先检测1,5,9,13四个像素的灰度，若这四个像素中有三个灰度超过了阈值，则将像素点P视为一个关键点，否则直接排除。以FAST角点作为关键点提取算法具有高效性，但由于不具有方向信息，且存在尺度和旋转平移等问题，从而缺乏对应关键点的描述子。针对这方面，ORB特征提取算法中通过构建图像金字塔，在不引进噪声的前提下模糊图像，模拟不同尺度下的图像，对图像进行不同层次的降采样，以获得不同分辨率的图像，并在金字塔的每一层维度上检测角点实现尺度不变性；使用灰度质心法来实现对FAST角点旋转的描述,保证旋转一致性。灰度质心法说是由Ethen提出用于计算图像特征点方向的一种方法。质心是指以像素灰度值为权重的图像重心。对于一个图像块B,它的矩n0可以定义为式3-2。TnPq=WXPXql(X,y),p,q0,1(3.2)xtyEB式中I(x,y)是每个像素的灰度值，通过矩Mpq可以找到灰度质心Cm1Qm01C=H)(3-3)mOOmoo将图像块的质心C和几何中心O连接，得到向量沆，定义特征点方向为m01=arctan)(3-4)mIQ以此角度作为特征点的旋转描述，且具有旋转一致性。上述为角点的常规提取方法，本设计是在手机端运行，对实时性要求较高，因而特征点要保证一定数量的基础上尽可能的覆盖图像。为实现这一要求，将图像均匀划分为M*N个栅格区域，若栅格内没有检测到角点则将其设为不感兴趣区域，并不再考虑此栅格；若栅格内检测到角点，且角点数量小于等于设定的一个阈值i,则将该栅格内的所有角点都作为关键点；若栅格内检测到角点，且角点数量大于阈值i,则利用HarrisCornerDetecctor对关键点排序，选取前i个角点作为关键点。为计算每个关键点对应的描述子，ORB特征提取算法使用BRIEF描述子对每个关键点描述。BRlEF按概率随机挑选关键点附近的两个像素，并用0,1编码表示两像素间的大小关系。这种二进制描述子运算速度非常快，减小内存压力，并且存储也很方便。结合FAST提取关键点使得ORB特征点法的提取速度得到了很大的提高。3.2 特征点匹配特征匹配是三维重建过程中极至关重要的一步，为解决数据间的信息关联问题，将图像与图像或图像与地图间的描述子进行匹配。目前特征匹配算法主要有两个不足之处：一是匹配计算量大，运算慢；二是特征点匹配精度不高，存在误匹配情况。SIFT和SUFT特征点的描述子都是采用计算欧氏距离(35)来找出最佳匹配对，dy)=x-y=一%/(3-5)Ji=I式中%是描述子向量，欧氏距离D(%y)作为两特征点相似度系数，为找到最佳匹配点对需找出图像所有特征点中与待匹配点欧式距离最小点。本设计中ORB特征点的描述子是二进制形式，可以采用最小汉明距离作为最佳匹配对的标准。ORB特征点提取后得到对应的描述子，设两幅图像中待匹配的描述子分别为K1和K2:Kl=XoxX119K?=y。%扬（3-6）两描述子的汉明距离定义为：nZ）（K1，2）=W阳yi（3-7）i=0与欧氏距离一样，D（KI,七）越小，两描述子相似度越高，选择相似度最高的一对作为匹配特征对。汉明距离求相似度使用的是二进制异或，其复杂度远低于求解欧式距离的复杂度，在特征匹配过程有很大优势。本设计采用的就是汉明距离法特征匹配，同时选择使用RANSA算法（一种模型估计算法）对匹配过程中出现的误匹配情况进行剔除，提高匹配的正确率。搜索一副图像中与待匹配特征点相对应的点的搜索算法有很多，其中最简单的是暴力匹配法（BrUteFOrCe穷举法）。这种算法是全局搜索算法，对前一时刻的每个特征点都要通过测量与后一时刻每个特征点描述子之间的汉明距离，取最近的一个作为匹配点，简单直白，但没有用到数据集本身的结构信息，搜索效率低。在特征点数量较多情况下，将这一算法作为手机端的三维重建特征匹配算法显然是不可取的。此时，选择基于ORB特征点的K-D树空间索引和近似查询算法P叫利用数据集的结构信息，不断降维查找，解决高维矢量的检索问题，可以有效提高匹配效率。K-D树是二叉树的扩展，K维树上的每个节点都是一个K维空间点，每一层都可视为一个超平面将空间分成两部分，树的顶节点为一维，下一层节点为另一维，依此类推，且每一维都符合左子树上的数据均小于根节点数据，右子树上的数据均大于根节点数据。三维K-D树如下图33。将ORB特征点构建成K.D树形式，然后按最近邻域搜索，使用二分查找找出K-D树上与待匹配特征点距离最近的特征点。在搜索时使用一个优先队列辅助工具，该队列是以距离递增的顺序搜索节点。同时，若K-D树上某个节点数据在被进行树的遍历时，将它标记为己访问，避免在其它树中被重复访问。这样经过反复遍历与比较就可以得到每个特征点对应的前一刻的最邻近节点，也就是最佳匹配点，实现两幅图像的特征匹配。图3-3三维K-D树红色超平面先将K维空间分成两部分，这是第一维，超平面左侧空间点均小于超平面上的值，右侧空间点均大于超平面上的值。在此基础上绿色超平面划分出第二维，继而蓝色超平面划分出第三维。多维K-D树依次类推，维度的排序是通过各维度上方差的大小比较，每个超平面的选取是按照在该维度上的中位数选取。搭建完K-D树后按二分查找，结合利用数据集本身的结构信息，找出符合最佳匹配的叶子节点，该叶子节点代表的特征点与待匹配特征点在空间坐标系下为同一特征点。3.3 本章小结本章介绍了三维重建的视觉里程计模块中特征点的提取和匹配过程。使用FAST角点和BRIEF描述子作为ORB特征点牺牲了部分精度但大大提高了特征点提取的效率，同时ORB特征点的匹配是使用最小汉明距离查找最佳匹配对，查找过程使用了快速的K-D树搜索算法，整个特征点提取和匹配过程较SIFT和SUFT方法所耗时间大大缩短，同时有利于接下来的后端优化和闭环检测。第四章闭环检测与非线性优化4.1 闭环检测4.1.1 闭环检测的意义经过视觉里程计的初步构建之后，可以得到一个三维场景模型，但该模型存在部分物体重叠现象，这是由于在构建过程仅考虑了相邻时间的关联，尽管有后端的非线性优化，但误差的长期累积会严重影响全局的一致性。第一幅图像与第二幅图像匹配完成后一定会存在一个与真实场景的偏差，不管这个偏差大与小，当第三幅图像进行特征匹配时，是在这个偏差的基础上进行的。当相机重建一周，回到第一幅图像的位置，此时这幅图像中的特征点匹配之后可能和第一次匹配的位置发生了很大的变化，导致同一特征点先后匹配到两个不同的位置，这就是重影的原因。从位姿图上更好的体现出闭环检测的重要性，如图4-1所示。OOO(a)(b)(c)图4-1位姿累积漂移示意图图中a为真实环境下相机位姿图。b为没有闭环检测时累积误差影响下的位姿图，从b图中可以明显看出没有闭环检测时的位姿图与真实位姿偏差较大，且在大规模场景重建或在重建过程为追求重建出每个细节多次出现回环时，产生的漂移会更加剧烈。C为重建过程加入闭环检测模块后的位姿图，比较C图与a图，可以看出重建的位姿图与真实位姿图基本一致。这三个位姿图的变化很好的诠释了闭环检测在三维重建过程的重要意义。经过闭环检测模块，可以有效分辨出之前扫描过程是否到达过目前的场景位置，若到达过则通过约束条件将位姿图优化，降低场景重建的累积误差，实现全局一致性，同时也可以避免场景的重复构建，提高效率，降低处理的时间复杂度。闭环检测的方法一般是计算两图像的相似性系数S(A,B),设定阈值，根据图像的相似性来判断是否是回环。计算S(A,B)不能简单的认为是图像矩阵A减去图像矩阵B再取范数，即S(A,B)=IA-Bo由此求得的相似性系数会受到光照和相机移动的严重影响，即使在同一个位置，当光照强度变化或者稍微偏转一个小角度，S(A,B)都会发生很大的偏差。当然,若将两幅图像进行特征点匹配并设定一个匹配对占比阈值,当超过这个阈值则认为是一个闭环。这种方法是可行的，但因为其利用特征匹配检测闭环会比较费时，在本设计中不易采用。因而本文使用了词袋模型的方法来计算相似性系数S(A,B)从而检测是否闭环。4.1.2 词袋模型词袋模型是将一幅图像用多个特征表示出来。构建K叉树记录每个特征，K叉树的每个叶子节点单词即代表一种特征。对一幅图像，通过树查找可以多个节点表示:A=m*w1+n2*w2+n3*w3(w1,w2,w3是节点，也是不同类的特征，n1,n2,n3是对应特征点的数目。)由于树是事先搭建好的，每个特征对应的节点也是固定的，多以可以将上式简化为矩阵形式A=.,mg。这是最简单的表示方法，没有考虑不同特征的重要性不同，若考虑这点，则要使用TF-IDE(TermFrequency-InverseDocumentFreqUenCy)方法。TF是某一个特征在图像上出现的频率，假设一幅图像有n个特征，其中出现Wi特征的次数为小个，那么Tli(4-1)TFt=nIDF是描述在建立词袋时，某个特征Wi出现的频率，也可以说是区分度，频率越低，区分度越高。n(4-2)(4-3)IDFi=log由4-1和4-2可以求出特征Wi的权重为rji=TFiXIDFi加入特征权重后，计算时就可以简化掉特征点的数量，对于一幅图像的描述也随之变化:(4-4)4=(W11),(W272)(WNMN)=%对于两幅图像分别得到不同的描述以和如,为计算出两幅图像的相似性程度，本设计采用了Ll范数形式求解。N(4-5)1以4+WeI一W人一加i=lS(48)越小，相似度越高。4.2 非线性优化4.2.1 非线性系统的状态估计经典SLAM可以总结为一个运动方程和一个观测方程用于定位和建图:(4-6)(Xk=(->)+k卜=2.NtZNJ=M%以)+以Jj11：2，M该式中&是相机位置也叫做位姿，l是传感器读数(一般为测量运动的传感器),%是路标，ZkJ是观测数据，Wk和IZkj均为噪声项。通过视觉里程计的特征点提取和匹配可以实现在短时间内的地图构建，但是存在噪声带来的误差，较长时间内的误差累计会产生很大的漂移，让构建的模型极不准确。为解决这一问题，不能仅利用之前时刻的状态约束信息来估计，还要考虑之后的状态来估计，找出最可能产生当前观测数据的状态。目前求解状态估计问题的方法可分为两类：一类是基于滤波器的求解方法，如卡尔曼滤波和扩展卡尔曼滤波；一类是基于平滑的方法，如图优化法估计非线性动态系统内部状态22】。基于滤波器的方法在求解过程中仅考虑与前一个状态的关系，没有考虑全局的关联，即便能减少噪声，但没有解决误差累积的问题。另一方面，该类方法在求解非线性系统时是先对系统方程求一阶导将系统线性化，当系统具有较为强烈的非线性时，滤波类方法的效果不是很显著，且有时需要存储协方差矩阵,效率较低。在本设计中，选择了使用基于图优化的优化库g2实现对非线