Polyhedral Model Retrieval Using Weighted Point Sets

Due to the recent improvements in laser scanning technology, 3D visualization and modeling, there is an increasing need for tools supporting the automatic search for 3D objects in archives. In this paper we describe a new geometric approach to 3D shape comparison and retrieval for arbitrary objects described by 3D polyhedral models that may contain gaps. In contrast with the existing approaches, our approach takes the overall relative spatial location into account by representing the 3D shape as a weighted point set. To compare two objects geometrically, we enclose each object by a 3D grid and generate a weighted point set, which represents a salient point for each non-empty grid cell. We compare three methods to obtain a salient point and a weight in each grid cell: (1) choosing the vertex in the cell with the highest Gaussian curvature, and choosing a measure as weight for that curvature, (2) choosing the area-weighted mean of the vertices in the cell, and choosing a measure as weight denoting the normal variation of the facets in the cell and (3) choosing the center of mass of all vertices in the cell, and choosing one as weight. Finally, we compute the similarity between two shapes by comparing their weighted point sets using a new shape similarity measure based on weight transportation that is a variation of the Earth Mover's Distance. Unlike the Earth Mover's Distance, the new shape similarity measure satisfies the triangle inequality. This property makes it suitable for use in indexing schemes, that depend on the triangle inequality, such as the one we introduce, based on the so-called vantage objects. The strength of our approach is proven through experimental results using a database consisting of 133 models such as mugs, cars and boats, and a database consisting of 512 models, mostly air planes, classified into conventional air planes, delta-jets, multi-fuselages, biplanes, helicopters and other models. The results show that the retrieval performance is better than related shape matching methods.