Distance estimation from image motion for moving obstacle detection

Distance from a moving image capture device to one or more points is determined. An optical flow is calculated from a first image and a second image captured by the moving image capture device. The horizontal component of the optical flow is used to generate a horizontal distance map including horizontal distances and the vertical component of the optical flow is used to generate a vertical distance map including vertical distances. Horizontal weights are applied to the horizontal distance map to generate a modified horizontal distance map where horizontal distances proximate to a vertical line intersecting a focus of expansion are attenuated. Vertical weights are applied to the vertical distance map to generate a modified vertical distance map where vertical distances proximate to a horizontal line intersecting the focus of expansion are attenuated. The modified vertical distance map and the modified horizontal distance map are then summed.

FIELD OF THE INVENTION

This invention relates generally to object detection, and more particularly to identifying moving objects based on differences between images captured from a stereo image capture device and from a moving image capture device.

BACKGROUND OF THE INVENTION

Conventional techniques for determining distance between an image capture device and a stationary object do not account for certain types of errors which limit the accuracy of the determined distance. Conventional distance estimation techniques have significant errors when estimating distance to objects proximate to a horizontal or vertical line intersecting the focus of expansion of an image.

SUMMARY OF THE INVENTION

The present invention provides a system and method for determining a distance from a moving image capture device to one or more points. A first image and a second image are received from the moving image capture device and an optical flow is calculated using the first image and the second image. Using a horizontal component of the optical flow, a horizontal distance map including horizontal distances from the moving image capture device to a plurality of points is determined. Similarly, a vertical component of the optical flow is used to determine a vertical distance map including vertical distances from the moving image capture device to the plurality of points. A set of horizontal weights are applied to the horizontal distance map to generate a modified horizontal distance map by attenuating horizontal distances associated with pixels in the horizontal distance map proximate to a vertical line intersecting a focus of expansion of the horizontal distance map. Similarly, a set of vertical weights are applied to the vertical distance map to generate a modified vertical distance map by attenuating vertical distances associated with pixels in the vertical distance map proximate to a horizontal line intersecting the focus of expansion of the vertical distance map. A distance map is generated by combining the modified horizontal distance map and the modified vertical distance map. In one embodiment, the modified horizontal distance map and the modified vertical distance map are summed to generate the distance map. The distance map is then stored.

DETAILED DESCRIPTION OF THE INVENTION

A preferred embodiment of the present invention is now described with reference to the Figures where like reference numbers indicate identical or functionally similar elements. Also in the Figures, the left most digits of each reference number correspond to the Figure in which the reference number is first used.

Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by a variety of operating systems.

FIG. 1is an illustration of a computing system102in which one embodiment of the present invention may operate. The computing system102includes a computing device100, a moving image capture device105and a stereo image capture device107. The computing device100comprises a processor110, an output device120and a memory140. In an embodiment, the computing device100further comprises a communication module130including transceivers or connectors. In other embodiments, the computing system102may include additional components, such as one or more input devices.

The moving image capture device105, is a video camera, a video capture device or another device capable of electronically capturing data describing the movement of an entity, such as a person or other object. For example, the moving image capture device105captures image data or positional data. The moving image capture device105is coupled to the computing device100and transmits the captured data to the computing device100.

The stereo image capture device107comprises an image capture device having two or more lenses each associated with a separate image sensor. The lenses included in the stereo image capture device107are separated by a predetermined spacing, or “baseline,” allowing the computing device100to measure of distances, or disparities, from the stereo image capture device107to using images captured using different lenses. The length of the baseline, or separation between lenses in the stereo image capture device107, affects the accuracy of distance measured using images captured by different lenses, with a larger baseline increasing the accuracy of the distance measurement. However, a large baseline may increase the complexity of disparity measurement. In one embodiment, lenses of stereo image capture device107have a baseline, or separation, of 24 centimeters. For accurate calculation of distance or disparity by the computing device100, different lenses and their corresponding image sensors in the stereo image capture device107capture images at substantially the same time. Although shown inFIG. 1as discrete devices, in one embodiment the moving image capture device105comprises a lens and its associated image sensor included in the stereo image capture device107.

The processor110processes data signals and may comprise various computing architectures including a complex instruction set computer (CISC) architecture, a reduced instruction set computer (RISC) architecture, or an architecture implementing a combination of instruction sets. Although only a single processor is shown inFIG. 1, multiple processors may be included in the computing device100. The processor110comprises an arithmetic logic unit, a microprocessor or some other information appliance equipped to transmit, receive and process electronic data signals from the memory140, the output device120, the communication module130or other modules or devices.

