面向制造领域的三视图模型组件快速检索方法研究*

周 燕，曾凡智，卢炎生，周月霞

(1.佛山科学技术学院 计算机系，广东 佛山 528000；2.华中科技大学 计算机学院，湖北 武汉 430074)

随着3D模型建模、数字化、可视化技术的进步，三维模型在机械设计和制造领域的应用越来越广泛，由此产生了海量的产品模型及组件。如何有效地实现面向制造领域的存储、检索与重用这些模型组件，从而达到降低设计成本和缩短产品研发周期，已成为目前制造行业的一个研究热点。随着三维模型组件数量的不断激增，现有搜索引擎难以满足三维模型快速检索要求，迫切需要一种高效的检索方法。基于内容的三维模型检索(content based 3D model retrieval)应运而生[1-10]，从三维模型的基础数据出发，提取能描述其外观等基于内容的特征信息，该技术不仅可用在三维模型的检索，也用于三维物体形状分析、识别与分类。

目前对三维模型的特征提取方法主要有：基于统计的特征提取、基于扩展的特征提取、基于体积的特征提取、基于曲面几何特征提取、基于视图的特征提取、基于图的特征提取等[7-8]，这些方法目前还无法从理论上验证它们对模型特征描述的精确度，更多的是通过查准率和查全率来判断其优劣。特别地，如没有考虑三维深度信息、所提取特征不能完全表达三维模型信息、用户交互操作较难实现。本文结合压缩感知理论和图像检索技术[11-16]，提出一种面向制造领域的三视图模型组件检索方法。首先获得模型库中组件的三视图，然后采用压缩感知方法提取三视图的颜色、纹理等特征并将特征向量存入模型库。其次，检索时提取待检索图像的三视图特征并与模型库中的组件特征进行相似性匹配，最后，结合中心点的压缩测量特征，计算组件的整体相似度并输出检索结果。算法的核心在于首先计算单个视图之间的相似度，然后通过正、侧、俯视图像的相似度估算出组件的整体相似度。

1 压缩感知理论

2)选择测量矩阵：ΦM×N，(M≪N)

y=Φx=ΦΨa=Θa

(1)

称y为x的测量值。

3)当M≪N时，对问题(1)由y计算出a并得到原始信号x是一个未定问题，但当Θ满足RIP条件时[11]，即对任意x是K稀疏的，如果满足下列公式：

通过重构系数a可以恢复原始信号x，其中δk称为限制等容系数。其解为下列优化问题：

(2)

(3)

问题(3)是一个线性凸优化问题，已经研究了各类算法如单纯形法、基于贪婪迭代MP算法、正交匹配追踪(Orthogonal Matching Pursuit, OMP)算法、稀疏自适应匹配追踪(Sparsity Adaptive Matching Pursuit, SAMP)算法等加以求解[ 17-18]。

上述压缩感知理论说明，只要选取合适的Ф，就能把一个高维的可稀疏信号x∈RN用一个低维测量值y∈RM表示，并且能够重构原始信号。这意味着用测量值可以代表原始信号x的压缩感知特征，本文称y为原始信号x的压缩测量特征。

2 图像压缩感知测量值提取

2.1 基于行列方式的压缩感知测量

文献[15]对压缩感知理论应用于图像快速检索做了有益的探索，其核心思想是把图像的颜色、纹理等特征按照行或者列优先次序形成一个高维列向量，然后采用公式(1)进行压缩测量得到测量值y，通过测量值y进行图像相似度检索，取得了较好的检索效果。如果能更进一步考虑图像中像素点之间的行、列之间的特征联系及位置关系，使其根据图像特征所计算的测量值y代表性更全面，应该能达到更好的检索效果。

针对这一新的思想，以下提出一种基于行列的压缩感知测量过程，同时考虑行、列的相对位置关系，从而提取图像的测量值作为压缩测量特征，其测量过程如下：

1)设X是N×N矩阵，代表图像相应特征的原始二维信号量，记XN×N=(xij)N×N；

2)设Xi=(x1i,x2i,...,xNi)T为矩阵X的第i列构成的列向量。

3)矩阵X可表达为：X=(X1,X2,...,XN)。

