TOP > 国内特許検索 > 算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体 > 明細書

明細書 :算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4547503号 (P4547503)
登録日 平成22年7月16日(2010.7.16)
発行日 平成22年9月22日(2010.9.22)
発明の名称または考案の名称 算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体
国際特許分類 H03M   7/40        (2006.01)
H04N   7/26        (2006.01)
FI H03M 7/40
H04N 7/13 Z
請求項の数または発明の数 9
全頁数 35
出願番号 特願2008-503883 (P2008-503883)
出願日 平成19年3月6日(2007.3.6)
国際出願番号 PCT/JP2007/054358
国際公開番号 WO2007/102518
国際公開日 平成19年9月13日(2007.9.13)
優先権出願番号 2006061780
優先日 平成18年3月7日(2006.3.7)
優先権主張国 日本国(JP)
審査請求日 平成20年7月4日(2008.7.4)
特許権者または実用新案権者 【識別番号】304020292
【氏名又は名称】国立大学法人徳島大学
発明者または考案者 【氏名】宋 天
【氏名】山田 篤
【氏名】島本 隆
個別代理人の代理人 【識別番号】100104949、【弁理士】、【氏名又は名称】豊栖 康司
【識別番号】100074354、【弁理士】、【氏名又は名称】豊栖 康弘
審査官 【審査官】渡辺 未央子
参考文献・文献 特開2005-130099(JP,A)
特開2005-504471(JP,A)
特開2005-525018(JP,A)
山田篤, 他,H.264/AVCにおけるCABAC高速処理アーキテクチャ,電子情報通信学会総合大会講演論文集,2006年 3月 8日,D-11-39,p.39
Tian Song, et al.,Efficient Multistate Estimated Architecture of CABAC for H.264/AVC Encoder,Journal of Signal Processing,2008年 1月,Vol.12, No.1,pp.65-71
調査した分野 H03M 7/40
H04N 7/26
特許請求の範囲 【請求項1】
多値信号を2値化するための2値化部と、
前記2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、
コンテキスト番号を生成するためのコンテキスト計算部と、
前記2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、
前記コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、前記シンボル値と前記シンボル出現確率とを格納するための確率状態格納部と、
を備える算術符号化装置であって、
前記算術符号化部は、
劣勢シンボルの区間を発生確率に基づいて分割した領域rLPSの予測値を格納する第1格納部と、
同じくrLPSの予測値を格納する、前記第1格納部とは別個の第2格納部と、
前記第1格納部及び第2格納部に格納されたrLPSの予測値を参照して算術符号化を行う演算部と、
を備えてなることを特徴とする算術符号化装置。
【請求項2】
多値信号を2値化するための2値化部と、
前記2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、
コンテキスト番号を生成するためのコンテキスト計算部と、
前記2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、
前記コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、前記シンボル値と前記シンボル出現確率とを格納するための確率状態格納部と、
を備える算術符号化装置であって、
前記算術符号化部は、
優勢シンボル処理時の優勢シンボル処理連続数、初期の区間、シンボル出現確率に基づいて決定される更新区間の予測値を格納する更新区間格納部と、
優勢シンボル処理時の優勢シンボル処理連続数、及び初期のシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するためのコンテキスト更新テーブルと、
再正規化の回数に基づいて、更新区間の補集合であるlowを更新する再正規化テーブルを有する再正規化部と、
を備えることを特徴とする算術符号化装置。
【請求項3】
多値信号を2値化するための2値化部と、
前記2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、
コンテキスト番号を生成するためのコンテキスト計算部と、
前記2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、
前記コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、前記シンボル値と前記シンボル出現確率とを格納するための確率状態格納部と、
を備える算術符号化装置であって、
前記算術符号化部は、
優勢シンボル処理時の優勢シンボル処理連続数、初期の区間、シンボル出現確率に基づいて決定される更新区間の予測値を格納する第1更新区間格納部と、
同じく更新区間の予測値を格納する、前記第1更新区間格納部と別個の第2更新区間格納部と、
優勢シンボル処理時の優勢シンボル処理連続数、及び初期のシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するための第1コンテキスト更新テーブルと、
優勢シンボル処理時の優勢シンボル処理連続数、及び前記第1コンテキスト更新テーブルで更新されたシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するための、前記第1コンテキスト更新テーブルと別個の第2コンテキスト更新テーブルと、
再正規化の回数に基づいて、更新区間の補集合であるlowを更新する再正規化テーブルを有する再正規化部と、
を備えることを特徴とする算術符号化装置。
【請求項4】
多値信号を2値化するための2値化部と、
前記2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、
コンテキスト番号を生成するためのコンテキスト計算部と、
前記2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、
前記コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、前記シンボル値と前記シンボル出現確率とを格納するための確率状態格納部と、
を備える算術符号化装置であって、
前記算術符号化部が、
劣勢シンボルの区間を発生確率に基づいて分割した領域rLPSの予測値を格納する第1格納部と、
同じくrLPSの予測値を格納する、前記第1格納部とは別個の第2格納部と、
前記第1格納部及び第2格納部に格納されたrLPSの予測値を参照して算術符号化を行う演算部と、
を備える2サイクル予測部と、
優勢シンボル処理時の優勢シンボル処理連続数、初期の区間、シンボル出現確率に基づいて決定される更新区間の予測値を格納する更新区間格納部と、
優勢シンボル処理時の優勢シンボル処理連続数、及び初期のシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するためのコンテキスト更新テーブルと、
再正規化の回数に基づいて、更新区間の補集合であるlowを更新する再正規化テーブルを有する再正規化部と、
を備える連続優勢シンボル処理予測部と
前記2サイクル予測部と連続優勢シンボル処理予測部のいずれかを切り替える予測手法切替部と、
を備えることを特徴とする算術符号化装置。
【請求項5】
2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、
その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号化方法であって、
符号化対象のシンボルが優勢シンボルである場合の優勢シンボル処理時の区間座標値、及び劣勢シンボルである場合の劣勢シンボル処理時の区間座標値を予め記録した第1rLPSテーブルを参照して、第1シンボルの区間を更新した分割領域を求める工程と、
得られた分割領域と、第1rLPSテーブルと別個の第2rLPSテーブルを参照して、第1シンボルに続く第2シンボルの区間を更新した分割領域を求める工程と、
必要に応じて再正規化を行い、出力符号を出力する工程と、
コンテキスト番号を更新する工程と、
を含むことを特徴とする算術符号化方法。
【請求項6】
2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、
その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号化方法であって、
2値シンボルの優勢シンボルが連続する場合に、優勢シンボルの連続数とコンテキスト番号に基づいて、更新区間格納部を参照して更新区間の予測値を求める工程と、
コンテキスト番号を格納するコンテキスト更新テーブルを用いて更新する工程と、
を含むことを特徴とする算術符号化方法。
【請求項7】
2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、
その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号プログラムであって、
符号化対象のシンボルが優勢シンボルである場合の優勢シンボル処理時の区間座標値、及び劣勢シンボルである場合の劣勢シンボル処理時の区間座標値を予め記録した第1rLPSテーブルを参照して、第1シンボルの区間を更新した分割領域を求める機能と、
得られた分割領域と、第1rLPSテーブルと別個の第2rLPSテーブルを参照して、第1シンボルに続く第2シンボルの区間を更新した分割領域を求める機能と、
必要に応じて再正規化を行い、出力符号を出力する機能と、
コンテキスト番号を更新する機能と、
をコンピュータに実現させることを特徴とする算術符号化プログラム。
【請求項8】
2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、
その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号化プログラムであって、
2値シンボルの優勢シンボルが連続する場合に、優勢シンボルの連続数とコンテキスト番号に基づいて、更新区間格納部を参照して更新区間の予測値を求める機能と、
コンテキスト番号を格納するコンテキスト更新テーブルを用いて更新する機能と、
をコンピュータに実現させることを特徴とする算術符号化プログラム。
【請求項9】
請求項7又は8に記載されるプログラムを格納したコンピュータで読み取り可能な記録媒体。
発明の詳細な説明 【技術分野】
【0001】
本発明は、動画像符号化・復号に用いられる算術符号化技術に関するものであり、特に、動画像符号化規格であるH.264/AVCにおけるCABAC(Context-based Adaptive Binary Arithmetic Coding:コンテキスト準拠適応2進算術符号化)に準拠した算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体に関する。
【背景技術】
【0002】
近年、DVDや地上デジタルハイビジョン等の高画質動画像の普及が急速に進んでおり、動画像の高ビットレート、高解像度によって情報量が飛躍的に増加し、効率のよい動画像データの圧縮が必須となっている。デジタル動画像圧縮の主な構成技術は、予測符号化、動き処理、変換符号化、量子化、符号割当の5つがある。この内、符号割当は、量子化レベルなどに「0」、「1」の符号を効率よく割り当て、冗長な符号の削減をする。符号割当には可変長符号化、適応符号化、固定長符号化等が知られている。可変長符号化(VLC:Variable Length Cording)はハフマン符号化、ランレングス符号化、算術符号化、適応ビット割当等に区分される。この内、算術符号化は、シンボルの出現確率に応じて符号化テーブルを作成し符号割当を行うものである。
【0003】
算術符号化は、画像データの特徴に応じた最適な符号割当ができるため、固定した符号化テーブルを使用するハフマン符号化などに比べて符号化効率が優れている。しかしながら算術符号化は、シンボルの出現確率を計算しながら符号化テーブルを作成し符号割当をする動的な方式のため、一般的にハフマン符号化と比較して多大な計算処理を必要とするという問題がある。
【0004】
一方、ITU-T(International Telecommunication Union - Telecommunication Standardization Sector)では、動画像符号化・復号技術としてH.264の規格策定を行っている(非特許文献1参照)。特許文献1には、ITU-T規格H.264による算術符号化・復号の処理プロセスの具体的な実現方法の実例が開示される。図26は、H.264/AVCによる算術符号化・復号の処理プロセスのフローチャートである。同図は、非特許文献1のFig.9-1を、機能を中心に再編集したものである。図26を用いて、算術符号化・復号の流れを以下に説明する。
【0005】
あるシンタックス要素(Syntax Element:SE)について、符号化又は復号が開始されると、ステップ1において、そのシンタックス要素に対して、コンテキスト計算が行われる。コンテキスト計算では、コンテキストに対応するコンテキスト番号が求められ、コンテキスト番号によりシンボル値と確率状態が求められる。シンボル値は、一部の例外はあるものの、多くは対応表を参照することによって求められる。確率状態は、後述のステップ3で格納されている値を参照して求められる。求められたシンボル値と確率状態は、算術符号化・復号プロセスに与えられ、ステップ2に進む。
【0006】
ステップ2においては、ステップ1より受け取ったシンボル値と確率状態を用いて、当該シンタックスの算術符号化又は復号を行い、結果を出力信号として出力する。同時に、符号化又は復号したシンボルの情報を、シンボル出現確率制御プロセスに出力し、ステップ3に進む。
【0007】
ステップ3においては、符号化または復号したシンボルの情報を受けて、次の処理で用いるシンボル値と確率状態の更新値を求め、確率状態として格納しておく。
【0008】
ステップ4において、当該シンタックス要素の符号化又は復号が完了したかどうかを判定し、完了してない場合には、ステップ1に戻り、符号化又は復号が完了するまで同様のプロセスを繰り返す。当該シンタックス要素の符号化又は復号が完了すると、次のシンタックス要素について符号化又は復号を行う。
【0009】
図27に、H.264/AVCの算術符号化の処理プロセスを具現化した算術符号化装置のブロック図を示す。この算術符号化装置700は、適応算術符号化・復号部710、コンテキスト計算部720、及び符号化・復号制御部730を備え、適応算術符号化・復号部710は、算術符号化・復号部711、シンボル出現確率制御部712、及び確率状態格納部713を有する。コンテキスト計算部720は、入力信号(Sin)S11のシンタックス要素(SE)の種別と既符号化ビット数又は復号ビット数より、コンテキスト番号を生成する(図26のステップ1の処理に相当する)。
【0010】
この算術符号化装置700では、各処理ステップは、その前のステップでの処理結果を受けて、そのステップでの処理を開始する必要があるため、その動作は、シーケンシャルな処理となり、一つのシンタックス要素が処理される時間は、各処理ステップの和となる。すなわち、例えば、シンタックス要素0の処理に必要な区間S0は、処理51と処理52と処理53と処理54とのそれぞれに費やされる時間の和となる。
【0011】
符号化又は復号の時間当たりの処理符号量(即ちシンタックス要素数)が多い場合、符号化又は復号の処理時間を短縮することは、必須の要件となる。本検討例の算術符号化・復号装置40では、各ステップは、シーケンシャルな処理を行っているため、全体の処理時間の短縮のためには、各ステップの処理時間を短縮しなければならず、現状の技術レベルでは、高速化には限界がある。
【0012】
これに対して、特許文献1には、算術符号化処理を高速化した算術符号化装置が開示される。この算術符号化装置800は、図28のブロック図に示すように適応算術符号化部810、コンテキスト計算部820、及び符号化制御部830を備える。コンテキスト計算部820は、レジスタ821と比較判定部822とを有する。適応算術符号化部810は、算術符号化部811とシンボル出現確率制御部814と確率状態格納部815とを有する。これによれば、ある入力信号が算術符号化部811で符号化される間に、コンテキスト計算部820は、次の入力信号についてコンテキストを求めることができるので、算術符号化部811は、ある入力信号を符号化後、直ちに次の入力信号の符号化処理を行える。従って、符号化処理の高速化が可能となる。
【0013】
さらに、ある信号が算術符号化部811で符号化される間に、シンボル出現確率制御部814は、算術符号化部811による符号化シンボルが、優勢シンボルである場合と劣勢シンボルである場合とについて、それぞれのシンボル値と確率状態の更新値を求めておき、符号化シンボルが確定した後に、一方の更新値を選択する。この結果、算術符号化部811は、次の符号の符号化において、必要なシンボル値と確率状態を得て、直ちに符号化処理と確率状態記録部815への書込み処理を行えるため、算術符号化処理の更なる高速化が可能となる。

