JPH0793728B2 - Motion vector detector - Google Patents

Description

The present invention relates to a motion vector detecting device used in a moving image interframe coding device, and more particularly to expanding a search area by using a plurality of basic arithmetic units. The present invention relates to a suitable motion vector detection device.

[Conventional technology]

In videophones and the like, there is an example in which a motion vector is detected in order to reduce the amount of image transmission. What is a motion vector?
Between the current screen and the previous screen, the motion between the screens is obtained as a vector.

Specifically, the detection block a (M × M pixels) is set on the current screen, and the search range b (N ×
N pixels) is set. The search range is larger than the detection block and N> M. The entire search range is scanned with a search block having the same capacity as the detection block. Evaluation data D _ij is obtained between the detection block and each search block. The evaluation data D _ij is obtained by taking the difference in pixel data for each corresponding pixel between the detection block and the search block, and cumulatively adding (summing) the absolute value of all the pixels of the block. The evaluation data is obtained by the number (N−M + 1) of all search blocks included in the search range.

The calculation formula of the evaluation data D _ij is as follows.

In the equation (1), i and j are coordinates (addresses), a is a detection block on the current screen, and b is search block data on the previous screen. The number of the search block is determined by k and l.

The minimum evaluation data is obtained from the N−M + 1 pieces of evaluation data obtained within the search range. The search block given the minimum evaluation data is regarded as the block before the movement of the detection block, and the positional relationship between the detection block and the search block is displayed as a vector. This vector is a motion vector.

The search range is as follows. In the previous screen, at the same position as the detection block and with the same capacity (this
Around the same position block), a range larger than the same position block is taken. This is the search range. Therefore,
The search range may be considered as a movable range of the block. Also, if the detection block is large, the number of calculations is small and it is simple, but the accuracy is lowered, so it cannot be made too large.

[Problems to be Solved by the Invention]

The applicant has applied for a patent as a motion vector detecting device. (Japanese Patent Application No. 1-244454). FIG. 7 shows the configuration of the motion vector calculation unit 101A of the prior application. The arithmetic unit 101A has three input terminals 50 to 52 and one output terminal 61. The control terminal 70 is a terminal for inputting the same position vector selection signal E / C. In FIG. 7, the input switching section 10 selects the input data a, b, b ', and
, B, a, and b'are selectively assigned to the arithmetic circuits 20, 21, and 22. Here, the input data a is the input image block 8 and is the above-mentioned detection block. Although not shown, these may be stored in the current screen data memory and the previous screen data memory, or may be obtained online. The input data b, b ′ are data obtained by dividing the previous screen image block 9 into two, and the previous screen image block 9 is the search range itself.

Further, the reason why it is divided into b and b'is to reduce the number of calculations.

The arithmetic circuits 20, 21, 22 are arithmetic circuits that individually operate the evaluation data.

The output switching unit 30 selects and outputs the evaluation data obtained from the arithmetic circuits 20, 21, and 22.

The minimum value detection unit 40 detects the minimum value of a plurality of evaluation data obtained from the search range. The position (address) of the search block that gives this minimum value becomes the motion vector.

FIG. 8 shows the relationship between the detection block and the search range.
FIG. 8A shows an example of input screen data, which is an example in which this input screen is divided into 6 × 8 blocks. The size of each block is equal to M × M pixels, and each of these blocks becomes a detection block.

FIG. 8B shows an example of previous screen data, which is also equally allocated to blocks as in the input screen. Each block of the previous screen data corresponds to the same-position block of the detection block. A search range N × N pixels is set around the same position block.

FIG. 9 is a diagram showing a detection block and a search range,
The detection block in FIG. 9A is an example in which M = 3. The search range in FIG. 9B is an example in which N = 5.
The search range is divided into a 5 × 3 partial block b on the left side and a 5 × 2 partial block b ′ on the right side, which corresponds to the data b and b ′ in FIG.

