A Search for Shape

Abstract

As 3D object collections grow, searching based on shape becomes crucial. 3D capturing has seen a rise in popularity over the past decade and is currently being adopted in consumer mobile hardware such as smartphones and tablets, thus increasing the accessibility of this technology and by extension the volume of 3D scans. New applications based on large 3D object collections are expected to become commonplace and will require 3D object retrieval similar to image based search available in current search engines. The work documented in this thesis consists of three primary contributions. The first one is the RICI and QUICCI local 3D shape descriptors, which use the novel idea of intersection counts for shape description. They are shown to be highly resistant to clutter and capable of effectively utilising the GPU for efficient generation and comparison of descriptors. Advantages of these descriptors over the previous state of the art include speed, size, descriptiveness and resistance to clutter, which is shown by a new proposed benchmark. The second primary contribution consists of two indexing schemes, the Hamming tree and the Dissimilarity tree. They are capable of indexing and retrieving binary descriptors (such as the QUICCI descriptor) and respectively use the Hamming and proposed Weighted Hamming distance functions efficiently. The Dissimilarity tree in particular is capable of retrieving nearest neighbour descriptors even when their Hamming distance is large, an aspect where previous approaches tend to scale poorly. The third major contribution is achieved by combining the proposed QUICCI descriptor and Dissimilarity tree into a complete pipeline for partial 3D object retrieval. The method takes a collection of complete objects, which are indexed using the dissimilarity tree and can subsequently efficiently retrieve objects that are similar to a partial query object. Thus, it is shown that local descriptors based on shape intersection counts can be applied effectively on tasks such as clutter resistant matching and partial 3D shape retrieval. Highly efficient GPU implementations of the proposed, as well as several popular descriptors, have been made publicly available to the research community and may assist with further developments in the field.