JP3335137B2 - MOTION VECTOR SEARCH METHOD, MOTION VECTOR SEARCH DEVICE, AND RECORDING MEDIUM CONTAINING MOTION VECTOR SEARCH PROGRAM - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique used in inter-frame image coding of a moving image and the like. The present invention relates to a motion vector search method, a motion vector search device, and a recording medium storing a motion vector search program for searching for a motion vector to be searched.

[0002]

2. Description of the Related Art Various conventional motion vector searching methods will be described below with reference to schematic explanatory diagrams.

FIG. 11 schematically shows a template 1 from which a motion vector is to be obtained, and a search area 2 which is a search range for a motion vector. Template 1
Is the pixel block in the image to be processed, search area 2
Is a pixel block in another image to be compared, which is larger than the template 1. In the figure, 3 indicated by a white triangle indicates a pixel constituting the template 1, and 4 indicated by a white circle indicates a pixel constituting the search area 2.

In FIG. 11, since the template 1 is shown over the search area 2, the pixel 4 (画素) in the overlapped search area is not shown. Hereinafter, the unit of the number of pixels in the horizontal direction is referred to as “pixel”, and the unit of the number of pixels in the vertical direction is referred to as “line”. Therefore, template 1 shown in FIG. 11 is 4 pixels × 4 lines, and search area 2 is 11 pixels.
Pixel × 11 lines.

[0005] A "first search method", which is a first conventional technique for searching for a motion vector for a template 1, will now be described. In this method, an area of 4 pixels × 4 lines having the same size as the template 1 is sequentially cut out from the search area 2, and a pixel value of each pixel of the cut out area and a pixel value of a corresponding pixel of the template 1 are calculated. Between them, a difference absolute value, a difference square value, and the like are sequentially obtained, and a total sum of the obtained values for each pixel is obtained for each cut-out region.

That is, in the search area 2, when the area of 4 pixels × 4 lines is shifted by 1 pixel or 1 line from the upper left to the lower right, the search area 2 is 11 pixels × 11 lines. , And a total of 8 × 8 = 64 areas are targets for performing an operation (an operation for obtaining a difference absolute value, a difference square value, and the like) with the template 1. Then, a motion vector is obtained assuming that the template 1 has moved from the area where the calculation result is minimum.

In FIG. 11, assuming that the motion vector of the pixel block at the position corresponding to template 1 is (0,0), the range of possible values of the motion vector is horizontal,
It is “−4 to +3” in both vertical directions. This is shown in FIG.
, The template 1 can be moved by four pixels (or four lines) on one side and three pixels (or three lines) on the other side in each of the horizontal direction and the vertical direction.

For example, when the operation value (sum of absolute difference, sum of squared difference, etc.) of the pixel block 5 is the minimum, referring to FIG.
2, -2). The above is the description of the principle of obtaining a motion vector. A generalized version of this motion vector search will be described with reference to the schematic diagram of FIG.

The size of the template 6 in the image to be processed is a pixels × b lines, and the size of the search area 7 in the other images to be compared is c pixels × d lines (c ≧
a, d ≧ b), assuming that the motion vector of the pixel block at the center of the search area 7 corresponding to the template 6 is “(0, 0)”, the range of values that the motion vector can take is “horizontal direction: − ( c−a + 1) / 2 to (ca) / 2, vertical direction: − (d−b + 1) / 2 to (db) / 2 ”,
It is necessary to evaluate “(c−a + 1) × (d−b + 1)” motion vectors.

Incidentally, the motion vector of the pixel block 8 at the upper left corner shown in FIG. 12 is (-(c-a + 1) / 2,-
(D−b + 1) / 2), and the motion vector of the pixel block 9 at the lower right corner is ((ca) / 2, (db) / 2). In the following, only the case of using the sum of absolute differences will be described as a motion vector search operation expression for obtaining a motion vector. Of course, it is also conceivable to use an evaluation expression such as a sum of squared differences as another arithmetic expression.

By adopting such a full search method,
To search the search area 2 in FIG. 11, 64 × 16 = 10
It is necessary to calculate the absolute value of the difference 24 times (one area consisting of 16 pixels is cut out 64 times), which requires a huge amount of calculation. Therefore, in order to reduce the amount of computation, as a second conventional technique, first, motion is evaluated on a reduced image obtained by sub-sampling, and then the resulting motion vector is set as an initial value, A technique for performing a search by using only the information has been proposed.

This will be described with reference to the schematic diagram of FIG. FIG. 13 is a drawing schematically showing pixels extracted by sub-sampling when one pixel is sub-sampled per 2 pixels × 2 lines. 1 indicated by a black triangle
0 and 11 indicated by black circles represent pixels to be sub-sampled from the template 1 and the search area 2, respectively.

First, a reduced image is obtained by sub-sampling, and a difference absolute value calculation is performed on the reduced image 16 × 4 = 64 times (16 regions of 4 pixels are cut out).
In this method, the amount of calculation is 1 in comparison with the first conventional technique.
/ 16. However, in order to search the range of “−1 to +1” around the initial value on the original image, 9 × 16 = 1
Forty-four difference absolute value calculations are required. Therefore, the total amount of calculation is 208 times (64 times + 144 times), and
The amount of calculation is greatly reduced as compared with the full search method.

A method for searching for a motion vector using such a reduced image is described in, for example, "N. Hayashi, TK
itui, I.Tamitani, H.Honma, Y.Ooi, T.Miyazaki, K.Oo
buchi: "A biderectional motion compensation LSI wi
th a compact motion estimator "IEICE Trans. Electr
on, E78-C, 12, pp. 1682-1690, Dec. 1995 ".

[0015] The above-mentioned second prior art and the current latest LSI
When the manufacturing techniques are combined, the “horizontal direction: −128 to +12” necessary to obtain good image quality with a normal motion image is obtained.
8. Vertical direction: A search range of about -64 to +64 "can be integrated on one chip, and can be realized at low cost.

On the other hand, in an image having extremely fast movement such as a sports broadcast, "horizontal direction: -200 to +200,
Vertical direction: It is necessary to search a wide range of about -100 to +100 ". For a motion vector search device having such a wide search range, for example, “E. Ogra, M. Taka
shima, D.Hiranaka, T.Ishikawa, Y.Yanagita, S.Suzuk
i, T.Fukuda, T.Ishii; "A 1.2W Single-Chip MPEG2 MP @
ML Video Encoder LSI including Wide Search Range Mo
tion Estimation and 81 MOPS Controller "ISSCC98 Di
gest of Technical Papers, Feb. 1998 ". Note that the search range in the example of this document is "horizontal: -288 to +287.5, vertical: -9.
6 to +95.5 ".

In order to realize such a wide search range, one pixel per 4 pixels × 2 lines, or 4 pixels × 4
It is conceivable to search on a reduced image with further reduced resolution by subsampling one pixel per line,
The lower the resolution, the more likely it is that the motion vector will be detected incorrectly.
There is a drawback that the image quality is deteriorated as compared with the case where the narrow range is searched by the first and second conventional techniques.

Therefore, as a third prior art, there has been proposed a method of dividing a search area into a plurality of areas, assigning separate motion vector search devices to each of the divided search areas, and searching a wide range. .

This will be described with reference to the schematic diagram of FIG. FIG. 14 schematically shows a template 13 from which a motion vector is to be obtained, and a search area 12 which is a search range of the motion vector. The range of values that the motion vector can take is “−8 to +
7 ", and the search area 12 is 19 pixels × 19 lines, so that 16 × 16 = 256 areas, four times as large as those in FIG. .

That is, the motion vector searching device is required to have four times the computational power as compared with the case where the range of values that the motion vector can take is "-4 to +3" in both the horizontal and vertical directions. At this time, as shown in FIG. 14, the search area 12 is divided into four areas 1 in which the border pixels overlap.
If the motion vector search device is divided into 4, 15, 16, and 17, and each region is searched in parallel by a separate motion vector search device, a motion vector search device capable of performing a sum of absolute difference calculation for 64 regions is provided. With four units, the sum of absolute differences can be calculated for 256 areas.

A search method in which such a search region is divided into a plurality of regions and different motion vector search devices are assigned to the respective divided search regions is described in, for example,
"K. Yang, MTSun, L. Wu:" A Family of VLSI Designs
for the Motion Compensation Block-Matching Algori
thm "IEEE Trans. CAS, pp. 1317-1325, Oct. 1989".

However, in the third prior art, as the search range is widened, the calculation capability of the motion vector search device must be increased, and the cost increases. Therefore, a fourth conventional technique has been proposed as a method of artificially expanding the search range without increasing the cost.

In the fourth prior art, since the motion of an object on an image in a moving image is temporally continuous, the distribution of the motion vector of an image encoded in the past is examined to check the current encoding. Focusing on the fact that the motion of the entire image can be predicted to some extent, the search is performed by shifting the center of the search range in the direction of the predicted motion. This will be described with reference to the schematic diagram of FIG.

FIG. 15 shows that the motion of the entire image is (−2, −).
3), and search for a motion vector centered on the pixel block 19 where the motion vector = (− 2, −3). That is, the search for the motion vector in the range of “−6 to +1” in the horizontal direction and “−7 to 0” in the vertical direction is performed on the pixel block 13. The number of pixels in the search area 18 to be searched based on the shifted pixel block 19 is “−4 to
This is the same as when searching for a motion vector in the range of “+3”. With this method, when the entire image is moving in one direction, such as rightward or upward, a pseudo wide range can be searched without increasing the amount of calculation.