FIG. 10 is a diagram showing a calculation process for obtaining evaluation data for the data of FIG. 9 under the configuration of FIG. The clock timing is shown in the vertical direction, the input data is shown in the horizontal direction, and the data flow in the arithmetic circuits 20, 21, 22 (PE1, PE2, PE3) is shown. For example, at clock timings 0 to 8, the data a and b of the detection block of FIG. 9 (a) and the first search block of FIG. 9 (b) (in the shaded area) are fetched. This data a, b
On the other hand, the arithmetic circuit 20 takes the difference between the two each time it takes in the data and converts it into an absolute value. The absolute valued difference is sent to an accumulator (not shown) and accumulated. Thus, at the end of clock timing 8, the evaluation data D ₁₁ between the detection block and the first search block is obtained.

On the other hand, the arithmetic circuit 21 obtains the evaluation data D ₁₂ between the second search block and the detection block, which are obtained by shifting the first search block by 1 pixel to the right, over the clock timings 1 to 9. The arithmetic circuit 22 obtains the evaluation data D ₁₃ between the third search block obtained by shifting the second search block to the right by one pixel and the detection block over the clock timings 2 to 10.

Calculation of other evaluation data is similarly performed according to FIG.

However, there is a demand to expand the search range. Expanding the search range means increasing the number of search blocks with respect to one detection block, resulting in an increase in search time and an increase in calculation time. It is necessary to reconfigure the circuit configuration in accordance with the expanded search range and perform processing of the expanded search range with a small number of circuit points.

An object of the present invention is to provide a motion vector detection device corresponding to a search range expanded by using a plurality of arithmetic units configured for a specific search range.

[Means for Solving the Problems]

The present invention relates to a detection block of size M × M pixels in the input screen and a plurality of size M × M pixels in the search range of size (2M−1) × (2M−1) pixels in the previous screen. And a plurality of calculation units for sequentially comparing the read detection block with a plurality of search blocks to calculate a local motion vector. In the motion vector detection device, the search range is set to the size (2M-1) ×
(2M-1) from the pixel (Q × M-1) × (Q × M-1) the number of the arithmetic unit at the time of expanding the pixel ^{P (P = 2 2, 3} 2,
4 ² , ...) and Q and P are It is a relationship. Further, in the P calculation units, the expanded search range of the previous screen is M (horizontal direction) ×
(2M-1) (vertical direction) divided into sub-regions of pixels and input, and the sub-regions of the P operation units that are adjacent to each other in the horizontal direction are input to two computation units. One small partial area is commonly input.

Further, the search range and the extended search range in the present invention are centered on the same position block at the same position as the detection block.

Further, each of the P arithmetic units in the present invention calculates the upper left position (edge) of the search block at the first clock time, and the spatially same position (center) as the input image block at the mth position. Calculate with clock time (m = (M + 1) × M /
2 + 1), and a means for selecting and outputting the operation result at both clock times by an external signal, and the upper left partial area is the first when the expanded search range is processed by P operation units. The second arithmetic unit processes the right adjacent partial area, the second lower arithmetic section processes the last lower right partial area, and the P-th arithmetic unit processes the last lower partial area.
The calculation result at the m-th clock time is selected for the +1) / 2-th calculation unit to determine the same position vector for the expanded search range. If the value of P is an even number, the n-th calculation result is determined. Regarding the arithmetic unit, the arithmetic result at the first clock time is selected and defined as the same position vector for the expanded search area. I decided to do it.

[Action]

According to the present invention, the number P of arithmetic units having a search range having a size of (2M−1) × (2M−1) pixels and the extended search range (Q
× M−1) × (Q × M−1) Due to this limitation, a quick search within the expanded search range is possible.

Further, according to the present invention, the detection of the same position vector is automatically detected during the search process for the extended search range.

[Embodiment] FIG. 1 is an embodiment of a motion vector detecting device of the present invention. This motion vector detecting device has four calculation units 101 to 10
4. Comprised of an external comparison unit 200.

Each of the arithmetic units 101 to 104 is the three-input arithmetic unit 101A itself shown in FIG. Among the three inputs, the detection block data a is commonly input to each circuit, and the remaining 2
One input is a specific two of the divided data b ₁ , b _{1 ′} , b _{2 ′} , b ₃ , b _{3 ′} , b _{4 ′} of the data b indicating the expanded search range. (B ₁ , b _{1 ′ in} the arithmetic unit 101, b _{1 ′} , b _{2 ′} in the arithmetic unit 102, b ₃ , b _{3 ′} in the arithmetic unit 103, b _{3 ′} , b _{4 ′ in the} arithmetic unit 104 ).

