Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-09-27
2003-10-14
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C375S240210
Reexamination Certificate
active
06633610
ABSTRACT:
BACKGROUND
The invention generally relates to video motion estimation.
Data compression typically removes redundant information from a set of data to produce another set of data that has a smaller size. This smaller size may be beneficial, for example, for purposes of transmitting the data over a bus or network.
For example, data compression may be used to reduce the amount of data that indicates snapshot images, or frames, of a video. In this manner, successive frames of a particular scene of the video may exhibit temporally redundant information that changes very little between the frames. Most changes from one frame to the next in a particular scene typically may be attributable to the motion of objects in the scene. As an example, referring to
FIG. 1
, an object
3
of one frame
4
may be displaced by a few pixels in a particular direction and reappear in a different location in the next successive frame
5
.
Thus, for purposes of compressing the total data that is used to indicate the frames
4
and
5
, the redundant pixel data that indicates the object
3
may not appear twice. Instead, as an example, for the frame
5
, the data may indicate a motion vector that represents the relative displacement of the object
3
between the frames
4
and
5
. Similarly, data for the subsequent frames in which the object
3
appears may indicate motion vectors instead of the pixel intensity data for the object
3
. The above-described technique typically is referred to as motion compensation, and one such technique is described in the Moving Picture Experts Group (MPEG) standard, such as the MPEG-2 standard, for example. The MPEG-2 standard is described in ISO/IEC 13818-1 (MPEG-2 Systems), ISO/IEC 13818-2 (MPEG-2 Video), and ISO/IEC 13818-3 (MPEG-2 Audio), dated in 1994 and provided by the International Organization For Standardization (ISO) and the International Electrotechnical Commission (IEC).
Motion estimation is used to generate the motion vectors and thus, is used to identify and track object movement between frames. One such motion estimation technique uses a block matching algorithm, an algorithm that includes spatially subdividing frames into rectangular grids of subimages
8
(as depicted by a portion
6
of a frame in FIG.
2
). Each subimage
8
is a rectangular block of pixels, and the block matching algorithm tracks movement of the subimages
8
between frames. For example, a particular subimage
8
a
may move by a vector
9
(see
FIG. 3
of a corresponding portion
7
of a successive frame) from the Cartesian coordinates (x
1
,y
1
) in one frame to the Cartesian coordinates (x
2
,y
2
) in the next frame.
To identify the subimages
8
that have moved between successive frames, each subimage
8
of a particular frame may be compared with a subimages
8
of a corresponding region of the next frame. In this manner, this corresponding region may include the subimage
8
of the next frame that has the same Cartesian coordinates and it neighboring subimages
8
. Thus, each subimage
8
of a particular frame may be compared one at a time with selected subimages of the next frame to determine the maximum likelihood that the subimage
8
appears in the next frame, and if the subimage
8
does appear, relative displacement of the subimage
8
between frames is then computed. The maximum likelihood that the subimage appears in the next frame may be determined after each comparison using an image block matching criteria that is based on the computation of the standard deviation of the two subimages being compared.
Unfortunately, typical block matching algorithms use a large amount of memory and use a large amount of processing power. These characteristics may prevent their use with interactive video applications and low cost portable imaging devices.
Thus, there is a continuing need for a technique that address one or more of the problems that are stated above.
SUMMARY
In one embodiment of the invention, a method includes decomposing a first frame of a video into a first set of frequency subbands. The first frame includes a first subimage. A second frame of the video is decomposed into a second set of frequency subbands, and portions of the first and second sets of frequency subbands are selectively compared to locate a second subimage of the second frame. The second subimage is substantially identical to the first subimage.
Advantages and other features of the invention will become apparent from the following description, drawing and claims.
REFERENCES:
patent: 5398067 (1995-03-01), Sakamoto
patent: 5734431 (1998-03-01), Drachiku et al.
patent: 5974186 (1999-10-01), Smith et al.
patent: 5995668 (1999-11-01), Corset al.
patent: 6091777 (2000-07-01), Goetz et al.
patent: 6154557 (2000-11-01), Boon
patent: 6208692 (2001-03-01), Song et al.
patent: 6298163 (2001-10-01), Sodager et al.
Bugg, Jr. George A
Intel Corporation
Kelley Chris
LandOfFree
Video motion estimation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video motion estimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video motion estimation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3160153