JP4867620B2 - 画像処理装置及び画像処理プログラム - Google Patents

Description

本発明は、２つの画像を照合する画像処理装置及び画像処理プログラムに関する。

検索対象の画像データベースから、基準画像と類似する画像を検索する場合などに用いるために、２つの画像の照合を行う様々な技術が開発されている。画像の照合を行う一般的な技術として、画像から物理的な特徴量を抽出し、抽出された画像の特徴量に基づいて２つの画像の類似性を判断する技術がある。このような技術において、例えば、画像の色の特徴や、画像に表示される対象の輪郭線などが特徴量として抽出される。１つの画像からＮ個の特徴量が抽出された場合、抽出された特徴量はＮ次元の特徴量ベクトルとして表すことができる。一般に、画像から抽出された特徴量に基づいて画像の類似度を判断する技術では、基準画像の特徴量ベクトルと検索対象の画像の特徴量ベクトルとの間のユークリッド距離が小さいほど、基準画像と検索対象の画像とが類似していると判断する。

画像から特徴量を抽出する方法の１つとして、画像内の特徴点を選定し、選定した特徴点における特徴量を抽出する方法がある。この場合、照合する２つの画像内の対応する特徴点から抽出される特徴量の類似度に基づいて画像の類似度を判断する。特許文献１及び特許文献２には、画像内の特徴点における特徴量を用いて画像の類似度を判断する技術において、画像の位置ずれや歪みなどの変形があっても適切な画像の照合を可能とするための技術が開示されている。

特許文献１には、２つのパターン画像内の特徴点を選定し、選定した特徴点の特徴量を抽出して、被照合パターン画像内の各特徴点の特徴量と、その特徴点に対応する基準パターン画像内の特徴点の特徴量と、の類似度が最大になるように、被照合パターン画像内の各特徴点を水平方向及び垂直方向に変位させる技術が開示されている。特許文献１に記載の技術では、被照合パターン画像内の各特徴点の特徴量に加えて、その特徴点の水平方向及び垂直方向の近傍点の特徴量を求め、その特徴点に対応する基準パターン画像内の特徴点の特徴量との類似度が最大となる特徴量を有する近傍点を新たな特徴点とする。

特許文献２には、線図形のパターン照合を行う技術において、検査図形及びモデル図形に生じている位置ずれや歪みなどの変形について、検査図形の特徴点とモデル図形の特徴点との対応関係を基に変形の種類を推定し、推定した変形の種類に基づいて検査図形を補正し、検査図形とモデル図形との類似度を判断する技術が開示されている。特許文献２に記載の技術では、線図形内の線の端点、分岐点、及び交差点などをその線図形の特徴点として選択し、選択した特徴点から抽出される特徴量に基づいて検査図形の特徴点とモデル図形の特徴点との対応づけを行う。

特開２００１−１３４７５７号公報 特開２００２−２９８１４１号公報

しかしながら、特許文献１に記載の技術では、特徴点の水平方向及び垂直方向の近傍点の特徴量を逐次的に評価するため、例えば特徴点の位置が垂直方向にずれた状態で水平方向の近傍点の特徴量を評価しても、正しい評価結果が得られるとは限らない。

また、特許文献２に記載の技術は、線の端点、分岐点、交差点などの特徴点の対応関係に基づいて画像の照合を行うので、線図形など、特徴点の選定が容易な画像が照合対象として適している。例えば濃淡画像のように画像中の図形の線の端点などが明確でない画像や、例えば紙文書を複写機で複製して得られる画像のようにノイズや濃度変化、コントラスト変化などによって局所的な特徴量が大きく変動する画像などについては、画像の特徴点の適切な選定が困難であるため、特許文献２に記載の技術を適用するのは困難である。

本発明の目的は、２つの画像を精度良く照合できる画像処理装置及び画像処理プログラムを提供することである。

本発明に係る画像処理装置は、基準画像と検索対象画像とを照合する画像処理装置であって、前記基準画像を複数の領域に分割する領域分割手段と、前記基準画像の各領域に対応する前記検索対象画像の領域を選択する対応領域選択手段であって、前記基準画像の各領域を注目領域とし、その注目領域に対応する前記検索対象画像の領域の候補である複数の対応候補領域のそれぞれについて、その注目領域から抽出された特徴量と、その対応候補領域から抽出された特徴量と、に基づいて特徴量の適合度を求め、前記基準画像上のその注目領域の位置から、前記検索対象画像上のその対応候補領域の位置に相当する前記基準画像上の位置への変位方向と、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向と、に基づいて変位方向の整合度を求め、前記対応候補領域のそれぞれについて求められた、前記特徴量の適合度及び前記変位方向の整合度に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択する対応領域選択手段と、前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段と、を備えることを特徴とする。

本発明に係る画像処理装置において、前記領域分割手段は、さらに、前記検索対象画像を複数の領域に分割し、前記対応領域選択手段は、前記領域分割手段で分割された前記検索対象画像の複数の領域から、前記複数の対応候補領域を選択することが好ましい。

また、前記領域分割手段は、前記基準画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下になるように、前記基準画像を複数の領域に分割するものとしても良い。

本発明に係る情報処理装置において、さらに、それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像を、それぞれ、前記基準画像及び前記検索対象画像の各領域よりも小さい領域にさらに分割する多重領域分割手段を備え、所定の条件を満たすまで、前記多重領域分割手段における処理と、前記多重領域分割手段において分割された前記基準画像及び前記検索対象画像を処理対象とする前記対応領域選択手段における処理と、を反復して行うことが好ましい。また、前記所定の条件は、それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下であることが好ましい。

本発明に係る画像処理装置において、前記変位方向の整合度は、その注目領域の前記基準画像上の位置から、その対応候補領域の前記検索対象画像上の位置に相当する前記基準画像上の位置への変位方向を表すベクトルと、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向を表すベクトルと、の内積に基づいて求められることが好ましい。

本発明に係る画像処理装置において、前記対応領域選択手段は、前記対応候補領域のそれぞれについて、前記特徴量の適合度及び前記変位方向の整合度に基づく評価関数を用いて評価値を求め、前記対応候補領域のそれぞれについて求められた評価値と、前記評価関数と、を用いて、前記対応候補領域のそれぞれについて新たな評価値を求める処理を、所定の条件を満たすまで反復して行った後、前記対応候補領域のそれぞれについて求められた評価値に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択することが好ましい。

また、前記対応領域選択手段は、弛緩法（relaxation method）に従って、前記対応候補領域のそれぞれについて、前記特徴量の適合度及び前記変位方向の整合度に基づく評価関数を用いて評価値を求め、前記対応候補領域のそれぞれについて求められた評価値と、前記評価関数と、を用いて、前記対応候補領域のそれぞれについて新たな評価値を求める処理を、所定の条件を満たすまで反復して行うことが好ましい。

本発明に係る画像処理プログラムは、基準画像と検索対象画像とを照合する画像処理装置としてコンピュータを機能させるプログラムであって、前記基準画像を複数の領域に分割する領域分割手段、前記基準画像の各領域に対応する前記検索対象画像の領域を選択する対応領域選択手段であって、前記基準画像の各領域を注目領域とし、その注目領域に対応する前記検索対象画像の領域の候補である複数の対応候補領域のそれぞれについて、その注目領域から抽出された特徴量と、その対応候補領域から抽出された特徴量と、に基づいて、特徴量の適合度を求め、前記基準画像上のその注目領域の位置から、前記検索対象画像上のその対応候補領域の位置に相当する前記基準画像上の位置への変位方向と、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向と、に基づいて、変位方向の整合度を求め、前記対応候補領域のそれぞれについて求められた、前記特徴量の適合度及び前記変位方向の整合度に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択する対応領域選択手段、前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段、として前記コンピュータを機能させることを特徴とする。

請求項１及び９に係る発明によると、基準画像と検索対象画像とを精度良く照合することができる。

