Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
1999-02-01
2001-09-18
Lee, Thomas O. (Department: 2624)
Image analysis
Image compression or coding
Predictive coding
C358S296000, C375S240120
Reexamination Certificate
active
06292587
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image encoding method and apparatus, and more particularly, to reversible encryption for multi-valued images.
2. Description of the Related Art
Full color images generally have a great amount of data. For example, four-color full color images of 300 SPI (spot per inch), A4 size have a data quantity of about 32 MB. Accordingly, when images are accumulated or transmitted, image compression may be used. A memory capacity required for accumulation and time required for transmission can be reduced by image compression, whereas since the image compression itself applies complex processing to an entire image, image compression by software has been time-consuming. Although hardware dedicated to image compression may be used to reduce the time, adding the hardware has been costly.
For example, in nonreversible encryption called a base line process defined in JPEG (Joint Photographic Expert Group), which is a standard of image encryption, an image is divided into blocks, each with eight pixels wide and eight pixels long, transformation called DCT (Discrete Cosine Transform) is applied to each block, a block image is transformed into frequency components before being quantized, and finally Huffman encoding is performed.
FIG. 1
shows an example of a block diagram of an apparatus that performs compression using the JPEG method.
That is, in the example of
FIG. 1
, an image input unit
10
divides an image into blocks, each with eight pixels wide and eight pixels long, and a DCT transformation unit
11
subjects the image of each block to DCT transformation. A quantization unit
12
quantizes the DCT transformation data for each DCT coefficient using a quantization matrix to compress high-frequency components. Furthermore, an encoding unit
13
subjects the quantized data to entropy encoding (Huffman encoding) and outputs a result from a code output unit
14
.
Since DCT performs two eight-by-eight matrix multiplications and quantization is achieved by divisions among elements of the matrix, to process one pixel of one color requires 16 multiplications, 14 additions, and one division. An entire image of 300 SPI, which contains about eight million pixels of four colors, requires a total of about five hundred and twelve million multiplications, four hundred and forty-eight million additions, and thirty-two million divisions. With Huffman encoding, image reading, and other overheads further added, one or more minutes have been required to compress a full color image of 300 SPI, A4 size even by the use of the most advanced workstation.
On the other hand, with general-purpose data compression methods such as LZW (Lempel-Ziv-Welch), the use of a complex compression method using dictionaries provides no significant improvement in processing time and leads to a low compression rate.
A prediction encoding system enables compression with a relatively small amount of computation. There is disclosed in e.g., Japanese Published Unexamined Patent Application No. Hei 9-200774, an apparatus that uses the values of a plurality of surrounding pixels as prediction values to perform reversible encoding by using information for identifying a prediction part outputting the smallest prediction error and the prediction error.
FIG. 2
shows the configuration of the apparatus.
This apparatus comprises: a plurality of prediction units
20
that predict the value of a target pixel from the values of pixels around it on the basis of respectively different parameters; prediction error calculation units
21
that calculate differences (prediction errors) between prediction values obtained by the plurality of prediction units
20
and the value of target pixel; a prediction selection unit
22
that selects a prediction unit on the basis of the magnitude of the prediction errors and priority; a priority setting unit
23
that sets priority for each of the plurality of prediction units; and an encoding unit
24
that encodes the value of target pixel on the basis of a prediction value obtained by the selected prediction unit. The priority setting unit
23
determines the order of selection on the basis of selection history. The prediction selection unit
22
comprises: a minimum prediction error detection unit
221
; a first multiplexer
222
that selectively outputs a prediction unit on the basis of a minimum prediction error and priority set by the priority setting unit
23
; a latch unit
223
that latches selective output; and a second multiplexer
224
that outputs prediction errors supplied from the prediction units
20
on the basis of selective output from the latch unit
223
. The prediction unit
20
performs prediction using the values of left, upper, and other pixels, as shown in FIG.
3
.
This apparatus, which uses pixels around a target pixel or the average of them as a prediction method, requires no multiplication and division for pixel values. However, multiple prediction units must be used to obtain a high compression rate, and prediction and error calculation, selection of a prediction unit to give a minimum error, and determination of priority of predictors are performed for each pixel. Therefore, implementing this compression apparatus by software would require much time for compression.
There is disclosed in Japanese Published Unexamined Patent Application No. Hei 9-224253 an apparatus that reversibly compresses images produced in computer graphics and page description language (PDL) processing systems.
This apparatus comprises: an image input part that inputs images; a plurality of pixel value prediction parts that predict the pixel values of a plurality of pixels to be encoded within an image inputted by the image input part by respectively different prediction methods; a prediction error calculation part that calculates an error between the value of a target pixel within the image inputted by the image input part and a prediction value predicted by a predetermined prediction method; a match determination part that determines whether or not prediction values predicted by the plurality of pixel value prediction parts match the value of a target pixel; a selection part that alternatively outputs, on the basis of the determination output of the match determination part, identification information for identifying a pixel value prediction part whose prediction value is determined matching by the match determination part and an error calculated by the prediction error calculation part; an encoding part that encodes the identification information and the error outputted by the selection part; and an output part that output codes encoded by the encoding part.
FIG. 4
is a block diagram showing the configuration of this apparatus.
In
FIG. 4
, image data
34
is supplied from an image input unit
30
to a first prediction unit
31
, a second prediction unit
32
, and a prediction error calculation unit
33
. The first prediction unit
31
and the second prediction unit
32
each predict the pixel value of a target pixel on the basis of the image data
34
by a predetermined method and outputs it to a selection unit
37
as prediction value data
35
. The prediction error calculation unit
33
predicts the pixel value of the target pixel on the basis of the image
34
by a predetermined method, subtracts the predicted value from the actual pixel value of the target pixel, and outputs a result to the selection unit
37
as prediction error data
36
.
The selection unit
37
determines from the image data
34
and the prediction value data
35
whether the prediction on the target pixel is correct or incorrect. As a result, the identification number of a prediction unit that made prediction correctly, if any, is outputted to the encoding unit
39
; if there is no prediction unit that made prediction correctly, the prediction error data
36
is converted into prediction status data
38
before being sent to an encoding unit
39
.
The encoding unit
39
uses a predetermined encoding method to encode the identification numbe
Chen Wenpeng
Fuji 'Xerox Co., Ltd.
Lee Thomas O.
Oliff & Berridg,e PLC
LandOfFree
Image encoding method and apparatus with adaptive prediction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image encoding method and apparatus with adaptive prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image encoding method and apparatus with adaptive prediction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2498044