Visual tracking using depth data

RELATED APPLICATIONS

This application is a divisional application under 35 U.S.C. §121 of, and claims priority under 35 U.S.C. §120 from, co-pending U.S. patent application Ser. No. 10/857,581 entitled “Visual Tracking Using Depth Data,” filed on May 28, 2004, which claims priority under 35 U.S.C. § 119(e) from, U.S. Provisional Patent Application Ser. No. 60/474,795, titled “Head Tracking Using Depth Data,” filed on May 29, 2003, and from Ser. No. 60/497,026, titled “Illumination Invariant Driver Monitoring: Head Tracking, Head Pose, and Body Lean Estimation,” filed on Aug. 20, 2003, which are incorporated by reference herein in their entirety.

FIELD OF THE INVENTION

The present invention relates generally to real-time computer vision and more particularly to computer based visual tracking of moving targets.

BACKGROUND OF THE INVENTION

Tracking is a key component for many areas of real-time computer vision such as Human-Computer Interaction (“HCI”). One example of an HCI application is driver monitoring. In this area, work has been done to determine head pose and body lean using various techniques. This information can be used for example to assist an air-bag deployment system, or for attention and fatigue monitoring in a safety system. Tracking spatial location of the driver's head or other body parts facilitates the operation of these and other HCI systems.

Conventional tracking systems are typically based on two-dimensional (2D) gray or color images. There are situations in which methods using templates or probabilistic frameworks do not function very robustly. Conventional tracking algorithms often fail when the environment is cluttered. The algorithms fail because the hypothesis being examined often cannot distinguish the real target. Distractions by edges caused by non-target environmental objects are major contributors to this problem even though the target object may have distinct depth difference compared to its surroundings (e.g., background). For example, this effect is common in many important tracking applications including head tracking, human tracking, and hand gesture recognition. Accordingly, using conventional systems, distinguishing a target object in the foreground from other objects in the background is not a trivial task.

This problem common to conventional tracking methods is basically that the target tends to get lost when the environment has a cluttered background. A similar problem arises when changing lighting conditions distract contours or patterns that tracking algorithms are based on. There have been many different approaches to solving the tracking problems. Some conventional systems use contour information, while others use depth from stereo imaging systems, intensity and color distribution, or a combination of these features.

Some systems have attempted to use depth characteristics of the target to aid in the tracking functions. For example, stereo (dual camera) systems are used to track heads with a model-fitting approach. Some of these systems use stereoscopic images, but still rely on other intensity-based information, or if using stereoscopic images only, it is used with a computationally intensive algorithm.

Thus, there is a need for tracking methods and systems that are based on (1) real-time image data, (2) using algorithms that are not computationally intensive, and (3) using simple single-camera systems.

SUMMARY OF THE INVENTION

A computer-based method for real-time tracking of a target using a depth-sensing camera is described. The method involves the reception of depth information in a real-time video image stream. The video depth information includes an image of the target to be tracked. Based on the depth information, the edge of the target's periphery in the depth image is found. Then, a mathematically representable contour that models the target's shape is fit at different locations in the image to find the best fit with respect to target's edge. The contour and its location within the image provide the tracking of the target.

A human-computer interaction system based on these principles of operation can visually track human movement as computer control input. The system includes an active depth sensor for capturing depth images of the human. A processing unit receives the depth images and derives the control input information. To do this, the processing unit includes an edge detection module that is configured to determine, from the image data, which pixels correspond to the edge of the human to be tracked. Then, a tracking module using a contour that models the human (or human body part) to be tracked determines how to best fit the contour with respect to the edge in the image. Based on the best fit, a position of the target within the captured depth images is provided. This position information can be then used to, for example, use other machine vision techniques to recognize hand signs, arm motions, or the like, corresponding to computer commands.

Further, the human-computer interaction system can also include a body-lean determination module to receive the position information and to calculate an average distance of one or more body parts with respect to the active sensor. Then, by relating the average distance of each body part with respect to other body parts the module determines body-lean information. The body-lean information can be used, for example, in a vehicle control unit to control air-bag deployment.

In one embodiment, a motor vehicle is configured to track occupant body-lean information for multiple purposes. The motor vehicle is equipped with an active depth sensor for capturing depth images of the occupants. A processing unit with an edge detection module and a tracking module similar to the modules described above can provide tracking data to other control logic in the motor vehicle. The tracking data can be used for driver assist technology, air-bag deployment, or the like.

