王家乐

浙江工商大学，杭州，310018



一种基于法向量分布特征的机械零件模型手绘草图查询接口

王家乐

浙江工商大学，杭州，310018

提出一种面向三维机械零件模型检索的手绘草图查询接口。首先，利用模型的法向量最大分布方向来辅助主成分分析(PCA)算法对三维模型的空间姿态进行旋转归一，使得模型投影视图和用户手绘草图的视角一致；然后采用一种二维图像相似性比较算法衡量用户草图和模型投影视图之间的相似性，从而得到与用户提交的查询草图相似的三维零件模型。实验结果表明所提出的手绘草图查询接口能够让用户快速地表达查询意图，且具有较高的检索准确性。

三维模型检索；查询接口；手绘草图；形状分析

0　引言

三维辅助设计软件的广泛使用使得机械零件领域中的三维零件模型数目日益庞大。要有效地管理海量机械零件模型，需要有效的模型形状相似性检索方法，从而让用户可以快速从零件模型数据库中找到特定形状的零件模型。

三维形状的复杂性令如何让用户方便且准确地表达查询意图成为三维模型检索中的一个难点问题。一个实用的三维模型检索系统，应拥有友好的查询接口和人机交互界面，为用户提供方便的查询手段。在机械零件设计领域，检索相似零件模型的目的一般是为了设计重用，复用已有的零件模型及其设计方案。在检索时，用户很可能没有现成的零件模型可作为查询递交，在这种情况下应该支持用户通过手绘草图表达待查询零件的形状。

本文提出一种适合于三维机械零件模型检索系统的手绘草图查询接口，用户可通过绘制零件的若干幅二维草图来表达查询形状。

1　相关研究

三维模型检索系统的查询接口一般可分为文字接口、模型接口、手绘草图接口三类。

文字接口采用基于文本的关键词检索方式，将用户输入的关键词同三维模型的文件名或备注信息作文本匹配。这种查询不属于形状特征比较的范畴，因此本文不作讨论。

模型接口让用户提交一个完整的三维模型作为查询输入，检索系统对此模型提取形状特征，然后计算其形状特征向量与数据库中模型的形状特征向量的距离。模型接口的优点是查询模型十分精确，包含了完整的形状信息；缺点是查询时要求用户拥有一个现成的查询模型。

手绘草图接口可让用户自主、快速地用手绘方式表达出查询形状，从而解决了模型接口需要提供查询模型的问题。本文对手绘草图接口展开了重点研究。

文献[1]基于Teddy手绘建模系统实现了一个面向三维模型检索的三维草图接口，用户在平面上绘制表示三维形体的线条草图，然后查询接口根据二维线条构建出三维形体。三维草图接口对用户的绘图水平要求高，操作起来比较复杂；而且从二维线条图重构三维形体的效果并不理想。二维草图接口让用户手绘若干幅不同角度的模型轮廓图，检索系统对三维模型的投影视图和用户手绘轮廓图进行相似性比较。二维草图接口避开了三维重建的难题，实用性较好，因此得到了较多研究者的关注[2-3]。

文献[4]和文献[5]分别提出了通过绘制三维模型的骨架草图来构建查询，骨架图包含了模型的拓扑结构信息，因此可以实现三维模型间的拓扑相似性检索。但是骨架提取算法易受到模型中噪声影响，所以检索准确度受限。

上述各文献中研究的查询接口均为非交互式接口，文献[6]提出一种交互式的三维模型检索系统查询接口，用户可根据检索返回的模型投影视图来修改草图，然后重新提交草图进行二次查询。这种交互式的手绘草图接口让用户能修正查询形状，使草图更加准确地表示用户的查询意图。但交互过程也复杂化了查询步骤，非熟练用户使用该系统是有一定困难的。

文献[7] 比较了近几年来的手绘草图三维形状查询研究，其中性能较好的方法均需大量的“视图采样”(view sampling)，即从多个视角生成模型的投影视图(一般为几十幅至上百幅视图)。本文研究三维模型姿态旋转归一算法，三维模型经过旋转归一后可以只生成和比较特定视角的少数几幅视图，计算量减小但检索准确度一般次于多角度视图采样方法。

