用于三维物体识别的三维点表示方法研究 31页

'用于三维物体识别的三维点表示方法研究3DPointRepresentationfor3DModel-BasedObjectRecognition数学科学学院计算与应用数学系刘子舜PB09001094蔡锐研究员刘利刚教授二〇一三年六月 中国科学技术大学UniversityofScienceandTechnologyofChina本科毕业论文ADissertationSubmittedfortheBachelor’sDegree用于三维物体识别的三维点表示方法研究3DPointRepresentationfor3DModel-BasedObjectRecognition姓名刘子舜B.S.CandidateZishunLiu导师蔡锐研究员刘利刚教授SupervisorDr.RuiCai,Prof.LigangLiu2013年6月June,2013 致谢我的毕业论文是在微软亚洲研究院的蔡锐研究员和我们学校的刘利刚老师的共同指导下完成的.感谢两位老师的教导！两位老师以其严谨求实的治学态度、高度的敬业精神、孜孜以求的工作作风和大胆创新的进取精神对我产生了重要影响。他们渊博的知识、开阔的视野和敏锐的思维给了我深深的启迪.感谢我的班主任宋立功老师和本科四年来所有的任课老师！感谢母校和研究院提供了无与伦比的学习环境！在此，也感谢所有的同学.在共同的学习中，大家互相帮助，结下了深厚的友谊.特别要感谢同在研究院实习的天津大学的郝强师兄，他的指导让我获益良多.最后，感谢家人的养育之恩，“谁言寸草心，报得三春晖”. 中国科学技术大学本科毕业论文目录致谢i摘要ivAbstractv第一章绪言11.1研究意义与相关工作.........................11.2本文的主要内容和组织形式.....................3第二章基于三维模型的物体识别方法概述42.1局部特征...............................42.2针孔相机模型.............................52.2.1针孔相机模型的基础.....................52.2.2齐次坐标表示的中心投影..................62.2.3像平面的坐标系.......................72.2.4相机的旋转和平移......................72.2.5主轴方向...........................92.2.6小结..............................92.3SFM..................................92.4k-d树.................................92.5姿态估计...............................102.6物体识别的流水线..........................10第三章点表示的改进123.1模型丰富...............................123.1.1相机参数...........................123.1.2亮度..............................133.1.3清晰度.............................14ii 中国科学技术大学本科毕业论文3.2基于聚类方法的点表示........................153.2.1k-means算法.........................153.2.2k-means++算法.......................163.3系统实现...............................16第四章实验184.1实验设计...............................184.2实验结果和分析............................184.3时间和空间的消耗..........................19第五章总结与展望22参考文献24iii 中国科学技术大学本科毕业论文摘要本文提出了一种三维点的表示方法，用来改进基于三维模型的物体识别系统的性能.这种方法首先从训练图像生成多幅人工图像，然后从所有图中提取局部特征描述子，再将每个三维点对应的所有描述子聚类，最后以这个三维点的坐标和所聚得的一系列类的中心来表示这个点.暂时不存在对视角、模糊和光照都具有完全的不变性的局部特征.通过模拟这些条件生成人工图像，可以从中抽取到模型中的点在不同条件下的描述子.当把这些描述子全部装入数据库时，识别系统的精度有了明显提升.为了使系统加速，对每个点的所有描述子进行聚类，并以各类的中心代替原始描述子.与未经模型丰富的基准进行比较，每个点的描述子被保留10个类的中心时系统在不花费更多时间的情况下精度提高了高达4%.关键字:物体识别，局部特征，人工视角，模型丰富，聚类，点表示iv 中国科学技术大学本科毕业论文AbstractThispaperpresentsamethodforimprovingtheperformanceof3dmodel-basedobjectrecognitionbyrepresentingeach3dpointinthemodelsasitscoordinateandaseriesoflocalfeaturedescriptors,ofwhicheachisthecenterofsomeclusterinallofthepoint’sfeaturesextractedfromthetrainingimagesandsyntheticones.Thereisnolocalfeaturethatisfullyinvarianttoviewpoint,blurringandchangeinilluminationexistsforthetimebeing.Bygeneratingsyn-theticimagestosimulatetheseconditions,thefeaturedescriptorsunderdifferenttransformationofthepointsinthemodelareextracted.Theaccuracyoftherecognitionsystemcanbeimproveddefinitelybyloadingthesedescriptorsintothedatabase.Tospeeditupandpreservetheac-curacyatthesametime,thedescriptorsofeachpointisreplacedbythecentersoftheclustersoftherawdescriptors.Comparingtothebaselinewithoutmodelenrichment,therateofrecognitionisimprovedbyupto4%wheneachpointwasdescriptedby10clustercenters,whilethetimecostisnomorethanit.Keywords:ObjectRecognition,LocalFeature,SyntheticView,ModelEnrich-ment,Clustering,PointRepresentationv 中国科学技术大学本科毕业论文第1章绪言1.1研究意义与相关工作计算机视觉是研究如何使机器获得“看”的能力的科学，它包括图像的获取、处理、分析和理解等方面.物体识别是其中一个经典而重要的任务.物体识别，就是在一张图像或一段视频数据中找到某个特定的物体.这是动物视觉的一个基本功能.给计算机或机器人赋予这种能力，是对人工智能的巨大推进.它可以用于机器人设计、自动导航、工业生产控制等领域，也可以用于抽象的信息处理.这些应用又给物体识别提出了更高的要求——计算目标物体的姿态，即它与相机（或摄像机）的相对位置（包括位移和朝向）.之前的学者在物体识别上有相当多的工作，提出了各种各样的方法.这些方法的流程可以概括为训练和测试两部分.训练是指从一个图片集中获取目标物体的信息，这里的图片称为训练图片.这一阶段是离线的，或称线下的.测试是指从一个查询请求（一张图片或视频的一帧，称为测试图片）中找到目标物体.测试的过程也就是完成一次识别的过程.这一过程是线上的，或称在线的.在物体识别引起大家的研究兴趣的初期（20世纪六七十年代），人们重点关注基于几何形状的方法（如参考文献[1]，[2]）.比如根据物体的外轮廓，或者几何构成（将物体描述为球体、柱体等几何体及其组合）.这样的方法有明显的局限，可以处理CAD模型类的简单物体，但对复杂物体效果不好.随着基于内容的图像检索（“以图搜图”）的发展（20世纪九十年代之后），基于外观的三维物体识别发展起来.基于外观的方法按照描述外观所采取的策略可以分成两种（参见参考文献[3]）：局部方法和全局方法.局部方法在训练阶段从训练图片中寻找特征显著的局部区域（比如角、边缘），通过合适的描述子（一般是一个向量）加以描述，在测试阶段从测试图中以相同的方法抽取局部特征描述子，并与训练图片的那些描述子相匹配以判断是否有目标物体出现.与之对应的全局方法，所抽取的特征则是对整个图片的描述（比如对图片的降维处理结果）.全局的特征对于场景识别有较好的效果，但对于物体识别则会因为背景的干扰或其他物体的遮挡而出现问题.基于局部特征的方法有更好的表现.局部特征（localfeature）描述了二维图像中一些关键点的某个小邻域的外观.使用它进行点匹配从而实现物体识别是一个行之有效的方法.SIFT、1 中国科学技术大学本科毕业论文SURF、ORB等局部特征提取算法具有对尺度、旋转、平移、光照等条件的鲁棒性，可以将空间中的某个点在不同条件下的拍摄结果匹配起来.到此为止，仅凭二维（测试图片的局部特征）到二维（训练图片的局部特征）的匹配，我们就可以一定程度上实现物体识别.但是，训练图片的数量总是有限的，不可能遍历所有的视角，而且二维之间的匹配不能满足计算物体姿态的需要.基于三维模型进行二维到三维的匹配则可以解决这一问题（参见参考文献[4]，[5]，[6]，[7]）.三维模型可以由训练图像通过SFM过程得到.在已有三维模型的基础上进行的物体识别就是我们所说的基于三维模型的物体识别.这里的三维模型指的是点云模型（pointcloudmodel），它是一个点的集合，其中每个点的表示由两部分组成：一是它在三维模型中的坐标，二是它的一组来自不同训练图片的局部特征描述子.参与匹配的是二维图像的局部特征，三维结构则用于姿态估计.一方面，三维结构有很大的作用，另一方面，在匹配上起基础性作用的仍是局部特征.因而提高匹配的正确率是提高系统性能的直接手段.尽管局部特征对多种图像变换具有鲁棒性，但在条件改变时仍然会发生一定的变化.而训练图片的数量限制了对这些变化的观测.事先获得不同条件下关键点的局部特征观测实例并存入数据库，有助于提高匹配成功率.这就是对模型进行丰富增强的意义.但是，数据库的增大将不可避免地减慢程序的运行速度.我们必须对这些数据进行压缩，去除冗余实例而保留有代表性的.已知聚类算法是数据去冗的有效方法.我们采用它来对这些实例进行表示，就可以在对效果牺牲不大的情况下提高效率.对模型的丰富增强和聚类表示就是本文的意义所在.基于三维模型的物体识别方法需要多方面的数学工具.局部特征的提取涉及高斯函数、卷积、泰勒展开和梯度，三维模型重建需要使用三维空间的解析几何.在我们的改进中，模型的丰富增强中图像处理的部分要用到卷积和视角变换，利用聚类进行表示使用的是统计学习和数据挖掘的方法，本质上是最小化某个目标函数和计算Voronoi图.广义地讲，物体识别也包括人脸识别、指纹识别等鉴别类的问题，车辆计数等类别检测的问题以及光学字符识别等.不同目的的物体识别所使用的方法有时是相通的，但往往各有其特点，这里不再涉及.我们仅狭义地讨论物体识别，以外观是否相同作为判断识别结果的标准，在此意义下，外观相同的两件物体认为是同一物体，同一物体的不同形态被认为是不同物体，也就是说不考2 中国科学技术大学本科毕业论文虑非刚体（人手、折叠椅等）的识别.1.2本文的主要内容和组织形式全文共分为五章.本章作为绪论，介绍了物体识别的研究意义和相关工作，简要介绍了物体识别方法的分类，最终引出了二维到三维匹配的基于三维点云模型的方法，指出了我们在点表示上进行丰富增强和聚类表示这种改进的意义.接下来第二章将要介绍基于三维模型的物体识别方法的流程，为第三章点表示的改进作铺垫，其中包括了离线处理中的SIFT局部特征提取和三维模型重建，涉及了多视角几何中重要公式的推导.第三章是本文的主要部分，叙述了本项工作的方法和一些实现细节.主要包括两部分：一是模型丰富增强所使用的人工视角的生成、亮度改变和清晰度改变方法；二是模型去冗表示使用的聚类算法.最后给出了系统实现的一些细节.第四章展示了本文方法的实验结果和分析，使用丰富前后的识别成功率和正确匹配数的对比证明了我们的方法的有效性.最后第五章是对本文的总结和对将来工作的展望.3 中国科学技术大学本科毕业论文第2章基于三维模型的物体识别方法概述为了更好地阐述我们的改进方法，必须首先厘清基于局部特征和点云模型的物体识别方法的流水线.在这一章，我们首先介绍所需要的各种算法工具，最后给出整个系统的流水线.2.1局部特征局部特征是一种在不同图片之间寻找点匹配的工具，对物体识别和模型重建都有重要意义.DavidLowe提出的SIFT（Scale-invariantfeaturetransform尺度不变特征变换，相关文献[8]，[9]）是一种出色的局部特征，具有对尺度、平面旋转、平移、噪声、模糊、光照等条件的不变性.由于它所描述的邻域足够小，对视角也有一定的鲁棒性.该项技术受到专利保护，所有权归英属哥伦比亚大学.SIFT局部特征的描述子是一个128维的向量，它描述的是某个特征点周围一个圆形区域的外观.SIFT的提取包括特征点检测和描述子生成两部分，所作用的目标图片是灰度图.第一步特征点检测确定特征点的位置和邻域的尺度（圆形邻域的半径）.这一步对目标图片I(x,y)选取一组不同大小的高斯核G(x,y,kσ)做卷积（参见小节3.1.3），如公式2-1，其中k是代表卷积核尺度大小的变量.L(x,y,kσ)=G(x,y,kσ)∗I(x,y).(2-1)然后对相邻的卷积结果做差分，得到一系列DoG（DifferenceofGaussians）图.这些DoG图中的极值点成为特征点的候选.这些候选点的位置精确到像素，为了得到更确切的坐标，在候选点处做泰勒展开∂DT1∂2DTTD(x)=D+x+xx.∂x2∂x2为了结果的稳定性，还要依据对比度等标准筛选候选点.第二步描述子生成指定邻域的朝向并计算描述子.如图2.1，对于每个特征点，在它对应的L(x,y,kσ)中计算它邻域各点的梯度大小和方向，并以此来给这个特征点指定朝向.然后计算描述子，将特征点的邻域划分成4×4=16个方4 中国科学技术大学本科毕业论文图2.1:SIFT局部特征：（a）图像中某个特征点的邻域；（b）将邻域分为16个方块，计算每个方块中各点的梯度；（c）统计每个方块中各点梯度的分布.i块，在每个方块中计算其中各点的梯度，统计这些梯度在{π:i=0,1,...,7}4这8个方向上的分布（histogram），写成一个8维向量.这16个8维向量，共同128维.最后把这个128维的向量归一化为L2模为512的向量，就完成了整个提取过程.实践中，SIFT特征描述子以长为128的无符号字符（unsignedchar）数组表示.SIFT局部特征匹配时，以L2模度量两个描述子之间的距离，距离越小说明这两个区域的外观越接近，它们越有可能对应空间中的同一个点.2.2针孔相机模型相机是将三维世界投影成二维图像的设备.相机模型用投影矩阵的数学语言刻画相机的性质.针孔相机（pinholecamera）是其中最简单的一种，而且能够满足我们这里的需要.2.2.1针孔相机模型的基础考虑三维空间到二维平面的中心投影.以其投影中心建立三维空间的正交坐标系，并设平面z=f为像平面.在针孔相机模型中，对于空间中一点X=(x,y,z)T，它与投影中心的连线交像平面于一点，该点即X的像.如图2.2所示.由三角形的相似可以得到，(x,y,z)T被映射到(fx/z,fy/z,f)T.在5 中国科学技术大学本科毕业论文像平面上建立合适的坐标系，可以有TT(X,Y,Z)7→(fX/Z,fY/Z)(2-2)这就刻画了一个从三维欧式空间R3到二维欧式空间R2的映射.该模型中，像平面又称为焦平面，投影中心称为相机中心或光心.像平面的法线中经过相机中心的那一条称为主轴或主光轴，它与像平面的交点称为主点.图2.2:针孔相机模型的几何2.2.2齐次坐标表示的中心投影使用齐次坐标（homogeneouscoordinates，定义见参考文献[10]第2页）可以使中心投影的表达十分简洁.当三维空间和像平面的点都以齐次坐标表示时，如公式2-2所述的投影可以用矩阵乘法表示为XXfXf0YY7→fY=f0.(2-3)ZZZ1011上式中的投影矩阵也可写为diag(f,f,1)[I|0]，其中diag(f,f,1)是一个对角阵，[I|0]是一个分块矩阵，包括一个单位阵和一个零列向量.引入符号X表示三维空间中点的齐次坐标四元组，x表示像点的齐次坐标三元组，P表示3×4的相机投影矩阵，那么公式2-3可以简写为x=PX,其中P=diag(f,f,1)[I|0].6 中国科学技术大学本科毕业论文2.2.3像平面的坐标系上文中我们选取像平面的坐标系时，假设其原点为相机的主点，而事实上并不总是如此.实际应用中，我们选取照片的一角为坐标原点以便整张图片位于坐标系的第一象限.因此，对于一般的情况，公式2-2的映射应该写为TT(X,Y,Z)7→(fX/Z+px,fY/Z+py),1其中(p,p)T是主点的坐标.应用中p、p分别是图片宽度和高度的.这样，xyxy2公式2-3用齐次坐标表示，应为XXfX+Zpxfpx0YY7→fY+Zpy=fpy0.(2-4)ZZZ1011现在，记fpxK=fpy(2-5)1则公式2-4可以简写为x=K[I|0]Xcam.(2-6)矩阵K称为相机标定矩阵.这里我们把(X,Y,Z,1)T记为X以强调这里的cam欧氏坐标系是依据相机选取的，也就是以相机中心为原点，主轴为z轴且z轴正方向指向主点.这个特殊的坐标系称为相机坐标系（简称相机系）.2.2.4相机的旋转和平移一般情况下，三维空间中点的坐标是在独立于任何相机的标架中表达的，我们称之为世界坐标系（简称世界系）.这两个正交坐标系之间相差一个旋转和一个平移.如图2.3对于空间中的一点，用Xe表示它在世界系中的非齐次坐标（三元组），用Xecam表示它在相机系中的非齐次坐标，则Xecam=R(Xe−Ce),(2-7)7 中国科学技术大学本科毕业论文图2.3:针孔相机模型的几何其中Ce是相机中心在世界系中的坐标，R是一个3×3的表示相机系朝向的旋转矩阵（R是正交阵，有R−1=RT）.用齐次坐标表达，X[][]R−RCeYR−RCeXcam==X(2-8)01Z011与公式2-6合并，则有x=KR[I|−Ce]X.(2-9)这就给出了一个一般的针孔相机模型的投影映射.可以看到，P=KR[I|−Ce]有9个自由度：K有3个（f，px和py），R有3个，Ce也有3个.其中，K所包含的参数由相机本身决定，称为相机的内参数，R和Ce的参数与相机朝向和位置有关，称为相机的外参数.有时候把投影写成Xecam=RXe+t，其中t=−RCe，则投影矩阵可以简写为P=K[R|t].8 中国科学技术大学本科毕业论文2.2.5主轴方向当旋转矩阵已知时，可以得到主轴方向的坐标.记主轴的单位方向向量在世界系中为⃗p（非齐次坐标），在相机系中为⃗p，则⃗p=(0,0,1)T，于是，camcam由公式2-7，⃗pcam=R⃗p，进一步推出00⃗p=R−10=RT0=RT的第3列=(R的第3行)T,(2-10)11即主轴的方向向量在世界系中为旋转矩阵的第3行.2.2.6小结以上给出了针孔相机模型的投影矩阵的相关理论，对于已知内参数的相机，当已知投影矩阵时，可以推导出它的位置和朝向；当已知相机位置和主轴方向时，可以得到所有对应的投影矩阵（并不唯一，因为主轴方向仅提供了相机朝向的3个自由度中的2个）.2.3SFMSFM（structurefrommotion，从运动回复结构），是一个从一组二维图像重建出三维结构的过程.它本质上是求解同一点在不同图片中的投影所约束的线性方程组.极几何（epipolargeometry）为这一过程提供了理论依据，这里从略.对于一组针对同一物体（或场景）的视角不同的图像输入，SFM过程的输出为物体（或场景）的三维点云模型，同时估计出相机的参数.2.4k-d树测试阶段的的局部特征匹配，是对每一个查询请求到数据库中查找最近邻（对于SIFT是L2模意义下的），最显然的方法是进行线性的查找，即遍历数据库中所有的描述子，逐一计算与查询请求的距离.当数据库足够大时这是无9 中国科学技术大学本科毕业论文法接受的，k-d树（k-dtree，k-dimensionaltree）是一种用于近邻查找的高效数据结构.可参见参考文献[11]的第3章.k-d树将k维空间中的实例点进行存储以便快速检索.它是一种二叉树，构建k-d树的过程相当于不断用垂直于坐标轴的超平面切分k维空间，构造成一系列k维超矩形区域.k-d树的每个结点对应于一个k维超矩形区域.这一过程可以递归地实现.2.5姿态估计RANSAC（RANdomSAmpleConsensus，参考文献[12]）是一种模型参数估计的迭代算法.对于包含噪声的数据有较好的效果.由于二维到三维的点匹配中存在不正确的情况，所以选择RANSAC算法进行姿态估计.RANSAC算法的本质在于反复进行随机取样，直到样本估计出的模型参数可以在数据中找到足够多的一致点.如图2.4，要估计出数据中蕴含的那条直线，左图以最小二乘法拟合，受噪声的影响得到的结果不符合预期.右图中展示了RANSAC得到的符合要求的结果.图2.4:RANSAC与最小二乘法对比（右图为RANSAC）2.6物体识别的流水线整个系统分为线上和线下两个部分.10 中国科学技术大学本科毕业论文线下部分主要是从训练图集重建三维模型.首先对每张训练图提取局部特征，然后由SFM系统进行匹配和重建.得到的点云模型中每个点由一个三维坐标和一系列来自不同训练图的局部特征描述子所表示.线上部分首先将所有目标物体的三维模型装入内存，并对所有模型的所有局部特征描述子建立k-d树.当有测试图输入时，对测试图提取局部特征并在k-d树中查找它们的最近邻，当匹配达到设定的阈值时认为找到目标物体，然后对这些包含噪声的二维到三维的点对匹配使用RANSAC算法进行姿态估计，在得到物体姿态的同时也可以判断出每对匹配正确与否.本文对系统的改进在于线下部分重建三维模型后对其进行丰富增强，并对每个点的所有描述子进行聚类表示，详见下一章.11 中国科学技术大学本科毕业论文第3章点表示的改进为了提升识别正确率，我们希望获得关键点的更多局部特征描述子观测实例.为了保证系统速度，我们希望用尽量少的实例有效地表示所有数据.本章阐述了这一想法的实现，分为模型丰富和聚类表示两部分.3.1模型丰富为了得到更多的描述子实例，我们先对图像做变换，然后提取特征，再将它们映射到原图，得到各个关键点的更多观测实例，完成对模型的丰富扩充.图像变换从相机参数、亮度和清晰度三个方面进行.3.1.1相机参数针孔相机模型有9个相互独立的参数：3个内参数（构成矩阵K）和6个外参数.内参数矩阵K总是可逆的，因而理论上由一张精度足够高、范围足够大的图片就可以模拟出相同外参数下任意不同内参数的图像.而外参数的模拟则较为复杂.对于一般的三维物体，不同相机位置得到的图像不能相互变换得到.这是由于视差现象的存在，如图3.1，相机在C得到的图像记为I，C′处得到的为I′，则I中只有三维世界中点x的像而没有x的像，而I′可以同时出现了12x和x，因而I不可能变换I′，同理，I′也不能变换到I.12另一方面，如果已知内参数，相同相机位置下不同相机朝向的图像之间可以相互生成（假设原始图像精度和范围足够）.它的理论支持在于，当相机中心都是Ce时，对应于相机朝向Ri和R2的投影矩阵分别是Pi=KiRi[I|−Ce]，−1−1i=1,2.若xi是Pi的像，则x2=K2R2R1K1x1，这就建立了两幅图之间的一一对应，我们称−1−1H=K2R2R1K1为单应矩阵.求解两个视角之间的单应矩阵然后作用于图像，即可实现视角变换.在实现的过程中，人工视角的选取是在球面上均匀取点作为主轴方向来产生不同视角的图像.包含的正十二面体细分网格的顶点.由主轴方向计算投影矩阵的算法已经在小节2.2.5中给出.12 中国科学技术大学本科毕业论文图3.1:视差我们取了不同的相机焦距以产生不同尺度的图像，3.1.2亮度为了模拟不同亮度条件下，我们把RGB色彩空间表达的图像转到HSL色彩空间，然后通过调整L值实现亮度变换.HSL色彩空间是对RGB的一种符合人类直观感知表述，其中H指色相（hue），S指饱和度（saturation），L指亮度（lightness）.下面给出HSL和RGB相互转化的公式.以(r,g,b)表示一个颜色的红、绿和蓝坐标，它们的值是在0到1之间的实数.设max为r，g和b中的最大者，min为最小者.(h,s,l)是HSL空间中的坐标，其中s,l∈[0,1]，h∈[0,360◦).下面三个式子给出了把(r,g,b)转换为(h,s,l)的公式，0◦,若max=min◦g−b60×,若max=r且g≥bmax−min1.h=60◦×g−b+360◦,若max=r且g12−(max+min)2−2l2h把(h,s,l)转换为(r,g,b)的公式如下，首先，令hk=，把h换算到360[0,1)内，然后计算中间变量{l×(l+s),若l<1q=2,p=2l−ql+s−l×s,若l≥1211tR=hk+,tG=hk,tB=hk−33最后对C∈{R,G,B}分别执行如下三步1.若tC<0,tC←tC+1.02.若tC>1,tC←tC−1.0p+(q−p)×6×t,若t<1CC611q,若≤tC<3.Color=62Cp+(q−p)×6×(2−t),若1≤t<23C2C3p,其它情况(ColorR,ColorG,ColorB)就是所求的(r,g,b)值.3.1.3清晰度我们认为训练图像已足够清晰，因而不再做提高清晰度的锐化处理，而只进行模糊，要模拟现实中可能出现的相机不稳定或对焦问题导致的图像模糊，可以使用高斯模糊.高斯模糊是使用高斯函数来计算像素变换的一种图像滤波器.二维的高斯函数形如221−x+yG(x,y)=e22.2πσ214 中国科学技术大学本科毕业论文它是二维高斯分布的分布函数.服从这个分布的数值构成了一个卷积矩阵用来作用于原始图像.每个像素的新值是它的邻域的加权平均，作用在该像素的原值上的权值最大，理它越远则权值越小.这样的结果是高斯模糊比均值滤波等均一性的方法更多地保持了边界信息.理论上，高斯函数在每一点的取值都是正数，这就意味着计算每一像素的新值时整张图片都要参与计算.而实际操作中使用的是高斯函数的一个离散逼近，3σ以外的数值足够小而被设为零，超过此范围的像素的影响忽略不计.因此我们只计算一个维度为⌈6σ⌉×⌈6σ⌉（其中⌈·⌉是上取整函数）的卷积矩阵.关于人工模糊（artificialblur），参考文献[13]有更详尽的讨论，我们这里仅采用了高斯模糊的方法.3.2基于聚类方法的点表示在上一节中，我们得到了足够多的描述子实例，把它们全部装入数据库用于实时的线上物体识别在时间和空间上都是不可行的.而且，这些数据中会存在某些实例相距非常近，只需要保留它们之一即可代表全部，全部保留也是不必要的.因而我们需要一种去除冗余的算法来解决这一问题.这一问题，用聚类的语言可以描述为：对于一个点的所有描述子，怎样把它们分成几类，使得其中每一类都有一个代表能够很好地表示这个类中的所有描述子.做到了这一点，就可以只将每一类的代表装入数据库参与匹配.k-means算法是聚类的一个有效算法，给定要聚出的类数k，就可以获得每个类的代表元.3.2.1k-means算法k-means算法的结果是把数据集分割成Voronoi图.具体步骤见算法3.1.算法的目标是使目标函数最小化，即求∑k∑2argmin∥xj−µi∥,Si=1xj∈Si其中µi是Si的平均值.由算法可以看出，它的性能很大程度上依赖于初始中心的选取，但选取最好的初始中心是一个NP-hard问题.为k-means++算法提供了一种初始中心选取的有效策略.15 中国科学技术大学本科毕业论文input:所有n个数据点x1,x2,...xn和要分成的类数koutput:k个类的代表元和这个类所包含的数据点1适当选择k个类的初始中心;2repeat3对任意一样本，求其到k个中心的距离，将其归类到距离最短的中心所在的类;4利用平均值更新该类的中心值;5until聚类中心保持不变;算法3.1:k-means聚类3.2.2k-means++算法DavidArthur和SergeiVassilvitskii提出了k-means++算法来近似地解决k-means中初始中心选择的问题（参考文献[14]）.具体步骤见算法3.2.在确定了初始中心之后，聚类的算法与k-means相同.input:所有n个数据点X={x1,x2,...xn}output:n个数据点中可以作为起始中心的k个C={xi1,xi2,...,xik}1在X中等概率地随机选取一个数据点作为中心xi;12forj=2到kdo3随机选择一个新点做为一个新的中心xi，随机选取服从的分布是，jx被选中的概率与D(x)2成正比;mm4end5return{xi1,xi2,...,xik}算法3.2:k-means++起始中心选取3.3系统实现在系统的实现中，我们使用了许多学者提供的工具.SIFT特征提取使用的是其作者，英属哥伦比亚大学的DavidLowe教授提供的可执行文件.三维模型重建使用的是华盛顿大学的ChangchangWu实现的VisualSFM系统.人工视16 中国科学技术大学本科毕业论文角选取使用的是开源工具MeshLab中的相关模块.图像处理和聚类算法使用的是WillowGarage公司维护的函数库OpenCV.在此谨向这些工具的贡献者致谢.17 中国科学技术大学本科毕业论文第4章实验4.1实验设计我们设计了如下的实验来评价模型丰富增强和聚类表示对识别效果的影响.对每个物体分别进行单独识别.每个物体大概使用510张测试图像，每张图像都确实含有目标物体.对识别结果的评价有两个指标：一是在测试图集中识别成功的百分比，以成功找到目标物体的测试图数量除以该物体总的测试图数量得到；二是平均每张测试图获得的正确匹配的数量，以所有测试图获得的总的正确匹配的数量除以测试图数量得到，越多的正确匹配表明越好的性能.由于条件的限制，测试集是和训练集在相同环境下得到的，为了模拟真实的情况，我们对测试图进行了随机的变换，包括亮度、清晰度、视角等.设对于物体O，它的点云模型包含点{p1,p2,...,pn}，点pi有描述子D={d,d,...,d}，丰富后的结果为D′={d′,d′,...,d′}，则实验效果ii1i2isiii1i2iti的基准是未经增强的模型的识别效果，即对每个点pi，使用Di进行识别.我们对k-means算法取不同的k值，对聚类结果测试识别效果.为了对比，对丰富前后的模型的每个点的描述子D和D′都进行相同k取值的聚类.但是，Diii中描述子的数量可能不足k，这时就直接保留所有的描述子.也就是说，类数表明了每个点至多保留多少描述子.由于D′过于庞大，为了避免系统效率低下，i我们最多保留20个类.4.2实验结果和分析我们进行了大量物体的测试，以其中5个为例进行讨论.表格分为两栏，对比对模型进行丰富前后的情况.每组数据包含识别成功率百分比和平均正确匹配数两项（具体含义见上一小节）.识别成功率直接表示了系统对该物体识别的效果.平均正确匹配数的绝对数值不能进行物体之间的比较.因为它受物体本身外观上局部特征多少的影响.每个物体的测试结果的数据包含基准和对照两部分.基准是由丰富前的所有描述子（完全保留，不做聚类）能做到的最好效果.对照包含5组，分别对应了k={1,3,5,10,20}的情况.18 中国科学技术大学本科毕业论文表4.1:#1物体识别结果丰富前丰富后类数成功率（%）平均正确匹配数成功率（%）平均正确匹配数（未聚类）100.0070.9198.8451.599.6153.4399.6163.3100.0067.1599.8166.4100.0071.310100.0069.1100.0075.220100.0070.4100.0077.8如表4.1和表4.2，这两个物体识别成功率的基准已经足够好，达到100%，说明这是两个容易识别的物体.但从平均匹配数仍能看到我们的方法对系统性能的改进.提高正确匹配数有助于提高RANSAC算法的效率，对姿态估计有很大帮助.成功率和匹配数中超过基准的数据已经加粗标示.如表4.3和表4.4，这两个物体识别成功率的基准较低，说明这是两个物体不容易识别.我们的结果不仅提高了平均匹配数，而且提高了识别的成功率，两个物体最好情况的提高幅度达到4%.如表4.5，物体#5代表了居中的情况，由于测试图比较容易，系统基准能够超过达到99%的正确率，在我们的改进后可以达到100%，而平均匹配数也有所提高.从实验数据中我们断言，当保留相同的类数代表时，丰富后的方法总是好于丰富前的方法.当保留的类数达到10时，系统的识别率和平均正确匹配数总是超过基准情况.4.3时间和空间的消耗方法的内存消耗由数据库的规模（也就是描述子实例的数量）直接决定，粗略来说，时间的消耗也是和数据库的规模正相关的，但是由于k-d树的特殊结构，这一规律并不明显.对于本实验，k取1和20两种情况处理每张测试图后者比前者多用的时间总是低于0.004秒.19 中国科学技术大学本科毕业论文表4.2:#2物体识别结果丰富前丰富后类数成功率（%）平均正确匹配数成功率（%）平均正确匹配数（未聚类）100.0067.7199.7943.6100.0041.73100.0058.9100.0057.85100.0062.9100.0063.010100.0065.6100.0068.620100.0067.0100.0072.1表4.3:#3物体识别结果丰富前丰富后类数成功率（%）平均正确匹配数成功率（%）平均正确匹配数（未聚类）92.4941.6184.0127.887.6927.9389.6035.592.8736.4589.9837.993.0639.01091.5239.995.3841.72091.5241.196.5343.7表4.4:#4物体识别结果丰富前丰富后类数成功率（%）平均正确匹配数成功率（%）平均正确匹配数（未聚类）92.7744.5180.8631.385.1631.5388.4839.192.5839.8590.4341.294.7342.31090.6343.096.2845.02091.9943.996.8846.520 中国科学技术大学本科毕业论文表4.5:#5物体识别结果丰富前丰富后类数成功率（%）平均正确匹配数成功率（%）平均正确匹配数（未聚类）99.2648.3193.0430.697.6831.2397.6840.299.6141.3598.8443.399.4244.51098.2645.7100.0048.42099.0347.4100.0050.821 中国科学技术大学本科毕业论文第5章总结与展望在上一章中我们已经看到，对模型的丰富增强使得匹配的成功率大大提高.在经过聚类表示，可以在节省内存的情况下得到比原有方法更好的效果.在系统的实现中，数学工具起了很大的作用.局部特征的提取中高斯卷积的查分实现了局部特征的尺度不变，泰勒展开实现了特征点的精确定位.三维模型重建中三维空间的初等解析几何发挥到了极致.模型的拟合的RANSAC算法是概率算法的一个代表性实例.在模型的丰富增强中，高斯卷积保住实现了图像模糊，矩阵变换为视角变换提供了依据，k-means聚类算法体现了计算几何中Voronoi图的作用.在物体识别这一计算机视觉课题中无处不见数学应用之美.我们的项目还有一些可改进之处.在本文的实现中，我们的聚类总是事先给定最后保留的类的数量，但一个显然的事实是，有的局部特征随着外界条件的变化而产生的改变大，有的则改变小.应该为前者保留更多的实例而为后者保留较少的实例，以节省内存并提高时间效率.这就需要自适应地选择聚类的类别个数.一个更长远的想法是，局部特征随着视角的变化而变化，那么如果能够回归出两者之间的关系，则可以仅从一个二维与三维的匹配出发估计物体与相机的相对位置.这样，对于一张图中的大量匹配，可以从中剔除与其它矛盾的离群点，从而减少RANSAC的迭代次数，提高效率.但是这一点的难度较大，有待进一步研究.22 中国科学技术大学本科毕业论文参考文献[1]LawrenceG.Roberts.Machineperceptionofthree-dimensionalsolids.Tech-nicalreport,DTICDocument,1963.[2]RamakantNevatiaandThomasO.Binford.Descriptionandrecognitionofcurvedobjects.ArtificialIntelligence,8(1):77–98,1977.[3]PeterM.RothandMartinWinter.Surveyofappearance-basedmethodsforobjectrecognition.2008.[4]YunpengLi,NoahSnavely,andDanielP.Huttenlocher.Locationrecognitionusingprioritizedfeaturematching.InComputerVision–ECCV2010,pages791–804.Springer,2010.[5]TorstenSattler,BastianLeibe,andLeifKobbelt.Fastimage-basedlocal-izationusingdirect2d-to-3dmatching.InComputerVision(ICCV),2011IEEEInternationalConferenceon,pages667–674.IEEE,2011.[6]TorstenSattler,BastianLeibe,andLeifKobbelt.Improvingimage-basedlocalizationbyactivecorrespondencesearch.InComputerVision–ECCV2012,pages752–765.Springer,2012.[7]TorstenSattler,TobiasWeyand,BastianLeibe,andLeifKobbelt.Imageretrievalforimage-basedlocalizationrevisited.2012.[8]DavidGLowe.Objectrecognitionfromlocalscale-invariantfeatures.InComputervision,1999.TheproceedingsoftheseventhIEEEinternationalconferenceon,volume2,pages1150–1157.Ieee,1999.[9]DavidGLowe.Distinctiveimagefeaturesfromscale-invariantkeypoints.Internationaljournalofcomputervision,60(2):91–110,2004.[10]R.I.HartleyandA.Zisserman.MultipleViewGeometryinComputerVision.CambridgeUniversityPress,ISBN:0521540518,secondedition,2004.23 中国科学技术大学本科毕业论文[11]李航.统计学习方法.清华大学出版社，ISBN:978-7-302-27595-4,北京,2012.[12]MartinAFischlerandRobertCBolles.Randomsampleconsensus:aparadigmformodelfittingwithapplicationstoimageanalysisandauto-matedcartography.CommunicationsoftheACM,24(6):381–395,1981.[13]J.R.Parker.AlgorithmsforImageProcessingandComputerVision.WileyPublishing,2ndedition,2010.ISBN0470643854,9780470643853.[14]DavidArthurandSergeiVassilvitskii.k-means++:Theadvantagesofcare-fulseeding.InProceedingsoftheeighteenthannualACM-SIAMsymposiumonDiscretealgorithms,pages1027–1035.SocietyforIndustrialandAppliedMathematics,2007.24'