基于体素构造和遗传算法的三维模型检索

白 柳， 宋超超

(1. 山西工程职业技术学院机械系，山西 太原 030009；2. 中国矿业大学(北京)机电与信息工程学院，北京 100083)

基于体素构造和遗传算法的三维模型检索

白 柳1， 宋超超2

(1. 山西工程职业技术学院机械系，山西 太原 030009；2. 中国矿业大学(北京)机电与信息工程学院，北京 100083)

以体素构造三维模型原理为基础，阐述了体素的几何信息和体素间的拓扑关系及基准问题，建立了三维模型特征提取函数，并对其旋转、平移和尺寸变化进行了经典不变矩处理，提出了一种基于体素构造和遗传算法的三维模型检索方法。该方法通过对遗传信息编码，以及迭代中的遗传信息交叉与变异，减小了检索区域的收敛速度，提高了检索准确率和检索速度。

体素构造；遗传算法；特征提取；检索

随着计算机辅助设计技术的飞速发展，三维模型应用的领域变得越来越广泛，其数量呈几何式快速增长。研究表明，约有 80%的模型是在原有模型的基础上进行小范围的改动，甚至是对原有模型的重用[1]。因此，如何快速、准确地获得相似度高的三维模型，是提高设计效率、缩短新产品研发周期的有效手段。三维模型检索过程一般可分为：①提取目标三维模型的检索特征；②根据所提取的检索特征确立唯一的特征函数；③与检索库中的三维模型进行逐个比对；④根据特征相似度，按照由高到低的顺序，排列出检索到的三维模型。因此，如何有效地提取目标三维模型的检索特征、提高特征函数的确定性、增强检索结果的准确性、缩短检索时间，是三维模型检索过程中要解决的关键问题。现有三维模型的特征信息都是由几何信息和拓扑信息组成的，其几何信息和拓扑信息的融合匹配检索，是一种特征检索重复度很低的三维模型检索方式[2]。本文基于体素构造和遗传算法，提出了一种有别于蚁群算法、形态分布算法的三维模型检索方法。与遗传算法相比，蚁群算法的局部搜索能力较弱，容易出现检索停滞、局部收敛和收敛速度过慢等情况，从而产生三维模型的具体细节检索不到位、检索成本较高等问题。与遗传算法相比，形态分布算法缺乏具体的数学模型，当三维模型出现旋转或者尺寸成比例变化时，其检索结果可靠性较低。本文阐述的检索特点在于描述三维模型的几何信息和拓扑信息，提取三维模型特征，建立特征函数，并对特征函数进行不变矩处理，最后利用遗传算法检索，匹配到最优的三维模型。

1 体素构造三维模型

任何一个复杂的三维模型都可以看作是由 n个最为简单的基本体，经过有序的布尔运算构成的，这些最简单的基本体称为体素。体素包括长方体、圆柱体、球体、楔形体、圆锥体和圆环体6种基本类型。

在利用计算机进行辅助设计时，可运用体素构造三维模型方法提高设计的效率。任意一个复杂的三维模型，只需要确定其各个体素形状的尺寸以及在空间中的相对位置，再辅以(n-1)个布尔算子来表示每一个体素加入整体三维模型的方式，就可以得到完整的三维模型几何特征信息和拓扑特征信息[3]。

1.1 三维模型几何信息特征

根据自身构成特点，每一种体素拥有各自的几何参数特征。

(1) 长方体：长a1、宽b1、高h1、基准为指定的定点位置；

(2) 圆柱体：半径 r2、高 h2，基准为一端面圆心；

(3) 球体：半径r3，基准为球心；

(4) 楔形体：毗邻直角的三边长(a4、b4、c4)，基准为其中一个直角点位置；

(5) 圆锥体：底面半径r5，高h5，基准为底面圆心；

(6) 圆环体：圆环体中心圆半径r6，截面圆半径r7，基准为中心圆半径所在的圆心。

1.2 三维模型拓扑信息特征

根据具体三维模型的结构特点，将孤立的体素进行有效地组合，确定体素之间的相对位置关系和具体体素数量。为了有序地组合基本体素，形成有实际需求的具体三维模型，需要引入布尔运算。在建模过程中，布尔运算是通过对2个及2个以上的体素进行并集、差集、交集运算，从而得到新的模型。一般采用布尔运算的树状结构图来形象、直观地表现三维模型各个体素间的数量关系及拓扑关系[4]。三维模型树状结构示例如图1所示。

图1 三维模型树状结构

根据上述体素的布尔运算，可得到体素与复杂三维模型的关系——体素拓扑关系树其中，Pi为描述基于三维模型树状结构图中第i个体素和第i-1个体素的拓扑关系子向量。

在确定了体素组合关系的基础上，需进一步确定各体素基准点相对于三维模型的具体位置。体素基准关系包含拓扑关系特征的各个体素基准向量，其表示为

根据上文所述，体素拓扑关系树 P与体素基准关系D共同决定了三维模型拓扑信息特征。

2 三维模型特征提取

