(57)【特許請求の範囲】
【請求項１】
１つのクエリ画像を複数の画像とマッチングする方法であって、画像は一組の特徴点および一組の対応する特徴ベクトルによって表され、
前記複数の画像の各々と前記クエリ画像との間の既定値より大きい推定一致の数に少なくとも一部は基づいて、前記複数の画像から推定一致画像を見出すことと、
前記推定一致画像の各々と前記クエリ画像との間の推定一致のサブセットで位相同型性試験を行うことと、
前記位相同型性試験を合格した前記推定一致画像の各々と前記クエリ画像との間の前記推定一致のサブセットを使用して動き推定を行うことによって候補マッチを見出すことと
を含む方法。
【請求項２】
前記推定一致画像は、他の複数の画像に見出された推定一致の数に基づく値より大きい前記推定一致の数にさらに基づく、請求項１に記載の方法。
【請求項３】
前記推定一致は、前記複数の画像のうちの１つの画像の各特徴ベクトルと前記クエリ画像の各特徴ベクトルとが既定値より大きいベクトル・ドット積を有することを含む、請求項１に記載の方法。
【請求項４】
前記推定一致画像の１つと前記クエリ画像との間の前記推定一致のサブセットに対して位相同型性試験を行うことは、
前記推定一致画像の１つにおいて２つの特徴点を接続して第１の直線を形成することであって、前記２つの特徴点は前記サブセットから選択されることと、
前記クエリ画像において２つの対応する特徴点を接続して第２の直線を形成することと、
前記サブセットの残りの特徴点について、
前記第１の直線から、前記推定一致画像の１つにおける残りの特徴点の１つまでの第１の符号付きの距離を計算することと、
前記第２の直線から、前記クエリ画像における対応する残りの特徴点までの第２の符号付きの距離を計算することであって、
前記残りの特徴点の１つが前記第１の直線上に位置する場合、または前記対応する残りの特徴点が前記第２の直線上に位置する場合、同じ順番であるかの試験を行い、前記同じ順番であるかの試験は、前記第１の直線に関する前記２つの特徴点および前記残りの特徴点の順番と前記第２の直線に関する前記２つの対応する特徴点および前記対応する残りの特徴点の順番とが同じではないことに基づき前記サブセットが位相同型ではないと判定することを含み、
前記残りの特徴点の１つが前記第１の直線上に位置しない場合、または前記対応する残りの特徴点が前記第２の直線上に位置しない場合、同じ側にあるかの試験を行い、前記同じ側にあるかの試験は、前記第１の符号付きの距離の符号と前記第２の符号付きの距離の符号とが同じではないことに基づき前記サブセットが位相同型ではないと判定することを含む、計算することと、
前記同じ順番であるかの試験または前記同じ側にあるかの試験のうちの１つを使用して前記残りの特徴点の各々を判定することに基づき、前記１つのサブセットが位相同型であると判定することと
を含む、請求項１に記載の方法。
【請求項５】
前記クエリ画像のカバー範囲および候補マッチの各々のカバー範囲を判定することと、前記候補マッチの１つのカバー範囲および前記クエリ画像のカバー範囲の最大値が既定の閾値より小さいとき、前記候補マッチの１つを拒否することと、をさらに含む、請求項１に記載の方法。
【請求項６】
前記推定一致画像の１つと前記クエリ画像との間の前記推定一致のサブセットに対して前記動き推定を実行することは、
対応する推定一致のサブセット内の特徴点間で変換を計算することと、
前記変換を使用して、前記推定一致画像の１つと前記クエリ画像との間の前記推定一致の各々から内座層を計算することと、
前記変換の内座層の数が現在の最も良い変換の内座層の数より大きいことに基づき、前記変換を最も良い変換であるとして保持することと
を含む、請求項１に記載の方法。
【請求項７】
前記推定一致のサブセットに対して方向一致試験を行うことをさらに含む、請求項６に記載の方法。
【請求項８】
前記推定一致のサブセットに対して方向一致試験を行うことは、
２つの画像の１つにおいて前記特徴点の各々に対するオフセット点を決定することであって、前記各オフセット点は、前記特徴点から前記特徴点の方向の向きに移動され、前記特徴点は前記推定一致画像の１つと前記クエリ画像との間の前記推定一致のサブセットから選択され、前記２つの画像は前記推定一致画像の１つおよび前記クエリ画像を含むことと、
前記オフセット点および前記２つの画像のうちの１つにおける特徴点に前記変換を適用することと、
前記２つの画像のうちの別の画像における特徴点と前記変換されたオフセット点との間の移動に基づき予想される方向を決定することと、
前記予想される方向の１つが、前記２つの画像のうちの１つにおける変換された特徴点の方向と既定限度だけ異なるとき、前記変換を破棄することと
をさらに含む、請求項７に記載の方法。
【請求項９】
内座層の数が内座層の既定数より大きく、近似誤差が既定の閾値より小さい前記候補マッチを選択することによって、前記候補マッチから最終マッチの１つまたは複数の系列を特定することをさらに含む、請求項１に記載の方法。
【請求項１０】
前記候補マッチから最終マッチの１つまたは複数の系列を特定することをさらに含む、請求項１に記載の方法。
【請求項１１】
前記最終マッチの１つまたは複数の系列を特定することは、
内座層の数で前記候補マッチを降順に並べ替えることと、
最大数の内座層を有する第１の候補マッチを少なくとも１つの系列の第１の要素として最終マッチの少なくとも１つの系列を生成することと、
前記残りの候補マッチの前記内座層を包囲する多角形と、前記既存の系列の第１の要素の前記内座層を包囲する多角形との交差領域が、既定の閾値より大きい場合は、前記各残りの候補マッチを既存の系列に追加することと、
前記残りの候補マッチの前記内座層を包囲する多角形と、前記既存の系列の第１の要素の前記内座層を包囲する多角形との交差領域が、すべての既存の系列に対して既定の閾値を下回る場合は、前記残りの候補マッチを含む新しい系列を生成することと
を含む、請求項１０に記載の方法。
【請求項１２】
前記動き推定は、ＲＡＮＳＡＣアルゴリズムまたはその変形に基づいている、請求項１に記載の方法。
【請求項１３】
１つのクエリ画像を複数の画像とマッチングするシステムであって、画像は一組の特徴点および一組の対応する特徴ベクトルによって表され、
前記複数の画像の各々と前記クエリ画像との間の既定値より大きい推定一致の数に少なくとも一部は基づいて、前記複数の画像から推定一致画像を見出す推定一致モジュールと、
前記推定一致画像の各々と前記クエリ画像との間の推定一致のサブセットで位相同型性試験を行う位相同型モジュールと、
前記位相同型性試験を合格した前記推定一致画像の各々と前記クエリ画像との間の前記推定一致のサブセットを使用して動き推定を行う動き推定モジュールと、
前記動き推定に基づき前記クエリ画像にマッチする前記推定一致画像の１つまたは複数の系列を特定する最終特定モジュールと
を含むシステム。
【請求項１４】
コンピュータに１つのクエリ画像を複数の画像とマッチングする方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、画像は一組の特徴点および一組の対応する特徴ベクトルによって表され、
前記方法は、
前記複数の画像の各々と前記クエリ画像との間の既定値より大きい推定一致の数に少なくとも一部は基づいて、前記複数の画像から推定一致画像を見出すことと、
前記推定一致画像の各々と前記クエリ画像との間の推定一致のサブセットで位相同型性試験を行うことと、
前記位相同型性試験を合格した前記推定一致画像の各々と前記クエリ画像との間の前記推定一致のサブセットを使用して動き推定を行うことによって候補マッチを見出すことと
を含むコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、デジタル画像処理の分野に関する。より詳細には、本発明は、画像を別の画像とマッチングするための方法およびシステムに関する。
【背景技術】
【０００２】
画像マッチングは、コンピュータ画像認識、オブジェクト認識、動作追跡、３Ｄモデリングなどに使用される基礎的な技術である。画像マッチングは、２つの画像が同じ内容を有するかどうかを照合するために実行される。２つの画像は、まったく同じである必要はない。たとえば、片方の画像がもう片方の画像と比べて回転されていたり、異なる視点から撮影されていたりしても良く、または片方の画像が、他方の画像の拡大縮小版でもよい。さらに、その２つの画像は、異なる照明条件下で撮影されていてもよい。２つの画像にこのような差異があっても、同じ内容、場面または対象物が含まれている。したがって、画像マッチング技術が、画像を効果的にマッチングするために使用される。
【０００３】
通常の画像マッチングアルゴリズムは、被写体または場面の画像が多くの特徴点を含むという事実を活用する。特徴点は、画像の回転、縮尺、および視点または照明条件の変化に強い、画像内の特有の点である。このことは、これらの特徴点が、２つの画像が上述のように異なる場合であっても、両方の画像に存在することが多いことを意味する。したがって、画像マッチングアルゴリズムの第１段階は、これらの特徴点を画像内に見出すことである。通常、画像ピラミッドが、画像の特徴点を決定するために構成される。画像ピラミッドは、画像の尺度空間の表象である、すなわち画像ピラミッドは、様々なピラミッド画像を含み、ピラミッド画像のそれぞれが、特定の縮尺での画像の表象である。尺度空間の表象によって、画像マッチングアルゴリズムが全体の縮尺が異なる画像をマッチングすることが可能になる。画像ピラミッド内のピラミッド画像の特徴点を決定後、特徴点の方向が、特徴点における局所画像の勾配に基づいて判定される。これらの方向は、特徴点の不変性を回転に対して提供する。特徴ベクトルの表象は、局所の歪みおよび照明の著しい変化のために提供される、すなわち、特徴ベクトルは、歪みおよび照明条件の変化によって変わることがない。
【０００４】
ピラミッド画像の特徴点、特徴点の方向および特徴ベクトルは、画像の完全な表象を形成する。これらの表象を、マッチ画像を見出すために複数の画像にわたって比較することができる。一対の画像は、画像の特徴点のマッチングに基づいてマッチングされる。該対の画像は、十分な数の特徴点が他方の画像の対応する特徴点に視覚的および幾何学的の両方で一致すると、マッチしていると判定できる。相互に近接した特徴ベクトルは、視覚的に類似しており、対応する特徴点は、「推定一致」または「一致」と呼ばれる。推定一致は、一般に幾何学的一致を試験するために統計的アルゴリズムによって処理される。
【０００５】
一般に、画像の幾何学的マッチングのために、使用される統計的アルゴリズムは、無作為標本コンセンサス（Ｒａｎｄｏｍ  Ｓａｍｐｌｅ  Ｃｏｎｓｅｎｓｕｓ）（ＲＡＮＳＡＣ）アルゴリズムであるが、ＲＡＮＳＡＣ様アルゴリズムの他の変形または他の統計的アルゴリズムも使用することができる。ＲＡＮＳＡＣでは、小さい組の推定一致が無作為に抽出される。その後、これらの抽出された特徴点を使用して幾何学的変換が生成される。該変換の生成後、そのモデルに適合する推定一致が決定される。そのモデルに適合する推定一致は、幾何学的に一致し、「内座層」と呼ばれる。その後、内座層の総数が判定される。上述のステップは、反復／試行回数が既定の閾値を超えるまで、または画像に対する内座層の数がマッチとして判定できるのに十分に大きくなるまで繰り返される。ＲＡＮＳＡＣアルゴリズムは、モデルに対応する内座層の最高数を有するモデルを戻す。
【０００６】
このタイプの方法の使用に伴う１つの問題は、統計的アルゴリズムによって生成された可能な変換の組が、物理的に有効な変換の組より大きいことがあり得ることである。たとえば、変換は長方形の１辺を反転させて、剛性物の達成が不可能な湾曲を引き起こし得る。別の例では、変換は長方形全体を反転させ得るが、これはオブジェクトの鏡映の像を撮ることによってのみ達成可能な変換である。これによって画像の誤ったマッチングを引き起こす可能性がある。さらに、変換によって生成されるパラメータ／点の分析は、変換自体が物理的に無効または実現不可能であってもなされるので、これが無益な計算をする可能性がある。
【０００７】
推定一致における各特徴点は、その方向を伴う。回転不変性が必要とされる適用例において、変換が有効になるために、好ましくは推定一致における２つの特徴点の方向を保たなければならない。ＲＡＮＳＡＣを使用する多くの適用例は、この制約を考慮しない。
【０００８】
推定一致が緊密にマッチすると判定された場合であっても、推定一致のみでは一般に、対の画像が最終のマッチを形成することを確実にすることはない。推定一致は、対の画像の特徴点間の視覚的類似についての情報を与えるに過ぎない。このことは一般に、対の画像間の最終マッチングを判定するには十分ではない。両方の画像の対応する領域が、多数の推定一致を生成する可能性がある。たとえば、画像の特徴が、複数の尺度で顕著である場合、多数の特徴点が生成され得、恐らくは複数の推定一致を引き起こす。これらの推定一致の１つを選択して変換を生成することは、他の推定一致も内座層になることを意味し、それによって、この変換を使用してマッチングされた２つの画像が真にマッチしているという錯覚の情報を作り出す。推定で１組の対応する特徴点の１つを除くすべてを除去することは誤った手法である。なぜなら推定一致が異なるクエリ画像に対しては複数の推定一致が存在しない可能性があり、偽って解釈された複数の推定一致があり得るので、どの特徴点が最良であるかを知り得ないからである。換言すると、一般に推定一致のみの使用では、明白なマッチをクエリ画像とデータベース画像との間に確立するために、十分な情報を提供できない。
【０００９】
さらに、２つの画像が企業もしくは他の団体のロゴのような画像の要素または小部分を共有し得る可能性はある。また画像は、文字列の一部を同じ書体で共有し得る。これらの共有した要素は、画像マッチングを言明するのに十分な内座層を生成し得るが、実際には２つの画像は類似していない。さらに、クエリ画像は、多数の画像対象を有し得、画像対象のそれぞれが、別個のデータベース画像で表される場合があり得る。データベース画像は、クエリ画像がマッチングされる必要がある複数の画像である。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述の限界を打開する改良された画像マッチング方法の存在が必要とされている。
【課題を解決するための手段】
【００１１】
本発明の目的は、クエリ画像を複数の画像に対してマッチングするための方法、システム、およびコンピュータ・プログラム製品を提供することである。
【００１２】
本発明の目的は、幾何学的に一貫する一致を決定するための方法、システム、およびコンピュータ・プログラム製品を提供することである。
【００１３】
本発明の目的は、物理的に有効な変換を生成するための方法、システム、およびコンピュータ・プログラム製品を提供することである。
【００１４】
本発明の目的は、異なる視点および／もしくは照明条件から捕捉された同一の対象または場面の２つ以上の画像をマッチングするための方法、システム、およびコンピュータ・プログラム製品を提供することである。
【００１５】
本発明の様々な実施形態が、画像マッチングのための方法、システム、およびコンピュータ・プログラム製品を提供する。まず、推定一致画像、すなわち非常に多数の推定一致を有する画像が、複数の画像から複数の画像とクエリ画像との間の推定一致を見出すことによって決定される。その後、変換が画像に対して決定される前に、位相同型性試験が行われ、あらゆる物理的に無効な変換が回避される。位相同型性試験では、推定一致画像内の推定一致のサブセットの特徴点とクエリ画像との間の位相同型性が決定される。推定一致のサブセットが位相同型性試験に不合格する場合、そのサブセットは破棄され、推定一致の新しいサブセットが選択されて変換が確立される。さらに、該変換から獲得した特徴点に対して方向一致試験が実行されて、変換の有効性をさらに試験する。次に推定一致のサブセットを使用して、動き推定を行うことによって候補マッチが決定される。クエリ画像と変換に適合するデータベース画像との間の推定一致が、内座層として決定される。
【００１６】
その後、画像の内座層上で、カバー範囲の試験が実行される。カバー範囲の試験では、クエリ画像およびデータベース画像の両方の内座層によって包囲される領域の百分率が測定される。該画像は、２つの百分率の最大値が既定の閾値より小さいと、マッチの候補から破棄される。その後、最終の画像マッチが、１組の条件に基づいて特定される。第１の条件は、候補画像に対する内座層の数が内座層の既定数より大きいことである。さらに、第２の条件は、候補マッチと関連する二乗平均平方根（Ｒｏｏｔ  Ｍｅａｎ  Ｓｑｕａｒｅ）（ＲＭＳ）誤差が、既定の閾値より小さいことである。これらの試験を満たす画像が、最終のマッチ画像として戻される。複数の画像がこれらの試験を満たす場合があり得る。このような場合、カバー範囲の試験からの測定値を使用して、多数のデータベース画像がマッチしたかどうかを判定する。画像の同じ領域が多数のデータベース画像と一致する場合、これらの画像は、最終のマッチ画像が含む内座層の数の降順に戻される。
【図面の簡単な説明】
【００１７】
【図１】本発明の様々な実施形態が実行可能な画像環境を示す図である。
【図２】本発明の一実施形態に従って、画像をマッチングする方法を示す流れ図である。
【図３】本発明の別の実施形態に従って、画像をマッチングする方法を示す流れ図である。
【図４】本発明の別の実施形態に従って、画像をマッチングする方法を示す流れ図である。
【図５】本発明の一実施形態に従って、画像をマッチングする詳細な方法を示す流れ図である。
【図６】本発明の一実施形態に従って、画像をマッチングする詳細な方法を示す流れ図である。
【図７】本発明の一実施形態に従って、画像をマッチングする詳細な方法を示す流れ図である。
【図８】本発明の様々な実施形態に従って、画像をマッチングするのに使用可能なシステムを示す構成図である。
【発明を実施するための形態】
【００１８】
本発明の様々な実施形態が、示される添付図面とともに以下に説明されるが、本発明を限定するものではない。同様の記号は、同様の要素を示す。
【００１９】
図の要素は、本発明の実施形態の理解を深めるように簡略化して、明確に示されていることが当業者には理解されよう。
【００２０】
本発明の様々な実施形態は、画像をマッチングするための方法、システムおよびコンピュータ・プログラム製品に関する。該方法は、画像を表すためにその画像に存在する特徴点を使用する。該方法の第１のステップは、クエリ画像とデータベース画像との間で推定一致を判定することである。推定一致は、視覚的に相互に類似しているクエリ画像およびデータベース画像の１対の特徴ベクトルである。推定一致が決定された後、物理的に無効な変換を回避するために推定一致のサブセットに対して位相同型性試験が実行される。変換が決定された後、方向一致試験が実行される。１つの画像内の推定一致のサブセットの特徴点に対して１つのオフセット点が判定される。各オフセット点は、その対応する特徴点からその特徴点の方向の向きに移動される。該変換は、マッチングされる画像およびそのオフセット点のいずれか１つが、推定された方向と既定限度だけ異なる場合、推定一致のサブセット内の特徴点から得られた特徴点の方向に基づいて破棄される。続いて、位相同型性試験を満たす推定一致のサブセットを使用して、動き推定が実行される。動き推定は、クエリ画像とデータベース画像との間で幾何学的に一貫する推定一致を判定するために実行される。１組の条件に基づいて、最終マッチ画像が戻される。
【００２１】
図１は、本発明の様々な実施形態が実施可能な環境１００を示す。本発明は、コンピュータ・ビジョン、物体認識、動作追跡および三次元造形の分野に使用され得る。画像は、ＪＰＥＧ、ＧＩＦ、ＢＭＰなどの異なる形式でもよい。さらに、これらの画像の質および解像度は、用途によって異なり得る。また、マッチングされる画像は、厳密に同じ必要はないが、相互に変換された形であり得る。したがって、画像マッチングアルゴリズムは、画像が相互にマッチングできるように、特定の形式で表される画像である必要がある。
【００２２】
環境１００は、クエリ画像１０２および画像１０４ａ〜ｎのデータベースを含む。データベースは、クエリ画像１０２にマッチする画像（複数可）を見出すために検索される。マッチ画像は、クエリ画像１０２と厳密に同じ必要はないが、クエリ画像１０２と同じ内容を含むものでなければならない。たとえば、データベース１０４は、雑誌からの印刷広告のコピーを含み得るが、クエリ画像１０２は、同じ広告から撮った画像である。本発明の画像マッチングアルゴリズムは、クエリ画像１０２のマッチを画像１０４ａ〜ｎに見出すが、マッチは上記のように異なっていてもよい。画像マッチングアルゴリズムは、特徴点および特徴ベクトルに関して各画像を表すことによって作動する。画像の特徴点、方向および特徴ベクトルを使用して、画像間のマッチが決定される。本発明は、画像をマッチングする方法およびシステムを説明する。
【００２３】
図２は、本発明の一実施形態による、画像をマッチングする方法を示す流れ図である。図２は、好ましくは画像を別の画像とマッチングするために画像に対して実行するべき主要なステップの簡単な概説を提供する。図２の各ステップについては、図５、図６、および図７を用いて以下に詳述する。クエリ画像をデータベース画像とマッチングする前に、画像に関連する特徴点および特徴ベクトルが決定される。画像は、特徴点、特徴点の方向、およびそれらに対応する特徴ベクトルに基づいてマッチングされる。
【００２４】
ステップ２０２では、推定一致がクエリ画像の特徴点とデータベース画像との間で見出される。対応する特徴点に関連する特徴ベクトルを使用して、画像の推定一致が決定される。推定一致は、一方はクエリ画像から、他方はデータベース画像からの１対の特徴点であり、その１対の特徴点は相互に視覚的に類似している。推定一致は、ドット積をクエリ画像の特徴ベクトルとデータベース画像の特徴ベクトル間で見出すことによって決定することができる。特徴点の対は、ドット積の特徴ベクトルのドット積の大きさが既定値より大きいと、推定一致である。特徴ベクトルが単位長さを有するとき、ドット積の大きさは、特徴ベクトル間の角度の余弦に等しく、したがってそれらの近さを測定する。その後、ステップ２０４で、クエリ画像とデータベース画像との間の推定一致に基づいて推定一致画像が選択される。より詳細には、ステップ２０２で決定された推定一致の数および各データベース画像で見出された推定一致の数に基づいて、画像が推定一致画像として選択される。換言すると、推定一致画像は、データベース画像と比較した場合に十分な数の推定一致を有さなくてはならない。一実施形態では、推定一致画像は、少なくとも９個の推定一致を有さなくてはならない。画像が推定一致画像として選択された後、変換が生成されて２つの画像間の相対運動が説明される。さらに、対応する画像のサブセットを使用して、変換係数を決定する。ステップ２０６で、推定一致のサブセットがそれらの位相同型性について確認される。推定一致のサブセットが位相同型でない場合は、推定一致のサブセットは破棄される。２組の対応する点が位相同型であるのは、所与の２本の線の、一方が１組の１対の点を通り、他方が他の組の対応する点を通り、残りの対応する点が（上または下の）各線の同じ側にある場合である。このことは、物理的に無効な変換を伴う計算を回避するためになされる。推定一致の位相同型性が確認された後、動き推定が推定一致のこのサブセットを使用してステップ２０８で行われる。動き推定を行うために、変換マッピング特徴点が、サブセットでクエリ画像とデータベース画像との間（またはその逆）の推定一致において決定される。該変換は、クエリ画像の推定一致の特徴点に適用され、その特徴点に対応して一変換点がデータベース画像で獲得される。さらに、変換は、クエリ画像とデータベース画像との間の相対運動（回転、尺度変更など）を符号化する。推定一致は、変換点が特徴点の既定限度内にあるときは、内座層であると決定される。内座層がデータベース画像に対して決定された後、最終マッチがステップ２１０で特定される。最終マッチは、所定の閾値より大きい内座層数を有するデータベース画像である。内座層の総数は、クエリ画像とデータベース画像との間で視覚的マッチングおよび幾何学的マッチングの両方を備える特徴点の数に対応する。本発明の一実施形態では、所定の閾値は９である。さらに、二乗平均平方根（ＲＭＳ）誤差またはデータベース画像に関連した近似誤差は、好ましくは既定の閾値より少なくなければならない。本発明の一実施形態では、我々は最終変換を内座層全体に亘って計算し、各点の実際の位置と予想される位置との間の距離の二乗を計算し、これらの二乗距離の平均を計算し、二乗距離の平均平方根を画像幅の５％の既定の閾値と比較する。
【００２５】
図３は、本発明の別の実施形態による、画像のマッチング方法を示す流れ図である。図３は、好ましくは画像を別の画像とマッチングするために画像上で実行するべき主要なステップの簡単な概説を提供する。図３の各ステップについては、図５、図６、および図７を用いて以下に詳述する。さらに、本発明は、図３に記載されたステップによって限定されない。図３に表されたステップの多くの変形形態が、画像マッチングアルゴリズムの効率および精度を高めるために可能であることは、当業者には認識され理解されよう。
【００２６】
ステップ３０２では、クエリ画像の特徴点とデータベース画像との間で図２を用いて説明したように、推定一致が決定される。推定一致を使用して推定的に一致する画像を決定した後、推定一致のサブセットを使用してステップ３０４で図２を用いて説明したように、変換が生成される。方向の不一致が推定一致のサブセットに存在する場合は、ステップ３０４で計算された変換は、無効とみなされる。それ故、変換が有効になるために、各特徴点に関連する方向は、変換が各特徴点に適用された後、特定の許容限度内に維持されるべきである。変換の有効性を判定するために、方向一致試験がステップ３０６で行われる。試験は、ステップ３０４から獲得された推定一致に対して実行される。方向一致試験を実行するために、推定一致に存在する特徴点のオフセット点が、特徴点の方向の向きで決定される。この試験に使用される特徴点は、クエリ画像またはデータベース画像のいずれかに属する。その後、変換が、オフセット点および特徴点に適応される。画像の特徴点の予想される方向が、変換された点から決定される。特徴オフセット点の予想される方向が、ステップ３０４から獲得された特徴点の実際の方向と許容限度より大きく異なるときに、変換が無効となる。該限度は、画像の遠近歪みが、方向を正確に維持しないので、十分に大きくなければならない。本発明の一実施形態では、０．１ラジアンの限度が使用される。特徴オフセット点の予想される方向は、ステップ３０４から獲得された特徴点の実際の方向と比較される。１つまたは複数の方向が限度を超える場合、変換は破棄される。そうでなければ、動き推定が、図２を用いて上述したようにステップ３０８において行われる。動き推定を実行する間、方向一致試験を再度動き推定によって見出された内座層で使用することができる。内座層が方向一致試験を満たさない場合は、内座層は破棄される。
【００２７】
内座層の方向一致が決定された後、最終マッチ画像がステップ３１０で図２を用いて記載されたように特定される。
【００２８】
図４は、本発明の別の実施形態による、画像のマッチング方法を示す流れ図である。図４は、好ましくは画像を別の画像とマッチングするために画像上で実行するべき主要なステップの簡単な概説を提供する。図４の各ステップについては、図５、図６、および図７を用いて以下に詳述する。図４に表されたステップの多くの変形形態が、画像マッチングアルゴリズムの効率および精度を高めるために可能であることは、当業者には認識され理解されよう。
【００２９】
ステップ４０２では、クエリ画像の特徴点とデータベース画像との間で決定された推定一致に基づいて、推定一致画像が見出される。このステップは、すでに図２を用いて詳細が記載されている。推定一致の決定後、推定一致のサブセットが、推定一致から無作為に抽出される。推定一致のこのサブセットを使用して、動き推定が、ステップ４０４で図２を用いて記載されたように行われる。動き推定は、ステップ４０２から判定された推定一致で実行されて内座層の組を決定する。動き推定を行った後、データベース画像のカバー範囲がステップ４０６で決定される。カバー範囲の試験は、データベース画像の内座層の被覆率を判定する。カバー範囲の試験では、内座層の領域の画像の領域に対する割合が、クエリ画像およびデータベース画像の両方に対して決定される。本発明の一実施形態では、内座層の領域は、内座層の凸包によって形成された多角形の領域である。凸包は、全内座層を包囲する最小の多角形である。本発明の別の実施形態では、内座層の領域は、全内座層を包囲する、軸に位置合わせした最小の外接矩形である。このような矩形は、画像の境界線に（水平または垂直に）平行な辺を有するべきである。データベース画像は、２つの割合の最大値が既定の閾値より小さいと、拒絶される。カバー範囲の試験は、画像に存在する共通の要素が単に比較されるのではなく、データベース画像全体がクエリ画像に対してマッチングされることを判定するために実行される。カバー範囲の試験が実行された後、最終マッチング画像がステップ４０６で図２を用いて記載されたように特定される。
【００３０】
図５、図６、および図７は、画像マッチングの詳細の方法を示す流れ図を示す。クエリ画像を他の画像とマッチングするために、画像は特徴点、特徴点の方向、および対応する特徴ベクトルの形で表される。このような表象は、マッチング画像を見出すために複数の画像にわたって比較することができる。画像マッチングのための方法は、クエリ画像とデータベース画像との間で独立して実行される。しかし、曖昧性を低減させるために、画像マッチングアルゴリズムの以下の記述が、単一のデータベース画像を考慮して説明されている。
【００３１】
２つの画像をマッチングするために、クエリ画像とデータベース画像との間で推定一致が特定される。推定一致は、相互に視覚的に類似しているクエリ画像およびデータベース画像内の特徴点の対である。
【００３２】
ステップ５０２では、クエリ画像の特徴ベクトルとデータベース画像の特徴ベクトルとの間でドット積が計算される。クエリ画像およびデータベース画像の特徴ベクトルに対するドット積の計算は、２つのマトリックスを乗じてなされ得る。一方のマトリックスはその行が１つの画像の特徴ベクトルに対応し、他方はその列が他方の画像の特徴ベクトルに対応する。ドット積は、単位ベクトル間のユークリッド距離に対する高速近似である。
【００３３】
ステップ５０４では、既定の大きさより大きいドット積は、どの特徴ベクトルの対が推定一致かを示す。本発明の一実施形態では、既定の大きさは、０．９３である。１つの画像の１つの特徴ベクトルは、複数の推定一致に関与し得る。この現象の考えられる理由は、その特徴ベクトルに対応する特徴点が、黒色背景上の９０度の白色隅部などの一般的なものであることである。特徴ベクトルが関与する推定一致が多過ぎる場合、最大でもそれらの推定一致の１つしか正しくないので、動き推定を実行する機能を低下させ得る。この理由は、ＲＡＮＳＡＣアルゴリズム（動き推定アルゴリズム）が内座層である該一致のある一定の割合に依存するためであり、一致の実際の百分率が低い場合は、内座層のみからなるサブセットを無作為に選択することが著しく困難になる。本発明の一実施形態では、６を超える推定一致に関与する特徴ベクトルは、考慮の対象から除外される。
【００３４】
ステップ５０６では、データベース画像の推定一致の数の確認が行われる。推定一致の数は、既定の閾値と比較される。データベース画像の推定一致の数が既定の閾値より小さい場合は、データベース画像はステップ５０８で破棄される。閾値は、好ましくは少なくともステップ５１０で選択されたサブセットに使用される推定一致の数およびステップ５２４でマッチが確信されるのに要する内座層の数より大きくなければならない。閾値はまた、クエリ画像にマッチする可能性が少ない画像の計算を回避するために、他のデータベース画像に見出される推定一致の数に依存し得る。このステップにより、計算コストが高い動き推定が、多くの他の画像より少ない一致を有する画像では実行されないことが確実になる。
【００３５】
推定一致を決定し、どの画像を続行するかを決定した後、動き推定が、これらの推定マッチ画像で実行される。動き推定の過程で、幾何学的変換が生成される。クエリ画像の特徴点は、その変換に基づいてデータベース画像の特徴点にマッピングされる。本発明に選択された変換は、ホモグラフィである。ホモグラフィとは、クエリ画像の回転、拡大および縮小を符号化する変換である。クエリ画像とデータベース画像との間の動き推定の記載は、ステップ５１０〜ステップ５１６に示されている。
【００３６】
ステップ５１０では、推定一致のサブセットが、ステップ５０６から獲得した推定一致から無作為に選択される。本発明の一実施形態では、サブセットは、最低４個の推定一致がホモグラフィを生成するために必要であるので、無作為に選択された４個の推定一致を含み得る。
【００３７】
ステップ５１２では、位相同型性試験が推定一致のサブセットに対して行われる。２組の点が位相同型であるのは、両方の組で任意の点から他の任意の点に引かれた任意の射線に対して、残りの点が射線の左側または射線の右側にある場合である。位相同型性試験を行う第１のステップとして、一方の画像の２つの特徴点が、１本の直線で接続され、他方の画像の対応する点に対しても同様の操作が行われる。別の一致が選択され、クエリ画像の特徴点からクエリ画像の線までの符号付きの距離が計算される。同様の計算がデータベース画像に対してなされる。２つの符号が異なる場合は、推定一致のサブセットは位相同型ではない。２つの符号が同じ場合は、別の一致が試験される。しかし、２つの対応する点がそれぞれの線上に位置するか、またはそれぞれの線に非常に近接していると、厄介な状況が起こる可能性がある。その場合、線に対して３点（線を生成した２点および試験される点）の順番を判定するために、試験が行われる。対応する点が線について同じ順番を有する場合は、それらの点は位相同型である。推定一致のサブセットが位相同型試験に合格しない場合は、物理的に無効な変換が生じ、したがって該サブセットはステップ５１４で破棄され、推定一致の新しいサブセットがステップ５１０で選択される。
【００３８】
推定一致のサブセットが位相同型性試験に合格すると、動き推定がステップ５１６で、ステップ５１０から獲得した推定一致のサブセットに対して行われる。動き推定の過程では、変換が生成される。この変換を使用して、クエリ画像の特徴点をデータベース画像の特徴点にマッピングする。本発明に選択された変換は、ホモグラフィである。ホモグラフィ以外の変換もまた、動き推定を行うために使用できることは、当業者には理解されよう。たとえば、抽出された１組の３個の推定一致から生成可能なアフィン変換は、動き推定に使用できる。
【００３９】
推定一致のサブセットの推定一致を、それらのセントロイドを（０，０）に有し、平均距離を原点から√２にするように正規化する。これらの点は同次であり、式[ｘｙｗ]（式中ｗ＝１）を有する。これは、１自由度に要する計算を除去することによって数値的に安定した計算をするためになされる。推定一致の正規化後、２つの拘束が１つの推定一致から生成される。これらの拘束は２列のマトリックスとして表される：
【００４０】
【数１】
0005347034.tif 000002
【００４１】
（式中Ｐ1＝[ｘ1ｙ1ｗ1]およびＰ2＝[ｘ2ｙ2ｗ2]は推定一致における２点である）。４個の推定一致は、１個の８ｘ９のマトリックスを生成する。このマトリックスの特異値分解（ｓｉｎｇｕｌａｒ  ｖａｌｕｅ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）（ＳＶＤ）の最後の右特異値ベクトルは、行順でホモグラフィの係数である。これらの係数は、一方の画像の４個の特徴点を他方の画像の特徴点にマッピングする。
【００４２】
ステップ５１６で決定されたホモグラフィは、位相的に有効であり得るが、特徴点によって課された方向制限によってホモグラフィが実行不可能になり得る。ホモグラフィを実行可能にするために、各特徴点に関連する方向は、ホモグラフィが各特徴点に適用された後、特定の許容限度内に維持されなければならない。ホモグラフィの実行可能性を決定するために、方向一致試験がステップ５１８で行われる。該試験は、ステップ５１０から獲得した推定一致に対して行われる。方向一致試験では、推定一致のサブセット内の一方の画像からの特徴点のオフセット点が、特徴点の方向の向きで決定される。その後、ホモグラフィが、これらのオフセット点に適用される。該画像の特徴点の予想される方向は、他方の画像の特徴点とそれらに対応して変換されたオフセット点との間の移動から得られる。ホモグラフィを適用後に得られた特徴点の予想される方向が、特徴点の実際の方向と既定の許容限度を超えて異なると、ホモグラフィは実行不可能である。このような場合、推定一致のサブセットは、ステップ５１４で破棄され、新しいサブセットがステップ５１０で選択される。一実施形態では、既定の許容限度は、０．１ラジアンである。方向試験では、クエリ画像とデータベース画像との間の遠近歪みを良好に考慮しないので、大きい限度が必要である。
【００４３】
ステップ５２０では、オフセット点から獲得した特徴点の方向が、ステップ５１８から獲得した特徴点の方向と比較される。特徴点の方向が変換を適用後に一貫しない場合、ホモグラフィは、実行不可能とみなされる。こうした場合、推定一致のサブセットは、ステップ５１４で破棄され、推定一致の新しいサブセットがステップ５１０で選択されて、新しい変換が生成される。
【００４４】
内座層は、クエリ画像およびデータベース画像の推定一致の特徴点からステップ５２２で計算される。内座層は、ホモグラフィを通して相互にマッピングする推定一致である。内座層の数は、２つの画像間のマッチングの尺度である。内座層を計算する前に、ホモグラフィの条件数が判定される。理論上は、３ｘ３のマトリックスであるホモグラフィが、ランク３を有することのみが必要とされる。しかし、アルゴリズムの数値的安定のために、よく調整されたマトリックスのより強い拘束が望ましい。最大の特異値の最小の特異値に対する比率である条件数は、１０7未満でなければならない。、その後、推定一致は、各画像のホモグラフィ下での実際の特徴点とそれらの予想値との間の距離が、既定の限度内であるとき、可能性のある内座層として決定される。ｐ1およびｐ2が１対の対応する特徴点である場合、変換Ｈは、予想される特徴点位置Ｈｐ1およびＨ-1ｐ2を判定するために前後両方向に適用される。これらの予想される特徴点は、それらのｗ成分を１として有するように正規化される。その後、Ｈｐ1−ｐ2およびｐ1−Ｈ-1ｐ2のＬ2の二乗ノルムが計算される。これらの差の合計が、既定の閾値より小さい場合は、推定一致ｐ1およびｐ2は可能性のある内座層である。本発明の一実施形態では、既定の閾値は、０．０１である。
【００４５】
可能性のある内座層が決定された後、上述の方向一致試験が可能性のある内座層に対して行われる。方向一致試験を満たさない可能性のある内座層は破棄され、残りの内座層はデータベース画像に対する内座層として決定される。これらの内座層を使用して、最終ホモグラフィを最小二乗適合を使用して計算する。このホモグラフィを使用して、点を画像の対の間でマッピングし、二乗平均平方根（ＲＭＳ）誤差またはデータベース画像に関する近似誤差を判定する。
【００４６】
内座層を確立後、この変換で見出された内座層の総数とデータベース画像の変換の内座層の総数が、ステップ５２４で比較される。この変換がこれまでに見出された最良の内座層より多い内座層を有する場合は、この変換およびその内座層は、ステップ５２６によって保持される。あるいは、その内座層は破棄され、推定一致の新しいサブセットがステップ５１０で選択される。
【００４７】
ステップ５２８では、動き推定の段階を継続するかどうかの決定がなされる。十分な数の試行がなされた場合は、アルゴリズムが先に進む。本発明の一実施形態では、５００回の試行が使用される。代替的に、これまでに見出された最良の変換での内座層の数が、推定一致の数の十分に高い割合である場合は、統計的アルゴリズムは、より良い変換が見出される見込みがないと決定する可能性があり、その場合は動き推定段階が早期に終結する。
【００４８】
データベース画像は、画像に関連する内座層の数が既定の閾値より大きいと、可能性のあるマッチとしてステップ５３０で選択される。既定の閾値は８の内座層であり得る。その後、可能性のあるマッチに対する二乗平均平方根（ＲＭＳ）誤差または近似誤差が、ステップ５３２で確認される。ＲＭＳ誤差が既定限度以上である場合は、その過程はステップ５０８に戻され、データベース画像は破棄される。本発明の一実施形態では、既定のＲＭＳ誤差の限度は、データベース画像の幅の２．５％であり得る。
【００４９】
しかし、ＲＭＳ誤差または潜在的マッチングの近似誤差が既定限度を下回る場合は、可能性のあるマッチの内座層のカバー範囲がステップ５３４で計算される。カバー範囲の試験では、データベース画像およびクエリ画像の両方の内座層によって包囲された領域の割合が測定される。カバー範囲の試験を使用して、画像の小部分（たとえば、ロゴまたは同じ書式を有する文字列）のみが、クエリ画像とデータベース画像との間で共有される状況が回避される。カバー範囲は、内座層の組によって包囲された領域の画像領域に対する比率として定義される。一部の実施形態を利用して、内座層の組を包囲する多角形を計算できる。一実施形態では、最小ならびに最大のｘ座標およびｙ座標を使用して、外接矩形を形成する。別の実施形態では、内座層の凸包が計算される。クエリ画像およびデータベース画像の内座層を包囲する多角形の領域を、それぞれＡpqおよびＡpdと示し、クエリ画像およびデータベース画像の面積をそれぞれＡqおよびＡdと示すと、カバー範囲Ｃは以下のように定義できる：
【００５０】
【数２】
0005347034.tif 000003
【００５１】
カバー範囲Ｃは好ましくは、既定の閾値より大きく、画像の一部のみではなく、画像全体がマッチされることを確実にしなければならない。ステップ５３６では、カバー範囲は、既定のカバー範囲の閾値と比較される。本発明の一実施形態では、既定のカバー範囲の閾値は０．３であり得る。
【００５２】
ステップ５３８では、上記の試験すべてに合格した候補のデータベース画像が、最終マッチとなる。ステップ５４０では、これ以上データベース画像がないかどうかが確認される。いくつかの画像が残っている場合は、同じ手順がステップ５０４から開始されて反復される。複数の画像がすべての要件を満たして最終マッチングして決定される場合があり得る。その場合、最終マッチは、内座層の数の降順にステップ５４２において並び替えられる。
【００５３】
ステップ５４４では、クエリ画像が複数のデータベース画像を含む場合に対処するために、ステップ５４２からの最終マッチの並べ替えられた一覧が分割される。我々は、最終マッチを検討し、その内座層を包囲する多角形を、最終マッチの並べ替えられた一覧の既存の系列の先頭（最初の要素）の内座層を包囲する多角形と比較する。最終マッチの多角形と系列の先頭の多角形の交差面積の、２つの多角形のより小さい面積に対する割合が、既定の閾値より大きい場合は、２つのマッチは実質的に重複するとみなされ、最終マッチはその系列に追加される。最終マッチの多角形が、いずれの系列の先頭の多角形とも実質的に重複しない場合は、最終マッチは、新しい系列の先頭になる。このようにして、画像の互いにつながっていない領域を占める複数の画像マッチが、それらの位置とともに報告できる。１つのマッチのみがエンドユーザに戻すことが可能な場合は、画像の中心に最も近い系列の先頭が、使用され得る。
【００５４】
図８は、本発明の様々な実施形態による、画像をマッチングするために使用するシステムの要素を示す構成図である。該システムは、クエリ画像および複数のデータベース画像の特徴表現を入力として取り込み、最終マッチ画像を各最終マッチ画像が含む内座層の数の降順に出力する。図８は、推定マッチングモジュール（Ｐｕｔａｔｉｖｅ  Ｍａｔｃｈｉｎｇ  Ｍｏｄｕｌｅ）（ＰＭＭ）８０２、動き推定モジュール（Ｍｏｔｉｏｎ  Ｅｓｔｉｍａｔｉｏｎ  Ｍｏｄｕｌｅ）（ＭＥＭ）８０４、カバー範囲の試験モジュール（Ｃｏｖｅｒａｇｅ  Ｔｅｓｔ  Ｍｏｄｕｌｅ）（ＣＴＭ）８０６および最終特定モジュール（Ｆｉｎａｌ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｍｏｄｕｌｅ）（ＦＩＭ）８０８を含む。
【００５５】
ＰＰＭ８０２は、データベースの特徴と視覚的に類似している特徴をクエリ画像で見出すように構成されている。ＰＰＭ８０２は、ドット積をクエリ画像の特徴ベクトルとデータベース画像の特徴ベクトルとの間で計算する。また、ＰＭＭ８０２は、該ドット積を既定値と比較し、特徴点のドット積が既定値より大きい特徴点の対を推定一致として出力する。これらの推定一致はＭＥＭ８０４に入力される。
【００５６】
ＭＥＭ８０４は、十分な推定一致を有するデータベース画像の組の中から幾何学的に一致するデータベース画像の組を判定する。このモジュールは、推定一致のサブセットを無作為に抽出して変換を生成する。ＭＥＭ８０４はまた、位相同型性を推定一致のサブセットの各推定一致間で決定するために、位相同型試験を推定一致のサブセットで実行するように構成されている。さらに、ＭＥＭ８０４は、位相同型性試験に合格する推定マッチのサブセットを使用して、変換を決定するように構成されている。ＭＥＭ８０４は、変換を、方向一致について、推定一致のサブセットに対して、次いで該変換下でマッチする特徴点に対して試験する。ＭＥＭ８０４は、結果として得られる内座層を既定の閾値より十分に大きい数の内座層を有し、かつ既定限度より小さいＲＭＳ誤差または近似誤差を有する各データベース画像に対して出力するように構成されている。特に、このタスクは、内座層計算モジュール（Ｉｎｌｉｅｒｓ  Ｃｏｍｐｕｔｉｎｇ  Ｍｏｄｕｌｅ）（ＩＣＭ）８１０によって実行される。ＩＣＭ８１０は、内座層を推定一致のサブセットからクエリ画像と推定一致画像との間で変換を使用して計算する。ＭＥＭ８０４は、結果として得られる内座層を入力としてＣＴＭ８０６に出力し、ＣＴＭ８０６は、カバー範囲の試験をデータベース画像に対して実行する。その後、カバー範囲の試験を満たすデータベース画像は、入力としてＦＩＭ８０８に提供される。ＦＩＭ８０８は、最終マッチングを各最終マッチングによって含まれた内座層の数の降順に並び替える。さらに、ＦＩＭ８０８は、最終マッチングを１つまたは複数の系列に分割し、該系列（複数可）を出力として提供するように構成されている。
【００５７】
本発明の様々な実施形態によれば、本発明は、有効に画像をマッチングする方法を提供する。本発明は、１つの画像を１つまたは複数の画像と有効にマッチングする一方で、起こり得る不要な計算を減少させる。該方法は１組の試験を使用して、マッチングするのに不適当な画像もしくは無駄な計算となる不適当な画像を引き起こす可能性のある、有り得ない変換または実行不可能な変換が試験されるのを排除する。
【００５８】
また、疑似の多数のマッチングを有する特徴は、画像全体によく見受けられ、真の画像マッチングに向けて貢献しないので、これらの特徴は破棄される。カバー範囲の試験が、マッチングされた特徴がクエリ画像またはデータベース画像のいずれの領域も十分にカバーし、単に画像の小部分ではないことを確実にするために行われる。複数のデータベース画像を含むクエリ画像を効率よく取り扱うことができる。
【００５９】
本発明に記載される画像をマッチングするシステム、またはいかなるその構成要素も、コンピュータ・システムとともに使用するコンピュータ・プログラム製品の形状で具現化され得る。コンピュータ・プログラム製品は、コンピュータが使用できる媒体を有し、該媒体は、その上に画像をマッチングするように具現化したコンピュータ可読コードを有する。コンピュータ・システムの典型的な例には、汎用コンピュータ、プログラムされたマイクロプロセッサ、マイクロ・コントローラ、周辺集積回路素子、および本発明の方法を構成するステップを実施可能な他の装置または装置の配置が含まれる。
【００６０】
コンピュータ・システムは通常、コンピュータ、入力装置、および表示装置を含む。コンピュータはさらに、マイクロプロセッサを含む。マイクロプロセッサは、コミュニケーション・バスに接続される。コンピュータはまた、メモリを含む。メモリは、ランダム・アクセス・メモリ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）（ＲＡＭ）または読み取り専用メモリ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）（ＲＯＭ）であり得る。コンピュータ・システムはさらに、記憶装置を含む。記憶装置は、ハード・ディスク・ドライブまたはフロッピー・ディスク・ドライブ、光ディスク・ドライブなどの、リムーバブル記憶装置であり得る。記憶装置はまた、コンピュータ・プログラムまたは他の命令をコンピュータ・システムにロードする他の同様の手段でもよい。コンピュータ・システムはまた、通信装置も含む。通信装置によってコンピュータが他のデータベースおよびインターネットに入出力（Ｉ／Ｏ）インターフェースを介して接続可能になり、データが他のデータベースから転送および受信可能になる。通信装置には、モデム、イーサネット・カードまたはコンピュータ・システムをデータベースならびにＬＡＮ、ＭＡＮ、ＷＡＮおよびインターネットなどのネットワークに接続可能になる、あらゆる他の同様の装置が含まれ得る。コンピュータ・システムによって、ユーザからの入力が入力装置を介して容易になり、Ｉ／Ｏインターフェースを介して該システムにアクセス可能になる。
【００６１】
コンピュータ・システムは、入力データを処理するために１つまたは複数の記憶素子に保存された１組の命令を実行する。記憶素子はまた、データまたは所望の他の情報も格納し得る。記憶素子は、情報源または物理記憶素子の形状で処理機内に存在し得る。
【００６２】
プログラム可能な命令は、処理機に本発明の方法を実行するステップなどの具体的なタスクを実行するよう命令する様々なコマンドを含み得る。記載された方法およびシステムはまた、ソフトウェア・プログラミングもしくはハードウェアのみを使用して、または２つの技術の様々な組合せによって実施できる。本発明は、コンピュータで使用されるプログラミング言語およびオペレーティング・システムから独立している。本発明のための命令は、「Ｃ」、「Ｃ＋＋」、「Ｖｉｓｕａｌ  Ｃ＋＋」および「Ｖｉｓｕａｌ  Ｂａｓｉｃ」を含むがこれに限定されない、すべてのプログラミング言語で記述することができる。さらに、ソフトウェアは、本発明に記載されているように、個別のプログラムの集合体、大規模なプログラムのプログラム・モジュールまたはプログラム・モジュールの一部の形状であり得る。ソフトウェアはまた、モジュラー・プログラミングをオブジェクト指向プログラミングの形状で含み得る。処理機による入力データの処理は、ユーザ・コマンド、前の処理の結果または別の処理機によってされた要求に応答し得る。本発明はまた、「Ｕｎｉｘ（登録商標）」、「ＤＯＳ」、および「Ｌｉｎｕｘ」を含むが、これに限定されない、すべてのオペレーティング・システムおよびプラットフォームで実施可能である。
【００６３】
プログラム可能な命令は、コンピュータ可読媒体に格納および転送可能である。プログラム可能な命令はまた、データ信号により搬送波を通して転送可能である。本発明はまた、コンピュータ可読媒体、上記の方法およびシステムを実施可能な製品またはその多くの可能な変形形態を含むコンピュータ・プログラム製品で具現化できる。
【００６４】
付記項１  １つのクエリ画像を複数の画像とマッチングする方法であって、画像は一組の特徴点および一組の対応する特徴ベクトルによって表され、
ａ．複数の画像の１つとクエリ画像との間で推定一致を見出すことによって複数の画像から推定一致画像を見出すことと、
ｂ．１つの推定一致画像とクエリ画像との間の推定一致のサブセット間で位相同型性を確認することと、
ｃ．１つの推定一致画像とクエリ画像との間の推定一致のサブセットを使用して動き推定を行うことによって候補マッチを見出すことと、を含む方法。
【００６５】
付記項２  推定一致画像は、推定画像の推定一致の数が既定値および推定画像に見出された推定一致の数に基づく値の両方より大きい推定画像から選択される、付記項１に記載の方法。
【００６６】
付記項３  推定一致を見出すことは、複数の画像の１つの特徴ベクトルと既定値より大きいクエリ画像の特徴ベクトルとの間にベクトル・ドット積を見出すことを含む、付記項１に記載の方法
【００６７】
付記項４  候補マッチを見出すことは、クエリ画像と動き推定によって得られた推定一致画像との間で推定一致の組から一組の内座層を計算することを含む、付記項１に記載の方法。
【００６８】
付記項５  候補マッチおよびクエリ画像の両方の内座層によって包囲される領域の百分率を測定することと、２つの百分率の最大値が既定の閾値より小さいとき、候補マッチを拒否することと、をさらに含む、付記項４に記載の方法。
【００６９】
付記項６  動き推定を実行することは、対応する推定一致のサブセット内の特徴点間で変換を計算することを含む、付記項１に記載の方法。
【００７０】
付記項７  推定一致のサブセット内の特徴点に対して方向一致試験を実行することをさらに含む、付記項６に記載の方法。
【００７１】
付記項８  
ａ．一方の画像の推定一致のサブセットにおいて特徴点に対するオフセット点を決定することであって、該オフセット点は、その対応する特徴点から該特徴点の方向の向きに移動されることと、
ｂ．他方の画像における推定一致のサブセット内の特徴点に対応する第２のオフセット点を生成するためにオフセット点を変換することと、
ｃ．他方の画像で推定一致のサブセット内の特徴点と、その対応する変換されたオフセット点との間の方向が、既定限度によってその見積られた方向と異なるとき、変換を破棄することと、をさらに含む、付記項７に記載の方法。
【００７２】
付記項９  内座層の数が内座層の既定数より大きく、候補マッチングの近似誤差が既定の閾値より小さい候補マッチを選択することによって候補マッチから最終マッチの１つまたは複数の系列を特定することをさらに含む、付記項１に記載の方法。
【００７３】
付記項１０  候補マッチから最終マッチの１つまたは複数の系列を特定することをさらに含む、付記項１に記載の方法。
【００７４】
付記項１１  最終マッチの１つまたは複数の系列を特定することは、
ａ．内座層の数で、系列の候補マッチを降順に並べ替えることと、
ｂ．クエリ画像内の候補マッチの内座層を包囲する多角形と、クエリ画像内の既存の系列の第１の要素の内座層を包囲する多角形との交差領域が、既定の閾値より大きい場合に、候補マッチを既存の系列に追加することと、
ｃ．クエリ画像内の候補マッチングの内座層を包囲する多角形とクエリ画像内の既存の系列の第１の要素の内座層を包囲する多角形との交差領域が、すべての既存の系列に対して既定の閾値を下回る場合は、候補マッチからなる新しい系列を生成することと、を含む、付記項１０に記載の方法。
【００７５】
付記項１２  動き推定は、ＲＡＮＳＡＣ手順を使用して生成された変換を使用することによって行われる、付記項１に記載の方法。
【００７６】
付記項１３  クエリ画像を複数の画像とマッチングする方法であって、画像は一組の特徴点、一組の対応する特徴方向および一組の対応する特徴ベクトルによって表され、
ａ．複数の画像の１つとクエリ画像との間で推定一致を見出すことによって複数の画像から推定一致画像を見出すことと、
ｂ．１つの推定一致画像とクエリ画像との間で推定一致のサブセットを使用して動き推定を行うことによって、また方向一致試験を推定一致のサブセット内の特徴点に対して行うことによって、候補マッチを見出すことと、を含む方法。
【００７７】
付記項１４  １つの推定一致画像と方向一致試験を実行する前のクエリ画像との間で推定一致のサブセット間の位相同型性を確認することをさらに含む、付記項１３に記載の方法。
【００７８】
付記項１５  方向一致試験を実行することは、
ａ．特徴点に対するオフセット点を一方の画像の推定一致のサブセット内で決定することであって、オフセット点は、その対応する特徴点からその特徴点の方向の向きに移動されることと、
ｂ．他方の画像で推定一致のサブセット内の特徴点に対応する第２のオフセット点を生成するためにオフセット点を変換することと、
ｃ．他方の画像で推定一致のサブセット内の特徴点とその対応する変換されたオフセット点との間の方向が既定限度だけその見積られた方向と異なる際に、変換を破棄することと、をさらに含む、付記項１３に記載の方法。
【００７９】
付記項１６  候補マッチを見出すことは、クエリ画像と見積られた動きによって得られた推定一致画像との間で推定一致のセットから一組の内座層を計算することを含む、付記項１３に記載の方法。
【００８０】
付記項１７  最終マッチの１つまたは複数の系列を候補マッチから特定することをさらに含む、付記項１３に記載の方法。
【００８１】
付記項１８  最終マッチの１つまたは複数の系列を特定することは、候補マッチに対する多くの内座層が内座層の既定数より大きく、既定の閾値より小さい近似誤差を有する際に、候補マッチを選択することを含む、付記項１７に記載の方法。
【００８２】
付記項１９  クエリ画像を複数の画像とマッチングする方法であって、画像は、一組の特徴点および一組の対応する特徴ベクトルによって表され、
ａ．複数の画像の１つとクエリ画像との間で推定一致を見出すことによって複数の画像から推定一致画像を見出すことと、
ｂ．複数の画像の１つとクエリ画像との間で推定一致のサブセットを使用して動き推定を実行することによって候補マッチを見出すことと、
ｃ．候補マッチングおよびクエリ画像の両方の内座層によって包囲される領域の百分率を測定し、２つの百分率の最大値が既定の閾値より小さい場合は、該候補を拒否することと、を含む方法。
【００８３】
付記項２０  クエリ画像を複数の画像とマッチングする方法であって、画像は一組の特徴点および一組の対応する特徴ベクトルによって表され、
ａ．複数の画像の１つとクエリ画像との間で推定一致を見出すことによって複数の画像から推定一致画像を見出すことと、
ｂ．複数の画像の１つとクエリ画像との間で推定一致のサブセットを使用して動き推定を実行することによって候補マッチを見出すことと、
ｃ．最終マッチの１つまたは複数の系列の候補マッチから特定することと、を含む方法であって、
ｉ．内座層の数によって候補マッチの系列を降順に並べ替えることと、
ｉｉ．クエリ画像内の候補マッチの内座層を包囲する多角形と、クエリ画像内の既存の系列の第１の要素の内座層を包囲する多角形との交差領域が、既定の閾値より大きい場合は、該候補マッチを既存の系列に追加することと、
ｉｉｉ．クリエ画像内の候補マッチングの内座層を包囲する多角形とクエリ画像内の既存の系列の第１の要素の内座層を包囲する多角形との交差領域が、すべての既定の系列に対する既定の閾値を下回る際に、候補マッチからなる新しい系列を生成することと、を含む方法。
【００８４】
付記項２１  クエリ画像を複数の画像とマッチングするシステムであって、画像は一組の特徴点および一組の対応する特徴ベクトルによって表される、システムであって、
ａ．特徴点の組を使用して複数の画像から推定一致画像を見出すための推定一致モジュールと、
ｂ．１つの推定一致画像とクエリ画像との間で推定一致のサブセットの位相同型性を確認するため、および推定一致のサブセットを使用して推定一致画像に対して動き推定を行うための動き推定モジュールと、
ｃ．動き推定に基づいてクエリ画像にマッチする画像の１つまたは複数の系列を特定するための最終特定モジュールと、を含むシステム。
【００８５】
付記項２２  推定一致モジュールは、ベクトル・ドット積モジュールを含み、該ベクトル・ドット積モジュールは、
ａ．推定一致を見出すために複数の画像の１つの特徴ベクトルとクエリ画像の特徴ベクトルとの間でベクトル・ドット積を計算することと、
ｂ．推定一致数が既定値より大きい場合、複数の画像から推定一致画像を選択することと、に適合される、付記項２１に記載のシステム。
【００８６】
付記項２３  動き推定モジュールは、方向一致確認モジュールを含み、該方向一致確認モジュールは、
ａ．一方の画像の推定一致のサブセット内で特徴点に対するオフセット点を決定することであって、オフセット点は、その対応する特徴点から該特徴点の方向の向きに移動されることと、
ｂ．他方の画像で推定一致のサブセット内の特徴点に対応する第２のオフセット点を生成するためにオフセット点を変換することと、
ｃ．他方の画像で推定一致のサブセット内の特徴点とそのオフセット点との間の方向が既定限度を超える際に、該変換を破棄することと、に適合される、付記項２１に記載のシステム。
【００８７】
付記項２４  動き推定モジュールは、変換を使用してクエリ画像と推定一致画像との間で推定一致の組から内座層を計算するための内座層計算モジュールをさらに含む、付記項２１に記載のシステム。
【００８８】
付記項２５  最終特定モジュールは、候補マッチの内座層の数が内座層の既定数より大きく、既定の閾値より小さい近似誤差を有する際に、１つまたは複数の画像を選択するよう適合される、付記項２１に記載のシステム。
【００８９】
付記項２６  最終特定モジュールは、候補マッチおよびクエリ画像の両方の内座層によって包囲された領域の百分率最高値が既定の閾値より小さい場合、候補マッチングを拒否する、付記項２１に記載のシステム。
【００９０】
付記項２７  動き推定モジュールは、ＲＡＮＳＡＣ手順を使用して生成された変換を使用することによって動き推定を計算する、付記項２１に記載のシステム。
【００９１】
付記項２８  複数の画像を有するクエリ画像をマッチングするためのコンピュータ・プログラム製品であって、画像は、一組の特徴点および一組の対応する特徴ベクトルによって表され、該コンピュータ・プログラム製品は、コンピュータ可読媒体に保存された命令を含み、
ａ．複数の画像の１つとクエリ画像との間で推定一致を見出すことによって複数の画像から推定一致画像を見出すことと、
ｂ．１つの推定一致画像とクエリ画像との間の推定一致のサブセット間で位相同型性を確認することと、
ｃ．１つの推定一致画像とクエリ画像との間で推定一致のサブセットを使用して動き推定を行うことによって候補マッチを見出すことと、を実行するコンピュータ・プログラム製品。
【００９２】
本発明の様々な実施形態が示され説明されたが、本発明はこれらの実施形態のみに限定されないことは明らかであろう。多くの修正形態、変更形態、変形形態、代替形態および等価形態が、特許請求の範囲に記載された本発明の精神および範囲を逸脱せずに、当業者には明らかとなるであろう。
【図１】
0005347034.tif 000004
【図２】
0005347034.tif 000005
【図３】
0005347034.tif 000006
【図４】
0005347034.tif 000007
【図５】
0005347034.tif 000008
【図６】
0005347034.tif 000009
【図７】
0005347034.tif 000010
【図８】
0005347034.tif 000011