(57)【要約】【課題】  ＤＣＴ係数に対する可逆圧縮の費用を減らし、単純にする。【解決手段】  デジタル画像は、ピクセルの配列を含む。空間領域において、各ピクセルを、ｎビットワードで表す。ＲＧＢ色空間を表す典型的な２４ビットワードにおいて、たとえば、８ビットは赤成分を表し、８ビットは緑成分を表し、８ビットは青成分を表す。デジタル画像を、空間領域から周波数領域に変換する（１１０）。離散コサイン変換を使用して、空間領域のピクセルのブロックを周波数領域のＤＣＴ係数のブロックに変換することができる。たとえば、８×８ブロックのピクセルを８×８ブロックのＤＣＴ係数に変換することができる。変換係数のブロックに対し非可逆圧縮を実行する（１１２）。たとえば、ＤＣＴ係数を量子化することができる。量子化は、ＤＣＴ係数を四捨五入してゼロ値と非ゼロ値とにする。
2005525006.tif 000002
【特許請求の範囲】
【請求項１】
デジタル画像の周波数領域表現を処理する装置（５１０）であって、
前記周波数領域表現の少なくとも１つのブロック（２１０）の少なくとも３つの異なる領域に対しスキャン（２１２、２１４、２１６）を実行するプロセッサ（５１２）
を具備するデジタル画像の周波数領域表現を処理する装置。
【請求項２】
前記スキャン（２１２、２１４、２１６）は、同じ数の係数をカバーする
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項３】
前記領域は、前記画像の特性に従って選択される
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項４】
前記領域は、前記画像のエッジに対して最適化される
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項５】
前記領域は、オーバラップしない
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項６】
第１のスキャン（２１２）が第１の領域に対して実行され、第２のスキャン（２１４）が第２の領域に対して実行され、第３のスキャン（２１６）が第３の領域に対して実行され、前記第１の領域はブロックの対角線に沿い、前記第２および第３の領域は前記第１の領域の反対側にある
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項７】
各領域においてジグザグスキャンが実行される
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項８】
前記プロセッサ（５１２）はまた、前記スキャン（２１２、２１４、２１６）によってカバーされる係数を符号化し、該スキャン（２１２、２１４、２１６）は別々に符号化される
請求項１に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項９】
各スキャン（２１２、２１４、２１６）に対し、最後の非ゼロ係数が見つけられ、前記係数は、該最後の非ゼロ係数から最初の係数に向かって逆の順序で符号化される
請求項８に記載のデジタル画像の周波数領域表現を処理する装置。
【請求項１０】
前記プロセッサ（５１２）は、前記係数に対するコードワードを選択するために異なるコードブックから選択し、
ｎ番目の係数に対するコードブックは、前記スキャン（２１２、２１４、２１６）におけるｎ−１番目の係数に従って選択される
請求項９に記載のデジタル画像の周波数領域表現を処理する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数スキャンを使用する変換係数圧縮に関する。
【背景技術】
【０００２】
［背景］
コンピュータに大きいデータファイルを格納するコストを低減するとともに、コンピュータ間で大きいデータファイルを送信する時間を低減するために、データ圧縮が使用される。
いわゆる「変換方法」において、データは、周波数領域においてデータを表現する係数に変換される。
係数を、量子化された係数から復元されるデータの品質に著しく影響を与えることなく量子化することができる（非可逆圧縮）。
そして、係数における冗長性を、復元されたデータの品質に影響を与えることなく低減または削除することができる（可逆圧縮）。
変換の１つの種類は、離散コサイン変換である。
ＤＣＴは、画像情報の大部分をわずかな数の係数にする。
圧縮を得るために、係数の大部分をより小さいビットサイズに量子化することができる。
【非特許文献１】APOSTROPOULOS J: "Position Dependent Encoding", Proceedings of the international conference on acoustics, speech and signal processing. Adelaide, April. 19-22, 1994, New York, IEEEE US, vil.  Conf. 19, 19 April 1994 (1994--4-19), pages V-573-V-576, XP000533778 ISBN: 0-7803-1776-9
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ＤＣＴは、計算が高速である。
しかしながら、ＤＣＴ係数に対し可逆圧縮を実行することは、費用がかかり複雑である可能性がある。
【課題を解決するための手段】
【０００４】
［要約］
本発明の一態様によれば、デジタル画像の周波数領域表現の変換係数ブロックを、そのブロックの少なくとも３つの異なる領域に対しスキャンを実行することによって処理する。
本発明の他の態様および利点は、本発明の原理を例として示す添付図面に関連して、以下の詳細な説明から明らかとなろう。
【発明を実施するための最良の形態】
【０００５】
［詳細な説明］
例示の目的で図面に示すように、本発明を、デジタル画像を圧縮する方法において実施する。
本方法は、特に、テキストならびに水平および垂直エッジを有する他の形状を含むデジタル画像を圧縮するのに効率がある。
本方法を、テキストおよびグラフィックスのために別々のパイプラインを有するプリンタおよび他の機械によって使用することができる。
【０００６】
本方法を、離散コサイン変換に関連して説明する。
しかしながら、本方法は、ＤＣＴ変換に限定されない。
本方法を、ウェーブレットベースの変換およびエネルギーが集中する（たとえば、低周波数成分におけるエネルギーの大部分）他の変換と使用してもよい。
【０００７】
デジタル画像を圧縮する方法を示す、図１を参照する。
デジタル画像は、ピクセルの配列を含む。
空間領域において、各ピクセルを、ｎビットワードで表す。
ＲＧＢ色空間を表す典型的な２４ビットワードにおいて、たとえば、８ビットは赤成分を表し、８ビットは緑成分を表し、８ビットは青成分を表す。
【０００８】
デジタル画像を、空間領域から周波数領域に変換する（１１０）。
離散コサイン変換を使用して、空間領域のピクセルのブロックを周波数領域のＤＣＴ係数のブロックに変換することができる。
たとえば、８×８ブロックのピクセルを８×８ブロックのＤＣＴ係数に変換することができる。
【０００９】
変換係数のブロックに対し非可逆圧縮を実行する（１１２）。
たとえば、ＤＣＴ係数を量子化することができる。
量子化は、ＤＣＴ係数を四捨五入してゼロ値と非ゼロ値とにする。
【００１０】
ここで、図２をさらに参照する。
図２は、ＤＣＴ係数の８×８ブロック２１０を示す。
ＤＣ係数は、左上角にあり、周波数は、右下角に向かって増大する。
典型的に、量子化されたより高い周波数係数はゼロに等しくなる。
【００１１】
そして、変換係数の可逆圧縮を実行する（１１４）。
各変換係数ブロックの３つの異なる領域に対し、スキャン２１２、２１４および２１６を実行する（１１６）。
第１の領域は、変換係数ブロック２１０の対角線に沿って位置するそれらの係数を含み、第１のスキャン２１２はそれらの係数をカバーする。
第２の領域は、第１の領域の上にあるそれらの係数を含み、第２のスキャン２１４はそれらの係数をカバーする。
第３の領域は、第１の領域の下にあるそれらの係数を含み、第３のスキャン２１６はそれらの係数をカバーする。
第２のスキャン２１４（第２の領域の係数をカバーする）は、水平エッジをカバーする傾向があり、第３のスキャン２１６（第３の領域の係数をカバーする）は、垂直エッジをカバーする傾向がある。
【００１２】
各スキャンは、低周波数係数から高周波数成分まで進行することができる。
通常、ＤＣ係数は別個に符号化されるためスキャンされない。
好ましくは、各スキャン２１２、２１４および２１６は、同じ数の係数をカバーする。
図２に示す８×８ブロックの変換係数では、各スキャン２１２、２１４および２１６は、２１個の係数をカバーする。
【００１３】
係数を、一度に１ブロックで符号化する（１１８）。
さらに、各ブロックのスキャンを、別々に符号化する。
たとえば、ＤＣ係数を符号化して出力ビットストリームに追加し、第１のスキャン２１２によってカバーされる係数を符号化してビットストリームに追加し、次いで第２のスキャン２１４によってカバーされる係数を符号化してビットストリームに追加し、次いで第３のスキャン２１６によってカバーされる係数を符号化してビットストリームに追加する。
符号化により、画像情報を低減することなくビットの数が低減する。
符号化を、多数の方法で実行することができる。
例として、各スキャンにおける係数を、従来のハフマン符号化によって符号化した後にランレングス符号化によって符号化され、または、エントロピー符号化または算術符号化によって符号化されることができる。
【００１４】
ここで、図３を参照する。
図３はさらに別の符号化方法、すなわちコンテキストベースの符号化を示す。
コンテキストベースの符号化は、スキャンにおける係数が典型的には異なる分布を有することになるという仮説に基づく。
コンテキストベースの符号化は、異なる分布に異なるコードブックを割り当てる。
たとえば、第１のコードブックを、ゼロを中心とする狭い分布を表示する係数に割り当て、異なるコードブックを、ゼロを中心とする広い分布を表示する係数に割り当てる。
この手法は、異なる分布に対して同じコードブックを使用するより効率的になる傾向がある。
【００１５】
コンテキストベースの符号化を、以下のように各ブロックに対して実行してもよい。
ＤＣ係数を符号化しビットストリームに追加する（３１２）。
すべてのスキャンにおけるすべての係数がゼロに等しい場合（３１４）、それを示す特別なシンボルをビットストリームに追加し（３１６）、符号化を終了する。
すべてのスキャンのすべての係数がゼロに等しくはない場合（３１４）、それを示す特別なシンボルをビットストリームに追加し（３１８）、第１のスキャンを検査する（３２６）。
【００１６】
スキャンにおける最後の非ゼロ係数を見つけ、その位置を符号化してビットストリームに追加する（３２０）。
そして、スキャンにおける係数を、逆の順序で、すなわちスキャンにおける最後の非ゼロ係数から最初の係数に向かって処理する（３２２）。
スキャンがすべてゼロ係数を含む場合、最後の非ゼロ係数の位置をゼロとして符号化してもよく、いずれの係数も処理しない。
すべてのスキャンが符号化される（３２４）まで別のスキャンを検査する（３２６）。
【００１７】
スキャンの係数を、スキャンのｎ番目の係数をスキャンのｎ−１番目の係数に対するコンテキストとして使用することにより処理してもよい（３２２）。
ｎ番目の係数を使用して、ｎ−１番目の係数に対し複数のコードブックのうちの１つを選択し、選択されたコードブックを使用してｎ−１番目の係数に対するコードワードを提供する。
各係数のパス長および大きさを符号化してもよい。
ｎ−１番目の係数に対応するコードワードをビットストリームに追加する。
【００１８】
スキャンの係数の以下の例を考える。
すなわち、１５３、−４１、−８、−１、−１、１、０、１、０、０、…、０、０である。
ここで、コードブックを割り当てる以下のルールを考える。
すなわち、コードブックｃ０を０に先立つ係数に割り当て、コードブックｃ１を±１に先立つ係数に割り当て、コードブックｃ２を±２に先立つ係数に割り当て、コードブックｃ３を±３または±４に先立つ係数に割り当て、コードブックｃ４を±５または±６または±７または±８に先立つ係数に割り当て、コードブックｃ５を他のすべての係数に割り当てる。
下の表１に示すようにコードブックを割り当てる。
１５３に対するコードワードをコードブックｃ５から取得し、−４１に対するコードワードをコードブックｃ４から取得し、−８に対するコードワードをコードブックｃ１から取得する、等である。
【００１９】
【表１】
2005525006.tif 000003
【００２０】
単一カラーチャネルに対する圧縮方法を説明した。
複数のカラーチャネル（たとえば、ＲＧＢ、ＹＵＶ）を有するカラーデジタル画像の場合、本方法を各カラーチャネルに対して実行する。
結果は、ブロック毎に９つのスキャンであり、それらは別々に符号化される。
輝度チャネルからのコンテキストを使用して、クロミナンスチャネルを符号化することができる。
輝度値が０である場合、クロミナンス成分もまたゼロであると仮定してもよい。
【００２１】
ここで、図４を参照する。
ビットストリームを周波数領域係数に復号化し（４１０）、各変換係数ブロックの少なくとも３つの異なる領域に復号化した周波数領域成分を充填することにより周波数領域表現を生成し（４１２）、周波数領域表現に対し逆変換を実行する（４１４）ことによって、デジタル画像を復元する。
【００２２】
ここで、図５を参照する。
図５は、上述した圧縮および復元方法の一方または両方を実行する機械５１０を示す。
機械５１０は、プロセッサ５１２とメモリ５１４とを含む。
メモリ５１４は、実行時に、プロセッサ５１２に対し上述したようにデジタル画像を圧縮または復元させるプログラム５１６を格納する。
【００２３】
圧縮方法は、上述したスキャンパターンの数とスキャンパターンの形状とに限定されない。
このため、圧縮方法は、ジグザグ形状を有する３つのスキャンパターンに限定されない。
スキャンパターンの形状を、デジタル画像の特性に従って選択することができる。
【００２４】
異なるスキャンはオーバラップしなくてもよく、あるいは、いくつかの係数をオーバラップしてもよい。
異なるスキャンは、異なる数の変換係数をカバーしてもよく、あるいは同じ数の係数をカバーしてもよい。
【００２５】
４つ以上のスキャンを使用してもよい。
しかしながら、スキャンの数が増大することにより、各スキャンの係数の数が低減する。
【００２６】
本方法は、８×８ブロックの変換係数に限定されない。
他のサイズのブロックを使用してもよい。
【００２７】
本発明は、上に説明し例示した特定の実施形態に限定されない。
代りに、本発明は、特許請求の範囲に従って解釈される。
【図面の簡単な説明】
【００２８】
【図１】デジタル画像を圧縮する方法の図である。
【図２】デジタル画像の周波数領域表現の変換係数ブロックの図である。
【図３】周波数領域表現のブロックに対しコンテキストベース符号化を実行する方法の図である。
【図４】ビットストリームからデジタル画像を復元する方法の図である。
【図５】デジタル画像の圧縮および復元を実行する装置の図である。
【符号の説明】
【００２９】
２１０・・・８×８ブロック、
２１２，２１４，２１６・・・スキャン、
【図１】
2005525006.tif 000004
【図２】
2005525006.tif 000005
【図３】
2005525006.tif 000006
【図４】
2005525006.tif 000007
【図５】
2005525006.tif 000008
【国際調査報告】
2005525006.tif 000009
2005525006.tif 000010