請求項２に係る発明によると、基準画像と検索対象画像とを精度良く、かつ容易に照合することができる。

請求項３に係る発明によると、基準画像生成時の画像の幾何学的誤差に応じて適切に基準画像と検索対象画像とを照合できる。

請求項４に係る発明によると、基準画像及び検索対象画像のいずれか一方又は両方に大きな幾何学的変動がある場合でも、高速に基準画像と検索対象画像とを照合できる。

請求項５に係る発明によると、基準画像生成時の画像の幾何学的誤差に応じて適切に基準画像と検索対象画像とを照合できる。

請求項６に係る発明によると、基準画像の注目領域の変位方向の整合度を容易に求めることができる。

請求項７及び８に係る発明によると、基準画像と検索対象画像とを精度良く、かつ容易に照合できる。

以下に、本発明の実施の形態を、図面を用いて詳細に説明する。

図１は、本発明の１つの実施形態の画像処理装置の構成の一例を示す図である。画像処理装置１０は、制御部１２、記憶部１４、画像入力部１６、標準入力部１８、出力部２０、及び通信部２２を備える。制御部１２、記憶部１４、画像入力部１６、標準入力部１８、出力部２０、及び通信部２２は、バス２４を介して相互に接続される。

制御部１２は、記憶部１４に記憶された画像処理プログラムを読み出して実行し、画像の照合に関する後述の処理を行う。制御部１２は、例えば一般的なコンピュータのＣＰＵ（中央演算装置：Central Processing Unit）などの演算装置によって実現できる。

記憶部１４は、ハードディスクやＣＤ、ＤＶＤなどの記憶媒体であり、画像処理装置１０の処理対象となる画像データや、制御部１２が行う処理の流れを記述したプログラムなどを記憶することができる。

画像入力部１６は、画像処理装置１０で処理対象となる画像データの入力を受け付ける。例えば、画像入力部１６は、画像を所定間隔ごとにサンプリングし、画素ごとに色相、輝度、又は明度などの値を有するデジタル画像データとして読み込む。画像入力部１６によって読み込まれた画像データは、記憶部１４に記憶させることができる。画像入力部１６は、スキャナ、デジタルカメラ又はデジタルビデオなどの一般的な画像入力装置を用いて実現できる。

標準入力部１８は、キーボード、マウスなどの入力装置であって、制御部１２で行われる処理において必要な指示など、ユーザからの入力を受け付ける。

出力部２０は、例えばＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどの表示装置であって、処理対象の画像の内容や、制御部１２における処理の結果などを表示する。

通信部２２は、例えばインターネットなどの通信手段（図示しない）を介して画像処理装置１０に接続された図示しないサーバ、他のコンピュータ、又はその他の機器と、画像処理装置１０と、の間の通信を行うためのインターフェースである。画像処理装置１０は、通信部２２を介して処理対象の画像データを取得することができる。

図２は、制御部１２が行う画像の類似度算出処理の一例を示すフローチャートである。図２に示す処理は、ある基準画像と検索対象の画像との類似度を算出する処理である。例えば、記憶部１４に記憶された画像データベースの中から、ユーザが指定した基準画像と最も類似する画像を検索する場合に、画像データベース中の画像のそれぞれについて図２に示す処理を行うことで基準画像との類似度を算出し、画像データベース中の画像のうち基準画像との類似度が最大である画像を、基準画像に最も類似する画像として抽出することができる。

ステップＳ１で、制御部１２は、画像照合の基準となる基準画像を取得する。基準画像の画像データは、画像入力部１６又は通信部２２を介して取得できる。制御部１２は、例えばユーザの指示などに応じて、記憶部１４に記憶された画像の１つを基準画像として取得することもある。

次に、ステップＳ２で、制御部１２は、基準画像との類似度を算出する検索対象の画像を取得する。検索対象画像は、記憶部１４に記憶された画像データベースから取得しても良いし、画像入力部１６又は通信部２２を介して取得しても良い。

ステップＳ３で、基準画像を複数の領域（メッシュ）に分割する。例えば、図３のように、基準画像を矩形のメッシュに分割する。各メッシュの大きさは均等であっても良いし、不均等であっても良い。また、メッシュの形状は、閉曲線で囲まれる任意の形状とすることができる。例えば、矩形、円形、又は多角形とすることができる。

各メッシュの大きさは、処理対象となる画像の特性によって決定することができる。例えば、基準画像が紙文書を複写機で複製したり、スキャナで読み取ったりして得られる再生画像である場合、使用されるスキャナ、光学系、又は印刷機構などの誤差により、再生画像の印刷位置や拡大率に誤差が生じる。この印刷位置や拡大率の誤差により発生する変位量の最大値が既知である場合、この最大変位量に応じて各メッシュの大きさを決定することが好適である。例えば、主走査、副走査方向の最大変位量がそれぞれδｈ、δｖである場合、各メッシュの幅をδｈ以下、高さをδｖ以下とすることが好適である。

以下の説明では、図３に示すように、画像データを横１０×縦１０＝１００個の均等な矩形メッシュとして分割したものとする。このとき、画像データが横５００画素×縦５００画素であったならば、１つのメッシュには横５０画素×縦５０画素が含まれることになる。

ステップＳ４で、制御部１２は、ステップＳ３で分割された基準画像の各メッシュについて特徴量を抽出する。以下の説明では、各メッシュの平均色及びエッジ画素量を特徴量として抽出するものとする。しかし、以下の説明は一例であり、他の物理量を特徴量として抽出しても良い。

各メッシュの平均色は、各メッシュに含まれる画素毎の色の成分をメッシュ全体について平均することによって算出することができる。例えば、各画素が赤、緑及び青（ＲＧＢ）の各色成分により表現され、各色成分が数値化されている場合、メッシュに含まれる全画素のＲ成分、Ｇ成分及びＢ成分の色成分ごとに加算し、その合計値を画素数で割ることによって、そのメッシュの平均色の各色成分を算出する。画像データが白黒である場合には、各画素をＲＧＢの色空間に変換した後に平均色を計算することができる。例えば、画素が白の場合にはＲＧＢ＝（２５５，２５５，２５５）、黒の場合にはＲＧＢ＝（０，０，０）と変換した後に、メッシュ毎の平均色を算出する。ここでは、画素の色データがＲＧＢ色空間で表現されている場合を例示したが、これに限定されるものではない。画素の色データがＹＵＶ色空間、ＹＭＣＫ色空間などの他の色空間で表現されている場合も、各色成分の平均値を算出することによって平均色を算出することができる。

各メッシュのエッジ画素量とは、１つのメッシュ内の全画素数に対するエッジ画素数の割合を示す。エッジ画素量の算出は、既存のエッジ画素の検出方法を用いて行うことができる。例えば、画像の輝度成分に対してエッジ抽出フィルタを用いて画素単位のエッジ量を抽出し、所定の閾値を超えるエッジ量を有する画素をエッジ画素とする。

以上のように、各メッシュに対して平均色とエッジ画素量の２つの特徴量が抽出される。図３の例では、メッシュ分割数が１００個であるので、平均色及びエッジ画素量がそれぞれ１００個ずつ得られる。

次に、図２のステップＳ５で、制御部１２は、検索対象画像を複数のメッシュに分割する。ステップＳ５では、ステップＳ３について説明したのと同様の処理を検索対象画像に対して行う。

ステップＳ６では、制御部１２は、ステップＳ５で分割された検索対象画像の各メッシュについて特徴量を抽出する。ステップＳ６では、ステップＳ４について説明したのと同様の処理を検索対象画像に対して行う。

