基于非完全拓?fù)浞治龅娜S建筑重建識(shí)別算法

王傳安，葛 華，王亞軍

（安徽科技學(xué)院，安徽 鳳陽(yáng) 233100）

基于非完全拓?fù)浞治龅娜S建筑重建識(shí)別算法

王傳安，葛 華，王亞軍

（安徽科技學(xué)院，安徽 鳳陽(yáng) 233100）

為實(shí)現(xiàn)基于單幅圖像的三維建筑物重建識(shí)別過程，本文提出了一種有效的重建方法——非完全拓?fù)浞治?首先，對(duì)三維建筑物可見部分的輪廓進(jìn)行拓?fù)浞治霾⑻崛。玫酵暾耐負(fù)浣Y(jié)構(gòu).其次，將分割后的拓?fù)浣Y(jié)構(gòu)與數(shù)據(jù)庫(kù)中原始信息進(jìn)行快速識(shí)別匹配.實(shí)驗(yàn)表明，本方法與SSDA圖像匹配算法相比，大大提高了計(jì)算速度和匹配效率.

拓?fù)浞治?；三維重建；噪聲閾值；識(shí)別算法

0 引 言

三維建筑重建是計(jì)算機(jī)視覺、計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)等領(lǐng)域一個(gè)非常重要的研究主題［1］.近年來，三維建筑重建技術(shù)已取得巨大進(jìn)展，產(chǎn)生了許多有效的算法［2，3］.建筑物重建是三維重建中的一個(gè)重要方面，其中建筑物的識(shí)別是一大難題，如何準(zhǔn)確快速的識(shí)別出圖像中的建筑物是一個(gè)亟待解決的問題.

三維建筑物識(shí)別方法通常采用基于建筑物邊緣線性特征的識(shí)別算法，這些算法大都要求三維建筑物的輪廓線是完整的，缺失部分或被遮擋的部分需要進(jìn)行人工添加［4，5］.典型的SSDA算法本身沒有抗干擾性能、計(jì)算過程中沒有利用圖像自身的特點(diǎn)，過多的人工交互影響了匹配速度，使得效率比較低［6］.曹珩等提出一種多尺度全方位復(fù)合廣義形態(tài)邊緣檢測(cè)的算法對(duì)圖像邊緣進(jìn)行檢測(cè)［7］.針對(duì)這種情況，本文提出了一種加權(quán)的建筑物識(shí)別方法，該方法不要求建筑物的輪廓是完整的，僅分析建筑物的可見部分就能夠在數(shù)據(jù)庫(kù)中找到對(duì)應(yīng)的匹配模型.

1 建筑物的拓?fù)浣Y(jié)構(gòu)分析

1.1 非完全拓?fù)浣Y(jié)構(gòu)的分析

通常情況下，三維建筑物的整體形狀是由簡(jiǎn)單幾何體組成的，比如立方體，棱柱體，球體等.如何從圖像的輪廓中提取的這些簡(jiǎn)單幾何體進(jìn)行解析，主要依靠建筑物的投影拓?fù)浣Y(jié)構(gòu)，也就是頂點(diǎn)，邊的布局.因此需要對(duì)可見部分的邊和頂點(diǎn)進(jìn)行分析.在分析之前，先引入幾個(gè)相關(guān)概念.

概念1：間接平差法

通過選定t個(gè)與觀測(cè)值有一定關(guān)系的獨(dú)立未知量作為參數(shù)，然后將觀測(cè)值分別表達(dá)成這t個(gè)參數(shù)的函數(shù)，建立函數(shù)模型，最后按最小二乘原理，用求自由極值的方法解出參數(shù)的最或然值，從而求得各觀測(cè)值的平差值.

概念2：滅點(diǎn)

指立體圖形各點(diǎn)延伸線向消失延伸的相交點(diǎn)，即透視點(diǎn)的消失點(diǎn).

下面分析可見部分的邊和頂點(diǎn).

分析1：頂點(diǎn)分析

為了加快與數(shù)據(jù)庫(kù)的匹配速度，每個(gè)頂點(diǎn)都被賦予了一個(gè)權(quán)值，用來表示連接到這個(gè)頂點(diǎn)的邊的數(shù)目，權(quán)值越大表示連入的邊越多.根據(jù)這個(gè)權(quán)值與數(shù)據(jù)庫(kù)進(jìn)行匹配.

