\documentstyle[jair,twoside,11pt,theapa]{article}
\input epsf %% at top of file

\jairheading{3}{1995}{325-348}{5/95}{12/95}
\ShortHeadings{Vision-Based Road Detection}
{Alberto Broggi, Simona Bert\`e}
\firstpageno{325}

\begin{document}

\title{Vision-Based Road Detection in Automotive Systems:\\ a Real-Time
Expectation-Driven Approach}

\author{\name Alberto Broggi \email broggi@ce.unipr.it \\
        \name Simona Bert\`e \email simona@ce.unipr.it \\
       \addr Dipartimento di Ingegneria dell'Informazione\\
       Universit\`a di Parma\\
       Viale delle Scienze\\
       I-43100 Parma, Italy}

% For research notes, remove the comment character in the line below.
% \researchnote

\maketitle

%\newcommand{\I}{{\cal I}}
%\newcommand{\W}{{\cal W}}
%\newcommand{\Cdot}{~}


\begin{abstract}
The main aim of this work is the development of a 
vision-based road detection system fast enough to cope with the
difficult
real-time constraints imposed by moving vehicle applications.
The hardware platform, a special-purpose massively parallel system, has
been chosen to minimize system production and
operational costs.

This paper presents a novel approach to expectation-driven low-level
image segmentation, which can be mapped naturally onto
mesh-connected massively parallel {\sc Simd} architectures capable of handling
hierarchical data structures.
The input image is assumed to
contain a distorted version of a given template; a multiresolution
stretching process is
used to reshape the original template 
in accordance with the 
acquired image content, minimizing a potential function.
The distorted template is the process output.
\end{abstract}




%%\makeatletter
%%\newcommand{\singlespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1}\tiny\CS}
%%\newcommand{\doublespacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{1.5}\tiny\CS}
%%\newcommand{\normalspacing}{\let\CS=\@currsize\renewcommand{\baselinestretch}{\BLS}\tiny\CS}
%%\makeatother

\newcommand{\eg}{\`{e}\ }
\newcommand{\Eg}{\`{E}\ }
\newcommand{\ea}{\'{e}\ }
\newcommand{\ag}{\`{a}\ }
\newcommand{\Ag}{\`{A}\ }
\newcommand{\og}{\`{o}\ }
\newcommand{\ug}{\`{u}\ }
\newcommand{\ig}{\`{\i}\ }
\newcommand{\ia}{\'{\i}\ }
\newcommand{\bary}{\begin{array}}
\newcommand{\eary}{\end{array}}
\newcommand{\bde}{\begin{description}}
\newcommand{\ede}{\end{description}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqy}{\begin{eqnarray*}}
\newcommand{\eeqy}{\end{eqnarray*}}
\newcommand{\bcen}{\begin{center}}
\newcommand{\ecen}{\end{center}}
\newcommand{\bfig}{\begin{figure}}
\newcommand{\efig}{\end{figure}}
\newcommand{\bit}{\begin{itemize}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\vs}{\vspace{7mm}}
\newcommand{\ds}{\displaystyle}
\newcommand{\frat}[2]{\frac{\textstyle #1}{\textstyle #2}}
\newcommand{\ms}{\,\,}
\newcommand{\dst}{{\rm d}}
\newcommand{\cpxrct}{\cpx_{\rm RCT}}
\newcommand{\cpx}{{\cal C}}
\newcommand{\ovr}{{\cal O}}
\newcommand{\fram}{{\cal F}}
\newcommand{\origin}{$\hspace{-3pt}\raisebox{-2.9pt}{$\rightarrow$}\hspace{-12pt }\uparrow\hspace{0pt}$}
%\newcommand{\origin}{$\;\!\!\!\!\rightarrow\!\!\!\!\!\!\:\uparrow\!\!$}
\newcommand{\uno}{$\!\!\bullet\!\!$}
%\newcommand{\zero}{$\!\!\circ\!\!$}
\newcommand{\zero}{$\!$}
\newcommand{\dilat}{\oplus}
\newcommand{\eros}{\ominus}
\newcommand{\match}{\oslash}
\newcommand{\open}{\circ}
\newcommand{\close}{\bullet}
\newcommand{\masker}{\odot}
\newcommand{\define}{\stackrel{{\Delta}}{=}}



%\doublespacing

\section{Introduction}

The work discussed in this paper
forms part of the Eureka {\sc Prometheus} activities, aimed at
improved road traffic safety.  
Since the processing of images is of fundamental importance in automotive 
applications, our current work has been aimed at the development of an
embedded low-cost {\em computer vision} system.
Due to the special field of application, the
vision system must be able to process data and produce results in
real-time.  It is therefore necessary to consider data structures, processing
techniques, and computer architectures capable of reducing
the response time of the system as a whole.

The system considered is
currently integrated on the {\sc Mob-Lab} land vehicle~\cite{laplante}.
\bfig[htb]
\centerline{
\epsfxsize=11cm
\epsffile{moblab.ps}
\hfill
\epsfxsize=4.83cm
\epsffile{controlpanel.ps} }
\caption{(a) The {\sc Mob-Lab} land vehicle;
(b) the control panel used as output to display the processing results
\label{MOBLAB}}
\efig
The MOBile LABoratory, the result of Italian
work within the {\sc Prometheus} project (see Figure~\ref{MOBLAB}.a),
comprises a camera 
for the acquisition and digitization of images, which pipelines
data to an on-board massively parallel
computer for processing. As illustrated in Figure~\ref{schema},
the current output configuration comprises a set
of warnings to the driver, displayed by means of a set of {\sc Leds}
on a control-panel (shown in Figure~\ref{MOBLAB}.b). But,
due to the high performance levels achieved,
it will be possible to replace this output device with a heads-up 
display showing the enhanced features superimposed onto the original image.


%\bfig[htb]
%\centerline{
%\epsfxsize=14cm
%\epsffile{schema_r1.eps}  }
%\caption{Block diagram of the complete system\label{schema}}
%\vspace{-9.15cm}
%\hspace{-0.3cm}
 %\hspace{0.85cm}
%\epsfxsize=2cm
%\epsffile{images/input19.ps}
%\hspace{9.55cm}
%\epsfxsize=2cm
%\epsffile{images/bordi19.ps}
%\vspace{3.4cm}
%
%\hspace{8.0cm}
 %\hspace{0.85cm}
%\epsfxsize=2cm
%\epsffile{images/sovrapp19.ps}
%\vspace{1.5cm}
%\efig

\bfig[htb]
\centerline{
\epsfxsize=14cm
\epsffile{cvsystem-bw.eps}  }
\caption{Block diagram of the complete system: (a) planned heads-up display
output and (b) current {\sc Led}-based output
\label{schema}}
\efig





This paper presents a move toward the use
of {\em top-down} control (the following feature extraction mechanism
is based on a {\em model-driven} approach), instead of the traditional {\em
data-driven} approach, which is generally used for data-parallel algorithms.

Starting from the experience gained in the development of a 
different approach \cite{ieee.ip} based on the parallel
detection of image
edges pointing to the Focus of Expansion, this work presents
a {\em model-driven}
low-level processing technique aimed at road detection and enhancement of the
road (or lane) image acquired from a moving vehicle.
The model which contains {\em a-priori knowledge} of the feature
to be extracted (road or lane) is encoded in the
traditional data structure handled in low-level processing: a
two-dimensional array.  In this case, a binary
image representing two different regions
(road and off-road) has been chosen.  
Hereinafter this image will be referred to as {\em Synthetic Image}.
It is obvious that different synthetic images must be used according to
different acquisition conditions (camera position, orientation,
optics, etc., which are fixed) and environment (number of lanes,
one way or two way traffic, etc., which may change at run-time). 
In the final system implementation some {\em a-priori} world knowledge 
enables the correct synthetic model selection.
As an example, Figure~\ref{dis00} presents several
different synthetic images for different conditions.
\bfig[htb]
\centerline{
\epsfxsize=14.5cm
\epsffile{synthimgs.eps}  }
\caption{Synthetic images used as road models for: {\em (a)}
different camera positions and/or
orientations {\em (b)} different number of lanes (assuming 
driving on the right) \label{dis00}}
\efig

The following Section presents a survey of vision-based lane detection
systems; Section 3
explains the choice of the multiresolution approach;
Section 4 presents the details of the complete algorithm;
Section 5 discusses the performances of current implementation on the
{\sc Paprica} system; Section 6 presents some results and a critical analysis
of the approach which leads to the present development;
finally Section 7 presents some concluding remarks.




\section{Comparison with Related Systems}

Many different vision-based road detection systems have been developed
worldwide, each relying on various characteristics
such as different road models (two or three dimensional), 
acquisition devices (color or monochromatic camera, using 
mono or stereo vision), hardware systems (special- or 
general-purpose, serial or parallel), and computational techniques
(template matching, neural networks, etc.).

\bit
\itemsep -1mm
\item 
The {\sc Scarf} system (tested on the {\sc Navlab} vehicle at Carnegie Mellon
University) uses two color cameras for color-based image segmentation;
the different regions are classified and grouped together to form larger
areas; finally a Hough-like transform is used to vote for different
binary model candidates.
Due to the extremely high amount of data to be processed, the
two incoming color images ($480\times512$) are reduced to $60\times64$ pixel.
Nevertheless, a high performance computer architecture, a 10 cell Warp
\cite{warpieee,warp2,warp}, has been chosen to speed-up the
processing. The system, capable of detecting even unstructured roads,
reaches a processing rate of $\frac{1}{3}$~Hz 
\cite{scarf,unscarf,cmucap2,thorpe.delft}.
In addition to 
its heavy computational load, the main problems with this approach
are found in the implicit models assumed:
if the road curves sharply or if it changes
width, the assumed shape model becomes invalid and detection
fails \cite{cmumodels}.

\item The {\sc Vits} system (tested on the {\sc Alv} vehicle and
developed at Martin Marietta) also relies on two color cameras.
It uses a combination of
the red and blue color bands to segment the image, in an effort to reduce
the artifacts caused by shadows.
Information on vehicle motion is also used to aid the segmentation process.
Tested successfully on straight, single lane roads, it runs faster than
{\sc Scarf}, sacrificing general capability for speed \cite{turk}.

\item {\sc Alvinn} (tested on {\sc Navlab}, {\sc Cmu})
is a  neural network based
$30\times32$ video retina designed, like {\sc Scarf},
to detect unstructured roads,
but it does not have any road model: it learns associations
between visual patterns and steering wheel angles, without considering
the road location.
It has also been implemented on the Warp system, reaching 
a processing rate of about 10~Hz \cite{alvinn,pomerleau,cmunn}.

\item A different neural approach has been developed at {\sc Cmu} and tested on
{\sc Navlab}:
a $256\times256$ color image is segmented on a 16k processor MasPar
MP-2 \cite{maspar}. A trapezoidal road model is used, but the road
width is assumed to be constant throughout the sequence: this means
that although the trapezoid may be skewed to the left or right,
the top and bottom edges maintain a constant length.
The high performance offered by such a powerful hardware
platform is limited by its low I/O bandwidth; therefore a simpler reduced
version (processing $128\times128$ images) has been implemented, working
at a rate of 2.5~Hz \cite{navlab}.
\eit

Due to the high amount of data (2 color images) and to the complex
operations involved (segmentation, clustering, Hough transform, etc.) the
system discussed, even if implemented on extremely powerful hardware
machines,
achieve a low processing rate.
Many different methods have been considered to
speed-up the processing, including the processing of monochromatic images and
the use of windowing techniques \cite{turk} to process only the regions
of interest, thus implementing a Focus of Attention mechanism \cite{wolfe,neu}.

\bit
\itemsep -1mm
\item As an example, in {\sc VaMoRs} (developed at
Universit\"at der Bundeswehr, M\"unchen)
monochromatic images are processed by custom hardware, focusing only on the
regions of interest \cite{vamors}.
The windowing techniques are supported by
strong road and vehicles models to predict features
in incoming images \cite{dickmans92}. In this case, the vehicle was
driven at high speeds (up to 100~kph) on German autobahns, which have
constant lane width, and where the road has specific shapes: straight,
constant curvature, or clothoidal. The use of a single monochromatic camera
together with these simple road models 
allows a fast processing based on simple edge detection; a match with a
structured road model is then used to discard anomalous edges.
This approach is disturbed in
shadow conditions, when the overall illumination changes, or when
road imperfections are found \cite{cmumodels}.

\item The {\sc Lanelok}
system (developed at General Motors) also relies on strong
road models: it estimates the location of lane boundaries with a curve
fitting method \cite{lanelok1,lanelok2,lanelok3}, using a quadratic
equation model.
In addition to being disturbed by the presence of vehicles close to the road
markings, lane detection generally fails in shadow conditions. 
An extension for the correct interpretation of shadows has therefore been
introduced \cite{lanelokombre}; unfortunately this technique relies on
fixed brightness thresholds which is far from being a robust and general
approach.
\eit


The main aim of the approach discussed in this paper, on the other hand,
is to build a
{\em low-cost} system capable of achieving {\em real-time} performance
in the detection of {\em structured} roads (with painted lane markings),
and robust enough to tolerate severe illumination changes such as {\em
shadows}. Limitation to the analysis of structured environments
allows the use of simple road models which, together with
the processing of monocular
monochromatic images on special-purpose hardware allows the achievement of
low-cost high performances.
The use of a high performance 
general-purpose architecture, such as a 10 cell Warp or a 16k MasPar
MP-2 (as in the case of Carnegie Mellon's {\sc Navlab}), involves high
costs which are not compatible with
widespread large-scale use.  It is for this
reason that the execution of low-level computations
(efficiently performed by massively parallel systems)
has usually been implemented on general purpose processors, as in the case of
{\sc VaMoRs}. 
The design and implementation of special-purpose application-oriented
architectures (like {\sc Paprica}, Broggi, Conte, Gregoretti, Sanso\`e,
\& Reyneri, 1995, 1994), on the other
hand, keep the production costs down, while
delivering very high performance levels.
More generally, the features that enable the integration of
this architecture on a generic vehicle are:
\bit
\itemsep -1mm
\item[{\em (a)}] its low production cost, 
\item[{\em (b)}] its low operational cost, and 
\item[{\em (c)}] its small physical size.
\eit


\subsection{The Computing Architecture}

Additional considerations on power consumption show that
mobile computing
is moving in the direction of massively parallel architectures comprising
a large number of relatively slow-clocked processing
elements.
The power consumption of dynamic systems
can be considered proportional to $C f V^2$, where
$C$ represents the capacitance of the circuit, $f$ is the clock
frequency, and $V$ is the voltage swing.
Power can be saved in three different ways \cite{mobilecomputing},
by minimizing $C$, $f$, and $V$ respectively:
\bit
\itemsep -1mm
\item using a greater level of {\sc Vlsi} integration,
thus reducing the capacitance $C$;
\item trading computer speed (with a lower clock frequency $f$)
for lower power consumption (already
implemented on many portable PCs);
\item reducing the supply voltage $V_{DD}$.
\eit

Recently, new technological solutions have been
exploited to reduce the IC supply voltage from 5~V to 3.3~V.
Unfortunately, there is a speed penalty to pay for this reduction:
for a {\sc Cmos} gate \cite{cmos}, the device
delay $T_d$ (following a first order approximation)
is proportional to
$\frat{V_{DD}}{\left(V_{DD}- V_T\right)^2}$, which shows that
the reduction of $V_{DD}$ determines a quasi-linear increment (until the
device threshold value $V_T$) of the circuit delay $T_d$.
On the other hand, the reduction of $V_{DD}$ determines a quadratic
reduction of the power consumption.
Thus, for power saving reasons, it is desirable
to operate at the lowest possible speed, but, in order
to maintain the overall
system performance, compensation for these increased delays is required.

The use of a lower power supply voltage has been investigated
and different architectural solutions have been considered so as to overcome
the undesired side effects caused by the reduction of $V_{DD}$
\cite{lavagno,lavagno.ieee}.
The reduction of power
consumption, while maintaining computational power, can be achieved
by using low cost {\sc Simd} computer architectures,
comprising a large number of extremely simple and
relatively slow-clocked processing elements.
These systems, using slower device speeds,
provide an effective mechanism for
trading power consumption for silicon area,
while maintaining the computational
power unchanged. The 4 major drawbacks of this approach are:
\bit
\itemsep -1mm
\item a solution based on
hardware replication increases the silicon area, and
thus it is not suitable for designs with extreme area constraints;
\item parallelism must be accompanied by extra-routing, requiring
extra-power; this issue must be carefully considered and optimized;
\item the use of parallel computer architectures involves the
redesigning
of the algorithms with a different computational model;
\item since the number of processing units must be high, if the system
has size constraints the processing elements must be extremely simple,
performing only simple basic operations.
\eit
This paper investigates a novel approach to real-time road following
based on the use of low-cost
massively parallel systems and data-parallel algorithms.



\section{The Multiresolution Approach}

The image encoding the model ({\em Synthetic Image}) and the image 
from the camera ({\em Natural Image}) cannot be directly compared with
local computations, because the latter contains much more detail than
the former.  From all the known methods used to decrease the presence
of details, it is necessary to choose one that does not decrease the
strength of the feature to be extracted.  For this purpose, a low-pass
filter, such as a $3\times3$ neighborhood-based anisotropic
average filter,
would not only reduce the presence of details, but
also the sharpness of the road boundaries, rendering their detection 
more difficult.  Since the road boundaries
exploit a long-distance correlation, a subsampling of both the natural
and the synthetic image would lead to a comparison which was 
less dependent on
detail content.  More generally, it is much easier to detect large
objects at a low resolution, where only their main characteristics are
present, than at a high resolution, where the details of the specific
represented object can make its detection more difficult.
The complete recognition and description process, on the other hand,
can only take place
at high resolutions, where it is possible to detect even small details
because of the preliminary results obtained at a coarse
resolution.

These considerations lead to the use of a pyramidal data
structure \cite{rosenfeld.pyr,ball-brown,TanimotoKilger},
comprising the same image at
different resolutions. Many different architectures have been
developed recently to support this computational
paradigm~\cite{cantoniferretti,papiaold,fountain,CantoniLevialdi}: where
the computing architecture contains a number of
processing elements which is smaller than the number of image pixels and an
external
processor virtualization mechanism~\cite{ischia} is used. A useful
side effect due to resolution reduction is a decrease in
the number of computations to be 
performed.
Thus, the choice of a pyramidal computational paradigm,
in addition to being supported by theory, offers an
advantage in terms of computational efficiency.

\section{Algorithm Structure}

As shown in Figure~\ref{dis1}, before each subsampling the natural
image is filtered.  In this way it is possible to decrease both the
influence of noise and redundant details, and the distortion due to
{\em aliasing} \cite{pratt} introduced by the subsampling process.
The image is partitioned into non-overlapping square subsets of 
$2\times2$
pixels each; the filter comprises a simple average
of the pixels values for a given subset, which reduces
the signal bandwidth.  The set
of resulting values forms the subsampled image.


\bfig
\centerline{
\epsfxsize=15cm
\epsffile{dis1_r1.eps}  }
\caption{Block diagram of the whole algorithm; for each step the depth
of every image is shown (in bit/pixel)\label{dis1}}
\efig

The stretching of the synthetic image is performed through an iterative
algorithm
({\em Driven Binary Stretching}, {\sc Dbs}), a much simpler and
morphological \cite{haralick,serra} version of the ``snake'' 
technique \cite{activevision,cohen2,cohen1,kass}.
The result is then
oversampled, and further improved using the same {\sc Dbs} algorithm,
until the original resolution is reached. The boundary of the stretched
template represents the final result of the process.



\subsection {The DBS Filter}

The purpose of the {\sc Dbs} filter, illustrated in Figure~\ref{dis3},
is to stretch the binary input model
in accordance with the data encoded in the grey-tone natural
image and to produce a reshaped
version of the synthetic model as an output.

Usually the boundary of a generic
object is represented by brightness discontinuities in the image
reproducing it, therefore, in the first version,
the first step of the {\sc Dbs} filter
comprises an extremely fast and simple
gradient-based filter computed on the $3\times3$ neighborhood of each 
pixel. Then, as shown in
Figure~\ref{dis3}, a threshold is applied to the gradient image, in
order to keep only the most significant edges. The threshold value is 
now fixed, but its automatic tuning based on median filtering is 
currently being tested \cite{follitesi}. 
More precisely, two different threshold values 
are computed for the left and right halves of the image, in order to 
detect both road boundaries even under different 
illumination conditions.

\bfig[htb]
\centerline{
\epsfxsize=7cm
\epsffile{dis3_r1.eps}  }
\caption{Block diagram of the {\sc Dbs} filter \label{dis3}}
\efig

Since a 2D mesh-connected massively parallel architecture is used,  an
iterative algorithm must be performed in
order to stretch the synthetic model toward the positions encoded in
the thresholded image.
A further advantage of the pyramidal approach is that the
number of iterations required for successful stretching is low
at a coarse resolution since the image size is small; and 
again, only a few iterations are required for high-resolution 
refinement, due to the initial coarse low-resolution stretching.
Each border pixel of the synthetic image
is attracted towards the position of the
nearest foreground pixel of the thresholded image, as shown in
Figure~\ref{attract}. 
\bfig[htb]
\centerline{
\epsfxsize=14cm
\epsffile{attract.eps}  }
\caption{The attraction of the boundary pixels of the model (in grey)
toward the thresholded image (the rectangular contour): (a)
two-dimensional case; (b) monodimensional section\label{attract}}
\efig

For this purpose, a
scalar field $V$ is defined on $E^2$. 
Field~$V : E^2 \rightarrow E$,
links the position of each pixel $p \in E^2$ to a scalar value $V(p)
\in E$, which represents the {\em potential} associated to the pixel
itself.  The set of these values is encoded in a {\em potential} image.  The
difference $V(p) - V(q)$ represents the {\em cost} of moving pixel $p$
toward position $q$. The scalar field is defined in such a way that 
a negative cost corresponds to the movement toward the
nearest position of the foreground pixels $t_i$ of the thresholded
image. As a consequence, the iterative process is designed explicitly to
enable all the pixel
movements associated to a negative cost.

Thus, the value $V(p)$ depends on the minimum distance between
pixel $p$ and pixels~$t_i$:
\beq
V(p) = - \min_i \, d(p, t_i) \ms,
\eeq
where $d:E^2\times E^2 \rightarrow E$ represents the distance between
two pixels, measured with respect to a given metric.
In this case, due to the special simplicity of the implementation, a
{\em city block} ({\em Manhattan distance}) metric has been chosen (see
Figure~\ref{metric}).

\bfig[htb]
\centerline{
\epsfxsize=3cm
\epsffile{figM.eps}  }
\caption{{\em City block} or {\em Manhattan} distance from the central
pixel \label{metric}}
\efig

\noindent
A very efficient method for the computation of the potential
image using 2D mesh-connected architectures is based on the iterative
application of morphological dilations \cite{haralick,serra}:
\ben
\itemsep -1mm
\item a scalar counter is initialized to 0; for parallel architectures 
which cannot run any fragment of scalar code, this counter
is associated to every pixel in the image, thus constituting a ``parallel''
counter;
\item the counter is decremented;
\item the binary input image
is dilated using a 4-connected structuring
element $N$, formed by the following elements:

%\singlespacing
\beq
N = \Big\{ (0,1); (0,-1); (0,0); (1,0); (-1,0) \Big\} =
\makebox{
  {\scriptsize
    \begin{tabular}{|c|c|c|}
    \hline
    \zero & \uno & \zero \\
    \hline
    \uno  & \uno\origin & \uno \\
    \hline
    \zero & \uno & \zero \\
    \hline
    \end{tabular}
  }
}\ms;
\label{enne}
\eeq
%\doublespacing

\item the value of the counter is assigned to the potential image in the
positions where the pixel, due to the previous dilation, changes its
state from {\em background} to {\em foreground}.
\item the process is then repeated from step 2, until the output of the
morphological dilation is equal to its input.
\een

This shows that the potential image can be generated by the application of a
{\em Distance Transform}, {\sc DT} \cite{gunilla} to the binary
thresholded image.  Due to a more efficient implementation-dependent
data handling, the final version of the potential image {\sc DT} is obtained
by adding a constant $\lambda$ to every coefficient, so as to work
with only positive values: $\lambda$ represents the maximum value
allowed for grey-tone images\footnote{In this specific case, since
8-bit images are considered, $\lambda = 255$.}. Thus the new
definition of the scalar field $V$ is:
\beq
V(p) = \lambda - \min_i \, d(p, t_i) \ms.
\eeq

Furthermore, since the `distance' information is used only by
the pixels belonging to the border of the synthetic image and their
neighbors, the iterative process is stopped when the {\sc DT} has been
computed for these pixels, producing a noticeable performance improvement.

\bfig[t]
\centerline{
\epsfxsize=10cm
\epsffile{figx.eps}  }
\caption{Example of 4 iterations of the {\sc Dbs} algorithm (monodimensional
case) \label{figx}}
\efig

As already mentioned, the crux of the algorithm is an
iterative process whose purpose is to move the edge pixels of the
synthetic image in the directions in which the {\sc DT} gradient has a maximum.
Figure~\ref{figx} shows an example of a monodimensional stretching.
As shown in Appendix~A, the strength of this approach lies in the
fact that the stretching algorithm can be expressed simply by a sequence 
of morphological operations, and can 
therefore be mapped efficiently on mesh-connected massively parallel 
architectures, achieving higher performance levels than other 
approaches \cite{cohen2,cohen1,kass}.

In order to describe the {\sc Dbs} algorithm, let us introduce some
definitions using 
Mathematical Morphology operators \cite{haralick,serra} such as 
dilation ($\dilat$), erosion ($\eros$), or complement 
($\overline{\cdot}$).
A two-dimensional binary image $S$ is represented as a
subset of $E^2$, whose elements correspond to the {\em foreground}
pixels of the image:
  \beq
  S = \Big\{ s \in E^2 \,\, \Big\| \, \,  s=(x, y), \, \, x, y \in E
  \Big\} \ms,
  \eeq
where vector $(x, y)$ represents the coordinates of the generic element $s$.


The {\em external edge} of $S$ is defined as the set of elements 
representing the difference between $S$ and
the dilation of $S$ by the 4-connected structuring
element $N$ shown in expression~(\ref{enne}):
  \beq
  {\cal B}_{e}(S) = (S\dilat N) \cap \overline {S} \ms.
  \eeq
In a similar way, the set of elements representing the difference 
between $S$ and its erosion
using the same structuring element $N$ is defined to be the {\em
internal edge} of $S$:
  \beq
  {\cal B}_{i}(S) = \overline {(S \eros N)} \cap S \ms.
  \eeq
%% The logical union of ${\cal B}_{e}(S)$ and ${\cal B}_{i}(S)$ is the {\em
%% edge} of $S$:
%% 
%% \beq
%% {\cal B}(S) = {\cal B}_{e}(S) \cup {\cal B}_{i}(S) \ms.
%% \eeq

\subsubsection{The Iterative Rules}

The set of elements ${\cal B}(S) = {\cal B}_{e}(S) \cup {\cal B}_{i}(S)$
are the only
elements which can be inserted or removed from set $S$
by the application of a single iteration of the {\sc Dbs} algorithm.
More precisely, two different rules are applied to the two edges: the
first, applied to the external edge ${\cal B}_{e}(S)$, 
determines the elements to be
included in set $S$; while the second, applied to the internal edge
${\cal B}_{i}(S)$,
determines the elements to be removed from set $S$.
%\noindent
\bit
\item {\bf Rule for the external edge:}
\bit
\item each pixel of the external edge of $S$ computes the minimum value
of the {\sc DT} associated to its 4-connected neighbors belonging to set $S$;
\item all the pixels, whose associated {\sc DT} is greater than
the value previously computed, are inserted into set $S$.
\eit
The application of this rule has the effect of  expanding
the synthetic image towards the foreground pixels $t_i$ which are not
included in the synthetic model (see the right hand side of
Figure~\ref{attract}.b).
\item {\bf Rule for the internal edge:}
\bit
\item each pixel of the internal edge of $S$ computes the minimum value
of the {\sc DT} associated to its 4-connected neighbors not 
belonging to set $S$;
\item all the pixels, whose associated {\sc DT} is greater than the value
previously computed, are removed from set $S$.
\eit

The application of this rule has the effect of shrinking
the synthetic image (see the left hand side of Figure~\ref{attract}.b).
\eit

\noindent
Note that rule 2 is the inverse of rule 1: 
the latter tends to stretch the foreground onto the background, while
the former acts in the opposite way, using the complement of the
synthetic image.


\subsubsection{Flat Handling}

Figure~\ref{figx} refers to a monodimensional stretching.
Unfortunately, when dealing with 2D data structures, the
{\sc DT} image does not present a strictly increasing or decreasing
behavior, even locally.  Thus, an extension to the previous rules
must be considered for correct flat-handling in the 2D space.

\bfig
\centerline{
\epsfxsize=15cm
\epsffile{2d_r1.eps}  }
\caption{Two-dimensional stretching: different square markings represent 
different states of input binary image; dark grey areas represent the 
stretching area \label{2d}}
\efig

Figure~\ref{2d}.a shows the modulus of the {\sc DT} coefficients (in the case
of $\lambda=0$), together with the input binary image (shown
in grey).  The output of the iterative {\sc Dbs} algorithm 
is presented in Figure~\ref{2d}.b.

Since the movement of a generic pixel towards positions holding an
equal {\sc DT} coefficient is expressly disabled, the
resulting binary image does not completely follow the shape encoded in
the {\sc DT} image. A minor revision to the definition of rule 1
is thus required.
Figure~\ref{2d}.c is obtained  with the following rule applied to the
external edge.
\bit
\item {\bf Rule for the external edge, including flat handling:}
\bit
\item each pixel of the external edge of $S$ computes the minimum value
of the {\sc DT} associated to its 4-connected neighbors belonging to set $S$;
\item all the pixels, whose associated {\sc DT} is greater than
the value previously computed, and all the pixels not belonging
to the thresholded image, whose associated {\sc DT} is equal to the value
previously computed  are inserted into set $S$.
\eit
\eit

\noindent
The specific requirement for the pixels moving toward a flat region,
of not belonging to the thresholded image, ensures that the binary
image does not follow the {\sc DT} chain of maxima.  With such a
requirement, in the specific case of Figure~\ref{2d}, the maxima in the
upper-right hand area are not included in the resulting binary image.





\newcommand{\qua}{$^2$}
\newcommand{\frec}{$\rightarrow$}


\section{Performance Analysis of the Current Implementation\label{prfanl}}

Since the final aim of this work is to integrate the road 
detection system on a mobile vehicle, the main requirement is to achieve
real-time performance. The choice of a special-purpose massively 
parallel architecture has already been justified in Section~1; moreover, 
the algorithm discussed in this paper maps naturally onto a single-bit 
mesh-connected {\sc Simd} machine, because the whole computation can be 
efficiently expressed as a sequence of binary morphological operators,
as shown in
Appendix~A (which presents the morphology-based description of the 
whole {\sc Dbs} algorithm).


The complete processing, first tested on a Connection Machine 
{\sc CM}-2 \cite{hillis}, is now implemented on the special-purpose
massively parallel {\sc Simd} architecture {\sc Paprica}.
The {\sc Paprica} system (PArallel
PRocessor for Image Checking and Analysis),
based on a hierarchical morphology computational model,
has been designed as
a specialized coprocessor to be attached to a general purpose host workstation:
the current implementation, consisting of a $16\times16$ square array of 
processing units, is connected to a Sparc-based
workstation via a
{\sc Vme} bus, and installed on {\sc Mob-Lab}.
The current hardware board (a single {\sc 6U Vme} board integrating the
Processor Array, the Image and Program Memories, and a frame grabber
device for the direct acquisition of images for the {\sc Paprica} Image Memory)
is the result of the full reengineering of the
first {\sc Paprica} prototype
which has been extensively
analyzed and tested \cite{venezia} for several years.

The {\sc Paprica} architecture
has been developed explicitly to meet the 
specific requirements of real-time image processing
applications \cite{ieee.ip,rti,letoquet};
the specific processor virtualization mechanism 
utilized by {\sc Paprica} architecture allows the
handling of pyramidal data structures without any additional
overhead equipment.

As shown in Figure~\ref{schema}, the output device can be:
\ben
\itemsep -1mm
\item[(a)] a heads-up display in which the road (or lane)
boundaries are highlighted;
\item[(b)] a set of {\sc Leds} indicating the relative position of the road
(or lane) and the vehicle.
\een
Starting from $256\times256$ grey-tone images and after the resolution 
reduction process, in the first case (a) the initial resolution 
must be recovered
in order to superimpose the result onto the original 
image. In the second case (b), on the other hand, 
due to the high quantization of the output device,
the processing can be stopped at a low resolution (e.g., $64\times64$),
where only a stripe of the resulting image is analyzed to drive the {\sc
Leds}.
Table~\ref{algperf} presents the computational time required by each 
step of the algorithm (considering 5 {\sc DT} iterations and 5 {\sc Dbs} iterations 
for each pyramid level).

\begin{table}[htb]
\centerline{
\begin{tabular}{|l|c|c|c|}
\hline
Operation & Image size & Time [ms] \\
\hline
Resolution Reduction & 256\qua\frec32\qua &  149.70 \\
{\sc DT}, {\sc Dbs} \& Oversampling & 32\qua\frec64\qua  & 18.55 \\
{\sc DT}, {\sc Dbs} \& Oversampling & 64\qua\frec128\qua & 69.13 \\
{\sc DT}, {\sc Dbs} \& Oversampling & 128\qua\frec256\qua & 296.87 \\
%%%%{\sc DT}, {\sc Dbs}             & 256\qua\frec256\qua & 1038.58 \\
\hline
\hline
Total ({\sc Led} output) &    256\qua\frec32\qua\frec64\qua&  168.25\\
Total (heads-up display output)&    256\qua\frec32\qua\frec256\qua&  534.25\\
\hline
\end{tabular}
}
\caption{Performance of {\sc Paprica} system;
the numbers refer to 5 iterations of the {\sc DT} process 
and 5 iterations of the {\sc Dbs} filter for each pyramid level. \label{algperf}}
\end{table}
In the current {\sc Mob-Lab} configuration, the output device (shown in
Figure~\ref{MOBLAB}.b) consists of a 
set of 5 {\sc Leds}: Table~\ref{algperf} shows that
the $256^2 \rightarrow 32^2 \rightarrow 64^2$ filtering
of a single frame takes 150$\div$180~ms (depending on the number of
iterations required), allowing the acquisition and
processing of about 6 frames per second.

Moreover, due to the high correlation between two consecutive sequence
frames, the final stretched template can be used as the
input model to be stretched by the
processing of the following frame. In these conditions a lower number of
{\sc Dbs} and {\sc DT} iterations are
needed for the complete template reshaping,
thus producing a noticeable performance improvement. The reduction in the
time required to process a single frame also increases the
correlation between the current and the following frame in the sequence,
thus allowing a further reduction in computation time\footnote{In the
processing of highly correlated sequences (namely when the road
conditions change slowly or in an off-line slow-motion tape playback in
the laboratory)
the computational time required by the processing of a single
frame can reach a minimum value of 150 ms.}.

\input{fig10}

Images acquired in many different conditions and environments have been
used for extensive experimentation, which was
performed first off-line on a functional
simulator implemented on an 8k processor Connection Machine {\sc CM}-2
\cite{hillis}
and then in real-time on the {\sc Paprica} hardware itself on {\sc Mob-Lab}.
The complete system was demonstrated at the final 
{\sc Prometheus} project meeting in Paris, in
October 1994: the {\sc Mob-Lab} land vehicle
was driven around the two-lane track at Mortefontaine, under
different conditions (straight and curved roads, with 
shadows and changing illumination conditions
and with other vehicles on the path).

The performances obtained during this demonstration allowed
the main limitations of the system to be detected 
and enabled a critical
analysis of the approach, thus leading to proposals for its development.



\section{Critical Analysis and Evolution}


The approach discussed achieves good performances in terms of
output quality when the model matches (or is sufficiently similar to)
the road conditions, namely when road markings are
painted on the road surface (on structured roads, see Figures~\ref{figXok}.a
and~\ref{figXcurva}.a) inducing a sufficiently high luminance gradient.
This approach is successful when the road or lane boundaries can
be extracted from the input image through a gradient thresholding
operation (see Figures~\ref{figXok}.b and~\ref{figXcurva}.b). 
Unfortunately, this is not always
possible, for example when the road region is a patch of shadow or sunlight,
as in Figure~\ref{figXombre}.a.
In this case the computation of the {\sc DT} starting from the thresholded
image (see Figure~\ref{figXombre}.b)
is no longer significant: a different method must be devised for the
determination of the binary image to
be used as input for the Distance Transform.

\input{fig11}
\input{fig12}

In a recent work \cite{detroit} an approach
based on the removal of the perspective
effect is presented and its performances discussed. 
A transform, a non-uniform resampling similar to what happens in the
human visual system \cite{human,wolfe}, is applied to the input image
(Figures~\ref{figXreorg}.a); assuming a flat road, every pixel of the
resampled image (Figures~\ref{figXreorg}.b) now represent the same
portion of the road\footnote{Note that, due to the perspective effect,
the pixels in the lower part of the original image
(Figures~\ref{figXreorg}.a) represent a few cm$^2$ of the road region, 
while the central
pixels represent a few tens of cm$^2$. The non-uniform resampling of the
original image has been explicitly designed for a homogeneous
distribution of the information among all the pixels in the image.}.
Due to their constant width within the overall
image, the road markings can now be easily enhanced and extracted by
extremely simple
morphological filters~\cite{detroit} (Figures~\ref{figXreorg}.c).
Finally the perspective effect is reintroduced
(Figures~\ref{figXreorg}.d).



\input{fig13}

\input{fig14}

Due to the high effectiveness of this filter, 
in the test version of the system currently operational in
the laboratory, the {\sc Dbs} filter has been improved by replacing the gradient
thresholding with the perspective-based filter.
The {\em extended} version of the
{\sc Dbs} filter is shown in Figure~\ref{newDBS}.
\bfig[htb]
\centerline{
\epsfxsize=6cm
\epsffile{newDBS.eps}  }
\caption{Diagram of the extended {\sc Dbs} filter including the perspective-based
filtering\label{newDBS}}
\efig

Since the removal (and reintroduction) of the perspective effect can be
reduced to a mere image resampling and the filter 
is based on simple morphological operators~\cite{detroit}, the
implementation on the {\sc Paprica} system is straightforward. The preliminary
results obtained by
the current test version of the system 
are encouraging both for the output quality (the problems caused
by shadows
are now resolved) and for computation time:
a single frame is processed in less
than 100~ms, thus allowing the processing of about 10~frames per second.
The improvement of the {\sc Dbs} process
by means of the perspective-based filter, in addition to allowing correct
road (or lane) detection in presence of shadows, can be implemented
extremely efficiently on the {\sc Paprica} system,
taking advantage of a specific
hardware extension designed explicitly for this purpose (non
uniform-resampling) \cite{detroit}.

Figures~\ref{figXok}, \ref{figXcurva}, \ref{figXombre}, and
\ref{figXveicolo} show the results of the processing in different
conditions: straight and curved road, with shadows and other vehicles
in the path, respectively\footnote{
Some sequences in MPEG format (200 and 1000 frames respectively)
are available via World Wide Web at 
{\tt http://WWW.CE.UniPR.IT/computer\_vision}, 
showing lane detection in particularly challenging conditions. 
The images shown in
Figures~\ref{figXok}, \ref{figXcurva}, \ref{figXombre}, 
\ref{figXveicolo}, and \ref{figXroadlane} 
are part of the sequences available in
the previously mentioned WWW page.}.
In the last case the lane cannot be detected
successfully due to the presence of an obstacle


The use of a pair of stereo
images is currently being investigated to overcome this
problem: the removal of the perspective effect from both the 
stereo images would lead to the same image {\em iff} the road is
flat, namely if no obstacles are found on the vehicle path. A difference in the
two reorganized images (namely when an obstacle is detected) would
cause the algorithm to stop the lane detection and warn the driver.

The general nature of the presented approach enables the detection 
of other  sufficiently large-sized features: for example, using 
different synthetic models 
it is possible to detect road or lane boundaries, 
as shown in Figure~\ref{figXroadlane}.

\input{fig16}

\section{Conclusions}

In this paper a novel approach for the detection of road
(or lane) boundaries for vision-based systems
has been presented. The multiresolution
approach, together with top-down control, allows achievement of remarkable
performances in terms of both computation time (when mapped on 
massively parallel architectures) and output quality.

A perspective-based filter has been introduced to improve 
system performance in shadow conditions.
However, even if the perspective-based filter alone
is able to extract the road markings with a high degree of confidence, 
the hierarchical application of the {\sc Dbs}
filter (and its extension to the handling of image sequences) is of basic
importance since it allows the exploitation of the temporal correlation between
successive sequence frames (performing solution tracking).

The presence of an obstacle in the vehicle path is still an
open problem, which is currently being approached using stereo
vision \cite{detroit}.

The algorithm has been implemented on the {\sc Paprica} system, a massively
parallel low-cost {\sc Simd} architecture; because of its
specific hardware features, {\sc Paprica} is capable of processing
about 10 frames per second. 




\appendix

\section{The Morphological Implementation of the DBS Filter}

In this appendix, the rule for the external edge will be considered,
assuming step $n$ in the iterative process.  Recalling the
Mathematical Morphology notations used to identify a grey-tone
two-dimensional image, the {\sc DT} image is a subset of $E^3$:
  \beq
  DT = \{ d \in E^3 \,\, | \, \, d=(u, v), \,\, v = V(u), \,
  \, \forall \, u \in E^2\} \ms,
  \eeq
where $u$ represents the position of element $d$ in $E^2$, and $v$
represents its {\em value}.

The {\em pixelwise masking} operation between a binary and a grey-tone
image is here defined as a function
\beq
\masker : E^2 \times E^3 \rightarrow E^3
\eeq
such that $A \masker B$ represents a subset of $B$ containing only the
elements $b = (u, v)$ whose position vector $u \in E^2$ also belongs to $A$:
  \beq
  A \masker B \define \{ x \in E^3 \, \, | \, \, x = (u, v) \in B,
  \, u \in A\}
  \eeq
In order to compute the minimum value of the $DT$ in the specified
neighborhood, let us consider image~$K^{(n)}_{e}$
  \beq
  K^{(n)}_{e} = \Big (S_e^{(n)} \masker DT\Big) \cup \Big(\overline {S_e^{(n)}}
  \masker L \Big ) \ms,
  \eeq
where $S_e^{(n)}$ represents the binary image at step $n$, the
subscript $e$ indicates that the rule for the external edge is being considered, and
finally
  \beq
  L = \{ l \in E^3 \, \, | \, \, l = (u, \lambda), \, \, \forall \, u
  \in E^2\} \ms.
  \eeq
As shown in \cite{haralick}, in order to compute the minimum
value of a grey-tone image $K^{(n)}_{e}$ in a 4-connected
neighborhood, the following grey-scale morphological erosion should be
used:
  \beq
  M^{(n)}_{e} = K^{(n)}_{e} \eros Q \ms,
  \eeq
where
  \beq
  Q = \{(1,0,0); \, (-1,0,0); \, (0,1,0); \, (0,-1,0) \} \ms,
  \eeq
as shown in Figure~\ref{disQ}.

\bfig[htb]
\centerline{
\epsfxsize=12cm
\epsffile{figQ.eps}  }
\caption{Structuring element $Q$ \label{disQ}}
\efig

In order to determine the set of elements in which
$M^{(n)}_{e}$ has a value smaller than $DT$, a new
function ${\cal M}$ is required:
\beq
{\cal M} : E^3 \times E^3 \rightarrow E^2 \ms.
\eeq

\noindent
\bfig[htb]
\begin{minipage}[t]{9cm}
%\bcen
%\fbox[8cm][c]{
\epsfysize=10cm
\epsffile{mm2.eps}
%}
%\ecen
\end{minipage}
\hfill
\hspace{-1cm}
\begin{minipage}[t]{9cm}
%\bcen
%\fbox[8cm][c]{
\epsfysize=10cm
\epsffile{mm.eps}
%}
%\ecen
\end{minipage}
\caption{Monodimensional stretching in the case of external edge (left) 
and internal edge (right)\label{disxx}}
\efig

\noindent
Such a function is defined as
   \beq
   {\cal M} (A, B) \define \{ x \in E^2 \, \, | \, \, {\cal V } (A,
   x) < {\cal V } (B, x) \} \ms,
   \eeq
where  ${\cal V} : E^3 \times E^2 \rightarrow E$ is defined as
  \beq
  {\cal V} (A, x) \define \left\{ \begin {array}{ll}
  a & \mbox{${\rm if} \, \, \exists \, a \in E \, \, | \, \, (x, a) \in
  T(A)$} \\
  -\infty & \mbox{otherwise} \end{array}
  \right.
  \label{qwe}  \ms.
  \eeq
In equation~(\ref{qwe}), $T(A)$ represents the {\em top} of 
$A$ \cite{haralick},
here defined as
  \beq
  T(A) \define \{ t \in A, \, \, t=(u, v) \, \, | \, \,
  \not\exists \,\,  t^{\prime} = (x, v^{\prime}) \in A \, \,
  {\rm for} \, \, {\rm  which} \, \, v^{\prime} > v\}  \ms.
  \eeq
The set of elements which will be included in set $S_e^{(n+1)}$ is given by the
logical intersection between ${\cal M} (M^{(n)}_{e}, DT)$ and the set
of elements
belonging to the external edge of $S_e^{(n)}$:
   \beq
   E^{(n)}_{e} = {\cal M} \Big (M^{(n)}_{e}, DT\Big ) \cap {\cal B}_{e}
   \Big (S_e^{(n)}\Big )  \ms.
   \eeq
Thus, the final result  of iteration $n$ is given by
   \beq
   S_e^{(n+1)}  = S_e^{(n)} \cup E^{(n)}_{e}   \ms.
   \eeq
Figure~\ref{disxx}.a shows the execution of an individual iteration of rule 1
on a monodimensional image profile.

Following similar steps, it is possible to formalize rule 2.
In order to compute the maximum value of the $DT$ in the specified
neighborhood, let us consider image $K^{(n)}_{i}$
  \beq
  K^{(n)}_{i} = \overline {S_i^{(n)}} \masker DT  \ms,
  \eeq
where the subscript $i$ indicates that the rule for the internal edge
is being considered.  As shown above, in order to compute the maximum
value of a grey-tone image $K^{(n)}_{i}$ in a 4-connected
neighborhood, the following morphological dilation should be used:
  \beq
  M^{(n)}_{i} = K^{(n)}_{i} \dilat Q \ms,
  \eeq
where $Q$ is shown in Figure~\ref{disQ}.

The set of elements which will be removed from set $S_i^{(n+1)}$ is given
by the logical intersection between ${\cal M} (M^{(n)}_{i}, DT)$ and the
set of elements belonging to the internal~edge~of~$S_i^{(n)}$:
   \beq
   E^{(n)}_{i} = {\cal M} \Big (M^{(n)}_{i}, DT\Big ) \cap {\cal B}_{i}
   \Big (S_i^{(n)}\Big )   \ms.
   \eeq
Thus, the final result of iteration $n$ is given by
   \beq
   S_i^{(n+1)} = \overline{ \Big (\overline{S_i^{(n)}} \cup
   E^{(n)}_{i}\Big )} =
   S^{(n)}_{i} \cap \overline{E^{(n)}_{i}}   \ms.
   \eeq
Figure~\ref{disxx}b shows the execution of an individual iteration of rule 2
on a monodimensional profile of an image.


\acks{This work was partially supported by the Italian {\sc Cnr} within the
framework of the Eureka {\sc Prometheus} Project -- Progetto Finalizzato
Trasporti under contracts n.~93.01813.PF74 and 94.01371.PF74.

The authors are indebted to Gianni Conte for the
valuable and constructive discussions and for his
continuous support throughout the project.
}



% \singlespacing
\vskip 0.2in
\bibliography{dii,ca,misc,mm,autom}
\bibliographystyle{theapa}


\end{document}


\section{Removing the Perspective Effect}
The procedure aimed to remove the perspective
effect from the acquired image can be considered as a transform,
performed after the acquisition process and before the mere low-level
processing.  It reads the incoming image and  resamples it,
remapping each pixel toward a
different position and producing a new 2-dimensional array of pixels.

The reorganization process, in fact,
produces a new image representing a top view of the road region in front
of the vehicle,
as it were observed from the top.
This is accomplished by applying a transform that
associates to each pixel of the new reorganized image its corresponding
pixel in the original one, according to a given projection function.

\bfig[htb]
\centerline{
\epsfxsize=10cm
\epsffile{tlc.eps} }
\caption{The relationship between the two coordinate systems
\label{tlc}}
\efig

\noindent
Two Euclidean spaces are thus defined:
\bit
\itemsep -1mm
\item
$\W = \Big\{ (x,y,z) \Big\}
\in E^3$ representing the $3D$ world space ({\em world-coordinate
system}), where the real world is defined;
\item
$\I = \Big\{ (u,v) \Big\}
\in E^2$ representing the $2D$ image space ({\em screen-coordinate
system}), where the 3D scene is projected.
\eit
The image acquired by the camera belongs to the $\I$ space, while the
reorganized image is defined as the $z=0$ plane of the $\W$ space
(according to the assumption of a flat road).
Figure~\ref{tlc} shows the relationships between the two spaces $\W$ and
$\I$; their correspondence is discussed in the two following
subsections.

The reorganization process
associates to each pixel $P=(x,y,0)$
of the reorganized image its corresponding
pixel $Q=(u,v)$ in the original one:
namely, as shown in Figure~\ref{tlc},
it projects the acquired image onto the
$z=0$ plane of the 3D world space $\W$, acting as the dual of a {\em
ray-tracing} algorithm~\cite{computer-graphics}.

Figures~\ref{figXreorg}.b shows the result of the reorganization process
applied to Figures~\ref{figXreorg}.a, using a set of parameters corresponding to
the real camera and acquisition conditions~\cite{tsai}
of the {\sc Mob-Lab} land vehicle.


\subsection{Mapping the $\W$ Space to the $\I$ Space}

In order to generate a 2D view of a 3D scene, a {\em viewpoint}, {\em
viewing direction}, {\em aperture}, and {\em resolution} must be
specified~\cite{computer-graphics}.
Let us make the following assumptions:
\bit
\itemsep -1mm
\item {\em viewpoint}: the camera is placed in $C=(l, d, h)\in \W$;
\item {\em viewing direction}: the optical axis $\hat o$ is
determined by the following angles:
\bit
\itemsep -1mm
\item $\overline{\gamma}$:  the angle formed by the projection (defined
by
versor $\hat\eta$) of the
optical axis $\hat o$ on the  plane $z=0$ and the
$x$ axis (as shown in Figure~\ref{figuab}.a);
\item $\overline{\theta}$: the angle formed by the optical axis $\hat o$
and
versor $\hat \eta$ (as shown in Figure~\ref{figuab}.b);
\eit
\item {\em aperture}: the camera angolar aperture is $2\alpha$;
\item {\em resolution}: the camera resolution is $n\times n$.
\eit

\bfig[htb]
\centerline{
\epsfxsize=12cm
\epsffile{figuab.eps} }
\caption{{\em (a)} the $xy$ plane in the $\W$ space and {\em (b)}
the $z\eta$ plane,
assuming the Origin translated onto the projection $C_{xy}$ of $C$ on
$z=0$
\label{figuab}}
\efig
Now let us determine the intersection between
each of the $n^2$ rays leaving the camera (within the viewing
pyramid~\cite{computer-graphics})
and the plane $z=0$, assuming the region of interest belonging
to this plane.

The $n^2$ rays are determined by $\theta(u)$ and $\gamma(v)$, obtained
by the
scanning of the camera angolar aperture. $\theta(u)$ and $\gamma(v)$ can
vary
as follows:

\beq
\left\{
\begin{array}{l}
\theta(u) = \Big(\overline{\theta}-\alpha\Big) + u\Cdot
\frat{2\alpha}{n-1} \\[12pt]
\gamma(v) = \Big(\overline{\gamma}-\alpha\Big) + v\Cdot
\frat{2\alpha}{n-1} \\
\end{array}
\right. \ms,
\label{eq:thetagamma}
\eeq
where $u,v = 0,1,2,...,n-1$ represent the coordinates in the $\I$ space.

The distance between the projection $C_{xy} \in \W$  of $C$ on $z=0$ and
the intersection $P\in \W$ between the generic ray determined by the
couple
$\Big(\theta(u)$,
$\gamma(v)\Big)$ and the plane $z=0$  is given by the following
expression:
\beq
{\rm distance~}(C_{xy},P) = \frat{h}{{\rm tg~} \Big[\theta(u)\Big]}\ms.
\eeq
The projection of $P$ on the $x$ and $y$ axes is given by:
\beq
\left\{
\begin{array}{lcl}
x(P) &=& \frat{h}{{\rm tg~} \Big[\theta(u)\Big]} ~{\rm cos~} \gamma(v) +
l\\
y(P) &=& \frat{h}{{\rm tg~} \Big[\theta(u)\Big]} ~{\rm sin~} \gamma(v) +
d\\
\end{array}
\right. \ms.
\label{eq:yuv}
\eeq

Using equations~(\ref{eq:thetagamma}),
the final mapping $f:\I\rightarrow \W$
as a function of $u$ and $v$ is then given by:
\beq
\left\{
\begin{array}{lcl}
x(u, v) &=& \frat{h}{{\rm tg~} \Big[(\overline{\theta}-\alpha)
+ u \Cdot \frat{2\alpha}{n-1}\Big]} \Cdot {\rm cos~}
\Big[(\overline{\gamma}-\alpha) +
v \Cdot \frat{2\alpha}{n-1}\Big] + l\\
y(u, v) &=& \frat{h}{{\rm tg~} \Big[(\overline{\theta}-\alpha)
+ u \Cdot \frat{2\alpha}{n-1}\Big]} \Cdot {\rm sin~}
\Big[(\overline{\gamma}-\alpha) +
v \Cdot \frat{2\alpha}{n-1}\Big] + d\\
z &=& 0\\
\end{array}
\right. \ms.
\label{eq:xyz}
\eeq

Given the coordinates $(u,v)$ of a generic point $Q$ in the $\I$ space,
equations~(\ref{eq:xyz}) return the coordinates $(x, y, 0)$ of the
corresponding point $P$ in the $\W$ space (see Figure~\ref{tlc}).
It is easy to understand (even intuitively) that this transform causes
an information loss, which is higher in the central region
and lower in the peripheral region.

\subsection{Mapping the $\I$ Space to the $\W$ Space}

Following similar algebraic and trigonometric manipulations, the inverse
transform (the dual
mapping) is given as follows.
Given a generic point $P$ with coordinates $(x,y,0)$, let us now
compute the angles formed by the optical axis $\hat o$ and segment
$\overline{CP}$.
Following the definitions of $\theta$ and $\gamma$ given before, it is:
\beq
\left\{
\begin{array}{lcl}
\gamma(x,y,0) &=& {\rm arctg~} \left[\frat{y-d}{x-l}\right] \\
\theta(x,y,0) &=& {\rm arctg~} \left[\frat{h\Cdot
{\rm sin~}\gamma(x,y,0)}{y-d}\right] \\
\end{array}
\right. \ms.
\eeq
If $\gamma(x,y,0) \in \Big[\overline{\gamma}-\alpha ,
\overline{\gamma}+\alpha\Big]$ and
$\theta(x,y,0) \in \Big[\overline{\theta}-\alpha ,
\overline{\theta}+\alpha\Big]$, then point $P$ belongs to the viewing
pyramid and its coordinates $(u,v)$ in the $\I$ space are given by the
following mapping $g:\W\rightarrow \I$:
\beq
\left\{
\begin{array}{lcl}
u(x,y,0) &=& \frat{ \gamma(x,y,0) - \Big(\overline{\gamma}-\alpha\Big) }
{\frat{2 \alpha}{n-1}}\\
v(x,y,0) &=& \frat{ \theta(x,y,0) - \Big(\overline{\theta}-\alpha\Big) }
{\frat{2 \alpha}{n-1}}\\
\end{array}
\right. \ms.
\label{eq:uv}
\eeq
The reorganization process defined by equation~(\ref{eq:uv})
removes the perspective effect and recovers the texture of the
$z=0$ plane in the $\W$ space. It
consists of scanning the array of pixels of coordinates
$(x,y,0) \in \W$ which form
the reorganized image, in order to associate to
each of them the corresponding value assumed by the point of
coordinates
$\Big( u(x,y,0), v(x,y,0) \Big) \in \I$.

Note that, as shown in Figures~\ref{figXreorg}.c, the lower portion of the
reorganized image is undefined. The
undefined area  is due to
the specific camera position with respect to the $x$ axis, and to the
finite angolar aperture.



\acks{This work was partially supported by the Italian {\sc Cnr} within the
framework of the Eureka {\sc Prometheus} Project -- Progetto Finalizzato
Trasporti under contracts n.~93.01813.PF74 and 94.01371.PF74.

The authors are indebted to Gianni Conte for the
valuable and constructive discussions and for his
continuous support throughout the project.
}



% \singlespacing
\vskip 0.2in
\bibliography{dii,ca,misc,mm,autom}
\bibliographystyle{theapa}


\end{document}
