図面 (/)

技術 算術符号の復号化方法および算術符号の復号化装置ならびに算術符号の復号化処理プログラム

出願人 セイコーエプソン株式会社
発明者 稲積満広
出願日 2002年1月15日 (18年10ヶ月経過) 出願番号 2002-006223
公開日 2003年7月25日 (17年3ヶ月経過) 公開番号 2003-209473
状態 未査定
技術分野 TV信号の圧縮,符号化方式 FAX帯域、冗長度の圧縮 TV信号の圧縮,符号化方式 FAXの帯域、冗長度の圧縮 圧縮、伸長・符号変換及びデコーダ
主要キーワード 実行長 適応化処理 ビット面 復号化処理プログラム 浮動小数 最大投 ワーストケース 投機実行
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2003年7月25日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

解決手段

ある復号化開始点から所定の長さだけ優勢シンボル(MPS)の連鎖があると仮定し、そのMPSの連鎖に対応する部分を投機的実行長Lとし、その投機的実行長Lの先頭位置に対応するMPSの符号語C1と、初期の符号語(領域121の符号語C)から前記投機的実行長Lの先頭に位置する当該MPSの符号語の領域を与える積算確率値を引いた値(C−積算確率値)との大きさを判断し、 C1<(C−積算確率値)を満たす場合は、投機的実行長に対応するMPSを一括して復号化し、 C1<(C−積算確率値)を満たさない場合は、1ステップごとの復号処理を行う。

概要

背景

概要

算術符号復号化処理高速に行う。

ある復号化開始点から所定の長さだけ優勢シンボル(MPS)の連鎖があると仮定し、そのMPSの連鎖に対応する部分を投機的実行長Lとし、その投機的実行長Lの先頭位置に対応するMPSの符号語C1と、初期の符号語(領域121の符号語C)から前記投機的実行長Lの先頭に位置する当該MPSの符号語の領域を与える積算確率値を引いた値(C−積算確率値)との大きさを判断し、 C1<(C−積算確率値)を満たす場合は、投機的実行長に対応するMPSを一括して復号化し、 C1<(C−積算確率値)を満たさない場合は、1ステップごとの復号処理を行う。

目的

本発明は、情報源モデル化を用いるものではなく、一般の復号化対象においても効果を有することが特徴であり、また、可能性のある連鎖の全てを実行すると言うような事を行わないために、回路的、消費電力的に非常に有利なものとし、また、確率的に複数のデータを同時に処理するために、1つ1つのデータの復号化を高速化する方法に比較して、より大きな効果を得ることができるようにすることを目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

算術符号復号化する算術符号の復号化方法において、ある復号化開始位置から後に続く所定長優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖の仮定部分を投機的実行長とし、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語の領域を与える劣勢シンボルの積算生起確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定し、優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化する投機的復号処理を行うことを特徴とする算術符号の復号化方法。

請求項2

前記投機的実行長に対応する優勢シンボルの連鎖の有無を判定した結果、その優勢シンボルの連鎖が無いと判定された場合は、入力データに対して1ステップごとの復号化処理を行うことを特徴とする請求項1記載の算術符号の復号化方法。

請求項3

前記投機的復号処理に先立って、初期の符号語(Cとする)から前記投機的実行長の先頭位置に対応する優勢シンボル部分の符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)と符号語の領域に対して予め設定された下限値とを比較する処理を行い、(C−積算生起確率値)が下限値より大きい場合に、前記投機的復号化処理を行うことを特徴とする請求項1または2記載の算術符号の復号化方法。

請求項4

前記投機的実行長に対応する優勢シンボルの連鎖の有無の判定は、投機的実行長の先頭に位置する当該優勢シンボル部分の符号語(C1とする)と、初期の符号語(Cとする)から前記投機的実行長の先頭に位置する当該優勢シンボルの符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)とについて、 C1<(C−積算生起確率値)を判定し、 C1<(C−積算生起確率値)を満たす場合は、前記優勢シンボルの連鎖が有りと判定し、 C1<(C−積算生起確率値)を満たさない場合は、前記優勢シンボルの連鎖が無しと判定することを特徴とする請求項1から3のいずれかに記載の算術符号の復号化方法。

請求項5

前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定することを特徴とする請求項1から4のいずれかに記載の算術符号の復号化方法。

請求項6

算術符号を復号化する算術符号の復号化装置において、入力データに対して1ステップごとの復号化処理を行うステップ復号化手段と、少なくとも1つの投機的実行長およびそれと対をなす積算確率値でなる投機的実行パラメータを記憶する投機的実行パラメータ記憶手段と、この投機的実行パラメータ記憶部を参照して投機的実行を行う投機的実行制御手段およびその投機的実行結果を判定する投機的実行判定手段とを有する投機的復号化手段と、前記投機的実行パラメータ記憶手段を参照し、前記投機的復号化手段と前記ステップ復号化手段のいずれかを選択する実行機能選択手段と、を構成要素として含み、前記投機的復号化手段が行う投機的復号化処理は、ある復号化開始位置から後に続く所定長の優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖の仮定部分を投機的実行長とし、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語の領域を与える劣勢シンボルの積算生起確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定し、優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化する処理であることを特徴とする算術符号の復号化装置。

請求項7

前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖が無いと判定された場合は、入力データに対して1ステップごとの復号化処理を行うことを特徴とする請求項6記載の算術符号の復号化装置。

請求項8

前記投機的復号化手段が行う投機的復号化処理に先立って、前記実行機能選択手段は、初期の符号語(Cとする)から前記投機的実行長の先頭位置に対応する優勢シンボル部分の符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)と符号語の領域に対して予め設定された下限値とを比較する処理を行い、(C−積算生起確率値)が下限値より大きい場合に、前記投機的復号化処理を行うための指示を前記投機的復号化手段に出すことを特徴とする請求項6または7記載の算術符号の復号化装置。

請求項9

前記投機的実行長に対応する優勢シンボルの連鎖の有無の判定は、投機的実行長の先頭に位置する当該優勢シンボル部分の符号語(C1とする)と、初期の符号語(Cとする)から前記投機的実行長の先頭に位置する当該優勢シンボルの符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)とについて、 C1<(C−積算生起確率値)を判定し、 C1<(C−積算生起確率値)を満たす場合は、前記優勢シンボルの連鎖が有りと判定し、 C1<(C−積算生起確率値)を満たさない場合は、前記優勢シンボルの連鎖が無しと判定することを特徴とする請求項6から8のいずれかに記載の算術符号の復号化装置。

請求項10

前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定することを特徴とする請求項6から9のいずれかに記載の算術符号の復号化装置。

