). In this 
undaries 
Canny's 
id apply 
to the 
'ctances, 
1 for the 
n easily 
'ojection 
a coarse 
asier to 
ll errors 
mination 
obtained 
generate 
ints) by 
f central 
sections 
rmine a 
raced to 
to work 
ures, by 
ive us a 
“the 3D 
ondence 
is based 
sed onto 
| in pairs 
images. 
linearity 
occluded 
uple the 
re of 3D 
on the 
long the 
d out to 
s which 
omputer 
Ber97]). 
because 
graphies 
ws. The 
/deletion 
mentary 
to the 
a simple 
raph Gr 
nd their 
riangles. 
folds the 
ith the 
ation of 
y are no 
je image 
cclusion 
ed than 
in above 
ts along 
jents are 
inserted/deleted by modifying the corresponding graph 
associated by using adjacency relations in the same way as for 
the Delaunay graph. Thus, the insertion of a new segment 
generates at most three new regions which are represented in the 
updated graph as a ternary unfolding of the original graph. 
3. Trapezoidal maps for grouping 
We have focused towards an automatic generation of robust 
grouping criteria onto each image, instead of using more 
traditional comparisons between successive images with 
epipolar constraints. Grouping criteria are represented by 
bilinear incidence conditions linked to deformed rectangles with 
an apparent motion. Hence, our emphasis is put directly onto 
shear transformations involving the projection of rectangular 
regions in the world. Redundant information linked to the 
estimation of trapezoids supporting geometric transforms is 
robust. Furthermore, it allows us to maintain incidence and 
adjacent constrains with an easy discrimination between interior 
and exterior regions w.r.t. reference lines. 
To avoid an excessive number of triangles with abrupt changes 
in the depth, we have adapted the trapezoidization algorithm 
described in [Ber97] by including degenerate cases. Main 
restrictions for the selected data concern to the length and 
orientation of segments. Such restrictions allow us to simplify 
the treatment of meaningful information as much as possible. In 
this way, we obtain less regions than for the original algorithm 
described in [Ber97]. This lower number of candidates 
simplifies the local grouping and the global generation of coarse 
perspective models. 
The insertion/deletion of segments plays the role of elementary 
events, and it allow us to update the available information 
associated to a trapezoidal graph. The symbolic representation 
associated to such a graph plays the same role as the Delaunay 
graph linked to a triangulation. To accelerate the comparison 
between trapezoidal maps associated to a sequence of views, we 
reduce ourselves to the study of complete trapezoids inside a 
vanishing cone Cy associated to the projection lines with vertex 
the vanishing point py. Such cone is symmetric w.r.t. to the 
horizontal vanishing line /oo 
The lack of symmetry w.r.t. the perpendicular to the vanishing 
line through the vanishing point give us information about the 
relative orientation of the platform w.r.t. 
the lateral walls. The relative orientation is evaluated in terms of 
the ratios between homologue trapezoidal regions located at left 
and right sides of the perpendicular. Let us see how to manage 
such trapezoidal regions. 
We construct 7rapezoidal maps as a mid-level grouping after 
generating a coarse perspective model for the scene without 
reconstruction. Let us see some details. We decompose our 
construction in the following steps: initialization, tracking of 
homologue elements, propagation, prediction and errors 
estimation. The main novelty concerns to the homologue 
elements which are not points, not even segments, but 
trapezoidal regions. In our case, the reduction to the 1- 
dimensional case is possible thanks to trapezoids have always 
two vertical segments. Hence, it suffices to evaluate how 
trapezoids are stretching, decomposing or grouping following a 
list of easily updatable events. Let us see how to initiate the 
process. 
Canny's minisegments are grouped according to collinearity 
constraints giving a collection of vertical large segments. Skew 
projection lines are obtained by applying a regression technique 
to the extremes of large segments. Next, we compute the 
pairwise intersections of projection lines. By using a weighted 
average for such six intersections around the vanishing line, we 
determine the vanishing points and retrace some "virtual" 
projection lines starting from the computed vanishing points. 
The intersection of such virtual projection lines with the upper 
and lower boundaries of the image determine a light cone C. 
We construct a trapezoidal map inside the cone of light (by 
adapting [Ber97]). Elementary events are given by meaningful 
segments. The trapezoidal map is easily updated in an 
incremental way by inserting/deleting trapezoids associated to 
elementary events given by segments. The splitting/grouping 
process arising from such updating can be described by an 
algorithm with a linear complexity in the number of elementary 
events. 
Some references 
[Agu01] S.Aguilar and M.J.Antolínez: "Estimación del 
movimiento aparente a partir del análisis de escenas 
estructuradas de interior", Master's thesis, Univ. of Valladolid, 
2001. 
[Avi00] S.Avidan and A.Shashua: "Trajectory triangulation: 
3D reconstruction of moving points from a monocular image 
sequence", IEEE Transactions on Pattern Analysis and Machine 
Intelligence, 22(4), 348-357, 2000. 
[Ber97] M.de Berg, M.Van Kreveld, M.Overmars, and O. 
Schwarzkopf: "Computational Geometry. Algorihtms | and 
Applications", Springer-Verlag, 1997. 
[Coe92] C.Coelho, A.Heller, J.L.Mundy, D.A.Forsyth and 
A.Zisserman: "An Experimental Evalaution of Projective 
Invariants", in J.L.Mundy and A.Zisserman (eds): "Geometric 
Invariance in Computer Vision", The MIT Press, 87-104, 1992. 
[Fau93] O.Faugeras: "Three-dimensional computer vision", The 
MIT Press, Cambridge, MA, 1993. 
[Har00] R.Hartley and A.Zisserman: "Multiple View 
Geometry", Cambridge Univ. Press, 2000. 
[Hor81] B.K.P.Horn and B.G.Schunk: "Determining Optic 
Flow", Artificial Intelligence 17, 185-203, 1981. 
[Ma98] Y.Ma, J.Kosecka and S.Sastry: "Motion Recovery from 
Image Sequences: Discrete Viewpoint vs. Differential 
Viewpoint", Computer Vision, ECCV'98, 5th European 
Conference on Computer vision, Vol.II, LNCS 1407, 337-353, 
1998. 
[SGB98] M.C.Shing, D.B.Goldgof and K.W.Bowyer: "An 
objective methodology of edge detection algorithms using a 
structure from motion task", Proc. of the IEEE Intl Conference 
CVPR, 1998. 
[Tia96] T.Y.Tian, C.Tommasi and D.J.Heeger: "Comparison of 
Approaches to Egomotion Computation", Computer Vision and 
Pattern Recognition, IEEE, 315-320, 1996 
[Zha92] Z.Zhang and O.Faugeras: Springer-Verlag, 1992. 
—151—