A motion vector search method for shifting the center of the search range to search a pseudo wide range is described in, for example, "Sousou Zhu, Masayuki Mizuno, Yutaka Yokoyama, Yasushi Oi,
“One-chip MPEG2-MP @ ML video coding LSI
Motion vector search window shift ", 199
7 IEICE General Conference, SC-11-5 "(S. Zhu, et al.,
"Video Quality Improvement by Search Window Shift
ing ", Preceding of the 1997 IEICE General Conferen
ce, pp. 306, 1997).

Although the description has been made by paying attention only to the calculation amount, the problem that the number of pixels in the search area increases when the search range is widened is also a problem. FIG. 16 shows a typical configuration of the motion vector search device.

The template and the search area are both stored in the image memory 24 outside the motion vector search device 20.
0 is read into the template memory 22 and the search area memory 23 inside, and the sum of absolute difference values / minimum value detector 2
Sent to 1.

Normally, the transfer of pixels inside the motion vector search device 20, that is, between the template memory 22 and the sum of absolute difference value / minimum value detector 21 and between the search area memory 23 and the sum of absolute difference value calculation / The transfer to and from the minimum value detector 21 is fast, but the motion vector search device 20
Is low speed, that is, the transfer between the template memory 22 and the image memory 24 and the transfer between the search area memory 23 and the image memory 24 are slow.

Here, since the number of pixels of the template is small, the transfer between the template memory 22 and the image memory 24 does not pose a problem in configuring the motion vector search device 20, but the pixels in the search area do not matter. Since the number is large, the transfer amount between the search area memory 23 and the image memory 24 must be minimized.

Referring to FIG. 17, a fifth conventional technique which is usually used to reduce this transfer amount in image coding will be described. In image coding, an image is divided vertically into template sizes, which are called slices. The slice is further divided in the horizontal direction into template sizes. Encoding is performed in order from top to bottom for slices, and in each slice for templates from left to right. Therefore, the search areas of two adjacent templates have a considerable overlap.

For example, the search areas of the templates 27 and 28 in the slice 26 shown in FIG.
When the detection of the motion vector of the template 27 is completed, all pixels of the search area 29 are present in the search area memory 23 in FIG. Following the detection of the motion vector of template 27, template 2
8 is obtained, when the detection of the motion vector of the template 27 is completed, a new pixel of the area 31 is read, and all the pixels of the search area 30 of the template 28 are stored in the search area memory 23. Yes.
That is, if the motion vector is searched in the order of the template from the left to the right in the slice, it is not necessary to transfer all the pixels of the search area of each template from the image memory 24 to the search area memory 23. It is only necessary to transfer only the portion that does not overlap with the search area.

In FIG. 17, the pixel positions in the vertical direction of the search area 29 and the search area 30 coincide with each other, but the positions of the two search areas 29 and 30 are shifted in the drawing for easy viewing.

The fifth prior art described here is:
Good consistency with the fourth prior art. That is, in the fourth conventional technique, if the search range of all templates included in a slice is shifted equally, the fifth conventional technique can be easily applied.

[0034]

However, in the fourth prior art proposed to expand the search range while suppressing an increase in cost, the fourth prior art analyzes a motion vector of a previously coded image to analyze a change in motion. If the motion of the image currently being encoded suddenly changes and a motion vector cannot be detected in a narrow area to be actually searched, it cannot be determined how much the search area is shifted thereafter. There's a problem. For example, if an image with a motion exceeding the actual narrow search area continues immediately after the scene change, determine the number of pixels to be shifted first even if it moves at a constant speed in a certain direction. Can not predict the movement thereafter.

Further, in the fourth prior art, since the same shift is performed for the entire image, it is not possible to cope with the case where different motions exist in the image. For example, in an image in which the pendulum is a close-up, the fulcrum side of the pendulum moves slowly, and moves closer to the tip. Also, for example, in an image of a train, the background is stationary,
The train translates horizontally. In order to detect a motion vector in a search area as narrow as possible in these images, it is necessary to change the amount by which the search area is shifted even in the same image.

Further, in the fourth prior art,
As a result of searching for a part in the image, even if it is detected that the motion has changed from the past image, it cannot be reflected in the search for the remaining part in the same image.

The present invention has been made to solve such a conventional problem, and its purpose is to increase the search range without causing an increase in the cost of the motion vector search device, and to improve the coding range in the past. Regardless of the image obtained, the motion of the image currently being coded is checked in the expanded search range, so that if the motion is within the expanded search range, the motion is always detected, and the number of pixels for shifting the search area is determined. Is to provide a means for determining

[0038]

In order to achieve the above object, the present invention evaluates the movement of the entire template group consisting of a fixed number of templates, and when the movement of the entire template group can be detected, the evaluation is performed. The motion is output, and when the motion cannot be detected, the fact that the motion cannot be detected is output.
When the movement of the entire template group can be detected, the search area of the template group to be searched next is shifted in accordance with the movement, and when the movement of the entire template group cannot be detected, the search of the template group to be searched next is performed. , A motion vector search method for shifting a search area to a predetermined position, and a motion vector search apparatus including means for performing these steps. Thus, the search range can be expanded without causing an increase in the cost of the motion vector search device, and if the motion is within the expanded search range, the motion can always be detected. , The shift amount of the search area can be corrected. In addition, the motion of the entire number of templates (template group) is evaluated, and the search area of the next group of templates to be searched is shifted in accordance with the motion of the entire number of templates (template group) to search in detail. Thereby, variation in motion vectors due to erroneous detection is suppressed, and as a result, image quality is improved.

Further, according to the present invention, in a motion vector search method and a motion vector search apparatus for searching for an area having a certain area by shifting an area which may be referred to by a search, a template comprising a certain number of templates Reference vector set for each template in group
By searching the search area shifted only by
The rate change vector is obtained, and the rate
By adding the quasi-vectors,
Calculate actual motion vectors and set templates
The actual motion vector of a certain number of templates in
It evaluates the overall motion using, balance when able to detect movement of the whole template group is to be next searched the movement
Set as reference vector of rate group, first step
A second step and, overall group the template group to return to
A predetermined vector is set as a quasi vector, and the first scan is performed.
And returning to the step.

According to the present invention, in the motion vector search method and the motion vector search apparatus, when the motion of the entire template group cannot be detected in the third step, the search area is searched in the next search for the template group. Is reset, and a block at the center of the search area is set as a block indicated by the motion vector after the reset.

Further, in the motion vector search method and the motion vector search apparatus according to the present invention, in the third step, when the motion of the entire template group cannot be detected, the motion is searched from the next template group to be searched. Until a detectable template group appears, the reference vector indicating the shift of the search area is changed for each template group to search for a different range of motion vectors.

Further, according to the present invention, in the motion vector search method and the motion vector search apparatus, before starting the search for the first image, a template group at an appropriate position for detecting the motion of the entire image in the first image. about,
Perform multiple searches by shifting the search area to different positions, detect the motion of the entire image in a wide range, and when motion is detected, change the search area of the first template group according to the motion. If you shift and cannot detect the motion,
The method further includes the step of shifting the search area of the first template group by a predetermined reference vector. In the third step, when the motion of the entire template group cannot be detected, the motion can be detected from the template group to be searched next. A template group appears or a predetermined reference vector is set up to the last template group of an image including the template group, a search is performed, and before the search for the next image is started, the motion of the entire image in the next image is determined. For a template group at an appropriate position to be detected, the search area is shifted to different positions, and a plurality of searches are performed, the motion of the entire image is detected in a wide range, and the motion of the next image is adjusted in accordance with the motion. The search area of the first template group is shifted.

Further, according to the present invention, in the motion vector search method and the motion vector search apparatus, in the second step, when a motion of the entire template group can be detected, the motion and the motion in the screen searched in the past are detected. Using the motion, the shift of the search area of the template group to be searched next is determined and shifted. In the third step, when the motion of the entire template group cannot be detected, the set motion and the search The shift of the search area of the template group to be searched next is determined and shifted using the movement on the screen.

Further, in the motion vector search method and the motion vector search apparatus according to the present invention, in the first step, even if there is no template in the search area of each template that does not have a block that matches the template. When detected, it is output that the movement of the entire template group cannot be detected in the step.

Further, in the motion vector search method and the motion vector search apparatus according to the present invention, all templates in the same slice are included in the same template group.

[0046] Further, the present invention provides a recording medium recording a program for executing the motion vector search method of the present invention on the computer. Here, the recording medium is a computer-readable portable medium memory, a semiconductor memory, a hard disk, or the like.

[0047]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS In the present embodiment, two motion vector searching apparatuses and methods each having different characteristics will be disclosed. The processing outline of the first motion vector search method and apparatus is as follows. First, a motion vector of the entire image to be processed is obtained by a predetermined method, and this is set as a reference vector indicating the motion of the entire image. Here, examples of the predetermined method include a method of obtaining a motion vector in a wide search area for some templates in an image to be processed, a method of searching on a reduced image created by sub-sampling, and the like. .

Then, a narrow search area centering on the reference vector is set for each template in the image to be processed, and a search is performed within this area to obtain a displacement vector. The motion vector of the template is a vector obtained by adding the obtained displacement vector and the reference vector. This process is performed for all templates in the image to be processed.

The processing outline of the second motion vector search method and apparatus is as follows. In an image to be processed, a template group is set in units of one or more templates. When a motion vector as a template group can be detected from a motion vector of each template in the template group, the motion vector of the detected template group as a whole is used to search for a search area in the next template group. Set the shift position. On the other hand, when the motion vector as the template group cannot be detected, the shift position of the search area in the next template group is different from the shift position of the search area of the template group in which the motion cannot be detected.

