TL;DR
This paper introduces a novel shape matching method for 2D and 3D objects that is robust to articulation and other deformations. It uses an "eccentricity transform" to create compact shape descriptors based on geodesic distances, achieving state-of-the-art results on challenging benchmarks.
What Problem Does This Paper Address?
The increasing availability of 3D models and acquisition systems has fueled the need for efficient and robust shape matching techniques. A significant challenge in this field is handling articulated objects, where parts can move relative to each other. Traditional methods often struggle with these deformations, leading to incorrect matches. This paper aims to address this by developing a shape descriptor that is inherently invariant to articulation, as well as other common transformations like rotation and scaling.
Methods
The core of this work is the eccentricity transform. For a given shape (represented as a set of points in 2D or 3D), this transform assigns to each point the length of the longest geodesic path from that point to any other point within the shape. This is computed using geodesic distances, which are inherently more robust to articulation than Euclidean distances.
The eccentricity transform is then used to create two types of histograms, forming a compact shape descriptor:
- ECC histogram (h): A normalized histogram of the eccentricity values across all points in the shape. This captures the shape's "compactness" or elongation.
- ECC structure histogram (s): A histogram of the number of connected components of the level sets of the eccentricity transform. This captures the shape's "structure" or the number of distinct parts.
These two histograms, when combined, provide a powerful and compact representation that is invariant to translation, rotation, scaling, and articulation. Matching is performed by calculating the L2-norm distance between these descriptor pairs.
Datasets
The paper evaluates its method on several established shape matching benchmarks:
- 2D Shape Matching:
- Kimia 25
- Kimia 99
- MPEG7 CE-Shape-1
- Ling articulated shape database (specifically designed for articulated objects)
- 3D Shape Matching:
- McGill Shape Benchmark (features a large number of articulated shapes)
- Princeton Shape Benchmark (used for comparison, though less emphasis on articulation)
- SHREC'10 robustness benchmark (for triangle meshes)
Key Insights and Ideas
- Geodesic distances are key to articulation invariance: By using geodesic distances, which measure paths within the shape, the method naturally handles deformations that change the shape's overall configuration but not its internal connectivity.
- Two histograms are better than one: Combining a histogram of eccentricity values (compactness) with a histogram of connected components (structure) provides a more discriminative descriptor than either alone.
- Compactness and structure are complementary: The ECC histogram captures the overall shape, while the structure histogram helps differentiate shapes with similar overall forms but different internal arrangements.
- Simplicity leads to efficiency: The descriptor is compact and the matching process is straightforward, leading to fast retrieval times, which is crucial for large-scale databases.
Key Results
The proposed method achieves state-of-the-art performance on several benchmarks, particularly for articulated shapes.
- 2D Shape Matching: The method performs comparably to or better than existing methods on the Ling articulated shape database.
- 3D Shape Matching: On the McGill Shape Benchmark, which has a high proportion of articulated objects, the ECC-based descriptors (ECCobj, ECCborder, ECCmesh) show strong results, often outperforming other methods in terms of recall and average ranks. For instance, ECCobj often achieves better recall than other methods.
- Robustness: The method demonstrates robustness to articulation, scaling, and rotation.
Limitations and Future Work
- Limited structural detail: The authors acknowledge that the structure histogram (s) may not fully capture complex part structures or connections between parts. This can lead to similar histograms for shapes with different part arrangements.
- Low-level matching: The histogram matching (L2-norm) is described as "low level" and does not inherently consider higher-level context, which can lead to misclassifications in cases where shapes have superficially similar histograms but belong to different semantic classes.
- Disconnected shapes: The current method cannot handle disconnected shapes.
Future work suggested includes:
- Incorporating part structure: Developing methods to better capture the explicit part structure and topology of shapes.
- Context-aware matching: Exploring more sophisticated matching functions that consider the context of the shapes, potentially through metric learning or learning from representative examples.
- Partial shape similarity: Extending the approach to handle partial shape matching and occlusion by decomposing shapes into parts.
- Higher dimensional data: Applying the method to 4D data (e.g., time-varying shapes) and other metric spaces.
Summary updated