JPS5921185A - Coding system of picture signal - Google Patents

Abstract

PURPOSE:To ensure the variable length coding with high efficiency, by combining the quantized values of sequences obtained by dividing an input picture with a Hadamard conversion. CONSTITUTION:Picture element signals x1-x4 are supplied to a Hadamard converter 10, and sequences H0a-H3a converted into frequency regions are supplied to an quantizing part 20. Quantizers 22, 23 and 24 deliver the sequence quantized value H2 of horizontal component, the sequence quantized value H1 of vertical component and the sequence quantized value H3 of slope component respectively. An estimator 30 performs a linear estimation to the sequence H0 of DC component and delivers an estimation error component DELTAH0. A comparator 41 consists of a PLA and designates the address of an ROM42 based on sequence quantized values H0, H1, H2 and H3. A code length data CL is read out of the ROM42 and then set to a counter 43. The contents of shift registers 44 and 45 are delivered in response to the count value of the counter 43.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a coding method for the purpose of narrowband transmission or storage of images, and in particular to a variable length code that combines quantized values of each sequence transformed into the frequency domain by Hadamard transform. Regarding the method of conversion.

It has been widely practiced in the past to efficiently transmit or store images by removing redundant signals due to their syntactic properties or by removing unnecessary signals due to their visual characteristics. An orthogonal transform encoding method is known as one of these methods. This orthogonal transform encoding method divides an image into multiple blocks consisting of groups of pixels adjacent to each other, transforms the groups of pixels within one block into the frequency domain by orthogonal transform, and biases the spectrum of each frequency that is the transform output. This method takes advantage of the existence of a spectrum and allocates an appropriate quantization level to each spectrum, that is, applies distortion within a visually permissible range, thereby reducing the amount of information. Hadamard transform, which is one method of orthogonal transform, has a transform matrix having "1" and "-1" as elements, and has the advantage that the circuit can be simplified because it can be configured with only adders.

By the way, the sequence transformed into the frequency domain by Hadamard transform corresponds to the frequency axis in Fourier transform, and the zero-order sequence represents the amount of DC component as
The higher-order sequences can be regarded as parameters each representing the amount of high-frequency components. Therefore, if the correlation between original pixels within a block is strong, the energy of the Hadamard-transformed signal will be concentrated in a low-order sequence.

In a typical image, high frequency components have little energy, so the number of bits at the quantization level can be reduced within a visually permissible range. Further, the Hadamard transform encoding method, which aims at band compression, is particularly effective as low bit rate encoding, and can disperse deterioration due to quantization so as not to be visually noticeable. In other words, due to the visual characteristic that noise in smooth areas is easily noticeable, noise in areas with steep changes is less noticeable.
It has the advantage that quantization can be easily performed.

However, in order to prevent deterioration of image quality due to distortion and to perform highly efficient encoding, it is necessary to increase the block size, which increases the amount of circuitry, resulting in an expensive device. Therefore, in view of the above-mentioned points, it is an object of the present invention to provide an image signal encoding method that prevents image deterioration, has a simple circuit configuration, and realizes highly efficient encoding.

This invention will be explained below.

This invention relates to an image signal encoding method,
dividing the input image into a group of adjacent blocks consisting of a group of pixels m (1, 2) × n (≧2), converting the group of pixels in each block into a frequency domain sequence by Hadamard transform and then quantizing it; At least the DC component of this sequence quantized value is linearly predicted and transformed into a prediction error component, and a plurality of combinations thereof are formed by comparing the sequence quantized values with each other, and a plurality of combinations are formed corresponding to each of these combinations. The prediction error component and other sequence quantized values are variable-length encoded.

Figure 1 shows an image divided into 2×2 blocks Bij (i=1, 2,
..., j=1, 2, ...), where pixel 1 is divided into scanning lines h, h+1, ...
It is designed to be scanned sequentially. Then, if the pixel signals (density signals) for pixel 1 of block Bij are x1, x2, x3, and x4 as shown in the figure, then the normalized Hadamard transform is calculated as follows ( 1) It can be expressed as follows.