针对机械零件模型，文献[8] 提出利用模型特征拓扑结构的检索算法，文献[9] 提出将整个三维模型拆分成若干平面体、回转体和曲面体，根据形体之间特征数量和参数的不同进行形体之间的匹配。以上两篇文献所提出的方法充分利用了机械零件模型自身的特点来构造有效的检索算法，但均没有提供手绘草图查询接口，它们不支持手绘草图查询。

2　确定投影方向

实现手绘草图查询接口的关键步骤有两个：①确定模型的投影方向，获得与用户手绘草图相同视角的模型投影视图；②用户草图和模型投影视图间的相似度计算。下面阐述确定模型投影方向的方法。

三维空间中模型可能处在任意的旋转姿态下，而用户提交的手绘草图表示了用户选定角度下模型某侧面的轮廓图。因此在生成模型投影视图之前，需要将模型的空间姿态进行旋转归一，以达到如下两个目的：①不管模型初始旋转姿态如何，相似的模型在旋转归一后处在近乎同样的姿态下；②在旋转归一后，能够得到与用户习惯视角一致的模型投影方向。

三维模型旋转归一最常用的方法是PCA旋转归一算法，它通过计算模型所有顶点坐标协方差矩阵的特征向量(eigen-vector)得到模型的“主轴”，从而归一化模型旋转姿态。PCA算法并不完全适用于基于手绘草图的三维模型检索，因为它只能实现上述目的①而不能实现目的②。在一些情况下，尽管PCA算法将相似三维模型的旋转方向归为一致，但这个方向却不符合人们的视觉习惯。图1展示了两个经PCA算法旋转归一后的椅子模型。可以看出，这两个模型旋转归一后的空间姿态是一样的，但PCA确定的投影轴(即图1中坐标轴)方向不符合人们的视觉习惯，人们通常按图2中箭头所示的方向去描绘模型的侧轮廓。用户一般从一个“正立”面描绘三维物体，例如工程师所用的三视图是从正前、正侧和正上方来投影物体。

图1　PCA旋转归一后的模型姿态及PCA定义的投影方向

图2　用户的视觉习惯方向

PCA算法之所以产生上述问题是因为它仅从模型顶点的分布来考虑模型姿态，而不涉及模型的面片朝向。机械零件模型的面片朝向一般具有较明显的规律性，因此本文通过计算模型面片的法向量最大分布方向来确定模型总体朝向，以此辅助PCA算法更准确地将模型旋转归一到用户的习惯观察角度。

为了计算三维模型的法向量分布，首先获得模型的扩展高斯图像(EGI)。EGI把构成三维模型的每一个面片映射为单位球面上的一个向量，这个向量的方向与该面片的法向量方向相同，向量的模为该面片的面积率(面片面积/模型总面积)。图3所示为一个三维模型及其EGI，图中左边是一个以面片形式显示的椅子模型，右边是该模型的EGI(单位球面上的外指线段表示法向量)。

图3　三维模型及其EGI

获得模型的EGI后，建立一个球面坐标系，如图4所示。在此坐标系中定义一个搜索游标向量I(φ,θ)， 其模r为1。

图4　球面坐标系

(1)

其中，E为模型的EGI上全部向量的集合，φ∈[0,2π],θ∈[0,π]。然后计算集合U(φ,θ)中所有向量在I(φ,θ)上投影的模长之和：

A(φ,θ)=∑I(φ,θ)·PiPi∈U

(2)

模型的最大法向量分布方向I1即为使得A(φ,θ)值最大的(φ,θ)所定出的方向。

获得了最大法向量分布方向I1后，再在与I1垂直的平面上搜索法向量分布最大的方向I2。I2的计算过程与I1一样，只是多了一个约束条件：搜索游标向量I(φ,θ)与I1垂直，即I(φ,θ)·I1=0。求得I1、I2后就可以沿I1、I2以及与它们垂直的方向对模型进行投影。

以上算法的计算结果可以辅助PCA算法对模型进行旋转归一：把用户手绘草图跟用PCA算法旋转归一后的模型投影图以及用最大法向量分布算法旋转归一后的模型投影图均作比较，取两次比较中最小的相似性距离作为查询草图与模型间的相似性距离。

