(57)【要約】【課題】符号化をより高速に行うことができるようにする。【解決手段】パラメータ生成部１０５は、コードブロック化部１０３およびビットプレーン展開部１０４から供給される情報に基づいて、各コードブロックの特徴を表すパラメータを生成する。グループ分け部１０６は、そのパラメータが全て互いに同一のコードブロックを最大１６個ずつグループ化する。並列演算用係数データ生成部１０７は、グループ毎に各コードブロックの係数データを並び替える。EBCOT１０８は、複数のコードブロックに対する符号化を並列に実行する。符号化コードストリーム生成部１０９は、符号化データの並べ替えを行い、１つのコードストリームとして出力する。本発明は、例えば、画像符号化装置に適用することができる。【選択図】図１
2011091575.tif 000002
【特許請求の範囲】
【請求項１】
画像データをサブバンド毎の係数データに変換するウェーブレット変換手段と、
前記ウェーブレット変換手段により生成された前記係数データの前記サブバンドの領域をコードブロックに分割するコードブロック化手段と、
前記コードブロック化手段により生成された前記コードブロックを、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けするグループ分け手段と、
前記グループ分け手段により生成されたグループ毎に、グループ内の各コードブロックの係数データを並列に符号化する符号化手段と
を備える符号化装置。
【請求項２】
前記符号化手段は、前記グループ内の各コードブロックの互いに同じ位置の係数データを並列に符号化する
請求項１に記載の符号化装置。
【請求項３】
前記グループ分け手段により生成されたグループ内の各コードブロックの互いに同じ位置の係数データを、所定のデータ量毎に、前記符号化手段が並列に符号化することができるような順序に並び替え、並列演算用係数データを生成する並列演算用係数データ生成手段をさらに備え、
前記符号化手段は、前記並列演算用係数データ生成手段により生成された前記並列演算用係数データを、複数のコードブロックを並列に処理するように符号化する
請求項１に記載の符号化装置。
【請求項４】
前記グループ分け手段により生成されたグループにおいて、所属する前記コードブロックが前記所定数に満たない場合、前記コードブロックの数が前記所定数となるようにダミーデータを追加する追加手段をさらに備える
請求項１に記載の符号化装置。
【請求項５】
前記符号化手段により生成された符号化データを所定順に並び替え、コードストリームを生成するコードストリーム生成手段をさらに備える
請求項１に記載の符号化装置。
【請求項６】
前記グループ分け手段により生成されたグループにおいて、所属する前記コードブロックが前記所定数に満たない場合、前記コードブロックの数が前記所定数となるようにダミーデータを追加する追加手段をさらに備え、
前記コードストリーム生成手段は、前記追加手段により追加された前記ダミーデータの符号化結果を破棄する
請求項５に記載の符号化装置。
【請求項７】
前記符号化手段による符号化の並列数は、データレジスタ長をデータ処理単位のビット長で除算したときの商である
請求項１に記載の符号化装置。
【請求項８】
前記コードブロック化手段により生成された前記コードブロックの特徴を示すパラメータを生成するパラメータ生成手段をさらに備え、
前記グループ分け手段は、前記パラメータ生成手段により生成された前記パラメータの値が全て互いに一致する所定数のコードブロックをグループ化する
請求項１に記載の符号化装置。
【請求項９】
前記パラメータ生成手段は、前記コードブロックの水平サイズおよび垂直サイズ、前記コードブロックにおいて用いられる符号化パスの数を示す符号化パス数、並びに、前記コードブロックが属するサブバンドタイプを、前記パラメータに含める
請求項８に記載の符号化装置。
【請求項１０】
前記コードブロック化手段により生成された前記コードブロックを、互いに同一の位のビットの集合であるビットプレーンに展開するビットプレーン展開手段をさらに備え、
前記パラメータ生成手段は、前記符号化パス数を、前記コードブロックの最大ビット深度と、前記ビットプレーン展開手段により展開された前記ビットプレーンの中のMSBのビットプレーンから連続する全ての係数の値が０のビットプレーンの数であるゼロビットプレーン数との差の３倍から２を引いた値として算出する
請求項９に記載の符号化装置。
【請求項１１】
前記符号化手段は、ビットプレーン展開されたバイナリデータを１ピクセル単位にモデリングしながら算術符号化するEBCOTを行い、CUパス、SPパス、MRパスの３つの符号化パスによって前記係数データを符号化する
請求項１０に記載の符号化装置。
【請求項１２】
画像データをサブバンド毎の係数データに変換し、
生成された前記係数データの前記サブバンドの領域をコードブロックに分割し、
生成された前記コードブロックを、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けし、
生成されたグループ毎に、グループ内の各コードブロックの係数データを並列に符号化する
符号化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置および方法に関し、特に、より高速に符号化を行うことができるようにした符号化装置および方法に関する。
【背景技術】
【０００２】
2000年にISO/IEC（International Organization for Standardization / International Electrotechnical Commission）で標準化されたJPEG（Joint Photographic Experts Group）2000は、高圧縮率、可逆と非可逆圧縮対応、スケラビリティ（解像度・画質など）、およびエラー耐性等の多くの機能を持った技術として、JPEGの代替技術としての期待が高まっている。
【０００３】
2004年にはデジタルシネマの標準規格（DCI（Digital Cinema Initiative））によって、標準コーデックとしてJPEG2000 Part-1が選ばれた。これによってデジタルシネマの映像撮影から、画像編集、画像配信まで、すべてJPEG2000で統一することが可能になった。
【０００４】
また、医用画像や衛星写真画像などはオリジナルのまま保存が必須である。さらに、最近の一眼レフデジタルカメラでは、CCD（Charge Coupled Device）やCMOS（Complementary Metal Oxide Semiconductor）のイメージセンサから取得したRAWデータまたはRGBデータを、非圧縮のままメモリカードに保存できるものが多い。
【０００５】
しかしながら、マスタ画像を非圧縮とすることは、画像としてのデータ欠損をなくすことが出来る点で有利であるが、データサイズが巨大になる点で不利である。そのため、デジタルシネマ以外の、例えば以上のような、画質を重要とする用途でも、JPEG2000可逆圧縮によって圧縮・伸長されるニーズが今後高まる。
【０００６】
特許文献１には、固定小数点型ウェーブレット変換器と、整数型ウェーブレット変換器の両方を備え、可逆変換および非可逆変換の両方を行うことができ、画質や圧縮率の選択の自由度を高め得るような画像符号化装置が記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許３９０６６３０号
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、JPEG2000の場合、その計算負荷がJPEGに比べて圧倒的に大きくなる恐れがあった。特に可逆圧縮の場合にはすべての係数データを欠損なく圧縮することから、膨大な時間を要する恐れがあった。
【０００９】
JPEG2000符号化技術の中でも、１番計算負荷が大きいものが、EBCOT（Embedded Block Coding with Optimized Truncation）と呼ばれるエントロピ符号化部である。これはビットプレーン展開されたバイナリデータを１ピクセル単位にモデリングしながら算術符号化する技術を用いている。従って、逐次処理を行う上、上位のビットプレーンの結果が下位のビットプレーンの結果に影響する「依存性」が存在するため、コードブロック内部の並列化が困難とされてきた。従って、大きな解像度の画像のエンコードや可逆圧縮の場合には、如何にしてJPEG2000の計算負荷、特にEBCOTの高速化を実現できるかが、鍵であった。
【００１０】
本発明は、このような状況に鑑みて提案されたものであり、符号化をより高速に行うことができるようにすることを目的とする。
【課題を解決するための手段】
【００１１】
本発明の一側面は、画像データをサブバンド毎の係数データに変換するウェーブレット変換手段と、前記ウェーブレット変換手段により生成された前記係数データの前記サブバンドの領域をコードブロックに分割するコードブロック化手段と、前記コードブロック化手段により生成された前記コードブロックを、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けするグループ分け手段と、前記グループ分け手段により生成されたグループ毎に、グループ内の各コードブロックの係数データを並列に符号化する符号化手段とを備える符号化装置である。
【００１２】
前記符号化手段は、前記グループ内の各コードブロックの互いに同じ位置の係数データを並列に符号化することができる。
【００１３】
前記グループ分け手段により生成されたグループ内の各コードブロックの互いに同じ位置の係数データを、所定のデータ量毎に、前記符号化手段が並列に符号化することができるような順序に並び替え、並列演算用係数データを生成する並列演算用係数データ生成手段をさらに備え、前記符号化手段は、前記並列演算用係数データ生成手段により生成された前記並列演算用係数データを、複数のコードブロックを並列に処理するように符号化することができる。
【００１４】
前記グループ分け手段により生成されたグループにおいて、所属する前記コードブロックが前記所定数に満たない場合、前記コードブロックの数が前記所定数となるようにダミーデータを追加する追加手段をさらに備えることができる。
【００１５】
前記符号化手段により生成された符号化データを所定順に並び替え、コードストリームを生成するコードストリーム生成手段をさらに備えることができる。
【００１６】
前記グループ分け手段により生成されたグループにおいて、所属する前記コードブロックが前記所定数に満たない場合、前記コードブロックの数が前記所定数となるようにダミーデータを追加する追加手段をさらに備え、前記コードストリーム生成手段は、前記追加手段により追加された前記ダミーデータの符号化結果を破棄することができる。
【００１７】
前記符号化手段による符号化の並列数は、データレジスタ長をデータ処理単位のビット長で除算したときの商であるようにすることができる。
【００１８】
前記コードブロック化手段により生成された前記コードブロックの特徴を示すパラメータを生成するパラメータ生成手段をさらに備え、前記グループ分け手段は、前記パラメータ生成手段により生成された前記パラメータの値が全て互いに一致する所定数のコードブロックをグループ化することができる。
【００１９】
前記パラメータ生成手段は、前記コードブロックの水平サイズおよび垂直サイズ、前記コードブロックにおいて用いられる符号化パスの数を示す符号化パス数、並びに、前記コードブロックが属するサブバンドタイプを、前記パラメータに含めることができる。
【００２０】
前記コードブロック化手段により生成された前記コードブロックを、互いに同一の位のビットの集合であるビットプレーンに展開するビットプレーン展開手段をさらに備え、前記パラメータ生成手段は、前記符号化パス数を、前記コードブロックの最大ビット深度と、前記ビットプレーン展開手段により展開された前記ビットプレーンの中のMSBのビットプレーンから連続する全ての係数の値が０のビットプレーンの数であるゼロビットプレーン数との差の３倍から２を引いた値として算出することができる。
【００２１】
前記符号化手段は、ビットプレーン展開されたバイナリデータを１ピクセル単位にモデリングしながら算術符号化するEBCOTを行い、CUパス、SPパス、MRパスの３つの符号化パスによって前記係数データを符号化することができる。
【００２２】
本発明の一側面は、また、画像データをサブバンド毎の係数データに変換し、生成された前記係数データの前記サブバンドの領域をコードブロックに分割し、生成された前記コードブロックを、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けし、生成されたグループ毎に、グループ内の各コードブロックの係数データを並列に符号化する符号化方法である。
【００２３】
本発明の一側面においては、画像データがサブバンド毎の係数データに変換され、生成された係数データのサブバンドの領域がコードブロックに分割され、生成されたコードブロックが、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けされ、生成されたグループ毎に、グループ内の各コードブロックの係数データが並列に符号化される。
【発明の効果】
【００２４】
本発明によれば、画像を符号化することができる。特に、より高速に画像を符号化することができる。
【図面の簡単な説明】
【００２５】
【図１】本発明を適用した画像符号化装置の主な構成例を示すブロック図である。
【図２】サブバンドの構成例を示す図である。
【図３】各サブバンド中のコードブロックの例を示す図である。
【図４】ビットプレーンの例を説明する図である。
【図５】符号化パスの例を説明する図である。
【図６】係数の走査の例を説明する図である。
【図７】符号化パスについて説明する図である。
【図８】コードブロックのグループ化を説明する図である。
【図９】並列演算用係数データの生成の様子を説明する図である。
【図１０】係数データの並列演算の様子を説明する図である。
【図１１】符号化処理の流れの例を説明するフローチャートである。
【図１２】本発明を適用するハードウェアの例を示す図である。
【図１３】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００２６】
以下、発明を実施するための形態（以下実施の形態とする）について説明する。なお、説明は以下の順序で行う。
１．第１の実施の形態（画像符号化装置）
２．第２の実施の形態（パーソナルコンピュータ）
【００２７】
＜１．第１の実施の形態＞
［画像符号化装置の構成］
図１は、本発明を適用した画像符号化装置の一実施の形態の構成を表している。図１に示される画像符号化装置１００は、画像データをJPEG（Joint Photographic Experts Group）2000の方式で、可逆または非可逆に、符号化する符号化装置である。
【００２８】
画像符号化装置１００は、画像データをウェーブレット変換し、得られた係数を、コードブロック毎にビットプレーンに展開し、ビットプレーン毎にエントロピ符号化する。
【００２９】
このEBCOT（Embedded Block Coding with Optimized Truncation）と呼ばれるエントロピ符号化は、ビットプレーン展開されたバイナリデータを１ピクセル単位にモデリングしながら算術符号化する技術である。
【００３０】
従来、この処理は、逐次処理を行う上、上位のビットプレーンの結果が下位のビットプレーンの結果に影響する「依存性」が存在するため、コードブロック内部の並列化が困難とされてきた。つまり、大きな解像度の画像のエンコードや可逆圧縮の場合、如何にしてJPEG2000の計算負荷、特にEBCOTの高速化を実現できるかが、鍵であった。
【００３１】
そこで、画像符号化装置１００は、コードブロックを適切にグループ化して並列演算用係数データを生成し、複数のEBCOTを並列に実行する。これにより、画像符号化装置１００は、EBCOTの高速化、すなわち、JPEG2000の計算負荷の軽減を実現することができる。
【００３２】
図１に示されるように、画像符号化装置１００は、ウェーブレット変換部１０１、量子化部１０２、コードブロック化部１０３、ビットプレーン展開部１０４、パラメータ生成部１０５、グループ分け部１０６、並列演算用係数データ生成部１０７、EBCOT１０８、および符号化コードストリーム生成部１０９を有する。
【００３３】
ウェーブレット変換部１０１は、通常、低域フィルタと高域フィルタから構成されるフィルタバンクによって実現される。また、デジタルフィルタは通常複数タップ長のインパルス応答（フィルタ係数）を有するので、ウェーブレット変換部１０１は、フィルタリングが行えるだけの入力画像を予めバッファリングするバッファを有する。
【００３４】
ウェーブレット変換部１０１は、入力された画像データ（矢印１２１）を、フィルタリングに最低限必要なデータ量以上取得する。ウェーブレット変換部１０１は、その画像データに対して、例えば５×３ウェーブレット変換フィルタを用いてフィルタリングを行い、ウェーブレット係数を生成する。なお、ウェーブレット変換部１０１は、画像の垂直方向および水平方向のそれぞれに対して、画像データを低域成分と高域成分に分離するフィルタリングを行う。
【００３５】
そして、ウェーブレット変換部１０１は、このようなフィルタリング処理を、図２に示されるように、垂直方向および水平方向の両方において低域成分として分離されたサブバンドに対して再帰的に所定回数繰り返す。これは、画像のエネルギーの多くが低域成分に集中しているからである。
【００３６】
図２は、分割レベル数３のウェーブレット変換処理により生成されるサブバンドの構成例を示す図である。この場合、ウェーブレット変換部１０１は、まず、画像全体をフィルタリングし、サブバンド3LL（図示せず）、3HL、3LH、および3HHを生成する。次に、ウェーブレット変換部１０１は、生成されたサブバンド3LLに対して再度フィルタリングを行い、2LL（図示せず）、2HL、2LH、および2HHを生成する。さらに、ウェーブレット変換部１０１は、生成されたサブバンド2LLに対して再度フィルタリングを行い、1LL、1HL、1LH、および1HHを生成する。
【００３７】
なお、ウェーブレット変換の分割レベル数は任意である。
【００３８】
図１に戻り、ウェーブレット変換部１０１は、フィルタリングにより得られた係数データ（ウェーブレット係数）を、サブバンド毎に、量子化部１０２に供給する（矢印１２２）。
【００３９】
量子化部１０２は、供給された係数データ（ウェーブレット係数）を量子化する。量子化部１０２は、得られた係数データ（量子化係数）を、コードブロック化部１０３に供給する（矢印１２３）。なお、JPEG2000の規格では、可逆圧縮の場合、量子化処理は省略される。その場合、ウェーブレット変換部１０１より出力された係数データ（ウェーブレット係数）は、コードブロック化部１０３に供給される（矢印１２４）。
【００４０】
コードブロック化部１０３は、供給された係数データを、予め定められた所定の大きさの矩形の、エントロピ符号化の処理単位であるコードブロックに分割する。JPEG2000の規格上の定義によって、コードブロックの縦・横サイズはどのサブバンドにおいても一定である。但し画像（サブバンド）の両端や上端・下端などでは、同じサイズのコードブロックが取れないケースも多々ある。
【００４１】
図３は、図２を参照して説明した各サブバンド中のコードブロックの位置関係を示したものである。例えば64×64画素程度のサイズのコードブロックが、分割後のすべてのサブバンド中に生成される。例えば、最も分割レベルが小さい3HHのサブバンドの大きさが例えば640×320画素であるとすると、64×64画素のコードブロックは合計５０個存在することになる。後段の各処理部は、このコードブロック毎に処理を行う。もちろん、このコードブロックのサイズ（画素数）は任意である。
【００４２】
図１に戻り、コードブロック化部１０３は、係数データをコードブロック毎にビットプレーン展開部１０４に供給する（矢印１２５）。また、コードブロック化部１０３は、各コードブロックに関する情報をパラメータ生成部１０５に供給する（矢印１２６）。
【００４３】
ビットプレーン展開部１０４は、供給されたコードブロック毎の係数データを、ビットの位毎のビットプレーンに展開する。
【００４４】
ビットプレーンは、所定の数のウェーブレット係数よりなる係数群（例えばコードブロック）を、１ビット毎、つまり位毎に分割（スライス）したものである。つまり、ビットプレーンは、それぞれが複数ビットのビット深度を持つ複数のデータの、互いに同一の位のビット（係数ビット）の集合である。したがって、展開されるビットプレーン数は、各係数のビット深度に依存する。
【００４５】
図４にその具体例を示す。図４の左図は縦４個、横４個の計１６個の係数を示している。この１６個の係数のうち、絶対値が最大のものは１３で、２進数で１１０１と表現される。ビットプレーン展開部１０４は、このような係数群を、絶対値を示す４枚のビットプレーン（絶対値のビットプレーン）と、符号を示す１枚のビットプレーン（符号のビットプレーン）に展開する。つまり、図４中左の係数群は、図４中右に示されるように、４枚の絶対値のビットプレーンと１枚の符号のビットプレーンに展開される。ここで、絶対値のビットプレーンの要素はすべて０か１の値をとる。また、符号を示すビットプレーンの要素は、係数の値が正であることを示す値、係数の値が０であることを示す値、または係数の値がマイナスを示す値のいずれかをとる。
【００４６】
なお、このようにビットプレーンとされる係数群における係数の数は任意である。以下においては、処理単位を統一することで各部における処理を容易にするために、ビットプレーン展開部１０４が、係数をコードブロック毎にビットプレーン展開するものとして説明する。
【００４７】
図１に戻り、ビットプレーン展開部１０４は、このように展開したビットプレーンを、係数の最上位ビット（MSB：Most Significant Bit）から最下位ビット（LSB：Less Significant Bit）に向かう順に、並列演算用係数データ生成部１０７に供給する。つまり、ビットプレーン展開部１０４は、ビット深度の上位側から下位側に向かう順に、展開したビットプレーンを並列演算用係数データ生成部１０７に供給する（矢印１３０）。また、ビットプレーン展開部１０４は、このようにビットプレーン展開についての情報をパラメータ生成部１０５に供給する（矢印１２７）。
【００４８】
パラメータ生成部１０５は、コードブロック化部１０３およびビットプレーン展開部１０４から供給される情報に基づいて、各コードブロックの特徴を表すパラメータを生成する。
【００４９】
このパラメータとしては、コードブロックの特徴を表すものであればどのようなものであってもよいが、例えば、コードブロックの水平サイズ（h_size）、コードブロックの垂直サイズ（v_size）、サブバンドタイプ（LL,HL,LH.HH）、および、後述するように算出される符号化パス数(num_pass)を含むようにしてもよい。もちろん、これら以外のものがパラメータに含まれていてもよい。
【００５０】
これらのパラメータがどのコードブロックに対応するものであるかは、任意の方法で示されている。例えば、コードブロックの識別情報（コードブロック番号等）により関連付けられるようにしてもよい。
【００５１】
ここで符号化パスについて説明する。後述するように、画像符号化装置１００は、特にJPEG2000規格で定められたEBCOT(Embedded Coding with Optimized Truncation)と呼ばれるエントロピ符号化を行う（参考文献：IS0/IEC 15444-1, Information technology-JPEG 2000, Part 1:Core coding system）。
【００５２】
EBCOTは、所定の大きさのブロック毎にそのブロック内の係数の統計量を測定しながら符号化を行う手段である。量子化係数をコードブロック単位に、エントロピ符号化する。コードブロックは、最上位ビット（MSB）から最下位ビット（LSB）方向にビットプレーン毎に独立して符号化される。コードブロックの縦横のサイズは４から256までの２のべき乗で、通常使用される大きさは、32x32、64x64、または128x32等がある。量子化係数値がｎビットの符号付き２進数で表されていて、bit 0からbit n-1がLSBからMSBまでのそれぞれのビットを表すとする。残りの１ビットは符号である。コードブロックの符号化は、MSB側のビットプレーンから順番に、次の３種類の符号化パスによって行われる。
【００５３】
（１）Significant Propagation Pass
（２）Magnitude Refinement Pass
（３）Cleanup Pass
【００５４】
３つの符号化パスの用いられる順序は、図５で示される。最初にBit-plane（n-1）（MSB）がCleanup Passによって符号化される。続いて順次LSB側に向かい、各ビットプレーンの符号化が、３つの符号化パスをSignificant Propagation Pass、Magnitude Refinement Pass、Cleanup Passの順序で用いて行われる。
【００５５】
ただし、実際にはMSB側から何番目のビットプレーンで初めて１が出てくるかをヘッダに書き、MSB側から連続するオール０のビットプレーン（ゼロビットプレーンと呼ぶ）は符号化しない。この順序で３種類の符号化パスを繰返し用いて符号化し、任意のビットプレーンの、任意の符号化パス迄で符号化を打ち切ることにより、符号量と画質のトレードオフを取る（レート制御を行う）。
【００５６】
次に、係数の走査（スキャニング）について図６を用いて説明する。コードブロックは高さ４個の係数毎にスプライト（sprite）に分けられる。スプライトの幅はコードブロックの幅に等しい。スキャン順とは、１個のコードブロック内の、すべての係数をたどる順番で、コードブロック中では上のスプライトから下のスプライトへの順序、スプライトの中では、左の列から右の列へ向かっての順序、列の中では上から下へという順序である。各符号化パスにおいてコードブロック中のすべての係数が、このスキャン順で処理される。
【００５７】
以下、３つの符号化パスについて述べる。以下はいずれもJPEG-2000規格書（参考文献：IS0/IEC 15444-1, Information technology-JPEG 2000, Part 1:Core coding system）に記述されている内容である。
【００５８】
（１）Significance Propagation Pass（SPパス）：
あるビットプレーンを符号化するSignificance Propagation Passでは、８近傍の少なくとも１つの係数が有意（significant）であるようなnon-significant係数のビットプレーンの値を算術符号化する。その符号化したビットプレーンの値が１である場合は、符号が＋であるか、−であるかを続けてMQ符号化する。
【００５９】
ここでsignificanceというJPEG2000特有の用語について説明する。significanceとは、各係数に対して符号化器が持つ状態で、significanceの初期値はnon-significantを表す０、その係数で１が符号化されたときにsignificantを表す１に変化し、以降常に１であり続けるものである。従って、significanceとは有効桁の情報を既に符号化したか否かを示すフラグとも言える。あるビットプレーンでsignificantになれば、以降のビットプレーンではsignificantになったままである。
【００６０】
（２）Magnitude Refinement Pass（MRパス）：
ビットプレーンを符号化するMagnitude Refinement Passでは、ビットプレーンを符号化する Significance Propagation Passで、且つ符号化していないsignificantな係数のビットプレーンの値をMQ符号化する。
【００６１】
（３）Cleanup Pass（CUパス）：
ビットプレーンを符号化するCleanup Passでは、ビットプレーンを符号化するSignificance Passで、且つ符号化していないnon-significantな係数のビットプレーンの値をMQ符号化する。その符号化したビットプレーンの値が１である場合は符号が＋であるか−であるか（Sign情報）を続けてMQ符号化する。
【００６２】
尚、以上の３つの符号化パスでのMQ符号化では、ケースに応じて、ZC（Zero Coding）、RLC（Run-Length Coding）、SC（Sign Coding）、およびMR（Magnitude Refinement）が使い分けられる。ここでMQ符号化と呼ばれる算術符号が用いられる。MQ符号化は、JBIG2（参考文献：ISO/IEC FDIS 14492, “Lossy/Lossless Coding of Bi-level Images”, March 2000）で規定された学習型の２値算術符号である。
【００６３】
図７は、横軸がコードブロック（CB0乃至CBn：n+1個のCodeblock）、縦軸がビットプレーンを示している。MSBのビットプレーンから連続する、係数が全て０のビットプレーンをゼロビットプレーンと称し、それ以外のビットプレーンを有効ビットプレーンと称する。更に、図７のZero.Bitsは、ゼロビットプレーン数、一方、エンコード以前に定義される最大ビット深度（LSB乃至MSB）をMax.Bitsと定義する。
【００６４】
従って、１つのコードブロックにおいて用いられる符号化パスの数を示す符号化パス数(num_pass)は、以下の式（１）のように算出される。
【００６５】
num_pass＝（Max.Bits−Zero.Bits）×３−２    ・・・（１）
【００６６】
図１に戻り、パラメータ生成部１０５は、以上のように生成したパラメータをグループ分け部１０６に供給する（矢印１２８）。
【００６７】
グループ分け部１０６は、パラメータ生成部１０５から供給されるパラメータに基づいて、コードブロックのグループ分けを行う。グループ分け部１０６は、１ピクチャ分のコードブロックについてパラメータを取得する。
【００６８】
図８Ａに示される例のように、ピクチャ内のコードブロックのサイズ（水平サイズおよび垂直サイズ）は全てが同一ではない。上述したように、コードブロック化は基本的に同一のサイズ（基本サイズ）とするように行われるが、画像（サブバンド）の両端や上端・下端等において、その基本サイズを確保できない場合がある。このような部分のコードブロックのサイズは、基本サイズより小さいものとなる。
【００６９】
また、上述したように、コードブロック化は係数データに対して行われるので、ピクチャ内の各コードブロックが属するサブバンドは全てが同一ではない。さらに、各コードブロックのゼロビットプレーン数（有効ビットプレーン数）は互いに独立しているので、符号化パス数もコードブロック毎に異なる可能性がある。
【００７０】
グループ分け部１０６は、ピクチャ内の各コードブロックのパラメータの値を比較し、図８Ｂに示されるように、全ての値が同一となるコードブロックをグループ化する。
【００７１】
図８Ｂにおいて、グループ２０１乃至グループ２０４は、それぞれ、このようにパラメータによって分類されたコードブロック群である。換言すれば、各グループにおいて、全てのコードブロックの全パラメータの値は、互いに同一である。
【００７２】
グループ分け部１０６は、各グループが最大１６個のコードブロックにより形成されるように、パラメータによって分けたグループを、適宜分割する。図８Ｃの例に示されるグループ２１１乃至グループ２１６は、図８Ｂの各グループを、コードブロック数が最大１６個となるように、さらに分割したものの中の一部である。例えば、図８Ｃのグループ２１１乃至グループ２１３は、図８Ｂのグループ２０１をさらに分割したものであり、図８Ｃのグループ２１４およびグループ２１５は、図８Ｂのグループ２０２をさらに分割したものである。図８Ｃのグループ２１６は、図８Ｂのグループ２０４に対応するが、グループ２０４に属するコードブロックの数が１６以下であるので、グループ２０４と同じコードブロック数である。
【００７３】
図１に戻り、グループ分け部１０６は、そのグループ分けの情報を、パラメータ等の各コードブロックの情報とともに、並列演算用係数データ生成部１０７に供給する（矢印１２９）。
【００７４】
並列演算用係数データ生成部１０７は、グループ内のコードブロックを並列に演算（エントロピ符号化）することができるように、グループ毎に各コードブロックの係数データを並び替えて並列演算用係数データを生成する。
【００７５】
並列演算用係数データ生成部１０７は、ビットプレーン展開部１０４から係数データを取得すると、それをメモリ（図示せず）に保持する。並列演算用係数データ生成部１０７は、１ピクチャ分の係数データを取得すると（保持すると）、グループ分け部１０６によるグループ分けに従って、処理対象グループに属する各コードブロックの互いに同位置の係数データを、上から下、左から右の順番に読み出して、メモリ内のレジスタに配置する。並列演算用係数データ生成部１０７は、この係数データの読み出しを各ビットプレーンについて行う。
【００７６】
図９は、サイズが６４×６４のコードブロックのグループから、並列演算用係数データを生成する様子の例を示している。図９において、上段のcodeblock0乃至codeblock15は、処理対象グループに属する１６個のコードブロックを示している。下段はレジスタに配置された（並び替えられた）係数データを示す。
【００７７】
図９に示されるように、ビットプレーン毎に、各コードブロックの互いに同位置の係数データが８ビット（幅８×高さ１×１ビット）ずつ読み出され、レジスタに配置される。例えば、Sign bitplaneにおいては、codeblock0から８ビットの係数データ２２１−１が読み出され、codeblock1から８ビットの係数データ２２１−２が読み出され、codeblock3乃至codeblock14においても同様に読み出しが行われ、codeblock15から８ビットの係数データ２２１−１６が読み出される。それらの係数データ２２１−１乃至係数データ２２１−１６は、レジスタに並べて配置される。つまり、１２８ビット（幅１２８×高さ１×１ビット）の並列演算用係数データとなる（レジスタのサイズは１２８ビット以上である）。
【００７８】
後述するように、そのレジスタの並列演算用係数データが、各８ビットの係数データ毎に並列化されて符号化されると、次に、codeblock0から次の８ビットの係数データ２２２−１が読み出され、codeblock1からも次の８ビットの係数データ２２２−２が読み出され、codeblock3乃至codeblock14においても同様に次の８ビットの係数データの読み出しが行われ、codeblock15からも次の８ビットの係数データ２２２−１６が読み出される。それらの係数データ２２２−１乃至係数データ２２２−１６は、係数データ２２１−１乃至係数データ２２１−１６と同様に、レジスタに並べて配置される。つまり、１２８ビット（幅１２８×高さ１×１ビット）の並列演算用係数データとなる。
【００７９】
この並列演算用係数データも、各８ビットの係数データ毎に並列化されて符号化される。このような処理が、コードブロック内の全ての係数データに対して行われる。
【００８０】
このとき、同一グループ内のコードブロックは、パラメータ（横サイズ、縦サイズ、符号化パス数（有効ビットプレーン数）、およびサブバンドタイプ）の値がすべて一致している。すなわち、codeblock0乃至codeblock15のそれぞれのサンプル数（64×64＝4,096個）やMSB乃至LSBのビットプレーン数等が全て互いに同一である。
【００８１】
つまり、同一グループ内の各コードブロックは、互いに同一の方法で符号化することができるデータ構造になっている。換言すれば、各コードブロックは、最も並列化が容易なデータ構造になっている。
【００８２】
また、互いにデータ構造が同一であるので、上述した並び替えにより、容易に、各コードブロックの係数データを、不足や余り無く並列化するように並び替えることができる。
【００８３】
なお、グループ内のコードブロック数が１６個に満たない場合、並列演算用係数データ生成部１０７は、ダミーデータ（例えばゼロ値）を補充することで対応する（コードブロック数を疑似的に１６個にする）。
【００８４】
図１に戻り、並列演算用係数データ生成部１０７は、並列演算用係数データをEBCOT１０８に供給する。EBCOT１０８は、JPEG2000規格で定められた手順に従って、係数データに対してビットモデリングを行い、係数のビットプレーンを算術符号化する。
【００８５】
ただし、EBCOT１０８は、EBCOT１０８−１乃至EBCOT１０８−１６を有する。EBCOT１０８−１乃至EBCOT１０８−１６は、それぞれ、JPEG2000規格で定められた手順に従って、係数データに対してビットモデリングを行い、係数のビットプレーンを算術符号化する。すなわち、EBCOT１０８は、最大１６並列で、JPEG2000規格で定められたEBCOTと呼ばれるエントロピ符号化を行う。
【００８６】
並列演算用係数データ生成部１０７は、レジスタの並列演算用係数データを、８ビットずつ、すなわち、各コードブロックから読み出した係数データを、EBCOT１０８−１乃至EBCOT１０８−１６に供給する（矢印１３１−１乃至矢印１３１−１６）。
【００８７】
EBCOT１０８−１乃至EBCOT１０８−１６は、互いに並列に、供給された係数データを符号化し、符号化データを生成する。
【００８８】
図１０は、図９の１２８ビットレジスタ内の係数を、１度に１６並列動作させる様子を図示したものである。図中、８ピクセルで区切られたバイナリ値を左端から１ビットずつシフトしながら右端まで処理する。
【００８９】
従来の場合、
手順１：CB0のX→Y→・・・・0
手順２：CB1のX→Y→・・・・0
手順３：CB2のX→Y→・・・・0
・・・・・・・・・・・・・
手順１５：CB14のX→Y→・・・・0
手順１６：CB15のX→Y→・・・・0
という順番に符号化が行われていた。したがって、手順１乃至手順１６に示されるように、１６個のコードブロック×８ビット分の時間が必要であった。
【００９０】
これに対して本発明の場合、１６個のコードブロックの同一位置にある係数を１度に（並列に）符号化する。
【００９１】
つまり、本発明の場合、
手順１：CB0、CB1、CB2、・・・・・・CB14、CB15のX
手順２：CB0、CB1、CB2、・・・・・・CB14、CB15のY
手順３：CB0、CB1、CB2、・・・・・・CB14、CB15の0
手順４：CB0、CB1、CB2、・・・・・・CB14、CB15の0
手順５：CB0、CB1、CB2、・・・・・・CB14、CB15の0
手順６：CB0、CB1、CB2、・・・・・・CB14、CB15の0
手順７：CB0、CB1、CB2、・・・・・・CB14、CB15の0
手順８：CB0、CB1、CB2、・・・・・・CB14、CB15の0
という順番に符号化が行われる。従って、EBCOT１０８は、手順１乃至手順８の８ビット分の時間で符号化を行うことができる。つまり、EBCOT１０８は、従来よりも高速に符号化を行うことができる。
【００９２】
図１に戻り、EBCOT１０８−１乃至EBCOT１０８−１６は、生成した符号化データを符号化コードストリーム生成部１０９に供給する（矢印１３２−１乃至矢印１３２−１６）。
【００９３】
符号化コードストリーム生成部１０９は、EBCOT１０８−１乃至EBCOT１０８−１６から供給された符号化データを、従来の場合の符号化データの並びと同様の並び順に並べ替え、１つのコードストリームとして出力する（矢印１３３）。
【００９４】
上述したように、従来の場合、ビットプレーン展開された係数データの各コードブロックが順番に符号化される。符号化コードストリーム生成部１０９は、このような手順で符号化されて生成された係数データと同じ並び順になるように、各符号化データの順序を並び替える。
【００９５】
この符号化データの並び替えは、例えば、EBCOT１０８−１乃至EBCOT１０８−１６により生成された各符号化データをメモリに一旦保持し、従来の符号化の順で読み出すことにより行われる。
【００９６】
なお、並列演算用係数データ生成部１０７によりダミーデータが挿入されてから、符号化が行われた場合、符号化コードストリーム生成部１０９は、そのダミーデータに対応する符号化データは削除する（コードストリームには含めない）。
【００９７】
［処理の流れ］
以上のような符号化処理の流れの例を図１１のフローチャートを参照して説明する。
【００９８】
符号化処理が開始されると、ウェーブレット変換部１０１は、ステップＳ１０１において、１ピクチャ分の画像データをウェーブレット変換する。ステップＳ１０２において、量子化部１０２は、ステップＳ１０１において生成された係数データを量子化する。なお、可逆符号化の場合、このステップＳ１０２の処理は省略される。
【００９９】
ステップＳ１０３において、コードブロック化部１０３は、係数データをコードブロック化する。ステップＳ１０４において、ビットプレーン展開部１０４は、係数データをビットプレーン展開する。
【０１００】
ステップＳ１０５において、パラメータ生成部１０５は、各コードブロックのパラメータ（例えば、h_size，v_size，num_pass、およびsub_type）を生成する。ステップＳ１０６において、グループ分け部１０６は、パラメータに基づいて、各コードブロックのグループ分けを行う。上述したように、グループ分け部１０６は、パラメータの値が全て一致する最大１６個のコードブロックを集めて１つのグループとする。
【０１０１】
ステップＳ１０７において、並列演算用係数データ生成部１０７は、ステップＳ１０６において生成された各グループの中の未処理のグループから、処理対象のグループを選択する。
【０１０２】
ステップＳ１０８において、並列演算用係数データ生成部１０７は、処理対象グループにコードブロックが１６個存在するか否かを判定する。存在すると判定された場合、ステップＳ１１０に進む。
【０１０３】
また、ステップＳ１０８において、処理対象グループにコードブロックが１６個存在しないと判定された場合、ステップＳ１０９に進む。ステップＳ１０９において、並列演算用係数データ生成部１０７は、１６個に不足する数分のコードブロックのダミーデータを追加する。並列演算用係数データ生成部１０７は、例えば、全ての係数値が０のコードブロックをダミーデータとして処理対象グループのコードブロックに追加する。
【０１０４】
ステップＳ１０９の処理により、処理対象グループのコードブロック数がダミーデータも含めて１６個になると、ステップＳ１１０に進む。
【０１０５】
ステップＳ１１０において、並列演算用係数データ生成部１０７は、処理対象グループの各コードブロックの係数データを用いて並列演算用係数データを生成する。ステップＳ１１１において、EBCOT１０８は、その並列演算用係数データを用いて１６並列でエントロピ符号化を行う。
【０１０６】
ステップＳ１１２において、並列演算用係数データ生成部１０７は、未処理のグループが存在するか否かを判定する。存在すると判定された場合、ステップＳ１０７に戻り、それ以降の処理を繰り返す。また、ステップＳ１１２において、ピクチャ内の全てのグループを処理したと判定された場合、ステップＳ１１３に進む。
【０１０７】
ステップＳ１１３において、符号化コードストリーム生成部１０９は、EBCOT１０８において生成された符号化データを並び替え、コードストリームを生成し、出力する。ステップＳ１１３の処理が終了すると、符号化処理が終了される。
【０１０８】
なお、この符号化処理は、ピクチャ毎に行われる。
【０１０９】
以上の様に、画像符号化装置１００は、各コードブロックの特徴を表すパラメータを生成し、そのパラメータの値が全て同一のコードブロックを、最大１６個ずつ、グループ化し、グループ毎に、各コードブロックを並列にエントロピ符号化する。
【０１１０】
これにより、画像符号化装置１００は、複数のコードブロックに対するEBCOTを並列に行うことができ、より高速に符号化を行うことができる。
【０１１１】
上述したように、計算負荷の大きなEBCOTの並列化を実現することができるため、画像符号化装置１００は、符号化処理の計算負荷をより大きく軽減することができる。
【０１１２】
［適用例］
なお、以上において、レジスタ長を１２８ビットとして説明したが、レジスタ長は任意である。また、EBCOTの並列数を１６として説明したが、これに限らず、いくつであってもよい。当然、並列数が増えるほど、符号化処理はより高速になる。
【０１１３】
なお、図１において、EBCOT１０８がEBCOT１０８−１乃至EBCOT１０８−１６を有するように説明したが、これは、実行可能な処理の並列数が１６の場合の構成例である。つまり、EBCOT１０８の構成は、その並列数によって決まる。例えば、並列数がＮの場合、EBCOT１０８は、EBCOT１０８−１乃至EBCOT１０８−Ｎを有する。
【０１１４】
ただし、EBCOTの並列数は、レジスタ長と、その処理単位データ量に依存する。例えば、上述したように、レジスタ長が１２８ビットで、処理単位が８ビットである場合、並列数は１２８／８＝１６となる。つまり、EBCOTの並列数Ｎは、コンピュータまたはハードウェアのデータレジスタ長Ｌビットを、データ処理単位のビット長Ｄビットで除算した値（Ｎ＝Ｌ／Ｄ）で表すことができる（Ｎ，Ｌ、およびＤは自然数）。
【０１１５】
一般的に、コンピュータやハードウェアのデータレジスタ長は最初の設計の段階で決まっている。つまり、EBCOTの最大並列数は、ハードウェアの仕様に依存する場合が多い。図１２は、図１の画像符号化装置１００を適用するハードウェアの構成例を示す図である。
【０１１６】
図１２に示される構成は、CBE（Cell Broadband Engine）と称されるプロセッサの中に８個存在するサブプロセッサであるSPE（Synergistic Processing Elements）の構成である。図１２に示されるように、SPEにおいては、２５６KBのLocal Store（キャッシュメモリ）に対して、１２８ビット単位の読み出しや書き込み（Read/Write）が可能な構成になっている。つまり、これはレジスタ長が１２８ビットであることに対応している。
【０１１７】
また、この１２８ビットレジスタに対する読み出しや書き込み（Read/Write）は、８ビット×１６並列の他、１６ビット×８並列、３２ビット×４並列が可能になっている。従って、SPEでは１６並列が最大並列度であるが、例えば別のコンピュータシステムまたはハードウェアにおいて、４ビット×３２並列、２ビット×６４並列が可能であることも考えられる。その場合、符号化処理の更なる高速化が実現可能である。
【０１１８】
＜２．第２の実施の形態＞
［パーソナルコンピュータ］
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。この場合、例えば、図１３に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０１１９】
図１３において、パーソナルコンピュータ５００のCPU（Central Processing Unit）５０１は、ROM（Read Only Memory）５０２に記憶されているプログラム、または記憶部５１３からRAM（Random Access Memory）５０３にロードされたプログラムに従って各種の処理を実行する。RAM５０３にはまた、CPU５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０１２０】
CPU５０１、ROM５０２、およびRAM５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５１０も接続されている。
【０１２１】
入出力インタフェース５１０には、キーボード、マウスなどよりなる入力部５１１、CRT（Cathode Ray Tube）やLCD（Liquid Crystal Display）などよりなるディスプレイ、並びにスピーカなどよりなる出力部５１２、ハードディスクなどより構成される記憶部５１３、モデムなどより構成される通信部５１４が接続されている。通信部５１４は、インターネットを含むネットワークを介しての通信処理を行う。
【０１２２】
入出力インタフェース５１０にはまた、必要に応じてドライブ５１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア５２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５１３にインストールされる。
【０１２３】
上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、ネットワークや記録媒体からインストールされる。
【０１２４】
この記録媒体は、例えば、図１３に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM（Compact Disc - Read Only Memory）,DVD（Digital Versatile Disc）を含む）、光磁気ディスク（MD（Mini Disc）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM５０２や、記憶部５１３に含まれるハードディスクなどで構成される。
【０１２５】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１２６】
また、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０１２７】
また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表すものである。
【０１２８】
また、以上において、１つの装置（または処理部）として説明した構成を分割し、複数の装置（または処理部）として構成するようにしてもよい。逆に、以上において複数の装置（または処理部）として説明した構成をまとめて１つの装置（または処理部）として構成されるようにしてもよい。また、各装置（または各処理部）の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置（または処理部）の構成の一部を他の装置（または他の処理部）の構成に含めるようにしてもよい。つまり、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【０１２９】
本発明は、例えば、デジタルシネマ用編集装置、アーカイブシステム、放送局の画像伝送装置、画像データベース、医用画像の記録システム、ネットワークサーバ、ノンリニア編集装置、ゲーム機、テレビ受像機システム、HDDレコーダ、PC上のオーサリング・ツールまたはそのソフトウェア・モジュール等に適用することができる。
【符号の説明】
【０１３０】
１００  画像符号化装置，  １０１  ウェーブレット変換部，  １０２  量子化部，  １０３  コードブロック化部，  １０４  ビットプレーン展開部，  １０５  パラメータ生成部，  １０６  グループ分け部，  １０７  並列演算用係数データ生成部，  １０８  EBCOT，  １０９  符号化コードストリーム生成部
【図１】
2011091575.tif 000003
【図２】
2011091575.tif 000004
【図３】
2011091575.tif 000005
【図４】
2011091575.tif 000006
【図５】
2011091575.tif 000007
【図６】
2011091575.tif 000008
【図７】
2011091575.tif 000009
【図８】
2011091575.tif 000010
【図９】
2011091575.tif 000011
【図１０】
2011091575.tif 000012
【図１１】
2011091575.tif 000013
【図１２】
2011091575.tif 000014
【図１３】
2011091575.tif 000015