Hereinafter, a first method and apparatus for searching for a motion vector will be described as first to first to sixth embodiments. A second motion vector search method and apparatus will be described as the second to second embodiments.

Hereinafter, an embodiment of the present invention relating to a first motion vector search method and apparatus will be described with reference to the drawings.

[Embodiment 1-1] FIG. 1 is a block diagram showing a configuration example of an embodiment 1-1 of the present invention.

The motion vector search device 1 according to the present embodiment
00 has a wide search area motion vector search unit 110 for calculating a reference vector and a narrow search area motion vector search unit 120 for calculating a displacement vector. Here, the “reference vector” in the first motion vector search method and apparatus refers to a vector representing the motion of the entire image to be processed with respect to the image to be compared. Further, the “transition vector” means a motion vector in a search area having a shift position in consideration of a reference vector with respect to each template in an image to be processed.

FIG. 2 is a flowchart showing processing in the 1-1 embodiment. Here, the description of the operation in the 1-1 embodiment shows processing contents common to the first motion vector method. In the present embodiment, first, in the motion vector search unit 110 for a wide search area,
A wide area is searched, and a reference vector indicating the motion of the entire image is obtained (step S1). At this time, the wide search area motion vector search unit 110 obtains motion vectors in a wide search area for some templates in the processing target image. Then, using the obtained one or more motion vectors, a motion vector of the entire processing target image with respect to the comparison target image is obtained. Of course, if the calculation capability of the wide search area motion vector search unit 111 is sufficiently large, motion vectors in a wide search area may be obtained for all templates in the image to be processed. Details of the operation of the wide search area motion vector search unit 110 will be described in the first to second to fourth embodiments. Here, the “wide area” or the “wide search area” refers to an area wider than the search area normally set for the template to be processed. For example, the size of an image of one frame when the NTSC signal is digitized is 720 pixels × 480 lines. The size of the template (generally called "macroblock") in this image is 16 images × 16 lines. The search area set for this macroblock is ± 32 in the horizontal direction as the range that the motion vector of this macroblock can take.
It is generally set in an area where the image is ± 32 images in the vertical direction. On the other hand, in the case of the “wide area” or the “wide area search area” in the present invention, for example, the range in which the motion vector of the macroblock can be
It is set in an area of 100 pixels and ± 50 pixels in the vertical direction. In addition, 1080 of HDTV (High Definition TV)
In the case of the I format, the size of an image of one frame is
It is 1920 pixels × 1080 lines. In this case, the size of the macro block is also generally 16 images × 16 lines. In this case, the “wide area” or the “wide area search area” is set, for example, as an area in which the motion vector of the macroblock can take ± 200 pixels in the horizontal direction and ± 100 pixels in the vertical direction. in this way,
By setting a search area wider than a normally set search area, it is possible to cope with a case where an image to be processed includes a fast-moving image, that is, a case where a motion vector of a template is large. As a result, an appropriate reference vector can be obtained.

Next, the motion vector search unit 120 for narrow search area searches all templates in the image individually for a narrow area centered on the reference vector, and finds a displacement vector from the reference vector for each template. (Step S2), the reference vector and the displacement vector are added for each template, and the result is used as the motion vector of each template (step S3). That is, the narrow search area motion vector search unit 120 sets a narrow search area with the reference vector shifted as described with reference to FIG. 15 for one template A in the image to be processed. And
The narrow search area motion vector search unit 120 obtains a motion vector (displacement vector) of the template A within the search area by using, for example, the “all search method” described with reference to FIGS. Motion vector search unit 12 for narrow search area
0 performs the process of step S2 by performing this process on all templates included in the image to be processed. Subsequently, the narrow search area motion vector search unit 1
Step 20 calculates motion vectors of all templates included in the processing target image by adding a reference vector to each displacement vector obtained for each template in step S3.

It should be noted that there may be two or more reference vectors representing the motion of the entire image in one image. For example, there is a case where a large object moves across a stationary background.

[Embodiment 1-2] FIG. 3 is a diagram for explaining Embodiment 1-2 of the present invention. In a moving image, a plurality of images are temporally continuous, and in image encoding, a motion vector of not only an image one frame before but also a plurality of images before the frame may be obtained. In FIG. 3, A, B, C, and D are temporally continuous images, and the motion vector Vt is a reference vector indicating the motion of the image D with respect to the image A. Here, the image is originally two-dimensional, but is represented by one-dimensional for simplicity of explanation. The motion vector V1 is a vector indicating the motion of the image B with respect to the image A. Similarly, V2, V
Reference numerals 3 denote vectors indicating the motions of the image C based on the image B and the image D based on the image C, respectively, and Vt = V1
+ V2 + V3.

FIG. 4 is a flowchart showing processing in the 1-2 embodiment. The device configuration is shown in FIG.
Is the same as in the 1-1 embodiment shown in FIG. In the present embodiment, the wide search area motion vector search unit 110 performs separate searches for obtaining V1, V2, and V3 (steps S11 to S13), and adds V1, V2, and V3 to determine the image A as a reference. Is set as a reference vector Vt indicating the motion of the image D (step S14). Here, how to obtain a motion vector between adjacent images A and B by the wide search area motion vector search unit 110 will be described. The wide search area motion vector search unit 110 performs the following processing. 1) Select a plurality of templates at predetermined locations in the image A (for example, near the center of the image A or near the corners of the image A). 2) Set a wide search area for the selected template. Then, a motion vector of the template for the image B is obtained. This is performed for all the selected templates. Here, as a method of obtaining a motion vector, for example, any of the first to fourth conventional techniques described above is used. 3) When a difference absolute value or a difference square value obtained when each motion vector is obtained is larger than a predetermined threshold value among a plurality of obtained motion vectors, the image A is used as a reference. It is determined that the motion of the image B is not determined. Then, the motion vector between the images A and B is set to (0, 0). 4) When the absolute value of the difference or the difference squared value is equal to or smaller than a predetermined threshold value for all of the obtained motion vectors, the average value of the motion vectors, or
The median of the distribution of the motion vectors is set to the adjacent image A,
A motion vector between B and B is assumed.

Wide search area motion vector search section 110
Performs the processing described above in steps S11, S12, S1.
Perform in step 3. Steps S11 to S14 in FIG.
Is the specific processing content of step S1 in FIG.

Next, the narrow search area motion vector search section 120 searches for a narrow area centering on the reference vector individually for all templates on the image D based on the image A, and Find a displacement vector from the vector (step S1)
5). Thereafter, the reference vector and the displacement vector are added for each template, and the result is set as the motion vector of each template (step S16). Steps S15 and S16 are the same processing as steps S2 and S3 in FIG.

When detecting a motion vector of an object moving at the same speed, searching for a motion vector between temporally distant images requires searching for a wider range than searching for a temporally close image. No. In the present embodiment, the search for motion vectors between images that are close in time is repeated, and the sum thereof is used as a motion vector between images that are temporally separated. The search range can be narrower than in the case where the search is performed.

In this embodiment, an example is shown in which there are two images B and C between the image A to be processed and the image D to be compared. Even if other numbers of images are included, the same processing can be used.

[Embodiment 1-3] FIG. 5 is a flowchart showing a process according to Embodiment 1-3. The device configuration of the first to third embodiments is the same as that of the first embodiment shown in FIG.

In this embodiment, the wide search area motion vector search section 110 shown in FIG. 1 directly subsamples a high-resolution image or converts a high-resolution image using a low-pass filter, and then performs subsampling. A wide area is searched using the reduced image created with the low resolution, and a reference vector indicating the motion of the entire image is obtained (step S21). The processing in step S21 will be described in more detail below. 1) Create a reduced image A of an image to be processed and a reduced image B of an image to be compared. The method of creating the reduced image is as described above. 2) For a certain template a in the reduced image A, a large search area b is set using the reduced image B. 3) A motion vector of the template a is obtained using the search area b. 4) By repeating the above 2) and 3), the motion vectors of all the templates in the reduced image A are obtained. 5) The average value of all the obtained motion vectors or the median value of the distribution of the motion vectors is set as the reference vector of the processing target image. Step S21 is the same as step S21 in FIG.
1 is the specific processing content.

When the processing in step S21 is completed, the narrow search area motion vector search unit 120 uses the high-resolution image used to create the reduced-resolution reduced image and deletes all the images in the image. A narrow area around the reference vector is individually searched for the template in detail, and a displacement vector from the reference vector is obtained for each template (step S2).
2). Thereafter, the reference vector and the displacement vector are added for each template, and the result is set as the motion vector of each template (step S23). Steps S22 and S23 are the same processing as steps S2 and S3 in FIG.

In the present embodiment, the motion vector search unit for wide search area 110 obtains a reference vector on a reduced image having a low resolution, so that the cost for searching a wide area can be suppressed.

In the above-described embodiment 1-2, the wide search area motion vector search section 110 uses step S21 to execute steps S11 and S1 in FIG.
In each step of S2, S13, the motion vectors V1, V2, V
You may ask for 3.

[First to Fourth Embodiment] FIG. 6 is a flowchart showing processing in the first to fourth embodiments. The device configuration of the 1-4th embodiment is the same as that of the 1-1 embodiment shown in FIG.

