ANALYSIS OF THREE-DIMENSIONAL SCENES

• US 20110293137A1
• Filed: 08/11/2010
• Published: 12/01/2011
• Est. Priority Date: 05/31/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: PrimeSense Ltd (Apple Inc.)
• Inventors: Brand, Michael, Yanir, Tomer, Gurman, Amiad, Guendelman, Eran
• Granted Patent: US 8,594,425 B2
• Time in Patent Office: Days
• US Class Current: 382/103
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2215/12 Shadow map, environment map
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06T 7/507 from shading G06T7/586 takes precedence
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands
• CPC Class Codes: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition

Abstract

A method for processing data includes receiving a depth map of a scene containing a humanoid form. The depth map is processed so as to identify three-dimensional (3D) connected components in the scene, each connected component including a set of the pixels that are mutually adjacent and have mutually-adjacent depth values. Separate, first and second connected components are identified as both belonging to the humanoid form, and a representation of the humanoid form is generated including both of the first and second connected components.

Claims

1. A method for processing data, comprising:

receiving a temporal sequence of depth maps of a scene containing a stationary background and one or more moving foreground objects that conceal a part of the background, the depth maps comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene;

using a digital processor, processing a first depth map in the sequence so as to identify a first portion of the stationary background that is not concealed by the moving foreground objects in the first map;

processing at least a second depth map in the sequence so as to identify at least a second portion of the stationary background, which is different from the first portion due to motion of at least one of the foreground objects over the sequence; and

constructing a background model of the scene by combining at least the first and second portions of the stationary background.

2. The method according to claim 1, and comprising generating one or more foreground maps by removing, based on the background model, one or more background objects from the depth maps.

3. The method according to claim 2, wherein at least one of the moving foreground objects is a humanoid figure, and wherein the method comprises extracting the humanoid figure from a foreground map derived from the second depth map together with information relating to the humanoid figure in the first depth map.

4. The method according to claim 3, wherein extracting the humanoid figure comprises detecting an area belonging to the humanoid figure that is touching one of the background objects, and identifying the area as a part of the humanoid figure.

5. The method according to claim 1, and comprising identifying a planar surface in the depth maps.

6. The method according to claim 1, and comprising identifying a shadow of an object in the depth maps.

7. The method according to claim 1, wherein constructing the background model comprises updating the background model responsively to changes that appear in the background over the sequence of the depth maps.

8. The method according to claim 7, wherein the depth maps are captured by an imaging assembly, and wherein the method comprises assessing an extent of the changes in the background model between the depth maps in the sequence, and detecting that the imaging assembly has moved when the extent of the changes exceeds a predetermined threshold.

9. A method for processing data, comprising:

receiving a depth map of a scene containing one or more objects positioned in relation to a surface, the depth map comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene;

using a digital processor, processing the depth map so as to identify and generate a parametric model of the surface; and

segmenting one or more of the objects in the scene by removing the surface represented by the parametric model from the depth map.

10. The method according to claim 9, wherein at least one of the objects is a humanoid figure, and wherein segmenting the one or more of the objects comprises extracting the humanoid figure from the depth map.

11. The method according to claim 9, wherein the surface is a planar surface corresponding to a floor on which at least one of the objects is positioned.

12. The method according to claim 11, wherein processing the depth map comprises computing local normals at the pixels in the depth map, and clustering the pixels according to the local normals in order to identify the planar surface.

13. The method according to claim 12, wherein the depth maps are captured by an imaging assembly, and wherein clustering the local normals comprises processing respective depth values of at least some of the pixels in order to predict a height of the imaging assembly with respect to each pixel, and clustering the pixels having the same predicted height of the imaging assembly.

14. A method for processing data, comprising:

receiving a depth map of a scene containing a humanoid form, the depth map comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene;

using a digital processor, processing the depth map so as to identify three-dimensional (3D) connected components in the scene, each connected component comprising a set of the pixels that are mutually adjacent and have mutually-adjacent depth values;

identifying separate, first and second connected components as both belonging to the humanoid form; and

generating a representation of the humanoid form comprising both of the first and second connected components.

