石 民，张树生，李 亮，白晓亮

SHI Min, ZHANG Shu-sheng, LI Liang, BAI Xiao-liang

（西北工业大学 现代设计与集成制造技术教育部重点实验室，西安 710072）

0 引言

在目前的机械设计制造领域，基于三维模型的产品设计与制造已经成为当前的主流模式，被广泛应用在产品开发的各个环节（CAD、CAE、CAPP、CAM等）。统计数据表明，在新产品的研发过程中有超过75%的设计活动都是对已有的设计进行重用或微小修改[1]。基于内容的三维CAD模型检索技术能够帮助企业对已有的产品设计成果进行管理和重用，进而提高设计效率，缩短研发周期，并最终有效地提升企业的核心竞争力。

对于基于内容的三维模型CAD检索技术，它的关键问题之一是如何有效描述CAD模型的形状特征，其对于检索结果的精度和准度有着直接影响[2]。目前，基于视觉相似的三维模型检索算法被认为是检索效果最好的一类算法[3,4]，该类算法仿效了人类视觉对物体的认知过程，将三维模型表示为所对应的二维投影视图的集合。这样一来，两个三维模型之间的比较就转化为各自投影集合中所对应的二维投影视图之间的比较。如果所对应的二维投影视图都相似，则认为这两个模型相似。该类算法中最著名的为Chen等提出的光场算法[5]。然而，在使用投影视图对三维模型进行相似性匹配时，光场算法只是笼统地对视图集中的每一幅视图都同等看待，却忽视了不同视图在匹配过程中其实具有不同的重要性。相较于其它视图，模型的某些投影视图包含更多的信息，因而更能影响模型间的相似性匹配。从图1可以很明显地看出，螺丝刀的主视图相较于它的俯视图含有更多的信息，对于模型来说更具有代表性。因此，区别对待每个视图在模型相似性匹配过程中的重要程度是十分必要的。Li[6]等提出了一种基于二维投影视图最优权重的三维模型检索算法。该算法通过使用拉格朗日乘数子和支持向量机为视图配置权重，以达到区分不同视图重要性的目的。

本文提出一种基于二维典型视图的三维CAD模型检索算法，该算法通过从CAD模型二维投影视图集中甄选出其中具有代表性（即信息含量高）的视图， 将三维模型间的比较转化为各自典型视图间的相似性匹配。首先对一个三维CAD模型沿固定视角进行投影，获得相应的二维投影视图集；然后采用Apriori算法从中挖掘出具有代表性的视图作为该模型的典型视图； 最后通过比较模型各自对应的典型视图来获得三维模型间的相似性评价。

1 投影视图的获取

和其他基于视觉相似的检索算法一样， 在本文中，对三维模型的投影视角来自于平均分布在该模型球形包围盒工的顶点，为了能够获得足够多数量的投影视图作为典型视图的候选样本，同时又不会造成过大的计算负担，本文选用正八十面体的42个顶点作为投影视角。这样一来，一个三维模型将被表示为二维投影视图集合I ={i1, i2,...i42}。

对于一幅投影视图i，使用二维极半径傅立叶变换，二维Zernike矩[5]，二维Krawtchouk矩[7]描述它的特征

Di=(DFT,DZern,DKraw)

式中：Di是由分别来自于二维基半径傅立叶变化、二维Zernike矩，二维Krawtchouk矩的特征向量DFT、DZern和DKraw串联组成的投影视图特征描述子。

图2 三维CAD模型的投影规则

2 典型视图的甄选

获得二维投影视图集合之后，接下来将甄选其中的典型视图。在本文中，典型视图被定义为在一个投影视图集合中与其他若干视图相似, 可以代表这些视图的一类视图。对于一幅视图，若集合中与其相似的视图越多，则认为该视图越具有典型性。例如，球体的正投影视图可以用来代表其他所有的视图。由于在内容中体现了与其相似的若干视图的共同特点，因此典型视图相较其它视图含有更高的信息量。本文将通过Apriori算法挖掘出二维投影视图集中的典型视图，将三维模型进一步表示为由典型视图所组成的二维典型视图集合。

2.1 Apriori 算法

Apriori算法作为关联规则的挖掘技术已经在计算机信息与数据挖掘领域得到了广泛应用[8]。下面介绍关于它的一些基本概念：

事务：事务是数据集ITEM=item item item的一个子集，不同事务的全体构成了事务数据库DATA。

关联规则：关联规则指如果项集X在某一事物中出现，则必然会导致项目集Y在同一事务中出现的一种规则，即X⇒Y ，其中X⊂ITEM ，Y⊂ITEM ，X∩Y≠Φ。

数据项的支持度和频繁集：设X⊂ITEM为数据项集的一个子集，B为全体事务集DATA中包含X的事务的数量，A为DATA中包含的所有事务的数量，则项集X的支持度为：

它描述了数据项集X的重要性。支持度大于最小支持度的数据集为频繁集。

关联规则的置信度：一个关联规则的置信度表示为

它被用来描述该规则的可靠程度。

Apriori算法的核心思想是通过对事务数据库的多轮扫描来发现所有的频繁集。首先找出所有支持度大于最小支持度的项集，即频繁项集；然后基于这些频繁项集产生新的关联规则往复扫描。此过程不断重复直到不再有新的频繁项集产生为止。

2.2 甄选典型视图

在使用Apriori算法挖掘典型视图之前，需要构建一个事务数据库DATA。首先，将二维投影视图间的相似性度量定义为

