Image processing apparatus and method Number:7,149,327 from the United States Patent and Trademark Office (PTO) owispatent Image processing apparatus transforms an input image from a first camera by using a parameter of affine transformation based on a position of a second camera. The first camera and the second camera are loaded onto a vehicle respectively and input an image of a road plane in time series. A status prediction unit predicts a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1). A parallel moving vector estimation unit estimates a parallel moving vector of timing (t) included in the parameter of affine transformation by using an input image of timing (t) from the first camera, an input image of timing (t) from the second camera, and the temporary status information. A status estimation unit estimates a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information.<H processing, apparatus, Image, processin, 7149327.html, Patent, pto, 7149327

Title: Image processing apparatus and method

Abstract: Image processing apparatus transforms an input image from a first camera by using a parameter of affine transformation based on a position of a second camera. The first camera and the second camera are loaded onto a vehicle respectively and input an image of a road plane in time series. A status prediction unit predicts a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1). A parallel moving vector estimation unit estimates a parallel moving vector of timing (t) included in the parameter of affine transformation by using an input image of timing (t) from the first camera, an input image of timing (t) from the second camera, and the temporary status information. A status estimation unit estimates a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information.

Patent Number: 7,149,327 Issued on 12/12/2006 to Okamoto, et al.

Inventors: Okamoto; Yasukazu (Hyogo-ken, JP), Takeda; Nobuyuki (Kanagawa-ken, JP)
Assignee: Kabushiki Kaisha Toshiba (Tokyo, JP)

Appl. No.: 10/391,626

Filed: March 20, 2003

Foreign Application Priority Data


Mar 28, 2002 [JP]			2002-092980

Current U.S. Class: 382/104 ; 340/939; 382/294

Current International Class: G06K 9/00 (20060101); G06K 9/32 (20060101); G08G 1/01 (20060101)

Field of Search: 382/104,154,190,294 340/937,939 348/118

References Cited [Referenced By]

U.S. Patent Documents


6385334	May 2002	Saneyoshi et al.
6535114	March 2003	Suzuki et al.
6577952	June 2003	Geier et al.
6985619	January 2006	Seta et al.

Foreign Patent Documents


2001-76128	Mar., 2001	JP
2001-243456	Sep., 2001	JP
2001243456	Sep., 2001	JP

Other References

Zomet et al., "Omni-Rig: Linear Self-calibration of a Rig with Varying Internal and External Parameters," Proceedings 5.sup.th IEEE International Conference on Computer Vision, Jul. 7-14, 2001, vol. 1, pp. 135-141. cited by examiner .
U.S. Appl. No. 09/779,619, filed Feb. 9, 2001, Takeda et al. cited by othe- r .
U.S. Appl. No. 10/391,626, filed Mar. 20, 2003, Okamoto et al. cited by other.

Primary Examiner: Wu; Jingge
Assistant Examiner: Hung; Yubin
Attorney, Agent or Firm: Oblon, Spivak, McClelland, Maier & Neustadt, P.C.

Claims

What is claimed is:

1. An image processing apparatus for transforming an input image from a first camera by using a parameter of affine transformation based on a position of a second camera, comprising: a status prediction unit configured to predict a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1); a parallel moving vector estimation unit configured to estimate a parallel moving vector of timing (t) included in the parameter of affine transformation by using a first camera input image of timing (t), a second camera input image of timing (t), and the temporary status information; and a status estimation unit configured to estimate a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information of the vehicle of timing (t).

2. The image processing apparatus according to claim 1, wherein the first camera and the second camera, respectively, have a different view position each of which projecting an optical axis onto the road plane that is almost parallel to a moving direction of the vehicle.

3. The image processing apparatus according to claim 2, wherein the first camera input image and the second camera input image, respectively, represents the road plane along the moving direction of the vehicle.

4. The image processing apparatus according to claim 3, wherein the first camera is one of a right side camera and a left side camera loaded on the vehicle, and the second camera is the other of the right side camera and the left side camera.

5. The image processing apparatus according to claim 1, further comprising a status memory being configured to store initial values of a status vector and a covariance matrix of each element of the status vector, the initial values being calculated by calibration of the first camera and the second camera loaded onto the vehicle.

6. The image processing apparatus according to claim 5, wherein said status prediction unit predicts a temporary status vector of timing (t) and a temporary covariance matrix of timing (t) by using the initial values of the status vector and the covariance matrix stored in said status memory.

7. The image processing apparatus according to claim 6, wherein said status prediction unit calculates a Kalman gain of timing (t) by using the temporary covariance matrix of timing (t).

8. The image processing apparatus according to claim 7, wherein said parallel moving vector estimation unit includes an image transformation unit being configured to calculate a prediction value of the parallel moving vector of timing (t) by using the temporary status vector of timing (t), and to calculate a probability distribution of the prediction value by using the temporary covariance matrix of timing (t) and the prediction value of the parallel moving vector of timing (t).

9. The image processing apparatus according to claim 8, wherein said image transformation unit selects a candidate parallel moving vector from candidate values based on the probability distribution in an order, calculates the parameter of affine transformation based on a view position of the second camera by using the selected candidate parallel moving vector, and transforms the first camera input image of timing (t) by using the parameter of affine transformation.

10. The image processing apparatus according to claim 9, wherein said parallel moving vector estimation unit includes an image matching unit being configured to extract a matching area from the transformed image and the second input image of timing (t), the matching area being almost part of a road area based on one from the group of intensity and texture, and to correct brightness of two matching areas.

11. The image processing apparatus according to claim 10, wherein said image matching unit calculates a matching similarity by comparing the matching area from the transformed image and the second input image of timing (t), and sets the parallel moving vector used for the transformed image of which the matching similarity is at least a preferred value as the parallel moving vector of timing (t).

12. The image processing apparatus according to claim 11, wherein, if the matching similarity is not the at least the preferred value, said image matching unit repeatedly calculates the matching similarity by comparing a matching area of a transformed image based on a next parallel moving vector with the matching area of the input image from the second camera.

13. The image processing apparatus according to claim 12, wherein said status estimation unit estimates a status vector of timing (t) and a covariance matrix of timing (t) by using the parallel moving vector of timing (t), the temporary status vector of timing (t) and the temporary covariance matrix of timing (t).

