JPH01286677A - Picture data compressing system - Google Patents

Abstract

PURPOSE:To lower redundancy with an adjacent element and to improve an encoding efficiency by dividing an index into a high-order bit and a low-order bit and executing the forecasting sequence encoding of the high-order bit with the index of the block of the circumference. CONSTITUTION:Out of two compressing signals distributed from a code distributer 50, one of them is inputted to a variable length decoder 53 and other one is inputted to a variable length decoder 54 respectively, and the signal decoded here is sent converted to forecasting inverse converting circuits 56 and 57 and inversely converted. Next, the high-order bit of the index is decoded by a variable length decoder 51, the forecasting sequence of the signal is inputted to a forecasting sequence inverse converting circuit 55 and the index high-order bit of the noticed block is restored. Based on the deviation to occur thereafter, the distributer 50 is switched to a variable length decoder 52 and the low-order bit of the index is decoded. Next, the bits of the high-order and the low-order are addressed to a code table 58 and outputted through a picture reproducing circuit 59 from a terminal 5 as a picture signal.

Description

[Detailed Description of the Invention] [Summary] This invention relates to an image data compression method that compresses and transmits image data, receives and reproduces the transmitted data, and aims to transmit image data efficiently and with high image quality. , divides a multilevel halftone image into blocks consisting of a predetermined plurality of pixels, creates an input vector from the pixel data of each divided block, performs vector quantization1, and encodes the index of the output vector. The index is divided into high-order bits and low-order bits, and the high-order bits are configured to be encoded in a prediction order based on the indexes of surrounding blocks.

[Field of Industrial Application] The present invention relates to an image data compression method for compressing and transmitting image data, and receiving and reproducing the transmitted data.

The amount of information required to represent image data increases by an order of magnitude compared to numerical data. This increase in the amount of information is remarkable among image data, especially in multi-value halftone images and color images. In order to accumulate such image data or transmit it at high speed and with high quality, it is necessary to encode (that is, compress) the gradation information for each image with high efficiency.

[Prior Art] As compression encoding methods for image data, block encoding methods and vector quantization methods have been commonly used. Improvements to these methods are being researched,
A vector dangling coding method as shown below (for example, Journal of the Society of Television Engineers).

Vo138. No. 5. 1984 "Vector suspension of r picture m letter M") has been proposed. Here, the vector quantization method considers the image signal grouped into multiple pixels as a multidimensional vector, and converts the input vector into the output vector (of a finite number of representative points) at the shortest distance in the multidimensional space. This method performs multidimensional quantization by mapping to (1).

As a vector quantization method for multilevel halftone images, the mean value separation normalized vector proton coding method (Mean 5e
Parated VectorQuantize
r) is well known.

This method divides the image into blocks consisting of NxN (-k) pixels, and each block has 5i pixels (i=1.2.
. . k) input vector S-[St.

S2 +...83] is separated by subtracting the average value μ, and normalized by the deviation σ to form an average value separated normalized input vector X'' [X1+×2+...Xdo1.X This is a vector pointing to one point on the 2-dimensional signal space.

Therefore, R is divided into N subspaces, and subspace R1 is represented by a vector of representative points Yi = ['171*V;z
, '...Vik].

Then, the set of Yl is defined as Y−(Yt, Y2...Y
N), and the set of indices of yl is 1-(1,
2,...N), vector quantization VQ is expressed by the following equation.

S = [St e S 2 ,...s,]
(1)μ=(1/k)2. s, (2)
x #-(s H-μ), /σ (4)X-
[Xt, X,, -, X),] (5) Vector quantization of the above
) <d (X, Y, >< 7) However, i a
-Pj Encoding by vector hanging C1 decoding represents the following mapping operation.

