JPH0645948A - Orthogonal converter and reverse orthogonal converter - Google Patents

Abstract

PURPOSE:To reduce the number of hardwares for an orthogonal converter as compared to that of a DCT by setting up the values of a1, a2 in a conversion matrix consisting of 4 rows and 4 columns relating to quaternary orthogonal conversion differently from the values of respective elements in the orthogonal conversion of a quaternary DCT. CONSTITUTION:It is supposed that all input data, output data, data on the way of operation, etc., are expressed by binary digital values expressed as 2's complements. When a multiplier to be multiplied by data is 2<n> (n is an integer value), data are shifted only by n bits in the left or right direction while extending the code bits of the data. When the multiplier to be multiplied by data is 2<n>, the size of hardware for multiplication is reduced as compared with a multiplier other than 2<n>. Namely twice of multiplication other than the final multiplication for obtaining y1 to y4 can be obtained by prescribed bit shift. Thereby, two multipliers having large hardware size can be used and an orthogonal converter having small hardware size as compared with that of a quaternary DCT can be obtained.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an orthogonal transform device and an inverse orthogonal transform device used for high-efficiency coding of images and sounds.

[0002]

2. Description of the Related Art With the digitization of images and sounds, high efficiency coding techniques have become important. Orthogonal transform coding is an effective means of high efficiency coding. Commonly used orthogonal transforms include Hadamard transform, DCT (discrete cosine transformation) and the like.

The following equation is the transformation matrix [d
ij] (i, j = 1, 2, 3, 4).

[0004]

[Equation 1]

Here, Cp (p = 1, 2, 3) is

[Equation 2] Is represented.

The inverse transformation matrix [vij] is

[0007]

[Equation 3] Here, T indicates that it is a transposed matrix.

The fourth-order DCT is to obtain a column vector [yi] consisting of four output data from a column vector [xj] consisting of four input data by the following equation (i, j = 1, 2). 3, 4). [Yi] = [dij]  [xj] --- (1) However, in the calculation of the expression (1), a large number of 16 multiplications are required to obtain four output data. For this reason, high-speed algorithms have been published that reduce the number of multiplications.

FIG. 3 is a block diagram of a fourth-order high-speed DCT converter, which embodies the operation of the equation (1).

The broken line in the figure indicates positive and negative inversion, and Ci,

[Equation 4] , 1/2 is Ci times

[0011]

[Mathematical formula-see original document] This shows multiplication by multiplying by 1/2, and the intersection of the arrows indicates addition. With respect to ½ times, a result can be obtained by a 1-bit shift to the right, and therefore, excepting this, three multiplications are required in this case.

On the other hand, the Hadamard transform requires only a small amount of hardware required for the conversion device as compared with the DCT because the conversion can be performed only by adding and subtracting the input data, but for high efficiency encoding. When using it, the efficiency of concentrating the information of input data on specific output data is DCT.
It is known to be inferior to.

[0013]

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention
Then, the amount of hardware of the conversion device becomes large, and
The Hadamard transform has a problem of poor coding efficiency. The present invention aims to solve the above-mentioned problems of the prior art.

[0014]

In order to solve the above problems, the present invention provides an orthogonal transform device and an inverse orthogonal transform device having the following configurations.

The fourth-order orthogonal transformation is [yi] = [tij] .multidot.
[Xj] where [yi]: a column vector consisting of 4 output data [tij]: a transformation matrix of 4 rows and 4 columns [xj]: a column vector consisting of 4 input data i, j: 1, 2, 3, 4 It is an orthogonal transformation device that performs calculation, and among the four rows forming the transformation matrix [tij], the element of each row for two rows is a
1, a2 (real numbers) are arranged as a1, a2, -a2, -a1, a2, -a1, a1, -a2, and said a1: a2 is m: 1 or m:
An orthogonal transform device characterized by being set to 2 (m is a natural number).

An inverse orthogonal transform device for the above-mentioned orthogonal transform device, wherein a fourth-order inverse orthogonal transform is [yi] = z.
[Uij] · [xj] where [yi]: column vector consisting of 4 output data z: real value [uij]: transposed matrix [xj] of 4 × 4 conversion matrix [tij]: consisting of 4 input data An inverse orthogonal transform device characterized by performing calculation of column vectors i, j: 1, 2, 3, 4.

[0017]

BEST MODE FOR CARRYING OUT THE INVENTION The present invention enables an orthogonal transform apparatus having a relatively small amount of hardware and having an efficiency close to the coding efficiency of DCT by the above-mentioned configuration. Further, the hardware amount can be further reduced by adopting a configuration in which multiplication and addition / subtraction using a simple natural number as a multiplier are performed as multipliers of multiplications excluding the final multiplication for each orthogonal component. [Embodiment 1] A transformation matrix [tij] of a fourth-order orthogonal transformation which is an embodiment of the orthogonal transformation device of the present invention is shown in the following equation.

