Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (11A): 230300237-5.doi: 10.11896/jsjkx.230300237

• Interdiscipline & Application • Previous Articles     Next Articles

Study on Decomposition of Two-dimensional Polygonal Objects

JIN Jianguo   

  1. Applied Mathematics Department of Science College,Zhejiang University of Technology,Hangzhou 310032,China
  • Published:2023-11-09
  • About author:JIN Jianguo,born in 1970,Ph.D,asso-ciate professor.His main research interests include computer graphics and applied mathematics.
  • Supported by:
    National Natural Science Foundation of China(61972458).

PDF (PC)

388

Abstract: This paper studies how to decompose the two-dimensional polygonal objects into meaningful parts.Psychologists have found that meaningful decomposition of objects is an important process for human beings to recognize objects.Especially,in image recognition,after the edge of the object in the image has been detected,the edge can be expressed as a closed polygon.So how to decompose the polygon is a very important step to recognize the object in image.In this paper,we first separate the vertices of polygon into several clusters by spectral analysis combined with K-means,and then by computing cut line fitness proposed in the paper,the algorithm choose the best cut line recursively on between-cluster and within-cluster.Experimental results show the effectiveness of this method.The quantitative analysis and comparison between the algorithm and the well-known artificial decomposition data set show that the algorithm decomposition results are in line with human thinking and have achieved good decomposition results.

Key words: Pattern recognition, Polygon decomposition, Spectral analysis, Clustering, Convexity

CLC Number: 

  • TP391
