一种基于立体匹配的建筑物三维重建方法_图文

1、1引言随着信息技术的高速发展,立体视觉技术已经广泛应用于医学诊断,工业检测,机器人视觉,航空测绘等领域中。双目立体视觉作为一种被动式的三维测距技术,以其实现方式灵活、对环境要求低、价格低廉等优点而广受重视,旨在模拟人类双眼识别场景三维信息的机理,从两个角度获取场景的二维图像,再根据建立图像之间的匹配关系重建三维模型。双目立体视觉主要包括摄像机标定,立体匹配,三维重建三个步骤,其中立体匹配是核心环节。立体匹配的目的是找出两幅图像中像素点的对应关系,分为局部算法和全局算法。常用的局部算法有区域相关算法,自适应窗口算法,区域增长算法等1,局部算法以视差连续性约束为前提,利用像素邻域窗口内的灰度信息计

2、算待匹配点与候选匹配点的相关度,在无纹理和深度不连续的区域容易产生误匹配。全局算法将平滑性代价加入匹配代价的计算中,使匹配转化为能量函数的全局最优过程,主要包括图割算法2,置信度传播算法3和动态规划算法4。全局算法可以得到比较理想的匹配结果,但计算量庞大,动态规划算法是全局算法中实时性比较高的一种算法。本文结合建筑物这一特定的应用环境,提出了一种基于控制点的分段动态规划算法,利用控制点的匹配结果指导稠密匹配,改善了动态规划算法应用于建筑物三维重建所造成的条状瑕疵。实验结果证明,该算法可以得到光滑逼真的建筑物三维点云模型。2动态规划算法局部匹配算法是基于独立点的匹配算法,没有利用像素之间的视差相