15. The method according to claim 14, wherein processing the depth map comprises constructing a background model of the scene based on the depth map, removing the background model from the depth map in order to generate a foreground map, and identifying the 3D connected components in the foreground map.

16. The method according to claim 14, wherein processing the depth map comprises locating edges in the depth map and blocks of pixels between the edges, and clustering adjacent blocks of the pixels in three dimensions in order to identify the 3D connected components.

17. The method according to claim 14, wherein receiving the depth map comprises receiving a temporal sequence of depth maps, and wherein identifying the first and second connected components comprises tracking the connected components over multiple, successive depth maps in the sequence.

18. The method according to claim 17, wherein tracking the connected components comprises assigning a common identifier to the first and second connected components in a first depth map in the sequence, and using the common identifier to determine that the first and second connected components belong to the humanoid form in a second, subsequent depth map in which the first and second connected components have been separated.

19. The method according to claim 18, wherein assigning the common identifier comprises labeling the pixels of the first and second connected components in the depth map with the common identifier.

20. The method according to claim 19, wherein the humanoid form in the second depth map is in contact with another object, thereby causing the second connected component to incorporate the other object, and wherein using the common identifier comprises separating the labeled pixels of the second connected component that belong to the humanoid form from the pixels belonging to other object in order to generate the representation of the humanoid form appearing in the second depth map.

21. The method according to claim 17, wherein tracking the connected components comprises estimating a velocity of motion of the connected components, and wherein generating the representation comprises maintaining an identification of an occluded part of the humanoid form using the estimated velocity.

22. The method according to claim 14, wherein the humanoid form in the depth map is partly occluded by another object, and wherein the first and second connected components correspond to parts of the humanoid form that are separated by the occluding object, and wherein generating the representation comprises incorporating both of the first and second connected components in the representation of the humanoid form.

23. The method according to claim 14, wherein the first and second connected components correspond to first and second parts of the humanoid form, wherein the second part partly occludes the first part in the depth map, and wherein generating the representation comprises incorporating both of the first and second connected components in the representation of the humanoid form.

24. Apparatus for processing data, comprising:

an imaging assembly, which is configured to produce a temporal sequence of depth maps of a scene containing a stationary background and one or more moving foreground objects that conceal a part of the background, the depth maps comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene; and

a processor, which is configured to process a first depth map in the sequence so as to identify a first portion of the stationary background that is not concealed by the moving foreground objects in the first map, and to process at least a second depth map in the sequence so as to identify at least a second portion of the stationary background, which is different from the first portion due to motion of at least one of the foreground objects over the sequence, and to construct a background model of the scene by combining at least the first and second portions of the stationary background.

25. The apparatus according to claim 24, wherein the processor is configured to generate one or more foreground maps by removing, based on the background model, one or more background objects from the depth maps.

26. The apparatus according to claim 25, wherein at least one of the moving foreground objects is a humanoid figure, and wherein the processor is configured to extract the humanoid figure from a foreground map derived from the second depth map together with information relating to the humanoid figure in the first depth map.

27. The apparatus according to claim 26, wherein the processor is configured to detect an area belonging to the humanoid figure that is touching one of the background objects, and to identify the area as a part of the humanoid figure.

28. The apparatus according to claim 24, wherein the processor is configured to identify a planar floor in the depth maps.

29. The apparatus according to claim 24, wherein the processor is configured to identify a shadow of an object in the depth maps.

30. The apparatus according to claim 24, wherein the processor is configured to update the background model responsively to changes that appear in the background over the sequence of the depth maps.

31. The apparatus according to claim 30, wherein the processor is configured to assess an extent of the changes in the background model between the depth maps in the sequence, and to detect that the imaging assembly has moved when the extent of the changes exceeds a predetermined threshold.

32. Apparatus for processing data, comprising:

an imaging assembly, which is configured to produce a depth map of a scene containing one or more objects positioned in relation to a surface, the depth map comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene; and

a processor, which is configured to process the depth map so as to identify and generate a parametric model of the surface, and to segment one or more of the objects in the scene by removing the surface represented by the parametric model from the depth map.

33. The apparatus according to claim 32, wherein at least one of the objects is a humanoid figure, and wherein the processor is configured to extract the humanoid figure from the depth map.