請求項11

算術符号を復号化する算術符号の復号化処理プログラムであって、その処理プログラムは、ある復号化開始位置から後に続く所定長の優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖の仮定部分を投機的実行長とする手順と、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語の領域を与える劣勢シンボルの積算生起確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定する手順と、優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化する投機的復号処理を行う手順と、を含むことをことを特徴とする算術符号の復号化処理プログラム。

請求項12

前記投機的実行長に対応する優勢シンボルの連鎖の有無を判定した結果、その優勢シンボルの連鎖が無いと判定された場合は、入力データに対して1ステップごとの復号化処理を行うことを特徴とする請求項11記載の算術符号の復号化処理プログラム。

請求項13

前記投機的復号処理に先立って、初期の符号語(Cとする)から前記投機的実行長の先頭位置に対応する優勢シンボル部分の符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)と符号語の領域に対して予め設定された下限値とを比較する処理を行い、(C−積算生起確率値)が下限値より大きい場合に、前記投機的復号化処理を行うことを特徴とする請求項11または12記載の算術符号の復号化処理プログラム。

請求項14

前記投機的実行長に対応する優勢シンボルの連鎖の有無の判定は、投機的実行長の先頭に位置する当該優勢シンボル部分の符号語(C1とする)と、初期の符号語(Cとする)から前記投機的実行長の先頭に位置する当該優勢シンボルの符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)とについて、 C1<(C−積算生起確率値)を判定し、 C1<(C−積算生起確率値)を満たす場合は、前記優勢シンボルの連鎖が有りと判定し、 C1<(C−積算生起確率値)を満たさない場合は、前記優勢シンボルの連鎖が無しと判定することを特徴とする請求項11から13のいずれかに記載の算術符号の復号化処理プログラム。

請求項15

前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定することを特徴とする請求項11から14のいずれかに記載の算術符号の復号化処理プログラム。

技術分野

0001

本発明は、算術符号復号化する算術符号の復号化方法および算術符号の復号化装置ならびに算術符号の復号化処理プログラムに関する。

0002

算術符号の符号化は他の符号化、例えばハフマン符号化に比較して、符号化効率が高い符号化方式である。一方、ハフマン符号化などに比較して処理量が大きく、そのため、高速な符号化、復号化方法が求められている。

0003

算術符号の符号化には、その対象とするデータにより幾つかの種類があるが、ここでは2値データを対象とする算術符号の符号化を考える。この2値のデータの内、出現頻度の高い方のデータを優勢シンボル(More Probable Symbol :以下、MPSと略す)と呼び、出現頻度の低い方のデータを劣勢シンボル(Less Probable Symbol : 以下LPSと略す)と呼ぶ。たとえば、2値画像を例にとり、MPSとLPSを説明する。図11のような画像を考え、白画素ビット0、黒画素をビット1と仮定すると、図11(a)のように白地に黒というようなデータの場合、MPSは0、LPSは1となる。また、図11(b)のように、黒地に白というようなデータの場合は、MPSは1、LPSは0となる。さらに、図11(c)のように、データが途中で白地に黒から、黒地に白と変わるような場合、それぞれの領域において、MPSは0から1に、LPSは1から0に変化する。このように、MPSとLPSはデータ中において固定されたものではない。

0004

この例に述べたように、算術符号の画像への応用については、2値画像、たとえば、ファクシミリ画像の符号化などに用いることができる。また多値画像においても、それぞれのビット面、たとえば、8ビット精度のデータを構成するビット0からビット7のそれぞれの面を符号化するような場合にも用いられる。

0005

図12はそれを示したもので、図12(a)はある画像のビット6の面を、図12(b)はビット4の面を、図12(c)はビット2の面を示す。このように、2値の算術符号は、多値のデータを取り扱うこともできる。

0006

このような算術符号の符号化の原理について、図13および図14を用いて簡単に説明する。なお、以下、それぞれの説明で用いる図面において、MPSとLPSを表す場合、MPSは白色、LPSは薄い黒色表現する。

0007

図13は算術符号の原理であり、符号語の領域の再帰的な分割を説明するためのものである。符号語の領域として最初に0.0と1.0の区間を考え、また、LPSの生起確率をQeとする。したがって、必然的にMPSの生起確率は(1−Qe)である。

0008

図13における縦方向で示す領域(符号語の領域)を考え、その0.0から1.0の区間を、図13のように、LPSの生起確率QeとMPSの生起確率(1−Qe)の区間に2分する。

0009

図13において、薄い黒色で表された部分がLPSの生起確率Qeの区間であり、白色で表された部分がMPSの生起確率(1−Qe)の区間である。以降、そのぞれぞれの区間を、 LPSの生起確率QeとMPSの生起確率(1−Qe)の比率において、再帰的に分割して行く。図13の例では、入力データ列方向に4つステップで分割を行っている。

0010

算術符号の符号化は、この再帰的に分割された領域を識別できる値を、その符号出力とするものである。たとえば、図13における横方向(入力データ列方向)の帯状領域101は、図示の左から右方向に向かって、順に、LPS,LPS,MPS,LPSという連鎖に対応する領域である。また、同様に、帯状領域102は、MPS,LPS,MPS,MPSという連鎖に対応する領域であり、同様に、帯状領域103は、MPS,MPS,MPS,MPSの連鎖に対応する領域である。

0011

ここで、たとえば、帯状領域103を例にとれば、この帯状領域103は4つのMPSの連鎖でなっているので、この帯状領域103を指定するための値は、0のみで十分であり、 MPS,MPS,MPS,MPSという4つのMPSの連鎖は、1つの0に符合化される。

0012

図14は、算術符号の符号化処理のステップを説明するためのものであり、MPS,LPS,MPS,MPSの連鎖を符号化する手順を説明するものである。つまり、最初のデータがMPSであるので、最初の符号語の領域のうち、MPSに対応する部分が選択される。そして、次のデータはLPSであるので、最初に選択されたMPSに対応する符号語の領域を再帰的に分割して得られる領域のうち、LPSに対応する符号語の領域が選択される。以降、同様に、MPSの符号語の領域、MPSの符号語の領域が選択される。

0013

なお、この図14において、選択された部分をそれぞれ太線黒枠104で示す。そして、最終的に選択された符号語の領域を識別する値が、符号化出力となる。多くの場合、選択された符号語の領域の下限値が符号語とされる。さて、本発明において考慮する要素である正規化処理適応処理について説明するために、この図14で示した算術符号の符号化処理を数式とフローチャートにより再度説明する。ここで、符号語の領域をA、符号語をC、LPSの生起確率の値をQeとする。Aの初期値は1.0であり、Cの初期値は0である。そうすると、図14で説明した処理は以下のように数式で表現される。入力データがMPSである場合は、