分析2：邊分析

假設(shè)三維建筑物是由三維空間中分別平行于X、Y、Z坐標(biāo)軸的“三組”平行線組成，而這三組平行線又互相垂直.首先利用間接平差法求得三個(gè)方向上的滅點(diǎn)pv0，pv1和pv2.其次利用下式計(jì)算任意一邊e與所求滅點(diǎn)p之間的方位角：

其中d（e，pv）是邊e和滅點(diǎn)pv之間的距離函數(shù)，若滅點(diǎn)是無窮點(diǎn)，它就是邊的中點(diǎn)和對(duì)應(yīng)滅點(diǎn)方向的夾角，若滅點(diǎn)是有窮點(diǎn)，它就是邊的中點(diǎn)和滅點(diǎn)之間的夾角.Tα是噪聲閾值，用以處理圖像中存在的噪聲.將每條邊和三個(gè)滅點(diǎn)分別代入上式，則使上式取得最大值的那個(gè)滅點(diǎn)為與這條邊對(duì)應(yīng)的滅點(diǎn).

1.2 非完全拓?fù)浣Y(jié)構(gòu)的提取

使用邊緣檢測(cè)的方法獲得建筑物可見部分的邊緣框圖，同時(shí)逐步建立一個(gè)圖G（V，E）.初始狀態(tài)G（V，E）為空.每檢測(cè)出一條邊就把它和對(duì)應(yīng)的頂點(diǎn)信息分別加到圖G（V，E）中，頂點(diǎn)信息放入集合V中，邊信息放入集合E中.頂點(diǎn)信息包括每個(gè)頂點(diǎn)的編號(hào)和權(quán)值，初始狀態(tài)每個(gè)頂點(diǎn)的權(quán)值為0，每連入一條邊它的權(quán)值就增加1.邊信息包括用頂點(diǎn)序號(hào)表示的數(shù)對(duì)和一個(gè)表明這條邊和哪個(gè)滅點(diǎn)相對(duì)應(yīng)的數(shù)字，即這條邊屬于哪一個(gè)組.

1.3 構(gòu)建原始數(shù)據(jù)庫(kù)

原始數(shù)據(jù)庫(kù)中存儲(chǔ)了某一視點(diǎn)下的每個(gè)基本幾何體的非完全拓?fù)浣Y(jié)構(gòu)及其約束條件.每個(gè)視點(diǎn)信息是利用單幅圖像獲得的.每個(gè)幾何體的非完全拓?fù)浣Y(jié)構(gòu)分別存儲(chǔ)在圖Gmx（V，E）中，m為小于等于建筑物的立體面數(shù)，x為在一立體面下的攝取視點(diǎn)數(shù)；對(duì)應(yīng)的約束條件存儲(chǔ)在方陣Amx中，Amx的階數(shù)為邊的數(shù)目，約束條件包括邊與邊之間的相等、平行或垂直關(guān)系.

2 改進(jìn)的識(shí)別算法

2.1 圖像預(yù)處理

首先對(duì)待匹配圖G（V，E）進(jìn)行掃描，將其像素點(diǎn)與模板圖為Gm（Vm，Em）中對(duì)應(yīng)點(diǎn)的灰度值進(jìn)行比較，并將其差值與Tα作判斷，從而決定待匹配圖的當(dāng)前像素點(diǎn)是否存在噪聲，均值濾波和中值濾波是比較常用的對(duì)圖像噪聲抑制的方法，本文采用中值濾波的方式去除噪聲.其中，Tα的取值根據(jù)多次實(shí)驗(yàn)結(jié)果決定.

2.2 識(shí)別算法過程

為了進(jìn)一步簡(jiǎn)化識(shí)別過程，提高識(shí)別速度，首先根據(jù)提取的物體拓?fù)浣Y(jié)構(gòu)對(duì)數(shù)據(jù)庫(kù)中的模型進(jìn)行如下操作：