14. The image processing apparatus according to claim 13, wherein said status estimation unit calculates the status vector of timing (t) and the covariance matrix of timing (t) in accordance with a Kalman filter including the Kalman gain of next timing.

15. The image processing apparatus according to claim 13, wherein said status memory stores the status vector of timing (t) and the covariance matrix of timing (t) in place of previous values of the status vector and the covariance matrix.

16. The image processing apparatus according to claim 15, wherein, whenever said status memory newly stores the status vector of next timing and the covariance matrix of next timing, said status prediction unit, said parallel moving vector estimation unit and said status estimation unit, recursively execute respective processing.

17. The image processing apparatus according to claim 16, wherein said status memory updates the status vector and the covariance matrix stored in said status memory at each timing.

18. The image processing apparatus according to claim 17, further comprising a road plane estimation unit being configured to calculate a tilt of a road plane using the status vector stored in said status memory at each timing.

19. An image processing method for transforming an input image from a first camera by using a parameter of affine transformation based on a position of a second camera, comprising: predicting a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1); estimating a parallel moving vector of timing t included in the parameter of affine transformation by a first camera input image of timing (t), a second camera input image of timing (t), and the temporary status information; and estimating a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information of the vehicle of timing (t).

20. A computer program product, comprising: a computer readable medium storing a computer program for causing a computer to transform an input image from a first camera by using a parameter of affine transformation based on a position of a second camera, said computer program comprising: a first program code to predict a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1); a second program code to estimate a parallel moving vector of timing (t) included in the parameter of affine transformation by using a first camera input image of timing (t), a second camera input image of timing (t), and the temporary status information; and a third program code to estimate a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information of the vehicle of timing (t).

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is based upon and claims the benefit of priority from the prior Japanese Patent Application P2002-092980, filed on Mar. 28, 2002; the entire contents of which are incorporated herein by reference.

FIELD OF THE INVENTION

The present invention relates to an image processing apparatus and a method for estimating a transformation parameter used for transforming an input image in order to detect an obstacle object on a road.

BACKGROUND OF THE INVENTION

A technique to detect an obstacle is classified into a first one using a laser or a supersonic wave and a second one using a TV camera. In the first one, the laser can be expensive and resolution of the supersonic wave may be low. Accordingly, accuracy to detect the obstacle may become a problem. Furthermore, an active sensor using the laser or the supersonic wave cannot independently recognize a traveling lane.

On the other hand, in the second one, the TV camera is relatively cheap and suitable for obstacle detection from the viewpoint of resolution, measurement accuracy and measurement-limit. Furthermore, recognition of the traveling lane is possible. In case of using the TV camera, there is a method using one camera and another method using a plurality of cameras (stereo camera). In the method using one camera, a road area and an obstacle area are separated from an input image through the one camera according to information such as intensity, a color or a texture. For example, the road area is detected by extracting an intensity area of low brightness (gray area) from the image. Furthermore, the road area is detected by extracting an area of few textures from the image, and the other area is detected as the obstacle area. However, many obstacles having the intensity, the color or the texture similar to the road exist. Accordingly, it may be impossible to separate the obstacle area from the road area by this method.

In another method using a plurality of cameras, the obstacle area is detected according to three-dimensional information. In general, this method is called "stereo view". In the stereo view, for example, two cameras are located at the left side and the right side of a vehicle along a moving direction on a road plane. The same point is projected onto the left image and the right image in three-dimensional space. A three-dimensional position of the same point is calculated by a triangulation method. If a position and a direction of each camera for the road plane are previously calculated, a height from the road plane of arbitrary point on the image can be detected by the stereo view. In this way, the obstacle area and the road area can be separated by the height. In the stereo view, a problem in the case using one camera can be avoided.

However, in ordinary stereo view, a problem exists when searching for the corresponding point. In general, the stereo view is a technique to detect a three-dimensional position of an arbitrary point on the image based on a coordinate system fixed to a stereo camera (The coordinate system is called a "world coordinate system"). The search for the corresponding point means a search calculation necessary to correspond the same point in space between the left image and the right image. Because the calculation cost is extremely high, a problem exists. The search for the corresponding point is a factor to prevent realization of stereo view.

On the other hand, another method to separate the obstacle area from the road area is disclosed in Japanese Patent Disclosure (Kokai) P2001-76128 and P2001-243456. In this method, a point in one of the left image and the right image is assumed to exist in the road plane. A parameter to transform the point to a projection point on the other of the left image and the right image is included. The one image is transformed by using the parameter, and the obstacle area is separated from the road area by using a difference between the transformed image and the other image.

In certain situations, such as when a vehicle passes a road including bumps, when a loading condition of persons or a carrying condition of baggage within the vehicle changes, when the vehicle vibrates, or when the road tilts, the position and direction of the cameras (i.e., tilt of the road plane based on the vehicle) changes. Additionally, in those situations, the value of the transformation parameter also changes.

In Japanese Patent Disclosure (Kokai) P2001-76128, transformation parameter of the image is calculated using two white lines drawn on the road. However, in this method, if one white line is only viewed or the two white lines become dirty, the transformation parameter cannot be calculated.

In Japanese Patent Disclosure (Kokai) P2001-243456, a plurality of suitable directions are selected from a limit of relative location between the camera and the road plane. A transformation parameter corresponding to each of the plurality of suitable directions is then calculated. One image is transformed by using the transformation parameter, the transformed image is compared with the other image, and an area of the lowest similarity is detected as the obstacle object from the image. In this method, in case of matching the transformed image with the other image as a road plane, the area of the lowest similarity is detected. Accordingly, the obstacle object is not often detected when periodical pattern is drawn on the vehicle or a road surface is reflected by rain. In this case, the transformation parameter of the road plane is necessary.

In order to accurately detect the obstacle object, a selected transformation parameter must be within an actual transformation parameter by a sufficient accuracy. Furthermore, for example, when heavy baggage is carried on the rear part of the vehicle, the body of the vehicle often leans from the front to the rear. Briefly, transformation parameter based on event of low generation possibility is also necessary. In order to satisfy the above-mentioned two conditions, many transformation parameters are necessary. As a result, the creation of many transformed images greatly costs calculation time.

