JPH05268593A - Difference absolute sum/difference square sum parallel arithmetic operation device - Google Patents

Abstract

PURPOSE:To reduce number of output ports of a memory and to eliminate the need for a selector selecting a picture element to be sent to each arithmetic operation circuit and a shift register used to shift picture elements of a current picture element block read from the memory for each cycle. CONSTITUTION:An L1.L2 norm parallel arithmetic operation unit calculating a difference absolute sum (L1) norm and a difference square sum (L2) norm between plural picture element blocks deviated by one picture element each in the horizontal direction segmented from a preceding frame and a picture element block segmented from a current frame in parallel is provided with a means which latches picture elements of a preceding frame to memories 7-0-7-3 having plural outputs port able to read plural data at once at consecutive addresses and reads plural picture elements having consecutive addresses at once, segments simultaneously picture elements of a picture element block from a current frame and transfers the segmented picture elements of the picture element block to all of plural computing elements 22-0-22-3 whose number is the same as the number of the port.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a sum of absolute differences (hereinafter referred to as L1 norm) or a difference square operator (which will be referred to as "L1 norm"), which is the basis of block matching required for motion compensation, which is one of moving image coding algorithms. Hereinafter, the present invention relates to an L1 · L2 norm parallel arithmetic device for performing parallel calculations.

[0002]

2. Description of the Related Art (1) L1 / L2 Norm FIG. 2 is a diagram for explaining an example of a pixel block which is a target of a conventional L1 / L2 norm calculation. In this example,
The pixel block has a size of 8 × 8. The L1 · L2 norm is calculated by the following equations (1) and (2) between the pixel block 1 in the current frame and the pixel blocks 3 to 5 in the previous frame 2.

[0003]

[Equation 1]

[0004]

[Equation 2]

Here, Xj (i) is a pixel in the pixel blocks 3 to 5 cut out from the previous frame 2. Also,
Y (i) is the pixel block 1 cut out from the current frame
It is the inside pixel. j represents a number given to a plurality of preceding pixel blocks. In the case of FIG. 2, the pixel blocks of j = 3, 4, and 5 are shifted by one pixel in the horizontal direction, and most of the pixels are common. However, actually, the shift between the plurality of previous pixel blocks to be the target of the L1 or L2 norm calculation is not limited to one pixel in the horizontal direction. There may be a case where the number of pixels is shifted in the horizontal or vertical direction. The difference between the L1 norm and the L2 norm is only that the difference between two pixels is calculated and then the absolute value is taken or multiplied. Therefore, only the L1 norm will be described below.

Regarding the technique relating to the L1 and L2 norms, for example, K. Kikuchi, Y. Nukada, Y. Aoki, T. Kanou,
Y.Endo, T. Nishitani, “A Single-Chip 16-bit 25ns V
ideo / Image Signal Processor ”ISSCC Digest Technic
al Paper, pp.170-171, Feb 1989.

(2) First Example of Prior Art FIG. 3 shows an example of a pixel block for which the L1 norm is to be calculated. Here, for simplification, the size of the pixel block is 4 × 4. The L1 norm is calculated for the pixel block 6 in the area surrounded by the broken line in the figure. Note that X
5, X6, X7, X8, X21, X22, ... Are respectively X5 (0), X5 (1), X5 in the above formula (1).
(2), X5 (3), X5 (4), X5 (5), ..., Y
0, Y1, Y2, Y3, Y4, ... are each Y
(0), Y (1), Y (2), Y (3), Y (4), ... The L1 norm for this pixel block 6 is set to 4
FIG. 4 shows a circuit configuration of a first example of the prior art in which parallel calculation is performed. The pixels of the previous frame 2 are 4-bank memory 7-
It is located at 0-7-3. In the memories 7-0 to 7-3, the memory 7-0 has the address 0, the memory 7-1 has the address 1, and the memory 7-
Addresses are given to 2 at address 2, 7-3 at address 3, memory 7-0 at address 4, and memory 7-1 at address 5, so that data at consecutive addresses 4 can be read at once. Pixel X0 is located at address 0, X1 at address 1, X2 at address 2, ... At the same address as the subscript. This memory 7-
The four data read from 0 to 7-3 are shifted by the four data rotation circuit 9 so that the data at the lowest address is input to the difference absolute value calculator 11-0 at the left end. The pixels in the current pixel block 1 are stored in the memories 7-0 to 7-3.
It is placed at the same address as the subscript on the memories 8-0 to 8-3 having the same configuration as. The operation of the 4-data rotation circuit 9 is also the same. Therefore, as shown in the figure, | X5-Y0 in the absolute difference value calculators 11-0 to 11-3
|, | X6-Y1 |, | X7-Y2 |, | X8-Y3 |
Can be calculated simultaneously, and finally the L1 norm for the previous pixel block 6 can be obtained in the accumulator 13.

