《武汉工程大学学报》 2011年10期
100-102
出版日期：2011-11-30
ISSN:1674-2869
CN:42-1779/TQ
基于非完全拓扑分析的三维建筑重建识别算法
0引言三维建筑重建是计算机视觉、计算机图形学、虚拟现实等领域一个非常重要的研究主题［1］.近年来，三维建筑重建技术已取得巨大进展，产生了许多有效的算法［2,3］.建筑物重建是三维重建中的一个重要方面，其中建筑物的识别是一大难题，如何准确快速的识别出图像中的建筑物是一个亟待解决的问题.三维建筑物识别方法通常采用基于建筑物边缘线性特征的识别算法，这些算法大都要求三维建筑物的轮廓线是完整的，缺失部分或被遮挡的部分需要进行人工添加［4,5］.典型的SSDA算法本身没有抗干扰性能、计算过程中没有利用图像自身的特点，过多的人工交互影响了匹配速度，使得效率比较低［6］.曹珩等提出一种多尺度全方位复合广义形态边缘检测的算法对图像边缘进行检测［7］.针对这种情况，本文提出了一种加权的建筑物识别方法，该方法不要求建筑物的轮廓是完整的，仅分析建筑物的可见部分就能够在数据库中找到对应的匹配模型.1建筑物的拓扑结构分析1.1非完全拓扑结构的分析通常情况下，三维建筑物的整体形状是由简单几何体组成的，比如立方体，棱柱体，球体等.如何从图像的轮廓中提取的这些简单几何体进行解析，主要依靠建筑物的投影拓扑结构，也就是顶点，边的布局.因此需要对可见部分的边和顶点进行分析.在分析之前，先引入几个相关概念.概念1：间接平差法通过选定t个与观测值有一定关系的独立未知量作为参数，然后将观测值分别表达成这t个参数的函数，建立函数模型，最后按最小二乘原理，用求自由极值的方法解出参数的最或然值，从而求得各观测值的平差值.概念2：灭点指立体图形各点延伸线向消失延伸的相交点，即透视点的消失点.下面分析可见部分的边和顶点.分析1：顶点分析为了加快与数据库的匹配速度，每个顶点都被赋予了一个权值，用来表示连接到这个顶点的边的数目，权值越大表示连入的边越多.根据这个权值与数据库进行匹配.分析2：边分析假设三维建筑物是由三维空间中分别平行于X、Y、Z坐标轴的“三组”平行线组成，而这三组平行线又互相垂直.首先利用间接平差法求得三个方向上的灭点pv0，pv1和pv2.其次利用下式计算任意一边e与所求灭点p之间的方位角：g(e,pv)=1-d(e,pv)Tα(d(e,pv)＜Tα)
0(1)其中d(e,pv)是边e和灭点pv之间的距离函数，若灭点是无穷点，它就是边的中点和对应灭点方向的夹角，若灭点是有穷点，它就是边的中点和灭点之间的夹角.Tα是噪声阈值，用以处理图像中存在的噪声.将每条边和三个灭点分别代入上式，则使上式取得最大值的那个灭点为与这条边对应的灭点.1.2非完全拓扑结构的提取使用边缘检测的方法获得建筑物可见部分的边缘框图，同时逐步建立一个图G(V,E).初始状态G(V,E)为空.每检测出一条边就把它和对应的顶点信息分别加到图G(V,E)中，顶点信息放入集合V中，边信息放入集合E中.顶点信息包括每个顶点的编号和权值，初始状态每个顶点的权值为0，每连入一条边它的权值就增加1.边信息包括用顶点序号表示的数对和一个表明这条边和哪个灭点相对应的数字，即这条边属于哪一个组.1.3构建原始数据库原始数据库中存储了某一视点下的每个基本几何体的非完全拓扑结构及其约束条件.每个视点信息是利用单幅图像获得的.每个几何体的非完全拓扑结构分别存储在图Gmx(V,E)中,m为小于等于建筑物的立体面数，x为在一立体面下的摄取视点数；对应的约束条件存储在方阵Amx中，Amx的阶数为边的数目，约束条件包括边与边之间的相等、平行或垂直关系.2改进的识别算法2.1图像预处理首先对待匹配图G(V,E)进行扫描,将其像素点与模板图为Gm(Vm,Em)中对应点的灰度值进行比较,并将其差值与Tα作判断,从而决定待匹配图的当前像素点是否存在噪声，均值滤波和中值滤波是比较常用的对图像噪声抑制的方法，本文采用中值滤波的方式去除噪声.其中,Tα的取值根据多次实验结果决定.2.2识别算法过程为了进一步简化识别过程，提高识别速度，首先根据提取的物体拓扑结构对数据库中的模型进行如下操作：物体的某个部分可能被遮挡住，或者在拍摄过程中没有被拍下来，那么从图片上提取到的拓扑结构就是不完全的，此种情况下，从图像上提取到的顶点个数和边数将小于等于数据库中对应模型的顶点个数和边数.所以首先将提取到的具有不同权值的顶点个数和原始模型的顶点个数进行比较，如出现提取到的具有某个权值的顶点的个数大于模型中同等权值的顶点个数，则直接越过此模型，只与其他模型进行匹配.具体的匹配过程如下：(1)从原始数据库中任意选取一个模型Gm(Vm,Em)，并从G(V,E)的顶点集V中任意选取一个权值最大的顶点v作为起始点，在Gm(Vm,Em)的顶点集Vm中查找与v权值一样的顶点，比较与它们相连的边的组号是否相同，若相同，则执行步骤（2），否则执行步骤（3）.(2)再从顶点集V剩余的顶点中任取一个权值最大的顶点v，并从顶点集Vm剩余的顶点中查找与它权值相同的顶点，再次比较与它们相连的边的组号是否相同，若相同则重复执行步骤（2），直至V中所有权值大于1的顶点都被遍历过.那么此模型就是目标模型，则匹配完成，否则执行步骤（3）.(3)从顶点集Vm中再另外取一个权值与v相同的顶点，比较与它们相连的边的组号是否相同，若相同则执行步骤（2），否则重复执行步骤（3），直至Vm中权值与v相同的顶点被遍历过，此时执行步骤（4）.(4)再从原始数据库任意选取一个模型，重复执行步骤（1）至（4），直至所有的模型都被匹配完，此时计算每个模型的匹配率，最大者即为所求得的模型.匹配率是指已匹配的顶点数与提取的整体轮廓中所有顶点的比值.第10期王传安，等：基于非完全拓扑分析的三维建筑重建识别算法
武汉工程大学学报第33卷
2.3识别算法的计算时间识别算法的有效越性取决于算法的计算时间能否满足实时性的要求.由于该快速识别算法分为提取过程和匹配过程，因此算法的所耗时间由提取时间和匹配时间组成,分别用tq,tp表示，实时图为G(V,E),模板图为Gm(Vm,Em).提取时间tq为tq=4TαVEts(2)
式(2)中ts为计算2个8字节的整型数据相减所用的时间.匹配时间tp为tp=V-Vm×(E-Em)×Vm×Em(Tα+1)2×ts(3)综上可知，整个识别算法的计算时间为
t=tq+tq=(V-Vm)×(E-Em)(Tα+1)2+4TαVmEmts(4)3实验分析从图片上提取到的非完全拓扑结构是三维建筑物基本几何形状拓扑结构的组合，为了和数据库中存储的基本几何形状的拓扑结构匹配，需要把提取到的整体非完全拓扑结构分割成一个个基本形状的拓扑结构.图2为对图1中所示的建筑物原图进行拓扑分析后，进行分割所得的拓扑分割图.图1三维建筑物原图
Fig.1ImageBased 3D Building图2建筑物拓扑分割图
Fig.2The topology analysis of 3D Building为了测试该算法的有效性,采用本文提出的改进的识别算法和序贯相似度检测匹配法（SSDA）进行性能比较，结果如图3所示.图3本文方法与SSDA性能比较
Fig.3Performance comparison of two algorithms由图3可知，改进识别算法在提取时间和匹配时间上都优于SSDA算法，从图3中还可以看出，随着数据模型顶点集合V中顶点个数的增加，SSDA算法的匹配时间是线性增加的，而本文方法的匹配时间几乎没有增加.4结语采用非完全拓扑分析的方法对三维建筑物进行拓扑分析，对从图片上提取到的非完全拓扑结构进行分割，然后用改进的快速识别算法与原始数据库信息进行快速识别匹配.该方法简单、高效，仅对可见部分的拓扑结构进行分析，并不需要完备的拓扑信息；同时，它省去了复杂的数学运算，大大节省了识别匹配的时间.参考文献：