Furthermore, except for a sudden vibration by a difference in the level of the road, a change of vibration of the vehicle and a change of tilt of the road plane are slow in comparison with the input interval of a TV image, and the loading condition of persons or the carrying condition of baggage does not change during the vehicle's traveling. Accordingly, the transformation parameter of the image smoothly changes under such vibration and tilt conditions. However, in above-mentioned method, the status of the current transformation parameter is not taken into consideration, and transformed images using each of all transformation parameters are respectively prepared. As a result, a problem exists with executing useless transformations.

As mentioned-above, in the prior art, it is assumed that an input image through the TV camera includes the road plane. When an image input from one camera is transformed (projected) onto an image input from another camera, the transformation parameter is calculated using the white line. However, if the white line is not included in the image, the transformation parameter cannot be calculated.

Furthermore, in a method for preparing a large number of transformation parameters and detecting an obstacle area of the lowest similarity by comparing the transformed one image with the other image, it is necessary to prepare each transformation parameter of various events of which generation possibility is low. Creation of each transformed image greatly takes calculation time. In addition to this, the current status of the vehicle is not taken into consideration in the prepared transformation parameter. Accordingly, useless transformation is largely executed.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide an image processing apparatus and a method for certainly estimating the transformation parameter to transform an input image from a first camera onto another input image from a second camera when each camera is loaded on the vehicle, even if a tilt of the road plane changes based on a status of the vehicle.

In accordance with the present invention, there is provided an image processing apparatus for transforming an input image from a first camera by using a parameter of affine transformation based on a position of a second camera. The first camera and the second camera are loaded onto a vehicle, respectively, and input an image of a road plane in time series. The apparatus comprises a status prediction unit configured to predict a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1); a parallel moving vector estimation unit configured to estimate a parallel moving vector of timing (t) included in the parameter of affine transformation by using an input image of timing (t) from the first camera, an input image of timing (t) from the second camera, and the temporary status information; and a status estimation unit configured to estimate a status information of the vehicles of timing (t) by using the parallel moving vector and the temporary status information.

Further in accordance with the present invention, there is also provided an image processing method for transforming on input image from a first camera by using a parameter of affine transformation based on a position of a second camera. The first camera and the second camera are loaded onto a vehicle respectively input an image of a road plane in the series. The method comprises predicting a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1); estimating a parallel moving vector of timing (t) included in the parameter of affine transformation by an input image of timing (t) from the first camera, on input image of timing (t) from the second camera, and the temporary status information; and estimating a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information.

Further in accordance with the present invention, there is also provided a computer program product, comprising: a computer readable program code embodied in said product for causing a computer to transform in input image from a first camera by using a parameter of affine transformation based on a position of a second camera. The first camera and the second camera are loaded onto a vehicle respectively input an image of a road plane in time series. The computer readable program code comprises a first program code to predict a temporary status information of the vehicle of timing (t) by using a status information of the vehicle of timing (t-1); a second program code to estimate a parallel moving vector of timing, (t) included in the parameter of affine transformation by using an input image of timing (t) from the first camera, an input image of timing (t) from the second camera, and the temporary status information; and a third program code to estimate a status information of the vehicle of timing (t) by using the parallel moving vector and the temporary status information.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of an image processing apparatus according to one embodiment of the present invention.

FIG. 2 is a schematic diagram of position relation between the road plane and two cameras.

FIG. 3 is a schematic diagram of projection system of the camera onto the road plane.

FIG. 4 is a schematic diagram of moving direction of a vanishing point based on matching images at timings (t-1) and (t).

FIG. 5 is a schematic diagram of probability distribution of prediction value of parallel moving vector.

FIG. 6 is a schematic diagram of a matching area on the image.

FIG. 7 is a schematic diagram of a processing step of an image matching unit according to one embodiment of the present invention.

FIG. 8 is a flow chart of estimation processing of a status vector and a covariance matrix according to one embodiment of the present invention.

FIG. 9 is a schematic diagram of calculation of coefficient value necessary for estimating a tilt of the road plane according to one embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Hereinafter, various embodiments of the present invention will be explained by referring to the drawings.

In the image processing apparatus according to one embodiment of the present invention, two stereo cameras (a left side camera and a right side camera) are loaded onto the vehicle. While the vehicle is traveling on the road, the image processing apparatus is used for detecting an obstacle object, such as another vehicle or a pedestrian.

(1) Component of the Image Processing Apparatus:

FIG. 1 is a block diagram of the image processing apparatus according to one embodiment of the present invention. As shown in FIG. 1, the image processing apparatus consists of an image input unit 1, an image memory 2, an image transformation unit 3, an image matching unit 4, a status estimation unit 5, a status memory 6, and a status prediction unit 7. A function of each unit 1.about.7 is realized by a computer program.

The image input unit 1 inputs stereo images (a left image and a right image) of a front scene or a rear scene of the vehicle traveling on the road. The stereo images are photographed by two cameras (the left side camera and the right side camera) loaded on the vehicle. In this embodiment, as the simplest example, the left image input from the left side camera is transformed (projected) onto the right image input from the right side camera. However, the right image input from the right side camera may be transformed onto the left image input from the left side camera in other embodiments. Furthermore, if a plurality of cameras more than two units is loaded on the vehicle, another embodiment of the present invention can be applied to transformation between two camera images having a common view.

The image memory 2 stores the left image and the right image from the image input unit 1.

In the image transformation unit 3, the left image is assumed as an image of the road plane in the image memory 2, and the left image is respectively transformed using each of a plurality of transformation parameters.

In the image matching unit 4, the left image transformed by the image transformation unit 3 is compared with the right image, and the transformation parameter used for the left image of best matching is output.

In the status estimation unit 5, the status memory 6 and the status prediction unit 7, the transformation parameter selected by the image matching unit 4 is input, and a status information to estimate the present road plane is calculated using Kalman filter based on the transformation parameter. Briefly, change of geometrical relationship between the camera and the road plane by a vibration of the vehicle means a change of a tilt of the road plane based on the camera loaded on the vehicle. The status estimation unit 5, the status memory 6 and the status prediction unit 7, estimates the tilt of the road plane for the vehicle.

