(57)【要約】      （修正有）【課題】ブロック適応時空間分散型ディザを用いる固定バジェットフレームバッファ圧縮。【解決手段】デジタル表現又はフレームをブロック化し、特別処理の対象になっていないブロックの各画素値とブロックの最小値との差を適応分散型ディザを用いて符号化することでビデオデータを圧縮するコーデック。フレームからフレームにディザ行列を変えることでより高度な出力品質を得ることができる。ビットをさらに節約するために、そのブロックの最大画素値と最小画素値との差が定義済みしきい値に満たないブロックである定ブロック（全ての画素が最大ブロック値か最小ブロック値かどちらかの所定の範囲内にあるブロックをバイナリ型ブロックと呼ぶ）は符号化の仕方を変え単一ビットで符号化する。圧縮出力の固定ビットバジェットに合わせて総体的なコード構成(coding scheme)をさらに修正変更することができる。【選択図】図８
2005354684.tif 000002
【特許請求の範囲】
【請求項１】
データを圧縮するための方法であって、
入力表現又はフレームを複数のブロックにタイル化するステップ（a）と、該ステップ(a)において前記複数のブロックは複数の画素を各々含み、該複数の画素は値を各々有するものであり、
前記入力表現又はフレームのブロック毎に最大画素値及び最小画素値を判定及び格納するステップ（b）と、
前記入力表現又はフレームの選ばれたブロックについて、圧縮された出力を生成するために、ある所与のブロックの画素の値を、そのブロックについて判定された最大又は最小画素値に基づいて適応分散型ディザを用いて符号化するステップ（c）とを含む、方法。
【請求項２】
前記符号化ステップ（c）において、ある所与のブロックの画素毎に、その画素の値とそのブロックの最小画素値との差を適応分散型ディザを用いて符号化する、請求項１に記載の方法。
【請求項３】
適応分散型ディザを用いたある所与のブロックの画素の値の符号化は、
適応分散型ディザを実行するビット深度bを判定するステップと、
所与のブロックの各画素値を再スケーリングするステップと、
所与のブロックの再スケーリングされた各画素値を２個のディザ処理されたbビット値の一つとして表現するステップとを含む請求項２に記載の方法。
【請求項４】
入力表現又はフレームのブロック毎に、ブロックの最大画素値と最小画素値との差が定義済みしきい値に満たないかどうか判定するステップと、
最大画素値と最小画素値との差が定義済みしきい値に満たないと判定されたブロックについては各々、符号化のステップ（c）をスキップするステップとをさらに含む、請求項２に記載の方法。
【請求項５】
入力表現又はフレームのブロック毎に、そのブロックの全ての画素がそのブロックの最大画素値又は最小画素値の所定の範囲内にあるかどうか判定するステップと、
全ての画素がそのブロックの最大又は最小画素値の所定範囲内にあるブロックについては各々、符号化ステップ（c）をスキップするステップとをさらに含む、請求項２に記載の方法。
【請求項６】
全ての画素がブロックの最大又は最小画素値の所定範囲内にあると判定されたブロックについては各々、そのブロックの画素を各々単一ビットで符号化してなる、請求項５に記載の方法。
【請求項７】
生成された圧縮出力はビットバジェットによって束縛され、適応分散型ディザを用いた所与のブロックの画素の値の符号化は、
ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出するステップと、
適応分散型ディザを行なう推奨ビット深度を判定するステップと、
ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てと前のブロックの符号化から利用できる節約されたビットとを足した値を超える場合には、推奨ビット深度を低下させるステップと、
推奨ビット深度を下げたブロック毎にそのブロックについて算出され、低くなったビット深度で各ブロックに適応分散型ディザを実施する一方、推奨ビット深度を下げなかったブロックについては推奨ビット深度で適応分散型ディザを実施するステップとを含む、請求項１に記載の方法。
【請求項８】
生成された圧縮出力はビットバジェットによって束縛され、適応分散型ディザを用いた所与のブロックの画素の値の符号化は、
ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出するステップと、
適応分散型ディザを行なう推奨ビット深度を判定するステップと、
現ブロックがビットを借用できるこれから符号化されるブロック数を指定する水平線パラメータを定義するステップと、
水平線パラメータ内でこれから符号化される全てのブロックから所与のブロックが利用できるビット数を計算するステップと、
ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足した上さらに水平線パラメータ内でこれから符号化される全ブロックからそのブロックが利用できるビット数を足した値を越える場合には、推奨ビット深度を低下させるステップと、
推奨ビット深度を下げたブロック毎に、そのブロックについて算出された低くなったビット深度で各ブロックに適応分散型ディザを実施する一方、推奨ビット深度を下げなかった各ブロックについては、推奨ビット深度で適応分散型ディザを実施するステップとを含む、請求項１に記載の方法。
【請求項９】
前記入力表現又はフレームの選ばれたブロックは、前記入力表現又はフレームの全ブロック又は全ブロックの部分集合からなる、請求項１に記載の方法。
【請求項１０】
データを圧縮するように構成された装置であって、
（i）入力表現又はフレームを複数のブロックにタイル化するように構成され、複数のブロックは複数の画素を各々保有し、該複数の画素は値を各々有し、さらに（ii）入力表現又はフレームの各ブロックの最大画素値及び最小画素値を判定するように構成されたプロセッサと、
判定された最大及び最小画素値を格納するように構成されたメモリと、
圧縮された出力を生成するために適応分散型ディザを用いて、入力表現又はフレームの選ばれたブロックのうちのある所与のブロックの画素の値を、そのブロックについて判定された最大画素値又は最小画素値に基づいて符号化するように構成されたエンコーダとを含む、装置。
【請求項１１】
前記エンコーダはさらに、ある所与のブロックの画素毎に、その画素の値とそのブロックの最小画素値との差を適応分散型ディザを用いて符号化するように構成されている、請求項１０に記載の装置。
【請求項１２】
適用分散型ディザを用いて所与のブロックの画素の値を符号化する際に、エンコーダはさらに、
適応分散型ディザを実行するビット深度bを判定することと、
所与のブロックの各画素値を再スケーリングすることと、
所与のブロックの再スケーリングされた各画素値を２個のbビット値の一つで表現することとを行うように構成されている、請求項１１に記載の装置。
【請求項１３】
エンコーダはさらに、
入力表現又はフレームのブロック毎に、ブロックの最大画素値と最小画素値との差が定義済みしきい値に満たないかどうか判定することと、
（i）最大及び最小画素値の差が定義済みしきい値に満たないと判定されたブロックの各々について、又は（ii）全ての画素がそのブロックの最大又は最小画素値の所定の範囲内にあると判定されたブロックの各々について、符号化作業をスキップすることとを行うように構成されている、請求項１１に記載の装置。
【請求項１４】
エンコーダはさらに、全ての画素がそのブロックの最大又は最小画素値の所定の範囲内にあると判定されたブロックの画素を各々単一ビットで符号化するように構成されている、請求項１３に記載の装置。
【請求項１５】
生成された圧縮出力はビットバジェットによって束縛され、前記エンコーダはさらに、
ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出することと、
適応分散型ディザを実行する推奨ビット深度を判定することと、
ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足した値を超える場合には、推奨ビット深度を低下させることと、、
推奨ビット深度を下げた各ブロックにはそのブロックについて算出された低下したビット深度で適応分散型ディザを実施する一方、推奨ビット深度を下げなかった各ブロックについては推奨ビット深度で適応分散型ディザを実施することとを行うように構成されている、請求項１０に記載の装置。
【請求項１６】
生成された圧縮出力はビットバジェットによって束縛され、前記エンコーダはさらに、
ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出することと、
適応分散型ディザを実行する推奨ビット深度を判定することと、
現ブロックがビットを借用できるこれから符号化されるブロック数を指定する水平線パラメータを定義することと、
水平線パラメータ内でこれから符号化される全ブロックからある所与のブロックが利用できるビット数を計算することと、
ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足した上さらに水平線内でこれから符号化される全ブロックからそのブロックが利用できるビット数を足した値を超える場合には、推奨ビット深度を低下させることと、
推奨ビット深度を下げた各ブロックにはそのブロックについて算出された低下したビット深度で適応分散型ディザを実施する一方、推奨ビット深度を下げなかった各ブロックについては推奨ビット深度で適応分散型ディザを実施することとを行うように構成されている、請求項１０に記載の装置。
【請求項１７】
前記装置はコーデックである、請求項１０に記載の装置。
【請求項１８】
装置にデータを圧縮させるための命令プログラムを保有している装置可読媒体であって、プログラムは、
（a）入力表現又はフレームを複数のブロックにタイル化するための命令を有し、複数のブロックは複数の画素を各々保有し、複数の画素は値を各々有し、
（b）入力表現又はフレームの各ブロックの最大画素値及び最小画素値を判定及び格納するための命令を有し、
（c）圧縮された出力を生成するために、適応分散型ディザを用いて、入力表現又はフレームの選ばれたブロックのうち、ある所与のブロックの画素の値を、その画素について判定された最大又は最小画素値に基づいて符号化するための命令を有する、装置可読媒体。
【請求項１９】
符号化の命令（c）は、ある所与のブロックの画素毎に、その画素の値とそのブロックの最小画素値との差を適応分散型ディザを用いて符号化するための命令を有する、請求項１８に記載の装置可読媒体。
【請求項２０】
ある所与のブロックの画素の値を適応分散型ディザを用いて符号化するための命令は、
適応分散型ディザを実行するビット深度bを判定するための命令と、
所与のブロックの各画素値を再スケーリングするための命令と、
所与のブロックの再スケーリングされた各画素値を２個のディザ処理されたbビット値の一つとして表わすための命令とからなる、請求項１９に記載の装置可読媒体。
【請求項２１】
入力表現又はフレームのブロック毎に、ブロックの最大画素値と最小画素値との差が定義済みしきい値に満たないかどうか判定するための命令と、
最大画素値と最小画素値との差が定義済みしきい値に満たないと判定されたブロックの各々については符号化命令（c）をスキップするための命令とを、
さらに備える請求項１９に記載の装置可読媒体。
【請求項２２】
入力表現又はフレームのブロック毎に、そのブロックの全ての画素がそのブロックの最大画素値又は最小画素値の所定の範囲内にあるかどうか判定するための命令と、
全ての画素がそのブロックの最大又は最小画素値の所定範囲内にあると判定されたブロックについては符号化ステップ（c）を各々スキップするための命令とを、
さらに有する請求項１９に記載の装置可読媒体。
【請求項２３】
全ての画素がそのブロックの最大又は最小画素値の所定範囲内にあると判定されたブロックの画素を各々単一ビットで符号化するための命令をさらに有する、請求項２２に記載の装置可読媒体。
【請求項２４】
生成された圧縮出力はビットバジェットに束縛され、適応分散型ディザを用いてある所与のブロックの画素の値を符号化するための命令は、
ビットバジェットと符号化対象のブロック数とに基づいてブロック毎にビット割当てを算出するための命令と、
適応分散型ディザを実行するビット深度を判定するための命令と、
ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足した値を超える場合には、推奨ビット深度を下げるための命令と、
推奨ビット深度を下げた各ブロックにはそのブロックについて算出された低下させたビット深度で適応分散型ディザを実施する一方、推奨ビット深度を下げなかったブロック毎に推奨ビット深度で適応分散型ディザを実施するための命令とからなる、請求項１８に記載の装置可読媒体。
【請求項２５】
生成された圧縮出力はビットバジェットに束縛され、適応分散型ディザを用いてある所与のブロックの画素の値を符号化するための命令は、
ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出するための命令と、
適応分散型ディザを実行するビット深度を判定するための命令と、
現ブロックがビットを借用できるこれから符号化されるブロック数を指定する水平線パラメータを定義するための命令と、
水平線パラメータ内でこれから符号化される全てのブロックからある所与のブロックが利用できるビット数を計算するための命令と、
ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足した上さらに水平線パラメータ内でこれから符号化される全てのブロックからそのブロックが利用できるビット数を足した値を超える場合には、推奨ビット深度を低下させるための命令と、
推奨ビット深度を下げた各ブロックにはそのブロックについて算出された低下したビット深度で適応分散型ディザを実施する一方、推奨ビット深度を下げなかったブロック毎に推奨ビット深度で適応分散型ディザを実施するための命令とからなる、請求項１８に記載の装置可読媒体。
【請求項２６】
入力表現又はフレームの選ばれたブロックは、入力表現又はフレームの全ブロック又は全ブロックの部分集合からなる、請求項１８に記載の装置可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はフレームバッファでビデオデータを圧縮するためのブロックベースの技法に関する。この技法はビデオディスプレイコントローラといった装置にハードウェア又はソフトウェアとして実装することができる。
【背景技術】
【０００２】
コーデック（エンコーダとデコーダを一つの装置に組み立てたもの）はデータを圧縮及び解凍しなければならない大型装置の重要な構成要素である。コーデックにはビデオ、静止画像、及び／又は音声データのどれでも構わないデータを圧縮及び解凍するのに使用されるアルゴリズムを含んでいるので、プロセッサはそうしたデータを管理しやすい。ビデオ又はLCDディスプレイコントローラにおいて、コーデックはフレームレート及びサイズといったビデオ設定を定義すると共に、オーディオがサポートされていれば、オーディオ設定を品質ビット(bits of quality)として定義する。ほとんどのコーデックにはレートコントロールがあるので、コーデックを含んだ装置は使用可能なバンド幅に適応できる。そうした装置において、表示されたビデオの品質は関連付けられたコーデックの機能に一部分依存する。
【０００３】
表示解像度と大きさが増すと、内部にあるコーデックにかかる負担が大きくなる。そうした改善を実現するには、コーデックは大型の表示サイズと高い色深度をサポートできなければならない。コーデックが作動する資源（演算能力、表示バッファ配分など）が限られている携帯電話またはパーソナルデジタルアシスタント（PDA）といったハンドヘルドの環境において、コーデックにかかる負担はさらに大きくなるのが普通である。したがって、ハンドヘルドの環境で表示品質の改善をサポートするために、操作オーバーヘッドの低いコーデックに対する継続的なニーズがある。
【０００４】
【特許文献１】米国特許第6,625,327号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
そこで、本発明の目的は上記の問題を克服し、そうしたコーデックを提供することである。
【０００６】
本発明のもう一つの目的は、低計算量で作動し、所要メモリ量が小さなコーデックを提供することである。
【課題を解決するための手段】
【０００７】
本発明の一つの態様によれば、データを圧縮するための方法は、入力表現又はフレームを複数のブロックにタイル化するステップ（a）と、該ステップ（a）において前記複数のブロックは複数の画素を各々含み、該複数の画素は値を各々有するものであり、入力表現又はフレームの各ブロックの最大値と最小画素値を判定及び格納するステップ（b）と、入力表現又はフレームの選ばれたブロックについて、圧縮された出力を生成するために適応分散型ディザを用いて、ある所与のブロックの画素の値をそのブロックについて判定された最大又は最小画素値に基づいて符号化するステップ（c）とを含む。
【０００８】
入力表現又はフレームの選ばれたブロックは、入力表現又はフレームの全ブロック又は全ブロックの部分集合からなり得る。
【０００９】
符号化のステップ（c）で、ある所与のブロックの画素毎に、適応分散型ディザを用いて、その画素の値とそのブロックの最小画素値との差が符号化されるのが好ましい。一つのスキームで、適応分散型ディザを用いた所与のブロックの画素の値の符号化には、適応分散型ディザを実行するビット深度bを判定し、所与のブロックの各画素値を再スケーリングし、所与のブロックの再スケーリングされた各画素値を２個のディザ処理されたbビット値の一つとして表現することが含まれる。
【００１０】
この方法はさらに、入力表現又はフレームのブロック毎に、ブロックの最大画素値と最小画素値との差が定義済みしきい値に満たないかどうか判定し、最大画素値と最小画素値との差が定義済みしきい値に満たないと判定されたブロックの各々、又は全ての画素がそのブロックの最大又は最小画素値の所定範囲内にあると判定されたブロックの各々かどちらかについては、符号化ステップ（c）をスキップすることを含むことがある。後者の場合、全ての画素がそのブロックの最大又は最小画素値の所定範囲内にあると判定されたブロックの画素は各々単一ビットで符号化されるのが好ましい。
【００１１】
生成された圧縮出力がビットバジェット(a bit budget)で束縛されているときにこの方法を採用してもいい。一つのそうしたバジェット制約型構成において、適応分散型ディザを用いたある所与のブロックの画素の値の符号化は、ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出し、適応分散型ディザを実行する推奨ビット深度を判定し、ある所与のブロックについて、そのブロックの推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足した値を超える場合には、推奨ビット深度を下げ、推奨ビット深度を下げた各ブロックについては、そのブロックについて算定された低くなったビット深度で各ブロックに適応分散型ディザを実施する一方、推奨ビット深度が下げられなかった各ブロックについては、推奨ビット深度で適応分散型ディザを実施することからなる。別のバジェット制約型構成において、適応分散型ディザを用いたある所与のブロックの画素の値の符号化は、ビットバジェットと符号化対象のブロック数とに基づいてブロック毎のビット割当てを算出し、適応分散型ディザを実行する推奨ビット深度を判定し、現ブロックがビットを借用できるこれから符号化されるブロック数を指定する水平線パラメータを定義し、水平線パラメータの範囲内でこれから符号化される全てのブロックから所与のブロックが利用できるビット数を計算し、ある所与のブロックについて、そのブロックに推奨ビット深度を用いると、ブロックの算定割当てに前のブロックの符号化から利用できる節約されたビットを足したものにさらに水平線パラメータの範囲内でこれから符号化される全ブロックからそのブロックが利用できるビット数を足した値を超える場合には、そのブロックの推奨ビット深度を下げ、推奨ビット深度を下げた各ブロックについては、そのブロックについて算定された低くなったビット深度で各ブロックに適応分散型ディザを実施する一方、推奨ビット深度を下げなかった各ブロックについては、推奨ビット深度で適応分散型ディザを実施することからなる。
【００１２】
もう一つの態様において、発明はビデオデータを圧縮するように構成された装置を必要とする。コーデックであるこの装置は、（i）入力表現またはフレームを複数のブロックにタイル化し、複数のブロックは各々が複数の画素を保有し、複数の画素は各々が一つの値をもっており、（ii）入力表現又はフレームの各ブロックの最大画素値と最小画素値を判定するように構成されたプロセッサと、判定された最大及び最小画素値を格納すうように構成されたメモリと、圧縮された出力を生成するために適応分散型ディザを用いて、入力表現又はフレームの選ばれたブロックのうちのある所与のブロックの画素の値をそのブロックについて判定された最大又は最小画素値に基づいて符号化するように構成されたエンコーダとを備える。
【００１３】
エンコーダを、方法に関して先に説明した追加の処理を実行するように構成して構わない。
【００１４】
発明の更なる態様によれば、上記の方法又はそのステップを、実行するためにコンピュータやその他のプロセッサ制御型装置に格納又は伝達することができる命令プログラム（例えば、ソフトウェア）で実施することができる。もしくは、方法又はそのステップを機能的に等価なハードウェア（例えば、ASIC、デジタル信号処理回路機構など）またはソフトウェアとハードウェアとの組合せを用いて実施してもいい。
【００１５】
添付の図面と共に以下の説明並びに請求項を参照することにより発明をより深く理解できるようになると共に、発明のその他の目的及び成果が明らかになる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施形態を図面に基づいて説明する。
【実施例１】
【００１７】
A.  概要
発明は、ビデオ又はLCDディスプレイコントローラのフレームバッファでデータを符号化／復号化するように特に設計されている。この環境において、圧縮は、データ信号をテレビなどのディスプレイに出力できるようにNTSCといった別のドメインの信号に変換する前に行なわれるのが一般的である。本発明の圧縮／解凍技法は、高度のビジュアル品質を維持しながら、低計算量及び低メモリ量になるように設計されているので有益な効果がある。この技法はまた、自然画像を表現する良好な階調プロパティを有しながら、テキスト及び行の内容を高品質でぼやけを最小に抑えて表現するように設計されている。
【００１８】
本発明の圧縮／解凍技法をコーデック、つまり、エンコーダとデコーダを共に有する装置に組み入れることができるので都合がいい。コーデック自体は一般的にその機能の一つとしてデータ圧縮／解凍を実行する大型システム又は装置（例えば、ビデオ又はLCDコントローラ）の一部である。本発明の技法は特にビデオ又はLCDディスプレイコントローラに使用するように設計されてはいるけれども、限定されてはいない。発明の技法を圧縮／解凍を必要とする他のシステム／装置に組み入れてもいい。発明の完全な作用効果は圧縮及び解凍の両機能を有するシステム／装置で実現されるけれども、当業者ならば発明の特定の態様をエンコーダだけで或いはデコーダだけで実現して構わないことを理解するだろう。
【００１９】
図１において、ビデオディスプレイコントローラ１２に実施されたコーデック１１の詳細な概略図は、発明の原理に従って作動するように構成されている。コーデック１１のエンコーダ部は、デジタルカメラ、デジタルカムコーダ、デコーダなどといった様々なデジタルソースを出所として入ってくるデジタルデータに操作を行なう。アナログ-デジタル変換器でデジタルデータに変換された後、様々なソースからのアナログデータも受け取れる。
【００２０】
圧縮するためのデータを用意するプレプロセッサ１３がデジタルデータを受け取る。基本的に、プレプロセッサ１３は、必要ならば、符号化の対象となる画素数を減らし、残りの画素を符号化に最も適したフォーマットに配列する。プレプロセッサ１３は次の操作のどれでも行なうことができる。必要ならば、圧縮に最も適した色フォーマット、例えば、YUVへの変換操作、ブランキング間隔中に集めたデジタルビットの除去操作、適切ならば、インタリーブ方式からプログレッシブ走査フォーマットへの変換操作、及び／又は解像度を調整する、フレームレートを下げるなどのために、符号化の前に、しかるべく、データ又はその成分をアップサンプリング又はダウンサンプリングする操作。
【００２１】
前処理済みデジタルデータはそれからフレームバッファ１４のフレームに格納されて、圧縮されるのを待つ。エンコーダ１５はフレーム単位でデータをフェッチし、以下に説明するように各カラープレーン又はチャネルを符号化する。エンコーダ１５の出力はバッファ１６にバッファリングされ、圧縮が進行している間様々な画像成分は保持される。圧縮されたフレームはそれから、伝送及び／又は格納できるように、伝送エンコーダ１７で標準ビデオストリーム１８にアセンブルされるのが一般的である。伝送／格納は、テレビに出力できるように、エンコーダ出力のNTSCといった別のドメインの信号への変換前または変換後に行なって構わない。
【００２２】
復号化のプロセスは逆に機能し、オリジナルビデオデータストリームの近似表現を復元するために逆の操作を行なう。符号化されたビデオストリーム２１は伝送デコーダ２２によって処理され、復号化より前にバッファ２３に格納される。デコーダ２４はエンコーダの操作を反転させた動作を行なう。ビデオポストプロセッサ２６が出力できるように復号化された(decompressed)デジタルデータ２７をリフォーマットしているときに、デコーダ２４の出力はバッファ２５に一時格納される。
【００２３】
図１の実施例において、バッファ１６及び２３、伝送エンコーダ１７、伝送デコーダ２２はそれぞれビデオコントローラ１２の外にあるとして示している。これは一つの構成にしかすぎない。他の構成において、これらの構成要素をビデオコントローラ１２の一部分として含めても構わない。どちらの場合にもビデオコントローラ１２は単一の集積回路で構わない。
【００２４】
ここで、エンコーダ１５及びデコーダ２４の機能の詳細を説明する。
【００２５】
B.  エンコーダ
例証のために、エンコーダ１５が行なう圧縮プロセスを、例えば、１色につき８ビットの単一カラープレーン(color plane)について説明する。複数のカラープレーンを含んでいる画像又はフレームの場合、追加のカラープレーンに対してもプロセスを行なうことができる。多色のビデオ又は画像（例えば、YUVデータ）の場合、各カラーチャネル又はプレーンに対して個別に以下に説明する符号化操作を行なう。
【００２６】
図２と図３はそれぞれ、多色の画像を表わす入力画像２１とその入力画像のY成分３１を示している。符号化操作をYUV色空間における多色画像のYチャネル又はY成分に関して以下に説明する。処理対象のカラー画像がYUV色空間にない場合には、公知の色変換方法を用いて先ずその色空間に変換される。
【００２７】
図４において、入力画像／フレームのY成分３１がblockWidth × blockHeightの次元をもつ画素ブロックにタイル化されてタイル状の画像／フレーム３２が生まれる。ブロック毎に、最大画素値と最小画素値が判定され格納される。一つの実施例において、最大及び最小画素値はY成分Block-Maximum画像３３とY成分Block-Minimum画像３４にそれぞれ格納されるが、フレームバッファ１４に或いはビデオコントローラ１２と通信している容易にアクセス可能な他のメモリに格納しても構わない。Block-Maximum画像３３の拡大版を図５に示し、Block-Minimum画像３４の拡大版を図６に示した。Block-Maximum画像及びBlock-Minimum画像の各々の次元はblockWidth及びblockHeightという因子によって水平方向及び垂直方向の次元がそれぞれ縮小される。したがって、次元imageWidth × imageHeightをもつ画像のBlock-Minimum画像及びBlock-Maximum画像の大きさは
【数１】
2005354684.tif 000003
バイトによって与えられ、ここで
【数２】
2005354684.tif 000004
は比率の結果であるx以上の最小整数を示す。
【００２８】
画像ブロックの各画素値はそのブロックの最小値と最大値との間にある。ブロックのある画素値とブロックの最小画素値との差が適応分散型ディザを用いて符号化される。概して、ディザ処理は画素あたり何ビットを用いてディザを実行すべきかを先ず判定することで進む。一つの実施例において、ディザ処理のビット深度はrecommendedBitDepthを指定しているルックアップテーブルと見て決められる。図に示した例のrecommendedBitDepthルックアップテーブルはブロックの（最大‐最小）値を対応するビット深度に写像する２５６要素テーブルである。
【００２９】
多重レベルのディザ処理された画像３５を生成するために、dijと示された８ビットのしきい値のM × N行列を用いることによってタイル状画像／フレーム３２に多重レベルのディザ処理を実施する。blockMax及びblockMinはある所与のブロックの画素の最大値及び最小値を示しているとしよう。このブロックのある画素をディザ処理するのに好ましいビット数は次の式によって与えられる：
b = recommendedBitDepth[blockMax-blockMin].
bビットを有する位置（x,y）にある画素値をディザ処理するには、（Pxyと示された）位置（x,y）にある画素を先ず下記に再スケーリングする。
【数３】
2005354684.tif 000005
【００３０】
再スケーリングされた値rxyはいまやディザ処理されたbビット値oxyとして表わされ、ここで、
【数４】
2005354684.tif 000006
ここで、
【数５】
2005354684.tif 000007
そして>>はビット右シフト演算子で、<<はビット左シフト演算子である。
【００３１】
B.1  定ブロック(Constant Blocks)
ビットをさらに節約するために、エンコーダ１５は定ブロックの符号化をスキップするように修正変更されているのが好ましい。定ブロックはblockMax - blockMinの差が定義済みしきい値に満たないブロックとして定義される。この場合、この差のrecommendedBitDepthを0ビットにする。この場合、(blockMax + blockMin)/2の値が最大画像及び最小画像両方に記録され、ディザビットは生成されない。
【００３２】
B.2  バイナリ型ブロック(Binary-Like Blocks)
ビットをさらに節約するために、エンコーダ１５は以下に説明するバイナリ型ブロックを符号化するように修正変更されているのが好ましい。これは定ブロックに関する修正変更に加えた更なる修正変更が好ましいが、その代わりに修正変更を上述の基本的なエンコーダ構成に直接加えることができる。
【００３３】
一つのブロックの全ての画素がblockMax又はblockMinの所定範囲内に入っている場合には、recommendedBitDepth[blockMax - blockMin]がより大きなビット深度を規定しても、これらの画素は全て単一ビットを用いて符号化される。この場合、入力画素Pxyの出力oxyは次の式で与えられる。
【００３４】
【数６】
2005354684.tif 000008
【００３５】
この修正変更により（一般にテキストやラインの境界の周りに現れる）大型のステップ型データを符号化するのに必要なビット数が減り、そうしたエッジが分散型ディザよりも良好に保存される。（最大画像及び最小画像の同等性を確認することによりビットが生成されなかった全てのブロックにマークが付くから）飛ばしたブロックの符号化は特別のマーカーを必要としないけれども、バイナリ型ブロックのrecommendedBitDepth[blockMax-blockMin]からビット深度を推測するとブロックをディザ処理するのに使用されるビット数を過大に見積ることになるのが一般的だからバイナリ型ブロックの符号化にはマーカーが必要である。エンコーダ１５は全ての非定ブロック(non-constant block)のblockMaxの最下位ビットを摂動させること(perturbing)によってバイナリ型ブロックにフラッグを付ける。したがって、所与の非定ブロックがバイナリ型ブロックならば、blockMaxの最下位ビットを無理に０にし、そうでなければ無理に１にする。
【００３６】
先に述べたように、上述のエンコーダ１５は、修正変更を含み、各チャネル又はカラープレーンを個別に符号化することによって簡単に多色画像（例えば、YUV）に利用できるようになる。
【００３７】
C.  デコーダ
デコーダ２４はエンコーダ１５で実行された操作の反転した操作を行なって進む。復号化処理を図７に概略的に示した。先ず、格納されている最大画像３３及び最小画像３４それぞれからある所与のブロックのblockMaxとblockMinを判定する。blockMaxがblockMinと等しければ、この値がブロック全体について出力される。次に、blockMaxの最下位ビットが０（バイナリ型ブロック）ならば、０と符号化された全ての画素についてblockMinが出力される一方、（１と符号化された）ブロックの他の全ての画素についてはblockMaxが出力される。画像又はフレームの全ての他のブロックは分散型ディザ３５によって生成されたデータを保有している。この場合、符号化に用いたビット深度をrecommendedBitDepth[blockMax-blockMin]から取り戻し、対応する画素値を出力するために上記の符号化の反転した操作を行なう。
【００３８】
最終の復号化された出力３７を望ましい知覚品質にするために、低域フィルタ３６に対応する又は鮮明化と対等のフィルタ処理を復号化されたデータに施してもいい。
【００３９】
D.  固定ビットバジェット下での符号化／復号化
圧縮された出力の最大サイズが最大ビットバジェットによって束縛される場合には、上記のスキームを図８及び９に関連して以下に説明するように修正変更することができる。符号化中に、ビットバジェット合計の符号化対象画像ブロック数に対する比で与えられるビット割当てがブロック毎に予約される（ステップ８０１／９０１）。適応分散型ディザを実施する推奨ビット深度（recommendedBitDepth）が決められる（ステップ８０２／９０２）。
【００４０】
図８に示した固定ビットバジェット符号化／復号化の実施例において、最初の又は次のブロックが取得され（ステップ８０３）、ステップ８０４で、推奨ビット深度（recommendedBitDepth）でディザ処理するとブロックの事前に算出されたビット割当てに前のブロックの符号化から節約された利用できるビットを足した値を超えるかどうかが判定される。より具体的に言えば、符号化中に、recommendedBitDepth[blockMax-blockMin]によって与えられるビット深度を用いるとブロックのビットバジェットから（maxBlockとminBlock用の）２バイトを引いた値を超える場合には、ステップ８０５でビット深度をビットバジェットで足りる程度になるまで低下させる。但し、ビットが節約される場合もあることに注意：例えば、（i）定ブロックの符号化に（maxBlockとminBlock用の）２バイトしか消費せず、ディザ処理にビットが全く消費されない場合、及び（ii）バイナリ型ブロックの符号化に２バイト、ディザ処理に１ビット／画素消費する場合。こうした操作は共にビット節約になり、節約分を予約された割当て以上のビットを必要とする分散型ディザブロックに分配することができる。この節約したビットを共用及び使用するメカニズムは、ブロックあたりの予約割当てを増やすために節約したビットを一部流用する、及び（ビットの使用可能性を条件として）その残りを追加ビットを必要とするブロックにビットを提供できるビットリザーバに吸い上げることによってインプリメントされる。
【００４１】
ディザ処理のビット深度をブロックのビットバジェット相応のレベルに下げた（ステップ８０５）後、ブロックを符号化するためにその低下したビット深度で適応分散型ディザ処理が実行される（ステップ８０６）。ビット深度を下げる必要がない（ステップ８０４が"no"をリターンする）場合には、ブロックを符号化するために推奨ビット深度で適応分散型ディザ処理を実行する（ステップ８０７）。ステップ８０８で、符号化すべきブロックがもっとあると判定された場合には、プロセスはステップ８０３に戻る。ブロックが全て符号化されたら、プロセスは停止する。
【００４２】
この又は別の固定ビットバジェット符号化／復号化スキームは、図９の実施例に関連して示した「先物借用(borrow from the future)」の機能を取り入れることもできる。現ブロックのrecommendedBitDepthを満足させられるだけのビットが（前に符号化されたブロックから）節約されてない場合には、将来符号化するブロックからビットを借用してもいい。これは、現ブロックがビットを借用できる将来のブロック数を指定する水平線パラメータを定義する（ステップ９−１）ことによって達成される。水平線が与えられているとして、エンコーダ１５は、水平線内の全てのブロックが１ビット／画素と（maxBlockとminBlock用の）２バイトとだけで符号化された場合に使用可能になるビット数を計算する（ステップ９−２）。この数と水平線内のブロックのビットバジェット合計との差は、現ブロックが使用して構わず、なおかつ将来のブロックを符号化するのに十分なビットが使用可能であることを保証するビット数を表わしている。この機能拡張により、現ブロックはすでに節約されているビットだけでなく将来のブロックからもビットを借用することができる。
【００４３】
図９の実施例の処理の流れは図８のそれと類似しているが、違いは推奨ビット深度を低下させるかどうか判定するとき（ステップ９０４）、ブロックの事前に算出されたビット割当て及び前のブロックの符号化から節約された利用できるビットに将来のブロックから借用する使用可能なビットを足した値を考慮に入れることである。ビット深度を下げる場合には、ステップ９０５で行なわれ、それに続いてブロックを符号化するために適応分散型ディザ処理が行なわれる（ステップ９０６）。ビット深度を下げる必要がない場合には、ブロックを符号化するために推奨ビット深度で適応分散型ディザ処理が行なわれる（ステップ９０７）。上に説明したように、この符号化プロセスはブロックが全て符号化されてしまうまで続き（ステップ９０８）、その後プロセスは停止する。
【００４４】
デコーダ２４はブロック毎の正確なビット消費を記録しておくことができるので、総体的なビットバジェットを知っていることによりエンコーダでの全ての符号化ステップを逆に行なうことができる。したがって、エンコーダ１５及びデコーダ２４は圧縮されたビットストリームが規定のサイズを間違いなく超えないように作動することができる。指定ビットバジェットは画像全体の圧縮を保証するのに必要な最小ビット数以上、つまり、ブロックあたり２バイト及び画素あたり１ビット以上でなければならないということを知っていることが重要である。
【００４５】
E.  時間的ディザ処理(temporal dithering)
各フレームで分散型ディザ処理に使用するディザ行列を変えることで本発明の技法によって圧縮されたビデオフレームの知覚出力品質を有意に改善することができる。これを、エンコーダ１５並びにデコーダ２４で周期的に循環するディザ行列集合を用いて達成する。そうしたディザ行列集合を構築するための一つの方法は次の通り。１２８×１２８の分散型ディザ行列から始める。この行列から、初期行列を、i及びjを共に偶数としてオリジナルの１２８×１２８行列からのdijからなるMatrix Aと、iは偶数だけれどもjを奇数としてdijを有するMatrix Bと、iは奇数だけれどもjを偶数としてdijを有するMatrix Cと、i及びjを共に奇数としてdijを有するMatrix Dとに分割することによって４個の分散型ディザ行列（各々６４×６４）を生成することができる。逐次フレームのディザ行列を順繰りにA, D, B, C, A, D, B, C、、、、のように選ぶ。
【００４６】
時間的ディザ処理のためにディザ行列及びシーケンスの族を生成するための他の方法を選んでも構わない。符号化及び復号化のステップはディザ行列のロックステップが変わる以外何も変わらない。この技法の使用により低ビット深度で符号化された画像シーケンスの視的認知がとりわけ良くなる。
【００４７】
F.  ブロックの説明
図１０は、本発明の符号化の技法を適用した画像の実例である。定ブロック、バイナリ型ブロック、及びディザ処理ブロックが識別されている。参照番号１０１で識別された中間の濃色領域は定ブロックを保有し、参照番号１０２で識別された明るい色の領域はバイナリ型ブロックを保有している。分散型ディザブロックは最も暗い領域１０３に入っている。色合いが濃くなるほどディザ処理のビット深度が高くなる。ブロックの次元はアスペクト比２（つまり、ブロックあたり４行×８列）を有しているから、アスペクト比は正方形ではないことを知っておくべきである。
【００４８】
G.  コーデックがサポートしているその他の機能
G.1  コントラスト及び明度(brightness)の調整
説明したコーデック１１ははるかに小さくなった最小及び最大画像の値だけを調整することで明度とコントラストの調整を簡単に実行できる。最小画像と最大画像の値が共に増加すると、画像は明るさを増す。最小画像値をスケールダウンする一方、最大画像値をスケールアップすると、画像のコントラストが増す。
【００４９】
G.2  ランダムブロックアクセス及び復号化
説明したコーデック１１は画像全体を復号化しないで対象ブロックの部分集合だけを高速復号化するのを可能にする。この操作は、ディザ処理されたデータの中の所望のブロックのビット位置を見出すのに、（はるかに小さくなった）最小及び最大画像をステップバイステップで進み、前のセクションで説明した所望のブロックを復号化しなければならない。
【００５０】
H.  応用／インプリメンテーション
発明の特定の応用いかんにより、様々なシステム構成が可能である。図１に示した構成において、コーデック１１はビデオコントローラ１２の中に実施され、他の構成要素を含んだ符号化／復号化パイプラインの一部となっている。こうした他の構成要素の一部又は全てをビデオコントローラ１２の中に実施する（例えば、プリプロセッサとフレームバッファ）一方、他を外部に置いても構わない（例えば、バッファ伝送エンコーダとデコーダ）。図に示した構成における「内部」構成要素と「外部」構成要素との境界線は模式的なものに過ぎない。そうした境界線は特定の応用及び／又は使用状況いかんによって変わることがあり、またそうなることが多い。
【００５１】
コーデック１１（及び個々のエンコーダ１５及びデコーダ２４）の機能はハードウェアかソフトウェアかのいずれか或いはそれらの組合せで容易にインプリメントできる。ソフトウェアインプリメンテーションで、コーデック１１は、本発明の符号化／復号化操作の様々な態様をインプリメントするプログラムにアクセスするランダムアクセスメモリ（RAM）とインタフェースするかもしれない命令駆動型プロセッサを含んでいる。より大まかに言えば、そうしたプログラムを任意の適切な場所（ローカル又は遠隔）からコーデック１１に、磁気テープ又はディスク又は光ディスク、ネットワーク信号、或いは赤外線信号など適切な電磁搬送波信号といった様々な機械可読媒体のどれかで伝達することができる。ハードウェアインプリメンテーションは、例えば、ASIC、デジタル信号処理回路機構などを用いて実現されて構わない。したがって、クレーム表現「装置可読媒体」には、ソフトウェア搬送メディアだけでなく、必要な処理を実行するための命令がハードワイヤされたハードウェアも含まれるし、ハードウェアとソフトウェアとの組合せも含まれる。同様に、クレーム表現「命令プログラム」には、ソフトウェアも、ハードウェアに実装された命令も含まれる。こうしたインプリメンテーションの変形例を考えれば、図面及びそれに伴う説明は当業者がプログラムコード（つまり、ソフトウェア）を書いたり、必要な処理を実行するための回路（つまり、ハードウェア）を作るのに欠かせない機能情報を提供していると理解するべきである。
【００５２】
発明をいくつかの具体的な実施例と共に説明してきたが、上記の説明に照らして当業者ならばさらに数多くの変形例、修正例、変更例及び応用例が明白になるだろう。したがって、ここで説明した発明は、添付の請求項の精神及び範囲から逸脱しない限りにおいて、そうした変形例、修正例、変更例及び応用例を全て網羅するものと考えている。
【図面の簡単な説明】
【００５３】
【図１】発明の実施例による、符号化／復号化システムの様々な構成要素を示す概略図。
【図２】本発明の符号化及び復号化の技法を適用できる多色画像を表わす入力画像。
【図３】図２に示した入力画像のY成分。
【図４】システムの符号化の構成要素の機能を示すブロック図。
【図５】発明の実施例と共に使用したBlock-Maximum画像の拡大版。
【図６】発明の実施例と共に使用したBlock-Minimum画像の拡大版。
【図７】システムの復号化の構成要素の機能を示すブロック図。
【図８】固定ビットバジェット符号化／復号化スキームの一つの実施例を示す流れ図。
【図９】固定ビットバジェット符号化／復号化スキームのもう一つの実施例を示す流れ図。
【図１０】本発明の符号化技法を適用した画像の図で、定ブロック、バイナリ型ブロック、ディザ処理されたブロックを識別している。
【符号の説明】
【００５４】
12・・・ビデオコントローラ
13・・・プレプロセッサ
14・・・フレームバッファ
15・・・エンコーダ
16・・・バッファ
17・・・伝送エンコーダ
22・・・伝送エンコーダ
24・・・デコーダ
25・・・フレームバッファ
26・・・ポストプロセッサ
23・・・バッファ
21・・・入力画像
33・・・Y成分Block-Maximum画像
31・・・入力画像のY成分
32・・・タイル状の画像／フレーム
33・・・Y成分Block-Maximum画像
34・・・Y成分Block-Minimum画像
35・・・多重レベルのディザ処理された画像
36・・・低域フィルタ
37・・・出力
【図１】
2005354684.tif 000009
【図８】
2005354684.tif 000010
【図９】
2005354684.tif 000011
【図２】
2005354684.tif 000012
【図３】
2005354684.tif 000013
【図４】
2005354684.tif 000014
【図５】
2005354684.tif 000015
【図６】
2005354684.tif 000016
【図７】
2005354684.tif 000017
【図１０】
2005354684.tif 000018