4)选取测量矩阵：ΦM×N=(Φ1,Φ2,...,ΦN)，其中Φi∈RM，测量矩阵ΦM×N的选取可参考文献[19]中描述的构造方式生成高斯随机矩阵作为测量矩阵。

(4)

其中：

1)当M≪N时，采用以上的测量过程(4)，能够把一个高维的N×N原始信号压缩到一个低维的M×M的测量值。实际应用时，行、列测量矩阵的选取可以是不同的测量矩阵。

2)由于图像在小波变换、DCT变换等变换下具有可稀疏性，根据第1节中4)的结论，当Ф满足相应RIP条件时，由产生的测量值YM×M能够恢复原始信号XN×N。

3)对公式(4)产生的测量矩阵YM×M称之为原始二维信号X的压缩感知测量特征，记为：

Y=CS(Φ,X)

(5)

其中XN×N∈mN×N(R)，ΦM×N∈mM×N(R)，YM×M∈mM×M(R),mN×N(R)代表实数域R上的N×N矩阵集合。

2.2 图像分块压缩感知测量特征提取

采用分块方法提取整幅图像的特征。设原始图像大小为L×L，采用N×N像素的小分块对原始图像进行分块，如图1所示。分块行、列数为B=L/N，则分块总数为H=B2。

图1 图像分块示意图Fig.1 The schematic diagram of image block

对于分块采用从左到右、从上到下进行编号，把第i行第j列分块记为Dij，则

Dij={(x,y)|(i-1)*N+1≤x≤i*N,

(j-1)*N+1≤y≤j*N且x,y都为整数}

1)针对Dij分块，与其分块相关的各类特征值如颜色R(红)、颜色G(绿)、颜色B(蓝)，纹理等特征都是定义在Dij的一个映射.

三个颜色映射：

(6)

纹理映射：

其中：对于纹理特征映射，选取如下方式：

P(i,j)=#{(x1,y1)∈Dij|f(x1,y1)=f(i,j)}，其中(i,j)∈Dij。

f(x,y)为二维数字图像的灰度函数，级别为Ng，P(i,j)代表空间关系的灰度共生矩阵。颜色特征映射类似。

2)对于Dij上的某类特征如红色分量R，通过以下映射形成一个N×N的原始信号表示的矩阵。

定义域Dij上与红色分量特征有关的映射如下：

(7)

其中:

MR=(MRlh)N×N;

MRlh=R((i-1)*N+l,(j-1*N+h))

1≤l,h≤N,函数R(·,·)由(6)给出。

类似地，可以定义与其他特征相关的映射：

(8)

(9)

(10)

3)对于Dij分块，原始信号包含了颜色(R、G、B)、纹理等相关信号，采用公式(7)-(10)分别得到N×N的各类原始信号，采用公式(5)得到M×M的各类压缩测量特征值。颜色相关的三个测量特征如下：

RYij=CS(Φ,MR(Dij,R(·,·)))

(11)

BYij=CS(Φ,MB(Dij,B(·,·)))

(12)

GYij=CS(Φ,MG(Dij,G(·,·)))

(13)

公式(11)、(12)、(13)分别代表红、蓝、绿三类颜色的压缩感知测量特征。

纹理相关的测量特征如下：

PYij=CS(Φ,MP(Dij,P(·,·)))

(14)

其中，在(11)-(14)中，i,j=1...B。

2.3 中心点相关的压缩感知测量特征

以P0(x0,y0)为中心，以D00作为原始信号的选取窗口。在该观察窗口上，采用公式(5)得到颜色、纹理等原始信号的压缩感知测量特征，记：

RY00=CS(Φ,MR(D00,R(·,·)))

(15)

BY00=CS(Φ,MB(D00,B(·,·)))

(16)

GY00=CS(Φ,MG(D00,G(·,·)))

(17)

PY00=CS(Φ,MP(D00,P(·,·)))

(18)

3 基于三视图的模型组件检索方法

在工业设计、艺术设计等领域中，由组件或者零件的正、侧、俯视图能够唯一确定一个组件的立体图形。因此，要检索具有相似的两个组件或者零件，只需要比较其相应三视图的相似性，从而检索出具有相似特征的组件或零件。检索算法的核心是：首先给出单个视图之间的相似度，然后通过正、侧、俯视图像的相似度估算出组件的整体相似度。

