JPH10322706A - Motion vector detection device - Google Patents

Abstract

(57) [Summary] [Problem] Even if the number of pixels in an encoding block is increased, the sum of absolute differences is calculated without taking a method of outputting one pixel value to many circuits at the same time, and high accuracy without error Accordingly, the present invention provides a motion vector detection circuit that facilitates the arrangement of an integrated circuit. A pixel value from an input port (1) is input to an RA register (2) for holding a pixel value of a block of interest and an RB register (3) for holding a pixel value of a search range, and is kept in the RA register (2) during the detection period. Pixel value and RB
The arithmetic unit 4 calculates the absolute value of the difference between the pixel values in the search range that are sequentially input to and held in the register 3, accumulates the output in the adder 5, and holds the intermediate result of the accumulation in each RC register 6. I do. The delay element 8 delays the intermediate result in accordance with the operation timing, inputs the total accumulated value to the minimum value detection circuit 9, obtains a candidate block having the minimum value for the target block, and detects a motion vector. Further, the detection can be performed for each field / frame by changing the circuit configuration.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to video coding, and more particularly, to a motion vector detection circuit required in a coding system using motion compensated prediction.

[0002]

2. Description of the Related Art In recent years, as a high-efficiency coding method for a moving image, a coding method using motion compensation prediction is often used. The motion compensation prediction method divides each image of a moving image sequence into coding blocks, detects a motion vector representing a displacement to a most correlated block from among reference images prepared for each coding block, and detects the motion vector. This is a coding method that obtains a prediction block using a motion vector and reduces temporal redundancy included between images.

As a method of detecting a motion vector, a block matching method is known. Hereinafter, the block matching method will be described. In the block matching method,
The prediction block candidate in the motion vector search area is extracted, and an error amount between the block candidate and the coded block is calculated. Then, the candidate with the smallest error amount is set as the prediction block, and the relative shift amount of the prediction block position from the coded block position is set as the motion vector. Here, assuming that the error amount is D represented by the following equation (1), that is, the sum of absolute differences between the pixels in the coding block and the pixels in the search area (hereinafter, referred to as “AE”): (I, j) that minimizes the error amount D is a motion vector. However, in equation (1), the size of the coding block is M × N,
The search area is set to [-K: K-1] and [-
L: L-1]. Further, T represents a pixel of the coding block, and R represents a pixel in the search area.

[0004]

(Equation 1)

[0005] As a conventional motion vector detecting circuit for detecting a motion vector by the block matching method,
There is one disclosed in Japanese Patent Application Laid-Open No. 7-184210.
Hereinafter, a conventional motion vector detection circuit will be described.
FIG. 37 is a block diagram of a conventional motion vector detection circuit. Here, for simplicity of description, the block size is 2 × 2 and the search range is 4 × 4. In FIG. 37, reference numeral 101 denotes an A register that holds a pixel in a block of interest, 102 denotes a binary operation unit that calculates an absolute value of a difference between two values, 103 denotes an A register 101 and a binary operation unit 10
2 are processors (1) to (4). 104 is an S port for inputting a pixel value in the block of interest, 105 is input a pixel value in the block of interest, and outputs the input pixel value to the A register 101 of each of the processors (1) to (4) 103. A pixel value input circuit in the block of interest; 106 and 107 are RA ports and RB ports for inputting pixel values within the search range;
Is a search range pixel value input circuit that inputs pixel values within the search range and outputs the input pixel values to the binomial calculator 102 of the processors (1) to (4) 103.
9 is adder (1) to adder (4) and B register 1
An accumulative addition circuit consisting of 10 and 112 is a minimum value detection circuit. The internal configuration of the pixel value input circuit 105 in the block of interest includes a control signal G for controlling the gates (1) to (4) and the gates (1) to (4) 201 of 201.
(1) to G (4), control signals G (1) to G of 202
It is composed of a ROM storing the pattern of (4) and a counter of 203. Search range pixel value input circuit 108
Has an internal configuration of selectors (1) to (4) 301, control signals F (1) to F (4) for controlling the selectors 301 and (4) 301, and control signals F (1) to
ROM of 302 storing the pattern of F (4),
It comprises 303 counters.

[0008] The operation of the conventional motion vector detecting circuit having the above-described configuration will be described with reference to FIG.
Pixel value R (i, j) within the search range (see FIG. 3B)
And the pixel value S (x, y) in the 2 × 2 block of interest
This will be described with reference to FIG. The pixel value S (x, y) in the 2 × 2 target block is input from the S port 104 in FIG.
8, ie, S (1,1), S (1,
2), S (2,1), S (2,2) are input in this order and selected by gates (1) to (4) 201 controlled by control signals G (1) to G (4), S (1, 1) is stored in the A register 101 of the processor (1) 103.
S (1,2) is stored in the A register of the processor (2).
The A register of the processor (3) holds S (2,1), and the A register of the processor (4) holds S (2,2) the pixel value in the target block.

