JPH03214256A - 2D orthogonal transformation device - Google Patents

Abstract

PURPOSE:To secure about the double processing speed with a two-dimensional orthogonal converter by providing two systems of means which performs the inner product operations among the vectors having the number of elements equal to 4. CONSTITUTION:The m-th line of TA is calculated after the processing X(m) and therefore the processing Y(m) is calculated among the operations of TATT based on the TA calculation data. In the same way, the processing Y(m) is carried out within the calculation of (TA)TT based on the TA calculation data since the m-th line of TA is calculated after the processing X(m). Thus two systems of means are provided for calculation of the inner products carried out among the vectors having the number N of elements. Thus the processing X(m+1) and the processing Y(m) are simultaneously calculated after the processing X(m). Then the pipeline processing is attained between both processings X(m) and Y(m).

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention divides a target image into a certain unit of block images during image compression, and applies two-dimensional Hadamard transform or two-dimensional Tilt transformation, 2D DCT
(Discrete Co51ne Transfer
This invention relates to a device that performs a two-dimensional orthogonal transform such as m), encodes and transmits the transform coefficients, and performs the two-dimensional orthogonal transform.

[Conventional technology] First, a method of one-dimensional orthogonal transformation will be explained.

FIG. 4 shows, as an example, a formula for one-dimensional orthogonal transformation using a 4×4-element orthogonal transformation matrix T for a four-element one-dimensional data vector.

In FIG. 4, Ta is calculated for one-dimensional data (vector a) (42) using an orthogonal transformation matrix (matrix T) (41).

(Ta) is calculated by the inner product operation of the m-th column data of T and a, and this calculation is repeated from m=1 to m=4.

As a result, the orthogonal transformation coefficient vector (vector T a ) (4, 3) of the one-dimensional data is obtained.

Next, a method of two-dimensional orthogonal transformation will be explained.

FIG. 5 shows, as an example, a formula for two-dimensional orthogonal transformation using a 4x4 orthogonal transformation matrix T for a two-dimensional data vector of 4x4 elements.

First, TA is calculated for two-dimensional data (matrix A) (502) using an orthogonal transformation matrix (matrix T) (501). The two-dimensional data (matrix A) is transformed into one-dimensional data (511) (512) (
513) (514), and performs one-dimensional orthogonal transformation using an orthogonal transformation matrix (matrix T) (501) on each one-dimensional data.

As a result, two-dimensional data (matrix TA) (504), which is a collection of one-dimensional orthogonal transformation coefficient vectors of one-dimensional data, is obtained. Divide the 2-dimensional data (matrix TA) (504) into 1-dimensional data (515) (516) (517) (51B) in the direction of 4 row hectares, and A two-dimensional orthogonal transformation can be realized by similarly performing a one-dimensional orthogonal transformation.

For actual calculation, two-dimensional data (matrix TA) (50
By performing the operation (TA)TT of multiplying the transposed matrix T' (505) of the orthogonal transformation matrix (matrix T) (501) from the right side of 4), the two-dimensional orthogonal transformation coefficient matrix (matrix TAT''
) (506) is obtained.

Fig. 3 shows an example of a conventional two-dimensional orthogonal transform orthogonal transform method.
A processing procedure for two-dimensional orthogonal transformation using a ×4 orthogonal transformation matrix T is shown.

A conventional two-dimensional orthogonal transformation processing method will be described below with reference to FIG.

In implementing the two-dimensional orthogonal transformation operation represented by TATr, in the conventional method, all elements of TA are first calculated, and then (TA)T' is calculated. By means of inner product operation, the operation of writing (TA), which is obtained by performing an inner product operation of the m-th vector of T and the vector of A (Dn-th column), into the buffer memory B1. from m=1 to m= 4
Repeat until T A O) Process the operation to calculate the nth column vector.

(n), and by means of inner product calculation, m-th row vector of TA read from buffer memory B and n of TT
Perform the inner product operation with the column vector (TAT”)m
Repeat the steps to find n from n=1 to n-4 and TA
Process Y (m
).