1)计算两幅三视图图像之间的相似度。

采用以下算法计算两个组件相对应的视图之间的相似度。

算法1 计算两幅视图之间相似度算法。

输入：测量矩阵Ф。

输出：视图图像T,T′的相似度D(T,T′)。

方法：

STEP1对两幅图像按照第2.2节描述方式进行分割；

STEP3按照公式(11)-(14)分别计算T,T′的颜色、纹理压缩测量特征：

RYij=CS(Φ,MR(Dij,R(·,·)))

BYij=CS(Φ,MB(Dij,B(·,·)))

GYij=CS(Φ,MG(Dij,G(·,·)))

PYij=CS(Φ,MP(Dij,P(·,·)))

(i,j=0...B)

STEP4计算并归一化处理：

STEP5计算两幅图像T,T′的相似度，输出：

D(T,T′)=ε1LR+ε2LB+ε3LG+ε4LP。

2)检索两个三维模型组件匹配算法。

对于两个三维模型组件，采用基于三视图进行检索时，使用如图3表示的检索框架。

图3 三维模型检索总体框架Fig.3 The overall framework for three-dimensional model retrieval

算法2 三维模型组件匹配算法。

输入：测量矩阵Ф。

输出：相似度满足要求的检索组件Z2。

初始化：设定两组件Z1、Z2。Z1是待检索组件，Z2是库中任意组件。设定加权系数：ε1、ε2、ε3、ε。

方法：

STEP1设Z1的正、侧、俯图像分别记为ZZ1、CZ1、FZ1，Z2组件的正、侧、俯图像分别记为ZZ2、CZ2、FZ2。

STEP2 按照视图图像间相似度算法1分别计算三个值：

L1=D(ZZ1,ZZ2)

L2=D(CZ1,CZ2)

L3=D(FZ1,FZ2)

STEP3计算组件间的整体相似度：

STEP4输出满足HD≤ε条件的库中前32幅组件Z2。

以上方法根据三视图可以唯一决定组件立体形状的原理，以三视图中相对应的两幅视图的相似度计算为基础，给出整体组件的相似度。当相似度满足阀值ε时，作为组件检索的结果，最后采用降序原则进行排序。

在本文的仿真试验中，对算法2分别选取ε1=0.4、ε2=0.3、ε3=0.3、ε=0.02。

4 仿真实验

本文实验数据包含机械CAD设计组件图、机械制造零件图、艺术设计图、陶瓷设计图、组合实物等共1 000套三维模型数据。在 Visual Studio 2008 环境下，对各种模型应用本文算法进行检索可看出，本文算法具有较好的检索结果。并从查全率、查准率这两个性能指标进行评价，同时与其它三维图像检索算法进行比较。

4.1 检索结果

选择机械制造零件类和组合实物类三维图像作为待检索图像(图4)。由三维图像得到相应的三视图(图5)，并以正、侧、俯视图作为待检索图像，分别检索出相似度排序前32幅图像作为检索结果。然后，基于三视图的综合相似度，检索出三维图的检索结果，从图中检索结果图可以看出，检索效果优良，查全率和查准率高。见图6-图9。

1)机械制造零件三维图检索效果。

图4 机械制造零件的三维图Fig.4 The three-dimensional figure for machinery manufacturing parts

图5 机械制造零件的三视图Fig.5 The three-view figure for machinery manufacturing parts

图6 机械制造零件的检索结果Fig.6 The retrieval result of machinery manufacturing parts

2)组合实物三维实体图检索效果。

图7 组合实物三维实体图Fig.7 The three-dimensional figure for combination physical

图8 组合实物的三视图Fig.8 The three-view figure for combination physical

按照机械制造零件三维图相同的检索方法，得到组合实物三维图的检索结果如图9所示。

图9 组合实物三维图的检索结果Fig.9 The retrieval result of three-dimensional figure for combination physical

4.2 性能分析

