Title: A quasi-visibility graph based clique-extraction heuristic model for partitioning of planar shape

Authors: Sourav Saha; Ankita Mandal; Sayantan Rana; Priya Ranjan Sinha Mahapatra

Addresses: Department of Computer Science, Institute of Engineering & Management, Kolkata, India ' Department of Computer Science, Institute of Engineering & Management, Kolkata, India ' Department of Computer Science, Institute of Engineering & Management, Kolkata, India ' Department of Computer Science, Institute of Engineering & Management, Kolkata, India

Abstract: This paper presents a graph theoretical model to partition polygonal approximation of a shape into visually meaningful constituent parts based on a heuristic approach. The proposed model introduces a new concept of approximated vertex-visibility graph termed as quasi-visibility graph to generate different viable cuts for partitioning the shape. In the shape representative graph, a maximal-clique perceptually corresponds to a distinguishable part. Based on this notion, we propose a heuristic based clique extraction strategy to decompose the shape exploring its quasi-visibility graph. A few refinement strategies are also attempted by exploring the options of: a) merging correlated parts for better visual interpretation; b) inserting antipodal points of reflex vertices in polygonal approximation for more possible viable cuts. The performance of the proposed model is evaluated by comparing partition-graphs of similar shapes. The partitioning based on the proposed model appears to be coherent with human observation and comparable with existing algorithms.

Keywords: shape partitioning; visibility graph; shape analysis; shape descriptor; quasi-visibility graph; clique-extraction heuristic; contour analysis; shape-graph.

DOI: 10.1504/IJAMS.2019.096654

International Journal of Applied Management Science, 2019 Vol.11 No.1, pp.36 - 54

Received: 24 Jul 2017
Accepted: 14 Jan 2018
Published online: 07 Dec 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article