(57)【特許請求の範囲】
【請求項１】
入力される対象カラー画素データを符号化データに符号化し、出力するマルチカラー画像の符号化装置において、
符号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切り、前記短冊に対応する画素データを出力する短冊生成手段と、
前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素に対する周辺画素データおよび符号化対象画素の直前の画素を除いた周辺の４画素の参照画素に対する参照画素データを生成し、前記周辺画素データおよび参照画素データを出力するラインバッファ手段と、を有し、
前記周辺画素データに基づいて、色順位テーブルを作成し、前記参照画素データに基づいてマルコフモデルのコンテクストを作成し、
前記色順位テーブルおよび前記コンテクストに基づいて、前記各短冊内に位置する前記符
号化対象画素を順次符号化することを特徴とする符号化装置。
【請求項２】
入力される対象カラー画素データを符号化データに符号化し、出力するマルチカラー画像の符号化方法において、
符号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切り、前記短冊に対応する画素データを出力する短冊生成工程と、
前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素に対する周辺画素データおよび符号化対象画素の直前の画素を除いた周辺の４画素の参照画素に対する参照画素データを生成し、前記周辺画素データおよび参照画素データを出力するラインバッファ工程と、を有し、
前記周辺画素データに基づいて、色順位テーブルを作成し、前記参照画素データに基づいてマルコフモデルのコンテクストを作成し、前記色順位テーブルおよび前記コンテクストに基づいて、前記各短冊内に位置する前記符号化対象画素を順次符号化することを特徴とする符号化方法。
【請求項３】
入力される対象符号化データを復号化データに復号化し出力するマルチカラー画像の復号化装置において、
復号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切って復号する短冊合成手段と、
前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素データおよび参照画素データを生成し、前記周辺画素データおよび前記参照画素データを出力するラインバッファ手段と、を有し、
前記周辺画素データに基づいて、色順位テーブルを作成し、直前の画素を除いた周辺の４画素の復号化データに基づいてマルコフモデルのコンテクストを作成し、
前記色順位テーブルおよび前記コンテクストに基づいて、短冊状に前記復号化の対象とな
る対象画像を順次復号化することを特徴とする復号化装置。
【請求項４】
入力される対象符号化データを復号化データに復号化し出力するマルチカラー画像の復号化方法において、
復号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切って復号する短冊合成工程と、
前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素データおよび参照画素データを生成し、前記周辺画素データおよび前記参照画素データを出力するラインバッファ工程と、を有し、
前記周辺画素データに基づいて、色順位テーブルを作成し、直前の画素を除いた周辺の４画素の復号化データに基づいてマルコフモデルのコンテクストを作成し、
前記色順位テーブルおよび前記コンテクストに基づいて、短冊状に前記復号化の対象とな
る対象画像を順次復号化することを特徴とする復号化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチカラー画像の符号化装置およびその方法ならびにマルチカラー画像の復号化装置およびその方法に関する。そして、さらに詳細に述べれば、特にマルチカラー画像を符号化および復号化する際のその対象画像の区切り方の改良に関する。
【０００２】
【従来の技術】
従来からパソコンやゲーム機器等では、マルチカラー画像と呼ばれる画像が使用されている。このマルチカラー画像とは、代表色画像とか限定色画像等とも呼ばれているもので、図２２に示すように、特定の色、すなわち特定のＲ（赤）、Ｇ（緑）、Ｂ（青）の値を持つ色に対してインデックスを付与し、そのインデックスのデータを利用して、１６色や２５６色等の限定された代表色で表現するようにした画像のことである。
【０００３】
このようなマルチカラー画像のデータは、仮にＲ、Ｇ、Ｂの各色が８ビット（２５６種）で表されるとしたら、合計２４ビット必要になるのであるが、インデックスそのものも例えば８ビットで表示するようにしているので、相当な圧縮率となっている。しかし、圧縮はされているが、それでも情報量が多いため、何の工夫もせず、そのままの形で処理すると、メモリ容量が大きくなり、また通信速度も遅くなり実用的でない。したがって、マルチカラー画像も他の画像データと同様にその圧縮技術は極めて重要なものとなる。特に、マルチカラー画像は、その色の数が限定されていることから、ロスレスでの符号化および復号化、すなわち可逆的な圧縮技術が必要とされている。
【０００４】
一方、近年、データ圧縮の手法の一つとして、エントロピー符号器および復号器を用いた技術が注目されている。このエントロピー符号化および復号化技術の一つとして、例えば、算術符号化および復号化の技術を用いたものがある。この技術の概要は、例えば、特開昭６２−１８５４１３号公報、特開昭６３−７４３２４号公報、特開昭６３−７６５２５号公報等に記載されている。
【０００５】
図１６に、このような技術を用いた従来のマルチカラー画像の符号化システム５０および復号化システム６０を示す。この符号化システム５０は、ラインバッファ５１と、エントロピー符号器５２とを含むものである。入力されるインデックスのデータ、すなわちカラー画素データ１００Ａは、ラインバッファ５１およびエントロピー符号器５２へ入力される。このカラー画素データ１００Ａは、図１７に示すように、いずれもラスタースキャンされ水平走査順に順次画素データとして入力される。なお、このインデックスのデータ、すなわちカラー画素データ１００Ａを作成する方法としては、入力する色の順番にインデックスを付与する方法が一般的であり、図２２に示すように、インデックスの番号が近いもの、例えば「１」と「２」でもその色が大きく異なったり、インデックスの番号が遠いもの、例えば「１００」と「２００」でもその色は近似している現象が生じている。このような現象を避けるため、特開平５−３２８１４２に示されるように、色の近いものに連続番号を付与するようにしたものも現れている。
【０００６】
符号化システム５０中のラインバッファ５１は、参照画素生成手段として、既に入力されたカラー画素データ１００Ａから、符号化対象画素Ｘに対する参照画素データＡ，Ｂ，Ｃ，Ｄを作成する。すなわち、ラインバッファ５１は、画像をスキャンするときにｎライン（１〜５ライン程度が多い）分の履歴を記憶しておく。そして、符号化対象画素Ｘのカラー画素データ１００Ａが入力されるごとに、この直前の画素Ａと、周辺の画素Ｂ，Ｃ，Ｄとからなる一連の画素データを参照画素データ１１０としてエントロピー符号器５２へ向けて出力する。
【０００７】
このエントロピー符号器５２は、例えば、算術符号化またはハフマン符号化などの手法を用いて形成される。そして、参照画素データ１１０を状態信号として用い、対象カラー画素データ１００Ａを符号化データ２００に変換出力する。
【０００８】
一方、復号化システム６０は、ラインバッファ６１とエントロピー復号器６２を含んで構成される。ここにおいて、ラインバッファ６１とエントロピー復号器６２は、入力される符号化データ２００を符号化システム５０のラインバッファ５１、エントロピー符号器５２とは全く逆の手順で復号化出力するように形成されている。
【０００９】
このようにして、符号化システム５０と、復号化システム６０とは、互いに全く逆のアルゴリズムを用いて、カラー画素データ１００Ａを符号化データ２００に符号化し、さらにこの符号化データ２００をカラー画素データ１００Ｂに復号化して出力することができる。したがって、このシステムは、各種用途に幅広く用いることができる。
【００１０】
ところで、このようなシステムでは、カラー画素データ１００Ａの値、すなわちインデックスの番号が一定の番号付近に偏るとそのデータの圧縮率が向上する。また、このシステムでは、参照画素データ１１０を、エントロピー符号器５２、エントロピー復号器６２の状態信号として使用している。したがって、その状態数、すなわち、参照画素数を多くとれば、同様にデータ圧縮率は向上する。すなわち、算術符号化またはハフマン符号化などの手法を用いてエントロピー符号器５２および復号器６２を構成する場合には、０または１のシンボルの発生確率に大きな偏りがあると、データの圧縮率を高めることができる。これは、エントロピー符号化技術では、発生確率の高い入力データには短い符号化データを割り当て、発生率の低い入力データには相対的に長い符号化データを割り当てるからである。
【００１１】
シンボル、すなわちインデックスの番号の発生確率の大きな偏りを得るために、従来より、入力データをいくつかの状態に分類して符号化することが行われている。なぜなら、分類をしないと、良い圧縮率は得られないからである。例えば、図１６に示す従来の手法では、ラインバファ５１，６１を用い、参照画素データを作成し、これを分類用の状態信号としてエントロピー符号器５２およびエントロピー復号器６２へ入力している。そして、これらエントロピー符号器５２およびエントロピー復号器６２は、前記状態信号を用いることにより入力データを分類し、符号化および復号化を行っている。すなわち、参照画素データの各状態の発生確率を計算し、その発生確率の高い組み合わせのものに短い符号化データを割り当てている。そして、これによりデータの圧縮率を高めている。
【００１２】
しかし、前述したエントロピー符号器５２およびエントロピー復号器６２では、参照画素データの状態数に対応した数の符号化パラメータテーブルが必要となる。このため、圧縮率を高めるために参照画素数を大きくとればとるほど、符号化および復号化のパラメータテーブルが大きくなる。このため、エントロピー符号器５２およびエントロピー復号器６２が大型化かつ高価となってしまうという問題がある。
【００１３】
例えば、カラー画素データ、すなわちインデックスの番号を４ビットデータ（１６種）で構成し、しかも参照画素データ１１０の画素数が４である場合を想定する。この場合には、符号化および復号化パラメータテーブルの状態数は、４画素×４ビット＝１６ビット分の状態数、すなわち２16の状態数をとる。このため、２16＝６５５３６通りのパラメータテーブルを用意しなければならない。このことからも、参照画素を１つ増やすごとに、その分、符号化および復号化パラメータテーブルが極めて大きくなり、エントロピー符号器５２およびエントロピー復号器６２を構成するハードウェアが大型化してしまうことが理解される。しかも、対象画素も４ビット、すなわち、４プレーンで構成され、各プレーンに１ビットずつの信号が割り当てられ、結果として４ビットで１６通りの値（色）をとるので、パラメータテーブルは６５５３６×１６の大きさを持つテーブルとなる（図１８参照）。
【００１４】
このような問題に対し、対象画素のカラーシンボル、すなわち色に対応するインデックスの番号の出現頻度の偏りを計算し、出現頻度順位に対応して、インデックスの番号を並び替える色順位変換の方法（特開平６−２７６０４１号）がある。すなわち、これにより出現頻度の高いものに短い符号化データを割り当て、さらに、圧縮率を高めている。また、この公開公報には、エントロピー符号器５２およびエントロピー復号器６２の中に縮退した状態数に応じてパラメータテーブルを小さくさせる技術も開示されている。
【００１５】
この特開平６−２７６０４１号公報に示されている状態数を縮退するシステムの特徴は、図１９に示すように、従来の符号化システム５０や復号化システム６０と同様にエントロピー符号器５２およびエントロピー復号器６２に参照画素データ１１０を状態信号として入力するわけであるが、その入力に際し、その状態信号１４０を、ラインバッファ５１，６１から出力される参照画素データ１１０を縮退する状態縮退器５３，６３によって生成する点にある。
【００１６】
この状態縮退器５３、６３は、入力される参照画素データ１１０を、より少ないビット数の状態信号１４０に縮退し、対応するエントロピー符号器５２およびエントロピー復号器６２へ向け出力するように構成されている。なお、予測器５４，６４は、それぞれカラーシンボルの出現頻度に基づいてカラー画素データを色順位に変換するためおよびその逆を行うための色順位テーブル（詳細は後述）をそのメモリーに保有しているものである。
【００１７】
なお、縮退とは、縮退後の状態数に、元の状態を分類する操作である。この分類は、分類後のエントロピー（１つのシンボルを表示するための平均情報量）が最少となるように、その組み合わせを選択して行う。そして、縮退後の状態数、すなわち、分類された後の状態数に対して識別ビットを付加する。これが状態信号１４０である。
【００１８】
ところで、状態縮退器５３，６３に用いる縮退テーブルとしては、参照画素データ１１０のカラーシンボルの組み合わせパターンと、縮退データとの関係を特定する縮退テーブルを設定し、この縮退テーブルを用い、入力される参照画素データ１１０のカラーシンボルの組み合わせパターンを、縮退データに変換出力する方法がある。
【００１９】
図２０には、このような手法を用いて行われる縮退動作の一例が示されている。ここでは、説明を簡単にするために、図２０（Ａ）に示すよう、符号化対象画素Ｘに対し、Ａ，Ｂ，Ｃの３つの画素から形成されるマルコフモデルを参照画素パターンとして用いる場合を例にとり説明する。
【００２０】
参照画素が、図２０（Ａ）に示すように、３つの画素から構成される場合には、そのカラーシンボルの組み合わせパターンは、図２０（Ｂ）に示すように５通りとなる。すなわち、３つに画素のカラーシンボルが全て一致するパターンと、２つのカラーシンボルのみが一致する場合に該当する３つのパターンと、全ての画素のカラーシンボルが異なるパターンの計５つのパターンに分類される。
【００２１】
したがって、図２０（Ｂ）に示すテーブルを状態縮退器５３，６３の縮退テーブルとして用いることにより、本来３つの画素の組み合わせが取りうる２12パターンの状態を、図２０（Ｂ）に示す５つの状態Ｓ１〜Ｓ５に縮退することができる。このようにすることによって、参照画素データ１１０を効果的に縮退し、エントロピー符号器５２およびエントロピー復号器６２の状態数を大幅に少なくすることができる。
【００２２】
ところで、このような算術符号化および復号化の一般的な手法は、既に１画像符号化標準ＪＢＩＧ（インターナショナルスタンダードＩＳＯ／ＩＥＣ１１５４４）のｐ２６〜４４およびｐ４４〜ｐ５０に詳細に述べられているが、ここでは後述する本発明を展開する際の前提技術として簡単に説明する。
【００２３】
図１６に用いられる算術符号型のエントロピー符号器５２の一例を図２１に示す。なお、算術復号型のエントロピー復号器６２の構成は、エントロピー符号器５２の構成と実質的に同一であるので、ここではその説明は省略する。
【００２４】
このエントロピー符号器５２は、算術演算部５５と、状態記憶器として機能する発生確率生成手段５６とを含んで構成される。この発生確率生成手段５６内には、符号化に必要なシンボル発数確率を決定するために必要な状態パラメータテーブルが書き込まれている。上記の状態パラメータは、入力される状態信号によって特定される。そして、この状態信号によって特定された状態パラメータのテーブルに対し、発生確率生成手段５６の発生確率演算パラメータが算術演算部５５へ向けて出力される。算術演算部５５は、このようにして入力される発生確率に基づき、エントロピー符号化を行い、入力される色順位データ１２０を符号化データ２００に変換出力する。そして、符号化した色順位データ１２０の値により、状態信号に対する発生確率を再計算し、演算パラメータ更新値として、発生確率生成手段５６へ入力する。この更新結果が次データの発生確率としてテーブルに記憶されることで、エントロピー符号器５２の圧縮効率が向上することとなる。
【００２５】
なお、色順位データ１２０を生成するために、先に述べたように予測器５４，６４内に色順位テーブルが配置されている。この色順位テーブルの一例として、図２３に示されるものが知られている（特開平６ー２７６０４１号公報参照）。この例では、符号化対象画素Ｘに対しての色順位テーブルを決める際、２次元的な周辺画素データＲ０，Ｒ１，Ｒ２，Ｒ３を上位の色順位データとして使用し、符号化対象画素Ｘと同一ラインの１次元テーブルを下位の色順位データとして使用するものである。このとき、１次元テーブルから周辺画素データＲ０，Ｒ１，Ｒ２，Ｒ３のカラーシンボルを除去した後、上位と下位の色順位データをドッキングさせ符号化対象画素Ｘの色順位テーブルとしている。
【００２６】
具体的にどのように色順位テーブルができあがるかを図２３に基づき説明する。符号化されるカラーシンボルが１６色の場合を考える。仮に、色順位を図２３（Ａ）に示すように、各画素の位置Ｒ０，Ｒ１，Ｒ２…Ｒ８… で固定したとき、それぞれのカラーシンボルが図２３（Ｂ）に示すように、Ｃ４，Ｃ３，Ｃ６，Ｃ５，Ｃ２，Ｃ２…のとき、できあがる最新出現表となる色順位テーブルは、図２３（Ｃ）に示すようになる。すなわち、最上位はＲ０のＣ４，２番目はＲ１のＣ３，３番目はＲ２のＣ６，４番目はＲ３のＣ５，５番目はＲ４のＣ２，６番目はＲ５にあるＣ２となるが、Ｃ２は既に発生しており、さらにＲ６のＣ４も既に発生しているので、第６番目はＲ７のＣ０となる。このようにして既に上位にある色すなわち、Ｒ０〜Ｒ３に出現するカラーシンボルを除いた色順位データがＲ０〜Ｒ３のデータに加わり、１６色のカラーシンボルの第１番目から１６番目までが決められる。なおこのとき、上位４つの周辺画素を学習により可変とすることもできる。
【００２７】
【発明が解決しようとする課題】
図２３に示される２次元の色順位変換を行うための色順位テーブルは、そのテーブルを作成する際、２次元的な周辺画素と１次元テーブルとの重複したカラーシンボルを１次元テーブルから削除する作業が必要となっている。１次元テーブルから重複したカラーシンボルを削除するこの処理は、カラーシンボルのインデックスコードのビット数が増加すると、莫大な処理量になってしまう。すなわち、図２３に示すように全カラーシンボルの数が１６色、すなわちインデックスコードとしては４ビットあれば十分な場合には、重複するカラーシンボルを検索し、該当するカラーシンボルを１次元テーブルから削除する作業もそれ程の負荷にはならないが、インデックスコードが８ビットとなると２５６色となり、重複するカラーシンボルを検索し、削除する作業は莫大となる。
【００２８】
例えば、周辺画素データＲ０，Ｒ１，Ｒ２，Ｒ３が全部異なる色であったとき、４色それぞれについて１次元テーブル中の２５６色から検索し、同じ色が見つかったところで、そのカラーシンボルを削除し、それ以後の順位を詰めて最後のカラーシンボルに２５６番目の順位を付ける作業を行う。このため、最高２５６×４回の比較を行わなければならない。この作業量は極めて莫大なものである。さらに、図２３に示す色順位テーブルを構成する１次元テーブルや、特開平６ー２７６０４１の図４５に示すような１次元テーブルのみから構成する色順位テーブルでは、複数のレジスタからなるＦＩＦＯを利用した、いわゆる先頭移動処理（Ｍｏｖｅ  ｔｏ  Ｆｒｏｎｔ）の最新出現表作成処理を行っている。この最新出現表作成時のソーティング処理も、インデックスコードのビット数の増加に伴い演算量が増大し、その処理量が増加する。このため、ビット数が多いインデックスコードを扱う場合には、マルチカラー画像の符号化や復号化の際の処理速度が低下してしまう。
【００２９】
また、図１６や図１９に示すような符号化システム５０のラインバッファ５１や復号化システム６０のラインバッファ６１は、参照画素や周辺画素を生成するために、多数の画素が保存できるものとなっている。このため、ラインバッファ５１，６１が大型化し、その結果、装置が大型化すると共に高価格なものとなる。また、図１６や図１９に示す従来の装置では、画像の横方向の長さを固定したサイズにして圧縮したり復号しているため、任意の画像サイズを効率良く圧縮したり復号化できないものとなっている。
【００３０】
本発明は、以上のような問題に対処してなされたものであり、符号化や復号化に際し、低容量のラインバッファ等の周辺画素生成手段を使用できるマルチカラー画像の符号化装置およびその方法ならびにマルチカラー画像の復号化装置およびその方法を提供することを目的とする。
【００３１】
【課題を解決するための手段】
かかる目的を達成するため、請求項１記載の発明では、入力される対象カラー画素データを符号化データに符号化し、出力するマルチカラー画像の符号化装置において、符号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切り、前記短冊に対応する画素データを出力する短冊生成手段と、前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素に対する周辺画素データおよび符号化対象画素の直前の画素を除いた周辺の４画素の参照画素に対する参照画素データを生成し、前記周辺画素データおよび参照画素データを出力するラインバッファ手段と、を有し、前記周辺画素データに基づいて、色順位テーブルを作成し、前記参照画素データに基づいてマルコフモデルのコンテクストを作成し、前記色順位テーブルおよび前記コンテクストに基づいて、前記各短冊内に位置する前記符号化対象画素を順次符号化する。
【００３２】
このように、対象画像を限定した画素数の横幅を有する短冊に区切っているので、ラインバッファ手段を具体化したラインバッファにより周辺画素生成や参照画素生成するに際し、回路規模やメモリ量を削減できる。この結果、装置の小型化、低コスト化が可能となる。
さらに、マルチカラー画像の符号化を行うにあたって、マルコフモデルのコンテクスト作成を直前の画素を除いた周辺の４画素である参照画素に基づいて行うので、符号化処理の高速化を図ることができる。
【００３３】
さらに請求項２記載の発明では、入力される対象カラー画素データを符号化データに符号化し、出力するマルチカラー画像の符号化方法において、符号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切り、前記短冊に対応する画素データを出力する短冊生成工程と、前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素に対する周辺画素データおよび符号化対象画素の直前の画素を除いた周辺の４画素である参照画素に対する参照画素データを生成し、前記周辺画素データおよび参照画素データを出力するラインバッファ工程と、を有し、前記周辺画素データに基づいて、色順位テーブルを作成し、前記参照画素データに基づいてマルコフモデルのコンテクストを作成し、前記色順位テーブルおよび前記コンテクストに基づいて、前記各短冊内に位置する前記符号化対象画素を順次符号化している。
【００３４】
このように、対象画像を限定した画素数の横幅を有する短冊に区切っているので、ラインバッファ工程に用いられる周辺画素生成工程や参照画素生成工程に使用されるラインバッファ等の回路規模、メモリ量を削減できる。この結果、この方法を具体化する装置の小型化や低コスト化が可能となる。
さらに、マルチカラー画像の符号化を行うにあたって、マルコフモデルのコンテクスト作成を直前の画素を除いた周辺の４画素である参照画素に基づいて行うので、符号化処理の高速化を図ることができる。
【００３５】
さらに、請求項３記載の発明では、入力される対象符号化データを復号化データに復号化し出力するマルチカラー画像の復号化装置において、復号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切って復号する短冊合成手段と、前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素データおよび参照画素データを生成し、前記周辺画素データおよび前記参照画素データを出力するラインバッファ手段と、を有し、前記周辺画素データに基づいて、色順位テーブルを作成し、直前の画素を除いた周辺の４画素の復号化データに基づいてマルコフモデルのコンテクストを作成し、前記色順位テーブルおよび前記コンテクストに基づいて、短冊状に前記復号化の対象となる対象画像を順次復号化している。
【００３６】
このように、対象画像を限定した画素数の横幅を有する短冊に区切っているので、ラインバッファ手段を具体化したラインバッファにより周辺画素生成や参照画素生成を行う際の回路規模、メモリ量を削減できる。この結果、装置の小型化、低コスト化が可能となる。
さらに、マルチカラー画像の復号化を行うにあたって、マルコフモデルのコンテクスト作成を直前の画素を除いた周辺の４画素である参照画素に基づいて行うので、復号化処理の高速化を図ることができる。
【００３７】
加えて、請求項４記載の発明では、入力される対象符号化データを復号化データに復号化し出力するマルチカラー画像の復号化方法において、復号化の対象となる対象画像を、限定した画素数の横幅を有する短冊に区切って復号する短冊合成工程と、前記短冊に対応する画素データに基づき、当該画素データに対応する２次元の周辺画素データおよび参照画素データを生成し、前記周辺画素データおよび前記参照画素データを出力するラインバッファ工程と、を有し、前記周辺画素データに基づいて、色順位テーブルを作成し、直前の画素を除いた周辺の４画素の復号化データに基づいてマルコフモデルのコンテクストを作成し、前記色順位テーブルおよび前記コンテクストに基づいて、短冊状に前記復号化の対象となる対象画像を順次復号化している。
【００３８】
このように、対象画像を限定した画素数の横幅を有する短冊に区切っているので、ラインバッファ工程に用いられる周辺画素生成や参照画素生成に使用されるラインバッファ等の回路規模やメモリ量を削減できる。この結果、この方法を具体化する装置の小型化、低コスト化が可能となる。
さらに、マルチカラー画像の復号化を行うにあたって、マルコフモデルのコンテクスト作成を直前の画素を除いた周辺の４画素の参照画素に基づいて行うので、復号化処理の高速化を図ることができる。
【００６５】
【発明の実施の形態】
本発明の実施の形態を図１から図１５に基づき説明する。なお、従来技術中のデータと対応する各データには、同一符号を付して説明する。
【００６６】
図１に、本発明に係るマルチカラー画像の符号化システム１の好適な実施の形態を示す。また、図２に、図１の符号化システム１に対応するマルチカラー画像の復号化システム３の好適な実施の形態を示す。
【００６７】
この符号化システム１は、短冊生成手段５と、周辺画素生成手段および参照画素生成手段となるラインバッファ１０と、縮退手段となるマルコフモデル生成部１１と、エントロピー符号化手段となるエントロピー符号器１２と、予測手段となる予測器１３とを含み、入力されるカラー画素データ１００Ａのデータストリームを符号化データ２００のデータストリームに変換して出力するように構成されている。
【００６８】
予測器１３は、色順位生成部１４と、エスケープ符号発生手段を兼ねる判別部１５とから構成される。また、色順位生成部１４は、上位の色順位を決める２次元色順位生成部１６と、下位の色順位を決める１次元色順位生成部１７と、両生成部１６，１７からの出力を入力し合成された色順位テーブル２３と生成する予測表合成部１８とから構成される。さらに、２次元色順位生成部１６は、優先順位切替部１９と、２次元色順位テーブル２０とから構成され、１次元色順位生成部１７は、テーブル更新部２１と、１次元色順位テーブル２２とから構成されている。
【００６９】
この実施の形態において、符号化の対象とするカラー画素データ１００Ａは、マルチカラーの画素であり、１画素当たり８ビットのインデックスコードのデータで構成され、２５６色分のカラーシンボルを表示できる。
【００７０】
入力されたカラー画素データ１００Ａは、ラインバッファ１０と、予測器１３内のテーブル更新部２１へ供給される。
【００７１】
ラインバッファ１０は、図３に示すように、対象となる画像を、限定した画素数の短冊に区切った部分の画素データを入力し保存する機能を有するものである。具体的には、図３に示すような全体画像をメモリ（図示省略）に取り込み、その後、そのメモリにアクセスしてデータを取りだす。その際、ＣＰＵなどの短冊生成手段５によって、データを図３に示す短冊Ｌ１〜Ｌ５の形状に取り出している。そして、ラインバッファ１０は、横幅１６画素に区切ったその各短冊Ｌ１〜Ｌ５中の少なくとも最新に入力された１７画素を保存するものである。そして、その値を周辺画素として２次元色順位生成部１６に入力し、２次元色順位テーブル２０を作成すると共に参照画素としてマルコフモデル生成部１１に入力し、状態信号Ｃｘを生成している。
【００７２】
マルコフモデル生成部１１は、図４に示すように、符号化対象画素Ｘに対して参照画素として直前の画素（「ー」で表示）を除いた周辺の４画素（Ａ，Ｂ，Ｃ，Ｄで表示）を取り入れ、状態信号Ｃｘを発生させている。ここで、直前の画素を採用せず、２画素前の画素であるＡを参照画素としたのは、次の理由による。従来どおりに直前の画素を参照画素として採用すると、その画素のカラーシンボルが確定するまでエントロピー符号器１２やエントロピー復号器３２に入力する状態信号Ｃｘ，すなわちマルコフモデルのコンテクストが確定せず、符号化や復号化の処理動作を高速化できない。本実施の形態では高速化の要請のため、２画素前の画素であるＡを参照画素として採用している。
【００７３】
エントロピー符号器１２は、図２１に示す算術型のエントロピー符号器となっている。すなわち、その内部に状態パラメータ毎の変換テーブル（図示省略）を有するものとなっている。
【００７４】
予測器１３は、予測手段として機能するものである。そして、符号化の対象となるカラー画素データ１００Ａが予測器１３内の色順位生成部１４と判別部１５にそれぞれ入力する。また、色順位生成部１４には、ラインバッファ１０から周辺画素データが入力される。
【００７５】
ラインバッファ１０から入力される周辺画素データは、優先順位切替部１９に入力される。この周辺画素データは、図５に示すように符号化対象画素Ｘの周辺の画素Ｐ０，Ｐ１，Ｐ２，Ｐ３としている。ここで、先に示したマルコフモデルの参照画素Ａ，Ｂ，Ｃ，Ｄとは、Ｂ＝Ｐ１，Ｃ＝Ｐ２，Ｄ＝Ｐ３となり、画素Ａのみが異なるものとなっている。
【００７６】
優先順位切替部１９は、２次元色順位テーブル２０を生成するための優先順位を所定の切り替え指令に基づき変更するように形成されるものである。しかし、この実施の形態では、Ｐ０，Ｐ１，Ｐ２，Ｐ３の順位と位置は、図５および図７に示すように固定されている。固定せずに切り替える方法としては、例えば、符号化の対象となる画像に対しプリスキャンを行い、良好な圧縮率が得られる周辺画素の優先順位パターンを予め求めておいたり、符号化や復号化の動作中にカラーシンボルの一致回数を計算し、一致回数の多い位置の画素を上位にもってくるような切り替え指令を出力するような方法が採用できる。
【００７７】
この優先順位切替部１９の指令に基づき、予測表合成部１８中の色順位テーブルの上位となる２次元色順位テーブル２０（図６参照）が作成される。予測表合成部１８中の色順位テーブルは図８に示すような、いわば最新出現表で、その上位、この実施の形態では、最高第０位から第３位までの上位４つを２次元色順位テーブル２０から求めている。なお、この２次元色順位テーブル２０は、メモリ（図示省略）に記憶される。
【００７８】
１次元色順位生成部１７中のテーブル更新部２１にカラー画素データ１００Ａが入力されると、テーブル更新部２１は、メモリに記憶されている１次元色順位テーブル２２内を検索し、入力カラー画素データに対応したカラーシンボルの色順位を、第０位に繰り上げる最新出現表作成動作を行う。例えば、図５のＴ０の位置のカラーシンボルＣ４が入力されると、テーブル更新部２１は、１次元色順位テーブル２２内を検索し、該当するカラーシンボルＣ４を取り出し、そのＣ４の色順位を第０位に繰り上げ、以前第０位であったＣ２を第１位に、第１位であったＣ０を第２位というように順次繰り下げる。そして、その更新された１次元色順位テーブル２２をメモリ（図示省略）に記憶させる。
【００７９】
１次元色順位生成部１７は、２５６個のレジスタからなるＦＩＦＯ部で構成しても良いが、この実施の形態では、処理速度の向上を図るために、第０位から第３１位までの上位計３２個のみをレジスタからなるＦＩＦＯ部で構成し、完全な最新出現表作成動作をさせている。一方、第３２位から第２５５位までは２２４バイトのデュアルポートのＲＡＭで構成し、該当するカラーシンボルが第３２位以下の第ｎ位のときは、該当するカラーシンボルを第０位に繰り上げ、元第３１位（＝３２番目）であったのものを第ｎ位に入れ替える処理を行っている。なお、第３２位以下をデュアルポートのＲＡＭで構成したのは、並行処理により処理速度を上げるためで、低価格化や小型化等を特に考慮する場合は、シングルポートのＲＡＭで構成するようにしても良い。
【００８０】
予測表合成部１８には、２次元色順位テーブル２０のデータと、１次元色順位テーブル２２のデータとが入力され、図８に示される一種の最新出現表となる色順位テーブル２３が作成される。この色順位テーブル２３は、図８に示すように、最大第０位から第３位までが２次元色順位テーブル２０に相当する周辺画素から構成される。例えば、周辺画素のＰ０，Ｐ１，Ｐ２，Ｐ３の色が全て異なるときは、第０位から第３位までをそれらの画素が占めることとなる。一方、Ｐ０からＰ３までが全て同じ色のときは、第０位のみを占め、１次元色順位テーブル２２の第１位のものが、この色順位テーブル２３でも第１位となる。
【００８１】
この色順位テーブル２３は、第０位が、２次元色順位テーブル２０の第０位であり、しかも１次元色順位テーブル２２の第０位でもある。また、第２５５位、すなわち、上から２５６番目以後の順位のものには、コードとしてエスケープ符号を付すようにしている。具体的には、第２５５位には、“１１１１１１１１”で現されるエスケープ符号と、“００００００００”で現される「０」を示すコードとを出力するようにしている。また、第２５６位には同じく“１１１１１１１１”のエスケープ符号と、“０００００００１”の「１」を示すコードとを出力するようにしている。
【００８２】
このように、合成された色順位テーブル２３は、周辺の画素の値である２次元色順位テーブル２０の値と１次元色順位テーブル２２との重複部分を削除しない構成となっており、削除を行うための検索（比較）動作が不要となり高速化される。なお、圧縮率の劣化は従来のものに比べ１％以下である一方、処理速度は２倍以上速くなっている。また、このようなエスケープ符号を使用せずに、色順位のコードのビット数を増加させて対応する手段も考えられるが、その場合は、ビット数の増加により符号化の効率が大幅に劣化してしまう。これに対し、エスケープ符号の利用は、圧縮率がほとんど劣化しないので極めて有利となる。
【００８３】
合成された色順位テーブル２３のデータが判別部１５へ出力される。判別部１５は、合成された色順位テーブル２３のデータと、符号化しようとするカラー画素データ１００Ａのカラーシンボルとを照合し、符号化しようとするカラー画素データ１００Ａに対応した色順位データ１２０を出力するものとなっている。
【００８４】
エントロピー符号器１２は、先の状態信号Ｃｘとこの色順位データ１２０を入力し、符号化データ２００として出力する。
【００８５】
次に、以上の構成を有する符号化システム１の動作について、図１０に示すフローチャートに基づいて説明する。なお、説明に当たって、まず通常の場合の動作を説明し、次に各短冊Ｌ１〜Ｌ６の端部の例外処理について説明する。
【００８６】
符号化に際しては、まず、メモリからデータを短冊状に取りだすための短冊生成工程が行われる。その後、具体的に各画素の符号化を開始する。通常の符号化処理においては、符号化対象画素より２つ前のカラー画素データ１００Ａが既に入力済（ステップＳ１）となっている。このデータおよび１ライン上の３つの参照画素のデータからマルコフモデル作成部１１によってマルコフモデルのコンテクストが作成される（ステップＳ２）。
【００８７】
このコンテクスト作成処理と併行して、色順位変換のため次の処理が行われる。すなわち、符号化対象画素の１画素前のデータも入力済（ステップＳ３）で、その画素の入力によって周辺画素の入力が全て完了し（ステップＳ４）、２次元色順位テーブル２０が作成される（ステップＳ５）。一方、符号化対象画素の１画素前のデータの入力は、１次元色順位生成部１７への直前画素入力（ステップＳ６）と同一であり、その入力により１次元色順位テーブル２２が作成される（ステップＳ７）。
【００８８】
次に、２次元色順位テーブル２０および１次元色順位テーブル２２の各データが予測表合成部１８へ入力し、合成された色順位テーブル２３が作成される（ステップＳ８）。このとき、第２５５位（第２５６番目）以下の順位のカラーシンボルには、全てエスケープ符号（＝“１１１１１１１１”）とそれぞれ異なる番号（０〜３）が付与される。
【００８９】
次に、符号化対象のカラー画素データ１００Ａが入力してきて（ステップＳ９）、合成された色順位テーブル２３のデータと照合される（ステップＳ１０）。カラー画素データ１００Ａが、２次元色順位テーブル２０中のものと異なるとき、１次元色順位テーブル２２に相当する部分を検索し、該当するカラーシンボルを見つけ出す。そして、そのカラーシンボルが例えば１次元色順位テーブル２２中の第１０位（１１番目）にあるとき、仮に２次元色順位テーブル２０中の順位が４つあるとすると、３をプラスして、第１３位となる色順位データ１２０を出力する（ステップＳ１１）。このように、実質的な検索は、２次元色順位テーブル２０と１次元色順位テーブル２２に対して行われ、２次元色順位テーブル２０中に見つかるときは、その検索された順位をそのまま出力し、１次元色順位テーブル２２中にあるときは、所定の値をプラスして出力する。
【００９０】
一方、その該当したカラーシンボルを１次元色順位テーブル２２の第０位にもってくると共に、２次元色順位テーブル２０および合成された色順位テーブル２３の各第０位にそのカラーシンボルをもってくる。このような各テーブル２０，２２，２３の更新作業をステップＳ１２にて行う。この際、１次元色順位テーブル２２および合成された色順位テーブル２３の下位の部分では、その値が第０位から第３１位までのときは、完全な最新出現表作成動作を行い、最新のものが第０位に上がり、その他のものは１つずつ繰り下がる。しかし、第３２位以下のものが対象となったときは図９に示すように、元の第３１位のものを該当の順位の所にもってくる入れ替え処理を行っている。
【００９１】
出力された色順位データ１２０と、マルコフモデルのコンテクスト、すなわち状態信号Ｃｘとからエントロピー符号器１２で、符号化処理を行い（ステップＳ１３）、符号化データ２００を出力する（ステップＳ１４）。そして、符号化が終了するのか否か判断し（ステップＳ１５）、終了の場合は符号化を終了し、継続のときはステップＳ９に戻る。
【００９２】
以上が通常の符号化のステップとなる。次に、各短冊Ｌ１〜Ｌ５の端部の例外処理について、説明する。
【００９３】
まず、最初の短冊Ｌ１の最初の部分、すなわち図１１（Ａ）の最上部の左端の画素を符号化するときについて説明する。まず、対象となる符号化対象カラー画素データ１００Ａが入力される。すなわち、ステップＳ９が最初に実行される。このとき、周辺画素は入力されていないので、２次元色順位テーブル２０は、１次元色順位テーブル２２の第０位のものに全て初期化され、一方、１次元色順位テーブル２２も、２５６色のカラーシンボルが第０位から第２５５位までに並べられて初期化されている。このため、合成された色順位テーブル２３としては第０位から第２５５位までに並べられた２５６色のカラーシンボルの表が予測表合成部１８内に存在することとなる。また、ラインバッファ１０内も、当初はすべて「０」に初期化されている。なお、ラインバッファ１０の初期値として、「０」以外の値のカラーシンボルを採用するようにしても良い。
【００９４】
その後は、図１０に示すステップＳ１０、Ｓ１１，Ｓ１２，Ｓ１３，Ｓ１４，Ｓ１５の作業を行い、ステップＳ９に戻る。このとき、各テーブルの更新（ステップＳ１２）における２次元色順位テーブル２０の更新では、２次元色順位テーブル２０のＰ０の位置に入力されたカラー画素に対応するカラーシンボルを入れ込む処理をする。Ｐ１，Ｐ２，Ｐ３は、まだ生じていないので、ラインバッファ１０の初期値「０」がカラーシンボルとなる。一方、１次元色順位テーブル２２では、第０位の位置に入力されたカラー画素に対応するそのカラーシンボルを繰り上げる先頭移動処理すなわち最新出現表作成動作を行う。
【００９５】
図１１（Ｂ）に示す短冊Ｌ１の最上ラインでは、常に周辺画素としてはＰ０のみが入力されている状態となっている。一方、１次元色順位テーブル２２は、常に最新出現表作成動作が行われ、最も最新に入力されてきたカラーシンボルを最上位に上げる処理を行っている。なお、マルコフモデルのコンテクストは、第１番目の画素の入力時には本来のものは作成されておらず、状態信号Ｃｘとしては仮の値として１色としてＣｘ＝０を出力している。第２番目の画素の入力時も同様で、第３番目の画素の入力時点から図４に示すＡの値が確定してくるが、やはり本来のマルコフモデルは形成できない。しかし、１ライン上の画素のカラーシンボル、すなわちインデックスが「０」に初期化されているので、Ｐ０のカラーシンボルが「０」であれば、状態信号は、１色を示すＣｘ＝０が出力され、Ｐ０のカラーシンボルが「０」でなければ、状態信号は、２色を示すＣｘ＝１が出力される。
【００９６】
その後、短冊Ｌ１の第２ラインの左端（第１７番目の画素）のカラー画素データ１００Ａが入力されてくると、周辺画素としてのＰ０，Ｐ１，Ｐ２は図１２（Ａ）に示すとおりとなる。すなわち、符号化対象画素Ｘの１画素前がＰ０で、１５画素前がＰ２で、１６画素前、すなわち１ライン上の同位置にくるのがＰ１となる。そして、Ｐ３はまだ生じていないので、カラーシンボル「０」が入っているものとして処理する。
【００９７】
このように、この実施の形態では、周辺画素Ｐ０〜Ｐ３や参照画素Ａ〜Ｄを符号化対象画素Ｘからラインバッファ１０内で一定距離離れた位置の値としている。すなわち、図１２（Ｂ）にも示されているように周辺画素Ｐ０は、１つ前、参照画素Ａは２つ前、周辺画素Ｐ２（これは参照画素Ｃでもある）は１５個前、周辺画素Ｐ１（これは参照画素Ｂでもある）は１６個前、すなわち符号化対象画素の１ライン前の同じ位置、周辺画素Ｐ３（これは参照画素Ｄでもある）は１７個前となる。以上のような考え方は、図１２（Ｃ）に示すように、符号化対象画素Ｘや周辺画素等が、短冊Ｌ２と短冊Ｌ１に分離されている場合も同様となる。このようにして、１７個分の画素をラインバッファ１０内に保存しておけば参照画素や周辺画素として常に利用できることとなる。また、ラインバッファ１０の初期値として「０」をセットするという簡単な作業を行うものの、符号化の途中で、「０」の値を仮想的に入れ込む等の煩わしい例外処理を行ってはいない。すなわち、この実施の形態では、煩わしい例外処理を特別に施すことなく、１つの短冊から次の短冊へ通常と変わらない同じ処理動作で進むことができる。
【００９８】
また、短冊を横幅１６画素単位で区切っていった場合、図３に示すように最後の短冊Ｌ５の横幅が１６画素未満となることがある。その場合、その短冊Ｌ５の横幅が４画素以上の場合、図１３に示すように、その横幅の画素数をｎとすると、Ｐ０は符号化対象画素の１つ前、参照画素Ａは２つ前、周辺画素Ｐ２（参照画素Ｃ）は（ｎー１）個前、周辺画素Ｐ１（参照画素Ｂ）はｎ個前、周辺画素Ｐ３（参照画素Ｄ）は（ｎ＋１）個前となる。
【００９９】
短冊Ｌ５の横幅が３画素であると、図１４（Ａ）に示すように、参照画素Ａが参照画素Ｃと同一となり周辺画素Ｐ２の場所となる。その他は横幅４画素のときと同じ関係となる。短冊Ｌ５の横幅が２画素であると、図１４（Ｂ）に示すように、符号化対象画素Ｘの１つ前がＰ０となり、２つ前がＰ１となり、３つ前がＰ３となる。ここで、Ｐ２は、図１３に示す関係では、（２−１）個前、すなわち１つ前となりＰ０と同じ値となる。しかし、Ｐ２に対応する参照画素Ｃは、１つ前とはならずＰ１の位置のものとなる。このため、参照画素Ｂ，Ｃ，Ａが全てＰ１の位置となる。さらに、短冊Ｌ５の横幅が１画素であると、同様に図１３の関係を準用し、図１４（Ｃ）に示すように、符号化対象画素Ｘの１つ前がＰ０，Ｐ１，Ｐ２を示し、２つ前がＰ３を示すものとなる。ここで、参照画素Ａ，Ｂ，Ｃ，Ｄは全て同じでＰ３の位置のものとなる。
【０１００】
以上のような例外処理を行うと、例えば端部について、周辺画素や参照画素の位置関係上足りない部分に仮想的に“０”をおいて処理したり、横幅１６画素未満の短冊については、横幅１６画素となるように処理する場合に比べ処理が効率化されると共に、横幅自由な画素数の画像を簡単に扱えるようになる。
【０１０１】
次に、符号化システム１に対応したマルチカラー画像の復号化システム３について説明する。
【０１０２】
この復号化システム３は、短冊合成手段７と、周辺画素生成手段および参照画素生成手段となるラインバッファ３０と、縮退手段となるマルコフモデル生成部３１と、エントロピー復号化手段となるエントロピー復号器３２と、予測手段となる予測器３３とを含み、入力される符号化データ２００のデータストリームをカラー画素データ１００Ｂのデータストリームに変換して出力するように形成されている。このとき、復号化システム３のアルゴリズムは、符号化システム１のアルゴリズムと全く逆のアルゴリズムになるように構成されている。したがってカラー画素データ１００Ａのビット構成およびデータストリームと、カラー画素データ１００Ｂのビット構成およびデータストリームとは全く同じものとなる。予測器３３は、符号化システム１中の予測器１３と全く同一構成となっている。すなわち、予測器３３は、色順位生成部１４と、エスケープ符号化発生手段を兼ねる判別部１５とから構成される。また、色順位生成部１４は、上位の色順位を決める２次元色順位生成部１６と、下位の色順位を決める１次元色順位生成部１７と、両生成部１６，１７からの出力を入力し合成された色順位テーブル２３を生成する予測表合成部１８とから構成される。さらに、２次元色順位生成部１６は、優先順位切替部１９と、２次元色順位テーブル２０とから構成され、１次元色順位生成部１７は、テーブル更新部２１と、１次元色順位テーブル２２とから構成されている。
【０１０３】
ラインバッファ３０は、符号化システム１のラインバッファ１０と同様に少なくとも１７画素分を保存できるものとなっている。そして、その値を周辺画素として２次元色順位生成部１６に入力し、２次元色順位テーブル２０を作成すると共に、参照画素としてマルコフモデル生成部３１に入力し状態信号Ｃｘを生成している。
【０１０４】
エントロピー復号器３２は、状態信号Ｃｘを利用して、入力する符号化データ２００を、エントロピー符号器１２と逆の手順で復号化演算処理し、これを色順位データ１２０に変換して予測器３３へ向け出力する。なお、エントロピー復号器３２は、エントロピー符号器１２とは全く逆のアルゴリズムでその演算を行うように形成しなければならない。したがって、エントロピー復号器３２は、エントロピー符号器１２に算術符号器が用いられた場合には、それと同様な構成の算術復号器として形成する必要があり、また、エントロピー符号器１２にハフマン符号器が用いられた場合には、それと同じ構成のハフマン復号器として構成する必要がある。これにより、符号化データ２００は、これと対をなす色順位データ１２０に正確に変換して出力されることとなる。
【０１０５】
予測器３３は、予測手段として機能するものである。そして、その内部に符号化システム１の予測器１３と同一の合成された色順位テーブル２３が設定されており、入力される色順位データ１２０および周辺画素のデータに基づき、色順位テーブル２３から対応するカラーシンボルをカラー画素データ１００Ｂとして復号化し出力する。
【０１０６】
次に、このように構成される復号化システム３の動作について、図１５に示すフローチャートに基づいて説明する。
【０１０７】
まず、復号化対象画素の符号化データ２００がエントロピー符号器３２へ入力する（ステップＳ３１）。一方、２画素前のデータに基づきマルコフモデルのコンテクストが作成され（ステップＳ３２）、状態信号Ｃｘとしてエントロピー復号器３２へ入力する。エントロピー復号器３２は、符号化データ２００を、状態信号Ｃｘを利用して復号化処理する（ステップＳ３３）。
【０１０８】
エントロピー復号器３２による復号化処理によって、色順位データ１２０が出力し（ステップＳ３４）、予測器３３内の判別部１５へ入力する。
【０１０９】
一方、既にカラー画素データ１００Ｂとして復号化されたデータは、ラインバッファ３０を経由して周辺画素として予測器３３の優先順位切替部１９へ入力する（ステップＳ３５）と共に予測器３３内のテーブル更新部２１へ直前画素として入力する（ステップＳ３６）。周辺画素が入力されると、２次元色順位テーブル２０が作成される（ステップＳ３７）。直前画素が入力されると、１次元色順位テーブル２２が作成される（ステップＳ３８）。
【０１１０】
ここで２次元色順位テーブル２０は、図６に示すものと同一で、１次元色順位テーブル２２は、図７に示すものと同一となっている。そして、テーブル更新部２１は、図９に示すように、第０位から第３１位までが完全な先頭移動動作を行うＦＩＦＯ部となり、その下位は２２４バイトからなるＲＡＭで構成されるものとなっている。
【０１１１】
予測表合成部１８で、両テーブル２０，２２から合成された色順位テーブル２３を作成する（ステップＳ３９）。この色順位テーブル２３のデータは、判別部１５へ入力し、先の色順位データ１２０と照合される（ステップＳ４０）。ここで色順位データは、例えば第６３位のものであると“００１１１１１１”なる符号で、第２５６位であると、エスケープ符号“１１１１１１１１”と“０００００００１”の符号となる。そして、照合の結果、合成された色順位テーブル２３中の該当する順位の所のカラーシンボルのカラー画素データ１００Ｂ（＝インデックスコード）を出力する（ステップＳ４１）。
【０１１２】
次に、例えば、第２位のコードが出てきたとき、対応するカラーシンボルのカラー画素データ１００Ｂを出力すると共に、合成された色順位テーブル２３中のそのカラーシンボルを第０位に繰り上げ、第０位のものを第１位に、第１位のものを第２位に繰り下げる更新処理を行う（ステップＳ４２）。この更新は、２次元色順位テーブル２０や１次元色順位テーブル２２についても必要により適宜行われる。
【０１１３】
なお、更新作業の際、２次元色順位テーブル２０は、Ｐ０，Ｐ１，Ｐ２，Ｐ３の順位が決まっているが、もし、復号化されるものがＰ０，Ｐ１，Ｐ２，Ｐ３のいずれかと同一であると、例えば、第２位にあるＰ２と同一であると、そのカラーシンボルを第０位に繰り上げる。このとき、１次元色順位テーブル２２について、全く先頭移動処理を行わないとすると、符号化時の１次元色順位テーブル２２とは異なるものとなってしまう。このため、２次元色順位テーブル２２中の第２位の位置にあったカラーシンボルと同一のカラーシンボルを１次元色順位テーブル２２の中で検索し、そのカラーシンボルを第０位に上げ、その他のものを並び替える先頭移動処理を行わせる。
【０１１４】
このとき、この１次元色順位テーブル２２の検索は、１次元色順位テーブル２２の中の第０位から第１６位までの上位１７個の検索に限定できる。すなわち、Ｐ０〜Ｐ３は、１次元色順位テーブル２２の中の最新１７個の画素の１つであるためである。このように、復号化される画素がＰ０〜Ｐ３のいずれか１つであると、１次元色順位テーブル２２の更新のためには、最高１７回の検索（比較）のみで良くなる。このように、最高１７回に限定されるのは、画像が横幅１６画素の短冊に区切られているため、ラインバッファ１０に保存する参照画素を１７個に限定できるためである。
【０１１５】
一方、復号化される画素がＰ０〜Ｐ３のいずれでもないときは、色順位データ１２０、例えば第１５０位と示す色順位データ１２０がステップＳ３４で出力されると、Ｐ０〜Ｐ３で計４色となるときは、その色順位データ１２０に相当するものは、１次元色順位テーブル２２中では、第１５３位に相当するものとなるので、検索をせず直接第１５３位のカラーシンボルを抜き出し第０位に繰り上げることとなる。
【０１１６】
このように、復号化の場合、最高１６個の検索（比較）が行われるが、この１６回という検索（比較）回数は、特開平６ー２７６０４１で示される従来の技術における重複カラーの削除のための検索回数（２５６×４）に比べれば極めて少なくなっており、非常な高速処理が可能となる。なお、復号化時の検索を符号化時と等価なものとし、１次元色順位テーブル２２内を全て検索するようにしても良いが、高速処理の点では、上述した実施の形態の方が好ましい。
【０１１７】
カラー画素データ１００Ｂが出力されると、ステップＳ４３で復号化が終了なのか否か判断する。そして、新たな符号化データ２００の入力がなく、復号化が終了であると判断すると終了する。一方、継続のときはステップＳ３１に戻る。なお、復号化の際においても、短冊の端部や小さい幅の短冊に関する例外処理が図１１から図１４に示すものと同様なアルゴリズムで実行される。また、復号化されたカラー画素データ１００Ｂは、短冊合成手段７による短冊復号工程によって短冊状に復号され、そのデータがメモリ（図示省略）に取り込まれ、図３に示すような全体画像として復号される。
【０１１８】
なお、この実施の形態において、第２５５位以下の順位のものはエスケープ符号と、全体順位（第１番目から数えるもの）から２５６を引いた数値を示す符号の２つの符号（計１６ビット）を出力することとなるが、第２５５位以下というような順位が低いものは、ほとんど発生しないカラーコードを示しており、そのような２つの符号を出力することはほとんど発生しない。しかも、発生したとしてもその後は、出やすい順位に割り当てられるので、先に示したように圧縮率はほとんど劣化しない。これに比べ重複するカラーコードを削除し、順番を入れ替えるソーティング処理をなくすことができる効果は極めて大きなものとなる。
【０１１９】
この実施の形態のマルコフモデルは、従来のものと異なり、符号化対象画素の直前の画素を参照画素として採用していないが、圧縮率の劣化は数％に抑えられている。一方、処理速度は、エントロピー符号器１２やエントロピー復号器３２と色順位変換とのパイプライン処理が可能となり、２倍以上に高速化されている。なお、この実施の形態では、直前画素を周辺画素としては利用しているが、この実施の形態とは異なり、直前の画素を色順位テーブル２３の作成のための周辺画素としても採用しない場合においても、圧縮率の劣化は１０％程度に抑えられる一方、処理速度は２倍以上となる。
【０１２０】
さらに、この実施の形態のラインバッファ１０，３０は画像が短冊に区切られているため、小容量のものとすることができる。すなわち、マルコフモデルの参照画素、色順位変換のための周辺画素としては、１ライン上の画素を見る必要があるが、短冊的に横幅が区切られているので、１ライン上の画素を見るために保存しておくべき画素の数が少なくなる。このため、ラインバッファ１０，３０は小型化、小容量化でき、低コスト化できる。
【０１２１】
なお、上述の実施の形態は、本発明の好適な実施の形態の例であるが、これに限定されるものではなく本発明の要旨を逸脱しない範囲において、種々変形実施可能である。例えば、カラー画素データ１００Ａとしては、ｎビット（ｎは２以上の整数）のカラー画素データ１００Ａを対象とし、その符号化や復号化を行うように構成することができる。
【０１２２】
また、対象画像を短冊に区切る方法は、図２３に示す重複したカラーシンボルを削除する従来の装置や方法に適用することもできる。その場合、処理を高速化できるという効果を有するものとなる。また、本実施の形態に示す合成された色順位テーブル２３や図２３に示す従来の合成された色順位テーブルを持たない、図１６に示すような通常の符号化システム５０や復号化システム６０に、対象画像を短冊に区切る方法を採用することもできる。その場合、ラインバッファ５１，６１の低容量化、低コスト化等の効果を有するものとなる。
【０１２３】
さらに、短冊の横幅としては、ラインバッファ１０，３０の容量等を考慮すると８〜６４画素が好ましいが、検索効率や端部の例外処理による圧縮効率を考慮すると１６〜３２画素が最も好ましい。さらに、１次元色順位生成部１７内のＦＩＦＯ部とＲＡＭの構成比としては、ＦＩＦＯ部を全体の１／４〜１／３２として残りをＲＡＭとするのが好ましく、ＦＩＦＯ部を１／８〜１／１６として残りをＲＡＭとするのが、圧縮率がそれ程落ちず、しかも高速処理することができる点で最も好ましい。
【０１２４】
また、符号化や復号化の手段としては、算術符号型のエントロピー符号器１２や復号器３２の他に、ランレングス符号化（復号化）技術や他の符号化（復号化）技術を採用することができる。
【０１２５】
さらに、マルコフモデルのコンテクストとしては、１色から４色の４状態以外に図２０に示すように異なる色がどこにあるかによって状態信号Ｃｘも異ならせるようにしたりする等他の状態信号Ｃｘを発生させるようにしても良い。
【０１２６】
また、マルコフモデルの参照画素と色順位変換のための周辺画素とを異ならしめるには、この実施の形態で示すように１画素前のものを参照画素として採用せず２画素前のものを採用する他に、３画素以上の前の参照画素として採用するようにしても良い。すなわち、１画素前に加え、２画素前の画素も参照画素として採用しないようにしても良い。
【０１２７】
このマルコフモデルのコンテクスト作成技術、すなわち、符号化対象画素の直前の画素を参照画素として採用しない技術は、色順位変換を行わせる技術と併行してきはなく単独として各種の符号化や復号化の技術に利用することができる。
【０１２８】
【発明の効果】
以上説明したように、本発明のマルチカラー画像の符号化装置およびその方法では、対象画像を短冊に区切ることにより、演算量の大幅な削減が可能となり符号化処理を高速化できると共に任意の画像サイズのマルチカラー画像を効率良く符号化できる。しかも、符号化に際し利用する周辺画素生成手段等、例えばラインバッファ等を低容量化かつ低コスト化させることができる。
【０１２９】
また、本発明のマルチカラー画像の復号化装置およびその方法では、対象画像を短冊に区切ることにより、演算量の大幅な削減が可能となり復号化処理を高速化できると共に任意の画像サイズのマルチカラー画像を効率良く符号化できる。しかも、復号化に際し利用する周辺画素生成手段等となるラインバッファを低容量化かつ低コスト化させることができる。
【図面の簡単な説明】
【図１】本発明のマルチカラー画像の符号化装置およびその方法を採用した符号化システムを示す図である。
【図２】本発明のマルチカラー画像の復号化装置およびその方法を採用した復号化システムを示す図である。
【図３】図１および図２の符号化システムおよび復号化システムに採用されるスキャン方法を説明するための図である。
【図４】図１および図２の符号化システムおよび復号化システムに採用されるマルコフモデルとそのコンテクストを説明する図で、（Ａ）はマルコフモデルとして採用する参照画素の配置を示す図で、（Ｂ）はマルコフモデルのコンテクスト、すなわち状態信号の種類を示す図である。
【図５】図１および図２の符号化システムおよび復号化システムに採用される色順位テーブルの作成に使用される画素を説明するための図で、（Ａ）は使用される画素の配置と画素優先順位を示す図で、（Ｂ）は（Ａ）の各画素のカラーシンボルを示す図である。
【図６】図１および図２の符号化システムおよび復号化システムに採用される２次元色順位テーブルを示す図である。
【図７】図１および図２の符号化システムおよび復号化システムに採用される１次元色順位テーブルを示す図である。
【図８】図１および図２の符号化システムおよび復号化システムに採用される合成された色順位テーブルを示す図である。
【図９】図１および図２の符号化システムおよび復号化システムに採用される１次元色順位テーブルの構成とその更新処理を説明するための図である。
【図１０】図１の符号化システムにおける符号化動作を示すフローチャートである。
【図１１】図１の符号化システムの符号化動作における２次元色順位テーブル用の周辺画素の取扱いを説明する図で、（Ａ）は最も初めの符号化対象画素を符号化する場合を説明するための図で、（Ｂ）は第１番目のライン中の符号化対象画素を符号化する場合を説明するための図である。
【図１２】図１の符号化システムの符号化動作における２次元色順位テーブル用の周辺画素の取扱いを説明する図で、（Ａ）は符号化対象画素が第２ラインの始めにきたときの符号化を説明するための図で、（Ｂ）は符号化対象画素が第２ラインの終端にきたときの符号化を説明するための図で、（Ｃ）は符号化対象画素が隣の短冊の最初の部分にきたときの符号化を説明するための図である。
【図１３】図１の符号化システムの符号化動作における２次元色順位テーブル用の周辺画素およびマルコフモデル用の参照画素の取扱いを説明する図で、狭幅の短冊でも通常の短冊と同様な考えで取り扱うことができる場合を示す図である。
【図１４】図１の符号化システムの符号化動作における２次元色順位テーブル用の周辺画素およびマルコフモデル用の参照画素の取扱いを説明する図で、通常の短冊とは異なる例外処理を施す必要がある場合を示し、（Ａ）は横幅が３画素のときを、（Ｂ）は２画素のときを、（Ｃ）は１画素のときをそれぞれ示す図である。
【図１５】図２の復号化システムにおける復号化動作を示すフローチャートである。
【図１６】従来のマルチカラー画像の符号化システムおよび復号化システムのブロック図である。
【図１７】従来の符号化対象画素データに対する参照画素データの説明図である。
【図１８】従来のパラメータテーブルを示す図である。
【図１９】状態縮退器を有する従来のマルチカラー画像の符号化システムおよび復号化システムのブロック図である。
【図２０】従来の縮退テーブルの一例を示す図である。
【図２１】従来の算術符号型のエントロピー符号器およびエントロピー復号器の説明図である。
【図２２】従来のマルチカラー画像のインデックスを説明するための図である。
【図２３】従来の合成された色順位テーブルの作成原理を示す説明図で、（Ａ）は各画素の配置関係を示し、（Ｂ）は各画素のカラーシンボルを示し、（Ｃ）は合成された色順位テーブル（最新出現表）を示す図である。
【符号の説明】
１  符号化システム
３  復号化システム
５  短冊生成手段
７  短冊合成手段
１０  ラインバッファ（周辺画素生成手段）
１１  マルコフモデル作成部（縮退手段）
１２  エントロピー符号器（エントロピー符号化手段）
１３  予測器（予測手段）
１４  色順位生成部
１５  判別部（エスケープ符号発生手段を兼ねる）
１６  ２次元色順位生成部
１７  １次元色順位生成部
１８  予測表合成部
１９  優先順位切替部
２０  ２次元色順位テーブル
２１  テーブル更新部
２２  １次元色順位テーブル
２３  合成された色順位テーブル
３０  ラインバッファ
３１  マルコフモデル生成部（縮退手段）
３２  エントロピー復号器（エントロピー復号化手段）
３３  予測器
１００Ａ  符号化されるカラー画素データ
１００Ｂ  復号化されたカラー画素データ
１２０  色順位データ
２００  符号化データ
【図１】
0004034385.tif 000002
【図２】
0004034385.tif 000003
【図３】
0004034385.tif 000004
【図４】
0004034385.tif 000005
【図５】
0004034385.tif 000006
【図６】
0004034385.tif 000007
【図７】
0004034385.tif 000008
【図８】
0004034385.tif 000009
【図９】
0004034385.tif 000010
【図１０】
0004034385.tif 000011
【図１１】
0004034385.tif 000012
【図１２】
0004034385.tif 000013
【図１３】
0004034385.tif 000014
【図１４】
0004034385.tif 000015
【図１５】
0004034385.tif 000016
【図１６】
0004034385.tif 000017
【図１７】
0004034385.tif 000018
【図１８】
0004034385.tif 000019
【図１９】
0004034385.tif 000020
【図２０】
0004034385.tif 000021
【図２１】
0004034385.tif 000022
【図２２】
0004034385.tif 000023
【図２３】
0004034385.tif 000024