The features and advantages described in the specification are not all inclusive and, in particular, many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification, and claims. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1A</figref> shows depth images of a driver with different positions for the upper torso.

<figref idref="DRAWINGS">FIG. 1B</figref> shows output images of one embodiment of a tracker in which the right hand of a person is the tracked target.

<figref idref="DRAWINGS">FIG. 2</figref> shows one embodiment of a sample tracking system using a depth-sensing camera.

<figref idref="DRAWINGS">FIG. 3</figref> shows a depth image with a corresponding sample edge potential transform map.

<figref idref="DRAWINGS">FIG. 4A</figref> shows a visual representation of a profile defined by a set of potential values.

<figref idref="DRAWINGS">FIG. 4B</figref> shows a visual representation of a profile defined by a set of potential values corresponding to an elliptic head tracking embodiment.

<figref idref="DRAWINGS">FIG. 5</figref> shows a simple scene that contains just two regions (upper far area and lower near area) and a set of alternative tracking outputs.

<figref idref="DRAWINGS">FIG. 6</figref> shows one embodiment of a tracking method.

<figref idref="DRAWINGS">FIG. 7</figref> shows one embodiment of a potential field determination process.

<figref idref="DRAWINGS">FIG. 8</figref> shows one embodiment of a contour fitting process.

<figref idref="DRAWINGS">FIG. 9</figref> shows a frame of a complete occlusion state of a target hand being tracked.

<figref idref="DRAWINGS">FIG. 10</figref> shows one embodiment of a body-lean estimation method.

DETAILED DESCRIPTION OF THE INVENTION

The Figures and the following description relate to preferred embodiments of the present invention by way of illustration only. It should be noted that from the following discussion, alternative embodiments of the structures and methods disclosed herein will be readily recognized as viable alternatives that may be employed without departing from the principles of the claimed invention.

Referring now to Figure (“FIG.”) <b>1</b>A, depth images of a driver with different positions for the upper torso are shown with the output of an elliptic tracking system. A depth image is visually represented with variations in the pixel intensity based on the depth value, that is, the objects closer to the camera appear brighter and progressively darker until the background outside a depth window is shown as black. A depth sensor can be set to capture or sense depth information for objects within a specified depth range or depth window. When this is done in real-time and a stream of depth images or frames are produced, the depth sensor functions as a motion picture camera, e.g., video, film, digital video, or the like, but it outputs hybrid image data. The hybrid image data includes depth data for each pixel; for example, data for a hybrid or depth image generally includes pixel coordinates, color values, depth value and other conventional image data. One benefit of using a depth-sensing camera is the ability to set a depth window by controlling shutter speed. For example, <figref idref="DRAWINGS">FIG. 1B</figref> shows output images of one embodiment of a tracker in which the right hand of a person is the tracked target. As shown in the images, target right hand <b>101</b> is tracked while body <b>102</b> and head <b>103</b> of the person are at the edge of the depth window leaving anything behind it outside to avoid cluttering the depth information with non-tracked objects. As another example, in a driver's pose tracking application (for example as shown in <figref idref="DRAWINGS">FIG. 1A</figref>), the camera can be set to a depth window that ranges from the steering wheel area (Dmin) to the headrest of the driver seat <b>110</b> (Dmax) thereby avoiding cluttering the depth information with, for example, depth data from back-seat passenger movement.

<figref idref="DRAWINGS">FIG. 2</figref> shows a sample tracking system using a depth-sensing camera. Depth-sensing cameras <b>202</b> operate according to the time-of-flight principle, hence the name: time-of-flight cameras. One embodiment of a tracking system <b>200</b> includes one time-of-flight camera <b>202</b>, such as, for example, a camera manufactured by 3DV Systems, of Yokneam, Israel, or Canesta, Inc., of San Jose, Calif. The time-of-flight camera <b>202</b> is set to a depth window <b>204</b> that includes the area from Dmin to Dmax in which the target <b>206</b> being tracked will move about. One benefit of this approach is that non-target objects <b>208</b>, e.g., background objects, do not produce depth image information. The depth-sensing camera <b>202</b> is connected to the tracking computer <b>210</b>. In one embodiment, the tracking computer <b>210</b> includes an image processing library, such as for example, Intel's image processing library, from Intel Corporation of Santa Clara, Calif., and runs at 14 frames per second (320×240 pixels) on a 1.2 GHz Pentium III processor by Intel Corporation. In another embodiment, the depth-sensing camera <b>202</b> is part of a robotic vision unit and the tracking computer is a module within the control logic in a robot, for example, the ASIMO humanoid robot by Honda Motor Co., Ltd, of Tokyo, Japan. Yet another embodiment includes a small time-of-flight camera <b>202</b> in a vehicle cabin connected to a tracking module <b>210</b> in a data processing control unit within the vehicle, for example, for controlling air-bag deployment.

