A simple and effective relevance-based point sampling for 3D shapes

Highlights

• We propose a significant points sampling method that can be useful within many tasks.

• Control parameters allow to fine-tune the selection of distinctive points.

• The method is very easy to implement and fast to compute, yet effective.

• Experiments shows that the sampling performs well in several practical scenarios.

Abstract

The surface of natural or human-made objects usually comprises a collection of distinct regions characterized by different features. While some of them can be flat or can exhibit a constant curvature, others may provide a more mixed landscape, abundant with high frequency information. Depending on the task to be performed, individual region properties can be helpful or harmful. For instance, surface registration can be eased by a set of non-coplanar smooth areas, while distinctive points with high curvature can be key for object recognition. For this reason, it is often critical to perform a surface sub-sampling that is suitable to the actual processing goal. To this end, most of the shape processing pipelines found in literature come bundled with one or more sampling rules, designed to boost their performance and accuracy. In this paper we introduce a sampling method for 3D surfaces that aims to be general enough to be useful for a wide range of tasks. The main idea of our method is to exploit the extent of the region around each point that exhibits limited local changes, granting higher relevance to points contained in compact neighborhoods. The effectiveness of the proposed method is experimented through its adoption as a point sampler within three very different shape processing scenarios.

Introduction

Point sampling is a key operation for many algorithms dealing with surfaces. Its adoption is needed for several reasons. If the surface to analyze is expressed as a parametric 3D curve, sampling is a useful discretization step to produce data which is easier to handle with standard algorithms. Even if the surface is represented as a triangulated mesh, sampling may help in reducing the total amount of points to handle, which can be mandatory if the complexity of the intended task is not linear and the meshes are large. However, the most important goal of sampling is probably the selection of surface points that are meaningful with respect to the task that is to be performed. To this end, it is quite natural that different sampling methods have been proposed to deal with each specific problem.

A quite standard example is the case of ICP surface registration [1], [2]. This widely adopted method is used to obtain an accurate alignment between two coarsely registered surfaces. It is widely applied in the field of 3D scanning, where devices are able to capture only partial views and a proper alignment between them is needed to recover the complete surface of the scanned object. It basically works by iteratively minimizing a distance function measured between pairs of selected neighboring points. Regardless of the chosen distance function and matching criteria, for an accurate registration it is very important to sample points that are able to constrain well the rigid transformation between the processed surfaces. In fact, many different sampling variants have appeared in literature throughout the last decades. The normal space subsampling introduced by Rusinkiewicz and Levoy [3] attempts to sample uniformly on the sphere of normal directions rather than on the surface. The rationale is to avoid the predominance of large coplanar regions that would result in too many degrees of freedom. An interesting approach to better constrain the transformation is to select points that best equalize the error covariance matrix. To this effect Guehring [4] proposes to weigh the samples based on their contribution to the covariance matrix, but since the analysis is performed after the sampling, the approach cannot constrain the transformation if too few samples are chosen in a relevant region. On the other extreme, Gelfand et al. [5] propose an approach that selects the points that bind the transformation the most.

Sampling is also crucial for 3D object recognition tasks. However, differently from registration, the goal for the selected points set is not to be able to constrain a rigid motion, but rather to be distinctive enough to ease their recognition among different instances of the same object. The idea of point distinctiveness has been extensively used in image processing to develop interest point detectors such as the Harris Operator [6] and Difference of Gaussians [7]. While these approaches work well with 2D intensity images, they cannot be easily extended to handle 3D surfaces since no intensity information is directly available. Several efforts have been made to use other local measures, such as curvature or normals to find relevant points on a surface. One of the first descriptors to capture the structural neighborhood of a surface point was described by Chua and Jarvis, who with their Point Signatures [8] suggest both a rotation and translation invariant descriptor and a surface matching technique.

More recent 3D interest point detectors include Harris 3D [9], a generalization of the Harris 2D detector to Euclidean surfaces, Normal Aligned Radial Features [10], making explicit use of object boundary information, and Intrinsic Shape Signatures [11], providing a weighted occupational histogram of data points, computed with respect to a local intrinsic 3D reference frame. In order to guarantee such frame to be stable, it is aligned on selected salient features characterized by large three dimensional point variations. Such property is assessed by looking at the smallest eigenvalue of the point scatter matrix of the feature neighborhood. An additional check is finally performed on the ratios of the eigenvalues to avoid ambiguous frames resulting from symmetries. Zaharescu et al. [12] presented an approach for feature point detection (MeshDOG) and description (MeshHOG), based on the value of any scalar function defined over the surface (i.e., curvature or texture, if available). Other widely adopted 3D point descriptors include Spin Images [13], a rich characterization obtained by a binning of the radial and planar distances of the surface samples respectively from the feature point and from the plane fitting its neighborhood, and SHOT [14], which, in addition to the feature vector, also derives a repeatable local reference frame. The interested reader can refer to [15] for a comprehensive evaluation of recent 3D keypoint detectors.

In this paper we introduce a general sampling method, described in the next section, which aims to select points that can be successfully adopted within all the described scenarios. To this end, we associate to each surface point a weight, named relevance, assessing its degree of uniqueness with respect to the region in which it is contained. The basic idea is that the relevance should be high for points that have unique normal orientation with respect to their surroundings, while it should be low for evenly oriented patches. Also, relevance should be inversely proportional to the area of the neighborhood, thus fostering points that do not belong to large regions of uniform curvature. Furthermore, the measure should be computed through an integral measure, thus making it robust with respect to noise. Such relevance can be used to define the probability density distribution upon which the actual sampling is based. The rationale of a relevance-based sampling is that distinctive points that can be adopted for object recognition usually correspond to ridges, corners or valleys. Such features will obtain high relevance values, and thus should be favored in the selection. At the same time, points lying in flat areas, while yielding low relevance, can still be selected due to their large number. Also, areas with uniform curvature are expected to be regularly sampled over all their span in a similar manner to what would happen adopting normal space subsampling. The stated all-roundness of this sampling has been put to the test in the experimental section, where we use it as a drop-in replacement for several state-of-the-art points selection methods within three tasks.