aIB算法在古建筑信息模型特征提取中的应用与研究

宋 阳，李昌华，马宗方，李智杰

（1.西安建筑科技大学信息与控制工程学院，陕西 西安 710055 2.西安建筑科技大学建筑学院，陕西 西安 710055）

点云数据是通过三维激光扫描仪等获取的图形图像数据，准确地表达真实物体的表面信息[1-7]，形成建筑信息模型．古建筑传承了人类光辉灿烂的文明，凝聚了广大劳动人民的智慧结晶，成为了人类文明发展中活生生的化石，使用三维激光扫描仪记录古建筑，形成古建筑信息模型，为古建筑保护和研究提供详实可靠的基础数据，能够实现古建筑数字化保护．古建筑信息模型中的特征能够实现形状分析、数据表达，为点云数据处理提供充足的信息，古建筑信息模型特征获取的精准度能够影响信息恢复的有效性．古建筑信息模型特征提取可以去除噪声，简化特征描述，保持古建筑重建的重要信息，为古建筑保护和研究提供重要的参考依据．

目前，已有诸多学者展开了针对三维模型特征提取的研究，诞生了多种算法[8-13]．尽管建筑信息模型特征提取算法得到了广泛的研究和改进，但是经过分析，许多建筑信息模型特征提取算法存在以下问题：

（1）点云数据特征提取过程中，许多算法采用硬聚类或分类思想，因此一些算法非常武断的将点云数据划分为特征，这些特征中包含过多的噪声信息，并且不能够过滤掉，特征划分不准确．

（2）点云数据采集过程中，使用的仪器、模型物体和光照等客观原因，导致点云模型缺少连接信息，严重的存在特征点被遗漏，造成特征数据缺失，容易产生空洞．

因此，为了能够解决上述问题，本文基于互信息理论提出了一种新的 aIB算法（agglomerative Information Bottleneck，凝聚式信息瓶颈算法），该算法采用层次凝聚思想，在特征提取过程中尽量压缩点云数据，过滤噪声．为了验证本文算法的有效性，与基于非线性核回归的特征提取算法[14]和基于图像处理的点云特征提取算法[15]从特征点提取数量、算法运行时间等方面进行了比较，实验结果显示该算法能够有效地提高点云数据特征提取的精准度，并且降低了特征提取耗费时间．如图1所示．

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

1 互信息原理

互信息定义：给定随机变量x和y联合概率分布因此可以随机变量x和y之间的互信息可以为公式（1）：

互信息I(X;Y) 可以描述两个随机变量x和y相互包含的程度，如果则表示两个随机变量是独立的，二者互不包含，它们之间的互信息为零．

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

在古建筑信息模型特征提取过程中，为了能够更好地提取相关的点云数据，可以使用变量X描述原始古建筑点云数据集，使用相关变量Y描述法向量，两者之间的联合概率分布为满足在古建筑信息模型特征提取过程中，尽力的把源变量X集合中的元素划分到特征集合T中时，需要尽可能的保持法向量Y的信息，也就是需要最大化保持互信息I(X;Y)，因此基于互信息的点云数据特征提取原理如图2所示．

其中:

表示一个概率归一化函数，由于目标函数仅仅表示古建筑信息模型特征提取的形式解．

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

基于互信息的古建筑信息模型特征提取目标函数可以如公式（2）所示．

目标函数是一个关于自变量p(t|x)的函数，由于古建筑信息模型点云数据集是客观存在的，因此互信息I(X;Y) 是一个常量，在目标函数中可以忽略其变化；β是目标函数引入的一个拉格朗日因子，其可以在点云数据特征提取过程中尽可能的平衡互信息I(X;T) 和I(T;Y)，为了能够求解目标函数，可以引入马尔科夫链基于马尔科夫链的条件独立性关系，可以获取目标函数的解，具体如公式（3）所示．

