宋 陽(yáng)，李昌華，馬宗方，李智杰

（1.西安建筑科技大學(xué)信息與控制工程學(xué)院，陜西 西安 710055 2.西安建筑科技大學(xué)建筑學(xué)院，陜西 西安 710055）

點(diǎn)云數(shù)據(jù)是通過(guò)三維激光掃描儀等獲取的圖形圖像數(shù)據(jù)，準(zhǔn)確地表達(dá)真實(shí)物體的表面信息[1-7]，形成建筑信息模型．古建筑傳承了人類光輝燦爛的文明，凝聚了廣大勞動(dòng)人民的智慧結(jié)晶，成為了人類文明發(fā)展中活生生的化石，使用三維激光掃描儀記錄古建筑，形成古建筑信息模型，為古建筑保護(hù)和研究提供詳實(shí)可靠的基礎(chǔ)數(shù)據(jù)，能夠?qū)崿F(xiàn)古建筑數(shù)字化保護(hù)．古建筑信息模型中的特征能夠?qū)崿F(xiàn)形狀分析、數(shù)據(jù)表達(dá)，為點(diǎn)云數(shù)據(jù)處理提供充足的信息，古建筑信息模型特征獲取的精準(zhǔn)度能夠影響信息恢復(fù)的有效性．古建筑信息模型特征提取可以去除噪聲，簡(jiǎn)化特征描述，保持古建筑重建的重要信息，為古建筑保護(hù)和研究提供重要的參考依據(jù)．

目前，已有諸多學(xué)者展開了針對(duì)三維模型特征提取的研究，誕生了多種算法[8-13]．盡管建筑信息模型特征提取算法得到了廣泛的研究和改進(jìn)，但是經(jīng)過(guò)分析，許多建筑信息模型特征提取算法存在以下問(wèn)題：

（1）點(diǎn)云數(shù)據(jù)特征提取過(guò)程中，許多算法采用硬聚類或分類思想，因此一些算法非常武斷的將點(diǎn)云數(shù)據(jù)劃分為特征，這些特征中包含過(guò)多的噪聲信息，并且不能夠過(guò)濾掉，特征劃分不準(zhǔn)確．

（2）點(diǎn)云數(shù)據(jù)采集過(guò)程中，使用的儀器、模型物體和光照等客觀原因，導(dǎo)致點(diǎn)云模型缺少連接信息，嚴(yán)重的存在特征點(diǎn)被遺漏，造成特征數(shù)據(jù)缺失，容易產(chǎn)生空洞．

因此，為了能夠解決上述問(wèn)題，本文基于互信息理論提出了一種新的 aIB算法（agglomerative Information Bottleneck，凝聚式信息瓶頸算法），該算法采用層次凝聚思想，在特征提取過(guò)程中盡量壓縮點(diǎn)云數(shù)據(jù)，過(guò)濾噪聲．為了驗(yàn)證本文算法的有效性，與基于非線性核回歸的特征提取算法[14]和基于圖像處理的點(diǎn)云特征提取算法[15]從特征點(diǎn)提取數(shù)量、算法運(yùn)行時(shí)間等方面進(jìn)行了比較，實(shí)驗(yàn)結(jié)果顯示該算法能夠有效地提高點(diǎn)云數(shù)據(jù)特征提取的精準(zhǔn)度，并且降低了特征提取耗費(fèi)時(shí)間．如圖1所示．

圖1 aIB算法在古建筑信息模型特征提取中的應(yīng)用Fig.1 Application of aIB algorithm in ancient building information model feature extraction

1 互信息原理

互信息定義：給定隨機(jī)變量x和y聯(lián)合概率分布因此可以隨機(jī)變量x和y之間的互信息可以為公式（1）：

互信息I(X;Y) 可以描述兩個(gè)隨機(jī)變量x和y相互包含的程度，如果則表示兩個(gè)隨機(jī)變量是獨(dú)立的，二者互不包含，它們之間的互信息為零．