物體的某個(gè)部分可能被遮擋住，或者在拍攝過程中沒有被拍下來，那么從圖片上提取到的拓?fù)浣Y(jié)構(gòu)就是不完全的，此種情況下，從圖像上提取到的頂點(diǎn)個(gè)數(shù)和邊數(shù)將小于等于數(shù)據(jù)庫(kù)中對(duì)應(yīng)模型的頂點(diǎn)個(gè)數(shù)和邊數(shù).所以首先將提取到的具有不同權(quán)值的頂點(diǎn)個(gè)數(shù)和原始模型的頂點(diǎn)個(gè)數(shù)進(jìn)行比較，如出現(xiàn)提取到的具有某個(gè)權(quán)值的頂點(diǎn)的個(gè)數(shù)大于模型中同等權(quán)值的頂點(diǎn)個(gè)數(shù)，則直接越過此模型，只與其他模型進(jìn)行匹配.具體的匹配過程如下：

（1）從原始數(shù)據(jù)庫(kù)中任意選取一個(gè)模型Gm（Vm，Em），并從G（V，E）的頂點(diǎn)集V 中任意選取一個(gè)權(quán)值最大的頂點(diǎn)v作為起始點(diǎn)，在Gm（Vm，Em）的頂點(diǎn)集Vm中查找與v權(quán)值一樣的頂點(diǎn)，比較與它們相連的邊的組號(hào)是否相同，若相同，則執(zhí)行步驟（2），否則執(zhí)行步驟（3）.

（2）再?gòu)捻旤c(diǎn)集V剩余的頂點(diǎn)中任取一個(gè)權(quán)值最大的頂點(diǎn)v，并從頂點(diǎn)集Vm剩余的頂點(diǎn)中查找與它權(quán)值相同的頂點(diǎn)，再次比較與它們相連的邊的組號(hào)是否相同，若相同則重復(fù)執(zhí)行步驟（2），直至V中所有權(quán)值大于1的頂點(diǎn)都被遍歷過.那么此模型就是目標(biāo)模型，則匹配完成，否則執(zhí)行步驟（3）.

（3）從頂點(diǎn)集Vm中再另外取一個(gè)權(quán)值與v相同的頂點(diǎn)，比較與它們相連的邊的組號(hào)是否相同，若相同則執(zhí)行步驟（2），否則重復(fù)執(zhí)行步驟（3），直至Vm中權(quán)值與v相同的頂點(diǎn)被遍歷過，此時(shí)執(zhí)行步驟（4）.

（4）再?gòu)脑紨?shù)據(jù)庫(kù)任意選取一個(gè)模型，重復(fù)執(zhí)行步驟（1）至（4），直至所有的模型都被匹配完，此時(shí)計(jì)算每個(gè)模型的匹配率，最大者即為所求得的模型.匹配率是指已匹配的頂點(diǎn)數(shù)與提取的整體輪廓中所有頂點(diǎn)的比值.

2.3 識(shí)別算法的計(jì)算時(shí)間

識(shí)別算法的有效越性取決于算法的計(jì)算時(shí)間能否滿足實(shí)時(shí)性的要求.由于該快速識(shí)別算法分為提取過程和匹配過程，因此算法的所耗時(shí)間由提取時(shí)間和匹配時(shí)間組成，分別用tq，tp表示，實(shí)時(shí)圖為G（V，E），模板圖為Gm（Vm，Em）.

提取時(shí)間tq為

式（2）中ts為計(jì)算2個(gè)8字節(jié)的整型數(shù)據(jù)相減所用的時(shí)間.

匹配時(shí)間tp為

3 實(shí)驗(yàn)分析

從圖片上提取到的非完全拓?fù)浣Y(jié)構(gòu)是三維建筑物基本幾何形狀拓?fù)浣Y(jié)構(gòu)的組合，為了和數(shù)據(jù)庫(kù)中存儲(chǔ)的基本幾何形狀的拓?fù)浣Y(jié)構(gòu)匹配，需要把提取到的整體非完全拓?fù)浣Y(jié)構(gòu)分割成一個(gè)個(gè)基本形狀的拓?fù)浣Y(jié)構(gòu).圖2為對(duì)圖1中所示的建筑物原圖進(jìn)行拓?fù)浞治龊螅M(jìn)行分割所得的拓?fù)浞指顖D.

圖1 三維建筑物原圖Fig.1 Image-Based 3D Building