In the present embodiment, the wide search area motion vector search section 110 searches a wide area only for the number of templates smaller than the total number of templates of the entire image and necessary for knowing the motion of the entire image. Then, a reference vector indicating the motion of the entire image is obtained (step S3).
1 to S33). The operation of the wide search area motion vector search unit 110 in S31 to S33 will be described more specifically as follows. First, at the start of processing (start time) of an image to be processed, templates in the image to be processed, in which the number of templates necessary to know the movement of the entire image to be processed are set. And Here, the number of “templates necessary for knowing the entire image” and their positions, which are processed in steps S31 to S33, will be described separately. It is also assumed that a template to be processed first is selected from a plurality of set templates at the start of processing. First, the wide search area motion vector search unit 110 sets a wide search area for the selected template template using the image to be compared. Then, a motion vector of the template is obtained. Here, as a method of obtaining a motion vector, for example, the first to fourth
Using any of the prior arts. (Step S31).
Next, it is determined whether or not the processing of all templates set at the start of the processing has been completed, thereby determining whether or not a reference vector can be obtained (step S32). A template to be processed next is selected from the templates (step S33).
On the other hand, when the motion vectors of all the templates set at the start of the processing are obtained, the reference vector can be obtained.
Calculates a “reference vector”, which is the motion of the entire image, using the plurality of obtained motion vectors (step S3).
2). The calculation of the reference vector is performed as follows. Among the obtained plurality of motion vectors, a difference absolute value or a difference squared value obtained when each motion vector is obtained,
When there is something larger than the predetermined threshold,
It is determined that no movement is obtained. Then, the reference vector is set to (0, 0). When the difference absolute value or difference square value obtained when obtaining all the motion vectors is equal to or smaller than a predetermined threshold value, the average value of the motion vectors or the motion vector The median of the distribution is defined as a reference vector.

Steps S31 to S33 are specific processing contents of step S1 in FIG.

If it is determined in step S32 that the reference vector has been determined, the narrow search area motion vector search unit 120 individually determines the reference vector for each template in the image used to determine the reference vector. A narrow area at the center is searched, and a displacement vector from a reference vector is obtained for each template (step S34). When the displacement vector is obtained for each template, the reference vector and the displacement vector are added, and the result is set as the motion vector of each template (step S35). Step S
Steps S34 and S35 are the same as steps S2 and S3 in FIG.

In the present embodiment, the wide search area motion vector search unit 110 searches only a very small number of templates compared to the total number of templates of the entire image, thereby suppressing the cost for searching a wide area. be able to. The number of templates required to know the motion of the entire image is set in advance according to the type of the image. For example, when the entire image is moving in a uniform direction, a search for a wide area with only one template can obtain a reference vector indicating the motion of the entire image. When the movement of the image is unknown and it is desired to determine whether or not the entire image is moving in one direction, a total of five templates at the center and four corners of the image may be examined.
The number of templates required to know the movement of the entire image can be determined by, for example, taking statistics, and examining the movements of as many templates as possible to eliminate the influence of erroneous detection.

In the above-described embodiment 1-2, the wide search area motion vector search unit 110 uses steps S31 to S33 to execute step S1 in FIG.
In each step of S1, S12 and S13, the motion vector V1,
V2 and V3 may be obtained.

[First to Fifth Embodiment] FIG. 7 is a block diagram showing a configuration example of the first to fifth embodiments of the present invention. The motion vector search device 200 according to the present embodiment includes only a narrow search area motion vector search unit 210 for searching a narrow area. In the present embodiment, the reference vector and the displacement vector are obtained by using a single narrow search area motion vector search unit 210 by time division.

FIG. 8 is a flowchart showing processing in the first to fifth embodiments. For one template, a narrow area is searched a plurality of times while changing the search area until the search of the entire wide area is completed, and a motion vector for the wide area is obtained. Specifically, for example, FIG.
The motion vector of the large search area 12 is obtained by temporally and sequentially searching the four narrow areas 14, 15, 16, 17 shown in FIG.

That is, the following processing is performed. Move the search center for a certain template to the motion vector = (0,0)
A search area shifted from the position is set (step S4).
1) Search for a motion vector in the set area (step S42). Until the search for the entire wide area is completed and a motion vector of a certain template is obtained (step S43), the amount of shifting the center of the search for the same template is changed while setting a different search area (step S44). The search processing for the region that has been set is repeated.

The above processing is performed until the search for the number of templates necessary to know the motion of the entire image is completed and a reference vector indicating the motion of the entire image is obtained (step S4).
5) Repeat while changing the template (step S46).

More specifically, with reference to FIG. 14, the operation of the narrow search area motion vector search section 210 is as follows. First, at the start of processing of the image to be processed, the template in the image to be processed is
It is assumed that a required number of templates have been set to know the motion of the entire image to be processed. Here, regarding the number of “templates necessary to know the entire image” and their positions, which are processed in steps S41 to S46,
This is the same as the fourth embodiment. It is also assumed that the template 13 in FIG. 14 is selected as a template to be processed first among a plurality of set templates at the start of the processing. First, the narrow search area motion vector search unit 210 sets the search area for the set template 13 to the area indicated by the reference numeral 14 (Step S).
41). Next, a motion vector is obtained by comparing the search area 14 with the template 13 (step S4).
2). Four search areas 14, 15, 16, 17 in FIG.
Is completed, that is, it is determined whether the search of the search area 12 in the wide range has been completed and the motion vector of the template currently being processed has been obtained (step S4).
3). If the search has not been completed, the next search area (for example, search area 15) is set (step S44), and the process proceeds to step S42.

When the search in all four search areas 14, 15, 16, 17 is completed (step S43: YES), the motion vector of the template 13 in the wide search area processing 12 is obtained. Thus, it is determined whether or not the search for all preset templates has been completed, thereby determining whether a reference vector is obtained (step S45). If the result of the determination in step S45 is that the search for a preset number of templates has not been completed, an unprocessed template that is a preset template is selected (step S46), and the process returns to step S41. Step S when the search for the preset number of templates is completed.
The method of calculating the reference vector at 45 is the same as the method described in step S32 of FIG. The reference vector is obtained as described above.

Once the reference vector indicating the motion of the entire image has been obtained, a narrow area centered on the reference vector is individually described in detail for all the templates in the image including the template group for obtaining the reference vector. A search is performed to determine a displacement vector from the reference vector for each template (step S47). When the displacement vector is obtained for each template, the reference vector and the displacement vector are added, and the result is set as the motion vector of each template (step S4).
8). Steps S47 and S48 are the same as step S of FIG.
This is the same processing as in steps 2 and 3.

Although there is a difference between the processing units, steps S41 to S46 are the specific processing contents of step S1 in FIG. Also, in the above-described 1-2 embodiment, the motion vector search device 100 performs steps S41 to S41.
Using S46, steps S11, S12, and S in FIG.
In each of the thirteenth steps, processing for obtaining the motion vectors V1, V2, and V3 may be performed.

In the present embodiment, the time required for the search is the sum of the time for obtaining the displacement vector and the time for obtaining the reference vector. If the number of templates to be searched to know the reference vector is small, the time required for the processing of steps S41 to S46 for obtaining the reference vector in the flowchart of FIG. The reference vector can be obtained with a small increase in the processing time, which is shorter than the processing time.

However, when the search area becomes large, the search area stored in the external image memory 24 is read into a search area memory (not shown) in the motion vector search apparatus 200 when the motion vector search is performed. Even with this configuration, the pixel transfer capability of the search area memory and the image memory 24 may be insufficient.

FIG. 9 is a schematic explanatory view of the first to fifth embodiments. In FIG. 9, reference numeral 46 denotes an overlapping portion of the four narrow regions 14, 15, 16, 17 shown in FIG. . As can be seen from FIG. 9, the four narrow areas 14, 15, 1
In pixels 6 and 17, the number of pixels belonging to two or more regions is small. Therefore, in the first to fifth embodiments, a configuration is adopted in which the search area stored in the external image memory 24 is read into the search area memory 23 inside the motion vector search apparatus 200 at the time of the motion vector search. However, the number of pixels to be transferred from the image memory 24 to the search area memory 23 when the area to be searched is changed only slightly decreases. As the search area becomes wider, the ratio of the number of pixels of the overlapping portion 46 to the number of pixels of the entire wide search area becomes smaller, and the search area memory 23 and the image memory 2
4 is a serious problem.

[1-6th Embodiment] FIG. 10 is a flowchart showing a process in the 1-6th embodiment. The device configuration of the first to sixth embodiments is as follows:
This is the same as the first to fifth embodiments shown in FIG. In the present embodiment, when the reference vector is obtained, the conventional fifth technique is applied to reduce the transfer amount of pixels between the search area memory 23 and the image memory 24. That is, first, for all templates to be searched within a specific slice,
A search area in which the center of the search is shifted by a fixed number of pixels from the position of the motion vector = (0, 0) is set, and the search is performed in order from the template located at the end. Next, when the search is completed for all the templates to be searched in the specific slice, the center of the search is set to the motion vector = (0,
A search area shifted by another number of pixels from the position 0) is set, and the search is performed in the same manner. By repeating this, a wide area is searched, and a motion vector of a wide area is obtained for each search target template in a certain slice. Further, the same search is performed for another slice, and the number of slices necessary to know the motion of the entire image is searched to obtain a reference vector.

[0086] This will be described in more detail with reference to FIG.
Among the templates to be searched in the slice, for the template located at the end, a search area is set in which the search center is shifted from the position of the motion vector = (0, 0) (step S51). A motion vector of the set area is searched (step S52). This process is repeated while changing to adjacent templates in the same slice until motion vectors are obtained for all the search target templates in the slice (step S53) (step S54). However, in step S54, the amount by which the center of the search is shifted is not changed.

When the motion vectors are obtained for all the templates to be searched in the slice, the search is completed for the entire wide area, and the motion vectors are obtained for the individual templates in the slice (step S5).
5) Change the template in the slice to the template located at the end (step S56), and
Returning to step 52, the same processing is repeated. This step S5
In step 6, the amount of shifting the center of the search is changed to set a different search area.