The output device120represents any device equipped to display electronic images and data as described herein. Output device120may be, for example, an organic light emitting diode display (OLED), a liquid crystal display (LCD), a cathode ray tube (CRT) display or any other similarly equipped display device, screen or monitor. In one embodiment, output device120is equipped with a touch screen in which a touch-sensitive, transparent panel covers the screen of output device120.

In one embodiment, the computing device100also includes a communication module130which links the computing device100to a network (not shown) or to other computing devices100. The network may comprise a local area network (LAN), a wide area network (WAN) (e.g., the Internet), and/or any other interconnected data path across which multiple devices man communicate. In one embodiment, the communication module130is a conventional connection, such as USB, IEEE 1394 or Ethernet, to other computing devices100for distribution of files and information. In another embodiment, the communication module130is a conventional type of transceiver, such as for infrared communication, IEEE 802.11a/b/g/n (or WiFi) communication, Bluetooth® communication, 3G communication, IEEE 802.16 (or WiMax) communication, or radio frequency communication.

The memory140stores instructions and/or data that may be executed by processor110. The instructions and/or data may comprise code that performs any and/or all of the techniques described herein when executed by the processor110. Memory140may be a dynamic random access memory (DRAM) device, a static random access memory (SRAM) device, a Flash RAM or another non-volatile storage device, combinations of the above, or some other memory device known in the art. The memory140is adapted to communicate with the processor110, the output device120and/or the communication module130.

In one embodiment, the memory140includes a moving obstacle detection module150having instructions for executing a method for detecting one or more moving objects by analyzing images received from the moving image capture device105and the stereo image capture device107. For example, the processor110executes instructions, or other computer code, stored in the moving obstacle detection module150to identify moving objects within images captured by the moving image capture device105and by the stereo image capture device107. In one embodiment, the moving obstacle detection module150includes a motion determination module152, an optical flow determination module154, a stereo disparity determination module156and a color segmentation module158.

The motion determination module152includes computer executable code, such as data or instructions, that, when executed by the processor110, remove rotational motion from the images captured by the moving image capture device105. Rotational motion is caused by movement of the moving image capture device105. While the motion determination module152removes rotational motion from captured images, translational motion in the captured images is preserved. Hence, a method described by instructions or code stored in the motion determination module152generates a modified sequence of images from images captured by the moving image capture device105where rotational motion is removed from the modified images while translational motion is retained. Preserving translational motion within the images allows detection or identification of moving objects within the field of view of the moving image capture device105. Because rotational motion from movement of the moving image capture device105itself reduces the accuracy of moving object detection, removing rotational motion from images captured by the moving image capture device105allows more accurate detection of moving objects. One embodiment of a method for cancelling rotational motion stored in the motion determination module152is further described below in conjunction withFIG. 3.

The optical flow determination module154includes computer executable code, such as data or instructions, that, when executed by the processor110, calculate an optical flow of images received from the moving image capture device105. The calculated optical flow associates a two-dimensional vector with multiple pixels in an image captured by the moving image capture device105. In one embodiment, the optical flow associates a two-dimensional vector with each pixel in an image captured by the moving image capture device105. The two-dimensional vector associated with a pixel describes the relative motion of an object associated with the pixel between the moving image capture device105and one or more entities or objects included in the image captured by the moving image capture device105. In one embodiment, the optical flow determination module154uses a “block matching” method for efficient computation of a dense and accurate optical flow. However, in other embodiments, the optical flow determination module154may use any of a variety of methods for optical flow calculation.

In one embodiment, the optical flow determination module154also modifies the calculated optical flow to increase the density or accuracy of the calculated optical flow. For example, the optical flow determination module154uses data from the color segmentation module158, further described below, to reduce noise in the optical flow and determine additional optical flow data. For example, the color segmentation module158identifies various segments of an image from the moving image capture device105which are used by the optical flow determination module154to estimate motion model parameters. The optical flow determination module154then recomputes the optical flow using the motion model parameters.

The disparity determination module156includes computer executable code, such as data or instructions, that, when executed by the processor110, calculate the stereo disparity of images from the stereo image capture device107and/or calculate motion disparity of images from the moving image capture device105. Stereo disparity describes the difference between an object's position in images captured by different lenses in the stereo image capture device107. In one embodiment, the disparity determination module156calculates motion disparity for different pixels within an image from the moving image capture device105by determining the difference between a coordinate associated with the pixel and the focus of expansion of the image. The difference is then divided by a component of the optical flow associated with the pixel. In one embodiment, a horizontal motion disparity and a vertical motion disparity are respectively computed from a horizontal distance from a pixel coordinate to the focus of expansion of an image and a horizontal component of the optical flow and from a vertical distance from a pixel coordinate to the focus of expansion of an image and a vertical component of the optical flow, respectively. The focus of expansion of an image is a point in the image from which a majority of image motion trajectories originate or a point in the image where a majority of image motion trajectories end.