在三维模型特征提取过程中，定义三维模型的几何信息特征为X，拓扑信息特征为Y。因此，三维模型的特征信息可以描述为关于几何特征信息X和拓扑特征信息Y的函数F(X,Y)。

在统计学中矩用来表示随机变量的分布情况，而在物理学中用来表示物体在三维空间中的分布位置。如果把三维模型看作是体素在三维空间中带有布尔运算的有序分布，那么三维模型的特征就可以用矩来描述[5]。F(X,Y)的n+m阶矩定义为

由此可知，pmn和F(X,Y)存在唯一确定的关系。F(X,Y)的m+n阶中心距定义为

F(X,Y)的 m+n阶中心距的中心坐标为(X,Y)。F(X,Y)归一化的中心矩可表示为

其中，u为F(X,Y)的0阶中心距；m≥1；n≥1。

在三维模型的检索过程中，F(X,Y)归一化的中心矩主要讨论其二阶矩和三阶矩，即在二维平面(m+n=2)、三维空间(m+n=3)的问题[6]。针对三维模型检索中出现的旋转、平移和尺寸变化的情况，用以下7个经典不变矩组作处理运算[7]

3 遗传算法在三维模型检索中的应用

在对三维模型提取的几何特征信息和拓扑特征信息函数进行不变矩处理后，可得到如下的一组特征向量

在容量较大的三维模型库中，由于平移、旋转和尺度变化等影响因素的存在，能够检索出相似度较高的三维模型是非常困难的。因此，本文在体素构造三维模型原理的基础上，提出了利用遗传算法寻优程序检索最优匹配三维模型的方法。遗传算法寻优程序能够在设定的搜索范围内自适应地搜索出最优解，尤其是在这种高维度空间内进行检索，能够有效地改善检索结果，缩短检索时间[8]。

3.1 遗传编码

根据遗传算法模拟生物遗传变异的特点，针对三维模型几何特征信息和拓扑特征信息，选用二进制遗传编码形式进行编码[9]，具有简单、方便、符合最小二进制字符集编码原则的优点。几何特征信息和拓扑特征信息对三维模型的影响，可以用 F(X,Y)归一化的中心矩 ρmn来表示。染色体C=(c1,c2,c3,…,cL)，是由ρmn二进制转换得到的长度为L的向量，其中向量元素c∈{0,1}。

3.2 适应度函数选择

适应度是用来衡量种群中个体优劣的指标。在遗传算法中，适应度函数是通过比较排序来计算选择概率的，所以适应度函数值为正值。在检索三维模型时，遗传算法在寻优过程中能够通过不断地自动修正其参数值，得到最优选择，即对于个体的优劣评判具有运算自适应性。其适应度函数g(x)为

根据本文实例应用中的具体要求，a值取0.5，b值为minF(x)，β值取2，α值取0.5。当α等于0.5时，适应度函数值能够较为快速地反映出目标函数的变化情况，在算法运行后期，可以有效地拉开最优解附近点的适应度值，防止过早收敛，便于在较大范围内检索匹配度最高的三维模型。

3.3 遗传过程中的交叉与变异

遗传过程中交叉的意义在于产生新的拓扑特征信息，探测检索区域里新的匹配三维模型。遗传过程中变异能够恢复丢失的遗传信息，产生新的遗传信息，保持检索区域个体的多样性，有效地防止算法过早收敛[9]。

3.4 遗传算法步骤

利用遗传算法进行三维模型检索，其具体算法步骤如下：

步骤1.T=0 ( T代表进化代数)；

步骤2. 对三维模型中心距参数ρmn进行编码；

步骤3. 随机选择初试种群P(T)；

步骤4. 个体的适应度函数g(x)；

步骤5. 判别遗传算法的终止条件(终止条件为达到最大的遗传代数或者超过进化要求的偏差)是否满足，若满足则直接进行最后一步；

步骤6.T=T+1；

步骤7. 应用选择算子在P(T-1)中选择P(T)；

步骤8. 对P(T)进行交叉、变异操作，获得新的遗传信息后转向步骤4；

步骤9. 输出最优的中心矩参数ρmn，进而得到最优三维模型几何信息和拓扑信息，然后对零件库中的三维模型进行测试以获得最优检索结果[10]。

4 应用实例与对比分析

三维模型检索实验是在Open CASCADE平台下的CAD三维模型库中进行的，检索资源涉及到500多个三维模型。选择库中的一种胀紧联接套作为检索目标，遗传算法检索参数设置如下：染色体种群规模Spop=300，交叉概率Pcros=0.5，变异概率Pmu=0.1t，最大迭代次数maxiter=500。

其相似度大于0.1的检索结果如图2所示，在三维模型检索库容量较大的情况下，依然能够检索到相似度比较高的三维模型。编号01的三维模型与目标三维模型相比较，都是含有环状分布的圆柱、两个半径不同的圆环体的 3段结构，具有非常高的相似特征和局部结构的重复度。编号 12的三维模型在图中相似度最低，主要是由于在特征提取过程中，环状分布的圆柱布尔运算从并集运算变异为差集运算。

