Method and apparatus for detecting independent motion in three-dimensional scenes

• US 6,353,678 B1
• Filed: 07/13/2000
• Issued: 03/05/2002
• Est. Priority Date: 07/14/1999
• Status: Expired due to Term

• Current Assignee: SRI International, Inc.
• Original Assignee: Sarnoff Corporation (SRI International, Inc.)
• Inventors: Guo, Yanlin, Sawhney, Harpreet, Kumar, Rakesh
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Bali, Vikkram
• Application Number:
  US09/614,690
• Time in Patent Office: 600 Days
• Field of Search: 382/154, 382/103, 382/107, 382/284, 382/128, 382/199, 382/106, 345/419, 345/427, 356/12
• US Class Current: 382/154
• CPC Class Codes: G06T 7/285 using a sequence of stereo image pairs
• CPC Class Codes: G06V 10/147 Details of sensors, e.g. sensor lenses fingerprint or palmprint sensors G06V40/13; vascular sensors G06V40/145; eye sensors G06V40/19

Abstract

A system and method that detects independently moving objects in 3D scenes which are viewed under camera motion progressively applies constraints to the images to ensure the stability of the constraints. The system first calculates 2D view geometry constraints for a set of images. These constraints are tested to determine if the imaged scene exhibits significant 3D characteristics. If it does, then 3D shape constraints, are applied to the set of images. The 3D shape constraints are themselves constrained by the 2D view geometry constraints. The set of images is then tested to identify areas that are inconsistent with the 2D or 3D constraints. These areas correspond to the moving objects. The 2D view geometry constraints are calculated by computing a dominant image alignment for successive pairs of images and then computing constrained epipolar transformations for the two image pairs. This 2D view geometry is further refined based on a plurality of target point correspondences among the plurality of frames. The epipolar geometry for the point correspondence having a minimum median error is selected as the 2D view geometry of the scene. The 3D shape constraint is a parallax geometry that is calculated by iteratively minimizing errors in a parametric alignment of the images using an estimated parallax geometry.

Claims

1. A method for detecting independently moving objects in a video sequence of successive images of a three-dimensional (3D) scene at least two of the images being taken from respectively different camera positions, the method comprising the steps of:

selecting a group of images including the at least two images taken from different camera positions;

calculating a set of two-dimensional (2D) view geometry constraints for the group of images;

testing the 2D view geometry constraints to determine if the imaged scene exhibits significant 3D characteristics;

if the imaged scene exhibits significant 3D characteristics, calculating a set of 3D shape constraints for the group of images, wherein the 3D shape constraints are constrained by the 2D view geometry constraints; and

if the imaged scene exhibits significant 3D characteristics, identifying areas in the group of images that are inconsistent with 3D constraints as areas corresponding to the moving objects.

2. A method according to claim 1, further including the step of, if the imaged scene does not exhibit significant 3D characteristics, identifying areas in the group of images that are inconsistent with the 2D constraints as areas corresponding to the moving objects.

3. A method according to claim 1, wherein the step of calculating the 2D view geometry constraints includes the step of computing respective dominant image alignments for successive pairs of images.

4. A method according to claim 3, wherein the step of calculating the 2D view geometry constraints further includes the step of computing epipolar geometries for the successive image pairs, wherein the epipolar geometries are constrained by the respective dominant image alignments.

5. A method according to claim 4, wherein the step of computing epipolar geometries for the successive image pairs includes the steps of:

selecting a plurality of target point correspondences among the successive images;

calculating respective epipolar geometries for each of the plurality of target point correspondences;

calculating a median error for each calculated epipolar geometry; and

selecting one of the epipolar geometries having a minimum median error as the 2D view geometry of the scene.

6. A method according to claim 5, further including the steps of:

comparing the point correspondences to the selected epipolar geometry to separate the point correspondences into inlier point correspondences that conform to the selected epipolar geometry and outlier point correspondences that do not conform to the selected epipolar geometry;