The disparity determination module156also calculates a scale associated with an image from the moving image capture device105. In one embodiment, the scale is the product of the baseline of the stereo image capture device107and the focal length of the lenses of the stereo image capture device107divided by the distance between the position of the moving image capture device105when a first image is captured and the position of the moving image capture device105when a second image is captured. In one embodiment, the first image and second image are consecutive images. However, because the distance between the position of the moving image capture device105when the first image is captured and when the second image is captured is unknown, the disparity determination module156initially selects a predetermined value for the scale and uses the predetermined value to calculate an error associated with the scale. The disparity determination module156subsequently modifies the scale to minimize the error. Calculation of the stereo disparity, motion disparity and scale is further described below in conjunction withFIG. 5.

The color segmentation module158includes computer executable code, such as data or instructions, that, when executed by the processor110, partition an image into segments. In one embodiment, the color segmentation module158applies a “mean shift” process to an image from the stereo image capture device107or from the moving image capture device105. The mean shift process associates a three-dimensional color vector and a two-dimensional location with multiple pixels in an image. Hence, the mean shift process converts an image into a plurality of points in a five-dimensional space from which maxima are determined using an initial estimate. A kernel function modifies the weighting of points to re-estimation of the mean. Various kernel functions or initial estimates may be used in different embodiments of the color segmentation module158. However, in other embodiments of the color segmentation module158, a different process may be used for clustering data to segment received images from the moving image capture device105or from the stereo image capture device107.

It should be apparent to one skilled in the art that computing device100may include more or less components than those shown inFIG. 1without departing from the spirit and scope of the present invention. For example, computing device100may include additional memory, such as, for example, a first or second level cache, or one or more application specific integrated circuits (ASICs). Similarly, computing device100may include additional input or output devices. In some embodiments of the present invention one or more of the components (110,120,130,140,150,152,154,156,158) may be positioned in close proximity to each other while in other embodiments these components may be positioned in geographically distant locations. For example the modules in memory140may be programs capable of being executed by one or more processors110located in separate computing devices100.

FIG. 2is a flowchart of one embodiment of a method200for detecting one or more moving objects from image date. In an embodiment, the steps of the method200are implemented by the processor110executing software or firmware instructions that cause the described actions, such as instructions stored in a memory140or other computer readable storage medium. Those of skill in the art will recognize that one or more steps of the method200may be implemented in embodiments of hardware and/or software or combinations thereof. Furthermore, those of skill in the art will recognize that other embodiments can perform the steps ofFIG. 2in different orders and additional embodiments can include different and/or additional steps than the ones described here.

A computing device100receives images from the moving image capture device105and from the stereo image capture device107and a processor110included in the computing device100executes computer executable code, such as data or instructions stored in a motion determination module152, to remove210rotational motion from images received from the moving image capture device105while preserving translational motion in the images received from the moving image capture device105. By removing210rotational motion from captured images, moving objects are more accurately detected using images from the moving image capture device105. Removing210rotational motion from images received from the moving image capture device105generates one or more rotation-cancelled images where motion caused by movement of the moving image capture device105is removed210. One embodiment of a method for removing210of motion from images received from the moving image capture device105is further described below in conjunction withFIG. 3.

Using images received from the stereo image capture device107, the computing device100determines220a stereo distance map. In one embodiment, block matching is used to determine220the difference between the location of an object in a first image captured by a first image capture device included in the stereo image capture device107and the location of the object in a second image captured by a second image capture device included in the stereo image capture device107. Differences in the position of the object between images captured by different image capture devices included in the stereo image capture device107allow triangulation of the object's distance from the stereo image capture device107. Distances from the stereo image capture device107to various objects are computed and stored to determine220the stereo distance map.

A motion distance map is generated230from the one or more rotation-cancelled images to reconstruct distance to one or more objects from image motion. Instructions from the optical flow determination module154are executed by the processor110to generate an optical flow map from consecutive images captured from the moving image capture device105. The optical flow map associates motion vectors with a plurality of pixels in images captured by the moving image capture device105. For example, the optical flow map includes a motion vector associated with each pixel in the image captured by the moving image capture device105.

A horizontal component or a vertical component of the optical flow calculated from a pair of rotation-cancelled images is used to determine a distance from the moving image capture device105to a stationary object. However, using the horizontal component of optical flow to calculate distance causes large errors proximate to a vertical line passing through a focus of expansion of the rotation-cancelled images. Similarly, computing distance using the vertical component of optical flow creates large errors proximate to a horizontal line passing through the focus of expansion of the rotation-cancelled images. As indicated above, the focus of expansion of an image is the point in the image from which a majority of image motion trajectories of the optical flow originate or a point in the image where a majority of image motion trajectories of the optical flow end.

