(57)【要約】【課題】従来のＣＡＢＡＣの算術符号化では、確率更新処理に続いてその結果を用いて再正規化処理を行うので、演算器を有効に活用した処理時間の短縮ができない。【解決手段】時間ｔ０において、最初のｂｉｎＶａｌのｂ０に対して、最初の確率更新Ｐ０がなされる。次に、時間ｔ１において、上記Ｐ０の結果を受けて上記ｂ０の再正規化Ｒ０を行う。同時に、時間ｔ１において、上記ｂ０に対する区間算出Ｅ０、及びｂ１に対する確率更新Ｐ１の各処理を連続して行う。以下、同様の動作が繰り返される。本発明では区間算出処理のみを独立に行うことができるため、区間算出処理を再正規化処理と並行して行うことで、再正規化のときに確率更新の待ち時間がなくなるので、再正規化の処理が常に行われ、演算器を常に動作させることができ、その結果処理時間を短縮できる。【選択図】図７
2008131526.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象の動画像信号と参照画像信号との間の動き予測信号を生成し、前記動画像信号と前記動き予測信号との差分信号に対して、所定画素数の符号化単位で直交変換及び量子化をして得られた量子化後信号に対して、算術符号化回路によりエントロピー符号化を行って符号化信号を生成する動画像符号化装置において、
前記算術符号化回路を、
前記量子化後信号を２値信号に変換する２値化部と、
前記量子化後信号であるシンボルに基づいて、出現確率が高いシンボルが示すシンボル値とシンボル出現確率の情報をインデックス化した、コンテキストインデックスを出力するコンテキスト生成部と、
前記２値信号と前記コンテキストインデックスとを入力として受け、所定の数直線の区間を、前記コンテキストインデックスと前記２値信号の値に基づいて分割することを再帰的に繰り返す確率更新処理と、前記確率更新処理により分割された前記区間の幅が所定値以下に狭くなった時に前記区間の幅を前記所定値よりも広げる再正規化処理と、前記区間の幅と前記区間の下限値とを算出する区間算出処理とを行って前記符号化信号を出力する際に、或る入力時点の第１の入力２値信号に対する前記再正規化処理と並行して、前記第１の入力２値信号に対する前記区間算出処理と、その区間算出処理により算出した前記区間の幅及び前記区間の下限値と前記第１の入力２値信号に続いて入力される第２の入力２値信号に対する前記コンテキストインデックスと該２値信号の値とを用いて処理する前記確率更新処理とを連続して行う算術符号化部と
を有する構成としたことを特徴とする動画像符号化装置。
【請求項２】
符号化対象の動画像信号と参照画像信号との間の動き予測信号を生成し、前記動画像信号と前記動き予測信号との差分信号に対して、所定画素数の符号化単位で直交変換及び量子化をして得られた量子化後信号に対して、算術符号化回路によりエントロピー符号化を行って符号化信号を生成する処理を、コンピュータを用いて行う動画像符号化プログラムにおいて、
前記コンピュータに、
前記量子化後信号を２値信号に変換する第１のステップと、
前記量子化後信号であるシンボルに基づいて、出現確率が高いシンボルが示すシンボル値とシンボル出現確率の情報をインデックス化した、コンテキストインデックスを出力する第２のステップと、
前記２値信号と前記コンテキストインデックスとを入力として受け、所定の数直線の区間を、前記コンテキストインデックスと前記２値信号の値に基づいて分割することを再帰的に繰り返す確率更新処理と、前記確率更新処理により分割された前記区間の幅が所定値以下に狭くなった時に前記区間の幅を前記所定値よりも広げる再正規化処理と、前記区間の幅と前記区間の下限値とを算出する区間算出処理とを行って前記符号化信号を出力する際に、或る入力時点の第１の入力２値信号に対する前記再正規化処理と並行して、前記第１の入力２値信号に対する前記区間算出処理と、その区間算出処理により算出した前記区間の幅及び前記区間の下限値と前記第１の入力２値信号に続いて入力される第２の入力２値信号に対する前記コンテキストインデックスと該２値信号の値とを用いて処理する前記確率更新処理とを連続して行う第３のステップと
を実行させて前記算術符号化を行うことを特徴とする動画像符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は動画像符号化装置及び動画像符号化プログラムに係り、特に動画像をコンテキスト適応２値算術符号化（ＣＡＢＡＣ）によりエントロピー符号化する動画像符号化装置及び動画像符号化プログラムに関する。
【背景技術】
【０００２】
近年、インターネットやＤＶＤ(Digital versatile Disc)レコーダなどの普及により、デジタル表現された動画像はますます一般的になっている。動画像を少ない符号量で効率的に表現する手法として、ＭＰＥＧ(Moving Picture Experts Group)などに代表される直交変換・エントロピー符号化方式が広く用いられている。しかし、従来のエントロピー符号化方式であるハフマン符号化は、符号化するシンボルに対して整数個のビットを割り当てることしかできないので、更なる符号化効率の向上に限界があった。
【０００３】
そこで、動画像符号化方式の新たな規格であるＨ.２６４／ＭＰＥＧ４−ＡＶＣにおいては、エントロピー符号化方式にＣＡＢＡＣ（Context Adaptive Binary Arithmetic Coding;コンテキスト適応型２値算術符号化）と呼ばれる算術符号化方式が導入された（例えば、非特許文献１参照）。この算術符号化方式は、情報の統計的な特徴に適応させ、またコンテキストというものを用いて情報間の統計的な特徴に適応させ、符号化するシンボルに対して非整数個のビットを割り当てることによって符号長を理論的に限界のエントロピーに近づけることができるので、高い符号化効率を実現できる。
【０００４】
ＣＡＢＡＣを始めとする算術符号化の基本原理について、図１０の例を用いて説明する。算術符号化は、再帰的な区間分割により成り立つ。まず、ｔ０（初期状態）において、確率の数直線（０，１）を用意する。そして、簡単のためシンボルを２値とすると、ｔ１において、シンボルＳ∋｛０，１｝に対する出現確率ｐ０とｐ１に応じて数直線を区間に分割し、そのシンボルにあたる区間を選択する。これをｔ２以降において、再帰的に繰り返し、対応する区間を符号とする。このとき、出現確率が高い方のシンボルをＭＰＳ（Most Probable Symbol）、出現確率が低い方のシンボルをＬＰＳ（Least Probable Symbol）という。本例の場合、ＭＰＳ＝０，ＬＰＳ＝１である。
【０００５】
しかし、この基本原理のみでは、算術符号化を実現することは困難である。なぜなら、数直線の区間を再帰的に分割して次第に区間が狭くなることで、その区間を表現するために際限なくビットを必要とするからである。そこで、実際の算術符号化では、区間分割によって区間が狭くなった時、再正規化（renormalization）と呼ばれる処理によって区間を２倍に広げるようにしている。同時に、符号化結果を逐次出力することで、算術符号化を実現している。再正規化は、必要なだけ繰り返し行われる。
【０００６】
算術符号化は、高い符号化効率を達成できる一方、ハフマン符号化と比較してその演算量が多くなるので、演算量の削減や処理時間の短縮が強く求められている。そこで、処理時間を短縮する手法として、ＭＰＳとＬＰＳを符号化する場合について、シンボル値とシンボル出現確率の新たな２通りの更新値を算出し、符号化結果が確定した後に、算出された２通りの更新値のうちいずれか適する方の更新値を選択する符号化装置が提案されている（例えば、特許文献１参照）。
【０００７】
また、区間分割を計算するビット領域の長さを予め拡張しておき、拡張した領域の分だけ再正規化による確率区間の拡大を一度に行い、その後で拡張領域のデータをまとめて符号出力する符号化装置が提案されている（例えば、特許文献２参照）。
【０００８】
【非特許文献１】ISO/IEC 14496-10：2004, Information technology--Coding of audio−visual objects--Part 10：Advanced Video Coding
【特許文献１】特開２００５−１３００９９号公報
【特許文献２】特開２００５−１８４２３２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかし、前述の特許文献１に記載の符号化装置は、符号化結果が確定するまで確率状態の更新ができないため、処理の並列化による効果が十分でなく、算術符号化の処理時間を短縮することに限界がある。
【００１０】
一方、前述の特許文献２に記載の符号化装置は、区間分割を計算するビット領域の長さを予め拡張しておく必要がある。その上、拡張領域のデータをまとめて符号出力することにより、符号化処理が特定の時間に偏って演算器が動作する時間と動作しない時間とができるので、演算器を有効に活用した処理時間の短縮ができない。そのため、特許文献２に記載の符号化装置では、算術符号化の処理時間を更に短縮することが課題である。
【００１１】
本発明は以上の点に鑑みなされたもので、ＭＰＳとＬＰＳのうち符号化シンボルである方のみを処理し、符号化結果が確定する前に確率状態の更新値を求めると共に、演算器が常に動作する構成をとることにより、算術符号化の処理時間を更に短縮し得る動画像符号化装置及び動画像符号化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の目的を達成するため、本発明の動画像符号化装置は、符号化対象の動画像信号と参照画像信号との間の動き予測信号を生成し、動画像信号と動き予測信号との差分信号に対して、所定画素数の符号化単位で直交変換及び量子化をして得られた量子化後信号に対して、算術符号化回路によりエントロピー符号化を行って符号化信号を生成する動画像符号化装置において、上記の算術符号化回路を、
量子化後信号を２値信号に変換する２値化部と、量子化後信号であるシンボルに基づいて、出現確率が高いシンボルが示すシンボル値とシンボル出現確率の情報をインデックス化した、コンテキストインデックスを出力するコンテキスト生成部と、２値信号とコンテキストインデックスとを入力として受け、所定の数直線の区間を、コンテキストインデックスと２値信号の値に基づいて分割することを再帰的に繰り返す確率更新処理と、確率更新処理により分割された区間の幅が所定値以下に狭くなった時に区間の幅を所定値よりも広げる再正規化処理と、区間の幅と区間の下限値とを算出する区間算出処理とを行って符号化信号を出力する際に、或る入力時点の第１の入力２値信号に対する再正規化処理と並行して、第１の入力２値信号に対する区間算出処理と、その区間算出処理により算出した区間の幅及び区間の下限値と第１の入力２値信号に続いて入力される第２の入力２値信号に対するコンテキストインデックスと２値信号の値とを用いて処理する確率更新処理とを連続して行う算術符号化部とを有する構成としたことを特徴とする。
【００１３】
また、上記の目的を達成するため、本発明の動画像符号化プログラムは、符号化対象の動画像信号と参照画像信号との間の動き予測信号を生成し、動画像信号と動き予測信号との差分信号に対して、所定画素数の符号化単位で直交変換及び量子化をして得られた量子化後信号に対して、算術符号化回路によりエントロピー符号化を行って符号化信号を生成する処理を、コンピュータを用いて行う動画像符号化プログラムにおいて、コンピュータに、
量子化後信号を２値信号に変換する第１のステップと、量子化後信号であるシンボルに基づいて、出現確率が高いシンボルが示すシンボル値とシンボル出現確率の情報をインデックス化した、コンテキストインデックスを出力する第２のステップと、２値信号とコンテキストインデックスとを入力として受け、所定の数直線の区間を、コンテキストインデックスと２値信号の値に基づいて分割することを再帰的に繰り返す確率更新処理と、確率更新処理により分割された区間の幅が所定値以下に狭くなった時に区間の幅を所定値よりも広げる再正規化処理と、区間の幅と区間の下限値とを算出する区間算出処理とを行って符号化信号を出力する際に、或る入力時点の第１の入力２値信号に対する再正規化処理と並行して、第１の入力２値信号に対する区間算出処理と、その区間算出処理により算出した区間の幅及び区間の下限値と第１の入力２値信号に続いて入力される第２の入力２値信号に対するコンテキストインデックスと２値信号の値とを用いて処理する確率更新処理とを連続して行う第３のステップとを実行させて算術符号化を行うことを特徴とする。
【００１４】
本発明の動画像符号化装置及び動画像符号化プログラムでは、或る入力時点の第１の入力２値信号に対する再正規化処理と並行して、第１の入力２値信号に対する区間算出処理と、その区間算出処理により算出した区間の幅及び区間の下限値と第１の入力２値信号に続いて入力される第２の入力２値信号に対するコンテキストインデックスと２値信号の値とを用いて処理する確率更新処理とを連続して行うようにしたため、再正規化のときに確率更新の待ち時間がなくなるので、再正規化の処理が常に行われ、演算器を常に動作させることができる。
【発明の効果】
【００１５】
本発明によれば、区間算出処理を再正規化処理と並行して（並列に）行うことで、再正規化のときに確率更新の待ち時間がなくなるので、再正規化の処理が常に行われ、演算器を常に動作させることができるようにしたため、演算器の使用効率が上がるので、ソフトウェア的には、並列処理が可能であれば処理時間を短縮することが可能となり、また、ハードウェア的には、並列処理を組むことによって、処理時間を短縮することが可能となる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の実施の形態について図面と共に説明する。図１は本発明になる動画像符号化装置の一実施の形態のブロック図を示す。この実施の形態は、算術符号化回路２３の構成に特徴がある。図１において、符号化対象の動画像信号は減算器１１において、必要に応じてスイッチ２２を介して供給されるイントラ予測部２１による画面内予測信号、あるいはＭＥ（動き推定）部１９による動き推定・ＭＣ（動き補償）部２０による画面間予測信号との差分が、所定の符号化単位（例えば、フレーム、マクロブロック、複数のマクロブロックをまとめたスライス、あるいはブロックなど）でとられた後、直交変換器１２に供給されて、例えば離散コサイン変換（ＤＣＴ:Discrete Cosine Transform）等の直交変換されて直交変換係数とされる。
【００１７】
なお、上記のマクロブロックは横１６画素、縦１６画素（以下、１６×１６と表記、他の画素数の場合も同様の表記とする）、１６×８、８×１６、８×８などの複数の種類（ＭＢタイプ）が存在しており、このＭＢタイプに応じて、１６×１６、１６×８、８×１６、８×８の各領域（ブロック）に分割して取り扱うことができる。
【００１８】
上記の直交変換係数は量子化器１３に供給されて量子化された後、逆量子化器１４及び後述する算術符号化回路２３にそれぞれ供給される。量子化器１３から出力された量子化後信号は、逆量子化器１４で逆量子化され、更に逆直交変換器１５で逆直交変換されて復号差分画像データにされた後、加算器１６でイントラ予測部２１あるいはＭＥ部１９・ＭＣ部２０からの予測画像信号と加算されて復号画像データとされる。この復号画像データは、デブロックフィルタ１７でブロック歪みを除去するための所定のフィルタ処理が施された後メモリ１８に格納される。
【００１９】
イントラ予測部２１は符号化対象の動画像信号に基づいて、またＭＥ部１９、ＭＣ部２０は符号化対象の動画像信号とメモリ１８からの復号画像データとに基づいて、公知の予測方法によりそれぞれ予測が行われる。
【００２０】
算術符号化回路２３は、本実施の形態特有の構成により、量子化器１３からの量子化後信号などの文脈エレメント（ＳＥ；Syntax Element）に基づいて、エントロピー符号化の一種である算術符号化処理を行い、処理結果の符号化信号が出力される。
【００２１】
次に、本実施の形態の要部である算術符号化回路２３について更に詳細に説明する。図２は算術符号化回路２３の一実施の形態のブロック図を示す。同図に示すように、算術符号化回路２３は、コンテキスト生成部２３１、２値化部２３２及び算術符号化部２３３から構成され、ＣＡＢＡＣによる算術符号化を行って得た符号化データをバイトスタッフィング部３１に供給する。本実施の形態は、算術符号化部２３３の構成に特徴がある。
【００２２】
ＣＡＢＡＣによる算術符号化は、以下の手順によりなされる。まず、符号化しようとする信号である文脈エレメントＳＥ（Syntax Element）３０がコンテキスト生成部２３１及び２値化部２３２にそれぞれ入力される。コンテキスト生成部２３１においては、入力された信号ＳＥに関するＭＰＳのシンボル値とシンボル出現確率の情報をインデックス化し、コンテキストインデックスｃｔｘｌｄｘを出力する。また、２値化部２３２においては、入力された信号ＳＥを２値化してバイナリ列ｂｉｎとし、そのバイナリ列ｂｉｎを１ビットずつｂｉｎＶａｌとして出力する。
【００２３】
そして、上記のｃｔｘｌｄｘ及びｂｉｎＶａｌが算術符号化部２３３にそれぞれ入力され、算術符号化がなされ（詳細は後述）、得られた符号化結果はバイトスタッフィング部３１に出力される。最後にバイトスタッフィング部３１にて、必要に応じて非特許文献１の規格を満たすフォーマットに合わされ、符号化信号であるバイトストリームＢＳ（Byte Stream）３２として出力される。
【００２４】
次に、算術符号化部２３３の動作について詳述する。まず、ＣＡＢＡＣにおける算術符号化の区間分割に用いる変数について、図３を用いて説明する。ＣＡＢＡＣによる符号化では、ＭＰＳ及びＬＰＳに対して、確率区間の下限値ｃｏｄＩＬｏｗ及びその区間ｃｏｌｄＲａｎｇｅが図３（Ａ）、（Ｂ）に示すように定められている。ここで、確率区間の下限値ｃｏｄＩＬｏｗは１０ビット、区間ｃｏｄＩＲａｎｇｅは９ビットである。また、ｖａｌＭＰＳは、ＭＰＳがシンボルＳ∋｛０，１｝のいずれかを示すもので、コンテキストインデックスｃｔｘｌｄｘにより与えられる。図３（Ａ）はｖａｌＭＰＳがｂｉｎＶａｌと等しい場合の各変数を示し、同図（Ｂ）はｖａｌＭＰＳがｂｉｎＶａｌと等しくない場合（すなわち、ｂｉｎＶａｌ！＝ｖａｌＭＰＳ）の各変数を示す。
【００２５】
ＣＡＢＡＣには、エンコード・デシジョン（EncodeDecision），エンコード・バイパス（EncodeBypass），エンコード・ターミネイト（EncodeTerminate）の３種類の方法があり、ＳＥの種類に応じて決められている。このうちＳＥが係数の正負を示すcoeff_sign_flagの時などに使用する算術符号化エンコード・バイパス（EncodeBypass）、及びＳＥがスライスの終端を示すend_of_slice_flagの時に使用する算術符号化エンコード・ターミネイト（EncodeTerminate）の２つは、特殊な場合の算術符号化である。
【００２６】
特殊な場合でない時に使用する算術符号化エンコード・デシジョン（EncodeDecision）については、図４のフローチャートに従ってなされる。このフローチャートは、コンテキスト生成部２３１からのｃｔｘｌｄｘ及び２値化部２３２からのｂｉｎＶａｌが入力されるたびに繰り返される。また、図４のフローチャートで示される非特許文献１に記載の算術符号化エンコード・デシジョン（EncodeDecision）は、確率更新部Ｓ１０による処理と、再正規化部Ｓ２０（ＲｅｎｏｒｍＥ）による処理とからなる。再正規化部Ｓ２０（ＲｅｎｏｒｍＥ）は、図５のフローチャートにより実行される再正規化処理を表す。さらに、図５のステップＳ２３、Ｓ２８に示す「ＰｕｔＢｉｔ」は非特許文献１に記載の公知の符号出力処理を表す。
【００２７】
非特許文献１に記載の算術符号化エンコード・デシジョン（EncodeDecision）の確率更新部Ｓ１０による処理では、まず、codIrangeの値を右へ６ビットシフトし、その下位２ビットをとった値をqCodIRangedxとし、規定されたテーブル値rangeTabLPSを用いてＬＰＳの確率幅codIRangeLPSを求めると共に、codIRangeをＭＰＳの確率幅に変更する（図４のステップＳ１１）。
【００２８】
続いて、入力シンボルbinValとvalMPSとが不一致であるかどうか判定し（図４のステップＳ１２）、binValとvalMPSとが等しい（一致する）場合は、入力シンボルｂｉｎがＭＰＳのときであり、規格で規定しているテーブル値transIdxMPSによって状態を遷移させ、pStateIdxを更新する（図４のステップＳ１７）。pStateIdxはＭＰＳの発生確率を持つテーブルのテーブル番号であり、その値が大きいほど、ＭＰＳの高い発生確率に対応するようにされている。
【００２９】
一方、binValとvalMPSとが不一致の場合は、入力シンボルｂｉｎがＬＰＳのときであり、codILowとcodIRangeとを加算した値をcodILowに代入し、codIRangeLPSをcodIRangeに代入する（図４のステップＳ１３）。ステップＳ１３に続いて、pStateIdxが０でないかどうか判定され（図４のステップＳ１４）、pStateIdxが０である場合は（１−valMPS）の値をvalMPSに代入する（図４のステップＳ１５）。ステップＳ１５の処理後、又はステップＳ１４でpStateIdxが０でないと判定した場合は、pStateIdxの値を更新する（図４のステップＳ１６）。ステップＳ１６又はＳ１７の処理後に、再正規化部（ＲｅｎｏｒｍＥ）による再正規化処理が実行される（図４のステップＳ２０）。
【００３０】
ステップＳ２０の再正規化処理では、図５のフローチャートに示すように、まず区間codIRangeが予め設定された第１の所定値（０ｘ１００）よりも小さいかどうか判定し（図５のステップＳ２１）、所定値よりも小さいときは確率区間の下限値codILowが第１の所定値（０ｘ１００）より小さいかどうか判定し（図５のステップＳ２２）、所定値以上であるときは確率区間の下限値codILowが第２の所定値（０ｘ２００）以上であるかどうか判定する（図５のステップＳ２４）。
【００３１】
codILowが第２の所定値未満であるときはcodILowをcodILowから第１の所定値を減算した値に更新した後（図５のステップＳ２５）、キャリーオーバー対策の変数であるbitOutstandingの値を１加算して更新する（図５のステップＳ２６）。一方、codILowが第２の所定値以上であるときはcodILowをcodILowから第２の所定値を減算した値に更新した後（図５のステップＳ２７）、PutBit(1)の処理を行う（図５のステップＳ２８）。また、ステップＳ２２で確率区間の下限値codILowが第１の所定値未満であると判定されたときはPutBit(0)の処理を行う（図５のステップＳ２３）。前述したように、上記の「PutBit(0)」、「PutBit(1)」は非特許文献１に記載の公知の符号出力処理を表し、その詳細の説明は本発明と直接の関係が無く、また公知であるので省略する。キャリーオーバー対策も同様である。
【００３２】
ステップＳ２３、Ｓ２６、又はＳ２８の処理に続いて、区間codIRangeを１ビット左へシフトして２倍とした値に更新すると共に、確率区間の下限値codILowも１ビット左へシフトして２倍とした値に更新する（図５のステップＳ２９）。その後、ステップＳ２１の処理に戻る。
【００３３】
次に、非特許文献１に記載の算術符号化エンコード・デシジョン（EncodeDecision）における処理の流れと本実施の形態の処理の流れとの差異について説明する。いま、図４の点線で囲まれた確率更新部Ｓ１０による処理を確率更新Ｐ、図５に示す再正規化処理を再正規化Ｒとする。さらに、前述の各記号Ｐ，Ｒに添字をつけることで、符号化処理の順を表すものとする。加えて、符号化処理の時間ｔの経過をｔ０，ｔ１，ｔ２，・・・とし、２値化部２３２から入力されるｂｉｎＶａｌを符号化順にｂ０，ｂ１，ｂ２，・・・として表すものとする。
【００３４】
これらの記号を用いて、非特許文献１に記載の従来の算術符号化の流れを表すと、確率更新Ｐの処理の流れは図６（Ａ）に、再正規化の処理の流れは同図（Ｂ）のようになる。まず、時間ｔ０において、ｂ０に対して確率更新Ｐ０がなされる。次に、時間ｔ１において、確率更新Ｐ０の結果を受けて、ｂ０の再正規化Ｒ０を行う。そして、時間ｔ２において、再正規化Ｒ０によって計算されたｃｏｄＩＲａｎｇｅ及びｃｏｄＩＬｏｗの値を受けて、ｂ１に対する確率更新Ｐ１の処理がなされる。以下、同様の動作が繰り返される。
【００３５】
これに対し、本実施の形態の算術符号化は、区間算出処理を再正規化処理と並列に行うことによってなされる。説明のため、上記と同様に、図４の点線で囲まれた処理Ｓ１０を確率更新Ｐとする。また、図５の処理を再正規化Ｒ、同図中のステップＳ２９の処理を区間算出処理Ｅとする。さらに、前述の各記号Ｐ，Ｒ，Ｅに添字をつけることで、符号化処理の順を表すものとする。加えて、符号化処理の時間ｔの経過をｔ０，ｔ１，ｔ２，・・・とし、ｂｉｎＶａｌを符号化順にｂ０，ｂ１，ｂ２，・・・として表すものとする。
【００３６】
これらの記号を用いて、本実施の形態の算術符号化の流れを表すと、確率更新Ｐと区間算出Ｅの処理の流れは図７（Ａ）に示され、再正規化の処理の流れは同図（Ｂ）に示される。この図７を用いて具体的に説明する。まず、時間ｔ０において、最初のｂｉｎＶａｌのｂ０に対して、最初の確率更新Ｐ０がなされる。次に、時間ｔ１において、上記Ｐ０の結果を受けて上記ｂ０の再正規化Ｒ０を行う。同時に、時間ｔ１において、上記ｂ０に対する区間算出Ｅ０、及びｂ１に対する確率更新Ｐ１の各処理を連続して行う。
【００３７】
同様に、時間ｔ２では、上記Ｐ１の結果を受けて２番目のｂｉｎＶａｌのｂ１に対して再正規化Ｒ１を行う。同時に、時間ｔ２において、上記ｂ１に対する区間算出Ｅ１、及びｂ２に対する確率更新Ｐ２の各処理を連続して行う。以下、同様の動作が繰り返される。
【００３８】
非特許文献１に記載のＲｅｎｏｒｍＥ（図５）によると、区間算出処理は再正規化処理に包含されているので、区間算出処理のみを行うことはできない。しかし、本実施の形態では、図７に示したように区間算出処理のみを独立に行うことができる。この区間算出処理のみを独立に行うことができる理由について、以下、詳細に説明する。
【００３９】
本実施の形態において、ｂ０に対する再正規化Ｒ０の処理と並行して、ｂ０に対する区間算出Ｅ０の処理を独立に行う方法を述べる。ここで、ビット列の最も上位のビットをＭＳＢ（Most Significant Bit）、ビット列の最も下位のビットをＬＳＢ（Least Significant Bit）という。区間算出Ｅ０の処理は、図５のフローチャートにより、確率区間codIRangeが下記に示すステップＳ２１の条件を満たす間は繰り返し処理がなされる。
【００４０】
ｃｏｄＩＲａｎｇｅ＜０ｘ１００
上記の条件を満たさなくなり、区間算出の処理が終了した後のcodIRangeの値は、次のようにして求めることができる。すなわち、９ビットである確率区間codIRangeのＭＳＢに最も近い“１”を特定し、その位置がＬＳＢから数えてｐｏｓビット目である（ただしＬＳＢを０ビット目）とすると、そのcodIRangeを（9−pos−1）ビットだけ左へシフトすることで区間算出の処理が終了した後のcodIRangeの値を求めることができる。これを数式で表すと
ｃｏｄＩＲａｎｇｅ＝ｃｏｄＩＲａｎｇｅ＜＜（９−ｐｏｓ−１）      （１）
となる。
【００４１】
あるいは、以下のようにして求めることができる。いま、確率区間codIRangeを、
【００４２】
【数１】
2008131526.tif 000003
とする。ここで、Ｒｉは、codIRangeのｉ番目のビットであり、ＭＳＢはｉ＝８、ＬＳＢはｉ＝０の場合である。これに対し、
【００４３】
【数２】
2008131526.tif 000004
を定義すると、
ｃｏｄＩＲａｎｇｅ＝ｃｏｄＩＲａｎｇｅ・Ｍ          （２）
である。なお、数２に示すように、Ｍはビット列ｒと、ビット列ｒを反転したものに１を加算した値とのＡＮＤをとった値を示す。
【００４４】
また、区間算出の処理が終了した後の確率区間の下限値codILowの値は、区間codIRangeとほぼ同様にして求めることができる。その方法を以下に述べる。図５において、codILowの値を求めるパターンは３種類ある。
【００４５】
（１）ｃｏｄＩＬｏｗ＜０ｘ１００の場合、ｃｏｄＩＬｏｗは変化しない（図５のステップＳ２２、Ｓ２３、Ｓ２９）。
【００４６】
（２）（１）でなく、かつ、ｃｏｄＩＬｏｗ＜０ｘ２００である場合、
ｃｏｄＩＬｏｗ＝ｃｏｄＩＬｏｗ−０ｘ１００
として求める（図５のステップＳ２２、Ｓ２４、Ｓ２５）。しかし、このときのｃｏｄＩＬｏｗは、
０ｘ１００≦ｃｏｄＩＬｏｗ＜０ｘ２００
であるから、ステップＳ２５でｃｏｄＩＬｏｗの下位８ビットの値を求めているに過ぎない。
【００４７】
（３）（１）でも（２）でもない場合、
ｃｏｄＩＬｏｗ＝ｃｏｄＩＬｏｗ−０ｘ２００
として求める（図５のステップＳ２２、Ｓ２４、Ｓ２７）。しかし、このときのｃｏｄＩＬｏｗは、
ｃｏｄＩＬｏｗ≧０ｘ２００
であるから、ステップＳ２７でｃｏｄｌＬｏｗの下位９ビットの値を求めているに過ぎない。
【００４８】
従って、上記（１）〜（３）のいずれのパターンにおいても、上述した確率の区間codIRangeと同じ式を計算し、ビットマスクして或る特定のビットを取り出すようにすればよい。ここで、確率区間の下限値codILowのＭ以上のビットが全て“１”でない限り、区間算出の処理が終了した後の値がｃｏｄＩＬｏｗ≧０ｘ２００とはならないことを考えれば、０ｘ１ＦＦによりビットマスクすればよいことが分かる。すなわち、次式が成立する。
【００４９】
【数３】
2008131526.tif 000005
この数３に示す（３）式の確率区間の下限値codILowは、図５のフローチャートによる再正規化処理の最終結果を示す。なお、０ｘ１ＦＦによりビットマスクせずに、確率区間の下限値codILowから０ｘ２００を引く、つまり
【００５０】
【数４】
2008131526.tif 000006
としてもよい。
【００５１】
これにより、ｂ０に対する区間算出Ｅ０の処理が終了した後の区間codIRange及び確率区間の下限値codILowの値は、ｂ０に対する再正規化Ｒ０の処理が終了する前に求めることができる。
【００５２】
よって、本実施の形態によれば、ｂ０に対する図５のフローチャートによる再正規化Ｒ０の処理と並行して、ｂ０に対する（１）式又は（２）式による確率の区間codIRangeの算出と、ｂ０に対する数３で示す（３）式による確率区間の下限値codILowの算出を行う区間算出Ｅ０の処理と、それに続いてＥ０の処理により求めたcodIRange及びcodILowの値と、ｂ０の次の信号ｂ１に対するbinVal及びctxldxとを用いた図４中のＳ１０による確率更新Ｐ１の処理とを行うことができる。
【００５３】
ゆえに、本実施の形態によれば、再正規化処理の前に確率更新の待ち時間がないので、再正規化の処理が常に行われ、演算器を常に動作させることができる。以上が、図７の時間ｔ１における動作である。時間ｔ２以降、同様のタイミングで順次処理を行う。
【００５４】
このようにして、本実施の形態によれば、ＭＰＳとＬＰＳのうち符号化シンボルである方のみを処理し、符号化結果が確定する前に確率状態の更新値を求めることができる。また、区間算出処理を再正規化処理と並行して（並列に）行うことで、再正規化処理の前に確率更新の待ち時間がなくなるので、再正規化の処理が常に行われ、演算器を常に動作させることができる。
【００５５】
その結果、演算器の使用効率が上がるので、ソフトウェア的には、並列処理が可能であれば処理時間を短縮することが可能となる。また、ハードウェア的には、並列処理を組むことによって、処理時間を短縮することが可能となる。
【００５６】
上記の実施形態における図5の再正規化処理について、ステップS21における条件判定（再正規化処理のループ回数の制御）にｃｏｄＩＲａｎｇｅの値を用いたが、数２で示した式中のＭの値を用いてもよい。また、上記の実施の形態において示したビットマスクの方法により、再正規化処理のｃｏｄＩＬｏｗを計算してもよい。換言すると、図５のステップＳ２２からステップＳ２９の直前までのいずれのループを通っても、ステップＳ２９において
【００５７】
【数５】
2008131526.tif 000007
として計算してもよい。
【００５８】
なお、上述のエンコード・デシジョン（EncodeDecision）により算術符号化されたデータを復号化するには、図８及び図９のフローチャートに従って処理を行う。ただし、図４〜図９のフローチャートのうち、算術復号化は非特許文献１の規格の範囲であるが、算術符号化はあくまで参考のための説明（informative）であり、規格の範囲ではない。
【００５９】
復号化部では、図８のフローチャートに示すデコード・デシジョン(DecodeDecision)テーブルを引いて復号化対象のシンボルのＭＰＳの区間幅を求め（図８のステップＳ３１）、確率区間の下限値が確率の区間以上であるかどうか判定し（図８のステップＳ３２）、区間以上であれば、ＬＰＳシンボルをデコード結果として出力し（図８のステップＳ３３）、ＬＰＳのオフセット値をＭＰＳの区間幅を使って求める（図８のステップＳ３４）。
【００６０】
そして、ＭＰＳとＬＰＳのシンボルが逆になるかどうか判定し（図８のステップＳ３５）、逆にならない場合は次のシンボルを復号化する際のＬＰＳの区間幅を変える（図８のステップＳ３７）。ステップＳ３５で逆になると判定した場合は、そのシンボルを逆にし（図８のステップＳ３６）、ステップＳ３７に進む。一方、ステップＳ３２で確率区間の下限値が確率の区間未満であると判定したときは、ＭＰＳシンボルをデコード結果として出力し（図８のステップＳ３８）、次のシンボルを復号化する際のＭＰＳの区間幅を変える（図８のステップＳ３９）。
【００６１】
上記のステップＳ３７又はＳ３９の処理終了後、ＲｅｎｏｍｅＤの処理が行われる（図８のステップＳ４０）。このＲｅｎｏｍｅＤの処理は図９のフローチャートに従って行われる。すなわち、まず、区間幅(codIRange)が所定値より小さいかどうか判定し（図９のステップＳ４１）、小さいときには区間幅を２倍にし、また１ビットを読み込む（図９のステップＳ４２）。大きい時には処理を終了する。
【００６２】
なお、本発明は以上の実施の形態の処理をコンピュータにより実行させる算術符号化プログラムも含むものである。この場合、算術符号化プログラムは記録媒体に記録されてコンピュータに取り込まれてもよいし、ネットワークを介して配信してコンピュータにダウンロードしてもよい。
【図面の簡単な説明】
【００６３】
【図１】本発明の動画像符号化装置の一実施の形態のブロック図である。
【図２】図１の要部である算術符号化回路の一実施の形態のブロック図である。
【図３】ＣＡＢＡＣにおける算術符号化の区間分割に用いる変数を説明する図である。
【図４】ＣＡＢＡＣにおける算術符号化EncodeDecisionの処理の流れを示すフローチャートである。
【図５】図４の中にある再正規化RenormEの処理の流れを示すフローチャートである。
【図６】非特許文献１に記載のEncodeDecisionによる算術符号化の処理を行った場合のタイムチャートである。
【図７】本発明の一実施の形態によりEncodeDecisionの算術符号化の処理を行った場合のタイムチャートである。
【図８】EncodeDecisionによって符号化された場合の復号化処理である、算術復号化DecodeDecisionの処理の流れを示すフローチャートである。
【図９】図８の中にある再正規化RenormDの処理の流れを示すフローチャートである。
【図１０】算術符号化の基本原理を説明するための図である。
【符号の説明】
【００６４】
１２  直交変換器
１３  量子化器
１９  ＭＥ部
２０  ＭＣ部
２１  イントラ予測部
２２  算術符号化回路
３０  ＳＥ
２３１  コンテキスト生成部
２３２  ２値化部
２３３  算術符号化部
３１  バイトスタッフィング部
Ｓ１０  確率更新処理
Ｓ２０  再正規化処理
Ｐ０、Ｐ１、Ｐ２  確率更新
Ｒ０、Ｒ１  再正規化
Ｅ０、Ｅ１  区間算出
【図１】
2008131526.tif 000008
【図２】
2008131526.tif 000009
【図３】
2008131526.tif 000010
【図４】
2008131526.tif 000011
【図５】
2008131526.tif 000012
【図６】
2008131526.tif 000013
【図７】
2008131526.tif 000014
【図８】
2008131526.tif 000015
【図９】
2008131526.tif 000016
【図１０】
2008131526.tif 000017