7th International Symposium on Computer Music Modeling and Retrieval (CMMR 2010) 会议网址： http://www.icad.org/node/3106 论文提交截止日期：2010年1月15日，录用通知：2010年3月1日 会议地点：西班牙马拉加，2010年6月21日2010年6月24日 该会议基本是每年召开一次，CMMR 2010已是7届，历届会议论文均刊登在Springer出版的丛书丛刊《Lecture Notes in Computer Science》上，2010年的7届会议论文仍旧刊登在《Lecture Notes in Computer Science》，该会议论文均被EI、ISTP收录。 2008年5届CMMR会议刊登在Lecture Notes in Computer Science，2009年Volume 4969被EI、ISTP收录23篇，其中芬兰5篇，丹麦、德国各3篇，法国2篇，比利时、巴西、意大利、挪威、西班牙、突尼斯等各1篇。 会议主题： Auditory perception and cognition * Virtual reality, augmented reality and human-computer interaction * Digital music libraries * New methods for music representation and visualization * Retrieval and recommendation tools * Games and interactive learning * Music production and composition tools * Structuring of audio data * Cooperative music networks * Analysis, recognition, comparison, classification, and modeling of sound and music * Music and sound data mining * Sound synthesis * Optical music recognition * Semantic music technologies * Sound source separation * Music structure analysis * Music transcription * Artificial intelligence and cognitive science for sound and music
信息检索领域最著名的奖是Gerald Salton奖，由信息检索领域顶级会议SIGIR发布，获得Salton奖的，毫无疑问是IR里公认的大牛，比如仙逝的Salton与Karen、Rijsbergen、Robertson、Dumais、Croft等。 欧盟向来有与美国争夺科技制高点的传统，老美搞SIGIR，EU就搞ECIR（European Conference in Information Retrieval），SIGIR设立SALTON奖，ECIR就出来了Karen Sparck Jones奖。 无论从纪念Karen教授的角度，还是从推动IR研究与应用的角度来说，这都是大好事。 关于Karen奖的情况可以参见下面附件。 -------------------------------------------------------------------------- 附： Karen Sparck Jones Award情况 BCS / BCS IRSG Karen Sparck Jones Award An Award to Commemorate Karen Sparck Jones *** Information Retrieval and Natural Language Processing **** *** Deadline for nominations 30 October, 2009 **** The British Computer Society Information Retrieval Specialist Group (BCS IRSG) in conjunction with the BCS has created an award to commemorate the achievements of Karen Sparck Jones. Karen was an Emeritus Professor of Computing and Information at the University of Cambridge and one of the most remarkable women in computer science. Her contributions to the fields of Information Retrieval (IR) and Natural Language Processing (NLP), especially with regards to experimentation, have been outstanding and highly influential. Karen's achievements resulted in her receiving a number of prestigious accolades such as the BCS Lovelace medal, for her advancement in Information Systems, and the ACM Salton Award for her significant, sustained and continuing contributions to research in information retrieval. In order to honour Karen's achievements, the BCS/BCS-IRSG has established an annual award to encourage and promote talented researchers who have endeavoured to advance our understanding of Information Retrieval and Natural Language Processing with significant experimental contributions. To celebrate the commemorative event, the recipient of the award would be invited to present a keynote lecture at the BCS-IRSG's annual conference the European Conference in Information Retrieval (ECIR). This forum provides an excellent venue to present and announce the award as the conference attracts many new and younger researchers. The recipient would also be presented with a prize consisting of a certificate, a trophy and a cash prize of 1000 plus expenses to travel to ECIR. BCS/BCS-IRSG Karen Sparck Jones Award: Eligibility: Open to all IR/NLP researchers, who have no more than 10 years post doctoral or equivalent experience. Criteria: To have endeavoured to advance our understanding of IR and/or NLP through experimentation. Nominations: The following should be provided - name, position, affiliation, years since completing PhD, a short case for the award (composed of a short description of why the individual should receive the award), a short description of what contributions the individual has made, a list of the individuals top five publications reflecting the relevant contributions, and two referees. The nomination text should not exceed 2500 words. If you are intending to nominate someone or yourself, it would be helpful, at this stage nearing the deadline, if you could let us know in as soon aspossible in advance (contact as per further below ayse.goker.1@soi.city.ac.uk). Award Panel: The Panel Chair, appointed by the BCS IRSG Committee, will invite panel members from amongst representatives of the BCS main council, the BCSIRSG Committee, sponsoring organisation(s), as well as at least two experts appointed by the BCS-IRSG committee and the Awards Coordinator of the BCSIRSG. Prize: The recipient of the award would receive a certificate, a trophy, a cash prize of 1000 plus expenses to travel to ECIR to present the keynote lecture. Presentation: The recipient of the award is expected to give a keynote lecture at ECIR when he/she would also be presented with their trophy, and cash prize. Timeline: 8 April, 2009 - Call for nominations. 30 October, 2009 - Deadline for nominations. 15 December, 2009 - Notification of the prize winner. 28-31 March, 2010- Winner presents keynote at ECIR. Sponsors: Currently, the award is being sponsored by the BCS IRSG and Microsoft Research Cambridge. Contact: Ayse Goker, ayse.goker.1@soi.city.ac.uk http://irsg.bcs.org/ksjaward.php http://irsg.bcs.org/ksjaward/KSJ_Award_Flyer_final.pd
1 、 引言 在互联网、计算机辅助设计（ 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 数据最基本的特征。用户对形状的概念并没有统一的定义。下面给出一些最常用的定义： 韦氏字典形状（名词）： 1、 某个或某种特定对象的可见组成特性。 2、 轮廓的空间形态。 3、 标注的或普遍公认的空间形态。 Kendall's 的定义 ： 形状是对象的位置、比例、方向被去除后剩下的所有几何信息。 Kendall's 的定义认为对象的形状与其相似性变换无关，例如，汽车的 3D 模型再旋转、缩放或平移情况下应该是保持不变的。对给定的 2 个模型，直观上确定其是否相似的方法是寻找模型直接的对应关系并将模型重合。重合的程度即说明了模型的相似度。这种方法被 Besl 和 McKay 提出，称为形状注册问题。其主要应用是从多视角（例如 3D 点阵）重合模型以进行 3D 重建。但这在大型数据库的 3D 模型检索中的效率并不高。 目前 3D 模型检索的方法以简洁的方式描述模型（特征向量或图等结构化描述），并比较这些简洁的描述子来加快匹配的速度。因为形状是旋转、平移和缩放无关的，描述子也应该是变换无关的，或者数据库中的 3D 模型都预先被变换到规范的坐标系中。这即为姿态规范化问题。 本文对基于内容的 3D 形状检索的进行调研。上文以指出形状是 3D 数据最基本的特征，因此文中会交替使用 3D 形状、 3D 模型和 3D 对象等术语。同样，文献中 3D 模型检索或 3D 模型搜索引擎都代表同样的研究领域。 荷兰乌特列支大学的 Tangelder 和 Veltkamp 在形状表示、相似度 / 不相似度度量、检索性能、部分匹配能力、鲁棒性和姿态规范化需求等方面对形状检索方法进行评价。普度大学机械工程学院的 Lyer 等人 对包括具体 CAD 方法的形状搜索技术进行了概述。新加坡国立大学的 Atmosukarto 和 Naval 给出了当前技术的介绍。此外， Siggraph2004 的 3D 想着检索课程也由 Funkhouser 和 Kazhdan 在普林斯顿大学的计算机科学系开展。 本文的结构如下： 第二章给出 3D 形状表示技术的综述。由于 3D 形状重建（激光扫描、基于立体视觉的重建、运动结构）和建模（ CAD 根据）的方法不同，这些数据在数字环境中的组织方法也不同。文中给出静态和动态模型（摆动或变形）的表示方法，但只给出静态模型的相似度和匹配方法。 第三章介绍形状相似度和匹配的概念。 第四章介绍相似度匹配和模型检索中的 3D 形状描述方法。这些方法分为 2 类：直接从 3D 模型抽取（基于模型的）或从其 2D 投影中抽取（基于视图的）。基于模型的方法可以是纯几何的、结构的或两者的结合。几何方法包括全局或局部的形状描述。 第五章介绍 3D 形状搜索引擎的整体结构及各部分子系统。 第六章给出 3D 形状检索系统的评价和性能描述。 2 、数字世界中的 3D 形状表示 许多应用都需要在数字环境中构造真实时间中的对象，这些模型的质量受到硬件和软件能力的限制。近来硬件的发展是用户可以更方便的可视化和操作复杂的模型。当前的扫描技术也可以生产几何精确的对象模型。除了硬件的发展，建模软件（例如 CAD 工具）的功能也越来越健全。 由于创建对象模型有不同的方法，数字环境中数据的技术也有不同。本章将对这些技术做简单的介绍。如前所述，这里只讲述对象形状的表示方法，不包括纹理和颜色。本章的 3D 对象表示方法可用于处理 3D 形状建设系统的输入数据。由于模型生产过程本身的原因，其中一些方法比其他方法更为普遍。 在数字世界中， 3D 模型的首要工作是可视化，有时也需要对模型进行编辑。 3D 模型的存储和显示的效率是主要关心的问题。不同的任务可能需要不同的表示方法。例如，如果需要识别场景中的对象，我们不需要非常细致的对象模型。本文不涉及 3D 模型重建、对象识别和相关的技术。读者可参阅这些技术的相关文献，包括 Campbell 和 Flynn ， Jain 和 Dorai ， Bennamoun 和 Mamic 以及 Pope 。 形状大致可以分为 2 类：静态形状和动态形状。静态形状为不受形变和转动而改变的刚性形状。例如咖啡杯的模型为静态形状，而人脸则为动态形状，因为其形状随说话、微笑等动作而变化。本文主要考虑静态形状的检索技术，因此只会稍微提及动态形状的表示。 2.1 静态形状 表示对象有 2 种不同的方法：基于模型（对象为中心）和基于试图（观察者为中心）的方法。基于模型的方法直接作用于 3D 数据，而基于试图的方法则存储 3D 模型的若干 2D 投影。 2.1.1 基于模型的表示 3D 对象可在不同抽象层次进行表示。首先是 3D 空间的原始数据点集表示，这种表示缺乏结构性，但足够进行可视化。这相当于 2D 图像中的像素。第二抽象层是形状的轮廓，也就是 3D 形状的表面，这与 2D 曲线相对应。第三抽象层为体表示，这与 2D 形状的面积相对应。 2.1.1.1 基于点的表示 点集 点集的定义为点 P={p1,p2,,pN} 的集合，其中 P R 3 且 pi=(xi,yi,zi) T 。 图 2.1: 两个点集的 2D 抽点打印（ Bunny 兔子和 CAD 模型） 范围图像 范围图像与密度图像都从某个视角捕捉形状，但与捕捉颜色信息不同的是，范围图像捕捉距离的深度信息。图 2.2 由 Ohio 州立大学给出了的天使的密度和范围图像。这种表示多用于 3D 模型重建，将不同视角的图像进行合并。这是 3D 形状注册的一个例子。 图 2.2: Ohio 州立大学的天使图像（密度和范围图像） 范围图像中深度值根据不同的图像生成方式而变化。例如，在图 2.2 中，对象离摄像机越远，则相应的像素值越深。反之依然，见图 2.3 。 图 2.3: 范围图像数据库中的多面体对象（密度和范围图像） 2.1.1.2 表面表示 3D 形状可由其外表面表示，这类似 2D 形状的轮廓。本节介绍表示形状表面的数学模型。 多边形 Soups 这种表示多用于 CAD 工具，也称作多边形 Soup 模型。这种模型中所有的多边形不完全相连。 3D 模型检索中多认为这种模型是错误定义的，而网上的很多 3D 模型都是以多边形 Soups 表示的。 图 2.4: 一个多边形 Soup 的 CAD 模型 多边形网格 多边形网格由于其简单性成为表示 3D 模型的常用方法。 3D 模型的多边形网格的定义为一对有序的链表： M= P ， V 其中， V={v1,v2,,vN} 为顶点的列表且 vn=(xn,yn,zn) T ； P={p1,p2,,pN} 为平面多边形的列表，且 pr=(v n,1 , v n,2 , , v n,kr ) 。 Kr 为多边形 pr 的顶点数目。如果所有 pr 的 k=3 ，则所有 pr 均为三角形网格。 图 2.5: 人脚骨的多边形网格模型 ( ) 参数形式 一般 3D 表面的参数形式由如下定义： 图 2.6: 以网格形式显示的 NURBS 曲线 ( ) 其中 u 和 v 为参数变量。 3D 表面由两曲线进行笛卡尔积生成。非均匀有理 B 样条（ NURBS ）是一种参数形式，其定义如下： 其中 N 和 M 为 k 阶和 l 阶的 B 样条基函数， B h i,j 为控制点的齐次坐标。 参数形式通常用于最初的模型表示，之后再由此生成多边形网格的表示 。 子分表面 由提出的子分表面的思想是很简单的：子分定义了一系列逐渐精化的光滑曲线或表面。 下图介绍如何从粗略的表示构建精确的表面。左边网格中的每个三角形都根据子分规则细分成 4 个三角形，得到中间网格。再进行子分操作则得到右边的网格。 图 2.7: 子分表面 ( ) 子分表面是建模和动画中非常有用的表示方法，它可以捕捉不同分辨率层的模型。具体介绍间文献 隐式表面 3D 表面可隐式定义为任意函数 f 的 0 集如下： 下图给出了由公式 生成的模型。 图 2.8: 隐式表面 ( ) 超二次曲面 超二次曲面的定义为由向量包含的闭合曲面，向量的 x,y,z 由角度函数和两个 2D 参数曲线进行球积确定。 超椭圆体为一种超二次曲面，其参数形式如下： 其中 (a1; a2; a3) T 为缩放向量， 1 2 表示平面经纬度上的正方度。 超二次曲面可以通过增加特定的加尖、扭转、弯曲等操作对多种自由形体进行建模。下图给出了由沿 z 轴加尖后绕 z 轴扭转变化后的超二次曲面 。 图 2.9: 变形的超二次曲面 ( ) 2.1.1.3 体表示 体素 体素是体绘制中最小的 3D 单元，相当于 2D 绘制中的像素。 该方法是最简单的空间子分表示方法，但耗费内存。在医学应用中使用较多。 图 2.10: 由体素表示的飞机模型 ( ) 八分树 八分树是基于空间的子分表示方法，立方体空间被递归地分成更小的立方体，进而建立层次的数据结构。下图给出了实体模型的八分树。 图 2.11: 八分树表示 白色节点表示空的子立方体，黑色节点表示完全填充的子立方体，灰色节点表示部分填充的子立方体。这种方法比体素的更节省内存。 空间二分树（ BSP ） 空间二分树是八分树的另外一种表示方式。 BSP 树提供了对象或空间中的多个对象的搜索结构和几何表示。 图 2.12: 2D 对象的 BSP 树 ( ) 非叶结点表示被二份的平面。平面可从任何方向进行子分。 图 2.13: 多对象的 2DBSP 树表示 ( ) 构造实体几何 (CSG) 构造实体几何是一种层次化的表示。每个形状由形状单元通过二值操作组合而成。 图 2.14: CSG 通用圆柱体 这种方法也称作扫描表示，由环状轮廓 C(s, ) 沿模型主轴（样条）的空间曲线 A(s) 移动生成。 图 2.15: 通用圆柱体 ( ) 2.1.2 基于视图的表示 基于试图的表示的出发点是相似的 3D 形状从相同的视角看起来也是相似的，因此可采用对象的一系列视角（ 2D 投影）来表示形状。 该方法通常用于对象识别，本节将介绍一些主要技术。 轮廓 轮廓包括对象某个视角的边界。为了表示 3D 形状，需要生成并存储轮廓的集合。相对于基于模型的表示，这种方法更加简洁。该方法通常用于对象分类，采用一系列轮廓表示模型并从匹配相应的视图。但不同的 3D 形状可能具有相同的轮廓图像组。 图 2.16: 椅子的轮廓图像 ( ) 视点图 3D 形状从不同视角看起来可能是不同的。例如，立方体的上视图是一个正方形。因此，可将视图空间分成视图类或典型视图。每类的视图具有某种相同的属性，并可由聚类算法生成试图类。 1979 年 Koenderink 和 van Doorn 将视图类表示称为视点图。图中的结点表示根据视点命名的视图类，连接不同结点的边表示视点的改变。结点之间的不同称作视觉事件。但这种表示较复杂，使用受限。 图 2.17: 视点图表示 2.2 动态形状 在建模和视觉应用中常涉及到动态形状。这些形状可以随时间摆动或形变，且有多种表示方法。下面是一些例子 。 Snakes: 主动轮廓模型 对给定点集拟合其形变轮廓 (snakes) 是一个约束的能量最小化问题。主动轮廓模型由 Kass, Witkin 和 Terzopoulos 于 1987 年提出 。其中总能量包括三个组成部分：弯曲或伸展轮廓的内部轮廓能量， . 轮廓和图像密度或梯度间的图像能量，和预定义约束下的外部能量。 形变体模型 Park, Metaxas 和 Axel 根据心脏运动的四面体元素对人类心脏的运动进行建模。 气球模型 这是一种形变的网格表示，其中通过弹簧建模网格的边，使得整个网格可随用户而拉伸或压缩。 Chen 和 Medioni 给出了这种表示的例子。 3 、形状相似度和匹配概念 形状匹配比较两个形状的相似性，是检索、识别和注册等应用中非常重要的概念。通常，这通过计算距离进行不相似度度量，其中距离越小不相似性越小，相似性越大 。 定义 ：给定形状集合 S={s 1 ,s 2 ,,s N } ，相似度距离由 d(s i ,s j ):S S R + 0 定义，其中 s i ,s j S ，距离函数 d 具有如下性质： (i) 自相似性 : s i S, d(s i ,s i ) = 0 (ii) 正定性 : s i , s j S, s i s j , d(s i ,s j ) 0 (iii) 对称性 : s i , s j S, d(s i , s j ) = d(s j , s i ) (iv) 三角不等性 : s i , s j ,s k S,d(s i , s k ) d(s i ,s j ) + d(s j ,s k ) (v) 变换无关性 : 对给定变换组 G ， s i , s j S,g G,d(s i ,g(s j ))=d(s i ,s j ). 自相似性表示形状与本身完全匹配。正定性表示两个不同的形状无法完全匹配。 定义： 具有自相似性、正定性、对称性和三角不等性的距离函数称作度量。 定义： 具有自相似性、对称性和三角不等性的距离函数称作伪度量。 定义： 具有自相似性、正定性、对称性的距离函数称作半度量。 3.1 形状匹配问题分类 给定两形状 s 1 ， s 2 和不相似度度量 d ， Veltkamp 对形状匹配做了如下分类： ▲ 计算问题 令 d 为变换无关的不相似度函数，计算 d(s 1 ; s 2 ). ▲ 决策问题 令 d 为变换无关的不相似度函数，给定阈值 t ，判断是否 d(s 1 ; s 2 ) t 。 ▲ 决策问题 给定阈值 t ，判断是否存在变换 g ，其中 d(g(s 1 ); s 2 ) t. ▲ 最优化问题 寻找变换 g ，其中 d(g(s 1 ); s 2 ) 最小。很多形状匹配的应用需要以此为基础。 ● 基于形状的检索 给定形状数据库 S={s1, s2, sN} 和查询形状 q ，检索与 q 相似的形状。有两种方法： 1 ）（决策问题）给定阈值 t ，寻找所有 d(q,si)t 的形状。 2 ）（计算问题）寻找 d(q,si) 最小的 k 个形状。 ● 形状识别和分类 1 ）（决策问题）给定形状 s 和模型 o ，判断是否 d(s,o) 足够小。 2 ）（计算问题）给定形状 s ， k 类形状以及各类形状表示 r1, r2, ,,,, rk ，找到类 ri ，使得 d(ri,s) 最小。 ● 形状校准和注册 ( 优化问题 ) 给定两形状 s1 和 s2 ，寻找变换 g 使得 d(g(s1),s2) 最小。 如上所述，这个问题通常被 3D 形状检索的文献归为计算问题。给定查询模型，系统返回数据库中最相似的模型。 形状匹配中形状的表示方法，决定了相似度度量的选择。 第四章对 3D 形状检索中的匹配技术做综述。本节给出最常用的相似度度量。 Veltkamp 给出了计算几何模型中的形状匹配以及多边形和曲线匹配的相似度度量方法的综述。 ● L p 范式 (Minkowski 距离 ) 该方法用于匹配数字的向量形式的形状描述子。 定义： 给定 x ， y 两点，则 Lp 距离定义为： 对 p1 ， Lp 距离为一种度量。 若 p=1 ，称为 L1 范式或曼哈顿距离或城市块距离。 若 p=2 ，称为 L2 范式或欧几里德距离。 Lp 距离不是变换无关的不相似性度量。 图 3.1: 2D 空间满足 ||x||p=1 的点 ● Hausdorff 距离 定义 给定由点集表示的两个形状 X={x1,x2,,xM} 和 Y={y1,y2,,yN} ，则 X 和 Y 之间的 Hausdorff 距离定义为： H(X,Y) = max(h(X,Y),h(Y,X)) 其中 ， ||.|| 为欧几里德距离。 图 3.2: Hausdorff 距离的可视化 Hausdorff 距离是一种度量。但它不是变换无关的，且对噪音不够鲁棒。这种方法的优点是可以进行局部匹配。 点集 A 和 B 之间的 Hausdorff 距离定义为： H(A,B) = max(h(A,B),h(B,A)) 其中 且 。 ||a-b|| 表示点 a 和 b 之间的距离度量（例如欧几里德距离）。 h(A;B) 称为 A 到 B 的有向 Hausdorff 距离，等于 A 中点到 B 中点最近距离的最大值。直观上如果 h ( A;B ) = d ，则 A 中的每个点距离 B 中点的距离不超过 d 。 h(B;A) 称为 B 到 A 的有向 Hausdorff 距离，按照同样的方法计算。注意通常 h ( A;B ) h ( B;A ) ，图 5 给出了示例。 Hausdorff 距离为两有向距离中的最大值。 图 5: 有向 Hausdorff 距离距离示意图。 Hausdorff 距离为两有向距离的最大值，即本图中的 h ( A;B ) . 原始 Hausdorff 距离对噪音敏感。如图 5 所示，如果两个接近的点集中有一个较远的噪音点，则 Hausdorff 距离将受噪音影响而无法确定两点集的相似性。在模式识别中，噪音和异常通常会导致这样的问题。 提出了变形的局部 Hausdorff 距离来缓解这一问题，他对 A 中点到 B 中点的距离进行降序排列，并将第 k 个点的距离赋为 h ( A;B ) 。 A 到 B 的局部 Hausdorff 距离可如下定义： 例如，对 k=3 ， h 3 (A,B) 将忽略 A 中较远的两点，而选择 A 到 B 第三远的距离。 h k (B;A) 按照同样方法计算。局部 Hausdorff 距离通过舍弃较远的噪声点使得距离度量更加灵活。接下来的文章中我们采用 6% 排序进行有向距离的计算，其中舍弃 6% 远的点。该数值根据我们的系统由经验确定。 尽管在实现中采用局部 Hausdorff 距离代替原始 Hausdorff 距离，方便起见在下文中我们仍使用 Hausdorff 距离指代局部 Hausdorff 距离。由于 Hausdorff 距离的原始形式使用的较少，在文献中这两者的称呼也经常通用。但我们需要区分 Hausdorff 距离与接下来在下节中介绍的变形 Hausdorff 距离。 不管是计算第 k 个还是最大有向距离值， h(A;B) 都需要计算 A 中每个点到 B 中点的最近距离。通过距离变换可加速计算的过程。主要思想在训练阶段预先 一次 计算所有需要的距离值，在识别过程中通过索引快速地获取想要的距离值。在系统中，我们通过距离的阶进行加速变换。具体的变换方法和模版匹配的应用可在 4.5 节，相似度度量之后进行介。， 变形 Hausdorff 距离 提出了变形 Hausdorff 距离 (MHD) ，将有向距离计算中的 max 操作符替换为距离的平均值 : 其中 N a 为 A 中点的数目。变形 Hausdorff 距离则等于两有向平均距离中的最大值 : Although 虽然当 k = 50% 时 与 相似， 但前者为平均有向距离而后者为其中值。 Dubuisson 和 Jain 认为在对象匹配时，平均有向距离比局部有向距离更可靠，因为前者收噪音影响较小。 我们仍然采用距离变换辅助距离计算。变形 Hausdorff 距离比原始 Hausdorff 距离的计算性能更高，因为无需存储最小距离信息。 ● 弹性匹配距离 定义 令 A={a1,a2,,aM} 和 B={b1,b2,,bN} 为有限的有序轮廓点集， f 为 A 与 B 中所有点的相关性并满足 : { ai,aj A,aiaj f(ai)f(aj)} 。伸缩 s 定义为 : 则 A 与 B 之间的非线性弹性匹配距离为 : 其中 d(a i ; b j ) 为 ai 与 bi 正切角的差。 距离可通过动态规划方法计算。弹性匹配距离不满足三角不等性，因此不是度量。 ● 地面移动距离 这也被称作传输距离。 定义 给定加权点对 A={(A1,w(A1)),(A2,w(A2)),,(AM,w(AM))} 以及 B={(B1,w(B1)),(B2,w(B2)),,(BN,w(BN))} ，其中 A i ;B i R 2 。 A 与 B 之间的传输距离为将 A 转换到 B 的所需的最小工作量。 3.2 3D 形状匹配的距离函数 根据定义， 3D 对象的形状独立于任何平移、算法和旋转。因此距离函数也应具有变换无关性。独立于所有可能变换的距离函数可由如下公式给出 : 其中 G 为变换组。 该距离函数对 3D 形状匹配并不十分有效。下面给出两种变换无关的定义 定义 ( 姿态规整化 ) : 给定形状集合 S={s1,s2,,sN} ，度量 d(si,sj) 和变换组 G 。设 n 为多到一的函数，其中 g G ， si S,n(g(si))=?i 且 si,sj S,d(si,sj)~d(?i, ?j) ，则 d(si,sj)~d(?i, ?j)=d(g(si),g(sj)) G 为平移、缩放和旋转等变换的任意组合。 G 上定义的函数 n 即称作姿态规整化函数。 定义 ( 不变特征 ) : 给定形状集合 S={s1,s2,,sN} ，度量 d(si,sj) 和变换组 G 。令 f + 为函数，其中 g G, si S,f+(g(si))=f+(si) 且 d(si,sj)~d(f+(si), f+(sj)) ，则 d(si,sj)~d(f+(si), f+(sj))=d(g(f+(si)),g(f+(sj)) 函数 f+ 称作 不变特征抽取函数 。 3D 形状的表示形式无法用于匹配。因此需要简化的描述子（形状描述子）来捕捉这些重要的形状特征。 定义 ( 形状描述子生成 ) : 给定形状集合 S={s1,s2,,sN} ， 度量 d(si,sj) 。令 f 为函数 ， 其中 si S, d(si,sj)~d(f(si), f(sj)) 。则 f 称作形状描述子生成函数。 若 f 对平移、缩放和旋转无关，则称作无关形状描述子生成函数。 形状描述子可以是数字的或结构化的。 数字形状描述子生成映射 X-Rn ，其中 X 为原始形状表示空间。 定义 ( 基于 3D 形状的检索问题 ) : 给定 3D 形状数据库 S={s 1, s 2 ;, s N} 以及查询形状 q ，寻找与 q 相似的形状。 解决方案 : （决策问题）给定阈值 t ，寻找所有 d(f(q),f(si))t 的形状。 （计算问题）寻找 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 对其进行了比较详尽的介绍。这种方法需要捕捉足够多的视图来反映 3D 模型的各个方面。 4.1 基于模型的技术 3D 形状检索中基于模型的方法作用于 3D 形状本身，主要有两类方法。有些方法只考虑全局或局部的形状特性，其他方法考虑形状的结构特性，如空洞和组件等。 4.1.1 几何方法 这些方法挖掘形状的量化的特性，包括从形状中抽取出的体积、纵横比、表面积、曲率或其他数字的描述子。这些特性可以是全局的或局部的。全局特性计算速度快但无法进行局部匹配，而局部的方法则刚好相反。 4.1.1.1 全局形状描述子 全局方法把形状看作一个整体，已有很多描述对象全局形状的方法。本节按照主要思想对这些方法进行分类。 特征 给定形状，直观的方法是提取可区分不同形状的特征，例如体积、表面积或由形状表面或体积计算得到的矩。但这些特征描述里不强，因此可用于 3D 形状检索的初步过滤。 Elad 等人 提出了应用于多边形网格的基于矩的方法。他们定义了近似矩，检索如下： 作者首先在模型表面采用 N 的点。对一阶矩中心化可使其满足平移无关性，对采样点计算二阶矩的 3*3 矩阵进行分解可满足缩放和旋转无关性。规整化后计算 3D 模型的矩并生成特征向量，再根据欧几里德距离计算相似度。 Zhang 和 Chen 描述了有效计算多边形网格体积、表面积和矩的有效方法。 特征分布 这些方法采用特征的分布，本节将稍作介绍。 Osada 等人 提出了全局特征的分布方法，并通过概率分布比较得到相似度。他们定义了不同的全局几何形状函数： A3: 3D 形状表面上任意三点的角度度量。 D1: 固定点与表面上任意点的距离度量。通常固定点选择形状边界质心。 D2: 表面上任意两点的距离度量。 D3: 表面上任意三点组成三角形的面积的开发度量。 D4: 表面上任意四点组成四面体体积的开立方度量。 这些函数容易计算，且具有旋转和平移无关性。为了从这些函数产生形状分布，研究者在上述函数的每个形状分布中采样 N 个点，再创建 B 等宽的直方图。这些直方图即为分布的近似。形状相似度匹配也就转换为直方图匹配，可根据 Minkowski 范式、 Kolmogorov-Smirnov 距离、 Kullback-Leibler 散度、地面移动距离、 Bhattacharyya 距离、 X 2 统计等方法计算。 作者实现了八种计算简单的相似度度量。设 a 、 b 为待比较的两个形状， fa 、 fb 为通过直方图近似的形状概率分布函数（ pdf ）， f^a 、 f^b 为累积分布函数。相似度度量为： ? ? Bhattacharyya 距离： ? Pdf 的 Minkowski （ Lp ）范式： ? Cdf 的 Minkowski （ Lp ）范式： 这些方法不满足缩放无关性，需要进行规整化处理。作者表示 D2 函数在实验中效果最好。 Obhuchi 等人 和 Ip 等人 给出了 D2 方法的扩展。 Obhuchi 等人 提出了一种方法，沿 3D 模型的主轴计算若干统计数据，并应用于多边形网格模型。首先他们沿主轴对其模型，再计算直方图：（ 1 ）轴惯量的矩，（ 2 ）表面到轴的平均距离，（ 3 ）表面到轴距离的方差。这样每个模型得到由 9 个特征向量组成的特征向量，并采用欧式距离和弹性匹配对其匹配。实验表示该方法仅对旋转对称的模型效果较好。 空间图 这些方法意图捕捉形状的空间组成。 3D 形状首先被分割，再计算各部分的点分布或其特征。相似度匹配也考虑各部分之间的关系。下面给出一个例子。 Ankerst 等人 的方法包括两部分。第一部分基于离散表示产生形状直方图。第二部分定义二次距离函数。形状要事先按其质心对齐，并在表面上均匀采样以计算直方图。 他们提出了三种生成形状直方图的方法。每种方法定义了不同的形状分解：壳模型（ 3D 模型被分解为绕中心点的同心壳）、扇模型（ 3D 模型被分解为从中心点出发的若干扇块）和蜘蛛网模型（前两者结合）。 除了扇模型，其他两者都不是旋转无关的。作者认为欧式距离不考虑组件直接的关系而导致匹配效果不好。在这种情况下，组件反映了当前空间分解情况下点分布的空间关系，他们定义了如下的二次距离函数形式： 其中 N 为特征向量维数，或空间分解模型中 bin 的个数。 A 为相似度矩阵，其中 aij 表示特征向量中组件的相似度。可以看出，如果 A 为对称矩阵，则表示欧式距离。采用该公式可根据空间关系方便为不同的 bin 设定权值。 积分变换和特别函数 微积分的方法也被用于数字图像识别和信号处理。在 3D 检索中，一些方法采用了积分变换（变换系数）和一些特殊的函数。本节做简单的介绍。 定义 一般积分变换的定义如下 : 其中函数 K(s,t) 称作核函数。根据核函数的不同积分变换也有不同的名字。常用的包括 Hough 变换、傅利叶变换、小波变换、 Radon 变换和 Laplace 变换。 3D 形状检索对离散数据进行变换，并采用系数最为形状描述子组成特征向量。 Zaharia 和 Preteux 提出了基于 Hough 变换（ 3DHT ）的 3D 形状检索系统。由于 PCA 的局限性，，他们在姿态规整化过后计算所有可能的坐标轴顺序上的 3DHT 。他们称得到的 48 个 3DHT 为优化 3DHT （ O3DHT ），满足形状无关性。再计算 48 个 3DHT 形状描述子直接的 L1 和 L2 距离，并选择其中的最小值来比较模型。 Vranic 和 Saupe 采用离散 3D 傅利叶变换 (3DDFT) 产生多边形网格模型的描述子。 通过多种 PCA 算法满足旋转无关性，再对体素模型应用 3D 傅利叶变换。并由变换的实系数生成特征向量，实验中采用 L1 和 L2 距离进行度量。 Paquet 等人 采用基于小波变换的 3D 模型检索。 Daras 等人 则采用 3D Radon 变换和 L1 距离进行匹配。 3D 形状检索中也用到一些特殊的函数。 Kazhdan 等人 提出了采用球谐函数的方法，他们首先将多边形网格模型进行体素化，采用同心球面与其相交，并根据球面包含的模型多少描述每个球面函数。接下来对其进行谐波分解（频率分解）。他们总结了每个频率的谐波并生成由球面半径和频率索引的 L2 距离的 2D 图。该描述子具有形状无关性，也可应用于任何体素网格。 Novotni 和 Klein 采用 3D Zernike 矩生成形状描述子，该方法也是旋转无关的。 信息理论方法 Page 等人 对 3D 模型表面的形状复杂度进行度量。他们计算曲率熵，并称其为形状信息。他们认为曲别针比球面的复杂度更大，因此可进行量化的度量，并定义了离散情况下墒的概念 : 对网格进行均匀点采样并估计这些点的高斯曲率生成 M 个等宽的 bin ，由此估计形状的曲率概率密度函数 pdf 。根据上述定义，从 M 个 bin 中计算熵 H ，表示了 3D 形状再高斯曲率方面的复杂度。 作者表示球面为曲率复杂度最低的形状。因此上述公式计算球面的信息值为 0 。他们的实验证明具有不同曲率的模型比对称模型或重复曲率的模型更加复杂。 体积差 这种方法的前提是不同形状的空间体积构成是不同的，无法由简单的体积差技术捕捉。两个形状可能体积相同，但却不相似。为了匹配，所以的形状必须先进行姿态规整化，如下所示。 Kaku 等人 的方法采用有 Gottschalk 提出的 OBB 树数据结构。姿态规整化后，数据库中每个 3D 模型表示为二叉树，其中节点表示定向包围盒 OBB 的中心。他们根据对应节点差的总和进行相似度匹配。同时也保留原始模型的纵横比以进行其他的相似度度量。最终的相似度由加权上述两种方法的结果组成。作者与 D2 方法 进行了对比。 Leifman 等人 提出基于体积差的 oc 树。对模型进行 oc 树表示后，根节点的体积差 D 由底向上递归计算。这种方法相对较慢。 Ichida 等人 提出了交互的 3D 形状检索界面 ActiveCube 。用户可采用边长 5 厘米的立方体构建查询形状。系统实时识别用户创建的模型。数据库中的模型和查询形状均由体素表示，并通过对比体素的重叠进行匹配。 对规范形状的投影（变形） 基于投影的方法的思想是将一个形状变形到另一个所需的能量可用于两个形状的相似度匹配。在 3D 形状检索中，数据库中的每个模型都被变形对哦规范形状（如球面），变换所需的能量即作为匹配的描述子。计算能量的方法有很多，下面做些介绍。 Leifman 等人 提出了球面投影方法。首先进行姿态规整化以满足相似变换的无关性。将形状变形为其半径为 R 的包围球面的能量定义为 ，其中 为应用的力， dist 为对象表面到包围球面的距离。对表面上所有点的力假设是相同的。因此能量与球面与模型表面的距离成正比。 他们对球面上的点进行采样并计算距离。第一个距离 d1 是球面到模型的最小欧式距离，第二个距离 d2 为从模型到球面的距离，计算如下：模型上的每个点由球面坐标 ( a,q, r) 表示，对模型上每个点，寻找球面上 a,q 最为相近的点。对应关系建立以后，球面上的每个点对应表面上的一个点集。 d 2 即为从球面点到其对应点集的平均距离 (|R-r|) 。最终距离 d 为 d1 和 d2 的平均或串联。 作者从因特网收集了 1068 个任意的对象，手动将其中 258 个对象分成 17 类（人、导弹、汽车等等）。他们的方法在多数情况下性能优于形状矩 和形状分布 的方法，但对对不具有通用全局形状的类别效果不好，因为该法只捕捉全局性质。 Yu 等人 提出了相似的方法。他们生成从对象到包围球面的距离图，事先仍然需要进行姿态规整化，还对这些距离图应用快速傅利叶变换 FFT 来处理姿态规整化中的错误对齐。这些图的规整化的加权欧式距离用于相似度计算。 作者在由 34 个类、 52 个模型的数据库上进行了实验，但没与其他方法进行对比。 加权点集 这些方法从形状生成点集，按某种方式进行加权，并采用不同方法计算相似度。 Tangelder 和 Veltkamp 提出三种不同的生成加权点集的方法。将姿态规整化后的 3D 多边形网格放置在 3D 网格中。每个非空网格单元包含一个显著点。显著点的选取和加权有不同的方式：（ 1 ）选取高斯曲率最高的点，并将曲率值作为点的权值，（ 2 ）选择按面积加权的顶点的均值点，将面的法向方差作为权值，（ 3 ）计算所有顶点的质心，并赋权值为 1 。 他们采用地面移动距离的变种来进行相似度度量，使其满足三角不等性。作者表示他们的方法由于形状分布的方法。 4.1.1.2 局部形状描述子 这些方法考虑表面上邻居点之间的局部性质。曲率是局部性质的一个例子，在全局方法中也被用于表示上下文信息。在上下文环境中，将所有局部性质组合起来，可以作为形状的全局描述子。 这里我们不考虑组合局部性质的方法，因此可以进行局部匹配。同时这些方法的描述能力更好，因为虽然有些耗时，但它们可以捕捉形状的细节信息。该类方法多用于聚类环境中的对象识别和表面注册问题，也有一些已用于 3D 形状检索。这些方法不需要预先进行姿态规整化。 Johnson 和 Hebert 提出了旋转图像方法。旋转图像是在模型表面某点处计算的 2D 直方图。对一个网格模型，可对网格的每个顶点检索旋转图像。表面法线可在选定作为定向点的顶点处进行估计。与定向点距离 D 最大的点集中，满足其法线和定向点法线之间夹角在允许范围内的点将作为候选点。 2D 直方图则根据到表面法线和定向点处切平面的垂直距离进行计算。该直方图可用作图像。作者给出了聚类场景中的对象识别算法。 De Alarcon 等人 将旋转图像用于 3D 形状检索。对多边形 3D 网格，生成大量的旋转图像，并应用自组织映射 SOM 算法生成旋转图像的简化集合。此外，他们还采用 k 均值聚类方法对旋转图像进行聚类，以对数据库进行索引。作者在小数据库上进行了实验。 Yamany 等人 的方法捕捉表面上某点的曲率，并为每个点生成表面签名图像。该方法用于表面注册。他们发现为了对齐表面，至少需要对模型的三个对应点进行表面签名匹配并对其参数进行相似度变换。 Kortgen 等人 将 Belongie 等人 提出的 2D 形状上下文扩展到 3D 形状上下文。他们对表面上的 N 个点计算直方图。某采样点的直方图包含其余 N-1 个点的坐标。根据采样点集的大小，该方法的局部描述功能也不同。他们的分级方法将空间分解为壳或扇区。形状匹配则通过比较形状上下文来寻找模型上的对应点。 4.1.2 结构和拓扑技术 3D 形状的几何特性无法表达形状的语义。他们描述形状的全局或局部特性，却无法表达形状各部分之间的关系，也无法区分拓扑不同的形状。例如，采用拓扑方法可以方便地区分圆环和球面。同样，拓扑相似而几何不同的形状有时需要被分成一类。例如，不同种类的桌子应属于一类。长方形或圆形桌面、三条腿或四条腿的桌子尽管几何不相似，但确实拓扑相似的。 结构描述子更加直观，但匹配却比几何方法耗时。他们比几何方法的优势在于可以进行局部匹配。 表面透射图 Yu 等人 通过将模型变形到球面来抽取拓扑信息，这称作表面透射图，基本思想为：假设从模型中心发出射线到其包围球，则将根据模型的拓扑和凹度穿透一个或多个表面。包围球被分为多个扇区，并计算每个扇区射线穿透表面的平均值。作者没有与其他方法进行对比。 图结构 Hilaga 等人 提出了拓扑匹配的方法。他们构建多分辨率 Reeb 图（ MRG ）来匹配 3D 模型。 Reeb 图是对象上连续标量函数的骨架，作者采用测地距离分布作为连续函数。该方法对回转形状同样有效。 Tung 和 Schmit 加入体积和曲率对 Reeb 图进行扩展。因为在人体匹配中，仅采用拓扑相似，无法区分胳膊和腿。 Sundar 等人 采用骨架图匹配 3D 模型。他们同时利用了拓扑和几何信息，生成 3D 模型骨架也有很多方法。作者采用基于参数的细化算法抽取体素 3D 模型。模型各部分的骨架图也包括半径等几何信息。 关系结构 3D 模型可看作一系列单元何其关系的组合。每个单元可由面积、半径等几何属性描述。由关系匹配得到的检索框架由 Vosselman 给出。同时 Haralick 和 Shapiro 给出了基于关系距离定义的一致标记框架。 4.2 基于视图的技术 在利用 3D 几何或结构的同时， 3D 形状的外观或视图也可用于形状描述，其基本思想是相似的物体在各个角度上看起来都是相近的，已有一些相关研究。本节将介绍采用 3D 模型的视图来进行模型的相似度匹配。 Chen 等人 提出了基于光场的方法。光场为一个五维的函数，表示给定 3D 点在给定方向上的半径。对平移和缩放无关的 3D 模型，他们在近似包围球上均匀取 10 个点，并创建其轮廓生成光场。结合使用面积的 Zernike 矩（基于区域的描述子）和边界的傅立叶变换（基于轮廓的描述子）作为每个轮廓的 2D 描述子。这十个不同旋转球面产生十个光场的集合将保存下来。设 a 、 b 为待比较的两个模型，则相似度度量定义如下： 其中 I a ik ,I b ik 为轮廓的 2D 描述子，距离 d 为 L1 范式。 作者将他们的方法与 Funkhouser 提出 提出的 3D 球谐函数方法做比较，并说明他们的方法的处理效率较高。 Obhuchi 等人 提出应用于多边形 soup 3D 模型的方法。这些模型是平移和缩放无关的。他们计算 N=42 个深度的渲染图像，基本上包含了模型的所有视图。再对每幅图像应用傅立叶变换作为 2D 描述子。总共 42 个描述子形成 3D 模型的形状描述子。设 a 、 b 为待比较的两个模型，则相似度度量定义如下： 其中 I a i , I b j 为 2D 描述子，距离 d 为 L 1 范式。 因为所有的旋转是无序的，相似度度量比较所有可能的对并选取最小的 L 1 距离用来计算所有的 42 的视图。 5 、 3D 模型搜索引擎分析 前面的章节讲述了数字世界中 3D 模型的表示、相似度和匹配的概念以及 3D 形状检索技术。本节给出概念框架，将这些模块组合到一起形成 3D 形状搜索引擎。 3D 形状搜索引擎的主要组件是模型数据库。模型可表示为不同形式，例如多边形网格、多边形 soup 、体素模型。数据库可以针对领域的，例如 CAD 模型，或包含各种模型。除了名字之外，模型还可以包含文本描述。 对用户最重要的组件是查询界面，可有不同的形式： 用户提供 3D 模型，检索所有相似的模型。 草绘 3D 草图，检索相似的模型。 草图一个或多个 2D 视图，检索相似的模型。 用户还可以加入文本描述进行搜索，例如汽车。 由于模型本身不适用于匹配，需要创建简化的形状描述子，这些描述子通常预先离线创建。因此相似度匹配可以达到在线情况下的实时性。描述子也可以建立索引，提高检索的效率。下图给出了概念框架的各个组件 ： 图 5.1: 概念 3D 形状搜索引擎框架图 6 、 3D 形状检索性能和相关问题 前面我们给出了基于形状的 3D 模型检索的方法，本章将更加细致地讨论这些系统的性能。 本章的结构是： 6.1 节对 3D 模型搜索系统的检索性能做综述。 6.2 节给出检索中主观评价的方法。多数系统采用形状等底层特征进行相似度匹配，但语义特征同样不能被忽略。因此，需要将用户的喜好加入相似度匹配。 6.3 节提出根据查询选择最佳的形状描述子。 6.1 性能评估和 Benchmarking 多数 3D 形状检索检索的性能通过结果与预定义分类之间的相近程度来评估。因为数据库随不同的系统分类而不同，需要一个统一的框架来比较不同的匹配算法。普林斯顿的形状 Benchmark 对此做出了贡献，它提供了不同类别的测试数据库，还附带一些比较检索性能的工具。 如果匹配算法通过计算形状之间的距离大小来进行匹配，通常有一些性能度量方法。 给定形状匹配算法和 3D 模型 (M = {m 1 ;m 2 ; :::;m N }), 可以计算模型之间的距离。对任意模型 q M ，可根据距离矩阵选择 k 个最相似的模型。 以下是评价 3D 形状检索性能的量化方法： 最匹配的图像根据相似度递减的顺序排列。 查准率 - 查全率图 距离图像 等级图像 6.2 主观检索 3D 模型搜索系统抽取底层的形状特征，但它们无法捕捉形状的语义。用户对形状的理解包括形状和语义两方面，同时每个人对语义的理解也可能不同。一个成功的搜索引擎应该能够适应用户的喜好。本节对这些方法做介绍。 Suzuki 等人 创建了对象特征框架 OFS 和用户喜好框架 UPS 并建立两者之间的映射。在特征抽取阶段，他们只考虑多边形网格的顶点，生成模型的规整化包围立方体，并将其分割为单位单元。最后，每个立方体内规整化顶点的个数即作为模型的特征向量。 算法其余部分如下 : 1. 选择数据库中的模型子集（训练集），要求用户提供这些模型的相似度，为每个用户建立相似度矩阵 2. 采用多维缩放 MDS 对上一步中建立的相似度矩阵进行降维。这是用户喜好空间。 3. 对不属于训练集中的模型进行预测。采用多元回归分析建立对象特征空间到每个用户的喜好空间的映射。 Elad 等人 提出循环优化算法允许用户标记相关和不相关的结果来调整距离度量函数。他们采用的特征是规整化矩，并采用加权欧式距离进行相似度度量。 用户反馈通过修改距离度量的权重是结果靠近相关匹配而远离不相关的匹配。支撑向量机 SVM 被用于训练距离函数的权重。这样，系统学习不同用户的主观相似度度量方式。 Zhang 和 Chen 提出主动式学习的概念将语义特征融合到检索过程。他们采用的底层特征是体表面纵横比、不变矩和傅利叶系数。 该系统采用汽车、身体、飞机等 53 个预定义的属性，对每个对象计算其属于每种属性的概率。训练过程中，随机选择若干模型给用户进行标记。用户判断对象是否具有某种属性，给出 0 或 1 的赋值，这称作隐式标注。因为无法收到标注所有模型，系统将估计其余模型的概率。作者采用有偏核回归技术估计未标注样本的概率。有偏估计表示如果一个对象远离标注的模型，则不应受某种标记的影响。 下一步即从数据库中选择最不确定的模型，并要用户进行标注。这采用知识增益进行判断，主要目的是降低数据库的不确定性。 检索过程采用底层特征的加权距离度量和基于模型概率的语义相似度度量。系统性能随标注模型的数量增多而提高。 6.3 形状描述子选择 前面介绍了匹配和检索 3D 形状的方法，以及比较不同形状描述子的性能评估方法和 benchmarking 技术。 本节将形状描述子选择问题看作模式识别环境下的特征子集选择问题。每个形状描述子被看作一种特征，多种特征组合可进行形状检索，问题是如何进行组合以取得最好的检索效果。 本文介绍文献中包含的两种形状描述子选择方法。 Vandeborre 等人 从多边形网格模型生成三种形状描述子（特征），包括：由每个网格面住曲率直方图组成的曲率索引，面之间的距离直方图（距离索引），和每个面的体积直方图（体积索引）所以特征对欧式变换无关。他们采用 L1 范式度量相似度，模型数据库包括飞机、汽车、鱼、象棋等类别。 作者提出两种方法组合形状描述子： 将结果集中对象的排名的曲率、距离和体积索引表示为 Rc ， Rd 和 Rv 。 N 为每个查询检索到的模型， F 表示某种特征组合模式下，检索到模型与查询的相关程度。 ? OR 方法： ? MEAN 方法： 上述方法返回 0 到 1 之间的实数值，因此可根据 F 的大小选择最佳的 N 个匹配。 实验表面组合的形状描述子比单独使用其中任何一种的效果都要好。 Bustos 等人 采用基于熵不纯度的方法进行特征选择。 数据库中包括 1838 个 3D 模型，其中 292 个被预分类成汽车、飞机、海洋生物等。分类后的模型用作查询检索其同类的模型。模型特征向量之间的 L1 范式用于相似度度量。 检索的有效性通过结果集的一致性进行评估。查询应返回同类的模型，有些特征的区分性可能好于其他特征，特征组合一般会取得比较好的效果。其出发点是没有一种特征抽取可以对每种查询都有效，例如有效对汽车模型描述效果好，其他则对海洋生物效果好。 作者实现了 15 种特征抽取技术，并表示为特征向量。其共性是他们都描述了 3D 形状的全局特征，表 6.1 给出了这些特征和其出处。 方法 引用 深度缓存 Heczko 等人 体素 Heczko 等人 轮廓 Heczko 等人 体积 Heczko 等人 阴影 Vranic 和 Saupe 3D 谐波 Funkhouser 等人 形状复合函数 Vranic and Saupe 球谐射线 Vranic and Saupe 弦 Paquet et al. 矩 Paquet et al. D2 形状分布 Osada et al 3D FFT Vranic and Saupe 基于射线的方法 Vranic and Saupe 关系无关特征 Kato et al. 形状图谱 Zaharia and Preteux 表 6.1: Bustos 等人抽取的特征种类 . 作者采用熵不纯度度量来估计每种特征的性能，实验表面熵不纯度比 Gini 和误分类不纯度的效果要好。 他们开发了两种方法：独立于查询的特征选择和组合。 设 U 为 3D 模型空间， M 为 U 的有限模型子集（数据库）。对每个模型 m M ，都对应类别 c1; c2; :::; cN ，且 。 设 q U 为查询模型。对特征抽取函数 f ， R q f 为按照 d(f(q),f(r)) 升序排列的模型序列，其中 d 为 L1 范式距离度量， q 为查询模型， r 为检索到的模型。 设 P k (c n , R q f ) 为类 cn 中属于 R q f 前 k 个模型的比例。 ? 最佳特征抽取选择的熵不纯度度量 搞定查询 q ，特征抽取函数 f 的 k 熵不纯度为： 若所有 k 个结果属于同一类，则 k 熵不纯度为 0 。当结果集合中不同类别的数目达到最大是，熵不纯度取得最大值。 最佳特征抽取函数根据下式选择： 其中 F ={f1; f2; :::; fT} 为特征抽取函数集合。 ? 最佳特征抽取组合的熵不纯度度量 这里选择查询 q 的最佳特征组合，而不是最佳特征抽取函数 f 。作者采用上述 k 熵不纯度进行特征函数的加权组合。不纯度值越小则权值越大， 并根据 k 熵不纯度建立查询 q 和对象 o U 之间新的距离度量函数如下： 其中 i(f t ,q,k) 为特征抽取函数 f t 和查询模型 q 的 k 熵不纯度。 D max t 为 q 到数据库中模型的最大距离（ L1 范式）。 d t (q,o) 为 q 到模型 o 的距离。根据距离 d (q,o) 对结果进行排序。 作者采用查准率 P 和查全率 R 图对各种特征抽取方法和 k 熵不纯度的最佳特征效果进行对比。同样，也用 PR 图对特征组合结果进行评价。结果表面，特征组合可以提高 30% 左右的性能。 下图为查询的一个例子，采用赛车模型作为查询，给出了深度缓存、轮廓以及两者组合的检索效果。 图 6.1: 采用深度缓存、轮廓以及两者组合的查询结果 (Bustos 等人 ) 但这种方法需要手动对数据库中的对象进行分类。对未分类的数据库，则需要预先进行分类处理。如果不知道数据库的规模，可以通过聚类算法等非监督学习技术。但分类有很多方法，也可以考虑主观信息。例如纯基于形状的聚类可能将不相关的模型分为一类，比如导弹和笔。因此需要其他的成组方法，比如基于模型功能的费力或其他相关的文本信息。 参考文献 Mihael Ankerst, Gabi Kastenmuller, Hans-Peter Kriegel, and Thomas Seidl. 3d shape histograms for similarity search and classi_cation in spatial databases. In Ralf Hartmut Guting, Dimitris Papadias, and Frederick H. Lochovsky, editors, Advances in Spatial Databases, 6th International Symposium, SSD'99, Hong Kong, China, July 20-23, 1999, Proceedings, volume 1651 of Lecture Notes in Computer Science, pages 207-226. Springer, 1999. I. Atmosukarto and P. Naval. A survey of 3d model retrieval systems. not published, N/A 2003. not published. B. Bustos, D. Keim, D. Saupe, T. Schreck, and D. Vrani_c. Using entropy impurity for improved 3d object similarity search. In Proc. IEEE International Conference on Multimedia and Expo (ICME'04), 2004. P. J Besl and N. D. MacKay. A method for registration of 3-d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239-256, 1992. M. Bennamoun and G. J. Mamic. Object recognition: fundamentals and case studies. Springer- Verlag New York, Inc., 2002. Serge Belongie, Jitendra Malik, and Jan Puzicha. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(24):509-522, April 2002. Richard J. Cambell and Patrick J. Flynn. A survey of free-form object representation and recognition techniques. Computer Vision and Image Understanding, (81):166-210, 2001. Yang Chen and G_erard Medioni. Description of complex objects from multiple range images using an inating balloon model. Computer Vision and Image Understanding: CVIU, 61(3):325-334, 1995. De-Alarcon, Pascual-Montano PA, and JM Carazo. Spin images and neural networks for e_cient content-based retrieval in 3d object databases. In CIVR, 2002. Yu-Te Shen Ding-Yun Chen, Xiao-Pei Tian and Ming Ouhyoung. On visual similarity based 3d model retrieval. In Computer Graphics Forum (EUROGRAPHICS'03), volume 22, pages 223-232, September 2003. P. Daras, D. Zarpalas, D. Tzovaras, and M.G. Strintzis. Shape matching using the 3d radon transform. In 3D Data Processing, Visualization and Transmission, 2004. 3DPVT 2004, pages 953{960, september 2004. Michael Elad, Ayellet Tal, and Sigal Ar. Directed search in a 3d objects database using svm. Technical report, HP Laboratories, Israel, 2000. M. Elad, A. Tal, and S. Ar. Content based retrieval of vrml objects-an iterative and interactive approach. Eurographics Multimedia Workshop, pages 97{108, 2001. Thomas Funkhouser and Michael Kazhdan. Shape based retrieval and analysis of 3d models. Siggraph2004 Course 15, 2004. Thomas Funkhouser, Patrick Min, Michael Kazhdan, Joyce Chen, Alex Halderman, David Dobkin, and David Jacobs. A search engine for 3d models. ACM Trans. Graph., 22(1):83{105, 2003. M. Heczko, Keim, D. D., Saupe, and D. V. Vranic. Verfahren zur hnlichkeitssuche auf 3dobjekten. In Datenbank Spektrum Zeitschrift fr Datenbanktechnologie, volume 2, pages 54-63, 2002. Robert M. Haralick and Linda G. Shapiro. Computer and Robot Vision. Addison-Wesley Longman Publishing Co., Inc., 1993. Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu L. Kunii. Topology matching for fully automatic similarity estimation of 3d shapes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 203{212. ACM Press, 2001. Hiroyasu Ichida, Yuichi Itoh, Yoshifumi Kitamura, and Fumio Kishino. Interactive retrieval of 3d virtual shapes using physical objects. In IEEE Virtual Reality, 2004. N. Iyer, K. Lou, S. Janyanti, Y. Kalyanaraman, and K. Ramani. Three dimensional shape searching : State-of-the-art review and future trends. Computer Aided Design, 2004. Cheuk Yiu Ip, Daniel Lapadat, Leonard Sieger, and William C. Regli. Using shape distributions to compare solid models. In Proceedings of the seventh ACM symposium on Solid modeling and applications, pages 273{280. ACM Press, 2002. Anil J. Jain and Chitra Dorai. 3d object recognition: Representation and matching. Statistics and Computing, (10):167{182, 2000. A.E Johnson and M. Hebert. Using spin images for e_cient object recognition in cluttered 3d scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(5):433{449, May 1999. A. Young J. Park, D. Mataxas and L. Axel. Deformable models with parameter functions for cardiac motion analysis from tagged mri data. IEEE Transactions on Medical Imaging, 15:278{ 289, 1996. J. J. Koenderink and A. J. van Doorn. The internal representation of shape with respect to vision. In Biological Cybernetics, volume 32, pages 211{216, 1979. D.G. Kendall, Barden D., Carne T.K., and Le H. Shape and Shape Theory. Wiley Series in Probability and Statistics, 1999. Michael Kazhdan, Thomas Funkhouser, and Szymon Rusinkiewicz. Rotation invariant spherical harmonic representation of 3d shape descriptors. In Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing, pages 156{164. Eurographics Association, 2003. Keitaro Kaku, Yoshihiro Okada, and Koichi Niijima. Similarity measure based on obbtree for 3d model search. In International Conference on Computer Graphics, Imaging and Visualization (CGIV'04), volume I, pages 46{51, july 2004. M. Kortgen, G.J Park, M. Novotni, and R. Klein. 3d shape matching with 3d shape contexts. The 7th Central European Seminar on Computer Graphics, April 2003. Toshikazu Kato, Motofumi T. Suzuki, and Nobuyuki Otsu. A similarity retrieval of 3d polygonal models using rotation invariant shape descriptors. In IEEE International Conference on Systems, Man, and Cybernetics (SMC2000), pages 2946{2952, 2000. G. Leifman, S. Katz, A. Tal, and R. Meir. Signatures of 3d models for retrieval. 4th Israel Korea Bi-National Conference on Geometric Modeling and Computer Graphics, pages 159{163, 2003. A. Witkin M. Kass and D. Terzopoulos. Snakes: Active contour models. International Journal of Computer Vision, 1(4):321{331, 1987. Bruce Naylor. Representations of geometry for computer graphics. In Siggraph 1996 Course Notes, 1996. M. Novotni and R. Klein. 3d zernike descriptors for content based shape retrieval. Solid Modeling, 2003. Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin. Shape distributions. ACM Transactions on Graphics, 21(4):807{832, October 2002. Ryutarou Ohbuchi, Takahiro Minamitani, and Tsuyoshi Takei. Shape-similarity search of 3d models by using enhanced shape functions. In Proceedings of the Theory and Practice of Computer Graphics 2003, page 97. IEEE Computer Society, 2003. Ryutarou Ohbuchi, Masatoshi Nakazawa, and Tsuyoshi Takei. Retrieving 3d shapes based on their appearance. Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, pages 39{45, 2003. Ryutarou Ohbuchi, Tomo Otagiri, Masatoshi Ibato, and Tsuyoshi Takei. Shape-similarity search of three-dimensional models using parameterized statistics. In Proceedings of the 10th Paci_c Conference on Computer Graphics and Applications, page 265. IEEE Computer Society, 2002. D. L. Page, A. F. Koschan, J. K. Paik, and M. A. Abidi. Shape analysis algorithm based on information theory. In Proceedings of the International Conference on Image Processing, volume I, pages 229{232, 2003. E. Paquet, A. Murching, T. Naveen, A. Tabatabai, and M. Rioux. Description of shape information for 2-d and 3-d objects. In Signal Processing: Image Communication, volume 16, pages 103{122, 2000. A. R. Pope. Model-based object recognition: A survey of recent research. Technical report, Univ. of British Columbia, 1994. P. Shilane, M. Kazhdan, P. Min, and T. Funkhouser. The princeton shape benchmark. SMI, 2004. Motofumi T. Suzuki, Toshikazu Kato, and Hideo Tsukune. 3d object retrieval based on subjective measures. In Proceedings of the 9th International Workshop on Database and Expert Systems Applications, page 850. IEEE Computer Society, 1998. Linda G. Shapiro and George C. Stockman. Computer Vision. Prentice Hall, 2001. H. Sundar, D. Silver, N. Gagvani, and S. Dickinson. Skeleton based shape matching and retrieval. In Shape Modeling International, 2003, 2003. T.Tung and F.Schmitt. Augmented reeb graphs for content-based retrieval of 3d mesh models,. In International Conference on Shape Modeling and Applications (SMI'04), pages 157{166, 2004. J. Tangelder and R. Veltkamp. Polyhedral model retrieval using weighted point sets. Int. Journal of Image and Graphics, 3(1), pp. 209-229 (2003)., 2003. Johan W. H Tangelder and Remco C. Veltkamp. A survey of content based 3d shape retrieval methods. Shape Modeling Conference, 2004. Jean-Philippe Vandeborre, Vincent Couillet, and Mohamed Daoudi. A practical approach for 3d model indexing by combining local and global invariants. In 1st International Symposium on 3D Data Processing Visualization and Transmission, pages 644{647, 2002. R.C Veltkamp. Shape matching: Similarity measure and algorithms. In Proceedings Shape Modelling International, pages 188{197, 2001. G. Vosselman. Relational Matching. Lecture Notes in Computer Science, vol. 628, Springer Verlag., 1992. D. V. Vranic and D. Saupe. 3d model retrieval. In Proceedings Spring Conference on Computer Graphics 2000(SCCG2000), Budmerice, Slovakia, may 2000. D. V. Vranic and D. Saupe. 3d shape descriptor based on 3d fourier transform. In Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services(ECMCS 2001),Budapest, Hungary, pages 271{274, september 2001. D. V. Vranic and D. Saupe. Description of 3d-shape using a complex function on the sphere. In Proceedings IEEE International Conference on Multimedia and Expo, Lausanne, Switzerland, pages 177{180, August 2002. M. Yu, I. Atmosukarto, W. K. Leow, Z. Huang, and R. Xu. 3d model retrieval with morphingbased geometric and topological feature maps. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 2003. Sameh M. Yamany and Aly A. Farag. Free-form surface registration using surface signatures. In Proceedings of the International Conference on Computer Vision-Volume 2, page 1098. IEEE Computer Society, 1999. C. Zhang and T. Chen. E_cient feature extraction for 2d/3d objects in mesh representation. CIP, 2001. C. Zhang and T. Chen. An active learning framework for content based information retrieval. Technical report, CMU, 2002. D. S. Zhang and G. Lu. Review of shape representation and description techniques. Pattern Recognition, 37(1):1{19, 2004. T. Zaharia and F. Preteux. Hough transform-based 3d mesh retrieval. In Proceedings of SPIE 4476 on Vision Geometry X, San Diego, USA, august 2001. Dennis Zorin and Peter Schroder. Subdivision for modeling and animation. In Siggraph 1999 Course Notes, 1999. ( http://www.graphics.stanford.edu/data/mich ) ( http://www.formaurbis.stanford.edu/index.html ) ( http://edge.mcs.drexel.edu/repository/frameset.html ) ( http://www.rcsb.org/pdb ) ( http://www.viewtec.ch/meddiv/hugo_e.html ) ( http://www.nlm.nih.gov/research/visible/visible_human.html ) ( http://marathon.csee.usf.edu/range/DataBase.html ) ( http://sampl.eng.ohio-state.edu/~sampl/data/3DDB/RID/minolta/angel.0699/index.html )
标签: 信息检索