古建筑信息模型特征提取过程中，本文引入了自底向上层次凝聚、互信息等理论，提出了一种aIB算法，该算法可以将原始点云数据集中的每一个数据集都作为一个特征点，使用互信息度量包含程度最大的两个特征点进行合并，也即是选择两个最为相似的数据点合并为一个数据点，直到将所有的数据点合并到一个特征簇中．具体的，aIB算法在古建筑信息模型特征提取中的形式化描述如下：原始数据集X中的每一个对象x都划分到特征集t中，其中t∈T，合并任意两个特征对象ti和tj，合并过程中使得T算是的互信息最小，也就是尽可能的保存I(T;Y)，直到将所有的特征对象合并到一个簇中．自底向上凝聚古建筑信息模型特征提取算法可以生成一棵层次树，该层次树针对数据集的可视化管理能够提供非常优越的便利条件．

在自底向上层次凝聚的古建筑信息模型特征提取算法aIB中，给定T中两个对象ti和tj，合并所产生的信息损失称为为合并代价，其可以定义为公式（4）：

其中，I(Tbefore,Y)和I(Tafter,Y)分别代表合并ti和tj前后的T和Y之间的互信息．进一步把式（4）规范化为公式（5）：

自底向上凝聚点云数据特征提取算法流程：

输入:联合分布p(x,y),平衡参数β.

输出:数据模式T.

算法步骤：

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

3. While (|T|>1)

4. 对∀t∈T,基于公式（5）计算

自底向上点云数据特征提取算法描述如下：

在自底向上层次凝聚的古建筑信息模型特征提取算法aIB中，每一次迭代合并过程中，算法都需要计算、比较所有的特征对象合并代价，以便能够选择合并代价最低的两个特征对象进行合并，因此点云数据特征提取算法运行中，假设算法执行为当前层Ti-1，算法将“最佳合并特征对象对”之后的层为Ti，因此可以得知程序控制的核心因子为自底向上层次凝聚的古建筑信息模型特征提取算法aIB在每一次合并过程中使得I(T;Y)最大化，其得到一个局部最优解．但是，这不能保证对每一个划分T都得到最优解，甚至对一个确定的T也不能得到最优解，此时自底向上古建筑信息模型特征提取的时间复杂度是如果想得到一个最优解，其算法时间复杂度，将呈指数级增长．

3 实验及结果分析

3.1 实验数据

本文实验环境采用Matlab2011平台，在实验过程中，算法是在一台Intel(R) Core(TM) i5-4590 CPU（主频为3.3GHz）、4G内存的台式机上运行．实验数据采用第一批全国重点文物保护单位西安市兴教寺的基师塔古建筑作为算法试验数据集，数据采集过程中使用瑞士徕卡C10便携式三维激光扫描仪进行扫描，扫描的点云数量共计为599 942个．

3.2 实验结果分析

基师塔古建筑模型原始点云数据点共计 599 942个，由于基师塔所在区域的光照、遮挡和扫描仪设备自身缺陷等导致获取的古建筑信息模型存在大量的噪声点，因此基师塔的特征数据点比较分散，为后期基师塔重建带来困难．如图3所示．

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

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

本文是非线性核回归算法和图像处理算法对基师塔古建筑模型提取点云数据特征效果如图 5-6所示．

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

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

本文使用aIB算法提取点云数据特征，在尽可能的压缩噪声数据的同时能够最大程度的保存模型特征，提取了241 002个特征点．如图4所示．

具体的，三种算法运行结果如表1所示．

表1 三种算法运行结果数据Tab.1 Three algorithms operating results data

通过分析，aIB算法能够在较短的时间内提取更多的点云数据特征点，特征检测能力较好．另外，非线性核回归算法和图像处理算法检测出的特征点多集中于基师塔数据的明显特征处，比如外轮廓，aIB算法检测的出特征点的部位更加广泛，除上述两种算法检测出特征点的部位之外，还包括塔檐边界线等特征，因此aIB算法更加适应于复杂部位点云特征提取．

本文aIB算法的创新点：

(1) 自动化确定β的取值．在aIB算法运行过程中，β因子是目标函数引入的一个拉格朗日因子，其可以在点云数据特征提取过程中尽可能的平衡互信息I(X;T)和I(T;Y)，确定β的取值需要用户掌握较多的点云数据应用背景与经验知识，以便能够更好地实现古建筑信息模型特征提取，提高特征提取精确度．本文算法基于层次凝聚思想，算法运行过程中可以自动排列互信息损失度，选择最少的互信息损失进行点云数据特征提取．