ステップＳ６までの処理が終了すると、基準画像及び検索対象画像はそれぞれメッシュに分割され、各メッシュから特徴量が抽出される。図３に示すように、基準画像の各メッシュをＭＳＨｘ_ｉｊと表記し、検索対象画像の各メッシュをＭＳＨｙ_ｉｊと表記する。添え字ｉ及びｊは、それぞれメッシュの横及び縦の位置を示す。図３の画像分割例では、メッシュの分割数が横１０×縦１０であるので、添え字のｉ，ｊはそれぞれ０から９までの値となり、基準画像において（横２，縦１）の位置にあるメッシュはＭＳＨｘ_２１と表記される。

また、各メッシュから抽出された平均色及びエッジ画素量を、それぞれＡＶＥｘ_ｉｊ及びＥＧＥｘ_ｉｊと表記する。平均色はＲＧＢ色空間においてＲ成分、Ｇ成分及びＢ成分を有し、各成分をＡＶＥ_Ｒｘｉｊ，ＡＶＥ_Ｇｘｉｊ及びＡＶＥ_Ｂｘｉｊと表記する。すなわち、ＡＶＥｘ_ｉｊ＝（ＡＶＥ_Ｒｘｉｊ，ＡＶＥ_Ｇｘｉｊ，ＡＶＥ_Ｂｘｉｊ）と表される。メッシュＭＳＨｘ_ｉｊから抽出された平均色及びエッジ画素量をＭＳＨｘ_ｉｊの特徴量ベクトル（ＡＶＥ_Ｒｘｉｊ，ＡＶＥ_Ｇｘｉｊ，ＡＶＥ_Ｂｘｉｊ，ＥＧＥｘ_ｉｊ）として表すことができる。

次に、図２のステップＳ７で、制御部１２は、基準画像の各メッシュについて、検索対象画像において対応するメッシュを選択する。ステップＳ７では、基準画像の各メッシュについて、そのメッシュの特徴量と、そのメッシュの周辺のメッシュの変位方向と、を考慮して検索対象画像上の対応メッシュを選択する。

図４から図６を参照し、図２に示すフローチャートのステップＳ７の対応メッシュ選択処理について説明する。ここでは、弛緩法（relaxation method）に従ってステップＳ７の対応メッシュ選択処理を行う例について説明する。弛緩法は、対象物にその特徴によってラベルを付ける方法において、対象物間の関係の情報を用いてラベル付けのあいまいさを取り除いていく方法である。

図４は、図２のフローチャートのステップＳ７の対応メッシュ選択処理の流れの例を示すフローチャートである。図５は、図４に示す処理における基準画像及び検索対象画像の各メッシュの関係の一例を表す説明図である。

まずステップＳ７０で、制御部１２は、基準画像のメッシュのうちから、１つの注目メッシュａ_ｉを選択する。図５（ａ）に示す例では、基準画像のメッシュＭＳＨｘ_１１が注目メッシュａ_ｉとして選択されている。

次に、図４のステップＳ７１で、制御部１２は、基準画像の注目メッシュａ_ｉに対応する検索対象画像内のメッシュの候補を選択する。例えば、図５（ａ）及び図５（ｂ）に示すように、基準画像の注目メッシュａ_ｉの周囲８個のメッシュを近傍メッシュｂ_ｎ（ｎ＝１，２，・・・，８）とし、基準画像上の注目メッシュａ_ｉ及び近傍メッシュｂ_ｎの位置に対応する検索対象画像上の位置にある９個のメッシュｙ_ｎ（ｎ＝０，１，・・・，８）を注目メッシュａ_ｉの対応候補メッシュとして選択する。つまり、検索対象画像上において、注目メッシュａ_ｉの基準画像上の位置（横１，縦１）に対応する位置のメッシュＭＳＨｙ_１１（＝ｙ０）及びＭＳＨｙ_１１の周囲８個のメッシュを対応候補メッシュｙ_ｎとする。 図６に、基準画像の注目メッシュａ_ｉの位置から近傍メッシュｂ_ｎの位置への変位方向λ_ｎを示す。変位方向λ_１，λ_２，…，λ_８は、それぞれ、注目メッシュａ_ｉの位置から近傍メッシュｂ_１，ｂ_２，…，ｂ_８の位置への変位方向を示し、λ_０は「変位なし」の状態を示す。対応候補メッシュｙ_ｎは、注目メッシュａ_ｉを図６に示す変位方向λ_ｎ（ｎ＝０，１，…，８）へ変位させた場合の基準画像上の位置（注目メッシュａ_ｉの位置及び近傍メッシュｂ_ｎの位置）に対応する検索対象画像上の位置にあるメッシュであるとも言える。よって、「注目メッシュａ_ｉの対応メッシュがｙ_ｊである」ことは、「注目メッシュａ_ｉの変位方向がλ_ｊである」ことであると言える。

図４のステップＳ７１で選択された対応候補メッシュｙ_ｎのうちの１つのメッシュが、ステップＳ７２以下の処理により、注目メッシュａ_ｉの対応メッシュとして選択される。

ステップＳ７２では、制御部１２は、ある対応候補メッシュｙ_ｊについて、注目メッシュａ_ｉの対応メッシュとしての適合度を計算する。ここで、注目メッシュａ_ｉの対応メッシュとしてｙ_ｊが正解である確率、つまり、注目メッシュａ_ｉの変位方向がλ_ｊである確率をｐ_ｉ ^（ｒ）（λ_ｊ）とする。すべての変位方向λ_ｊ（ｊ＝０，１，・・・，８）についてのｐ_ｉ ^（ｒ）（λ_ｊ）の和は１である（式（１））。

式（１）で、Ｍは、変位方向λ_ｊの個数を示し、ここではＭ＝８である。また、式（１）で、（ｒ）は、ステップＳ７０からステップＳ７５までの処理のｒ回目の反復を表し、初期値ｒ＝０は例えばｐ_ｉ ^（０）（λ_ｊ）＝１／（Ｍ＋１）＝１／９とする。ステップＳ７０からステップＳ７５までの処理を反復して行って、ｐ_ｉ ^（ｒ）（λ_ｊ）を求めることで、注目メッシュａ_ｉの対応メッシュを選択する。

注目メッシュａ_ｉの変位方向がλ_ｊであることの適合度を求めるための適合関数として、例えば式（２）で定義される関数を用いる。適合関数ｃ_ｉｎ（ｊ，ｋ）は、基準画像において注目メッシュａ_ｉの周辺に位置する近傍メッシュｂ_ｎが、注目メッシュａ_ｉの変位方向λ_ｊと同じ変位方向を有し、かつ、注目メッシュａ_ｉから抽出された特徴量と対応候補メッシュｙ_ｊから抽出された特徴量との類似性が高い場合に大きな値を取るように定義される。

ここで、λ_ｊは、注目メッシュａ_ｉの変位方向を表すベクトル（‖λ_ｊ‖＝１）、λ_ｋは、近傍メッシュｂ_ｎの変位方向を表すベクトル（‖λ_ｋ‖＝１）、ｃｏｒｒ（ｖ_ｉ，ｗ_ｊ）は、注目メッシュａ_ｉの特徴量ベクトルｖ_ｉと対応候補メッシュｙ_ｊの特徴量ベクトルｗ_ｊとの間の相関係数、αは調整パラメータである。

式（２）において、注目メッシュａ_ｉの特徴量ベクトルｖ_ｉと対応候補メッシュｙ_ｊの特徴量ベクトルｗ_ｊとの間の相関係数ｃｏｒｒ（ｖ_ｉ，ｗ_ｊ）の項は、注目メッシュａ_ｉの特徴量ベクトルｖ_ｉと対応候補メッシュｙ_ｊの特徴量ベクトルｗ_ｊとの類似性を表すものである。各メッシュから抽出される特徴量の個数をＮ、ｖ_ｉ＝（ｖ_ｉ１，・・・，ｖ_ｉＮ）、ｗ_ｊ＝（ｗ_ｊ１，・・・，ｗ_ｊＮ）とすると、ｃｏｒｒ（ｖ_ｉ，ｗ_ｊ）は、例えば次の式（３）に従って計算でき、−１≦ｃｏｒｒ（ｖ_ｉ，ｗ_ｊ）≦１となる。

