基于函数映射的二维形状内蕴对称检测算法

doi:10.3785/j.issn.1008-9497.2023.06.002

浙江大学学报（理学版）

2023, Vol. 50

Issue (6): 668-680 DOI: 10.3785/j.issn.1008-9497.2023.06.002

第26届全国计算机辅助设计与图形学学术会议专题

基于函数映射的二维形状内蕴对称检测算法

刘圣军^1,²(

),滕子¹,王海波¹(

),刘新儒¹

^1.中南大学数学与统计学院，湖南长沙 410083
^2.中南大学工程建模与科学计算研究所，湖南长沙 410083

Two-dimensional shape intrinsic symmetry detection algorithm based on functional map

Shengjun LIU^1,²(

),Zi TENG¹,Haibo WANG¹(

),Xinru LIU¹

^1.School of Mathematics and Statistics，Central South University，Changsha 410083，China
^2.Institute of Engineering Modeling and Scientific Computing，Central South University，Changsha 410083，China

全文: PDF(4078 KB)

HTML( 4 )

摘要：

针对现有的二维形状内蕴对称检测方法表现欠佳的问题，提出了基于函数映射的二维形状内蕴对称稠密点对应谱优化（FM-2DSISD）方法。首先，设计了对噪声数据鲁棒的稀疏特征对称点对提取算法。其次，利用特征对称点对和函数映射框架，建立了以保持函数映射矩阵每个主子矩阵对角正交性为优化目标的数学模型，证明了该优化目标能保持内蕴对称映射的等距性。借助谱上采样技术，通过频谱域和空间域交替迭代优化函数映射矩阵和逐点映射矩阵。数值实验表明，FM-2DSISD方法对二维光滑形状和噪声形状的检测效果均优于现有检测方法。

关键词： 二维形状; 内蕴对称; 谱方法; 函数映射

Abstract:

To address the problem that the performance of existing methods is unsatisfactory for detecting intrinsic symmetry in two-dimensional shapes, based on the flexible function mapping framework, we propose a spectral optimization method, named FM-2DSISD, to compute dense point maps for two-dimensional intrinsic symmetric shapes. Firstly, we design an algorithm robust to noise to extract sparse feature symmetry point maps. Secondly, using the feature symmetric point maps and the functional map framework, a mathematical model is developed whose optimization objective is to maintain the diagonality and orthogonality of each principal submatrix of the functional map matrix. We prove that the defined optimization objective can preserve the isometry of intrinsic symmetry maps. To solve the formula, we give an alternating iterative algorithm between the spatial and spectral domains via the spectral up-sampling technique. Numerical experiments show that the proposed algorithm performs better than the state-of-the-art methods on two-dimensional smooth shapes and noisy shapes.

Key words: two-dimensional shape intrinsic symmetry spectral method functional map

收稿日期: 2023-06-12 出版日期: 2023-11-30

CLC:

TP 391.41

基金资助: 国家自然科学基金资助项目(62172447)

通讯作者: 王海波 E-mail: shjliu.cg@csu.edu.cn;wanghaibo2022@csu.edu.cn

作者简介: 刘圣军（1979—），ORCID：https：//orcid.org/0000-0002-3222-5656，男，博士，教授，主要从事几何造型、数字几何处理、数据分析与智能计算研究，E-mail：shjliu.cg@csu.edu.cn.

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	刘圣军
	滕子
	王海波
	刘新儒

引用本文:

刘圣军,滕子,王海波,刘新儒. 基于函数映射的二维形状内蕴对称检测算法[J]. 浙江大学学报（理学版）, 2023, 50(6): 668-680.

Shengjun LIU,Zi TENG,Haibo WANG,Xinru LIU. Two-dimensional shape intrinsic symmetry detection algorithm based on functional map. Journal of Zhejiang University (Science Edition), 2023, 50(6): 668-680.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2023.06.002 或 https://www.zjujournals.com/sci/CN/Y2023/V50/I6/668

图1 二维形状内蕴对称性检测算法流程

图2 二维图形轮廓特征点提取原理示意

图3 文献［31］中方法在二维形状上得到的错误特征点匹配

图4 关于条件（1）的直观解释

图5 二维形状特征点配对示例

图6 二维内蕴对称检测实验结果

图7 二维光滑轴对称形状不同方法的对称轴可视化结果

图8 二维光滑内蕴对称形状不同方法的可视化检测结果

方法	轴对称图形	$Δ θ$	$Δ d$
SCC	Crab	1.484 5	0.9874
SCC	Bat	0.170 4	2.476 7
R-Detector	Crab	0	0.484 6
R-Detector	Bat	0	0.349 7
LIP-Detector	Crab	0	0.484 6
LIP-Detector	Bat	0	0.349 7
FM-2DSISD	Crab	0.069 1	0.007 4
FM-2DSISD	Bat	0.003 4	0.043 1