The status memory 6 stores the present status information of the vehicle.

The status estimation unit 5 updates the status information of the vehicle stored in the status memory 6 by using the transformation parameter output from the image matching unit 4.

In the status prediction unit 7, status information of timing (t) of new input image is predicted from the status information of previous timing (t-1) stored in the status memory 6 by using a prediction expression of Kalman filter. This predicted status information is called temporary status information. The temporary status information is output to the image transformation unit 3.

(2) The Image Transformation of the Prior Art and the Problem:

Next, the prior art and the problem are explained where one camera image is transformed based on a view position of the other camera. This is guided from geometrical relationship between the road plane and two cameras.

First, as shown in FIG. 2, two cameras are located on the road plane. Assume that a projection coordinate of a three-dimensional point "P=(x, y, z)" onto the left image is (u, v). In general, the following expression (1) is concluded in perspective transformation.

.times..times..times..times..times..times..times..times..times..times..tim- es..times..times. ##EQU00001##

In one example, a position "P=(X, Y, 0)" on the road plane in which "Z=0" is supposed. Accordingly, the relationship of the projection point is represented as follows.

.times..times..times..times..times..times..times..times..times. ##EQU00002##

In the expression (2), "h.sub.11.about.h.sub.34" are parameters determined by position and direction of the camera for world coordinate axis "XYZ", the focal distance of camera lens, and the origin of the image. A multiple of the parameters "h.sub.11.about.h.sub.34" represents the same camera model. In other words, even if one of "h.sub.11.about.h.sub.34" is set as "1", characteristic of the camera model is maintained. Accordingly, hereinafter "h.sub.32" is set as "1".

As shown in FIG. 3, a denominator "d=h.sub.31X+h.sub.32Y+h.sub.34" of the expression (2) represents a distance along an optical direction between the camera view position C and a road position P, i.e., a depth. In the present example apparatus of FIG. 3, the stereo camera is located in a condition that the optical axis is almost perpendicular to the X axis. In other words, the projection of the optical axis onto the road plane is parallel to the moving direction of the vehicle. Concretely, the depth d does not depend on X. Accordingly, the expression (2) is approximated in a condition that "h.sub.31=0" as follows,

.times..times..times..times..times. ##EQU00003##

The expression (3) is represented in a condition that "Yc=Y+h.sub.34" as follows.

.fwdarw..times..times..times..times..times. ##EQU00004##

When a coordinate of a vanishing point (a projection of infinite distance point as "Y=.infin.") is "{right arrow over (t)}=(u.sub.0, v.sub.0).sup.T", "{right arrow over (t)}=(h.sub.12, h.sub.22).sup.T" is guided from the expression (4). Assuming that a matrix of the right side of the expression (4) is M and

.times..fwdarw..times. ##EQU00005## the following expression is concluded. {right arrow over (u)}-{right arrow over (t)}=M{right arrow over (X)} (5)

This relationship is applied to both the left image and the right image. Assuming that the projection point of the point P of the road plane onto the left image and the right image is {right arrow over (u)}.sub.l, {right arrow over (u)}.sub.r, the following expressions are concluded. {right arrow over (u)}.sub.l-{right arrow over (t)}.sub.l=M.sub.l{right arrow over (X)}, {right arrow over (u)}.sub.r-{right arrow over (t)}.sub.r=M.sub.r{right arrow over (X)} (6) {right arrow over (u)}.sub.r-{right arrow over (t)}.sub.r=A({right arrow over (u)}.sub.l-{right arrow over (t)}.sub.1), (A=M.sub.rM.sub.l.sup.-1) (7)

Accordingly, it is apparent that the left image and the right image each including the road plane are mutually related as an affine transformation.

A transformation parameter of the expression (7) is calculated by a calibration operation. Concretely, at a timing when two cameras (the left side camera and the right side camera) are loaded on the vehicle, the vehicle is located on a horizontal flat road plane and the two cameras respectively input the road plane image. A coordinate of the same point on the road plane is detected from the left image and the right image. The transformation parameter can be calculated by more than three pairs of the coordinates on the left image and the right image. In one example, by using larger number of the coordinates, a suitable parameter is calculated based on method of least squares. Furthermore, if the vehicle is located on the center of two white lines (a left side white line and a right side white line) along advance direction of the straight road, a coordinate of a vanishing point vector can be calculated using a cross point of the left side white line and the right side white line.

(3) Change of Image in a Case of Changing the Road Plane:

Next, assume that the road plane changes from "Z=0" to "Z=pY" by tilt of the road plane or vibration of the vehicle. Concretely, when the vehicle passes a road of ups and downs, when the loading condition of persons or carrying condition of baggage onto the vehicle changes, or when the vehicle vibrates or the road tilts, the relationship of position and direction between the camera of the vehicle and the road plane changes. Briefly, a tilt of the road plane based on the vehicle changes and contents of the image often change by vibration of top and bottom direction. In this case, the expression (3) of "Z=0" is represented as follows.

'.times..times..times..times.'.times..times..times. ##EQU00006##

When "Yc=Y+h.sub.34", the following expression is concluded.

''.times..function..times..function..times. ##EQU00007##

When a coordinate of the vanishing point is "{right arrow over (t)}'=(u.sub.0', v.sub.0').sup.T", "{right arrow over (t)}'=(h.sub.12+ph.sub.13, h.sub.22+ph.sub.23).sup.T" is concluded from the expression (9). Accordingly, as shown in FIG. 4, the vanishing point moves along a straight line by tilt of the road plane or vibration of the vehicle. Furthermore, the expression (9) is represented using the vanishing point as follows.

.fwdarw.''.times..times.'.times..times.'.times.'' ##EQU00008##

Assuming that .DELTA.{right arrow over (u)}={right arrow over (u)}-{right arrow over (t)}, .DELTA.{right arrow over (u)}'={right arrow over (u)}'-{right arrow over (t)}', .DELTA.u.sub.0=u.sub.0-u.sub.0', .DELTA.v.sub.0=v.sub.0-v.sub.0', following expression is concluded.