The depth cameras <b>202</b> based on the time-of-flight principle can capture depth and color information simultaneously using the same optical axis in real-time. Moreover, time-of-flight cameras provide the advantageous feature of setting a depth window <b>204</b> that corresponds to a range of operation (Dmin, Dmax) for which depth information is to be recorded. This unique feature eliminates background clutter by setting Dmax immediately behind the subject or target <b>206</b> being imaged, in effect, removing objects beyond certain depth from the image acquired.

The image capturing method is based on active sensing with a time-of-flight camera <b>202</b>, where a pulse of infrared illumination is projected to the target <b>206</b> and the sensor reads its echo signal reflected from the target <b>206</b>. Furthermore, the device has a high-speed shutter by which it controls the sensing scope for targets whose signal can enter the sensor, i.e., the depth window <b>204</b>. For a far object <b>208</b>, the echo reaches the device only after the shutter has been closed. Thus, no signal is recorded for the corresponding object, i.e., most background objects <b>208</b> do not appear in the recorded scene.

Compared to stereoscopic systems, a depth-sensing tracking system <b>200</b> includes several improved characteristics. For example, the image is illumination-invariant in in-door environments, as long as the environment does not contain light of the same wavelength used for the pulse of the sensor. The performance over any given range is improved over the stereoscopic system; any error in depth is approximately 5˜15 mm for 0.5˜3 m depth window <b>204</b>. Depth information can be recorded in real time in a separate corresponding depth image (e.g., 8 additional bits for each pixel). This definition provides sufficient separation between image elements, such as, for example hand and rest of the body in a system <b>200</b> used for gesture recognition. In addition, both depth and color information are captured at real-time speed (e.g., 30 frames/sec), in effect producing a depth and a color image of the same scene. The depth sensing performance for objects with no texture (such as walls) is much better than stereoscopic systems that cannot differentiate between the images of each camera. All these improved features and other features are provided with a single camera tracking system <b>200</b> as opposed to a multi-camera stereoscopic system. The single camera system <b>200</b> also provides the additional benefit of obviating the need for calibration between the two or more cameras of a conventional stereoscopic multi-camera system.

Potential Fields