在相同的检索条件下，查全率分别为 10%、20%、50%、80%、100%时，遗传算法、蚁群算法、形态分布算法分别检索到的最优相似度三维模型如图3所示[1,11]。从检索的相似度值分析，在查全率为10%时，即只在Open CASCADE库中检索50多个三维模型，3种方法能够检索到相同的最优三维模型。当查全率增高时，蚁群算法和形态分布算法检索到的最优模型相似度比遗传算法低。由此可知，在检索范围变大、检索特征信息干扰因素增多的情况下，遗传算法相比于其他两种检索方法，具有更可靠的特征提取匹配性能。

图2 遗传算法检索结果

图3 3种算法检索结果比较

为了进一步验证遗传算法在三维模型检索过程中的实用价值，采用了最为常用的查全率-查准率、查全率-检索时间作为检索结果的评价依据，其结果分别如图4～5所示。

图4 查全率-查准率

图5 查全率-检索时间

由图 4～5可知，相比于蚁群算法和形态分布算法，遗传算法具有更准确的检索结果和更高的检索效率，但是在查全率较低的范围内，其查准率与检索时间并不具有明显优势。

5 结 束 语

本文根据三维模型的体素构造原理和遗传算法寻优程序，提出了一种新的三维模型检索方法。该方法在体素构造原理的基础上，利用三维模型的几何特征信息和拓扑特征信息，提取三维模型的特征函数，并根据检索过程中出现的模型平移、旋转、尺寸变化等情况，对特征函数进行不变矩处理，最后利用遗传算法实现三维模型的最优相似度检索。实验结果表明，在相同的检索条件下，遗传算法的查准率和检索时间都优于蚁群算法、形态分布算法等其他检索算法。因此，在三维模型检索领域，基于体素构造和遗传算法的三维模型检索方法具有更高的效率和可靠性能。

[1] 张开兴, 张树生, 李 亮. 基于蚁群算法的三维CAD模型检索[J]. 计算机辅助设计与图形学学报, 2011, 23(4): 633-639.

[2] Stavropoulos G, Moschonas P, Moustakas K, et al. 3-D model search and retrieval from range images using salient features [J]. IEEE Transactions on Multimedia, 2010, 12(7): 692-704.

[3] 张申生. 基于单元分解的实体构造几何技术(CDCSG)——一种构造试题模型的新方法[J]. 计算机辅助设计与图形学学报, 1990, 1(2): 14-23.

[4] 邓念东, 侯恩科, 张志华, 等. 三维拓扑关系形式化描述及拓扑关系模型研究[J]. 西安建筑科技大学学报, 2007, 39(6): 873-877.

[5] 邵 红, 崔文成, 张继武, 等. 遗传算法在基于内容的图像检索中的应用[J]. 计算机工程, 2003, 29(16): 21-22.

[6] Chen C, Leng B, Xiong Z. A stable viewing strategy for rotation normalization free 3D model retrieval [J]. Procedia Environmental Sciences, 2011, 10(Part A): 613-621.

[7] 何 青, 杜永祚, 宋之平. 一种实用的不变矩计算方法[J]. 华北电力大学学报, 1998, 25(4): 80-83.

[8] 李 亮, 张树生, 白晓亮, 等. 基于遗传算法的三维CAD模型多特征融合和检索[J]. 制造业自动化, 2013, 35(2): 78-81.

[9] 沈 艳, 郭 兵, 古天祥. 粒子群优化算法及其与遗传算法的比较[J]. 电子科技大学学报, 2005, 34(5): 696-699.

[10] Ding B, Zhang Z, Yu X Y, et al. 3D CAD model retrieval based on GA-ACO [C]//Ulaanbaatar. Strategic Technology (IFOST). New York: IEEE Press, 2013: 36-41.

[11] 朱文博, 吴新仁, 甘 屹. 基于形状拆分的机械零件三维模型检索[J]. 图学学报, 2015, 36(1): 35-40.

3D Model Retrieval Based on CGS and Genetic Algorithm

Bai Liu1, Song Chaochao2
(1. Department of Mechanical Engineering, Shanxi Engineering Vocation Technology College, Taiyuan Shanxi 030009, China; 2. College of Mechanical Electrical and Information Engineering, China University of Mining and Technology (Beijing), Beijing 100083, China)

The voxels structure principle of 3D model as the foundation, expounds the voxel geometry information and body elements of topological relations and benchmark problems, establish the 3D model feature extraction function and of its rotation, translation and size changes of classic moment invariant processing, put forward a based on voxel structure and genetic algorithm of 3D model retrieval method. This method reduces the convergence speed of the search area and improves the retrieval accuracy and retrieval speed by the genetic information encoding, the genetic information in the iteration and the variation of the genetic information.

constructice solid geometry; genetic algorithm; feature extraction; retrieval

TH 128；TB 23

10.11996/JG.j.2095-302X.2016060754

A

2095-302X(2016)06-0754-05

2016-01-25；定稿日期：2016-05-24

白 柳(1964−)，女，山西太谷人，副教授，硕士。主要研究方向为工程图学、CAD/CAM 应用等。E-mail：sxtybliu@163.com