Source-linked AI summary
GIFT: A Real-time and Scalable 3D Shape Search Engine
Song Bai, Xiang Bai, Zhichao Zhou, Zhaoxiang Zhang, Longin Jan Latecki
TL;DR
Large-scale 3D shape retrieval requires scalable alternatives to computationally heavy projection-based pipelines. GIFT combines GPU acceleration with two inverted files for matching and re-ranking, achieving sub-second query times while reporting higher retrieval accuracy than state-of-the-art methods. Its rotation handling remains only partially invariant and relies on sufficient projections for reliable performance.
Problem
Projection-based 3D shape retrieval uses informative views but suffers heavy computational costs that limit scalability on large datasets.
Method
GIFT uses GPU acceleration for projection and feature extraction, plus inverted files for efficient multi-view matching and context-based re-ranking.
Results
GIFT controls average query time within one second and outperforms state-of-the-art methods in retrieval accuracy by a large margin.
Takeaways & Limitations
GIFT demonstrates potential for large-scale 3D shape retrieval and was reported as winning first place on the perturbed SHREC2016 large-scale dataset.
Takeaways & Limitations
The system normalizes scale and translation but not rotation completely; reliable performance is observed when more than 25 projections are used.
Abstract
from arXiv · showhide
Projective analysis is an important solution for 3D shape retrieval, since human visual perceptions of 3D shapes rely on various 2D observations from different view points. Although multiple informative and discriminative views are utilized, most projection-based retrieval systems suffer from heavy computational cost, thus cannot satisfy the basic requirement of scalability for search engines. In this paper, we present a real-time 3D shape search engine based on the projective images of 3D shapes. The real-time property of our search engine results from the following aspects: (1) efficient projection and view feature extraction using GPU acceleration; (2) the first inverted file, referred as F-IF, is utilized to speed up the procedure of multi-view matching; (3) the second inverted file (S-IF), which captures a local distribution of 3D shapes in the feature manifold, is adopted for efficient context-based re-ranking. As a result, for each query the retrieval task can be finished within one second despite the necessary cost of IO overhead. We name the proposed 3D shape search engine, which combines GPU acceleration and Inverted File Twice, as GIFT. Besides its high efficiency, GIFT also outperforms the state-of-the-art methods significantly in retrieval accuracy on various shape benchmarks and competitions.
1. Introduction
3D shape retrieval needs to scale to large repositories, but projection-based pipelines remain computationally expensive across feature extraction, multi-view matching, and re-ranking. GIFT addresses these bottlenecks with GPU acceleration and two inverted files while targeting real-time retrieval.
- Large 3D repositories and benchmarks make retrieval scalability increasingly important for practical applications.
- Projection-based retrieval leverages 2D observations because human visual perception of 3D shapes depends on multiple viewpoints.
- Projection rendering: Projection rendering uses virtual cameras to capture view collections, often after pose normalization for translation, rotation, and scale invariance.
- View feature extraction: High-dimensional view features make descriptor extraction, quantization, and distance calculation time-consuming.
- Multi-view matching: Set-to-set multi-view matching has high time complexity, limiting sophisticated matching strategies on large datasets.
- Re-ranking: Diffusion-based re-ranking commonly requires O(TN 3) complexity, making it unsuitable for real-time analysis.
- GIFT combines GPU acceleration with inverted files for projection, feature extraction, multi-view matching, and context-based re-ranking.
2. Proposed Search Engine
GIFT combines GPU acceleration with two inverted files to make projection-based 3D shape retrieval efficient and scalable. Its pipeline accelerates view extraction, multi-view matching, and contextual re-ranking while retaining retrieval quality.
- Projection and feature extraction: GIFT normalizes scale and translation before rendering views, while accepting that rotation is not completely invariant.The authors avoid PCA-based rotation normalization because it can be unstable for symmetric or planar shapes.
- Projection and feature extraction: GPU acceleration speeds projection rendering and CNN-based feature extraction from depth images.The CNN uses five convolutional layers and three fully connected layers, with normalized activations.
- F-IF multi-view matching: Multi-view matching uses Hausdorff-style set comparison, whose naive retrieval cost is O(N × N_v^2).Pairwise view-set matching is costly for large databases despite Hausdorff distance being relatively simple.
- F-IF multi-view matching: The first inverted file approximates matching by retaining comparisons between views assigned to the same nearest visual codeword.Multiple Assignment can improve precision at the cost of memory and online query time.
- S-IF contextual re-ranking: ACA re-ranking compares contextual neighbor distributions using fuzzy membership values rather than only pairwise shape similarity.It weights neighbors through fuzzy sets and is designed to avoid the high time complexity of diffusion processes.
- S-IF contextual re-ranking: The second inverted file exploits sparse contextual activations to accelerate ACA similarity computation.Each database shape stores its fuzzy-neighbor-set cardinality, shape IDs, and membership values.
3. Experiments
GIFT is evaluated across ModelNet, SHREC14LSGTB, and generic retrieval benchmarks using fixed multi-view, matching, and re-ranking settings. It achieves strong retrieval accuracy while keeping query time below one second, with inverted-file approximations trading a small accuracy decrease for substantial speedups.
- Experimental setup: Experiments use MAP, AUC, NN, FT, and ST, with 64 projections, a 256-entry inverted file, multiple assignment of 2, and CNN features from layers L5 and L7.These settings define the common experimental configuration, although the supplied passage truncates the re-ranking specification.
- ModelNet: 5.82% AUC and 5.31% MAP gains on ModelNet40, plus 3.32% AUC and 3.07% MAP gains on ModelNet10, are reported over the L7 baseline.GIFT also outperforms the compared state-of-the-art methods on both ModelNet subsets.
- Large Scale Competition: GIFT outperforms the compared SHREC14LSGTB methods, returning results in 63.14ms per query—four orders of magnitude faster than LCDR-DBSVC.LCDR-DBSVC requires 668.6s per query, whereas ZFDR reaches 1.77s with lower retrieval accuracy.
- Generic 3D Retrieval: GIFT achieves state-of-the-art performance consistently across all three metrics on PSB, WM-SHREC07, and McGill datasets.The comparison includes multiple descriptor, coding, and retrieval methods.
- Execution Time: Average query time remains within one second across datasets, including the largest SHREC14LSGTB set, despite substantial offline preprocessing costs.Training the CNN and building the first inverted file are identified as the most time-consuming offline operations.
- Parameter Discussion: Re-ranking produces a substantial performance boost, while approximate Hausdorff matching with F-IF causes a slight decrease relative to exact matching but significantly shortens query time.The F-IF analysis reports a 0.69s exact-Hausdorff baseline, at least one order of magnitude slower than the approximate version.
4. Conclusions
GIFT addresses the scalability challenges that limited earlier 3D shape retrieval systems by combining GPU acceleration with two inverted files. It achieves sub-second average query time while maintaining strong retrieval accuracy, including first place on the SHREC2016 perturbed dataset.
- 4. Conclusions: Earlier 3D shape retrieval methods faced severe obstacles as databases grew larger.The paper notes that retrieval had often been evaluated on small shape collections and that classical methods struggled with larger databases.
- 4. Conclusions: GIFT combines GPU acceleration with two inverted files to enable real-time multi-view matching and re-ranking.The system is presented as a scalability-focused search engine for larger 3D shape corpora.
- 4. Conclusions: Average query time is controlled within one second, demonstrating GIFT’s potential for large-scale 3D shape retrieval.The reported timing concerns online retrieval and supports the system’s real-time positioning.
- 4. Conclusions: GIFT won first place on the perturbed dataset in the SHREC2016 large-scale track.The submitted version competed in the latest SHREC2016 large-scale track cited by the paper.