3　草图和视图间的相似度计算

用户提交的三幅手绘草图和模型三幅投影视图之间的对应关系是未知的，需将三幅手绘草图与模型三幅投影视图的所有可能排列相匹配，所有排列中最小的相似性距离和为手绘草图和投影之间的相似性距离。

三维模型的投影视图有多种：剪影图像、深度图像、轮廓图、外轮廓图等。其中的轮廓图属于线条图像，适合于作为与用户手绘草图匹配的模型视图。三维模型的轮廓图是模型表面点的集合，在这些点上模型表面的法向量与视线方向垂直。用数学语言表达即为：构成轮廓线的点满足ni·(pi-c)=0，其中pi代表模型上的点，ni代表pi的法向量，c代表观察者视点，pi-c是从视点出发到pi点的视线。由于三维网格模型由面片组成，其表面法向量方向不连续，一般情况下不存在法向量正好与视线垂直的面片，所以在网格模型上，把轮廓线定义为前向面片(法向量指向视点的面片)和后向面片(法向量背向视点的面片)的公共边集合(图5)，即构成轮廓线的边满足：[nm·(v-c)][nn·(v-c)]<0，其中nm和nn是共有该边的两个面片的法向量，v是该边上的任意点。

图5　轮廓线定义

(3)

disImg(·)是一个衡量图像间相似性的函数，本文采用文献[10]提出的线条图相似性比较算法ARP(angularradialpartitioning)来衡量模型投影视图和用户手绘草图之间的相似性。ARP算法首先需要将线条图像作平移和缩放归一化，使得其恰好被一个同心圆和扇形组合的网格覆盖，这个网格被划分为M×N个区域，M是径向划分数目，N是角度划分数目，如图6所示。ARP算法统计每个区域中图像像素的数目，假设f(k,i)表示第(k,i)个扇形区域内的像素数(k=0,1,2,…,M-1，i=0,1,2,…,N-1)，对每个给定的k值，对f(k,i)进行一维傅里叶变换：

(4)

傅里叶变换后，取{‖F(k,u)‖}(k=0,1,2,…，M-1;u=0,1,2,…,N-1)作为图像的特征向量。这个特征向量是具有旋转不变性的。

图6　图像划分网格

4　实验分析

实验使用ESB(engineeringshapebenchmark)模型库[11]来测试算法的检索性能。ESB模型库包含了45个机械零件模型分类，共有867个零件模型。本文实验选用了ESB模型库中42个模型类，未被选用的3个模型类均为杂类(Miscellaneous类，它们包含类型意义不明显的零件模型)。实验对42个类的每一个类进行2～3次查询。

图7所示为用户通过本文所提出的手绘草图查询接口进行的一次查询，图中上部为用户提交的三幅手绘草图，下部为检索返回的前四个查询结果。

图7　用户手绘草图查询和查询结果

本文采用信息检索领域中常用的查准率-查全率(precision-recall)[12]指标来衡量检索准确度。查准率是指检索系统只返回相关对象的能力(即检索的准确性)，查全率是指检索系统返回所有相关对象的能力(即检索的全面性)。

图8展示了单独使用法向量最大分布算法(MN)、单独使用PCA算法，以及组合PCA算法和法向量最大分布算法的查准率-查全率曲线。可以看出组合PCA算法和法向量最大分布算法可使得查准率-查全率指标更理想。

图8　查准率-查全率曲线

表1中列出了基于PCA算法和基于法向量最大分布算法的模型形状特征提取时间，后者比前者的耗时要多，但由于特征提取可以在用户进行查询之前就进行(通常是在数据库建立或有新模型加入到数据库时进行)，因此特征提取时间的长短并不会影响检索系统对用户查询的响应速度。表1中最后一行列出了两种算法的查询响应时间，几乎没有差异。

组合PCA算法和法向量最大分布算法虽然会在提升检索准确度的同时带来额外的时间开销，但不影响查询响应速度，只是增加了数据库系统后台提取模型特征的时间，所以这种方式是有价值的。

表1　计算时间　s

5　结束语