0014

0015

となり、入力データがLPSである場合は、

0016

0017

となる。これをフローチャートとして示したものが図15である。また、この逆処理としての復号化処理を示したものが図16のフローチャートである。これら、図15および図16に示す処理は、最も原理的な処理を示すもので、無限精度の浮動小数演算を用いる場合である。

0018

図15のフローチャートを簡単に説明する。まず、符号語の領域AをA=1.0、符号語CをC=0と設定し(ステップS1)、符号化終了か否かを判断して(ステップS2)、符号化が終了していなければ、データを1つ読み込む(ステップS3)。

0019

そして、その読み込んだデータがMPSであるか否かを判定し(ステップS4)、MPSであれば、A=A−A*Qeの演算を行って(ステップS5)、ステップS2に戻る。一方、ステップS4において、読み込んだデータがLPSであれば、A=A*QeとC=C+A*(1ーQe)の演算を行って(ステップS6)、ステップS2に戻る。

0020

このような符号化終了まで行い、符号化終了であればその符号語Cを出力し(ステップS7)、符号化処理を終了する。

0021

また、復号化処理を説明する図16のフローチャートにおいては、まず、符号語の領域AをA=1.0、符号語CをC=1−Qe、復号化データDateをDate=0と設定し(ステップS11)、復号化対象となる符号化データInputを入力し(ステップs12)、復号化終了か否かを判断して(ステップS13)、復号化が終了していなければ、符号化データInputが復号化データDateよりも小さいか否か、つまり、 Input <Dateを判定する(ステップS14)。

0022

この判定結果が、 Input <Date であれば、復号化データDateの最下位へMPSを追加する(ステップS15)。そして、 A=A−A*Qeの演算を行うとともにC=C−A*Qeの演算を行って(ステップS16,S17)、符号化データDateを左へ1ビットシフトする(ステップS18)。

0023

一方、 ステップS14におけるInput<Dateの判定結果が、 Input<Date でなければ、復号化データDateの最下位へLPSを追加し(ステップS19)、A=A*Qeの演算を行うとともにC=C+A*(1−Qe)の演算を行って(ステップS20,S21)、符号化データDateを左へ1ビットシフトする(ステップS18)。

0024

このような処理を繰り返し行い、復号化処理が終了したら(ステップS13)、復号化データDateを出力し(ステップS22)、復号化処理を終了する。

0025

以上説明した処理方法は2つの問題点があり、その1つは、入力が長くなるにつれて符号領域が小さくなり、その精度を維持するために、非常に大きな演算精度が要求されることである。また、もう一つは、演算処理量が大きい乗算が含まれることである。

0026

これを解決するために、通常、正規化という処理が導入される。正規化処理は、符号語の領域がある設定された範囲よりも小さくなった場合、符号語の領域を倍々と拡大し、その大きさが常に設定範囲内にあるようにする処理である。通常、この設定範囲は0.75と1.5の間とされる。

0027

図17はこの正規化処理を説明するためのものである。入力データがMPS,MPS,MPSと連続した場合、符号語の領域は図17における太線の枠110内において、下限値0.75を下回り、2倍に拡大される。さらに、その後、入力データがLPSで連続した場合、太線の枠111内において下限値を下回り、4倍に拡大される。

0028

算術符号の符号化においては、このような正規化処理がその都度実行され、符号語の領域が、設定された範囲(通常は、0.75と1.5の間)に維持される。それにより、小さな演算精度により、算術符号の符号化または復号化処理を実行することができる。

0029

なお、現実のデータにおいて、正規化処理を実行すると、符号語の領域の平均値として、1.0よりもわずかに大きな値が保持されることが分かっている。このことを用いた近似を行うことにより、算術符号の符号化における乗算を削除することができる。つまり、

0030

0031

のような近似を行うことにより、入力がMPSの場合におけるの符号化の式、つまり(1)式は、

0032

0033

のように変形することができる。また、入力がLPSの場合におけるの符号化の式、つまり(2)式は、

0034

0035

のように変形することができる。この(4)式および(5)式からわかるように、加減算のみで算術符号の符号化を実行することができる。

0036

以上のように、加減算と有限桁の演算のみで算術符号の符号化または復号化処理を実行できるが、これは処理において、ビット位置が常に変動することを考慮しなければならないことを意味する。

0037

算術符号の符号化または復号化処理において用いられるもう一つの重要な技術要素は適応処理である。図11で説明したように、MPSとLPSは、その値そのものも、また、その生起確率もデータ中で変動する。この変動に生起確率Qeを適応させることにより、高効率な符号化を実現することが可能となる。

0038

図18はこれを簡単に説明するためのものである。たとえば、入力としてMPSが連続する場合は、Qeの値、つまりLPSの生起確率を小さくすることにより、符号化効率を高めることができる。逆に、データ中にLPSが増えてきた場合、Qeの値を大きくすることにより符号化効率を高めることができる。さらに言うと、図11(c)のように、途中でMPSとLPSの値が逆転するような場合も有り得る。

0039

この適応処理については、計算式よる方法もあるが、実際に多く用いられるのは表を用いる方法である。

0040

図19はその具体例であり、この表はJPEG2000の規格で用いられるもので、識別番号(ID)、LPSの生起確率の値(Qe)、MPS適応(NMPS)、LPS適応(NLPS)、Switchの5要素よりなる表を用いる方法である。

0041

適応処理は、上述した正規化処理が行われたときに行われ、正規化処理がMPS処理時に起こった場合(図17の例では太線の枠110で囲った部分の処理)は、MPS適応(NMPS)に指示された識別番号(ID)の要素へ適応が行われ、正規化処理がLPS処理時に起こった場合(図17の例では太線の枠111で囲った部分の処理)は、LPS適応(NLPS)に指示された識別番号(ID)の要素へ適応が行われる。さらに、 Switchの値が1であるときは、MPSとLPSの値が交換される。

0042

具体例として、識別番号(ID)が2の状態で、MPSが入力されたときに正規化処理がなされた場合、状態は識別番号(ID)における3へ適応することになる。

0043

これにより生起確率Qeの値は、0x1801から0x0ac1へ変化し、確かに生起確率Qeの値は小さくなる。また、識別番号(ID)が2の状態で、LPSが入力されたときに正規化処理がなされた場合、状態は識別番号9へ適応し、生起確率Qeの値は、0x1801から0x3801へ変化し、生起確率Qeの値は大きくなる。

0044