2 基于aIB的古建筑信息模型特征提取算法設(shè)計(jì)

在古建筑信息模型特征提取過(guò)程中，為了能夠更好地提取相關(guān)的點(diǎn)云數(shù)據(jù)，可以使用變量X描述原始古建筑點(diǎn)云數(shù)據(jù)集，使用相關(guān)變量Y描述法向量，兩者之間的聯(lián)合概率分布為滿足在古建筑信息模型特征提取過(guò)程中，盡力的把源變量X集合中的元素劃分到特征集合T中時(shí)，需要盡可能的保持法向量Y的信息，也就是需要最大化保持互信息I(X;Y)，因此基于互信息的點(diǎn)云數(shù)據(jù)特征提取原理如圖2所示．

其中:

表示一個(gè)概率歸一化函數(shù)，由于目標(biāo)函數(shù)僅僅表示古建筑信息模型特征提取的形式解．

圖2 基于互信息的古建筑信息模型特征提取Fig.2 Ancient building information model based on mutual information feature extraction

基于互信息的古建筑信息模型特征提取目標(biāo)函數(shù)可以如公式（2）所示．

目標(biāo)函數(shù)是一個(gè)關(guān)于自變量p(t|x)的函數(shù)，由于古建筑信息模型點(diǎn)云數(shù)據(jù)集是客觀存在的，因此互信息I(X;Y) 是一個(gè)常量，在目標(biāo)函數(shù)中可以忽略其變化；β是目標(biāo)函數(shù)引入的一個(gè)拉格朗日因子，其可以在點(diǎn)云數(shù)據(jù)特征提取過(guò)程中盡可能的平衡互信息I(X;T) 和I(T;Y)，為了能夠求解目標(biāo)函數(shù)，可以引入馬爾科夫鏈基于馬爾科夫鏈的條件獨(dú)立性關(guān)系，可以獲取目標(biāo)函數(shù)的解，具體如公式（3）所示．

古建筑信息模型特征提取過(guò)程中，本文引入了自底向上層次凝聚、互信息等理論，提出了一種aIB算法，該算法可以將原始點(diǎn)云數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)集都作為一個(gè)特征點(diǎn)，使用互信息度量包含程度最大的兩個(gè)特征點(diǎn)進(jìn)行合并，也即是選擇兩個(gè)最為相似的數(shù)據(jù)點(diǎn)合并為一個(gè)數(shù)據(jù)點(diǎn)，直到將所有的數(shù)據(jù)點(diǎn)合并到一個(gè)特征簇中．具體的，aIB算法在古建筑信息模型特征提取中的形式化描述如下：原始數(shù)據(jù)集X中的每一個(gè)對(duì)象x都劃分到特征集t中，其中t∈T，合并任意兩個(gè)特征對(duì)象ti和tj，合并過(guò)程中使得T算是的互信息最小，也就是盡可能的保存I(T;Y)，直到將所有的特征對(duì)象合并到一個(gè)簇中．自底向上凝聚古建筑信息模型特征提取算法可以生成一棵層次樹，該層次樹針對(duì)數(shù)據(jù)集的可視化管理能夠提供非常優(yōu)越的便利條件．

在自底向上層次凝聚的古建筑信息模型特征提取算法aIB中，給定T中兩個(gè)對(duì)象ti和tj，合并所產(chǎn)生的信息損失稱為為合并代價(jià)，其可以定義為公式（4）：

其中，I(Tbefore,Y)和I(Tafter,Y)分別代表合并ti和tj前后的T和Y之間的互信息．進(jìn)一步把式（4）規(guī)范化為公式（5）：

自底向上凝聚點(diǎn)云數(shù)據(jù)特征提取算法流程：

輸入:聯(lián)合分布p(x,y),平衡參數(shù)β.

輸出:數(shù)據(jù)模式T.

算法步驟：

1. 初始化:T←X,β=∞；

