Patent Description:
Prior Art approaches for egomotion estimation usually involve detection of persistent features across images, such as described by <NPL>, which describes using a scale-invariant feature transform (SIFT), and by <NPL>.

These prior art approaches are computationally intensive for detection, and features may not persist across images due to variations in illumination, changing weather conditions, or occlusions. Such features are often matched with corresponding features in the next image frame using random sampling techniques, such as RANSAC, as described by <NPL>).

Such random sampling approaches, which are theoretically guaranteed to robustly estimate a motion model given enough random samplings, often require far too many random samplings to be computationally tractable in real time for low power platforms, such as unmanned autonomous vehicles.

Another "holistic" egomotion method based on the Fourier-Mellin (F-M) transformation, uses properties of geometric transformations in the spectral domain to effectively estimate a motion model for the scene. However, this approach requires computation of a two dimensional (<NUM>-D) Fourier Transform of the whole image, which is a computationally expensive operation, and which is not robust to outliers in the generic method. While the F-M based approach can be made more robust, using techniques like random sampling or a trimmed-mean approach, these techniques increase the already high computational cost and make real-time operation on a low power platform infeasible.

<NPL>, discloses an ego-motion detection algorithm compatible with hardware implementation. The algorithm utilizes local motion detection scheme based on edge-histogram matching, which enables to detect local motions robustly in segmented blocks in a visual field. An I8-dimension motion field vector is generated by summarizing local motions. Then the vector quantization is carried out to recognize the ego motion. In order to achieve further robustness, two thresholding techniques, block thresholding and median processing, are employed in the procedure. In computer simulation, over <NUM>% of detecting accuracy has been experimentally demonstrated by template matching using <NUM> template vectors generated from each of four ego-motion types.

<NPL>) discloses an ego-motion detection system where edge features are extracted from an image and analyzed to detect any motion from the camera holder instead of using the conventional method of comparing pixel intensities. Such edge-based feature representation scheme reduces the computational complexity and increases the accuracy, thus being better suited to hardware implementation due to its simplicity. In this paper we have enhanced the reliability and flexibility of the system by introducing a new pre-processing scheme in edge detection and an automatic speed adaptation capability in local motion detection. The pre-processing improves the local motion detection accuracy by only highlighting the apparent general contour edges, while filtering out insignificant features in the background which may lead to misjudgement. The automatic speed adaptation capability improves the system and renders it more flexible to accommodate to more complex motion patterns with variable speeds. The system performance has been demonstrated by simulation experiments and the robustness against disturbing moving objects in the scene has also been shown.

<NPL>, discloses an edge projection-based image registration method. First, Radon transform is used to project the edges of images along different directions, then cross-correlation-based approach is used to estimate global rotation and shift, finally polynomial fit is used to improve the accuracy of image registration, Simulation indicates that the proposed method can estimate global rotation and shift accurately and speedily.

What is needed is a computationally efficient apparatus and method for egomotion estimation. The embodiments of the present disclosure answer these and other needs.

The invention is defined by the enclosed claims.

In a first embodiment disclosed herein, a method for improving computational efficiency for egomotion estimation comprises detecting a first image, detecting a second image, wherein the second image is detected at a time after detecting the first image, forming a first edge detected image from the first image, forming a second edge detected image from the second image, dividing the first edge detected image into a first set of first edge detected image patches, dividing the second edge detected image into a second set of second edge detected image patches, wherein the second edge detected image is divided into the second set of second edge detected image patches in the same manner as the first edge detected image is divided into the first set of first edge detected image patches, determining a local translation vector for each corresponding pair of a respective first edge detected image patch and a respective second edge detected image patch by computing correlations between projections of the respective first edge detected image patch onto a first respective vertical axis and a first respective horizontal axis and the respective second edge detected image patch onto a second respective vertical axis and a second respective horizontal axis to derive a set of local translation vectors, determining a center of rotation from the set of local translation vectors, using the center of rotation to estimate a local rotation angle for each local translation vector, estimating a global rotation angle by using the local rotation angles and the corresponding local translation vectors, and estimating egomotion by calculating a two dimensional translation vector between the second image and the first image.

