Shape representation using concavity graphs

In this paper, a new graph data structure for 2-D shape representation is proposed. The new structure is called a concavity graph, and is an evolution from the already known "concavity tree". Even though a concavity graph bears a fundamental resemblance to a concavity tree, the former is able to describe the shape of multiple objects in an image and their spatial configuration, and is hence inherently more complex. The aim of concavity graphs is two-fold: first we want to analyze the patterns in a multi-object image in a way that will (1) provide better representation of their shapes, and (2) convey useful information about how they "interact" together. Second, we want our analysis technique to facilitate similarity matching between two images. This paper introduces the new structure and outlines how it can be used for shape representation as well as similarity matching.