The motion distance map generated230from the rotation-cancelled images comprises a weighted sum of a distance map calculated from the horizontal component of optical flow from a pair of rotation-cancelled images (“a horizontal distance map”) and a distance map obtained from the vertical component of optical flow calculated from the pair of rotation-cancelled images (“a vertical distance map”). Horizontal weights are associated with different pixels in the horizontal distance map and vertical weights are associated with different pixels in the vertical distance map. The horizontal weights associated with the horizontal distance map and the vertical weights associated with the vertical distance map are selected to minimize erroneous regions in the respective distance maps.

Horizontal weights associated with pixels in the horizontal distance map proximate to a vertical line passing through the focus of expansion have a smaller value than pixels in the horizontal distance map having a greater distance from the vertical line passing through the focus of expansion. Similarly, vertical weights associated with pixels in the vertical distance map proximate to a horizontal line passing through the focus of expansion have a smaller value than pixels in the vertical distance map having a greater distance from the horizontal line passing through the focus of expansion. The motion distance map is generated230from a sum of the horizontal distance map multiplied by the horizontal weights and the vertical distance map multiplied by the vertical weights. An embodiment of a method for generating230of the motion distance map is further described below in conjunction withFIG. 4.

However, distances determined using the motion distance map become less accurate as the distances equal or exceed a scale value which is determined240using images from the stereo image capture device107and from the moving image capture device105. To determine240the scale, a stereo disparity, or a stereo distance, is computed for multiple pixels in an image capture by the stereo image capture device107. The stereo disparity and the stereo distance are related according to:

B=the baseline, or distance between the optical centers of two lenses included in the stereo image capture device107,

f=the focal length of the lenses of included in the stereo image capture device and

Similarly, a motion disparity or a motion distance is computed for multiple pixels in a pair of images captured by the moving image capture device105. The motion disparity and the motion distance are related as follows:

T=distance between a position of the moving image capture device105when a first image is captured and a position of the moving image capture device when a second image is captured and

The scale associated with the motion distance map is then determined240by selecting an initial value for the scale and calculating an error between the stereo disparity, or the stereo distance, associated with an image pixel and the product of the scale and the motion disparity, or the motion distance, associated with the pixel. This difference is calculated for multiple pixels within the image and a median error is determined using the error associated with different pixels within the image. The median error is stored and associated with the initial value. The scale is then modified from the initial value. Using the modified scale, the error between stereo disparity and the product of the scale and motion disparity is again computed for various pixels and the median error is computed and associated with the modified scale. The scale is modified until a minimum median error is calculated. The scale associated with the minimum median error is then determined240and associated with the motion distance map. In one embodiment, the motion distance map is modified to offset removal210of the rotational motion and the modified motion distance map is used to determine240the scale. Embodiments of methods for determining240the scale is further described below in conjunction withFIGS. 5 and 6.

The determined scale is then used to scale250the motion distance map. For example, the motion distance map is multiplied by the determined scale value. In one embodiment, the motion distance map is modified to offset removal210of the rotational motion and the modified motion distance map is scaled250using the determined scale. For multiple pixels in an image, the difference between the stereo disparity associated with a pixel and the product of the determined scale and the motion disparity associated with the pixel is computed. The difference is compared to a threshold and if the difference equals or exceeds the threshold, the pixel is associated with a moving object. For example, a pixel is associated with a moving object when:
|d−α*{tilde over (d)}|≧c
Where:

d=stereo disparity associated with the pixel,

a*=determined scale value

{tilde over (d)}=motion disparity associated with the pixel and

In one embodiment, the accuracy of the stereo disparity and/or the motion disparity are estimated and used to specify the threshold. For example, if the stereo disparity or the motion disparity is noisy, the threshold is set to a large value to avoid erroneously identifying a stationary region as a moving object.

Determining240the scale between the stereo distance map and the motion distance map allows more accurate detection of small moving objects than conventional moving object detection techniques. Further, many conventional techniques for moving obstacle detection rely on identifying the shape of detected objects, making it difficult for these techniques to detect obstacles having different shapes. However, the method200allows identification of moving objects having a variety of shapes.

FIG. 3is a flowchart of one embodiment of a method for removing210rotational motion from captured images. In the embodiment shown byFIG. 3, a generated imaging plane differing from the imaging plane of the moving image capture device105is used to generate rotation-cancelled images. For example, the images from which rotational motion is removed210are frames of video data captured by the moving image capture device105projected onto the generated imaging plane.

In an embodiment, the steps of the method for rotational motion removal210are implemented by the processor110executing software or firmware instructions that cause the described actions, such as instructions stored in a computer-readable storage medium, such as the memory140or, the motion determination module152. Those of skill in the art will recognize that one or more steps of the method for removing210rotational motion may be implemented in embodiments of hardware and/or software or combinations thereof. Furthermore, those of skill in the art will recognize that other embodiments can perform the steps ofFIG. 3in different orders and additional embodiments can include different and/or additional steps than the ones described here.