In another embodiment disclosed herein, a device for improving computational efficiency for egomotion estimation of a moving platform comprises a camera mounted on the platform, the camera detecting a first image and detecting a second image, wherein the second image is detected at a time after detecting the first image, and a processor coupled to the camera, the processor configured to: form a first edge detected image from the first image, form a second edge detected image from the second image, divide the first edge detected image into a first set of first edge detected image patches, divide the second edge detected image into a second set of second edge detected image patches, wherein the second edge detected image is divided into the second set of second edge detected image patches in the same manner as the first edge detected image is divided into the first set of first edge detected image patches, determine a local translation vector for each corresponding pair of a respective first edge detected image patch and a respective second edge detected image patch by computing correlations between projections of the respective first edge detected image patch onto a first respective vertical axis and a first respective horizontal axis and the respective second edge detected image patch onto a second respective vertical axis and a second respective horizontal axis to derive a set of local translation vectors, determine a center of rotation from the set of local translation vectors, use the center of rotation to estimate a local rotation angle for each local translation vector, estimate a global rotation angle by using the local rotation angles and the corresponding local translation vectors, and estimate egomotion by calculating a two dimensional translation vector between the second image and the first image.

These and other features and advantages will become further apparent from the detailed description and accompanying figures that follow. In the figures and description, numerals indicate the various features, like numerals referring to like features throughout both the drawings and the description.

In the following description, numerous specific details are set forth to clearly describe various specific embodiments disclosed herein. One skilled in the art, however, will understand that the presently claimed invention may be practiced without all of the specific details discussed below. In other instances, well known features have not been described so as not to obscure the invention.

The invention of the present disclosure takes a pair of consecutive images from a moving camera and estimates the rotation angle and the <NUM>-D translation vector that best models the camera motion between the image frames. This "egomotion estimation" is performed by breaking the pair of images into grids of overlapping patches, using an efficient projected correlation approach to estimate a local <NUM>-D translation vector for each image patch, grouping together the vectors from all image patches to obtain a vector field, and then using a trimmed-mean method to robustly and efficiently estimate the rotation angle and the <NUM>-D translation that best models the camera motion.

By modelling the motions within patches as <NUM>-D translations, the invention of the present disclosure performs the egomotion estimation of the whole image much more efficiently than prior art approaches based on feature detection as described by <NPL>, which describes a scale-invariant feature transform (SIFT), and/or random sampling (RANSAC) as described by <NPL>).

The projected correlation used to estimate the local <NUM>-D translation vectors is applied to patches, which may, for example, be patches with <NUM> x <NUM> pixels, and reduces the <NUM>-D image matching problem to a <NUM>-D correlation problem between vectors. Despite its computational efficiency, the patch-based approach is also highly robust, enabling the correct rotation angle and the correct translation vector for whole images to be estimated despite objects moving in the scene that violate the global motion model as well as individual local translation vectors having gross errors.

The improved egomotion estimation provided by this invention directly enables improved automated control and improved performance in higher-level processing. For example, using the present invention with a gyroscope or similar control system, the invention may be used to keep an object or target at the center of the field of view despite the motion of a camera. Alternatively, this invention can be used in an image processing pipeline for wide area detection and recognition of multiple objects. The improved egomotion estimation provided by this invention results in an improved motion channel input to the image processing pipeline, which results in more accurate detection and recognition of objects whose motion differs from the camera motion.

The patch-based projected correlation approach of the present invention does not rely on feature detection and matching, instead estimating a local translation vector efficiently from all of the pixels in the image patch. This enables the present invention to be more robust to variations in illumination, weather conditions, and occlusions compared to feature based approaches. In a reduction to practice, it has been seen that the estimated local <NUM>-D translation vectors are remarkably consistent with one another, enabling the use of a lighter weight, more computationally efficient robust estimation method, which for example may be the trimmed mean of the motion model for the whole image.

The following practical assumptions are made about a pair of consecutive image frames in order to efficiently and effectively estimate the egomotion of the camera between the two frames.

First, it is assumed that the consecutive images only differ by <NUM>-D rotation and translation. That is, changes of scale as well as <NUM>-D perspective effects are negligible.

Second, it is assumed that the maximum amount of translation between consecutive images is known. In practice, this can be calculated from the speed and orientation of the platform, such as the speed of an aerial platform and its distance to the ground.

