Research On Two-Dimensional Shape Representation And Applications

Two-dimensional (2D) shape representation is a problem central to research fields like computer vision and pattern recognition. It plays an important role in many applica-tions related to shape processing, such as shape retrieval, object recognition, symmetry detection, etc. A high-quality 2D shape descriptor should have the power of discrimi-nating shapes belonging to different classes. Besides that, it should not only be invariant to translation, rotation, uniform scaling and articulation of a shape, but also be robust to minor boundary noise and deformations. Designing a 2D shape descriptor that satisfies all the above requirements is still a key and challenging problem. Laplacian eigenfunc-tions of a shape are isometric invariants and capture important intrinsic characteristics of the shape, which makes it possible to use these eigenfunctions to represent a 2D shape. However, there are still some issues that need to be solved when representing a 2D shape with Laplacian eigenfunctions. For example, the analytic expressions for the Laplacican eigenfunctions are only known for a limited number of shapes; the signs of these eigenfunctions are undefined; and two eigenfunctions that correspond to close Laplacian eigenvalues can switch their orders for reasons like numerical instabilities. Skeleton can also capture important intrinsic characteristics of a shape, and it is one of the most important tools for representing 2D shapes. However, the shape descriptors that describe a shape based on skeleton are generally sensitive to boundary noise. Be-sides that, a skeleton is usually represented by a graph or a tree. When applying such skeleton-based shape descriptors to applications like symmetry detection, it usually re-quires some post-processing operations.One of the most important applications of 2D shape description is 2D shape re-trieval. A shape retrieval method computes the dissimilarity between two shapes by comparing their shape descriptors, hence the quality of a shape descriptor is directly re-lated to the accuracy of the retrieval results. Another application is symmetry detection for 2D shapes. Most existing symmetry detection methods focus on detecting one kind or several kinds of symmetries in a shape. Designing a simple and robust method that can automatically detect variety of symmetries (such as global and local, extrinsic and intrinsic, reflectional and rotational symmetries) in a 2D shape is still a challenge.Concerning the problems mentioned above, this thesis mainly focuses on (1) s-tudying the characteristics of Laplacian eigenfunctions and exploring the relationships between the Laplacian eigenfunctions of a 2D shape, (2) using Lapalcian eigenfunc-tions for 2D shape representation and retrieval and (3) describing a 2D shape based on its skeleton and using this skeleton-based shape descriptor for detecting variety of symmetries in a 2D shape. Concrete works and main innovations are as follows:(1) We proposed a method for characterizing the Laplacian eigenfunctions of 2D shapes, and clustered the Laplacian eigenfunctions of a 2D shape based on compar-ing the characteristics of the eigenfunctions. Specifically, we defined a 20-dimensional feature vector for a Laplacian eigenfunction based on analyzing the structure of the eigenfunction’s quasi Morse-Smale complex. This feature vector captures both topo-logical and geometrical characteristics of the eigenfunction. The similarity between two Laplacian eigenfunctions is the cosine similarity between their corresponding fea-ture vectors. Based on the similarity between each pair of Laplacian eigenfunctions of a 2D shape, we used a hierarchical clustering method to group the eigenfunctions. Eigen-functions within a same group have similar basic structures. The proposed method is helpful in gaining insight into both topological and geometrical characteristics of the abstract Laplacian eigenfunctions for 2D shapes, and is useful in exploring the relation-ships between the Laplacian eigenfunctions of a 2D shape. It opens up possibilities for the broader use of these eigenfunctions in various applications and potentially a smaller representation space for a 2D shape.(2) We proposed a novel method that uses Laplacian eigenfunctions for 2D shape retrieval. Shape representation and shape matching are two most important compo-nents of a shape retrieval method. For a Laplacian eigenfunction of a 2D shape, we constructed a weighted directed graph to represent the distribution of its extrema. This graph is named as signed natural neighbor graph (SNNG). For a 2D shape, we used the SNNGs of its first k non-trivial Laplacian eigenfunctions to describe it. The proposed shape descriptor is invariant to the translation, rotation, uniform scaling and articula-tion of the shapes, and is also insensitive to minor boundary noise. When matching two shapes, we determined the dissimilarity between two Laplacian eigenfunctions by comparing their associated SNNGs. Based on the dissimilarity matrix between the first k non-trivial Laplacian eigenfunctions of two shapes, we used the Hungarian algorithm to compute a best one-to-one matching between the two shapes’Laplacian eigenfunc-tions. The sum of the dissimilarities between the Laplacian eigenfunctions matched to each other is considered as the dissimilarity between the two shapes. By assigning signs to the weights of the SNNG’s edges, the proposed method handles the sign problem of the Laplacian eigenfunctions. By computing a best one-to-one matching between two shapes’Laplacian eigenfunctions, the proposed method handles the ordering problem of the eigenfunctions. Experimental results discussed in section 4 demonstrate that the proposed method is effective for 2D shape retrieval. Besides that, the proposed method is easy to extend to handle 3D shapes theoretically.(3) We proposed a method using the skeleton of a 2D shape for symmetry detec-tion. The method uses a 1D discrete function to describe a 2D shape, and this function is defined based on the relationship between the shape’s boundary sample points and skeleton. There is a one-to-one correspondence between the boundary sample points and the points on this function’s curve. We used the extrema to segment the curve of the 1D function into a number of curved segments. By comparing the characteristics of the segments, the proposed method automatically detects both global and partial, both extrinsic and intrinsic, and both reflectional and rotational symmetries in a 2D shape. The proposed method is insensitive to boundary noise as it uses pruned skeleton. The proposed shape descriptor is invariant to articulation because it uses inner distance as the distance metric. Instead of using a 2D graph to represent a shape’s skeleton, using a discrete 1D function reduces the complexity of skeleton-based processing and is easier to implement.