C:X-*i, D:i-+Y1 Therefore, VQ-
D −C The above d(X, Yi) is a distortion measure and represents the distance between input and output, and the squared distortion measure d(X, Yi)=! (X; −y; Hl (8) Absolute value distortion is defined as d(X, Yi)−, etc. In mean value separation normalized vector quantization, the encoded information is the mean value μ for each block, It becomes the width deviation and the index i of the output vector.

FIG. 6 is a diagram showing an example of a conventional configuration of a mean value separation vector quantizer. In the figure, (a) shows an encoder, and (b) shows a decoder. First, the encoder shown in (a) will be explained. Here, the image signal is made into a 4×4 pixel block, normalized using the average value and deviation to create an input vector, and vector quantized using the absolute value distortion temperature. 8 4x4 pixel image signals! −[S 1 + 82 +...S
, 6], then the normalized input vector X−[Xt
, X2, . . . x+bE are created by the separation/normalization circuit 1 as follows.

X 1 = (8iup) / (jp
(10)μl′″(1/16)F,,Si
(11) Through the above conversion, the input vector X has an average value O
The sum of absolute values of one element is normalized to one. The normalized input vector X is then temporarily held in register 2.

On the other hand, output vectors Yi are sequentially read from the output vector code table 3 and temporarily held in the register 4. Then, the encoder shown in the figure calculates the difference (distortion) d(X, Yi) between the input vector .

Encoded together with σ1. That is, the result of subtraction by the subtracter 5 is input to the absolute value circuit 6 and converted into an absolute value.

Then, the outputs of these absolute value circuits 6 are input to an accumulation circuit 7.

The accumulating circuit 7 accumulates the absolute value type measure d shown by equation (9). The output of the accumulator circuit 7 enters the minimum distortion detection circuit 8 and is compared to see if it is smaller than the distortion of the output vector sought so far.
is entered and latched. Next, the code table index counter 10 is counted up by one, and then an index I for checking distortion is output. This index ■ enters the output vector code table 3 and outputs the corresponding next output vector Yr. When the code table index counter 10 sequentially counts up and scans all the indexes, the index with the minimum distortion will be found in the index latch 9. As a result, index i.

The normalization constant μ and the deviation σ are output.

Next, the operation of the decoder shown in (b) will be explained. (a
Of the compressed data transmitted from the encoder shown in ), the index i is latched in the index latch 11. The latched in-books data enters the output vector code table 12, and the output vector code table 12 uses index i as an address to read out the output vector Yi stored at the corresponding address. The read output vector Yi is transmitted to the reproducing circuit 14
to go into. The reproduction circuit 14 also receives the normalization constant μ and the deviation σ of the input data, and calculates μ and σ on the output vector Yi to obtain a restored image signal.

The vector quantizer shown in FIG. 6 compares the output vectors one by one with respect to the input vectors and selects the output vector that causes the least distortion, and is called a full search type.

In this full search type vector quantizer, the operation Rffi of detecting the input vector and the output vector that has the minimum distortion becomes large, so the processing takes time. Therefore, as a method for performing high-speed vector quantization, there is tree search vector quantization that gives a set of output vectors a certain structure.

Binary tree search vector quantization, which is often used in this search constantization, will be explained.

In binary tree search vector quantization, a training sequence of normalized input vectors is divided in stages to create a set of output vectors having the structure shown in FIG.

In the figure, the root of the tree corresponds to a dimensional space R, and each node corresponds to a space obtained by sequentially dividing R into two. A temporary output vector is placed at each node, the input vectors are compared with these output vectors, and the final output vector can be selected with log2 k distortion operations.

FIG. 8 is a block diagram showing an example of the configuration of an encoder for binary search vector quantization. The example shown in the figure speeds up processing at each node by pipeline processing, and shows the (n+1)th stage. In the figure, b(n) is an n-digit binary index, which indicates the binary launch route up to the n-th stage. The input vector X first enters the input vector register 21 and is temporarily held there. On the other hand, the n-digit binary index b (n) from the previous stage is entered into the output vector code table 22. Then, at the (n+1)th stage shown in the figure, distortion calculations are performed on the input vector O/1 at the n+1st digit
is determined and input to the index register 26. Then, the index b(
n) Output O/1.

FIG. 9 is a diagram showing an example of the configuration of a conventional vector quantization variable length encoding circuit. This figure shows an example of the configuration of a data compressor using mean value separation normalized vector quantization and variable length coding in the prior art.

In the figure, 1 is an input terminal for an image signal, 30 is a normalization circuit similar to that shown in FIG. 6, and the average value μ1. and standard deviation σme are separated and output, and the average value 0. Outputs the input vector X normalized to a standard deviation of 1.

31 is a binary search vector quantization encoder, which converts the binary search vector quantizer shown in FIG. 8 by l og2 k stages,
It is connected to a pipeline. The binary tree search vector quantization coder 31 outputs an index of l 002 k pits. The average value μl and standard deviation σ (normalization coefficient) output from the normalization circuit 30 are D
Data is compressed by PCM encoding. Therefore, μl and σl are respectively input to predictive protonizers 33 and 34,
The difference from the predicted value is quantized and output.

For example, considering the average value μl, the predicted value μl (X) is calculated by using the predictor shown in FIG. 10, the average value μ, (
By referring to A>, μt (B), and μl (C), it can be determined as shown in the following equation.

toμt (X) −μl (A> +μ) (B) −
μe (C) (13) From now on, the prediction error ε force (X) is ε force (X) − μl (X) − μl (X)
It is expressed as (14).

Here, assuming that the image signal has 256 gradations and is represented by O to 255, the prediction error εμ is from -255 to 2
It can take values up to 55. Therefore, a quantizer outputs the quantized value εA from the 512-level prediction error to about 63 levels. The same applies to the standard deviation σ, and the predictive quantizer 33 performs predictive quantization and outputs εσ.

Next, the standard deviation after hanging is used as the index i, and the adaptive quantizer 32 outputs i by adaptively truncating the actual index length. This is because when the deviation is small, the gradation change of the input block is considered to be gentle, so that it can be sufficiently expressed by an output vector higher in the binary tree. Then, these εA, εσ, and 1 are variable-length encoded by a variable-length encoder 35 and output as a compressed code.

[Problem to be solved by the invention] In the prior art described above, the normalization coefficient μl.

Since σL is predictively encoded, redundancy due to correlation with adjacent blocks can be reduced. However, index i
However, there remains a correlation with adjacent blocks, and as a result, there is a problem in that the encoding efficiency cannot be sufficiently increased.

The present invention has been made in view of these problems, and an object of the present invention is to provide an image data compression method that can efficiently transmit image data including an index with high image quality.

[Means for Solving the Problems] FIG. 1 is a flowchart without showing the principle of the system of the present invention. The present invention divides a multilevel halftone image into blocks each consisting of a predetermined plurality of pixels (Step [1]), creates an input vector from pixel data for each divided block, and performs vector quantization (Step [2]). ]) When encoding the index of the output vector, the index is divided into upper pits and lower bits (step [3]), and the upper pit is encoded in prediction order from the indexes of the surrounding blocks (step [4]). ]).

