[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP2011091576A - 符号化装置および方法 - Google Patents

符号化装置および方法 Download PDF

Info

Publication number
JP2011091576A
JP2011091576A JP2009242769A JP2009242769A JP2011091576A JP 2011091576 A JP2011091576 A JP 2011091576A JP 2009242769 A JP2009242769 A JP 2009242769A JP 2009242769 A JP2009242769 A JP 2009242769A JP 2011091576 A JP2011091576 A JP 2011091576A
Authority
JP
Japan
Prior art keywords
encoding
state
coefficient data
calculation
pass
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
JP2009242769A
Other languages
English (en)
Inventor
Takahiro Fukuhara
隆浩 福原
Katsutoshi Ando
勝俊 安藤
Koji Hara
耕司 原
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sony Corp
Original Assignee
Sony Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sony Corp filed Critical Sony Corp
Priority to JP2009242769A priority Critical patent/JP2011091576A/ja
Priority to US12/924,780 priority patent/US20110091123A1/en
Priority to CN2010105118020A priority patent/CN102045565A/zh
Publication of JP2011091576A publication Critical patent/JP2011091576A/ja
Withdrawn legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
    • H04N19/436—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation using parallelised computational arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/63—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

【課題】符号化をより高速に行うことができるようにする。
【解決手段】CUパス部１２４は、ステップＳ１４１においてRLCの結果が０である計算を行い、ステップＳ１４２においてRLCの結果が１である計算を行い、ステップＳ１４３において１番目のUNIFORMエンコードの計算を行い、ステップＳ１４４において２番目のUNIFORMエンコードの計算を行う。MQ符号化部１１２は、ステップＳ１４５においてRLCコンテキストで値０をMQ符号化し、ステップＳ１４６においてRLCコンテキストで値１をMQ符号化し、ステップＳ１４７においてUNIFORMコンテキストで１回目のMQ符号化を行い、ステップＳ１４８においてUNIFORMコンテキストで２回目のMQ符号化を行う。本発明は、例えば、画像符号化装置に適用することができる。
【選択図】図１１

Description

本発明は、符号化装置および方法に関し、特に、より高速に符号化を行うことができるようにした符号化装置および方法に関する。
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の高速化を実現できるかが、鍵であった。
本発明は、このような状況に鑑みて提案されたものであり、符号化をより高速に行うことができるようにすることを目的とする。
本発明の一側面は、画像データをサブバンド毎の係数データに変換するウェーブレット変換手段と、前記ウェーブレット変換手段により生成された前記係数データの前記サブバンドの領域をコードブロックに分割するコードブロック化手段と、処理対象の係数データに隣接する周囲のバイナリ係数データの値および状態に応じて、処理対象の係数データの状態を遷移させる状態遷移手段と、前記状態遷移手段により遷移された前記係数データの状態に従って、符号化パスを選択する選択手段と、前記選択手段により選択された符号化パスに従って、前記コードブロック化手段により生成されたコードブロック毎に、前記係数データを符号化する符号化手段とを備える符号化装置である。
前記係数データの状態は、係数の正負符号（Sign）、状態変数１（State-0）、状態変数２（State-1）、および有効（Sig）の４つの変数によって定義されるようにすることができる。
前記係数データの状態は、状態変数１（State-0）、状態変数２（State-1）、および有効（Sig）の３つの変数と、前記係数データの７つの状態との対応関係を示すテーブル情報に基づいて、前記３つの変数の値から求められるようにすることができる。
前記７つの状態のうち、第１の状態は、CUパスで符号化される状態であり、第２の状態は、無効なサンプルとされる状態であり、第３の状態は、周囲に有意なサンプルがあり、且つ現在のビットプレーンで未符号化時にはCUパスで符号化される状態であり、第４の状態は、周囲に有意なサンプルがあり、SPパスで符号化される状態であり、第５の状態は、有意であり、且つ既に現在のビットプレーンはSPパスで符号化済みの状態であり、第６の状態は、有意であり、MRパスで符号化され、次のMRパスが１回目である状態であり、第７の状態は、有意であり、MRパスで符号化され、次のMRパスが２回目である状態であるようにすることができる。
前記状態遷移手段は、処理対象の係数データの状態が前記第１の状態であって、前記CUパスで周囲の係数データのいずれかが有意になった場合、前記第３の状態に遷移させることができる。
前記状態遷移手段は、処理対象の係数データが前記第１の状態であって、前記CUパスで有意になった場合、前記第５の状態に遷移させることができる。
前記状態遷移手段は、処理対象の係数データが前記第３の状態であって、前記SPパスで符号化する場合、前記第４の状態に遷移させることができる。
前記状態遷移手段は、処理対象の係数データが前記第３の状態であって、前記CUパスで有意になった場合、前記第５の状態に遷移させることができる。
前記状態遷移手段は、処理対象の係数データが前記第５の状態であって、１つのビットプレーンの符号化がすべて終了した場合、前記第６の状態に遷移させることができる。
前記状態遷移手段は、処理対象の係数データが前記第６の状態であって、１つのビットプレーンの符号化がすべて終了した場合、前記第７の状態に遷移させることができる。
前記状態遷移手段により遷移された、処理対象のコードブロック内の各係数データの状態を保持する保持手段をさらに備え、前記選択手段は、前記保持手段により保持される前記係数データの状態に従って、符号化パスを選択することができる。
前記符号化手段は、前記選択手段により選択された符号化パスに従って、前記係数データに対して所定の演算を行う演算手段と、前記演算手段による演算結果を用いて算術符号化を行う算術符号化手段とを備えることができる。
前記演算手段は、前記選択手段によりCUパスが選択された場合、前記係数データに対して所定の演算を行うCUパス演算手段と、前記選択手段によりSPパスが選択された場合、前記係数データに対して所定の演算を行うSPパス演算手段と、前記選択手段によりMRパスが選択された場合、前記係数データに対して所定の演算を行うMRパス演算手段とを備えることができる。
前記CUパス演算手段は、前記コードブロックの４つの係数データに対して、ランレングス符号化の結果が０になる計算と、ランレングス符号化の結果が１になる計算の両方を実行し、前記算術符号化手段は、前記ランレングス符号化のコンテキストを用いて、値０の係数データをMQ符号化し、さらに、値１の係数データをMQ符号化することができる。
前記CUパス演算手段は、前記コードブロックの４つの係数データに対して、UNIFORMエンコード符号化を２回行い、前記算術符号化手段は、その２回各々に対して、UNIFORMのコンテキストを用いて、係数０または１をMQ符号化することができる。
前記CUパス演算手段は、前記コードブロックの係数データ毎に、CUエンコードを実行するか否かの計算を行い、前記算術符号化手段は、前記計算の結果に従って、Significanceコンテキストを用いてMQ符号化することができる。
前記CUパス演算手段は、前記コードブロックの係数データ毎に、Signエンコードを実行するか否かの計算を行い、前記算術符号化手段は、前記計算の結果に従ってSignコンテキストを用いてMQ符号化することができる。
前記SPパス演算手段は、前記係数データの値が１か否かの計算を行い、前記算術符号化手段は、前記計算の結果に従ってSignコンテキストを用いてMQ符号化することができる。
前記MRパス演算手段は、MRエンコードを実行するか否かの計算を行い、前記算術符号化手段は、前記計算の結果に従ってMRコンテキストを用いてMQ符号化することができる。
本発明の一側面は、また、画像データをサブバンド毎の係数データに変換し、変換された前記係数データの前記サブバンドの領域をコードブロックに分割し、分割された前記コードブロック毎に、処理対象の係数データに隣接する周囲のバイナリ係数データの値および状態に応じて、処理対象の前記係数データの状態を遷移させ、遷移された前記係数データの状態に従って、符号化パスを選択し、選択された符号化パスに従って、生成されたコードブロック毎に、前記係数データを符号化する符号化方法である。
本発明の一側面においては、画像データがサブバンド毎の係数データに変換され、変換された係数データのサブバンドの領域がコードブロックに分割され、分割されたコードブロック毎に、処理対象の係数データに隣接する周囲のバイナリ係数データの値および状態に応じて、処理対象の係数データの状態が遷移され、遷移された係数データの状態に従って、符号化パスが選択され、選択された符号化パスに従って、生成されたコードブロック毎に、係数データが符号化される。
本発明によれば、画像を符号化することができる。特に、より高速に画像を符号化することができる。
本発明を適用した画像符号化装置の主な構成例を示すブロック図である。 サブバンドの構成例を示す図である。 各サブバンド中のコードブロックの例を示す図である。 ビットプレーンの例を説明する図である。 符号化パスの例を説明する図である。 係数の走査の例を説明する図である。 状態の定義の例を説明する図である。 状態遷移テーブルの例を説明する図である。 符号化処理の流れの例を説明するフローチャートである。 EBCOT処理の流れの例を説明するフローチャートである。 CUパス処理の流れの例を説明するフローチャートである。 CUパス処理の流れの例を説明する、図１１に続くフローチャートである。 CUパス処理の実際に動作が発生する処理の例について説明するフローチャートである。 CUパス処理の実際に動作が発生する処理の、他のについて説明するフローチャートである。 CUパス処理の実際に動作が発生する処理の、さらに他のについて説明するフローチャートである。 従来のCUパス処理の流れの例を説明するフローチャートである。 SPパス処理の流れの例を説明するフローチャートである。 従来のSPパス処理の流れの例を説明するフローチャートである。 MRパス処理の流れの例を説明するフローチャートである。 従来のMRパス処理の流れの例を説明するフローチャートである。 本発明を適用した画像符号化装置の他の構成例を示すブロック図である。 符号化パスについて説明する図である。 コードブロックのグループ化を説明する図である。 並列演算用係数データの生成の様子を説明する図である。 係数データの並列演算の様子を説明する図である。 符号化処理の流れの、他の例を説明するフローチャートである。 本発明を適用するハードウェアの例を示す図である。 本発明を適用したパーソナルコンピュータの構成例を示すブロック図である。
以下、発明を実施するための形態（以下実施の形態とする）について説明する。なお、説明は以下の順序で行う。
１．第１の実施の形態（画像符号化装置）
２．第２の実施の形態（画像符号化装置）
３．第３の実施の形態（パーソナルコンピュータ）
＜１．第１の実施の形態＞
［画像符号化装置の構成］
図１は、本発明を適用した画像符号化装置の一実施の形態の構成を表している。図１に示される画像符号化装置１００は、画像データを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符号化（算術符号化）を実行するようにすることにより、符号化パス内での条件分岐の削除を実現する。より具体的には、画像符号化装置１００は、コードブロック内の係数が持つ状態の遷移を新たに定義することで、従来、処理速度のネックになっていた条件分岐を不要にした。これにより、画像符号化装置１００は、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）に向かう順に、EBCOT１０５に供給する。つまり、ビットプレーン展開部１０４は、ビット深度の上位側から下位側に向かう順に、展開したビットプレーンを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）で規定された学習型の２値算術符号である。
つまり、図１に示されるように、EBCOT１０５は、ビットモデリングを行うビットモデリング部１１１と、算術符号化を行うMQ符号化部１１２とを有する。
ビットモデリング部１１１は、状態遷移生成部１２１、状態遷移テーブル１２２、選択部１２３、CUパス（Cleanup Pass）部１２４、SPパス（Significant Propagation Pass）部１２５、およびMRパス（Magnitude Refinement Pass）部１２６を有する。
本発明では、ビットモデリング部１１１においてビットモデリングを行う際に必須となる、係数の持つ状態の遷移を効率的に実行することにより、EBCOTを高速に実行させる。
EBCOTのビットモデリングには、以下の特徴がある。
（１）コードブロックの各係数は、必ず「状態」を保持する。
（２）その「状態」は、係数がどの符号化パスで、どの様にエンコードされるかを規定する。
（３）その「状態」はエンコード中に、周囲の係数や周囲の「状態」によって遷移する。
ビットモデリング部１１１は、各係数の持つ「状態」を定義するために、以下の４つのパラメータを設ける。
１．正負符号（Sign）
２．状態変数１（Status-0）
３．状態変数２（Status-1）
４．有効（Sig）
なお、このうち、正負符号（Sign）の変数は省略することができる。図７は、このパラメータの内の正負符号を除く３つの変数に対して、７つの状態を定義したものである（正負符号が不要な理由は、図４で示した様に、正負符号を表すSignビットプレーンは別にエンコードされるためである）。
従来のEBCOTの場合、CUパス、SPパス、MRパスの３つしか存在しないが、ビットモデリング部１１１は、各符号化パスに遷移する前の段階も定義する。各状態の意味は図７に示されるテーブルの通りである。
状態１：CUパスでエンコードする。
状態２：無効なサンプルである。
状態３：周囲に有意なサンプルがあり、且つ現在のビットプレーンで未エンコード時にはCUパスでエンコードする。
状態４：周囲に有意なサンプルがあり、SPパスでエンコードする。
状態５：有意であり、且つ既に現在のビットプレーンはSPパスでエンコード済みである。
状態６：有意であり、MRパスでエンコードする。次のMRパスは１回目である。
状態７：有意であり、MRパスでエンコードする。次のMRパスは２回目である。
CUパスでの符号化は従来の場合と基本的に同様であるが、SPパスは、CUパスからSPパスに移行する前段階のPreSPと、SPパスを実行する２つの状態に分割されている。また、MRパスは、MRパス以前でMRパスを行わないPreMRの他、MRパスを実行する内、１回目と２回目以降とで、MR1stとMR2ndとに分割されている。このように、ビットモデリング部１１１は、従来の３つの符号化パスを細分化して、各状態間の状態遷移を定義している。
図１に戻り、状態遷移生成部１２１は、このテーブルを用いることにより、上述した３つの変数の値から、係数データの状態を求めることができる。
状態遷移生成部１２１は、各係数の状態を保持するとともに、その状態の遷移を管理する。例えば、状態遷移生成部１２１は、状態遷移テーブル１２２を参照しながら、処理対象の係数に隣接する周囲のバイナリ係数値とその状態等の各種条件に応じて、処理対象の係数や周囲の係数の状態を遷移させる（矢印１３７および矢印１３８）。状態遷移の条件と遷移内容は、状態遷移テーブル１２２として、例えば図８に示されるように、予め定義されている。
つまり、状態遷移は、以下のように行われる。
（１）CUパスにて周囲の係数のいずれかが有意になった場合、CUからPreSPに遷移する。
（２）CUパスにてその注目係数が有意になった場合、CUからPreMRに遷移する。
（３）SPパスにてエンコードの直前において、PreSPからSPに遷移する。
（４）CUパスにて有意になった場合、PreSPからPreMRに遷移する。
（５）SPパスにて有意になった場合、SPからPreMRに遷移する。
（６）１つのビットプレーンのエンコードが終了すると、PreMRからMR1stに遷移する。
（７）１つのビットプレーンのエンコードが終了すると、MR1stからMR2ndに遷移する。
図１に戻り、状態遷移生成部１２１は、以上のような状態遷移の発生に関する情報を、係数データ等とともに、選択部１２３に供給する（矢印１３９）。
選択部１２３は、状態遷移の有無やその内容に応じて、状態遷移生成部１２１に接続される端子１２３Ａの接続先を、端子１２３Ｂ−１乃至端子１２３Ｂ−３の中からいずれか１つ選択する（端子１２３Ａを選択した端子１２３Ｂに接続する）。
端子１２３Ｂ−１は、CUパス部１２４に接続され、端子１２３Ｂ−２は、SPパス部１２５に接続され、端子１２３Ｂ−３は、MRパス部１２６に接続される。つまり、選択部１２３は、状態遷移生成部１２１の接続先を、CUパス部１２４、SPパス部１２５、およびMRパス部１２６の中から選択する。係数データは、選択された符号化パスに供給される。
CUパス部１２４は、係数データ等が供給されると（矢印１４０）、それらを用いてCUパスによってコンテキストやラベルの決定を行う。CUパス部１２４は、生成したコンテキストやラベル等の情報をMQ符号化部１１２に供給する（矢印１４３）。
SPパス部１２５は、係数データ等が供給されると（矢印１４１）、それらを用いてSPパスによってコンテキストやラベルの決定を行う。SPパス部１２５は、生成したコンテキストやラベル等の情報をMQ符号化部１１２に供給する（矢印１４４）。
MRパス部１２６は、係数データ等が供給されると（矢印１４２）、それらを用いてMRパスによってコンテキストやラベルの決定を行う。MRパス部１２６は、生成したコンテキストやラベル等の情報をMQ符号化部１１２に供給する（矢印１４５）。
MQ符号化部１１２は、ビットモデリング部１１１の各符号化パス（CUパス部１２４、SPパス部１２５、およびMRパス部１２６）より供給される、コンテキストやラベル等の情報に基づいてMQ符号化を行う。このときMQ符号化部１１２は、各符号化パスにおける計算結果に関わらず、MQ符号化を行う。
MQ符号化部１１２は、算術符号化結果を符号化コードストリーム生成部１０６に供給する（矢印１４６）。
符号化コードストリーム生成部１０６は、EBCOT１０５（MQ符号化部１１２）から供給された符号化データを整列し、１つのコードストリームとして出力する（矢印１４７）。
［処理の流れ］
次に、このような画像符号化装置１００により実行される符号化処理の流れの例を図９のフローチャートを参照して説明する。
符号化処理が開始されると、ウェーブレット変換部１０１は、ステップＳ１０１において、１ピクチャ分の画像データをウェーブレット変換する。ステップＳ１０２において、量子化部１０２は、ステップＳ１０１において生成された係数データを量子化する。なお、可逆符号化の場合、このステップＳ１０２の処理は省略される。
ステップＳ１０３において、コードブロック化部１０３は、係数データをコードブロック化する。ステップＳ１０４において、ビットプレーン展開部１０４は、係数データをビットプレーン展開する。
ステップＳ１０５において、EBCOT１０５は、EBCOT処理を実行し、係数データを符号化する。
ステップＳ１０６において、符号化コードストリーム生成部１０６は、EBCOT１０５において生成された符号化データを整列してコードストリームを生成し、出力する。ステップＳ１０６の処理が終了すると、符号化処理が終了される。
なお、この符号化処理は、ピクチャ毎に行われる。
次に、図１０のフローチャートを参照して、図９のステップＳ１０５において行われるEBCOT処理の詳細について説明する。
EBCOT処理が開始されると、状態遷移生成部１２１は、ステップＳ１２１において、コードブロックの係数の状態を初期化する。ステップＳ１２２において、選択部１２３は、状態や係数に応じてパスを選択する。ステップＳ１２３において、選択部１２３は、CUパスを選択したか否かを判定する。
CUパスを選択したと判定された場合、ステップＳ１２４に進む。ステップＳ１２４において、CUパス部１２４およびMQ符号化部１１２は、CUパスにより符号化を行うCUパス処理を実行する。CUパス処理が終了すると、ステップＳ１２８に進む。
また、ステップＳ１２３において、CUパスを選択していないと判定された場合、ステップＳ１２５に進む。ステップＳ１２５において、選択部１２３は、SPパスを選択したか否かを判定する。
SPパスを選択したと判定された場合、ステップＳ１２６に進む。ステップＳ１２６において、SPパス部１２５およびMQ符号化部１１２は、SPパスにより符号化を行うSPパス処理を実行する。SPパス処理が終了すると、ステップＳ１２８に進む。
また、ステップＳ１２５において、SPパスを選択していないと判定された場合、ステップＳ１２７に進む。ステップＳ１２７において、MRパス部１２６およびMQ符号化部１１２は、MRパスにより符号化を行うMRパス処理を実行する。MRパス処理が終了すると、ステップＳ１２８に進む。
ステップＳ１２８において、EBCOT１０５は、EBCOT処理を終了するか否かを判定する。未処理の係数データが存在し、EBCOT処理を終了しないと判定された場合、ステップＳ１２２に戻り、それ以降の処理が繰り返される。また、ステップＳ１２８において、ピクチャ内の全ての係数データを処理したと判定された場合、EBCOT処理を終了し、図９のステップＳ１０５に戻り、ステップＳ１０６以降の処理を実行する。
次に、図１０のステップＳ１２４において実行されるCUパス処理の流れの例を、図１１および図１２のフローチャートを参照して説明する。なお、スプライトの横サイズを６４、縦サイズを４とする。また、図１１および図１２において、点線矢印は、データの依存関係を示す。
CUパスでは、スプライト内の縦方向の係数群（図６の例の場合、４係数）が上から下方向の順番に走査されながら、この係数群（４係数）毎に以下の計算（ステップＳ１４１乃至ステップＳ１４８）が行われる。
ステップＳ１４１において、CUパス部１２４は、ランレングス符号化（RLC（Run length coding））の結果が０である計算を行う。この計算が成功した場合、計算結果はFFとなる。また、この計算が失敗した場合、計算結果は00となる。これらの計算結果は、ステップＳ１４５の処理に影響を与える。
ステップＳ１４１の処理が終了するとステップＳ１４２に進む。ステップＳ１４２において、CUパス部１２４は、ランレングス符号化（RLC（Run length coding））の結果が１である計算を行う。この計算が成功した場合、計算結果はFFとなる。また、この計算が失敗した場合、計算結果は00となる。これらの計算結果は、ステップＳ１４６乃至ステップＳ１４８の処理に影響を与える。
ステップＳ１４２の処理が終了するとステップＳ１４３に進む。ステップＳ１４３において、CUパス部１２４は、１番目のUNIFORMエンコードの計算を行う。エンコード対象は０または１である。この計算結果は、ステップＳ１４７の処理に影響を与える。
ステップＳ１４３の処理が終了するとステップＳ１４４に進む。ステップＳ１４４において、CUパス部１２４は、２番目のUNIFORMエンコードの計算を行う。エンコード対象は０または１である。この計算結果は、ステップＳ１４８の処理に影響を与える。
CUパスの処理において、ステップＳ１４１における、RLCの処理を実行するか否かが最初の分岐点である。ただし、図１１に示されるように、本発明においては、RLCの結果が１である計算と０である計算のいずれも行う。そしてその結果（FFまたは00）を見ることで、MQ符号化部１１２は、実際にRLCが有効であったか否かを自動的に判別することができる。
ステップＳ１４４の処理が終了するとステップＳ１４５に進む。MQ符号化部１１２は、ステップＳ１４５において、RLCコンテキストで値０をMQ符号化し、ステップＳ１４６において、RLCコンテキストで値１をMQ符号化する。
また、MQ符号化部１１２は、ステップＳ１４７において、UNIFORMコンテキストで１回目のMQ符号化を行い、ステップＳ１４８において、UNIFORMコンテキストで２回目のMQ符号化を行う。
図１１のステップＳ１４８の処理が終了すると、図１２のステップＳ１６１に進む。CUパスでは、上述した係数群（４係数）内の各係数に対して以下の計算（ステップＳ１６１乃至ステップＳ１６７）が行われる。
ステップＳ１６１において、CUパス部１２４は、CUエンコードを行うか否かの計算を行う。例えば、CUエンコードを行う場合、計算結果はFFとなり、CUエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ１６３のMQ符号化に用いられる。
ステップＳ１６１の処理が終了するとステップＳ１６２に進む。ステップＳ１６２において、CUパス部１２４は、Significanceコンテキストの計算を行う。ステップＳ１６３において、MQ符号化部１１２は、SignificanceコンテキストでSymbolをMQ符号化する。
ステップＳ１６３の処理が終了するとステップＳ１６４に進む。ステップＳ１６４において、CUパス部１２４は、Signエンコードするか否かの計算を行う。例えば、Signエンコードを行う場合、計算結果はFFとなり、Signエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ１６６のMQ符号化に用いられる。また、この計算結果は、ステップＳ１６７の状態の更新にも用いられる。
ステップＳ１６４の処理が終了するとステップＳ１６５に進む。ステップＳ１６５において、CUパス部１２４は、Signコンテキストの計算を行う。ステップＳ１６６において、MQ符号化部１１２は、SignコンテキストでSignをMQ符号化する。
ステップＳ１６７において、状態遷移生成部１２１は、Signエンコードするか否かの計算結果に基づいて、周囲８係数の状態をPreSPに更新し、現在の係数の状態をPreMRに更新する。具体的には、周囲８係数の内のどれかの係数が１になり、且つ周囲の係数がPreSPに書き換えられた場合、現在の係数がCUからPreSPに遷移する。また、現在の係数が１になり、且つ現在の係数がPreMRに書き換えられた場合、現在の係数がCUからPreMRに遷移する。
ステップＳ１６８において、CUパス部１２４は、処理対象の係数群（４係数）内の全ての係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ１６１に戻り、それ以降の処理を繰り返す。
また、ステップＳ１６８において、処理対象の係数群（４係数）内の全ての係数が処理されたと判定された場合、ステップＳ１６９に進む。ステップＳ１６９において、CUパス部１２４は、処理対象ビットプレーンの全てのスプライトの全係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、図１１のステップＳ１４１に戻り、それ以降の処理を繰り返す。
また、図１２のステップＳ１６９において、全ての係数を処理したと判定された場合、ステップＳ１７０に進む。CUパスは、図５に示される様に、必ず１つのビットプレーンの最後に行われる。したがって、CUパス処理の最後のステップＳ１７０において、状態遷移生成部１２１は、全ての係数について、MR1stからMR2ndに、PreMRからMR1stに、それぞれ状態を更新する。
ステップＳ１７０の処理が終了すると、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の結果が１の場合の、実際に動作が発生する処理について説明する。
≪ケース２（RLCの結果が１の場合）≫
（１）RLCの結果が０である計算を実行する（ステップＳ１４１）と、その結果は00になる。
（２）RLCの結果が１である計算を実行する（ステップＳ１４２）と、その結果はFFになる。
（３）１番目のUNIFORMエンコードの計算を実行して（ステップＳ１４３）、符号語を発生させる。
（４）２番目のUNIFORMエンコードの計算を実行して（ステップＳ１４４）、符号語を発生させる。
（５）RLCコンテキストで値０をMQ符号化しても（ステップＳ１４５）、符号語は発生しない。
（６）RLCコンテキストで値１をMQ符号化して（ステップＳ１４６）、符号語を出力する。
（７）UNIFORMコンテキストでMQ符号化を行って（１番目）（ステップＳ１４７）、符号語を出力する。
（８）UNIFORMコンテキストでMQ符号化を行って（２番目）（ステップＳ１４８）、符号語を出力する。
以上のように、RLCの結果が１の場合、ステップＳ１４１乃至ステップＳ１４８の各処理が行われるが、実際に符号語を発生するのは、（３）（ステップＳ１４３）、（４）（ステップＳ１４４）、（６）（ステップＳ１４６）、（７）（ステップＳ１４７）、および（８）（ステップＳ１４８）である。
次に、図１５を参照し、RLCを行わない場合の、実際に動作が発生する処理について説明する。
≪ケース３（RLCを行わない場合）≫
（１）RLCの結果が０である計算を実行する（ステップＳ１４１）と、その結果は00になる。
（２）RLCの結果が１である計算を実行する（ステップＳ１４２）と、その結果は00になる。
（３）１番目のUNIFORMエンコードの計算を実行しても（ステップＳ１４３）、符号語は発生しない。
（４）２番目のUNIFORMエンコードの計算を実行しても（ステップＳ１４４）、符号語は発生しない。
（５）RLCコンテキストで値０をMQ符号化しても（ステップＳ１４５）、符号語は発生しない。
（６）RLCコンテキストで値１をMQ符号化しても（ステップＳ１４６）、符号語は発生しない。
（７）UNIFORMコンテキストでMQ符号化を行っても（１番目）（ステップＳ１４７）、符号語は発生しない。
（８）UNIFORMコンテキストでMQ符号化を行っても（２番目）（ステップＳ１４８）、符号語は発生しない。
以上のように、RLCが行われない場合、ステップＳ１４１乃至ステップＳ１４８の各処理が行われるが、実際に符号語を発生する処理は存在しない。これは、後述の従来のCUパス処理においてRLCを行わない場合と同様である。
以上において重要な事は、本発明ではMQ符号化を、ビットモデリングの計算結果に関係なく実行している点である。MQ符号化は、例えばある計算結果がFFの場合、実際の有効な符号語を出力するが、その計算結果が00の場合、符号語を出力しない。EBCOT１０５は、このMQ符号化の特徴を巧みに利用することで条件判定を不要としている。
これに対して従来のCUパス処理の流れは、図１６のフローチャートに示されるようになる。
つまり、スプライト内の縦方向の係数群（４係数）に対する処理は、ステップＳ１８１乃至ステップＳ１８６に示されるように行われる。したがって、RLCを実行するか否か（ステップＳ１８１）と、４係数は全て０か否か（ステップＳ１８２）の２か所で条件分岐が発生する。
コンピュータシステムでは、条件分岐（if then else）が発生すると、キャッシュのミスヒットやペナルティが発生して、速度の急激な低下を余儀なくされることは、よく知られている事実である。JPEG2000のEBCOTの処理負荷が重く、高速化が困難とされてきた最大の原因の１つが、このような条件分岐の多さである。
これに対して、EBCOT１０５は、上述したように、スプライト内の縦方向の係数群（４係数）に対する処理（図１１のステップＳ１４１乃至ステップＳ１４８）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
なお、付言するに、従来の方法の場合、その後の係数単位のループ処理（図１６のステップＳ１８７乃至ステップＳ１９３）においても、CUエンコードを行うか否かの条件分岐（ステップＳ１８７）と、係数が１であるか否かの条件分岐（ステップＳ１９０）が存在している。これらの２つの条件分岐は、スプライト内の縦方向の係数群（４係数）の各係数に対して行われる。したがって、これらの条件分岐によるオーバヘッドは、上述したステップＳ１８１およびステップＳ１８２における条件分岐によるオーバヘッドよりも、さらに大きいものとなる。
これに対して、EBCOT１０５は、上述したように、各係数に対する処理（図１２のステップＳ１６１乃至ステップＳ１６７）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
次に、図１０のステップＳ１２６において実行されるSPパス処理の流れの例を、図１７のフローチャートを参照して説明する。なお、点線矢印は、データの依存関係を示す。
SPパス処理が開始されると、ステップＳ２１１において、状態遷移生成部１２１は、現係数の状態をPreSPからSPに遷移する。ステップＳ２１２において、SPパス部１２５は、SPエンコードを行うか否かの計算を行う。例えば、SPエンコードを行う場合、計算結果はFFとなり、SPエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ２１４のMQ符号化に用いられる。
ステップＳ２１２の処理が終了するとステップＳ２１３に進む。ステップＳ２１３において、SPパス部１２５は、Significanceコンテキストの計算を行う。ステップＳ２１４において、MQ符号化部１１２は、SignificanceコンテキストでSymbolをMQ符号化する。
ステップＳ２１４の処理が終了するとステップＳ２１５に進む。ステップＳ２１５において、SPパス部１２５は、係数が１であるか否かの計算を行う。例えば、係数が１である場合、計算結果はFFとなり、係数が０である場合、計算結果は00となる。この計算結果は、ステップＳ２１７のMQ符号化に用いられる。また、この計算結果は、ステップＳ２１８の状態の更新にも用いられる。
ステップＳ２１５の処理が終了するとステップＳ２１６に進む。ステップＳ２１６において、SPパス部１２５は、Signコンテキストの計算を行う。ステップＳ２１７において、MQ符号化部１１２は、SignコンテキストでSignをMQ符号化する。
ステップＳ２１８において、状態遷移生成部１２１は、係数が１かどうかの計算結果に基づいて、周囲８係数の状態をPreSPに更新し、現在の係数の状態をPreMRに更新する。具体的には、周囲８係数の内のどれかの係数が１になり、且つ周囲の係数がPreSPに書き換えられた場合、現在の係数がCUからPreSPに遷移する。また、現在の係数が１になり、且つ現在の係数がPreMRに書き換えられた場合、現在の係数がCUからPreMRに遷移する。
ステップＳ２１９において、SPパス部１２５は、処理対象の係数群（４係数）内の全ての係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ２１１に戻り、それ以降の処理を繰り返す。
また、ステップＳ２１９において、処理対象の係数群（４係数）内の全ての係数が処理されたと判定された場合、ステップＳ２２０に進む。ステップＳ２２０において、SPパス部１２５は、処理対象ビットプレーンの全てのスプライトの全係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ２１１に戻り、それ以降の処理を繰り返す。
また、ステップＳ２２０において、全ての係数を処理したと判定された場合、SPパス処理が終了され、図１０のステップＳ１２６に戻り、ステップＳ１２８以降の処理が行われる。
このSPパス処理の場合も、CUパスの場合と同様に、MQ符号化が、ビットモデリングの計算結果に関係なく実行される。EBCOT１０５は、MQ符号化の特徴を巧みに利用することにより、SPパス処理においても条件判定を不要としている。
これに対して従来のSPパス処理の流れは、図１８のフローチャートに示されるようになる。
つまり、SPエンコードを行うか否かの条件分岐（ステップＳ２４１）と、係数が１であるか否かの条件分岐（ステップＳ２４４）が存在している。これらの２つの条件分岐は、スプライト内の縦方向の係数群（４係数）の各係数に対して行われる。したがって、これらの条件分岐によるオーバヘッドによって速度が大幅に低下する恐れがある。
これに対して、EBCOT１０５は、上述したように、各係数に対する処理（図１７のステップＳ２１１乃至ステップＳ２１８）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
次に、図１０のステップＳ１２７において実行されるMRパス処理の流れの例を、図１９のフローチャートを参照して説明する。なお、点線矢印は、データの依存関係を示す。
MRパス処理が開始されると、ステップＳ２６１において、MRパス部１２６は、MRエンコードを行うか否かの計算を行う。例えば、MRエンコードを行う場合、計算結果はFFとなり、MRエンコードを行わない場合、計算結果は00となる。この計算結果は、ステップＳ２６３のMQ符号化に用いられる。
ステップＳ２６１の処理が終了するとステップＳ２６２に進む。ステップＳ２６２において、MRパス部１２６は、MRコンテキストの計算を行う。ステップＳ２６３において、MQ符号化部１１２は、MRコンテキストでSymbolをMQ符号化する。
ステップＳ２６３の処理が終了するとステップＳ２６４に進む。ステップＳ２６４において、MRパス部１２６は、処理対象の係数群（４係数）内の全ての係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ２６１に戻り、それ以降の処理を繰り返す。
また、ステップＳ２６４において、処理対象の係数群（４係数）内の全ての係数が処理されたと判定された場合、ステップＳ２６５に進む。ステップＳ２６５において、MRパス部１２６は、処理対象ビットプレーンの全てのスプライトの全係数を処理したか否かを判定する。未処理の係数が存在すると判定された場合、ステップＳ２６１に戻り、それ以降の処理を繰り返す。
また、ステップＳ２６５において、全ての係数を処理したと判定された場合、MRパス処理が終了され、図１０のステップＳ１２７に戻り、ステップＳ１２８以降の処理が行われる。
このMRパス処理の場合も、CUパスやSPパスの場合と同様に、MQ符号化が、ビットモデリングの計算結果に関係なく実行される。EBCOT１０５は、MQ符号化の特徴を巧みに利用することにより、MRパス処理においても条件判定を不要としている。
これに対して従来のMRパス処理の流れは、図２０のフローチャートに示されるようになる。
つまり、MRエンコードを行うか否かの条件分岐（ステップＳ２８１）が存在している。この条件分岐は、スプライト内の縦方向の係数群（４係数）の各係数に対して行われる。したがって、この条件分岐によるオーバヘッドによって速度が大幅に低下する恐れがある。
これに対して、EBCOT１０５は、上述したように、各係数に対する処理（図１９のステップＳ２６１乃至ステップＳ２６３）において、全く条件分岐が発生していない。これにより、EBCOT１０５は、従来の方法よりも高速に符号化を行うことができる。
以上のように、EBCOT１０５は、コードブロック内の係数が持つ状態の遷移を新たに定義することで、これまでEBCOTエンコードで大きな問題点とされてきた係数単位の条件分岐を、事前に求めた計算結果に基づく処理によって完全に不要とすることができる。したがって、画像符号化装置１００は、より高速に符号化処理を行うことができる。
＜２．第２の実施の形態＞
［画像符号化装置の構成］
なお、さらに高速に符号化処理を行うことができるように、複数のコードブロックに対するEBCOTを並列に実行することができるようにしてもよい。
図２１は、本発明を適用した画像符号化装置の他の構成例を示すブロック図である。図２１に示される画像符号化装置２００は、基本的に図１の画像符号化装置１００と同様に、画像データをJPEG2000の方式で、可逆または非可逆に、符号化する符号化装置である。
ただし、画像符号化装置２００は、複数のコードブロックに対するEBCOTを並列に実行する。
従来、このEBCOTは、逐次処理を行う上、上位のビットプレーンの結果が下位のビットプレーンの結果に影響する「依存性」が存在するため、コードブロック内部の並列化が困難とされてきた。つまり、大きな解像度の画像のエンコードや可逆圧縮の場合、如何にしてJPEG2000の計算負荷、特にEBCOTの高速化を実現できるかが、鍵であった。
そこで、画像符号化装置２００は、コードブロックを適切にグループ化して並列演算用係数データを生成し、複数のEBCOTを並列に実行する。これにより、画像符号化装置２００は、EBCOTの高速化、すなわち、JPEG2000の計算負荷の軽減を実現することができる。
図２１に示されるように、画像符号化装置２００は、基本的に図１の画像符号化装置１００と同様の構成を有する。すなわち、画像符号化装置２００は、図１のウェーブレット変換部１０１と同様のウェーブレット変換部２０１、図１の量子化部１０２と同様の量子化部２０２、図１のコードブロック化部１０３と同様のコードブロック化部２０３、図１のビットプレーン展開部１０４と同様のビットプレーン展開部２０４を有する。
ただし、画像符号化装置２００は、図１のEBCOT１０５の代わりにEBCOT２０８を有し、図１の符号化コードストリーム生成部１０６の代わりに符号化コードストリーム生成部２０９を有する。
さらに、画像符号化装置２００は、パラメータ生成部２０５、グループ分け部２０６、および並列演算用係数データ生成部２０７を有する。
ウェーブレット変換部２０１は、入力された画像データ（矢印２２１）を、例えば５×３ウェーブレット変換フィルタを用いてフィルタリングを行い、ウェーブレット係数を生成する。ウェーブレット変換部２０１は、フィルタリングにより得られた係数データ（ウェーブレット係数）を、サブバンド毎に、量子化部２０２に供給する（矢印２２２）。
量子化部２０２は、供給された係数データ（ウェーブレット係数）を量子化する。量子化部２０２は、得られた係数データ（量子化係数）を、コードブロック化部２０３に供給する（矢印２２３）。なお、可逆圧縮の場合、量子化処理は省略され、ウェーブレット変換部２０１より出力された係数データ（ウェーブレット係数）は、コードブロック化部２０３に供給される（矢印２２４）。
コードブロック化部２０３は、供給された係数データを、予め定められた所定の大きさの矩形の、エントロピ符号化の処理単位であるコードブロックに分割する。コードブロック化部２０３は、係数データをコードブロック毎にビットプレーン展開部２０４に供給する（矢印２２５）。また、コードブロック化部２０３は、各コードブロックに関する情報をパラメータ生成部２０５に供給する（矢印２２６）。
ビットプレーン展開部２０４は、供給されたコードブロック毎の係数データを、ビットの位毎のビットプレーンに展開する。ビットプレーン展開部２０４は、展開したビットプレーンを、係数の最上位ビット（MSB：Most Significant Bit）から最下位ビット（LSB：Less Significant Bit）に向かう順に、並列演算用係数データ生成部２０７に供給する。つまり、ビットプレーン展開部２０４は、ビット深度の上位側から下位側に向かう順に、展開したビットプレーンを並列演算用係数データ生成部２０７に供給する（矢印２３０）。また、ビットプレーン展開部２０４は、このようにビットプレーン展開についての情報をパラメータ生成部２０５に供給する（矢印２２７）。
パラメータ生成部２０５は、コードブロック化部２０３およびビットプレーン展開部２０４から供給される情報に基づいて、各コードブロックの特徴を表すパラメータを生成する。
このパラメータとしては、コードブロックの特徴を表すものであればどのようなものであってもよいが、例えば、コードブロックの水平サイズ（h_size）、コードブロックの垂直サイズ（v_size）、サブバンドタイプ（LL,HL,LH.HH）、および、後述するように算出される符号化パス数(num_pass)を含むようにしてもよい。もちろん、これら以外のものがパラメータに含まれていてもよい。
これらのパラメータがどのコードブロックに対応するものであるかは、任意の方法で示されている。例えば、コードブロックの識別情報（コードブロック番号等）により関連付けられるようにしてもよい。
図２２は、横軸がコードブロック（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２０８は、係数データに対してビットモデリングを行い、係数のビットプレーンを算術符号化する。
ただし、EBCOT２０８は、EBCOT２０８−１乃至EBCOT２０８−１６を有する。EBCOT２０８−１乃至EBCOT２０８−１６は、それぞれ、係数データに対してビットモデリングを行い、係数のビットプレーンを算術符号化する。すなわち、EBCOT２０８は、最大１６並列でエントロピ符号化を行う。
なお、EBCOT２０８−１乃至EBCOT２０８−１６は、それぞれ、図１のEBCOT１０５と同様の構成を有し、同様にEBCOTを行う。つまり、EBCOT２０８−１乃至EBCOT２０８−１６は、それぞれ、コードブロック内の係数が持つ状態の遷移を新たに定義することで、これまでEBCOTエンコードで大きな問題点とされてきた係数単位の条件分岐を、事前に求めた計算結果に基づく処理によって完全に不要とすることができる。つまり、EBCOT２０８−１乃至EBCOT２０８−１６は、それぞれ、より高速に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２０８−１乃至EBCOT２０８−１６から供給された符号化データを、従来の場合の符号化データの並びと同様の並び順に並べ替え、１つのコードストリームとして出力する（矢印２３３）。
上述したように、従来の場合、ビットプレーン展開された係数データの各コードブロックが順番に符号化される。符号化コードストリーム生成部２０９は、このような手順で符号化されて生成された係数データと同じ並び順になるように、各符号化データの順序を並び替える。
この符号化データの並び替えは、例えば、EBCOT２０８−１乃至EBCOT２０８−１６により生成された各符号化データをメモリに一旦保持し、従来の符号化の順で読み出すことにより行われる。
なお、並列演算用係数データ生成部２０７によりダミーデータが挿入されてから、符号化が行われた場合、符号化コードストリーム生成部２０９は、そのダミーデータに対応する符号化データは削除する（コードストリームには含めない）。
［処理の流れ］
以上のような符号化処理の流れの例を図２６のフローチャートを参照して説明する。
符号化処理が開始されると、ウェーブレット変換部２０１は、ステップＳ３０１において、１ピクチャ分の画像データをウェーブレット変換する。ステップＳ３０２において、量子化部２０２は、ステップＳ３０１において生成された係数データを量子化する。なお、可逆符号化の場合、このステップＳ２０２の処理は省略される。
ステップＳ３０３において、コードブロック化部２０３は、係数データをコードブロック化する。ステップＳ３０４において、ビットプレーン展開部２０４は、係数データをビットプレーン展開する。
ステップＳ３０５において、パラメータ生成部２０５は、各コードブロックのパラメータ（例えば、h_size，v_size，num_pass、およびsub_type）を生成する。ステップＳ３０６において、グループ分け部２０６は、パラメータに基づいて、各コードブロックのグループ分けを行う。上述したように、グループ分け部２０６は、パラメータの値が全て一致する最大１６個のコードブロックを集めて１つのグループとする。
ステップＳ３０７において、並列演算用係数データ生成部２０７は、ステップＳ３０６において生成された各グループの中の未処理のグループから、処理対象のグループを選択する。
ステップＳ３０８において、並列演算用係数データ生成部２０７は、処理対象グループにコードブロックが１６個存在するか否かを判定する。存在すると判定された場合、ステップＳ３１０に進む。
また、ステップＳ３０８において、処理対象グループにコードブロックが１６個存在しないと判定された場合、ステップＳ３０９に進む。ステップＳ３０９において、並列演算用係数データ生成部２０７は、１６個に不足する数分のコードブロックのダミーデータを追加する。並列演算用係数データ生成部２０７は、例えば、全ての係数値が０のコードブロックをダミーデータとして処理対象グループのコードブロックに追加する。
ステップＳ３０９の処理により、処理対象グループのコードブロック数がダミーデータも含めて１６個になると、ステップＳ３１０に進む。
ステップＳ３１０において、並列演算用係数データ生成部２０７は、処理対象グループの各コードブロックの係数データを用いて並列演算用係数データを生成する。ステップＳ３１１において、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， １０６ 符号化コードストリーム生成部， １１１ ビットモデリング部， １１２ MQ符号化部， １２１ 状態遷移生成部， １２２ 状態遷移テーブル， １２３ 選択部， １２４ CUパス部， １２５ SPパス部， １２６ MRパス部， ２００ 画像符号化装置， ２０１ ウェーブレット変換部， ２０２ 量子化部， ２０３ コードブロック化部， ２０４ ビットプレーン展開部， ２０５ パラメータ生成部， ２０６ グループ分け部， ２０７ 並列演算用係数データ生成部， ２０８ EBCOT， ２０９ 符号化コードストリーム生成部

Claims (20)

  1. 画像データをサブバンド毎の係数データに変換するウェーブレット変換手段と、
    前記ウェーブレット変換手段により生成された前記係数データの前記サブバンドの領域をコードブロックに分割するコードブロック化手段と、
    処理対象の係数データに隣接する周囲のバイナリ係数データの値および状態に応じて、処理対象の係数データの状態を遷移させる状態遷移手段と、
    前記状態遷移手段により遷移された前記係数データの状態に従って、符号化パスを選択する選択手段と、
    前記選択手段により選択された符号化パスに従って、前記コードブロック化手段により生成されたコードブロック毎に、前記係数データを符号化する符号化手段と
    を備える符号化装置。
  2. 前記係数データの状態は、係数の正負符号（Sign）、状態変数１（State-0）、状態変数２（State-1）、および有効（Sig）の４つの変数によって定義される
    請求項１に記載の符号化装置。
  3. 前記係数データの状態は、状態変数１（State-0）、状態変数２（State-1）、および有効（Sig）の３つの変数と、前記係数データの７つの状態との対応関係を示すテーブル情報に基づいて、前記３つの変数の値から求められる
    請求項１に記載の符号化装置。
  4. 前記７つの状態のうち、第１の状態は、CUパスで符号化される状態であり、第２の状態は、無効なサンプルとされる状態であり、第３の状態は、周囲に有意なサンプルがあり、且つ現在のビットプレーンで未符号化時にはCUパスで符号化される状態であり、第４の状態は、周囲に有意なサンプルがあり、SPパスで符号化される状態であり、第５の状態は、有意であり、且つ既に現在のビットプレーンはSPパスで符号化済みの状態であり、第６の状態は、有意であり、MRパスで符号化され、次のMRパスが１回目である状態であり、第７の状態は、有意であり、MRパスで符号化され、次のMRパスが２回目である状態である
    請求項３に記載の符号化装置。
  5. 前記状態遷移手段は、処理対象の係数データの状態が前記第１の状態であって、前記CUパスで周囲の係数データのいずれかが有意になった場合、前記第３の状態に遷移させる
    請求項４に記載の符号化装置。
  6. 前記状態遷移手段は、処理対象の係数データが前記第１の状態であって、前記CUパスで有意になった場合、前記第５の状態に遷移させる
    請求項４に記載の符号化装置。
  7. 前記状態遷移手段は、処理対象の係数データが前記第３の状態であって、前記SPパスで符号化する場合、前記第４の状態に遷移させる
    請求項４に記載の符号化装置。
  8. 前記状態遷移手段は、処理対象の係数データが前記第３の状態であって、前記CUパスで有意になった場合、前記第５の状態に遷移させる
    請求項４に記載の符号化装置。
  9. 前記状態遷移手段は、処理対象の係数データが前記第５の状態であって、１つのビットプレーンの符号化がすべて終了した場合、前記第６の状態に遷移させる
    請求項４に記載の符号化装置。
  10. 前記状態遷移手段は、処理対象の係数データが前記第６の状態であって、１つのビットプレーンの符号化がすべて終了した場合、前記第７の状態に遷移させる
    請求項４に記載の符号化装置。
  11. 前記状態遷移手段により遷移された、処理対象のコードブロック内の各係数データの状態を保持する保持手段をさらに備え、
    前記選択手段は、前記保持手段により保持される前記係数データの状態に従って、符号化パスを選択する
    請求項１に記載の符号化装置。
  12. 前記符号化手段は、
    前記選択手段により選択された符号化パスに従って、前記係数データに対して所定の演算を行う演算手段と、
    前記演算手段による演算結果を用いて算術符号化を行う算術符号化手段と
    を備える請求項１に記載の符号化装置。
  13. 前記演算手段は、
    前記選択手段によりCUパスが選択された場合、前記係数データに対して所定の演算を行うCUパス演算手段と、
    前記選択手段によりSPパスが選択された場合、前記係数データに対して所定の演算を行うSPパス演算手段と、
    前記選択手段によりMRパスが選択された場合、前記係数データに対して所定の演算を行うMRパス演算手段と
    を備える請求項１２に記載の符号化装置。
  14. 前記CUパス演算手段は、前記コードブロックの４つの係数データに対して、ランレングス符号化の結果が０になる計算と、ランレングス符号化の結果が１になる計算の両方を実行し、
    前記算術符号化手段は、前記ランレングス符号化のコンテキストを用いて、値０の係数データをMQ符号化し、さらに、値１の係数データをMQ符号化する
    請求項１３に記載の符号化装置。
  15. 前記CUパス演算手段は、前記コードブロックの４つの係数データに対して、UNIFORMエンコード符号化を２回行い、
    前記算術符号化手段は、その２回各々に対して、UNIFORMのコンテキストを用いて、係数０または１をMQ符号化する
    請求項１３に記載の符号化装置。
  16. 前記CUパス演算手段は、前記コードブロックの係数データ毎に、CUエンコードを実行するか否かの計算を行い、
    前記算術符号化手段は、前記計算の結果に従って、Significanceコンテキストを用いてMQ符号化する
    請求項１３に記載の符号化装置。
  17. 前記CUパス演算手段は、前記コードブロックの係数データ毎に、Signエンコードを実行するか否かの計算を行い、
    前記算術符号化手段は、前記計算の結果に従ってSignコンテキストを用いてMQ符号化する
    請求項１３に記載の符号化装置。
  18. 前記SPパス演算手段は、前記係数データの値が１か否かの計算を行い、
    前記算術符号化手段は、前記計算の結果に従ってSignコンテキストを用いてMQ符号化する
    請求項１３に記載の符号化装置。
  19. 前記MRパス演算手段は、MRエンコードを実行するか否かの計算を行い、
    前記算術符号化手段は、前記計算の結果に従ってMRコンテキストを用いてMQ符号化する
    請求項１３に記載の符号化装置。
  20. 画像データをサブバンド毎の係数データに変換し、
    変換された前記係数データの前記サブバンドの領域をコードブロックに分割し、
    分割された前記コードブロック毎に、処理対象の係数データに隣接する周囲のバイナリ係数データの値および状態に応じて、処理対象の前記係数データの状態を遷移させ、
    遷移された前記係数データの状態に従って、符号化パスを選択し、
    選択された符号化パスに従って、生成されたコードブロック毎に、前記係数データを符号化する
    符号化方法。
JP2009242769A 2009-10-21 2009-10-21 符号化装置および方法 Withdrawn JP2011091576A (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2009242769A JP2011091576A (ja) 2009-10-21 2009-10-21 符号化装置および方法
US12/924,780 US20110091123A1 (en) 2009-10-21 2010-10-05 Coding apparatus and coding method
CN2010105118020A CN102045565A (zh) 2009-10-21 2010-10-14 编码装置和编码方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2009242769A JP2011091576A (ja) 2009-10-21 2009-10-21 符号化装置および方法

Publications (1)

Publication Number Publication Date
JP2011091576A true JP2011091576A (ja) 2011-05-06

Family

ID=43879337

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2009242769A Withdrawn JP2011091576A (ja) 2009-10-21 2009-10-21 符号化装置および方法

Country Status (3)

Country Link
US (1) US20110091123A1 (ja)
JP (1) JP2011091576A (ja)
CN (1) CN102045565A (ja)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8983213B1 (en) * 2010-08-30 2015-03-17 Accusoft Corporation Image coding and decoding methods and apparatus
US8934725B1 (en) 2010-08-30 2015-01-13 Accusoft Corporation Image coding and decoding methods and apparatus
JP5825965B2 (ja) * 2011-10-05 2015-12-02 キヤノン株式会社 ズームレンズ及びそれを有する撮像装置
CN102752599B (zh) * 2012-07-12 2014-11-12 浙江工商大学 一种二维图像小波系数重要性程度的随机计算方法
US9813718B2 (en) * 2013-10-03 2017-11-07 Samsung Display Co., Ltd. Apparatus and method for compact bit-plane data compression
CN105846828A (zh) * 2016-03-23 2016-08-10 北京裕源大通科技股份有限公司 Iq数据的压缩和解压缩方法、装置和iq数据的传输方法、系统
CN110365346B (zh) 2019-07-22 2021-07-06 浙江大华技术股份有限公司 一种算术熵编码方法及系统
CN112087636B (zh) * 2020-08-07 2022-01-11 北京博雅慧视智能技术研究院有限公司 一种图像编码的处理方法、装置、存储介质及终端

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5835636A (en) * 1996-05-28 1998-11-10 Lsi Logic Corporation Method and apparatus for reducing the memory required for decoding bidirectionally predictive-coded frames during pull-down
JP3906630B2 (ja) * 2000-08-08 2007-04-18 ソニー株式会社 画像符号化装置及び方法並びに画像復号装置及び方法
AUPQ982400A0 (en) * 2000-09-01 2000-09-28 Canon Kabushiki Kaisha Entropy encoding and decoding
US7308146B2 (en) * 2002-09-30 2007-12-11 Canon Kabushiki Kaisha Digital video compression
FR2857527B1 (fr) * 2003-07-11 2006-01-06 Cit Alcatel Compression contextuelle d'images numeriques
CN1560916A (zh) * 2004-02-27 2005-01-05 清华大学 一种用于集成电路设计的静止图像熵编码方法
CN1267858C (zh) * 2004-04-07 2006-08-02 西安交通大学 实时截断的jpeg2000速率控制方法
US7352903B2 (en) * 2004-08-17 2008-04-01 Pegasus Imaging Corporation Methods and apparatus for implementing JPEG 2000 encoding operations
US20060039613A1 (en) * 2004-08-17 2006-02-23 Withers William D Methods and apparatus for generating and using lists of coefficients to be coded
JP4745865B2 (ja) * 2006-02-28 2011-08-10 富士通セミコンダクター株式会社 符号化装置および方法

Also Published As

Publication number Publication date
CN102045565A (zh) 2011-05-04
US20110091123A1 (en) 2011-04-21

Similar Documents

Publication Publication Date Title
JP2011091576A (ja) 符号化装置および方法
Lian et al. Analysis and architecture design of block-coding engine for EBCOT in JPEG 2000
Schwartz et al. Implementation of compression with reversible embedded wavelets
KR101129655B1 (ko) 압축비가 높고 최소의 자원을 필요로 하는 고속 코덱
JP4025847B2 (ja) 符号化装置
US8098947B2 (en) Method and apparatus for processing image data by rearranging wavelet transform data
EP1279290A1 (en) Video encoding method using a wavelet transform
JP2011091575A (ja) 符号化装置および方法
Descampe et al. A flexible hardware JPEG 2000 decoder for digital cinema
JP4443165B2 (ja) 画像圧縮装置及び画像圧縮方法
JP5966345B2 (ja) 画像処理装置および方法
JP5950157B2 (ja) 画像処理装置および方法、並びに、プログラム
JP5966347B2 (ja) 画像処理装置および方法
Hussin et al. A comparative study on improvement of image compression method using hybrid DCT-DWT techniques with huffman encoding for wireless sensor network application
JP5966346B2 (ja) 画像処理装置および方法
US8249375B2 (en) Information processing apparatus and method
JP2010245855A (ja) 情報処理装置および方法
JP2011091577A (ja) 符号化装置および方法
JP4111761B2 (ja) 画像処理装置
CN1809169A (zh) 对画面进行无损直流分量编码的方法和设备
Mundy The study and HDL implementation of the JPEG 2000 MQ coder
JP2002223446A (ja) 画像圧縮装置および画像撮像装置
JP2004080185A (ja) 画像処理装置、画像処理方法、電子カメラ装置、プログラム、記録媒体
Matela Designing Image Compression Algorithms for Massively Parallel Processors
Rusnak Design and implementation of arithmetic coder for CUDA platform

Legal Events

Date Code Title Description
A300 Application deemed to be withdrawn because no request for examination was validly filed

Free format text: JAPANESE INTERMEDIATE CODE: A300

Effective date: 20130108