本実施形態では、各メッシュから平均色のＲ成分ＡＶＥ_Ｒ、Ｇ成分ＡＶＥ_Ｇ、及びＢ成分ＡＶＥ_Ｂと、エッジ画素量ＥＧＥと、の４個の特徴量が抽出される。よって、注目メッシュａ_ｉの特徴量ベクトルｖ_ｉ＝（ｖ_ｉ１，・・・，ｖ_ｉ４）＝（ＡＶＥ_Ｒａｉ，ＡＶＥ_Ｇａｉ，ＡＶＥ_Ｂａｉ，ＥＧＥａ_ｉ）、対応候補メッシュｙ_ｊの特徴量ｗ_ｊ＝（ｗ_ｊ１，・・・，ｗ_ｊ４）＝（ＡＶＥ_Ｒｙｊ，ＡＶＥ_Ｇｙｊ，ＡＶＥ_Ｂｙｊ，ＥＧＥｙ_ｊ）として、式（３）によりｃｏｒｒ（ｖ_ｉ，ｗ_ｊ）を計算する。

図５を参照すると、例えば注目メッシュａ_ｉが変位方向λ_１を有すること、つまり、注目メッシュａ_ｉの対応メッシュがｙ_１であることの適合度を求める場合、注目メッシュａ_ｉの特徴量ベクトルｖ_ｉと、対応メッシュｙ_１の特徴量ベクトルｗ_１と、の相関係数ｃｏｒｒ（ｖ_ｉ，ｗ_１）を求めることになる。特徴量ベクトルｖ_ｉと特徴量ベクトルｗ_ｊとの間の相関係数の代わりに、２つの特徴量ベクトル間のユークリッド距離を求めても良い。

注目メッシュａ_ｉの変位方向λ_ｊ及び近傍メッシュｂ_ｎの変位方向λ_ｋのいずれも「変位なし」ではない場合（ｊ，ｋ≠０）、式（２−１）に従って適合関数ｃ_ｉｎ（ｊ，ｋ）を計算する。式（２−１）の第１項のλ_ｊ・λ_ｋは、注目メッシュａ_ｉの変位方向の整合度を表し、λ_ｊとλ_ｋとの内積である。ここでは、‖λ_ｊ‖＝‖λ_ｋ‖＝１より、−１≦λ_ｊ・λ_ｋ≦１となる。

注目メッシュａ_ｉの変位方向λ_ｊ及び近傍メッシュｂ_ｎの変位方向λ_ｋのいずれも「変位なし」である場合（ｊ＝ｋ＝０）、式（２−２）に従って適合関数ｃ_ｉｎ（ｊ，ｋ）を計算する。式（２−２）の第１項において、注目メッシュａ_ｉの変位方向の整合度を表す値を１とする。この場合、注目メッシュａ_ｉ及び近傍メッシュｂ_ｎの変位方向は同じであるので、変位方向の整合度を高く設定する。

注目メッシュａ_ｉの変位方向λ_ｊ及び近傍メッシュｂ_ｎの変位方向λ_ｋのいずれか一方のみが「変位なし」である場合、式（２−３）に従って適合関数ｃ_ｉｎ（ｊ，ｋ）を計算する。式（２−３）では、注目メッシュａ_ｉの変位方向の整合度は０としている。

式（２）の適合関数ｃ_ｉｎ（ｊ，ｋ）を用いて、ある近傍メッシュｂ_ｎとの関係において注目メッシュａ_ｉが変位方向λ_ｊを持つ平均適合度ｆ_ｉｎ ^（ｒ）（ｊ）は、式（４）で表される。

ｆ_ｉｎ ^（ｒ）（ｊ）を、注目メッシュａ_ｉのすべての近傍メッシュｂ_ｎ（ｎ＝１，２，・・・，８）について考えると、注目メッシュａ_ｉの変位方向がλ_ｊである適合度ｑ_ｉ ^（ｒ）（λ_ｊ）は、次の式（５）で表される。

以上で説明したとおり、ステップＳ７２では、制御部１２は、式（５）に従って、ある対応候補メッシュｙ_ｊの適合度（注目メッシュａ_ｉの変位方向がλ_ｊである適合度）ｑ_ｉ ^（ｒ）（λ_ｊ）を求める。

ステップＳ７３では、制御部１２は、注目メッシュａ_ｉのすべての対応候補メッシュｙ_ｎについて、適合度ｑ_ｉ ^（ｒ）（λ_ｊ）が計算されたか否かを判定する。すべての対応候補メッシュｙ_ｎについて適合度が計算されていれば、ステップＳ７４に進み、すべての対応候補メッシュｙ_ｎについて適合度が計算されていなければ、ステップＳ７２に戻ってまだ適合度の計算されていない対応候補メッシュについて適合度を計算する。

ステップＳ７４では、制御部１２は、ステップＳ７２で求めた各対応候補メッシュｙ_ｊの適合度ｑ_ｉ ^（ｒ）（λ_ｊ）を用いて、注目メッシュａ_ｉの対応メッシュとしてｙ_ｊが正解である確率、つまり、注目メッシュａ_ｉの変位方向がλ_ｊである確率ｐ_ｉ ^（ｒ）（λ_ｊ）の値を次の式（６）に従って更新する。

ステップＳ７４では、注目メッシュａ_ｉのすべての対応候補メッシュｙ_ｎ（ｎ＝０，１，２，・・・，８）について、正解確率ｐ_ｉ ^（ｒ）（λ_ｎ）を計算する。

ステップＳ７５では、基準画像のすべてのメッシュについて処理が行われたか否かを確認する。基準画像のすべてのメッシュについて処理が行われていればステップＳ７６に進み、基準画像のすべてのメッシュについて処理が行われていなければ、ステップＳ７０に戻ってまだ処理が行われていないメッシュを注目メッシュとしてステップＳ７１以下の処理を行う。

ステップＳ７６では、所定の収束条件が満たされているか否かを判定する。例えば、ステップＳ７０からステップＳ７５までの処理の反復回数ｒが予め設定された回数を超えていれば収束条件を満たすと判定する。また、例えば、基準画像において、変位方向がλ_ｊである確率ｐ_ｉ ^（ｒ）（λ_ｊ）が予め設定された値以上（例えば、０．８以上）となるメッシュが、予め設定された値以上（例えば、基準画像のメッシュ数の合計の９割以上）となった場合に収束条件を満たすと判定しても良い。

ステップＳ７７では、基準画像上のすべてのメッシュａ_ｉについて、確率ｐ^（ｒ）（λ_ｊ）が最大となるλ_ｊを変位方向として採用する。つまり、確率ｐ^（ｒ）（λ_ｊ）が最大となる検索対象画像の対応候補メッシュｙ_ｊを、そのメッシュａ_ｉの対応メッシュとして選択する。ステップＳ７７の処理の後、対応メッシュ選択処理（図２のステップＳ７）は終了する。

以上、図４から図６を参照して説明したステップＳ７の処理では、近傍メッシュｂ_ｎとしては、注目メッシュａ_ｉの周囲８個のメッシュを選択し（図５（ａ））、対応候補メッシュｙ_ｎとしては、基準画像上の注目メッシュａ_ｉ及び近傍メッシュｂ_ｎの位置に対応する検索対象画像上の位置にあるメッシュを選択した。図７に、近傍メッシュｂ_ｎ及び対応候補メッシュｙ_ｎの選択の他の一例を示す。図７を参照すると、注目メッシュａ_ｉの近傍メッシュｂ_ｎとしては、注目メッシュａ_ｉの周囲の２４個のメッシュが選択され、対応候補メッシュｙ_ｎとしては、注目メッシュａ_ｉ（ＭＳＨｘ_２２）の位置に対応する検索対象画像上の位置のメッシュｙ_０（＝ＭＳＨｙ_２２）と、近傍メッシュｂ_ｎ（ｎ＝１，２，・・・，２４）の位置に対応する、ｙ_０の周囲の２４個のメッシュと、が選択される。図７に示すように近傍メッシュｂ_ｎ及び対応候補メッシュｙ_ｎを選択した場合、図４のステップＳ７２において、注目メッシュａ_ｉの変位方向がλ_ｊであることの適合度ｑ_ｉ ^（ｒ）（λ_ｊ）は、変位方向λ_ｊの個数Ｍ＝２４として、次の式（７）に従って計算される。