First, the process Xc(k) is repeated from 1 to 4 (31) (32) (33) (34). Through this calculation, all elements of TA are found and stored in buffer memory B.

Next, the operation of (TA)T'' is performed using the data of TA and the data of TT in buffer memory B.
This can be achieved by repeating (m) starting from m = 1 until m = 4 (35) (36) (37) (38
).

Here, the processing Xe(m) is a one-dimensional orthogonal transformation on the m-th column one-dimensional data of A, and the processing Y(m) is T
This is a one-dimensional orthogonal transformation for the m-th row of one-dimensional data of A, and in the conventional method, processing processing X, (rIl) and processing Y
(m) was applied directly.

[Problems to be Solved by the Invention] However, in the above configuration, in order to perform the TAT operation on the data to be transformed of N×N elements, it is necessary to perform N times of vectors with N elements. Corresponding to the fact that the inner product operation is required 2N times, the total processing time Tp is the time Tv required to repeat N times the operation of performing the inner product operation on vectors with N elements and writing them to the buffer memory. Then, read data from the buffer memory and the number of elements is N.
Assuming that the time required to repeat the inner product calculation of the vectors N times is equal to T, the problem becomes Tp-TvX2N, which requires a lot of processing time.

In view of this point, it is an object of the present invention to provide a two-dimensional orthogonal transformation device that requires less calculation processing time.

[Means for Solving the Problems] In the present invention, in order to solve the above problems, two-dimensional data A=i (i=1 to N, j=1 to
N) one-dimensional orthogonal transformation matrix T =; (1-1~N,j
A two-dimensional orthogonal transformation device that performs matrix operation TAT'' from ``=1 to N), comprising a first inner product operation means, a second inner product operation means, a buffer memory, and an operation control means, and includes a first The inner product calculation means performs an operation of writing (TA) □ obtained by performing an inner product calculation on the m-th row vector of the matrix T and the n-th column vector of the matrix A into the buffer memory from n=1 to n=N. The process X (m) of calculating the m-th row vector of the matrix TA is repeated until
Process Y that calculates the m-th row vector of TATT by repeating the operation of calculating the inner product of the row-th vector and the n-th column vector of the matrix TT to obtain (TATT) mn from n=1 to n=N. (m), and the calculation means performs processing Y (1
), then repeat the process of sequentially performing processing X (m+1) and processing Y (-) simultaneously starting from m = 1 until N-1, and finally performing control to perform Y (N). It was configured to obtain two-dimensional orthogonal transformation coefficients.

[For production]

According to the two-dimensional orthogonal transformation device of the present invention, after performing the process X(m), the m-th row of TA has been calculated, so this data is used to perform the process Y ( m) becomes possible.

Similarly, after processing X (m), the m-th row of TA has been calculated, so using this data, (TA)T
”, processing Y (resistance is possible).

Therefore, by providing two systems of inner product calculation means for vectors with N elements, after processing X (m), processing X (m+1) and processing Y (m) can be calculated simultaneously, and processing X ( m) and processing Y (Ill) become possible.

〔Example〕

Examples of the present invention will be described in detail below.

FIG. 1 is a block diagram of a two-dimensional orthogonal transform device according to the present invention.

In FIG. 1, (11) is the first inner product calculation means,
or) etc. (12) is a buffer memory for storing the data calculated by the first inner product calculation means (11), (13) is the 20th inner product calculation means, and (14) is the calculation control means.

The tenth inner product calculation means (11) calculates the elements of TA from the two-dimensional A and the orthogonal transformation matrix T, and the buffer memory (12
). The second inner product calculation means (13) calculates and outputs the elements of TATT from the elements of the data TA in the buffer memory (12) and the orthogonal transformation matrix TT.

FIG. 2 shows an example of the present invention in which a 4×4 orthogonal transformation matrix
The processing procedure of dimensional orthogonal transformation will be shown, and the two-dimensional orthogonal transformation method of the present invention will be explained.

