Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-10-31
2004-06-22
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Lossless compression
Reexamination Certificate
active
06754395
ABSTRACT:
TECHNICAL FIELD
The present invention relates to encoding and decoding techniques for image information, and more particularly, to encoding and decoding techniques for image information whereby Haffman encoding is improved.
BACKGROUND ART
The Haffman encoding technique is known as one type of encoding (compression) and decoding technique for image information. This encoding technique compresses image information by assigning short code words to information having a high frequency of appearance (high occurrence probability) within image information that is to be compressed, and assigning long code words to information having a low frequency of appearance.
However, according to this technique, since a bifurcating scheme is determined for allocating the code words when calculating the appearance frequency of all of the image information to be compressed, the bifurcating scheme differs according to the respective image information. In other words, the structure of the bifurcating scheme is not uniform. When the compressed image information is decoded by hardware, the decoding circuit must be designed to correspond to the structure of the bifurcating scheme, and therefore the hardware design is extremely complex.
Moreover, when decoding image information which has been stored in a memory using this technique, it is necessary previously to read in the correspondence chart (table) for code words assigned to the image information, and since the code words are assigned to each type of image information on a one-to-one basis, the amount of data in the table is large, the table read time becomes long, and moreover, the amount of memory required also increases.
DISCLOSURE OF THE INVENTION
Therefore, it is an object of the present invention to provide an encoding method and decoding method for image information whereby image information can be compressed with good efficiency and decoded readily by hardware. Moreover, it is a further object of the present invention to provide an information storage medium which is encoded by means of the aforementioned encoding method, an image information decoding device for decoding code words recorded on the aforementioned information storage medium, and an image processing device comprising this image information decoding device.
In the image information encoding method according to the present invention, the appearance frequency of all image information items to be encoded is determined, short code words are allocated from predetermined code words in accordance with leaves of a bifurcating scheme to image information items having an appearance frequency up to a predetermined ranking, in sequential fashion starting from the image information item having the highest appearance frequency, and a predetermined identifier (header) is appended to the beginning of each of the remaining image information items, the resulting codes being taken as the respective code words allocated to the remaining image information items.
In other words, in addition to assigning short code words to image information items having a high appearance frequency, in a similar manner to a conventional Haffman encoding technique, image information items having an appearance frequency of a specified ranking or lower fare encoded by appending an identifier to the beginning of said image information items. In particular, it is desirable if the bifurcating scheme has a predetermined structure. By previously fixing the structure of the bifurcating scheme, the design of the decoding circuit is markedly simplified.
Furthermore, the identifier is set as a code word which does not match the combination pattern of any other code word. For example, it is set as a code word corresponding to any leaf of the aforementioned bifurcating scheme.
Moreover, the length of the code words allocated to the remaining image information items is uniform. By adopting this encoding method, a decode operation for the aforementioned image information can be performed readily by hardware.
Moreover, desirably, the image information items are differential values of image information between adjacent picture elements. Generally, there is a strong correlation between adjacent pixels in image information, and by deriving the differential values between pixels, it is possible to obtain image information which approximates ‘0’ and hence the compression rate for the image information can be improved. Furthermore, image information containing colour data in RGB format, or the like, is suitable as the image information to be encoded.
The image information decoding method according to the present invention is a method for decoding image information encoded by means of the encoding method of the present invention, characterized in that, when the beginning of the code word matches the identifier, the code following the identifier, being of a code length corresponding to the information volume (for example, 8 bits) of the image information items, is decoded as the code word assigned to the image information item which is equivalent to the code, and when the beginning of the source code does not match the identifier, the source code is decoded by referring to a table of source codes assigned to each image information item.
The information storage medium according to the present invention is a computer-readable information storage medium storing image information encoded by means of the encoding method of the present invention. Here, an information storage medium is a medium on which information, principally, image information, as well as other digital data, image processing programs, and the like, is stored by physical means of some kind, and which is capable of causing prescribed functions to be executed in a computer, and in particular, a dedicated processor (for example, a video display processor), or the like. Consequently, it should be capable of downloading information to a computer by means of some kind, in order to cause prescribed functions to be implemented. Examples of such a medium include: a flexible disk (FD), hard disk (HD), CD-ROM, CD-R, DVD-ROM, DVD-RAM, DVD-R, PD disk, MD disk, MO disk, or the like.
Moreover, image information principally signifies colour data (RGB data in the case of an RGB system, and palette numbers in the case of a palette system), but also includes various image processing control information, such as transparency processing control flags, window control flags, and the like. Furthermore, this image information also includes data from which original image information (original data) can be obtained reversibly by performing prescribed calculations, such as the differential values in image information between picture elements.
The image information decoding device according to the present invention comprises: first storage means for reading out code words from the information storage medium according to the present invention, in sequential fashion, and storing same temporarily; second storage means for storing a correspondence table for the code words and corresponding image information items; and a decoding circuit which, if the beginning of the code word sequence stored in the first storage means matches the identifier, outputs the code following the identifier, being a code having a code length corresponding to the information volume of the image information items, as a decode result, and if the beginning of the code word does not match the identifier, outputs a decode result for the code word by referring to the table stored in the second storing means. This image information decoding device may be used in an image processing device, such as a video game device, or the like, for example.
REFERENCES:
patent: 5227875 (1993-07-01), Suu et al.
patent: 5600812 (1997-02-01), Park
patent: 5673042 (1997-09-01), Yoshida et al.
patent: 5764804 (1998-06-01), Yajima et al.
patent: 6121903 (2000-09-01), Kalkstein
patent: 6188338 (2001-02-01), Yokose
patent: 2267410 (1993-12-01), None
patent: 6-44038 (1994-02-01), None
patent: 8-18981 (1998-01-01), None
patent: 10-022835 (1998-01-01), None
J.A. Storer
Ishiyama Masahiro
Kaji Toshiyuki
Couso Jose L.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Kabushiki Kaisha Sega Enterprises
LandOfFree
Image information encoding method and decoding method 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 information encoding method and decoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image information encoding method and decoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3312285