式（７）中の適合関数ｃ_ｉｎ（ｊ，ｋ）は、式（２）に従って計算される。式（７）において、ｄ_ｉｎは、注目メッシュａ_ｉと近傍メッシュｂ_ｎとの距離に関する重みであり、距離が大きいほど小さな値とする。例えば、メッシュａ_ｉとｂ_ｎとの距離の逆数をｄ_ｉｎとすることができる。

以上で説明したステップＳ７の処理によって、基準画像の各メッシュと検索対象画像の各メッシュとの対応付けを行った後、ステップＳ８で、制御部１２は、ステップＳ７で求められた基準画像の各メッシュと検索対象画像の各メッシュとの対応関係に基づいて、基準画像と検索対象画像との類似度を算出する。例えば、基準画像と検索対象画像との対応するメッシュの各組について、特徴量ベクトル間の相関係数やユークリッド距離などを求めることで特徴量の類似度を算出し、算出した類似度を基に基準画像と検索対象画像との類似度を評価する。

図８及び図９を参照し、制御部１２が行う類似度算出処理の他の一例について説明する。

図８は、制御部１２が行う処理の流れの一例を示すフローチャートである。図８に示すフローチャートにおいて、図２に示すフローチャートと同様の処理には同様の符号を付す。

図８において、基準画像取得処理（ステップＳ１）から基準画像の特徴量の抽出処理（ステップＳ４）までは、図２を参照して説明した上述のステップＳ１からステップＳ４までの処理と同様の処理が行われる。次に、図８に示すフローチャートの処理は、検索対象画像をメッシュ分割（図２のステップＳ５）及び検索対象画像の特徴量の抽出（図２のステップＳ６）を行うことなく、ステップＳ１０の対応メッシュ選択処理へ進む。

ステップＳ１０の対応メッシュ選択処理では、制御部１２は、図４に示すフローチャートに従って処理を行うが、対応候補メッシュの選択処理（ステップＳ７１）及び対応候補メッシュの適合度計算処理（ステップＳ７２）の内容が、図４から図７を参照して説明した上述のステップＳ７１及びステップＳ７２の処理の内容と異なる。

図９を参照し、ステップＳ１０の対応メッシュ選択処理における、基準画像の注目メッシュの対応候補メッシュ選択処理（図４のステップＳ７１）について説明する。図９（ａ）に示すように、基準画像の注目メッシュａ_ｉの周辺の領域である近傍Ｂ内において、所定の方向及び所定の大きさを有する変位方向ベクトルλ_ｎに従って注目メッシュａ_ｉを変位させた位置のメッシュを近傍メッシュｂ_ｎとする。変位方向ベクトルλ_ｎの個数は必要に応じて設定できるし、変位方向ベクトルλ_ｎそれぞれの方向及び大きさも、必要に応じて設定できる。例えば、λ_ｎの大きさを基準画像の各メッシュの横方向又は縦方向の大きさのγ倍（０＜γ）とし、γの値を任意に設定することができる（例えば、γ＝０．５，０．７５，１．０，１．２５）。

図８及び図９を参照して説明する本例の処理では、図８のステップＳ３において分割された基準画像のメッシュに一致しない領域が近傍メッシュｂ_ｎとして選択されることがある。図９（ａ）に示すように、注目メッシュａ_ｉの一部と近傍メッシュｂ_ｎの一部とが重複していても良い。また、異なる近傍メッシュｂ_ｉ及びｂ_ｊの一部が重複しても良い。このように近傍メッシュｂ_ｎが選択され、基準画像上の近傍メッシュｂ_ｎの位置に対応する検索対象画像上の位置にある領域が、対応候補メッシュｙ_ｎとして選択される。

ステップＳ１０の対応メッシュ選択処理において、図９を参照して説明したように注目メッシュａ_ｉの対応候補メッシュｙ_ｎを選択した（図４のステップＳ７１）後、ステップＳ７２において、制御部１２は、まず、選択した対応候補メッシュｙ_ｎから特徴量を抽出する。この、特徴量を抽出する処理は、図８のステップＳ４において基準画像の各メッシュについて行われる特徴量抽出処理と同様である。そして、次の式（８）に従って、注目メッシュａ_ｉの変位方向がλ_ｊであることの適合度ｑ_ｉ ^（ｒ）（λ_ｊ）を計算する。

式（８）中の適合関数ｃ_ｉｎ（ｊ，ｋ）は、式（２）に従って計算される。式（８）において、Ｂは、近傍メッシュに付される番号の集合である。ｄ_ｉｎは、注目メッシュａ_ｉと近傍メッシュｂ_ｎとの距離に関する重みであり、距離が大きいほど小さな値とする。例えば、メッシュａ_ｉとｂ_ｎとの距離の逆数をｄ_ｉｎとすることができる。

以上のようにステップＳ７２で対応候補メッシュの適合度を計算した後、図４のステップＳ７３からステップＳ７７では、制御部１２は、上記で説明したステップＳ７３からステップＳ７７の処理と同様の処理を行い、図８のステップＳ１０の対応メッシュ選択処理を終了する。その後、ステップＳ８で、図２を参照して説明したステップＳ８の処理と同様に基準画像と検索対象画像との類似度が算出される。

以上で説明した実施形態の処理では、基準画像の各メッシュについて検索対象画像上の対応メッシュを選択する際に、基準画像の注目メッシュ及び注目メッシュの近傍メッシュの位置に対応する検索対象画像上の位置にあるメッシュの特徴量を考慮し、かつ、注目メッシュの変位方向と注目メッシュの近傍メッシュの変位方向との整合性を考慮する。したがって、例えば、図１０に示すように、基準画像（図１０（ａ））と検索対象画像（図１０（ｂ））とが同じ画像を表すが、画像データ上での位置がずれている場合に、本実施形態の処理によると、基準画像の各メッシュに対して、そのメッシュの近傍のメッシュ位置に対応する検索対象画像の位置にあるメッシュの特徴量が考慮されるので、基準画像の各メッシュと検索対象画像の各メッシュとの正しい対応関係が得られる。

また、上述の実施形態の処理によると、基準画像の各メッシュについて、特徴量の類似性が高く、かつ、基準画像の各メッシュの変位方向とその近傍のメッシュの変位方向との整合性が高くなるように、検索対象画像の対応メッシュが選択される。つまり、上述の実施形態の処理では、基準画像の各メッシュがその近傍のメッシュと同じ方向又は近い方向に変位するように、基準画像の各メッシュと検索対象画像の各メッシュとの対応関係が決定される。したがって、上述の実施形態の処理は、画像の局所領域内のメッシュ同士が同じ方向又は近い方向に変位するような画像の変動が生じている場合、例えば図１１に示すように、画像の縮小（図１１（ａ））又は回転（図１１（ｂ））が生じている場合に、基準画像の各メッシュと検索対象画像の各メッシュとの正しい対応関係を得るのに適している。

以上より、上述の実施形態の処理によると、例えば紙文書を複写機で複製して得られる画像において生じやすい、画像の位置ずれ、拡大縮小、及び回転などの変動に対してロバストな画像照合が可能となる。

図１２及び図１３を参照し、制御部１２が行う類似度算出処理の他の一例について説明する。

図１２は、制御部１２が行う処理の流れの他の一例を示すフローチャートである。図１２に示すフローチャートにおいて、図２に示すフローチャートと同様の処理には同様の符号を付している。