.DELTA..times..times..fwdarw..times..times..times..times..times..function.- '.function.'.times..times..times..fwdarw..function..DELTA..DELTA..times..f- wdarw..DELTA..times..times..fwdarw..times..DELTA..times..times. ##EQU00009##

Further assumptions may be made that {right arrow over (X)}=M.sub.-1.DELTA.{right arrow over (u)} and a matrix value is as follows.

##EQU00010##

In this case,

.times..times..times..DELTA..times..times..times..DELTA..times..times. ##EQU00011## is guided. Accordingly, following expression is concluded.

.DELTA..times..times..fwdarw..times..times..DELTA..times..times..times..ti- mes..DELTA..times..times..times..times..times..DELTA..times..times..times.- .times..times..DELTA..times..times..times..DELTA..times..times..fwdarw. ##EQU00012##

In the above expression (13), if a yaw angle (rotation around vertical axis) of the vehicle is very small, h.sub.34 is also small value. Accordingly, even if the tilt of the road or vibration of the vehicle occurs, .DELTA.{right arrow over (u)}' is almost equal to .DELTA.{right arrow over (u)}, and image transformation does not occur by tilt of the road plane.

From the above-mentioned explanation of geometrical relationship between the road plane and the camera, the left image and the right image are mutually related as affine transformation. In other words, image deformation does not occur by tilt of the road or vibration of the vehicle. From this conclusion that image deformation does not occur, when the road plane changes from "Z=0" to "Z=pY", the relationship between the left image and the right image is represented as follows in the same way of the expression (7). {right arrow over (u)}.sub.r'-{right arrow over (t)}.sub.r'=A({right arrow over (u)}.sub.l'-{right arrow over (t)}.sub.l') (13-A)

Furthermore, from the expressions (4) and (9), a position of the vanishing point changes as "{right arrow over (t)}'={right arrow over (t)}+p{right arrow over (d)} ({right arrow over (d)}=(h.sub.13,h.sub.23).sup.T)" by tilt of the road plane. Accordingly, the expression (13-A) is represented as follows. {right arrow over (u)}.sub.r'-{right arrow over (t)}.sub.r=A({right arrow over (u)}.sub.l'-{right arrow over (t)}.sub.l)+p({right arrow over (d)}.sub.r+A{right arrow over (d)}.sub.l) (13-B)

From this expression (13-B), it is found that a parallel moving vector changes by tilt of the road plane and a direction of change quantity of the parallel moving vector is fixed. In this case, assume that elements changed by tilt of the road in the parallel moving vector is (.alpha., .beta.). From the expression (13-B), (7) and (.alpha., .beta.), affine transformation between the left image and the right image is represented as follows. {right arrow over (u)}.sub.r'-{right arrow over (t)}.sub.r=A({right arrow over (u)}.sub.l'-{right arrow over (t)}.sub.l)+(.alpha., .beta.).sup.T (13-C)

In the expression (13-C), values of constants "A, {right arrow over (t)}.sub.r, {right arrow over (t)}.sub.l" are previously calculated. Concretely, a vehicle is located on a horizontal road plane. Two cameras (the left side camera and the right side camera) loaded on the vehicle inputs the horizontal road plane. A position of a feature point on the road plane is corresponded between the left image and the right image. The values of constants "A, {right arrow over (t)}.sub.r, {right arrow over (t)}.sub.l" are calculated by a pair of coordinates of a plurality of feature points between the left image and the right image. Accordingly, affine transformation parameter for tilt of the road can be calculated by the expression (7) and (.alpha., .beta.)

(4) Function of the Image Transformation Unit 3:

As mentioned-above, if the road and the vehicle are horizontal, affine transformation parameter to transform the left image is calculated by a calibration operation. Furthermore, even if the road or the vehicle tilts, the affine transformed image changes in that it parallely moves along a fixed direction occurs only. Accordingly, in the image transformation unit 3, the left image is transformed from a viewpoint of the right image (the right camera) by using the transformation parameter of which parallel moving vector (.alpha., .beta.) variously changes. One parallel moving vector of best matching similarity is regarded as the parallel moving vector (.alpha., .beta.) to be searched.

The distribution of prediction value Y of the two-dimensional parallel moving vector is represented as a two-dimensional normal distribution Z(Y) using an average "Y.sub.t/.sub.t-1=(.alpha..sub.t, .beta..sub.t).sup.T" and a prediction covariance matrix Pt as follows.

.function..times..pi..times..function..times..times..function. ##EQU00013##

In the expression (14), "Y.sub.t/.sub.t-1" is calculated by applying h.sub.t of expression (24) to a prediction value X.sub.t/.sub.t-1 of status vector as explained later. Subscript ".sub.t/.sub.t-1" of "Y.sub.t/.sub.t-1" means a prediction value Y of the next timing (t) at present timing (t-1). In the same way, "X.sub.t/.sub.t-1" and "P.sub.t/.sub.t-1" means each prediction value.

Hereinafter, each sign of covariance matrix P, status vector X, parallel moving vector Y and two-dimensional normal distribution Z is different from each sign of the above-mentioned three-dimensional point "P=(X, Y, Z)". Furthermore, a hat sign "^" of "{circumflex over (P)}t, {circumflex over (F)}, H" means a prediction value.

In the image transformation unit 3, g.sub.i=(.alpha..sub.i, .beta..sub.i) (i=1.about.n) of a fixed number (n units) is selected according to a probability distribution of the expression (14). For example, "g.sub.i" may be selected at random according to the probability distribution or may be selected in order by equal probability. Next, the transformation parameter is calculated by selected g.sub.i=(.alpha..sub.i, .beta..sub.i) and the expression (7), and the left image is transformed from a viewpoint of the right image (right side camera) by using the transformation parameter.

FIG. 5 shows an example of random sample (candidate values) of prediction value based on probability distribution. In FIG. 5, an ellipse is represented by a counter line linking coordinates of equal probability as a two-dimensional normal distribution. The possibility of a candidate value (random sample) in the ellipse is higher than the possibility of a candidate value outside the ellipse. If the candidate value is selected according to the probability distribution, the candidate value is densely sampled in the high probability area and the candidate value is sparsely sampled in the low probability area. Accordingly, in the high probability area, the transformation parameter can be estimated finely.