[0018]

[Equation 5] Here, if a1: a2 = m: n, then m = 2, n = 1
Is.

The orthogonal transform of this embodiment uses a column vector [xj] consisting of four input data x1, x2, x3, x4.

[0020]

[Equation 6] And a column vector [yi] consisting of four output data y1, y2, y3, y4

[0021]

[Equation 7] However, T represents transposition. And the conversion matrix [tij], [yi] = [tij]. [Xj] --- (2).

Further, the matrix [uij] representing the inverse transformation is

[0023]

[Equation 8] And

FIG. 1 is a block diagram of an embodiment of the orthogonal transformation apparatus of the present invention, and the drawing is similar to that of FIG.

Now, input data, output data, data in the middle of calculation, etc. are all two's complements.

Consider the case where the display is represented by a binary digital value. At this time, the multiplier to multiply the data

[Equation 9] , The sign bit of the data is expanded to n
Bits left (when n is positive) or right (when n is negative)
It is known that the data may be shifted in the direction.

As an example, consider multiplication of multiplier 2 and data 5. When the data 5 is represented by an 8-bit binary digital value in 2's complement notation,

[0028]

[Equation 10] Is. 2 × 5 is obtained by leaving the sign bit, shifting the other bits left by 1 bit, and inserting 0s in the vacant bits. Ie

[0029]

[Equation 11] Is. Is 0 in the empty bit.

Similarly, the multiplier

[Equation 12] And the data (-5) are multiplied, the data (-5) is

[0031]

[Equation 13] 4 × (−5) is obtained by leaving the sign bit and shifting the other bits leftward by 2 bits. Ie

[0032]

[Equation 14] Is. Is 0 in the empty bit.

From the above, the multiplier for multiplying the data is

When ## EQU9 ## the hardware for multiplication is smaller than that otherwise (especially when the multiplier is represented by a binary digital value and the number of bits having a value of 1 is large). It is self-explanatory. The configuration of FIG. 1 utilizes this fact.

That is, the orthogonal components y1, y2, y3, y
With the exception of the last multiplication to get 4, the remaining multiplications, double, can be obtained with the above bit shifts. In addition, the case of ½ times is excluded as in the case of FIG.

Therefore, in FIG. 1, the number of multipliers having a large hardware scale can be two, and the fourth-order DCT can be used.
It is possible to provide an orthogonal transform device having a smaller amount of hardware than that of the above. Further, in FIG. 1, as the multiplier of the last multiplication to obtain the orthogonal components y2 and y4,

,

[Equation 15] However, this may be approximated by 81/256 or the like. Further, the result obtained by two-dimensionally extending the conversion of the present invention with respect to the block [xij] composed of input data of vertical 4 pixels and horizontal 4 pixels using the input data as image data is vertical 4 data, horizontal 4 data. If the block [yij] consists of

[0037]

[Equation 16] Is. Therefore, the conversion of FIG. 1 may be performed twice, but in that case, 2 × 4 × 2 = 16 multipliers are required for the entire conversion. On the other hand, the conversion matrix of the conversion equivalent to the operation excluding the final multiplication for each output yj in FIG. 1 is [t'i
j]

[0038]

