宋 陽，李昌華，馬宗方，李智杰

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

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

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

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

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

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

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

1 互信息原理

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

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

2 基于aIB的古建筑信息模型特征提取算法設計

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

其中:

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

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

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

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

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

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

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

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

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

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

算法步驟：

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

3. While (|T|>1)

4. 對?t∈T,基于公式（5）計算

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

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

3 實驗及結果分析

3.1 實驗數(shù)據(jù)

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

3.2 實驗結果分析

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

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

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

本文是非線性核回歸算法和圖像處理算法對基師塔古建筑模型提取點云數(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算法提取點云數(shù)據(jù)特征，在盡可能的壓縮噪聲數(shù)據(jù)的同時能夠最大程度的保存模型特征，提取了241 002個特征點．如圖4所示．

具體的，三種算法運行結果如表1所示．

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

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

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

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

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

4 結語

古建筑信息模型特征提取是模型重建、古建筑恢復等關鍵前提，也是當前是計算機視覺、圖像理解等領域的重要課題之一．

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

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

References

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

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

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

[4] 宮鈺嵩, 張巖, 文艷,等. Kinect掃描數(shù)據(jù)驅動的幾何建模方法[J]. 計算機輔助設計與圖形學學報, 2014,(11):1957-1965.

[5] 胡鑫,習俊通,金燁等.反求工程中散亂點云數(shù)據(jù)的自動分割與曲面重構[J].上海交通大學學報,2014,38(1):62-65

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

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

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

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

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

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

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

[13] 王小超, 劉秀平, 李寶軍,等. 基于局部重建的點云特征點提取[J]. 計算機輔助設計與圖形學學報, 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.