Each selected g.sub.i(i=1.about.n) is arranged in order of nearer value from a prediction valve "Y.sub.t/.sub.t-1=(.alpha..sub.t, .beta..sub.t).sup.T" shown in FIG. 5. The transformation parameter is calculated using each g.sub.i(i=1.about.n) in order of arrangement. The left image is transformed using each transformation parameter in order, and each transformed image is output to the image matching unit 4. If a size of the image is small and the creation time of the transformed image is short, gi may be selected at a predetermined interval without the probability distribution of the expression (14).

(5) Function of the Image Matching Unit 4:

In the image matching unit 4, the left image transformed by the image transformation unit 3 is compared (matched) with the right image. In this case, assume that the left image is I.sub.l and the right image is I.sub.r.

(5-1) Creation of Matching Area:

First, an area including the most part of the road area is selected from the left image as a matching area R.sub.l. The matching area may be dynamically set by using extraction result of the vehicle or the white line drawn on boundary of the road. Otherwise, as shown in FIG. 6, by the user's indication of an area including the most part of the road plane, the indicated area may be set as the matching area. In the image transformation unit 3, the matching area R.sub.l is transformed by using the transformation parameter. In an embodiment shown in FIG. 7, the left image I.sub.l is transformed by using the transformation parameter. This transformed left image is set as an image I.sub.l'. The matching area R.sub.l can be transformed in the same way of the left image I.sub.l. Accordingly, the transformed matching area is set as a matching area R.sub.l'. Furthermore, a matching area R.sub.r is extracted from the right image I.sub.r. In this embodiment, assume that pixel value of coordinate (i, j) on the transformed image I.sub.l' is I.sub.l' (i, j) and the pixel value of coordinate (i, j) on the right image I.sub.r is I.sub.r(i, j).

(5-2) Correction Based on Difference of Photograph Condition of the Left Image and the Right Image:

Even if two cameras (the left camera and the right camera) photography the same point (the-same coordinate) on the road plane, it often happens that pixel values of the same point of the left image and the right image are different due to the different photopraphic conditions of the left image and the right image. For example, if a white car is included in a view of the left image, an iris of the left camera is closed more than an iris of the right camera when using auto iris lens camera. As a result, even if the same position of the road plane is photographed by the left camera and the right camera, the brightness of the position of the left image is often lower than brightness of the position of the right image. Accordingly, the matching similarity is corrected using an average of brightness of the images I.sub.l' and I.sub.r.

.times..di-elect cons.'.di-elect cons..times.'.function..times..di-elect cons.'.di-elect cons..times..function. ##EQU00014##

(5-3) Matching Method:

There are a plurality of matching methods using a corrected average of brightness. In this case, four example matching methods are explained.

(5-3-1) The First and Second Matching Methods:

After the left image and the right image are corrected so that a difference of the average of brightness is equal to "0", the matching evaluation value (matching similarity) is calculated as the sum of the difference of brightness. This evaluation expression is represented as follows.

.di-elect cons.'.di-elect cons..times.'.function.'.function. ##EQU00015##

Otherwise, if the left image and the right image is corrected so that a ratio of the average of brightness is equal, the evaluation expression is represented as follows.

.di-elect cons.'.di-elect cons..times.'.function.'.function. ##EQU00016##

If the matching evaluation value "D.sub.1=0 or D.sub.2=0" represents a coincidence of two images, the matching evaluation value is calculated by comparing each transformed left image using all transformation parameters with the right image. A transformation parameter of which absolute value of the matching evaluation value is smallest and a transformation parameter of which absolute value of the matching evaluation value is second smallest, are selected. Assuming that the former parameter is W.sub.i, the latter parameter is W.sub.j, the matching evaluation value of the parameter W.sub.i is D.sub.i, and the matching evaluation valve of the parameter W.sub.j is D.sub.j. In this case, the transformation parameter is determined as follows.

'.times..times..times..times..times..times..times..times..noteq..times..ti- mes. ##EQU00017##

Briefly, if the sign of two evaluation values (Di and Dj) are different, a transformation parameter of which matching evaluation value is "0" is regarded as the estimated transformation parameter W'.

(5-3-2) The Third and Fourth Matching Methods:

Alternatively, the third matching method using the expression (19), or the fourth matching method using the expression (20), may be used.

.di-elect cons.'.di-elect cons..times.'.function.'.function..di-elect cons.'.di-elect cons..times.'.function.'.function. ##EQU00018##

This evaluation expression represents the sum of the absolute value of a difference of brightness of each pixel. Each matching evaluation value is a positive value. In this case, a parallel moving vector (.alpha., .beta.) is selected where the matching evaluation value is smallest. While the matching evaluation value of the left image is calculated for each parallel moving vector, if a matching evaluation value of one parallel moving vector is below the minimum of the evaluation values already calculated, calculation of the evaluation value of the left image may be completed. In this case, the one parallel moving vector (.alpha., .beta.) is selected.

The image transformation unit 3 creates the transformed image of each transformation parameter according to probability distribution of the expression (14). In the image matching unit 4, each transformed image created by the image transformation unit 3 is compared with the right image in order. Before this processing, the image transformation unit 3 creates a large number of transformed images by using the parallel moving vector (.alpha., .beta.) near the prediction value Y.sub.t/.sub.t-1 as shown in FIG. 5. Accordingly, if the prediction does not largely miss, the parallel moving vector (.alpha., .beta.) can be finitely selected. Furthermore, because each parallel moving vector is arranged in order of nearer distance from the prediction value, a probability that the matching evaluation value of the transformation parameter of earlier order is the minimum is high. Accordingly, if the evaluation expression (19) or (20) is used for calculating the matching evaluation value, a probability that the calculation of the matching evaluation value is stopped halfway is high, and the matching processing can be executed at high speed.

As mentioned-above, in the image matching unit 4, the left image is transformed by using a plurality of transformation parameter (.alpha., .beta.). Each transformed image is compared with the right image, and the matching similarity is calculated for each transformation parameter. One transformation parameter (.alpha., .beta.) of which the matching similarity (evaluation value) is maximum (minimum) is selected as the parallel moving vector to be searched.

(6) Function of the Status Estimation Unit 5:

