JPS61294586A - Conversion coding and decoding device for picture signal - Google Patents

Abstract

PURPOSE:To decrease arithmetic operations needed for conversion and to attain easily the conversion into hardware by giving the prescribed orthogonal conversion to the picture elements within a block consisting of plural picture elements and then giving the code conversion after quantization. CONSTITUTION:Picture signals are supplied to a scan converting circuit 10 and converted into blocks to be supplied to an orthogonal converting circuit 20. The circuit 20 gives the orthogonal conversion to the picture elements included in the block by means of only a sequence of the next prescribed degree to obtain a conversion coefficient. The output of the circuit 20 is quantized by a quantizing circuit 30 and undergoes code conversion through a code converting circuit 40. At the receiver side the picture signals are led out based on the original time series through a code adverse converting circuit 50, an orthogonal adverse converting circuit 60 and a scan adverse converting circuit 70.

Description

[Detailed description of the invention] (Industrial application field) The present invention relates to encoding of image signals.

(Prior Art) Transform coding, particularly coding using orthogonal transform, is known to be highly efficient as it can largely remove redundancy in image signals. However, the amount of calculation required to perform the conversion is so large that various high-speed calculation methods have been proposed. Taking the case of Fourier transform as an example, Cooley and Tukey (Coo
Fast Fourier transform (FFT) by Ley and Tukey and FFT by Winograd are well known. In encoding image signals, cosine transformation using the real part of the image signal is often used, and high-speed calculation methods have been devised for this as well. For example, Wen-Hsi
[A Fast Computational Algorithm for the Discrete Cosine Transform] (A Fast Computational Algorithm for the Discrete Cosine Transform)
tional Algorithm for th
eDiscrete Co51ne Transfer
m”, IEEE Transactions onC
communications, vol, C0M-2
5, No, 9. September 1977) describes a fast discrete cosine transform algorithm.

(Problem to be Solved by the Invention) These high-speed calculation methods are methods for calculating all transform coefficients, so they cannot be used to calculate transform coefficients with small values, which are frequently performed in low bit rate encoding of images. If truncation often results in a specific value (usually zero), this means that the calculation is wasted. Further, even if a high-speed calculation method is used, there are still many calculation methods required, and if this is implemented using hardware, it will be considerably complicated and large. SUMMARY OF THE INVENTION An object of the present invention is to provide a transform encoding/decoding device that can significantly reduce the calculations required for transform and can be easily implemented in hardware.

(Means for Solving the Problem) According to the present invention, means for configuring a block consisting of a plurality of pixels, orthogonalization using only a sequence of a predetermined order for the pixels included in the block. orthogonal transformation means for converting to obtain transformation coefficients and giving predetermined specific values to transformation coefficients that do not correspond to the sequence; means for quantizing the output of the orthogonal transformation means; and code conversion for the output of the quantization means. There is obtained an image signal transform encoding device comprising means for. Further, according to the present invention,
An image signal conversion/decoding device is obtained, which includes means for performing code inverse transformation, and means for performing orthogonal inverse transformation on the transform coefficients obtained by the code inverse transformation using the sequence of the order used at the time of encoding. Furthermore, according to the present invention, code inverse conversion means is capable of replacing conversion coefficients other than those obtained by a predetermined sequence with predetermined specific values for a code-converted image signal;
An image signal transformation/decoding device is obtained, which includes an orthogonal inverse transform means that performs an inverse transform corresponding to the applied orthogonal transform on the transform coefficients obtained by the code inverse transform means.

(Function) When F is the result of converting an image (X) divided into blocks of N lines x N pixels using an arbitrary two-dimensional transformation (C), the relationship between F and X is generally F:c, It is expressed as x-cT. F is a two-dimensional transformation coefficient matrix (hereinafter abbreviated as transformation coefficient). In normal encoding, this F is quantized and is limited in its possible values. Furthermore, when transmitting this quantized result, it is especially convenient if there are many zeros, since the amount of information will be reduced.

When the spectral characteristics of the image itself are mapped to frequencies, the transformation coefficient F is usually such that energy is concentrated in the low frequency region and energy in the high frequency region is small, so the value of the transformation coefficient representing this high frequency component is small. It often becomes zero due to quantization. The coefficient corresponding to this high-frequency component may become large only when converting a screen with a complicated pattern.

