JP4133357B2 - 画像符号化装置および画像符号化方法 - Google Patents
画像符号化装置および画像符号化方法 Download PDFInfo
- Publication number
- JP4133357B2 JP4133357B2 JP2003007468A JP2003007468A JP4133357B2 JP 4133357 B2 JP4133357 B2 JP 4133357B2 JP 2003007468 A JP2003007468 A JP 2003007468A JP 2003007468 A JP2003007468 A JP 2003007468A JP 4133357 B2 JP4133357 B2 JP 4133357B2
- Authority
- JP
- Japan
- Prior art keywords
- image data
- data
- pixel data
- encoding
- pixel
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Editing Of Facsimile Originals (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
- Image Processing (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、画像符号化装置および画像符号化方法に関し、特に、段階的に縮小された解像度の異なる画像データを符号化する符号化装置およびその方法に関する。
【０００２】
【従来の技術】
従来、画像符号化方法として、１つの画像データから複数の解像度の画像データを生成して、階層的に符号化する方法がある。この画像符号化方法は、画像データそのものを最下位階層とし、その階層より解像度の低い画像データを上位の階層の画像データとして生成する処理を繰返すことにより、上位の階層の画像データほど程解像度が低い、いわゆるピラミッド型の複数階層の画像データを生成する。そして、生成された各階層の画像データをそれぞれ圧縮するために符号化する（例えば、特許文献１参照）。
【０００３】
【特許文献１】
特許第３３３７１６０号公報
【０００４】
【発明が解決しようとする課題】
しかしながら、ピラミッド型の複数階層の画像データを符号化する画像符号化方法では、画像データから生成された複数の階層それぞれに対応する解像度の画像データのすべてについて符号化するため、符号化処理の対象となるデータ量が膨大となる。このため、最下位の階層の画像データのみを符号化する場合と比較して、符号化後のデータ量が大きくなるという問題がある。
【０００５】
また、ピラミッド型の複数階層の画像データが符号化されたデータを復号する画像復号方法では、必要とする解像度に対応した階層を指定するだけで、その階層の符号化データだけを復号すれば、所望の解像度の画像データを得ることができる。しかしながら、指定した階層に対応する解像度の画像データのすべてを復号しなければならない。このため、画像の局所的な領域のみを必要とする場合には、不必要な部分まで復号しなければならず、復号に不要な時間を費やしてしまうといった問題がある。
【０００６】
この発明は上述の問題点を解決するためになされたもので、この発明の目的の１つは、ピラミッド型の複数階層の画像データを効率的に符号化するとともに、圧縮率を向上させた画像符号化装置を提供することである。
【０００８】
【課題を解決するための手段】
上述の目的を達成するためにこの発明のある局面によれば、画像符号化装置は、画像データに含まれる画素データの一部を間引いて画像データを縮小することにより解像度が低い、階層レベルが上位の画像データを生成する画像縮小手段と、
階層レベルが上位の画像データから順に処理対象とする処理画像データを選択する選択手段と、
処理対象となる処理画像データを、前記処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割する分割手段と、
前記分割手段により分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データを符号化対象画素データとして復元可能に符号化するための符号化手段と、
２次元に配列された前記符号化対象画素データを予め定められた所定の順序で１次元に配列された画素データに並替える並替手段とを備え、
前記符号化手段は、参照部と符号化部とを備える適応型辞書法に基づく符号化方式を用いて符号化し、
前記並替手段は、前記符号化対象画素データを、２次元に配列された画素位置の横方向に隣接する順に横方向に配列し、該横方向に画素データがなくなると、次の行の画素データを横方向に配列する処理、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列し、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の前記符号化対象画素データがなくなるまで繰り返すことにより１次元に配列し、
前記分割手段は、前記並替手段が１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積を、前記符号化方式の参照部に格納されるデータ数および前記符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割する。
【０００９】
この発明に従えば、階層レベルが上位の画像データから順に処理対象とする処理画像データが選択され、処理画像データが、当該処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割され、分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データが符号化対象画素データとして復元可能に符号化される。並替手段の働きにより、２次元に配列された符号化対象画素データが予め定められた所定の順序で１次元に配列された画素データに並替えられる。符号化手段には、参照部と符号化部とを備える適応型辞書法に基づく符号化方式が用いられて符号化される。並替手段の働きにより、符号化対象画素データが、２次元に配列された画素位置の横方向に隣接する順に横方向に配列され、該横方向に画素データがなくなると、次の行の画素データを横方向に配列される処理が、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列され、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列される処理が、ブロック内の符号化対象画素データがなくなるまで繰り返されることにより１次元に配列される。分割手段の働きにより、並替手段が１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積が、符号化方式の参照部に格納されるデータ数および符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割される。階層レベルが下位の画像データを符号化する際には、より上位の画像データに含まれる画素データが除かれるので、符号化の対象となる画素データを少なくすることができ、圧縮率を向上させることができる。また、ブロック単位で符号化するため、復号する際に部分的に復号することができる。また、符号化の対象とされる画素データが、予め定められた所定の順序で並替えられるので、圧縮率をさらに向上させることができる。さらに、符号化方式の参照部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、圧縮率を向上させることができ、符号化方式の符号化部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、効率よく符号化することができる。その結果、画像データを効率的に符号化するとともに、圧縮率を向上させた画像符号化装置を提供することができる。
【００１８】
この発明のさらに他の局面によれば、画像符号化方法は、画像データに含まれる画素データの一部を間引いて画像データを縮小することにより解像度が低い、階層レベルが上位の画像データを生成するステップと、
階層レベルが上位の画像データから順に処理対象とする処理画像データを選択するステップと、
処理対象となる処理画像データを、前記処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割するステップと、
前記分割ステップにより分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データを符号化対象画素データとして復元可能に符号化するステップと、
２次元に配列された前記符号化対象画素データを予め定められた所定の順序で１次元に配列された画素データに並替えるステップとを含み、
前記符号化するステップは、参照部と符号化部とを備える適応型辞書法に基づく符号化方式を用いて符号化し、
前記並替えるステップは、前記符号化対象画素データを、２次元に配列された画素位置の横方向に隣接する順に横方向に配列し、該横方向に画素データがなくなると、次の行の画素データを横方向に配列する処理、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列し、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の前記符号化対象画素データがなくなるまで繰り返すことにより１次元に配列し、
前記分割するステップは、前記並替えるステップが１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積を、前記符号化方式の参照部に格納されるデータ数および前記符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割する。
【００１９】
この発明に従えば、階層レベルが下位の画像データを符号化する際には、より上位の画像データに含まれる画素データが除かれるので、符号化の対象となる画素データを少なくすることができる。また、ブロック単位で符号化するため、復号する際に部分的に復号することができる。また、符号化の対象とされる画素データが、予め定められた所定の順序で並替えられるので、圧縮率をさらに向上させることができる。さらに、符号化方式の参照部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、圧縮率を向上させることができ、符号化方式の符号化部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、効率よく符号化することができる。その結果、画像データを効率的に符号化する画像符号化方法を提供することができる。
【００２２】
【発明の実施の形態】
以下、図面を参照しつつ、本発明の実施の形態について説明する。以下の説明では、同一の部品には同一の符号を付してある。それらの名称および機能も同じである。したがってそれらについての詳細な説明は繰返さない。
【００２３】
図１は、本発明の実施の形態の１つにおける画像変換装置１００の機能の概略を示すブロック図である。図１を参照して、画像変換装置１００は、画像データを圧縮するために符号化する符号化処理部１０４と、符号化処理部１０４により符号化されたデータを復号するための復号処理部１０５と、符号化処理部１０４および復号処理部１０５で実行されるプログラムが入力されるプログラム入力部１０２と、処理対象となる画像データが入力される画像入力部１０３と、復号された画像データを出力するための画像出力部１０６と、プログラムやデータを記憶するための記憶部１０７と、ユーザからの操作の入力を受付けるための指示入力部１０１とを含む。
【００２４】
また、画像変換装置１００は、画像データを光学的に読取って電子データに変換して出力するスキャナ１０８と、画像データを出力するためのディスプレイ１１０およびプリンタ１１１と、外部記憶装置１１２と、ネットワークインターフェース１０９と接続されている。
【００２５】
画像入力部１０３は、スキャナ１０８、ネットワークインターフェース１０９または外部記憶装置１１２と接続されており、これらから画像データが入力される。画像入力部１０３は、また、符号化処理部１０４と接続されており、入力された画像データを符号化処理部１０４に出力する。
【００２６】
符号化処理部１０４は、プログラム入力部１０２と接続されており、プログラム入力部１０２から受信した符号化プログラムを実行することにより、画像入力部１０３から出力されてきた画像データを圧縮するために画像データを符号化する処理を実行する。この処理は、画像データからピラミッド型の階層をなす複数の解像度の画像データを生成する処理と、生成された複数の解像度の画像データを圧縮するための符号化処理とが含まれる。符号化処理部１０４は、記憶部１０７と接続されており、符号化されたデータを記憶部１０７に記憶する。符号化処理部１０４は、また、指示入力部１０１と接続されており、指示入力部１０１で受付けられたユーザの操作に基づいて、上述の処理を実行する。
【００２７】
復号処理部１０５は、プログラム入力部１０２および記憶部１０７と接続されており、プログラム入力部１０２から受信した復号プログラムを実行することにより、符号化処理部１０４で復号化されたデータを記憶部１０７から読出し、復号する。なお、別の画像変換装置で符号化されたデータが、ネットワークインターフェース１０９を介して受信され、または、外部記憶装置１１２から読出されて記憶部１０７に記憶されている場合には、そのような符号化データを復号することも可能である。
【００２８】
復号処理部１０５は、また、指示入力部１０１と接続されており、指示入力部１０１で受付けられたユーザの操作に基づいて、符号化データを復号する。
【００２９】
外部記憶装置１１２は、フレキシブルディスク（ＦＤ）、コンパクトディスク（ＣＤ）、ミニディスク（ＭＤ）またはハードディスク（ＨＤ）等の記録媒体に対して、画像データ、符号化された画像データまたはプログラムの読出しまたは書込みする。外部記憶装置１１２は、画像出力部１０６、記憶部１０７、プログラム入力部１０２および画像入力部１０３と接続され、これらから送信されてきたデータまたはプログラムを記録媒体に書込む。また、記録媒体に記録された画像データまたは符号化された画像データを読出して、記憶部１０７または画像入力部１０３に送信する。さらに、記録媒体に記録されたプログラムを読出して、プログラム入力部１０２に送信する。
【００３０】
ネットワークインターフェース１０９は、ローカルエリアネットワークやインターネット等の通信網と画像変換装置１００とを接続するためのインターフェースである。画像変換装置１００は、通信網に接続された他のコンピュータとの間で通信することが可能となり、画像データ、符号化された画像データまたはプログラムを、他のコンピュータとの間で送受信する。
【００３１】
スキャナ１０８は、画像入力部１０３と接続されており、読取った画像データを画像入力部１０３に出力する。ディスプレイ１１０およびプリンタ１１１は、画像出力装置１０６と接続されており、画像出力装置１０６から出力される画像データを表示または印刷する。
【００３２】
このように構成してなる画像変換装置１００は、一般的に知られているコンピュータで実現することが可能である。コンピュータ自体のハード構成およびその動作は周知であるので、ここでは説明を繰返さない。
【００３３】
次に、本実施の形態における画像変換装置１００の符号化処理部１０４で実行される処理を説明する。符号化処理部１０４は、画像データからピラミッド型の階層をなす複数の解像度の画像データを生成する処理と、生成された複数の解像度の画像データを圧縮するための符号化処理とを実行する。まず、複数の解像度の画像データを生成する処理を説明する。
【００３４】
符号化処理部１０４では、処理対象となる画像データに基づき、解像度が低い画像データを生成することにより、ピラミッド型の複数階層の画像データを生成する。画像データは、画素データが二次元に配列されたデータからなる。画素データは、２値であっても、多値であってもよい。図２は、画像データを画素の位置を示す符号を付して示した図である。図２を参照して、画素データは、図中Ｘ方向に８列、図中Ｙ方向に８行の行列で表される。図中に示される２桁の数字は、画素の位置を示し、十の位が行を、一の位が列を示す。図では、Ｘ方向に０列〜７列、Ｙ方向に０行〜７行の行列を示している。、例えば、「００」は０行０列の画素を示し、「１３」は１行３列の画素を示し、「７７」は７行７列の画素を示す。
【００３５】
図３は、ピラミッド型の２階層の画素データを示す図である。図３に示す画像データは、図２に示した画像データに基づき生成される各階層の画素データを示す。従って、図３に示す画像データの画素の位置は、図２に示した画像データの各画素に付された位置で示している。
【００３６】
図３（ａ）は、第２階層の画像データを示し、図３（ｂ）は第１階層の画像データを示す。第１階層の画像データは図２に示した画像データと解像度が同じで、第２階層の画像データは第１階層の画像データに対してＸ方向およびＹ方向にそれぞれ１／２の解像度である。第２階層の画像データは、第１階層の画像データよりも解像度が低く、上位の階層の画像データである。
【００３７】
第２階層の画像データは、図２に示した画像データの画素を間引く縮小処理を実行することにより生成される。間引く画素は、処理前の画像データと生成する画像データの解像度により定まる。解像度をＸ方向に１／２にする場合には、１つおきに間引けば良く、Ｘ方向に２／３にする場合には２つおきに間引けば良い。
【００３８】
図４は、ピラミッド型の３階層の画素データを示す図である。図４に示す画像データは、図２に示した画像データに基づき生成される各階層の画素データを示す。従って、図４に示す画像データの画素の位置は、図２に示した画像データの各画素に付された位置で示している。
【００３９】
図４（ａ）は、第３階層の画像データを示し、図４（ｂ）は第２階層の画像データを示し、図４（ｃ）は第１階層の画像データを示す。第１階層の画像データは図２に示した画像データと解像度が同じで、第２階層の画像データは第１階層の画像データに対してＸ方向およびＹ方向にそれぞれ１／２の解像度である。第３階層の画像データは第２階層の画像データに対してＸ方向およびＹ方向にそれぞれ１／２の解像度である。
【００４０】
したがって、第２階層の画像データは、第１階層の画像データよりも解像度が低く上位の階層の画像データである。同様に、第３階層の画像データは、第２階層の画像データよりも解像度が低く上位の階層の画像データである。第１階層の画像データよりも上位の階層の画像データには、第２階層の画像データと第３階層の画像データが含まれる。
【００４１】
第２階層の画像データは、図２に示した画像データの画素を間引く縮小処理を実行することにより生成され、第３階層の画像データは、第２階層の画像データの画素を間引く縮小処理を実行することにより生成される。
【００４２】
次に符号化処理について説明する。符号化処理は、各階層の画像データをブロックに分割して、分割したブロックごとに符号化する。まず、ブロック分割について、図３および図４を用いて説明する。ブロック分割の条件は、ある階層の画像データのブロックそれぞが、より上位の階層の画像データの画素を少なくとも１つ含むことである。まず、図３を用いて説明する。図３（ｂ）に示す第１階層の画像データを、Ｘ方向に４分割、Ｙ方向に４分割し、ブロックＡ００〜Ａ３３が生成される。ブロックもまた行列で表すことができる。このため、ブロックに付された符号は、「Ａ」が第１階層の画像データのブロックを示し、その後数字の十の位が列方向（Ｘ方向）の位置、一の位が行方向（Ｙ方向）の位置を示している。例えば、ブロックＡ００は、第１階層の画像データの０行０列の位置を示す。ここでは、各ブロックは、Ｘ方向の画素数が２、Ｙ方向の画素数が２のブロックとされる。
【００４３】
図３（ａ）に示す第２階層の画像データを、Ｘ方向に２分割、Ｙ方向に２分割し、ブロックＢ００〜Ｂ１１が生成される。ブロックに付された符号は、「Ｂ」が第２階層の画像データのブロックを示し、その後数字の十の位が列方向（Ｘ方向）の位置、一の位が行方向（Ｙ方向）の位置を示している。例えば、ブロックＢ００は、第２階層の画像データの０行０列の位置を示す。ここでは、各ブロックは、Ｘ方向の画素数が２、Ｙ方向の画素数が２のブロックとされる。
【００４４】
図３から明らかなように、、第２階層の画像データに含まれるブロックのそれぞれは、下位の第１階層の画像データのブロックをそれぞれ４つ含んでいる。第１階層の画像データの各ブロックＡ００〜Ａ３３それぞれは、第２階層の画像データの画素を１つ含んでいる。たとえば、ブロックＡ００には、第２階層の画像データの位置「００」の画素データが含まれ、ブロックＡ２１には、第２階層の画像データの位置「４２」の画素データが含まれ、ブロックＡ３３には、第２階層の画像データの位置「６６」の画素データが含まれる。
【００４５】
図４に示した３階層の画像データにおいては、第１階層および第２階層の画像データは、上述した図３に示した２階層の画像データと同様である。図４（ａ）に示す第３階層の画像データは、画素数が少ないためブロックに分割されない。ブロックに付された符号は、「Ａ」が第１階層の画像データのブロックを示し、「Ｂ」が第２階層の画像データのブロックを示し、「Ｃ」が第３階層の画像データのブロックを示し、それぞれの後の数字は十の位が列方向（Ｘ方向）の位置、一の位が行方向（Ｙ方向）の位置を示している。例えば、ブロックＡ００は、第１階層の画像データの０行０列の位置を示す。ここでは、各ブロックは、Ｘ方向の画素数が２、Ｙ方向の画素数が２のブロックとされる。
【００４６】
図４から明らかなように、第３階層の画像データに含まれるブロックそれぞれは、第２階層の画像データのブロックを４つ含んでおり、第２階層の画像データに含まれるブロックそれぞれは、第１階層の画像データのブロックを４つ含んでいる。第１階層の画像データの各ブロックＡ００〜Ａ３３それぞれは、第２階層の画像データの画素を１つ含んでいる。第１階層の画像データのブロックと第２階層の画像データの画素との関係は、図３を用いて説明した２階層の画像データの場合と同様である。第２階層の画像データの各ブロックＢ００〜Ｂ１１のそれぞれは、第３階層の画像データの画素を１つ含んでいる。ブロックＢ００には、第３階層の画像データの位置「００」の画素データが含まれ、ブロックＢ０１には、第３階層の画像データの位置「０４」の画素データが含まれ、ブロックＢ１０には、第３階層の画像データの位置「４０」の画素データが含まれ、ブロックＢ１１には、第３階層の画像データの位置「４４」の画素データが含まれる。
【００４７】
なお、本実施形態では各階層におけるブロックサイズを２のべき乗としているが、上位階層におけるブロックが下位階層における複数のブロックを包含する構造であれば、本発明はこれに限ったものではない。
【００４８】
このようにブロックに分割された画像データは、ブロック毎に符号化される。この符号化の際に、対象となる画素データは、より上位の階層の画像データに含まれる画素データを含まない。また、符号化は、辞書に基づく復元可能な符号化方式が用いられる。本実施の形態においては、ＬＺ７７符号化方式を用いている。さらに、辞書に基づく符号化方式では１次元に配列されたデータを符号化するため、２次元に配列された画素データを１次元に配列しなおす必要がある。このため、本実施の形態においては、２次元に配列された画素データをブロック毎に１次元に配列する。より具体的には、ブロックに含まれる画素データのうちより上位に含まれる画素データを除く画素データを、上位に含まれる画素データの近傍で連続するように配列する処理を、ブロック内の画素データが無くなるまで繰返すことにより１次元に配列する。
【００４９】
画像データは、ある画素の周辺の画素が同じ値となることが多く、横方向および縦方向に同じ値の画素データで配列されることが多い。本実施の形態においては、画像データをブロックに分割するので、横方向（Ｘ方向）に連続する画素データの数が、ブロックに分割しない場合に比較して少なくなる。このため、１次元に配列された画素データは、縦方向（Ｙ方向）に隣接する画素データが比較的近くに配列される。したがって、ＬＺ７７の符号化方式において、参照部にブロックの横方向に隣接する画素データのすべてが格納されるので、圧縮率を向上させることができる。ブロックの横方向の大きさは、参照部に格納されるデータ数より小さいことが望ましい。
【００５０】
これについてさらに詳細に説明する。画像データの横方向（Ｘ方向）の画素数をＷ（ドット）、画素データのビット数（階調を表す）をｋ(ビット)、ＬＺ７７アルゴリズムにおける参照部の長さをＮ（ビット）、ＬＺ７７の符号化部の長さをＦ（ビット）とする。画像データ全体をライン単位で１次元に配列する従来のラスタ順（画素順）でＬＺ７７アルゴリズムを適用すると、画像データの左上にある位置「００」の画素（以下「着目画素」という）に着目し、同じ列で次の行にある位置「１０」の画素を符号化する場合に、着目画素が参照部にあるためにはｋ×Ｗ＜Ｎが成立しなければならない。同様にして同じ列でさらに次の行にある位置「２０」の画素を符号化する場合に、着目画素が参照部にあるためにはｋ×２Ｗ＜ｎが成立しなければならない。これは、次の行の画素が縦方向（Ｙ方向）の近傍にありながらも符号化を行う際に参照部に存在する確率は１画素離れただけで非常に小さくなることを意味する。
【００５１】
本実施の形態におけるブロックの横方向の画素数はＬ（ドット）なので、Ｌ＜Ｗが成立する。このようにすることで、縦方向の近傍にある画素が参照部に存在する確率が高くなる。画像データには２次元的な相関関係があるため、縦近傍の画素が参照部に存在する確率が高くなることで符号化部における最長一致がより長くなる確率が高くなるといえる。さらに近傍のＬ画素は同系列の記号列で一致する確率が高いといえる。よって、符号化を行う際にＬ画素分を参照部と比較できたほうがよい。したがって、符号化部の長さに収まること、すなわち、Ｌ×ｋ＜Ｆが成立すれば効率よく符号化することができる。また、Ｌ＝１（ドット）の場合、ラスタ順を縦型としたものと同様となるため、折り返すことによる効果は得られない。したがって、ブロックの１辺の画素数Ｌは、次式を満たすことが望まれる。 ｋ＜Ｌ×ｋ＜Ｆ
１＜Ｌ＜Ｆ／ｋ、Ｌ＜Ｗ … （１）
また、ＬＺ７７アルゴリズムのような適応型辞書法では、初期状態で参照すべき辞書がないと圧縮よりも伸張が起こる可能性があり、十分に長い記号列に対して効果的な圧縮が得られる。十分に長い記号列に対して効果的な圧縮が得られる理由は参照すべき辞書が十分に得られるためだからである。すなわち、ＬＺ７７アルゴリズムの参照部の大きさを十分にうめるだけの記号列があれば、効果的な圧縮が得られる。したがって、符号化を行う１ブロック内の容量（画素数）が、参照部の大きさ以上となるようなブロックサイズを設定することで効果的な圧縮が得られる。例えば、最下位の階層について説明すると、ブロックサイズをＳ（ドット）、１画素をｋ（ビット）、ＬＺ７７アルゴリズムの参照部の大きさをＮ（ドット）、ブロックを正方形であるとすると、次の式からブロックサイズＳを求めることができる。
【００５２】
Ｓ×Ｓ×ｋ×３／４＞Ｎ
Ｓ＞√（４×Ｎ／（３×ｋ））…（２）
なお、１次元への配列は、画素データを縦方向（Ｙ方向）に配列し、縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の画素データがなくなるまで繰り返すことにより１次元に配列するようにしてもよい。この場合には、ブロックの縦方向の大きさは、参照部に格納されるデータ数より小さいことが望ましい。
【００５３】
さらに、１次元への配列は、横に隣接する画素そして縦に隣接する画素の順、または、縦に隣接する画素、横に隣接する画素の順にジグザグに配列するようにしてもよい。いずれにしても、縦方向に隣接画素と横方向に隣接する画素が参照部に格納されるデータ数より小さくなる間隔で配列されればよく、そのような配列順を予め定めておけばよい。
【００５４】
図５は、２階層の画像データにおいて符号化対象となる画素データを示す図である。図５では、図３に示した２階層の画像データについて示している。図５（ａ）を参照して、第２階層の画像データについては、そのすべての画素データが符号化の対象となる。上位の階層の画像データが存在しないからである。図５（ｂ）を参照して、第１階層の画像データは、第２階層の画像データに含まれる画素データをのぞく画素データが符号化の対照となる。例えば、ブロックＡ００に含まれる画素データには、位置「００」、「０１」、「１０」、「１１」があるが、位置「００」の画素データは第２階層の画像データに含まれるので、符号化の対象とはならない。このように、下位の階層において符号化のとなるデータ数を少なくすることにより、圧縮率を向上させることができる。
【００５５】
図６は、３階層の画像データにおいて符号化対象となる画素データを示す図である。図６では、図４に示した３階層の画像データについて示している。図６（ａ）を参照して、第３階層の画像データについては、そのすべての画素データが符号化の対象となる。上位の階層の画像データが存在しないからである。図６（ｂ）を参照して、第２階層の画像データは、第３階層の画像データに含まれる画素データを除く画素データが符号化の対照となる。例えば、ブロックＢ００に含まれる画素データには、位置「００」、「０２」、「２０」、「２２」があるが、位置「００」の画素データは第３階層の画像データに含まれるので、符号化の対象とはならない。図６（ｃ）を参照して、第１階層の画像データは、第２階層および第３階層の画像データに含まれる画素データを除く画素データが符号化の対照となる。例えば、ブロックＡ００に含まれる画素データには、位置「００」、「０１」、「１０」、「１１」があるが、位置「００」の画素データは第２階層の画像データに含まれるので、符号化の対象とはならない。また、ブロックＡ０１に含まれる画素データには、位置「０２」、「０３」、「１２」、「１３」があるが、位置「０２」の画素データは第２階層の画像データに含まれるので、符号化の対象とはならない。このように、下位の階層（例えば第１の階層）の画像データにおいて、符号化の対象となる画素データは、より上位の階層（第２および第３の階層）の画像データに含まれる画素データを含まない。
【００５６】
図７は、本実施の形態における画像変換装置１００の符号化処理部１０４で実行される符号化処理の流れを示すフローチャートである。ここでは説明のため、図２に示した画像データを２階層の画像データで符号化する場合を例に説明する。図７を参照して、符号化処理では、まず、符号化する階層の指定が受付けられる（ステップＳ０１）。階層の指定は、ユーザが指示入力部１０１を操作することにより入力される。ここでは、画像データを２階層で説明することとしたので、ステップＳ０２で指定されるのは２階層である。
【００５７】
そして、符号化するブロックサイズの指定が受付けられる（ステップＳ０２）。ブロックサイズの指定は、ユーザが指示入力部１０１を操作することにより入力される。上述したように、ブロックの１辺の画素数は式（１）、ブロックサイズは式（２）を満たすことが望ましい。ここでは、縦×横が２×２のブロックサイズが指定されたとする。なお、ステップＳ０１またはステップＳ０２において指示がない場合は、プログラム入力部１０２に入力されたプログラムに記憶されている初期設定を用いることとなる。
【００５８】
次に、符号化処理の対象となる画像データが画像入力部、または記憶部１０７から読込まれる（ステップＳ０３）。そして、最上位レベルの階層が設定される（ステップＳ０４）。ステップＳ０４では、ステップＳ０１で指定された階層（２階層）の数だけ、各階層の画像データを、ステップＳ０３で入力された画像データを間引きによる縮小処理を実行することにより生成し、最上位の階層の画像データを処理対象の画像データに設定する。ここでは、ステップＳ０３で入力された画像データが最下位の第１階層の画像データとされる。そして、指定された階層が２階層であるため、第２階層の画像データが生成される。さらに、最上位の第２階層の画像データが処理対象の画像データに設定される。 次に処理対象の画像データにおけるブロックサイズが設定される（ステップＳ０５）。ステップＳ０５では、ステップＳ０２で指定されたブロックサイズに基づき、処理対象の画像データのブロックサイズが設定される。ここでは、図３（ａ）に示した、縦×横が２×２のブロックサイズが設定されることになる。そして、設定されたブロックサイズに基づいて、処理対象の画像データがブロックに分割される（ステップＳ０６）。
【００５９】
次に、分割されたブロックのうち符号化されていないブロックが設定される（ステップＳ０７）。ここでは、図３（ａ）に示した４ブロックＢ００，Ｂ０１，Ｂ１０，Ｂ１１のうちからブロックＢ００が設定されたとする。設定されたブロックの画素データが並替えられ（ステップＳ０８）、並替えられた画素データがＬＺ７７アルゴリズムに従って符号化される（ステップＳ０９）。画素データの並替えは、図５（ａ）に示す矢印の順である。
【００６０】
次のステップＳ１０では、処理対象の画像データに含まれるすべてのブロックについて符号化が終了したかどうかが判定される（ステップＳ１０）。すべてのブロックについての符号化が終了していない場合、それらのブロックのうちいずれかを処理対象のブロックに設定し、設定されたブロックに対してステップＳ０７からステップＳ０９の処理を繰り返し実行する。処理対の画像データのすべてのブロックについてステップＳ０７からステップＳ０９の処理が終了した場合、ステップＳ１１に進む。
【００６１】
ステップＳ１１では、下位の階層の画像データが存在するか否かが判断される。下位の階層の画像データが存在する場合には、その下位の階層の画像データを処理対象の画像データに設定して（ステップＳ１２）、ステップＳ０５〜ステップＳ１０の処理を実行する。下位の階層の画像データが存在しない場合、すなわち、第１階層の画像データについてステップＳ０５〜ステップＳ１０の処理が実行された場合には、処理を終了する。この際、符号化された符号化データは符号化処理部１０４から記憶部１０７へ入力され、記憶される。
【００６２】
記憶部１０７へ記憶される際に、符号化されたデータは、階層毎およびブロック毎に分類されて記憶される。この分類するための情報は、符号化されたデータのヘッダ部分に含まれる。すなわち、このヘッダ部分には、どの階層のどのブロックがどの符号化データに該当するかの情報を含む。したがって、このヘッダ部分の情報を得ることにより、任意の階層の任意のブロックの符号化データのみを得ることができる。
【００６３】
第１階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。これは、ステップＳ０２で指定されたブロックサイズである。また、ステップＳ０９における符号化においては、第１階層の画像データに含まれる画素データは符号化の対象とされない。また、ステップＳ０８における並替えは、図５（ｂ）の矢印で示す順に並替えられる。
【００６４】
画像データを３階層の画像データとして符号化する場合は、ステップＳ０５からステップＳ１１までの処理が、第３階層の画像データから第２階層、第１階層の画像データの順に、それぞれの階層の画像データに対して繰り返し実行される。
【００６５】
第３階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。そして、ステップＳ０９における符号化においては、第３階層の画像データに含まれるすべての画素データが対象となる。また、ステップＳ０８における並替えは、図６（ｃ）の矢印で示す順に並替えられる。
【００６６】
第２階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。そして、ステップＳ０９における符号化においては、第３階層の画像データに含まれる画素データは対象とならない。また、ステップＳ０８における並替えは、図６（ｂ）の矢印で示す順に並替えられる。
【００６７】
第１階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。そして、ステップＳ０９における符号化においては、第２階層および３階層の画像データに含まれる画素データは対象とならない。また、ステップＳ０８における並替えは、図６（ａ）の矢印で示す順に並替えられる。
【００６８】
以上説明したように本実施の形態における画像変換装置１００は、下位階層の画像データを符号化する際に、既に符号化された上位階層の画像データを重複して符号化することがない。このため、符号化する画素データは、入力された画像データ、すなわち最下位の画像データ（第１階層の画像データ）の画素数から増加することはない。より具体的には、図５（ｂ）を参照して、最下位の第１階層の画像データは、元の画像データの４分の３の画素データからなる。このため、符号化の対象となる画素データ数を少なくすることで、圧縮容量を削減することができる。
【００６９】
また、２次元に配列された画素データを１次元に並替える順番は、各階層の画像データにおいて隣接する画素の順番とするので、類似した系列の画素が連続するようになる。これにより、ＬＺ７７のような可変長の記号列を固定長もしくは可変長の符号語に変換する手法において、より長い可変長の記号列を固定長もしくは可変長の符号語に変換することができる。即ち、最長一致系列を検索するような辞書に基づく符号化方式によって効率良く符号化されるので、圧縮容量を削減することができる。
【００７０】
図８は、本実施の形態における画像変換装置１００の復号処理部１０５で実行される復号処理の流れを示すフローチャートである。復号処理部１０５は、復号処理プログラムがプログラム入力部１０２から復号処理部１０５へ入力される。復号処理プログラムは、外部記憶装置１１２、または、ネットワークインターフェース１０９から入力される。また、記憶部１０７に記憶しておくようにしても良い。
【００７１】
図８を参照して、復号処理ははじめに復号したい階層レベルの指定が受付けられる（ステップＳ２１）。階層レベルとは、復号の対象となる画像の解像度に対応する階層を示す。階層レベルと解像度との関係を、符号化データのヘッダ部に記憶しておくようにすれば、そのヘッダ部を読取り、画像出力部１０６からディスプレイ１１０に表示することにより、ユーザに知らせることができる。また、ユーザが解像度を指定することにより、ヘッダ部に記憶された情報を基にして階層レベルを決定するようにしてもよい。
【００７２】
次に復号の対象となる領域の指定が受付けられる（ステップＳ２２）。階層レベルの指定および復号対象領域の指定は、ユーザが指示入力部１０１を操作することにより入力される。復号対象領域は、符号化の際に処理単位とされたブロック単位でもよいし、複数のブロックを含んでもよい。
【００７３】
次に指定された階層レベルおよび領域に対応する符号化データが読込まれる（ステップＳ２３）。指定された階層レベルおよび領域に対応する符号化データは、符号化データのヘッダ部に含まれる情報から特定される。また、指定された階層レベルおよび領域に対応する符号化データは、指定された階層レベルの指定された領域に含まれるブロックに対応する符号化データに加えて、そのブロックを含む上位の階層の画像データのブロックに対応する符号化データも含まれる。より具体的には、３階層の画像データで符号化されたデータについて図６を用いて説明すると、指定された階層レベルが第１階層、指定された領域がブロックＡ００とすると、読出される符号化データは、ブロックＡ００の画素データを符号化した符号化データに加えて、ブロックＡ００を含む第２階層の画像データのブロックＢ００および第１階層の画像データのブロックＣ００の画素データを符号化した符号化データが含まれる。以下、これらの符号化データが読込まれた場合を例に説明する。
【００７４】
次に、最上位の階層の符号化データが処理対象データに設定される（ステップＳ２４）。
【００７５】
次のステップＳ２５では、設定された処理対象データのうち復号されていないブロックが設定される。そして、設定されたブロックの符号化データが復号される（ステップＳ２６）。この符号化データは復号されることにより１次元に配列された画素データが得られる。ステップＳ２６では、復号された画素データが、階層レベルが最下位の第１階層の画像データに含まれるブロックの画素位置にそれぞれ割当てらる。これにより、１次元に配列された画素データが２次元に配列されることになる。
【００７６】
そして、ステップＳ２７では、設定された処理対象データのすべてのブロックについて復号されたか否かが判断され、真の場合にはステップＳ２８に進み、偽の場合にはステップＳ２５に進む。すなわち、設定された処理対象データのすべてのブロックについて復号されるまで、ステップＳ２５とステップＳ２６とが繰返し実行される。
【００７７】
次に、復号されたブロックの画像が結合される（ステップＳ２８）。処理対象の符号化データが複数のブロックからなる場合に実行される処理である。ブロックを結合するための情報、すなわちブロックの位置情報は、符号化データのヘッダ部に記憶されているため、この情報を参照して結合される。位置情報は、例えば、Ａ００、Ａ０１などの行列で表現することができる。
【００７８】
そして、復号されたブロックの画像が結合された画像を、上位の階層の復号された画像で補間する。ステップＳ２４では、最上位の階層の符号化データが、第３階層の画像データを符号化したデータが該当し、ステップＳ２５〜ステップＳ２８までの処理が実行されると、図６（ａ）に示した画像データが復号される。この場合に、ステップＳ２９においては、第３階層の画像データより上位の階層が存在しないため、何も実行しない。
【００７９】
次のステップＳ３０では、指定された階層レベルまで復号されたか否かが判断され、真の場合には処理を終了し、偽の場合にはステップＳ３１に進む。復号された画像データは復号処理部１０５から画像出力部１０６または、記憶部１０７に出力される。
【００８０】
ステップＳ３１では、処理対象の符号化データを次に下位の階層の符号化データに設定し、ステップＳ２５に進む。第２階層の符号化データ、より具体的には、第２階層の画像データのブロックＢ００を符号化したデータが処理対象データとされ、ステップＳ２７において、図６（ｂ）に示したブロックＢ００の画素データが復号される。ブロックＢ００には、位置「００」の画素データが含まれないため、ステップＳ２９において、上位の階層の画像データの位置「００」の画素データが補間される。これにより、補間された画像データは、位置「００」、「０２」、「２０」および「２２」の画素データを含むことになる。
【００８１】
さらに、ステップＳ３１において、第３階層の符号化データ、より具体的には、第３階層の画像データのブロックＡ００を符号化したデータが処理対象データとされ、ステップＳ２７において、図６（ｃ）に示したブロックＡ００の画素データが復号される。ブロックＡ００には、位置「００」の画素データが含まれないため、ステップＳ２９において、上位の階層の画像データの位置「００」の画素データが補間される。これにより、補間された画像データは、位置「００」、「０１」、「１０」「１１」の画素データを含むことになる。なお、上述の処理で、位置「０２」、「２０」および「２２」の画素データが復号されたが、指定された領域に含まれないため利用する必要はない。
【００８２】
以上説明したように、本実施の形態における画像変換装置１００では、符号化された画像データをブロック単位で復号するため、画像データの局所的な領域だけを復号することができる。また、不要な領域を復号することがないので、復号処理の処理速度を速くすることができる。
【００８３】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【図１】 本発明の実施の形態の１つにおける画像変換装置の機能の概略を示す機能ブロック図である。
【図２】 画像データを画素の位置を示す符号を付して示した図である。
【図３】 ピラミッド型の２階層の画素データを示す図である。
【図４】 ピラミッド型の３階層の画素データを示す図である。
【図５】 ２階層の画像データにおいて符号化対象となる画素データを示す図である。
【図６】 ３階層の画像データにおいて符号化対象となる画素データを示す図である。
【図７】 本実施の形態における画像変換装置の符号化処理部で実行される符号化処理の流れを示すフローチャートである。
【図８】 本実施の形態における画像変換装置の復号処理部で実行される復号処理の流れを示すフローチャートである。
【符号の説明】
１００ 画像変換装置、１０１ 指示入力部、１０２ プログラム入力部、１０３ 画像入力部、１０４ 符号化処理部、１０５ 復号処理部、１０６ 画像出力装置、１０６ 画像出力部、１０７ 記憶部、１０８ スキャナ、１０９ ネットワークインターフェース、１１０ ディスプレイ、１１１ プリンタ、１１２ 外部記憶装置。
【発明の属する技術分野】
本発明は、画像符号化装置および画像符号化方法に関し、特に、段階的に縮小された解像度の異なる画像データを符号化する符号化装置およびその方法に関する。
【０００２】
【従来の技術】
従来、画像符号化方法として、１つの画像データから複数の解像度の画像データを生成して、階層的に符号化する方法がある。この画像符号化方法は、画像データそのものを最下位階層とし、その階層より解像度の低い画像データを上位の階層の画像データとして生成する処理を繰返すことにより、上位の階層の画像データほど程解像度が低い、いわゆるピラミッド型の複数階層の画像データを生成する。そして、生成された各階層の画像データをそれぞれ圧縮するために符号化する（例えば、特許文献１参照）。
【０００３】
【特許文献１】
特許第３３３７１６０号公報
【０００４】
【発明が解決しようとする課題】
しかしながら、ピラミッド型の複数階層の画像データを符号化する画像符号化方法では、画像データから生成された複数の階層それぞれに対応する解像度の画像データのすべてについて符号化するため、符号化処理の対象となるデータ量が膨大となる。このため、最下位の階層の画像データのみを符号化する場合と比較して、符号化後のデータ量が大きくなるという問題がある。
【０００５】
また、ピラミッド型の複数階層の画像データが符号化されたデータを復号する画像復号方法では、必要とする解像度に対応した階層を指定するだけで、その階層の符号化データだけを復号すれば、所望の解像度の画像データを得ることができる。しかしながら、指定した階層に対応する解像度の画像データのすべてを復号しなければならない。このため、画像の局所的な領域のみを必要とする場合には、不必要な部分まで復号しなければならず、復号に不要な時間を費やしてしまうといった問題がある。
【０００６】
この発明は上述の問題点を解決するためになされたもので、この発明の目的の１つは、ピラミッド型の複数階層の画像データを効率的に符号化するとともに、圧縮率を向上させた画像符号化装置を提供することである。
【０００８】
【課題を解決するための手段】
上述の目的を達成するためにこの発明のある局面によれば、画像符号化装置は、画像データに含まれる画素データの一部を間引いて画像データを縮小することにより解像度が低い、階層レベルが上位の画像データを生成する画像縮小手段と、
階層レベルが上位の画像データから順に処理対象とする処理画像データを選択する選択手段と、
処理対象となる処理画像データを、前記処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割する分割手段と、
前記分割手段により分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データを符号化対象画素データとして復元可能に符号化するための符号化手段と、
２次元に配列された前記符号化対象画素データを予め定められた所定の順序で１次元に配列された画素データに並替える並替手段とを備え、
前記符号化手段は、参照部と符号化部とを備える適応型辞書法に基づく符号化方式を用いて符号化し、
前記並替手段は、前記符号化対象画素データを、２次元に配列された画素位置の横方向に隣接する順に横方向に配列し、該横方向に画素データがなくなると、次の行の画素データを横方向に配列する処理、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列し、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の前記符号化対象画素データがなくなるまで繰り返すことにより１次元に配列し、
前記分割手段は、前記並替手段が１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積を、前記符号化方式の参照部に格納されるデータ数および前記符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割する。
【０００９】
この発明に従えば、階層レベルが上位の画像データから順に処理対象とする処理画像データが選択され、処理画像データが、当該処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割され、分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データが符号化対象画素データとして復元可能に符号化される。並替手段の働きにより、２次元に配列された符号化対象画素データが予め定められた所定の順序で１次元に配列された画素データに並替えられる。符号化手段には、参照部と符号化部とを備える適応型辞書法に基づく符号化方式が用いられて符号化される。並替手段の働きにより、符号化対象画素データが、２次元に配列された画素位置の横方向に隣接する順に横方向に配列され、該横方向に画素データがなくなると、次の行の画素データを横方向に配列される処理が、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列され、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列される処理が、ブロック内の符号化対象画素データがなくなるまで繰り返されることにより１次元に配列される。分割手段の働きにより、並替手段が１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積が、符号化方式の参照部に格納されるデータ数および符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割される。階層レベルが下位の画像データを符号化する際には、より上位の画像データに含まれる画素データが除かれるので、符号化の対象となる画素データを少なくすることができ、圧縮率を向上させることができる。また、ブロック単位で符号化するため、復号する際に部分的に復号することができる。また、符号化の対象とされる画素データが、予め定められた所定の順序で並替えられるので、圧縮率をさらに向上させることができる。さらに、符号化方式の参照部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、圧縮率を向上させることができ、符号化方式の符号化部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、効率よく符号化することができる。その結果、画像データを効率的に符号化するとともに、圧縮率を向上させた画像符号化装置を提供することができる。
【００１８】
この発明のさらに他の局面によれば、画像符号化方法は、画像データに含まれる画素データの一部を間引いて画像データを縮小することにより解像度が低い、階層レベルが上位の画像データを生成するステップと、
階層レベルが上位の画像データから順に処理対象とする処理画像データを選択するステップと、
処理対象となる処理画像データを、前記処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割するステップと、
前記分割ステップにより分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データを符号化対象画素データとして復元可能に符号化するステップと、
２次元に配列された前記符号化対象画素データを予め定められた所定の順序で１次元に配列された画素データに並替えるステップとを含み、
前記符号化するステップは、参照部と符号化部とを備える適応型辞書法に基づく符号化方式を用いて符号化し、
前記並替えるステップは、前記符号化対象画素データを、２次元に配列された画素位置の横方向に隣接する順に横方向に配列し、該横方向に画素データがなくなると、次の行の画素データを横方向に配列する処理、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列し、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の前記符号化対象画素データがなくなるまで繰り返すことにより１次元に配列し、
前記分割するステップは、前記並替えるステップが１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積を、前記符号化方式の参照部に格納されるデータ数および前記符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割する。
【００１９】
この発明に従えば、階層レベルが下位の画像データを符号化する際には、より上位の画像データに含まれる画素データが除かれるので、符号化の対象となる画素データを少なくすることができる。また、ブロック単位で符号化するため、復号する際に部分的に復号することができる。また、符号化の対象とされる画素データが、予め定められた所定の順序で並替えられるので、圧縮率をさらに向上させることができる。さらに、符号化方式の参照部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、圧縮率を向上させることができ、符号化方式の符号化部にブロックの横方向の１行内または縦方向の１列内に隣接する画素データのすべてが格納されるので、効率よく符号化することができる。その結果、画像データを効率的に符号化する画像符号化方法を提供することができる。
【００２２】
【発明の実施の形態】
以下、図面を参照しつつ、本発明の実施の形態について説明する。以下の説明では、同一の部品には同一の符号を付してある。それらの名称および機能も同じである。したがってそれらについての詳細な説明は繰返さない。
【００２３】
図１は、本発明の実施の形態の１つにおける画像変換装置１００の機能の概略を示すブロック図である。図１を参照して、画像変換装置１００は、画像データを圧縮するために符号化する符号化処理部１０４と、符号化処理部１０４により符号化されたデータを復号するための復号処理部１０５と、符号化処理部１０４および復号処理部１０５で実行されるプログラムが入力されるプログラム入力部１０２と、処理対象となる画像データが入力される画像入力部１０３と、復号された画像データを出力するための画像出力部１０６と、プログラムやデータを記憶するための記憶部１０７と、ユーザからの操作の入力を受付けるための指示入力部１０１とを含む。
【００２４】
また、画像変換装置１００は、画像データを光学的に読取って電子データに変換して出力するスキャナ１０８と、画像データを出力するためのディスプレイ１１０およびプリンタ１１１と、外部記憶装置１１２と、ネットワークインターフェース１０９と接続されている。
【００２５】
画像入力部１０３は、スキャナ１０８、ネットワークインターフェース１０９または外部記憶装置１１２と接続されており、これらから画像データが入力される。画像入力部１０３は、また、符号化処理部１０４と接続されており、入力された画像データを符号化処理部１０４に出力する。
【００２６】
符号化処理部１０４は、プログラム入力部１０２と接続されており、プログラム入力部１０２から受信した符号化プログラムを実行することにより、画像入力部１０３から出力されてきた画像データを圧縮するために画像データを符号化する処理を実行する。この処理は、画像データからピラミッド型の階層をなす複数の解像度の画像データを生成する処理と、生成された複数の解像度の画像データを圧縮するための符号化処理とが含まれる。符号化処理部１０４は、記憶部１０７と接続されており、符号化されたデータを記憶部１０７に記憶する。符号化処理部１０４は、また、指示入力部１０１と接続されており、指示入力部１０１で受付けられたユーザの操作に基づいて、上述の処理を実行する。
【００２７】
復号処理部１０５は、プログラム入力部１０２および記憶部１０７と接続されており、プログラム入力部１０２から受信した復号プログラムを実行することにより、符号化処理部１０４で復号化されたデータを記憶部１０７から読出し、復号する。なお、別の画像変換装置で符号化されたデータが、ネットワークインターフェース１０９を介して受信され、または、外部記憶装置１１２から読出されて記憶部１０７に記憶されている場合には、そのような符号化データを復号することも可能である。
【００２８】
復号処理部１０５は、また、指示入力部１０１と接続されており、指示入力部１０１で受付けられたユーザの操作に基づいて、符号化データを復号する。
【００２９】
外部記憶装置１１２は、フレキシブルディスク（ＦＤ）、コンパクトディスク（ＣＤ）、ミニディスク（ＭＤ）またはハードディスク（ＨＤ）等の記録媒体に対して、画像データ、符号化された画像データまたはプログラムの読出しまたは書込みする。外部記憶装置１１２は、画像出力部１０６、記憶部１０７、プログラム入力部１０２および画像入力部１０３と接続され、これらから送信されてきたデータまたはプログラムを記録媒体に書込む。また、記録媒体に記録された画像データまたは符号化された画像データを読出して、記憶部１０７または画像入力部１０３に送信する。さらに、記録媒体に記録されたプログラムを読出して、プログラム入力部１０２に送信する。
【００３０】
ネットワークインターフェース１０９は、ローカルエリアネットワークやインターネット等の通信網と画像変換装置１００とを接続するためのインターフェースである。画像変換装置１００は、通信網に接続された他のコンピュータとの間で通信することが可能となり、画像データ、符号化された画像データまたはプログラムを、他のコンピュータとの間で送受信する。
【００３１】
スキャナ１０８は、画像入力部１０３と接続されており、読取った画像データを画像入力部１０３に出力する。ディスプレイ１１０およびプリンタ１１１は、画像出力装置１０６と接続されており、画像出力装置１０６から出力される画像データを表示または印刷する。
【００３２】
このように構成してなる画像変換装置１００は、一般的に知られているコンピュータで実現することが可能である。コンピュータ自体のハード構成およびその動作は周知であるので、ここでは説明を繰返さない。
【００３３】
次に、本実施の形態における画像変換装置１００の符号化処理部１０４で実行される処理を説明する。符号化処理部１０４は、画像データからピラミッド型の階層をなす複数の解像度の画像データを生成する処理と、生成された複数の解像度の画像データを圧縮するための符号化処理とを実行する。まず、複数の解像度の画像データを生成する処理を説明する。
【００３４】
符号化処理部１０４では、処理対象となる画像データに基づき、解像度が低い画像データを生成することにより、ピラミッド型の複数階層の画像データを生成する。画像データは、画素データが二次元に配列されたデータからなる。画素データは、２値であっても、多値であってもよい。図２は、画像データを画素の位置を示す符号を付して示した図である。図２を参照して、画素データは、図中Ｘ方向に８列、図中Ｙ方向に８行の行列で表される。図中に示される２桁の数字は、画素の位置を示し、十の位が行を、一の位が列を示す。図では、Ｘ方向に０列〜７列、Ｙ方向に０行〜７行の行列を示している。、例えば、「００」は０行０列の画素を示し、「１３」は１行３列の画素を示し、「７７」は７行７列の画素を示す。
【００３５】
図３は、ピラミッド型の２階層の画素データを示す図である。図３に示す画像データは、図２に示した画像データに基づき生成される各階層の画素データを示す。従って、図３に示す画像データの画素の位置は、図２に示した画像データの各画素に付された位置で示している。
【００３６】
図３（ａ）は、第２階層の画像データを示し、図３（ｂ）は第１階層の画像データを示す。第１階層の画像データは図２に示した画像データと解像度が同じで、第２階層の画像データは第１階層の画像データに対してＸ方向およびＹ方向にそれぞれ１／２の解像度である。第２階層の画像データは、第１階層の画像データよりも解像度が低く、上位の階層の画像データである。
【００３７】
第２階層の画像データは、図２に示した画像データの画素を間引く縮小処理を実行することにより生成される。間引く画素は、処理前の画像データと生成する画像データの解像度により定まる。解像度をＸ方向に１／２にする場合には、１つおきに間引けば良く、Ｘ方向に２／３にする場合には２つおきに間引けば良い。
【００３８】
図４は、ピラミッド型の３階層の画素データを示す図である。図４に示す画像データは、図２に示した画像データに基づき生成される各階層の画素データを示す。従って、図４に示す画像データの画素の位置は、図２に示した画像データの各画素に付された位置で示している。
【００３９】
図４（ａ）は、第３階層の画像データを示し、図４（ｂ）は第２階層の画像データを示し、図４（ｃ）は第１階層の画像データを示す。第１階層の画像データは図２に示した画像データと解像度が同じで、第２階層の画像データは第１階層の画像データに対してＸ方向およびＹ方向にそれぞれ１／２の解像度である。第３階層の画像データは第２階層の画像データに対してＸ方向およびＹ方向にそれぞれ１／２の解像度である。
【００４０】
したがって、第２階層の画像データは、第１階層の画像データよりも解像度が低く上位の階層の画像データである。同様に、第３階層の画像データは、第２階層の画像データよりも解像度が低く上位の階層の画像データである。第１階層の画像データよりも上位の階層の画像データには、第２階層の画像データと第３階層の画像データが含まれる。
【００４１】
第２階層の画像データは、図２に示した画像データの画素を間引く縮小処理を実行することにより生成され、第３階層の画像データは、第２階層の画像データの画素を間引く縮小処理を実行することにより生成される。
【００４２】
次に符号化処理について説明する。符号化処理は、各階層の画像データをブロックに分割して、分割したブロックごとに符号化する。まず、ブロック分割について、図３および図４を用いて説明する。ブロック分割の条件は、ある階層の画像データのブロックそれぞが、より上位の階層の画像データの画素を少なくとも１つ含むことである。まず、図３を用いて説明する。図３（ｂ）に示す第１階層の画像データを、Ｘ方向に４分割、Ｙ方向に４分割し、ブロックＡ００〜Ａ３３が生成される。ブロックもまた行列で表すことができる。このため、ブロックに付された符号は、「Ａ」が第１階層の画像データのブロックを示し、その後数字の十の位が列方向（Ｘ方向）の位置、一の位が行方向（Ｙ方向）の位置を示している。例えば、ブロックＡ００は、第１階層の画像データの０行０列の位置を示す。ここでは、各ブロックは、Ｘ方向の画素数が２、Ｙ方向の画素数が２のブロックとされる。
【００４３】
図３（ａ）に示す第２階層の画像データを、Ｘ方向に２分割、Ｙ方向に２分割し、ブロックＢ００〜Ｂ１１が生成される。ブロックに付された符号は、「Ｂ」が第２階層の画像データのブロックを示し、その後数字の十の位が列方向（Ｘ方向）の位置、一の位が行方向（Ｙ方向）の位置を示している。例えば、ブロックＢ００は、第２階層の画像データの０行０列の位置を示す。ここでは、各ブロックは、Ｘ方向の画素数が２、Ｙ方向の画素数が２のブロックとされる。
【００４４】
図３から明らかなように、、第２階層の画像データに含まれるブロックのそれぞれは、下位の第１階層の画像データのブロックをそれぞれ４つ含んでいる。第１階層の画像データの各ブロックＡ００〜Ａ３３それぞれは、第２階層の画像データの画素を１つ含んでいる。たとえば、ブロックＡ００には、第２階層の画像データの位置「００」の画素データが含まれ、ブロックＡ２１には、第２階層の画像データの位置「４２」の画素データが含まれ、ブロックＡ３３には、第２階層の画像データの位置「６６」の画素データが含まれる。
【００４５】
図４に示した３階層の画像データにおいては、第１階層および第２階層の画像データは、上述した図３に示した２階層の画像データと同様である。図４（ａ）に示す第３階層の画像データは、画素数が少ないためブロックに分割されない。ブロックに付された符号は、「Ａ」が第１階層の画像データのブロックを示し、「Ｂ」が第２階層の画像データのブロックを示し、「Ｃ」が第３階層の画像データのブロックを示し、それぞれの後の数字は十の位が列方向（Ｘ方向）の位置、一の位が行方向（Ｙ方向）の位置を示している。例えば、ブロックＡ００は、第１階層の画像データの０行０列の位置を示す。ここでは、各ブロックは、Ｘ方向の画素数が２、Ｙ方向の画素数が２のブロックとされる。
【００４６】
図４から明らかなように、第３階層の画像データに含まれるブロックそれぞれは、第２階層の画像データのブロックを４つ含んでおり、第２階層の画像データに含まれるブロックそれぞれは、第１階層の画像データのブロックを４つ含んでいる。第１階層の画像データの各ブロックＡ００〜Ａ３３それぞれは、第２階層の画像データの画素を１つ含んでいる。第１階層の画像データのブロックと第２階層の画像データの画素との関係は、図３を用いて説明した２階層の画像データの場合と同様である。第２階層の画像データの各ブロックＢ００〜Ｂ１１のそれぞれは、第３階層の画像データの画素を１つ含んでいる。ブロックＢ００には、第３階層の画像データの位置「００」の画素データが含まれ、ブロックＢ０１には、第３階層の画像データの位置「０４」の画素データが含まれ、ブロックＢ１０には、第３階層の画像データの位置「４０」の画素データが含まれ、ブロックＢ１１には、第３階層の画像データの位置「４４」の画素データが含まれる。
【００４７】
なお、本実施形態では各階層におけるブロックサイズを２のべき乗としているが、上位階層におけるブロックが下位階層における複数のブロックを包含する構造であれば、本発明はこれに限ったものではない。
【００４８】
このようにブロックに分割された画像データは、ブロック毎に符号化される。この符号化の際に、対象となる画素データは、より上位の階層の画像データに含まれる画素データを含まない。また、符号化は、辞書に基づく復元可能な符号化方式が用いられる。本実施の形態においては、ＬＺ７７符号化方式を用いている。さらに、辞書に基づく符号化方式では１次元に配列されたデータを符号化するため、２次元に配列された画素データを１次元に配列しなおす必要がある。このため、本実施の形態においては、２次元に配列された画素データをブロック毎に１次元に配列する。より具体的には、ブロックに含まれる画素データのうちより上位に含まれる画素データを除く画素データを、上位に含まれる画素データの近傍で連続するように配列する処理を、ブロック内の画素データが無くなるまで繰返すことにより１次元に配列する。
【００４９】
画像データは、ある画素の周辺の画素が同じ値となることが多く、横方向および縦方向に同じ値の画素データで配列されることが多い。本実施の形態においては、画像データをブロックに分割するので、横方向（Ｘ方向）に連続する画素データの数が、ブロックに分割しない場合に比較して少なくなる。このため、１次元に配列された画素データは、縦方向（Ｙ方向）に隣接する画素データが比較的近くに配列される。したがって、ＬＺ７７の符号化方式において、参照部にブロックの横方向に隣接する画素データのすべてが格納されるので、圧縮率を向上させることができる。ブロックの横方向の大きさは、参照部に格納されるデータ数より小さいことが望ましい。
【００５０】
これについてさらに詳細に説明する。画像データの横方向（Ｘ方向）の画素数をＷ（ドット）、画素データのビット数（階調を表す）をｋ(ビット)、ＬＺ７７アルゴリズムにおける参照部の長さをＮ（ビット）、ＬＺ７７の符号化部の長さをＦ（ビット）とする。画像データ全体をライン単位で１次元に配列する従来のラスタ順（画素順）でＬＺ７７アルゴリズムを適用すると、画像データの左上にある位置「００」の画素（以下「着目画素」という）に着目し、同じ列で次の行にある位置「１０」の画素を符号化する場合に、着目画素が参照部にあるためにはｋ×Ｗ＜Ｎが成立しなければならない。同様にして同じ列でさらに次の行にある位置「２０」の画素を符号化する場合に、着目画素が参照部にあるためにはｋ×２Ｗ＜ｎが成立しなければならない。これは、次の行の画素が縦方向（Ｙ方向）の近傍にありながらも符号化を行う際に参照部に存在する確率は１画素離れただけで非常に小さくなることを意味する。
【００５１】
本実施の形態におけるブロックの横方向の画素数はＬ（ドット）なので、Ｌ＜Ｗが成立する。このようにすることで、縦方向の近傍にある画素が参照部に存在する確率が高くなる。画像データには２次元的な相関関係があるため、縦近傍の画素が参照部に存在する確率が高くなることで符号化部における最長一致がより長くなる確率が高くなるといえる。さらに近傍のＬ画素は同系列の記号列で一致する確率が高いといえる。よって、符号化を行う際にＬ画素分を参照部と比較できたほうがよい。したがって、符号化部の長さに収まること、すなわち、Ｌ×ｋ＜Ｆが成立すれば効率よく符号化することができる。また、Ｌ＝１（ドット）の場合、ラスタ順を縦型としたものと同様となるため、折り返すことによる効果は得られない。したがって、ブロックの１辺の画素数Ｌは、次式を満たすことが望まれる。 ｋ＜Ｌ×ｋ＜Ｆ
１＜Ｌ＜Ｆ／ｋ、Ｌ＜Ｗ … （１）
また、ＬＺ７７アルゴリズムのような適応型辞書法では、初期状態で参照すべき辞書がないと圧縮よりも伸張が起こる可能性があり、十分に長い記号列に対して効果的な圧縮が得られる。十分に長い記号列に対して効果的な圧縮が得られる理由は参照すべき辞書が十分に得られるためだからである。すなわち、ＬＺ７７アルゴリズムの参照部の大きさを十分にうめるだけの記号列があれば、効果的な圧縮が得られる。したがって、符号化を行う１ブロック内の容量（画素数）が、参照部の大きさ以上となるようなブロックサイズを設定することで効果的な圧縮が得られる。例えば、最下位の階層について説明すると、ブロックサイズをＳ（ドット）、１画素をｋ（ビット）、ＬＺ７７アルゴリズムの参照部の大きさをＮ（ドット）、ブロックを正方形であるとすると、次の式からブロックサイズＳを求めることができる。
【００５２】
Ｓ×Ｓ×ｋ×３／４＞Ｎ
Ｓ＞√（４×Ｎ／（３×ｋ））…（２）
なお、１次元への配列は、画素データを縦方向（Ｙ方向）に配列し、縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の画素データがなくなるまで繰り返すことにより１次元に配列するようにしてもよい。この場合には、ブロックの縦方向の大きさは、参照部に格納されるデータ数より小さいことが望ましい。
【００５３】
さらに、１次元への配列は、横に隣接する画素そして縦に隣接する画素の順、または、縦に隣接する画素、横に隣接する画素の順にジグザグに配列するようにしてもよい。いずれにしても、縦方向に隣接画素と横方向に隣接する画素が参照部に格納されるデータ数より小さくなる間隔で配列されればよく、そのような配列順を予め定めておけばよい。
【００５４】
図５は、２階層の画像データにおいて符号化対象となる画素データを示す図である。図５では、図３に示した２階層の画像データについて示している。図５（ａ）を参照して、第２階層の画像データについては、そのすべての画素データが符号化の対象となる。上位の階層の画像データが存在しないからである。図５（ｂ）を参照して、第１階層の画像データは、第２階層の画像データに含まれる画素データをのぞく画素データが符号化の対照となる。例えば、ブロックＡ００に含まれる画素データには、位置「００」、「０１」、「１０」、「１１」があるが、位置「００」の画素データは第２階層の画像データに含まれるので、符号化の対象とはならない。このように、下位の階層において符号化のとなるデータ数を少なくすることにより、圧縮率を向上させることができる。
【００５５】
図６は、３階層の画像データにおいて符号化対象となる画素データを示す図である。図６では、図４に示した３階層の画像データについて示している。図６（ａ）を参照して、第３階層の画像データについては、そのすべての画素データが符号化の対象となる。上位の階層の画像データが存在しないからである。図６（ｂ）を参照して、第２階層の画像データは、第３階層の画像データに含まれる画素データを除く画素データが符号化の対照となる。例えば、ブロックＢ００に含まれる画素データには、位置「００」、「０２」、「２０」、「２２」があるが、位置「００」の画素データは第３階層の画像データに含まれるので、符号化の対象とはならない。図６（ｃ）を参照して、第１階層の画像データは、第２階層および第３階層の画像データに含まれる画素データを除く画素データが符号化の対照となる。例えば、ブロックＡ００に含まれる画素データには、位置「００」、「０１」、「１０」、「１１」があるが、位置「００」の画素データは第２階層の画像データに含まれるので、符号化の対象とはならない。また、ブロックＡ０１に含まれる画素データには、位置「０２」、「０３」、「１２」、「１３」があるが、位置「０２」の画素データは第２階層の画像データに含まれるので、符号化の対象とはならない。このように、下位の階層（例えば第１の階層）の画像データにおいて、符号化の対象となる画素データは、より上位の階層（第２および第３の階層）の画像データに含まれる画素データを含まない。
【００５６】
図７は、本実施の形態における画像変換装置１００の符号化処理部１０４で実行される符号化処理の流れを示すフローチャートである。ここでは説明のため、図２に示した画像データを２階層の画像データで符号化する場合を例に説明する。図７を参照して、符号化処理では、まず、符号化する階層の指定が受付けられる（ステップＳ０１）。階層の指定は、ユーザが指示入力部１０１を操作することにより入力される。ここでは、画像データを２階層で説明することとしたので、ステップＳ０２で指定されるのは２階層である。
【００５７】
そして、符号化するブロックサイズの指定が受付けられる（ステップＳ０２）。ブロックサイズの指定は、ユーザが指示入力部１０１を操作することにより入力される。上述したように、ブロックの１辺の画素数は式（１）、ブロックサイズは式（２）を満たすことが望ましい。ここでは、縦×横が２×２のブロックサイズが指定されたとする。なお、ステップＳ０１またはステップＳ０２において指示がない場合は、プログラム入力部１０２に入力されたプログラムに記憶されている初期設定を用いることとなる。
【００５８】
次に、符号化処理の対象となる画像データが画像入力部、または記憶部１０７から読込まれる（ステップＳ０３）。そして、最上位レベルの階層が設定される（ステップＳ０４）。ステップＳ０４では、ステップＳ０１で指定された階層（２階層）の数だけ、各階層の画像データを、ステップＳ０３で入力された画像データを間引きによる縮小処理を実行することにより生成し、最上位の階層の画像データを処理対象の画像データに設定する。ここでは、ステップＳ０３で入力された画像データが最下位の第１階層の画像データとされる。そして、指定された階層が２階層であるため、第２階層の画像データが生成される。さらに、最上位の第２階層の画像データが処理対象の画像データに設定される。 次に処理対象の画像データにおけるブロックサイズが設定される（ステップＳ０５）。ステップＳ０５では、ステップＳ０２で指定されたブロックサイズに基づき、処理対象の画像データのブロックサイズが設定される。ここでは、図３（ａ）に示した、縦×横が２×２のブロックサイズが設定されることになる。そして、設定されたブロックサイズに基づいて、処理対象の画像データがブロックに分割される（ステップＳ０６）。
【００５９】
次に、分割されたブロックのうち符号化されていないブロックが設定される（ステップＳ０７）。ここでは、図３（ａ）に示した４ブロックＢ００，Ｂ０１，Ｂ１０，Ｂ１１のうちからブロックＢ００が設定されたとする。設定されたブロックの画素データが並替えられ（ステップＳ０８）、並替えられた画素データがＬＺ７７アルゴリズムに従って符号化される（ステップＳ０９）。画素データの並替えは、図５（ａ）に示す矢印の順である。
【００６０】
次のステップＳ１０では、処理対象の画像データに含まれるすべてのブロックについて符号化が終了したかどうかが判定される（ステップＳ１０）。すべてのブロックについての符号化が終了していない場合、それらのブロックのうちいずれかを処理対象のブロックに設定し、設定されたブロックに対してステップＳ０７からステップＳ０９の処理を繰り返し実行する。処理対の画像データのすべてのブロックについてステップＳ０７からステップＳ０９の処理が終了した場合、ステップＳ１１に進む。
【００６１】
ステップＳ１１では、下位の階層の画像データが存在するか否かが判断される。下位の階層の画像データが存在する場合には、その下位の階層の画像データを処理対象の画像データに設定して（ステップＳ１２）、ステップＳ０５〜ステップＳ１０の処理を実行する。下位の階層の画像データが存在しない場合、すなわち、第１階層の画像データについてステップＳ０５〜ステップＳ１０の処理が実行された場合には、処理を終了する。この際、符号化された符号化データは符号化処理部１０４から記憶部１０７へ入力され、記憶される。
【００６２】
記憶部１０７へ記憶される際に、符号化されたデータは、階層毎およびブロック毎に分類されて記憶される。この分類するための情報は、符号化されたデータのヘッダ部分に含まれる。すなわち、このヘッダ部分には、どの階層のどのブロックがどの符号化データに該当するかの情報を含む。したがって、このヘッダ部分の情報を得ることにより、任意の階層の任意のブロックの符号化データのみを得ることができる。
【００６３】
第１階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。これは、ステップＳ０２で指定されたブロックサイズである。また、ステップＳ０９における符号化においては、第１階層の画像データに含まれる画素データは符号化の対象とされない。また、ステップＳ０８における並替えは、図５（ｂ）の矢印で示す順に並替えられる。
【００６４】
画像データを３階層の画像データとして符号化する場合は、ステップＳ０５からステップＳ１１までの処理が、第３階層の画像データから第２階層、第１階層の画像データの順に、それぞれの階層の画像データに対して繰り返し実行される。
【００６５】
第３階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。そして、ステップＳ０９における符号化においては、第３階層の画像データに含まれるすべての画素データが対象となる。また、ステップＳ０８における並替えは、図６（ｃ）の矢印で示す順に並替えられる。
【００６６】
第２階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。そして、ステップＳ０９における符号化においては、第３階層の画像データに含まれる画素データは対象とならない。また、ステップＳ０８における並替えは、図６（ｂ）の矢印で示す順に並替えられる。
【００６７】
第１階層の画像データが処理対象とされた場合、ステップＳ０５におけるブロックサイズは、縦×横が２×２となる。そして、ステップＳ０９における符号化においては、第２階層および３階層の画像データに含まれる画素データは対象とならない。また、ステップＳ０８における並替えは、図６（ａ）の矢印で示す順に並替えられる。
【００６８】
以上説明したように本実施の形態における画像変換装置１００は、下位階層の画像データを符号化する際に、既に符号化された上位階層の画像データを重複して符号化することがない。このため、符号化する画素データは、入力された画像データ、すなわち最下位の画像データ（第１階層の画像データ）の画素数から増加することはない。より具体的には、図５（ｂ）を参照して、最下位の第１階層の画像データは、元の画像データの４分の３の画素データからなる。このため、符号化の対象となる画素データ数を少なくすることで、圧縮容量を削減することができる。
【００６９】
また、２次元に配列された画素データを１次元に並替える順番は、各階層の画像データにおいて隣接する画素の順番とするので、類似した系列の画素が連続するようになる。これにより、ＬＺ７７のような可変長の記号列を固定長もしくは可変長の符号語に変換する手法において、より長い可変長の記号列を固定長もしくは可変長の符号語に変換することができる。即ち、最長一致系列を検索するような辞書に基づく符号化方式によって効率良く符号化されるので、圧縮容量を削減することができる。
【００７０】
図８は、本実施の形態における画像変換装置１００の復号処理部１０５で実行される復号処理の流れを示すフローチャートである。復号処理部１０５は、復号処理プログラムがプログラム入力部１０２から復号処理部１０５へ入力される。復号処理プログラムは、外部記憶装置１１２、または、ネットワークインターフェース１０９から入力される。また、記憶部１０７に記憶しておくようにしても良い。
【００７１】
図８を参照して、復号処理ははじめに復号したい階層レベルの指定が受付けられる（ステップＳ２１）。階層レベルとは、復号の対象となる画像の解像度に対応する階層を示す。階層レベルと解像度との関係を、符号化データのヘッダ部に記憶しておくようにすれば、そのヘッダ部を読取り、画像出力部１０６からディスプレイ１１０に表示することにより、ユーザに知らせることができる。また、ユーザが解像度を指定することにより、ヘッダ部に記憶された情報を基にして階層レベルを決定するようにしてもよい。
【００７２】
次に復号の対象となる領域の指定が受付けられる（ステップＳ２２）。階層レベルの指定および復号対象領域の指定は、ユーザが指示入力部１０１を操作することにより入力される。復号対象領域は、符号化の際に処理単位とされたブロック単位でもよいし、複数のブロックを含んでもよい。
【００７３】
次に指定された階層レベルおよび領域に対応する符号化データが読込まれる（ステップＳ２３）。指定された階層レベルおよび領域に対応する符号化データは、符号化データのヘッダ部に含まれる情報から特定される。また、指定された階層レベルおよび領域に対応する符号化データは、指定された階層レベルの指定された領域に含まれるブロックに対応する符号化データに加えて、そのブロックを含む上位の階層の画像データのブロックに対応する符号化データも含まれる。より具体的には、３階層の画像データで符号化されたデータについて図６を用いて説明すると、指定された階層レベルが第１階層、指定された領域がブロックＡ００とすると、読出される符号化データは、ブロックＡ００の画素データを符号化した符号化データに加えて、ブロックＡ００を含む第２階層の画像データのブロックＢ００および第１階層の画像データのブロックＣ００の画素データを符号化した符号化データが含まれる。以下、これらの符号化データが読込まれた場合を例に説明する。
【００７４】
次に、最上位の階層の符号化データが処理対象データに設定される（ステップＳ２４）。
【００７５】
次のステップＳ２５では、設定された処理対象データのうち復号されていないブロックが設定される。そして、設定されたブロックの符号化データが復号される（ステップＳ２６）。この符号化データは復号されることにより１次元に配列された画素データが得られる。ステップＳ２６では、復号された画素データが、階層レベルが最下位の第１階層の画像データに含まれるブロックの画素位置にそれぞれ割当てらる。これにより、１次元に配列された画素データが２次元に配列されることになる。
【００７６】
そして、ステップＳ２７では、設定された処理対象データのすべてのブロックについて復号されたか否かが判断され、真の場合にはステップＳ２８に進み、偽の場合にはステップＳ２５に進む。すなわち、設定された処理対象データのすべてのブロックについて復号されるまで、ステップＳ２５とステップＳ２６とが繰返し実行される。
【００７７】
次に、復号されたブロックの画像が結合される（ステップＳ２８）。処理対象の符号化データが複数のブロックからなる場合に実行される処理である。ブロックを結合するための情報、すなわちブロックの位置情報は、符号化データのヘッダ部に記憶されているため、この情報を参照して結合される。位置情報は、例えば、Ａ００、Ａ０１などの行列で表現することができる。
【００７８】
そして、復号されたブロックの画像が結合された画像を、上位の階層の復号された画像で補間する。ステップＳ２４では、最上位の階層の符号化データが、第３階層の画像データを符号化したデータが該当し、ステップＳ２５〜ステップＳ２８までの処理が実行されると、図６（ａ）に示した画像データが復号される。この場合に、ステップＳ２９においては、第３階層の画像データより上位の階層が存在しないため、何も実行しない。
【００７９】
次のステップＳ３０では、指定された階層レベルまで復号されたか否かが判断され、真の場合には処理を終了し、偽の場合にはステップＳ３１に進む。復号された画像データは復号処理部１０５から画像出力部１０６または、記憶部１０７に出力される。
【００８０】
ステップＳ３１では、処理対象の符号化データを次に下位の階層の符号化データに設定し、ステップＳ２５に進む。第２階層の符号化データ、より具体的には、第２階層の画像データのブロックＢ００を符号化したデータが処理対象データとされ、ステップＳ２７において、図６（ｂ）に示したブロックＢ００の画素データが復号される。ブロックＢ００には、位置「００」の画素データが含まれないため、ステップＳ２９において、上位の階層の画像データの位置「００」の画素データが補間される。これにより、補間された画像データは、位置「００」、「０２」、「２０」および「２２」の画素データを含むことになる。
【００８１】
さらに、ステップＳ３１において、第３階層の符号化データ、より具体的には、第３階層の画像データのブロックＡ００を符号化したデータが処理対象データとされ、ステップＳ２７において、図６（ｃ）に示したブロックＡ００の画素データが復号される。ブロックＡ００には、位置「００」の画素データが含まれないため、ステップＳ２９において、上位の階層の画像データの位置「００」の画素データが補間される。これにより、補間された画像データは、位置「００」、「０１」、「１０」「１１」の画素データを含むことになる。なお、上述の処理で、位置「０２」、「２０」および「２２」の画素データが復号されたが、指定された領域に含まれないため利用する必要はない。
【００８２】
以上説明したように、本実施の形態における画像変換装置１００では、符号化された画像データをブロック単位で復号するため、画像データの局所的な領域だけを復号することができる。また、不要な領域を復号することがないので、復号処理の処理速度を速くすることができる。
【００８３】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【図１】 本発明の実施の形態の１つにおける画像変換装置の機能の概略を示す機能ブロック図である。
【図２】 画像データを画素の位置を示す符号を付して示した図である。
【図３】 ピラミッド型の２階層の画素データを示す図である。
【図４】 ピラミッド型の３階層の画素データを示す図である。
【図５】 ２階層の画像データにおいて符号化対象となる画素データを示す図である。
【図６】 ３階層の画像データにおいて符号化対象となる画素データを示す図である。
【図７】 本実施の形態における画像変換装置の符号化処理部で実行される符号化処理の流れを示すフローチャートである。
【図８】 本実施の形態における画像変換装置の復号処理部で実行される復号処理の流れを示すフローチャートである。
【符号の説明】
１００ 画像変換装置、１０１ 指示入力部、１０２ プログラム入力部、１０３ 画像入力部、１０４ 符号化処理部、１０５ 復号処理部、１０６ 画像出力装置、１０６ 画像出力部、１０７ 記憶部、１０８ スキャナ、１０９ ネットワークインターフェース、１１０ ディスプレイ、１１１ プリンタ、１１２ 外部記憶装置。
Claims (2)
- 画像データに含まれる画素データの一部を間引いて画像データを縮小することにより解像度が低い、階層レベルが上位の画像データを生成する画像縮小手段と、
階層レベルが上位の画像データから順に処理対象とする処理画像データを選択する選択手段と、
処理対象となる処理画像データを、前記処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割する分割手段と、
前記分割手段により分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データを符号化対象画素データとして復元可能に符号化するための符号化手段と、
２次元に配列された前記符号化対象画素データを予め定められた所定の順序で１次元に配列された画素データに並替える並替手段とを備え、
前記符号化手段は、参照部と符号化部とを備える適応型辞書法に基づく符号化方式を用いて符号化し、
前記並替手段は、前記符号化対象画素データを、２次元に配列された画素位置の横方向に隣接する順に横方向に配列し、該横方向に画素データがなくなると、次の行の画素データを横方向に配列する処理、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列し、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の前記符号化対象画素データがなくなるまで繰り返すことにより１次元に配列し、
前記分割手段は、前記並替手段が１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積を、前記符号化方式の参照部に格納されるデータ数および前記符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割する、画像符号化装置。 - 画像データに含まれる画素データの一部を間引いて画像データを縮小することにより解像度が低い、階層レベルが上位の画像データを生成するステップと、
階層レベルが上位の画像データから順に処理対象とする処理画像データを選択するステップと、
処理対象となる処理画像データを、前記処理画像データより階層レベルが上位の画像データに含まれる画素データを少なくとも１つ含むブロックに分割するステップと、
前記分割ステップにより分割されたブロック毎に、該ブロックに含まれる画素データのうち階層レベルがより上位の画像データに含まれる画素データを除く画素データを符号化対象画素データとして復元可能に符号化するステップと、
２次元に配列された前記符号化対象画素データを予め定められた所定の順序で１次元に配列された画素データに並替えるステップとを含み、
前記符号化するステップは、参照部と符号化部とを備える適応型辞書法に基づく符号化方式を用いて符号化し、
前記並替えるステップは、前記符号化対象画素データを、２次元に配列された画素位置の横方向に隣接する順に横方向に配列し、該横方向に画素データがなくなると、次の行の画素データを横方向に配列する処理、または２次元に配列された画素位置の縦方向に隣接する順に縦方向に配列し、該縦方向に画素データがなくなると、次の列の画素データを縦方向に配列する処理を、ブロック内の前記符号化対象画素データがなくなるまで繰り返すことにより１次元に配列し、
前記分割するステップは、前記並替えるステップが１次元に配列するブロックの横方向の１行内または縦方向の１列内に含まれる画素数と階調を表す画素データのビット数との積を、前記符号化方式の参照部に格納されるデータ数および前記符号化方式の符号化部に格納されるデータ数よりそれぞれ小さいブロックに分割する、画像符号化方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2003007468A JP4133357B2 (ja) | 2003-01-15 | 2003-01-15 | 画像符号化装置および画像符号化方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2003007468A JP4133357B2 (ja) | 2003-01-15 | 2003-01-15 | 画像符号化装置および画像符号化方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2004221986A JP2004221986A (ja) | 2004-08-05 |
| JP4133357B2 true JP4133357B2 (ja) | 2008-08-13 |
Family
ID=32897564
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2003007468A Expired - Fee Related JP4133357B2 (ja) | 2003-01-15 | 2003-01-15 | 画像符号化装置および画像符号化方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP4133357B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4721258B2 (ja) * | 2005-01-11 | 2011-07-13 | 株式会社リコー | 画像処理装置、画像処理方法、プログラム及び情報記録媒体 |
| US8103111B2 (en) * | 2006-12-26 | 2012-01-24 | Olympus Imaging Corp. | Coding method, electronic camera, recording medium storing coded program, and decoding method |
-
2003
- 2003-01-15 JP JP2003007468A patent/JP4133357B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2004221986A (ja) | 2004-08-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4480119B2 (ja) | 画像処理装置及び画像処理方法 | |
| US6031938A (en) | Image encoding apparatus with selective Markov and predictive coding | |
| US6614939B1 (en) | Image compression apparatus and decoding apparatus suited to lossless image compression | |
| JPH11163733A (ja) | 符号化方法および装置 | |
| US6020923A (en) | Method and apparatus for coding and recording an image signal and recording medium for storing an image signal | |
| CN115297218B (zh) | 基于哈夫曼编码规则和位置图压缩的可逆数据隐藏方法 | |
| JP2002034043A (ja) | 符号化装置及び符号化方法並びに記憶媒体 | |
| JP2009290552A (ja) | 動画圧縮装置および動画圧縮プログラム | |
| JP4133357B2 (ja) | 画像符号化装置および画像符号化方法 | |
| TW200531456A (en) | Repetition coded compression for encrypting highly correlated data | |
| JP3201448B2 (ja) | 符号化復号化装置，符号化装置，および復号化装置 | |
| WO2001050769A1 (en) | Method and apparatus for video compression using multi-state dynamical predictive systems | |
| JP2002190956A (ja) | 画像符号化装置および画像復号装置 | |
| JP2005124001A (ja) | 動画像符号化装置、動画像符号化方法、動画像符号化プログラム、動画像復号装置、動画像復号方法、及び動画像復号プログラム | |
| JP4633576B2 (ja) | データ圧縮装置およびデータ圧縮プログラム | |
| JP3676078B2 (ja) | ランレングス符号化方法及び圧縮装置 | |
| JP4462360B2 (ja) | 画像圧縮装置および画像伸張装置 | |
| JP4173498B2 (ja) | データ圧縮装置およびデータ圧縮プログラム | |
| JPH07274006A (ja) | 画像処理装置及びスキャナ装置及びプリンタ装置及びディジタル複写機及びディスプレイ装置 | |
| Renji et al. | A reversible data hiding technique for secure image transmission | |
| JP3990949B2 (ja) | 画像符号化装置及び画像符号化方法 | |
| JP2005295307A (ja) | 画像圧縮方法、画像圧縮装置、画像伸張装置、およびプログラム | |
| JP4696738B2 (ja) | 画像データの圧縮方法および装置並びに擬似階調画像の復元方法 | |
| JP4633577B2 (ja) | データ圧縮装置およびデータ圧縮プログラム | |
| JP4741317B2 (ja) | データ圧縮装置およびデータ圧縮プログラム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050810 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20070622 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070904 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20071102 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20080507 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20080602 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110606 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120606 Year of fee payment: 4 |
|
| LAPS | Cancellation because of no payment of annual fees |