Abstract
A Bayesian network formulation for relational shape matching is presented. The main advantage of the relational shape matching approach is the obviation of the nonrigid spatial mappings used by recent nonrigid matching approaches. The basic variables that need to be estimated in the relational shape matching objective function are the global rotation and scale and the local displacements and correspondences. The new Bethe free energy approach is used to estimate the pairwise correspondences between links of the template graphs and the data. The resulting framework is useful in both registration and recognition contexts. Results are shown on hand-drawn templates and on 2D transverse T1-weighted MR images.
Introduction
Shape matching—the process of finding correspondences between two sets of points—is a fundamental challenge in computer vision and medical imaging. Shapes often differ due to intrinsic factors like non-rigid deformations and topological changes, as well as extrinsic factors such as noise, occlusion, and varying global poses (rotation and scale).
Previous state-of-the-art methods, such as Thin-Plate Spline Robust Point Matching (TPS-RPM) or Shape Context, often rely on generic mathematical tools to warp space. However, these methods typically suffer from a "fundamental disconnect": the warping mechanism (e.g., a spline) is independent of the actual structure of the object being matched. This paper introduces the Relational Shape Matching (RSM) framework to bridge this gap by ensuring that the object's relational structure directly drives the matching and deformation process.
Methodology
The RSM framework treats shape matching as an inference problem within a Bayesian network. By representing a shape as a graph of interconnected points, the model can capture complex structural relationships.
Graph Representation and Cost Function
The template shape is represented as an undirected graph $G(V, E)$. The RSM objective function is designed to simultaneously estimate:
- Global Pose: Rotation ($R$) and scale ($s$).
- Local Deformations: Displacements ($U$).
- Correspondences: Point-to-point mappings ($M$).
Unlike methods that penalize absolute movement, RSM employs a Graph Laplacian prior. This prior penalizes relative deformations between connected neighbors, effectively using the shape's own topology to regularize the match.
Bethe Free Energy and Optimization
To solve for correspondences, the authors utilize the Bethe free energy approach. This concept, derived from statistical physics, provides a more accurate estimation of marginal probabilities on graphs with loops compared to simpler "fuzzy" matching techniques.
The optimization process is implemented via an alternating algorithm consisting of an "Outer Loop" and an "Inner Loop." The outer loop solves for rotation, scale, and deformation using conjugate gradient descent, while the inner loop updates correspondences using a belief propagation-style algorithm.
Experimental Evaluation
The algorithm was evaluated across three primary scenarios:
- Hand-drawn Templates: Successfully matched simple point sets to noisy, deformed versions.
- Fish Silhouettes: Demonstrated precision in matching points sampled from fish silhouettes against synthetic deformations.
- Medical Imaging (MRI): Tested on 2D transverse T1-weighted MR images of subcortical brain structures. Notably, the algorithm remained robust even when faced with topological differences, such as missing connections in the data graph.
Key Insights
- Structure-Driven Warping: Using the object's internal topology as the regularization mechanism is more physically intuitive than global splines.
- Inference-Based Matching: Framing shape matching as Bayesian inference allows the use of powerful tools like Belief Propagation.
- Computational Efficiency: By exploiting the sparsity of real-world shape connections, the complexity is reduced from $O(N^3)$ or $O(N^4)$ to $O(N^2)$, facilitating the processing of larger point sets.
Conclusion and Future Work
The RSM framework provides a robust, invariant approach to shape matching that excels in preserving topology. While current results are promising for 2D shapes, future work will focus on extending the framework to 3D environments, improving outlier rejection in highly cluttered scenes, and optimizing the algorithm for real-time recognition in large-scale databases.
Summary updated