Image analysis – Color image processing – Compression of color images
Reexamination Certificate
1999-03-19
2003-06-03
Wu, Jingge (Department: 2623)
Image analysis
Color image processing
Compression of color images
Reexamination Certificate
active
06574364
ABSTRACT:
The present invention relates to the encoding and decoding of whole or partial digital video image frames, where a partial frame may be in the form of a graphic overlay on a full motion video (FMV) image, and particularly to the coding of pixel color values.
A known technique for pixel color value encoding is run length coding. 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.
An example of an encoding and decoding system making use of run length coding to reduce the necessary volume of data to code whole or partial image frames is given in International patent application WO 96/25010 commonly assigned with the present application. In the example, a method is described of encoding pixel color values for a digital video image frame in which each of up to 15 different colors within the image is assigned a color value. A predominant color (i.e. the most commonly occurring pixel color value) is identified for the image frame and, in a first embodiment, each pixel having one of the 14 colors other than the predominant color is separately coded simply identifying its respective color value (the codes
0010
to
1111
being used), with runs of three or more successive pixels of the predominant color being run-length encoded. A further code (
0000
0011
followed by a four bit color code), similar in arrangement to that indicating a run, is provided to allow a change in the specified predominant color during the course of a frame. In a further embodiment, runs of all colors are run-length encoded but with a shorter coding scheme for runs of the predominant color or, in a still further embodiment, a small range of predominant colors.
A principle use for these coding schemes is to improve efficiency of coding for certain classes of image material, in particular subtitling or other text boxes to be displayed overlaid on a video image. For such applications, the particular aim is to achieve at least a reasonable degree of compression without incurring large overheads due to complexity. For the particular case of recorded video, where the subtitling or other data may be stored as, for example, a separate file on an optical disc, the requirement for compression increases due to the limitations of available storage space whilst efficiency must not be degraded to the point where decoding and regeneration of the data becomes a significant factor affecting playback performance.
It is accordingly an object of the present invention to provide a coding methodology for pixel color values which provides good compression without causing undue delays in decoding.
It is a further object to provide a means for encoding and decoding according to such a methodology.
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, wherein a predominant color is identified for the image frame, and runs of at least three successive pixels of the predominant color are encoded as a first code indicating a run and a second code indicating the run length; characterised in that runs of successive pixels having a color other than the predominant color are encoded as successive iterations of a code containing only the respective color value when the run length is less than or equal to a threshold value and as a first code indicating a run, a second code indicating a run length, and a third code identifying the color value when the threshold value is exceeded.
As will become apparent hereinafter, the present invention is optimised for limited color schemes and especially for the coding of text blocks, although it is not limited to such. In an embodiment to be described, four different colors including the predominant color may be supported with each pixel having a color other than the predominant color being separately coded as a 2-bit code: the predominant color is likely but not certain to be a background color and the three remaining colors may be respectively assigned to foreground and to two intermediate levels between foreground and background for the purposes of anti-aliasing. By keeping the non-predominant color codes short, the repetitive iterations for short to medium length runs (i.e. below the threshold—which threshold may differ for different colors) do not generate an excessive bit load.
For increased savings, one of the colors other than the predominant color may be selected, with a range of run lengths between minimum and maximum values being specified for that color, wherein: runs of the selected color below the minimum value are coded as separate iterations of the color code; runs of the selected color between the minimum and maximum values are coded as a first code indicating a run of that color and a second code indicating the length; and runs of the selected color above the maximum value are coded as a first code indicating a run, a second code indicating a run length, and a third code identifying the color value of the selected color. With this shortened code for short to medium runs (e.g. 4 to 11 pixels) in what may be the text color for subtitling applications for example, the present applicants have found that further bit-savings. of up to 5% in relation to the Digital Video Broadcast 2-bit coding standard may be achieved.
In a practical arrangement, all codes for a pixel or a run preferably comprise an integer number of bit-pairs for ease of decoder implementation. A further code may be provided, wherein subsequent to the placing of the further code in a stream of pixel color codes, the color specified for the immediately preceding pixel is applied to all further pixels to the end of a display line. This further code is suitably only used if run-length specification of the remainder of the line or repeated iterations of the color code per pixel do not require fewer bits to specify, that is to say if the further code is the most economical option.
A still further code may be provided in a stream of pixel color codes, with the code identifying to a host decoder a predetermined and stored pattern of pixel color values to be called up and applied to the following pixels.
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; characterised in that the apparatus includes means arranged to identify runs of successive pixels having a color other than the predominant color and encode the same as successive iterations of a code containing only the respective color value when the run length is less than or equal to a threshold value and as a first code indicating a run, a second code indicating a run length, and a third code identifying the color value when the threshold value is exceeded.
Further in accordance with the present invention there is provided a video image signal comprising encoded frames of pixel color values, a storage medium carrying such a video image signal, and video image playback apparatus as defined in the attached claims, the disclosure of which is incorporated herein and to which reference should now be made.
REFERENCES:
patent: 4760459 (1988-07-01), Sato et al.
patent: 4843466 (1989-06-01), Music et al.
patent: 5353132 (1994-10-01), Katsuma
patent: 5467134 (1995-11-01), Laney et al.
patent: 5625712 (1997-04-01), Schoenzeit et al.
patent: 6014464 (2000-01-01), Kurzweil et al.
patent: 6035059 (2000-03-01), Kurosawa et al.
patent: 6205255 (2001-03-01), Mak
patent: 6259810 (2001-07-01), Gill et al.
paten
Economidis Nikolaos
Gibson Brian
Penna David E.
Goodman Edward W.
Koninklijke Philips Electronics N. V.
Wu Jingge
LandOfFree
Pixel color value encoding and decoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pixel color value encoding and decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pixel color value encoding and decoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102715