ここで、生起確率Qeの値は、2/3*0x10000倍、つまり、43691倍されているものとする。このスケールにおいて、前述した符号語の領域の設定範囲(1.5〜0.75)の1.5は0x10000であり、0.75は0x8000である。つまり、符号語の領域の設定範囲は、

0045

0046

で表すことができ、符号化領域の大きさが0x8000よりも小さくなった場合に正規化処理が行われることになる。

0047

図20は正規化処理と適応化処理を含む算術符号の符号化処理を簡単に説明するフローチャートであり、図15のフローチャートに正規化処理と適応化処理を付加したものである。図20において、まず、符号語の領域AをA=0x8000、符号語CをC=0と設定し(ステップS31)、符号化終了か否かを判断して(ステップS32)、符号化処理が終了していなければ、データを1つ読み込む(ステップS33)。

0048

そして、その読み込んだデータがMPSであるか否かを判定し(ステップS34)、MPSであれば、A=A−Qeの演算を行う(ステップS35)。一方、読み込んだデータがLPSであれば、A=QeとC=C+A−Qeの演算を行う(ステップS36)。

0049

次に、A<0x8000を判定し(ステップS37)、 A<0x8000でなければ、つまり、Aが0x8000よりも大きければ、ステップS32に戻り、 逆に、A<0x8000であれば、Aを左を1ビットシフトし、Cを左に1ビットシフトする(ステップS38)。そして、再び、 A<0x8000を判定し(ステップS39)、 A<0x8000であれば、ステップS38の処理、つまり、Aを左へ1ビットシフトし、Cを左へ1ビットシフトする処理を繰り返す。

0050

そして、 ステップS39において、A<0x8000でなければ、つまり、Aが0x8000よりも大きければ、適応化処理を行って(ステップS40)、ステップS32に処理が戻り、符号化処理が終了していなければ、ステップS33以降の処理を行い、符号化処理が終了していればその符号語Cを出力し(ステップS41)、符号化処理を終了する。

0051

図21は正規化処理と適応化処理を含む算術符号の復号化処理を簡単に説明するフローチャートであり、図16のフローチャートに正規化処理と適応化処理を付加したものである。

0052

この図21のフローチャートにおいては、まず、符号語の領域AをA=0x8000、符号語CをC=0x8000−Qe、復号化データDateをDate=0と設定し(ステップS51)、復号化対象となる符号化データInputの上位16ビットを入力し(ステップs52)、復号化終了か否かを判断し(ステップS53)、符号化処理が終了していなければ、符号化データInputが復号化データDateよりも小さいか否か、つまり、Input<Dateを判定する(ステップS54)。

0053

その判定結果がInput<Date であれば、復号化データDateの最下位へMPSを追加する(ステップS55)。そして、 A=A−A*Qeの演算を行うとともにC=C−A*Qeの演算を行って(ステップS56,S57)、復号化データDateを左へ1ビットシフトする(ステップS58)。

0054

一方、 ステップS54におけるInput<Dateの判定結果が、Input<Date でなければ、復号化データDateの最下位へLPSを追加し(ステップS59)、 A=A*Qeの演算を行うとともにC=C+A*(1−Qe)の演算を行って(ステップS60,S61)、復号化データDateを左へ1ビットシフトする(ステップS58)。

0055

次に、A<0x8000を判断し(ステップS62)、 A<0x8000でなければ、つまり、Aが0x8000より大きければ、ステップS53に戻り、A<0x8000であれば、Aを左へ1ビットシフトし、Cを左へ1ビットシフトして(ステップS63)、符号化データInputを左へ1ビットシフトして次の1ビットを入力する(ステップS64)。

0056

そして、再び、 A<0x8000を判断し(ステップS65) 、A<0x8000であれば、ステップS63,S64の処理、つまり、Aを左へ1ビットシフトし、Cを左へ1ビットシフトして、さらに、符号化データInputを左へ1ビットシフトして次の1ビットを入力する処理を繰り返す。

0057

そして、 A<0x8000でなければ、つまり、Aが0x8000より大きければ、適応化処理を行って(ステップS66)、ステップS53に処理が戻り、復号化処理が終了していなければ、ステップS54以降の処理を行い、復号化処理が終了していればその復号化データDateを出力し(ステップS67)、復号化処理を終了する。

0058

このような正規化処理と適応化処理は、算術符号化の高速化に際し考慮しなければならない重要な技術要素である。

発明が解決しようとする課題

0059

これら算術符号化の高速化のための手法としては、大別して2つの方法がある。その1つは、(1)式や(2)式からも明らかであるように、LPSに比較して処理量の少ないMPSの出現頻度を上げるようにする方法である。これは符号化効率の向上にもつながるものである。もう1つは、MPS、LPSそれぞれの処理量そのものを少なくする方法である。

0060

MPSの出現頻度を上げる方法としては、情報源モデル化、あるいは予測を用いる方法が用いられる。符号化対象が画像の場合、あるデータはその近傍のデータと相関が高く、そのデータの近傍からの予測値とそのデータが一致した場合をMPS、予測が間違った場合をLPSとするものである。つまり、予測値と実際のデータ値の間で排他的論理和をとる。そうすると、予測と実際のデータ値が一致した時にデータは0となり、異なった場合に1となる。情報源のモデル化が有効であれば、予測の一致の頻度は高く、実際のデータ値によらずに0が多くなり、0をMPSとする頻度を上げることができる。これを具体的に実行した例としては、特開平5−67978、特開平11−55531などがある。しかし、これらの方法は先に述べたように、符号化対象のモデル化と密接に関連したものであり、一般の符号化対象に適用できるものではない。また、標準化として符号化方式が定まった場合、それをこのような手法により高速化することはできない一方、MPS、LPS処理のそれぞれを高速化する方法としては以下のようなものがある。

0061

たとえば、特開平8−195680は先行するデータを未確定のまま、継続する処理を二重に行い、先行するデータが確定した時に、その何れかを選択するものである。しかし、これは継続した処理を複数段にすると、処理量が指数関数的に大きくなり、実用的ではなくなる。また、仮にそれが実行可能であったとしても、そのほとんどが無駄な処理となり、回路規模消費電力などでは著しく不利となる。

0062

また、特開平10−135841は処理の一部をパイプライン化し、時間的に重複して行う方法である。これは回路規模、消費電力などの面において無駄がなく有利な方法であるが、並列実行できるのは高々1データの処理のみであり、それで得られる高速化の効果は小さい。

0063

