Shape Analysis

Shape and Image Retrieval by Organizing Instances Using Population Cues
A. Temlyakov, P. Dalal, J. Waggoner, D. Salvi, S. Wang
IEEE Workshop on the Applications of Computer Vision (WACV), 2013
PDF
Abstract

Reliably measuring the similarity of two shapes or images (instances) is an important problem for various computer vision applications such as classification, recognition, and retrieval. While pairwise measures take advantage of the geometric differences between two instances to quantify their similarity, recent advances use relationships among the population of instances when quantifying pairwise measures. In this paper, we propose a novel method which re- fines pairwise similarity measures using population cues by examining the most similar instances shared by the compared shapes or images. We then use this refined measure to organize instances into disjoint components that consist of similar instances. Connectivity is then established between components to avoid hard constraints on what instances can be retrieved, improving retrieval performance. To evaluate the proposed method we conduct experiments on the wellknown MPEG-7 and Swedish Leaf shape datasets as well as the Nister and Stewenius image dataset. We show that the proposed method is versatile, performing very well on its own or in concert with existing methods.

Landmark Sliding for 3D Shape Correspondence
P. Dalal, S. Wang
Intelligent Data Analysis for Real-Life Applications: Theory and Practice, 2012
PDF
Abstract

Shape correspondence, which aims at accurately identifying corresponding landmarks from a given population of shape instances, is a very challenging step in constructing a statistical shape model such as the Point Distribution Model. Many shape correspondence methods are primarily focused on closedsurface shape correspondence. The authors of this chapter discuss the 3D Landmark Sliding method of shape correspondence, which is able to identify accurately corresponding landmarks on 3D closedsurfaces and open-surfaces (Dalal 2007, 2009). In particular, they introduce a shape correspondence measure based on Thin-plate splines and the concept of explicit topology consistency on the identified landmarks to ensure that they form a simple, consistent triangle mesh to more accurately model the correspondence of the underlying continuous shape instances. The authors also discuss issues such as correspondence of boundary landmarks for open-surface shapes and different strategies to obtain an initial estimate of correspondence before performing landmark sliding.

Pre-organizing Shape Instances for Landmark-Based Shape Correspondence
B. C. Munsell, A. Temlyakov, M. Styner, S. Wang
International Journal of Computer Vision (IJCV), 2012
PDF
Abstract

The major challenge in constructing a statistical shape model for a structure is shape correspondence, which identifies a set of corresponded landmarks across a population of shape instances to accurately estimate the underlying shape variation. Both global or pairwise shape-correspondence methods have been developed to automatically identify the corresponded landmarks. For global methods, landmarks are found by optimizing a comprehensive objective function that considers the entire population of shape instances. While global methods can produce very accurate shape correspondence, they tend to be very inefficient when the population size is large. For pairwise methods, all shape instances are corresponded to a given template independently. Therefore, pairwise methods are usually very efficient. However, if the population exhibits a large amount of shape variation, pairwise methods may produce very poor shape correspondence. In this paper, we develop a new method that attempts to address the limitations of global and pairwise methods. In particular, we first construct a shape tree to globally organize the population of shape instances by identifying similar shape instance pairs. We then perform pairwise shape correspondence between such similar shape instances with high accuracy. Finally, we combine these pairwise correspondences to achieve a unified correspondence for the entire population of shape instances. We evaluate the proposed method by comparing its performance to five available shape correspondence methods, and show that the proposed method achieves the accuracy of a global method with the efficiency of a pairwise method.

2D Nonrigid Partial Shape Matching Using MCMC and Contour Subdivision
Y. Cao, Z. Zhang, I. Czogiel, I. Dryden, S. Wang
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011
PDF
Abstract

Shape matching has many applications in computer vision, such as shape classification, object recognition, object detection, and localization. In 2D cases, shape instances are 2D closed contours and matching two shape contours can usually be formulated as finding a one-to-one dense point correspondence between them. However, in practice, many shape contours are extracted from real images and may contain partial occlusions. This leads to the challenging partial shape matching problem, where we need to identify and match a subset of segments of the two shape contours. In this paper, we propose a new MCMC (Markov chain Monte Carlo) based algorithm to handle partial shape matching with mildly non-rigid deformations. Specifically, we represent each shape contour by a set of ordered landmark points. The selection of a subset of these landmark points into the shape matching is evaluated and updated by a posterior distribution, which is composed of both a matching likelihood and a prior distribution. This prior distribution favors the inclusion of more and consecutive landmark points into the matching. To better describe the matching likelihood, we develop a contour-subdivision technique to highlight the contour segment with highest matching cost from the selected subsequences of the points. In our experiments, we construct 1,600 test shape instances by introducing partial occlusions to the 40 shapes chosen from different categories in MPEG-7 dataset. We evaluate the performance of the proposed algorithm by comparing with three well-known partial shape matching methods.

