Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1998-01-13
2001-04-17
Mehta, Bhavesh (Department: 2621)
Image analysis
Color image processing
Compression of color images
C382S238000, C382S247000, C382S233000
Reexamination Certificate
active
06219445
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a multi-color image encoding and/or decoding apparatus and its method. More particularly, the present invention relates to color order transformation of an index which is attached during encoding and decoding the multi-color image.
2. Description of Related Art
Multi-color images have been used in personal computers, game machines and the like. A multi-color image is also called a representative color image or a limited color image. As shown in
FIG. 22
, a multi-color image is an image in which an index is attached to a specific color, namely a color having a specific R(red), G(green) and B(blue) value, and using the index data to express the image by limited representative colors consisting of 16,256 colors.
This type of multi-color image data requires a total of 24 bits assuming that each of R, G, and B color is displayed by 8 bits (256 types). However, because an index is also displayed by 8 bits, the data compression rate is substantial. Despite the compression, the information volume is still very large, which makes the communication of data too slow to be practical if the data is processed without any change. Hence, compression technology of multi-color images is extremely important. A multi-color image requires encoding and decoding compression technology (i.e., a reversible compression technology) without loss because the number of colors is limited for a multi-color image.
A technology based on an entropy encoder and decoder has drawn attention in recent years as one type of data compression technique. An example of such is a technology which uses an arithmetic encoding and decoding technology. Synopsis of this technology is described in Japanese Laid-Open Patent Publication 62-185413, Japanese Laid-Open Patent Publication 63-74324 and Japanese Laid-Open Patent Publication 63-76525, the subject matters of which are incorporated herein by reference.
FIGS.
16
(A)-(B) show a conventional multi-color encoding system
50
and decoding system
60
which use the above technology. The encoding system
50
includes a line buffer
51
and an entropy encoder
52
. Color pixel data
100
A is input to the line buffer
51
and the entropy encoder
52
. All the color pixel data
100
A (shown in
FIG. 17
) is raster scanned and sequentially input as pixel data in the order of horizontal scanning. A method of attaching an index in the order of the input color is used as a method to form the index data (i.e., the color pixel data
100
A) which creates a phenomena such that the colors are substantially different for data with close index such as “1” and “2” or that the colors are quite close for the data with large differences in index such as “100” and “200” as shown in
FIG. 22. A
method to avoid such phenomena by attaching successive numbers to similar colors is disclosed in Japanese Laid-Open Patent Publication 5-328142, the subject matter of which is incorporated herein by reference.
The line buffer
51
is a reference pixel generation device that generates reference pixel data A, B, C and D for encoding the target pixel X (from the input color pixel data
100
A). In other words, the line buffer
51
stores the chronology of n lines (usually 1 to 5 lines) when scanning the image. Moreover, each time the color pixel data
100
A is input, the line buffer
51
outputs a series of pixel data to the entropy encoding device
52
consisting of the most recently input pixel A and surrounding pixels B, C and D as reference pixel data
110
.
The entropy encoding device
52
uses an arithmetic encoding or Huffman encoding technique. The entropy encoder
52
uses the reference pixel data
110
as status signals, transforms the color pixel data
100
A into encoding data
200
and outputs the same.
On the other hand, the decoding system
60
includes a line buffer
61
and an entropy decoder
62
. The line buffer
61
and the entropy decoder
62
are created such that the input encoding data
200
is decoded and output through a reverse procedure than that taken by the line buffer
51
and the entropy encoder
52
of the encoding system
50
.
The encoding system
50
and the decoding system
60
use completely reversible algorithms to encode the color pixel data
100
A into encoding data
200
, and to decode the encoding data
200
into the color pixel data
100
B. This system is widely used in a variety of applications.
However, when the value or index number of the color pixel data
100
A approaches a certain number, the data compression rate improves. The reference pixel data
110
is used as a status signal of the entropy encoder
52
and the entropy decoder
62
. Hence, by taking a large number of status numbers (i.e., the reference pixel data) the data compression rate improves. In other words, in structuring the entropy encoder
52
and the entropy decoder
62
using an arithmetic encoding or Huffman encoding technique, the data compression rate may be drastically improved by making large disparity in the occurrence probabilities of the symbols 0 or 1. This is because the entropy encoding technique assigns short encoding data to input data with a high occurrence probability while it assigns relatively long encoding data to input data with a low occurrence probability.
In order to obtain large disparity in the occurrence probability of symbols (i.e., index numbers) a method has been used in which the input data is classified into several statuses and encoded. This is because an improved compression rate is not obtained unless the data is classified. For example, in a conventional technology such as shown in FIGS.
16
(A)-(B), reference pixel data is created using the line buffers
51
,
61
and is input in the entropy encoder
52
and the entropy decoder
62
as status signals to be used for classification. The entropy encoder
52
and the entropy decoder
62
classify the input data using the status signals and execute encoding and/or decoding. In other words, the entropy encoder
52
and the entropy decoder
62
compute the occurrence probability of each state of the reference pixel data and assign short encoding data to the combination of data with the higher occurrence probability. This improves the data compression rate.
However, a number of encoding parameter tables corresponding to the number of status of the reference pixel data is necessary for the entropy encoder
52
and the entropy decoder
62
. The larger the number of reference pixel data, the larger the parameter tables for encoding and decoding. Hence, the entropy encoder
52
and the entropy decoder
62
become large in size and more expensive.
For example, suppose that the color pixel data, namely, the index number includes a 4 bit data (16 types), and the number of pixels of the reference pixel data
110
is four. In this case, the number of status of the encoding and the decoding parameter tables becomes 4 pixels×4 bit=16 status per bit, namely 2
16
numbers of status. Hence, a parameter table for 2
16
=65536 entries must be prepared. This shows that an increase in reference pixels results in a large number of encoding and decoding tables which causes the hardware (i.e., the entropy encoder
52
and the entropy decoder) to become large. Moreover, because the target pixel is composed of 4 bits, and because a one bit signal is assigned to each plane, resulting in 16 entries of colors for 4 bits, which in turn requires the parameter table to become a table of 65536×16 as shown in FIG.
18
.
Japanese Laid-Open Patent Publication 6-276041, the subject matter of which is incorporated herein by reference, describes a method of color order transformation in which the disparity of occurrence frequency of color symbols for the target pixel is computed and the index number is rearranged corresponding to the occurrence frequency order. The compression rate is further increased by assigning a short encoding data to the index number with a high occurrence frequency. Japanese Laid-Open Patent Publication 6-276041 also discl
Mehta Bhavesh
Oliff & Berridg,e PLC
Seiko Epson Corporation
LandOfFree
Multi-color image encoding and/or decoding apparatus... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-color image encoding and/or decoding apparatus..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-color image encoding and/or decoding apparatus... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521652