本発明は、情報源のモデル化を用いるものではなく、一般の復号化対象においても効果を有することが特徴であり、また、可能性のある連鎖の全てを実行すると言うような事を行わないために、回路的、消費電力的に非常に有利なものとし、また、確率的に複数のデータを同時に処理するために、1つ1つのデータの復号化を高速化する方法に比較して、より大きな効果を得ることができるようにすることを目的とする。

課題を解決するための手段

0064

上述した目的を達成するために本発明の算術符号の復号化方法は、算術符号を復号化する算術符号の復号化方法において、ある復号化開始位置から後に続く所定長の優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖の仮定部分を投機的実行長とし、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語の領域を与える劣勢シンボルの積算生起確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定し、優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化する投機的復号処理を行うようにしている。

0065

このような算術符号の復号化方法において、前記投機的実行長に対応する優勢シンボルの連鎖の有無を判定した結果、その優勢シンボルの連鎖が無いと判定された場合は、入力データに対して1ステップごとの復号化処理を行うようにしている。

0066

また、この算術符号の復号化方法において、前記投機的復号処理に先立って、初期の符号語(Cとする)から前記投機的実行長の先頭位置に対応する優勢シンボル部分の符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)と符号語の領域に対して予め設定された下限値とを比較する処理を行い、(C−積算生起確率値)が下限値より大きい場合に、前記投機的復号化処理を行うようにしている。

0067

また、この算術符号の復号化方法において、前記投機的実行長に対応する優勢シンボルの連鎖の有無の判定は、投機的実行長の先頭に位置する当該優勢シンボル部分の符号語(C1とする)と、初期の符号語(Cとする)から前記投機的実行長の先頭に位置する当該優勢シンボルの符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)とについて、 C1<(C−積算生起確率値)を判定し、 C1<(C−積算生起確率値)を満たす場合は、前記優勢シンボルの連鎖が有りと判定し、 C1<(C−積算生起確率値)を満たさない場合は、前記優勢シンボルの連鎖が無しと判定するようにしている。

0068

また、この算術符号の復号化方法において、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定することも可能である。

0069

また、本発明の算術符号の復号化装置は、算術符号を復号化する算術符号の復号化装置において、入力データに対して1ステップごとの復号化処理を行うステップ復号化手段と、少なくとも1つの投機的実行長およびそれと対をなす積算確率値でなる投機的実行パラメータを記憶する投機的実行パラメータ記憶手段と、この投機的実行パラメータ記憶部を参照して投機的実行を行う投機的実行制御手段およびその投機的実行結果を判定する投機的実行判定手段とを有する投機的復号化手段と、前記投機的実行パラメータ記憶手段を参照し、前記投機的復号化手段と前記ステップ復号化手段のいずれかを選択する実行機能選択手段とを構成要素として含み、前記投機的復号化手段が行う投機的復号化処理は、ある復号化開始位置から後に続く所定長の優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖の仮定部分を投機的実行長とし、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語の領域を与える劣勢シンボルの積算生起確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定し、優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化するようにしている。

0070

このような算術符号の復号化装置において、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖が無いと判定された場合は、入力データに対して1ステップごとの復号化処理を行うようにしている。

0071

また、この算術符号の復号化装置において、前記投機的復号化手段が行う投機的復号化処理に先立って、前記実行機能選択手段は、初期の符号語(Cとする)から前記投機的実行長の先頭位置に対応する優勢シンボル部分の符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)と符号語の領域に対して予め設定された下限値とを比較する処理を行い、(C−積算生起確率値)が下限値より大きい場合に、前記投機的復号化処理を行うための指示を前記投機的復号化手段に出すようにしている。

0072

また、この算術符号の復号化装置において、前記投機的実行長に対応する優勢シンボルの連鎖の有無の判定は、投機的実行長の先頭に位置する当該優勢シンボル部分の符号語(C1とする)と、初期の符号語(Cとする)から前記投機的実行長の先頭に位置する当該優勢シンボルの符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)とについて、 C1<(C−積算生起確率値)を判定し、 C1<(C−積算生起確率値)を満たす場合は、前記優勢シンボルの連鎖が有りと判定し、 C1<(C−積算生起確率値)を満たさない場合は、前記優勢シンボルの連鎖が無しと判定するようにしている。

0073

また、この算術符号の復号化装置において、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定することも可能である。

0074

また、本発明の算術符号を復号化する算術符号の復号化処理プログラムは、ある復号化開始位置から後に続く所定長の優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖の仮定部分を投機的実行長とする手順と、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語の領域を与える劣勢シンボルの積算生起確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定する手順と、優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化する投機的復号処理を行う手順とを含むものである。

0075

このような算術符号の復号化処理プログラムにおいて、前記投機的実行長に対応する優勢シンボルの連鎖の有無を判定した結果、その優勢シンボルの連鎖が無いと判定された場合は、入力データに対して1ステップごとの復号化処理を行うようにしている。

0076

また、この算術符号の復号化処理プログラムにおいて、前記投機的復号処理に先立って、初期の符号語(Cとする)から前記投機的実行長の先頭位置に対応する優勢シンボル部分の符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)と符号語の領域に対して予め設定された下限値とを比較する処理を行い、(C−積算生起確率値)が下限値より大きい場合に、前記投機的復号化処理を行うようにしている。

0077

また、算術符号の復号化処理プログラムにおいて、前記投機的実行長に対応する優勢シンボルの連鎖の有無の判定は、投機的実行長の先頭に位置する当該優勢シンボル部分の符号語(C1とする)と、初期の符号語(Cとする)から前記投機的実行長の先頭に位置する当該優勢シンボルの符号語の領域を与える劣勢シンボルの積算生起確率値を引いた値(C−積算生起確率値)とについて、 C1<(C−積算生起確率値)を判定し、 C1<(C−積算生起確率値)を満たす場合は、前記優勢シンボルの連鎖が有りと判定し、 C1<(C−積算生起確率値)を満たさない場合は、前記優勢シンボルの連鎖が無しと判定するようにしている。

0078

また、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定することも可能である。

0079

このように、本発明の算術符号の復号化方法および装置は、投機的実行長に対応する優勢シンボルの連鎖を判定し、その優勢シンボルの連鎖があると判定された場合にはその優勢シンボルまとめて復号化するようにしているので、効率よく高速な復号化処理を行うことができ、また、情報源のモデル化を用いるものではなく、一般の復号化対象においても効果を有することが特徴である。

0080

また、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、従来から行われている1ステップごとの復号を行うようにしているので、優勢シンボルの連鎖がないと判定されたワーストケースであっても、従来と同様の復号化処理がなされるので、従来よりも処理が大幅に遅れることはなく、復号化処理全体としてみれば高速化が図れる。

0081

