JPS61294585A - Convertion coding system for picture signal - Google Patents

Abstract

PURPOSE:To decrease arithmetic operations needed for conversion by omitting the arithmetic operation which is executed in a conversion mode for prescribed conversion coefficients including those that are easily concentrated on the specific value through quantization. CONSTITUTION:Picture signals are supplied to a scan converting circuit 10 and converted into blocks. These blocks of picture signal are supplied to an orthogonal converting circuit 20. For the circuit 20, the arithmetic operation carried out for conversion is omitted with the prescribed conversion coefficients including those that are easily concentrated on the specific value through quantization. The output of the circuit 20 is supplied to a quantizing circuit 30 to be quantized. The quantized conversion coefficient is converted into a code by a code converting circuit 40 and supplied to a code adverse converting circuit 50 at the receiver side. Then the conversion coefficient subjected to the code adverse conversion undergoes the orthogonal adverse conversion through an orthogonal adverse converting circuit 60 and then undergoes the scan adverse conversion into the picture signals through a scan adverse converting circuit 70 according to the original time series.

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-Hsiu
ng Chen) et al., “A Fast Comp
utional Algorithm for t
heDiscrete Co51neTransfo
rm”, IEEE Transactions on
Communications, vol, C0M-
25, 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 violet (usually zero), the calculation is wasted. In addition, even if a high-speed calculation method is used, the required calculation method is still large, and this is
If implemented as one-ware, it would be quite complex and large. An object of the present invention is to provide a conversion method that can significantly reduce the calculations required for conversion and can be easily implemented in hardware.

(Structure of the Invention) According to the present invention, when converting an image signal and quantizing and encoding the obtained transform coefficients, predetermined transform coefficients containing transform coefficients that are often concentrated in specific values due to quantization are used. A transform encoding method for image signals is obtained, which is characterized by omitting calculations performed during transform for transform coefficients.

(Principle of the Invention) 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: It is expressed as c, x, c'r. 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. At this time, the number of operations for X and CT, for example, the number of multiplications is C
Since only those included in the shaded area are required, the number of times is nXNxN. Therefore, the number of multiplications appearing in the calculation of C, X-CT is 2nXNXN times. Assuming that all coefficients are calculated, the calculation of C,X-CT will include 2N3 multiplications.

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

V.S.Patent 4.385.363. May
24.1983) is shown in FIG. 2. Xo-A'15 is a one-dimensional input signal, Fo-
F1a represents a coefficient 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 X-CT calculation, 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 side are not zero, the conversion results from calculation results F15 to Fn in FIG. 2 are all zero as a result, so there is no need to calculate them.

According to Figure 2, the multiplications used only in the calculations from F1a to Fn are 24 times in total when n = 4, and F1
This is 1/2 of the number of multiplications (48) when all calculations from a to Fo are performed. That is, when using Cheno's high-speed algorithm, 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, 2n x N2/2N3=
n/N = 1/4. The calculations for X and CT have been explained above, but the calculations for C0X and CT are also 1/2 when using the high-speed algorithm, and 1/4 when directly calculated.

