Image analysis – Image compression or coding – Interframe coding
Reexamination Certificate
1998-04-13
2001-07-03
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Interframe coding
C382S235000
Reexamination Certificate
active
06256418
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to compressing techniques, and more particularly to compressing a sequence of images including a moving figure.
BACKGROUND OF THE INVENTION
In the prior art, many techniques are know for compressing a sequence of images, for example, a video or television broadcast. A compressed video consumes less storage in memory, and less bandwidth to transmit on a channel. Video compression can be both spatial and temporal.
Spatial compressing can be used for images that have few details. For example, a block of pixels having identical values can be expressed by the shape of the block, the position of the block, and a single pixel value for the entire block. Temporal compressing can be used for images where changes over time are minimal. In this case, a reference image can be sent, and the reference image can be update with a rate commensurate with the rate of change in the images. Alternatively, compression can be achieved by reducing the sampling rate, although this method tends to degrade the quality of the reproduced images.
Compressing a moving 3-D figures in a video is more difficult. First of all, the pixels which capture the motion of the figure are in constant motion that is hard to predict and track, second the motion of the figure along its track is difficult to described with simple affine models. There, only the 2-D motion of the figure can be represented. This may be adequate for compressing the simple linear movement of a train across a background for example, but using the same technique on a human figure would appear stilted. To accurately represent the track of a 3-D figure in a sequence of images is difficult.
Video-based figure tracking has received a great deal of recent attention in other applications. 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, including video compression, where only a single camera view of a moving figure is available, for example, videos, 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 an arm is rotated, it may be difficult to discern whether the arm is moving at all. This situation causes standard gradient-based estimation schemes to fail.
Furthermore, in many video compressing 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 and inadequate for compressing purposes.
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, such as television broadcast.
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 &thgr; 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:
[
dx
dy
]
=
Jdq
=
[
-
sin
(
θ
)
sin
(
&p
Morris Daniel D.
Rehg James Matthew
Alavi Amir
Compaq Computer Corporation
Hamilton Brook Smith & Reynolds P.C.
Tran Phuoc
LandOfFree
Method and system for compressing a sequence of images... 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 and system for compressing a sequence of images..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for compressing a sequence of images... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2450252