また、本発明の算術符号化処理は、符号語の領域が予め設定した範囲内に入るような正規化処理を考慮した処理設定となっている場合にも対応できる、さらに、適応化処理を行うような符号化処理にも適用することができる。

0082

また、投機的実行長に対応する優勢シンボルの連鎖を判定する処理は、C1<(C−積算生起確率値)を判断する単純な演算処理で行うことができ、復号化処理全体の処理を大きな負担を与えることはない。

0083

また、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、当該投機的実行長を1つの優勢シンボルに対応する分ずつ減じた長さにして、その投機的実行長に対応する優勢シンボルの連鎖を判定するようにしているので、優勢シンボルの連鎖がないと判定された場合であっても、いきなり従来のステップ復号化を行う場合に比べて、より高速な復号化が可能となる。

発明を実施するための最良の形態

0084

以下、本発明の実施の形態について説明する。なお、この実施の形態で説明する内容は、本発明の算術符号の復号化方法、算術符号の復号化装置についての説明であるとともに、本発明の算術符号の復号化処理プログラムの具体的な処理内容をも含むものである。本発明は、MPSとLPSの出現頻度に差が期待されると言う算術符号の根本的な原理により、複数個のMPSの連鎖を仮定することによって、復号化処理の高速化を図るものである。

0085

つまり復号化時においては、復号化点から後に続く、ある長さ(ここではこれを投機的実行長と呼んでいる)のMPSの連鎖を仮定し、それを実行した場合と実際のデータを比較し、それが成功した場合は、その投機的実行長のMPSを一度に復号化する事により、復号化処理を高速化するものである。

0086

なお、符号化時においては、入力データは既知であるので、その入力データ中に、投機的実行長に対応するMPSの連鎖がある場合、復号化時と同様のパラメータを用い、それらを一括して符号化することにより、符号化を高速化するものであるが、ここでは、特に復号化処理について説明する。

0087

以上、何れの場合も、投機的実行が失敗した場合は、入力データに対して1ステップごとに復号化を行う従来のステップ復号化処理が行われるので、たとえ、本発明におけるワーストケースにおいても、従来よりも処理が遅くなることはない。

0088

つまり、本発明による投機的実行処理が成功すれば処理は高速化されるし、もし、投機的実行処理が失敗したとしても従来例と同じ処理を行う。実際は、多少の条件判断が従来処理に追加されるが、この処理量は非常に小さいので、算術符号の復号化処理全体の処理量に与える影響は殆どないといえる。

0089

図1および図2は本発明の算術符号の復号化装置の実施の形態を説明する構成図であり、図1は生起確率の適応化処理を考慮しない単純な算術符号の復号化装置の構成例を示すもので、図2はより一般的な例として生起確率の適応化処理を考慮した算術符号の復号化装置の構成例を示すものである。

0090

図1に示す算術符号の復号化装置は、データ入力手段1、ステップ復号化手段2、コンテキスト記憶手段3、データ出力手段4、投機的実行パラメータ記憶手段5、投機的復号化手段6、実行機能選択手段7を有した構成となっている。なお、データ入力手段1、ステップ復号化手段2、コンテキスト記憶手段3、データ出力手段4は従来のステップ復号化処理を用いた算術符号の復号化装置に含まれる構成要素であり、コンテキスト記憶手段13は、この図1の場合、領域記憶手段31、符号記憶手段32、生起確率値記憶手段33を有している。なお、以下では生起確率を単に確率と表記し、本発明の実施の形態で用いる図1図10においても生起確率を単に確率と表現する。したがって、たとえば、確率値記憶手段は生起確率値記憶手段を意味し、積算確率値は積算生起確率値を意味している。

0091

投機的実行パラメータ記憶手段5は、投機的実行長を記憶する投機的実行長記憶手段51、それと対をなす積算確率値記憶手段52を有している。また、投機的復号化手段6は、投機的実行パラメータ記憶手段5とコンテキスト記憶手段3を参照して投機的実行を行う投機的実行制御手段61およびその投機的実行結果を判断する投機的実行判断手段62とを有している。また、実行機能選択手段7は、コンテキスト記憶手段3および投機的実行パラメータ記憶手段5を参照し、前記投機的復号化手段6とステップ復号化手段2のいずれかを選択する機能を有している。

0092

一方、図2に示す生起確率の適応化処理を考慮した算術符号の復号化装置も図1と同様に、従来のステップ復号化処理を用いた算術符号の復号化装置を構成するデータ入力手段1、ステップ復号化手段2、コンテキスト記憶手段3、データ出力手段4に加えて、投機的実行パラメータ記憶手段5、投機的復号化手段6、実行機能選択手段7を有した構成となっているが、この図2の場合、コンテキスト記憶手段3は、領域記憶手段31、符号記憶手段32、確率値選択・適応手段34を有しており、この確率値選択・適応手段34は、複数の確率値記憶手段351,・・・,35nとそれに対をなす適応先記憶手段361,・・・,36nを参照していずれかを選択する機能を有している。

0093

また、この図2の場合、投機的実行パラメータ記憶手段5は、複数の投機的実行長を記憶する投機的実行長記憶手段511,・・・,51nと、それと対をなす積算確率値記憶手段521,・・・,52nを有している。

0094

図3図1および図2の投機的復号化手段6が行う本発明の復号化処理を簡単に説明するものである。図3において、ある時点t0までの復号化処理が終了し、その時点t0での符号語の領域が図示の符号121で示す領域であったと仮定する。この後、図中の投機的実行長LだけMPSの連鎖があったと仮定すると、最終的に得られる符号語の領域は図示の符号122で示す領域となる。この後、MPSとLPSがどのように連鎖しようとも、符号語の領域は図示の符号122の領域となる。

0095

よって、本発明は、この図示の符号122で示す領域を与える積算確率値をあらかじめ保持し、その値と図示の符号122で示す領域の値より、この投機的実行長Lに対応するMPSの連鎖の有無を一度に判断するものである。

0096

この処理をフローチャートとしたものが図4である。図4において、その時点(図3におけるt1)において入力されている符号語(これをC1で表す)と、図示の符号121で示す領域の符号語(これをCで表す)から積算確率値を引いた値(C−積算確率値)との比較、つまり、C1<(C−積算確率値)を判断し(ステップS71)、 C1<(C−積算確率値)であれば、投機的実行長LのMPSを出力し(ステップS72)、次の入力データの復号化に移る(ステップS73)。一方、ステップS71における C1<(C−積算確率値)の判定結果が、 C1<(C−積算確率値)でなければ、従来のステップ復号化処理を行う(ステップS74)。

0097

