Method for determining sensor motion and scene structure and image processing system therefor

The invention is a method for determining the motion of an image sensor through a scene directly from brightness derivatives of an image pair. A global image sensor motion constraint is combined with the local brightness constancy constraint to relate local surface models with the global image sensor motion model and local brightness derivatives. In an iterative process, the local surface models are refined using the image sensor motion as a constraint, and then the image sensor motion model is refined using the local surface models as constraints. The analysis is performed at multiple resolutions to enhance the speed of the process.

The invention is a method for determining the motion of an image sensor 
through a scene and the structure of the scene from two or more images of 
the scene. The invention is also a system for determining the motion of 
the image sensor in the scene and the structure of the scene. 
BACKGROUND OF THE INVENTION 
Techniques for recognizing pattern shapes of objects graphically 
represented in image data are known in the art. Further, techniques for 
discriminating between moving and stationary objects having a preselected 
angular orientation, or objects having any other predetermined feature of 
interest, are also known in the art. 
A well known technique for locating a single moving object (undergoing 
coherent motion), contained in each of successive frames of a motion 
picture of an imaged scene, is to subtract the level value of each of the 
spatially corresponding image data pixels in one of two successive image 
frames from the other to remove those pixels defining stationary objects 
in the given scene and leave only those pixels defining the single moving 
object in the given scene in the difference image data. Further, by 
knowing the frame rate and the displacement of corresponding pixels of the 
single moving object in the difference image data, the velocity of the 
single moving object can be computed. However, when the image data of the 
successive frames define two motions, for example a background region 
which moves with a certain global velocity pattern in accordance with the 
movement (e.g., translation, rotation and zoom) of the camera recording 
the scene, the problem is more difficult. In this case, a scene-region 
occupied by a foreground object that is locally moving with respect to the 
background region will move in the motion picture with a velocity which is 
a function of both its own velocity with respect to the background region 
and the global velocity pattern of the background region itself. The 
global velocity pattern due to motion of the image sensor can be very 
complex since it depends upon the structure of the scene. 
A problem is to employ, in real time, the image data in the series of 
successive frames of the motion picture to (1) measure and remove the 
effects (including those due to parallax) of the global motion and (2) 
detect and then track the locally-moving foreground object to the 
exclusion of this global motion. A conventional general image-motion 
analysis technique is to compute a separate displacement vector for each 
image pixel of each frame of a video sequence. This is a computationally 
challenging task, because it requires pattern matching between frames in 
which each pixel can move differently from one another. More recently, a 
so-called "majority-motion" approach has been developed for solving the 
aforesaid problem in real time. This "majority-motion" approach and its 
implementation are disclosed in detail in the article "Object Tracking 
with a Moving Camera-an Application of Dynamic Motion Analysis," by Burt 
et al., appearing in Proceedings of the Workshop on Visual Motion, Irvine, 
Calif., Mar. 20-22, 1989, which is published by The Computer Society of 
the IEEE. Further, certain improvements of this "majority-motion" approach 
are disclosed in detail in the article "A Practical, Real-Time Motion 
Analysis System for Navigation and Target Tracking," by Burt et al., 
Pattern Recognition for Advanced Missile Systems Conference, Huntsville, 
Nov. 14-15, 1988. 
The specific approaches disclosed in these two Burt et al. articles rely on 
segmenting the image data contained in substantially the entire area of 
each frame into a large number of separate contiguous small local-analysis 
window areas. This segmentation is desirable to the extent that it permits 
the motion in each local-analysis window to be assumed to have only its 
own computed single translational-motion velocity. The closer the size of 
each local-analysis window approaches that occupied by a single pixel 
(i.e., the greater the segmentation), the closer this assumption is to the 
truth. However, in practice, the size of each local-analysis window is 
substantially larger than that occupied by a single image pixel, so that 
the computed single translational-motion velocity of a local-analysis 
window is actually an average velocity of all the image pixels within that 
window. This segmentation approach is artificial in that the periphery of 
a locally-moving imaged object in each successive frame is unrelated to 
the respective boundary borders of those local-analysis windows it 
occupies in that frame. If it happens to occupy the entire area of a 
particular window, the computed single translational-motion velocity for 
that window will be correct. However, if it happens to occupy only some 
unresolved part of a particular window, the computed single 
translational-motion velocity for that window will be incorrect. 
Nevertheless, despite its problems, the "majority-motion" and other 
approaches employing segmentation disclosed in the aforesaid Burt et al. 
articles are useful in certain dynamic two-motion image analysis, such as 
in removing the effects of the global motion so that a locally-moving 
foreground object can be detected and then tracked to the exclusion of 
this global motion. 
For many problems in computer vision, it is important to determine the 
motion of an image sensor using two or more images recorded from different 
viewpoints or recorded at different times. The motion of an image sensor 
moving through an environment provides useful information for tasks like 
moving-obstacle detection and navigation. For moving-obstacle detection, 
local inconsistencies in the image sensor motion model can pinpoint some 
potential obstacles. For navigation, the image sensor motion can be used 
to estimate the surface orientation of an approaching object like a road 
or a wall. 
Prior art techniques have recovered image sensor motion and scene structure 
by fitting models of the image sensor motion and scene depth to a 
predetermined flow-field between two images of a scene. There are many 
techniques for computing a flow-field, and each technique aims to recover 
corresponding points in the images. The problem of flow-field recovery is 
not fully constrained, so that the computed flow-fields are not accurate. 
As a result, the subsequent estimates of image sensor motion and 
three-dimensional structure are also inaccurate. 
One approach to recovering image sensor motion is to fit a global image 
sensor motion model, to a flow field computed from an image pair. An image 
sensor motion recovery scheme that used both image flow information and 
local image gradient information has been proposed. The contribution of 
each flow vector to the image sensor motion model was weighted by the 
local image gradient to reduce errors in the recovered image sensor motion 
estimate that can arise from local ambiguities in image flow from the 
aperture problem. 
There is, however, a need in the art for a method and apparatus to 
accurately determine the motion of an image sensor when the motion in the 
scene, relative to the image sensor, is non-uniform. There is also a need 
in the art for a method and apparatus to accurately determine the 
structure of the scene from images provided by the image system. A system 
possessing these two capabilities can then automatically navigate itself 
through an environment containing obstacles. 
SUMMARY OF THE INVENTION 
The invention is a method for accurately determining the motion of an image 
sensor through a scene using local scene characteristics such as the 
brightness derivatives of an image pair. A global image sensor motion 
constraint is combined with the a local scene characteristic constancy 
constraint to relate local surface structures with the global image sensor 
motion model and local scene characteristics. The method for determining a 
model for image sensor motion through a scene and a scene-structure model 
of the scene from two or more images of the scene at a given image 
resolution comprises the steps of: 
(a) setting initial estimates of local scene models and an image sensor 
motion model; 
(b) determining a new value of one of said models by minimizing the 
difference between the measured error in the images and the error 
predicted by the model; 
(c) resetting the initial estimates of the local scene models and the image 
sensor motion model using the new value of the one of said models 
determined in step (b); 
(d) determining a new value of the second of said models using the 
estimates of the models determined in step (b) by minimizing the 
difference between the measured error in the images and the error 
predicted by the model; 
(e) warping one of the images towards the other image using the current 
estimates of the models at the given image resolution; and 
(f) repeating steps (b), (c), (d) and (e) until the differences between the 
new values of the models and the values determined in the previous 
iteration are less than a certain value or until a fixed number of 
iterations have occurred. 
The invention is also an image processing system for determining the image 
sensor motion and structure of a scene comprising image sensor means for 
obtaining more than one images of a scene; means for setting the initial 
estimate of a local scene model and an image sensor motion model at a 
first image resolution; means for refining the local scene models and the 
image sensor motion model iteratively; means for warping the first image 
towards the second image using the current, refined estimates of the local 
scene models and image sensor motion model.

