Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-12-26
2004-02-03
Wu, Jingge (Department: 2623)
Image analysis
Image compression or coding
Transform coding
Reexamination Certificate
active
06687411
ABSTRACT:
TECHNICAL FIELD
This invention relates to an image coding/decoding method and to a recording medium on which a program for this method has been recorded. More specifically, the invention relates to an image coding/decoding method that is capable of reproducing a high-quality image (CG images, animated images and natural images, etc.) at high speed even with comparatively low-performance hardware (CPU, memory, etc.) such as that of a game machine, and to a recording medium on which the program of this method has been recorded.
BACKGROUND ART
FIGS. 16 and 17
diagrams (
1
), (
2
), for describing the prior art, in which
FIG. 16
illustrates the concept of image compression processing in accordance with the JPEG standard.
In accordance with the JPEG standard, which currently is the main scheme for compressing still pictures, an image is divided into blocks of 8×8 pixels, as shown in FIG.
16
(A), and the block is converted to DC (a mean value) and to coefficient values ranging from a fundamental frequency to a frequency which is 63 times the fundamental frequency by a two-dimensional DCT (Discrete Cosine Transform). By utilizing the fact that the frequency components of a natural image concentrate in the low-frequency region, each coefficient value is quantized at a different quantization step to such an extent that image quality will not decline, and variable-length coding (Huffman coding) is performed after the quantity of information is reduced.
In a case where such coded image data is utilized in a home game machine, the fact that there are limitations upon CPU performance and memory capacity results in various disadvantages when an image compression method (JPEG, etc.) involving a large decoding burden is implemented by software. For example, with the JPEG scheme, 64 codes for undergoing variable-length coding are generated for a block of 8×8 pixels, thereby inviting an increase in computation load at the time of decoding.
FIG.
16
(B) illustrates a portion of Huffman code.
With Huffman coding, a coefficient H
13
, etc., having a high frequency of appearance is coded by bits of relatively short code length, and a coefficient H
6
, etc., having a low frequency of appearance is coded by bits of relatively long code length. As a consequence, these codes are packed into each octet (byte) unevenly in the manner illustrated. This increases computation load greatly at the time of decoding. In a conventional game system, therefore, the state of the art is such that sacrifice of image quality is inevitable in order to decode images at a speed that allows the images to appear as a moving picture.
In regard to image quality, the higher the frequency component, the coarser the precision with which quantization is carried out. As a result, image information concerning contours is lost, thereby producing mosquito noise. Such a scheme is not suitable for the compression of characters and animated images. In particular, since game software makes abundant use of artificial images (CG images and animated images, etc.), a decline in subjective image quality due to mosquito noise is a major problem.
In this regard, the following literature (1) to (5) has been reported in recent years:
(1) Michael F. Barnsley, Lyman P. Hurd “FRACTAL IMAGE COMPRESSION”, A K Peters Ltd., 1993;
(2) Takashi Ida, Takeshi Datake “Image Compression by Iterative Transformation Coding”, 5
th
Circuit and System Karuizawa Workshop Collection of Papers, pp. 137-142, 1992;
(3) Hyunbea You, Takashi Takahashi, Hiroyuki Kono, Ryuji Tokunaga “Improving LIFS Image Coding Scheme by Applying Gram Schmidt Orthogonalization”, The Institute of Electronics, Information and Communication Engineers Research Report, vol. NLP-98, no. 146, pp. 37-42, 1998;
(4) Toshiaki Watanabe, Kazuo Ozeki “Study of AC Component Prediction Scheme Using Mean Values”, Image Coding Symposium (PCSJ89), pp. 29-30, October 1989; and
(5) Takashi Takahashi, Ryuji Tokunaga “High-Speed Computation Algorithm for Predicting AC Components from Block Mean Values of Images”, The Institute of Electronics, Information and Communication Engineers Papers, Vol. J81-D-II, No. 4, pp. 778-780, April 1998.
Schemes (1) and (2) relate to fractal coding as a compression method involving little decoding computation load, scheme (3) relates to improvements in adaptive orthogonal transformation having a coding efficiency equivalent to that of the JPEG scheme, and schemes (4) and (5) concern AC-component prediction based upon block mean values (DC values).
Among these, scheme (3) is a block coding method which divides an image into square blocks of K×K pixels and approximates all blocks by the AC-component prediction method, fractal conversion method or adaptive orthogonal transformation, depending upon an allowable error Z. The AC-component prediction method is utilized in block coding by mean-value separation in which an AC component (addition data) of a local block is found from the block mean values (DC values) of blocks surrounding the local block, and the residual between this and an image of interest is coded. Adaptive orthogonal transformation is a method in which use is made of the autosimilarity possessed by an image, a base vector for approximating a block image is extracted from an image (nest) corresponding to a vector quantization code book, and an orthogonal base system of the minimum required dimensions is constructed by the Gram Schmidt Method.
However, the fractal conversion of schemes (1) and (2) necessitates iterative computation in decoding and consumes work space on the scale of the image plane. This scheme is therefore not suitable for video game machines.
The adaptive orthogonal transformation of scheme (3) utilizes addition data, the size of which is equivalent to that of the image of interest, as a nest. As a consequence, a very large work space is required at the time of decoding. Furthermore, though image quality is improved because blocks decompressed at the time of decoding are sequentially written back to corresponding blocks in the nest, the load imposed by address computation and data transfer is great. Further, Huffman coding is applied to compression of the coordinates of the base and to sampling coefficients in scheme (3). In the case of a natural image, however, large deviations are absent in the frequency of occurrence of any base whatsoever. Consequently, not only is there no improvement in compression efficiency but what is expended is only the amount of computation of Huffman code. With adaptive orthogonal transformation, there are cases where, depending upon the image, the number of orthogonal bases of the minimum required number of dimensions is large. When the number of bases is large, however, the number of bits used is greater than when the residual vector is coded directly, and coding efficiency declines as a result.
With the AC component prediction method of scheme (4), there is a tendency for overshoot or undershoot to occur in the vicinity of contours in the image, and image quality tends to be degraded in the case of artificial images in which luminance rises sharply.
In the case of the indirect method of AC component prediction of scheme (5), not only is the load on the CPU great but it is also required to have a storage area for interpolated values that are generated along the way.
FIG. 17
illustrates the concept of the indirect method of AC component prediction.
In accordance with indirect method of AC component prediction, as shown in FIG.
17
(A), the DC values of sub-blocks S
1
~S
4
in a block S of interest are estimated in accordance with the following equations from the DC values (S, U, R, B, L) of four surrounding blocks and the block of interest:
S
1
=S+
(
U+L−B−R
)/8
S
2
=S+
(
U+R−B−L
)/8
S
3
=S+
(
B+L−U−R
)/8
S
4
=S+
(
B+R−U−L
)/8
In FIG.
17
(B), the above equations are applied recursively, whereby the pixel values of four pixels P
1
~P
4
in sub-block S
1
can be estimated in acc
Itagaki Fumihiko
Kawashima Miyuki
Miura Takashi
Hudson Co., Ltd.
Katten Muchin Zavis & Rosenman
Wu Jingge
LandOfFree
Image coding/decoding method and recording medium having... 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/decoding method and recording medium having..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image coding/decoding method and recording medium having... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3325094