Here, sequences H0, H1, H2, and H3 respectively correspond to fourth-order frequency components transformed into the frequency domain by Hadamard transform, H0 is a DC component sequence, H1 is a vertical component sequence, and H2 is a horizontal component sequence. , and H3 indicate the slope component sequences, respectively. Note that scanning lines h and h+1 in the i row of block Bij may be simultaneously scanned to read out the image information of pixels x1 to x4. First, scanning line h is scanned and pixel x
1 and x3 are temporarily stored in the buffer memory, and then when scanning line h+1 is scanned, the image signal x
1 to x4 may be read out in order.

By the way, in a typical image, since there is a strong correlation between adjacent pixels, low-order components are observed to have high energy and high-order components have low energy. Then, each component will receive a distribution of the number of bits of the quantization level according to the magnitude of its energy, but since the energy of the DC component is particularly large compared to other components (vertical, horizontal, tilt), It is necessary to realize highly efficient encoding by adopting a conversion method that lowers the energy of the DC component.

As such a conversion method, a method of linearly predicting each sequence obtained by Hadamard transform is known.

Next, this linear prediction method will be explained.

The linear prediction method is possible when the block size is 1 × n or 2 × n. Now, as an example where the block size is 2 × n as shown in Fig. 2, first, each block is Consider a case where Hadamard transform is applied and then linear prediction is performed for each block in the vertical direction. Then, each sequence obtained by Hadamard transformation is Hl0, Hl
1 and arranged as shown in FIG. 2 for convenience. However, l=0
, 1, ..., (n-1).

Then, the sequence Hl in block Bi-1,j
0′ to the sequence Hl0 in block Bij,
Prediction is made according to the following equation (2).

Hl0=Hl0'-Hl1'-Hl1...
...(2) Prediction error component sequence ΔH at this time
l0 as ΔHl0=Hl0-Hl0 = Hl0-Hl0'+Hl1'+Hl1...
...(3), then this prediction error component sequence △H
l0 is the value that makes the distance between each pixel between blocks the shortest. Note that the sequence Hl1 is transmitted as is without any prediction.

Here, in order to show the effect of linearly predicting each sequence obtained by Hadamard transform, a comparison will be made with the total energy of the image to be transmitted.

The variance of the image x according to the memoryless Gaussian distribution is σ2x,
The variance of each sequence y is σ2y, the block size is N,
The variance when linear prediction is used for some sequences is σ2
Δy is based on the rate distortion theory (Rate distortion theory).
tion theory), the absolute value of the transmission energy is given as an average value Pa as follows.

Or, the relative value of transmission energy Pr is Pr=10lo
g10σ2-Pa (6). The results shown in FIG. 3 were obtained from calculations using equations (4) to (6) above.

In this figure, characteristic I shows the change in power corresponding to the block size of the one-dimensional Hadamard transform, and characteristic II shows the change in power corresponding to the block size of the two-dimensional Hadamard transform. and II
I and IV indicate the characteristics when the characteristics I and II are respectively subjected to Hadamard transform in the horizontal direction and linearly predicted in the vertical direction.

Note that the total energy is 35.2 dB. As is clear from this, in both Characteristics I and II, the transmission energy decreases as the block size increases, whereas in Characteristics III and IV, the transmission energy is constant (approximately 15
dB). From the perspective of transmission energy, this means that if you choose a block size of 4×1 or 2×2,
This shows that linear prediction is efficient.

It has been found that it is efficient to perform Hadamard transform in the horizontal direction and perform linear prediction in the vertical direction. In this case, a buffer memory is required to store the entire sequence in the previous block line, but in order to save the capacity of this buffer memory, the block size is 2.
It may be considered to perform Hadamard transform in the horizontal direction using ×2 and similarly perform linear prediction in the horizontal direction. In this case, the buffer memory only needs to have the capacity to store a fourth-order sequence, and like blocks Bi, j-1 and Bij in FIG. 1, each sequence H0 of the previous block Bi, j-1 on the same block line ', H1', H2'
, H3' to the sequence H0, H1 of the current block Bij
In the end, the sequence to be transmitted is
Prediction error component sequence, horizontal component sequence H2, slope component sequence H3
becomes. Here, since the vertical component sequence H1 is already composed of sums and differences within the block Bij and the transmission energy is much smaller than that of the DC component sequence H0, linear prediction has little effect. That is, sequence H1
There is almost no difference in the magnitude of the transmission energy between the prediction error component ΔH1 and the prediction error component ΔH1, so linear prediction is performed only for the sequence H0, and the sequence to be transmitted is determined by ΔH0, H1, H2.
and H3.

