Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
1999-03-05
2004-11-30
Johnson, Timothy M. (Department: 2625)
Image analysis
Applications
Motion or velocity measuring
C382S236000, C375S240160
Reexamination Certificate
active
06826294
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to the field of digital video compression and specifically to a method for producing a motion vector while reducing the complexity and increasing the speed of the required computations.
Historically, in communication systems, a transmitter would send information to a receiver in an analog format. This means a continuous stream of data (generally voltage variations) is sent from the transmitter to the receiver. The problem with this type of transmission is that there will inevitably be some loss in information. To reduce this loss, many transmission systems have moved to a digital format where the data is converted into a binary digital stream (a sequence of zeros and ones). This type of transmission is useful in that it is robust—it can be stored, recovered, transmitted, processed, etc., all without virtually any error. Any system using the data merely has to distinguish between a zero and a one which is generally easy to do.
A problem arises, however, with a digital transmission that was generally not present in analog transmission. A video stream can be broken down into a series of juxtaposed frames. When a frame is digitized so that it can be transmitted digitally, the frame contains a large amount of data (the series of zeroes and ones), which is much greater than the data required to represent an analog picture. This data is sent to the receiver through a transmission medium which can handle only a finite amount of data per time interval. This becomes problematic when a user requires continuously updated data. For example, in television, film, or other types of video communications, the illusion of motion would be frustrated if there was too large a time interval between consecutive frames. A typical transmission medium may not be able to handle the large amount of data present in a digital transmission in the time interval necessary for many applications. This problem led to the introduction of compression technology which is focused on representing and transmitting a frame of data using fewer bits than without compression.
Briefly, compression algorithms recognize that not every bit of every frame of data need be encoded and transmitted. Samples of data are generally similar enough to each other so that one sample could be used as an estimate of the next sample. These similarities can be further broken down into spatial and temporal relations. Spatial similarities assume that for a given frame of data, information in one portion of the frame will be similar to other information in the same frame. Temporal similarities assume that consecutive frames will generally be similar. This means a frame can basically be represented by a frame which came immediately before it. The temporal similarities are determined using motion estimation algorithms.
There are many types of motion estimation algorithms. These include: the block-based method, pixel-based recursion, and feature based. The block based method, generally referred to as a block matching algorithm, has been adopted by several video compression standards including H.261 and MPEG (Moving Picture Experts Group), and is the focus of the invention.
In the block matching algorithm, a field or frame (collectively referred to hereinafter as a “picture”) which is to be motion compressed is compared to a previously encoded picture which is not motion compressed. The comparison is a correlation of the luminance values between the pictures. The non-motion compressed pictures are called I-pictures (or intra-pictures). They are compressed using only spatial techniques such as a discrete cosine transform. During compression, the first picture to be encoded, which is compared to the I-picture, is called a P-picture (predictive). The P-picture or I-picture could also be used as a reference for encoding a B-picture (bi-directional, prediction can come from prior or subsequent I- or P-pictures). Therefore the terms “reference picture” and “coded picture” will be used throughout the specification to avoid limitation in scope. All of the pictures (both coded and reference) are divided into a plurality of picture elements (“pixels” or “pels”). A macroblock is defined as a rectangular block having 16 by 16 pixels and is the foundation of block matching compression techniques.
For each macroblock of coded picture, a search is performed in a corresponding search area of a reference picture for the macroblock yielding the best match. A best match motion vector is ascertained which starts at the origin of the coded macroblock and points to the macroblock in the reference picture within the search area. The search area is basically a window of the reference picture which generally corresponds spatially to the macroblock of the coded picture. The best match is usually determined by subtracting the corresponding pixels in each macroblock from one another, squaring the result, and then adding up all the squared subtracted values. This is known as the Mean Square Error and is mathematically expressed as
MSE
(
i
,
j
)
=
1
N
2
∑
m
=
1
N
∑
n
=
1
N
(
S
t
(
m
,
n
)
-
S
t
-
1
(
m
-
i
,
n
-
j
)
)
2
,
-
w
≤
(
i
,
j
)
≤
w
where N×N is a rectangular block size, w is the search range, S
t
is the block to be motion compressed in the coded picture, S
t−1
is the reference picture, and i and j represent the horizontal and vertical shift, respectively, of the reference macroblock in the reference picture. This produces the most accurate comparison because any differences between the compared blocks are squared thereby emphasizing larger differences.
As can easily be discerned, this comparison is an expensive process because it requires a multiplier which is not cheaply realized in silicon technologies. Moreover, this comparison is performed for each possible macroblock location in the search range. Considering the large amount of computations required, and the need for a multiplier, this comparison is generally not used in real world applications, but is useful in computer simulations.
One example of a more practical comparison is the Mean Absolute Error (MAE). This computation is similar to the MSE but takes the absolute value of the results instead of squaring them. The Mean Absolute Error is thus defined as:
MAE
(
i
,
j
)
=
1
N
2
∑
m
=
1
N
∑
n
=
1
N
&LeftBracketingBar;
S
t
(
m
,
n
)
-
S
t
-
1
(
m
-
i
,
n
-
j
)
&RightBracketingBar;
,
-
w
≤
(
i
,
j
)
≤
w
However, even this comparison causes problems because the search area chosen could be quite large and each computation requires many circuits. To illustrate, the following 10 stages of circuitry would be necessary:
Stage 1: 256 subtraction circuits (comparing the coded picture to the reference picture).
Stage 2: 256 square compute circuits (if using the MSE) or absolute value circuits (if using MAE).
Stage 3: 128 summation circuits to add 256 numbers.
Stage 4: 64 summation circuits to add 128 numbers.
Stage 5: 32 summation circuits to add 64 numbers.
Stage 6: 16 summation circuits to add 32 numbers.
Stage 7: 8 summation circuits to add 16 numbers.
Stage 8: 4 summation circuits to add 8 numbers.
Stage 9: 2 summation circuits to add 4 numbers.
Stage 10: 1 summation circuit to add 2 numbers.
Ten stages are required for every macroblock being compared. Each adder can generally perform only one addition per clock cycle. So, even when the Mean Absolute Error is used, there is still a 10 stage delay.
One prior art solution utilizing a hierarchical approach, decimates the reference picture thereby reducing the number of pixels which need to be analyzed. The decimation process generally includes taking a specified number of pixels, usually 4, in the horizontal and vertical direction, and replacing them with their average value. This yields a picture with 16 times less information which can be more easily processed but with decreased precision. The decimated image is searche
Johnson Timothy M.
Koninklijke Philips Electronics , N.V.
LandOfFree
Block matching motion estimation using reduced precision... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Block matching motion estimation using reduced precision..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block matching motion estimation using reduced precision... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3288060