the statues memory 6 and the status prediction unit 7.

In the status estimation unit 5, the status memory 6, and the status prediction unit 7, the transformation parameter (parallel moving vector) selected by the image matching unit 4 is input. The present road plane is estimated by using Kalman filter including the transformation parameter. Concretely, a tilt of the road plane is calculated and a distance from the vehicle to an obstacle object is calculated using the tilt of the road plane.

The status memory 6 stores a status vector X.sub.t and a covariance matrix P.sub.t as status information of timing (t). Briefly, the status memory 6 stores above-mentioned information of parallel moving of the image. The tilt of the road plane can be estimated using this information.

(6-1) Explanation of the Status Vector:

In one embodiment, the status vector X.sub.t consists of a unit vector "C.sub.x, C.sub.y" representing a parallel moving direction, a magnitude "l" of the parallel moving direction, and a change quantity "a" of the magnitude l per unit time. The status vector X.sub.t is represented as follows. X.sub.t=[C.sub.x, C.sub.y, l, a].sup.T (21)

(6-2) Explanation of the Covariance Matrix:

In one embodiment, the covariance matrix P.sub.t is a matrix of four rows and four columns representing covariance of each element of the status vector. In this matrix, element of the i-th row and the j-th column represents a variance of the i-th element of the status vector in the case of "i=j", and represents a covariance of the i-th element and the j-th element of the status vector in the case of "i.noteq.j". The variance represents a change in degree of the value of the element, and the covariance represents a co-change in degree of the values of two elements. Concretely, if the variance and the covariance are small values, the change in degree of the value of the status vector is small and reliability of the element is high. Conversely, if the variance and the covariance are large value, the change in degree of the value of the status vector is large and reliability of the element is low.

(6-3) Explanation of Measurement Value:

Assume that the measurement value of parallel moving vector of timing (t) obtained by the image matching unit 4 is Y.sub.t. The measurement value Y.sub.t is represented as follows. Y.sub.t=[.alpha., .beta.].sup.T (22)

(6-4) Status Transition Function f:

Assume that vibration of the vehicle and change of tilt of the road are smooth. A status vector X.sub.t+1 passing from the status vector X.sub.t by a unit time is represented using a status transition function f as follows. X.sub.t+1=f(X.sub.t) f(X.sub.t)=[C.sub.x, C.sub.y, l+a, a].sup.T (23)

(6-5) Explanation of Kalman Filter:

A Kalman filter is an algorithm to calculate a suitable value of a model parameter by applying the status transition function to a time series of data measured from the image. The relationship between the measurement value Y.sub.t and the status vector is defined as follows.

.function..times..times..function..times..times. ##EQU00019##

In this case, the Kalman filter to estimate the status vector of the vehicle is represented as follows. X.sub.t+1/t=f(X.sub.t/t)+m.sub.t (25) X.sub.t/t=X.sub.t/t-1+K.sub.t[Y.sub.t-h.sub.t({circumflex over (X)}.sub.t/t-1)] (26) K.sub.t=P.sub.t/t-1H.sub.t.sup.T[H.sub.tP.sub.t/t-1H.sub.t.sup.T+S.sub.t]- .sup.-1 (27) P.sub.t+1/t={circumflex over (F)}.sub.tP.sub.t/t{circumflex over (F)}.sub.t.sup.T+Q.sub.t (28) P.sub.t/t=P.sub.t/t-1-P.sub.t/t-1H.sub.t.sup.T[H.sub.tP.sub.t/t-1H.sub.t.- sup.T+S.sub.t].sup.31 1H.sub.tP.sub.t/t-1 (29)

In the above expressions (24) and (25), "m.sub.t" and "n.sub.t" are respectively a Gaussian white noise vector of average "0" representing error and a measurement error of status transition. The covariance matrix of "m.sub.t" and "n.sub.t" are respectively represented as "Q.sub.t" and "S.sub.t".

.times..function..times. ##EQU00020##

In above expressions (27) (28) (29), {circumflex over (F)}.sub.t is a defined matrix of "4.times.4" and H.sub.t is a defined matrix of "2.times.2". "4" is a length of the status vector and "2" is a length of measurement vector. Concretely, value of the matrix is represented as follows.

##EQU00021##

(6-6) Estimation Step of the Status Vector and the Covariance Matrix:

The estimation step of the status vector and the covariance matrix of timing (t) using the Kalman filter is explained. FIG. 8 is a flow chart of estimation processing of the status vector and the covariance matrix according to one embodiment of the present invention.

(Step 1)

Assume that a status vector "X.sub.t-1/t-1" of timing (t-1) and a covariance matrix P.sub.t-1/t-1 of timing (t-1) are stored in the status memory 6. In the status prediction unit 7, a temporary status vector .sub.Xt/t-1 and a temporary covariance matrix P.sub.t/t-1 are calculated by using the status vector X.sub.t-1/t-1 and the covariance matrix P.sub.t-1/t-1. The temporary status vector X.sub.t/t-1 and the temporary covariance matrix P.sub.t/t-1 are predicted status information of the vehicle of timing (t) (also referred to as the next timing). This prediction is executed using the expressions (25) and (28).

(Step 2)

In the status prediction unit 7, a Kalman gain of timing (t) (next timing) is calculated by using the expression (27). In this case, the temporary covariance matrix P.sub.t/t-1 is utilized

(Step 3)

In the image transformation unit 3, a prediction value Y.sub.t/t-1 is calculated by using the temporary status vector X.sub.t/t-1 and the expression (24). A covariance matrix P.sub.t is calculated by using the temporary status covariance matrix P.sub.t/t-1 and the expression (29). Additionally, a probability distribution is calculated by using the prediction value Y.sub.t/t-1, the covariance matrix P.sub.t and the expression (14). Then, a parallel moving vector "g.sub.i=(.alpha..sub.i, .beta..sub.i) (i=1.about.n)" is selected from candidate values of the probability distribution in order as a candidate (parallel moving vector). For example, "g.sub.i" may be selected at random from the candidate values of the probability distribution or selected at equal probability from the candidate values of the probability distribution.

(Step 4)

In the image transformation unit 3, a transformation parameter of affine transformation is calculated by using the selected parallel moving vector (.alpha., .beta.) and the expression (7). Briefly, the transformation parameter is created for each parallel moving vector selected in order.

