Method for run-length encoding of a bitmap data stream

• US 20060140496A1
• Filed: 05/06/2004
• Published: 06/29/2006
• Est. Priority Date: 07/01/2003
• Status: Active Grant

• Current Assignee: InterDigital CE Patent Holdings SAS (InterDigital, Inc.)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Kochale, Axel, Gandolph, Dirk, Peters, Hartmut, Ostermann, Ralf, Horentrup, Jobst
• Granted Patent: US 7,657,109 B2
• Time in Patent Office: Days
• US Class Current: 382/245
• CPC Class Codes: H04N 1/64 Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor H04N19/00 takes precedence
• CPC Class Codes: H04N 19/93 Run-length coding
• CPC Class Codes: H04N 21/4884 for displaying subtitles

Abstract

Subtitling aims at the presentation of text information and graphical data, encoded as pixel bitmaps. The size of subtitle bitmaps may exceed video frame dimensions, so that only portions are displayed at a time. The bitmaps are a separate layer lying above the video, e.g. for synchronized video subtitles, animations and navigation menus, and therefore contain many transparent pixels. An advanced adaptation for bitmap encoding for HDTV, e.g. 1920×1280 pixels per frame as defined for the Blu-ray Disc Prerecorded format, providing optimized compression results for such subtitling bitmaps, is achieved by a four-stage run length encoding. Shorter or longer sequences of pixels of a preferred color, e.g. transparent, are encoded using the second or third shortest code words, while single pixels of different color are encoded using the shortest code words, and sequences of pixels of equal color use the third or fourth shortest code words.

Claims

1. A method for run-length encoding of a data stream, the data stream comprising bitmap formatted subtitle or menu data for video presentation on a display, wherein the subtitle or menu data include graphics or text or both, comprising the steps of

defining a preferred color;

defining a range of run-lengths;

encoding pixels of the preferred color to first code words with two or three bytes, wherein said first code words comprise a run-length value, and wherein the run-length value comprised in first code words having three bytes exceeds said defined range and may exceed the width of the display;

encoding pixels of another than the preferred color to second code words with one, three or four bytes, wherein the second code words comprise a color value, and wherein second code words having three or four bytes comprise a run-length value, and wherein the run-length value comprised in second code words having four bytes exceeds said defined range and may exceed the width of the display.

2. Method according to claim 1, wherein said color values and the preferred color are mapped with a look-up table to display colors.

3. Method according to claim 1, wherein the shortest redundant code word is used for line synchronization.

12. Disc containing data encoded according to claim 1.

4. Method for run-length decoding of an encoded data stream for a video presentation on a display, comprising the steps of

determining the first byte of a code word;

if said first byte has not a defined first value, decoding said first byte to a single pixel having individual color defined by the value of said first byte, the color being other than a defined first color;

if said first byte has the defined first value, determining the first and second bit of the following byte being the second byte;

if the first and second bit of the second byte have a first value, decoding the remaining bits of the second byte to a sequence of pixels of the defined first color, wherein said remaining bits of the second byte define the sequence length;

if the first and second bit of the second byte have a second value, decoding said remaining bits of the second byte together with the following third byte to a sequence of pixels of the defined first color, wherein said remaining bits of the second byte and said third byte define the sequence length, and wherein said sequence length may exceed the display width;

if the first and second bit of the second byte have a third value, decoding said remaining bits of the second byte together with the third byte to a sequence of pixels, wherein said remaining bits of the second byte define the sequence length and the third byte defines the pixels color; and

if the first and second bit of the second byte have a fourth value, decoding said remaining bits of the second byte together with the third and a following fourth byte, wherein said remaining bits of the second byte and the third byte define the sequence length and the fourth byte defines the pixel color, and wherein said sequence length may exceed the display width.

5. Method according to claim 4, wherein said defining of a pixel color from the first, third or fourth byte and from said first value comprises using a look-up table.

6. Method according to claim 4, wherein the encoded data stream for a video presentation is a separate layer overlaying other video data on the display, further comprising the step of selecting a portion of said separate layer for displaying.

7. An apparatus for run-length encoding of a data stream comprising bitmap formatted subtitle or menu data for a visual presentation on a display, wherein the subtitle or menu data include graphics or text or both, comprising

means for defining a first color;

means for defining a range of run-lengths;

means for encoding pixels of the first color to first code words with two or three bytes, wherein said first code words comprise a run-length value, and wherein the run-length value comprised in first code words having three bytes exceeds said defined range and may exceed the width of the display;

means for encoding pixels of another than the first color to second code words with one, three or four bytes, wherein the second code words comprise a color value, and wherein second code words having three or four bytes comprise a run-length value, and wherein the run-length value comprised in second code words having four bytes exceeds said defined range and may exceed the width of the display.

10. Apparatus according to claim 7, further comprising look-up table means for mapping between said color values, including said defined first color, and display colors.

11. Apparatus according to claim 7, wherein said encoded data stream is distributed to multiple transport packets.

8. An apparatus for run-length decoding of an encoded data stream containing compressed bitmap formatted subtitle or menu data for video application, comprising

means for determining code word length, wherein the first byte of a code word is evaluated, and wherein if said first byte has another than a defined first value then said code word length is determined to be one byte, and otherwise the first and second bit of the following, second byte are evaluated, and depending on said first and second bit the code word length is determined to be two, three or four bytes respectively;

means for decoding code words determined to be one byte long to single pixels having a color defined by said one byte, the color being different from a defined first color;

means for decoding code words determined to be two bytes long to sequences of pixels of the defined first color, wherein the sequence length is defined by the remaining bits of the second byte of the code word;

means for decoding code words determined to be three bytes long either to sequences of pixels of the defined first color, wherein the sequence length may exceed the width of the video display and is defined by the third byte and the remaining bits of the second byte, or to sequences of pixels of equal color other than the defined first color, wherein the sequence length is defined by the remaining bits of the second byte; and

means for decoding code words determined to be four bytes long to sequences of pixels of equal color other than the defined first color, wherein the sequence length may exceed the width of the video display.

9. Apparatus according to the claim 8, wherein the means for decoding code words having two bytes that include a sequence length of zero as a sync code word, further comprising means for decoding said sync code word to an end-of-line indication.