The above processing is repeated until the search for the number of templates necessary to know the motion of the entire image is completed and a reference vector indicating the motion of the entire image is obtained (step S5).
7) Repeat while changing slices (step S5)
8).

More specifically, with reference to FIG. 17, the operation of the narrow search area motion vector search section 210 is as follows. At the start of processing the image to be processed,
It is assumed that one or more slices to be processed for obtaining a reference vector from within an image to be processed are set. As an example, three slices near the top, near the center, and near the bottom of the image are to be processed. It is also assumed that slice 26 in FIG. 17 is set as the slice to be processed first. In steps S51 to S56, motion vectors are obtained for all the templates included in the slice. For simplicity, only two templates are included in each slice (see FIG. 17). Slice 26 includes only templates 27 and 28).

First, the narrow search area motion vector search section 210 searches for the template to be searched in the set slice 26 (here, two templates 27 and 28).
Of the end template 27, the shifted search area (for example, an area corresponding to the search area 14 in FIG. 14)
Is set (step S51). Next, a motion vector is obtained by comparing the set search area with the template 27 (step S52). Slice 2 being processed
It is determined whether or not the search for the search areas set with the same shift amount has been completed for all the search target templates 27 and 28 in 6 (step S53). If the search has not been completed, the template 28 is changed to the next template 28, and a search area having the same shift amount (for example, an area corresponding to the search area 14 in FIG. 14) is set for this template 28 (step S5).
4) Return to step S52. Two templates 2
When the search for the search areas having the same shift amount is completed for steps 7 and 28 (step S53: YES), all search areas (for example, the four search areas 14, 15, 16, and
It is determined whether or not the search of the search area 12) of a wide range including 17 has been completed (step S55). If all the search areas have not been searched, among the templates to be searched in the slice 26, the search areas having different shift amounts (for example, the search area 15 in FIG.
Is set (step S56), and the process returns to step S52. When the search in all search areas is completed for all the templates to be searched in the slice (step S55), a wide search area (an area corresponding to reference numeral 12 in FIG. 14) is obtained for each template to be searched. Is obtained. Next, it is determined whether or not the processing of all the slices set in advance for obtaining the reference vector has been completed, thereby determining whether or not the reference vector can be obtained (step S5).
7). When there is an unprocessed slice (step S5
7) An unprocessed slice that is a preset slice is selected (step S58), and the process returns to step S52. The method of calculating the reference vector in step S57 when the processing of a predetermined number of slices is completed is the same as the method described in step S32 of FIG. The reference vector is obtained as described above.

When the reference vector indicating the motion of the entire image is obtained, a narrow area centered on the reference vector is individually described in detail for all the templates in the image including the template group for obtaining the reference vector. A search is performed to determine a displacement vector from the reference vector for each template (step S59). When the displacement vector is obtained for each template, the reference vector and the displacement vector are added, and the result is set as the motion vector of each template (step S6).
0). Steps S59 and S60 are the same as step S of FIG.
This is the same processing as in steps 2 and 3.

Although there is a difference between the processing units, steps S51 to S58 are the specific processing contents of step S1 in FIG. Also, in the above-described 1-2 embodiment, the motion vector search device 100 performs steps S51 to S51.
Using S58, steps S11, S12, and S in FIG.
In each of the thirteenth steps, processing for obtaining the motion vectors V1, V2, and V3 may be performed. In the present embodiment,
Although it has been described that the movement vectors of all the templates included in the slice set for obtaining the reference vector are obtained, the present invention is not limited to this. For example, a part of templates in a slice and only continuous templates may be processed.
Also in this case, efficient memory access can be performed in the search for the motion vector.

Of course, the present invention can be used in combination with the fourth prior art. For example, by analyzing the distribution of motion vectors of previously searched images, a first reference vector indicating the motion of the entire image is predicted, and at the same time, a second target indicating the motion of the entire image is searched for the image to be searched according to the present invention. Find the reference vector. Next, for all the templates in the image to be searched, a narrow area centered on the first reference vector and a narrow area centered on the second reference vector are individually searched for in detail. Is the first that minimizes
Or a displacement vector from the second reference vector. Although the cost of obtaining the displacement vector is doubled, a more accurate motion vector can be obtained.

According to the present invention described in the first to the first to sixth embodiments, the search range is expanded without causing an increase in the cost of the motion vector search device, and the motion vector search device within the expanded search range is provided. There is an effect that the movement can always be detected if it is a movement. Further, even if the full search method, which is the first prior art, which is said to have the highest search accuracy, is not able to avoid erroneous detection. When the search is performed with a wide range, the variation of the motion vector becomes large due to the erroneous detection. Therefore, when the reference vector indicating the motion of the entire image is detected as in the present invention and only the surrounding area is searched in detail, variation in the motion vector due to erroneous detection is suppressed, and as a result, the image quality is improved. .

Next, an embodiment of the present invention relating to the above-described second motion vector search method and apparatus will be described with reference to the drawings.

[2-1 Embodiment] FIG. 18 is a block diagram showing an embodiment of the present invention relating to a second motion vector device. The motion vector search device 100 according to the present invention includes a motion vector search unit 130 that can shift a search area and search for an area having a certain area. The motion vector search unit 130 evaluates the motion of a certain number of templates (hereinafter, referred to as a template group) by a preset evaluation function by the motion evaluation unit 131 of the entire template group. If it is detected, the search area shift unit 132 shifts the search area of the template group to be searched next according to the movement. Hereinafter, this shift amount is referred to as a reference vector. The configuration of the motion vector device shown in FIG. 18 is common to all the following embodiments.

FIG. 19 shows an example in which one slice is used as the template group. One slice includes ten templates, and the motion of the slice 140 is obtained by analyzing ten motion vectors, and the search area of the slice 141 is shifted using the motion as a reference vector. As an example of such an evaluation function, for example, when the sum of absolute difference values used as a reference for obtaining each motion vector of the template group is equal to or less than a preset threshold value, A function that outputs a vector as the motion of the entire template group can be considered.

In the example shown in FIG.
The motion vector of the template is motion vector 14
2 and a motion vector 143. The number of appearances of the motion vector 142 is seven and the number of appearances of the motion vector 143 is three. In this case, the motion vector 142 is output as the motion 144 of the slice 140. In this example, the case where only two types of motion vectors exist is shown. However, since the size of each motion vector is usually slightly different, it is necessary to analyze the distribution by means such as taking a histogram. Become.

FIG. 20 is a flowchart showing a process according to the 2-1 embodiment. First, a predetermined reference vector, for example, a reference vector = (0,0) is set (step S110), and a motion search is started in a search area centered on a block with a motion vector = (0,0) (step S110).
111), the motion of the entire template group detected by the evaluation function is set as a reference vector of the next template group (step S113). Thereafter, until the search for the last template group in the entire image sequence is completed (step S112), a motion vector search is performed using the detected motion of the entire template group as a reference vector for the next template group.

The flowchart shown in FIG. 20 will be described in more detail as follows. First, the motion vector search unit 130 sets a predetermined reference vector, for example, a reference vector = (0, 0) (step S110). Next, in step S111, the motion vector search unit 130 performs a process on the topmost (first) template group in the first image included in the image sequence. That is, the motion vector search unit 130 searches for a motion vector of each template of the template group. This processing will be described in time series as follows. 1) First, the motion vector search unit 130 selects the first template (for example, the leftmost template) in the template group as a processing target. 2) Next, the search area shift unit 132 sets a search area for the selected template using the currently set reference vector as a shift amount. 3) The motion vector search unit 130 obtains a motion vector (displacement vector) in the set search area for the processing target template. 4) The motion vector search unit 130 obtains an actual motion vector of the template by adding the displacement vector obtained for the processing target template and the current reference vector. 5) The motion vector search unit 130 determines whether all templates in the template group have been processed. If the processing has been completed, the process proceeds to step S112. If not, the next template in the template group (the template on the right of the processed template) is selected, and the process returns to 2). As described above, step S111
Is performed.

When the processing of step S111 is completed, the motion vector search unit 130 determines whether the processing of the template group at the bottom of the last image in the image sequence has been completed (step S112), and When the processing of the template group ends, the processing ends. Otherwise, the motion evaluation unit 13 for the entire template group
In step 1, a motion vector of the entire template group detected by the evaluation function described with reference to FIG. 19 is obtained by using the motion vectors of the template group obtained in step S111.
Also, the motion estimation unit 131 for the entire template group sets the motion vector for the entire template group as a reference vector for the next template group (step S113), and proceeds to step S111. Next, in step S111, the motion vector search unit 130 performs a process on the next topmost template group in the first image included in the image sequence. Note that the order of processing of the template group is from left to right and from top to bottom of the image to be processed in consideration of memory access efficiency when processing according to international standards such as MPEG. . As described above, the motion vector search device uses the motion vector (reference vector) of the entire template group when searching for a motion vector of each template of the next template group. In the present embodiment, as described above, when searching for individual templates included in the template group (step S111), the actual motion vector of the template (the “reference” in the above-described 1-1 embodiment and the like) is used. Vector + transition vector), and from these actual motion vectors, a reference vector indicating the motion of the entire template group is calculated. This point is the second
The same applies to the second to second to fifth embodiments.

[2-2] Second Embodiment In the above-mentioned 2-1 embodiment, even if the motion of an image suddenly changes due to a scene change or the like, the reference vector cannot be changed correspondingly. The search for an area different from that of the movement is continued. Therefore, in the second embodiment, when the motion of the entire template group can be detected, not only the motion of the entire template group is output, but when the motion cannot be detected, the “motion detected Use an evaluation function that outputs "cannot do".
Here, “when motion can be detected” includes no motion, that is, a case where motion vector = (0, 0) is detected, and “when motion cannot be detected” includes This means that there is no block that matches the template.