In the arithmetic units 101 to 104, the difference between a, b and b ′ is calculated, and the absolute values of these are accumulated. This cumulative result is the evaluation data. This evaluation data is sent to the external comparison unit 200 as local motion vector information, and the search block that gives the minimum evaluation data is extracted from the terminal 60 as motion vector information.

The arithmetic unit 101 is a combination of all the elements 10, 30, 40, 20 to 22 shown in FIG. The other arithmetic units 102 to 104 are also the same. That is, when the size of the detection block is M × M, the arithmetic units 101 to 104 are circuits having a search range of (2M−1) × (2M−1).

Here, the relationship between the number of arithmetic units and the expansion rate is shown below. When the size of the detection block is M × M pixels, the size of the expanded search range is (Q × M−1) × (Q × M−1), and the number of arithmetic units is P, P and the expansion rate The relation with Q is set as follows. However, Q> 2.

This equation (2) is calculated as follows:
The value obtained by adding the values is used as the expansion rate Q. The number of arithmetic units P is 1,2 ² , 3 ² , 4 ² , ...

A specific example will be shown. M of the detection block size M × M is M =
When 3 pixels and the number of arithmetic units P = 4 (example of FIG. 1), the size of the extended search range is (Q × M−1) × (Q × M−
1) = 8 × 8 pixels. FIG. 2 shows an example of the share of calculation by the calculation units 101 to 104 for such an extended search range. The first divided search range of FIG. 2 (a) is used for the arithmetic unit 101, the second divided search range of FIG. 2 (b) is used for the arithmetic unit 102, and the third divided search range of FIG. 2 (c) is used. Is for the arithmetic unit 103, and the fourth divided search range in FIG. 2D is for the arithmetic unit 104.
Also, the 3 × 3 pixels indicated by the diagonal lines in (d) correspond to the same position block.

The size of the four divided search ranges is (2 × M−1) × (2
× M−1) = 5 × 5 pixels of uniform size.

FIG. 3 shows how to provide the data of the four divided search ranges. In FIG. 3, three pixels are horizontally divided from the left side. Finally, 2 pixels remain. On the other hand, it is vertically divided into 3 pixels from the top, and then divided into 2 pixels. The rest is 3 pixels. Thus, although it is not uniform, 9 sections have been created.

With respect to the section of FIG. 3 (a), it is divided into 5 pixels from the top in the vertical direction to be FIG. 3 (b), and is divided into 5 pixels from the bottom in the vertical direction to be FIG. 3 (c). 3B and 3C, the blocks of 2 × 8 size in the intermediate section shown by the diagonal lines in FIG. 3A overlap.

Here, the data of the three sections of FIG. 3 (b) b _1,
Let b _{1 ′} and b _{2 ′} , and define the data of the three sections in FIG. 3C as b ₃ , b _{3 ′} and b _{4 ′} . b ₁ is b (0.0) to b (4.
15 data of 2), b1 _' is b (0.3) to b (4.5)
15 data of b _{2 ′} is 10 of b (0.6) to b (4.7)
Pieces of data, b ₃ 15 pieces of data of b (3.0) ~b (7.2) is, _{b 3 '15} pieces of data of b (3.3) ~b (7.5) is, _{b 4'} is b ( 10 data from 3.6) to b (7.7) are given. Each input from the block b to the arithmetic units 101 to 104 in FIG. 1 is data for each of these sections.

The operation of the arithmetic units 101 to 104 based on each of these b inputs will be described with reference to FIG. The operation of each arithmetic unit is basically the same as that shown in FIG.

The calculation unit 101 obtains evaluation data between the detection block and the search block in the divided search range having a size of 5 × 5 pixels at the upper left of FIG. Here, the size of each of the detection block and the search block is 3 × 3 pixels.

There are three search blocks in the horizontal direction and three in the vertical direction, for a total of 3 × 3 = 9. Therefore, as shown in FIG. 3 (b), this first divided search block has b ₁ and b
_Since it is formed of 1'and the arithmetic unit 101, the data a
In addition to this, b ₁ and b _{1 ′} are also fetched together, and as shown in FIG. 11, the operation ends at clock 28.