[Operation 1] When encoding the index of an output vector, the index is divided into upper pits and lower pits, and the upper pit is encoded in a predictive order from the indexes of the surrounding blocks.

As a result, a correlation can also be taken with respect to the index i, so redundancy with adjacent elements can be reduced, and therefore encoding efficiency can be increased.

[Embodiment J] Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

In the present invention, among the indexes of output vectors that have been converted into m-child vectors, the upper pits are encoded in a prediction order based on the indexes of adjacent blocks, thereby reducing the correlation between adjacent blocks of the indexes.

In order to reduce the correlation between adjacent blocks of an index of an output vector (hereinafter simply referred to as an index), a method of using predictive encoding at the same time as encoding the normalization coefficient can be considered. However, since the index is Wj@ attached to the subspace obtained by dividing the multidimensional space into binary water,
Distance is not defined. Therefore, since the magnitude of the difference between the two indexes does not correspond to the magnitude of the distortion m degree, DP
Even if CM encoding is applied, redundancy cannot be expected to be removed.

The method of the present invention attempts to remove redundancy by applying predictive coding to encode the order in which the block of interest is likely to appear based on the indices of surrounding blocks. However, since the index is usually selected between 8 and 12 pits, if prediction order coding is used as is, the number of prediction states will become very large even with two block references (e.g. 3, jy+1 = 2 to 2), and prediction will fail if it is used as is. It is impossible to construct a vessel. However, since the index has a binary configuration and the higher bits are more likely to be predicted correctly, in the present invention only the upper pits of the index are predictively encoded.

FIG. 2 is a block diagram showing an embodiment of an encoder used in the present invention, and FIG. 3 is a block diagram showing an embodiment of a decoder used in the present invention. First, the encoder shown in FIG. 3 will be explained. The encoder shown in the figure differs from the encoder shown in FIG. 9 in that a prediction rank generator 40 and variable length encoders 41 and 42 are added. The binary main search vector quantizer 31, which receives the mean value separation normalized input vector X from the normalization circuit 30, divides the index i into an upper pit i' and a lower pit i=' and outputs them. The upper bits i' are input to a predicted rank generator 40, and a predicted rank is output.