Third, it is assumed that the maximum amount of the rotation between consecutive images is known. The present invention has been empirically observed to operate effectively when the rotation angle between consecutive images is less than <NUM> degrees. This is a reasonable assumption to make for consecutive image frames captured from a camera with a sufficient frame rate, for example a frame rate greater than <NUM> frames/second.

Fourth, it is assumed that the rotation happens around a known point on the image. For example, in a reduction to practice, it has been assumed that the rotation is around the optical center point.

The consecutive input images, as shown in <FIG>, are first transformed into edge images, as shown in <FIG>, respectively. For example, the current image C(x,y), as shown in <FIG>, is transformed into the edge image as shown in <FIG>, and the previous image P(x,y), as shown in <FIG> is transformed into the edge image, as shown in <FIG>. To transform the images into an edge image, an edge operator E(·) is used. The edge operator may be an edge detection method using an image gradient, such as described by <NPL>. Alternatively, an edge detection method, such as described by <NPL>, may be used. The application of the edge operator E(·) results in a sparse representation, which helps calculation and makes it easier to identify rotation in this domain.

Then the edge images, such as the edge images in <FIG>, are divided into patches, which may be overlapped and may be along a predefined grid. In a reduction to practice, a regular grid has been used; however, the measurements can potentially be taken with patches at any position. In one example, the edge images may have high definition (HD) resolution. For example, the edge images of <FIG> may have a size of <NUM> x <NUM> pixels, as shown for example in current edge image <NUM> shown in <FIG> and in previous edge image <NUM> shown in <FIG>. The image patches, for example image patches <NUM> and <NUM> in <FIG> and image patches <NUM> and <NUM> in <FIG>, may have a size of <NUM> x <NUM> pixels with a stride of <NUM> x <NUM> pixels between image patches, so that the image patches have a <NUM>% overlap or <NUM> pixel overlap in the x-direction and a <NUM>% overlap or <NUM> pixel overlap in the y-direction, as shown in <FIG>. In this example, both the previous frame edges (<FIG>) and the current frame edges (<FIG>) would each have a <NUM> x <NUM> grid of image patches or a set of <NUM> patches over the high definition (HD) resolution image of <NUM> x <NUM> pixels. The patches in within these two sets may be paired according their corresponding offsets within the larger images.

Next, relative displacements are calculated between the corresponding pairs of image patches obtained from the previous frame and current frame edge images. This results in a local translation vector for each of the <NUM> pairs of edge image patches or grid positions, such as obtained from the edge images of <FIG>. An example of the resulting set of translation vectors is shown in <FIG>.

The local translation vector for each of the image patch pairs is estimated by computing correlations between projections of the edge detected image patches onto the X- and Y- axes, as for example, shown in <FIG>, respectively, for one of the previous image patches, such as image patch <NUM> shown in <FIG>, or <FIG> for one of the current image patches, such as image patch <NUM> shown in <FIG>.

The horizontal x and vertical y projections of the image patches, for example for the edge map of <FIG>, as shown in <FIG>, respectively are calculated for each image patch. For a patch Pk the horizontal and vertical projections for the patch are defined by the following equations where Vpk, Hpk, are vertical and horizontal projections of a k'th patch from a previous edge image, and Vck, Hck are vertical and horizontal projections of a corresponding k'th patch Ck from a current edge image. <MAT> <MAT>.

The projection calculation for the patches may be optimized by using a method described by <NPL>). By indexing out four points from the integral image, the sum of a rectangular area in the integral image can be obtained without explicitly summing each element.

The horizontal edge X- and vertical edge Y-projections at any rectangular region or image patch from the integral image are derived for both the current and the previous image, as shown, for example, in <FIG>, respectively for one of the previous image patches, such as image patch <NUM> shown in <FIG>, or <FIG> for one of the current image patches, such as image patch <NUM> shown in <FIG>. Then a <NUM>-D translation is estimated that maximizes the correlation between the X- and Y- axes vectors for corresponding image patches in the current and previous images. The correlations are calculated between corresponding image patches in the current and previous images, for example between image patch <NUM> in the current image <NUM> shown in <FIG>, and the corresponding image patch <NUM> in the previous image <NUM> shown in <FIG>. More specifically, the <NUM>-D translation is estimated to be the vector that minimizes the L1 difference between the projected vectors:<MAT>.