The search range pixel input circuit 108 has 4 ×
The pixel value R (i, j) within the search range of No. 4 is RA
Each pixel value of the band A in FIG. 38 from the port 106 is arranged in the order indicated by the arrow in FIG. 38, that is, R (1,1), R (1,
2), R (2,1), R (2,2), ..., R (4
1) and R (4, 2) in order, and the pixel values of the band B in FIG. 38 from the RB port 107 in FIG. 37 are changed in the order indicated by the arrows in FIG. 37, that is, R (1, 3), R ( 1,4),
R (2,3), R (2,4), ..., R (4,3), R
They are input in the order of (4, 4). Here, the input of band B is started two cycles after the start of input of band A.
The search range pixel input circuit 108, as shown in FIG.
Each of the selectors (1) to (4) 301 includes a control signal F input from the counter 303 and the ROM 302.
If the level of (1) to F (4) is LOW, the pixel value input from the RA port 106 is used. If the level is HI, the RB port 1 is used.
07, the input pixel value is selected and output to the binomial calculator 102 of the processors (1) to (4) 103. FIG. 39 shows each control signal and the input to each binomial calculator 102. Thereby, for candidate block 1 shown in FIG. 38, processor (1)
In the second cycle, R (1,1) is stored in the binary operation unit 102 of the processor (2), and R (1,2) is stored in the binary operation unit 102 of the processor (2).
In the third cycle, the binomial operator 10 of the processor (3).
R (2,1) in 2 and processor (4) in 4th cycle
R (2,2) in the binomial calculator 102 of
Binary operation unit 10 of processors (1) to (4)
2 every other cycle, the processor's A register 1
The pixel value in the target block held at 01 and the pixel value at the same position in the candidate block 1 are input.

Focusing on the pixel value of each candidate block input to the processor (1) 103, FIG.
From the first cycle, regarding the candidate block 1, from the second cycle, regarding the candidate block 2, from the third cycle, regarding the candidate block 3,..., Pixel values regarding the next candidate block are input every other cycle. Is done.
Similarly, pixel values for the next candidate block are sequentially input to the binomial calculators 102 of the processors (2) to (4) every other cycle. In the processors (1) to (4) 103 of FIG.
2 is a pixel value S (x, y) in the block of interest held in the A register 101 and a pixel value R in the input search range.
The absolute value | S (x, y) −R (i, j) | of the difference from (i, j) is calculated, and the calculation result is added to adders (1) to ( 4) Output to 109. In the accumulator 111, each adder 109 adds the output of the binomial operator 102 and the output of the left adder, and stores the result in the B register 110. For example, regarding candidate block 1 in FIG. 38, first, the processor (1)
| S (1,1) -R (1,1) | is calculated, and the result is stored in the B register (1) via the adder (1). Next, | S (1,2) -R (1,2) | is calculated by the processor (2), and | S (1,1) -R (1,1) in the B register (1) is calculated. ) | Is added by the adder (2), and | S (1,1) -R (1,1) | + | S (1,2) -R
(1,2) | is stored in the B register (2). Similarly, finally, in the B register (4), | S (1,1) -R (1,1) | + | S (1,2) -R
(1,2) | + | S (2,1) -R (2,1) | + | S
(2,2) −R (2,2) | That is, AE for candidate block 1 (see equation (1))
Will be stored. As a result of the above-described pipeline operation, the candidate blocks 2, 3,... Are also sequentially calculated and sequentially supplied to the minimum value detection circuit via the B register (4). The minimum value detection circuit 112
The AE for each candidate block sequentially output from the accumulator 111 is detected as the one having the smallest value, and the deviation of the corresponding candidate block is output as a motion vector value.

[0009]

When the size of the block of interest is M × N, the conventional motion vector detection circuit described above uses the pixel value in the block of interest input from the port S and the RA and RB ports. The input pixel values in the candidate block are M × N gates (1) to (M × N) and selectors (1) to (M × N), respectively.
However, if the numerical values of M and N increase, one input pixel value must be output to a very large number of circuits at the same time, which results in an increase in output load and signal delay. At the time of realization, there is a problem that wiring is difficult or skew occurs in timing unless the arrangement in the integrated circuit is properly performed.

The present invention has been made in view of the above-mentioned problems in the prior art, and does not take a method of simultaneously outputting one pixel value to many circuits even if the number of pixels of the coding block is increased. Thus, it is necessary to solve the problem of providing a motion vector detection circuit that performs the calculation of the sum of absolute differences, does not cause an error in the calculation, increases the detection accuracy, and facilitates the arrangement of the integrated circuit. Make it an issue.

[0011]

According to the present invention, there is provided a circuit for detecting a motion vector by performing a full search on a reference image by a block matching method with a block size of an encoded (attention) block being M × N. A single port for inputting pixel values within the search range is provided, a register for holding the pixel values within the search range is provided for each fixed number of processors, and a register for holding the pixel value of the block of interest and M × are calculated by cascade-connecting the registers for holding the pixel values of the above and calculating the absolute value of the difference between the output of the register for holding the pixel values of the block of interest and the output of the register for holding the pixel values within the search range. N arithmetic units, a cascade-connected adder for cumulatively adding the calculation result of the arithmetic unit, and a register for holding an intermediate result of the cumulative addition And a delay holding means for delaying a register holding an intermediate result of the cumulative addition to match the operation timing of the processor, and a minimum value detecting circuit for detecting a minimum value from the result of the cumulative adder. Things.

According to a first aspect of the present invention, a block consisting of M × N pixels in an image is set as a coding block, and a candidate block for the coding block is searched for in a search range on a reference image by a block matching method. A motion vector detecting device that detects a motion vector based on a position of a candidate block indicating an optimum matching to be performed, and inputs M × N pixel values in the encoded block and pixel values in the search range. An input unit, M × N first registers connected in cascade to hold each pixel value in an encoding block input from the input unit for each pixel, and the search range input from the input unit And a cascade-connected second register for holding each pixel value in each pixel, and a difference between an output of the first register and an output of the second register. M × N arithmetic units for performing logarithmic calculation for each output of the first register, M × N adders each of which is cascaded to perform cumulative addition, and cumulative addition performed by the adder A third method for storing the result for each adder
And an adder for delaying the output of the third register by an operation timing period of a predetermined cycle so that the output of the arithmetic unit and the output of the third register are added at a predetermined operation timing in the adder. (M-1) or (N-1) delay means and the minimum value from at least some of the cumulative addition results of the M × N adders for each candidate block in the search range. A minimum value detection circuit for detecting a candidate block is provided.