If the prediction rank generator 40 refers to the indexes of the immediately preceding block and the block directly above it, as shown in FIG. 4, for example, the configuration will be as shown in FIG. 5. That is, it has a shift register 40b that can store index upper pits for one block line, and performs a shift operation for one block each time the index of interest 40a is input. Then, A from the shift register 40b.

The predictor 40 determines the index corresponding to the blocks B and
Enter c. This predictor 40c is composed of a ROM, and assuming that the upper pit of the index is 6 bits,
The capacity of the predictor 40c is 2J%b (-2) kW x 6 pits. The prediction 540C is A,
From the index at position B, the order in which the indexes of the block of interest are more likely to appear is output.

The variable length encoder 41 performs variable length encoding on this prediction rank. Further, the variable length encoder 42 adaptively truncates the lower pit 1'' of the index according to the magnitude of the deviation σl in the same way as in the prior art, and then encodes it. Since it is the same as the figure, its explanation will be omitted.These variable length encoders 35.41.4
The outputs of 2 are sequentially switched by the multiplexer 43 and output from the output terminal 2.

Next, the decoder shown in FIG. 3 will be explained. Similarly to the prior art, τμ and σl are sent in the order sent from the encoder.
variable length decoding. That is, among the compressed signals distributed from the code distributor 50, εG and ε are transmitted to the variable length decoder 5.
3.54 and is decrypted. The decoded signals εσ and εl are respectively input to the following predictive inverse transform circuits 56 and 57 and inversely transformed into σl and μl.

Then, the upper bit i' of the index is decoded by a variable length decoder 51. Thereafter, the signaled prediction order is input to the prediction order inverse conversion circuit 55, and the high-order bit i' of the index of the target block X is restored with reference to the indices of blocks A and B in FIG. 4 mentioned above. Next, the code distributor 50 is changed to the variable length decoder 5 according to the II difference σ which has been found.
2 and decode the lower bit i=- of the index.

Then, address the output vector code table 58 by combining the upper and lower bits of the determined index,
Read the output vector Y1 stored at the corresponding address. The process is similar to the conventional technology, and μ, σl, and Yl are determined by the image reproducing circuit 59.
, normalize the output vector, add an offset of the average value, and output it to terminal 4 as an image signal.

[Effects of the Invention] As explained in detail above, according to the present invention, the correlation between adjacent blocks of output vectors is reduced, so it is possible to provide an image data compression method that can improve encoding efficiency. .

[Brief explanation of the drawing]

Fig. 1 is a flowchart showing the principle of the method of the present invention, Fig. 2 is a block diagram showing an embodiment of the encoder used in the invention, and Fig. 3 is a configuration showing an embodiment of the decoder used in the invention. Block diagram: Figure 4 is a diagram showing the arrangement of adjacent indices for predictive rank encoding; Figure 5 is a block diagram of a predictor for predictive rank encoding; Figure 6 is a conventional mean value separation normalization vector quantizer. Figure 7 is a diagram showing a subspace division of binary water; Figure 8 is a block diagram showing an example configuration of a two-tree search vector quantizer encoder; Figure 9 is a diagram showing a configuration example of a binary search vector quantizer; FIG. 10 is a diagram showing an example of the configuration of a variable length encoding circuit for vector quantization. FIG. 10 is a diagram showing an example of the configuration of a predictor. In FIGS. 2 and 3, 1.3 is an input terminal, 2.4 is an output terminal, 30 is a normalization circuit, 31 is a binary search vector interpolator, 33.34 is a prediction interpolator, 35 is a variable length encoder, 40 is a prediction rank generator, 41.42 is a variable length encoder, 43 is a multiplexer, 50 is a code distributor, 51 to 54 are variable length decoders, 55 is a prediction rank inverse converter, 56 and 57 are predictive inverse transform circuits, 58 are output vector code tables, and 59 are image reproduction circuits. Patent applicant Fujitsu Ltd. Company representative
Person Patent Attorney Fuji Ijima Jigai 1
Figure 1 is a flowchart showing the principle of the method of the present invention.

Claims (1)

[Claims] A multilevel halftone image is divided into blocks each consisting of a predetermined plurality of pixels (step [1]), an input vector is created from pixel data for each divided block, and vector quantization is performed (step [1]). 2]) When encoding the index of the output vector, divide the index into upper bits and lower bits (step [3]
), an image data compression method characterized in that the high-order bits are encoded in prediction order based on the indexes of surrounding blocks (step [4]).