SVk and SHk are the minimum error terms for the vertical and horizontal offsets, respectively, for the k'th pair of patches. Corresponding to SVk is a minimizing offset iVk and to SHk is an offset iHk. These offsets are components of a two-dimensional (<NUM>-D) local translation vector for the k'th patch offset. The <NUM>-D translation vector is (iHk,iVk). From the complete set of local translation estimations, for all pairs of patches k, a vector field can be displayed, as shown in <FIG>, which at every point <NUM> contains the calculated shift vector of the image patch centered at the k'th position. For example, there may be <NUM>*<NUM> = <NUM> points shown in the example of <FIG>.

Based on the fourth assumption above, it is assumed that the center of the rotation is known. However, the center of rotation may alternatively be estimated from the vector field using a method such as the eight-point algorithm described by <NPL>).

Given the center of rotation, the local rotation is estimated at every point, calculating angles between the <NUM>-D translation vectors for each pair of corresponding image patches by pointing from the center of rotation to the center of the image patch, or by pointing from the center of rotation to the end of the local translation vector.

Based on this local angle data and the local translation vector, the global rotation of the image can be estimated. A matrix is constructed containing the estimated rotation at every grid patch. The rotation values may not be the same for each grid patch due to perspective distortion, periodic structures in the image, noise, moving objects, and measurement errors. However, since these outliers are caused by noise and other factors, they result in an incoherent set of measurements, and the largest coherent set will provide the most robust estimate of the global rotation angle. Given an input image sequence having HD resolution (<NUM> x <NUM> pixels), and calculating a vector field for <NUM> x <NUM> pixel patches with <NUM>%-pixel overlap for a <NUM> x <NUM> grid of patches, as described above, for most scenes, more than half of the local rotation estimates are consistent with one another, even in sequences with many moving objects, periodic structures and non-negligible perspective distortion.

To filter out the outliers and identify the largest set, a trimmed mean calculation may be used, as described by <NPL>), (see section <NUM>, page <NUM>) to throw out the lower <NUM>% and the upper <NUM>% of the distribution. (see section <NUM>, page <NUM>)In a reduction to practice, the remaining <NUM>% always belonged to the real rotation values and the mean of this set estimated the original rotation fairly well. Alternatively, one can use a sampling method such as RANSAC as described by M. Fischler and <NPL>). Such methods are more robust, tolerating a larger percentage of outliers, but requiring a large number of samples and model fitting to find a motion model with high consensus. In the reduction to practice, it has been observed that the proportion of outliers in the vector field is relatively small, which indicates that computationally intense methods such as RANSAC are unnecessary.

Once a global rotation angle is determined, then the proportional rotation vectors may be computed corresponding to each of the k displacement vectors (iHk,iVk). Subtracting each of the rotation vectors from their corresponding displacement vector, a new set of displacement vectors are obtained that are free of distortion from rotation. The last step is to obtain a final displacement for the total image (iH,i) where iH = Tr(i'Hk), iV = Tr(i'Vk) where Tr() is a trimmed mean calculation and i'Hk, i'Vk are the displacement vectors corrected for rotation.

In the reduction to practice, the egomotion estimation performance of the present invention was qualitatively and quantitatively evaluated in comparison with other egomotion estimation methods. In all of the reduction to practice examples, the "ground truth" motion between the consecutive frames was taken to be a single global rotation of the image. It would be obvious to one with ordinary skill in the art to apply this invention to scenes that have both rotation and translation with similar performance results.

The performance of the present invention was compared to a method that estimates a single global translation for the whole image. For each method, <FIG> display for a pair of consecutive image frames from a Neovision2 dataset, the difference between the current image and the previous image, which has been transformed or corrected for translation. In <FIG>, a single global translation was estimated for both images, even though there is some rotation between the two frames. In <FIG> the rotation between frames was modelled by translating each patch by the local translation vector, in accordance with the present invention. As <FIG> shows, a prior art method that estimates a single global translation cannot handle rotation and the difference image thus has more and more high values towards the right edge of the image, because rotation is larger in these regions. On the other hand, applying local translations to every image patch using the present invention, results in very few high intensity points at the edges of the airplanes and the building, as shown in <FIG>, indicating that the transformation of the pixels using the present invention has a superior performance.

