Method and apparatus for fast computational stereo

• US 8,761,509 B1
• Filed: 11/15/2011
• Issued: 06/24/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,144
• Time in Patent Office: 952 Days
• Field of Search: 382/154
• US Class Current: 382/173
• 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 system may include an image acquisition system for acquiring a plurality of images; and a processor for clustering pixels from one of the images into one or more segments, each segment being defined in a state of either stable, mesostable or unstable, the processor further performing the clustering by 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 the unstable segment is determined to have a valid depth, transitioning mesostable segments to corresponding stable segments upon a determination that one or more predetermined stability criteria have been met, and merging one or more stable and mesostable segments.

Claims

1. A system for segmenting an image, comprising:

an image acquisition system for acquiring a plurality of images; and

a processor for 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 processor further performing the clustering by 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 the unstable segment is determined to have a valid depth, transitioning one or more mesostable segments to one or more corresponding stable segments upon a determination that one or more predetermined stability criteria have been met, and merging one or more stable and mesostable segments.

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

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

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

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

6. The system of claim 1, wherein the depth for all unstable and mesostable segments is further determined by the processor determined in a grayworld, and in a colorspace, and wherein the processor is further adapted to combine the colorspace depth and the grayworld depth to provide an overall depth map.

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

8. The system of claim 1, wherein the processor is further adapted to transition a stable segment to a mesostable segment when change less than a predetermined threshold is determined.

9. The system of claim 1, wherein the processor is further adapted to transition a stable segment to an unstable segment when change greater than a predetermined threshold is determined.

10. The system of claim 1, wherein the processor is further adapted to generate a depth map associated with the one of the plurality of images in accordance with the determined segments.

11. The system of claim 10, wherein the processor is further adapted to generate a depth map of a next sequential frame from the plurality of acquired images.

12. The system of claim 11, wherein a depth map associated with the next sequential frame is generated by the processor 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. The system of claim 1, wherein the processor comprises a Graphical Processing Unit (GPU).

14. The system of claim 13, wherein the architecture of the GPU is exploited, the GPU further comprising a thread scheduler to account for one or more local statistics.

15. The system of claim 13, wherein the GPU computes a GPU-based depth by efficiently implementing disparity decomposition from one of right-to-left or left-to-right.

16. The system of claim 13, further comprising an API for the GPU that enables access to crude data associated therewith.

17. The system of claim 16, wherein the API further comprises one or more access points for debugging the depth map that is associated with the GPU.

18. The system of claim 16, wherein the API is adapted to receive a specification of one or more different FLOPs loads associated with a stack itself, based on the accuracy of the intended depth computation, as an optimization process relative to cost.

19. The system of claim 13, wherein the GPU takes advantage of cache coherency between the GPU and CPU on-board a system on a chip.

20. The system of claim 13, wherein the GPU is an embedded GPU.

21. The system of claim 13, wherein the GPU is a discrete GPU.

22. The system of claim 13, wherein the GPU integrates one or more stability criteria into one or more alpha-encoded bytes that are associated with images stored in global memory on the GPU.