王傳安，葛 華，王亞軍

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

基于非完全拓撲分析的三維建筑重建識別算法

王傳安，葛 華，王亞軍

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

為實現(xiàn)基于單幅圖像的三維建筑物重建識別過程，本文提出了一種有效的重建方法——非完全拓撲分析.首先，對三維建筑物可見部分的輪廓進行拓撲分析并提取，得到完整的拓撲結(jié)構(gòu).其次，將分割后的拓撲結(jié)構(gòu)與數(shù)據(jù)庫中原始信息進行快速識別匹配.實驗表明，本方法與SSDA圖像匹配算法相比，大大提高了計算速度和匹配效率.

拓撲分析；三維重建；噪聲閾值；識別算法

0 引 言

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

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

1 建筑物的拓撲結(jié)構(gòu)分析

1.1 非完全拓撲結(jié)構(gòu)的分析

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

概念1：間接平差法

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

概念2：滅點

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

下面分析可見部分的邊和頂點.

分析1：頂點分析

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

分析2：邊分析

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

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

1.2 非完全拓撲結(jié)構(gòu)的提取

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

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

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

2 改進的識別算法

2.1 圖像預(yù)處理

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

2.2 識別算法過程

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

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

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

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

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

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

2.3 識別算法的計算時間

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

提取時間tq為

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

匹配時間tp為

3 實驗分析

從圖片上提取到的非完全拓撲結(jié)構(gòu)是三維建筑物基本幾何形狀拓撲結(jié)構(gòu)的組合，為了和數(shù)據(jù)庫中存儲的基本幾何形狀的拓撲結(jié)構(gòu)匹配，需要把提取到的整體非完全拓撲結(jié)構(gòu)分割成一個個基本形狀的拓撲結(jié)構(gòu).圖2為對圖1中所示的建筑物原圖進行拓撲分析后，進行分割所得的拓撲分割圖.

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

圖2 建筑物拓撲分割圖Fig.2 The topology analysis of 3D Building

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

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

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

4 結(jié) 語

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

［1］夏春林，王佳奇.3DGIS中建筑物三維建模技術(shù)綜述［J］.測繪科學(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］.測繪學(xué)報，2005，34（4）：21-24.

［4］張會霞，陳宜金，劉國波.基于三維激光掃描儀的校園建筑物建模研究［J］.測繪工程，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］吳培景，陳光夢.一種改進的SSDA圖像匹配算法［J］.計算機工程與應(yīng)用，2005，33（11）：75-78.

［7］曹珩，楊述斌，羅帆，等.多尺度全方位復(fù)合廣義形態(tài)邊緣檢測的算法［J］.武漢工程大學(xué)學(xué)報，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)用型本科計算機公共基礎(chǔ)課程群研究與實踐（X201013）；安徽省自然科學(xué)研究項目（KJ2011Z070）

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