Motion vector search methods, motion vector search...

Details Motion vector search methods, motion vector search... Motion vector search methods, motion vector search...

1998-06-15

2001-04-03

Kelley, Chris S. (Department: 2613)

Pulse or digital communications

Bandwidth reduction or expansion

Television or motion video signal

Reexamination Certificate

active

06212237

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a technique for searching for a motion vector, which expresses from which position in other moving-video images a pixel block in a certain moving-video image has moved, being used in video-encoding algorithms, such as MPEG1, MPEG2, and H261, H263, etc., which are international standard.
This specification is based on the patent application No. Hei 9-159964 filed in Japan, the contents of which is incorporated herein by reference.
2. Description of the Related Art
Hereafter, with reference to some typical diagrams, various kinds of conventional motion vector searching methods will be explained.
FIG. 1
shows exemplarily a template
1
which is the object which is searched for a motion vector, and a search area
2
which is a search range of the motion vector. In
FIG. 1
, the template
1
is a pixel block in a certain image and the search area
2
is a pixel block in another image, which is larger than the template
1
. The symbols &Dgr;
3
denote the pixels which comprise the template
1
, and the symbols O
4
are the pixels which comprise the search area
2
.
In
FIG. 1
, since a template
1
is superimposed on the search area
2
, the pixels O
4
of the overlapped part in the search area is not shown. In addition, hereafter, the unit of the number of horizontal pixels is defined as a “pixel,” and the unit of the number of perpendicular pixels is called a line. Therefore, the template
1
shown in
FIG. 1
is 4-pixel×(by) 4-line, and the search area
2
is 11-pixel×11-line.
Now, a “whole searching method,” which is a first prior art for searching for a motion vector to the template
1
, will be explained. By this technique, areas of 4-pixel×4-line of the same size with the template
1
are extracted sequentially by one from the search area
2
. Between the pixel value of each pixel of this extracted area, and the pixel value of the corresponding pixel in the template
1
, sequentially, an absolute difference value or a square difference value, etc., is calculated, and the plural sum-totals of the calculated values for the pixels are calculated for each extracted area.
That is, in the search area
2
, over the upper left to the lower right, when the area of 4-pixel×4-line is shifted by 1 line or 1 pixel at a time, since the search area
2
has 11-pixel×11-line, the total 8×8=64 areas are the objects for the operation between the templates
1
(the operation, which calculates a absolute difference value, a square difference value, etc.). And, the motion vector is obtained from the area where the operational result has the minimum result, where this template
1
has moved from.
In
FIG. 1
, when (0, 0) is set as the motion vector of the pixel block of the position corresponding to the template
1
, the range of the value which a motion vector can take is “−4−+3” in both the horizontal direction and the perpendicular direction. Because the template
1
can be transferred to one side by 4 pixels (or 4 lines) and can be transferred to the other side by 3 pixels (or 3 lines), in the horizontal direction and the perpendicular direction, respectively, as understood by referring to FIG.
1
.
For example, if the operational value (a sum of absolute difference values, a sum of square difference values, etc.) of an area
5
is the minimum, as shown in
FIG. 1
, the motion vector is (2, 2). The above is description of the principle to obtain a motion vector. With reference to the typical diagram of
FIG. 2
, the generalized of this motion vector search is explained.
If the size of a template
6
in a certain image is defined as a-pixel×b-line, the size of a search area
7
in another image is defined as c-pixel×d-line (c≧a, d≧b), and the motion vector of the pixel block at the center of the search area
7
which corresponds to the template
6
is defined as “(0, 0),” the ranges of the values which a motion vector can take are “−(c−a)/2 . . . (c−a) /2+1 in the horizontal-direction, and −(d−b)/2 . . . (d−b), 2+1 in the perpendicular-direction,” an evaluation of “(c−a+1)×(d−b+1)” motion vectors. In
FIG. 2
, the motion vector of the block
8
at the upper-left edge is ((c−a)/2−1 (d−b)/2−1), and the motion vector of the block
9
at the lower-right edge is (−(c−a)/2, −(d−b)/2). Hereinafter, as an example, only the case where a sum of absolute difference values is used as a motion vector searching operational expression for obtaining a motion vector will be explained. Of course, other evaluation formulas, such as a sum of square difference values can be also used as the operational formulas.
Now, if such whole searching methods are adopted, in order to search the search area
2
of
FIG. 1
, it is required to calculate absolute difference values at 64×16=1024 times (by extracting 64 areas, wherein each area consists of 16 pixels). Therefore, the number of operations becomes huge. On the other hand, in order to cut down the number of operations, as a second prior art, a different searching method was proposed, wherein, as first, a motion is evaluated on a reductional image obtained by subsampling, next, a search is conducted only in a narrow range by using the motion vector obtained as the evaluation result as initial value.
With reference to the typical diagram of
FIG. 3
, this technique will be explained.
FIG. 3
exemplarily shows the pixels which are subsampled, when subsampling one pixel per 2-pixel×2 lines. The symbol ▴
10
and the symbol &Circlesolid;
11
show the pixels by which subsampled from the template
1
and the search area
2
, respectively.
First, when obtaining reductional images by subsampling and searching the range of “−1 . . . +1” of the neighborhood of the initial value on the original image, 16×4=64 times of the calculation of absolute difference values (by extracting 16 areas wherein each area consists of 4 pixels) are required on the reductional images, and next 9×16=144 times of absolute difference values are required on the original image. Therefore, the sum total of the number of operations becomes 208 times (64+144 times), and the number of operations is sharply cut down compared with the whole searching methods. Such a motion vector searching method using such a reductional image is described, for instance, in “N. Hayasi, T. Kitui, L. Tamitani, H. Honma, Y. Ooi, T. Miyazaki, K. OobuchI;” “A bidirectional motion compensation LSI with a compact motion estimator,” IEICE Trans. Electron, E78-C, 12, pp.1682-1690, December 1995, etc. In order to realize the vast searching range as an extension of the above-mentioned technique, it can be also thought that searching is conducted on reductional images whose resolution is further lowered by subsampling one pixel per 4-pixel×2-line one pixel per 4-pixel×4-line.
A moving-video image consists of two or more images which continued in a time domain. In case that a motion vector is needed to be obtained between the images which are separated in a time domain, the search must be conducted in a relatively wide range since the range to be searched becomes wide. In such a case, in order to cut down the number of operations, the telescopic-search method is proposed as the third prior art.
With reference to the typical diagram in
FIG. 4
, this telescopic-search method will be explained. In
FIG. 4
, images
12
,
13
,
14
, and
15
are 4 images which continue in a time domain, the image
15
is the present image, and the image
12
, the image
13
, and the image
14
are the previous images of 3 screens before, 2 screens before, and 1 screen before, respectively. A rectangle block
16
moves to the image
13
from the image
12
by a motion vector mv
1
. Similarly, the block
16
moves to the image
14
from the image
13
and moves to the image
15
from the image
14
by motion

Affiliated with

Also associated with

Rating

Motion vector search methods, motion vector search... 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 methods, motion vector search..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Motion vector search methods, motion vector search... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2442119