表1 用不同方法得到的不同光滑轴对称图形的对称轴指标

表2 用不同方法得到的不同光滑内蕴对称图形的平均测地误差

图9 二维噪声轴对称形状不同方法的可视化检测结果

图10 二维噪声内蕴对称形状不同方法的可视化检测结果

方法	轴对称图形	$Δ θ$	$Δ d$
SCC	Crab	0.491 6	0.330 6
SCC	Bat	0.846 8	1.271 0
R-Detector	Crab	0	0.515 6
R-Detector	Bat	0	0.349 7
LIP-Detector	Crab	0	0.515 6
LIP-Detector	Bat	0	0.349 7
FM-2DSISD	Crab	0.119 6	0.089 2
FM-2DSISD	Bat	0.033 6	0.016 8

表3 用不同方法得到的不同噪声轴对称图形的对称轴指标

表4 用不同方法得到的不同噪声内蕴对称图形的平均测地误差

表5 用FM-2DSISD方法得到的不同三角面片数图形的平均测地误差

图11 用Triangle库［35］得到的不同三角面片数图形的三角化可视化结果

表6 轴对称图形不同方法的平均运行时间

表7 内蕴对称图形不同方法的平均运行时间

图12 双手长度相差较大的人体形状及FM-2DSISD方法可视化结果

