A simple and effective relevance-based point sampling for 3D shapes
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.
Section snippets
Contribution and application scenarios
The goal of our method is to introduce a general purpose sampler that yields points that can be adopted successfully to solve problems ranging from surface registration to object recognition. To this end, our sampler is not to be considered an interest point detector and the relevance measure we are introducing cannot be directly translated into a distinctiveness assessment. In fact, while distinctive points can be paramount for object recognition or classification, they could not be enough
Relevance-based sampling
Central to our sampling strategy is the concept of relevance defined for each point over a mesh. The relevance of a point p is related to how similar points around p are to it. The larger the number of similar points, the less distinctive, and thus the less relevant, p is. For this reason we formalize the idea of relevance of point p in terms of the area of a surface patch around it where points have a similar orientation. This is a very simple similarity notion, as it only accounts for the
Experimental evaluation
According to our stated goals, we designed a set of experiments specially crafted to assess the performance of the proposed approach with respect to three different problems. Namely, we tested the relevance-based sampling when used as a supplier of samples for the following tasks:
- •
Surface registration with ICP [3]. Relevance-based sampling is adopted as a substitute for uniform sampling and normal space subsampling [26];
- •
Object recognition in cluttered scenes [17]. Our method is used as a
Conclusions
In this paper we have presented a novel surface sampling strategy, based on the local distinctiveness of each point. Such distinctiveness is gauged through an integral measure, called relevance, that is robust with respect to noise. The points are then sampled with a density proportional to their distinctiveness. The method is easy to implement and it is genuinely adaptable, as the selectivity of the sampling can be easily tuned through parameters. Since we are proposing our sampling as a
References (26)
- et al.
Shot: Unique signatures of histograms for surface and texture description
Comput. Vis. Image Und.
(2014) - et al.
Object modeling by registration of multiple range images
Proceedings of the ICRA
(1991) - et al.
A method for registration of 3-d shapes
IEEE Trans. Pattern Anal. Mach. Intell.
(1992) - et al.
Efficient variants of the ICP algorithm
Third International Conference on 3D Digital Imaging and Modeling
(2001) Reliable 3d surface acquisition, registration and validation using statistical error models
International Conference on 3-D Digital Imaging and Modeling
(2001)- et al.
Geometrically stable sampling for the ICP algorithm
International Conference on 3-D Digital Imaging and Modeling
(2003) - et al.
A combined corner and edge detector
Proceedings of Fourth Alvey Vision Conference
(1988) - et al.
Theory of edge detection
Royal Soc. London Proc. Ser. B
(1980) - et al.
Point signatures: A new representation for 3d object recognition
Intl. J. Comput. Vis.
(1997) - et al.
A robust 3d interest points detector based on harris operator
Proceedings of the 3rd Eurographics Conference on 3D Object Retrieval
(2010)
Point feature extraction on 3d range scans taking into account object boundaries
2011 IEEE International Conference on Robotics and Automation (ICRA)
Intrinsic shape signatures: A shape descriptor for 3d object recognition
Proceedings of the ICCV Workshops
Surface feature detection and description with applications to mesh matching
Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition
Cited by (28)
A completely digital approach to scanning dental implants placed in a limited space or with an adverse angulation
2020, Journal of Prosthetic DentistryCitation Excerpt :As a result, the incomplete seating of the SBs was prevented. If the intraoral digital scans,7,8,11,12 superimposition process of SBs,13 and manufacturing of SBs10 are accurate and precise, the described technique can be applied in more complex clinical situations. However, the technique has limitations.
Intraoral scan bodies in implant dentistry: A systematic review
2018, Journal of Prosthetic DentistryStatistical shape modelling of the thoracic spine for the development of pedicle screw insertion guides
2023, Biomechanics and Modeling in MechanobiologyLearning Dense Features for Point Cloud Registration Using a Graph Attention Network
2022, Applied Sciences (Switzerland)
This paper has been recommended for acceptance by Dr. Y. Liu.