(2) 基于互信息I(T;Y)的进行特征提取．aIB算法运行时需要在尽可能的压缩互信息I(X;T)，同时最大化的保存互信息I(T;Y)，因此该算法扩展了互信息在模式识别、机器学习领域的应用，创新地提出保留点云数据特征的情况下压缩噪声数据，更好地实现特征点检测．

4 结语

古建筑信息模型特征提取是模型重建、古建筑恢复等关键前提，也是当前是计算机视觉、图像理解等领域的重要课题之一．

本文针对古建筑信息模型在特征提取问题，提出了一种基于互信息理论新的aIB算法．该算法引入层次凝聚思想，采用自底向上层次凝聚思想，将所有的点云数据作为特征点，利用模拟逐层凝聚，将相似的点云数据集聚，提高了点云数据特征提取的准确度．引入互信息，提出一种信息瓶颈算法，使用法向量作为相关变量信息，在提取特征点是尽可能的保持法向量和数据对象之间的互信息，即使用互信息度量任意两个点云数据对象合并的代价，保留最佳的数据对象到特征集中，这样提取的特征点能够尽可能地保留图像内部结构特征信息．实验结果显示该算法能够有效地提高点云数据特征提取的精准度，且在保存点云特征的同时能够有效压缩噪声数据，能够降低所需要处理的信息量，同时又能够保留古建筑内部结构特征相关信息．与现有的基于非线性核回归算法和基于图像处理的检测算法相比，本文算法检测出的特征点部位更加广泛，更加适应于复杂部位点云特征提取．

本文采用自底向上层次凝聚的古建筑信息模型特征提取算法，每一次迭代合并过程中，算法都需要计算、比较所有的特征对象合并代价，如果想得到一个最优解，其算法时间复杂度，将呈指数增长．因此，下一步的工作将优化算法，降低算法时间复杂度．

References

[1] 李健,王宗敏,马玉荣等.多站激光点云数据全自动高精度拼接方法研究[J].武汉大学学报（信息科学版）,2014,26(9):41-42.

[2] 孙殿柱,崔传辉,康新才等.基于散乱点云数据的五轴数控加工刀轨生成算法[J].农业机械学报,2012,43(5):226-229

[3] 吴宾,余柏蒗,岳文辉等.一种基于车载激光扫描点云数据的单株行道树信息提取方法[J].华东师范大学学报（自然科学版）,2013,(2):38-49

[4] 宫钰嵩, 张岩, 文艳,等. Kinect扫描数据驱动的几何建模方法[J]. 计算机辅助设计与图形学学报, 2014,(11):1957-1965.

[5] 胡鑫,习俊通,金烨等.反求工程中散乱点云数据的自动分割与曲面重构[J].上海交通大学学报,2014,38(1):62-65

[6] 徐伟恒,冯仲科,苏志芳等.一种基于三维激光点云数据的单木树冠投影面积和树冠体积自动提取算法[J].光谱学与光谱分析,2014, 24(2):465-471

[7] 张德强,牛兴林,程杰等.汽车散热盖模具点云数据曲面逆向重构技术研究[J].机械设计与制造,2014,(7):243-245

[8] 邹万红, 陈志杨, 叶修梓,等. 一种新的点云数据特征骨架提取方法[J]. 浙江大学学报：工学版, 2008,42(12):2103-2107.

[9] 郝泳涛, 肖文生, 胡雅俊. 离散点云数据的小波变换处理算法[J]. 同济大学学报：自然科学版, 2009,37(5):674-679.

[10] 张量,姜晓峰.基于线元几何的旋转面点云数据旋转轴提取算法[J].计算机研究与发展,2009,46(10):1737-1742.

[11] 王茹,周明全,邢毓华等.基于聚类平面特征的三维点云数据精简算法[J].计算机工程,2011,37(10):249-251.

[12] 程效军, 贾东峰, 刘燕萍. 海量点云数据轮廓特征线的快速生成算法[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.