3. While (|T|>1)

4. 對(duì)?t∈T,基于公式（5）計(jì)算

自底向上點(diǎn)云數(shù)據(jù)特征提取算法描述如下：

在自底向上層次凝聚的古建筑信息模型特征提取算法aIB中，每一次迭代合并過(guò)程中，算法都需要計(jì)算、比較所有的特征對(duì)象合并代價(jià)，以便能夠選擇合并代價(jià)最低的兩個(gè)特征對(duì)象進(jìn)行合并，因此點(diǎn)云數(shù)據(jù)特征提取算法運(yùn)行中，假設(shè)算法執(zhí)行為當(dāng)前層Ti-1，算法將“最佳合并特征對(duì)象對(duì)”之后的層為Ti，因此可以得知程序控制的核心因子為自底向上層次凝聚的古建筑信息模型特征提取算法aIB在每一次合并過(guò)程中使得I(T;Y)最大化，其得到一個(gè)局部最優(yōu)解．但是，這不能保證對(duì)每一個(gè)劃分T都得到最優(yōu)解，甚至對(duì)一個(gè)確定的T也不能得到最優(yōu)解，此時(shí)自底向上古建筑信息模型特征提取的時(shí)間復(fù)雜度是如果想得到一個(gè)最優(yōu)解，其算法時(shí)間復(fù)雜度，將呈指數(shù)級(jí)增長(zhǎng)．

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)環(huán)境采用Matlab2011平臺(tái)，在實(shí)驗(yàn)過(guò)程中，算法是在一臺(tái)Intel(R) Core(TM) i5-4590 CPU（主頻為3.3GHz）、4G內(nèi)存的臺(tái)式機(jī)上運(yùn)行．實(shí)驗(yàn)數(shù)據(jù)采用第一批全國(guó)重點(diǎn)文物保護(hù)單位西安市興教寺的基師塔古建筑作為算法試驗(yàn)數(shù)據(jù)集，數(shù)據(jù)采集過(guò)程中使用瑞士徠卡C10便攜式三維激光掃描儀進(jìn)行掃描，掃描的點(diǎn)云數(shù)量共計(jì)為599 942個(gè)．

3.2 實(shí)驗(yàn)結(jié)果分析

基師塔古建筑模型原始點(diǎn)云數(shù)據(jù)點(diǎn)共計(jì) 599 942個(gè)，由于基師塔所在區(qū)域的光照、遮擋和掃描儀設(shè)備自身缺陷等導(dǎo)致獲取的古建筑信息模型存在大量的噪聲點(diǎn)，因此基師塔的特征數(shù)據(jù)點(diǎn)比較分散，為后期基師塔重建帶來(lái)困難．如圖3所示．

圖3 基師塔古建筑信息模型原始圖Fig.3 Ancient building information model original image of Jishi Pagoda

圖4 aIB算法特征提取效果Fig.4 aIB algorithm feature extraction result

本文是非線性核回歸算法和圖像處理算法對(duì)基師塔古建筑模型提取點(diǎn)云數(shù)據(jù)特征效果如圖 5-6所示．

圖5 非線性核回歸算法特征提取效果Fig.5 Nuclear non-linear regression algorithms feature extraction result

圖6 圖像處理算法特征提取效果Fig.6 Image processing algorithm feature extraction result

本文使用aIB算法提取點(diǎn)云數(shù)據(jù)特征，在盡可能的壓縮噪聲數(shù)據(jù)的同時(shí)能夠最大程度的保存模型特征，提取了241 002個(gè)特征點(diǎn)．如圖4所示．

具體的，三種算法運(yùn)行結(jié)果如表1所示．

表1 三種算法運(yùn)行結(jié)果數(shù)據(jù)Tab.1 Three algorithms operating results data

