JP3046313B2 - Motion compensation method for interframe coding - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a motion compensation method in an inter-frame encoding device, and more particularly to a motion compensation method suitable for reducing the amount of computation for motion compensation.

[Prior Art] FIGS. 8 to 10 show, for example, a document “Interframe Coding Method Using Motion Compensation / Background Prediction” (Transactions of the Institute of Electronics, Information and Communication Engineers'85 / 1Vol.J68-BNo.1p77-p84 Kuroda) Hideo, Naoki Takekawa, Hideo Hashimoto), which is an explanatory diagram of a conventional motion compensation calculation method, specifically illustrating an all search method.

In the figure, (1) is an input signal of image data, (2)
Is an input frame buffer for temporarily storing one frame of input data, (3) is a current input block having a block size of 1 × l2 for motion compensation at a predetermined position in a current input frame, and (4) is a reproduction of a previous input frame. This is a motion vector search range indicating the range 1 + 2m and l2 + 2n where the block to be matched with the current input block (3) in the data exists.

In this case, the number M of search target blocks is M = (2m + 1) × (2n + 1) (100), and the search range is a range of −m to + m pixels in the horizontal direction.
The range is -n to + n pixels in the vertical direction.

The motion compensation uses the inter-frame correlation between the current input frame data and the previous input frame reproduction data in the inter-frame coded transmission method, and performs a process of obtaining a prediction signal closer to the current input frame data in block units of a predetermined size. To be processed.

Then, the block having the highest correlation with the current input block (3) in the current input frame data, that is, the block having the least amount of inter-block distortion due to the condition of minimizing the sum of absolute differences is determined as the motion vector in the previous input frame reproduction data. A search is performed from the search range (4) to obtain a motion vector and a prediction signal.

In the figure, reference numeral (5) denotes motion compensation for obtaining a prediction signal by correlation approximation calculation between the current input block (3) of the input signal (1) and the motion vector search range (4) given as the previous input signal reproduction data. , (6) is a prediction signal output from the motion compensation unit (5), and (7) is motion vector information output from the motion compensation unit (5).

Further, (9) encodes a difference signal (8) between the input block signal (3) and the prediction signal (6), and encodes the encoded signal (1).
An encoding unit that outputs (0), and a decoding unit (11) that decodes the encoded signal (10) encoded by the encoding unit (9).

Then, (14) adds the decoded signal (12) from the decoding unit (11) and the prediction signal (6) from the motion compensating unit (5), returns to the reproduced data (13), and stores it. A frame memory for providing a motion vector search range (4) to the motion compensator (5), (15) a transmission buffer, and (16) a transmission signal.

 Next, the operation will be described with reference to FIGS. 9 and 10.

For the current input block (3) in the current input frame, the motion vector search range (4) in the previous input frame reproduction data for the block X of 1 × l2 size at a specific position
Calculate the amount of inter-block distortion between M blocks in
The minimum value of this distortion, that is, the minimum distortion block that gives the minimum distortion
A relative position of yi with respect to the position of the current input block (3), that is, a motion vector V is obtained, and a signal ymin of the block yi is output as a prediction signal (6).

Then, in the inter-frame coded transmission, the prediction signal (6) can be generated even on the signal receiving side.

For example, if the number of motion vectors V to be searched in a given motion vector search range (4) is M (an integer of 2 or more), the previous frame block at the position of the specific motion vector V and the current input vector When the sum of absolute differences is used as the amount of distortion with the block, the amount of distortion is Becomes Here, the input block is X = {x1, x2,... XL}, the search target block is yi = {yi1, yi2,... YiL}, i = 1 to M, and L is l × l2. Then, the motion vector V is obtained by V = Vi {min dili = 1 to M} (102).

The calculation amount S1 in this case is calculated by a
When the machine cycle and the comparison process are b-mine cycles, S1 = M (L × a + b) (103)

Here, for example, if a = 1 machine cycle, b = 2 machine cycles, 1 = 8, l2 = 8, m = 8, n = 8, L = 64, M = 289, and S119000 ... (104) machine Cycle. The amount of operation S1 is a very large value from the viewpoint of the hardware configuration, and a high-speed operation system such as pipeline processing is used in accordance with the cycle of a frame that is a video signal.

However, simplifying hardware is a major challenge,
For example, Japanese Patent Application Laid-Open No. 63-181585 proposes a method of performing a tree search type motion compensation operation for the purpose of reducing the amount of operation in a TV signal motion compensation interframe coding device.

The tree search type motion compensation calculation method, as shown in FIG.
When a first search target block (）) having a low density is arranged at regular intervals in the motion vector search range (4), and a block を that gives the minimum distortion is detected,
Is located in a narrow area centered on, a block □ that gives the minimum distortion is detected therein, and a third block □ is located in the area centered on the block □.
The search target block (△) is set to detect the block 与 え る that gives the minimum distortion, and finally the block 与 え る that gives the minimum distortion in the motion vector search range (4) is specified.

The calculation amount S2 in this case is S2 = {9 × L × a + 9 × b} × 3 (105) Therefore, under the same conditions as above, the number of machine cycles is S21800, and this tree search type motion compensation operation method requires less computation than the full search type.

[Problems to be Solved by the Invention] Since the conventional motion compensation calculation method is configured as described above, the amount of calculation increases when performing a full search with high reliability in the motion compensation calculation, and the amount of hardware increases. If the configuration becomes large-scale and the amount of calculation is reduced by tree search or the like, the detection performance of the minimum distortion block is inferior, that is, the position of the minimum distortion block is separated from the position of the original minimum distortion block in the matching process at the time of the first low-density search. There is a problem that the block at the position may be selected, and the number of cases where the target minimum distortion amount is not reached and the determination of no correlation is made increases, so that inefficient transmission must be enjoyed. Was.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problem, and is a motion compensation method capable of reducing the amount of calculation without deteriorating the detection performance of the minimum distortion block and simplifying and miniaturizing hardware. The purpose is to obtain.

[Means for Solving the Problems] The motion compensation method according to the present invention divides an input frame into input blocks of a predetermined size, and compares the input block with a search target block in a previous frame. A motion compensation method in an inter-frame encoding device that detects a motion vector, wherein the input block is divided into a plurality of average value blocks, and for each average value block, an average value of pixel data in the average value block is obtained. An average value pattern is calculated for the input block, a motion vector search range in the previous frame for the input block is set based on the position of the input block in the frame, and a plurality of search target blocks are set in the motion vector search range. Are arranged at a low density, and the arranged search target blocks are divided into a plurality of average value blocks. Divided into
For each average value block, the average value of the pixel data in the average value block is calculated, the average value pattern for each search target block is calculated, and the average value pattern of the input block and the average value pattern of each search target block are calculated. Find the optimal search target block from the obtained distortion amount, and based on the position of the detected optimal search target block in the previous frame, place the limited search target block around it at high density. In this arrangement, the amount of distortion between the input block and each of the limited search target blocks is obtained in smaller units based on both pixel data, and a motion vector is detected from the obtained amount of distortion.

[Operation] Based on the above-described configuration, the motion compensation unit arranges the search target blocks at a low density within the motion vector search range, and calculates the block in which the average inter-average distortion amount of these blocks is the minimum distortion by the calculation target motion vector. By detecting as a block, setting a limited search range around the minimum distortion block as a high-density search target block, detecting a motion vector from the block, and first comparing the distortion amount with an average value pattern, It is possible to narrow down the existence position of the minimum distortion block with high accuracy, and thereafter perform high-density motion vector search within a limited area, thereby performing high-precision detection while suppressing the amount of calculation.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.

The same or corresponding parts as those described above are denoted by the same reference numerals and description thereof will be omitted.

FIG. 1 is a block diagram of a motion compensation interframe coding apparatus. In the figure, (17) indicates the number of pixels in the average value block in units of small blocks (average value blocks) of a predetermined size that can evenly divide a block of 1 × 12 size used for motion compensation for one frame of the reproduction frame. Average (1
An average value calculation circuit for obtaining 8) and an average value frame memory 19 for holding an average value (18) in units of average value blocks for one frame.

FIG. 2 is a diagram showing the internal configuration of the motion compensation unit (5). In FIG. 2, (21) denotes an average value calculation for calculating the average value (18) in the average value block unit in the input block to be encoded. A circuit (23) is an input average value memory for holding each average value of the average value blocks in the input block as one pattern.

Also, (24) is an average value pattern matching circuit that calculates the amount of distortion between the average value pattern of the input block and the average value pattern in the average value frame memory (19) and detects the minimum distortion block. ) Is a pixel pattern matching circuit that calculates the inter-image distortion amount between the input block and the block within the search range in the frame memory and detects the position of the minimum distortion block.