DESCRIPTION OF THE PREFERRED EMBODIMENTS 
FIGS. 1 and 2 illustrate a prior art approach to motion detection which 
will be helpful in understanding the present invention. In FIG. 1 it is 
assumed that a moving image sensor (e.g., a video camera) is viewing the 
ground below from aboard an aircraft in search of an object, such as an 
automobile, which is locally moving with respect to the ground, for the 
purpose of detecting the locally-moving object and then tracking its 
motion with respect to the ground in real time. In this case, the camera 
produces a sequence of image frames of the ground area at a relatively 
high rate (e.g., 30 frames per second) so that the area being viewed 
changes only a small amount between any pair of successive frames. The 
frame area 100 of each of the successive image frames is divided into a 
majority region, which is moving at a global velocity determined by the 
coherent motion of the aircraft, and a minority region occupied by 
locally-moving automobile 101 on the ground. The frame-area 100 of of each 
of a pair of successive frames, excluding border-area 102 thereof, is 
divided into an array of sub-area windows 104-11 . . . 104-mn, and the 
local velocity (designated in FIG. 1 by its vector) for each of these 
sub-area windows is computed. This may be done by displacing the image 
data in each sub-area window of one of the pair of successive frames with 
respect to the image data in its corresponding sub-area windows of the 
other of the pair of successive frames to provide a match therebetween. 
Border-area 102 is excluded in order to avoid boundary problems. Further, 
the image data included in a sub-area window of a frame may overlap to 
some extent the image data included in an adjacent sub-area window of that 
frame. In any event, the size of each sub-area window is large compared to 
the maximum displacement of image data between a pair of successive 
frames. 
The average velocity of all the local velocities is calculated and the size 
of the difference error between each local velocity and this average 
velocity determined. In general, these errors will be small and result 
from such effects as parallax and the fact that the ground viewed by the 
moving camera is not flat. However, as shown in FIG. 1, the error for 
those two sub-area windows which include locally-moving automobile 101 is 
quite large, because the computed velocities therefor include both the 
global velocity of the moving camera on the aircraft and the local 
velocity of moving on the ground. Therefore, the two sub-area windows 
which include locally-moving automobile 101 are excluded by the fact that 
their respective errors exceed a given threshold, and the average velocity 
is then recomputed from only the remaining sub-area windows. This 
recomputed average velocity constitutes an initial estimate of the global 
velocity of the motion picture due to the movement of the camera. Because 
only an initial estimate of the global velocity is being derived, the 
image data of each of the sub-area windows 104-11 . . . 104-mn employed 
for its computation is preferably of relatively low resolution in order to 
facilitate the required matching of the image data in each of the large 
number of corresponding sub-area windows 104-11 . . . 104-mn of the pair 
of successive frames. 
In FIG. 2 a feedback loop for carrying out the prior-art approach is shown 
in generalized form. The feedback loop comprises motion model 200 (that is 
derived in whole or at least in part by the operation of the feedback 
loop), residual motion estimator 202, summer 204, image warper 206, frame 
delays 208 and 210, and image data from a current frame and from a 
previous frame that has been shifted by image warper 206. Residual motion 
estimator 202, in response to image data from the current frame and from 
the previous shifted frame applied as inputs thereto, derives a current 
residual estimate, which is added to the previous estimate output from 
motion model 200 by summer 204 and then applied as a warp control input to 
image warper 206. Current-frame image data, after being delayed by frame 
delay 208, is applied as an input to image warper 206. Image warper 206 
shifts the frame-delayed current-frame image data in accordance with its 
warp-control input, and then frame-delays the output therefrom by frame 
delay 210 to derive the next previous shifted frame. 
The feedback loop of FIG. 2 performs an iterative process to refine the 
initial estimate of the global velocity to the point that substantially 
all of that portion of the respective computed sub-area windows velocities 
of the minority region due to global velocity is eliminated. This 
iterative process derives the respective local residual velocities of the 
sub-area windows 104-11 . . . 104-mn of each consecutively-occurring pair 
of successive frames, and then uses each of these residual velocities to 
derive a current estimate of the residual global velocity. More 
specifically, the respective local velocities of each pair of successive 
frames are computed and a current estimate of residual global velocity is 
made during the each cycle of the iterative process as described above, 
after the previous estimate of global velocity has, in effect, been 
subtracted out. In the case of the first cycle, the previous estimate of 
global velocity is zero, since no previous estimate of global velocity has 
been made. Therefore, in this case, the residual velocity itself 
constitutes the initial estimate of the global velocity discussed above. 
The effect of this iterative process is that the magnitude of the residual 
velocities become smaller and smaller for later and later occurring 
cycles. It is, therefore, preferable that residual motion estimator 202 
employ image data of the lowest resolution during the first cycle of the 
iterative process, and during each successive cycle employ higher 
resolution image data than was employed during the immediately preceding 
cycle, in order to minimize the required precision for the matching of the 
image data in each successive cycle. 
Residual motion estimator 202 may comprise hardware and/or software. 
Several alternative implementation species of residual motion estimator 
202 are disclosed in the aforesaid Burt et al. articles. Each of these 
species provides effective division of the computational burden between 
general and special purpose computing elements. The first step of 
ascertaining local motion within the respective sub-area windows is 
ideally suited for implementation within custom hardware. Data rates are 
high because the analysis is based on real-time video-rate image data, but 
processing is simple and uniform because only local translations need be 
estimated. The second step, in which a global model must be fit to the 
entire set of of local-motion vectors of all the sub-area windows, is well 
suited for software implementation in a microprocessor because the 
computations are relatively complex and global, but the local-motion 
vector data set is relatively small. Further, as is brought out on the 
aforesaid Burt et al. articles, the adjustment of the image-data 
resolution preferably employed in the different cycles of the iteration 
process, can be efficiently performed by Laplacian and Gaussian pyramid 
techniques known in the image-processing art as shown for example by 
Anderson et al in U.S. Pat. No. 4,692,806 and by van der Wal in U.S. Pat. 
No. 4,703,514. 
Burt et al. also describe an improvement of the "majority-motion" approach 
which employs a foveation technique where, after the each cycle of the 
above-described iterative process has been completed, only that minority 
portion of the entire analysis area that has been determined during that 
cycle not to define the global motion (i.e., automobile 101 is contained 
within this minority portion) is employed as the entire analysis region 
during the next cycle of the iterative process. Further, the size of each 
of the sub-area windows is decreased during each successive cycle, so that 
the smaller analysis area during each successive cycle can still be 
divided into the same number of sub-area windows. 
This ability in the prior art to determine the motion of an image sensor 
from analysis of a sequence of image of a scene is needed to enable an 
image sensor to navigate through a scene. The complexity arises, however, 
as the sensor moves through the scene, that objects at varying distances 
and orientation from the sensor (scene-structure) will move with different 
velocities (both speed and direction). These non-uniformities create 
substantial complexities in the analysis and necessitate using different 
techniques other than those disclosed by Burt et al. I have developed a 
method and apparatus that fits image sensor motion and scene-structure 
models directly to the images to determine the local scene structure and 
the global image sensor motion. A global image sensor motion constraint is 
combined with the local scene characteristic constraint to relate local 
surface models with the global image sensor motion model and local scene 
characteristics. In an iterative process, the local surface models are 
first refined using the image sensor motion as a constraint, and then the 
image sensor motion model is refined using the local surface models as 
constraints. The estimates of image sensor motion and scene-structure at a 
given resolution are refined by an iterative process to obtain 
increasingly more accurate estimates of image sensor motion and 
scene-structure; ie. there is a "ping-pong" action between the local model 
of scene characteristics and the global image sensor model with successive 
warps of the images to bring them into acceptable congruence with one 
another. The refinement process starts with estimates of initial image 
sensor and local scene structure models, estimates from previous frames or 
any other source of an a priori estimate. This iterative process is then 
repeated at successively higher resolution until an acceptable accuracy is 
obtained. Specifically, the models are fitted to an image pair represented 
at a coarse resolution, and the resultant models are then refined using 
the same fitting procedure at the next finest resolution. 
Image flow is bypassed as the intermediary between local scene 
characteristic changes and the global image sensor motion constraint. The 
local scene characteristic constancy constraint is combined with the image 
sensor motion constraint to relate local-planar or local-constant-depth 
models with an image sensor motion model and local scene characteristic 
derivatives. A local-planar model assumes that the scene locally has the 
shape a flat planar surface, such as a wall. A local-constant-depth 
surface model is a special case of a local-planar model. It assumes that 
the flat planar surface is oriented parallel to the surface of rhe sensor. 
Beginning with initial estimates of the image sensor motion and the local 
surface parameters, the local surface models are refined using the global 
image sensor motion model as a constraint. The global image sensor motion 
model is then refined using the local surface models as constraints. 
The following analysis uses changes in the local brightness as the local 
scene characteristic to illustrate the principles of the invention. Other 
local scene characteristics include edges, corners, landmarks and other 
features. The image brightness is related to local surface models and an 
image sensor motion model as follows. From the first order Taylor's 
expansion of the brightness constancy assumption, the brightness 
constraint equation is 
EQU .gradient.I.sup.T du+I.sub.t =0 (1) 
where .gradient.I.sup.T is the gradient vector of the image brightness 
values, du is the incremental image motion vector, and I.sub.t is the time 
derivative of the image brightness; values. Using the perspective 
projection image sensor model and the derivative of the three dimensional 
position of a moving object, the image motion u of a static object that 
results from image sensor translation T and image sensor rotation .OMEGA. 
can be written as 
EQU u=KTZ.sup.-1 +A.OMEGA. (2) 
where Z is the depth of the object, 
##EQU1## 
and x, y are image coordinates and f is the focal length of the image 
sensor. 
For a local planar patch model, 
EQU R.sup.T P=1 R=(X, Y, Z).sup.T P=(a, b, c).sup.T (4) 
where R.sup.T is a point in world coordinates and P defines the orientation 
and depth of the plane. By combining Eq. 4 with the standard perspective 
projection equations, x=Xf/Z, y=Yf/Z, and by eliminating X,Y, 
EQU Z.sup.-1 =F.sup.T P F=(x/f,y/f,1).sup.T (5) 
Inserting Eq. 5 into Eq. 2 gives the image motion in terms of image sensor 
image sensor motion, local surface orientation and depth: 
EQU u=KTF.sup.t P+A.OMEGA. (6) 
From a previous resolution or iteration an estimate of the global image 
sensor motion parameters, T.sub.0, .OMEGA..sub.0, and also an estimate, 
P.sub.0, for each local surface model may exist. Eq. 6 can be used to 
write an incremental image sensor motion equation: 
EQU du=(KTF.sup.T P+A.OMEGA.)-u.sub.0 =(KTF.sup.T P+A.OMEGA.)-(KT.sub.0 F.sup.T 
P.sub.0 +A.OMEGA..sub.0) (7) 
where u.sub.0 is the image motion corresponding to the previous estimates 
of the local surface and image sensor motion models. Inserting this 
incremental image sensor motion equation into the brightness constraint 
equation (Eq. 1) 
EQU .gradient.I.sup.T KTF.sup.T P+.gradient.I.sup.T A.OMEGA.-.gradient.I.sup.T 
KT.sub.0 F.sup.T P.sub.0 -.gradient.I.sup.T A.OMEGA..sub.0 +I.sub.t =0(8) 
The error in this equation is used to refine both the local surface models 
and the global image sensor motion model. Specifically, the least-: 
squared error in Eq. 8 is minimized with respect to the local surface 
parameters over each local region. The least squares error is then 
minimized with respect to the image sensor motion parameters over all the 
local regions. In each local image region, the least squares error measure 
is minimize as follows 
##EQU2## 
with respect to P. Differentiating Eq. 9 with respect to P.sub.min gives 
##EQU3## 
At the minimum de/dp is zero and P.sub.min is 
##EQU4## 
The planar patch model is simplified to a constant depth model so that 
P=(0,0c).sup.T. Eq. 11 then becomes 
##EQU5## 
where c.sub.0 is an estimate of the local depth from a previous scale or 
iteration. 
In the global image region, the minimized least squares error measure is 
##EQU6## 
with respect to T and .OMEGA. where c.sub.min for each local region is 
given by Eq. 13. Eq. 14 is valid only for the local-constant-depth model. 
As formulated here, the error is quadratic in .OMEGA. but non-quadratic in 
T, and a non-linear minimization technique is required. In the current 
implementation of the method, the Gauss-Newton minimization is done using 
.OMEGA. and T.sub.0 as initial starting values. It is to be understood 
that other minimization techniques can also be used. If initial estimates 
of .OMEGA..sub.0 and T.sub.0 are not available, for example from a 
previous frame in a sequence, trial translation values are inserted into 
Eq. 14, solve for .OMEGA.-.OMEGA..sub.0 (in closed form since Eq. 14 is 
quadratic in .OMEGA.-.OMEGA..sub.0) and choose as our initial estimates 
the T and .OMEGA.-.OMEGA..sub.0 that give the lowest error in Eq. 14. 
Preferably the local and global minimization is performed within a 
multi-resolution pyramid framework. 
The invention is method for determining a model for image sensor motion 
through a scene and a scene-structure model of the scene from two or more 
images of the scene at a given image resolution comprising the steps of: 
(a) setting initial estimates of local scene models and an image sensor 
motion model; 
(b) determining a new value of one of said models by minimizing the 
difference between the measured error in the images and the error 
predicted by the model; 
(c) resetting the initial estimates of the local scene models and the image 
sensor motion model using the new value of the one of said models 
determined in step (b); 
(d) determining a new value of the second of said models using the 
estimates of the models determined in step (b) by minimizing the 
difference between the measured error in the images and the error 
predicted by the model; 
(e) warping one of the images towards the other image using the current 
estimates of the models at the given image resolution; 
(f) repeating steps (b), (c), (d) and (e) until the differnces between the 
new values of the models and the values determined in the previous 
iteration are less than a certain value or until a fixed number of 
iterations have occurred; 
(g) expanding the images to a higher resolution; and 
(h) repeating steps (b), (c), (d), (e) and (f) at the higher resolution 
using the current estimates of the models as the initial starting values. 
The invention is also an image processing system for determining the image 
sensor motion and structure of a scene comprising image sensor means for 
obtaining one or more images of a scene; means for setting the initial 
estimate of a local scene model and the motion of the image sensor at a 
first image resolution; means for warping the first image towards the 
second image using the current estimates of the local scene models and 
image sensor motion model at a first image resolution; means for refining 
all local scene models and refining the image sensor motion model by 
performing one minimization step; and iteration means for repeating steps 
(b) and (c) several times. 
In the local minimization, the global image sensor motion constraint is 
constraining the refinement of the surface parameters locally. Conversely 
in the global minimization, the local constraints provided by local image 
structures constrain the refinement of the global image sensor motion 
parameters. 
In the first part of the method, the image sensor motion constraint and the 
local image brightness derivatives are used to refine each local surface 
parameter c. The incremental image sensor motion equation (Eq. 7) can be 
rewritten for the simplified local-constant-depth model so that 
EQU du=(KTc+A.OMEGA.)-(KT.sub.0 c.sub.0 +A.OMEGA..sub.0) (15) 
At .OMEGA.=.OMEGA..sub.0 and T=T.sub.0 
EQU du.sub.0 =KT.sub.0 (c-c.sub.0) (16) 
where du.sub.0 is the incremental motion introduced by an increment in the 
parameter c. Therefore, the increment in local motion is constrained to 
lie along a line in velocity space in the direction of vector KTO (the 
image sensor motion constraint line). The vector KT.sub.0 points towards 
the current estimate of the focus-of-expansion of the image pair. 
Within a local region containing a single edge-like image structure, the 
brightness constraint equation constrains the motion to lie along a line 
in velocity space in the direction of the edge (perpendicular to 
.gradient.I). By combining the image sensor motion and brightness motion 
constraint, the surface parameter, c, is refined such that the incremental 
motion introduced by the refinement lies at the intersection of the image 
sensor motion constraint line and the local brightness constraint line. In 
this case, a local motion ambiguity arising from the aperture problem has 
been resolved using only the image sensor motion constraint. However, 
local motion ambiguities cannot be resolved using the image sensor motion 
constraint when the image sensor motion constraint line and the local 
motion constraint line are parallel. In this case, .SIGMA..sub.local 
(.gradient.I.sup.T KT.sub.0.sup.2).apprxeq.0, and the denominator in Eq. 
13 tends to zero. The physical interpretation is that the local edge 
structure is aligned in the direction of the current estimate of the 
focus-of-expansion. The local surface parameter cannot be refined reliably 
because the image sensor motion estimate adds little or no constraint to 
the local brightness constraint. In the current implementation of the 
method, the local surface parameter is not refined if the denominator in 
Eq. 13 is below a threshold. 
Within a local region containing a corner-like image structure, both motion 
components can be resolved from local information and the local brightness 
constraint constrains the incremental motion to lie at a single point in 
velocity space. However, the image sensor motion estimate constrains the 
incremental motion to lie along the image sensor motion constraint line in 
velocity space. If the point and line intersect in velocity space, then 
the incremental motion introduced by the refinement corresponds to the 
point in velocity space. If the point and line do not intersect, then the 
incremental motion lies between the line and the point in velocity space. 
Within a local region containing a single edge-like image structure, the 
brightness constraint equation (Eq. 1) shows that the error in the 
equation will remain constant for any du that is perpendicular to the 
gradient vector (.gradient.I) of the edge. As a result, only the local 
motion component normal to the edge is used to refine the global image 
sensor motion estimate. Since there is no contribution from the motion 
component along the edge direction, fewer errors in the global image 
sensor motion estimate are caused by local motion ambiguities arising from 
the aperture problem. 
Within a local region containing a corner-like image structure, both motion 
components can be resolved from only local information, and both motion 
components contribute to the refinement of the global image sensor motion 
estimate. 
We use a Gaussian or Laplacian pyramid to refine the image sensor motion 
estimate and local surface parameters at multiple resolutions. In the 
pyramid framework, large pixel displacements at the resolution of the 
original image are represented as small pixel displacements at coarse 
resolutions. Therefore, the first order Taylor's expansion of the 
brightness constancy constraint (Eq. 1--approximately true only for small 
du) becomes valid at coarse resolutions even when the image motion is 
large at the original resolution. The local depth estimates from previous 
resolutions are used to bring the image pair into closer registration at 
the next finest resolution. As a result, the first order Taylor's 
expansion is to be valid at all resolutions in the pyramid framework, 
disregarding basic violations in the brightness assumption that will occur 
at occlusion boundaries, for example. In addition, independently moving 
objects in the scene will also violate the image sensor motion constraint. 
Preliminary results have shown that the recovered image sensor motion 
estimate is not greatly sensitive to such failures in the models. 
In the image sensor motion recovery method presented here, the additional 
change in image brightness introduced by Gaussian or Laplacian blurring 
within the pyramid have not been determined. The recovered image sensor 
motion estimates are often similar at each resolution, and the error 
surfaces computed as a function of image sensor translation using a 
flow-based, multi-resolution, image sensor motion recovery method are 
similar at all resolutions. 
In FIG. 3, a feedback loop 300 for implementing the invention comprises an 
image sensor 302, such as a video camera, whose output is a sequence of 
images of a scene at a given resolution. Other types of image sensors 
include radar detectors, optical line sensors or other electromagnetic or 
sonic detectors or any other source of signals. The images are alternately 
applied by switch 304 to a first pyramid processor 306 and to a frame 
delay 308 and then to a second pyramid processor 310. Such pyramid 
processors are known in the image-processing art as shown for example by 
Anderson et al in U.S. Pat. No. 4,692,806 and by van der Wal in U.S. Pat. 
No. 4,703,514. The two pyramid processors have as their output images 
separated in time by the delay provided by the frame delay 308 and 
corresponding to the original images but at a resolution e which is 
typically less than that of the original image. The time delayed image is 
applied through a warper 312 and then to the estimator 314. While the 
warper is shown operating on the time delayed image, it can equally 
operate on the other image. The other image is applied directly to 
estimator 314. In the estimator 314 the first step the error function for 
the mismatch between the actual image motion and the models of the image 
sensor motion and the local scene structure is minimized with respect to 
each local scene model, keeping the current estimate of the global image 
sensor motion constant. In the second step the error function for the 
mismatch between the global image sensor motion and the models of the 
image sensor motion and the local scene structure is minimized with 
respect to the global image sensor motion, keeping the current estimate of 
the local scene models constant. Estimator 314 provides as its outputs 
estimates of the global motion model and the local scene structure model 
or local depth model for the images. The initiator 315 provides the 
initial constraints on the local scene structure and the global motion 
model to the estimator 314. This information may be embedded in the 
initiator 315 or may come from another sensor. The outputs of the 
estimator 314 are new estimates of the global sensor motion and the local 
scene structure model. These new estimators are then applied to 
synthesizer 316 which derives a warp-control signal which is applied to 
warper 312. The warper 312 then distorts the time delayed image, bringing 
it closer to congruence with the other image. The cycle is then repeated 
until the required number of iterations have been completed or the 
differences between the two images has been reduced below a certain value. 
The local depth model information is then available at port 318 and the 
global motion model information is available at 319. The images are then 
recalculated at a higher resolution and the iterative cycle is repeated. 
This sequence of iteration at a given resolution level and iteration at 
successively higher resolutions is repeated until the differences in the 
models between successive iterations is less than a certain value or a 
sufficient level of resolution RE has been attained. 
The image sensor motion method was tested on both natural and 
computer-rendered image sequences. The motion in the image sequences 
ranges from about 4 to 8 pixels at the original resolution, so that 
analysis at only the original resolution will be inaccurate since the 
motion will be outside the range of the incremental motion estimator. In 
the results presented here, four resolutions are used. T=(0,0,1).sup.T and 
.OMEGA.=(0,0,0).sup.T are used as the initial image sensor motion 
estimate, unless stated otherwise. All local inverse depth estimates are 
initialized to zero. 
Results of the method are shown on computer-rendered images that have size 
256.times.256 pixels, and also on natural images that have size 
256.times.240 pixels. A Laplacian pyramid was used to produce 
reduced-resolution images of size 128.times.128, 64.times.64 and 
32.times.32 pixels for the computer-rendered images, and size 
128.times.120, 64.times.60 and 32.times.30 pixels for the natural images. 
We fit the local surface models to 5 .times.5 pixel windows centered on 
each point in the image, and the image sensor motion model is fitted to 
each point in the image. For example, as part of a vehicle navigation 
system, analysis would be restricted to a number of larger local windows 
directed purposively at image regions like the road ahead or an oncoming 
object. The global image sensor model is fitted to each point in the 
image. 
We have found that the method can converge to an incorrect solution or fail 
to converge when analysis begins at a very coarse resolution 
(corresponding to 16.times.16 pixels for the image sizes presented here). 
This behavior may result from excessive blurring of the image intensities 
at very coarse scales, and also from the limited number of sample points 
at very coarse resolutions. 
FIG. 4a shows an image pair which have been synthesized and resampled from 
a known depth map and known imge sensor motion parameters. For this image 
pair, an initial image sensor motion estimate was recovered by sampling 
17.times.17=289 translation values at the coarsest resolution. FIG. 4b 
shows the difference image between the original image pair. FIG. 4c shows 
the image of the local surface parameters (inverse depths) such that 
bright points are nearer the image sensor than the dark points. The bottom 
portion of the image shows a surface sloping away from the camera towards 
a ridge at which point the depth changes rapidly. The very top of the 
image shows the parameters recovered at a blank portion of the image where 
there is no texture. FIG. 4d shows the difference image between the second 
image and the first image after motion compensation. Note that there are 
few intensity differences indicting that the model has succesfully been 
fit to the image pair. In the foregoing portion of the scene, the rms 
error in the estimated depths is approximately 1%. In the background 
portion of the scene (just over the ridge) the error is much larger, and 
measurement in a 100.times.15 window gives an rms error of approximately 
8%. This difference is explained by observing that in both regions the 
difference between the actual motion and the recovered motion is 
approximately 0.05-0.1 pixels, whereas the actual motion is approximately 
4-8 pixels in the foregoing, and approximately 1 pixel in the background. 
We expect such accuracy in the recovered motion in the foreground and 
background portions of the image since the image is heavily textured 
there, but there are large errors in the recovered depth and motion at the 
very top of the image where there is no texture at all. 
FIG. 4e shows the recovered image sensor motion at each resolution and also 
the actual image sensor motion. The estimate of the image sensor motion 
components at the final resolution is very close to the actual image 
sensor motion of the camera despite an occlusion boundary across the 
center of the image where the brightness constancy assumption is violated. 
In general, the least squares minimization technique should be sensitive 
to measurement outliers that might be introduced by such deviations in the 
model. Similar robustness to measurement outliers has also been observed 
in other motion fitting techniques that use the same incremental motion 
estimator (Eq. 1) within the same coarse-fine analysis framework. 
FIG. 5a shows the second image of a road sequence where there is less image 
texture, where the image center has been estimated, and where the camera 
motion is unknown. The image motion is the foreground is approximately 9 
pixels towards the image sensor. FIG. 5b shows the difference image 
between the original images. Note there are few differences except in the 
foreground and at the top left hand corner of the image. FIG. 5c shows the 
inverse depth image recovered at the finest resolution. In this case the 
inverse depth parameters are more noisy since there are fewer features in 
the image. The depth parameters are plausible near the drain-hole in the 
image foreground, but are not plausible along most the white line to the 
left of the image since the image structure in parallel to the load 
ego-motion constrain line given the vehicle's motion. FIG. 5d shows the 
difference image between the second and the first image after motion 
compensation. Note that there are few intensity differences despite the 
errors in the recovered depths. 
FIG. 6a shows the second image of a natural image pair where the image 
center has been estimated, and where the precise image sensor motion is 
unknown. The image motion in the foreground is approximately 5 pixels 
towards the image sensor, FIG. 6b shows the difference image between the 
two original images. FIG. 6c shows the inverse depth image recovered at 
the finest resolution. The recovered depths ate plausible almost 
everywhere except at the image border and near the recovered focus of 
expansion (near the gate at the image center). The bright dot at the 
bottom right hand side of the inverse depth map corresponds to a leaf in 
the original image that is blowing across the ground towards the image 
sensor. We might expect such plausible results from a scene that is 
heavily textured almost everywhere. FIG. 6d shows the difference image 
between the second and first images after motion compensation. FIG. 6e 
shows the computed image sensor motion at each resolution. The initial 
image sensor motion estimate is close to the estimates recovered at the 
two finest scales, yet the recovered estimates are different at the two 
coarsest resolutions. At these coarse resolutions, the minimization 
procedure followed a low-gradient, incorrect direction in the error 
surface that led to the incorrect estimates. While this shows how the 
estimation procedure can recover from following the incorrect, 
minimization path, it also shows how thw error surfaces can differ very 
slightly between resolutions due to differences introduced by image 
blurring. 
FIG. 7 presents the results for another road sequence. In this case the 
recovered solutions remain close to the initial image sensor motion 
estimate. The inverse depth parameters corresponding to the top portion of 
the image (sky) are clearly incorrect, and in fact the local surface 
parameters should probably not be refined in image regions containing such 
small gradients, but for the same reason, such regions have minimal effect 
on the recovered image sensor motion estimate. We determined that the 
focus of expansion to lie at the end of the visible portion of the road, 
at the road center. 
An iterative, multi-resolution method that estimates image sensor motion 
directly from image gradients in two images, and how constraints from 
different local image structures interact with the image sensor motion 
constraint is disclosed. The image sensor motion and depths were recovered 
quite accurately in the computer rendered example, and the recovered image 
sensor motion and depths appeared plausible in the natural image sequences 
where ground truth was unavailable. 
The main advantages of the multi-resolution analysis disclosed here over 
existing single-resolution analyses are: 
a) Increased range of motion: At the resolution of the original image, 
limitations on the fitting model means that motions of greater than 
approximately 1 image pixel cannot be measured accurately. Using 
multi-resolution analysis, our range of motion is increased to 
approximately 16 pixels (or more) at the resolution of the original image. 
This allows the image sensor motion and scene-structure recovery methods 
to be used for applications in which single-resolution analysis would not 
work. In fact, image disparity or image motion is greater than a pixel in 
many, if not most, applications. 
b) Accuracy of motion estimates: Because results from previous resolutions 
are used to update image sensor motion and scene-structure estimates at 
the next finest resolution, the estimates of image sensor motion and scene 
structure at the finest resolution (the resolution of the original images) 
are significantly more accurate than in single-resolution analysis where 
estimates are computed only at the resolution of the original images 
without refining previous estimates. 
c) Efficiency of method: At coarse resolutions, the representation of the 
image is small so the method runs very quickly at such resolutions. We can 
stop processing at a coarse resolution if our refined estimates of image 
sensor motion and scene-structure are sufficiently accurate for a 
particular task. Compared to single-resolution analysis, therefore, there 
is flexibility in trading hardware resources and/or computing power versus 
accuracy of the image sensor motion and scene-structure estimates. 
In summary, because of multi-resolution refinement (as well as single 
resolution refinement) of the depth and image sensor motion estimates, the 
warped depth approach is much more accurate than alternative approaches; 
because of multi-resolution analysis, the allowable range of motion over 
which the method works is much greater than many alternative methods. As a 
result, the warped depth method can be used in many applications where 
alternative methods cannot be used and the method is efficient. As a 
result, real-time implementation in hardware and software is relatively 
simple. 
The image sensor motion and scene-structure models do not have to be fitted 
to the entire images; specific regions can be selected and processing is 
only performed in those regions. The coarse-fine resolution refinement of 
image sensor motion and scene-structure estimates can be extended to 
include refinement over time; that is refine the estimates over an image 
sequence rather than just an image pair. This method can be applied to 
many problems that require estimation of scene-structure and/or image 
sensor motion from two of more image pairs. Applications include vehicle 
navigation, obstacle detection, depth recovery and image stabilization. 
The method disclosed here made use of local image brightness and image 
brightness derivatives as the local scene characteristic or constraint. It 
is understood that other image characteristics can also be used in the 
method of the invention. It is also understood that methods other than 
pyramid processing for expanding the local local scene characteristic 
characteristics into a higher resolution can be used.