International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
Danish estimator GermanMcClure estimator
F(oyss Epor | ICTY FR a
W(v)2 Exp(- | FG) ) wv) = wv) = 1 on
, (I v^y
Minimum Sum estimator Huber estimator
W (i) = d. I para |v|/0< a
s | V i Wy) = ]
EL ara Ivl/o »a
|vi/o A
Fig. 2: Robust estimators
2.3.1 Strategy of resolution
The typical algebraic resolution of the problem relies on the
condition that the area of the triangle formed by each edge
points P,(xi, y;); , P2(xo, y3); of the extracted segments and the
candidate vanishing point Vp(x,y) equals zero (collinearity
condition). This leads to the minimization of the residuals (V;)
of the observation equation:
Thus, the most critical step of the resolution is to invert the
normal matrix which gives the solution of the Least Squares
Adjustment equivalent to minimizate areas of triangles.
The solution corresponds to the minimum eigenvalue of the
diagonal matrix D corresponding to a SVD decomposition
A=UDV" of A, being U, V are orthogonal matrices. With more
details, the SVD consists of two steps: 1) Obtain a bi-diagonal
matrix by operating with Householder's reflectors, and 2)
Develop an iterative process by using Given's rotations. As it is
well known, the exact algebraic resolution is a typical example
of an ill-conditioned problem due to two issues: a) The
apparition of a great number of null entries in the matrix A
which give serious round errors in normal matrix inversion. b)
Redundant information can generate blunders errors that appear
irregularly distributed among observations, by making difficult
their identification. Several strategies based on using some a
priori knowledge have been developed including more
advanced variants of RANSAC methods [Tor03]. In this work,
we have selected a more down-to-earth solution based on the
robust Danish estimator, which improve results of more
traditional adjustment based on LSM. To justify our choice, we
shall compare different estimators.
2.4 Grouping tools: maps of quadrilaterals and cuboids
The automatic management of convex quadrilaterals related to
the intersection of pairs of pencils from perspective lines in
each view is symbolically performed with quadtrees according
to the quadrangular segmentation. To avoid an excessive
fragmentation of intersections of pencils of perspective lines,
and to lower the high complexity of corresponding quadtrees,
we use typical tricks of ray-tracing allowing us to identify
partial occlusions following a typical multilayered model.
Similarly the management of closed regions in the orthogonal
3D model of the scene is performed in terms of octrees obtained
from triplets of pencils of perspective planes through three
vanishing lines. Exterior or cross-product and contraction in
Geometric Algebra allow to transfer information between
simplified 2D and 3D models. A convex quadrilateral is the
image of a rectangle by a projective transformation in the plane.
A quadrilateral map of convex quadrilaterals is automatically
generated from the intersection of pairs of pencils (bundles of
perspective lines) through two vanishing points Vi, V5. A pair
of pencils is called a net of lines. To simplify the management
of 2D projective primitives linked to nets of lines, we introduce
a symbolic representation. given by quadtrees linked to
templates of convex quadrilaterals. By using a third vanishing
point away from the vanishing line, we lift quadrilateral 2D
nets to cuboid 3D families of lines (called webs) which provide
an easily adjustable 3D template. The computer management of
nets is performed by quadtrees supported on planar templates
given by perspective quadrilaterals. In the same way, the
computer management of webs of lines is performed by octrees
supported on volumetric templates given by cuboids. A cuboid
is the image of a rectangle parallelepiped by an affine
transformation in 3D space. The quadrilateral map linked to
changing quadrilaterals is easily updated in an incremental way
by inserting/deleting quadrilaterals associated to elementary
events given by segments. The splitting/grouping process of
quadrilaterals arising from such updating can be described by
an algorithm with a linear complexity in the number of
elementary events. Multiple junctions are extracted by means of
a variant of the Deriche's filter. Types of junctions inform to us
about typical occlusions, or about convex or concave features.
The allowed types of multiple junctions are double, triple and
quadruple (only allowed at vanishing points in our case).
Typical junctions at architectural scenes correspond to a) two
incident walls (without additional information about ceiling or
floor) are L-type double junctions, b) corners of inserted
elements (doors, windows, etc) on a wall are T-type double
junctions, . c) corners associated to the perspective
representation of trihedrals are Y or T-type triple junctions, d)
vertices of wireframed 3D representations or vanishing points
linked to 4-tuples of lines are quadruple junctions. The
automatic identification of collections of junctions along a
closed polygonal allow us to generate facets, by including
information about partially occluded regions, due to the relative
localization of the camera. The comparison between regions in
different views is reduced to find isomorphism between
maximal ordered collections of junctions along candidate to be
homologue polygonals.
An automatic interpretation of saliencies in the 3D scene is
performed with corners labelled. To begin with, let us suppose
that the sweep out has given us segmentation by quadrilaterals
supported on perspective lines. Each salient or entrant corner is
characterized by three walls confluent at a typical Y-triple
corner, ie. a corner where discontinuities arising from
extending visible segments are alternant with visible segments
incident at such junction. So, in a typical architectural scene
each triple junction Y is the common vertex for three
quadrilaterals. The union of such three quadrilaterals give an
hexagon H with.8 the triple point inside connected to three
vertexes of H which are also triple junctions. The hexagon H
inheritates the natural orientation induced by compatible
positively oriented quadrilaterals that are incident at the triple
junction. If central triple junction is a right Y, then the central
junction is salient. Otherwise, i.e. if central point is an inverted
Y, then it corresponds to a corner of a concave region w.r.t. the
observer. Typical hall indoor scenes or piecewise linear
approach to baroque facades exhibit an alternant behaviour
between right and inverse Y junctions. The continuous or
alternant character between triple junctions provides tools to
connect local and global aspects. So, we obtain easily verifiable
criteria for an automatic interpretation of the scene w.r.t. the
observer's viewpoint. Intersections of perspective lines
determine a structure given by convex quadrilaterals, which are
automatically superimposed to each image. For each pair of
Internation
Jag iii
vanishing p
this map i:
perspective
vanishing [
quadrilatera
perspective
coarse man
flat walls
quadrilatera
the alternan
Baroque St;
The solutio
onto the ma
241 Au
models
The interse
through tw
quadrilaters
perspective
quadrilatere
external prc
by the diffe
diagonal. 1
depending
Each map
from persp
grouping a
optimizatio
of bilinear
similarity re
propagation
between cat
can be perfi
we obtain tl
between the
non-aligned
algebraicall
vanishing [
vector field
each map o
the support
fields whos
transformat
performed |
the vector
vanishing [
each view 1
product of 1
universal €
orthogonal
ordinary sp
reading — tl
transformat
The prograi
and visuali
geometrical
friendly cor
several ima;