According to a second aspect of the present invention, in the first aspect, each of the M × N adders for performing the cascade-connected cumulative addition and the cumulative addition result performed by the adder are stored for each of the adders. For each of the third registers, the M × (N / 2) registers are set as one set, the whole is divided into two sets, cumulative addition is performed in each set, and the minimum value is obtained from the obtained cumulative addition results. And a first and a second minimum value detection circuit for detecting the candidate block shown in FIG.

According to a third aspect of the present invention, in the first aspect, M × N fourth registers for delaying an intermediate result of the cumulative addition held in the third register are added to each of the third registers. And the delay means is (2 × (M−
1)) The M × N adders that perform the cumulative addition in cascade and increase the number of the adders, the third register, the fourth register, and the delay unit that hold the cumulative addition result are represented by (M / 2) × N adders and (M
(2) × N third registers, (M / 2) × N fourth registers, and (M−1) delay means as one set, and the whole is divided into two sets. The present invention is provided with first and second minimum value detection circuits for performing cumulative addition on a set and detecting candidate blocks having the minimum value from the obtained cumulative addition results.

According to a fourth aspect of the present invention, in the second or third aspect, each of the divided two sets corresponds to an odd field and an even field of the encoded block.

According to a fifth aspect of the present invention, in any one of the second to fourth aspects, a further adder for obtaining a sum of the cumulative additions obtained for the two sets divided by one, and a cumulative addition of the further adder A third minimum value detection circuit for detecting a candidate block having the minimum value from the results is provided.

[0017]

BEST MODE FOR CARRYING OUT THE INVENTION

(Embodiment 1) FIG. 1 is a diagram showing an embodiment of a motion vector detecting device according to the present invention. In FIG. 1, reference numeral 1 denotes an input port for inputting both a pixel value in a target block and a pixel value in a search range. Reference numeral 2 denotes an RA register for holding a pixel value in a target block input from the input port 1, reference numeral 3 denotes an RB register for holding a pixel value in a search range to be input, and reference numeral 4 denotes an RA register. | AB | computing unit for calculating the absolute value of the difference between the pixel value in the target block held in 2 and the pixel value in the search range held in the RB register 3, and 5 is | A-
B | is an adder for cumulatively adding the output of the arithmetic unit 4, and 6 is an RC register for holding an intermediate result of the cumulative addition calculated by the adder 5. Reference numeral 7 denotes a processing element (PE) composed of the RA register 2, | AB | arithmetic unit 4, adder 5, and RC register 6. Reference numeral 8 denotes a delay element that delays the intermediate result of the cumulative addition held in the predetermined RC register 6 in order to match the operation timing in the predetermined PE 7. Reference numeral 9 denotes a minimum value detection circuit for detecting a minimum value from the sum of absolute differences (AE) between the block of interest obtained as a result of the cumulative addition and each block within the search range, and a minimum value detection circuit 9 based on the timing at which the minimum value is detected. The deviation of the value block from the target block is output as a motion vector. In FIG. 1, M corresponds to the number of pixels in the horizontal direction of the block of interest, N corresponds to the number of pixels in the vertical direction of the block of interest, and PE is PE [1], P
.., And constitutes an M × N element composed of PE [M × N]. In this embodiment, the number of input ports 1 is one. However, the input ports may be divided into different input ports based on the pixel values in the target block and the pixel values in the search range.

Hereinafter, the operation of this embodiment will be described. For simplicity, the example of FIG. 2, that is, the size of the block of interest is 4 × 4 (see FIG. 1A), The search range is [-2:
1] (see FIG. 2B), the pixel value T (m, n) in the block of interest and the pixel value R in the search range
This will be described using (i, j). In this case, M, N in FIG.
Becomes 4. First, in the order shown in FIG. 2 (in the order of the arrow (A) in FIG. 2), the pixel values in the target block are T (0,0), T (0,1), T (0, 2),
T (0,3), T (1,0),..., T (3,3) are input, and the input pixel values in the target block are, as shown in FIG. R to hold
RA [16], RA [15], RA [1
4],..., RA [2], RA [1] every other cycle.
[1], RA [2],.
(0,0), T (0,1),..., T (3,3) are held, and the input of the pixel values in the target block is completed. The pixel value T (m, m) in the block of interest held in the RA register 2
n) is output to the arithmetic unit 4. At this time, each pixel in the block of interest is arranged one pixel in each PE.

After the input of the pixel values in the target block is completed, the pixel values in the search range are changed from the input terminal 1 in the order shown in FIG. 2 (in the order of the arrow (A) in FIG. 2) by R (−). 2,-
2), R (-2, -1), R (-2, 0), ..., R (-
2, 4), R (-1, -2),..., R (4, 4), and as shown in FIG. 4, an RB register 3 for holding a pixel value within the search range of FIG. RB [4], RB
[3], RB [2] and RB [1] are transferred every other cycle. The output of each RB register 3 is input to a computing unit 4 in N (= 4) PEs 7 arranged side by side in FIG. Using the pixel value T (m, n) of the block of interest held in the RA register 2 and the pixel value R (i, j) in the search range held in the RB register 3, the operation of Expression (1) is performed. , M × N (4 × 4 = 16) PEs 7 and M−1 (three) delay elements 8.