[1]SIDDIQI K,KIMIA B B.Parts of Visual Form:ComputationalAspects[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17:239-251.
[2]LATECKI L J,LAKAMPER R.Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution[J].Computer Vision and Image Understanding,1999,73(3):441-454.
[3]LIEN J M,AMATO N M.Approximate Convex Decomposition of Polygons[C]//SCG’04.Brooklyn,New York,USA,2004:9-11.
[4]BERTAMINI M,WAGEMANS J.Processing convexity andconcavity along a 2-D contour:figure-ground,structural shape,and attention[J].Psychon Bull Rev,2013,20:191-207.
[5]MENG F M,LI H L,WU Q B,et al.Seeds-Based Part Segmentation by Seeds propagation and Region Convexity Decomposition[J].IEEE Transactions on multimedia,2018,20(2):310-322.
[6]LI Z Y,QU W Y,QI H,et al.Near-convex decomposition of 2D shape using visibility range[J].Computer Vision and Image Understing,2021,210(9):103243.
[7]HOFFMAN D D,SINGH M.Salience of visual parts[J].Cognition,1997,63(1):29-78.
[8]BRAUNSTEIN M L,HOFFMAN D D,SAIDPOUR A.Parts of visual objects:an experimental test of the minima rule[J].Perception,1989,18:817-826.
[9]XU Y,EARLY S M.Computation of part structure:Evidence from visual search[J].Perception and Psychophysics,2002,64:1039-1054.
[10]LIN H Y S,LIAO H Y M,LIN J C.Visual Salience-Guided Mesh Decomposition[J].IEEE Transactions on Multimedia,2007,9(1):46-57.
[11]SINGH M,SEYRANIAN G D,HOFFMAN D D.Parsing Silhouettes:The Short-Cut rule[J].Perception and Psychophysics,1999,61:636-660.
[12]LUO L,SHEN C H,LIU X W,et al.A Computational Model of the Short-Cut Rule for 2D Shape Decomposition[J].IEEE Transactions on Image Processing,2015,24(1):273-283.
[13]TANASE M,VELTKAMP R C.Polygon Decomposition based on the Straight Line Skeleton[C]//SOCG’03.San Diego,USA,2002:58-67.
[14]LIEN J M,KEYSER J,AMATO N M.Simultaneous Shape Decomposition and Skeletonization[C]//ACM Symposium on Solid and Physical Modeling(SPM 2006).Cardiff,UK,2006:219-228.
[15]PAPANELOPOULOS N,AVRITHIS Y,KOLLIAS S.Revisiting the Medial Axis for Planar Shape Decomposition[J].Computer Vision and Image Understanding,2019,179:66-78.
[16]DE WINTER J,WAGEMANS J.Segmentation of object outlines into parts:A large-scale integrative study[J].Cognition,2006,99:275-325.
[17]LIU R,ZHANG H.Segmentation of 3D Meshes through Spectral Clustering[C]//Proceedings of the 12th Pacific Conference on Computer Graphics and Applictaions.2004.
[18]CHAHHOU M,MOUMOUN L,El FAR M,et al.Segmentation of 3D Meshes Using p-Spectral Clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2014,36(8):1687-1693.
[19]PANG Y W,XIE J,NIE F P,et al.Spectral Clustering by Joint Spectral Embedding and Spectral Rotation[J].IEEE Transactions on Cybernetics,2020,50(1):247-258.
[20]DUDA R O,HART P E,STORK D G.Pattern Classification,Second Edition[M].Wiley-Interscience Publication,2001:117-124.
[1] XU Jie, WANG Lisong. Contrastive Clustering with Consistent Structural Relations [J]. Computer Science, 2023, 50(9): 123-129.
[2] HU Shen, QIAN Yuhua, WANG Jieting, LI Feijiang, LYU Wei. Super Multi-class Deep Image Clustering Model Based on Contrastive Learning [J]. Computer Science, 2023, 50(9): 192-201.
[3] LIU Xiang, ZHU Jing, ZHONG Guoqiang, GU Yongjian, CUI Liyuan. Quantum Prototype Clustering [J]. Computer Science, 2023, 50(8): 27-36.
[4] CUI Yunsong, WU Ye, XU Xiaoke. Decoupling Analysis of Network Structure Affecting Propagation Effect [J]. Computer Science, 2023, 50(7): 368-375.
[5] WANG Mingxia, XIONG Yun. Disease Diagnosis Prediction Algorithm Based on Contrastive Learning [J]. Computer Science, 2023, 50(7): 46-52.
[6] LUO Ruiqi, YAN Jinlin, HU Xinrong, DING Lei. EEG Emotion Recognition Based on Multiple Directed Weighted Graph and ConvolutionalNeural Network [J]. Computer Science, 2023, 50(6A): 220600128-8.
[7] CHEN Jie. Study on Long Text Topic Clustering Based on Doc2Vec Enhanced Features [J]. Computer Science, 2023, 50(6A): 220800192-6.
[8] ZHANG Peng, LI Xiaolin, WANG Liyan. Dynamic Neighborhood Density Clustering Algorithm Based on DBSCAN [J]. Computer Science, 2023, 50(6A): 220400127-7.
[9] LIU Yao, GUAN Lihe. Superpixel Segmentation Iterative Algorithm Based on Ball-k-means Clustering [J]. Computer Science, 2023, 50(6A): 220600114-7.
[10] WANG Zhen, YANG Zhengwei, GAO Shunqi, ZHANG Lei. Visualization of Ocean Data Vector Field Based on Streamline Distance Clustering [J]. Computer Science, 2023, 50(6A): 220300284-7.
[11] CAI Shaotian, CHEN Xiaojun, CHEN Longteng, QIU Liping. Stratified Pseudo-label Based Image Clustering [J]. Computer Science, 2023, 50(6): 225-235.
[12] XU Yi, LUO Fan, WANG Min. Three-way Decision Movement Strategy Based on Hierarchical Clustering [J]. Computer Science, 2023, 50(6): 92-99.
[13] SHEN Qiuping, ZHANG Qinghua, GAO Man, DAI Yongyang. Three-way DBSCAN Algorithm Based on Local Eps [J]. Computer Science, 2023, 50(6): 100-108.
[14] RAO Dan, SHI Hongwei. Study on Air Traffic Flow Recognition and Anomaly Detection Based on Deep Clustering [J]. Computer Science, 2023, 50(3): 121-128.
[15] WANG Lei, DU Liang, ZHOU Peng. Hierarchical Multiple Kernel K-Means Algorithm Based on Sparse Connectivity [J]. Computer Science, 2023, 50(2): 138-145.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.