(Step 5)

In the image transformation unit 3, the left image of timing (t) is transformed by using the transformation parameter. Briefly, the left image is transformed based on a view point of the right side camera (the right image).

(Step 6) In the image matching unit 4, a matching area is extracted from the transformed left image and the right image of timing (t).

(Step 7)

In the image matching unit 4, brightness of the matching area is corrected by using the expression (13). Concretely, a correction method is determined by a difference of the photographic condition between the left image and the right image.

(Step 8) In the image matching unit 4, the transformed left image of timing (t) is compared (matched) with the right image of timing (t). In this case, one method of above-mentioned four matching methods is used. Then, a matching similarity of timing (t) is calculated.

(Step 9)

The processing of steps 4.about.8 are repeated for each of the selected parallel moving vectors in order. The best matching similarity of timing (t) is selected from each of the calculated matching similarities. Concretely, the matching evaluation value of the minimum is selected as the best matching similarity.

(Step 10)

The parallel moving vector (.alpha., .beta.) used for the transformed left image of the best matching similarity is set as a parallel moving vector Y.sub.t of timing (t)

(Step 11)

In the status estimation unit 5, a status vector X.sub.t/t of timing (t) and a covariance matrix P.sub.t/t of timing (t) are estimated by using the parallel moving vector Y.sub.t, the temporary status vector X.sub.t/t-1 and the temporary covariance matrix P.sub.t/t-1. In this case, the expressions (26) and (29) are used.

(Step 12)

The processing of steps 1.about.11 are repeated for each timing. In this way, the status vector X.sub.t/t and the covariance matrix P.sub.t/t are updately calculated at each timing.

(6-7) Estimation of the Road Plane:

Next, estimation of the road plane is explained. As mentioned-above at the expressions (9) and (13), if a tilt of the road plane changes, in the image phtographed by the camera, a matching point between the left image and the right image (calculated by the image matching unit 4) is parallely moving along a straight line as shown in FIG. 4. The status memory 6 stores information to estimate the parallel moving vector of the matching point. The tilt of the road plane can be calculated by using information stored in the status memory 6.

Assume that a tilt of the road plane is B and a moving vector of the matching point is (B.times.h.sub.13, B.times.h.sub.23) by using the expression (9). In this case, "h.sub.13" and "h.sub.23" are variables used in the expression (8) for a coordinate of tilted road plane and a projected coordinate. A calculation method of "h.sub.13" and "h.sub.23" is explained.

As shown in FIG. 9, a vehicle is located on a flat road, an object of predetermined height is located at a front distance D from the vehicle on the road, and a camera loaded on the vehicle photographs the object. Assume that the upper end P1 of the object is a coordinate on the tilted road plane and the lower end P2 of the object is a coordinate on the flat road plane. By comparing the coordinate P.sub.1 with the coordinate P.sub.2, the variable "h.sub.13" and "h.sub.23" of the expression (8) are calculated. Other variables in the expression (8), i.e., variables in the expression (3), are also calculated. For example, the camera loaded on the vehicle photographs a plurality of feature points, each of which coordinate is predetermined on the road. By using a correspondence between a coordinate on the image and a coordinate on the road for each feature point, these variables can be calculated.

The "h.sub.13" and "h.sub.23" are values representing moving direction of a vanishing point based on tilt of the road. As shown in the expression (13-B), these values are represented as {right arrow over (d)}.sub.l for the left side camera (left image) and represented as {right arrow over (d)}.sub.r for the right side camera (right image). As shown in FIG. 2, the left side camera and the right side camera are loaded on the vehicle so that two optical axes are almost parallel. Accordingly, if it is assumed that "{right arrow over (d)}.sub.l={right arrow over (d)}.sub.r", the change in quantity "{right arrow over (d)}.sub.r-A{right arrow over (d)}.sub.l" by tilt of the road in affine transformation between two (left and right) images is calculated from the expression (13-B). As each initial value of the status vector, a vector "{right arrow over (d)}.sub.r-A{right arrow over (d)}.sub.l" of which length is normalized by "1" is set as the initial value of "(C.sub.x, C.sub.y).sup.T". Initial values of other element (l, a) of the status vector are set as "(0, 0)". These initial values are previously stored in the status memory 6.

As mentioned-above, the status memory 6 stores the unit vector "(C.sub.x, C.sub.y)" of parallel moving direction of timing (t) and the parallel moving quantity "l". Accordingly, tilt B of the road of timing (t) is calculated by using these values as follows. B=l.times.sqrt(C.sub.x.sup.2+C.sub.y.sup.2)/sqrt(h.sub.13.sup.2+h.sub.33.- sup.2) (33)

In the present invention, the status information is estimated by using the parallel moving vector at each timing. Accordingly, when the vehicle travels on the road of ups and downs, when a loading condition of persons or a carrying condition of baggage onto the vehicle changes, or when the vehicle vibrates or the road tilts (i.e., in case that tilt of the road plane changes from a view point of the camera loaded on the vehicle), the status information of the vehicle can be certainly estimated. As a result, the transformation parameter can be correctly calculated by using the status information.

Furthermore, a suitable parallel moving vector is selected from a plurality of parallel moving vectors by using a Kalman filter and the probability distribution. Accordingly, a calculation for selecting of the suitable parallel moving vector can be effectively executed.

Furthermore, the road plane is estimated by using the status information calculated and updated at each timing. Accordingly, the tilt of the road plane is correctly calculated irrespective of existence of white line on the road plane.

For embodiments of the present invention, the processing of the present invention can be accomplished by computer-executable program, and this program can be realized in a computer-readable memory device.

In embodiments of the present invention, the memory device, such as a magnetic disk, a floppy disk, a hard disk, an optical disk (CD-ROM, CD-R, DVD, and so on), an optical magnetic disk (MD, and so on) can be used to store instructions for causing a processor or a computer to perform the processes described above.

Furthermore, based on an indication of the program installed from the memory device to the computer, OS (Operation system) operating on the computer, or MW (middle ware software), such as database management software or network, may execute one part of each processing to realize the embodiments.

Furthermore, the memory