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

doi:10.3785/j.issn.1008-9497.2023.06.002

Journal of Zhejiang University (Science Edition)

2023, Vol. 50

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

CCF CAD/CG 2023

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

Download:

HTML( 4 )

PDF(4078KB)
Export: BibTeX | EndNote (RIS)

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

Received: 12 June 2023 Published: 30 November 2023

CLC:

TP 391.41

Corresponding Authors: Haibo WANG E-mail: shjliu.cg@csu.edu.cn;wanghaibo2022@csu.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Shengjun LIU
	Zi TENG
	Haibo WANG
	Xinru LIU

Cite this article:

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.

URL:

https://www.zjujournals.com/sci/EN/Y2023/V50/I6/668

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

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

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

Fig.1 Pipeline of detecting intrinsic symmetry in two-dimensional shapes method

Fig.2 Schematic diagram of the principle of extracting contour feature points from two-dimensional shapes

Fig.3 Incorrect feature point matching obtained on two-dimensional shapes by the method in reference ［31］

Fig.4 Intuitive explanation of condition （1）

Fig.5 Example of feature point matching in a two-dimensional shape

Fig.6 Experimental results for two-dimensional intrinsic symmetry detection

Fig.7 Visualization of symmetric axes in two-dimensional smooth axisymmetric shapes obtained by different methods

Fig.8 Visualization of intrinsic symmetry axes in two-dimensional smooth axisymmetric shapes obtained by different methods

方法	轴对称图形	$Δ θ$	$Δ 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

Table 1 Comparison of

Δ θ

and

Δ d

on different smooth axisymmetric shapes using different methods

Table 2 Comparison of average geodesic error on different smooth intrinsic symmetric shapes using different methods

Fig.9 Visualization of symmetric axes in two-dimensional noisy-axisymmetric shapes obtained by different methods

Fig.10 Visualization of intrinsic symmetry detection results on two-dimensional noisy shapes with different methods

方法	轴对称图形	$Δ θ$	$Δ 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

Table 3 Comparison of

Δ θ

and

Δ d

on different noisy axisymmetric shapes using different methods

Table 4 Comparison of average geodesic error on different noisy intrinsic symmetric shapes using different methods

Table 5 Average geodesic error for shapes with different densities and uniformity levels

Fig.11 Visualization of triangulation for shapes with different densities and uniformity levels using Triangle^［35］

Table 6 Average running time of different methods on axisymmetric shapes

Table 7 Average running time of different methods on intrinsic symmetric shapes

Fig.12 Human body shapes and algorithm results for individuals with significantly different arm lengths


[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]	Ye XingdeJiang Jinsheng. A New Pseudospectral Approximationfor. the Biharmonic Boundary Value Problem[J]. Journal of Zhejiang University (Science Edition), 1995, 22(1): 13-21.

Viewed

Full text

Abstract

Cited

Shared

Discussed