Method and apparatus for fast computational stereo

• US 8,705,877 B1
• Filed: 11/15/2011
• Issued: 04/22/2014
• Est. Priority Date: 11/11/2011
• Status: Active Grant

• Current Assignee: Golden Edge Holding Corporation
• Original Assignee: Edge Technologies, Inc
• Inventors: Cluster, Jordan, El Dokor, Tarek
• Primary Examiner(s): Patel, Jayesh A
• Assistant Examiner(s): Kholdebarin, Iman K
• Application Number:
  US13/297,029
• Time in Patent Office: 889 Days
• Field of Search: 382/154, 382/128, 382/224, 382/225, 382/173, 345419-427
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2207/10021 Stereoscopic video; Stereoscopic image sequence
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20112 Image segmentation details
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: H05K 999/99 dummy group

Abstract

A method, system and computer program for segmenting an image are provided. The method may include the steps of acquiring a plurality of images, and clustering pixels from one of the plurality of images into one or more segments, each segment being defined in a state of either stable, mesostable or unstable. The clustering may include the steps of determining residual pixels changing by more than a predetermined threshold, grouping the determined residual pixels to form segments selected from the group of unstable and mesostable segments, determining depth for all unstable and mesostable segments, transitioning unstable segments to corresponding mesostable segments if predetermined stability criteria are met, transitioning mesostable segments to corresponding stable segments upon a determination that the mesostable segments have remained stable for a predetermined number of frames, and merging stable and mesostable segments.

Claims

1. A method for segmenting an image, comprising the steps of:

acquiring, through an image acquisition system, a plurality of images;

clustering pixels from one of the plurality of images into one or more segments, each segment being defined in a state of either stable, mesostable or unstable, the clustering further comprising the steps of;

determining one or more residual pixels changing by more than a predetermined threshold;

grouping the one or more determined residual pixels to form one or more segments selected from the group of unstable and mesostable segments;

determining depth for all unstable and mesostable segments;

transitioning one or more unstable segments to one or more corresponding mesostable segments if one or more predetermined stability criteria are met;

transitioning one or more mesostable segments to one or more corresponding stable segments upon a determination that the one or more mesostable segments have remained stable for a predetermined number of frames; and

merging one or more stable and mesostable segments.

2. The method of claim 1, wherein the stable and mesostable segments are merged when a color match therebetween is determined for adjacent segments.

3. The method of claim 1, wherein the one or more residual pixels are determined to have changed color by more than the predetermined threshold.

4. The method of claim 1, wherein the depth for all unstable and mesostable segments is determined in a grayworld.

5. The method of claim 1, wherein the depth for all unstable and mesostable segments is determined in color.

6. The method of claim 1, wherein the depth for all unstable and mesostable segments is determined in a grayworld, and in a colorspace, further comprising the step of combining the colorspace depth and the grayworld depth to provide an overall depth map.

7. The method of claim 1, wherein the depth for all unstable and mesostable segments is determined with respect to two orthogonal features, further combining the step of combining the two orthogonal depths to provide an overall depth map.

8. The method of claim 1, further comprising the step of transitioning a stable segment to a mesostable segment when change less than a predetermined threshold is determined.

9. The method of claim 1, further comprising the step of transitioning a stable segment to an unstable segment when change greater than a predetermined threshold is determined.

10. The method of claim 1, further comprising the step of generating a depth map associated with the one of the plurality of images in accordance with the determined segments.

11. The method of claim 10, further comprising the step of repeating the process for generating the depth map of a next sequential frame from the plurality of acquired images.

12. The method of claim 11, wherein a depth map associated with the next sequential frame is generated by starting with the depth map associated with the one of the plurality of images, and recalculating depth associated with one or more pixels that have been reclassified.

13. A non-transitory computer program stored to a non-volatile computer medium, the computer program causing a multi-purpose computer to segment an image by performing the steps of:

acquiring, through an image acquisition system, a plurality of images;

clustering pixels from one of the plurality of images into one or more segments, each segment being defined in a state of either stable, mesostable or unstable, the clustering further comprising the steps of;

determining one or more residual pixels changing by more than a predetermined threshold;

grouping the one or more determined residual pixels to form one or more segments selected from the group of unstable and mesostable segments;

determining depth for all unstable and mesostable segments;

transitioning one or more unstable segments to one or more corresponding mesostable segments if one or more predetermined stability criteria are met;

transitioning one or more mesostable segments to one or more corresponding stable segments upon a determination that the one or more mesostable segments have remained stable for a predetermined number of frames; and

merging one or more stable and mesostable segments.

14. The computer program of claim 13, wherein the stable and mesostable segments are merged when a color match therebetween is determined.

15. The computer program of claim 13, wherein the one or more residual pixels are determined to have changed color by more than the predetermined threshold.

16. The computer program of claim 13, wherein the depth for all unstable and mesostable segments is determined in a grayworld.

17. The computer program of claim 13, wherein the depth for all unstable and mesostable segments is determined in color.

18. The computer program of claim 13, wherein the depth for all unstable and mesostable segments is determined in a grayworld, and in a colorspace, further comprising the step of combining the colorspace depth and the grayworld depth to provide an overall depth map.

19. The computer program of claim 13, wherein the depth for all unstable and mesostable segments is determined with respect to two or more orthogonal feature spaces, further combining the step of combining the two orthogonal depths to provide an overall depth map.

20. The computer program of claim 13, the computer program causing the computer to perform the step of transitioning a stable segment to a mesostable segment when change less than a predetermined threshold is determined.

21. The computer program of claim 13, the computer program causing the general purpose computer to perform the step of transitioning a stable segment to an unstable segment when change greater than a predetermined threshold is determined.

22. The computer program of claim 13, the computer program causing the general purpose computer to perform the step of generating a depth map associated with the one of the plurality of images in accordance with the determined segments.

23. The computer program of claim 13, the computer program causing the general purpose computer to perform the step of repeating the process for generating the depth map of a next sequential frame from the plurality of acquired images.

24. The computer program of claim 23, wherein a depth map associated with the next sequential frame is generated by starting with the depth map associated with the one of the plurality of images, and recalculating depth associated with one or more pixels that have been reclassified.