Method and system to segment depth images and to detect shapes in three-dimensionally acquired data

• US 8,009,871 B2
• Filed: 02/06/2006
• Issued: 08/30/2011
• Est. Priority Date: 02/08/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rafii, Abbas, Gokturk, Salih Burak
• Primary Examiner(s): Lu; Tom Y
• Assistant Examiner(s): Conway; Thomas A
• Application Number:
  US11/349,311
• Publication Number:
  US 20060239558A1
• Time in Patent Office: 2,031 Days
• Field of Search: 382168-173, 382/180, 382/181, 382/190, 382/191, 382/195, 382/203, 382/204, 382/206, 382/209, 382/224, 382/225
• US Class Current: 382/106
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/30261 Obstacle
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

A method and system analyzes data acquired by image systems to more rapidly identify objects of interest in the data. In one embodiment, z-depth data are segmented such that neighboring image pixels having similar z-depths are given a common label. Blobs, or groups of pixels with a same label, may be defined to correspond to different objects. Blobs preferably are modeled as primitives to more rapidly identify objects in the acquired image. In some embodiments, a modified connected component analysis is carried out where image pixels are pre-grouped into regions of different depth values preferably using a depth value histogram. The histogram is divided into regions and image cluster centers are determined. A depth group value image containing blobs is obtained, with each pixel being assigned to one of the depth groups.

Claims

1. A method for use in recognizing at least one object in image depth data acquired by three-dimensional time-of-flight imaging system that includes an emitter of optical energy, an array of pixels to detect z-depth data from at least a fraction of the emitted optical energy reflected by at least one of said objects, and means for generating said image depth data by comparing emitted said optical energy and the fraction of emitted optical energy detected by said array of pixels, the method useable with a single acquisition of image depth data comprising the following steps:

(a) examining at least some of said image depth data captured during a single data acquisition;

(b) forming segments by grouping together those of said pixels whose acquired said data captured at step (a) have at least one common characteristic selected from a group consisting of depth distance, depth distance change, object size, and object shape;

(c) assigning on a per-segment basis a label to pixels comprising each of said segments formed in step (b);

wherein pixels so labeled enable recognition of said at least one object with a single acquisition of image depth data.

2. The method of claim 1, wherein:

in a single acquisition of image depth data said array of pixels further acquires intensity data; and

step (b) includes forming segments by grouping together pixels based upon their acquired intensity data.

3. The method of claim 1, further including steps:

(d) providing at least one pre-defined blob;

(e) examining said segments formed in step (b) to determine presence in said image data of a blob matching a pre-defined blob provided at step (d); and

(f) providing for output a signal commensurate with detection of a recognized pre-defined blob in said image data.

4. The method of claim 1, wherein step (b) includes forming segments by at least one of (i) grouping together pixels based upon their acquired z-depth data, and (ii) grouping together pixels based upon their acquired z-depth data, where said grouping together is based upon pre-determined z-depth values.

5. The method of claim 1, wherein step (b) includes forming segments by grouping together pixels based upon their acquired z-depth data, wherein grouped-together said pixels are within a number k of neighboring pixels, where k is selected from a group consisting of k=4 and k=8.

6. The method of claim 1, wherein step (b) includes forming segments by grouping together pixels based upon their acquired z-depth data, wherein pixels representing an overlapping portion of objects in said image data are assigned a single label.

7. The method of claim 1, wherein step (b) includes forming segments by grouping together pixels based upon their acquired z-depth data, wherein pixels representing an overlapping portion of objects in said image data are assigned values intermediate values associated with said objects.

8. The method of claim 1, wherein said imaging system is selected from a group consisting of (i) a time-counting time-of-flight system, and (ii) a time-of-flight system employing phase-shift z-depth measurement.

9. The method of claim 1, wherein step (b) includes forming segments by grouping together pixels based upon their acquired z-depth data, wherein pixels are pre-grouped based upon a histogram record of z-depth values of pixels in said array.

10. The method of claim 9, further including dividing said histogram into at least two sub-regions and determining image cluster centers such that each relevant pixel of said pixels in said array is assigned to a z-depth-determined group.

11. The method of claim 10, wherein at least two of said sub-regions overlap.

12. An image-analyzing system useable in recognizing at least one object in image depth data acquired by three-dimensional time-of-flight imaging system that includes an emitter of optical energy, an array of pixels to detect z-depth data from at least a fraction of the emitted optical energy reflected by at least one of said objects, means for generating said image depth data by comparing emitted said optical energy and the fraction of emitted optical energy detected by said array of pixels, the image-analyzing system useable with a single acquisition of image depth data comprising:

means for examining at least some of said image depth data captured during a single data acquisition;

means for forming segments by grouping together those of said pixels whose acquired said data share at least one common characteristic selected from a group consisting of depth distance, depth distance change, object size and object shape;

means for assigning on a per-segment basis a label to pixels comprising each of said segments formed by said means for forming;

wherein pixels so assigned enable recognition of said at least one object with a single acquisition of image depth data.

13. The image-analyzing system of claim 12, further including:

memory storing at least one pre-defined blob;

means for comparing said segments formed by said means for forming with contents of said memory to determine presence in said image data of a blob matching a pre-defined blob stored in said memory; and

means for providing an output signal commensurate with detection of a recognized pre-defined blob in said image data.

14. The image-analyzing system of claim 12, wherein at least two of said means for examining, said means for forming, and said means for assigning are carried out in software executable by a microprocessor in said image-analyzing system.

15. The image-analyzing system of claim 12, wherein said imaging system is selected from a group consisting of (i) a time-counting time-of-flight system, and (ii) a time-of-flight system employing phase-shift z-depth measurement.

16. The image-analyzing system of claim 12, wherein:

said array of pixels further acquires intensity data in a single acquisition of image depth data; and

said means for forming groups based upon at least one pixel characteristic selected from a group consisting of intensity data acquired by said pixels, z-depth data acquired by said pixels, and z-depth acquired data using pre-determined z-depth values.

17. The image-analyzing system of claim 16, wherein said means for forming groups together pixels that are within a number k of neighboring pixels, where k is selected from a group consisting of k=4 and k=8.

18. The image-analyzing system of claim 16, wherein said means for forming groups together pixels based upon their acquired z-depth data, wherein pixels representing an overlapping portion of objects in said image data are assigned a single label.

19. The image-analyzing system of claim 16, wherein said means for forming groups together pixels based upon their acquired z-depth data, wherein pixels representing an overlapping portion of objects in said image data are assigned values intermediate values associated with said objects.

20. The image-analyzing system of claim 16, wherein said means for forming groups together pixels based upon their acquired z-depth data, and does so in a manner selected from a group consisting of (i) pre-grouping pixels based upon a histogram record of z-depth values of pixels in said array, and (ii) pre-grouping pixels based upon their acquired z-depth data, wherein pixels are pre-grouped based upon a histogram record of z-depth values of pixels in said array, where said histogram is divided into at least two sub-regions and image cluster centers are determined such that each relevant pixel of said pixels in said array is assigned to a z-depth-determined group.