The first inner product calculation means (11) performs an inner product calculation of the vector in the mth row of T and the vector in the nth column of AOn (TA), and writes n into the buffer memory B, n=1. The process of calculating the m-th row vector of TA by repeating from n=4 to n=4 is defined as process X(+n), and the second inner product calculation means (13) calculates the
Perform inner product operation with the nth column vector of (TAT”)
Repeat the operation to find mn from n=1 to n=4,
Process the process of calculating the m-th row vector of TATT Y
(m).

First, after processing X (1) is performed (21), processing X (n++1) and processing Y (m
) at the same time is repeated. That is, process X(2) and process Y(1) ((22) and (25)), then process X(3) and process Y(2) ((23) and (26))
, then process X (4) and process Y (3) ((24)
and (27)) respectively.

As a result, a two-dimensional orthogonal transformation coefficient TAT'' is calculated.

After performing the first process X(1), the first row of TA has been calculated, so using this data, process Y(1) of the calculation of (TA)T'' is possible.

Similarly, after processing X (m), the mth row of TA has been calculated, so using this data, (TA)T
Among the calculations of ', processing Y (m) is possible.

Therefore, by providing two systems of inner product calculation means for vectors with four elements, after processing, processing X (
m+1) and processing Y (m) can be calculated simultaneously.

According to this processing device, the total processing time TP is the time required to repeat N times the operation of calculating the inner product of vectors with N elements and writing them to the buffer memory.
Assuming that the time required to read data from the buffer memory and repeat the inner product operation N times between vectors with N elements is equal to TV, then Tp=TvX (N+
1).

This is the processing time (TV x 2N) by conventional processing equipment.
Compared to this, it is almost twice as fast.

In this way, according to the present invention, it is possible to achieve a speed increase of about twice as much as the calculation time required by a conventional processing device.

Although the explanation was given as a two-dimensional orthogonal transformation, the orthogonal transformation matrix P
, Q can produce the same effect.

〔Effect of the invention〕

As described in detail above, according to the two-dimensional orthogonal transformation device of the present invention, by providing two systems of inner product calculation means for vectors each having four elements, processing X ( n++1) and the processing Y (m) can be performed simultaneously, so an effect can be obtained that the processing speed is approximately twice as high as that of conventional processing devices.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a two-dimensional orthogonal transform device according to the present invention, FIG. 2 is a process flow chart in the two-dimensional orthogonal transform device, FIG. 3 is a process flow chart in a conventional two-dimensional orthogonal transform device, and FIG. FIG. 5 is an explanatory diagram of calculation of one-dimensional orthogonal transformation, and FIG. 5 is an explanatory diagram of calculation of two-dimensional orthogonal transformation. (11) - first inner product calculation means, (12) - buffer memory, (13) - second inner product calculation means (13), (
14) - Arithmetic control means. Figure 181 @ Figure 2 Processing of ()υ Figure 4

Claims (1)

[Claims] A two-dimensional orthogonal transformation device that performs matrix operation TAT^T from a one-dimensional orthogonal transformation matrix T_i_j of two-dimensional data A_i_j consisting of N×N elements, the apparatus comprising: a first inner product calculation means;
The first inner product calculation means includes a second inner product calculation means, a buffer memory, and an operation control means, and the first inner product calculation means performs an inner product calculation between the m-th row vector of the matrix T and the n-th column vector of the matrix A. The operation of writing (TA)_m_n obtained by calculates the inner product of the m-th row vector of the matrix TA stored in the buffer memory and the n-th column vector of the matrix T^T to obtain (TAT^T)_m_
Repeat the operation to find n from n=1 to n=N and TA
Processing Y(m) is performed to calculate the m-th row vector of T^T, and after performing processing Y(1), the calculation means sequentially processes X(m+1) starting from m=1 and up to N-1. Y(m)
A two-dimensional orthogonal transform device characterized in that two-dimensional orthogonal transform coefficients are obtained by repeating the process of simultaneously performing the above steps and finally performing control to perform Y(n).