(57)【要約】【課題】ＪＰＥＧ−２０００におけるＳｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（ＳＰパス）での処理時間を短くすることで３つの符号化パスでの符号ブロックの符号化を高速化する。【解決手段】ビットプレーン符号化パス生成部は、ビットプレーンに分割された符号ブロック毎の量子化係数をＳＰパスで処理する際に、予め定めたエリア及びその周囲における有意（ｓｉｇｎｉｆｉｃａｎｔ：Ｓ）か否か（ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ：Ｎ）のデータをメモリから読み出し、これをＳ／Ｎマッチングパターンと比較する。このＳ／Ｎマッチングパターンは、任意のサンプル点から次のＳＰパス処理対象サンプル点にジャンプ可能な場合におけるパターンが設定されたものであり、現在のＳ／Ｎマッチングパターンと一致するパターンから得られたジャンプアドレス値により、次のＳＰパス処理対象サンプル点にジャンプする。【選択図】　図６
2004080273.tif 000002
【特許請求の範囲】
【請求項１】
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換手段と、
上記ウェーブレット変換手段によって生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成手段と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成手段と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理手段と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化手段とを備え、
上記符号化パス処理手段は、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行うことにより、次の処理対象となるサンプル点を検出すること
を特徴とする画像符号化装置。
【請求項２】
上記マッチングパターンは、任意のサンプル点位置から次の処理対象サンプル点位置へとジャンプ可能である場合における複数のサンプル点での有意又は非有意のパターンを示したものであり、
上記符号化パス処理手段は、上記現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における上記有意／非有意情報と上記複数のマッチングパターンとの比較を並列して行うことにより、現サンプル点位置からジャンプ可能なサンプル点を検出すること
を特徴とする請求項１記載の画像符号化装置。
【請求項３】
上記マッチングパターンにはそれぞれジャンプアドレス値が設定されており、
上記符号化パス処理手段は、上記有意／非有意情報と上記複数のマッチングパターンとを比較した結果、何れかのマッチングパターンと一致した場合には、当該一致したマッチングパターンに設定されている上記ジャンプアドレス値に応じて、次の処理対象となるサンプル点を検出すること
を特徴とする請求項１記載の画像符号化装置。
【請求項４】
上記符号化パス処理手段は、上記有意／非有意情報と上記複数のマッチングパターンとを比較した結果、何れのマッチングパターンとも一致しなかった場合には、上記所定のサンプル数の新たな領域を設定し、当該新たな領域及びその周囲のサンプル点における有意又は非有意を示す新たな有意／非有意情報を上記記憶手段から読み出し、この新たな有意／非有意情報と予め設定された上記複数のマッチングパターンとの比較を並列して行うことを特徴とする請求項３記載の画像符号化装置。
【請求項５】
上記有意／非有意情報は、各符号ブロック毎に予め非有意に初期化されることを特徴とする請求項１記載の画像符号化装置。
【請求項６】
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換手段と、
上記ウェーブレット変換手段によって生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成手段と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成手段と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理手段と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化手段とを備え、
上記符号化パス処理手段は、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行い、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点を、次の処理対象となるサンプル点として検出すること
を特徴とする画像符号化装置。
【請求項７】
上記符号化パス処理手段は、上記有意／非有意情報と上記複数のマッチングパターンとを比較した結果、一致するサンプル点がなかった場合には、上記所定のサンプル数の新たな領域を設定し、当該新たな領域及びその周囲のサンプル点における有意又は非有意を示す新たな有意／非有意情報を上記記憶手段から読み出し、この新たな有意／非有意情報と予め設定された上記複数のマッチングパターンとの比較を並列して行うことを特徴とする請求項６記載の画像符号化装置。
【請求項８】
上記有意／非有意情報は、各符号ブロック毎に予め非有意に初期化されることを特徴とする請求項６記載の画像符号化装置。
【請求項９】
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、
上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、
上記符号化パス処理工程では、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われることにより、次の処理対象となるサンプル点が検出されること
を特徴とする画像符号化方法。
【請求項１０】
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、
上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、
上記符号化パス処理工程では、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点が、次の処理対象となるサンプル点として検出されること
を特徴とする画像符号化方法。
【請求項１１】
所定の処理をコンピュータに実行させるプログラムにおいて、
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、
上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、
上記符号化パス処理工程では、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われることにより、次の処理対象となるサンプル点が検出されること
を特徴とするプログラム。
【請求項１２】
所定の処理をコンピュータに実行させるプログラムにおいて、
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、
上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、
上記符号化パス処理工程では、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点が、次の処理対象となるサンプル点として検出されること
を特徴とするプログラム。
【請求項１３】
所定の処理をコンピュータに実行させるプログラムが記録されたコンピュータ読み取り可能な記録媒体において、
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、
上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、
上記符号化パス処理工程では、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われることにより、次の処理対象となるサンプル点が検出されること
を特徴とするプログラムが記録された記録媒体。
【請求項１４】
所定の処理をコンピュータに実行させるプログラムが記録されたコンピュータ読み取り可能な記録媒体において、
入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、
上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、
上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、
上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、
上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、
上記符号化パス処理工程では、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点が、次の処理対象となるサンプル点として検出されること
を特徴とするプログラムが記録された記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えばＪＰＥＧ−２０００のように、ウェーブレット変換とエントロピー符号化とにより画像を圧縮する画像符号化装置及び方法、並びに画像符号化処理をコンピュータに実行させるプログラム及びそのプログラムが記録された記録媒体に関する。
【０００２】
【従来の技術】
従来の代表的な画像圧縮方式として、ＩＳＯ（Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｔａｎｄａｒｄｓ　Ｏｒｇａｎｉｚａｔｉｏｎ）によって標準化されたＪＰＥＧ（Ｊｏｉｎｔ　Ｐｈｏｔｏｇｒａｐｈｉｃ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ）方式がある。これは、離散コサイン変換（ＤＣＴ：Ｄｅｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ）を用い、比較的高いビットが割り当てられる場合には、良好な符号化画像及び復号画像を供することが知られている。しかし、ある程度以上に符号化ビット数を少なくすると、ＤＣＴ特有のブロック歪みが顕著になり、主観的に劣化が目立つようになる。
【０００３】
一方、近年では画像をフィルタバンクと呼ばれるハイパス・フィルタとローパス・フィルタとを組み合わせたフィルタによって複数の帯域に分割し、各帯域毎に符号化を行う方式の研究が盛んになっている。その中でも、ウェーブレット変換符号化は、ＤＣＴのように高圧縮でブロック歪みが顕著になるという欠点がないことから、ＤＣＴに代わる新たな技術として有力視されている。
【０００４】
例えば２００１年１月に国際標準化が完了したＪＰＥＧ−２０００は、このウェーブレット変換に高能率なエントロピー符号化（ビットプレーン単位のビット・モデリングと算術符号化）を組み合わせた方式を採用しており、ＪＰＥＧに比べて符号化効率の大きな改善を実現している。
【０００５】
このＪＰＥＧ−２０００方式で圧縮符号化を行う画像符号化装置においては、入力画像に対してウェーブレット変換処理を施すことにより複数のサブバンドに分割し、各サブバンド毎のウェーブレット変換係数に対して量子化処理を施す。そして、得られたサブバンド毎の量子化係数をエントロピー符号化の処理単位である例えば６４×６４程度の所定の大きさの符号ブロックに分割し、この符号ブロック単位の量子化係数に対して、係数ビット・モデリングを行う。
【０００６】
ここで、この係数ビット・モデリングについて詳細に説明する。なお、以下では、特にＪＰＥＧ−２０００規格で定められたＥＢＣＯＴ（Ｅｍｂｅｄｄｅｄ　Ｃｏｄｉｎｇ　ｗｉｔｈ　Ｏｐｔｉｍｉｚｅｄ　Ｔｒｕｎｃａｔｉｏｎ）と呼ばれるエントロピー符号化を例に取りながら説明する。このＥＢＣＯＴについては、例えば、文献「ＩＳ０／ＩＥＣ　１５４４４−１，　Ｉｎｆｏｒｍａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｙ−ＪＰＥＧ　２０００，　Ｐａｒｔ　１：Ｃｏｒｅ　ｃｏｄｉｎｇ　ｓｙｓｔｅｍ」等に詳細に記載されている。
【０００７】
このＥＢＣＯＴの説明の前に、ビットプレーンの概念について図２３を用いて説明する。図２３（Ａ）は、縦４個、横４個の計１６個の係数から成る量子化係数を仮定したものである。この１６個の係数のうち絶対値が最大のものは１３であり、２進数表現では１１０１となる。したがって、係数の絶対値のビットプレーンは、図２３（Ｂ）に示すような４つのビットプレーンから構成される。なお、各ビットプレーンの要素（サンプル点）は、全て０又は１の数を取る。一方、量子化係数の符号は、−６が唯一負の値であり、それ以外は０又は正の値である。したがって、符号のビットプレーンは、図２３（Ｃ）に示すようになる。
【０００８】
ＥＢＣＯＴは、所定の大きさのブロック毎にそのブロック内の係数ビットデータの統計量を測定しながら符号化する手段であり、符号ブロック単位に係数ビットデータをエントロピー符号化する。符号ブロックは、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）方向にビットプレーン毎に独立して符号化される。また、符号ブロックの縦横のサイズは、４から２５６までの２の冪乗で、通常は３２×３２、６４×６４、１２８×３２等の大きさが使用される。量子化係数は、ｎビットの符号付き２進数で表されており、ｂｉｔ０からｂｉｔ（ｎ−２）がＬＳＢからＭＳＢまでのそれぞれのビットを表す。なお、残りの１ビットは符号である。符号ブロックの符号化は、ＭＳＢ側のビットプレーンから順番に、以下の（ａ）〜（ｃ）に示す３種類の符号化パスによって行われる。
【０００９】
（ａ）　Ｓｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ
（ｂ）　Ｍａｇｎｉｔｕｄｅ　Ｒｅｆｉｎｅｍｅｎｔ　Ｐａｓｓ
（ｃ）　Ｃｌｅａｎ　Ｕｐ　Ｐａｓｓ
【００１０】
３つの符号化パスの用いられる順序を図２４に示す。図２４に示すように、先ずビットプレーン（ｎ−２）（ＭＳＢ）がＣｌｅａｎ　Ｕｐ　Ｐａｓｓによって符号化される。続いて、順次ＬＳＢ側に向かい、各ビットプレーンが、Ｓｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（以下、適宜ＳＰパスという。）、Ｍａｇｎｉｔｕｄｅ　Ｒｅｆｉｎｅｍｅｎｔ　Ｐａｓｓ（以下、適宜ＭＲパスという。）、Ｃｌｅａｎ　Ｕｐ　Ｐａｓｓ（以下、適宜ＣＵパスという。）の順序で用いられて符号化される。
【００１１】
但し、実際にはＭＳＢ側から何番目のビットプレーンで初めて１が出てくるかをヘッダに書き、オール０のビットプレーンは符号化しない。この順序で３種類の符号化パスを繰り返し用いて符号化し、任意のビットプレーンの任意の符号化パスまでで符号化を打ち切ることにより、符号量と画質のトレードオフを取る、すなわちレート制御を行うことができる。
【００１２】
ここで、係数ビットデータの走査（スキャニング）について図２５を用いて説明する。符号ブロックは、高さ４個のサンプル点毎にストライプ（ｓｔｒｉｐｅ）に分けられる。ストライプの幅は、符号ブロックの幅に等しい。スキャン順とは１個の符号ブロック内の全てのサンプル点を辿る順番であり、符号ブロック中では上のストライプから下のストライプへの順序、各ストライプ中では左の列から右の列への順序、各列中では上から下への順序でスキャニングされる。なお、各符号化パスにおいて符号ブロック中の全てのサンプル点がこのスキャン順で処理される。以下、上述した３つの符号化パスについて説明する。
【００１３】
（ａ）　Ｓｉｇｎｉｆｉｃａｎｃｅ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ
あるビットプレーンを符号化するＳＰパスでは、８近傍の少なくとも１つのサンプル点が有意（ｓｉｇｎｉｆｉｃａｎｔ）であるようなｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。その符号化した係数ビットデータが１である場合には、符号の正負が続けて算術符号化される。
【００１４】
ここでｓｉｇｎｉｆｉｃａｎｔとは、各サンプル点に対して符号化器が持つ状態である。ｓｉｇｎｉｆｉｃａｎｔの初期値は、ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔを表す「０」であり、そのサンプル点で１が符号化されたときにｓｉｇｎｉｆｉｃａｎｔを表す「１」に変化し、以降常に「１」であり続ける。したがって、ｓｉｇｎｉｆｉｃａｎｔとは、有効桁の情報を既に符号化したか否かを示すフラグとも言える。あるビットプレーンでＳＰパスが発生すれば、以降のビットプレーンではＳＰパスは発生しない。
【００１５】
（ｂ）　Ｍａｇｎｉｔｕｄｅ　Ｒｅｆｉｎｅｍｅｎｔ　Ｐａｓｓ
ビットプレーンを符号化するＭＲパスでは、ビットプレーンを符号化するＳＰパスで符号化していないｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。
【００１６】
（ｃ）　Ｃｌｅａｎ　Ｕｐ　Ｐａｓｓ
ビットプレーンを符号化するＣＵパスでは、ビットプレーンを符号化するＳＰパスで符号化していないｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。その符号化した係数ビットデータが１である場合には、符号の正負が続けて算術符号化される。
【００１７】
なお、以上の３つの符号化パスでの算術符号化では、ケースに応じてＺＣ（Ｚｅｒｏ　Ｃｏｄｉｎｇ）、ＲＬＣ（Ｒｕｎ−Ｌｅｎｇｔｈ　Ｃｏｄｉｎｇ）、ＳＣ（Ｓｉｇｎ　Ｃｏｄｉｎｇ）、ＭＲ（Ｍａｇｎｉｔｕｄｅ　Ｒｅｆｉｎｅｍｅｎｔ）が使い分けられてサンプル点のコンテキストが選択される。そして、ＭＱ符号化と呼ばれる算術符号によって選択されたコンテキストが符号化される。このＭＱ符号化は、ＪＢＩＧ２で規定された学習型の２値算術符号である。ＭＱ符号化については、例えば、文献「ＩＳＯ／ＩＥＣ　ＦＤＩＳ　１４４９２，　“Ｌｏｓｓｙ／Ｌｏｓｓｌｅｓｓ　Ｃｏｄｉｎｇ　ｏｆ　Ｂｉ−ｌｅｖｅｌ　Ｉｍａｇｅｓ”，　Ｍａｒｃｈ　２０００」等に記載されている。ＪＰＥＧ−２０００では、全ての符号化パスで合計１９種類のコンテキストがある。
【００１８】
以上のようにして、ＪＰＥＧ−２０００方式で圧縮符号化を行う画像符号化装置においては、符号ブロック毎の量子化係数をビットプレーンに分解すると共に各ビットプレーンを３つの符号化パスに分解し、符号化パス毎に係数ビットデータを生成する。そして、この符号化パス毎の係数ビットデータに対して算術符号化を施す。
【００１９】
【発明が解決しようとする課題】
ところで、上述したように、ＭＲパスは、他のビットプレーンにおけるＣＵパス処理又はＳＰパス処理によってｓｉｇｎｉｆｉｃａｎｔとなった係数ビットデータの算術符号化を行うものであり、ＣＵパスは、ＳＰパスで符号化していないｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔな係数ビットデータを算術符号化するものである。したがって、ＳＰパス処理を高速化することができれば、３つの符号化パスでの符号ブロックの符号化を高速化することができると考えられる。
【００２０】
ここで、このＳＰパスでは、上述したように、８近傍の少なくとも１つのサンプル点がｓｉｇｎｉｆｉｃａｎｔであるようなｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。そして、符号化した係数ビットデータが１である場合には、そのサンプル点の状態がｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔからｓｉｇｎｉｆｉｃａｎｔに変化する。この変化によりＳＰパス処理の対象となるサンプル点が新たに発生する場合があるため、従来ではＳＰパス処理対象サンプル点のみを選んで処理することができなかった。
【００２１】
この問題について、図２６を用いて簡単に説明する。なお、この図２６は、縦４個、横４個の計１６個の係数ビットデータから成るビットプレーンを仮定したものであり、各サンプル点の左上に付された番号は、そのサンプル点の位置を説明するための便宜的な数値である。また、図中太枠は、ｓｉｇｎｉｆｉｃａｎｔなサンプル点を示す。図２６（Ａ）に示すように、ビットプレーンの符号化を始める段階では、ｓｉｇｎｉｆｉｃａｎｔなサンプル点は１０番サンプルのみであるため、ＳＰパス処理対象となるサンプル点は、５番〜７番，９番，１１番，１３番〜１５番の８サンプルである。しかしながら、７番サンプルにおける係数ビットデータは１であるため、ＳＰパス処理により、図２６（Ｂ）に示すようにｓｉｇｎｉｆｉｃａｎｔに変化する。これにより、８番サンプル及び１２番サンプルが新たにＳＰパス処理対象となる。
【００２２】
このようなことから、ＳＰパス処理では、上述したスキャン順でＳＰパス処理対象となるサンプル点であるか否かを判定し、対象となるサンプル点であればＳＰパス処理を行い、対象となるサンプル点でなければ次のサンプル点に移るという手順を繰り返していた。このため、ビットプレーン内でＳＰパス処理対象サンプル点の数に相当する処理サイクル数でＳＰパス処理が終わらず、全サンプル点数に相当する処理サイクル数が必要になるという問題があった。
【００２３】
本発明は、このような従来の実情に鑑みて提案されたものであり、上述したＳＰパスの処理時間を短くすることで３つの符号化パスでの符号ブロックの符号化を高速化する画像符号化装置及びその方法、並びに画像符号化処理をコンピュータに実行させるプログラム及びそのプログラムが記録されたコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００２４】
【課題を解決するための手段】
上述した目的を達成するために、本発明に係る画像符号化装置は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換手段と、上記ウェーブレット変換手段によって生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成手段と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成手段と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理手段と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化手段とを備え、上記符号化パス処理手段は、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行うことにより、次の処理対象となるサンプル点を検出する。
【００２５】
また、本発明に係る画像符号化装置は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換手段と、上記ウェーブレット変換手段によって生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成手段と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成手段と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理手段と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化手段とを備え、上記符号化パス処理手段は、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行い、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点を、次の処理対象となるサンプル点として検出する。
【００２６】
このような画像符号化装置は、例えばＪＰＥＧ−２０００方式におけるＳｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（ＳＰパス）でビットプレーン内の各サンプル点を処理する際に、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意（ｓｉｇｎｉｆｉｃａｎｔ）又は非有意（ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ）を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行い、又は各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行う。そして、比較の結果、探索している領域内にＳＰパス処理対象サンプル点がある場合、そのサンプル点にジャンプしてＳＰパス処理を行い、ＳＰパス処理対象でないサンプル点における処理を省略する。
【００２７】
また、上述した目的を達成するために、本発明に係る画像符号化方法は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、上記符号化パス処理工程では、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われることにより、次の処理対象となるサンプル点が検出される。
【００２８】
また、本発明に係る画像符号化方法は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、上記符号化パス処理工程では、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点が、次の処理対象となるサンプル点として検出される。
【００２９】
このような画像符号化方法では、例えばＪＰＥＧ−２０００方式におけるＳｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（ＳＰパス）でビットプレーン内の各サンプル点を処理する際に、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意（ｓｉｇｎｉｆｉｃａｎｔ）又は非有意（ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ）を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、又は各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われる。そして、比較の結果、探索している領域内にＳＰパス処理対象サンプル点がある場合、そのサンプル点にジャンプしてＳＰパス処理が行われ、ＳＰパス処理対象でないサンプル点における処理が省略される。
【００３０】
また、本発明に係るプログラムは、上述した画像符号化処理をコンピュータに実行させるものであり、本発明に係る記録媒体は、そのようなプログラムが記録されたコンピュータ読み取り可能なものである。
【００３１】
【発明の実施の形態】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、ＪＰＥＧ−２０００方式により入力画像を圧縮符号化する画像符号化装置及びその方法に適用したものである。この画像符号化装置は、後述するように、ビットプレーンを符号化する際のＳｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓの処理時間を短くすることで、符号ブロックの符号化を高速化する。
【００３２】
本実施の形態における画像符号化装置の概略構成を図１に示す。図１に示すように、画像符号化装置１は、ＤＣレベルシフト部１０と、ウェーブレット変換部１１と、量子化部１２と、符号ブロック化部１３と、ビットプレーン符号化パス生成部１４と、算術符号化部１５と、レート制御部１７と、ヘッダ生成部１８と、パケット生成部１９とから構成されている。ここで、ビットプレーン符号化パス生成部１４と算術符号化部１５とにより、ＥＢＣＯＴ（Ｅｍｂｅｄｄｅｄ　Ｃｏｄｉｎｇ　ｗｉｔｈ
Ｏｐｔｉｍｉｚｅｄ　Ｔｒｕｎｃａｔｉｏｎ）部１６が構成される。
【００３３】
ＤＣレベルシフト部１０は、後段のウェーブレット変換部１１におけるウェーブレット変換を効率的に行い圧縮率を向上させるために、原信号のレベルシフトを行う。原理的には、ＲＧＢ信号は、正の値（符号なしの整数値）を持つため、原信号のダイナミックレンジを半分にするレベルシフトを行うことで、圧縮効率を向上させることができる。これに対して、ＹＣｂＣｒ信号におけるＣｂやＣｒといった色差信号は、正負両方の整数値を持つため、レベルシフトは行われない。
【００３４】
ウェーブレット変換部１１は、通常、低域フィルタと高域フィルタとから構成されるフィルタバンクによって実現される。なお、デジタルフィルタは、通常複数タップ長のインパルス応答（フィルタ係数）を持っているため、フィルタリングが行えるだけの入力画像を予めバッファリングしておく必要があるが、簡単のため、図１では図示を省略する。
【００３５】
ＤＣレベルシフト部１０は、フィルタリングに必要な最低限の画像信号Ｄ１０を入力し、上述のようにレベルシフトを行う。そして、ウェーブレット変換部１１は、ＤＣレベルシフト後の画像信号Ｄ１１に対して、ウェーブレット変換を行うフィルタリング処理を行い、ウェーブレット変換係数Ｄ１２を生成する。
【００３６】
このウェーブレット変換では、通常図２に示すように低域成分が繰り返し変換されるが、これは画像のエネルギの多くが低域成分に集中しているためである。ここで、図２におけるウェーブレット変換のレベル数は３であり、この結果計１０個のサブバンドが形成されている。ここで、図２においてＬ，Ｈはそれぞれ低域，高域を表し、Ｌ，Ｈの後の数字は分割レベルを表す。すなわち、例えばＬＨ−１は、水平方向が低域で垂直方向が高域である分割レベル＝１のサブバンドを表す。
【００３７】
量子化部１２は、ウェーブレット変換部１１から供給されたウェーブレット変換係数Ｄ１２に対して非可逆圧縮を施す。量子化手段としては、ウェーブレット変換係数Ｄ１２を量子化ステップサイズで除算するスカラ量子化を用いることができる。ここで、ＪＰＥＧ−２０００の規格上、上述の非可逆圧縮を行う場合で、非可逆の９×７ウェーブレット変換フィルタを用いる場合には、自動的にスカラ量子化を併用することが決められている。一方、可逆の５×３ウェーブレット変換フィルタを用いる場合には、量子化を行わず、後述のように符号化パスを切り捨てることによって、符号量制御が行われる。したがって、図１の量子化部１２が動作するのは、実際には非可逆の９×７ウェーブレット変換フィルタを用いた場合である。以下、この非可逆の９×７ウェーブレット変換フィルタを用いる場合を想定して説明を進める。
【００３８】
符号ブロック化部１３は、量子化部１２で生成された量子化係数Ｄ１３を、エントロピー符号化の処理単位である所定の大きさの符号ブロックに分割する。ここで、サブバンド中の符号ブロックの位置関係を図３に示す。通常、例えば６４×６４程度のサイズの符号ブロックが、分割後の全てのサブバンド中に生成される。したがって、最も分割レベルが小さいＨＨ−１（図２）のサブバンドの大きさが６４０×３２０であった場合には、６４×６４の符号ブロックは水平方向に１０個、垂直方向に５個、合計５０個存在することになる。符号ブロック化部１３は、符号ブロック毎の量子化係数Ｄ１４をビットプレーン符号化パス生成部１４に供給し、後段の符号化処理は、これらの符号ブロック毎に行われる。
【００３９】
ビットプレーン符号化パス生成部１４は、符号ブロック毎の量子化係数Ｄ１４に対して、以下のようにして係数ビット・モデリングを行う。ここで、本実施の形態では、特にＪＰＥＧ−２０００規格で定められたＥＢＣＯＴと呼ばれるエントロピー符号化を例に取りながら説明する。
【００４０】
ＥＢＣＯＴは、所定の大きさのブロック毎にそのブロック内の係数の統計量を測定しながら符号化する手段であり、符号ブロック単位に量子化係数をエントロピー符号化する。なお、符号ブロックの縦横のサイズは、４から２５６までの２の冪乗であり、通常は３２×３２、６４×６４、１２８×３２等の大きさが使用される。
【００４１】
ここで、符号ブロック毎の量子化係数Ｄ１４は、ｎビットの符号付き２進数で表されており、ｂｉｔ０からｂｉｔ（ｎ−２）がＬＳＢからＭＳＢまでのそれぞれのビットを表す。なお、残りの１ビットは符号である。この２進数で表された量子化係数について、係数の絶対値のビットプレーンと符号のビットプレーンとが構成される。上述した符号ブロックは、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）方向に、Ｓｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（以下、適宜ＳＰパスという。）、Ｍａｇｎｉｔｕｄｅ　Ｒｅｆｉｎｅｍｅｎｔ　Ｐａｓｓ（以下、適時ＭＲパスという。）及び　Ｃｌｅａｎ　ＵｐＰａｓｓ（以下、適宜ＣＵパスという。）という３種類の符号化パスによって、ビットプレーン毎に独立して符号化される。
【００４２】
符号化の際には、先ず最上位ビット（ＭＳＢ）のビットプレーンがＣＵパスによって符号化される。続いて、順次ＬＳＢ側に向かい、各ビットプレーンが、ＳＰパス、ＭＲパス、ＣＵパスの順序で用いられて符号化される。
【００４３】
簡単には、ＳＰパスでは、８近傍の少なくとも１つの係数が有意（ｓｉｇｎｉｆｉｃａｎｔ）であるようなｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。その符号化した係数ビットデータが１である場合には、符号の正負が続けて算術符号化される。ここでｓｉｇｎｉｆｉｃａｎｔとは、各サンプル点に対して符号化器が持つ状態である。ｓｉｇｎｉｆｉｃａｎｔの初期値は、ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔを表す０であり、そのサンプル点で１が符号化されたときにｓｉｇｎｉｆｉｃａｎｔを表す１に変化し、以降常に１であり続ける。したがって、ｓｉｇｎｉｆｉｃａｎｔとは、有効桁の情報を既に符号化したか否かを示すフラグとも言える。また、ＭＲパスでは、ＳＰパスで符号化していないｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。また、ＣＵパスでは、ＳＰパスで符号化していないｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点の係数ビットデータが算術符号化される。その符号化した係数ビットデータが１である場合には、符号の正負が続けて算術符号化される。
【００４４】
但し、実際にはＭＳＢ側から何番目のビットプレーンで初めて１が出てくるかをヘッダに書き、オール０のビットプレーンは符号化しない。この順序で３種類の符号化パスを繰り返し用いて符号化し、任意のビットプレーンの任意の符号化パスまでで符号化を打ち切ることにより、符号量と画質のトレードオフを取る、すなわちレート制御を行うことができる。
【００４５】
なお、以上の３つの符号化パスでの算術符号化では、ケースに応じてＺＣ（Ｚｅｒｏ　Ｃｏｄｉｎｇ）、ＲＬＣ（Ｒｕｎ−Ｌｅｎｇｔｈ　Ｃｏｄｉｎｇ）、ＳＣ（Ｓｉｇｎ　Ｃｏｄｉｎｇ）、ＭＲ（Ｍａｇｎｉｔｕｄｅ　Ｒｅｆｉｎｅｍｅｎｔ）が使い分けられて係数のコンテキストが選択される。そして、ＭＱ符号化と呼ばれる算術符号によって選択されたコンテキストが符号化される。このＭＱ符号化は、ＪＢＩＧ２で規定された学習型の２値算術符号である。ＪＰＥＧ−２０００では、全ての符号化パスで合計１９種類のコンテキストがある。
【００４６】
以上のようにしてビットプレーン符号化パス生成部１４は、符号ブロック毎の量子化係数Ｄ１４をビットプレーンに分解すると共に各ビットプレーンを３つの符号化パスに分解し、符号化パス毎に量子化係数Ｄ１５を生成する。そして、算術符号化部１５は、この符号化パス毎の量子化係数Ｄ１５に対して算術符号化を施す。
【００４７】
レート制御部１７は、少なくとも一部の符号化パスの処理を行った後で、算術符号化部１５から供給された算術符号Ｄ１６の符号量をカウントし、目標の符号量に達した時点で、又は達する直前に、それより後の算術符号Ｄ１６を切り捨てる。このように、符号量をオーバーする直前で切り捨てることにより、確実に目標の符号量に抑えることができる。レート制御部１７は、この符号量制御完了後の算術符号Ｄ１７を、ヘッダ生成部１８及びパケット生成部１９に供給する。
【００４８】
ヘッダ生成部１８は、レート制御部１７から供給された符号量制御完了後の算術符号Ｄ１７に基づいて、符号ブロック内での付加情報、例えば符号ブロック内の符号化パスの個数や圧縮コードストリームのデータ長等をヘッダＤ１８として生成し、このヘッダＤ１８をパケット生成部１９に供給する。
【００４９】
パケット生成部１９は、符号量制御完了後の算術符号Ｄ１７とヘッダＤ１８とを合わせてパケットＤ１９を生成し、符号化コードストリームとして出力する。この際、パケット生成部１９は、図４に示すように同一解像度レベルから個々のパケットを生成する。なお、図４から分かるように、最低域であるパケット−１は、ＬＬ成分のみを含み、それ以外のパケット−２乃至パケット−４は、ＬＨ成分，ＨＬ成分及びＨＨ成分を含む。
【００５０】
以上のように、本実施の形態における画像符号化装置１は、ウェーブレット変換及びエントロピー符号化を用いて入力画像を高効率に圧縮符号化し、パケット化して符号化コードストリームとして出力することができる。
【００５１】
ところで、従来、上述した３つの符号化パスでの処理を行う際の係数ビットデータのスキャニングは、各ビットプレーンで上から下へ４個のサンプル点を処理した後、右隣上のサンプル点に移り、右隣のサンプル点がない場合には下側左のサンプル点に移る、という順序で行われる。
【００５２】
特に、ＳＰパス処理を行う際には、符号化した係数ビットデータが１である場合に、そのサンプル点の状態がｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔからｓｉｇｎｉｆｉｃａｎｔに変化し、この変化によりＳＰパス処理の対象となるサンプル点が新たに発生する場合があるため、ＳＰパス処理対象サンプル点のみを選んで処理することができなかった。
【００５３】
このため、ビットプレーン内で、ＳＰパス処理対象サンプル点の数に相当する処理サイクル数でＳＰパス処理が終わらず、全サンプル数に相当する処理サイクル数が必要になるという問題があった。
【００５４】
そこで、本実施の形態における画像符号化装置１は、以下に説明する２通りの手法により、ＳＰパス処理を高速化している。
【００５５】
先ず第１の手法の処理概念について説明する。この第１の手法では、符号ブロック内の各サンプル点のｓｉｇｎｉｆｉｃａｎｔ（Ｓ）又はｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）の状態を表すＳ／Ｎビットメモリを用意する。符号ブロックサイズが６４×６４である場合、Ｓ／Ｎビットメモリのサイズは、６４×６４×１ビットとなる。このＳ／Ｎビットメモリでは、そのアドレスにおけるサンプル点がｓｉｇｎｉｆｉｃａｎｔ（Ｓ）のとき「１」が立ち、ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）のとき「０」が立つとする。一方、係数ビットデータは、係数ビットメモリに格納される。符号ブロックサイズが６４×６４、ビットプレーン数がＮである場合、係数ビットメモリのサイズは、６４×６４×Ｎビットとなる。
【００５６】
上述したように、ビットプレーン符号化パス生成部１４における係数ビット・モデリングは、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）の方向に、ビットプレーン毎に独立に３つの符号化パスで処理を行う。この際、予めＳ／Ｎビットメモリの全アドレスの値を「０」、すなわちｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）に初期化しておく。
【００５７】
係数ビットデータが０しかないビットプレーンＺは、０ビットプレーンとして、３つの符号化パスの処理は行わない。また、何れかのサンプル点における係数ビットデータが１である最初のビットプレーンＺ１は、ＣＵパスで処理される。このとき、係数ビットデータが１であるサンプル点はｓｉｇｎｉｆｉｃａｎｔ（Ｓ）となり、Ｓ／Ｎビットメモリのそのサンプル点を示すアドレスに「１」が立つ。続いて、１ビット下位のビットプレーンＺ２に移り、ＳＰパス、ＭＲパス、ＣＵパスの順に３つの符号化パスで処理し、順次ＬＳＢ側のビットプレーンに移って同様の処理を繰り返す。
【００５８】
ここで、第１の手法では、ＳＰパス処理を高速化するために、複数のＳ／Ｎマッチングパターンを用意する。このＳ／Ｎマッチングパターンとは、あるサンプル点から次のＳＰパス処理対象サンプル点に移ることができる場合における、関連するサンプル点のｓｉｇｎｉｆｉｃａｎｔ（Ｓ）又はｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）のパターンを示したものである。
【００５９】
このＳ／Ｎマッチングパターンについて、図５、図６を用いて簡単に説明する。なお、この図５、図６において、Ｓ及びｓはｓｉｇｎｉｆｉｃａｎｔなサンプル点を示し、ｓは他のｓと共にＯＲを形成する。すなわち、複数のｓのうち、少なくとも１つのｓがｓｉｇｎｉｆｉｃａｎｔであればよい。また、Ｎはｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点を示し、Ｘはｓｉｇｎｉｆｉｃａｎｔであるかｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔであるかを考慮しないサンプル点を示す。さらに、各サンプル点の左上に付された番号は、そのサンプル点の位置を説明するための便宜的な数値である。
【００６０】
図５は、１番サンプルから３番サンプルへと移る場合のＳ／Ｎマッチングパターンを示したものである。この図５に示す２通りのパターンに該当する場合にのみ、１番サンプルから３番サンプルへと移ることができる。一方、図６は、１番サンプルから８番サンプルへと移る場合のＳ／Ｎマッチングパターンを示したものである。この図６に示す２通りのパターンに該当する場合にのみ、１番サンプルから８番サンプルへと移ることができる。
【００６１】
ここで、各Ｓ／Ｎマッチングパターンには、それぞれに応じてジャンプアドレス値が設定される。上述の図５に示したＳ／Ｎマッチングパターンでは、１番サンプルから３番サンプルに移るため、ジャンプアドレス値は２となり、図６に示したＳ／Ｎマッチングパターンでは、１番サンプルから８番サンプルに移るため、ジャンプアドレス値は７となる。
【００６２】
つまり、任意のサンプル点から次のＳＰパス処理対象サンプル点に移る場合に該当するＳ／Ｎマッチングパターンを予め設定しておけば、現在のＳ／Ｎマッチングパターンから得られたジャンプアドレス値により、ジャンプ先のサンプル点を知ることができる。
【００６３】
なお、この第１の手法では、従来のスキャン順で次のサンプル点に移る場合のＳ／Ｎマッチングパターンも用意しておくものとする。
【００６４】
ここで、用意すべきＳ／Ｎマッチングパターン数は、一度に探索するエリアのサイズに応じて変わる。以下では、一例として、水平３サンプル×垂直４サンプルのエリアにジャンプ先となるＳＰパス処理対象サンプル点があるか否かを一度に探索するものとして説明する。この場合、参照するサンプル点は、３×４エリアの上下左右に１サンプルずつ増えて、水平５サンプル×垂直６サンプルのエリアとなる。なお、符号ブロック外を参照することになる場合には、その位置にｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点が存在するものとして処理を行う。
【００６５】
上述したように、ビットプレーンＺ２で、最初のＳＰパス処理が行われる。先ず、図７（Ａ）に示すような水平３サンプル×垂直４サンプルのエリアＡＲ１に対して、ＳＰパス処理対象サンプル点があるか否かを判別するため、Ｓ／ＮビットメモリからこのエリアＡＲ１及びその周囲に相当する水平５サンプル×垂直６サンプルのＳ／Ｎビットデータがロードされる。
【００６６】
ここで、Ｓ／Ｎマッチングパターンはそれぞれ排他的であり、エリアＡＲ１にＳＰパス処理対象サンプル点があった場合には、何れかのＳ／Ｎマッチングパターンが一致し、そのＳ／Ｎマッチングパターンに応じたジャンプアドレス値が出力される。このジャンプアドレス値を出力するためのテーブルを図８に示す。図７（Ａ）の例では、２番サンプルＡから１１番サンプルＢに移るため、ジャンプアドレス値は９となる。そして、アドレスジャンプしたサンプル点ＢがＳＰパスで処理され、続いて、アドレスジャンプしたサンプル点Ｂが左端の列となる新たなエリアＡＲ２を設定し、上記手順を繰り返す。なお、アドレスジャンプしたサンプル点Ｂを左端の列とする例に限定されず、このサンプル点Ｂを起点とするエリアを設定するようにしても構わない。
【００６７】
一方、エリアＡＲ１にＳＰパス処理対象サンプル点がなかった場合には、何れのＳ／Ｎマッチングパターンも不一致となる。この場合には、図７（Ｂ）に示すようなエリアＡＲ１より先のエリアＡＲ３に対して再度ＳＰパス処理対象サンプル点があるか否かを判別するため、Ｓ／ＮビットメモリからエリアＡＲ３及びその周囲に相当する水平５サンプル×垂直６サンプルのＳ／Ｎビットデータがロードされる。
【００６８】
以上説明した第１の手法を行う場合におけるビットプレーン符号化パス生成部１４のＳＰパス処理に関係する部分の概略構成を図９に示す。図９に示すように、ビットプレーン符号化パス生成部１４は、Ｓ／Ｎビットメモリ１００と、係数ビットメモリ１０１と、エリア設定部１０２と、１番乃至１２番サンプル用のＡＮＤ・ＯＲ回路１０３１〜１０３１２と、ジャンプアドレス値テーブル１０４と、決定用ＡＮＤ・ＯＲ回路１０５と、係数モデリング回路１０６と、ＤＦＦ（Ｄフリップフロップ）１０７，１０８とを少なくとも有する。
【００６９】
符号ブロックサイズが６４×６４である場合、Ｓ／Ｎビットメモリ１００のサイズは、図１０に示すように、６４×６４×１ビットとなる。このＳ／Ｎビットメモリ１００には、そのアドレスにおけるサンプル点がｓｉｇｎｉｆｉｃａｎｔ（Ｓ）のとき「１」が立ち、ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）のとき「０」が立つ。
【００７０】
一方、符号ブロックサイズが６４×６４、ビットプレーン数がＮである場合、係数ビットメモリ１０１のサイズは、図１１に示すように、６４×６４×Ｎビットとなる。この係数ビットメモリ１０１には、そのサンプル点における係数ビットデータが格納される。
【００７１】
以下では、図示しないサンプル点Ｙから図１０（Ａ）、図１１（Ａ）の２番サンプルにジャンプすることが決定された状態からのＳＰパス処理について、図９及び図１２のタイミングチャートを参照しながら詳細に説明する。なお、この例では、水平３サンプル×垂直４サンプルのエリアにジャンプ先となるＳＰパス処理対象サンプル点があるか否かを一度に探索するものとする。
【００７２】
決定用ＡＮＤ・ＯＲ回路１０５は、２番サンプル用のジャンプアドレス値を係数モデリング回路１０６及びＤＦＦ１０７に供給する。
【００７３】
係数モデリング回路１０６は、２番サンプル用のジャンプアドレス値が供給されると、２番サンプルをＳＰパスで処理し、係数ビットデータＸとコンテキストＣＸを算出する。ここで、係数モデリング回路１０６は、２番サンプルの係数ビットデータＸが１である場合には、ＤＦＦ１０８において処理クロックとの同期を取った後、Ｓ／Ｎビット更新フラグとして「１」をＳ／Ｎビットメモリ１００に供給し、Ｓ／Ｎビットメモリ１００は、このフラグに応じて、２番サンプルに対応するアドレスのＳ／Ｎビットを、ｓｉｇｎｉｆｉｃａｎｔ（Ｓ）を示す「１」に更新する。
【００７４】
一方、ＤＦＦ１０７は、決定用ＡＮＤ・ＯＲ回路１０５から供給された２番サンプル用のジャンプアドレス値について、処理クロックとの同期を取り、このジャンプアドレス値をエリア設定部１０２に供給する。
【００７５】
エリア設定部１０２は、ＤＦＦ１０７から供給されたジャンプアドレス値に基づいて、Ｓ／Ｎビットメモリ１００において２番サンプルを左から２個目に取る水平方向５サンプル×垂直方向６サンプルのエリアＡＲ４（図１０（Ａ））を設定し、係数ビットメモリ１０１において２番サンプルを左端に取る水平方向３サンプル×垂直方向４サンプルのエリアＡＲ５（図１１（Ａ））を設定する。
【００７６】
そして、Ｓ／Ｎビットメモリ１００は、設定されたエリアＡＲ４のＳ／ＮビットデータをＡＮＤ・ＯＲ回路１０３１〜１０３１２及び係数モデリング回路１０６に供給する。また、係数ビットメモリ１０１は、設定されたエリアＡＲ５の係数ビットデータを係数モデリング回路１０６に供給する。
【００７７】
上述したＤＦＦ１０７は、２番サンプル用のジャンプアドレス値の同期を取り、現サンプル点位置情報として、ＡＮＤ・ＯＲ回路１０３１〜１０３１２及びジャンプアドレス値テーブル１０４に供給する。
【００７８】
ＡＮＤ・ＯＲ回路１０３３〜１０３１２は、現サンプル点位置情報に応じて、現サンプル点位置から、それぞれのサンプル点位置にジャンプ可能か否かを判別する。
【００７９】
例えば、１１番サンプル用のＡＮＤ・ＯＲ回路１０３１１は、第１サンプルから第１１サンプルにジャンプ可能か否かを判別するためのＡＮＤ・ＯＲ回路（１→１１用）を始めとして、第１０サンプルから第１１サンプルにジャンプするか否かを判別するためのＡＮＤ・ＯＲ回路（１０→１１用）まで、１０種類のＡＮＤ・ＯＲ回路を有している。それぞれのＡＮＤ・ＯＲ回路は、現在のＳ／Ｎパターンが図１３に示すＳ／Ｎマッチングパターンと一致するか否かを判別するため、例えば同図に示すようなパターンマッチング論理式を計算する。ここで、パターンマッチング論理式において、「・」はＡＮＤを示し、「＋」はＯＲを示し、「！」はＮＯＴを示す。現サンプル点位置は第２サンプルであるため、ＡＮＤ・ＯＲ回路（２→１１用）のみが使用され、図１３に示す２通りのＳ／Ｎマッチングパターンと一致するか否かが判別される。
【００８０】
このとき、３番乃至１２番サンプルにＳＰパス処理対象サンプル点があれば、ＡＮＤ・ＯＲ回路１０３３〜１０３１２の何れかの出力が「１」になる。一方、３番乃至１２番サンプルにＳＰパス処理対象サンプル点がなければ、ＡＮＤ・ＯＲ回路１０３３〜１０３１２のどの出力も「０」になる。
【００８１】
図９に戻って、決定用ＡＮＤ・ＯＲ回路１０５において、ＡＮＤゲート１５０１〜１５０１２の一方の端子には、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の各出力が与えられる。また、ＡＮＤゲート１５０１〜１５０１２の他方の端子には、現サンプル点位置情報に基づいてジャンプアドレス値テーブル１０４が設定した１番乃至１２番サンプルへのジャンプアドレス値が与えられる。したがって、３番乃至１２番サンプルにＳＰパス処理対象サンプル点があり、ＡＮＤ・ＯＲ回路１０３３〜１０３１２の何れかの出力が「１」になった場合には、そのＡＮＤ・ＯＲ回路からの出力がＯＲゲート１５２に与えられ、ジャンプアドレス値として上述の係数モデリング回路１０６に供給される。
【００８２】
一方、決定用ＡＮＤ・ＯＲ回路１０５において、ＡＮＤゲート１５１の一方の端子には、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の全出力が反転して与えられる。また、ＡＮＤゲート１５１の他方の端子には、エリアをジャンプするエリアジャンプフラグが与えられる。したがって、３番乃至１２番サンプルにＳＰパス処理対象サンプル点がなく、ＡＮＤ・ＯＲ回路１０３３〜１０３１２の出力が全て「０」の場合には、ＡＮＤゲート１５１が有効となるため、そのエリアジャンプフラグがＯＲゲート１５２に与えられ、ジャンプアドレス値として上述の係数モデリング回路１０６に供給される。
【００８３】
ここで、次のＳＰパス処理対象サンプル点として１１番サンプルが見つかったとして説明を進める。この場合、ＡＮＤ・ＯＲ回路１０３１１の出力が「１」となり、ＡＮＤゲート１５０１１が有効となるため、決定用ＡＮＤ・ＯＲ回路１０５は、ＯＲゲート１５２を介して、１１番サンプル用のジャンプアドレス値を係数モデリング回路１０６及びＤＦＦ１０７に供給する。
【００８４】
係数モデリング回路１０６は、１１番サンプル用のジャンプアドレス値が供給されると、１１番サンプルをＳＰパスで処理し、係数ビットデータＸとコンテキストＣＸを算出する。ここで、係数モデリング回路１０６は、１１番サンプルの係数ビットデータＸが１である場合には、Ｓ／Ｎビット更新フラグとして「１」をＤＦＦ１０８を介してＳ／Ｎビットメモリ１００に供給し、Ｓ／Ｎビットメモリ１００は、このフラグに応じて、１１番サンプルに対応するアドレスのＳ／Ｎビットを、ｓｉｇｎｉｆｉｃａｎｔ（Ｓ）を示す「１」に更新する。
【００８５】
一方、ＤＦＦ１０７は、決定用ＡＮＤ・ＯＲ回路１０５から供給された１１番サンプル用のジャンプアドレス値の同期を取り、このジャンプアドレス値をエリア設定部１０２に供給する。
【００８６】
エリア設定部１０２は、ＤＦＦ１０７から供給されたジャンプアドレス値に基づいて、Ｓ／Ｎビットメモリ１００において１１番サンプルを左から２個目に取る水平方向５サンプル×垂直方向６サンプルのエリアＡＲ６（図１０（Ａ））を設定し、係数ビットメモリ１０１において１１番サンプルを左端に取る水平方向３サンプル×垂直方向４サンプルのエリアＡＲ７（図１１（Ａ））を設定する。この結果、図１０（Ｂ）、図１１（Ｂ）に示すように、１１番サンプルのサンプル番号は、３番に変更される。
【００８７】
そして、Ｓ／Ｎビットメモリ１００は、設定されたエリアのＳ／ＮビットデータをＡＮＤ・ＯＲ回路１０３１〜１０３１２及び係数モデリング回路１０６に供給する。また、係数ビットメモリ１０１は、設定されたエリアＡＲ７の係数ビットデータを係数モデリング回路１０６に供給する。
【００８８】
上述したＤＦＦ１０７は、１１番サンプル用のジャンプアドレス値の同期を取り、現サンプル点位置情報として、ＡＮＤ・ＯＲ回路１０３１〜１０３１２及びジャンプアドレス値テーブル１０４に供給する。
【００８９】
このとき、４番乃至１２番サンプルにＳＰパス処理対象サンプル点があれば、ＡＮＤ・ＯＲ回路１０３４〜１０３１２の何れかの出力が「１」になる。一方、４番乃至１２番サンプルにＳＰパス処理対象サンプル点がなければ、ＡＮＤ・ＯＲ回路１０３４〜１０３１２のどの出力も「０」になる。
【００９０】
決定用ＡＮＤ・ＯＲ回路１０５において、ＡＮＤゲート１５０１〜１５０１２の一方の端子には、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の各出力が与えられる。また、ＡＮＤゲート１５０１〜１５０１２の他方の端子には、現サンプル点位置情報に基づいてジャンプアドレス値テーブル１０４が設定した１番乃至１２番サンプルへのジャンプアドレス値が与えられる。したがって、４番乃至１２番サンプルにＳＰパス処理対象サンプル点があり、ＡＮＤ・ＯＲ回路１０３４〜１０３１２の何れかの出力が「１」になった場合には、そのＡＮＤ・ＯＲ回路からの出力がＯＲゲート１５２に与えられ、ジャンプアドレス値として上述の係数モデリング回路１０６に供給される。
【００９１】
一方、決定用ＡＮＤ・ＯＲ回路１０５において、ＡＮＤゲート１５１の一方の端子には、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の全出力が反転して与えられる。また、ＡＮＤゲート１５１の他方の端子には、エリアをジャンプするエリアジャンプフラグが与えられる。したがって、４番乃至１２番サンプルにＳＰパス処理対象サンプル点がなく、ＡＮＤ・ＯＲ回路１０３４〜１０３１２の出力が全て「０」の場合には、これら全出力が反転されてＡＮＤゲート１５１の一方の端子に与えられ、そのエリアジャンプフラグがＯＲゲート１５２に与えられ、ジャンプアドレス値として上述の係数モデリング回路１０６に供給される。これにより、エリア設定部１０２は、Ｓ／Ｎビットメモリ１００において新たに水平方向５サンプル×垂直方向６サンプルのエリアＡＲ８（図１０（Ｂ））を設定し、係数ビットメモリ１０１において新たに水平方向３サンプル×垂直方向４サンプルのエリアＡＲ９（図１１（Ｂ））を設定する。
【００９２】
なお、このようにエリアジャンプを行った際には、現サンプル点位置は更新されない。各ＡＮＤ・ＯＲ回路１０３１〜１０３１２は、当該エリアにおける最初のＳＰパス処理対象サンプル点を見つけるために、それぞれのサンプル点位置が最初のＳＰパス処理対象サンプル点か否かを判別する。
【００９３】
例えば、１１番サンプル用のＡＮＤ・ＯＲ回路１０３１１は、現在のＳ／Ｎパターンが図１４に示すＳ／Ｎマッチングパターンと一致するか否かを判別するため、例えば同図に示すようなパターンマッチング論理式を計算する。
【００９４】
以上説明したように、第１の手法によれば、探索エリア内にＳＰパス処理対象サンプル点がある場合、そのサンプル点にジャンプしてＳＰパス処理を行い、ＳＰパス処理対象でないサンプル点における処理を省略することができるため、スキャン順で処理した場合と比較して、処理サイクル数を少なく、或いは処理時間を短くすることができる。また、処理クロック周波数を低減することもでき、低消費電力なハードウェアが実現可能である。
【００９５】
続いて第２の手法の処理概念について説明する。この第２の手法においても、符号ブロック内の各サンプル点のｓｉｇｎｉｆｉｃａｎｔ（Ｓ）又はｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）の状態を表すＳ／Ｎビットメモリを用意する。一方、係数ビットデータは、係数ビットメモリに格納される。
【００９６】
上述したように、ビットプレーン符号化パス生成部１４における係数ビット・モデリングは、最上位ビット（ＭＳＢ）から最下位ビット（ＬＳＢ）の方向に、ビットプレーン毎に独立に３つの符号化パスで処理を行う。この際、予めＳ／Ｎビットメモリの全アドレスの値を「０」、すなわちｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）に初期化しておく。
【００９７】
係数ビットデータが０しかないビットプレーンＺは、０ビットプレーンとして、３つの符号化パスの処理は行わない。また、何れかのサンプル点における係数ビットデータが１である最初のビットプレーンＺ１は、ＣＵパスで処理される。このとき、係数ビットデータが１であるサンプル点はｓｉｇｎｉｆｉｃａｎｔ（Ｓ）となり、Ｓ／Ｎビットメモリのそのサンプル点を示すアドレスに「１」が立つ。続いて、１ビット下位のビットプレーンＺ２に移り、ＳＰパス、ＭＲパス、ＣＵパスの順に３つの符号化パスで処理し、順次ＬＳＢ側のビットプレーンに移って同様の処理を繰り返す。
【００９８】
ここで、第２の手法では、ＳＰパス処理を高速化するために、Ｓ／Ｎマッチングパターンを探索するエリアのサンプル数分用意する。各サンプル点のＳ／Ｎマッチングパターンには、それぞれに応じたジャンプアドレス値が設定される。このＳ／Ｎマッチングパターンとは、上述した第１の手法とは異なり、任意のサンプル点がＳＰパス処理対象サンプル点であるか否かを判断するための、当該サンプル点及びその周囲におけるｓｉｇｎｉｆｉｃａｎｔ（Ｓ）又はｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）のパターンを示したものである。具体的には、図１５に示すように、８近傍の少なくとも１つのサンプル点がｓｉｇｎｉｆｉｃａｎｔであるようなｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点が、ＳＰパス処理対象サンプル点とされる。なお、図１５において、ｓはｓｉｇｎｉｆｉｃａｎｔなサンプル点を示し、他のｓと共にＯＲを形成する。また、Ｎはｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点を示す。
【００９９】
第２の手法では、各サンプル点についてこのＳ／Ｎマッチングパターンとの一致、不一致を調べ、ＳＰパス処理対象サンプル点であるか否かを判別する。そして、プライオリティ・エンコーダにおいて、一致したサンプル点のうち現サンプル点にスキャン順で最も近いサンプル点が選択され、このサンプル点が次のＳＰパス処理対象サンプル点とされる。
【０１００】
ここで、用意すべきＳ／Ｎマッチングパターン数は、一度に探索するエリアのサイズに応じて変わる。以下では、一例として、水平３サンプル×垂直４サンプルのエリアにジャンプ先となるＳＰパス処理対象サンプル点があるか否かを一度に探索するものとして説明する。この場合、参照するサンプル点は、３×４エリアの上下左右に１サンプルずつ増えて、水平５サンプル×垂直６サンプルのエリアとなる。なお、符号ブロック外を参照することになる場合には、その位置にｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔなサンプル点が存在するものとして処理を行う。
【０１０１】
上述したように、ビットプレーンＺ２で、最初のＳＰパス処理が行われる。先ず、図１６（Ａ）に示すような水平３サンプル×垂直４サンプルのエリアＡＲ１０に対して、ＳＰパス処理対象サンプル点があるか否かを判別するため、Ｓ／ＮビットメモリからこのエリアＡＲ１０及びその周囲に相当する水平５サンプル×垂直６サンプルのＳ／Ｎビットデータがロードされる。
【０１０２】
そして、エリアＡＲ１０の各サンプル点について上述したＳ／Ｎマッチングパターンとの一致、不一致を調べ、ＳＰパス処理対象サンプル点であるか否かを判別する。エリアＡＲ１０にＳＰパス処理対象サンプル点があった場合には、プライオリティ・エンコーダにおいて、現サンプル点にスキャン順で最も近いサンプル点のアドレスがジャンプアドレス値として出力される。
【０１０３】
なお、現サンプル点にスキャン順で最も近いサンプル点のアドレスをジャンプアドレス値として出力する例に限定されず、このアドレスを次サンプル点位置として、図８に示したジャンプアドレス値テーブル１０４を参照して得られるジャンプアドレス値を出力するようにしても構わない。
【０１０４】
現サンプル点位置が１番サンプル、５番サンプルである場合のＳ／Ｎマッチングパターンとの一致点位置、不一致点位置とプライオリティ・エンコーダの出力との関係をそれぞれ図１７（Ａ）、（Ｂ）に示す。なお、図１７において、「○」は一致点位置を示し、「×」は不一致点位置を示す。また、「−」は一致／不一致を考慮しないサンプル点を示す。また、ＰＥ　ｏｕｔは、プライオリティ・エンコーダから出力されるジャンプアドレス値である。
【０１０５】
図１６（Ａ）の例では、現サンプル点位置が２番サンプルＡであるときに、５番サンプルＢ、１１番サンプルＣがＳ／Ｎマッチングパターンと一致しているため、プライオリティ・エンコーダから出力されるジャンプアドレス値は５となる。そして、アドレスジャンプしたサンプル点ＢがＳＰパスで処理され、続いて、アドレスジャンプしたサンプル点Ｂが左端の列となる新たなエリアＡＲ１１を設定し、上記手順を繰り返す。なお、アドレスジャンプしたサンプル点Ｂを左端の列とする例に限定されず、このサンプル点Ｂを起点とするエリアを設定するようにしても構わない。
【０１０６】
一方、エリアＡＲ１０にＳＰパス処理対象サンプル点がなかった場合には、何れのＳ／Ｎマッチングパターンも不一致となる。この場合には、図１６（Ｂ）に示すようなエリアＡＲ１０より先のエリアＡＲ１２に対して再度ＳＰパス処理対象サンプル点があるか否かを判別するため、Ｓ／ＮビットメモリからエリアＡＲ１２及びその周囲に相当する水平５サンプル×垂直６サンプルのＳ／Ｎビットデータがロードされる。
【０１０７】
以上説明した第２の手法を行う場合におけるビットプレーン符号化パス生成部１４のＳＰパス処理に関係する部分の概略構成を図１８に示す。図１８に示すように、ビットプレーン符号化パス生成部１４は、Ｓ／Ｎビットメモリ１００と、係数ビットメモリ１０１と、エリア設定部１０２と、１番乃至１２番サンプル用のＡＮＤ・ＯＲ回路１０３１〜１０３１２と、ジャンプアドレス値テーブル１０４と、係数モデリング回路１０６と、ＤＦＦ１０７，１０８と、プライオリティ・エンコーダ１１０とを少なくとも有する。
【０１０８】
符号ブロックサイズが６４×６４である場合、Ｓ／Ｎビットメモリ１００のサイズは、図１９に示すように、６４×６４×１ビットとなる。このＳ／Ｎビットメモリ１００には、そのアドレスにおけるサンプル点がｓｉｇｎｉｆｉｃａｎｔ（Ｓ）のとき「１」が立ち、ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ（Ｎ）のとき「０」が立つ。
【０１０９】
一方、符号ブロックサイズが６４×６４、ビットプレーン数がＮである場合、係数ビットメモリ１０１のサイズは、図２０に示すように、６４×６４×Ｎビットとなる。この係数ビットメモリ１０１には、そのサンプル点における係数ビットデータが格納される。
【０１１０】
以下では、図示しないサンプル点Ｙから図１９（Ａ）、図２０（Ａ）の２番サンプルにジャンプすることが決定された状態からのＳＰパス処理について、図１８及び図２１のタイミングチャートを参照しながら詳細に説明する。なお、この例では、水平３サンプル×垂直４サンプルのエリアにジャンプ先となるＳＰパス処理対象サンプル点があるか否かを一度に探索するものとする。
【０１１１】
プライオリティ・エンコーダ１１０は、２番サンプル用のジャンプアドレス値を係数モデリング回路１０６及びＤＦＦ１０７に供給する。
【０１１２】
係数モデリング回路１０６は、２番サンプル用のジャンプアドレス値が供給されると、２番サンプルをＳＰパスで処理し、係数ビットデータＸとコンテキストＣＸを算出する。ここで、係数モデリング回路１０６は、２番サンプルの係数ビットデータＸが１である場合には、ＤＦＦ１０８において処理クロックとの同期を取った後、Ｓ／Ｎビット更新フラグとして「１」をＳ／Ｎビットメモリ１００に供給し、Ｓ／Ｎビットメモリ１００は、このフラグに応じて、２番サンプルに対応するアドレスのＳ／Ｎビットを、ｓｉｇｎｉｆｉｃａｎｔ（Ｓ）を示す「１」に更新する。
【０１１３】
一方、ＤＦＦ１０７は、プライオリティ・エンコーダ１１０から供給された２番サンプル用のジャンプアドレス値について、処理クロックとの同期を取り、このジャンプアドレス値をエリア設定部１０２に供給する。
【０１１４】
エリア設定部１０２は、ＤＦＦ１０７から供給されたジャンプアドレス値に基づいて、Ｓ／Ｎビットメモリ１００において２番サンプルを左から２個目に取る水平方向５サンプル×垂直方向６サンプルのエリアＡＲ１３（図１９（Ａ））を設定し、係数ビットメモリ１０１において２番サンプルを左端に取る水平方向３サンプル×垂直方向４サンプルのエリアＡＲ１４（図２０（Ａ））を設定する。
【０１１５】
そして、Ｓ／Ｎビットメモリ１００は、設定されたエリアＡＲ１３のＳ／ＮビットデータをＡＮＤ・ＯＲ回路１０３１〜１０３１２及び係数モデリング回路１０６に供給する。また、係数ビットメモリ１０１は、設定されたエリアＡＲ１４の係数ビットデータを係数モデリング回路１０６に供給する。
【０１１６】
上述したＤＦＦ１０７は、２番サンプル用のジャンプアドレス値の同期を取り、現サンプル点位置情報として、プライオリティ・エンコーダ１１０に供給する。
【０１１７】
ＡＮＤ・ＯＲ回路１０３３〜１０３１２は、各サンプル点についてこのＳ／Ｎマッチングパターンとの一致、不一致を調べ、ＳＰパス処理対象サンプル点であるか否かを判別する。例えば、第１、第４、第７、第１１サンプル用のＡＮＤ・ＯＲ回路は、現在のＳ／Ｎパターンが図２２に示すＳ／Ｎマッチングパターンと一致するか否かを判別するため、例えば同図に示すようなパターンマッチング論理式を計算する。ここで、パターンマッチング論理式において、「・」はＡＮＤを示し、「＋」はＯＲを示し、「！」はＮＯＴを示す。
【０１１８】
このとき、１番乃至１２番サンプルにＳＰパス処理対象サンプル点があれば、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の何れかの出力が「１」になる。一方、１番乃至１２番サンプルにＳＰパス処理対象サンプル点がなければ、ＡＮＤ・ＯＲ回路１０３１〜１０３１２のどの出力も「０」になる。
【０１１９】
図１８に戻って、プライオリティ・エンコーダ１１０には、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の各出力の他、現サンプル点位置情報が与えられる。そして、３番乃至１２番サンプルにＳＰパス処理対象サンプル点があり、ＡＮＤ・ＯＲ回路１０３３〜１０３１２のうち１以上の出力が「１」になった場合には、そのうち現サンプル点にスキャン順で最も近いサンプル点のアドレスがジャンプアドレス値として上述の係数モデリング回路１０６に供給される。
【０１２０】
一方、プライオリティ・エンコーダ１１０には、エリアをジャンプするエリアジャンプフラグも与えられる。そして、３番乃至１２番サンプルにＳＰパス処理対象サンプル点がなくＡＮＤ・ＯＲ回路１０３３〜１０３１２の出力が全て「０」である場合、或いはＡＮＤ・ＯＲ回路１０３１の出力のみが「１」である場合には、そのエリアジャンプフラグがジャンプアドレス値として上述の係数モデリング回路１０６に供給される。
【０１２１】
ここで、次のＳＰパス処理対象サンプル点として１１番サンプルのみが見つかったとして説明を進める。この場合、ＡＮＤ・ＯＲ回路１０３１１の出力が「１」となり、プライオリティ・エンコーダ１１０は、１１番サンプル用のジャンプアドレス値を係数モデリング回路１０６及びＤＦＦ１０７に供給する。
【０１２２】
係数モデリング回路１０６は、１１番サンプル用のジャンプアドレス値が供給されると、１１番サンプルをＳＰパスで処理し、係数ビットデータＸとコンテキストＣＸを算出する。ここで、係数モデリング回路１０６は、１１番サンプルの係数ビットデータＸが１である場合には、Ｓ／Ｎビット更新フラグとして「１」をＤＦＦ１０８を介してＳ／Ｎビットメモリ１００に供給し、Ｓ／Ｎビットメモリ１００は、このフラグに応じて、１１番サンプルに対応するアドレスのＳ／Ｎビットを、ｓｉｇｎｉｆｉｃａｎｔ（Ｓ）を示す「１」に更新する。
【０１２３】
一方、ＤＦＦ１０７は、決定用ＡＮＤ・ＯＲ回路１０５から供給された１１番サンプル用のジャンプアドレス値の同期を取り、このジャンプアドレス値をエリア設定部１０２に供給する。
【０１２４】
エリア設定部１０２は、ＤＦＦ１０７から供給されたジャンプアドレス値に基づいて、Ｓ／Ｎビットメモリ１００において１１番サンプルを左から２個目に取る水平方向５サンプル×垂直方向６サンプルのエリアＡＲ１５（図１９（Ａ））を設定し、係数ビットメモリ１０１において１１番サンプルを左端に取る水平方向３サンプル×垂直方向４サンプルのエリアＡＲ１６（図２０（Ａ））を設定する。この結果、図１９（Ｂ）、図２０（Ｂ）に示すように、１１番サンプルのサンプル番号は、３番に変更される。
【０１２５】
そして、Ｓ／Ｎビットメモリ１００は、設定されたエリアＡＲ１５のＳ／ＮビットデータをＡＮＤ・ＯＲ回路１０３１〜１０３１２及び係数モデリング回路１０６に供給する。また、係数ビットメモリ１０１は、設定されたエリアＡＲ１６の係数ビットデータを係数モデリング回路１０６に供給する。
【０１２６】
上述したＤＦＦ１０７は、１１番サンプル用のジャンプアドレス値の同期を取り、現サンプル点位置情報として、プライオリティ・エンコーダ１１０に供給する。
【０１２７】
このとき、１番乃至１２番サンプルにＳＰパス処理対象サンプル点があれば、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の何れかの出力が「１」になる。一方、１番乃至１２番サンプルにＳＰパス処理対象サンプル点がなければ、ＡＮＤ・ＯＲ回路１０３１〜１０３１２のどの出力も「０」になる。
【０１２８】
上述したように、プライオリティ・エンコーダ１１０には、ＡＮＤ・ＯＲ回路１０３１〜１０３１２の各出力の他、現サンプル点位置情報が与えられる。したがって、４番乃至１２番サンプルにＳＰパス処理対象サンプル点があり、ＡＮＤ・ＯＲ回路１０３４〜１０３１２のうち１以上の出力が「１」になった場合には、そのうち現サンプル点にスキャン順で最も近いサンプル点のアドレスがジャンプアドレス値として上述の係数モデリング回路１０６に供給される。
【０１２９】
一方、プライオリティ・エンコーダ１１０には、エリアをジャンプするエリアジャンプフラグも与えられる。そして、４番乃至１２番サンプルにＳＰパス処理対象サンプル点がなくＡＮＤ・ＯＲ回路１０３４〜１０３１２の出力が全て「０」である場合、或いはＡＮＤ・ＯＲ回路１０３１，１０３２の出力のみが「１」である場合には、そのエリアジャンプフラグがジャンプアドレス値として上述の係数モデリング回路１０６に供給される。これにより、エリア設定部１０２は、Ｓ／Ｎビットメモリ１００において新たに水平方向５サンプル×垂直方向６サンプルのエリアＡＲ１７（図１９（Ｂ））を設定し、係数ビットメモリ１０１において新たに水平方向３サンプル×垂直方向４サンプルのエリアＡＲ１８（図２０（Ｂ））を設定する。
【０１３０】
以上説明したように、第２の手法によれば、探索エリア内にＳＰパス処理対象サンプル点がある場合、そのサンプル点にジャンプしてＳＰパス処理を行い、ＳＰパス処理対象でないサンプル点における処理を省略することができるため、スキャン順で処理した場合と比較して、処理サイクル数を少なく、或いは処理時間を短くすることができる。また、処理クロック周波数を低減することもでき、低消費電力なハードウェアが実現可能である。
【０１３１】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【０１３２】
例えば、上述の実施の形態では、ハードウェアの構成として説明したが、これに限定されるものではなく、任意の処理を、ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）にコンピュータプログラムを実行させることにより実現することも可能である。この場合、コンピュータプログラムは、記録媒体に記録して提供することも可能であり、また、インターネットその他の伝送媒体を介して伝送することにより提供することも可能である。
【０１３３】
【発明の効果】
以上詳細に説明したように本発明に係る画像符号化装置は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換手段と、上記ウェーブレット変換手段によって生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成手段と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成手段と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理手段と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化手段とを備え、上記符号化パス処理手段は、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行うことにより、次の処理対象となるサンプル点を検出する。
【０１３４】
また、本発明に係る画像符号化装置は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換手段と、上記ウェーブレット変換手段によって生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成手段と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成手段と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理手段と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化手段とを備え、上記符号化パス処理手段は、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行い、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点を、次の処理対象となるサンプル点として検出する。
【０１３５】
このような画像符号化装置によれば、例えばＪＰＥＧ−２０００方式におけるＳｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（ＳＰパス）でビットプレーン内の各サンプル点を処理する際に、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意（ｓｉｇｎｉｆｉｃａｎｔ）又は非有意（ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ）を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行い、又は各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報を記憶手段から読み出し、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較を並列して行う。そして、比較の結果、探索している領域内にＳＰパス処理対象サンプル点がある場合、そのサンプル点にジャンプしてＳＰパス処理を行い、ＳＰパス処理対象でないサンプル点における処理を省略する。これにより、従来のスキャン順で処理した場合と比較して、処理サイクル数を少なく、或いは処理時間を短くすることができる。
【０１３６】
また、本発明に係る画像符号化方法は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、上記符号化パス処理工程では、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われることにより、次の処理対象となるサンプル点が検出される。
【０１３７】
また、本発明に係る画像符号化方法は、入力画像に対してウェーブレット変換を施すことによりサブバンドを生成するウェーブレット変換工程と、上記ウェーブレット変換工程にて生成されたサブバンドを分割し、所定の大きさの符号ブロックを生成する符号ブロック生成工程と、上記符号ブロック単位に最上位ビットから最下位ビットに至るビットプレーンを生成するビットプレーン生成工程と、上記ビットプレーン内の各サンプル点を複数の符号化パスの何れかで処理する符号化パス処理工程と、上記符号化パスによる処理結果に基づいて算術符号化を行う算術符号化工程とを有し、上記符号化パス処理工程では、上記ビットプレーン内の各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、上記複数のマッチングパターンの何れかと一致したサンプル点のうち、現サンプル点位置からスキャン順で最も近いサンプル点が、次の処理対象となるサンプル点として検出される。
【０１３８】
このような画像符号化方法によれば、例えばＪＰＥＧ−２０００方式におけるＳｉｇｎｉｆｉｃａｎｔ　Ｐｒｏｐａｇａｔｉｏｎ　Ｐａｓｓ（ＳＰパス）でビットプレーン内の各サンプル点を処理する際に、現サンプル点位置を含む所定のサンプル数の領域及びその周囲のサンプル点における有意（ｓｉｇｎｉｆｉｃａｎｔ）又は非有意（ｎｏｎ−ｓｉｇｎｉｆｉｃａｎｔ）を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われ、又は各サンプル点及びその周囲のサンプル点における有意又は非有意を示す有意／非有意情報が記憶手段から読み出され、この有意／非有意情報と予め設定された複数のマッチングパターンとの比較が並列して行われる。そして、比較の結果、探索している領域内にＳＰパス処理対象サンプル点がある場合、そのサンプル点にジャンプしてＳＰパス処理が行われ、ＳＰパス処理対象でないサンプル点における処理が省略される。これにより、従来のスキャン順で処理した場合と比較して、処理サイクル数を少なく、或いは処理時間を短くすることができる。
【０１３９】
また、本発明に係るプログラムは、上述した画像符号化処理をコンピュータに実行させるものであり、本発明に係る記録媒体は、そのようなプログラムが記録されたコンピュータ読み取り可能なものである。
【０１４０】
このようなプログラム及び記録媒体によれば、上述した画像符号化処理をソフトウェアにより実現することができる。
【図面の簡単な説明】
【図１】本実施の形態における画像符号化装置の概略構成を説明する図である。
【図２】第３レベルまでウェーブレット変換・分割した場合のサブバンドを説明する図である。
【図３】符号ブロックとサブバンドとの関係を説明する図である。
【図４】同画像符号化装置で生成されるパケットを説明する図である。
【図５】同画像符号化装置のビットプレーン符号化パス生成部において、１番サンプルから３番サンプルへと移る場合のＳ／Ｎマッチングパターンを示す図である。
【図６】同ビットプレーン符号化パス生成部において、１番サンプルから８番サンプルへと移る場合のＳ／Ｎマッチングパターンを示す図である。
【図７】同ビットプレーン符号化パス生成部におけるアドレスジャンプを説明する図であり、同図（Ａ）は、エリアＡＲ１にＳＰパス処理対象サンプル点があった場合の例を示し、同図（Ｂ）は、エリアＡＲ１にＳＰパス処理対象サンプル点がなかった場合の例を示す。
【図８】ジャンプアドレス値を出力するためのテーブルを示す図である。
【図９】第１の手法におけるビットプレーン符号化パス生成部のＳＰパス処理に関係する部分の概略構成を説明する図である。
【図１０】同ビットプレーン符号化パス生成部におけるＳ／Ｎビットメモリを説明する図であり、同図（Ａ）は、２番サンプルから１１番サンプルへと移る場合のエリア設定を示し、同図（Ｂ）は、エリアジャンプする際のエリア設定を示す。
【図１１】同ビットプレーン符号化パス生成部における係数ビットメモリを説明する図であり、同図（Ａ）は、２番サンプルから１１番サンプルへと移る場合のエリア設定を示し、同図（Ｂ）は、エリアジャンプする際のエリア設定を示す。
【図１２】第１の手法を行う場合におけるビットプレーン符号化パス生成部の処理のタイミングチャートを示す図である。
【図１３】１１番サンプル用のＡＮＤ・ＯＲ回路におけるパターンマッチングを説明する図である。
【図１４】エリアジャンプ後における１１番サンプル用のＡＮＤ・ＯＲ回路でのパターンマッチングを説明する図である。
【図１５】第２の手法におけるＳ／Ｎマッチングパターンを示す図である。
【図１６】同ビットプレーン符号化パス生成部におけるアドレスジャンプを説明する図であり、同図（Ａ）は、エリアＡＲ１０にＳＰパス処理対象サンプル点があった場合の例を示し、同図（Ｂ）は、エリアＡＲ１０にＳＰパス処理対象サンプル点がなかった場合の例を示す。
【図１７】Ｓ／Ｎマッチングパターンとの一致点位置、不一致点位置とプライオリティ・エンコーダの出力との関係を示す図であり、同図（Ａ）は、現サンプル点位置が１番サンプルの場合を示し、同図（Ｂ）は、現サンプル点位置が５番サンプルである場合を示す。
【図１８】第２の手法を行う場合におけるビットプレーン符号化パス生成部のＳＰパス処理に関係する部分の概略構成を説明する図である。
【図１９】同ビットプレーン符号化パス生成部におけるＳ／Ｎビットメモリを説明する図であり、同図（Ａ）は、２番サンプルから１１番サンプルへと移る場合のエリア設定を示し、同図（Ｂ）は、エリアジャンプする際のエリア設定を示す。
【図２０】同ビットプレーン符号化パス生成部における係数ビットメモリを説明する図であり、同図（Ａ）は、２番サンプルから１１番サンプルへと移る場合のエリア設定を示し、同図（Ｂ）は、エリアジャンプする際のエリア設定を示す。
【図２１】第１の手法を行う場合におけるビットプレーン符号化パス生成部の処理のタイミングチャートを示す図である。
【図２２】第１、第４、第７、第１１サンプル用のＡＮＤ・ＯＲ回路におけるパターンマッチングを説明する図である。
【図２３】ビットプレーンを説明する図であり、同図（Ａ）は、計１６個の係数から成る量子化係数を示し、同図（Ｂ）は、係数の絶対値のビットプレーンを示し、同図（Ｃ）は、符号のビットプレーンを示す。
【図２４】符号ブロック内の符号化パスの処理手順を説明する図である。
【図２５】符号ブロック内の係数のスキャン順序を説明する図である。
【図２６】従来のＳＰパス処理を説明する図であり、同図（Ａ）は、ＳＰパス処理前における有意なサンプル点を示し、同図（Ｂ）は、ＳＰパス処理により有意なサンプル点が新たに発生した様子を示す。
【符号の説明】
１　画像符号化装置、２　画像復号装置、１０　ＤＣレベルシフト部、１１　ウェーブレット変換部、１２　量子化部、１３　符号ブロック化部、１４　ビットプレーン符号化パス生成部、１５　算術符号化部、１６　ＥＢＣＯＴ部、１７レート制御部、１８　ヘッダ生成部、１９　パケット生成部、１００　Ｓ／Ｎビットメモリ、１０１　係数ビットメモリ、１０２　エリア設定部、１０３１〜１０３１２　ＡＮＤ・ＯＲ回路、１０４　ジャンプアドレス値テーブル、１０５決定用ＡＮＤ・ＯＲ回路、１０６　係数モデリング回路、１０７，１０８　ＤＦＦ、１１０　プライオリティ・エンコーダ
【図１】
2004080273.tif 000003
【図２】
2004080273.tif 000004
【図３】
2004080273.tif 000005
【図４】
2004080273.tif 000006
【図５】
2004080273.tif 000007
【図６】
2004080273.tif 000008
【図７】
2004080273.tif 000009
【図８】
2004080273.tif 000010
【図９】
2004080273.tif 000011
【図１０】
2004080273.tif 000012
【図１１】
2004080273.tif 000013
【図１２】
2004080273.tif 000014
【図１３】
2004080273.tif 000015
【図１４】
2004080273.tif 000016
【図１５】
2004080273.tif 000017
【図１６】
2004080273.tif 000018
【図１７】
2004080273.tif 000019
【図１８】
2004080273.tif 000020
【図１９】
2004080273.tif 000021
【図２０】
2004080273.tif 000022
【図２１】
2004080273.tif 000023
【図２２】
2004080273.tif 000024
【図２３】
2004080273.tif 000025
【図２４】
2004080273.tif 000026
【図２５】
2004080273.tif 000027
【図２６】
2004080273.tif 000028