JPH02100577A - Discrete cosine converting device - Google Patents

Abstract

PURPOSE:To perform a matrix operation at high speed through the use of a few multipliers by using a fact that the number of the kinds of coefficients to be read out from a coefficient storing means are the half of the number of picture data in respect of the picture data of the portion of one direction of a block, and switching selection using an adding and subtracting selecting means at every readout of said coefficient. CONSTITUTION:A latch 30 holds data to be inputted respectively from the latches 21,22...28 because the clock signal of eight times shorter period than the clock signal to be inputted to the latches 21,22...28 is sent from a frequency divider 18. Accordingly, the portion of eight pieces of the clock signals sent from the clock generation circuit 16 is inputted to the latches 21,22...28, and after eight pieces of picture data x00, x10, x20...x70 are held in the latches 21,22...28, these data are inputted and latched to/in the latch 30 by the clock signal of the eight times shorter period to be sent from the frequency divider 18 to the latch 30. The outputs of eight pieces of picture element data are connected respectively to the inputs of four pieces of adders 71...74 and four pieces of subtracters 81...84.

Description

TECHNICAL FIELD The present invention relates to a discrete cosine transform device, and more particularly to a discrete cosine transform device that performs two-dimensional discrete cosine transform on each block of image data obtained by dividing digital image data.

When storing digital image data in a memory, various types of encoding are used to reduce the amount of data and the capacity of the memory.

As such encoding, for example, two-dimensional discrete cosine transform is encoded as follows. Image data constituting one screen is divided into blocks of a predetermined size, and a matrix P is an array of data constituted by data of each pixel constituting the block. An operation is performed on this matrix P using a transformation matrix C and a transposed matrix CT of C.

Two-dimensional discrete cosine transformation after calculation e! ! F
is given by F=Cφ P · CT.

When performing two-dimensional discrete cosine transformation on image data that has been divided into blocks in this way, the pixel data constituting one screen is divided into a predetermined number of blocks, for example, 8x8 blocks, and the It is necessary to read the pixel data for each block and perform the two-dimensional discrete cosine transformation described above. Therefore, when reading out image data from a memory that stores one screen of image data, pixel data in each block must be read out, which has the drawback of requiring complicated processing for address control during readout.

For example, there is a device disclosed in Japanese Patent Application Laid-Open No. 81-135283 that reads pixel data for each divided block and performs two-dimensional discrete cosine transformation. There is a problem in that the calculation requires time proportional to the number n of rows or columns of data constituting the block matrix, and the calculation is not accelerated.

[An object of the present invention is to provide a discrete cosine transform device that solves the problems of the prior art and can perform two-dimensional discrete cosine transform at high speed without requiring complicated address control to read out one image data.] The purpose is to

DISCLOSURE OF THE INVENTION According to the present invention, a discrete cosine transform device divides digital image data representing one screen into a plurality of blocks and performs two-dimensional discrete cosine transform on the image data of each block. An image data storage means that can store image data and read it out in the horizontal and vertical directions of the screen, an image data storage means that can store the image data read from the storage means for at least one direction of a block, and an image data storage means. addition/subtraction selection means that performs either addition or subtraction for each symmetrical position of the image data in one direction of the pro-nk read out in parallel from the means; and two-dimensional discrete cosine transformation for the image data of the block. a coefficient storage means for storing coefficients used to perform the calculation, and data subjected to either addition or subtraction output from the addition gn selection means and the coefficient read from the coefficient storage means are multiplied. It has a multiplication means and an addition means for adding the data multiplied by the multiplication means, and the coefficients read from the coefficient storage means are half the number of image data for the image data in one direction of the block. 1 type, and the selection by the addition/subtraction selection means is switched every time a coefficient is read.

DESCRIPTION OF EMBODIMENTS Next, embodiments of a discrete cosine transformer according to the present invention will be described in detail with reference to the accompanying drawings.

FIG. 1 shows an embodiment of a discrete cosine transform device according to the present invention.