通過(guò)分析，aIB算法能夠在較短的時(shí)間內(nèi)提取更多的點(diǎn)云數(shù)據(jù)特征點(diǎn)，特征檢測(cè)能力較好．另外，非線性核回歸算法和圖像處理算法檢測(cè)出的特征點(diǎn)多集中于基師塔數(shù)據(jù)的明顯特征處，比如外輪廓，aIB算法檢測(cè)的出特征點(diǎn)的部位更加廣泛，除上述兩種算法檢測(cè)出特征點(diǎn)的部位之外，還包括塔檐邊界線等特征，因此aIB算法更加適應(yīng)于復(fù)雜部位點(diǎn)云特征提?。?/p>

本文aIB算法的創(chuàng)新點(diǎn)：

(1) 自動(dòng)化確定β的取值．在aIB算法運(yùn)行過(guò)程中，β因子是目標(biāo)函數(shù)引入的一個(gè)拉格朗日因子，其可以在點(diǎn)云數(shù)據(jù)特征提取過(guò)程中盡可能的平衡互信息I(X;T)和I(T;Y)，確定β的取值需要用戶掌握較多的點(diǎn)云數(shù)據(jù)應(yīng)用背景與經(jīng)驗(yàn)知識(shí)，以便能夠更好地實(shí)現(xiàn)古建筑信息模型特征提取，提高特征提取精確度．本文算法基于層次凝聚思想，算法運(yùn)行過(guò)程中可以自動(dòng)排列互信息損失度，選擇最少的互信息損失進(jìn)行點(diǎn)云數(shù)據(jù)特征提?。?/p>

(2) 基于互信息I(T;Y)的進(jìn)行特征提?。產(chǎn)IB算法運(yùn)行時(shí)需要在盡可能的壓縮互信息I(X;T)，同時(shí)最大化的保存互信息I(T;Y)，因此該算法擴(kuò)展了互信息在模式識(shí)別、機(jī)器學(xué)習(xí)領(lǐng)域的應(yīng)用，創(chuàng)新地提出保留點(diǎn)云數(shù)據(jù)特征的情況下壓縮噪聲數(shù)據(jù)，更好地實(shí)現(xiàn)特征點(diǎn)檢測(cè)．

4 結(jié)語(yǔ)

古建筑信息模型特征提取是模型重建、古建筑恢復(fù)等關(guān)鍵前提，也是當(dāng)前是計(jì)算機(jī)視覺(jué)、圖像理解等領(lǐng)域的重要課題之一．

本文針對(duì)古建筑信息模型在特征提取問(wèn)題，提出了一種基于互信息理論新的aIB算法．該算法引入層次凝聚思想，采用自底向上層次凝聚思想，將所有的點(diǎn)云數(shù)據(jù)作為特征點(diǎn)，利用模擬逐層凝聚，將相似的點(diǎn)云數(shù)據(jù)集聚，提高了點(diǎn)云數(shù)據(jù)特征提取的準(zhǔn)確度．引入互信息，提出一種信息瓶頸算法，使用法向量作為相關(guān)變量信息，在提取特征點(diǎn)是盡可能的保持法向量和數(shù)據(jù)對(duì)象之間的互信息，即使用互信息度量任意兩個(gè)點(diǎn)云數(shù)據(jù)對(duì)象合并的代價(jià)，保留最佳的數(shù)據(jù)對(duì)象到特征集中，這樣提取的特征點(diǎn)能夠盡可能地保留圖像內(nèi)部結(jié)構(gòu)特征信息．實(shí)驗(yàn)結(jié)果顯示該算法能夠有效地提高點(diǎn)云數(shù)據(jù)特征提取的精準(zhǔn)度，且在保存點(diǎn)云特征的同時(shí)能夠有效壓縮噪聲數(shù)據(jù)，能夠降低所需要處理的信息量，同時(shí)又能夠保留古建筑內(nèi)部結(jié)構(gòu)特征相關(guān)信息．與現(xiàn)有的基于非線性核回歸算法和基于圖像處理的檢測(cè)算法相比，本文算法檢測(cè)出的特征點(diǎn)部位更加廣泛，更加適應(yīng)于復(fù)雜部位點(diǎn)云特征提?。?/p>

