Shape matching based on skeletonisation and inexact graph matching

Shape matching is a difficult and important problem that remains unsolved. There are many applications of shape matching, including content-based image retrieval, computer-aided design, optical character recognition, and computational biology. Three criteria common to many shape matching applications are accuracy, robustness towards noise, and efficiency. An efficient shape matching method makes good use of the available computational resources. While many shape matching methods have been developed in the past, none completely meet these criteria. The aim of this thesis is to advance the state of the art in shape matching by meeting these three criteria of a shape matching method. To perform shape matching successfully, the shape representation must also be considered. A shape matching method will not meet these criteria unless an appropriate shape representation is chosen. Therefore, in this thesis, determining the shape representation is considered important and is the first step taken in performing shape matching. The second step, shape matching itself, is based on the representations of two shapes to be matched. The shape matching method determines how similar the two shapes are, and which parts of the two shapes best correspond to each other. The shape matching method developed in this thesis is based on the skeleton representation. Two skeletonisation algorithms are developed that ensure that the skeleton representation of a shape is accurate and conforms to a human's perception of the shape. The first skeletonisation algorithm adaptively places the contour points used to determine the skeleton, such that skeleton error is within a specified tolerance throughout the shape. The second skeletonisation algorithm targets accuracy issues more directly, by iteratively refining the skeleton in each region of the shape