The process is shown in FIGS. In addition,
6 to 9 show A1, B1, and C in FIG. 5, respectively.
1 is a partial view corresponding to D1. 5 to 9 will be described focusing on the calculation for the candidate block 1 within the search range in FIG. Assuming that the start of the input of the pixel value within the search range from the input terminal 1 is the first cycle, R (−2, −2) which is the first pixel value of the candidate block is RB [1] in the fifth cycle.
Is held. In the sixth cycle, the pixel R (−) of the candidate block 1 held in RB [1] in the fifth cycle is
From the pixel T (0,0) of the block of interest held in RA [1], the absolute value | R (−2, −2) −T (0,0) | Calculated by the arithmetic unit 4 in [1], the result and 0 are added in the adder 5 in PE [1], and the addition result | R (−2, −2) −T (0, 0) | is held in the temporary addition register RC [1] for cumulative addition. In the seventh cycle, pixels R (−2, −1) of candidate block 1 held in RB [1] in the sixth cycle and RA
Pixel value T (0,1) of the block of interest held in [2]
The absolute value | R (−2, −1) −T (0,1) | of the difference between them is calculated by the arithmetic unit 4 in PE [2], and the result and RC
The addition with [1] is performed by the adder 5 in PE [2], and the addition result | R (−2, −2) −T (0, 0) | + | R (−2, −
1) -T (0, 1) | is held in the temporary register RC [2] for cumulative addition. In the eighth cycle, the same processing as in the seventh cycle is performed in PE [3], and | R (−2, −2) −T (0,0) | + | R ( −2, −
1) -T (0,1) | + | R (-2, -0) -T (0,
2) | is maintained. In the ninth cycle, PE [4]
The same processing as in the cycle is performed, and R (−2, −2) −T (0, 0) | + | R (−2, −
1) -T (0,1) | + | R (-2, -0) -T (0,
2) | + | R (−2, −1) −T (0, 3) | In the tenth cycle and the eleventh cycle, the register RB holding the pixel value within the search range
Since [1] contains a pixel value other than that of candidate block 1, the delay element [1] is used to set the RC value in the ninth cycle.
The intermediate result of the cumulative addition held in [4] is delayed until the pixel value in the candidate block 1 is input and the next operation can be performed. At the 12th cycle, candidate block 1 is assigned to RB [2].
, The pixel R (-1, -2) in the second column is held, and the R (-) held in this RB [2] in PE [5] is stored.
1, [-2] and the pixel value T (1,0) of the block of interest held in RA [5], the absolute value calculation of the difference and the cumulative addition calculation with the output of the delay element [1] are performed. 5] includes | R (−2, −2) −T (0,0) | + | R (−2, −1) −T
(0,1) | + | R (-2,0) -T (0,2) | + | R (-2,
1) -T (0,3) | + | R (-1, -2) -T (1,0) | Hereinafter, by repeating the same processing, RC [1] in PE [16] at the 28th cycle.
6]: | R (−2, −2) −T (0,0) | + | R (−2, −
1) -T (0,1) | + | R (-2,0) -T (0,
2) | + | R (-2,1) -T (0,3) | + | R (-
1,2) -T (1,0) | + | R (-1, -1) -T
(1,1) | + | R (-1,0) -T (1,2) | + |
R (-1,1) -T (1,3) | + | R (0, -2)-
T (2,0) | + | R (0, -1) -T (2,1) | R
(0,0) -T (2,2) | + | R (0,1) -T
(2,3) | + | R (1,2) -T (3,0) | + | R
(1, -1) -T (3,1) | + | R (1,0) -T
(3,2) | + | R (1,1) -T (3,3) | is held, and is represented by Expression (1) between the pixel of the target block and the candidate block 1 within the search range. The value of AE is determined.

The processing for candidate block 2 is performed in the pipeline one cycle later than the processing for candidate block 1 described above. Therefore, the 29th cycle between the pixel of the target block and candidate block 2 within the search range is performed. AE is held in RC [16] in PE [16]. The same applies to the candidate block 3 and thereafter. The minimum value detection circuit 9 in FIG. 1 calculates the absolute value of the difference between the pixel values and the cumulative addition value from PE [1] to PE [16] as described above, and calculates the difference between the target block T and the candidate block R. AE for each candidate block
Is sequentially input as an accumulated value from RC [16] in PE [16] in each cycle, and the minimum AE value is detected among them. At the same time, a motion vector between the candidate block and the block of interest is detected from the candidate block having the minimum AE. In FIG. 1 (Embodiment 1), if M and N are exchanged, even if the pixels of the target block and the pixels in the search range are input in the input order shown in FIG. 10, the input order shown in FIG. A motion vector can be detected by the same processing as in the case.

(Embodiment 2) FIG. 11 is a diagram showing another embodiment of the motion vector detecting device according to the present invention. In the present embodiment, a motion vector between frames and a motion vector between fields are simultaneously detected. In FIG. 11, M corresponds to the number of pixels in the horizontal direction of the block of interest, and N corresponds to the number of pixels in the vertical direction of the block of interest. Further, the processing is divided into two sets in the vertical direction, and the minimum value detection circuits [1] and [2] are used as the minimum value detection circuit 9 for each group.
And an adder 10 for adding two sets of cumulative addition results, and a minimum value detection circuit [3] for this output. 11, the same elements in FIG. 1 are given the same numbers.

