35. Istanbul 2004
a more accurate
n. The rest of the
give a summary
details of fitting
lges. We present
ion 4, along with
mation accuracy
jects. Finally, we
ctions for future
E
s it was noted in
d point clouds as
nate scan-to-scan
cthod (Besl and
from this pre-
n recognized and
ned in the final
stration (Dijkman
jon or exterior
G model contour
terior orientation
s of the modelled
recognition only
nages it provides
otter chances of
| iue for the
their man-made
imitives can be
et al. (1980) 85%
approximated by
ercentage rises to
> set of available
tjean, 2002).
ach, consisting of
m based object
on growing based
, Constraint. It is
faces in industrial
with their surface
edges. First of all
in the point cloud
Il neighbourhood.
ving in which we
he angle between
illy, segmentation
ms, because if we
ntation is reduced
from the object
segmentation, the
fitting and finding
fit. Most of the
1 able to achieve a
et al., 2000). The
sually to under-
ig assigned to one
stage detects the
ts using a Hough
1d outliers is not a
le to recover from
tation. The object
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
detection is currently limited to cylinders and planes, but in
many industrial environments they can account for more than
70% of the objects.
Next is the Constraint Detection stage where objects which have
been multiply detected are combined together, the cylinders
which might be connected are found, and the presence of curves
between pipes in proximity is hypothesized, and then checked
against the point cloud. The process of combining various
segments and assigning them to CSG objects from the Object
Catalogue is currently manual. But in future, we plan to make it
automatic.
The next stage of surface fitting assumes that the combination
of preceding segmentation and object recognition stages have
resulted in correctly labelled points, and we know which points
belong to which CSG model. Similarly in images the point
measurements (either manual or automatic) are correctly
assigned to their corresponding CSG objects. The details of
fiting the selected CSG objects to the point cloud and the
image measurements as well as their combination are discussed
in the following sections.
3. MODEL FITTING
3.1 Fitting of CSG model to point clouds
The problem we are addressing can be formulated as follows.
We have a set of points, which are sampled from some object
that can be approximated by the given CSG model. We want to
estimate those values of the parameters for the CSG object,
which minimize the sum of the squares of the orthogonal
distance of the points from the surface of the model i.e.,
N
min XY Vp Ett )] (D
i=]
O defines the shortest distance of a given point p to the
surface of the CSG model P which has M shape and pose
parameters given by. 7,,7,,...,7,,. The point cloud consists of
N'poiuts, p, p... py (Fig. 2(2)).
To solve this non-linear least-squares problem we need a
method to find the value of the distance function Q in (1) and
its partial derivatives with respect to the CSG parameters i.c.
dQ 9Q dQ
00 01, 07,
The calculation of Qis a difficult problem, as due to the
bounded surfaces used by the CSG specification it is not
possible to have closed form analytical expressions. For a
comparison of different numerical methods for its computation
we refer the reader to Rabbani and van den Heuvel (2004). Here
we use ACIS (2004), which is a commercial geometric
modelling engine to compute €. Similarly, the partial
derivatives are estimated numerically using finite differences.
As noted by Dennis and Schnabel (1996), for sufficiently small
step-size, the results obtained from the finite difference
approximation of the partial derivatives for the least-squares
solution are indistinguishable from the analytical ones.
(2)
For minimizing the function (1) with respect to parameters of
the CSG model we use Levenberg-Marquardt method (Bjórk,
1996; Press et al., 1996). Starting from an initial estimate of
CSG parameters [, at each iteration we get an adjustment
given by:
(a) (b)
Fig. 2: Calculation of distances for fitting (a) Q for a Point
Cloud, the model is shown in yellow, the red arrows from green
points to model surface indicate the distance (b) Y for an
Image, the measurements are in green, the back-projected model
is in yellow, and red arrows indicate their distance in image
space.
AF 2 (JJ - AJ) (JD) (3)
DU zD.-—AD (4)
where J is the Jacobian matrix and D is the distance vector
299. :
ik OT, (5)
D, = ©, (p,.T 4) (6)
©, is the distance of the ith point from the CSG surface, and
7, is the kth parameter of the CSG tree. In (3) above À is the
Levenberg-Marquardt parameter. When A =0 Newton step is
taken while for A — eo results in steepest descent step.
We are using quaternions (Shoemake 1985) for the specification
of rotation as they provide a singularity free representation. This
means we have four rotation parameters with one constraint i.e.:
G +4, +4; +4; =I (7)
The constraint in (7) cannot be enforced during the adjustment,
as Levenberg Marquardt is an unconstrained optimization
method. This means that we have an over-parameterisation and
the resulting matrix of normal equations can be singular. To
avoid the resulting numerical problems we use Singular Value
Decomposition (Golub, 1996) for inverting the matrix in (3).
This way if there is a rank deficiency we take the column
corresponding to minimum singular value out of the matrix
system and thus get a minimum norm solution.
3.2 Fitting of CSG Model to images
The use of CAD models for fitting to images was pioneered by
Lowe (1991). He estimated the pose and the shape parameters
by minimizing the distance of the visible edges from the hidden-
line projection of the estimated model. Vosselman et al. (2003)
extended and modified this approach for fitting CSG objects to
image gradients and point measurements for industrial
reconstruction. They also used internal and external geometric
constraints to reduce the number of degrees of freedom and thus
the required image measurements. We follow their fitting
approach for images, with one exception that we don't know a
priori the correspondence between image measurements and
back projected edges of the CSG model. Due to this missing
information we follow an iterative procedure, where before each
iteration for fitting, the measurements are assigned to the closest
edge.