Therefore, when an image with a complex pattern is input and the coefficient corresponding to the high frequency component becomes zero, by allowing a slight blur in the reproduced image after inverse transformation, the coefficient corresponding to this high frequency component can be obtained. The calculations required for this can be omitted. For example, as shown in FIG.
If we assume that it is only necessary to encode the low-frequency components included in the nXn area (hatched area) containing (corresponding to the DC component), then the transformation matrix C for the image (X) consisting of a block of N lines x N pixels is the shaded area. All parts other than those shown can be set to zero. CT is the transpose of matrix C.

That is, as shown in FIG. 1, the result of the matrix operation C,X-CT is zero except for the shaded part of F on the left side. The number of operations of X-CT at this time, for example, the number of multiplications is C
Since only those included in the shaded area are required, the number of times is nXNX8. Therefore, the number of multiplications appearing in the calculations of C-X and CT is 2nXNXN times. - Assuming that all coefficients are calculated, the C-X-CT calculation will include 2N3 multiplication.

Furthermore, when converting signals, high-speed calculations, such as FFT in Fourier transform, are often applied. The 16th order discrete cosine transform (D
CT) when using Che 2 (W, H, Chen.

V.S.Patent 4.385.363. May
24.1983) is shown in FIG. 2. XO to X15 are one-dimensional input signals, Fo-F
15 represents coefficients obtained by one-dimensional DCT. The calculation shown in FIG. 2 shows the case where, for example, the transformation matrix C in FIG. 1 is applied to an arbitrary row in the image X. Therefore, in the calculation of X and CT, the example shown in FIG. 2 is applied to rows of the image X sequentially N times. In CT, if only the n columns on the left are not zero, the calculation results F15 to F in FIG.
The conversion results up to n are all set to zero, so there is no need to calculate them.

According to Figure 2, the multiplications used only in the calculations from F15 to Fn are 24 times in total when n = 4, and F1
When calculating everything from 5 to Fo, the number of multiplications (48) is 172. That is, when using the high-speed algorithm according to Che 2, the calculation for each row of image X is n=4, that is, n
When /N = 1/4, the number of multiplications becomes 1/2. If you calculate directly without using high-speed arithmetic, 2nX N2/2N3=n
/N = 1/4. The above has explained the calculation of x-CT, but similarly, if high-speed calculation is used for C. As another example, when n=8, the number of multiplications in the fast algorithm is 1
Since it can be reduced only 6 times, (48-16)/48: 2
/3. Direct calculation yields 8116=112.

This reduction in the number of operations corresponds to a reduction in the number of multipliers used when constructing a conversion circuit.

(Example) Examples will be described in detail below with reference to the drawings. FIG. 3 shows an overall block diagram of an encoding/decoding apparatus according to the present invention. In the figure, the image signal is input to the scan conversion circuit 10 via line 1000 and is divided into blocks.

The size of the block is generally NxN square and N
is often a power of 2. This blocked image signal is supplied to the orthogonal transform circuit 20 via a line 2000 and undergoes NXN orthogonal transform. At this time, only the calculations necessary to obtain the nXn coefficients in the upper left corner are performed as shown in FIG.

This orthogonal transform circuit 20 will be explained in detail later. The transform coefficients that are the output of the orthogonal transform circuit 20 are supplied to a quantizer 30 via a line 3000 and are quantized. At this time, the coefficients other than the nXn conversion coefficient at the upper left corner are always zero.

The quantized transform coefficients are supplied to the code conversion circuit 40 via line 4000 and are represented by an efficient code such as a Huffman code. The code conversion circuit 40 will be described in detail later. The code-converted transform coefficients are supplied via line 5000 to the code inverse conversion circuit 50 on the receiving side. line 5
000 is a transmission line in a transmission system, and is a recording medium in a recording/reproducing system. This code inversion circuit 50 will also be described in detail later. The transform coefficients subjected to sign inverse transformation are orthogonally inversely transformed in an orthogonal inverse transform circuit 60 via a line 6000, and restored to a time domain image signal. This restored image signal is supplied to a scanning and inverse conversion circuit 70 via a line 7000, where the blocked signal is scanned and inversely converted to an image signal according to the original time series. Then, it is output via line 8000 as a decoded image signal on the receiving side.

Next, the configuration of the orthogonal transform circuit 20 will be explained with reference to FIGS. 4 and 5. For simplicity, X, CT
In the operation, explain the operation between the first and second rows of do. It is assumed that the image signals of the first row of X, Xll to XIN, are stored in the shift register a (abbreviated as SRa) 210 at a certain time. Here, it is assumed that the 5Ra 210 has a configuration capable of serially shifting the pixel signal one sample at a time and outputting N samples in parallel. The N samples of image signals are provided in parallel to switch 220 via line 2100. In the switch 220, 5Ra
The image signal from 210 is selected and provided to the sum-of-products circuit 230 via line 2030. In the product-sum circuit 230, a product-sum operation is performed between the coefficients of the column J and the image signal X, which are supplied in parallel from the coefficient memory 240 via the line 4030.
For example, in the case of the first row of X and the first column of CT, ΣX17'C7+·J1 is executed and the result is supplied to the buffer memory 250 via line 3050. In the example of Fig. 4, it is Σ・5・c.