Therefore, in the following, this example (ΔH0, H1, H2, H3)
Explain using.

Using a block size of 2x2, apply Hadamard transform to the pixel group in the horizontal direction, quantize each resulting sequence within a visually permissible range, then predict the DC component H0 of the current block, and It is assumed that the prediction error component ΔH0 is determined and the sequence ΔH0, H1, H2, and H3 is transmitted.

Conventionally, appropriate quantization levels are given to these sequences ΔH0, H1, H2, and H3, and the number of bits is allocated for encoding. For example, if 7 pits, 5 bits, 5 bits, and 3 bits are allocated to sequences ΔH0, H1, H2, and H3, respectively, a total of 20 bits (average 5 bits/pixel) will be transmitted or stored for one block. , it cannot be said to be efficient encoding. Therefore, in order to further increase the compression rate, it is necessary to increase the block size, which also has the disadvantage of increasing the number of circuits.

In contrast, in the present invention, variable-length encoding is performed depending on the probability of occurrence of the combination by combining the quantized values of each sequence, thereby making it possible to perform wide-ranging data compression.

Table 1 below shows the sequence H0a obtained by sampling a standard image at 7 bits/pixel and performing Hadamard transform in the horizontal direction using block size 2x2.
A suitable quantization level is given to each of H1a, H2a, and H3a, and these are used as sequence quantization values. This quantization allows distortion D to each frequency component y within the range that does not cause visual deterioration in the spatial power spectrum of the image, and the amount of information R required for transmission at this time is determined by the rate-distortion theory. It is given by R [bits/pixel].

When pixel signals x1 to x4 are input at 7 bits/pixel and a block size of 2×2 is used, the output sequence H0a to H3a of the normalized Hadamard transform requires a maximum of 8 bits. However, as visually acceptable distortion levels, the sequences H0a, H1a, H2a and H
For example, 1 bit, 2 bits, 2 bits for 3a, respectively.
It is also possible to provide white noise equivalent to bits and 3 pits, and here, the bits are shifted by 1 bit, 2 bits, 2 bits, and 3 bits to the least significant bit (LSB) side of each of the sequences H0a to H3a. It is compressed and quantized. After this, linear prediction is performed by expanding the quantized compressed value for the DC component sequence H0 to obtain a prediction error component ΔH0, and then a combination number is determined based on the combination of sequence quantized values ΔH0, H1, H2, and H3. Form C0 to C3.

In Table 1, for example, the combination number C1 indicates that only the prediction error component sequence ΔH0 takes a value of "1" or "-1", and the other sequence quantization values H1 to H3 all take a value of "0". The probability of occurrence of this combination is 2
This means that it is 3.9%. In addition, ±h indicates that the sequence quantization value can take any value, and the block code is a code that indicates a break within a block, and since there is little difference in the probability of occurrence of each combination, all blocks have two Bits are allocated. Furthermore, the data code indicates that no data is transmitted for the combination number C0, only the plus/minus sign S is transmitted for the combination number C1, and 6 bits of data is sent after the plus/minus sign S for the combination number C2. As for combination number C3, sequence quantized values H3, H2, H1, ΔH0 are respectively 3 bits, 5 bits, 5 bits, 7 bits with plus/minus sign S.
This shows that bits are allocated to transmit variable length code data according to the combination of sequence quantization values ΔH0 to H3.

Therefore, the code length to be transmitted is 2 bits for combination number C0, 3 bits for combination number C1, 9 bits for combination number C2, and 2 bits for combination number C3.
It is 2 bits. Note that the combination occurrence probability is determined as an average by testing various images with low spatial frequency such as portraits, images with high spatial frequency such as landscape photographs, etc.

In this way, by providing variable length codes, it is possible to realize efficient encoding. Note that the probability distribution of sequence quantization values is similar to the Laplace distribution, and it is possible to give a variable length code to each sequence quantization value, but in this case, even if the shortest code length is given to each sequence, the total 4 bits/block. However, if you encode the combinations as shown in Table 1,
Since the shortest code length is 2 bits/block and its occurrence frequency is 25.5%, it is clear that the encoding method of the present invention is very efficient.