Multiple Cortical Surface Correspondence using Pairwise Shape Similarity
P. Dalal, F. Shi, D. Shen, S. Wang
International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), 2010
PDF
Abstract

Accurately corresponding a population of human cortical surfaces provides important shape information for the diagnosis of many brain diseases. This problem is very challenging due to the highly convoluted nature of cortical surfaces. Pairwise methods using a fixed template may not handle well the case when a target cortical surface is substantially different from the template. In this paper, we develop a new method to organize the population of cortical surfaces into pairs with high shape similarity and only correspond such similar pairs to achieve a higher accuracy. In particular, we use the geometric information to identify colocated gyri and sulci for defining a new measure of shape similarity. We conduct experiments on 40 instances of the cortical surface, resulting in an improved performance over several existing shape-correspondence methods.

Two Perceptually Motivated Strategies for Shape Classification
A. Temlyakov, B. C. Munsell, J. Waggoner, S. Wang
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010
PDF
Abstract

In this paper, we propose two new, perceptually motivated strategies to better measure the similarity of 2D shape instances that are in the form of closed contours. The first strategy handles shapes that can be decomposed into a base structure and a set of inward or outward pointing “strand” structures, where a strand structure represents a very thin, elongated shape part attached to the base structure. The similarity of two such shape contours can be better described by measuring the similarity of their base structures and strand structures in different ways. The second strategy handles shapes that exhibit good bilateral symmetry. In many cases, such shapes are invariant to a certain level of scaling transformation along their symmetry axis. In our experiments, we show that these two strategies can be integrated into available shape matching methods to improve the performance of shape classification on several widely-used shape data sets.

Imaging Multidimensional Therapeutically Relevant Circadian Relationships
J. Singletary, P. Wood, J. Du-Quiton, S. Wang, X. Yang, S. Vishnoi, W. Hrushesky
International Journal of Biomedical Imaging, 2009
PDF
Abstract

Circadian clocks gate cellular proliferation and, thereby, therapeutically target availability within proliferative pathways. This temporal coordination occurs within both cancerous and noncancerous proliferating tissues. The timing within the circadian cycle of the administration of drugs targeting proliferative pathways necessarily impacts the amount of damage done to proliferating tissues and cancers. Concurrently measuring target levels and associated key pathway components in normal and malignant tissues around the circadian clock provides a path toward a fuller understanding of the temporal relationships among the physiologic processes governing the therapeutic index of antiproliferative anticancer therapies. The temporal ordering among these relationships, paramount to determining causation, is less well understood using two- or three-dimensional representations. We have created multidimensional multimedia depictions of the temporal unfolding of putatively causative and the resultant therapeutic effects of a drug that specifically targets these ordered processes at specific times of the day. The systems and methods used to create these depictions are provided, as well as three example supplementary movies.

3D Open-Surface Shape Correspondence for Statistical Shape Modeling: Identifying Topologically Consistent Landmarks
P. Dalal, L. Ju, M. McLaughlin, X. Zhou, H. Fujita, S. Wang
IEEE International Conference on Computer Vision (ICCV), 2009
PDF
Video
Abstract

Shape correspondence, which aims at accurately identifying corresponding landmarks from a given population of shape instances, is a very challenging step in constructing a statistical shape model such as the Point Distribution Model. The state-of-the-art methods such as MDL and SPHARM are primarily focused on closed-surface shape correspondence. In this paper we develop a novel method aimed at identifying accurately corresponding landmarks on 3D open-surfaces with a closed boundary. In particular, we enforce explicit topology consistency on the identified landmarks to ensure that they form a simple, consistent triangle mesh to more accurately model the correspondence of the underlying continuous shape instances. The proposed method also ensures the correspondence of the boundary of the open surfaces. For our experiments, we test the proposed method by constructing a statistical shape model of the human diaphragm from 26 shape instances.

