Segmenting three-dimensional video images using stereo

• US 6,873,723 B1
• Filed: 06/30/1999
• Issued: 03/29/2005
• Est. Priority Date: 06/30/1999
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Romrell, David A., Aucsmith, David W.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Chawan, Sheela
• Application Number:
  US09/346,499
• Time in Patent Office: 2,099 Days
• Field of Search: 382/154, 382/173, 382/199, 382/266, 382/281, 382/291, 382/219, 345/84, 345/419, 345/420, 345/421, 345/582, 348/159, 348/43, 348/586
• US Class Current: 382/154
• CPC Class Codes: G06T 2207/10012 Stereo images
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

The present invention is a method and apparatus to segment a three-dimensional scene having foreground and background regions. Regions in stereo images of the 3-D scene are matched. The stereo images include left and right images. Ranges of matched regions are computed. The foreground region is separated from the background region using the computed ranges of the matched regions.

Claims

1. A method comprising:

matching regions in stereo images of a three-dimensional (3-D) scene, the 3-D scene having foreground and background regions, the stereo images including left and right images;

computing ranges of matched regions; and

separating the foreground region from the background region using the computed ranges of the matched regions.

2. The method of claim 1 wherein matching comprises:

segmenting the left and right images into left and right regions, respectively;

determining a characteristic for each of the left and right regions; and

matching one of the left regions to one of the right regions based on the characteristics in the one of the left regions and the one of the right regions and a similarity measure.

3. The method of claim 2 wherein the characteristic is one of a local busyness, a local variance, a local color distribution, a local gray level distribution, and a neighborhood spatial relationship.

4. The method of claim 3 wherein matching one of the left regions to one of the right regions comprises:

computing correlation measures between the left and right regions; and

selecting the left and right regions that have a best correlation measure.

5. The method of claim 2 wherein the left and right regions include one or more left and right points, respectively.

6. The method of claim 5 wherein computing ranges comprise:

obtaining image coordinates of the matched points, the matched points corresponding to an object point in the 3-D scene; and

computing a depth coordinate of the object point using the image coordinates, focal lengths of imaging devices that capture the 3-D scene, and a distance between the imaging devices, the depth coordinate corresponding to the range of the object point.

7. The method of claim 6 wherein separating comprises:

comparing the range of object point to a range limit; and

assigning the object point to the background region if the range is less than the range limit.

8. The method of claim 7 wherein the range limit is provided by a context database.

9. The method of claim 8 wherein the range limit is provided by a context database.

10. The computer program product of claim 8 wherein the range limit is provided by a context database.

11. A computer program product comprising:

a computer usable medium having computer program code embodied therein to segment a three-dimensional scene having foreground and background regions, the computer program code comprising;

computer readable program code for matching regions in stereo images of the 3-D scene, the stereo images including left and right images;

computer readable program code for computing ranges of matched regions; and

computer readable program code for separating the foreground region from the background region using the computed ranges of the matched regions.

12. The computer program product of claim 11 wherein the computer readable program code for matching comprises:

computer readable program code for segmenting the left and right images into left and right regions, respectively;

computer readable program code for determining a characteristic for each of the left and right regions; and

computer readable program code for matching one of the left regions to one of the right regions based on the characteristics in the one of the left regions and the one of the right regions and a similarity measure.

13. The computer program product of claim 12 wherein the characteristic is one of a local busyness, a local variance, a local color distribution, a local gray level distribution, and a neighborhood spatial relationship.

14. The computer program product of claim 13 wherein the computer readable program code for matching one of the left regions to one of the right regions comprises:

computer readable program code for computing correlation measures between the left and right regions; and

computer readable program code for selecting the left and right regions that have a best correlation measure.

15. The computer program product of claim 12 wherein the left and right regions include one or more left and right points, respectively.

16. The computer program product of claim 15 wherein the computer readable program code for computing ranges comprise:

computer readable program code for obtaining image coordinates of the matched points, the matched points corresponding to an object point in the 3-D scene; and

computer readable program code for computing a depth coordinate of the object point using the image coordinates, focal lengths of imaging devices that capture the 3-D scene, and a distance between the imaging devices, the depth coordinate corresponding to the range of the object point.

17. The computer program product of claim 16 wherein the computer readable program code for separating comprises:

computer readable program code for comparing the range of object point to a range limit; and

computer readable program code for assigning the object point to the background region if the range is less than the range limit.

18. The computer program product of claim 17 wherein the range limit is provided by a context database.

19. A system comprising:

an imaging device to capture images of a three-dimensional scene;

a video processor coupled to the imaging device to segment a three-dimensional (3-D) scene having foreground and background regions, the video processor comprising;

a correspondence analyzer to match regions in stereo images of the (3-D) scene, the stereo images including left and right images,

a range calculator coupled to the correspondence analyzer to compute ranges of matched regions, and

a foreground separator coupled to the range calculator to separate the foreground region from the background region using the computed ranges of the matched regions.

20. The system of claim 19 wherein the correspondence analyzer comprises:

left and right segmenters to segment the left and right images into left and right regions, respectively, the left and right segmenters determining a characteristic for each of the left and right regions; and

a stereo matcher coupled to the left and right segmenters to match one of the left regions to one of the right regions based on the characteristics in the one of the left regions and the one of the right regions and a similarity measure.

21. The system of claim 20 wherein the characteristic is one of a local busyness, a local variance, a local color distribution, a local gray level distribution, and a neighborhood spatial relationship.

22. The system of claim 21 wherein the stereo matcher comprises:

a correlator to compute correlation measures between the left and right regions, the correlator selecting the left and right regions that have a best correlation measure.

23. The system of claim 20 wherein the left and right regions include one or more left and right points, respectively.

24. The system of claim 23 wherein the range calculator computes a depth coordinate of the object point using image coordinates of the matched points, focal lengths of imaging devices that capture the 3-D scene, and a distance between the imaging devices, the matched points corresponding to an object point in the 3-D scene, the depth coordinate corresponding to the range of the object point.

25. The system of claim 24 wherein the foreground separator comprises:

a comparator to compare the range of object point to a range limit, the comparator assigning the object point to the background region if the range is less than the range limit.

26. The system of claim 25 wherein the range limit is provided by a context database.

27. The system of claim 26 wherein the range limit is provided by a context database.