As mentioned above, data below the distortion level given during quantization in the spatial spectrum of the image is discarded without being transmitted, and Table 1
In the example, the sequence quantization values H3, H2, H1, ΔH0
The encoding method is compressed to 3 bits, 5 bits, 5 bits, and 7 bits, respectively, and transmitted, and the average amount of transmitted information is 2.1 bits/pixel, making it an extremely efficient encoding method. I understand.

Next, a specific example of a circuit for realizing the encoding method according to the present invention according to Table 1 will be described with reference to FIGS. 4 and 5. The pixel signals x1 to x4 read out by the scanning line
is input to the Hadamard transformer 10, and the sequence H0a to H3a transformed into the frequency domain is input to the quantization unit 20, and the horizontal component sequence quantization is performed by the quantizer 22 constituting the quantization unit 20. Value H2, quantizer 23
The sequence quantization value H1 of the vertical component quantized by the quantizer 23 and the sequence quantization value H3 of the slope component quantized by the quantizer 23 are respectively input to the variable length code conversion circuit 40 at the subsequent stage. Further, the sequence quantized value H0 of the DC component, which is the output of the quantizer 21, is inputted to the predictor 30 as shown in FIG. 5 together with the sequence quantized value H2.
The prediction error component sequence ΔH0 predicted by is input to the variable length encoding circuit 40. Note that the quantizers 21 to 24
are each composed of a parallel shifter or a shift register, and simultaneously shift the sequence H0a to H3a converted by the Hadamard converter 10 to the lower bit side by an appropriate number of pits, respectively.
For example, the sequence H0a is shifted by 1 bit, the sequence H1a by 2 bits, the sequence H2a by 2 bits, and the sequence H3a by 3 bits. Further, the expander 31 of the predictor 30 is composed of, for example, a parallel shifter, and includes a sequence quantized value H0 of the input DC component and a sequence quantized value H2 of the horizontal component.
Since the levels are different from each other, the level of the horizontal component sequence H2 is changed to match the levels of the two, and the delay circuits 32 and 33 are each used to delay the time by one block.

