计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (7): 135-141.doi: 10.11896/jsjkx.240600124

• 计算机图形学&多媒体 • 上一篇    下一篇

基于新型势场模型的二维骨架计算

万照麟1, 马广哲2, 米乐2, 栗志扬2,3, 范晓鹏1   

  1. 1 哈尔滨工业大学计算学部 哈尔滨 150006
    2 大连海事大学信息科学技术学院 辽宁 大连 116026
    3 海口经济学院网络学院 海口 571132
  • 收稿日期:2024-06-20 修回日期:2024-09-07 发布日期:2025-07-17
  • 通讯作者: 范晓鹏(fxp@hit.edu.cn)
  • 作者简介:(zlwan@hit.edu.cn)
  • 基金资助:
    国家自然科学基金(62102059);国家资助博士后研究人员计划(GZB20230969);博士后面上项目(2023M740939)

Computing 2D Skeleton Using Novel Potential Model

WAN Zhaolin1, MA Guangzhe2, MI Le2, LI Zhiyang2,3, FAN Xiaopeng1   

  1. 1 Faculty of Computing, Harbin Institute of Technology, Harbin 150006, China
    2 Information Science and Technology College, Dalian Maritime University, Dalian, Liaoning 116026, China
    3 School of Network Science, Haikou University of Economics, Haikou 571132, China
  • Received:2024-06-20 Revised:2024-09-07 Published:2025-07-17
  • About author:WAN Zhaolin,born in 1992,Ph.D,assistant professor,master's supervisor,is a member of CCF(No.K8244M).Her main research interests include multimedia information processing and computer vision.
    FAN Xiaopeng,born in 1978,Ph.D,professor,Ph.D supervisor.His main research interests include data compression and computer vision.
  • Supported by:
    National Natural Science Foundation of China (62102059),Post-Doctoral Fellowship Program of CPSF(GZB20230969) and China Post-Doctoral Science Foundation(2023M740939).

PDF (PC)

20

摘要： 作为形状的一种简洁表示,骨架同时保留了形状的几何特性以及完整的拓扑结构。在骨架计算中,基于势场的方法认为骨架位于势场曲面的奇异点区域,并能够提供拓扑正确的连续骨架表示。但目前该方法得到的骨架仍然存在一些局限性,比如对噪声和等距变换敏感度较高等。为了解决这些问题,假定形状边界上均匀放置电荷,定义了一种新型的电势场用于二维骨架的计算。不同于传统势场采用欧氏距离,提出了利用热核函数来逼近形状内部的测地距离,进而计算形状内部的新型电势分布。由于热核测地距具有光滑性,因此其对形状噪声和等距变换表现出更强的鲁棒性。进一步,基于Nyström距离插值技术,提出了所定义势场的快速计算方法。最后,在两个形状数据集上进行了大量的骨架计算实验,分析了方法的主要参数。实验表明,所提方法可以产生稳定且简洁的形状骨架,在噪声的鲁棒性方面优于主流的骨架计算方法。

关键词: 形状表示, 骨架计算, 广义电势场, 热核, 平滑测地距离

Abstract: As a concise representation of shapes,skeletons preserve both the geometric characteristics and complete topological structure of the shapes.Among skeleton computation methods,the potential field-based approach suggests that skeletons are located in the region of singular points on the potential field surface and are capable of providing a topologically correct and con-tinuous representation of skeletons.However,the skeletons derived from this method still have some limitations,such as high sensitivity to noise and isometric transformations.To address these issues,this paper assumes that charges are evenly distributed on the shape boundary and defines a novel potential field inside the shape for the computation of 2D skeletons.Unlike traditional potential fields that use Euclidean distance,this paper utilizes heat kernel functions to approximate the geodesic distance within the shape,and then calculates the novel electric potential distribution within the shape.Due to the smoothness of the heat kernel geodesic distance,it exhibits stronger robustness against shape noise and isometric transformations.Furthermore,based on the Nyström distance interpolation technique,a fast computation method for the defined potential field is proposed.Extensive experiments are conducted on two shape datasets,and the parameters of this method are thoroughly analyzed,demonstrating that the proposed method can generate stable and concise shape skeletons,outperforming state-of-the-art competitors in the robustness of noise.