calculating a refined epipolar geometry responsive to the inlier point correspondences;

testing the refined epipolar geometry against the sequence of images to determine if the refined epipolar geometry corresponds to the dominant plane of the images or to ones of the moving objects and, if the epipolar geometry corresponds to the dominant plane, providing the epipolar geometry as the 2D view geometry of the scene;

if the refined epipolar geometry is determined to correspond to the ones of the moving objects, redefining the inlier point correspondences as further outlier point correspondences and the outlier point correspondences as further inlier point correspondences, calculating a further refined epipolar geometry responsive to the further inlier point correspondences and providing the further refined epipolar geometry as the 2D view geometry of the scene.

7. A method according to claim 6, further including the steps of:

selecting a first pair of images of the sequence of images;

estimating a parallax geometry for the first pair of images by selecting an initial estimate of the parallax geometry and adjusting the estimated parallax geometry to iteratively minimize errors in a parametric alignment of the first pair of images;

selecting a second pair of images of the sequence of images; and

estimating a further parallax geometry for the second pair of images by further adjusting the estimated parallax geometry to minimize errors in a parametric alignment of the second pair of images.

8. Apparatus for detecting independently moving objects in a video sequence of successive images of a three-dimensional (3D) scene at least two of the images being taken from respectively different camera positions, the apparatus comprising:

a video camera and a memory which are controlled to obtain a group of images of the sequence of images, the group of images including the at least two images taken from different camera positions;

means for calculating a set of two-dimensional (2D) view geometry constraints for the group of images;

means for testing the 2D view geometry constraints to determine if the imaged scene exhibits significant 3D characteristics;

means for calculating a set of 3D shape constraints for the group of images if the imaged scene exhibits significant 3D characteristics, wherein the 3D shape constraints are constrained by the 2D view geometry constraints; and

means for identifying areas in the group of images that are inconsistent with 3D constraints as areas corresponding to the moving objects if the imaged scene exhibits significant 3D characteristics.

9. Apparatus according to claim 8, further including means for identifying areas in the group of images that are inconsistent with the 2D constraints as areas corresponding to the moving objects if the imaged scene does not exhibit significant 3D characteristics.

10. Apparatus according to claim 8, wherein the means for calculating the set of 2D view geometry constraints includes means for computing respective dominant image alignments for successive pairs of images.

11. Apparatus according to claim 10, wherein the means for calculating the set of 2D view geometry constraints includes a pyramid processor that calculates a Laplacian decomposition of each image and means for calculating a parametric transformation between images in each successive pair of images by calculating the parametric transformation between successive levels of the respective Laplacian decompositions of the images.

12. Apparatus according to claim 10, wherein the means for calculating the 2D view geometry constraints further includes means for computing epipolar geometries for the successive image pairs, wherein the epipolar geometries are constrained by the respective dominant image alignments.

13. Apparatus according to claim 12, wherein the means for computing epipolar geometries for the successive image pairs includes:

means for selecting a plurality of target point correspondences from among the successive images;

means for calculating respective epipolar geometries for each of the plurality of target point correspondences;

means for calculating a median error for each calculated epipolar geometry; and

means for selecting one of the epipolar geometries having the minimum median error as the 2D view geometry of the scene.

14. Apparatus according to claim 13, further including:

means for comparing the point correspondences to the selected epipolar geometry to separate the point correspondences into inlier point correspondences that conform to the selected epipolar geometry and outlier point correspondences that do not conform to the selected epipolar geometry;

means for calculating a refined epipolar geometry responsive to the inlier point correspondences;

means for testing the refined epipolar geometry against the sequence of images including;

means for determining if the refined epipolar geometry corresponds to the dominant plane of the images or to ones of the moving objects; and

means for providing the refined epipolar geometry as the 2D view geometry of the scene if the refined epipolar geometry corresponds to the dominant plane;

