On the Advantages of Polar and Log-Polar Mapping for Direct Estimation of Time-To-Impact from Optical Flow.
The application of an anthropomorphic retina-like visual sensor and the advantages of polar and log-polar mapping for visual navigation are investigated. It is demonstrated that the motion equations that relate the egomotion and/or the motion of the objects in the scene to the optical flow are considerably simplified if the velocity is represented in a polar or log-polar coordinate system, as opposed to a Cartesian representation. The analysis is conducted for tracking egomotion but is then generalized to arbitrary sensor and object motion. The main result stems from the abundance of equations that can be written directly that relate the polar or log-polar optical flow with the time to impact. Experiments performed on images acquired from real scenes are presented.
Introduction
Autonomous systems should be able to control their movements in the environment
and adapt to unexpected events. This is possible only if the robot
has the capability to "sense" the environment. Among the sensors used for
robots, visual sensors are the ones that require the greatest computational
power to process the acquired data, but also generate the greatest amount
of information. Despite the fact that many researchers have addressed the
problem of "how to process" visual data [?, ?, ?, ?], less attention has been
given to the definition of devices and strategies for image acquisition which
could, possibly, reduce the amount of data to be processed and the algorithmic
complexity for the extraction of useful information [?, ?, ?, ?, ?, ?].
Ballard et al. [?] and also Sandini and Tistarelli [?, ?] among others, investigated
a tracking motion strategy which greatly simplifies the problem
of visual navigation.
To this extent the major effort done so far to try to reduce the amount of
information flowing from the visual sensors to the processing part of artificial
visual systems, has been concentrated on the image itself. This approach
is certainly justified in those situations in which images are acquired "pas-
sively" and transmitted to a distant station to be analyzed (e.g. satellites).
The data reduction strategy solves, in this case, a communication problem.
Very different strategies can be exploited when the data reduction has to be
achieved in order to solve understanding and behavioural problems. In this
case the main goal of the data reduction strategy is to avoid overloading the
system with "useless" information. The hardest part is to define the term
useless unless its meaning is directly tied to the task to be performed: useful
information is the information necessary to carry out the task. Also in this
case, if we only think in terms of images, it is impossible to extract the "use-
ful" information unless at least a rough processing of the images has been
performed. For example, if the strategy is related to the extraction of edges,
this processing has to be applyed to the overall image even if, for the task
at hand, only a small portion of the image would be sufficient. Solutions
to this problem have been proposed in the past through the use of multiple
windows system and the achieved results are certainly very interesting [?, ?].
Our approach is that of studying and developing smart sensing devices with
buit-in data compression capabilities [?, ?]. The space-variant sensor which
produces the log-polar transformation described in this paper, is an example
of how it may be possible to reduce the information amount directly at the
sensor level.
Using a foveated sensor (i.e. a sensor with a small, high resolution part,
surrounded by a lower resolution area) poses the problem of where to look
(i.e. where to position the central, high resolution, part of the visual field).
To solve this problem two approaches are possible: the first is to base the
selection of the focus of attention on the results of some interpretation pro-
cedure, the second is to take advantage of the task to be carried out. The
first approach is mandatory for static systems while the second approach
has the advantage of being less dependent on visual information processing.
In fact, following the second approach the selection of the focus of attention
can be done pre-attentively i.e. before the visual processing part has even
started. In case of space-variant sensors of the kind described in this paper,
the selection of the focus of attention goes along with the selection of the
direction of gaze. In fact, the direction of gaze defines the part of the scene
which is analyzed with the highest detail, or conversely, the region around
the focus of attention has to be sampled with the highest resolution. Stemming
from this consideration the strategies of gaze control can be seen as a
way to reduce the amount of information to be processed. Moreover, if these
strategies can be made dependent upon the task alone this data reduction
can be carried out before the interpretation of visual images. Examples of
what we mean by this are some visuo-motor strategies performed by humans
during the execution of specific behaviours. For example during locomotion
the direction of gaze is either pointed straight ahead toward the direction
of motion (to provide gross orientation information) or down, just ahead of
the actual position (to detect unexpected obstacles) [?, ?]. Of course other
safety level processes are running simultaneously but the major feature is
the possibility of defining the "focus of attention" (and as a consequence the
direction of gaze) as a function of the task alone. Other examples can be
presented in the field of manipulation. During the final stage of grasping,
for example, the focus-of-attention is in the vicinity of the contact area that
is, close to the end-effector. Also in this case the position of the hand in
space is known and the direcition of gaze can be controlled first by knowing
the trajectory of the end-effector and, secondly, by tracking it.
It is obvious that, even in this case, some image processing has to be
performed (e.g. the tracking of a point in space) but the important observation
is that these procedures are independent of the content of the images
or, in other words, they are data driven. One of the major goal of this paper
is to demonstrate that these data driven processes are performed even
"better" by using a space-variant sensor than using a conventional device.
1 It is worth noting, however, that in reality this is a problem that need to be solved
also for conventional sensors. In fact the location of the "fixation point" for stereo systems
with convergent optical axis has to be defined as well as for focussing procedures (it is not
feasible to "focus" everywhere).
As a result the poposed approach is not only usefulf in limiting the amount
of information to be processed through a "hardware focus-of-attention" (the
fovea) but its geometrical structure is advantageous to control the position
of the focus-of-attention.
Active tracking motion is the basis of the analysis conducted in this pa-
per. It is related to the properties of a retina-like sensor, defining the depth-
from-motion equations after the log-polar mapping. Due to its particular
topology, a retina-like sensor incorporates many advantages for dynamic image
processing and shape recognition. This potential can be considerably
augmented, making the sensor "smart", e.g. defining a set of visual tasks
that can be performed directly on the sensor, without the need for any other
external input, and dramatically reducing the time required for processing.
The computation of the optical flow from an image sequence and the tracking
of moving targets are examples of the visual tasks that can be defined.
In this paper we derive the optical flow equations for the retinal CCD
sensor. The flow field, computed on the log-polar plane, is then used to
estimate the time-to-impact. The analysis is performed considering the optical
flow equations due to the tracking egomotion on the retinal, Cartesian
plane and relating them to the computed velocity field on the log-polar
plane. Even though quantitative results can be obtained, this is not a natural
way of approaching the problem. Jain [?] pointed out the advantages of
processing the optical flow, due to camera translation, by using a log-polar
complex mapping of the images and choosing the position of the FOE as the
center for the representation. If the observer rotates during translation, to
fixate a static target in space, or conversely, just rotates without translating,
but tracking a moving target; then it is possible to intuitively understand
that the time to fly before reaching the obstacle(s) is proportional to the
rate of expansion of the projection of the object's shape on the retinal plane.
We demonstrate in fact, that only the radial component of the optical flow,
represented on the polar plane, depends on the time-to-impact. The polar
flow representation is analysed and a number of simple relations are derived,
which allow us to directly compute the time-to-impact with arbitrary ego-
and/or eco- motion.
Conformal mapping
In the human visual system the receptors of the retina are distributed in
space with increasing density toward the center of the visual field (the fovea)
and decreasing density from the fovea toward the periphery. This topology
can be simulated, as proposed by Sandini and Tagliasco [?], by means of
a discrete distribution of elements whose sampling distance (the distance
between neighbouring sampling points) increases linearly with eccentricity
from the fovea. An interesting feature of the space-variant sampling is the
topological transformation of the retinal image into the cortical projection 2
[?, ?].
This transformation is described as a conformal mapping of the points
on the polar (retinal) plane (ae;
log ae; where the values of (ae; j) can be obtained mapping the Cartesian
coordinates (x; y) of each pixel into the corresponding polar coordinates.
The resulting cortical projection, under certain conditions, is invariant to
linear scalings and rotations on the retinal image. These complex transformations
are reduced to simple translations along the coordinate axes of the
cortical image. This property is valid if, and only if, the scene and/or the
sensor move along (scaling) or around (rotation) the optical axis.
The same properties hold in the case of a simple polar mapping of the im-
age, but a linear dialation around the fovea is transformed into a linear shift
along the radial coordinate in the (ae; plane. Meanwhile, the log-polar
transformation produces a constant shift along the radial coordinate of the
cortical projection.
Beyond the geometric properties of the polar and log-polar mapping, which
will be referred to in the following sections, the log-polar transformation
performs a relevant data reduction (because the image is not equally sampled
throughout the field of view) while preserving a high resolution around
the fovea; thus providing a good compromise between resolution and band-limiting
needs. This property turns out to be very effective if you wish to
focus attention on a particular object feature, or to track a moving target
(i.e. to stabilize the image of the target in the fovea). Therefore the
properties of the topological log-polar mapping has found interesting applications
for object and, more specifically, shape recognition and object
tracking [?, ?, ?, ?, ?, ?].
The main focus of the paper is, in fact, to stress the peculiarity of this
transformation in the computation of dynamic measures. In particular the
main observation is that during the tracking of a moving object the mapping
2 The terms "retinal" and "cortical" derive from the observation that the conformal
mapping described here is very similar to the mapping of the retinal image onto the visual
cortex of humans [?, ?].
of the stabilized retinal image onto its cortical image deforms in such a way
that it is easier to compute those "behavioral variables" usefulf to control
the position of the focus-of-attention. In fact, if the object is perfectly
stabilized on the retina, and the shape does not change due to perspective
changes (this is a good approximation for images sampled closely in time)
the component of the velocity field along the log ae axis alone measures the
"rate of dilation" of the retinal image of the object. This measure can be
used to compute the time-to-crash.
In this paper we will illustrate how the log-polar transformation as well as
a simple polar mapping can dramatically simplify the recovery of structural
information from image sequences, allowing direct estimation of the time-
to-impact from the optical flow.
2.1 Structure of the retina-like sensor
A prototype retina-like visual sensor has been designed within a collaborative
project involving several partners 3 . In this paper we will refer to
the physical characteristics of the prototype sensor when dealing with the
log-polar transformation. The results could be easily generalised to any particular
log-polar mapping, by modifying the constant parameters involved
in the transformation.
The retino-cortical mapping is implemented in a circular CCD array, using
a polar scan of a space-variant sampling structure, characterized by the
sampling period and the eccentricity (the distance from the center of the
sensor). The spatial geometry of the receptors is obtained through a square
tassellation and a sampling grid formed by concentric circles [?]. The prototype
CCD sensor, depicted in Fig. 1, is divided into 3 concentric areas each
consisting of 10 circular rows and a central fovea. Each circular row consists
of 64 light sensitive elements [?]. The central fovea is covered by a square
array of 102 light sensitive elements. 4 In the experiments the information
coming from the fovea is not used.
As for the extra-foveal part of the sensor the retino-cortical transformation
3 The institutions involved in the design and fabrication of the retinal CCD sensor
are: DIST - University of Genoa, Italy; University of Pennsylvania - Dept. of Electrical
Engineering, Italy. The actual fabrication
of the chip was done at IMEC, Leuven, Belgium
4 Currently the performances of the CCD sensor are being evaluated (the first "real"
image has been recently acquired) and a prototype camera is being built. The experiments
reported in this paper are carried out by re-sampling standard TV images following the
geometry of the sampling structure of the sensor.
is defined by:
log a ae \Gamma p
(1)
are the polar coordinates of a point on the retinal plane,
and a are constants determined by the physical layout of the CCD sensor.
Tracking ego-motion and optical flow
The ability to quickly detect obstacles and evaluate the time-to-impact to
react in order to avoid it is of vital importance for animates. Passive vision
techniques can be beneficially adopted if active movements are performed
[?, ?, ?, ?, ?, ?]. A dynamic spatio-temporal representation of the scene,
which is the time-to-impact with the objects, can be computed from the
optical flow which is extracted from monocular image sequences acquired
during "tracking" movements of the sensor. The image velocity can be
described as function of the camera parameters and split into two terms
depending on the rotational and translational components of camera velocity
respectively:
~
F
(2)
~
Z
are the distances of the camera from the fixation point in two
successive instants of time, OE, ' and / are the rotations of the camera referred
to its coordinate axes, shown in Fig. 2 and Z is the distance of the
world point from the image plane. As we are interested in computing the
time-to-impact Wz
Z , then ~ V t must be derived from the total optical flow.
The rotational part of the flow field ~
V r can be computed from proprioceptive
data (e.g. the camera rotational angles) and the focal length. Once
the global optic flow ~
V is computed, ~
V t is determined by subtracting ~
from ~
. Adopting the constrained tracking egomotion, the rotational angles
are known, as they correspond to the motor control generated by the
fixation/tracking system.
The image velocity is computed by applying an algorithm for the estimation
of the optical flow to a sequence of cortical images [?]. In Fig. 3
the first and last images of a sequence of 16 are shown. The images have
been acquired with a conventional CCD camera and digitized with 256x256
pixels and 8 bits per pixel. The motion of the sensor was a translation plus a
rotation OE around its horizontal axis X. During the movement, the direction
of gaze was fixed on a point on the ground far behind the sensor. In Fig.
4 (a) the result of the retinal sampling applied to the first image in Fig. 3
and 4(b) the simulated output of the retinal sensor obtained following the
characteristics of the chip are shown. The resulting images are 30x64 pixels.
When evaluating the presented experimental results, the extremely low number
of pixels (1920) should be considered.
The optical flow is computed by solving an over-determined system of
linear equations in the unknown terms (u;
. The equations impose
the constancy of the image brightness over time [?] and the stationarity of
the image motion field [?, ?]:
d
d
where I represents the image intensity of the point (x; y) at time t. The
least squares solution of (3) is computed for each point on the cortical plane
as:
~
@I
@-
@I
@t
@- @t
where (-; fl) represent the point coordinates on the cortical plane.
In Fig. 5 the optical flow of the sequence of Fig. 4(b) is shown.
3.1 First step: relating the motion equations to the log-polar
mapping
In (2) we defined the relation between camera velocity and optical flow. Now
we develop the same equations for the velocity field transformed onto the
cortical plane. The goal is to find an expression which relates the cortical
velocity ~
to the rotational flow ~
V r to derive the translational flow
~
compute the time-to-impact).
Firstly we derive the motion equations on the cortical plane:
ae
ae log a e
where e is the natural logarithmic base and a; q are constants related to
the eccentricity and the density of the receptive fields of the retinal sensor.
The retinal velocity ( -
can be expressed as a function of the retinal
coordinates relative to a Cartesian reference system (as
y
x
is the retinal velocity of the image point, relative to a
Cartesian reference system centered on the fovea. Substituting (6) in (5)
yields:
log a
developing (7) and making explicit the retinal velocity ~
\Gammay
x
log e a
by substituting the expression for ~
V r from (2) in (8) we obtain the translational
flow ~
referred to the retinal plane:
~
log e a \Gamma y -
F
log e a
fl) is the velocity field computed from the sequence of cortical images.
It is worth noting that, expressing the Cartesian coordinates of a retinal
sampling element in microns, the focal length and the retinal velocity ~
are
also expressed in the same units. If the rotational velocity of the camera
during the tracking is avaliable, then ~
V t can be computed.
The time-to-impact of all the image points on the retinal plane can be
recovered using a well-known relation [?]:
D f is the displacement of the considered point from the focus of the translational
field on the image plane, and WZ is the translational component of the
sensor velocity along the optical (Z) axis. The ratio on the left-hand side
represents the time-to-impact with respect to the considered world point.
The location of the FOE is estimated by computing the least squares fitting
of the pseudo intersection of the set of straight lines determined by the
velocity vectors ~ V t .
This formulation is very direct as it does not exploit completely the implications
and advantages of the log-polar mapping, and also many external
parameters related to the camera and the motion are required to compute
the time-to-impact. Both the focal length and the rotational motion of the
camera must be known in order to estimate the translational component
of velocity ~
while the FOE must be computed from ~
V t to estimate the
time-to-impact. Moreover, this schema can not be used in the presence of
independently moving objects since the basic assumption is that the environment
is completely static. In summary the algorithm can be applied
- the rotational part of the camera motion is known;
- the intrinsic camera parameters, at least the focal length, are known;
- the objects in the scene do not move independently.
By exploiting further the advantages and peculiarities of the polar and
log-polar mapping, all these requirements and constraints will be "gradu-
ally" relaxed in the analysis performed in the remainder of the paper. Our
final aim being the estimation of the time to impact using only image-derived
parameters, in the case of camera and object motion.
Even though this algorithm requires many constraints, they still do not
limit the generality of its possible applications. It can be successfully ap-
plied, for example, to locate obstacles and detect corridors of free space
during robot navigation. The accuracy of the measurements depends on
the resolution of the input images, which, for the retinal sensor, is very
low. Nevertheless, the hazard map computed with this method can still be
exploited for its qualitative properties in visual navigation.
Fig. 6(a) shows the time-to-impact of the objects (hazard map) of the
scene in Fig. 4(a), and in Fig. 6(b) the associated uncertainty. In appendix
A a quantitative measure of the error in the estimated time-to-impact, is
derived.
3.2 Exploiting further the polar and log-polar mapping for
optical flow
It is possible to generalise the logarithmic-polar complex mapping property
of transforming object's dialation into a translation along the - (radial)
coordinate to more general and complex kind of motions. Generally, any
expansion of the image of an object, due either to the motion of the camera
or the object itself, will produce a radial component of velocity on the retinal
plane. This intuitive observation can be also stated in the following way :
the time-to-impact of a point on the retinal plane, only effects the radial
component of the optical flow
we will formally prove this assertion in the remainder of the paper.
This observation lead us to adopt an approach different to the one pursued
in the previous section, in order to represent the optical flow on the cortical
plane. It turns out that the most convenient way of representing and
analysing velocity is in terms of its radial and angular components with
respect to the fovea.
Let us consider, for the moment, a general motion of the camera both
rotational and translational. We will later consider the special case of tracking
egomotion, explaining how it simplifies the analyisis, and finally dealing
also with object motion. The velocity on the image plane along the radial
and angular coordinates is :
ae
y) is the retinal velocity with respect to a Cartesian coordinate
system centered on the fovea. Plugging in the motion equations for small
angular rotations (as from (2)):
F
F
sin j
ae
F
F
sin j
by substituting the values for
ae
hi Wx
sin
Z
as the retinal sensor performs a logarithmic mapping, we obtain:
ae
ae log a e
Z
ae
ae
OE sin fl
log a e
ae
hi Wx
sin
Z
cos
These equations simply show that, while both components of the optical
flow depend upon the depth Z of the objects in space, only the radial component
depends upon the time-to-impact Z
Wz . Moreover, only the angular
component -
depends upon rotations around the optical axis, while the radial
component is invariant with respect to /. Notice that up to now we
have not made any hypothesis about the motion of the sensor. Therefore
equations certainly hold for any kind of camera motion. Even though
the analysis has been conducted for a moving camera in a static environment
the result obtained in (13) holds for any combination of object and
camera motion. All the motion parameters are expressed in terms of translational
velocities in space (W x rotational velocities referred
to a camera-centered Cartesian coordinate system (OE; '; /). These velocities
have not to be absolute velocities but can represent the relative motion of the
camera with respect to the objects, which is the sum of the two velocities.
Equations (13) can be further developed in the case of tracking egomo-
tion. By imposing ~
in the general optical flow equations this
motion constraint can be expressed as:
D 2 is the distance of the fixation point from the retinal plane measured at
the frame time following the one where the optical flow is computed.
By developing equation (13) using the values for W x and W y given in
(14), we obtain:
ae
Z
OE sin fl
log a e
ae
Z
sin fl
The structure of the two equations is very similar. If the rotational
velocity of the camera is known, then it is possible to substitute the values
for (OE; '; /) into (15) to directly obtain Z
from -
Wz from the radial
component -
-:
Z
F
OE cos fl
F
OE cos fl
Z
log e a
F
OE sin fl
also the focal length F must be known , while q and a are constant values
related to the physical structure of the CCD sensor [?]. It is worth noting
the importance of Z
and Z
Wz . In fact, they both represent relative measurements
of depth which are of primal importance in humans and animals
to relate to the environment.
It is interesting to compare this last equation with equations (9) and
(10). As it can be noticed, equation (16) does not depend on the position
of the FOE. Therefore it is not necessary to differentiate the optical flow
with respect to the rotational component ~
V r to estimate the translational
component ~
A further option is to try to compute the time-to-impact from the partial
derivatives of both velocity components:
ae
OE sin fl
by combining this equation with the expression of -
-, as from equation (15),
we obtain:
log e a
Z
F
OE sin fl
Z
W z
log e a
ae
F
OE sin fl
also in this case the time-to-impact can be computed by directly substituting
the values of the rotational angles. Note that in this case the equation does
not depend on the rotation around the optical axis. This is the first important
result, as it makes the computation of the time-to-impact independent
of one motion parameter. We now develop alternative methods which allow
us to release the other parameters also, which can not be easily computed
from the images.
Let us consider the first derivative of -
-:
@-
F
F
ae
Z
'-'
OE sin
notice that ae = a -+q .
This result suggests another possibility of using the first derivative of -
- to
obtain a relation which is similar to (18):
Z
W z
log e a
F
OE sin fl
By considering neighbouring pixels (- at the same eccentricity
is possible to formulate two equations in two unknown terms in
the form:
Z
W z
F
OE sin
Setting now
@-
Z
W z
We have obtained an equation for the time-to-impact which only involves
image-derived parameters, like velocity and its derivative and image coor-
dinates, without requiring the knowledge of the motion parameters. It is
also worth noting that in all the formulations derived in this section the
optical flow has not to be differentiated to recover the translational flow
(like in other approaches [?, ?]), nor has the FOE position to be computed.
These are very important features of a method for the computation of the
time-to-impact, as in fact the rotational velocity and the FOE are computed
indirectly from the optical flow and are therefore subject to errors.
Even though equation (22) can be directly applied, more points along
the same ray should be used to improve the robustness of the algorithm. In
this case an over-constrained system of equations can be used and solved
using standard least squares techniques:
W z
Z
~
A t A
A t ~ b
~
Z
The underlying assumption of constant depth requires the use of a small
neighbourhood of ae i . Depth discontinuities can in fact introduce artifacts
and errors processing images from cluttered scenes.
Another equation (which is simpler) for the time-to-impact can be obtained
by combining equation (17) and (19):
W z
Z
log e a
ae
F
OE sin fl
W z
Z
log e a
F
OE sin fl
by combining these two equations we obtain:
Z
W z
log e a \Gamma
@-
Again, equation (25) allows the direct computation of the time-to-impact
from the images only. Notice that only first order derivatives of the optical
flow are required and the pixel position does not appear. The parameters q
and a are calibrated constants of the CCD sensor. It is interesting to relate
this result to the divergence approach proposed by Thompson [?] and also
recently by Nelson and Aloimonos [?]. Equation (25) can be regarded as a
formulation of the oriented divergence for the tracking motion, modified to
take into account the fact that the sensor is planar and not spherical.
In Fig. 7(a) the first and last image of a sequence of 10 is shown. The
images have been acquired at the resolution of 256x256 pixels and then re-sampled
performing the log-polar and polar mapping. The motion of the
camera was a translation plus a rotation ' around its vertical axis Y . The
direction of gaze was controlled so as to keep the fixation on the apple in the
center of the basket (which is the object nearest to the observer). The inverse
time-to-impact Wz
Z , computed by applying equation (25) to the optical flow
in Fig. 8(a) is shown in Fig. 9(a). Despite the low resolution the closest
object is correctly located.
A last equation for the time-to-impact can be obtained by computing
the second order partial derivative of -
-:
F
ae
Z
'-'
OE sin fl
log e a (26)
Z
W z
log e a \Gamma
log a e
This equation clearly states that the time-to-impact can be computed
using only the radial component of velocity with respect to the fovea. More-
over, this formulation does not depend on the motion of the fixated target.
The motion parameters involved can also represent relative motion. As the
equation is applied to each image point the method is still valid for scenes
containing many independently moving objects. In Fig. 9(b) the inverse
time-to-impact of the scene in Fig. 7, computed by applying equation (31)
to the optical flow in Fig. 8(b), is shown.
The analysis performed in this section has been developed for the CCD
retinal sensor but many of the results are still valid for conventional raster
sensors. Some advantages are still obtained by using the retinal sensor. Let
us consider equation (12) and apply the tracking constraint without making
the complex logarithmic mapping:
Z
ae
Z
The partial derivative of -
with respect to j only changes for a constant
factor, while the partial derivatives of -
ae with respect to ae are:
ae
@ae
Z
F
ae
A first formulation for the time-to-impact involves the second order partial
derivatives of the radial component -
ae of the optical flow:
Z
W z
ae
@ae
ae
An equation for the time-to-impact containing only first order partial
derivatives of velocity can be obtained by considering also the angular component
ae
by combining this equation with (28) and (29) obtain:
Z
W z
ae
ae
ae
@ae
We can conclude that an abundance of equations exist to compute the
time-to-impact in the case of tracking egomotion if the proper coordinate
system is chosen (polar in this approach). It has been shown that a polar
velocity representation seems to be best suited to recover the time-to-impact
from image sequences. Even though technology has been very conservative
in producing only raster CCD arrays and imaging devices (therefore strongly
linked to a Cartesian coordinate system), a polar transformation can be performed
in real-time by using commercially avaliable hardware, enforcing the
feasibility of the proposed methodology. On the other hand a retinal CCD
sensor naturally incorporates the polar representation, and also introduces
a logarithmic scaling effect which makes the equations simpler (they do not
depend on the radial coordinate of the point ae) [?].
In Fig. 10 the measurements of the inverse time-to-impact for the sequence
in Fig. 7, computed using 10(a) equation (31) and 10(b) equation
(33), are shown.
In order to demonstrate the applicability of the method in the case of
independently moving objects equation (33) has been applied to a sequence
of images where the camera is moving along a trajectory parallel to the
optical axis and an object is moving along a collision course toward the
camera (but not along the direction of the camera optical axis and slightly
rotating as well). The first and last images are shown in Fig. 11(a). The
output of the polar mapping on the Cartesian plane is shown in Fig. 11(b)
and in 11(c) the polar mapping in the ae; ' plane. The hazard maps of the
scene relative to 2 successive frames are shown in Fig 12.
In appendix B a comparative analysis of the accuracy of the formulations
derived for the time-to-impact in the case of polar and log-polar mapping is
performed.
4 Analysing a general motion
At this stage it is possible to relax the tracking constraint and consider a
general motion of the camera and/or of the objects in the scene (we already
pointed out that the equations still hold for relative motions). To compute
the time-to-impact in the case of general motion equation (25) can be still
applied. Computing the partial derivatives of the optical flow, as stated by
equation (13), we obtain:
ae Z
ae
OE sin fl
ae
hi Wx
cos
sin
now combining the expressions for the optical flow and its partial derivatives
we obtain:
log e a
F
OE sin fl
log e a
F
OE sin fl
combining these two equations we obtain:
Z
W z
log e a \Gamma
@-
which is exactly equation (25). Similarly it can be also demonstrated that
the other equations, developed to recover the time-to-impact, hold for general
motion.
This is a very important result as it enforces the relevance of a polar
representation for the optical flow and furthermore extends the validity to
arbitrary motion.
As already pointed out, the equations obtained for the time-to-impact
are very similar to the divergence operator: Wz
Z , which is the factor that is
directly estimated from the equations, corresponds to the divergence mea-
surement. But, while the divergence theory finds its mathematical proof
assuming a spherical geometry for the imaging device, the proposed method
holds exactly for any kind of planar sensor.
The best way to implement this schema, by using a conventional raster
sensor, is to map each sampled image into a polar representation and then
compute the optical flow directly on the polar images. The estimated optical
flow is then already represented in the polar (ae; plane. As a matter of fact,
computing the mapping of the optical flow obtained from the original images
in the Cartesian plane, is more efficient only considering the beginning of the
visual process. But, in a steady state, after the initial time delay has been
passed, by mapping the original images only one frame has to be processed
at any time (instead of the two components of the optical flow). Moreover,
mapping the original images results in a more accurate evaluation of the
retinal flow. The mapping can be implemented very efficently by using two
look-up tables to directly address the pixels from the polar to the Cartesian
coordinate system.
5 Conclusion
The application of a retina-like anthropomorphic visual sensor and the implications
of polar and log-polar image mapping for dynamic image analysis
has been investigated. In particular the case of a moving observer undertaking
active movements has been considered as a starting point to directly
estimate the time-to-impact from optical flow. The main advantages obtained
with a log-polar retina-like sensor are related to the space-variant
sampling structure characterized by image scaling and rotation invariance
and a variable resolution. Due to this topology, the amount of incoming
data is considerably reduced but a high resolution is preserved in the part
of the image corresponding to the focus of attention (which is also the part
of the image where a higher resolution in the computation of velocity is
necessary).
Adopting a tracking egomotion strategy, the computation of the optical
flow and time-to-impact, is simplified. Moreover, as the amplitude of image
displacements increases from the fovea to the periphery of the retinal image,
almost the same computational accuracy is achieved throughout the visual
field, minimizing the number of pixels to be processed.
The polar mapping introduces a considerable simplification in the motion
equations, which allow the direct computation of the time-to-impact. The
polar and log-polar representation for optical flow are certainly best suited
for the computation of scene structure mainly for three reasons:
- a number of simple equations can be written which relate the optical
flow and its derivatives (up to the second order only in one case) to
the time-to-impact;
- relative depth is easily computed from image parameters only, it is
either relative to the observer velocity Z
Wz or the distance from the
fixation point in space Z
- the dependence on depth is decoupled in the radial and angular component
of the optical flow: only the radial component is proportional
to the time-to-impact;
- the derived equations can be easily applied also to images acquired
with a conventional raster CCD sensor. The polar mapping can be
efficently implemented using general purpose hardware obtaining real-time
performances (the complete system, implemented on a Sun SPARC
station-1, computes the optical flow and the time-to-impact in less
than one minute).
The estimation of the time-to-impact seems to be a very important process
in animals to avoid obstacles or to catch prey. The importance of the
time-to-impact as a qualitative feature has already been pointed out [?].
The time-to-impact or its inverse measurement can be effectively used to
detect and avoid obstacles, without requiring an exact recovery of the ob-
ject's surface. Therefore, even though optical flow and its derivatives have
to be computed (unfortunately with low accuracy) they are not critical because
accuracy is not mandatory for qualitative estimates. This fact also
implies that accurate camera calibration in not needed to accomplish visual
navigation.
In human beings most "low-level" visual processes are directly performed
on the retina or in the early stages of the visual system. Simple image processes
like filtering, edge and motion detection must be performed quickly
and with minimal delay from the acquisition stage because of vital importance
for survival (for example to detect static and moving obstacles). The
computation of the time-to-impact represents a simple process (a sort of
building block ) which could be implemented directly on the sensor as local
(even analogic, using the electrical charge output of the sensitive elements)
parallel operations, avoiding the delay for decoding and transmitting data
to external devices. 5


Appendix

A: "A quantitative estimation of the error recovering
the time-to-impact"
The estimation of the time-to-impact is modeled as a stochastic process
where the parameters involved in the computation are uncorrelated
probabilistic variables. Assuming the process to be Gaussian, with a set of
variables whose mean values are equal to the measured ones, then:
oe T

Acknowledgements

: The authors thank F. Bosero, F. Bottino and A. Ceccherini for
the help in developing the computer simulation environment for the CCD retinal sensor.
We are also gratefull to Frank and Susan Donoghue which carefully proofread the text
and corrected the English.
This research was supported by the Special Project on Robotics of the Italian National
Council of Research.
(x; y) is the position of the point on the retinal plane, with reference to a
Cartesian coordinate system centered on the fovea; ~
is the estimated
retinal velocity; are the coordinates of the focus of
expansion on the retinal plane; (OE; '; /) are the rotation angles undertaken
by the camera during the tracking motion. J is the Jacobian of the T ti
function and S is the diagonal matrix of the variances of the independent
variables (x; Computing the partial derivatives
of (10) we obtain:
oe y+
oe
The variances (oe x associated with the position of the image point are
set equal to the radius of the sensitive cell on the CCD array, which depends
on the spatial position of the point within the field of view. The variances
in the rotational angles are set equal to a constant, which is determined by
the positional error of the driving motors. In the experiments performed
these values are set to (0:1; 0:1; 0:1) degrees, which is a reasonable error for
standard DC servo-motors. The variances of the FOE position (oe Fx
are determined from the least squares fit error.
The variances in the optical flow components (-
fl) on the
cortical plane are directly determined by differentiating the least squares
solution of (4). The variance of the computed image derivatives, which is
used to compute the variances in the optical flow, are estimated by assuming
a uniform distribution and unitary quantization step of the gray levels [?]:
are the weights of the derivative operator with a 5 point (frames for time
derivative) support. A value of oe I 2 equal to 0.0753 for the first derivative,
and oe II
2 equal to 0.8182 for the second derivative are obtained.
The variances of the velocity vectors on the retinal plane are obtained
by differentiating (8) with respect to -
- and -
fl:
oe
oe
are the variances of the optical flow computed on the cortical plane.
Grouping similar terms in (38), we obtain:
oe
The expression within brackets appearing in the last two rows represents
the more relevant term as it is multiplyed by D f
. Consequently, the higher
errors are those due to the computation of image velocity and the estimation
of the rotational angles of the cameras (or conversely, the positioning error
of the driving motors). The terms containing the errors in the rotational
angles are also quadratic in the image coordinates, hence the periphery of
the visual field (which is the area where the spatial coordinates of the pixels
reach the greatest values) will be affected more then the foeva. Nevertheless,
all these terms are divided by the modulus of velocity raised at the sixth
power. Therefore, if the amplitude of image displacement is sufficiently large
the errors drop very quickly. As a matter of fact, the amplitude of the optical
flow is of crucial importance in reducing the uncertainty in the estimation
of the time-to-impact.


Appendix

B: "A comparative analysis of the accuracy recovering
the time to impact in the case of polar and log-polar mapping"
It is beyond the aim of this paper to perform an exhaustive error analysis
for all the derived equations, but it is interesting to compare, analitically,
the results obtained for the polar and the log-polar mapping.
In analogy to the analysis conducted for equation (10) it is possible to model
the computation of the time-to-impact as a Gaussian stochastic process
where the parameters involved in the computation are uncorrelated probabilistic
variables. Then the variance of the time-to-impact as from equation
is:
oe T
(log e a) 2 oe -
@- and ffi -
@fl .
Similarly the variance of the time-to-impact as from equation (33) is:
oe T
ae
ae
ae
@ae and ffi -
@j .
Let us assume the variances of the optical flow and its partial derivatives
to be the same in both equation (41) and (42). This assumption is justified
by the fact that the same formulation is used to estimate the optical flow.
Considering a unitary sampling step in the polar mapping, then oe ae 2 - 1.
Then it is possible to compare the two variances through the inequality:
ae 4
where oe 2 is the variance of the radial component of the optical flow. We can
first notice that the value of the term on the left hand side depends on the
value of ae while the term on the right hand side is constant. Therefore the
first term on the left hand side can be neglected with a good approximation
because it constitutes a higher order infinitesimal term with respect to 1
and the variance oe 2 is close to a unit. Then, it is sufficient to evaluate the
given the value of a = 1:0945543, it is trivial to find that the value of the
variance as from equation (41) is lower then that from equation (42) if the
radial coordinate ae is less than about 22.
The same analysis can be made comparing equation (27) and (31). The
expressions for the variance of the time-to-impact for the two equations are:
oe T
(log e a) 2 oe -
(44a)
oe T
ae
ae
ae3
and
ae
. Let us assume the variances oe -
aeof the independent parameters to be small or, at least, bounded to some integer
value. If the velocity field is smooth then also the value of
ae
is
bounded. Then the higher terms turn out to be those relative to the error
in the second derivative of the optical flow. We can then compare equation
(44a) and (44b) by analysing the inequality:
ae
-Again, assuming the variances oe
ae
2 to be almost equal, then
this inequality simply represents the intersection of a parabola, which is
function of the radial coordinate ae, with an horizontal straight line. The
meaurement of the time to impact performed using equation (27) turns out
to be more accurate than that obtained using equation (31), in the sense
of minimum variance, if the radial coordinate of the considered point is
greater than about log a e. This result nicely complements the constraint
found comparing equation (25) and (33): considering a point in the image
and varying the radial coordinate ae, whereas equation (31) allows a more
accurate estimation than equation (27), equation (25) has a lower variance
than equation (33), thus balancing the performances of the two formulations
involving the polar or log-polar mapping throughout the entire field of view.



--R





Simulated output of the retinal CCD sensor.


of the time to impact in Fig.

applied to the first image

in the Cartesian (x

the log-polar (-




equation (31) to the optical flow in Fig.


same of (a)


in the Cartesian (x

to the 8th (a) and 10th (b) frame of the sequence in Fig.
--TR
On edge detection
Motion stereo using ego-motion complex logarithmic mapping
Active vision: integration of fixed and mobile cameras
Motor and spatial aspects in artificial vision
Obstacle Avoidance Using Flow Field Divergence
Active Tracking Strategy for Monocular Depth Inference over Multiple Frames
Extending the `oriented smoothness constraint'' into the temporal domain and the estimation of derivatives of optical flow
Estimation of depth from motion using an anthropomorphic visual sensor
Active vision based on space-variant sensing
Measurement of Visual Motion
Robot Vision
Computer Vision

--CTR
Konrad Schindler, Geometry and construction of straight lines in log-polar images, Computer Vision and Image Understanding, v.103 n.3, p.196-207, September 2006
Mohammed Yeasin, Optical Flow in Log-Mapped Image Plane-A New Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.1, p.125-131, January 2002
Jos Martnez , Leopoldo Altamirano, A new foveal Cartesian geometry approach used for object tracking, Proceedings of the 24th IASTED international conference on Signal processing, pattern recognition, and applications, p.133-139, February 15-17, 2006, Innsbruck, Austria
V. Javier Traver , Filiberto Pla, Similarity motion estimation and active tracking through spatial-domain projections on log-polar images, Computer Vision and Image Understanding, v.97 n.2, p.209-241, February 2005
Sovira Tan , Jason L. Dale , Alan Johnston, Performance of three recursive algorithms for fast space-variant Gaussian filtering, Real-Time Imaging, v.9 n.3, p.215-228, June
Nattel , Yehezkel Yeshurun, Direct feature extraction in a foveated environment, Pattern Recognition Letters, v.23 n.13, p.1537-1548, November 2002
Didi Sazbon , Hctor Rotstein , Ehud Rivlin, Finding the focus of expansion and estimating range using optical flow images and a matched filter, Machine Vision and Applications, v.15 n.4, p.229-236, October 2004
Pierre Chalimbaud , Franois Berry, Embedded active vision system based on an FPGA architecture, EURASIP Journal on Embedded Systems, v.2007 n.1, p.26-26, January 2007
Swarup Reddi , George Loizou, Analysis of Camera Behavior During Tracking, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.765-778, August 1995
Phillipe Burlina , Rama Chellappa, Analyzing Looming Motion Components From Their Spatiotemporal Spectral Signature, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.10, p.1029-1033, October 1996
Philippe Burlina , Rama Chellappa, Temporal Analysis of Motion in Video Sequences through Predictive Operators, International Journal of Computer Vision, v.28 n.2, p.175-192, June 1998
Frank Tong , Ze-Nian Li, Reciprocal-Wedge Transform for Space-Variant Sensing, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.5, p.500-511, May 1995
Pelegrn Camacho , Fabin Arrebola , Francisco Sandoval, Multiresolution vision in autonomous systems, Autonomous robotic systems: soft computing and hard computing methodologies and applications, Physica-Verlag GmbH, Heidelberg, Germany,
Zoran Duric , Azriel Rosenfeld , James Duncan, The Applicability of Greens Theorem to Computation of Rate of Approach, International Journal of Computer Vision, v.31 n.1, p.83-98, Feb. 1999
Jose Antonio Boluda , Fernando Pardo, A reconfigurable architecture for autonomous visual-navigation, Machine Vision and Applications, v.13 n.5-6, p.322-331, March
F. Wrgtter , A. Cozzi , V. Gerdes, A parallel noise-robust algorithm to recover depth information from radial flow fields, Neural Computation, v.11 n.2, p.381-416, Feb. 15, 1999
C. Capurro , F. Panerai , G. Sandini, Dynamic Vergence Using Log-Polar Images, International Journal of Computer Vision, v.24 n.1, p.79-94, Aug. 1997
direct estimation;log-polar mapping;motion estimation;egomotion;tracking;visual navigation;anthropomorphic retina-like visual sensor;CCD image sensors;time-to-impact;optical flow