本文提出了一种面向三维机械零件模型检索的手绘草图查询接口。由于机械零件模型的面片朝向一般具有规律性，面片法向量通常在某几个方向上存在显著的聚集，因此可利用模型的法向量最大分布方向来辅助PCA算法对三维模型的空间姿态进行旋转归一，使得模型投影视图和用户手绘草图的视角一致。实验结果表明本文提出的手绘草图查询接口对用户友好，具有较高的检索准确性；虽然特征提取时间有所增加，但并不会影响到检索系统对用户查询的响应速度。

[1]Funkhouser T, Min P, Kazhdan M, et al. A Search Engine for 3D Models[J]. ACM Transactions on Graphics, 2003, 22(1): 83-105.

[2]Hou S, Ramani K. Classifer Combination for Sketch-Based 3D Part Retrieval[J]. Computers & Graphics, 2007, 31(4): 598-609.

[3]Eitz M, Richter R, Boubekeur T, et al. Sketch-based Shape Retrieval[J]. ACM Transactions on Graphics, 2012, 31(4): 13-15.

[4]Wang Jiale, He Yuanjun, Tian Haishan, et al. Retrieving 3D CAD Model by Freehand Sketches for Design Reuse[J]. Advanced Engineering Informatics, 2008, 22(3):385-392.

[5]Hou S, Ramani K. Dynamic Query Interface for 3D Shape Search[C]//Proceedings of ASME IDETC/CIE. Salt Lake City, 2004.

[6]Pu J, Ramani K. A 2D Sketch-Based User Interface for 3D CAD Model Retrieval[J]. Journal of Computer Aided Design and Application, 2005, 2(6):717-727.

[7]Li Bo, Lu Yijuan, Li Chunyuan, et al. A Comparison of 3D Shape Retrieval Methods Based on a Large-scale Benchmark Supporting Multimodal Queries[J]. Computer Vision and Image Understanding, 2015, 131(1):1-27.

[8]孙长乐, 宁大勇, 熊伟, 等. 基于特征的工程领域CAD模型检索技术[J]. 计算机集成制造系统, 2014, 20(4):747-754.

Sun Changle, Ning Dayong, Xiong Wei, et al. Feature-based CAD Model Retrieval Technique in Engineering Field[J]. Computer Integrated Manufacturing Systems, 2014, 20(4):747-754.

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

Zhu Wenbo, Wu Xinren, Gan Yi. 3D Model Retrieval of Mechanical Parts Based on Shape Split[J]. Journal of Graphics, 2015, 36(1):35-40.

[10]Chalechale A, Mertins A, Naghdy G. Edge Image Description Using Angular Radial Partitioning[J]. IEE Proceedings—Vision, Image and Signal Processing, 2004, 151(2):28-41.

[11]Jayanti S, Kalyanaraman Y, Iyer N, et al. Developing an Engineering Shape Benchmark for CAD Models[J]. Computer-Aided Design, 2006, 38(9): 939-953.

[12]Singhal A. Modern Information Retrieval: a Brief Overview[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2001, 24(4):35-42.

(编辑卢湘帆)

Free-hand Sketch Query Interface for Retrieving Mechanical Parts Using Normal Vector Distribution Feature

Wang Jiale

Zhejiang Gongshang University,Hangzhou,310018

A sketch query interface was proposed for retrieving 3D models of mechanical parts. The maximum normal distribution of a 3D model was computed to assist the principal component analysis(PCA) to normalize the orientation of the 3D model, and then the projected views of the 3D model could be coordinated with the free-hand sketches submitted by users. To retrieve the 3D models similar with the user sketches, an image similarity assessment algorithm was employed to compare the shape similarity between user sketches and the views of the model. Experiments demonstrate that users can express their query intentions through the proposed query interface rapidly with satisfactory retrieval performance.

3D model retrieval; query interface; free-hand sketch; shape analysis

2015-10-15

国家自然科学基金资助项目(61202200)；浙江省教育厅科研项目(Y201018008)

TP391

10.3969/j.issn.1004-132X.2016.16.002

王家乐，男，1980年生。浙江工商大学计算机与信息工程学院副教授。主要研究方向为信息检索、人机交互。发表论文10余篇。