After receiving a first image and a second image from the moving image capture device105, an optic center of the first image is determined310and an optic center of the second image is determined320. For example, the first image and the second image are consecutive frames of video data captured by the moving image capture device105. In one embodiment, the optic center of the first image and the optic center of the second image are determined310,320using an ego-motion estimation process which estimates relative motion of the moving image capture device105. The relative motion estimated by the ego-motion estimation process includes rotational motion and translational motion of the moving image capture device105. The relative position of the optic centers of the first image and the second image are determined310,320from the motion estimated by the ego-motion estimation process. Different embodiments may use various ego-motion estimation processes to calculate image motion and properties of motion field equations for determining moving image capture device105motion.

After determining310,320the optic center of the first image and the optic center of the second image, a line connecting the optic center of the first image and the optic center of the second image is determined330. In one embodiment, the optic center of the first image is the origin of a coordinate system associated with the first image and the ego-motion process used to determine320the optic center of the second image determines the location of the optic center of the second image relative to the first image. A line passing through the optic center of the first image and the optic center of the second image is then determined330. An imaging plane perpendicular to the line passing through the optic center of the first image and the optic center of the second image is determined and used to generate340a rotation-cancelled first image and to generate350a rotation-cancelled second image.

In one embodiment, the rotation-cancelled first image is generated340by computationally reprojecting the first image to the imaging plane perpendicular to the line passing through the optic center of the first image and the optic center of the second image. Similarly, the rotation-cancelled second image may be generated350by computationally reprojecting the second image to the imaging plane perpendicular to the line passing through the optic center of the first image and the optic center of the second image. The rotation-cancelled first image and the rotation-cancelled second image remove motion caused by rotation of the moving image capture device105while including translational motion, allowing the translational motion between the first image and the second image to be used for detection of moving objects from the images while reducing the likelihood of incorrectly identifying a stationary object as a moving object. In one embodiment, rotation-cancelled images are generated340,350for multiple pairs of images captured by the moving image capture device105, such as for a plurality of pairs of consecutive images from a video stream.

FIGS. 7A and 7Bshow an example application of the method for removing210rotational motion. In the example shown byFIGS. 7A and 7B, the moving image capture device105moves along a motion path700, introducing rotational motion between a first image705A and a second image705B captured by the moving image capture device105. The optical center of the first image715and the optical center of the second image717are determined310,320using an ego-motion process. For purposes of illustration,FIG. 7Aalso identifies the focus of expansion of the first image725A and the focus of expansion of the second image727A.

After determining310,320the optical center of the first image715and the optical center of the second image717, a line720connecting the optical center of the first image715and the optical center of the second image717is determined. As shown inFIG. 7B, the line720connects the position of the optical center of the moving image capture device105when the first image705A is captured and the position of the optical center of the moving image capture device105when the second image707A is captured. An imaging plane perpendicular to the line720is determined and a rotation-cancelled first image705B and a rotation-cancelled second image707B are generated340,350by reprojecting the first image705A and the second image707B into the imaging plane perpendicular to the line.

FIG. 7Bshows that the focus of expansion of the first rotation-cancelled image725B and the focus of expansion of the second rotation-cancelled image727B are both positioned along the determined line720, which reduces the effect of rotational motion from movement of the moving image capture device105along the motion path700. Using the rotation-cancelled first image705B and the rotation-cancelled second image705B to identify moving objects results in fewer false positives where a stationary object is identified as a moving object.

FIG. 4is a flowchart of one embodiment of a method for generating230a distance map from data captured by the moving image capture device105, also referred to as a “moving distance map.” Those of skill in the art will recognize that one or more steps of the method for generating230the moving distance map may be implemented in embodiments of hardware and/or software or combinations thereof. In an embodiment, the steps of the method for generating230the moving distance map are implemented by the processor110executing software or firmware instructions that cause the described actions, such as instructions stored in a computer-readable storage medium, such as the memory140or the motion moving obstacle detection module150. Furthermore, those of skill in the art will recognize that other embodiments can perform the steps ofFIG. 4in different orders and that additional embodiments can include different and/or additional steps than the ones described here.