As an example of such an evaluation function, for example, when all the sums of absolute differences, which are references for obtaining each motion vector of the template group, are equal to or less than a preset threshold value, A function that outputs a motion vector as the motion of the entire template group, and outputs “not detect motion” when there is at least one template whose sum of absolute differences of the motion vectors is equal to or greater than a threshold value is considered. It is.

In the 2-2 embodiment, when the movement of the template group cannot be detected, the shift of the search area is reset in the search for the next template group, and a predetermined reference vector, for example, reference vector = (0, 0) is set.

FIG. 21 is a flowchart showing a process according to the 2-2 embodiment. First, a predetermined reference vector, for example, a reference vector = (0,0) is set (step S120), and a motion search is started in a search area centered on a block with a motion vector = (0,0) (step S120).
121), while the motion cannot be detected, the motion vector =
A search is performed in a search area centered on the block (0,0). When the motion of the entire template group is detected by the evaluation function (step S123), the motion is set as a reference vector of the next template group (step S12).
4). Thereafter, until the search for the last template group in the entire image sequence is completed (step S122).
When a motion can be detected, the reference vector of the next template group is used as the reference vector. When no motion is detected, the reference vector of the next template group is reset to (0, 0), and the search for the motion vector is performed. Do.

As can be seen by comparing FIGS. 21 and 20, steps S120 to S122 and S124 correspond to steps S110 to S113, respectively. In the present embodiment, step S123 is newly added to FIG. In step S123, the motion evaluator 131 for the entire template group makes a determination based on the above-described evaluation function.

[2-3 Embodiment] In the 2-3 embodiment of the present invention, when the movement of the template group cannot be detected, the template group which can detect the movement from the next template group appears. The reference vector is changed for each template group to search for motion vectors in different ranges. Therefore, by performing a motion search on a plurality of template groups, a motion vector can be detected in a wide range.

FIG. 22 is a flowchart showing processing according to the second to third embodiments. First, a predetermined reference vector, for example, a reference vector = (0,0) is set (step S130), and a motion search is started in a search area centered on a block with a motion vector = (0,0) (step S131). ), When the movement of the entire template group is detected (step S133), the movement is set as a reference vector of the next template group (step S134).

If no motion can be detected, the reference vector of the next template group is changed to a reference vector other than (0, 0) = (x1, y1) in accordance with a preset rule (step S136). Search for the template group vector. When the motion of the entire template group is detected by this search, the motion is used as a reference vector of the next template group. If the motion cannot be detected again, the reference vector of the next template group is changed to a reference vector other than (0, 0) and (x1, y1) = (x2, y2) according to a preset rule, and the search is performed. .
If the processed template group is the last template group in the image currently being processed (step S13)
5) Return to step S130, and reset the reference vector of the template group to be processed first in the image to be processed next to (0, 0).

The above processing is repeated until the search for the last template group in the entire image sequence (step S132).

As can be seen by comparing FIG. 22 and FIG. 21, steps S130 to S134 correspond to steps S120 to S124, respectively. In this embodiment, steps S135 and S136 are newly added to FIG. In step S135, the motion vector search unit 130 determines whether or not the current template is the last template group in the image currently being processed.
If it is the last, the process returns to step S130 to process the next image in the image sequence. On the other hand, if it is not the last, in step S135, the motion vector search unit 130 sets a different reference vector according to the rule described above.

[2-4 Embodiment] In the 2-4 embodiment of the present invention, first, a different reference group is used for a template group at an appropriate position for detecting the movement of the entire image such as the center of the image. A search is performed a plurality of times by setting a vector, and a motion vector is detected in a wide range.
If a motion vector can be detected, it is searched as a reference vector. When the movement of the template group cannot be detected, a predetermined reference vector, for example, a reference vector = (0, 0) is set and a search is performed.

Thereafter, while the motion of the entire template group can be detected, the search is continued using the detected motion as a reference vector of the next template group. If it is not possible to detect the movement of the entire template group and proceed to the processing of the next image, before starting the search for the next image, set an appropriate position for detecting the movement of the entire image, such as the center of the next image. For the template group, a different reference vector is set and a plurality of searches are performed to detect a motion vector in a wide range, and use that as the initial value of the reference vector in the next image.

FIG. 23 is a flowchart showing processing according to the second to fourth embodiments. First, a non-detectable bit for storing that the motion of the entire template group could not be detected in the image to be processed in the image sequence is initialized to 0 (step S14).
0). Next, for a template group at a position suitable for detecting the movement of the entire image such as the center of the image, a different reference vector is set and a plurality of searches are performed to detect a motion vector in a wide range (step S141). The search for the motion vector of the entire template group is almost the same as the repetition of steps S120 and S121 in FIG. However, the difference is that different reference vectors are sequentially set in accordance with a predetermined rule in the processing corresponding to step S120, and that the position of the template group is sequentially changed in the processing corresponding to step S121.

When a motion vector is detected by this search (step S142), the motion is set as a reference vector (step S143), and the search is started (step S145). If a motion vector of the entire template group at an appropriate position cannot be detected, a predetermined reference vector, for example, a reference vector = (0, 0) is set, and a non-detectable bit is set to 1 (step S144). A search for a motion vector of the template group is started (step S145). Note that the determination in step S142 is based on FIG.
This is the same as Step S123 of Step 1. Step S
In 140 to S144, the processing in step S142 is performed by the motion estimating unit 131 for the entire template group.
The setting of the search area in steps S143 and S144 is performed by the search area shift unit 132. Further, other processing is performed by the motion vector search unit 130.

Until the search for the last template group in the entire image sequence is completed, or until the search for the last template group in the image is completed (steps S146 and S1).
47), while the motion of the entire template group can be detected (step S148), the detected motion is used as a reference vector of the next template group (step S149). If the entire template group cannot be detected,
A predetermined reference vector is set, the undetectable bit is set to 1 (step S150), and a search for a motion vector of the template group is performed (step S145).

If the last template group in the image has been searched (step S147), it is determined whether the undetectable bit is 1 (step S151). If the undetectable bit is 1, the flow returns to step S140. The same process is repeated for the next image. If the undetectable bit is 0, it is determined whether or not the motion of the entire template group has been detected (step S152). If the motion has been detected, the motion detected as the reference vector is set in step S153, and the motion vector The search is continued (step S145). If the movement of the entire template group cannot be detected, the process returns to step S140.

The above processing is repeated until the search for the last template group in the entire image sequence is completed, and when the last template group has been searched, the processing is terminated (step S146).

As can be seen by comparing FIGS. 23 and 22, steps S145 and S146 correspond to steps S131 and S132, respectively. Step S
148 and S149 are steps S133 and S1 respectively.
Steps S152 and S1153 also correspond to steps S133 and S134, respectively. And
Steps S147 and S150 are respectively performed in step S1.
35 and S136. However, step S150
Also includes processing for undetectable bits. Then, in the present embodiment, the processing of the portion corresponding to step S130 in FIG. 22 is steps S140 to S144. Here, if the motion of the entire template group cannot be detected in any of the template groups in the image to be processed immediately before, the continuity of the template motion between the images is low, and the image to be processed in the future It is inappropriate to set the reference vector detected immediately before.
Therefore, the motion vector search unit 130 determines in step S14
In steps 0 to S144, an initial reference vector is obtained using a part of the image to be processed, and is set. On the other hand, when the movement of the entire template group can be detected in all the template groups in the image to be processed immediately before, it is considered that the movement of the template between the images has continuity. Therefore, in step S153, the motion vector search unit 130 sets the detected reference vector as the initial value of the reference vector of the image to be processed. The process for each template group of the image to be processed is performed in step S145.
This is performed in steps S153 to S153.

In step S141, the vicinity of the center of the image to be processed is shown as an example of a template group at an appropriate position. When the motion vector of the entire image is obtained, the vicinity of the center of the image is considered to be the most representative motion, but is not limited thereto. For example, the template group at an appropriate position in step S141 may be the leftmost template group (the first template group in the image) included in the uppermost slice of the image to be processed. In this case, by calculating the motion vector of each template in the template group in step S141,
In step S145, the motion vector search unit 130 can set the first template group to be processed as the template group next to the template group processed in step S141. In this case, the processing speed can be shortened, and the memory access can be performed more efficiently.

In order to reflect the processing result of the immediately preceding image while simplifying the processing, steps S141 to S141 are executed.
S143 may be omitted, and step S144 may be performed only by setting a predetermined reference vector.

[2-5th Embodiment] The 2nd to 5th embodiments of the present invention correspond to the above-mentioned 2-1 to 2nd embodiments.
In the embodiments up to -4, all templates in the same slice are included in the same template group. That is, the template group in this embodiment is configured by one or more slices.

If the template belonging to the same slice is allowed to be included in a different template group, unlike the present embodiment, the fifth conventional technique cannot be used for switching the template group, and the pixel in the search area is not changed. Extra transfer is required. FIG. 24 shows an example thereof.
This will be described with reference to FIG.

In the example of FIG. 24, the left half template and the right half template in one slice are included in different template groups, and the template group 150 to which the left half template belongs and the template group to which the right half template belongs 151, the reference vector is different. Assuming that the reference vectors of the template group 150 to which the left half template belongs and the template group 151 to which the right half template belongs are vector 153 and vector 156, respectively, the search area of the last template 152 in the template group 150 and the first in the template group 151 Are the search area 154 and the search area 157, respectively. If the two search areas are shifted as described above, the fifth conventional technique cannot be used, and almost all the pixels in the search area 157 are transferred from the image memory 24 to the search area memory 23 described with reference to FIG. The extra pixel transfer is required.

