Abstract
Efficient retrieval of shape-based information is a critical requirement for large-scale medical image databases. However, the non-Euclidean nature of shape spaces often necessitates the use of complex metric-tree indexing, which can be computationally inefficient. This paper presents a method for the optimal embedding of shape spaces into standard vector spaces. By aligning shapes to a Procrustean mean and minimizing distance distortions, we demonstrate that standard vector-indexing tools, such as kd-trees, can achieve high fidelity and superior search performance compared to specialized metric-tree approaches.
Introduction
In clinical practice, the geometric "shape" of an anatomical structure is often a primary diagnostic feature. For example, identifying specific vertebral deformities or bony growths (osteophytes) is essential for diagnosing spinal diseases. As medical databases grow to include tens of thousands of images, the ability to perform rapid similarity searches becomes paramount.
Mathematically, a shape is defined as the geometric information remaining after filtering out translation, scale, and rotation. This definition places shapes on a curved manifold—specifically, a complex projective space—where standard Euclidean coordinates do not exist. Traditionally, researchers have relied on metric space indexing, which only requires a distance function between objects. While flexible, metric trees are often slower and less efficient than vector space indexing (e.g., kd-trees), which leverages well-defined coordinates. The core challenge addressed here is how to "flatten" these curved shape spaces into a vector space without losing the accuracy of the original Procrustes distance metrics.
Methodology
The Shape Space Pipeline
The proposed method transforms raw image data into a searchable vector space through a multi-stage process of normalization and alignment.
- Landmark Representation: Each 2D shape is represented as a set of $m$ landmark points in a complex vector space $\mathbb{C}^m$.
- Normalization: Translation and scaling are factored out, moving the shapes into a "pre-shape space," which is geometrically equivalent to a unit sphere.
- Optimal Alignment: The innovation of this work lies in the rotation step. Every shape in the database is rotated to align with a common reference point, typically the Procrustean mean of the dataset.
- Embedding and Optimization: Once aligned, the shapes are represented as points in $\mathbb{C}^m$. An alternating iterative algorithm is employed to minimize the difference between the Euclidean distance in this new embedding and the "true" partial Procrustes distance of the original manifold.
Experimental Evaluation
The study utilized the NHANES II (National Health and Nutrition Examination Survey) database, containing approximately 17,000 spine X-ray images. From this, 2,812 segmented vertebral boundaries were extracted, each defined by a consistent set of 34 landmark points.
The performance of the proposed embedding was evaluated based on two criteria: Fidelity (how well the Euclidean distance approximates the Procrustes distance) and Search Efficiency (the computational cost of finding nearest neighbors).
Results and Discussion
High Fidelity and Accuracy
The embedding proved to be an exceptionally accurate approximation of the true shape space. The "Fractional Difference" (FD) between the embedded Euclidean distance and the Procrustes distance was a mere $4.59 \times 10^{-4}$. In practical search tests involving 100 queries for the 20 nearest neighbors, the embedding method produced results identical to the true metric 98% of the time. In the remaining 2% of cases, the discrepancy was limited to a single missing image.
Superior Search Efficiency
The primary advantage of the embedding is the ability to use kd-trees for indexing. As shown in the performance metrics, the kd-tree consistently outperformed various configurations of metric and clustering trees.
As the database size increases, the kd-tree demonstrates sub-linear complexity, scaling significantly better than traditional metric-based searches. Even when metric trees were "adapted" using greedy optimization algorithms to prune inefficient nodes, they could not match the raw efficiency of the kd-tree applied to the optimally embedded data.
Conclusion
This work demonstrates that while shape spaces are technically non-Euclidean, they are "flat enough" locally to allow for highly accurate linear embeddings. By mathematically aligning shapes to a central mean, we can leverage the speed of standard vector-indexing tools without sacrificing the clinical accuracy of shape-based retrieval. Future work will look toward extending this framework to 3D Procrustes analysis and exploring the impact of multi-organ datasets on embedding stability.
Summary updated