Fast Multiple Shape Correspondence by Pre-Organizing Shape Instances
B. C. Munsell, A. Temlyakov, S. Wang
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009
PDF
Abstract

Accurately identifying corresponded landmarks from a population of shape instances is the major challenge in constructing statistical shape models. In general, shapecorrespondence methods can be grouped into one of two categories: global methods and pair-wise methods. In this paper, we develop a new method that attempts to address the limitations of both the global and pair-wise methods. In particular, we reorganize the input population into a tree structure that incorporates global information about the population of shape instances, where each node in the tree represents a shape instance and each edge connects two very similar shape instances. Using this organized tree, neighboring shape instances can be corresponded efficiently and accurately by a pair-wise method. In the experiments, we evaluate the proposed method and compare its performance to five available shape correspondence methods and show the proposed method achieves the accuracy of a global method with speed of a pair-wise method.

Evaluating Shape Correspondence for Statistical Shape Analysis: A Benchmark Study
B. C. Munsell, P. Dalal, S. Wang
IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2008
PDF
Abstract

This paper introduces a new benchmark study to evaluate the performance of landmark-based shape correspondence used for statistical shape analysis. Different from previous shape-correspondence evaluation methods, the proposed benchmark first generates a large set of synthetic shape instances by randomly sampling a given statistical shape model that defines a ground-truth shape space. We then run a test shape-correspondence algorithm on these synthetic shape instances to identify a set of corresponded landmarks. According to the identified corresponded landmarks, we construct a new statistical shape model, which defines a new shape space. We finally compare this new shape space against the ground-truth shape space to determine the performance of the test shape-correspondence algorithm. In this paper, we introduce three new performance measures that are landmark independent to quantify the difference between the ground-truth and the newly derived shape spaces. By introducing a ground-truth shape space that is defined by a statistical shape model and three new landmark-independent performance measures, we believe the proposed benchmark allows for a more objective evaluation of shape correspondence than previous methods. In this paper, we focus on developing the proposed benchmark for 2D shape correspondence. However it can be easily extended to 3D cases.

A New Benchmark for Shape Correspondence Evaluation
B. C. Munsell, P. Dalal, S. Wang
International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), 2007
PDF
Abstract

This paper introduces a new benchmark study of evaluating landmark-based shape correspondence used for statistical shape analysis. Different from previous shape-correspondence evaluation methods, the proposed benchmark first generates a large set of synthetic shape instances by randomly sampling a specified ground-truth statistical shape model. We then run the test shape-correspondence algorithms on these synthetic shape instances to construct a new statistical shape model. We finally introduce a new measure to describe the difference between this newly constructed statistical shape model and the ground truth. This new measure is then used to evaluate the performance of the test shape-correspondence algorithm. By introducing the ground-truth statistical shape model, we believe the proposed benchmark allows for a more objective evaluation of the shape correspondence than those that do not specify any ground truth.

A Fast 3D Correspondence Method for Statistical Shape Modeling
P. Dalal, B. C. Munsell, S. Wang, J. Tang, K. Oliver, H. Ninomiya, X. Zhou, H. Fujita
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007
PDF
Abstract

Accurately identifying corresponded landmarks from a population of shape instances is the major challenge in constructing statistical shape models. In this paper, we address this landmark-based shape-correspondence problem for 3D cases by developing a highly efficient landmark-sliding algorithm. This algorithm is able to quickly refine all the landmarks in a parallel fashion by sliding them on the 3D shape surfaces. We use 3D thin-plate splines to model the shape-correspondence error so that the proposed algorithm is invariant to affine transformations and more accurately reflects the nonrigid biological shape deformations between different shape instances. In addition, the proposed algorithm can handle both open-and closed-surface shape, while most of the current 3D shape-correspondence methods can only handle genus-0 closed surfaces. We conduct experiments on 3D hippocampus data and compare the performance of the proposed algorithm to the state-of-the-art MDL and SPHARM methods. We find that, while the proposed algorithm produces a shape correspondence with a better or comparable quality to the other two, it takes substantially less CPU time. We also apply the proposed algorithm to correspond 3D diaphragm data which have an open-surface shape.

Open-Curve Shape Correspondence Without Endpoint Correspondence
T. Richardson, S. Wang
International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), 2006
PDF
Abstract

