Image analysis – Color image processing
Reexamination Certificate
1998-09-18
2003-04-01
Boudreau, Leo (Department: 2621)
Image analysis
Color image processing
C382S166000, C382S164000, C382S171000, C382S173000, C382S232000, C382S246000, C382S253000
Reexamination Certificate
active
06542631
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to a method of encoding a color image to display the color image on a personal computer, a portable terminal, or the like and an encoding device therefor, and a method of decoding the color image and a decoding device therefor.
2. Description of Related Art
Conventionally, when a color image is encoded or decoded, a palette is provided which is formed of a predetermined number of colors. An index is assigned in the palette for each pixel, and the color image is encoded and decoded by encoding and decoding the index.
For example, in a personal computer, game equipment, or the like, an image called a multi-color image is used. The multi-color image is also called a representative color image, a limited color image, or the like. As shown in
FIG. 15
, these are images for which indexes are assigned to specified colors, that is, colors having specified values of R (red), G (green), and B (blue), and which are expressed by a representative color which is limited to 16 colors, 256 colors, or the like by using the data of the indexes.
In this type of the data of the multi-color image, if each color of R, G, and B is hypothetically expressed by 8 bits (256 groups), a total of 24 bits is needed. However, because the index itself is displayed, for example, by 8 bits, the compression percentage is relatively high. However, the amount of information is still large regardless of the compression. Thus, if the information is processed as-is without any consideration, the required memory capacity becomes large and the communication rate becomes slow so that it is not practical. Therefore, the compression technology is extremely important in the multi-color image as well as in other image data. In particular, the number of colors is limited in the multi-color image so that lossless encoding and decoding, that is, a reversible compression technique is needed.
Recently, the technology of using an entropy encoder and decoder has been focused upon as a method of data compression. One example of the entropy encoding and decoding technology is a technology of arithmetical encoding and decoding. The gist of this technology is disclosed, for example, in Japanese Patent Laid-Open Publication Nos. Sho 62-185413, Sho 63-74324, Sho 63-76525, and the like.
FIGS. 20A and 20B
show a conventional multi-color image encoding system
50
and decoding system
60
which uses this type of technology. The encoding system
50
includes a line buffer
51
and an entropy encoder
52
. The data of the index to be input, that is, the color pixel data
100
A, is input to the line buffer
51
and the entropy encoder
52
. The color pixel data
100
A is input as sequential pixel data in a horizontal scanning order which is raster-scanned as shown in FIG.
21
.
Furthermore, as a method for creating the data of the index, that is, the color pixel data
100
A, the method to apply the index in order of the color to be input is common. As shown in
FIG. 19
, phenomena occur such that the colors are significantly different even if the numbers of the index are close (e.g., “1”and “2”) and the colors are close even if the numbers of the index are distant (e.g., “100” and “200”). In order to avoid these phenomena, as shown in Japanese Patent Laid-Open Publication No. Hei 5-328142, there is also a method to apply a sequential number to the approximate color.
The line buffer in the encoding system
50
, which functions as a reference pixel formation means, forms the reference pixel data A, B, C, and D for an encoding object pixel X, i.e., that is to be encoded, from the color pixel data
100
A which was already input. That is, the line buffer
51
stores the history of a portion that includes n lines (approximately 1-5 lines are commonly used) when scanning the image. Furthermore, every time the color pixel data
100
A of the encoding object pixel X is input, a series of pixel data which is formed by the previous pixel A and the surrounding pixels B, C, and D is output to the entropy decoder
52
as reference pixel data
110
.
The entropy encoder
52
is formed by using methods such as an arithmetical encoding and Huffmnan encoding. Furthermore, the reference pixel data
110
is used as a state signal and the object color pixel data
100
A is converted and output to the encoding data
200
.
Meanwhile, the decoding system
60
is structured so as to include a line buffer
61
and an entropy decoder
62
. At this point, the line buffer
61
and the entropy decoder
62
are formed so as to decode and output the encoded data
200
to be input in the completely reverse order of the line buffer
51
and the entropy encoder
52
of the encoding system
50
.
Thus, the encoding system
50
and the decoding system
60
use algorithms which are completely opposite to each other and encode the color pixel data
100
A to the encoded data
200
. Furthermore, it is possible to output the encoded data
200
by decoding the encoded data
200
to the color pixel data
100
B. Therefore, the system can be widely used for various uses.
Here, one example of an arithmetical encoding type of the entropy encoder
52
which is used in the system of
FIG. 20A
is shown in FIG.
22
. Moreover, the structure of the entropy decoder
62
of the arithmetical encoding type is substantially the same as the structure of the entropy encoder
52
, so the explanation is omitted here.
The entropy encoder
52
is structured so as to include an arithmetical operation part
55
and a generation probability formation means
56
which functions as a state memory device. In the generation probability formation means
56
, in order to determine the symbol generation number probability which is needed for encoding, a state parameter table is written. The above-written state parameter is specified by the state signal to be input. Moreover, for the table of the state parameter, which was specified by the state signal, the generation probability operation parameter of the generation probability formation means
56
is output to the arithmetical operation part
55
.
Based upon the generation probability which is thus input, the arithmetical operation part
55
performs entropy encoding, and the color pixel data
100
A to be input is converted and output as the encoded data
200
. Moreover, the generation probability is re-calculated for the state signal by the value of the encoded color pixel data
100
A and is input to the generation probability formation means
56
as an operation parameter update value. The update result is stored in the table as the generation probability of the following data so that the compression efficiency of the entropy encoder
52
improves.
Unlike this type of encoding of a multi-color image, a natural image is fetch-encoded by a scanning device and changed to a multi-color image. In a case like this, in order to efficiently encode the color image, various methods and devices are suggested. For example, in Japanese Patent Laid-Open Publication No. Hei 6-178122, the read image is identified in block units as to whether it is a binary area or a multi-value area, and the respective encoded data of binary image, multi-value image (=natural image), and area information is formed.
Furthermore, in Japanese Patent Laid-Open Publication No. Hei 8-9163, the input color image data is divided into blocks of 16×16 pixels, and it is checked whether each block is a color area or a black-and-white area. With respect to a block of a color area, after sampling is performed in a predetermined sub-sampling ratio, DCT conversion, linear quantization, and entropy encoding are performed. Meanwhile, with respect to a block of a black-and-white area, only the Y component of the color components YCrCb which form the color image data is performed by DCT conversion, linear quantization, and entropy encoding.
Moreover, as a method of compression of two-dimensional image data, using the data information of the previous line is also known (see Japanese Patent Laid-Open Publication No. Hei 7-33
Alavi Amir
Boudreau Leo
Oliff & Berridg,e PLC
Seiko Epson Corporation
LandOfFree
Encoding method of a color image and its encoding device and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Encoding method of a color image and its encoding device and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Encoding method of a color image and its encoding device and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3087333