Calculation of N products and sums such as J 1 (to be exact, N products and (N-1)
We take as an example the case where the sum of the numbers is executed in parallel at once. The product-sum operation from the second column to the nth column of CT is continuously executed for the first row of
The image signal of the row is transferred to shift register b (abbreviated as SRb) 21
1 via line 2000 and serially shifted to output N samples in parallel via line 2110. When the calculation for the first row of X is completed, the switch 220 selects the output of 5Rb 211, performs the same product-sum calculation as for the first row of X, and outputs the calculation result via the line 3050. X, C of the image signal X obtained in this way
The conversion result by T is stored in the -tan buffer memory 250, and the line 5 is stored in the -tan buffer memory 250 when the calculation of C.
060. This buffer memory 250
can be realized with a so-called first-in first-out memory if the result of the X-CT operation is obtained by first performing it in the row direction for each column in the order of 1 to N. For each row in the order of ~N, when the data is first executed in the column direction, the input data and output data are read out so that the relationship is a transposed relationship of a two-dimensional matrix. In other words, it is realized by a memory that has the function of converting scanning lines.

The output of this buffer memory 250 is supplied via line 5060 to either shift register c (abbreviated as SRc) 260 or shift register d (SRd) 261 for serial shifting. 5Rc260 and 5Rd261 are 5
The same operation as the relationship between Ra210 and 5Rb211 is performed.

That is, when 5Rc 260 is used for input and serial shift, 5Rd 261 outputs N data in parallel on line 2160, and conversely, when 5Rd 261 is used for input serial shift, 5Rc 260 outputs N data on line 2.
600 for parallel output. switch 27
0 selects the parallel output of these two systems of N data, and the line 70
80 to the product-sum circuit 280. Product-sum circuit 28
The operation of 0 is the same as that of the product-sum circuit 230 described above, and performs N product-sum calculations between the calculation results of X and CT and the coefficient C1j supplied from the coefficient memory 290 via the line 9080. The transform coefficient F thus obtained is sent to the quantizer 3 via a line 3000.
0.

Next, the configuration and operation of the coefficient memory 240 will be explained using FIG. For simplicity, the explanation will be made assuming that n=4 in FIG. 1, but the following explanation is of course applicable to cases other than 4. Memory A242 stores Cjl (j=1 to N), memory B243 stores Cj2, memory C244 stores Cj3, and memory D245 stores Cj4.

In the calculation of ) is output, and xlj (j=1
~N) and a product-sum operation is performed. Similarly, when performing calculations on the first row and second column, for example, memory B 243 is selected and N coefficients are output via lines 4341 and 4030. It is clear that in the coefficient memories A-D, when only addition or subtraction is to be performed, the corresponding coefficient may be set to +1 or -1.

Next, with reference to FIGS. 6 and 7, an embodiment will be described in which the present invention is applied to the high-speed algorithm based on Che 7 described above.

The scan-converted and blocked image signal is a line 2000.
It is first supplied to the bath sofa 810 via. 5Ra210.5Rb211 and switch 220 shown in FIG. 4 output N data in parallel and supply it to the next arithmetic unit a820. Arithmetic unit a820
~Arithmetic unit e824 and arithmetic unit a' 840~Arithmetic unit e'
All of the 844 arithmetic units can be realized with the basic configuration shown in FIG. That is, the input signal (N parallel) is distributed and outputted by the distribution 801, multiplied by the coefficient (maximum 2N parallel) supplied from the coefficient multiplier 803 in the multiplier 802, and the result is added in the adder 804. The calculation for one stage is completed. This will be explained using FIG. 2. In the first stage, input data X. ~
X1. (N=16) is rearranged in the distributor 801, +1 for addition and -1 for subtraction.
The process ends by giving a coefficient and performing multiplication and addition. This distributor 801 is required to be able to output up to 2N data in parallel after rearranging the parallel input of N data. Furthermore, the multiplier 802 is capable of performing 2N parallel multiplications at maximum. Similarly adder 804
It is also assumed that N parallel additions can be performed at maximum. In order to realize the configuration shown in FIG. 2, by simply changing the distribution rule of the distributor 801 for the 1st 2.4th stage, the multipliers in FIG. Can be used as a device d823. The coefficient at this time is +1 or -
Only 1 is enough. Regarding the third stage, as shown in FIG. 2, the coefficient is +1. -1. +C4゜-C4, +C8
, -C8, +84 are prepared in the coefficient unit 803. Fifth
The same goes for the steps. In particular, when n=4 in the fifth stage, the outputs of F4 to F15 are fixedly set to zero as shown in Figure 8, so the products and sums necessary to calculate this are unnecessary. .