34. The apparatus according to claim 32, wherein the surface is a planar surface corresponding to a floor on which at least one of the objects is positioned.

35. The apparatus according to claim 34, wherein the processor is configured to compute local normals at the pixels in the depth map, and to cluster the pixels according to the local normals in order to identify the planar surface.

36. The apparatus according to claim 35, wherein the processor is configured to process respective depth values of at least some of the pixels in order to predict a height of the imaging assembly with respect to each pixel, and to cluster the pixels having the same predicted height of the imaging assembly.

37. Apparatus for processing data, comprising:

an imaging assembly, which is configured to produce a depth map of a scene containing a humanoid form, the depth map comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene; and

a processor, which is configured to process the depth map so as to identify three-dimensional (3D) connected components in the scene, each connected component comprising a set of the pixels that are mutually adjacent and have mutually-adjacent depth values, to identify separate, first and second connected components as both belonging to the humanoid form, and to generate a representation of the humanoid form comprising both of the first and second connected components.

38. The apparatus according to claim 37, wherein the processor is configured to construct a background model of the scene based on the depth map, to remove the background model from the depth map in order to generate a foreground map, and to identify the 3D connected components in the foreground map.

39. The apparatus according to claim 37, wherein the processor is configured to locate edges in the depth map and blocks of pixels between the edges, and to cluster adjacent blocks of the pixels in three dimensions in order to identify the 3D connected components.

40. The apparatus according to claim 37, wherein the imaging assembly is configured to produce a temporal sequence of depth maps, and wherein the processor is configured to track the connected components over multiple, successive depth maps in the sequence.

41. The apparatus according to claim 40, wherein the processor is configured to assign a common identifier to the first and second connected components in a first depth map in the sequence, and to use the common identifier to determine that the first and second connected components belong to the humanoid form in a second, subsequent depth map in which the first and second connected components have been separated.

42. The apparatus according to claim 41, wherein the processor is configured to label the pixels of the first and second connected components in the depth map with the common identifier.

43. The apparatus according to claim 42, wherein the humanoid form in the second depth map is in contact with another object, thereby causing the second connected component to incorporate the other object, and the processor is configured to separate the labeled pixels of the second connected component that belong to the humanoid form from the pixels belonging to other object in order to generate the representation of the humanoid form appearing in the second depth map.

44. The apparatus according to claim 40, wherein the processor is configured to estimate a velocity of motion of the connected components, and to maintain an identification of an occluded part of the humanoid form using the estimated velocity.

45. The apparatus according to claim 37, wherein the humanoid form in the depth map is partly occluded by another object, and wherein the first and second connected components correspond to parts of the humanoid form that are separated by the occluding object, and wherein the processor is configured to incorporate both of the first and second connected components in the representation of the humanoid form.

46. The apparatus according to claim 37, wherein the first and second connected components correspond to first and second parts of the humanoid form, wherein the second part partly occludes the first part in the depth map, and wherein the processor is configured to incorporate both of the first and second connected components in the representation of the humanoid form.

47. A computer software product, comprising a tangible computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a temporal sequence of depth maps of a scene containing a stationary background and one or more moving foreground objects that conceal a part of the background, the depth maps comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene,

wherein the instructions cause the computer to process a first depth map in the sequence so as to identify a first portion of the stationary background that is not concealed by the moving foreground objects in the first map, and to process at least a second depth map in the sequence so as to identify at least a second portion of the stationary background, which is different from the first portion due to motion of at least one of the foreground objects over the sequence, and to construct a background model of the scene by combining at least the first and second portions of the stationary background.

48. The product according to claim 47, wherein the instructions cause the computer to generate one or more foreground maps by removing, based on the background model, one or more background objects from the depth maps.

49. The product according to claim 48, wherein at least one of the moving foreground objects is a humanoid figure, and wherein the instructions cause the computer to extract the humanoid figure from a foreground map derived from the second depth map together with information relating to the humanoid figure in the first depth map.

50. The product according to claim 49, wherein the instructions cause the computer to detect an area belonging to the humanoid figure that is touching one of the background objects, and to identify the area as a part of the humanoid figure.