[Equation 17] By this [t'ij]

[0039]

[Equation 18] For each block [y'ij] consisting of vertical 4 data and horizontal 4 data as a result, y'ij =
By adopting a configuration for performing multiplication for yij, it is possible to reduce the total number of multipliers to 12.

Next, in the case of the inverse transformation using the inverse transformation matrix [uij], the above orthogonal component y1

, Y2, y3, y4 The last multiplier multiplied to obtain

[Mathematical formula-see original document] By multiplying the input data by [1/2], 1/2 and performing the operation represented by the transposed matrix of the matrix of [t'ij] on the multiplication results, the conversion described above is performed. The number of multipliers can be reduced as in the case of.

FIG. 2 is a block diagram of an embodiment of the inverse orthogonal transform device of the present invention.

By the way, human vision and hearing are generally less sensitive to high-frequency distortion. Therefore, in high-efficiency coding, a large weight is often given to the orthogonal component representing the low band, and a small weight is often given to the orthogonal component representing the high band. The weighting multiplication for that purpose may be performed on the output data of the orthogonal transformation, but it is also possible to use it as the final multiplication for obtaining the orthogonal components y1, y2, y3, y4 in FIG.

At this time, the multipliers of the last multiplication to obtain y1, y2, y3 and y4 in FIG.

[Mathematical formula-see original document] A value obtained by multiplying 1/2 with a multiplier for weighting may be used. By doing so, it is possible to further reduce the calculation amount of the entire high-efficiency encoding and reduce the hardware amount of the encoding device.

When the orthogonal transform of this embodiment is extended to two dimensions and applied to high-efficiency image coding, its efficiency is slightly inferior to that of the two-dimensional fourth-order DCT, but two-dimensional four-dimensional DCT is used.
Good results were obtained compared to the Hadamard transform. [Embodiment 2] The transformation matrix [tij] of the fourth-order pseudo-orthogonal transformation of the second embodiment of the present invention is shown in the following equation.

[0046]

[Formula 19] Here, assuming that a1: a2 = m: n, m = 5 and n = 2. Also in the case of the present embodiment, as in the case of FIG. 1, the configuration of the conversion device is made 5 times and 2 times other multiplications except for the last multiplication for obtaining the orthogonal components y1, y2, y3, y4. 5 times = 4
Since the multiplication is +1, the multiplication result can be obtained by the above bit shift and one addition. Therefore, as in the first embodiment, the number of multipliers having a large hardware scale can be two, and an orthogonal transform device having a smaller amount of hardware can be provided as compared with the fourth-order DCT.

As mentioned above, the present invention particularly provides the following:
It is characterized by (1) to (3). (1) The element ratio a1: a2 in each row and each column of the transformation matrix [tij] is n or 1 in a simple natural number ratio m: n (2) [yi] = [tij] · [xj ], The second and fourth rows of the transformation matrix [tij] and the column vector [xj
] The operation excluding the final multiplication of the operation with] is an operation for obtaining m · (x1−x4) + n · (x2−x3) n · (x1−x4) + m · (x2−x3)

[0048]

As described above, the orthogonal transform device of the present invention has a 4 × 4 transformation matrix [ti] relating to the fourth-order orthogonal transformation.
Since the values of a1 and a2 of j] are made different from the values of the elements of the transformation matrix [dij] in the fourth-order DCT, the efficiency when used for high-efficiency coding in the fourth-order orthogonal transformation is the fourth-order DCT. The effect is that it can be obtained at about the same level as, and the hardware amount of the orthogonal transform device can be made smaller than that of the DCT.

As described above, the inverse orthogonal transform device of the present invention uses the transpose matrix of the transformation matrix [tij] of 4 rows and 4 columns relating to the inverse orthogonal transform of the 4th order as [uij]. The efficiency when used for high-efficiency coding / decoding in the inverse orthogonal transform is almost the same as that of the fourth-order inverse DCT, and the hardware amount of the inverse orthogonal transform device is smaller than that of the inverse DCT. There is an effect that can be.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of an orthogonal transform device of the present invention.

FIG. 2 is a configuration diagram of an embodiment of an inverse orthogonal transform device of the present invention.

FIG. 3 is a configuration diagram of a fourth-order high-speed DCT conversion device.

[Explanation of symbols]

 a0, a2 matrix element [dij] 4 × 4 transformation matrix in DCT [tij] 4 × 4 transformation matrix [uij] 4 × 4 transformation matrix [tij] transpose matrix [xj] 4 From input data Column vector [yi] Column vector consisting of 4 output data z Real value

─────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] September 7, 1992

[Procedure Amendment 1]

[Document name to be amended] Statement

[Correction target item name] 0036

[Correction method] Change

[Correction content]

[0036]

This is an irrational number of
You may approximate by 6 grade. Further, in order to set the magnitude of the multiplier of the last multiplication to a value within a predetermined range, the multiplier of the last multiplication is multiplied by 2 ^B (B is an integer), and the multiplier of the multiplication excluding the last multiplication is 2 ^{−. It} may be a value multiplied by ^B , and even in that case, it is natural that the multiplication except the last multiplication can be performed by bit shift and addition. Further, using the input data as image data, a block [xij] composed of input data of 4 pixels in the vertical direction and 4 pixels in the horizontal direction is subjected to the conversion of the present invention two-dimensionally, and the result is vertical 4 data, horizontal 4 If it is a block [yij] consisting of data,

Claims (2)

[Claims] 1. A fourth-order orthogonal transform is [yi] = [tij] .multidot.
[Xj] where [yi]: a column vector consisting of 4 output data [tij]: a transformation matrix of 4 rows and 4 columns [xj]: a column vector consisting of 4 input data i, j: 1, 2, 3, 4 An orthogonal transformation device that performs arithmetic operations, wherein among the four rows forming the transformation matrix [tij], the elements of each row for two rows are a1, a2, -a2, -a1, by a1, a2 (real numbers), a2, -a1, a1, and -a2, and a1: a2 is m: 1 or m: 2 (m is a natural number).
An orthogonal transform device characterized in that 2. An inverse orthogonal transform device for the orthogonal transform device according to claim 1, wherein a fourth-order inverse orthogonal transform is [yi] = z. [Uij]. [Xj
] [Yi]: column vector consisting of 4 output data z: real number [uij]: transposed matrix of transformation matrix [tij] of 4 rows and 4 columns [xj]: column vector consisting of 4 input data i, j: An inverse orthogonal transform device, characterized in that the calculation is performed by 1, 2, 3, 4.