ステップＳ１の基準画像取得及びステップＳ２の検索対象画像取得の処理は、図２のフローチャートを参照して説明した処理と同様である。

ステップＳ２０で、制御部１２は、基準画像を現在よりも小さいメッシュにメッシュ分割する。例えば、現在の基準画像の各メッシュを、縦方向及び横方向の長さがそれぞれ現在の半分である４つのメッシュに分割する。このように分割すると、基準画像は２倍の解像度にメッシュ分割されることになる。

ステップＳ４では、制御部１２は、ステップＳ２０で分割された基準画像の各メッシュについて、図２を参照して説明したステップＳ４と同様の処理を行い、基準画像の特徴量を抽出する。

ステップＳ２１で、制御部１２は、検索対象画像に対してステップＳ２０と同様の処理を行い、検索対象画像を現在よりも小さいメッシュにメッシュ分割する。

ステップＳ６では、制御部１２は、ステップＳ２１で分割された検索対象画像の各メッシュについて、図２を参照して説明したステップＳ６と同様の処理を行い、検索対象画像の特徴量を抽出する。

ステップＳ２２の対応メッシュ選択処理では、前回ステップＳ２２の処理を行ったときに得られた情報を用いて、基準画像の各メッシュについて対応メッシュを選択する。ステップＳ２２の対応メッシュ選択処理では、図４に示すフローチャートと同様の処理を行うが、ステップＳ７１における対応候補メッシュの選択処理の内容が、図４から図７を参照して説明した上述の処理、及び図９を参照して説明した上述の処理と異なる。以下、ステップＳ２２の対応メッシュ選択処理において行われる、注目メッシュの対応候補メッシュの選択処理（図４のステップＳ７１）について説明する。

本例の対応候補メッシュ選択処理（図４のステップＳ７１）では、制御部１２は、前回のステップＳ２２の処理において選択された基準画像の各メッシュの対応メッシュの位置を参照して対応候補メッシュを選択する。

例えば図１３に示すように、１回目のステップＳ２２の処理において、注目メッシュａ_ｉ（ＭＳＨｘ_１１）に対応するメッシュとしてｙ_８（ＭＳＨｙ_２２）が選択されたとする。その後、ステップＳ２３の判定の結果、処理がステップＳ２０に戻り、ステップＳ２０及びステップＳ２１での処理によって、基準画像及び検索対象画像がそれぞれ２倍の解像度に分割されたとする。２回目のステップＳ２２の処理において、１回目のステップＳ２２の処理を行った際の注目メッシュａ_ｉを分割して得られた４つのメッシュのうち、左上のメッシュ（ＭＳＨｘ_１ａ１ａ）が新たな注目メッシュａ’_ｉとされたとする。２回目のステップＳ２２の処理において、この新たな注目メッシュａ’_ｉの対応候補メッシュとしては、ＭＳＨｙ_１ａ１ａを中心とする９個のメッシュではなく、１回目のステップＳ２２の処理において注目メッシュａ_ｉの対応メッシュとして選択されたｙ_８（ＭＳＨｙ_２２）を分割して得られた４つのメッシュの左上のメッシュＭＳＨｙ_２ａ２ａを中心とする９個のメッシュが選択される。

ステップＳ２２の処理を初めて行う場合は、ステップＳ７１の対応候補メッシュ選択処理において、制御部１２は、図４から図７を参照して説明した上述の処理、及び図９を参照して説明した処理と同様に、基準画像の注目メッシュａ_ｉの位置（横ｉ，縦ｊ）に対応する検索対象上の位置（横ｉ，縦ｊ）のメッシュを対応候補メッシュｙ_０とし、注目メッシュａ_ｉの近傍メッシュｂ_ｎ（ｎ＝１，…，Ｍ）に対応する検索対象画像のメッシュを対応候補メッシュｙ_ｎ（ｎ＝１，…，Ｍ）として選択する。

以上で説明したステップＳ７１の処理の後、図４のステップＳ７２からステップＳ７７では、既に上記で説明したステップＳ７２からステップＳ７７の処理と同様の処理を行い、図１２のステップＳ２２の処理を終了する。

ステップＳ２２の処理の後、ステップＳ２３で、基準画像が所定の解像度までメッシュ分割されたか否かを判定する。例えば、予め設定された回数だけ繰り返した場合に、基準画像が所定の解像度まで分割されたと判定する。又は、各メッシュの大きさが予め設定された大きさ以下である場合に、所定の解像度であると判定する。このように、各メッシュの大きさに基づいて判定を行う場合、判定基準となるメッシュの大きさは、処理対象となる画像の特性によって決定することができる。例えば、基準画像が紙文書を複写機で複製したり、スキャナで読み取ったりして得られる再生画像である場合、使用されるスキャナ、光学系、又は印刷機構などの誤差により、再生画像の印刷位置や拡大率に誤差が生じる。この印刷位置や拡大率の誤差により発生する変位量の最大値が既知である場合、この最大変位量に応じて判定基準となるメッシュの大きさを決定することが好適である。例えば、主走査、副走査方向の最大変位量がそれぞれδｈ、δｖである場合、判定基準となるメッシュの幅をδｈ以下、高さをδｖ以下とすることが好適である。

ステップＳ２３で、所定の解像度であると判定されたらステップＳ８へ進み、所定の解像度でないと判定されたらステップＳ２０に戻る。

ステップＳ８では、制御部１２は、図２を参照して説明したステップＳ８と同様の処理を行い、基準画像と検索対象画像との類似度を算出する。

図１２及び図１３を参照して説明した処理を行うと、基準画像及び検索対象画像に比較的大きな変位が生じている場合でも基準画像の各メッシュと検索対象画像の各メッシュとの対応付けを適切に行うことができる。

例えば、図１４Ａに示すように、メッシュ分割数が横８×縦８になるように基準画像及び検索対象画像をメッシュ分割した場合において、基準画像のメッシュａ_ｉ（＝ＭＳＨｘ_３３）に対応する検索対象画像のメッシュがＭＳＨｙ_５４であるとする。この図１４Ａに例示する画像を処理する場合、図２のフローチャートに従って基準画像及び検索対象画像のメッシュ分割（ステップＳ３，Ｓ５）と対応メッシュ選択処理（ステップＳ７）とをそれぞれ一度だけ行って、基準画像のメッシュａ_ｉ（＝ＭＳＨｘ_３３）に対応する検索対象画像のメッシュＭＳＨｙ_５４を正しく選択するためには、注目メッシュａ_ｉの近傍メッシュｂ_ｎとして、図１４Ａの実線太枠中の２４個のメッシュ（ＭＳＨｘ_ｉｊ（ｉ，ｊ＝１，２，…，５））を選択し、基準画像上の注目メッシュａ_ｉ及び近傍メッシュｂ_ｎのそれぞれの位置に対応する検索対象画像上の位置にある２５個の対応候補メッシュｙ_ｎ（ｎ＝０，１，…，２４）について、その適合度を計算する必要がある。例えば図５を参照して説明した場合のように、注目メッシュａ_ｉの近傍メッシュｂ_ｎとして、注目メッシュａ_ｉの周囲８個のメッシュ（図１４Ａの点線太枠内のメッシュ）を選択すると、正しい対応メッシュＭＳＨｙ_５４が対応候補メッシュｙ_ｎに含まれない。

