Image analysis – Image compression or coding
Reexamination Certificate
1996-01-30
2001-10-09
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Reexamination Certificate
active
06301389
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the encoding and decoding of digital video image frames, and particularly to the coding of pixel color values.
2. Description of the Related Art
A well known technique is run length coding, used for example as one of the coding modes in the Compact Disc interactive (CD-i) standard. The technique allows sets of adjacent pixel values to be coded more compactly by specifying the color once and then the count of the number (n) of identical pixels instead of repeating the color code (n) times. Further information about run length coding may be found in, for example, “Principles of Interactive Computer Graphics” by W M Newman and R F Sproul, International Student Edition, 1979, pp 287-289, pub McGraw-Hill, ISBN 0-07-066455-2, and a brief summary of the relevant points will be given below with reference to prior art
FIGS. 1
to
3
of the accompanying drawings.
SUMMARY OF THE INVENTION
Whilst run length coding is very efficient in terms of data compression for long runs, this efficiency is reduced for shorter runs and frames with a large number of short runs can be computationally expensive to encode. Accordingly, it is an object of the present invention to provide a coding scheme which achieves at least a reasonable degree of compression without incurring large overheads due to complexity.
In accordance with the present invention there is provided a method of encoding pixel color values for a digital video image frame in which each different color within the image is assigned a color value, where a predominant color is identified for the image frame, and runs of at least two successive pixels of the predominant color are encoded as a first code word indicating a run and a second code word indicating the run length, and wherein pixels having colors other than the predominant color are encoded as codes containing at least the respective color values.
Also in accordance with the present invention there is provided video image encoding apparatus arranged to encode pixel color values for a digital video image frame by assigning to each different color within the image a respective color value, wherein a predominant color is identified for the image frame, the apparatus including means operable to identify runs of at least two successive pixels of the predominant color and encode each such run as a first code word indicating a run and a second code word indicating the run length, and means operable to determine pixels having colors other than the predominant color and encode these as codes containing at least the respective color values.
Still further in accordance with the present invention there is provided a video image signal comprising encoded frames of pixel color values, wherein runs of two or more successive pixels of a predetermined predominant color for the frame are encoded in the form of a first code word indicating a run and a second code word indicating the run length, and pixels of colors other than the predetermined color are encoded in the form of a code containing at least the respective color value. A storage medium (such as a compact or floppy disc) carrying such a video image signal is also provided, together with initialisation data including specification of the said predetermined predominant color.
The invention additionally provides a video image display apparatus arranged to receive and decode signals such as described above, the said apparatus including at least one look-up table of pixel colors, including the predominant color, for the digital video image frames addressed by the encoded pixel color values, and means operable to generate for display runs of at least two successive pixels of the predominant color as well as individually generated pixels having colors other than the predominant color.
In a first embodiment of the invention, only the predominant color of the frame is run length coded. Thus, for the predominant color it is not necessary to specify the color code each time a run is specified. Also, as the predominant color, the efficiency is improved as the likelihood of runs is generally highest. A particularly common situation will be that there will be many runs of short to medium length in the predominant color with fewer such runs in other colors. To achieve higher efficiency for this situation, all runs of, for example, two or more pixels of the same color might be run-length encoded to achieve high data compression but still without the requirement for at least the short to medium length runs (e.g., 3 to 9 pixels) to contain a color code where the run is of the predominant color.
The first code word may suitably include a sub-code indicating one of a number of ranges of run lengths, with the second code word indicating a run length from within the range indicated. In this way, the length of the second code word can be kept shorter than would be the case if the absolute length were required to be specified.
In order to allow for situations where the predominant color changes within the frame (for example a “split-screen” with a different color background in each part), a further code may be provided including specification of a color value, wherein subsequent to the placing of the further code in a stream of pixel color codes, the predominant color specified for encoded runs is changed to the color specified in the further code. This further code is referred to as a CHANGE BACKGROUND code in the following description, and may comprise a first code word indicating a run and a sub-code indicating a change of predominant color, and a second code word comprising the color value for the new predominant color. By having the same sub-code in the first code word to indicate both a run and a change of predominant color, with the difference being indicated by a specific sub-code of the first code word, the number of “control” codes is kept to a minimum, thus allowing a greater number of “free” codes to be assigned to colors.
To avoid the inefficiency associated with run-length coding of short runs, runs of one or two pixels of the predominant color may be respectively coded as one or two successive iterations of the color value for the predominant color, or unique short codes may be respectively assigned.
To allow for the situation where the predominant color changes between successive frames, the code sequence for a frame may suitably commence with the further code specifying the initial predominant color, that is to say instructing a change to the specified predominant color to be used for all subsequent runs, even if unchanged from the previous frame.
If it is the case that the predominant color may change a number of times during the course of a frame, the change command may prove inefficient. Accordingly, in a still further embodiment of the present invention a subset of the colors within the image may be identified as predominant colors, with colors (other than predominant) being assigned respective color codes of a first length, predominant colors being assigned respective color codes of a second length shorter than the first, and runs of one of the predominant colors being encoded as a first code word indicating a predominant color run and a second code word indicating in separate subcodes the run length and (shorter) color code respectively.
REFERENCES:
patent: 4229768 (1980-10-01), Kurahayashi et al.
patent: 4301469 (1981-11-01), Modeen et al.
patent: 4610027 (1986-09-01), Anderson et al.
patent: 4646356 (1987-02-01), Anderson et al.
patent: 4673977 (1987-06-01), Stelzenmuller
patent: 4847677 (1989-07-01), Music et al.
patent: 5032838 (1991-07-01), Murayama et al.
patent: 5046119 (1991-09-01), Hoffert et al.
patent: 5046122 (1991-09-01), Nakaya et al.
patent: 5091977 (1992-02-01), Katata et al.
patent: 5172237 (1992-12-01), Blonstein et al.
patent: 5198898 (1993-03-01), Miyata
patent: 5274719 (1993-12-01), Taniguchi et al.
patent: 5339164 (1994-08-01), Lim
patent: 5537616 (1996-07-01), Higuchi
patent: 5552832 (1996-09-01), Astle
“Principles of Interactive
Hoskins Asher J.
Penna David E.
Couso Jose L.
Gathman Laurie E.
U. S. Philips Corporation
LandOfFree
Video image color encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Video image color encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Video image color encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2582767