本文采用自底向上層次凝聚的古建筑信息模型特征提取算法，每一次迭代合并過(guò)程中，算法都需要計(jì)算、比較所有的特征對(duì)象合并代價(jià)，如果想得到一個(gè)最優(yōu)解，其算法時(shí)間復(fù)雜度，將呈指數(shù)增長(zhǎng)．因此，下一步的工作將優(yōu)化算法，降低算法時(shí)間復(fù)雜度．

References

[1] 李健,王宗敏,馬玉榮等.多站激光點(diǎn)云數(shù)據(jù)全自動(dòng)高精度拼接方法研究[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）,2014,26(9):41-42.

[2] 孫殿柱,崔傳輝,康新才等.基于散亂點(diǎn)云數(shù)據(jù)的五軸數(shù)控加工刀軌生成算法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2012,43(5):226-229

[3] 吳賓,余柏蒗,岳文輝等.一種基于車載激光掃描點(diǎn)云數(shù)據(jù)的單株行道樹信息提取方法[J].華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版）,2013,(2):38-49

[4] 宮鈺嵩, 張巖, 文艷,等. Kinect掃描數(shù)據(jù)驅(qū)動(dòng)的幾何建模方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2014,(11):1957-1965.

[5] 胡鑫,習(xí)俊通,金燁等.反求工程中散亂點(diǎn)云數(shù)據(jù)的自動(dòng)分割與曲面重構(gòu)[J].上海交通大學(xué)學(xué)報(bào),2014,38(1):62-65

[6] 徐偉恒,馮仲科,蘇志芳等.一種基于三維激光點(diǎn)云數(shù)據(jù)的單木樹冠投影面積和樹冠體積自動(dòng)提取算法[J].光譜學(xué)與光譜分析,2014, 24(2):465-471

[7] 張德強(qiáng),牛興林,程杰等.汽車散熱蓋模具點(diǎn)云數(shù)據(jù)曲面逆向重構(gòu)技術(shù)研究[J].機(jī)械設(shè)計(jì)與制造,2014,(7):243-245

[8] 鄒萬(wàn)紅, 陳志楊, 葉修梓,等. 一種新的點(diǎn)云數(shù)據(jù)特征骨架提取方法[J]. 浙江大學(xué)學(xué)報(bào)：工學(xué)版, 2008,42(12):2103-2107.

[9] 郝泳濤, 肖文生, 胡雅俊. 離散點(diǎn)云數(shù)據(jù)的小波變換處理算法[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版, 2009,37(5):674-679.

[10] 張量,姜曉峰.基于線元幾何的旋轉(zhuǎn)面點(diǎn)云數(shù)據(jù)旋轉(zhuǎn)軸提取算法[J].計(jì)算機(jī)研究與發(fā)展,2009,46(10):1737-1742.

[11] 王茹,周明全,邢毓華等.基于聚類平面特征的三維點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法[J].計(jì)算機(jī)工程,2011,37(10):249-251.

[12] 程效軍, 賈東峰, 劉燕萍. 海量點(diǎn)云數(shù)據(jù)輪廓特征線的快速生成算法[J]. 同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版, 2012,40(10):1559-1563.

[13] 王小超, 劉秀平, 李寶軍,等. 基于局部重建的點(diǎn)云特征點(diǎn)提取[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013,25(5):659-665.

[14] OOZTIRELI A C, GUENNEBAUD G., Gross M. Feature preserving point set surfaces based on non-linear kernel regression[J].Computer Graphics Forum, 2009, 28(2):493–501.

[15] ZHU A L, SHORTRIDGE A, LUSCH D, et al. Feature extraction from 3D LiDAR point clouds using image processing methods[J]. Proceedings of SPIE - The International Society for Optical Engineering, 2011,8159(5):361-372.