Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1998-04-22
2001-03-20
Au, Amelia (Department: 2623)
Image analysis
Image compression or coding
Adaptive coding
C382S246000, C382S247000, C382S251000
Reexamination Certificate
active
06205254
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to image compression. In particular, this invention relates to a coding technology appropriate for efficient lossless or near-lossless compression of both artificial (computer generated graphics) image data generated by a computer, e. g. PDL (Page Description Language) image data, and scan-in image data.
2. Description of the Related Art
In PDL images, identical pixel values appear consecutively at an extremely high rate. In other words, PDL images include many “0” (zeros) as the difference between two consecutive pixel values (See FIG.
24
). Meanwhile, since identical pixel values rarely appear consecutively in a scan-in image, the compression ratio thereof is low (See FIG.
25
). Because of the differences between the features of PDL and scan-in images, it is difficult to improve the coding rate of both images in a frame work.
In order to improve the coding rate of both scan-in images and PDL images, lossy coding, such as, e.g., coding according to an international standard JPEG (Joint Photographic Experts Group), can be used in combination with lossless coding, such as Huffman coding. However, the switching between lossless coding and lossy coding causes trouble, because of the difference in scanning order or the difference in code data streams. For example, while Huffman coding uses raster-scan, JPEG uses block-scan. Two examples of the lossless/lossy adaptive coding are explained below.
(1) Multi-plain Method
A candidate for an international standard, MRC (Mixed Raster Content), represents an image as three plains, which are a plain for lossless coding, a plain for lossy coding and a tag plain for switching between the former two plains. This method requires synchronization of the lossless plain and the lossy plain, when decoded images are sent to an image output device, such as a printer. In other words, image data of all plains should be prepared at a particular moment. Accordingly, an image buffer memory or plural decoders for accommodating the synchronization should be provided.
(2) Block Coding
A common scanning order is required to switch between lossless coding and lossy coding. For example, the scanning order of the lossless coding is changed to block scan. Instead, code data should be multiplexed. For example, a lossless coding stream and a lossy coding stream are multiplexed in a unit of a block. Accordingly, a lossless coding circuit or a multiplexing circuit becomes complicated.
LOCO-I (ISO/IEC JTX 1/SC 29/WG1 N203) is an example that performs lossy coding for scan-in images by using prediction coding. LOCO-I realizes near-lossless coding by quantizing prediction errors.
FIG. 29
is used to explain LOCO-I. As shown in this figure, windowing unit
1
receives input image data
7
and decoded pixel data
13
. The input image data
7
is set as a coding object pixel. Pixel value predicator
2000
receives peripheral pixel values
8
output from the windowing unit
1
and supplies prediction value
9000
to prediction error calculator
3000
. The prediction error calculator
3000
calculates prediction error
10000
, which is an error between the coding object pixel and the prediction value
9000
. Error quantizer
4000
quantizes the prediction error
10000
. Then, entropy coding unit
5
encodes the quantized prediction error and outputs output code data
12
. Local decoder
6000
receives the quantized prediction error
10000
and peripheral pixel values
8
, performs local decoding and outputs decoded pixel data
13
to the windowing unit
1
.
This method is based on pixel value prediction. Resolution adaptation or sub-sampling is not considered. This method determines a statistic of prediction errors by using a small prediction error or high auto-correlation of an image in a low frequency image area. Sub-sampling is efficient, since all information regarding a pixel is discarded and a source is extended. It is particularly desired to improve a compression ratio by using sub-sampling in a low frequency image area, such as a gradation area, in a scan-in image.
In addition, since this method is based on pixel value prediction, the coding rate is decreased in a fine image structure area where auto-correlation in the image is low and pixel value prediction is difficult. Since the fine image structure area includes an AC-coefficient and requires a small tone level for an effective tone level reproduction, it is desired that a pixel value is directly quantized without pixel value prediction.
Objects of this invention include:
(1) performing lossless or near-lossless coding for both an artificial image, such as a PDL image, and a scan-in image in a framework, and
(2) improving a coding rate of near-lossless coding for scan-in images.
SUMMARY OF THE INVENTION
The present invention has been made in view of the above circumstances. An objective of the present invention is to provide an image coding apparatus that receives a value of a first pixel and a value of a second pixel located near the first pixel, and calculates approximate values of the first pixel using plural approximation methods on the basis of the value of the second pixel. The value of the second pixel has been approximated in a preceding process. An error between the value of the first pixel and each of the approximate values is calculated. Then, one of the approximation methods whose error is a minimum is selected. The image coding apparatus assigns a rank to the selected approximation method, and encodes the rank and outputs a code data for the first pixel.
According to the image coding apparatus and method of the present invention, since an approximation method depending on essential factors of an image is selected, the volume of the image data can be compressed without lowering the quality of the image.
Furthermore, an objective of the present invention is to provide an image decoding apparatus and method that decodes the code data obtained by the process of the image coding apparatus of the present invention.
The image decoding apparatus receives code data encoded by the image coding apparatus described above and decodes the code data so as to obtain a rank of an approximation method. A plurality of approximation methods are provided and respectively are corresponded with ranks. An approximation method corresponding to the rank obtained by encoding the code data is used to calculate an approximate value of a first pixel on the basis of a value of a second pixel. The second pixel is located near the first pixel and is decoded in a preceding process. The calculated approximate value is output as image data.
According to the image decoding apparatus and method described above, since an approximation method depending on essential factors of an image is selected, the volume of the image data can be compressed and expanded without lowering the quality of the image.
REFERENCES:
patent: 4885636 (1989-12-01), Sullivan
patent: 5828789 (1998-10-01), Yokose et al.
patent: 5963673 (1999-10-01), Kodama et al.
patent: 5966183 (1999-10-01), Kondo et al.
patent: 6008847 (1999-12-01), Bauchspies
patent: 6061474 (2000-05-01), Kajiwara et al.
patent: 9-224253 (1997-08-01), None
LOCO-I: “A Low Complexity Lossless Image Compression Algorithm”, Weinberger et al., ISO/IEC JTC 1/SC 29/WG 1 N 203 (Jul. 10, 1995).
“Revision of D25 Forming the Basis for Draft Rec. T.44(MRC-Colour)”, ITU—Telecommunication Standardization Sector, Temporary Document 1018 (Feb. 4-13, 1997).
Andoh Akihiro
Koshi Yutaka
Kunitake Setsu
Au Amelia
Fuji 'Xerox Co., Ltd.
Johnson Timothy M.
Oliff & Berridg,e PLC
LandOfFree
Image coding apparatus and method, and image decoding... 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 coding apparatus and method, and image decoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image coding apparatus and method, and image decoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494421