Television – Image signal processing circuitry specific to television – Motion vector generation
Reexamination Certificate
1999-05-12
2002-04-30
Britton, Howard (Department: 2613)
Television
Image signal processing circuitry specific to television
Motion vector generation
C375S240160, C382S107000, C382S236000
Reexamination Certificate
active
06380986
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technology used for inter-frame video encoding, and relates in particular to a motion vector search method and apparatus for determining a motion vector to indicate a movement of a pixel block in one image to a location in another image, and a computer program product to execute motion vector search.
This application is based on patent application No. Hei 10-136287 and Hei 10-202628 filed in Japan, the contents of which are incorporated herein by reference.
2. Description of the Related Art
Various conventional motion vector search methods will be described in the following with reference to schematic diagrams.
FIG. 11
shows a schematic diagram of a template
1
that is selected for obtaining a motion vector and a search area
2
in which to search for a motion vector. Template
1
is a pixel block in a target image to be matched, search area
2
is a pixel block in another image, which is larger than the template
1
, to be compared against the target image. White triangles
3
refer to pixels in the template
1
and white circles refer to pixels in the search area
2
.
In
FIG. 11
, template
1
is superimposed over the search area
2
, therefore, white circle pixels
4
that are overlapped in the search area are not indicated. In the following presentation, horizontal pixels are referred as pixels, and vertical pixels are referred as lines, so that template
1
shown in
FIG. 11
is described as 4 pixels×4 lines, and the search area
2
is described as 11 pixels×11 lines.
A first conventional method of searching for a motion vector using template
1
is the exhaustive search method. In this method, a template
1
comprised by 4 pixels×4 lines is used to successively search a search area
2
that is larger than the template size, and the values of each pixel in the sampled areas are calculated with the values of the corresponding pixels in the reference image, in terms of some search parameter such as the absolute value of the differences or squares of differences, and a sum of the chosen search parameter of each pixel in the sampled areas is obtained for each sampled area.
Specifically, the template
1
begins a search from left top to the right bottom in the search area
2
by shifting one pixel or by one line for each sampling, and since the search area
2
is comprised by 11 pixels×11 lines, and the template is 4 pixels×4 lines, a total of 8×8=64 sample areas are subjected to analysis in terms of the absolute value of the differences or squares of the differences between the template
1
and the sample area. A motion vector is then determined and a location in a target area having the minimum computed value of the chosen search parameter.
In
FIG. 11
, if it is supposed that the motion vector of a pixel block of template
1
is described by the zero motion vector (
0
,
0
), then, a possible range of values that the motion vector can have is [−4~+3] in both horizontal and vertical directions, respectively. This is because, as can be seen in
FIG. 11
, template
1
is able to move four pixels (or four lines) in one direction (left and top) and similarly, template
1
is able to move three pixels (or three lines) in the opposite direction (right and bottom).
And, for example, if it is assumed that the minimum computed value (sum of absolute value of differences or sum of squares of the differences) is obtained in pixel block
5
, then the motion vector V is (−
2
, −
2
). This is a numerical illustration of the principle of obtaining a motion vector, but a general approach to vector search will be explained with reference to FIG.
12
.
The size of a template
6
in a target image is described by “a pixels×b lines”, and the size of search area
7
in a comparison (reference) image is described by “c pixels×d lines”, where c≧a, d≧b. Suppose that the motion vector of the center pixel block in the search area
7
corresponding to template
6
is [(
0
,
0
)], then, possible range of motion vector
6
is given by [−(c−a+1)/2~(c−a)/2 horizontal; −(d−b+1)/2~(d−b)/2 vertical], and it is necessary to evaluate [(c−a+1)×(d−b+1)] pieces of motion vectors.
In the case shown in
FIG. 12
, a motion vector for the pixel block
8
at the left upper corner is described by [−(c−a+1)/2, −(d−b+1)/2)], and a motion vector for the right lower corner pixel block
9
is described by [(c−a)/2, (d−b)/2]. Motion vector search parameters referred to in the following presentation are always those that are determined based on a sum of the absolute values of differences. It is, of course, permissible to choose a sum of squares of differences as the search parameter.
When the exhaustive search method is employed, the search area
2
shown in
FIG. 11
requires an absolute value of differences to be calculated 64×16=1024 times (sampling 64 pieces of areas each comprised by 16 pixels), requiring a vast amount of computation. So, to reduce the amount of computation, a second conventional technique of determining a motion vector is known. First, movements are evaluated on a reduced size image obtained by sub-sampling, and then the motion vector thus obtained is used as an initial value of the motion vector to carry out further searches in small areas only.
The second conventional technique will be explained with reference to FIG.
13
.
FIG. 13
shows those pixels
10
,
11
to be matched using sub-sampling size of 2 pixels×2 lines, where black triangles
10
represent pixels in template
1
in a reference image and black circles
11
represent corresponding target pixels in the search area
2
to be sampled.
First, a reduced image is obtained by sub-sampling, and an absolute value of differences is calculated 16×4=64 times (16 sub-sampling of an area having 4 pixels) in the reduced image. Compared with the first conventional technique, the amount of processing required in this technique is reduced by {fraction (1/16)}. However, to search a range of [−1~+1] pixels about the initial values in the reference (comparison) image, absolute value of differences must be computed 9×16=144 times. Therefore, the total number of computations is 208 (=64+144), and the total number of computations is reduced considerably compared with the exhaustive search technique.
Details regarding motion vector search techniques are described, for example, in “A bidirectional motion compensation LSI with a compact motion estimator”, by N. Hayashi, et. al., IEICE Trans. Electron, E78-C, 12, pp. 1682-1690, Dec., 1995.
By combining the second conventional technique and the most advance LSI technology, it is possible to implement a search range of [−128~+128 horizontal; −64~+64 vertical] pixels in one integrated device to obtain good quality video images of normal activity levels, and thereby realizing low manufacturing cost.
However, for moving images at higher speeds such as sports broadcasting, it is necessary to carry out searches over a range of [−200~+200 horizontal; −100~+100 vertical] pixels. Such a motion vector search apparatus capable of searching over a wide area is described in a reference, for example, E. Ogura et. al., “A 1.2 W Single-Chip MPEG2 MP@ML Video Encoder LSI including Wide Search Range Motion Estimation and 81 MOSP Controller”, ISSCC98 Digest of Technical Papers, February., 1998. Incidentally, search range in this reference is [−288~+287.5 horizontal; −96~+95.5 vertical] pixels.
To realize such a vast search area, a technique may be considered in which one pixel is extracted from 4 pixels×2 lines or 4 pixels×4 lines to obtain a reduced image having a reduced resolution. However
Ikeda Mitsuo
Kondo Toshio
Minami Toshihiro
Nakamura Ken
Ogura Takeshi
Britton Howard
Burns Doane , Swecker, Mathis LLP
Nippon Telegraph and Telephone Corporation
LandOfFree
Motion vector search method and apparatus 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 search method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion vector search method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2841494