(57)【要約】【課題】多値画像データに対して、高能率な予測符号化装置、予測符号化方法、及びその記憶媒体を提供することを目的としている。【解決手段】周辺画素を用いて符号化画素を予測する予測符号化であって、周辺画素の画素値と重み係数を用いて予測を行う予測変換手段と、前記重み係数を画素値と予測値の大小関係によって更新する重み係数更新手段と、画像データの走査順を変換する走査変換手段とを備え、前記走査変換手段によって変換された走査順に前記予測変換手段による予測及び、前記重み係数更新手段による重み係数の更新を行うようにしたので、予測に用いる重み係数をラスター走査順ではなく、画像のもつ２次元的な相関の強いデータ順に更新することができ、画像に適した予測を適応的に行うことができ、高能率な予測符号化装置が得られる。【選択図】  図２
2004229196.tif 000002
【特許請求の範囲】
【請求項１】
周辺画素を用いて符号化画素を予測する予測符号化であって、周辺画素の画素値と重み係数を用いて予測を行う予測変換手段と、前記重み係数を画素値と予測値の大小関係によって更新する重み係数更新手段と、画像データの走査順を変換する走査変換手段とを備え、前記走査変換手段によって変換された走査順に前記予測変換手段による予測及び、前記重み係数更新手段による重み係数の更新を行うことを特徴とする予測符号化装置。
【請求項２】
前記重み係数更新手段における重み係数の更新は、予測値と画素値の差分値に応じて更新幅を変更して更新することを特徴とする予測符号化装置。
【請求項３】
周辺画素を用いて符号化画素を予測する予測符号化であって、周辺画素の画素値と重み係数を用いて予測を行う予測変換ステップと、前記重み係数を画素値と予測値の大小関係によって更新する重み係数更新ステップと、画像データの走査順を変換する走査変換ステップとを有し、前記走査変換ステップによって変換された走査順に前記予測変換ステップによる予測及び、前記重み係数更新ステップによる重み係数の更新を行うことを特徴とする予測符号化方法。
【請求項４】
前記重み係数更新ステップにおける重み係数の更新は、予測値と画素値の差分値に応じて更新幅を変更して更新することを特徴とする予測符号化方法。
【請求項５】
請求項３または４記載の予測符号化方法を記述した制御プログラムを記憶した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像データを高能率に圧縮伸長する予測符号化方法及び予測符号化装置に関するものである。
【０００２】
【従来の技術】
プリンタ、スキャナ、複写機、ファクシミリ等の高解像度化、カラー化に伴って、プリンタ、スキャナ等のデータ入出力装置、データ蓄積装置、ネットワーク通信装置などの記憶容量、伝送時間削減のためのデータ圧縮技術が重要となってきている。特に医療画像、リモートセンシング、歴史的文化財のデジタルアーカイビング等の分野においては画質劣化のない可逆圧縮技術が重要である。
【０００３】
多値画像の可逆圧縮としては、予測符号化が主流であり、予測符号化は符号化画素周辺の参照画素を用いて符号化画素値の予測を行う。そして予測した値と実際の画素値の差分である予測誤差を出力し、予測誤差信号に対して周辺画素の状態（コンテクスト）に応じて分離し、それぞれに最適なエントロピー符号化を適用する（例えば非特許文献１参照）。ＪＰＥＧ−ＬＳなどの国際標準化方式においても予測符号化をベースに圧縮を行っている（例えば非特許文献２参照）。
【０００４】
以下に多値画像の予測符号化技術に対する従来の手法を説明する。図９は従来の予測符号化装置の構成図、図１０は従来の予測符号化装置のブロック図、図１１は予測符号化に用いる参照画素の説明図である。図９において９０１は制御手段、９０２は入力手段、９０３は予測符号化における予測変換により予測誤差信号を出力する予測変換手段、９０４は符号化画素周辺の画素の状態（コンテクスト）を検知するコンテクスト検出手段、９０５はコンテクスト検出手段によって決定されたコンテクストに応じて予測変換手段による予測誤差信号を符号化するエントロピー符号化手段、９０６は出力手段、９０７は記憶手段である。以上のように構成された予測符号化装置について図１０のブロック図を用いて処理の流れを説明する。制御手段９０１は入力手段９０２から入力データである多値画像を受け取り、記憶手段９０７に記憶する。次に予測変換手段９０３は記憶手段９０７に記憶された入力データに対して予測変換を行う。予測変換においては周辺画素を用いて対象となる画素の値を予測し、対象となる画素の値と予測値の差分である予測誤差信号を出力する（Ｓ１００１）。次に、コンテクスト検出手段９０４は周辺画素の値を用いて対象画素のコンテクストを検出する（Ｓ１００２）。そして、エントロピー符号化手段９０５ではコンテクスト検出手段９０４によって決定されたコンテクストに応じて最適なエントロピー符号化を予測誤差信号に対して行う（Ｓ１００３）。最後に、出力手段９０６から符号化データが出力される。また、これらの動作は記憶手段９０７に記憶された制御プログラムによって制御される場合もある。
【０００５】
ここで、予測変換手段９０３は周辺画素の値を用いて符号化画素の値を予測するが、予測の方法としては以下に示すＪＰＥＧ  Ｓｐａｔｉａｌ方式に規定された７つの予測式（数１）や、ＪＰＥＧ−ＬＳに規定された予測式（数２）が考えられる。また、以下のように周辺画素と重み係数による線形予測式（数３）も考えられる。この場合、重み係数は予測値と画素値の大小関係に応じて適応的に更新される。そして、得られた予測値と符号化画素値の差分である予測誤差を出力する。ここで、各予測式の示す値は図１１に示す周辺参照画素の画素値であり、ｘは符号化画素ｘの予測値である。また参照画素は図１１に示す画素に限定するものでないことはいうまでもない。
【０００６】
【数１】
2004229196.tif 000003
【０００７】
【数２】
2004229196.tif 000004
【０００８】
【数３】
2004229196.tif 000005
【０００９】
また、コンテクスト検出手段９０４は周辺画素の値を用いて符号化画素のコンテクストを決定する。決定方法としては周辺画素の濃度勾配、エッジの状態などによって決定される。例えば（数４）のように周辺画素のいくつかの差分値を求め、その値を線形あるいは非線形に量子化することにより得られた値によってコンテクストを決定する。あるいは周辺の予測誤差を用いて決定する場合も考えられる。
【００１０】
【数４】
2004229196.tif 000006
【００１１】
また、エントロピー符号化手段９０５は予測変換手段９０３によって得られた予測誤差信号に対して、コンテクスト検出手段９０４で得られたコンテクストに応じて最適なエントロピー符号化を適用する。エントロピー符号化としてはハフマン符号化や算術符号化あるいはＧｏｌｏｍｂ符号化等が考えられる。また、その際コンテクストごとに最適な符号化を適用することになるが、その方法としては、テーブルを切り換えたり、パラメータを切り換えたりする方法が考えられる。
【００１２】
【非特許文献１】
Ｎ．Ｍｅｍｏｎ，Ｘ．Ｗｕ，“Ｒｅｃｅｎｔ  Ｄｅｖｅｌｏｐｍｅｎｔｓ  ｉｎ  Ｃｏｎｔｅｘｔ−Ｂａｓｅｄ  Ｐｒｅｄｉｃｔｉｖｅ  Ｔｅｃｈｎｉｑｕｅｓ  ｆｏｒ  Ｌｏｓｓｌｅｓｓ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ”，Ｔｈｅ  Ｃｏｍｐｕｔｅｒ  Ｊｏｕｒｎａｌ，Ｖｏｌ．４０，Ｎｏ．２／３，１９９７，ｐｐ．１２７−１３６．
【非特許文献２】
上野幾朗，梶尾浩，望月孝志，小野文孝，“多値ロスレス符号化技術の最新動向”，画像電子学会誌，Ｖｏｌ．２７，Ｎｏ．４，１９９８，ｐｐ．４０５−４１２．
【００１３】
【発明が解決しようとする課題】
しかしながら、上記従来の方法では、ラスター走査順に予測変換を行って予測符号化を行うため、画像データがもつ２次元的な冗長度を十分に削除した効率的な予測符号化装置を得ることが困難であるという問題点を有していた。
【００１４】
本発明は上記従来の問題点を解決するもので、高能率な予測符号化装置を提供することを目的としている。
【００１５】
【課題を解決するための手段】
上記課題を解決するために、本発明は画像データを近傍保存性の高いデータ走査順に変換し、変換された走査順に予測変換及び予測に用いる重み係数の更新を行うようにしたもので、この方法により、画像の２次元的な相関を用いて十分に冗長性を削除することができ、高能率の予測符号化装置が得られる。
【００１６】
【発明の実施の形態】
本発明の請求項１に記載の発明は、周辺画素を用いて符号化画素を予測する予測符号化であって、周辺画素の画素値と重み係数を用いて予測を行う予測変換手段と、重み係数を画素値と予測値の大小関係によって更新する重み係数更新手段と、画像データの走査順を変換する走査変換手段とを備え、走査変換手段によって変換された走査順に予測変換手段による予測及び、重み係数更新手段による重み係数の更新を行うことを特徴とする予測符号化装置で、予測に用いる重み係数をラスター走査順ではなく、画像のもつ２次元的な相関の強いデータ順に更新することができるので、高能率な予測符号化を行うことができるという作用を有する。
【００１７】
請求項２に記載の発明は、重み係数更新手段における重み係数の更新は、予測値と画素値の差分値に応じて更新幅を変更して更新することを特徴とする予測符号化装置で、予測値と画素値の差分が大きい場合は更新幅を大きくし、予測値と画素値の差分が小さい場合は更新幅を小さくして重み係数を更新することができ、画像のもつ局所的な性質により速く適応することができるので、高能率な予測符号化を行うことができるという作用を有する。
【００１８】
請求項３に記載の発明は、周辺画素を用いて符号化画素を予測する予測符号化であって、周辺画素の画素値と重み係数を用いて予測を行う予測変換ステップと、重み係数を画素値と予測値の大小関係によって更新する重み係数更新ステップと、画像データの走査順を変換する走査変換ステップとを有し、走査変換ステップによって変換された走査順に予測変換ステップによる予測及び、重み係数更新ステップによる重み係数の更新を行うことを特徴とする予測符号化方法で、予測に用いる重み係数をラスター走査順ではなく、画像のもつ２次元的な相関の強いデータ順に更新することができるので、高能率な予測符号化を行うことができるという作用を有する。
【００１９】
請求項４に記載の発明は、重み係数更新ステップにおける重み係数の更新は、予測値と画素値の差分値に応じて更新幅を変更して更新することを特徴とする予測符号化方法で、予測値と画素値の差分が大きい場合は更新幅を大きくし、予測値と画素値の差分が小さい場合は更新幅を小さくして重み係数を更新することができ、画像のもつ局所的な性質により速く適応することができるので、高能率な予測符号化を行うことができるという作用を有する。
【００２０】
（実施の形態１）
以下、本発明の実施の形態１について説明する。図１は本発明の実施の形態１における予測符号化装置を実現するための構成図を、図２は本発明の実施の形態１における予測符号化装置を実現するためのブロック図を表している。
【００２１】
図１において１０１は画像データに施す処理を制御する制御手段、１０２は多値画像データの入力手段、１０３は予測変換及び重み係数の更新を行う順番をラスター走査から近傍保存性の高い走査順に変換する走査変換手段、１０４は重み係数を用いた予測符号化による予測変換により予測誤差信号を出力する予測変換手段、１０５は予測変換に用いる重み係数の値を更新する重み係数更新手段、１０６は符号化画素周辺の画素の状態（コンテクスト）を検知するコンテクスト検出手段、１０７はコンテクスト検出手段によって決定されたコンテクストに応じて予測変換変換による予測誤差信号を符号化するエントロピー符号化手段、１０８は符号化データの出力手段、１０９は制御プログラムや画像データを記憶する記憶手段である。
【００２２】
以上のように構成された予測符号化装置について、以下図２のブロック図を用いて処理の流れを説明する。最初に制御手段１０１は入力手段１０２から入力画像である多値画像データを受け取り、記憶手段１０９に記憶する。次に、走査変換手段１０３は、記憶手段１０９に記憶された多値画像データに対して予測変換及び予測変換に用いる重み係数の更新を行う順番を変換するために走査変換を行う（Ｓ２０１）。そして、予測変換手段１０４は走査変換されて順番に（数３）による重み係数を用いた予測変換を行い、予測値と符号化画素の差分である予測誤差信号を出力する（Ｓ２０２）。その後、重み係数更新手段１０５では予測値と符号化画素値の大小関係に応じて重み係数の更新を行う（Ｓ２０３）。一方、コンテクスト検出手段１０６は符号化画素周辺の参照画素を用いて（数４）を用いて符号化画素のコンテクストを決定する（Ｓ２０４）。そして、エントロピー符号化手段１０７では予測変換手段１０４によって出力された予測誤差信号に対してコンテクスト検出手段１０６によって決定されたコンテクストに最適なエントロピー符号化を行う（Ｓ２０５）。最後に出力手段１０８から符号化データが出力される。また、これらの動作は記憶手段１０９に記憶された制御プログラムによって制御される場合もある。
【００２３】
走査変換手段１０３は、入力された多値画像データに対して、予測変換及び予測に用いる重み係数を更新するための順番を、ラスター走査順から近傍保存性の高い走査順に変換する。近傍保存性の高い走査データとしては図３（ａ）に示すブロックヒルベルト走査の例示図がある。しかし、この走査を用いて走査変換を行った場合、（数３）による重み係数を用いた予測符号化を行って復号化する際に、復号化画素周辺の参照画素がないという問題が発生する。そこで、図３（ｂ）に示すようなブロックラスター走査の例示図を用いて変換すると都合が良い。しかし、走査方法はこのような方法に限ったものではなく、予測変換方法と走査方法の整合性がとれれば何れの走査を用いても構わない。
【００２４】
重み係数更新手段１０５は、予測値と符号化画素値の大小関係によって予測変換に用いる重み係数を更新する。更新方法としては図４に示すような方法が考えられる。図４（ａ）は重み係数の更新規則の例示図（更新幅固定）であり、予測値が符号化画素値より小さい場合は参照画素のうち最大値をもつ参照画素の重み係数に１／２５６を加え、参照画素のうち最小値をもつ参照画素の重み係数から１／２５６を引く。一方、予測値が符号化画素値より大きい場合は参照画素のうち最大値をもつ参照画素の重み係数から１／２５６を引き、参照画素のうち最小値をもつ参照画素の重み係数に１／２５６を加える。また、図４（ｂ）は重み係数の更新規則の例示図（更新幅可変）であり、予測値と符号化画素値の差分αの大きさに応じて更新幅をα／２５６に調整する。その他、領域ごとあるいは過去のデータ系列における予測誤差信号の出現頻度等に応じて更新幅を変えるなどの方法も考えられる。
【００２５】
図５は本発明の実施の形態１における予測符号化装置を実現するためのハードウェア構成図、図６は本発明の実施の形態１における予測符号化装置を実現するためのハードウェア構成図を表している。図５において５０１は外部記憶装置、５０２は中央演算処理装置（以下「ＣＰＵ」と略称する）、５０３はリードオンリーメモリ（以下「ＲＯＭ」と略称する）、５０４はランダムアクセスメモリ（以下「ＲＡＭ」と略称する）でそれぞれがバス結合されている。ＲＯＭ５０３内にはプログラムの記憶領域があり、ＲＡＭ５０４内には画像記憶領域がある。図５は組込み機器のハードウェア構成図であるが、汎用機器で本実施の形態を実現する場合は図６に示すように外部記憶装置６０１内にプログラムの記憶領域がある場合もある。ここで、外部記憶装置としてはハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ等がある。また、外部記憶装置はネットワーク等によって接続されている場合もある。
【００２６】
図７は本発明の実施の形態１における予測符号化方法を実現するためのフローチャートを表している。以下に図７を用いて処理の流れを説明する。
【００２７】
図７において外部記憶装置５０１等に記憶されている画像データがＲＡＭ５０４の画像記憶領域に入力された後、（Ｓ７０１）では画素番号を０に初期化する。次に（Ｓ７０２）では予測変換及び重み係数の更新を近傍保存性の高い走査順に行うために走査順の変換を行う。そして（Ｓ７０３）では符号化画素周辺の参照画素を用いて予測変換を行い予測値を求める。そして、（Ｓ７０４）では予測値と画素値の差分値である予測誤差信号αを求める。次に（Ｓ７０５）では予測値と画素値の大小関係を求め、予測値が大きい場合は（Ｓ７０６）に、画素値が大きい場合は（Ｓ７１０）に進む。（Ｓ７０６）では参照画素のうち最大値の画素を検出し、（Ｓ７０７）では検出された画素の重み係数をα／２５６デクリメントする。また、（Ｓ７０８）では参照画素のうち最小値の画素を検出し、（Ｓ７０９）では検出された画素の重み係数をα／２５６インクリメントする。一方、（Ｓ７１０）では参照画素のうち最大値の画素の検出し、（Ｓ７１１）では検出された画素の重み係数をα／２５６インクリメントする。また、（Ｓ７１２）では参照画素のうち最小値の画素を検出し、（Ｓ７１３）では検出された画素の重み係数をα／２５６デクリメントする。そして（Ｓ７１４）では周辺画素の値を用いてコンテクストを求め、求めたコンテクストに応じて（Ｓ７１５）では予測誤差信号をエントロピー符号化する。最後に（Ｓ７１６）では画素数と画素番号の比較を行い、全ての画素の処理が終わったら終了し、終わっていない場合は（Ｓ７０２）に戻って（Ｓ７０２）から（Ｓ７１６）までの処理を繰り返す。また、エントロピー符号化された符号化データは外部記憶装置５０１等に記憶されるか、ネットワークを介して外部に送信される。また、上述の処理はＣＰＵ５０２を用いて行う。
【００２８】
また、図８は、本発明の実施の形態１における各種データ処理プログラムを格納する記憶媒体のメモリマップの説明図である。
【００２９】
なお、特に図示しないが、記憶媒体に記憶されるプログラム群を管理する情報、例えばバージョン情報、作成者等も記憶され、かつ、プログラム読み出し側のＯＳ等に依存する情報、例えばプログラムを識別表示するアイコン等も記憶される場合もある。
【００３０】
さらに、各種プログラムに従属するデータも上記ディレクトリに管理されている。また、各種プログラムをコンピュータにインストールするためのプログラムや、インストールするプログラムが圧縮されている場合に、解凍するプログラム等も記憶される場合もある。
【００３１】
実施の形態１における図７に示す機能が外部からインストールされるプログラムによって、ホストコンピュータにより遂行されていてもよい。そして、その場合、ＣＤ−ＲＯＭやフラッシュメモリやＦＤ等の記憶媒体により、あるいはネットワークを介して外部の記憶媒体から、プログラムを含む情報群を出力装置に供給される場合でも本発明は適用されるものである。
【００３２】
以上のように、前述した実施の形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、本発明の目的が達成されることは言うまでもない。
【００３３】
この場合、記憶媒体から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００３４】
プログラムコードを供給するための記憶媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭ、ＥＥＰＲＯＭ等を用いることができる。
【００３５】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施の形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実施される場合も含まれることは言うまでもない。
【００３６】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部または全部を行い、その処理によって前述した実施の形態の機能が実現される場合も含まれることは言うまでもない。
【００３７】
【発明の効果】
以上のように本発明によれば、周辺画素を用いて符号化画素を予測する予測符号化であって、周辺画素の画素値と重み係数を用いて予測を行う予測変換手段と、前記重み係数を画素値と予測値の大小関係によって更新する重み係数更新手段と、画像データの走査順を変換する走査変換手段とを備え、前記走査変換手段によって変換された走査順に前記予測変換手段による予測及び、前記重み係数更新手段による重み係数の更新を行うようにしたので、予測に用いる重み係数をラスター走査順ではなく、画像のもつ２次元的な相関の強いデータ順に更新することができ、画像に適した予測を適応的に行うことができ、高能率な予測符号化装置を実現することができる。
【００３８】
また、前記重み係数更新手段における重み係数の更新は、予測値と画素値の差分値に応じて更新幅を変更して更新するようにしたので、予測値と画素値の差分が大きい場合は更新幅を大きくし、予測値と画素値の差分が小さい場合は更新幅を小さくして重み係数を更新することができ、画像のもつ局所的な性質により速く適応することができるので、高能率な予測符号化装置を実現することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態１における予測符号化装置を実現するための構成図
【図２】本発明の実施の形態１における予測符号化装置を実現するためのブロック図
【図３】（ａ）ブロックヒルベルト走査の例示図
（ｂ）ブロックラスター走査の例示図
【図４】（ａ）重み係数の更新規則の例示図（更新幅固定）
（ｂ）重み係数の更新規則の例示図（更新幅可変）
【図５】本発明の実施の形態１における予測符号化装置を実現するためのハードウェア構成図
【図６】本発明の実施の形態１における予測符号化装置を実現するためのハードウェア構成図
【図７】本発明の実施の形態１における予測符号化方法を実現するためのフローチャート
【図８】本発明の実施の形態１における各種データ処理プログラムを格納する記憶媒体のメモリマップの説明図
【図９】従来の予測符号化装置の構成図
【図１０】従来の予測符号化装置のブロック図
【図１１】予測符号化に用いる参照画素の説明図
【符号の説明】
１０１  制御手段
１０２  入力手段
１０３  走査変換手段
１０４  予測変換手段
１０５  重み係数更新手段
１０６  コンテクスト検出手段
１０７  エントロピー符号化手段
１０８  出力手段
１０９  記憶手段
５０１  外部記憶装置
５０２  中央演算処理装置（ＣＰＵ）
５０３  リードオンリーメモリ（ＲＯＭ）
５０４  ランダムアクセスメモリ（ＲＡＭ）
６０１  外部記憶装置
６０２  中央演算処理装置
６０３  リードオンリーメモリ（ＲＯＭ）
６０４  ランダムアクセスメモリ（ＲＡＭ）
９０１  制御手段
９０２  入力手段
９０３  予測変換手段
９０４  コンテクスト検出手段
９０５  エントロピー符号化手段
９０６  出力手段
９０７  記憶手段
【図１】
2004229196.tif 000007
【図２】
2004229196.tif 000008
【図３】
2004229196.tif 000009
【図４】
2004229196.tif 000010
【図５】
2004229196.tif 000011
【図６】
2004229196.tif 000012
【図７】
2004229196.tif 000013
【図８】
2004229196.tif 000014
【図９】
2004229196.tif 000015
【図１０】
2004229196.tif 000016
【図１１】
2004229196.tif 000017