Amusement devices: games – Including means for processing electronic data – Perceptible output or display
Reexamination Certificate
1999-12-03
2002-07-09
Martin-Wallace, Valencia (Department: 3713)
Amusement devices: games
Including means for processing electronic data
Perceptible output or display
C463S032000, C463S034000, C463S043000, C345S614000, C345S629000, C345S631000, C345S684000, C345S688000, C382S232000, C382S233000, C704S503000, C704S504000
Reexamination Certificate
active
06416410
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to data compression/decompression and more particularly, to image data compression and decompression. Still more particularly, the present invention relates to run length encoding of patterns and symbols (e.g., characters) to provide efficient and rapid loss-less decompression of character-mapped graphics data within a limited resource environment such as a handheld portable video game system.
BACKGROUND AND SUMMARY OF THE INVENTION
The world of video games has been transformed by the increased amount of computing power that can be placed on a single semiconductor integrated circuit chip. Games that just a few years ago were available only on expensive arcade video systems can now be played on inexpensive handheld portable video game systems.
The GAME BOYS® and GAME BOY COLOR® portable video game systems sold by Nintendo have become quite popular in recent years. These handheld systems offer impressive interactive video game play in a very compact and inexpensive (less than $100) package. One of the challenges facing game developers for these systems is how to develop increasingly sophisticated and complex games that are fun and interesting and yet operate within the very limited memory and processing resources these systems offer.
As one example, suppose one wants to implement an adventure game on GAME BOY COLOR®. The display memory of GAME BOY COLOR® stores a background character map that is several (e.g., four to eight) times larger than the screen the liquid crystal display can display at one time. This allows for smooth scrolling of a display “window” within a larger virtual display area (for example, a landscape or “level” within the adventure game). But suppose one desires to make a very interesting adventure game allowing smooth scrolling within an expansive landscape comprising many hundreds of image screens. The limited display memory of GAME BOY COLOR® cannot store so many screens worth of image information at one time, and storing this many screens of image information in a game cartridge will require a large amount of read only memory space. One way to solve this problem is to use data compression to transform the image data so it occupies less space.
Because images can take up a lot of storage space, data compression is especially important in computer graphics. Computer scientists have developed a variety of data compression techniques for graphics files. A useful survey of a variety of compression techniques that have been applied to graphics files can be found in Chapter 9 (“Data Compression”) of Murray et al,
Graphics File Formats
(O'Reilly & Associates, 2d Ed. 1996) at pages 153-218.
Generally, two kinds of data compression exist: lossless compression in which no loss of data occurs during compression, and lossy compression, in which some data is lost and is not incorporated in the compressed data. In general, both types of data compression techniques rely on reducing the amount of data redundancy in the compressed image. Data compression is a type of data encoding that is used to reduce the size of the data file. The process of converting recurring characters or patterns into shorter symbols, known as codes, is called encoding. The process of translating codes back into the original characters or patterns is called decoding.
One simple but effective data compression technique commonly used in the past for compressing graphics files is called run length encoding. Run length encoding is supported by many commonly-used bitmap graphics file formats such as, for example, TIFF, BMP and PCX. Run length encoding works by reducing the physical size of a repeating string of symbols (e.g., characters). This repeating string, called a “run”, is typically encoded into two bytes. The first byte, called the “run count,” represents the number of symbols in the run. The second byte, called the “run value,” is the value of the symbol in the run (in the range of 0 to 255 binary for ASCII characters). For example, a character run of 15 “A” characters (“AAAAAAAAAAAAAAA”) would normally require 15 bytes to store. The same string after run length encoding would require only two bytes: “15A”.
Although much data compression work has been done in the past, further improvements are possible. In particular, there is a need for a data compression and decompression technique that has the simplicity, efficiency and low overhead associated with run length encoding techniques, but which is especially suited for character-mapped image and attribute data and allows efficient image decompression in a limited resource system such as a handheld portable video game system.
The present invention provides a new and improved data compression technique that enhances typical run length encoding by examining the input image file and finding the recurrence of symbols as well as recurrence of patterns of symbols that could be represented by shorter symbols. This multi-level compression technique can be implemented quite efficiently using only a small amount of overhead data so that resulting compressed image data can be efficiently decompressed, at run time “on the fly”, in a processing-and-memory constrained environment such as a compact portable video game system. Such loss-less data compression/decompression is especially useful in a limited resource environment such as a handheld portable video game system, since it allows graphics and/or attribute data to be efficiently and quickly decompressed on an as-needed basis in real time response to interactive user inputs.
In the preferred embodiment, a common “sentinel” field format encodes whether data following the field is non-redundant data, a symbol run, or a pattern run. Compression ratios of 60% for representative character-mapped video display graphics/attribute files can be achieved.
A data compression method in accordance with one aspect of the invention is characterized by scanning an input file to detect pattern and symbol redundancy; if the scanning step reveals a pattern redundancy, run length encoding said pattern redundancy and writing said run length encoded pattern redundancy to an output file; if the scanning step reveals symbol redundancy, run length encoding said symbol redundancy and writing said run length encoded symbol redundancy to said output file; and if the scanning step reveals neither symbol redundancy nor pattern redundancy, writing non-redundant information to said output file.
A data decompression method is characterized by reading, within an input file, a predetermined data format capable of indicating any of (a) pattern redundancy, and (b) symbol redundancy; if the predetermined data format indicates pattern redundancy, run length decoding a redundant pattern run associated with said predetermined data format; if the predetermined data format indicates symbol redundancy, run length decoding a redundant symbol run associated with said predetermined data format; and if the predetermined data format indicates neither pattern redundancy nor symbol redundancy, reading non-redundant data associated with said predetermined data format.
The predetermined data format may comprise a sentinel field format including a first field indicating redundancy or non-redundancy and a second field indicating the number of redundant symbols if symbol redundancy exists, the value of said first and second fields together being encoded with a predetermined value if the scanning step reveals pattern redundancy.
REFERENCES:
patent: 4398189 (1983-08-01), Pasierb, Jr. et al.
patent: 4580134 (1986-04-01), Campbell et al.
patent: 5353061 (1994-10-01), Rodriguez et al.
patent: 5371512 (1994-12-01), Otake et al.
patent: 5418568 (1995-05-01), Keith
patent: 5434568 (1995-07-01), Moll
patent: 5483257 (1996-01-01), Otake et al.
patent: 5600316 (1997-02-01), Moll
patent: 5996033 (1999-11-01), Chiu-Hao
patent: 6139433 (2000-10-01), Miyamoto et al.
patent: 6198477 (2001-03-01), Kurtze et al.
patent: 6215523 (2002-04-01), Anderson
patent: 0 581 713 (1994-02-01), None
patent: 0 783 208 (1997-07-01), None
Mu
Abou-Samra Samir
Champagne Robert
Comair Claude
Fam Sun Tjen
Ghali Prasanna
Martin-Wallace Valencia
Nguyen Binh-An
Nintendo Co. Ltd.
Nixon & Vanderhye P.C.
LandOfFree
Data compression/decompression based on pattern and symbol... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression/decompression based on pattern and symbol..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression/decompression based on pattern and symbol... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2871192