(57)【要約】【課題】  例えばＪＰＥＧ２０００方式におけるゼロビットプレーン数等のように所定の順序で階層的に符号化する必要のある非負整数２次元配列データを省メモリ且つ効率的に符号化する。【解決手段】  中間データ生成部１００は、例えばラスタスキャン順に８ビットのアドレスが付され２５６個の配列要素が格納されたゼロビットプレーン数ＲＡＭ２０から所定の順序で各要素を読み出し、それぞれ２＾(２ｎ)個毎の最小値をタグプレーンｎＲＡＭ１１〜１５に書き込む。符号計算部２００は、符号化対象の要素に対応付けられた要素をタグプレーンｎＲＡＭ１１〜１５から読み出し、それらの要素の符号を繋げることで目的の符号を生成する。特に中間データ生成部１００は、ｎビットのリニアカウンタの値｛n-1, n-2,・・・, 1, 0｝を｛n-1, n-3,・・・, 3, 1, n-2, n-4, ・・・, 2, 0｝へと変換して読出アドレスとする。【選択図】  図１１
2006115194.tif 000002
【特許請求の範囲】
【請求項１】
ラスタスキャン順にｎビットのアドレスが付された２＾(ｎ／２)×２＾(ｎ／２)の要素からなる配列要素が格納された第１の記憶手段から所定の順序で各要素を読み出す読出手段と、
上記読出手段によって読み出された要素のそれぞれ所定個数毎の最小値を(ｎ／２)＋１個の第２の記憶手段に書き込む書込手段と、
上記第１の記憶手段に格納された要素のうち、符号化対象となる要素に対応付けられた要素を(ｎ／２)＋１個の上記第２の記憶手段から読み出し、各第２の記憶手段の要素の符号を繋げることで上記符号化対象となる要素の符号を生成する符号化手段とを備え、
上記読出手段は、ｎビットのリニアカウンタの値｛n-1, n-2, n-3,・・・, 1, 0｝を｛n-1, n-3, n-5,・・・, 3, 1, n-2, n-4, n-6,・・・, 2, 0｝へと変換した値を読出アドレスとして、上記第１の記憶手段の各要素を順次読み出し、
上記書込手段は、ｋ番目（ｋは０≦ｋ≦ｎ／２を満たす整数）の第２の記憶手段に対して、２＾(２ｋ)個毎の最小値を書き込む
ことを特徴とする符号化装置。
【請求項２】
上記符号化手段は、０番目の上記第２の記憶手段に格納されている上記符号化対象となる要素と同一の要素の符号、及びｍ番目（ｍは１≦ｋ≦ｎ／２を満たす整数）の上記第２の記憶手段に格納されている上記符号化対象となる要素が最小値を求める際に考慮された要素の符号を繋げることで、上記符号化対象となる要素の符号を生成することを特徴とする請求項１記載の符号化装置。
【請求項３】
上記符号化手段は、(ｎ／２)＋１個の上記第２の記憶手段に格納されている要素のうち、既に符号が繋げられた要素を用いないことを特徴とする請求項２記載の符号化装置。
【請求項４】
上記ｋ番目の第２の記憶手段には、ラスタスキャン順にｎ−ｋビットのアドレスが付された２＾((ｎ−ｋ)／２)×２＾((ｎ−ｋ)／２)の要素からなる配列要素が格納されていることを特徴とする請求項１記載の符号化装置。
【請求項５】
上記書込手段は、上記ｋ番目の第２の記憶手段に対して、ｎビットのリニアカウンタの下位ｎ−２ｋビットの値｛n-2k-1, n-2k-2,・・・, 1, 0｝を｛n-2k-1, n-2k-3,・・・, 3, 1, n-2k-2, n-2k-4,・・・, 2, 0｝へと変換した値を書込アドレスとして、上記読出手段によって読み出された要素の２＾(２ｋ)個毎の最小値を書き込むことを特徴とする請求項４記載の符号化装置。
【請求項６】
上記第１の記憶手段には、ＪＰＥＧ２０００方式におけるコードブロック毎のゼロビットプレーン数の情報又はインクルージョン情報が、サブバンド内におけるコードブロックの並び順に従って格納されていることを特徴とする請求項１記載の符号化装置。
【請求項７】
上記第１の記憶手段のうち、コードブロックが存在しない部分については、上記ゼロビットプレーン数の情報又はインクルージョン情報として、該ゼロビットプレーン数の情報又は該インクルージョン情報が取り得る値よりも大きな値が書き込まれていることを特徴とする請求項６記載の符号化装置。
【請求項８】
ラスタスキャン順にｎビットのアドレスが付された２＾(ｎ／２)×２＾(ｎ／２)の要素からなる配列要素が格納された第１の記憶手段から所定の順序で各要素を読み出す読出工程と、
上記読出工程にて読み出された要素のそれぞれ所定個数毎の最小値を(ｎ／２)＋１個の第２の記憶手段に書き込む書込工程と、
上記第１の記憶手段に格納された要素のうち、符号化対象となる要素に対応付けられた要素を(ｎ／２)＋１個の上記第２の記憶手段から読み出し、各第２の記憶手段の要素の符号を繋げることで上記符号化対象となる要素の符号を生成する符号化工程とを有し、
上記読出工程では、ｎビットのリニアカウンタの値｛n-1, n-2, n-3,・・・, 1, 0｝を｛n-1, n-3, n-5,・・・, 3, 1, n-2, n-4, n-6,・・・, 2, 0｝へと変換した値を読出アドレスとして、上記第１の記憶手段の各要素を順次読み出し、
上記書込工程では、ｋ番目（ｋは０≦ｋ≦ｎ／２を満たす整数）の第２の記憶手段に対して、２＾(２ｋ)個毎の最小値を書き込む
ことを特徴とする符号化方法。
【請求項９】
上記符号化工程では、０番目の上記第２の記憶手段に格納されている上記符号化対象となる要素と同一の要素の符号、及びｍ番目（ｍは１≦ｋ≦ｎ／２を満たす整数）の上記第２の記憶手段に格納されている上記符号化対象となる要素が最小値を求める際に考慮された要素の符号を繋げることで、上記符号化対象となる要素の符号を生成することを特徴とする請求項８記載の符号化方法。
【請求項１０】
上記符号化工程では、(ｎ／２)＋１個の上記第２の記憶手段に格納されている要素のうち、既に符号が繋げられた要素を用いないことを特徴とする請求項９記載の符号化方法。
【請求項１１】
上記ｋ番目の第２の記憶手段には、ラスタスキャン順にｎ−ｋビットのアドレスが付された２＾((ｎ−ｋ)／２)×２＾((ｎ−ｋ)／２)の要素からなる配列要素が格納されていることを特徴とする請求項８記載の符号化方法。
【請求項１２】
上記書込工程では、上記ｋ番目の第２の記憶手段に対して、ｎビットのリニアカウンタの下位ｎ−２ｋビットの値｛n-2k-1, n-2k-2,・・・, 1, 0｝を｛n-2k-1, n-2k-3,・・・, 3, 1, n-2k-2, n-2k-4,・・・, 2, 0｝へと変換した値を書込アドレスとして、上記読出工程にて読み出された要素の２＾(２ｋ)個毎の最小値を書き込むことを特徴とする請求項１１記載の符号化方法。
【請求項１３】
上記第１の記憶手段には、ＪＰＥＧ２０００方式におけるコードブロック毎のゼロビットプレーン数の情報又はインクルージョン情報が、サブバンド内におけるコードブロックの並び順に従って格納されていることを特徴とする請求項８記載の符号化方法。
【請求項１４】
上記第１の記憶手段のうち、コードブロックが存在しない部分については、上記ゼロビットプレーン数の情報又はインクルージョン情報として、該ゼロビットプレーン数の情報又は該インクルージョン情報が取り得る値よりも大きな値が書き込まれていることを特徴とする請求項１３記載の符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばＪＰＥＧ（Joint Photographic Experts Group）２０００方式におけるゼロビットプレーン数やインクルージョン情報のような非負整数２次元配列データを所定の順序で階層的に符号化する際に用いて好適な符号化装置及びその方法に関する。
【背景技術】
【０００２】
従来の代表的な画像圧縮方式として、ＩＳＯ（International Standards Organization）によって標準化されたＪＰＥＧ方式がある。これは、離散コサイン変換（Descrete Cosine Transform；ＤＣＴ）を用い、比較的高いビットが割り当てられる場合には、良好な符号化画像及び復号画像を供することが知られている。しかし、ある程度以上に符号化ビット数を少なくすると、ＤＣＴ特有のブロック歪みが顕著になり、主観的に劣化が目立つようになる。
【０００３】
一方、近年では画像をフィルタバンクと呼ばれる低域フィルタと高域フィルタとを組み合わせたフィルタによって複数の帯域に分割し、各帯域毎に符号化を行う方式の研究が盛んになっている。その中でも、ウェーブレット変換符号化は、ＤＣＴのように高圧縮でブロック歪みが顕著になるという欠点がないことから、ＤＣＴに代わる新たな技術として有力視されている。２００１年１月に国際標準化が完了したＪＰＥＧ２０００方式は、このウェーブレット変換と高能率なエントロピー符号化（ビットプレーン単位のビットモデリング及び算術符号化）とを組み合わせた方式を採用しており、ＪＰＥＧ方式に比べて符号化効率の大きな改善を実現している。
【０００４】
ＪＰＥＧ２０００方式に従って画像データを圧縮符号化する画像符号化装置の概略構成の一例を図２０に示す。図２０に示すように、画像符号化装置５００は、ウェーブレット変換部５０１と、コードブロック化部５０２と、エントロピー符号化部５０３と、レイヤ化部５０４と、符号生成部５０５とから構成されている。
【０００５】
この画像符号化装置５００において、ウェーブレット変換部５０１は、入力された画像データに対してウェーブレット変換を施し、複数のサブバンドに分割する。このウェーブレット変換は、図２１に示すように、縦横２次元に分割し、低域については再帰的に分割するMallat分割である。なお、図２１では、２回のウェーブレット変換により７個のサブバンドが生成されている。コードブロック化部５０２は、各サブバンドを複数のコードブロックに分割する。図２２（Ａ）に示すように、コードブロックは同じ大きさの矩形領域であり、縦横６４×６４のサイズのコードブロックがよく用いられる。エントロピー符号化部５０３は、各コードブロックの係数を正負の符号＋絶対値に変換し、係数絶対値についてはビットプレーンに分割してＭＳＢ（Most Significant Bit）側からビットプレーン毎にエントロピー符号化を行う。なお、ＭＳＢ側から数えて初めて有効なビット（０でないビット）が出現するビットプレーンまではゼロビットプレーンであるため、エントロピー符号化を行わず、コードブロック毎のゼロビットプレーン数が別途符号化される。エントロピー符号化部５０３は、コードブロック毎の符号列とその符号量等の付随データとをレイヤ化部５０４に供給する。符号列の例を図２２（Ｂ）に示す。このように、一般的にコードブロックによって符号量は異なる。
【０００６】
レイヤ化部５０４は、各コードブロックの符号列をレイヤに分割する。このレイヤは、ＪＰＥＧ２０００方式においてＳＮＲ（Signal to Noise Ratio）スケーラビリティを実現するためのものである。総符号量をＳ以下とし、且つ可能な限り高画質の復号画像を得るためには、レイヤ０から
Ｓ≧size(０)＋size(１)＋・・・＋size(Ｘ)
を満たす最大のＸを与えるレイヤＸまで、すなわちレイヤ０、１、・・・、Ｘを復号すればよい。ここでsize(Ｎ)とは、レイヤＮの符号量を示す。なお、図２２（Ｃ）に示すように、各コードブロックは全てのレイヤに含まれる訳ではなく、各コードブロックが含まれるレイヤ番号の最小値がインクルージョン情報として別途符号化される。符号生成部５０５は、これらのデータを繋げた符号列を生成して出力する。
【０００７】
ところで、上述したコードブロック毎のゼロビットプレーン数やインクルージョン情報は非負整数であるが、ＪＰＥＧ２０００方式では、これらの非負正数データをサブバンド内におけるコードブロックの並び方の通りに２次元に配列し、得られた非負整数２次元配列データをタグツリーによって所定の順序で階層的に符号化する（下記特許文献１を参照）。
【０００８】
【特許文献１】特開２００３−２７４４０５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来、このタグツリーによる符号化は、ソフトウェアにより逐次的なループ処理を伴って実行されていたため、これをそのままハードウェアで実現した場合には、実行に長時間を要する上、内部状態をもった複雑な順序回路になり、ハードウェア規模が大きくなると共に消費電力が大きくなり、さらに設計及び検証にかかる時間も長くなってしまうという問題が発生する。特に近年、デジタルカメラ等が高解像度化されているが、ゼロビットプレーン数の情報やインクルージョン情報は各コードブロックにつき１つあるため、高解像度になるほど上記問題は顕著なものとなる。
【００１０】
本発明は、このような従来の実情に鑑みて提案されたものであり、例えばＪＰＥＧ２０００方式におけるゼロビットプレーン数やインクルージョン情報のように所定の順序で階層的に符号化する必要のある非負整数２次元配列データを省メモリ且つ効率的に符号化することが可能な符号化装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した目的を達成するために、本発明に係る符号化装置は、ラスタスキャン順にｎビットのアドレスが付された２＾(ｎ／２)×２＾(ｎ／２)の要素からなる配列要素が格納された第１の記憶手段から所定の順序で各要素を読み出す読出手段と、上記読出手段によって読み出された要素のそれぞれ所定個数毎の最小値を(ｎ／２)＋１個の第２の記憶手段に書き込む書込手段と、上記第１の記憶手段に格納された要素のうち、符号化対象となる要素に対応付けられた要素を(ｎ／２)＋１個の上記第２の記憶手段から読み出し、各第２の記憶手段の要素の符号を繋げることで上記符号化対象となる要素の符号を生成する符号化手段とを備え、上記読出手段は、ｎビットのリニアカウンタの値｛n-1, n-2, n-3,・・・, 1, 0｝を｛n-1, n-3, n-5,・・・, 3, 1, n-2, n-4, n-6,・・・, 2, 0｝へと変換した値を読出アドレスとして、上記第１の記憶手段の各要素を順次読み出し、上記書込手段は、ｋ番目（ｋは０≦ｋ≦ｎ／２を満たす整数）の第２の記憶手段に対して、２＾(２ｋ)個毎の最小値を書き込むことを特徴とする。
【００１２】
ここで、上記符号化手段は、０番目の上記第２の記憶手段に格納されている上記符号化対象となる要素と同一の要素の符号、及びｍ番目（ｍは１≦ｋ≦ｎ／２を満たす整数）の上記第２の記憶手段に格納されている上記符号化対象となる要素が最小値を求める際に考慮された要素の符号を繋げることで、上記符号化対象となる要素の符号を生成する。
【００１３】
なお、上記第１の記憶手段に格納されるデータとしては、例えばＪＰＥＧ２０００方式におけるコードブロック毎のゼロビットプレーン数の情報又はインクルージョン情報をサブバンド内におけるコードブロックの並び順に従って配列したものを挙げることができる。
【００１４】
また、上述した目的を達成するために、本発明に係る符号化方法は、ラスタスキャン順にｎビットのアドレスが付された２＾(ｎ／２)×２＾(ｎ／２)の要素からなる配列要素が格納された第１の記憶手段から所定の順序で各要素を読み出す読出工程と、上記読出工程にて読み出された要素のそれぞれ所定個数毎の最小値を(ｎ／２)＋１個の第２の記憶手段に書き込む書込工程と、上記第１の記憶手段に格納された要素のうち、符号化対象となる要素に対応付けられた要素を(ｎ／２)＋１個の上記第２の記憶手段から読み出し、各第２の記憶手段の要素の符号を繋げることで上記符号化対象となる要素の符号を生成する符号化工程とを有し、上記読出工程では、ｎビットのリニアカウンタの値｛n-1, n-2, n-3,・・・, 1, 0｝を｛n-1, n-3, n-5,・・・, 3, 1, n-2, n-4, n-6,・・・, 2, 0｝へと変換した値を読出アドレスとして、上記第１の記憶手段の各要素を順次読み出し、上記書込工程では、ｋ番目（ｋは０≦ｋ≦ｎ／２を満たす整数）の第２の記憶手段に対して、２＾(２ｋ)個毎の最小値を書き込むことを特徴とする。
【発明の効果】
【００１５】
本発明に係る符号化装置及びその方法によれば、例えばＪＰＥＧ２０００方式におけるゼロビットプレーン数の情報やインクルージョン情報のように所定の順序で階層的に符号化する必要のある非負整数２次元配列データを符号化する際に、逐次的なループ処理がないため高速に処理を行うことができる上、組み合わせ回路で済むためハードウェア規模を小さく抑えることができ、消費電力も少なく抑えることができる。さらに、設計及び検証に要する時間も短くなる上、順序回路の場合に必要だった常態変数のためのメモリが不要になる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、ＪＰＥＧ２０００方式におけるゼロビットプレーン数及びインクルージョン情報を配列した非負整数２次元配列データを所定の順序で階層的に符号化する符号化装置及びその方法に適用したものである。
【００１７】
ＪＰＥＧ２０００方式では、非負整数２次元配列データを階層的に符号化する方法としてタグツリーによる符号化を用いている。そこで、以下では先ず、このタグツリー及びタグツリーによる従来の符号化手法について説明し、次いで、本実施の形態における符号化装置及びその動作について説明する。
【００１８】
先ず、タグツリーについて説明する。
【００１９】
非負整数の２次元配列Ａを図１（Ａ）に示す。この２次元配列Ａは、横方向の要素数が５、縦方向の要素数が２の２次元配列となっている。２次元配列Ａを表すタグツリーＴは、図１（Ｂ）に示す木構造である。このタグツリーＴには４つの階層があり、各階層は非負整数の２次元配列である。具体的に、階層０は２次元配列Ａそのものである。そして、階層ｎ（ｎ≧０）の２次元配列の縦横２×２の配列要素についての最小値を並べたものが階層ｎ＋１の２次元配列となる。なお、配列の大きさが縦横２×２とならない境界部分では、それよりも小さい配列要素の最小値が並べられる。最後の階層では、配列要素の数は１である。また、各階層の要素は図１（Ｂ）に示すように４分木の形にリンクで繋がれている。
【００２０】
ここで、タグツリーの各階層の配列要素のそれぞれはノードと呼ばれる。また、最初の階層である２次元配列Ａの各要素に対応するノードは葉と呼ばれ、タグツリーの最後の階層にある唯一のノードは根と呼ばれる。また、階層ｎの各ノードは、階層ｎ＋１の何れかのノードとリンクで繋がれているが、リンクで繋がれた２つのノードは親子関係にあると呼ばれ、この場合、階層ｎに属するノードは子、階層ｎ＋１に属するノードは親と呼ばれる。
【００２１】
次に、タグツリーによる符号化の基本について説明する。
【００２２】
タグツリーＴの葉Ｎを表す符号とは、タグツリーＴにおいて根から葉Ｎに至るリンク上の各ノードを順に符号化したものである。タグツリーＴの複数の葉を続けて符号化する場合、根からそれらの葉までのリンクには共通のノードがあるが、その共通部分を複数回符号化することがないように、一度符号化したノードは再度符号化しない。
【００２３】
リンク上の各ノードの符号は、その親との差がｄであるとき、ｄ個の「０」に続く１個の「１」というビット列である。なお、根については親が存在しないが、親の値が「０」であるとして同様に符号化する。
【００２４】
この各ノードの符号について、具体的に図１（Ｃ）を用いて説明する。以下、階層０の横、縦に振られたインデックス（それぞれｈ，ｖとする）を用いて、インデックス(h, v)の葉を葉(h, v)と記す。葉(0, 0)の値は３であり、親の値が２であることから、その差は１である。したがって、葉(0, 0)の符号は、１個の「０」に続く１個の「１」というビット列「０１」となる。葉(2, 0)の値は３であり、親の値が１であることから、その差は２である。したがって、葉(2, 0)の符号は、２個の「０」に続く１個の「１」というビット列「００１」となる。他のノードについても同様である。図１（Ｃ）では、各ノードの符号が括弧内に記されている。
【００２５】
タグツリーＴのそれぞれの葉を表す符号は、図１（Ｃ）の各ノードの符号を用いて図１（Ｄ）で表される。ここでは、葉をラスタスキャン順（葉(0, 0)，葉(1, 0)，葉(2, 0)，葉(3, 0)，葉(4, 0)，葉(0, 1)，葉(1, 1)，葉(2, 1)，葉(3, 1)，葉(4, 1)の順）で符号化するものとする。最初に符号化する葉(0, 0)を表す符号は、葉(0, 0)に至るリンク上の全てのノードの符号を根から順に繋げた「０１１０１０１」である。続いて符号化する葉(1, 0)を表す符号は、階層１以上のノードの符号化は既に終わっているため、階層０のノードのみの符号を用いて「０１」である。続いて符号化する葉(2, 0)を表す符号は、階層２以上のノードの符号化は既に終わっているため、階層１、階層０のノードの符号を繋げた「１００１」である。他の葉も同様である。
【００２６】
タグツリーの符号化では、根から葉への順にノードの値の更新及び確定を行っている。根については初期値を０とし、他のノードについては親の値を初期値としている。そして、符号「０」の場合には値に１を加算して更新し、符号「１」の場合には現在の値をそのノードの値として確定する。
【００２７】
例えば、各コードブロックのゼロビットプレーン数をタグツリーによって符号化する場合、その符号化の処理順序は図２のフローチャートの２重ループで表される。図２において、外側のループ（ステップＳ２〜ステップＳ８）はレイヤのループであり、レイヤ０から順に処理する。一方、内側のループ（ステップＳ３〜ステップＳ６）は全ての葉についてのラスタスキャン順のループである。この内側のループで符号化が行われるのであるが、葉に対応するコードブロックがそのレイヤで最初に符号化される場合のみ符号化されるようになっている。各コードブロックが最初に符号化されるレイヤ番号が図３（Ａ）で表され、ゼロビットプレーン数が図３（Ｂ）で表される場合を例として、図２に示す符号化の処理順序について具体的に説明する。
【００２８】
先ずステップＳ１において、レイヤ番号Ｌを０に初期化し、ステップＳ２において、葉Ｎをラスタスキャン順で最初の葉に設定する。次にステップＳ３において、葉Ｎに対応するコードブロックが最初に符号化されるのがレイヤＬであるか否かを判別し、最初に符号化されるのがレイヤＬである場合にはステップＳ４でその葉Ｎを符号化してステップＳ５に進み、そうでない場合にはステップＳ５に進む。続いてステップＳ５において、葉Ｎがラスタスキャン順で最後の葉であるか否かを判別し、最後の葉でない場合にはステップＳ６でラスタスキャン順で次の葉に設定してステップＳ３に戻り、最後の葉である場合にはステップＳ７に進む。最終的にレイヤ０で符号化されるコードブロックは図３（Ｃ）において斜線で示すものである。同じレイヤ中ではラスタスキャン順に符号化されるため、葉(1, 0)，葉(2, 0)，葉(1, 1)の順に符号化される。
【００２９】
続いてステップＳ７において、レイヤＬが最後のレイヤであるか否かを判別し、最後のレイヤでない場合にはステップＳ８でレイヤ番号Ｌに１を加算し、ステップＳ２に戻って次のレイヤの処理を行う。この結果、レイヤ１では、図３（Ｄ）に示すように葉(0, 0)，葉(3, 0)，葉(4, 0)，葉(0, 1)の順に符号化され、レイヤ２では、図３（Ｅ）に示すように葉(2, 1)，葉(3, 1)，葉(4, 1)の順に符号化される。一方、ステップＳ７において最後のレイヤである場合には処理を終了する。
【００３０】
各レイヤにおいて各コードブロックの符号化で発生する符号は図４のようになる。以下、具体的に説明する。
【００３１】
最初はレイヤ０における葉(1, 0)の符号化である。この符号化では、根から葉(1, 0)へのリンク上のノードが符号化される。最初の符号化であり、何れのノードもまだ符号化されていないため、根から葉(1, 0)に至るリンク上の全てのノードに対応する符号を根から順に繋げた「０１１０１０１」が符号として出力される。
【００３２】
次はレイヤ０における葉(2, 0)の符号化である。この符号化では、根から葉(2, 0)に至るリンク上のノードが符号化される。このリンク上のノードのうち、階層２及び階層３のノードは既に符号化されているため、残りのノードの符号を繋げた「１００１」が符号として出力される。
【００３３】
次はレイヤ０における葉(3, 0)の符号化である。この符号化では、根から葉(3, 0)に至るリンク上のノードが符号化される。このリンク上のノードのうち、階層１、階層２及び階層３のノードは既に符号化されているため、残る階層０のノードの符号「１」が符号として出力される。
【００３４】
次はレイヤ１における葉(0, 0)の符号化である。この符号化では、根から葉(0, 0)に至るリンク上のノードが符号化される。このリンク上のノードのうち、階層１、階層２及び階層３のノードは既に符号化されているため、残る階層０のノードの符号「０１」が符号として出力される。
【００３５】
以降の葉、レイヤの符号化も同様である。
【００３６】
このタグツリーによるゼロビットプレーン数の符号化は、従来、以下に説明するようにソフトウェアで実現されていた。ここではJasPer（http://www.ece.uvic.ca/~mdadams/jasper/を参照）を例として説明する。JasPerにおいて、タグツリーの符号化はファイルjasper-1.701.0/src/libjasper/jpc/jpc_tagtree.c の関数jpc_tagtree_encode()で行われている。
【００３７】
ここで使われているデータ構造には次の２つがある。１つ目は各ノードを表すデータ構造であり、親ノードへのポインタ、実際の値、現在の値、値が確定しているか否かの値確定フラグをメンバーに持っている。２つ目はタグツリーを表すデータ構造であり、葉となる階層０のノードの縦横の数、全ノード数、最初の葉へのポインタをメンバーに持っている。
【００３８】
関数jpc_tagtree_encode()が行うことは、タグツリーのデータ構造、符号化対象となる葉、符号化を打ち切るための閾値、を入力とし、タグツリー符号を出力することである。
【００３９】
全ての符号化に先だって、タグツリーのデータ構造が作られる。このとき、葉の実際の値が符号化するゼロビットプレーン数に初期化され、各ノードの値確定フラグ及び現在の値は全て０に初期化される。
【００４０】
関数jpc_tagtree_encode()の処理を図５のフローチャートを用いて説明する。図５の処理では、それぞれの葉について１重ループ（ステップＳ１２〜ステップＳ１４）の処理を１回行った後で２重ループ（ステップＳ１６〜ステップＳ２６）の処理を１回行う。
【００４１】
先ずステップＳ１１において、ノードＮをタグツリーで符号化する葉に設定してステップＳ１２に進み、１重ループに入る。次にステップＳ１２においてノードＮが根であるか否かを判別し、根でない場合にはステップＳ１３でノードＮの親からノードＮへのリンクを作り、ステップＳ１４でノードＮをノードＮの親に設定してステップＳ１２に戻る。一方、ステップＳ１２おいて根である場合には、ループを抜け、ステップＳ１５に進む。
【００４２】
この１重ループは符号化の前処理であり、ノードＮを葉から根に向かって進めながらのループである。ループを抜ける条件はＮが根であることである。１回のループで行われることは、ノードＮの親からノードＮへのリンクを作ること、及びノードＮの親を新しくノードＮとすることである。
【００４３】
これにより、このループを抜けたとき、ノードＮはタグツリーの根となり、その根から符号化対象の葉までのリンクが作られることになる。なお、タグツリーのデータ構造には、親から子へのポインタはあるが子から親へのポインタはないため、このリンクを作るために、階層数−１個のポインタを覚えるメモリ領域が必要である。
【００４４】
例えば、図６の葉(3, 0)を符号化する場合、太線矢印を根に至るまで辿りながら、３つの親から子への太破線矢印を葉(3, 0)へ戻るために覚えておく。上述のようにタグツリーのデータ構造には親へのポインタはあるが子へのポインタはないため、ステップＳ１６以降の実際の符号化を行うループにおいて根から符号化対象の葉に向かっての処理を効率よく行うために、この１重ループで作ったリンクが必要となる。
【００４５】
続いてステップＳ１５において、ＬＢ＝０と初期化してステップＳ１６に進み、２重ループに入る。この２重ループが実際の符号化部分である。この２重ループのうち、外側のループ（ステップＳ１６〜ステップＳ２６）はノードＮを根から符号化対象の葉に戻しながらのループであり、内側のループ（ステップＳ１７〜ステップＳ２０）はＬＢを増やしながらのループである。
【００４６】
ステップＳ１６では、ノードＮの現在の値とＬＢとを比較し、何れか小さい方の値を大きい方の値に揃えてステップＳ１７に進み、内側のループに入る。すなわち、ＬＢの方が大きい場合にはノードＮの現在の値にＬＢを代入し、そうでない場合にはＬＢにノードＮの現在の値を代入する。
【００４７】
続いてステップＳ１７では、ＬＢが所定の閾値よりも小さいか否かを判別し、閾値よりも小さい場合にはステップＳ１８に進み、そうでない場合にはステップＳ２４に進んでループを抜ける。また、ステップＳ１８では、ＬＢがノードＮの実際の値よりも小さいか否かを判別し、実際の値よりも小さい場合にはステップＳ１９に進み、そうでない場合にはステップＳ２１に進む。ＬＢが閾値とノードＮの実際の値との何れよりも小さい場合には、ステップＳ１９において符号「０」を送り、ステップＳ２０においてＬＢを１増やす処理を繰り返す。一方、ＬＢが閾値よりも小さく、ノードＮの実際の値と同じか大きい場合には、ステップＳ２１においてノードＮの値確定フラグが「１」であるか否かを判別する。ステップＳ２１において値確定フラグが「０」である場合には、ステップＳ２２において符号「１」を送り、ステップＳ２３において値確定フラグを「１」にした後、ステップＳ２４に進む。一方、ステップＳ２１において値確定フラグが「１」である場合には、ステップＳ２４に進む。
【００４８】
続いてステップＳ２４において、ノードＮの現在の値としてＬＢを保存しておく。そして、ステップＳ２５においてノードＮが符号化対象の葉であるか否かを判別し、ノードＮが葉でない場合には、ステップＳ２６においてリンクに従ってノードＮの次のノード、すなわちノードＮの子を新たにノードＮとしてステップＳ１６に戻り、ノードＮが葉である場合にはループを抜け、符号化処理を終了する。
【００４９】
従来、各コードブロックのインクルージョン情報をタグツリーによって符号化する場合には、ステップＳ１７における閾値をゼロビットプレーン数が取り得る最大値に設定して、この関数jpc_tagtree_encode()を使用していた。
【００５０】
一方、各コードブロックのインクルージョン情報をタグツリーによって符号化する場合、その符号化の処理順序は図７のフローチャートの２重ループで表される。図７において、外側のループ（ステップＳ３２〜ステップＳ３７）はレイヤのループであり、レイヤ０から順に処理する。一方、内側のループ（ステップＳ３３〜ステップＳ３５）は全ての葉についてのラスタスキャン順のループである。ゼロビットプレーン数の場合と同様に、この内側のループで符号化が行われるのであるが、レイヤｎで葉を符号化するときには、葉に対応したコードブロックが初めて含まれるのがレイヤｎであるかレイヤ（ｎ＋１）以上であるかということが符号化されるようになっている。各コードブロックが最初に含まれるレイヤ番号が図８（Ａ）で表される場合を例として、図７に示す符号化の順序について具体的に説明する。
【００５１】
先ずステップＳ３１において、レイヤ番号Ｌを０に初期化し、ステップＳ３２において、葉Ｎをラスタスキャン順で最初の葉に設定する。
【００５２】
次にステップＳ３３において、葉Ｎを符号化する。図８（Ｂ）に示すように、レイヤ０では各コードブロックが最初に含まれるレイヤが０であるか１以上であるかということを符号化する。ここでは、全てのコードブロックにおいて、最初に含まれるのがレイヤ１以上であることが表されている。
【００５３】
続いてステップＳ３４において、葉Ｎがラスタスキャン順で最後の葉であるか否かを判別し、最後の葉でない場合にはステップＳ３５でラスタスキャン順で次の葉に設定してステップＳ３３に戻り、最後の葉である場合にはステップＳ３６に進む。
【００５４】
続いてステップＳ３６において、レイヤＬが最後のレイヤであるか否かを判別し、最後のレイヤでない場合にはステップＳ３７でレイヤ番号Ｌに１を加算し、ステップＳ３２に戻って次のレイヤの処理を行う。
【００５５】
このループにより、レイヤ１では、図８（Ｃ）に示すように各コードブロックが最初に含まれるレイヤが１であるか２以上であるかということを符号化する。葉(3, 0)に対応するコードブロックにおいて最初に含まれるのがレイヤ１であり、他のコードブロックにおいては最初に含まれるレイヤが２以上であることが表されている。
【００５６】
また、レイヤ２では、図８（Ｄ）に示すように各コードブロックが最初に含まれるレイヤが２であるか３以上であるかということを符号化する。ここで葉(3, 0)については、レイヤ１で最初に含まれるということがレイヤ１において符号化されているため、レイヤ２で最初に含まれることはあり得ない。そのため、レイヤ２で符号化する必要がなく、符号は発生しない。なお、図８（Ｄ）及び後述する図８（Ｅ）においては、符号化されないコードブロックを斜線で示している。
【００５７】
また、レイヤ３では、図８（Ｅ）に示すように各コードブロックが最初に含まれるレイヤが３であるか４以上かということを符号化する。ここで葉(3, 0)については、レイヤ１で最初に含まれるということがレイヤ１において符号化されており、葉(0, 1)，葉(1, 1)，葉(2, 1)についてはレイヤ２で最初に含まれるということがレイヤ２において符号化されているため、レイヤ３では符号化されない。
【００５８】
この各レイヤの符号化では、図１（Ｄ）で示した符号の一部が符号として発生し、最後のレイヤの符号化が終わるまでに出力される符号を繋げると、図１（Ｄ）で示した符号と同じになるという特徴がある。
【００５９】
各レイヤにおいて各コードブロックの符号化で発生する符号は図９のようになる。以下、具体的に説明する。
【００６０】
最初はレイヤ０における葉(0, 0)の符号化である。この符号化では、根から葉(0, 0)へのリンク上のノードが符号化されて「０１１０１０１」という符号が出力される可能性がある。レイヤ０では、含まれるレイヤの最小値が０であるか１以上であるかを符号化すればよい。始めのビット「０」は根の値が１以上であることを意味している。根の値が１以上であれば、その子を辿って着く葉(0, 0)も１以上であることが決まるため、レイヤ０における葉(0, 0)のための符号は「０」となる。
【００６１】
続いてレイヤ０における他の葉の符号化に移る。他の葉についても根の子を辿って着く点では同じである。葉(0, 0)の符号化において既に根の値が１以上であることが符号化されており、レイヤ０における他の葉についても値が１以上であることが決まるため、新たに符号を送らずに符号化が完了となる。図９における「−」は、符号が発生しない、すなわち符号長０であることを示している。
【００６２】
次はレイヤ１における葉(0, 0)の符号化である。レイヤ１では値が１であるか２以上であるかを符号化すればよい。この符号化では、根から葉(0, 0)へのリンク上のノードが符号化されて「０１１０１０１」という符号が出力される可能性があるが、既に始めの「０」は出力されているため、続く「１１０１０１」に可能性が絞られる。始めのビット「１」は根の値が１で確定であることを示す。この段階ではまだ葉(0, 0)が１であるか２以上であるかは分からないため、さらに符号が必要である。続くビット「１」は階層２の要素が１で確定であることを示す。この段階でもまだ葉(0, 0)が１であるか２以上であるかは分からないため、さらに符号が必要である。続くビット「０」は階層１の要素が２以上であることを示す。この段階で漸く葉(0, 0)が２以上であることが分かる。そこで、レイヤ１における葉(0, 0)のための符号は「１１０」となる。
【００６３】
レイヤ１における葉(1, 0)の符号化では符号が発生せずに符号化が完了となる。これは、葉(0, 0)の符号化で階層１にある共通の親が２以上であることが分かっているからである。
【００６４】
レイヤ１における葉(2, 0)の符号化では、根から葉(2, 0)へのリンク上のノードが符号化されて「１００１」という符号が出力される可能性がある。始めのビット「１」は階層２のノードの値が１で確定であることを示す。この段階ではまだ葉(2, 0)が１であるか２以上であるかは分からない。続くビット「０」は葉(2, 0)が２以上であることを示す。そこで、レイヤ１における葉(2, 0)のための符号は「１０」となる。
【００６５】
以降の葉、レイヤの符号化も同様である。
【００６６】
このタグツリーによるインクルージョン情報の符号化も、従来、ソフトウェアで実現されており、基本的には図５、図６を用いて説明したゼロビットプレーン数の場合と同様である。但し、全ての符号化に先だって、タグツリーのデータ構造が作られるが、このとき、葉の実際の値が符号化するインクルージョン情報に初期化され、各ノードの値確定のフラグ及び現在の値は全て０に初期化される。また、図５のステップＳ１７における閾値は、符号化するレイヤ番号に設定される。
【００６７】
従来、このタグツリーによる符号化は、図２、図５、図７に示したようにソフトウェアにより逐次的なループ処理を伴って実行されていたため、これをそのままハードウェアで実現した場合には、実行に長時間を要する上、内部状態をもった複雑な順序回路になり、ハードウェア規模が大きくなると共に消費電力が大きくなり、さらに設計及び検証にかかる時間も長くなってしまうという問題が発生する。特に近年、デジタルカメラ等が高解像度化されているが、ゼロビットプレーン数の情報やインクルージョン情報は各コードブロックにつき１つあるため、高解像度になるほど上記問題は顕著なものとなる。
【００６８】
そこで、本実施の形態では、タグツリーによる符号化部分を以下に説明するようなハードウェアで実現することにより、上記問題を解決する。
【００６９】
先ず、ゼロビットプレーン数をタグツリーにより符号化する本実施の形態における符号化装置の概略構成を図１０に示す。この符号化装置１０は、データ読出開始信号read_start、使用される最後の階層番号plane、符号化開始信号enc_start、及びインデックスｘ，ｙを入力とし、外部にあるゼロビットプレーン数ＲＡＭ（Random Access Memory）２０に対して読出アドレスzbra000、読出イネーブル信号zbre000を送ってゼロビットプレーン数を表すデータzbrd010を読み出し、コードブロック毎のゼロビットプレーン数の符号を計算して、その符号codeとその長さlenとを出力するものである。
【００７０】
ゼロビットプレーン数ＲＡＭ２０は、１ワード＝４ビットで２５６ワードの容量である。アドレスｈ＋ｖ×１６に書き込まれている値は、葉(h, v)に対応するコードブロックのゼロビットプレーン数である。ゼロビットプレーン数ＲＡＭ２０にはゼロビットプレーン数のデータが横方向の周期１６でラスタスキャン順で書き込まれていると表現することもできる。なお、画枠が小さい等の理由でコードブロックが存在しない場合、存在しないコードブロックに対応するアドレスには、使われることのない大きな値がゼロビットプレーン数として書き込まれている。
【００７１】
符号化装置１０は、中間データ生成部１００と、符号計算部２００とを有する。中間データ生成部１００は、ゼロビットプレーン数ＲＡＭ２０から所定の順序でデータzbrd010を読み出し、中間データとしてタグツリーの各階層の値を生成し、その中間データをタグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５に書き込む。なお、このタグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５には、それぞれタグプレーンの階層０〜階層４の値が書き込まれる。一方、符号計算部２００は、タグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５から中間データを読み出し、ゼロビットプレーン数の符号を計算して、その符号codeとその長さlenとを出力する。中間データ生成部１００の詳細な構成を図１１に、符号計算部２００の詳細な構成を図１４にそれぞれ示す。
【００７２】
図１１に示す中間データ生成部１００は、データ読出開始信号read_start、及び使用される最後の階層番号planeを入力とし、外部にあるゼロビットプレーン数ＲＡＭ２０に対して読出アドレスzbra000、及び読出イネーブルzbre000を送ってゼロビットプレーン数を表すデータzbrd010を読み出し、中間データとしてタグツリーの各階層の値を生成し、その中間データをタグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５に書き込むものである。
【００７３】
データ読出開始信号read_startは１クロックのパルスである。カウンタ１０１は、データ読出開始信号read_startが入力されると、１０進数で０から２５５までに対応する２進数のカウント値cnt000を１クロック毎に順に出力する。値が２５５に達した後は、次のデータ読出開始信号read_startが入力されるまで２５５を保ち続ける。
【００７４】
８ビット逆シャッフル部（iS8）１０２は、カウント値cnt000を８ビット逆シャッフルすることで、ゼロビットプレーン数ＲＡＭ２０の読出アドレスzbra000に変換する。ここで、ｎビット（ｎは偶数）の逆シャッフルとは、{n-1,n-2,n-3,・・・,1,0}という入力に対して{n-1,n-3,n-5,・・・,3,1,n-2,n-4,n-6,・・・,2,0}を出力するものである。
【００７５】
この８ビット逆シャッフルについて図１２を用いて説明する。図１２は、１０進数及び２進数で示したカウント値cnt000と逆シャッフル後の１０進数及び２進数で示した読出アドレスzbra000とを対応付けて示したものである。例えば、カウント値cnt000が１０進数で２の場合、２進数では「００００００１０」となるが、逆シャッフルにより２進数で「０００１００００」、すなわち１０進数で１６に変換される。したがって、カウント値cnt000が１０進数で２の場合、読出アドレスzbra000が１０進数で１６で示されるアドレスからデータzbrd010を読み出すことになる。
【００７６】
変換後の読出アドレスzbra000を図１３に示す。図１３に示すように、ラスタスキャン順に書き込まれたデータzbrd010が、０，１，１６，１７，２，・・・の順序で読み出される。前述したように、タグツリーでは、階層ｎ（ｎ≧０）の２次元配列の縦横２×２の配列要素についての最小値を並べたものが階層ｎ＋１の２次元配列となる。したがって、このような順序でデータzbrd010を読み出すことで、その４個、１６個、６４個、２５６個毎の最小値を求めれば、それぞれタグプレーン１ＲＡＭ１２〜タグプレーン４ＲＡＭ１５に書き込む中間データを得ることができる。この結果、例えば、読出アドレスzbra000が０，１，１６，１７で示されるアドレスに書き込まれたゼロビットプレーン数の最小値を求める場合、ラスタスキャン順では１８クロック要するのに対して、カウント値cnt000を逆シャッフルして読出アドレスzbra000に変換することで４クロックしか要さなくなり、処理を高速化することができる。
【００７７】
デコーダ１０３は、カウント値cnt000をデコードし、カウント値cnt000の最上位ビットが「０」である間、すなわちカウント値cnt000が０から２５５までの間、ゼロビットプレーン数ＲＡＭ２０に読出イネーブルzbre000を送り続ける。
【００７８】
ゼロビットプレーン数ＲＡＭ２０から読み出されたデータzbrd010はフリップフロップ１３３に入り、１クロック遅れてデータzbrd020となる。このデータzbrd020の末尾に「１」が付け加えられたデータzbrd020が加工されて中間データとなり、タグプレーン１ＲＡＭ１２〜タグプレーン４ＲＡＭ１５に書き込まれる。タグプレーンｎＲＡＭ（タグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５の何れかを示す。以下同じ。）は、１ワード＝５ビットで２＾(２×(４−ｎ))ワードの容量である。上述したように、タグプレーンｎＲＡＭに書き込まれるデータはタグプレーンの階層ｎの値である。また、データの並ぶ順序はそれぞれの中で周期２＾(４−ｎ)のラスタスキャン順である。
【００７９】
なお、タグプレーンｎＲＡＭの１ワードはゼロビットプレーン数ＲＡＭ２０の１ワードよりも１ビット大きいが、これは、タグプレーンｎＲＡＭでは、既に符号化が終わっているか否かのフラグ（符号化が終わっていないときに「１」、符号化が終わっているときに「０」をとる。）を最下位ビットで表し、他のビットでゼロビットプレーン数を表しているからである。
【００８０】
以下、タグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５へのデータの書き込みについて説明する。
【００８１】
先ず、タグプレーン０ＲＡＭ１１の場合について説明する。タグプレーン０ＲＡＭ１１には、データzbrd020の末尾に「１」が付け加えられたデータzbrd020（＝データp0wd021＝データp0wd023）がフリップフロップ１３４で１クロック遅れた中間データp0wd030が書き込まれる。この際の書込アドレスp0wa030は、カウント値cnt000がフリップフロップ１３０，１３１，１３２でそれぞれ１クロックずつ遅れたカウント値cnt030[7:0]を８ビット逆シャッフル部（iS8）１０７で８ビット逆シャッフルしたものである。この書込アドレスp0wa030の生成は、ゼロビットプレーン数ＲＡＭ２０からの読出アドレスzbra000の生成と同じ変換であるため、読み出したアドレスと同じアドレスに書き込むことになる。したがって、タグプレーン０ＲＡＭ１１におけるデータの順序は、ゼロビットプレーン数ＲＡＭ２０における順序と同じくラスタスキャン順となる。書込イネーブルp0we030は１クロック毎である。このため、タグプレーン０ＲＡＭ１１にはデータzbrd020が全て書き込まれる。この書込イネーブルp0we030は、カウント値cnt030[8:0]をデコーダ１０５でデコードすることで得られる。
【００８２】
次に、タグプレーン１ＲＡＭ１２の場合について説明する。タグプレーン１ＲＡＭ１２には、データzbrd020の末尾に「１」が付け加えられたデータzbrd020が加工された中間データp1wd030が書き込まれる。ここで、セレクタ１１３には、カウント値cnt020がデコーダ１０４でデコードされたセレクト信号p1sel023が送られる。このセレクト信号p1sel023により、セレクタ１１３は、カウント値cnt020が２＾２（＝４）で割り切れる場合にはデータp1wd021を選択し、割り切れないときには比較部１１２で求められたデータp1wd021とデータp1wd030とのうちの小さい方のデータp1min022をデータp1wd023として出力する。タグプレーン１ＲＡＭ１２には、このデータp1wd023がフリップフロップ１３５で１クロック遅れた中間データp1wd030が書き込まれる。つまり、このセレクタ１１３、比較部１１２及びフリップフロップ１３５は、４クロックの間の最小値を求めるものである。その前段には、データzbrd020か０を選択するセレクタ１１１があり、このセレクタ１１１には、使用される最後の階層番号planeがデコーダ１０６でデコードされたセレクト信号p1sel021が送られる。このセレクト信号p1sel021により、セレクタ１１１は、使用される最後の階層番号planeが１より小さい場合、すなわち階層１を使用しない場合に０を選択する。
【００８３】
この最小値を計算する４クロックの間にカウント値cnt000の下２ビットは「００」，「０１」，「１０」，「１１」と変化し、他の桁は変化しない。ゼロビットプレーン数ＲＡＭ２０の読出アドレスzbra000はカウント値cnt000を８ビット逆シャッフルして作られるため、その２＾０の桁と、２＾４の桁が０、１全ての組み合わせを取るように変化し、他の桁は変化しない。２＾０の桁のみが異なるとゼロビットプレーン数ＲＡＭ２０上で横方向に隣り合い、２＾４の桁のみが異なると縦方向に隣り合うことを考えると、最小値を計算する４クロックの間に４分木の階層１のノードの４つの子のアドレスが生成されることになる。したがって、この４つの値の最小値を求めることにより、階層１のノードの値が決まる。
【００８４】
上述のように、タグプレーン１ＲＡＭ１２には中間データp1wd030が書き込まれるが、その書き込みアドレスはカウント値cnt030[7:2]を６ビット逆シャッフル部（iS6）１０８で６ビット逆シャッフルしたものである。これは、カウント値cnt030を６ビット逆シャッフルして２＾０の桁及び２＾４の桁を取り除いたものと同じである。ゼロビットプレーン数ＲＡＭ２０には２＾４周期のラスタスキャン順でデータが書き込まれているため、タグプレーン１ＲＡＭ１２には２＾３周期のラスタスキャン順でデータが書き込まれることになる。
【００８５】
書込イネーブルp1we030は基本的に４クロック毎である。このため、タグプレーン０ＲＡＭ１１にはデータzbrd020の４個毎の最小値が書き込まれることになる。例外的に始めのデータが流れてきたときにも書き込まれる。このデータは最初の最小値の書き込みで上書きされるため、データ数が４未満の場合に意味がある。使用される最後の階層番号planeが１であればデータ数は(２＾１)＾２＝４であるため、使用される最後の階層番号planeが１未満の場合には書き込んだ値が上書きされないことになる。この場合には上述したセレクタ１１１で選択した０が書き込まれる。
【００８６】
他のタグプレーンｎＲＡＭの場合も同様であり、データzbrd020の２＾(２ｎ)個毎の最小値が書き込まれる。
【００８７】
一方、図１４に示す符号計算部２００は、符号化開始信号enc_start、及び次に符号化するデータの横方向，縦方向のインデックスｘ，ｙを入力とし、外部にあるタグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５に対して読出アドレスpnra100（p0ra100〜p4ra100）、及び読出イネーブルpnre100（p0re100〜p4re100）を送って中間データpnrd110（p0rd110〜p4rd110）を読み出し、コードブロック毎の符号を計算してその符号codeとその長さlenとを出力すると共に、タグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５に対して書込アドレスpnwa130、及び書込イネーブルpnwe130を送って中間データpnwd130を書き込むものである。
【００８８】
タグプレーンｎＲＡＭから中間データpnrd110を読み出す場合、階層０においては、｛ｙ，ｘ｝がそのままタグプレーン０ＲＡＭ１１にアクセスするための読出アドレスp0ra100となる。また、階層１においては、｛ｘ／２，ｙ／２｝がタグプレーン１ＲＡＭ１２にアクセスするための読出アドレスp1ra100となる。各階層で縦横それぞれ１／２に縮小されていることを考えると、階層１での横方向のオフセットを０として読み出すのはｘが０，１のとき、オフセットを１として読み出すのはｘが２，３のとき、となるからである。以降の階層についても同様であり、階層ｎにおいては、｛ｘ／(２＾ｎ），ｙ／(２＾ｎ）｝がタグプレーンｎＲＡＭにアクセスするための読出アドレスpnra100となる。なお、タグプレーンｎＲＡＭの読出イネーブルpnre100には符号化開始信号enc_startをそのまま使う。
【００８９】
先ず、全符号の長さlenを求めるための構成について説明する。タグプレーン０ＲＡＭ１１〜タグプレーン４ＲＡＭ１５から読み出された中間データp0rd〜p4rdは、それぞれフリップフロップ２０３〜２０７に送られ、続くクロックでデータpnrd120として使えるようになっている。データpnrd120の最下位ビット以外がゼロビットプレーン数を表しているため、階層ｎのノードの符号はp(n+1)rd120[4:1]−pnrd120[4:1]個の「０」の後に１個の「１」が続くもので、その長さはp(n+1)rd120[4:1]−pnrd120[4:1]＋１である。そこで、符号長演算部２０８〜２１２は、このp(n+1)rd120[4:1]−pnrd120[4:1]＋１を階層ｎのノードの符号長として出力する。ここで、この階層ｎのノードの符号長とデータpnlen121とは、データpnrd120[0]が０のときにデータpnlen121が０となる点を除いて同じである。データpnrd120[0]が０のときには既に当該ノードの符号化が終わっており符号が発生しないことを考慮すると、階層ｎのノードで実際に発生する符号の長さは、ＡＮＤ回路２１３〜２１７において符号長演算部２０８〜２１２の出力とデータpnlen121との論理積をとったデータpnlen121で表される。
【００９０】
階層ｎのノードの符号長を表すデータpnlen121が得られると、加算器２１８〜２２１は、これらのデータを加算し、全符号の長さlenを求める。ここで、データpnlen121とデータp(n-1)len122とが加算されてデータpnlen122が作られているため、データpnlen122は階層ｎ以下の符号長の和となっている。したがって、全符号の長さlenは、加算器２２１から出力されたデータp4len122で表される。
【００９１】
続いて、全符号codeを求めるための構成について説明する。上述したように、階層ｎのノードの符号は、p(n+1)rd120[4:1]−pnrd120[4:1]個の「０」の後に１個の「１」が続くものである。符号計算部２００では、このノード毎の符号を繋げるのではなく、階層１以上のノードについてはpnデコーダ２２２〜２２５で符号を生成し、階層０のノードの符号とpnデコーダ２２２〜２２５の出力データ（p1code〜p4code）とについてＯＲ回路２２６で論理和をとって実際に出力する符号codeを作るという構成になっている。データpnrd120[0]が０の場合には、階層ｎでは符号が出力されないため、データpncodeは「０」である。一方、データpnrd120[0]が１の場合には、データpncodeは１個の「１」の後にp(n-1)len122個の「０」が続くものとなっている。p(n-1)len122個の「０」は、葉に近い階層の符号と論理和をとるときのためのビットであり、その上の桁の１個の「１」がこの階層の符号の「１」である。各階層のノードで出力される符号は幾つかの「０」が続いた後に１個の「１」が続くものであるため、このように最下位ビットの「１」の桁だけを合わせる構成になっている。
【００９２】
ＡＮＤ回路２２７〜２３１は、データpnrd120と符号「１１１１０」との論理積をとることにより、データpnrd120の最下位ビットを「０」で置き換えたデータpnwd120を生成する。このデータpnwd120がフリップフロップ２３３〜２３７で１クロック遅れたデータpnwd130がタグプレーンｎＲＡＭに書き戻される中間データとなる。タグプレーンｎＲＡＭのデータの最下位ビットの初期値は「１」になっているため、各ノードは最初に読み出されて符号化されるときには符号が発生するが、２度目以降の読み出しにおいては符号が発生しないようになっている。書き戻す際の書込アドレスpnwa130は、読出アドレスpnra100と同様に｛ｘ／(２＾ｎ），ｙ／(２＾ｎ）｝である。また、書込イネーブルpnwe130には、符号化開始信号enc_startがフリップフロップ２０１，２０２，２３２でそれぞれ１クロック遅れた信号start130が用いられる。
【００９３】
具体的に、図３（Ｂ）に示したゼロビットプレーン数を符号化する場合について考える。符号化は、レイヤ０からラスタスキャン順に行われる。
【００９４】
最初に符号化されるのは、葉(1, 0)である。タグプレーンｎＲＡＭから読み出されたデータの下位１ビットは、
p0rd120[0]＝１
p1rd120[0]＝１
p2rd120[0]＝１
p3rd120[0]＝１
p4rd120[0]＝０
であり、上位４ビットは、
p0rd120[4:1]＝３
p1rd120[4:1]＝２
p2rd120[4:1]＝１
p3rd120[4:1]＝１
p4rd120[4:1]＝０
という値である。
【００９５】
ここで、pnlen121は以下で表される。
p0rd120[0]＝１なので、p0len121＝p0rd120[4:1]−p1rd120[4:1]＋１＝３−２＋１＝２
p1rd120[0]＝１なので、p1len121＝p1rd120[4:1]−p2rd120[4:1]＋１＝２−１＋１＝２
p2rd120[0]＝１なので、p2len121＝p2rd120[4:1]−p3rd120[4:1]＋１＝１−１＋１＝１
p3rd120[0]＝１なので、p3len121＝p3rd120[4:1]−p4rd120[4:1]＋１＝１−０＋１＝２
p4rd120[0]＝０なので、p4len121＝０
【００９６】
したがって、pnlen122は次の通りになる。
p0len122＝p0len121＝２
p1len122＝p1len121＋p0len122＝２＋２＝４
p2len122＝p2len121＋p1len122＝１＋４＝５
p3len122＝p3len121＋p2len122＝２＋５＝７
p4len122＝p4len121＋p3len122＝０＋７＝７
【００９７】
一方、pncodeは次の通りになる。
p0code＝p0rd120[0]＝１
p1rd120[0]＝１なので、p0len122＝２を使って、p1code＝１００
p2rd120[0]＝１なので、p1len122＝４を使って、p2code＝１００００
p3rd120[0]＝１なので、p2len122＝５を使って、p3code＝１０００００
p4rd120[0]＝０なので、p4code＝０
これらのpncodeの論理和をとることにより、code＝１１０１０１が得られる。
【００９８】
また、符号長は、len＝p4len122＝７である。
【００９９】
したがって、７ビットになるようにcodeの上位に０を補った「０１１０１０１」が実際の符号である。これは、図４の葉(1, 0)の符号と一致している。
【０１００】
pnrd120の値は、「１１１１０」と論理積をとってpnwd120となり、タグプレーンｎＲＡＭに書き戻される。このため、タグプレーンｎＲＡＭのデータは、２回目以降に読み出されたときには最下位ビットが必ず「０」となっている。
【０１０１】
続いて符号化されるのは、葉(2, 0)である。タグプレーンｎＲＡＭから読み出されたデータの下位１ビットは、
p0rd120[0]＝１
p1rd120[0]＝１
p2rd120[0]＝０
p3rd120[0]＝０
p4rd120[0]＝０
であり、上位４ビットは、
p0rd120[4:1]＝３
p1rd120[4:1]＝１
p2rd120[4:1]＝１
p3rd120[4:1]＝１
p4rd120[4:1]＝０
という値である。
【０１０２】
ここで、pnlen121は以下で表される。
p0rd120[0]＝１なので、p0len121＝p0rd120[4:1]−p1rd120[4:1]＋１＝３−１＋１＝３
p1rd120[0]＝１なので、p1len121＝p1rd120[4:1]−p2rd120[4:1]＋１＝１−１＋１＝１
p2rd120[0]＝０なので、p2len121＝０
p3rd120[0]＝０なので、p3len121＝０
p4rd120[0]＝０なので、p4len121＝０
【０１０３】
したがって、pnlen122は次の通りになる。
p0len122＝p0len121＝３
p1len122＝p1len121＋p0len122＝１＋３＝４
p2len122＝p2len121＋p1len122＝０＋４＝４
p3len122＝p3len121＋p2len122＝０＋４＝４
p4len122＝p4len121＋p3len122＝０＋４＝４
【０１０４】
一方、pncodeは次の通りになる。
p0code＝p0rd120[0]＝１
p1rd120[0]＝１なので、p0len122＝３を使って、p1code＝１０００
p2rd120[0]＝０なので、p2code＝０
p3rd120[0]＝０なので、p3code＝０
p4rd120[0]＝０なので、p4code＝０
これらのpncodeの論理和をとることにより、code＝１００１が得られる。
【０１０５】
また、符号長は、len＝p4len122＝４である。
【０１０６】
code＝１００１は符号長が４ビットであるため、これが実際の符号である。これは、図４の葉(2, 0)の符号と一致している。
【０１０７】
以降の葉の符号化についても同様である。
【０１０８】
次に、インクルージョン情報をタグツリーにより符号化する本実施の形態における符号化装置の概略構成を図１５に示す。この符号化装置３０は、データ読出開始信号read_start、使用される最後の階層番号plane、符号化開始信号enc_start、レイヤ番号layer、及びインデックスｘ，ｙを入力とし、外部にあるインクルージョン情報ＲＡＭ４０に対して読出アドレスzbra000、読出イネーブル信号zbre000を送ってインクルージョン情報を表すデータzbrd010を読み出し、コードブロック毎のインクルージョン情報の符号を計算して、その符号codeとその長さlenとを出力するものである。
【０１０９】
インクルージョン情報ＲＡＭ４０は、１ワード＝４ビットで２５６ワードの容量である。アドレスｈ＋ｖ×１６に書き込まれている値は、葉(h, v)に対応するコードブロックのインクルージョン情報である。インクルージョン情報ＲＡＭ４０にはインクルージョン情報のデータが横方向の周期１６でラスタスキャン順で書き込まれていると表現することもできる。なお、画枠が小さい等の理由でコードブロックが存在しない場合、存在しないコードブロックに対応するアドレスには、使われることのない大きな値がインクルージョン情報として書き込まれている。
【０１１０】
符号化装置３０は、中間データ生成部３００と、符号計算部４００とを有する。中間データ生成部３００は、インクルージョン情報ＲＡＭ４０から所定の順序でデータzbrd010を読み出し、中間データとしてタグツリーの各階層の値を生成し、その中間データをタグプレーン０ＲＡＭ３１〜タグプレーン４ＲＡＭ３５に書き込む。なお、このタグプレーン０ＲＡＭ３１〜タグプレーン４ＲＡＭ３５には、それぞれタグプレーンの階層０〜階層４の値が書き込まれる。一方、符号計算部４００は、タグプレーン０ＲＡＭ３１〜タグプレーン４ＲＡＭ３５から中間データを読み出し、インクルージョン情報の符号を計算して、その符号codeとその長さlenとを出力する。中間データ生成部３００の詳細な構成を図１６に、符号計算部４００の詳細な構成を図１７にそれぞれ示す。
【０１１１】
図１６に示す中間データ生成部３００は、データ読出開始信号read_start、及び使用される最後の階層番号planeを入力とし、外部にあるインクルージョン情報ＲＡＭ４０に対して読出アドレスzbra000、及び読出イネーブルzbre000を送ってインクルージョン情報を表すデータzbrd010を読み出し、中間データとしてタグツリーの各階層の値を生成し、その中間データをタグプレーン０ＲＡＭ３１〜タグプレーン４ＲＡＭ３５に書き込むものである。この中間データ生成部３００の処理は、インクルージョン情報ＲＡＭ４０からデータを読み出す点以外は上述した中間データ生成部１００の処理と同様であるため、同一の構成については同一の符号を付し、詳細な説明を省略する。
【０１１２】
一方、図１７に示す符号計算部４００は、符号化開始信号enc_start、符号化中のレイヤ番号layer、及び次に符号化するデータの横方向，縦方向のインデックスｘ，ｙを入力とし、外部にあるタグプレーン０ＲＡＭ３１〜タグプレーン４ＲＡＭ３５に対して読出アドレスpnra100（p0ra100〜p4ra100）、及び読出イネーブルpnre100（p0re100〜p4re100）を送って中間データpnrd110（p0rd110〜p4rd110）を読み出し、コードブロック毎の符号を計算してその符号codeとその長さlenとを出力するものである。
【０１１３】
タグプレーンｎＲＡＭから中間データpnrd110を読み出す場合、階層０においては、｛ｙ，ｘ｝がそのままタグプレーン０ＲＡＭ３１にアクセスするための読出アドレスp0ra100となる。また、階層１においては、｛ｘ／２，ｙ／２｝がタグプレーン１ＲＡＭ３２にアクセスするための読出アドレスp1ra100となる。各階層で縦横それぞれ１／２に縮小されていることを考えると、階層１での横方向のオフセットを０として読み出すのはｘが０，１のとき、オフセットを１として読み出すのはｘが２，３のとき、となるからである。以降の階層についても同様であり、階層ｎにおいては、｛ｘ／(２＾ｎ），ｙ／(２＾ｎ）｝がタグプレーンｎＲＡＭにアクセスするための読出アドレスpnra100となる。なお、タグプレーンｎＲＡＭの読出イネーブルpnre100には符号化開始信号enc_startをそのまま使う。
【０１１４】
タグプレーンｎＲＡＭから読み出されたデータpnrd110はフリップフロップ４０１〜４０５に入る。フリップフロップ４０１〜４０５から出力されたデータpnrd120、レイヤ番号layer、及びインデックスｘ，ｙを入力とした組み合わせ回路により、符号code及びその長さlenが求められる。その組み合わせ回路について以下で説明する。
【０１１５】
比較部４０６〜４１０は、データpnrd120とレイヤ番号layerとを比較し、pnrd120＞layerであるか否かをデータpngrとして、pnrd120≧layerであるか否かをデータpngeとして出力する。
【０１１６】
タグツリーによる符号化においては、既に符号化されているため符号が出力されない場合がある。階層ｎで符号が出力される可能性がない場合にデータpnvalidが０となり、符号が出力される可能性がある場合にデータpnvalidが１となるようにデータpnvalidの値を計算するように回路が接続されている。
【０１１７】
具体的に、階層０において既に符号化されていることはない。そこで、符号が出力される可能性があるため、データp0validは「１」で固定となっている。
【０１１８】
階層１においては、葉(0, 0)、葉(0, 1)、葉(1, 0)、葉(1, 1)の共通の親が１回だけ符号化されることを考えると、ｘ，ｙが共に２の倍数であればデータp0validは「１」であり、そうでなければデータp0validは「０」である。図１７では、ＮＯＲ回路４１１の出力をデータp1validとすることにより、ｘ，ｙの下１桁に「１」があればデータp1validが「０」となり、何れも「０」ならデータp1validが「１」となる構成になっている。
【０１１９】
同様に、階層ｎ（ｎ≧２）においては、ｘ，ｙが共に２＾ｎの倍数であればデータpnvalidは「１」であり、そうでなければデータpnvalidは「０」である。図１７では、ＮＯＲ回路４１２〜４１４の出力をデータpnvalidとすることにより、ｘ，ｙの下１桁に「１」があればデータpnvalidが「０」となり、何れも「０」ならデータpnvalidが「１」となる構成になっている。
【０１２０】
各階層では、１ビットの符号「０」又は「１」が発生するか、それとも符号が発生しないかである。符号が発生する場合、データpnrd120が現在符号化しているレイヤ番号layer以上であれば「０」、それ以外なら「１」なので、データpngrの否定と同じである。そこで、ＮＯＴ回路４１５〜４１９においてデータpngrを反転してデータpncodeを求め、これを並べることで、データtmpcode{p6code, p5code,..., p0code}を作っている。
【０１２１】
また、図１７において、ＡＮＤ回路４２０〜４２４は、データp(n+1)grとデータpnvalidとの論理積をとってデータpnmaskedを出力し、ＡＮＤ回路４２５〜４２９は、データpngeとデータpnvalidとの論理積をとってデータpnusedを出力している。そして、加算器４３０は、データpnmaskedを加算することによりデータpnmaskedが１であるものの数を表すデータmaskedを求め、加算器４３１は、データpnusedを加算することによりデータpnusedが１であるものの数を表すデータusedを求めている。差分器４３２は、データusedからデータmaskedを減算することにより符号の長さlenを求めて出力している。また、シフト回路４３３は、データtmpcodeをデータmaskedで表されるビット数だけ右シフトしたものを符号codeとして出力している。このデータused、データmasked、及び符号の長さlenの関係を図１８に示す。図１８に示すように、データtmpcodeの下位のデータusedで示される数のビットから下位のデータmaskedで示されるビットを取り除いたものが、最終的な符号codeとなっている。
【０１２２】
ここで、レイヤＬの符号化を各階層のノードの符号化に着目してみると、(a)レイヤＬ未満で既に値が確定している、(b)現在の値のままレイヤＬで値が確定する、(c)レイヤＬで現在の値が１増える、の３通りに分類される。(a)の場合には符号が発生せず、(b)の場合は符号「１」が発生し、(c)の場合は符号「０」が発生する。
【０１２３】
この各階層での符号が上述したデータpncodeと類似することを簡単に説明する。データpncodeを並べたデータtmpcodeは、ＭＳＢから何ビットか「１」が連続し、続いてＬＳＢ（Least Significant Bit）まで何ビットか「０」が連続するというものである（全て「１」、又は全て「０」の場合も含む。）。ＬＳＢ側の連続する「０」は(c)で出力される符号に対応する。他の連続する「１」には、(b)に対応していて符号となるものと、(a)に対応していて符号とならないものとがある。
【０１２４】
データpngeが１となるのはpnrd120≧layerのときであったので、以前のレイヤで階層ｎの値は確定していないことを表す。そこで、データtmpcodeから(a)に対応する部分を取り除くには、データpngeが０の部分を取り除けばよい。これは、データpngeが１である階層の数だけのビット数をデータtmpcodeのＬＳＢ側から使うことにより実現できる。但し、データpnvalidが１という条件も満たす必要があるため、図１７では、データpngeが１であり且つデータpnvalidである階層の数を計算してデータusedとしている。
【０１２５】
(c)のデータを１つ符号化すると現在の値が１増えるため、最初に含まれるのはレイヤＬ＋１以上であることが確定する。このため、(c)のデータは各レイヤで１つだけ符号化すればよい。番号が大きい階層が先に符号化されることを考えると、データpngrが１であった場合、階層ｎ−１では(c)のデータが出力されないことが分かる。但し、データpnvalidが１という条件も満たす必要があるため、図１７では、データp(n+1)grが１であり且つデータpnvalidが１である階層の数を計算して、(c)のデータが出力されない階層の数を示すデータmaskedを求めている。そして、データusedとデータmaskedとを用いることにより、図１８で表されるように、データtmpcodeから実際の符号codeを取り出して出力するようになっている。
【０１２６】
なお、以上の説明ではデータpnmaskedが１であるものの数を表すデータmasked、及びデータpnusedが１であるものの数を表すデータusedを求めるために、加算器４３０，４３１を用いたが、実際には普通の加算器を用いることなく、図１９で示されるようなケース文に従って簡単に求めることができる。この場合、ドントケアが多いため、非常に簡単な回路となる。
【０１２７】
具体的に、図８（Ｂ）に示した情報を符号化する場合について考える。
【０１２８】
レイヤ１で葉(0, 0)を符号化する場合であれば、入力される座標は、{y, x}＝{0000, 0000}であり、符号化するレイヤ番号layerは、layer＝１である。
【０１２９】
pnvalidの値は、次の通りである。
p0valid＝１
p1valid＝~(y[0] | x[0])＝~０＝１
p2valid＝~(y[1:0] | x[1:0]) ＝~０＝１
p3valid＝~(y[2:0] | x[2:0]) = ~０＝１
p4valid＝~(y[3:0] | x[3:0]) = ~０＝１
【０１３０】
また、タグプレーンｎＲＡＭから読み出されたデータは次のようになる。
p0rd120＝３
p1rd120＝２
p2rd120＝１
p3rd120＝１
p4rd120＝０
【０１３１】
そこで、
p0gr＝p1gr＝１、p2gr＝p3gr＝p4gr＝０
p0ge＝p1ge＝p2ge＝p3ge＝１、p4ge＝０
となる。
【０１３２】
ここで、pncode＝~pngrなので、
p0code＝p1code＝０、p2code＝p3code＝p4code＝１
となる。
【０１３３】
また、pnused＝pnvalid ＆ pngeなので、
p0used＝p1used＝p2used＝p3used＝１、p4used＝０
となる。
【０１３４】
また、pnmasked＝pnvalid ＆ p(n+1)grなので、
p0masked＝１、p1masked＝p2masked＝p3masked＝p4masked＝０
となる。
【０１３５】
よって、
used＝p0used＋p1used＋p2used＋p3used＋p4used＝４
masked＝p0masked＋p1masked＋p2masked＋p3masked＋p4masked＝１
tmpcode＝{p4code, p3code, ..., p0code}＝１１１００
code＝tmpcode>>masked＝１１１００>>１＝１１１０
len＝used−maked＝４−１＝３
となる。
【０１３６】
したがって、code＝１１１０のうちＬＳＢ側のlen＝３ビットが実際の符号「１１０」である。これは、図９の葉(0, 0)のレイヤ１における符号と一致している。
【０１３７】
次に、レイヤ１で葉(2, 0)を符号化する場合であれば、入力される座標は、{y, x} = {0000, 0010}であり、符号化するレイヤ番号layerは、layer＝１である。
【０１３８】
pnvalidの値は、次の通りである。
p0valid＝１
p1valid＝~(y[0] | x[0])＝~０＝１
p2valid＝~(y[1:0] | x[1:0])＝~１＝０
p3valid＝~(y[2:0] | x[2:0])＝~１＝０
p4valid＝~(y[3:0] | x[3:0])＝~１＝０
【０１３９】
また、タグプレーンｎＲＡＭから読み出された値は次のようになる。
p0rd120＝３
p1rd120＝１
p2rd120＝１
p3rd120＝１
p4rd120＝０
【０１４０】
そこで、
p0gr＝１、p1gr＝p2gr＝p3gr＝p4gr＝０
p0ge＝p1ge＝p2ge＝p3ge＝１、p4ge＝０
となる。
【０１４１】
ここで、pncode＝~pngrなので、
p0code＝0、p1code＝p2code＝p3code＝p4code＝１
となる。
【０１４２】
また、pnused＝pnvalid ＆ pngeなので、
p0used＝p1used＝１、p2used＝p3used＝p4used＝０
となる。
【０１４３】
また、pnmasked＝pnvalid ＆ p(n+1)grなので、
p0masked＝p1masked＝p2masked＝p3masked＝p4masked＝０
となる。
【０１４４】
よって、
used＝p0used＋p1used＋p2used＋p3used＋p4used＝２
masked＝p0masked＋p1masked＋p2masked＋p3masked＋p4masked＝０
tmpcode＝{p4code, p3code, ..., p0code}＝１１１１０
code＝tmpcode>>masked＝１１１１０>>０＝１１１１０
len＝used−maked＝２−０＝２
となる。
【０１４５】
したがって、code＝１１１１０のうちＬＳＢ側のlen＝２ビットが実際の符号「１０」である。これは、図９の葉(2, 0)のレイヤ１における符号と一致している。
【０１４６】
以降の葉の符号化についても同様である。
【０１４７】
以上説明したように、本実施の形態における符号化装置１０，３０によれば、ＪＰＥＧ２０００方式におけるゼロビットプレーン数の情報やインクルージョン情報をタグツリーにより符号化する際に、従来のソフトウェアの方法のように逐次的なループ処理がないため、高速に処理を行うことができる上、組み合わせ回路で済むためハードウェア規模を小さく抑えることができ、消費電力も少ない。さらに、設計及び検証に要する時間も短くなる上、順序回路の場合に必要だった常態変数のためのメモリが不要になるという利点がある。
【０１４８】
また、この符号化装置１０，３０によれば、各ノードの実際の値のためのメモリのみで済むため、省メモリになるという特徴がある。因みに、従来のソフトウェアの方法をそのまま使った場合には、他にタグツリーのデータ構造のためのメモリや、各ノードについて必要な親ノードへのポインタ、現在の値、値が確定しているか否かのフラグのためのメモリが必要となる。
【０１４９】
さらに、符号化装置３０によれば、符号計算部４００においてデータpnvalidが０である階層ｎでは信号が０になるため、例えば階層１では１／４(＝１／(２＾２))の間信号が変化せず、階層２では１／１６(＝１／(２＾４))の間、一般的に階層ｎでは１／(２＾２ｎ)の間変化せず、省電力になるという効果がある。
【０１５０】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【０１５１】
例えば、上述した符号化装置１０，３０は、葉の数が縦１６横１６までのタグツリーを取り扱えるものであったが、より大きいタグツリーを扱いたい場合には、ゼロビットプレーン数ＲＡＭ２０又はインクルージョン情報ＲＡＭ４０のワード数を増やし、符号化装置内部で階層を増やすと共に、カウンタのビット数を増やせばよい。また、最大のレイヤ番号を増やしたい場合には、ゼロビットプレーン数ＲＡＭ２０又はインクルージョン情報ＲＡＭ４０のワード長を大きくし、データパスのビット幅とタグプレーンｎＲＡＭのワード長もそれに応じて増やせばよい。
【図面の簡単な説明】
【０１５２】
【図１】タグツリーを説明する図である。
【図２】各コードブロックのゼロビットプレーン数をタグツリーによって符号化する場合の処理順序を説明するフローチャートである。
【図３】各レイヤで符号化するゼロビットプレーン数の情報を示す図である。
【図４】ゼロビットプレーン数をタグツリーによって符号化する際に、各レイヤにおいて各コードブロックの符号化で発生する符号を示す図である。
【図５】関数jpc_tagtree_encode()の処理を説明するフローチャートである。
【図６】タグツリーを葉から根へと辿る際に記憶されるポインタを示す図である。
【図７】各コードブロックのインクルージョン情報をタグツリーによって符号化する場合の処理順序を説明するフローチャートである。
【図８】各レイヤで符号化する情報を示す図である。
【図９】インクルージョン情報をタグツリーによって符号化する際に、各レイヤにおいて各コードブロックの符号化で発生する符号を示す図である。
【図１０】ゼロビットプレーン数をタグツリーにより符号化する本実施の形態における符号化装置の概略構成を示す図である。
【図１１】同符号化装置の中間データ生成部の詳細な構成を示す図である。
【図１２】同中間データ生成部における８ビット逆シャッフルを説明する図である。
【図１３】８ビット逆シャッフルによる変換後の読出アドレスzbra000を説明する図である。
【図１４】同符号化装置の符号計算部の詳細な構成を示す図である。
【図１５】インクルージョン情報をタグツリーにより符号化する本実施の形態における符号化装置の概略構成を示す図である。
【図１６】同符号化装置の中間データ生成部の詳細な構成を示す図である。
【図１７】同符号化装置の符号計算部の詳細な構成を示す図である。
【図１８】データused、データmasked、及び符号の長さlenの関係を説明する図である。
【図１９】同符号計算部の加算器と同様の処理を実現するケース文を示す図である。
【図２０】ＪＰＥＧ２０００方式に従って画像データを圧縮符号化する画像符号化装置の概略構成の一例を示す図である。
【図２１】同画像符号化装置におけるウェーブレット変換を説明する図である。
【図２２】同画像符号化装置におけるコードブロック化、エントロピー符号化及びレイヤ化を説明する図である。
【符号の説明】
【０１５３】
１０，３０  符号化装置、１１〜１５  タグプレーン０ＲＡＭ〜タグプレーン４ＲＡＭ、２０  ゼロビットプレーン数ＲＡＭ、４０  インクルージョン情報ＲＡＭ、１００，３００  中間データ生成部、１０１  カウンタ、１０２  ８ビット逆シャッフル部、１０３〜１０６  デコーダ、２００，４００  符号計算部、
【図１】
2006115194.tif 000003
【図２】
2006115194.tif 000004
【図３】
2006115194.tif 000005
【図４】
2006115194.tif 000006
【図５】
2006115194.tif 000007
【図６】
2006115194.tif 000008
【図７】
2006115194.tif 000009
【図８】
2006115194.tif 000010
【図９】
2006115194.tif 000011
【図１０】
2006115194.tif 000012
【図１１】
2006115194.tif 000013
【図１２】
2006115194.tif 000014
【図１３】
2006115194.tif 000015
【図１４】
2006115194.tif 000016
【図１５】
2006115194.tif 000017
【図１６】
2006115194.tif 000018
【図１７】
2006115194.tif 000019
【図１８】
2006115194.tif 000020
【図１９】
2006115194.tif 000021
【図２０】
2006115194.tif 000022
【図２１】
2006115194.tif 000023
【図２２】
2006115194.tif 000024