(57)【特許請求の範囲】
【請求項１】
入力画像あるいは動き補償予測差分画像を符号化対象信号として符号化する画像符号化方法において、
符号化対象信号を、水平及び垂直の両方向について高域と低域に周波数帯域分割し、水平及び垂直の両方向に対しての低域成分を同様に再分割し、該再分割処理を再帰的にそれぞれ指定された回数繰り返すことで符号化対象信号変換係数を算出するステップと、
該符号化対象信号変換係数をそれぞれ量子化して量子化後変換係数を算出するステップと、
前記各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、最低周波数帯域の係数を幹に持つ階層的な４分木構造であるツリーを形成するステップと、
該ツリー中の各量子化後変換係数について、該量子化後変換係数及び該量子化後変換係数の全ての子孫が有意係数を持たない部分木であるゼロツリーを探索するステップと、
前記ツリー内のある量子化後変換係数を符号化するに当たり、該量子化後変換係数の直接の子供係数のうち、該子供係数を幹とする部分木がゼロツリーである個数を示すＺカウントを算出するステップと、
該量子化後変換係数の絶対値及びＺカウントからなる二次元可変長符号を符号化データに出力するステップとを有する
ことを特徴とする画像符号化方法。
【請求項２】
請求項１記載の画像符号化方法において、
ある量子化後変換係数を符号化するに当たり、該量子化後変換係数の絶対値がゼロでない場合は、前記二次元可変長符号を符号化データに出力した直後に、該量子化後変換係数の正負の符号を符号化データに出力することを特徴とする画像符号化方法。
【請求項３】
請求項１記載の画像符号化方法において、
ツリーの幹以外の量子化後変換係数を符号化するに当たり、該量子化後変換係数の親係数の子供の係数を示す兄弟係数を検査し、該兄弟係数それぞれに対応する前記二次元可変長符号を符号化データに出力する前に、該兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を符号化データに出力することを特徴とする画像符号化方法。
【請求項４】
請求項３記載の画像符号化方法において、
兄弟係数のマップ符号を出力するに当たり、該兄弟係数の親係数を符号化した際に符号化データに出力済みの該兄弟係数のＺカウントを参照し、該Ｚカウントの値が、該兄弟係数が全てゼロツリーの幹であるか、あるいは全てゼロツリーの幹ではないことを示している値である場合には前記マップ符号を符号化データに出力せず、該兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には前記マップ符号を符号化データに出力することを特徴とする画像符号化方法。
【請求項５】
請求項４記載の画像符号化方法において、
親係数を符号化した際に符号化データに出力済みのＺカウントが、兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合、Ｚカウントの値に対応するマップ符号用の可変長符号テーブルを用意しておき、前記親係数のＺカウントに応じて該マップ符号用の可変長符号テーブルを切り替えて符号化することを特徴とする画像符号化方法。
【請求項６】
請求項３または４記載の画像符号化方法において、
マップ符号を符号化データに出力した後に、前記親係数を符号化した際に符号化データに出力済みの兄弟係数のうちのゼロツリーの幹ではない係数の数だけ、該ゼロツリーの幹ではない係数の二次元可変長符号及び請求項２記載の条件に応じて前記正負の符号を符号化データに出力することを特徴とする画像符号化方法。
【請求項７】
請求項３記載の画像符号化方法において、
４つの兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を生成するに当たり、該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に該４つの兄弟係数がゼロツリーの幹であるかどうかを調べることを特徴とする画像符号化方法。
【請求項８】
請求項１乃至７いずれか記載の画像符号化方法による符号化データを復号する方法であって、
ある係数を復号対象係数として復号するに当たり、該復号対象係数の親係数を復号した際に復号済みの該復号対象係数の兄弟係数のＺカウントを取り出すステップと、
該兄弟係数のＺカウントが、該兄弟係数の全てがゼロツリーの幹ではないかあるいは全てがゼロツリーの幹であることを示す場合は、マップ符号を復号せず、兄弟係数のうちのいくつかはゼロツリーの幹でいくつかはゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のＺカウントの値に応じて可変長符号化テーブルを切り替えてマップ符号を復号するステップと、
該マップ符号によりゼロツリーの幹ではないと示されている兄弟係数について、それぞれ、該兄弟係数の子供係数のＺカウント及び復号対象係数の絶対値からなる二次元可変長符号を復号し、復号された該絶対値がゼロでない場合は該復号対象係数の正負の符号を復号し、該絶対値及び該正負の符号より復号係数値を算出し、同時に該兄弟係数の子供係数を復号する際に利用するために該Ｚカウントを記録するステップと、
該マップ符号によりゼロツリーの幹であると示されている兄弟係数については、ゼロツリーの幹の場所情報を記録するステップと、
それぞれ算出された兄弟係数の該復号係数値を該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に復号係数メモリに記録するステップとを有する
ことを特徴とする画像復号方法。
【請求項９】
入力画像あるいは動き補償予測差分画像を符号化対象信号として符号化する画像符号化装置において、
符号化対象信号を、水平及び垂直の両方向について高域と低域に周波数帯域分割し、水平及び垂直の両方向に対しての低域成分を同様に再分割し、該再分割処理を再帰的にそれぞれ指定された回数繰り返すことで符号化対象信号変換係数を算出する手段と、
該符号化対象信号変換係数をそれぞれ量子化して量子化後変換係数を算出する手段と、
前記各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、最低周波数帯域の係数を幹に持つ階層的な４分木構造であるツリーを形成する手段と、
該ツリー中の各量子化後変換係数について、該量子化後変換係数及び該量子化後変換係数の全ての子孫が有意係数を持たない部分木であるゼロツリーを探索する手段と、
前記ツリー内のツリーの幹以外のある量子化後変換係数及び該量子化後変換係数の親係数の子供の係数を示す兄弟係数を符号化するに当たり、該兄弟係数を幹とする部分木がゼロツリーである個数を示すＺカウントが、該兄弟係数が全てゼロツリーの幹であるかあるいは全てゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を符号化データに出力せず、該兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に該４つの兄弟係数がゼロツリーの幹であるかどうかを調べて、該兄弟係数のＺカウントに応じて可変長符号化テーブルを切り替えつつ、該兄弟係数に対応するマップ符号を符号化データに出力する手段と、
該兄弟係数のうちのゼロツリーの幹ではない変換係数に関し、該変換係数の直接の子供係数のＺカウントを算出し、該変換係数の絶対値及びＺカウントからなる二次元可変長符号を符号化データに出力する手段と、
該絶対値がゼロでない場合は、該二次元可変長符号の後に該変換係数の正負の符号を符号化データに出力する手段とを有する
ことを特徴とする画像符号化装置。
【請求項１０】
請求項９記載の画像符号化装置による符号化データを復号する装置であって、
ある係数を復号対象係数として復号するに当たり、該復号対象係数の親係数を復号した際に復号済みの該復号対象係数の兄弟係数のＺカウントを取り出す手段と、
該兄弟係数のＺカウントが、該兄弟係数の全てがゼロツリーの幹ではないかあるいは全てがゼロツリーの幹であることを示す場合は、マップ符号を復号せず、兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のＺカウントの値に応じて可変長符号化テーブルを切り替えてマップ符号を復号する手段と、
該マップ符号によりゼロツリーの幹ではないと示されている兄弟係数について、それぞれ、該兄弟係数の子供係数のＺカウント及び復号対象係数の絶対値からなる二次元可変長符号を復号し、復号された該絶対値がゼロでない場合は該復号対象係数の正負の符号を復号し、該絶対値及び該正負の符号より復号係数値を算出し、同時に該兄弟係数の子供係数を復号する際に利用するために該Ｚカウントを記録する手段と、
該マップ符号によりゼロツリーの幹であると示されている兄弟係数については、ゼロツリーの幹の場所情報を記録する手段と、
それぞれ算出された兄弟係数の該復号係数値を該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に復号係数メモリに記録する手段とを有する
ことを特徴とする画像復号装置。
【請求項１１】
入力画像あるいは動き補償予測差分画像を符号化対象信号として符号化する画像符号化プログラムを記憶した媒体であって、
前記プログラムはコンピュータに読み取られた際、該コンピュータ上に、
符号化対象信号を、水平及び垂直の両方向について高域と低域に周波数帯域分割し、水平及び垂直の両方向に対しての低域成分を同様に再分割し、該再分割処理を再帰的にそれぞれ指定された回数繰り返すことで符号化対象信号変換係数を算出する手段と、
該符号化対象信号変換係数をそれぞれ量子化して量子化後変換係数を算出する手段と、
前記各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、最低周波数帯域の係数を幹に持つ階層的な４分木構造であるツリーを形成する手段と、
該ツリー中の各量子化後変換係数について、該量子化後変換係数及び該量子化後変換係数の全ての子孫が有意係数を持たない部分木であるゼロツリーを探索する手段と、
前記ツリー内のツリーの幹以外のある量子化後変換係数及び該量子化後変換係数の親係数の子供の係数を示す兄弟係数を符号化するに当たり、該兄弟係数を幹とする部分木がゼロツリーである個数を示すＺカウントが、該兄弟係数が全てゼロツリーの幹であるかあるいは全てゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を符号化データに出力せず、該兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に該４つの兄弟係数がゼロツリーの幹であるかどうかを調べて、該兄弟係数のＺカウントに応じて可変長符号化テーブルを切り替えつつ、該兄弟係数に対応するマップ符号を符号化データに出力する手段と、
該兄弟係数のうちのゼロツリーの幹ではない変換係数に関し、該変換係数の直接の子供係数のＺカウントを算出し、該変換係数の絶対値及びＺカウントからなる二次元可変長符号を符号化データに出力する手段と、
該絶対値がゼロでない場合は、該二次元可変長符号の後に該変換係数の正負の符号を符号化データに出力する手段とを構成する
ことを特徴とする画像符号化プログラムを記憶した媒体。
【請求項１２】
請求項９記載の画像符号化装置もしくはコンピュータ及び請求項１１記載の画像符号化プログラムを記憶した媒体によって実現される画像符号化装置による符号化データを復号する画像復号プログラムを記憶した媒体であって、
前記プログラムはコンピュータに読み取られた際、該コンピュータ上に、
ある係数を復号対象係数として復号するに当たり、該復号対象係数の親係数を復号した際に復号済みの該復号対象係数の兄弟係数のＺカウントを取り出す手段と、
該兄弟係数のＺカウントが、該兄弟係数の全てがゼロツリーの幹ではないかあるいは全てがゼロツリーの幹であることを示す場合は、マップ符号を復号せず、兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のＺカウントの値に応じて可変長符号化テーブルを切り替えてマップ符号を復号する手段と、
該マップ符号によりゼロツリーの幹ではないと示されている兄弟係数について、それぞれ、該兄弟係数の子供係数のＺカウント及び復号対象係数の絶対値からなる二次元可変長符号を復号し、復号された該絶対値がゼロでない場合は該復号対象係数の正負の符号を復号し、該絶対値及び該正負の符号より復号係数値を算出し、同時に該兄弟係数の子供係数を復号する際に利用するために該Ｚカウントを記録する手段と、
該マップ符号によりゼロツリーの幹であると示されている兄弟係数については、ゼロツリーの幹の場所情報を記録する手段と、
それぞれ算出された兄弟係数の該復号係数値を該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に復号係数メモリに記録する手段とを構成する
ことを特徴とする画像復号プログラムを記憶した媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像符号化方法及び画像復号方法、画像符号化装置及び画像復号装置、並びにそれらのプログラムを記憶した媒体に関するものである。
【０００２】
【従来の技術】
従来、静止画像又は動画像の圧縮符号化にはＤＣＴ（離散コサイン変換）が広く用いられてきた。しかしながら、ＤＣＴによる画像符号化は、ある程度以上の圧縮率では、変換処理の単位であるブロックの境界が不連続になるブロック歪みや、急峻なエッジ部周辺に発生するモスキートノイズ等の特有の画質劣化が主観画質上問題となっていた。これらの問題点を回避する符号化方法として、離散ウェーブレット変換（Ｉ．Ｄａｕｂｅｃｈｉｅｓ，”Ｏｒｔｈｏｎｏｒｍａｌ  ｂａｓｅｓ  ｏｆ  ｃｏｍｐａｃｔｌｙ  ｓｕｐｐｏｒｔｅｄ  ｗａｖｅｌｅｔｓ”，Ｃｏｍｍ．Ｐｕｒｅ  Ａｐｐｌ．Ｍａｔｈ，ｖｏｌ．４１，ｐｐ．９０９−９９６，１９８８）を利用した符号化方法が種々検討されている。
【０００３】
離散ウェーブレット変換は、階層的なサブバンド分割と同様に、画像を解像度の異なる周波数帯域成分に分解する。分解された変換係数の総数は原画像の画素数と同じであるが、一般的に、より低い周波数成分に信号エネルギーが集中したものになる。
【０００４】
ウェーブレット変換係数は、１次元のフィルタバンクとサブサンプリング処理によって求められる。図１（ａ）に示すように、画像Ｘ（ｚ）の水平方向について低域フィルタＨl（ｚ）及び高域フィルタＨh（ｚ）出力を求め、その出力を１／２（↓２）に間引く。さらに、同様の処理を垂直方向に適用することにより、４成分ＬＬ1，ＬＨ1，ＨＬ1，ＨＨ1に分解される。
【０００５】
このうち、最も低い周波数成分ＬＬ1をＬＬ2，ＬＨ2，ＨＬ2，ＨＨ2に再分解する。この処理を必要なレベル数繰り返すことにより、図２に示すような画像のオクターブ分割を求めることができる。再生過程においては、図１（ｂ）に示すように、帯域成分ＬＬi+1、ＬＨi+1の垂直方向の各係数間にゼロ値を挿入（↑２）し、その垂直方向にそれぞれ合成フィルタＦl（ｚ），Ｆh（ｚ）をかけ、それらの出力の和を求める。同様の処理を水平方向にＨＬi+1，ＨＨi+1成分に行う。即ち得られた２成分に、水平方向に同様のフィルタ処理を行うことによりＬＬi成分が合成される。
【０００６】
この合成処理を必要なレベル数だけ繰り返すことにより、画像の再生値が得られる。画像が完全再構成されるためには、分解・合成フィルタは
Ｈl（ｚ）Ｈh（−ｚ）＋Ｈl（−ｚ）Ｈh（ｚ）＝ｃ        ……（１）
Ｆl（ｚ）＝（２／ｃ）Ｈh（−ｚ）                      ……（２）
Ｆh（ｚ）＝（２／ｃ）Ｈl（−ｚ）                      ……（３）
という条件を満たしていなければならない。ここで、分解・合成フィルタのタップ長は奇数であり、ｃは任意の定数である。また、分解及び合成フィルタ係数の相互関係を図３に示す。
【０００７】
入力画像信号に水平・垂直ウェーブレット変換を施して得られたウェーブレット変換係数は量子化され、符号化される。一般に、同レベルの高周波数帯域（ＨＬm，ＬＨm，ＨＨm，ｍ∈自然数）内の変換係数を同じ量子化ステップで量子化を行い、量子化後のウェーブレット変換係数をＲｕｎ−Ｌｅｎｇｔｈ符号化、Ｒｕｎ−Ｌｅｖｅｌ符号化等を用いて可変長符号化し、発生符号量を低減する。
【０００８】
この時、最低周波数帯域ＬＬを除く他の高周波数帯域内のウェーブレット変換係数値は、ゼロ近傍に集中するラプラス分布で近似可能なため、後述のゼロツリー符号化の効率改善を考慮し、一般的にセンターデッドゾーン付きスカラー量子化が用いられる。なお、ＬＬ帯域は粗く、量子化すると復号画像に視覚的に妨害な歪みが目立つため、量子化を行わずにＤＰＣＭを用いて可逆符号化する手法が一般的である。
【０００９】
また、ウェーブレット変換係数の符号化方法に関しては、各周波数帯域の相似な位置の係数間で相関を持つことを利用した符号化方法も提案されている。ウェーブレットを用いた二次元オクターブ分割では、１レベルの分解によりＬＬ，ＬＨ，ＨＬ，ＨＨの４成分に分解され、Ｍレベルの分割を行うと、最低周波数帯域であるＬＬM成分から、ＬＨ1，ＨＬ1，ＨＨ1成分までの（３Ｍ＋１）個の成分に分解される。図４はＭ＝３の時の周波数帯域分割例である。
【００１０】
分割された周波数帯域信号には、図４に示すようにＬＬ，ＬＨ，ＨＬ，ＨＨの各周波数帯域がある。
【００１１】
ＬＬ帯域は水平・垂直方向に低域側の信号であり、画像に２次元の低域フィルタ（ＬＰＦ）をかけた信号である（以下、「低域成分」あるいは「最低周波数帯域」と呼ぶことがある。）。ＨＬ帯域は水平方向に高域フィルタ（ＨＰＦ）、垂直方向に低域フィルタをかけた信号であり、垂直方向のエッジ成分が現れる（以下、「水平成分」と呼ぶことがある。）。ＬＨ帯域は水平方向に低域フィルタ、垂直方向に高域フィルタをかけた信号であり、水平方向のエッジ成分が現れる（以下、「垂直成分」と呼ぶことがある。）。ＨＨ帯域は水平、垂直方向ともに高域フィルタをかけた信号で、斜め方向のエッジ成分が現れる（以下、「対角成分」と呼ぶことがある。）。
【００１２】
先に述べた自己相似性によるデータの冗長性を除くため、ｉレベルの分割で得られたＬＨi，ＨＬi，ＨＨiの３つの高周波成分内の各変換係数と、（ｉ−１）レベルのＬＨi-1，ＨＬi-1，ＨＨi-1内において、前記各変換係数とそれぞれ空間的に相似な位置の変換係数間で親子関係を定義する。この高周波成分間の前記親子関係は、一つの係数（親，親係数）に対し４つの係数（子供，子供係数）が対応する。また、最低周波数帯域ＬＬM帯域内の変換係数に対しては、例外的にＬＨM，ＨＬM，ＨＨM帯域内において該変換係数と同位置の３つの変換係数が３つの子として対応する。従って、この親子関係は最低周波数帯域ＬＬ内の各変換係数を幹（以下、「ルート」と呼ぶことがある。）とし、解像度の粗い低周波側から解像度の密な高周波側に向かって、相似な位置の変換係数に対して枝（以下、「ノード」と呼ぶことがある。）が生成され、図４に示すような木構造（以下、「ツリー」と呼ぶことがある。）が生成される。
【００１３】
先に、各変換係数の逆方向、即ちルート方向へのノードに対応する変換係数のことを親あるいは親係数と呼び、各変換係数の順方向のノードに対応する変換係数のことを子あるいは子供あるいは子供係数と呼ぶと定義したが、ここで、親子関係に基づくツリー構造に関し、以下、いくつかの言葉について定義を行う。
【００１４】
各変換係数の親係数の子供係数のことを兄弟あるいは兄弟係数と呼ぶ。例えば、図４中のＨＨ2帯域内にハッチングで示した４係数のうち、任意の１係数から見て該４係数は兄弟係数である。各変換係数の子供及び該子供の子供等、各変換係数から順方向に最後のノードまでの各変換係数を子孫と呼ぶ。
【００１５】
例えば、ＨＨ3帯域内にハッチングで示した係数から見て、ＨＨ2帯域内のハッチングで示した４係数及びＨＨ1帯域内のハッチングで示した１６係数は子孫である。また、あるツリー中の任意の変換係数及び該変換係数以下の全ての変換係数によって構成される係数群をサブツリーと定義する。サブツリーとは、即ち”変換係数＋該変換係数の子孫”である。
【００１６】
以上定義した周波数帯域間の係数ツリーを用いて、ウェーブレット変換係数に対しエントロピー符号化を行う方式として、ゼロツリー符号化（Ｊ．Ｍ．Ｓｈａｐｉｒｏ，”Ｅｍｂｅｄｄｅｄ  ｉｍａｇｅ  ｃｏｄｉｎｇ  ｕｓｉｎｇ  ｚｅｒｏｔｒｅｅｓ  ｏｆ  ｗａｖｅｌｅｔ  ｃｏｅｆｆｉｃｉｅｎｔｓ”，ＩＥＥＥ  Ｔｒａｎｓ．Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ，ｖｏｌ．４１，ｐｐ．３４４５−３４６２，Ｄｅｃ．１９９３）が提案されている。
【００１７】
ゼロツリー符号化では、あるサブツリー中の各変換係数を量子化した結果、量子化後の係数が全てゼロとなる場合、該サブツリーをゼロツリーと呼び、該サブツリーを１つのゼロツリールート（Ｚｅｒｏ  Ｔｒｅｅ  Ｒｏｏｔ：ＺＴＲ）符号に置き換えて符号化することでデータ圧縮を行う。
【００１８】
ＺＴＲ符号で置換されたサブツリーはこの時点で既に符号化済みであり、該ＺＴＲ符号の子孫を後に符号化する必要はない。また、ＺＴＲ符号とは逆に、ある変換係数自体の量子化後の値はゼロであるものの、該変換係数の子孫の係数に一つでも有意係数がある場合は、該変換係数を孤立ゼロ（Ｉｓｏｌａｔｅｄ  Ｚｅｒｏ：ＩＺ）符号として符号化データに出力する。また、符号化対象の変換係数が有意係数である場合は、ＺＴＲ符号・ＩＺ符号のいずれの条件にも合わない。この場合は、該変換係数が有意係数であることを示す符号（ＬＥＶＥＬ符号）を出力し、該有意係数の値を符号化データに出力する。
【００１９】
従って、ゼロツリー符号化において実際に可変長符号化を行うシンボルは、
・ＺＴＲ符号
・ＩＺ符号
・ＬＥＶＥＬ符号＋量子化後係数値
の３種額の符号となる。
【００２０】
図５に、ゼロツリー符号化を用いて、ＬＬ3帯域内のある変換係数をルートとするツリーを符号化する例を示す。図中の各変換係数はウェーブレット変換係数の量子化後の値であり、それぞれサブツリー（ａ）はＬＨ帯域、サブツリー（ｂ）はＨＬ帯域、サブツリー（ｃ）はＨＨ帯域内でのサブツリーである。
【００２１】
まず、ＬＬ3の係数に関し、該係数は”＋３”であるため、ＬＥＶＥＬ符号を出力し、値”＋３”を出力、即ち
・ＬＬ３帯域  （LEVEL，3）
を出力する。
【００２２】
ＬＨ帯域のサブツリーであるサブツリー（ａ）を符号化する場合は、以下のステップで符号化を行う。
【００２３】
・ＬＨ3帯域内の係数
量子化後係数は”３”であり、有意係数であるため、ＬＥＶＥＬ符号と”＋３”を符号化する。
【００２４】
・ＬＨ2帯域内の係数
−左上の量子化後係数は”−１”であり有意係数であるため、ＬＥＶＥＬ符号と”−１”を符号化する。
【００２５】
−右上の量子化後係数は”０”であるが、該係数の４つの子供の係数に有意係数”−２”が含まれている。従って、ＩＺ符号を符号化データに出力する。
【００２６】
−左下の量子化後係数は”０”であるが、該係数の４つの子供の係数に有意係数”−１，３，１”が含まれている。従って、同様にＩＺ符号を符号化データに出力する。
【００２７】
−右下の量子化後係数は”０”であり、該係数以下のサブツリー内には有意係数が存在しないので、ＺＴＲ符号を符号化データに出力する。
【００２８】
・ＬＨ1帯域内の係数
１６個の係数のうち、右下の４つの係数は上位のＺＴＲ符号により既に符号化済みであるため、その他の１２個の係数を順に符号化する。
【００２９】
実際に、以上の手順でサブツリー（ａ）を符号化した場合、結果として以下の符号、即ち
0003660548.tif 000002
を可変長符号あるいは算術符号にて符号化データに出力することとなる。
【００３０】
同様な方法によりＨＬ帯域のサブツリーであるサブツリー（ｂ）を符号化すると、ＨＬ2帯域内の二つの係数をＺＴＲ符号で符号化することとなり、結果として以下の符号、即ち
0003660548.tif 000003
を可変長符号あるいは算術符号にて符号化データに出力することとなる。
【００３１】
さらに、同様な方法でＨＨ帯域のサブツリーであるサブツリー（ｃ）を符号化する。ＨＨ3帯域内の量子化後係数は”０”であり、該量子化後係数の４つの子は全て”０”であり、さらに該４つの子に派生するサブツリーも全て”０”であるため、サブツリー（ｃ）は一つのゼロツリー符号で置換することができる。故に、
・ＨＨ３帯域  （ZTR）
の符号のみを符号化データに出力すれば良い。
【００３２】
以上の例では、ＬＨ内のサブツリー、ＨＬ内のサブツリー、ＨＨ内のサブツリーと、順に各サブツリー毎に符号化データに出力したが、実際には多様な解像度及び画質を段階的に出力する機能（スケーラビリティ）を有する符号化データを生成するために、これらを図６に示すように、インターリーブさせて符号化データに出力するのが一般的である。なお、水平方向の周波数帯域であるＨＬ帯域は先に述べたように縦方向の係数間に冗長性があるため、スキャンを縦方向に行うのが一般的である。
【００３３】
【発明が解決しようとする課題】
以上説明したゼロツリー符号化はそれなりの符号化効率を有する方式であるが、ゼロツリー符号化の符号体系には幾つかの冗長性があると考えられる。
【００３４】
（ａ）ＩＺ符号とその子供の係数
ＩＺ符号は、（１）符号化対象量子化後係数がゼロであり、（２）符号化対象量子化後係数以下のサブツリー中の係数の中に一つ以上有意係数が存在することを示す符号である。従って、ＩＺ符号の４つの子供が全てＺＴＲである可能性はない。しかし、実際にはＩＺ符号の４つの子供が全てＺＴＲとなっている符号化データを復号器で復号することが可能である。符号化器から出力されることのあり得ない符号を復号器が復号可能と言うことは、符号体系に冗長性があることとなる。
【００３５】
（ｂ）親係数の絶対値の大きさに関係なく４つの子供の係数を符号化する
ゼロツリー符号化では、ある符号化対象の量子化後係数がゼロである場合、該量子化後係数以下のサブツリー中の量子化後係数が全てゼロである可能性が高くなる性質を利用して、これを一つのＺＴＲ符号に置き換えることで圧縮を行う。
【００３６】
しかし、実際にはゼロの場合だけではなく、量子化後係数の絶対値（｜ＬＥＶＥＬ｜）が小さければ小さい程、該量子化後係数の４つの子供をルートとするサブツリーがそれぞれＺＴＲである可能性が高くなり、逆に量子化後係数の絶対値が大きい程、該量子化後係数の４つの子供がＺＴＲである可能性か低くなる。しかし、従来のゼロツリー符号化ではこの性質を利用することが困難である。
【００３７】
（ｃ）符号化対象のシンボル数が少ない
先に示したように、ゼロツリー符号化において実際に可変長符号化を行うシンボルは、わずか３つである。これら３つのシンボルの発生頻度が各々２の階乗分の１で近似できる場合は良いが、実際にはそうではない。このため、該３つのシンボルを可変長符号化する際の平均符号長が、３つのシンボルのエントロピーと比較して著しく大きくなってしまう。
【００３８】
以上述べたように、ウェーブレット変換係数をエントロピー符号化する際に、ゼロツリールート符号、孤立ゼロ符号、レベル符号を用いてゼロツリー符号化を行う方法が一般に利用されている。しかし、従来のゼロツリー符号化にはその符号体系に冗長性があるという問題があった。また、可変長符号化を用いてゼロツリー符号化を行う場合には親の係数のレベルの大きさに応じて、子供のＺＴＲ符号の発生確率を動的に変更することは極めて困難であるという問題があった。
【００３９】
本発明の目的は、入力画像信号を、サブバンド分割あるいはウェーブレット変換を用いて周波数帯域に分割し、算出された変換係数をエントロピー符号化する際に、上記問題点を解決し、符号化効率を改善できる画像符号化方法及び画像復号方法、画像符号化装置及び画像復号装置、並びにそれらのプログラムを記憶した媒体を提案することにある。
【００４０】
【課題を解決するための手段】
上記の問題点を解決するため、本発明の請求項１では、入力画像あるいは動き補償予測差分画像を符号化対象信号として符号化する画像符号化方法において、符号化対象信号を、水平及び垂直の両方向について高域と低域に周波数帯域分割し、水平及び垂直の両方向に対しての低域成分を同様に再分割し、該再分割処理を再帰的にそれぞれ指定された回数繰り返すことで符号化対象信号変換係数を算出するステップと、該符号化対象信号変換係数をそれぞれ量子化して量子化後変換係数を算出するステップと、前記各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、最低周波数帯域の係数を幹に持つ階層的な４分木構造であるツリーを形成するステップと、該ツリー中の各量子化後変換係数について、該量子化後変換係数及び該量子化後変換係数の全ての子孫が有意係数を持たない部分木であるゼロツリーを探索するステップと、前記ツリー内のある量子化後変換係数を符号化するに当たり、該量子化後変換係数の直接の子供係数のうち、該子供係数を幹とする部分木がゼロツリーである個数を示すＺカウントを算出するステップと、該量子化後変換係数の絶対値及びＺカウントからなる二次元可変長符号を符号化データに出力するステップとを有する画像符号化方法を提案する。
【００４１】
また、本発明の請求項２では、上記請求項１記載の画像符号化方法において、ある量子化後変換係数を符号化するに当たり、該量子化後変換係数の絶対値がゼロでない場合は、前記二次元可変長符号を符号化データに出力した直後に、該量子化後変換係数の正負の符号を符号化データに出力する画像符号化方法を提案する。
【００４２】
また、本発明の請求項３では、上記請求項１記載の画像符号化方法において、ツリーの幹以外の量子化後変換係数を符号化するに当たり、該量子化後変換係数の親係数の子供の係数を示す兄弟係数を検査し、該兄弟係数それぞれに対応する前記二次元可変長符号を符号化データに出力する前に、該兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を符号化データに出力する画像符号化方法を提案する。
【００４３】
また、本発明の請求項４では、上記請求項３記載の画像符号化方法において、該兄弟係数のマップ符号を出力するに当たり、該兄弟係数の親係数を符号化した際に符号化データに出力済みの該兄弟係数のＺカウントを参照し、該Ｚカウントの値が、該兄弟係数が全てゼロツリーの幹であるか、あるいは全てゼロツリーの幹ではないことを示している値である場合には前記マップ符号を符号化データに出力せず、該兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には前記マップ符号を符号化データに出力する画像符号化方法を提案する。
【００４４】
また、本発明の請求項５では、上記請求項４記載の画像符号化方法において、親係数を符号化した際に符号化データに出力済みのＺカウントが、兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合、Ｚカウントの値に対応するマップ符号用の可変長符号テーブルを用意しておき、前記親係数のＺカウントに応じて該マップ符号用の可変長符号テーブルを切り替えて符号化する画像符号化方法を提案する。
【００４５】
また、本発明の請求項６では、上記請求項３または４記載の画像符号化方法において、マップ符号を符号化データに出力した後に、前記親係数を符号化した際に符号化データに出力済みの兄弟係数のうちのゼロツリーの幹ではない係数の数だけ、該ゼロツリーの幹ではない係数の二次元可変長符号及び請求項２記載の条件に応じて前記正負の符号を符号化データに出力する画像符号化方法を提案する。
【００４６】
また、本発明の請求項７では、上記請求項３記載の画像符号化方法において、該４つの兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を生成するに当たり、該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に該４つの兄弟係数がゼロツリーの幹であるかどうかを調べる画像符号化方法を提案する。
【００４７】
また、本発明の請求項８では、上記請求項１乃至７いずれか記載の画像符号化方法による符号化データを復号する方法であって、
ある係数を復号対象係数として復号するに当たり、該復号対象係数の親係数を復号した際に復号済みの該復号対象係数の兄弟係数のＺカウントを取り出すステップと、該兄弟係数のＺカウントが、該兄弟係数の全てがゼロツリーの幹ではないかあるいは全てがゼロツリーの幹であることを示す場合は、マップ符号を復号せず、兄弟係数のうちのいくつかはゼロツリーの幹でいくつかはゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のＺカウントの値に応じて可変長符号化テーブルを切り替えてマップ符号を復号するステップと、該マップ符号によりゼロツリーの幹ではないと示されている兄弟係数について、それぞれ、該兄弟係数の子供係数のＺカウント及び復号対象係数の絶対値からなる二次元可変長符号を復号し、復号された該絶対値がゼロでない場合は該復号対象係数の正負の符号を復号し、該絶対値及び該正負の符号より復号係数値を算出し、同時に該兄弟係数の子供係数を復号する際に利用するために該Ｚカウントを記録するステップと、該マップ符号によりゼロツリーの幹であると示されている兄弟係数については、ゼロツリーの幹の場所情報を記録するステップと、それぞれ算出された兄弟係数の該復号係数値を該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に復号係数メモリに記録するステップとを有する画像復号方法を提案する。
【００４８】
また、本発明の請求項９では、入力画像あるいは動き補償予測差分画像を符号化対象信号として符号化する画像符号化装置において、符号化対象信号を、水平及び垂直の両方向について高域と低域に周波数帯域分割し、水平及び垂直の両方向に対しての低域成分を同様に再分割し、該再分割処理を再帰的にそれぞれ指定された回数繰り返すことで符号化対象信号変換係数を算出する手段と、該符号化対象信号変換係数をそれぞれ量子化して量子化後変換係数を算出する手段と、前記各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、最低周波数帯域の係数を幹に持つ階層的な４分木構造であるツリーを形成する手段と、該ツリー中の各量子化後変換係数について、該量子化後変換係数及び該量子化後変換係数の全ての子孫が有意係数を持たない部分木であるゼロツリーを探索する手段と、前記ツリー内のツリーの幹以外のある量子化後変換係数及び該量子化後変換係数の親係数の子供の係数を示す兄弟係数を符号化するに当たり、該兄弟係数を幹とする部分木がゼロツリーである個数を示すＺカウントが、該兄弟係数が全てゼロツリーの幹であるかあるいは全てゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を符号化データに出力せず、該兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に該４つの兄弟係数がゼロツリーの幹であるかどうかを調べて、該兄弟係数のＺカウントに応じて可変長符号化テーブルを切り替えつつ、該兄弟係数に対応するマップ符号を符号化データに出力する手段と、該兄弟係数のうちのゼロツリーの幹ではない変換係数に関し、該変換係数の直接の子供係数のＺカウントを算出し、該変換係数の絶対値及びＺカウントからなる二次元可変長符号を符号化データに出力する手段と、  該絶対値がゼロでない場合は、該二次元可変長符号の後に該変換係数の正負の符号を符号化データに出力する手段とを有する画像符号化装置を提案する。
【００４９】
また、本発明の請求項１０では、請求項９記載の画像符号化装置による符号化データを復号する装置であって、
ある係数を復号対象係数として復号するに当たり、該復号対象係数の親係数を復号した際に復号済みの該復号対象係数の兄弟係数のＺカウントを取り出す手段と、該兄弟係数のＺカウントが、該兄弟係数の全てがゼロツリーの幹ではないかあるいは全てがゼロツリーの幹であることを示す場合は、マップ符号を復号せず、兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のＺカウントの値に応じて可変長符号化テーブルを切り替えてマップ符号を復号する手段と、該マップ符号によりゼロツリーの幹ではないと示されている兄弟係数について、それぞれ、該兄弟係数の子供係数のＺカウント及び復号対象係数の絶対値からなる二次元可変長符号を復号し、復号された該絶対値がゼロでない場合は該復号対象係数の正負の符号を復号し、該絶対値及び該正負の符号より復号係数値を算出し、同時に該兄弟係数の子供係数を復号する際に利用するために該Ｚカウントを記録する手段と、該マップ符号によりゼロツリーの幹であると示されている兄弟係数については、ゼロツリーの幹の場所情報を記録する手段と、それぞれ算出された兄弟係数の該復号係数値を該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に復号係数メモリに記録する手段とを有する画像復号装置を提案する。
【００５０】
また、本発明の請求項１１では、入力画像あるいは動き補償予測差分画像を符号化対象信号として符号化する画像符号化プログラムを記憶した媒体であって、
前記プログラムはコンピュータに読み取られた際、該コンピュータ上に、
符号化対象信号を、水平及び垂直の両方向について高域と低域に周波数帯域分割し、水平及び垂直の両方向に対しての低域成分を同様に再分割し、該再分割処理を再帰的にそれぞれ指定された回数繰り返すことで符号化対象信号変換係数を算出する手段と、該符号化対象信号変換係数をそれぞれ量子化して量子化後変換係数を算出する手段と、前記各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、最低周波数帯域の係数を幹に持つ階層的な４分木構造であるツリーを形成する手段と、該ツリー中の各量子化後変換係数について、該量子化後変換係数及び該量子化後変換係数の全ての子孫が有意係数を持たない部分木であるゼロツリーを探索する手段と、前記ツリー内のツリーの幹以外のある量子化後変換係数及び該量子化後変換係数の親係数の子供の係数を示す兄弟係数を符号化するに当たり、該兄弟係数を幹とする部分木がゼロツリーである個数を示すＺカウントが、該兄弟係数が全てゼロツリーの幹であるかあるいは全てゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のうちのどの係数がゼロツリーの幹であるかを示すマップ符号を符号化データに出力せず、該兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に該４つの兄弟係数がゼロツリーの幹であるかどうかを調べて、該兄弟係数のＺカウントに応じて可変長符号化テーブルを切り替えつつ、該兄弟係数に対応するマップ符号を符号化データに出力する手段と、該兄弟係数のうちのゼロツリーの幹ではない変換係数に関し、該変換係数の直接の子供係数のＺカウントを算出し、該変換係数の絶対値及びＺカウントからなる二次元可変長符号を符号化データに出力する手段と、該絶対値がゼロでない場合は、該二次元可変長符号の後に該変換係数の正負の符号を符号化データに出力する手段とを構成する画像符号化プログラムを記憶した媒体を提案する。
【００５１】
また、本発明の請求項１２では、請求項９記載の画像符号化装置もしくはコンピュータ及び請求項１１記載の画像符号化プログラムを記憶した媒体によって実現される画像符号化装置による符号化データを復号する画像復号プログラムを記憶した媒体であって、
前記プログラムはコンピュータに読み取られた際、該コンピュータ上に、
ある係数を復号対象係数として復号するに当たり、該復号対象係数の親係数を復号した際に復号済みの該復号対象係数の兄弟係数のＺカウントを取り出す手段と、該兄弟係数のＺカウントが、該兄弟係数の全てがゼロツリーの幹ではないかあるいは全てがゼロツリーの幹であることを示す場合は、マップ符号を復号せず、兄弟係数のうちのいくつかはゼロツリーの幹で、いくつかはゼロツリーの幹ではないことを示している値である場合には、該兄弟係数のＺカウントの値に応じて可変長符号化テーブルを切り替えてマップ符号を復号する手段と、該マップ符号によりゼロツリーの幹ではないと示されている兄弟係数について、それぞれ、該兄弟係数の子供係数のＺカウント及び復号対象係数の絶対値からなる二次元可変長符号を復号し、復号された該絶対値がゼロでない場合は該復号対象係数の正負の符号を復号し、該絶対値及び該正負の符号より復号係数値を算出し、同時に該兄弟係数の子供係数を復号する際に利用するために該Ｚカウントを記録する手段と、該マップ符号によりゼロツリーの幹であると示されている兄弟係数については、ゼロツリーの幹の場所情報を記録する手段と、それぞれ算出された兄弟係数の該復号係数値を該４つの兄弟係数が垂直方向の帯域内である場合には左上、右上、左下、右下の順に、水平方向の帯域内である場合には左上、左下、右上、右下の順に、対角方向の帯域内である場合には左上、右下、右上、左下あるいは左上、右下、左下、右上の順に復号係数メモリに記録する手段とを構成する画像復号プログラムを記憶した媒体を提案する。
【００５２】
本発明によれば、符号化対象係数の絶対値と、該符号化対象係数の子供係数を幹とするゼロツリーの個数を用いた二次元可変長符号化を用いて、ウェーブレット変換係数をエントロピー符号化することにより、符号体系に冗長性がない状態で符号化することができる。さらに、子供係数を幹とするサブツリーがＺＴＲである場合、親係数の値の大きさに応じて、子供係数以下のサブツリーを効率的に打ち切ることが可能となり、エントロピー符号化の符号化効率を改善することが可能となる。
【００５３】
【発明の実施の形態】
以下、本発明の実施の形態について説明する。
【００５４】
図７は本発明に関わる画像符号化方法及び装置の全体を示すもので、図中、１はウェーブレット変換部、２は量子化部、３は係数符号化部、４はスキャン部である。
【００５５】
入力画像あるいは動き補償予測差分画像等の符号化対象信号５は、ウェーブレット変換部１にて、水平及び垂直の両方向について高域と低域に周波数帯域分割され、水平及び垂直の両方向に対しての低域成分が同様に再分割され、該再分割処理が再帰的にそれぞれ指定された回数繰り返されることで符号化対象信号変換係数６として出力される。符号化対象信号変換係数６は、量子化部２にて量子化され、量子化後変換係数７として係数符号化部３に出力される。
【００５６】
スキャン部４では最低周波数帯域ＬＬから順に、高周波数帯域ＨＬ1，ＬＨ1，ＨＨ1の方向にスキャンを行い、そのスキャンの過程でその係数位置を符号化対象係数位置８として同様に係数符号化部３に出力する。各周波数帯域内での係数スキャンの順番は、以下の４つの条件を満たしてスキャンを行う。
【００５７】
１．各周波数帯域内では、最低周波数帯域ＬＬ内の変換係数をルートとする同一のツリーに属する係数群を一単位としてスキャンする。
【００５８】
２．該同一ツリー内の係数の中でも、各４つの兄弟係数をひとまとめにしてスキャンする。
【００５９】
３．該４つの兄弟係数内の中では、
・垂直方向の周波数帯域では、左上、右上、左下、右下の順
・水平方向の周波数帯域では、左上、左下、右上、右下の順
・対角方向の周波数帯域では、左上、右下、右上、左下あるいは左上、右下、左下、右上の順
に係数をスキャンする。
【００６０】
４．各４つの兄弟係数間及び同一ツリーに属する係数群間は、
・垂直方向の周波数帯域では、水平方向に
・水平方向の周波数帯域では、垂直方向に
優先してスキャンを行う。
【００６１】
スキャンの一例を、図８に示す。厳密に図８に示す順に係数をスキャンする必要はないが、少なくとも先に示したスキャンの条件を満たし、かつ画像符号化装置及び画像復号装置で同じ順にスキャンを行えば良い。
【００６２】
係数符号化部３では、入力された量子化後変換係数７を、符号化対象係数位置８に示される順にスキャンしながら符号化し、符号化データ９として出力する。
【００６３】
本発明における符号化処理は、係数符号化処理を行う係数符号化部３に関わるものであり、ウェーブレット変換部１及び量子化部２は、従来と同様の手法で良い。従って、以下、係数符号化部３について説明する。なお、ウェーブレット変換による周波数帯域の再帰分割処理を３回行う場合を想定して説明するが、一般に、帯域分割の回数をＮ回とした場合も本発明を同様に適用できることは明白である。
【００６４】
図９は本発明による係数符号化処理及び係数符号化部の実施の形態の一例を示すもので、図中、１１はゼロツリー生成部、１２はゼロツリーメモリ、１３は絶対値・符号分離部、１４は二次元可変長符号化部、１５は選択器、１６は子供係数位置算出部、１７は子供係数検査部、１８はマップ符号生成部、１９は遅延器、２０は多重化部である。
【００６５】
前述した量子化後変換係数７は、ゼロツリー生成部１１に入力される。ゼロツリー生成部１１では、まず、各周波数帯域間で空間的に相似な位置として対応する量子化後変換係数間で、垂直成分・水平成分・対角成分の各成分毎に、図４に示したような最低周波数帯域の係数をルートに持つ階層的なツリーをそれぞれ形成する。そして、該ツリー中の任意の変換係数について、該変換係数をルートとするサブツリーが全てゼロであるサブツリーを探索する。この探索処理を最低周波数帯域の係数をルートに持つ全てのツリー中の全変換係数に関して行い、どの変換係数がゼロツリーのルート係数（ゼロツリールート）であるか、あるいは既にゼロツリーにより打ち切られている係数であるかを示す情報をゼロツリー情報２１として、ゼロツリーメモリ１２に出力する。
【００６６】
同時に、量子化後変換係数７及びスキャン部４より与えられる符号化対象係数位置８が、絶対値・符号分離部１３に入力される。絶対値・符号分離部１３では、量子化後変換係数７のうちの符号化対象係数位置８の位置にある変換係数が取り出され、これを符号化対象係数として符号化するに当たり、該符号化対象係数の絶対値が絶対値２２として二次元可変長符号化部１４に、該符号化対象係数の正負の符号が符号２３として選択器１５に出力される。
【００６７】
符号化対象係数位置８は、子供係数位置算出部１６にも入力され、ここで該符号化対象係数の子供係数の位置が算出され、子供係数位置２４は子供係数検査部１７に出力される。該符号化対象係数の属する周波数帯域毎に異なるが、一つの親に対し子供係数位置２４としては３つあるいは４つの係数位置が示される。
【００６８】
同様に、子供係数検査部１７には、ゼロツリーメモリ１２より、量子化後変換係数７のゼロツリーの情報であるゼロツリー情報２５が入力され、該ゼロツリー情報２５のうち、該子供係数位置２４により示される位置にあるゼロツリー情報を子供係数ゼロツリー情報として取り出す。そして、該子供係数ゼロツリー情報のうち、ゼロツリールートである個数をＺカウント２６として二次元可変長符号化部１４に出力し、同時にどの子供係数がゼロツリールートで、どの子供係数がゼロツリールートでないか等の情報を、子供係数マップ情報２７としてマップ符号生成部１８に出力する。
【００６９】
この時、該子供係数のスキャンの順は、各水平・垂直・対角方向の周波数帯域内の係数間の特性を利用するため、該子供係数が、垂直方向の周波数帯域内の時は左上、右上、左下、右下の順、水平方向の周波数帯域内の時は左上、左下、右上、右下の順、対角方向の周波数帯域内の時は左上、右下、右上、左下あるいは左上、右下、左下、右上の順とする。
【００７０】
マップ符号生成部１８では、入力された子供係数マップ情報２７を元に子供係数の符号化の際に出力するマップ符号２８を生成する。表１はマップ符号の符号化テーブルの一例を示すもので、子供係数が４つある帯域に対応する。マップ符号の符号化テーブルは、Ｚカウントの値毎に用意されており、該符号化対象係数の兄弟係数のＺカウントに応じて、該兄弟係数のＺカウントに対応する符号化テーブルを切り替えて用いてマップ符号を生成する。また、Ｚカウントが２の場合は兄弟係数のスキャン順を水平方向・垂直方向・対角方向の周波数帯域毎に各周波数帯域の特性を利用したスキャンを行っているため、マップ符号ｍａｐ４［０，０，１，１］、ｍａｐ４［１，１，０，０］には短い符号長の符号を割り当てることができる。また、Ｚカウントが”０”、即ち兄弟係数の全てがゼロツリールートではない場合、あるいはＺカウントが“４”、即ち兄弟係数の全てがゼロツリールートである場合は、マップ符号を出力する必要はなく、マップ符号３１として空の符号を出力する。表１では”符号化不要”と表した。
【００７１】
【表１】
0003660548.tif 000004
【００７２】
該符号化テーブルを用いて算出されたマップ符号２８は、該符号化対象係数の子供係数を符号化する時に多重化して符号化データに出力するため、遅延器１９に出力しておく。
【００７３】
二次元可変長符号化部１４では、絶対値・符号分離部１３より入力された絶対値２２及び子供係数検査部１７より入力されたＺカウント２６を二次元可変長符号化データ２９として符号化し、多重化部２０に出力する。ＬＨ1,2，ＨＬ1,2，ＨＨ1,2帯域等、子供係数が４つある帯域を符号化する際に用いる二次元可変長符号（ＴＤＶＬＣ４）の例を表２に示す。表２には、絶対値がゼロでＺカウントが４つ、即ちゼロツリールートの場合の二次元可変長符号を示していない。しかし、ゼロツリーの場所は、親係数を符号化した際のＺカウントと、該二次元可変長符号の前に符号化するマップ符号により一意に特定可能であるため、ゼロツリールートの符号を用意する必要がないためである。
【００７４】
【表２】
0003660548.tif 000005
【００７５】
選択器１５では、絶対値２２により示される該符号化対象係数の絶対値がゼロではない場合、符号２３により示される該符号化対象係数の正負の符号を、正負符号データ３０として多重化部２０に出力する。
【００７６】
多重化部２０では、遅延器１９より入力されるマップ符号３１、二次元可変長符号化データ２９、そして正負符号データ３０を多重化して符号化データ９として出力する。遅延器１９を介して入力されるマップ符号３１は該符号化係数を含む兄弟符号のゼロツリー情報が含まれており、二次元可変長符号化データ２９及び正負符号データ３０は該符号化係数を含む兄弟符号毎の符号化データである。
【００７７】
多重化部２０では、以下の手順で多重化を行う。
【００７８】
・符号化対象係数の親係数を符号化する際に算出されたマップ符号３１を符号化データに出力。（親係数のＺカウントの値が、兄弟係数の全てがゼロツリールートであるか、あるいは全てがゼロツリールートでないことを示す値である場合には、先に述べたようにマップ符号３１には何も入っていない）
・マップ符号３１により、ゼロツリールートではないと判断される各兄弟係数毎に以下の２つの符号化データを順に符号化データに出力。（符号化対象係数の絶対値がゼロである場合には、選択器１５により正負符号データ３０には何も入っていない）
−二次元可変長符号化データ２９
−正負符号データ３０
従って、以下の４係数からなる、垂直方向の周波数帯域内のある兄弟係数を符号化すると、図１０に示す多重化された符号を符号化データとして出力することとなる。
【００７９】
１．左上がＺＴＲ、
２．右上の量子化後変換係数が−１で、子供係数のＺカウントが４つ、
３．左下の量子化後変換係数が３で、子供係数のＺカウントが０、
４．右下の量子化後変換係数が０で、子供係数のＺカウントが３つ
この例では、表１及び表２に示した符号化テーブルを用いている。
【００８０】
以下、本発明を用いて図５に示した変換係数ツリーを符号化する例を示す。
【００８１】
・ＬＬ3帯域内の係数
ＬＬ帯域内の符号化対象である量子化後変換係数は”＋３”であり、３つの子供係数のうち、ＨＨ3帯域内の子供係数がＺＴＲである。本方式では、量子化後変換係数の絶対値と、該量子化後変換係数の子供の係数のうちの該子供係数が幹となるゼロツリーである個数、即ちＺカウントからなる、二次元可変長符号（ＴＤＶＬＣ３［変換係数の絶対値，Ｚカウント］）を符号化データに出力する。ＴＤＶＬＣ３は兄弟係数が３つの場合の二次元可変長符号であり、表２に示したＴＤＶＬＣ４とは別に画像符号化装置／画像復号装置に用意しておく。但し、ＬＬ係数には親係数が存在しないため、親係数でＺカウントを符号化していない。従って、ＴＤＶＬＣ４とは異なり、ＴＤＶＬＣ３は絶対値が０で、３つの子供が全てゼロツリールートである符号も用意しておく必要がある。
【００８２】
また、該二次元可変長符号を符号化データに出力した後に、該量子化後変換係数の正負の符号を出力する。”＋３”の符号は正であるため、正の符号を出力する。以下、正の符号をＰＯＳ、負の符号をＮＥＧと記載する。従って、本例では、ＬＬ帯域の符号化に当たり、
（ＴＤＶＬＣ３［３，１］）（ＰＯＳ）
という符号を出力する。
【００８３】
・ＬＨ3，ＨＬ3，ＨＨ3帯域内の係数
ＬＨ3帯域内の符号化対象である量子化後変換係数は”＋３”である。ＨＬ3帯域内の符号化対象である量子化後変換係数は”０”である。ＨＨ3帯域内の符号化対象である量子化後変換係数は”０”であり、また、ゼロツリールートである。
【００８４】
また、ＬＬ3帯域内にある上記３係数の親係数を符号化する際に出力したＺカウントは１である。従って、マップ符号としてｍａｐ３［０，０，１］を出力する。表３はマップ符号用ｍａｐ３［］の符号化テーブルの一例を示しており、兄弟係数が互いに３つあるＬＨ3，ＨＬ3，ＨＨ3帯域を符号化する際に用いる。
【００８５】
なお、該Ｚカウントが３の時は３つの兄弟係数が全てゼロツリールートであることを示し、また、該Ｚカウントが０の時は３つの兄弟係数が全てゼロツリールートでないことを示すため、マップ符号を符号化データに出力する必要はない。
【００８６】
【表３】
0003660548.tif 000006
【００８７】
次に、ＬＨ3，ＨＬ3，ＨＨ3帯域内の３係数に対応する二次元可変長符号を出力する。
【００８８】
ＬＨ3内の符号化対象係数は”＋３”であり、４つの子供のうち、ＺＴＲは一つであるため、ＴＤＶＬＣ４［３，１］及び正の符号ＰＯＳを出力する。
【００８９】
ＨＬ3内の符号化対象係数は”０”であり、４つの子供のうち、ＺＴＲは二つであるため、ＴＤＶＬＣ４［０，２］を出力する。該符号化対象係数の絶対値はゼロであるため、正負の符号を出力する必要はない。
【００９０】
ＨＨ3内の符号化対象係数は、親係数を符号化した際のＺカウント及び先に出力したマップ符号により、既に符号化済みである。
【００９１】
従って、本例では、ＬＨ3，ＨＬ3，ＨＨ3帯域の符号化に当たり、
ｍａｐ３［０，０，１］
（ＴＤＶＬＣ４［３，１］）（ＰＯＳ）
（ＴＤＶＬＣ４［０，２］）
という符号を出力する。なお、二次元可変長符号ＴＤＶＬＣ４として、表２に示した符号化テーブルを用いる。
【００９２】
・ＬＨ2，ＨＬ2，ＨＨ2帯域内の係数
ＬＨ2帯域内の係数を符号化するに当たり、ＬＨ3帯域内に存在する親係数を符号化した際に出力したＺカウントは”１”であり、また、ＬＨ2帯域内の兄弟係数のうちのゼロツリールートは右下の係数である。また、ＬＨ3周波数帯域は垂直方向の周波数帯域であるため、左上、右上、左下、右下の順に兄弟係数をスキャンする。さらに、左上の係数の子供係数のＺカウントは２、右上の係数の子供係数のＺカウントは３、左下の係数の子供係数のＺカウントは１である。
【００９３】
同様にＨＬ2帯域については、ＨＬ3帯域内に存在する親係数を符号化した際に出力したＺカウントは”２”であり、また、ＨＬ2帯域内の兄弟係数のうちのゼロツリールートは左上及び右上の係数である。ＨＬ3周波数帯域は水平方向の周波数帯域であるため、左上、左下、右上、右下の順に兄弟係数をスキャンする。さらに、左下の係数の子供係数のＺカウントは１、右下の係数の子供係数のＺカウントは３である。
【００９４】
同様にＨＨ2帯域については、ＨＨ3帯域の時と同様、既にゼロツリーにより打ち切られているため、符号化不要である。
【００９５】
従って、本例では、ＬＨ2，ＨＬ2，ＨＨ2帯域の符号化に当たり、
ｍａｐ４［０，０，０，１］
（ＴＤＶＬＣ４［１，２］）（ＮＥＧ）
（ＴＤＶＬＣ４［０，３］）
（ＴＤＶＬＣ４［０，１］）
ｍａｐ４［１，０，１，０］
（ＴＤＶＬＣ４［１，１］）（ＮＥＧ）
（ＴＤＶＬＣ４［０，３］）
という符号を出力する。マップｍａｐ４［］は、表１に示した符号化テーブルを用いる。
【００９６】
・ＬＨ1，ＨＬ1，ＨＨ1帯域内の係数
ＬＨ1，ＨＬ1，ＨＨ1帯域内の係数には子供係数が存在しないため、絶対値と子供係数のＺカウントの二次元可変長を用いる本発明を適用して符号化を行うことはできない。従って、従来のゼロツリー符号化と同様の絶対値を入力シンボルとする一次元可変長符号を用いて符号化を行う。但し、ゼロツリー符号化とは異なり、親係数の符号化の際に兄弟係数のゼロツリーの数は符号化データに記述済みであるため、マップ符号と前記一次元可変長符号を用いて符号化すれば良い。
【００９７】
具体的には、
・ＬＨ１帯域
ｍａｐ４［１，０，０，１］，
（LEVEL，1），（LEVEL，2），
ｍａｐ４［０，１，１，１］，
（LEVEL，-2），
ｍａｐ４［１，０，０，０］，
（LEVEL，-1），（LEVEL，3），（LEVEL，1）
・ＨＬ１帯域
ｍａｐ４［１，０，０，０］，
（LEVEL，-2），（LEVEL，-1），（LEVEL，1），
ｍａｐ４［０，１，１，１］，
（LEVEL，-1）
・ＨＨ１帯域
符号化不要
という符号を出力する。
【００９８】
次に、本発明による画像復号処理について詳細に説明する。
【００９９】
図１１は本発明に関わる画像復号方法及び装置の全体を示すもので、図中、４１は係数復号部、４２は逆量子化部、４３はウェーブレット逆変換部である。
【０１００】
画像復号装置では、まず、始めに符号化データ４４が係数復号部４１に入力され、復号処理が行われて、量子化後変換係数４５が出力される。量子化後変換係数４５は逆量子化部４２に入力され、画像符号化装置の量子化部２での処理に対応する逆量子化が行われ、復号変換係数４６がウェーブレット逆変換部４３に出力される。
【０１０１】
ウェーブレット逆変換部４３では、ウェーブレット最大分割回数４７により示される回数に従って、復号変換係数４６に対して逆ウェーブレット変換が再帰的に行われ、復号信号４８が出力される。ウェーブレット再帰分割回数４７は、画像符号化装置・画像復号装置において前もって回数を決定しておくことで、符号化データ４４に記載する必要はなくなる。
【０１０２】
本発明における復号処理は、係数復号処理を行う係数復号部４１に関わるものであり、逆量子化部４２及びウェーブレット逆変換部４３は、従来と同様の手法で良い。従って、以下、係数復号部４１について説明する。
【０１０３】
図１２は本発明による係数復号処理及び係数復号部の実施の形態の一例を示すもので、図中、５１は分離部、５２は選択器、５３はゼロツリーメモリ、５４は二次元可変長復号部、５５は遅延器、５６は絶対値・符号合成部、５７は選択器、５８は係数メモリ、５９はスキャン部、６０はマップ符号復号部、６１は子供係数位置算出部である。
【０１０４】
入力された符号化データ４４は分離部５１に入力され、マップ符号データ７１、絶対値データ７２及び正負の符号７３に分離される。
【０１０５】
絶対値データ７２は選択器５２に入力される。選択器５２では、ゼロツリーメモリ５３より入力されるゼロツリー情報７４により、ゼロツリーにより既に符号済みの係数でない場合は絶対値データ７２を二次元可変長復号部５４に出力する。
【０１０６】
二次元可変長復号部５４では、表２等の画像符号化装置と共通の二次元可変長符号の符号化テーブルを用いて復号を行い、Ｚカウント７５を遅延器５５に、絶対値７６を絶対値・符号合成部５６に出力する。
【０１０７】
正負の符号７３は選択器５７に入力される。選択器５７は、ゼロツリー情報７４により現在復号している係数がゼロツリーにより既に符号化済みではなく、かつ絶対値７６がゼロでない場合は、正負の符号７３を絶対値・符号合成部５６に出力する。
【０１０８】
絶対値・符号合成部５６では、絶対値７６及び正負の符号７３より復号係数７７を算出し、これを係数メモリ５８に出力する。
【０１０９】
係数メモリ５８では、スキャン部５９より出力される復号係数位置７８により示される位置に復号係数７７を記録し、復号が全ての係数について終了した後に、量子化後変換係数４５として出力する。
【０１１０】
スキャン部５９は画像符号化装置におけるスキャン部４と同様な順でスキャン位置を算出する回路であり、スキャン部５９より出力される復号係数位置７８は画像符号化装置における符号化対象係数位置８と同様の種類の値である。
【０１１１】
マップ符号データ７１は、マップ符号復号部６０に入力され、Ｚカウント７９に応じて可変長符号化テーブルを切り替えて用いてマップ符号８０を復号する。ここにおいてＺカウント７９は遅延器５５より入力されており、先に親係数を二次元可変長復号部５４にて復号した際の子供係数のＺカウント、即ち現在復号している係数の兄弟係数のＺカウントである。
【０１１２】
マップ符号復号部６０では、係数符号化部におけるマップ符号生成部１８における処理に対応する処理を行う。Ｚカウント７９が”０”、即ち兄弟係数の全てがゼロツリールートではない場合、あるいはＺカウント７９が兄弟係数の全てがゼロツリールートであることを示す場合は、マップ符号データ７１を復号することなくマップ符号８０を生成し、ゼロツリーメモリ５３に出力する。それ以外の場合、即ちＺカウント７９が兄弟係数のうちのいくつかはゼロツリールートで、いくつかはゼロツリールートではないことを示している値である場合には、マップ符号データ７１を復号し、マップ符号８０をゼロツリーメモリ５３に出力する。
【０１１３】
また、復号係数位置７８は同時に子供係数位置算出部６１に入力され、ここで係数符号化部における子供係数位置算出部１６と同様に子供係数の位置が算出され、子供係数位置８１としてゼロツリーメモリ５３に出力する。
【０１１４】
ゼロツリーメモリ５３では、子供係数位置８１の位置にマップ符号８０に従いゼロツリー情報を記録し、後に子供係数を復号する際に用いる。この時、該兄弟係数が属する周波数帯域が垂直方向の周波数帯域の時は左上、右上、左下、右下の順、水平方向の周波数帯域の時は左上、左下、右上、右下の順、対角方向の周波数帯域の時は左上、右下、右上、左下あるいは左上、右下、左下、右上の順に前記ゼロツリー情報をゼロツリーメモリ５３に記録する。さらに、ゼロツリールートである係数の子孫には、既に符号化済みであるという情報を記録しておく。
【０１１５】
なお、本発明は、コンピュータ読み取り可能な媒体であって、コンピュータに読み取られた時、該コンピュータ上に、図７及び図９並びに図１０及び図１１に示した装置を構成するプログラム（ソフトウェア）を記憶した媒体によっても実現可能である。
【０１１６】
【発明の効果】
Ｊ．Ｍ．Ｓｈａｐｉｒｏらによる従来のゼロツリー符号化では、その符号体系に冗長性があり、親の係数のレベルの大きさに応じて、子供のＺＴＲ符号の発生確率を動的に変更することは、極めて困難である。
【０１１７】
これに対して、本発明によれば、その存在自体が冗長である孤立ゼロ符号を用いる必要がなく、また、親係数の絶対値に応じて子供係数にゼロツリールートが発生する確率が変動する特性を効率的に利用して符号化を行えるため、符号化効率を改善することが可能となる。
【図面の簡単な説明】
【図１】離散ウェーブレット変換の概要を示す説明図
【図２】画像のオクターブ分割のようすを示す説明図
【図３】分解フィルタ及び合成フィルタの係数の相互関係を示す説明図
【図４】画像の二次元オクターブ分割のようすを示す説明図
【図５】ゼロツリー符号化を用いた符号化の一例を示す説明図
【図６】スケーラビリティを有する符号化データの生成のようすを示す説明図
【図７】本発明に関わる画像符号化方法及び装置全体の実施の形態の一例を示す構成図
【図８】本発明によるスキャンの一例を示す説明図
【図９】本発明の係数符号化部の実施の形態の一例を示す構成図
【図１０】符号化データ出力の一例を示す説明図
【図１１】本発明に関わる画像復号方法及び装置全体の実施の形態の一例を示す構成図
【図１２】本発明の係数復号部の実施の形態の一例を示す構成図
【符号の説明】
１：ウェーブレット変換部、２：量子化部、３：係数符号化部、４：スキャン部、１１：ゼロツリー生成部、１２：ゼロツリーメモリ、１３：絶対値・符号分離部、１４：二次元可変長符号化部、１５：選択器、１６：子供係数位置算出部、１７：子供係数検査部、１８：マップ符号生成部、１９：遅延器、２０：多重化部、４１：係数復号部、４２：逆量子化部、４３：ウェーブレット逆変換部、５１：分離部、５２：選択器、５３：ゼロツリーメモリ、５４：二次元可変長復号部、５５：遅延器、５６：絶対値・符号合成部、５７：選択器、５８：係数メモリ、５９：スキャン部、６０：マップ符号復号部、６１：子供係数位置算出部。
【図１】
0003660548.tif 000007
【図２】
0003660548.tif 000008
【図３】
0003660548.tif 000009
【図４】
0003660548.tif 000010
【図５】
0003660548.tif 000011
【図６】
0003660548.tif 000012
【図７】
0003660548.tif 000013
【図８】
0003660548.tif 000014
【図９】
0003660548.tif 000015
【図１０】
0003660548.tif 000016
【図１１】
0003660548.tif 000017
【図１２】
0003660548.tif 000018