3. Superimposed geometric structures for relative 
localization. The static approach 
The high complexity of information contained in a view 
suggests to superimpose geometric structures as the support of a 
symbolic representation. Following a static approach based on a 
dense map of points (Voronoi sites), traditional Voronoi 
diagrams or their dual Delaunay triangulations ([Ber97], 
[Kre97]) provide an irregular tessellation linked to influence- 
regions or optimality properties. Irregular tessellations provide a 
metrical hierarchised representation with their corresponding 
structures of nearest neighbourhoods and cellular subdivisions. 
Metric structures allow to superimpose criteria for topological 
properties such as the connectivity index, i.e. the number of 
connected regions linked which are adjacent to a fixed one. This 
information simplifies the query procedures to find meaningful 
data for the relative localization, which are very important for 
the assistance with applications to automatic searching 
procedures or optimal resources allocation. Triangular Delaunay 
decompositions are better suited than convex Voronoi 
decompositions to update mobile information by simple 
subdivision or regrouping. Indeed, triangulations are based on 
split-and-merge algorithms which are easier to implement and 
to update than mobile Voronoi diagrams. In despite of the 
precision of triangular decompositions, the mise in 
correspondence between homologue elements is time 
consuming, and some coarser approach can be more useful for 
on-line applications. 
Stereo matching requires at least four points not so far between 
them. Four points in the image generate a quadrilateral, which is 
used to patch together different views in a panoramic view after 
a rectification ([Har00]). We restrict ourselves to convex 
quadrilaterals. Usual method to construct small homographies 
in Stereo Vision is based on triangular decompositions. To 
compare triangulations corresponding to different aerial or 
satellite views, it is convenient to perform a rectification 
([Har00]). Nevertheless the accuracy and easy use of triangular 
decompositions, the information relative to 1D data contained in 
contours is often ignored. This information can be incorporated 
by means a trapezoidization algorithms based on detection of 
large segments inside the view (besides some threshold). 
Trapezoidization can be refined to give triangulations, but with 
some edges labelled as true segments meaningful for the image 
analysis. Trapezoidization are obviously compatible with 
triangular decompositions, and the method of small 
homographies is also applied, but with a redundant condition 
which is automatically solved by means of a simple 
optimisation procedure between the candidate to homologue 
vertices in rectified adjacent views. 
4. Correspondence between sampled images. 
The quasi-static case 
The mise-in-correspondence between common data belonging 
to a sequence of views is a highly complex task which can be 
simplified if we have an easily updateable reference pattern 
based on the selection and tracking of homologue points along a 
sequence of views. A structural approach to this problem is 
based on the Epipolar restriction ([Har00]) applied to a 
perspective model. Usual approach is based on the method of 
small planar homographies supported onto triangles whose 
vertices are located to a similar depth. Traditional algorithms 
use the correspondence between pairs of homologue triangles 
along a sequence of views. The automatic identification of 
homologue triangles is far from being trivial due to variations in 
depth. However, for aerial or satellite images differences in the 
relative depth can be forgotten. The main problem concerns to 
the accumulation of errors arising form relative positioning, 
which can give meaningful errors for the evaluation of relative 
movement. To avoid such errors one can use absolute 
positioning based on landmarks on the terrain or the 
determination of the absolute conic ([Har00]) for metric 
information. Orthographic projections play a privileged role as 
reference images to obtain structure from motion. 
Modern radargrammetric or satellite views perform a sweep of 
regions. Following our approach, we superimpose a sequence of 
2D convex quadrilaterals to central regions. There exist 
different rectification methods which transform quadrilaterals in 
rectangles associated to an orthogonal projection, as the frames 
would be taken in a fronto-parallel view, always ([Har00]). 
These methods provide a common pattern to compare different 
views, provided we have some information about parallel lines. 
Vertices of quadrilaterals are selected as multiple (triple or 
quadruple) junctions, in such way that resulting quadrilaterals 
are empty (there are no other quadruple junction inside). So, we 
have a stable structure which is not involved by perspective 
changes. Next, we take quadrilaterals to compare (and 
eventually to patch together) pairs of successive images. To 
each positively (i.e. counterclockwise) oriented quadrilateral we 
associate its oriented area given as: 
A(ABCD) = ; (AB + DC) A BD = : (AB + DC) A AC 
Next, we compute the affine transformation between homologue 
quadrilaterals. The automatic choice of homologue 
quadrilaterals is based on the Epipolar Geometry ([Har00]). The 
identification of epipoles in the image plane imposes strong 
conditions about the localization of homologue elements along a 
sequence of views. A general affine transformation is 
determined by six parameters. The translation vector 
corresponds to the displacement of the centre of gravity of 
homologue regions; it is easily computed from a standard 
navigation system giving the changes every second of latitude 
and longitude coordinates. A simple computation of parameters 
shows that we need at least six normal flow vectors. Hence, we 
take two pairs of homologue quadrilaterals with a common 
edge. So, the (pairs of adjacent) homologue quadrilaterals 
provide a geometric support for bilinear forms which give an 
algebraic expression to the transformation between sampled 
near frames. A voting scheme about the differences between 
normalized oriented areas of homologue quadrilaterals 
contained in two views gives an unbiased estimator of the 
angular velocity. 
The automatic management of the superimposed quadrilateral 
structure is performed by a local trapezoidal map. Trapezoids 
are obtained from a sweep performed along two orthogonal 
directions which are associated to the orthogonal view. So, we 
prevent degenerate situations linked to lines parallel to the 
sweep line. Conflicts in data structures are solved by discarding 
degenerate situations linked to the presence of a segment 
parallel to the sweep line. 
5. Multiobjective Optimisation 
There exist two main approaches to multiobjective optimisation 
problems which are labelled as Min-max formulation and the 
method of objective weights. The second method is based on 
the selection able of weights to minimize an energy functional 
which is usually given by a weighted combination of L'- and L7- 
norms which can be interpreted as the usual potential and 
-498—