Image compression and decompression using predictive coding and error diffusion

An encoding/compression technique using a combination of predictive coding and run length encoding allows for efficient compression of images produced by error diffusion.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
This invention relates to a lossless compression technique and an apparatus 
in which an image produced by error diffusion is predictively run length 
encoded and decoded. 
2. Discussion of Related Art 
Data compression systems have been used to reduce costs associated with 
storing and communicating image data. However, conventional compression 
methods yield very little compression when the input image is halftoned by 
error diffusion. Error diffusion is an important technique for digital 
halftoning. It usually generates images with superior quality. Due to 
irregular, high frequency noise patterns introduced in the process, it is 
very difficult to compress error diffused images. For example, 
conventional run length based techniques, such as CCITT Group3 and Group4 
formats used in facsimile operations, are inappropriate for compressing 
error diffused images since they cannot suitably handle short run lengths 
which are dominant in error diffused images. 
SUMMARY OF THE INVENTION 
It is therefore an object of this invention to compress an error diffused 
image without losing image information. 
It is another object of this invention to use a predictive coding technique 
for the lossless compression of error diffused images. 
It is still another object of this invention to predictively code an error 
diffused image using run length encoding to realize lossless image 
compression. 
It is still a further object of this invention to predictively code and 
decode an original error diffused image using run length 
encoding/decoding. 
To achieve these and other objects, the inventive method and apparatus 
predictively code error diffused images into run length encoded error 
signals which can be transmitted or otherwise sent to a complimentary 
receiver/decoder.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
Unless otherwise indicated, the term "signal" is used interchangeably 
herein to mean both an individual signal and a multicomponent signal 
having numerous individual signals. 
A basic system for carrying out the compressive method of the present 
invention is shown in FIG. 1. As shown, an image produced by error 
diffusion is received as the input of a compressor 2 at point 1. The image 
comprises a plurality of signals b(m,n) (hereafter "b"), which is 
typically, 1 or 2 bits per pixel. The compressor 2 comprises prediction 
circuitry 3 such as a predictor, comparison circuitry or subtraction 
circuitry 4 and a run length encoding means or encoder 5. The compressor 2 
also includes as a part of the subtraction circuitry 4, circuitry for 
generating a plurality of prediction errors 6 based on the results derived 
by the subtraction circuitry 4. The signal b is input into the predictor 3 
and also into the subtraction circuitry 4. The predictor 3 generates a 
predicted signal, b* (m,n) (hereafter "b*") based on stored values of 
previous quantization errors, e*(m-i, n-j), and an average of previous 
signals b(m-i, n-j). The signal b, and predicted signal b*, are input into 
the subtraction circuitry 4. This circuitry generates a plurality of 
prediction errors, E(m,n) (hereinafter "E"), by comparing the predicted 
image to the error diffused image. Prediction errors are determined by 
subtracting the predicted image from the error diffused image. 
Prediction errors are output at point 7 and input into a run length encoder 
5. In this manner, only the differences or errors between an error 
diffused signal or image and a predicted image is transmitted to point 8. 
FIGS. 2(A) and (B) are flow charts showing the operation of the compressor 
2 shown in FIG. 1. Initially, an error diffused signal, b, is input into 
the compressor 2 at step S50. At step S100 a predicted, modified signal 
i*.sub.mod (m,n) (hereinafter "i*.sub.mod "), is calculated in the 
predictor 3 according to the following equation: 
EQU i*.sub.mod (m,n)=i*(m,n)+.SIGMA.a(i,j)e*(m-i,n-j) (1) 
where the * denotes an estimation or prediction and a(i,j) denotes weights 
used in error diffusion. 
The two values on the right side of equation (1) represent an average for 
previous error diffused signals for a set of past pixels and a weighted 
summation of previous quantization errors, respectively. Both values are 
stored in a memory or storage (not shown in FIG. 1) which may be a part 
of, or separate from, the compressor 2. 
The predicted, modified signal or predicted continuous tone signal i* mod 
(m, n) is a continuous tone signal because it is based upon an average of 
previous error diffused halftone digital signals i* (m, n) which is a 
continuous tone signal. This average is a continuous tone signal because 
it is an average of previous error-diffused signals. Thus, even though 
each individual previous error-diffused signal is digital the average of 
these signals will produce a value that falls between the thresholds of 
the error-diffused signal and, therefore, is a continuous tone signal. 
The predicted continuous tone signal i* mod is also a continuous tone 
signal because it is also based upon a weighted average of previous 
prediction error signals which is based upon previous predicted continuous 
tone signals as will be explained below in connection with Eq. (5). 
Once the predicted, modified signal i*.sub.mod is determined, the next step 
is to predict b* from a quantized value of i*.sub.mod at step S200. 
Mathematically the predicted signal b* is calculated as follows: 
EQU b*(m,n)=Qi*.sub.mod (m,n)! (2) 
where Q is the quantization operation. 
In this manner the error diffused signal is predicted as b*. Because b* is 
a prediction of an error diffused halftone digital signal it is known as 
the predicted error diffused halftone digital signal. 
Once b* is known, the prediction error E can be calculated using the 
equation: 
EQU E(m,n)=b(m,n)-b*(m,n). (3) 
The prediction error is calculated in the comparison circuitry 4 by 
subtracting the predicted image from the error diffused image. Such a 
comparison results in a plurality of prediction errors being generated by 
comparison circuitry 4 at step S300. If during such comparisons a 
prediction error E is determined to be zero, then the predictor 3 has 
predicted a correct signal. In such a case there is no need to adjust 
i*.sub.mod. 
On the other hand, if during such comparisons E.noteq.0, then i*.sub.mod 
must be adjusted in step 510 in one of two ways. If: 
EQU i*.sub.mod =minimum value in a quantization interval of b(m,n), if 
E(m,n)&gt;0;4(a) 
or 
EQU i*.sub.mod =maximum value in a quantization interval of b(m,n), if 
E(m,n)&lt;0.4(b) 
For example, if 0.5 is used as a threshold for quantization then a 
"minimum" value corresponding to equation 4(a) would be a value greater 
than 0.5 e.g., 0.51 (b=1 in this case and the quantization internal is any 
value greater than 0.5). Likewise, a "maximum" value would be a value less 
than 0.5, e.g., 0.49 (b=0 in this case, and the quantization interval is 
any value less than 0.5). 
The actual adjustment is carried out by adjustment circuitry which may be a 
part of the predictor 3. 
In either equation 4(a) or (b) a new, predicted quantization error, e*(m,n) 
(hereafter "e*") must eventually be calculated and stored in the predictor 
3 at step S600. This quantization error is calculated using the following 
formula: 
EQU e*(m,n)=i*.sub.mod (m,n)-b(m,n). (5) 
As can be seen from equation (5) a present predicted quantization error, 
e*, is derived from a predicted, modified signal, i*.sub.mod, and b. This 
present quantization error is then stored in memory in order to calculate 
a new, predicted modified signal when the next error diffused signal is 
input into the predictor 3. 
After the prediction errors are generated they are output to point 7 and 
eventually input into a run length encoder 5. 
Typically, error diffused signals have short "run lengths." A run length is 
defined as a group of continuously coded pixels, i.e. 10 white pixels 
represented by binary 1s in a row. The use of predictor 3 increases the 
run length of error diffused signals. 
The use of a run length encoder 5 allows these "lengthened" run lengths to 
be transmitted or otherwise output using a code which identifies, in this 
instance 10 "non-errors" (as opposed to 10 white pixels) in a row by, for 
instance "10x" (where x=error) instead of transmitting each of the 10 
"non-errors" individually, i.e., 1x, 1x, 1x . . . etc. Thus, it can be 
seen that in the event there are no errors generated, a continuous stream 
of "no errors" is input into the run length encoder 5. This continuous 
stream can be encoded by the run length encoder 5 and output to point 8 as 
one code indicating "no errors." 
FIG. 3 depicts a block diagram of an apparatus according to one embodiment 
of the invention which receives, decodes and decompresses the run length 
encoded image transmitted or otherwise sent from the apparatus shown in 
FIG. 1. 
As shown in FIG. 3, a decompressor 9 comprises run length decoding means or 
decoder 11, predictive coding circuitry or receiver predictor 12 and 
addition means or circuitry 13. 
The run length decoder 11 decodes run length encoded prediction errors 
input from point 10 and outputs a plurality of prediction errors at point 
14. 
Prediction circuitry 12 inputs at point 15 past decoded signals output from 
addition circuitry 13 and outputs a plurality of predicted signals at 
point 16. These predicted signals are calculated within the prediction 
circuitry 12 by quantizing a predicted modified signal, i*.sub.mod. This 
signal, i.e., i*.sub.mod, is in turn first calculated by circuitry 
preferably a part of the prediction circuitry from an average of past 
decoded signals over a "neighborhood" and previous receiver quantization 
errors which are stored in receiver memory or storage (not shown in FIG. 
3) in the same manner as in equations (1) and (2). The receiver memory or 
storage may be a part of, or separate from, the decompressor 9. 
The predicted signals from point 16 and prediction errors from point 14 are 
thereafter input into the addition circuitry 13 which adds the two signals 
together. In this manner, each predicted signal from the prediction 
circuitry 12 is added to each decoded prediction error from the run length 
decoder 11. As in the compressor 2, if at any point no prediction error is 
present, then the predicted signal is output as the decoded signal from 
the addition circuitry 13 to form an image at point 17. If an error 
exists, the corresponding predicted, modified signal is adjusted in the 
same manner as in equation (4). 
A decoded image can be output to a printer 18 or other reproducing 
apparatus. Each decoded signal is generated from each addition of a 
predicted signal and a decoded prediction error. 
In order to decode and correctly predict the next image or signal a present 
receiver quantization error is calculated within the decompressor 9. This 
error is then stored in the receiver memory. 
Similarly, FIGS. 4(A), (B) and (C) are flow charts depicting the 
decompressing operation of the illustrative apparatus shown in FIG. 3. The 
operative steps of the decompressor (S1050 to S1600) are analogous to the 
operation of the compressor with the exception that in step S1200 a 
decoded output b'(m,n) is first calculated from a decoded error as follows 
: 
EQU b'(m,n)=E(m,n)+b*(m,n) 
The invention has been described with reference to a particular embodiment. 
Modifications and alterations will occur to others upon reading and 
understanding this specification. It is intended that all such 
modifications and alterations are included insofar as they come within the 
scope of the appending claims or equivalents thereof.