☁️Point Cloud Shape Detection
Last updated
Last updated
Due to the increasing size and complexity of geometric data sets there is an ever-growing demand for concise and mean- ingful abstractions of this data. Especially when dealing with digitized geometry, e.g. acquired with a laser scanner, no handles for modification of the data are available to the user other than the digitized points themselves. However, in or- der to be able to make use of the data effectively, the raw digitized data has to be enriched with abstractions and pos- sibly semantic information, providing the user with higher- level interaction possibilities.
The RANSAC paradigm extracts shapes by randomly draw- ing minimal sets from the point data and constructing cor- responding shape primitives. A minimal set is the smallest number of points required to uniquely define a given type of geometric primitive. The resulting candidate shapes are tested against all points in the data to determine how many of the points are well approximated by the primitive (called the score of the shape). After a given number of trials, the shape which approximates the most points is extracted and the algorithm continues on the remaining data. RANSAC exhibits the following, desirable properties:
it is conceptually simple, which makes it easily extensible and straightforward to implement
It is very general, allowing its application in a wide range of settings
It can robustly deal with data containing more than 50% of outliers [RL93]
Its major deficiency is the considerable computational demand if no further optimizations are applied.
apply RANSAC to extract cylinders from range data, use RANSAC and the gaussian image to find cylinders in 3D point clouds. Both methods, though, do not consider a larger number of different classes of shape primitives. Describe an algorithm that uses RANSAC to detect a set of different types of simple shapes. However, their method was adjusted to work in the image domain or
Given a point-cloud P = { p1 , . . . , pN } with associated nor- mals {n1,...,nN} the output of our algorithm is a set of primitive shapes Ψ = {ψ1 , . . . , ψn } with corresponding disjoint sets of points Pψ1 ⊂ P,...,Pψn ⊂ P and a set of remaining points R=P{Pψ1,...,Pψn}. Similar to [RL93] and [DDSD03], we frame the shape extraction problem as an optimization problem defined by a score function. The overall structure of our method is outlined in pseudo-code in algorithm 1. In each iteration of the algorithm, the prim- itive with maximal score is searched using the RANSAC paradigm. New shape candidates are generated by randomly sampling minimal subsets of P using our novel sampling strategy . Candidates of all considered shape types are generated for every minimal set and all candidates are collected in the set C. Thus no special ordering has to be imposed on the detection of different types of shapes. After new candidates have been generated the one with the highest score m is computed employing the efficient lazy score evaluation scheme.. The best candidate is only accepted if, given the size |m| (in number of points) of the candidate and the number of drawn candidates |C|, the probability P(|m|,|C|) that no better candidate was over- looked during sampling is high enough. We provide an analysis of our sampling strategy to derive a suit- able probability computation. If a candidate is accepted, the corresponding points Pm are removed from P and the candidates Cm generated with points in Pm are deleted from C. The algorithm terminates as soon as P(τ,|C|) for a user deined minimal shape size τ is large enough.
The complexity of RANSAC is dominated by two major factors: The number of minimal sets that are drawn and the cost of evaluating the score for every candidate shape. As we desire to extract the shape that achieves the highest possible score, the number of candidates that have to be considered is governed by the probability that the best possible shape is indeed detected, i.e. that a minimal set is drawn that defines this shape.
Consider a point cloud P of size N and a shape ψ therein consisting of n points. Let k denote the size of a minimal set required to define a shape candidate. If we assume that any k points of the shape will lead to an appropriate candidate shape then the probability of detecting ψ in a single pass is:
The probability of a successful detection P(n, s) after s can- didates have been drawn equals the complementary of s con- secutive failures:
Solving for s tells us the number of candidates T required to detect shapes of size n with a probability
For small P(n) the logarithm in the denominator can be approximated by its Taylor series
ln(1 − P(n)) = −P(n) + O(P(n)2 ) so that:
Given the cost C of evaluating the cost function, the asymptotic complexity of the RANSAC approach