On the other hand, the variable length encoding circuit 40 uses PLA (Program
The combination numbers C0 to C3 determined by the comparator 41 are stored in a ROM (Read Only Me
42 as an address signal. Then, the code length CL read from the ROM 42 is counted by the counter 4.
3, and the block code BC is set in the shift register 45. When the code length CL is set in the counter 43, the signal P goes into the set state, starts counting down by the clock pulse CP, and when the counter 43 reaches 0, the signal P goes into the reset state. When signal P is in the set state, clock pulse CP and signal P
sends the shift signal SS to the shift register 44 via the AND gate 46. Here, shift registers 44, 45
is a parallel-in/serial-out type shift register. Also, the horizontal component sequence H2 from the quantization unit 20, the vertical component sequence H1, the slope component sequence H3, and the prediction error component sequence Δ from the predictor 30
H0 is input to the shift register 44, the shift data shifted out from the shift register 44 is input to the shift register 45 which stores the block code BC, and the output of the shift register 45 is input to the serial input. /parallel-out type register 48. When a certain number of bits is input to the register 48, the entire bit is read out in parallel, and after being temporarily stored in the buffer memory 49, it is transmitted to another device or stored as an image signal PD. There is.

The puffer memory 49 is for absorbing fluctuations in the time axis between input and output during real-time processing, that is, for correcting the time axis, and is added as necessary.

In such a configuration, simultaneous reading of two scanning lines,
Alternatively, when the pixel signals x1 to x4 read out by one scanning line and one scanning line delay are input to the Hadamard transformer 10, these pixel signals x1 to x4 are converted into frequency domain sequences H0a to H3a. quantization unit 20
is input. Then, the quantizer 21 of the quantization unit 20 shifts the sequence H0a to the lower side by 1 bit, the quantizer 22 shifts the sequence H2a to the lower side by 2 bits, and similarly the quantizer 23 shifts the sequence H0a to the lower side by 2 bits. 2
The quantizer 23 shifts the sequence H3a by 3 bits to the lower order side. Here, positive and negative signs are shifted from the upper bit side. Of the sequence quantized values H0 to H3 obtained in this way, H1 to H3 are assigned to the variable length encoding circuit 40.
The signal is input to the comparator 41 and also to the shift register 44. Then, the DC component sequence H0 is calculated by the predictor 3.
0, and in this predictor 30 the horizontal component sequence H
2 to form a prediction error sequence ΔH0, input this prediction error sequence ΔH0 to the comparator 41, and
It is input to the shift register 44. Here, the comparator 41 is configured with PLA programming, and determines the combination numbers C0 to C3 according to the above-mentioned Table 1 based on the input sequence quantized values ΔH0, H1, H2, and H3. , one of the combination numbers C0 to C3 is a binary signal, for example "1". For example, the prediction error sequence ΔH0
is "1", and all other sequences H1 to H3 are "0".
”, only the combination number C1 is “1”, and the other combination numbers C0, C2, and C3 are all “0”.

In this way, the combination numbers C0 to C determined by the comparator 41
3 is input to the ROM 42, the ROM 42 uses "1" of the combination numbers C0 to C3 as an address signal to read out the code length data CL and block code BC stored in the corresponding address, and reads out the code length data CL. The block code BC is set in the counter 43 and the block code BC in the shift register 45. Therefore, for example, when the combination number C2 is determined and input to the ROM 42, the code length "9" is set from the ROM 42 to the counter 43, and "10" is set to the shift register 45, corresponding to the countdown of the counter 43. The contents of shift registers 44 and 45 are shifted out. Therefore, nine bits below "10" are input to the shift register 48. Also, the comparator 41 selects the combination number C.
If it is determined that the code length is 0, the code length “2” is stored in the counter 43.
is set, and "00" is set in the shift register 45, and "00" is set in the shift register 48.
” is entered. In this way, shift register 4
The data inputted in series to 8 is converted into parallel data and stored in a buffer memory 49 in units of, for example, 8 pits, and after time axis correction is output as an image signal PD. Thus, according to the circuits of FIGS. 4 and 5, it is possible to realize the transmission or storage of image signals according to Table 1 above.

In the embodiment shown in FIG. 4, the dividers 11 to 14 are inserted after the Hadamard transformer 10 for the purpose of explanation to "1/2", but the quantization section 20 ” is generally performed. Also, the quantization amount 2
It is easy to understand that 1 to 24 can be omitted if the quantization characteristics are fixed and not adaptively changed according to the spatial frequency of the image. Furthermore, when the block size of the Hadamard transform is small as in this example, the slope component corresponding to the high frequency component generally causes almost no visual deterioration when viewed from the entire screen. It is also possible to omit the circuits for obtaining H3a and H3 from the beginning.

[Brief explanation of the drawing]

Fig. 1 is a diagram for explaining the details of this invention, Fig. 2 is a diagram for explaining the linear prediction method used in this invention, and Fig. 3 is a diagram for explaining the relationship between block size and Hadamard transform. , FIG. 4, and FIG. 5 are circuit configuration diagrams showing an embodiment to which the method of the present invention is applied. 1... Pixel, 10... Hadamard transformer, 21-2
4... quantizer, 30... predictor, 31... decompressor, 32, 33... delay circuit, 40... variable length encoding circuit, 41... comparator, 42 ...ROM, 43
...Counter, 44, 45, 48...Shift register, 49...Buffer memory.

Claims (1)

[Claims] 1. Divide an input image into a group of adjacent blocks consisting of a pixel group m(1, 2) x n (≧2), and transform the pixel group in each block into a frequency domain sequence by Hadamard transform. and then quantize it, linearly predict at least the DC component of this sequence quantized value and convert it into a prediction error component, and form a plurality of combinations by comparing the sequence quantized values with each other. , the prediction error component and the other sequence quantized value are variable-length encoded in correspondence with each of these combinations. 2. Divide the input image into adjacent blocks of 2×2 pixels and perform Hadamard transform for each block in the horizontal direction to generate a DC component sequence, a vertical component sequence, a horizontal component sequence, and a gradient in the frequency domain. obtain a component sequence, linearly predict at least one of the DC component sequence or the vertical component sequence in the horizontal direction to obtain a DC prediction error component and a vertical prediction error component, and the DC prediction error component and the vertical prediction error component or vertical By comparing the quantized values of the component sequence, the horizontal component sequence, and the gradient component sequence, a plurality of combinations thereof are formed, and the DC prediction error component and the vertical prediction error are calculated correspondingly to each of these combinations. 1. A method for encoding an image signal, characterized in that a component or a vertical component sequence, the horizontal component sequence, and the tilt component sequence are variable-length encoded.