Decomposition of two-dimensional shapes by graph-theoretic clustering.

Area of Science:

• Computer Vision
• Computational Geometry
• Pattern Recognition

Background:

• Automated shape decomposition remains challenging.
• Existing methods often lack intuitive part interpretation.
• Human perception of shape parts is complex and subjective.

Purpose of the Study:

• To develop a computational technique for decomposing 2D shapes into meaningful parts.
• To establish a method for representing shape structure via binary relations.
• To validate the method's ability to identify human-like shape decompositions.

Main Methods:

• Transforming 2D shapes into a binary relation defined on boundary points or segments.
• Utilizing a graph-theoretic clustering approach to identify dense regions.
• Merging dense regions based on overlap to form shape part clusters.

Main Results:

• The clustering method successfully identified distinct parts in hand-drawn colon shapes and handprinted characters.
• The identified parts often align with human intuitive decompositions of the shapes.
• The binary relation effectively captures the internal structure of the shapes.

Conclusions:

• The proposed technique offers a robust method for automated shape decomposition.
• The graph-theoretic clustering provides an effective means to reveal intuitive shape parts.
• This approach has potential applications in image analysis and pattern recognition.