(57)【要約】      （修正有）【課題】データ圧縮に関するデータ要素を発生確率に基づいて効率よく符号化する。【解決手段】分かっている又は測定した確立分布に最適に適合されるシステム、方法及びコンピュータプログラムプロダクトにより、過度に大きなルックアップテーブルを使用することなしに、データを符号化する。エンコーダ２０１は２つ以上の異なる符号化方法を組み合わせて用いる。テーブル検索によるハフマン符号化を指数ゴロム式を用いることによるような計算による生成と組み合わせる。最も一般に生じる要素を小さなハフマンテーブルで検索し、残りの要素を式で符号化する。また、２つ以上の式を用いてデータを符号化する。更に、複数のテーブルを１つ以上の式と関連させて用いることによりデータを符号化する。【選択図】図１
2010183595.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの符号化技術の組み合わせを用いて、少なくとも１つのシンボルを有する入力データストリームを符号化する工程と、この入力データストリームのこの少なくとも１つのシンボルの発生確率が予め決定したしきい値よりも大きい場合に、第１の符号化技術を適用する工程と、この入力データストリームのこの少なくとも１つのシンボルの発生確率が前記予め決定したしきい値よりも大きくない場合に、前記第１の符号化技術を適用せずに第２の符号化技術を適用する工程とを具えるデータ圧縮方法。
【請求項２】
請求項１に記載のデータ圧縮方法において、前記第１の符号化技術が、ハフマンルックアップテーブルを有するようにするデータ圧縮方法。
【請求項３】
請求項２に記載のデータ圧縮方法において、前記第２の符号化技術が、計算による生成を有するようにするデータ圧縮方法。
【請求項４】
請求項３に記載のデータ圧縮方法において、前記計算による生成を指数ゴロム形式とするデータ圧縮方法。
【請求項５】
請求項１に記載のデータ圧縮方法において、前記少なくとも２つの符号化技術が、それぞれ異なる符号化式を用いる少なくとも２つの計算による生成を有するようにするデータ圧縮方法。
【請求項６】
請求項１に記載のデータ圧縮方法において、このデータ圧縮方法が更に、前記少なくとも１つのシンボルの大きさを計算する工程を有しているデータ圧縮方法。
【請求項７】
請求項１に記載のデータ圧縮方法において、このデータ圧縮方法が更に、符号付きシンボル及び符号無しシンボルを符号化する工程を有しているデータ圧縮方法。
【請求項８】
少なくとも２つの符号化技術の組み合わせを用いて、少なくとも１つのシンボルを有する入力データストリームを符号化する工程と、この少なくとも１つのシンボルの発生確立のアルゴリズム的解析に基づいて前記少なくとも２つの符号化技術の１つを選択的に適用することにより、この少なくとも１つのシンボルを符号化する工程とを有するデータ圧縮方法であって、前記アルゴリズム的解析が、前記少なくとも１つのシンボルの大きさを計算する工程を有し、一定の定数よりも大きい大きさを有する前記少なくとも１つのシンボルのシンボルはハフマンルックアップテーブルにより符号化し、一定の定数よりも大きくない大きさを有する前記少なくとも１つのシンボルのシンボルは計算による生成を用いて符号化するデータ圧縮方法。
【請求項９】
少なくとも２つの符号化技術の組み合わせを用いて、少なくとも１つのシンボルを有する入力データストリームを符号化する工程と、この少なくとも１つのシンボルの発生確立のアルゴリズム的解析に基づいて前記少なくとも２つの符号化技術の１つを選択的に適用することにより、この少なくとも１つのシンボルを符号化する工程と、符号付きシンボル及び符号無しシンボルを符号化する工程と、出力ビットストリームに追加のビットを導入することなしに、符号化された符号付きシンボルに対しハフマンルックアップテーブル内に導入する工程とを具えるデータ圧縮方法。
【請求項１０】
少なくとも２つの符号化技術の組み合わせを用いて、少なくとも１つのシンボルを有する入力データストリームを符号化する工程と、この入力データストリームのこの少なくとも１つのシンボルの発生確率が予め決定したしきい値よりも大きい場合に、第１の符号化技術を適用する工程と、この入力データストリームのこの少なくとも１つのシンボルの発生確率が前記予め決定したしきい値よりも大きくない場合に、前記第１の符号化技術を適用せずに第２の符号化技術を適用する工程とを具えるデータ圧縮方法を、機械が実行しうるようにする命令を具現化する機械可読媒体。
【請求項１１】
少なくとも２つの符号化技術の組み合わせを用いて、少なくとも１つのシンボルを有する入力データストリームを符号化する手段と、この入力データストリームのこの少なくとも１つのシンボルの発生確率が予め決定したしきい値よりも大きい場合に、第１の符号化技術を適用する手段と、この入力データストリームのこの少なくとも１つのシンボルの発生確率が前記予め決定したしきい値よりも大きくない場合に、前記第１の符号化技術を適用せずに第２の符号化技術を適用する手段とを具えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ圧縮に関するものであり、特にデータ要素をこれらの発生確率に基づいて効率よく符号化することに関するものである。
【０００２】
本出願は、
“RATE CONTROL WITH VARIABLE SUBBAND QUANTIZATION ”の名称で２００４年９月２１日に出願された米国特許出願第60/612,311号と、
“SPLIT TABLE ENTROPY CODING”の名称で２００４年９月２２日に出願された米国特許出願第60/612,652号と、
“PERMUTATION PROCRASTINATION ”の名称で２００４年９月２２日に出願された米国特許出願第60/612,651号と、
“MOBILE IMAGING APPLICATION, DEVICE ARCHITECTURE, AND SERVICE PLATFORM ARCHITECTURE”の名称で２００４年１０月１２日に出願された米国特許出願第60/618,558号と、
“VIDEO MONITORING APPLICATION, DEVICE ARCHITECTURES, AND SYSTEM ARCHITECTURE”の名称で２００４年１０月１３日に出願された米国特許出願第60/618,938号と、
“MOBILE IMAGING APPLICATION, DEVICE ARCHITECTURE, AND SERVICE PLATFORM ARCHITECTURE AND SERVICES ”の名称で２００５年２月１６日に出願された米国特許出願第60/654,058号と
の仮出願の優先権を主張するものであるが、これらの各仮出願は全て参考のために記載したものである。
【０００３】
本出願は、
“MULTIPLE CODEC-IMAGER SYSTEM AND METHOD ”の名称で２００４年９月１６日に出願された米国特許出願第10/944,437号であり、２００５年５月１９日に公開された米国特許出願公開第US2005/0104752号の一部継続出願、
“SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCT FOR IMAGE AND VIDEO TRANSCODING ”の名称で２００３年４月１７日に出願された米国特許出願第10/418,4649号であり、２００３年１１月６日に公開された米国特許出願公開第US2003/0206597号の一部継続出願、
“WAVELET TRANSFORM SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCT ”の名称で２００３年４月１７日に出願された米国特許出願第10/418,4649号であり、２００３年１０月２３日に公開された米国特許出願公開第US2003/0198395号の一部継続出願、
“PILE-PROCESSING AND METHOD FOR PARALLEL PROCESSORS”の名称で２００３年５月２８日に出願された米国特許出願第10/447,455号であり、２００３年１２月１１日に公開された米国特許出願公開第US2003/0229773号の一部継続出願、
“CHROMA TEMPORAL RATE REDUCTION AND HIGH-QUALITY PAUSE SYSTEM AND METHOD ”の名称で２００３年５月２８日に出願された米国特許出願第10/447,514号であり、２００３年１２月２５日に公開された米国特許出願公開第US2003/0235340号の一部継続出願、
“SYSTEM AND METHOD FOR TEMPORAL OUT-OF-ORDER COMPRESSION AND MULTI-SOURCE COMPRESSION RATE CONTROL ”の名称で２００４年９月２９日に出願された米国特許出願第10/955,240号であり、２００５年５月１９日に公開された米国特許出願公開第US2005/0105609号の一部継続出願、
“COMPRESSION RATE CONTROL SYSTEM AND METHOD WITH VARIABLE SUBBAND PROCESSIN”の名称で２００５年９月２０日に出願された米国特許出願の一部継続出願（出願人の整理番号は74189-200301/US である）
であるが、これらの一部継続出願は全て参考のために記載したものである。参考のために記載するが、本出願には、
“MULTIPLE CODEC-IMAGER SYSTEM AND METHOD ”の名称で２００４年１１月３０日に発行された米国特許 6,825,780号、
“SYSTEM AND METHOD FOR A DYADIC-MONOTONIC(DM) CODEC”の名称で２００５年１月２５日に発行された米国特許6,847,317号及び
“PERMUTATION PROCRASTINATION ”の名称で２００５年９月２１日に出願された米国特許出願（出願人の整理番号は74189-200501/US である）
をも関連している。
【背景技術】
【０００４】
静止画像及びビデオをそのままデジタル化するには多くの“ビット”を必要とする。従って、記録、転送及びその他の使用の為には、画像及びビデオを圧縮するのが一般的である。殆どの、画像及びビデオコンプレッサは、基本的なアーキテクチャを共有してこれに変化を与えている。この基本的なアーキテクチャは、図１に示すように、３段、すなわち、変換段と、量子化段と、エントロピーコーディング段とを有する。
【０００５】
画質と、プロセッサ条件（すなわち、費用／電力消費量）と、圧縮比（すなわち、得られるデータ転送速度）とのバランスをとることにより、データ通信のストリーム（流れ）に必要とするデータ転送速度を低減させるのに、ビデオ“コーデック(codec )”（コンプレッサ／デコンプレッサ）が用いられている。現在得られるデータ圧縮手段は、異なるレンジのトレードオフを提供するとともに、各々が特定の分野の必要性を満足するように最適化されている複数のコーデックプロファイルを生ぜしめる。
【０００６】
ビデオコンプレッサにおける変換段の目的は、ソース画像又はシーケンスにおける局部的な類似性及びパターンの利点をとることにより、ソース画像のエネルギー又は情報をできるだけコンパクトな形態に収縮させることである。コンプレッサは、“ティピカル”入力で良好に動作するとともにこれらの欠落を無視して、“ランダム”又は“パスオロジカル（pathological）”入力を圧縮するように設計されている。
【０００７】
ＭＰＥＧ‐２のような多くの画像圧縮及びビデオ圧縮方法は、変換段として離散コサイン変換（ＤＣＴ）を用いている。
【０００８】
ＭＰＥＧ−４テクスチュアのような幾つかのより新規な画像圧縮及びビデオ圧縮方法は、変換段として種々のウェーブレット変換を用いている。
【０００９】
ウェーブレット変換には、一次元又はそれよりも多い次元の何れかで一組のデータにウェーブレットフィルタ対を繰り返し適用することが含まれている。画像圧縮の場合、２Ｄ（水平及び垂直）ウェーブレット変換を用いることができる。ビデオデータストリームの場合、３Ｄ（水平、垂直及び時間）ウェーブレット変換を用いることができる。
【００１０】
従来技術の図２には、現在得られる種々の圧縮アルゴリズムのうちのトレードオフの一例１００を示す。図示するように、このような圧縮アルゴリズムは、ウェーブレットに基づくコーデック１０２と、種々のＭＰＥＧビデオ分布プロファイルを含む、ＤＣＴに基づくコーデック１０４とを有する。
【００１１】
２Ｄ及び３Ｄウェーブレットは、ＤＣＴに基づくコーデックアルゴリズムとは相違して、その画質が良く、圧縮比に融通性がある為に、高く評価されており、依然として画像の標準化となっているＪＰＥＧ２０００に対しウェーブレットアルゴリズムを採用することをＪＰＥＧ委員に指示するものである。しかし、残念ながら、殆どのウェーブレットを実行するのに、極めて複雑なアルゴリズムが用いられており、代案のＤＣＴに比べて多量の処理電力が必要となる。更に、ウェーブレットは３Ｄウェーブレットを特に困難とする独特な課題を時間圧縮に対し課する。
【００１２】
上述した理由で、ウェーブレットは、ＭＰＥＧのような高容量の標準規格であるコーデックよりも価格的に優位性のある利点を提供するものではなく、従って、すき間産業で採用されているにすぎない。従って、３つの主たる市場区分に主眼を置いた低電力及び低価格に最適な３Ｄウェーブレットを商業的に実現可能にする必要がある。
【００１３】
例えば、小型ビデオカメラが広く用いられるようになってきており、信号をデジタル処理する利点が明白となっている。例えば、幾つかの国での携帯電話市場の最も成長の速い部分は、画像及びビデオクリップ能力を有する電話に対するものである。殆どのデジタルスチルカメラはビデオクリップ特性を有している。携帯電話市場では、これらのスチル画像及び短いビデオクリップを伝送するのに、装置のバッテリの容量をより多くすることを要求している。現存のビデオ符号化の標準規格及びデジタル信号プロセッサが更に多くの負担をバッテリに加えている。
【００１４】
他の新規な適用分野は、視聴者が生のテレビジョン及びビデオ録画プログラミングを一時停止しうるようにするパーソナルビデオレコーダ（ＰＶＲ）である。これらの装置は、ビデオ記録するデジタルハードディスク記録装置を用いており、ケーブルからのアナログビデオをビデオ圧縮する必要がある。これらの特徴をピクチュア・イン・ピクチュア（画像中の画像）及びウオッチ・ファイル・レコード（記録中の視聴）として提供するためには、これらの装置が複数のビデオ圧縮エンコーダを必要とする。
【００１５】
成長している他の適用分野は、監視及び警備ビデオ用のデジタルビデオレコーダ（ＤＶＲ）である。この場合も、記録すべき入力ビデオの各チャネルに対し圧縮符号化が必要となる。便利で融通性のあるデジタルネットワーク伝送アーキテクチャの利点をとるためには、ビデオがしばしばカメラにおいてデジタル化される。旧来の多重化レコーダアーキテクチャの場合でも、多チャネル圧縮エンコーダが用いられている。
【００１６】
低電力及び低価格に最適で商業的に実現可能な圧縮機構により利益を得る多数の他の市場が存在すること、勿論である。
【００１７】
エントロピーコーディング
（文献では“ソースコーディング”としても知られている）エントロピーコーディングの目的は、一般に、メッセージすなわち情報ソースから、後に、好ましくは正確にオリジナルとしてもとのメッセージに戻すように復号しうる、より短いメッセージを生ぜしめることである。代表的には、過大なコードブックにおける大きなブロックを又は全入力メッセージ（例えば、画像又はビデオＧＯＰ）さえをも検索（ルックアップ）することによってではなく、ソースメッセージを“シンボル”に分割し、メッセージをシンボル毎に処理することにより上述した目的を達成している。
【００１８】
一定の大きさの入力シンボルで動作するとともに、各シンボルに対し可変長のビットストリングを生じる種類のエントロピーコーダは文献において“ブロック‐バリアブルコーダ”として知られている。
【００１９】
シンボルを符号化する２つの代表的な方法
符号化する入力シンボルが与えられた場合に、これを符号化する１方法は、このシンボルをインデックスとしてとらえ、これを“コードブック”と称するテーブルで検索することである。このコードブックで見いだされた入力（エントリー）が、シンボルに対する符号化された出力である。コードブックは代表的に、可能なあらゆるシンボルに対する入力を提供するのに充分な大きさとなっている。
【００２０】
ある実施では、テーブルに対する１回のランダムアクセスが極めて高速且つ有効となるものである。しかし、他の実施では、大きなテーブルに対するランダムアクセスが（キャッシュメモリのローディングの為に）比較的ゆっくりとなるか、又は（ＦＰＧＡ又はＡＳＩＣにおけるようなオンチップメモリが高価である為に）比較的高価なものとなる。
【００２１】
シンボルを符号化する他の代表的な構成は、通常結果として符号化された出力を生じる２進ビットストリングである表示に関するある計算処理を行うことである。この場合、大きなコードブックを必要とすることなしに出力が生じる。
【００２２】
このような計算はある実施においては程よい速さで有効である。しかし他の実施では、多数の計算工程が必要となり、この計算が比較的ゆっくりとなる。
【００２３】
デコーダは、シンボルに戻るように復号する必要がある可変寸法の各ビットストリング（すなわち、符号語）の長さを決定しうるようにする必要がある。このことは一般に、符号語が、どの符号語も他の符号語の接頭語となっていない“ハフマン接頭語特性”を有するようにすることにより達成されている。
【００２４】
分布
上述したエントロピーコーディングは、シンボル間の非画一性の確率の利点を採用することにより機能する。シンボルの発生確率が高い（このことは、このシンボルがしばしばメッセージすなわち情報ソース内に生じることを意味する）と、このシンボルは短い符号語で符号化される。シンボルの発生確率が低い（このことは、このシンボルはまれにしかメッセージすなわち情報ソース内に生じないことを意味する）と、このシンボルは長い符号語で符号化される。従って、短い符号語が多く、長い符号語が少ない符号化された出力は通常、入力よりも短くなる。
【００２５】
１９４８年７月及び１０月に発行された技術誌“Bell System Technical Journal ”の論文“The Mathematical Theory of Communications ”（C. E. Shannon 氏著）に記載されているように、最適な符号化は、ソース入力における対応のシンボルの発生確率に対し逆対数関係にある各出力符号語の長さを有する。このことは、通常は正確に達成されないが、エンコーダの設計によりその概算を達成しようとしている。
【００２６】
従って、有効なエントロピーコードを設計するために、シンボルの確率分布を知るか、測定するか、概算するか、又は想定する。
【００２７】
ある確率分布に対しては、極めて少ない工程で符号化計算方法を行うことができるが、他の確率分布に対しては、良好な符号化を計算するのに多くの工程が必要となる。
【００２８】
ビデオ計算作業では、量子化係数の確率分布がしばしば不適切なものとなるおそれがある。換言すると、確率分布は既知の高速計算符号化を有するものではなく、可能な値の個数が、得られるルックアップ記憶装置に適合させるには大きすぎるコードブックを必要とする。
【００２９】
従って、分かっている又は測定された確率分布に最適に適合するが、過度に大きなルックアップテーブルを必要としない符号化方法が必要となるものである。
【発明の概要】
【００３０】
過度に大きなルックアップテーブルを用いることなくデータを符号化するために、分かっている又は測定された確率分布に最適に適合するシステム、方法及びコンピュータプロダクトを提供する。本発明により構成するエンコーダは、２つ以上の異なる符号化方法を組み合わせて用いる。
【００３１】
本発明の１つの観点によれば、テーブル検索によるハフマン符号化を、指数ゴロム（Golomb）式を用いることによるような計算による符号語生成と組み合わせる。最も一般的に発生する要素を小さなハフマンテーブルで検索し、残りの要素を式で符号化する。この構成によれば、テーブル検索によるハフマン符号化の利点（すなわち、分かっている又は測定された確率分布に最適に適合すること）と、簡単な計算による符号化の利点（すなわち、検索を行わない迅速計算）とを組み合わせるが、完全なハフマン符号化の欠点（すなわち、極めて大きなテーブルを維持する必要があること）を回避することを提供する。
【００３２】
本発明の他の観点によれば、２つ以上の式を用いてデータを符号化する。１つの式がデータの種類に正確に適合しない状態で、各々がデータの異なる部分に対している別の式を用いて、全データの確率分布を良好に表すようにすることができる。
【００３３】
本発明の更なる他の観点によれば、複数のテーブルを１つ以上の式と関連させて用いて、データを符号化する。式はデータの一部に対して用いられ、これらの式はデータ部分の確率分布を正確に表している。テーブルには式を散在させて、高速の計算による符号化が分からない個所のような式中の隙間を補填するようにしうる。
【図面の簡単な説明】
【００３４】
【図１】図１は、本発明の一実施例によるデータ圧縮／解凍用フレームワークを示すブロック線図である。
【図２】図２は、現在得られる種々の圧縮アルゴリズムのうちのトレードオフの一例を示す説明図である。
【００３５】
図１は、本発明の一実施例によるデータ圧縮／解凍用フレームワーク２００を示す。このフレームワーク２００には、コーダ部分２０１と、デコーダ部分２０３とが含まれており、これらが相俟って“コーデック”を構成している。ファイル２０８内に記憶するデータを圧縮するために、コーダ部分２０１には、変換モジュール２０２と、量子化器２０４と、エントロピーエンコーダ２０６とが含まれている。このようなファイル２０８の解凍を行うために、デコーダ部分２０３には、エントロピーデコーダ２１０と、逆量子化器２１２と、逆変換モジュール２１４とが含まれており、使用データ（すなわち、ビデオデータ等の場合には、見るためのデータ）を解凍する。使用に際しては、変換モジュール２０２が、非相関の目的で（ビデオデータの場合には）複数の画素の可逆変換、しばしば線形変換を行う。次に、量子化器２０４が、変換値の量子化を行い、その後エントロピーエンコーダ２０６が量子化変換係数のエントロピーコーディングに関与しうるようになる。
【００３６】
本発明により構成したエンコーダは２つ以上の異なる符号化法を組み合わせて用いる。量子化されたあるデータ分布は、（入力ソースにおいて発生確率の低い）大きな計数値に対し負の指数を用い、（入力ソースにおいて最も頻繁に生じる発生確率の最大の）小さな計数値に対し小さなテーブルを用いることにより良好に概算される。従って、本発明の１つの観点によれば、小さなテーブルのみを用いるか、簡単な計算方法を用いるか、これら２つの技術の何れか（テーブル又は計算）を選択する方法を適用するようにしうる。
【００３７】
本発明の他の観点によれば、どのデータ要素又はシンボルにどの技術を適用するかの選択は大きさの簡単なテストとすることができる。本例では、エントロピーコーディングすべきシンボルを１〜２15−１の範囲内で常に正とする。値ゼロは排除する。又、シンボルを、これが一定値よりも小さいかどうかに関して簡単にテストする。シンボルが一定値よりも小さい場合には、この一定値と同じ大きさのテーブルを用いる。シンボルが一定値よりも小さくない場合には、計算方法を用いる。
【００３８】
本例では、小さな（頻繁に生じる）値に対して、ルックアップテーブル中のハフマン符号語が用いられる。大きな（頻繁に生じない）値に対しては式、例えば、指数ゴロム形式の式を用いて符号語を計算する。このような実施によれば、過去にいかに符号化されたかを保持することなしにシンボルを順次符号化しうる。一定長のシンボルは１６ビットとしてエンコーダに入力され、出力長において１ビット（頻繁に生じる値）から１６ビット（まれな値）に変化する。
【００３９】
エンコーダの２つの部分の各々は、ハフマン接頭語特性を別々に有する。換言すると、エンコーダの１つの部分におけるシンボルに対し用いられている符号語が、エンコーダの同じ部分における他のシンボルに対する符号語の開始部分に等しくない。多くの分野に対する代表的な確率分布のレンジの場合、エンコーダの２つの部分に対する合成符号もハフマン接頭語特性を有し、従って、１つの符号語が終了し、次の符号語が開始する個所をデコーダに示すのに、符号語の出力ストリーム中に追加のマーカービットを必要としない。
【００４０】
アルゴリズム例１
このアルゴリズム例は、２進表示における１６ビットのゼロでない正の整数であるシンボルＳを入力として受け入れる。その出力としてビットストリングＷを生じる。
【００４１】
工程１
Ｓ＞１５の場合、工程３に進む。
【００４２】
工程２
以下に示すテーブル１におけるＳを検索して値Ｂ及び長さＬを見いだす。
ＷはＢの下位のＬビットより成る。
出力ビットストリームにＷを加える。終了する。
【００４３】
工程３
数Ｓ＋８において、最も左側の“１”ビット（これを含む）から始まる上位ビットを計数する。計数値Ｃを呼び出す。
【００４４】
工程４
Ｗは２Ｃ−１個のビット、すなわち、Ｃ−１個の“０”ビットと、これに続く数Ｓ＋８のＣ個の上位ビットとより成る。
Ｗを出力ビットストリームに加える。終了する。
【００４５】
【表１】
2010183595.tif 000003
【００４６】
比較の目的で、テーブル１が用いられなかった場合に、１６よりも小さいシンボル値に対し上述した工程３及び４（符号語の計算による生成）により得られる出力を以下のテーブル２に示す。２つのテーブルを比較することから分かるように、テーブル１のハフマンテーブル手法を用いることにより、テーブル２の計算により生成させる手法に比べて、あるより頻繁に生じるシンボルに対してより短い符号語を生ぜしめる。
【００４７】
【表２】
2010183595.tif 000004
【００４８】
性能
本例の方法によれば、あるコンピュータプラットフォームで実行した際に高性能の目的を達成する。その理由は、
‐最も一般的な場合に対し任意のハフマン符号を提供し、
‐測定した確率分布の部分に最適に適合させるために、制限されたメモリ内に適合する小さなテーブルしか必要とせず、
‐まれな場合に対して、指数ゴロムコーディングの極めて簡単な計算が用いられ、
‐シンボルにかかわらず、処理が高速である
為である。
【００４９】
本発明の上述した実施例には種々の改良を行うことができる。例えば、エントロピーコーダを、符号付き数値のシンボルや、上述した符号無し数値（正のみ）のシンボルを符号化するように変更を施すことができる。このことを有効に行うために、テーブル中の各Ｌ入力を１だけ増大させ、符号ビットを各Ｂ値に加え、負のシンボルに対するテーブル入力を含める。以下のテーブル３は、その一例を示す。このテーブル３には、より迅速な直接的な検索を可能にするためにシンボル０に対する入力がある。この０のシンボルの入力は、用いられない擬似の入力である為、その内容は実体のないものである。
【００５０】
上述した簡単なアルゴリズムは、この場合アルゴリズム例２におけるように僅かに変更させる。
【００５１】
アルゴリズム例２
このアルゴリズムは、入力として、シンボルＳ、すなわち、２進表示で表した１６ビットの整数（値ゼロは考慮しない）。生成される圧縮ビットストリームにビット毎に加えるためのビットストリングＷが出力として生ぜしめられる。
【００５２】
工程１
Ｓの絶対値が１５よりも大きい場合に、工程３に進む。
【００５３】
工程２
以下のテーブル３において、Ｓを検索して値Ｂ及び長さＬを見いだす。
ＷはＢの下位のＬビットより成る。
出力ビットストリームにＷを加える。終了する。
【００５４】
工程３
数Ｓ＋８の絶対値において、最も左側の“１”ビット（これを含む）から開始して上位ビットを計数する。これをＣと称する。
【００５５】
工程４
Ｗは、Ｃ−１個の“０”ビットと、これに続く数Ｓ＋８のＣ個の上位ビットと、これに続くＳの符号ビットとより成る。
出力ビットストリームにＷを加える。終了する。
【００５６】
【表３】
2010183595.tif 000005
【００５７】
上述した例では、テーブル検索によるハフマンコーディングの利点（分かっている又は測定された確率分布に最適に適合すること）を、指数ゴロムのような簡単な計算による符号化の利点（検索のない迅速な計算）と組み合わせることができるとともに、ハフマンコーディングの欠点（テーブルが極めて大きくなる）を回避しうる。通常の場合に、出力に追加のビットを導入することなしに、符号ビットをルックアップテーブルに導入することにより、符号付きシンボルデータをより高速に符号化する方法をも実現される。
【００５８】
上述したのと同様に、テーブル検索と計算による生成との種々に組み合わせを採用することができる。例えば、２つの異なる式を用い、各式を、符号化されるシンボルの異なるサブセットに適用することができる。このような組み合わせを用いるコトに対する利点は、１つの既知の式は特定の種類のデータの確率分布に良好に適合しないが、２つ以上の式を組み合わせることにより、より一層適合するようになるということである。他の利点は、多くの共通のシンボルに対し簡単な式を用いて、符号化の全処理速度を高めるようにすることができる。
【００５９】
複数の式の各々に対して、同じ一般形式の式を用いることができ、又は異なる形式の式を組み合わせることができる。本発明により構成したシステムに用いて有利な異なる形式の式又は処理のある例は、指数ゴロム、ゴロム、ゴロム‐ライス（又はライス‐ゴロム）符号及び演算コーデックを含む。シンボル毎ではない方法で動作する演算コーデックは更に、(System and Method for a Dyadic-Monotonic (DM) Codec の名称で２００５年１月２５日に発行された米国特許第 6,847,317号明細書に記載されているように)ダイナミック‐モノトニック（ＤＭ）コーデックのような、サブタイプのもの及びＣＡＢＡＣを有する。
【００６０】
他の実施例では、複数のテーブルを１つ以上の式と関連させて用いることによりデータを符号化する。式は、これらの式がデータ部分の確立分布を正確に表わしている当該データ部分に対し用いられる。テーブルには式を散在させて、高速の計算による符号化が分からない式中の隙間を補填するようにしうる。
【００６１】
本発明によれば、システムが、符号化のために与えられるものと予期される個別のシンボルの個数と、ルックアップテーブル中の個別のシンボルの個数との間にある関係を提供するように設計された、又はこの関係を提供する際に、エンコーダに利点が得られることを確かめた。更に、システムは、テーブルが代表的にエントロピーコーディングで処理されるシンボルの総数（又は頻度）のある割合を表わす複数の個別のシンボルを有するようにするか、又はこのように設計されると、更なる利点が得られる。
【００６２】
例えば、ルックアップテーブルと、少なくとも１つの式とを組み合わせるエンコーダのある例では、ルックアップテーブルのシンボルが代表的に符号化すべき個別のシンボルの０パーセント〜５０パーセントを表わすようにした当該ルックアップテーブルを提供するのが有利であることを確かめた。説明の便宜上、この百分率を“テーブル個別シンボル百分率（すなわち、ＴＤＳＰ）”として表わす。特に、レンジが、代表的に符号化のために与えられるものと予期される個別のシンボルの、総合同定の０〜３０パーセント、特に０〜１０パーセント、更に特に０〜３パーセント、更に特に０〜１パーセント、更に特に０〜０．１パーセント、更に特に０〜０．０１パーセントを表わしうるようにする。
【００６３】
更に、本発明によれば、代表的に符号化のために与えられるシンボルの総数（又は頻度）の１００〜５０パーセントを合計で有する複数のシンボルを含むようにテーブルを設計しうる。説明の便宜上、この百分率を“テーブル総計頻度百分率（すなわち、ＴＡＦＰ）”として表わす。特に、複数のシンボルは総計で、代表的に符号化のために与えられるシンボルの総数（又は頻度）の１００〜７０パーセント、特に１００〜８０パーセント、更に特に１００〜８５パーセント、更に特に１００〜９０パーセント、更に特に１００〜９５パーセントを有するようにしうる。
【００６４】
例えば、本発明による１つの圧縮方法においては、符号化すべき個別のシンボルの総数を３２，７６６個とする。エンコーダに与えられるデータ中に高頻度を有するものと予期される１５個の個別のシンボルがルックアップテーブルにあるものとする。従って、これらの１５個のシンボルは、個別のシンボルの総数の約０．０４６パーセントとなる。従って、本例は約０．０４６パーセントのテーブル個別シンボル百分率を有する。しかし、代表的な処理では、これらの１５個のシンボルは、符号化のために与えられる総計のシンボル発生の約９０パーセントを表わすことを確かめた。従って、本例は、約９０パーセントのテーブル総計頻度百分率を有する。従って、１５個のシンボルの比較的小さなテーブルにより、圧倒的に多数のシンボル（符号化のために与えられるシンボルの約９０％）の符号化に対処しうる。
【００６５】
更に、本発明の範囲内で、複数のルックアップテーブル又はその他のテーブルを用い、テーブル個別シンボル百分率とテーブル総計頻度百分率とを複数のテーブルの組み合わせに基づいて計算するようにする符号化技術を提供することが考えられる。
【００６６】
本発明の更なる観点には、少なくとも１つのルックアップテーブルと少なくとも１つの符号化式との組み合わせを有し、テーブル個別シンボル百分率とテーブル総計頻度百分率とのある組み合わせが与えられているエンコーダを提供することが含まれる。例えば、有利な組み合わせには、０〜５パーセントのＴＤＳＰと１００〜７０パーセントのＴＡＦＰとの組み合わせが含まれる。更なる有利な組み合わせを以下のテーブル４に示す。
【００６７】
【表４】
2010183595.tif 000006
【００６８】
上述したことは、本発明の好適実施例を完全に説明したものであるが、種々の変更及び等価な手段を採用しうるものである。従って、上述した説明は本発明の範囲を制限するものとしてとらえるべきものではなく、本発明の範囲は特許請求の範囲により規定されるものである。
【図１】
2010183595.tif 000007
【図２】
2010183595.tif 000008
【外国語明細書】
2010183595000001.pdf