Regarding the technique relating to the first example of the prior art, for example, Minami, Yamauchi, Tashiro, Suzuki, Kasai, Takahashi,
Endo, Hamaguchi, "Data flow control of video signal processor IDSP", 1991, IPSJ, ICD91-12, pp.2
It is described in 5-32.

(3) Second Example of Prior Art FIG. 5 shows a second example of the pixel block for which the L1 norm is to be calculated. Pixel block 6 shown in the first example
In addition to the above, a pixel block 1 that is shifted by one pixel in the horizontal direction
5,16,17 are shown. FIG. 6 shows a circuit configuration of a second example of the prior art for calculating the L1 norm for these four pixel blocks 6, 15, 16, 17 in four parallels.
Pixel of previous frame 2 is memory 1 with 2 output ports
It is placed at the same address as the subscript above 8. The pixel in the current pixel block 1 is placed at the same address as the subscript on the memory 19. Pixels surrounded by broken lines are read from the port 0 of the memory 18, and pixels surrounded by straight lines are read from the port 1. Selectors 21-0, 21-1, 21-
2 are pixel blocks 17 and 1 from these pixels, respectively.
Select pixels 6 and 15. Also, register 20-0 to
Reference numeral 20-3 is a shift register, which shifts the pixels of the current pixel block 1 read from the memory 19 for each cycle. Therefore, the absolute difference value calculator 22-0 to 22-
3 calculates the absolute value of the difference between the pixel blocks 17, 16, 15, 6 and the current pixel block 1, respectively, and the accumulator 2
The L1 norms of the pixel blocks 17, 16, 15, 6 and the current pixel block 1 can be obtained in 3-0 to 23-3.

The technique relating to the second example of the prior art is, for example, K. Yang M. Sun L. Wu "A Family VLSI Design for th.
e Motion Compensation Block Algorithm ”IEEE Tran
s. on Circuits and Systems, vol.36, pp.137-1325, O
ct. 1989.

[0011]

However, in the first example of the prior art, in the case of 4-parallel operation, the previous frame 2
There is a problem that 4 ports are required to read the pixels of 4 and 4 ports are required to read the pixels of the current pixel block 1, that is, a total of 8 output ports are required, and a memory having a large number of output ports is required. Also, in order to accumulate the absolute difference value,
There is a problem that a path for connecting the adder 12 in a tree shape is required.

In the second example of the prior art, a 2-port memory 18 is required to read out two pixels of the previous frame 2 at the same time, and selectors 21-0 to 21-21 for selecting the pixels to be sent to the individual arithmetic circuits. There is a problem that -2 is required. Further, there is a problem that the shift registers 20-0 to 20-3 are required to shift the pixels of the current pixel block 1 read from the memory 19 every cycle.

The present invention has been made to solve the above problems, and an object of the present invention is to provide a technique capable of reducing the output ports of a memory.

Another object of the present invention is to eliminate the need for a selector for selecting pixels to be sent to individual arithmetic circuits and a shift register for shifting the pixels of the current pixel block 1 read from the memory for each cycle. It is to provide the technology that is possible.

The above and other objects and novel features of the present invention will become apparent from the description of this specification and the accompanying drawings.

[0016]

