(57)【要約】【課題】２つの画像を精度良く照合できる画像処理装置及び画像処理プログラムを提供する。【解決手段】画像処理装置は、基準画像及び検索対象画像を取得し（ステップＳ１，Ｓ２）、基準画像を複数のメッシュに分割し（ステップＳ３）、基準画像から特徴量を抽出する（ステップＳ４）。画像処理装置は、基準画像の各メッシュについて、特徴量の適合度と変位方向の整合度とに基づいて、検索対象画像上の対応メッシュを選択する（ステップＳ７）。【選択図】図２
2008134791.tif 000002
【特許請求の範囲】
【請求項１】
基準画像と検索対象画像とを照合する画像処理装置であって、
前記基準画像を複数の領域に分割する領域分割手段と、
前記基準画像の各領域に対応する前記検索対象画像の領域を選択する対応領域選択手段であって、
前記基準画像の各領域を注目領域とし、その注目領域に対応する前記検索対象画像の領域の候補である複数の対応候補領域のそれぞれについて、
その注目領域から抽出された特徴量と、その対応候補領域から抽出された特徴量と、に基づいて特徴量の適合度を求め、
前記基準画像上のその注目領域の位置から、前記検索対象画像上のその対応候補領域の位置に相当する前記基準画像上の位置への変位方向と、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向と、に基づいて変位方向の整合度を求め、
前記対応候補領域のそれぞれについて求められた、前記特徴量の適合度及び前記変位方向の整合度に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択する対応領域選択手段と、
前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段と、
を備えることを特徴とする画像処理装置。
【請求項２】
請求項１に記載の画像処理装置であって、
前記領域分割手段は、さらに、前記検索対象画像を複数の領域に分割し、
前記対応領域選択手段は、前記領域分割手段で分割された前記検索対象画像の複数の領域から、前記複数の対応候補領域を選択することを特徴とする画像処理装置。
【請求項３】
請求項１又は２に記載の画像処理装置において、
前記領域分割手段は、前記基準画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下になるように、前記基準画像を複数の領域に分割することを特徴とする画像処理装置。
【請求項４】
請求項２に記載の画像処理装置において、さらに、
それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像を、それぞれ、前記基準画像及び前記検索対象画像の各領域よりも小さい領域にさらに分割する多重領域分割手段を備え、
所定の条件を満たすまで、前記多重領域分割手段における処理と、前記多重領域分割手段において分割された前記基準画像及び前記検索対象画像を処理対象とする前記対応領域選択手段における処理と、を反復して行うことを特徴とする画像処理装置。
【請求項５】
請求項４に記載の画像処理装置において、
前記所定の条件は、それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下であることを特徴とする画像処理装置。
【請求項６】
請求項１から５のいずれか１項に記載の画像処理装置において、
前記変位方向の整合度は、その注目領域の前記基準画像上の位置から、その対応候補領域の前記検索対象画像上の位置に相当する前記基準画像上の位置への変位方向を表すベクトルと、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向を表すベクトルと、の内積に基づいて求められることを特徴とする画像処理装置。
【請求項７】
請求項１から６のいずれか１項に記載の画像処理装置において、
前記対応領域選択手段は、
前記対応候補領域のそれぞれについて、前記特徴量の適合度及び前記変位方向の整合度に基づく評価関数を用いて評価値を求め、
前記対応候補領域のそれぞれについて求められた評価値と、前記評価関数と、を用いて、前記対応候補領域のそれぞれについて新たな評価値を求める処理を、所定の条件を満たすまで反復して行った後、前記対応候補領域のそれぞれについて求められた評価値に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択することを特徴とする画像処理装置。
【請求項８】
請求項７に記載の画像処理装置において、
前記対応領域選択手段は、弛緩法（relaxation method）に従って、
前記対応候補領域のそれぞれについて、前記特徴量の適合度及び前記変位方向の整合度に基づく評価関数を用いて評価値を求め、
前記対応候補領域のそれぞれについて求められた評価値と、前記評価関数と、を用いて、前記対応候補領域のそれぞれについて新たな評価値を求める処理を、所定の条件を満たすまで反復して行うことを特徴とする画像処理装置。
【請求項９】
基準画像と検索対象画像とを照合する画像処理装置としてコンピュータを機能させるプログラムであって、
前記基準画像を複数の領域に分割する領域分割手段、
前記基準画像の各領域に対応する前記検索対象画像の領域を選択する対応領域選択手段であって、
前記基準画像の各領域を注目領域とし、その注目領域に対応する前記検索対象画像の領域の候補である複数の対応候補領域のそれぞれについて、
その注目領域から抽出された特徴量と、その対応候補領域から抽出された特徴量と、に基づいて、特徴量の適合度を求め、
前記基準画像上のその注目領域の位置から、前記検索対象画像上のその対応候補領域の位置に相当する前記基準画像上の位置への変位方向と、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向と、に基づいて、変位方向の整合度を求め、
前記対応候補領域のそれぞれについて求められた、前記特徴量の適合度及び前記変位方向の整合度に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択する対応領域選択手段、
前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段、
として前記コンピュータを機能させることを特徴とする画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２つの画像を照合する画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
検索対象の画像データベースから、基準画像と類似する画像を検索する場合などに用いるために、２つの画像の照合を行う様々な技術が開発されている。画像の照合を行う一般的な技術として、画像から物理的な特徴量を抽出し、抽出された画像の特徴量に基づいて２つの画像の類似性を判断する技術がある。このような技術において、例えば、画像の色の特徴や、画像に表示される対象の輪郭線などが特徴量として抽出される。１つの画像からＮ個の特徴量が抽出された場合、抽出された特徴量はＮ次元の特徴量ベクトルとして表すことができる。一般に、画像から抽出された特徴量に基づいて画像の類似度を判断する技術では、基準画像の特徴量ベクトルと検索対象の画像の特徴量ベクトルとの間のユークリッド距離が小さいほど、基準画像と検索対象の画像とが類似していると判断する。
【０００３】
画像から特徴量を抽出する方法の１つとして、画像内の特徴点を選定し、選定した特徴点における特徴量を抽出する方法がある。この場合、照合する２つの画像内の対応する特徴点から抽出される特徴量の類似度に基づいて画像の類似度を判断する。特許文献１及び特許文献２には、画像内の特徴点における特徴量を用いて画像の類似度を判断する技術において、画像の位置ずれや歪みなどの変形があっても適切な画像の照合を可能とするための技術が開示されている。
【０００４】
特許文献１には、２つのパターン画像内の特徴点を選定し、選定した特徴点の特徴量を抽出して、被照合パターン画像内の各特徴点の特徴量と、その特徴点に対応する基準パターン画像内の特徴点の特徴量と、の類似度が最大になるように、被照合パターン画像内の各特徴点を水平方向及び垂直方向に変位させる技術が開示されている。特許文献１に記載の技術では、被照合パターン画像内の各特徴点の特徴量に加えて、その特徴点の水平方向及び垂直方向の近傍点の特徴量を求め、その特徴点に対応する基準パターン画像内の特徴点の特徴量との類似度が最大となる特徴量を有する近傍点を新たな特徴点とする。
【０００５】
特許文献２には、線図形のパターン照合を行う技術において、検査図形及びモデル図形に生じている位置ずれや歪みなどの変形について、検査図形の特徴点とモデル図形の特徴点との対応関係を基に変形の種類を推定し、推定した変形の種類に基づいて検査図形を補正し、検査図形とモデル図形との類似度を判断する技術が開示されている。特許文献２に記載の技術では、線図形内の線の端点、分岐点、及び交差点などをその線図形の特徴点として選択し、選択した特徴点から抽出される特徴量に基づいて検査図形の特徴点とモデル図形の特徴点との対応づけを行う。
【０００６】
【特許文献１】特開２００１−１３４７５７号公報
【特許文献２】特開２００２−２９８１４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に記載の技術では、特徴点の水平方向及び垂直方向の近傍点の特徴量を逐次的に評価するため、例えば特徴点の位置が垂直方向にずれた状態で水平方向の近傍点の特徴量を評価しても、正しい評価結果が得られるとは限らない。
【０００８】
また、特許文献２に記載の技術は、線の端点、分岐点、交差点などの特徴点の対応関係に基づいて画像の照合を行うので、線図形など、特徴点の選定が容易な画像が照合対象として適している。例えば濃淡画像のように画像中の図形の線の端点などが明確でない画像や、例えば紙文書を複写機で複製して得られる画像のようにノイズや濃度変化、コントラスト変化などによって局所的な特徴量が大きく変動する画像などについては、画像の特徴点の適切な選定が困難であるため、特許文献２に記載の技術を適用するのは困難である。
【０００９】
本発明の目的は、２つの画像を精度良く照合できる画像処理装置及び画像処理プログラムを提供することである。
【課題を解決するための手段】
【００１０】
本発明に係る画像処理装置は、基準画像と検索対象画像とを照合する画像処理装置であって、前記基準画像を複数の領域に分割する領域分割手段と、前記基準画像の各領域に対応する前記検索対象画像の領域を選択する対応領域選択手段であって、前記基準画像の各領域を注目領域とし、その注目領域に対応する前記検索対象画像の領域の候補である複数の対応候補領域のそれぞれについて、その注目領域から抽出された特徴量と、その対応候補領域から抽出された特徴量と、に基づいて特徴量の適合度を求め、前記基準画像上のその注目領域の位置から、前記検索対象画像上のその対応候補領域の位置に相当する前記基準画像上の位置への変位方向と、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向と、に基づいて変位方向の整合度を求め、前記対応候補領域のそれぞれについて求められた、前記特徴量の適合度及び前記変位方向の整合度に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択する対応領域選択手段と、前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段と、を備えることを特徴とする。
【００１１】
本発明に係る画像処理装置において、前記領域分割手段は、さらに、前記検索対象画像を複数の領域に分割し、前記対応領域選択手段は、前記領域分割手段で分割された前記検索対象画像の複数の領域から、前記複数の対応候補領域を選択することが好ましい。
【００１２】
また、前記領域分割手段は、前記基準画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下になるように、前記基準画像を複数の領域に分割するものとしても良い。
【００１３】
本発明に係る情報処理装置において、さらに、それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像を、それぞれ、前記基準画像及び前記検索対象画像の各領域よりも小さい領域にさらに分割する多重領域分割手段を備え、所定の条件を満たすまで、前記多重領域分割手段における処理と、前記多重領域分割手段において分割された前記基準画像及び前記検索対象画像を処理対象とする前記対応領域選択手段における処理と、を反復して行うことが好ましい。また、前記所定の条件は、それぞれ複数の領域に分割された前記基準画像及び前記検索対象画像の各領域の縦方向及び横方向の大きさが、それぞれ、前記基準画像の生成時に生じる画像位置についての誤差に基づいて得られる縦方向及び横方向の予想変位の大きさ以下であることが好ましい。
【００１４】
本発明に係る画像処理装置において、前記変位方向の整合度は、その注目領域の前記基準画像上の位置から、その対応候補領域の前記検索対象画像上の位置に相当する前記基準画像上の位置への変位方向を表すベクトルと、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向を表すベクトルと、の内積に基づいて求められることが好ましい。
【００１５】
本発明に係る画像処理装置において、前記対応領域選択手段は、前記対応候補領域のそれぞれについて、前記特徴量の適合度及び前記変位方向の整合度に基づく評価関数を用いて評価値を求め、前記対応候補領域のそれぞれについて求められた評価値と、前記評価関数と、を用いて、前記対応候補領域のそれぞれについて新たな評価値を求める処理を、所定の条件を満たすまで反復して行った後、前記対応候補領域のそれぞれについて求められた評価値に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択することが好ましい。
【００１６】
また、前記対応領域選択手段は、弛緩法（relaxation method）に従って、前記対応候補領域のそれぞれについて、前記特徴量の適合度及び前記変位方向の整合度に基づく評価関数を用いて評価値を求め、前記対応候補領域のそれぞれについて求められた評価値と、前記評価関数と、を用いて、前記対応候補領域のそれぞれについて新たな評価値を求める処理を、所定の条件を満たすまで反復して行うことが好ましい。
【００１７】
本発明に係る画像処理プログラムは、基準画像と検索対象画像とを照合する画像処理装置としてコンピュータを機能させるプログラムであって、前記基準画像を複数の領域に分割する領域分割手段、前記基準画像の各領域に対応する前記検索対象画像の領域を選択する対応領域選択手段であって、前記基準画像の各領域を注目領域とし、その注目領域に対応する前記検索対象画像の領域の候補である複数の対応候補領域のそれぞれについて、その注目領域から抽出された特徴量と、その対応候補領域から抽出された特徴量と、に基づいて、特徴量の適合度を求め、前記基準画像上のその注目領域の位置から、前記検索対象画像上のその対応候補領域の位置に相当する前記基準画像上の位置への変位方向と、前記基準画像においてその注目領域に隣接する領域を含む複数の周辺領域それぞれの変位方向と、に基づいて、変位方向の整合度を求め、前記対応候補領域のそれぞれについて求められた、前記特徴量の適合度及び前記変位方向の整合度に基づいて、その注目領域に対応する領域として前記対応候補領域のうちの１つを選択する対応領域選択手段、前記基準画像の各領域から抽出された特徴量と、前記対応領域選択手段において前記基準画像のその領域に対応する領域として選択された前記検索対象画像の領域から抽出された特徴量と、の類似度に基づいて、前記基準画像と前記検索対象画像との類似度を算出する類似度算出手段、として前記コンピュータを機能させることを特徴とする。
【発明の効果】
【００１８】
請求項１及び９に係る発明によると、基準画像と検索対象画像とを精度良く照合することができる。
【００１９】
請求項２に係る発明によると、基準画像と検索対象画像とを精度良く、かつ容易に照合することができる。
【００２０】
請求項３に係る発明によると、基準画像生成時の画像の幾何学的誤差に応じて適切に基準画像と検索対象画像とを照合できる。
【００２１】
請求項４に係る発明によると、基準画像及び検索対象画像のいずれか一方又は両方に大きな幾何学的変動がある場合でも、高速に基準画像と検索対象画像とを照合できる。
【００２２】
請求項５に係る発明によると、基準画像生成時の画像の幾何学的誤差に応じて適切に基準画像と検索対象画像とを照合できる。
【００２３】
請求項６に係る発明によると、基準画像の注目領域の変位方向の整合度を容易に求めることができる。
【００２４】
請求項７及び８に係る発明によると、基準画像と検索対象画像とを精度良く、かつ容易に照合できる。
【発明を実施するための最良の形態】
【００２５】
以下に、本発明の実施の形態を、図面を用いて詳細に説明する。
【００２６】
図１は、本発明の１つの実施形態の画像処理装置の構成の一例を示す図である。画像処理装置１０は、制御部１２、記憶部１４、画像入力部１６、標準入力部１８、出力部２０、及び通信部２２を備える。制御部１２、記憶部１４、画像入力部１６、標準入力部１８、出力部２０、及び通信部２２は、バス２４を介して相互に接続される。
【００２７】
制御部１２は、記憶部１４に記憶された画像処理プログラムを読み出して実行し、画像の照合に関する後述の処理を行う。制御部１２は、例えば一般的なコンピュータのＣＰＵ（中央演算装置：Central Processing Unit）などの演算装置によって実現できる。
【００２８】
記憶部１４は、ハードディスクやＣＤ、ＤＶＤなどの記憶媒体であり、画像処理装置１０の処理対象となる画像データや、制御部１２が行う処理の流れを記述したプログラムなどを記憶することができる。
【００２９】
画像入力部１６は、画像処理装置１０で処理対象となる画像データの入力を受け付ける。例えば、画像入力部１６は、画像を所定間隔ごとにサンプリングし、画素ごとに色相、輝度、又は明度などの値を有するデジタル画像データとして読み込む。画像入力部１６によって読み込まれた画像データは、記憶部１４に記憶させることができる。画像入力部１６は、スキャナ、デジタルカメラ又はデジタルビデオなどの一般的な画像入力装置を用いて実現できる。
【００３０】
標準入力部１８は、キーボード、マウスなどの入力装置であって、制御部１２で行われる処理において必要な指示など、ユーザからの入力を受け付ける。
【００３１】
出力部２０は、例えばＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどの表示装置であって、処理対象の画像の内容や、制御部１２における処理の結果などを表示する。
【００３２】
通信部２２は、例えばインターネットなどの通信手段（図示しない）を介して画像処理装置１０に接続された図示しないサーバ、他のコンピュータ、又はその他の機器と、画像処理装置１０と、の間の通信を行うためのインターフェースである。画像処理装置１０は、通信部２２を介して処理対象の画像データを取得することができる。
【００３３】
図２は、制御部１２が行う画像の類似度算出処理の一例を示すフローチャートである。図２に示す処理は、ある基準画像と検索対象の画像との類似度を算出する処理である。例えば、記憶部１４に記憶された画像データベースの中から、ユーザが指定した基準画像と最も類似する画像を検索する場合に、画像データベース中の画像のそれぞれについて図２に示す処理を行うことで基準画像との類似度を算出し、画像データベース中の画像のうち基準画像との類似度が最大である画像を、基準画像に最も類似する画像として抽出することができる。
【００３４】
ステップＳ１で、制御部１２は、画像照合の基準となる基準画像を取得する。基準画像の画像データは、画像入力部１６又は通信部２２を介して取得できる。制御部１２は、例えばユーザの指示などに応じて、記憶部１４に記憶された画像の１つを基準画像として取得することもある。
【００３５】
次に、ステップＳ２で、制御部１２は、基準画像との類似度を算出する検索対象の画像を取得する。検索対象画像は、記憶部１４に記憶された画像データベースから取得しても良いし、画像入力部１６又は通信部２２を介して取得しても良い。
【００３６】
ステップＳ３で、基準画像を複数の領域（メッシュ）に分割する。例えば、図３のように、基準画像を矩形のメッシュに分割する。各メッシュの大きさは均等であっても良いし、不均等であっても良い。また、メッシュの形状は、閉曲線で囲まれる任意の形状とすることができる。例えば、矩形、円形、又は多角形とすることができる。
【００３７】
各メッシュの大きさは、処理対象となる画像の特性によって決定することができる。例えば、基準画像が紙文書を複写機で複製したり、スキャナで読み取ったりして得られる再生画像である場合、使用されるスキャナ、光学系、又は印刷機構などの誤差により、再生画像の印刷位置や拡大率に誤差が生じる。この印刷位置や拡大率の誤差により発生する変位量の最大値が既知である場合、この最大変位量に応じて各メッシュの大きさを決定することが好適である。例えば、主走査、副走査方向の最大変位量がそれぞれδｈ、δｖである場合、各メッシュの幅をδｈ以下、高さをδｖ以下とすることが好適である。
【００３８】
以下の説明では、図３に示すように、画像データを横１０×縦１０＝１００個の均等な矩形メッシュとして分割したものとする。このとき、画像データが横５００画素×縦５００画素であったならば、１つのメッシュには横５０画素×縦５０画素が含まれることになる。
【００３９】
ステップＳ４で、制御部１２は、ステップＳ３で分割された基準画像の各メッシュについて特徴量を抽出する。以下の説明では、各メッシュの平均色及びエッジ画素量を特徴量として抽出するものとする。しかし、以下の説明は一例であり、他の物理量を特徴量として抽出しても良い。
【００４０】
各メッシュの平均色は、各メッシュに含まれる画素毎の色の成分をメッシュ全体について平均することによって算出することができる。例えば、各画素が赤、緑及び青（ＲＧＢ）の各色成分により表現され、各色成分が数値化されている場合、メッシュに含まれる全画素のＲ成分、Ｇ成分及びＢ成分の色成分ごとに加算し、その合計値を画素数で割ることによって、そのメッシュの平均色の各色成分を算出する。画像データが白黒である場合には、各画素をＲＧＢの色空間に変換した後に平均色を計算することができる。例えば、画素が白の場合にはＲＧＢ＝（２５５，２５５，２５５）、黒の場合にはＲＧＢ＝（０，０，０）と変換した後に、メッシュ毎の平均色を算出する。ここでは、画素の色データがＲＧＢ色空間で表現されている場合を例示したが、これに限定されるものではない。画素の色データがＹＵＶ色空間、ＹＭＣＫ色空間などの他の色空間で表現されている場合も、各色成分の平均値を算出することによって平均色を算出することができる。
【００４１】
各メッシュのエッジ画素量とは、１つのメッシュ内の全画素数に対するエッジ画素数の割合を示す。エッジ画素量の算出は、既存のエッジ画素の検出方法を用いて行うことができる。例えば、画像の輝度成分に対してエッジ抽出フィルタを用いて画素単位のエッジ量を抽出し、所定の閾値を超えるエッジ量を有する画素をエッジ画素とする。
【００４２】
以上のように、各メッシュに対して平均色とエッジ画素量の２つの特徴量が抽出される。図３の例では、メッシュ分割数が１００個であるので、平均色及びエッジ画素量がそれぞれ１００個ずつ得られる。
【００４３】
次に、図２のステップＳ５で、制御部１２は、検索対象画像を複数のメッシュに分割する。ステップＳ５では、ステップＳ３について説明したのと同様の処理を検索対象画像に対して行う。
【００４４】
ステップＳ６では、制御部１２は、ステップＳ５で分割された検索対象画像の各メッシュについて特徴量を抽出する。ステップＳ６では、ステップＳ４について説明したのと同様の処理を検索対象画像に対して行う。
【００４５】
ステップＳ６までの処理が終了すると、基準画像及び検索対象画像はそれぞれメッシュに分割され、各メッシュから特徴量が抽出される。図３に示すように、基準画像の各メッシュをＭＳＨｘｉｊと表記し、検索対象画像の各メッシュをＭＳＨｙｉｊと表記する。添え字ｉ及びｊは、それぞれメッシュの横及び縦の位置を示す。図３の画像分割例では、メッシュの分割数が横１０×縦１０であるので、添え字のｉ，ｊはそれぞれ０から９までの値となり、基準画像において（横２，縦１）の位置にあるメッシュはＭＳＨｘ２１と表記される。
【００４６】
また、各メッシュから抽出された平均色及びエッジ画素量を、それぞれＡＶＥｘｉｊ及びＥＧＥｘｉｊと表記する。平均色はＲＧＢ色空間においてＲ成分、Ｇ成分及びＢ成分を有し、各成分をＡＶＥＲｘｉｊ，ＡＶＥＧｘｉｊ及びＡＶＥＢｘｉｊと表記する。すなわち、ＡＶＥｘｉｊ＝（ＡＶＥＲｘｉｊ，ＡＶＥＧｘｉｊ，ＡＶＥＢｘｉｊ）と表される。メッシュＭＳＨｘｉｊから抽出された平均色及びエッジ画素量をＭＳＨｘｉｊの特徴量ベクトル（ＡＶＥＲｘｉｊ，ＡＶＥＧｘｉｊ，ＡＶＥＢｘｉｊ，ＥＧＥｘｉｊ）として表すことができる。
【００４７】
次に、図２のステップＳ７で、制御部１２は、基準画像の各メッシュについて、検索対象画像において対応するメッシュを選択する。ステップＳ７では、基準画像の各メッシュについて、そのメッシュの特徴量と、そのメッシュの周辺のメッシュの変位方向と、を考慮して検索対象画像上の対応メッシュを選択する。
【００４８】
図４から図６を参照し、図２に示すフローチャートのステップＳ７の対応メッシュ選択処理について説明する。ここでは、弛緩法（relaxation method）に従ってステップＳ７の対応メッシュ選択処理を行う例について説明する。弛緩法は、対象物にその特徴によってラベルを付ける方法において、対象物間の関係の情報を用いてラベル付けのあいまいさを取り除いていく方法である。
【００４９】
図４は、図２のフローチャートのステップＳ７の対応メッシュ選択処理の流れの例を示すフローチャートである。図５は、図４に示す処理における基準画像及び検索対象画像の各メッシュの関係の一例を表す説明図である。
【００５０】
まずステップＳ７０で、制御部１２は、基準画像のメッシュのうちから、１つの注目メッシュａｉを選択する。図５（ａ）に示す例では、基準画像のメッシュＭＳＨｘ１１が注目メッシュａｉとして選択されている。
【００５１】
次に、図４のステップＳ７１で、制御部１２は、基準画像の注目メッシュａｉに対応する検索対象画像内のメッシュの候補を選択する。例えば、図５（ａ）及び図５（ｂ）に示すように、基準画像の注目メッシュａｉの周囲８個のメッシュを近傍メッシュｂｎ（ｎ＝１，２，・・・，８）とし、基準画像上の注目メッシュａｉ及び近傍メッシュｂｎの位置に対応する検索対象画像上の位置にある９個のメッシュｙｎ（ｎ＝０，１，・・・，８）を注目メッシュａｉの対応候補メッシュとして選択する。つまり、検索対象画像上において、注目メッシュａｉの基準画像上の位置（横１，縦１）に対応する位置のメッシュＭＳＨｙ１１（＝ｙ０）及びＭＳＨｙ１１の周囲８個のメッシュを対応候補メッシュｙｎとする。  図６に、基準画像の注目メッシュａｉの位置から近傍メッシュｂｎの位置への変位方向λｎを示す。変位方向λ１，λ２，…，λ８は、それぞれ、注目メッシュａｉの位置から近傍メッシュｂ１，ｂ２，…，ｂ８の位置への変位方向を示し、λ０は「変位なし」の状態を示す。対応候補メッシュｙｎは、注目メッシュａｉを図６に示す変位方向λｎ（ｎ＝０，１，…，８）へ変位させた場合の基準画像上の位置（注目メッシュａｉの位置及び近傍メッシュｂｎの位置）に対応する検索対象画像上の位置にあるメッシュであるとも言える。よって、「注目メッシュａｉの対応メッシュがｙｊである」ことは、「注目メッシュａｉの変位方向がλｊである」ことであると言える。
【００５２】
図４のステップＳ７１で選択された対応候補メッシュｙｎのうちの１つのメッシュが、ステップＳ７２以下の処理により、注目メッシュａｉの対応メッシュとして選択される。
【００５３】
ステップＳ７２では、制御部１２は、ある対応候補メッシュｙｊについて、注目メッシュａｉの対応メッシュとしての適合度を計算する。ここで、注目メッシュａｉの対応メッシュとしてｙｊが正解である確率、つまり、注目メッシュａｉの変位方向がλｊである確率をｐｉ（ｒ）（λｊ）とする。すべての変位方向λｊ（ｊ＝０，１，・・・，８）についてのｐｉ（ｒ）（λｊ）の和は１である（式（１））。
【数１】
2008134791.tif 000003
式（１）で、Ｍは、変位方向λｊの個数を示し、ここではＭ＝８である。また、式（１）で、（ｒ）は、ステップＳ７０からステップＳ７５までの処理のｒ回目の反復を表し、初期値ｒ＝０は例えばｐｉ（０）（λｊ）＝１／（Ｍ＋１）＝１／９とする。ステップＳ７０からステップＳ７５までの処理を反復して行って、ｐｉ（ｒ）（λｊ）を求めることで、注目メッシュａｉの対応メッシュを選択する。
【００５４】
注目メッシュａｉの変位方向がλｊであることの適合度を求めるための適合関数として、例えば式（２）で定義される関数を用いる。適合関数ｃｉｎ（ｊ，ｋ）は、基準画像において注目メッシュａｉの周辺に位置する近傍メッシュｂｎが、注目メッシュａｉの変位方向λｊと同じ変位方向を有し、かつ、注目メッシュａｉから抽出された特徴量と対応候補メッシュｙｊから抽出された特徴量との類似性が高い場合に大きな値を取るように定義される。
【数２】
2008134791.tif 000004
ここで、λｊは、注目メッシュａｉの変位方向を表すベクトル（‖λｊ‖＝１）、λｋは、近傍メッシュｂｎの変位方向を表すベクトル（‖λｋ‖＝１）、ｃｏｒｒ（ｖｉ，ｗｊ）は、注目メッシュａｉの特徴量ベクトルｖｉと対応候補メッシュｙｊの特徴量ベクトルｗｊとの間の相関係数、αは調整パラメータである。
【００５５】
式（２）において、注目メッシュａｉの特徴量ベクトルｖｉと対応候補メッシュｙｊの特徴量ベクトルｗｊとの間の相関係数ｃｏｒｒ（ｖｉ，ｗｊ）の項は、注目メッシュａｉの特徴量ベクトルｖｉと対応候補メッシュｙｊの特徴量ベクトルｗｊとの類似性を表すものである。各メッシュから抽出される特徴量の個数をＮ、ｖｉ＝（ｖｉ１，・・・，ｖｉＮ）、ｗｊ＝（ｗｊ１，・・・，ｗｊＮ）とすると、ｃｏｒｒ（ｖｉ，ｗｊ）は、例えば次の式（３）に従って計算でき、−１≦ｃｏｒｒ（ｖｉ，ｗｊ）≦１となる。
【数３】
2008134791.tif 000005
【００５６】
本実施形態では、各メッシュから平均色のＲ成分ＡＶＥＲ、Ｇ成分ＡＶＥＧ、及びＢ成分ＡＶＥＢと、エッジ画素量ＥＧＥと、の４個の特徴量が抽出される。よって、注目メッシュａｉの特徴量ベクトルｖｉ＝（ｖｉ１，・・・，ｖｉ４）＝（ＡＶＥＲａｉ，ＡＶＥＧａｉ，ＡＶＥＢａｉ，ＥＧＥａｉ）、対応候補メッシュｙｊの特徴量ｗｊ＝（ｗｊ１，・・・，ｗｊ４）＝（ＡＶＥＲｙｊ，ＡＶＥＧｙｊ，ＡＶＥＢｙｊ，ＥＧＥｙｊ）として、式（３）によりｃｏｒｒ（ｖｉ，ｗｊ）を計算する。
【００５７】
図５を参照すると、例えば注目メッシュａｉが変位方向λ１を有すること、つまり、注目メッシュａｉの対応メッシュがｙ１であることの適合度を求める場合、注目メッシュａｉの特徴量ベクトルｖｉと、対応メッシュｙ１の特徴量ベクトルｗ１と、の相関係数ｃｏｒｒ（ｖｉ，ｗ１）を求めることになる。特徴量ベクトルｖｉと特徴量ベクトルｗｊとの間の相関係数の代わりに、２つの特徴量ベクトル間のユークリッド距離を求めても良い。
【００５８】
注目メッシュａｉの変位方向λｊ及び近傍メッシュｂｎの変位方向λｋのいずれも「変位なし」ではない場合（ｊ，ｋ≠０）、式（２−１）に従って適合関数ｃｉｎ（ｊ，ｋ）を計算する。式（２−１）の第１項のλｊ・λｋは、注目メッシュａｉの変位方向の整合度を表し、λｊとλｋとの内積である。ここでは、‖λｊ‖＝‖λｋ‖＝１より、−１≦λｊ・λｋ≦１となる。
【００５９】
注目メッシュａｉの変位方向λｊ及び近傍メッシュｂｎの変位方向λｋのいずれも「変位なし」である場合（ｊ＝ｋ＝０）、式（２−２）に従って適合関数ｃｉｎ（ｊ，ｋ）を計算する。式（２−２）の第１項において、注目メッシュａｉの変位方向の整合度を表す値を１とする。この場合、注目メッシュａｉ及び近傍メッシュｂｎの変位方向は同じであるので、変位方向の整合度を高く設定する。
【００６０】
注目メッシュａｉの変位方向λｊ及び近傍メッシュｂｎの変位方向λｋのいずれか一方のみが「変位なし」である場合、式（２−３）に従って適合関数ｃｉｎ（ｊ，ｋ）を計算する。式（２−３）では、注目メッシュａｉの変位方向の整合度は０としている。
【００６１】
式（２）の適合関数ｃｉｎ（ｊ，ｋ）を用いて、ある近傍メッシュｂｎとの関係において注目メッシュａｉが変位方向λｊを持つ平均適合度ｆｉｎ（ｒ）（ｊ）は、式（４）で表される。
【数４】
2008134791.tif 000006
【００６２】
ｆｉｎ（ｒ）（ｊ）を、注目メッシュａｉのすべての近傍メッシュｂｎ（ｎ＝１，２，・・・，８）について考えると、注目メッシュａｉの変位方向がλｊである適合度ｑｉ（ｒ）（λｊ）は、次の式（５）で表される。
【数５】
2008134791.tif 000007
【００６３】
以上で説明したとおり、ステップＳ７２では、制御部１２は、式（５）に従って、ある対応候補メッシュｙｊの適合度（注目メッシュａｉの変位方向がλｊである適合度）ｑｉ（ｒ）（λｊ）を求める。
【００６４】
ステップＳ７３では、制御部１２は、注目メッシュａｉのすべての対応候補メッシュｙｎについて、適合度ｑｉ（ｒ）（λｊ）が計算されたか否かを判定する。すべての対応候補メッシュｙｎについて適合度が計算されていれば、ステップＳ７４に進み、すべての対応候補メッシュｙｎについて適合度が計算されていなければ、ステップＳ７２に戻ってまだ適合度の計算されていない対応候補メッシュについて適合度を計算する。
【００６５】
ステップＳ７４では、制御部１２は、ステップＳ７２で求めた各対応候補メッシュｙｊの適合度ｑｉ（ｒ）（λｊ）を用いて、注目メッシュａｉの対応メッシュとしてｙｊが正解である確率、つまり、注目メッシュａｉの変位方向がλｊである確率ｐｉ（ｒ）（λｊ）の値を次の式（６）に従って更新する。
【数６】
2008134791.tif 000008
【００６６】
ステップＳ７４では、注目メッシュａｉのすべての対応候補メッシュｙｎ（ｎ＝０，１，２，・・・，８）について、正解確率ｐｉ（ｒ）（λｎ）を計算する。
【００６７】
ステップＳ７５では、基準画像のすべてのメッシュについて処理が行われたか否かを確認する。基準画像のすべてのメッシュについて処理が行われていればステップＳ７６に進み、基準画像のすべてのメッシュについて処理が行われていなければ、ステップＳ７０に戻ってまだ処理が行われていないメッシュを注目メッシュとしてステップＳ７１以下の処理を行う。
【００６８】
ステップＳ７６では、所定の収束条件が満たされているか否かを判定する。例えば、ステップＳ７０からステップＳ７５までの処理の反復回数ｒが予め設定された回数を超えていれば収束条件を満たすと判定する。また、例えば、基準画像において、変位方向がλｊである確率ｐｉ（ｒ）（λｊ）が予め設定された値以上（例えば、０．８以上）となるメッシュが、予め設定された値以上（例えば、基準画像のメッシュ数の合計の９割以上）となった場合に収束条件を満たすと判定しても良い。
【００６９】
ステップＳ７７では、基準画像上のすべてのメッシュａｉについて、確率ｐ（ｒ）（λｊ）が最大となるλｊを変位方向として採用する。つまり、確率ｐ（ｒ）（λｊ）が最大となる検索対象画像の対応候補メッシュｙｊを、そのメッシュａｉの対応メッシュとして選択する。ステップＳ７７の処理の後、対応メッシュ選択処理（図２のステップＳ７）は終了する。
【００７０】
以上、図４から図６を参照して説明したステップＳ７の処理では、近傍メッシュｂｎとしては、注目メッシュａｉの周囲８個のメッシュを選択し（図５（ａ））、対応候補メッシュｙｎとしては、基準画像上の注目メッシュａｉ及び近傍メッシュｂｎの位置に対応する検索対象画像上の位置にあるメッシュを選択した。図７に、近傍メッシュｂｎ及び対応候補メッシュｙｎの選択の他の一例を示す。図７を参照すると、注目メッシュａｉの近傍メッシュｂｎとしては、注目メッシュａｉの周囲の２４個のメッシュが選択され、対応候補メッシュｙｎとしては、注目メッシュａｉ（ＭＳＨｘ２２）の位置に対応する検索対象画像上の位置のメッシュｙ０（＝ＭＳＨｙ２２）と、近傍メッシュｂｎ（ｎ＝１，２，・・・，２４）の位置に対応する、ｙ０の周囲の２４個のメッシュと、が選択される。図７に示すように近傍メッシュｂｎ及び対応候補メッシュｙｎを選択した場合、図４のステップＳ７２において、注目メッシュａｉの変位方向がλｊであることの適合度ｑｉ（ｒ）（λｊ）は、変位方向λｊの個数Ｍ＝２４として、次の式（７）に従って計算される。
【数７】
2008134791.tif 000009
【００７１】
式（７）中の適合関数ｃｉｎ（ｊ，ｋ）は、式（２）に従って計算される。式（７）において、ｄｉｎは、注目メッシュａｉと近傍メッシュｂｎとの距離に関する重みであり、距離が大きいほど小さな値とする。例えば、メッシュａｉとｂｎとの距離の逆数をｄｉｎとすることができる。
【００７２】
以上で説明したステップＳ７の処理によって、基準画像の各メッシュと検索対象画像の各メッシュとの対応付けを行った後、ステップＳ８で、制御部１２は、ステップＳ７で求められた基準画像の各メッシュと検索対象画像の各メッシュとの対応関係に基づいて、基準画像と検索対象画像との類似度を算出する。例えば、基準画像と検索対象画像との対応するメッシュの各組について、特徴量ベクトル間の相関係数やユークリッド距離などを求めることで特徴量の類似度を算出し、算出した類似度を基に基準画像と検索対象画像との類似度を評価する。
【００７３】
図８及び図９を参照し、制御部１２が行う類似度算出処理の他の一例について説明する。
【００７４】
図８は、制御部１２が行う処理の流れの一例を示すフローチャートである。図８に示すフローチャートにおいて、図２に示すフローチャートと同様の処理には同様の符号を付す。
【００７５】
図８において、基準画像取得処理（ステップＳ１）から基準画像の特徴量の抽出処理（ステップＳ４）までは、図２を参照して説明した上述のステップＳ１からステップＳ４までの処理と同様の処理が行われる。次に、図８に示すフローチャートの処理は、検索対象画像をメッシュ分割（図２のステップＳ５）及び検索対象画像の特徴量の抽出（図２のステップＳ６）を行うことなく、ステップＳ１０の対応メッシュ選択処理へ進む。
【００７６】
ステップＳ１０の対応メッシュ選択処理では、制御部１２は、図４に示すフローチャートに従って処理を行うが、対応候補メッシュの選択処理（ステップＳ７１）及び対応候補メッシュの適合度計算処理（ステップＳ７２）の内容が、図４から図７を参照して説明した上述のステップＳ７１及びステップＳ７２の処理の内容と異なる。
【００７７】
図９を参照し、ステップＳ１０の対応メッシュ選択処理における、基準画像の注目メッシュの対応候補メッシュ選択処理（図４のステップＳ７１）について説明する。図９（ａ）に示すように、基準画像の注目メッシュａｉの周辺の領域である近傍Ｂ内において、所定の方向及び所定の大きさを有する変位方向ベクトルλｎに従って注目メッシュａｉを変位させた位置のメッシュを近傍メッシュｂｎとする。変位方向ベクトルλｎの個数は必要に応じて設定できるし、変位方向ベクトルλｎそれぞれの方向及び大きさも、必要に応じて設定できる。例えば、λｎの大きさを基準画像の各メッシュの横方向又は縦方向の大きさのγ倍（０＜γ）とし、γの値を任意に設定することができる（例えば、γ＝０．５，０．７５，１．０，１．２５）。
【００７８】
図８及び図９を参照して説明する本例の処理では、図８のステップＳ３において分割された基準画像のメッシュに一致しない領域が近傍メッシュｂｎとして選択されることがある。図９（ａ）に示すように、注目メッシュａｉの一部と近傍メッシュｂｎの一部とが重複していても良い。また、異なる近傍メッシュｂｉ及びｂｊの一部が重複しても良い。このように近傍メッシュｂｎが選択され、基準画像上の近傍メッシュｂｎの位置に対応する検索対象画像上の位置にある領域が、対応候補メッシュｙｎとして選択される。
【００７９】
ステップＳ１０の対応メッシュ選択処理において、図９を参照して説明したように注目メッシュａｉの対応候補メッシュｙｎを選択した（図４のステップＳ７１）後、ステップＳ７２において、制御部１２は、まず、選択した対応候補メッシュｙｎから特徴量を抽出する。この、特徴量を抽出する処理は、図８のステップＳ４において基準画像の各メッシュについて行われる特徴量抽出処理と同様である。そして、次の式（８）に従って、注目メッシュａｉの変位方向がλｊであることの適合度ｑｉ（ｒ）（λｊ）を計算する。
【数８】
2008134791.tif 000010
【００８０】
式（８）中の適合関数ｃｉｎ（ｊ，ｋ）は、式（２）に従って計算される。式（８）において、Ｂは、近傍メッシュに付される番号の集合である。ｄｉｎは、注目メッシュａｉと近傍メッシュｂｎとの距離に関する重みであり、距離が大きいほど小さな値とする。例えば、メッシュａｉとｂｎとの距離の逆数をｄｉｎとすることができる。
【００８１】
以上のようにステップＳ７２で対応候補メッシュの適合度を計算した後、図４のステップＳ７３からステップＳ７７では、制御部１２は、上記で説明したステップＳ７３からステップＳ７７の処理と同様の処理を行い、図８のステップＳ１０の対応メッシュ選択処理を終了する。その後、ステップＳ８で、図２を参照して説明したステップＳ８の処理と同様に基準画像と検索対象画像との類似度が算出される。
【００８２】
以上で説明した実施形態の処理では、基準画像の各メッシュについて検索対象画像上の対応メッシュを選択する際に、基準画像の注目メッシュ及び注目メッシュの近傍メッシュの位置に対応する検索対象画像上の位置にあるメッシュの特徴量を考慮し、かつ、注目メッシュの変位方向と注目メッシュの近傍メッシュの変位方向との整合性を考慮する。したがって、例えば、図１０に示すように、基準画像（図１０（ａ））と検索対象画像（図１０（ｂ））とが同じ画像を表すが、画像データ上での位置がずれている場合に、本実施形態の処理によると、基準画像の各メッシュに対して、そのメッシュの近傍のメッシュ位置に対応する検索対象画像の位置にあるメッシュの特徴量が考慮されるので、基準画像の各メッシュと検索対象画像の各メッシュとの正しい対応関係が得られる。
【００８３】
また、上述の実施形態の処理によると、基準画像の各メッシュについて、特徴量の類似性が高く、かつ、基準画像の各メッシュの変位方向とその近傍のメッシュの変位方向との整合性が高くなるように、検索対象画像の対応メッシュが選択される。つまり、上述の実施形態の処理では、基準画像の各メッシュがその近傍のメッシュと同じ方向又は近い方向に変位するように、基準画像の各メッシュと検索対象画像の各メッシュとの対応関係が決定される。したがって、上述の実施形態の処理は、画像の局所領域内のメッシュ同士が同じ方向又は近い方向に変位するような画像の変動が生じている場合、例えば図１１に示すように、画像の縮小（図１１（ａ））又は回転（図１１（ｂ））が生じている場合に、基準画像の各メッシュと検索対象画像の各メッシュとの正しい対応関係を得るのに適している。
【００８４】
以上より、上述の実施形態の処理によると、例えば紙文書を複写機で複製して得られる画像において生じやすい、画像の位置ずれ、拡大縮小、及び回転などの変動に対してロバストな画像照合が可能となる。
【００８５】
図１２及び図１３を参照し、制御部１２が行う類似度算出処理の他の一例について説明する。
【００８６】
図１２は、制御部１２が行う処理の流れの他の一例を示すフローチャートである。図１２に示すフローチャートにおいて、図２に示すフローチャートと同様の処理には同様の符号を付している。
【００８７】
ステップＳ１の基準画像取得及びステップＳ２の検索対象画像取得の処理は、図２のフローチャートを参照して説明した処理と同様である。
【００８８】
ステップＳ２０で、制御部１２は、基準画像を現在よりも小さいメッシュにメッシュ分割する。例えば、現在の基準画像の各メッシュを、縦方向及び横方向の長さがそれぞれ現在の半分である４つのメッシュに分割する。このように分割すると、基準画像は２倍の解像度にメッシュ分割されることになる。
【００８９】
ステップＳ４では、制御部１２は、ステップＳ２０で分割された基準画像の各メッシュについて、図２を参照して説明したステップＳ４と同様の処理を行い、基準画像の特徴量を抽出する。
【００９０】
ステップＳ２１で、制御部１２は、検索対象画像に対してステップＳ２０と同様の処理を行い、検索対象画像を現在よりも小さいメッシュにメッシュ分割する。
【００９１】
ステップＳ６では、制御部１２は、ステップＳ２１で分割された検索対象画像の各メッシュについて、図２を参照して説明したステップＳ６と同様の処理を行い、検索対象画像の特徴量を抽出する。
【００９２】
ステップＳ２２の対応メッシュ選択処理では、前回ステップＳ２２の処理を行ったときに得られた情報を用いて、基準画像の各メッシュについて対応メッシュを選択する。ステップＳ２２の対応メッシュ選択処理では、図４に示すフローチャートと同様の処理を行うが、ステップＳ７１における対応候補メッシュの選択処理の内容が、図４から図７を参照して説明した上述の処理、及び図９を参照して説明した上述の処理と異なる。以下、ステップＳ２２の対応メッシュ選択処理において行われる、注目メッシュの対応候補メッシュの選択処理（図４のステップＳ７１）について説明する。
【００９３】
本例の対応候補メッシュ選択処理（図４のステップＳ７１）では、制御部１２は、前回のステップＳ２２の処理において選択された基準画像の各メッシュの対応メッシュの位置を参照して対応候補メッシュを選択する。
【００９４】
例えば図１３に示すように、１回目のステップＳ２２の処理において、注目メッシュａｉ（ＭＳＨｘ１１）に対応するメッシュとしてｙ８（ＭＳＨｙ２２）が選択されたとする。その後、ステップＳ２３の判定の結果、処理がステップＳ２０に戻り、ステップＳ２０及びステップＳ２１での処理によって、基準画像及び検索対象画像がそれぞれ２倍の解像度に分割されたとする。２回目のステップＳ２２の処理において、１回目のステップＳ２２の処理を行った際の注目メッシュａｉを分割して得られた４つのメッシュのうち、左上のメッシュ（ＭＳＨｘ１ａ１ａ）が新たな注目メッシュａ’ｉとされたとする。２回目のステップＳ２２の処理において、この新たな注目メッシュａ’ｉの対応候補メッシュとしては、ＭＳＨｙ１ａ１ａを中心とする９個のメッシュではなく、１回目のステップＳ２２の処理において注目メッシュａｉの対応メッシュとして選択されたｙ８（ＭＳＨｙ２２）を分割して得られた４つのメッシュの左上のメッシュＭＳＨｙ２ａ２ａを中心とする９個のメッシュが選択される。
【００９５】
ステップＳ２２の処理を初めて行う場合は、ステップＳ７１の対応候補メッシュ選択処理において、制御部１２は、図４から図７を参照して説明した上述の処理、及び図９を参照して説明した処理と同様に、基準画像の注目メッシュａｉの位置（横ｉ，縦ｊ）に対応する検索対象上の位置（横ｉ，縦ｊ）のメッシュを対応候補メッシュｙ０とし、注目メッシュａｉの近傍メッシュｂｎ（ｎ＝１，…，Ｍ）に対応する検索対象画像のメッシュを対応候補メッシュｙｎ（ｎ＝１，…，Ｍ）として選択する。
【００９６】
以上で説明したステップＳ７１の処理の後、図４のステップＳ７２からステップＳ７７では、既に上記で説明したステップＳ７２からステップＳ７７の処理と同様の処理を行い、図１２のステップＳ２２の処理を終了する。
【００９７】
ステップＳ２２の処理の後、ステップＳ２３で、基準画像が所定の解像度までメッシュ分割されたか否かを判定する。例えば、予め設定された回数だけ繰り返した場合に、基準画像が所定の解像度まで分割されたと判定する。又は、各メッシュの大きさが予め設定された大きさ以下である場合に、所定の解像度であると判定する。このように、各メッシュの大きさに基づいて判定を行う場合、判定基準となるメッシュの大きさは、処理対象となる画像の特性によって決定することができる。例えば、基準画像が紙文書を複写機で複製したり、スキャナで読み取ったりして得られる再生画像である場合、使用されるスキャナ、光学系、又は印刷機構などの誤差により、再生画像の印刷位置や拡大率に誤差が生じる。この印刷位置や拡大率の誤差により発生する変位量の最大値が既知である場合、この最大変位量に応じて判定基準となるメッシュの大きさを決定することが好適である。例えば、主走査、副走査方向の最大変位量がそれぞれδｈ、δｖである場合、判定基準となるメッシュの幅をδｈ以下、高さをδｖ以下とすることが好適である。
【００９８】
ステップＳ２３で、所定の解像度であると判定されたらステップＳ８へ進み、所定の解像度でないと判定されたらステップＳ２０に戻る。
【００９９】
ステップＳ８では、制御部１２は、図２を参照して説明したステップＳ８と同様の処理を行い、基準画像と検索対象画像との類似度を算出する。
【０１００】
図１２及び図１３を参照して説明した処理を行うと、基準画像及び検索対象画像に比較的大きな変位が生じている場合でも基準画像の各メッシュと検索対象画像の各メッシュとの対応付けを適切に行うことができる。
【０１０１】
例えば、図１４Ａに示すように、メッシュ分割数が横８×縦８になるように基準画像及び検索対象画像をメッシュ分割した場合において、基準画像のメッシュａｉ（＝ＭＳＨｘ３３）に対応する検索対象画像のメッシュがＭＳＨｙ５４であるとする。この図１４Ａに例示する画像を処理する場合、図２のフローチャートに従って基準画像及び検索対象画像のメッシュ分割（ステップＳ３，Ｓ５）と対応メッシュ選択処理（ステップＳ７）とをそれぞれ一度だけ行って、基準画像のメッシュａｉ（＝ＭＳＨｘ３３）に対応する検索対象画像のメッシュＭＳＨｙ５４を正しく選択するためには、注目メッシュａｉの近傍メッシュｂｎとして、図１４Ａの実線太枠中の２４個のメッシュ（ＭＳＨｘｉｊ（ｉ，ｊ＝１，２，…，５））を選択し、基準画像上の注目メッシュａｉ及び近傍メッシュｂｎのそれぞれの位置に対応する検索対象画像上の位置にある２５個の対応候補メッシュｙｎ（ｎ＝０，１，…，２４）について、その適合度を計算する必要がある。例えば図５を参照して説明した場合のように、注目メッシュａｉの近傍メッシュｂｎとして、注目メッシュａｉの周囲８個のメッシュ（図１４Ａの点線太枠内のメッシュ）を選択すると、正しい対応メッシュＭＳＨｙ５４が対応候補メッシュｙｎに含まれない。
【０１０２】
図１４Ｂを参照し、図１４Ａに例示した画像と同じ画像について、図１２及び図１３を参照して説明した処理に従って基準画像の各メッシュと検索対象画像の各メッシュとの対応付けを行う場合の処理について説明する。例えば、１回目の図１２のステップＳ２０，Ｓ２１において、図１４Ｂ（ａ）のように、メッシュ分割数が横４×縦４になるように基準画像及び検索対象画像がメッシュ分割されたとする。次に、ＭＳＨｘ３３の領域を含む注目メッシュＡｉについて、注目メッシュＡｉの周囲８個のメッシュを近傍メッシュＢｎとしてステップＳ２２の対応メッシュ選択処理が行われ、近傍メッシュＢ８に対応する検索対象画像のメッシュが注目メッシュＡｉの対応メッシュとして選択されたとする。ステップＳ２３の判定の後に行われる２回目のステップＳ２０，Ｓ２１の処理では、図１４Ｂ（ｂ）に示すように、基準画像及び検索対象画像の図１４Ｂ（ａ）に示す各メッシュを４個のメッシュに分割して、それぞれの画像のメッシュ分割数を図１４Ａと同じ横８×縦８とする。その後のステップＳ２２の対応メッシュ選択処理において、基準画像の注目メッシュａｉ（＝ＭＳＨｘ３３）について検索対象画像の対応候補メッシュを選択する際には、１回目のステップＳ２２の処理（図１４Ｂ（ａ））において得られたメッシュの対応関係を利用する。１回目のステップＳ２２の処理では、上述の通り、注目メッシュＡｉの対応メッシュとして、基準画像上の近傍メッシュＢ８の位置に対応する検索対象画像上の位置にあるメッシュ（ＭＳＨｙｉｊ（ｉ，ｊ＝４，５））が選択された。この関係を利用して、図１４Ｂ（ｂ）に示すように、基準画像上の注目メッシュａｉ（＝ＭＳＨｘ３３）の位置に対応する検索対象画像上の位置にある対応候補メッシュｙ０として、ＭＳＨｙ３３ではなくＭＳＨｙ５５を選択し、注目メッシュａｉの周囲８個の近傍メッシュにそれぞれ対応する対応候補メッシュｙｎとして、ＭＳＨｙ５５の周囲８個のメッシュを選択する。このように選択された対応候補メッシュｙｎの適合度を計算すると、基準画像のメッシュＭＳＨｙ３３の正しい対応メッシュＭＳＨｙ５４を選択できる。
【０１０３】
図１２及び図１４Ｂを参照して説明した処理の例によると、１回目のステップＳ２２の対応メッシュ選択処理において、基準画像の注目メッシュＡｉ及び近傍メッシュＢｎ（ｎ＝１，２，…，８）（図１４Ｂ（ａ））に対応する検索対象画像上の位置にある９個の対応候補メッシュの適合度を計算し、２回目のステップＳ２２の処理において、９個の対応候補メッシュｙｎ（ｎ＝０，１，…，８）（図１４Ｂ（ｂ））の適合度を計算することで、つまり、合計で１８個の対応候補メッシュの適合度を計算することで、基準画像のメッシュＭＳＨｘ３３の正しい対応メッシュＭＳＨｙ５４を選択できる。したがって、図１２のフローチャートに従う処理によると、２５個の対応候補メッシュの適合度を計算する図２及び図１４Ａを参照して説明した処理よりも、少ない計算量で基準画像のメッシュＭＳＨｘ３３の対応メッシュを選択できる。
【０１０４】
以上のように、図１２及び図１３を参照して説明した処理によると、画像に大きな変位が生じている場合であっても、適切に、かつ高速に基準画像の各メッシュと検索対象画像の各メッシュとの対応関係を得ることができる。
【０１０５】
なお、以上で説明した実施形態の制御部１２の処理では、図２のステップＳ７、図８のステップＳ１０、及び図１２のステップＳ２２の対応メッシュ選択処理において、いずれも、図４のフローチャートを参照し、弛緩法に従って基準画像の各メッシュについて検索画像上の対応メッシュを選択する方法について説明した。注目メッシュ及び対応候補メッシュの特徴量ベクトルの類似性と、注目メッシュの近傍のメッシュの変位方向に基づく変位方向の整合性と、の両方を考慮して注目メッシュの対応メッシュを選択できるような方法であれば、自己組織化マップ（Self Organizing Map）や動的計画法マッチングなど、弛緩法以外の方法を適用することもできる。
【図面の簡単な説明】
【０１０６】
【図１】本発明の１つの実施形態の画像処理装置の構成の一例を示す図である。
【図２】本発明の１つの実施形態で行われる画像の類似度算出処理の一例を示すフローチャートである。
【図３】本発明の１つの実施形態で行われる処理において、画像を複数の領域に分割した様子の一例を示す図である。
【図４】本発明の１つの実施形態で行われる対応メッシュ選択処理の流れの一例を示すフローチャートである。
【図５】図４に示すフローチャートによる処理において、基準画像及び検索対象画像の各メッシュの関係の一例を表す説明図である。
【図６】本発明の１つの実施形態で行われる処理において、基準画像のメッシュの変位方向の一例を示す説明図である。
【図７】図４に示すフローチャートによる処理において、基準画像及び検索対象画像の各メッシュの関係の他の一例を表す説明図である。
【図８】本発明の１つの実施形態で行われる画像の類似度算出処理の他の一例を示すフローチャートである。
【図９】図８に示すフローチャートによる処理において、基準画像及び検索対象画像のメッシュの関係の一例を表す説明図である。
【図１０】本発明の１つの実施形態で行われる画像の類似度算出処理において処理される画像の一例を示す図である。
【図１１】本発明の１つの実施形態で行われる画像の類似度算出処理において処理される画像の一例を示す図である。
【図１２】本発明の１つの実施形態で行われる類似度算出処理の他の一例を示すフローチャートである。
【図１３】図１２に示すフローチャートによる処理において、基準画像及び検索対象画像の各メッシュの関係の一例を表す説明図である。
【図１４Ａ】本発明の１つの実施形態で行われる画像の類似度算出処理において処理される画像の一例を示す図である。
【図１４Ｂ】図１２に示すフローチャートによる処理において、画像のメッシュ分割の例を示す図である。
【符号の説明】
【０１０７】
１０  画像処理装置、１２  制御部、１４  記憶部、１６  画像入力部、１８  標準入力部、２０  出力部、２２  通信部、２４  バス。
【図１】
2008134791.tif 000011
【図２】
2008134791.tif 000012
【図３】
2008134791.tif 000013
【図４】
2008134791.tif 000014
【図５】
2008134791.tif 000015
【図６】
2008134791.tif 000016
【図７】
2008134791.tif 000017
【図８】
2008134791.tif 000018
【図９】
2008134791.tif 000019
【図１０】
2008134791.tif 000020
【図１１】
2008134791.tif 000021
【図１２】
2008134791.tif 000022
【図１３】
2008134791.tif 000023
【図１４Ａ】
2008134791.tif 000024
【図１４Ｂ】
2008134791.tif 000025