means for redefining the inlier point correspondences as further outlier point correspondences and the outlier point correspondences as further inlier point correspondences if the refined epipolar geometry is determined to correspond to the ones of the moving objects, and for calculating a further refined epipolar geometry responsive to the further inlier point correspondences and for providing the further refined epipolar geometry as the 2D view geometry of the scene.

15. Apparatus according to claim 14, further including:

means for selecting a first pair of images of the sequence of images;

means for estimating a parallax geometry for the first pair of images by selecting an initial estimate of the parallax geometry and adjusting the estimated parallax geometry to iteratively minimize errors in a parametric alignment of the first pair of images;

means for selecting a second pair of images of the sequence of images; and

means for estimating a further parallax geometry for the second pair of images by further adjusting the estimated parallax geometry to minimize errors in a parametric alignment of the second pair of images.

16. An article of manufacture comprising a carrier including a plurality of computer program instructions, the computer program instructions causing a general purpose computer to perform a method of detecting independently moving objects in a video sequence of successive images of a three-dimensional (3D) scene, at least two of the images being taken from respectively different camera positions, the method comprising the steps of:

selecting a group of images including the at least two images taken from different camera positions;

calculating a set of two-dimensional (2D) view geometry constraints for the group of images;

testing the 2D view geometry constraints to determine if the imaged scene exhibits significant 3D characteristics;

if the imaged scene exhibits significant 3D characteristics, calculating a set of 3D shape constraints for the group of images, wherein the 3D shape constraints are constrained by the 2D view geometry constraints; and

if the imaged scene exhibits significant 3D characteristics, identifying areas in the group of images that are inconsistent with 3D constraints as areas corresponding to the moving objects.

17. An article of manufacture according to claim 16 wherein the computer program instructions that cause the computer to calculate the 2D view geometry constraints include instructions that cause the computer to calculate respective dominant image alignments for successive pairs of images.

18. An article of manufacture according to claim 17, wherein the computer program instructions that cause the computer to calculate the 2D view geometry constraints further include computer program instructions that cause the computer to calculate epipolar geometries for the successive image pairs, wherein the epipolar geometries are constrained by the respective dominant image alignments.

19. An article of manufacture according to claim 18, wherein the computer program instructions that cause the computer to calculate the epipolar geometries for the successive image pairs include computer program instructions that cause the computer to perform the steps of:

selecting a plurality of target point correspondences among the successive images;

calculating respective epipolar geometries for each of the plurality of target point correspondences;

calculating a median error for each calculated epipolar geometries; and

selecting one of the epipolar geometries having the minimum median error as the 2D view geometry of the scene.

20. An article of manufacture according to claim 19 further including computer program instructions that cause the computer to perform the steps of:

comparing the point correspondences to the selected epipolar geometry to separate the point correspondences into inlier point correspondences that conform to the selected epipolar geometry and outlier point correspondences that do not conform to the selected epipolar geometry;

calculating a refined epipolar geometry responsive to the inlier point correspondences;

testing the refined epipolar geometry against the sequence of images to determine if the refined epipolar geometry corresponds to the dominant plane of the images or to ones of the moving objects and if the epipolar geometry corresponds to the dominant plane, providing the epipolar geometry as the 2D view geometry of the scene;

if the refined epipolar geometry is determined to correspond to the ones of the moving objects, redefining the inlier point correspondences as further outlier point correspondences and the outlier point correspondences as further inlier point correspondences, calculating a further refined epipolar geometry responsive to the further inlier point correspondences and providing the further refined epipolar geometry as the 2D view geometry of the scene.

21. An article of manufacture according to claim 20, further including computer program instructions that cause the computer to perform the steps of:

selecting a first pair of images of the sequence of images;

estimating a parallax geometry for the first pair of images by selecting an initial estimate of the parallax geometry and adjusting the estimated parallax geometry to iteratively minimize errors in a parametric alignment of the first pair of images;

selecting a second pair of images of the sequence of images; and

estimating a further parallax geometry for the second pair of images by all further adjusting the estimated parallax geometry to minimize errors in a parametric alignment of the second pair of images.