図１４Ｂを参照し、図１４Ａに例示した画像と同じ画像について、図１２及び図１３を参照して説明した処理に従って基準画像の各メッシュと検索対象画像の各メッシュとの対応付けを行う場合の処理について説明する。例えば、１回目の図１２のステップＳ２０，Ｓ２１において、図１４Ｂ（ａ）のように、メッシュ分割数が横４×縦４になるように基準画像及び検索対象画像がメッシュ分割されたとする。次に、ＭＳＨｘ_３３の領域を含む注目メッシュＡ_ｉについて、注目メッシュＡ_ｉの周囲８個のメッシュを近傍メッシュＢ_ｎとしてステップＳ２２の対応メッシュ選択処理が行われ、近傍メッシュＢ_８に対応する検索対象画像のメッシュが注目メッシュＡ_ｉの対応メッシュとして選択されたとする。ステップＳ２３の判定の後に行われる２回目のステップＳ２０，Ｓ２１の処理では、図１４Ｂ（ｂ）に示すように、基準画像及び検索対象画像の図１４Ｂ（ａ）に示す各メッシュを４個のメッシュに分割して、それぞれの画像のメッシュ分割数を図１４Ａと同じ横８×縦８とする。その後のステップＳ２２の対応メッシュ選択処理において、基準画像の注目メッシュａ_ｉ（＝ＭＳＨｘ_３３）について検索対象画像の対応候補メッシュを選択する際には、１回目のステップＳ２２の処理（図１４Ｂ（ａ））において得られたメッシュの対応関係を利用する。１回目のステップＳ２２の処理では、上述の通り、注目メッシュＡ_ｉの対応メッシュとして、基準画像上の近傍メッシュＢ_８の位置に対応する検索対象画像上の位置にあるメッシュ（ＭＳＨｙ_ｉｊ（ｉ，ｊ＝４，５））が選択された。この関係を利用して、図１４Ｂ（ｂ）に示すように、基準画像上の注目メッシュａ_ｉ（＝ＭＳＨｘ_３３）の位置に対応する検索対象画像上の位置にある対応候補メッシュｙ_０として、ＭＳＨｙ_３３ではなくＭＳＨｙ_５５を選択し、注目メッシュａ_ｉの周囲８個の近傍メッシュにそれぞれ対応する対応候補メッシュｙ_ｎとして、ＭＳＨｙ_５５の周囲８個のメッシュを選択する。このように選択された対応候補メッシュｙ_ｎの適合度を計算すると、基準画像のメッシュＭＳＨｙ_３３の正しい対応メッシュＭＳＨｙ_５４を選択できる。

図１２及び図１４Ｂを参照して説明した処理の例によると、１回目のステップＳ２２の対応メッシュ選択処理において、基準画像の注目メッシュＡ_ｉ及び近傍メッシュＢ_ｎ（ｎ＝１，２，…，８）（図１４Ｂ（ａ））に対応する検索対象画像上の位置にある９個の対応候補メッシュの適合度を計算し、２回目のステップＳ２２の処理において、９個の対応候補メッシュｙ_ｎ（ｎ＝０，１，…，８）（図１４Ｂ（ｂ））の適合度を計算することで、つまり、合計で１８個の対応候補メッシュの適合度を計算することで、基準画像のメッシュＭＳＨｘ_３３の正しい対応メッシュＭＳＨｙ_５４を選択できる。したがって、図１２のフローチャートに従う処理によると、２５個の対応候補メッシュの適合度を計算する図２及び図１４Ａを参照して説明した処理よりも、少ない計算量で基準画像のメッシュＭＳＨｘ_３３の対応メッシュを選択できる。

以上のように、図１２及び図１３を参照して説明した処理によると、画像に大きな変位が生じている場合であっても、適切に、かつ高速に基準画像の各メッシュと検索対象画像の各メッシュとの対応関係を得ることができる。

なお、以上で説明した実施形態の制御部１２の処理では、図２のステップＳ７、図８のステップＳ１０、及び図１２のステップＳ２２の対応メッシュ選択処理において、いずれも、図４のフローチャートを参照し、弛緩法に従って基準画像の各メッシュについて検索画像上の対応メッシュを選択する方法について説明した。注目メッシュ及び対応候補メッシュの特徴量ベクトルの類似性と、注目メッシュの近傍のメッシュの変位方向に基づく変位方向の整合性と、の両方を考慮して注目メッシュの対応メッシュを選択できるような方法であれば、自己組織化マップ（Self Organizing Map）や動的計画法マッチングなど、弛緩法以外の方法を適用することもできる。

本発明の１つの実施形態の画像処理装置の構成の一例を示す図である。 本発明の１つの実施形態で行われる画像の類似度算出処理の一例を示すフローチャートである。 本発明の１つの実施形態で行われる処理において、画像を複数の領域に分割した様子の一例を示す図である。 本発明の１つの実施形態で行われる対応メッシュ選択処理の流れの一例を示すフローチャートである。 図４に示すフローチャートによる処理において、基準画像及び検索対象画像の各メッシュの関係の一例を表す説明図である。 本発明の１つの実施形態で行われる処理において、基準画像のメッシュの変位方向の一例を示す説明図である。 図４に示すフローチャートによる処理において、基準画像及び検索対象画像の各メッシュの関係の他の一例を表す説明図である。 本発明の１つの実施形態で行われる画像の類似度算出処理の他の一例を示すフローチャートである。 図８に示すフローチャートによる処理において、基準画像及び検索対象画像のメッシュの関係の一例を表す説明図である。 本発明の１つの実施形態で行われる画像の類似度算出処理において処理される画像の一例を示す図である。 本発明の１つの実施形態で行われる画像の類似度算出処理において処理される画像の一例を示す図である。 本発明の１つの実施形態で行われる類似度算出処理の他の一例を示すフローチャートである。 図１２に示すフローチャートによる処理において、基準画像及び検索対象画像の各メッシュの関係の一例を表す説明図である。 本発明の１つの実施形態で行われる画像の類似度算出処理において処理される画像の一例を示す図である。 図１２に示すフローチャートによる処理において、画像のメッシュ分割の例を示す図である。

符号の説明

１０ 画像処理装置、１２ 制御部、１４ 記憶部、１６ 画像入力部、１８ 標準入力部、２０ 出力部、２２ 通信部、２４ バス。

Claims (6)