This device has a memory 12 that stores image data for l@ planes. Image data constituting one screen as shown in FIG. 2 is input to the memory 12 from a signal source such as an imaging device or an external storage device through the input terminal 10, and is stored therein. The memory 12 reads out the stored pixel data for one screen in the vertical direction as shown in FIG. 3B, or in the vertical direction as shown in FIG. In the case of reading out in the horizontal direction as shown in FIG. 3B, the second A
As shown by arrow A in the figure and FIG. 2B, the pixel data of the first column is X 00. x 10, x 20,...-x V
-10, and after being read from the top to the bottom of the screen, the pixel data in the second column is xQl, xll, x21, -x'J
-11 is read out, and all pixel data are read out in the same way. In the case of horizontal readout shown in FIG. 4B, as shown by arrow B in FIGS. i2A and 2B,
The pixel data of the first row is xoo, x 01. x 02
, ... xOH-1, and after being read from the left to the right of the screen, the pixel data on the second line is xlo, xll, x12, .
... xlH-1, and all pixel data are read out in the same way.

Pixel data read from the memory 12 is sequentially input from the latch 28 side to eight latches 21, 22, . . . , connected in series, and is held therein.

In this embodiment, the image data is 8x8 as shown in Figure 3A.
In order to perform two-dimensional discrete cosine transformation by dividing into blocks each consisting of pixels, eight latches 21, 22,
. . 28 are provided, but a different number of latches may be provided depending on the size of the block to be divided.

The latches 21, 22, . . . , 28 represent the clock generation circuit 1
Data holding and reading operations are performed by a clock signal sent from 6. For example, as shown in Figure 2B,
The pixel data of the first row is xoo, xlO1x20°...
When read out in the order of xV-10, the pixel data x00 is input to the latch 28 by the first clock signal, and the pixel data xlo is input to the latch 2B by the held 0th order clock signal. , latch 2
8, pixel data is sent to a latch adjacent to latch 28. Similarly, eight pieces of pixel data x00, xlo, x20, . . . x70 are held in latches 21, 22, .

Each output of the latches 21, 22, . . . 28 is connected to the latch 30.
is connected to the input of A clock signal is input to the latch 30 from the frequency divider 18 . The frequency divider 18 is a frequency divider that divides the frequency of the clock signal sent from the clock generation circuit 16 into n times the period. It is converted into a clock signal and output to the latch 30.

The latches 30 are connected to the latches 21, 22, .
- Holds the data input from 28 respectively. Therefore, eight clock signals sent from the clock generation circuit 18 are input to the latches 21, 22, . . . , and eight pixel data X0O1xlO1x20, .
x? After 0 is held in the latches 21, 22, . .

The output of the 8 pixel data from the latch 30 is transmitted to 4 adders 71...74 and 4 subtracters 81...84.
are connected to the respective inputs. The first output of the latch 30 outputs data xoO and is connected to one input of the adder 71 and the subtracter 81, respectively. The latch 30 is connected to the other input of the adder 71 and the subtracter 81.
The eighth output of is connected and the data x? 0 is input.

The second output of the latch 30 is the data xlo,
It is connected to one input of adder 72 and subtracter 82, respectively. The other input of the adder 72 and the subtracter 82 is connected to the seventh output of the latch 30, and the data x
80 is input. Similarly, adder 73 and subtracter 8
3 is connected to the third and sixth outputs of the latch 30, and the adder 74 and the subtracter 84 are connected to the fourth and fifth outputs of the latch 30.

8 pixel data x00, xl held in latch 30
o, x20, -.
74 and subtracters 81...84, respectively.

That is, as shown in the figure, an adder 71 and a subtracter 8
1 receives data xOO and x70, adder 72 and subtractor 82 receive data xlO and x60, adder 73 and subtractor 83 receive data x20 and x50, and adder 74 and subtracter 84 receive data x30. and x40 are input, respectively. Therefore, for example, in the adder 71, the data X00 and x70 are added, and in the subtracter 81, the data X00 to x? O is subtracted.

The outputs of adder 71 and subtracter 81 are connected to switch 91, which connects other adders 72, 73, 74 and subtracter 82.
．． Similarly, the output of 83.84 is also connected to switch 92.93.9.
Connected to 4. The outputs of the switches 91...94 are connected to multipliers 41...44. switch 91
...94 are controlled all at once by a control signal from the switch control section 90, and select the outputs of the adders 71...74 or the outputs of the subtracters 81...84, and select the outputs of the multipliers 41, .
...44 respectively.