The distance from the moving image capture device105to a stationary object is determined from a horizontal component or a vertical component of scaled image motion. In one embodiment, the horizontal component or the vertical component of an optical flow vector associated with a pixel is used to determine the distance from the moving image capture device105to an object associated with the pixel. Multiple pixels in an image are associated with a two-dimensional optical flow vector having a horizontal component and a vertical component. To generate230the moving distance map, a horizontal distance map is determined410from the horizontal component of the optical flow vector associated with multiple pixels. In one embodiment, the horizontal component of a vector associated with each pixel in an image is used. Hence, an optical flow between a first image captured by the moving image capture device105and a second image captured by the moving image capture device105is calculated and the horizontal component of the optical flow associated with multiple pixels is used to determine410the horizontal distance map. In one embodiment, rotational motion is removed from the first image and from the second image, as described above in conjunction withFIG. 3, and the rotation-cancelled images are used to calculate the optical flow. Horizontal distances are determined from the horizontal component of the optical flow according to:

Z=distance from the moving image capture device105to an object associated with a pixel located at position (x,y) within the image,

T=distance between a position of the moving image capture device105when a first image is captured and a position of the moving image capture device when a second image is captured,

x=horizontal location of the pixel within the image and

vx=horizontal component of the optical flow associated with the pixel at horizontal location x.

Hence, the horizontal distance map includes distances associated with multiple pixels in the image determined from the horizontal component of the optical flow, so the horizontal distance map describes the distance from the moving image capture device105to objects associated with various pixels within the image.

Similarly, a vertical distance map is determined420from the vertical component of the optical flow. From the optical flow between the first image and the second image captured by the moving image capture device105, distances comprising in the vertical distance map are determined according to:

Z=distance from the moving image capture device105to an object associated with a pixel located at position (x,y) within the image,

T=distance between a position of the moving image capture device105when a first image is captured and a position of the moving image capture device when a second image is captured,

y=vertical location of the pixel within the image and

vy=vertical component of the optical flow associated with the pixel at vertical location y.

Thus, the vertical distance map includes distances associated with multiple objects associated with pixels in the image based on the vertical component of optical flow.

However, the distance calculated from the horizontal component of the optical flow is inaccurate for objects associated with pixels proximate to a vertical line passing through the focus of expansion of the image. Similarly, the distance calculated from the vertical component of the optical flow is inaccurate for objects associated with pixels proximate to a horizontal line passing through the focus of expansion of the image. The focus of expansion of an image is a point in the image from which a majority of image motion trajectories of the optical flow originate or a point in the image where a majority of image motion trajectories of the optical flow end. Hence, the focus of expansion of the horizontal distance map and the focus of expansion of the vertical distance map are identified430. Both the horizontal distance map and the vertical distance map have the same focus of expansion, which, in one embodiment, is identified using ego-motion estimation.

To mitigate inaccuracies in the distances associated with points in the horizontal map proximate to the vertical line passing through the focus of expansion, a set of horizontal weights are applied440to distances from the horizontal distance map. The set of horizontal weights has a relative minimum value at the position of a vertical line intersecting the focus of expansion. Additionally, the horizontal weights associated with points proximate to the vertical line passing through the focus of expansion have smaller values than the horizontal weights associated with pixels having a larger distance from the vertical line passing through the focus of expansion. In one embodiment, a horizontal weight, wx, associated with a pixel in the horizontal distance map at location x, is determined using:

x=horizontal position of a pixel,

ex=horizontal position of the focus of expansion and

σ=standard deviation of a location including a significant error from the horizontal distance map and the vertical distance map.

In one embodiment, a location, or group of pixels, including a significant error used to determine the standard deviation, a, is determined by measuring the maximum vertical range for the location from the horizontal distance map and the maximum horizontal range for the location using the vertical distance map. In one embodiment, the set of horizontal weights has a Gaussian distribution, so the standard deviation of the Gaussian distribution is calculated so that the minimum values of the set of horizontal weights correspond to a size of the location including the significant error, minimizing the effect of the significant error. For example, the horizontal distance map includes a location of 40 pixels having a maximum vertical range and the vertical distance map includes a location of 40 pixels having a maximum horizontal range; hence, the standard deviation is calculated so that the Gaussian distribution of the set of horizontal weights has a width of 40 pixels. Because the width of the Gaussian distribution is approximately 3σ, the standard deviation in this example is 40/3 pixels.

Similarly, a set of vertical weights are applied450to distances associated with pixels in the vertical distance map to mitigate inaccuracies in the distances of the vertical map proximate to a horizontal line passing through the focus of expansion. The set of vertical weights includes a relative minimum at the position of a horizontal line intersecting the focus of expansion. Additionally, the vertical weights associated with pixels proximate to the horizontal line passing through the focus of expansion have smaller values than the vertical weights associated with pixels having a greater distance from the horizontal line passing through the focus of expansion. In one embodiment, a vertical weight, wy, associated with a pixel in the horizontal distance map at location y, is determined using:

y=vertical position of the pixel,

ey=vertical position of the focus of expansion and

σ=standard deviation of a location including a significant error from the horizontal distance map and the vertical distance map, which is calculated as described above with respect to the set of horizontal weights.

