(57)【特許請求の範囲】
【請求項１】
画像に可逆符号化を行う画像符号化装置において、
画像を入力する画像入力手段と、
前記画像入力手段から入力した画像に対して注目画素の画素値を予測する複数の画素値予測手段と、
前記画像入力手段から入力した画像に対して注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する予測誤差算出手段と、
前記画素値予測手段のいずれかの予測値と実際の画素値が一致する場合には一致した１つの画素値予測手段の識別情報を、そうでない場合には１つの前記予測誤差算出手段で算出された予測誤差を選択する選択手段と、
前記選択手段で選択された画素予測手段の識別情報またはそのランレングス表現および予測誤差を含んで成る中間コードを生成する中間コード生成手段と、
前記中間コード生成手段により生成された中間コードを格納する中間コード記憶手段と、
上書き、つなぎ合わせ、および重ね合わせのうちの少なくとも１つを含む編集処理により複数の画像情報から合成されるべき１つの合成画像情報に対して、当該１つの合成画像情報に対応する１つの中間コードを生成するために、当該複数の画像情報について前記中間コード生成手段によりそれぞれ生成され前記中間コード記憶手段に記憶されている複数の中間コードを、前記上書き、つなぎ合わせ、または重ね合わせに応じて前記１つの中間コードに合成する中間コード編集手段と、
前記中間コード記憶手段に記憶された編集後の前記中間コードを、所定の手法で符号化する符号化手段と、
前記符号化手段で作成した符号を出力する符号出力手段とから構成されることを特徴とする画像符号化装置。
【請求項２】
前記複数の画像情報に対して実行したい編集は、複数画像をつなぎ合わせる処理であることを特徴とする請求項１に記載の画像符号化装置。
【請求項３】
前記複数の画像情報に対して実行したい編集は、前記複数の画像情報のうちの１つの画像情報に前記複数の画像情報のうちの他の画像情報を上書き合成する処理であることを特徴とする請求項１に記載の画像符号化装置。
【請求項４】
さらに前記中間コードに含まれる同一符号のランを計算するラン計算手段を備え、前記中間コードに含まれる符号の少なくともひとつはランレングス符号化されることを特徴とする請求項１ないし３のいずれかに記載の画像符号化装置。
【請求項５】
前記中間コードに含まれる情報は直上画素による予測結果と直左画素による予測結果と予測誤差とからなることを特徴とする請求項１ないし４のいずれかに記載の画像符号化装置。
【請求項６】
実装されている画素値予測手段の他に仮想的な画素値予測手段を設定し、先行する目標画素に関して予測が的中して中間コードとして採用された実装されている画素値予測手段の予測用画素位置と上記先行する目標画素の画素位置との関係が、現時点での当該実装されている画素値予測手段の予測用画素位置と上記仮想的な画素値予測手段の予測用画素位置との関係に対応するときに、上記先行する目標画素に関して予測が的中して採用された中間コードに基づいて上記当該実装されている画素値予測手段の予測値と上記仮想的な画素値予測手段の予測値とが等しいと判断して、上記仮想的な画素値予測手段が的中したことを示す中間コードを採用できるようにしたことを特徴とする請求項１ないし５のいずれかに記載の画像符号化装置。
【請求項７】
前記中間コードに含まれる前記画素値予測手段の識別情報は、前記複数の画素値予測手段の予測ヒットの履歴を用いて算出される予測順位によって表現されることを特徴とした請求項１ないし６のいずれかに記載の画像符号化装置。
【請求項８】
前記中間コードに含まれる前記画素値予測手段の識別情報は、最近に使われた前記画素値予測手段を１位としそれ以外は所定の優先順に順位づけする予測順位によって表現されることを特徴とした請求項１ないし６のいずれかに記載の画像符号化装置。
【請求項９】
画像を入力する画像入力手段と、
前記画像入力手段から入力した画像に対して注目画素の画素値を予測する少なくとも１つの画素値予測手段と、
前記画像入力手段から入力した画像に対して注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する少なくとも１つの予測誤差算出手段と、
前記画素値予測手段のいずれかの予測値と実際の画素値とが対応する場合には当該対応する１つの画素値予測手段の識別情報を、そうでない場合には１つの前記予測誤差算出手段で算出された１つの予測誤差を選択する選択手段と、
前記選択手段で選択された画素予測手段の識別情報またはそのランレングス表現および予測誤差を含んで成る中間コードを生成する中間コード生成手段と、
前記中間コード生成手段により生成された中間コードを格納する中間コード記憶手段と、
上書き、つなぎ合わせ、および重ね合わせのうちの少なくとも１つを含む編集処理により複数の画像情報から合成されるべき１つの合成画像情報に対して、当該１つの合成画像情報に対応する１つの中間コードを生成するために、当該複数の画像情報について前記中間コード生成手段によりそれぞれ生成され前記中間コード記憶手段に記憶されている複数の中間コードを、前記上書き、つなぎ合わせ、または重ね合わせに応じて前記１つの中間コードに合成する中間コード編集手段と、
前記中間コード記憶手段に記憶された編集後の前記中間コードを、所定の手法で符号化する符号化手段と、
前記符号化手段で作成した符号を出力する符号出力手段とから構成されることを特徴とする画像符号化装置。
【請求項１０】
前記選択手段は前記予測値と実際の画素値との差が所定の閾値を越えないときに、対応する画素値予測手段の識別情報を選択する請求項９記載の画像符号化装置。
【請求項１１】
前記予測誤差算出手段の１つは、注目画素の値と予測値との間のスケール上の誤差を算出する請求項９または１０記載の画像符号化装置。
【請求項１２】
前記予測誤差算出手段の１つは、注目誤差を表すビットデータと予測値を表すビットデータとの排他的論理和を誤差として出力する請求項９、１０または１１記載の画像情報符号化装置。
【請求項１３】
請求項９記載の画像符号化装置から出力された符号を復号して前記中間コードを生成する復号手段と、
前記復号手段から出力された前記中間コードを格納する画像復号装置の中間コード記憶手段と、
上書き、つなぎ合わせ、および重ね合わせのうちの少なくとも１つを含む編集処理により複数の画像情報から合成されるべき１つの合成画像情報に対して、当該１つの合成画像情報に対応する１つの中間コードを生成するために、当該複数の画像情報について請求項９規制の画像符号化装置の前記中間コード生成手段によりそれぞれ生成され前記中間コード記憶手段に記憶されている複数の中間コードを、前記上書き、つなぎ合わせ、または重ね合わせに応じて前記１つの中間コードに合成する中間コード編集手段と、
画像内の復号対象である注目画素の画素値を、それぞれ異なる予測手法で予測することによって注目画素の画素値を算出する複数の画素値予測手段と、
前記中間コードにより表される誤差と所定の予測手法で予測された予測値とを加算することによって画像内の注目画素の画素値を算出する予測誤差加算手段と、
前記中間コードの情報に応じて、前記画素値予測手段のいずれか又は前記予測誤差加算手段を選択する選択手段と、
前記選択手段により前記画素値予測手段の１つが選択されたときには、その選択された画素値予測手段により算出された注目画素値を出力し、前記選択手段により前記予測誤差加算手段が選択されたときには、その選択された予測誤差加算手段により算出された注目画素を出力する注目画素出力手段とを具備することを特徴とする画像復号装置。
【請求項１４】
画像に可逆符号化を行う画像符号化方法において、
画像入力手段により、画像を入力する画像入力ステップと、
複数の画素値予測手段により、前記画像入力手段から入力した画像に対して注目画素の画素値を予測する画素値予測ステップと、
予測誤差算出手段により、前記画像入力手段から入力した画像に対して注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する予測誤差算出ステップと、
前記画素値予測手段のいずれかの予測値と実際の画素値が一致する場合には一致した１の画素値予測手段の識別情報を、そうでない場合には１の前記予測誤差算出手段で算出された予測誤差を選択手段により選択する選択ステップと、
中間コード生成手段により、前記選択手段で選択された画素予測手段の識別情報またはそのランレングス表現および予測誤差を含んで成る中間コードを生成する中間コード生成ステップと、
前記中間コード生成手段により生成された中間コードを中間コード格納手段に格納する中間コード記憶ステップと、
上書き、つなぎ合わせ、および重ね合わせのうちの少なくとも１つを含む編集処理により複数の画像情報から合成されるべき１つの合成画像情報に対して、当該１つの合成画像情報に対応する１つの中間コードを生成するために、中間コード編集手段が、当該複数の画像情報について前記中間コード生成手段によりそれぞれ生成され前記中間コード記憶手段に記憶されている複数の中間コードを、前記上書き、つなぎ合わせ、または重ね合わせに応じて前記１つの中間コードに合成する中間コード編集ステップと、
前記中間コード記憶手段に記憶された編集後の前記中間コードを、符号化手段により所定の手法で符号化する符号化ステップと、
符号出力手段により、前記符号化手段で作成した符号を出力する符号出力ステップとを有することを特徴とする画像符号化方法。
【請求項１５】
画像入力手段により、画像を入力する画像入力ステップと、
少なくとも１つの画素値予測手段により、前記画像入力手段から入力した画像に対して注目画素の画素値を予測する画素値予測ステップと、
少なくとも１つの予測誤差算出手段により、前記画像入力手段から入力した画像に対して注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する予測誤差算出ステップと、
前記画素値予測手段のいずれかの予測値と実際の画素値とが対応する場合には当該対応する１つの画素値予測手段の識別情報を、そうでない場合には１つの前記予測誤差算出手段で算出された１つの予測誤差を選択手段により選択する選択ステップと、
中間コード生成手段により、前記選択手段で選択された画素予測手段の識別情報またはそのランレングス表現および予測誤差を含んで成る中間コードを生成する中間コード生成ステップと、
前記中間コード生成手段により生成された中間コードを中間コード記憶手段に格納する中間コード記憶ステップと、
上書き、つなぎ合わせ、および重ね合わせのうちの少なくとも１つを含む編集処理により複数の画像情報から合成されるべき１つの合成画像情報に対して、当該１つの合成画像情報に対応する１つの中間コードを生成するために、中間コード編集手段が、当該複数の画像情報について前記中間コード生成手段によりそれぞれ生成され前記中間コード記憶手段に記憶されている複数の中間コードを、前記上書き、つなぎ合わせ、または重ね合わせに応じて前記１つの中間コードに合成する中間コード編集ステップと、
符号化手段により、前記中間コード記憶手段に記憶された編集後の前記中間コードを、所定の手法で符号化する符号化ステップと、
符号出力手段により、前記符号化手段で作成した符号を出力する符号出力ステップとを有することを特徴とする画像符号化方法。
【請求項１６】
復号手段により、請求項９記載の画像符号化装置から出力された符号を復号して前記中間コードを生成する復号ステップと、
前記復号手段から出力された前記中間コードを画像復号装置の中間コード記憶手段に格納する中間コード記憶ステップと、
上書き、つなぎ合わせ、および重ね合わせのうちの少なくとも１つを含む編集処理により複数の画像情報から合成されるべき１つの合成画像情報に対して、当該１つの合成画像情報に対応する１つの中間コードを生成するために、中間コード編集手段が、当該複数の画像情報について請求項９規制の画像符号化装置の前記中間コード生成手段によりそれぞれ生成され前記中間コード記憶手段に記憶されている複数の中間コードを、前記上書き、つなぎ合わせ、または重ね合わせに応じて前記１つの中間コードに合成する中間コード編集ステップと、
複数の画素値予測手段により、画像内の復号対象である注目画素の画素値を、それぞれ異なる予測手法で予測することによって注目画素の画素値を算出する画素値予測ステップと、
予測誤差加算手段により、前記中間コードにより表される誤差と所定の予測手法で予測された予測値とを加算することによって画像内の注目画素の画素値を算出する予測誤差加算ステップと、
前記中間コードの情報に応じて、前記画素値予測手段のいずれか又は前記予測誤差加算手段を選択手段により選択する選択ステップと、
前記選択手段により前記画素値予測手段の１つが選択されたときには、その選択された画素値予測手段により算出された注目画素値を出力し、前記選択手段により前記予測誤差加算手段が選択されたときには、その選択された予測誤差加算手段により算出された注目画素を出力する注目画素出力ステップとを有することを特徴とする画像復号方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像符号化方式に関するものであり、特に符号の状態で編集が可能な多値の入力画像に対する符号化方式に関するものである。
【０００２】
【従来の技術】
一般的に画像データは音声データやテキストデータに比べてデータ量が大量になる。よって画像データを蓄積ないし伝送する際には符号化によって圧縮するのが一般的である。符号化方式は復号画像に対して画質劣化を許容するか許容しないかで、それぞれ可逆符号化方式と非可逆符号化方式に大別できる。
【０００３】
画像データ一般の符号化方式としては、ＪＰＥＧ（Ｊｏｉｎｔ  Ｐｈｏｔｏｇｒａｐｈｉｃ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）を代表とする非可逆符号化方式が著名である。しかし非可逆符号化方式だと、ＰＤＬ（ページ記述言語）を含むＣＧ画像（Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃ；  コンピュータ作成の画像）に対しては、エッジ部分等で画質劣化が非常に目立つ。よってＣＧ画像に対しては非可逆符号化方式ではなく、従来の可逆符号化方式の改良が有効と考えられる。
【０００４】
本出願人は、ＣＧ画像データに対して有効な可逆符号化方式を提案している（特願平８−３１０７４号）。この方式はＣＧ画像データの性質、すなわち同一画素値を持つ画素が周辺に存在する可能性が高いことを利用した予測符号化方式である。
【０００５】
以下、この提案の符号化方式について説明する。図１８はこの符号化方式の画像符号化装置を示すブロック図である。図中、１０は画像入力部、２０は第１予測部、２１は第２予測部、３０は予測誤差算出部、４０は選択部、５０は符号化部、６０は符号出力部、１００は画像データ、１１０は予測値データ、１２０は予測誤差データ、１３０は予測状況データ、１４０は符号データである。
【０００６】
図１８の各部について説明する。画像入力部１０は、外部から入力画像を受け取り、画像データ１００として第１予測部２０、第２予測部２１および予測誤差算出部３０へ送出する。第１予測部２０、第２予測部２１は、それぞれ所定の手法で画像データ１００に基づいて注目画素の画素値を予測し、予測値データ１１０として選択部４０へ送出する。予測誤差算出部３０は、所定の手法で画像データ１００に基づいて注目画素の画素値を予測し、その予測値と注目画素の実際の画素値との差分を計算し、予測誤差データ１２０として、選択部４０へ送出する。選択部４０は、画像データ１００と予測値データ１１０から、注目画素における予測の一致／不一致を検出する。その結果、予測が的中した予測部があればその識別番号を、いずれも的中しなかった場合には予測誤差データ１２０を予測状況データ１３０に変換して符号化部５０へ送出する。符号化部５０は、所定の符号化手法を用いて予測状況データ１３０を符号化し、符号データ１４０として符号出力部６０へ送出する。符号出力部６０は、符号データ１４０を出力符号として外部へ出力する。
【０００７】
以上の構成における符号化の動作について説明する。図１９、図２０はこの符号化の動作を示すフローチャートである。
【０００８】
図１９を用いて符号化処理について説明する。Ｓ１０では画像入力部１０において画像の入力を行ない、画像データ１００を得る。Ｓ２０では第１予測部２０、第２予測部２１において画像データ１００に基づいて注目画素の画素値予測を行い、同時に予測誤差算出部３０において、所定の手法による予測値の予測誤差の算出を行う。
【０００９】
Ｓ３０については図２０を用いて説明する。Ｓ３１では、選択部４０において第１予測部の予測値と注目画素の画素値が一致するか否かを判定し、一致した場合Ｓ３４へ、一致しない場合Ｓ３２へ進む。同様にしてＳ３２では第２予測部の予測値と注目画素値が一致した場合Ｓ３４へ、一致しない場合はＳ３３へ進む。Ｓ３３では、選択部４０において、予測誤差データ１２０を予測状況データ１３０に変換して符号化部５０へ送出する。Ｓ３４では、選択部４０において、予測が的中した予測部の識別番号を予測状況データ１３０に変換して符号化部５０へ送出する。
【００１０】
Ｓ４０では符号化部５０において、予測状況データ１３０を所定の符号化手法で符号化し、符号データ１４０を得る。Ｓ５０では符号出力部６０において符号データ１４０を外部へ出力する。Ｓ６０では入力された画像データをすべて処理したか否かを判定し、すべて処理していれば符号化処理を終了する。また、未処理データが残っている場合には、Ｓ１０へ戻る。
【００１１】
さて、このような符号化を行なうシステムで画像の編集を行なう場合、符号のままでの編集は困難であり、復号して画像の状態に戻してから編集を行う必要がある。この場合、画像データを蓄積する装置の規模と読み出し時間が問題になる。読み出し時間を優先するために画像１ページ分の主記憶装置（ページメモリ）を持つと、装置規模の拡大とコスト増加を招く。逆にディスク装置に画像を蓄積すると、読み出し時間が長くなる。この両問題を解決する技術として頻繁にアクセスするデータ部分は主記憶装置に、その他はディスク等の二次記憶装置に格納するキャッシュという技術がある。しかし上述の編集の場合には広範囲の画素を取り扱うため、アクセス頻度が特定のデータに偏らず全体のアクセス時間を短くできない。
【００１２】
もし符号の状態で編集が可能になれば、以上の問題点を効果的に解決することができる。そこで、このような課題に関連する従来例として、符号の状態で編集する画像符号化方式（特開平５−３７７９１号公報）を説明する。ここでは、便宜上、動作原理のみ説明する。
【００１３】
特開平５−３７７９１号公報の従来例は２値画像を対象とし、図２１に示すようなブロック（４×４画素）毎に処理する。図中の１から１６までの数字は、ブロック内の位置を表すために用いられる。このブロックの画像情報は図２２に示す２バイトからなるデータ形式に変換される。図２２（ａ）（ｂ）はそれぞれラン特定パターン、エッジパターンのためのデータ形式で、最上位ビットに表されるデータＩＤフラグは、両者を区別するためのものである。
【００１４】
ブロックのデータが図２３に示す１６個のラン特定パターンである場合には、図２２（ａ）に示すデータ形式で符号化が行われる。図２３のパターンにはそれぞれの下に記した４ビットの数字のパターンコードが対応し、図２２（ａ）データ形式はこのパターンコードとそのパターンが連続するランの長さ１１ビットとからなる。
【００１５】
一方、図２３の１６個のパターン以外の場合にはエッジパターンとなり、各画素のデータは図２２（ｂ）中の数字に示すように図２１中の各画素の番号と対応して記憶される。すなわち、このビットマップデータを図２２（ｂ）に示すデータ形式の中で表す。ここで、番号１の画素のデータは省略し、復号時に周辺画素から所定の方式で類推することにより補う。
【００１６】
次にこの従来例における編集方式について説明する。図２３から明らかなように、特定パターンの行単位の黒ランの位置と、パターンコード中の”１”ビット位置とが対応する。例えば、ブロックにおいて一番下のラインのデータが黒ランの場合、パターンコードの４桁目は１である。また白ランであればそのラインに対応する桁のデータは”０”で表される。したがって、簡単な論理演算により画像の重ね合わせの処理ができる。編集例を図２４を用いて説明する。パターンコード０００１で表される画像と、パターンコード００１０で表される画像を重ねると、パターンコード００１１で表される画像が得られる。これに対応する演算は、２つのパターンコードの論理和”０００１”＋”００１０”＝”００１１”であり、得られたパターンコードは前記の重ね合わせ画像に対応する。
【００１７】
この従来例によれば２値画像を符号のまま重ね合わせ処理することができる。しかし新たな問題点として、対象が２値画像のランレングス符号化であるため多値画像を扱う時には高い圧縮率が期待できない。
【００１８】
【発明が解決しようとする課題】
特願平８−３１０７４号の符号化方式においては、符号に対しては復号する以外に画像データの編集を行なうことができない。また特開平５−３７７９１号公報の符号化方式においては、対象とする画像データが２値画像で、ＣＧ画像を始めとする多値画像を扱う時には高い圧縮率が期待できない。
【００１９】
本発明の目的は、以上の課題を解決するためになされたもので、符号化された画像データの編集において記憶装置の必要容量が少なく、多値画像であるＣＧ画像に対し圧縮率の高い画像符号化装置を提供することにある。
【００２０】
【課題を解決するための手段】
本発明は上述の目的を達成するために、第１に、画像に可逆符号化を行う画像符号化装置に、画像を入力する画像入力手段と、前記画像入力手段から入力した画像に対して注目画素の画素値を予測する複数の画素値予測手段と、前記画像入力手段から入力した画像に対して注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する予測誤差算出手段と、前記画素値予測手段のいずれかの予測値と実際の画素値が一致する場合にはその画素値予測部の識別情報を、そうでない場合には前記予測誤差算出手段で算出された予測誤差を選択する選択手段と、前記選択手段で選択された情報を所定の方式で中間コードに符号化する中間コード生成手段と、前記中間コード生成手段で生成された符号を格納する中間コード記憶手段と、前記中間コード記憶手段に記憶された複数の画像情報を表す中間コードを前記中間コードの特性に合わせた方式で編集する編集手段と、前記中間コード記憶手段に記憶された編集後の前記中間コードを所定の手法で符号化する符号化手段と、前記符号化手段で作成した符号を出力する符号出力手段とを設けるようにしている。
【００２１】
この構成によれば、前記中間コードをその特性に応じて直接に編集することができる。
【００２２】
また、この構成において、前記編集手段で用いられる編集処理は複数画像をつなぎ合わせる処理であってもよく、所定の画像に別の画像を上書き合成する処理であってもよい。
【００２３】
また、中間コードに含まれる同一符号のランを計算するラン計算手段を備え、前記中間コードに含まれる符号の少なくともひとつはランレングス符号化されるようにしてもよい。また、前記中間コードに含まれる情報は直上画素による予測結果と直左画素による予測結果と予測誤差とからなるようにしてもよい。
【００２４】
また、前記複数の画素値予測手段の少なくともひとつは、その予測値を前記中間コードの組み合せで近似的に表現するようにしてもよい。
【００２５】
また、前記中間コードに含まれる前記画素値予測手段の識別情報は、前記複数の画素値予測手段の予測ヒットの履歴を用いて算出される予測順位によって表現されるようにできる。
【００２６】
また、前記中間コードに含まれる前記画素値予測手段の識別情報は、最近に使われた前記画素値予測手段を１位としそれ以外は所定の優先順に順位づけする予測順位によって表現されるようにできる。
【００２７】
また、本発明の第２の側面によれば、上述の目的を達成するために、画像符号化装置に、画像を入力する画像入力手段と、前記画像入力手段から入力した画像に対して注目画素の画素値を予測する少なくとも１つの画素値予測手段と、前記画像入力手段から入力した画像に対して注目画素の画素値と所定の予測手法で予測された予測値との誤差を算出する少なくとも１つの予測誤差算出手段と、前記画素値予測手段のいずれかの予測値と実際の画素値とが対応する場合にはその画素値予測手段の識別情報を、そうでない場合には前記予測誤差算出手段で算出された１の予測誤差を選択する選択手段と、前記選択手段で選択された情報に基づいて中間コードを生成する中間コード生成手段と、前記中間コード生成手段により生成された中間コードを格納する中間コード記憶手段と、前記中間コード記憶手段に記憶された複数の画像情報を表す中間コードを、前記中間コードの特性に合わせた方式で編集する編集手段と、前記中間コード記憶手段に記憶された編集後の前記中間コードを、所定の手法で符号化する符号化手段と、前記符号化手段で作成した符号を出力する符号出力手段とを設けるようにしている。
【００２８】
この構成においても、前記中間コードをその特性に応じて直接に編集することができる。また、前記選択手段は前記予測値と実際の画素値との差が所定の閾値を越えないときに、対応する画素値予測手段の識別情報を選択するようにできる。この場合、可逆符号方式が修正される。また、前記予測誤差算出手段の１つは、注目画素の値と予測値との間のスケール上の誤差を算出するようにできる。さらに、前記予測誤差算出手段の１つは、注目誤差を表すビットデータと予測値を表すビットデータとの排他的論理和を誤差として出力するようにしてもよい。
【００２９】
また、本発明の第３の側面によれば、上述の目的を達成するために、上述の画像符号化装置で生成された符号を復号化する画像復号装置に、前記符号を復号して前記中間コードを生成する復号手段と、前記復号手段から出力された前記中間コードを格納する中間コード記憶手段と、前記中間コード記憶手段に記憶された複数の画像情報を表す中間コードを、前記中間コードの特性に合わせた方式で編集する編集手段と、画像内の復号対象である注目画素の画素値を、それぞれ異なる予測手法で予測することによって注目画素の画素値を算出する複数の画素値予測手段と、前記中間コードにより表される誤差と所定の予測手法で予測された予測値とを加算することによって画像内の注目画素の画素値を算出する予測誤差加算手段と、前記中間コードの情報に応じて、前記画素値予測手段のいづれか又は前記予測誤差加算手段を選択する選択手段と、前記選択手段により前記画素値予測手段の１つが選択されたときには、その選択された画素値予測手段により算出された注目画素値を出力し、前記選択手段により前記予測誤差加算手段が選択されたときには、その選択された予測誤差加算手段により算出された注目画素を出力する注目画素出力手段とを設けるようにしている。この構成においても、前記中間コードをその特性に応じて直接に編集することができる。
【００３０】
【発明の実施の態様】
以下本発明の実施例について説明する。
［実施例１］
図１は本発明の画像符号化装置の実施例１を示すブロック図である。図１において、図１８と同様の部分には同一の符号を付して説明を省略する。７０は中間コード生成部、８０は編集部、９０は中間コード記憶部、１５０，１６０，１７０，１８０は中間コードである。中間コード生成部７０は、予測状況データ１３０より中間コード１５０を生成し、中間コード記憶部９０に格納する。編集部８０は、所定の外部要求に応じて中間コード記憶部９０に格納されている中間コードの編集を行う。符号化部５０は、中間コード記憶部９０より中間コード１８０を取り出し、所定の符号化を行う。
【００３１】
図３は本発明の実施例の動作を示すフローチャートである。以下、実施例の動作について説明するが、図１９と同様の部分には同一の符号を付して説明を省略し、異なる部分についてのみ述べる。
【００３２】
Ｓ２０１０では、中間コード生成部７０において予測状態データ１３０を所定の方式により中間コード１５０に変換し、中間コード記憶部９０に格納する。Ｓ２０２０では、中間コード記憶部９０内において中間コード編集を行う。Ｓ２０４０では、符号化部５０において中間コード記憶部９０より中間コード１８０を取り出し、所定の符号化方式で符号化し、符号データ１４０を得る。
【００３３】
以上が本実施例の動作であるが、Ｓ２０２０の中間コード編集ではさまざまな機能を実装することが考えられる。以下では、一例として図７で示されるようなある画像に対して他の画像を上書きする場合について説明する。
【００３４】
ここで説明を簡易にするために、第１予測部２０、第２予測部２１は、画素値予測を注目画素のそれぞれ、直左画素値、直上画素値を利用することにする。この設定の下で中間コードの構造を図２のように定める。中間コードの最初の２ビットは中間コードの種別を区別するための識別子として用いる。ここで（ａ）は左画素上画素参照、（ｂ）は左画素参照、（ｃ）は上画素参照、（ｄ）は誤差値を表す。左画素上画素参照（ａ）は、直左画素と直上画素が共に注目画素の画素値と等しい場合を表す。左画素参照（ｂ）は、直左画素と注目画素の画素値が等しい場合を表す。上画素参照（ｃ）は、直上画素と注目画素の画素値が等しい場合を表す。誤差値（ｄ）は、直左画素直上画素ともに注目画素と画素値が等しくない場合を表し、誤差値により直左画素値と注目画素値との差分を表す。図９に中間コードの例を示す。
【００３５】
Ｓ２０２０の中間コード編集の実装例を図４，図５を用いて説明する。ここにおいて、上書きされる画像データの中間コードを下地符号、上書きする画像データの中間コードを入力符号と呼ぶものとする。また、下地符号、入力符号中の符号参照位置を下地符号カーソル（ＢＣＵＲ）、入力符号カーソル（ＩＣＵＲ）として設定する。
【００３６】
Ｓ２１０１では、下地符号の上書き開始位置までＢＣＵＲを移動させる。Ｓ２１０２では、入力符号の終了を確認する。入力符号が終了でなければＳ２１０３へ、終了であれば、Ｓ２１１２へ進む。Ｓ２１０３では、位置ＩＣＵＲが画素値展開した場合に行の最右であるかどうかを判断する。最右の場合はＳ２１０４へ、最右でない場合はＳ２１０９へ進む。Ｓ２１０４では、入力符号をそのまま下地符号に対して置換する。Ｓ２１０５ではＢＣＵＲを１進める。Ｓ２１０６では、ＢＣＵＲにおける符号が左参照を行っているかどうかを判断する。左参照を行っている場合はＳ２１３１へ、行っていない場合にはＳ２１０１へ進む。Ｓ２１３１では、すでに入力符号によって置換済である直左符号を参照して注目画素値と等しいかどうかを判断する。等しい場合はＳ２１３２へ、等しくない場合はＳ２１３３へ進む。Ｓ２１３２では、下地符号を左画素参照に置換する。Ｓ２１３３では、下地符号を誤差値に置換する。Ｓ２１０８では、下地符号の次行の挿入開始位置を検索する。その後、Ｓ２１０２に戻り、次の入力符号の処理に進む。
【００３７】
Ｓ２１０９では、入力符号を下地符号に対して置き換える。Ｓ２１１０では、ＢＣＵＲを１進める。Ｓ２１１１では、ＩＣＵＲを１進める。その後、Ｓ２１０２に戻り、次の入力符号の処理に進む。
【００３８】
Ｓ２１１２では、ＢＣＵＲを入力符号の最左最下画素の直下、すなわち図８の位置（ｂ）中の最左まで移動する。Ｓ２１１３では、入力符号の直下位置、すなわち図８の位置（ｂ）を外れたかどうかを判断する。外れた場合は処理を終了する。外れていない場合はＳ２１１４へ進む。Ｓ２１１４では、下地符号が直上画素の参照を行なっているかどうかかを判断する。直上画素を参照している場合はＳ２１４１へ、参照していない場合はＳ２１１６へ進む。Ｓ２１４１では、すでに入力符号によって置換済である直上符号を参照して注目画素値と等しいかどうかを判断する。等しい場合はＳ２１４２へ、等しくない場合はＳ２１４３へ進む。Ｓ２１４２では、下地符号を上画素参照に置換する。Ｓ２１３４３では、下地符号を誤差値に置換する。Ｓ２１１６では、ＢＣＵＲを１進める。
【００３９】
以上の編集処理について図２、図８を用いて補足説明する。まず図２を用いて中間コード上で画像データ同様に編集が行えることを説明する。図２の中間コードの構成によれば、画素値と中間コードの割当ては一対一対応しており、中間データの画素参照（ａ），（ｂ），（ｃ）と誤差値（ｄ）のビット数差さえ考慮して位置検索してやれば、任意の画素に対する中間コード位置は容易に特定できる。編集対象となる画素が中間データ上で特定できれば、編集は中間コードの置き換えで済む。
【００４０】
ただし、中間コードは画素間の関係を情報として持つので、中間コード特有の処理が発生する。そこでその点について図８を用いて説明する。図８において位置（ａ）、位置（ｂ）で示した部分に対する予測用の画素値が上書きされてしまうため、中間コード特有の処理を必要とする。Ｓ２１０５の処理終了時において、ＢＣＵＲは位置（ａ）の範囲のどこかの中間コードを参照している。この位置において直左画素は入力画像の画素のため、下地符号の参照関係が正しくない可能性がある。よって、そのための検査をＳ２１０６で行なっている。また、Ｓ２１１２の処理終了時において、ＢＣＵＲは位置（ｂ）の最左の中間コードを参照している。同様にして、位置（ｂ）の範囲では直上画素は入力画素のため、下地符号の参照関係が正しくない可能性がある。よって、そのための検査をＳ２１１４で行なっている。
【００４１】
まず本実施例による中間コードの符号量削減効果を実証する。図６（ａ）（ｂ）に実験例を示す。図６（ａ）はＰＤＬ画像から５つのテスト画像に対して予測を行った結果で、直上予測と直左予測のいずれかが当たる場合がほとんどとなる。次に図２のフォーマットで中間コードを表した場合の平均符号長を図６（ｂ）に示す。テストに用いた画像は８［ｂｉｔ］の階調を持っているのに対し、中間コードは１画素あたり２［ｂｉｔ］強ですむので、中間コード記憶部９０は画像を蓄積する場合に比較して１／４程度ですむ。
【００４２】
次に、Ｓ２０４０の中間コードの符号化について述べる。本発明では特願平８−３１０７４号と同様に的中した予測部の識別番号を符号化する。そこで中間コードから識別番号を作成する処理について具体的に説明する。
【００４３】
例えば直左予測の識別番号を０、直上予測の識別番号を１とし、予測誤差を符号化する場合の識別番号を２とする。このとき中間コードと符号化すべき識別番号の関係を図１０（ａ）に示す。ただし直左予測と直上予測が両方とも注目画素値に等しい場合、直左予測を優先するものとした。参考に符号化部５０において識別番号にハフマン符号化を行う例を図１０（ａ）の一番右の列に示す。
【００４４】
この変形例として第１の従来例では予測器に優先順位をつけ、その順位を識別番号の代わりに用いることで符号量を小さくする手法が述べられている。このような手法を本実施例に取り入れた場合の符号化例を図１０（ｂ）に示す。左から順に中間コード、直前に符号化した予測器と優先順位、今回使用する予測器と更新される優先順位、符号化する順位とハフマン符号の例である。ただしここではデフォルトの優先順位を直左−直上−予測誤差の順とし、直前で使用された予測器を第１位、それ以外の順位はデフォルト通りとした。この他に統計を用いた優先順位の決め方などもあるが、同様に考えることができる。また図１０（ｂ）の処理であれば、簡単なルックアップテーブル処理により実現できる。
【００４５】
さらに同様の中間コードを用いて予測器の種類を増やす手法について述べる。注目画素に対する直左予測、直上予測の関係を図示すると、それぞれ図１１（ａ）の画素Ｘに対する画素Ａと画素Ｂの関係になる。中間コードはこの２者に対応するものだから、例えば図１１（ａ）の画素Ｃ、画素Ｄからの予測は直接表現できない。しかし次のような手法で近似的なシミュレートが可能である。
【００４６】
以下、図１１（ａ）の画素の表記を画素値で置き換える。例えば直左予測が成立するのはＸ＝Ａの場合、というように書く。すると、Ｘ＝Ｃが成立するには以下の４つのケースが考えられる。
【００４７】
（１）  Ｘ＝ＡかつＸ＝ＢかつＡ＝Ｃ（Ｂ＝Ｃ）
（２）  Ｘ＝ＡかつＸ≠ＢかつＡ＝Ｃ
（３）  Ｘ≠ＡかつＸ＝ＢかつＢ＝Ｃ
（４）  Ｘ≠ＡかつＸ≠ＢかつＸ＝Ｃ
それぞれのケースをベン図にしたものを図１１（ｂ）に示す。（４）以外は画素Ｘと画素Ｃを直接比較する必要がないことがわかる。さらに画素Ａを符号化するときに画素Ａと画素Ｃの関係が、また画素Ｂを符号化するときに画素Ｂと画素Ｃの関係が中間コードとして得られているから、この情報を保持しておけば（４）のケースを除いて画素Ｃによる予測が近似できる。画素Ｄによる予測も同様に近似が可能である。これにより近似された予測が復号の際に可能であれば、符号化器には存在しない予測部を符号化することができる。
【００４８】
ただし符号化の観点から言えば、画素Ｃからの予測が成立する時にはすでに直左予測と直上予測のいずれかが成立しているので、画素Ｃの予測を加えても符号量の削減に効果的でない場合もある。これに対して画素Ｄによる予測はＸ＝ＥかつＥ＝Ｄというケースがあるので、効果的な場合がある。ちなみに画素Ｅは画素Ｘの処理時には未処理画素なので普通予測には使われないが、この場合画素Ｄを近似したシミュレートをするだけなので、復号の際に画素Ｄを直接参照することができれば何の問題も生じない。また近似は予測が当たっていてもはずれたと認識するような近似なので、復号器が誤った予測を行う危険はない。
【００４９】
［実施例２］
図１２は本発明の画像符号化装置の実施例２を示すブロック図である。図１，図１８と同様の部分には同一の符号を付して説明を省略する。９５はラン計算部、１９０はラン予測状況データである。ラン計算部９５は、予想状況データ１３０より同一予測部の予測的中の連続数を検出し、それを他の予測状況データを含めて所定の手法でラン予測状況データ１９０に変換する。
【００５０】
実施例２の動作を図１４に示す。図３と同様の部分については説明を省略する。Ｓ２００５においてラン計算部９５が予測状況データ１３０をラン予測状況データ１９０に変換する。Ｓ２０１０において中間コード生成７０がラン予測状況データ１９０を中間コード１６０に変換する。
【００５１】
この場合の中間コード構成について図２との差分のみを図１３に示す。（ａ’）ランは直左画素、直上画素共に注目画素値と等しい場合を表し、ラン数によりその連続数を表している。中間コードの例を図１５に示す。
【００５２】
ここにおいて、実施例１と比較して編集時に中間コードのランを扱う点が異なるので、その点について簡単に説明する。図１６はランの編集処理の説明図である。図１６（ｂ）と（ｃ）に示すようにランをとると下地データ１画素に中間コード１符号が対応しなくなるので、特に入力データのエッジに対応する部分では図１６（ｄ）に示すようにラン数を減算する。入力データの下に隠れる部分はランのコードごと削除し、逆に入力データにかからない部分はそのまま保持すればよい。
【００５３】
本実施例では、予測状況データに対してランレングスをとるため、中間コードの符号量が少なくできると言う特徴がある。特にＰＤＬ画像に対しては図６（ａ）の例で示すように２／３以上が直上直左画素一致で占められるため、かなりの符号量の削減が期待できる。
【００５４】
［変形例］
本発明は以上の実施例に限定されるものではなく、その趣旨を逸脱しない範囲で種々変更が可能である。例えば、編集部８０は他の編集機能、例えば従来例２で用いられるような二画像を重ね合わす機能、あるいは二画像をつなぎ合わせる機能等を提供するものでもよい。後者の場合、本実施例の図８で示されるような下地画像、入力画像間の境界での問題は発生せず、中間コードを単純に挿入するだけの処理で済む。
【００５５】
また、上述実施例においては予測部が完全に一致したときに予測部の識別データを送出して中間コードに含ませているが、完全な一致でなく、そのエラーが所定の閾値以下の場合に一致したと判断して当該予測部の識別データを送出するようにしてもよい。また、予測誤差算出部を複数設けてもよい。さらに予測誤差算出部が、目標画素と予測値との間の誤差をスケール上の差分として生成してもよいし、またビットデータの論理演算例えば排他的論理和により生成してもよい。もちろん双方の誤差を用いてもよい。誤差の選択は、例えば、エントロピーを算出して小さいエントロピーの誤差を選ぶようにできる。
【００５６】
また符号化した中間データを復号し、復号して得た中間データを編集する場合にも本発明を適用できる。例えば、図１７に示すように画像復号器を構成することができる。図１７において、符号入力部６１に符号が入力され、この符号を復号部５１が復号し、復号データに基づいて中間コード生成部７０が中間コードを生成する。この中間コードは中間コード記憶部９０に記憶する。編集部８０は他の実施例と同様に、中間コード記憶部９０中の中間コードを編集する。編集された中間コードは選択部４１に送られ、さらに第１予測部２０、第２予測部２１および予測誤差加算部３０に送られる。そして中間コードの情報に基づいて第１予測部２０、第２予測部２１および予測誤差加算部３０からの出力が択一的に画像出力部１１に供給され、復号画像として出力される。なお、図１７において、図１８および図１と対応する箇所には対応する符号を付して詳細な説明を省略した。
【００５７】
【発明の効果】
以上説明したように、本発明による多値画像に対する符号化方式においては、最終出力の符号において特願平８−３１０７４号（図１８）の符号化方式と同等の高い圧縮率を実現し、かつ中間コードの状態で画像と同じように編集が可能である。また圧縮した状態で編集を行なうので、記憶装置の必要容量を削減できる。
【図面の簡単な説明】
【図１】  本発明の画像符号化装置の実施例１を示すブロック図である。
【図２】  本発明の画像符号化装置の実施例１における中間コード構成例の説明図である。
【図３】  本発明の画像符号化装置の実施例１における符号化処理の動作の一例を示すフローチャートである。
【図４】  本発明の画像符号化装置の実施例１における編集処理の動作の一例を示すフローチャートである。
【図５】  本発明の画像符号化装置の実施例１における編集処理の動作の一例を示すフローチャートである。
【図６】  ＰＤＬ画像の画素値分布の説明図である。
【図７】  本発明の画像符号化装置の実施例１における画像データの編集方式の説明図である。
【図８】  本発明の画像符号化装置の実施例１における中間コード置換位置についての説明図である。
【図９】  本発明の画像符号化装置の実施例１における中間コード例の説明図である。
【図１０】  本発明の画像符号化装置の実施例１における中間コードと予測器識別番号および予測器順位の関係の説明図である。
【図１１】  予測器と予測結果の説明図である。
【図１２】  本発明の画像符号化装置の実施例２を示すブロック図である。
【図１３】  本発明の画像符号化装置の実施例２における中間コード構成例の説明図である。
【図１４】  本発明の画像符号化装置の実施例２における符号化処理の動作の一例を示すフローチャートである。
【図１５】  本発明の画像符号化装置の実施例２における中間コード例の説明図である。
【図１６】  本発明の画像符号化装置の実施例２におけるランに対する編集処理の説明図である。
【図１７】  本発明の画像復号装置の実施例を説明するブロック図である。
【図１８】  本出願人が提案している画像符号化装置を示すブロック図である。
【図１９】  図１８の画像符号化装置における符号化処理の動作の一例を示すフローチャートである。
【図２０】  従来例の画像符号化装置における予測器の選択処理の動作の一例を示すフローチャートである。
【図２１】  図２０の従来例における画素ブロックの説明図である。
【図２２】  図２０の従来例におけるパターン構成例の説明図である。
【図２３】  図２０の従来例におけるラン特定パターンコード例の説明図である。
【図２４】  図２０の従来例におけるパターン重ね合わせ例の説明図である。
【符号の説明】
１０は画像入力部、２０は第１予測部、２１は第２予測部、３０は予測誤差算出部、４０は選択部、５０は符号化部、６０は符号出力部、７０は中間コード生成部、８０は編集部、９０は中間コード記憶部、９５はラン計算部、１００は画像データ、１１０は予測値データ、１２０は予測誤差データ、１３０は予測状況データ、１４０は符号データ、１５０，１６０，１７０，１８０は中間コード、１９０はラン予測状況データである。
【図１】
0003721644.tif 000002
【図２】
0003721644.tif 000003
【図３】
0003721644.tif 000004
【図４】
0003721644.tif 000005
【図５】
0003721644.tif 000006
【図６】
0003721644.tif 000007
【図７】
0003721644.tif 000008
【図８】
0003721644.tif 000009
【図９】
0003721644.tif 000010
【図１０】
0003721644.tif 000011
【図１１】
0003721644.tif 000012
【図１２】
0003721644.tif 000013
【図１３】
0003721644.tif 000014
【図１４】
0003721644.tif 000015
【図１５】
0003721644.tif 000016
【図１６】
0003721644.tif 000017
【図１７】
0003721644.tif 000018
【図１８】
0003721644.tif 000019
【図１９】
0003721644.tif 000020
【図２０】
0003721644.tif 000021
【図２１】
0003721644.tif 000022
【図２２】
0003721644.tif 000023
【図２３】
0003721644.tif 000024
【図２４】
0003721644.tif 000025