(57)【要約】  精度のよい照合を可能にする画像照合装置等を提供しなければならない。  アフィン変換に関する別の不変量である、連結領域もしくはその和領域の累積画素値比を特徴量として用いるように画像照合装置を構成することによって、より高精度な照合が行えるようにする。加えて、領域の相対的な位置情報を利用することにより、さらに高精度な照合を実現する。
2009110410.tif 000002
【特許請求の範囲】
【請求項１】
照合対象となる第１の画像と第２の画像について、前記第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、前記組から計算される特徴量を用いて前記第１の画像と前記第２の画像を照合する画像照合装置であって、
前記特徴量として、前記組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された前記累積画素値の比を計算する、累積画素値比計算手段を含むことを特徴とする画像照合装置。
【請求項２】
前記累積画素値比計算手段は、累積画素値を計算する際に、画素値として二値を利用することを特徴とする請求項１に記載された画像照合装置。
【請求項３】
前記累積画素値比計算手段は、累積画素値を計算する際に、画素値として濃淡画像における画素値を利用することを特徴とする請求項１に記載された画像照合装置。
【請求項４】
前記累積画素値比計算手段は、累積画素値を計算する際に、画素値としてカラー画像中の各画素における画素情報を基に計算された値を画素値として利用することを特徴とする請求項１に記載された画像照合装置。
【請求項５】
前記カラー情報を表す画素情報を元に画素値を計算する手段を１つ以上備え、カラー画像から計算される１つ以上の種類の濃淡画像のそれぞれに対して前記累積画素値比計算手段を利用した照合を行い、あらかじめ定められた数の濃淡画像について画像照合結果が一致と判定された場合に、画像として一致したと判定することを特徴とする請求項１に記載された画像照合装置。
【請求項６】
前記累積画素値比計算手段により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算する特徴点配置計算手段と、
前記特徴点配置計算手段により計算された特徴点配置を用いてアフィンパラメータを推定するアフィンパラメータ推定手段と、
前記アフィンパラメータにより計算された値を用いて特徴点配置の当てはまりのよさを検証するアフィンパラメータ検証手段と
を含むことを特徴とする請求項１に記載された画像照合装置。
【請求項７】
前記累積画素値比計算手段により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、アフィンパラメータ推定手段と、アフィンパラメータ検証手段とが動作することを特徴とする請求項６に記載された画像照合装置。
【請求項８】
前記累積画素値比計算手段により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算し、特徴点配置から特徴点三角形面積比である不変量の組を計算する特徴点三角形面積比計算手段と、
少なくとも前記特徴点三角形面積比計算手段により計算された特徴点三角形面積比である不変量を用いて検証を行う不変量検証手段と
を含むことを特徴とする請求項１に記載された画像照合装置。
【請求項９】
前記累積画素値比計算手段により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、不変量検証手段が動作することを特徴とする請求項８に記載された画像照合装置。
【請求項１０】
検索される画像に対応する登録画像を検索または同定するための結果を出力する最終一致判定手段を備えることを特徴とする請求項１乃至９のいずれか１項に記載の画像照合装置。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の画像照合装置により計算される特徴量を含むデータを格納した画像照合用特徴量格納記憶媒体。
【請求項１２】
照合対象となる第１の画像と第２の画像について、前記第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、前記組から計算される特徴量を用いて前記第１の画像と前記第２の画像を照合する画像照合方法であって、
前記特徴量として、前記組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された前記累積画素値の比を計算することを特徴とする画像照合方法。
【請求項１３】
コンピュータに、
照合対象となる第１の画像と第２の画像について、前記第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、前記組から計算される特徴量を用いて前記第１の画像と前記第２の画像を照合する処理を実行させるプログラムであって、
前記特徴量として、前記組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された前記累積画素値の比を計算する、累積画素値比計算処理を実行させることを特徴とするプログラム。
【請求項１４】
前記累積画素値比計算処理で、累積画素値を計算する際に、画素値として二値を利用することを特徴とする請求項１３に記載されたプログラム。
【請求項１５】
前記累積画素値比計算処理で、累積画素値を計算する際に、画素値として濃淡画像における画素値を利用することを特徴とする請求項１３に記載されたプログラム。
【請求項１６】
前記累積画素値比計算処理で、累積画素値を計算する際に、画素値としてカラー画像中の各画素における画素情報を基に計算された値を画素値として利用することを特徴とする請求項１３に記載されたプログラム。
【請求項１７】
前記カラー情報を表す画素情報を元に画素値を計算する処理を実行させ、カラー画像から計算される１つ以上の種類の濃淡画像のそれぞれに対して前記累積画素値比計算処理を利用した照合を行い、あらかじめ定められた数の濃淡画像について画像照合結果が一致と判定された場合に、画像として一致したと判定する処理を実行させることを特徴とする請求項１３に記載されたプログラム。
【請求項１８】
前記累積画素値比計算処理により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算する特徴点配置計算処理と、
前記特徴点配置計算処理により計算された特徴点配置を用いてアフィンパラメータを推定するアフィンパラメータ推定処理と、
前記アフィンパラメータにより計算された値を用いて特徴点配置の当てはまりのよさを検証するアフィンパラメータ検証処理と
を実行させることを特徴とする請求項１３に記載されたプログラム。
【請求項１９】
前記累積画素値比計算処理により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、アフィンパラメータ推定処理と、アフィンパラメータ検証処理とが実行されることを特徴とする請求項１８に記載されたプログラム。
【請求項２０】
前記累積画素値比計算処理により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算し、特徴点配置から特徴点三角形面積比である不変量の組を計算する特徴点三角形面積比計算処理と、
少なくとも前記特徴点三角形面積比計算処理により計算された特徴点三角形面積比である不変量を用いて検証を行う不変量検証処理と
を実行させることを特徴とする請求項１３に記載されたプログラム。
【請求項２１】
前記累積画素値比計算処理により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、不変量検証処理を実行させることを特徴とする請求項２０に記載されたプログラム。
【請求項２２】
検索される画像に対応する登録画像を検索または同定するための結果を出力する最終一致判定処理を実行させることを特徴とする請求項１３乃至２１のいずれか１項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像照合装置に関し、同一オブジェクトに関する画像を照合する画像照合技術に関するものである。
【背景技術】
【０００２】
関連する画像照合方法が非特許文献１に記載されている。非特許文献１には、英文文書の画像検索に画像照合装置を提供した例が掲載されている。【０００３】
関連する画像照合処理は、登録処理と照合処理の２つの処理に分けることができる。
登録処理においては、予め登録される複数の画像の各々に対して、次の処理が行われる。【０００４】
まず、登録画像の一つが入力されると、
（登録手続きＡ）英文文書の単語領域の重心が特徴点として抽出される。【０００５】
次に、抽出された特徴点から、順序付きの特徴点組み合わせが計算され、特徴点配置が計算される。具体的には、次のような処理が行われる。【０００６】
（登録手続きＣ）次に、特徴点のうちの一つｐを取り出す。次に、その特徴点の近傍にあるｎ個の点を取り出す。【０００７】
（登録手続きＤ）次に、特徴点の近傍にあるｎ個の点からｍ点を取り出す。【０００８】
（登録手続きＥ）次に、取り出されたｍ点から適当な一つの点をｐ０として選び、ｐを中心としてｐ０を先頭として時計回りに並べて特徴点の列Ｌｍを生成する。【０００９】
（登録手続きＦ）次に、Ｌｍから順序を保存してｆ点を選択するすべての特徴点の列Ｌｆを求め、辞書式順序に並べる。【００１０】
（登録手続きＣ）はすべての特徴点をｐとして選択するまで処理が継続し、（登録手続きＤ）はＮ個の点から得られるすべてのＭ点の組み合わせについて処理を行うまで処理が継続する。（登録手続きＣ）から（登録手続きＦ）までの手続きにより得られる特徴点の列の数は、一般には多数である。【００１１】
さらに、
（登録手続きＧ）特徴点の列Ｌｆから、不変量の列が計算される。当該の登録画像を一意に指定する番号（以下、登録画像番号と呼ぶ）と、特徴点を一意に指定する特徴点番号（以下、特徴点番号と呼ぶ）と共に、特徴量リストとして、格納される。【００１２】
格納された特徴量リストは、後段の照合処理に用いられる。なお、非特許文献１中では、検索を高速化するために、不変量を離散化した後、ハッシュを用いて特徴量リストを格納する方法について提案しているが、本発明には無関係であるため当該部分の説明は省略する。【００１３】
以上、登録画像の一つについての登録処理を説明した。この処理は、すべての登録画像に対して行われる。【００１４】
照合処理においては、まず、検索画像が入力されると、
（検索手続きＡ）英文文書の単語領域の重心が特徴点として抽出される。【００１５】
次に、抽出された特徴点から、順序付きの特徴点組み合わせが計算され、その組み合わせを巡回させたものが特徴点配置となる。具体的には、次のような処理が行われる。【００１６】
（検索手続きＣ）次に、特徴点のうちの一つｐを取り出す。次に、その特徴点の近傍にあるｎ個の点を取り出す。【００１７】
（検索手続きＤ）次に、特徴点の近傍にあるｎ個の点からｍ点を取り出す。【００１８】
（検索手続きＥ）次に、取り出されたＭ点から適当な一つの点をｐ０として選び、ｐを中心としてｐ０を先頭として時計回りに並べて特徴点の列Ｌｍを生成する。【００１９】
（検索手続きＦ）次に、Ｌｍから順序を保存してｆ点を選択するすべての特徴点の列Ｌｆを求め、辞書式順序に並べる。（検索手続きＣ）はすべての特徴点をｐとして選択するまで処理が継続し、（検索手続きＤ）はＮ個の点から得られるすべてのＭ点の組み合わせについて処理を行うまで処理が継続し、（検索手続きＥ）はｍ個の点をすべてｐ０として選ぶまで処理が継続する。【００２０】
（検索手続きＣ）から（検索手続きＦ）までの手続きにより得られる特徴点の列の数は、一般には多数である。【００２１】
さらに、
（検索手続きＧ）特徴点の列Ｌｆから、不変量の列が計算される。【００２２】
（検索手続きＨ）計算された不変量の列は、登録処理において格納された特徴量リスト中の不変量の列と照合される。照合の結果一致していた場合には、当該特徴量リストの登録画像番号に対する一致数（得票数）を１だけ増加させる（投票する）。【００２３】
なお、非特許文献１中では、その他の不変量の列の誤対応を防止する処理について提案しているが、本発明には無関係であるため当該部分の説明は省略する。これらの手続きは、すべての登録画像について処理を行うまで処理が継続する。【００２４】
最後に、各登録画像に対する一致数（各登録画像に投票された結果得られる得票数）から、【００２５】
【数１】
2009110410.tif 000003
なる計算式を用いて各登録画像のスコアを計算し、最大のスコアを持つ登録画像が照合結果として出力される。ここでｄｉは登録画像番号、Ｖ（ｄｉ）は登録画像番号ｄｉの登録画像についての得票数、Ｎ（ｄｉ）は登録画像番号ｄｉの登録画像に含まれる特徴点数、ｃは予備実験で定められる特徴点数と誤投票の比例定数である。【００２６】
これらの登録処理と照合処理を行う際のｆの値は、登録画像と検索画像との間に許容する変換に関する不変量の計算方法に依存して変わる。【００２７】
非特許文献１中では、ｆ＝４点から構成される２つの三角形の面積比（以下、特徴点三角形面積比と呼ぶ。）として計算される値をアフィン不変量として用いる例が示されている。アフィン不変量は、２つの画像間で任意のアフィン変換が起きた場合でも、対応する点の組み合わせから同一の値をとる性質がある。従って、登録画像と検索画像との間で任意のアフィン変換による変形が起きたとしても、登録画像から得られた特徴点配置とそれに対応する検索画像から得られた特徴点配置のおのおのから計算された不変量の列は、原理上同一となる。【００２８】
つまり、アフィン不変量を不変量として利用する画像照合装置は、登録画像と検索画像との間の変形がアフィン変換で表せるとみなせる場合に、高精度な照合を行うことができるよう構成されている。【００２９】
また、登録画像と検索画像との間のアフィン変換による変形が起きたとしても照合を可能にする別の技術として、特許文献１に開示されている技術がある。【００３０】
特許文献１では、段落番号００７６〜００８０に開示されているように、入力濃淡画像と参照濃淡画像との相関値が大きくなるように、アフィン変換パラメータの決定と、そのパラメータを用いて入力濃淡画像からアフィン変換重畳入力濃淡画像を生成し、アフィン変換重畳入力濃淡画像で入力画像を置き換えることを、反復して行う技術が開示されている。
【特許文献１】特開２０００−２５９８３６号公報
【非特許文献１】中居友弘、他２名、“デジタルカメラを用いた高速文書画像検索におけるアフィン不変量および相似不変量の利用”、電子情報通信学会技術研究報告（パターン認識・メディア理解、ＰＲＭＵ‐１８４〜２０１）、２００６年２月１６日、２５−３０頁
【発明の開示】
【発明が解決しようとする課題】
【００３１】
第１の問題点は、ある画像Ａに対して計算された特徴量リストと、本来画像Ａとは一致しないが画像Ａから得られる特徴点とほぼ同一な特徴点位置が得られる別の画像Ｂに対して計算された特徴量リストと、が、（特徴量リストの照合としては一致する場合であるが、本来画像として一致しないという意味で）誤って一致してしまうことがある。これにより、精度の良い画像照合ができない場合があるということである。【００３２】
これは、特徴点三角形面積比を特徴量として用いていることが理由である。この問題は、特に、（１）異なる連結領域（文字）でもほぼ同じ位置に特徴点（重心）が得られてしまう場合や、（２）三角形を構成する３つの特徴点が直線上に配置している場合（特徴点三角形面積比を計算すると０または∞となる場合）に見られる。【００３３】
（１）の場合の理由として、特徴量として重心からのみ計算できる値を用いて特徴量リストを生成していることが挙げられる。特に、ほぼ等間隔で文字が配置されている文字列画像の場合にこのような問題がおきやすい。【００３４】
（２）の場合の理由として、特徴点三角形の面積比を特徴量リストの要素として用いていることが挙げられる。三角形を構成する３つの特徴点が直線上に配置している場合には、特徴点三角形面積比を計算する際の分子（または分母）が０となる。分子（分母）の値が０となる場合、分母（分子）の値にかかわらず、分子（分母）の値が０（∞）となる。これは特徴量リストの誤った一致を引き起こす原因となる。【００３５】
本発明は、以上のような課題を解決するためになされたもので、精度のよい照合を可能にする画像照合装置、画像照合用特徴量格納記憶媒体、画像照合方法および画像照合用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３６】
かかる目的を達成するために、本発明は、以下の特徴を有することとする。【００３７】
本発明の画像照合装置は、画像の指定された領域から画素値の和である累積画素値を計算し、かつ、指定された２つの累積画素値からそれらの比を計算する累積画素値比計算手段を備え、累積画素値比を特徴量とする特徴量リスト（以下、特徴ベクトルと呼ぶ。）を計算するように動作する。このような構成を採用し、累積画素値比から計算される特徴量リストを計算し、登録画像から計算される特徴ベクトルと検索画像から計算される特徴ベクトルについて照合を行い、その照合された特徴ベクトル対の数を利用して画像照合を行うことにより、本発明の目的を達成することができる。【００３８】
なお、同目的は、上記構成の画像照合装置に対応する画像照合方法によっても達成される。【００３９】
また、同目的は、上記の各構成を有する画像照合方法、ならびに対応する装置をコンピュータによって実現するコンピュータ・プログラム、及びそのコンピュータ・プログラムが格納されている、コンピュータ読み取り可能な記憶媒体によっても達成される。
【発明の効果】
【００４０】
本発明によれば、関連する画像照合装置において、特徴点三角形面積比を特徴量として用いる場合に高精度に照合が行えない場合においても、高精度な照合ができる。
その理由は、累積画素値の比を特徴量として用いているので、異なる領域であるにもかかわらずほぼ同じ位置の特徴点が得られたり、特徴点三角形の面積が０となったりする場合の影響を受けないためである。
【発明を実施するための最良の形態】
【００４１】
図１を参照すると、本発明の第１の実施の形態は、登録モジュールにおける連結領域計算モジュールＲ１１と、登録モジュールにおける領域組み合わせ計算モジュールＲ１２と、登録モジュールにおける累積画素値比計算モジュールＲ１３と、登録モジュールにおける累積画素値比格納モジュールＲ１４、検索モジュールにおける連結領域計算モジュールＱ１１と、検索モジュールにおける領域組み合わせ計算モジュールＱ１２と、検索モジュールにおける累積画素値比計算モジュールＱ１３と、検索モジュールにおける累積画素値比一致判定モジュールＱ１４とから構成されている。【００４２】
これらはそれぞれ概略つぎのように動作する。
登録モジュールにおける連結領域計算モジュールＲ１１は、入力される画像から既存の手法を用いて、入力された登録画像から連結領域を抽出する。例えば、入力画像に対して、既存の手法で二値化を行い、既存のラベリング手法を用いて、連結領域のラベリングを行うことで抽出できる。既存の画質改善処理を二値化の前後に行っても良い。これは、連結成分重心が連結成分から計算されることを考慮すれば、背景技術で記載した登録処理の（登録手続きＡ）に相当する処理となる。【００４３】
登録モジュールにおける領域組み合わせ計算モジュールＲ１２は、登録モジュールにおける連結領域計算モジュールＲ１１で計算された連結領域から、連結領域の組み合わせを計算する。連結成分重心が１つの連結成分につき１つ定められることを考慮すると、背景技術で説明した（登録手続きＣ）、（登録手続きＤ）、（登録手続きＥ）、（登録手続きＦ）と同様の手続きで、領域の組み合わせ列が計算できる。ただし（登録手続きＦ）においては、ｆ＝２であるものとする。（登録手続きＤ）に相当する処理において、ｎ個の領域からｍ個の領域を取り出す際に、必ずしもｎ個の領域からｍ個の領域を選択しなくてもよい。例えば、あらかじめ得られている連結領域のうち、いくつか連結領域の和領域を新たな領域として生成し、その領域をｍ個の領域の中に含めることも可能である。【００４４】
登録モジュールにおける累積画素値比計算モジュールＲ１３は、登録モジュールにおける領域組み合わせ計算モジュールＲ１２にて計算された領域の組み合わせ（列）から、特徴ベクトル（特徴量リスト）を計算する。各領域の組み合わせに含まれる２つの領域の面積比を計算することを、領域組み合わせ列に含まれるすべての領域の組み合わせに対して行う。結果として、入力画像が濃淡画像の場合は、領域の組み合わせ列１つにつき、１つの特徴ベクトルが計算される。【００４５】
登録モジュールにおける累積画素値比格納モジュールＲ１４は、登録モジュールにおける累積画素値比計算モジュールＲ１３にて計算された特徴ベクトルを、少なくともその特徴ベクトルが計算された元となる登録画像を一意に指定できる情報とともに、格納する。【００４６】
検索モジュールにおける連結領域計算モジュールＱ１１は、登録モジュールにおける連結領域計算モジュールＲ１１と同様の処理を行う。【００４７】
検索モジュールにおける領域組み合わせ計算モジュールＱ１２は、登録モジュールにおける領域組み合わせ計算モジュールＲ１２と同様の処理を行う。処理中の（登録手続きＥ）に相当する処理では、背景技術で説明した（検索手続きＥ）のように、ｍ個の点をすべてｐ０として選ぶまで処理が継続させてもよい。【００４８】
検索モジュールにおける累積画素値比計算モジュールＱ１３は、登録モジュールにおける累積画素値比計算モジュールＲ１３と同様の処理を行う。【００４９】
検索モジュールにおける累積画素値比計算モジュールＱ１４は、検索モジュールにおける累積画素値比計算モジュールＱ１３により計算された特徴ベクトルと、登録モジュールにおける累積画素値比格納モジュールＲ１４に格納された特徴ベクトルとを比較し、一致するかどうかを判定する。一致するかどうかを判定する手法としては、既存の判定手法、例えば、ベクトル間の相違度（あるいは類似度）を、市街地距離、誤差二乗和、ユークリッド距離、２つのベクトルのなす角度、内積などにより計算し、それらをある閾値よりも相違度が小さい（あるいは類似度が大きい）場合に一致すると判定するようにすればよい。【００５０】
次に、図２及び図４のフローチャートを参照して本実施の形態の全体の動作について詳細に説明する。
処理全体は、登録処理と、検索処理とから構成される。画像照合装置のＣＰＵによりこれらの処理がなされてもよい。【００５１】
最初に、登録処理について説明する。
まず、登録モジュールにおける連結領域計算モジュールＲ１１が、入力される画像から連結領域を計算する（図２のステップＳＲ１１：背景技術の（登録手続きＡ）に相当。）。次に、登録モジュールにおける領域組み合わせ計算モジュールＲ１２は、計算された連結領域の中から注目連結領域ｐを１つ選択し（ステップＳＲ１２：背景技術の（登録手続きＣ）に相当。）、特徴点の近傍にあるｎ個の連結領域からｍ個の連結領域を取り出し（ステップＳＲ１３：背景技術の（登録手続きＤ）に相当）、取り出されたｍ個の連結領域から、その重心が最も注目連結領域ｐの重心に近くなるような連結領域を注目連結領域ｐ０として選んだ上で、ｐの重心を中心とし、ｐ０を先頭として、各連結領域の重心が時計回りに並ぶように連結領域の列Ｌｍを生成し、（ステップＳＲ１４：ほぼ背景技術の（登録手続きＥ）に相当）、Ｌｍから順序を保存してｆ点を選択するすべての連結領域の列Ｌｆを求め、辞書式順序に並べる。（ステップＳＲ１５：背景技術の（登録手続きＦ）に相当）。【００５２】
ここで計算されるＬｆの列は、【００５３】
【数２】
2009110410.tif 000004
であり、各【００５４】
【数３】
2009110410.tif 000005
は、【００５５】
【数４】
2009110410.tif 000006
で表される。ここで【００５６】
【数５】
2009110410.tif 000007
は、連結領域である。連結領域は、連結領域を一意に指定できる番号で表現することとする。図３は領域とその領域の累積画素値の様子を表す図である。なお、簡単のために、上記の説明においては連結領域を利用した方法について述べたが、これは必ずしも連結領域でなくても良い。例えば、２つ以上の連結領域の和領域を【００５７】
【数６】
2009110410.tif 000008
としても良い。【００５８】
さらに、登録モジュールにおける累積画素値比計算モジュールＲ１３は、計算されたＬｆの列から特徴ベクトルを計算する（ステップＳＲ１６）。これは、例えば、Ｌｆの列に対して、【００５９】
【数７】
2009110410.tif 000009
を計算することにより実現される。Ｓ（ｉ）は、連結領域ｉに関する累積画素値である。累積画素値とは、連結領域ｉに属すすべての画素の画素値の和である。画素値が二値で表現されている場合、累積画素値は面積となる。【００６０】
また、当然であるが、特徴ベクトルの累積画素値比は、上記で表現される特徴ベクトルの各要素を逆数とするように計算することも可能である。【００６１】
さらに、登録モジュールにおける累積画素値比格納モジュールＲ１４は、登録モジュールにおける累積画素値比計算モジュールＲ１３で計算された特徴ベクトルを、その登録画像を一意に指定できる情報とともに格納する。【００６２】
次に、検索処理について説明する。
まず、検索モジュールにおける連結領域計算モジュールＱ１１が、入力される画像から連結領域を計算する（図４のステップＳＱ１１）。次に、検索モジュールにおける領域組み合わせ計算モジュールＱ１２が、登録処理と同様に連結領域の列を計算する。図４における各ステップ、ＳＱ１２、ＳＱ１３、ＳＱ１４、ＳＱ１５は、それぞれ登録処理における各ステップ、ＳＲ１２、ＳＲ１３、ＳＲ１４、ＳＲ１５と同じ動作を行う。ここで計算された連結領域の列をＬｆＢで表すこととすると、ＬｆＢは、【００６３】
【数８】
2009110410.tif 000010
であり、各【００６４】
【数９】
2009110410.tif 000011
は、【００６５】
【数１０】
2009110410.tif 000012
で表される。ここで【００６６】
【数１１】
2009110410.tif 000013
は、連結領域である。連結領域は、連結領域を一意に指定できる番号で表現することとする。【００６７】
さらに、検索モジュールにおける累積画素値比計算モジュールＱ１３は、登録モジュールにおける累積画素値比計算モジュールＲ１３と同様に、計算されたＬｆＢから特徴ベクトルを計算する（ステップＳＱ１６）。これは、例えば、ＬｆＢの列に対して、【００６８】
【数１２】
2009110410.tif 000014
を計算することにより実現される。【００６９】
次に、検索モジュールにおける累積画素値比計算モジュールＱ１４が、計算された特徴ベクトルと、登録モジュールにおける累積画素値比格納モジュールＲ１４に格納されたすべての特徴ベクトルのそれぞれとの照合を行い、登録モジュールにおける累積画素値比格納モジュールＲ１４に格納されたそれぞれの特徴ベクトルがＱ１３により計算された特徴ベクトルと一致しているかどうかの判定結果を出力する（ステップＳＱ１７）。【００７０】
以下に、本実施の形態の効果について説明する。
まず、累積画素値比が持つ性質について説明する。例えば、非特許文献２には次のような事実が記載されている。
（非特許文献２）
池山保、平山豊一著「理工系のための微分積分」、裳華房、２００６年３月２５日、ｐ．１３７
（ここから非特許文献２を引用。）【００７１】
【数１３】
2009110410.tif 000015
（引用はここまで。）【００７２】
【数１４】
2009110410.tif 000016
となる。したがって、【００７３】
【数１５】
2009110410.tif 000017
の値は、アフィン変換に拠らない量、すなわちアフィン不変量となる。【００７４】
コンピュータ上で扱う画像は、座標として離散的な値をとる。したがって、二重積分で表される項は、対応する領域における累積画素値の比で近似することが自然である。つまり、累積画素値比は、アフィン不変量（の近似）である。このような量を用いると、登録画像と検索画像との間にアフィン変換が起きたとしても、登録画像のある領域の組み合わせ（列）Ｌｆから計算されたある特徴ベクトルに対して、検索画像中からＬｆに対応する領域の組み合わせ（列）から計算された特徴ベクトルは、理想的には同じ値をとるはずである。【００７５】
ここで、【００７６】
【数１６】
2009110410.tif 000018
なる定数関数を考えると、左辺が検索画像における２つの閉領域Ｄ１、Ｄ２の面積比、右辺が登録画像における２つの閉領域Ａ１、Ａ２の面積比となる。したがって、２つの連結成分の面積比は、アフィン変換に関する不変量（の近似）となる。【００７７】
図５は、一般の濃淡画像の場合（ａ）、二値画像の場合について（ｂ）、領域Ａ、領域Ｂが得られた場合の累積画素値比の計算の様子を示した図である。【００７８】
ここで、【００７９】
【数１７】
2009110410.tif 000019
とすると、画素値が多値の場合（ａ）、
累積画素値比＝（領域Ａの画素値の和）／（領域Ｂの画素値の和）
＝２８／１２
となり、
画素値が二値の場合（ｂ）、
（画素値の和は面積となるので、）
累積画素値比＝（領域Ａの面積の和）／（領域Ｂの面積の和）
＝７／４
となる。【００８０】
本実施の形態では、登録画像と検索画像との双方からアフィン不変量の近似である累積画素値比を要素として特徴ベクトルが構成され、それらの特徴ベクトルが一致するかどうかを判定するというように構成されているため、登録画像と検索画像との間にアフィン変換で記述できる変形が起こっていたとしても、精度良く画像の照合が行える。特に、上述したような、特徴点三角形面積比を用いる関連技術では精度良い認識が行えない場合であっても、累積画素値比を用いることにより精度良く認識することが可能である。【００８１】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。【００８２】
図６を参照すると、本発明の第２の実施の形態は、本発明の第１の実施の形態における構成に加えて、登録モジュールにおける特徴点配置計算モジュールＲ１５、登録モジュールにおける特徴点配置格納モジュールＲ１６、検索モジュールにおける特徴点配置計算モジュールＱ１５、アフィンパラメータ推定部Ａ１、アフィンパラメータ検証部Ａ２から構成される。【００８３】
登録モジュールにおける特徴点配置計算モジュールＲ１５は、登録モジュールにおける領域組み合わせ計算モジュールＲ１２が計算する登録画像連結領域の列Ｌｍに対して、特徴点配置を計算する。例えば、Ｌｍ＝（ｉ１、ｉ２、…、ｉｍ）であるとする。ここで、ｉ１は対応する連結領域を一意に指定する番号である。このとき、登録モジュールにおける特徴点配置計算モジュールＲ１５は、次のような特徴点配置Ｆｍを計算する。【００８４】
【数１８】
2009110410.tif 000020
【００８５】
登録モジュールにおける特徴点配置格納モジュールＲ１６は、登録モジュールにおける特徴点配置計算モジュールＲ１５で計算された特徴点配置Ｆｍを、特徴点配置Ｆｍを計算する元となった領域組み合わせＬｍを一意に指定できる指標とともに格納する。【００８６】
検索モジュールにおける特徴点配置計算モジュールＱ１５は、登録モジュールにおける特徴点配置計算モジュールＲ１５と同様に、検索モジュールにおける領域組み合わせ計算モジュールＱ１２が計算する連結領域の列ＬｍＢに対して、特徴点配置を計算する。計算される特徴点配置ＦｍＢを【００８７】
【数１９】
2009110410.tif 000021
とする。【００８８】
図７は、領域とその領域から計算される特徴点の様子を表す図である。なお、本実施の形態においては、１つの（連結）領域から、特徴点として重心を計算するように説明しているが、必ずしも重心でなくてもよい。また、１つの領域から１つの特徴点を抽出するように限る必要はなく、登録画像から計算される特徴点の数と、検索画像から計算される特徴点の数が同じになる方法であればそれを適用することが可能である。【００８９】
アフィンパラメータ推定部Ａ１は、登録モジュールにおける特徴点配置格納モジュールＲ１６に格納されている特徴点配置の１つを取得し、それと検索モジュールにおける特徴点配置計算モジュールＱ１５により計算された特徴点配置の１つとから、アフィンパラメータを求める。アフィンパラメータを求めるには、例えば、次のような方法を用いる。【００９０】
【数２０】
2009110410.tif 000022
を用いると、α＝Ｘβとあらわすことができる。アフィンパラメータを推定する問題は、βを推定する問題となる。【００９１】
βの推定値【００９２】
【数２１】
2009110410.tif 000023
は、最小二乗法を用いれば、【００９３】
【数２２】
2009110410.tif 000024
で求めることができる。【００９４】
【数２３】
2009110410.tif 000025
【００９５】
また、【００９６】
【数２４】
2009110410.tif 000026
のように、各ｋに対して計算された市街地距離の和で求められる値であってもよい。また、より一般に各ｋに対して計算される何らかの相違度（類似度）を引数とする関数値がある閾値よりも小さい（大きい）場合に一致すると判定することもできる。【００９７】
また、検索モジュールにおける累積画素値比一致判定モジュールＱ４にて計算された相違度（あるいは類似度）とこれらの値を合わせて利用する照合を行っても良い。【００９８】
次に、図８及び図９、図１０のフローチャートを参照して本発明の第２の実施の形態の全体の動作について詳細に説明する。
処理全体は、登録処理と、検索処理とから構成される。画像照合装置のＣＰＵによりこれらの処理がなされてもよい。【００９９】
最初に、登録処理について説明する。本発明の第２の実施の形態における登録処理は、本発明の第１の実施の形態における登録処理とほぼ同じである。従って、本発明の第１の実施の形態と相違する処理のみ、すなわち図８におけるステップＳＲＢ１４およびＳＲＢ１７を説明する。【０１００】
ステップＳＲＢ１４では、本発明の第１の実施の形態におけるステップＳＲ１４における処理が行われた後、登録モジュールにおける特徴点配置計算モジュールＲ１５が、Ｌｍから特徴点配置Ｆｍを計算する。計算されたＦｍは、登録モジュールにおける特徴点配置計算モジュールＲ１６に格納される。【０１０１】
ステップＳＲＢ１７では、本発明の第１の実施の形態におけるステップＳＲ１７における処理が行われた後、特徴ベクトルが計算される元となったＬｍを一意に指定できる情報があわせて格納される。【０１０２】
次に、検索処理について説明する。本発明第２の実施の形態における検索処理は、本発明の第１の実施の形態における検索処理とほぼ同じである。従って、本発明の第１の実施の形態と相違する処理のみ、すなわち図９におけるステップＳＱＢ１７のみ説明する。【０１０３】
ステップＳＱＢ１７の処理について、図１０を用いて説明する。【０１０４】
まず、ステップＳＱＢ１７１では、検索モジュールにおける累積画素値比一致判定モジュールＱ１４が登録画像から計算された特徴ベクトルと検索画像から計算された特徴ベクトルとの間の類似度を計算する。【０１０５】
ステップＳＱＢ１７２では、ステップＳＱＢ１７１にて計算された相違度（あるいは類似度）があらかじめ定められる範囲内にあるかを判定する。この場合、相違度（類似度）がある値より小さい（大きい）場合に一致すると判定できるように範囲を決めておくことが一つの方法である。あらかじめ定められる範囲内にある場合はステップＳＱＢ１７３へ、そうでない場合にはステップＳＱＢ１７７へ進む。【０１０６】
ステップＳＱＢ１７３では、検索モジュールにおける特徴点配置計算モジュールＱ１５が特徴点配置ＦｍＢを計算する。【０１０７】
ステップＳＱＢ１７４では、アフィンパラメータ推定部Ａ１が、現在照合を行っている登録画像から計算された特徴ベクトルを生成する元となった領域組み合わせＬｍから計算した特徴点配置Ｆｍを取得する。【０１０８】
ステップＳＱＢ１７５では、アフィンパラメータ検証部Ａ２が、ＦｍとＦｍＢとからアフィンパラメータを推定する。【０１０９】
ステップＳＱＢ１７６では、アフィンパラメータ検証部Ａ２が、最終的に一致するかどうかの判定を判定し、その結果を出力する。【０１１０】
ステップＳＱＢ１７７では、検索モジュールにおける累積画素値比一致判定モジュールＱ１４が、最終結果として不一致を出力する。【０１１１】
次に、本発明の第２の実施の形態の効果について説明する。
本発明の第２の実施の形態では、累積画素値比を要素とする特徴ベクトルを照合に加えて、特徴ベクトルを構成する元の領域組み合わせから特徴点配置を構成し、特徴点配置をも利用して照合が行えるように構成されているため、より高精度な照合が可能である。【０１１２】
特に、図１１のような画像Ｉが登録画像として、画像ＩＢが検索画像として与えられており、ある特徴ベクトルを計算する元となった領域の組み合わせが、図中に図示されたように、ある領域が個々に移動して得られている場合を考える。（ｍ＝６の例に相当する。）この場合、累積画素値比を要素とする特徴ベクトルは、登録画像Ｉと検索画像ＩＢとで同じ値をとるため、一致と判定される。しかしながら、これらの画像は一致しないと考えるのが自然である。このような誤りが起こる要因は、特徴ベクトルとして各領域の面積の情報から計算される値のみを利用しているためである。【０１１３】
本発明の第２の実施の形態においては、面積だけでなく、図１２に図示されているような画像Ｉと画像ＩＢの双方から抽出された特徴点を利用することにより、領域の位置に関する情報をも照合に利用できるため、図１１のような場合においても、高精度な照合が可能となる。【０１１４】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
図１３を参照すると、本発明の第３の実施の形態は、本発明の第１の実施の形態における構成に加えて、登録モジュールにおける三角形面積比計算モジュールＲ１７、登録モジュールにおける三角形面積比格納モジュールＲ１８、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６、不変量検証部Ｑ１７から構成される。【０１１５】
登録モジュールにおける三角形面積比計算モジュールＲ１７は、背景技術における（登録手続きＧ）と同様の手続きで、登録画像から計算された特徴点の列Ｌｆから不変量の列を計算する。【０１１６】
登録モジュールにおける三角形面積比格納モジュールＲ１８は、登録モジュールにおける三角形面積比計算モジュールＲ１５にて計算された不変量の列を、画像番号および不変量の列を計算する元となった連結領域の列Ｌｍを一意に指定できる指標とともに、格納する。【０１１７】
検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６は、背景技術における（登録手続きＧ）と同様の手続きで、検索画像から計算された特徴点の列Ｌｆから不変量の列を計算する。【０１１８】
不変量検証部Ｑ１７は、登録モジュールにおける三角形面積比計算モジュールＲ１５にて計算された不変量の列と、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６にて計算された不変量の列を特徴ベクトルとみなし、検索モジュールにおける累積画素値比計算モジュールＱ１４が持つ機能において説明した相違度（または類似度）を計算し、その値を利用して一致しているかどうかを判定する。例えば、Ｑ１７にて計算される相違度（類似度）があらかじめ定められた範囲内の値をとる場合に一致したとみなし、それ以外の場合は不一致であると判定すればよい。また、Ｑ１４にて計算された相違度（類似度）を合わせて照合に利用することもできる。【０１１９】
次に、図１４及び図１５、図１６のフローチャートを参照して本発明の第３の実施の形態の全体の動作について詳細に説明する。
処理全体は、登録処理と、検索処理とから構成される。画像照合装置のＣＰＵによりこれらの処理がなされてもよい。【０１２０】
最初に、登録処理について説明する。本発明の第３の実施の形態における登録処理は、本発明の第１の実施の形態における登録処理とほぼ同じである。従って、本発明の第１の実施の形態と相違する処理のみ、すなわち図１４におけるステップＳＲＣ１４およびＳＲＣ１７を説明するについて説明する。【０１２１】
ステップＳＲＣ１４では、本発明の第１の実施の形態におけるステップＳＲ１４における処理が行われた後、登録モジュールにおける特徴点配置計算モジュールＲ１５が、Ｌｍから不変量の列を計算する。計算された不変量の列は、登録モジュールにおける三角形面積比格納モジュールＲ１８に格納される。【０１２２】
ステップＳＲＣ１７では、本発明の第１の実施の形態におけるステップＳＲ１７における処理が行われた後、特徴ベクトルが計算される元となったＬｍから計算される不変量の列を一意に指定できる情報があわせて格納される。【０１２３】
次に、検索処理について説明する。本発明の第３の実施の形態における検索処理は、本発明の第１の実施の形態における検索処理とほぼ同じである。従って、本発明の第１の実施の形態と相違する処理のみ、すなわち、図１５におけるステップＳＱＣ１７のみ説明する。【０１２４】
図１６を参照して、ステップＳＱＣ１７について説明する。
まず、ステップＳＱＣ１７１は、ステップＳＱＢ１７１の処理と同一である。【０１２５】
ステップＳＱＣ１７２は、ステップＳＱＣ１７１にて計算された相違度（あるいは類似度）があらかじめ定められる範囲内にあるかを判定する。この場合、相違度（類似度）がある値より小さい（大きい）場合に一致すると判定できるように範囲を決めておくことが一つの方法である。あらかじめ定められる範囲内にある場合はステップＳＱＣ１７３へ、そうでない場合にはステップＳＱＣ１７７へ進む。【０１２６】
ステップＳＱＣ１７３では、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６が不変量の列を計算する。この処理にはこれまでの手法を用いることができる。なお、これまでの手法の説明においては、１つの（連結）領域から、特徴点として重心を計算するように説明しているが、必ずしも重心でなくてもよい。また、１つの領域から１つの特徴点を抽出するように限る必要はなく、登録画像から計算される特徴点の数と、検索画像から計算される特徴点の数が同じになる方法であればそれを適用することが可能である。【０１２７】
ステップＳＱＣ１７４では、不変量検証部Ｑ１７が、現在照合を行っている登録画像から計算された特徴ベクトルを生成する元となった領域組み合わせＬｍから計算した不変量の列を取得する。【０１２８】
ステップＳＱＣ１７５では、不変量検証部Ｑ１７が、一致しているかどうかの判定結果を出力する。【０１２９】
ステップＳＱＣ１７７では、不変量検証部Ｑ１７が、最終結果として一致であるか不一致であるかを出力する。【０１３０】
次に、本発明の第３の実施の形態の効果について説明する。
本発明の第３の実施の形態では、累積画素値比を要素とする特徴ベクトルを照合に加えて、特徴ベクトルを構成する元の領域組み合わせから特徴点配置を構成し、特徴点配置から特徴点三角形面積比を不変量として計算される不変量の列を用いて照合が行えるように構成されている。【０１３１】
本発明の第２の実施の形態と同様に、面積だけでなく、領域の位置に関する情報をも照合に利用できるため、より高精度な照合が可能となる。【０１３２】
なお、第２の実施の形態におけるアフィンパラメータの推定および検証と、第３の実施の形態における不変量による検証は独立して付加することができる処理である。したがって、第１の実施の形態にアフィンパラメータの推定及び検証と、不変量による検証の双方を付加することにより、新たな実施の形態が構成可能であることを付記しておく。【０１３３】
以上の説明は、入力画像が（二値を含む）濃淡画像の場合についての説明である。
入力画像がカラー画像の場合は、画像中の各画素について、色空間上の点から濃淡値を計算する手続きにより、カラー画像から１枚の濃淡画像を作成する方法を構成すれば、本発明が適用できるようになる。【０１３４】
また、既存の手法でカラー画像から複数の濃淡画像を作成し、それらを利用した照合を行うこともできる。【０１３５】
例えば、次のような手法が可能である。【０１３６】
まず、登録モジュールにおける累積画素値比計算モジュールＲ１３、検索モジュールにおける累積画素値比計算モジュールＱ１３、登録モジュールにおける特徴点配置計算モジュールＲ１５、検索モジュールにおける特徴点配置計算モジュールＱ１５、登録モジュールにおける三角形面積比計算モジュールＲ１７、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１５では、それぞれの濃淡画像から計算が行われる。【０１３７】
登録モジュールにおける累積画素値比格納モジュールＲ１４、登録モジュールにおける特徴点配置格納モジュールＲ１６、登録モジュールにおける三角形面積比格納モジュールＲ１８では、複数の画像から計算された値が格納される。【０１３８】
そうしておけば、検索モジュールにおける累積画素値比計算モジュールＱ１４、アフィンパラメータ推定部Ａ１、アフィンパラメータ検証部Ａ２、不変量検証部Ｑ１７が持つ機能を複数回動作させることで、同じ領域組み合わせについて、複数の画像における照合が可能となる。【０１３９】
例えば、ＲＧＢ空間における、Ｒ値が表す濃淡画像Ｒ、Ｇ値が表す濃淡画像Ｇ、Ｂ値が表す濃淡画像Ｂの３画像を用いる場合は、濃淡画像Ｒから計算された特徴ベクトル同士による照合と、濃淡画像Ｇから計算された特徴ベクトル同士による照合と、濃淡画像Ｂから計算された特徴ベクトル同士による照合を行うことができる。照合結果としては、すべての濃淡画像において計算された特徴ベクトル同士が一致であった場合に、最終的に一致したと判定する。また、あらかじめ定められた数以上の濃淡画像における特徴ベクトル同士が一致した場合に、最終的に一致したとすることもできる。あらかじめ定められた数が２の場合は、例えば、濃淡画像Ｒにおける特徴ベクトル同士が一致し、かつ、濃淡画像Ｂにおける特徴ベクトル同士が一致した場合に、最終的に一致したとすることになる。ここでは、色空間から複数の濃淡画像を生成する方法として、ＲＧＢ各成分が表す濃淡画像を例に取ったが、これに限る必要はない。【０１４０】
複数の濃淡画像を作る方法としては、入力される画像がカラー画像の場合は、ＲＧＢ空間、ＸＹＺ空間、ＬＡＢ空間、ＬＵＶ空間、ＹＩＱ空間など既存の色空間における各成分についての濃淡画像を利用することができる。もちろん、これに限らず、色空間における画素値の組を１次元の濃淡値に変換する関数を複数用意しておけば、複数の濃淡画像が得られる。【０１４１】
複数の濃淡画像は、画像が入力された時点で計算しておいてもよいし、特徴ベクトルあるいは不変量リストの列が計算される直前に計算するのでもよい。【０１４２】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
図１７に示すように、第１の実施例においては、本発明の第１の実施の形態の画像照合装置、もしくは、本発明の第２の実施の形態の画像照合装置、もしくは、本発明の第３の実施の形態の画像照合装置に加えて、最終一致判定部Ｑ３から構成される。なお、図１７中の結果出力部Ｑ２は、本発明の第１の実施の形態の画像照合装置においては検索モジュールにおける累積画素値比一致判定モジュールＱ１４、本発明の第２の実施の形態の画像照合装置においてはアフィンパラメータ検証部Ａ２、本発明の第３の実施の形態の画像照合装置においては不変量検証部Ｑ１７のことを指す。いずれも、登録画像から計算された領域の組み合わせと検索画像から計算された領域の組み合わせ１対に対し、一致または不一致１回を１回出力する点で共通である。【０１４３】
最終一致判定部Ｑ３は、まず、結果出力部Ｑ２から一致が出力された数を、登録画像に応じて別々に計数する。例えば、登録画像ＲＩｒのある領域の組み合わせと検索画像のある領域の組み合わせが一致であった場合に、一致数Ｃｒを１だけ増加させる。照合開始前に各Ｃｒをすべて０で初期化しておけば、結果として、登録画像ＲＩｒに対して、一致数がＣｒ個であるというように計数される。次に、この値を用いて、最終的に検索画像に対応する登録画像がどの画像であるかを判定し、登録画像を一意に指定できる情報を出力する。例えば、Ｃｒの値が最も大きい登録画像ＲＩｒを用いることもできるし、背景技術で説明したような計算式を使って、各画像のスコアを求め、その値を利用して照合を行ってもよい。もちろん、Ｃｒあるいはスコアが同点のものがあれば結果を棄却としてもよい。また、Ｃｒの数があらかじめ定めた値よりも小さい場合、スコアがあらかじめ定めた範囲に入っていない場合について結果を棄却とすることも考えられる。【０１４４】
最終一致判定部Ｑ３は、すべての登録画像に対するすべての領域組み合わせと、検索画像に対するすべての領域組み合わせについての一致判定が終了した後に動作する。【０１４５】
このような画像照合装置は、図１８のような一つの計算機で構成することができることを説明した。すなわち、計算機上のメモリ（ＲＡＭ２）に本発明の画像照合機能を搭載したプログラムを搭載し、動作させるような構成として説明した。【０１４６】
つまり、上述した各実施形態を例に説明した本発明は、上述した画像照合装置に対して、その説明において参照したフローチャートの機能を実現可能なコンピュータ・プログラムを供給した後、そのコンピュータ・プログラムを、当該装置のＣＰＵ１に読み出して実行することにより達成される。【０１４７】
また、当該装置内に供給されたコンピュータ・プログラム、特徴を含むデータ、画像データは、読み書き可能なＲＡＭ２またはハードディスク３等の記憶媒体に格納すれば良い。そして、このような場合において、本発明は、係るコンピュータ・プログラムのコード或いは記憶媒体によって構成される。【０１４８】
もちろん、本発明の画像照合機能をハードウェア化した計算機を構成することも可能である。また、一部の機能をハードウェアで実現し、それらのハードウェアとソフトウェア・プログラムの協調動作により同様の機能を実現してもよい。登録画像および検索画像は、あらかじめ撮像手段で撮像した画像を計算機内のメモリあるいはハードディスク３に蓄えておいても良いし、（図示しない）別の計算機との通信回線により取得してもよい。また、入力装置として１つ以上の撮像装置と、撮像装置と計算機とをつなぐ通信線を付け加えることも可能である。【０１４９】
また、本発明の機能は、図１９のように、複数の計算機上に分散させて構成することも可能である。例えば、第１の実施の形態の画像照合装置を用いた第１の実施例においては、計算機ＣｏｍＡが、登録モジュールにおける連結領域計算モジュールＲ１１、登録モジュールにおける領域組み合わせ計算モジュールＲ１２、登録モジュールにおける累積画素値比計算モジュールＲ１３を、計算機ＣｏｍＣが登録モジュールにおける累積画素値比格納モジュールＲ１４を、計算機ＣｏｍＢが、検索モジュールにおける連結領域計算モジュールＱ１１、検索モジュールにおける領域組み合わせ計算モジュールＱ１２、検索モジュールにおける累積画素値比計算モジュールＱ１３、検索モジュールにおける累積画素値比一致判定モジュールＱ１４、最終一致判定部Ｑ３を含むよう構成すればよい。第２の実施の形態の画像照合装置を用いた本発明の第１の実施例においては、計算機ＣｏｍＡが、登録モジュールにおける連結領域計算モジュールＲ１１、登録モジュールにおける領域組み合わせ計算モジュールＲ１２、登録モジュールにおける累積画素値比計算モジュールＲ１３、登録モジュールにおける特徴点配置計算モジュールＲ１５を、計算機ＣｏｍＣが登録モジュールにおける累積画素値比格納モジュールＲ１４、登録モジュールにおける特徴点配置格納モジュールＲ１６を、計算機ＣｏｍＢが検索モジュールにおける連結領域計算モジュールＱ１１、検索モジュールにおける領域組み合わせ計算モジュールＱ１２、検索モジュールにおける累積画素値比計算モジュールＱ１３、検索モジュールにおける累積画素値比一致判定モジュールＱ１４、検索モジュールにおける特徴点配置計算モジュール１５、アフィンパラメータ推定部Ａ１、アフィンパラメータ検証部Ａ２、最終一致判定部Ｑ３を含むように構成すればよい。第３の実施の形態の画像照合装置を用いた本発明の第１の実施例においては、計算機ＣｏｍＡが、登録モジュールにおける連結領域計算モジュールＲ１１、登録モジュールにおける領域組み合わせ計算モジュールＲ１２、登録モジュールにおける累積画素値比計算モジュールＲ１３、登録モジュールにおける三角形面積比計算モジュールＲ１７を、計算機ＣｏｍＣが登録モジュールにおける累積画素値比格納モジュールＲ１４、登録モジュールにおける三角形面積比格納モジュールＲ１８を、計算機ＣｏｍＢが検索モジュールにおける連結領域計算モジュールＱ１１、検索モジュールにおける領域組み合わせ計算モジュールＱ１２、検索モジュールにおける累積画素値比計算モジュールＱ１３、検索モジュールにおける累積画素値比一致判定モジュールＱ１４、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６、不変量検証部Ｑ１７、最終一致判定部Ｑ３を含むように構成すればよい。【０１５０】
このようにすれば、例えば、次のような動作が可能である。
まず、登録画像は撮像装置ＳｃＡを用いて撮像される。
撮像された登録画像は計算機ＣｏｍＡにより計算され、計算されたデータが計算機ＣｏｍＣに格納される【０１５１】
次に、検索画像は撮像装置ＳｃＢを用いて撮像され、撮像された検索画像は計算機ＣｏｍＢにより計算される。【０１５２】
最後に計算機ＣｏｍＢは、計算機ＣｏｍＣに格納されたデータと比較照合することにより画像照合を行う。【０１５３】
この例においては、登録処理を行う計算機、検索処理を行う計算機、格納を行う計算機はそれぞれ１台ずつで構成されているが、必ずしも１台に限らず、複数用意してもよい。また、格納を行う装置は、必ずしも計算機である必要は無く、ハードディスク、ＣＤ、ＤＶＤ、フラッシュメモリなど、データを格納する機能を有していればよい。また、登録処理と検索処理の双方を行うような計算機を用いても良い。また、登録処理を行う計算機と、検索処理を行う計算機とは必ずしも接続される必要なない。例えば、一方の計算機で計算されたデータを別の計算機にデータを利用するために、特徴量データを含む情報が格納された記憶媒体などを利用して、データのコピーを行っても良い。【０１５４】
以上、発明について詳細に説明した。ここで説明したのは、あくまで一例である。したがって、構成や動作などに一部に異なるところがあっても、本質的に同様に照合を行う場合は本発明と同一であるとみなすべきである。【０１５５】
なお、この出願は、２００８年３月４日に出願した、日本特許出願番号２００８−０５３９２５号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１５６】
本発明は、例えば、一般の画像、特に文書画像に関する画像照合装置、あるいは画像照合用プログラムといった用途に適用できる。また、文書に検索するために特徴的な領域を入力画像とするように構成することによる画像照合装置の応用、例えば、郵便物画像における住所等の文字列画像を入力とする画像検索、あらかじめ画像検索のために設計された識別子をあらかじめ付与した画像に対する検索といった用途にも適用可能である。
【図面の簡単な説明】
【０１５７】
【図１】本発明の第１の実施の形態におけるモジュール構成を示す図である。
【図２】本発明の第１の実施の形態における登録処理を説明するためのフローチャートである。
【図３】領域とその領域の累積画素値の様子の一例を表す図である。
【図４】本発明の第１の実施の形態における検索処理を説明するためのフローチャートである。
【図５】累積画素値比の計算の様子の一例を示した図である。
【図６】本発明の第２の実施の形態におけるモジュール構成を示す図である。
【図７】領域とその領域から計算される特徴点の様子の一例を表す図である。
【図８】本発明の第２の実施の形態における登録処理を説明するためのフローチャートである。
【図９】本発明の第２の実施の形態における検索処理を説明するためのフローチャートである。
【図１０】本発明の第２の実施の形態における検索処理中のステップＳＱＢ１７の処理を説明するためのフローチャートである。
【図１１】本発明の第２の実施の形態における特有の効果を説明するための登録画像および検索画像の例である。
【図１２】２つの画像について、領域とその領域から計算される特徴点の様子の一例を表す図である。
【図１３】本発明の第３の実施の形態におけるモジュール構成を示す図である。
【図１４】本発明の第３の実施の形態における登録処理を説明するためのフローチャートである。
【図１５】本発明の第３の実施の形態における検索処理を説明するためのフローチャートである。
【図１６】本発明の第３の実施の形態における検索処理中のステップＳＱＣ１７の処理を説明するためのフローチャートである。
【図１７】本発明の第１の実施例の構成を示すための図である。
【図１８】本発明の第１の実施の形態を実行するためのハードウェア資源の例を表した図である。
【図１９】本発明の機能を複数の計算機上に分散させて構成した例である。
【図１】
2009110410.tif 000027
【図２】
2009110410.tif 000028
【図３】
2009110410.tif 000029
【図４】
2009110410.tif 000030
【図５】
2009110410.tif 000031
【図６】
2009110410.tif 000032
【図７】
2009110410.tif 000033
【図８】
2009110410.tif 000034
【図９】
2009110410.tif 000035
【図１０】
2009110410.tif 000036
【図１１】
2009110410.tif 000037
【図１２】
2009110410.tif 000038
【図１３】
2009110410.tif 000039
【図１４】
2009110410.tif 000040
【図１５】
2009110410.tif 000041
【図１６】
2009110410.tif 000042
【図１７】
2009110410.tif 000043
【図１８】
2009110410.tif 000044
【図１９】
2009110410.tif 000045
【手続補正書】
【提出日】平成21年9月2日(2009.9.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
照合対象となる第１の画像と第２の画像について、前記第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、前記組から計算される特徴量を用いて前記第１の画像と前記第２の画像を照合する画像照合装置であって、
前記部分領域として、前記第１の画像および前記第２の画像を二値化してそれぞれの画像中の連結領域を求める連結領域計算手段と、
前記組として、同一画像中で互いに近傍に存在する、前記連結領域もしくは２つ以上の前記連結領域の和領域、の組を求める領域組み合わせ計算手段と、
前記特徴量として、前記組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された前記累積画素値の比を計算する、累積画素値比計算手段と
前記第１の画像から得られた前記特徴量と前記第２の画像から得られた前記特徴量とが一致するかどうかを判定する累積画素値比一致判定手段と
を含むことを特徴とする画像照合装置。
【請求項２】
前記累積画素値比計算手段は、累積画素値を計算する際に、画素値として二値を利用することを特徴とする請求項１に記載された画像照合装置。
【請求項３】
前記累積画素値比計算手段は、累積画素値を計算する際に、画素値として濃淡画像における画素値を利用することを特徴とする請求項１に記載された画像照合装置。
【請求項４】
前記累積画素値比計算手段は、累積画素値を計算する際に、画素値としてカラー画像中の各画素における画素情報を基に計算された値を画素値として利用することを特徴とする請求項１に記載された画像照合装置。
【請求項５】
前記カラー情報を表す画素情報を元に画素値を計算する手段を１つ以上備え、カラー画像から計算される１つ以上の種類の濃淡画像のそれぞれに対して前記累積画素値比計算手段を利用した照合を行い、あらかじめ定められた数の濃淡画像について画像照合結果が一致と判定された場合に、画像として一致したと判定することを特徴とする請求項１に記載された画像照合装置。
【請求項６】
前記累積画素値比計算手段により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算する特徴点配置計算手段と、
前記特徴点配置計算手段により計算された特徴点配置を用いてアフィンパラメータを推定するアフィンパラメータ推定手段と、
前記アフィンパラメータにより計算された値を用いて特徴点配置の当てはまりのよさを検証するアフィンパラメータ検証手段と
を含むことを特徴とする請求項１に記載された画像照合装置。
【請求項７】
前記累積画素値比計算手段により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、アフィンパラメータ推定手段と、アフィンパラメータ検証手段とが動作することを特徴とする請求項６に記載された画像照合装置。
【請求項８】
前記累積画素値比計算手段により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算し、特徴点配置から特徴点三角形面積比である不変量の組を計算する特徴点三角形面積比計算手段と、
少なくとも前記特徴点三角形面積比計算手段により計算された特徴点三角形面積比である不変量を用いて検証を行う不変量検証手段と
を含むことを特徴とする請求項１に記載された画像照合装置。
【請求項９】
前記累積画素値比計算手段により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、不変量検証手段が動作することを特徴とする請求項８に記載された画像照合装置。
【請求項１０】
検索される画像に対応する登録画像を検索または同定するための結果を出力する最終一致判定手段を備えることを特徴とする請求項１乃至９のいずれか１項に記載の画像照合装置。
【請求項１１】
請求項１乃至１０のいずれか１項に記載の画像照合装置により計算される特徴量を含むデータを格納した画像照合用特徴量格納記憶媒体。
【請求項１２】
照合対象となる第１の画像と第２の画像について、前記第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、前記組から計算される特徴量を用いて前記第１の画像と前記第２の画像を照合する画像照合方法であって、
連結領域計算手段によって、前記部分領域として、前記第１の画像および前記第２の画像を二値化してそれぞれの画像中の連結領域を求めるステップと、
領域組み合わせ計算手段によって、前記組として、同一画像中で互いに近傍に存在する、前記連結領域もしくは２つ以上の前記連結領域の和領域、の組を求めるステップと、
累積画素値比計算手段によって、前記特徴量として、前記組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された前記累積画素値の比を計算するステップと
累積画素値比一致判定手段によって、前記第１の画像から得られた前記特徴量と前記第２の画像から得られた前記特徴量とが一致するかどうかを判定するステップと
を有することを特徴とする画像照合方法。
【請求項１３】
コンピュータに、
照合対象となる第１の画像と第２の画像について、前記第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、前記組から計算される特徴量を用いて前記第１の画像と前記第２の画像を照合する処理を実行させるプログラムであって、
前記部分領域として、前記第１の画像および前記第２の画像を二値化してそれぞれの画像中の連結領域を求める連結領域計算処理と、
前記組として、同一画像中で互いに近傍に存在する、前記連結領域もしくは２つ以上の前記連結領域の和領域、の組を求める領域組み合わせ計算処理と、
前記特徴量として、前記組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された前記累積画素値の比を計算する、累積画素値比計算処理と
前記第１の画像から得られた前記特徴量と前記第２の画像から得られた前記特徴量とが一致するかどうかを判定する累積画素値比一致判定処理とを実行させることを特徴とするプログラム。
【請求項１４】
前記累積画素値比計算処理で、累積画素値を計算する際に、画素値として二値を利用することを特徴とする請求項１３に記載されたプログラム。
【請求項１５】
前記累積画素値比計算処理で、累積画素値を計算する際に、画素値として濃淡画像における画素値を利用することを特徴とする請求項１３に記載されたプログラム。
【請求項１６】
前記累積画素値比計算処理で、累積画素値を計算する際に、画素値としてカラー画像中の各画素における画素情報を基に計算された値を画素値として利用することを特徴とする請求項１３に記載されたプログラム。
【請求項１７】
前記カラー情報を表す画素情報を元に画素値を計算する処理を実行させ、カラー画像から計算される１つ以上の種類の濃淡画像のそれぞれに対して前記累積画素値比計算処理を利用した照合を行い、あらかじめ定められた数の濃淡画像について画像照合結果が一致と判定された場合に、画像として一致したと判定する処理を実行させることを特徴とする請求項１３に記載されたプログラム。
【請求項１８】
前記累積画素値比計算処理により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算する特徴点配置計算処理と、
前記特徴点配置計算処理により計算された特徴点配置を用いてアフィンパラメータを推定するアフィンパラメータ推定処理と、
前記アフィンパラメータにより計算された値を用いて特徴点配置の当てはまりのよさを検証するアフィンパラメータ検証処理と
を実行させることを特徴とする請求項１３に記載されたプログラム。
【請求項１９】
前記累積画素値比計算処理により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、アフィンパラメータ推定処理と、アフィンパラメータ検証処理とが実行されることを特徴とする請求項１８に記載されたプログラム。
【請求項２０】
前記累積画素値比計算処理により計算された特徴量を計算するために用いた前記領域の組から特徴点配置を計算し、特徴点配置から特徴点三角形面積比である不変量の組を計算する特徴点三角形面積比計算処理と、
少なくとも前記特徴点三角形面積比計算処理により計算された特徴点三角形面積比である不変量を用いて検証を行う不変量検証処理と
を実行させることを特徴とする請求項１３に記載されたプログラム。
【請求項２１】
前記累積画素値比計算処理により計算される前記特徴量を用いた照合により特徴量が一致したと判定された場合に、不変量検証処理を実行させることを特徴とする請求項２０に記載されたプログラム。
【請求項２２】
検索される画像に対応する登録画像を検索または同定するための結果を出力する最終一致判定処理を実行させることを特徴とする請求項１３乃至２１のいずれか１項に記載のプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
合には、特徴点三角形面積比を計算する際の分子（または分母）が０となる。分子（分母）の値が０となる場合、分母（分子）の値にかかわらず、分子（分母）の値が０（∞）となる。これは特徴量リストの誤った一致を引き起こす原因となる。
［００３５］
本発明は、以上のような課題を解決するためになされたもので、精度のよい照合を可能にする画像照合装置、画像照合用特徴量格納記憶媒体、画像照合方法および画像照合用プログラムを提供することを目的とする。
課題を解決するための手段
［００３６］
かかる目的を達成するために、本発明は、以下の特徴を有することとする。
［００３７］
本発明の画像照合装置は、照合対象となる第１の画像と第２の画像について、第１および第２の画像中の部分領域から複数の部分領域を領域の組として求め、組から計算される特徴量を用いて第１の画像と第２の画像を照合する画像照合装置であって、部分領域として、第１の画像および第２の画像を二値化してそれぞれの画像中の連結領域を求める連結領域計算手段と、組として、同一画像中で互いに近傍に存在する、連結領域もしくは２つ以上の連結領域の和領域、の組を求める領域組み合わせ計算手段と、特徴量として、組に属する２つの部分領域における画素値の和である累積画素値を計算し、計算された累積画素値の比を計算する、累積画素値比計算手段と第１の画像から得られた特徴量と第２の画像から得られた特徴量とが一致するかどうかを判定する累積画素値比一致判定手段とを含む。このような構成を採用し、累積画素値比から計算される特徴量リストを計算し、登録画像から計算される累積画素値比を特徴量とする特徴量リスト（以下、特徴ベクトルと呼ぶ。）と検索画像から計算される特徴ベクトルについて照合を行い、その照合された特徴ベクトル対の数を利用して画像照合を行うことにより、本発明の目的を達成することができる。
［００３８］
なお、同目的は、上記構成の画像照合装置に対応する画像照合方法によっても達成される。
［００３９］
また、同目的は、上記の各構成を有する画像照合方法、ならびに対応する装置をコンピュータによって実現するコンピュータ・プログラム、及びそのコンピュータ・プログラムが格納されている、コンピュータ読み取り可能な記憶媒体によっても達成される。
発明の効果
［００４０］
本発明によれば、関連する画像照合装置において、特徴点三角形面積比を特徴量として用いる場合に高精度に照合が行えない場合においても、高精度な照合ができる。
その理由は、累積画素値の比を特徴量として用いているので、異なる領域であるにもかかわらずほぼ同じ位置の特徴点が得られたり、特徴点三角形の面積が０となったりする場合の影響を受けないためである。
発明を実施するための最良の形態
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
み合わせに対して行う。結果として、入力画像が濃淡画像の場合は、領域の組み合わせ列１つにつき、１つの特徴ベクトルが計算される。
［００４５］
登録モジュールにおける累積画素値比格納モジュールＲ１４は、登録モジュールにおける累積画素値比計算モジュールＲ１３にて計算された特徴ベクトルを、少なくともその特徴ベクトルが計算された元となる登録画像を一意に指定できる情報とともに、格納する。
［００４６］
検索モジュールにおける連結領域計算モジュールＱ１１は、登録モジュールにおける連結領域計算モジュールＲ１１と同様の処理を行う。
［００４７］
検索モジュールにおける領域組み合わせ計算モジュールＱ１２は、登録モジュールにおける領域組み合わせ計算モジュールＲ１２と同様の処理を行う。処理中の（登録手続きＥ）に相当する処理では、背景技術で説明した（検索手続きＥ）のように、ｍ個の点をすべてｐ０として選ぶまで処理が継続させてもよい。
［００４８］
検索モジュールにおける累積画素値比計算モジュールＱ１３は、登録モジュールにおける累積画素値比計算モジュールＲ１３と同様の処理を行う。
［００４９］
検索モジュールにおける累積画素値比一致判定モジュールＱ１４は、検索モジュールにおける累積画素値比計算モジュールＱ１３により計算された特徴ベクトルと、登録モジュールにおける累積画素値比格納モジュールＲ１４に格納された特徴ベクトルとを比較し、一致するかどうかを判定する。一致するかどうかを判定する手法としては、既存の判定手法、例えば、ベクトル間の相違度（あるいは類似度）を、市街地距離、誤差二乗和、ユークリッド距離、２つのベクトルのなす角度、内積などにより計算し、それらをある閾値よりも相違度が小さい（あるいは類似度が大きい）場合に一致すると判定するようにすればよい。
［００５０］
次に、図２及び図４のフローチャートを参照して本実施の形態の全体の動作について詳細に説明する。
処理全体は、登録処理と、検索処理とから構成される。画像照合装置のＣＰＵによりこれらの処理がなされてもよい。
［００５１］
最初に、登録処理について説明する。
まず、登録モジュールにおける連結領域計算モジュールＲ１１が、入力される画像
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
2009110410.tif 000046
であり、各
［００６４］
［数９］
2009110410.tif 000047
は、
［００６５］
［数１０］
2009110410.tif 000048
で表される。ここで
［００６６］
［数１１］
2009110410.tif 000049
は、連結領域である。連結領域は、連結領域を一意に指定できる番号で表現することとする。
［００６７］
さらに、検索モジュールにおける累積画素値比計算モジュールＱ１３は、登録モジュールにおける累積画素値比計算モジュールＲ１３と同様に、計算されたＬｆＢから特徴ベクトルを計算する（ステップＳＱ１６）。これは、例えば、ＬｆＢの列に対して、
［００６８］
［数１２］
2009110410.tif 000050
を計算することにより実現される。
［００６９］
次に、検索モジュールにおける累積画素値比一致判定モジュールＱ１４が、計算された特徴ベクトルと、登録モジュールにおける累積画素値比格納モジュールＲ１４に格納されたすべての特徴ベクトルのそれぞれとの照合を行い、登録モジュールにおける累積画素値比格納モジュールＲ１４に格納されたそれぞれの特徴ベクトルがＱ１３により計算された特徴ベクトルと一致しているかどうかの判定結果を出力する（ステップ
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
＝２８／１２
となり、
画素値が二値の場合（ｂ）、
（画素値の和は面積となるので、）
累積画素値比＝（領域Ａの面積の和）／（領域Ｂの面積の和）
＝７／４
となる。
［００８０］
本実施の形態では、登録画像と検索画像との双方からアフィン不変量の近似である累積画素値比を要素として特徴ベクトルが構成され、それらの特徴ベクトルが一致するかどうかを判定するというように構成されているため、登録画像と検索画像との間にアフィン変換で記述できる変形が起こっていたとしても、精度良く画像の照合が行える。特に、上述したような、特徴点三角形面積比を用いる関連技術では精度良い認識が行えない場合であっても、累積画素値比を用いることにより精度良く認識することが可能である。
［００８１］
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
［００８２］
図６を参照すると、本発明の第２の実施の形態は、本発明の第１の実施の形態における構成に加えて、登録モジュールにおける特徴点配置計算モジュールＲ１５、登録モジュールにおける特徴点配置格納モジュールＲ１６、検索モジュールにおける特徴点配置計算モジュールＱ１５、アフィンパラメータ推定モジュールＡ１、アフィンパラメータ検証モジュールＡ２から構成される。
［００８３］
登録モジュールにおける特徴点配置計算モジュールＲ１５は、登録モジュールにおける領域組み合わせ計算モジュールＲ１２が計算する登録画像連結領域の列Ｌｍに対して、特徴点配置を計算する。例えば、Ｌｍ＝（ｉ１、ｉ２、…、ｉｍ）であるとする。ここで、ｉ１は対応する連結領域を一意に指定する番号である。このとき、登録モジュールにおける特徴点配置計算モジュールＲ１５は、次のような特徴点配置Ｆｍを計算する。
［００８４］
［数１８］
2009110410.tif 000051
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
2009110410.tif 000052
の値、あるいはこれらから計算される値があらかじめ定められた範囲内の値にある場合に一致すると判定する。例えば、Ｂｘをｘ方向の伸縮率、Ｂｙをｙ方向の伸縮率、θを回転角として
2009110410.tif 000053
なるモデルを仮定する。この場合、撮像系から得られる条件などによりＢｘ、Ｂｙ、θの値の範囲が定められると、ａ、ｂ、ｃ、ｄの値の範囲も定められる。したがって、
2009110410.tif 000054
の当てはまりがよい場合に、特徴点配置が一致すると判定をすることが可能になる。
2009110410.tif 000055
に仮定できる条件から定められる範囲内に入っているかどうかを検証することにしても良い。例えば、各ｋに対して計算される
2009110410.tif 000056
2009110410.tif 000057
いは類似度）を、市街地距離、誤差二乗和、ユークリッド距離、２つのベクトルのなす角度、内積などにより計算し、それらをある閾値よりも相違度が小さい（あるいは類似度が大きい）場合に一致すると判定するようにすればよい。
［００９５］
また、
［００９６］
［数２４］
2009110410.tif 000058
のように、各ｋに対して計算された市街地距離の和で求められる値であってもよい。また、より一般に各ｋに対して計算される何らかの相違度（類似度）を引数とする関数値がある閾値よりも小さい（大きい）場合に一致すると判定することもできる。
［００９７］
また、検索モジュールにおける累積画素値比一致判定モジュールＱ１４にて計算された相違度（あるいは類似度）とこれらの値を合わせて利用する照合を行っても良い。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
図１３を参照すると、本発明の第３の実施の形態は、本発明の第１の実施の形態における構成に加えて、登録モジュールにおける特徴点三角形面積比計算モジュールＲ１７、登録モジュールにおける特徴点三角形面積比格納モジュールＲ１８、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６、不変量検証モジュールＱ１７から構成される。
［０１１５］
登録モジュールにおける特徴点三角形面積比計算モジュールＲ１７は、背景技術における（登録手続きＧ）と同様の手続きで、登録画像から計算された特徴点の列Ｌｆから不変量の列を計算する。
［０１１６］
登録モジュールにおける特徴点三角形面積比格納モジュールＲ１８は、登録モジュールにおける特徴点三角形面積比計算モジュールＲ１７にて計算された不変量の列を、画像番号および不変量の列を計算する元となった連結領域の列Ｌｍを一意に指定できる指標とともに、格納する。
［０１１７］
検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６は、背景技術における（登録手続きＧ）と同様の手続きで、検索画像から計算された特徴点の列Ｌｆから不変量の列を計算する。
［０１１８］
不変量検証モジュールＱ１７は、登録モジュールにおける特徴点三角形面積比計算モジュールＲ１７にて計算された不変量の列と、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６にて計算された不変量の列を特徴ベクトルとみなし、検索モジュールにおける累積画素値比一致判定モジュールＱ１４が持つ機能において説明した相違度（または類似度）を計算し、その値を利用して一致しているかどうかを判定する。例えば、Ｑ１７にて計算される相違度（類似度）があらかじめ定められた範囲内の値をとる場合に一致したとみなし、それ以外の場合は不一致であると判定すればよい。また、Ｑ１４にて計算された相違度（類似度）を合わせて照合に利用することもできる。
［０１１９］
次に、図１４及び図１５、図１６のフローチャートを参照して本発明の第３の実施の形態の全体の動作について詳細に説明する。
処理全体は、登録処理と、検索処理とから構成される。画像照合装置のＣＰＵによりこれらの処理がなされてもよい。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
［０１２０］
最初に、登録処理について説明する。本発明の第３の実施の形態における登録処理は、本発明の第１の実施の形態における登録処理とほぼ同じである。従って、本発明の第１の実施の形態と相違する処理のみ、すなわち図１４におけるステップＳＲＣ１４およびＳＲＣ１７を説明するについて説明する。
［０１２１］
ステップＳＲＣ１４では、本発明の第１の実施の形態におけるステップＳＲ１４における処理が行われた後、登録モジュールにおける特徴点配置計算モジュールＲ１５が、Ｌｍから不変量の列を計算する。計算された不変量の列は、登録モジュールにおける特徴点三角形面積比格納モジュールＲ１８に格納される。
［０１２２］
ステップＳＲＣ１７では、本発明の第１の実施の形態におけるステップＳＲ１７における処理が行われた後、特徴ベクトルが計算される元となったＬｍから計算される不変量の列を一意に指定できる情報があわせて格納される。
［０１２３］
次に、検索処理について説明する。本発明の第３の実施の形態における検索処理は、本発明の第１の実施の形態における検索処理とほぼ同じである。従って、本発明の第１の実施の形態と相違する処理のみ、すなわち、図１５におけるステップＳＱＣ１７のみ説明する。
［０１２４］
図１６を参照して、ステップＳＱＣ１７について説明する。
まず、ステップＳＱＣ１７１は、ステップＳＱＢ１７１の処理と同一である。
［０１２５］
ステップＳＱＣ１７２は、ステップＳＱＣ１７１にて計算された相違度（あるいは類似度）があらかじめ定められる範囲内にあるかを判定する。この場合、相違度（類似度）がある値より小さい（大きい）場合に一致すると判定できるように範囲を決めておくことが一つの方法である。あらかじめ定められる範囲内にある場合はステップＳＱＣ１７３へ、そうでない場合にはステップＳＱＣ１７７へ進む。
［０１２６］
ステップＳＱＣ１７３では、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６が不変量の列を計算する。この処理にはこれまでの手法を用いることができる。なお、これまでの手法の説明においては、１つの（連結）領域から、特徴点として重心を計算するように説明しているが、必ずしも重心でなくてもよい。また、１つの領域から１つの特徴点を抽出するように限る必要はなく、登録画像から計算される特徴点の数と、検索画像から計算される特徴点の数が同じになる方法
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
であればそれを適用することが可能である。
［０１２７］
ステップＳＱＣ１７４では、不変量検証モジュールＱ１７が、現在照合を行っている登録画像から計算された特徴ベクトルを生成する元となった領域組み合わせＬｍから計算した不変量の列を取得する。
［０１２８］
ステップＳＱＣ１７５では、不変量検証モジュールＱ１７が、一致しているかどうかの判定結果を出力する。
［０１２９］
ステップＳＱＣ１７７では、不変量検証モジュールＱ１７が、最終結果として一致であるか不一致であるかを出力する。
［０１３０］
次に、本発明の第３の実施の形態の効果について説明する。
本発明の第３の実施の形態では、累積画素値比を要素とする特徴ベクトルを照合に加えて、特徴ベクトルを構成する元の領域組み合わせから特徴点配置を構成し、特徴点配置から特徴点三角形面積比を不変量として計算される不変量の列を用いて照合が行えるように構成されている。
［０１３１］
本発明の第２の実施の形態と同様に、面積だけでなく、領域の位置に関する情報をも照合に利用できるため、より高精度な照合が可能となる。
［０１３２］
なお、第２の実施の形態におけるアフィンパラメータの推定および検証と、第３の実施の形態における不変量による検証は独立して付加することができる処理である。したがって、第１の実施の形態にアフィンパラメータの推定及び検証と、不変量による検証の双方を付加することにより、新たな実施の形態が構成可能であることを付記しておく。
［０１３３］
以上の説明は、入力画像が（二値を含む）濃淡画像の場合についての説明である。
入力画像がカラー画像の場合は、画像中の各画素について、色空間上の点から濃淡値を計算する手続きにより、カラー画像から１枚の濃淡画像を作成する方法を構成すれば、本発明が適用できるようになる。
［０１３４］
また、既存の手法でカラー画像から複数の濃淡画像を作成し、それらを利用した照合を行うこともできる。
［０１３５］
例えば、次のような手法が可能である。
［０１３６］
まず、登録モジュールにおける累積画素値比計算モジュールＲ１３、検索モジュ
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】
ールにおける累積画素値比計算モジュールＱ１３、登録モジュールにおける特徴点配置計算モジュールＲ１５、検索モジュールにおける特徴点配置計算モジュールＱ１５、登録モジュールにおける特徴点三角形面積比計算モジュールＲ１７、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６では、それぞれの濃淡画像から計算が行われる。
［０１３７］
登録モジュールにおける累積画素値比格納モジュールＲ１４、登録モジュールにおける特徴点配置格納モジュールＲ１６、登録モジュールにおける特徴点三角形面積比格納モジュールＲ１８では、複数の画像から計算された値が格納される。
［０１３８］
そうしておけば、検索モジュールにおける累積画素値比一致判定モジュールＱ１４、アフィンパラメータ推定モジュールＡ１、アフィンパラメータ検証モジュールＡ２、不変量検証モジュールＱ１７が持つ機能を複数回動作させることで、同じ領域組み合わせについて、複数の画像における照合が可能となる。
［０１３９］
例えば、ＲＧＢ空間における、Ｒ値が表す濃淡画像Ｒ、Ｇ値が表す濃淡画像Ｇ、Ｂ値が表す濃淡画像Ｂの３画像を用いる場合は、濃淡画像Ｒから計算された特徴ベクトル同士による照合と、濃淡画像Ｇから計算された特徴ベクトル同士による照合と、濃淡画像Ｂから計算された特徴ベクトル同士による照合を行うことができる。照合結果としては、すべての濃淡画像において計算された特徴ベクトル同士が一致であった場合に、最終的に一致したと判定する。また、あらかじめ定められた数以上の濃淡画像における特徴ベクトル同士が一致した場合に、最終的に一致したとすることもできる。あらかじめ定められた数が２の場合は、例えば、濃淡画像Ｒにおける特徴ベクトル同士が一致し、かつ、濃淡画像Ｂにおける特徴ベクトル同士が一致した場合に、最終的に一致したとすることになる。ここでは、色空間から複数の濃淡画像を生成する方法として、ＲＧＢ各成分が表す濃淡画像を例に取ったが、これに限る必要はない。
［０１４０］
複数の濃淡画像を作る方法としては、入力される画像がカラー画像の場合は、ＲＧＢ空間、ＸＹＺ空間、ＬＡＢ空間、ＬＵＶ空間、ＹＩＱ空間など既存の色空間における各成分についての濃淡画像を利用することができる。もちろん、これに限らず、色空間における画素値の組を１次元の濃淡値に変換する関数を複数用意してお
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
けば、複数の濃淡画像が得られる。
［０１４１］
複数の濃淡画像は、画像が入力された時点で計算しておいてもよいし、特徴ベクトルあるいは不変量リストの列が計算される直前に計算するのでもよい。
［０１４２］
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作を説明する。
図１７に示すように、第１の実施例においては、本発明の第１の実施の形態の画像照合装置、もしくは、本発明の第２の実施の形態の画像照合装置、もしくは、本発明の第３の実施の形態の画像照合装置に加えて、最終一致判定部Ｑ３から構成される。なお、図１７中の結果出力部Ｑ２は、本発明の第１の実施の形態の画像照合装置においては検索モジュールにおける累積画素値比一致判定モジュールＱ１４、本発明の第２の実施の形態の画像照合装置においてはアフィンパラメータ検証モジュールＡ２、本発明の第３の実施の形態の画像照合装置においては不変量検証モジュールＱ１７のことを指す。いずれも、登録画像から計算された領域の組み合わせと検索画像から計算された領域の組み合わせ１対に対し、一致または不一致１回を１回出力する点で共通である。
［０１４３］
最終一致判定部Ｑ３は、まず、結果出力部Ｑ２から一致が出力された数を、登録画像に応じて別々に計数する。例えば、登録画像ＲＩｒのある領域の組み合わせと検索画像のある領域の組み合わせが一致であった場合に、一致数Ｃｒを１だけ増加させる。照合開始前に各Ｃｒをすべて０で初期化しておけば、結果として、登録画像ＲＩｒに対して、一致数がＣｒ個であるというように計数される。次に、この値を用いて、最終的に検索画像に対応する登録画像がどの画像であるかを判定し、登録画像を一意に指定できる情報を出力する。例えば、Ｃｒの値が最も大きい登録画像ＲＩｒを用いることもできるし、背景技術で説明したような計算式を使って、各画像のスコアを求め、その値を利用して照合を行ってもよい。もちろん、Ｃｒあるいはスコアが同点のものがあれば結果を棄却としてもよい。また、Ｃｒの数があらかじめ定めた値よりも小さい場合、スコアがあらかじめ定めた範囲に入っていない場合について結果を棄却とすることも考えられる。
［０１４４］
最終一致判定部Ｑ３は、すべての登録画像に対するすべての領域組み合わせと、検索画像に対するすべての領域組み合わせについての一致判定が終了した後に動
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
３を含むよう構成すればよい。第２の実施の形態の画像照合装置を用いた本発明の第１の実施例においては、計算機ＣｏｍＡが、登録モジュールにおける連結領域計算モジュールＲ１１、登録モジュールにおける領域組み合わせ計算モジュールＲ１２、登録モジュールにおける累積画素値比計算モジュールＲ１３、登録モジュールにおける特徴点配置計算モジュールＲ１５を、計算機ＣｏｍＣが登録モジュールにおける累積画素値比格納モジュールＲ１４、登録モジュールにおける特徴点配置格納モジュールＲ１６を、計算機ＣｏｍＢが検索モジュールにおける連結領域計算モジュールＱ１１、検索モジュールにおける領域組み合わせ計算モジュールＱ１２、検索モジュールにおける累積画素値比計算モジュールＱ１３、検索モジュールにおける累積画素値比一致判定モジュールＱ１４、検索モジュールにおける特徴点配置計算モジュール１５、アフィンパラメータ推定モジュールＡ１、アフィンパラメータ検証モジュールＡ２、最終一致判定部Ｑ３を含むように構成すればよい。第３の実施の形態の画像照合装置を用いた本発明の第１の実施例においては、計算機ＣｏｍＡが、登録モジュールにおける連結領域計算モジュールＲ１１、登録モジュールにおける領域組み合わせ計算モジュールＲ１２、登録モジュールにおける累積画素値比計算モジュールＲ１３、登録モジュールにおける特徴点三角形面積比計算モジュールＲ１７を、計算機ＣｏｍＣが登録モジュールにおける累積画素値比格納モジュールＲ１４、登録モジュールにおける特徴点三角形面積比格納モジュールＲ１８を、計算機ＣｏｍＢが検索モジュールにおける連結領域計算モジュールＱ１１、検索モジュールにおける領域組み合わせ計算モジュールＱ１２、検索モジュールにおける累積画素値比計算モジュールＱ１３、検索モジュールにおける累積画素値比一致判定モジュールＱ１４、検索モジュールにおける特徴点三角形面積比計算モジュールＱ１６、不変量検証モジュールＱ１７、最終一致判定部Ｑ３を含むように構成すればよい。
［０１５０］
このようにすれば、例えば、次のような動作が可能である。
まず、登録画像は撮像装置ＳｃＡを用いて撮像される。
撮像された登録画像は計算機ＣｏｍＡにより計算され、計算されたデータが計算機ＣｏｍＣに格納される
［０１５１］
次に、検索画像は撮像装置ＳｃＢを用いて撮像され、撮像された検索画像は計算機
【国際調査報告】
2009110410.tif 000059
2009110410.tif 000060
2009110410.tif 000061
2009110410.tif 000062