(57)【特許請求の範囲】
【請求項１】
画像に対応する信号を処理することによって前記画像の表現を導出する方法であって、
画像の特徴点を識別し、識別された特徴点に対応する画像領域を選択することにより、前記画像を代表するか又は前記画像にとって有意である複数の画像領域を識別すること、
識別された画像領域毎に、
前記画像領域の少なくとも一部分に対して第１の汎関数を適用してトレース変換を得ること、及び
マルチ解像度の識別子と、トレース変換のサーカス関数及びトレース変換における帯から得られる識別子とを生成する、前記トレース変換又は前記トレース変換の一部に関連する複数の中間表現を取得すること、並びに
前記複数の画像領域のうちの２つ以上の画像領域の前記中間表現から前記画像の前記表現を導出すること、
を含む、方法。
【請求項２】
前記画像領域を選択するステップは、
前記画像の複数の前記識別された特徴点を特徴強度に従って選択すること、及び
前記選択された複数の前記識別された特徴点に対応する画像領域を確定すること、
を含む、請求項１に記載の方法。
【請求項３】
前記画像領域を選択するステップは、
前記画像の識別された特徴点に対応する複数の画像領域を、識別された特徴点の前記画像内における位置に従って選択することを含む、請求項１又は２に記載の方法。
【請求項４】
前記選択された複数の画像領域は、前記画像にわたって分散している、請求項３に記載の方法。
【請求項５】
各選択された画像領域は、他の選択された画像領域の前記特徴点から前記画像内で少なくとも所定の距離だけ離れている特徴に対応する、請求項３又は４に記載の方法。
【請求項６】
前記画像の特徴点を識別するステップは、特徴点を検出するために強度画像勾配法を使用する、請求項１から請求項５までのいずれか１項に記載の方法。
【請求項７】
前記中間表現は一次元関数である、請求項１から請求項６までのいずれか１項に記載の方法。
【請求項８】
２つ以上の前記画像領域の前記中間表現から前記画像の前記表現を導出するステップは、
前記画像領域の前記中間表現から各画像領域の表現を導出すること、及び
前記画像の前記表現を導出するために、前記画像領域の複数の導出された表現を使用すること、
を含む、請求項１から請求項７までのいずれか１項に記載の方法。
【請求項９】
前記画像領域の前記中間表現から各画像領域の表現を導出するステップは、
前記中間表現の周波数表現の複数の周波数成分を使用して、前記画像領域の前記少なくとも一部分の前記中間表現を処理することを含む、請求項８に記載の方法。
【請求項１０】
前記画像の前記表現を導出するステップは、
選択された複数の識別された画像領域の対応する中間表現から導出された、該選択された複数の識別された画像領域の表現の、選択された複数の部分を結合することを含む、請求項１から請求項９までのいずれか１項に記載の方法。
【請求項１１】
前記複数の画像領域のうちの２つ以上の画像領域の前記中間表現から前記画像の前記表現を導出するステップは、所定の数の画像領域の前記中間表現を使用し、該所定の数は好ましくは２〜２５６の範囲にある、請求項１から請求項１０までのいずれか１項に記載の方法。
【請求項１２】
各画像領域に関連する幾何学的情報を、前記識別された画像領域の導出された表現と関連付けることをさらに含む、請求項１から請求項１１までのいずれか１項に記載の方法。
【請求項１３】
請求項１から請求項１２までのいずれか１項に記載の方法を使用して前記画像の表現を導出すること、及び
前記表現を前記画像と関連付けること、
を含む、画像を識別するための方法。
【請求項１４】
請求項１から請求項１３までのいずれか１項に記載の方法を使用して導出された各画像の表現を導出することを含む、画像を比較するための方法。
【請求項１５】
第１の画像の前記表現に関連付けられる画像領域を、第２の画像の前記表現に関連付けられる画像領域と比較することを含む、請求項１４に記載の画像を比較するための方法。
【請求項１６】
前記第１の画像の画像領域の表現と、前記第２の画像の画像領域の表現との間のハミング距離を求めるために、前記第１の画像の前記表現及び前記第２の画像の前記表現を使用すること、及び
前記対応する画像領域の前記表現間の前記ハミング距離が第１の所定の閾値未満である場合、前記第１の画像及び前記第２の画像を潜在的な一致として識別すること、
を含む、請求項１５に記載の方法。
【請求項１７】
前記第１の画像及び前記第２の画像の複数の画像領域の表現に関するハミング距離を求めることを含む、請求項１６に記載の方法。
【請求項１８】
前記第１の画像及び前記第２の画像から所定の数の画像領域対を識別することであって、該識別される対は、前記第１の所定の閾値未満であるとともに最も低いハミング距離が求められる、対応する表現を有している、識別することをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記画像領域の前記識別される対における各領域は一意的である、請求項１８に記載の方法。
【請求項２０】
前記画像領域の前記識別された対の前記表現に関する前記ハミング距離の合計を使用して累積ハミング距離を求めること、及び
前記画像領域の前記識別された対の前記表現の前記累積ハミング距離が第２の所定の閾値未満である場合、前記第１の画像及び前記第２の画像を潜在的な一致として識別すること、
をさらに含む、請求項１７、１８、又は１９に記載の方法。
【請求項２１】
前記画像が一致であるか否かを判断するために、潜在的な一致であると判断された複数の画像領域対又は画像対に関する幾何学的情報に幾何学的制約条件を適用することであって、ことを含む、請求項１６から請求項２０までのいずれか１項に記載の方法。
【請求項２２】
幾何学的制約条件を適用するステップは、
前記第１の画像内の所定の数の画像領域間の距離の第１の比を求めること、
前記第２の画像内の前記所定の数の画像領域間の距離の第２の比を求めること、及び
前記第１の比と前記第２の比との間の差分が第３の所定の閾値未満である場合、前記第１の画像及び前記第２の画像を一致であると判断すること、
を含む、請求項２１に記載の方法。
【請求項２３】
前記所定の数は３である、請求項２２に記載の方法。
【請求項２４】
幾何学的制約条件を適用するステップは、
前記第１の画像及び前記第２の画像のそれぞれについて、
以下の式を使用して、前記３つの画像領域に対応する点（ａ、ｂ、及びｃ）間のユークリッド距離の比を計算すること、
Ｌ１＝ａｂ／ａｃ、及びＬ２＝ａｂ／ｂｃ
並びに、
以下の式を使用して、前記第１の画像及び前記第２の画像（Ａ，Ｂ）の線長比（Ｌ１，Ｌ２）間の距離を測定すること、
【数１】
0005431362.tif 000006
を含む、請求項２３に記載の方法。
【請求項２５】
前記第３のしきい値は、Ｇ１、Ｇ２、及びＧ１＋Ｇ２のうちの１つ又は複数に関する閾値を含む、請求項２４に記載の方法。
【請求項２６】
表現の比較に基づいて前記複数の画像から照合する画像を選択することを含む、請求項１４から請求項２５までのいずれか１項に記載の方法。
【請求項２７】
請求項１から請求項２５までのいずれか１項に記載の方法を実行させるための制御装置を備える、装置。
【請求項２８】
画像及び／又は画像の表現を記憶する記憶手段、画像データベース及び／又は記述子データベース、表示手段、並びに画像選択手段のうちの１つ又は複数をさらに備える、請求項２７に記載の装置。
【請求項２９】
コンピュータによって実行されると、請求項１〜２５のいずれか一項に記載の方法を実施する命令を備えるコンピュータ記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像を表現するための方法及び装置、並びに、加えて、例えば検索又は検証する目的で画像を比較又は照合するための方法及び装置に関する。
【背景技術】
【０００２】
本発明は、先願の同時係属中の欧州特許出願第０６２５５２３９．３号、並びに英国特許出願第０７００４６８．２号、英国特許出願第０７１２３８８．８号、及び英国特許出願０７１９８３３．６号に開示される画像識別技法に対する改善に関する。それらの特許文献の内容は参照により本明細書に援用される。それらの先願の同時係属中の特許出願に開示される発明の詳細及び実施の形態は、本発明及び本発明の実施の形態にも同様に適用される。
【０００３】
欧州特許出願第０６２５５２３９．３号明細書、英国特許出願第０７００４６８．２号明細書、英国特許出願第０７１２３８８．８号明細書、及び英国特許出願０７１９８３３．６号明細書に記載される方法及び装置において使用される画像識別技法はそれぞれ、画像から短いバイナリ記述子を抽出する（図２を参照されたい）。これらの技法は、従来技術の多くの欠点に対処すると共に、特に以下によって特徴付けられる：
・特徴抽出及び特徴照合の双方の計算複雑度の低減
・画像記述子サイズの低減
・様々な画像の変更に対するロバスト性の増加、及び
・広範囲にわたる画像の変更に関して９９．８％の検出率を通常維持しながら、誤報率を０．０５ｐｐｍ（百万分率）レベルへ低減。
【０００４】
これらの方法は、多くの一般的な画像変更に対する非常に高レベルのロバスト性を提供する。しかしながらこれらは、平行移動及びクロッピングのように、画像コンテンンツの重要な部分が欠損するか又は置き換えられる、或る特定の種類の画像変更に対し、必要とされるレベルのロバスト性を提供しない場合がある。
【０００５】
したがって、画像コンテンツの部分的な欠損を伴う或る特定の種類の画像変更に対するロバスト性を大きく改善することが所望されている。
【発明の概要】
【０００６】
第１の態様によれば、本発明は、添付の請求項１において定義される、画像の表現を導出する方法を提供する。
【０００７】
第２の態様によれば、本発明は、本発明の第１の態様に従って導出される画像の表現を比較することによって、例えば画像照合のために画像を比較するための方法を提供する。
【０００８】
本発明の他の態様は、本発明の第１の態様に従って導出される画像表現の使用、本発明の第１の態様及び／又は第２の態様による方法を実施するための装置及びコンピュータプログラムを含む。
【０００９】
本発明は、領域ベースのトレース変換記述子によって記述される少数の対象領域に基づいて画像を表現する新たな手法に関する。本発明は画像照合の新たな方法にも関する。
【００１０】
本発明の実施の形態によれば、対象点又は特徴点から成る代表的な小さな集合が画像から選択される。選択手順において、予め選択された特徴の周囲の除外区域のような制約条件が使用される。変更されたトレース変換ベースの方法を使用して、各選択された対象領域からバイナリ「特徴識別特性（feature signature）」が抽出される。特徴識別特性を使用して、特徴の局所近傍を特徴付ける。画像は、複数の局所特徴識別特性及びそれらの幾何学的関係によって表現される。
【００１１】
本発明の実施の形態によれば、画像照合手順は、累積ハミング距離を使用して特徴点の一致する対の候補集合を迅速に識別し、その後、本方法の正確度を増大させるために幾何学的制約条件を適用することを含む２段階のプロセスとして実施される。特に、画像から選択される特徴点の配置によって提供される情報は、誤報率を大幅に低減するのに役立つ。また、幾何学的情報を使用して、画像変換の種類及び変換パラメータを確定することができる。
【００１２】
本発明の実施の形態は、欧州特許出願第０６２５５２３９．３号明細書、英国特許出願第０７００４６８．２号明細書、英国特許出願第０７１２３８８．８号明細書、及び英国特許出願０７１９８３３．６号明細書に記載される画像識別装置及び画像識別方法を補うように意図される。本発明は、有利には或る特定の画像変更に対するさらなるロバスト性を提供する。しかしながら、最新技術による処理資源を使用すると、本発明の技術の単独の使用は、検索速度の観点から、上記で参照した先願の同時係属中の特許出願において提案される技法と同じ性能を提供しない場合がある。特に、本発明の実施の形態による潜在的な特徴対の識別プロセスは、従来提案された方法より少なくとも１桁遅い場合がある。本発明による方法及び先願の同時係属中の特許出願の１つ又は複数の方法を単独で使用することができるが、これらの方法を組み合わせることが好ましい。このようにして、下記で示すように、より早い方法を使用した結果を、さらに分析するために、本発明による比較的低速な方法に渡すことができる。速度、誤検出率、及びロバスト性の観点からの性能利得は、組み合わせて適用すると最大になる。
【００１３】
本発明の他の特徴及び利点は、以下の説明及び添付の特許請求の範囲から明らかとなるであろう。
【００１４】
ここで、添付の図面を参照して本発明の実施形態を説明する。
【図面の簡単な説明】
【００１５】
【図１ａ】画像を示す図である。
【図１ｂ】図１ａの画像を縮小したバージョンを示す図である。
【図１ｃ】図１ａの画像を回転させたバージョンを示す図である。
【図１ｄ】図１ａの画像をぼかしたバージョンを示す図である。
【図１ｅ】図１ａの画像を（左右に）反転させたバージョンを示す図である。
【図１ｆ】図１ａの画像を大きく圧縮したバージョンを示す図である。
【図１ｇ】図１ａの画像をクロップしたバージョンを示す図である。
【図２】従来技術による画像及び該画像のビットストリング表現を示す図である。
【図３】勾配ベースの特徴検出器によって検出される対象点の集合例を示す図である。
【図４】特徴が一切選択されない画像境界領域、及び強度に基づく最終的な特徴集合を示す図である。
【図５ａ】原画像からのハミング距離を使用して一致することがわかった対象点を示す図である。ここで、対象点間の線長を使用して、配置制約を適用する。
【図５ｂ】図５ａを回転させた変形からのハミング距離を使用して一致することがわかった対象点を示す図である。ここで、対象点間の線長を使用して、配置制約を適用する。
【図６】本発明の一実施形態による装置のブロック図である。
【発明を実施するための形態】
【００１６】
画像の表現、具体的には画像識別子を導出すると共に、そのような表現／識別子を、例えば１つ又は複数の画像の識別、照合又は検証のために使用する様々な実施形態を以下に説明する。本発明は、画像を識別するために特に有用であるが、画像の識別に限定されるものではない。説明する実施形態において、「画像識別子」（単純に「識別子」、「識別特性(signature)」、又は「画像識別特性(image signature)」とも呼ばれる）は画像の表現の一例であり、この用語は単に画像の表現又は記述子を表すのに使用される。
【００１７】
当業者であれば、本発明の一実施形態による画像識別装置及び画像識別方法の具体的設計の詳細、並びに画像識別において使用するための画像識別子の導出は、画像識別子がロバストであるべき画像の変更の種類、識別子の大きさ、抽出及び照合の複雑度、目標誤報率等に関連する要件によって決まることを理解するであろう。
【００１８】
以下の例では、画像に対する以下の変更に対してロバストな識別子をもたらす一般的設計を示す（これは網羅的なリストではない）：
・色数削減、
・ぼかし、
・明るさの変更、
・反転（左右及び上下）、
・階調変換、
・ヒストグラム等化、
・ＪＰＥＧ圧縮、
・ノイズ、
・回転、
・クロップ、
・スケーリング、
・平行移動、
・スキューイング、及び
・視点変更(Perspective change)。
【００１９】
提案される設計は通常、広範な種類の画像に対する１０ｐｐｍ（百万分率）未満の低い誤報率、及び９５．０％を超える通常検出率を達成することができることがわかっている。
【００２０】
図１は、画像の一例及びその画像の変形バージョンを示す。より具体的には、図１ａは原画像であり、図１ｂは図１ａの画像を縮小（スケーリング）したバージョンであり、図１ｃは図１ａの画像を回転させたバージョンであり、図１ｄは図１ａの画像をぼかしたバージョンであり、図１ｅは図１ａの画像を反転させたバージョンであり、図１ｆは図１ａの画像を圧縮したバージョンであり、図１ｇは図１ａの画像をクロップしたバージョンである。
【００２１】
本発明の一実施形態は、画像に対応する信号及び／又は画像データを処理することによって、画像の表現、及びより具体的には画像識別子を導出する。
【００２２】
欧州特許出願第０６２５５２３９．３号明細書、英国特許出願第０７００４６８．２号明細書、英国特許出願第０７１２３８８．８号明細書、及び英国特許出願０７１９８３３．６号明細書に整合して、画像識別子の抽出の最初の段階において、画像はサイズ変更及びフィルタリングによって任意選択で前処理される。サイズ変更ステップは、処理前に画像を正規化するために使用される。フィルタリングステップは、エイリアシングのような効果を除去するためのフィルタリングを含むことができ、領域選択及びテーパリングも含むことができる。一実施形態では、画像は、１９２×Ｎ又はＮ×１９２の解像度にサイズ変更され（ここでＮ≧１９２である）、縦横比を維持する。別の実施形態では、画像は１９２×１９２の正方形にサイズ変更される。次に、画像は３×３のガウスカーネルを用いてローパスフィルタリングされる。画像の中心から円形領域がさらなる処理のために抽出される。前処理ステップは任意選択であり、上記のものの任意の組み合わせを含むことができる。
【００２３】
次の段階において、画像内で対象点を検出する。一実施形態は、特徴検出器を使用して、画像勾配の測定に基づいて、画像内の潜在的な特徴及びそれらの強度を検出する。１つの適切な画像勾配特徴検出器は、ハリス特徴検出器である。ハリス特徴検出器を図２の画像に適用した結果例を図３に示す。選択手順を適用して、代表的な特徴集合を選ぶ。一実施形態において、最大１６個の特徴が選ばれる。特徴が一切選ばれない画像のエッジの周囲に境界を設定する。この実施形態では、境界は幅１６ピクセルである。検出された特徴の中の許容可能な特徴から最も強い特徴を最初に選択する。特徴が以前に選択された特徴の周囲の除外区域内にある場合には該特徴は選択されないという制限で、後続の特徴が強度順に選択される。一実施形態では、１０ピクセルの半径を有する円形領域を除外区域として使用する。選択プロセスは、所定の数の代表的な特徴（たとえば好ましい実施形態では１６ピクセル）が選択された場合か、又はこれ以上特徴が残っていない場合に終了する。図３において検出された特徴から選択される特徴集合を図４に示す。
【００２４】
ここで特徴点（又は対象点）のロケーションが選択されているが、それらの位置は、好ましくは、たとえばインターネット上でhttp://opencvlibrary.sourceforge.net/CvReference, reference [I])において取得することができるOpenCV(FindCornerSubPix)03/01/2008において記載されるような方法を使用して、サブピクセル解像度に精緻化（リファイン）される。
【００２５】
参照により本明細書に援用される英国特許出願０７１９８３３．６号明細書において、バイナリ画像識別特性又は画像表現を抽出するための方法が開示される。本発明の一実施形態では、英国特許出願０７１９８３３．６号明細書の方法を適用して、特徴点の周囲の領域からバイナリ「特徴識別特性」を抽出する。
【００２６】
このため、各特徴識別特性は、検出される特徴に関連付けられる画像領域のバイナリ表現である。一実施形態では、３２ピクセルの半径を有し特徴点を中心とする円形画像領域が選択され、該画像領域に関してバイナリ識別特性が計算される。円形領域は、好ましくは、たとえば三次補間法を使用して、サブピクセルレベルの精度で抽出する。次に、英国特許出願０７１９８３３．６号明細書による方法を使用して、抽出した領域を処理して対応する画像識別子を導出する。この方法の概要が下記で提供される。
【００２７】
画像領域のトレース変換Ｔ（ｄ，θ）は、ｄ、θによってパラメータ化される全ての可能な線を画像に射影し、これらの線に第１の汎関数Ｔを適用することによって実施される。英国特許出願０７００４６８．２号明細書に開示される方法に従って、トレース変換の結果を分解して、該トレース変換の次元ｄ、θのいずれか又は双方において該トレース変換の解像度を低減することができる。欧州特許出願第０６２５５２３９．３号明細書、及び英国特許出願第０７００４６８．２号明細書の方法のように、第２の汎関数Ｐをトレース変換の列に適用して、実数のベクトル（すなわち一次元関数）を得ることができる。この第２の汎関数Ｐは対角汎関数(diametrical functional)として知られ、結果として得られるベクトルはサーカス関数（circus function）として知られる。
【００２８】
第３の汎関数であるサーカス汎関数をサーカス関数に適用して、単一の数を得ることができるが、このステップは好ましい実施形態では使用されない。
【００２９】
代替的に、英国特許出願０７１９８３３．６号明細書の方法に従って、上記で論考したサーカス関数に対する代替としていわゆる「帯サーカス関数（band-circus function）」を取得してもよい。帯サーカス関数は、値をトレース変換の一部分のみから選択及び処理することによって、トレース変換を画像の線の部分集合に限定する。
【００３０】
第１の汎関数、第２の汎関数、及び／又は第３の汎関数（トレース関数、対角関数、及びサーカス関数）を適切に選ぶことによって、結果の特性を制御することができる。
【００３１】
周波数表現を介して、サーカス関数（又は帯サーカス関数）から画像領域に関するバイナリ識別子を抽出する。たとえば、フーリエ変換の複数の絶対値の係数(magnitude coefficients)について関数ｃ（ω）を定義することができる。この関数の１つの例示は、隣接する係数の差分を取ることである。
ｃ（ω）＝｜Ｆ（ω）｜−｜Ｆ（ω＋１）｜
【００３２】
結果として得られるベクトルに、以下となるように閾値を適用することによってバイナリストリングを抽出することができる。
【００３３】
【数１】
0005431362.tif 000002
全てのωについて
【００３４】
Ｓに関する適切な選択は、Ｓ＝０及びＳ＝ｍｅａｎ（ｃ）を含む。次に、これらのバイナリストリング値Ｂ＝｛ｂ0，．．．，ｂn｝から画像領域のバイナリ表現を構築する。
【００３５】
本発明の一実施形態では、（英国特許出願０７１９８３３．６号明細書におけるように画像全体を使用するのとは対照的に）局所画像領域を使用するため、該特許文献に記載される識別特性抽出技法に対し複数の変更を加える必要がある。特に、欧州特許出願第０６２５５２３９．３号明細書に開示される方法に従って、汎関数
ｍａｘ（ξ（ｔ））      （１）
及び
∫｜ξ（ｔ）’｜ｄｔ      （２）
を使用して、完全トレース変換のサーカス関数から２つの識別子を抽出する。
【００３６】
欧州特許出願第０７００４６８．２号明細書に開示される方法に従って、トレース変換の距離（ｄ）パラメータを８分の１、１６分の１、及び３２分の１に分解（又はサブサンプリング）し、式（１）及び式（２）の双方を適用することによって取得されるサーカス関数からさらなる６つの「マルチ解像度」識別子を抽出することができる。
【００３７】
欧州特許出願第０７１２３８８．８号明細書に開示される方法に従って、トレース変換における帯からさらなる３つの関数を選択し、欧州特許出願第０７１９８３３．６号明細書に開示される方法に従って、トレース環形関数から２つの関数を抽出するとともに、トレース円形関数から１つの関数を抽出する。
【００３８】
これらの１４個の成分識別子のそれぞれは８ビットであり、各特徴識別子の総計は１１２ビットとなる。特徴点の（前処理された画像における）座標を、対応する特徴／画像領域に関する幾何学的情報として、識別子と共に記憶する。任意選択で、１１２ビットから成る部分集合を選択又は導出することができる。
【００３９】
特徴点の完全な集合を多数の形で表現することができる。好ましい実施形態では、画像記述子は、多数の情報フィールドを含むビットストリームである。第１のフィールドは特徴の個数である。そして、各特徴は、ビットストリームにおいて特徴点座標（ｘ及びｙ）として表現され、次に識別子が続く。任意選択で、特徴の数を記憶するのではなく、未使用フィールドを表すためにセットされたフラグとともにパディングが使用されてもよい。
【００４０】
上述したように、画像特徴間の完全照合手順は、２つの段階を含む。
【００４１】
第１の段階は、１つの画像からの全ての特徴を第２の画像からの全ての特徴と比較することを含む。共に長さＮである２つの特徴識別特性Ｂ1及びＢ2間で照合を実施するために、ハミング距離を取る。
【００４２】
【数２】
0005431362.tif 000003
【００４３】
ここで、
【００４４】
【数３】
0005431362.tif 000004
【００４５】
は排他的ＯＲ（ＸＯＲ）演算子である。
【００４６】
一実施形態では、最小ハミング距離Ｈを有する３つの一意的な対を見つける。２つの画像間の特徴ベースの累積ハミング関数は、３つの個々のハミング距離の合計である。
【００４７】
第２のステップは、幾何学的制約条件を適用して、それらの画像が真の一致であるか又は偽の一致であるかを判断することを含む。幾何学的制約条件の適用は、ハミング距離と比較して計算コストが比較的高い。複雑度を最小にするために、潜在的な一致に関する所定の閾値未満の累積ハミング距離を有する画像対のみを、幾何学的方法を使用して比較する。１つの可能な実施形態では、３つの特徴点（ａ、ｂ、及びｃ）から成る集合を選ぶ。図５に示すように、これらの３つの点を使用して、特徴間の線長比を制約条件として使用することができる。識別子内の関連付けられる座標情報を使用して、３つの特徴点間のユークリッド距離、ａｂ、ａｃ、及びｂｃを得ることによって、線長比を計算する。２つの線長比、
Ｌ1＝ａｂ／ａｃ
及び
Ｌ2＝ａｂ／ｂｃ
を得る。
【００４８】
画像Ａ及びＢからの線長比間の距離の測定値を以下のように定義する。
【００４９】
【数４】
0005431362.tif 000005
【００５０】
有利には、画像内の定義される点間の線長比は、回転、平行移動、及びスケーリングのような変形に対し不変であるため、上記の幾何学的制約は、そのような幾何学的変形を受けた画像の照合に適している。しかしながら、設計要件に整合する他の適切な幾何学的制約条件を使用してもよい。
【００５１】
一実施形態では、２つの閾値を距離測定値に適用する。一方は個々の測定値の大きさを制約するためのものであり、他方は距離の合計を制約するためのものである。
【００５２】
代替的に、累積ハミング距離制約条件（及び／又は対的(pairwise)ハミング距離制約条件）を使用して、３つの特徴点対から成る複数の候補集合を予め選択することができる。次に、幾何学的一致が見つかるか、又はこれ以上候補集合が残っていなくなるまで、幾何学的制約条件を、（たとえば累積ハミング距離によって順序付けされている場合がある）候補集合のそれぞれに順番に適用することができる。
【００５３】
上記で説明したように、本発明の画像照合技法は、英国特許出願０７１９８３３．６号明細書に開示される方法のような他の画像照合技法と組み合わせることができる。個々の識別子の全てを含む画像毎に記述子を生成する。好ましい実施形態では、識別子ビットストリームは、英国特許出願０７１９８３３．６号明細書に基づく２つの識別子と、本発明のための記述子とを含む。英国特許出願０７１９８３３．６号明細書に基づく２つの識別子のうち、第１の識別子は、画像縦横比を維持するために画像を前処理することによって生成され、他方の識別子は、画像を処理して正方形にするときに生成される。
【００５４】
好ましくは、照合を、まず、非常に低い誤報閾値において、英国特許出願０７１９８３３．６号明細書のより高速なアルゴリズムを用いて実施する。閾値未満の任意の画像対を一致であると見なし、閾値を超える対（英国特許出願０７１９８３３．６号明細書では一致であると見なされない）を、次に本発明に従って処理する。最初に、累積ハミング距離を適用し、閾値を超える３つの対から成る集合を、異なっている（一致しない）と見なす。幾何学的制約を、累積ハミング距離閾値未満の３つの対から成るセットに適用する。３つの対から成る集合に関する幾何学的測定値が、幾何学的測定値に関する閾値レベル未満である場合、画像対を一致であると見なす。そうでない場合、画像対を異なっていると見なす。
【００５５】
上記の方法を実行するための、一実施形態による、本発明を実施するための装置を図６に示す。実施は、画像データベース２３０に格納されている画像のための識別子のデータベース２４０を構築することを含む。２つのデータベース２３０及び２４０は、同じデータベースであってもよく、又は別個のデータベースであってもよい。装置によって、問い合わせ画像２５０から抽出される識別子２６０を検索して、識別子データベース１４０内の一致を見つけることが可能になる。順序付けされている場合がある画像のリストをユーザ２９０又はクエリアプリケーションに返す。
【００５６】
当業者であれば、説明した実施形態に対し多くの変形及び変更を行うことができることを理解するであろう。たとえば、説明した実施形態は、特徴検出に基づいて、画像識別特性が導出される画像領域を識別するが、他の技法を使用して、画像を代表する画像領域又は画像内で重要な画像領域を識別してもよい。さらに、説明される実施形態は、画像勾配法に基づく特徴検出器を使用するが、他の適切な方法を使用して画像内の対象点又は領域を検出してもよい。同様に、最良の又は最強の検出される特徴点又は対象点を選択するための他の技法も可能である。
【００５７】
加えて、説明した実施形態において使用される３つの特徴点から成る集合に関連付けられる線長比に関連する距離測定と異なる様々な幾何学的制約のうちの１つ又は複数を使用することが可能である。たとえば、任意の数の特徴点を、距離測定値と合わせて使用することができる。代替的に、他の幾何学的制約は、特徴点間の角度に基づいてもよい。さらに、アフィンモデルを使用して、幾何学的制約を定義してもよい。
【００５８】
本発明の精神及び範囲に入る全ての変形、変更、及び均等物を含むことを意図している。
【００５９】
参照
［１］Open CV Reference Manual, Chapter 1: Image Processing Gradients, Edge and Corners - “FindCornerSubPix”: http://opencvlibrary.sourceforge.net/CvReference
【図５ａ】
0005431362.tif 000007
【図５ｂ】
0005431362.tif 000008
【図６】
0005431362.tif 000009
【図１ａ】
0005431362.tif 000010
【図１ｂ】
0005431362.tif 000011
【図１ｃ】
0005431362.tif 000012
【図１ｄ】
0005431362.tif 000013
【図１ｅ】
0005431362.tif 000014
【図１ｆ】
0005431362.tif 000015
【図１ｇ】
0005431362.tif 000016
【図２】
0005431362.tif 000017
【図３】
0005431362.tif 000018
【図４】
0005431362.tif 000019