Shape decomposition and retrieval

Abstract

This thesis is about geometric algorithms for shape-based image retrieval. The shapes we consider are 2-D contours forming the boundaries of objects and regions of interest in an image. In order to do shape-based retrieval, we need to be able to evaluate how much two given shapes resemble each other. This is the shape matching problem. We concentrate in this thesis on a variant of this problem, the partial shape matching problem, which is concerned with matching a piece of one shape with a piece of the other. For this purpose, we use a decomposition of the shape into parts.

The first problem we study is the shape decomposition problem. We present in chapter 2 a framework for decomposing the boundary of a given polygonal shape that uses a skeleton of the shape. Among the skeleton branching points, some are points of special significance since they capture connections between different parts of the shape. Our decomposition framework applies to any skeleton, provided that some additional information is given. This additional information allows on one hand to identify those skeleton branching points that capture connections between parts, and on the other hand to find out the boundary demarcation points between these parts. We also describe in this chapter an instantiation of the proposed framework that uses the medial axis.

A decomposition of the interior of a polygonal shape, that uses the straight skeleton, is introduced in chapter 3. The skeleton nodes and the way they are generated in the propagation are also central to this decomposition method.

In chapter 4, we introduce the linear axis, a new skeleton for polygonal shapes. It is a straight skeleton of a modified version of the original polygon: a number of zero-length edges are inserted at reflex vertices. The insertion of these edges leads to linear skeletons that closely approximate the medial axis. This chapter offers also a thorough analysis of the relation between the number of inserted edges and the quality of this approximation.

We concentrate on the partial shape matching problem in chapter 5. Specifically, we are interested in evaluating how closely an ordered set of polylines is to being part of a given polygon. We introduce here a similarity measure for such a part-based matching, that is based on the turning function representation of the given polylines. This similarity measure was tested in a part-based shape retrieval application. The retrieval problem we considered is the following: given a large collection of shapes and a query consisting of a set of polylines, we want to retrieve those shapes in the collection that best match our query. The set of polylines forming the query are boundary parts in a decomposition of a database shape. We compared this part-based approach to shape matching with a global shape matching technique, based on a curvature scale space representation (CSS) of the shape. Experimental results indicate that in instances when the CSS matching has a low performance, our approach consistently performs better.

In the last chapter, we present another approach to part-based shape retrieval. The query, in this case, is a polygon, and in order to select among the large number of possible searches in the database with parts of the query, the user interacts with the system over a few successive searches in the database. This relevance feedback mechanism has two distinct steps. First, each database polygon has its constituent parts matched against the query polygon. The best matches are shown to the user, who marks those relevant to its query. In each successive iteration, based on the user’s feedback, the system computes a set of parts of the query polygon, that are used to re-search the database.