圖2 建筑物拓?fù)浞指顖DFig.2 The topology analysis of 3D Building

為了測(cè)試該算法的有效性，采用本文提出的改進(jìn)的識(shí)別算法和序貫相似度檢測(cè)匹配法（SSDA）進(jìn)行性能比較，結(jié)果如圖3所示.

圖3 本文方法與SSDA性能比較Fig.3 Performance comparison of two algorithms

由圖3可知，改進(jìn)識(shí)別算法在提取時(shí)間和匹配時(shí)間上都優(yōu)于SSDA算法，從圖3中還可以看出，隨著數(shù)據(jù)模型頂點(diǎn)集合V中頂點(diǎn)個(gè)數(shù)的增加，SSDA算法的匹配時(shí)間是線性增加的，而本文方法的匹配時(shí)間幾乎沒有增加.

4 結(jié) 語(yǔ)

采用非完全拓?fù)浞治龅姆椒▽?duì)三維建筑物進(jìn)行拓?fù)浞治?，?duì)從圖片上提取到的非完全拓?fù)浣Y(jié)構(gòu)進(jìn)行分割，然后用改進(jìn)的快速識(shí)別算法與原始數(shù)據(jù)庫(kù)信息進(jìn)行快速識(shí)別匹配.該方法簡(jiǎn)單、高效，僅對(duì)可見部分的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，并不需要完備的拓?fù)湫畔?；同時(shí)，它省去了復(fù)雜的數(shù)學(xué)運(yùn)算，大大節(jié)省了識(shí)別匹配的時(shí)間.

［1］夏春林，王佳奇.3DGIS中建筑物三維建模技術(shù)綜述［J］.測(cè)繪科學(xué)，2011，36（1）：70-72.

［2］Ting Z，F(xiàn)eng D D，Zheng T.3D Reconstruction of Single Picture［C］∥ACM Conf on Visual Information Processing，2004：83-86.

［3］吳軍.3維城市建模中的建筑墻面紋理快速重建研究［J］.測(cè)繪學(xué)報(bào)，2005，34（4）：21-24.

［4］張會(huì)霞，陳宜金，劉國(guó)波.基于三維激光掃描儀的校園建筑物建模研究［J］.測(cè)繪工程，2010，19（1）：32-35.

［5］Van den Heuvel，F(xiàn) A.Reconstruction from a single architectural image from the Meydenbauer archives.In：Proceedings of the XVIII［C］∥International Symposium of CIPA 2001.Potsdam，2001：699.

［6］吳培景，陳光夢(mèng).一種改進(jìn)的SSDA圖像匹配算法［J］.計(jì)算機(jī)工程與應(yīng)用，2005，33（11）：75-78.

［7］曹珩，楊述斌，羅帆，等.多尺度全方位復(fù)合廣義形態(tài)邊緣檢測(cè)的算法［J］.武漢工程大學(xué)學(xué)報(bào)，2010，32（9）：32-36.

Image-Based 3D Building Reconstruction based on Non-complete topological analysis

WANG Chuan-an，GE Hua，WANG Ya-jun
（College of Science and Technology Anhui University；Fengyang 233100，China）

Image-Based 3D Building Reconstruction is a very difficult problem in computer vision and computer graphics.An efficient method of 3D building reconstruction method is proposed by using noncomplete topological analysis，which rapidly achieves the process of recognizing architectures based one or two images.Firstly，the outline of visible parts of 3D reconstruction is extracted from image and is analyzed to get the incomplete topology of architectures.Then，the resulted topology will be divided into some primitive geometry，and these geometries are used to match models in databases finally.Experiments show that this method VS SSDA has better effectiveness.

topology analysis；3D reconstruction；Noise threshold；recognition algorithm

陳小平

TQ177.5

A

10.3969／j.issn.1674-2869.2011.10.023

16742869（2011）10010003

20110424

應(yīng)用型本科計(jì)算機(jī)公共基礎(chǔ)課程群研究與實(shí)踐（X201013）；安徽省自然科學(xué)研究項(xiàng)目（KJ2011Z070）

王傳安（1980），男，安徽淮北人，講師，碩士.研究方向：數(shù)據(jù)挖掘.