In the second to fifth embodiments, all the templates in the same slice are included in the same template group, so that the above-described extra pixel transfer can be omitted.

Here, in the image coding system which is an international standard such as MPEG1 or MPEG2, coding is performed in order from left to right and from top to bottom of the screen. From the viewpoint of manufacturing a device conforming to these encoding systems, FIG.
It is preferable that the slice direction is the horizontal direction as shown in FIG.

[2nd Embodiment] In the 2-6 embodiment, when the motion of the entire template group can be detected, the detected motion is set as a reference vector, and the motion of the entire template group is detected. If not, the reference vector is changed for each template group to search for a different range of motion vectors until a template group capable of detecting a motion appears from the next template group. However, before performing the motion search for the next template group, the motion vector distribution of the previously encoded image is analyzed to predict the motion of the next template group. Then, it is determined whether or not the predicted motion is likely to be correct. If the predicted motion is high, the reference vector is changed to the predicted motion. As a method for determining whether or not the prediction is correct, for example, the motions of all the detected template groups on the screen on which motion is currently detected and the motions of the corresponding template groups on the screen on which the motion was detected immediately before are detected. May be determined to be correct when 一致 coincides with each other, and the prediction may be erroneous when there is at least one template group having a different motion.

FIG. 25 is a flowchart showing the processing according to this embodiment. First, the motion vector detection unit 130
Is a predetermined reference vector, for example, reference vector =
(0, 0) is set (step S161). Next, the motion vector detection unit 130 analyzes the distribution of the motion vectors of the previously coded images before performing the motion search of the template group, except for the templates included in the image to be initially searched for motion in the image sequence. Then, the motion of the template group is predicted (step S162). The prediction method is as described above. Then, the motion vector detecting unit 130
Determines whether the motion predicted by the above-described method is likely to be correct (step S163), and if the probability is high, changes the reference vector to the predicted motion (step S164). Here, a motion vector searched in the past does not exist in an image on which a motion search is performed first. For this reason, the motion vector detection unit 130 determines that the motion predicted from the past motion vector distribution is an error,
Skip 4 Next, the motion vector detection unit 130
Sets and searches a narrow search area centered on the reference vector for each template included in the template group, and obtains a displacement vector within the search area (step S165). Then, the motion vector detecting unit 1
30 calculates the sum of the reference vector and the obtained displacement vector to obtain the motion vector of each template in the template group (step S166). Next, the motion vector detection unit 130 determines whether the processed template group is the last template group in the last image of the image sequence (step S167), and ends the processing if it is the last. If it is not the last, the entire template group motion estimating unit 131 detects the motion of the entire template group from the motion vector of each template obtained in step S166 by the method described above (step S168). At this time, in order to analyze the motion vector in S162, the motion evaluation unit 1 of the entire template group
Numeral 31 stores the detected motion vector in a memory (not shown) in association with the position of the template group.

If the motion of the entire template group has been detected in step S168, the motion vector
A value of 0 sets the motion as a reference vector of the next template group (step S170), and proceeds to step S162. If the motion cannot be detected, the motion vector detection unit 130 sets a reference vector (x1, y1) other than the reference vectors set up to now according to a preset rule for a reference vector of the next template group (step S1). S171), and proceeds to step S162. In this step, when the motion cannot be detected again, the reference vectors of the next template group are set in accordance with the preset rules in accordance with the previously set reference vectors (0, 0),
A reference vector (x2, y2) other than (x1, y1) is set. When the processing of the last template group in the currently processed screen is completed (step S16)
9), the motion vector detection unit 130 determines in step S161
To the processing of the next image in the image sequence.

Here, comparing FIG. 25 with FIG. 22, step S161 corresponds to step S130. Steps S165 and S166 are processes included in step S131. Steps S167 to S171 correspond to steps S132 to S136, respectively. FIG. 25 and FIG.
The difference lies in steps S162 to S164. With these steps, the motion vector detection unit 130 can set a reference vector that reflects the distribution of motion vectors of previously encoded images.

Specifically, the following effects can be obtained. For example, the train is moving in the lower half of the screen,
When the upper half is the background, the movement between the background and the train is different. Therefore, simply using the motion of the immediately preceding template group as the reference vector of the next template group cannot detect the motion vector of the template included in the template group at the boundary between the background and the train well. In the present embodiment, the reference vector is set using the reference vector predicted from the motion vector distribution of the image encoded in the past (steps S162 to S164).
An appropriate reference vector can be set for the template group at the boundary between the background and the train. As a result, the motion vector of each template can be accurately detected.

Also in this embodiment, as described in the second to fifth embodiments, by including all templates in the same slice in the same template group, efficient memory access can be achieved. And processing can be performed.

[Embodiment 2-7] In the present embodiment, a motion vector detecting device which can also perform a telescopic search in the motion vector searching device described above will be described. First, the telescopic search will be described.

In image coding, there is a case where a motion vector of an image several frames earlier in time is obtained. In such a case, there is a method of repeatedly obtaining a motion vector for an adjacent image, using that as an initial value to obtain a motion vector for the next adjacent image, and obtaining a motion vector between temporally separated images. This method is called a telescopic search method. Since the movement of the adjacent image is small, by using this method, the movement can be detected by searching in a narrower range than in the case of directly searching between distant images. This telescopic search method will be described with reference to the schematic diagram of FIG. Images 204, 205, and 206 in FIG. 26 are three images that are temporally continuous. The image 206 is the current image, and the image 205 and the image 204 are each 1
The image before the screen and the image two screens before. Rectangular block 201
Is the motion vector m between the image 204 and the image 205
v2, and similarly, the image 205 and the image 206
Are moving with a motion vector mv1 between the two. At this time, the rectangular block 201 from the image 206 to the image 204
Is (mv1 + mv2).

In the telescopic search method, to obtain a motion vector from the image 206 to the image 205, the image 2
First, a region 202 in the image 205 is searched using the rectangular block 201 in
v1 is detected. At this time, the motion vector at the center of the area 202 is (0, 0). Next, the motion vector mv2 is detected by searching the area 202 in the image 204. Considering the motion vector from the image 206 to the image 205 of the rectangular block 201, the motion vector at the center of the area 202 in the image 204 is mv1. Here, the vector mv1
Are defined as mv1 _x and mv1 _y , respectively. The possible ranges of these components are-
a ≦ mv1 _x ≦ a, and -b ≦ mv1 _y ≦ b. Similarly, the horizontal component and the vertical component of the vector mv2 are respectively represented by mv2 _x
If the mv2 _y, the possible range of these components, respectively -a ≦ mv2 _x ≦ a, and -b ≦ mv2 _y ≦ b. In this case, the motion range of possible vector (mv1 + mv2), _{respectively, -2a ≦ mv1 x + mv2 x} ≦ 2a, -2
b ≦ mv1 _y + mv2 _y ≦ 2b. That is, in the telescopic search, as the distance between the images increases, the range that the motion vector can take, in other words, the area that may be referred to by the search, increases. Looking at this in FIG. 26, the area that may be referred to by the search in the image 205 one image away from the image 206 is the area 202, and may be referred to by the search in the image 204 two images away from the image 206 The region having the property is the region 203. A method combining the above-described telescopic search method and the above-described second conventional technique is described in, for example, “K. Suguri, T. Min.
ami, H.Matuda, R.Kusaba, T.Kondo, R.Kasai, T.watanabe,
H.Sato, N.Shibata, Y.Tashiro, T.Izuoka, A.Shimiz, H.Kot
era, “A real-time motion estimation and compensati
on LSI with wide search range for MPEG2 video enco
ding ", IEEE J. Solid-State Circuits, vol. 31, no. 11, p
p. 1733-1741, Nov. 1996 ".

In the present embodiment, the above-mentioned 2-1 to 2-6
In each of the embodiments described above, an area that may be referred to by the search is read into a search area memory (not shown) in the motion vector search apparatus shown in FIG. For example, in the case of the above-described telescopic search, the area 202 on the screen 205 and the area 203 on the screen 204 in FIG. 26 are read into the search area memory. In each of the above embodiments 2-1 to 2-6, assuming that only an area to be actually searched is read into a search area memory (not shown) in the motion vector search apparatus.
In the motion vector search device described in each embodiment, the telescopic search could not be applied. Therefore,
The motion vector search device described in each of the embodiments reads an area that may be referred to by search into a search area memory in the device, so that there is a possibility that a motion vector exists like a telescopic method. Although a certain range is wide, it is possible to cope with a search method in which an actual search is limited to an area where a motion vector is likely to exist.

As described above, the motion vector search method and apparatus according to the present invention expand the search range without causing an increase in the cost of the motion vector search apparatus, and use the motion within the expanded search range. This has the effect that the movement can always be detected, and the shift amount of the search area can be corrected by reflecting the search result of a part of the image. Further, even if the full search method, which is the first prior art, which is said to have the highest search accuracy, is not able to avoid erroneous detection, and to improve the image quality of images with large motion, When the search is performed with a wide range, the variation of the motion vector increases due to the erroneous detection. Therefore, as in the present invention, when the motion of a certain number of templates as a whole is evaluated and the search area of the next group of templates to be searched is shifted in detail in accordance with the motion of the certain number of templates, an error occurs. Variations in motion vectors due to detection are suppressed, and as a result, there is an effect that image quality is improved.

