Image analysis – Image compression or coding – Interframe coding
Reexamination Certificate
1999-01-22
2004-02-10
Couso, Jose L. (Department: 2721)
Image analysis
Image compression or coding
Interframe coding
C382S251000
Reexamination Certificate
active
06690834
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the compression of pixel data.
2. Related Art
In picture processing applications, particularly video display applications such as those that use one or more standards defined by the Motion Picture Group (MPEG). The amount of memory space required to display and process picture data can be quite large, and can sometimes exceed the capability of the processing entity, commonly a graphics processor in a computer.
As an example, when utilizing the MPEG 2 standard method of processing motion picture data in the PAL format, the amount of picture data which must be stored per frame can be as much as approximately 2.5 megabytes of raw data. Without compression, this image would require five 256 K×16 bit memory chips for display. However, using a compression algorithm, the same 2.5 megabyte image can be stored in 2.0 megabytes or less, requiring only four memory chips instead of five. This reduction in memory requirements translates into real cost savings when considering engineering design time, component costs, and the physical space needed for more memory devices and associated control circuits. Thus, it is desirable to reduce the amount of memory space required for storing and displaying pixel data.
One method that is sometimes used in other picture processing contexts is to compress the picture data, that is to rewrite the data in another format, which requires less memory space. There are two types of compression, lossless and lossy. In lossless compression, the entire amount of information can be recovered from the compressed data; whereas in lossy compression, the process of compression loses some information.
Lossless compression would have the advantage of preserving the original pixel data and allowing that information to be recovered from the compressed data. However, known methods of lossless compression, such as the Liv-Zempel compression algorithm, may record individual pixels in fewer or more bits than in the original pixel data, and thus do not preserve the relative locations of pixels in memory. Thus, it can be difficult to identify the pixel data associated with a particular selected pixel.
Known methods of lossy compression suffer from the drawback that information which is lost is occasionally apparent to a viewer, resulting in a degraded display of the video data on the screen. The visual fidelity of the displayed picture width respect to the original image is then lower than desired.
It would be advantageous to provide a method of compressing pixel data in which the compressed pixel data has a high degree of fidelity with the original pixel data, and in which data associated with each pixel of information in a video display can be quickly and easily located i.e. randomly accessed quickly and with the minimum logic. It would also be advantageous to provide a method of compressing data which upon decompression is scalable and capable of being displayed in multiple environments such as TV, PC, or PDA environments.
SUMMARY OF THE INVENTION
The invention provides a method and system for pixel data compression in which sets of adjacent pixels are compressed as a block, in a manner, which is sometimes lossy and sometimes lossless. When lossy, the greatest loss in fidelity between the original and the compressed pixels is almost entirely reserved for circumstances where the loss is masked by the high-frequency components of the video data, resulting in a display which is indistinguishable from the original picture.
This invention is not format restricted, and can be used with other video signal formats such as SECAM, NTSC, etc. Depending on the video format being used, there are generally several pixel values which when used together, make up the pixel represented on the display screen. For a pixel R, there might be three bytes of data, each representing a degree of color, one for red, one for green, and one for blue. When choosing the values to be compared in the extant method, data representing common pixel attributes are compared and compressed together. For instance, in pixels R
1
through R
4
, each represented by pixel values 1 through 3, pixel values R
11
, R
21
, R
31
and R
41
would be compared for similarity. Next, pixel values R
12
, R
22
, R
32
, and R
42
might be compared, and so on.
The plurality of pixel values in the block are reformatted using a technique in which a first pixel value is represented as an approximate absolute value, and a set of dependent pixel values are represented as approximate relative differences in value. In cases where the relative differences are small or zero, the compression is completely lossless. In cases where the relative differences are larger, the formatting of the first pixel value is responsive to the degree of lossiness required to encode all of the pixels in the memory space allotted.
In a preferred embodiment, the first pixel value and the corresponding dependent pixel relative differences are compressed to a sufficient degree that the resulting compressed values fit within the available memory space.
REFERENCES:
patent: 4562305 (1985-12-01), Gaffney
patent: 4675612 (1987-06-01), Adams et al.
patent: 4713621 (1987-12-01), Nakamura et al.
patent: 4823260 (1989-04-01), Imel et al.
patent: 4876660 (1989-10-01), Owen et al.
patent: 5142380 (1992-08-01), Sakagami et al.
patent: 5191548 (1993-03-01), Balkanski et al.
patent: 5196946 (1993-03-01), Balkanski et al.
patent: 5218431 (1993-06-01), Gleicher et al.
patent: 5253078 (1993-10-01), Balkanski et al.
patent: 5270832 (1993-12-01), Balkanski et al.
patent: 5341318 (1994-08-01), Balkanski et al.
patent: 5379356 (1995-01-01), Purcell et al.
patent: 5528309 (1996-06-01), Nguyen
patent: 5574572 (1996-11-01), Malinowski et al.
patent: 5612743 (1997-03-01), Lee
patent: 5638130 (1997-06-01), Linzer
patent: 5650824 (1997-07-01), Huang
patent: 5719511 (1998-02-01), Le Cornec et al.
patent: 5790881 (1998-08-01), Nguyen
patent: 5832120 (1998-11-01), Prabhakar et al.
patent: 5844617 (1998-12-01), Faroudja et al.
patent: 5867601 (1999-02-01), Phillips
patent: 5982459 (1999-11-01), Fandrianto et al.
patent: 6084909 (2000-07-01), Chiang et al.
patent: 6184936 (2001-02-01), Hu
patent: 6205255 (2001-03-01), Mak
patent: 6275263 (2001-08-01), Hu
patent: 6412024 (2002-06-01), Hsu et al.
patent: 6421096 (2002-07-01), Nguyen
patent: 6427203 (2002-07-01), Le Cornec
patent: 6448825 (2002-09-01), Le Cornec et al.
patent: 6501512 (2002-12-01), Nguyen et al.
patent: 2002/0075411 (2002-06-01), Nguyen
patent: WO 9210911 (1992-06-01), None
Greg Pastrick. “Full Motion Video: ReelMagic Points to a Future of Fast, Full-Screen Film Clips”. Feb. 8, 1994. PC Magazine.
Tsai Y T: “Color Image Compression for Single-Chip Cameras” IEEE Transactions on Electron Devices, vol. 38, No. 5, May 1, 1991, pp. 1226-1232, XP000200683, see abstract; figures 1, 6.
Couso Jose L.
Dang Duy M.
Sigma Designs, Inc.
Swernofsky Law Group PC
LandOfFree
Compression of pixel data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression of pixel data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression of pixel data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3349068