Algorithms for two-dimensional shape analysis using concavity trees

Abstract

This thesis presents data structures and algorithms for the analysis of the 2-D shape of patterns. In this work, a pattern is typically an object in a bi-level image and analyzing it involves two main ingredients: representing it in computer memory; and determining its degree of similarity to other patterns. The core idea around which this work is based is that of the convex hull of a set of points in the plane; after all, an object is a set of pixels in the plane of the image. From the simple concept of the convex hull stems the more involved concept of a concavity tree, a data structure that has remained largely unstudied, especially in connection to shape analysis. We present an efficient contour-based algorithm for concavity tree extraction, detailing its use in the decomposition of 2-D shapes into, and their reconstruction from, convex polygons. We compare the performance of the proposed algorithm with that of other existing algorithms and we report smaller reconstruction errors and faster execution speeds. We then introduce modifications to the contour-based algorithm that allow the resulting trees to better capture shape information for similarity matching purposes. We also propose a concavity tree matching algorithm that takes as input two labelled trees and returns the distance between them as a measure of the dissimilarity between the corresponding shapes. We then propose an efficient method for nearest-neighbour shape-based image retrieval based on concavity trees that allow for a query to be matched to a database without the need to fully compare the query against all the database entries. The shape matching abilities of concavity trees are evaluated and results and comparisons are reported. We show that concavity trees are able to boost the performance of global shape features by as much as 20% when those features are used to label the nodes of the trees. We also show how any shape matching metric that returns a "normalizable" distance between two silhouettes can be plugged in the proposed concavity tree matching algorithm, consistently resulting in a measurable improvement in the former's matching ability at a small performance cost. While their overall matching precision is not as good as the current state-of-the-art in shape matching when applied to data sets like MPEG7, concavity trees do provide a performance edge (in terms of computational complexity and retrieval time), allowing them to be used for first-stage matching, for example. Representing a shape using its concavity tree can be made a reversible process. That is, by storing appropriate information in the tree nodes, it is possible to reconstruct the original image from its tree representation. We take this idea further and show how, with some modifications to the core algorithm, a very compact and reversible representation of a shape can be computed during concavity-tree extraction. This new representation can be exact, or approximate to a pre-set degree, making it equivalent to a lossless or lossy compression of the image containing the shape. We report near-lossless compression ratios that are 40% better than the JBIG standard on the MPEG7 dataset. This technique allows for shape information to be extracted, possibly for shape retrieval and matching purposes, without the need to fully decompress the image (i.e., in the compressed domain). We also show how to extend the technique to images containing multiple shapes, with or without holes. In making the above technique applicable to arbitrary bi-level images while maintaining its low computational complexity, an on-line linear-time algorithm for computing the convex hull of a class of complex polygons was devised. Based on Melkman's simple-polyline algorithm, the proposed algorithm makes it possible to extract both, the contour of an object, as well as its convex hull, in one sequential pass, even when those contours form complex polygons. When an image contains multiple objects, each will have its own shape. However, it is quite possible that, collectively, groups of objects will project a shape that is different from that of their constituent objects. We propose a method for discovering object groupings in multi-object images and we accompany it with an algorithm for extracting their envelope. The proposed method involves a hierarchical clustering of the objects in the image based on their proximity as well as their "global" features. The proposed accompanying algorithm morphologically merges the objects in a grouping into a super-object, and then extracts their envelope by adaptively pruning the super-object's concavity tree and then reconstructing the resulting object. Since its concavity tree is readily available, the extracted envelope can then be used in shape matching using the approach outlined earlier. One viable application of shape matching is the trademark registration problem in which it is required to judge whether a new trademark is similar enough to an existing one as to warrant the rejection of the new trademark. In the case when the trademark is an abstract shape, it is very hard to carry out this task without using automated shape matching and retrieval tools. It is not unlikely for an abstract-shape trademark to be composed of multiple object groupings, making the matching and retrieval process even more challenging. We finally propose a data structure for representing the shape of multi-object images and their interactions. We introduce the new structure in detail, and outline how it can be used for shape analysis as well as similarity matching.