(57)【特許請求の範囲】
【請求項１】
画像を表す複数の係数を発生する発生手段と、
該発生手段により発生した複数の係数を、予め予測された該係数の頻度分布に基づいて各係数毎に可変長符号化する可変長符号化手段と、
該可変長符号化手段の可変長符号化により得られた各係数に対応する可変長符号化データの各ビットを、各可変長符号化データの最上位ビットを基準として、各可変長符号化データのビット数分だけ、各ビットの位に対応させることにより複数のビットプレーンに分配し、前記複数のビットプレーンを階層的に順次出力する階層的出力手段を有することを特徴とする画像処理装置。
【請求項２】
前記可変長符号化により得られる可変長符号化データはＧｏｌｏｍｂ符号を含むことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記複数の係数は画像を表す画像データを周波数成分に変換することにより得られた変換係数であることを特徴とする請求項１に記載の画像処理装置。
【請求項４】
前記周波数成分への変換には、ウェーブレット変換を用いることを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記周波数成分への変換には、ＤＣＴ変換を用いることを特徴とする請求項３に記載の画像処理装置。
【請求項６】
前記階層的出力手段は、階層的に出力するべきビットプレーン毎に更にランレングス符号化を施すことを特徴とする請求項１に記載の画像処理装置。
【請求項７】
前記階層的出力手段は、階層的に出力するべきビットプレーン毎に更に算術符号化を施すことを特徴とする請求項１に記載の画像処理装置。
【請求項８】
画像を表す複数の係数を発生する発生ステップと、
該発生ステップで発生した複数の係数を、予め予測された該係数の頻度分布に基づいて各係数毎に可変長符号化する可変長符号化ステップと、
該可変長符号化ステップの可変長符号化により得られた各係数に対応する可変長符号化データの各ビットを、各可変長符号化データの最上位ビットを基準として、各可変長符号化データのビット数分だけ、各ビットの位に対応させることにより複数のビットプレーンに分配し、前記複数のビットプレーンを階層的に順次出力する階層的出力ステップを有することを特徴とする画像処理方法。
【請求項９】
画像を表す複数の係数を発生する発生ステップと、
該発生ステップで発生した複数の係数を、予め予測された該係数の頻度分布に基づいて各係数毎に可変長符号化する可変長符号化ステップと、
該可変長符号化ステップの可変長符号化により各係数に対応する可変長符号化データの各ビットを、各可変長符号化データの最上位ビットを基準として、各可変長符号化データのビット数分だけ、各ビットの位に対応させることにより複数のビットプレーンに分配し、前記複数のビットプレーンを階層的に順次出力する階層的出力ステップを実行させるための画像処理プログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理装置及び方法及びこの方法を記憶した記憶媒体に関するものである。
【０００２】
【従来の技術】
画像、特に多値画像は非常に多くの情報を含んでおり、その画像を蓄積・伝送する際にはデ−タ量が膨大になってしまうという問題がある。このため画像の蓄積・伝送に際しては、画像の持つ冗長性を除く、或いは画質の劣化が視覚的に認識し難い程度で画像の内容を変更することによってデ−タ量を削減する高能率符号化が用いられる。
【０００３】
しかしながら高能率符号化によりある程度デ−タ量を削減できたとしても、その符号化データを伝送或いは読み出すには時間がかかる場合がある。このような場合、伝送された符号化データを受信する側においてデータ受信の初期段階で画像の概略を認識でき、更に後続の符号化データを受信することにより、この画像を徐々に高画質なものとして認識できる階層的符号化が用いられることが好ましい。
【０００４】
従来、一般的な階層的符号化として、各画素が多値で表される画像データを複数のビットプレ−ンに変換し、これらのビットプレーンを上位のビットプレーンから下位のビットプレーンの順に伝送するといった方法が行われる。
【０００５】
例えば、静止画像の国際標準符号化方式としてＩＳＯとＩＴＵ−Ｔにより勧告されたＪＰＥＧでは、符号化対象となる画像の内容や符号化データの使用目的に応じて数種の符号化方式が規定されており、拡張ＤＣＴプロセスにおいて階層的符号化を実現するためのＳＳ（Spectrum Selection）とＳＡ（Successive Approximation）と呼ばれる方法が規定されている。
【０００６】
ＪＰＥＧについての詳細は、勧告書ＩＴＵ−Ｔ Recommendation T.８１| ＩＳＯ／ＩＥＣ １０９１８−１等に記載されているのでここでは省略するが、Successive Approximationでは画像のブロック毎に離散コサイン変換（ＤＣＴ）を施し、得られた周波数成分の全てをｎビットの係数に量子化した後、得られた複数の量子化係数をｎ階層（ｎ〜１）のビットプレ−ンに変換し、上位（階層ｎ）のビットプレーンから下位（階層１）のビットプレーンの順に伝送するといった方法が行われる。
【０００７】
【発明が解決しようとする課題】
しかしながら従来、多値の画像データを所定階層数のビットプレ−ンに変換し、ビットプレーン毎に階層的に出力する様なビットプレ−ン符号化方法では、未だビットプレ−ンに冗長性が含まれているという問題があった。
【０００８】
また、従来の階層的符号化方式では、受信側が上位のビットプレ−ンのみ受信した場合に、符号化された多値画像の概略が早期に分かりにくい場合があるという問題があった。
【０００９】
本発明は、上述の問題点に鑑みてなされたものであり、一部の符号化データから早期に画像の概略を効率良く認識できる様にすると共に、圧縮効率の良い階層符号化の技術を提供することを目的とする。
【００１０】
【課題を解決するための手段】
上述の課題を解決するために本発明の画像処理装置によれば、画像を表す複数の係数（本実施の形態では画素値或いは量子化値に相当）を発生する発生手段（同じく、画像入力部１０１、係数量子化部６０４、１３０４、１６０４に相当）と、該発生手段により発生した複数の係数を、予め予測された該係数の頻度分布に基づいて各係数毎に可変長符号化する可変長符号化手段（同じく、可変長符号化部１０２、Ｇｏｌｏｍｂ符号化部６０５、１３０５、１６０５に相当）と、該可変長符号化手段の可変長符号化により得られた各係数に対応する可変長符号化データの各ビット（同じく、例えば図３の３ビット〜数ビットの符号）を、各可変長符号化データの最上位ビットを基準として、各可変長符号化データのビット数分だけ、各ビットの位に対応させることにより複数のビットプレーンに分配し（同じく例えば図４の分配に相当）、前記複数のビットプレーンを階層的に順次出力する階層的出力手段（同じく例えば、図５の階層的出力に相当）を有することを特徴とする。
【００１１】
【発明の実施の形態】
（第１の実施の形態）
以下、本発明を代表する実施形態について図面を用いて説明する。
【００１２】
図１は本発明の第１の実施の形態を実行する為の画像処理装置を示したものである。
【００１３】
同図において１０１は画像入力部、１０２は可変長符号化部、１０３はビットプレ−ン順走査部、１０４はバッファ、１０５は符号表メモリ、１０６は符号出力部である。
【００１４】
本実施の形態においては各画素を４ビットで表すモノクロ画像デ−タを符号化するものとして説明する。しかしながら本発明はこれに限らず、各画素８ビットで表すモノクロ画像、或いは各画素における各色成分（ＲＧＢ／Ｌａｂ／ＹＣｒＣｂ）を８ビットで表現するカラ−の多値画像を符号化する場合に適用することも可能である。また、画像を構成する各画素の状態等を表す多値情報を符号化する場合、例えば各画素の色を表す多値のインデックス値を符号化する場合にも適用できる。これらに応用する場合には、各種類の多値情報を後述するモノクロ画像データとしてそれぞれ符号化すれば良い。
【００１５】
以下、本実施の形態における各部の動作を詳細に説明する。
【００１６】
まず、画像入力部１０１から符号化対象となる画像を表す画像データ（画素データ）が連続的にラスタ−スキャン順で入力される。この画像入力部１０１は、例えばスキャナ、デジタルカメラ等の撮像装置、或いはＣＣＤなどの撮像デバイス、或いはネットワ−ク回線のインタ−フェ−ス等が用いられる。また、画像入力部１０１はＲＡＭ、ＲＯＭ、ハードディスク、ＣＤ−ＲＯＭ等の記録媒体であっても良い。
【００１７】
図２は画像入力部１０１から発生する画素データの頻度分布を示したものである。
【００１８】
本実施の形態において、符号化対象となる複数の画素デ−タは図２に示す様に、小さい値の画素データが発生する頻度が高く、大きい値の画素データが発生する頻度は低いものとして説明する。
【００１９】
この様な頻度分布の偏りは画像入力部１０１の特性、また符号化対象となる画像の特性によって発生し得るものである。特に画像入力部１０１がＣＣＤである場合にはガンマ補正をかけなければ頻度分布の偏りが発生しやすい。なお本実施の形態では図示しないが、画像入力部から可変長符号化部に入力される間に意図的に前処理等を行うことによって、図２の様な発生頻度の偏りを生じさせる場合も本発明の範疇に含まれる。
【００２０】
可変長符号化部１０２は画像入力部１０１から入力された画素データを、符号表メモリ１０５に格納される符号表を参照しながら可変長符号化する。
【００２１】
図３はこの符号表メモリ１０５に格納されている符号表の一例を示すものであり、可変長符号化の前に予め符号表メモリ１０２に格納しておくものとする。なお、符号表メモリ１０２に格納されるこの符号表は、図２に示される様なあるサンプル画像を表す画素データの発生頻度分布を一般的な分布であると考え、この分布に基づいて生成されたものである。図２に示される符号の長さは、基本的に発生頻度の高い画素データ（画素値）に短い符号を割り当てる様にしてある。なお、本発明は１つの符号表を使用する場合に限らず、複数の符号表を選択的に使用する場合も含むものである。この場合には符号化対象となる画像の内容（各画素データの発生頻度）を実際に識別し、この識別結果に応じて複数の符号表から最適な１つを選択するものとする。
【００２２】
本実施の形態における図３の符号表では、後段においてビットプレ−ン毎に伝送することを考慮し、例えば各画素データのＭＳＢ（最上位ビット）が０か１かにより、これら画素データが０〜２の範囲にあるのか３以上の範囲にあるのかを識別できる様に可変長符号を割り当てる様にしている。即ち、各可変長符号の上位ビットから順に認識した場合に、次の下位ビットに対応する復号画素値の候補値が連続する様に決められている。これはハフマン符号を構成するためのアルゴリズムにおける発生頻度の低い２つを繰り返して統合して符号木を作成する過程において、統合は隣接する２つに限定して符号木を構成することで実現することができる。
【００２３】
上述の可変長符号の割り当て方をすることにより、後述するビットプレーン毎の符号化データ出力が行われる場合には、階層的に各画素の濃度範囲に基づいた効率の良い濃度域の限定が行うことが可能となる。即ち符号化データの受信側が各画素において最初の１ビット（ＭＳＢ）だけを後述するビットプレーンとして受信した場合であっても、各画素において最も発生頻度が大きい濃度に対して高い値であるかのか或いは低い値であるのかを早期に認識することができる。これにより画像の概略が非常によく分かる。同様にこれに続く上位ビットのプレーンも受信すれば、各画素に対して更に効率の良い濃度限定を行うことができる。これに対して従来の様に多値の画素値をビットプレーン毎に階層出力する場合には最初の１ビット（ＭＳＢ）だけを受信した場合には各画素の濃度が中間値より高い値であるか低い値であるか程度しか分からない。よって、画像全体の濃度が低濃度域或いは高濃度域に集まっている様な画像を符号化した場合には、受信側で画像の概略を知ることが困難になる。
【００２４】
可変長符号化部１０２では、入力される画素データが「０」ならば出力符号は「０００」、画素値が「１」ならば「００１」、画素値が「２」ならば「０１」といった具合に入力される画素データを順次符号化してゆく。
【００２５】
ビットプレ−ン順走査部１０３は可変長符号化部１０２から出力されてくる可変長の符号化データをバッファ１０４に一旦格納する。そして、可変長の符号化データの最上位ビット（ＭＳＢ）を第１のビットプレ−ンにおける２値データとして格納し、その次の上位ビットを第２のビットプレ−ンにおける２値データとして格納する。なお、各ビットプレーンにおける２値データとして格納される位置は、符号化対象である元の画像の各画素の位置に対応する様にアドレス制御される。以下同様に、上記可変長の符号化データを構成する各ビットは、上位ビットから順に第３のビットプレーン、第４のビットプレーン・・・の順に２値データとしてバッファ１０４に格納される。
【００２６】
なお後述するが、上記符号化データは可変長符号化であるので、この符号化データを構成するビットが何番目のビットプレーンまで格納されるかは、各画素毎に異なる。
【００２７】
例えば、可変長符号化部１０２から出力されてくる可変長の符号化データが「１０１」である場合、「１」を第１のビットプレ−ンに、「０」を第２のビットプレ−ンに、「１」を第３のビットプレ−ンに格納し、第４以降のビットプレーンにはデータが格納されない。一方、可変長符号化部１０２から出力されてくる可変長の符号化データが「１１０１０」である場合には、第５のビットプレーンまでデータが格納されることになる。
【００２８】
図４は画素データの系列「０,１,３,・・・,１,２,３,・・・,２,３,・・・」が可変長符号化部１０２により符号化されたデータを、ビットプレ−ンとして格納した様子を表すものである。
【００２９】
図中斜線の部分は、その上位プレ−ンにて可変長符号が終端しているのでビット情報が必要なく、格納されていないこと表すものである。
【００３０】
ビットプレ−ン順走査部１０３は、可変長符号化部１０２から１画面分の符号化データを受け取り、バッファ１０４に格納する。続いてビットプレーン順走査部１０３は、バッファ１０４から第１のビットプレ−ン（ＭＳＢ）、第２ビットプレ−ン、・・・という様に上位のビットプレ−ンから下位のビットプレ−ンの順に、各ビットプレ−ンのビット情報「１／０」をラスタ−スキャン順に読み出す。
【００３１】
図５にバッファ１０４から返送される符号化データ（ビット情報）の順番を示す。なお、図４に示す斜線部についてはスキップして読み出すこととする。即ち図４の第３のビットプレーンの第２ライン目では左から「１」の次に斜線領域のブランクをスキップして「０」が読み出されることになり、第３ライン目では左から１画素分の斜線領域をスキップして「０」が最初に読み出されることになる。なおこの読み出しにより得られた図５に示すデータを復号化する受信側が受信した場合、受信側ではこれらのデータが上位のビットプレーンから順に読み出し、出力されてきたことが分かっているので、図４に示されるブランクがどの位置に存在するかを予測することが可能である。
【００３２】
上述した本実施の形態のデータ形態によれば、各画素が固定ビットとして表現された単純にビットプレーン毎に出力する場合と比較して符号量を大きく減少させることができる。
【００３３】
図５に示されたビットプレーン単位の符号化データは、符号出力部１０６においてメモリ格納或いは外部機器へ送信される。符号出力部１０６には、例えば、ハ−ドディスク、ＲＡＭ、ＲＯＭ、ＤＶＤ等の記録媒体を用いても良いし、公衆回線、無線回線、ＬＡＮ等の回線にデータ送信するインタ−フェ−スを用いても良い。
【００３４】
以上の符号化処理により、上位のビットプレ−ンから階層的にデータ送信する場合にも、受信側において効率良く画像の概要を把握することができる。また、通常のビットプレーン毎符号化と比べて全体の符号量を減少させることができる。
【００３５】
なお、上記実施の形態において生成された符号化データには、画像のサイズ、符号表メモリ１０２に格納している符号表に関する表指定情報（複数の符号表の内何れの符号表を使用したか示すインデックス、或いは符号表に示される画素データと可変長符号の各対応を示す具体的なデータ）等が付属データとして適宜付加される。例えば、画像をライン単位、ブロック単位、バンド単位で行う場合には、上記画像のサイズを示す情報が必要である。また、符号表メモリ１０５に複数の符号表が格納されており、符号化対象となる画像の内容に応じて選択的に使用される場合には上記表指定情報が必要である。
【００３６】
（第２の実施の形態）
次に、本発明を実施する第２の実施の形態について図面を用いて説明する。
【００３７】
本実施の形態では８ビットのモノクロ画像デ−タを符号化するものとして説明する。しかしながら本発明はこれに限らず、各画素４ビットで表すモノクロ画像、或いは各画素における各色成分（ＲＧＢ／Ｌａｂ／ＹＣｒＣｂ）を８ビットで表現するカラ−の多値画像を符号化する場合に適用することも可能である。また、画像を構成する各画素の状態等を表す多値情報を符号化する場合、例えば各画素の色を表す多値のインデックス値を符号化する場合にも適用できる。これらに応用する場合には、各種類の多値情報を後述するモノクロ画像データとしてそれぞれ符号化すれば良い。
【００３８】
図６は本発明の第２の実施の形態を実行する為の画像処理装置を示したものである。同図において６０１は画像入力部、６０２は離散ウェ−ブレット変換部、６０３はバッファ、６０４は係数量子化部、６０５はGolomb符号化部、６０６はビットプレ−ン順走査部、６０７はバッファ、６０８は符号出力部である。
【００３９】
まず、画像入力部６０１から符号化対象となる画像を構成する画素デ−タがラスタ−スキャン順に入力される。この画像入力部６０１は、例えばスキャナ、デジタルカメラ等の撮像装置、或いはＣＣＤなどの撮像デバイス、或いはネットワ−ク回線のインタ−フェ−ス等が用いられる。また、画像入力部６０１はＲＡＭ、ＲＯＭ、ハードディスク、ＣＤ−ＲＯＭ等の記録媒体であっても良い。
【００４０】
離散ウェ−ブレット変換部６０２は画像入力部６０１から入力される１画面分の各画素データを、一旦バッファ６０３に格納する。次に、バッファ６０３に格納した１画面分の各画素データに対して公知の離散ウェ−ブレット変換を施し、複数の周波数帯域に分解する。本実施の形態では、画像デ−タ列ｘ（ｎ）に対する離散ウェ−ブレット変換は次式によって行うものとする。
【００４１】
ｒ（ｎ）＝ｆｌｏｏｒ｛（ｘ（２ｎ）＋ｘ（２ｎ＋１））／２｝
ｄ（ｎ）＝ｘ（２ｎ＋２）−ｘ（２ｎ＋３）
＋ｆｌｏｏｒ｛（−ｒ（ｎ）＋ｒ（ｎ＋２）＋２）／４｝
ｒ（ｎ）、ｄ（ｎ）は変換係数であり、ｒ（ｎ）は低周波成分、ｄ（ｎ）は高周波成分である。また、上式においてｆｌｏｏｒ｛Ｘ｝はＸを超えない最大の整数値を表す。本変換式は一次元のデ−タに対するものであるが、この変換を水平方向、垂直方向の順に適用すること二次元の変換を行うことが可能であり、図７（ａ）の様なＬＬ，ＨＬ，ＬＨ，ＨＨの４つの周波数帯域（サブブロック）に分割することができる。
【００４２】
生成したＬＬ成分について同様の手順にて離散ウェ−ブレット変換を施すことにより図７（ｂ）の様に７個の周波数帯域（サブブロック）に分解する。本実施の形態においては、更にもう一度繰り返して離散ウェ−ブレット変換を施すことにより図７（c）に示す様にＬＬ，ＨＬ３,ＬＨ３,ＨＨ３,ＨＬ２,ＬＨ２,ＨＨ２,ＨＬ１,ＬＨ１,ＨＨ１の１０個の周波数帯域（サブブロック）に分割する。
【００４３】
変換係数はＬＬ，ＨＬ３,ＬＨ３,ＨＨ３,ＨＬ２,ＬＨ２,ＨＨ２,ＨＬ１,ＬＨ１,ＨＨ１のサブブロックの順に、かつ各サブブロック毎にラスタ−スキャン順に係数量子化部６０４へと出力される。
【００４４】
係数量子化部６０４は離散ウェ−ブレット変換部６０２から出力されるウェ−ブレット変換係数の各々を各周波数成分毎に定めた量子化ステップで量子化し、量子化後の値をGolomb符号化部６０５へと出力する。係数値をＸ、この係数の属する周波数成分に対する量子化ステップの値をｑとするとき、量子化後の係数値Ｑ（Ｘ）は次式によって求めるものとする。
【００４５】
Ｑ（Ｘ）=ｆｌｏｏｒ｛（Ｘ／ｑ）＋０.５｝
但し、上式においてｆｌｏｏｒ｛Ｘ｝はＸを超えない最大の整数値を表す。本実施の形態における各周波数成分と量子化ステップとの対応を図８に示す。図に示す様に低周波成分（ＬＬ等）よりも高周波成分（ＨＬ１、ＬＨ１、ＨＨ１）等の方が量子化ステップを大きくしている。
【００４６】
Golomb符号化部６０５は係数量子化部６０４で量子化された量子化値を符号化し、符号を出力する。この量子化値に対する符号化データは正負（＋／−）を表す符号ビットと量子化値の絶対値に対するGolomb符号により構成される。
【００４７】
なお、Golomb符号は、最も発生頻度が高い値（Golomb符号化の場合には０）の発生確率から発生頻度が低い値へ向かって発生頻度の減少する度合いが異なるｋ個の発生頻度分布に対応した可変長符号を、符号化パラメータkの設定により簡易に生成することができる。具体的にはGolomb符号化に用いるパラメータkを小さく設定すれば、符号化される画素データの発生頻度の最も高い値から低い値への発生頻度（発生確率）の減少の度合いが大きい画素データ群を効率良く符号化することができ、パラメータｋを大きくすれば、符号化される画素データの発生頻度の最も高い値から低い値への発生頻度（発生確率）の減少の度合いが小さい画素データ群を効率良く符号化することができる。例えば０の発生頻度が最も高い画像を符号化する際、ｋ＝０に設定した場合には、０の発生確率が１／２で、1の発生確率が１／４といった具合に、発生確率が大きく減少する発生頻度分布を有する画素データ群を効率良く符号化することができる。
【００４８】
特に本実施の形態では自然画像を符号化する場合に符号化効率が良い。即ち、自然画像を表す画素データをウェーブレット変換して得られる変換係数の確率分布は、ＬＬ成分以外のＨＬ３・・・ＨＨ１の変換係数の各サブブロックにおいては、０を中心（発生頻度の最も高い値）として正（＋１〜・・・）及び負（−１〜・・・）の両方向にだんだん発生頻度が減少してゆく発生頻度分布となる傾向にある。Golomb符号化は、変換係数（即ち量子化値）の絶対値の小さい順に０、１、−１、２、−２・・・の様に並べて、この順番で一番短い符号長の可変長符号から順に割り当てるような可変長符号化を行うことになる。
【００４９】
従って、ウェーブレット変換を実行する場合には得られた変換係数を単なる可変長符号化ではなくGolomb符号化を実行することにより特に圧縮効率を良好にすることが可能となる。
【００５０】
本実施の形態で符号化される一般的な自然画像は、低周波成分よりも高周波成分の変換係数（例えばＨＨ３よりもＨＨ１）ほど発生頻度の最も高い値から低い値への発生頻度（発生確率）の減少の度合いが大きくなる傾向がある。また、本実施の形態では高周波成分の変換係数を低周波成分の変換係数より荒く量子化するので、高周波成分に相当する量子化値の発生頻度分布は低周波成分に相当する量子化値の発生頻度分布と比べて、発生頻度の最も高い値（本実施の形態の場合０）から低い値への発生頻度（発生確率）の減少の度合いが大きくなると予測することにより、上記符号化パラメータkを設定している。なお、本実施の形態における周波数成分と符号化パラメータｋの対応関係については図９に示す通りである。
【００５１】
以下にGolomb符号化部６０５が行うGolomb符号化の基本的方法は公知であるので、符号化の基本的な動作及び本発明の特徴的な部分についてのみ簡単に説明する。
【００５２】
Golomb符号化部６０５は、まず順次入力される量子化値の正／負を調べ、符号（＋／−）ビットを出力する。具体的には量子化値が０または正である場合には「１」を、負である場合には「０」を符号ビットとする。
【００５３】
次に、量子化値の絶対値をGolomb符号化する。符号化対象となる量子化値の絶対値がＶ、係数の属する周波数成分に対する符号化パラメ−タがｋである場合のGolomb符号化は次の手順にて行われる。まず、Ｖをｋビット右シフトして整数値ｍを求める。Ｖに対するGolomb符号ｍ個の「０」に続く「１」とＶの下位ｋビットの組み合わせにて構成する。図１０にｋ＝０,１,２におけるGolomb符号の例を示す。
【００５４】
なお、このGolomb符号化は符号表（図３の様な入力値と可変長符号の対応を示すテーブル）を保持せずに符号化及び復号化を行うことができ、更には、第１の実施の形態の図３で説明した様に、各可変長符号の上位ビットから順次階層的に認識した場合に、次の下位ビットに対応する復号値の範囲を順次限定してゆける様に構成されているので、これら可変長符号化データをビットプレーン毎に階層出力した場合には、受信側において早期かつ効率良く復号画像の概略を認識できる。
【００５５】
以上の様にして、入力される量子化値に対する符号（＋／−）ビットとGolomb符号からなる符号化データを生成し、ビットプレ−ン順走査部６０６へと出力する。
【００５６】
ビットプレ−ン順走査部６０６は、上述した周波数成分（サブブロック）単位に処理を行う。まず、Golomb符号化部６０５で生成された符号化データを１つの周波数成分（ＬＬ〜ＨＨ１のサブブロックの何れか１つ）分バッファ６０７に格納する。Golomb符号化部６０５で発生した各画素に対応する符号（＋／−）ビットについては正負を示す符号プレ−ンに格納し、各画素に対応するGolomb符号の先頭ビット（ＭＳＢ）を第１のビットプレ−ンに格納し、同じく二番目のビットを第２のビットプレ−ンに格納する。同じく三番目以降のビットも第３以降のビットプレーンに順次格納する。この方法は第１の実施の形態と同様である。以上の様にして各画素に対応する符号化データが複数のビットプレ−ンとしてバッファ６０７に格納される。
【００５７】
例えば、Golomb符号化部６０５から出力される符号が「０１１０」である場合、「０」を正負を示す符号プレ−ンに、「１」を第１のビットプレ−ンに、「１」を第２のビットプレ−ンに、「０」を第３のビットプレ−ンに格納する。なお、上記データ「０１１０」であれば、第４のビットプレーンにはビット情報は格納されない。
【００５８】
図１１はＨＬ３成分について量子化された係数値（量子化値）のデータ系列「３,４,−２,−５,−４,０,１,・・・」を、Golomb符号化部６０５により符号化して得られる符号化データをビットプレ−ンとして格納する様子を示すものである。同図において斜線の部分はその上位プレ−ンにて符号化データが終端しているのでビット情報が必要無い部分、即ちビット情報を記憶しない部分を示す。ビットプレ−ン順走査部６０６は、Golomb符号化部６０５から１つの周波数成分（ＬＬ〜ＨＨ１の何れか１つのサブブロック）を表す全ての符号化データを受け取り、上述の様にバッファ６０７に格納し終えると、正負を示す符号ビットプレ−ン、第１のビットプレ−ン、第２のビットプレ−ンという順、即ち符号ビットプレ−ンに続けて上位のビットプレ−ンから下位のビットプレ−ンの順に、各ビットプレ−ンの情報をラスタ−スキャン順に読み出して、符号出力部６０８に出力する。図１２に、バッファ６０７に格納されたビット情報をビットプレ−ン順に出力した際のデータ形態を示す。
【００５９】
上記ビットプレーン毎の階層出力が、低周波成分のサブブロックＬＬ、ＨＬ３、ＬＨ３,ＨＨ３、ＨＬ２、ＬＨ２、ＨＨ２、ＨＬ１、ＬＨ１、ＨＨ１の順で行われる。
【００６０】
符号出力部６０８では上記出力により得られた複数のビットプレーンデータを順次階層的に送信する。この符号出力部６０８には、公衆回線、無線回線、ＬＡＮ等のインタ−フェ−スを用いることができる。また、符号出力部６０８は上記階層的データを格納しておくハ−ドディスク、ＲＡＭ、ＲＯＭ、ＤＶＤ等の記録媒体であっても良い。
【００６１】
上述した符号化により低周波成分から高周波成分の順で階層的に画像が送信され、受信側では階層的に画像の概略を把握することが可能となる。更に、各周波成分においてビットプレーン毎の階層的な送信が行われるので、受信側では各周波数成分においても更に階層的に画像の概略を把握することが可能となる。また第１の実施の形態と同じく、各画素（変換係数）を可変長で表現する様にしているので、通常のビットプレーン毎の符号化と比べて全体の符号量を減少させることができる。
【００６２】
なお、上記実施の形態において生成された符号化データには、画像のサイズ、１画素当たりのビット数、各周波数成分に対する量子化ステップ、符号化パラメータｋ等の復号側に必要な付属情報が適宜付加される。例えば、画像をライン単位、ブロック単位、バンド単位で行う場合には、上記画像のサイズを示す情報が必要である。
【００６３】
（第３の実施の形態）
上述の第２の実施の形態では各ビットプレ−ンのビット情報をそのまま出力した。この場合、ウェ−ブレット変換し、量子化された各量子化値について、正負を示す符号（＋／−）ビットが１ビット、更に量子化値の絶対値をGolomb符号で表現する為に少なくとも１ビット必要であり、計２ビットは必要となる。これは即ち、第２の実施の形態で示した方法では、１つの変換係数当たり２ビット以下の圧縮は実現できないことを示している。
【００６４】
本実施の形態では、ビット情報をそのまま符号出力部へ出力するのではなく、第２の実施の形態で最終的に出力されたビット情報を更に高能率符号化することにより、全体の符号量を削減するものである。以下、具体例について説明する。
【００６５】
図１３は、第３の実施の形態のブロック図を示すものである。同図において１３０１は画像入力部、１３０２は離散ウェ−ブレット変換部、１３０３はバッファ、１３０４は係数量子化部、１３０５はGolomb符号化部、１３０６はビットプレ−ン順走査部、１３０７はバッファ、１３０８はランレングス符号化部、１３０９は符号出力部である。
【００６６】
本実施の形態では８ビットのモノクロ画像デ−タを符号化するものとして説明する。しかしながら本発明はこれに限らず、各画素４ビットで表すモノクロ画像、或いは各画素における各色成分（ＲＧＢ／Ｌａｂ／ＹＣｒＣｂ）を８ビットで表現するカラ−の多値画像を符号化する場合に適用することも可能である。また、画像を構成する各画素の状態等を表す多値情報を符号化する場合、例えば各画素の色を表す多値のインデックス値を符号化する場合にも適用できる。これらに応用する場合には、各種類の多値情報を後述するモノクロ画像データとしてそれぞれ符号化すれば良い。
【００６７】
画像入力部１３０１、離散ウェ−ブレット変換部１３０２、バッファ１３０３、係数量子化部１３０４、Golomb符号化部１３０５、ビットプレ−ン順走査部１３０６、バッファ１３０７の動作は第２の実施の形態と同様である。よってこれらの部分の説明は省略する。
【００６８】
ビットプレ−ン順走査部１３０６は、第２の実施の形態のビットプレ−ン順走査部６０６と同様のデータ形態で、各ビットプレ−ンのビット情報を後段のランレングス符号化部１３０８に順次出力する。
【００６９】
ランレングス符号化部１３０８はビットプレ−ン順走査部１３０６から受け取った各ビットプレーンに相当するビット情報の内、正負（＋／−）を示す符号プレ−ンと第１のビット（ＭＳＢ）プレ−ンについては、ビット情報の「１」が連続する数を生成し、この連続数を図１５の対応表に従って可変長符号化する。図１４はビット情報の「１」が連続する数を生成する様子を示したものである。図１４において、最初はビット情報「１」が３つ連続するので最初の連続数が「３」となる。そして次のビット情報は「０」であることが分かるのでこの１つをスキップする。続くビット情報には「１」が２つ続くので２つ目の連続数は「２」となる。先と同様に次のビット情報は「０」になるのでスキップするが、その次のビット情報も「０」であるのでビット情報「１」が連続しなかったことになる。よって３つ目の連続数は「０」となる。そして２つ連続する「０」についてはスキップして良いことになるので、次に続くビット情報「１」が３つ連続することに着目し、４つ目の連続数として「３」が出力される。以上の連続数を図１５の対応表に基づいて符号化されることにより、結果的にランレングス符号化が行われることになる。
【００７０】
なお、上記ランレングス符号化は続いて第２のビットプレーン、第３のビットプレーンの順に順次行われる。またビットプレーン毎の階層符号化という性格上、各ビットプレーン毎にラン長のカウントにはリセットをかける必要がある。
【００７１】
符号出力部１３０９は、ランレングス符号化部１３０８から出力されたランレングス符号化データを受け取ると共に、ビットプレ−ン順走査部１３０６から別に出力される付属情報も受け取りこれらを合成したデータを最終的な符号化データとする。
【００７２】
符号出力部１３０９では、上記出力により得られた複数のビットプレーンデータ（更にランレングス符号化されたデータ）を順次階層的に送信する。この符号出力部１３０９には、公衆回線、無線回線、ＬＡＮ等のインタ−フェ−スを用いることができる。また、符号出力部１３０９は上記階層的データを格納しておくハ−ドディスク、ＲＡＭ、ＲＯＭ、ＤＶＤ等の記録媒体であっても良い。
【００７３】
上述した符号化により低周波成分から高周波成分の順で階層的に画像が送信され、受信側では階層的に画像の概略を把握することが可能となる。更に、各周波成分においてビットプレーン毎の階層的な送信が行われるので、受信側では各周波数成分においても更に階層的に画像の概略を把握することが可能となる。また上記ビットプレーン毎に更にランレングス符号化を施すことにより総符号量を更に減少させることが可能となる。また第１の実施の形態と同じく、各画素（変換係数）を可変長で表現する様にしているので、通常のビットプレーン毎の符号化と比べて全体の符号量を減少させることができる。
【００７４】
なお、上記実施の形態において生成された符号化データには、画像のサイズ、１画素当たりのビット数、各周波数成分に対する量子化ステップ、符号化パラメータｋ等の復号側に必要な付属情報が適宜付加される。例えば、画像をライン単位、ブロック単位、バンド単位で行う場合には、上記画像のサイズを示す情報が必要である。
【００７５】
（第４の実施の形態）
上述の第３の実施の形態では各ビットプレ−ンに相当するビット情報を高能率符号化する手法としてランレングス符号化を用いた。ランレングス符号化の代わりに他の高能率符号化手法を用いて更に全体の符号量の削減を図ることも可能である。以下、その変形例について説明する。
【００７６】
図１６は、本発明に係わる第４の実施の形態のブロック図を示すものである。同図において１６０１は画像入力部、１６０２は離散ウェ−ブレット変換部、１６０３はバッファ、１６０４は係数量子化部、１６０５はGolomb符号化部、１６０６はビットプレ−ン順走査部、１６０７はバッファ、１６０８は算術符号化部、１６０９は符号出力部である。
【００７７】
本実施の形態では８ビットのモノクロ画像デ−タを符号化するものとして説明する。しかしながら本発明はこれに限らず、各画素４ビットで表すモノクロ画像、或いは各画素における各色成分（ＲＧＢ／Ｌａｂ／ＹＣｒＣｂ）を８ビットで表現するカラ−の多値画像を符号化する場合に適用することも可能である。また、画像を構成する各画素の状態等を表す多値情報を符号化する場合、例えば各画素の色を表す多値のインデックス値を符号化する場合にも適用できる。これらに応用する場合には、各種類の多値情報を後述するモノクロ画像データとしてそれぞれ符号化すれば良い。
【００７８】
画像入力部１６０１、離散ウェ−ブレット変換部１６０２、バッファ１６０３、係数量子化部１６０４、Golomb符号化部１６０５、ビットプレ−ン順走査部１６０６、バッファ１６０７の動作は第２の実施の形態と同様に動作する。よってこれらの部分の説明は省略する。
【００７９】
ビットプレ−ン順走査部１６０６は、第２の実施の形態のビットプレ−ン順走査部６０６と同様のデータ形態で、各ビットプレ−ンのビット情報を後段の算術符号化部１６０８へ出力する。
【００８０】
算術符号化部１６０８はビットプレ−ン順走査部１６０６の出力するビット情報の列を着目ビットの直前６ビットにて分別される６４個の状態に分離してＱＭ−Ｃｏｄｅｒにて符号化する。ＱＭ−Ｃｏｄｅｒの動作については勧告書ＩＴＵ−Ｔ Recommendation Ｔ.８１| ＩＳＯ／ＩＥＣ １０９１８−１等に説明されているのでここでは省略する。
【００８１】
なお、上記算術符号化は続いて第１のビットプレーン、第２のビットプレーンの順に順次行われる。またビットプレーン毎の階層符号化という性格上、各ビットプレーン毎にリセットをかける必要がある。
【００８２】
符号出力部１６０９は算術符号化部１６０８の生成した複数のビットプレーンデータ（更に算術符号化されたデータ）を順次階層的に送信する。この符号出力部１３０９には、公衆回線、無線回線、ＬＡＮ等のインタ−フェ−スを用いることができる。また、符号出力部１３０９は上記階層的データを格納しておくハ−ドディスク、ＲＡＭ、ＲＯＭ、ＤＶＤ等の記録媒体であっても良い。
【００８３】
上述した符号化により低周波成分から高周波成分の順で階層的に画像が送信され、受信側では階層的に画像の概略を把握することが可能となる。更に、各周波成分においてビットプレーン毎の階層的な送信が行われるので、受信側では各周波数成分においても更に階層的に画像の概略を把握することが可能となる。また上記ビットプレーン毎に更に算術符号化を施すことにより総符号量を更に減少させることが可能となる。また第１の実施の形態と同じく、各画素（変換係数）を可変長で表現する様にしているので、通常のビットプレーン毎の符号化と比べて全体の符号量を減少させることができる。
【００８４】
なお、上記実施の形態において生成された符号化データには、画像のサイズ、１画素当たりのビット数、各周波数成分に対する量子化ステップ、符号化パラメータｋ等の復号側に必要な付属情報が適宜付加される。例えば、画像をライン単位、ブロック単位、バンド単位で行う場合には、上記画像のサイズを示す情報が必要である。
【００８５】
（その他の実施の形態）
本発明は上述の実施の形態に限定されるものではない。
【００８６】
例えば第２〜第４の実施の形態では離散ウェ−ブレット変換を用いた符号化の例を示したが、離散ウェ−ブレット変換についても本実施の形態で使用したものに限定されるものではなく、フィルタの種類や周波数帯域分割方法を変えても構わない。更に離散ウェ−ブレット変換以外にも、ＤＣＴ変換（離散コサイン変換）等、その他の変換手法に基く符号化方式に適用しても構わない。
【００８７】
また周波数成分の量子化の方法や可変長符号化の方法についても上述の実施の形態に限定されるものではない。例えば、１つの周波数成分（サブブロック）を更に分割したブロック毎に局所的性質を判別することにより数種類のクラスに分類し、これらのクラス毎に量子化ステップや符号化パラメ−タを更に細かく設定しても良い。
【００８８】
また、Golomb符号化の構成についても上記実施の形態に限定されるものではない。例えば上記実施の形態では符号化パラメータkである場合の非負の整数値Ｖに対するGolomb符号を、ｍ個（ｍはＶをｋビット右シフトして求める）の「０」に続く「１」（可変長部と呼ぶ）とＶの下位ｋビット（固定長部と呼ぶ）の組み合わせにより構成するものとしたが、「０」と「１」の使用方法を逆、即ち「０」と「１」を「１」と「０」としてGolomb符号を生成しても構わない。また、最終的なGolomb符号として可変長部の後ろに固定長部を合成しても固定長部の後ろに可変長部を合成しても構わない。
【００８９】
また、上記実施の形態では正負（＋／−）を示す符号に対応するビットプレーンと各変換係数（量子化値）に対応するビットプレーンを別々に出力していたが本発明はこれに限定されるものではない。例えば、正負を示す符号についてはビットプレーンとして出力しないでも良く、例えば階層的にビットプレーンを出力してゆく途中に正負を示す符号ビットを挟み込む様に出力しても良い。例えば、第１１図に示す係数値（量子化値）「３」，「４」，「−２」，「−５」，「−４」，「０」，「１」を含むデータをビットプレーン毎に階層的に出力する場合、「０」以外の量子化値に対しては正負符号が必要になるが、この変形例においてはまず初めに第１プレーンを出力する。その際、１ビット目（ＭＳＢ）が「１」で示される元の量子化値（図１１中「３」，「−２」，「０」，「１」に相当）は「０」である可能性があるので正負符号は挿入しない。一方、１ビット目（ＭＳＢ）が「０」で示される元の量子化値（図１１中「４」，「−５」，「−４」）は「０」である可能性が無いので量子化値に相当する正負符号「１」，「０」，「０」を第１のビットプレーン全ての後ろ（第２のビットプレーンの前）に挿入して出力する。上記正負符号の挿入を以下同様に行う。なお、各量子化値に対して挿入出力される正負符号は一度で十分であるので、第２ビットプレーンと第３ビットプレーンの間に正負符号を挿入するか否かの判断は、図１１中「３」，「−２」，「０」，「１」に対しては行われるが、図１１中「４」，「−５」，「−４」に対しては行われない。なお、上記挿入出力の仕方は第１と第２ビットプレーンの間に挿入するのではなく、第１のビットプレーン内の各値「４」，「−５」，「−４」を示す１ビット目（ＭＳＢ）「１」，「１」，「１」の各々後ろに上記各量子化値に相当する正負符号「１」，「０」，「０」を付加し、「１，１」，「１，０」，「１，０」として出力する様にしても良い。
【００９０】
また、正負符号を有する上記各量子化値を正負符号を有さない整数の中間値に一旦変換した後、この中間値を可変長符号化（Golomb符号化）しても良い。この場合、０．−１．１．−２．２・・・の各量子化値を０，１，２，３，４・・・の中間値に変換する。
【００９１】
また、上記実施の形態ではウェーブレット変換された変換係数（量子化値）は０の値が最も高い頻度で発生するものと予め予測して符号化パラメータkを設定し、Golomb符号化を実行していたが、上記変換係数の発生頻度に基づいて効率良くGolomb符号化できる設定方法であれば本発明はこれに限らない。例えば、可変長符号化される変換係数の発生頻度を実際に解析し、その都度最適な符号化パラメータkを設定する様にすればより効果的な符号化が行える。
【００９２】
また、上述の実施の形態においては１つのサブブロックを構成する複数のビットプレーンの全てを階層的に出力した後に次の１つのサブブロックを構成する複数のビットプレーンの全てを階層的に出力する様にして階層的な符号化を行ったが、例えば、最初のサブブロックを構成する第１のビットプレーンを出力した後に次のサブブロックを構成する第１のビットプレーンを出力し、全てのサブブロックの第１のビットプレーンを出力し終わった後に、最初のサブブロックを構成する第２のビットプレーンを出力する様な順序にしても階層的な符号化が行える。
【００９３】
また第３、第４の実施の形態では、各ビットプレ−ンに相当するビット情報を更に高能率符号化する為にランレングス符号化と算術符号化を適用する例を示したが、これに限定されるものではなく、他の高能率符号化法を用いることも可能である。
【００９４】
なお、本発明は複数の機器（例えばホストコンピュ−タ、インタ−フェ−ス機器、リ−ダ、プリンタ等）から構成されるシステムの一部として適用しても、１つの機器（例えば複写機、ファクシミリ装置、デジタルカメラ等）からなる装置の１部に適用してもよい。
【００９５】
また、本発明は上記実施の形態を実現するための装置及び方法のみに限定されるものではなく、上記システム又は装置内のコンピュ−タ（ＣＰＵあるいはＭＰＵ）に、上記実施の形態を実現するためのソフトウエアのプログラムコ−ドを供給し、このプログラムコ−ドに従って上記システムあるいは装置のコンピュ−タが上記各種デバイスを動作させることにより上記実施の形態を実現する場合も本発明の範疇に含まれる。
【００９６】
またこの場合、前記ソフトウエアのプログラムコ−ド自体が上記実施の形態の機能を実現することになり、そのプログラムコ−ド自体、及びそのプログラムコ−ドをコンピュ−タに供給するための手段、具体的には上記プログラムコ−ドを格納した記憶媒体は本発明の範疇に含まれる。
【００９７】
この様なプログラムコ−ドを格納する記憶媒体としては、例えばフロッピ−ディスク、ハ−ドディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テ−プ、不揮発性のメモリカ−ド、ＲＯＭ等を用いることができる。
【００９８】
また、上記コンピュ−タが、供給されたプログラムコ−ドのみに従って各種デバイスを制御することにより、上記実施の形態の機能が実現される場合だけではなく、上記プログラムコ−ドがコンピュ−タ上で稼動しているＯＳ（オペレ−ティングシステム）、あるいは他のアプリケ−ションソフト等と共同して上記実施の形態が実現される場合にもかかるプログラムコ−ドは本発明の範疇に含まれる。
【００９９】
更に、この供給されたプログラムコ−ドが、コンピュ−タの機能拡張ボ−ドやコンピュ−タに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムコ−ドの指示に基づいてその機能拡張ボ−ドや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって上記実施の形態が実現される場合も本発明の範疇に含まれる。
【０１００】
【発明の効果】
以上説明した様に本発明によれば、予め予測された該係数の頻度分布に基づいて可変長符号化された符号化データをビットプレーンに分配して階層的に出力するので、一部の符号化データから早期に画像の概略を効率良く認識することができる。更には、圧縮効率の良い階層符号化の技術を提供することができる。
【図面の簡単な説明】
【図１】第１の実施の形態のブロック図
【図２】第１の実施の形態で符号化対象とする画像の頻度分布を示す図
【図３】符号表メモリ１０５に格納される符号表の例を示す図
【図４】ビットプレ−ン分割の様子を例示する図
【図５】ビットプレ−ン順走査部１０３の出力する符号化データ列示す図
【図６】第２の実施の形態のブロック図
【図７】２次元ウェ−ブレット変換の様子の模式図
【図８】周波数成分と量子化ステップの対応を示す図
【図９】周波数成分と符号化パラメ−タkの対応を示す図
【図１０】  Golomb符号の例を示す図
【図１１】ビットプレ−ン分割の様子を示す図
【図１２】ビットプレ−ン順走査部６０６の出力する符号列の例を示す図
【図１３】第３の実施の形態のブロック図
【図１４】ランレングス符号化部１３０８でのビット列からラン長への変換例
【図１５】ランレングス符号化部１３０８の符号化の様子を示す図
【図１６】本発明に係わる第４の実施の形態のブロック図
【符号の説明】
１０１  画像入力部
１０２  可変長符号化部
１０３  ビットプレ−ン順走査部
１０４  バッファ
１０５  符号表メモリ
１０６  符号出力部
６０２  離散ウェ−ブレット変換部
６０４  係数量子化部
６０５  Ｇｏｌｏｍｂ符号化部
１３０８  ランレングス符号化部
１６０８  算術符号化部
【図１】
0004054430.tif 000002
【図２】
0004054430.tif 000003
【図３】
0004054430.tif 000004
【図４】
0004054430.tif 000005
【図５】
0004054430.tif 000006
【図６】
0004054430.tif 000007
【図７】
0004054430.tif 000008
【図８】
0004054430.tif 000009
【図９】
0004054430.tif 000010
【図１０】
0004054430.tif 000011
【図１１】
0004054430.tif 000012
【図１２】
0004054430.tif 000013
【図１３】
0004054430.tif 000014
【図１４】
0004054430.tif 000015
【図１５】
0004054430.tif 000016
【図１６】
0004054430.tif 000017