Now referring to <figref idref="DRAWINGS">FIG. 3</figref>, a depth image with a corresponding sample edge potential transform map is shown. The transform map <b>300</b> includes the target <b>206</b> to be tracked modeled as an attractor in a potential field. Each point <b>302</b> outside of the target's edge is associated with a value indicating how far the point is from the target's edge <b>301</b>, which is given a reference value (e.g., “0” potential). Since the exact position of the attractor is not known, i.e., this is what is being tracked, an approximate potential field is generated by using image edges. There are several variations for potential functions that define the shape of the “landscape” (represented as the potential field). In one embodiment, a distance transform is used to provide a fast computation. Specifically, distance D between a point p and a set of points Y is defined as the Manhattan distance between p and the point in Y that is closest to p (i.e., the point in the outline of the target's edge <b>301</b> that is closest to the outside point <b>302</b> for which the distance D is calculated):

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><mi>D</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>p</mi><mo>,</mo><mi>Y</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>y</mi><mo>∈</mo><mi>Y</mi></mrow></munder><mo>⁢</mo><mrow><mo></mo><mrow><mi>p</mi><mo>-</mo><mi>Y</mi></mrow><mo></mo></mrow></mrow></mrow></math></maths><img file="US7590262B2_D0001.tif" />

With this metric, a potential field can be determined where each point <b>301</b> in the target's edge has a reference value, for example, a value of “0” potential, and every point <b>302</b> outside the target's edge has a D value, for example, corresponding to its Manhattan distance to the closest edge point <b>301</b> as shown in <figref idref="DRAWINGS">FIG. 3</figref>. A visual representation of a profile defined by a set of potential values is shown in <figref idref="DRAWINGS">FIG. 4A</figref>.

<figref idref="DRAWINGS">FIG. 4A</figref> shows a profile or “landscape” <b>400</b> of the potential field corresponding to the depth image of the target. The lowest points or valleys <b>402</b> correspond to the edge points <b>301</b> of the target in the corresponding depth image. The other points in the profile are graphical representations of the potential values (e.g., D) for the neighboring points in the depth image. Thus, for example, the representation of the target's head <b>404</b> can be detected and differentiated from the target's body <b>406</b> as the “hill” <b>404</b> completely surrounded by “valleys.” Concentric equidistant lines of points can be defined reaching a local maxima at the top of the “hill” corresponding to the points <b>302</b> furthest away from the edge points <b>301</b>. In the opposite direction, points <b>302</b> generally increase in a gradual slope <b>402</b> towards the image edges. The “valleys” <b>402</b> are formed by the edge points <b>301</b> and make up the lowest potential zone <b>408</b> that can be fit with a mathematically representable contour <b>410</b>, in this sample embodiment an ellipse. An analysis of the image data as further detailed below can yield the coordinates of the image (search area S) likely to include the target. Thus, for example, in <figref idref="DRAWINGS">FIG. 4A</figref>, if a person's head, as opposed to the body, is to be tracked (i.e., the head is the target), the search area S would not include the right side of the profile <b>400</b>. Thus, by using the general search area S restriction, only the low potential zone <b>408</b><i>a </i>would meet this restriction and the low potential zone <b>408</b><i>b </i>corresponding to the body can be ignored.

As with the potential field calculation, a measure of the proximity between the outline <b>410</b> and the low potential zone <b>408</b><i>a </i>can be given by a distance metric. For example, if the points of the mathematically representable contour <b>410</b> (X) are taken as a whole to be compared with the set of points <b>301</b> (Y) that make up the target low potential zone <b>408</b><i>a</i>, in one embodiment, the distance between the two point sets X (e.g., contour <b>410</b>) and Y (e.g., target's edge <b>408</b><i>a</i>) is defined as what sometimes is referred to as Chamfer Distance: <br />dist(<i>X,Y</i>)=Σ_xεX(<i>x,Y</i>)/|<i>X|</i><br /> where the Manhattan distance D between each point x in set X to set Y is added over the set of points in X. This measure can be used for comparison between several “best guess” outline <b>410</b> locations or states to determine the best fit as described below.

An algorithm for tracking a target according to one embodiment includes the following metric: <br /><i>s</i>_t+1=arg min_sεS(dist(<i>s,I</i>_t+1))<br /> In this embodiment, s corresponds to a state of the contour <b>410</b>, while S is the search space for the contour s containing all possible states s can take in the neighborhood of s's current state. The symbol I is used to represent the edge map <b>400</b> corresponding to a particular depth image or frame. For the first frame the position of the target s is estimated and for subsequent frames, the final position from previous image s_tis used to determine a search area in the neighborhood of the s_tposition to find the next target state s at t+1, i.e., s_t+1.

For each candidate target state s, the overall fit of the contour <b>410</b> to the actual target edge <b>408</b><i>a </i>is assessed and the one that has the least overall match value (potential) is selected as the best fit. For example, the match value can be the sum of point distances dist( ) from the edge points <b>408</b><i>a </i>(Y) to the contour <b>410</b> (X). For the contour <b>410</b>, any of a number of mathematically representable shapes or curves can be used, such as for example, ellipses, rectangles, squares, ovals, free-form curves, or the like. In one embodiment, an ellipse is used due to the ease of change of its location and size using a fixed aspect ratio for its axis.

Elliptic Head Tracking

In one embodiment for head detection and tracking, the projection of a human head in 2D is modeled as a vertical ellipse with a fixed aspect ratio of 1.2. That is, an ellipse with major axis h and minor axis

<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mfrac><mi>h</mi><mn>1.2</mn></mfrac><mo>.</mo></mrow></math></maths><img file="US7590262B2_D0002.tif" /><br /> Thus, at any given moment, the state of the head (ellipse) s is represented by a triplet (x,y,h) where (x,y) is the position of the center of the head in the image coordinate system and h is the height of the major axis of the ellipse used to model the projection of the head in the image. In other embodiments, the tracked target can be modeled by any mathematically representable outline with a state s, for example, a center position and a radius, e.g., circle (x, y, c), a center position and a side length, i.e., square (x, y, l), or any other position and related mathematical relationship between a set of points (i.e., contour <b>410</b>). In this embodiment, head tracking is done by trying to optimize the ellipse measure as discussed bellow, in a search space S in the neighborhood of the predicted head state.

Now referring to <figref idref="DRAWINGS">FIG. 4B</figref>, an elliptic head tracking embodiment is shown. Given an ellipse <b>410</b> state s=(x,y,h) and a gradient image I <b>408</b> corresponding to a depth image D, the ellipse measure of s with respect to I gives a measure of an ellipse of size h, at position (x,y) in the image I. In one embodiment, a measure for this ellipse is the measure proposed by Nishihara et al. in “Real-time Tracking of People Using Stereo and Motion,” SPIE Proceedings, Vol. 2183 (1994), incorporated herein by reference in its entirety. Thus, the ellipse measure of state s is given by:

<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><mrow><mi>EM</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>s</mi><mo>,</mo><mi>I</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><msub><mi>N</mi><mi>h</mi></msub></mfrac><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><msub><mi>N</mi><mi>h</mi></msub></munderover><mo>⁢</mo><mrow><mo></mo><mrow><mrow><msub><mi>n</mi><mi>h</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow><mo>·</mo><mrow><mi>Is</mi><mo>⁡</mo><mrow><mo>(</mo><mi>i</mi><mo>)</mo></mrow></mrow></mrow><mo></mo></mrow></mrow></mrow></mrow></math></maths><img file="US7590262B2_D0003.tif" />

where Is(i) is the depth gradient, at the ith perimeter pixel of the ellipse in state s in the image I. N_his the number of pixels on the periphery of an ellipse of size h. n_h(i) is the unit vector, normal to the ellipse of size h at the same ith perimeter pixel as above and “.” denotes a dot product. This measure takes gradient direction and magnitude of depth discontinuity into account. As shown in <figref idref="DRAWINGS">FIG. 4B</figref> with respect to two points i and j, the measure EM is proportional to the depth gradient's magnitude and alignment with the ellipse's periphery as measured by the dot product. For example, when the ellipse state s coincides with the outline of the target head I (e.g., point j), at each such point of the ellipse periphery the unit vector n_h(j) has the same direction as the depth gradient vector Is(j) (i.e., cos 0°=1), thus, the EM measure is proportional to the magnitude of the depth gradient vector (i.e., n_h(j)·Is(j)=|n_h(j)∥Is(j)|cos 0°). In addition, the more perfectly matching points, i.e., the better the fit between the contour and the target's edge in the image, the greater the EM value since the magnitude of the gradient is the greatest at the target's edge due to the large variation in depth with respect to the background. Accordingly, the best fit amongst a set of possible states can be determined by comparing the resulting EM values are discussed below.

For tracking purposes, given the state s_t=(x_t, y_t, h_t) and s_t−1=(x_t−1, y_t−1, h_t−1), of the head at time t and t−1 respectively, the position of the head at time t+1 is predicted using a constant velocity assumption. The size of the head is predicted to stay the same. <br /><i>x′</i>_t+1<i>=x</i>_t+(<i>x</i>_t<i>−x</i>_t−1)<br /><i>y′</i>_t+1<i>=Y</i>_t+(<i>y</i>_t<i>−y</i>_t−1)<br /><i>s′</i>_t+1=(<i>x</i>_t+1<i>,y</i>_t+1<i>,h</i>)

This simple motion model greatly improves the performance of the tracker system by removing any restriction of the lateral velocity of the head. Although, the constant velocity model restricts the amount of acceleration, the robust input features and the large enough window of search compensate for that. For head size, it has been observed in practice that it changes very gradually and does not obey the constant change model. The search space S does take gradual and occasional variations of head size into account.

The ellipse measure EM is calculated for all states in the search space S, (where S contains all states within some range of the predicted state s′_t+1) with respect to the gradient image I at time t+1. The state corresponding to the maximum ellipse measure in this search is chosen as the state of the head in frame t+1. <br /><i>s</i>_t+1=max <i>EM</i>(<i>s,I</i>_t+1)<i>sεS</i>

In <figref idref="DRAWINGS">FIG. 4B</figref>, the contour <b>410</b> “falls” to the low potential valley <b>408</b> corresponding to the edge of the target <b>404</b> because the best fit (maximum EM) will correspond to the state in which the distance measure from the contour <b>410</b> to the edge <b>408</b> is minimized, that is, when the points of the contour <b>410</b> periphery coincide with the points of the target edge <b>408</b>.

In addition, in one embodiment, a confidence measure (CM) is calculated to prevent drifting, e.g., as a basis to stop the tracking system or initiate a detection module to provide a new estimated location of the target head. The confidence measure for a state s with respect to an image I is defined as:

<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><mrow><mi>CM</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>s</mi><mo>,</mo><mi>I</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mfrac><mrow><mrow><mi>EM</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mi>I</mi></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mi>min</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>EM</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow><mrow><mrow><mi>max</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>EM</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>-</mo><mrow><mi>min</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>EM</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>h</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mrow></mrow></mrow></mrow></mfrac></mrow></math></maths><img file="US7590262B2_D0004.tif" /><br /> where max EM(h_t+1) and min EM(h_t+1) are the maximum and minimum values of EM observed so far for an ellipse of size h_t+1. If the confidence measure goes below a predetermined threshold, appropriate action is taken (e.g., stop tracker, start detection module, or the like). <br /> Component Based Potential Field Tracking

An alternative embodiment, especially suitable for object tracking where depth information is used, implements a component based tracking method. As opposed to non-component based embodiments, the ‘sides’ of the target's edge are differentiated, namely, contour <b>410</b> is attracted to edge fragments of the target edge <b>408</b> depending on which side is higher (farther from the camera) or lower (closer to the camera). For an edge in a depth map, its orientation is defined in a natural way based on which side of the edge <b>480</b> contains higher values in depth; higher values in depth correspond to the outer side of the edge while lower values in depth correspond to the inner side, i.e., part of the target itself.

For example, contour <b>410</b> (e.g., a set of points X defining an ellipse, a rectangle, a square, a circle, or the like) is divided into k parts (e.g., a k-sided ellipse), where k is typically an even number, (e.g., 2, 4, 8, or the like). Each of the k parts is defined with an outer side (higher depth values) and an inner side (lower depth values) such that pixels within the same part are of similar orientation. Each part is matched against edge segments of the target's edge <b>408</b> only when their orientations match. That is, when the depth values to the outer side are larger than the depth values to the inner side of the edge segment. This way, the likelihood of correct a match is highly increased, particularly when there are many spurious edges in the neighborhood of the target.

The calculation dist ( ) is applied k times, one each for each orientation. For example, in one embodiment, Iⁱand sⁱrepresent the edge image corresponding to the i-th orientation and part of s with the i-th orientation, respectively. That is, the plurality of edge images Iⁱ(and parts sⁱ) are mutually disjoint (I=∪Iⁱ, and likewise s=∪sⁱ). Then, the tracking method according to this embodiment includes the following expression: <br /><i>s</i>_t+1=arg min_sεS(Σ_idist(<i>s</i>ⁱ<i>,I</i>ⁱ_t+1))

In addition, in one embodiment weights can be assigned to the k parts or components to represent the significance for the orientation for a particular target. For example, human tracking should have more weights on vertical sides than horizontal sides.

Now referring to <figref idref="DRAWINGS">FIG. 5</figref>, a simple scene that contains just two regions (upper far area and lower near area) is shown. Suppose that contour <b>510</b> at position (a), (shown as <b>510</b><i>a</i>) is the correct match for the tracked target <b>508</b>. The contour <b>510</b> at position (b) (shown as <b>510</b><i>b</i>), is a mismatch, but could be considered as a match in embodiments that do not distinguish edge orientation. Contour <b>510</b> at position (c) (shown as <b>510</b><i>c</i>), is also a mismatch, but it is considered as a local minimum whose evaluation for a search area S that estimates s_t+1to be in that general area is lower than at position (a). For the non-component-based embodiments, contours at positions (a) <b>510</b><i>a </i>and (b) <b>510</b><i>b </i>will get an approximately equal “match score.” However, according to the present embodiment, contour <b>510</b><i>b </i>will be discarded since it does not meet the proper orientation for each of the parts of the contour sⁱ. For example, giving higher weight values to match scores corresponding to parts of the contour that matched the target at the wrong orientation would make contour <b>510</b><i>a </i>at position (a) have the overall minimum match score out of the three contour positions shown.

Now referring to <figref idref="DRAWINGS">FIG. 6</figref>, one embodiment of a tracking method is shown. According to this embodiment, a video depth image stream is received <b>601</b> as input. A first frame of the stream is selected for processing <b>602</b>. For the first frame, the edges of the target to be tracked are determined <b>603</b>. Based on the determined edges the general search area for the target is determined <b>604</b>. Within the search area and based on a corresponding potential field, a contour is fit <b>605</b> over the target's edges. For example, six alternative states each with a corresponding elliptic fit are produced. From amongst these six states, the best fit is selected. Once the “best fit” or optimal match is determined between the contour and the target's edge, the tracking data is output <b>606</b> for example as an image coordinate value (x, y) and the associated modeling contour (e.g., h for an ellipse contour). The estimated next frame search area S is determined <b>607</b>. The search area S is chosen stochastically or deterministically in the neighborhood of the predicted target position in the next frame. The predicted position is based on a constant velocity assumption, for example, using a Kalman filter. Unless a termination command is provided <b>608</b>, the next frame is selected <b>609</b> and the fitting process is repeated. The search area determination <b>604</b> with subsequent frames involves matching the predicted search area to the current image frame. Once a termination command is received <b>608</b>, the tracking ends <b>610</b>.

In one embodiment, a potential field is used to simplify the contour fitting process. Now referring to <figref idref="DRAWINGS">FIG. 7</figref>, one embodiment of a potential field determination process <b>700</b> for a given frame of a depth video stream is shown. The frame image is divided <b>702</b> into segments, (e.g., pixels, sets of pixels, or the like) as for example shown in <figref idref="DRAWINGS">FIG. 3</figref>. The depth data values are compared <b>704</b> among segments to determine segments corresponding to the target's edge. For example, segments that when compared to neighboring segments provide a depth differential above a maximum threshold are deemed edge segments. A reference value is assigned <b>706</b> to those edge segments and a transform is used to assign <b>708</b> values to other segments with respect to the edge segments (e.g., a Manhattan distance transform based on pixel values). The resulting potential field of the depth image can be used for fitting a mathematically representable contour. For example, in one embodiment, gradient vectors can be calculated based on the potential filed.

Now referring to <figref idref="DRAWINGS">FIG. 8</figref>, in one embodiment, the contour fitting process <b>800</b> for any given frame includes dividing <b>802</b> the mathematically representable contour in a number of parts with a fixed orientation. For example, an ellipse can be divided into four arches oriented with the concave sides facing towards the centroids of the ellipse. First, one part is fit <b>804</b> using the depth data or potential field data corresponding to a frame of the target's depth video image as described above. Then, for as long as there are parts of the contour left <b>806</b>, the next part is selected <b>808</b> and fit <b>804</b> over the target edge as above. When no other parts are left to be fit <b>806</b>, a match value is calculated <b>810</b> for the combination of parts of the contour in a first estimated state. For as long as there are states to check <b>812</b>, the same process is repeated with each of the states. The match values for each of the states is used for comparison with other match values at different locations or states within the search area S to determine <b>814</b> the “best fit” from amongst them for tracking the target. The tracking data is then output <b>816</b> and the process is repeated with subsequent frames of the stream.

In one embodiment, the tracking system has shown robustness against partial and temporary complete occlusions. <figref idref="DRAWINGS">FIG. 9</figref> shows a frame of a complete occlusion state of a target hand being tracked. In this frame <b>900</b>, the target hand <b>101</b> is entirely behind a non-tracked arm <b>104</b>. The tracker estimates the position of the target <b>101</b> (e.g., shown as the location of circle <b>106</b>) and catches up with the hand <b>101</b> as soon as it becomes slightly visible again (see, e.g., <figref idref="DRAWINGS">FIG. 1B</figref>). The tracker proves to be robust to partial occlusion of the hand <b>101</b>. In other embodiments, the tracker continues its tracking operation when a passenger's head is occluded by the driver and also operates after a prolonged extreme head tilt by the passenger when he sleeps on the driver's shoulder. In this embodiment, the tracker relies only on shape derived from depth data, therefore unless the occluding object is of generally the same shape, the tracker is able to lock on the tracked target (in case of partial occlusion) or detect the target after complete occlusion. In addition, as described above, in one embodiment the tracking system provides a confidence measure CM, for example, based on its ellipse measure. In this embodiment, the tracker does not drift away during complete occlusions but instead lowers the value of its confidence measure CM for the tracking performance until the occlusion concludes (i.e., a higher confidence measure value is attained).

Body Lean Estimation

One embodiment of a head tracking system includes a body-lean estimator. Body-lean estimation is used for example as an aid for an airbag deployment system. Airbags save thousands of lives worldwide each year but in some instances the airbag deployment can cause injury. Body-lean estimation provides useful information about occupants' positions that can be used for controlling airbag deployment.

In a body-lean estimation system, the tracker's output is used to calculate the mean depth (distance from the camera) of the heads of vehicle occupants. The position of the head is used to determine the general location of the body in the depth image. The depth data corresponding to the body is further used to calculate the mean depth of the body with respect to the camera. These two mean depth values are used to decide the lean of a person (forward, backward or none). If the absolute difference between the distance (mean depth) of the head from the camera and the distance of the body from the camera is more than a fixed threshold, then the person is leaning backward or forward, which can be decided based on the sign of the difference (head at a greater depth implying backward lean and body at a greater depth implying forward lean). As pixel intensities can be translated to real world distance values, choice of threshold is based on real world depth difference, which is used to define body lean.

It should be noted that one benefit of using depth windows with time-of-flight depth sensing cameras includes the ability to use a single camera to track driver and back seat passenger body-lean. For example, for one side of a vehicle (i.e., driver side), a camera can alternate two depth windows to provide two depth image streams one for the driver (closer depth window) and one for the back seat passenger (further depth window) if present. In addition, search area S analysis can include longitudinal divisions of a depth image frame to separate depth information for tracking driver side occupants and front passenger side occupants, for example by splitting the image along its vertical center-line. Thus, depth image streams from a single depth-sensing camera can be used to track at least four regions of a vehicle independently of each other.

Now referring to <figref idref="DRAWINGS">FIG. 10</figref>, a body-lean estimation method is shown. According to one embodiment of this method <b>1000</b>, to estimate the head depth or distance from the head to the camera, for each frame the tracker provides as an output the current state s of the head with a corresponding fitted contour. For example, an ellipse corresponding to s is superimposed on the depth map. This output is input <b>1002</b> for body-lean estimation method <b>1000</b>. The median of the pixel values inside the contour is chosen as the depth or distance from the camera to the head. Although an average depth value can be used, the median is chosen because of its robustness to noise and outliers. If for some reason, e.g., sudden acceleration, the tracker is not right on target or the contour model does not fit the real shape of the head exactly, median gives us the correct value of the depth if at least half of the pixels inside the contour belong to the head being tracked. This makes the depth estimation system very robust to occasional inaccuracies of the tracker.

To estimate body depth or distance from the body to the camera, based on the position of the head as a reference, connected component analysis is used on the depth map to determine <b>1006</b> the region of the image that corresponds to the body of the person whose head is being tracked, i.e., the target. The median of the depth value of this region is calculated <b>1008</b> and taken as the body depth or distance from the body to the camera. For reasons discussed above, the choice of median makes the system robust to noise, occlusion and imperfect segmentation.

As mentioned above, the values for median head depth and median body depth are used to decide <b>1010</b> the lean of the person (forward, backward or none). The body-lean information is output <b>1012</b>. For example, in one embodiment the body-lean data is output to a control unit in a vehicle. The output can be communicated either at a particular time based on a predetermined occurrence, or otherwise on a continuous basis for use by the control unit as necessary. The occupant body-lean and general tracking information can be used by a motor vehicle control logic or control unit for several applications, for example, air-bag deployment, collision avoidance, driver assistance, attention detection, and the like.

Hand and Body Tracking

Other applications of a tracking system include hand tracking and recognition including computer based sign language recognition, computer gesture understanding, and the like. One embodiment of a gesture recognition system includes a module for visual instruction recognition in a robot such as the ASIMO humanoid robot referred to above. Other machine vision techniques can be applied to the tracked target image to recognize hand signs, arm motions, or the like. The image recognition techniques can determine correspondence between human actions and computer commands. This embodiment enables a user to give visual hand commands for control of robot actions, for example, making turns, moving, following, staying, and the like.

The tracking of hands and other body parts can also be used in other human-computer interaction applications such as for example, computer gaming, pedestrian detection, or the like. The implementation of these techniques with respect to this applications as well as similar adaptations falls within the scope of this invention.

While particular embodiments and applications of the present invention have been illustrated and described herein, it is to be understood that the invention is not limited to the precise construction and components disclosed herein and that various modifications, changes, and variations may be made in the arrangement, operation, and details of the methods and apparatuses of the present invention without departing from the spirit and scope of the invention as it is defined in the appended claims.