1) 鲁棒性测试结果分析。对三维模型沿X、Y、Z轴随机地进行平移、旋转和缩放后进行检索，得到的鲁棒性测试结果如图10所示。从图中看到，本文算法对三维模型的缩放、旋转和平移具有较好的鲁棒性。

图10 鲁棒性测试结果对比Fig.10 The comparison of robustness test result

2)查全率、查准率分析。本文算法与文献[9]、文献[10]进行比较，结果如图11所示。从中可以看出，本文算法检索的查全率和查准率优于文献[9]和文献[10]。

图11 查全率、查准率对比分析Fig.11 The comparative analysis for recall and precision

5 结 论

三维模型检索是计算机图形学、机器视觉和模式识别领域中一个活跃的研究方向。本文应用压缩感知理论结合图像的特征，给出了一种基于行列与中心点的压缩感知测量过程得到压缩感知特征值，提出一种面向制造领域的三视图模型组件检索方案。算法首先计算模型的正、侧、俯视图像的相似度，然后通过加权求和进行融合，得到总体上模型间的相似度，在提高检索准确率的同时，也能保证检索效率。三维模型检索可以广泛应用在计算机辅助设计、分子生物学、机器人、军事、虚拟地理环境等多个领域，并且在电子商务和搜索引擎的研究中也将有广阔的应用前景。

[1] 徐士彪,车武军,张晓鹏. 基于形状特征的三维模型检索技术综述[J]. 中国体视学与图像分析,2010,4:439-450.

[2] 黄瑞,张树生,白晓亮,等. 融合制造语义的三维CAD模型检索方法[J]. 计算机集成制造系统,2013,19(6):1177-1185.

[3] 王小凤,张飞,耿国华,等. 一个基于深度图像的三维模型检索算法[J]. 计算机工程与应用,2012,48(7):197-200.

[4] 王羡慧,覃征,庄春晓,等. 基于差异特征协同语义标注的三维模型检索方法[J]. 计算机辅助设计与图形学学报,2011,23(1): 152-160.

[5] 郑赢,周明全,耿国华,等. 多特征动态融合的三维模型检索方法[J]. 计算机科学,2010,37(7):260-263.

[6] 王小凤,耿国华,张飞. 一个相关反馈三维模型深度图像检索算法[J]. 计算机应用研究,2012,29(6):2350-2353.

[7] HORN B K. Extended gaussian images [J]. Proceeding of the IEEE, 1984, 72(12): 1671-1686.

[8] HECZKO M, KEIM D A, DIETMAR S D, et al. Methods for similarity search on 3D databases [J]. Databank Spec-trum, 2002, 2(2): 54-63.

[9] GAO Yue, DAI Qionghai, WANG Meng, et al. 3D model retrieval using weighted bipartite graph matching[J]. Image Communi,2011,26(1):39-47.

[10] ADAN A, MERCHAN P, SALAMANCA S. 3D scene retrieval and recognition with depth gradient images[J]. Pattern Recognition Letters,2011,32(9):1337-1353.

[11] DONOHO D. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[12] CANDES E, WAKIN M. An introduction to compressive sampling [J]. IEEE Signal Processing Magazine, 2008, 25(2): 21-30.

[13] TANER I, ARIF N, NURDAL W. Nonconvex compressed sensing with partially known signal support [J].Signal Processing, 2013, 93(1):338-344.

[14] 许志强. 压缩感知[J]. 中国科学:数学,2012,42(9): 865-877.

[15] 周燕,曾凡智,卢炎生, 等.基于压缩感知的图像检索方法研究[J]. 中山大学学报:自然科学版,2014,53(1):57-62.

[16] 方艳梅,杨灿,肖自美,等.基于内容图像检索系统的性能改进方法[J]. 中山大学学报:自然科学版,2001,40(6):39-43.

[17] 杨海蓉,张成,末为,等.压缩传感理论与重构算法[J].电子学报,2011,39(1):142-148.

[18] 甘伟,许录平,罗楠,等.一种自适应压缩感知重构算法[J]. 系统工程与电子技术,2011,33(9):1948-1953.

[19] 曾凡智,卢炎生,周燕 . 基于压缩传感的半脆弱水印的视频篡检测算法[J]. 电路与系统学报,2011,16(4):86-93.