Hereinafter, the operation of this embodiment will be described. For simplicity, the example of FIG.
The size of the block of interest is 4 × 4 (see FIG. 10A),
The search range of the motion vector is set to [-
2: 1] (see FIG. 10B) will be described using the pixel value T (m, n) in the target block and the pixel value R (i, j) in the search range. In this case, M and N are each equal to 4. The pixel values in the block of interest are input from the input terminal 1 in the order shown in FIG. 10 (in the order of the arrow (A) in FIG. 10), and the pixel values in the block of interest are input as shown in FIG. The data is transferred to the RA register 2 for holding the pixel value in the block. FIG.
In the 17th cycle, all pixels in the block of interest are
One pixel is arranged for each PE in FIG. 11, and the pixel input of the target block is completed.

After the input of the pixels in the block of interest is completed, the pixel values in the search range are input from the input terminal 1 in the order shown in FIG. 10, and as shown in FIG. The data is transferred to the RB register 3 for holding. The output of each RB register 3 is M
Are input to the arithmetic unit 4 in the PEs 7. The pixel value T (m, n) of the block of interest held in the RA register and the pixel value R within the search range held in the RB register
Using (i, j), the calculation of the expression (1) is performed by M × N (4 ×
4 = 16) PE7 and N-1 (three) delay elements 8
Done in The PE 7 and the delay element 8 are the PEs (PE [1] to PE [4], PE
[9] to PE [12]) and a first arithmetic system composed of delay elements [1] and [3], and PEs (PE [5] to PE [5] in the second and fourth rows of FIG. 11). 8], PE [13] to PE
[16]) and a second operation system including a delay element [2]. Here, the first arithmetic system determines the AE for the pixels in the odd-numbered row (first field) of the block of interest, and the second arithmetic system calculates the AE for the pixels in the even-numbered row (second field) of the block of interest. Is what you want.

FIGS. 14 to 19 show the steps of the operation performed in the first operation system. FIGS. 20 to 25 show the steps of the operation performed in the second operation system. 15 to 19 correspond to FIG.
FIGS. 21 to 25 are partial views corresponding to A2, B2, D2, E2, and F2 in FIGS.
It is a partial view corresponding to D3, E3, and F3. FIG.
Paying attention to the calculation for the candidate block 1 within the search range shown in (B), similar to the first embodiment,
In the first arithmetic system, | R (−2, −2) −T (0, 0) | + | R (−1, −) is added to RC [12] in PE [12] at the 21st cycle.
2) -T (1,0) | + | R (0, -2) -T (2,
0) | + | R (1, -2) -T (3,0) | + | R (-
2,0) -T (0,2) | + | R (-1,0) -T
(1,2) | + | R (0,0) -T (2,2) | + | R
(1,0) -T (3,2) | is held, which is the AE for the odd-numbered row (first field) of the block of interest and candidate block 1. On the other hand, in the second arithmetic system, | R (−2, −1) −T (0, 1) | + | R (−1, −
1) -T (1,1) | + | R (0, -1) -T (2,
1) | + | R (1, -1) -T (3,1) | + | R (-
2,1) -T (0,3) | + | R (-1,1) -T
(1,3) | + | R (0,1) -T (2,3) | + | R
(1,1) -T (3,3) | is held, which is the AE for the even block (second field) of the block of interest and candidate block 1. These calculation results correspond to the AE between the fields of the target block and the candidate block 1.

In the first operation system, the operation result AE for the first field between the block of interest and the candidate block 1 held in RC [12] in PE [12] at the 21st cycle is obtained by the second operation. The result is delayed by the delay element [3] until the 27th cycle in which the result AE for the second field is held in the arithmetic system.
Is added to the result of the second operation system, and | R (−2, −2) −T (0,0) | + | R (−1, −
2) -T (1,0) | + | R (0, -2) -T (2,
0) | + | R (1, -2) -T (3,0) | + | R (-
2, -1) -T (0,1) | + | R (-1, -1) -T
(1,1) | + | R (0, -1) -T (2,1) | + |
R (1, -1) -T (3,1) | + | R (-2,0)-
T (0,2) | + | R (-1,0) -T (1,2) | +
| R (0,0) -T (2,2) | + | R (1,0) -T
(3,2) | + | R (-2,1) -T (0,3) | + |
R (-1,1) -T (1,3) | + | R (0,1) -T
(2,3) | + | R (1,1) -T (3,3) | This addition result corresponds to the inter-frame AE between the target block and the candidate block 1. And 2
In the eighth cycle, the AE values obtained for the two fields between the target block and the candidate block 1 as described above are input to the minimum value detection circuit [1] and the minimum value detection circuit [2], respectively. The value of the inter-frame AE obtained from the adder 10 as described above is input to the minimum value detection circuit [3].

Since the processing for candidate block 2 is performed in the pipeline one cycle later than the processing for candidate block 1, the AE between the two fields for the block of interest and candidate block 2 is performed at the 29th cycle.
And the value of one inter-frame AE are input to the minimum value detection circuits [1] to [3] in the same manner as described above. The same applies to the candidate block 3 and thereafter. In the minimum value detection circuit [1], PE [1] to PE [4] and P
The value of the inter-field AE for each of the odd-numbered rows (first field) of the target block T and the candidate block R obtained in E [9] to PE [12] is sequentially input in each cycle. Is detected. At the same time, a first inter-field motion vector between the target block T and the candidate block R is detected from the candidate block R in which the AE becomes the minimum value. In the minimum value detection circuit [2], as described above, PE [5] to PE [8] and PE [13] to P
The inter-field AE values for the even-numbered rows (second fields) of the target block T and the candidate block R obtained in E [16] are sequentially input in each cycle, and the minimum AE value among them is To detect. At the same time, this A
A second inter-field motion vector between the block of interest T and this candidate block R is detected from the candidate block R where E becomes the minimum value. In the minimum value detection circuit [3], the inter-frame AE between the target block T and the candidate block R calculated by the adder 10 and the PEs [1] to PE [6] as described above.
Are successively input in each cycle, and the value of AE which is the smallest among them is detected. At the same time, a second inter-field motion vector between the candidate block R and the target block T is detected from the candidate block R in which the AE becomes the minimum value.

