(57)【要約】  【課題】  高速な符号化処理を実現することができる符号化装置を提供する。  【解決手段】  符号化装置２は、例えば、ハッシュテーブル及び履歴テーブルを２組有し、一方を新ハッシュテーブル及び新履歴テーブルとして新エントリが追加されるテーブルとし、他方を旧ハッシュテーブル及び旧履歴テーブルとして参照のみが許容されるテーブルとする。符号化装置２は、これらのテーブルを画素ライン毎に新旧を入れ替えて使用することにより、データの古さを確認することなく古いデータを削除する。また、符号化装置２は、ハッシュテーブルに出現の有無を記憶することにより、ハッシュテーブルのデータサイズを抑えてもよい。【選択図】図５
2005159820.tif 000002
【特許請求の範囲】
【請求項１】
符号化対象として入力された入力データの履歴を記憶する複数の記憶手段と、
いずれかの記憶手段に記憶される履歴に基づいて、入力データを符号化する符号化手段と、
前記符号化手段により符号化処理がなされた入力データの履歴がいずれかの記憶手段に書き込まれる場合に、複数の記憶手段を順番に割り当てる記憶割当手段と
を有する符号化装置。
【請求項２】
前記入力データは、画像データであり、
前記記憶割当手段は、画像データの履歴を画像の１ライン毎にいずれかの記憶手段に割り当てる
請求項１に記載の符号化装置。
【請求項３】
入力された入力データに基づいて、ハッシュ値を算出するハッシュ算出手段と、
前記ハッシュ値が記憶される複数の記憶手段と、
いずれかの記憶手段に記憶されるハッシュ値を参照して、符号化対象となる入力データと既に入力された入力データとの相関関係を判定する相関判定手段と
前記ハッシュ算出手段により算出されるハッシュ値がいずれかの記憶手段に書き込まれる場合に、複数の記憶手段を順番に割り当てる記憶割当手段と
を有する符号化装置。
【請求項４】
符号化対象として入力される入力データに基づいて、ハッシュ値を算出するハッシュ算出手段と、
既に入力された入力データについて算出されたハッシュ値を記憶する記憶手段と、
前記記憶領域に記憶されているハッシュ値と入力データのハッシュ値とを比較して、同一のハッシュ値が存在するか否かを判定する有無判定手段と、
前記有無判定手段により同一のハッシュ値が存在すると判定された場合に、このハッシュ値に対応する入力データの探索処理を行い、前記有無判定手段により同一のハッシュ値が存在しないと判定された場合に、前記探索処理を禁止する画素探索手段と、
前記画素探索手段により探索された入力データを参照して、符号化対象の入力データを符号化する符号化手段と
を有する符号化装置。
【請求項５】
前記入力データは、少なくとも画素値が含まれる画像データであり、
前記有無判定手段は、前記符号化手段により参照可能な画素の範囲内に、符号化対象画素とハッシュ値が一致する画素が存在するか否かを判定する
請求項４に記載の符号化装置。
【請求項６】
前記入力データは、画像を構成する各画素の画素値及びこれらの位置情報が含まれる画像データであり、
前記ハッシュ算出手段は、この画像データの画素の位置情報及びこの画素の画素値に基づいて、ハッシュ値を算出する
請求項３又は４に記載の符号化装置。
【請求項７】
前記位置情報は、それぞれの画素に対して符号化対象として走査する順序で連続的に割り当てられた二進数の上位ビットであり、
前記ハッシュ算出手段は、それぞれの画素に割り当てられた二進数の上位ビットと、これらの画素の画素値とに基づいて、ハッシュ値を算出する
請求項６に記載の符号化装置。
【請求項８】
前記二進数の上位ビットは、前記符号化手段により参照可能な画素の範囲に対応する
請求項７に記載の符号化装置。
【請求項９】
複数の記憶領域に記憶される入力データの履歴に基づいて、符号化対象として入力される入力データを符号化し、
符号化処理がなされた入力データの履歴をいずれかの記憶領域に書き込む場合に、複数の記憶領域を順番に割り当てる
符号化方法。
【請求項１０】
コンピュータを含む符号化装置において、
複数の記憶領域に記憶される入力データの履歴に基づいて、符号化対象として入力される入力データを符号化するステップと、
符号化処理がなされた入力データの履歴をいずれかの記憶領域に書き込む場合に、複数の記憶領域を順番に割り当てるステップと
を前記符号化装置のコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化対象データを符号化する場合に、他のデータを参照する符号化装置に関する。
【背景技術】
【０００２】
例えば、既出データを辞書として符号化するＬＺ符号化方式などでは、既出データの探索のために、データの出現履歴が登録された履歴テーブルを用いる場合がある。このような履歴テーブルを更新する場合に、それぞれのデータの古さを確認しながら削除等されていた。
また、特許文献１は、現行辞書及び待機辞書を同時に作成するデータ圧縮／伸長システムを開示する。
【特許文献１】特開平７−２７３６６７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、上述した背景からなされたものであり、高速な符号化処理を実現することができる符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、符号化対象として入力された入力データの履歴を記憶する複数の記憶手段と、いずれかの記憶手段に記憶される履歴に基づいて、入力データを符号化する符号化手段と、前記符号化手段により符号化処理がなされた入力データの履歴がいずれかの記憶手段に書き込まれる場合に、複数の記憶手段を順番に割り当てる記憶割当手段とを有する。
【０００５】
好適には、前記入力データは、画像データであり、前記記憶割当手段は、画像データの履歴を画像の１ライン毎にいずれかの記憶手段に割り当てる。
【０００６】
また、本発明にかかる符号化装置は、入力された入力データに基づいて、ハッシュ値を算出するハッシュ算出手段と、前記ハッシュ値が記憶される複数の記憶手段と、いずれかの記憶手段に記憶されるハッシュ値を参照して、符号化対象となる入力データと既に入力された入力データとの相関関係を判定する相関判定手段と、前記ハッシュ算出手段により算出されるハッシュ値がいずれかの記憶手段に書き込まれる場合に、複数の記憶手段を順番に割り当てる記憶割当手段とを有する。
【０００７】
また、本発明にかかる符号化装置は、符号化対象として入力される入力データに基づいて、ハッシュ値を算出するハッシュ算出手段と、既に入力された入力データについて算出されたハッシュ値を記憶する記憶手段と、前記記憶領域に記憶されているハッシュ値と入力データのハッシュ値とを比較して、同一のハッシュ値が存在するか否かを判定する有無判定手段と、前記有無判定手段により同一のハッシュ値が存在すると判定された場合に、このハッシュ値に対応する入力データの探索処理を行い、前記有無判定手段により同一のハッシュ値が存在しないと判定された場合に、前記探索処理を禁止する画素探索手段と、前記画素探索手段により探索された入力データを参照して、符号化対象の入力データを符号化する符号化手段とを有する。
【０００８】
好適には、前記入力データは、少なくとも画素値が含まれる画像データであり、前記有無判定手段は、前記符号化手段により参照可能な画素の範囲内に、符号化対象画素とハッシュ値が一致する画素が存在するか否かを判定する。
【０００９】
好適には、前記入力データは、画像を構成する各画素の画素値及びこれらの位置情報が含まれる画像データであり、前記ハッシュ算出手段は、この画像データの画素の位置情報及びこの画素の画素値に基づいて、ハッシュ値を算出する。
【００１０】
好適には、前記位置情報は、それぞれの画素に対して符号化対象として走査する順序で連続的に割り当てられた二進数の上位ビットであり、前記ハッシュ算出手段は、それぞれの画素に割り当てられた二進数の上位ビットと、これらの画素の画素値とに基づいて、ハッシュ値を算出する。
【００１１】
好適には、前記二進数の上位ビットは、前記符号化手段により参照可能な画素の範囲に対応する。
【００１２】
［符号化方法］
また、本発明にかかる符号化方法は、複数の記憶領域に記憶される入力データの履歴に基づいて、符号化対象として入力される入力データを符号化し、符号化処理がなされた入力データの履歴をいずれかの記憶領域に書き込む場合に、複数の記憶領域を順番に割り当てる。
【００１３】
［プログラム］
また、本発明にかかるプログラムは、コンピュータを含む符号化装置において、複数の記憶領域に記憶される入力データの履歴に基づいて、符号化対象として入力される入力データを符号化するステップと、符号化処理がなされた入力データの履歴をいずれかの記憶領域に書き込む場合に、複数の記憶領域を順番に割り当てるステップとを前記符号化装置のコンピュータに実行させる。
【発明の効果】
【００１４】
本発明の符号化装置によれば、符号化処理を高速化することができる。
【発明を実施するための最良の形態】
【００１５】
［第１の実施形態］
まず、本発明の理解を助けるために、その背景及び概略を説明する。
ＬＺ７７符号化方式は、符号化対象データ列と一致するデータ列を、既出データ群（ウィンドウ）から検索し、この符号化対象データ列の位置から検索により発見されたデータ列までの距離とその一致長とを符号化し、符号化対象データ列の符号とする圧縮方式である。このＬＺ７７符号化方式では、最長一致列の検索処理においてハッシュ関数を用いることにより、符号化処理を高速化できる。
【００１６】
図１は、ハッシュ関数を用いて高速化したＬＺ７７符号化方式を説明する図であり、図１（Ａ）は、符号化処理における参照可能範囲であるウインドウを例示し、図１（Ｂ）は、符号化装置に記憶されるハッシュテーブルを例示し、図１（Ｃ）は、符号化装置に記憶される履歴テーブルを例示する。
図１（Ａ）に例示するように、符号化装置は、既定の参照範囲（すなわち、ウインドウ）の中から、符号化対象データ列と一致するデータ列を探索し、発見されたデータ列のうち最長のデータ列の位置と一致長とを符号化する。このウインドウは、そのサイズを一定に保ったまま、符号化対象データ列の位置に応じて変化する。
そして、このような最長一致列の候補を絞るために、符号化装置は、各画素のハッシュ値を算出して、図１（Ｂ）に例示するようなハッシュテーブルを生成する。生成されるハッシュテーブルは、データ（画素値）のハッシュ値と、そのデータの最新の出現位置とを互いに対応付ける。そして、符号化装置は、このハッシュテーブルを用いて、ハッシュ値が同一のデータを検索することにより、直近の一致データを決定する。
さらに、符号化装置は、図１（Ｃ）に例示するように、既出のデータ群について一致するデータの出現位置を対応付ける履歴データを有し、決定された直近の一致データ（画素）から一致するデータの出現位置を辿ることにより、複数の一致データを最長一致列の候補として抽出する。
なお、ハッシュ値が一致する場合であっても実際のデータが一致しない場合もあるので、符号化装置は、ハッシュテーブル又は履歴テーブルの出現位置に基づいて、ウインドウ内から実際のデータ値（画素値）を参照して、符号化対象データ（画素値）の一致／不一致を判定する。
【００１７】
ここで、ウインドウのサイズ（参照可能な画素値の範囲）は、符号化装置と復号化装置との間で対応している必要があるため、ウインドウから外れる古いデータは、符号化装置により参照されないように削除等する必要がある。したがって、このウインドウから外れるデータに対応するハッシュ値及び履歴データも、ハッシュテーブル及び履歴テーブルから削除等されることが望ましい。
このようなハッシュテーブル又は履歴テーブルの更新方法としては、履歴テーブルをリングバッファで構成して処理と共に更新する形態、履歴テーブルに新しいエントリを追加するとともに、古いデータが選択されないよう、ハッシュテーブルから古いエントリを削除する形態、又は、ハッシュテーブルに記憶されるデータの使用可否は出現位置から判断する形態などが考えられる。しかしながら、これらの形態では、それぞれに特別な処理が必要となる。
そこで本発明にかかる符号化装置２は、既定のデータ範囲に対応するハッシュテーブル及び／又は履歴テーブルを複数用意して、これらのハッシュテーブル及び／又は履歴テーブルを符号化処理の順序に応じて使いまわすことにより、ハッシュテーブル及び／又は履歴テーブルの更新処理に伴う手間を削減する。
なお、本実施形態において、画像データを符号化対象の具体例として説明するが、これに限定されるものではない。
【００１８】
［ハードウェア構成］
次に、符号化装置２のハードウェア構成を説明する。
図２は、本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
図２に例示するように、符号化装置２は、ＣＰＵ２１２及びメモリ２１４などを含む制御装置２１、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置およびキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２５から構成される。
符号化装置２は、例えば、本発明にかかる符号化プログラム５（後述）がプリンタドライバの一部としてインストールされた汎用コンピュータであり、通信装置２２又は記録装置２４などを介して画像データを取得し、取得された画像データを符号化してプリンタ装置３に送信する。
【００１９】
［第１の符号化プログラム］
図３は、制御装置２１（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
図３に例示するように、符号化プログラム５は、画像データ取得部５００、ハッシュ算出部５１０、書込み部５２０、データ記憶部５３０、相関判定部５４０及び符号化部５６０を有する。
符号化プログラム５において、画像データ取得部５００は、通信装置２２又は記録装置２４などを介して、ラスタライズされた画像データを取得し、ハッシュ算出部５１０に対して出力する。
ハッシュ算出部５１０は、画像データ取得部５００から入力された画像データに基づいて、ハッシュ値を算出し、算出されたハッシュ値と、入力された画像データとを書込み部５２０に対して出力する。
【００２０】
書込み部５２０は、ハッシュ算出部５１０から入力されたハッシュ値及び画像データをデータ記憶部５３０の各テーブルに書き込む。また、書込み部５２０は、入力されたハッシュ値及び画像データを相関判定部５４０に対して出力する。
より具体的には、書込み部５２０は、エントリ更新部５２２及びテーブル切換部５２４（記憶割当手段）を含む。
エントリ更新部５２２は、入力されたハッシュ値を、後述する複数のハッシュテーブル（第１ハッシュテーブル５３２又は第２ハッシュテーブル５３４）のいずれかに書き込む。例えば、エントリ更新部５２２は、入力されたハッシュ値（すなわち、符号化対象画素についてハッシュ算出部５１０により算出されたハッシュ値）と、第１ハッシュテーブル５３２及び第２ハッシュテーブル５３４に記憶されているハッシュ値とを比較して、一致するハッシュ値を検索する。一致するハッシュ値がいずれかのハッシュテーブルに存在する場合に、エントリ更新部５２２は、この符号化対象画素が含まれる部分画像（画素ライン）に対応するハッシュテーブルに、この符号化対象画素のハッシュ値及び出現位置を新エントリとして追加又は上書きし、このハッシュテーブルに対応する履歴テーブルに、この符号化対象画素の出現位置と、ハッシュ値が一致した一致画素の出現位置（すなわち、符号化対象画素とハッシュ値が一致する画素の最新の出現位置）とを新エントリとして追加する。
また、エントリ更新部５２２は、一致するハッシュ値がいずれかのハッシュテーブルに存在する場合に、このハッシュテーブルを参照して、最新のハッシュ値と対応付けられた出現位置を読み出し、読み出された出現位置を一致判定部５４２に対して出力する。
【００２１】
テーブル切換部５２４は、入力された画像データが部分画像の最終データ（ラインの後端）であるか否かを判定し、最終データ（ラインの後端）である場合に、ハッシュテーブル及び履歴テーブルの切換処理を行う。具体的には、テーブル切換部５２４は、ラインの後端である場合に、最も古いデータが含まれるハッシュテーブルを初期化して、このハッシュテーブルに次のハッシュ値を書き込むようにエントリ更新部５２２に指示する。また、複数の履歴テーブルは、それぞれいずれかのハッシュテーブルと対応しており、テーブル切換部５２４は、初期化されたハッシュテーブルに対応する履歴テーブルを初期化して、この履歴テーブルに次の一致情報（本例では、画素値が一致する画素の出現位置）を書き込むよう一致判定部５４２に対して指示する。
【００２２】
データ記憶部５３０は、書込み部５２０から入力されるハッシュ値及び画像データと、相関判定部５４０から入力される一致情報とを記憶する。より具体的には、データ記憶部５３０は、第１ハッシュテーブル５３２、第２ハッシュテーブル５３４、第１履歴テーブル５３６、第２履歴テーブル５３８及び画素値ウインドウ５３９を含む。
第１ハッシュテーブル５３２及び第２ハッシュテーブル５３４は、画像を構成する画素の画素値に基づいて算出されたハッシュ値をこの画素の出現位置に対応付けて記憶する記憶領域であり、互いに異なる部分画像（画素ライン）に相当するハッシュ値を記憶する。本例では、第１ハッシュテーブル５３２及び第２ハッシュテーブル５３４は、画像の主走査方向に配列された画素ラインに対応する記憶容量を有し、それぞれ副走査方向に交互に画素ラインを記憶する。すなわち、第１ハッシュテーブル５３２は、まず第１ラインの画素群のハッシュ値を記憶し、次に、第２ハッシュテーブル５３４が、第２ラインの画素群のハッシュ値を記憶し、第３ラインの画素についてハッシュ値が算出されると、第１ハッシュテーブル５３２は、テーブル切換部５２４により初期化された後で、この第３ラインの画素群のハッシュ値を記憶する。このように、第１ハッシュテーブル５３２及び第２ハッシュテーブル５３４は、符号化対象画素の副走査方向への移動に応じて、交互に各画素ラインについて生成されたハッシュ値を記憶していく。
【００２３】
第１履歴テーブル５３６及び第２履歴テーブル５３８は、それぞれ第１ハッシュテーブル５３２及び第２ハッシュテーブル５３４に対応している。すなわち、第１履歴テーブル５３６及び第２履歴テーブル５３８は、それぞれ第１ハッシュテーブル５３２及び第２ハッシュテーブル５２４に対応する部分画像（画素ライン）に含まれる画素の出現位置と、この画素とハッシュ値（又は画素値）が一致する既出の画素（以下、一致画素）の出現位置（すなわち、一致情報）とを互いに対応付けて記憶している。本例の第１履歴テーブル５３６及び第２履歴テーブル５３８は、同一のハッシュ値を有する２つの画素について、それぞれの画素の出現位置を互いに対応付けて記憶する。例えば、第３ラインの画素値が符号化対象である場合に、第１履歴テーブル５３６は、いずれも第３ラインに含まれる画素同士が一致する場合のこれらの出現位置、又は、第２ラインに含まれる画素と第３ラインに含まれる画素とが一致する場合のこれらの出現位置を互いに対応付けて記憶し、第２履歴テーブル５３８は、いずれも第２ラインに含まれる画素同士が一致する場合のこれらの出現位置、又は、第１ラインに含まれる画素と第２ラインに含まれる画素とが一致する場合のこれらの画素の出現位置を互いに対応付けて記憶する。
また、第１履歴テーブル５３６及び第２履歴テーブル５３８は、上記ハッシュテーブルと同様に、互いに異なる部分画像（画素ライン）の画素について、一致情報を記憶しており、上記ハッシュテーブルの初期化に応じて、対応する履歴テーブルが初期化される。
【００２４】
画素値ウインドウ５３９は、入力された画像データを記憶する。本例の画素値ウインドウ５３９は、符号化対象画素の移動に応じて、符号化対象画素の画素値と、この画素の出現位置とを互いに対応付けて新たに記憶し、ウインドウから外れる画素の画素値及び出現位置を削除して行く。例えば、画素値ウインドウ５３９は、画素の出現位置を記憶領域における相対アドレスとして、各画素の画素値を記憶する。
【００２５】
相関判定部５４０は、符号化対象画素と他の画素との相関関係（画素値が一致する画素の連続数、画素値の差分値の連続数など）を判定し、判定結果を相関情報として符号化部５６０に対して出力する。本例の相関判定部５４０は、第１履歴テーブル５３６及び第２履歴テーブル５３８を用いて、符号化対象画素と画素値が一致する既出の画素（一致画素）を検索して、発見された画素を最長一致列の候補とする。そして、相関判定部５３６は、これらの候補の中から、最長一致列を決定する。
【００２６】
より具体的には、相関判定部５４０は、一致判定部５４２及び最長列判定部５４４を含む。
一致判定部５４２は、エントリ更新部５２０から入力される出現位置（符号化対象画素と画素値が一致する画素の最新の出現位置）に基づいて、第１履歴テーブル５３６及び第２履歴テーブル５３８をたどり、ハッシュ値が一致する既出の画素を抽出し、抽出された画素の出現位置に基づいて画素値ウインドウ５３９からこれらの画素の画素値を読み出す。そして、一致判定部５４２は、読み出された少なくとも１つの画素値と、書込み部５２０から入力された画素値（すなわち、符号化対象画素の画素値）とを比較して、画素値が一致している既出の画素の出現位置を一致情報として最長列判定部５４４に対して出力する。
【００２７】
最長列判定部５４４は、一致判定部５４２から入力される出現位置（一致情報）に基づいて、一致長が最も長い画素列（最長一致列）を判定し、この最長一致列の出現位置及び一致長（画素連続数）を符号化部５６０に対して出力する。具体的には、最長列判定部５４４は、最長一致列の候補それぞれについて一致数カウンタを設け、一致判定部５４２から出現位置（一致情報）が入力される毎に、一致数カウンタのカウント値を増加させて、このカウント値に基づいて最長一致列を判定する。なお、最長列判定部５４４は、入力される出現位置がない場合（すなわち、符号化対象画素と一致する画素が存在しない場合）に、この符号化対象画素の画素値を符号化部５６０に対して出力する。
【００２８】
符号化部５６０は、相関判定部５４０から入力された最長一致列の出現位置及び一致長あるいは符号化対象画素の画素値を符号化し、この符号データを通信装置２２又は記録装置２４に対して出力する。
【００２９】
図４は、データ記憶部５３０により記憶されるデータを例示する図であり、図４（Ａ）は、第１ハッシュテーブル５３２又は第２ハッシュテーブル５３４を例示し、図４（Ｂ）は、第１履歴テーブル５３６及び第２履歴テーブル５３８を例示する。
図４（Ａ）に例示するように、第１ハッシュテーブル５３２及び第２ハッシュテーブル５３４は、それぞれ対応する画素ラインに含まれる画素について算出されたハッシュ値と、その画素の出現位置とを互いに対応付けて記憶する。
また、図４（Ｂ）に例示するように、第１履歴テーブル５３６及び第２履歴テーブル５３８は、それぞれに対応する画素ラインに含まれる所定の画素の出現位置と、この画素よりも前に出現した同一画素値の画素の出現位置とを互いに対応付けて記憶する。なお、本例において履歴テーブルに新たなエントリが追加されるのは、第１ハッシュテーブル５３２又は第２ハッシュテーブル５３４に登録されたエントリから、ハッシュ値が一致する既出の画素が抽出される場合のみであるため、これら第１履歴テーブル５３６及び第２履歴テーブル５３８に記憶される画素の出現位置は、それぞれの履歴テーブルに対応する画素ラインよりも１ライン前までである。すなわち、第１履歴テーブル５３６又は第２履歴テーブル５３８に基づいて参照される画素の範囲は、それぞれの履歴テーブルに対応する画素ラインの１ライン前までに制限されている。
【００３０】
［全体動作］
次に、符号化装置２による符号化処理の全体動作を説明する。
図５は、符号化プログラム５の動作（Ｓ１０）を示すフローチャートである。
図５に示すように、ステップ１００（Ｓ１００）において、画像データ取得部５００が画像データを取得すると、符号化プログラム５は、注目画素位置の初期設定、ハッシュテーブル及び履歴テーブルの初期化、並びに、一致数カウンタの初期化などを行う。なお、ハッシュテーブル及び履歴テーブルが初期化されると、第１ハッシュテーブル５３２及び第１履歴テーブル５３６は、テーブル切換部５２４により書込み許可状態及び参照許可状態となり、第２ハッシュテーブル５３４及び第２履歴テーブル５３８は、参照許可状態となる。
また、画像データ取得部５００は、取得された画像データがラスタデータでない場合には、取得された画像データをラスタデータに変換する。
画像データ取得部５００は、ラスタデータ（各画素の画素値及び出現座標）を１画素ずつハッシュ算出部５１０に対して出力する。
【００３１】
ステップ１０５（Ｓ１０５）において、ハッシュ算出部５１０は、画像データ取得部５００から入力された画素値に基づいて、ハッシュ値を算出し、算出されたハッシュ値と、入力された画素値及び出現座標とを書込み部５２０に対して出力する。
【００３２】
ステップ１１０（Ｓ１１０）において、エントリ更新部５２２は、書込み許可状態にあるハッシュテーブル（新ハッシュテーブル）において、ハッシュ算出部５１０から入力されたハッシュ値と一致するエントリを、新しいエントリから順に検索する。
ステップ１１５（Ｓ１１５）において、エントリ更新部５２２は、ハッシュ値が一致するエントリが発見された場合に、このエントリの出現座標を新ハッシュテーブルから読み出して、読み出された出現座標を一致判定部５４２に対して出力する。次いで、エントリ更新部５２２は、新ハッシュテーブルにおけるこのエントリの出現座標を、この符号化対象画素の出現座標に書き換え、さらに、新履歴テーブルに、このエントリの出現座標（ハッシュ値が一致した既出画素の出現座標）とこの符号化対象画素の出現位置とを対応付けたエントリを追加する。
一方、エントリ更新部５２２は、ハッシュ値が一致するエントリが存在しない場合に、入力されたハッシュ値及び出現座標（すなわち、符号化対象画素のハッシュ値及び出現座標）を新しいエントリとして新ハッシュテーブルに追加して、Ｓ１２０及びＳ１２５の処理をスキップし、旧テーブルの処理（Ｓ１４０以降）に移行させる。
また、書込み部５２０は、入力された画素値及び出現座標を画素値ウインドウ５３９に記憶して、ウインドウの範囲を更新すると共に、入力されたハッシュ値、画素値及び出現座標を相関判定部５４０に対して出力する。
【００３３】
ステップ１２０（Ｓ１２０）において、一致判定部５４０は、エントリ更新部５２２から入力された出現位置に基づいて、新ハッシュテーブルに対応する履歴テーブル（新履歴テーブル）を順にたどり、符号化対象画素とハッシュ値が一致する一致画素の出現位置を新しいものから順に抽出する。
ステップ１２５（Ｓ１２５）において、符号化プログラム５は、新履歴テーブルに記憶されている最後のエントリまで検索が完了したか否かを判断し、新履歴テーブルの最後のエントリまで検索が完了した場合に、Ｓ１４０の処理に移行し、これ以外の場合に、Ｓ１３０の処理に移行する。
【００３４】
ステップ１３０（Ｓ１３０）において、一致判定部５４２は、抽出された出現座標に基づいて画素値ウインドウ５３９から一致画素の画素値を読み出し、読み出された画素値と、書込み手段５２０から入力された画素値（すなわち、符号化対象画素の画素値）とを比較する。
一致判定部５４２は、これらの画素値が一致する場合に、抽出された出現座標を一致情報として最長列判定部５４４に対して出力し、一致しない場合に、その旨を最長列判定部５４４に対して出力する。
【００３５】
ステップ１３５（Ｓ１３５）において、最長列判定部５４４は、一致判定部５４２から一致情報（出現座標）が入力されると、入力された出現座標に対応する一致数カウンタ（連続する出現座標に基づいてカウントされているもの）のカウント値を１つ増加させる。なお、最長列判定部５４４は、入力された出現座標に対応する一致数カウンタが無い場合に、この出現座標に対応する一致数カウンタを追加する。
また、最長列判定部５４４は、一致判定部５４２から一致しない旨が入力されると、そのまま次のステップに移行する。このように、ハッシュ値が一致しても実際の画素値が一致しない場合（ハッシュの衝突）もあるので、一致判定部５４２が実際の画素値を比較して、画素値が一致する場合にのみカウント値を増加させる。
【００３６】
ステップ１４０（Ｓ１４０）において、エントリ更新部５２２は、参照のみが許可されるハッシュテーブル（旧ハッシュテーブル）において、ハッシュ値算出手段から入力されたハッシュ値と一致するエントリを、新しいエントリから順に検索する。
エントリ更新部５２２は、ハッシュ値が一致するエントリが発見された場合に、このエントリの出現座標を旧ハッシュテーブルから読み出して、読み出された出現座標を一致判定部５４２に対して出力する。次いで、エントリ更新部５２２は、新履歴テーブルに、このエントリの出現座標（ハッシュ値が一致した既出画素の出現座標）とこの符号化対象画素の出現位置とを対応付けたエントリを追加する。
一方、エントリ更新部５２２は、ハッシュ値が一致するエントリが存在しない場合には、Ｓ１４５及びＳ１５０の処理をスキップして、Ｓ１６５の処理に移行させる。
【００３７】
ステップ１４５（Ｓ１４５）において、一致判定部５４０は、エントリ更新部５２２から入力された出現位置に基づいて、旧ハッシュテーブルに対応する履歴テーブル（旧履歴テーブル）を順にたどり、符号化対象画素とハッシュ値が一致する一致画素の出現位置を新しいものから順に抽出する。
ステップ１５０（Ｓ１５０）において、符号化プログラム５は、旧履歴テーブルに記憶されている最後のエントリまで検索が完了したか否かを判断し、旧履歴テーブルの最後のエントリまで検索が完了した場合に、Ｓ１６５の処理に移行し、これ以外の場合に、Ｓ１５５の処理に移行する。
【００３８】
ステップ１５５（Ｓ１５５）において、一致判定部５４２は、抽出された出現座標に基づいて画素値ウインドウ５３９から一致画素の画素値を読み出し、読み出された画素値と、書込み手段５２０から入力された画素値（すなわち、符号化対象画素の画素値）とを比較する。
一致判定部５４２は、これらの画素値が一致する場合に、抽出された出現座標を一致情報として最長列判定部５４４に対して出力し、一致しない場合に、その旨を最長列判定部５４４に対して出力する。
【００３９】
ステップ１６０（Ｓ１６０）において、最長列判定部５４４は、一致判定部５４２から一致情報（出現座標）が入力されると、入力された出現座標に対応する一致数カウンタのカウント値を１つ増加させる。なお、最長列判定部５４４は、入力された出現座標に対応する一致数カウンタが無い場合に、この出現座標に対応する一致数カウンタを追加する。
また、最長列判定部５４４は、一致判定部５４２から一致しない旨が入力されると、そのまま次のステップに移行する。
【００４０】
ステップ１６５（Ｓ１６５）において、符号化プログラム５は、符号化対象画素が画素ラインの後端であるか否かを判定し、画素ラインの後端である場合に、Ｓ１７０の処理に移行し、画素ラインの後端でない場合に、Ｓ１００の処理に戻って次の画素についてＳ１００〜Ｓ１６０までの処理を行う。
【００４１】
ステップ１７０（Ｓ１７０）において、テーブル切換部５２４は、現時点で新ハッシュテーブルであるものを旧ハッシュテーブルに切り替えて、現時点で新履歴テーブルであるものを旧履歴テーブルに切り替えて、これらのテーブルを参照のみが許可される状態にする。また、テーブル切換部５２４は、現時点で旧ハッシュテーブルであるものを新ハッシュテーブルに切り替えて、現時点で旧履歴テーブルであるものを新履歴テーブルに切り替えて、これらのテーブルを書込みが許可される状態にして初期化の準備を施す。
ステップ１７５（Ｓ１７５）において、テーブル切換部５２４は、新ハッシュテーブル及び新履歴テーブルを初期化する。
【００４２】
ステップ１８０（Ｓ１８０）において、符号化プログラム５は、入力された画像の全ての画素について処理が完了したか否かを判断する。
全ての画素について処理が完了した場合に、最長列判定部５４４は、一致数カウンタのカウント値に基づいて、最長の一致列を判定し、この一致列までの距離（参照される一致列と符号化対象の一致列との間の距離）及びその一致長を符号化部５６０に対して出力する。符号化部５６０は、最長列判定部５４４により入力された一致列までの距離及び一致長を符号化し、符号化対象の一致列の符号として出力し、符号化対象となる一致列に含まれない画素についてはその画素値を符号化して出力して、符号化処理を終了する。
また、全ての画素について処理が完了していない場合に、符号化プログラム５は、Ｓ１００の処理に戻って、次の画素について処理を行う。
【００４３】
以上説明したように、本実施形態における符号化装置２は、複数のハッシュテーブル（複数の履歴テーブル）を切り替えて使いまわすため、古いデータであるか否かをわざわざ判断することなく、参照可能範囲を超えたデータを削除することができる。
【００４４】
［変形例］
次に、第１の実施形態の変形例を説明する。
上記実施形態では、符号化装置２は、新ハッシュテーブル及び新履歴テーブルを参照可能として、これらのテーブルにおいてもハッシュ値が一致する画素の探索を行ったが、これらの新ハッシュテーブル及び新履歴テーブルに対してはエントリの追加又は更新のみを行うようにしてもよい。これにより、符号化処理が簡略化される。
図６は、新ハッシュテーブル及び新履歴テーブルに対して書込みのみが許可される形態の符号化処理のフローチャートである。なお、本図における各処理のうち、図５に示された処理と実質的に同一のものには同一の符号が付されている。
図６に示すように、本変形例における符号化プログラム５は、Ｓ１１５において符号化対象画素についてのエントリ追加／更新がなされた後は、図５に示された新履歴テーブルの検索（Ｓ１２０）及び新履歴テーブルから発見された一致画素の一致判定（Ｓ１３０）などを行うことなく、旧ハッシュテーブルの検索処理（Ｓ１４０）に移行する。
また、Ｓ１７０において、テーブル切換部５２４は、現時点で新ハッシュテーブルであるものを旧ハッシュテーブルに切り替えて、現時点で新履歴テーブルであるものを旧履歴テーブルに切り替えて、これらのテーブルを参照のみが許可される状態にし、現時点で旧ハッシュテーブルであるものを新ハッシュテーブルに切り替えて、現時点で旧履歴テーブルであるものを新履歴テーブルに切り替えて、これらのテーブルを書込みが許可されて、参照が禁止される状態にする。
このように、本変形例における符号化装置２は、新ハッシュテーブル及び新履歴テーブルに対する参照処理を禁止して、これらのテーブルに対しては新エントリの追加のみを行うことにより、符号化処理を簡略化することができる。
【００４５】
また、上記実施形態では、ハッシュテーブル及び履歴テーブルがそれぞれ２つずつ設けられた形態を具体例として説明したが、ハッシュテーブル及び履歴テーブルは、それぞれ複数存在してもよい。
また、符号化装置２は、上記ハッシュテーブルの代わりに、実際の画素値と出現位置とを対応付けたエントリを部分画像毎に記憶するテーブルを設けてもよい。
【００４６】
［第２の実施形態］
次に、第２の実施形態を説明する。
図７は、第２の実施形態における符号化処理（予測符号化処理）を説明する図であり、図７（Ａ）は、予測符号化処理において参照される画素の位置を例示し、図７（Ｂ）は、それぞれの参照位置の画素が符号化対象画素と一致した場合に生成される符号を例示し、図７（Ｃ）は、本実施形態における符号化装置２により生成される符号データを例示する。
【００４７】
図７（Ａ）に例示するように、本実施形態における符号化装置２は、固定的に設定された複数の参照位置Ａ〜Ｄの画素値と、動的に設定される参照位置Ｚの画素値とに基づいて、符号化対象画素Ｘの画素値を予測し、この予測情報を符号化する。
これらの参照位置Ａ〜Ｄ及び参照位置Ｚは、符号化対象画素Ｘに対する相対位置として規定されており、符号化装置２が注目画素Ｘの位置を主走査方向又は副走査方向に移動させると、参照位置Ａ〜Ｄ及び参照位置Ｚもこれに応じて移動する。
【００４８】
予測情報の符号化処理についてより具体的に説明すると、図１（Ｂ）に例示するように、本実施形態における符号化装置２は、参照位置Ａ〜Ｄ及び参照位置Ｚを符号に対応付ける符号テーブルを有する。この符号テーブルに含まれる符号は、それぞれの参照位置の画素値と注目画素Ｘの画素値とが一致する確率に応じて設定されており、ＭＲＵ（Most Recently Used）アルゴリズムなどにより動的に更新されてもよい。
符号化装置２は、参照位置Ａ〜Ｄ及び参照位置Ｚの画素値（以下、予測値）と、符号化対象画素Ｘの画素値とを比較し、いずれかの予測値が符号化対象画素Ｘの画素値と一致（ヒット）している場合に、この符号テーブルを参照してその参照位置に対応する符号を出力し、いずれの予測値も注目画素Ｘの画素値と一致しない場合に、既定の予測値（本例では、参照位置Ａの画素値）と符号化対象画素Ｘの画素値との差分を誤差値として符号化する。
【００４９】
その際に、符号化装置２は、同一の参照位置の画素値（予測値）が連続して注目画素Ｘの画素値と一致（ヒット）する場合には、図１（Ｃ）に例示するように、その連続数をラン数として符号化することにより、さらに画像データの圧縮率を高める。
このように、本実施形態において符号化装置２により参照される範囲は、符号化対象画素Ｘが存在する画素ライン、及び、その直前の画素ラインであり、第１の実施形態で例示したＬＺ７７符号化処理における参照範囲よりも狭い。
【００５０】
このように、符号化処理における参照範囲がそれ程広くない場合、又は、それぞれの部分画像（すなわち、それぞれのハッシュテーブルのエントリに対応する画素数）が小さい場合などでは、実際に既出の画素を参照して一致／不一致の判定処理を行ったとしても、それほど処理負荷が重くならない。
そこで、第２の実施形態における符号化装置２は、ハッシュテーブルにハッシュ値が以前に出現したか否かを書き込み、符号化対象画素の画素値に基づいて算出されたハッシュ値と、ハッシュテーブルに登録されているハッシュ値とを比較して、ハッシュ値が一致する既出の画素が存在する場合にのみ、実際の画素値の一致判定処理を行って、画素値が一致する参照位置を探索する。これにより、符号化装置２は、具体的な出現位置をハッシュテーブルに書き込む必要がないため、ハッシュテーブルのデータサイズを小さくすることができる。なお、本実施形態における符号化装置２のハードウェア構成は、図２に示されたものと実質的に同一である。
【００５１】
［第２の符号化プログラム６］
図８は、制御装置２１（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム６の機能構成を例示する図である。なお、本図における各構成のうち、図３に例示された構成と実質的に同一のものには同一の符号が付されている。
【００５２】
図８に例示するように、符号化プログラム６は、画像データ取得部５００、ハッシュ算出部６１０、書込み部６２０、データ記憶部６３０、相関判定部６４０及び符号化部６６０を有する。また、書込み部６２０は、エントリ更新部６２２を含み、データ記憶部６３０は、ハッシュテーブル６３２及び画素値ウインドウ５３６を含む。
【００５３】
符号化プログラム６において、ハッシュ算出部６１０は、画像データ取得部５００から入力された各画素の画素値及びその出現位置に基づいて、ハッシュ値を算出し、書込み部６２０に対して出力する。具体的には、ハッシュ算出部６１０は、画素値を示すビット列の一部と、出現位置のＸ座標（主走査方向の位置情報）を示すビット列の上位ビットとを用いて、ハッシュ値を算出する。なお、本実施形態では、画素のＸ座標（主走査方向の位置）が１３ビットのビット列で連続的に表現されている場合を具体例として説明する。
【００５４】
書込み部６２０は、エントリ更新部６２２を含む。なお、本実施形態では、ハッシュテーブルが１つだけ設けられた形態を具体例として説明するため、テーブル切換部５２４が設けられていない。
エントリ更新部６２２は、ハッシュ算出部５１０から入力されたハッシュ値（符号化対象画素について算出されたもの）をハッシュテーブル６３２に書き込む。なお、本実施形態におけるハッシュ値は出現位置と対応しているため、参照範囲外の画素について算出されたハッシュ値がハッシュテーブル６３２内に存在しても、ハッシュ値が一致する可能性が低い。したがって、エントリ更新部５２２は、古い画素について算出されたハッシュ値がハッシュテーブル６３２に存在する場合に、参照範囲内の画素に関するハッシュ値であるか否かをわざわざ判定して、古いハッシュ値を削除する必要がない。
【００５５】
データ記憶部６３０は、ハッシュテーブル６３２及び画素値ウインドウ５３９を含む。
ハッシュテーブル６３２は、参照範囲の画素について算出されるハッシュ値を十分に記憶できるだけの記憶領域を有し、それぞれの画素について算出されたハッシュ値と、そのハッシュ値が出現したか否かを示す有無情報とを互いに対応付けて記憶する。例えば、ハッシュテーブル６３２は、ハッシュ値のエントリ数が参照可能範囲の画素数よりも多くなった状態で新たなハッシュ値が入力されると、最も古いハッシュ値を削除して、この新たなハッシュ値を記憶する。
なお、本実施形態における画素値ウインドウ５３９は、少なくとも画素ライン２つ分の画素値を記憶していればよい。
【００５６】
相関判定部６４０は、書込み部６２０から入力されたハッシュ値と、ハッシュテーブル６３２に記憶されているハッシュ値とを比較して、ハッシュ値が一致する既出画素が存在する場合にのみ、符号化対象画素と既出画素との相関関係を判定し、判定結果を相関情報として符号化部６６０に対して出力する。本例の相関判定部６４０は、ハッシュ値が一致する既出画素が存在する場合に、複数の参照位置の画素値に基づいてそれぞれ予測値を生成し、これらの予測値と符号化対象画素の画素値との一致情報（予測情報）を符号化部６６０に対して出力する。
符号化部６６０は、相関判定部６５０から入力される予測情報を符号化し、符号データとして通信装置２２又は記録装置２４に対して出力する。
【００５７】
図９は、ハッシュテーブル６３２に記憶されるデータを例示する図である。
図９に例示するように、ハッシュテーブル６３２は、ハッシュ算出部６１０により画素値と出現位置（Ｘ座標）とに基づいて既定の手順で生成されたハッシュ値と、このハッシュ値の画素が出現したか否かを示す有無データ（「Ｙ」又は「Ｎ」）とを互いに対応付けて記憶する。本例の有無データは、「Ｙ」又は「Ｎ」を示すビットが８つパッキングされたものである。
また、ハッシュ算出部６１０により算出されるハッシュ値は、各画素のＲ、Ｇ、Ｂの値（ビット列）の部分ビット列の排他的論理和と、それぞれの画素の出現位置のＸ座標（ビット列）の上位８ビット（第５ビットから最上位ビットである第１２ビットまで）とが合成されたものである。このハッシュ値の最後の３ビットは、有無データ（８ビット）におけるビット位置を指定する情報である。
【００５８】
このように、ハッシュ算出部６１０は、画素のＸ座標の上位ビットでハッシュ値の上位ビットを構成することにより、符号化対象画素が主走査方向に移動してもハッシュ値が大きく変動することがなくなる。これにより、符号化装置２は、キャッシュを有効に活用することができる。特に、本例のハッシュ算出部６１０は、画素のＸ座標を表すビット列の上位８ビットと画素値とを用いてハッシュ値を算出するため、画素値が一致又は近似する限りにおいて、前後３２画素（第０ビットから第４ビットまでの下位５ビットに対応する範囲）のハッシュ値が一致する。これにより、符号化装置２は、符号化対象画素の近傍（主走査方向に前後３２画素の範囲）にある既出画素について、画素値が一致又は近似する画素の有無を判定することができる。
また、ハッシュ値は、ある範囲（例えば１４〜１５ビット程度）に収めないとメモリ効率が落ちる。これに対して、ハッシュ値算出の引数となるべき画像データは、Ｘ座標（１３ビット程度）に色情報２４ビットがあるので、どこかを削らなければならない。そこで、本例のハッシュ算出部６１０は、色情報の各データをずらして排他的論理和をとり、この排他的論理和と、画素の位置情報（Ｘ座標）とでハッシュ値を構成する。これは、画素のＸ座標は、まんべんなく出現するのでそのままハッシュ値の一部とすることにより、ハッシュの使用効率がよくなる（ハッシュの衝突が発生しにくい）。
また、画像は高い自己相関性（近接する画素同士で近似する性質）を有するため、画素値の上位ビットを用いてハッシュ値を算出すると、ハッシュの衝突が発生しやすい。そこで、ハッシュ算出部６１０は、画素値（色情報）を示すビット列同士について排他的論理和をとる場合に、ハッシュが衝突しにくいように色情報の下位ビットを優先的に適用することが望ましい。
【００５９】
図１０は、相関判定部６５０をより詳細に説明する機能構成図である。
図１０に例示するように、相関判定部６５０は、有無判定部６４２、画素探索部６４４、参照位置判定部６４６、予測誤差算出部６４８、ラン計数部６５０及び選択部６５２を含む。
相関判定部６５０において、有無判定部６４２は、書込み部６２０から入力されたハッシュ値（符号化対象画素について算出されたハッシュ値）と、ハッシュテーブル６３２に記憶されているハッシュ値とを比較して、ハッシュ値が一致する既出の画素が存在するか否かを判定する。
画素探索部６４４は、有無判定部６４２によりハッシュ値が一致する既出画素が存在すると判断された場合に、画素値ウインドウ５３９により管理されている画素値の中から、符号化対象画素と画素値が一致する画素を探索する。
【００６０】
参照位置判定部６４６は、画素探索部６４４により発見された既出画素が、参照位置Ａ〜Ｄ又は参照位置Ｚのいずれに相当するかを判定し、その参照位置の識別情報（参照位置ＩＤ）をラン計数部６５０に対して出力する。
予測誤差算出部６４８は、予め定められた予測方法で符号化対象画素の画素値を予測し、その予測値を符号化対象画素の画素値から減算し、予測誤差値としてラン計数部５３６に対して出力する。予測誤差算出部６４８の予測方法は、符号データを復号化する復号化装置の予測方法と対応していればよい。本例では、予測誤差算出部６４８は、参照位置Ａの画素値を予測値として、予測値と符号化対象画素Ｘの画素値との差分を算出する。
【００６１】
ラン計数部６５０は、同一の参照位置ＩＤが連続する数をカウントし、参照位置ＩＤ及び連続数を選択部６５２に対して出力する。また、ラン計数部６５０は、予測誤差値が入力され場合に、この予測誤差値をそのまま選択部６５２に対して出力する。
【００６２】
選択部６５２は、ラン計数部６５０から入力された参照位置ＩＤ、連続数及び予測誤差値に基づいて、最も長く連続した予測部ＩＤを選択し、この予測部ＩＤ及びその連続数を予測情報として符号化部６６０に対して出力する。
例えば、選択部６５２は、いずれかの参照位置ＩＤが入力された場合には、この参照位置ＩＤに対応する内部カウンタを１だけ増やし、予測誤差値が入力された場合で、かつ、内部カウンタが０でない場合には、それぞれの内部カウンタの値から最大値を選択し、この内部カウンタに対応する参照位置ＩＤと対応付けて符号化部６６０に対して出力し、その後に入力された予測誤差値を出力する。
符号化部６６０は、選択部６５２から入力された予測情報（予測部ＩＤ、連続数又は予測誤差値）を符号化する。
【００６３】
［全体動作］
次に、第２の実施形態における符号化装置２の動作を説明する。
図１１は、符号化プログラム６の動作（Ｓ２０）を示すフローチャートである。
図１１に示すように、ステップ２００（Ｓ２００）において、画像データ取得部５００が画像データを取得すると、符号化プログラム６は、注目画素位置の初期設定及びハッシュテーブ６３２の初期化などを行う。
また、画像データ取得部５００は、ラスタデータ（各画素の画素値及び出現座標）を１画素ずつハッシュ算出部６１０に対して出力する。
【００６４】
ステップ２０５（Ｓ２０５）において、ハッシュ算出部６１０は、画像データ取得部５００から入力された画素値及び出現位置に基づいて、ハッシュ値を算出し、算出されたハッシュ値と、入力された画素値及び出現座標とを書込み部６２０に対して出力する。
【００６５】
ステップ２１０（Ｓ２１０）において、エントリ更新部６２２は、ハッシュテーブル６３２において、ハッシュ算出部６１０から入力されたハッシュ値と一致するエントリを検索する。
ステップ２１５（Ｓ２１５）において、エントリ更新部６２２は、ハッシュ値が一致するエントリが発見された場合に、このエントリの有無データを更新する。具体的には、エントリ更新部６２２は、有無データのビット列においてハッシュ値の最後の３ビットに対応するビットを「Ｎ」から「Ｙ」に変換する。
また、エントリ更新部６２２は、ハッシュ値が一致するエントリが発見されない場合に、入力されたハッシュ値及び有無データからなるエントリをハッシュテーブル６３２に追加する。
また、書込み部６２０は、入力された画素値及び出現座標を画素値ウインドウ５３９に書き込んで、ウインドウの範囲を更新すると共に、入力されたハッシュ値、画素値及び出現座標を相関判定部６４０に対して出力する。
【００６６】
ステップ２２０（Ｓ２２０）において、相関判定部６４０の有無判定部６４２は、符号化対象画素について算出されたハッシュ値と一致する画素が存在するか否かを判定する。本例では、有無判定部６４２は、エントリ更新部６２２がＳ２１０において行った検索結果に基づいて、ハッシュ値が一致するエントリの有無を判定する。
符号化プログラム６は、有無判定部６４２によりハッシュ値が一致するエントリがハッシュテーブル６３２に存在すると判定された場合に、Ｓ２２５の処理に移行し、有無判定部６４２により存在しないと判定された場合に、Ｓ２４０の処理に移行する。
【００６７】
ステップ２２５（Ｓ２２５）において、画素探索部６４４は、画素値ウインドウ５３９に管理されている画素値を参照して、符号化対象画素の画素値と一致する既出画素を探索する。
ステップ２３０（Ｓ２３０）において、符号化プログラム６は、符号化対象画素と画素値が一致する既出画素が画素値ウインドウ５３９から発見できた場合に、Ｓ２３５の処理に移行し、画素値が一致する既出画素が発見できない場合に、Ｓ２４０の処理に移行する。
【００６８】
ステップ２３５（Ｓ２３５）において、参照位置判定部６４６は、画素探索部６４４により符号化対象画素と画素値が一致すると判定された既出画素の位置に応じて、参照位置ＩＤを生成し、ラン計数部６５０に対して出力する。
ラン計数部６５０は、入力された参照位置ＩＤに対応する内部カウンタをインクリメントする。
【００６９】
ステップ２４０（Ｓ２４０）において、予測誤差算出部６４８は、符号化対象画素の画素値と、参照位置Ａの画素値との差分値を算出し、算出された差分値を予測誤差値としてラン計数部６５０に対して出力する。
ラン計数部６５０は、予測誤差値が入力されると、それぞれの参照位置ＩＤとこれに対応する内部カウンタの値（連続数）とを選択部６５２に対して出力する。次いで、ラン計数部６５０は、入力された予測誤差値を選択部６５２に対して出力する。
選択部６５２は、入力された参照位置ＩＤ、連続数、及び、予測誤差値を符号化部６６０に対して出力する。
【００７０】
ステップ２４５（Ｓ２４５）において、符号化プログラム６は、画像データの全画素について処理が終了したか否かを判定し、未処理の画素が存在する場合に、Ｓ２００の処理に戻って、次の画素に対する処理を行い、これ以外の場合に、Ｓ２４５の処理に移行する。
ステップ２５０（Ｓ２５０）において、符号化部６６０は、選択部６５２から入力された予測情報（参照位置ＩＤ、連続数及び予測誤差値）を符号化し、符号データとして出力する。
【００７１】
以上説明したように、第２の実施形態における符号化装置２は、ハッシュテーブルにハッシュ値が一致する画素の有無を示す情報を記憶し、ハッシュ値が一致する画素の有無に応じて、符号化対象画素の画素値と既出画素の画素値とが一致するか否かを判定する一致判定処理を行う。これにより、符号化装置２は、一致判定処理の実行回数を抑えて、符号化処理における処理負荷の低減及び処理時間の短縮を実現する。
【００７２】
［変形例］
次に、第２の実施形態における第１の変形例を説明する。
上記実施形態では、画素のＸ座標が１３ビットのビット列で表現されている場合を具体例として説明している。この場合に、ハッシュ算出部６１０は、画素のＸ座標を表すビット列の上位８ビットと画素値とを用いてハッシュ値を算出するため、画素値が一致又は近似する限りにおいて、前後３２画素（下位５ビットに対応する範囲）のハッシュ値が一致する。以下、このようにハッシュ値が一致する画素群（３２画素）をセグメントと呼ぶ。
このように、符号化装置２は、同一セグメントにおいてハッシュ値が一致することにより、符号化対象画素の近傍領域（前後３２画素）から画素値が一致又は近似する既出画素の有無を判定することができる。しかしながら、このセグメントの境界部分では、たとえ画素値が一致している場合であっても異なるハッシュ値が算出され、セグメント境界部分にある画素が一致又は近似していても有無判定の対象から除外されることになる。
そこで、本変形例における符号化装置２は、符号化対象画素がセグメントの境界部分にある場合には、ハッシュ値が一致するセグメントだけでなく、その隣のセグメントも加味して、画素値が一致又は近似する既出画素が存在するか否かを判定する。
【００７３】
図１２は、隣接セグメントの参照方法を説明する図である。
図１２に例示するように、本例のハッシュ値は、画素の位置情報（上位８ビット）と画素値とに基づいて算出されている。そして、このハッシュ値の下位３ビットは、画素の位置情報の一部（第５ビットから第７ビットまで）で構成され、位置情報の上位５ビット（この下位３ビットを除いたもの）と画素値とが一致するハッシュ値は、同一の有無データに対応付けられている。すなわち、互いに近接する８セグメント分のハッシュ値が同一の有無データに対応付けられている。
したがって、符号化装置２は、有無データの隣のビットを参照することにより、隣のセグメントに符号化対象画素のハッシュ値が一致する画素が存在するか否かを判定することができる。
なお、符号化装置２は、隣接セグメントのハッシュ値から画素値に由来するビット列を抽出し、抽出されたビット列と、符号化対象画素のハッシュ値における当該部分とを比較することにより、ハッシュ値が一致する画素が隣接セグメントに存在するか否かを判定してもよい。
【００７４】
また、第２の変形例としては、上記第１の実施形態と第２の実施形態とを組み合わせてもよい。すなわち、本変形例の符号化装置２は、第１ハッシュテーブル６３２及び第２ハッシュテーブル６３４を有し、これらのハッシュテーブルを使いまわすことにより、ハッシュテーブルに登録されるエントリの削除を容易にする。
【００７５】
図１３は、２つのハッシュテーブルに記憶されるデータを例示する図である。
図１３に例示するように、本変形例における書込み部６２０は、画素ライン（部分画像）毎にエントリ（ハッシュ値及び有無データ）を追加するハッシュテーブル（第１ハッシュテーブル６３２又は第２ハッシュテーブル６３４）を切り替える。
このように、本変形例の符号化装置２は、部分画像毎に複数のハッシュテーブルを有し、これらのハッシュテーブルを部分画像毎にリセットする。
【００７６】
［実験結果］
図１４は、符号化装置２による一致判定処理の回数を示すグラフである。
図１４において、グラフＡ〜グラフＣは、第２の実施形態における符号化装置２の一致判定処理回数を示し、グラフＤは、ハッシュ値を用いずに直接それぞれの参照位置の画素値と符号化対象画素の画素値とを比較して一致判定処理を行う場合の処理回数を示す。また、「ｅｈ＝０」は、符号化対象画素とハッシュ値が一致するセグメントのみを一致判定の対象とした場合の一致判定処理回数を示し、「ｅｈ＝１」は、片方の隣接セグメントを一致判定対象に加えた場合の一致判定処理回数を示し、「ｅｈ＝２」は、両方の隣接セグメントを一致判定の対象とした場合の一致判定処理回数を示す。
第２の実施形態における符号化装置２は、それぞれの参照位置の画素を比較する場合に、５箇所の参照位置について、画素値読出し処理及び画素値の比較処理などで構成されるループを繰り返す必要がある。なお、ランが途切れた参照位置については、他の参照位置でランが続く限りにおいて、画素値の比較処理を省略することができるが、例えば、写真画像等が入力された場合に、同一の画素値が連続する可能性が低いため、ほとんど画素毎に５回のループを通ることになり、処理速度が極端に低下する。
これに対して、第２の実施形態における符号化装置２は、図１１に示したＳ２０５からＳ２２０までの処理がオーバーヘッドとなるが、写真画像などの自然画像が入力された場合には、Ｓ２２０の後で直接Ｓ２４０の処理に移行するフローが多くなり、Ｓ２２５からＳ２３５までの処理を行わずにすむ。したがって、第２の実施形態における符号化装置２は、ハッシュ処理のオーバーヘッドとトレードオフがあるものの、符号化処理の高速化が図れる。
【図面の簡単な説明】
【００７７】
【図１】ハッシュ関数を用いて高速化したＬＺ７７符号化方式を説明する図であり、（Ａ）は、符号化処理における参照可能範囲であるウインドウを例示し、（Ｂ）は、符号化装置に記憶されるハッシュテーブルを例示し、（Ｃ）は、符号化装置に記憶される履歴テーブルを例示する。
【図２】本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
【図３】制御装置２１（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
【図４】データ記憶部５３０により記憶されるデータを例示する図であり、（Ａ）は、第１ハッシュテーブル５３２又は第２ハッシュテーブル５３４を例示し、（Ｂ）は、第１履歴テーブル５３６及び第２履歴テーブル５３８を例示する。
【図５】符号化プログラム５の動作（Ｓ１０）を示すフローチャートである。
【図６】新ハッシュテーブル及び新履歴テーブルに対して書込みのみが許可される形態の符号化処理のフローチャートである。
【図７】第２の実施形態における符号化処理（予測符号化処理）を説明する図であり、（Ａ）は、予測符号化処理において参照される画素の位置を例示し、（Ｂ）は、それぞれの参照位置の画素が符号化対象画素と一致した場合に生成される符号を例示し、（Ｃ）は、本実施形態における符号化装置２により生成される符号データを例示する。
【図８】制御装置２１（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム６の機能構成を例示する図である。
【図９】ハッシュテーブル６３２に記憶されるデータを例示する図である。
【図１０】相関判定部６５０をより詳細に説明する機能構成図である。
【図１１】符号化プログラム６の動作（Ｓ２０）を示すフローチャートである。
【図１２】隣接セグメントの参照方法を説明する図である。
【図１３】２つのハッシュテーブルに記憶されるデータを例示する図である。
【図１４】符号化装置２による一致判定処理の回数を示すグラフである。
【符号の説明】
【００７８】
２・・・符号化装置
５，６・・・符号化プログラム
５００・・・画像データ取得部
５１０，６１０・・・ハッシュ算出部部
５２０，６２０・・・書込み部
５２２，６２２・・・エントリ更新部
５２４・・・テーブル切換部
５３０，６３０・・・データ記憶部
５３２・・・第１ハッシュテーブル
５３４・・・第２ハッシュテーブル
６３２・・・ハッシュテーブル
５３６・・・第１履歴テーブル
５３８・・・第２履歴テーブル
５３９・・・画素値ウインドウ
５４０，６４０・・・相関判定部
５４２・・・一致判定部
５４４・・・最長列判定部
６４２・・・有無判定部
６４４・・・画素探索部
６４６・・・参照位置判定部
６４８・・・予測誤差算出部
６５０・・・ラン計数部
６５２・・・選択部
５６０・・・符号化部
【図１】
2005159820.tif 000003
【図２】
2005159820.tif 000004
【図３】
2005159820.tif 000005
【図４】
2005159820.tif 000006
【図５】
2005159820.tif 000007
【図６】
2005159820.tif 000008
【図７】
2005159820.tif 000009
【図８】
2005159820.tif 000010
【図９】
2005159820.tif 000011
【図１０】
2005159820.tif 000012
【図１１】
2005159820.tif 000013
【図１２】
2005159820.tif 000014
【図１３】
2005159820.tif 000015
【図１４】
2005159820.tif 000016