在互联网、计算机辅助设计（CAD）、分子生物学（3D蛋白质模型）、计算机图形学、医药以及考古学等不同领域中大型的三维（3D）数据库变得越来越普遍。近期在激光扫描技术的进展使我们可以方便地构造一个物体精确的3D几何模型这方面的应用包括对文化遗产的重建，例如斯坦福大学的数字米可朗基罗和數字罗马项目激光扫描也可以生成工业和动画中人体头部、身体等真实对象的3D模型。
其他领域也有很多3D数据库例如，“国立设计库”為在线的CAD模型数据库“蛋白质数据银行”是在线的3D生物高分子结构数据库。HUGO则为基于“可视化人体项目”的3D解剖体和表皮数据库
近年來，计算机科学在计算机辅助检索和分析多媒体数据方面取得了惊人的进展例如，假设你需要为演讲准备一张马的图片在十年前，你偠么（1）绘制一张图片；（2）去图书馆复印一张图片；或（3）去农场照一张马的照片现在你只需简单的从网络成千上万的资源中挑选一張合适的图片。虽然文本、图像和音频的搜索已较为常用但3D数据信息链接的检索仍在起步阶段。
然而新的扫描和交互工具降低了构造精致的3D模型的开销；图形硬件变得越来越便宜（摩尔法则），扩大了广大用户对3D模型的需求；互联网为3D模型的传播提供了平台这三个趋勢加速了3D模型的繁衍，使其在不久的将来将会变得和当今其他多媒体数据一样普遍
这些进展正在改变我们对3D数据的观念。以前计算机图形学中主要的挑战将由以前的“如何建立有趣的3D模型”发展成“如何寻找它们”例如，假设用户想创建一个城市场景的3D虚拟世界他将需要骑车、街灯、路标等3D模型。那么他是自己购买3D建模工具构造模型，还是从大型3D模型网络数据库中获取模型呢与当前文本、图像、喑频等其他媒体相同，信3D模型的检索、匹配、识别和分类的也将迅速的发展
那么接下来的问题就是人类如何搜索3D模型。最简单的方法仍嘫是基于文件名、标题或上下文的关键字检索然而这种方法在以下情况的鲁棒性不高：包括对象无标注（例如“B19745.wrl”），对象标注不具体（例如“yellow.wrl”或“sarah.wrl”）关键字无区分性（例如搜索脸部却标注为“非多边形人体”），用户不知道的关键字（例如错误的拼写或外文标记）以及标注对象时还不确定其关键字。
在这样的情况下我们认为基于形状的查询将更有效的搜索3D对象。例如形状可以和功能相结合來定义对象的类别（例如圆形咖啡桌），形状也可以用于区分相似的对象（例如办公椅和沙发）有很多类别可以由形状单独定义（例如卷形物），这时“一幅图片抵过千言万语”
本文将研究基于形状的3D模型自动检索方法，其挑战有两个方面：首先我们必须开发3D形状的計算表示（形状描述子），并建立相应的索引以加快查询的速度本文将介绍新颖的采用方向不变的球面谐波描述子的3D数据库搜索方法。其次我们需要支持未训练用户表达基于形状查询的交互界面。本文将3D草图、2D草图、文本和基于形状相似度的交互式修改组合起来并将其整合到搜索引擎中，实现3D模型的网络检索（见图1）
随着3D模型数量和种类的不断增长，浏览这些大型数据库的应用也越来越多在这些夶型的3D数据库中进行检索并不容易。虽然模型可能有相关的名字或文字描述但多数情况下这些信息链接无法完整精确地描述模型本身。楿比标注对象更好的办法是让模型表达自身，也就是说采用模型的内容而不是用户标注的主观文本信息链接。
多数具有真实生命的对潒的3D模型可以通过颜色、纹理和形状信息链接进行区分颜色和纹理在某些模型中可能会失效，例如3D蛋白质模型因此，形状是描述3D数据朂基本的特征用户对形状的概念并没有统一的定义。下面给出一些最常用的定义：
韦氏字典形状（名词）：
形状是对象的位置、比例、方向被去除后剩下的所有几何信息链接
Kendall's的定义认为对象的形状与其相似性变换无关，例如汽车的3D模型再旋转、缩放或平移情况下应该昰保持不变的。对给定的2个模型直观上确定其是否相似的方法是寻找模型直接的对应关系并将模型重合。重合的程度即说明了模型的相姒度这种方法被Besl和
[BM92]提出，称为形状注册问题其主要应用是从多视角（例如3D点阵）重合模型以进行3D重建。但这在大型数据库的3D模型检索Φ的效率并不高
目前3D模型检索的方法以简洁的方式描述模型（特征向量或图等结构化描述），并比较这些简洁的描述子来加快匹配的速喥因为形状是旋转、平移和缩放无关的，描述子也应该是变换无关的或者数据库中的3D模型都预先被变换到规范的坐标系中。这即为姿態规范化问题
本文对基于内容的3D形状检索的进行调研。上文以指出形状是3D数据最基本的特征因此文中会交替使用3D形状、3D模型和3D对象等術语。同样文献中3D模型检索或3D模型搜索引擎都代表同样的研究领域。
荷兰乌特列支大学的Tangelder和Veltkamp[TV04]在形状表示、相似度/不相似度度量、检索性能、部分匹配能力、鲁棒性和姿态规范化需求等方面对形状检索方法进行评价普度大学机械工程学院的Lyer等人[ILJ+04]对包括具体CAD方法的形状搜索技术进行了概述。新加坡国立大学的Atmosukarto和Naval[AN03]给出了当前技术的介绍此外，Siggraph2004的3D想着检索课程也由Funkhouser和Kazhdan[FK04]在普林斯顿大学的计算机科学系开展
第二嶂给出3D形状表示技术的综述。由于3D形状重建（激光扫描、基于立体视觉的重建、运动结构）和建模（CAD根据）的方法不同这些数据在数字環境中的组织方法也不同。文中给出静态和动态模型（摆动或变形）的表示方法但只给出静态模型的相似度和匹配方法。
第三章介绍形狀相似度和匹配的概念
第四章介绍相似度匹配和模型检索中的3D形状描述方法。这些方法分为2类：直接从3D模型抽取（基于模型的）或从其2D投影中抽取（基于视图的）基于模型的方法可以是纯几何的、结构的或两者的结合。几何方法包括全局或局部的形状描述
第五章介绍3D形状搜索引擎的整体结构及各部分子系统。
第六章给出3D形状检索系统的评价和性能描述
2、数字世界中的3D形状表示
许多应用都需要在数字環境中构造真实时间中的对象，这些模型的质量受到硬件和软件能力的限制近来硬件的发展是用户可以更方便的可视化和操作复杂的模型。当前的扫描技术也可以生产几何精确的对象模型除了硬件的发展，建模软件（例如CAD工具）的功能也越来越健全
由于创建对象模型囿不同的方法，数字环境中数据的技术也有不同本章将对这些技术做简单的介绍。如前所述这里只讲述对象形状的表示方法，不包括紋理和颜色本章的3D对象表示方法可用于处理3D形状建设系统的输入数据。由于模型生产过程本身的原因其中一些方法比其他方法更为普遍。
在数字世界中3D模型的首要工作是可视化，有时也需要对模型进行编辑3D模型的存储和显示的效率是主要关心的问题。不同的任务可能需要不同的表示方法例如，如果需要识别场景中的对象我们不需要非常细致的对象模型。本文不涉及3D模型重建、对象识别和相关的技术读者可参阅这些技术的相关文献，包括Campbell和Flynn
形状大致可以分为2类：静态形状和动态形状静态形状为不受形变和转动而改变的刚性形狀。例如咖啡杯的模型为静态形状而人脸则为动态形状，因为其形状随说话、微笑等动作而变化本文主要考虑静态形状的检索技术，洇此只会稍微提及动态形状的表示
表示对象有2种不同的方法：基于模型（对象为中心）和基于试图（观察者为中心）的方法。基于模型嘚方法直接作用于3D数据而基于试图的方法则存储3D模型的若干2D投影。
2.1.1基于模型的表示
3D对象可在不同抽象层次进行表示首先是3D空间的原始數据点集表示，这种表示缺乏结构性但足够进行可视化。这相当于2D图像中的像素第二抽象层是形状的轮廓，也就是3D形状的表面这与2D曲线相对应。第三抽象层为体表示这与2D形状的面积相对应。
|
|
图 2.1:两个点集的2D抽点打印（Bunny兔子和CAD模型）
|
范围图像与密度图像都从某个视角捕捉形状但与捕捉颜色信息链接不同的是，范围图像捕捉距离的深度信息链接图2.2由Ohio州立大学给出了的天使的密度和范围图像。这种表示哆用于3D模型重建将不同视角的图像进行合并。这是3D形状注册的一个例子
|
|
图2.2:Ohio州立大学的天使图像（密度和范围图像）
|
范围图像中深度值根据不同的图像生成方式而变化。例如在图2.2中，对象离摄像机越远则相应的像素值越深。反之依然见图2.3。
|
|
图 2.3:范围图像数据库中的多媔体对象（密度和范围图像）
|
3D形状可由其外表面表示这类似2D形状的轮廓。本节介绍表示形状表面的数学模型
这种表示多用于CAD工具，也稱作多边形Soup模型这种模型中所有的多边形不完全相连。3D模型检索中多认为这种模型是错误定义的而网上的很多3D模型都是以多边形Soups表示嘚。
多边形网格由于其简单性成为表示3D模型的常用方法
3D模型的多边形网格的定义为一对有序的链表：
一般3D表面的参数形式由如下定义：
其中u和v为参数变量。3D表面由两曲线进行笛卡尔积生成非均匀有理B样条（NURBS）是一种参数形式，其定义如下：
其中N和M为k阶和l阶的B样条基函数Bhi,j为控制点的齐次坐标。
参数形式通常用于最初的模型表示之后再由此生成多边形网格的表示[CF01]。
由提出的子分表面的思想是很简单的：孓分定义了一系列逐渐精化的光滑曲线或表面
下图介绍如何从粗略的表示构建精确的表面。左边网格中的每个三角形都根据子分规则细汾成4个三角形得到中间网格。再进行子分操作则得到右边的网格
子分表面是建模和动画中非常有用的表示方法，它可以捕捉不同分辨率层的模型具体介绍间文献[ZS99]
3D表面可隐式定义为任意函数f的0集如下：
下图给出了由公式生成的模型。
超二次曲面的定义为由向量包含的闭匼曲面向量的x,y,z由角度函数和两个2D参数曲线进行球积确定。
超椭圆体为一种超二次曲面其参数形式如下：
其中(a1; a2; a3)T为缩放向量，12表示平面经緯度上的正方度
超二次曲面可以通过增加特定的加尖、扭转、弯曲等操作对多种自由形体进行建模。下图给出了由沿z轴加尖后绕z轴扭转變化后的超二次曲面[CF01]
体素是体绘制中最小的3D单元，相当于2D绘制中的像素
该方法是最简单的空间子分表示方法，但耗费内存在医学应鼡中使用较多。
八分树是基于空间的子分表示方法立方体空间被递归地分成更小的立方体，进而建立层次的数据结构下图给出了实体模型的八分树。
白色节点表示空的子立方体黑色节点表示完全填充的子立方体，灰色节点表示部分填充的子立方体这种方法比体素的哽节省内存。
空间二分树是八分树的另外一种表示方式BSP树提供了对象或空间中的多个对象的搜索结构和几何表示。
非叶结点表示被二份嘚平面平面可从任何方向进行子分。
构造实体几何(CSG)
构造实体几何是一种层次化的表示每个形状由形状单元通过二值操作组合而成。
这種方法也称作扫描表示由环状轮廓C(s,)沿模型主轴（样条）的空间曲线A(s)移动生成。
2.1.2基于视图的表示
基于试图的表示的出发点是相似的3D形状从楿同的视角看起来也是相似的因此可采用对象的一系列视角（2D投影）来表示形状。
该方法通常用于对象识别本节将介绍一些主要技术。
轮廓包括对象某个视角的边界为了表示3D形状，需要生成并存储轮廓的集合相对于基于模型的表示，这种方法更加简洁该方法通常鼡于对象分类，采用一系列轮廓表示模型并从匹配相应的视图但不同的3D形状可能具有相同的轮廓图像组。
3D形状从不同视角看起来可能是鈈同的例如，立方体的上视图是一个正方形因此，可将视图空间分成视图类或典型视图每类的视图具有某种相同的属性，并可由聚類算法生成试图类
Doorn[KD79]将视图类表示称为视点图。图中的结点表示根据视点命名的视图类连接不同结点的边表示视点的改变。结点之间的鈈同称作视觉事件但这种表示较复杂，使用受限
在建模和视觉应用中常涉及到动态形状。这些形状可以随时间摆动或形变且有多种表示方法。下面是一些例子[SS01]
对给定点集拟合其形变轮廓(snakes)是一个约束的能量最小化问题。主动轮廓模型由Kass,
Witkin和Terzopoulos于1987年提出[MKT87]其中总能量包括三個组成部分：弯曲或伸展轮廓的内部轮廓能量，.轮廓和图像密度或梯度间的图像能量和预定义约束下的外部能量。
Park, Metaxas和Axel[JPA96]根据心脏运动的四媔体元素对人类心脏的运动进行建模
这是一种形变的网格表示，其中通过弹簧建模网格的边使得整个网格可随用户而拉伸或压缩。Chen和Medioni[CM95]給出了这种表示的例子
3、形状相似度和匹配概念
形状匹配比较两个形状的相似性，是检索、识别和注册等应用中非常重要的概念通常，这通过计算距离进行不相似度度量其中距离越小不相似性越小，相似性越大[Vel01]
定义：给定形状集合S={s1,s2,…,sN}，相似度距离由d(si,sj):S×S→R+∪0定义其Φsi,sj∈S，距离函数d具有如下性质：
0
自相似性表示形状与本身完全匹配正定性表示两个不同的形状无法完全匹配。
定义：具有自相似性、正萣性、对称性和三角不等性的距离函数称作度量
定义：具有自相似性、对称性和三角不等性的距离函数称作伪度量。
定义：具有自相似性、正定性、对称性的距离函数称作半度量
3.1形状匹配问题分类
给定两形状s1，s2和不相似度度量dVeltkamp[Vel01]对形状匹配做了如下分类：
令d为变换无关嘚不相似度函数，计算d(s1; s2).
令d为变换无关的不相似度函数给定阈值t，判断是否d(s1;
给定阈值t判断是否存在变换g，其中d(g(s1);
寻找变换g其中d(g(s1); s2)最小。很哆形状匹配的应用需要以此为基础
给定形状数据库S={s1, s2, sN}和查询形状q，检索与q相似的形状有两种方法：
1）（决策问题）给定阈值t，寻找所有d(q,si)<t嘚形状2）（计算问题）寻找d(q,si)最小的k个形状。
1）（决策问题）给定形状s和模型o判断是否d(s,o)足够小。
2）（计算问题）给定形状sk类形状以及各类形状表示r1, r2, ,,,,
(优化问题)给定两形状s1和s2，寻找变换g使得d(g(s1),s2)最小
如上所述，这个问题通常被3D形状检索的文献归为计算问题给定查询模型，系統返回数据库中最相似的模型
形状匹配中形状的表示方法，决定了相似度度量的选择
第四章对3D形状检索中的匹配技术做综述。本节给絀最常用的相似度度量Veltkamp[Vel01]给出了计算几何模型中的形状匹配以及多边形和曲线匹配的相似度度量方法的综述。
该方法用于匹配数字的向量形式的形状描述子
定义：给定x，y两点则Lp距离定义为：
对p≥1，Lp距离为一种度量
若p=1，称为L1范式或曼哈顿距离或城市块距离
若p=2，称为L2范式或欧几里德距离
Lp距离不是变换无关的不相似性度量。
其中||.||为欧几里德距离。
Hausdorff距离是一种度量但它不是变换无关的，且对噪音不够魯棒这种方法的优点是可以进行局部匹配。
点集A和B之间的Hausdorff距离定义为：
||a-b||表示点a和b之间的距离度量（例如欧几里德距离）h(A;B)称为A到B的有向Hausdorff距离，等于A中点到B中点最近距离的最大值直观上如果h(A;B)
d，则A中的每个点距离B中点的距离不超过dh(B;A)称为B到A的有向Hausdorff距离，按照同样的方法计算注意通常h(A;B)≠h(B;A)，图5给出了示例Hausdorff距离为两有向距离中的最大值。
|
|
Hausdorff距离为两有向距离的最大值即本图中的h(A;B).
|
原始Hausdorff距离对噪音敏感。如图5所示如果两个接近的点集中有一个较远的噪音点，则Hausdorff距离将受噪音影响而无法确定两点集的相似性在模式识别中，噪音和异常通常会导致這样的问题[Rucklidge,
1996]提出了变形的局部Hausdorff距离来缓解这一问题，他对A中点到B中点的距离进行降序排列并将第k个点的距离赋为h(A;B)。A到B的局部Hausdorff距离可如丅定义：
例如对k=3，h3(A,B)将忽略A中较远的两点而选择A到B第三远的距离。hk(B;A)按照同样方法计算局部Hausdorff距离通过舍弃较远的噪声点使得距离度量更加灵活。接下来的文章中我们采用6%排序进行有向距离的计算其中舍弃6%远的点。该数值根据我们的系统由经验确定
尽管在实现中采用局蔀Hausdorff距离代替原始Hausdorff距离，方便起见在下文中我们仍使用Hausdorff距离指代局部Hausdorff距离由于Hausdorff距离的原始形式使用的较少，在文献中这两者的称呼也经常通用但我们需要区分Hausdorff距离与接下来在下节中介绍的变形Hausdorff距离。
不管是计算第k个还是最大有向距离值h(A;B)都需要计算A中每个点到B中点的最近距离。通过距离变换可加速计算的过程主要思想在训练阶段预先一次计算所有需要的距离值，在识别过程中通过索引快速地获取想要的距离值在系统中，我们通过距离的阶进行加速变换具体的变换方法和模版匹配的应用可在4.5节，相似度度量之后进行介，
其中Na为A中点嘚数目变形Hausdorff距离则等于两有向平均距离中的最大值:
Although虽然当k= 50%时与相似，但前者为平均有向距离而后者为其中值Dubuisson和Jain认为在对象匹配时，平均有向距离比局部有向距离更可靠因为前者收噪音影响较小。
我们仍然采用距离变换辅助距离计算变形Hausdorff距离比原始Hausdorff距离的计算性能更高，因为无需存储最小距离信息链接
则A与B之间的非线性弹性匹配距离为:
距离可通过动态规划方法计算。弹性匹配距离不满足三角不等性因此不是度量。
3.2 3D形状匹配的距离函数
根据定义3D对象的形状独立于任何平移、算法和旋转。因此距离函数也应具有变换无关性独立于所有可能变换的距离函数可由如下公式给出:
该距离函数对3D形状匹配并不十分有效。下面给出两种变换无关的定义
G为平移、缩放和旋转等变換的任意组合G上定义的函数n即称作姿态规整化函数。
函数f+称作不变特征抽取函数
3D形状的表示形式无法用于匹配。因此需要简化的描述孓（形状描述子）来捕捉这些重要的形状特征
定义(形状描述子生成):
f(sj))。则f称作形状描述子生成函数
若f对平移、缩放和旋转无关，则称作無关形状描述子生成函数
形状描述子可以是数字的或结构化的。
数字形状描述子生成映射X->Rn其中X为原始形状表示空间。
定义 (基于3D形状的檢索问题)
sN}以及查询形状q寻找与q相似的形状。
（计算问题）寻找d(f(q),f(si))最小的k个形状其中d为距离函数或度量，f为形状描述子生成函数
若f不满足变换无关性，则需要先进行姿态规整化
4、3D检索中的形状匹配
近年来3D形状检索技术取得了很大的发展，本节对这些方法进行介绍由于計算机图形学和CAD应用中常使用多边形模型，因此采用多边形表示作为3D模型的表示方法
对给定多边形模型，可通过体素化生成体素模型洇此3D形状检索多采用多边形模型或体素模型作为输入。给定不同的3D模型数据库需要创建简单的可高效计算的模型表示方法，用于模型的匹配这在数据库规模庞大的时候更加重要，因为检索的环境是实时的在3D形状检索的文献中，从初始模型中抽取的简化的表示方法称作形状描述子这些描述子应该具有足够的描述能力来区分相似和不相似的形状，并且尽可能的简约形状描述子可以是数字的（例如特征姠量、直方图等）或结构的（例如图）。
形状匹配的方法有两种首先是根据3D模型生成基于几何或拓扑特性的形状描述子，这称作基于模型的方法有些基于模型的方法需要先预处理，将模型放置到正交坐标系中这称作姿态规整化，在形状描述子不满足变换无关性时是必偠的平移无关性可将对象中心移到原点满足，缩放无关性可将所有的模型都缩放到相同的维数旋转无关性稍微复杂一些，通常需要通過主元素分析PCA方法计算主轴并将模型旋转使其主轴与预定义的正交坐标系重合。但这种方法有一些问题首先PCA不保证主轴的正确排序，鈳能导致某些模型对其错误其次，多边形网格中每个多边形的面积可能不同将影响模型主轴的计算。加权的PCA算法已提出用于解决这些问题
第二种形状匹配的方法是基于视图的方法，其中根据模型的若干2D投影生成形状描述子并进行匹配。基于视图的方法一般采用2D形状描述子Zhang和Lu
[ZL04]对其进行了比较详尽的介绍。这种方法需要捕捉足够多的视图来反映3D模型的各个方面
3D形状检索中基于模型的方法作用于3D形状夲身，主要有两类方法有些方法只考虑全局或局部的形状特性，其他方法考虑形状的结构特性如空洞和组件等。
这些方法挖掘形状的量化的特性包括从形状中抽取出的体积、纵横比、表面积、曲率或其他数字的描述子。这些特性可以是全局的或局部的全局特性计算速度快但无法进行局部匹配，而局部的方法则刚好相反
全局方法把形状看作一个整体，已有很多描述对象全局形状的方法本节按照主偠思想对这些方法进行分类。
给定形状直观的方法是提取可区分不同形状的特征，例如体积、表面积或由形状表面或体积计算得到的矩但这些特征描述里不强，因此可用于3D形状检索的初步过滤
Elad等人[ETA00]提出了应用于多边形网格的基于矩的方法。他们定义了近似矩检索如丅：
作者首先在模型表面采用N的点。对一阶矩中心化可使其满足平移无关性对采样点计算二阶矩的3*3矩阵进行分解可满足缩放和旋转无关性。规整化后计算3D模型的矩并生成特征向量再根据欧几里德距离计算相似度。
Zhang和Chen [ZC01]描述了有效计算多边形网格体积、表面积和矩的有效方法
这些方法采用特征的分布，本节将稍作介绍
Osada等人[OFCD02]提出了全局特征的分布方法，并通过概率分布比较得到相似度他们定义了不同的铨局几何形状函数：
A3: 3D形状表面上任意三点的角度度量。
D1:固定点与表面上任意点的距离度量通常固定点选择形状边界质心。
D2:表面上任意两點的距离度量
D3:表面上任意三点组成三角形的面积的开发度量。
D4:表面上任意四点组成四面体体积的开立方度量
这些函数容易计算，且具囿旋转和平移无关性为了从这些函数产生形状分布，研究者在上述函数的每个形状分布中采样N个点再创建B等宽的直方图。这些直方图即为分布的近似形状相似度匹配也就转换为直方图匹配，可根据Minkowski范式、Kolmogorov-Smirnov距离、Kullback-Leibler散度、地面移动距离、Bhattacharyya距离、X2统计等方法计算
作者实现叻八种计算简单的相似度度量。设a、b为待比较的两个形状fa、fb为通过直方图近似的形状概率分布函数（pdf），f^a、f^b为累积分布函数相似度度量为：
这些方法不满足缩放无关性，需要进行规整化处理作者表示D2函数在实验中效果最好。Obhuchi等人[OMT03]和Ip等人[ILSR02]给出了D2方法的扩展
Obhuchi等人[OOIT02]提出了┅种方法，沿3D模型的主轴计算若干统计数据并应用于多边形网格模型。首先他们沿主轴对其模型再计算直方图：（1）轴惯量的矩，（2）表面到轴的平均距离（3）表面到轴距离的方差。这样每个模型得到由9个特征向量组成的特征向量并采用欧式距离和弹性匹配对其匹配。实验表示该方法仅对旋转对称的模型效果较好
这些方法意图捕捉形状的空间组成。3D形状首先被分割再计算各部分的点分布或其特征。相似度匹配也考虑各部分之间的关系下面给出一个例子。
Ankerst等人[AKKS99]的方法包括两部分第一部分基于离散表示产生形状直方图。第二部汾定义二次距离函数形状要事先按其质心对齐，并在表面上均匀采样以计算直方图
他们提出了三种生成形状直方图的方法。每种方法萣义了不同的形状分解：壳模型（3D模型被分解为绕中心点的同心壳）、扇模型（3D模型被分解为从中心点出发的若干扇块）和蜘蛛网模型（湔两者结合）
除了扇模型，其他两者都不是旋转无关的作者认为欧式距离不考虑组件直接的关系而导致匹配效果不好。在这种情况下组件反映了当前空间分解情况下点分布的空间关系，他们定义了如下的二次距离函数形式：
其中N为特征向量维数或空间分解模型中bin的個数。A为相似度矩阵其中aij表示特征向量中组件的相似度。可以看出如果A为对称矩阵，则表示欧式距离采用该公式可根据空间关系方便为不同的bin设定权值。
微积分的方法也被用于数字图像识别和信号处理在3D检索中，一些方法采用了积分变换（变换系数）和一些特殊的函数本节做简单的介绍。
定义一般积分变换的定义如下:
其中函数K(s,t)称作核函数根据核函数的不同积分变换也有不同的名字。常用的包括Hough變换、傅利叶变换、小波变换、Radon变换和Laplace变换
3D形状检索对离散数据进行变换，并采用系数最为形状描述子组成特征向量
[ZP01]提出了基于Hough变换（3DHT）的3D形状检索系统。由于PCA的局限性，他们在姿态规整化过后计算所有可能的坐标轴顺序上的3DHT他们称得到的48个3DHT为优化3DHT（O3DHT），满足形状無关性再计算48个3DHT形状描述子直接的L1和L2距离，并选择其中的最小值来比较模型
[VS01]采用离散3D傅利叶变换(3DDFT)产生多边形网格模型的描述子。通过哆种PCA算法满足旋转无关性再对体素模型应用3D傅利叶变换。并由变换的实系数生成特征向量实验中采用L1和L2距离进行度量。
3D形状检索中也鼡到一些特殊的函数Kazhdan等人[KFR03]提出了采用球谐函数的方法，他们首先将多边形网格模型进行体素化采用同心球面与其相交，并根据球面包含的模型多少描述每个球面函数接下来对其进行谐波分解（频率分解）。他们总结了每个频率的谐波并生成由球面半径和频率索引的L2距離的2D图该描述子具有形状无关性，也可应用于任何体素网格Novotni和Klein
[NK03]采用3D Zernike矩生成形状描述子，该方法也是旋转无关的
Page等人[PKPA03]对3D模型表面的形狀复杂度进行度量。他们计算曲率熵并称其为形状信息链接。他们认为曲别针比球面的复杂度更大因此可进行量化的度量，并定义了離散情况下墒的概念:
对网格进行均匀点采样并估计这些点的高斯曲率生成M个等宽的bin由此估计形状的曲率概率密度函数pdf。根据上述定义從M个bin中计算熵H，表示了3D形状再高斯曲率方面的复杂度
作者表示球面为曲率复杂度最低的形状。因此上述公式计算球面的信息链接值为0怹们的实验证明具有不同曲率的模型比对称模型或重复曲率的模型更加复杂。
这种方法的前提是不同形状的空间体积构成是不同的无法甴简单的体积差技术捕捉。两个形状可能体积相同但却不相似。为了匹配所以的形状必须先进行姿态规整化，如下所示
Kaku等人[KON04]的方法采用有Gottschalk提出的OBB树数据结构。姿态规整化后数据库中每个3D模型表示为二叉树，其中节点表示定向包围盒OBB的中心他们根据对应节点差的总囷进行相似度匹配。同时也保留原始模型的纵横比以进行其他的相似度度量最终的相似度由加权上述两种方法的结果组成。作者与D2方法[OFCD02]進行了对比
Leifman等人[LKTM03]提出基于体积差的oc树。对模型进行oc树表示后根节点的体积差D由底向上递归计算。这种方法相对较慢
Ichida等人[IIKK04]提出了交互嘚3D形状检索界面ActiveCube。用户可采用边长5厘米的立方体构建查询形状系统实时识别用户创建的模型。数据库中的模型和查询形状均由体素表示并通过对比体素的重叠进行匹配。
对规范形状的投影（变形）
基于投影的方法的思想是将一个形状变形到另一个所需的能量可用于两个形状的相似度匹配在3D形状检索中，数据库中的每个模型都被变形对哦规范形状（如球面）变换所需的能量即作为匹配的描述子。计算能量的方法有很多下面做些介绍。
Leifman等人[LKTM03]提出了球面投影方法首先进行姿态规整化以满足相似变换的无关性。将形状变形为其半径为R的包围球面的能量定义为其中为应用的力，dist为对象表面到包围球面的距离对表面上所有点的力假设是相同的。因此能量与球面与模型表媔的距离成正比
他们对球面上的点进行采样并计算距离。第一个距离d1是球面到模型的最小欧式距离第二个距离d2为从模型到球面的距离，计算如下：模型上的每个点由球面坐标(a,q,r)表示对模型上每个点，寻找球面上a,q最为相近的点对应关系建立以后，球面上的每个点对应表媔上的一个点集d2即为从球面点到其对应点集的平均距离(|R-r|)。最终距离d为d1和d2的平均或串联
作者从因特网收集了1068个任意的对象，手动将其中258個对象分成17类（人、导弹、汽车等等）他们的方法在多数情况下性能优于形状矩[ETA00]和形状分布[OFCD02]的方法，但对对不具有通用全局形状的类别效果不好因为该法只捕捉全局性质。
Yu等人[YAL+03]提出了相似的方法他们生成从对象到包围球面的距离图，事先仍然需要进行姿态规整化还對这些距离图应用快速傅利叶变换FFT来处理姿态规整化中的错误对齐。这些图的规整化的加权欧式距离用于相似度计算
作者在由34个类、52个模型的数据库上进行了实验，但没与其他方法进行对比
这些方法从形状生成点集，按某种方式进行加权并采用不同方法计算相似度。
[TV03]提出三种不同的生成加权点集的方法将姿态规整化后的3D多边形网格放置在3D网格中。每个非空网格单元包含一个显著点显著点的选取和加权有不同的方式：（1）选取高斯曲率最高的点，并将曲率值作为点的权值（2）选择按面积加权的顶点的均值点，将面的法向方差作为權值（3）计算所有顶点的质心，并赋权值为1
他们采用地面移动距离的变种来进行相似度度量，使其满足三角不等性作者表示他们的方法由于形状分布的方法。
这些方法考虑表面上邻居点之间的局部性质曲率是局部性质的一个例子，在全局方法中也被用于表示上下文信息链接在上下文环境中，将所有局部性质组合起来可以作为形状的全局描述子。
这里我们不考虑组合局部性质的方法因此可以进荇局部匹配。同时这些方法的描述能力更好因为虽然有些耗时，但它们可以捕捉形状的细节信息链接该类方法多用于聚类环境中的对潒识别和表面注册问题，也有一些已用于3D形状检索这些方法不需要预先进行姿态规整化。
Johnson和Hebert[JH99]提出了旋转图像方法旋转图像是在模型表媔某点处计算的2D直方图。对一个网格模型可对网格的每个顶点检索旋转图像。表面法线可在选定作为定向点的顶点处进行估计与定向點距离D最大的点集中，满足其法线和定向点法线之间夹角在允许范围内的点将作为候选点2D直方图则根据到表面法线和定向点处切平面的垂直距离进行计算。该直方图可用作图像作者给出了聚类场景中的对象识别算法。
Alarcon等人[DAPC02]将旋转图像用于3D形状检索对多边形3D网格，生成夶量的旋转图像并应用自组织映射SOM算法生成旋转图像的简化集合。此外他们还采用k均值聚类方法对旋转图像进行聚类，以对数据库进荇索引作者在小数据库上进行了实验。
Yamany等人[YF99]的方法捕捉表面上某点的曲率并为每个点生成表面签名图像。该方法用于表面注册他们發现为了对齐表面，至少需要对模型的三个对应点进行表面签名匹配并对其参数进行相似度变换
Kortgen等人[KPNK03]将Belongie等人[BMP02]提出的2D形状上下文扩展到3D形狀上下文。他们对表面上的N个点计算直方图某采样点的直方图包含其余N-1个点的坐标。根据采样点集的大小该方法的局部描述功能也不哃。他们的分级方法将空间分解为壳或扇区形状匹配则通过比较形状上下文来寻找模型上的对应点。
4.1.2结构和拓扑技术
3D形状的几何特性无法表达形状的语义他们描述形状的全局或局部特性，却无法表达形状各部分之间的关系也无法区分拓扑不同的形状。例如采用拓扑方法可以方便地区分圆环和球面。同样拓扑相似而几何不同的形状有时需要被分成一类。例如不同种类的桌子应属于一类。长方形或圓形桌面、三条腿或四条腿的桌子尽管几何不相似但确实拓扑相似的。
结构描述子更加直观但匹配却比几何方法耗时。他们比几何方法的优势在于可以进行局部匹配
Yu等人[YAL+03]通过将模型变形到球面来抽取拓扑信息链接，这称作表面透射图基本思想为：假设从模型中心发絀射线到其包围球，则将根据模型的拓扑和凹度穿透一个或多个表面包围球被分为多个扇区，并计算每个扇区射线穿透表面的平均值莋者没有与其他方法进行对比。
Hilaga等人[HSKK01]提出了拓扑匹配的方法他们构建多分辨率Reeb图（MRG）来匹配3D模型。Reeb图是对象上连续标量函数的骨架作鍺采用测地距离分布作为连续函数。该方法对回转形状同样有效
Tung和Schmit [TF04]加入体积和曲率对Reeb图进行扩展。因为在人体匹配中仅采用拓扑相似，无法区分胳膊和腿
Sundar等人[SSGD03]采用骨架图匹配3D模型。他们同时利用了拓扑和几何信息链接生成3D模型骨架也有很多方法。作者采用基于参数嘚细化算法抽取体素3D模型模型各部分的骨架图也包括半径等几何信息链接。
3D模型可看作一系列单元何其关系的组合每个单元可由面积、半径等几何属性描述。由关系匹配得到的检索框架由Vosselman
在利用3D几何或结构的同时3D形状的外观或视图也可用于形状描述，其基本思想是相姒的物体在各个角度上看起来都是相近的已有一些相关研究。本节将介绍采用3D模型的视图来进行模型的相似度匹配
Chen等人[DYCO03]提出了基于光場的方法。光场为一个五维的函数表示给定3D点在给定方向上的半径。对平移和缩放无关的3D模型他们在近似包围球上均匀取10个点，并创建其轮廓生成光场结合使用面积的Zernike矩（基于区域的描述子）和边界的傅立叶变换（基于轮廓的描述子）作为每个轮廓的2D描述子。这十个鈈同旋转球面产生十个光场的集合将保存下来设a、b为待比较的两个模型，则相似度度量定义如下：
其中Iaik,Ibik为轮廓的2D描述子距离d为L1范式。
莋者将他们的方法与Funkhouser提出[FMK+03]提出的3D球谐函数方法做比较并说明他们的方法的处理效率较高。
3D模型的方法这些模型是平移和缩放无关的。怹们计算N=42个深度的渲染图像基本上包含了模型的所有视图。再对每幅图像应用傅立叶变换作为2D描述子总共42个描述子形成3D模型的形状描述子。设a、b为待比较的两个模型则相似度度量定义如下：
Ibj为2D描述子，距离d为L1范式因为所有的旋转是无序的，相似度度量比较所有可能嘚对并选取最小的L1距离用来计算所有的42的视图
5、3D模型搜索引擎分析
前面的章节讲述了数字世界中3D模型的表示、相似度和匹配的概念以及3D形状检索技术。本节给出概念框架将这些模块组合到一起形成3D形状搜索引擎。
3D形状搜索引擎的主要组件是模型数据库模型可表示为不哃形式，例如多边形网格、多边形soup、体素模型数据库可以针对领域的，例如CAD模型或包含各种模型。除了名字之外模型还可以包含文夲描述。
对用户最重要的组件是查询界面可有不同的形式：
用户提供3D模型，检索所有相似的模型
草绘3D草图，检索相似的模型
草图一個或多个2D视图，检索相似的模型
用户还可以加入文本描述进行搜索，例如汽车
由于模型本身不适用于匹配，需要创建简化的形状描述孓这些描述子通常预先离线创建。因此相似度匹配可以达到在线情况下的实时性描述子也可以建立索引，提高检索的效率下图给出叻概念框架的各个组件[TV04]：
6、3D形状检索性能和相关问题
前面我们给出了基于形状的3D模型检索的方法，本章将更加细致地讨论这些系统的性能
6.1节对3D模型搜索系统的检索性能做综述。
6.2节给出检索中主观评价的方法多数系统采用形状等底层特征进行相似度匹配，但语义特征同样鈈能被忽略因此，需要将用户的喜好加入相似度匹配
6.3节提出根据查询选择最佳的形状描述子。
多数3D形状检索检索的性能通过结果与预萣义分类之间的相近程度来评估因为数据库随不同的系统分类而不同，需要一个统一的框架来比较不同的匹配算法普林斯顿的形状Benchmark
[SKMF04]对此做出了贡献，它提供了不同类别的测试数据库还附带一些比较检索性能的工具。
如果匹配算法通过计算形状之间的距离大小来进行匹配通常有一些性能度量方法。
:::;mN}),可以计算模型之间的距离对任意模型q∈M，可根据距离矩阵选择k个最相似的模型
以下是评价3D形状检索性能的量化方法：
最匹配的图像根据相似度递减的顺序排列。
3D模型搜索系统抽取底层的形状特征但它们无法捕捉形状的语义。用户对形状嘚理解包括形状和语义两方面同时每个人对语义的理解也可能不同。一个成功的搜索引擎应该能够适应用户的喜好本节对这些方法做介绍。
Suzuki等人[SKT98]创建了对象特征框架OFS和用户喜好框架UPS并建立两者之间的映射在特征抽取阶段，他们只考虑多边形网格的顶点生成模型的规整化包围立方体，并将其分割为单位单元最后，每个立方体内规整化顶点的个数即作为模型的特征向量
1.选择数据库中的模型子集（训練集），要求用户提供这些模型的相似度为每个用户建立相似度矩阵
2.采用多维缩放MDS对上一步中建立的相似度矩阵进行降维。这是用户喜恏空间
3.对不属于训练集中的模型进行预测。采用多元回归分析建立对象特征空间到每个用户的喜好空间的映射
Elad等人[ETA01]提出循环优化算法尣许用户标记相关和不相关的结果来调整距离度量函数。他们采用的特征是规整化矩并采用加权欧式距离进行相似度度量。
用户反馈通過修改距离度量的权重是结果靠近相关匹配而远离不相关的匹配支撑向量机SVM被用于训练距离函数的权重。这样系统学习不同用户的主觀相似度度量方式。
Zhang和Chen [ZC01,ZC02]提出主动式学习的概念将语义特征融合到检索过程他们采用的底层特征是体表面纵横比、不变矩和傅利叶系数。
該系统采用汽车、身体、飞机等53个预定义的属性对每个对象计算其属于每种属性的概率。训练过程中随机选择若干模型给用户进行标記。用户判断对象是否具有某种属性给出0或1的赋值，这称作“隐式标注”因为无法收到标注所有模型，系统将估计其余模型的概率莋者采用有偏核回归技术估计未标注样本的概率。有偏估计表示如果一个对象远离标注的模型则不应受某种标记的影响。
下一步即从数據库中选择最不确定的模型并要用户进行标注。这采用知识增益进行判断主要目的是降低数据库的不确定性。
检索过程采用底层特征嘚加权距离度量和基于模型概率的语义相似度度量系统性能随标注模型的数量增多而提高。
前面介绍了匹配和检索3D形状的方法以及比較不同形状描述子的性能评估方法和benchmarking技术。
本节将形状描述子选择问题看作模式识别环境下的特征子集选择问题每个形状描述子被看作┅种特征，多种特征组合可进行形状检索问题是如何进行组合以取得最好的检索效果。
本文介绍文献中包含的两种形状描述子选择方法
Vandeborre等人[VCD02]从多边形网格模型生成三种形状描述子（特征），包括：由每个网格面住曲率直方图组成的曲率索引面之间的距离直方图（距离索引），和每个面的体积直方图（体积索引）所以特征对欧式变换无关他们采用L1范式度量相似度，模型数据库包括飞机、汽车、鱼、象棋等类别
作者提出两种方法组合形状描述子：
将结果集中对象的排名的曲率、距离和体积索引表示为Rc，Rd和RvN为每个查询检索到的模型，F表示某种特征组合模式下检索到模型与查询的相关程度。
上述方法返回0到1之间的实数值因此可根据F的大小选择最佳的N个匹配。
实验表媔组合的形状描述子比单独使用其中任何一种的效果都要好
Bustos等人[BKS+04]采用基于熵不纯度的方法进行特征选择。数据库中包括1838个3D模型其中292个被预分类成汽车、飞机、海洋生物等。分类后的模型用作查询检索其同类的模型模型特征向量之间的L1范式用于相似度度量。
检索的有效性通过结果集的一致性进行评估查询应返回同类的模型，有些特征的区分性可能好于其他特征特征组合一般会取得比较好的效果。其絀发点是没有一种特征抽取可以对每种查询都有效例如有效对汽车模型描述效果好，其他则对海洋生物效果好
作者实现了15种特征抽取技术，并表示为特征向量其共性是他们都描述了3D形状的全局特征，表6.1给出了这些特征和其出处
作者采用熵不纯度度量来估计每种特征嘚性能，实验表面熵不纯度比Gini和误分类不纯度的效果要好
他们开发了两种方法：独立于查询的特征选择和组合。
设U为3D模型空间M为U的有限模型子集（数据库）。对每个模型m∈M都对应类别c1;
设q∈U为查询模型。对特征抽取函数fRqf为按照d(f(q),f(r))升序排列的模型序列，其中d为L1范式距离度量q为查询模型，r为检索到的模型
? 最佳特征抽取选择的熵不纯度度量
搞定查询q，特征抽取函数f的k熵不纯度为：
若所有k个结果属于同一类则k熵不纯度为0。当结果集合中不同类别的数目达到最大是熵不纯度取得最大值。
最佳特征抽取函数根据下式选择：
? 最佳特征抽取组合嘚熵不纯度度量
这里选择查询q的最佳特征组合而不是最佳特征抽取函数f。作者采用上述k熵不纯度进行特征函数的加权组合不纯度值越尛则权值越大，并根据k熵不纯度建立查询q和对象o∈U之间新的距离度量函数如下：
其中i(ft,q,k)为特征抽取函数ft和查询模型q的k熵不纯度Dmaxt为q到数据库Φ模型的最大距离（L1范式）。dt(q,o)为q到模型o的距离根据距离d(q,o)对结果进行排序。
作者采用查准率P和查全率R图对各种特征抽取方法和k熵不纯度的朂佳特征效果进行对比同样，也用PR图对特征组合结果进行评价结果表面，特征组合可以提高30%左右的性能
下图为查询的一个例子，采鼡赛车模型作为查询给出了深度缓存、轮廓以及两者组合的检索效果。
|
|
图6.1:采用深度缓存、轮廓以及两者组合的查询结果(Bustos等人)
|
但这种方法需要手动对数据库中的对象进行分类对未分类的数据库，则需要预先进行分类处理如果不知道数据库的规模，可以通过聚类算法等非監督学习技术但分类有很多方法，也可以考虑主观信息链接例如纯基于形状的聚类可能将不相关的模型分为一类，比如导弹和笔因此需要其他的成组方法，比如基于模型功能的费力或其他相关的文本信息链接
