PATENT DOCUMENT

Publication Number: US-9836645-B2
Application Number: US-201514661123-A
Country: US
Kind Code: B2

Title: Depth mapping with enhanced resolution

Abstract:
A method for depth mapping includes receiving an image of a pattern of spots that has been projected onto a scene, which includes a hand having fingers. The image is processed in order to segment and find a three-dimensional (3D) location of the hand. Based on the spots appearing on the hand in the 3D location, a first depth value that is characteristic of the hand and a second depth value that is characteristic of a background of the scene behind the hand are computed. The spots in a vicinity of the hand in the image between the first and second depth values are sorted in order to extract separate, respective contours of each of the fingers. The respective contours are processed in order to identify a posture of the hand and fingers.

Claims:
The invention claimed is: 
     
       1. A method for depth mapping, comprising:
 receiving in a digital processor an image of a pattern of spots that has been projected onto a scene, which includes a hand having fingers, 
 wherein the fingers have a transverse dimension that is less than twice an average distance between the spots in the pattern that is projected onto the scene; 
 processing the image in order to segment and find a three-dimensional (3D) location of the hand, wherein processing the image comprises computing 3D coordinates of points on the hand and fingers based on transverse shifts of the spots in the image; 
 based on the spots appearing on the hand in the 3D location, computing a first depth value that is characteristic of the hand and a second depth value that is characteristic of a background of the scene behind the hand; 
 sorting the spots in a vicinity of the hand in the image between the first and second depth values in order to extract separate, respective contours of each of the fingers; and 
 processing the respective contours in order to identify a posture of the hand and fingers. 
 
     
     
       2. The method according to  claim 1 , wherein sorting the spots comprises delineating a respective contour of at least one of the fingers that has a transverse dimension that is less than the average distance between the spots in the pattern. 
     
     
       3. The method according to  claim 1 , and comprising finding depth coordinates of the points on the hand and fingers with a resolution finer than a depth increment corresponding to a transverse shift equal to the average distance between the spots in the image. 
     
     
       4. The method according to  claim 1 , wherein sorting the spots comprises delineating a respective contour of at least one of the fingers while no more than a single chain of the spots is connected along a length of each of the at least one of the fingers. 
     
     
       5. The method according to  claim 1 , wherein processing the respective contours comprises detecting gestures of the hand, and wherein the method comprises controlling an application running on a computer responsively to the gestures. 
     
     
       6. The method according to  claim 1 , wherein sorting the spots comprises:
 identifying in the image an area of shadow between the fingers; 
 adding further points to the image in the area of the shadow, and assigning the second depth value to the further points; and 
 applying the further points in delineating the contours of the fingers. 
 
     
     
       7. Apparatus for depth mapping, comprising:
 an imaging assembly, which is configured to capture an image of a pattern of spots that has been projected onto a scene, which includes a hand having fingers, 
 wherein the fingers have a transverse dimension that is less than twice an average distance between the spots in the pattern that is projected onto the scene; and 
 a processor, which is configured to process the image in order to compute 3D coordinates of points on the hand and fingers based on transverse shifts of the spots in the image, to segment and find a three-dimensional (3D) location of the hand, and to compute, based on the spots appearing on the hand in the 3D location, a first depth value that is characteristic of the hand and a second depth value that is characteristic of a background of the scene behind the hand, to sort the spots in a vicinity of the hand in the image between the first and second depth values in order to extract separate, respective contours of each of the fingers, and to process the respective contours in order to identify a posture of the hand and fingers. 
 
     
     
       8. The apparatus according to  claim 7 , wherein the processor is configured to delineate a respective contour of at least one of the fingers that has a transverse dimension that is less than the average distance between the spots in the pattern. 
     
     
       9. The apparatus according to  claim 7 , wherein the processor is configured to find depth coordinates of the points on the hand and fingers with a resolution finer than a depth increment corresponding to a transverse shift equal to the average distance between the spots in the image. 
     
     
       10. The apparatus according to  claim 7 , wherein the processor is configured to delineate a respective contour of at least one of the fingers while no more than a single chain of the spots is connected along a length of each of the at least one of the fingers. 
     
     
       11. The apparatus according to  claim 7 , wherein the processor is configured to detect gestures of the hand based on the extracted contours, and to control an application running on a computer responsively to the gestures. 
     
     
       12. The apparatus according to  claim 7 , wherein the processor is configured to identify in the image an area of shadow between the fingers, to add further points to the image in the area of the shadow, to assign the second depth coordinate to the further points, and to apply the further points in delineating the contours of the fingers. 
     
     
       13. A computer software product, comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a processor, cause the processor to receive a an image of a pattern of spots that has been projected onto a scene, which includes a hand having fingers, wherein the fingers have a transverse dimension that is less than twice an average distance between the spots in the pattern that is projected onto the scene, to process the image in order to compute 3D coordinates of points on the hand and fingers based on transverse shifts of the spots in the image, to segment and find a three-dimensional (3D) location of the hand, and to compute, based on the spots appearing on the hand in the 3D location, a first depth value that is characteristic of the hand and a second depth value that is characteristic of a background of the scene behind the hand, to sort the spots in a vicinity of the hand in the image between the first and second depth values, to extract separate, respective contours of each of the fingers using the identified cut edges, and to process the respective contours in order to identify a posture of the hand and fingers. 
     
     
       14. The method according to  claim 1 , wherein extracting the separate, respective contours comprises drawing the contours by choosing and connecting together points on the cut-edges. 
     
     
       15. The apparatus according to  claim 7 , wherein the processor is configured to draw the contours by choosing and connecting together points on the cut-edges. 
     
     
       16. The method according to  claim 1 , wherein sorting the spots comprises constructing a graph having vertices corresponding to the spots in the image, and identifying cut-edges of the graph in order to find the contours, wherein the cut-edges connect between the spots at the first and second depth values. 
     
     
       17. The apparatus according to  claim 7 , wherein the processor is configured to construct a graph having vertices corresponding to the spots in the image, and to identify cut-edges of the graph in order to find the contours, wherein the cut-edges connect between the spots at the first and second depth values.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a continuation of U.S. patent application Ser. No. 13/663,518, filed Oct. 30, 2012, which is incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to methods and systems for three-dimensional (3D) mapping, and specifically to extraction of features from 3D map data. 
     BACKGROUND 
     A number of different methods and systems are known in the art for creating depth maps. In the present patent application and in the claims, the term “depth map” refers to a representation of a scene as a two-dimensional matrix of pixels, in which each pixel corresponds to a respective location in the scene and has a respective pixel depth value, indicative of the distance from a certain reference location to the respective scene location. In other words, the depth map has the form of an image in which the pixel values indicate topographical information, rather than brightness and/or color of the objects in the scene. The terms “depth map” and “3D map” are used herein interchangeably and have the same meaning. 
     Depth maps may be created, for example, by detection and processing of an image of an object onto which a pattern of spots is projected. In some such systems, the positions of the spots are uncorrelated in planes transverse to the projection beam axis. The positions are “uncorrelated” in the sense that the auto-correlation of the positions of the speckles in the pattern as a function of transverse shift is insignificant for any shift larger than the spot size. Random patterns, such as those created by primary laser speckle, are uncorrelated in this sense. Patterns created by human or computer design, such as pseudo-random and quasi-random patterns, may also be uncorrelated. Depth mapping methods using these sorts of projected patterns are described, for example, in PCT International Publications WO 2007/043036, WO 2007/105205, WO 2008/120217, and WO 2010/004542, whose disclosures are incorporated herein by reference. 
     Depth maps may be processed in order to segment and identify objects in the scene. Identification of humanoid forms (meaning 3D shapes whose structure resembles that of a human being) in a depth map, and changes in these forms from scene to scene, may be used as a means for controlling computer applications. For example, PCT International Publication WO 2007/132451, whose disclosure is incorporated herein by reference, describes a computer-implemented method in which a depth map is segmented so as to find a contour of a humanoid body. The contour is processed in order to identify a torso and one or more limbs of the body. An input is generated to control an application program running on a computer by analyzing a disposition of at least one of the identified limbs in the depth map. 
     As another example, U.S. Patent Application Publication 2011/0052006, whose disclosure is incorporated herein by reference, describes a method for processing a temporal sequence of depth maps of a scene containing a humanoid form. A digital processor processes at least one of the depth maps so as to find a location of the head of the humanoid form, and estimates dimensions of the humanoid form based on this location. The processor tracks movements of the humanoid form over the sequence using the estimated dimensions. 
     SUMMARY 
     Embodiments of the present invention provide improved methods, apparatus and software for extracting information from depth maps, and particularly information regarding structures having fine dimensions. 
     There is therefore provided, in accordance with an embodiment of the present invention, a method for depth mapping, which includes receiving an image of a pattern of spots that has been projected onto a scene, which includes a feature having a set of elongate appendages, which have respective transverse dimensions that are less than twice an average distance between the spots in the pattern that is projected onto the feature. The image is processed in order to segment and find a three-dimensional (3D) location of the feature. The spots appearing on the feature in the 3D location are connected in order to extract separate, respective contours of the appendages. 
     In some embodiments, the spots have respective positions in the pattern that are uncorrelated, and processing the image includes computing 3D coordinates of points on the feature based on transverse shifts of the spots in the image. The depth coordinates of the points on the feature may be found with a resolution finer than a depth increment corresponding to a transverse shift equal to the average distance between the spots in the image. 
     In a disclosed embodiment, connecting the spots includes delineating a respective contour of one of the appendages that has a transverse dimension that is less than the average distance between the spots in the pattern. Additionally or alternatively, connecting the spots includes delineating a respective contour of one of the appendages while no more than a single chain of the spots is connected along a length of the one of the appendages. 
     In a disclosed embodiment, the feature includes a hand, the appendages are fingers of the hand, and the extracted contours are indicative of a posture of the hand and fingers. The method may include detecting gestures of the hand, and controlling an application running on a computer responsively to the gestures. 
     In some embodiments, connecting the spots includes computing a first depth value that is characteristic of the feature and a second depth value that is characteristic of a background of the scene behind the feature, and sorting the spots in a vicinity of the feature in the image between the first and second depth values. Connecting the spots may include identifying in the image an area of shadow between the appendages, adding further points to the image in the area of the shadow, and assigning the second depth coordinate to the further points, and applying the further points in delineating the contours of the appendages. 
     In a disclosed embodiment, connecting the spots includes constructing a graph having vertices corresponding to the spots in the image, and identifying cut-edges of the graph in order to find the contours. Connecting the spots may include identifying features of the image in a vicinity of the appendages, and finding the features that correspond to the contours responsively to the graph. 
     There is also provided, in accordance with an embodiment of the present invention, apparatus for depth mapping, which includes an imaging assembly, which is configured to capture an image of a pattern of spots that has been projected onto a scene, which includes a feature having a set of elongate appendages, which have respective transverse dimensions that are less than twice an average distance between the spots in the pattern that is projected onto the feature. A processor is configured to process the image in order to segment and find a three-dimensional (3D) location of the feature and to connect the spots appearing on the feature in the 3D location in order to extract separate, respective contours of the appendages. 
     There is additionally provided, in accordance with an embodiment of the present invention, a computer software product, including a computer-readable medium in which program instructions are stored, which instructions, when read by a processor, cause the processor to receive a an image of a pattern of spots that has been projected onto a scene, which includes a feature having a set of elongate appendages, which have respective transverse dimensions that are less than twice an average distance between the spots in the pattern that is projected onto the feature, and to process the image in order to segment and find a three-dimensional (3D) location of the feature and to connect the spots appearing on the feature in the 3D location in order to extract separate, respective contours of the appendages. 
     The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken together with the drawings in which: 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is schematic, pictorial illustration of a depth mapping system, in accordance with an embodiment of the present invention; 
         FIG. 2  is a schematic representation of a depth map that is captured and processed in a depth mapping system, in accordance with an embodiment of the present invention; 
         FIG. 3  is a flow chart that schematically illustrates a method for finding a contour of a hand in a depth map, in accordance with an embodiment of the present invention; 
         FIG. 4  is a schematic representation of a hand extracted from a depth map, in accordance with an embodiment of the present invention; 
         FIG. 5  is a schematic representation of an image of a pattern of spots that is projected onto an area of a scene containing the hand of  FIG. 4 , in accordance with an embodiment of the present invention; 
         FIGS. 6-9  are schematic representations of the pattern of spots of  FIG. 5 , showing successive stages in processing of the pattern to extract a contour of the hand, in accordance with an embodiment of the present invention; 
         FIG. 10  is a schematic representation of a Delaunay graph having the spots of  FIG. 9  as vertices, in accordance with an embodiment of the present invention; 
         FIG. 11  is a schematic representation of the graph of  FIG. 10  showing a contour of a hand that is extracted from the graph, in accordance with an embodiment of the present invention; and 
         FIG. 12  is a schematic illustration of an image of the hand formed by the contour of  FIG. 11 , in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS 
     Overview 
     Practical depth mapping systems that are known in the art, particularly compact, low-cost systems that are used in mass-market applications, generally have low spatial resolution. For example, in systems that extract depth coordinates by processing an image of a pattern of spots that is projected onto a scene, the resolution is determined generally by the size of and spacing between the spots, which are typically several times greater than the pixel size in the image. Typically, for robust, artifact-free depth mapping, the resolution can be no better than three or four times the spot spacing. As a result fine features of the scene that would be visible in a conventional gray scale or color image cannot be distinguished in the depth map. 
     As a result of these limitations, when a humanoid form is extracted from a depth map (using the techniques described in the above-mentioned WO 2007/132451 or US 2011/0052006, for example), the locations and postures of the arms and hands can generally be detected, but not the individual fingers. When the depth map is used as part of a 3D user interface, such as a gesture-based interface for a computer or entertainment console, the interface will respond only to gross gestures of the arms, hands and body. It would be desirable to enable such systems to detect and respond to finger gestures at the same time, but without adding substantially to the hardware complexity and cost of the system. 
     Embodiments of the present invention address use novel image processing techniques to enhance the resolution of depth mapping systems that operate by projecting and capturing an image of a spot pattern, so as to enable fine features to be extracted from a scene. These techniques take advantage of heuristic knowledge of the features that are to be extracted, and are specifically adapted to resolve features having a set of elongate appendages, such as the fingers of a hand. The disclosed techniques start by finding the 3D location of the feature of interest (such as the hand) in the depth map, and then systematically connect the spots appearing on the feature in order to extract separate, respective contours of the appendages (such as the fingers). These embodiments may be used, for example, to find the posture of the hand and fingers, and thus to detect gestures of the hand in order to control an application running on a computer. 
     The disclosed embodiments are capable of extracting these fine contours even when the respective transverse dimensions of the appendages (such as the widths of the fingers) are on the order of the average distance between the spots in the pattern that is projected onto the feature, i.e., when these transverse dimensions are less than twice the average distance, or even less than the actual average distance, between the spots. Typically, the contour of any one of the appendages can be found even when no more than a single chain of the spots is connected along the length of the appendage. In other words, the resolution of the contours found in these embodiments is considerably finer than the inherent resolution of the spot pattern itself. 
     System Description 
       FIG. 1  is a schematic, pictorial illustration of a 3D user interface system  20 , in accordance with an embodiment of the present invention. The user interface is based on a 3D imaging assembly  22 , which captures 3D scene information that includes at least a part of the body of a human user  28 . The user in this example scenario is seated in a chair  30 . Assembly  22  may also capture 2D color video images of the scene. Details of a 3D imaging assembly of this sort are described, for example, in the above-mentioned PCT International Publication WO 2010/004542. 
     Assembly  22  outputs a sequence of frames containing 3D map data (and possibly color image data, as well) to a computer  24 , which extracts high-level information from the map data. This high-level information is provided via an Application Program Interface (API) to an application running on computer  24 , which drives a display screen  26  accordingly. For example, user  28  may select and interact with content appearing on screen  26  by moving his arms and hands  32 . 
     In one embodiment, assembly  22  projects a pattern of spots onto the scene and captures an image of the projected pattern. Assembly  22  or computer  24  then computes the 3D coordinates of points in the scene (including points on the surface of the user&#39;s body) by triangulation, based on transverse shifts of the spots in the pattern. This approach is advantageous in that it does not require the user to hold or wear any sort of beacon, sensor, or other marker. It gives the depth coordinates of points in the scene relative to a predetermined reference plane, at a certain distance from assembly  22 . Methods and devices for this sort of triangulation-based 3D mapping using a projected pattern are described, for example, in the above-mentioned PCT International Publications WO 2007/043036, WO 2007/105205, WO 2008/120217 and WO 2010/004542. 
     Alternatively, system  20  may use other methods of 3D mapping that use projected spot patterns (which may be uncorrelated or possibly more regular grid-based patterns), such as stereoscopic imaging or time-of-flight measurements, based on single or multiple cameras or other types of sensors, as are known in the art. 
     In the embodiment shown in  FIG. 1 , system  20  captures and processes a temporal sequence of depth maps (also referred to as 3D maps) containing user  28 . The user typically moves his body during this process. Software running on a digital processor in assembly  22  and/or computer  24  processes the 3D map data to extract geometrical features of the humanoid form corresponding to user  28 . The software analyzes these geometrical features (as described in detail hereinbelow) in order to extract at least the upper-body pose of the user, which typically includes 3D locations and orientations of the user&#39;s shoulders, arm joints, hands and head. For this purpose, the software may, for example, apply techniques described in the above-mentioned U.S. Patent Application Publication 2011/0052006, as well as in U.S. patent application Ser. No. 13/461,802, filed May 2, 2013, whose disclosure is incorporated herein by reference. 
     After locating hand  32  of user  28  in the depth map, the software performs further processing to find the pose of the fingers of the hand, using the techniques that are described below. It may also analyze the trajectories of the hand and fingers over multiple frames in the sequence in order to identify gestures made by the user. The pose and gesture information are provided via the above-mentioned API to an application program running on computer  24 . This program may, for example, move and modify images presented on display  26  in response to the pose and/or gesture information regarding the user hand (or hands) and fingers, as well as the arms and possibly the entire 3D skeleton. 
     Computer  24  typically comprises a general-purpose digital processor, which is programmed in software to carry out the functions described hereinbelow. The software may be downloaded to the processor in electronic form, over a network, for example, or it may, alternatively or additionally, be stored on tangible, non-transitory media, such as optical, magnetic, or electronic memory media. Further alternatively or additionally, at least some of the described functions of the computer may be implemented in dedicated hardware, such as a custom or semi-custom integrated circuit or a programmable gate array or digital signal processor (DSP). Although computer  24  is shown in  FIG. 1 , by way of example, as a separate unit from imaging assembly  22 , some or all of the processing functions of the computer may be performed by a suitable microprocessor and software or by dedicated circuitry within the housing of the imaging assembly or otherwise associated with the imaging assembly. 
     As another alternative, at least some of these processing functions may be carried out by a suitable digital processor that is integrated with display screen (in a television set, for example) or with any other suitable sort of computerized device, such as a game console or media player. The sensing functions of assembly  22  may likewise be integrated into the computer or other computerized apparatus that is to be controlled by the sensor output. References in the description and the claims to a “processor” should thus be understood as referring to any and all processing configurations that may be used in implementing the methods described herein. 
       FIG. 2  is a schematic representation of a depth map captured by assembly  22 , in accordance with an embodiment of the present invention. The depth map, as explained above, comprises a matrix of pixels having respective depth values. The depth values are represented in  FIG. 2  as gray-scale values, with lighter shades of gray corresponding to smaller depth values, i.e., locations closer to assembly  22 . (Black areas correspond to pixels for which no depth values could be determined.) In this particular scene, the depth values of user  28  blend into those of chair  30  on which the user is sitting. 
     Computer  24  processes this depth map, using the methods described in the above-mentioned U.S. patent application Ser. No. 13/461,802, for example, in order to segment and extract an upper body skeleton  36  of user  28 . The skeleton is represented in  FIG. 2  by a set of line segments connecting joints that correspond to the head, shoulders and one (or both) of the user&#39;s arms. The right arm represented in the figure culminates in the 3D location of hand  32 , which is typically indicated by the joint locations and angles and the segment lengths of the extracted skeleton. Additionally or alternatively, the hand location may be found by tracking movements of the arm and hand over multiple successive depth frames captured by assembly  22 . The 3D hand location is used in finding the contours of the user&#39;s fingers, as described below. 
     Methods for Extracting Finger Contours and Posture 
       FIG. 3  is a flow chart that schematically illustrates a method for finding a contour of a hand and fingers in a depth map, in accordance with an embodiment of the present invention. For clarity and convenience, the method will be described here with reference to the components of system  20  and user  28 , as illustrated in  FIGS. 1 and 2 . Alternatively, as noted earlier, the method of  FIG. 3  may be applied in other sorts of depth mapping systems that use a projected pattern of spots in creating a depth map. The principles of this method may be applied not only in finding finger poses, as described below, but also in extracting the contours of other sorts of elongate appendages that might otherwise be beyond the 3D mapping resolution of the system in question. 
     The method of  FIG. 3  begins with acquisition of an image of the spot pattern that is projected onto the scene containing user  28 , at an image input step  40 . It will be assumed that the image is a gray-scale image, although color images may also be processed in similar fashion. Assembly  22  and/or computer  24  processes this image in order to compute a depth map of the scene, at a depth map generation step  50 . Computer  24  then segments and processes the depth map in order to find the location of hand  32 , at a segmentation step  60 . Steps  40 ,  50  and may be performed using any suitable techniques that are known in the art, such as the techniques that are described in the patent applications described above. 
       FIG. 4  is a schematic representation of a contour  62  of hand  32  that is extracted from a depth map at step  60 , in accordance with an embodiment of the present invention. Once computer  24  has located the hand, it defines a bounding box  64  that contains the hand for further processing in order to find the contours of the fingers. These finger contours are much finer than the resolution of the depth map at this stage. 
       FIG. 5  is a schematic representation of an image of the pattern of spots  66  within bounding box  64 , in accordance with an embodiment of the present invention. The figure shows the part of the gray-scale image within the bounding box that is captured by assembly  22 . For convenience of representation, the gray scale in this and subsequent figures is reversed, i.e., dark areas in the figure corresponding to bright spots, while white areas of the figure corresponding to dark areas of the actual image. 
     Spots  66  appear in the image both on the hand (which can be seen as a faint gray area in the image) and in the background area that is behind the hand in the actual scene. The widths of the fingers are on the order of the average distance between adjacent spots (which is equal to the inverse root of the density of spots per unit area in the projected pattern) and are considerably less than twice this average distance. There are no spots in the image of areas  68  of the background that fall within the shadow of the hand, and thus appear simply as dark areas in the image. 
     To find the finger contours using the depth and gray scale information illustrated in  FIGS. 4 and 5 , computer begins by finding the locations of spots  66  within bounding box  64 , at a spot finding step  70  ( FIG. 3 ). For this purpose, the computer may, for example, smooth the gray-scale image illustrated in  FIG. 5  and then differentiate to find local brightness maxima corresponding to spots  66 . 
       FIG. 6  is a schematic representation of the area of the image within bounding box  64  after marking of local brightness maxima  72  at step  70 , in accordance with an embodiment of the present invention. The result at this stage is a binary map, in which local maxima have been marked without regard to whether they belong to hand  32  or to the background behind it. The outline of the hand is shown as a dotted line in this and subsequent figures as an aid to understanding, but the actual contour of the hand is not computed or otherwise known to computer  24  until the steps in the method of  FIG. 3  have been completed. 
     Computer  24  uses the distribution of maxima  72  in  FIG. 6  in order to identify and fill in shadow areas  68  of the image of  FIG. 5 , at a dark area processing step  80  ( FIG. 3 ). For this purpose, for example, computer may use morphological image processing techniques: Brightness maxima  72  are gradually dilated to fill in the illuminated areas of the hand and background, and at the same time, the darkest pixels in the image, which typically fall within shadow areas  68 , are dilated to fill in the shadow areas. This process continues until all pixels in the image have been assigned to either a bright or a dark area. The bright areas already contain maxima  72 , corresponding to the locations of spots  66  in the projected pattern. 
     Computer  24  chooses and marks points at certain of the darkest pixels within the dark areas, as well, with a density that is approximately equal to the spot density. To ensure that the spaces between fingers appear clearly, the computer may use heuristic knowledge of the shape of the hand to identify these spaces and mark a sufficient number of points in the spaces. For example, the computer may draw radii extending from the wrist joint location provided at step  60 , and may then identify radii passing through brightness maxima as fingers and other, neighboring radii passing through brightness minima as the spaces between the fingers. 
       FIG. 7  is a schematic representation of the area of the image within bounding box  64  in which dark points  82  have been added at step  80 , along with local brightness maxima  72  found at step  70 , in accordance with an embodiment of the present invention. 
     For each brightness maximum  72  within bounding box  64 , computer  24  finds a respective depth value, at a depth identification step  90  ( FIG. 3 ). The depth values are determined at the depth resolution of the original depth map that was computed at step  50 , at least as an initial estimate. Subsequently, using the techniques described below, the transverse dimensions of the hand (i.e., the dimensions within the plane of the image shown in  FIG. 5 ), and possibly the depth dimensions, as well, are extracted with much finer resolution than the original depth map. 
     Step  90  can be simplified by assuming that only two depth values are possible within the bounding box: the depth that was computed for hand  32  (corresponding to contour  62  in  FIG. 4 ) or the depth that was computed for the background area behind the hand. These representative depth values may be calculated, for example, as the respective centers-of-mass of the hand pixels and of the background pixels. Computer  24  thus sorts spots  66  as belonging either to the hand depth or the background depth. 
     One way to find the depth values at step  90  is by a simplified cross-correlation computation. In preparation for this computation, computer  24  prepares two reference images of the projected spot pattern, one with a transverse shift corresponding to the depth value of the hand and the other with a transverse shift corresponding to the depth value of the background. (The transverse shift varies with depth due to parallax between the pattern projector and image capture device in assembly  22 , as explained in the above-mentioned PCT publications.) Computer  24  then computes the cross-correlation value between a group of pixels in the gray-scale image of the projected spot pattern ( FIG. 5 ) at the location of each brightness maximum  72  and corresponding groups of pixels in each of the two reference images at the same location. Since there are only two possible depth values, it is sufficient to compute the cross-correlation at this step over only a small matrix of pixels (for example, a 3×3 matrix) at each location, and the computation can therefore be completed quickly and easily. Each brightness maximum  72  is thus assigned a depth value corresponding to the reference image—either hand depth or background depth—that gave the higher correlation value for the location of the given brightness maximum. 
     In an alternative embodiment, computer  24  may find the depth values at step  90  with finer resolution than the original depth map. For this purpose, multiple “stable” depth values may be identified initially within the bounding box, for both the hand and the background. A “stable” value may be defined, for example, as a depth value that is consistent over a number of neighboring locations, and these locations are defined as “stable” locations. Different parts of the hand may have different stable depths, and similarly different parts of the background may have different stable depths, particularly when the background is not simply a uniform plane. The depth value at each point is then found precisely, by cross-correlation computation, for example, using the stable depth value at the nearest stable location as a starting point. 
     In this manner, the computer is able to calculate depth values with resolution finer than the depth increment corresponding to a transverse shift equal to the average distance between the spots in the projected pattern. Furthermore, stable depth values and locations may be used to extract hand postures (and other 3D shapes) from a depth map even without prior segmentation and identification of the arm humanoid form to which the hand belongs. 
       FIG. 8  is a schematic representation of the area of the image within bounding box  64 , in which the local brightness maxima have been respectively identified as hand points  92  or background points  94  in accordance with an embodiment of the present invention. Dark points  82  remain unassigned at this stage. Although most of the brightness maxima are correctly assigned in  FIG. 8 , some artifacts may still remain, such as outlier locations  98  at which the correlation computation of step  90  gave an incorrect value. 
     Computer  24  corrects possible artifacts in the map of  FIG. 8 , at a global optimization step  100  ( FIG. 3 ). At this step, the computer typically identifies outlier locations  98  and changes their respective depth values to the “correct” value at each point. The computer then assigns dark points  82  to be part of the background, i.e., it arbitrarily (but correctly, from a heuristic perspective) assigns the depth value of the background to these dark points. 
     To correct artifacts due to outliers at step  100 , for example, the computer may construct connected components of background points  94  and may then identify presumed hand points, such as location  98 , that cut these connected components. By the same token, the computer may identify presumed background points that cut connected components of hand points  92 . For each such cutting point, the computer may compute a score based, for example, on the geometrical isolation of this point from other points of the presumably same depth, as well as on the correlation values for the cutting point and its neighboring points that were computed at step  90 . The computer may then change the depth value of cutting points whose (high) score indicates that their depth values are probably erroneous. To construct the connected components and identify cutting points, the computer may construct and use a graph over points  92  and  94 , such as the sort of graph that is described below at step  110 . 
       FIG. 9  is a schematic representation of the map of  FIG. 8 , following artifact removal and processing of shadow areas at step  100 , in accordance with an embodiment of the present invention. Obvious outliers have been removed, and dark points  82  have been converted to background points  94 , as described above. 
     To extract the hand contour from the map of  FIG. 9 , computer  24  constructs a graph having points  92  and  94  as vertices, at a graph construction step  110  ( FIG. 3 ). A triangular Delaunay graph may be used for this purpose. (If such a graph was created previously for the connected component analysis at step  100 , the same graph may be reused at step  110 .) A Delaunay graph over a set of points P in a plane is a triangulation DT(P) such that no point in P falls inside the circumscribed circle of any triangle in DT(P). Various algorithms are known in the art for constructing a Delaunay graph, and any suitable algorithm may be used for this purpose at step  110 . 
       FIG. 10  is a schematic representation of a Delaunay graph  112  having the spots of  FIG. 9  as vertices  114 , in accordance with an embodiment of the present invention. 
     Computer  24  extracts the contour of hand  32 , and specifically of the fingers of the hand, from graph  112 , at a contour extraction step  120  ( FIG. 3 ). For this purpose, the computer may find cut-edges of the graph, i.e., edges that connect a hand point  92  to a background point  94 . These cut-edges are presumed to cross the contour of the hand or fingers. The computer thus concludes that the contour passes through the cut-edges and draws the contour by choosing a point on each cut-edge, sorting the edges, and then connecting the neighboring points. 
       FIG. 11  is a schematic representation of graph  112 , showing extraction of a contour  122  of hand  32  from the graph, in accordance with an embodiment of the present invention. Cut-edges  124  each connect one vertex  114  corresponding to a hand point  92  to another vertex corresponding to a background point  94 . These cut-edges  124  are shown in the figure as dashed lines, through which contour  122  runs. In the example shown in  FIG. 11 , only a single chain of vertices  114  (corresponding to a single chain of spots  66  in the original image of  FIG. 5 ) is connected along the length of each of the fingers. In other words, the resolution of contour  122  is actually finer than the resolution of the spot pattern on which the depth map is based. 
     It is possible simply to draw contour  122  through the centers of the successive cut edges and to derive a reasonable approximation of the hand and finger posture in this manner. Alternatively, for greater accuracy, graph  112  may be overlaid on the original gray-scale image (as in  FIG. 5 ) from which the graph was derived, and the location of the contour at each cut-edge may be extracted using features of the gray-scale image. For example, the gray-scale image may be differentiated to find image edges that pass through the cut-edges of the graph, and contour  122  may be drawn along these image edges; or the contour may be considered to cross each cut-edge at the point along the cut-edge at which the gray-scale value of the image passes a given threshold. Alternatively or additionally, if a color image is registered with the depth map, information from the color image may be used in drawing contour  122 . 
     Alternatively or additionally, the contour may be found accurately by identifying the fingertips and the bases of the fingers, and then drawing the contour between them based on the assumption of smoothness. The computer may find the fingertips and bases by extending radii from the wrist, as explained above: The fingertips will be the bright points farthest from the wrist along respective radii, while the finger bases will be the dark points nearest to the wrist along intervening radii. Based on these points and the assumption of smoothness, the computer stretches the contour to find the shortest path that passes through the contour edges. Gradient descent methods may be applied, for example, in finding the optimal contour. Using this method, the computer can achieve a resolution that is even finer than the resolution of the image of the projected pattern itself. 
       FIG. 12  is a schematic illustration of an image  126  of hand  32  that is formed by the contour of  FIG. 11 , in accordance with an embodiment of the present invention. Despite minor artifacts remaining in the image, the contours and posture of the fingers are clearly delineated. 
     Although the functions performed by computer  24  at some steps in the method of  FIG. 3  are described above, for the sake of clarity and completeness, in terms of certain specific algorithms, other algorithms that are known in the art of image processing may be applied to similar effect in order to carry out the steps of the method, and such alternative implementations are considered to be within the scope of the present invention. It will thus be appreciated that the embodiments described above are cited by way of example, and that the present invention is not limited to what has been particularly shown and described hereinabove. Rather, the scope of the present invention includes both combinations and subcombinations of the various features described hereinabove, as well as variations and modifications thereof which would occur to persons skilled in the art upon reading the foregoing description and which are not disclosed in the prior art.

Metadata:
Filing Date: 20150318
Publication Date: 20171205
Grant Date: 20171205
Priority Date: 20121030
Inventors: GURMAN AMIAD
Assignee: APPLE INC
CPC Classifications: [{"code": "G06V40/113", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06V40/11", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06V10/426", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/00382", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/00389", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06K9/48", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/12", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/00375", "inventive": true, "first": false, "tree": "[]"}, {"code": "G01B11/254", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06K9/469", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/521", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/017", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/162", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T15/30", "inventive": false, "first": false, "tree": "[]"}, {"code": "G06T7/593", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/73", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/0203", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/194", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06V40/11", "inventive": true, "first": true, "tree": "[]"}, {"code": "G06V40/107", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06V10/426", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/162", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/521", "inventive": true, "first": false, "tree": "[]"}, {"code": "H04N13/204", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/593", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/12", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/194", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/73", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T15/30", "inventive": false, "first": false, "tree": "[]"}, {"code": "H04N13/204", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/194", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/162", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/12", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/593", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/521", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06T7/73", "inventive": true, "first": false, "tree": "[]"}, {"code": "G01B11/254", "inventive": true, "first": false, "tree": "[]"}, {"code": "G06F3/017", "inventive": true, "first": false, "tree": "[]"}]
Family ID: 50546659