(Embodiment 3) FIG. 26 is a diagram showing another embodiment of the motion vector detecting device according to the present invention. This embodiment is another embodiment different from the above (Embodiment 2) in which a motion vector between frames and a motion vector between fields are simultaneously detected. In FIG. 26, reference numeral 11 denotes an RD register for delaying the intermediate result of the cumulative addition. The delay elements 8 are A and B delay elements corresponding to the two systems of processing, and the numbers in FIG. 26 are assigned the same numbers for the same elements in FIGS. 1 and 11. Hereinafter, the operation of this embodiment will be described. For simplicity, the example of FIG. 2, that is, the size of the block of interest is 4 × 4 (see FIG. 2A), and the search range of the motion vector is horizontal. In the case where [-2: 1] is set in both directions (see FIG. 2B), the pixel value T (m, n) in the block of interest and the pixel value R (i, j) in the search range are used. Will be explained. In this case, M and N in FIG.

From the input terminal, as in (Embodiment 1), the pixel values in the block of interest are arranged at the timing shown in FIG. 3 in the order shown in FIG. 2 (in the order indicated by the arrow (A) in FIG. 2). The pixel values in the search range are transferred to the RA register 2 to the RB register 3 at the timing shown in FIG. The output of each RB register 3 is N (= 4) PEs arranged side by side in FIG.
7 is input to the arithmetic unit 4. The pixel value T (m, n) of the block of interest held in the RA register and the RB
Using R (i, j) within the search range held in the register, the operation of Expression 1 is performed using M × N (4 × 4 = 16) PEs.
7, M-1 (three) A delay elements 8 and M-1 (three) B delay elements 8, and M × N (4 × 4 = 16) RD registers 11. PE7, A and B above
The delay element 8 and the RD register 11 are PE [2p-1]
(P = 1, 2,..., 8), A delay elements [1] to [3],
A first operation system composed of RD [2p] (p = 1, 2,..., 8), PE [2p] (p = 1, 2,.
B delay elements [1] to [3], RD [2p-1] (p =
, 8) are divided into a second operation system. Here, the first arithmetic system determines the AE for the pixels in the odd-numbered row (first field) of the target block, and the second arithmetic system determines the AE for the pixels in the even-numbered row (second field) of the target block. Things.

FIGS. 27 to 33 show the steps of the operations performed in the first operation system and the second operation system. 26 to 33 are partial views corresponding to A4, B4, C4, D4, E4, and F4 in FIG. 27, respectively. Paying attention to the operation on candidate block 1 in the search range shown in FIG. 2, the operation proceeds as shown in FIGS. 27 to 33, and in the first operation system, PE [15 | R (−2, −2) −T (0,0) | + | R (−2,
0) -T (0,2) | + | R (-1, -2) -T (1,
0) | + | R (-1,0) -T (1,2) | + | R
(0, -2) -T (2,0) | + | R (0,0) -T
(2,2) | + | R (1, -2) -T (3,0) | + |
R (1,0) -T (3,2) is held, which is the AE for the odd-numbered row (first field) of the block of interest and candidate block 1. On the other hand, in the second arithmetic system, | R (−2, −1) −T (0,1) | + | R (−2,
1) -T (0,3) | + | R (-1, -1) -T (1,
1) | + | R (-1,1) -T (1,3) | + | R
(0, -1) -T (2,1) | + | R (0,1) -T
(2,3) | + | R (1, -1) -T (3,1) | + |
R (1,1) -T (3,3) | is held, which is the AE for the even block (second field) of the block of interest and candidate block 1. These calculation results correspond to the inter-field AE between the block of interest and the candidate block.

In the first operation system, P
The operation result AE for the first field between the block of interest and the candidate block 1 held in RC [15] in E [15] is calculated by the register RD [16] in the second operation system with respect to the second field. The result of the first operation system and the result of the second operation are added by the adder 10 in the adder 10 in the 28th cycle, and the result is | R (-2, -2)- T (0,0) | + | R (−2, −
1) -T (0,1) | + | R (-2,0) -T (0,
2) | + | R (-2,1) -T (0,3) | + | R (-
1, -2) -T (1,0) | + | R (-1, -1) -T
(1,1) | + | R (-1,0) -T (1,2) | + |
R (-1,1) -T (1,3) | + | R (0, -2)-
T (2,0) | + | R (0, -1) -T (2,1) | +
| R (0,0) -T (2,2) | + | R (0,1) -T
(2,3) | + | R (1, -2) -T (3,0) | + |
R (1, -1) -T (3,1) | + | R (1,0) -T
(3,2) | + | R (1,1) -T (3,3) | This addition result corresponds to the inter-frame AE between the target block and the candidate block 1. And 2
In the eighth cycle, the AE values obtained for the two fields between the target block and the candidate block 1 as described above are input to the minimum value detection circuit [1] and the minimum value detection circuit [2], respectively. The value of the inter-frame AE obtained from the adder 10 as described above is input to the minimum value detection circuit [3].

Since the processing for candidate block 2 is performed in the pipeline one cycle later than the processing for candidate block 1, the value of the AE between the two fields between the block of interest and candidate block 2 The value of one inter-frame AE is determined by the minimum value detection circuit [1] to
[3] is input in the same manner as described above. Candidate block 3
The same applies to the following. In the minimum value detection circuit [1], PE [2p-1] (p = 1, 2,...,
8) The inter-field AE values for the odd-numbered rows (first field) of the target block T and the candidate block R obtained in 8) are sequentially input in each cycle, and the minimum AE value is detected among them. . At the same time, a first inter-field motion vector between the candidate block R having the minimum AE is detected. In the minimum value detection circuit [2], as described above, the inter-field between the even-numbered row (the second field) of the target block T and the candidate block R obtained by PE [2p] (p = 1, 2,..., 8) The values of AE are inputted one after another in each cycle, and the smallest value of AE is detected among them. At the same time, a second inter-field motion vector between the candidate blocks R having the minimum AE is detected. In the minimum value detection circuit [3], the value of the inter-frame AE between the target block T and the candidate block R obtained by PE [1] to PE [16] as described above is sequentially input in each cycle. A which is the smallest among
The value of E is detected. At the same time, an inter-frame motion vector between the candidate block R having the minimum AE is detected.

The following is a description of a modification that can be applied to each of the first to third embodiments. In each circuit configuration of the device, when there are many output destinations from one RB register 3, the search range is The RB register 3 for holding the pixel values of the two lines may be divided into two series.
This is an example in which (RE [1] to RE [N]) are added. For example, looking at PE7 in the first row, the left half of PE7 arranged horizontally (in the case of the top row, PE [1] to PE [1]
The output from RB [1] is output to the arithmetic unit 4 in [N / 2]), and the right half of the PEs 7 arranged side by side (in the case of the top row, P
E [N / 2 + 1] to PE [N]) have R
The output may be made from E [1]. In particular,
Taking the case of Embodiment 1 as an example, the block diagram is as shown in FIG. The same applies when the number of RB registers 3 is three or more. In each of Embodiments 1 to 3, the input order of the pixel values in the target block and the connection order of the RA register 2 for holding the pixel values in the target block may be reversed. Specifically, taking the case of Embodiment 1 as an example, the input order of the pixel values in the block of interest is T (3,3), T (3,2), T (3,3) as shown in FIG.
1),..., T (0,1), T (0,0), and a circuit configuration as shown in FIG.