【特許文献1】特開2005-130099号公報
【非特許文献1】Joint Video Team(JVT) of ISO/IEC MPEG & ITU-TVCEG; "DraftI TU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264|ISO/IEC 14496-10 MPEG-AVC)."
【非特許文献2】Hassan Shojania and Subramania Sudharsanan, "A VLSI Architecture for High Performance CABAC Encoding." Visual Communications and Image Processing 2005, Proc. of SPIE Vol. 5960, pp.1444.
【非特許文献3】大久保榮他「改訂版 H.264/AVC教科書」インプレス
【非特許文献4】「技術分野別特許マップ 電気14 デジタル動画像圧縮技術」特許庁
【非特許文献5】Roberto R. Osorio, Javier D. Bruguera, "High-Throughput Architecture for H.264/AVC CABAC Compression System" IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 16, NO. 11, NOVEMBER 2006.
【発明の開示】
【発明が解決しようとする課題】
【0014】
しかしながらこの方法でも、1サイクルで1ビットの符号化を実現するものでなく、高速化対策としては十分ではない。一方、非特許文献2では1サイクルで1バイナリシンボルを処理可能な高速化手法が提案されているが、この手法でも十分でなく1サイクルで複数の処理を行うには至っておらず、十分な高速処理が実現できるとは言い難い。
【0015】
H.264/AVCの符号化処理処理においては、エントロピー符号化である可変長符号化(VLC)が採用されている。VLCは、実際にH.264/AVCのビットストリームを生成しているモジュールである。この符号化方式としてCABACとCAVLCがある。CAVLC(Context-Adaptive Variable Length Coding:コンテキスト適応型可変長符号化方式)は、量子化されたDCT係数値の符号化にのみ用いられる。一方CABAC(Context Adaptive Binary Arithmetic Coding:コンテキスト適応型2値算術符号化方式)は、算術符号化を用いたエントロピー符号化方式であり、CAVLCと比較して符号化効率が高いという利点を有する。
【0016】
しかしながら、CABAC処理は高い符号化効率を得ることができる反面、処理時間が長いという問題がある。特に高解像度アプリケーションにおいて、リアルタイムに符号化を行うには、処理に極めて高い動作周波数を要する。既存のMPUやCPUでは、計算上数GHzもの動作周波数が要求されることとなって、ハイビジョン放送などのメディアに対応できないという問題があった。このため、CABAC処理を高速に行うための構成が切望されているものの、上述の通り従来の手法では未だ不十分であった。
【0017】
本発明は、このような問題点を解消するためになされたものである。本発明の主な目的は、H.264/AVCにおけるCABACの処理の演算量を削減し、実装を容易にした算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【0018】
上記の目的を達成するために、本発明の第1の算術符号化装置は、多値信号を2値化するための2値化部と、2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、コンテキスト番号を生成するためのコンテキスト計算部と、2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、シンボル値とシンボル出現確率とを格納するための確率状態格納部とを備える算術符号化装置であって、算術符号化部は、劣勢シンボルの区間を発生確率に基づいて分割した領域rLPSの予測値を格納する第1格納部と、同じくrLPSの予測値を格納する、第1格納部とは別個の第2格納部と、第1格納部及び第2格納部に格納されたrLPSの予測値を参照して算術符号化を行う演算部とを備える。これにより、1サイクル中に2ビット以上の処理が可能な高速な算術符号化を実現できる。
【0019】
さらに第2の算術符号化装置は、多値信号を2値化するための2値化部と、2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、コンテキスト番号を生成するためのコンテキスト計算部と、2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、シンボル値とシンボル出現確率とを格納するための確率状態格納部とを備える算術符号化装置であって、算術符号化部は、優勢シンボル処理時の優勢シンボル処理連続数、初期の区間、シンボル出現確率に基づいて決定される更新区間の予測値を格納する更新区間格納部と、優勢シンボル処理時の優勢シンボル処理連続数、及び初期のシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するためのコンテキスト更新テーブルと、再正規化の回数に基づいて、更新区間の補集合であるlowを更新する再正規化テーブルを有する再正規化部とを備える。これにより、連続して優勢シンボル処理が行われる場合の算術符号化処理を数サイクル削減でき、処理の低減と高速化が図られる。
【0020】
さらにまた第3の算術符号化装置は、多値信号を2値化するための2値化部と、2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、コンテキスト番号を生成するためのコンテキスト計算部と、2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、シンボル値とシンボル出現確率とを格納するための確率状態格納部とを備える算術符号化装置であって、算術符号化部は、優勢シンボル処理時の優勢シンボル処理連続数、初期の区間、シンボル出現確率に基づいて決定される更新区間の予測値を格納する第1更新区間格納部と、同じく更新区間の予測値を格納する、第1更新区間格納部と別個の第2更新区間格納部と、優勢シンボル処理時の優勢シンボル処理連続数、及び初期のシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するための第1コンテキスト更新テーブルと、優勢シンボル処理時の優勢シンボル処理連続数、及び前記第1コンテキスト更新テーブルが更新したシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するための、第1コンテキスト更新テーブルと別個の第2コンテキスト更新テーブルと、再正規化の回数に基づいて、更新区間の補集合であるlowを更新する再正規化テーブルを有する再正規化部とを備える。これにより、連続して優勢シンボル処理が行われる場合の算術符号化処理を、複数の異なるコンテキストが使用される場合でも削減できる。
【0021】
さらにまた第4の算術符号化装置は、多値信号を2値化するための2値化部と、2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、コンテキスト番号を生成するためのコンテキスト計算部と、2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、シンボル値とシンボル出現確率とを格納するための確率状態格納部とを備える算術符号化装置であって、算術符号化部が、劣勢シンボルの区間を発生確率に基づいて分割した領域rLPSの予測値を格納する第1格納部と、同じくrLPSの予測値を格納する、第1格納部とは別個の第2格納部と、第1格納部及び第2格納部に格納されたrLPSの予測値を参照して算術符号化を行う演算部とを備える2サイクル予測部と、優勢シンボル処理時の優勢シンボル処理連続数、初期の区間、シンボル出現確率に基づいて決定される更新区間の予測値を格納する更新区間格納部と、優勢シンボル処理時の優勢シンボル処理連続数、及び初期のシンボル出現確率に基づいて決定されるシンボル出現確率の予測値を格納するためのコンテキスト更新テーブルと、再正規化の回数に基づいて、更新区間の補集合であるlowを更新する再正規化テーブルを有する再正規化部とを備える連続優勢シンボル処理予測部と、2サイクル予測部と連続優勢シンボル処理予測部のいずれかを切り替える予測手法切替部とを備える。これにより、2サイクル予測又は連続優勢シンボル処理予測を適宜切り替えて、サイクル数を効率よく削減して更に高速な算術符号化が実現できる。
【0022】
一方、算術符号化方法は、2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号化方法であって、符号化対象のシンボルが優勢シンボルである場合の優勢シンボル処理時の区間座標値、及び劣勢シンボルである場合の劣勢シンボル処理時の区間座標値を予め記録した第1rLPSテーブルを参照して、第1シンボルの区間を更新した分割領域を求める工程と、得られた分割領域と、第1rLPSテーブルと別個の第2rLPSテーブルを参照して、第1シンボルに続く第2シンボルの区間を更新した分割領域を求める工程と、必要に応じて再正規化を行い、出力符号を出力する工程と、コンテキスト番号を更新する工程とを含む。これにより、1サイクル中に2ビット以上の処理が可能な高速な算術符号化を実現できる。
【0023】
また算術符号化方法は、2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号化方法であって、2値シンボルの優勢シンボルが連続する場合に、優勢シンボルの連続数とコンテキスト番号に基づいて、更新区間格納部を参照して更新区間の予測値を求める工程と、コンテキスト番号を格納するコンテキスト更新テーブルを用いて更新する工程とを含む。これにより、連続して優勢シンボル処理が行われる場合の算術符号化処理を数サイクル削減でき、処理の低減と高速化が図られる。
【0024】
さらに、算術符号化プログラムは、2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号プログラムであって、符号化対象のシンボルが優勢シンボルである場合の優勢シンボル処理時の区間座標値、及び劣勢シンボルである場合の劣勢シンボル処理時の区間座標値を予め記録した第1rLPSテーブルを参照して、第1シンボルの区間を更新した分割領域を求める機能と、得られた分割領域と、第1rLPSテーブルと別個の第2rLPSテーブルを参照して、第1シンボルに続く第2シンボルの区間を更新した分割領域を求める機能と、必要に応じて再正規化を行い、出力符号を出力する機能と、コンテキスト番号を更新する機能とをコンピュータに実現させる。これにより、1サイクル中に2ビット以上の処理が可能な高速な算術符号化を実現できる。
【0025】
さらにまた算術符号化プログラムは、2値シンボルの算術符号化にあたり、出現確率の高いシンボルである優勢シンボルと出現確率の低いシンボルである劣勢シンボルとを、前シンボルまでの数線上の区間及び劣勢シンボルの数線上の区間の座標値に基づいて、数線上の所定の区間に対応させ、その数線上の区間対応結果と入力される2値シンボルから符号化信号を出力する算術符号化プログラムであって、2値シンボルの優勢シンボルが連続する場合に、優勢シンボルの連続数とコンテキスト番号に基づいて、更新区間格納部を参照して更新区間の予測値を求める機能と、コンテキスト番号を格納するコンテキスト更新テーブルを用いて更新する機能とをコンピュータに実現させる。これにより、連続して優勢シンボル処理が行われる場合の算術符号化処理を数サイクル削減でき、処理の低減と高速化が図られる。
【0026】
またコンピュータで読み取り可能な記録媒体は、上記プログラムを格納するものである。記録媒体には、CD-ROM、CD-R、CD-RWやフレキシブルディスク、磁気テープ、MO、DVD-ROM、DVD-RAM、DVD-R、DVD+R、DVD-RW、DVD+RW、Blue-ray(登録商標)、HD DVD(登録商標)(AOD)等の磁気ディスク、光ディスク、光磁気ディスク、半導体メモリその他のプログラムを格納可能な媒体が含まれる。またプログラムには、上記記録媒体に格納されて配布されるものの他、インターネット等のネットワーク回線を通じてダウンロードによって配布される形態のものも含まれる。さらに記録媒体には、上記プログラムがソフトウェアやファームウェア等の形態で実行可能な状態に実装された汎用もしくは専用機器を含む。さらにまたプログラムに含まれる各処理や機能は、コンピュータで実行可能なプログラムソフトウエアにより実行してもよいし、各部の処理を所定のゲートアレイ(FPGA、ASIC)等のハードウエア、又はプログラム・ソフトウエアとハードウェアの一部の要素を実現する部分的ハードウエア・モジュールとが混在する形式で実現してもよい。
【発明の効果】
【0027】
本発明の算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体によれば、H.264/AVCにおけるCABACの処理のサイクル数を削減し、処理の低負荷化、高速化を図ることができる。
【発明を実施するための最良の形態】
【0028】
以下、本発明の実施の形態を図面に基づいて説明する。ただし、以下に示す実施の形態は、本発明の技術思想を具体化するための算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体を例示するものであって、本発明は算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体を以下のものに特定しない。また、本明細書は請求の範囲に示される部材を、実施の形態の部材に特定するものでは決してない。特に実施の形態に記載されている構成部品の寸法、材質、形状、その相対的配置等は特に特定的な記載がない限りは、本発明の範囲をそれのみに限定する趣旨ではなく、単なる説明例にすぎない。なお、各図面が示す部材の大きさや位置関係等は、説明を明確にするため誇張していることがある。さらに以下の説明において、同一の名称、符号については同一もしくは同質の部材を示しており、詳細説明を適宜省略する。さらに、本発明を構成する各要素は、複数の要素を同一の部材で構成して一の部材で複数の要素を兼用する態様としてもよいし、逆に一の部材の機能を複数の部材で分担して実現することもできる。
【0029】
本明細書において算術符号化装置に接続される操作、制御、入出力、表示、その他の処理等のためのコンピュータ、プリンタ、外部記憶装置その他の周辺機器との接続は、例えばIEEE1394、RS-232x、RS-422、RS-423、RS-485、USB等のシリアル接続、パラレル接続、あるいは10BASE-T、100BASE-TX、1000BASE-T等のネットワークを介して電気的に接続して通信を行う。接続は有線を使った物理的な接続に限られず、IEEE802.1x、OFDM方式等の無線LANやBluetooth等の電波、赤外線、光通信等を利用した無線接続等でもよい。さらに検索対象のテキストや画像データの保存やデータベース構築、検索等に関する設定の保存等を行うための記録媒体には、メモリカードや磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等が利用できる。
(動画像符号化/復号装置)
【0030】
図1に、H.264/AVCの符号化処理処理により、画像データからビットストリームを得る動画像符号化/復号装置を構成するブロック図の一例を、図1に示す。この図に示す動画像符号化/復号装置100は、メモリ管理を行うDMA1(Direct Memory Access)と、動き探索部2(ME)と、デブロッキングフィルタ3(DF:Deblocking Filter)と、動き補償部4(MC)と、変換部5と、量子化部6と、逆量子化部7と、逆変換部8と、全体制御部9と、可変長符号化部(VLC:Variable Length Coder)である算術符号化/復号装置10と、可変長復号化部11(VLD:Variable Length Decoder)とを備える。算術符号化/復号装置10は、算術符号化技術としてCABACやCAVLCを行う。動画像符号化/復号装置100は、ハードウェアで構成する他、プロセッサでソフトウェア的に処理することも可能である。この場合は、コンピュータにインストールされた算術符号化プログラムにて、算術符号化を行う。なおコンピュータには、汎用のパーソナルコンピュータやワークステーションの他、携帯電話やスマートフォン、PDA、通信機能付カーナビゲーションやデータ通信可能な固定電話等の、動画像を表示可能な機器が適宜利用できる。
【0031】
動画像符号化/復号装置100では、まず符号化処理を行う動画像が入力され、動き探索部2において動き検出処理を行う。この処理で求められた動きベクトルを用い、動き補償部4、変換部5、量子化部6において、動き補償処理、変換処理、量子化処理を行う。量子化処理を行ったブロック係数、および符号化に使用するすべての情報が算術符号化/復号装置10に集められ、ビットストリームを作成する。次のフレームの符号に用いる参照フレームを作成するため、逆符号化部7、逆変換部8、動き補償部4を用いて、その逆処理を行い、参照フレームを作成し、フレームメモリFMに保管する。フレームメモリFMに保管する前に、デブロッキングフィルタ3を用いれば、ブロックノイズを軽減する効果が得られる。
【0032】
この動画像符号化/復号装置100では、符号化以外に復号処理も可能となる。その処理手順は、まず入力されるビットストリームを復号処理を行う可変長復号化部11より解析し、ビットストリームにある画像情報を復号し、参照フレーム生成手順と同じく逆量子化部7、逆変換部8、動き補償部4を用いて画像フレームを復元し、フレームメモリFMに保管する。このように、算術符号化技術には、符号化されたデータの復号も含まれる。本明細書においては、算術符号化装置、方法、プログラム等は、算術符号化のみならず、復号を行う装置、方法、プログラムも含むものとして説明する。
(算術符号化方式)
【0033】
本実施の形態では、H.264/AVCにおけるCABAC処理の高速化を図る。CABACは算術符号化方式である。基本的な算術符号化であるエリアス符号化・復号化の概念を、図2に示す。算術符号化では、一般に下限値0以上、上限値1未満の実数直線を考える。この区間を初期のrangeとする。算術符号化においては、優勢シンボル(Most Possible Symbol:MPS)、劣勢シンボル(Least Possible Symbol:LPS)の発生確率に基づいて実数直線を分割する。分割した領域をそれぞれrMPS、rLPSとする。その後、符号化出力対象となるシンボルが属する領域を選択する。ここでは仮にrMPSを選択したとする。その後、選択したrMPSを次のrangeとし、このrangeに対して同様にrMPS、rLPSに分割し、符号化出力対象となる領域を選択する。この動作を符号化出力対象が無くなるまで繰り返し、最終的に特定された領域であるrangeの範囲内に収まる値を出力値valueとして出力することで符号化が完了する。通常はrangeの下限値を出力値valueとして出力する。このような基本的な算術符号化は、区間のrangeや入力値であるvalueが実数値であり、演算精度の問題から現実的ではない。そこで実数直線を有限のビット幅を持つ整数区間とし、特定した区間の幅であるrangeと特定した区間の下限値であるvalueに対して正規化処理を導入することで問題を解決している。正規化処理は、左シフト演算により行われ、この正規化処理によって、rangeとvalueの演算精度を確保している。CABACでは、複数のコンテキスト変数情報を利用して符号化効率の向上を図っている。
【0034】
次に算術符号化(AC:Arithmetic Coding)を行う手順を、図3に基づいて説明する。CABACにおいて用いられる2値算術符号化の場合、与えられた2値シンボルの発生確率に基づいて、入力信号に応じて実数0.0から1.0の間で区間を逐次分割していく。ここで、入力信号00010とすると、”0”の発生確率が0.8、”1”の発生確率が0.2となる。このため、入力信号の内”0”が符号化されると、前の区間の下0.8の部分が、新しい区間として更新される。一方、”1”が符号化されると、前の区間の上0.2が新しい区間として更新される。
【0035】
図3の最初のステップ1では”0”を符号化する。この結果、初期区間の0.0-1.0の下側0.8の部分(0.0~0.8)が新しい区間として更新される。
【0036】
次にステップ2で”0”を符号化する。この結果、現在の区間(0.0~0.8)の下側で0.8×0.8=0.64の部分(0.0~0.64)が更新された区間となる。
【0037】
同様にステップ3で”0”を符号化する。この結果、現在の区間(0.0~0.64)のさらに下側で0.64×0.8=0.512の部分(0.0~0.512)が更新区間となる。
【0038】
次にステップ4では”1”を符号化する。この結果、現在の区間(0.0~0.512)の上側で、0.512×0.2=0.1024の部分、すなわち((0.512-0.1024=0.4096)~0.512)=(0.4096~0.512)が更新区間となる。
【0039】
そしてステップ5で再び”0”を符号化する。この結果、現在の区間(0.4096~0.512)の下側で0.1024×0.8=0.08192の部分(0.4096~(0.4096+0.08192))=(0.4096~0.49152)が更新区間となる。
【0040】
最後に、ステップ6で符号を決定する。算術符号の符号語は、最終区間を特定する実数値の2進表現となる。この例では、最終の更新区間が(0.4096~0.49152)となるので、その間に含まれる実数の中で最も2進表現が短くなる0.4375をとることができる。0.4375の2進表現は0.0111になるので、常に0となる最初の桁を除いた、小数点以下の”0111”が符号語として出力される。
(算術符号化装置のブロック図)
【0041】
次に、CABAC処理を行う算術符号化装置の例を、図4に示す。この図に示すように算術符号化装置10Aは、多値信号を2値シンボルに変換する2値化部12と、符号化すべき2値シンボルの発生確率を周囲の状況すなわちコンテキストに応じて計算・更新するためのコンテキスト計算部14と、これら2値シンボルと2値シンボル発生確率に基づいて算術符号化を行う2値算術符号化部16で構成されている。
【0042】
2値算術符号化部16の詳細を図5に示す。この図に示すように、2値算術符号化部16はrLPSテーブル20と、コンテキスト変更テーブル30と、演算部40と、再正規化部50とを有する。
(再正規化)
【0043】
CABAC内部の2値算術符号化部も、算術符号化にあたっては上記と同様の動作を行う。ただ、実際に区間区間を保持する記憶素子であるレジスタの桁数が有限であるため、出力すべき区間の上位ビットが確定した段階で適時確定ビットを出力し、更新区間の幅を広げる再正規化(Renormalization)の処理が加わる。
【0044】
再正規化の手順を、図6に基づいて説明する。ステップ1で0を符号化した結果、更新区間が(0~0.8)となる。次にステップ2で1を符号化した結果、区間(0.0~0.8)の上側0.2の部分(0.64~0.8)が更新区間となる。この段階で、出力すべき区間の代表値が0.5以上になることが確定する。すなわち、先頭のビットが”1”であることが確定するため、この時点でステップ3として、”1”を出力すると共に、(0.5~1.0)の区間を(0.0~1.0)に拡大するようマッピング(対応付け)する。ここでは、(0.64~0.8)の区間を(((0.64-0.5)×2=0.28)~((0.8-0.5)×2=0.6))=(0.28~0.6)に拡大する。このように、処理の途中で(この例ではステップ2で1を符号化した時点で)区間の座標値が0.5(2進表現で0.1)以上となることが判明するので、その時点で小数点第1位の”1”を出力する。同時に、区間から0.5を減算して2倍することにより、区間を実質的に拡張でき、使用可能な桁数を大きくできる。一方、区間の座標値が0.25よりも小さくなると、先頭ビットが”0”であることが判明する。この処理によって、区間の幅を表す実数の桁数が増え続けることを防ぐことができ、有限桁数の演算で符号化を行うことが可能となる。
【0045】
以上の例では、説明のため2値シンボルの発生確率は固定のものとしたが、実際には一動作ごとに適応的に変更させることも可能である。2値算術符号化部に2値シンボルの発生確率を与える役割は、コンテキスト計算部14が行っている。
(CABACの動作)
【0046】
CABACの動作としては、更新区間を更新する、すなわちrange(更新区間)とlow(更新区間以外)に区分する動作として、MPS(Most Possible Symbol)処理とLPS(Least Possible Symbol)処理の2種類がある。上記図3の例では、0を符号化する処理がMPSに該当し、1を符号化する処理がLPSに相当する。
【0047】
MPS処理時には、以下の式によってrangeとlowが決定される。
range=range-rLPS
low=low
【0048】
一方、LPS処理時には以下の式でrangeとlowが決定される。
range=rLPS
low=low+range-rLPS
これらの処理のいずれが行われるかは、コンテキストとrangeによって決定される。コンテキストは、2値シンボルの発生確率を示しており、シンボルの処理時に更新される。
【0049】
コンテキストは図4に示すコンテキスト計算部14で保持、更新される。コンテキスト計算部14は、2値シンボルの発生確率を複数保持しており、現在の符号化対象や周囲の状況すなわちコンテキストに応じて発生確率を切り替え、2値算術符号化部16に与える。2値シンボルの発生確率は、発生確率テーブルに保持され、発生確率が高い0、1いずれかのシンボル(MPS:Most Probable Symbol:発生確率が最も高いシンボル)と、その発生確率テーブル番号(pStateIdx)とが対応付けて保持される。発生確率テーブル番号を指定すると、対応する発生確率が得られる。
(従来のCABAC処理)
【0050】
次に、CABAC処理を行う従来の算術符号化装置において、2値算術符号化部16が、コンテキスト計算部14から与えられた発生確率(コンテキスト)に従って、2値化部12から与えられる2値シンボルの符号化を行い、区間を更新する手順を、図7のブロック図及び図8の動作図に基づいて説明する。
【0051】
図7に示す算術符号化装置200は、演算部40と、rLPSテーブル20と、コンテキスト更新部70とを備える。また算術符号化装置200は、入力端子として、区間を入力するrange入力及び/又はlow入力、2値列入力、コンテキスト入力を備えている。range入力、low入力はそれぞれ、演算部40、rLPSテーブル20に接続される。また2値列入力は演算部40、rLPSテーブル20、コンテキスト更新部70に接続される。さらにコンテキスト入力は、rLPSテーブル20、コンテキスト更新部70に接続される。ここでrLPSテーブル20は、指定されたrangeとコンテキストに応じて、rLPSを選択するテーブルである。また演算部40は再正規化部を備え、再正規化の際に符号ビットを生成し、演算部40から出力符号を出力する。コンテキストは、range、lowの更新後に更新される。コンテキスト更新部70は、前段の処理結果に基づいてコンテキストを更新して出力する。
【0052】
演算部40は、算術符号化演算を行う。ここでは、入力された区間range及び/又はlow、これに対応するrLPSをrLPSテーブル20を参照して決定し、これらに基づいて区間を更新し、range’とlow’を出力する。
【0053】
この処理を、図8の動作図に基づいて説明する。ここでは、所定の区間に対して、(サイクル1)MPS処理と、(サイクル2)LPS処理及び再正規化を行う処理を説明している。すなわち、まずサイクル1で、rangeとlowが決定されている区間に対して、2値シンボルA及び対応するコンテキストXの場合に演算部40がMPS処理して符号化を行い、区間をrange’とlow’に更新する。ここでは、
range’=range-rLPS、
low’=low
となる。一方でコンテキスト更新部70がコンテキストXを更新する。そしてサイクル2で、このrange’とlow’を2値シンボルB及び対応するコンテキストYの場合に演算部40がLSP処理で符号化を行って、区間をrange”とlow”に更新する。ここでは
range”=rLPS’、
low”=low’+range’-rLPS’
となる。また一方、コンテキスト更新部70がコンテキストYを更新する。
【0054】
さらに再正規化を行って区間をrange”’とlow”’に拡大する。この結果、
range”’=(range”-0.5)×2
low”’=(low”-0.5)×2
となる。さらに演算部40が出力符号”1”を出力する。このように従来のCABAC処理では、上記の処理を完了するまでに2サイクルを要した。
【0055】
一方で近年の画像の高精細化に伴ってH.264/AVCの符号化処理をリアルタイムで行うなど、高速化の要求が高く、CABAC処理の演算量を削減することが求められている。しなしながら、上記の構成ではrange、lowの値が前の処理に依存するため、演算をパイプライン化できないという問題があった。すなわち、隣接するシンボルの算術符号化においては、2シンボル目の処理にはrange、lowだけでなくrLPSの値までも前の処理(1シンボル目の処理)に依存する。このため、1サイクル間に2シンボル以上の処理は困難とされていた。
【0056】
言い換えると、従来、CABACの実行速度の高速化手法としては、CABAC装置の各処理部の処理やメモリアクセス、符号化器部分の動作並列化等に着目し、如何に効率よくデータ処理を行うかという手法を主眼として、1シンボル/1サイクルの処理の実現が研究されている。しかしながら、CABACのシンボル処理は、常に過去のシンボルの出現確率に依存する特徴があり、各シンボルの処理時に更新が必要なコンテキスト、rLPSは、直前のシンボルの処理結果を得なければならない。このため従来は、前段の処理に依存する性質上、演算処理のハードウェアを増やすことでは処理の効率化は望めないと考えられており、十分に満足できる高速化が実現されていないにもかかわらず、1シンボル/1サイクルの処理速度が高速化の限界であると理解されていた。
【0057】
これに対し本発明では、シンボルの出現確率の演算手順を分析し、シンボル間の依存性の詳細関係を解明した。これにより、状況によりシンボル間の依存性を失くし、事前に次サイクルの処理を実行し、テーブルの更新も同時に実現できる手法を開発するに至った。
(2サイクル予測)
【0058】
本実施の形態では、2シンボルの処理に必要な情報を一括して入力し、1サイクル間に2シンボルの処理を行うため、コンテキスト更新テーブル、rLPSテーブル、演算部をそれぞれ2つ設けている。ここではrangeとlowを演算するために必要なコンテキスト、すなわち2値列とシンタックス要素と周囲の状況(コンテキスト)に基づいて、生成された2値列に使用するコンテキストを決定するためのrLPSテーブルを予め作成し、処理時にはこれを参照することで先の演算の予測を可能としている。さらにrLPSテーブルを2つ用意することで、2サイクル分の処理を行うための異なるrLPSを、同時に参照可能とした。例えば、一方のテーブルをMPS処理用のLPSを記録した第1rLPSテーブルとし、他方をLPS処理用のLPSを記録した第2rLPSを保持したテーブルとしており、1サイクル中にMPS処理、LPS処理両方に対応できる。また各rLPSテーブルはマルチポート(デュアルポート)メモリを利用し、2つのアクセスポートから同時に書き込みと読み出しを可能としている。これにより、一方のアクセスポートからデータを読み書きしているときに、他方のアクセスポートを使用してデータの読み出しなどが行なえる。これにより、2つのプロセッサが同じメモリに同時にアクセス可能となり、2サイクル分の処理を1サイクル内で完了でき、処理サイクル数を低減してCABAC処理の高速化を図っている。
【0059】
なおコンテキストをメモリから2つ同時に読み出し、且つ2つ同時に書き込むには、更新コンテキストの内容により、最大で従来の4倍程度のメモリ量が必要になると見込まれる。またメモリ量を従来の2倍のみ使用した場合には、同じコンテキストの更新が必要となる際に2サイクルの処理を要し、処理速度の低減になる。同様に3シンボルの処理も可能であるが、コンテキストのメモリ量は従来の6倍程度となる。このように、パフォーマンスとハードウェア仕様のバランス、及び要求される処理能力や速度などに応じて、適切な構成に設計する必要がある。好ましくは、一括に入力する情報は2シンボル分とし、2サイクル予測と、後述する連続MPS処理予測を併用して、これらを切り替えることにより、画像にあまり依存せず、高い処理速度を保つことができる。以下、順次説明する。
(実施の形態1)
【0060】
図9に、本実施の形態1に係る算術符号化装置を示す。この図に示す算術符号化装置は、多値信号を2値シンボルに変換する2値化部112と、符号化すべき2値シンボルの発生確率を周囲の状況(コンテキスト)に応じて計算・更新するためのコンテキスト計算部114と、これら2値シンボルと2値シンボル発生確率に基づいて算術符号化を行う算術符号化部116と、コンテキストを保持する第1メモリ部117と、range及びlowを保持する第2メモリ部118と、2サイクル予測を行う予測部119と、出力バッファ121とを備える。この算術符号化装置は、多値信号及び/又は符号化対象のシンタックス要素を2値化部112で入力すると、2値列に変換して算術符号化部116と予測部119に送られる。また必要に応じて周囲の状況(コンテキスト)もコンテキスト計算部114に入力される。そして予測部119でrangeの予測を行う一方、算術符号化部116で算術符号化を行い、得られた結果を符号ビットとして各々出力バッファ121に出力する。なお、必要に応じて入力側にバッファを設けることも可能であることは言うまでもない。
(第1メモリ部117)
【0061】
第1メモリ部117は、コンテキストを保持するコンテキストテーブルとして機能する。コンテキストテーブルは必要に応じて随時更新される。このため第1メモリ部117には更新が可能なメモリ、例えばRAMなどが使用される。第1メモリ部117の例を図10に示す。この図に示すように第1メモリ部117内にはコンテキスト#1、#2、#3、・・・が保持され、各コンテキストが2値列(0,1)と対応付けられる。この際、1のコンテキストに複数の2値列を割り当てることも可能である。
【0062】
第2メモリ部118は、コンテキストを保持する第2コンテキスト更新テーブルとして機能する。range、low値の保持には、レジスタなどが使用できる。
【0063】
また、図11の変形例に示すように、第1メモリ部と第2メモリ部を共通のメモリ部117Aとして構成し、コンテキストとrange、lowを一のメモリ内に各々保持することも可能である。
【0064】
第1メモリ部117にはデュアルポート型メモリを使用する。これによって、コンテキストテーブルに同時にリード/ライトを行うことが可能となる。
(算術符号化部116)
【0065】
図9の算術符号化部116の詳細を、図12のブロック図及び図13の動作図に基づいて説明する。図12に示す算術符号化部116は、演算部140と、第1rLPSテーブル120と、第2rLPSテーブル122と、符号ビット生成部160と、コンテキスト更新部170とを備える。また算術符号化部116は、入力端子として、区間を入力するrange入力及び/又はlow入力、2値列入力、コンテキスト入力としてコンテキストX入力、コンテキストY入力を備えている。range入力は、演算部140、第1rLPSテーブル120、第2rLPSテーブル122、符号ビット生成部160に接続される。一方low入力は、演算部140、第2rLPSテーブル122、符号ビット生成部160に接続される。また2値列入力は演算部140、第2rLPSテーブル122、符号ビット生成部160、コンテキスト更新部170に接続される。さらにコンテキストX入力は、第1rLPSテーブル120、第2rLPSテーブル122、符号ビット生成部160、コンテキスト更新部170に接続される。一方コンテキストY入力は、第2rLPSテーブル122、符号ビット生成部160、コンテキスト更新部170に接続される。
【0066】
第1rLPSテーブル120、第2rLPSテーブル122は、それぞれ入力されたrangeとコンテキストに応じて、rLPSを決定するテーブルである。テーブルを2つ備えたことで、1サイクル中に2ビットの読み出しや書き込みを行うことが可能となり、高速な処理が見込まれる。また一方、いずれのテーブルに最新のデータが保持されているかを管理し、必要に応じてテーブルを切り替える制御が必要となる。このため、図9の算術符号化部116はテーブル管理手段を備えている。
【0067】
符号ビット生成部160は、再正規化の際に出力符号を出力する。さらにコンテキスト更新部170は、前段の処理結果に基づいてコンテキストを更新して出力する。演算部140は、入力された区間range及び/又はlow、これに対応するrLPSをrLPSテーブル20を参照して決定し、これらに基づいて区間を更新し、range’とlow’を出力する。
【0068】
この処理を、図13の動作図に基づいて説明する。図13は図8と同様、所定の区間に対してMPS処理、LPS処理、再正規化を行う処理を説明している。ここではrangeとlowが決定されている区間に対して、2値シンボルA及び対応するコンテキストXの場合に演算部140がMPS処理して符号化を行い、区間をrange’とlow’に更新する処理と、このrange’とlow’を2値シンボルB及び対応するコンテキストYの場合に演算部140がLSP処理で符号化を行って、区間をrange”とlow”に更新する処理、及び再正規化を行って区間をrange”’とlow”’に拡大する処理と、コンテキスト更新部170がコンテキストX、コンテキストYをそれぞれ更新する処理を、1サイクルで行う。すなわち、演算部140は第1rLPSテーブル120を参照してMPS時のrLPSを、第2rLPSテーブル122を参照してLPS時のrLPS’を、各々取得し、以下の計算を行う。
range”’=(rLPS’-0.5)×2
low”’=(low+range-rLPS-rLPS’-0.5)×2
【0069】
また同じサイクル内で符号ビット生成部160が出力符号”1”を出力し、コンテキスト更新部170はコンテキストX、コンテキストYをそれぞれ更新する。これによって、1サイクルでMPS処理、LPS処理、再正規化を完了させることができる。
【0070】
次に、図14に、他の構成に係る算術符号化部300の例を示す。この図に示す算術符号化部300は、1サイクル中で2シンボルを処理するために、1シンボル目処理用の第1算術符号化手段301と、2シンボル目処理用の第2算術符号化手段302と、符号ビット生成部360を備える。第1算術符号化手段301は、第1rLPSテーブル320と、第1コンテキスト更新テーブル330と、第1演算部340と、第1再正規化部350とを備える。また第2算術符号化手段302は同様に、第2rLPSテーブル322と、第2コンテキスト更新テーブル332と、第2演算部342と、第2再正規化部352とを備える。この算術符号化部300は、2値列としてシンボルA及びコンテキストXを入力すると、コンテキストX及びrangeに対応したrLPSを第1rLPSテーブル320を参照して求め、この値とシンボルAとで第1演算部340は算術符号化を行い、rangeとlowを更新する。さらに必要に応じて第1再正規化部350で再正規化を行い、range’とlow’を第2算術符号化手段302に送出すると共に、符号ビットを符号ビット生成部360に出力する。また第1コンテキスト更新テーブル330を更新し、コンテキストX’を出力する。
【0071】
一方、第2算術符号化手段302は、コンテキストY及びrange’に対応したrLPSを第2rLPSテーブル322を参照して求め、この値とrange’とlow’に基づいて第2演算部342で算術符号化を行い、range’とlow’を更新する。さらに必要に応じて第2再正規化部352で再正規化を行い、range”とlow”を出力すると共に、符号ビット生成部360に符号ビットを出力する。符号ビット生成部360は、出力符号ビットを出力する。またシンボルB及びコンテキストYに基づいて第2コンテキスト更新テーブル332を更新し、コンテキストY’を出力する。
【0072】
以上の処理は、1サイクル中で終えることができる。すなわち、rangeとlow、コンテキストXに基づいて第1算術符号化手段301で1シンボル目のシンボルAを算術符号化すると共に、得られたrange’とlow’、及びコンテキストYに基づいて第2算術符号化手段302が2シンボル目のシンボルBを算術符号化する。このように本実施の形態では、2値列とシンタックス要素と周囲の状況(コンテキスト)に基づいて、生成された2値列に使用するコンテキストを決定するrLPSテーブルを予め作成しておくと共に、rLPSテーブルを2つ用意することで、1サイクル中に演算部は各々のテーブルから必要なデータを読み出し、更新することができ、2サイクル分の演算を1サイクルで完了することができる。この結果、高い符号化効率を達成する一方で処理時間の長さが問題となっていたCABACの処理サイクル数を削減することが可能となり、もって処理の高速化を図り、高解像度アプリケーションのリアルタイム符号化等に実装可能なシステムを構築できる。この手法は、汎用のCPUやMPUでソフトウェア的に実装することも可能であるが、好ましくは専用のハードウェアを構築して実行させることで、より効率のよい処理が可能となる。
(2サイクル予測を行う算術符号化部の変形例)
【0073】
図9のブロック図に示す算術符号化装置の構成では、算術符号化部116で算術符号化演算を行う。算術符号化部116の具体的な構成としては、例えば図5のブロック図に示した構成が利用できる。ここで、コンテキスト更新テーブルを各々ROMで構成すると、各々がシンボルに応じてコンテキストを決定するため、ROMのサイズを大きくする必要がある。また、ROMではデータのアクセスに1サイクルを要するため、遅延が生じる。そこで、一方のコンテキスト更新テーブルを組み合わせ回路で構成することでROMのサイズを小さくでき、安価に構成できる。さらに組み合わせ回路では、演算論理の結果はそのサイクル中に生成されるので、余分なサイクルを要さず、処理を高速化できる利点が得られる。組み合わせ回路を用いた算術符号化部216の例を、図29に示す。
【0074】
この図に示す算術符号化部216は、コンテキストメモリ部217と、図29においてコンテキストメモリ部217の第1の出力側に接続された第1コンテキスト更新テーブル230と、第2の出力側に接続された第2コンテキスト更新テーブル232と、コンテキストメモリ部217の第1の出力側に接続された第1rLPSテーブル220と、第1コンテキスト更新テーブル230とコンテキストメモリ部217の加算器出力と接続された第2rLPSテーブル222と、rangeの値を保持するためのrangeメモリ部218と、rangeメモリ部218及び第1rLPSテーブル220の出力側に接続された第1選択器224と、第1選択器224及びrangeメモリ部218に接続された第1range更新部240と、第2rLPSテーブル222及び第1range更新部240の出力側に接続された第2選択器226と、第2選択器226及び第1range更新部240の出力側に接続され、且つ出力側をrangeメモリ部218に接続した第2range更新部242と、lowの値を保持するlowメモリ部219と、lowメモリ部219、第1range更新部240及び第1選択器224の出力側に接続された第1low更新部250と、第1low更新部250、第2range更新部242及び第2選択器226の出力側に接続され、且つ出力側をlowメモリ部219に接続した第2low更新部252とを備える。
【0075】
なお図29は、処理工程とデータの流れをブロック図的に表現した図であるため、実際のハードウェア的な結線とは必ずしも一致しない。例えばrange値については、rangeメモリ部218→第1rangeテーブル→第2rangeテーブル→rangeメモリ部218にループして、rangeが順次更新される様子を示しているが、実際には第1rangeテーブル及び第2rangeテーブルがそれぞれrangeメモリ部218に接続され、各々のrangeテーブルで更新したrange値をrangeメモリ部218に書き込むことができる。またコンテキストメモリ部217が重複して表示されているが、両者は同じものであり、図29において左側のコンテキストメモリ部217はリード時、中央のコンテキストメモリ部217はライト時の動作をそれぞれ示している。
【0076】
コンテキストメモリ部217は、図9においてコンテキストを保持する第1メモリ部117に相当する。ここでは、シンボルAとこれに対応するコンテキストX、シンボルBとこれに対するコンテキストYの4つの入力、及び更新されたコンテキストX’、Y’2つの出力を備えるデュアルポートRAM等で構成される。このコンテキストメモリ部217は、更新されたコンテキストを保持すると共に、指定されたアドレスに従い該当するコンテキストの読み込みを行い、さらに第1、第2コンテキスト更新テーブル232によって更新された2つのコンテキストX’、Y’の書き込みを各々行う。ここで第2コンテキスト更新テーブル232は、ROMで構成されるが、一方第1コンテキスト更新テーブル230は組み合わせ回路で構成される。一方のコンテキスト更新テーブルを組み合わせ回路で構成することで、第2段階でコンテキストX、Yを同時に更新できるので、1サイクルで2シンボルの処理を行う高速化に大きく資する。
【0077】
なお、図29に示す算術符号化部216の例において、第1コンテキスト更新テーブル230及び第2コンテキスト更新テーブル232の両方を組み合わせ回路で構成することもできる。この場合は、一層の高速化を図ることができる。なお、コンテキスト更新テーブルに大量のデータを記憶する場合は、組み合わせ回路で実現すると大面積化と高コスト化となるため不適となる。ただ、保存すべきデータ量が少ない場合は、組み合わせ回路で実装しても面積がROMの場合に比べさほど大きくならないため、両方を組み合わせ回路で構成することが好ましい。
【0078】
第1及び第2rLPSテーブル222は、各々ROMで構成され、入力されたコンテキストに従い、rLPSを出力する。ROMに保持されたrLPSテーブルのデータは、コンテキストに応じて4つに区分されているため、各rLPSテーブルが4つの出力を備える。各々のrLPSテーブルから出力されたrLPSは、第1及び第2選択器226にそれぞれ入力される。第1、第2選択器226は、各々入力されるrangeに従い、該当するrLPSを選択して、第1、第2range更新部242に出力する。第1、第2range更新部242は、rangeの値を更新してrangeメモリ部218のrange値を書き換える。同様にlowメモリ部219は、low値を保持する。これらrangeメモリ部218やlowメモリ部219は、レジスタで構成できる。また第1、第2low更新部252は、再正規化部の機能を実現しており、range及び再正規化の回数に従い再正規化してlowを更新する。このようにして第1low更新部250はシンボルAの算術符号化された符号ビット1を出力し、第2low更新部252はシンボルBの算術符号化された符号ビット2を出力する。
【0079】
なお図29の例では、各処理を行う部材を機能的に表現したものであって、実際のハードウェア構成においては、一の部材で複数の機能を実現することができる。例えば、コンテキストメモリ部217は図9において第1メモリ部117に、rangeメモリ部218及びlowメモリ部219は、第2メモリ部118に相当する。また、第1range更新部240及び第1low更新部250は、図14に示す第1演算部に、第2range更新部242及び第2low更新部252は、第2演算部に、各々相当し、さらにこれらを適宜纏めることもできる。
(DSEの算術符号化処理工程)
【0080】
以上の算術符号化部216で1サイクル中に2シンボルの算術符号化演算を行う処理は、図29及び図30のフローチャートに示すように、4段階に分けることができる。すなわち、ステップS1で示す第1段階では、各コンテキストの読み込みが行われる。具体的には、コンテキストメモリ部217で、アドレスに従いシンボルA、Bと対応するコンテキストX、Yの読み出しを行う。図29において、左側のコンテキストメモリ部217はリード状態を示している。
【0081】
次にステップS2で示す第2段階で、各コンテキストの更新と各rLPSの読み込みが行われる。具体的には、コンテキストメモリ部217の第1の出力から第1コンテキスト更新テーブル230がコンテキストXを読み込み、コンテキストX’に更新する。また、更新されたコンテキストX’を第2コンテキスト更新テーブル232が参照し、他方でコンテキストメモリ部217の第2の出力から得られたコンテキストYをコンテキストY’に更新する。ここで、コンテキスト更新テーブルを2つのROMとせず、一方を組み合わせ回路で構成した第1コンテキスト更新テーブル230とし、他方をROMで構成された第2コンテキスト更新テーブル232とすることで、処理の高速化と小面積化を両立させ、2つのシンボルA、BのコンテキストX、Yを同時に更新することが可能となる。また上述の通り、すべてのコンテキスト更新テーブルを組み合わせ回路で構成することで、一層の高速化が図られる。
【0082】
また一方で、第2段階において更新前のコンテキストXに基づき、シンボルAのrLPSをrLPSテーブルを参照して求める。すなわち、コンテキストメモリ部217の第1の出力から得られるコンテキストXに基づき、第1rLPSテーブル220がrLPSを第1選択器224に出力する。他方、第1コンテキスト更新テーブル230で得られるコンテキストX’及びコンテキストメモリ部217の第2の出力から得られるコンテキストYのAND出力が第2rLPSテーブル222に送られ、同様に更新前のコンテキストYのrLPSが求められ、第2選択器226に出力される。
【0083】
さらにステップS3で示す第3段階で、更新されたコンテキストの書き込みとrangeの更新が行われる。まず、第1コンテキスト更新テーブル230及び第2コンテキスト更新テーブル232から各々出力されるコンテキストX’、Y’がコンテキストメモリ部217に書き込まれる。図29において、中央下段のコンテキストメモリ部217はライト状態を示している。
【0084】
一方で、第1選択器224は、rangeメモリ部218を参照して得られるrangeに従い、シンボルAの該当するrLPSを選択して、第1range更新部240に出力する。第1range更新部240は、rangeメモリ部218に保持される現在のrangeを、選択されたrLPSに応じてrange’に更新すると共に、次段のシンボルBに相当するrangeを決定するために第2range更新部242に出力する。また一方で、更新されたrange’に応じて、再正規化の回数を決定し、第1low更新部250に出力する。
【0085】
第2range更新部242は、第1range更新部240で更新されたrange’を、第2選択器226で選択されたrLPSに従い、range”に更新し、rangeメモリ部218のrange値をrange”に更新する。一方、更新されたrange”に応じて再正規化の回数を決定し、第2low更新部252に出力する。
【0086】
最後にステップS4で示す第4段階で、lowの更新が行われる。第1low更新部250は、range’及び再正規化の回数に応じて、lowメモリ部219に保持されたlow値をlow’に更新すると共に、シンボルAの符号ビット1を出力する。一方第2low更新部252は、range”及び再正規化の回数に応じてlow’をlow”に更新し、lowメモリ部219のlow値をlow”に更新する。また、シンボルBの符号ビット2を出力する。
【0087】
以上のようにして、2つのコンテキスト更新テーブルの一方をROM、他方を組み合わせ回路で構成して、1サイクルで2シンボルの算術符号化を安価に実現できる。
(連続MPS処理予測)
【0088】
一方で、CABAC処理による2値化の特徴として、同じシンボルを連続して生成しやすい点が挙げられる。またCABAC処理に含まれるMPS処理とLPS処理の内、MPS処理の特徴として、lowは変化せずrangeの値のみ緩やかに減少するという傾向がある。そこで、2値列がMPSの連続である場合、この連続数とrange及びコンテキストから、数サイクル先までの結果を予測することが可能となる。
【0089】
この処理の手順を、図15の動作図に基づいて説明する。ここではコンテキストXが一定値で、MPS処理が連続して4回続くものとする。まず第1サイクルでrange0がrange1に更新されるとすると、このときのMPS処理で使用するrLPSがrLPS1であれば、
range1=range0-rLPS1
low0=low1
となる。また次の第2サイクルでrange1がrange2に更新されるとすると、このときのMPS処理で使用するrLPSがrLPS2であれば、
range2=range1-rLPS2
=range0-rLPS1-rLPS2
low2=low1=low0
となる。さらに第3サイクルでrange2がrange3に更新され、このときrLPS3であれば、
range3=range2-rLPS3
=range0-rLPS1-rLPS2-rLPS3
low3=low2=low1=low0
となり、最後に第4サイクルでrange3がrange4に更新され、このときrLPS4であれば、
range4=range3-rLPS4
=range0-rLPS1-rLPS2-rLPS3-rLPS4
low4=low3=low2=low1=low0
となる。このように同一コンテキストを用いたMPSの連続した処理は、range、コンテキストX、連続数から演算することができるので、予め演算した結果をテーブルに記録しておくことで、上記のパラメータから数サイクル先まで予測可能となる。これを実現するために、MPS連続数テーブルを用意する。
(MPS連続数テーブル)
【0090】
図16に、コンテキストが一定の場合のMPS連続数テーブルの例を示す。この図に示すように、MPS連続数テーブルは、range、コンテキスト、MPS連続数に応じたrangeを表として保持している。このため、これらのパラメータでテーブルを参照すれば、連続したMPS処理後のrangeの値を取り出すことができる。図15の例では、初期値であるrangeをrangeAmコンテキストX(一定)、MPS連続数4であるから、range予測値は、図16のMPS連続数テーブルにおいてEの位置に格納された値となる。このように、テーブルの参照のみによって数サイクル先の更新区間を求めることができるので、特にMPS処理が連続する場合には極めて大幅な演算量の低減が見込まれ、処理数低減による高速化が図られる。
(再正規化による変化)
【0091】
以上のMPS処理では、LPS処理が生じない間、すなわちMPS処理が連続する間はlowは一定である。しかしながら、図17(a)に示すように再正規化を行うとlowの値が変化する。ただ、再正規化の値はrangeによって決まる。このため、rangeの値と再正規化を行う回数が判れば、lowの値を求めることができる。このように、再正規化によって変化するlowについてもテーブル化することが可能となる。
【0092】
再正規化を考慮した連続MPS処理予測部400のブロック図を図18に示す。この図に示す連続MPS処理予測部400は、rangeテーブル420と、コンテキスト更新テーブル430と、再正規化部450を備える。この連続MPS処理予測部400は、rangeとMPS連続数、コンテキストに応じてrangeテーブル420を参照し、rengeをrange’に更新する。一方で再正規化回数とlowに基づいて、再正規化部450がlow’と符号ビットを出力する。さらに、MPS連続数とコンテキストに基づいて、コンテキスト更新テーブル430を参照し、コンテキストを更新する(context→context’)。
【0093】
再正規化を考慮したrange予測の例を、図17(b)に示す。この図に示すように、MPS連続数と再正規化の回数に応じて、rangeの値を予測でき、さらにコンテキストを更新できる。
(コンテキストの変化)
【0094】
また上記の例ではコンテキストが一定としたが、コンテキストが途中で切り替わる場合もあり得る。上記の手法では同一シンボルに対して同一コンテキストを使用することを前提としていたため、コンテキストが変更されるとそれ以降の変化を予測できないこととなる。そこで、rangeテーブルとコンテキスト更新テーブルとを各々2つ用意することで、このようなコンテキストの変化にも対応可能な連続MPS処理予測を実現する。
【0095】
図19は、連続するMPS処理において、コンテキストが4サイクルまではコンテキストX、続く2サイクルはコンテキストYに切り替わる例を示している。この場合も、コンテキスト毎にテーブル化することが可能である。図20に、range、コンテキスト(可変)、MPS連続数に応じたrange予測値を記録したMPS連続数テーブルの例を示す。図19の例では、初期値であるrangeをrangeA、コンテキストXでのMPS連続数が4、その時点でのrangeがrangeEで、その後のコンテキストYでのMPS連続数が2であるため、range予測値は、図20のMPS連続数テーブルにおいてEの位置に格納された値と、Iの位置に格納された値の和E+Iとなる。このように、コンテキストが変化する場合であっても、同様にテーブルの参照によって容易に更新区間を求めることができるので、大幅な処理の低減と高速化が図られる。
【0096】
コンテキストが変化する場合に連続MPS処理予測を実現する連続MPS処理予測部400Bを構成するブロック図の例を図21に示す。この図に示す連続MPS処理予測部400Bは、2つの予測テーブル420A、420B(MPS連続数テーブル)を設けることで、rangeとコンテキスト、MPS連続数が入力されると、これらのパラメータに応じたrange予測値が参照され、対応する値としてrange”が出力される。また予測テーブル420A、420B内のコンテキストは適宜更新される。この例ではコンテキストをX、Yの2種類とした例を説明したが、さらに多くのコンテキストに対応させた複数のテーブルを用意することも可能であることは言うまでもない。
【0097】
図22に、より詳細な連続MPS処理予測部500のブロック図を示す。この図に示すように、連続MPS処理予測部500は第1コンテキスト更新テーブル530と、第2コンテキスト更新テーブル532と、第1rangeテーブル520と、第2rangeテーブル522と、再正規化テーブルを有する一の再正規化部550を備える。この連続MPS処理予測部500は、rangeとMPS連続数X(図19の例では4)、コンテキストA(図19ではコンテキストX)に基づいて、第2rangeテーブル522を参照し、range’(rangeE)を求める。一方、コンテキストB(図19ではコンテキストY)、MPS連続数Y(図19では2)、第2rangeテーブル522で得られたrange’に基づいて、第1rangeテーブル520を参照し、range”を求める。一方で、第1rangeテーブル520及び第2rangeテーブル522の再正規化回数と、lowの値に基づいて、再正規化部550が再正規化テーブルを参照してlow’と、再正規化による符号ビットを出力する。このように、一の再正規化部550でコンテキストの異なる再正規化を加算して、適切な符号ビットを出力することができ、回路の簡素化に寄与する。さらにまた、コンテキストAを、MPS連続数に基づき第2コンテキスト更新テーブル532を参照してコンテキストA’に更新し、コンテキストBをMPS連続数に基づいて第1コンテキスト更新テーブル530を参照し、コンテキストB’に更新する。また上述の通り、コンテキスト変更数を増やすことも可能である。
(連続MPS処理予測を行う算術符号化部の変形例)
【0098】
また上記図29で説明したのと同様に、連続MPS処理予測においても、コンテキスト更新テーブルを各々ROMで構成する他、より安価で安定した高速化を得るために、一方を組み合わせ回路で構成したり、両方を組み合わせ回路で構成することもできる。このような算術符号化部316の例を、図31に示す。図31も処理工程をブロック的に表現した図であるため、コンテキストメモリ部217Bが重複して表示されているが、両者は同じものである。
【0099】
この図に示す算術符号化部316も、第1及び第2コンテキスト更新テーブル230B、232Bの出力側に接続されたコンテキストメモリ部217Bと、コンテキストメモリ部217Bの第1の出力側に接続された第1コンテキスト更新テーブル230Bと、第2の出力側に接続された第2コンテキスト更新テーブル232Bとを備え、これらの構成は図29とほぼ同様である。すなわち、第1コンテキスト更新テーブル230Bは組み合わせ回路で構成され、第2コンテキスト更新テーブル232BはROMで構成される。あるいは、第1コンテキスト更新テーブル230B及び第2コンテキスト更新テーブル232Bのいずれも、組み合わせ回路で構成してもよい。特に保存すべきデータ量が少ない場合は、実装面積も大きくならないので、より高速化が図られる組み合わせ回路のみでの構成が好ましい。
【0100】
また算術符号化部316は、rangeの値を保持するrangeメモリ部218Bと、lowの値を保持するlowメモリ部219Bも備え、これらもレジスタ等で構成できる。これらの部材は、図29とほぼ同様に構成できるので、詳細説明は省略する。
【0101】
一方で算術符号化部316は、シンボルA(MPS)の連続数m及び対応するコンテキストXを入力し、rangeメモリ部218Bから読み出したrangeをrange’に更新する第1rangeテーブル520Bと、シンボルB(MPS)の連続数n及び対応するコンテキストYを入力し、第1rangeテーブル520Bのrange’を更新してrange”を出力する第2rangeテーブル522Bを備える。これらrangeテーブルは、MPS連続数に基づき、rangeを予測する。さらに算術符号化部316は、図29と同様に第1rangeテーブル520Bで更新されたrange’と再正規化の回数に基づいて再正規化を行い、lowメモリ部219Bのlowを更新してlow’と符号ビット1を出力する第1low更新部250Bと、第2rangeテーブル522Bのrange”及び再正規化の回数に基づいて再正規化を行い、第1low更新部250Bで得られたlow’を更新したlow”と符号ビット2を出力する第2low更新部252Bを備える。
【0102】
図31も、図29と同様に処理工程とデータの流れをブロック図的に表現した図であるため、実際のハードウェア的な結線とは必ずしも一致しない。例えばコンテキストメモリ部217Bが重複して表示されているが、両者は同じものであり、図31において左側のコンテキストメモリ部217Bはリード時、中央のコンテキストメモリ部217Bはライト時の動作をそれぞれ示している。
(MPSEの算術符号化処理工程)
【0103】
この算術符号化部316も、図31及び図32のフローチャートに示すようにステップS’1~S’4の4段階で、シンボルA、Bの算術符号化処理を行える。すなわち、ステップS’1で示す第1段階では、各コンテキストの読み込みが行われる。具体的には、コンテキストメモリ部217Bで、シンボルA、Bと対応するコンテキストX、Yの読み出し(リード)を行う。
【0104】
次にステップS’2で示す第2段階で、各コンテキストの更新が行われる。具体的には、コンテキストメモリ部217Bの第1の出力から第1コンテキスト更新テーブル230BがコンテキストXを読み込み、さらにシンボルAのMPS連続数mに基づいてコンテキストX’に更新する。また、更新されたコンテキストX’を第2コンテキスト更新テーブル232Bが参照し、他方でコンテキストメモリ部217Bの第2の出力から得られたコンテキストY、及びそのMPS連続数nに基づき、コンテキストY’に更新する。
【0105】
さらにステップS’3で示す第3段階で、更新されたコンテキストの書き込みとrangeの更新が行われる。すなわち、第1コンテキスト更新テーブル230B及び第2コンテキスト更新テーブル232Bから各々出力されるコンテキストX’、Y’がコンテキストメモリ部217Bに書き込まれる。このようにして第1、第2コンテキスト更新テーブル232Bで、MPSを処理した分のコンテキスト(発生確率)の更新をステップS’2で行い、ステップS’3でコンテキストメモリ部217Bに書き込む。
【0106】
一方でシンボルAにつき、MPS連続数mとそのコンテキストXに基づき、第1rangeテーブル520Bがrangeの値をrange’に更新する。rangeの値は、rangeメモリ部218Bから読み込まれる。さらにシンボルBにつき、MPS連続数nとそのコンテキストYに基づき、第2rangeテーブル522Bがrange’の値をrange”に更新する。更新されたrange”の値は、rangeメモリ部218Bに書き込まれる。
【0107】
最後にステップS’4で示す第4段階で、lowの更新が行われる。第1low更新部250Bは、range’及び再正規化の回数に応じて、lowメモリ部219Bに保持されたlow値をlow’に更新すると共に、シンボルAの符号ビット1を出力する。一方第2low更新部252Bは、range”及び再正規化の回数に応じてlow’をlow”に更新し、lowメモリ部219Bのlow値をlow”に更新する。また、シンボルBの符号ビット2を出力する。この方法はシンボルがMPSのときのみ有効であるが、図29と同様に簡単な演算回路で1サイクルで2シンボルの処理が可能な算術符号化部316が実現できる。
【0108】
このようにして、前段のシンボルの演算を待たずに次段のシンボルの算術符号化を行うことができるので、パイプライン処理が可能となり、従来は不可能と考えられていた処理の高速化が図られる。図33に、このようなパイプライン処理の例を示す。図33に示すように、3つのシンボルについて、算術符号化処理を並列して行うことができるので、1サイクルで2シンボル以上の処理が可能となる。
(2つの手法の切り替え)
【0109】
以上のように、2サイクル予測は1サイクル分の処理を削減し、多くの場面で予測可能である利点を有する。一方連続MPS処理予測は、数サイクル分の処理を削減でき、削減量が大きいが、MPSが連続する場合のみ予測可能であるという制約がある。
【0110】
よって、これら2サイクル予測と連続MPS処理予測とを組み合わせ、状況に応じてより有効な手法を選択し、これらを切り替えて利用することで、一層の高速化を図ることができる。本発明の実施の形態3として、このような予測手法切替部を備える算術符号化装置の一例を、図23及び図24に示す。これらの図に示す算術符号化装置600も、図9と同様にコンテキスト計算部614、第1メモリ部617、第2メモリ部618、算術符号化部610を備える。これらの部材は基本的に図9等と同様であって、詳細説明を省略する。算術符号化部610は、入力された2信号をバッファリングする入力バッファ621と、2サイクル予測部622と、連続MPS処理予測部623と、これらを切り替える予測手法切替部624とを備える。予測手法切替部624は、入力されるコンテキストやrange等に応じて、その時点で適切な予測手法を選択して切り替える。図23の例では2サイクル予測部622を選択した状態を、図24の例では連続MPS処理予測部623を選択した状態を、それぞれ示している。これにより、2サイクル予測と、連続MPS処理予測を適宜組み合わせて、多くのサイクル数を削減できる。
【0111】
図25に、2サイクル予測と連続MPS処理予測を予測手法切替部624で切り替える様子を示す。この図に示すように、2値化されたビット列の状態に基づいて、予測手法切替部624がこれらの切り替えを行う。ここでは、切り替えの条件として、入力ビットが”0”の連続である場合のみ連続MPS処理予測を使用し、その他の場合は2サイクル予測を使用する。予測手法切替部624はこの条件に従い、いずれかの手法を選択し、選択した手法に従って処理を行う。
(実施例)
【0112】
次に本発明の実施例として、2サイクル予測、連続MPS処理予測、及びこれらを切り替える場合のそれぞれについて算術符号化を行い、削減されるサイクル数の比率をシミュレーションで求めた。ここでは、一括で入力するコンテキスト数を2として、種々のシミュレーション用画像シーケンス(akiyo、bridge-close、bridge-far、carphone、clair)に対して算術符号化を行い、そのシミュレーション結果を、それぞれ表1~表5に示す。表においてDSEは2サイクル予測、MPSEは連続MPS処理予測、DSE+MPSEはこれらを切り替えた例を、それぞれ示している。この表に示すように、いずれのシーケンスに対しても2サイクル予測、連続MPS処理予測によって演算量を削減でき、特に2サイクル予測が良好な結果を示している。またこれらを切り替える方式では、一層の演算量削減が図られ、本実施の形態の有用性が確認できた。またシミュレーション結果によれば、コンテキストの変更許可数を増すほど、削減率は向上した。ただ、コンテキストの変更許可数を増加すると、削減できるサイクル数は増加するものの、回路構成が複雑化して回路面積が増大するというデメリットもあるので、サイクル数削減効果と回路構成に要するコスト、要求される仕様などに応じて適宜決定する。
【0113】
【表1】
JP0004547503B2_000002t.gif

