（地图学与地理信息系统专业论文）增量式真三维重建方法.pdf

增量式真三维垂建方法 摘要 利用三维激光扫描仪获取的距离图像进行室内外场景三维重建的方法越来越受到关 注，已经成为遥感、测绘与计算机科学领域研究的重要课题。本文在研究和分析了传统基 于激光的三维重建方法的基础上，结台北京市学术创新团队计划。三维信息获取与应用处 理技术”和国家自然科学基金“城市三维空间信息一体化建模与表达关键技术研究”等科 研项目，提出了一种增量式的真实场景三维重建方法，论文主要贡献如下： 1 提出了三维激光扫描点云矢量化方法给出了基于投影的三维点集边界提取算法， 证明了边界透视不变性。 2 提出了基于微梯形合并的多边形凸分解的算法，给出了数学证明与推导实现了 增量式三维模型合并。 3 建立了增量式真三维重建方法体系，并对算法的复杂度进行了分析。 4 开发了增量式真三维重建软件，成功应用于室内室外三维激光数据处理中。 本文提出曲增量式真三维重建方法不仅适用于三维激光扫描数据处理，也为其它大型 三维数据处理提供了一种新的思路和方法。 关键字：三维重建、距离图像、增量式、平面分割、边界提取、矢量化、凸分解 2 0 0 7 6 6 增量式真二维重建方法 a b s t r a c t t h em e t h o do f dr e c o n s t r u c t i o ni n s i d e s0 1 o u t s i d e su s i n gt h ed i s t 锄c ci m a g e so b r a i n e d b yt h e3 dl a s e rs c a n n e rh a sg a i n e dm o l ea n dm o r ea t t e n t i o n s i th a sb e c o m et h ei m p o r t a n ta n d a d v a n e l 嘲e c ti nt h ef i d d so f i a o t es a 哦m a p p i n g dc o m p u t e rs e i c n e , e ，i nm yp a l e r , t h e t r a d i t i o n a lm e t h o d so fl a 3 e r3 - dr o c o n s t r u e t i o na f er e s e h e da n da n a l y z e d i na d d i t i o n , t h e r 站i e a t i f i ei t e m sa e o r a b i 皿e d , s u d h8 3o b t l f i i f i n ga r i du s i n gt e c h n i q l a eo f 3 一di a f o r m a t i o t l , f h i e l a i sf i l eb c i j i n gl e a r n i n gi n n o v a t i o ng r o u p , a n dt h ek e yt e c h n i q u e so fi n c o r p o r a t e db u i l d i n ga n d r e p r e s e a l t a t i o no f t h ee i t y3 - ds p a t i a li n f o r m a t i o nw h i c hi st h en a t i o n a ls c i e n c ef u n di t e m ，h a s e d o na b o v e e 瓢冶r c h 鼠t h ei n c r e m e n t a l3 - dr e b u i l d i n gm e t h o di nr e a l9 嘣1 ea 坤p u t t e df o r w a r d t h ec o l l t r i b u f i o n si nt h i sp a p c a a ”s h o w ni 1 5f o l l o w s ： l m v t d 畦z e d m e , h o d a f 3 - d l n s e rs e a n n i n g i s ! 出t t e d f o r w a r c l s y s t e m a t i e a u y , 3 - 1 3 b o r d e r l i n ce x t r a c t i o na r i t h m e t i eb a s e do nt h ed i s t a l j i m a g e si sd i s p l a y e d , a n df i n a l l y , t h e p r o p o s i t i o no f t h ei n v a r i a b i l i t yo f t h eb o r d e r l i n e 脚o c d v ei sp r o v e d ， 2 t h ec o n v e xd e c o m p o s i t i o na r i t h m e t i cb 翘s e do nt h em i c r oe c h e l o nc o m b i n a t i o n 哪 p u t t e df o r w a r da n dt h ep r o v eo ft h em a t h e m a t i cp r o v i d e d , s ot h ei n c r e m e n t a l3 - dr o o d e l c o m b i n n t i o nmr e a l i z e d 3 t l a ei n c r e m e n t a lr e a l3 一dr e c o n s t r u c t i o ns y s t e ma r ep r o d u c e d , a n dt h ec o m p t e x i t y o f t h e a r i t h m e t i cm a n a l y s i z e d 4 t h ei n e r m e n t a lr e a l3 - ds o f l w a 罅a d e v e l o p e d a n ds u c o e s 3 f i l l l yu s e di nt h od i s p o s a i o f t h ei n s i d eo ro u t s i d eo f 3 一d1 a s 盯d a t a m e t h o d o f t h e i n e r e n u m t a lr e a l3 - i ) r c c o n s l l l l c t i o i l i s n o t o n l y u s e d i n t h e d i s p o s a lo f t h e 3 d l a s t i r v 峨m m n gj 由a i t a l s o p r o v i d e sa n e w o r i e n l a l i o n a n d m e | h o d f o r t h e ( 1 l s p o d o f o t h e r l a r 9 83 - d d a t a k e yw o r d s ：3 - d n s t m c 6 0 n ，d i s t a n c ei m a g e s ，i n c r e m e n t a l ，p l a n es e g m e n t a t i o n , b o r d e r l i n ee x l r a c t i o n , v c c t o t i z e , c o n v t td e c o m p o s i t i o n 2 0 0 7 6 - 6i l l 首都师范大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外。本论文不含任何其他个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：羹别邑 日期：口7 p 葛月，汨 首都师范大学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学位论文 并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非赢利 目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据 库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规 定。 学位论文作者签名：垂俐匝 日期：力蝴朔 增量式真二维蓖建方法 1 1 研究背景 第一章引言 三维激光扫描技术因其获取的三维数据精确性以及采集数据手段的日渐成熟已经在 遥感、测绘、建筑、考古、影视制作等领域受到了广泛地关注，其中基于距离图像的三维 建模是整个工作的重要环节。只有通过建模过程才能将获取的离散数据点转化成具有几何 和拓扑意义的事物，因此，本文针对室内室外场景的结构特点，结合北京市学术创新团队 计划“三维信息获取与应用处理技术”和国家自然科学基金“城市三维空间信息一体化建 模与表达关键技术研究”等科研项目的需要，重点研究基于激光扫描数据的三维建模方 法。 1 2 研究现状 仅就三维建模问题前人已经做了大量的工作，主要集中在模型建立、模型绘制、大数 据量的模型绘制、模型的后期处理，以及模型再应用等方面。国内外的研究者在各个方向 分别提出了多种方法。 迄今为止，已经出现了多种三维数据的几何建模的方法。例如：广泛用于工业制造的 基于函数拟合的函数重建方法0 1 ，广泛应用于医学上的基于等值面的m c ( m a c h i n gc u b e ) 算法。而在此基础上 i o p p a 提出了一种具有理论意义上的可用于般性的散乱点表面重 建方法m 。g 1 、l c f i 【和m 咖y 针对距离图像一般需要多视点扫描才能得到完整物体模型的 特点提出一种基于距离图像的网格链接方法”1 。t a r b o x 和g o t i s h l i c h 则利用了八叉树方法 区分单视点中可视和不可视部分，然后利用融合方法来得到多视点距离图像的最终模型 脚。m k r e e d 和p k a l l 则在以上距离图像建模的基础上充分利用室外建筑具平面规则 性的特点，采用先构m e s h 表面，再根据视点方向作拉伸得到每个视点c a d 概念上的实体 模型，然后再合并各视点按上述方法得到的模型，从而得到最终c a d 观点上实体模型。不 过这个方法需要两个前提，首先需要先使用平面剖分的方式获得配准转换矩阵，其次需要 计划好扫描视点位置。当然作者其后的文章中提出了些视点选取自动化的方法”“，以及 2 0 0 7 - 6 - 6 1 增量式真三维重建方法 其它的基于自由变形，人工干预等建模方法| 9 , 1 0 , 1 1 1 。 通过以上三维数据建模的方法能够获得高精度的三维细节模型。这些高度细节模型对 于某些应用来说是需要的和必须的，但是对于有些应用来说则显得多余，并且这样高度细 节的模型对于模型的绘制、存储、和传输带来了压力。所以一些研究者提出了模型简化的 方法，模型简化的思想最早町以追溯到七十年代”“。而近些年来人4 f u 提出了一些更为有 效的模型简化方法“”。 r o s s i g n a ea n db o r r e l 提出了顶点聚类的方法1 1 4 】，k a l v i na n dt a y l o r 提出的区域合并方 法任5 1 ，l o u n s b e r y 等提出了基于小波分解的方法”1 以及由h o p p 目提出的一种迭代收缩边 的化简方法，其先在模型中给每条边付上权值，每次选代按权值顺序删除边及其相关三角 形，即将两个项点简化成了一个顶点。并且这个方法可以做逆操作恢复原来的模型。这个 化简方法降低了模型的传输，存储以及绘制的成本，同时也有利于l o d 的建立”。此后冯 结，查红彬等对p m 算法的改进“”。 1 3 本文的主要工作和论文的组织结构 本文作为托京市学术创新团队计划“三维信息获取与应用处理技术”和国家自然科学 基金“城市三维空间信息一体化建模与表达关键技术研究”等项目的重要组成部分，以基 于三维激光扫描仪系统获取的场景三维点云数据为研究对象，研究基于距离图像的真三维 表面重建的关键技术。 1 3 1 研究目标及研究思路 本文的主要目标是：以激光扫描仪获取的场景距离图像为基础，在较少的人工干预的 情况下完成室内外场景三维重建。整个重建过程将研究对象的特点和获取距离图像的特点 结合起来，降低场景三维重建的计算压力以及减少重建的复杂度。 基于距离图像的三维表面重建的一般方法分配准、融合、建三角网等几个阶段，几个 阶段数据按流的方式顺序处理。由于场景的数据量大、站点多，传统方法在处理场景数据 计算压力大且建模的复杂度较高。降低计算压力和降低建模复杂度，正是本文的重建方法 的出发点。 2 0 0 7 - 6 - 62 增量武真三维重建方法 一般方法计算压力主要来自于在多站点配准合并后的数据处理。一方面是存在大量的 冗余数据，另一方面是由站点合并后的数据量大而带来建模、化简时的计算压力。本文的 思路是将计算压力分摊到各个站点，先对站点独立矢量化然后再将矢量化的结果做凸分解 等处理逐个加入最终模型以达到降低计算压力的目的。这样做的原因是单站点数据量并不 大对单站点做数据处理计算压力小，其次站点合并过程中，合并的是矢量化后的数据， 数据量已经大大减少，其计算的压力远远小于一般方法，同时降低了三维建模的复杂度。 在基于距离图像重建的传统蒙皮方法的问题在于：其一，建立的三角网模型的冗余， 三角面片过多，使得建立后的模型不得不经过模型化简阶段去掉冗余面片来减少数据量； 其二，由于建模过程在站点合并之后，所以在处理合并后的数据时处理的数据源已经失去 了图像关联即图像点间不存在可利用的空间关系如相邻关系，减少了点云数据能被利用 的凡何信息，使得点云数据的处理不得不引入人工几何信息。例如在点云数据的边界提取 中【1 轴4 就人工引入三维边界网格以增加点间相邻的拓扑关系以达到提取得目的。 所以本文将建模放在了单站点中进行。主要原因在于：其一单站点获取的数据是一幅 距离图像，空间点和图像点存在映射关系。利用这种映射关系可以为三维重建提供更多的 几何信息，从而降低建模的复杂度。例如在边界提取过程中，将成熟的图像提取方法应用 到距离图像中来。并且在后文中町以证明图像投影并不改变平面点集内的边界关系；其二， 在本文合并模型的阶段输入数据是经过前期处理的数据，去除了模型中大部分所不需要的 数据，这样避免了模型的冗余面片的出现。例如利用平面内的所有点建立三角面片显然是 无意义的，一个平面的特性只需要平面边界的点即可描述。 本文除了考虑上述提到的计算压力和建模复杂度的问题，同时也考虑到了室内外场景 多平面的特性。所以本文在以上分析和考虑的基础之上提出了一种增量式的三维建模方 法。方法分成两个阶段，第一个阶段是对单站点数据傲矢量化，在这个阶段先对单站点平 面分割，然后提取平面点集的边界，这样就完成了单站点距离图像的矢量化。第二阶段则 是将前一阶段提取出来的矢量数据处理成最终模型。由于在前一个阶段提取出来的边界数 据中有着大量的非凸多边形，在后期绘制与处理的很多工作都是基于凸多边形的，所以需 要将得到的非凸多边形处理成凸多边形。如图l l 所示为本文建模方法流程。 增量式真三维重建方法 再站一自磷瑶嚣湃r i 啦 挝上敏v 蛳 二工二 柠取母穗胁再 髓宣蜘始i 点 = = j 匕= = 疏散f 十， 点 = = 】= 嚣择霰穗年露 = = 二 融台最蒋平晒 镬i ：三多 一一 警 二至童口 图卜1 增量式建模方法流程 由图1 1 可知，在整个流程中的一些主要的关键技术有：单站点距离图像的平面分割， 在同一平面内三维点集的边界提取，多边形的凸分解等。本文的研究工作也是围绕着这些 关键技术来进行的。 1 3 2 主要工作 本文提出了增量式真三维重建方法，并对其关键技术做了详细地分析和讨论提出了其 解决方法。主要的工作如下： 1 对距离图像获取方式、原理、以及获取后的预处理方法做了较全面地分析和讨论。 2 分析和讨论了图像分割的主要方法。采用了基于区域扩张的平面分割方法。并给出 了实验结果 3 分析了二维图像。三维点集的边界提取方法以及各自处理数据的特点，提出了基于 投影的三维点集边界提取方法，同时给出了方法的相关证明和定义 4 分析了多边形凸分解的两种主流方法以及待分解数据的连续性，提出了基于微梯形 的多边形凸分解方法，同时给出了方法的相关证明和定义。 5 分析和讨论了基于距离图像的多站点平面合并方法，并给出了实验结果。 2 咖啊缶 4 增量式真三维重建方法 1 3 3 论文结构 本文主要分为五个部分组成，第一部分是引言，介绍了本文的主要研究思路和研究工 作，给出之所以采取增量式建模方法的原因和方法流程，以及分析了采用这样的方法需要 解决的关键技术。第二部分是介绍距离图像的获取与处理，介绍了距离图像的主要获取方 法和获取原理，并较为全面地讨论了图像的预处理方法。第三部分讨论了单张点距离图像 的矢量化方法，在这部分详细介绍和讨论了研究中采用和提出的矢量化方法，对图像分割， 配准，边界提取等一般方法和本文提出的方法都做了较为详细讨论和介绍，并对方法相关 的命题给出了必要的证明。第四部分讨论了模型建立的最后环节，介绍边界多边形的凸分 解的一般方法和本文提出的方法并给出了必要的证明。最后给出了基于距离的模型合并方 法并给出了实验结果。最后一个部分是讨论与总结，对已完成的工作傲了总结性地分析以 及对目前还存在的问题做了必要讨论和展望。 增量式真三雏重建方法 第二章距离图像获取与预处理 2 1 距离图像 一幅图像就是一个平匿物体，其亮度或色彩距离逐点不同。这种变化在数学上可以表 示成两个空间变量的函数，称为图像函数，表示成，b 力。1 k y ) 表示图像平面在点g ，力 处的值域空间，图像平面的阵列点集仗y ) 构成图像函数的定义域空问。对于灰度图像而 言，g ，力的值域空间表示的是点o ，_ y ) 的灰度值，从而也被称为灰度图像。而对于彩色 ， ” 图像，图像函数的值域空间则是一个有值矢量。如果图像函数的值域空问表示的是图像平 面上所对应景物点的景深，即对应景物点到图像平面的距离，则图像函数b ，_ y ) 被称为 距离图像，记为d k ) ，) 。 在计算机处理时，距离图像d o ，y ) 通常看成是一个整数矩阵tx , y 取整数值- 且 0 j m 一1 , 0 y s n l ，即将图像函数的定义域空间量化成月的一个矩阵空间t 这样 的整数矩阵被称为数字距离图，常记作为d o ) ，其中矩阵的元素称为象素或点。图2 - 2 、 图2 1 显示了普通彩色图和距离图的对照。 图2 - 1 左边为彩色图像，右边为距离图像 7 增量式真三维重建方法 崮2 - 2 左边为彩色图像。右边为跑呙幽像 2 2 距离图像的成像原理 数字图像的成像方式主要分为两类；一类是设备不发出信号的被动成像如摄像机等。 一类是设各发出信号的主动成像，如激光雷达、c t 成像等。两种方式都可以获取距离图 像。这里以激光扫描仪为例，简单说明一下距离图像的成像的几何原理。 激光扫描仪采取扫描方式，在一定的坐标系中( 一般以激光扫描仪的架站点为坐标原 点，平行于扫描面的轴为z 轴，再以右手定则定义z ，y 轴) ，空间中某一点b ，弘z ) 在图像 矩阵中的像点为( f ，力，其激光束方向角度为和，田，点距扫描仪的距离为d 。则空间坐标 与扫描距和方向的关系如下： j=dsin8(2-1) y = d c o s c o s 0( 2 - 2 ) ：= d s i n # c o s 8( 2 - 3 ) 其中，口) 分别表示激光束方向的垂直、水平扫描角，d 为激光扫描仪到空间中点的距离。 其中角度，与图像点o ) 的对应的关系： 口= 岛+ i a 0 ( 2 - 4 ) = 丸+ 弘( 2 5 ) 这里九，岛为扫描起点角度，即图像点( f ，) 都为0 时的初始角度。a c , a 0 则为扫描的步长。 2 m 增量式真三维重建方往 如图2 3 所示错误l 未找到引用源。距离图像的成像原理。 z 图2 - 3 噩离图像的成像原理 2 3 距离图像的获取 当前距离图像的获取方式主要有雷达成像、激光成像、结构光威像等，这里主要介绍 激光获取距离图像以及结构光成像。 2 3 1 激光成像 激光雷达成像主要通过两种方式：一种是扫描成像，另一种是非扫描成像。扫描成像 的方式中，距离数据的获取是依靠测量发射激光脉冲与脉冲回波的间隔时问完成，即 d ：a t f( 2 6 ) 2 c 为光速，整幅图像的获取是通过扫描方式完成的，包括发射激光束扫描及接受显示 系统的扫描。激光成像具有波束窄、波长短等优点，因而具有极高的角分辨能力、距离 分辨能力和速度分辨能力。 2 3 2 结构光成像 结构光成像主要利用结构光投影成像的几何变形来获取距离信息。若将一个已知光平 面投影到景物上。将会形成一个“亮条”，该亮条在投影仅坐标方程为： “+砂+口=d(2-7) 根据投影原理可知，成像空间位置b ，y ) 与空间坐标g ，只：) 的关系如下； ，= 盎 ( 2 - 8 ) 增量式真三维重建方法 ，：l 。 f 一： ( 2 9 ) 其中，为投影仪的焦距。通过以上的三个方程可以求出z ，从而获得距离信息。使用 结构光成像时，若投影平面是一个均匀平面，则得到是一个均匀规则的条纹图像，否则得 到的将是一个不均匀的且带有畸形条纹的图像。 结构光成像的分辨率取决于光平面的宽度，结构光的光平面来自激光器或投影仪。相 对来说，采用激光方式可以得到更细密的光亮条。 2 4 距离图像的预处理 获取的距离图像往往带有噪声。噪声在图像理解以及基于距离图像的三维重建方面都 会发挥负面作用。例如对于基于边缘提取的距离图像分割方法，噪声就是主要的制约方法 效果的因素。所以在获取了距离图像以后，需要对距离图像进行一个去噪声的处理。这种 平滑处理主要坚持两个原则：其一，平滑非边缘区域，其二，保护边缘区域。这种处理主 要包括线性平滑、选择平滑等。 2 4 1 线性平滑 线性平滑基于两个假设： 1 噪声口o ) 是加性的白噪声，其均值为0 ，即整体噪声为0 ，其余图像函数，o ，) 不相 关。印 厶( i ，) = ，( f ，j ) + 目( f ，) ( 2 - 1 0 ) 其中( f ，) 表示为图像点值 2 图像点的周围点与图像点的域值相近。 基于以上的两个假设，线性平滑的主要方法就是用领域内的点的平均值代替该点的 值。用数学方式表达如下： 正2 韶b f ( i ，加面ii 静 ( 2 - 1 1 ) 其中五( f ，) 表示图像点线性平橱后的值。 狮- 6 _ 60 增量式真三维重建方法 通过对于该式进行f 。u r i c r 变换可知，线性滤波器的噪声功率得到下降，为原来的专， 即对噪声有所抑制，但图像值失真现象使得边界变得模糊。 2 4 2 选择平均平滑 选择平均平滑方法都是针对以上线性平滑图像失真的缺点而设计的。线性平滑导致图 像失真的主要原因在于点的域值被领域内点的域值所代替，使得边界模糊图像失真。即 ，变为吉，( f ) 选择平均平滑的思想是：只是部分而不是所有的点都用领域点的平均值来代替原来点 的域值。方式之一就是门域法，即只有平均值大于某个值的时候，才使用平均值代替原值。 即 ( f ，力： 专，( f ，诺| 厂o ，力一专，。1 2 r ( 2 一，2 ) 【f ( i , j )j 2 5 小结 奉章先介绍了距离图像的定义和距离图像的成像原理。接着介绍了距离图像的两种获 取方式：一种是激光扫描的获取方式，另一种是结构光的获取方式，并讨论了两种获取方 式的优缺点鉴于信号处理中噪声处理的必要性和重要性，在最后介绍了处理噪声的两种 方式：线性平滑和菲线性平滑，并比较了两种方式的优缺点。 糟毒五真三维重建方法 第三章三维激光扫描点云矢量化处理 3 。1 距离图像分割 本文的增量式建模方法，距离图像分割是建模的基础，一方面为基于特征的配准提供 特征，另一方面为后续的矢量化和3 d 重建提供低层次的待处理数据集，因此首先讨论图 象分割。 3 1 1 分割 分割就是将图像分成不同的区域，并让不同的区域分别具有不同的含义。例如，距离 图像分割的目标之一就是分割出图像的平面、曲面或者直线等几何特征，即相同区域内的 点都具有某种相同的几何特征，例如在某个平面内的点，任意两点的法向量夹角都是小于 某个阈值。 一般而言，分割有两个目的，第一个1 7 的是将整个图像分割成有效的部分以便进行进 一步的分析。对于距离图像而言，在于给图像空问中离散的无几何意义的阵列式的点集赋 予更高级的几何特性，即为建立除亮度、距离之外的新的图像函数g k y ) 。这个图像函 数的定义域空间仍然是图像空间，而值域空间则是由几何参量组成的矢量空问。 分割的第二个目的是新建图像的组织方式。获取的数字距离图像的存储主要采用二维 数组，进行分割之后将获得更高层次的几何描述所以需要相应的数据结构来表达这样的 描述。 图像分割的方法主要有两类：一类是基于边缘检测的方法，一类是基于区域增长的方 法。 3 1 1 基于边缘检测的分割方法。 基于边缘检测的分割方法主要基于这样的个假设：在同一区域内，特征的变化是平 缓且连续的，两相邻医域边界两侧的特征变化是剧烈的。所以基于边缘检测的分割方法的 思路就是检测出边缘，再将边缘间的区域连通起来，最后将连通的区域提取出来完成分割。 这类方法一般可以分成两个步骤：第一步是对图像做边缘捡测，第二步是按相同的表面类 2 0 0 7 - 6 - 61 3 增量式真三维重建方法 玉3k 吣 0 )0 ) 0 ) 留) ( 6 ) 阶跃边缘( 实际) 0 ) 阶跃边缘的二阶导数 g 矽如力= 篆f + 等， ( 3 - 1 ) 其中梯度的模表示为在点k ) ，) 的方向导数的最大值。即 i 删= 阿两 梯度方法就是用梯度的模作为衡量边缘变化的值。为了便于实现，将姿， 讲 用差分代替即 a = ( f ，) 一，p 一1 ，) ( 3 2 ) 篓分别 ( 3 - 3 ) 增量矗真三维重建办法 a ，f = ，( f ，) 一，( f ，一1 ) ( 3 - 4 ) 则梯度的模简化为： g m 矽( f ，j ) = i a ，州+ i a ，卅 ( 3 5 ) r o b e r t 算子也是基于梯度的分析。只是在计算x , y 方向的偏导数的时候，计算选择 的是对象方向相邻的两像素之差。 由于梯度算子和r o b e r t 算子的计算结果都直接依赖获取的距离值，这两种算子都对 噪声敏感，所以后续的一些算子对此作了改进，加入了去噪声的处理。 在以上边缘提取得基础上，有很多种方法来完成区域提取，例如区域生长、空间聚 类、分裂与合并等。此外也有一些非梯度的基于边缘检测的分割方法。 f a nm e d i o n i ”1 等以四个方向曲率值作为特征，将四个方向上曲率值的极值点和不过 零点作为特征不连续点将这些点连接起来得到对距离图像的分割。 唐四春珊1 等通过局部拟合估计表面、二阶偏导数得到跳跃和尖顶边界，然后对跳跃 边界进行边界连续，最终得到分割结果等。 但是基于边界提取的方法中主要的问题在于噪声的影响和扫描点的不连续性导致的 误提取。 3 1 1 2 基于区域增长的分割方法 基于区域增长的方法是从图象某个位置开始遍历图像中的点。将图像分割成不同的区 域，相同区域内的点具有相似的几何性质。这类方法的优点就是受噪声的影响不大，人们 做了较多研究。 b e s l l 2 ”以每一个点的高斯曲率为特征，分两次分割，先做一个粗分割，然后再利用 二次曲面拟合的方法做区域增长的二次分割，从而得到最后分割的结果。 h o f f m a n f ”l 以6 维向量( 包括行值、列值、距离值、三维的单位法向量) 作为标准， 实现对距离图像的分割。 j i a n g 等人则提出了一种基于扫描线的平面分割的方法。将同一行的点定义成一条扫 描线，将其分段拟合成一组直线段，最后将这些直线段分组且合并成平面区域，从而可以 实现了平面分割。 2 0 0 7 - 6 - 61 5 增量式真三维重建方法 1 s t a m o s 和p k a l l e n j 则利用了b e s l 的思想，将该问题具体应用到了平面分割的 问题当中，从而避免了拟台高斯曲率和二次曲面拟合的复杂性，较为快速简洁地完成了平 面分割。 在本文的讨论中，图像分割主要集中讨论图像的平面分割。做图像的平面分割主要考 虑到以下几个问题：一是场景建筑多平面特点，二是将图像分解成平面后，对于后续的处 理( 如矢量化和建模) 等降低了处理的复杂度，三是大多曲面分割算法复杂度高，且在后 续的建模中建立的是多边形模型，曲面提取意义不大。这里主要讨论距离图像平面分割 3 1 2 距离图像平面分割 距离图像平面分割有两种方法；一种是基于随机h o u g h 变换的方法，一种是基于 b c s l 思想的区域生长的方法。 3 1 2 1 基于随机霍夫( h o u g h ) 变换的分割方法 霍夫( h o u g h ) 变换是从图像中识剐出几何图形的一种重要的方法，其主要愚路是利 用对偶性原理，通过表决的方式来识别出几何图形。 霍夫( h o u g h ) 变换是利用图像的全局性的特点来检测平面的。一般三维空间的平面 方程式为： m + 缈+ 口= d( 3 嘲 但是由于此方程中参数是无界的，所以在霍夫( t i o u 曲) 变换中采用极坐标方程来表 示即为： o o s 勰+ c o s 缈+ c o s y z = do - _ 7 ) 这样参数肛，是有界的。即de ( 0 1 口l p ( o ，l ，e ( o ，) 。其中四个参数中有三 个是独立的，所以我们以口，厉d 构成参数空间。 这样图像空间中任意一点在参数空间中构成余弦曲线。如果在图像空间中的点严格处 于一个平面上，则在参数空间上所有的余弦曲线将交于一点，而这个点便是将图像空间点 拟合平面的参数值。如图3 - 2 所示： 增量式毒三维重建方法 ( b )( c ) 图3 - 2( a ) 为图像点( b ) 为极坐标下图像( c ) 为参数空间下图像 霍夫h o u g h ) 变换的实现过程又可分成两种方式；一种是最直接的实现方式，即标 准霍夫( h o u g h ) 变换，即其将参数空间口，卢，d 量化分解成p p x o 个单元，将每个图像 空间的点( ，) 和口，所有可能取值计算出对应的d 。将计算的结果放到参数空间对应的 格网中，最终统计所有的结果，将格网中值最多的作为图像空闻平面的参数值对。 但是上述方法存在些问题：第一，算法复杂度高，对于m x n 大小的图像其运算 a a o ( 埘v p 2 0 l 第二，分割的精度受到量化步长的影响。 所以对于霍夫( h o u g h ) 变换标准方法的改进是不去遍历所有参数空间的可能值，而 是利用三点决定一个平面的性质，随机在图像中找到三个点，通过三个点的坐标计算出这 三个点决定的平面的平面参数和其平面参数在参数空间中的取值，并累计在对应网格值 中，然后计数最多的网格值就是平面参数。这样就降低了算法的复杂度。 3 1 2 2 基于区域扩张的分割方法 i , s t a m o s 和p i c a i l e n 等人利用了b e s l 的思想，但将分割目标局限于平面，从而得到 2 0 0 7 6 - 61 7 增量式真三维重建方法 了简洁和较为快速的算法。本文也是使用这个方法来做平面分割。 该方法的思路是：把图像中的某一点作为算法开始的种子点，按从左到右、从上到下， 或者其它的顺序逐点开始比较扩张，得到连通的分割区域。该方法主要包括两个步骤：第 一，拟合小平面，计算各点法向量及抛弃不满足条件的点，第二，按同向性和共面性归并 各点，从而得到分割区域。 3 1 22 l 拟合小平面 平面拟合的思路是：通过点的一个k x k 的邻域点拟台出一个小平面，小平面的中心 点为k x k 领域点的质心点，法向量通过最小二乘法拟合出来。 假设在t x t 领域内的点l 的坐标b ，只z ) 构成矢量v i ，拟合小平面质点为m ，拟合法 向量为h ，根据最小二乘法 d 曼( ( v f m ) n r ( 3 - 8 ) o d 的最小值就是小平面的法向量。 号j 入协方差a - 骞舨一m r h 一辨目，可知： d - , t a n ( 3 9 ) 欲使d 最小，根据拉格朗日乘法可知： 兰( d + ( 1 0 一) ) o ( 3 - i o ) 却、 、 “ ；望+ 堕一! 虹! ! ) o 咖硼却 望一加7 0 ；坐知r 砌 一b r 4 j r 似rj r j 知- a n 增量式真三维重建方法 又d n 7 a n d - n 7 a n - 由上式可知，求d 值就是求a 的值，求d 最小值也就是求a 的最小值，也就是求协方 差矩阵a 的最小特征值，相对应的特征向量就是小平面的拟合法向量。这样该问题就转化 成求矩阵a 的最小特征值和最小特征向量。由于矩阵a 是实对称矩阵，可以使用雅柯比变 换经过5 次左右迭代得到星小特征值和最小特征向量，即得到拟合小平面法向量。拟合方 式如图3 - 3 所示： ir r 嫩 i 0 h i - 卅 - 5 一 图3 - 3 拟合小平面 在拟合小平面的法向量后，需要判断拟合的小平面的质量。如果d 的最小值大于某 个门域值晶。，则说明在领域内的并不是一个小平面区域，或者说当前点在t x t 领域内 是一个突出点或者是凹点，所以此时应将得到的点抛弃。 3 1 2 2 2 合并小平面 在拟合完小平面后，接下来的工作就是归并拟合的小平面。所谓归并，就是遍历所有 的点，并逐点判断两点的同向性和共面性。如果同时满足两个条件，则将两点所在的集合 合并起来，否则将建立新的集合。 判断是否归并的两个条件分别是同向性和共面性。 同向性是指两个平面法向一致性的判断，其定义如下： 口一c o s 1 缸。，n 2 )( 3 1 1 ) 如果口小于某个门域值，则认为满足同向性( 其中当1 2 较小时直接用c o s 口来代替避 免求反) 共面性是指两个平面距离的判断，其定义如下： d m a x 0 _ 。n l l ，k 一：i ) ( 3 1 2 ) ：为两点间距离，其意义是两点分别投影到各自平面上的投影点间的距离。当小于 2 0 0 7 6 - 6口 增量式真三维重建方法 某- f 7 域值时则认为满足共面性。 3 1 223 算法步骤 按扫描顺序遍历图像的各点尸； l 如果点p 小平面拟合成功，则转入步骤2 ，否则寻找下一个点，转入步骤l 。 2 如果点) 不属于任何集合，则建立新的集合找到下一个点转入步骤l ，否则转入步 骥3 。 3 分别考察点p 周围三个方向的点尸。 4 如果点，与尸不同时满足同向性和共面性，则继续寻找下一个点，否则转入步骤5 5 如果尸不属于任何集合，则将尸加入p 所在的集合。否则转入步骤6 。 6 合并尸和p 所在的集合。 7 删除点数少于门域值的点。 3 1 3 分割结果 2 0 0 7 6 6 图3 4 大门分割结果一 图3 - 5 大门分割结果二 2 0 增量式真三维重建方法 图弘6 大门分割结果三 图3 - 7 实验室室内分割结果一 图3 _ 8 实验室室内分割结果 图39 实验室室内分割结果三 2 1 增量式真三维重建方法 本文选取了校门和实验室某室作为实验数据，分别做了平面分割的试验。图3 - 4 、图 3 - 5 、图3 - 6 是分别对校门的三个站点的距离图像做的分割结果，数据量分别是3 8 5 0 4 、 4 7 5 4 0 、4 4 1 4 0 个点，计算时问分别是2 5 0 s 、2 6 3 s 、2 5 8 s ；图3 - 7 、图3 - 8 、图3 9 是 分别对实验室的三个站点的距离图像做的分割结果，数据量分别是4 4 2 3 0 、4 6 6 5 2 、4 6 4 7 9 个点，计算时间分别是2 5 8 s 、2 5 2 s 、2 6 2 s 。实验证明，结果可接受。 3 2 距离图像配准 通过激光扫描仪所获取的物体距离图像数据，鉴于观察方向和物体本身形状的限制， 不可能一次得到描述复杂物体的所有距离数据，所以在获取物体完整模型前需要做一个工 作，就是将在不同坐标系下获取的距离图像匹配到同一个坐标系下。距离图像匹配方面已 有大量的研究者们做了研究，一直以来存在两种策略：一种是利用离散特征进行匹配的方 法泌j ，该类方法的优势在于；它可以直接求解刚性变换而不需要一个初始的位置估计， 不足之处则在于对于那些找不弱明显特征的建方显得无能为力。另一种就是著名的i c p 算法【筠】，这类方法需要初始的估计位置，然后从一个视图中选取一定数量的控制点。并 在另外一个视图中找出这些点的近邻点作为对应点，通过对这些对应点问的距离最小化来 求得一个变换，最后不断的迭代该过程，直到满足收敛条件。这个方法的缺点是很容易陷 入局部最小，所以需要在选代前有一个不错的初始估计位置。所以针对这个特点一些研究 人员【2 7 j 对该方法做了一些改进，也有人 篮】提出一个折衷的方法，即通过找到对应的特征 求得一个初始位置，然后根据这个初始位置再使用i c p 迭代求糖的方法 f 3 2 1 经典i c p 算法 c p 算法是距离图像配准的主导性算法，很多算法都是在此基础上做改进或变异的。 该算法思路明确，配准的关键在于找到两个点集合的变换矩阵，而两个点集合对应点间的 变换矩阵就是所求的变换矩阵。所以该问题转换成找到两个点集合间的对应点。i c p 方 法就是通过多次迭代尝试的方法来找到对应点的，该判断依据是前后两次迭代的匹配误差 关系，为d 。一d 。c f ( f 为匹配误差) 或者是迭代次数过高i t 一，其中以为匹配质量 的判断标准，即匹配均方差： 2 0 0 7 - 6 - 6 增量式真二维莺娃方法 钆= 击籼坝l ( 3 - 1 3 ) 所以在i c p 算法中，有三点需要讨论：变换矩阵、最近距离、方法步骤。 变换矩阵 配准可以理解为两个坐标系间的坐标转换。任何坐标变换都可以归纳为两种变换的组 合即旋转变换和平移变换。用数学方式表示为： ( | ： = 协 ( 3 1 4 ) 设旋转四元组表示为i = k 。甄g ：吼r ，则四元组得到的旋转矩阵为： lg ；+ 卉一g ；一菇 2 ( q 。如一q o q j ) 2 ( 吼如+ q o q z ) 1 r = i2 ( q i q 2 + g o q ，) 9 0 2 一g ? + g ；一g ； 2 ( q 2 q ，一q o q l ) l ( 3 1 5 ) l 2 ( q i g ，一g o 吼)2 ( q 2 9 ，+ q o q 【)g ：一g ：一g ；+ g ；l 再设平移向量为云= b 吼吼r ，则变换矩阵可表示为 ；：医i 爿壮1 6 ) p = 嚣j 为操作点集，j ：j 为目标点集，由最小二乘估计知最小估计函数： ，g - 户瓦1 善me 一只瞄一玎 ( 3 7 ) 设点集p 和点集x 的质点分别为瓦和乏，可以通过以下两个方程求出： i = 击篓i p - 砷 z = 击善z p - 9 ) ，= 菇 e i e z 7 - 古粪矧一嚣 仔z 增量式真三维垂建方法 令对称矩阵a 为： a = ，一，7 ( 3 - 2 1 ) 构造对称矩阵 e ( e ，) = r ( 专f ，+ 夕一驴匮，) f ， r ，z ：， 加匹，) 表示为矩阵的迹，i s 表示一个3 3 的单位矩阵。单位向量 云= k 。q 。9 ：如r 为矩阵q 匹，) 的最大的特征值所对应的特征向量，优化的平移向 量为： 一q r = z r ( 一q d 一 ( 3 2 3 ) 这样，该问题从求最小值转换成求姬，) 的最大特征向量。 最近距离 i c p 算法中的最近距离表示的是点到点集的最近距离。设空间中有两点， i = ( 一，咒，毛) 和i = ( 屯，y 2 ，z ，) ，其欧氏距离为 d 石，乏) = 卜= 石j 再瓦j 再丽 ( 3 伽 假设有点数为的集合一，4 = i ”= 1 。 0 。则点到集台4 的距离为 d 咄由。m m i n d ( p ，n 0 ( 3 - 2 5 ) 方法步骤 i c p 方法主要分成四个步骤： 1 计算最近的距离点集； 2 计算最近距离点间的变换矩阵； 3 根据变换矩阵更新点集； 4 计算喀“2 玄善i p 一一丁( 只) i ，当前后两次迭代的点匹配误差( 均方差) 或一j 。 k 时，结束迭代过程，否则转到步骤l 继续迭代： ， 以上步骤中耗时最多的就在第一步，在计算最近距离点集中，其算法复杂度达到 o ( 删其中埘v 分别是两个点集的点数。 增量式真三维童建方法 对于点数较多的配准，这样的数据是不可接受的，由此产生了基于特征的配准。 3 2 2 基于特征的配准 i c p 算法的最大缺点在于该算法容易陷入局部最小，而这个结果是由初始位置迭代的 位置决定的。为了克服这个缺点，有学者提出了基于特征的i c p 算法。该思路是在使用 i c p 方法作迭代时找到两个点集问的同名特征，然后根据同名特征估计出一个初始估计位 置，然后再利用这个初始估计位置作为i c p 算法的初始估计位置进行迭代，从而避免了 陷入局部最小 罗先波捌等人采用先提取特征点，然后找到相似特征点来计算旋转矩阵的办法完成 配准