Representation, matching, and classification of multi-sequence shapes

In computer vision research, shape is usually referred to the geometric properties of objects and it is very important in detecting and recognizing objects. Shape representation, the data structure to describe the shape, is the basis for shape analysis. Graph, due to its power in representing various relationship among shape parts, is frequently used in describing part-based 2D shapes. The flexibility of graphs, however, results in difficulties in matching and recognition of graphic shapes, especially when the number of edges is large because the matching of the edges usually involves the matching of the two nodes it connects. In many graphical shape representation methods, however, the number of edges will grow quadratically with respect to the number of nodes. That is partly the reason why recent research on shape analysis often deal with graphs with a limited number of nodes, or with edges abandoned.;In order to keep more shape details to improve the performance of shape recognition, graphs with larger number of nodes should be applied. This motivates us to design a shape representation method that can keep the connectivity linear to the number of nodes while most of the shape details are kept. For images where edges can be reasonably detected, we are arguing that images' intensity edges are the right connectivity information that should be kept. A new shape representation, multi-sequence shape (or MSS), is proposed. The matching, classification and indexing algorithms of MSS are also proposed and experiments are conducted to demonstrate the advantage of our shape representation method. In our representation method, the number of edges of graphs is linear to the number of nodes. The time complexity of our matching algorithms are O(N2 ) where N is the number of nodes. We will also show that our representation method is suitable for indexing so that retrieving a shape from a 60,000 shape database only takes a few milliseconds using a pre-computed index.;Our method could match and retrieve shapes very fast and accurately, based on three contributions of this dissertation. We proposed an efficient partial matching algorithm to find the most similar parts of two sequential shapes, which is the base of our proposed shape representation. Our algorithm does not need to exhaustively search all possible pairs of subsequences. Instead, we use a dynamic programming algorithm (due to Smith Waterman) to find the most similar parts efficiently The complexity of our method to find similar parts of two contours of length m and n, is only O(m · n). We compared our matching algorithm with other methods using contour shape models. Empirical analysis shows that our approach is about 10 to 20 times faster in rotation-invariant recognition because our method does not need to search all possible rotations to find the optimal orientation. Because our matching algorithm only extract similar parts of two contours, shape variance, such as occlusion, can be better tolerated and hence our algorithm is more robust to shape variance. In contrast to arbitrary distance functions that are used by previous methods, we use a probabilistic similarity measurement, p-value, to evaluate the similarity of two shapes. We conducted experiments on several public shape databases and the result indicates that our method outperforms state-of-the-art global and partial shape matching algorithms.;Based on the partial sequence shape matching algorithm, we propose a new shape representation, the multi-sequence shape, to represent shapes in both binary images and realistic images. We propose a matching algorithm for multi-sequence shapes and an algorithm that could recognize multi-sequence shapes from cluttered background as well. We are arguing that the proposed shape representation method, compared to traditional graphical shape models, such as contour model, sparse graph model, and dense graph model, is straightforward in nature and less complicated in representation and matching whereas contains sufficient shape details for common shape recognition tasks.;A structured learning algorithm is also proposed to improve the shape classification. Traditional methods for shape classification involve the establishment of point correspondences between shapes to produce matching scores, which are in turn used as similarity measures for classification. Learning techniques have been applied only in the second stage of this process, after the matching scores have been obtained. We take a different approach by learning point-to-point matching measures to produce similarity scores that minimize the classification loss. Instead of simply taking for granted the scores obtained by matching and then learning a classifier, we embed both matching and classification together within single machine learning scheme that optimizes the shape classification accuracy. The solution is based on a max-margin formulation in the structured prediction setting. Experiments in several shape databases reveal that such integrated learning algorithm substantially improves the classification accuracy of existing methods.