The above embodiments (1-1 to 1-
Embodiment 6 and Embodiments 2-1 to 2-7)
In, the search procedure for each motion vector is stored as a program in a recording medium, and the computer can read and execute the program to realize the procedure. Here, the “computer system” includes an OS and hardware such as peripheral devices. The “computer-readable recording medium” includes a floppy disk, a magneto-optical disk, a ROM,
It refers to a portable medium such as a D-ROM or a storage device such as a hard disk built in a computer system. Further, a "computer-readable recording medium" refers to a communication line for transmitting a program via a network such as the Internet or a communication line such as a telephone line, and dynamically holds the program for a short time. In this case, a medium that stores a program for a certain period of time, such as a volatile memory in a computer system serving as a server or a client in that case, is also included. Further, the program may be for realizing a part of the functions described above. Furthermore, what can implement | achieve the function mentioned above in combination with the program already recorded on the computer system, and what is called a difference file (difference program) may be sufficient. Of course, the present invention can also be realized by manufacturing a semiconductor device that performs the above-described processing and performing the processing only with hardware.

The embodiment of the present invention has been described in detail with reference to the drawings. However, the specific configuration is not limited to this embodiment, and includes a design and the like without departing from the gist of the present invention. It is.

[0140]

As described above, the 2-1st to the 2nd
The present invention described in the -7 embodiment can expand the search range without causing an increase in the cost of the motion vector search device, and can always detect the motion if the motion is within the expanded search range, Further, there is an effect that the shift amount of the search area can be corrected by reflecting the search result of a part of the image.

Further, even if the first prior art full search method, which is said to be the highest in search accuracy, is used, erroneous detection cannot be avoided and the quality of images with large motion is improved. If the search is performed with a wider search range, the variation of the motion vector increases due to erroneous detection. Therefore, as in the present invention, when the motion of a certain number of templates as a whole is evaluated and the search area of the next group of templates to be searched is shifted in detail in accordance with the motion of the certain number of templates, an error occurs. Variations in motion vectors due to detection are suppressed, and as a result, there is an effect that image quality is improved.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration example of a motion vector search device according to embodiments 1-1, 1-2, 1-3, and 1-4 of the first invention;

FIG. 2 is a flowchart illustrating a process according to the first embodiment.

FIG. 3 is a diagram for explaining a 1-2 embodiment.

FIG. 4 is a flowchart illustrating a process according to the first embodiment.

FIG. 5 is a flowchart illustrating a process according to the first to third embodiments.

FIG. 6 is a flowchart illustrating processing according to the first to fourth embodiments.

FIG. 7 is a block diagram illustrating a configuration example of a motion vector search device according to the first to fifth and first to sixth embodiments of the first invention.

FIG. 8 is a flowchart illustrating processing according to the first to fifth embodiments.

FIG. 9 is a schematic explanatory diagram of the first to fifth embodiments.

FIG. 10 is a flowchart illustrating a process according to the first to sixth embodiments.

FIG. 11 is a schematic explanatory diagram of a conventional technique.

FIG. 12 is a schematic explanatory view of a conventional technique.

FIG. 13 is a schematic explanatory diagram of a conventional technique.

FIG. 14 is a schematic explanatory diagram of a conventional technique.

FIG. 15 is a schematic explanatory view of a conventional technique.

FIG. 16 is a diagram showing a configuration of a typical motion vector search device of the related art.

FIG. 17 is a schematic explanatory view of a conventional technique.

FIG. 18 is a configuration diagram of a motion vector search device according to the present invention.

FIG. 19 is a schematic explanatory view of the present invention.

FIG. 20 is a flowchart illustrating a process according to the embodiment 2-1.

FIG. 21 is a flowchart illustrating a process according to the second embodiment.

FIG. 22 is a flowchart illustrating processing according to the second to third embodiments.

FIG. 23 is a flowchart illustrating processing according to the second to fourth embodiments.

FIG. 24 is a schematic explanatory diagram of the second to fifth embodiments.

FIG. 25 is a schematic explanatory diagram of the second to sixth embodiments.

FIG. 26 is a diagram for explaining a telescopic search.

[Explanation of symbols]

 24 Image memory 100 Motion vector search device 110 Motion vector search unit for wide search area 120 Motion vector search unit for narrow search area 200 Motion vector search device 210 Motion vector search unit for narrow search area 131 Motion estimation unit for entire template group 132 Search Area shift unit

──────────────────────────────────────────────────の Continuing on the front page (72) Inventor Takeshi Kentome 3-19-2 Nishi-Shinjuku, Shinjuku-ku, Tokyo Nippon Telegraph and Telephone Corporation (72) Inventor Takeshi Ogura 3--19, Nishishinjuku, Shinjuku-ku, Tokyo No. 2 Nippon Telegraph and Telephone Corporation Examiner Michiharu Sugawara (56) References JP-A-4-3595 (JP, A) JP-A-9-212649 (JP, A) JP-A-3-129984 (JP, A) N.). Hayashi, T .; Kiti, I .; Tamitani, H .; Hon ma, Y .; Ooi, T. (58) Fields investigated (Int. Cl. ⁷ , DB name) H04N ^7/ 24-7/68

Claims (9)

(57) [Claims] 1. A motion vector search method for searching for a region having a fixed area by shifting a region that may be referred to by a search, wherein the setting is performed for each template in a template group including a fixed number of templates. By searching the search area shifted by the shifted reference vector ,
A displacement vector is obtained, and the displacement vector and the reference vector are determined.
The actual behavior of each template by adding
Vector in the template group
The motion of the entire template group is evaluated using the actual motion vectors of the number of templates, and when the motion of the entire template group can be detected, the motion is output, and the motion cannot be detected. A first step of outputting that no motion can be detected, and when a motion of the entire template group can be detected, the motion is set as a reference vector of a template group to be searched next. The second step to return, and when the movement of the entire template group cannot be detected,
A third step of setting a predetermined vector as a reference vector of a template group to be searched next and returning to the first step. 2. In the third step, when the motion of the entire template group cannot be detected, the shift of the search area is reset in the search of the template group to be searched next, and the block at the center of the search area is reset. motion vector search method according to claim 1, characterized in that the block indicated by the motion vector. 3. In the third step, when the movement of the entire template group cannot be detected,
A method of changing a reference vector indicating a shift of a search area for each template group and searching for a different range of motion vectors until a template group capable of detecting a motion appears from a template group to be searched next. Item 6. The motion vector search method according to Item 1 . 4. The method according to claim 1, wherein, before the search for the first image is started, the search area is shifted to a different position with respect to a group of templates at positions suitable for detecting the motion of the entire image in the first image. The search is performed multiple times, and the motion of the entire image is detected in a wide range. When the motion can be detected, the search area of the first template group is shifted according to the motion, and the motion cannot be detected. The method further comprises the step of shifting the search area of the first template group by a predetermined reference vector. In the third step, when the motion of the entire template group cannot be detected, A predetermined reference vector is set up to a template group that can detect the template or up to the last template group of the image containing the template group Before starting the search for the next image, perform a search multiple times by shifting the search area to a different position for a template group at an appropriate position for detecting the motion of the entire image in the next image. It is executed, by detecting the motion of the entire image in a wide range, a motion vector search method according to claim 1, wherein the shifting the search area of the first template group of the next image in accordance with the movement thereof. 5. In the second step, when a movement of the entire template group can be detected, the movement and a movement on a screen searched in the past are used.
Next, the shift of the search area of the template group to be searched is determined and shifted. In the third step, when the movement of the entire template group cannot be detected,
By using the movement in the set movement and searched in the past the screen, then a motion vector search method according to claim 1, characterized in that the determination and shift the shift of the search area of the template group to be searched. 6. In the first step, when at least one template that does not include a block that matches the template is detected in the search area of each template, the motion of the entire template group cannot be detected in the step. The motion vector search method according to any one of claims 2 to 5 , wherein the information is output. 7. The method according to claim 1, wherein all templates in the same slice are included in the same template group.
The motion vector search method according to any one of claims 2 to 6 . 8. A motion vector searching apparatus for shifting a search area to search for an area having a certain area, wherein the search is shifted by a reference vector set for each template in a template group including a certain number of templates. By searching the area ,
A displacement vector is obtained, and the displacement vector and the reference vector are determined.
The actual behavior of each template by adding
Vector in the template group
The motion of the entire template group is evaluated using the actual motion vectors of the number of templates, and when the motion of the entire template group can be detected, the motion is output, and the motion cannot be detected. When the first processing unit outputs that no motion can be detected, and when the motion of the entire template group can be detected, the motion is set as a reference vector of a template group to be searched next. A second processing unit that shifts the processing to the unit, and when the movement of the entire template group cannot be detected,
A motion vector search device comprising: a third processing unit that sets a predetermined vector as a reference vector of a template group to be searched next and shifts processing to a first processing unit. 9. A computer-readable recording medium which stores a motion vector search program for causing a computer to execute a motion vector search method for shifting a search area to search for an area having a certain area, comprising: from consisting only reference vector set for each template in the template group of each template by searching the shifted search region
A displacement vector is obtained, and the displacement vector and the reference vector are determined.
The actual behavior of each template by adding
Vector in the template group
The motion of the entire template group is evaluated using the actual motion vectors of the number of templates, and when the motion of the entire template group can be detected, the motion is output, and the motion cannot be detected. When the first process outputs that motion cannot be detected, and when the motion of the entire template group can be detected, the motion is set as a reference vector of the template group to be searched next, and the first process is performed. The second process of returning and the third process of setting a predetermined vector as a reference vector of the next template group to be searched when the movement of the entire template group cannot be detected and returning to the first step are performed by computer. Recording medium on which a motion vector search program to be executed is recorded.