Randomized Sub-Volume Partitioning for Part-Based 3D Model Retrieval

Abstract

Given a query that specifies partial shape, a Part-based 3D Model Retrieval (P3DMR) system would retrieve 3D models whose part(s) matches the query. Computationally, this is quite challenging; the query must be compared against parts of 3D models having unknown position, orientation, and scale. To our knowledge, no algorithm can perform P3DMR on a database having significant size (e.g., 100K 3D models) that includes polygon soup and other not-so-well-defined shape representations. In this paper, we propose a scalable P3DMR algorithm called Part-based 3D model retrieval by Randomized Sub-Volume Partitioning, or P3D-RSVP. To match a partial query with a set of (whole) 3D models in the database, P3D-RSVP iteratively partitions a 3D model into a set of sub-volumes by using 3D grids having randomized intervals and orientations. To quickly compare the query with all the sub-volumes of all the models in the database, P3D-RSVP hashes high dimensional features into compact binary codes. Quantitative evaluation using several benchmarks shows that the P3D-RSVP is able to query a 50K model database in 2 seconds.