留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

非刚性部分模型与完整模型的对应关系计算

杨军 王博

杨军, 王博. 非刚性部分模型与完整模型的对应关系计算[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
引用本文: 杨军, 王博. 非刚性部分模型与完整模型的对应关系计算[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
YANG Jun, WANG Bo. Non-rigid Shape Correspondence Between Partial Shape and Full Shape[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
Citation: YANG Jun, WANG Bo. Non-rigid Shape Correspondence Between Partial Shape and Full Shape[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055

非刚性部分模型与完整模型的对应关系计算

doi: 10.13203/j.whugis20190055
基金项目: 

国家自然科学基金 61862039

甘肃省科技计划 20JR5RA429

详细信息
    作者简介:

    杨军,博士,教授,博士生导师,主要从事计算机图形学、数字图像处理和地理信息系统等方面的研究。yangj@mail.lzjtu.cn

  • 中图分类号: P208

Non-rigid Shape Correspondence Between Partial Shape and Full Shape

Funds: 

The National Natural Science Foundation of China 61862039

the Science and Technology Program of Gansu Province 20JR5RA429

More Information
    Author Bio:

    YANG Jun, PhD, professor, specializes in computer graphics, image processing and geographic information system. E-mail: yangj@mail.lzjtu.cn

  • 摘要: 针对不同姿态下的三维等距部分模型与完整模型对应关系计算问题,提出了一种结合局部函数映射和局部流形谐波(localized manifold harmonics,LMH)算子计算三维模型特征描述符并构建模型间对应关系的新方法。首先,通过改进的Laplace算子的谱分解构造局部基产生LMH算子,并计算模型的特征描述符;其次,通过局部函数映射理论构建部分模型与完整模型间的初始对应关系;然后,交替迭代计算部分模型与完整模型间的稠密对应关系;最后,利用贪心算法优化对应关系直至收敛。实验结果表明,以局部流形谐波产生的新算子与局部函数映射方法计算得到的稀疏对应关系为基础,能构建更为准确的稠密对应关系,并在一定程度上减少等距误差。和已有算法相比,采用LMH算子构建的特征描述符比由Laplace-Beltrami算子构建的特征描述符更能体现出部分模型的本征属性,计算出的对应关系也更加准确。
  • 图  1  Laplace–Beltrami算子在三角网格上的离散化

    Figure  1.  Discretization of the Laplace-Beltrami Operator on a Triangular Mesh

    图  2  部分模型与完整模型

    Figure  2.  Partial Shape and Full Shape

    图  3  完整狼模型与带孔洞狼模型的对应关系比较

    Figure  3.  Comparison of the Constructed Correspondence Between the Full and the Holed Wolf Shapes

    图  4  完整狼模型和部分狼模型的对应关系比较

    Figure  4.  Comparison of the Constructed Correspondence Between the Full and the Partial Wolf Shapes

    图  5  完整狗模型与带孔洞狗模型的对应关系比较

    Figure  5.  Comparison of the Constructed Correspondence Between the Full and the Holed Dog Shapes

    图  6  完整狗模型与部分狗模型的对应关系比较

    Figure  6.  Comparison of the Constructed Correspondence Between the Full and the Partial Dog Shapes

    图  7  完整马模型与带孔洞马模型的对应关系比较

    Figure  7.  Comparison of the Constructed Correspondence Between the Full and the Holed Horse Shapes

    图  8  完整马模型与部分马模型的对应关系比较

    Figure  8.  Comparison of the Constructed Correspondence Between the Full and the Partial Horse Shapes

    图  9  完整人体模型与带孔洞人体模型的对应关系比较

    Figure  9.  Comparison of the Constructed Correspondence Between the Full and the Holed Man Shapes

    图  10  完整人体模型与部分人体模型的对应关系比较

    Figure  10.  Comparison of the Constructed Correspondence Between the Full and the Partial Man Shapes

    表  1  两种算法的部分模型与完整模型间等距误差的比较

    Table  1.   Comparison of the Isometric Errors for Calculating the Shape Correspondences Between Partial Shape and Full Shape of Two Algorithms

    模型 等距误差
    文献[18]算法 本文算法
    带孔洞狼模型 0.098 724 0.087 807
    部分狼模型 0.137 226 0.116 253
    带孔洞狗模型 0.042 952 0.034 749
    部分狗模型 0.033 408 0.032 362
    带孔洞马模型 0.087 351 0.085 248
    部分马模型 0.087 298 0.069 958
    带孔洞人体模型 0.061 264 0.048 689
    部分人体模型 0.057 785 0.041 543
    下载: 导出CSV
  • [1] VanKaick O, Zhang H, Hamarneh G, et al. A Survey on Shape Correspondence[J]. Computer Graphics Forum, 2011, 30(6): 1 681-1 707 doi:  10.1111/j.1467-8659.2011.01884.x
    [2] Golovinskiy A, Funkhouser T. Consistent Segmentation of 3D Models[J]. Computers and Graphics, 2009, 33(3): 262-269 doi:  10.1016/j.cag.2009.03.010
    [3] Kilian M, Mitra N J, Pottmann H. Geometric Modeling in Shape Space[J]. ACM Transactions on Graphics, 2007, 26(3), DOI:  10.1145/1276377.1276457
    [4] Schreiner J, Asirvatham A, Praun E, et al. Inter-Surface Mapping[J]. ACM Transactions on Graphics, 2004, 23(3): 870-877 doi:  10.1145/1015706.1015812
    [5] Jain V, Zhang H. A Spectral Approach to Shape-Based Retrieval of Articulated 3D Models[J]. Computer-Aided Design, 2007, 39(5): 398-407 doi:  10.1016/j.cad.2007.02.009
    [6] Raviv D, Bronstein A M, Bronstein M M, et al. Equi-Affine Invariant Geometry for Shape Analysis[J]. Journal of Mathematical Imaging and Vision, 2014, 50(1/2): 144-163
    [7] Sahillioglu Y, Yemez Y. Multiple Shape Correspondence by Dynamic Programming[J]. Computer Graphics Forum, 2015, 33(7): 121-130
    [8] Lipman Y, Funkhouser T. Mobius Voting for Surface Correspondence[J]. ACM Transactions on Graphics, 2009, 28(3), DOI:  10.1145/1576246.1531378
    [9] Aigerman N, Poranne R, Lipman Y. Seamless Surface Mappings[J]. ACM Transactions on Graphics, 2015, 34(4), DOI:  10.1145/2766921
    [10] Aigerman N, Lipman Y. Hyperbolic Orbifold Tutte Embeddings[J]. ACM Transaction on Graphics, 2016, 35(6), DOI:  10.1145/1576246.153137
    [11] Ovsjanikov M, Ben-Chen M, Solomon J, et al. Functional Maps: A Flexible Representation of Maps Between Shapes[J]. ACM Transactions on Graphics, 2012, 31(4), DOI:  10.1145/1576246.1531378
    [12] Sun J, Ovsjanikov M, Guibas L. A Concise and Provably Informative Multi-scale Signature Based on Heat Diffusion[J]. Computer Graphics Forum, 2009, 28(5): 1 383-1 392 doi:  10.1111/j.1467-8659.2009.01515.x
    [13] Aubry M, Schlickewei U, Cremers D. The Wave Kernel Signature: A Quantum Mechanical Approach to Shape Analysis[C]. 2011 IEEE International Conference on Computer Vision Workshops, Barcelona, Spain, 2011
    [14] 杨军, 闫寒, 王茂正. 融合特征描述符约束的3维等距模型对应关系计算[J]. 中国图象图形学报, 2016, 21(5): 628-635 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB201605010.htm

    Yang Jun, Yan Han, Wang Maozheng. Calculation of Correspondences Between Three-Dimensional Isometric Shapes with the Use of a Fused Feature Descriptor[J]. Journal of Image and Graphics, 2016, 21(5): 628-635 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB201605010.htm
    [15] Melzi S, Rodolà E, Castellani U, et al. Localized Manifold Harmonics for Spectral Shape Analysis[J]. Computer Graphics Forum, 2018, 37(6): 20-34 doi:  10.1111/cgf.13309
    [16] Kim V, Lipman Y, Funkhouser T. Blended Intrinsic Maps[J]. ACM Transactions on Graphics, 2011, 30(4), DOI:  10.1145/2010324.1964974
    [17] 杨军, 闫寒. 校准三维模型基矩阵的函数映射的对应关系计算[J]. 武汉大学学报·信息科学版, 2018, 43(10): 1 518-1 525 doi:  10.13203/j.whugis20160493

    Yang Jun, Yan Han. An Algorithm for Calculating Shape Correspondences Using Functional Maps by Calibrating Base Matrix of 3D Shapes[J]. Geomatics and Information Science of Wuhan University, 2018, 43(10): 1 518-1 525 doi:  10.13203/j.whugis20160493
    [18] Rodolà E, Cosmo L, Bronstein M M, et al. Partial Functional Correspondence[J]. Computer Graphics Forum, 2017, 36(1): 222-236 doi:  10.1111/cgf.12797
    [19] Litany O, Bronstein A M, Bronstein M M, et al. Non-rigid Puzzles[C]. Symposium on Geometry Processing, Eurographics Association, Berlin, Germany, 2016
    [20] Litany O, Rodolà E, Bronstein A M, et al. Fully Spectral Partial Shape Matching[J]. Computer Graphics Forum, 2017, 36(2): 247-258 doi:  10.1111/cgf.13123
  • [1] 霍亮, 段元晶, 朱翊, 沈涛, 张孝勇, 翟佳磊, 符季颖.  顾及局部特征的城市三维模型多尺度表达方法 . 武汉大学学报 ● 信息科学版, 2020, 45(8): 1282-1287. doi: 10.13203/j.whugis20200148
    [2] 徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕.  利用等距同构建立多尺度空间实体相似性度量模型 . 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
    [3] 杨军, 闫寒.  校准三维模型基矩阵的函数映射的对应关系计算 . 武汉大学学报 ● 信息科学版, 2018, 43(10): 1518-1525. doi: 10.13203/j.whugis20160493
    [4] 李媛, 胡翰, 谢金华, 朱庆, 张叶廷, 杜志强, 彭明军, 高山.  局部区域表面一致性约束的三维模型纹理映射方法 . 武汉大学学报 ● 信息科学版, 2016, 41(12): 1599-1604. doi: 10.13203/j.whugis20140537
    [5] 李祎, 芦碧波, 王永茂.  分区非局部均值色貌模型在色调映射中的应用 . 武汉大学学报 ● 信息科学版, 2016, 41(5): 649-655. doi: 10.13203/j.whugis20140024
    [6] 周维勋, 邵振峰, 侯继虎.  利用视觉注意模型和局部特征的遥感影像检索方法 . 武汉大学学报 ● 信息科学版, 2015, 40(1): 46-52.
    [7] 刘光明, 孟祥伟.  一种新的SAR图像局部统计活动轮廓模型及算法 . 武汉大学学报 ● 信息科学版, 2015, 40(5): 628-631. doi: 10.13203/j.whugis20130445
    [8] 孙伟伟, 刘春, 施蓓琦, 李巍岳.  等距映射降维用于高光谱影像低维流形特征提取 . 武汉大学学报 ● 信息科学版, 2013, 38(6): 642-647.
    [9] 何楚, 张宇, 廖紫纤, 廖明生.  基于分层自适应部分模型的遥感图像飞机目标检测 . 武汉大学学报 ● 信息科学版, 2013, 38(6): 656-660.
    [10] 臧天宁, 云晓春, 张永铮, 门朝光.  僵尸网络关系云模型分析算法 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 247-251.
    [11] 柯福阳, 王庆, 潘树国.  基于映射函数网络RTK的大气误差内插估计模型 . 武汉大学学报 ● 信息科学版, 2012, 37(1): 73-76.
    [12] 廖海斌, 陈庆虎, 王宏勇.  融合局部形变模型的鲁棒性人脸识别 . 武汉大学学报 ● 信息科学版, 2011, 36(7): 877-881.
    [13] 杨红娟, 丛振涛, 雷志栋.  谐波法与双源模型耦合估算土壤热通量和地表蒸散发 . 武汉大学学报 ● 信息科学版, 2009, 34(6): 706-710.
    [14] 林淼, 朱建军, 杨经豪, 邱斌.  地球重力位模型确定局部大地水准面起伏的比较研究 . 武汉大学学报 ● 信息科学版, 2009, 34(10): 1194-1198.
    [15] 王志刚, 边少锋.  基于局部地球重力场模型的水下目标被动定位 . 武汉大学学报 ● 信息科学版, 2008, 33(9): 918-921.
    [16] 郭庆胜, 郑春燕.  锥形空间方向关系模型的改进 . 武汉大学学报 ● 信息科学版, 2007, 32(1): 81-84.
    [17] 宋迎春, 朱建军, 陈正阳, 曾联斌.  部分参数有非负约束平差模型的一种新算法 . 武汉大学学报 ● 信息科学版, 2007, 32(10): 883-887.
    [18] 申文斌, 鄢建国, 晁定波.  重力场的局部虚拟向下延拓以及利用EGM96模型的模拟实验检验 . 武汉大学学报 ● 信息科学版, 2006, 31(7): 589-593.
    [19] 龙毅, 毋河海, 周侗, 汤国安.  地图目标局部分形描述的元分维模型的实现 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 891-895.
    [20] 田晋, 暴景阳, 刘雁春.  全球位系数模型构建高精度局部重力场的Clenshaw求和 . 武汉大学学报 ● 信息科学版, 2005, 30(10): 905-908.
  • 加载中
图(10) / 表(1)
计量
  • 文章访问数:  14
  • HTML全文浏览量:  2
  • PDF下载量:  6
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-28
  • 刊出日期:  2021-03-05

非刚性部分模型与完整模型的对应关系计算

doi: 10.13203/j.whugis20190055
    基金项目:

    国家自然科学基金 61862039

    甘肃省科技计划 20JR5RA429

    作者简介:

    杨军,博士,教授,博士生导师,主要从事计算机图形学、数字图像处理和地理信息系统等方面的研究。yangj@mail.lzjtu.cn

  • 中图分类号: P208

摘要: 针对不同姿态下的三维等距部分模型与完整模型对应关系计算问题,提出了一种结合局部函数映射和局部流形谐波(localized manifold harmonics,LMH)算子计算三维模型特征描述符并构建模型间对应关系的新方法。首先,通过改进的Laplace算子的谱分解构造局部基产生LMH算子,并计算模型的特征描述符;其次,通过局部函数映射理论构建部分模型与完整模型间的初始对应关系;然后,交替迭代计算部分模型与完整模型间的稠密对应关系;最后,利用贪心算法优化对应关系直至收敛。实验结果表明,以局部流形谐波产生的新算子与局部函数映射方法计算得到的稀疏对应关系为基础,能构建更为准确的稠密对应关系,并在一定程度上减少等距误差。和已有算法相比,采用LMH算子构建的特征描述符比由Laplace-Beltrami算子构建的特征描述符更能体现出部分模型的本征属性,计算出的对应关系也更加准确。

English Abstract

杨军, 王博. 非刚性部分模型与完整模型的对应关系计算[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
引用本文: 杨军, 王博. 非刚性部分模型与完整模型的对应关系计算[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
YANG Jun, WANG Bo. Non-rigid Shape Correspondence Between Partial Shape and Full Shape[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
Citation: YANG Jun, WANG Bo. Non-rigid Shape Correspondence Between Partial Shape and Full Shape[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 434-441. doi: 10.13203/j.whugis20190055
  • 在两个或多个模型间或相邻视频帧间建立有意义的对应关系是一项非常重要的基础性研究工作[1]。其主要目的是计算给定模型间(如完整模型与完整模型、部分模型与完整模型)有意义的匹配关系。对应关系在计算机图形学和计算机视觉等领域应用广泛,如模型分割[2]、模型变形和插值[3]、网格参数化[4]、模型分析检索[5]、统计模型分析[6]等。

    本文旨在构建部分模型与完整模型间的对应关系。由于3D传感器在实际数据采集的过程中不可避免地会因遮挡或部分视图丢失导致获取的三维模型缺少某些部件或存在孔洞,研究部分模型和完整模型间的对应关系就显得尤为重要。现有的方法大多是建立点到点的对应关系,文献[7]将计算三维模型间对应关系的问题转化为计算三维网格模型上最优路径的问题。但由于模型上的点对之间的关系在映射到函数空间时为指数形式,导致对应关系的优化过程变得非常困难。为了解决该问题,文献[8-10]在模型表面定义特征标记,并根据标记对模型进行分析,此方法更适合直接优化。文献[11]提出采用函数映射理论计算模型间对应关系,通过构建线性函数计算源模型与目标模型的函数映射矩阵,进而将两个模型各自对应的特征向量与函数映射矩阵联系起来。该算法的实质是将模型间对应关系的计算问题转化为模型间函数映射矩阵的计算问题。然而,Laplace算子本身是一个局部微分算子,其特征函数和特征值描述的是整个流形的几何和拓扑信息。此外,单一地使用Laplace算子计算的特征值和特征向量容易导致由于特征信息提取不准确而无法得到较为理想的对应关系。首先,本文引入局部流形谐波(localized manifold harmonics,LMH)算子,根据该算子计算模型的特征描述符,利用特征描述符计算出特征值与特征向量;然后,通过特征值和特征向量构建对应关系矩阵,使用交替迭代的方法构建部分模型和完整模型间的对应关系。

    • 由于对应关系的应用非常广泛,三维模型间对应关系的研究已成为国内外研究的热点。在源模型与目标模型的对应关系的计算过程中,首要任务是计算模型的特征描述符。Sun等[12]提出了具有多尺度特性的热核签名描述符(heat kernel signatures,HKS),能够有效区分模型的特征,利用特征相似性来建立对应关系。但HKS对模型尺度的变化比较敏感,且不能有效地区分模型间局部特征相似的采样点。Aubry等[13]提出了波核签名(wave kernel signatures,WKS)的概念,利用粒子能量的概率分布来测量不同模型上的分布点。但WKS在同一时刻不同频率的条件下,得到的分布点是有明显差异的。杨军等[14]提出了一种基于HKS与WKS的融合特征描述符。与单一使用HKS或WKS特征描述符相比,该算法得到了更加准确的对应关系。但是,针对存在缺失部件或带孔洞的模型,该算法不能构建出准确的对应关系。此外,Melzi等[15]改进了传统的Laplace-Beltrami算子,得出LMH算子用于分析模型的局部信息,但该算法需要手动设置谐波参数,计算模型间的对应关系时自适应性弱。

      在获得模型的描述符后,就可以计算模型间的对应关系,函数映射理论是近年来提出的一种新方法。Kim等[16]提出了一种混合映射的方法:首先,在源模型和目标模型上分别采样获取特征点,计算出各自点集中每一个采样点的置信度,同时建立植入映射候选集并赋予权重;然后,将每一个置信度值与映射中每一个对应关系的权重相关联。该方法在一定程度上解决了模型因对称性影响对应关系计算的问题,但计算过程相对繁杂。Ovsjanikov等[11]提出了函数映射理论,在两个模型间计算对应关系矩阵,由此构建出两个模型间的对应关系。该方法将复杂的模型对应关系计算问题转化为对应关系矩阵的计算,但该方法只适用于完整模型间的对应关系计算,对部分模型和完整模型间的对应关系计算准确率不高。杨军等[17]提出了一种通过校准三维几何模型间基矩阵来计算模型间对应关系的新方法,将模型间对应关系的构建转化为由模型特征函数所构建的基矩阵之间的校准运算。该方法在完整模型间的对应关系计算中效果较好,但是如果用于部分模型与完整模型间对应关系的计算,则需要进一步扩展该方法才能实现。Rodolà等[18]提出局部函数映射方法计算部分模型与完整模型的对应关系,通过加权的方式改进函数映射,计算出部分模型与完整模型的最大匹配区域。但此方法由于使用了能量函数,导致计算过程中存在多重最优解问题;此外,该方法并没有解决拓扑信息变化和类间相似性影响对应关系计算的问题。Litany等[19]结合了模型分割算法与部分模型间的稠密对应关系的计算,提出了一种非刚性部分模型集合与完整模型的匹配算法。然而,该方法要求模型近似等距,当数据产生噪声或者由于扫描获得数据错误时,需要一个更好的描述符来进行对应关系计算。Litany等[20]提出局部函数映射与匹配非等距模型的Laplace-Beltrami算子的联合近似对角化(joint approximate diagonalization,JAD)方法计算部分模型与完整模型间的对应关系。但该方法会由于模型自身对称性而导致错误匹配问题。

      本文在文献[18]的基础上提出了一种结合LMH算子与局部函数映射方法计算部分模型与完整模型间对应关系计算的新方法。该方法在初始匹配阶段利用LMH算子计算出特征描述符的特征值与特征向量,可更准确地描述模型的局部特征信息;在计算等距误差时,利用贪心算法优化局部信息,减少对应关系的等距误差,提高了部分模型与完整模型间对应关系的准确率。

    • 三维模型是由嵌入到$ {\bf{R}}^{3} $中的二维黎曼流形(光滑表面)X表示的,二维流形在离散集合中是由大量的三角形网格拼接而成的。在流形X的局部点x的周围,流形与其对应的切空间或者平面TXX是同胚的。其中,切空间中所有不相交部分的并集被称为切丛TX。切空间中的内积可由流形上的黎曼度量表示,即$ {〈\cdot , \cdot 〉}_{{T}_{X}X}:{T}_{X}X\times {T}_{X}X\to \bf{R} $,同时,该内积具有内蕴性。

      在二维流形X上定义一个包含边界$ \partial X $的模型,其Laplace-Beltrami算子可以特征分解[19]为:

      $$ {\Delta }_{X}{\mathit{\boldsymbol{\boldsymbol{\phi }}}}_{i}\left(x\right)={\lambda }_{i}{\mathit{\boldsymbol{\phi }}}_{i}\left(x\right), x\in \mathrm{i}\mathrm{n}\mathrm{t}\left(X\right) $$ (1)

      Neumann边界条件为:

      $$ 〈{\nabla }_{X}{\mathit{\boldsymbol{\phi }}}_{i}\left(x\right), \widehat{\mathit{\boldsymbol{n}}}\left(x\right)〉=0, x\in \partial X $$ (2)

      式(1)、式(2)中,$ {\Delta }_{X} $为流形X上的Laplace-Beltrami算子;$ {\nabla }_{X} $为流形X上的梯度算子;$ \widehat{\mathit{\boldsymbol{n}}}\left(x\right) $为边界的法向量;$ 0={\lambda }_{1}\le {\lambda }_{2}\le \cdots $为特征值;$ {\mathit{\boldsymbol{\phi }}}_{1}, {\mathit{\boldsymbol{\phi }}}_{2}\cdots {\mathit{\boldsymbol{\phi }}}_{n} $表示满足$ {〈\mathit{\boldsymbol{\phi }}{}_{i}, {\mathit{\boldsymbol{\phi }}}_{j}〉}_{X}={\delta }_{ij} $条件对应的特征函数;$ {\delta }_{ij} $为对应特征函数间的内积。

      对于流形X,Laplace特征函数形成的正交基被称为流形谐波(manifold harmonics,MH)。分别定义流形QP,Ovsjanikov等[11]提出将函数映射理论引入对应关系的计算中,即通过寻找源模型与目标模型间的线性映射关系$ T:P\to Q $计算最终的对应关系矩阵。定义模型Q的描述符函数$ f\to Q $,存在线性映射关系:

      $$ \begin{array}{c}T(f)=T{\mathop \sum \limits _{i\ge 1}〈f, {\mathit{\boldsymbol{\phi }}}_{i}〉}_{P}{\mathit{\boldsymbol{\phi }}}_{i}={\mathop \sum \limits _{i\ge 1}〈f, {\mathit{\boldsymbol{\phi }}}_{i}〉}_{P}T{\mathit{\boldsymbol{\phi }}}_{i}=\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }{\mathop \sum \limits _{i, j\ge 1}〈f, {\mathit{\boldsymbol{\phi }}}_{i}〉}_{P}\underset{{c}_{ij}}{\underset{⏟}{{〈T{\mathit{\boldsymbol{\phi }}}_{i}, {\mathit{\boldsymbol{\psi }}}_{j}〉}_{Q}}}{\mathit{\boldsymbol{\psi }}}_{j}\end{array} $$ (3)

      式中,$ {\left\{{\mathit{\boldsymbol{\phi }}}_{i}\right\}}_{i\ge 1} $与$ {\left\{{\mathit{\boldsymbol{\psi }}}_{j}\right\}}_{j\ge 1} $分别表示流形PQ中的特征函数。对应关系的构建实质上是计算出对应关系矩阵C中的各个元素cij

      文献[18]利用Laplace算子计算部分模型与完整模型间的对应关系。尽管Laplace算子是一个局部微分算子,但是其对应的特征函数和特征值描述的却是整个流形的信息,不能准确地描述部分模型所对应的部分流形信息。若将使用Laplace算子计算出的特征函数与特征值代入到后续的对应关系计算中,会导致实验结果中对应关系的准确率下降。因此,本文提出一种新的算子替代Laplace算子进行计算。

      定义整数k和流形X上的一块区域R$ \left(R\subseteq X\right) $,结合特征函数集合$ \left\{{\mathit{\boldsymbol{\phi }}}_{1}, {\mathit{\boldsymbol{\phi }}}_{2}\cdots {\mathit{\boldsymbol{\phi }}}_{k\mathrm{\text{'}}}\right\} $(由前k'个Laplace特征函数构成),计算出一个位于R上的平滑、正交的特征函数集合$ \left\{{\mathit{\boldsymbol{\psi }}}_{1}, {\mathit{\boldsymbol{\psi }}}_{2}\cdots {\mathit{\boldsymbol{\psi }}}_{k}\right\} $。该过程可以被看作最优化求解问题[15]

      $$ \underset{{\mathit{\boldsymbol{\psi }}}_{1}, {\mathit{\boldsymbol{\psi }}}_{2}\cdots {\mathit{\boldsymbol{\psi }}}_{k}}{\mathrm{m}\mathrm{i}\mathrm{n}}\mathop \sum \limits _{j=1}^{k}\varepsilon _{{}_{S}}\left({\mathit{\boldsymbol{\psi }}}_{j}\right)+{\mu }_{{}_{R}}\varepsilon _{{}_{R}}\left({\mathit{\boldsymbol{\psi }}}_{j}\right) $$ (4)

      式中,$ {\mu }_{{}_{R}} $表示权重,其值为给定区域R的面积与整个流形X面积的比值;$ \varepsilon _{{}_{S}}\left({\mathit{\boldsymbol{\psi }}}_{j}\right) $表示狄利克雷能量函数,用于提高新基的平滑性;$ \varepsilon _{{}_{R}}\left({\mathit{\boldsymbol{\psi }}}_{j}\right) $表示给定区域$ R\subseteq X $中的二次惩罚函数,用于计算R区域的局部化结果,可定义为:

      $$ \varepsilon _{{}_{\mathit{\boldsymbol{R}}}}\left(\mathit{\boldsymbol{\psi }}\right):={\int }_{X}\left(\mathit{\boldsymbol{\psi }}\right(x\left)\right(1-u{\left(x\right)\left)\right)}^{2}\mathrm{d}x $$ (5)

      式中,$ u\in \left[\mathrm{0, 1}\right] $表示隶属函数:当$ x\in R $时,u(x)=1;当$ x\notin R $时,u(x)=0。

      式(4)在同时满足以下两个约束条件时有解,称该解为LMH[15]

      $$ {〈{\mathit{\boldsymbol{\psi }}}_{i}, {\mathit{\boldsymbol{\psi }}}_{j}〉}_{X}={\delta }_{ij}, i\mathrm{、}j=\mathrm{1, 2}\cdots k $$ (6)
      $$ {〈{\mathit{\boldsymbol{\psi }}}_{i}, {\mathit{\boldsymbol{\phi }}}_{j}〉}_{X}=0\mathrm{ }, i=\mathrm{1, 2}\cdots k, j=\mathrm{1, 2}\cdots k\mathrm{\text{'}} $$ (7)

      式(6)为用流形X上的正交特征基函数$ {\mathit{\boldsymbol{\psi }}}_{1}, {\mathit{\boldsymbol{\psi }}}_{2}\cdots {\mathit{\boldsymbol{\psi }}}_{k} $的内积构造了新的函数$ {\delta }_{ij} $作为最优化的约束条件;式(7)表示所求基函数$ {\mathit{\boldsymbol{\psi }}}_{1}, {\mathit{\boldsymbol{\psi }}}_{2}\cdots {\mathit{\boldsymbol{\psi }}}_{k} $必须正交于给定集合$ \left\{{\mathit{\boldsymbol{\phi }}}_{1}, {\mathit{\boldsymbol{\phi }}}_{2}\cdots {\mathit{\boldsymbol{\phi }}}_{k\mathrm{\text{'}}}\right\} $。

      由于在式(4)求解过程中约束条件过于严格,因此,本文简化了式(4)的约束条件,提出了一种新的求解过程:

      $$ \left\{\begin{array}{l}\underset{{\mathit{\boldsymbol{\psi }}}_{1}, {\mathit{\boldsymbol{\psi }}}_{2}\cdots {\mathit{\boldsymbol{\psi }}}_{k}}{\mathrm{m}\mathrm{i}\mathrm{n}}\mathop \sum \limits _{j=1}^{k}\epsilon \left({\mathit{\boldsymbol{\psi }}}_{j}\right)\\ \varepsilon \left({\mathit{\boldsymbol{\psi }}}_{j}\right)=\varepsilon _{{}_{S}}\left({\mathit{\boldsymbol{\psi }}}_{j}\right)+{\mu }_{{}_{\mathit{\boldsymbol{R}}}}\varepsilon _{{}_{\mathit{\boldsymbol{R}}}}\left({\mathit{\boldsymbol{\psi }}}_{j}\right)+{\mu }_{\perp }\varepsilon _{\perp }\left({\mathit{\boldsymbol{\psi }}}_{j}\right)\\ \varepsilon _{\perp }\left({\mathit{\boldsymbol{\psi }}}_{j}\right)={\mathop \sum \limits _{i=1}^{k\mathrm{\text{'}}}\left|{〈{\mathit{\boldsymbol{\phi }}}_{i}, {\mathit{\boldsymbol{\psi }}}_{j}〉}_{X}\right|}^{2}\end{array}\right. $$ (8)

      式中,$ {\mu }_{\perp } $表示权重。

      在对LMH算子进行特征分解时,需要对LMH算子离散化。在流形X中,取n个顶点$ {x}_{1}, {x}_{2}\cdots {x}_{n} $作为采样点,并根据这些点构造三角网格(VEF),其中,V=$ \left\{\mathrm{1, 2}\cdots n\right\} $表示网格的顶点,$ E={E}_{i}\bigcup {E}_{b} $表示网格的边。如图 1所示,绿色线条表示网格的内边界Ei,红色线条表示网格的外边界EbF表示网格的面。

      图  1  Laplace–Beltrami算子在三角网格上的离散化

      Figure 1.  Discretization of the Laplace-Beltrami Operator on a Triangular Mesh

      LMH算子的离散化采用n×n的稀疏矩阵L=-A-1W表示。其中,矩阵A为由面积元素$ {a}_{i}=\frac{1}{3}\mathop \sum \limits _{jk:ijk\in F}{A}_{ijk} $构成的对角矩阵,其中,Aijk表示△ijk的面积,矩阵W包含的元素满足[18]

      $$ {w}_{ij}=\left\{\begin{array}{l}\left(\mathrm{c}\mathrm{o}\mathrm{t}{\alpha }_{ij}+\mathrm{c}\mathrm{o}\mathrm{t}{\beta }_{ij}\right)/2\mathrm{ }, ij\in {E}_{i}\\ \left(\mathrm{c}\mathrm{o}\mathrm{t}{\alpha }_{ij}\right)/2\mathrm{ }, ij\in {E}_{b}\\ -\mathop \sum \limits _{k\ne i}{w}_{ik}, i=j\\ 0\mathrm{ }\mathrm{ }, \mathrm{其}\mathrm{他}\end{array}\right. $$ (9)

      图 1(a)所示,$ {\alpha }_{ij}\mathrm{、}{\beta }_{ij} $分别表示△ijk公共边ij所对应的角$ \mathrm{\angle }ikj\mathrm{、}\mathrm{\angle }jhi $。

      对式(8)得出的LMH算子进行离散化,将求得的特征向量$ {\mathit{\boldsymbol{\psi }}}_{1}, {\mathit{\boldsymbol{\psi }}}_{2}...{\mathit{\boldsymbol{\psi }}}_{k} $(LMH)作为列向量构造矩阵$ \mathit{\boldsymbol{\Psi }}\in {\bf{R}}^{n\times k} $。将LMH算子计算出的特征向量结合函数映射方法,T(f)可表示为:

      $$ \begin{array}{c}T\left(f\right)=T{\mathop \sum \limits _{i, j=1}^{k+k\mathrm{\text{'}}}〈f, {\mathit{\boldsymbol{\omega }}}_{{l}_{i}}〉}_{P}{\mathit{\boldsymbol{\omega }}}_{{l}_{i}}={\mathop \sum \limits _{i, j=1}^{k+k\mathrm{\text{'}}}〈f, {\mathit{\boldsymbol{\omega }}}_{{l}_{i}}〉}_{P}T{\mathit{\boldsymbol{\omega }}}_{{l}_{j}}=\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }{\mathop \sum \limits _{i, j=1}^{k+k\mathrm{\text{'}}}〈f, {\mathit{\boldsymbol{\omega }}}_{{l}_{i}}〉}_{P}\underset{{c}_{ij}}{\underset{⏟}{{〈T{\mathit{\boldsymbol{\omega }}}_{{l}_{i}}, {\mathit{\boldsymbol{\omega }}}_{{m}_{j}}〉}_{Q}}}{\mathit{\boldsymbol{\omega }}}_{{m}_{j}}\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\left(10\right)\end{array} $$ (10)

      式中,$ {\mathit{\boldsymbol{\omega }}}_{l} $与$ {\mathit{\boldsymbol{\omega }}}_{m} $分别表示流形PQ中的特征向量,且$ \mathit{\boldsymbol{\omega }}\in \mathit{\boldsymbol{\Omega }} $,$ \mathit{\boldsymbol{\Omega }}={\left\{{\mathit{\boldsymbol{\Phi }}}_{i}\right\}}_{i=1}^{k\mathrm{\text{'}}}\bigcup {\left\{{\mathit{\boldsymbol{\Psi }}}_{j}\right\}}_{j=1}^{k} $为标准和局部流形谐波的联合表示,矩阵$ \mathit{\boldsymbol{\Phi }}\in {\bf{R}}^{n\times {k}^{\mathrm{\text{'}}}} $由前k'个Laplace特征向量$ {\mathit{\boldsymbol{\phi }}}_{1}, {\mathit{\boldsymbol{\phi }}}_{2}\cdots {\mathit{\boldsymbol{\phi }}}_{{k}^{\mathrm{\text{'}}}} $(标准流形谐波)构成。

    • 本文结合LMH算子和局部函数映射建立源模型与目标模型间的对应关系。

      给定一个完整模型M和一个部分模型N,其中部分模型N近似等距于形变后的部分$ M\mathrm{\text{'}}\subset M $。首先,通过隶属函数u确定部分模型N对应到完整模型M中的部分M'。当u(x)=1时,$ x\in M\mathrm{\text{'}} $,即模型N上的点对应到完整模型MM'上的点x;当u(x)=0时,$ x\in \stackrel{-}{M}=M/M\mathrm{\text{'}} $,表示模型N上的点对应在模型M上除去M'部分的其余区域$ \stackrel{-}{M} $中的点x。设模型MN分别包含mn个顶点,可知M'包含n个顶点,且$ \stackrel{-}{m}=m-n $。如图 2所示,图 2(a)表示部分模型N图 2(b)表示完整模型M,其中,红色部分表示M',蓝色部分表示$ \stackrel{-}{M} $。

      图  2  部分模型与完整模型

      Figure 2.  Partial Shape and Full Shape

      计算部分模型N与完整模型M的LMH算子,获取相应的特征向量$ {\mathit{\boldsymbol{\omega }}}_{l} $与$ {\mathit{\boldsymbol{\omega }}}_{m} $,根据特征向量分别构建部分模型N与完整模型M的基矩阵HBB(u)=$ \left\{{b}_{ij}\left(x\right)\right\} $是由u(x)构成的矩阵,其中,$ {b}_{ij}\left(x\right) $为:

      $$ {b}_{ij}\left(x\right)={\int }_{M}u\left(x\right){\mathit{\boldsymbol{\omega }}}_{{l}_{i}}\left(x\right){\mathit{\boldsymbol{\omega }}}_{{m}_{j}}\left(x\right)\mathrm{d}x $$ (11)

      局部函数映射对应关系可表示为CH=B(u),C为对应关系矩阵。

      本文采用组合优化的方式计算对应关系矩阵C

      $$ \underset{\mathit{\boldsymbol{C}}, \mathit{\boldsymbol{v}}}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{\boldsymbol{C}}\mathit{\boldsymbol{H}}-\mathit{\boldsymbol{B}}\left(\eta \left(\mathit{\boldsymbol{v}}\right)\right)‖}_{\mathrm{2, 1}}+{\rho }_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left(\mathit{\boldsymbol{C}}\right)+{\rho }_{\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}\left(\mathit{\boldsymbol{v}}\right) $$ (12)

      式中,$ \mathrm{m}\mathrm{i}\mathrm{n}{‖\mathit{\boldsymbol{C}}\mathit{\boldsymbol{H}}-\mathit{\boldsymbol{B}}\left(\eta \left(\mathit{\boldsymbol{v}}\right)\right)‖}_{\mathrm{2, 1}} $表示使用L2,1矩阵范数来处理对应关系矩阵C中距离矩阵对角线较远的非零元素,使剩余元素更加集中;$ {\rho }_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left(\mathit{\boldsymbol{C}}\right) $与$ {\rho }_{\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}\left(\mathit{\boldsymbol{v}}\right) $分别表示对应关系计算过程中的约束函数和部分模型对应完整模型过程中的约束函数[18];函数$ \eta \left(\mathit{\boldsymbol{v}}\right) $表示为:

      $$ \eta \left(\mathit{\boldsymbol{v}}\right)=\frac{1}{2}\left(\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{h}\left(2\mathit{\boldsymbol{v}}-1\right)+1\right) $$ (13)

      式中,函数$ \eta \left(\mathit{\boldsymbol{v}}\right) $取值在[0, 1];v表示由部分模型N与完整模型M中的对应部分M'。

      部分模型对应完整模型过程中的约束函数[18]可以表示为:

      $$ {\rho }_{\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}\left(\mathit{\boldsymbol{v}}\right)={\mu }_{1}{\left({S}_{N}-{\int }_{M}\eta \left(\mathit{\boldsymbol{v}}\right)\mathrm{d}x\right)}^{2} $$ (14)

      式中,$ {\mu }_{1}{\left({S}_{N}-{\int }_{M}\eta \left(\mathit{\boldsymbol{v}}\right)\mathrm{d}x\right)}^{2} $用于计算给定部分模型N与完整模型M中的对应部分M'。

      对应关系计算过程中的约束函数[18]可以表示为:

      $$ \begin{array}{l}\mathrm{ }\mathrm{ }{\rho }_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left(\mathit{\boldsymbol{C}}\right)={\mu }_{2}{‖\mathit{\boldsymbol{C}}\circ \mathit{\boldsymbol{W}}‖}_{F}^{2}+{\mu }_{3}\mathop \sum \limits _{i\ne j}{\left({\mathit{\boldsymbol{C}}}^{\mathrm{T}}\mathit{\boldsymbol{C}}\right)}_{ij}^{2}+\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }{\mu }_{4}{\mathop \sum \limits _{i}\left({\left({\mathit{\boldsymbol{C}}}^{\mathrm{T}}\mathit{\boldsymbol{C}}\right)}_{ij}-{\mathit{\boldsymbol{d}}}_{i}\right)}^{2}\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\left(15\right)\end{array} $$ (15)

      式中,$ {\mu }_{2}{‖\mathit{\boldsymbol{C}}\circ \mathit{\boldsymbol{W}}‖}_{F}^{2} $中的“$ \circ $”为Hadamard积,表示两矩阵内对应元素的乘积;$ {\mu }_{3}\mathop \sum \limits _{i\ne j}{\left({\mathit{\boldsymbol{C}}}^{\mathrm{T}}\mathit{\boldsymbol{C}}\right)}_{ij}^{2} $与$ {\mu }_{4}{\mathop \sum \limits _{i}\left({\left({\mathit{\boldsymbol{C}}}^{\mathrm{T}}\mathit{\boldsymbol{C}}\right)}_{ii}-{\mathit{\boldsymbol{d}}}_{i}\right)}^{2} $通过$ {\mathit{\boldsymbol{C}}}^{\mathrm{T}}\mathit{\boldsymbol{C}} $惩罚非对角元素来提升函数映射矩阵C的正交性;向量d=di(i=1,2$ \cdots $k)中存储了$ {\mathit{\boldsymbol{C}}}^{\mathrm{T}}\mathit{\boldsymbol{C}} $经奇异值分解所得的到非零奇异值。

      为了提高对应关系计算结果的准确性,本文提出在计算对应关系矩阵C时引入贪心算法对其进行优化,使得最终得到的C和矩阵v能够计算出更为准确的对应关系。设置Cv的初始值:v=1(由m个1构成的向量),C=W。优化步骤分为CstepRstepVstep,重复这些步骤直到收敛。

      Cstep:令v*=v,用$ \underset{\mathit{\boldsymbol{C}}}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖\mathit{\boldsymbol{C}}\mathit{\boldsymbol{H}}-\mathit{\boldsymbol{B}}\left(\eta \left({\mathit{\boldsymbol{v}}}^{\mathrm{*}}\right)\right)‖}_{\mathrm{2, 1}}+{\rho }_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left(\mathit{\boldsymbol{C}}\right) $计算出相应的对应关系矩阵C

      Rstep:利用贪心算法对C进行优化。

      Vstep:令$ {\mathit{\boldsymbol{C}}}^{\mathrm{*}} $=C,利用$ \underset{\mathit{\boldsymbol{v}}}{\mathrm{m}\mathrm{i}\mathrm{n}}{‖{\mathit{\boldsymbol{C}}}^{\mathrm{*}}\mathit{\boldsymbol{H}}-\mathit{\boldsymbol{B}}\left(\eta \left(\mathit{\boldsymbol{v}}\right)\right)‖}_{\mathrm{2, 1}}+{\rho }_{\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{t}}\left(\mathit{\boldsymbol{v}}\right) $计算出v

    • 在优化对应关系的过程中,本文采用基于测地距离的贪心优化算法对得到的对应关系矩阵进行优化。使用贪心算法在计算局部最优解时更有优势。同时,模型在发生形变后,模型上的两点间的欧氏距离可能发生改变,但是两点间的测地距离是通过模型表面上两点间的表面路径距离计算的,因而,不受形变因素的影响,可以得到更准确的结果。

      当构建了模型间初始匹配的关系矩阵C后,将集合S和集合Y视为加权无向连通图G的顶点集合,边的权重为两点之间的测地距离,进而将匹配问题抽象化为图的最小权重值的优化计算问题。集合S和集合Y是不相交集合,且集合S中的每个点都与集合Y中的任一点相连。对于集合S中的点无法直接连接集合Y点的情况,可将其权重设置为$ \mathrm{\infty } $。

      本算法采用测地距离作为距离度量形式,且使用等距误差作为相似度度量。要度量模型上点对间的匹配是否是最优或近似最优,本文使用形变误差累加函数进行衡量:

      $$ \left\{\begin{array}{l}{D}_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left(\xi \right)=\frac{1}{\xi }\mathop \sum \limits _{\left({s}_{i}, {t}_{j}\right)}{d}_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left({s}_{i}, {t}_{j}\right)\\ {d}_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left({s}_{i}, {t}_{j}\right)=\frac{1}{\xi }\mathop \sum \limits _{\left({s}_{l}, {t}_{k}\right)}\left|Z\left({s}_{i}-{s}_{l}\right)-Z\left({t}_{j}-{t}_{k}\right)\right|\end{array}\right. $$ (16)

      式中,$ \xi $是所有匹配点对;$ {d}_{\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{r}}\left({s}_{i}, {t}_{j}\right) $为选取单一点对$ \left({s}_{i}, {t}_{j}\right) $时,对全局形变造成的误差累加和;sltk分别表示在sitj附近的点;$ Z\left(\right) $表示两点间的测地距离。设匹配关系的初始参数为$ \xi ={\xi }_{0}^{\left(k\right)} $。遍历当前$ \xi $的所有对应关系点对$ \left({s}_{i}, {t}_{j}\right) $,并使用等距误差小的点对$ \left({s}_{i}, {t}_{n}\right) $替换当前点对。通过贪心策略对所有点对逐步搜索和最优替换,最终可使Dcorr收敛,此时的结果$ \xi $即为所求的最优匹配结果。

      在选择点对(sitj)中tj的候选替换点tn时,并不进行全局搜索,因为在Cstep中,已经完成了初始匹配,所以搜索范围只需限定在局部区域内即可。设候选集合为Y,对于集合Y中的每一个顶点tm,计算dcorr(sitm)。当计算出的形变误差较点对(sitj)的误差小时,则进行替换。虽然匹配过程已经具有较好的初始化,但因模型自身对称性会造成错误匹配问题,对于这种情况要进行对称形式的替换,即将$ \left({\mathrm{s}}_{i}^{+}, \mathrm{ }{t}_{m}\right) $替换为$ \left({\mathrm{s}}_{i}^{+}, \mathrm{ }{t}_{j}\right) $,其中,$ {s}_{i}^{+} $表示si的对称点。因为计算是基于全局的形变信息,所以总可以获得最终的收敛结果。

    • 本文的实验数据采用TOSCA模型库,包括人、猫、狼、狗、马、半人马等模型。通过大量实验发现,分别选取k̩̩̩̍̍̍̍̍̍′=100,k=60,$ {\mu }_{1}={\mu }_{2}=1 $,$ {\mu }_{3}={\mu }_{4}=1\mathrm{ }000 $可以更直观地反映出模型间的对应关系。

      实验中,分别使用Laplace–Beltrami算子[13]和LMH算子(本文算法)构建了TOSCA模型库中狼模型、狗模型、马模型和人模型等完整模型与部分(或带孔洞的)非刚性模型的对应关系,结果如图 3~图 10所示。图 3中,若相同部位对应关系正确,则对应颜色相同,反之则不同。

      图  3  完整狼模型与带孔洞狼模型的对应关系比较

      Figure 3.  Comparison of the Constructed Correspondence Between the Full and the Holed Wolf Shapes

      图  4  完整狼模型和部分狼模型的对应关系比较

      Figure 4.  Comparison of the Constructed Correspondence Between the Full and the Partial Wolf Shapes

      图  5  完整狗模型与带孔洞狗模型的对应关系比较

      Figure 5.  Comparison of the Constructed Correspondence Between the Full and the Holed Dog Shapes

      图  6  完整狗模型与部分狗模型的对应关系比较

      Figure 6.  Comparison of the Constructed Correspondence Between the Full and the Partial Dog Shapes

      图  7  完整马模型与带孔洞马模型的对应关系比较

      Figure 7.  Comparison of the Constructed Correspondence Between the Full and the Holed Horse Shapes

      图  8  完整马模型与部分马模型的对应关系比较

      Figure 8.  Comparison of the Constructed Correspondence Between the Full and the Partial Horse Shapes

      图  9  完整人体模型与带孔洞人体模型的对应关系比较

      Figure 9.  Comparison of the Constructed Correspondence Between the Full and the Holed Man Shapes

      图  10  完整人体模型与部分人体模型的对应关系比较

      Figure 10.  Comparison of the Constructed Correspondence Between the Full and the Partial Man Shapes

      图 3(a)为完整狼模型M图 3(b)为文献[18]算法构建的带孔洞的狼模型的对应关系,和完整模型之间存在较多的错误对应,如左前腿、尾巴等。图 5(b)中狗的腿部、图 7(b)中马的右前腿以及图 9(b)中人的腿部和手臂也均存在错误对应。本文算法主要基于LMH算子的局部特性,可以更好地描述模型的局部信息,利用局部函数映射方法计算模型间的对应关系,并结合基于测地距离的贪心优化算法获得了更准确的模型间对应关系,如图 3(c)图 5(c)图 7(c)图 9(c)所示。

      图 4(a)为完整狼模型M图 4(b)为旋转后的狼模型,图 4(c)为文献[18]算法构建的部分狼模型的对应关系,模型自身对称性导致与完整模型间身体部位产生错误的对应关系。图 6(b)中部分狗模型前腿部位、图 8(b)中部分马模型前腿部位及图 10(b)中人体模型的胳膊部位均发生了错误的对应关系。本文在对应关系计算过程中采用了基于测地距离的贪心优化算法,将模型自身对称性造成的错误匹配进行对称形式替换,很好地解决了该问题,获得了更准确的对应关系,实验结果分别如图 4(d)图 6(c)图 8(c)图 10(c)所示。

      此外,本文算法还与文献[18]算法的等距误差进行比较,如表 1所示。表 1中,数值为无量纲,没有单位。

      表 1  两种算法的部分模型与完整模型间等距误差的比较

      Table 1.  Comparison of the Isometric Errors for Calculating the Shape Correspondences Between Partial Shape and Full Shape of Two Algorithms

      模型 等距误差
      文献[18]算法 本文算法
      带孔洞狼模型 0.098 724 0.087 807
      部分狼模型 0.137 226 0.116 253
      带孔洞狗模型 0.042 952 0.034 749
      部分狗模型 0.033 408 0.032 362
      带孔洞马模型 0.087 351 0.085 248
      部分马模型 0.087 298 0.069 958
      带孔洞人体模型 0.061 264 0.048 689
      部分人体模型 0.057 785 0.041 543

      表 1中,根据等距误差可以衡量模型间对应关系的正确率。可以看出,与文献[18]相比,本文算法所计算出的部分模型(或带孔洞模型)与完整模型的对应关系所产生的等距误差有明显减小。因此,本文算法能够得到更为准确的对应关系。

    • 模型间的对应关系问题是计算机图形学和计算机视觉领域的一个基本问题,而部分模型和完整模型的对应关系更是一个难点问题。首先,本文利用局部流行谐波计算出完整模型和部分模型的特征值与特征向量;其次,通过局部函数映射的方法构建部分模型与完整模型的初始匹配关系;最后,利用贪心算法优化计算结果,得到更为准确的部分模型与完整模型的对应关系。

      实验结果表明,本文算法减少了模型间对应关系的等距误差,使对应关系准确率得到了提高。由于本文利用的是局部信息描述符,所以在构建完整模型之间的对应关系问题上并没有提高。此外,构建更为一般的模型对应关系问题,如模型集合的一致对应关系、缺失大部分部件的部分模型与完整模型之间的对应关系、不同种类模型间的对应关系等,是今后要继续研究的问题。

参考文献 (20)

目录

    /

    返回文章
    返回