1	MEHAFFY M， SALINGAROS N. Symmetry in architecture： Toward an overdue reassessment［J］. Symmetry： Culture and Science，2021，32： 311-343. DOI：10.26830/symmetry_2021_3_311 doi: 10.26830/symmetry_2021_3_311
2	GAO L， ZHANG L X， MENG H Y，et al. PRS-Net： Planar reflective symmetry detection net for 3D models［J］. IEEE Transactions on Visualization and Computer Graphics，2020，27（6）： 3007-3018. DOI：10.1109/tvcg.2020.3003823 doi: 10.1109/tvcg.2020.3003823
3	LIN H T， LIU Z C， CHEANG C，et al. SAR-Net： Shape alignment and recovery network for category-level 6D object pose and size estimation［C］// 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）. New Orleans： IEEE，2022： 6697-6707. DOI：10.1109/cvpr52688.2022. 00659 doi: 10.1109/cvpr52688.2022. 00659
4	DONATI N， CORMAN E， OVSJANIKOV M. Deep orientation-aware functional maps： Tackling symmetry issues in shape matching［C］// 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition （CVPR）. New Orleans： IEEE， 2022： 732-741. DOI：10.1109/cvpr52688.2022.00082 doi: 10.1109/cvpr52688.2022.00082
5	NAGAR R， RAMAN S. 3Dsymm： Robust and accurate 3D reflection symmetry detection［J］. Pattern Recognition，2020，107： 107483. DOI：10.1016/j.patcog.2020.107483 doi: 10.1016/j.patcog.2020.107483
6	HUANG J， STOTER J，NAN L. Symmetrization of 2D polygonal shapes using mixed-integer programming［J］. Computer-Aided Design，2023， 163： 103572. DOI：10. 1016/j.cad.2023.103572 doi: 10. 1016/j.cad.2023.103572
7	MITRA N J， GUIBAS L J， PAULY M. Symmetrization［J］. ACM Transactions on Graphics，2007，26（3）： 63-70. DOI：10.1145/1276377.1276456 doi: 10.1145/1276377.1276456
8	WU H， CHEN X， LI P，et al. Automatic symmetry detection from brain MRI based on a 2-channel convolutional neural network［J］. IEEE Transactions on Cybernetics，2019，51（9）： 4464-4475. DOI：10. 1109/tcyb.2019.2952937 doi: 10. 1109/tcyb.2019.2952937
9	HUANG T， DONG B， LIN J，et al. Symmetry-aware transformer-based mirror detection［C］// Proceedings of the AAAI Conference on Artificial Intelligence. 2023，37（1）： 935-943. DOI：10.1609/aaai.v37i1.25173 doi: 10.1609/aaai.v37i1.25173
10	NAGAR R， RAMAN S. Reflection symmetry detection by embedding symmetry in a graph［C］// 2019 IEEE International Conference on Acoustics，Speech and Signal Processing （ICASSP）. Brighton： IEEE，2019： 2147-2151. DOI：10.1109/icassp.2019.8682412 doi: 10.1109/icassp.2019.8682412
11	GNUTTI A， GUERRINI F， LEONARDI R. Combining appearance and gradient information for image symmetry detection［J］. IEEE Transactions on Image Processing，2021，30： 5708-5723. DOI：10. 1109/tip.2021.3085202 doi: 10. 1109/tip.2021.3085202
12	LEI M， HONG W， ZHAO Z，et al. 3D printing of auxetic metamaterials with digitally reprogrammable shape［J］. ACS Applied Materials & Interfaces，2019，11（25）： 22768-22776. DOI：10.1021/acsami. 9b06081 doi: 10.1021/acsami. 9b06081
13	NIU C J， LI J， XU K. Im2struct： Recovering 3D shape structure from a single RBG image［C］// 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City： IEEE，2018： 4521-4529. DOI：10.1109/cvpr.2018.00475 doi: 10.1109/cvpr.2018.00475
14	LEE S， LIU Y. Skewed rotation symmetry group detection［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，32（9）： 1659-1672. DOI：10.1109/tpami.2009.173 doi: 10.1109/tpami.2009.173
15	LEE S， COLLINS R T， LIU Y. Rotation symmetry group detection via frequency analysis of frieze-expansions［C］// 2008 IEEE Conference on Computer Vision and Pattern Recognition. Anchorage： IEEE，2008： 1-8. DOI：10.1109/cvpr. 2008.4587831 doi: 10.1109/cvpr. 2008.4587831
16	NGUYEN T P， NGUYEN T T. Robust detectors of rotationally symmetric shapes based on novel semi-shape signatures［J］. Pattern Recognition，2023，138： 109336. DOI：10.1016/j.patcog.2023.109336 doi: 10.1016/j.patcog.2023.109336
17	AGUILAR W， ALVARADO-GONZALEZ M， GARDUNO E，et al. Detection of rotational symmetry in curves represented by the slope chain code［J］. Pattern Recognition，2020，107： 107421. DOI：10.1016/j.patcog.2020.107421 doi: 10.1016/j.patcog.2020.107421
18	BRIBIESCA E. A geometric structure for two-dimensional shapes and three-dimensional surfaces［J］. Pattern Recognition，1992，25（5）： 483-496. DOI：10.1016/0031-3203（92）90047-m doi: 10.1016/0031-3203（92）90047-m
19	BRIBIESCA E. A measure of tortuosity based on chain coding［J］. Pattern Recognition，2013，46（3）： 716-724. DOI：10.1016/j.patcog.2012.09.017 doi: 10.1016/j.patcog.2012.09.017
20	ALVARADO-GONZALEZ M， AGUILAR W， GARDUÑO E，et al. Mirror symmetry detection in curves represented by means of the slope chain code［J］. Pattern Recognition，2019，87： 67-79. DOI：10.1016/j.patcog.2018.10.002 doi: 10.1016/j.patcog.2018.10.002
21	NGUYEN T P， TRUONG H P， NGUYEN T T，et al. Reflection symmetry detection of shapes based on shape signatures［J］. Pattern Recognition，2022，128： 108667. DOI：10.1016/j.patcog.2022.108667 doi: 10.1016/j.patcog.2022.108667
22	NGUYEN T P， NGUYEN X S. Shape measurement using LIP-signature［J］. Computer Vision and Image Understanding，2018，171： 83-94. DOI：10.1016/j.cviu.2018.05.003 doi: 10.1016/j.cviu.2018.05.003
23	TABBONE S， WENDLING L， SALMON J P. A new shape descriptor defined on the Radon transform［J］. Computer Vision and Image Understanding，2006，102（1）： 42-51. DOI：10.1016/j.cviu.2005.06.005 doi: 10.1016/j.cviu.2005.06.005
24	OVSJANIKOV M， SUN J， GUIBAS L. Global intrinsic symmetries of shapes［J］. Computer Graphics Forum，2008，27（5）： 1341-1348. DOI：10. 1111/j.1467-8659.2008.01273.x doi: 10. 1111/j.1467-8659.2008.01273.x
25	RUSTAMOV R M. Laplace-Beltrami eigenfunctions for deformation invariant shape representation［C］// Proceedings of the fifth Eurographics Symposium on Geometry Processing. Barcelona：Eurographics Association，2007，257： 225-233.
26	XU K， ZHANG H， TAGLIASACCHI A，et al. Partial intrinsic reflectional symmetry of 3D shapes［J］. ACM Transactions on Graphics，2009： 1-10. DOI：10.1145/1661412.1618484 doi: 10.1145/1661412.1618484
27	XU K， ZHANG H， JIANG W，et al. Multi-scale partial intrinsic symmetry detection［J］. ACM Transactions on Graphics，2012，31（6）： 1-11. DOI：10.1145/2366145.2366200 doi: 10.1145/2366145.2366200
28	KIM V G， LIPMAN Y， CHEN X，et al. Möbius transformations for global intrinsic symmetry analysis［J］. Computer Graphics Forum，2010，29（5）： 1689-1700. DOI：10.1111/j.1467-8659.2010.01778.x doi: 10.1111/j.1467-8659.2010.01778.x
29	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）： No.30. DOI：10.1145/2185520.2185526 doi: 10.1145/2185520.2185526
30	WANG H， HUANG H， Group representation of global intrinsic symmetries［J］. Computer Graphics Forum，2017，36（7）： 51-61. DOI：10.1111/cgf.13271 doi: 10.1111/cgf.13271
31	NAGAR R， RAMAN S. Fast and accurate intrinsic symmetry detection［C］// 15th European Conference on Computer Vision. Munich： Springer，2018： 433-450. DOI：10. 1007/978-3-030-01246-5_26 doi: 10. 1007/978-3-030-01246-5_26
32	QIAO Y L， GAO L， LIU S Z，et al. Learning-based real-time detection of intrinsic reflectional symmetry［J］. IEEE Transactions on Visualization and Computer Graphics，2023，29（9）： 3799-3808. DOI：10.1109/tvcg.2022.3172361 doi: 10.1109/tvcg.2022.3172361
33	REN J， POULENARD A， WONKA P，et al. Continuous and orientation-preserving correspondences via functional maps［J］. ACM Transactions on Graphics，2018，37（6）： 1-16. DOI：10.1145/3272127.3275040 doi: 10.1145/3272127.3275040
34	MELZI S， REN J， RODOLA E，et al. ZoomOut： Spectral upsampling for efficient shape correspondence［J］. ACM Transactions on Graphics，2019，38（6）： 1-14. DOI：10.1145/3355089.3356524 doi: 10.1145/3355089.3356524
35	SHEWCHUK J R. Triangle： Engineering a 2D quality mesh generator and Delaunay triangulator［C］// Applied Computational Geometry： Towards Geometric Engineering. Berlin： Springer，1996： 203-222. DOI：10. 1007/BFb0014497 doi: 10. 1007/BFb0014497
36	MEYER M， DESBRUN M， SCHRÖDER P，et al. Discrete differential-geometry operators for triangulated 2-manifolds［C］// Visualization and Mathematics III. Berlin： Springer，2003： 35-57. DOI：10.1007/978-3-662-05105-4_2 doi: 10.1007/978-3-662-05105-4_2
37	SARFRAZ M， MASOOD A， ASIM M R. A new approach to corner detection［C］// International Conference on Computer Vision and Graphics. Netherlands： Springer，2006： 528-533. DOI：10.1007/1-4020-4179-9_75 doi: 10.1007/1-4020-4179-9_75
38	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）： 1383-1392. DOI：10.1111/j.1467-8659. 2009.01515.x doi: 10.1111/j.1467-8659. 2009.01515.x
39	LATECKI L J， LAKAMPER R， ECKHARDT T. Shape descriptors for non-rigid shapes with a single closed contour［C］// 2000 IEEE Conference on Computer Vision and Pattern Recognition. Hilton Head： IEEE，2000： 424-429. DOI：10.1109/cvpr.2000. 855850 doi: 10.1109/cvpr.2000. 855850
40	ZENG W， GUO R， LUO F，et al. Discrete heat kernel determines discrete Riemannian metric［J］. Graphical Models，2012，74（4）： 121-129. DOI：10.1016/j.gmod.2012.03.009 doi: 10.1016/j.gmod.2012.03.009
41	EZUZ D， BEN-CHEN M. Deblurring and denoising of maps between shapes［J］. Computer Graphics Forum， 2017，36（5）： 165-174. DOI：10.1111/cgf. 13254 doi: 10.1111/cgf. 13254
42	REN J， MELZI S， WONKA P，et al. Discrete optimization for shape matching［J］. Computer Graphics Forum， 2021，40（5）： 81-96. DOI：10.1111/cgf.14359 doi: 10.1111/cgf.14359
43	SEBASTIAN T B， KLEIN P N， KIMIA B B.， Recognition of shapes by editing their shock graphs［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（5）： 550-571. DOI：10.1109/tpami.2004.1273924 doi: 10.1109/tpami.2004.1273924

[1]	叶兴德江金生. 双调和方程边值问题的一种新的伪谱逼近[J]. 浙江大学学报（理学版）, 1995, 22(1): 13-21.

Viewed

Full text

Abstract

Cited

Shared

Discussed