The performance of the present invention was quantitatively measured using <NUM> images randomly selected from a Neovision2 Heli dataset. Because the ground truth egomotion between consecutive frames is not known in this dataset, each of the randomly selected images were synthetically rotated and translated. For each randomly selected image, the experiment was repeated <NUM> times with different randomly generated rotation angles and <NUM>-D translation vectors, for a total of <NUM> experiments. These <NUM> experiments were repeated with four different types of edge processing, including one that simply retained the original intensity image. In <FIG> and <FIG>, these are labeled as follows: 2DGradient for a filter that computes the slope of image intensity in 2D; 1DGradient for a filter that computes the slope in one of either the x or y direction, (calculated orthogonally to the direction of the projection); Edge for a Sobel edge filter; and Intensity for the case where the image intensity is used directly. The average rotation angle error (root mean square error) of the estimated rotation was <NUM> degrees in these experiments, and the largest error was <NUM> degrees. The performance of the present invention shows that the invention is fairly robust and can be applied in practice to estimate image rotation in videos from aerial platforms.

The results were compared to an egomotion estimation method based on the prior art Fourier Mellin (F-M) transformation, as described by <NPL>), and which is a spectral method for estimating rotation, translation, and scale eqomotion from a pair of consecutive image frames. The errors for the <NUM> simulations using the F-M based egomotion estimation method are shown in <FIG>. The average root mean square error of the F-M based egomotion estimation method was <NUM> degrees. This is likely because, the FM transformation is not robust to outlier motions, which may be caused my moving objects in the scene, when the motion between images is large. The errors for the <NUM> simulations using the present invention are also shown in <FIG>, but aren't easy to see due to the gross errors of the prior art F-M based approach.

The rotation angle errors of our invention and the FM-based approach are comparable in many cases, but occasionally, the F-M transformation gives extremely poor egomotion estimation, as shown by the large errors <NUM> - the spikes in <FIG>. In a practical application, these large errors can be filtered out, because one can enforce temporal smoothness of motion between consecutive frames. For example, by assuming the image cannot turn upside-down from one frame to another.

To make a comparison using a temporal smoothness approach for the prior art F-M based approach, the gross errors in <FIG> where the rotation angle error for the F-M based approach was larger than <NUM> degrees have been removed in <FIG>. However, even with this filtering, the root mean square error (RMSE) of the prior art F-M based method was <NUM> degrees, and the highest error was <NUM> degrees, as shown in <FIG>. Meanwhile, the present invention required no filtering of gross errors and results are shown in <FIG>. It is noted that one could incorporate more robust techniques into the Fourier-Mellin transformation method, but this would require a significantly increased amount of computation, making the method infeasible for autonomous platforms with limited compute power.

Claim 1:
A method for improving computational efficiency for egomotion estimation comprising:
detecting a first image;
detecting a second image, wherein the second image is detected at a time after detecting the first image;
forming a first edge detected image (<NUM>) from the first image;
forming a second edge detected image (<NUM>) from the second image;
dividing the first edge detected image (<NUM>) into a first set of first edge detected image patches (<NUM>, <NUM>);
dividing the second edge detected image (<NUM>) into a second set of second edge detected image patches (<NUM>, <NUM>), wherein the second edge detected image (<NUM>) is divided into the second set of second edge detected image patches (<NUM>, <NUM>) in the same manner as the first edge detected image (<NUM>) is divided into the first set of first edge detected image patches (<NUM>, <NUM>);
determining a local translation vector for each corresponding pair of a respective first edge detected image patch and a respective second edge detected image patch by computing correlations between projections of the respective first edge detected image patch onto a first respective vertical axis and a first respective horizontal axis and the respective second edge detected image patch onto a second respective vertical axis and a second respective horizontal axis to derive a set of local translation vectors;
determining a center of rotation from the set of local translation vectors;
using the center of rotation to estimate a local rotation angle for each local translation vector;
estimating a global rotation angle by using the local rotation angles and the corresponding local translation vectors; and
estimating egomotion by calculating a two dimensional translation vector between the second image and the first imagewherein estimating egomotion by calculating a two dimensional translation vector between the second image and the first image comprises:
determining a horizontal and a vertical displacement for the second image (iH,iV) ;
where <MAT> and
where Tr() is a trimmed mean calculation and i'Hk, i'Vk are the local translation vectors corrected for rotation based on the global rotation angle.