A coefficient generator 5 is connected to the other input of the multipliers 41, . . .
Coefficients CkO to Ck3 sent from 1, . . . , 54 are input. The coefficient generators 51, . . . , 54 generate coefficients CkO1, .
) are generated and output to multipliers 41, . . . , 44, respectively. Note that the coefficient CkO and C(':) in FIG. 1 mean the same thing.

In this example, the block size is 8x8, and as will be described later, the coefficients are Vessel 51. The coefficients generated by . ((2j
+1)iπ/2N). Here, W(i) = 1 /σ (when i=0) 1
(When i≠O).

First 8 pixel data X0O1xlo, x20,...
・x? When O is input to the latch 30, as described above,
Data x00 and x70 are sent to adder 71 and subtracter 81, and data xlo and x60 are sent to adder 72 and subtracter 82.
, the data x20 and x50 are sent to the adder 73 and the subtracter 8.
3, data x30 and x40 are input to an adder 74 and a subtracter 84, respectively, and addition is performed in the adders 71...74, and subtraction is performed in the subtracters 81...84.

First 8 pixel data X0O1xlo, x20,...
- When addition and subtraction by x70 are performed, the switches 81 . . . 94 are connected as shown in the figure by a control signal from the switch control section 90. therefore,
The outputs from the adders 71...74 are sent to the multipliers 41...4
Output to 4. i.e. x COI x 70, x
10+ x Go, x20+ x50. x30+ x4
0 is sent to multipliers 41 and 44, respectively.

At this time, the coefficient generator 51 . ...54, the first four coefficients COO1...C03 (k=0) are multiplier 41...
44, and the following multiplications are performed respectively.

COOx (x00+x70) COI x (xlo+x80) CO2x (x20+x50) CO3x (x30+x40) The outputs from the multipliers 41, . When the outputs from the multipliers 41, .

z OO= COOx COI COlx lo+ C
02x 20+ C03x 30+ C0Ox? O+
C01xEiO+ C02x50+ C03x40
This Zoo is z OO= C00x00+ C01x 10+ C when the coefficient is CkOl...Ck7
02x20+ C03x30+C04x40+C05x
50+C013x80+CO? This value is the same as that expressed by x70. The reason for this will be explained next.

The formula representing the coefficient C4j is as follows. Therefore, it can be seen that Ci N-1-'j has the same absolute value as C1j, and only differs in sign depending on whether i is an even number or an odd number. That is, when i is an even number, Ci N-1-j = Cij, and when i is an odd number, Ci N-1j = -Cij.

When calculating the above data zoO, data x
OO1xlO1x20,...x 70 has i of xij set to 0, so i is an even number. Therefore, in this case, the relationship Ci N-1j = Cij holds true, so the coefficient C00 used for X00 and the coefficient CO7 used for X70 are equal, so the coefficient 000,...
Using only C03, xoo and X70, xlo and x f3
0. Zoo can be found by multiplying x20 and X50, and X30 and X40 using the same coefficients.

Next, in response to the clock signal from the clock generation circuit 16, the switches 91...94 are switched to positions opposite to those shown in the figure, and the outputs x00- from the subtracters 81...84 are
x 70, x 10- x 80, x, 2O-X50
, x 30 - x 40 are respectively multipliers 41 . ...
Sent to 44. On the other hand, the next four coefficients Cl01...C13 (k=1) are input from the coefficient generators 51, . . . to the multipliers 41, . .

Multiplier 41. ... 44, and the multiplied data is added in a multistage adder 80 to obtain the next data zlO.

Z lo= C10x oo+ Cllx to+ C
I2x 20+ C13x 30- CIOx 70-
Cllx Go -C12x 50- C13x 4
0 This zlo has a coefficient of CkOl...Ck? z 10= C10x OO+ Cllx 10+
CI2x 20+ C13x 30+ C14x a
o+ C15x 50+ C18x eo+ CI7x
The value is the same as that represented by 70.

Similarly, for each clock signal, a coefficient generator 51, .
・Four coefficients CkO1...CK3 from 54 are multiplier 4
1...44 and sent alternately from the adder or subtracter x00, xlO1x20,...X7
The data is multiplied by 0 and added in the multi-stage adder 60 to obtain data as follows.

X20=C20x00+C21xlO+...-C20
x70...These data are respectively X20= C20x00+ C21x 10+ ・
...＋C2? x? 0z70=C70xOO+
C71x IO+... + Corresponds to C77x70.

The data zoo, zlo, X2 obtained in this way
0, . . . The memory 12 stores data zOO1zlo, z20, .
...When X70 is input, the original data X00, x
lo, X20. ...X70 is read out and stored in memory 12
Since these addresses are empty, the input data 200, zlo, X20, --.-z 70 is the original data x 00. It can be stored at the address where x10, X20,...X70 were stored.

Similarly, the undrawn data xol, xll, X2 in the second column
1. ...X71 is read out from the memory 12 and subjected to similar calculations to become data zo1. zll, X21
．． --...X71 and is stored in the memory 12 again.

By reading the pixel data in the vertical direction of the screen from the memory 12 as described above and performing calculations on the data, a matrix calculation is performed using the formula C@X=Z as shown in FIG. is required.

A timing chart showing the operation up to this point is shown in FIG. In the figure, the arrow indicates the delay time due to addition by the multi-stage adder 60.

When the reading of pixel data in the vertical direction of the screen from the memory 12 and the calculation thereof are completed, and the data as shown in FIG. 4A is stored in the memory 12, the data shown in FIGS. 2A and 2B is Pixel data is read out in the horizontal direction of the screen as shown by arrow B, and Ntn for this is performed.

As shown in FIG. 4B, first, pixel data zOO1z01
．． 202, . , and addition and subtraction are performed in the same manner as above. Switch 9 as in 111j
1...94 are controlled, and the added data or subtracted data is sent alternately to the multipliers 41...44. First, when the added data is sent, the coefficient generator 51
, . . . , the coefficients COO1 . . . CO3 (k=O) are output from the coefficients COO1 . Multiplier 41...
At 44, these pixel data and coefficients are multiplied,
The multi-stage adder 60 adds the data to obtain data yOO. yOO is y OO= COOz OO+ COlz
01+...+C00z07, y00=C00z00+C01zO1+--・+GO7
Corresponds to z07.

This data yOO is the aforementioned data zO in the memory 12.
It is stored at the address where O was stored.

Next, the next four coefficients Cl are generated from the coefficient generators 51, . . . , by the clock signal from the clock generator 16.
01...C13 (k=1) is the multiplier 41,...4
4, and data yot is output from the multistage adder 80.

yo1= C10z 00+ Cllz 01+...
-C10z 07-...(C10z00+C11z01
+・=+C17z07) Repeat the same operation to get y02= C20zOO+ C21zO1+・−・−C
20z0? ...-(C20z OO+ C21z 01
+...+C27zO? )y07= C70z0
0+ C71z01+-・--C70z07・-・(C
70z OO+ C71z 01+...+C77z0
7) are sequentially output and stored at the address in the first row of the memory 12.

Similarly, the pixel data zlo, zll, z1 on the second row
2, .
y17 and is stored in the memory 12 again.

Similarly, by repeating the reading and calculation of pixel data in the horizontal direction, the matrix calculation expressed by the formula 7 as shown in FIG. 7 is performed, and the matrix Y is obtained.

Therefore, by the following operation, matrix operation Y=C
@X-CT has been carried out.

As described above, according to the present device, it is possible to perform a two-dimensional discrete cosine transformation represented by y=c−x·CT.

Conventionally, the two-dimensional discrete cosine transform was
When performing the calculation expressed as = Z=C-Xt or Y=Z-CT, eight coefficients CkO are calculated for one pixel data.
, Ckl, . . . Ck7 and then add them, so one calculated data is obtained for every eight system clock signals, which requires calculation time proportional to the block size. And so. Therefore, since data cannot be obtained every system clock, there is a drawback that calculations cannot be performed at high speed.

On the other hand, according to this device, 8 pieces of data read out sequentially are latched, each of these 8 pieces of data is simultaneously multiplied by a coefficient, and then added. It is possible to obtain one piece of data each time, and matrix operations can be performed at high speed.

According to this device, only one type of coefficient C1j is stored in the coefficient generators 51, . All you have to do is read out the corresponding data and perform the calculation. Data Xij and data zij are stored in the memory 12
Since the read directions from the coefficient generators 51, .
...Even if the coefficient generated from 54 and multiplied by data zij is the same as the coefficient multiplied by data Xij, it acts as the transposed matrix CT of C, so as a result, the above A two-dimensional discrete cosine transformation can be performed on .

Moreover, according to this embodiment, the coefficient generators 51...54
The type of coefficient C1j generated from Ci N-1-j
= (-1)' Using the relationship of Cij, reduce Nx
In the case of N matrices, the number of multipliers 41...44 is N/2, so the number of multipliers that take up space can be reduced, making the device smaller. can.

Furthermore, according to the present device, one screen worth of pixel data stored in the memory 12 can be sequentially read out and processed as is, so there is no need for complicated address control as in the case of reading out data in blocks. Address generation is easy. Therefore, no program or complicated controller is required for address control.

According to the present invention, one screen's worth of pixel data can be read out sequentially and subjected to matrix calculation processing without being divided into blocks, so that complicated address control is not required for reading out pixel data.

Moreover, the read pixel data is held in units of numbers according to the size of the pixel, and the coefficient C is applied to these data.
Since multiplication is performed on the same plane and then addition is performed in consideration of the symmetry of 1j, matrix operations can be performed at high speed with a small number of multipliers.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of the discrete cosine transform device according to the present invention, FIGS. 2A and 2B are diagrams showing how the screen is divided into blocks, and FIG. 3A is a block diagram showing how the screen is divided into blocks. FIG. 3B is a diagram showing the order in which the pixel data in FIG. 3A is read out in the first step by the device in FIG. 1, and FIG. 4A is a diagram showing the order in which the pixel data in FIG. FIG. 4B is a diagram showing the order in which the pixel data in FIG. 4A is read out in the next step by the device in FIG. 1. FIG. 5 is a diagram showing pixel data read out in the order shown in FIG. 4B and subjected to arithmetic processing by the device shown in FIG. 1, and FIG. 6 is a diagram showing pixel data read out in the order shown in FIG. 7 is a diagram showing matrix calculations performed by the second operation of the device in FIG. 1; FIG. 8 is a timing chart showing the first operation of the device in FIG. 1. It is. Explanation of the symbols of the main parts, memory, address control unit, clock generation circuit, frequency divider, latch launch, multiplier, coefficient generator, multi-stage adder, adder, g-multiplier switch! 2゜14. 1B. 18. 2+, 22. ...28°30°41...44. 51...54゜60゜71...74゜81...84゜91...94゜So3A 3rd day 4-A India 1st dawn Oゝ口 N -m- 慴×日

Claims (1)

[Claims] 1. A discrete cosine transform device that divides digital image data representing one screen into a plurality of blocks and performs two-dimensional discrete cosine transform on the image data of each block, the device comprising: Accumulates digital image data representing the screen,
an image data storage means that can be read in the horizontal and vertical directions of the screen; an image data storage means that can store the image data read from the storage means for at least one direction of the block; and from the image data storage means. addition/subtraction selection means for adding or subtracting image data in one direction of the block read out in parallel for each symmetrical position; and performing two-dimensional discrete cosine transformation on the image data of the block. coefficient storage means for storing coefficients used for the multiplication of the data outputted from the addition/subtraction selection means, which has been subjected to either addition or subtraction, and the coefficient read from the coefficient storage means; and an addition means that adds data multiplied by the multiplication means, and the coefficients read from the coefficient storage means are calculated based on the image data for one direction of the block. 1. A discrete cosine transform device, characterized in that the type is half the number of data, and the selection by the addition/subtraction selection means is switched every time the coefficient is read. 2. In the apparatus according to claim 1, the coefficients read from the coefficient storage means are the same when reading the image data from the image data storage means in a horizontal direction and when reading it in a vertical direction. Characteristic discrete cosine conversion device. 3. The apparatus according to claim 1, wherein the addition/subtraction selection means adds symmetrical data for each symmetrical position of image data in one direction of the block read out in parallel from the image data holding means. an adding means, a symmetrical data subtracting means for subtracting image data in one direction of the block for each data at a symmetrical position, and selection for selecting one of the data output from the symmetrical data adding means and the symmetrical data subtracting means. A discrete cosine conversion device comprising means.