FIG. 8graphically illustrates an example set of horizontal weights810and an example set of vertical weights820. As shown inFIG. 8, the example set of horizontal weights810has a Gaussian distribution with a minimum located along a vertical line intersecting the focus of expansion805. The horizontal weights810increase as the distance from the vertical line intersecting the focus of expansion805. In the example ofFIG. 8, the horizontal weights reach a maximum at a distance of 3σ from the vertical line intersecting the focus of expansion805.

Similarly, the set of vertical weights820shown inFIG. 8has a Gaussian distribution with a minimum located along a horizontal line intersecting the focus of expansion805. Like the horizontal weights810, the vertical weights820increase as the distance from the horizontal line intersecting the focus of expansion805increases. In the example ofFIG. 8, the vertical weights820reach a maximum at a distance of 3σ from the horizontal line intersecting the focus of expansion805.

After applying440the set of horizontal weights to the horizontal distance map and applying450the set of vertical weights to the vertical distance map, an integrated distance map is generated460by combining the weighted horizontal distance map and the weighted vertical distance map. In one embodiment, the distance in the integrated distance map associated with a pixel at the location (x,y) is generated by:

wx(x,y)=horizontal weight associated with the pixel at location (x,y),

Zx(x,y)=distance from the horizontal distance map associated with the pixel at location (x,y),

wy(x,y)=vertical weight associated with the pixel at location (x,y) and

Zy(x,y)=distance from the vertical distance map associated with the pixel at location (x,y)

Thus, in one embodiment, the distances included in the integrated distance map are generated460by weighting the distance of associated with a pixel from the horizontal distance map using the horizontal weight associated with the pixel and weighting the distance of the pixel from the vertical distance map using the vertical weight associated with the pixel. The weighted distances from the horizontal distance map and from the vertical distance map are summed and the result associated with the point in the integrated distance map. Application of the set of horizontal weights and the set of vertical weights to the horizontal distance map and the vertical distance map, respectively, allows the integrated distance map to minimize the effect of erroneous regions in either the horizontal distance map or the vertical distance map.

FIG. 5is a flowchart of one embodiment of a method for determining240a scale associated with an image captured by a moving image capture device105. Those of skill in the art will recognize that one or more steps of the method for determining240the scale may be implemented in embodiments of hardware and/or software or combinations thereof. In an embodiment, the steps of the method for determining240the scale are implemented by the processor110executing software or firmware instructions that cause the described actions, such as instructions stored in a computer-readable storage medium, such as the memory140or the motion moving obstacle detection module150. Furthermore, those of skill in the art will recognize that other embodiments can perform the steps ofFIG. 5in different orders and that additional embodiments can include different and/or additional steps than the ones described here.

Pixels within the field of view of the moving image capture device105and the stereo image capture device107are identified by differences between a distance from the moving image capture device105to the an object associated with a pixel and a distance from the stereo image capture device107to the object associated with a pixel. However, a scale associated with the moving image capture device105limits the accuracy of distances determined using the moving image capture device105. In one embodiment, rather than use the distance to from the moving image capture device105to an object associated with a pixel and the distance from the stereo image capture device107to an object associated with a pixel to identify moving objects, the disparity determination module156calculates510a stereo disparity associated with the pixel and calculates520a motion disparity associated with the pixel.

The stereo disparity associated with a pixel is calculated520using the distance from the stereo distance map. In one embodiment, the stereo disparity is calculated520using:

Z=the stereo distance from the stereo distance map,

B=the baseline of the stereo image capture device107, or distance between the optical centers of two lenses included in the stereo image capture device107and

f=the focal length of the lenses of included in the stereo image capture device107.

In one embodiment, the disparity determination module156calculates520the motion disparity associated with a pixel using the optical flow calculated by the optical flow determination module154. Alternatively, the disparity determination module156uses distances from the integrated distance map, described above in conjunction withFIG. 4, to calculate520the motion disparity associated with a pixel. In one embodiment, the disparity determination module156modifies the integrated distance map to offset image modification removing210rotational motion from images captured by the moving image capture device105. The disparity determination module156calculates the motion disparity associated with a point using:

T=distance between a position of the moving image capture device105when a first image is captured and a position of the moving image capture device when a second image is captured,

In one embodiment, the motion distance, Z, of a pixel located at (x2,y2) is determined by:

T=distance between a position of the moving image capture device105when a first image is captured and a position of the moving image capture device when a second image is captured. In one embodiment, T is estimated from the velocity of the moving image capture device105, or the velocity of a system including the moving image capture device105, and the time difference between capture of the first image and capture of the second image.

(vx,vy)=optical flow associated with the pixel at location (x2,y2)

(cx,cy)=horizontal and vertical coordinate of the focus of expansion.

