Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2000-09-06
2004-03-23
Mariam, Daniel (Department: 2621)
Image analysis
Image compression or coding
Adaptive coding
C382S235000, C348S404100, C358S426020
Reexamination Certificate
active
06711296
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus for performing loss-less compression-coding of adaptive evolution type on image data.
2. Description of the Related Art
A conventional loss-less compression-coding apparatus is disclosed in Kato and Suzuki, “Loss-less Compression-Coding for Still Image”, Interface (Japan), September 1996, pp 104-115.
FIG. 1
shows the conventional apparatus for effecting loss-less compression-coding on image data. As shown in
FIG. 1
, the apparatus comprises a modeling circuit
101
and an entropy encoder
102
. The modeling circuit
101
converts original image data to converted data which can be highly compressed and coded by the entropy encoder
102
. One example of the converted data is a signal obtained by extracting statistical characteristics from the original image data. The entropy encoder
102
allocates a code to each item of the converted data output from the modeling circuit
101
. In other words, the encoder
102
performs compression-coding on the converted data.
With entropy coding, it is impossible to produce a code series that has less entropy than the converted data generated by the modeling circuit
101
. Hence, the compression ratio depends upon whether or not the modeling circuit
101
can convert the image data to converted data of small entropy.
The term “entropy” used here means the amount of data, which constitutes one message, Assume that there are M massages m
1
, m
2
, . . . that have probabilities of occurrence P
1
, P
2
, . . . , respectively, and that N messages of these are transmitted for a considerable length of time. The total amount I of data sent in the form of the N messages is given as follows:
I
=
∑
i
=
1
M
p
i
N
ln
(
1
/
P
i
)
(
1
)
The average amount of data for each message, i.e., the entropy H, is calculated as follows:
H
=
I
/
N
=
∑
i
=
1
M
p
i
ln
(
1
/
P
i
)
(
2
)
Entropy coding is, by definition, the technique of allocating codes to a signal series and finding the coded data that has an average length as similar as possible to the desired entropy.
Run-length coding, Markov model coding, predictive coding and the like have been proposed as practical modeling methods. A conventional loss-less compression-coding apparatus designed to perform Markov model coding will be described, with reference to FIG.
2
.
Generally, each pixel value contained in image data greatly depends on the values of the neighboring pixels. The pixel value represents the gray level of a pixel; it is “0” or “1” for a binary image, and is one ranging from “0” to “255” for a 256-level image. The dependency each pixel value has on the neighboring pixels is utilized in the loss-less compression-coding apparatus that performs Markov model coding. In the apparatus, some of the neighboring pixels already coded are selected for reference pixels. Then, a probability of occurrence is estimated for the value of the pixel to be coded, on the basis of various patterns (or combinations) of the reference pixels. In accordance with the probability of occurrence thus estimated, or the statistical characteristics of the pixel, a suitable code is efficiently allocated to the pixel, thus encoding the pixel. The pattern the reference pixels constitute will be referred to as “context” hereinafter.
As shown in
FIG. 2
, the loss-less compression-coding apparatus that preforms Markov model coding comprises a context generator
201
and an entropy encoder
202
. Original image data
203
is input to the context generator
202
and entropy encoder
202
. The context generator
201
is equivalent in function to the modeling circuit
101
of the apparatus shown in FIG.
1
. The generator
201
generates a context
204
from the image data to be coded while being compressed. Note that the context
204
is composed of a plurality of reference pixels. The context
204
is supplied to the entropy encoder
202
. The encoder
202
, which is equivalent to the entropy encoder
102
of the apparatus shown in
FIG. 1
, effects compression-coding of the image data
203
by using the context
204
to extract the statistical characteristics from the original image data
203
.
To generate a context, the context generator
201
uses a template of the type shown in
FIG. 3
, which designates the positions of the reference pixels with reference to the target pixel to be coded. The template enhances the coding efficiency if designed in accordance with the type of the image (characters, figures, dithered image or the like), as is reported in Kato and Yasuda, “Adaptive Markov Model Coding for Two-Level Images by Dynamically Selecting Reference Pels”, Transaction of Institute of Electronics, Information, and Communication engineers in Japan, Vol. J 70-B, No. 7, pp 798-804, July 1987.
However, the conventional techniques described above transaction are disadvantageous in the following respects:
(1) The reference pixels cannot be located at any of desired positions. In other words, the context, i.e., the combination of reference pixels, cannot be designed freely.
(2) No devices are available that can optimize the context.
BRIEF SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide an apparatus for effectively performing loss-less compression-coding of adaptive evolution type on image data.
An image coding apparatus according to the present invention comprises a context generator configured to select a reference pixel that has been coded in image data to generate a context formed of the selected reference pixel, an entropy encoder configured to code the image data based on the context to generate coded data, an evaluation value calculator configured to calculate a compression ratio based on the image data and the coded data to output the compression ratio, and an adaptive evolution processor configured to perform adaptive evolution based on the compression ratio to find optimal reference pixels for the image data, the optimal reference pixels being supplied to the context generator for optimizing the context.
Additional objects and advantages of the present invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the present invention.
The objects and advantages of the present invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.
REFERENCES:
patent: 5835034 (1998-11-01), Seroussi et al.
patent: 5970174 (1999-10-01), Peters
patent: 6449393 (2002-09-01), Peters
patent: 5-64007 (1993-03-01), None
patent: 6-90363 (1994-03-01), None
patent: 6-326876 (1994-11-01), None
patent: 11-243491 (1999-09-01), None
Storer et al., “Data Compression Conference”—Mar. 30, 1998, pp. 219-228.
“Fifteenth National Conference on Artificial Intelligence”—Jul. 26, 1998, pp. 486-491.
Sipper et al., “Evolvable Systems: From Biology to Hardware”—ICES 98, Sep. 23, 1998, pp. 106-114.
“IEEE International Conference on Systems, Man, and Cybernetics”—Oct. 12, 1999.
“FAN Symposium '98”—Oct. 29, 1998, pp. 319-324.
“IEICE Technical Report”—vol. 99, No. 95, May 27, 1999—pp. 17-24.
“IEICE”—vol. J83, No. 5, May 2000—pp. 1274-1283.
Kato et al; “Loss-Less Compression-Coding for Still Image”; Interface, Sep. 96, pp. 104-115—(Discussed in the spec.).
Kato et al; “Adaptive Markov Model Coding for Two-Level Image by Dynamically Selecting Reference Pels”; Transaction of Institute of Electronics, Information and Communication engineers in Japan; vol. J. 70-B, No. 7, pp. 798-804; 1987. (Discussed in the spec.).
Higuchi Tetsuya
Kurita Takio
Sakanashi Hidenori
Tanaka Masaharu
Armstrong Kratz Quintos Hanson & Brooks, LLP
Japan as represented by Secretary of Agency of Industrial Scienc
Mariam Daniel
LandOfFree
Apparatus for performing loss-less compression-coding of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for performing loss-less compression-coding of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for performing loss-less compression-coding of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3221128