In order to achieve the above-mentioned object, the present invention relates to a horizontal direction 1 cut out from a front frame.
In an L1 and L2 norm parallel arithmetic unit that calculates in parallel the L1 or L2 norm between a plurality of pixel blocks that are shifted pixel by pixel and the pixel block that is cut out from the current frame, a plurality of data placed at consecutive addresses A memory having a plurality of output ports that can be read to, a pixel holding unit that holds the pixels of the previous frame on the memory, and a plurality of pixels with consecutive addresses read from the pixel holding unit at once, At the same time, it is provided with means for cutting out the pixels of the pixel block from the current frame, and means for broadcasting the pixels of the pixel block cut out by the cutting means to all of the plurality of arithmetic units of the same number as the number of ports. ..

The arithmetic unit is characterized by comprising a differential absolute value arithmetic unit or a differential square arithmetic unit and an accumulator.

[0018]

According to the above-mentioned means, a plurality of banks of memory used in the first example of the prior art and a data rotation circuit are used, and a plurality of data placed at consecutive addresses can be read at one time. In memory,
Holds the pixels of the previous frame, reads out a plurality of pixels with consecutive addresses at once, and sends them in parallel to a plurality of arithmetic circuits consisting of a difference absolute value calculator or a difference square calculator and an accumulator, At the same time, the pixels of the current pixel block are broadcast to all the arithmetic units, so that only one port is required to read the pixels of the current block from each memory, and the number of memory ports required is +1 for the arithmetic parallelism. Is significantly reduced as compared with the first example. Further, it is not necessary to combine the adders in a tree shape to accumulate the absolute difference values.

Also, a shifter for shifting the pixels of the current pixel block read from the memory and the selector for selecting the pixels to be sent to the individual arithmetic circuits, which is required in the second example of the prior art, for each cycle. No need for registers. Also, each memory may have only one output port, 2
The limitation of port memory is gone.

[0020]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an L1 / L2 norm parallel arithmetic unit according to an embodiment of the present invention. Similarly to the description of the second example of the prior art described above, the pixel blocks 6, 15, 16, 17 shown in FIG.
The case where the L1 norm is calculated for

In FIG. 1, reference numerals 7-0 to 7-3 denote pixels for holding pixels in a previous frame having a 4-bank structure, 9 denotes a 4 data rotation circuit, 10 denotes a register, 12 denotes an adder, and 14
Is a memory for writing L1 norm, 19 is a memory for holding pixels in the current pixel block, 22-0 to 22-3 are absolute difference value calculators, 23-0 to 23-3 are accumulators, 24-1
24-3 and 25-1 to 25-3 are 2.1 selectors.

First, from the memories 7-0 to 7-3 of the four-bank configuration used in the first example of the prior art, four pixels X
8, X5, X6, X7 are read and rearranged in the order of lower addresses X5, X6, X7, X8 by the 4 data rotation circuit 9 used in the first example of the prior art, and the absolute difference value is read. It is sent to the computing units 22-0 to 22-3.

The pixel Y0 of the current pixel block 1 read from the memory 19 is the absolute difference value calculator 22-0 to 22-3.
Will be broadcast on. Next, 4 pixels X from the memory 7-0 to 7-3
8, X9, X6, and X7 are read out, and the data rotation circuit 9 has the lowest address X6, X7, X8, and X9.
And are sent to the absolute difference calculators 22-0 to 22-3. From the memory 19, the pixel Y1 is broadcast to the absolute difference calculators 22-0 to 22-3. In the same manner, the absolute difference value calculators 22-0 to 22-3 similarly calculate the absolute difference values between the pixels of the pixel blocks 6, 15, 16, 17 and the pixel of the current pixel block 1, and the accumulator 23
The L1 norm can be obtained from -0 to 23-3. In addition,
In order to calculate the L1 norm without interruption, the accumulators 23-1 to 23-3 are duplicated as shown in FIG.
It is necessary to prevent the calculated L1 norm from being overwritten until it is written in the memory 14.

