(57)【要約】【課題】  ハフマン符号化とビデオ画像の圧縮とを高速化する隣接比較に基づく、ロスレス高速画像圧縮システムを提供すること。【解決手段】  隣接比較に基づくロスレス高速画像圧縮システムは、隣接するピクセルとのピクセル値の差を比較し、そのようなピクセル値を最小の差に置き換える。ピクセルのブロック内のすべてのピクセルが一方向の隣接ピクセルと比較されるように、ピクセルのブロックにマーカーが付される。マーカーは、そのブロック内のすべてのピクセルの比較方式を示す。いくつかのフレームに対して1つのツリーが使用されるように、ハフマンツリーの構築を断続的に行う。ハフマン符号化を使用して、結果のフレームを圧縮する。所定の数のフレームごとに1つのハフマンツリーを構築する。ハフマンツリーの構築の頻度は、構築を実行するためのプロセッサ時間の瞬間的な可用性に従って選択することができる。より多くの処理時間が利用可能であるときには、ハフマンツリーをより頻繁に計算する。そのような頻度の変動は、入力ビデオフレーム用のバッファを使用することによって実施することができる。バッファが特定のサイズである場合、ハフマンツリーを構築するためのプロセッサ時間が利用可能である。
2006526367.tif 000002
【特許請求の範囲】
【請求項１】
ビデオストリームを圧縮および伸長するプロセスであって、
前記ビデオストリームにおけるビデオフレームを最良隣接アルゴリズムを使用して前処理する高速前処理手段を提供するステップと、
前記ビデオフレームをハフマン符号化を使用して圧縮するステップと、
を含んでおり、
当該圧縮ステップによって前記ビデオフレームが受信されるにつれて、1レベルのハフマン符号ツリーが作成され、かつ、
当該圧縮ステップが、圧縮されたビデオストリームを出力する、
プロセス。
【請求項２】
当該圧縮ステップが、
一連のフレームにおける第1の数のフレームを走査し、前記第1の数のフレームにおける符号に対して統計的分布を実行する統計的分布計算手段、を提供するステップ、
をさらに有する、請求項1に記載のプロセス。
【請求項３】
当該圧縮ステップが、
前記走査されたフレームの前記統計的分布を使用してハフマンツリーを作成するステップと、
前記一連のフレームにおける前記符号を前記ハフマンツリーを使用して変換するステップと、
結果のハフマン符号を前記圧縮されたビデオストリームに格納するステップと、
当該作成するステップと、当該変換するステップと、当該格納するステップとを、前記ビデオストリームにおける前記ビデオフレームのすべてについて繰り返すステップと、
をさらに有する、請求項2に記載のプロセス。
【請求項４】
当該ハフマンツリーを作成するステップが、前記ハフマンツリーを前記圧縮されたビデオストリームに格納する、請求項3に記載のプロセス。
【請求項５】
当該圧縮ステップが、ビデオフレームを定期的な頻度において圧縮する、請求項1に記載のプロセス。
【請求項６】
当該圧縮ステップが、十分なCPUリソースが利用可能であるときにフレームを圧縮し、当該圧縮ステップが、入力フレームのバッファを維持することによって前記CPUの可用性を測定し、かつ、前記バッファ内のフレームの数が所定のしきい値よりも大きくなったときに、当該圧縮ステップが、前記バッファ内の前記フレームの数が第2の所定のしきい値よりも小さくなるまで、フレームの圧縮を省略し、前記バッファ内の前記入力フレームを出力ストリームにただちに書き込む、請求項1に記載のプロセス。
【請求項７】
フレームの圧縮比がしきい値よりも小さくなった場合に、当該圧縮ステップが、当該統計的分布計算手段に戻って新しいハフマンツリーを作成する、請求項2に記載のプロセス。
【請求項８】
圧縮されたビデオストリームを受信するステップと、
前記圧縮されたビデオストリームにおける一連のビットから符号を抽出するステップと、
前記抽出された符号を探索して符号におけるビットの長さを見つけるための復号化テーブルを提供するステップと、
当該復号化テーブルにおいて、当該抽出された符号のビットの長さを探索するステップと、
当該抽出するモジュールと当該探索するモジュールを、前記圧縮されたビデオストリームにおける前記ビットのすべてが処理されるまで繰り返すステップと、
をさらに有する、請求項1に記載のプロセスであって、
前記ビットの長さが所定の値に等しい場合、前記圧縮されたストリームから入力符号を抽出し、前記入力符号を圧縮されないビデオストリームに付加し、
前記ビットの長さが所定の値に等しくない場合、当該復号化テーブルから出力符号を探索し、前記出力符号を前記圧縮されないビデオストリームに付加する、
プロセス。
【請求項９】
ビデオストリームを圧縮および伸長する装置であって、
前記ビデオストリームにおけるビデオフレームを最良隣接アルゴリズムを使用して前処理する高速前処理手段と、
前記ビデオフレームをハフマン符号化を使用して圧縮するモジュールと、
を含んでおり、
当該圧縮モジュールによって前記ビデオフレームが受信されるにつれて、1レベルのハフマン符号ツリーが作成され、かつ、
当該圧縮モジュールが、圧縮されたビデオストリームを出力する、
装置。
【請求項１０】
当該圧縮モジュールが、
一連のフレームにおける第1の数のフレームを走査し、前記第1の数のフレームにおける符号に対して統計的分布を実行する統計的分布計算手段、
をさらに有する、請求項9に記載の装置。
【請求項１１】
当該圧縮モジュールが、
前記走査されたフレームの前記統計的分布を使用してハフマンツリーを作成するモジュールと、
前記一連のフレームにおける前記符号を前記ハフマンツリーを使用して変換するモジュールと、
結果のハフマン符号を前記圧縮されたビデオストリームに格納するモジュールと、
当該作成するモジュールと、当該変換するモジュールと、当該格納するモジュールとを、前記ビデオストリームにおける前記ビデオフレームのすべてについて繰り返すモジュールと、
をさらに有する、請求項10に記載の装置。
【請求項１２】
当該ハフマンツリーを作成するモジュールが、前記ハフマンツリーを前記圧縮されたビデオストリームに格納する、請求項11に記載の装置。
【請求項１３】
当該圧縮モジュールが、ビデオフレームを定期的な頻度において圧縮する、請求項9に記載の装置。
【請求項１４】
当該圧縮モジュールが、十分なCPUリソースが利用可能であるときにフレームを圧縮し、当該圧縮モジュールが、入力フレームのバッファを維持することによって前記CPUの可用性を測定し、かつ、前記バッファ内のフレームの数が所定のしきい値よりも大きくなったときに、当該圧縮モジュールが、前記バッファ内の前記フレームの数が第2の所定のしきい値よりも小さくなるまで、フレームの圧縮を省略し、前記バッファ内の前記入力フレームを出力ストリームにただちに書き込む、請求項9に記載の装置。
【請求項１５】
フレームの圧縮比がしきい値よりも小さくなった場合に、当該圧縮モジュールが、当該統計的分布計算手段に戻って新しいハフマンツリーを作成する、請求項10に記載の装置。
【請求項１６】
圧縮されたビデオストリームを受信するモジュールと、
前記圧縮されたビデオストリームにおける一連のビットから符号を抽出するモジュールと、
前記抽出された符号を探索して符号におけるビットの長さを見つけるための復号化テーブルと、
当該復号化テーブルにおいて、当該抽出された符号のビットの長さを探索するモジュールと、
当該抽出するモジュールと当該探索するモジュールを、前記圧縮されたビデオストリームにおける前記ビットのすべてが処理されるまで繰り返すモジュールと、
をさらに有する、請求項9に記載の装置であって、
前記ビットの長さが所定の値に等しい場合、前記圧縮されたストリームから入力符号を抽出し、前記入力符号を圧縮されないビデオストリームに付加し、
前記ビットの長さが所定の値に等しくない場合、当該復号化テーブルから出力符号を探索し、前記出力符号を前記圧縮されないビデオストリームに付加する、
装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ環境におけるデータ圧縮方法に関する。より詳細には、本発明は、ビデオフレームの前処理を使用する、リアルタイムのロスレス高速ビデオ圧縮／伸長に関する。
【背景技術】
【０００２】
ビデオデータは、一般に、大きなメモリブロックに符号化される。例えば、1K×1Kの大きさの1つのビデオフレームでさえも、それを記述するのに数メガバイトが必要となることがある。ビデオデータは、格納するには大量のメモリを必要とし、伝送するには大きな通信帯域を必要とする。従って、ビデオデータを圧縮することは極めて有利である。しかしながら、いくつかの圧縮方法では、プロセス中に情報が失われる。
【０００３】
いくつかのアプリケーションでは、ある程度のデータ消失を許容することができるが、それ以外のアプリケーションでは、ロスレス圧縮が依然として要求されている。
【０００４】
一般的なビデオデータロスレス圧縮方法では、差分パルス符号変調(DPCM)を使用する。現在のピクセル値が、それと前のピクセルとの間の差に置き換えられる。ピクセル値は、走査線に沿っては相当にゆっくりと変化するため、差の値はほぼ0であり、圧縮アルゴリズムが特に有効になる。しかしながら、ピクセル値の間のゆっくりな変化は、垂直帯域や対角帯域(vertical or diagonal bands)においてもしばしば起こる。画像における水平帯域(horizontal bands)しか利用できない先行技術の方法は、不都合である。
【０００５】
リアルタイムのビデオデータを圧縮する目的に、ハフマン符号化を使用することができる。ハフマンツリーが構築され、このツリーは、データを再符号化する目的に使用される。基本的な考え方は、頻繁に出現するビデオ符号を、必要なビットがより少ないハフマン符号に置き換えるというものである。まれに出現するビデオ符号は、ビデオ符号自体よりも多くのビットを必要とするハフマン符号によって記述される。これにもかかわらず、ハフマン符号の組み合わせでは、結果的に圧縮の全体的な効率が高まる。
【０００６】
従来の手法では、ハフマンツリーを一度しか計算しない。このことは、前のツリーからの結果としての実際の差と、その瞬間にジョブを処理する目的に利用できる処理時間には、無関係である。ハフマンツリーを計算するのに必要な計算時間は、そのツリーを使用して1つの画像に対して圧縮を実行するのに要する時間に等しくなることがある。
【０００７】
画像の高速な前処理を提供する隣接比較に基づく、ロスレス高速画像圧縮システムを提供することは、有利であろう。ハフマン符号化とビデオ画像の圧縮とを高速化する隣接比較に基づく、ロスレス高速画像圧縮システムを提供することは、さらに有利であろう。
【発明の開示】
【課題を解決するための手段】
【０００８】
本発明は、隣接比較に基づくロスレス高速画像圧縮システムを提供する。本発明は、画像の高速前処理を提供する。さらに、本発明は、より高速なハフマン符号化とビデオ画像圧縮とを提供する。
【０００９】
本発明の好ましい実施例は、隣接するピクセルとのピクセル値の差を比較し、ピクセル値を最小の差に置き換える、最良隣接アルゴリズム(best-neighbor algorithm)を使用してビデオストリームのビデオフレームの前処理を行う。これにより、画像フレームの値の変動が小さくなり、圧縮が良好になる。
【００１０】
n×mのピクセルのブロック内のすべてのピクセルが一方向の隣接ピクセルと比較されるように、n×mのピクセルのブロックにマーカーが付される。マーカーは、そのブロック内のすべてのピクセルの比較方式を示す。
【００１１】
結果のフレームは、ハフマン符号化を使用して圧縮する。本発明は、ハフマン符号ツリーの構築を断続的に行うことによって、CPUリソースをより効率的に使用する。所定の数のフレームごとに1つのハフマンツリーを一回構築し、それを使用して一連のフレームを圧縮する。リアルタイムのビデオ圧縮を目的として使用するとき、ハフマンツリーを構築する頻度は、その構築を実行するためのプロセッサ時間の瞬間的な可用性に従って選択する。
【００１２】
より多くの処理時間が利用可能であるときには、ハフマンツリーをより頻繁に計算する。頻度の変動は、圧縮するビデオフレーム用の入力ビデオフレームバッファをチェックすることによって実施する。フレームバッファのサイズが所定の値である場合、ハフマンツリーを構築する目的にプロセッサ時間が利用可能である。
【００１３】
本発明のその他の観点および利点は、本発明の原理を一例として示している添付の図面を参照することにより、以下の説明から明らかになるであろう。
【発明を実施するための最良の形態】
【００１４】
本発明は、隣接比較に基づくロスレス高速画像圧縮システムに具体化されている。本発明によるシステムは、画像の高速な前処理を提供する。本発明は、より高速なハフマン符号化とビデオ画像圧縮をさらに提供する。
【００１５】
ビデオフレームの圧縮および伸長をリアルタイムにおいて機能させるためには、圧縮および伸長が高速でなければならないのみならず、入力ビデオを前処理する時間がない。ビデオフレームの圧縮および伸長は、一定量の時間内に完了しなければならない。
【００１６】
本発明の好ましい実施例は、良好な圧縮のため画像フレームの値の変動を小さくすることを目的とする、ビデオ画像（フレーム）の高速な前処理を提供する。前処理されたビデオフレームは、ハフマン符号化を使用して圧縮する。ハフマン符号化には大量の計算時間が必要であるため、本発明は、ハフマン符号化を高速化する。また、本発明では、利用可能な計算容量が、圧縮すべきビデオデータに追いつかない場合、フレームを選択的に圧縮する。
【００１７】
図1は、本発明の高速前処理最良隣接圧縮方法の実施例を示しており、この方法は、本明細書においては参照番号100によって表されている。以下の説明においては、一例として4×4のサイズのブロックを使用しているが、n×m（nは走査線の数より小さい任意の数、mは1本の走査線におけるピクセルの数より小さい数）のブロックに本発明を一般化できることが、当業者には容易に理解されるであろう。
【００１８】
方法100によって圧縮する一般的なビデオストリームは、一連のビデオフレームを有し、各ビデオフレームは、複数の走査線を有し、各走査線は、複数のピクセルを含んでいる。方法100は、現在の走査線のアドレスカウンタをフレームの一番上の走査線に設定するステップ102を有する。ステップ104において、現在の走査線より下に残っている走査線が4（n）本未満であるかをチェックする。4（n）本未満ではない場合、ステップ106において、現在の走査線のアドレスカウンタを4（n）だけ小さくする。
【００１９】
ステップ108において、カーソルアドレスカウンタを、現在の走査線の最初の、すなわち最も左のピクセルに設定する。ステップ110において、カーソルの右側に存在しているピクセルが4（m）個未満であるかをチェックする。4（m）個未満である場合、制御はステップ104に戻る。4（m）個未満ではない場合、ステップ112において、カーソルアドレスカウンタを4（m）だけ右に進める。ステップ114において、カーソルピクセルが右下角である、例えば、4×4（n×m）のピクセル行列を選択する。
【００２０】
ステップ116において、選択されたピクセル行列の4つのピクセル差（デルタ）の値、すなわち、左デルタ、左上デルタ、上デルタ、および右上デルタを計算する。4つのデルタ演算の結果としての各デルタ行列ごとに1つの評価測度を計算する。評価測度が最良（最小）であるデルタ行列を選択する。どのデルタ行列が選択されたかを示す目的で、1つのマーカーを追加する。元の行列を、選択されたデルタ行列とそのマーカーとに置き換える。マーカーにハフマン符号化を適用する。
【００２１】
ステップ118において、現在の走査線より下の残りの走査線と一番上の走査線とに、ピクセル左デルタ計算を適用する。ピクセル左デルタ計算では、走査線全体のピクセル値が一番左のピクセルを除いて置き換わる。各ピクセルは、そのピクセルの値とすぐ左隣のピクセルの元の値との差に置き換えられる。ステップ122において、ランレングス符号化を適用する。例えば、0,0,0,0,1,1,1,1,2,2,2,2など、ピクセル値において連続する一連の同じ数が存在する場合、これは一連のタプル(4,0),(4,1),(4,2)として符号化される。この場合、最初の整数は、二番目の整数が重複している回数を示す。次いで、ステップ124において、結果のフレーム全体の各ピクセルに対してハフマン符号化を行う。
【００２２】
本発明の方法の実施例においては、左デルタ演算は、ピクセル値が元の行列から計算される4×4（n×m）の行列を戻す。元の行列の各ピクセルについて、現在のピクセル値と左隣のピクセル値との間の差を計算する。
【００２３】
左上デルタ演算は、ピクセル値が元の行列から計算される4×4（n×m）の行列を戻す。元の行列の各ピクセルについて、現在のピクセル値と斜め左上の隣接ピクセル値との間の差を計算する。
【００２４】
上デルタ演算は、ピクセル値が元の行列から計算される4×4（n×m）の行列を戻す。元の行列の各ピクセルについて、現在のピクセル値と上隣のピクセル値との間の差を計算する。
【００２５】
右上デルタ演算は、ピクセル値が元の行列から計算される4×4（n×m）の行列を戻す。元の行列の各ピクセルについて、現在のピクセル値と斜め右上の隣接ピクセル値との間の差を計算する。
【００２６】
ハフマン符号化は、ハフマンツリーを構築するステップと、ハフマンツリーに基づいて符号化するステップとを有する。ハフマンツリーの構築には、相当な時間がかかる。各画像フレームごとにハフマンツリーを作成すると、計算時間が長すぎてアルゴリズムがリアルタイムで動作しない。MPEGなどの圧縮手法では、ハフマン符号化を使用しているが、ビデオ全体に対して1つのハフマンツリーを使用している。このことは、多くの場合において、圧縮比が下がるため満足な結果が得られない。
【００２７】
本発明では、ハフマンツリーを周期的に作成する。1つの手法では、一定の数のフレームごとにハフマンツリーを一回作成する。ツリー生成の頻度は、フレームあたりのツリー生成の計算時間が符号化時間の約1／10になるように計算される。
【００２８】
もう1つの手法は、適応手法である。コンピュータが高速であり多数のサイクルが残っている場合には、ハフマンツリー生成をより頻繁に実行し、より良好な圧縮比を得る。本発明では、入力バッファを調べることによってこの問題に対処している。入力バッファが空またはほぼ空になっているときには、圧縮システムがビデオ入力に追いついており、従って、ツリー生成など別のことを行うための処理時間が残っていることを意味する。本発明のアルゴリズムでは、入力バッファのサイズを調べ、サイズがしきい値より小さい場合、ハフマンツリーの生成を行う。
【００２９】
図2は、本発明の単純な高速前処理最良隣接圧縮方法の実施例を示しており、この方法は、本明細書においては参照番号200によって表されている。方法200は、方法100に類似しているが、左デルタと上デルタを計算するのみである。
【００３０】
方法200によって圧縮する一般的なビデオストリームは、一連のビデオフレームを有し、各ビデオフレームは、複数の走査線を有し、各走査線は、複数のピクセルを含んでいる。方法200は、現在の走査線のアドレスカウンタをフレームの一番上の走査線に設定するステップ202を有する。ステップ204において、現在の走査線より下に残っている走査線が4（n）本未満であるかをチェックする。残っていない場合、ステップ206において、現在の走査線のアドレスカウンタを4（n）だけ小さくする。
【００３１】
ステップ208において、カーソルアドレスカウンタを、現在の走査線の最初の、すなわち最も左のピクセルに設定する。ステップ210において、カーソルの右側に存在しているピクセルが4（m）個未満であるかをチェックする。存在している場合、制御はステップ204に戻る。存在していない場合、ステップ212において、カーソルアドレスカウンタを4（m）だけ右に進める。ステップ214において、カーソルピクセルが右下角である、例えば、4×4（n×m）のピクセル行列を選択する。
【００３２】
ステップ216において、選択されたピクセル行列の2個のピクセル差（デルタ）の値、すなわち左デルタと上デルタを計算する。2つのデルタ演算の結果としての各デルタ行列ごとに1つの評価測度を計算する。評価測度が最良（最小）であるデルタ行列を選択する。どのデルタ行列が選択されたかを示す目的で、1つのマーカーを追加する。元の行列を、選択されたデルタ行列とそのマーカーとに置き換える。マーカーにハフマン符号化を適用する。
【００３３】
ステップ218において、現在の走査線より下の残りの走査線と一番上の走査線とに、ピクセル左デルタ計算を適用する。ステップ222において、ランレングス符号化を適用する。ステップ224において、フレーム全体の各走査線に対してハフマン符号化を行う。
【００３４】
ステップ116とステップ216に関して言及した評価測度は、結果としての4×4（n×m）デルタ行列におけるすべてのピクセルの絶対値の合計に等しいことが好ましい。ピクセルがフレームの縁に位置しているためにそれらのピクセル値の差を計算できない場合、評価値は存在しないかまたは示されない。以下では、表Iに示されている圧縮の例について検討する。
表I
圧縮の例
2006526367.tif 000003
【００３５】
表IIは、処理すべき第1の行列を示している。
表II
第1の行列
2006526367.tif 000004
【００３６】
第2行第2列には、現在値17が存在している。左デルタは、17−12＝5と計算される。左上デルタは、17−14＝3と計算される。上デルタは、17−18＝−1と計算される。右上デルタは、17−22＝−5と計算される。16個の現在のピクセル位置のそれぞれについて同様に計算し、左デルタ行列、左上デルタ行列、上デルタ行列、右上デルタ行列を生成する。完成した左デルタ行列では、表IIにおける第1の行列の評価測度としてnil（無効）が得られる。左上デルタ行列の計算からも、評価測度nil（無効）が得られる。
【００３７】
上デルタ行列では、表IIIに示すように、結果として評価測度は32となる。
表III
上デルタ行列
2006526367.tif 000005
【００３８】
右上デルタ行列では、表IVに示すように、結果として評価測度は83となる。
表IV
右上デルタ行列
2006526367.tif 000006
【００３９】
従って、評価速度の比較から、第1の4×4ピクセル行列については上デルタ(A)が最良であることが示される。表Vは、第2の行列を示している。
表V
第2の模範的な4×4行列
2006526367.tif 000007
【００４０】
このような第2の行列の左デルタ行列では、表VIに示すように、結果として評価測度が45である。
表VI
左デルタ行列
2006526367.tif 000008
【００４１】
左上デルタ行列では、結果として評価測度が58である。
表VII
左上デルタ行列
2006526367.tif 000009
【００４２】
上デルタ行列では、結果として評価測度が51である。
表VIII
上デルタ行列
2006526367.tif 000010
【００４３】
右上デルタ行列では、結果として評価測度がnil（無効）である。
【００４４】
従って、評価速度の比較から、第2の4×4ピクセル行列については左デルタ(L)が最良であることが示される。表IXは、第1の走査線のピクセル左デルタを示している。
表IX
第1の走査線のピクセル左デルタ
2006526367.tif 000011
【００４５】
表Xは結果を示している。
表X
結果
2006526367.tif 000012
【００４６】
隣接行列マーカーは次のとおりである。
2006526367.tif 000013
【００４７】
ハフマン圧縮処理の結果として、表XIのハフマンツリーが得られる。
表XI
ハフマンツリー
2006526367.tif 000014
この例の圧縮比は、(200-133)/200=34%である。
【００４８】
一般的には、本発明の方法の実施例では、隣接するピクセルとのピクセル値の差を比較し、いくつかの差のうち最小の差にピクセル値を置き換える。ブロック内のすべてのピクセルが一方向の隣接ピクセルと比較されるように、ピクセルのブロックにはマーカーが付される。マーカーは、そのブロック内のすべてのピクセルの比較方式を示す。
【００４９】
ハフマンツリーは、周期的に構築する。ハフマン符号化を使用して、結果のフレームを圧縮する。q個のフレームごとに1つのハフマンツリーを一回構築する。フレームは頻繁には変化しないため、qは30に設定することができ、その場合にもそれに起因して圧縮比が大きく下がることはない。リアルタイムのビデオ圧縮に使用するとき、ハフマンツリーの構築の頻度は、構築を実行するためのプロセッサ時間の瞬間的な可用性に従って選択する。より多くの処理時間が利用可能であるときには、ハフマンツリーをより頻繁に計算する。頻度の変動は、最初に入力ビデオフレーム用のバッファをチェックすることによって実施する。フレームバッファが空である場合、ハフマンツリーを構築する目的にプロセッサ時間が利用可能である。
【００５０】
画像のロスレス圧縮は、画像の色と明るさは表面的には徐々に変化するため、隣接するピクセルの値は大きくは変化しないという事実を利用して実施されている。言い換えれば、画像データは完全に任意なものではなく、各ピクセルは隣接するピクセルによって制約されている。
【００５１】
多くの圧縮方法は、差分パルス符号変調(DPCM)に基づいており、この変調方式では、走査線におけるあるポイントより前に位置するピクセルの何らかの線形関数から「予測子」を作成する。実際のピクセル値を、その実際のピクセル値と予測子との間の差に置き換える。予測子は、すぐ前のピクセルの値に等しいことがしばしばある。この方式では、画像のピクセル値全体が0に近く、より少ないビットを使用してピクセルを表すことによって圧縮するか、またはハフマン符号化を使用して圧縮することができる。
【００５２】
各ピクセルごとにマーカーを割り当てると、そのようなマーカーに必要なデータの合計量は、相当な量、例えば全体の1/4にもなりうる。このオーバーヘッドは、画像を複数の小さなn×mのブロックに分割することによって大幅に低減することができる。ブロック内のすべてのピクセルに対して1つのマーカーを割り当てる。この1つのマーカーは、各ブロックに付加され、4つの比較方式のうちどれが選択されているかを示す。各ブロック内のすべてのピクセルが、それぞれの隣接するピクセルと単一の方式で比較される。ブロックの形状および大きさは、任意の形式をとることができる。本発明の1つの実施例においては、n×mのブロックのサイズは、4×4の正方行列として設定されている。
【００５３】
ピクセルの絶対値のすべてを前処理して、小さな数の差値に低減した後、ハフマン符号化を使用してフレームを圧縮する。しかしながら、ビデオのハフマン符号化は、時間がかかることがある。ハフマン符号化は2つの段階、すなわち、符号化のためのハフマンツリーを作成する段階と、次いでピクセルを符号化する段階とから成る。第一段階のハフマンツリー生成の処理時間は、画像全体を符号化するのに要する第二段階の時間と同じ程度必要となることがある。本発明では、時間を低減する目的で、いくつかのフレームに対してツリー生成を一回実行する。連続するフレームの間で画像は大きくは変化しないため、このことによって圧縮比が大きく下がることはない。
【００５４】
ハフマンツリーの生成の頻度を設定する目的には、二種類の方式として固定方式と可変方式を使用することができる。一定数のフレーム、例えば30のフレームで1つのハフマンツリーを共有するようにすることができる。可変方式では、その時点において利用可能なプロセッサパワーに従ってハフマンツリーを生成する。プロセッサパワーの可用性は、入力バッファ内の圧縮する必要のあるエントリの数を調べることによって評価する。圧縮ジョブがほとんどまたはまったくなければ、より多くの時間を使用してハフマンツリーをより頻繁に生成できることを意味する。
【００５５】
ハフマンツリーを使用して、入力ビデオストリームにおける各符号をハフマン符号に変換する。ハフマン符号は可変長符号であり、頻繁に出現する入力符号に対しては長さが短く、出現頻度の小さい入力符号に対しては長い。
【００５６】
特定のハフマン符号ツリーの場合に、より小さな出力ファイルを生成できるならば、そのハフマン符号ツリーはそれ以外のハフマン符号ツリーよりも効率的であると考えられる。入力ビデオの統計的分布が既知である場合、非常に効率的なハフマン符号ツリーを作成することができる。しかしながら、リアルタイムの圧縮システムの場合、ビデオ全体における符号の分布を推定することはできない。1つの方法は、ほとんどの入力ファイルに対して有効に機能する所定のハフマン符号ツリーを使用することである。しかしながら、この方法は、特殊な場合にはうまく機能しないことがある。最適な方法は、各フレームに対してハフマン符号ツリーを作成することであるが、その場合には計算時間がかかりすぎる。
【００５７】
本発明は、ビデオの性質、すなわちフレームのコンテンツは非常に頻繁には変化しないという性質を前提としている。本発明では、最初のいくつかのフレームについて符号の統計的分布をとった後、ハフマン符号ツリーを作成する。ハフマン符号ツリーは、入力ビデオ全体に適用することができるが、全体に適用すると、この場合も、ビデオの別の部分についてはうまく機能しないことがある。その代わりに、本発明では、最初のいくつかの（走査済みの）フレーム、例えば3つのフレームからハフマン符号ツリーを作成し、そのハフマン符号ツリーを適用して、一連の、例えば20の（符号化する）フレームを変換する。この方法を使用すると、ハフマン符号ツリーの生成に必要な時間長を、長い期間にわたる平均値として、計算にとって大きな負荷ではない時間長にすることができる。
【００５８】
図3を参照する。本発明では、ファイル全体について一定である2つの数（走査するフレームと符号化するフレーム）を維持するか、または、ハフマン符号ツリーに適用するフレームの数を変化させることができる。本発明では、カウンタを使用して、符号化するフレームの数を数える（301）。本発明では、最初に走査プロセスを実行する。走査プロセスでは、scanFrameの数だけフレームを走査し、フレームにおける符号に対して統計的分布を実行する（302,303,304,305）。ScanFrameは、この例においては3である。
【００５９】
走査したフレームの統計的分布を使用して、ハフマンツリーを作成する（306）。このハフマンツリーを、伸長段階時に取得できるように出力ストリームに格納する（307）。本発明では、ハフマンツリーを使用して、走査する一連のフレームが含まれる一連のcodedFramesにおける符号を変換し、結果のハフマン符号を出力ストリームに格納する（308,309,310,311）。この例におけるCodedFramesは、20に等しい。
【００６０】
本発明では、ビデオにおけるすべてのフレームが変換されるまで（314）、ビデオにおけるフレームのすべて（totalFrames）についてこのプロセスを繰り返す（312，313）。
【００６１】
図4を参照する。圧縮比が小さくなった場合、その原因として、シーンが変化して、フレームにおける符号の統計値が大幅に変化したことが考えられる。本発明では、この状況が起きたときに符号ツリーを再作成する。図3の場合と同様に、本発明では、カウンタを使用して、符号化するフレームの数を数える（401）。本発明では、走査プロセスを実行する。走査プロセスでは、scanFrameの数だけフレームを走査し、フレームにおける符号に対して統計的分布を実行する（402,403,404,405）。ScanFrameは、この例においては3である。
【００６２】
走査したフレームの統計的分布を使用して、ハフマンツリーを作成する（406）。このハフマンツリーを、伸長段階時に取得できるように出力ストリームに格納する（407）。本発明では、ハフマンツリーを使用して、走査する一連のフレームが含まれる一連のcodedFramesにおける符号を変換し、結果のハフマン符号を出力ストリームに格納する（408,409,410,411,413）。この例におけるCodedFramesは、200に等しい。
【００６３】
フレームの圧縮比がしきい値（一般には0．7）より小さくなると（ほとんどの場合はシーンが変化したことを示す）、本発明では、currentFrameを次のフレームに設定し（412）、走査プロセスに戻って（402,403,404,405）、新しいハフマンツリーを作成する（406,407）。
【００６４】
本発明では、ビデオにおけるすべてのフレームが変換されるまで（416）、ビデオにおけるフレームのすべて（totalFrames）についてこのプロセスを繰り返す（414，415）。
【００６５】
高速な符号化のため、ルックアップテーブルを使用してハフマン符号を符号化する。しかしながら、ハフマンアルゴリズムでは短い符号を可変長符号に変換するため、符号によっては非常に長くなることがある。一般には、入力符号の長さが8ビットである場合、生成されるハフマン符号の最大長さは約30ビットである。本発明では、符号化は、表XIIに実例を示すように8ビットの入力符号用の256個のエントリのルックアップテーブルを使用して、相対的に単純な方法において実施する。
表XII
256個のエントリを有するハフマン符号符号化テーブル
2006526367.tif 000015
【００６６】
これに対して、復号化は、長い符号用のルックアップテーブルを実装することができないため、より複雑であり時間がかかる。ハフマン符号の最大長さが30ビットである場合、エントリ数が10億個のテーブルを作成しなければならず、これは、最新のコンピュータのメインメモリにおいても現実的ではない。
【００６７】
ほとんどのハフマン復号化では、メインメモリに収めることと実行速度を高めることとを目的として、符号を2つの部分に分割する。2つの部分とは、固定長の接頭部と可変長の残余部である。本発明では、表XIIIに実例を示したように、固定長の接頭部をルックアップテーブルのインデックスとして使用する。
【００６８】
いくつかのレベルのメモリ階層を有する最新のコンピュータを使用する場合、キャッシュメモリと称される最も高速のメモリにルックアップテーブルを格納することが望ましい。一般的なパーソナルコンピュータは、256 Kバイトのキャッシュメモリを有し、このことは、本発明において11ビットの大きさ（この数値はコンピュータが進歩し、より大きなキャッシュサイズが一般的になるにつれて変わりうる）の接頭部を使用できることを意味する。ハフマン符号化の性質、すなわち、頻繁に出現する入力符号ほど短い出力符号が割り当てられるという性質のため、多くの符号は11ビットに収まる。
表XIII
2048個のエントリを有するハフマン符号復号化テーブル
2006526367.tif 000016
【００６９】
しかしながら、符号が11ビットに収まらない場合、符号の残りは残余部に残される。残余部の変換を扱うための一般的な方法は、検索テーブルを使用することである。第1のルックアップテーブルのエントリは、特定の接頭部で始まる出力符号が11ビットより長い場合、別のテーブルを指す。表XIVに実例を示したこのオーバーフローテーブルにおいては、エントリは、一対の数値、すなわち残余部とターゲット符号である。符号が11ビットより長いことが第1のルックアップテーブルによって示される場合、残余部を比較インデックス(comparison index)（または対応ルックアップ）としてオーバーフローテーブルを検索する。合致するエントリが存在する場合、対応するターゲット符号を出力する。しかしながら、これは非常に時間がかかる。従って、一般には、ハッシュテーブルを使用して検索を高速化する。
表XIV
オーバーフロー検索テーブルA
2006526367.tif 000017
【００７０】
ハッシュテーブルが遅い(slow)場合にも、何度かの探索が必要である。従って、ハッシュテーブルは本発明の目的には適していない。その代わりに、本発明では、連結符号を使用する。ハフマン符号を生成するとき、出力が11ビットより長い場合、結果は、11ビットの接頭部と8ビットの入力符号とを連結することによって作成される19ビットの符号である。復号化テーブルのエントリは、接頭部が11ビットに等しいか11ビット未満である場合における接頭部の長さと8ビットの出力符号、または符号が11ビットより長いことを示すインジケータ、のいずれかである。表XVは、復号化テーブルの実例を示している。
表XV 
2048個のエントリを有する連結符号用の復号化テーブル
2006526367.tif 000018
【００７１】
図5および図6には、本発明の連結符号ハフマン復号化方法が示されている。本発明では、currentBitポインタ502を使用して（601）ストリームの中を移動することによって、入力ストリーム501を処理する。currentBitとそれに続く10ビットとを使用して、入力ストリーム501から符号を計算する（602）。表XVに示されている復号化テーブル（decodeTable）を使用し、計算された符号を探索し、符号におけるビットの数を見つける（603）。
【００７２】
ビットの数が19である場合、本発明では、入力ストリーム内をインデックス化することによって8ビットの入力符号をとり、その符号を出力ストリームに付加する（605,606,607,610）。ビットの数が19でない場合、符号化テーブル（decodeTable）から出力符号をとり、その出力符号を出力ストリームに付加する（608,609,610）。
【００７３】
入力ストリーム501の中のビットがすべて処理されるまで（612）、このプロセスを繰り返す（611）。
【００７４】
図7を参照すると、本発明の一連のタスクが示されている。圧縮側においては、ビデオキャプチャタスク701が、圧縮すべきビデオストリームをキャプチャする。このビデオストリームは、図1および図2に関連して上述されているようにビデオの前処理を行うビデオ高速前処理タスク702に送られる。ビデオにおけるフレームが前処理されると、図4および図5に関連して上述されているようにビデオを圧縮するビデオ圧縮タスク703に渡される。ビデオ圧縮タスク703は、使用されたハフマンツリーを圧縮された出力ストリームに格納し、出力ストリームをハードディスク704に格納する。
【００７５】
伸長側においては、圧縮されたビデオストリームが送られて伸長されるとき、圧縮ビデオキャプチャタスク705は、入力ストリームをキャプチャする。圧縮ビデオキャプチャタスク705から入力ストリームがビデオ伸長タスク706に渡される。ビデオ伸長タスク706は、図6に関連して上述されているように入力ストリームを伸長し、伸長されたビデオストリーム707を出力する。
【００７６】
ビデオのフレームサイズが大きい、またはフレームレートが高いときには、ビデオのデータレートが非常に大きくなることがあり、CPUのパワーが不足して各フレームの圧縮および伸長を行うことができないことがある。そのような場合、本発明では、入ってくるビデオデータにCPUが追いつくことができるように、所定の期間の間、フレームを圧縮しない。
【００７７】
選択的な圧縮には2つの方法がある。1つの方法は、一定の頻度において圧縮することである。例えば、本発明では、1つおきのフレームを圧縮する、または、2つのフレームを圧縮して3つ目のフレームには何もせず、次の2つのフレームを圧縮することができる。
【００７８】
図8に関連して、本発明において使用する別の方法は、適応可能なシステムである。本発明では、十分なCPUリソースが残っているときにフレームを圧縮する。本発明では、入力フレームのバッファ802を維持することによってCPUの可用性を測定する。このバッファ802は、ビデオ高速前処理タスク801とビデオ圧縮タスク803との間に配置されている。バッファ802の中のフレームの数がしきい値（例：5）より大きくなった場合、ビデオ圧縮タスク803はフレームの圧縮を省略し、バッファ802の中のフレームをただちにディスク804に書き込む。バッファのサイズが0になるか、または第2のしきい値より小さくなると、ビデオ圧縮タスク803は、フレームの圧縮を再び開始する。
【００７９】
本発明は、本明細書においては好ましい実施例を参照しながら説明されているが、本発明の精神および範囲から逸脱することなく、本明細書に記載されているものに代えて別のアプリケーションを適用できることが、当業者には容易に理解されるであろう。従って、本発明は、請求項によってのみ制限されるものとする。
【図面の簡単な説明】
【００８０】
【図１】本発明のビデオデータ圧縮の実施例のフローチャートであって、画像が水平帯域、垂直帯域、および/または対角帯域を有する場合に4つのデルタ計算を使用してパフォーマンスを向上させるフローチャートである。
【図２】本発明のビデオデータ圧縮の実施例のフローチャートであって、画像が水平帯域および/または垂直帯域を有する場合に2つのデルタ計算を使用してパフォーマンスを向上させるフローチャートである。
【図３】本発明に従って、一連のフレームからの統計的分布を使用してハフマンツリーを作成し、より長い一連のフレームにそのハフマンツリーを適用することによって、入力ビデオストリームのフレームを符号化する、フローチャート、のブロック線図である。
【図４】本発明に従って、一連のフレームからの統計的分布を使用してハフマンツリーを作成し、より長い一連のフレームにそのハフマンツリーを適用し、圧縮比が特定のしきい値より下がったときに別のハフマンツリーを作成することによって、入力ビデオストリームのフレームを符号化する、フローチャート、のブロック線図である。
【図５】本発明による入力ストリームおよび現在のビットのポインタのブロック線図である。
【図６】本発明による、連結符号手法と復号化テーブルとを使用して入力ストリームのフレームを復号化するフローチャート、のブロック線図である。
【図７】本発明の一連のタスクのブロック線図であり、本発明による圧縮段階および伸長段階を示している。
【図８】本発明による選択的圧縮方式のブロック線図である。
【符号の説明】
【００８１】
501  入力ストリーム
502  currentBitポインタ
701  ビデオキャプチャタスク
702  ビデオ高速前処理タスク
703  ビデオ圧縮タスク
704  ハードディスク
705  圧縮ビデオキャプチャタスク
706  ビデオ伸長タスク
801  ビデオ高速前処理タスク
802  バッファ
803  ビデオ圧縮タスク
804  ディスク
【図１】
2006526367.tif 000019
【図２】
2006526367.tif 000020
【図３】
2006526367.tif 000021
【図４】
2006526367.tif 000022
【図５】
2006526367.tif 000023
【図６】
2006526367.tif 000024
【図７】
2006526367.tif 000025
【図８】
2006526367.tif 000026
【国際調査報告】
2006526367.tif 000027
2006526367.tif 000028