The scale, α, to be determined is defined with respect to the stereo disparity and the motion disparity as:
d=α{tilde over (d)}
Hence, the scale, α, is expressed in terms of the baseline, B, the focal length, f, and the distance the moving image capture device105moves between capturing a first image and a second image according to:

Because the distance between the position of the moving image capture device105when the first image is captured and the position of the moving image capture device105when the second image is captured is unknown, the scale is initially unknown, so a scale estimate is selected530. In one embodiment, the initial scale value estimate is a predetermined value. Alternatively, the distance traveled by the moving image capture device105between capture of the first image and capture of the second image is estimated from the velocity of the moving image capture device105, or from the velocity of a system including the moving image capture device105, and the time difference between the first image and the second image. The product of the stereo image capture device107baseline and focal length is divided by the estimated moving image capture device105distance change to select530the scale estimate.

For multiple pixels in an image, the scale estimate is used to calculate a difference between the stereo disparity associated with a pixel and the motion disparity associated with the pixel. The median of the differences between the stereo disparity and motion disparity for multiple pixels is calculated540and associated550with the scale estimate. For example, the difference between the stereo disparity and the motion disparity of a pixel, p, in an image is calculated using:
errp=|dp−α{tilde over (d)}p|
where:

dp=stereo disparity at pixel p and

Calculating540the median of the differences between stereo disparity and scaled motion disparity and associating the median with the scale value allows the moving obstacle detection module150to store data describing the median error between stereo disparity and scaled stereo disparity when different scales are applied to the motion disparity. The scale is then modified560and the modified scale is used to calculate540the median difference between stereo disparity and scaled motion disparity for multiple pixels in the image which is associated550with the modified scale and stored.

In one embodiment, modification560increases the scale by a fixed amount. The median difference between stereo disparity and motion disparity for various pixels in the image is calculated540using the increased scale. If the median value associated with the increased scale is less than the median value associated with the prior scale, the increased scale is again increased by the fixed amount. If the median value associated with the increased scale is greater than the median value associated with the prior scale, the scale is decreased by a second fixed amount, such as decreasing the scale by half of the fixed amount. In this embodiment, the scale is increased or decreased responsive to the effect of different scales on the median difference between stereo disparity and scaled motion disparity.

The scale associated with the minimum median difference between stereo disparity and motion disparity is then selected570from scales associated with stored median differences between stereo disparity and scaled motion disparity. The scale associated with the minimum stored median difference is subsequently used with the stereo disparity and motion disparity associated with a pixel in the image to determine whether the pixel is associated with a moving object. In one embodiment, the scale associated with the minimum median difference between stereo disparity and motion disparity, α*, allows identification of pixels associated with a moving object when:
|d−α*{tilde over (d)}>c

Hence, when the difference between the stereo distance associated with a point, d, and the product of the selected scale, α*, and the motion distance, {tilde over (d)}p, associated with a pixel exceeds a threshold value, c, the pixel is associated with a moving object. Using the median difference between stereo distance and motion distance improves the accuracy of scale selection by reducing errors caused by non-stationary objects.

FIG. 6is a flowchart of an alternative embodiment of a method for determining240a scale of an image captured by a moving image capture device105. Those of skill in the art will recognize that one or more steps of the method for determining240the scale may be implemented in embodiments of hardware and/or software or combinations thereof. In an embodiment, the steps of the method for determining240the scale are implemented by the processor110executing software or firmware instructions that cause the described actions, such as instructions stored in a computer-readable storage medium, such as the memory140or the motion moving obstacle detection module150. Furthermore, those of skill in the art will recognize that other embodiments can perform the steps ofFIG. 6in different orders and that additional embodiments can include different and/or additional steps than the ones described here.

Initially, the disparity determination module156calculates610,620stereo disparity of various pixels within an image and the motion disparity of various pixels within the image as described above in conjunction withFIG. 5. For multiple pixels within the image, the ratio between a stereo disparity associated with a pixel and a motion disparity associated with the pixel is calculated630. In one embodiment, the ratio, Rp, of stereo disparity and motion disparity at a pixel, p, is calculated630as:

dp=stereo disparity at pixel p and

The median of the ratios of motion disparity to stereo disparity at various pixels is calculated640and the median is selected650as the scale. In one embodiment, the median of the ratios accounts for each pixel in the image for which a ratio was calculated630. Alternatively, the median of the ratios accounts for a subset of pixels in the image for which a ratio was calculated.

While particular embodiments and applications of the present invention have been illustrated and described herein, it is to be understood that the invention is not limited to the precise construction and components disclosed herein and that various modifications, changes, and variations may be made in the arrangement, operation, and details of the methods and apparatuses of the present invention without departing from the spirit and scope of the invention as it is defined in the appended claims.