4 and 5 are explanatory diagrams of the first-stage motion vector detection method based on the minimum distortion of the average value pattern. In the drawings, (20) indicates the search range of the reproduced frame average value pattern, and (22) indicates the search range. The average pattern of the input block, (27) is the average block.

 Next, the operation of the present invention will be described.

The input signal (1) is encoded by the encoding unit (9) and decoded by the decoding unit (11) to become decoded reproduction data (13) by the same operation as in the past, and the decoded reproduction data (13) Is stored in the frame memory (14) as in the prior art, and one frame is divided into average value blocks (27) having a size of k1 × k2, and an average value of pixels is obtained for each of the average value blocks (first). See figure).

Then, assuming that the average value block at this time has a size that can equally divide a block of 1 × 12 used for motion compensation, J (J = (1 × 12) in 1 × 12 block
There is an average value of / (k1 × k2).

In this case, the pixel average value aj in each average value block
(J = 1 to J) are collectively handled as one pattern A.

 That is, A = {a1, a2,... AJ}.

Next, as shown in the flowchart of FIG. 3, the method of motion vector detection is to search for the minimum distortion block as the first stage by setting the arrangement interval of the search motion vector according to the size of the average value block (step S1) (step S1). (See FIG. 6).

The average value calculation circuit (21) calculates an average value pattern (22) for the input block (3), and calculates the average value pattern of the input block and the previous frame corresponding to the block at the position of the motion vector. The average value pattern matching circuit (24) executes matching distortion calculation and minimum distortion block detection between the average value pattern and the average value pattern (step S).
2) (See FIG. 5).

 The average distortion amount is represented by the following equation.