【0114】
【表2】
JP0004547503B2_000003t.gif

【0115】
【表3】
JP0004547503B2_000004t.gif

【0116】
【表4】
JP0004547503B2_000005t.gif

【0117】
【表5】
JP0004547503B2_000006t.gif

【0118】
なお他の実施の形態に係る算術符号化装置は、多値信号を2値化するための2値化部と、2値化部で生成された2値シンボルを算術符号化するための算術符号化部と、コンテキスト番号を生成するためのコンテキスト計算部と、2値化部で生成された2値シンボルに基づいて、優勢シンボル或いは劣勢シンボルが示すシンボル値とシンボル出現確率とを更新するための更新部と、コンテキスト計算部で計算されたコンテキスト番号をインデックスとして、シンボル値とシンボル出現確率とを格納するための確率状態格納部とを備える算術符号化装置であって、算術符号化部は、劣勢シンボルの区間を発生確率に基づいて分割した領域rLPSの予測値を格納する第1格納部と、同じくrLPSの予測値を格納する、第1格納部とは別個の第2格納部と、第1格納部に格納されたrLPSの予測値及び初期の区間を参照して算術符号化を行い区間を更新する第1演算部と、同じく第2格納部に格納されたrLPSの予測値及び前記第1演算部で更新された更新区間を参照して算術符号化を行う、第1演算部とは別個の第2演算部と、シンボル出現確率及び優勢シンボルが示すシンボル値を更新する第1コンテキスト更新テーブルと、同じくシンボル出現確率及び優勢シンボルが示すシンボル値を更新する、第1コンテキスト更新テーブルとは別個の第2コンテキスト更新テーブルとを備え、第1コンテキスト更新テーブルは、入力されたコンテキストに対する出力を同サイクル中に前記第2コンテキストテーブルに入力可能な組み合わせ回路で構成されている。これにより、1サイクル中に2ビット以上の処理が可能な高速な算術符号化を実現できる。
【0119】
算術符号化装置においては、第1コンテキスト更新テーブル及び第2コンテキスト更新テーブルを組み合わせ回路で構成できる。これによって処理の高速化が図られる。なお、第1コンテキスト更新テーブルをROMで、第2コンテキスト更新テーブルを組み合わせ回路で構成してもよく、これによって算術符号化を安価に実現できる。
【産業上の利用可能性】
【0120】
本発明の算術符号化装置、算術符号化方法、算術符号化プログラム及びプログラムを格納したコンピュータで読み取り可能な記録媒体は、動画像信号を圧縮して記録したり伝送する用途に有用であり、例えば携帯端末装置、動画像撮像装置、動画像記録・再生装置等、高画質動画像を処理する装置及びその応用分野において好適に利用できる。
【図面の簡単な説明】
【0121】
【図1】H.264/AVCの符号化処理処理により、画像データからビットストリームを得る動画像符号化/復号装置を示すブロック図である。
【図2】算術符号化・復号化の概念を説明するための概念図である。
【図3】2値算術符号化を行う手順を示す概念図である。
【図4】CABAC処理を行う算術符号化装置を示すブロック図である。
【図5】図4の2値算術符号化部の詳細を示すブロック図である。
【図6】再正規化の手順を示す概念図である。
【図7】算術符号化装置を示すブロック図である。
【図8】図7の算術符号化装置の動作を示す概念図である。
【図9】本実施の形態1に係る算術符号化装置を示すブロック図である。
【図10】図9の第1メモリ部を示す概念図である。
【図11】本実施の形態1に係る算術符号化装置の変形例を示すブロック図である。
【図12】図9に示す算術符号化装置の算術符号化部のブロック図である。
【図13】図12の算術符号化部の動作を示す概念図である。
【図14】他の構成に係る算術符号化部を示すブロック図である。
【図15】連続MPS処理予測の手順を示す概念図である。
【図16】コンテキストが一定の場合のMPS連続数テーブルを示す概念図である。
【図17】図17(a)再正規化を行う様子を示す概念図、図17(b)は再正規化を考慮したrange予測を示す概念図である。
【図18】再正規化を考慮した連続MPS処理予測部のブロック図である。
【図19】連続するMPS処理において、コンテキストが変化する様子を示す概念図である。
【図20】MPS連続数テーブルの例を示す概念図である。
【図21】コンテキストが変化する場合に連続MPS処理予測を実現する連続MPS処理予測部を構成するブロック図である。
【図22】詳細な連続MPS処理予測部のブロック図を示す。
【図23】本発明の実施の形態3に係る算術符号化装置を示すブロック図である。
【図24】本発明の実施の形態3に係る算術符号化装置を示すブロック図である。
【図25】2サイクル予測と連続MPS処理予測を予測手法切替部で切り替える様子を示すブロック図である。
【図26】H.264/AVCによる算術符号化・復号の処理プロセスのフローチャートである。
【図27】H.264/AVCの算術符号化の処理プロセスを具現化した算術符号化装置を示すブロック図である。
【図28】従来の算術符号化装置を示すブロック図である。
【図29】2サイクル予測を行う算術符号化部の変形例を示すブロック図である。
【図30】図29の算術符号化部による算術符号化の手順を示すフローチャートである。
【図31】連続MPS処理予測を行う算術符号化部の変形例を示すブロック図である。
【図32】図31の算術符号化部による算術符号化の手順を示すフローチャートである。
【図33】図29、図31の算術符号をパイプライン処理で行う様子を示すタイミングチャートである。
【符号の説明】
【0122】
1…DMA
2…動き探索部
3…デブロッキングフィルタ
4…動き補償部
5…変換部
6…量子化部
7…逆量子化部
8…逆変換部
9…全体制御部
10…算術符号化/復号装置
10A…算術符号化装置
11…可変長復号化部
12、112…2値化部
14、114、614…コンテキスト計算部
16、116…2値算術符号化部
20…rLPSテーブル
30…コンテキスト変更テーブル
40、140…演算部
50…再正規化部
70、170…コンテキスト更新部
100…動画像符号化/復号装置
117…第1メモリ部
117A…メモリ部
118…第2メモリ部
119…予測部
120…第1rLPSテーブル
121…出力バッファ
122…第2rLPSテーブル
160、360…符号ビット生成部
200、300…算術符号化装置
216、316…算術符号化部
217、217B…コンテキストメモリ部
218、218B…rangeメモリ部
219、219B…lowメモリ部
220…第1rLPSテーブル
222…第2rLPSテーブル
224…第1選択器
226…第2選択器
230、230B…第1コンテキスト更新テーブル
232、232B…第2コンテキスト更新テーブル
240…第1range更新部
242…第2range更新部
250、250B…第1low更新部
252、252B…第2low更新部
301…第1算術符号化手段
302…第2算術符号化手段
320…第1rLPSテーブル
322…第2rLPSテーブル
330…第1コンテキスト更新テーブル
332…第2コンテキスト更新テーブル
340…第1演算部
342…第2演算部
350…第1再正規化部
352…第2再正規化部
400、400B、500…連続MPS処理予測部
420…rangeテーブル
420A、420B…予測テーブル
430…コンテキスト更新テーブル
450…再正規化部
520、520B…第1rangeテーブル
522、522B…第2rangeテーブル
530…第1コンテキスト更新テーブル
532…第2コンテキスト更新テーブル
550…再正規化部
600…算術符号化装置
610…算術符号化部
617…第1メモリ部
618…第2メモリ部
621…入力バッファ
622…2サイクル予測部
623…連続MPS処理予測部
624…予測手法切替部
700…算術符号化装置
710…適応算術符号化・復号部
711…算術符号化・復号部
712…シンボル出現確率制御部
713…確率状態格納部
720…コンテキスト計算部
730…符号化・復号制御部
800…算術符号化装置
810…適応算術符号化部
811…算術符号化部
814…シンボル出現確率制御部
815…確率状態格納部
820…コンテキスト計算部
821…レジスタ
822…比較判定部
830…符号化制御部
FM…フレームメモリ
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22
【図24】
23
【図25】
24
【図26】
25
【図27】
26
【図28】
27
【図29】
28
【図30】
29
【図31】
30
【図32】
31
【図33】
32