51. The product according to claim 47, wherein the instructions cause the computer to identify a planar floor in the depth maps.

52. The product according to claim 47, wherein the instructions cause the computer to identify a shadow of an object in the depth maps.

53. The product according to claim 47, wherein the instructions cause the computer to update the background model responsively to changes that appear in the background over the sequence of the depth maps.

54. The product according to claim 53, wherein the instructions cause the computer to assess an extent of the changes in the background model between the depth maps in the sequence, and to detect that the imaging assembly has moved when the extent of the changes exceeds a predetermined threshold.

55. A computer software product, comprising a tangible computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a depth map of a scene containing one or more foreground objects positioned in relation to a surface, the depth map comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene,

wherein the instructions cause the computer to process the depth map so as to identify and generate a parametric model of the surface, and to segment one or more of the objects in the scene by removing the surface represented by the parametric model from the depth map.

56. The product according to claim 55, wherein at least one of the objects is a humanoid figure, and wherein the instructions cause the computer to extract the humanoid figure from the depth map.

57. The product according to claim 55, wherein the surface is a planar surface corresponding to a floor on which at least one of the objects is positioned.

58. The product according to claim 57, wherein the instructions cause the computer to compute local normals at the pixels in the depth map, and to cluster the pixels according to the local normals in order to identify the planar surface.

59. The product according to claim 58, wherein the instructions cause the computer to process respective depth values of at least some of the pixels in order to predict a height of the imaging assembly with respect to each pixel, and to cluster the pixels having the same predicted height of the imaging assembly.

60. A computer software product, comprising a tangible computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to receive a depth map of a scene containing a humanoid form, the depth map comprising a matrix of pixels, at least some of which have respective pixel depth values and correspond to respective locations in the scene,

wherein the instructions cause the computer to process the depth map so as to identify three-dimensional (3D) connected components in the scene, each connected component comprising a set of the pixels that are mutually adjacent and have mutually-adjacent depth values, to identify separate, first and second connected components as both belonging to the humanoid form, and to generate a representation of the humanoid form comprising both of the first and second connected components.

61. The product according to claim 60, wherein the instructions cause the computer to construct a background model of the scene based on the depth map, to remove the background model from the depth map in order to generate a foreground map, and to identify the 3D connected components in the foreground map.

62. The product according to claim 60, wherein the instructions cause the computer to locate edges in the depth map and blocks of pixels between the edges, and to cluster adjacent blocks of the pixels in three dimensions in order to identify the 3D connected components.

63. The product according to claim 60, wherein the imaging assembly is configured to produce a temporal sequence of depth maps, and wherein the instructions cause the computer to track the connected components over multiple, successive depth maps in the sequence.

64. The product according to claim 63, wherein the instructions cause the computer to assign a common identifier to the first and second connected components in a first depth map in the sequence, and to use the common identifier to determine that the first and second connected components belong to the humanoid form in a second, subsequent depth map in which the first and second connected components have been separated.

65. The product according to claim 64, wherein the instructions cause the computer to label the pixels of the first and second connected components in the depth map with the common identifier.

66. The product according to claim 65, wherein the humanoid form in the second depth map is in contact with another object, thereby causing the second connected component to incorporate the other object, and the instructions cause the computer to separate the labeled pixels of the second connected component that belong to the humanoid form from the pixels belonging to other object in order to generate the representation of the humanoid form appearing in the second depth map.

67. The product according to claim 63, wherein the instructions cause the computer to estimate a velocity of motion of the connected components, and to maintain an identification of an occluded part of the humanoid form using the estimated velocity.

68. The product according to claim 60, wherein the humanoid form in the depth map is partly occluded by another object, and wherein the first and second connected components correspond to parts of the humanoid form that are separated by the occluding object, and wherein the instructions cause the computer to incorporate both of the first and second connected components in the representation of the humanoid form.

69. The product according to claim 60, wherein the first and second connected components correspond to first and second parts of the humanoid form, wherein the second part partly occludes the first part in the depth map, and wherein the instructions cause the computer to incorporate both of the first and second connected components in the representation of the humanoid form.