1. 基準画像と検索対象画像とを照合する画像処理装置であって、
   前記基準画像を複数の領域に分割する領域分割手段と、
   前記基準画像の各領域に対応する前記検索対象画像の領域を対応領域として選択する対応領域選択手段であって、
   前記基準画像の各領域を注目領域ａ _ｉ とし、各注目領域ａ _ｉ について、前記基準画像において当該注目領域ａ _ｉ の（ｉは１から前記基準画像上の前記複数の領域の領域数までの整数）周辺に位置する各近傍領域ｂ _ｎ （ｎは１からＭまでの整数。Ｍは前記注目領域に対する前記近傍領域の数）及び当該注目領域ａ _ｉ の位置に対応する前記検査対象画像上の各領域を対応候補領域ｙ _ｊ （ｊは０からＭまでの整数。ｊ＝０は、対応候補領域ｙ _ｊ が当該注目領域ａ _ｉ の位置に対応する前記検査対象画像上の領域であることを示す）とし、それら対応候補領域ｙ _ｊ のそれぞれについて、
   前記基準画像上の前記複数の領域のうちのある領域ａ _ｓ （ｓは１から前記基準画像上の前記複数の領域の領域数までの整数）が前記検査対象画像上の当該対応候補領域ｙ _ｔ （ｔは０からＭまでの整数）に変位する場合の変位方向を単位ベクトルλ _ｔ で表し、当該領域ａ _ｓ の変位方向がλ _ｔ である確率、すなわち当該領域ａ _ｓ の対応領域として当該対応候補領域ｙ _ｔ が正解である確率をｐ _ｓ ^（ｒ） （λ _ｔ ）と表す場合に、
   当該注目領域ａ _ｉ から抽出された特徴量ｖ _ｉ と、その対応候補領域ｙ _ｊ から抽出された特徴量ｗ _ｊ と、の相関係数ｃｏｒｒ（ｖ _ｉ ，ｗ _ｊ ）を、特徴量の適合度として求め、前記基準画像上の当該注目領域ａ _ｉ から前記検索対象画像上のその対応候補領域ｙ _ｊ への変位方向λ _ｊ と、前記基準画像において当該注目領域ａ _ｉ についての前記各近傍領域ｂ _ｎ それぞれの変位方向λ _ｋ （ｋは０からＭまでの整数）と、の内積λ _ｊ ・λ _ｋ を、変位方向の整合度として求め、求めた前記特徴量の適合度ｃｏｒｒ（ｖ _ｉ ，ｗ _ｊ ）と前記変位方向の整合度λ _ｊ ・λ _ｋ とから、次式（１）、
   

   

   に従って適合関数値ｃ _ｉｎ （ｊ，ｋ）を求める適合関数値計算処理（ここで、αは所定の調整パラメータ）と、
   次式（２）又は（３）又は（４）、
   

   

   

   

   により、前記注目領域ａ _ｉ の変位方向を表すベクトルがλ _ｊ である適合度ｑ _ｉ ^（ｒ） （λ _ｊ ）を求める適合度計算処理（ここで、式（３）及び（４）におけるｄ _ｉｎ は注目領域ａ _ｉ と近傍領域ｂ _ｎ との距離が大きいほど小さい値となる重みであり、式（４）におけるＢは前記各近傍領域ｂ _ｎ に付される番号ｎの集合である）と、
   次式（５）、
   

   

   により当該注目領域ａ _ｉ の変位方向がλ _ｊ である確率の更新値ｐ _ｉ ^{（ｒ＋１）} （λ _ｊ ）を求める確率更新処理と、
   を実行し、
   ここでｒは所定の初期確率ｐ _ｉ ^（０） （λ _ｊ ）から開始した前記適合関数値計算処理及び前記適合度計算処理及び前記確率更新処理の反復の回数であり、
   前記反復の結果、前記基準画像上の各注目領域ａ _ｉ について前記確率更新処理により求めた前記確率の更新値ｐ _ｉ ^{（ｒ＋１）} （λ _ｊ ）が所定の収束条件を満たした場合に、前記各注目領域ａ _ｉ について、確率ｐ _ｉ ^{（ｒ＋１）} （λ _ｊ ）が最大になる変位方向λ _ｊ に対応する対象候補領域ｙ _ｊ を、当該注目領域ａ _ｉ に対応する対象領域として選択する対応領域選択手段と、
   前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する対応領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段と、
   を備えることを特徴とする画像処理装置。
2. 請求項１に記載の画像処理装置であって、
   前記領域分割手段は、さらに、前記検索対象画像を複数の領域に分割し、
   前記対応領域選択手段は、前記領域分割手段で分割された前記検索対象画像の複数の領域から、前記複数の対応候補領域を選択することを特徴とする画像処理装置。
3. 請求項１又は２に記載の画像処理装置において、
   前記領域分割手段は、前記基準画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下になるように、前記基準画像を複数の領域に分割することを特徴とする画像処理装置。
4. 請求項２に記載の画像処理装置において、さらに、
   それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像を、それぞれ、前記基準画像及び前記検索対象画像の各領域よりも小さい領域にさらに分割する多重領域分割手段を備え、
   所定の条件を満たすまで、前記多重領域分割手段における処理と、前記多重領域分割手段において分割された前記基準画像及び前記検索対象画像を処理対象とする前記対応領域選択手段における処理と、を反復して行うことを特徴とする画像処理装置。
5. 請求項４に記載の画像処理装置において、
   前記所定の条件は、それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下であることを特徴とする画像処理装置。
6. 基準画像と検索対象画像とを照合する画像処理装置としてコンピュータを機能させるプログラムであって、
   前記基準画像を複数の領域に分割する領域分割手段、
   前記基準画像の各領域に対応する前記検索対象画像の領域を対応領域として選択する対応領域選択手段であって、
   前記基準画像の各領域を注目領域ａ _ｉ とし、各注目領域ａ _ｉ について、前記基準画像において当該注目領域ａ _ｉ の（ｉは１から前記基準画像上の前記複数の領域の領域数までの整数）周辺に位置する各近傍領域ｂ _ｎ （ｎは１からＭまでの整数。Ｍは前記注目領域に対する前記近傍領域の数）及び当該注目領域ａ _ｉ の位置に対応する前記検査対象画像上の各領域を対応候補領域ｙ _ｊ （ｊは０からＭまでの整数。ｊ＝０は、対応候補領域ｙ _ｊ が当該注目領域ａ _ｉ の位置に対応する前記検査対象画像上の領域であることを示す）とし、それら対応候補領域ｙ _ｊ のそれぞれについて、
   前記基準画像上の前記複数の領域のうちのある領域ａ _ｓ （ｓは１から前記基準画像上の前記複数の領域の領域数までの整数）が前記検査対象画像上の当該対応候補領域ｙ _ｔ （ｔは０からＭまでの整数）に変位する場合の変位方向を単位ベクトルλ _ｔ で表し、当該領域ａ _ｓ の変位方向がλ _ｔ である確率、すなわち当該領域ａ _ｓ の対応領域として当該対応候補領域ｙ _ｔ が正解である確率をｐ _ｓ ^（ｒ） （λ _ｔ ）と表す場合に、
   当該注目領域ａ _ｉ から抽出された特徴量ｖ _ｉ と、その対応候補領域ｙ _ｊ から抽出された特徴量ｗ _ｊ と、の相関係数ｃｏｒｒ（ｖ _ｉ ，ｗ _ｊ ）を、特徴量の適合度として求め、前記基準画像上の当該注目領域ａ _ｉ から前記検索対象画像上のその対応候補領域ｙ _ｊ への変位方向λ _ｊ と、前記基準画像において当該注目領域ａ _ｉ についての前記各近傍領域ｂ _ｎ それぞれの変位方向λ _ｋ （ｋは０からＭまでの整数）と、の内積λ _ｊ ・λ _ｋ を、変位方向の整合度として求め、求めた前記特徴量の適合度ｃｏｒｒ（ｖ _ｉ ，ｗ _ｊ ）と前記変位方向の整合度λ _ｊ ・λ _ｋ とから、次式（１）、
   

   

   に従って適合関数値ｃ _ｉｎ （ｊ，ｋ）を求める適合関数値計算処理（ここで、αは所定の調整パラメータである）と、
   次式（２）又は（３）又は（４）、
   

   

   

   

   により、前記注目領域ａ _ｉ の変位方向を表すベクトルがλ _ｊ である適合度ｑ _ｉ ^（ｒ） （λ _ｊ ）を求める適合度計算処理（ここで、式（３）及び（４）におけるｄ _ｉｎ は注目領域ａ _ｉ と近傍領域ｂ _ｎ との距離が大きいほど小さい値となる重みであり、式（４）におけるＢは前記各近傍領域ｂ _ｎ に付される番号ｎの集合である）と、
   次式（５）、
   

   

   により当該注目領域ａ _ｉ の変位方向がλ _ｊ である確率の更新値ｐ _ｉ ^{（ｒ＋１）} （λ _ｊ ）を求める確率更新処理と、
   を実行し、
   ここでｒは所定の初期確率ｐ _ｉ ^（０） （λ _ｊ ）から開始した前記適合関数値計算処理及び前記適合度計算処理及び前記確率更新処理の反復の回数であり、
   前記反復の結果、前記基準画像上の各注目領域ａ _ｉ について前記確率更新処理により求めた前記確率の更新値ｐ _ｉ ^{（ｒ＋１）} （λ _ｊ ）が所定の収束条件を満たした場合に、前記各注目領域ａ _ｉ について、確率ｐ _ｉ ^{（ｒ＋１）} （λ _ｊ ）が最大になる変位方向λ _ｊ に対応する対象候補領域ｙ _ｊ を、当該注目領域ａ _ｉ に対応する対象領域として選択する対応領域選択手段、
   前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する対応領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段、
   として前記コンピュータを機能させることを特徴とする画像処理プログラム。

Images