(57)【要約】【課題】符号化をより高速に行うことができるようにする。【解決手段】レジスタ展開部１５１は、ビットモデリング部１１１から出力されたデータ群をレジスタに展開する。データ統合部１５２は、レジスタに展開された入力データを、バッファ部１５３に保持されているバッファデータと統合する。データ統合部１５２は、バッファデータを読み出し、データ統合部１５２は、入力データをバッファ部１５３に保持させる。整列部１５４は、読みだされたデータを並び替え、有効なデータと無効なデータを分離する。MQ符号化実行部１５５は、有効なデータに対して確率推定テーブル１５６を参照しながらMQ符号化を施す。本発明は、例えば、画像符号化装置に適用することができる。【選択図】図８
2011091577.tif 000002
【特許請求の範囲】
【請求項１】
画像データをウェーブレット変換して得られるサブバンド毎の係数データに対して符号化のビットモデリングを行うビットモデリング手段と、
前記ビットモデリング手段により得られる、シンボル、コンテキスト、および制御情報よりなる複数のデータセットを入力データとしてレジスタに展開する展開手段と、
前記展開手段により展開された前記入力データをバッファデータとして保持する保持手段と、
前記展開手段により展開されている前記入力データの中の前記制御情報が有効な前記データセットと、前記保持手段に保持されている前記バッファデータの中の前記制御情報が有効な前記データセットとを統合する統合手段と、
前記統合手段により統合された前記制御情報が有効な前記データセットを符号化する符号化手段と
を備える符号化装置。
【請求項２】
前記統合手段は、前記バッファデータの中の前記制御情報が無効なデータセットを検出し、前記入力データの中の前記制御情報が有効なデータセットのうち、前記バッファデータにおいて検出された前記データセットと同じ位置のデータセットを、前記バッファデータの同じ位置に移動させることにより、前記制御情報が有効な前記データセットの統合を行う
請求項１に記載の符号化装置。
【請求項３】
前記統合手段により前記データセットが統合された後、前記入力データに前記制御情報が有効な前記データセットが含まれる場合、前記保持手段から前記バッファデータを読み出す読み出し手段をさらに備え、
前記符号化手段は、前記読み出し手段により読み出された前記バッファデータの中の前記制御情報が有効な前記データセットを符号化し、
前記保持手段は、前記読み出し手段により前記バッファデータが読み出された後、前記レジスタに展開されている前記入力データを新たなバッファデータとして保持する
請求項１に記載の符号化装置。
【請求項４】
前記読み出し手段により前記保持手段から読み出された前記バッファデータを並べ替え、前記制御情報が有効な前記データセットをまとめる整列手段をさらに備え、
前記符号化手段は、前記整列手段により並べ替えられてまとめられた前記制御情報が有効な前記データセットを符号化する
請求項３に記載の符号化装置。
【請求項５】
前記符号化手段は、前記統合手段により統合された前記制御情報が有効な、互いに異なる前記データセットに対する複数の符号化を並列に行う
請求項１に記載の符号化装置。
【請求項６】
前記展開手段は、複数のコードブロックのそれぞれの、互いに同じ位置のサンプルに対応する前記データセットを前記入力データとして前記レジスタに展開する
請求項１に記載の符号化装置。
【請求項７】
複数の前記コードブロックを、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けするグループ分け手段をさらに備え、
前記展開手段は、前記グループ分け手段により生成されたグループ毎に、グループ内の各コードブロックの互いに同じ位置のサンプルに対応する前記データセットを前記入力データとして前記レジスタに展開する
請求項１に記載の符号化装置。
【請求項８】
前記グループ分け手段は、前記コードブロックの水平サイズおよび垂直サイズ、前記コードブロックにおいて用いられる符号化パスの数を示す符号化パス数、並びに、前記コードブロックが属するサブバンドタイプを含む、前記コードブロックの特徴を示すパラメータに基づいて、前記コードブロックのグループ分けを行う
請求項７に記載の符号化装置。
【請求項９】
前記ビットモデリング手段は、CUパス、SPパス、またはMRパスのいずれかの符号化パスにより符号化を行うことを選択し、選択した符号化パスにより所定の演算を行う
請求項１に記載の符号化装置。
【請求項１０】
前記制御情報は、前記CUパスから送出されたものであって、ランレングス符号化結果が０になる有効・無効情報、ランレングス符号化の結果が１になる有効・無効情報、CU符号化を行うか否かの有効・無効情報、更にSign符号化を行うか否かの有効・無効情報、のいずれかである
請求項９に記載の符号化装置。
【請求項１１】
前記制御情報は、前記SPパスから送出されたものであって、SP符号化を行うか否かの有効・無効情報、Sign符号化を行うか否かの有効・無効情報、のいずれかである
請求項９に記載の符号化装置。
【請求項１２】
前記制御情報は、前記MRパスから送出されたものであって、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の高速化を実現できるかが、鍵であった。
【００１０】
EBCOTの内部構造は、ビットモデリング部とMQ符号化部とに分かれる。ビットモデリングでは、ウェーブレット変換係数または量子化係数をビットプレーン展開して、矩形のコードブロック単位に、符号化パスと呼ばれる３つのエンコード単位に符号化が行われる。各符号化パスでは、必要に応じて所定のパラメータ群がMQ符号化部に出力される。MQ符号化部は、そのパラメータ群を用いて符号語を生成する。
【００１１】
EBCOTの高速化のためには、このビットモデリング部およびMQ符号化部における計算負荷の低減が必要であった。
【００１２】
本発明は、このような状況に鑑みて提案されたものであり、符号化をより高速に行うことができるようにすることを目的とする。
【課題を解決するための手段】
【００１３】
本発明の一側面は、画像データをウェーブレット変換して得られるサブバンド毎の係数データに対して符号化のビットモデリングを行うビットモデリング手段と、前記ビットモデリング手段により得られる、シンボル、コンテキスト、および制御情報よりなる複数のデータセットを入力データとしてレジスタに展開する展開手段と、前記展開手段により展開された前記入力データをバッファデータとして保持する保持手段と、前記展開手段により展開されている前記入力データの中の前記制御情報が有効な前記データセットと、前記保持手段に保持されている前記バッファデータの中の前記制御情報が有効な前記データセットとを統合する統合手段と、前記統合手段により統合された前記制御情報が有効な前記データセットを符号化する符号化手段とを備える符号化装置である。
【００１４】
前記統合手段は、前記バッファデータの中の前記制御情報が無効なデータセットを検出し、前記入力データの中の前記制御情報が有効なデータセットのうち、前記バッファデータにおいて検出された前記データセットと同じ位置のデータセットを、前記バッファデータの同じ位置に移動させることにより、前記制御情報が有効な前記データセットの統合を行うことができる。
【００１５】
前記統合手段により前記データセットが統合された後、前記入力データに前記制御情報が有効な前記データセットが含まれる場合、前記保持手段から前記バッファデータを読み出す読み出し手段をさらに備え、前記符号化手段は、前記読み出し手段により読み出された前記バッファデータの中の前記制御情報が有効な前記データセットを符号化し、前記保持手段は、前記読み出し手段により前記バッファデータが読み出された後、前記レジスタに展開されている前記入力データを新たなバッファデータとして保持することができる。
【００１６】
前記読み出し手段により前記保持手段から読み出された前記バッファデータを並べ替え、前記制御情報が有効な前記データセットをまとめる整列手段をさらに備え、前記符号化手段は、前記整列手段により並べ替えられてまとめられた前記制御情報が有効な前記データセットを符号化することができる。
【００１７】
前記符号化手段は、前記統合手段により統合された前記制御情報が有効な、互いに異なる前記データセットに対する複数の符号化を並列に行うことができる。
【００１８】
前記展開手段は、複数のコードブロックのそれぞれの、互いに同じ位置のサンプルに対応する前記データセットを前記入力データとして前記レジスタに展開することができる。
【００１９】
複数の前記コードブロックを、互いに同一の特徴を有する所定数のコードブロック毎にグループ分けするグループ分け手段をさらに備え、前記展開手段は、前記グループ分け手段により生成されたグループ毎に、グループ内の各コードブロックの互いに同じ位置のサンプルに対応する前記データセットを前記入力データとして前記レジスタに展開することができる。
【００２０】
前記グループ分け手段は、前記コードブロックの水平サイズおよび垂直サイズ、前記コードブロックにおいて用いられる符号化パスの数を示す符号化パス数、並びに、前記コードブロックが属するサブバンドタイプを含む、前記コードブロックの特徴を示すパラメータに基づいて、前記コードブロックのグループ分けを行うことができる。
【００２１】
前記ビットモデリング手段は、CUパス、SPパス、またはMRパスのいずれかの符号化パスにより符号化を行うことを選択し、選択した符号化パスにより所定の演算を行うことができる。
【００２２】
前記制御情報は、前記CUパスから送出されたものであって、ランレングス符号化結果が０になる有効・無効情報、ランレングス符号化の結果が１になる有効・無効情報、CU符号化を行うか否かの有効・無効情報、更にSign符号化を行うか否かの有効・無効情報、のいずれかであるようにすることができる。
【００２３】
前記制御情報は、前記SPパスから送出されたものであって、SP符号化を行うか否かの有効・無効情報、Sign符号化を行うか否かの有効・無効情報、のいずれかであるようにすることができる。
【００２４】
前記制御情報は、前記MRパスから送出されたものであって、MR符号化を行うか否かの有効・無効情報であるようにすることができる。
【００２５】
本発明の一側面は、また、画像データをウェーブレット変換して得られるサブバンド毎の係数データに対して符号化のビットモデリングを行い、前記ビットモデリングにより得られる、シンボル、コンテキスト、および制御情報よりなる複数のデータセットを入力データとしてレジスタに展開し、前記レジスタに展開された前記入力データをバッファデータとして保持部に保持し、前記レジスタに展開されている前記入力データの中の前記制御情報が有効な前記データセットと、前記保持部に保持されている前記バッファデータの中の前記制御情報が有効な前記データセットとを統合し、統合された前記制御情報が有効な前記データセットを符号化する符号化方法である。
【００２６】
本発明の一側面においては、画像データをウェーブレット変換して得られるサブバンド毎の係数データに対して符号化のビットモデリングが行われ、ビットモデリングにより得られる、シンボル、コンテキスト、および制御情報よりなる複数のデータセットが入力データとしてレジスタに展開され、レジスタに展開された入力データがバッファデータとして保持部に保持され、レジスタに展開されている入力データの中の制御情報が有効なデータセットと、保持部に保持されているバッファデータの中の制御情報が有効なデータセットとが統合され、統合された制御情報が有効なデータセットが符号化される。
【発明の効果】
【００２７】
本発明によれば、画像を符号化することができる。特に、より高速に画像を符号化することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明を適用した画像符号化装置の主な構成例を示すブロック図である。
【図２】サブバンドの構成例を示す図である。
【図３】ビットプレーンの例を説明する図である。
【図４】各サブバンド中のコードブロックの例を示す図である。
【図５】符号化パスの例を説明する図である。
【図６】係数の走査の例を説明する図である。
【図７】符号化パスについて説明する図である。
【図８】図１のEBCOTの詳細な構成例を示すブロック図である。
【図９】ビットモデリングとMQ符号化との関係を説明する図である。
【図１０】符号化処理の流れの例を説明するフローチャートである。
【図１１】ビットモデリング処理の流れの例を説明するフローチャートである。
【図１２】CUパス処理の流れの例を説明するフローチャートである。
【図１３】CUパス処理の流れの例を説明する、図１２に続くフローチャートである。
【図１４】CUパス処理の実際に動作が発生する処理の例について説明するフローチャートである。
【図１５】CUパス処理の実際に動作が発生する処理の、他のについて説明するフローチャートである。
【図１６】CUパス処理の実際に動作が発生する処理の、さらに他のについて説明するフローチャートである。
【図１７】SPパス処理の流れの例を説明するフローチャートである。
【図１８】MRパス処理の流れの例を説明するフローチャートである。
【図１９】MQ符号化処理の流れの例を説明するフローチャートである。
【図２０】データ群のレジスタへの展開の様子を説明する図である。
【図２１】データ群のレジスタへの展開の様子を説明する図である。
【図２２】レジスタに展開されたデータ群の構成例を説明する図である。
【図２３】統合の様子の例を説明する図である。
【図２４】統合の様子の例を説明する図である。
【図２５】データ群の並び替えの様子を説明する図である。
【図２６】本発明を適用した画像符号化装置の他の構成例を示すブロック図である。
【図２７】コードブロックのグループ化の様子の例を説明する図である。
【図２８】MQ符号化の並列処理の様子の例を説明する図である。
【図２９】MQ符号化処理の流れの、他の例を説明するフローチャートである。
【図３０】MQ符号化処理の流れの他の例を説明する、図２９に続くフローチャートである。
【図３１】本発明を適用するハードウェアの例を示す図である。
【図３２】本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００２９】
以下、発明を実施するための形態（以下実施の形態とする）について説明する。なお、説明は以下の順序で行う。
１．第１の実施の形態（画像符号化装置）
２．第２の実施の形態（画像符号化装置）
３．第３の実施の形態（パーソナルコンピュータ）
【００３０】
＜１．第１の実施の形態＞
［画像符号化装置の構成］
図１は、本発明を適用した画像符号化装置の一実施の形態の構成を表している。図１に示される画像符号化装置１００は、画像データをJPEG（Joint Photographic Experts Group）2000の方式で、可逆または非可逆に、符号化する符号化装置である。
【００３１】
画像符号化装置１００は、画像データをウェーブレット変換し、得られた係数を、コードブロック毎にビットプレーンに展開し、ビットプレーン毎にエントロピ符号化する。
【００３２】
画像符号化装置１００は、特にJPEG2000規格で定められたEBCOT(Embedded Coding with Optimized Truncation)と呼ばれるエントロピ符号化を行う（参考文献：IS0/IEC 15444-1, Information technology-JPEG 2000, Part 1:Core coding system）。
【００３３】
このEBCOT（Embedded Block Coding with Optimized Truncation）と呼ばれるエントロピ符号化は、ビットプレーン展開されたバイナリデータを１ピクセル単位にモデリングしながら算術符号化する技術である。
【００３４】
従来、この処理は、逐次処理を行う上、上位のビットプレーンの結果が下位のビットプレーンの結果に影響する「依存性」が存在するため、コードブロック内部の並列化が困難とされてきた。つまり、大きな解像度の画像のエンコードや可逆圧縮の場合、如何にしてJPEG2000の計算負荷、特にEBCOTの高速化を実現できるかが、鍵であった。
【００３５】
そこで、画像符号化装置１００は、EBCOTにおいて、ビットモデリング結果に関わらず、MQ符号化（算術符号化）を実行するようにすることにより、符号化パス内での条件分岐の削除を実現する。また、画像符号化装置１００は、制御情報が有効なシンボルやコンテキストを統合することにより、有効なデータのみを効率よくMQ符号化する。これにより、画像符号化装置１００は、EBCOTの高速化、すなわち、JPEG2000の計算負荷の軽減を実現することができる。
【００３６】
図１に示されるように、画像符号化装置１００は、ウェーブレット変換部１０１、量子化部１０２、ビットプレーン展開部１０３、コードブロック化部１０４、EBCOT１０５、および符号化コードストリーム生成部１０６を有する。
【００３７】
ウェーブレット変換部１０１は、通常、低域フィルタと高域フィルタから構成されるフィルタバンクによって実現される。また、デジタルフィルタは通常複数タップ長のインパルス応答（フィルタ係数）を有するので、ウェーブレット変換部１０１は、フィルタリングが行えるだけの入力画像を予めバッファリングするバッファを有する。
【００３８】
ウェーブレット変換部１０１は、入力された画像データ（矢印１２１）を、フィルタリングに最低限必要なデータ量以上取得する。ウェーブレット変換部１０１は、その画像データに対して、例えば５×３ウェーブレット変換フィルタを用いてフィルタリングを行い、ウェーブレット係数を生成する。なお、ウェーブレット変換部１０１は、画像の垂直方向および水平方向のそれぞれに対して、画像データを低域成分と高域成分に分離するフィルタリングを行う。
【００３９】
そして、ウェーブレット変換部１０１は、このようなフィルタリング処理を、図２に示されるように、垂直方向および水平方向の両方において低域成分として分離されたサブバンドに対して再帰的に所定回数繰り返す。これは、画像のエネルギーの多くが低域成分に集中しているからである。
【００４０】
図２は、分割レベル数３のウェーブレット変換処理により生成されるサブバンドの構成例を示す図である。この場合、ウェーブレット変換部１０１は、まず、画像全体をフィルタリングし、サブバンド3LL（図示せず）、3HL、3LH、および3HHを生成する。次に、ウェーブレット変換部１０１は、生成されたサブバンド3LLに対して再度フィルタリングを行い、2LL（図示せず）、2HL、2LH、および2HHを生成する。さらに、ウェーブレット変換部１０１は、生成されたサブバンド2LLに対して再度フィルタリングを行い、1LL、1HL、1LH、および1HHを生成する。
【００４１】
なお、ウェーブレット変換の分割レベル数は任意である。
【００４２】
図１に戻り、ウェーブレット変換部１０１は、フィルタリングにより得られた係数データ（ウェーブレット係数）を、サブバンド毎に、量子化部１０２に供給する（矢印１２２）。
【００４３】
量子化部１０２は、供給された係数データ（ウェーブレット係数）を量子化する。量子化部１０２は、得られた係数データ（量子化係数）を、ビットプレーン展開部１０３に供給する（矢印１２３）。なお、JPEG2000の規格では、可逆圧縮の場合、量子化処理は省略される。その場合、ウェーブレット変換部１０１より出力された係数データ（ウェーブレット係数）は、ビットプレーン展開部１０３に供給される（矢印１２４）。
【００４４】
ビットプレーン展開部１０３は、供給された係数データを、ビットの位毎のビットプレーンに展開する。
【００４５】
ビットプレーンは、所定の数のウェーブレット係数よりなる係数群（例えば後述するコードブロック）を、１ビット毎、つまり位毎に分割（スライス）したものである。つまり、ビットプレーンは、それぞれが複数ビットのビット深度を持つ複数のデータの、互いに同一の位のビット（係数ビット）の集合である。したがって、展開されるビットプレーン数は、各係数のビット深度に依存する。
【００４６】
図３にその具体例を示す。図３の左図は縦４個、横４個の計１６個の係数を示している。この１６個の係数のうち、絶対値が最大のものは１３で、２進数で１１０１と表現される。ビットプレーン展開部１０３は、このような係数群を、絶対値を示す４枚のビットプレーン（絶対値のビットプレーン）と、符号を示す１枚のビットプレーン（符号のビットプレーン）に展開する。つまり、図３中左の係数群は、図３中右に示されるように、４枚の絶対値のビットプレーンと１枚の符号のビットプレーンに展開される。ここで、絶対値のビットプレーンの要素はすべて０か１の値をとる。また、符号を示すビットプレーンの要素は、係数の値が正であることを示す値、係数の値が０であることを示す値、または係数の値がマイナスを示す値のいずれかをとる。
【００４７】
なお、このようにビットプレーンとされる係数群における係数の数は任意である。以下においては、処理単位を統一することで各部における処理を容易にするために、ビットプレーン展開部１０３が、係数をコードブロック毎にビットプレーン展開するものとして説明する。
【００４８】
図１に戻り、ビットプレーン展開部１０３は、このように展開したビットプレーンを、係数の最上位ビット（MSB：Most Significant Bit）から最下位ビット（LSB：Less Significant Bit）に向かう順に、コードブロック化部１０４に供給する。つまり、ビットプレーン展開部１０３は、ビット深度の上位側から下位側に向かう順に、展開したビットプレーンをコードブロック化部１０４に供給する（矢印１２５）。
【００４９】
コードブロック化部１０４は、供給された各ビットプレーンの係数データを、予め定められた所定の大きさの矩形の、エントロピ符号化の処理単位であるコードブロックに分割する。JPEG2000の規格上の定義によって、コードブロックの縦・横サイズはどのサブバンドにおいても一定である。但し画像（サブバンド）の両端や上端・下端などでは、同じサイズのコードブロックが取れないケースも多々ある。
【００５０】
図４は、図２を参照して説明した各サブバンド中のコードブロックの位置関係を示したものである。例えば64×64画素程度のサイズのコードブロックが、分割後のすべてのサブバンド中に生成される。例えば、最も分割レベルが小さい3HHのサブバンドの大きさが例えば640×320画素であるとすると、64×64画素のコードブロックは合計５０個存在することになる。後段の各処理部は、このコードブロック毎に処理を行う。もちろん、このコードブロックのサイズ（画素数）は任意である。
【００５１】
図１に戻り、コードブロック化部１０４は、ビットプレーン展開された係数データをコードブロック毎にEBCOT１０５に供給する（矢印１２６）。
【００５２】
EBCOT１０５は、所定の大きさのブロック毎にそのブロック内の係数の統計量を測定しながら符号化を行う。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）×３−２    ・・・（１）
【００６６】
図１に示されるように、EBCOT１０５は、ビットモデリングを行うビットモデリング部１１１と、算術符号化を行うMQ符号化部１１２とを有する。ビットモデリング部１１１は、ビットモデリングを行うと、制御情報、シンボル、およびコンテキスト等の情報をMQ符号化部１１２に供給する（矢印１２７）。MQ符号化部１１２は、供給されたデータ群を用いてMQ符号化を行う。MQ符号化部１１２は、MQ符号化により生成された符号化データを符号化コードストリーム生成部１０６に供給する（矢印１２８）。
【００６７】
符号化コードストリーム生成部１０６は、EBCOT１０５（MQ符号化部１１２）から供給された符号化データを整列し、１つのコードストリームとして出力する（矢印１２９）。
【００６８】
図８は、図１のEBCOT１０５の詳細な構成例を示すブロック図である。
【００６９】
図８に示されるように、EBCOT１０５のビットモデリング部１１１は、選択部１４１、CUパス部１４２、SPパス部１４３、MRパス部１４４、および切り替え部１４５を有する。
【００７０】
選択部１４１は、コードブロック化部１０４から供給される係数データ（矢印１７１）の供給先を、CUパス部１４２乃至MRパス部１４４の中から１つ選択し、その選択した先に係数データを供給する。
【００７１】
例えば、選択部１４１は、CUパス部１４２を選択した場合、そのCUパス部１４２に係数データを供給する（矢印１７２）。また、例えば、選択部１４１は、SPパス部１４３を選択した場合、そのSPパス部１４３に係数データを供給する（矢印１７３）。さらに、例えば、選択部１４１は、MRパス部１４４を選択した場合、そのMRパス部１４４に係数データを供給する（矢印１７４）。
【００７２】
CUパス部１４２乃至MRパス部１４４は、それぞれの符号化パスにより係数データに対して所定の演算を行い、符号化する。CUパス部１４２乃至MRパス部１４４は、それぞれ、演算結果として、制御情報、シンボル、およびコンテキスト等のデータ群を切り替え部１４５に供給する（矢印１７５乃至矢印１７７）。
【００７３】
切り替え部１４５は、入力される符号化パスを適宜切り替え、CUパス部１４２乃至MRパス部１４４から供給されるデータ群を、MQ符号化部１１２のレジスタ展開部１５１に供給する（矢印１７８）。
【００７４】
つまり、各符号化パスからは、後述の（有効・無効を示す制御情報、シンボル、コンテキスト）のデータセットが出力され、レジスタ展開部１５１に、選択データとして供給される。
【００７５】
図９に示されるように、一般的なJPEG2000の場合、MQ符号化部１１２は、ビットモデリング部１１１から送出されるシンボルＸ（０または１）とコンテキスト（符号化パスによって取る値が異なる（０乃至１８））を一対で取得し、これらを基にしてMQ符号化を行う。
【００７６】
図８に戻り、EBCOT１０５のMQ符号化部１１２は、レジスタ展開部１５１、データ統合部１５２、バッファ部１５３、整列部１５４、MQ符号化実行部１５５、および確率推定テーブルを有する。
【００７７】
レジスタ展開部１５１は、供給されたデータセット群をデータ統合部１５２に供給し（矢印１７９）、レジスタに展開する。データ統合部１５２は、レジスタに展開されたデータを、バッファ部１５３に保持されているデータと統合する（矢印１８０および矢印１８１）。
【００７８】
バッファ部１５３は、過去にレジスタに展開されたデータセット群を保持する。また、上述したように行われるデータの統合結果を保持する（保持しているデータセット群が、データの統合により適宜更新される）。後述するように、レジスタの有効なデータをバッファ部１５３のデータに全て統合できない場合、データ統合部１５２は、バッファ部１５３からデータセット群を読み出し（矢印１８１）、整列部１５４に供給する（矢印１８２）。また、データ統合部１５２は、バッファ部１５３からデータセット群を読み出した後、レジスタに展開されているデータセット群をバッファ部１５３に保持させる（矢印１８０）。
【００７９】
整列部１５４は、供給されたデータセット群を並び替え、制御情報が有効なデータと無効なデータを分離する（有効なデータをまとめる）。整列部１５４は、有効なデータをMQ符号化実行部１５５に供給する（矢印１８３）。
【００８０】
MQ符号化実行部１５５は、供給されたデータに対して、通常のJPEG2000で規定された確率推定テーブル１５６を参照しながら（矢印１８４）MQ符号化を施すことで、符号化データを生成する。MQ符号化実行部１５５は、生成した符号化データを符号化コードストリーム生成部１０６に供給する（矢印１８５）。
【００８１】
［処理の流れ］
次に、このような画像符号化装置１００により実行される符号化処理の流れの例を図１０のフローチャートを参照して説明する。
【００８２】
符号化処理が開始されると、ウェーブレット変換部１０１は、ステップＳ１０１において、１ピクチャ分の画像データをウェーブレット変換する。ステップＳ１０２において、量子化部１０２は、ステップＳ１０１において生成された係数データを量子化する。なお、可逆符号化の場合、このステップＳ１０２の処理は省略される。
【００８３】
ステップＳ１０３において、ビットプレーン展開部１０３は、係数データをビットプレーン展開する。ステップＳ１０４において、コードブロック化部１０４は、係数データをコードブロック化する。
【００８４】
ステップＳ１０５において、EBCOT１０５のビットモデリング部１１１は、ビットモデリング処理を実行する。ステップＳ１０６において、EBCOT１０５のMQ符号化部１１２は、MQ符号化処理を行う。
【００８５】
ステップＳ１０７において、符号化コードストリーム生成部１０６は、EBCOT１０５において生成された符号化データを整列してコードストリームを生成し、出力する。ステップＳ１０７の処理が終了すると、符号化処理が終了される。
【００８６】
なお、この符号化処理は、ピクチャ毎に行われる。
【００８７】
次に、図１１のフローチャートを参照して、図１０のステップＳ１０５において行われるビットモデリング処理の詳細な流れの例について説明する。
【００８８】
ビットモデリング処理が開始されると、ステップＳ１２１において、選択部１４１は、符号化パスを選択する。ステップＳ１２２において、選択部１４１は、CUパスを選択したか否かを判定する。
【００８９】
CUパスを選択したと判定された場合、ステップＳ１２３に進む。ステップＳ１２３において、CUパス部１４２は、CUパスにより符号化を行うCUパス処理を実行する。CUパス処理が終了すると、ステップＳ１２７に進む。
【００９０】
また、ステップＳ１２２において、CUパスを選択していないと判定された場合、ステップＳ１２４に進む。ステップＳ１２４において、選択部１４１は、SPパスを選択したか否かを判定する。
【００９１】
SPパスを選択したと判定された場合、ステップＳ１２５に進む。ステップＳ１２５において、SPパス部１４３は、SPパスにより符号化を行うSPパス処理を実行する。SPパス処理が終了すると、ステップＳ１２７に進む。
【００９２】
また、ステップＳ１２４において、SPパスを選択していないと判定された場合、ステップＳ１２６に進む。ステップＳ１２６において、MRパス部１４４は、MRパスにより符号化を行うMRパス処理を実行する。MRパス処理が終了すると、ステップＳ１２７に進む。
【００９３】
ステップＳ１２７において、ビットモデリング部１１１は、ビットモデリング処理を終了するか否かを判定する。未処理の係数データが存在し、ビットモデリング処理を終了しないと判定された場合、ステップＳ１２１に戻り、それ以降の処理が繰り返される。また、ステップＳ１２７において、ピクチャ内の全ての係数データを処理したと判定された場合、ビットモデリング処理を終了し、図１０のステップＳ１０５に戻り、ステップＳ１０６以降の処理を実行する。
【００９４】
次に、図１１のステップＳ１２３において実行されるCUパス処理の流れの例を、図１２および図１３のフローチャートを参照して説明する。なお、スプライトの横サイズを６４、縦サイズを４とする。また、図１２および図１３において、点線矢印は、データの依存関係を示す。
【００９５】
CUパスでは、スプライト内の縦方向の係数群（図６の例の場合、４係数）が上から下方向の順番に走査されながら、この係数群（４係数）毎に以下の計算（ステップＳ１４１乃至ステップＳ１４８）が行われる。
【００９６】
ステップＳ１４１において、CUパス部１４２は、ランレングス符号化（RLC（Run length coding））の結果が０である計算を行う。この計算が成功した場合、計算結果は0xFF（以下、FFと称する）となる。また、この計算が失敗した場合、計算結果は0x00（以下00と称する）となる。これらの計算結果は、ステップＳ１４５の処理に影響を与える。
【００９７】
ステップＳ１４１の処理が終了するとステップＳ１４２に進む。ステップＳ１４２において、CUパス部１４２は、ランレングス符号化（RLC（Run length coding））の結果が１である計算を行う。この計算が成功した場合、計算結果はFFとなる。また、この計算が失敗した場合、計算結果は00となる。これらの計算結果は、ステップＳ１４６乃至ステップＳ１４８の処理に影響を与える。
【００９８】
ステップＳ１４２の処理が終了するとステップＳ１４３に進む。ステップＳ１４３において、CUパス部１４２は、１番目のUNIFORMエンコードの計算を行う。エンコード対象は０または１である。この計算結果は、ステップＳ１４７の処理に影響を与える。
【００９９】
ステップＳ１４３の処理が終了するとステップＳ１４４に進む。ステップＳ１４４において、CUパス部１４２は、２番目のUNIFORMエンコードの計算を行う。エンコード対象は０または１である。この計算結果は、ステップＳ１４８の処理に影響を与える。
【０１００】
CUパスの処理において、ステップＳ１４１における、RLCの処理を実行するか否かが最初の分岐点である。ただし、図１２に示されるように、本発明においては、RLCの結果が１である計算と０である計算のいずれも行う。そしてその結果（FFまたは00）を見ることで、MQ符号化部１１２は、実際にRLCが有効であったか否かを自動的に判別することができる。
【０１０１】
ステップＳ１４４の処理が終了するとステップＳ１４５に進む。CUパス部１４２は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、ステップＳ１４５において、RLCコンテキストで値０をMQ符号化させ、ステップＳ１４６において、RLCコンテキストで値１をMQ符号化させる。
【０１０２】
また、CUパス部１４２は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、ステップＳ１４７において、UNIFORMコンテキストで１回目のMQ符号化を行わせ、ステップＳ１４８において、UNIFORMコンテキストで２回目のMQ符号化を行わせる。
【０１０３】
図１２のステップＳ１４８の処理が終了すると、図１３のステップＳ１６１に進む。CUパスでは、上述した係数群（４係数）内の各係数に対して以下の計算（ステップＳ１６１乃至ステップＳ１６６）が行われる。
【０１０４】
ステップＳ１６１において、CUパス部１４２は、CUエンコードを行うか否かの計算を行う。例えば、CUエンコードを行う場合、計算結果はFFとなり、CUエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ１６３のMQ符号化に用いられる。
【０１０５】
ステップＳ１６１の処理が終了するとステップＳ１６２に進む。ステップＳ１６２において、CUパス部１４２は、Significanceコンテキストの計算を行う。CUパス部１４２は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、ステップＳ１６３において、SignificanceコンテキストでSymbolをMQ符号化させる。
【０１０６】
ステップＳ１６３の処理が終了するとステップＳ１６４に進む。ステップＳ１６４において、CUパス部１４２は、Signエンコードするか否かの計算を行う。例えば、Signエンコードを行う場合、計算結果はFFとなり、Signエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ１６６のMQ符号化に用いられる。
【０１０７】
ステップＳ１６４の処理が終了するとステップＳ１６５に進む。ステップＳ１６５において、CUパス部１４２は、Signコンテキストの計算を行う。CUパス部１４２は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、ステップＳ１６６において、SignコンテキストでSignをMQ符号化させる。
【０１０８】
ステップＳ１６７において、CUパス部１４２は、処理対象の係数群（４係数）内の全ての係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ１６１に戻り、それ以降の処理を繰り返す。
【０１０９】
また、ステップＳ１６７において、処理対象の係数群（４係数）内の全ての係数が処理されたと判定された場合、ステップＳ１６８に進む。ステップＳ１６８において、CUパス部１４２は、処理対象ビットプレーンの全てのスプライトの全係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、図１２のステップＳ１４１に戻り、それ以降の処理を繰り返す。
【０１１０】
また、図１３のステップＳ１６８において、全ての係数を処理したと判定された場合、CUパス処理が終了され、図１１のステップＳ１２３に戻り、ステップＳ１２７以降の処理が行われる。
【０１１１】
以上のCUパス処理において、例えば、RLCの結果が１である計算を行って（ステップＳ１４２）、その結果出力される符号がFFの場合、その計算が有効であったことを示している。尚、この場合には、RLCの結果が０である計算を行っても（ステップＳ１４１）、その計算結果は00（無効）であることは自明である。（結果が１と０は背反なため）。
【０１１２】
また、以上のRLCの結果が１である計算が有効だった場合、UNIFORMエンコードの計算が２回に渡って実行されるが、いずれの場合でもエンコード対象は０または１である。また、以上の２つのケース以外のケースとしてRLCを一切行わないモードも存在する。
【０１１３】
以下に３つのケースについて、図１１のステップＳ１４１乃至ステップＳ１４８の各処理の実行の様子を説明する。
【０１１４】
最初に、図１４を参照し、RLCの結果が０の場合の、実際に動作が発生する処理について説明する。
【０１１５】
≪ケース１（RLCの結果が０の場合≫
（１）RLCの結果が０である計算を実行する（ステップＳ１４１）と、その結果はFFになる。
（２）RLCの結果が１である計算を実行する（ステップＳ１４２）と、その結果は00になる。
（３）１番目のUNIFORMエンコードの計算を実行しても（ステップＳ１４３）、その符号語は発生しない。
（４）２番目のUNIFORMエンコードの計算を実行しても（ステップＳ１４４）、その符号語は発生しない。
（５）RLCコンテキストで値０をMQ符号化させて（ステップＳ１４５）、符号語を出力する。
（６）RLCコンテキストで値１をMQ符号化させても（ステップＳ１４６）、符号語は発生しない。
（７）UNIFORMコンテキストでMQ符号化を行わせても（１番目）（ステップＳ１４７）、符号語は発生しない。
（８）UNIFORMコンテキストでMQ符号化を行わせても（２番目）（ステップＳ１４８）、符号語は発生しない。
【０１１６】
以上のように、このケース１の場合、RLCの結果が０になったサンプルに対して、RLCコンテキストを用いて、この０という値をMQ符号化させる。この時にMQ符号化部１１２に入力されるデータは、上記のRLCコンテキスト、シンボル（０）、および制御情報（FF）の３つである。
【０１１７】
次に、図１５を参照し、RLCの結果が１の場合の、実際に動作が発生する処理について説明する。
【０１１８】
≪ケース２（RLCの結果が１の場合）≫
（１）RLCの結果が０である計算を実行する（ステップＳ１４１）と、その結果は00になる。
（２）RLCの結果が１である計算を実行する（ステップＳ１４２）と、その結果はFFになる。
（３）１番目のUNIFORMエンコードの計算を実行して（ステップＳ１４３）、符号語を発生させる。
（４）２番目のUNIFORMエンコードの計算を実行して（ステップＳ１４４）、符号語を発生させる。
（５）RLCコンテキストで値０をMQ符号化させても（ステップＳ１４５）、符号語は発生しない。
（６）RLCコンテキストで値１をMQ符号化させて（ステップＳ１４６）、符号語を出力する。
（７）UNIFORMコンテキストでMQ符号化を行わせて（１番目）（ステップＳ１４７）、符号語を出力する。
（８）UNIFORMコンテキストでMQ符号化を行わせて（２番目）（ステップＳ１４８）、符号語を出力する。
【０１１９】
以上のように、このケース２の場合、RLCの結果が１になったサンプルに対して、RLCコンテキストを用いて、この１という値をMQ符号化させる。またこの時には、１番目と２番目のUNIFORMエンコードも同時に行うので、各々UNIFORMコンテキストを用いて、０または１の値をMQ符号化させる。従って、このケース２では、３つのMQ符号化を動作させ、MQ符号化部１１２に入力されるデータは、上記のRLCコンテキスト、シンボル（１）、および制御情報（FF）であるか、１番目のUNIFORMコンテキスト、シンボル（０または１）、および制御情報（FF）であるか、２番目のUNIFORMコンテキスト、シンボル（０または１）、および制御情報（FF）である。
【０１２０】
次に、図１６を参照し、RLCを行わない場合の、実際に動作が発生する処理について説明する。
【０１２１】
≪ケース３（RLCを行わない場合）≫
（１）RLCの結果が０である計算を実行する（ステップＳ１４１）と、その結果は00になる。
（２）RLCの結果が１である計算を実行する（ステップＳ１４２）と、その結果は00になる。
（３）１番目のUNIFORMエンコードの計算を実行しても（ステップＳ１４３）、符号語は発生しない。
（４）２番目のUNIFORMエンコードの計算を実行しても（ステップＳ１４４）、符号語は発生しない。
（５）RLCコンテキストで値０をMQ符号化させても（ステップＳ１４５）、符号語は発生しない。
（６）RLCコンテキストで値１をMQ符号化させても（ステップＳ１４６）、符号語は発生しない。
（７）UNIFORMコンテキストでMQ符号化を行わせても（１番目）（ステップＳ１４７）、符号語は発生しない。
（８）UNIFORMコンテキストでMQ符号化を行わせても（２番目）（ステップＳ１４８）、符号語は発生しない。
【０１２２】
以上のように、RLCが行われない場合、ステップＳ１４１乃至ステップＳ１４８の各処理が行われるが、実際に符号語を発生する処理は存在しない。これは、従来のCUパス処理においてRLCを行わない場合と同様である。
【０１２３】
なお、付言するに、EBCOT１０５は、上述したように、各係数に対する処理（図１３のステップＳ１６１乃至ステップＳ１６６）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
【０１２４】
また、CUエンコードを行うか否かの計算結果がFFだった場合、Significanceコンテキストを用いて、そのサンプルのシンボルがMQ符号化される。同様に、Signエンコードするか否かの結果がFFだった場合、Signコンテキストを用いて、そのサンプルのシンボルがMQ符号化される。
【０１２５】
以上のように、図８のビットモデリング部１１１でCUパスが選択された場合、ストライプに対しては上記のケース１乃至ケース３のいずれか１つのデータ群（コンテキスト、シンボル、制御情報）がレジスタに展開され、サンプル毎に対しては上記のSignificance及びSignの情報（コンテキスト、シンボル、制御情報）が、レジスタに展開される。
【０１２６】
次に、図１１のステップＳ１２５において実行されるSPパス処理の流れの例を、図１７のフローチャートを参照して説明する。なお、点線矢印は、データの依存関係を示す。
【０１２７】
SPパス処理が開始されると、ステップＳ１８１において、SPパス部１４３は、SPエンコードを行うか否かの計算を行う。例えば、SPエンコードを行う場合、計算結果はFFとなり、SPエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ１８３のMQ符号化に用いられる。
【０１２８】
ステップＳ１８１の処理が終了するとステップＳ１８２に進む。ステップＳ１８２において、SPパス部１４３は、Significanceコンテキストの計算を行う。ステップＳ１８３において、SPパス部１４３は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、SignificanceコンテキストでSymbolをMQ符号化させる。
【０１２９】
ステップＳ１８３の処理が終了するとステップＳ１８４に進む。ステップＳ１８４において、SPパス部１４３は、係数が１であるか否かの計算を行う。例えば、係数が１である場合、計算結果はFFとなり、係数が０である場合、計算結果は00となる。この計算結果は、ステップＳ１８６のMQ符号化に用いられる。
【０１３０】
ステップＳ１８４の処理が終了するとステップＳ１８５に進む。ステップＳ１８５において、SPパス部１４３は、Signコンテキストの計算を行う。ステップＳ１８６において、SPパス部１４３は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、SignコンテキストでSignをMQ符号化する。
【０１３１】
ステップＳ１８７において、SPパス部１４３は、処理対象の係数群（４係数）内の全ての係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ１８１に戻り、それ以降の処理を繰り返す。
【０１３２】
また、ステップＳ１８７において、処理対象の係数群（４係数）内の全ての係数が処理されたと判定された場合、ステップＳ１８８に進む。ステップＳ１８８において、SPパス部１４３は、処理対象ビットプレーンの全てのスプライトの全係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ１８１に戻り、それ以降の処理を繰り返す。
【０１３３】
また、ステップＳ１８８において、全ての係数を処理したと判定された場合、SPパス処理が終了され、図１１のステップＳ１２５に戻り、ステップＳ１２７以降の処理が行われる。
【０１３４】
このSPパス処理の場合も、CUパスの場合と同様に、各係数に対する処理（図１７のステップＳ１８１乃至ステップＳ１８６）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
【０１３５】
また、SPエンコードするか否かの計算結果がFFだった場合、Significanceコンテキストを用いて、そのサンプルのシンボルがMQ符号化される。同様に、Signエンコードするか否かの計算結果がFFだった場合、Signコンテキストを用いて、そのサンプルのシンボルがMQ符号化される。
【０１３６】
以上のように、図８のビットモデリング部１１１においてSPパスが選択された場合、ストライプに対しては、符号発生は無く、サンプル毎に対しては上記のSignificance及びSignの情報（コンテキスト、シンボル、制御情報）が、レジスタに展開される。
【０１３７】
次に、図１１のステップＳ１２６において実行されるMRパス処理の流れの例を、図１８のフローチャートを参照して説明する。なお、点線矢印は、データの依存関係を示す。
【０１３８】
MRパス処理が開始されると、ステップＳ２０１において、MRパス部１４４は、MRエンコードを行うか否かの計算を行う。例えば、MRエンコードを行う場合、計算結果はFFとなり、MRエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ２０３のMQ符号化に用いられる。
【０１３９】
ステップＳ２０１の処理が終了するとステップＳ２０２に進む。ステップＳ２０２において、MRパス部１４４は、MRコンテキストの計算を行う。ステップＳ２０３において、SPパス部１４３は、MQ符号化部１１２にデータ（制御情報、シンボル、およびコンテキスト等）を供給することにより、MRコンテキストでSymbolをMQ符号化させる。
【０１４０】
ステップＳ２０３の処理が終了するとステップＳ２０４に進む。ステップＳ２０４において、MRパス部１４４は、処理対象の係数群（４係数）内の全ての係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ２０１に戻り、それ以降の処理を繰り返す。
【０１４１】
また、ステップＳ２０４において、処理対象の係数群（４係数）内の全ての係数が処理されたと判定された場合、ステップＳ２０５に進む。ステップＳ２０５において、MRパス部１４４は、処理対象ビットプレーンの全てのスプライトの全係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ２０１に戻り、それ以降の処理を繰り返す。
【０１４２】
また、ステップＳ２０５において、全ての係数を処理したと判定された場合、MRパス処理が終了され、図１１のステップＳ１２６に戻り、ステップＳ１２７以降の処理が行われる。
【０１４３】
このMRパス処理の場合も、CUパスやSPパスの場合と同様に、各係数に対する処理（図１８のステップＳ２０１乃至ステップＳ２０３）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
【０１４４】
また、MRエンコードするか否かの計算結果がFFだった場合、MRコンテキストを用いて、そのサンプルのシンボルがMQ符号化される。
【０１４５】
以上のように、図８のビットモデリング部１１１でMRパスが選択された場合、ストライプに対して符号発生は無く、サンプル毎に対して上記のMRのデータ（コンテキスト、シンボル、制御情報）がレジスタに展開される。
【０１４６】
次に、以上のような各符号化パスの処理に対応して図１０のステップＳ１０６において実行されるMQ符号化処理の流れの例を、図１９のフローチャートを参照して説明する。必要に応じて、図２０乃至図２５を参照して説明する。
【０１４７】
図８のMQ符号化部１１２は、MQ符号化処理を実行することにより、例えば、図１２のステップＳ１４５乃至ステップＳ１４８、図１３のステップＳ１６３およびステップＳ１６６、図１７のステップＳ１８３およびステップＳ１８６、並びに、図１８のステップＳ２０３の各処理により供給されるデータセット（制御情報、シンボル、およびコンテキスト等）に対するMQ符号化を行う。
【０１４８】
MQ符号化処理が開始されると、レジスタ展開部１５１は、ステップＳ２２１において、ビットモデリング部１１１から供給される、あるコードブロックのあるサンプルのシンボル、コンテキスト、および制御情報等のデータセットを取得する。
【０１４９】
ステップＳ２２２において、レジスタ展開部１５１は、予め定められている所定数（Ｎ個（Ｎは自然数））のコードブロックの全てのサンプル（係数）についてデータセットを取得したか否かを判定する。所定数（Ｎ個）のコードブロック分のデータセットを取得していないと判定された場合、ステップＳ２２１に戻り、それ以降の処理を繰り返す。
【０１５０】
ステップＳ２２２において、所定数（Ｎ個）のコードブロックの全てのサンプルについてデータセットを取得したと判定された場合、ステップＳ２２３に進む。
【０１５１】
ステップＳ２２３において、レジスタ展開部１５１は、データ群を取得した所定数のコードブロックのそれぞれから、処理対象サンプルのシンボル、コンテキスト、および制御情報のデータセットを取得し、それらをレジスタに展開する。このレジスタに展開されたデータセット群を入力データと称する。
【０１５２】
図２０は、そのデータセット群のレジスタへの展開の様子を説明する図である。図２０に示される例の場合、Codeblock0乃至Codeblock15の１６個のコードブロックについてデータセット群が取得され、下段のレジスタに展開される。
【０１５３】
図２０の例の場合、ビットプレーン毎に、各コードブロックの互いに同じ位置のサンプルのデータセット群が読み出され、レジスタに配置される。例えば、Sign bitplaneにおいては、codeblock0から左上のサンプルのデータセット２０１−１が読み出され、codeblock1から左上のサンプルのデータセット２０１−２が読み出され、codeblock3乃至codeblock14においても同様にデータセットの読み出しが行われ、codeblock15から左上のサンプルのデータセット２０１−１６が読み出される。それらのデータセット２０１−１乃至データセット２０１−１６は、レジスタに並べて配置される。
【０１５４】
そして、後述するように、そのレジスタの入力データが処理されると、次に、codeblock0から、右隣のサンプルのデータセット２０２−１が読み出され、codeblock1からも右隣のサンプルのデータセット２０２−２が読み出され、codeblock3乃至codeblock14においても同様に右隣のサンプルのデータセットの読み出しが行われ、codeblock15からも右隣のサンプルのデータセット２０２−１６が読み出される。それらのデータセット２０２−１乃至データセット２０２−１６は、データセット２０１−１乃至データセット２０１−１６と同様にレジスタに並べて配置される。
【０１５５】
この入力データも、データセット２０１−１乃至データセット２０１−１６の場合と同様に処理される。つまり、例えば、図２１に示されるように、CB0乃至CB15の１６個の各コードブロックにおいて、サンプルＸ、サンプルＹ、サンプル０、サンプル０、・・・・のように、各サンプルが互いに同順に処理される。
【０１５６】
図２２は、レジスタに展開された入力データの様子の例を説明する図である。
【０１５７】
図２２に示されるように、レジスタには、１６個のコードブロックの互いに同位置のサンプルのシンボル、コンテキスト、および制御情報が配置されている。したがって、コードブロックの数をＮ個（Ｎは自然数）とし、１つのデータを１バイトとすると、レジスタ長は、（３×Ｎ）バイトとなり、非常に小さいものである。
【０１５８】
図１９に戻り、以上のように入力データがレジスタに展開されると、ステップＳ２２４において、データ統合部１５２は、レジスタに展開された入力データ中の、制御情報が有効なデータをバッファ部１５３に保持されているデータ群（バッファデータ）に統合する。
【０１５９】
ここで、MQ符号化の従来の問題点について述べる。通常MQ符号化で制御情報が無効なシンボル、コンテキストのデータをエンコードすると符号語を発生しない。従って、図２２の例の場合、１６個のデータの内、１３個の無効データはエンコードが無駄になる。従って、無効のデータを予め除去しておくか、エンコードの対象から外しておけば効率的である。
【０１６０】
そこで、まずデータ統合部１５２は、入力データとバッファデータを統合することにより、有効なデータを集約する（有効なデータの密度を高める）。
【０１６１】
図２３に、そのデータの統合の様子の例を示す。図２３において、図中中央の矢印より上の段が、レジスタに展開された時の入力データとバッファデータの状態を示している。
【０１６２】
この上の段において、データ統合部１５２は、まずバッファデータの中で制御情報が無効（00）であるデータを探し、同位置の入力データで制御情報が有効（FF）であるデータを検出する。図２３の例の場合、左端から数えて４番目、７番目、および１３番目の３つのサンプルがこれに該当する。
【０１６３】
そして、データ統合部１５２は、これらの位置の入力データのシンボル、コンテキストのデータを、バッファデータに移動する（統合する）。図２３において図中中央の矢印より下の段が、データ統合後の入力データとバッファデータの状態を示している。
【０１６４】
図２３の下の段に示されるように、移動が行われた位置のバッファデータには、上の段において入力データに存在していた、制御情報が有効（FF）であるデータが配置される。
【０１６５】
その結果、移動が行われた位置の入力データは空になる。つまり、制御情報が無効（00）であるデータとなる。図２３の例の場合、入力データの１６個のサンプルの制御情報は、全て無効となる。したがって、この入力データをMQ符号化する必要が無くなり、破棄することができる。つまり、以上のデータの統合により、MQ符号化実行部１５５は、１回分のMQ符号化処理を省略することができ、MQ符号化の計算負荷が軽減させ、より効率よくMQ符号化を行うことができる。
【０１６６】
なお、実際には、次にレジスタに展開された入力データに対しても同様にバッファデータとの統合が行われる。つまり、データ統合部１５２は、可能な限りデータを統合するので、MQ符号化実行部１５５は、さらにMQ符号化の効率を向上させることができる。
【０１６７】
図１９に戻り、ステップＳ２２５において、データ統合部１５２は、入力データの中に制御情報が有効であるデータが存在するか否かを判定する。存在すると判定された場合、ステップＳ２２６に進む。
【０１６８】
ステップＳ２２６において、データ統合部１５２は、バッファ部１５３からバッファデータを読み出す。
【０１６９】
図２４の例の場合、データ統合後にも入力データに制御情報が有効であるデータが存在する。図２４において、上から１段目の入力データと、上から２段目のバッファデータが、統合前の状態を示し、上から３段目の入力データと、上から４段目のバッファデータが、統合後の状態を示している。
【０１７０】
データ統合前の状態において、入力データにおいては、４番目、７番目、および１３番目のサンプルの制御情報が有効であるが、バッファデータの１３番目のサンプルの制御情報は無効であるので、この位置については、図２３の場合と同様に、データの統合が可能である。
【０１７１】
これに対して、バッファデータの４番目と７番目のサンプルの制御情報が有効であるので、その位置の入力データとバッファデータを統合することはできない。
【０１７２】
したがって、データ統合後の状態においても、入力データの４番目と７番目の制御情報は有効（FF）のままであり、この入力データを破棄することはできない。
【０１７３】
したがって、この場合、データ統合部１５２は、このバッファデータを読み出し、MQ符号化させる。そして、データ統合部１５２は、図２４の一番下の段に示されるように、入力データをバッファ部１５３に保持させ、新たなバッファデータとする。次にレジスタに展開される入力データは、このバッファデータと統合される。
【０１７４】
図１９に戻り、ステップＳ２２７において、整列部１５４は、バッファ部１５３から読みだされたバッファデータの並び替えを行い、制御情報が有効なデータをまとめる。
【０１７５】
図２５は、このデータの整列の様子の例を説明する図である。図２５の上の段が、バッファ部１５３から読みだされた時の状態を示している。整列部１５４は、入力されたこのようなデータにおいて、図２５の下の段に示されるように、制御情報が有効であるサンプルのデータを例えば左によせてまとめる（制御情報が有効なデータと無効なデータを分離する）。
【０１７６】
このとき、図２５に示されるように、順序が並び替えられたデータ群には、制御情報が有効であるデータの数を示す有効データ数の情報が付加される。さらに、実際には、コードストリームにする際に並び替えた順序を元に戻す必要があるので、制御情報が有効であるデータの元の位置（番地）の情報も管理される。
【０１７７】
図１９に戻り、ステップＳ２２８において、MQ符号化実行部１５５は、その制御情報が有効な各データについて、そのコンテキストでそのシンボルをMQ符号化する。
【０１７８】
図２５の例の場合、MQ符号化実行部１５５は、左から有効データ数分のデータ群をMQ符号化すればよい。このようにすることにより、MQ符号化実行部１５５は、制御情報が無効であるデータの符号化を適切に省略することができ、より効率よくMQ符号化を行うことができる。
【０１７９】
図１９に戻り、ステップＳ２２９において、データ統合部１５２は、レジスタの入力データを、バッファ部１５３に供給し、保持させる。ステップＳ２２９の処理を終了すると、ステップＳ２３０に進む。また、ステップＳ２２６において、入力データの中に、制御情報が有効なデータが存在しないと判定された場合、ステップＳ２３０に進む。
【０１８０】
ステップＳ２３０において、レジスタ展開部１５１は、取得した所定数のコードブロックについて、未処理のサンプルが存在するか否かを判定する。未処理のサンプルが存在すると判定された場合、ステップＳ２２３に戻り、それ以降の処理を繰り返す。
【０１８１】
また、ステップＳ２３０において、未処理のサンプルが存在しないと判定された場合、ステップＳ２３１に進む。ステップＳ２３１において、レジスタ展開部１５１は、ピクチャ内に未処理のコードブロックが存在するか否かを判定する。未処理のコードブロックが存在すると判定された場合、ステップＳ２２１に戻り、それ以降の処理を繰り返す。
【０１８２】
また、ステップＳ２３１において、未処理のコードブロックが存在しないと判定された場合、MQ符号化処理を終了し、図１０のステップＳ１０６に戻り、ステップＳ１０７以降の処理を行う。
【０１８３】
以上のように、データ統合部１５２がデータを統合して制御情報が有効であるデータを集め、さらに、整列部１５４が、データの並び替えを行い、制御情報が有効であるデータをまとめることにより、MQ符号化実行部１５５は、制御情報が無効であるデータのMQ符号化を省略することができ、より効率よくMQ符号化を行うことができる。
【０１８４】
これにより、画像符号化装置１００は、より高速に符号化を行うことができる。
【０１８５】
なお、バッファ部１５３が保持するバッファデータの数は任意である。つまり、バッファデータを複数設けるようにしてもよい。このようにすることにより、入力データのバッファデータへの統合がより容易になる。
【０１８６】
例えば、図２４の例のように、入力データに、バッファデータと統合することができなかった、制御情報が有効であるデータが存在する場合であっても、他のバッファデータとの統合ができる可能性がある。
【０１８７】
当然、バッファデータの数を増大させると、その可能性は高くなる。ただし、バッファデータの数を増大させるとバッファ部１５３の容量が増大する。つまり、バッファデータの最適な数は、制御情報が有効なデータの集約率と、例えばコスト等とのトレードオフによって決定される。
【０１８８】
＜２．第２の実施の形態＞
［画像符号化装置の構成］
以上においては、MQ符号化実行部１５５が、バッファ部１５３から読みだされた、制御情報が有効である各データをMQ符号化するように説明したが、さらに高速に符号化処理を行うことができるように、この複数のサンプルに対するMQ符号化を並列に実行することができるようにしてもよい。
【０１８９】
ただし、ピクチャ内には、様々なタイプのコードブロックが存在するので、予め類似したコードブロック同士を集めておき、それらを一気にエンコードする方が効率的である。
【０１９０】
図２６は、本発明を適用したEBCOT１０５の他の構成例を示すブロック図である。図２６に示されるEBCOT１０５は、基本的に図８の場合と同様の構成を有するが、図８のMQ符号化部１１２の代わりに、MQ符号化部３１２を有する。
【０１９１】
MQ符号化部３１２は、MQ符号化部１１２と同様に、MQ符号化処理を行うが、MQ符号化部１１２の場合と異なり、互いに異なるサンプルのデータ群に対する複数のMQ符号化を並列に実行する。
【０１９２】
MQ符号化部３１２は、基本的にMQ符号化部１１２と同様の構成を有するが、整列部１５４の代わりに整列部３２４を有し、MQ符号化実行部１２５の代わりに並列MQ符号化実行部３２５を有し、さらに、並列演算用データ生成部３２１を有する。
【０１９３】
並列演算用データ生成部３２１は、並列に演算（MQ符号化）することができるように、コードブロック群を、コードブロックの特徴を表すパラメータによってグループ分けし、そのグループ毎に各コードブロックのデータ群をレジスタ展開部１５１に供給する。
【０１９４】
つまり、上述したように、レジスタ展開部１５１には複数のコードブロックのデータ群が入力されるが、並列演算用データ生成部３２１は、その複数のコードブロックを、そのパラメータ（特徴）が互いに同一のコードブロックとするように制御する。
【０１９５】
並列演算用データ生成部３２１は、ビットモデリング部１１１から供給される（矢印３３２）データ群を保持し、そのデータ群をコードブロック毎にグループ分けし、そのグループ毎にデータ群をレジスタ展開部１５１に供給する（矢印３３３）。
【０１９６】
このパラメータとしては、コードブロックの特徴を表すものであればどのようなものであってもよいが、例えば、コードブロックの水平サイズ（h_size）、コードブロックの垂直サイズ（v_size）、サブバンドタイプ（LL,HL,LH.HH）、および、後述するように算出される符号化パス数(num_pass)を含むようにしてもよい。符号化パス数(num_pass)は、例えば、上述した式（１）のように算出される。もちろん、これら以外のものがパラメータに含まれていてもよい。
【０１９７】
図２７Ａに示される例のように、ピクチャ内のコードブロックのサイズ（水平サイズおよび垂直サイズ）は全てが同一ではない。上述したように、コードブロック化は基本的に同一のサイズ（基本サイズ）とするように行われるが、画像（サブバンド）の両端や上端・下端等において、その基本サイズを確保できない場合がある。このような部分のコードブロックのサイズは、基本サイズより小さいものとなる。
【０１９８】
また、上述したように、コードブロック化は係数データに対して行われるので、ピクチャ内の各コードブロックが属するサブバンドは全てが同一ではない。さらに、各コードブロックのゼロビットプレーン数（有効ビットプレーン数）は互いに独立しているので、符号化パス数もコードブロック毎に異なる可能性がある。
【０１９９】
並列演算用データ生成部３２１は、ピクチャ内の各コードブロックのパラメータの値を比較し、図２７Ｂに示されるように、全ての値が同一となるコードブロックをグループ化する。
【０２００】
図２７Ｂにおいて、グループ３６１乃至グループ３６４は、それぞれ、このようにパラメータによって分類されたコードブロック群である。換言すれば、各グループにおいて、全てのコードブロックの全パラメータの値は、互いに同一である。
【０２０１】
並列演算用データ生成部３２１は、各グループが最大１６個のコードブロックにより形成されるように、パラメータによって分けたグループを、適宜分割する。図２７Ｃの例に示されるグループ３７１乃至グループ３７６は、図２７Ｂの各グループを、コードブロック数が最大１６個となるように、さらに分割したものの中の一部である。例えば、図２７Ｃのグループ３７１乃至グループ３７３は、図２７Ｂのグループ３６１をさらに分割したものであり、図２７Ｃのグループ３７４およびグループ３７５は、図２７Ｂのグループ３６２をさらに分割したものである。図２７Ｃのグループ３７６は、図２７Ｂのグループ３６４に対応するが、グループ３６４に属するコードブロックの数が１６以下であるので、グループ３６４と同じコードブロック数である。
【０２０２】
なお、グループ内のコードブロック数が１６個に満たない場合、並列演算用データ生成部３２１は、ダミーデータ（例えばゼロ値）を補充することで対応する（コードブロック数を疑似的に１６個にする）。
【０２０３】
レジスタ展開部１５１は、このグループ毎にコードブロックを蓄積し、そのデータ群をレジスタに展開する。このとき、同一グループに属するコードブロックのパラメータ（横サイズ、縦サイズ、符号化パス数（有効ビットプレーン数）、およびサブバンドタイプ）の値は、すべて互いに一致している。したがって、各コードブロックは、最も並列化が容易なデータ構造になっており、レジスタに展開される各サンプル（各データ群）は、互いに同一の方法でMQ符号化することができる。なお、１グループのコードブロック数は任意である。
【０２０４】
図２６に戻り、レジスタ展開部１５１、データ統合部１５２、およびバッファ部１５３は、図８の場合と同様に動作する。また、整列部３２４も図８の整列部１５４と基本的に同様に動作し、データの並び替えを行い、制御情報が有効であるデータをまとめる。
【０２０５】
図２６に示されるように、並列MQ符号化実行部３２５は、MQ符号化実行部１５５−１乃至MQ符号化実行部１５５−４を有する。MQ符号化実行部１５５−１乃至MQ符号化実行部１５５−４は、それぞれ、図８のMQ符号化実行部１５５と同様の処理部であり、同様に動作する。つまり、並列MQ符号化実行部３２５は、最大４並列にMQ符号化を行うことができる。
【０２０６】
整列部３２４は、制御情報が有効であるデータを、MQ符号化実行部１５５−１乃至MQ符号化実行部１５５−４に分配する（矢印３３８乃至矢印３４１）。
【０２０７】
MQ符号化実行部１５５−１乃至MQ符号化実行部１５５−４は、それぞれ、供給されたデータに対して、確率推定テーブル１５６を参照しながら（矢印３４２）MQ符号化を行う。MQ符号化実行部１５５−１乃至MQ符号化実行部１５５−４は、それぞれ、生成した符号語を符号化コードストリーム生成部１０６に供給する（矢印３４３乃至矢印３４６）。
【０２０８】
つまり、図２８に示されるように、並び替えられたデータ群は、点線で示されるように、４個ずつ並列にMQ符号化される。つまり、MQ符号化部３１２は、より高速にMQ符号化を行うことができる。しかも、原則、有効なMQ符号化しか行わないので、無駄が省ける効果がある。
【０２０９】
なお、このMQ符号化の並列数は任意である。
【０２１０】
［処理の流れ］
以上のようなMQ符号化処理の流れの例を図２９および図３０のフローチャートを参照して説明する。この処理は、図１９のフローチャートを参照して説明したMQ符号化処理に対応する。
【０２１１】
MQ符号化処理が開始されると、ステップＳ３０１において、並列演算用データ生成部３２１は、ビットモデリング部１１１から供給される、あるコードブロックのあるサンプルのシンボル、コンテキスト、および制御情報等のデータ群を取得する。
【０２１２】
ステップＳ３０２において、並列演算用データ生成部３２１は、ピクチャ内の全てのコードブロックのデータ群を全て取得したか否かを判定する。取得していないと判定された場合、ステップＳ３０１に戻り、それ以降の処理を繰り返す。
【０２１３】
ステップＳ３０２において、全てのコードブロックの全てのサンプルについてデータ群を取得したと判定された場合、ステップＳ３０３に進む。
【０２１４】
ステップＳ３０３において、並列演算用データ生成部３２１は、各コードブロックのパラメータに基づいて、コードブロックのグループ分けを行う。ステップＳ３０４において、並列演算用データ生成部３２１は、未処理のグループの中から処理対象を選択する。
【０２１５】
ステップＳ３０５において、並列演算用データ生成部３２１は、処理対象グループにコードブロックが予め定められた所定数（Ｍ個（Ｍは自然数））存在するか否かを判定する。存在する場合、ステップＳ３０７に進む。また、存在しない場合、ステップＳ３０６に進む。ステップＳ３０６において、並列演算用データ生成部３２１は、その処理対象グループに、所定数（Ｍ個）に不足するコードブロック数分のダミーデータ（例えば、全て０のデータ）を追加する。ステップＳ３０６の処理を終了するとステップＳ３０７に進む。
【０２１６】
ステップＳ３０７において、レジスタ展開部１５１は、処理対象グループの各コードブロックの処理対象サンプルのシンボル、コンテキスト、および制御情報をレジスタに展開する。このレジスタに展開されたデータ群を入力データと称する。
【０２１７】
ステップＳ３０８において、データ統合部１５２は、レジスタに展開された入力データ中の、制御情報が有効なデータをバッファ部１５３に保持されているデータ群（バッファデータ）に統合する。ステップＳ３０８の処理を終了すると図３０のステップＳ３２１に進む。
【０２１８】
ステップＳ３２１において、データ統合部１５２は、統合後の入力データの中に制御情報が有効であるデータが存在するか否かを判定する。存在すると判定された場合、ステップＳ３２２に進む。ステップＳ３２２において、データ統合部１５２は、バッファ部１５３からバッファデータを読み出す。
【０２１９】
ステップＳ３２３において、整列部３２４は、バッファ部１５３から読みだされたバッファデータの並び替えを行い、制御情報が有効なデータをまとめる。ステップＳ３２４において、並列MQ符号化実行部３２５は、制御情報が有効な各データを並列にMQ符号化する。
【０２２０】
ステップＳ３２５において、データ統合部１５２は、レジスタの入力データを、バッファ部１５３に供給し、保持させる。ステップＳ３２５の処理を終了すると、ステップＳ３２６に進む。また、ステップＳ３２１において、入力データの中に、制御情報が有効なデータが存在しないと判定された場合、ステップＳ３２６に進む。
【０２２１】
ステップＳ３２６において、レジスタ展開部１５１は、処理対象グループに属するコードブロックについて、未処理のサンプルが存在するか否かを判定する。未処理のサンプルが存在すると判定された場合、図２９のステップＳ３０７に戻り、それ以降の処理を繰り返す。
【０２２２】
また、図３０のステップＳ３２６において、未処理のサンプルが存在しないと判定された場合、ステップＳ３２７に進む。ステップＳ３２７において、並列演算用データ生成部３２１は、ピクチャ内に未処理のグループが存在するか否かを判定する。未処理のグループが存在すると判定された場合、図２９のステップＳ３０４に戻り、それ以降の処理を繰り返す。
【０２２３】
また、図３０のステップＳ３２７において、未処理のグループが存在しないと判定された場合、MQ符号化処理を終了し、図１０のステップＳ１０６に戻り、ステップＳ１０７以降の処理を行う。
【０２２４】
以上のように、MQ符号化部３１２は、複数のMQ符号化を並列に実行することができ、MQ符号化部１１２の場合よりもさらに効率よくMQ符号化を行うことができる。これにより、画像符号化装置１００は、より高速に符号化を行うことができる。しかも、原則、有効なMQ符号化しか行わないので、無駄が省ける効果がある。
【０２２５】
［適用例］
なお、データを展開するレジスタのレジスタ長は任意である。一般的に、コンピュータやハードウェアのデータレジスタ長は最初の設計の段階で決まっている。つまり、レジスタ長は、ハードウェアの仕様に依存する場合が多い。図３１は、画像符号化装置を適用するハードウェアの構成例を示す図である。
【０２２６】
図３１に示される構成は、CBE（Cell Broadband Engine）と称されるプロセッサの中に８個存在するサブプロセッサであるSPE（Synergistic Processing Elements）の構成である。図２７に示されるように、SPEにおいては、２５６KBのLocal Store（キャッシュメモリ）に対して、１２８ビット単位の読み出しや書き込み（Read/Write）が可能な構成になっている。つまり、これはレジスタ長が１２８ビットであることに対応している。
【０２２７】
なお、図２６に示されるMQ符号化部３１２において、レジスタにデータを展開するコードブロック数Ｎと、並列MQ符号化実行部３２５の実行可能な並列数（並列MQ符号化実行部３２５が有するMQ符号化実行部１５５の数）Ｍは、それぞれ任意であり、互いに異なる値であってもよいし、互いに同じ値であってもよい（ＮおよびＭは自然数）。
【０２２８】
また、ビットモデリング部１１１において、ビットモデリングを並列化するようにしてもよい。その場合、図２７を参照して説明したMQ符号化の並列化の場合と同様に、パラメータが互いに同一の複数のコードブロックを所定数毎にグループ化することにより、適切かつ容易に並列化を実現することができる。
【０２２９】
ビットモデリングを並列化する場合、その並列化したそれぞれについてMQ符号化を行う場合、各MQ符号化部を、図８のMQ符号化部１１２のように実現してもよいし、図２６のMQ符号化部３１２のように実現するようにしてもよい。ビットモデリングの並列化とMQ符号化の並列化を互いに独立して実現するようにしてももちろんよい。
【０２３０】
＜３．第３の実施の形態＞
［パーソナルコンピュータ］
上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。この場合、例えば、図３２に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。
【０２３１】
図３２において、パーソナルコンピュータ５００の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，  １０６  符号化コードストリーム生成部，  １１１  ビットモデリング部，  １１２  MQ符号化部，  １４１  選択部，  １４２  CUパス部，  １４３  SPパス部，  １４４  MRパス部，  １４５  切り替え部，  １５１  レジスタ展開部，  １５２  データ統合部，  １５３  バッファ部，  １５４  整列部，  １５５  MQ符号化実行部，  １５６  確率推定テーブル，  ３１２  MQ符号化部，  ３２１  並列演算用データ生成部，  ３２４  整列部，  ３２５  並列MQ符号化実行部
【図１】
2011091577.tif 000003
【図２】
2011091577.tif 000004
【図３】
2011091577.tif 000005
【図４】
2011091577.tif 000006
【図５】
2011091577.tif 000007
【図６】
2011091577.tif 000008
【図７】
2011091577.tif 000009
【図８】
2011091577.tif 000010
【図９】
2011091577.tif 000011
【図１０】
2011091577.tif 000012
【図１１】
2011091577.tif 000013
【図１２】
2011091577.tif 000014
【図１３】
2011091577.tif 000015
【図１４】
2011091577.tif 000016
【図１５】
2011091577.tif 000017
【図１６】
2011091577.tif 000018
【図１７】
2011091577.tif 000019
【図１８】
2011091577.tif 000020
【図１９】
2011091577.tif 000021
【図２０】
2011091577.tif 000022
【図２１】
2011091577.tif 000023
【図２２】
2011091577.tif 000024
【図２３】
2011091577.tif 000025
【図２４】
2011091577.tif 000026
【図２５】
2011091577.tif 000027
【図２６】
2011091577.tif 000028
【図２７】
2011091577.tif 000029
【図２８】
2011091577.tif 000030
【図２９】
2011091577.tif 000031
【図３０】
2011091577.tif 000032
【図３１】
2011091577.tif 000033
【図３２】
2011091577.tif 000034