つまり、図3における符号121で示す領域の符号語Cから、積算確率値を引いた値と、その時点で入力されている符号語C1との比較を行い、符号語C1が(C−積算確率値)の範囲に入っていればMPSの連鎖であることが判定され、投機的実行長LだけMPSの連鎖が有ることが判断される。また、符号語C1が(C−積算確率値)の範囲より大きければ、投機的実行長LだけMPSの連鎖が無いとが判断される。

0098

そして、もしも、MPSの連鎖があると判断された場合は、その投機的実行長Lに対応するMPSを一度に復号化する。また、その投機的実行長Lに対応するMPSの連鎖がないと判断された場合は、従来から行われている1ステップごとの復号化を行うステップ復号処理がなされる。

0099

以上の説明は、正規化処理、適応処理について述べていないが、たとえば、図2に示すような算術符号の復号化装置における算術符号の復号処理であっても、本発明は適用可能であることを以下に説明する。

0100

まず、正規化処理についてであるが、図2に見られるように、本発明においては投機的復号化手段6よる投機的復号化処理に先立った処理を行う実行機能選択手段7を有する。この実行機能選択手段7が行う処理についてを、図5のフローチャートにより説明する。

0101

図5において、まず、投機的実行長が0であるか否かを判定し(ステップS81)、投機的実行長が0であると指定されている場合は、当然であるが投機的実行を行わず、従来からのステップ復号化処理を行う(ステップS82)。なお、この投機的実行長をどのように決めるかは後述する。

0102

一方、投機的実行長が0でなければ、符号語Cから積算確率値を引いた値(C−積算確率値)と0x8000とを比較、つまり、(C−積算確率値)<0x8000の判断を行い(ステップS83)、(C−積算確率値)が0x8000よりも大きい場合のみ、投機的復号化を行う(ステップS84)。

0103

つまり、その時点の状態における符号語の領域が0x8000つまり0.75よりも大きい場合は、この区間で正規化処理が行われていないことを意味し、この区間で正規化処理を考慮する必要はない。

0104

次に適応処理であるが、まず基本的に、考慮している区間において正規化処理が行われた可能性は、上述した実行機能選択手段7の機能により排除されているので、先に述べたように、適応処理が正規化処理の同期して行われるような復号化方式においては、このような適応処理の効果を考慮する必要はない。しかし、本発明は、それとは異なる適応化方式、つまり、適応処理が正規化処理の同期して行われるとは限らない一般的な適応化方式においても適用できるようにしている。これについて図6を用いて説明する。図6(a)は、考慮している区間において、確率Qeを小さくするように適応処理が行われた場合である。つまり、MPSが連続している場合である。このとき、確率Qeの範囲は、図中の黒く塗りつぶした領域131へ変化するのであるが、これは、本発明が投機的実行を行うべき符号語の領域y1よりも広い領域y2へ広げてMPSの連鎖を判断するものであり、投機実行の成否の判断を行う範囲をより広くする方向としている。言い換えれば、本発明の投機実行の判定方法は、より厳しく投機実行の成否を判断することになる。そのため、本来はMPSの連鎖であって、投機が成功しているのに、それを失敗と判断することはあっても、投機が失敗しているにもかかわらず、誤って成功と判断してしまうといった不具合が発生することはない。よって、本発明の処理方法においては、効率が多少劣化することはあっても投機実行の成否の判断が破綻することはない。図6(b)は、図6(a)とは逆に、確率Qeの値を大きくするように適応処理が行われた場合である。つまり、その区間においてLPSがあった場合である。このとき、確率Qeの範囲は、図6(a)と同じく小さく黒く塗りつぶした範囲132となり、その範囲は、本発明の投機的実行の成否を判断する符号語の領域へy3だけ侵食してくることになる。しかし、このような適応が行われるのは、上述したように、データ中にLPSが現れた場合であり、復号化すべきデータは、その時点で本発明の投機的実行を成功と判断する領域以外へ変化することになる。つまり、確率Qeを大きくする前に、符号語そのものが、領域133へ変化することになり、結局、本発明の投機的実行は失敗であると判断される。したがって、このような状態においても、本発明が、投機的実行の失敗を、誤って成功と判断することはなく、本発明による投機実行の成否の判断が破綻することはない。以上のように本発明は、ある長さ(投機的実行長)のMPSの連鎖を仮定して、それに対応する処理を投機的に実行することにより、算術符号の復号化を高速化することができる。ここで、このある長さ(投機的実行長)は以下のようにして決められる。

0105

つまり、これまでの説明のように、符号語の領域の大きさは正規化処理により、平均値として、1.0前後にあることになる。したがって、MPSが連鎖した場合、その値が0.75を下回るまでは正規化処理が実行されず、同一の桁位置での処理が行われることになる。符号語の領域は、MPSが連鎖している間、1シンボル毎に確率Qeだけ減少することになるので、正規化処理が起動されるまでに、

0106

0107

だけのMPSが存在し得る。よって、投機的実行長としては、この値が適切であると言うことになる。

0108

図7図19で示した表にし、この(7)式を計算して投機的実行長を求め、また、そのときの確率Qeの積算値(積算確率値)を示したものである。この図7より明らかであるように、積算確率値の値が0x2aaa、つまり、0.25よりも小さい時には、投機的実行長は0となり、投機実行は行われない。また、この図7は原理的に非常に長い投機的実行が可能である値もあるが、あまり長い投機的実行は、実用上不利であるので、その最大長さを制限することも可能である。図8最大投機的実行長を15に制限した場合の表である。また、投機的実行に失敗した場合、すぐに従来のステップ復号化処理に移行せず、投機的実行長を1ずつ減らして実行する方が、実用上有利である場合がある。図9図8で示した表のデータに加え、投機的実行長(この図9は便宜上、投機的実行長の最大値を3としている)を1づつ減らして、投機的実行長を3から2さらに1へと減じたときの積算確率値を追加した例である。この例における処理の流れを図10のフローチャートに示す。図10において、まず、投機実行長を最大投機的実行長にセットする(ステップS91)。そして、投機的実行長が0か否かを判断し(ステップS92)、0でなければ、その投機的実行長に対応する積算確率値を読み込み(ステップS93)、符号語<(C−積算確率値)を判断し(ステップS94)、符号語<(C−積算確率値)であれば、そのときの投機的実行長に対応するMPSを出力して(ステップS95)、次のデータの復号化処理に移る(ステップS96)。また、ステップS94における判定結果が、符号語<(C−積算確率値)でなければ、投機的実行失敗として、そのときの投機的実行長から1を引いて(ステップS97)、再び、ステップS92に処理が戻り、ステップS92以降の処理を繰り返す。そして、投機的実行長が0であれば、従来からのステップ復号化処理を行う(ステップS98)。なお、図8の表による処理は、この図10のフローチャートから、投機的実行長に関するループつまり、ステップS97からステップS92へのループを削除したものに等しい。