[0034]

【The invention's effect】

Advantageous Effects According to Claim 1: It is possible to reduce the number of input terminals for pixel values and the number of output destinations from registers for holding pixel values within the search range, without increasing output load and signal delay. A circuit with less skew can be realized, and even when an integrated circuit is used, it is possible to prevent wiring from being concentrated on a specific portion, and to reduce difficulty in wiring and arrangement.

Effect corresponding to claim 2: In addition to the effect of claim 1, a circuit configuration corresponding to a method of generating an image can be employed, and a more accurate and appropriate motion vector can be detected. In addition, by dividing into two, the output load can be reduced, and the design of the circuit configuration can be made easier.

Effect corresponding to the third aspect: In addition to the effect of the first aspect, a circuit configuration corresponding to a method different from that of the second aspect can be adopted as a method of generating an image, and a more accurate and appropriate motion can be obtained. Vector can be detected. In addition, by dividing into two, the output load can be reduced, and the design of the circuit configuration can be made easier.

Effects corresponding to claim 4: Claims 2 and 3
In addition to the effects described above, the configuration corresponding to the odd field and the even field makes it possible to provide a motion vector detecting circuit suitable for interlaced scanning image generation.

Effect corresponding to claim 5: In addition to the effects of claims 2 to 4, it is also possible to detect a motion vector for the entire frame.

[Brief description of the drawings]

FIG. 1 is a diagram showing an embodiment of a motion vector detection device according to the present invention.

FIG. 2 is a diagram for explaining an arrangement of pixels and a first input order in a block matching operation according to the circuit configuration of the embodiment shown in FIG. 1;

FIG. 3 is a timing chart regarding input of each pixel value of a target pixel in the embodiment shown in FIGS. 1 and 2;

FIG. 4 is a timing chart for inputting each pixel value in a search area in the embodiment shown in FIGS. 1 and 2;

FIG. 5 is a diagram for explaining an operation process by showing data contents of RB and RC registers and delay elements in the embodiment shown in FIGS. 1 and 2 according to operation timing in each PE.

FIG. 6 is an enlarged partial view showing an A1 part in FIG. 5;

FIG. 7 is an enlarged partial view showing a B1 part in FIG. 5;

FIG. 8 is an enlarged partial view showing a C1 part in FIG. 5;

FIG. 9 is an enlarged partial view showing a D1 part in FIG. 5;

FIG. 10 is a diagram for explaining a second input order in the block matching operation according to the embodiment of the present invention.

FIG. 11 is a diagram showing another embodiment of the motion vector detecting device according to the present invention.

FIG. 12 is a timing chart for inputting each pixel value of a target pixel in the embodiment shown in FIGS. 11 and 10;

13 is a timing chart for inputting each pixel value in a search area when the input order shown in FIG. 10 is adopted in the embodiment shown in FIG. 11;

