Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-07-21
2002-07-23
Britton, Howard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000, C375S240240
Reexamination Certificate
active
06424676
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a motion image data coding technique and, in particular, to a method of efficiently detecting motion vectors included in motion image data.
2. Description of the Related Art
When transferring motion image data through a communication medium for a video conference, or recording them on a DVD (Digital Versatile Disk) or the like, the data are normally coded in order to reduce the size.
Normally, motion image data are composed of a plurality of image frames and it is well known that efficient coding is possible by utilizing temporal correlation. For example, if there are two image frames #
1
and #
2
obtained at time t
1
: and the t
2
, respectively, efficient compression can be performed by compressing instead of the image frame #
2
an image frame #
12
representing difference data between the frames #
1
and #
2
. This is because the image frame #
12
is data produced by utilizing the temporal correlation between the image frames #
1
and #
2
and that has small values upon normal image movements.
Nowadays, there have been proposed various methods to get higher compression ratios by using efficient coding techniques.
One of the known techniques for raising the compression ratio is a technique that detects motion vectors between contiguous image frames and codes the vectors. Sample implementation of this technique is done by dividing the image frame #
2
into small blocks, i.e. 16×16 square blocks, and for each of the blocks, searching for a small area in the image frame #
1
that resembles the block, and calculating difference data between the block and the small area in the image frame #
1
. Then, the mean absolute of the difference data is calculated. Because this mean absolute is smaller than that of the image frame #
12
, more efficient coding is possible. Although an offset from the detected small area should be coded as a “motion vector” with the difference data in this case, data size after coding will almost always be smaller than that which does not use the motion vector.
The detection of an offset between a block in the image frame #
2
and a small area in the image frame #
1
that resembles the block in the image frame #
2
is called “motion vector detection”. Specifically, a motion vector_mb_is detected such that the sum of each value calculated by an evaluation function applied to a pixel in a square block G
2
in the image frame #
2
and the corresponding pixel in a square block G
1
in the image frame #
1
is minimum. Normally, the absolute or square of a difference is used as an evaluation function.
Now, the primary problem on the motion vector detection is the method of searching for a block in an image frame corresponding to the subject block in another image frame. One of the well-known methods is a so-called “full search method”.
The full search method uses an error evaluation function to express the similarity between two pixels, that is, it regards a block whose sum of values of an error evaluation function is minimal as a block that most resembles the subject block. The error evaluation function is expressed by ferror(pixel
1
, pixel
2
), namely, the absolute value of a difference between pixel
1
and pixel
2
(|pixeI
1
−pixel
2
|) or the square of a difference ((pixel
1
−pixel
2
)×(pixel
1
−pixel
2
)). Now let (x, y) be a position in an image frame and A be a square block containing the position (x, y). And let A(bx, by) be a pixel in the block A. On the other hand, let B be a block in the image frame in which motion vectors are to be searched, let (x+dx, y+dy) be a point in B that corresponds to the point (x, y) in A, and let B(bx, by) be a pixel in B. And let E(dx, dy) be a sum of values, each value being calculated by an error evaluation function whose parameters are a point in A and the corresponding point in B. Then the sum E(dx, dy) can be expressed as the following equation:
E
(
dx, dy
)=&Sgr;
bx
(&Sgr;
by
(ferror(
A
(
bx, by
),
B
(
bx, by
)))
If the range of dx is from dx
1
through dx
2
, and the range of dy is from dy
1
through dy
2
, the full search is done by searching the square defined by (dx
1
, dy
1
) and (dx
2
, dy
2
) in order to find a motion vector.
Although the full search is supposed to achieve the precise motion vector detection, it has the following problems.
First, calculation will be extensive. To keep up with faster movements, the searching area should be expanded. That is to say, the search area should be wide enough to contain the actual motion vector for the precise detection, which requires a huge amount of calculation.
Second, the search result depends on the search order. That is, since the sums of values of the error evaluation function may have the same value at different points, the point to be chosen win depend on the search order. As a result, it is possible that a motion vector that is not reflecting the actual movement is found. Especially, if the image texture is flat or a repeating pattern exists, it is more likely for the sums of values of the error evaluation function to have similar values at different points. In this case, a square block that resembles the reference block will be found, which is far from the actual movement. The motion vector thus detected does not reflect the actual movement.
Furthermore, the full search is carried out assuming the image's simple parallel movement and no noise. But actual moving images are always transforming and there are some cases in which noise comes in. In this case, the motion vector that gives the minimum value of a mean error evaluation function does not necessarily reflect the actual movement. Especially, if a search area is expanded in order to catch hold of fast moving objects, the chance of erroneous detection will be increased. In this case, the erroneous vector may be a considerably long vector. As the result, the difference may be small but the total code length may be long, because the vector should also be coded at the time of data coding. Thus, the coding efficiency is decreased.
Since it is difficult for the full search method to search a wide area and detect the correct motion vector, there are considered some other methods which can reduce calculation, such as a subsampling search method, a sparse position search method, or a hierarchical search method using reduced resolution.
(1) Subsampling Search Method
When calculating a value with a mean error evaluation function, the subsampling search method picks some representative points Instead of every point for the calculation. For example, assuming that the size of a square block is 16×16 pixels, it does not use every point (256 pixels) for the calculation. Instead it uses only a half of them (128 pixels) or a quarter of them (64 pixels), in this method, the target pixels are subsampled so that the precision of motion vector detection will be less than the full search. Especially, if the value of an error evaluation function at a skipped pixel is considerably different from the average, miss detection will occur.
(2) Sparse Position Search Method
The sparse position search method does not implement point by point search in a search area. Instead, it detects a motion vector candidate from a coarse search area first, then, gradually raising the precision. For example, it first searches every four pixels to get a motion vector candidate A, then from the motion vector candidate A, it searches every two pixels to get a motion vector candidate B, and finally it searches point by point around the point B to get a final motion vector C.
Since this method is likely to overlook changes of the space around edges, the precision of motion vector detection is less than the full search. Moreover, since this method restricts motion vectors at the point of coarse search, it cannot detect the correct motion vector once the wrong motion vector candidates are chosen.
It is possible t
Kono Takehiko
Sashida Nobuyuki
Takeuchi Shunichi
Bachman & LaPointe P.C.
Britton Howard
Custom Technology Corp.
LandOfFree
Motion vector detecting method and device, and storage medium does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Motion vector detecting method and device, and storage medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion vector detecting method and device, and storage medium will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826814