(57)【要約】【課題】ウェーブレット変換のスケールに無関係に高い符号化効率を有するグループ化したゼロツリーウェーブレット符号化方法及び装置を提供する。【解決手段】隣接する多数のゼロツリーを結合する段階と、結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力する段階と、を含み、また入力映像を前記ゼロツリーウェーブレット変換を用いて多数のウェーブレット係数を有するウェーブレット領域に変換する段階と、前記多数のウェーブレット係数を各々有する前記隣接する多数のゼロツリーを生成する段階と、を含む。【選択図】　　　図２
2004023783.tif 000002
【特許請求の範囲】
【請求項１】
ゼロツリーウェーブレット変換を用いて、入力映像をビットストリームに符号化する方法において、
前記符号化方法は、
隣接する多数のゼロツリーを結合する段階と、
結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力する段階と、を含む、ことを特徴とする符号化方法。
【請求項２】
前記符号化方法は、
前記入力映像を、前記ゼロツリーウェーブレット変換を用いて、多数のウェーブレット係数を有するウェーブレット領域に変換する段階と、
前記多数のウェーブレット係数を各々有する、前記隣接する多数のゼロツリーを生成する段階と、を含む、ことを特徴とする請求項１に記載の符号化方法。
【請求項３】
多数のウェーブレット係数を各々有する多数のウェーブレットツリーを生成するために、ウェーブレット変換を用いて入力映像をビットストリームに符号化する方法において、
前記符号化方法は、
（ａ）各ウェーブレットツリーがゼロツリーであるか否かを判断する段階と、
（ｂ）前記ゼロツリーに隣接する前記各ウェーブレットツリーがゼロツリーであるか否かを判断する段階と、
（ｃ）前記ゼロツリーに隣接する多数のゼロツリーを結合する段階と、
（ｄ）結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力する段階と、を含む、ことを特徴とする符号化方法。
【請求項４】
前記符号化方法は、
前記（ａ）段階における判断の結果、前記各ウェーブレットツリーがゼロツリーではない場合、前記各ウェーブレットツリーに属する各ウェーブレット係数を独立的に符号化して出力する、ことを特徴とする請求項３に記載の符号化方法。
【請求項５】
前記符号化方法は、
前記（ａ）段階における判断の結果、前記ゼロツリーがただ一つである場合、前記ゼロツリーを符号化して出力する、ことを特徴とする請求項３に記載の符号化方法。
【請求項６】
請求項１に記載の符号化方法をコンピュータにて実行するためのプログラムを記録した記録媒体であって、コンピュータにて読取り可能に構成される、ことを特徴とする記録媒体。
【請求項７】
請求項３に記載の符号化方法をコンピュータにて実行するためのプログラムを記録した記録媒体であって、コンピュータにて読取り可能に構成される、ことを特徴とする記録媒体。
【請求項８】
前記記録媒体は、
前記（ａ）段階における判断の結果、前記各ウェーブレットツリーがゼロツリーではない場合、前記各ウェーブレットツリーに属する各ウェーブレット係数を独立的に符号化して出力する符号化方法をコンピュータにて実行するためのプログラムを記録した、ことを特徴とする請求項７に記載の記録媒体。
【請求項９】
前記記録媒体は、
前記（ａ）段階における判断の結果、前記ゼロツリーがただ一つである場合、前記ゼロツリーを符号化して出力する符号化方法をコンピュータにて実行するためのプログラムを記録した、ことを特徴とする請求項７に記載の記録媒体。
【請求項１０】
入力映像を、ウェーブレット変換を用いて、多数のウェーブレット係数を有するウェーブレット領域に変換するための離散ウェーブレット変換回路と、
前記多数のウェーブレット係数の同じ空間的な位置及び方向に対応する多数のゼロツリーを生成するためのゼロツリー発生器と、
隣接する多数のゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力するためのゼロツリー符号化器と、
を備える、ことを特徴とするゼロツリーウェーブレット映像符号化装置。
【請求項１１】
入力映像を、ウェーブレット変換を用いて、多数のウェーブレット係数を有するウェーブレット領域に変換するための離散ウェーブレット変換回路と、
前記多数のウェーブレット係数の同じ空間的な位置及び方向に対応するウェーブレットツリーがゼロツリーである場合、前記ゼロツリーに隣接する所定のウェーブレットゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力するためのゼロツリー符号化器と、を備える、ことを特徴とするゼロツリーウェーブレット映像符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデジタル映像信号圧縮方法及び装置に係り、より詳細には、ゼロツリーウェーブレット変換（Ｚｅｒｏ　Ｔｒｅｅ　Ｔｒａｎｓｆｏｒｍ）に基づく符号化方法及び装置に関する。
【０００２】
【従来の技術】
インターネット及びマルチメディアサービスにおいて、映像伝送及び貯蔵は必須な要素である。しかし、映像伝送及び貯蔵のためのシステムは、限られた帯域幅及びメモリを備えるため、映像符号化は、システムの性能、速度及びコスト面において重要である。
最近の映像符号化標準のうち、Ｈ．２６３は信頼性のある符号化効率を示しており、エム・ペグ（ＭＰＥＧ：Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）−４及びジェイ・ペグ（ＪＰＥＧ：Ｊｏｉｎｔ　Ｐｈｏｔｏｇｒａｐｈｉｃ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）−２０００においてはより向上した符号化効率のために各種の符号化技法が紹介されている。
【０００３】
特に、高い符号化効率を達成するために、ＭＰＥＧ−４及びＪＰＥＧ−２０００において、既存の離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍｓ）の代わりに、ウェーブレット変換（Ｗａｖｅｌｅｔ　Ｔｒａｎｓｆｏｒｍｓ）を用いた符号化技法が議論されている。
ＭＰＥＧ−４においてウェーブレット変換を用いた符号化（以下、“ウェーブレットコーディング”と称する。）は、優れたスケーラビリティ（Ｓｃａｌａｂｉｌｉｔｙ）特性により、テキスチャー符号化に採択された。また、ＪＰＥＧ−２０００において前記ウェーブレットコーディングは、各種の映像の大きさ、特に、極めて大きい映像からブロック化現象を除去して、符号化効率を極大化させるために用いられている。
【０００４】
Ｊ．Ｍ．Ｓｈａｐｉｒｏにより提案されたゼロツリー埋め込みウェーブレット符号化技法、及び、これを一層向上させたＡ．Ｓａｉｄ　及び　Ｗ．Ａ．Ｐｅａｒｌｍａｎによる階層ツリーにおける集合分割（ＳＰＩＨＴ：Ｓｅｔ　Ｐａｒｔｉｔｉｏｎｉｎｇ　Ｉｎ　Ｈｉｅｒａｒｃｈｉｃａｌ
Ｔｒｅｅｓ）方式に基づく符号化技法が、極めて優れた性能を示している。
これらの符号化技法は、図１の如きウェーブレット係数の同じ空間的な位置及び方向を用いて、多数のウェーブレット係数をゼロツリーという一つの符号で表わすことにより、圧縮効率を極大化させることができる。
【０００５】
しかしながら、一般に、離散ウェーブレット変換に基づくＭＰＥＧ−４及びＪＰＥＧ−２０００システムは固定されており、しかもウェーブレット分解の回数も固定されているため、映像の大きさが変わる場合や、または映像の特性によってウェーブレット分解の回数が変わる場合には、前記ＭＰＥＧ−４及びＪＰＥＧ−２０００システムの符号化効率は下がる。
【０００６】
【発明が解決しようとする課題】
そこで、本発明が解決しようとする技術的な課題は、ウェーブレット変換のスケールに無関係に、高い符号化効率を有するグループ化したゼロツリーウェーブレット符号化方法及び装置を提供することである。
【０００７】
【課題を解決するための手段】
本発明による、ウェーブレット変換を用いてゼロツリーをビットストリームに符号化する方法は、隣接する多数のゼロツリーを結合する段階と、結合された多数のゼロツリーを一つのシンボルに符号化して出力する段階と、を含む。
【０００８】
前記符号化方法は、前記入力映像をウェーブレット変換を用いて多数のウェーブレット係数を有するウェーブレット領域に変換する段階と、前記多数のウェーブレット係数を各々有する前記多数のゼロツリーを生成する段階と、を含む。
【０００９】
本発明による、多数のウェーブレット係数を各々有する多数のウェーブレットツリーを生成するために、ウェーブレット変換を用いて入力映像をビットストリームに符号化する方法は、（ａ）各ウェーブレットツリーがゼロツリーであるか否かを判断する段階と、（ｂ）前記ゼロツリーに隣接する前記各ウェーブレットツリーもゼロツリーであるか否かを判断する段階と、（ｃ）前記ゼロツリーに隣接する多数のゼロツリーを結合する段階と、（ｄ）結合された多数のゼロツリーを一つのシンボルに符号化して出力する段階と、を含む。
【００１０】
前記符号化方法は、前記（ａ）段階における判断の結果、前記各ウェーブレットツリーがゼロツリーではない場合、前記各ウェーブレットツリーに属する各ウェーブレット係数を独立的に符号化して出力するか、あるいは、前記符号化方法は、前記（ａ）段階における判断の結果、前記ゼロツリーがただ一つである場合、前記ゼロツリーを符号化して出力する。
【００１１】
本発明による符号化方法をコンピュータにて実行するためのプログラムを記録した、コンピュータにて読取り可能な記録媒体において、前記符号化方法は、ゼロツリーウェーブレット変換を用いて入力映像をビットストリームに符号化する方法であって、前記符号化方法は、隣接する多数のゼロツリーを結合する段階と、結合された多数のゼロツリーを一つのシンボルに符号化して出力する段階と、を含む。
【００１２】
本発明によるゼロツリーウェーブレット映像符号化装置は、入力映像をウェーブレット変換を用いて多数のウェーブレット係数を有するウェーブレット領域に変換するための離散ウェーブレット変換回路と、前記多数のウェーブレット係数の同じ空間的な位置及び方向に対応する多数のゼロツリーを生成するためのゼロツリー発生器と、隣接する多数のゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力するためのゼロツリー符号化器と、を備える。
【００１３】
また、本発明によるゼロツリーウェーブレット映像符号化装置は、入力映像をウェーブレット変換を用いて、多数のウェーブレット係数を有するウェーブレット領域に変換するための離散ウェーブレット変換回路と、前記多数のウェーブレット係数の同じ空間的な位置及び方向に対応するウェーブレットツリーがゼロツリーである場合、前記ゼロツリーに隣接する所定のウェーブレットゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力するためのゼロツリー符号化器と、を備える。
【００１４】
【発明の実施の形態】
本発明と本発明の動作上の利点、及び本発明の実施によって達成される目的、を十分に理解するためには、本発明の好適な実施の形態を例示する添付図面及び添付図面に記載された内容を参照しなければならない。
以下、添付した図面に基づき、本発明の好適な実施の形態を説明することによって、本発明を詳細に説明する。各図面に提示された同じ参照符号は同じ構成要素を表わす。
【００１５】
図２は、本発明によるアルゴリズムを説明するためのウェーブレット係数のツリー構造及び記号を示す。本発明によるアルゴリズムの説明の便宜のために、図２を参照してこの明細書中に用いられる記号の定義について説明すれば、下記の通りである。
ｎ１及びｎ２は映像の大きさを表わし、Ｄ（ｉ，ｊ）はノードまたはウェーブレット係数（ｉ，ｊ）の全ての子孫の係数集合を意味する。Ｏ（ｉ，ｊ）はノード（ｉ，ｊ）の直系子孫の係数集合を意味する。Ｌ（ｉ，ｊ）は、Ｄ（ｉ，ｊ）からＯ（ｉ，ｊ）を除いた係数の集合を意味する。ここで、（ｉ，ｊ）は画素の座標である。
【００１６】
集合分割規則は、下記の通りである。初期分割は｛（ｉ，ｊ）∈Ｈ｝に対して集合｛（ｉ，ｊ）｝及び集合Ｄ（ｉ，ｊ）をもって形成される。もし、Ｄ（ｉ，ｊ）が有意であれば、それはＬ（ｉ，ｊ）及び｛（ｋ，ｌ）∈Ｏ（ｉ，ｊ）｝である４つの単一要素集合に分割される。もし、Ｌ（ｉ，ｊ）が有意であれば、それは｛（ｋ，ｌ）∈Ｏ（ｉ，ｊ）｝である４つの集合Ｄ（ｋ，ｌ）に分割される。
Ｈは、初期のツリールーツ（Ｉｎｉｔｉａｌ　Ｔｒｅｅ　Ｒｏｏｔｓ）の最初の係数集合を表わす。すなわち、Ｈは全ての空間根源ツリールーツ（Ｓｐａｔｉａｌ　Ｏｒｉｅｎｔａｔｉｏｎ　Ｔｒｅｅ　Ｒｏｏｔｓ）の座標集合である。
【００１７】
重要ではない集合のリスト（ＬＩＳ：Ｌｉｓｔ　ｏｆ　Ｉｎｓｉｇｎｉｆｉｃａｎｔ　Ｓｅｔ）は、臨界値より小さい係数の集合リストを表わす。すなわち、ＬＩＳはゼロツリーの座標リストである。
ここで、類型Ａは、Ｄ（ｉ，ｊ）に属する係数が臨界値より小さい場合を意味する。そして、ｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙは、サブバンドが各方向に分けられる回数を意味する。
類型Ｂは、Ｌ（ｉ，ｊ）に属する係数が臨界値より小さい場合を意味する。
【００１８】
従って、図２を参照すれば、ｄｅｐｔｈ−ｘ＝０及びｄｅｐｔｈ−ｙ＝０はＨＬ３、ＬＨ３及びＨＨ３の各々に一つのゼロツリールート（Ｚｅｒｏ　Ｔｒｅｅ　Ｒｏｏｔ）が存在することを意味する。ｄｅｐｔｈ−ｘ＝１または　ｄｅｐｔｈ−ｙ＝１は各々に２つのゼロツリー根が存在することを意味する。ｄｅｐｔｈ−ｘ＝１及びｄｅｐｔｈ−ｙ＝１はＨＬ３、ＬＨ３及びＨＨ３の各々に４つのゼロツリー根が存在することを意味する。
【００１９】
重要ではない画素のリスト（ＬＩＰ：Ｌｉｓｔ　ｏｆ　Ｉｎｓｉｇｎｉｆｉｃａｎｔ　Ｐｉｘｅｌ）は、臨界値より小さい係数のリスト、すなわち、全てのウェーブレット係数の座標に関するリストを表わす。ｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙは、サブバンドが各方向に分けられる回数を表わす。
重要な画素の集合（ＬＳＰ：Ｌｉｓｔ　ｏｆ　Ｓｉｇｎｉｆｉｃａｎｔ　Ｐｉｘｅｌ）は、臨界値より大きい係数のリストを表わす。レベルはウェーブレット変換レベルを表わす。
【００２０】
【数１】
2004023783.tif 000003
【００２１】
ここで、Ｈｘは最も高いサブバンドの縦サイズｘを表わし、Ｈｙは最も高いサブバンドの横サイズｙを表わす。Ｓｘは、リストにある位置からの縦方向ｘに関するサーチ範囲を表わし、Ｓｙは、リストにある位置からの横方向ｙに関するサーチ範囲を表わす。
【００２２】
【数２】
2004023783.tif 000004
ここで、Ｓｎ（ｘ，ｙ）は個別画素を表わす集合を意味する。
【００２３】
以下、本発明によるアルゴリズムについて詳細に説明する。本発明によるアルゴリズムは、ＳＰＩＨＴ方式に基づく。
１．初期化
初期化から下記式３が導き出される。
【００２４】
【数３】
2004023783.tif 000005
【００２５】
ＬＳＰは空いているリストとして設定し、ｄｅｐｔｈ−ｘが０であり、ｄｅｐｔｈ−ｙが０であり、そして｛（ｉ，ｊ）∈Ｈ｝である各座標がＬＩＰに追加される。ｄｅｐｔｈ−ｘが０であり、ｄｅｐｔｈ−ｙが０であり、類型Ａであり、そして｛（ｉ，ｊ）∈Ｈ｝である各座標がＬＳＰに追加される。
【００２６】
２．並べ替え過程
２．１．　ＬＩＰにある各画素またはエントリー（ｉ，ｊ）に対して、下記の事項を行う。
２．１．１．　　Ｓｎ（ｉ，ｊ）を出力する；
２．１．２．　もし、Ｓｎ（ｉ，ｊ）＝１、Ｓｘ＝１、そしてＳｙ＝１であれば、座標（ｉ，ｊ）をＬＳＰに移動し、Ｃｉ，ｊの符号を出力する。
もし、Ｓｎ（ｉ，ｊ）＝１、Ｓｘ＝１、そしてＳｙ≠１であれば、ｄｅｐｔｈ−ｙを１だけインクリメントする（ｂｅ　ｉｎｃｒｅａｓｅｄ）；
座標（ｉ，ｊ）及び座標（（ｉ，（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ））をＬＩＰの末端に追加する；
座標（ｉ，ｊ）をＬＩＰから除去する；
もし、Ｓｎ（ｉ，ｊ）＝１、Ｓｘ≠１、そしてＳｙ＝１であれば、ｄｅｐｔｈ−ｘを１だけインクリメントする；
座標（ｉ，ｊ）及び座標（ｉ＋Ｈｘ／２ｄｅｐｔｈ−ｘ），ｊ）をＬＩＰの末端に追加する；
座標（ｉ，ｊ）をＬＩＰから除去する；
もし、Ｓｎ（ｉ，ｊ）＝１、Ｓｘ≠１、そしてＳｙ≠１であれば、ｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙを１だけインクリメントする；
座標（ｉ，ｊ），座標（ｉ，（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ）），座標（（ｉ＋Ｈｘ／２ｄｅｐｔｈ−ｘ），ｊ），及び　座標（（ｉ＋Ｈｘ／２ｄｅｐｔｈ−ｘ），（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ））を、ＬＩＰの末端に追加する；座標（ｉ，ｊ）をＬＩＰから除去する；
【００２７】
２．２．ＬＩＳにある各画素またはエントリー（ｉ，ｊ）に対して下記の事項を行う。
２．２．１．　もし、前記エントリー（ｉ，ｊ）が類型Ａであれば、Ｓｎ（Ｄ（ｉ，ｊ））を出力する；
もし、Ｓｎ（Ｄ（ｉ，ｊ））＝１、Ｓｘ＝１、そしてＳｙ＝１であれば、（ｋ，ｌ）∈０（ｉ，ｊ）である各座標に対して下記の事項を行う。
ｄｅｐｔｈ−ｘ＝ｌｏｇ（ｎ１／２）−レベル；
ｄｅｐｔｈ−ｙ＝ｌｏｇ（ｎ２／２）−レベル；
Ｓｎ（ｋ，ｌ）を出力する；
もし、Ｓｎ（ｋ，ｌ）＝１であれば、座標（ｋ，ｌ）をＬＳＰに追加し、Ｃｋ，ｌの符号を出力する；
もし、Ｓｎ（ｋ，ｌ）＝０であれば、ｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙを有する座標（ｋ，ｌ）をＬＩＰに追加する；
もし、Ｌ（ｉ，ｊ）≠０であれば、座標（ｉ，ｊ）を類型ＢのエントリーとしてＬＩＳの末端に移動させ、２．２．２へ進む；
そうでなければ、エントリー（ｉ，ｊ）をＬＩＳから除去する。
もし、Ｓｎ（Ｄ（ｉ，ｊ））＝１、Ｓｘ＝１、そしてＳｙ≠１であれば、ｄｅｐｔｈ−ｙを１だけインクリメントする；
座標（ｉ，ｊ）及び座標（ｉ，（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ））を、類型Ａのエントリーとして、ＬＩＳの末端に追加する；
座標（ｉ，ｊ）をＬＩＳから除去する；
もし、Ｓｎ（Ｄ（ｉ，ｊ））＝１、Ｓｘ≠１、そしてＳｙ＝１であれば、ｄｅｐｔｈ−ｘを１だけインクリメントする；
座標（ｉ，ｊ）及び座標（ｉ，（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ））を、類型Ａのエントリーとして、ＬＩＳの末端に追加する；
座標（ｉ，ｊ）をＬＩＳから除去する；
もし、Ｓｎ（Ｄ（ｉ，ｊ））＝１、Ｓｘ≠１、そしてＳｙ≠１であれば、ｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙを１だけインクリメントする；
座標（ｉ，ｊ），座標（ｉ，（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ）），座標（（ｉ＋Ｈｘ／２ｄｅｐｔｈ−ｘ），ｊ）及び座標（（ｉ＋Ｈｘ／２ｄｅｐｔｈ−ｘ），（ｊ＋Ｈｙ／２ｄｅｐｔｈ−ｙ））を、類型Ａのエントリーとして、ＬＩＰの末端に追加する；
座標（ｉ，ｊ）をＬＩＳから除去する；
【００２８】
２．２．２．もし、前記エントリーが類型Ｂであれば、Ｓｎ（Ｌ（ｉ，ｊ））を出力する；
もし、Ｓｎ（Ｌ（ｉ，ｊ））＝１であれば、
ｄｅｐｔｈ−ｘ＝ｌｏｇ（ｎ１／２）−レベル；
ｄｅｐｔｈ−ｙ＝ｌｏｇ（ｎ２／２）−レベル；
｛（ｋ，ｌ）∈０（ｉ，ｊ）｝である各座標を、類型Ａのエントリーｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙとして、ＬＩＳの末端に追加する；
座標（ｉ，ｊ）をＬＩＳから除去する；
【００２９】
３．精製過程
現在のｎ以前にＬＳＰに追加された各エントリー（ｉ，ｊ）に対して｜Ｃｉ，ｊ｜のｎ番目のビットを出力する。
【００３０】
４．量子化ステップ更新
ｎを１だけデクリメントし、並べ替え過程を行う。
図３は、本発明によるエンコーダのブロック図である。図３を参照すれば、エンコーダ４０は、ウェーブレット変換回路４１と、最適ゼロツリー発生器４３と、ゼロツリーコーダ４５及びエントロピーコーダ４７を備える。
ウェーブレット変換回路４１は、入力映像を、ウェーブレット変換を用いて、多数のウェーブレット係数（またはノード）を有するウェーブレット領域に変換する。図１及び図２は、ウェーブレット領域を表わす。すなわち、ウェーブレット変換回路４１は、入力映像を所定のレベルまたはスケールにウェーブレット変換する。
【００３１】
最適ゼロツリー発生器４３は、ゼロツリーコーダ４５の出力信号及びウェーブレット変換回路４１の出力信号に応答して、前記多数のウェーブレット係数の同じ空間的な位置及び方向に対応する多数のゼロツリーを生成する。すなわち、最適ゼロツリー発生器４３は、ウェーブレット係数の空間的な相関度を用いて最適のゼロツリーを構成する。
ゼロツリー符号化器４５は隣接する多数のゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化し、前記シンボルをエントロピーコーダ４７及び最適ゼロツリー発生器４３に出力する。
【００３２】
最適ゼロツリー発生器４３またはゼロツリー符号化器４５は、ウェーブレット変換回路４１から出力される多数のウェーブレット係数の同じ空間的な位置及び方向に対応するウェーブレットツリーがゼロツリーである場合、前記ゼロツリーに隣接する所定のウェーブレットゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化して前記シンボルを出力することができる。従って、最適ゼロツリー発生器４３またはゼロツリー符号化器４５は、単一の回路により構成されもする。
【００３３】
また、最適ゼロツリー発生器４３またはゼロツリー符号化器４５は、ゼロツリーを構成しないウェーブレット係数を独立的に符号化することができる。エントロピーコーダ４７は、ゼロツリー符号化器４５の出力信号を受信してビットストリームを形成する。従って、本発明によるエンコーダは、ゼロツリーウェーブレット変換を用いて入力映像をビットストリームに符号化する。
【００３４】
図４は、図３の最適ゼロツリー発生器の詳細なブロック図面であり、図５Ａないし図５Ｃは、図３の最適ゼロツリー発生器により生成されるゼロツリーグループの例を各々示す図面である。
図４及び図５を参照すれば、最適ゼロツリー発生器４３は、初期空間根源ツリー発生器４３１と、臨界値発生器４３３及びゼロツリースプリッタ４３５を備える。
【００３５】
初期空間根源ツリー発生器４３１は、最初のゼロツリーグループを構成する。すなわち、サブバンドそのものがゼロツリーを構成するとして初期化する。図５Ａを参照すれば、初期に３つのゼロツリーグループが存在する。ここで、同じ番号は、ウェーブレット係数の同じ空間的な位置及び方向に対応するゼロツリーを表わす。
臨界値発生器４３３は、初期空間根源ツリー発生器４３１に接続され、量子化を行うために臨界値を設定する。臨界値発生器４３３は、初期に前記式３で表わされるｎを出力し、本発明によるアルゴリズムを行う間に、臨界値発生器４３３は前記ｎを１ずつデクリメントしてその結果を出力する。臨界値発生器４３３により臨界値が決められれば、決められた臨界値に対するゼロツリーグループは、図５Ｂの如く分解される。
【００３６】
ゼロツリースプリッタ４３５は、臨界値発生器４３３から出力される量子化臨界値を受信し、前記量子化臨界値とウェーブレット係数とを比較し、前記量子化臨界値より大きい値のウェーブレット係数が存在する場合、ゼロツリースプリッタ４３５は、前記ウェーブレット係数を用いてゼロツリーグループを分解する。図５Ｃを参照すれば、同じ数字は同じゼロツリーグループに属する。ゼロツリースプリッタ４３５は、前記ｎがデクリメントされるにつれてゼロツリーグループを分解することにより、ｄｅｐｔｈ−ｘ及びｄｅｐｔｈ−ｙをインクリメントする。
【００３７】
図６は、本発明による、多数のウェーブレット係数を各々有する多数のウェーブレットツリーを生成するために、ゼロツリーウェーブレット変換を用いて、入力映像をビットストリームに符号化する方法を示すフローチャートである。
従って、図３ないし図６を参照すれば、最適ゼロツリー発生器４３は、現在のウェーブレット係数が少なくとも一つ以上のゼロツリーを構成するか否かを判断する（第７１段階）。すなわち、第７１段階においては、各ウェーブレットツリーがゼロツリーであるか否かを判断する。
【００３８】
前記現在のウェーブレット係数がゼロツリーを構成しない場合、ゼロツリーコーダ４５は、前記現在のウェーブレット係数を独立的に符号化する（第７９段階）。すなわち、各ウェーブレットツリーがゼロツリーではない場合、ゼロツリーコーダ４５は、前記各ウェーブレットツリーに属する各ウェーブレット係数を独立的に符号化して出力する。
前記現在のウェーブレット係数がゼロツリーを構成する場合、最適ゼロツリー発生器４３はゼロツリー値の数を判断する（第７３段階）。ゼロツリールートがただ一つである場合、ゼロツリーコーダ４５は１つのゼロツリーを符号化する（第７８段階）。
【００３９】
しかし、ゼロツリールートが２つ以上である場合、最適ゼロツリー発生器４３は隣接するゼロツリールートの範囲を検索する（第７５段階）。ゼロツリーコーダ４５は、隣接する多数のゼロツリー（すなわち、ゼロツリーグループ）を結合し、結合された多数のゼロツリーを一つのシンボルに符号化して、前記シンボルをエントロピーコーダ４７に出力する。
【００４０】
図７は、レナ（Ｌｅｎａ）映像を３レベルに変換した場合、従来のＳＰＩＨＴアルゴリズム及び本発明のＧＳＰＩＨＴ（Ｇｒｏｕｐｅｄ　Ｓｅｔ　Ｐａｒｔｉｔｉｏｎｉｎｇ　ｉｎ　Ｈｉｅｒａｒｃｈｉｃａｌ　Ｔｒｅｅｓ）Ｉｎアルゴリズムによるビット／ピクセル（ＢＰＰ：Ｂｉｔ　Ｐｅｒ　Ｐｉｘｅｌ）及びピーク雑音信号比（ＰＳＮＲ：Ｐｅａｋ　Ｓｉｇｎａｌ　ｔｏ　Ｎｏｉｓｅ　Ｒａｔｉｏ）を表わす。図８は、レナ映像を４レベルに変換した場合、従来のＳＰＩＨＴアルゴリズム及び本発明のＧＳＰＩＨＴアルゴリズムによる、ＢＰＰ及びＰＳＮＲを示す。
【００４１】
下記式４及び５は、図７ないし図１０に示された評価尺度（ＰＳＮＲ）を表わす。
【数４】
2004023783.tif 000006
ここで、Ｘ（ｉ，ｊ）は原映像を表わし、Ｙ（ｉ，ｊ）は再生された映像を表わす。ここで、概観的な性能評価の尺度は平均２乗平方根誤差（ＲＭＳＥ：Ｒｏｏｔ　Ｍｅａｎｓ　Ｑｕａｒｅ
Ｅｒｒｏｒ）である。
【数５】
2004023783.tif 000007
【００４２】
図７及び図８を参照すれば、本発明によるアルゴリズムを用いたエンコーダは、ウェーブレット変換レベルに無関係に従来のアルゴリズムを用いたエンコーダより優れた符号化性能を示している。
図９は、従来のＳＰＩＨＴアルゴリズムを用いてバーバラ（Ｂａｒｂａｒａ）映像を符号化した場合の符号化性能を示しており、図１０は、本発明のＧＳＰＩＨＴアルゴリズムを用いてバーバラ映像を符号化した場合の符号化性能を示している。図９及び図１０を参照すれば、本発明によるアルゴリズムを用いたエンコーダの符号化性能は、従来のＳＰＩＨＴアルゴリズムを用いたエンコーダの符号化性能より向上されて安定しているということが分かる。
【００４３】
本発明によるゼロツリーウェーブレット映像符号化アルゴリズム、及び前記アルゴリズムを用いるエントロピーは、隣接する多数のゼロツリーを結合し、結合された多数のゼロツリーを一つのシンボルに符号化して出力する。
【００４４】
【発明の効果】
上述したように、本発明によるグループ化したゼロツリーウェーブレット映像符号化方法及び装置は、符号化効率を高める効果がある。
本発明は図面に示された一実施の形態を参考として説明されたが、これは単に例示的なものに過ぎず、この技術分野における当業者であれば、これより各種の変形及び均等な他の実施形態が可能であるという点が理解できるであろう。よって、本発明の真の技術的な保護範囲は特許請求の範囲上の技術的な思想によって決められるべきである。
【図面の簡単な説明】
【図１】通常のウェーブレット係数のツリー構造を示す図面である。
【図２】本発明によるアルゴリズムを説明するためのウェーブレット係数のツリー構造及び記号を示す図面である。
【図３】本発明によるエンコーダのブロック図である。
【図４】図３の最適ゼロツリー発生器の詳細なブロック図である。
【図５】ＡないしＣは、図３の最適ゼロツリー発生器により生成されるゼロツリーグループの例を各々示す図面である。
【図６】本発明による符号化方法のフローチャートである。
【図７】レナ映像を３レベルに変換した場合、従来のアルゴリズム及び本発明のアルゴリズムによるＢＰＰ及びＰＳＮＲを示す図面である。
【図８】レナ映像を４レベルに変換した場合、従来のアルゴリズム及び本発明のアルゴリズムによるＢＰＰ及びＰＳＮＲを示す図面である。
【図９】従来のアルゴリズムを用いてバーバラ映像を符号化した符号化性能を示す図面である。
【図１０】本発明によるアルゴリズムを用いてバーバラ映像を符号化した符号化性能を示す図面である。
【図１】
2004023783.tif 000008
【図２】
2004023783.tif 000009
【図３】
2004023783.tif 000010
【図４】
2004023783.tif 000011
【図５】
2004023783.tif 000012
【図６】
2004023783.tif 000013
【図７】
2004023783.tif 000014
【図８】
2004023783.tif 000015
【図９】
2004023783.tif 000016
【図１０】
2004023783.tif 000017