FIG. 14 shows the data contents of the RC register and the delay element in each PE in the embodiment shown in FIGS. 11 and 10 according to the operation timing, and is a first diagram (FIG. 20 (second See Fig.).

FIG. 15 is an enlarged partial view showing an A2 part in FIG. 14;

FIG. 16 is an enlarged partial view showing a B2 part in FIG. 14;

FIG. 17 is an enlarged partial view showing a portion D2 in FIG. 14;

FIG. 18 is an enlarged partial view showing an E2 part in FIG. 14;

FIG. 19 is an enlarged partial view showing an F2 part in FIG. 14;

FIG. 20 is a second diagram (FIG. 14 (first diagram) for explaining the operation process, showing the data contents of the RC register and the delay element in each PE in the embodiment shown in FIGS. 11 and 10 according to the operation timing; See Fig.).

FIG. 21 is an enlarged partial view showing an A3 part in FIG. 20;

FIG. 22 is an enlarged partial view showing a B3 part in FIG. 20;

FIG. 23 is an enlarged partial view showing a portion D3 in FIG. 20;

FIG. 24 is an enlarged partial view showing a portion E3 in FIG. 20;

FIG. 25 is an enlarged partial view showing an F3 part in FIG. 20;

FIG. 26 is a diagram showing another embodiment of the motion vector detecting device according to the present invention.

FIG. 27 shows R in each PE in the embodiment shown in FIG. 26;
FIG. 9 is a diagram for illustrating data contents of a C register and a delay element according to operation timing, and explaining an operation process.

FIG. 28 is an enlarged partial view showing an A4 part in FIG. 27;

FIG. 29 is an enlarged partial view showing a B4 part in FIG. 27;

FIG. 30 is an enlarged partial view showing a C4 part in FIG. 27;

FIG. 31 is an enlarged partial view showing a D4 part in FIG. 27;

FIG. 32 is an enlarged partial view showing an E4 part in FIG. 27;

FIG. 33 is an enlarged partial view showing an F4 portion in FIG. 27;

FIG. 34 is a block diagram in a case where inputs of pixel values in a search area are made into two systems in the embodiment shown in FIG. 1;

FIG. 35 is a diagram illustrating a case where the input order of the pixel values of the target block is reversed in the embodiment shown in FIG. 1;

FIG. 36 is a block diagram showing a circuit configuration when the input order of the pixel values of the target block is reversed in the embodiment shown in FIG. 1;

FIG. 37 is a block diagram illustrating an example of a conventional motion vector detection device.

FIG. 38 is a diagram for explaining an arrangement of pixels and an input order when performing a block matching operation in the conventional example shown in FIG. 37;

FIG. 39 is a diagram for explaining pixel input and calculation timing in a search area in the conventional block matching operation shown in FIG. 37;

[Explanation of symbols]

1 ... input terminal (input terminal for inputting pixel value), 2
... RA register (register for holding pixel values in the block of interest), 3... RB register (register for holding pixel values in the search range), 4... Arithmetic unit (for calculating the absolute value of the difference) Arithmetic unit), 5, 10 ... adder, 6
... RC register (register for holding intermediate results), 7 ... processing element (PE), 8 ... delay element, 9 ... minimum value detection circuit, 12 ... RE register (holds pixel values in the search range in two series , 101... A register, 102.
3 Processor, 104 S port, 105 Pixel input circuit in block of interest, 106 RA port, 107 R
B port, 108 ... pixel input circuit in search range, 109 ...
Adder, 110 ... B register, 111 ... accumulator circuit,
112: minimum value detection circuit, 201: gate, 301: selector, 302: ROM, 303: counter.

Claims (5)

[Claims] 1. A block consisting of M × N pixels in an image is defined as a coded block, and a candidate block for the coded block is searched for in a search range on a reference image by a block matching method. A motion vector detection device that detects a motion vector based on the position of the candidate block shown in the input block, wherein an input unit that inputs M × N pixel values in the encoded block and pixel values in the search range; A cascade-connected M × N first register for holding, for each pixel, each pixel value in an encoding block input from an input unit, and each pixel value in the search range input from the input unit Cascaded second register for holding the
Calculating the absolute value of the difference between the output of the first register and the output of the second register for each output of the first register.
N arithmetic units, M × N adders each of which is cascade-connected to perform cumulative addition, a third register for holding the cumulative addition result performed by the adder for each adder, (M-1) delays the output of the third register by a predetermined cycle of operation timing so that the output of the arithmetic unit and the output of the third register are added at a predetermined operation timing in the unit. Or (N-1)
Delay means, and a minimum value detection circuit for detecting a candidate block having a minimum value from at least a part of the cumulative addition results of the M × N adders for each candidate block in the search range. A motion vector detecting device characterized in that: 2. The M × N number of adders, each of which performs cascade-connected cumulative addition, and a third register for holding the cumulative addition result performed by each adder for each of the adders. X (N / 2) units as one set, the whole is divided into two sets, cumulative addition is performed in each of the sets, and first and second candidate blocks each detecting a candidate block having the minimum value from the obtained cumulative addition results. The motion vector detection device according to claim 1, further comprising a second minimum value detection circuit. 3. An M × N fourth register for delaying an intermediate result of the cumulative addition held in the third register is added to each of the third registers. (M-1)) and the cascade-connected M × N adders that perform cumulative addition, the third register, the fourth register, and the delay unit that hold the result of cumulative addition. , (M / 2) × N adders and (M / 2) × N third registers and (M /
2) The entirety is divided into two sets with one set of × N fourth registers and (M−1) delay means, and cumulative addition is performed for each set. 2. The motion vector detecting device according to claim 1, further comprising a first and a second minimum value detecting circuit for respectively detecting a candidate block indicating a minimum value. 4. The motion vector detecting device according to claim 2, wherein each of the two divided sets corresponds to an odd field and an even field of the encoded block. 5. A further adder for obtaining the sum of the cumulative additions obtained for the two divided sets, and a third minimum value for detecting a candidate block having the minimum value from the cumulative addition result of the further adder. 5. The motion vector detecting device according to claim 2, further comprising a detecting circuit.