Image analysis – Applications – Target tracking or detecting
Reexamination Certificate
1998-04-13
2001-05-29
Bella, Matthew C. (Department: 2721)
Image analysis
Applications
Target tracking or detecting
C382S107000
Reexamination Certificate
active
06240198
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to vision systems, and more particularly to tracking three-dimensional figures in a sequence of two-dimensional images.
BACKGROUND OF THE INVENTION
The problem of video-based figure tracking has received a great deal of recent attention, and is the subject of a growing commercial interest. The essential idea is to employ a kinematic model of a figure to estimate its motion from a sequence of video images, given a known starting pose of the figure. The result is a 3-D description of figure motion which can be employed in a number of advanced video and multi-media applications. These applications include video editing, motion capture for computer graphics animation, content-based video retrieval, athletic performance analysis, surveillance, and advanced user-interfaces. In the most interesting applications, the figures are people.
One way to track the moving body of a human figures, i.e., the head, torso, and limbs, is to model the body as an articulated object composed of rigid parts, called links, that are connected by movable joints. The kinematics of an articulated object provide the most fundamental constraint on its motion. There has been a significant amount of research in the use of 3-D kinematic models for the visual tracking of people.
Kinematic models describe the possible motions, or degrees of freedom (DOF) of the articulated object. In the case of the human figure, kinematic models capture basic skeletal constraints, such as the fact that the knee acts as a hinge allowing only one degree of rotational freedom between the lower and upper leg.
The goal of figure tracking is to the estimate the 3-D motion of the figure using one or more sequences of video images. Typically, motion is represented as a trajectory of the figure in a state space. The trajectory is described by kinematic parameters, such as joint angles and link lengths. In applications where it is possible to use multiple video cameras to image a moving figure from a wide variety of viewpoints, good results for 3-D tracking can be obtained. In fact, this approach, in combination with the use of retro-reflective targets placed on the figure, is the basis for the optical motion capture industry.
However, there are many interesting applications in video editing and retrieval where only a single camera view of a moving figure is available, for example movies and television broadcasts. When traditional 3-D kinematic model-based tracking techniques are applied in these situations, the performance of the tracker will often be poor. This is due to the presence of kinematic singularities. Singularities arise when instantaneous changes in the state space of the figure produce no appreciable trajectory change in the image measurements of the kinematic parameters. For example, when the arm is rotated towards the camera, it may not appear to be moving very much. This situation causes standard gradient-based estimation schemes to fail.
Furthermore, in many video processing applications, there may not be a great deal of prior information available about the moving figures. In particular, dimensions such as the lengths of the arms and legs may not be known. Thus, it would be desirable to infer as much as possible about the 3-D kinematics from the video imagery itself.
The prior art can be divided into 2-D and 3-D methods. In 2-D tracking methods, the figure is represented as a collection of templates, or pixel regions, that follow a simple 2-D motion model, such as affine image flow. These methods suffer from two problems that make them unsuitable for many applications. First, there is no obvious method for extracting 3-D information from the output of these methods, as they have no straightforward connection to the 3-D kinematics of the object. As a result, it is not possible, for example, to synthesize the tracked motion as it would be imaged from a novel camera viewpoint, or to use motion of the templates to animate a different shaped object in 3-D. Second, these methods typically represent the image motion with more parameters than a kinematically-motivated model would require, making them more susceptible to noise problems.
There has been a great deal of work on 3-D human body tracking using 3-D kinematic models. Most of these 3-D models employ gradient-based estimation schemes, and, therefore, are vulnerable to the effects of kinematic singularities. Methods that do not use gradient techniques usually employ an ad-hoc generate-and-test strategy to search through state space. The high dimensionality of the state space for an articulated figure makes these methods dramatically slower than gradient-based techniques that use the local error surface gradient to quickly identify good search directions. As a result, generate-and-test strategies are not a compelling option for practical applications, for example, applications that demand results in real time.
Gradient-based 3-D tracking methods exhibit poor performance in the vicinity of kinematic singularities. This effect can be illustrated using a simple one link object
100
depicted in
FIG. 1
a.
There, the link
100
has one DOF due to joint
101
movably fixed to some arbitrary base. The joint
101
has an axis of rotation perpendicular to the plane of
FIG. 1
a
. The joint
101
allows the object
100
to rotate by the angle
74
in the plane of the Figure.
Consider a point feature
102
at the distal end of the link
100
. As the angle &thgr; varies, the feature
102
will trace out a circle in the image plane, and any instantaneous changes in state will produce an immediate change in the position of the feature
102
. Another way to state this is that the velocity vector for the feature
102
, V
&thgr;
, is never parallel to the viewing direction, which in this case is perpendicular to the page.
In
FIG. 1
b
, the object
100
has an additional DOF. The extra DOF is provided by a mechanism that allows the plane in which the point feature
102
travels to “tilt” relative to the plane of the page. The Cartesian position (x, y) of the point feature
102
is a function of the two state variables &thgr; and &phgr; given by:
x=cos(&phgr;)sin(&thgr;),y=cos(&thgr;).
This is simply a spherical coordinate system of unit radius with the camera viewpoint along the z axis.
The partial derivative (velocity) of any point feature position with respect to the state, also called the “Jacobian,” can be expressed as:
[
ⅆ
x
ⅆ
y
]
=
J
ⅆ
q
=
[
-
sin
(
θ
)
sin
(
φ
)
cos
(
θ
)
cos
(
φ
)
0
-
sin
(
θ
)
]
[
ⅆ
φ
ⅆ
θ
]
Singularities arise when the Jacobian matrix J loses rank. In this case, rank is lost when either sin(&phgr;) or sin(&thgr;) is equal to zero. In both cases, J
singq
dq=0 for state changes dq=[10 ]
T
, implying that changes in &phgr; cannot be recovered from point feature measurements in this configurations.
Singularities impact visual tracking by their effect on state estimation using error minimization. Consider tracking the object
100
of
FIG. 1
b
using the well known Levenberg-Marquardt update step:
q
k
=q
k−1
+dq
k
=q
k−1
−(
J
T
J+&Lgr;
)
−
J
T
R,
where &Lgr; is a stabilizing matrix with diagonal entries. See Dennis et al., “Numerical Methods for Unconstrained Optimization and Nonlinear Equations,” Prentice-Hall, Englewood Cliffs, N.J., 1983 for details.
At the singularity sin(&phgr;)=0, the update step for all trajectories has the form dq =[0 C], implying that no updates to &phgr; will occur regardless of the measured motion of the point feature
102
. This singularity occurs, for example, when the link rotates through a plane parallel to the image plane, resulting in a point velocity V
&phgr;
which is parallel to the camera or viewing axis.
FIG. 2
graphically illustrates the practical implications of singularities on tracker performance. In
FIG. 2
, the x-axis plots iterations, and the y-axis plots the an
Morris Daniel D.
Rehg James Matthew
Bella Matthew C.
Choobin M B
Compaq Computer Corporation
Hamilton Brook Smith & Reynolds P.C.
LandOfFree
Method for figure tracking using 2-D registration does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for figure tracking using 2-D registration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for figure tracking using 2-D registration will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2472017