式中： dis()为视图i和i’对应特征描述子Di和Di’的L-2距离，它被归一化在区间[0,1]。若度量结果大于规定的最小相似度min_ImgSim，则认为i和i’相似。然后，对于投影视图集合I的每一幅视图i，统计该集合中所有与其相似的视图（包括其自身）。最后，将统计后的项目作为一条事务存入事务数据库DATA。DATA由对应着视图集规模的42条事务组成，如表1所示。

对二维典型视图的挖掘从对事务数据库DATA的第一轮扫描开始。首先，对于项集中的每一个数据项（即投影视图）计算其所对应的支持度，筛选出大于最小支持度min_support的频繁1-项集组成频繁项目集L1；然后，以L1作为输入构建候选集，扫描数据库并从中找出大于最小支持度的2-项频繁项目集L2；接下来继续用L2作为输入去寻找L3。此过程不断重复直到没有新的频繁集产生为止。典型视图即为每个频繁项目集中对应关联规则置信度最小的数据项。算法1 给出了整个典型视图甄选的流程。

算法1：典型视图甄选算法

输入：事务数据库DATA，最小支持度阈值min_support

输出：三维模型的典型视图集C

1）L1= 1项频繁项目集

2）for（k=2；Lk-1；k++） do

3）CankApriori_gen(Lk-1，min_support)：构建候选集

4）for all 数据库DATA中的事务t do

5）Cant Subset(Cank，t)：提取包含在事务t中的候选集

6）for all Cant中的候选项Can’ do

7）Can’.Count++

8）end for

9）Lk= {Can’∈CankCan’.Count ≥ min_support}

10）end for

11）L = ∪kLk

12）end for

13）C SeekMinConf(L)：计算置信度，提取典型视图

完成典型视图的甄选之后，三维模型将由其对应的二维典型视图集C来表示。三维模型之间的相似性比较即可转换为各自典型视图集之间的比较。由于存在不同模型典型视图集规模不一致的问题，为了保证相似性计算的有效性，本文采用贪心算法。设模型M和Q对应的典型视图集分别为CM与CQ，则其相似性计算的具体步骤如下：

表1 事务数据库D示例

步骤1 取模型M的1幅典型视图ci∈C，遍历CQ中的每一幅视图crQ，找出与其最相似的视图cj。ci与cu之间的距离函数定义为

式中：r为模型Q典型视图集的规模；Dci于MDcQr分别是cMi和cQu对应的特征描述子。其值越小，表示视图越相似。

步骤2 重复步骤1，直至任一视图集合中所有的视图都成功匹配。在此过程中，视图集CM与CQ内已经匹配成功的视图不参与重复计算。则2个模型M和Q之间的相似性度量可表示为

式中：N =min(s, r )，s和r分别为模型M和Q所对应的典型视图集的规模。D为匹配成功的视图对之间的L-2距离。

3 算法验证与讨论

本文以OpenCASCADE[9]为几何造型平台，Microsoft Visual Studio 2008为集成开发环境，构建了一个三维CAD模型测试库。库中的模型主要来自于普渡大学建立的工程标准模型库ESB，包含了齿轮类、盘类、轴类等400多个CAD模型。在实验中，为了确保在对模型投影的过程中，从每一视角投影的唯一性，本文利用实验平台OPENCASCADE和改进PCA法对模型的姿态分别对模型进行位置尺度和旋转的归一化处理。投影视图的尺寸规定为256×256。衡量投影视图相似性的最小相似度min_ImgSim与典型视图甄选时

图3 三种算法的平均查全率-查准率曲线比较

甄选时的最小支持度min_support分别设定为70%与50%。

为了验证本文算法在三维CAD模型检索中的有效性，本文使用查全率-查准率曲线（P-R Curve）和E测度（E-Measures）作为检索结果的评价指标，将本文算法与光场算法（LFD）[5]及文献[6]中的算法（OWD）进行比较。综合图3、表2及表3的实验结果，可以看出本文算法的检索性能优于其他两种算法，检索结果更加符合人的相似性感知。

表2 三种算法的E测度指标比较

表3 检索实例

4 结论

本文提出了一种基于二维典型视图的三维CAD模型检索算法。通过对CAD模型进行二维投影并甄选出其中的典型视图， 将模型表示为其对应的二维典型视图的集合。三维模型间的相似性评价通过比较各自对应的二维典型视图来获得。实验结果表明本文算法的检索性能优于其他几种算法，能够更好地胜任对三维CAD模型的检索。

[1] Ulman D G.The mechanical design process,second ed.New York:McGraw-Hill,1997.

[2] Tangelder J W H,Veltkamp R C.A survey of content based 3D shape retrieval methods.Multimedia Tools and Applications,2007,39(3):441-471.

[3] Shilane P,Min P,Kazhdan M,et al.The Princeton Shape Benchmark.In Proc.Shape Modeling Applications,Genoa,Italy,2004.

[4] Jayanti S,Kalyanaraman Y,Iyer N et al. Developing an engineering shape benchmark for CAD models.Computer Aided Design,2006,28(9):939-953.

[5] Chen D Y,Tian X P,Shen Y T. On visual similarity based 3D model retrieval.Computer Graphics Forum,2003,22(3):223-232.

[6] Li L,Wang H Z,Chin T J.Retrieving 3D CAD models using 2D images with optimized weights. In Proc.International Congress on Image and Signal Processing,Yantai,China,2010.

[7] Yap P T,Paramesran R,Ong S H.Image analysis by Krawtchouk moments.IEEE Transactions on Image Processing,2003,12(11):1367-1377.

[8] Wu X D,Kumar V,Quinlan J R et al. Top 10 algorithms in data mining.Knowledge and information systems,2007,14(1):1-137.

[9] OpenCASCADE Technology www.opencascade.org.