The calculation unit 102 is in charge of the second divided search range in FIG. This is formed by the data b _{1 ′} and b _{2 ′} , and a
And b _{1 ',} b _2', as shown in FIG. 11 with the ends of the operation on the clock number 32.

The calculation units 103 and 104 also perform input acquisition calculation based on the same concept.

The calculation unit 104 has a function of obtaining a vector value (evaluation value) in the same position block, in addition to a function of obtaining a local motion vector over the fourth divided search range in FIG. When the extended search range has an odd-sized side such as (2m + 1) × (2m + 1), the co-located block is located exactly in the middle of the block. In the example of FIG. 2, since the extended search range has even-sized sides such as 2 m × 2 m, the same position block is not located at the center of the extended search range, and the same position block is shown in FIG. And the first search block (edge) in the calculation unit 104 corresponds to the same position block. Therefore, the arithmetic unit 104 takes in the data of the first search block and, when performing the arithmetic operation for obtaining the evaluation data with the detection block, the same-position latch signal E / C7 from the outside.
In response to 0 (in this embodiment, a signal indicating the edge E is given), the evaluation data for this first search block is held in the latch means provided separately. The evaluation data of the latched first search block is the same position vector and is provided to the outside as appropriate.

The external comparison unit 200 receives the local motion vector information 61 to 64 which is the evaluation data from the four calculation units 101 to 104, compares the sizes, and sets the smallest one as the motion vector 60 over the expanded search range. Identify.

According to the present embodiment, the evaluation data is obtained while appropriately sharing the expanded search range of the size of 8 × 8 pixels under the four arithmetic units, that is, the expanded search range is reduced. The number of calculations can be reduced by dividing into sub-regions and input to a plurality of arithmetic units, and the calculation time can be reduced by inputting one small sub-region in common to two arithmetic units. .

Another embodiment of the motion vector detecting device of the present invention is shown in FIG. The present embodiment is an example in which a larger expanded search range is searched by using P = 9 arithmetic units 101 to 109. According to the equation (2), the enlargement factor Q is The search range after expansion is (4 × M−1) × (4 ×
M-1) The size of the pixel. If M = 3, the size of the expanded search range is 11 × 11 pixels.

The fifth example of the concept of the divided search range in this extended search range
Figure and Figure 6 show.

The upper area shown in FIG.
Is processed and the central area shown in (b) is calculated by the calculation units 104, 105,
Processing is performed by 106, and the lower area shown in FIG.
08 and 109 respectively process. Of the 5 × 5 pixels in the central portion processed by the arithmetic unit 105 in FIG. 5B, the 3 × 3 pixels in the central portion indicated by diagonal lines correspond to the same position block. The calculation unit 105 outputs the evaluation data (same position vector) according to the control signal E / C70. In this embodiment, the center positions correspond to each other, so C
Input the (center) signal.

Next, the data array of the expanded search range b will be described. FIG. 6 shows division of the search range b. 11 x 11
Pixel block Fig. 6 (a) shows the upper 11x5 pixels in Fig. 6 (b), the central 11x5 pixels in Fig. 6 (c), the lower 11x.
It is divided into areas of 5 pixels in FIG. 11 of each
The × 5 pixel block is divided into three 3 × 5 pixel blocks and a 2 × 5 pixel block, and each of b ₁ , b _{1 '} = b ₂ , b _2' =
_{b 3, b 3 ', b} 4, b 4' = b 5, b 5 '= b 6, b 6', b 7, b 7 '=
_{b 8, b 8 '= b} 9, b 9' are. As shown in FIG. 4, in the nine arithmetic units 101 to 109, a, b ₁ and b _{1 ′} are input to the arithmetic unit 101 and a, b _{1 ′} and b _{2 ′} are to the arithmetic unit 102 as input data, a, b _{2 '} , b
_3'is in the arithmetic unit 103, and a, b ₄ , b _4'is in the arithmetic unit 104, and a, b
_{4 ′} and b _{5 ′} are in the operation unit 105, and a, b _{5 ′} and b _{6 ′} are in the operation unit 106.
A, b ₇ and b _{7 ′} are in the operation unit 107, and a, b _{7 ′} and b _{8 ′} are in the operation unit
At 108, a, b _{8 ′} and b _{9 ′} are input to the computing unit 109.

The arithmetic units 101 to 109 respectively execute the processes corresponding to the shared areas shown in FIG. 5, and output the local motion vector information 61 to 69. These nine output results are compared in magnitude by the external comparison means 200, and the smallest one is output as the motion vector information 60 over the expanded search range.

Next, a general method for obtaining the same position vector is shown below.

Each of the P motion vector calculation units calculates the upper left position (edge) of the search block at the first clock time and the spatially same position (center) as the input image block at the mth clock time. (M = (M + 1) × M / 2 + 1
Defined by 1.), the calculation result in both clock times is selected by an external signal and output. When the expanded search range is processed by the P operation units, the first operation unit processes the upper left partial region and the second operation unit processes the right adjacent partial region, and the last lower right region is processed. The P-th arithmetic unit processes the partial area. When the value of P is an odd number, the calculation result at the m-th clock time is selected for the (P + 1) / 2-th calculation unit to determine the same position vector for the expanded search range. When the value is an even number, the calculation result at the first clock time is selected for the nth calculation unit and the same position vector for the expanded search range is determined. Will be.

〔The invention's effect〕

According to the present invention, it is possible to extend a motion vector search area by using a plurality of the same arithmetic units, and to achieve a new function that enables a quick search within an extended search range. Also, the value of the same position vector can be easily calculated, and a large additional circuit is not required.

[Brief description of drawings]

FIG. 1 is an embodiment diagram of a motion vector detecting device of the present invention, and FIG.
FIG. 3 and FIG. 3 are examples of division of the search range of the present invention, FIG. 4 is a diagram of another embodiment of the motion vector detecting device of the present invention, and FIGS. 5 and 6 are search ranges of other examples. FIG. 7 is a diagram showing an example of division of FIG.
FIG. 9 is an explanatory diagram of the same position block, FIG. 9 is a relational diagram between a detection block and a search range, FIG. 10 is a diagram showing an operation time chart and a calculation example of a conventional motion vector detecting device, and FIG. 11 is a first diagram. 3 is a diagram showing an operation time chart and an example of calculation in the embodiment of FIG. 101 to 104 …… Calculator, 200 …… External comparison means.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Yutaka Maruyama 7-15 Minamiaoyama Minato-ku, Tokyo Column 6F Minamiaoyama 6F Brafix Communication Tenology Co., Ltd. (56) Reference JP-A-54-124927 JP, A) JP 63-244985 (JP, A)

Claims (3)

[Claims] 1. A plurality of detection blocks of size M × M pixels in the input screen and a plurality of size M × M of a search range of size (2M−1) × (2M−1) pixels in the previous screen. A motion vector including means for sequentially reading the search block, and a plurality of arithmetic units for sequentially comparing the read detection block with a plurality of search blocks to calculate a local motion vector. In the detection device, the search range of the previous screen is set to size (2M-1) x (2M-1)
When the number of the above-mentioned arithmetic units when expanding from pixels to (Q × M-1) × (Q × M-1) pixels is P (P = 2 ² , 3 ³ , 4 ² ...), the above expansion is performed. The rates Q and P are The P search units have an extended search range of M (horizontal direction) × (2M−1)
(Vertical direction) divided into small pixel areas and input
Further, one of the P operation units is input in common to two operation units to which the horizontally adjacent sub-regions are input. Motion vector detection device. 2. The motion vector detection device according to claim 1, wherein the extended search range is a range centered on the same position block at the same position as the detection block. 3. The P arithmetic units each calculate the upper left position (edge) of the search block in the first clock time, and the spatially same position (center) as the input image block in the mth position. The clock time is calculated as (m = (M + 1) × M /
2 + 1), and means for selecting and outputting an operation result in the both clock times by an external signal, and a first upper left small partial area for processing the expanded search range by the P operation sections. If the second arithmetic unit processes the right adjacent small partial region by the second arithmetic unit and the P-th arithmetic unit processes the last lower right small partial region, and the value of P is an odd number, The operation result at the m-th clock time is selected for the (P + 1) / 2-th operation unit and is defined as the same position vector for the expanded search range. If the value of P is an even number, the n-th operation vector is selected. For the calculation unit of, the calculation result at the first clock time is selected and defined as the same position vector for the expanded search area. The motion vector detecting device according to claim 1 or 2, wherein