The input block average value pattern A = ｛a1, a2,...
aJ｝, average playback frame position pattern Ay = ｛ay1, ay2,
... aJ｝

At this time, by using the average pattern matching, the amount of calculation is 1 × 12 machine cycles for calculating the average value per input block and reproduction frame block, and J machine cycles per average value pattern matching.

 Therefore, in the first stage search, the required computation amount C1 is as follows: C1 = (1 × l2) × (M1 + 1) + M1 + J × a + M1 × b (108) Mi is the number of first-stage search motion vectors.

Next, as shown in FIG. 7, the motion detection step in the pixel pattern matching circuit (26) is performed in the minimum distortion block (28) obtained by the average value pattern matching circuit (24).
, A limited search range (29) having a size of ml × nl is set, and motion vectors to be searched are arranged with high density within the range (step S3).

 The calculation amount C2 in the limited search range (29) is the sum of {(2ml + 1) (2nl + 1) × L × a} (109) and (2ml + 1) (2nl + 1) + b in the comparison processing.

Here, 1 = 8, l2 = 8, m = 8, n = 8, average value block k1 = 4, k2 = 4, number of operation machine cycles a = 1
If (absolute difference) and b = 2 (comparison processing), the number of search vectors M1 = 25 and J = 4.

Therefore, the required calculation amount C1 in the first stage is about 1800.

In the second search, the limited search range is set to m1 =
Assuming that 3, n1 = 3, the required operation amount C2 in the second stage is about 3200 machine cycles.

As described above, the number of machine cycles per input block is 5,000, which is about 1/4 of the calculation amount of the conventional full search.

[Effects of the Invention] As described above, according to the present invention, a matching error at the time of narrowing down is prevented by using the intra-block average value inter-pattern distortion amount for narrowing down the motion vector search range, and the narrowed area is narrowed down. Since a high-density motion vector search is performed only by using a motion compensation method, the amount of calculation can be reduced and the apparatus can be simplified, so that a motion compensation method capable of detecting a motion vector with high detection accuracy can be obtained.

[Brief description of the drawings]

FIG. 1 is a functional block diagram showing a configuration of a motion compensation interframe coding apparatus according to the present invention, FIG. 2 is a functional block diagram showing an internal configuration of a motion compensation unit, and FIG. 3 is a flowchart showing an operation of the present invention. FIG. 4, FIG. 4 is an explanatory diagram of average value pattern calculation, FIG. 5 is an explanatory diagram of motion vector detection using the first-stage average value pattern, and FIG. Illustration of the arrangement of motion vectors,
FIG. 7 is an explanatory diagram of the second-stage motion vector detection in the search range limited by the first-stage motion vector detection, and FIG. 8 is a function showing the configuration of a conventional motion compensation interframe coding apparatus. 9 (a) and 9 (b) are explanatory diagrams of a conventional motion vector detection method, FIG. 10 is an explanatory diagram of a conventional full search motion vector detection method, and FIG. 11 is a conventional tree search type FIG. 4 is an explanatory diagram of a motion vector detection method. In the figure, (5) is a motion compensation unit, (17) is a sampling circuit, (19) is a sample data memory, and (28) is a first data memory.
This is the stage detection minimum distortion block. In the drawings, the same reference numerals indicate the same or corresponding parts.

Claims (1)

(57) [Claims] 1. An interframe coding apparatus for detecting a motion vector by dividing an input frame into input blocks of a predetermined size and comparing the input block with a search target block in a previous frame. Dividing the input block into a plurality of average value blocks, obtaining an average value of pixel data in the average value block for each average value block, calculating an average value pattern for the input block, Based on the position in the frame, a motion vector search range in the previous frame for the input block is set, and a plurality of search target blocks are arranged at a low density in the motion vector search range. Is divided into multiple average value blocks, and the average value is calculated for each average value block. The average value of the pixel data in the lock is calculated, the average pattern for each search target block is calculated, and the amount of distortion between the average pattern of the input block and the average pattern of each search target block is calculated. The optimal search target block is detected from the detected distortion amount, and based on the position of the detected optimal search target block in the previous frame, the limited search target blocks are arranged at high density in the vicinity thereof, and the input block and each limited A motion compensation method in an inter-frame encoding device for obtaining a distortion amount between blocks to be searched for in finer units based on both pixel data and detecting a motion vector from the obtained distortion amount.