(57)【特許請求の範囲】
【請求項１】
データがシンボルＳと称される変換テーブルの一連のアドレスからなるポイントモードの画像（ビットマップデータ）のコーディングに対して用いられるグラフィックデータの圧縮方法であって、
−エンコードの間に徐々に充填される辞書に種々のシンボルを記憶し、
−辞書のアドレスに基づいてシンボルをコーディングし、
−辞書のアドレスの可変バイナリー解像度コーディングがシンボルをコーディングするために用いられる各段階を含み、更に
−同一の連続するシンボルの各範囲に対してシンボルＳに関連する同一のシンボルの数に対応する数Ｌを与えるようシンボルをランレングス・コーディングする段階と、
−Ｌの値の関数としてＬの可変バイナリー解像度コーディングをなす段階とを更に含み、
ビットマップデータの圧縮は：
−ランレングスフィールドの寸法を決定する第一のフィールドと、シンボルフィールドの寸法を決定する第二のフィールドとからなる可変寸法コードフィールドと、
−Ｌをコーディングするバイナリー解像度に対応する寸法の、Ｌのコーディングのためのランレングスフィールドと、
−Ｓをコーディングするバイナリー解像度に対応する寸法の、Ｓのコーディングのためのシンボルフィールドとを含む、
コード化されたデータストリームを発生し、
−Ｌのコーディングに対するバイナリー解像度は、Ｌのコーディングに対するビットの前に、この値Ｌがコード化されるビットの数の関数である数のゼロを送ることにより決定され、
−辞書のアドレスに基づくシンボルをコーディングするためのバイナリー解像度の増加したバイナリー解像度への変更は、アドレスのコーディングに対するビットの前に、Ｌのコーティングに対して用いられる連続するゼロの最大数より大きな値を有する所定の数のゼロを送ることにより決定される、
ことを特徴とする方法。
【請求項２】
グラフィックデータはＯＳＤデータであり、画像はパレット化された画像であることを特徴とする請求項１記載の方法。
【請求項３】
データがシンボルＳと称される変換テーブルの一連のアドレスからなるポイントモードの画像（ビットマップデータ）のコーディングに対して用いられるグラフィックデータの圧縮装置であって、
−エンコードの間に徐々に充填される辞書に種々のシンボルを記憶する手段と、
−辞書のアドレスに基づいてシンボルをコーディングする手段と、
−シンボルをコーディングするために用いられる辞書のアドレスを可変バイナリー解像度コーディングする手段とを含み、更に
−同一の連続するシンボルの各範囲に対してシンボルＳに関連する同一のシンボルの数に対応する数Ｌを与えるようシンボルをコーディングするランレングス・コーディングするランレングス・コーダーと、
−Ｌの値の関数としてＬをコーディングする可変バイナリー解像度コーダーとを更に含み、
ビットマップデータの圧縮は：
−ランレングスフィールドの寸法を決定する第一のフィールドと、シンボルフィールドの寸法を決定する第二のフィールドとからなる可変寸法コードフィールドと、
−Ｌをコーディングするバイナリー解像度に対応する寸法の、Ｌのコーディングのためのランレングスフィールドと、
−Ｓをコーディングするバイナリー解像度に対応する寸法の、Ｓのコーディングのためのシンボルフィールドとを含む、
コード化されたデータストリームを発生し、
−Ｌのコーディングに対するバイナリー解像度は、Ｌのコーディングに対するビットの前に、この値Ｌがコード化されるビットの数の関数である数のゼロを送ることにより決定され、
−辞書のアドレスに基づくシンボルをコーディングするためのバイナリー解像度の増加したバイナリー解像度への変更は、アドレスのコーディングに対するビットの前に、Ｌのコーティングに対して用いられる連続するゼロの最大数より大きな値を有する所定の数のゼロを送ることにより決定される、
ことを特徴とする装置。
【請求項４】
辞書のメモリ記憶用のメモリと、圧縮されたデータストリームを受けてＬ及びＳのバイナリー解像度を検出し、Ｌ及びＳのコード化された値を抽出するフィールド識別回路と、シンボルＳ抽出回路と、Ｌのコード化された値をデコーディングするランレングスデコーディング回路と、ストリームの値ＳをＬ回送り出すためにシンボルＳに対するデコードされたランレングス値Ｌ及びシンボルＳのデコードされた値を受けるシンボルのシーケンスを発生する回路とからなり、抽出回路はＳのコード化された値をアドレスとして送り、アドレスの内容を取り出すためのメモリにリンクされていることを特徴とする、請求項１記載の方法により圧縮されたグラフィックデータを復元する装置。
【請求項５】
請求項３記載のグラフィックデータ圧縮装置と、請求項４記載のグラフィックデータ復元装置とを含むことを特徴とするデジタルビデオデコーダ。
【請求項６】
請求項４記載のグラフィックデータ復元装置を含み、請求項１記載の方法により圧縮されたビットマップデータを記憶するＲＡＭメモリを含むことを特徴とするデジタルビデオデコーダ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はグラフィックデータのリアルタイムコーディングデコーディング及びリアルタイムグラフィックコーダー／デコーダー（コーデック；ｃｏｄｅｃ）に関する。
【０００２】
【従来の技術】
それはオンスクリーン表示又はＯＳＤという表現により良く知られているスクリーン用の表示データのコーティング／デコーディングによりよく適用される。この型の表示器はビデオデコーダ、ＴＶセット、ビデオレコーダ及び一般的にビデオ装置の全ての型に用いられる。
【０００３】
ＯＳＤ表示器は機器を設定するためのメニュー、プログラム用の電子ガイドメニュー（プログラマブルガイド）、及びＴＶ局を識別するために用いられるのみならず、天気図の背景の可視的表示のようなより複雑な応用にも用いられる。これはビデオ画像とオーバーレイ又はスーパーインポジションのこれらのデータの可視的表示のみを含む。
【０００４】
このＯＳＤ表示に関するデータはレジデントデータであり、すなわち表示器のこの型を用いるビデオ装置のメモリに恒久的に保持されたデータ又はそれはハードウエアが製造され、又は情報がダウンロードされたときにインストールされた情報の形を取る。これらのデータはまたビデオデータストリームと距離をおいて送信される。これは例えばデジタルデコーダを含む。動画エキスパートグループに対する頭字語であるＭＰＥＧ型のビデオデジタルデコーダの場合にはこれはこのＭＰＥＧ規格によりコード化されたビデオデータストリーム（ビデオビットストリーム）を処理し、ビデオ画像は圧縮された形で受信され、動きの推定のためによりビデオシーケンス及び離散的コサイン変換の空間的及び時間的な冗長性を特に活用する。ＯＳＤデータはこの処理に関係せず、圧縮されない形でＭＰＥＧデータストリームに含まれ、リアルタイムで使用されるためにこの形でデコーダーに記憶される。
【０００５】
ＯＳＤ表示器に用いられるアプリケーションはより一層複雑になり、より大量の記憶されるデータが必要とされる。コストのためにＯＳＤデータにアロケートされたランダムアクセスメモリＲＡＭは故に、そのようなアプリケーションを制限し、又は発生された画像又はパターンの解像度を減少させ、又はメニュー及びアプリケーションの多様性を制限する。
【０００６】
【発明が解決しようとする課題】
本発明の目的は上記の欠点を克服することにある。
【０００７】
【課題を解決するための手段】
上記の目的は、データはシンボルＳと称される変換テーブルの一連のアドレスからなるポイントモード（ビットマップデータ）でコーディング画像に対して用いられるグラフィックデータの圧縮方法であって、
−  辞書に種々のシンボルを記憶し、
−  辞書のアドレスに基づいてシンボルをコーディングし、
−  辞書のアドレスの可変バイナリー解像度コーディングはシンボルをコーディングするために提供される
各段階からなることを特徴とする方法により解決される。
【０００８】
本発明の一特徴によれば、
−  同一の連続するシンボルの各範囲に対してシンボルＳに関連する同一のシンボルの数に対応する数Ｌを与えるためにシンボルのランレングスをコーディングし、
−  Ｌの値の関数としてＬの可変バイナリー解像度コーディングをなす
各段階を更に含むことを特徴とする。
【０００９】
本発明はまた、データはデータストリームで送られ、シンボルＳと称される変換テーブルの一連のアドレスからなるポイントモード（ビットマップデータ）でコーディング画像に対して用いられるグラフィックデータの圧縮装置であって、各ランレングスに対してシンボルＳに関連する数Ｌを提供するためにデータストリームを受けるランレングスコーダーと、Ｌをコーディングするクラスによる可変バイナリー解像度コーダーと、種々のシンボルのメモリ記憶用の辞書とＳをコーディングするために辞書のアドレスの可変バイナリー解像度コーダーとからなる可変バイナリー解像度シンボルコーダーとからなることを特徴とする圧縮装置に関する。
【００１０】
本発明はまた、辞書のメモリ記憶用のメモリと、Ｌ及びＳのバイナリー解像度を検出するために圧縮されたデータストリームを受け、Ｌ及びＳのコード化された値を抽出するフィールド識別回路と、シンボルＳ抽出回路と、Ｌのコード化された値をデコーディングするランレングスデコーディング回路と、ストリームの値ＳをＬ回送り出すためにシンボルＳに対してデコードされたランレングス値Ｌ及びシンボルＳのデコードされた値を受けるシンボルのシーケンスを発生する回路とからなり、抽出回路はＳのコード化された値をアドレスとして送り、アドレスの内容を受けるメモリにリンクされていることを特徴とするグラフィックデータを復元（デコンプレス）する装置に関する。
【００１１】
圧縮される値は一般にビットマップ型のデータに関する。これらは有効画素の値のアドレスであり、即ちスクリーンに可視的に表示された画素の輝度（ルミナンス）及び／又はクロミナンス値であり、パレットと称されるカラーのパレットに記憶される。故に画像はパレット化されたと称される。
故に圧縮の２つの本質的な段階は以下の通りである：
−  ランレングスと称される同一のシンボルのシーケンス毎の長さの可変解像度コーディングをなす。長さＬの同一の連続するシンボルの各ランレングスに対して、検出された各繰り返しシーケンスの長さＬはランレングスＬの値に依存するその親のクラスの関数として可変である解像度でコード化される。クラスによるコーディングは親のクラスＬの関数として可変である最適な（最小の）コードを帰属させることを可能にする。これらのクラスはグラフィック画像の大きなポピュレーションに基づき統計的に決定される。
【００１２】
−  適応辞書で生ずる順序の関数としてシンボルそれ自体の可変バイナリー解像度コーディングをなす。これは遭遇したカラーの数で増加する可変バイナリーコーディングに対応する辞書の実際のアドレスに基づきシンボルに遭遇し、コーディングするときに辞書に種々のシンボルを記憶することにより達成される。有効アドレスはアドレスワードに対してゼロでのアクティベートされない高次のビットを無視することであると理解される。
【００１３】
本発明の一特徴はレジデントデータが発生するときにこのＯＳＤ情報を記憶する前又は圧縮された情報を記憶する前にそれを圧縮することである。用いられる圧縮アルゴリズムは簡単であり、ＯＳＤ表示器に対して用いられるグラフィックコーディングの性質により高い圧縮比を与える一方でリアルタイム応用を許容する。これは一方で、そのようなコーディング中に用いられるカラーの数がビデオレコーダに送られる又はこのデコーダに記憶されるデータの量を減少するためにそれ自体で制限されるためである。更にまた、ＯＳＤ表示器は一般に均一なカラー及び反復パターンの領域を示す。
【００１４】
故に、このアルゴリズムはコーディングの２つの型の組合せで実施される：ランレングスコーディング（ＲＬＣ）及び可変バイナリー解像度コーディングであり、両者はランレングスコーディング及びシンボル、即ちアドレスのコーディング用である。本発明の性質により、デコーダ、テレビジョン受信機、ビデオレコーダ、等々のランダムアクセスメモリの要求は減少される。ハードウエアの製造のコストは減少され、又は与えられたコストであり、オンスクリーン表示器（ＯＳＤ）に関するアプリケーションはより高い性能であり、及び／又は表示器はよりよい品質である。
【００１５】
【発明の実施の形態】
本発明の特徴及び利点は以下に図面を参照して、例により与えられた説明からよりよく理解される。
ＯＳＤ表示器の解像力、メモリー記憶、対応するデータの使用に対して、今日多くの解決策が存在する。一般的に、ＯＳＤデータはビットマップの形で記憶され、画像が画素により表示器（画像）を記述するデータ（輝度、クロミナンス）に基づく、即ちポイントモードでコード化される広く用いられる表現の意味である。カラーのパレットのメモリ又はレジスタはシンボル及びグラフィックを発生するために必要な種々のカラーを含む。これらのカラーのベクトル型のアドレッシングはこれらのコーディングのみによるものでなく、パレットのレジスタのそれらのアドレスによりこれらのカラーを決定することにより実行される。パレットのこのレジスタはまたカラー変換テーブル又はカラールックアップテーブル（ＣＬＵＴ）と称される。
【００１６】
ＯＳＤ情報は画像上の領域又はエリアに一般的に分配され、エリアは座標により決定される。各領域に対して、この領域に属する画素の座標に対して必要なカラー全てはこの領域に対するカラーのパレットに対応する。各領域に対して、ビットマップはこれらの画素に対する輝度及びクロミナンスを含む変換テーブルのアドレス、即ちＹ，Ｕ，Ｖを各領域の画素に割り当てる。
【００１７】
従来技術によるこのデコーダのランダムアクセスメモリＲＡＭでＭＰＥＧデコーダにより受容されたデータの記憶の一例が以下に記載される。ＲＡＭメモリの第一の部分は圧縮されたＭＰＥＧデータのストリームを記憶し、第二の部分はＯＳＤ表示器（ＯＳＤデータ＿に特有の表示を記憶し、第三の部分は例えばＭＰＥＧ規格による画像を再順序づけするために必要な圧縮された画像のビデオデータを記憶する。
【００１８】
より詳細にはＯＳＤデータのメモリ記憶は座標に対応する第一の領域と、カラーのパレットに対応する第二の領域と、ビットマップデータに対応する第三の領域とにそれ自体組織化される。決定されたＯＳＤ領域のデータに割り当てられ得たメモリの第一の領域には故に、この領域がスクリーン上に表示される場所を決定することを可能にする座標を記憶する。第二の領域にはこの領域を表すために必要なカラーのパレット又はＣＬＵＴ変換テーブルを記憶し、第三の領域には各画素に対して輝度及びクロミナンスにより画素のコーディングに対応する変換テーブル（ＣＬＵＴ）でアドレスが各画素に対して記憶される。この第三の領域のこれらのデータはビットマップデータと称される。
【００１９】
図１はコーダー１が例えばＭＰＥＧデコーダーのメモリのようなＲＡＭメモリに記憶される前にＯＳＤデータのコーディング及び圧縮の方法を実施することを示す。問題のＯＳＤデータは実際にはビットマップデータである。上記のようにシンボルＳと称される一連のアドレスを表すこれらのビットマップデータはこの図で破線で表されるコーダー１の入力として受容され、これは回路２から５で共に群をなす。これらのデータは固定されたバイナリー解像度ランレングスコーダー２に送られる。このコーダーは入力として受容された一連の同一のシンボルＳの数Ｌに対応して各領域に対して第一の出力でＬ情報を提供し、第二の出力でＳ情報を提供する。値Ｌを提供する出力はその親のクラスによりこの値Ｌをコーディングするためにクラス３により可変バイナリー解像度の入力に、値Ｓを提供する出力は可変バイナリー解像度シンボルコーダー４の入力に送られる。コーダー３、４の出力はＬ及びＳのコード化された値
【００２０】
【数１】
0004406481.tif 000002
【００２１】
をそれぞれ提供し、それらはマルチプレクサ５の入力にリンクされ、その出力はコーダー１の出力である。
ランレングスコーダー２はランレングスコーディング又はＲＬＣというタイトルにより良く知られている範囲でコーディングの方法に用いられる。ランレングスコーディングの原理はｋ番目のシンボルＳk の連続する繰り返しＬk を計算し、対Ｖk ＝（Ｌk ，Ｓk ）によりこのシンボルの繰り返しのシーケンスを置き換えることからなる。Ｌk は同一のシンボルＳk の繰り返しの数に対応する。この対の各値は以下に説明する特殊なコーディングを用いて別々にコード化される。
【００２２】
値Ｌのコーディングはクラス３により可変バイナリー解像度コーダーによりその親のクラスの関数として実行される。このコーダーにより用いられるコーディング原理は図２に示される。
ランレングスコーダー２から入来するコード化された情報Ｌはクラス決定回路６と可変解像度コーディング回路７とに同時に送られ、後者はコーダー３の出力に送られるＬ、
【００２３】
【数２】
0004406481.tif 000003
【００２４】
のコード化された値を提供する。
クラス検出回路はこの例ではクラスのそれぞれに特徴的であり、並列にコーダー３の入力に送られる情報、即ち値Ｌ（バイナリーでコード化された）を受容する５つの比較器８からなる。各比較器はこの比較器に特有のクラス（又は間隔）の制限以下、制限以上又は制限内でそれぞれ情報の項目に対応する３つの出力を有する。比較器の出力は比較器から由来する情報全てを一緒にグループ化する論理回路９に連結される。それは５つの出力を有し、これらはまたクラス検出回路６の出力であり、各クラスに対する一つの出力は可変バイナリー解像度コーディング回路７の５つの入力に連結される。このコーディング回路７は入力として値Ｌ（バイナリーコード化された）に対応する情報を受けるトランスコーダー１０と、この値が属するクラスに示される５つの入力とからなる。トランスコーダーの５つの出力はマルチプレクサ１１の５つの入力に連結され、この出力はコーダー３の出力である。この出力は入力データストリームＬに対応するコード化されたデータストリーム
【００２５】
【数３】
0004406481.tif 000004
【００２６】
を供給する。
回路の機能を詳細に説明する前に、クラスによるコーディングに応用された可変バイナリー解像度コーディングの原理を説明する。
値Ｌが変化しうる領域は２2m+2−１がコーディングＬに対する最大の可能な値（シンボルの繰り返しの最大数）に対応するように値ｍに基づいて予め決定される。この領域は値のｍ＋１区間に分割され、各区間は値２2nと２2n+2−１により囲まれ、ｎはゼロからｍまで変化し、一の区間は一のクラスに対応する。クラスによる可変バイナリー解像度コーディングの原理は各クラスに異なる解像度を属させることからなる。このバイナリー解像度はコーティングＬに対するビット数に対応し、故に値Ｌが属するクラスに依存する。実際にバイナリーワードＬを考慮に入れると”有効”コーディングビット、即ち、これらのビットの送信をしないことが値ゼロに対応することが知られているゼロでより高いオーダーのビットを無視することのみが問題となる。コーディングはＬの低い値（ｎ＝０、１）に対して低いバイナリ解像度であり、より高い値（ｎ＝２、３、４）に対してより高いバイナリ解像度である。
【００２７】
種々のクラスが識別コードと称される特定のコードにより識別される（識別ビットを考慮に入れないＬのコーディングに対するバイナリワードはシンボル＜Ｌ＞により表される）。故にコーディングワード＜Ｌ＞の前に送られたいくつかのゼロであるこのコードはすぐに続くランレングスＬの値がコード化されるビットの数を識別することを可能にする。シンボル
【００２８】
【数４】
0004406481.tif 000005
【００２９】
で示される、Ｌのコーディングに対するワードは故に２つの部分からなり：第一の部分はゼロからなり、値Ｌが属するクラスを識別することを可能にし、第二の部分＜Ｌ＞はこの値を２をベースにして〔すなわち二進法で〕コーディングし、このコーディングに対してビットの最小の数が必要とされる。ｍの値が４に等しく、Ｌが１０２３の最大値を有することが可能な例を以下の表に示す。
【００３０】
【表１】
0004406481.tif 000006
【００３１】
種々のコーディングクラスＲｎ＝２2n、２2n+2−１は１−３，４−１５，１６−６３，６４−２５５，２５６−１０２３である。“クラスによるコーディング”の列は、シンボルＳの繰り返しの数を表すＬの値をコーディングするために用いられるバイナリワード＜Ｌ＞に関係する。“識別コード”の列はクラスを識別するビットを示す。“解像度”の列はＬのコーディングに対して必要なビットの数を示す（これは完全なコーディングワード
【００３２】
【数５】
0004406481.tif 000007
【００３３】
が識別コード及びコーディングワード＜Ｌ＞を共にグループ化することを示す）。
例えば、値Ｌ＝５が６ビットバイナリーワード（００．０１０１）によりコード化され、一方で値４９は１０ビットバイナリーワード（００００．１１０００１）によりコード化される。ポイントは単に２つの異なるコードを並置して示すことであり、識別コードは＜Ｌ＞コーディングに続く。２つのゼロで始まる＜Ｌ＞コーディングワードに対応するＬの値が存在しない（Ｌは少なくとも１に等しい）故に、部分のそれぞれの識別、又はより正確には識別コードの検出はデコーディングに関して問題を有さない。
【００３４】
図２に示された装置の機能を再び参照する。
それぞれ５つのクラスに対応する５つの比較器８はその入力で並列にＬ情報を受ける。各比較器は３つの出力を有し、入力として受容された値がこの比較器に対するクラス属性に対応する期間より小さいか、この期間内にあるか、又はそれより大きいかのいずれかにより第一、第二、又は第三の出力が作動される。この情報は論理回路９へ送られ、、これはＬ情報が属するクラスに対応する出力を作動させる（これは明らかに一実施例であり、各比較器の第二の出力は回路６の出力として直接出力されることもまた可能である）。クラス検出回路は次にその５つの出力の一つで可変解像度コーディング回路７に値Ｌが属するクラスに対応する情報を送る。この情報はコーディング回路７の入力として受容された各Ｌ値に対して回路１０により受容される。トランスコーディング回路１０により実行されたトランスコーディングはまずコーダー３により受容されたＬコーディングバイナリーワードの打ち切り（トランケーション）をなすことにより＜Ｌ＞を得ることからなり、１０ビットの最初から値１から１０２３までをコーディングすることからなる。この打ち切りは対応するクラス情報がそれぞれ第一、第二、第三、第四、又は第五のクラスであるかどうかによりこのコーディングワードの２、４、６、８、又は１０のより低い字数のビットを保つことを可能にする。次にそれは斯くして得られたバイナリーワード、即ち対応するクラス情報が２、６、１０、１４、又は１８ビットにわたり
【００３５】
【数６】
0004406481.tif 000008
【００３６】
コーディングワードを与えるそれぞれ第一、第二、第三、第四、又は第五のクラスであるかどうかによりゼロ値の０、２、４、６、又は８ビットの前に識別コードを加えることによる。トランスコードされたバイナリーワードはマルチプレクサ１１の入力の一つに送られ、これは入力に現れる情報Ｌのコーディング
【００３７】
【数７】
0004406481.tif 000009
【００３８】
をその出力に供給する。コーダー３は斯くして、出力として入力として受容されたＬの値に対応する一連の
【００３９】
【数８】
0004406481.tif 000010
【００４０】
コーディングワードを出力する。
シンボルＳの値のコーディングはシンボルコーダー４によりなされる。値Ｓをコーディングする原理は図３に詳細に示される。
コーダー４に入力は辞書１２の発生回路の入力に連結され、シンボルＳのバイナリー値を受ける。回路の７つの出力は出力がシンボルコーダー４の出力であるトランスコーディング回路１３の７つの入力と連結される。コーダー４の入力は比較器１４の第一の入力及び辞書１５と称されるランダムアクセスメモリの第一の入力とに連結される。比較器の出力は８ビットカウンタ１６のクロック入力に連結される。このカウンタの出力はランダムアクセスメモリ１５のアドレス入力に連結される。それはまた論理回路１８の第一の入力とメモリ回路１の入力とに連結され、その出力は論理回路１８の第二の入力に連結される。この論理回路は７つの出力を有し、それらは辞書１の発生回路の出力である。それらはトランスコーディング回路１３の７つの入力に連結され、それはその出力でシンボルＳ即ち
【００４１】
【数９】
0004406481.tif 000011
【００４２】
のコーディングを提供する。
コーディング過程は辞書のアドレスのアロケーションに本質的には基づく。故にシンボルが辞書１２の発生回路により受容されるときはいつでも、そのバイナリー値は比較器１４により辞書１２のメモリに記憶された全ての値と比較される。これをなすために、図示されない管理回路はカウンターを制御し、それは新たなシンボルの各到着で辞書１５に対する入力としてアドレスをスクロールし、これらのアドレスに対応するメモリ記憶された各値は受容されたシンボルのバイナリー値と比較される。比較の結果が否定的であるときに、８ビットカウンターはメモリに記憶された最後のシンボルのアドレスとの比較によりインクリメントされ、新たなシンボルはこの新たなアドレスでメモリに記憶され辞書に加えられる。
【００４３】
回路１７は辞書のシンボルのメモリ記憶用に用いられる最大アドレスと、特にこのアドレスがコード化される“意味のある”ビットの数ｔ（即ちｔの最小数は２t-1が最大アドレスのバイナリー値以上であり、ｔの最小値は２に等しくとられる）を記憶する。それはｔの値を回路１８に送り、それにより後者はより低いオーダーのいくつかのビットのみを送信し、より低いオーダーのそれらのビットはメモリに記憶された最後のシンボルのアドレスをコーディングする意味のあるビットの数ｔに対応する。この論理回路の一出力はｔの各値に割り当てられ、ｔは辞書内の２５６の値の可能なメモリ記憶に対して２と８の間にある。出力はそれに続くトランスコーディングをなすコーディング回路１３に連結される。第一の入力で受容され、故に２ビットにわたるバイナリー情報はそれが出力としてあるように出力される。バイナリー情報が３ビットにわたる辞書のアドレスのコーディングを示す第二の入力にスイッチオーバーされるときに、値ゼロの一連の１０ビットが、３ビットにわたり受容されたこの最後のバイナリワードのコーディングに先行する。バイナリー情報が一の入力から他へスイッチオーバーされるときはいつも、値ゼロの一連の１０ビットがこの入力で受容された第一のバイナリーワードの前に加えられる。
【００４４】
辞書は新たなアドレスによりアドレス（シンボル）をコードする。それは意味のあるシンボルのみを含み、即ち、アドレスはＯＳＤコーディング用のカラーのパレットに用いられたカラーに対応する。例えば、シンボルが８ビットにわたりコード化された領域は２５６カラーのパレットを有する。２５６の内から６４カラーのみがこの領域で用いられた場合には辞書は６４シンボルのみを含む。
【００４５】
各シンボルのコーディングは故に辞書のそれ自体のアドレスに基づいてなされる。それは可変バイナリー解像度コーディングを用い、この解像度に関する情報はゼロの付加により供給される。前の例では、６４のカラーが存在し、コード化されたシンボルは８ビットの代わりに６ビットのバイナリー解像度を有する。この操作のみにより、２５％の節約が達成された。これは多くのＯＳＤ領域が用いるのは２５６カラーより少ない故にこのコーディングが効率的になる。
【００４６】
動作の例を以下に示す。
ビットマップデータからシンボルのシーケンシャルリーディングのサイクルの開始で、ＯＳＤ領域は４つの異なるカラーより少ないカラーを有すると仮定され、コード化された第一のシンボルは故に２ビットの解像度を有する。新たな、まだコード化されないシンボルが現れる度毎に、即ち、シンボルが辞書に存在していない場合にそれは辞書のメモリに記憶され、アドレスはインクリメントされる。第一のシンボルはアドレス０に記憶され、そのコードは故にこの第一のシンボルの値によらずに値００である。新たなシンボルが読み込まれたときに、それはアドレス０１に記憶され、そのコードは従って０１である。第四の新たなシンボルが同様にして取り扱われそのコードは１１である。読み込まれた他の値が辞書のメモリに記憶されたものである場合に、そのコードは００から１１の間に存在するアドレスである。故に受容されたシンボルがコード化されるバイナリ解像度が８ビットの代わりに２ビットである。辞書のメモリに記憶された４つと異なる新たなシンボルが受容されるまでこれは続く。故に解像度はインクリメントされ、他のシンボル全てに対して３ビットに変わる。読み込まれた第六番目のシンボルがアドレス０１で辞書に既に存在する場合にはそのコードはその時に００１である。本発明の方法は辞書が１２８カラー以上を含むまで続く。この段階から、全てのシンボルは８ビットの解像度を有する。
【００４７】
曖昧さなしにシンボルのデコーディングを実施するために、特殊なコードが辞書のアドレスの解像度がインクリメントされる度に毎回発生される。最悪の場合には、このコードは６回発生される。コードは１０個のゼロのシーケンスである。これは９の連続したゼロ（識別コードのための８つを含む）のみが２５５以上の値に対してランレングスＬによりコーディングする必要があるからである。
【００４８】
シンボルＳをコーディングするためのアルゴリズムは図４に示される。段階２０は種々のパラメータを初期化することからなる。辞書Ｄは最初からメモリに記憶されたデータなしに形成される。
注意書きは以下の通りである。
シンボルＳは  ｃ又はｚ．ｃの形でコード化される。
【００４９】
ｚは１０のゼロに対応する識別コードである。
ｃはシンボルがメモリに記憶されるバイナリーアドレスに対応する（可変ビット数）。
ｔはｃをコーディングするために用いられるビット数である。
ｉはコーダーの入力として受容されたシンボルがメモリに記憶され、又はリカバーされた辞書Ｄのアドレスのインデックスである。
【００５０】
ｎは辞書のメモリに記憶されたシンボル（又はカラー）の数である。
初期化で、値ｔは強制的に２にされ、インデックスｉはアドレス１に設定される（バイナリー形式の０１）。
第一のシンボルαが受容されたときに、その値は辞書のアドレス１でメモリに記憶される。
【００５１】
Ｄ（１）＝α、ｎ＝１
新たなシンボルは次の段階２１で読み込まれる。
段階２２はシンボルが辞書Ｄに既に存在するか否かを確認する。イエスの場合には段階２３がメモリに記憶されたワードがこのシンボルに対応するための辞書でアドレスｉの値に対する検索をランする。次の段階２４はｉのバイナリ値でシンボルＳをコードする。
【００５２】
ｃ＝アドレスｉのバイナリー形式
シンボルが辞書に現れない場合には段階２５が段階２２の後でランする。この段階は値ｎ及びアドレスｉ＝ｎでメモリに記憶された新たなシンボルをインクリメントする。次の段階２６は新たな値ｎは付加的なコーディングビットを必要とするか否かを確認する。
【００５３】
ｎが２t より大きい場合には、辞書に入来された最後のシンボルのアドレスにわたるビットの数であるｔはコード化され、段階２７が実行される。値ｔは新たなアドレスが付加的なビットにわたりコード化される故にインクリメントされる。ｃのバイナリー解像度は結果としてインクリメントされ、１０のゼロの識別コードｚはこの値ｃに先立つ。以下の動作は段階２７で実施される。
【００５４】
１０個のゼロを発生する
ｔ＝ｔ＋１
ｃのバイナリー解像度＝ｔ
段階２８は段階２７に続き、インデックスｉは値ｎを与えられシンボルαはアドレスｉで辞書のメモリに記憶される。
【００５５】
ｉ＝ｎ
Ｄ（ｉ）＝α
段階２６で、ｎが２t 以下である場合には、以下の段階は直接段階２８となる。  段階２８に続く段階は段階２４であり、これは段階２７が実行された場合に１０のゼロにより先行されるアドレスｉのバイナリー値によりシンボルの値をコードする。
【００５６】
図５は図でコード化され、符号３０で示されたビットマップデータストリームに基づいたコーディングの一例を示す。Ｌはシンボルの繰り返しの数に対応し、Ｓはシンボルの値に対応する。
【００５７】
【数１０】
0004406481.tif 000012
【００５８】
はシンボルＳをコーディングするためのバイナリーワードである。ビットマップデータストリーム３０のコーディングの段階では、辞書ＤはシンボルＳの値で充填され、メモリ記憶アドレスはシンボルをコーディングするために用いられる。コード化される値３２は辞書に記憶される先行するものと異なる第五の値である。データストリームのこの値に基づいて、バイナリーコーディングワード
【００５９】
【数１１】
0004406481.tif 000013
【００６０】
は故に少なくとも３ビットのワードである。
【００６１】
【数１２】
0004406481.tif 000014
【００６２】
は値Ｌをコーディングするためのバイナリーワードである。Ｌの値が区間１から３にあるときに、バイナリーコーディングワード
【００６３】
【数１３】
0004406481.tif 000015
【００６４】
は２ビットワードである。Ｌの値が区間４から１５にあるときに、コーディング用のバイナリーワード
【００６５】
【数１４】
0004406481.tif 000016
【００６６】
は６ビットワードであり、第一の２ビットはゼロでコーディングの解像度を示し、ここで４ビットの前にある。
符号３１で示された圧縮されたデータストリームは図の下部に示される。これは各ランレングスに対してバイナリーワード
【００６７】
【数１５】
0004406481.tif 000017
【００６８】
の連続に対応する。Ｓの新たな値がデータストリーム３０に遭遇する度毎に、新たなＬ，Ｓの対がコード化される。値３２でシンボルのコーディング中に、バイナリー解像度はインクリメントされ、コーディングはこのポイントから３ビット上でなされる。従って、バイナリーストリームでは、１０のゼロの連続は対応するＬ，Ｓ対のコーディングの直前に送られる。
【００６９】
デコーディング方法及び回路は以下に説明される。
上記のＯＳＤコーダーの出力で利用可能なコード化されたビットマップデータはビデオコーダーのＲＡＭメモリに記憶され、このメモリはＯＳＤコーダー及び以下に説明するようにこのビデオデコーダーに一体化されたＯＳＤデコーダーによりアクセス可能である。このメモリに記憶された情報はまたカラーのパレット、ビデオデコーダーにより受容されたＯＳＤエリアを決定する座標、ＯＳＤコーダーにより構成され、ＲＡＭに転送された辞書である。
【００７０】
本発明のデコーディング装置３２は図６に示される。
ビデオデコーダのＲＡＭメモリに関するバスはＦＩＦＯメモリ３３及び上記の辞書の容量を有する変換テーブル又はメモリ３５に連結される。ＦＩＦＯメモリの出力でのデータはフィールド識別回路３４に送られる。この回路の第一の出力はランレングスデコーディング回路３７に送られる。第二の出力はシンボル抽出回路３６の第一の入力に連結される。ＲＡＭメモリのバスから由来する情報を受けるメモリ３５は第二のシンボル抽出回路３６に連結される。この後者の回路の出力はシンボル３８のシーケンスを発生する回路の第二の入力に連結される。ランレングスデコーディング回路３７の出力はこの回路の第一の入力に連結され、その出力は破線で示されるデコーダー３２の出力となる。
【００７１】
故に、第一の部分で、ＯＳＤデータをコーディングするコーダーで形成され、変換テーブルの形のＲＡＭのメモリに記憶された辞書からのデータはデコーダーがシンボルを計算するときに、即ちＲＡＭメモリにアクセスを要求することなしにこの情報をこのメモリから直接使用することを許容するためにメモリ３２にＲＡＭメモリバスを介して転送される。
【００７２】
ポイントモードコード化されたデータのストリーム（ビットマップエンコード化されたビットストリーム又はＢＥＢ）又はビデオデコーダのＲＡＭのメモリに記憶されたコード化されたビットマップデータはＦＩＦＯメモリに送られる。規制する役割を有するこのメモリはこのデータストリームをフィールド識別回路３１に送る。この回路はゼロのシーケンスを検出し、コーディングフィールドを識別することを可能とする。
【００７３】
ＦＩＦＯメモリは上記の圧縮プロトコルにより３つの連続する部分からなるデータストリームを提供する。
−  コードフィールド
−  ランレングスフィールド
−  シンボルフィールド
これらのフィールドは可変の大きさを有する。コードフィールドは＜Ｌ＞のバイナリー解像度を示すクラスの識別用のコード（最大で８＋１のゼロ）が続くｃ（Ｓのコーディング）のバイナリー解像度の変化を示すために挿入された１０のゼロのシーケンスに対応する１９ビットの最大の大きさを有する。故にそれはビットｎi の数を決定することを可能にし、その上でＬの値はコード化され、ｎs はその上でシンボルのアドレスがコード化される。
【００７４】
コードフィールドのゼロの数が１０以下の時には例えばｐ個のゼロであるゼロの対応するシーケンスはＬのコーディングにのみ関係し、この数が１０より大きい時には最初の１０個のゼロがｃのバイナリー解像度がインクリメントされることを示し、シーケンスの残りのゼロの数ｐはＬのコーディングに関係する。  ｐの値はランレングスがコード化されるビットの数ｎi を示す。
【００７５】
−  ｐが偶数の場合、ｎi ＝ｐ＋２
−  ｐが奇数の場合、ｎi ＝ｐ
一旦ｎi 及びｎs の値が計算されると、シンボル及びランレングスフィールドは識別可能である。故にこれらのフィールドに対応する値は抽出されうる。
故にフィールド識別回路３４は第一の出力でランレングスデコーディング回路３７にそれらを送るためにランレングスのコーディングに対応するストリームからコード化されたバイナリーワードを抽出し、第二の出力でそれらをシンボル抽出回路３６に送るためにシンボルのコーディングに対応するストリームのコード化されたバイナリーワードを抽出する。ランレングスデコーディング回路はその出力で値Ｌを提供する。シンボル抽出回路はフィールド識別回路３４から受容したアドレスに基づいてメモリ３５のこのアドレスでメモリに記憶されたシンボルＳのバイナリー値を探す。シンボル３８のシーケンスを発生する回路はこれらのＬ及びＳ値を受け、その出力で、Ｌ回繰り返されたＳの各値に対応するデータストリームを与える。
【００７６】
このＯＳＤデコーダにより用いられるデコーディングアルゴリズムは図７に示される。
第一の段階４０はビデオデコーダーのＲＡＭメモリに記憶された辞書をＯＳＤデコーダのメモリ３２に読み込み、転送することからなる。シンボルｃをコーディングするビットｔの数は２に初期化される。次の段階４１はＦＩＦＯメモリにより送られたデータストリームのゼロのシーケンスを検出し、１０より小さい数である限りメモリ内の連続するゼロの数ｎを記憶する。この数が１０に等しいか又はゼロのシーケンスが終了するとすぐに、段階４２がトリガーされこれは２つの場合に識別される。
【００７７】
−  ｎが値１０に到達している場合、次の段階４３はｃをコーディングするために用いられるｔの値をインクリメントし、次に段階４１が続き、最初の１０のゼロを検出した後に残る新たなゼロの数ｎを測定する。
−  ｎが１０より小さい場合には、段階４４はランレングスデコーディングを実施する。これをなすために、１０より小さいゼロの数又は段階４３を通り過ぎてしまった場合には残りのゼロの数、前に呼ばれた数ｐはビットの数を決定するために用いられ、このゼロに続いてＬをデコーディングするために考慮するように、この数が上記のようにｐのパリティの関数である。
【００７８】
ランレングスＬの値をデコーディングした後に、次の段階４５は値ｃを決定するためにランレングスをコーディングするためにビットに続くビットｔの数を読み込む。段階４６はメモリ３２でＳの値であるアドレスｃの内容に対して検索をなす。
図８は本発明によりコード化されたデータストリームをデコーディングする一例を示し、図ではデータストリームは符号４７で示される。
【００７９】
最初に、値ｎs は２に初期化される。コードフィールドは一つのゼロに対応する。従って、ｎs の値はなお２に等しく、ｎi の値は１に等しい（ｐ＝１）。ランレングスフィールドは値１を含み、シンボルフィールドは値００を含む。従って、Ｌの値は１に等しく、Ｓの値はアドレス００の辞書の内容、即ち６である。続くコードフィールドは一のゼロ値を含み、フィールドの長さは故に変化せず、シンボルの値は辞書のアドレスＯ１に見いだされる。１０以上のゼロの連続に遭遇した時にコーディングＬに対するバイナリー解像度は変化する。この例では１３のゼロの連続が現れる。故に、ｎs インクリメントされ、Ｓは３ビットにわたり読み込まれる。ゼロで１０ビットに続く３つのゼロはランレングスフィールドは３ビットの寸法を有することを示す。Ｌは故に３ビット１０１によりコード化され、Ｓはそれに続く３ビット１００によりコード化される。故にアドレス１００で見いだされる値３２は５回繰り返される。
【００８０】
斯くして得られたデコードされたデータストリームは図の下の符号４８の下に示される。それはビデオデコーダにより受容されるＳバイナリーワードの連続に対応し、即ち、ＯＳＤコーディング及びＲＡＭ内のメモリ記憶の前である。
図９はビデオデコーダーにインストールされたＯＳＤコーダー及びＯＳＤデコーダーからなるコーデックの構成の例を示す。破線で図示されたコーデック５０はメモリバスを介してビデオデコーダのＲＡＭメモリ４９に連結される。
【００８１】
ビットマップデータ、ＯＳＤ領域の座標、カラーのパレット、ビデオデコーダにより受容され、ＯＳＤ情報に関するデータは例えば図示されないビデオデコーダのマイクロコントローラのインターフェイスを介して、ＯＳＤコーデックの入力に送られる。この入力はバス制御回路５１の入力に連結され、このＯＳＤ情報はバス制御回路５１を通して送られ、これは第一の出力を介してビットマップデータをＯＳＤコーダー５２に向け、カラーのパレット及びＯＳＤ座標は第二の出力を介して入出力回路５３の第一の入力に向けられる。ＯＳＤコーダー５２の出力は入出力回路５３の第二の入力に連結される。この回路５３は双方向リンクにより特にＲＡＭメモリであるコーデックの外側とデータを交換する。回路５３は第一の出力を介してＯＳＤデコーダ５４に連結され、第二の出力を介してコーデック５０の第一の出力に連結される。ＯＳＤデコーダ５４の出力はコーデック５０の第二の出力に連結される。このコーデック５０の第一の出力はビデオデコーダのメモリ５５の第一の入力に連結される。このコーデック５０の第二の出力はビデオデコーダのメモリ５５の第二の入力に連結される。最終的にこのメモリ５５は出力としてＹ，Ｕ，Ｖ情報を提供する輝度及びクロミナンス信号５６を発生する回路に連結される。
【００８２】
ビデオデコーダにより受容されたビットマップデータはバス制御器５１を介してＯＳＤコーダー５２に送られ、このコーダーの出力でコード化されたデータは入出力回路５３を介してそこに記憶されるようビデオデコーダーのＲＡＭメモリに送られる。パレット及び座標に関する他のＯＳＤデータはまたメモリエリアに記憶されるようバス制御器及び入出力インターフェイスを介してＲＡＭメモリに送られる。コーダーで作られた辞書はまたＲＡＭメモリに送られる。ビットマップデータの場合には圧縮され、パレット、座標、辞書の内容の場合には圧縮されないこの情報全てはＯＳＤデコーダ５４により用いられる。後者は入出力インターフェイス５３を介して、辞書と同様にビットマップデータストリーム又はＢＥＢ（ビットマップエンコード化されたビットストリーム）を受ける。これらのデータはこのＯＳＤデコーダ５４によりデコードされ、これはＣＬＵＴメモリ５５への出力として及び各画素ｉに対してこの画素に対応するカラーを含むパレットのアドレスであるアドレス（ここではコード化されていない）を送る。ＲＡＭのメモリに記憶されたこのパレットは入出力インターフェイス５３を介してビットマップデータのデコーディングの前にこのメモリ５５に送られている。デジタル輝度及びクロミナンスデータはメモリ５５から表示器回路（表示ユニット）５６に出力として送られ、これは付加的にビデオ情報を受信する。
【００８３】
ＯＳＤ情報がデコーダに送られる場合のコーデックが記載されてきた。この情報がレジデントである場合には、レジデントビットマップデータが他の部分にコード化されたビットマップデータであり、ビデオデコーダにＯＳＤコーダーを設ける必要はない。故に、ＯＳＤデコーダのみが本発明を機能させるためにビデオデコーダーで必要となる。
【００８４】
本発明はＭＰＥＧ  ＩＩビデオデコーダの文脈で説明されてきた。これは明らかに一実施例に関するものであり、如何なる種類、テレビジョンセット、ビデオレコーダ、又は他の如何なるデコーダのコーデックの如何なる設置も本発明の範囲から離れるものではない。
【図面の簡単な説明】
【図１】本発明によるビットマップデータのコーダーを示す。
【図２】Ｌをコーディングするためのクラスによるコーダーを示す。
【図３】シンボルＳコーダーを示す。
【図４】ビットマップデータをコーディングする方法のフローチャートを示す。
【図５】ビットマップデータのストリームをコーディングする例を示す。
【図６】ビットマップコード化データのデコーダを示す。
【図７】ビットマップコード化データをデコーディングする方法のフローチャートを示す。
【図８】ビットマップコード化データのストリームのデコーディングの例を示す。
【図９】コーデックを示す。
【符号の説明】
１、２、３、４、５  コーダー
６  クラス決定回路
７  コーディング回路
８、１４  比較器
９、１８  論理回路
１０  トランスコーダー
１１  マルチプレクサ
１２、１５  辞書
１３、３７  トランスコーディング回路
１６  カウンタ
３２  デコーディング装置
３３  ＦＩＦＯメモリ
３４  フィールド識別回路
３５  メモリ
３６  シンボル抽出回路
３８  シンボル
４９、５５  メモリ
５０  コーデック
５１  バス制御回路
５２  ＯＳＤコーダー
５３  入出力回路
５４  ＯＳＤデコーダ
５６  クロミナンス信号
Ｓ  シンボル
Ｌ  シンボルの数
【図１】
0004406481.tif 000018
【図２】
0004406481.tif 000019
【図３】
0004406481.tif 000020
【図４】
0004406481.tif 000021
【図５】
0004406481.tif 000022
【図６】
0004406481.tif 000023
【図７】
0004406481.tif 000024
【図８】
0004406481.tif 000025
【図９】
0004406481.tif 000026