Shape correspondence is the foundation for accurate statistical shape analysis; this is usually accomplished by identifying a set of sparsely sampled and well-corresponded landmark points across a population of shape instances. However, most available shape correspondence methods can only effectively deal with complete-shape correspondence, where a one-to-one mapping is assumed between any two shape instances. In this paper, we present a novel algorithm to correspond 2D open-curve partial-shape instances where one shape instance may only be mapped to part of the other, i.e., the endpoints of these open-curve shape instances are not presumably corresponded. In this algorithm, some initially identified landmarks, including the ones at or near the endpoints of the shape instances, are refined by allowing them to slide freely along the shape contour to minimize the shape-correspondence error. To avoid being trapped into local optima, we develop a simple method to construct a better initialization of the landmarks and introduce some additional constraints to the landmark sliding. We evaluate the proposed algorithm on 32 femur shape instances in comparison to some current methods.

Nonrigid Shape Correspondence using Landmark Sliding, Insertion and Deletion
T. Richardson, S. Wang
International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI), 2005
PDF
Abstract

The growing usage of statistical shape analysis in medical imaging calls for effective methods for highly accurate shape correspondence. This paper presents a novel landmark-based method to correspond a set of 2D shape instances in a nonrigid fashion. Different from prior methods, the proposed method combines three important factors in measuring the shape-correspondence error: landmark-correspondence error, shape-representation error, and shape-representation compactness. In this method, these three important factors are explicitly handled by the landmark sliding, insertion, and deletion operations, respectively. The proposed method is tested on several sets of structural shape instances extracted from medical images. We also conduct an empirical study to compare the developed method to the popular Minimum Description Length method.

Shape Correspondence through Landmark Sliding
S. Wang, T. Kubota, T. Richardson
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2004
PDF
Video
Abstract

Motivated by improving statistical shape analysis, this paper presents a novel landmark-based method for accurate shape correspondence, where the general goal is to align multiple shape instances by corresponding a set of given landmark points along those shapes. Different from previous methods, we consider both global shape deformation and local geometric features in defining the shape-correspondence cost function to achieve a consistency between the landmark correspondence and the underlying shape correspondence. According to this cost function, we develop a novel landmark-sliding algorithm to achieve optimal landmark-based shape correspondence with preserved shape topology. The proposed method can be applied to correspond various 2D shapes in the forms of single closed curves, single open curves, self-crossing curves, and multiple curves. We also discuss the practical issue of landmark initialization. The proposed method has been tested on various biological shapes arising from medical image analysis and validated in constructing statistical shape models.

Landmark-based Shape Deformation with Topology-Preserving Constraints
S. Wang, X. Ji, Z.-P. Liang
IEEE International Conference on Computer Vision (ICCV), 2003
PDF
Abstract

This paper presents a novel approach for landmarkbased shape deformation, in which fitting error and shape difference are formulated into a support vector machine (SVM) regression problem. To well describe nonrigid shape deformation, this paper measures the shape difference using a thin-plate spline model. The proposed approach is capable of preserving the topology of the template shape in the deformation. This property is achieved by inserting a set of additional points and imposing a set of linear equality and/or inequality constraints. The underlying optimization problem is solved using a quadratic programming algorithm. The proposed method has been tested using practical data in the context of shape-based image segmentation. Some relevant practical issues, such as missing detected landmarks and selection of the regularization parameter are also briefly discussed.

Shape Deformation: SVM Regression and Application to Medical Image Segmentation
S. Wang, W. Zhu, Z.-P. Liang
IEEE International Conference on Computer Vision (ICCV), 2001
PDF
Abstract

This paper presents a novel landmark-based shape deformation method. This method effectively solves two problems inherent in landmark-based shape deformation: (a) identification of landmark points from a given input image, and (b) regularized deformation the shape of an an object defined in a template. The second problem is solved using a new constrained support vector machine (SVM) regression technique, in which a thin-plate kernel is utilized to provide non-rigid shape deformations. This method offers several advantages over existing landmark-based methods. First, it has a unique capability to detect and use multiple candidate landmark points in an input image to improve landmark detection. Second, it can handle the case of missing landmarks, which often arises in dealing with occluded images. We have applied the proposed method to extract the scalp contours from brain cryosection images with very encouraging results.