Key words: Shape representation, Skeleton computation, Generalized electric potential, Heat kernel, Smoothed geodesic distance

中图分类号: 

  • TP391
[1]KURNIANGGORO L,WAHYON O,JO K H.A survey of 2d shape representation:Methods,evaluations,and future research directions[J].Neurocomputing,2018,300:1-16.
[2]LI Z,QU W,QI H,et al.Near-convex decomposition of 2d shape using visibility range[J].Computer Vision and Image Understanding,2021,210:103243.
[3]ZOU Z,CHEN K,SHI Z,et al.Object detection in 20 years:A survey[J].Proceedings of the IEEE,2023,111(3):257-276.
[4]YU X,GAO Y,BENNAMOUN M,et al.A Lie algebra representation for efficient 2d shape classification[J].Pattern Recognition,2023,134:109078.
[5]BARMAN A,DUTTA P.Facial expression recognition usingdistance and shape signature features[J].Pattern Recognition Letters,2021,145:254-261.
[6]YANG C,FANG L,FEI B,et al.Multi-level contour combination features for shape recognition[J].Computer Vision and Image Understanding,2023,229:103650.
[7]JOSEPH-RIVLIN M,ZVIRIN A,KIMMEL R.Momenet:Flavor the moments in learning to classify shapes[C]//Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops.2019.
[8]OSOWSKI S,NGHIA D D.Fourier and wavelet descriptors for shape recognition using neural networks-a comparative study[J].Pattern Recognition,2002,35(9):1949-1957.
[9]DAMON J.Rigidity properties of the blum medial axis[J].Journal of Mathematical Imaging and Vision,2021,63(1):120-129.
[10]CAI X Q,YANG Z,CAI R B,et al.Image Skeleton Extraction Method Based on Flood-Fill[J].Journal of System Simulation,2020,32(8):1455-1464.
[11]ISAKARI H.A fast skeletonisation of 2D objects using a generalised double-layer potential and the H-matrix method[J].Transactions of the Japan Society for Computational Methods in Engineering,2023,23:115-121.
[12]CRANE K,WEISCHEDEL C,WARDETZKY M.The heatmethod for distance computation[J].Communications of the ACM,2017,60(11):90-99.
[13]BAI X,LATECKI L J,LIU W Y.Skeleton pruning by contour partitioning with discrete curve evolution[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(3):449-462.
[14]ENGWIRDA D.Locally optimal Delaunay-refinement and op-timisation-based mesh generation[D].Sydney:University of Sydney,2015.
[15]SHAMAI G,ZIBULEVSKY M,KIMMEL R.Efficient inter-geodesic distance computation and fast classical scaling[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2018,42(1):74-85.
[16]GAO F,WEI G,XIN S,et al.2d skeleton extraction based on heat equation[J].Computers Graphics,2018,74:99-108.
[17]IGLESIAS-COFÁN S,FORMELLA A.Guided thinning[J].Pattern Recognition Letters,2019,128:176-182.
[18]EL-GAALY T,FROYEN V,ELGAMMAL A,et al.A Bayesian approach to perceptual 3D object-part decomposition using ske-leton-based representations[C]//Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.AAAI,2015:3762-3768.
[19]REZANEJA M,SIDDIQI K.Flux graphs for 2D shape analysis[M]//Shape Perception in Human and Computer Vision.London:Springer,2013:41-54.
[20]SU C Y,LIU X Y.Skeleton Extraction Algorithm Based onHeat Method[J].Computer and Modernization,2022,23(3):59-63.
[21]MA G,WANG X,LIU X,et al.Computing 2D Skeleton viaGeneralized Electric Potential[C]//The 6th Chinese Conference on Pattern Recognition and Computer Vision.Springer-Verlag,2023:346-357.
[22]SHEN W,BAI X,YANG X W,et al.Skeleton pruning as trade-off between skeleton simplicity and reconstruction error[J].Science China Information Sciences,2013,56:1-14.
[23]SHEN W,BAI X,HU R,et al.Skeleton growing and pruning with bending potential ratio[J].Pattern Recognition,2011,44(2):196-209.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发