As can be seen from the above description, according to the present embodiment, only one port is required to read out the pixels of the current block from each of the memories 7-0 to 7-3, and the required number of memory ports is required. Is the degree of parallel operation +1, which is the first
It is greatly reduced compared to the example. Further, it is not necessary to combine the adders 12 in a tree shape to accumulate the absolute difference values.

Further, the selectors 21-0 to 21-2 for selecting pixels to be sent to the individual arithmetic circuits required in the second example of the prior art, and the pixels of the current pixel block 1 read from the memory 19 The shift registers 20-0 to 20-3 for shifting each of the cycles are eliminated.
Further, each memory may have only one output port, and the limitation of 2-port memory is removed.

In the above-mentioned embodiment, 4 × is used for simplicity.
Although only the case of performing four parallel operations on four pixel blocks has been described, the present invention can be applied to any degree of parallelism and any pixel block size.

Although the present invention has been specifically described based on the embodiments, it is needless to say that the present invention is not limited to the above embodiments and various modifications can be made without departing from the scope of the invention. Absent.

[0029]

As described above, according to the present invention, only one port is required for reading out the pixels of the current block from each memory, and the required number of memory ports is +1 for the arithmetic parallelism. This is a significant reduction compared to the first example of the prior art. Further, it is not necessary to combine the adders in a tree shape to accumulate the absolute difference values.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an L1 · L2 norm parallel arithmetic unit for full search according to an embodiment of the present invention,

FIG. 2 is a diagram showing a pixel block and a current block in a previous frame for explaining formulas for calculating an L1 norm and an L2 norm.

FIG. 3 is a diagram showing a pixel block that is a calculation target for explaining a first example of the related art;

FIG. 4 is a circuit configuration diagram for explaining a first example of the related art;

FIG. 5 is a diagram showing a pixel block that is a calculation target for explaining a second example of the related art;

FIG. 6 is a circuit configuration diagram for explaining a second example of the related art.

[Explanation of symbols]

1 ... Current pixel block, 2 ... Previous frame, 3, 4, 5,
6, 15, 16, 17 ... Pixel block in the previous frame,
7-0 to 7-3 ... Memory for holding pixels in previous frame of 4 banks, 8-0 to 8-3 ... Memory for holding pixels in current pixel block of 4 banks, 9 ... 4 Data rotation circuit, 10 ... Register, 11-0 to 11-3, 22-0 to 2
2-3 ... Difference absolute value calculator, 12 ... Adder, 13, 23-
0-23-3 ... Accumulator, 14 ... L1 norm writing memory, 18 ... 2-port memory for holding pixels in previous frame, 19 ... Memory for holding pixels in current pixel block, 20-0 to 20-3 ... 4 Registers constituting a shift register, 21-0 to 21-2, 24-1 to 24-3, 25
-1 to 25-3 ... 2.1 selector.

Continuation of front page (51) Int.Cl. ⁵ Identification number Office reference number FI technical display location G06F 15/70 410 9071-5L

Claims (2)

[Claims] 1. A horizontal 1 cut out from a previous frame
The difference absolute value sum / difference sum of squares parallel calculation device that calculates the sum of absolute differences or the sum of squared differences in parallel between a plurality of pixel blocks that are shifted pixel by pixel and the pixel block cut out from the current frame A memory having a plurality of output ports capable of reading a plurality of placed data at a time, a pixel holding unit for holding a pixel of a previous frame on the memory, and a plurality of units having consecutive addresses from the pixel holding unit. Of the pixels of the pixel block are read out at the same time, and the pixels of the pixel block are simultaneously cut out from the current frame, and the means of broadcasting the pixels of the pixel block cut out by the cutting out means to all of the plurality of arithmetic units having the same number as the number of ports. A difference absolute value sum / difference sum of squares parallel arithmetic operation device comprising: 2. The difference absolute value sum / difference sum of squares parallel arithmetic operation device according to claim 1, wherein the arithmetic unit comprises a difference absolute value arithmetic unit or a difference squared arithmetic unit and an accumulator. Difference absolute value sum / difference sum of squares parallel calculation device.