matlab starcat_非刚性三维形状匹配中基于谱分析的形状描述符综述

非刚性三维形状匹配是图形学中的重要问题, 是形状识别[、形状检索[、形状配准[、形状分割[等工作的研究基础.同时, 非刚性形状匹配也为三维可视化[、生物计算[、人脸识别[、医学图像处理[等应用领域提供了坚实的理论依据.在上述研究中, 非刚性三维形状检索与非刚性三维形状匹配是两个非常相似却不相同的研究问题.非刚性三维形状检索的主要思想是:首先, 将非刚性三维形状库中的所有形状映射到特征空间中, 计算所有形状的特征值并添加索引; 其次, 根据用户的需求设置检索阈值, 并选择合适的相似度计算方法; 最后, 提取出满足阈值的形状, 并按照相似度降序输出形状[.而非刚性三维形状匹配研究的是形状相似性问题:同样将待匹配的形状映射到特征空间中, 选择形状的局部特征、全局特征或者两者的结合代替待匹配的形状; 然后选择某种代价函数或者距离函数度量特征, 并将特征之间的度量值作为非刚性三维形状匹配度.可将其概括为两个关键步骤:(1)提取形状上有效的形状描述符; (2)选择合适的相似度度量.

本文综述了非刚性三维形状匹配中基于谱分析的形状描述符.对于刚性三维形状匹配, 目前已有大量的研究成果[是最常用的三维形状匹配算法.ICP将形状上采样点的空间位置作为形状描述符, 通过多次迭代最小化源形状和目标形状采样点之间的空间距离, 实现刚性三维形状匹配.然而, ICP采用人为设置的迭代次数作为迭代终止条件, 导致算法容易陷入局部最优.此外, 对于有拓扑噪声的形状, 仅用空间位置作为形状描述符, 无法实现非刚性三维形状的高精度匹配.因此, 研究者需提取更加有效的形状描述符用于三维形状匹配.形状描述符是一种描述形状语义信息和几何信息的方法, 有时候也被称为某种算子, 研究者通过选择合适的形状描述符, 可以实现非刚性三维形状的高效匹配.常用的形状描述符一般包括4类:基于形状表面特征的描述符、基于形状统计特征的描述符、基于形状拓扑的描述符以及基于谱分析的形状描述符, 本文重点综述了基于谱分析的形状描述符.

第1类形状描述符致力于描述形状表面的特征及其在全局欧氏变换下的不变性.尺度不变特征变换(scale invariant feature transform, 简称SIFT)描述符[是其中应用最广的描述符, SIFT于1999年由Lowe等人提出, 被用于检测和描述图像中的局部特征, 并在2005年由Mikolajczy等人证明其具有很强的鲁棒性[.之后, 许多研究者也在此研究的基础上引入隐马尔可夫模型、核判别分析及测地线圆环等方法对其进行不断改进, 提高了SIFT的实时性及鲁棒性[描述了形状表面上图像中的线条, 同时存储每个点相对其他点位置的分布, 并给出形状上点的局部上下文信息, 在一定的图像区域内将点云分布转化为二维自旋图, 执行三维形状的表面匹配.为了分析有特殊铰链和关节的三维分子形状, Feng等人提出了一种基于节点感知的三维形状描述符[, 该描述符由形状边界上任意点的局部形状半径变化的信息编码定义, 用于描述有关节的三维形状.积分不变量(integral invariant)[由离散网格上顶点的几何特征定义, 例如曲率、测地线积分等, 该描述符描述了形状上的纹理特征而非几何特征.与此类似的还有Tombari等人提出的一种局部描述符——CSHOT描述符[, 该描述符通过匹配形状的特征点获得点对点的对应, 主要用于三维形状表面匹配、目标识别等.

第2类形状描述符基于对形状统计特征的描述, 主要描述形状的全局属性.Osada等人[在2002年提出了形状分布(shape distribution, 简称SD)描述符, 其算法步骤为:(1)在形状上选择合适的欧式度量函数, 如D1距离(测量形状上某个中心点到其他任意点的距离)、D2距离(测量形状上任意两点间的距离)以及D3距离(测量形状上任意3点组成区域面积的平方根)等, [使用基于D1距离改进的测地距离分布直方图作为新的形状描述符.测地距离是欧式空间中的直线段在黎曼流形上的推广, 具有等距不变性, 测地距离定义了曲面上两点间的最短距离[.测地距离不仅具有局部最短性, 还含有其他丰富的几何信息, 但当两点间的曲面部分发生缺失或者有缝隙时, 测地距离会因为联通路径不能通过而发生改变, 对拓扑变化鲁棒性不足.此后, 其他的工作也对此进行了改进, 但始终无法克服测地距离对拓扑变化的敏感性[.基于形状统计特征的形状描述符继承了统计学中统计量的稳定性, 在描述性状特征时鲁棒性较高, 很适用于分子形状比较(molecular shape comparison, 简称MSC)或者三维关节变形形状.Liu等人使用内部距离形状签名(inner distance shape signature, 简称IDSS)描述了三维分子形状, 并计算了IDSS直方图之间的度量作为三维分子形状间的相似度[.在此基础上, Liu等人基于可见性图提出一种新的内积距离计算方法, 计算了有关节的三维体模型的内部距离, 其对关节变形形状发生拓扑变化鲁棒, 能够很好地描述三维关节变形形状[.

图 1

Fig. 1

Fig. 1 Five distances defined in shape distribution

图 1 形状分布中定义的5种距离

第3类描述符基于对形状拓扑结构的特征提取, 该类描述符将三维形状匹配问题转换成其拓扑结构匹配问题, 应用两个形状拓扑结构的匹配结果作为形状的匹配结果.三维形状的拓扑结构精确地描述了形状的全局和局部几何形态特征, 并且保留了形状的层次结构.具有代表性的两类描述符分别是基于Reeb图理论的描述符和基于形状的骨架线理论的描述符,

图 2

Fig. 2

Fig. 2 Diagram of Reeb graph and skeleton with different shapes

图 2 不同形状Reeb图与骨架线图示

Reeb在1946年基于形状的拓扑结构提出了Reeb图的概念, 其具体步骤为:首先, 在三维形状的顶点上定义连续光滑函数f:M→R; 其次, 根据形状的顶点坐标计算顶点处的函数值, 并将顶点进行分类; 最后, 根据顶点分类结果将形状M映射为Reeb图R, 函数值相同且位于同一连通区域的顶点在Reeb图中映射为一个节点.Reeb图能够很好地刻画形状的拓扑结构, 且能起到降维的作用.定义合适的函数f是Reeb图算法的关键, 常用的函数f有高度函数和Morse函数.Shinagawa等人[采用高度函数、权重函数和形状上孔的数量等先验知识自动地生成三维形状的Reeb图.Hilaga等人[通过测地距离、测地线定义了Morse函数, 并基于此提出了多分辨率Reeb算法(MRG), Bespalov等人[在此研究上改进了MRG算法, 并用于CAD模型匹配.Biaso等人[基于Morse函数, 提出了扩展Reeb图算法(extend reeb graph, 简称ERG), 该算法刻画了形状上临界点之间的拓扑关系, 但该算法对形状发生拓扑变化时鲁棒性较差.Tierny J等人[基于特征点的思想构造Reeb图, 其通过特征提取算法提取形状的特征点, 并通过图构造方法生成Reeb图, 并应用Reeb图进行部分形状检索.骨架线, 也被称为三维形状的中轴, 是刻画三维形状拓扑结构的另一个重要方法, 不但能用线段很好地描述模型的结构信息, 而且能高效地保存形状, 提高形状空间存储率和形状检索率.Sundar等人[使用拓扑细化算法提取了形状的骨架线.Cao等人[提出了一种基于拉普拉斯压缩的骨架线提取算法, 该算法可快速提取点云模型的骨架线.Sfikas等人[基于形状的拓扑信息和共形几何特征, 提出了一种非刚性三维形状检索方法, 该算法具有稳健又高效的检索精度和计算速度.

以上3类形状描述符大多应用于描述刚性形状, 对于形状发生等距、拓扑等非刚性变化不鲁棒, 因此不适用于非刚性三维形状匹配.近年来, 应用基于谱分析的形状描述符进行非刚性三维形状匹配成为了一个新的研究热点, 部分研究工作[.谱分析源于形状的内蕴属性, 该方法提供了一种自然的方式进行非刚性三维形状匹配.

谱分析包括谱形状描述符及诱导出的谱距离, 常用的谱形状描述符包括形状DNA(shapeDNA)[、全局点签名(global point signature, 简称GPS)[、热核签名(heat kernel signature, 简称HKS)[、双调合签名(biharmonic signature, 简称BS)[、波动核签名(wave kernel signature, 简称WKS)[等.在一个形状表面上, 由谱形状描述符诱导出的谱距离[是一种较好的度量结构, 具有等距不变性以及对拓扑变化的鲁棒性.常用的谱距离包括交换时间距离(commute-time distance, 简称CD)[、热扩散距离(heat diffusion distance, 简称HDD)[、双调和距离(biharmonic distance, 简称BD)[及波核距离(wave kernel distance, 简称WKD)[.使用谱形状描述符进行三维非刚性形状匹配时, 需要选择数量一致的采样点, 为了避免非刚性形状匹配时采样点的选择问题, 基于SD方法, Bronstein等人提出使用谱距离分布函数作为一种新的形状描述符[.因此, 基于现有研究方法, 本文对基于谱分析的谱形状描述符和谱距离分布函数用于三维非刚性形状匹配进行了详细的研究.

本文第1节给出基于谱分析的三维非刚性形状匹配的一般框架、LB算子的详细介绍及离散化计算.第2节首先详细介绍了几种谱形状描述符:shapeDNA, GPS, HKS, BS, WKS, 给出了谱形状描述符的推导过程及其在离散网格上的计算方法; 其次, 总结与分析了这几种形状描述符在非刚性三维形状匹配中的表现和特性.第3节给出谱距离的定义和形式化表达, 同时给出不同谱距离在三角网格上的离散计算方法以及谱距离分布函数的计算方式.第4节是实验验证部分, 实验中使用不同谱形状描述符和谱距离分布函数进行非刚性三维形状匹配, 观察不同谱形状描述符参数变化对匹配效果的影响, 同时验证了第2节提出的预测的有效性, 并做出合理分析.

现有的形状描述符研究工作

表 1(Table 1)

Table 1 Several studies about summary and analysis of spectral analysis

表 1 谱分析的主要文章综述与分析

年份

第一作者

期刊/会议

题目

简介

2011

Bronstein MM

IEEE Trans. on Pattern Analysis & Machine Intelligence

Shape recognition with spectral distances[

介绍了应用谱距离分布进行非刚性形状识别的方法, 实验比较了HDD以及CD距离分布用于形状识别的性能

2011

Bronstein AM

Computer Science

Spectral descriptors for deformable shapes[

对比了HKS和WKS用于三维形状检索的性能, 并优化了HKS和WKS的参数, 在SREC’10上验证了其参数的优越性

2013

Cao W G

Computer Aided Drafting, Design and Manufacturing

Spectral distance distributions for non-rigid objects[

介绍了应用CD、HDD、BD三种谱形状描述符用于三维非刚性形状分类的方法, 并进行实验比较

2013

R Litman

IEEE Trans. on Pattern Analysis & Machine Intelligence

Learning spectral descriptors for deformable shape correspondence[

基于HKS和WKS构造了一种基于学习的谱形状描述符, 用于形状对应

2014

Patané G.

Pattern Recognition Letters

Laplacian spectral distances and kernels on 3D shapes ☆[

给出谱形状描述符和谱距离形式化表示以及离散化计算方法

2014

Li, Chunyuan,

Multimedia Systems

Spatially aggregating spectral descriptors for non-rigid 3D shape retrieval: A comparative survey[

应用HKS, SIHKS, HMS和WKS进行非刚性三维模型检索

2016

Biasotti S

Computer Graphics Forum

Recent trends, applications, and perspectives in 3D shape similarity assessment[

详细介绍了HKS、SIHKS用于三维形状相似度计算的过程

2016

Patané G.

Computer Graphics Forum

Accurate and Efficient Computation of Laplacian Spectral Distances and Kernels[

详细介绍了的计算过程和性能分析, 分析了谱形状描述符和谱距离的理论意义

2017

Patané G.

ACM SIGGRAPH

An introduction to laplacian spectral distances and kernels: Theory, computation, and applications[

详细介绍了谱形状描述符和谱距离的理论基础、计算过程和应用场景, 从鲁棒性、逼近精度和计算成本等方面讨论了国内外关于谱分析的研究工作

2018

李海生

软件学报

非刚性三维模型检索特征提取技术研究[

对于非刚性三维模型检索特征提取技术进行了详细的研究, 其在广泛调研大量文献和最新成果的基础上对shapeDNA, GPS, HKS, WKS用于三维非刚性形状检索进行了介绍

Table 1 Several studies about summary and analysis of spectral analysis

表 1 谱分析的主要文章综述与分析

(1)     提供应用基于谱分析的形状描述符进行三维非刚性形状匹配的框架, 并给出该方法的原理分析和数值计算;

(2)     系统地对比不同形状描述符的数学定义及算法特性; 从计算精度、鲁棒性、时间复杂度等多方面比较其各自优缺点; 并且在非刚性三维形状标准库中进行了两类描述符的实验比较;

(3)     给出不同谱形状描述符和谱距离分布函数的最优使用场景, 讨论了谱分析应用于非刚性三维形状匹配中存在的问题以及未来的发展趋势, 对谱分析进行推广, 为研究者选择基于谱分析的形状描述符提供参考.

1 基于谱分析的非刚性三维形状匹配框架

本文首先对基于谱分析的非刚性三维形状匹配的框架进行介绍.在数学中, 谱分析是一个广义的方法, 它将一个矩阵的特征向量和特征值理论扩展到一个含有更广泛运算符结构的谱空间中.在形状匹配中, 谱分析是指将形状上的LB算子离散化表示为LB矩阵, 对LB矩阵进行谱分解得到LB算子的特征向量和特征值.利用LB算子的特征值和特征向量, 可以定义出不同的谱形状描述符及其诱导出的不同的谱距离.通过计算一对形状上的谱形状描述符离散值或谱距离分布函数值, 研究者可以对比一对形状的局部或整体对应关系, 得到一对形状的非刚性匹配结果.本节首先给出非刚性匹配谱分析的一般框架, 其次给出LB算子的定义及离散化计算及谱分解形式.

1.1 非刚性匹配谱分析框架

LB算子的特征值与特征向量常常被用来描述模型的形状特性.利用谱形状描述符和谱距离可以很好地进行非刚性形状匹配, 本文给出基于谱分