(57)【特許請求の範囲】
【請求項１】
パラメータに基づいて、シンボル群を可変長符号部分と固定長符号部分とにそれぞれ符号化する符号化手段を備える符号化装置であって、
隣接するパラメータ間における前記可変長符号部分の符号量の差分値を算出する差分手段と、
前記複数の差分値を所定値と比較する比較手段と、
該比較結果に基づいて、符号化に適用するパラメータ値を決定する決定手段と、
を有することを特徴とする符号化装置。
【請求項２】
前記パラメータは、前記固定長符号部分の符号長を示すことを特徴とする請求項１記載の符号化装置。
【請求項３】
前記決定手段は、前記可変長符号部分の符号量が最小となるパラメータ値を決定することを特徴とする請求項２記載の符号化装置。
【請求項４】
前記決定手段は、前記比較手段における複数の比較結果を変換することにより、前記パラメータを得ることを特徴とする請求項２記載の符号化装置。
【請求項５】
前記固定長部分は、パラメータの値が同じ場合に固定長となる符号部分であることを特徴とする請求項４記載の符号化装置。
【請求項６】
前記符号化手段は、ゴロムライス符号化を行うことを特徴とする請求項５記載の符号化装置。
【請求項７】
前記差分手段は、
シンボル群をその桁毎に並列に累積する累積手段と、
該複数の累積結果間における減算を行なう減算手段と、
を備えることを特徴とする請求項１記載の符号化装置。
【請求項８】
前記減算手段は、複数の減算器によって必要な減算処理を並列に行なうことを特徴とする請求項７記載の符号化装置。
【請求項９】
前記減算手段は、単一の減算器によって逐次減算処理を行なうことを特徴とする請求項７記載の符号化装置。
【請求項１０】
前記差分手段は、
シンボル群をその桁間において減算する減算手段と、
該減算結果を累積する累積手段と、
を備えることを特徴とする請求項１記載の符号化装置。
【請求項１１】
前記差分手段は、
シンボル群をその桁毎に１ビットデータを加算するビット加算手段と、
前記ビット加算された桁毎の値を累積する累積手段と、
を備えることを特徴とする請求項１記載の符号化装置。
【請求項１２】
前記差分手段は、
シンボル群を桁毎に累積する累積手段を備え、該累積手段は、１ビットのキャリー入力機能を有する全加算器を備えることを特徴とする請求項１記載の符号化装置。
【請求項１３】
前記差分手段は、
シンボル群を桁毎に累積する累積手段と、
シンボル群の桁毎に所定値の個数をカウントするカウント手段と、
前記累算値とカウント値とを加算する第１の加算手段と、
を有することを特徴とする請求項１記載の符号化装置。
【請求項１４】
更に、前記累積手段による累積値を所定倍する乗算手段と、
前記累積手段による累積値と前記カウント手段によるカウント値、及び前記乗算手段によって所定倍された累積値とを加算する第２の加算手段と、を有し、
前記累積手段は、シンボル群を所定の桁毎に累積し、該所定の桁以外の桁については前記第２の加算手段を適用することを特徴とする請求項１３記載の符号化装置。
【請求項１５】
前記比較手段は、複数の比較器によって必要な比較処理を並列に行なうことを特徴とする請求項１記載の符号化装置。
【請求項１６】
前記比較手段は、単一の比較器によって逐次比較処理を行なうことを特徴とする請求項１記載の符号化装置。
【請求項１７】
前記シンボル群は、多値画像データに対してウェーブレット変換を施して得られたサブブロックであることを特徴とする請求項１記載の符号化装置。
【請求項１８】
前記決定手段は、プライオリティ・エンコーダを備えることを特徴とする請求項１記載の符号化装置。
【請求項１９】
前記決定手段は、カウンタを備えることを特徴とする請求項１記載の符号化装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像データを符号化する符号化装置に関する。
【０００２】
【従来の技術】
一般に画像、特に多値画像は非常に多くの情報を含んでおり、その画像を蓄積・伝送する際には扱うデータ量が膨大になってしまうという問題がある。このため、画像の蓄積・伝送に際しては、画像の持つ冗長性を取り除き、多少の画質の劣化を容認することで、データ量の削減を図る高能率符号化が用いられる。
【０００３】
これら高能率符号化の１つとして、ＪＰＥＧ方式の圧縮符号化が知られている。この方式では多値画像をブロック毎にＤＣＴ変換することにより周波数成分に変換し、得られた変換係数を量子化して可変長符号化するというものである。
【０００４】
上記ＤＣＴ変換を用いた符号化は、圧縮率を高く設定すると復号画像にブロック歪みが発生してしまうという問題がある。近年、このような歪みを解消するために、ウェーブレット変換を用いる新たな符号化方式が提案されている。
【０００５】
また、これら種々の高能率符号化の一部として、可変長符号化が適用されることが多い。
【０００６】
【発明が解決しようとする課題】
しかしながら、多値画像を簡単な処理で可変長符号化するための方式、更にはこの可変長符号化方式を高速に実行するための処理装置の構成については、未だ確立されていないというのが現状である。
【０００７】
本発明は該状況に鑑みてなされたものであり、多値画像を簡易な構成で高速に可変長符号化する符号化装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するための一手段として、本発明の符号化装置は以下の構成を備える。
【０００９】
即ち、パラメータに基づいて、シンボル群を可変長符号部分と固定長符号部分とにそれぞれ符号化する符号化手段を備える符号化装置であって、隣接するパラメータ間における前記可変長符号部分の符号量の差分値を算出する差分手段と、前記複数の差分値を所定値と比較する比較手段と、該比較結果に基づいて、符号化に適用するパラメータ値を決定する決定手段と、を有することを特徴とする。
【００１０】
例えば、前記パラメータは、前記固定長符号部分の符号長を示すことを特徴とする。
【００１１】
例えば、前記決定手段は、前記可変長符号部分の符号量が最小となるパラメータ値を決定することを特徴とする。
【００１２】
【発明の実施の形態】
以下、本発明に係る一実施形態について、図面を参照して詳細に説明する。
【００１３】
＜第１実施形態＞
本実施形態においては、８ビットのモノクロ画像データを符号化する例について説明する。しかしながら本発明はこれに限らず、例えば各画素を４ビット表現とするモノクロ画像、或いは各画素における色成分（ＲＧＢ／Ｌａｂ／ＹＣｒＣｂ）を８ビットで表現するカラーの多値画像等を符号化する場合にも適用可能である。本発明をカラー多値画像に適用する場合には、各色成分をそれぞれモノクロ画像として符号化を行えばよい。
【００１４】
図１は、本実施形態を適用する符号化装置の構成を示すブロック図である。同図において、１０１は画像入力部、１０２はデータ格納部、１０３は離散ウェーブレット変換部、１０４は係数量子化部、１０５は符号化パラメータ選択部、１０６は可変長符号化部、１０７はビットプレーン走査部、１０８はバッファ、１０９は符号出力部である。
【００１５】
まず、画像入力部１０１では、符号化対象となる画素データをラスタスキャン順に入力する。この画像入力部１０１としては、例えばスキャナやデジタルカメラ等の撮像装置、或いはＣＣＤなどの撮像デバイス、或いはネットワーク回線のインターフェース等からの画像データ入力処理、等が挙げられる。
【００１６】
画像データ格納部１０２は例えばＲＡＭによって構成され、画像入力部１０１で入力される画像データを記憶するが、例えばＲＯＭ，ハードディスク，ＣＤ−ＲＯＭ等の記録媒体によって構成されても良い。
【００１７】
離散ウェーブレット変換部１０３では、画像データ格納部１０２に記憶した１画面分の画像データに対して周知の離散ウェーブレット変換を施し、複数の周波数帯域に分解する。本実施形態では、ｘ(ｎ)で示す画像データ列に対する離散ウェーブレット変換を、次式に基づいて行なうとする。
【００１８】
0004086424.tif 000002
尚、上式においてｒ(ｎ)，ｄ(ｎ)は変換係数であり、ｒ(ｎ)は低周波成分、ｄ(ｎ)は高周波成分である。
【００１９】
また上式において、floor{Ｘ}はＸを超えない最大の整数値を表す。本変換式は一次元のデータに対するものであるが、この変換を水平方向、垂直方向の順に適用することで二次元の変換を行なうことが可能である。入力された画像データ列に対してこの２次元変換を施すことにより、図２（ａ）に示す様なＬＬ，ＨＬ，ＬＨ，ＨＨの４つの周波数帯域（サブブロック）に分割することができる。これらの変換データは、次段の係数量子化部１０４へスムーズにデータを出力したり、あるいは、更なるウェーブレット変換を行なうため、データ格納部１０２に記憶される。
【００２０】
生成したＬＬ成分について、同様の手順にて更に離散ウェーブレット変換を施すことにより、図２（ｂ）に示す様に７個の周波数帯域（サブブロック）に分解される。本実施形態においては、更にもう一度離散ウェーブレット変換を施すことにより、画像データ列を図２（ｃ）に示す様にＬＬ，ＨＬ３，ＬＨ３，ＨＨ３，ＨＬ２，ＬＨ２，ＨＨ２，ＨＬ１，ＬＨ１，ＨＨ１の１０個の周波数帯域（サブブロック）に分割し、前記データ格納部１０２に記憶する。
【００２１】
変換係数はＬＬ，ＨＬ３，ＬＨ３，ＨＨ３，ＨＬ２，ＬＨ２，ＨＨ２，ＨＬ１，ＬＨ１，ＨＨ１のサブブロック順に、かつ各サブブロック毎にはラスタースキャン順に、データ格納部１０２から係数量子化部１０４へと出力される。
【００２２】
係数量子化部１０４は、ウェーブレット変換係数の各々を各周波数成分毎に定めた量子化ステップによって量子化し、量子化後の値を符号化パラメータ選択部１０５及びバッファ１０８へと出力する。
【００２３】
ここで係数値をＸ、この係数の属する周波数成分に対する量子化ステップの値をｑとすると、量子化後の量子化値Ｑ(Ｘ)は次式によって求められるとする。
【００２４】
Ｑ(Ｘ)＝floor{(Ｘ/ｑ)+0.5}
本実施形態における各周波数成分と量子化ステップとの関係を図３に示す。同図に示すように、低周波成分（ＬＬ等）よりも高周波成分（ＨＬ１，ＬＨ１，ＨＨ１等）の方が量子化ステップを大きくしている。これにより、視覚的に劣化の目立ちにくい高周波成分の情報をより削減するようにし、圧縮率の向上を図っている。
【００２５】
上記量子化値は、符号化パラメータ選択部１０５で評価され、後段の可変長符号化部１０６でこの量子化値を符号化する際に必要となるｋパラメータが決定されるまで、バッファ１０８に保持される。
【００２６】
符号化パラメータ選択部１０５では、上記量子化値に基づいて後段の可変長符号化部１０６で使用されるｋパラメータを選択する。
【００２７】
このｋパラメータとは、ゴロムライス（Golomb Rice）符号化という可変長符号化を行なう際の固定長部の符号長を示す値である。説明の都合上、符号化パラメータ選択部１０５について説明する前に、可変長符号化部１０６におけるゴロムライス符号化処理について説明する。
【００２８】
この可変長符号化部１０６で行なうゴロムライス符号化処理の基本的な方法は周知ではあるが、以下に、この符号化の基本的な動作及び本発明の特徴的な部分について説明する。
【００２９】
まず、量子化値を格納したバッファ１０８から１サブブロック分のデータを順次読み出す。次に、可変長符号化部１０６において、該サブブロックに対応するｋパラメータに基づき、以下に説明する前処理及びゴロムライス符号化処理を行なう。
【００３０】
可変長符号化部１０６は、入力した各量子化値の正／負を調べ、負号ビットを出力する。具体的には、量子化値が０または正である場合には「０」を、負である場合には「１」を出力した後、該量子化値を絶対値に変換する。尚、この処理は厳密にはゴロムライス符号化処理には含まれないが、本実施形態ではこれをゴロムライス符号化の前処理として、可変長符号化部１０６内で行なうものとする。
【００３１】
次に、該絶対値をゴロムライス符号化する。符号化対象となる量子化値の絶対値をＶ、処理対象のサブブロックに適用されるｋパラメータの値がｋである場合のゴロムライス符号化処理は次の手順にて行なう。
【００３２】
まず、２進表現したＶをｋビット右シフトした後に、得られた値の個数だけ「０」を連続して配置し、その次に区切りのビットとして「１」を配置し、その次に元のＶの下位ｋビットを配置することにより、可変長符号（ゴロムライス符号）を生成する。
【００３３】
図４に、Ｖ＝０〜７，ｋ＝０，１，２に対するゴロムライス符号の例を示す。同図から分かるように、絶対値Ｖ及びパラメータｋから得られる各可変長符号の符号長は、Ｖ＞＞ｋ（Ｖをｋビット右シフトした値）＋１（区切りビット）＋ｋ（パラメータの値）ビット、であることが容易に推測できる。また、正／負を表わす負号ビットを加えれば、さらに１ビット増える。
【００３４】
また、同図からも分かるように、ｋ＝０の時のＶ＝０に対するゴロムライス符号長が、ｋ＝１，２の時よりも特に短くなっている。これは、符号化される量子化値群が０に偏っているため、ｋパラメータを小さくして符号化する方が適していることを示している。
【００３５】
また、ここで用いるゴロムライス符号化は、図４に示すような符号表を実際に保持することなく、簡単な演算によって符号化及び復号が実行可能であるという効果がある。尚、通常のハフマン符号化等の可変長符号化では、符号化対象値に対する可変長符号を示すテーブルを保持しなければならない。特に、関連する状態に応じて、符号化対象値に対して複数の可変長符号を適宜切り換える場合には、上記テーブルを複数持つ必要がある。
【００３６】
以上のようにして、入力される量子化値に対する負号ビット（＋／−を表わす）と可変長符号（ゴロムライス符号）からなる符号化データを生成し、後段のビットプレーン走査部１０７へ出力する。
【００３７】
次に、上述した可変長符号化部１０６で必要となるｋパラメータを生成する、符号化パラメータ選択部１０５における処理について説明する。
【００３８】
符号化するサブブロックの全符号量Ｔは、ｋパラメータの値をｐとすると
0004086424.tif 000003
となる。
【００３９】
符号化するサブブロック内の量子化値の数をＮ個とすると、上記（１）式は下式のようになる。
【００４０】
Ｔp ＝ (ｐ＋２)×Ｎ＋ΣＶi＞＞ｐ          ・・・（２）
上記（２）式の第１項：(ｐ＋２)×Ｎ が固定長符号部分による符号量を示し、第２項：ΣＶi＞＞ｐ が可変長符号部分による符号量を示す。ここで第２項のみ、即ち可変長符号量を以下の（３）式のようにＳpと表すとする。
【００４１】
Ｓp＝ΣＶi＞＞ｐ                        ・・・（３）
このＳpは、ｐの値が小さい程大きくなる。一方、固定長符号部分の符号量はｐの値に比例して大きくなり、ｐが１つ大きくなると該符号量はＮビット増える。
【００４２】
次に、Ｖiを２進表現したときの各ビットプレーンにおける「１」の個数について考える。Ｖi＞＞ｐの最下位ビットのプレーン中に存在する「１」の数をＢp+1とし、以下の（４）式で示す。
【００４３】
Ｂp+1＝Σ(Ｖi＞＞ｐ)＆１                ・・・（４）
即ち、Ｂ1はＶiの最下位ビットプレーン中の「１」の個数を表わし、Ｂ2はＶiの最下位ビットから２番目のプレーン中の「１」の個数を表わす。以上により、
0004086424.tif 000004
という関係と、（３），（４）式から、
Ｓp ＝ ２×Ｓp+1＋Ｂp+1                        ・・・（６）
という関係式が得られる。
【００４４】
ここで、ｋパラメータの値が１つだけ異なるＳp-1とＳp間の差分をＤpとすると、
0004086424.tif 000005
このＤpは、ｋパラメータの値がｐからｐ−１に変わることで、可変長符号量がどれだけ増えるかを表わすものである。この値がＮより小さいなら、全体の符号量は Ｎ−Ｄp だけ減るので、ｋパラメータの値はｐよりもｐ−１にする方が効率的である。逆に、Ｄp≧Ｎ ならばｋパラメータの値はｐとする方がよい。
【００４５】
上記（７）式をさらに変形すると、
0004086424.tif 000006
ここで、Ｓp，Ｂp-1≧０ であるから
Ｄp-1≧Ｄp                      ・・・（８）  上記（８）式の関係と、上述した説明から次のことが言える。
【００４６】
「数列：Ｄ1，Ｄ2，Ｄ3，…，Ｄp-1，Ｄp，Ｄp+1，…，Ｄm には、Ｄ1≧Ｄ2≧Ｄ3≧…≧Ｄp-1≧Ｄp≧Ｄp+1≧…≧Ｄm という関係があり、Ｄq≧Ｎ≧Ｄq+1 となるｑが存在するとき、このｑはｋパラメータの最適値の内の１つである（Ｎはサブブロック内の量子化値の数）。」
ここでいう最適値とは、ゴロムライス符号化したときの全体の符号量が最小になる値を意味する。また、ｍはゼロでないＢpの中で最も大きなｐの値であり、このｍに対応するＳmはゼロある。これは、一番大きな量子化絶対値をｍビット右シフトすると０になるためである。よって、Ｄm＝Ｂm≦Ｎ である。
【００４７】
即ち、ｋパラメータがｑからｑ＋１になると符号量がＮ−Ｄq+1だけ増加し、ｋパラメータがｑからｑ−１になると符号量がＤq−Ｎだけ増加することが分かる。但し、Ｄq+1＝ＮまたはＤq＝Ｎの時は符号量は増えず、最小のままである。尚、Ｄq+1＝Ｎの時はｑ＋１も最適値となり、Ｄq＝Ｎの時はｑ−１も最適値となる。
【００４８】
ｋパラメータの最適値は、最大３個存在しうる。その条件はＤq＝Ｎ＝Ｄq+1が成立する時であり、言い替えると、Ｓq-1＝０，Ｓq＝Ｎ，Ｓq+1＝２Ｎとなる時である。即ち、ｑ−１，ｑ，ｑ＋１がｋパラメータの最適値となり、全符号量Ｔは極値（最小値）をとる。よって、ｋパラメータが上記最適値から遠ざかる程、全符号量は増加する。
【００４９】
一方、上記ｑが存在しない場合は、Ｎ＞Ｄ1 となる時であり、この場合ｋパラメータの値が０で全符号量が最小となる。そして、全符号量はｋの値の変化（増加）に対して単調増加となる。
【００５０】
ここで、前記数列と最適値に関する関係を一般化するために、Ｄ0＝Ｄ1＋２Ｎと定義する。すると、次のことが言える。
【００５１】
「数列：Ｄ0，Ｄ1，Ｄ2，Ｄ3，…，Ｄp-1，Ｄp，Ｄp+1，…，Ｄm には、Ｄ0≧Ｄ1≧Ｄ2≧Ｄ3≧…≧Ｄp-1≧Ｄp≧Ｄp+1≧…≧Ｄm という関係があり、Ｄq≧Ｎ≧Ｄq+1 となるｑが存在するとき、このｑはｋパラメータの最適値の内の１つである。」
これにより、最適値ｑの存在が明確なものとなる。
【００５２】
ここで、ＤpとＮとの比較結果Ｃpを次式のように定義すると
Ｃp＝１    ：Ｄp＞Ｎの時
Ｃp＝０    ：Ｄp≦Ｎの時                    ・・・（９）
前述の Ｄ0≧Ｄ1≧Ｄ2≧Ｄ3≧…≧Ｄp-1≧Ｄp≧Ｄp+1≧…≧Ｄm という開係から、Ｃ0≧Ｃ1≧Ｃ2≧Ｃ3≧…≧Ｃp-1≧Ｃp≧Ｃp+1≧…≧Ｃm という関係が得られる。これは、Ｃ0，Ｃ1，Ｃ2，Ｃ3，…，Ｃp-1，Ｃp，Ｃp+1，…，Ｃm という数列が、Ｃ0＝１から始まってＣm＝０で終わり、途中１から０への変化点が一個所あるが、０から１への変化点はないことを示している。
【００５３】
上記数列（Ｃ0，Ｃ1，Ｃ2，…）中において、その値が１から０に変化する箇所は、ＤpとＮの大小関係が逆転する箇所である。
【００５４】
先頭のＣ0＝１を除いた、Ｃ1から始まる１の個数がｑ個ある時、即ち、Ｃq＝１，Ｃq+1＝０である時、Ｄq≧Ｎ＞Ｄq+1となるので、ｑがｋパラメータの最適値となる。
【００５５】
以上の原理を利用して、本実施形態は符号化パラメータ選択部１０５を構成する。符号化パラメータ選択部１０５のブロック構成を図５に示す。同図において、５０１は係数量子化部１０４から送られる量子化値を入力する端子、５０２ａ，５０２ｂ，５０２ｃ，…，５０２ｐは、入力された量子化値を順次１ビットずつ右へシフトするビットシフタ、５０３ａ，５０３ｂ，５０３ｃ，…，５０３ｑは、順次入力されるＮ個の値を加算する累算器、５０４ａ，５０４ｂ，５０４ｃ，…，５０４ｐは、隣接する２つの累算器の出力の差を求める減算器、５０５ａ，５０５ｂ，５０５ｃ，…，５０５ｐは、減算器の出力を所定値Ｎと比較する比較器、５０７は比較器による複数の比較結果から最適なｋパラメータを求めるプライオリティ・エンコーダである。
【００５６】
尚、図５に示すビットシフタ群５０２は、説明の都合上導入したものであって、回路構成上はほとんど実体の無いものである。即ち、各ビットシフタの入出力間では、信号の位取りが１ビット異なるだけであるから、ビットシフタを１つ通過するごとに、配線を上位側へ１ビットずつずらしていけば良い。
【００５７】
端子５０１から入力されるｉ番目の量子化値をＶiとすると、ビットシフタ５０２ａの出力はＶi＞＞１、ビットシフタ５０２ｂの出力はＶi＞＞２、ビットシフタ５０２ｃの出力はＶi＞＞３，…となる。
【００５８】
各々の累算器５０３は、サブブロックの最初の入力データで０に初期化され、入力データ及び各ビットシフタの出力を次々に加算し累算する。例えば、累算器５０３ｃは、Ｖi＞＞２（ｉ＝１，２，…，Ｎ−１，Ｎ）を累算する。
【００５９】
その結果、ｋパラメータ＝０，１，２，…，ｍに対する可変長符号部分の符号量が、各累算器から出力される。具体的には、累算器５０３ａからは、Ｓ0＝ΣＶi＞＞０、累算器５０３ｂからは、Ｓ1＝ΣＶi＞＞１、累算器５０３ｃからは、Ｓ2＝ΣＶi＞＞３といった具合である。
【００６０】
これらの累算器５０３の出力を減算器５０４に入力して、ｋパラメータが１つだけ異なる場合に可変長符号部分の符号量がどれだけ違うのか、すなわち前記（６）式におけるＤp＝Ｓp-1−Ｓpを、すべてのパラメータ値（ｐ＝１，２，３，…，ｍ）について計算する。
【００６１】
減算器５０４ａからは、Ｄ1＝Ｓ0−Ｓ1、減算器５０４ｂからは、Ｄ2＝Ｓ1−Ｓ2、減算器５０４ｃからは、Ｄ3＝Ｓ2−Ｓ3，…が出力される。
【００６２】
これらの減算器出力をサブブロック内の量子化値の個数Ｎと比較し、前記（８）式の判定を行ない、その判定結果Ｃpを、各比較器５０５から出力する。
【００６３】
前述のように、Ｃ0，Ｃ1，Ｃ2，…，Ｃp，…，Ｃmには順序関係があり、前半が１で後半に０がくる。この前半の１の数によって、ｋパラメータの最適値が決まる。この１の数をｋパラメータの値に変換するために、プライオリティ・エンコーダ５０７を用いる。
【００６４】
プライオリティ・エンコーダ５０７は、１５ビット入力かつ４ビット出力を行う。即ち、１５個の比較結果を入力し、ｋパラメータの値として０〜１５の値を出力する。図６に、プライオリティ・エンコーダ５０７における入出力関係を示す。
【００６５】
尚、図５に示した符号化パラメータ選択部１０５の構成においては、並列処理可能な箇所は全て並列に処理を行うために、減算器や比較器を複数備える例を示したが、減算器と比較器をそれぞれ１個だけ備える構成とし、ＤpとＣpをｐ＝１，２，３…，ｍの順にＣp＝０になるまでシーケンシャルに計算し、Ｃp＝０になった時のｐの値から１を減算した値（ｐ−１）をｋパラメータの値にすることも可能である。
【００６６】
符号化パラメータ選択部１０５では、以上のように処理を行なって最適なｋパラメータを導出し、既に説明した可変長符号化部１０６では、該ｋパラメータに基づいて符号化処理を実行する。符号化されたデータは、次段のビットプレーン走査部１０７に出力される。
【００６７】
ビットプレーン走査部１０７においては、量子化値毎に符号化・出力された符号化データを受け取り、それをビットプレーン単位に並び替えて出力するものである。これを、上述した周波数成分（サブブロック）単位で行なう。
【００６８】
まず、可変長符号化部１０６で生成された符号化データを、ｋパラメータの値で決まる固定長符号部分と可変長符号部分とに分離する。尚、符号にはその外に１ビット固定の負号ビットが含まれている。
【００６９】
そして重要な情報から走査を開始するが、まず最初に負号ビットをサブブロック内の全量子化値に対して走査する。次に、量子化値の上位ビットの情報を有する可変長符号部分を上位ビットプレーンから順に走査する。最後に、固定長符号部分を上位ビットプレーンから順に走査する。
【００７０】
図７に、本実施形態においてｋパラメータが２である場合に生成される、各量子化値に対するゴロムライス符号（但し、可変長符号部分と固定長符号部分とを分離したもの）及びその走査順序の一例を示す。以下、図７を参照して、可変長符号部分の走査についてもう少し詳しく説明する。可変長符号は符号長が一定でないため、短い符号と長い符号をどのようにそろえて並べるかが一意に定まらない。そこで本実施形態においては、可変長符号の先頭ビットが同じプレーンになるように並べるとする。即ち、可変長符号は図７に示す可変長符号領域の上から順にうめるようにして並べる。上記ビットプレーン情報を上位ビットから順に走査すると、短い符号では途中のプレーンから情報（符号ビット）が無くなるので、情報の無い符号は走査をスキップする。よって、下位のビットプレーンへ行くにつれ、走査する情報（符号ビット）が少なくなる。
【００７１】
図８に、図７に示す符号に対して上記順序（負号ビット，可変長符号，固定長符号）での走査を行うことによって得られるビット情報の並びを示す。
【００７２】
ビットプレーン走査部１０７においては、このようなビットプレーン走査をサブブロック単位でＬＬ，ＨＬ３，ＬＨ３，ＨＨ３，ＨＬ２，ＬＨ２，ＨＨ２，ＨＬ１，ＬＨ１，ＨＨ１の順に行なう。
【００７３】
ビットプレーン走査部１０７から出力されたビット列は、次段の符号出力部１０９において、順次転送される。転送先は、ハードディスクやＤＶＤ等の記録メディアであっても良いし、インターネット、一般公衆回線、無緑回線等のインターフェースであっても良い。
【００７４】
尚、本実施形態において生成された符号化データには、復号時に必要となる各種情報、すなわち、画像サイズ、１画素あたりのビット数、各周波数成分に対する量子化ステップ、ｋパラメータの値等を、付属情報として符号化データに適宜付加することが可能である。
【００７５】
以上説明したように本実施形態によれば、パラメータｋに基づいて画像データ列をゴロムライス符号化する際に、簡易な構成でｋ毎の可変長符号量の差分値を所定値と比較することによって、ｋの最適値を高速に決定することができる。
【００７６】
＜第２実施形態＞
以下、本発明に係る第２実施形態について説明する。第２実施形態における符号化装置の構成は、上述した図１と同様である。
【００７７】
図９に、第２実施形態における符号化パラメータ選択部１０５の詳細構成を示す。同図において、上述した第１実施形態で示した図５における構成と同様の動作を行うものには同一番号を付し、説明を省略する。
【００７８】
図９において、７０３ａ，７０３ｂ，７０３ｃ，…は、各ビットシフタ５０２の入出力間の差を求める減算器、７０４ａ，７０４ｂ，７０４ｃ，…は、上記減算器の出力を加算していく累算器である。
【００７９】
第２実施形態におけるｋパラメータの最適値決定の原理は、第１実施形態で説明した（７）式：Ｄp＝Ｓp-1−ＳpにおけるＳp-1，Ｓpに、（３）式を代入した以下の式に基づく。
【００８０】
0004086424.tif 000007
上記（１０）式における（Ｖi＞＞(ｐ-１))−(Ｖi＞＞ｐ)は、図９において上からｐ番めのビットシフタ５０２の入力値と出力値の差分（入力値−出力値）を意味する。よって、該差分値を減算器７０３で求め、その総和（Σ）に相当する部分を累算器７０４で算出する。
【００８１】
各累算器７０４から出力されるＤpは、上述した第１実施形態における減算器５０４からの出力と等価であるため、比較器５０５以降の処理は第１実施形態の場合と全く同様である。
【００８２】
即ち、第２実施形態における符号化パラメータ選択部１０５の構成においては、上述した第１実施形態における構成と比べて、ただ単に減算器と累算器の配置が入れ替わったのみならず、減算器の規模が小さくなると言う利点がある。例えばＮの値を６４とすると、累算器７０４の出力ビット幅は入力ビット幅より６ビット大きい。この場合、累算器７０４の入力側にある減算器７０３のビット幅は、出力側にある場合（第１実施形態における減算器５０４に相当）のビット幅よりも６ビット分小さくて済む。
【００８３】
尚、第２実施形態においても、減算器７０３を１個だけ備える構成とし、ＤpとＮをｐ＝１，２，３…，ｍの順にＣp＝０になるまでシーケンシャルに比較してゆき、Ｃp＝０になった時のｐの値から１を減算した値（ｐ−１）をｋパラメータの値にすることも可能である。
【００８４】
より具体的には、初期値０から始まるカウンタの動作と同期して、比較処理を行なってゆく構成が考えられる。即ち、カウント値０でＤ1とＮを比較してＣ1を出力し、カウント値１でＤ2とＮを比較してＣ2を出力し、Ｃp＝０になるまで順次比較処理を行なって行く。すると、Ｃp＝０になった時のカウント値はｐ−１であるため、該カウント値をｋパラメータの値として出力すれば良い。
【００８５】
以上説明したように第２実施形態によれば、第１実施形態よりも更に簡易な構成で、パラメータｋの最適値を高速に決定することができる。
【００８６】
＜第３実施形態＞
以下、本発明に係る第３実施形態について説明する。第３実施形態における符号化装置の構成は、上述した図１と同様である。
【００８７】
図１０に、第３実施形態における符号化パラメータ選択部１０５の詳細構成を示す。同図において、上述した第２実施形態で示した図９における構成と同様の動作を行うものには同一番号を付し、説明を省略する。
【００８８】
図１０において、８０３ａ，８０３ｂ，８０３ｃ，…は、ビット列に１ビットを加算する＋１加算器である。
【００８９】
第３実施形態におけるｋパラメータの最適値決定の原理は、既に説明した（５）式を変形して（１０）式に適用することによって得られる（１１）式に基づく。即ち、
0004086424.tif 000008
（５）式を変形することにより下式が得られる。
【００９０】
Ｖi＞＞(ｐ-１)＝２×(Ｖi＞＞ｐ)＋((Ｖi＞＞(ｐ-１))＆１)
これを（１０）式に代入することにより、
0004086424.tif 000009
（１１）式における(Ｖi＞＞ｐ)＋((Ｖi＞＞(ｐ-１))＆１)は、図１０において上からｐ番めのビットシフタ５０２の出力値に、入力側の最下位ビット（ＬＳＢ）を加算することを意味している。よって、該加算値を＋１加算器８０３で求め、その総和（Σ）に相当する部分を累算器７０４で算出する。
【００９１】
各＋１加算器８０３から出力される値は、上述した第２実施形態における減算器７０３からの出力と等価であるため、累算器７０４以降の処理は第２実施形態と全く同様である。
【００９２】
即ち、第３実施形態における符号化パラメータ選択部１０５の構成においては、上述した第２実施形態における減算器７０３が＋１加算器８０３に置き換わるため、ハードウェア規模を更に小さくすることができる。
【００９３】
尚、第３実施形態においても第２実施形態と同様に、比較器５０５を１個だけ備える構成とし、ＤpとＮをｐ＝１，２，３…，ｍの順にＣp＝０になるまでシーケンシャルに比較してゆき、Ｃp＝０になった時のｐの値から１を減算した値（ｐ−１）をｋパラメータの値にすることも可能である。
【００９４】
以上説明したように第３実施形態によれば、第２実施形態よりも更に簡易な構成で、パラメータｋの最適値を高速に決定することができる。
【００９５】
＜第４実施形態＞
以下、本発明に係る第４実施形態について説明する。第４実施形態における符号化装置の構成は、上述した図１と同様である。
【００９６】
第４実施形態においては、符号化パラメータ選択部１０５の構成において、その累算器の内部に備える加算器として、キャリー入力機能を持つ全加算器を使用することを特徴とする。これにより、第３実施形態で示した＋１加算器８０３を備える必要が無くなる。
【００９７】
上述した第１乃至第３実施形態で示した累算器（５０３，７０４）においては、キャリー入力を備えない半加算器とキャリー入力を備える全加算器のいずれも使用可能であった。但し、全加算器を使用した場合、該キャリー入力には０を与えておく必要があった。
【００９８】
ここで、第１乃至第３実施形態で使用可能な半加算器型の累算器の構成を図１１（ａ）に、第４実施形態で使用する全加算器型の累算器の構成を図１１（ｂ）に示す。
【００９９】
全加算器は、半加算器の機能に対して更に、＋１ビットを行う機能が付加されたもものであるため、上述した第３実施形態において累算器の前段に備える必要のあった＋１加算器８０３の機能を、累算器７０４内の全加算器に取り込むことができる。この場合、全加算器の回路規模は当然、半加算器の回路規模よりも大きくなるが、第３実施形態のように半加算器と＋１加算器をそれぞれ独立に備える場合と比べると、はるかに小さい。
【０１００】
以上説明しいたように第４実施形態によれば、第３実施形態における＋１加算器８０３と累算器７０４を、図１１（ｂ）に示す全加算器型の累算器に統合することにより、さらにハードウェア規模を小さくすることができる。
【０１０１】
＜第５実施形態＞
以下、本発明に係る第５実施形態について説明する。第５実施形態における符号化装置の構成は、上述した図１と同様である。
【０１０２】
図１２に、第５実施形態における符号化パラメータ選択部１０５の詳細構成を示す。同図において、上述した第１実施形態で示した図５における構成と同様の動作を行うものには同一番号を付し、説明を省略する。
【０１０３】
図１２において、１００３ａ，１００３ｂ，１００３ｃ，…は、カウンタ、１００４ａ，１００４ｂ，１００４ｃ，…は、加算器である。
【０１０４】
第５実施形態におけるｋパラメータの最適値決定の原理は、既に説明した（７）式に基づく。
【０１０５】
Ｄp＝Ｓp＋Ｂp（ｐ≧１）                          ・・・（７）
カウンタ１００３ａ，１００３ｂ，１００３ｃ，…は、上記（７）式におけるＢpを各プレーンごとに、１ビットずつカウントするものであり、加算器１００４ａ，１００４ｂ，１００４ｃ，…は、上記（７）式におけるＳp＋Ｂpを演算するものである。
【０１０６】
各加算器１００４の出力は、第１実施形態において図５に示した減算器５０４ａ，５０４ｂ，５０４ｃ，…の出力と等価である。従って第１実施形態と同様に、比較器５０５ａ，５０５ｂ，５０５ｃ，…において加算器１００４の出力を所定値Ｎと比較し、該比較結果Ｃpをプライオリティ・エンコーダ５０７に入力してｋパラメータの値に変換する。
【０１０７】
以上説明したように第５実施形態によれば、カウンタを用いた構成によっても、パラメータｋの最適値を高速に決定することができる。
【０１０８】
＜第６実施形態＞
以下、本発明に係る第６実施形態について説明する。第６実施形態における符号化装置の構成は、上述した図１と同様である。
【０１０９】
図１３に、第６実施形態における符号化パラメータ選択部１０５の詳細構成を示す。同図において、上述した第５実施形態で示した図１２における構成と同様の動作を行うものには同一番号を付し、説明を省略する。
【０１１０】
図１３において、１１０５ａ，１１０５ｃ，…は、累算器の出力を２倍にするために該出力を１ビット左シフトするビットシフタ、１１０７ａ，１１０７ｃ，…は、３入力のデータを加算する加算器である。
【０１１１】
第６実施形態においては、上述した第５実施形態におけるＳ1，Ｓ3，Ｓ5，…，Ｃ2i+1の算出に、先に示した（６）式を適用することを特徴とする。
【０１１２】
Ｓp＝２×Ｓp+1＋Ｂp+1                            ・・・（６）
即ち、２×Ｓ2i＋Ｂ2iからＳ2i-1 を演算し、該Ｓ2i-1にＢ2i-1を加算してＤ2i-1を求める。尚、Ｄ2iについては、第５実施形態と同様の演算によって求める。
【０１１３】
第６実施形態においては即ち、ビットシフタ１１０５ａ，１１０５ｃ，…において２×Ｓ2iを求め、加算器１１０７ａ，１１０７ｃ，…において２×Ｓ2i，Ｂ2i，Ｂ2i-1の３つの項を加算する。この演算により、各比較器５０５の入力に必要なＤp（ｐ＝１，２，３…）が全てそろうため、以降は第５実施形態と同様の処理でｋパラメータの最適値を得ることができる。
【０１１４】
以上説明したように第６実施形態によれば、第５実施形態で示した構成から更に累算器を減らした構成によって、パラメータｋの最適値を高速に決定することができる。
【０１１５】
【発明の効果】
以上説明したように本発明によれば、多値画像を簡易な構成で高速に可変長符号化する符号化装置を提供することができる。
【図面の簡単な説明】
【図１】本発明に係る一実施形態における符号化装置の構成を示すブロック図、
【図２】離散ウェーブレット変換の様子を示す図、
【図３】周波数成分（サブブロック）に用いる量子化ステップの一例を示す図、
【図４】ゴロムライス符号化によって得られる符号の一例を示す図、
【図５】本実施形態における符号化パラメータ選択部１０５の詳細構成を示すブロック図、
【図６】本実施形態におけるプライオリティ・エンコーダの入出力関係を示す図、
【図７】本実施形態におけるビットプレーン毎のゴロムライス符号例を示す図、
【図８】最終的に出力されるビットストリーム例を示す図、
【図９】第２実施形態における符号化パラメータ選択部１０５の詳細構成を示すブロック図、
【図１０】第３実施形態における符号化パラメータ選択部１０５の詳細構成を示すブロック図、
【図１１】第４実施形態における加算器の構成を示すブロック図、
【図１２】第５実施形態における符号化パラメータ選択部１０５の詳細構成を示すブロック図、
【図１３】第６実施形態における符号化パラメータ選択部１０５の詳細構成を示すブロック図、である。
【符号の説明】
１０１  画像入力部
１０２  データ格納部
１０３  離散ウェーブレット変換部
１０４  係数量子化部
１０５  符号化パラメータ選択部
１０６  可変長符号化部
１０７  ビットプレーン走査部
１０８  バッファ
１０９  符号出力部
５０２，１１０５  ビットシフタ
５０３，７０４  累算器
５０４，７０３  減算器
５０５  比較器
５０７  プライオリティ・エンコーダ
８０３  ＋１加算器
１００３  カウンタ
１００４，１００７  加算器
【図１】
0004086424.tif 000010
【図２】
0004086424.tif 000011
【図３】
0004086424.tif 000012
【図４】
0004086424.tif 000013
【図５】
0004086424.tif 000014
【図６】
0004086424.tif 000015
【図７】
0004086424.tif 000016
【図８】
0004086424.tif 000017
【図９】
0004086424.tif 000018
【図１０】
0004086424.tif 000019
【図１１】
0004086424.tif 000020
【図１２】
0004086424.tif 000021
【図１３】
0004086424.tif 000022