Therefore, when comparing FIG. 6 and FIG. 8, arithmetic unit a
The arithmetic units 820 to e824 execute the first to fifth stage calculations. The buffer 830 is thus obtained
o-F15 (F4 to Ft5 are zero), total 16 (N=16
(in the case of ) is temporarily stored and supplied to the arithmetic unit a' 840 in N data in parallel as an intermediate result. Hereinafter, the operations of arithmetic units a' 840 to arithmetic units e' 844 are in accordance with FIG. 8, and are the same as those of arithmetic units a820 to e824. This is the final conversion result. Since these coefficients are output in N parallel, the buffer 850 performs parallel-to-serial conversion and outputs the coefficients one by one via the line 3000 and supplies them to the quantizer 30. For transform coefficients for which orthogonal transform has been omitted, a specific value, for example zero, may be output.

As the orthogonal inverse transform for the approximate orthogonal transform of the present invention, both non-approximate inverse transform and approximate inverse transform can be applied. The non-approximate inverse transformation is the same as the usual case. Approximate inverse transformation can also be performed by simply replacing the coefficients in Figures 4 or 6 that perform the approximate orthogonal transformation, and the elements in the inverse transformation matrix that correspond to the coefficients that are not calculated during orthogonal transformation must be specified. By setting the value of , for example, to zero, the calculation can be effectively omitted.

Next, with reference to FIGS. 9 and 10, a method of representing this into an unequal length code and a method of decoding it will be explained.

FIG. 9 shows an example of the configuration of the code conversion circuit 40. Transform coefficients (after quantization) that are serially output one by one are simultaneously supplied to a coefficient encoder 410 and a zero detector 420 via a line 4000. . The coefficient encoder 410 performs code conversion that outputs a high-efficiency code such as a Huffman code obtained from the distribution of coefficients statistically determined for a large number of image signals, in association with non-zero input conversion coefficients, and performs multiplexing. 471. Zero detector 420 determines whether the input transform coefficients are zero and provides the result to run length counter 430 and multiplexer 470 via line 4200. Run length count 430
counts the number of consecutive zeros when the signal provided on line 4200 indicates that it has detected a zero, and provides the result of the count to run length encoder 440 on line 4344. do.

The control circuit 450 has a function of controlling the execution of this code conversion, and specifies the position of the horizontal and vertical synchronization signals of the image signal and selects the code conversion result thereof with the synchronization signal encoder 460 via a line 4500. A multiplexer 470 is provided. Run length encoder 440 converts the run length supplied via line 4344 into a code and outputs the code to multiplexer 470 . It goes without saying that the code representing the run length and the code representing non-zero coefficients must be distinguishable from each other. The synchronization signal encoder 460 outputs a code representing the presence of the synchronization signal to the multiplexer 470. Multiplexer 4
70 multiplexes the three types of codes to be supplied and outputs them via line 5000, the selection of which is determined by a signal indicating whether the input coefficient is zero or not, which is supplied via lines 4200 and 4500, respectively; following a signal indicating the presence of a synchronization signal,
That is, when a synchronization signal exists, a code representing the synchronization signal, when the coefficient is not zero, the code conversion result of the coefficient (output of the coefficient encoder 410), and when it is zero, the code conversion result of the run length are selected and multiplexed. Ru.

Note that if a large number of consecutive zero coefficients are followed by a synchronization signal, this last run length can be omitted because it can be correctly decoded during decoding even if it is not encoded. For this sowing, control circuit 450 stranded wire 4543
The run length counter 430 is notified of the occurrence of the synchronization signal via the run length counter 430, and its count value is reset. Multiplexer 5470 is also instructed via line 4500 to ignore the code representing the last run length.

Next, the configuration of the sign inversion circuit 50 will be explained with reference to FIG. 10.

The transcoded transform coefficients provided via line 5000 are provided to coefficient decoder 510, run length decoder 540, and synchronization signal decoder 560. Coefficient decoder 510 performs sign inversion of non-zero coefficients and provides the result to switch 570 via line 5157 and a signal indicating that inversion is in progress to control circuit 550 via line 5155. . The run length decoder 540 inversely transforms the code representing a run length (length of continuous zero transform coefficients), generates a zero run code according to the length, and supplies it to the switch 570 via a line 5457. At the same time, a signal is sent to line 54 to indicate that the run length is being decoded via line 5455.
55, respectively. Synchronization signal decoder 56
0 detects the presence of the encoded synchronization signal and communicates the result to control circuit 550.

Control circuit 550 receives signals representing these synchronization signals, line 5.
155 and 5455, respectively, are used to control the selection of switch 570. In addition, if the run immediately before the synchronization signal is not code-converted, the switch 570 commands to output zero for the time from the last non-zero coefficient until just before the synchronization signal is generated. Command and selection with switch 570 is line 5
557.

Next, another example of the conversion/decoding device of the present invention will be described with reference to FIGS. 11 and 12.

In this example, it is assumed that the code-converted transform coefficients supplied via the line 5000 are obtained by orthogonal transform that performs calculations on all sequences as usual. That is, Nx includes the transform coefficient arrangement shown in FIG.
Assume that N conversion coefficients are supplied. At this time, the present decoding apparatus applies approximate orthogonal inverse transform only to the nXn transform coefficients (shaded area) at the upper left of FIG.

The operations of the coefficient decoder 510, run length decoder 540, synchronization signal decoder 560, and switch 570 in this decoding apparatus are the same as in the case of FIG. 10, and therefore the description thereof will be omitted. The control circuit 550 is the same as the control circuit 550 in FIG. 10 regarding the selection control of the switch 570, but in addition, the control circuit 550 controls the conversion coefficients other than the shaded portion in FIG. A function has been added to instruct the gate circuit 580 to replace the conversion coefficient of , with a specific predetermined value (eg, zero). In accordance with this instruction signal supplied via line 5558, the gate circuit 580 outputs the input for the conversion coefficients included in the shaded area in FIG. For example, it outputs zero. In this way, a communicative transform decoding device can be realized regardless of whether a complete or approximate orthogonal transform is used in the transform encoding device.

(Effects of the Invention) When the present invention is put to practical use, although the encoding efficiency is high, it requires complicated hardware or a large number of additions to realize this.
Orthogonal transformations that require multiplication can be greatly simplified. Moreover, if the present invention is put to practical use, the effects will be extremely large, such as realizing a transform/decoder that can receive data regardless of whether or not simplified orthogonal transform is applied in the encoder.

[Brief explanation of drawings]

FIG. 1 is a diagram for explaining the present invention in detail, FIG. 2 is a diagram showing an example of a high-speed calculation method of discrete cosine transform, and FIG. 3 is a diagram for explaining the present invention in detail. 4, 5, 6, 7, 9, and 10 are diagrams showing embodiments of the encoding/decoding apparatus according to the present invention, and FIG. 8 is a diagram showing an embodiment of the encoding/decoding apparatus according to the present invention. FIG. 11 and FIG. 12 are diagrams showing other embodiments of the transform decoding device. In the figure, 10 is a scan conversion circuit, 20 is an orthogonal conversion circuit, 30 is a quantizer, 40 is a code conversion circuit, 50 is a code inverse conversion circuit, and 6
0 is an orthogonal inverse transform circuit, and 70 is a scanning inverse transform circuit. CII ” 11 - Ginkyo q Diagram

Claims (1)

[Claims] 1. In converting and encoding an image signal, means for configuring a block consisting of a plurality of pixels, using only a predetermined order sequence for the pixels included in the block. orthogonal transformation means for obtaining transform coefficients by orthogonal exchange and giving predetermined specific values for transform coefficients that do not correspond to the sequence; means for quantizing the output of the orthogonal transformation means; and encoding for the output of the quantization means. means of converting;
An image signal conversion encoding device comprising: 2. Means for performing orthogonal transformation using a sequence of a predetermined order for each block consisting of a plurality of pixels, and performing inverse code transformation when converting and decoding the code-transformed image signal for the obtained transform coefficients. , means for performing orthogonal inverse transform on the transform coefficients obtained by the code inverse transform means using a sequence of the order used at the time of encoding. 3. When performing orthogonal transformation for each block consisting of a plurality of pixels, and converting and decoding the code-transformed image signal using the resulting transform coefficients, the code-converted image signal is A sign inverse transform means capable of replacing transform coefficients other than the specified values with predetermined specific values, and performs an inverse transform corresponding to the applied orthogonal transform on the transform coefficients obtained by the sign inverse transform means. An image signal transformation/decoding device, comprising: orthogonal inverse transformation means.