(57)【要約】  【課題】  画像の相関特性に基づいて画像データを高い圧縮率で符号化する符号化装置を提供する。  【解決手段】  符号化装置２は、画素値のハッシュ値を算出し、算出されたハッシュ値に基づいて同一のハッシュ値が現れる画素間隔を算出し、それぞれの画素間隔が算出される回数（出現回数）に基づいて画像データの周期特性を判定する。そして、符号化装置２は、判定された周期特性に基づいて画素値の参照位置（第５予測部の参照位置）を選択し、画像データを符号化する。【選択図】図７
2005151278.tif 000002
【特許請求の範囲】
【請求項１】
画像データのハッシュ値を算出するハッシュ算出手段と、
前記ハッシュ算出手段により算出されたハッシュ値に基づいて、画像データの周期的な相関特性を判定する周期判定手段と、
前記周期判定手段により判定された周期的な相関特性に基づいて、画像データを符号化する符号化手段と
を有する符号化装置。
【請求項２】
前記ハッシュ算出手段は、前記画像データのハッシュ値として、画素値のハッシュ値を算出し、
前記周期判定手段は、前記相関特性として、同一のハッシュ値を有する画素の間隔を判定し、
前記符号化手段は、前記周期判定手段により判定された画素間隔に応じて、画素値の参照位置を決定する
請求項１に記載の符号化装置。
【請求項３】
前記画像データは、画素の配列を二進数で表現した位置情報と、それぞれの画素の画素値とを含み、
前記周期判定手段は、同一のハッシュ値を有する画素の位置情報に含まれる下位ビットに基づいて、画像データの周期的な相関特性を判定する
請求項１又は２に記載の符号化装置。
【請求項４】
画素値のハッシュ値を算出するハッシュ算出手段と、
前記ハッシュ算出手段により算出されたハッシュ値に基づいて、同一のハッシュ値が現れる画素間隔を算出する間隔計数手段と、
前記間隔計数手段により算出される画素間隔の出現回数をカウントするカウンタと、
前記カウンタによりカウントされる画素間隔の出現回数と、画素値の変化状況とに基づいて、同一のハッシュ値が出現する周期を抽出する周期抽出手段と、
前記周期抽出手段により抽出された周期に応じて、画素値の参照位置を決定して符号化処理を行う符号化手段と
を有する符号化装置。
【請求項５】
画像データのハッシュ値を用いて、画像データの周期特性を判定し、
判定された周期特性に基づいて、画像データを符号化する
符号化方法。
【請求項６】
コンピュータを含む符号化装置において、
画像データのハッシュ値を用いて、画像データの周期特性を判定するステップと、
判定された周期特性に基づいて、画像データを符号化するステップと
を前記符号化装置のコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の相関特性に基づいて画像データを符号化する符号化装置に関する。
【背景技術】
【０００２】
データの自己相関関係に着目して符号化する方法としては、例えば、ＬＺ符号化（Ziv-Lempel符号化）などがある。特に、画像データの場合には、近傍の画素同士が高い相関関係を有するので、この点に着目して画像データを高い圧縮率で符号化することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
本発明は、上述した背景からなされたものであり、画像の相関特性に基づいて画像データを高い圧縮率で符号化する符号化装置を提供することを目的とする。
【課題を解決するための手段】
【０００４】
［符号化装置］
上記目的を達成するために、本発明にかかる符号化装置は、画像データのハッシュ値を算出するハッシュ算出手段と、前記ハッシュ算出手段により算出されたハッシュ値に基づいて、画像データの周期的な相関特性を判定する周期判定手段と、前記周期判定手段により判定された周期的な相関特性に基づいて、画像データを符号化する符号化手段とを有する。
【０００５】
好適には、前記ハッシュ算出手段は、画素値のハッシュ値を算出し、前記周期判定手段は、符号化対象画素としてスキャンする方向に配列された画素群について、同一のハッシュ値を有する画素の間隔を判定し、前記符号化手段は、前記周期判定手段により判定された画素間隔に応じて、画素値の参照位置を決定する。
【０００６】
好適には、前記画像データは、画素の配列を二進数で表現した位置情報と、それぞれの画素の画素値とを含み、前記周期判定手段は、同一のハッシュ値を有する画素の位置情報に含まれる下位ビットに基づいて、画像データの周期的な相関特性を判定する。
【０００７】
また、本発明にかかる符号化装置は、画素値のハッシュ値を算出するハッシュ算出手段と、前記ハッシュ算出手段により算出されたハッシュ値に基づいて、同一のハッシュ値が現れる画素間隔を算出する間隔計数手段と、前記間隔計数手段により算出される画素間隔の出現回数をカウントするカウンタと、前記カウンタによりカウントされる画素間隔の出現回数と、画素値の変化状況とに基づいて、同一のハッシュ値が出現する周期を抽出する周期抽出手段と、前記周期抽出手段により抽出された周期に応じて、画素値の参照位置を決定して符号化処理を行う符号化手段とを有する。
【０００８】
［符号化方法］
また、本発明にかかる符号化方法は、画像データのハッシュ値を用いて、画像データの周期特性を判定し、判定された周期特性に基づいて、画像データを符号化する。
【０００９】
［プログラム］
また、本発明にかかるプログラムは、コンピュータを含む符号化装置において、画像データのハッシュ値を用いて、画像データの周期特性を判定するステップと、判定された周期特性に基づいて、画像データを符号化するステップとを前記符号化装置のコンピュータに実行させる。
【発明の効果】
【００１０】
本発明の符号化装置によれば、画像の相関特性に基づいて画像データを高い圧縮率で符号化することができる。
【発明を実施するための最良の形態】
【００１１】
［背景と概略］
まず、本発明の理解を助けるために、その背景及び概略を説明する。
画像データには自己相関性が含まれており、この自己相関性を利用することにより高い圧縮率での符号化が可能になる。例えば、画像データにスクリーン処理が施された場合に、中間調の色で一様に塗潰された領域であってもスクリーンパターンが周期的に現れる。このような場合に、ランレングス圧縮を適用しても同一画素値の連続数がそれ程多くないので高い圧縮率を実現することができない。そこで、本実施形態における符号化装置２は、画像データの周期的な相関特性に基づいて、画像データを符号化する。
【００１２】
図１は、本実施形態における符号化方法の概略を説明する図であり、図１（Ａ）は、周期的な相関特性に基づいて設定される画素の参照位置を例示し、図１（Ｂ）は、それぞれの参照位置と符号とを対応付ける符号テーブルを例示し、図１（Ｃ）は、本符号化方法により生成された符号データを例示する。
図１（Ａ）に例示するように、本実施形態における符号化装置２は、固定的に設定された複数の参照位置Ａ〜Ｄの画素値と、画像の周期的な相関特性に応じて設定される参照位置Ｚの画素値とに基づいて、符号化対象である注目画素Ｘの画素値を予測し、この予測情報を符号化する。ここで、画像の相関特性とは、画像データに含まれる自己相関性であり、例えば、近接する画素同士で画素値が一致又は近似することが多いという画像の特性に起因する近接相関特性と、画像中に周期的に画素値が一致又は近似するという画像の特性に起因する周期的相関特性とが含まれる。本実施形態における参照位置Ｚは、この周期的相関特性に応じて、画素値が一致又は近似する確率が高くなるように決定される。
これらの参照位置Ａ〜Ｄ及び参照位置Ｚは、注目画素Ｘに対する相対位置として規定されており、符号化装置２が注目画素Ｘの位置をスキャン方向（本実施形態では画像のＸ軸方向）に移動させると、参照位置Ａ〜Ｄ及び参照位置Ｚもこれに応じて移動する。
【００１３】
予測情報の符号化処理についてより具体的に説明すると、図１（Ｂ）に例示するように、本実施形態における符号化装置２は、参照位置Ａ〜Ｄ及び参照位置Ｚを符号に対応付ける符号テーブルを有する。この符号テーブルに含まれる符号は、それぞれの参照位置の画素値と注目画素Ｘの画素値とが一致する確率に応じて設定されており、ＭＲＵ（Most Recently Used）アルゴリズムなどにより動的に更新されてもよい。
符号化装置２は、参照位置Ａ〜Ｄ及び参照位置Ｚの画素値（以下、予測値）と、注目画素Ｘの画素値とを比較し、いずれかの予測値が注目画素Ｘの画素値と一致（ヒット）している場合に、この符号テーブルを参照してその参照位置に対応する符号を出力し、いずれの予測値も注目画素Ｘの画素値と一致しない場合に、既定の予測値（本例では、参照位置Ａの画素値）と注目画素Ｘの画素値との差分を誤差値として符号化する。
【００１４】
その際に、符号化装置２は、同一の参照位置の画素値（予測値）が連続して注目画素Ｘの画素値と一致（ヒット）する場合には、図１（Ｃ）に例示するように、その連続数をラン数として符号化することにより、さらに画像データの圧縮率を高める。
このように、符号化装置２が画素値の予測情報を符号化する場合に、画像データの周期特性と予測処理の周期特性とが一致している方が、いずれかの参照位置による予測値が連続してヒットするため符号量を小さくすることができる。
そこで、本実施形態における符号化装置２は、画像データの周期的な相関特性を判定し、判定された周期的相関特性に応じて参照位置Ｚを設定することにより、画像データを高い圧縮率で符号化する。
【００１５】
［ハードウェア構成］
次に、符号化装置２のハードウェア構成を説明する。
図２は、本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
図２に例示するように、符号化装置２は、ＣＰＵ２１２及びメモリ２１４などを含む制御装置２１、通信装置２２、ＨＤＤ・ＣＤ装置などの記録装置２４、並びに、ＬＣＤ表示装置あるいはＣＲＴ表示装置およびキーボード・タッチパネルなどを含むユーザインターフェース装置（ＵＩ装置）２５から構成される。
符号化装置２は、例えば、本発明にかかる符号化プログラム５（後述）がプリンタドライバの一部としてインストールされた汎用コンピュータであり、通信装置２２又は記録装置２４などを介して画像データを取得し、取得された画像データを符号化してプリンタ装置３に送信する。
【００１６】
［符号化プログラム］
図３は、制御装置２１（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
図３に例示するように、符号化プログラム５は、画像データ取得部５００、周期性判定部５１０、予測符号化部５３０及び符号出力部５５０を有する。
符号化プログラム５において、画像データ取得部５００は、通信装置２２又は記録装置２４などを介して、ラスタライズされた画像データを取得し、周期性判定部５１０に対して出力する。
周期性判定部５１０は、画像データ取得部５００から入力された画像データに基づいて、画像に含まれる周期的な相関特性を判定し、判定された相関特性（具体的には、周期に相当する画素間隔）と画像データとを予測符号化部５３０に対して出力する。
予測符号化部５３０は、周期性判定部５１０から入力された相関特性（画素間隔）に応じて、参照位置Ｚを設定し、設定された参照位置Ｚの画素値と参照位置Ａ〜Ｄの画素値と基づいて注目画素Ｘの画素値を予測し、この予測値に基づく予測情報（ヒット数及び誤差値など）を符号化し、符号データとして符号出力部５５０に対して出力する。
符号出力部５５０は、予測符号化部５３０から入力された符号データを通信装置２２又は記録装置２４を介して出力する。
【００１７】
図４は、周期性判定部５１０をより詳細に説明する機能構成図である。
図４に例示するように、周期性判定部５１０は、ハッシュ算出部５１２、ハッシュテーブル生成部５１４、間隔計数部５１６及び間隔判定部５１８を含む。
周期性判定部５１０において、ハッシュ算出部５１２は、画像データ取得部５００から入力された画像データに基づいて、それぞれの画素の画素値を引数としてハッシュ値を算出し、算出されたハッシュ値をハッシュテーブル生成部５１４に対して出力する。
ハッシュテーブル生成部５１４は、ハッシュ算出部５１２から入力されたハッシュ値に基づいて、それぞれの画素の画素値について算出されたハッシュ値と、これらの画素の位置情報とを互いに対応付けるハッシュテーブルを生成する。
間隔計数部５１６は、ハッシュテーブル生成部５１４により生成されたハッシュテーブルを参照して、ハッシュ値が一致する画素の間隔をそれぞれの画素について算出し、算出された画素間隔を間隔判定部５１８に対して出力する。
間隔判定部５１８は、間隔計数部５１６から入力される画素間隔に基づいて、それぞれの同一のハッシュ値が現れる画素間隔を集計し、集計された画素間隔に基づいて画像データの周期的な相関特性を判定する。具体的には、間隔判定部５１８は、出現回数が多い画素間隔の中から、周期的な相関特性を示す画素間隔を選択し、選択された画素間隔を判定結果として予測符号化部５３０に対して出力する。また、間隔判定部５１８は、この判定結果と共に、入力された画像データを予測符号化部５３０に対して出力する。
【００１８】
図５は、周期性判定部５１０において生成されるデータを説明する図であり、図５（Ａ）は、ハッシュテーブル生成部５１４により生成されるハッシュテーブル７１４を例示し、図５（Ｂ）は、間隔判定部５１８により生成される画素間隔カウンタ７１８を例示する。
図５（Ａ）に例示するように、ハッシュテーブル生成部５１４は、それぞれの画素の画素値を引数として算出されたハッシュ値と、これらの画素の出現位置（本例では、Ｘ座標）とを互いに対応付けるハッシュテーブル７１４を生成する。本例の出現位置は、それぞれの画素のＸ座標（二進表現）の下位５ビット（すなわち、二進表現されたＸ座標から少なくとも１つの上位ビットを削除したもの）の値をフラグで表現したものである。このように、符号化装置２は、画素の位置を示すビット列の下位ビットを適用することにより、ハッシュテーブル７１４のデータサイズを小さく抑えると共に、算出される画素間隔を一定の範囲（本例では、５ビットに相当する３２画素が最大周期となる）に収めることができる。
また、本例の符号化装置２は、３２ビットのビット列（直近３２画素に対応）において出現位置に対応する位置でフラグ「１」をたてることにより、それぞれのハッシュ値を示す画素の出現位置を表現する。間隔計数部５１６は、それぞれのハッシュ値に対応して記憶されたフラグ（出現位置に対応）に基づいて、同一のハッシュ値を有する画素の画素間隔を算出する。
【００１９】
図５（Ｂ）に例示するように、間隔判定部５１８は、間隔計数部５１６により算出された画素間隔と、この画素間隔の出現回数とを互いに対応付けて画素間隔カウンタ７１８に格納する。すなわち、間隔判定部５１８は、算出された画素間隔が間隔計数部５１６から入力されると、画素間隔カウンタ７１８によりこの画素間隔に対応付けて格納されたカウント値を１つ増加させる。
間隔判定部５１８は、画素間隔カウンタ７１８に格納されたカウント値（すなわち、各画素間隔の出現回数）に基づいて、画像データの周期的な相関関係を判定する。
【００２０】
図６は、予測符号化部５３０をより詳細に説明する機能構成図である。
図６に例示するように、予測符号化部５３０は、複数の予測部５３２（第１予測部５３２ａ〜第５予測部５３２ｅ）、予測誤差算出部５３４、ラン計数部５３６、選択部５３８及び符号化部５４０を含む。
予測符号化部５３０において、第１予測部５３２ａ〜第５予測部５３２ｅは、互いに異なる参照位置（図１に例示した参照位置Ａ〜Ｄ及び参照位置Ｚ）の画素値を参照して、この画素値を予測値とし、この予測値と注目画素Ｘの画素値との比較結果をラン計数部５３６に対して出力する。本例の予測部５３２は、予測値と注目画素の画素値とが一致した場合（すなわち、予測が的中した場合）に、自己を識別する予測部ＩＤをラン計数部５３６に対して出力し、これ以外の場合に、一致しなかった旨をラン計数部５３６に対して出力する。
本例では、参照位置が固定的に設定された第１予測部５３２ａ〜第４予測部５３２ｄと、参照位置が周期的な相関特性に応じて設定される第５予測部５３２ｅとが、注目画素Ｘに対して既定位置にある参照画素の画素値を用いて、注目画素Ｘの予測値を生成し、この予測値と注目画素Ｘの画素値との比較結果を出力する。なお、予測部５３２は、１種類以上であればよく、例えば、第５予測部５３２ｅのみで構成されてもよい。
【００２１】
予測誤差算出部５３４は、予め定められた予測方法で注目画素Ｘの画素値を予測し、その予測値を注目画素Ｘの実際の画素値から減算し、予測誤差値としてラン計数部５３６に対して出力する。予測誤差算出部５３４の予測方法は、符号データを復号化する復号化装置の予測方法と対応していればよい。本例では、予測誤差算出部５３４は、第１予測部５３２ａと同じ予測方法で予測値（すなわち、同じ参照位置の画素値）を生成し、予測値と注目画素Ｘの画素値との差分を算出する。
【００２２】
ラン計数部５３６は、同一の予測部ＩＤが連続する数をカウントし、予測部ＩＤ及び連続数を選択部５３８に対して出力する。また、ラン計数部５３６は、予測誤差値が入力され場合に、この予測誤差値をそのまま選択部５３８に対して出力する。
【００２３】
選択部５３８は、ラン計数部５３６から入力された予測部ＩＤ、連続数及び予測誤差値に基づいて、最も長く連続した予測部ＩＤを選択し、この予測部ＩＤ及びその連続数を予測情報として符号化部５４０に対して出力する。
例えば、選択部５３８は、予測部ＩＤがいずれかの予測部５３２を指している場合には、この予測部ＩＤに対応する内部カウンタを１だけ増やし、予測誤差値が入力された場合で、かつ、内部カウンタが０でない場合には、それぞれの内部カウンタの値から最大値を選択し、この内部カウンタに対応する予測部ＩＤと対応付けて符号化部５４０に対して出力し、その後に入力された予測誤差値を出力する。
符号化部５４０は、選択部５３８から入力された予測情報（予測部ＩＤ、連続数又は予測誤差値）を符号化し、符号出力部５５０に対して出力する。
【００２４】
［全体動作］
次に、符号化装置２による符号化処理の全体動作を説明する。
図７は、符号化プログラム５の動作（Ｓ１０）を示すフローチャートである。
図７に示すように、ステップ１００（Ｓ１００）において、画像データ取得部５００が画像データを取得すると、符号化プログラム５は、注目画素位置の初期設定、各予測部位置の初期設定、ハッシュテーブル７１４の初期化、及び、画素間隔カウンタ７１８の初期化などを行う。また、画像データ取得部５００は、取得された画像データがラスタデータでない場合には、取得された画像データをラスタデータに変換する。
画像データ取得部５００は、ラスタデータを周期性判定部５１０に対して出力する。
【００２５】
ステップ１０５（Ｓ１０５）において、ハッシュ算出部５１２は、画像データ取得部５００から入力された画像データの画素値に基づいて、ハッシュ値を算出し、算出されたハッシュ値とこの画素の位置情報（Ｘ座標値）とをハッシュテーブル生成部５１４に対して出力する。
【００２６】
ステップ１１０（Ｓ１１０）において、ハッシュテーブル生成部５１４は、ハッシュ算出部５１２から入力されたハッシュ値と、位置情報とをハッシュテーブル７１４に登録する。なお、ハッシュテーブル７１４に登録される位置情報は、画素のＸ座標値（二進表現）の下位５ビットに相当する相対位置情報（すなわち、前後３２画素における位置）であり、同一のハッシュ値を有する画素が２以上存在する場合には、これらの画素の位置情報は、同一のエントリに重畳して登録される。
【００２７】
ステップ１２０（Ｓ１２０）において、周期性判定部５１０は、３２画素分についてＳ１０５及びＳ１１０の処理が終了したか否かを判定する。符号化プログラム５は、３２画素分の処理が終了した場合に、Ｓ１２５の処理に移行し、これ以外の場合に、Ｓ１０５の処理に戻り、次の画素についてＳ１０５及びＳ１１０の処理を行う。
【００２８】
ステップ１２５（Ｓ１２５）において、ハッシュ算出部５１２は、次に３２画素についてハッシュ値を算出し、算出されたハッシュ値とその画素の位置情報とを間隔計数部５１６及びハッシュテーブル生成部５１４に対して出力する。
【００２９】
ステップ１３０（Ｓ１３０）において、間隔計数部５１６は、ハッシュテーブル７１４を参照して、ハッシュ算出部５１２により算出されたハッシュ値と同一のハッシュ値の位置情報を抽出する。間隔計数部５１６は、ハッシュ算出部５１２から入力された位置情報と、ハッシュテーブル７１４から抽出された位置情報とを比較して、フラグの間隔（すなわち、同一のハッシュ値を有する画素同士の間隔）を算出し、間隔判定部５１８に対して出力する。
間隔判定部５１８は、間隔計数部５１６から入力された画素間隔に対応する画素間隔カウンタ７１８のカウント値を１つ増加させる。
なお、本ステップにおいて、説明の便宜上、比較処理を行う旨を記載しているが、実装上は、比較処理を用いずに本ステップを実現することができる。
【００３０】
ステップ１４０（Ｓ１４０）において、ハッシュテーブル生成部５１４は、ハッシュ算出部５１２から入力されたハッシュ値及び位置情報に基づいて、ハッシュテーブル７１４を更新する。
ステップ１４５（Ｓ１４５）において、周期性判定部５１０は、３２画素についてＳ１２５〜Ｓ１４０の処理が終了したか否かを判定する。符号化プログラム５は、３２画素分の処理が終了した場合に、Ｓ１５０の処理に移行し、これ以外の場合に、Ｓ１２５の処理に戻る。
【００３１】
ステップ１５０（Ｓ１５０）において、周期性判定部５１０は、全ての画素についてＳ１０５〜Ｓ１４０の処理が終了したか否かを判定する。符号化プログラム５は、全ての画素について処理が終了した場合に、Ｓ１５５の処理に移行し、これ以外の場合に、Ｓ１００の処理に戻り、次の３２画素について処理を行う。
なお、本例では、画像に含まれる全ての画素に基づいて相関特性を判定する形態を説明するが、これに限定されるものではなく、スキャンライン毎又は画像領域毎に相関特性を判定してもよい。具体的には、周期性判定部５１０が、Ｓ１５０において、各スキャンライン又は各画像領域に含まれる全ての画素についてＳ１０５〜Ｓ１４０の処理が終了したか否かを判定する。
【００３２】
ステップ１５５（Ｓ１５５）において、間隔判定部５１８は、画素間隔カウンタ７１８の各画素間隔のカウント値を参照して、カウント値と画素間隔との相関関係を解析し、ハッシュ値が同一となる画素が出現しやすい画素間隔を判定し、判定された画素間隔（周期）の中から所定の画素間隔を選択し、画像データと共に予測符号化部５３０に対して出力する。
【００３３】
ステップ１６０（Ｓ１６０）において、予測符号化部５３０は、間隔判定部５１８から入力された画素間隔に応じて、第５予測部５３２ｅの参照位置Ｚを決定し、入力された画像データを符号化し、符号データを符号出力部５５０に対して出力する。
符号出力部５５０は、予測符号化部５３０から入力された符号データを、通信装置２２又は記録装置２４を介して外部（プリンタ装置３など）に出力する。
【００３４】
以上説明したように、本実施形態における符号化装置２は、ハッシュ値に基づいて画像の周期的な相関特性を判定し、判定された相関特性に基づいて画像データを符号化する。これにより、符号化装置２は、周期的な相関特性の判定を高速に行うことができるので、短い処理時間で高い圧縮率での符号化処理を実現する。
なお、本実施形態のように、ハッシュ値を用いて周期的な相関特性を判定する形態において、異なる画素値に基づいて同一のハッシュ値が算出される場合（ハッシュの衝突）がある。このような場合に、画素間隔のカウント値に誤差が含まれることになるが、ハッシュ値のビット数を調整することにより、ハッシュの衝突が発生する頻度を十分に低くすることができ、周期的な相関特性の判定に大きな影響を与えることはない。
【００３５】
［変形例］
次に、上記実施形態の変形例を説明する。
まず、変形例として、画素間の距離に対して負の相関を示す近接相関特性と、周期に依存する周期的相関特性とを分離する手段が備えられた符号化装置２を説明する。
図８は、相関特性と符号量との関係を示すグラフである。
図８において、折れ線グラフＡは、それぞれの画素間隔を横軸とし、これらの画素間隔におけるハッシュ値の一致度合いを縦軸として作成されたものである。また、棒グラフＢは、注目画素Ｘと参照位置Ｚとの間隔を横軸とし、これらの参照位置Ｚを用いて符号化した場合の符号量を縦軸として作成されたものである。
ハッシュ値の一致度合い（すなわち、相関特性）は、画素間隔が１の場合に最大であり、その後一定の周期（８画素）でピークが現れる。しかしながら、注目画素Ｘと参照位置Ｚとの間隔を１画素として符号化した場合の符号量は、注目画素Ｘと参照位置Ｚとの間隔を８画素として符号化した場合よりも大きい。すなわち、注目画素Ｘと参照画素Ｚとの間隔は、１画素よりも８画素であることが望ましい。
これは、ハッシュ値の一致度合いのみで計測された相関特性の中には、画素間の距離に依存した近接相関特性（すなわち、空間的に近い程、画素が近い値を取るという性質）と、周期的相関特性とが混在しているためである。すなわち、本例において、近接相関特性は、画像全体で現れる確率が高いためハッシュ値の一致度合いを高くしているが、周期的相関特性と比較して一致状態の連続数が小さいため、符号量が大きくなっている。
よって、本変形例における符号化装置２は、ハッシュ値の一致度合いに基づいて計測された相関特性の中から、周期的相関特性を抽出し、抽出された周期的相関特性に基づいて参照位置Ｚを決定する。
【００３６】
次に、周期的相関特性（周期間隔）を抽出する具体的な方法について説明する。本例での符号化装置２は、純粋な周期間隔を抽出するために、この周期間隔よりも１画素短い短周期と１画素長い長周期の挙動を解析する。すなわち、短周期及び長周期は、画素値のヒット率が低くなることが多いので、このヒット率の低下を検出することにより、本来の周期間隔を特定する。
【００３７】
図９は、長周期及び短周期の挙動を説明する図である。
図９に示すように、短周期における注目画素Ｘと参照画素Ｚ（すなわち、ハッシュ値の一致／不一致）は、注目画素Ｘの次の画素で色が変わる場合に不一致（すなわち、注目画素Ｘの色が変化する１画素手前で不一致）となる。また、長周期における注目画素Ｘと参照画素Ｚ（すなわち、ハッシュ値の一致／不一致）は、注目画素Ｘで色が変わる場合に不一致となる。
したがって、本変形例における符号化装置２は、注目画素Ｘで色（画素値）が変わる場合の相関特性（すなわち、長周期における一致度合いに相当）と、注目画素Ｘの次の画素で色（画素値）が変わる場合の相関特性（すなわち、短周期における一致度合いに相当）とを計数する。注目画素Ｘで色が変わる場合の相関特性が特に低くなる画素間隔が、長周期であり、この長周期よりも１画素短い周期が真の周期間隔となる。同様に、注目画素Ｘの次の画素で色が変わる場合の相関特性が特に低くなる画素間隔が、短周期であり、この短周期よりも１画素長い周期が真の周期間隔となる。
【００３８】
図１０は、注目画素Ｘで色が変わる場合の相関特性と、注目画素Ｘの次の画素で色が変わる場合の相関特性とを例示するグラフである。
図１０に例示するように、注目画素Ｘで色（画素値）が変わる場合の相関特性を示すグラフＡは、真の周期間隔（本例では８画素）よりも１画素長い画素間隔で相関特性（一致回数）が低下している。
また、注目画素Ｘの次の画素で色（画素値）が変わる場合の相関特性を示すグラフＢは、真の周期間隔（８画素）よりも１画素短い画素間隔で相関特性（一致回数）が低く、これよりも長い画素間隔で高くなっている。
したがって、本変形例のおける符号化装置２は、グラフＡが減少し、かつ、グラフＢが増加する画素間隔を真の周期間隔として抽出する。
なお、グラフＣは、注目画素Ｘで色（画素値）が変わる場合、又は、注目画素Ｘの次の画素で色（画素値）が変わる場合のいずれにも該当しない場合の相関特性を示すグラフである。
【００３９】
図１１は、第２の周期性判定部５２０の機能構成を例示する図である。なお、第２の周期性判定部５２０の各構成のうち、図４に例示された周期性判定部５１０の構成と実質的に同一のものには同一の符号が付されている。
図１１に例示するように、間隔判定部５１８は、画素値変化判定部５２２、状況別カウンタ５２４及び周期抽出部５２６を含む。
画素値変化判定部５２２は、スキャンに応じて注目画素Ｘの画素値の変化を判定し、判定結果を状況別カウンタ５２４に対して出力する。具体的には、画素値変化判定部５２２は、注目画素Ｘで画素値（色）が閾値Ａよりも大きく変化するか否かを判定し、画素値が閾値Ａよりも大きくが変化した場合に、「カウンタＡ」のカウント値を増加させるように状況別カウンタ５２４に指示する。また、画素値変化判定部５２２は、注目画素Ｘの次の画素で画素値（色）が閾値Ｂよりも大きく変化するか否かを判定し、画素値が閾値Ｂよりも大きく変化した場合に、「カウンタＢ」のカウント値を増加させるように状況別カウンタ５２４に指示する。なお、閾値Ａは、注目画素Ｘの画素値とその直前画素の画素値との差分値の中から、最大値を選択し、選択された最大値に既定の係数（例えば０．５）をかけて決定される。同様に、閾値Ｂは、注目画素Ｘの画素値とその次の画素の画素値との差分値の中から、最大値を選択し、選択された最大値に既定の係数（例えば０．５）をかけて決定される。
【００４０】
状況別カウンタ５２４は、画素値の変化状況に応じて、同一のハッシュ値が現れる画素間隔を集計する。具体的には、状況別カウンタ５２４は、注目画素Ｘで画素値が閾値Ａよりも大きく変化する場合に、この注目画素Ｘについて同一のハッシュ値が現れる画素間隔を「カウンタＡ」に記憶し、注目画素Ｘの次の画素で画素値が閾値Ｂよりも大きく変化する場合に、この注目画素Ｘについて同一のハッシュ値が現れる画素間隔を「カウンタＢ」に記憶し、これら以外の場合に、同一のハッシュ値が現れる画素間隔を「カウンタＣ」に記憶する。
【００４１】
周期抽出部５２６は、状況別カウンタ５２４に記憶されている画素間隔の集計値に基づいて、周期的な相関特性を抽出し、抽出された周期（画素間隔）を予測符号化部５３０に対して出力する。具体的には、周期抽出部５２６は、「カウンタＡ」が減少し、かつ、「カウンタＢ」が増加する画素間隔を抽出し、抽出された周期間隔の中から「カウンタＡ」、「カウンタＢ」及び「カウンタＣ」の合計（評価値）が最大となる周期間隔を真の周期として選択する。なお、周期抽出部５２６は、「カウンタＡ」の値から「カウンタＢ」の値を引いた数値（評価値）が最大となる周期間隔を真の周期として選択してもよい。
【００４２】
図１２は、状況別カウンタ５２４により記憶されるカウント値を例示する図である。
図１２に例示するように、状況別カウンタ５２４は、注目画素Ｘで画素値が閾値Ａよりも大きく変化する場合に、この注目画素Ｘと同一のハッシュ値が現れる画素間隔（注目画素Ｘと他の画素との間隔）の出現数を「カウンタＡ」に記憶し、注目画素Ｘの次の画素で画素値が閾値Ｂよりも大きく変化する場合に、この注目画素Ｘと同一のハッシュ値が現れる画素間隔（注目画素Ｘと他の画素との間隔）の出現回数を「カウンタＢ」に記憶し、これら以外の場合に、同一のハッシュ値が現れる画素間隔の出現回数を「カウンタＣ」に記憶する。
【００４３】
図１３は、周期抽出部５２６により算出される評価値を例示するグラフである。
図１３において、グラフＡは、閾値Ａ及び閾値Ｂを設定しない場合の評価値を示し、グラフＢは、閾値Ａ及び閾値Ｂを設定した場合の評価値を示す。このように、符号化装置２は、閾値Ａ及び閾値Ｂを設定することにより、評価値のピークを先鋭化させて、真の周期の抽出を容易にすることができる。
【００４４】
また、周期抽出部５２６による周期の抽出について、以下のように変形してもよい。すなわち、周期に関連するデータは、「カウンタＡ」と「カウンタＢ」の値に多く含まれていると考えられるので、逆に「カウンタＣ」の値は、周期性とは関係ない近接相関特性をより強く示していると考えられる。
そこで、周期抽出部５２６は、「カウンタＣ」の値を「カウンタＡ」、「カウンタＢ」及び「カウンタＣ」の合計値から減じたものを評価値としてもよい。これにより、周期抽出部５２６は、近接相関特性の影響が抑えられた評価値に基づいて、真の周期を抽出することができる。
【００４５】
また、「カウンタＣ」の値はいまだ周期性を反映しているので、周期抽出部５２６は、これを除去する補正を行い、補正後の「カウンタＣ」を各カウンタの合計値から減じたものを評価値としてもよい。具体的には、近接相関特性は、距離に対して逆比例した単調減少となるはずなので、周期抽出部５２６は、周期性を除去する補正を「カウンタＣ」の値にかける。例えば、周期抽出部５２６は、「カウンタＣ」の値から単調減少成分を抽出し、抽出された単調減少成分を、「カウンタＡ」、「カウンタＢ」及び「カウンタＣ」の合計値から減じたものを評価値とする。
図１４は、周期性を除去する前後の「カウンタＣ」の値を例示するグラフである。
図１４において、グラフＡは、周期性が除去される前の「カウンタＣ」の値を示し、グラフＢは、周期性が除去された後の「カウンタＣ」の値を示す。すなわち、グラフＢは、グラフＡから抽出された単調減少成分である。
このように、周期抽出部５２６は、「カウンタＣ」の値に基づいて近接相関特性（すなわち、単調減少成分）を抽出し、抽出された近接相関特性を各カウンタの合計値から減じたものを評価値とすることにより、周期的な相関特性をより顕在化させて、その周期の抽出を容易にすることができる。
【図面の簡単な説明】
【００４６】
【図１】本実施形態における符号化方法の概略を説明する図であり、（Ａ）は、周期的な相関特性に基づいて設定される画素の参照位置を例示し、（Ｂ）は、それぞれの参照位置と符号とを対応付ける符号テーブルを例示し、（Ｃ）は、本符号化方法により生成された符号データを例示する。
【図２】本発明にかかる符号化方法が適応される符号化装置２のハードウェア構成を、制御装置２０を中心に例示する図である。
【図３】制御装置２１（図２）により実行され、本発明にかかる符号化方法を実現する符号化プログラム５の機能構成を例示する図である。
【図４】周期性判定部５１０をより詳細に説明する機能構成図である。
【図５】周期性判定部５１０において生成されるデータを説明する図であり、（Ａ）は、ハッシュテーブル生成部５１４により生成されるハッシュテーブル７１４を例示し、（Ｂ）は、間隔判定部５１８により生成される画素間隔カウンタ７１８を例示する。
【図６】予測符号化部５３０をより詳細に説明する機能構成図である。
【図７】符号化プログラム５の動作（Ｓ１０）を示すフローチャートである。
【図８】相関特性と符号量との関係を示すグラフである。
【図９】長周期及び短周期の挙動を説明する図である。
【図１０】注目画素Ｘで色が変わる場合の相関特性と、注目画素Ｘの次の画素で色が変わる場合の相関特性とを例示するグラフである。
【図１１】第２の周期性判定部５２０の機能構成を例示する図である。
【図１２】状況別カウンタ５２４により記憶されるカウント値を例示する図である。
【図１３】周期抽出部５２６により算出される評価値を例示するグラフである。
【図１４】周期性を除去する前後の「カウンタＣ」の値を例示するグラフである。
【符号の説明】
【００４７】
２・・・符号化装置
５・・・符号化プログラム
５００・・・画像データ取得部
５１０，５２０・・・周期性判定部
５１２・・・ハッシュ値算出部
５１４・・・ハッシュテーブル生成部
５１６・・・間隔計測部
５１８・・・間隔判定部
５２２・・・画素値変化判定部
５２４・・・状況別カウンタ
５２６・・・周期抽出部
５３０・・・予測符号化部
５４０・・・符号出力部
【図１】
2005151278.tif 000003
【図２】
2005151278.tif 000004
【図３】
2005151278.tif 000005
【図４】
2005151278.tif 000006
【図５】
2005151278.tif 000007
【図６】
2005151278.tif 000008
【図７】
2005151278.tif 000009
【図８】
2005151278.tif 000010
【図９】
2005151278.tif 000011
【図１０】
2005151278.tif 000012
【図１１】
2005151278.tif 000013
【図１２】
2005151278.tif 000014
【図１３】
2005151278.tif 000015
【図１４】
2005151278.tif 000016