3、关信息,对匹配的准确性有很大的负面影响。全局最优算法引入全局搜索策略,将平滑性约束加入匹配代价的计算中,在全局范围内作能量优化,能量函数一般为:(data smoothE d E d E d=+(1一种基于立体匹配的建筑物三维重建方法曹云云1,达飞鹏1,隋宜桓11.东南大学自动化研究所, 南京210096E-mail: cyy08005301摘要: 针对传统动态规划算法固有的条状瑕疵问题,提出了一种改进的基于立体匹配的三维建筑物重建方法。该算法利用Canny算子和Harris算子提取建筑物的角点和边缘点作为稠密匹配的控制点。通过控制点分段扫描线进行动态规划,同时采用归一化互相关系数和一种类似线

4、性插值法相结合的匹配代价计算法,进一步提高了算法的实时性。实验结果证明,本文算法能够产生光滑逼真的建筑物三维点云模型。关键词: 三维建筑物重建,立体匹配,动态规划,控制点提取A Stereo Matching based 3D Building Reconstruction AlgorithmYunyun Cao1, Feipeng Da1, Yihuan Sui11.Research Institute of Automation, Southeast University, Nanjing 210096, ChinaE-mail: cyy08005301Abstract: In order

5、 to solve the well-known streaking effects of dynamic programming, an improved algorithm based on stereo matching technology is proposed to generate 3D building model. This algorithm obtains the feature points of the building by Harris corner detector and Canny edge detector to segment the scan line

6、s of dynamic programming. Moreover, a linearly interpolated dissimilarity measure is introduced into the cost computation which further improves the matching speed. The experimental results show that the proposed algorithm can produce smooth and dense 3D points cloud model of building.Key Words: 3D

7、reconstruction of building, stereo matching, dynamic programming, control-points其中,(data E d 是全局匹配代价,而(smooth E d 是相邻像素点间的平滑代价,根据像素之间的视差相关性,对相邻像素的不同视差施以惩罚,为权重系数,用于调整(data E d 与(smooth E d 之间的权重比例。 全局最优算法按照如图1a 所示的网格结构计算像素的平滑代价,很显然这是一个复杂的非线性优化问题,计算量很大,很难满足实时性要求,动态规划算法将网格结构切割成多个一维的扫描线,如图1b所示,在每条独立的扫描线

8、上作能量优化,得到最优的匹配路 径。 图1a :网格结构 图1b :动态规划路径 图1c :半全局路径平滑性约束在物体边缘等深度梯度变化的区域是不适用的,往往导致动态规划算法在一维扫描线内的错误累积,这就是条状瑕疵现象。对于该问题Hirschmuller提出一种半全局立体匹配方法5,采用局部算法逐点匹配的思想,在待匹配像素多个方向上作动态规划,用多个一维的平滑约束来近似该像素二维的平滑约束。该算法改进了动态规划算法的条状瑕疵现象,但同时也增加了计算的负担,对于大范围的建筑物匹配具有一定的不适用性,另外建筑物表面纹理不明显也导致了该算法的匹配准确度不高,如图2所示的图像中待匹配点没有一条路径捕捉

9、到纹理信息,这种情况下,容易受噪声影响 而导致错误的匹配结果。图2:弱纹理区域半全局匹配示意图3 一种基于控制点的分段动态规划算法建筑物模型具有棱角明显,纹理较弱的特性,棱角明显有助于特征点的提取与匹配,而纹理较弱给大范围的稠密匹配带来了很大的困难。针对建筑物模型这一特征,本文提出一种基于控制点的分段动态规划算法。控制点的思想最早由Bobick 和Intille 6提出,利用控制点的匹配信息指导后续的稠密匹配。本文主要以约束视差范围的方式实现控制点对稠密匹配的指导,主要分为四个部分:图像获取与极线校正,特征点的提取与匹配,基于控制点的稠密匹配和三维重建,流程如图3所示。其中,特征点的提取采用C

10、anny 算子和Harris 算子,基于控制点的稠密匹配将在本文3.3节中作详细介绍。 图3:算法流程图3.1 图像获取与极线校正本文利用CCD从两个角度拍摄建筑物模型,采用张友正标定法7得到标定信息。左图中某像素在右图像上的匹配像素位于该像素对应的外极线上,这就是外极线约束的主要思想。该约束将匹配从二维的搜索过程降到了一维,极大地减少了运算量,并且是一种明确可靠不存在歧义的约束。当两部内参相同的摄像机平行放置时就构成了平行式立体视觉模型,平行式立体视觉模型所有极线平行于两摄像机的光心的连线,对应匹配像素具有相同的纵坐标。而实际拍摄时很难满足这种模型的要求,我们采用Fusiello 8提出的校

11、正方法通过强制旋转形成虚拟的平行成像平面,得到平行式的双目视觉模型,校正后的图像准确度高,误差控制在1个像素内,大大简化了后续匹配的过程。3.2 特征点的提取与匹配特征点的准确提取与匹配对后续的稠密匹配意义重大,本文采用Harris 算子和Canny 算子提取模型的角点和边缘点作为特征点。边缘提取中利用非极大点抑制法细化边缘,在垂直于边缘的方向上比较邻域的梯度幅值。根据这一操作去除梯度幅值的非极大点,从而达到细化边缘的目的。然后再利用双阈值算法去除由噪声和细纹引起的虚假边缘。本文采用改进的灰度区域相关算法匹配特征点。灰度区域相关算法通过比较待匹配点与候选匹配区域内所有像素邻域窗口内的灰度相关度

12、得到匹配点对,常用的相关性测度有灰度差平方(squared difference ,灰度互相关系数(cross correlation coefficient ,归一化灰度差平方(normalized squared difference 和归一化灰度互相关系数(normalized cross correlation coefficient 。在这些相似性测度函数中,归一化方式受光照影响较小,但计算量相对较大。本文引入Birchfield 和Tomasi 9提出的一种类似线性插值的方法,如图4所示。(I x ( I y 图4:匹配代价计算示意图其中,'222211(1(22i i i

13、 I I y I y I y =+(2 '222211(122i i i I I y I y I y +=+=+(3然后定义,min 222min,(i I I I I y += (4 max 222max,(i I I I I y +=(5 则两点匹配代价为,1max min 1max0,(,(i i S I x I I I x =(6这种匹配代价的计算量非常小,同时类似线性插值 的方法对于采样点和噪声不敏感,但由于本文所研究的对象灰度特征不明显,纹理不丰富,同一待匹配点的候选范围内会出现多个匹配代价最小的点,本文先采用这种类似线性插值的方法滤去候选范围内的大部分点,再对剩下的点计算

14、归一化互相关函数作为第二轮比较的依据,代价最小的点即为待匹配点的共轭点,候选范围由极线约束和视差范围约束相交得到。显然,引入这种类似线性插值法计算匹配代价可以加速控制点的匹配。为了进一步提高特征点匹配结果的可靠性,本文采用双向匹配策略,用从右往左的匹配结果检验从左往右的匹配,剔除误匹配后,最终得到可以指导稠密匹配的高置信度控制点集合。 3.3 基于控制点的稠密匹配由于建筑物模型中有大范围的无纹理区域,稠密匹配相当困难,采用基于窗口的灰度区域相关算法会产生很多误匹配,而动态规划算法在整条扫描线上搜索最优路径时,扫描线穿过视差垂直突变的区域,条状瑕疵现象明显。本文针对该问题,首先用控制点分段扫描线

15、,然后结合视差连续性约束,在分段后的扫描线内做动态规划获得稠密匹配视差结果。物体的表面一般是平滑的,因此在深度变化不大的区域,相邻的点视差应该是连续的,这就是视差连续性约束。这个约束条件是以物体表面平滑为前提的,正是因为建筑物模型不满足该前提条件,才导致了传统匹配算法对该模型不适用。因此,问题转化成怎样使模型满足视差连续性约束的前提条件,我们仍然采用动态规划算法在一维扫描线内规划最优路径的思想,利用提取的特征点分段水平扫描线,得到多个扫描线段,如图5所示。1l 11(P d 22(P d图5:扫描线分段示意图分段扫描线的依据是前期工作中得到的特征点,而这些特征点是基于灰度的梯度提取的,也是深度

16、梯度比较大的区域,因此对于分段得到的扫描线段,分别满足视差连续性约束,并拥有各自的视差范围,我们对这些扫描线段分别做动态规划,以扫描线段12PP 为例,该线段端点由特征点提取所得,并且前期匹配得到的视差分别为1d 和2d 12(d d <,我们在线段12PP 上应用动态规划算法计算匹配代价,得到最优的匹配路径,规划过程中将每个像素的视差范围约束在12(,d d 内,如图6所示。dd 12d d图6:扫描线1l 视差分布示意图该算法将视差范围由全局视差范围(,min max d d 缩小到12(,d d ,降低了匹配的歧义性,同时扫描线的缩短也减少了错误累积的可能,提高了算法的精度,并且由

17、于搜索范围的缩小,算法效率也得到进一步的提高。 3.4 三维重建本文采用空间交汇法还原出三维点云,计算一对匹配点所对应的两条入射光线的方程,求出其交点,即可得到对应物点在世界坐标系下的三维空间坐标。在实际计算过程中,由于标定、匹配、运算等各个过程中都存在误差,逆向计算出的两条直线很可能不会正好相交,此时只需如图7所示取两条异面直线的公垂线中点即 可。 图7:空间交汇法示意图4 实验结果 摄像机获取的图像对如图8所示,分辨率为1380×1030,建筑物模型区域大约为5-6万个像素,算法在VC+6.0平台下编程实现。极线校正的结果对比如图9所示,从图中可以看出,校正后极线水平,并且误差控

18、制在1个像素内。特征点的提取如图10所示,红色的点表示角点,白色的线条表示边缘。 图8:摄像机获取的图像对 图9a :校正前的极线 图9b :校正后的极线图10:特征点提取结果图本文算法的三维建筑物模型重建结果与其他三种主流算法的对比如图11所示,算法耗时如表1所示。灰度区域相关算法得到的重建模型误匹配最高;动态规划的条状瑕疵明显,但耗时较少;而半全局算法重建结果与前两种算法相比有所改进,但点云仍不够光滑,并且算法实时性不高。本文算法得到的建筑物三维点云平滑逼真,特别是在边缘区域,重建结果也比较理想,另外,本文算法也是四种算法中耗时最少的。图11a :灰度区域相关算法 图11b :动态规划算法

19、图11c :半全局算法 图11d :本文算法表1.四种立体匹配算法运算耗时对比匹配算法灰度区域相关算法动态规划算法半全局算法本章算法耗时(sec30 19 40 155 结论本文构建了完整的基于立体匹配的建筑物三维重建系统,提出一种新的基于控制点的分段动态规划算法,首先提取建筑物特征点作为稠密匹配的控制点,通过控制点分段扫描线进行动态规划,并利用具有高置信度的控制点匹配结果约束动态规划过程中的视差范围,引导稠密匹配得到较准确的结果。最后根据匹配结果恢复出三维模型,该算法在保证一定实时性的前提下,得到光滑逼真的建筑物三维点云,但该算法没有利用图像的颜色信息,今后的研究将把颜色作为辅助信息加入匹配

20、代价的计算中。致谢本文受到国家自然科学基金(60775025、江苏省自然科学基金(BK2007116的资助。参考文献1 D. Scharstein, R. Szeliski. A taxonomy and evaluation of densetwo-frame stereo correspondence algorithmsJ. Computer Vision, 2002, 47(1: 7-42.2 H. LI, G. CHEN. Segment-based stereo matching using graphcutsC. Proceedings of the IEEE Computer

21、Society Conference on Computer Vision and Pattern Recognition, Washington, DC.IEEE Press, 2004:174-181. 3 P.F. Felzenszwalb, D.P. Huttenlocher. Efficient beliefpropagation for early visionC. Proceedings of the IEEE Computer Society Conference on Computer Vision and PatternRecognition, Washington, DC

22、. IEEE Press, 2004: 1261-1268. 4 J.C. Kim, K.M. Lee. A dense stereo matching using two-passdynamic programming with generalized ground control pointsC. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, SanDiego, CA. Washington: IEEE Press, 2005: 1075- 1082.5 H. Hirschmuller. Accurate and Effi