0109

以上、本発明は2値のデータ列を効率よく復号化するものであり、2値画像の処理や、多値画像のビット面の符号化に適応できるものである。また、本発明は、情報のモデル化を行っておらず、そのため、より一般的なデータに適応可能なものである。

0110

なお、本発明は以上説明した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲で種々変形実施可能となるものである。たとえば、前述の実施の形態では、算術符号の復号化について説明したが、符号化も同様に行えることは勿論である。この符号化の場合は、入力データは既知であるので、その入力データ中に、投機的実行長に対応するMPSの連鎖がある場合、復号化時と同様のパラメータを用い、その投機的実行長に対応するMPSを一括して符号化することができる。

0111

また、本発明は、以上説明した本発明を実現するための処理手順記述された処理プログラムを作成し、その処理プログラムをフロッピィディスク光ディスクハードディスクなどの記録媒体に記録させておくことができ、本発明はその処理プログラムが記録された記録媒体をも含むものである。また、ネットワークから当該処理プログラムを得るようにしてもよい。

発明の効果

0112

以上説明したように本発明によれば、ある復号化開始位置から後に続く所定長の優勢シンボルの連鎖を仮定し、その優勢シンボルの連鎖に対応する部分を投機的実行長とし、その投機的実行長の先頭位置に対応する優勢シンボルの符号語とその符号語を与える劣勢シンボルの積算確率値に基づいて、その投機的実行長に対応する優勢シンボルの連鎖の有無を判定し、その優勢シンボルの連鎖が有ると判定された場合には、その投機的実行長の優勢シンボルをまとめて復号化するようにしているので、効率よく高速に復号化処理を行うことができる。また、前記投機的実行長に対応する優勢シンボルの連鎖を判定した結果、その優勢シンボルの連鎖がないと判定された場合は、従来からの1ステップごとの復号を行うようにしているので、優勢シンボルの連鎖がないと判定されたワーストケースであっても、従来と同様の復号化処理がなされるので、従来よりも処理が大幅に遅れることはなく、復号化処理全体としてみれば高速化が図れる。

図面の簡単な説明

0113

図1本発明の算術符号の復号化装置の実施の形態を説明する図であり、生起確率の適応化処理を考慮しない単純な算術符号の復号化装置の構成図である。
図2本発明の算術符号の復号化装置の実施の形態を説明する図であり、より一般的な例として生起確率の適応化処理を考慮した算術符号の復号化装置の構成図である。
図3本発明の算術符号の復号化方法を単純な例で説明する図である。
図4本発明の算術符号の復号化方法において、投機的実行長に対応するMPSの連鎖の有無を判定するフローチャートである。
図5本発明の算術符号の復号化装置における実行機能選択手段が行う処理を説明するフローチャートである。
図6(a)は処理対象となる区間において生起確率Qeを小さくするような適応化処理が行われた例を示す図であり、(b)は処理対象となる区間において生起確率Qeを大きくするような適応化処理が行われた例を示す図である。
図7計算によって得られたそれぞれの投機的実行長とそのときの生起確率Qeを、JPEG2000における適応化処理に用いられるデータに対応付けて示す図である。
図8図7で示す投機的実行長に制限を設けた場合を示す図である。
図9図8のデータに対し、投機的実行長を1つずづ減らした場合の積算確率値を付加して示す図である。
図10投機的実行に失敗した場合、投機的実行長を1つずつ減らして投機的実行を行う処理手順を示すフローチャートである。
図11算術符号化について説明する図であり、優勢シンボルと劣勢シンボルについての具体例を説明する図である。
図12算術符号化を多値画像に適用する場合の例を説明する図である。
図13算術符号の原理を説明する図であり、入力データ列と符号出力を説明する図である。
図14算術符号の原理を説明する図であり、入力データ列と領域選択の例を説明する図である。
図15算術符号の符号化処理を説明する原理的な処理手順であり、無限精度の浮動小数点演算を用いる場合のフローチャートである。
図16算術符号の復号化処理を説明する原理的な処理手順であり、無限精度の浮動小数点演算を用いる場合のフローチャートである。
図17算術符号の符号化および復号化処理における正規化処理について説明する図である。
図18算術符号の符号化および復号化処理における適応化処理について説明する図である。
図19JPEG2000における適応化処理において用いられるデータを示す図である。
図20算術符号の符号化処理を説明するフローチャートであり、正規化処理と適応処理を含んだフローチャートである。
図21算術符号の復号化処理を説明するフローチャートであり、正規化処理と適応処理を含んだフローチャートである。

--

0114

1データ入力手段
2 ステップ復号化手段
3コンテキスト記憶手段
4データ出力手段
5投機的実行パラメータ記憶手段
6投機的復号化手段
7実行機能選択手段
31 領域記憶手段
32 符号記憶手段
33確率値記憶手段
34 確率値選択・適応手段
351・・・35n 確率値記憶手段
361・・・36n 適応先記憶手段
511・・・51n 投機的実行長記憶手段
521・・・ 52n 積算確率値記憶手段
61 投機的実行制御手段
62 投機的実行判定手段
L 投機的実行長
121復号化処理の終了した時点t0における符号語の領域
122 投機的実行長の先頭に対応する符号語の領域(最終的に得られる符号語の領域)

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 株式会社東芝の「 AD変換回路」が 公開されました。( 2020/09/24)

    【課題】一つの実施形態は、信号に含まれる誤差を低減できるAD変換回路を提供することを目的とする。【解決手段】一つの実施形態によれば、AD変換回路の第1のΔΣ変換回路において、第1の量子化器は、1.5ビ... 詳細

  • 株式会社デンソーの「 データ圧縮方法、データ圧縮装置」が 公開されました。( 2020/09/24)

    【課題】データを可逆的且つ効率よく圧縮することができるデータ圧縮方法、データ圧縮装置を提供する。【解決手段】実施形態のデータ圧縮方法は、文字および数字の少なくとも一方を含むデータを圧縮するものであって... 詳細

  • シャープ株式会社の「 画像スケーリング変換、逆変換装置及び方法」が 公開されました。( 2020/09/24)

    【課題】画質の低下を抑制可能な画像処理装置を実現する。【解決手段】画素スケーリング階調変換部(51)は、入力画像の各画素値にオフセットを加算又は減算したうえでスケーリングすることによりスケーリング済画... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