As another example, when n=8, the number of multiplications can be reduced by 16 times using the fast algorithm, so (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, all 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 calculation, explain the calculation of the first and second rows (each X□4.x-, but 1≦j≦N) and CT (the pixel in row j, column i is abbreviated as Cji). do. At a certain time, shift register a (abbreviated as SRa) 21
It is assumed that the image signals of the first row of X, Xll to XIN, are stored in 0. Here, it is assumed that the 5Ra 210 has a configuration capable of serially shifting the image signal one sample at a time and outputting N samples in parallel. This N-sample image signal is sent to switch 22 in parallel via line 2100.
0. The switch 220 selects the image signal from the 5Ra 210 and supplies it to the product-sum circuit 230 via the line 2030. In the product-sum circuit 230, a product-sum operation is performed between the coefficients of the first column supplied in parallel from the coefficient memory 240 via the line 4030 and the image signal X, for example, the first row of X and the first column of CT. In this case, ΣX17' CJl·Jl is executed and the result is supplied to the buffer memory 250 via line 3050. In the example of Fig. 4, it is photo, ・5・c.

(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 IJ 250 and output via line 5060 during the next calculation of C.(X-CT). This buffer memory 2
50, if the calculation result of X-CT is obtained by first performing it in the row direction for each column in the order of 1-N,
This can be realized using a so-called first-in first-out memory, but if the data is obtained by first executing each row in the order of 1 to N in the column direction, the relationship between input data and output data will be a transposed relationship of a two-dimensional matrix. It is read out as follows. 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 e (abbreviated as SRc) 260 or shift register d (SRd) 261 for serial shifting. , 5Rc260 and 5Rd261 perform the same operation as the relationship between 5Ra210 and 5Rb211. That is, when 5Rc 260 is used for input and serial shift, 5Rd 261 sends N data to line 2160.
Conversely, when 5Rd 261 is used for input serial shifting, 5Rc 260 will output N data in parallel via line 2600. switch 2
70 selects the parallel output of these two systems of N data, and connects the line 7
080 to the product-sum circuit 280. Product-sum circuit 2
The operation of 80 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 Cij supplied from the coefficient memory 290 via the line 9080. The transform coefficients F thus obtained are supplied to the quantizer 30 via line 3000.

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 of course the following explanation applies to cases other than 4 as well. Cjl (j=1 to N) is in memory B
243 has Cj2, and memory C244 has Cj3. Cj4 is stored in the memory D245. X-
In the CT calculation, when first performing the calculation in the first row and first column, the memory A242 is selected by the selector 241, and the N coefficients Cjl (i: 1 to N) are x, j (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. This coefficient memory A-D
It is clear that when performing only addition or subtraction, 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 2 described above.

The scan-converted and blocked image signal is a line 2000.
The signal is first supplied to buffer 810 via . This buffer 810 consists of 5Ra210.5Rb211 and switch 220 in FIG. 4, and outputs N data in parallel and supplies it to the next arithmetic unit a820. Arithmetic unit a820~
Arithmetic unit e824 and arithmetic unit a' 840 to arithmetic unit e' 8
All of the 44 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, and the coefficient multiplier 8
Multiplier 8 uses the coefficients supplied from 03 (maximum 2N parallel)
02, and the results are added in an adder 804, completing one stage of calculation. This will be explained using FIG. 2. In the first stage, input data X. ~X
1 degree (assuming N, = 16) is performed in the distributor 801, +1 for addition and -1 for subtraction.
The process ends by performing multiplication and addition by giving a coefficient. This distributor 801 is required to be able to output up to 2N data in parallel after rearranging the N data input in parallel. 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, the multipliers in FIG. Can be used as 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 to F15 (F4 to F15 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.3, orthogonal transformation is omitted. A specific value, such as zero, may be output for the conversion coefficient.

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. At this time, the control circuit 450 twists the 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 470 is further 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 decoding 5510 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 (a run length in which zero transform coefficients are continuous), generates a zero signal according to the length, and supplies it to the switch 570 via a line 5457. 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. This command and selection with switch 570
557.

(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 now be greatly simplified, and the effect is very high.

[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. Figures 4, 5, 6, 7, 9, and 10 are diagrams showing embodiments of the present invention, and Figure 8 is a high-speed calculation method for discrete cosine transform according to the present invention. It is a figure showing an example. In the figure, lO 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. "II C11 Heart α] * Tei q Diagram

Claims (1)

[Claims] 1. Regarding predetermined transform coefficients, including transform coefficients that often concentrate on specific values due to quantization, when converting an image signal and quantizing and encoding the resulting transform coefficients. is a conversion encoding method for image signals characterized by omitting calculations performed during conversion. 2. The image signal transform encoding method according to claim 1, wherein a predetermined specific value is assigned to the transform coefficient whose calculation is omitted.