(57)【特許請求の範囲】
【請求項１】
入力画像の所定の処理単位に含まれる色のうち、第１参照パレットに含まれない色を保持する追加パレットを決定する決定部と、
前記追加パレットに含まれる色と、前記第１参照パレットに含まれる色とを含む符号化用パレットを生成する第１パレット生成部と、
前記処理単位の各画素に、前記画素の色に対応する前記符号化用パレットの色を示すインデックスを割り当てる第１割り当て部と、
前記インデックスと、前記追加パレットの情報とを符号化する符号化部と、
前記符号化用パレットから前記第１参照パレットを生成する第１参照生成部と、
を備え、
前記第１割り当て部は、前記処理単位の前記各画素の色に対応する色として前記符号化用パレットの色が参照された参照回数を算出し、
前記第１参照生成部は、前記符号化用パレットに基づいて、該符号化用パレットの色数と同じ色数の前記第１参照パレットを生成し、
前記第１パレット生成部は、前記第１参照パレットの色のうち前記参照回数の少ない色から、前記追加パレットの色数の色を除いた残りの色と、該追加パレットの色とを含む前記符号化用パレットを生成する符号化装置。
【請求項２】
前記符号化部は、前記符号化用パレットの色のうち前記第１参照パレットの色に対応する前記インデックスを符号化する場合、前記参照回数が多い色に対応する該インデックスほど短い符号で符号化する請求項１に記載の符号化装置。
【請求項３】
前記符号化部は、前記符号化用パレットの色のうち前記第１参照パレットの色に対応する前記インデックスに対応する符号より短い符号によって、該符号化用パレットの色のうち前記追加パレットの色に対応する前記インデックスを符号化する請求項１に記載の符号化装置。
【請求項４】
前記第１割り当て部は、前記処理単位の各画素に、前記インデックスが示す前記符号化用パレットの色を割り当てることにより局所画像を生成し、
前記局所画像を記憶する記憶部を、さらに備え、
前記決定部は、前記追加パレットの色のうち、前記記憶部に記憶された前記局所画像の画素であって前記処理単位に隣接する参照画素の色と一致する色がある場合、前記追加パレットの前記一致する色を、対応する前記参照画素の色に置き換え、
前記符号化部は、前記追加パレットの情報を符号化する場合、前記追加パレットの色のうち前記参照画素に対応する色については該参照画素の情報を符号化する請求項１に記載の符号化装置。
【請求項５】
前記符号化部は、前記処理単位の各画素について、前記各画素に対応する前記インデックスを符号化し、該インデックスに対応する色が前記追加パレットの色であり、かつ、該追加パレットの色の情報が符号化されていない場合に、該情報を符号化する請求項１に記載の符号化装置。
【請求項６】
前記決定部は、前記処理単位に含まれる色のコンポーネントの値と、前記第１参照パレットに含まれる色のコンポーネントの値との差異が閾値より大きいと判定した場合、該処理単位に含まれる色は、前記第１参照パレットに含まれないと判定し、
前記閾値を変更することによって、前記追加パレットの色数を制御する制御部を、さらに備えた請求項１に記載の符号化装置。
【請求項７】
請求項１に記載された符号化装置により符号化された前記インデックス、および前記追加パレットの情報を復号する復号部と、
前記復号部により復号された前記追加パレットの色と、第２参照パレットに含まれる色とを含む復号用パレットを生成する第２パレット生成部と、
所定の処理単位の各画素に、前記復号部により復号された前記インデックスに対応する前記復号用パレットの色をそれぞれ割り当てる第２割り当て部と、
前記復号用パレットから前記第２参照パレットを生成する第２参照生成部と、
を備えた復号装置。
【請求項８】
請求項１に記載された符号化装置と、
請求項７に記載された復号装置と、
を備えた画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、符号化装置、復号装置および画像処理装置に関する。
【背景技術】
【０００２】
従来から、画像を符号化する方式の１つとして、画像を、その画像に含まれる１以上の色を保持するパレットと、画像の各画素がパレットのいずれの色であるかを示すインデックスとで表現するカラーパレット符号化方式が知られている。このカラーパレット符号化方式において、画像の符号化の効率を高めるためには、パレットまたはインデックスを効率よく符号化する方法が重要である。
【０００３】
このようなカラーパレット符号化方式を適用した技術として、符号化対象の画素よりも前に符号化された画素からパレットを作成することで、符号化効率を高める技術がある。また、入力画像（またはその一部）から予め色の出現頻度を取得し、その頻度に基づいてインデックスを可変長符号化することにより、インデックスの符号量を削減し、符号化効率を高める技術もある。
【０００４】
しかしながら、符号化対象の画素よりも前に符号化された画素からパレットを作成することで符号化効率を高める技術では、符号化対象の画素の直前までに符号化された複数の画素をパレットとして用いるが、このパレットを用いて画素を符号化する過程において、符号化対象の画素と同一または類似の画素がパレットに含まれない状況が多く発生する。このような場合、符号化対象の画素の色を新規に符号化する必要があることから、発生する符号量が増加して符号化の効率が低下する要因となる問題点がある。また、ある画素を符号化した後、次の画素を符号化する前にパレットの更新処理を行う必要があることから、複数画素の符号化処理を同時に処理できず、動作速度の高速化が難しいという問題点もある。なお、動作速度については、従来方法により複数画素の更新単位毎にパレットを更新することで、動作速度の問題は解決可能であるが、この場合、その更新単位内の画素は相互に参照することができなくなるため、符号化効率が低下するという問題点がある。
【０００５】
一方、入力画像（またはその一部）から予め色の出現頻度を取得し、その頻度に基づいてインデックスを可変長符号化する技術では、符号化装置と復号装置とで出現頻度の情報を共有する必要があることから、これを事前に共有する場合を除き、所定の処理単位毎に、符号化装置から復号装置へと出現頻度の情報を送る必要があり、これにより符号化効率が低下するという問題点がある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許出願公開第２０１４／０２４１６３０号明細書
【特許文献２】特許第３７４０３７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、上記に鑑みてなされたものであって、符号化効率を向上させ、符号化処理を高速化する符号化装置、復号装置および画像処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
実施形態の符号化装置は、決定部と、第１パレット生成部と、第１割り当て部と、符号化部と、第１参照生成部と、を備える。決定部は、入力画像の所定の処理単位に含まれる色のうち、第１参照パレットに含まれない色を保持する追加パレットを決定する。第１パレット生成部は、追加パレットに含まれる色と、第１参照パレットに含まれる色とを含む符号化用パレットを生成する。第１割り当て部は、処理単位の各画素に、画素の色に対応する符号化用パレットの色を示すインデックスを割り当てる。符号化部は、インデックスと、追加パレットの情報とを符号化する。第１参照生成部は、符号化用パレットから第１参照パレットを生成する。第１割り当て部は、処理単位の各画素の色に対応する色として符号化用パレットの色が参照された参照回数を算出する。第１参照生成部は、符号化用パレットに基づいて、符号化用パレットの色数と同じ色数の第１参照パレットを生成する。第１パレット生成部は、第１参照パレットの色のうち参照回数の少ない色から、追加パレットの色数の色を除いた残りの色と、追加パレットの色とを含む符号化用パレットを生成する。
【図面の簡単な説明】
【０００９】
【図１】図１は、画像処理装置の全体構成の一例を示す図である。
【図２】図２は、画像処理装置のハードウェア構成の一例を示す図である。
【図３】図３は、符号化装置の機能ブロックの一例を示す図である。
【図４】図４は、符号化装置の決定部の動作を説明する図である。
【図５】図５は、符号化装置のパレット生成部の動作を説明する図である。
【図６】図６は、符号化装置の割り当て部の動作を説明する図である。
【図７】図７は、符号化装置の符号化部の動作を説明する図である。
【図８】図８は、インデックスと追加パレットとを交互に符号化するための処理コードの一例を示す図である。
【図９】図９は、復号装置の機能ブロック構成の一例を示す図である。
【図１０】図１０は、復号装置の割り当て部の動作を説明する図である。
【図１１】図１１は、符号化装置の符号化処理の一例を示すフローチャートである。
【図１２】図１２は、復号装置の復号処理の一例を示すフローチャートである。
【図１３】図１３は、第２の実施形態の符号化装置のパレット生成部の動作を説明する図である。
【図１４】図１４は、第３の実施形態の符号化装置の機能ブロックの一例を示す図である。
【図１５】図１５は、第３の実施形態の復号装置の機能ブロックの一例を示す図である。
【発明を実施するための形態】
【００１０】
以下に、図面を参照しながら、本発明の実施形態に係る符号化装置、復号装置および画像処理装置を詳細に説明する。ただし、図面は模式的なものであるため、具体的な構成は以下の説明を参酌して判断すべきものである。
【００１１】
（第１の実施形態）
図１は、いくつかの実施形態の画像処理装置の全体構成の一例を示す図である。図１を参照しながら、画像処理装置１の全体構成について説明する。
【００１２】
図１に示すように、第１の実施形態に係る画像処理装置１は、符号化装置１０と、復号装置２０と、記憶装置３０と、を含む。
【００１３】
符号化装置１０は、入力画像を所定の処理単位（以下、単に「処理単位」という）（例えば、１以上の画素を含む１次元または２次元の画素のブロック）毎に符号化処理を行う装置である。符号化装置１０は、処理単位内の各画素を、１以上の画素を含む符号化用パレットと、符号化用パレット内のどの色を参照するかを示すインデックスとで表現し、符号化用パレットのうち後述する参照パレットとは異なる画素で構成された追加パレットの情報と、インデックスとを符号化する符号化処理を行う。
【００１４】
復号装置２０は、符号化装置１０で符号化されたビットストリームから、追加パレットの情報と、インデックスとに復号し、復号用パレット（符号化用パレットと同一）を生成し、処理単位内の各画素、インデックスが示す復号用パレットの色を割り当てて復号画像を生成する復号処理を行う装置である。
【００１５】
記憶装置３０は、符号化装置１０による符号化処理により生成されたビットストリームを一時記憶する装置である。記憶装置３０は、復号装置２０によって復号処理が実行されるビットストリームが読み出される。記憶装置３０は、後述する図２に示すＲＡＭ５０４によって実現される。
【００１６】
図２は、いくつかの画像処理装置のハードウェア構成の一例を示す図である。図２を参照しながら、画像処理装置１のハードウェア構成について説明する。
【００１７】
図２に示すように、画像処理装置１は、符号化プロセッサ５０１と、キャッシュ５０１ａと、復号プロセッサ５０２と、キャッシュ５０２ａと、補助記憶装置５０３と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５０４と、出力Ｉ／Ｆ５０５と、を有する。
【００１８】
符号化プロセッサ５０１は、図１に示す符号化装置１０の全体の動作を制御する演算装置である。符号化プロセッサ５０１は、符号化装置１０の符号化処理を実行する。
【００１９】
キャッシュ５０１ａは、符号化プロセッサ５０１が処理をする際のデータをワークエリアとして一時的に記憶するメモリである。
【００２０】
復号プロセッサ５０２は、図１に示す復号装置２０の全体の動作を制御する演算装置である。復号プロセッサ５０２は、復号装置２０の復号処理を実行する。
【００２１】
キャッシュ５０２ａは、復号プロセッサ５０２が処理をする際のデータをワークエリアとして一時的に記憶するメモリである。
【００２２】
補助記憶装置５０３は、符号化装置１０が入力する入力画像を記憶する記憶装置である。補助記憶装置５０３は、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、フラッシュメモリまたは光ディスク等の電気的、磁気的または光学的に記憶可能な記憶装置である。なお、補助記憶装置５０３は、画像取得装置（カメラ等）、ネットワーク、または他の処理装置等に置き換えられてもよい。
【００２３】
ＲＡＭ５０４は、符号化装置１０が符号化処理により生成したビットストームを一時記憶する揮発性記憶装置である。ＲＡＭ５０４は、復号装置２０によって復号処理が実行されるビットストリームが読み出される。ＲＡＭ５０４は、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ  ＲＡＭ）またはＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）である。
【００２４】
出力Ｉ／Ｆ５０５は、図２に示すように、例えば、画像を表示する表示装置２を接続するための出力インターフェースである。
【００２５】
Ｉ／Ｆ５０６は、図２に示すように、例えば、補助記憶装置５０３を接続するためのインターフェースである。
【００２６】
上述の符号化プロセッサ５０１、復号プロセッサ５０２、補助記憶装置５０３、ＲＡＭ５０４、出力Ｉ／Ｆ５０５、およびＩ／Ｆ５０６は、アドレスバスおよびデータバス等のバス５０７によって互いに通信可能に接続されている。
【００２７】
表示装置２は、例えば、復号装置２０により復号された復号画像を表示する液晶ディスプレイ、プラズマディスプレイ、または有機ＥＬ（Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ）ディスプレイ等の表示装置である。なお、表示装置２は、補助記憶装置（例えば、ＨＤＤ、ＳＳＤ、フラッシュメモリまたは光ディスク等の電気的、磁気的または光学的に記憶可能な記憶装置）、ネットワーク、または他の信号処理装置に置き換えられてもよい。
【００２８】
なお、図２に示すハードウェア構成の例では、符号化プロセッサ５０１と復号プロセッサ５０２とが別々のプロセッサとしているが、これに限定されるものではなく、符号化プロセッサ５０１と、復号プロセッサ５０２とがワンチップで形成されたプロセッサであってもよい。
【００２９】
図３は、第１の実施形態の符号化装置の機能ブロック構成の一例を示す図である。図４は、第１の実施形態の符号化装置の決定部の動作を説明する図である。図５は、第１の実施形態の符号化装置のパレット生成部の動作を説明する図である。図６は、第１の実施形態の符号化装置の割り当て部の動作を説明する図である。図７は、第１の実施形態の符号化装置の符号化部の動作を説明する図である。図８は、第１の実施形態の符号化部のインデックスと追加パレットとを交互に符号化するための処理コードの一例を示す図である。図３〜８を参照しながら、画像処理装置１の符号化装置１０の機能ブロックの構成および動作について説明する。
【００３０】
図３に示すように、第１の実施形態に係る符号化装置１０は、決定部１０１と、パレット生成部１０２（第１パレット生成部）と、割り当て部１０３（第１割り当て部）と、符号化部１０４と、参照生成部１０５（第１参照生成部）と、を有する。
【００３１】
決定部１０１は、外部から入力画像（例えば、図２に示す補助記憶装置５０３に記憶された画像、または、出力Ｉ／Ｆ５０５を介して受信した画像等）を受け取り、参照生成部１０５から参照パレット（第１参照パレット）を受け取り、入力画像の処理単位毎に、追加パレットを決定する機能部である。符号化装置１０が、入力画像を良好な画質を維持したまま符号化するためには、後述するパレット生成部１０２により生成される符号化用パレットが、処理単位内に含まれる各画素の色を表現するのに十分な色を保持している必要がある。このためには、決定部１０１が生成する追加パレットは、入力画像の処理単位内に含まれる画素の色のうち、参照生成部１０５からの参照パレット内に不足する色、すなわち、参照パレット内に同一または類似の画素が含まれない色を保持するようにすればよい。具体的には、決定部１０１は、例えば、図４に示す方法によって追加パレットを決定する。まず、決定部１０１は、図４に示す入力画像の処理単位６００内に含まれる画素の色を、同一または類似の色のグループに分類する。ここで、２つの色が同一または類似であるとは、例えば、下記の式（１）に示す条件を満たす場合とする。
【００３２】
｜ｒ１−ｒ２｜＋｜ｇ１−ｇ２｜＋｜ｂ１−ｂ２｜＜Ｔｈ              ・・・（１）
【００３３】
ここで、ｒ、ｇ、ｂは画素の各色（それぞれ赤、緑、青）の画素値であり、例えば、（ｒ１，ｇ１，ｂ１）は、２つの色の一方の画素値とし、（ｒ２，ｇ２，ｂ２）は、２つの色の他方の画素値とする。また、Ｔｈは、所定の閾値である。図４に示す例では、決定部１０１は、処理単位６００を３つのグループに分類している。
【００３４】
なお、上述の式（１）では、ｒ、ｇ、ｂの３つの画素値で色が表現される場合を示したが、画素のコンポーネントの数は任意（例えば、１、２または４等）であってもよく、また、ｒ、ｇ、ｂ以外の表色系（例えば、ＹＵＶ色空間またはＬａｂ色空間等）を用いてもよい。さらに、決定部１０１は、上述の式（１）のように、各画素値の差分絶対値の和を閾値判定する以外にも、各画素値の差分絶対値の最大値または最小値について閾値判定を行ってもよい。
【００３５】
次に、決定部１０１は、処理単位６００内の各グループについて代表となる色（代表色）を決定する。代表色は、例えば、各グループに含まれる画素の色の平均値とすればよい。なお、代表色は、例えば、各グループの最頻値であってもよい。また、代表色は、処理の簡単化のため、各グループ内の所定の画素（例えば、ラスタスキャン順で最初にスキャンされる画素）の色をそのまま用いるものとしてもよい。
【００３６】
次に、決定部１０１は、各グループの代表色について、参照生成部１０５からの参照パレット６１０に同一または類似の色が存在するか否かを、上述の式（１）または下記の式（２）により判定する。決定部１０１は、式（１）または（２）による判定の結果、参照パレット６１０に代表色と同一または類似の色が存在しない場合、その代表色を不足色として抽出し、その不足色を、追加パレット６２０を構成する色として追加し、追加パレット６２０を決定する。
【００３７】
（｜ｒ１−ｒ２｜＋｜ｇ１−ｇ２｜＋｜ｂ１−ｂ２｜）×Ｎ＜Ｔｈ      ・・・（２）
【００３８】
ここで、Ｎは、分類されたグループに含まれる画素の数である。また、決定部１０１が各グループの代表色と、参照パレット６１０に含まれる色と比較する場合に上述の式（１）または（２）を用いる場合、例えば、（ｒ１，ｇ１，ｂ１）は、代表色の画素値として、（ｒ２，ｇ２，ｂ２）は、参照パレット６１０に含まれる色の画素値とすればよい。また、上述の式（１）および（２）の閾値Ｔｈは、決定部１０１が処理単位６００内に含まれる画素の色を、同一または類似の色のグループに分類する場合に用いた式（１）での閾値Ｔｈと同一の値でもよく、または異なる値でもよい。
【００３９】
また、図４の例で示す追加パレット６２０を構成する色は１つとなっているが、言うまでもなく複数の色で構成される場合もある。この場合、決定部１０１は、追加パレット６２０を構成する色を代表色とするグループの画素の個数（参照回数）を算出し、この参照回数が多い順に追加パレット６２０をソートする。
【００４０】
そして、決定部１０１は、決定した追加パレット６２０を、パレット生成部１０２および符号化部１０４に送る。決定部１０１は、図２に示す符号化プロセッサ５０１により実現される。
【００４１】
なお、上述の追加パレット６２０を決定する方法では、処理単位の各画素について、所定のスキャン順（例えば、ラスタスキャン順等）に、画素の色と同一または類似の色が参照パレット６１０に含まれるか否かを判定し、含まれない場合にその色を順次追加パレット６２０に加えるようにしている。この場合、追加パレット６２０に同一または類似の色が複数入ってしまい、符号化効率が低下する場合が考えられるため、決定部１０１は、処理単位の各画素の色を追加パレット６２０に加える前に、直前の画素までに生成された追加パレット６２０内に同一または類似の色が無いか否かを判定し、無い場合のみ追加パレット６２０に加えるようにしてもよい。
【００４２】
また、決定部１０１は、複数の追加パレットパターンを設定し、これら追加パレットパターンのそれぞれについて、割り当て部１０３および符号化部１０４で割り当て動作および符号化動作が行われた際の符号化誤差（入力画像の各画素の色と、割り当て部１０３が割り当てた色との誤差（例えば、差分絶対値和または差分二乗和等））および発生符号量を算出または推定し、これらの値から下記の式（３）に示すコストＣｏｓｔを最小化するようにレート歪み最適化を行うことで、追加パレットを決定してもよい。複数の追加パレットパターンは、例えば、入力画像の各画素を同一または類似の色でグループに分類する際の閾値を変更することで用意してもよく、または、入力画像の任意の画素を抽出した各色としてもよい。
【００４３】
Ｃｏｓｔ＝Ｄｉｓｔｏｒｔｉｏｎ＋ｌａｍｂｄａ×Ｒａｔｅ            ・・・（３）
【００４４】
ここで、式（３）において、Ｃｏｓｔはコスト、Ｄｉｓｔｏｒｔｉｏｎは誤差（またはその推定値）、Ｒａｔｅは符号量（またはその推定値）、ｌａｍｂｄａは予め定められた係数を示す。
【００４５】
また、追加パレット６２０に含まれる色の数は、０以上所定色数（例えば、処理単位内の画素の数）以下であり、処理単位毎に異なってもよい。なお、上述の所定色数は処理単位内の画素の数よりも少ないものとして設定してもよい。この場合、決定部１０１は、例えば、誤差（例えば、上述の式（１）または（２）の左辺の値）が大きくなる色を優先して追加パレット６２０に挿入してもよい。このようにする場合、処理単位内の色数が多い場合に追加パレット６２０がすべての色を保持できない場合が発生するが、一方で、後述する符号化用パレット６３０のサイズが縮小されることから、インデックスの符号量を削減することができる。
【００４６】
パレット生成部１０２は、決定部１０１および参照生成部１０５から、それぞれ追加パレットおよび参照パレットを受け取り、追加パレットおよび参照パレットにそれぞれ含まれる色を統合して、符号化用パレットを生成する機能部である。具体的には、パレット生成部１０２は、図５に示すように、参照パレット６１０に含まれる色、および追加パレット６２０に含まれる色のすべての色を含むパレットとして、符号化用パレット６３０を生成する。ここで、追加パレット６２０に含まれる色の数は、０以上所定色数以下で処理単位毎に可変であることから、符号化用パレット６３０のサイズも、同様に処理単位毎に可変であってよい。
【００４７】
また、パレット生成部１０２は、追加パレット６２０を先頭に配置し、参照パレット６１０をその後に配置して、符号化用パレット６３０を生成する。ここで、符号化用パレット６３０の色のうち、追加パレット６２０に由来する部分は、上述のように決定部１０１により参照回数の多い順にソートされており、参照パレット６１０に由来する部分は、後述するように参照生成部１０５により、以前の処理単位における参照回数の多い順にソートされている。
【００４８】
そして、パレット生成部１０２は、例えば、図５に示すように、符号化用パレット６３０の先頭から小さい順に番号を付与する。図５の例では、符号化用パレット６３０は、色の数が５つであり、先頭から順に「０」〜「４」の番号が付与されている。すなわち、符号化用パレット６３０は、含む色の情報（画素値）だけでなく、各色に付与された番号の情報を含むことになる。このようにパレット生成部１０２により符号化用パレット６３０に付与された番号は、後述するように割り当て部１０３が処理単位に割り当てるインデックスに対応する。以上のように番号を付与した場合、後述するように、符号化部１０４が、番号が小さい順に短い符号を割り当てることで、後述するインデックスの可変長符号化を実現できるようになる。なお、図５に示す例では、符号化用パレット６３０に対する番号の付与順は例示であり、これと異なる順番で番号を付与するものとしてもよい。
【００４９】
そして、パレット生成部１０２は、生成した符号化用パレット６３０を、割り当て部１０３および参照生成部１０５に送る。パレット生成部１０２は、図２に示す符号化プロセッサ５０１により実現される。
【００５０】
割り当て部１０３は、外部から入力画像を受け取り、パレット生成部１０２から符号化用パレットを受け取り、入力画像の処理単位毎に、処理単位の各画素に、符号化用パレット内で対応する色を示す番号（パレット生成部１０２により付与された番号）をインデックスとしてそれぞれ割り当てる機能部である。具体的には、割り当て部１０３は、図６に示すように、処理単位６００内の各画素の色と、符号化用パレット６３０内の各色との比較を行い、符号化用パレット６３０から最も近い色を選択し、処理単位６００の各画素に対して、選択した色に対応する番号をインデックスとして割り当てる。ここで、図６に示すように、割り当て部１０３により、処理単位６００の各画素に、符号化用パレット６３０の番号をインデックスとして割り当てた情報をインデックス６４０としている。色の近さを示す指標値は、例えば、処理単位６００と符号化用パレット６３０との各色の画素値の差分絶対値和であればよい。この指標値が最も小さい色が、最も近い色である。なお、別の指標値として、例えば、各色の画素値の差分二乗値和を用いてもよく、または、各色の画素値の差分絶対値または差分二乗値の最大値を指標値として用いてもよい。
【００５１】
また、割り当て部１０３は、処理単位６００内で、符号化用パレット６３０内で最も近い色として参照された回数（処理単位６００におけるその色に最も近い画素数）を示す参照回数を算出する。図６の例では、符号化用パレット６３０に付与された番号「０」の色に最も近い処理単位６００内の色の画素数（参照回数）が３回であり、番号「１」の色に最も近い色の画素数が６回であり、番号「２」の色に最も近い色の画素数が７回であることを示している。
【００５２】
そして、割り当て部１０３は、処理単位６００の各画素にインデックスを割り当てたインデックス６４０を、符号化部１０４に送り、かつ、算出した参照回数を示す参照回数情報６５０を、参照生成部１０５に送る。ここで、参照回数情報６５０は、符号化用パレット６３０に付与された番号（インデックス）と、参照回数とが関連付けられた情報である。割り当て部１０３は、図２に示す符号化プロセッサ５０１により実現される。
【００５３】
符号化部１０４は、決定部１０１から追加パレットを受け取り、割り当て部１０３からインデックス（図６に示すインデックス６４０）を受け取り、追加パレット（色の数および色情報）およびインデックスを符号化して出力ストリームを生成する機能部である。そして、符号化部１０４は、生成した出力ストリームを外部（図１に示す記憶装置３０等）に出力する。符号化部１０４は、図２に示す符号化プロセッサ５０１により実現される。
【００５４】
まず、追加パレットは、０以上かつ所定色数以下の色を保持し、保持する色の数は処理単位毎に異なることから、符号化部１０４は、追加パレットに含まれる色の数と、追加パレットに含まれる各色を示す情報（色情報）とを符号化する。
【００５５】
符号化部１０４は、追加パレットに含まれる色の数を、例えば、予め定められた固定のビット長で符号化する。この固定のビット長は、０から上述の所定色数までの値を十分に符号化可能なビット長であればよく、例えば、所定色数が１５であった場合、４ビットであれば十分である。
【００５６】
なお、符号化部１０４は、追加パレットに含まれる色の数を可変長符号化してもよい。追加パレットは、符号化の対象の処理単位を符号化するために参照パレット内で不足する色のみを保持しており、このことから、参照パレットが十分な色を保持していれば、追加パレットに含まれる色数は０または小さい値になりやすい。そこで、追加パレットに含まれる色の数が０に近いほど短い符号を割り当て、色の数が多いほど長い符号を割り当てて符号化することにより、追加パレットに含まれる色の数を符号化するために必要な平均符号量を削減することができる。なお、それぞれの色数に対応する符号は予め定められたテーブルにより設定されているものとすればよい。または、符号化部１０４は、アルファ符号、ゴロム符号、または指数ゴロム符号等、一般に利用される可変長符号テーブルを用いて、追加パレットの色の数を符号化してもよい。
【００５７】
次に、符号化部１０４は、追加パレットに含まれる各色を示す情報（色情報）を符号化する。各色の色情報は、例えばＲ（赤）、Ｇ（緑）、Ｂ（青）の３つのコンポーネントのそれぞれの値を示すものであればよい。または、色情報は、ＹＵＶ色空間、Ｌａｂ色空間その他の表色系の各コンポーネントの値として表現されてもよい。符号化部１０４は、追加パレットの各色の色情報であるコンポーネントの値を、予め定められた固定のビット長で符号化、または予め定められたテーブルを用いて可変長で符号化する。なお、ある処理単位において追加パレットに色が含まれない場合（色の数が０である場合）、符号化部１０４は、その処理単位においては色情報を符号化しないものとすればよい。
【００５８】
なお、例えば、色情報がＹＵＶ色空間で表現される場合、Ｙコンポーネントは固定長、ＵおよびＶコンポーネントは可変長（例えば、０（色差無し）の符号を短く設定し、色差の絶対値が大きいほど長い符号とする等）で符号化されるものとしてもよい。
【００５９】
また、符号化部１０４は、符号化の対象の処理単位内で、追加パレット内で最も近い色として参照される回数に基づいて、追加パレット各色の色情報の符号化順を決定してもよい。この場合、符号化部１０４は、参照回数の降順（または昇順）で、追加パレットの各色の色情報を符号化すればよい。これによって、後述するように、復号装置２０が追加パレットに含まれる各色の参照回数の順番を判断することが可能になり、この情報を用いることにより後述するインデックスを符号化または復号する際に可変長符号化を実現することが可能になる。この場合、符号化部１０４は、割り当て部１０３から参照回数情報を受け取るものとすればよい。
【００６０】
次に、符号化部１０４は、処理単位内の各画素について割り当て部１０３により割り当てられたインデックスを符号化する。インデックスは、処理単位内の各画素について０以上かつ符号化用パレットの色数未満のいずれかの値を保持している。図７に示すように、符号化用パレット６３１は、パレット生成部１０２により参照パレット６１１と追加パレット６２１とが統合されて生成されたものであることから、符号化用パレット６３１には、参照パレットに由来する色（参照パレット部６３１ｂ）と、追加パレットに由来する色（追加パレット部６３１ａ）とが保持されている。また、参照パレット６１１は、後述する参照生成部１０５によって、直前の処理単位における参照回数でソートされており、追加パレット６２１は、上述のように決定部１０１によって参照回数でソートされている。
【００６１】
符号化部１０４は、インデックスの符号量を削減するために、図７に示すように、各インデックスについて可変長符号化を行う。具体的には、符号化部１０４は、まず、図７に示すように、符号化用パレット６３１内で追加パレットに由来する色（追加パレット部６３１ａ）に対応するインデックスについて、符号化の対象の処理単位内で参照回数の多いものから順に短い符号で符号化を行う。参照回数は、符号化部１０４が、インデックスに対して参照回数を数えることにより導出が可能であり、一方、復号装置２０では、上述の通り追加パレットの各色が符号化された順番から、参照回数の多い順を導出することが可能である。
【００６２】
次に、符号化部１０４は、図７に示すように、符号化用パレット６３１内で参照パレットに由来する色（参照パレット部６３１ｂ）に対応するインデックスについて、参照生成部１０５によりソートされた順の上位の色に対応するインデックスから順に短い符号で符号化を行う。
【００６３】
さらに、符号化部１０４は、追加パレットに由来する色（追加パレット部６３１ａ）に対応するインデックスについて、参照パレットに由来する色（参照パレット部６３１ｂ）に対応するインデックスよりも短い符号で符号化する。参照パレットに由来する色（参照パレット部６３１ｂ）は、前回の処理単位で利用された色である一方、追加パレットに由来する色（追加パレット部６３１ａ）は今回の処理単位内で必ず参照される色であるため、このような可変長符号化を行うことにより、インデックスの符号量を削減することが可能になる。
【００６４】
また、符号化部１０４は、可変長符号化で用いる符号を、予め定められたテーブルに基づいて割り当てる。例えば、図７に示す例では、符号化用パレット６３１のインデックス「０」〜「５」をそれぞれ、「０」、「１０」、「１１０」、「１１１０」、「１１１１０」、「１１１１１」に割り当てるテーブルとしている。
【００６５】
なお、符号化部１０４は、アルファ符号、ゴロム符号、または指数ゴロム符号等、一般に利用される可変長符号テーブルを用いて、インデックスを符号化してもよい。また、符号化部１０４は、処理単位毎にテーブルまたはそのパラメタ（ゴロム符号のサフィックス長等）を変更することとしてもよい。このパラメタは、処理単位毎に符号化してもよいし、例えば、追加パレット内の色数等に基づいて設定されるものとしてもよい。一般に、処理単位内の色数が多い場合、インデックスの値は分散しやすい傾向にあることから、例えば、符号化用パレット６３１内の色数が多い場合、符号長の傾斜が緩い（符号長が一定に近い）テーブルを利用することによって、インデックスを符号化する際の平均符号量を削減することが可能になる。
【００６６】
また、上述では、符号化用パレット６３１の追加パレットに由来する色に対応するインデックスには、参照パレットに由来する色よりも短い符号で符号化することとしたが、これに限定されるものではない。具体的には、符号化部１０４は、参照パレットに由来する色について、処理単位における参照回数が所定の閾値以上である場合に、この色が対応するインデックスについては、追加パレットに由来する色よりも短い符号で符号化することとしてもよい。例えば、以前の処理単位内が平たんであり、１色のみが参照されていた場合、次の処理単位内も平たんかつ同じ色である可能性が高くなる。このような場合に、対応するインデックスを短い符号で符号化することで、インデックスの符号量を削減することが可能になる。
【００６７】
また、符号化部１０４は、インデックスを処理単位内の各画素についてそれぞれ符号化する代わりに、所定のブロック毎にまとめて符号化するものとしてもよい。一般に、隣接する画素同士は類似の色である可能性が高いことから、同一のインデックスとなる可能性が高い。そこで、符号化部１０４は、処理単位を複数のブロックに分割し、分割したそれぞれのブロックについて、ブロック内のインデックスがすべて同一であるか否かを示すフラグ（以下、単一インデックスフラグという）を符号化し、このフラグが真である場合、インデックスを１つだけ符号化するようにしてよい。また、符号化部１０４は、単一インデックスフラグが偽である場合は、ブロック内の各画素についてインデックスを符号化するものとすればよい。ここで、ブロックは、処理単位を予め定められた方式（例えば、２等分、４等分、または、処理単位が２次元の画像領域である場合、画素ライン単位等）で処理単位を分割したものであってもよい。このように処理単位を複数のブロックに分割し、ブロック内のインデックスがすべて同一である場合、そのインデックスを１つだけ符号化することにより、入力画像の平たんな画像領域において少ない符号量でインデックスを符号化できる。
【００６８】
また、符号化部１０４は、処理単位を階層的にブロックに分割し、各階層のブロック内のインデックスがすべて同一か否かを示すフラグを符号化するようにしてもよい。具体的には、符号化部１０４は、まず、第１階層ブロック（処理単位と同一）においてフラグを符号化し、フラグが真である場合はインデックスを１つ符号化する。また、符号化部１０４は、フラグが偽である場合、第１階層ブロックを分割した第２階層ブロックのそれぞれについて、同様にフラグを符号化する。ここで、第２階層ブロックは、第１階層ブロックを所定の方法（例えば、２等分または４等分等）で分割したブロックである。符号化部１０４は、第２階層ブロックにおいても、フラグが真であればインデックスを１つ符号化し、偽であれば次の階層へと移行する。以上の処理を所定の階層数まで行い、最後の階層まで到達した場合、最後の階層ブロックの各画素についてインデックスを符号化する。以上のような階層的にブロックを分割する方式でも、入力画像の平たんな領域において少ない符号量でインデックスを符号化できる。
【００６９】
また、符号化部１０４は、処理単位内の各画素についてインデックスを符号化する際、インデックスが予測インデックスと一致するか否かを示す１ビットのフラグ（以下、スキップフラグという）を符号化するものとしてもよい。この場合、符号化部１０４は、スキップフラグが偽である場合のみ、インデックスをさらに符号化する。また、符号化部１０４は、この場合にインデックスを符号化する際、予測インデックスと同一のインデックスは符号化され得ない（この場合のスキップフラグは真である）ため、予測インデックスと同一のインデックスを除外して可変長符号化を行えばよい。ここで、符号化部１０４は、予測インデックスを、注目する画素の左、上および左上の画素のインデックスの値から、例えば、下記の式（４）により算出する。
【数１】
0006545570.tif 000002
【００７０】
以上のように予測インデックスと一致するか否かを示すスキップフラグを用いる方式でも入力画像の平たんな領域において少ない符号量でインデックスを符号化できる。
【００７１】
また、符号化部１０４は、処理単位を分割したブロック毎に単一インデックスフラグを符号化する方式と、処理単位の画素毎に対応するスキップフラグを符号化する方式とを組み合わせて用いてもよい。
【００７２】
また、上述では、符号化部１０４は、最初に追加パレットの情報（色の数および色情報）を符号化し、次に、インデックスを符号化するものとしているが、インデックスを符号化した後に、追加パレットの情報を符号化するようにしてもよい。
【００７３】
また、上述では、符号化部１０４は、最初に追加パレットの情報（色の数および色情報）を符号化し、次に、インデックスを符号化するものとしているが、図８に示す処理コードのように、インデックスと追加パレットの情報とを交互に符号化するようにしてもよい。復号装置２０を順序回路により動作させることを考えた場合、復号画像の各画素はインデックスおよびパレット（復号用パレット）が用意されて初めて復号可能となることから、インデックスと追加パレットとを交互に符号化していけば復号時のバッファの削減、および処理遅延を低減することが可能となる。
【００７４】
これを実現するために、符号化部１０４は、例えば、図８に示した処理コードの順番でインデックスと追加パレットとを符号化する。図８の例では、追加パレットに対応するインデックスを０〜（追加パレット色数−１)、参照パレットに対応するインデックスを（追加パレット色数）〜（符号化用パレット色数）に割り当てた場合が示されている。まず、初期化処理として、符号化部１０４は、変数ｉｓＣｏｄｅｄの初期化を行う。変数ｉｓＣｏｄｅｄは、「ｔｒｕｅ」または「ｆａｌｓｅ」を示す変数の配列であり、符号化用パレットの色数と同じ配列の長さを有する。変数ｉｓＣｏｄｅｄは、追加パレットに対応するインデックスの部分（０〜（追加パレット色数−１））について「ｆａｌｓｅ」に設定され、参照パレットに対応するインデックスの部分については「ｔｒｕｅ」に初期化される。
【００７５】
続いて、符号化処理では、符号化部１０４は、まず、追加パレットの色の数（追加パレット色数）が符号化され、その後各画素について、インデックスと、そのインデックスに対応する追加パレットの色情報が符号化されていない場合（変数ｉｓＣｏｄｅｄが「ｆａｌｓｅ」である場合）は対応する追加パレットの色情報を符号化する。そして、符号化部１０４は、追加パレットの色情報を符号化した場合、対応する変数ｉｓＣｏｄｅｄ変数を「ｔｒｕｅ」に設定し、その色情報が符号化されたことを示す。
【００７６】
参照生成部１０５は、パレット生成部１０２および割り当て部１０３から、それぞれ符号化用パレットおよび参照回数情報を受け取り、これらの情報に基づいて参照パレットを生成する機能部である。ここで、参照パレットは、所定色数の色を保持するパレットである。具体的には、参照生成部１０５は、処理単位毎に、符号化用パレットの各色を参照回数情報に基づいて、例えば、参照回数の降順にソートし、ソート結果の上位の色から所定の色数を抽出したものを参照パレットとして生成する。
【００７７】
なお、参照パレットには、参照回数が０であった色も含めて、所定色数が保持されていてもよい。処理単位における参照回数が０であった場合でも、前の処理単位において出現した色であることから、次以降の処理単位において再び参照される可能性があるためである。また、参照生成部１０５が行うソートは、安定ソートであってもよい。すなわち、参照回数が同じであった場合、ソート前に上位であった色がそのまま上位に保持されるようにしてもよい。このようにソート処理が行われることによって、処理単位における参照回数が同じであった場合でも、前の処理単位における参照回数でソートした結果が反映されるため、符号化部１０４がインデックスを可変長符号化する際の効率が向上する。
【００７８】
そして、参照生成部１０５は、生成した参照パレットを、決定部１０１およびパレット生成部１０２に送る。参照生成部１０５は、図２に示す符号化プロセッサ５０１により実現される。
【００７９】
なお、図３に示した決定部１０１、パレット生成部１０２、割り当て部１０３、符号化部１０４、および参照生成部１０５は、機能を概念的に示したものであって、このような構成に限定されるものではない。例えば、図３で独立した機能部として図示した複数の機能部を、１つの機能部として構成してもよい。一方、図３の１つの機能部が有する機能を複数に分割し、複数の機能部として構成するものとしてもよい。
【００８０】
また、図３に示した決定部１０１、パレット生成部１０２、割り当て部１０３、符号化部１０４、および参照生成部１０５は、いずれも図２に示す符号化プロセッサ５０１により実現されるものとしたが、これに限定されるものではない。すなわち、上述の各機能部のうち少なくともいずれかが、記憶装置（例えば、図２に示す補助記憶装置５０３）等の記憶媒体に記憶されているプログラムがＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）により実行されることによって実現されるものとしてもよい。
【００８１】
図９は、第１の実施形態の復号装置の機能ブロック構成の一例を示す図である。図１０は、第１の実施形態の復号装置の割り当て部の動作を説明する図である。図９および１０を参照しながら、画像処理装置１の復号装置２０の機能ブロックの構成および動作について説明する。
【００８２】
図９に示すように、第１の実施形態に係る復号装置２０は、復号部２０１と、パレット生成部２０２（第２パレット生成部）と、割り当て部２０３（第２割り当て部）と、参照回数算出部２０４と、参照生成部２０５（第２参照生成部）と、を有する。
【００８３】
復号部２０１は、外部からビットストリーム（入力ストリーム）（例えば、図２に示すＲＡＭ５０４に記憶されたビットストリーム）を受け取り、この入力ストリームから追加パレットとインデックスとに復号する機能部である。この入力ストリームは、符号化装置１０が出力する出力ストリームと同一である。具体的には、復号部２０１は、符号化装置１０の符号化部１０４が追加パレットとインデックスとを符号化する方法に対応した復号方法によって、入力ストリームからこれらの情報に復号する。例えば、符号化部１０４が追加パレットの色数、追加パレット内の各色の色情報、インデックス、の順で符号化を行った場合、復号部２０１は、初めに追加パレットの色数を復号し、次に、追加パレットの各色の色情報を復号し、そして、インデックスを復号する。なお、符号化部１０４が追加パレットおよびインデックスを上記と異なる順番で符号化した場合は、復号部２０１はそれに対応した順番で復号を行えばよい。
【００８４】
なお、上述のように、符号化部１０４によって、インデックスは可変長符号化が行われる。復号部２０１は、符号化部１０４がインデックスの可変長符号化を行う際に用いたテーブルと同一のテーブルにより復号処理を行ってもよい。このテーブルは、符号化装置１０と復号装置２０とで予め共有されていてよい。また、符号化部１０４が処理単位毎にテーブルを変更する場合、復号部２０１も同様にテーブルを変更して復号を行ってもよい。この場合、テーブルの変更に必要な情報は、符号化部１０４がテーブルを変更する際に用いる情報と同一のものを用いればよく、例えば、符号化部１０４が追加パレットの色数に応じてテーブルを変更する場合、復号部２０１も同様に追加パレットの色数に応じてテーブルの切り替えを行うものとすればよい。また、符号化部１０４がテーブルを変更するための情報を符号化する場合は、復号部２０１はこの情報をさらに復号し、テーブルの切り替えを行ってもよい。
【００８５】
復号部２０１は、復号した追加パレットをパレット生成部２０２に送り、復号したインデックスを割り当て部２０３および参照回数算出部２０４にそれぞれ送る。復号部２０１は、図２に示す復号プロセッサ５０２により実現される。
【００８６】
パレット生成部２０２は、復号部２０１および参照生成部２０５から、それぞれ追加パレットおよび参照パレット（第２参照パレット）を受け取り、符号化装置１０のパレット生成部１０２が符号化用パレットを生成する方法と同一の方法により、復号用パレットを生成する機能部である。すなわち、パレット生成部２０２は、復号用パレットを生成する際、追加パレットを先頭に配置し、参照パレットをその後に配置して、復号用パレットを生成する。ここで、復号パレットの色のうち、追加パレットに由来する部分は、既に符号化装置１０側で参照回数の多い順にソートされており、参照パレットに由来する部分は、後述するように参照生成部２０５により、以前の処理単位における参照回数の多い順にソートされている。
【００８７】
そして、パレット生成部２０２は、上述のパレット生成部１０２と同様に、復号用パレットの先頭から小さい順に番号を付与する。すなわち、復号用パレットは、含む色の情報（画素値）だけでなく、各色に付与された番号の情報を含むことになる。このようにパレット生成部２０２により復号用パレットに付与された番号は、後述するように割り当て部２０３が復号用パレットの色を割り当てるインデックスに対応する。
【００８８】
そして、パレット生成部２０２は、生成した復号用パレットを、割り当て部２０３および参照生成部２０５に送る。パレット生成部２０２は、図２に示す復号プロセッサ５０２により実現される。
【００８９】
割り当て部２０３は、復号部２０１およびパレット生成部２０２から、それぞれインデックスおよび復号用パレットを受け取り、処理単位の各画素に、インデックスに対応する復号用パレットの色をそれぞれ割り当てることにより復号画像を生成する機能部である。具体的には、割り当て部２０３は、図１０に示すように、処理単位の各画素に、インデックス７１０の各値に対応する復号用パレット７００の色をそれぞれ割り当てることにより復号画像７２０を生成する。そして、割り当て部２０３は、生成した復号画像を、外部（例えば、図２に示す表示装置２等）に出力する。割り当て部２０３は、図２に示す復号プロセッサ５０２により実現される。
【００９０】
参照回数算出部２０４は、復号部２０１からインデックスを受け取り、処理単位内で、復号用パレットの各色が参照された回数を示す参照回数を算出する機能部である。この算出処理は、インデックスの各値が処理単位内で何回出現したのかを数え上げることで算出が可能である。例えば、図１０に示す例の場合、インデックス７１０の値「０」は、処理単位内で３回出現していることから、値「０」に対応する復号用パレット７００の色の参照回数は「３」と算出される。参照回数算出部２０４は、復号用パレット７００内のすべての色について同様に算出回数を算出する。そして、参照回数算出部２０４は、算出した参照回数を示す参照回数情報を、参照生成部２０５に送る。ここで、参照回数情報は、復号用パレットに付与された番号（インデックス）と、参照回数とが関連付けられた情報である。参照回数算出部２０４は、図２に示す復号プロセッサ５０２により実現される。
【００９１】
参照生成部２０５は、パレット生成部２０２および参照回数算出部２０４から、それぞれ復号用パレットおよび参照回数情報を受け取り、符号化装置１０の参照生成部１０５が符号化用パレットと参照回数とから参照パレットを生成する方法と同一の方法により、これらの情報に基づいて参照パレットを生成する機能部である。そして、参照生成部２０５は、生成した参照パレットを、パレット生成部２０２に送る。参照生成部２０５は、図２に示す復号プロセッサ５０２により実現される。
【００９２】
なお、図９に示した復号部２０１、パレット生成部２０２、割り当て部２０３、参照回数算出部２０４、および参照生成部２０５は、機能を概念的に示したものであって、このような構成に限定されるものではない。例えば、図９で独立した機能部として図示した複数の機能部を、１つの機能部として構成してもよい。一方、図９の１つの機能部が有する機能を複数に分割し、複数の機能部として構成するものとしてもよい。
【００９３】
また、図９に示した復号部２０１、パレット生成部２０２、割り当て部２０３、参照回数算出部２０４、および参照生成部２０５は、いずれも図２に示す復号プロセッサ５０２により実現されるものとしたが、これに限定されるものではない。すなわち、上述の各機能部のうち少なくともいずれかが、記憶装置（例えば、図２に示す補助記憶装置５０３）等の記憶媒体に記憶されているプログラムがＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）により実行されることによって実現されるものとしてもよい。
【００９４】
図１１は、第１の実施形態の符号化装置の符号化処理の一例を示すフローチャートである。図１１を参照しながら、画像処理装置１の符号化装置１０による符号化処理の流れを説明する。
【００９５】
＜ステップＳ１１＞
符号化装置１０の決定部１０１は、外部から入力画像を受け取り、参照生成部１０５から参照パレットを受け取り、入力画像の処理単位毎に、追加パレットを決定する。そして、決定部１０１は、決定した追加パレットを、パレット生成部１０２および符号化部１０４に送る。そして、ステップＳ１２へ移行する。
【００９６】
＜ステップＳ１２＞
符号化装置１０のパレット生成部１０２は、決定部１０１および参照生成部１０５から、それぞれ追加パレットおよび参照パレットを受け取り、追加パレットおよび参照パレットにそれぞれ含まれる色を統合して、符号化用パレットを生成する。そして、パレット生成部１０２は、生成した符号化用パレットを、割り当て部１０３および参照生成部１０５に送る。そして、ステップＳ１３へ移行する。
【００９７】
＜ステップＳ１３＞
符号化装置１０の割り当て部１０３は、外部から入力画像を受け取り、パレット生成部１０２から符号化用パレットを受け取り、入力画像の処理単位毎に、処理単位の各画素に、符号化用パレット内で対応する色を示す番号をインデックスとしてそれぞれ割り当てる。また、割り当て部１０３は、処理単位内で、符号化用パレット内で最も近い色として参照された回数（処理単位におけるその色に最も近い画素数）を示す参照回数を算出する。そして、割り当て部１０３は、処理単位の各画素に割り当てたインデックスを、符号化部１０４に送り、かつ、算出した参照回数を示す参照回数情報を、参照生成部１０５に送る。そして、ステップＳ１４へ移行する。
【００９８】
＜ステップＳ１４＞
符号化装置１０の符号化部１０４は、決定部１０１から追加パレットを受け取り、割り当て部１０３からインデックスを受け取り、追加パレット（色の数および色情報）およびインデックスを符号化して出力ストリームを生成する。そして、符号化部１０４は、生成した出力ストリームを外部に出力する。そして、ステップＳ１５へ移行する。
【００９９】
＜ステップＳ１５＞
符号化装置１０の参照生成部１０５は、パレット生成部１０２および割り当て部１０３から、それぞれ符号化用パレットおよび参照回数情報を受け取り、これらの情報に基づいて参照パレットを生成する。参照生成部１０５は、処理単位毎に、符号化用パレットの各色を参照回数情報に基づいて、例えば、参照回数の降順にソートし、ソート結果の上位の色から所定の色数を抽出したものを参照パレットとして生成する。そして、参照生成部１０５は、生成した参照パレットを、決定部１０１およびパレット生成部１０２に送る。参照生成部１０５により生成された参照パレットは、次の処理単位において、決定部１０１による追加パレットの生成、およびパレット生成部１０２による符号化用パレットの生成に用いられる。
【０１００】
以上のステップＳ１１〜Ｓ１５の処理は、入力画像の処理単位毎に、入力画像の符号化が完了または中断されるまで繰り返される。なお、ステップＳ１４およびＳ１５の動作順については、逆であってもよく、または並列に処理されてもよい。
【０１０１】
図１２は、第１の実施形態の復号装置の復号処理の一例を示すフローチャートである。図１２を参照しながら、画像処理装置１の復号装置２０による復号処理の流れを説明する。
【０１０２】
＜ステップＳ２１＞
復号装置２０の復号部２０１は、外部からビットストリーム（入力ストリーム）を受け取り、この入力ストリームから追加パレットとインデックスとに復号する。そして、復号部２０１は、復号した追加パレットをパレット生成部２０２に送り、復号したインデックスを割り当て部２０３および参照回数算出部２０４にそれぞれ送る。そして、ステップＳ２２へ移行する。
【０１０３】
＜ステップＳ２２＞
復号装置２０のパレット生成部２０２は、復号部２０１および参照生成部２０５から、それぞれ追加パレットおよび参照パレットを受け取り、符号化装置１０のパレット生成部１０２が符号化用パレットを生成する方法と同一の方法により、復号用パレットを生成する。そして、パレット生成部２０２は、生成した復号用パレットを、割り当て部２０３および参照生成部２０５に送る。そして、ステップＳ２３へ移行する。
【０１０４】
＜ステップＳ２３＞
復号装置２０の割り当て部２０３は、復号部２０１およびパレット生成部２０２から、それぞれインデックスおよび復号用パレットを受け取り、処理単位の各画素に、インデックスに対応する復号用パレットの色をそれぞれ割り当てることにより復号画像を生成する。そして、割り当て部２０３は、生成した復号画像を、外部に出力する。そして、ステップＳ２４へ移行する。
【０１０５】
＜ステップＳ２４＞
復号装置２０の参照回数算出部２０４は、復号部２０１からインデックスを受け取り、処理単位内で、復号用パレットの各色が参照された回数を示す参照回数を算出する。そして、参照回数算出部２０４は、算出した参照回数を示す参照回数情報を、参照生成部２０５に送る。そして、ステップＳ２５へ移行する。
【０１０６】
＜ステップＳ２５＞
復号装置２０の参照生成部２０５は、パレット生成部２０２および参照回数算出部２０４から、それぞれ復号用パレットおよび参照回数情報を受け取り、符号化装置１０の参照生成部１０５が符号化用パレットと参照回数とから参照パレットを生成する方法と同一の方法により、これらの情報に基づいて参照パレットを生成する。そして、参照生成部２０５は、生成した参照パレットを、パレット生成部２０２に送る。参照生成部２０５により生成された参照パレットは、次の処理単位において、パレット生成部２０２による復号用パレットの生成に用いられる。
【０１０７】
以上のステップＳ２１〜Ｓ２５の処理は、処理単位毎に、ビットストリームの復号が完了または中断されるまで繰り返される。なお、ステップＳ２４の動作は、ステップＳ２２またはＳ２３と入れ替えてもよく、または並列に処理されてもよい。
【０１０８】
以上のように、本実施形態の画像処理装置１は、前の処理単位における符号化用パレット（復号用パレット）を参照回数でソートして参照パレットを生成し、追加パレットは処理単位を符号化するために、参照パレット内で不足する色のみを保持すればよい。したがって、参照パレット内に、次の処理単位内の色が含まれる確率が高くなり、さらに、符号化用パレット（復号用パレット）全体を符号化する必要がなく、追加パレットを符号化するための符号量を削減することができる。
【０１０９】
また、本実施形態の画像処理装置１は、符号化（復号）の対象の処理単位までに符号化装置１０（復号装置２０）が処理した情報に基づいて、可変長による符号化（復号）を行うものとしている。具体的には、本実施形態の画像処理装置１は、符号化用パレット（復号用パレット）から参照パレットを生成する際、処理単位内で符号化用パレット（復号用パレット）が参照された回数でソートすることにより参照パレットを生成するものとしている。一般に、前の処理単位で多く参照された色は、次の処理単位においても参照される可能性が高く、反対に前の処理単位で参照されなかった色は、次の処理単位においても参照されない可能性が高い。このため、ソート済みの参照パレットの各色に対応するインデックスについて、ソート順の上位（すなわち参照された回数が多い）色には相対的に短い符号を、下位色には相対的に長い符号を割り当てることにより、インデックスを符号化する際の平均的な符号量を削減することができる。また、処理単位毎にソートされた参照パレットを利用して可変長符号化を行うことにより、事前にインデックスの発生頻度を調べる処理に要する遅延、および可変長テーブルを共有するために必要な符号量を削減できる。
【０１１０】
また、本実施形態の画像処理装置１は、参照パレットに追加パレットを合成することで符号化用パレット（復号用パレット）を生成している。ここで、追加パレットは、符号化（復号）の対象の処理単位内の各色について、参照パレット内に同一または類似の色が存在しない色を保持する。つまり、追加パレットに含まれる色は、処理単位内で少なくとも１回以上参照される。一方で、参照パレット内の各色は、ソート順上位の色であっても、処理単位内で１回も参照されない可能性がある。そこで本実施形態の画像処理装置１は、追加パレットの各色に対応するインデックスに対し、参照パレットの各色に対応するインデックスよりも相対的に短い符号を割り当てるものとしている。これによって、インデックスを符号化する際の符号量をさらに削減することができる。さらに、追加パレット内の各色については、符号化（復号）の対象の処理単位内で実際に参照される回数に基づき、回数の高い色に対応するインデックスから順に短い符号を割り当てるようにすることによって、インデックスを符号化する際の符号量をさらに削減することができる。
【０１１１】
また、上述のように、本実施形態の画像処理装置１は、入力画像を符号化する場合の符号量を削減することができるので、符号化された入力画像（ビットストリーム）を一時記憶する記憶装置３０の容量を削減することができる。
【０１１２】
また、本実施形態の符号化装置１０は、各機能部は複数の画素を含む所定の処理単位毎に動作するため、参照パレットの更新と次の符号化とは、処理単位毎に交互に行えばよく、処理単位内で依存関係の無い処理については並列に動作が可能なので、動作速度の高速化が容易である。
【０１１３】
さらに、処理単位毎に追加パレットを設定することから、処理単位内の発生誤差を抑えることができる。例えば、上述の式（２）により追加パレットを決定することで、同一または類似色が多い画素は、相対的に符号化誤差が少なくなるように追加パレットが決定されるので、これにより処理単位内の平均符号化誤差が低減される。
【０１１４】
なお、本実施形態の画像処理装置１は、図１に示すように、符号化装置１０と復号装置２０とが記憶装置３０に接続された構成となっているが、このような構成に限定されるものではない。例えば、符号化装置１０を備える装置と、復号装置２０を備える装置とが、ネットワーク（伝送路）を介して接続される構成であってもよい。この場合、符号化装置１０を備える装置は、入力画像を上述の方法で符号化したビットストリームを、ネットワークを介して伝送し、復号装置２０を備える装置は、このビットストリームを復号して復号画像を得る。この場合、ネットワークを伝送する情報は、符号化（圧縮）された信号（ビットストリーム）であるので、符号化を行わない場合と比較して、ネットワークの通信容量を削減することができる。
【０１１５】
また、符号化装置１０は、発生する符号量を制御する目的で、符号量制御部（制御部）をさらに備えるものとしてもよい。符号量制御部は、符号化部１０４から、処理単位毎に、発生した符号量に関する情報を受け取り、受け取った符号量（または、符号量を所定期間で積算した値）が予め定められた値を上回ったか否かに基づいて、決定部１０１が決定する追加パレットの色数を制御する。符号量制御部による色数の制御は、例えば、決定部１０１が追加パレットを決定する際の判定に用いる上述の式（１）または（２）の閾値Ｔｈを変更することによって行うものとすればよい。閾値Ｔｈが大きいほど、追加パレットの色数は少なくなりやすいので、発生する符号量を削減することができる。なお、上述の制御の他に、符号量制御部は、追加パレットの色数の最大値を変更するものとしてもよい。または、複数画素（ブロック）でインデックスをまとめて符号化するようにしている場合（例えば、上述の単一インデックスフラグあるいはスキップフラグを用いる場合）、これらのフラグが指定されるブロック内でインデックスがすべて同一となるように制御するものとしてもよい。これらの制御によっても、インデックスの符号量を削減することができる。
【０１１６】
（第２の実施形態）
第２の実施形態に係る画像処理装置について、第１の実施形態に係る画像処理装置１と相違する点を中心に説明する。第１の実施形態では、固定の色数とした参照パレットに、色数が変動する追加パレットを統合することにより、色数が変動する符号化用パレットを生成して、インデックスを割り当てる動作について説明した。本実施形態では、所定色数の符号化用パレットを生成する動作について説明する。なお、本実施形態に係る画像処理装置の全体構成およびハードウェア構成、ならびに、符号化装置１０および復号装置２０の機能ブロックの構成は、第１の実施形態で説明した構成と同様である。
【０１１７】
パレット生成部１０２は、決定部１０１および参照生成部１０５から、それぞれ追加パレットおよび参照パレットを受け取り、追加パレットおよび参照パレットにそれぞれ含まれる色を統合して、符号化用パレットを生成する。ただし、本実施形態では、具体的には、パレット生成部１０２は、図１３に示すように、所定色数（図１３の例では４）の参照パレット６１５と、追加パレット６２５とから、所定色数（図１３の例では４）の符号化用パレット６３５を生成する。ここで、追加パレット６２５の色数は処理単位毎に異なるが、この色数をｋとし、上述の所定色数をＮとした場合、パレット生成部１０２は、追加パレット６２５のｋ個の色、および、参照パレット６１５に含まれるＮ個の色のうち（Ｎ−ｋ）個の色を含むパレットとして、Ｎ個の色を含む符号化用パレット６３５を生成する。ここで、参照パレット６１５は、参照生成部１０５により参照回数の降順にソートされたパレットであり、ソート結果の上位（すなわち、以前の処理単位における参照回数が高い）の色ほど、次の処理単位で同じ色を含む可能性が高い。そこで、パレット生成部１０２は、Ｎ個の色を含む参照パレット６１５のうち、ソート結果の上位の（Ｎ−ｋ）個の色を抽出して、符号化用パレット６３５に含めるようにする。そして、パレット生成部１０２は、追加パレット６２５を先頭に配置し、参照パレット６１５の色のうちの上述の（Ｎ−ｋ）個の色をその後に配置して、符号化用パレット６３５を生成する。その結果、パレット生成部１０２が生成する符号化用パレット６３５の色数は常に所定色数Ｎとなる。
【０１１８】
参照生成部１０５は、パレット生成部１０２および割り当て部１０３から、それぞれ符号化用パレットおよび参照回数情報を受け取り、これらの情報に基づいて参照パレットを生成する。第１の実施形態では、参照生成部１０５は、符号化用パレットを参照回数に基づいてソートした後、上位から所定色数を抽出して、参照パレットを生成した。本実施形態では、参照生成部１０５は、所定色数の抽出を行う必要はなく、符号化用パレットとのソートのみ行うことによって参照パレットを生成するものとすればよい。
【０１１９】
パレット生成部２０２は、復号部２０１および参照生成部２０５から、それぞれ追加パレットおよび参照パレットを受け取り、本実施形態の符号化装置１０のパレット生成部１０２が符号化用パレットを生成する方法と同一の方法により、復号用パレットを生成する。
【０１２０】
参照生成部２０５は、パレット生成部２０２および参照回数算出部２０４から、それぞれ復号用パレットおよび参照回数情報を受け取り、本実施形態の符号化装置１０の参照生成部１０５が参照パレットを生成する方法と同一の方法により、参照パレットを生成する。
【０１２１】
以上のように、本実施形態では、符号化用パレットおよび復号用パレット内の色数が常に所定色数となることから、第１の実施形態のように色数が変動する符号化用パレットとは異なり、これによりインデックスの取り得る値の幅が小さくなることからインデックスを符号化する際の符号量を削減することができる。また、インデックスを可変長符号化する際のテーブルが小さくなるという利点もある。
【０１２２】
なお、本実施形態では、パレット生成部１０２が生成する符号化用パレットは、ｋ個の色数である追加パレットと、（Ｎ−ｋ）個の色数である参照パレットとで構成されることから、追加パレットの色が１つ増えると、符号化用パレットに含まれる参照パレットに由来する色は１つ減少する。そこで、決定部１０１は、パレット生成部１０２の動作を考慮し、複数の追加パレットパターンから符号化用パレットを生成して、これら追加パレットパターンのそれぞれについて、割り当て部１０３および符号化部１０４で割り当て動作および符号化動作が行われた際の符号化誤差（入力画像の各画素の色と、割り当て部１０３が割り当てた色との誤差（例えば、差分絶対値和または差分二乗和等））および発生符号量を算出または推定し、これらの値から上述の式（３）に示すコストＣｏｓｔを最小化するレート歪み最適化を行うことで、追加パレットを決定してもよい。
【０１２３】
また、決定部１０１は、処理単位内の色数から追加パレットの色数の最大値（ｋｍａｘとする）を設定し、参照パレットのソート結果の上位の（Ｎ−ｋｍａｘ）個の色のみを抽出して、抽出した色と入力画素とを比較することによって追加パレットを生成してもよい。
【０１２４】
（第３の実施形態）
第３の実施形態に係る画像処理装置について、第１の実施形態に係る画像処理装置１と相違する点を中心に説明する。第１の実施形態では、基本的には、入力画像を所定の処理単位毎にラスタスキャンで符号化される。この場合、参照パレットは、ラスタスキャン順で前の処理単位における色を保持することとなるが、一方で、１ライン前の隣接する処理単位の色の情報は、失われている場合が想定される。本実施形態では、垂直方向に隣接する処理単位の色を参照可能にする動作について説明する。なお、本実施形態に係る画像処理装置の全体構成およびハードウェア構成は、第１の実施形態で説明した構成と同様である。
【０１２５】
図１４は、第３の実施形態の符号化装置の機能ブロック構成の一例を示す図である。図１４を参照しながら、本実施形態に係る画像処理装置の符号化装置１０ａの機能ブロックの構成および動作について説明する。
【０１２６】
図１４に示すように、第３の実施形態に係る符号化装置１０ａは、決定部１０１ａと、パレット生成部１０２と、割り当て部１０３ａ（第１割り当て部）と、符号化部１０４ａと、参照生成部１０５と、バッファ部１０６（記憶部）と、を有する。なお、パレット生成部１０２および参照生成部１０５の動作は、第１の実施形態で説明した動作と同様である。
【０１２７】
決定部１０１ａは、外部から入力画像（例えば、図２に示す補助記憶装置５０３に記憶された画像、または、出力Ｉ／Ｆ５０５を介して受信した画像等）を受け取り、参照生成部１０５から参照パレットを受け取り、入力画像の処理単位毎に、追加パレットを決定する。決定部１０１ａは、さらに、バッファ部１０６から参照画素を受け取り、追加パレット内の各色について、参照画素に同一または類似の色が存在するかを判定し、存在する場合、追加パレットの色を対応する参照画素の色に置き換える。ここで、参照画素とは、符号化の対象の処理単位に隣接する処理単位内の１以上の画素である。参照画素は、例えば、ラスタスキャン順で１ライン前の隣接する処理単位内の画素の全部または一部（例えば、符号化の対象の処理単位に隣接する１画素ライン等）であればよい。
【０１２８】
決定部１０１ａは、さらに、置き換えを行った追加パレットの各色が参照画素に由来するものか否かを示す情報である参照フラグ、および、どの参照画素の色に置き換えられたかを示す情報である参照インデックスを含む画素参照情報を生成する。そして、決定部１０１ａは、置き換えを行った追加パレットを、パレット生成部１０２および符号化部１０４ａに送り、画素参照情報を、符号化部１０４ａに送る。決定部１０１ａは、図２に示す符号化プロセッサ５０１により実現される。
【０１２９】
なお、決定部１０１ａは、上述の方式と異なる方式によって、追加パレットおよび画素参照情報を生成してもよい。具体的には、決定部１０１ａは、処理単位内の同一または類似の色に分類した各グループの代表色について、参照パレットまたは参照画素に、同一または類似の色が存在するかを上述の式（１）または（２）により判定する。参照パレットおよび参照画素のいずれにも同一または類似の色が存在しない場合、そのグループの代表色は、参照画素に由来しない追加パレットに追加される色となる。また、参照画素内に同一または類似の色が存在する場合、参照画素内の対応する色が、参照画素に由来する追加パレットに追加される色となる。この場合、画素参照情報には、上述のように、どの参照画素が選択されたかを示す情報が加えられる。また、参照パレット内に同一または類似の色が存在する場合は、その代表色は追加パレットに加えられない。なお、参照画素および参照パレットの双方に同一または類似の色が存在した場合、例えば、式（１）または（２）の左辺により算出される値（誤差値）を算出し、この値が小さい方を優先するものとすればよい。または、後述する符号化部１０４ａにおける発生符号量を考慮し、誤差値にそれぞれ所定の値を加算または乗算したコスト値を比較して、小さい方を優先することとしてもよい。
【０１３０】
割り当て部１０３ａは、外部から入力画像を受け取り、パレット生成部１０２から符号化用パレットを受け取り、入力画像の処理単位毎に、処理単位の各画素に、符号化用パレット内で対応する色を示す番号（パレット生成部１０２により付与された番号）をインデックスとしてそれぞれ割り当て、処理単位内で、符号化用パレット内で最も近い色として参照された回数（処理単位におけるその色に最も近い画素数）を示す参照回数を算出する。割り当て部１０３ａは、さらに、処理単位内の各画素（またはその一部）に、インデックスが示す符号化用パレットの色を割り当てることにより、局所画像を生成する。
【０１３１】
そして、割り当て部１０３ａは、処理単位の各画素に割り当てたインデックスを符号化部１０４ａに送り、算出した参照回数を示す参照回数情報を参照生成部１０５に送り、そして、生成した局所画像をバッファ部１０６に記憶させる。割り当て部１０３ａは、図２に示す符号化プロセッサ５０１により実現される。
【０１３２】
符号化部１０４ａは、決定部１０１ａから追加パレットおよび画素参照情報を受け取り、割り当て部１０３ａからインデックスを受け取り、追加パレットの情報およびインデックスを符号化して出力ストリームを生成する。そして、符号化部１０４ａは、生成した出力ストリームを外部（図１に示す記憶装置３０等）に出力する。符号化部１０４ａは、図２に示す符号化プロセッサ５０１により実現される。
【０１３３】
本実施形態では、追加パレットの色の一部は、参照画素に由来する色となっている。そこで、符号化部１０４ａは、追加パレットの参照画素に由来する色については、その色情報を符号化する代わりに、画素参照情報に含まれる参照フラグと、参照インデックスとを符号化する。具体的には、符号化部１０４ａは、まず、追加パレットの色の数を符号化する。その後、符号化部１０４ａは、追加パレットの各色について、参照フラグを符号化する。そして、参照フラグが「１」である場合、符号化部１０４ａは、その参照フラグに対応する参照インデックスを符号化する。一方、参照フラグが「０」である場合、符号化部１０４ａは、第１の実施形態の符号化部１０４と同様に、その参照フラグに対応する色を示す情報（色情報）を符号化する。
【０１３４】
また、符号化部１０４ａは、処理単位内の各画素について割り当て部１０３ａにより割り当てられたインデックスを、第１の実施形態の符号化部１０４と同様の方式で符号化する。
【０１３５】
バッファ部１０６は、割り当て部１０３ａから局所画像を受け取り、これを記憶する機能部である。バッファ部１０６は、局所画像を定められた期間（例えば、処理単位の１ラインが処理される間）記憶し、局所画像（あるいはその一部）を参照画素として決定部１０１ａに読み出される。
【０１３６】
なお、本実施形態において、参照画素は、隣接する処理単位内の全部または一部の画素としていたが、これに限定されるものではない。参照画素の中には、同一または類似の色が含まれる場合がある。そこで、バッファ部１０６が出力した画素を、参照画素生成部（図示せず）において変換して参照画素を生成し、決定部１０１ａに送るものとしてもよい。この参照画素生成部は、同一または類似の色をもつ画素をまとめることで、参照画素を生成する。これによって、参照画素の数が削減されるので、符号化部１０４ａが参照インデックスを符号化するための符号量を削減することが可能になる。
【０１３７】
また、上述では、処理単位ごとにラスタスキャン順で符号化が行われる場合について説明したが、ラスタスキャン順以外のスキャン順（例えば、ジグザグスキャン、またはＺスキャン等）で符号化が行われる場合も、同様の処理が行われるものとしてもよい。この場合、参照パレットには、直前の処理単位における色の情報が保持されることから、この処理単位と異なる隣接する処理単位内の画素（またはその一部）を参照画素として利用するものとすればよい。このような場合でも、追加パレットを符号化するための符号量を削減することができる。
【０１３８】
また、図１４に示した決定部１０１ａ、パレット生成部１０２、割り当て部１０３ａ、符号化部１０４ａ、参照生成部１０５、およびバッファ部１０６は、機能を概念的に示したものであって、このような構成に限定されるものではない。例えば、図１４で独立した機能部として図示した複数の機能部を、１つの機能部として構成してもよい。一方、図１４の１つの機能部が有する機能を複数に分割し、複数の機能部として構成するものとしてもよい。
【０１３９】
また、図１４に示した決定部１０１ａ、パレット生成部１０２、割り当て部１０３ａ、符号化部１０４ａ、および参照生成部１０５は、いずれも図２に示す符号化プロセッサ５０１により実現されるものとしたが、これに限定されるものではない。すなわち、上述の各機能部のうち少なくともいずれかが、記憶装置（例えば、図２に示す補助記憶装置５０３）等の記憶媒体に記憶されているプログラムがＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）により実行されることによって実現されるものとしてもよい。
【０１４０】
図１５は、第３の実施形態の復号装置の機能ブロック構成の一例を示す図である。図１５を参照しながら、本実施形態に係る画像処理装置の復号装置２０ａの機能ブロックの構成および動作について説明する。
【０１４１】
図１５に示すように、第３の実施形態に係る復号装置２０ａは、復号部２０１ａと、パレット生成部２０２と、割り当て部２０３ａ（第２割り当て部）と、参照回数算出部２０４と、参照生成部２０５と、バッファ部２０６と、を有する。なお、パレット生成部２０２、参照回数算出部２０４および参照生成部２０５の動作は、第１の実施形態で説明した動作と同様である。
【０１４２】
復号部２０１ａは、外部からビットストリーム（入力ストリーム）（例えば、図２に示すＲＡＭ５０４に記憶されたビットストリーム）を受け取り、この入力ストリームから追加パレットとインデックスとに復号する。また、復号部２０１ａは、さらに、バッファ部２０６から参照画素を受け取る。復号部２０１ａは、追加パレットを復号する際、まず、参照フラグを復号し、参照フラグが「１」である場合、参照インデックスを復号する。この場合、復号部２０１ａは、参照インデックスが示す参照画素の色を追加パレットへ加える。一方、復号部２０１ａは、参照フラグが「０」である場合、第１の実施形態と同様に、追加パレットの色を示す情報（色情報）を復号する。
【０１４３】
そして、復号部２０１ａは、復号した追加パレットをパレット生成部２０２に送り、復号したインデックスを割り当て部２０３ａおよび参照回数算出部２０４にそれぞれ送る。復号部２０１ａは、図２に示す復号プロセッサ５０２により実現される。
【０１４４】
割り当て部２０３ａは、復号部２０１ａおよびパレット生成部２０２から、それぞれインデックスおよび復号用パレットを受け取り、処理単位の各画素に、インデックスに対応する復号用パレットの色をそれぞれ割り当てることにより復号画像を生成する。そして、割り当て部２０３ａは、生成した復号画像を、外部（例えば、図２に示す表示装置２等）およびバッファ部２０６に出力する。割り当て部２０３ａは、図２に示す復号プロセッサ５０２により実現される。
【０１４５】
バッファ部２０６は、割り当て部２０３ａから復号画像を受け取り、これを記憶する機能である。バッファ部２０６は、復号画像を定められた期間（例えば、処理単位の１ラインが処理される間）記憶し、復号画像（あるいはその一部）を参照画素として復号部２０１ａに読み出される。
【０１４６】
なお、符号化装置１０ａが上述の参照画素生成部を有するものとした場合、復号装置２０ａの構成および動作もそれに合せて変更されるものとしてもよい。具体的には、バッファ部２０６が出力した画素を、参照画素生成部（図示せず）において符号化装置１０ａと同様の方式によって変換して参照画素を生成し、復号部２０１ａに送るものとしてもよい。
【０１４７】
符号化部１０４ａにおいて、追加パレットの色をそのまま符号化した場合、例えば、Ｒ、Ｇ、Ｂの各コンポーネントの値をそれぞれ８ビットで符号化する場合では、１色あたり２４ビットの符号量を要する。一方、本実施形態のように、参照インデックスを符号化する場合、参照画素の数が例えば４であった場合、参照インデックスの符号量は２ビットで済むことになる。上述のように、参照パレットは、符号化順で以前の処理単位における色の情報を保持するが、１ライン前の隣接する処理単位の色の情報は、失われている場合が想定される。第１の実施形態では、これらの色が符号化の対象の処理単位に出現した場合、追加パレットとしてその色を符号化していた。本実施形態によれば、１ライン前の隣接する処理単位内の色を参照画素として利用するので、追加パレットの符号量を削減することが可能になり、これにより符号化装置１０ａの符号化効率が改善することができる。
【０１４８】
本発明の各実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、および変更を行うことができる。これら実施形態は、発明の範囲および要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１４９】
１  画像処理装置
２  表示装置
１０、１０ａ  符号化装置
２０、２０ａ  復号装置
３０  記憶装置
１０１、１０１ａ  決定部
１０２  パレット生成部
１０３、１０３ａ  割り当て部
１０４、１０４ａ  符号化部
１０５  参照生成部
１０６  バッファ部
２０１、２０１ａ  復号部
２０２  パレット生成部
２０３、２０３ａ  割り当て部
２０４  参照回数算出部
２０５  参照生成部
２０６  バッファ部
５０１  符号化プロセッサ
５０１ａ  キャッシュ
５０２  復号プロセッサ
５０２ａ  キャッシュ
５０３  補助記憶装置
５０４  ＲＡＭ
５０５  出力Ｉ／Ｆ
５０６  Ｉ／Ｆ
５０７  バス
６００  処理単位
６１０、６１１、６１５  参照パレット
６２０、６２１、６２５  追加パレット
６３０、６３１  符号化用パレット
６３１ａ  追加パレット部
６３１ｂ  参照パレット部
６３５  符号化用パレット
６４０  インデックス
６５０  参照回数情報
７００  復号用パレット
７１０  インデックス
７２０  復号画像
【図１】
0006545570.tif 000003
【図２】
0006545570.tif 000004
【図３】
0006545570.tif 000005
【図４】
0006545570.tif 000006
【図５】
0006545570.tif 000007
【図６】
0006545570.tif 000008
【図７】
0006545570.tif 000009
【図８】
0006545570.tif 000010
【図９】
0006545570.tif 000011
【図１０】
0006545570.tif 000012
【図１１】
0006545570.tif 000013
【図１２】
0006545570.tif 000014
【図１３】
0006545570.tif 000015
【図１４】
0006545570.tif 000016
【図１５】
0006545570.tif 000017