複数画像レジストレーション装置及び方法
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法が説明される。この方法は、各画像内のディスティンクティブな特徴量を識別することと、一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、上記１つ又は複数の画像グループを求めるために、上記可能性のある一致を処理することとを含む。ディスティンクティブな特徴量を比較するときに、或る画像内のディスティンクティブな特徴量は、１つ又は複数の所定基準を満たす他の画像内のディスティンクティブな特徴量のサブセットのみと比較される。この基準は、画像の類似度、又は代替的に、関連する画像対に対してレジストレーションに関する決定が既に為されているか否かを含むことができる。このようにして、特徴量比較の回数が低減される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像セットを処理するとこによって、合成して１つのパノラマを形成することができる画像グループを識別し、画像グループに対応するパノラマデータを生成する方法に関する。
【背景技術】
【０００２】
パノラマ認識の方法については、Lowe及びBrownによって、文献「Recognising Panoramas」（the Proceedings of the 9th International Conference on Computer Vision, pp 1218-1225, Nice, France, October 2003）において考察されている。Lowe及びBrownによって採用された方法は、スケール不変特徴量の高速マッチング（ＳＩＦＴ）、ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）によるロバスト推定、バンドル調整、及びマルチバンド画像融合に基づく。具体的には、すべての特徴点（interest point）に対する画像記述子が比較された後、記述子空間における最近傍探索によって一致が識別される。次いで、確率的画像一致検証が行われる。確率的画像一致検証は、マッチングされた特徴量のセットが、正しい画像一致から生じたのか、或いは誤った画像一致から生じたのかの確率を比較する。これによって、画像間の重なり合っている領域内にあるインライア（inlier）及びアウトライア（outlier）の数に対する単純な条件がもたらされ、アルゴリズムが誤った画像一致を効率的に拒絶することが可能になる。
【０００３】
Lowe及びBrownの方法は、高次元特徴量空間を使用することによって、網羅的な特徴量マッチングの２次の複雑性（quadratic-complexity）の問題を回避する。この方法は効率的であるが、特に以下のようないくつかの欠点を有する：
画像記述子のすべてのセットを画像から抽出する必要があり、その結果、メモリ及び計算時間の消費が多大なものになる；
高次元空間（通常、上記の方法においては１２８次元）においては、高速最近傍探索が非効率になる。また、種々の近似探索方法を適用すると、頻繁に不一致が生じる。
【０００４】
したがって、特徴量マッチングの２次の複雑性を低減すると共に低次元基準のみを使用して、対応する特徴量を確立する方法を設計することが不可欠である。
【０００５】
欧州特許出願公開第１７３６９２８号は、画像レジストレーションに関する決定を行うためのクラスタベース手法の使用について考察している。第１の画像からの特徴量が反復して選択され、第２の画像の特徴量との最良の一致が計算される。これらの最良の一致に関して、その特徴点を中心とする画像領域間の局所的な回転及びスケール変換のパラメータが推定された後、回転・スケール累積器が、推定された変換パラメータに対応する成分をインクリメントすることによって更新される。次いで、回転・スケール累積器での最高のピークに寄与するすべての特徴量一致が抽出された後、ＲＡＮＳＡＣによって大域的整合性が調べられる。ＲＡＮＳＡＣのインライアの数が十分である場合、画像対はレジストレーションされたものとみなされ、繰り返しが終了する。
【０００６】
欧州特許出願公開第１７３６９２８号において考察されている方法は、いくつかの欠点を有する。特に：
− レジストレーションされないと決定される前に、一致しない画像対に対して多数の特徴量一致を計算しなければならない；
− 最初の数回の反復の後、雑音の多いクラスタが真の一致のクラスタよりも大きくなる可能性があり、雑音の多いクラスタをＲＡＮＳＡＣを用いて処理する結果として、レジストレーションに関する誤った決定が行われる可能性がある；
− 真のクラスタが正しく選択され、且つＲＡＮＳＡＣのインライアの数が多い場合であっても、正しく一致する特徴点が画像の一部にグループ化される可能性があり、その結果、レジストレーション精度が低くなる；
− 誤った一致もピークの最高値に寄与するため、累積器の最高のピークが真の一致を有するクラスタを常に示すわけではない。
【０００７】
画像セット内における画像対のレジストレーションを表現するために、グラフ構造が使用されることが多い。たとえば、D. Capel著「Image Mosaicing and Super-Resolution」（PhD thesis, Dept of Eng. Science, univ. of Oxford, 2001）、及び、Sawhney他著「Robust video mosaicing through topology inference and local to global alignment」（Proc. European Conference on Computer Vision and Image Understanding, No. 2, Vol. 93, pp 175-194, 2004）を参照されたい。画像がグラフノードによって表されており、それらの２ビュー関係（特徴量の対応、ホモグラフィ）がグラフエッジとして表されているレジストレーショングラフが採用されている。グラフの推移閉包が、画像レジストレーションアルゴリズムによって明示的に確立されていない画像関係を識別することを可能にする。たとえば、画像対（Ａ、Ｂ）がレジストレーションされ、レジストレーショングラフ内にＢとＣとの間の経路が存在する場合、ＡとＣのレジストレーション（又はレジストレーションしないことに関する決定）を、ＡとＣとの間の最適経路によって求められる一連のホモグラフィを使用して得ることができる。画像Ａと画像Ｃとが高い割合で重なり合っている場合、重なり合っている領域からの特徴量を使用する高速ホモグラフィ誘導アルゴリズムを使用してレジストレーションを行うことができる。
【０００８】
多くの従来手法において、レジストレーショングラフは、連続する画像又はビデオフレームのレジストレーション対によって初期化される。したがって、画像順序が決められていると仮定される。
【０００９】
隣接行列でグラフを表現する場合、このような初期化は主対角線の直上に位置する行列要素を満たすことに相当する。この初期化が実行されると、推移閉包の次のステップは、（既に満たされた対角線の上の）次の対角線内の要素を満たすことに相当し、このプロセスはレジストレーションされていない画像間の重なりを発見することができる間繰り返される。
【００１０】
順序付けされていない画像の場合には、グラフをレジストレーション対によって初期化することができないため、このような決定論的アルゴリズムを適用することはできない。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、それぞれが１つのパノラマに対応する画像グループを識別するために比較しなければならない画像セット内の特徴量の数を低減することである。
【課題を解決するための手段】
【００１２】
本発明の一態様によれば、複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法が提供される。この方法は、各画像内のディスティンクティブ（distinctive）な特徴量を識別することと、上記一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、１つ又は複数の画像グループを求めるために、上記可能性のある一致を処理することとを含む。或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較するときに、所定基準を満たす他の画像内のディスティンクティブな特徴量のみが考慮される。このようにして、必要な計算量が低減される。
【００１３】
好ましくは、ディスティンクティブな特徴量の特徴強度を計算し、類似の特徴強度を有する特徴量のみを比較する。画像内の各点ごとの特徴値を生成する特徴点検出器を使用して画像データを処理し、極大点を特徴点として識別し、極大点の値を正規化して特徴強度を生成することによって、特徴強度を計算することができる。好ましくは、対数正規化が行われる。
【００１４】
好ましくは、以前の特徴量比較の結果の確率的解析を反復して行い、確率的解析によって一致が統計的に起こりそうにないことが示される場合には、画像対のマッチングを拒絶することによって、特徴量比較の回数はさらに比較される。
【００１５】
推移グラフ閉包をレジストレーショングラフに対して反復して行うことによって、特徴量マッチングの回数をさらに低減することができる。このようにして、推移閉包演算によって識別される重なり合っている画像をレジストレーションすることができ、且つ／又は重なり合っていない画像を拒絶することができる。
【００１６】
ここで、本発明のさまざまな例示的な実施形態を添付の図面を参照して説明する。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施形態を概略的に表す。
【図２】図１に示す画像処理モジュールの主要構成要素を概略的に示す。
【図３】図２に示す画像処理モジュールによって実行される処理演算の概略を示すフローチャートである。
【図４】図３に示す処理演算のうちの１つである初期化サブルーチンをより詳細に示すフローチャートである。
【図５】図３において実行される処理演算のうちの１つである特徴量マッチングサブルーチンをより詳細に示すフローチャートである。
【図６】画像のサンプルセットに対する画像処理中にハフ変換累積器に記録されるデータを概略的に示す。
【図７】画像のサンプルセットに対する画像処理中に閾値累積器に記録されるデータを概略的に示す。
【図８】図３において実行される処理演算のうちの１つである、レジストレーショングラフ及び／又は確率条件を更新するサブルーチンにおける主要演算を示すフローチャートである。
【図９】図８に示すサブルーチンの一部として実行される、推移レジストレーショングラフ閉包を実行するサブルーチンにおける主要演算を示すフローチャートである。
【図１０】パノラマ認識中のレジストレーショングラフの展開を概略的に示す。
【発明を実施するための形態】
【００１８】
主実施形態
図１に示すように、この実施形態において、複数の画像１ａ〜１ｈが画像処理モジュール３内に入力される。この例示的な実施形態において、複数の画像１は８つの画像から成る順序付けされていないセット１であり、そのうちの４つから成る第１のグループはローマの円形競技場の写真であり、その他の４つから成る第２のグループは都市の屋根の光景の写真である。
【００１９】
下記で詳細に説明するように、画像処理モジュールは、パノラマビューを形成する画像グループを認識し、それらの画像をそれぞれの認識されたグループに合成する。このようにして、第１のパノラマ画像５ａがローマの円形競技場の形を形成し、第２のパノラマ画像５ｂが都市の屋根の光景の形を形成する。
【００２０】
図２は、画像処理モジュール３の主要構成要素を示す。この実施形態において、画像処理モジュール３は、バスシステム１７によって相互接続されるプロセッサ１１、入出力インタフェース１３、及びメモリ１５を有する演算装置の一部を形成する。
【００２１】
この実施形態において、入出力インタフェース１３は、データをＣＤ−ＲＯＭ１９に読み書きすることを可能にするＣＤ−ＲＯＭリーダ／ライタ（図示せず）と、データをデータ信号２１の形で入出力することを可能にするネットワークインタフェース（図示せず）とを備える。
【００２２】
プロセッサ１１は、メモリ１５内に記憶されているルーチンを使用して、メモリ１５内に記憶されているか又はインタフェース１３によって入力される画像データを処理し、パノラマデータを生成する。このパノラマデータは、メモリ１５内に記憶することができ且つ／又はインタフェース１３を介して出力することができる。
【００２３】
例示を容易にするために、図２は、複数のメモリ領域に分割されているメモリ１５を概略的に示している。図示されるように、メモリ１５は、画像領域２３と、特徴量領域２５と、累積器領域２７と、レジストレーショングラフ領域２９と、ワーキングメモリ領域３１と、ルーチン領域３３とを有する。これらのメモリ領域は、メモリの連続ブロックに対応する必要はないことは理解されよう。加えて、従来のように、メモリ１５は、処理時間を低減するために採用されている従来のデータキャッシング技法による異なるアクセス時間を有するさまざまなメモリ装置を含むことができる。
【００２４】
画像メモリ領域は、Ｎ個の画像３５ａ〜３５ｎを記憶する。各画像３５は、画像データの２次元配列を含む。それによって、画像３５はＩk（ｘ，ｙ）（ｋ＝１．．．．．Ｎ）として表される。
【００２５】
特徴量メモリ領域２５は、画像領域２３内に記憶されている画像３５内において識別される特徴点の特徴量データを記憶する。これらの特徴点は、画像３５内の画像が共通の特徴を含むか否かを判断するための比較可能でディスティンクティブな特徴量（distinctive feature）に対応する。各特徴点は対応する強度値を有する。以降でより詳細に考察されるように、この実施形態では、類似の強度値を有する特徴点は、ビン３７ａ〜３７ｎに共にグループ化される。
【００２６】
累積器メモリ領域は、ハフ変換累積器３９と、閾値累積器４１とを格納する。ハフ変換累積器３９は、画像３５の対ごとに、類似していると判定される画像対から抽出される特徴量の相対オリエンテーション及びスケールを記録する。類似の相対オリエンテーション及びスケールを有する画像対間の一致する特徴量のクラスタは、対応する画像間の重なりを示す。しかしながら、一致する特徴量の識別は処理集約的であり、そのため、この実施形態では、類似の相対オリエンテーション及びスケールを有する比較的少数の一致が識別されると、さらなる試験が行われて一致の信頼性が評価される。以降でより詳細に考察されるように、閾値累積器４１は、そのようなさらなる試験が実行されるのに先だって識別される必要のある、類似の相対オリエンテーション及びスケールを有する、信頼でき可能性のある一致する特徴量の個数を追跡する。
【００２７】
レジストレーショングラフ２９は、画像メモリ領域２３内の画像３５間の求められた一致を表すデータを記憶する。具体的には、画像対（ｋ1，ｋ2）ごとに、レジストレーショングラフ２９はレジストレーション［ｋ1，ｋ2］及び類似度［ｋ1，ｋ2］値を記憶する。レジストレーション［ｋ1，ｋ2］は３つの値をとることができる。すなわち、画像ｋ1が画像ｋ2と重なり合うことが分かっていることを示すＴＲＵＥ（真）と、画像ｋ1が画像ｋ2と重なり合わないことが分かっていることを示すＦＡＬＳＥ（偽）と、さらなる試験が必要であることを示すＵＮＤＥＦＩＮＥＤ（不明）とをとることができる。類似度［ｋ1，ｋ2］値は、画像ｋ1と画像ｋ2との類似度の質を示す数である。
【００２８】
ワーキングメモリ領域３１は、プロセッサ１１によって処理演算中の中間データを記憶するのに使用される。
【００２９】
ルーチンメモリ領域３３は、プロセッサ１１によってパノラマ認識中に使用されるルーチンを記憶する。この実施形態では、ルーチンメモリ領域は、以下のルーチンを記憶する。
− Master_Control（マスタ制御）ルーチン４３：パノラマ認識プロセスを統合する。
− Initialisation（初期化）サブルーチン４５：ハフ変換累積器３９、閾値累積器４１、及びレジストレーショングラフ２９を初期化する。
− Feature_Matching（特徴量マッチング）サブルーチン４７：反復的特徴量マッチングを実行する。
− Update_RG/PC（ＲＧ／ＰＣ更新）サブルーチン４９：画像の重なりを評価するのに使用されるレジストレーショングラフ及び／又は確率条件を更新するのに使用される。
− Evaluate_Accuracy（精度評価）サブルーチン５１：２つの画像の重なり合っている領域をリンクするホモグラフィ変換を評価及び改善するのに使用される。
− Graph_Closure（グラフ閉包）サブルーチン５３：レジストレーショングラフ２９に新たなエッジが追加されるたびに推移グラフ閉包を実行するのに使用される。
【００３０】
Master_Controlルーチン４３における主要ステップを図３に示す。図示されるように、Ｓ１においてＮ個の入力画像を受けとった後、Master_Controlルーチン４３はInitialisationサブルーチン４５をコールする。
【００３１】
図４に示されるように、Initialisationサブルーチン４５は、Ｓ３１において、画像対ごとにレジストレーショングラフ内の類似度値を−１に設定する。次いで、Initialisationサブルーチン４５は、Ｓ３５において、ハフ変換累積器のすべての要素を０に設定し、Ｓ３７において、閾値累積器のすべての要素をＮminに設定する。ここでＮminは、２つの画像間の重なりの確認を可能にするのに必要な信頼性のある特徴量一致の最小数である。Ｎminの値を計算する方法を下記でより詳細に考察する。
【００３２】
次いで、Initialisationサブルーチン４５は、Ｓ３７において、画像が自身の記録された順序を示す順序情報を含むか否かを調べる。画像が順序付けされている場合、Initialisationサブルーチン４５は、連続する画像のレジストレーションデータをＵＮＤＥＦＩＮＥＤに設定し、他のすべての画像対のレジストレーションデータをＦＡＬＳＥに設定する。これは、少なくとも最初は、連続していない画像間の重なりは調査されないことを意味する。次いでInitialisationサブルーチン４５は、Ｓ４７において終了する。
【００３３】
画像が順序付けされていない場合、Initialisationサブルーチン４５は、Ｓ４１において、画像にタイムスタンプが付されているか否か（すなわち、画像が自身の記録された時刻を含むか否か）を調べる。画像にタイムスタンプが付されている場合、Initialisationサブルーチン４５は、互いが所定時間、たとえば１０秒以内に記録された画像のレジストレーションデータをＵＮＤＥＦＩＮＥＤに設定し、他のすべての画像対のレジストレーションデータをＦＡＬＳＥに設定する。これは、少なくとも最初は、所定時間よりも離れて記録された画像間の重なりは調査されないことを意味する。次いでInitialisationサブルーチン４５は、Ｓ４７において終了する。画像３５がタイムスタンプを付されていない場合、Initialisationサブルーチンは、ステップ４５において、すべての画像対のレジストレーションデータをＵＮＤＥＦＩＮＥＤに設定し、Ｓ４７において終了する。
【００３４】
図３に戻って、Initialisationサブルーチン４５が終了すると、Master_Controlルーチンは、Ｓ５において、画像３５内の特徴点を検出する。この実施形態では、Foerstner及びGulchによる論文「A fast algorithm for detection and precise location of distinct points, corners, and circular features」（Proc. Intercommission Conference on Fast Processing of Photogrammetric Data, Interlaken (1987） pp287-305）（その全内容が参照により本明細書に援用される）に記載されているフェルスター演算子（Foerstner operator）を修正したものが使用される。具体的には、各画素の局所近傍ｎ（ｘ，ｙ）において計算される自己相関行列Ａの行列式とトレースとの比Ｒ（ｘ，ｙ）が、下記の式（１）及び式（２）に示されるように計算される。
【００３５】
【数１】
【００３６】
ここで、
【００３７】
【数２】
【００３８】
式（２）において、ガウシアンＧ（ｘ，ｙ）はウィンドウにわたって総和された導関数を重み付けするのに使用される。特徴点は、２次式をＲ（ｘ，ｙ）のマップ内の各極大点にフィッティングすることによって識別される。極大点の位置は特徴点の位置に対応し、極大点の推定値は特徴強度Ｒmを決定する。各画像内の検出された特徴点は、特徴強度の降順にソートされる。それによって、最も重要な特徴点はリストの上端に配置される。したがって、Ｒ1≧Ｒ2≧．．．≧Ｒm≧．．．≧Ｒnである。
【００３９】
特徴点の検出後、Master_Controlルーチン４３は、Ｓ７において、検出された特徴点を正規化する。この実施形態では、正規化は画像ごとに行われ、画像内の各特徴点ｍの正規化された特徴強度は下記の式（３）によって与えられる。
【００４０】
【数３】
【００４１】
これによって、０〜１の区間内で変化する正規化コーナー強度（normalised corner strength）の範囲が与えられる。次いで、すべての画像からの特徴量が、それらの特徴強度にしたがってビン３７内にソートされる。具体的には、この実施形態では、各ビン３７は区間０〜１の区別可能なパーセンタイル値に対応し、ビン１は０．００〜０．０１をカバーし、ビン２は０．０１〜０．０２をカバーし、ビン１００が範囲０．９９〜１．００をカバーするまで以下同様である。各特徴量ｆは特徴強度の順にすべての画像にわたる大域インデックスｉを付される、そして、特徴量ｆiは以下の情報を記憶する。
【００４２】
【数４】
【００４３】
ここで、ｋiは特徴量が現れる画像を識別し、ｍiはその画像内における特徴量のインデックス番号を識別し、（ｘi，ｙi）は特徴量の画像ｋi内における位置であり、ｄiは比較目的で使用される特徴量記述子である。この実施形態では、特徴量記述子ｄiは、以下の式にしたがって、特徴点を中心とする局所画像領域内における画素値の対数極変換（ＬＰＴ）によって形成される。
【００４４】
【数５】
【００４５】
特徴点を正規化及びソートする理由は、一般に、特徴量が、当該特徴量が現れる種々の画像内において類似のディスティンクティブネス（distinctiveness）を有するためである。しかしながら、特徴強度は倍数的な強度変化に対して不変ではない。したがって、倍数因子を除去するために正規化を行う。
【００４６】
特徴点が正規化及びソートされた後、Master_Controlルーチン４３はFeature_Matchingサブルーチン４７をコールする。
【００４７】
図５に示すように、Feature_Matchingサブルーチン４７は、Ｓ６１において、次に評価される特徴点を選択する。次に評価される特徴点は、対象特徴量（subject feature）と呼ばれることになる。この実施形態では、特徴点は特徴強度の降順に調査される（すなわち、最もディスティンクティブな特徴量が最初に識別される）。したがって、対象特徴量は、まだ評価されていない最高の特徴強度を有する特徴点である。
【００４８】
次いで、Feature_Matchingサブルーチン４７は、Ｓ６３において、対象特徴量が出現する画像に関連して現在レジストレーションされていない（すなわち、２つの画像間のレジストレーションデータがＵＮＤＥＦＩＮＥＤである）他の画像内に出現する、類似の正規化特徴強度を有する複数の特徴量を識別する。具体的には、この実施形態では、対象特徴量の正規化特徴強度の０．１５以内である正規化特徴強度を有する特徴量のみを調査する。換言すれば、対象特徴量の正規化特徴強度の０．１５以内である正規化特徴強度に対応するビン内の特徴量のみを調査する。
【００４９】
対象特徴量の画像に関連してまだレジストレーションされていない他の画像内にある類似の正規化特徴強度を有する複数の特徴量が識別されると、Feature_Matchingサブルーチン４７は、Ｓ６３において、対象特徴量と識別された複数の特徴量との間で最も良く一致するものを見つける。これは、対象特徴量ｆiの記述子ｄiと、識別された複数の特徴量の各記述子とを比較することを含む。類似度は、数値ν、画像領域間の局所的な相対オリエンテーション係数θ及びスケール係数Ｓによって特性化される。
【００５０】
上記で考察したように、各特徴点の記述子ｄiはＬＰＴ変換を使用して生成される。このようにして、軸を中心とするスケーリング及びオリエンテーションは（θ，ｓ）座標におけるシフトによって表される。したがって、２Ｄマッチングの方法を使用することによって、特徴点を中心とする画像領域間の類似度値、局所的な回転、及びスケールが得られる。この実施形態では、はじめに、高速ではあるが信頼性の劣る１Ｄマッチングアルゴリズムを対数極画像の射影に対して適用して、類似していない特徴量対をフィルタリング除去する。続いて、正規化相関又は位相相関２Ｄマッチングアルゴリズムを適用する。
【００５１】
最も良く一致するものが求められると、Feature_Matchingサブルーチン４７は、Ｓ６７において、オリエンテーションパラメータ及びスケールパラメータを整数座標に変換し、ハフ変換累積器３９及び閾値累積器４１を更新する。上記で考察したように、ハフ変換累積器３９は、類似のオリエンテーション値及びスケール値を有する一致の数を追跡する。これは、通常、２つの画像間の真の一致は類似のオリエンテーション値及びスケール値を有し、一方で偽の一致は回転−スケール領域内に均一に分布しているためである。整数座標［ｐ，ｑ］が、（θ，ｌｏｇＳ）領域内に以下のように導入される。
【００５２】
【数６】
【００５３】
ここでｓ＝ｌｏｇＳであり、ｓ0は最小スケール係数の対数であり、Δｓは対数スケール軸の離散的な間隔である。
【００５４】
この実施形態では、別個のハフ変換累積器が各画像対に使用され、Ｎ個の画像に対してＮ（Ｎ−１）／２個のハフ変換累積器が存在することになる。画像ｋi及び画像ｋj（ｋi＞ｋj）内にある特徴点間の一致のためのハフ変換累積器は、Ａij［ｐ，ｑ］によって表される。各ハフ変換累積器は整数の２Ｄ配列である。対象特徴量に関して、最も良く一致すると識別された特徴量がそれぞれ［ｐ，ｑ］座標内にマッピングされ、対象特徴量の画像と、それに最も良く一致する画像とを結びつけるハフ変換器内における対応する［ｐ，ｑ］値が１だけ加算される。
【００５５】
図６は、例示を容易にするために、画像１のうちの４つのみに対して適用したこの投票手法を示す。具体的には、ローマの円形競技場の重なり合っているビューを示す画像１ｅ及び１ｇ、並びに、都市の屋根の光景の重なり合っているビューを示す画像１ｄ及び１ｈに対して適用したこの投票手法を示す。累積器Ａ21が画像１ｈ及び１ｇの対に関連付けられ、累積器Ａ31が画像１ｅ及び１ｇの対に関連付けられ、累積器Ａ41が画像１ｄ及び１ｇの対に関連付けられ、累積器Ａ32が画像１ｅ及び１ｈの対に関連付けられ、累積器Ａ42が画像１ｄ及び１ｈの対に関連付けられ、累積器Ａ43が画像１ｄ及び１ｅの対に関連付けられている。
【００５６】
図６では、各画像からの特徴点のほぼ１０％が処理されている。同じ［ｐ，ｑ］値を有する多数の一致する特徴量を示す大きなピークが累積器Ａ31及びＡ42内に存在している。これは、これらの累積器が重なり合う画像対に関連付けられていることを予想させる。他の累積器内にある小さな雑音の多いピークは、対応する画像対が異なるシーケンスに属し、幾何学的に位置合わせすることができないことを示す。
【００５７】
ハフ変換累積器における特徴量一致の分布は、いずれの画像が重なり合っているかを示すが、幾何学的に整合している一致の数は、ハフ変換累積器におけるピークの高さよりもディスティンクティブな真のクラスタの指標である。これは、通常、ハフ変換累積器におけるピークが多数の誤った一致を含むためである。エラーを低減するために、これらの誤った一致は画像変換を計算する前に除去されるべきである。誤った一致は、ＲＡＮＳＡＣ推定器を適用することによって除去することができる。ＲＡＮＳＡＣ推定器は、画像間のホモグラフィを有する幾何学的に整合している一致する特徴量対（インライア（inlier）と呼ばれる）と、幾何学的に整合していない一致する特徴量対（アウトライア（outlier）と呼ばれる）とを識別する。この実施形態では、下記でより詳細に説明するように、画像が重なり合っているか否かを判断するときにインライアとアウトライアの割合を使用する。
【００５８】
図７に示すように、閾値累積器４１は、ハフ変換累積器３９と同様に、各画像対の［ｐ，ｑ］空間における２Ｄ累積器を含む。上記で考察したように、閾値累積器４１内にあるすべての要素は初期状態ではＮminに設定されている。そして、最も良く一致すると識別された特徴量がそれぞれ［ｐ，ｑ］座標内にマッピングされ、対象特徴量の画像と、それに最も良く一致する画像とを結びつける閾値累積器内における対応する［ｐ，ｑ］値が１だけ減算される。
【００５９】
図３に戻って、対象特徴量の特徴量マッチングを行った後、Master_Controlルーチン４３は、Ｓ１１において、閾値累積器４１の任意の要素がゼロに達したか否かを調べる。達していない場合、Master_Controlルーチン４３は、次の画像特徴量に対して特徴量マッチングを行う。一方、閾値累積器４１の或る要素がゼロに達している場合、Master_Controlルーチンは、Ｓ９において、インライア及び最良の変換を識別するＲＡＮＳＡＣを実行する。具体的には、ＲＡＮＳＡＣは、ハフ変換累積器３９におけるピークに対応する特徴量一致を処理することによって、重なり合っている領域、及び、その重なり合っている領域内における特徴点中のインライアの数を、推定されるホモグラフィに基づいて求める。次いで、ホモグラフィパラメータがすべてのインライアから再推定される。次いで、新しいより正確なホモグラフィパラメータと、隣接するハフ変換累積器要素からの特徴量一致を使用して、拡張されたインライアセットが求められる。このプロセスはインライアの数が安定するか、又は一定回数の反復が行われるまで繰り返される。
【００６０】
次いで、Master_Controlルーチン４３は、Ｓ１５において、ＲＡＮＳＡＣ処理の結果を解析するUpdate_RG/PCサブルーチン４９を実行する。これより、図８を参照してUpdate_RG/PCサブルーチンをより詳細に考察する。
【００６１】
Update_RG/PCサブルーチン４９は、Ｓ７１において、ＲＡＮＳＡＣ処理の結果を受け取った後、Ｓ７３において、画像マッチングの確率閾値が満たされているか否かを調べる。確率閾値はベイズルールに基づき、これによって、画像一致が正しい確率を、インライアの数Ｎ(i)及びアウトライアの数Ｎ(o)から求めることが可能となる。インライアの総数は２項分布を有するものと仮定すると、正しい画像一致の事後確率は、ベイズルールを使用して以下のように推定される。
【００６２】
【数７】
【００６３】
ここで、Ｐ（ｘ｜ｙ）はｙが与えられた場合にｘがＴＲＵＥである確率である。
【００６４】
Ｐ（正しい一致｜Ｎ(i)）がＰminよりも大きいときに画像一致を受け入れる結果として、条件は以下のようになる。
【００６５】
【数８】
【００６６】
ここで、α及びβの数値は、特徴量一致が正しい画像一致に対してインライアである確率、特徴量一致が正しい画像一致に対してアウトライアである確率、Ｐmin、及びＰ（正しい一致）を設定することによって得られる。したがって、Update_RG/PCサブルーチン４９は、式（９）において指定されている条件が満たされるか否かを調べる。
【００６７】
インライアの数が確率閾値を満たさない場合、Update_RG/PCサブルーチン４９は、Ｓ７５において、確率条件を更新すると共に、調査中の閾値累積器４１の要素［ｐ，ｑ］に新たな値を入力する。式（９）から、画像一致を確立するのに必要な最小数Ｎminは、アウトライアの数がゼロである場合に現れ、以下の式によって与えられることが分かる。
【００６８】
【数９】
【００６９】
ここで、［．．．］は実数の整数部分である。Ｎminは、上記で考察したように閾値累積器４１の要素に入力される初期値である。したがって、閾値累積器４１の要素が画像一致を示す最小数の特徴量を含むようになるまで、さらなる試験は行われない。
【００７０】
ＲＡＮＳＡＣ処理において識別されるインライアの数Ｎ(i)とアウトライアの数Ｎ(o)との間の関係が式（９）を満たさない場合、Update_RG/PCサブルーチン４９は、Ｓ７５において、満たされるべき確率条件をＲＡＮＳＡＣ処理が再び行われる前に更新する。これは、画像一致の可能性を示すのに必要な追加の特徴量一致の最小数Ｎmin’が、以下の式（１１）を満たさなければならないという事実に基づく。
【００７１】
【数１０】
【００７２】
これは、以下を意味する。
【００７３】
【数１１】
【００７４】
次いで、調査中の特徴量一致のクラスタに対応する、閾値累積器４１の［ｐ，ｑ］要素の値をＮmin’に設定する。これによって、最小数の追加の特徴量一致が［ｐ，ｑ］要素に追加されて式（９）を満たすことが可能になるまで、これらの特徴量一致のＲＡＮＳＡＣ処理は再び行われない。
【００７５】
式（１２）から、アウトライアの数Ｎ(0)が大きくなるほどＮmin’の値も大きくなることが理解されよう。これを前提とすると、Ｎmin’の値が、式（９）が常に満たされる可能性が統計的に低い値に達する可能性がある。具体的には、各ハフ変換累積器の要素［ｐ，ｑ］の増大速度の推定値は、累積器Ａ(i,j)［ｐ，ｑ］内の一致の数と、現在の画像内でこれまで処理されている特徴量ｍiの数との比によって与えられる。したがって、閾値累積器Ｔ(i,j)の次の要素がゼロに達する前に比較する必要がある特徴量の数を、以下の式によって推定することができる。
【００７６】
【数１２】
【００７７】
画像ｋiにおいて処理されていない特徴量の数が式（１３）によって求められる最小数ΔＮ(i,j)を下回る場合、画像対ｋi，ｋjがレジストレーションされる可能性は統計的に低い。したがって、これが起こるとき、レジストレーション［ｋi，ｋj］はＦＡＬＳＥに設定される。これによって、画像ｋiからの特徴量を画像ｋjからの特徴量とそれ以上比較することが回避される。
【００７８】
図７において、各画像からの約１０％の特徴量が処理されている。累積器Ｔ31内にある要素、及び累積器Ｔ42内にある要素は既にゼロに達しており、これは、画像対（３，１）及び（４，２）は、一致する可能性があることを示している。累積器Ｔ32内に位置する別の要素がゼロに近づいており、これは、対応する特徴量一致のクラスタが、次の数回の反復の後にＲＡＮＳＡＣを使用して処理される可能性があることを示している。この要素がゼロに達すると、ＲＡＮＳＡＣ処理は、ごく少数のインライア及び多数のアウトライアを発見することになる。その結果、その要素に大きな修正閾値がもたらされる。これは、画像３及び２は同じパノラマの一部を形成していないため、期待される結果である。
【００７９】
ＲＡＮＳＡＣ処理において識別されたインライアの数が式（９）によって規定される確率条件を満たす場合、Update_RG/PCサブルーチン４９は、Ｓ７７において、Evaluate_Accuracyサブルーチン５１を実行する。
【００８０】
Evaluate_Accuracyサブルーチン５１は、２つの画像ｋi，ｋjにおける重なり合っている領域の相関解析を行うことによって２つの画像のCurrent_Similarity（現在の類似度）値を計算し、画像ｋiと画像ｋjとの間の最良のホモグラフィを計算する。計算されたCurrent_Similarity値が類似度［ｋi，ｋj］の値よりも大きい場合、類似度［ｋi，ｋj］の値は計算されたCurrent_Similarity値に設定される。Current_Similarity値が所定閾値を上回る場合、レジストレーション［ｋi，ｋj］の値がＴＲＵＥに設定される。これによって画像ｋi及びｋjからの特徴量をそれ以上比較することが回避される。
【００８１】
図８に戻って、Update_RG/PCサブルーチン４９は、Ｓ８１において、Graph_Closureサブルーチン５３を実行する。一般に、Graph_Closureサブルーチン５３は、画像ｋi及びｋjの新たなレジストレーション情報を、任意の他の画像対のレジストレーション情報の改善に使用することができるか否かを調べる。これより、これについて図９を参照してより詳細に説明する。
【００８２】
図９に示すように、Graph_Closureサブルーチンは、いかなる時点においても、調査中である画像ｋk及びｋl（ｌ＞ｋ）の画像対間を反復する。最初に、Ｓ９１においてｋの値が１に設定され、Ｓ９３においてｌの値がｋ＋１に設定される。次いで、Graph_Closureサブルーチン５３は、Ｓ９５において、画像ｋkから画像ｋlへの経路が存在する否かを判断する。経路が存在しない場合、Ｓ９５においてｌがｌ＋１に設定された後、経路が存在するか否かが再び調べられる。経路が存在する場合、画像ｋkと画像ｋlとの間の最短経路に基づいてホモグラフィＨklが計算される。
【００８３】
２つの画像間の最短経路は必ずしも最小数の画像を通る経路ではない。より正確なホモグラフィを有するより長い経路が、正確さの劣るホモグラフィを有するより短い経路よりも好ましい場合がある。グラフ理論において、最短経路問題は、構成エッジの重みの総和が最小になるような、２つの頂点間の最短経路を求めることである。この実施形態では、重み（１−類似度［ｋi，ｋj］）が画像ｋiと画像ｋjとを連結するエッジに適用される。この重みは、画像レジストレーションの精度を考慮に入れる。ただし、重なり合っている領域又はインライアの数は、これらの因子は双方とも良好なレジストレーションにとって重要ではないため、考慮に入れない。
【００８４】
ホモグラフィＨklを計算した後、Ｓ１０５において、画像ｌの境界が画像ｋ上に射影されて、重なり合っている領域が計算される。重なり合っている領域が存在しない場合、Graph_Closureサブルーチンは、Ｓ１０５において、レジストレーション［ｋ，ｌ］をＦＡＬＳＥに設定する。これによって、画像ｋk内の特徴量と画像ｋl内の特徴量とをそれ以上比較することが回避される。重なり合っている領域が存在する場合、Graph_Closureサブルーチンは、Ｓ１０７において、Evaluate_Accuracyサブルーチン５１を実行して、類似度［ｋ，ｌ］及びホモグラフィ［ｋ，ｌ］の最良の値を最適化及び記憶する。類似度［ｋ，ｌ］の値が所定閾値を超える場合、レジストレーション［ｋ，ｌ］をＴＲＵＥに設定し、画像ｋk内の特徴量と画像ｋl内の特徴量とをそれ以上比較することを回避する。
【００８５】
次いで、Graph_Closureサブルーチン５３は、Ｓ１０９において、ｌの値がＮ（画像の総数）に等しいか否かを調べる。等しくない場合、Ｓ９７においてｌの値に１が加算された後、経路の存在が再び調べられる。ｌがＮに等しい場合、Graph_Closureサブルーチン５３は、Ｓ１１１において、ｋがＮ−１に等しいか否かを調べる。等しくない場合、Ｓ１１３においてｋの値に１が加算された後、Ｓ９３においてｌの値がｋ＋１に設定され、経路の存在が再び調べられる。ｋがＮ−１に等しい場合、Graph_Closureサブルーチン５３は、Ｓ１１５において終了する。
【００８６】
図１０Ａ〜図１０Ｄは、レジストレーショングラフが展開する様態を示す。図１０Ａにおいて、約４％の特徴量が処理されており、画像対（３，１）、（４，２）、及び（８，４）がレジストレーションされている（レジストレーショングラフの対応するノード間の実線で示す）。加えて、画像対（２，８）の間に画像４を介する経路が存在し、画像８及び画像４と画像４及び画像２との間の変換に基づいて、画像８と２との間の重なりが識別されている。
【００８７】
図１０Ｂにおいて、約１１％の画像特徴量が処理されており、画像対（５，１）がレジストレーションされている。加えて、画像対（５，１）間に経路が存在しているが、重なりは計算されていない。図１０Ｃにおいて、約４０％の特徴量が処理されており、画像対（７，５）がレジストレーションされている。加えて、画像７と画像１との間、及び画像７と画像３との間に経路が存在しているが、重なりは計算されていない。最後に、図１０Ｄにおいて、約４２％の特徴量が処理されており、画像対（６，４）がレジストレーションされている。加えて、画像対（８，６）間に経路が存在し、重なりが計算されている。また、画像対（６，２）間に経路が存在するが、重なりは計算されていない。
【００８８】
図３に戻って、レジストレーショングラフ及び確率条件の更新後、Master_Controlルーチン４３は、Ｓ１７において、すべての画像対が処理されているか否かを調べる。処理されていない場合、上述のような特徴量マッチングが次の特徴量に対して行われ、このプロセスはすべての画像対がレジストレーションされるまで繰り返される。すべての画像対がレジストレーションされると、接続された画像のグループがレジストレーショングラフから識別され、各グループ内の画像が共に融合されて１組のパノラマである出力が形成される。
【００８９】
変更形態及びさらなる実施形態
主実施形態においては、本発明は、画像の順序付けされていないセットからパノラマを形成するのに使用されている。ディジタルカメラのプロ及びアマチュアのユーザは同じシーンの複数のショットを撮影することが多いため、これはディジタル写真には有用である。これはたとえば、１）同じシーンのパノラマ的なシーケンス、２）フレーム内の最良の構図を発見しようとする複数回の試行、３）最良のカメラパラメータ（シャッタスピード、開口）を求めようとする複数回の試行、４）ディジタルカメラのバーストモード（カメラパラメータのできるだけの変更を伴って短い時間間隔で画像が撮影される）からの画像、５）異なる被写体に合焦した複数のショット、６）フラッシュをたく／たかない複数のショット、７）同じビュー内の異なる複数の人物の複数のショット、を含むことができる。したがって、同じシーンの複数のショットはユーザにとって特別な意味を有し、或るさらなる処理が望ましい場合がある（たとえば、パノラマ的なシーケンスに対してパノラマを作成すること、最良の構図／露出を有するショットを選択すること、最良のポートレートを選択すること等）。
【００９０】
本発明を、同じビューのショットから成るすべてのグループの高速抽出に使用することができる。パノラマ生成に関しては画像合成を自動化することができるが、他の用途においては合成画像は所望の結果ではなく、単に同じビューに関連する画像グループを識別することが所望の結果であることが理解されよう。本発明を写真処理ソフトウェアとして実施することは、ユーザが、そうでなければさらなる注意を必要とする手作業になる画像の作業を自動化するのに役立つ。一実施形態では、写真処理ソフトウェアをディジタルカメラ内に実装することができる。
【００９１】
本発明の別の応用形態は、空中／衛星偵察である。通常、空中偵察及び衛星偵察のセンサは、或るルートに沿って連続的に画像を収集する。これらの画像は順序付けされている。異なるルート又は軌道から撮影された画像をレジストレーションするときに問題が発生する。通常、航空機／衛星の位置に関する情報が、異なる飛跡からの重なり合っている画像を識別するのに役立つ。本発明によって、１つの飛跡に沿った複数の画像（along-track images）、及び、異なる飛跡間の複数の画像（between-track images）のレジストレーションの双方の問題を大幅に単純化することができる。本発明は、飛跡に沿った自然な画像の順序付けに関する情報、及び、飛跡自体の時間又は位置に基づく順序付けに関する情報をレジストレーショングラフ内に均一に組み込む。
【００９２】
本発明のさらなる応用形態は、マルチプロジェクタディスプレイにおけるものである。いくつかの大型マルチメディアディスプレイは、複数のプロジェクタを使用して同じシーンの異なる複数の部分を視覚化することができる。本発明は、複数のプロジェクタからの出力を、投影画像の自動レジストレーションによって同期させるのを支援することができる。この方法の順序付けされていない入力によって、異なるレイアウトのプロジェクタを使用することが可能となる。これによって、精密な手作業の処理又は半自動処理を行うことなくプロジェクタを柔軟に位置決めすることが可能となる。
【００９３】
主実施形態においては、修正されたフェルスター演算子が特徴点の識別に使用されている。特徴点を識別する他のアルゴリズム、例えばモラベック演算子又はハンナ演算子を使用することもできることが理解されよう。主実施形態において、特徴強度が対数関数を使用して０〜１の範囲に正規化されている。（Ｒm−Ｒn）／（Ｒ1−Ｒn）のような他の関数を使用することもできることが理解されよう。加えて、特徴強度を範囲０〜１にわたって正規化するのではなく、任意の範囲にスケーリングすることもできる。
【００９４】
主実施形態においては対数極記述子ｄiが使用されているが、正規化画像パッチ（normalised image patch）又はＳＩＦＴ記述子のような他の種類の記述子を使用することもできる。
【００９５】
主実施形態は、主に４つの技法、すなわち、
１）特徴量マッチングを類似の特徴強度を有する特徴量に限定すること
２）関連しない特徴量対を反復ベースの確率的手法を使用して拒絶すること
３）重なり合っている画像をレジストレーショングラフの反復ベースの推移閉包を使用してレジストレーションすること
４）重なり合っていない画像をレジストレーショングラフの推移閉包を使用して拒絶すること
を使用して必要な特徴量マッチングの演算数を低減する。
【００９６】
これら４つの方式をすべて使用すると最良の結果が得られるが、いくらかの利益を得るためにこれら４つの方式のすべてを使用する必要はないことは理解されよう。代替的な実施形態では、方式１）と２）、又は、方式１）と３）、又は、方式１）と３）と４）を使用することができる。
【００９７】
図面を参照して説明された実施形態は、コンピュータ装置を含む。また、コンピュータ装置において実行されるプロセスを含む。本発明は、コンピュータプログラム、特に本発明を実行に移すようになっている、キャリア上又はキャリア内のコンピュータプログラムにも及ぶ。プログラムはソースコード、オブジェクトコード、部分的にコンパイルされた形態のようなソースコードとオブジェクトコードとの中間のコード、又は本発明によるプロセスの実装において使用するのに適切な任意の他の形態とすることができる。
【００９８】
キャリアは、プログラムを保持することが可能な任意のエンティティ又は装置とすることができる。たとえば、キャリアは、ＲＯＭ、たとえばＣＤ−ＲＯＭ若しくは半導体ＲＯＭ、又は磁気記録媒体、たとえばフロッピー（登録商標）ディスク若しくはハードディスク、又は光記録媒体のような記憶媒体を含むことができる。さらに、キャリアは、電気ケーブル若しくは光ケーブルを介して、又は無線若しくは他の手段によって搬送することができる電気信号又は光信号のような伝送可能キャリアとすることもできる。
【００９９】
キャリアは、プログラムが組み込まれる集積回路とすることができ、当該集積回路は、関連するプロセスを実行するか、又は関連するプロセスの実行に使用されるようになっている。
【０１００】
説明された実施形態において、本発明はソフトウェアによって実施されているが、代替的に、本発明をハードウェア装置、又はハードウェア装置とソフトウェアとの組み合わせによって実施することもできることは理解されよう。
【技術分野】
【０００１】
本発明は、画像セットを処理するとこによって、合成して１つのパノラマを形成することができる画像グループを識別し、画像グループに対応するパノラマデータを生成する方法に関する。
【背景技術】
【０００２】
パノラマ認識の方法については、Lowe及びBrownによって、文献「Recognising Panoramas」（the Proceedings of the 9th International Conference on Computer Vision, pp 1218-1225, Nice, France, October 2003）において考察されている。Lowe及びBrownによって採用された方法は、スケール不変特徴量の高速マッチング（ＳＩＦＴ）、ランダムサンプルコンセンサス（ＲＡＮＳＡＣ）によるロバスト推定、バンドル調整、及びマルチバンド画像融合に基づく。具体的には、すべての特徴点（interest point）に対する画像記述子が比較された後、記述子空間における最近傍探索によって一致が識別される。次いで、確率的画像一致検証が行われる。確率的画像一致検証は、マッチングされた特徴量のセットが、正しい画像一致から生じたのか、或いは誤った画像一致から生じたのかの確率を比較する。これによって、画像間の重なり合っている領域内にあるインライア（inlier）及びアウトライア（outlier）の数に対する単純な条件がもたらされ、アルゴリズムが誤った画像一致を効率的に拒絶することが可能になる。
【０００３】
Lowe及びBrownの方法は、高次元特徴量空間を使用することによって、網羅的な特徴量マッチングの２次の複雑性（quadratic-complexity）の問題を回避する。この方法は効率的であるが、特に以下のようないくつかの欠点を有する：
画像記述子のすべてのセットを画像から抽出する必要があり、その結果、メモリ及び計算時間の消費が多大なものになる；
高次元空間（通常、上記の方法においては１２８次元）においては、高速最近傍探索が非効率になる。また、種々の近似探索方法を適用すると、頻繁に不一致が生じる。
【０００４】
したがって、特徴量マッチングの２次の複雑性を低減すると共に低次元基準のみを使用して、対応する特徴量を確立する方法を設計することが不可欠である。
【０００５】
欧州特許出願公開第１７３６９２８号は、画像レジストレーションに関する決定を行うためのクラスタベース手法の使用について考察している。第１の画像からの特徴量が反復して選択され、第２の画像の特徴量との最良の一致が計算される。これらの最良の一致に関して、その特徴点を中心とする画像領域間の局所的な回転及びスケール変換のパラメータが推定された後、回転・スケール累積器が、推定された変換パラメータに対応する成分をインクリメントすることによって更新される。次いで、回転・スケール累積器での最高のピークに寄与するすべての特徴量一致が抽出された後、ＲＡＮＳＡＣによって大域的整合性が調べられる。ＲＡＮＳＡＣのインライアの数が十分である場合、画像対はレジストレーションされたものとみなされ、繰り返しが終了する。
【０００６】
欧州特許出願公開第１７３６９２８号において考察されている方法は、いくつかの欠点を有する。特に：
− レジストレーションされないと決定される前に、一致しない画像対に対して多数の特徴量一致を計算しなければならない；
− 最初の数回の反復の後、雑音の多いクラスタが真の一致のクラスタよりも大きくなる可能性があり、雑音の多いクラスタをＲＡＮＳＡＣを用いて処理する結果として、レジストレーションに関する誤った決定が行われる可能性がある；
− 真のクラスタが正しく選択され、且つＲＡＮＳＡＣのインライアの数が多い場合であっても、正しく一致する特徴点が画像の一部にグループ化される可能性があり、その結果、レジストレーション精度が低くなる；
− 誤った一致もピークの最高値に寄与するため、累積器の最高のピークが真の一致を有するクラスタを常に示すわけではない。
【０００７】
画像セット内における画像対のレジストレーションを表現するために、グラフ構造が使用されることが多い。たとえば、D. Capel著「Image Mosaicing and Super-Resolution」（PhD thesis, Dept of Eng. Science, univ. of Oxford, 2001）、及び、Sawhney他著「Robust video mosaicing through topology inference and local to global alignment」（Proc. European Conference on Computer Vision and Image Understanding, No. 2, Vol. 93, pp 175-194, 2004）を参照されたい。画像がグラフノードによって表されており、それらの２ビュー関係（特徴量の対応、ホモグラフィ）がグラフエッジとして表されているレジストレーショングラフが採用されている。グラフの推移閉包が、画像レジストレーションアルゴリズムによって明示的に確立されていない画像関係を識別することを可能にする。たとえば、画像対（Ａ、Ｂ）がレジストレーションされ、レジストレーショングラフ内にＢとＣとの間の経路が存在する場合、ＡとＣのレジストレーション（又はレジストレーションしないことに関する決定）を、ＡとＣとの間の最適経路によって求められる一連のホモグラフィを使用して得ることができる。画像Ａと画像Ｃとが高い割合で重なり合っている場合、重なり合っている領域からの特徴量を使用する高速ホモグラフィ誘導アルゴリズムを使用してレジストレーションを行うことができる。
【０００８】
多くの従来手法において、レジストレーショングラフは、連続する画像又はビデオフレームのレジストレーション対によって初期化される。したがって、画像順序が決められていると仮定される。
【０００９】
隣接行列でグラフを表現する場合、このような初期化は主対角線の直上に位置する行列要素を満たすことに相当する。この初期化が実行されると、推移閉包の次のステップは、（既に満たされた対角線の上の）次の対角線内の要素を満たすことに相当し、このプロセスはレジストレーションされていない画像間の重なりを発見することができる間繰り返される。
【００１０】
順序付けされていない画像の場合には、グラフをレジストレーション対によって初期化することができないため、このような決定論的アルゴリズムを適用することはできない。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、それぞれが１つのパノラマに対応する画像グループを識別するために比較しなければならない画像セット内の特徴量の数を低減することである。
【課題を解決するための手段】
【００１２】
本発明の一態様によれば、複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法が提供される。この方法は、各画像内のディスティンクティブ（distinctive）な特徴量を識別することと、上記一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、１つ又は複数の画像グループを求めるために、上記可能性のある一致を処理することとを含む。或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較するときに、所定基準を満たす他の画像内のディスティンクティブな特徴量のみが考慮される。このようにして、必要な計算量が低減される。
【００１３】
好ましくは、ディスティンクティブな特徴量の特徴強度を計算し、類似の特徴強度を有する特徴量のみを比較する。画像内の各点ごとの特徴値を生成する特徴点検出器を使用して画像データを処理し、極大点を特徴点として識別し、極大点の値を正規化して特徴強度を生成することによって、特徴強度を計算することができる。好ましくは、対数正規化が行われる。
【００１４】
好ましくは、以前の特徴量比較の結果の確率的解析を反復して行い、確率的解析によって一致が統計的に起こりそうにないことが示される場合には、画像対のマッチングを拒絶することによって、特徴量比較の回数はさらに比較される。
【００１５】
推移グラフ閉包をレジストレーショングラフに対して反復して行うことによって、特徴量マッチングの回数をさらに低減することができる。このようにして、推移閉包演算によって識別される重なり合っている画像をレジストレーションすることができ、且つ／又は重なり合っていない画像を拒絶することができる。
【００１６】
ここで、本発明のさまざまな例示的な実施形態を添付の図面を参照して説明する。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施形態を概略的に表す。
【図２】図１に示す画像処理モジュールの主要構成要素を概略的に示す。
【図３】図２に示す画像処理モジュールによって実行される処理演算の概略を示すフローチャートである。
【図４】図３に示す処理演算のうちの１つである初期化サブルーチンをより詳細に示すフローチャートである。
【図５】図３において実行される処理演算のうちの１つである特徴量マッチングサブルーチンをより詳細に示すフローチャートである。
【図６】画像のサンプルセットに対する画像処理中にハフ変換累積器に記録されるデータを概略的に示す。
【図７】画像のサンプルセットに対する画像処理中に閾値累積器に記録されるデータを概略的に示す。
【図８】図３において実行される処理演算のうちの１つである、レジストレーショングラフ及び／又は確率条件を更新するサブルーチンにおける主要演算を示すフローチャートである。
【図９】図８に示すサブルーチンの一部として実行される、推移レジストレーショングラフ閉包を実行するサブルーチンにおける主要演算を示すフローチャートである。
【図１０】パノラマ認識中のレジストレーショングラフの展開を概略的に示す。
【発明を実施するための形態】
【００１８】
主実施形態
図１に示すように、この実施形態において、複数の画像１ａ〜１ｈが画像処理モジュール３内に入力される。この例示的な実施形態において、複数の画像１は８つの画像から成る順序付けされていないセット１であり、そのうちの４つから成る第１のグループはローマの円形競技場の写真であり、その他の４つから成る第２のグループは都市の屋根の光景の写真である。
【００１９】
下記で詳細に説明するように、画像処理モジュールは、パノラマビューを形成する画像グループを認識し、それらの画像をそれぞれの認識されたグループに合成する。このようにして、第１のパノラマ画像５ａがローマの円形競技場の形を形成し、第２のパノラマ画像５ｂが都市の屋根の光景の形を形成する。
【００２０】
図２は、画像処理モジュール３の主要構成要素を示す。この実施形態において、画像処理モジュール３は、バスシステム１７によって相互接続されるプロセッサ１１、入出力インタフェース１３、及びメモリ１５を有する演算装置の一部を形成する。
【００２１】
この実施形態において、入出力インタフェース１３は、データをＣＤ−ＲＯＭ１９に読み書きすることを可能にするＣＤ−ＲＯＭリーダ／ライタ（図示せず）と、データをデータ信号２１の形で入出力することを可能にするネットワークインタフェース（図示せず）とを備える。
【００２２】
プロセッサ１１は、メモリ１５内に記憶されているルーチンを使用して、メモリ１５内に記憶されているか又はインタフェース１３によって入力される画像データを処理し、パノラマデータを生成する。このパノラマデータは、メモリ１５内に記憶することができ且つ／又はインタフェース１３を介して出力することができる。
【００２３】
例示を容易にするために、図２は、複数のメモリ領域に分割されているメモリ１５を概略的に示している。図示されるように、メモリ１５は、画像領域２３と、特徴量領域２５と、累積器領域２７と、レジストレーショングラフ領域２９と、ワーキングメモリ領域３１と、ルーチン領域３３とを有する。これらのメモリ領域は、メモリの連続ブロックに対応する必要はないことは理解されよう。加えて、従来のように、メモリ１５は、処理時間を低減するために採用されている従来のデータキャッシング技法による異なるアクセス時間を有するさまざまなメモリ装置を含むことができる。
【００２４】
画像メモリ領域は、Ｎ個の画像３５ａ〜３５ｎを記憶する。各画像３５は、画像データの２次元配列を含む。それによって、画像３５はＩk（ｘ，ｙ）（ｋ＝１．．．．．Ｎ）として表される。
【００２５】
特徴量メモリ領域２５は、画像領域２３内に記憶されている画像３５内において識別される特徴点の特徴量データを記憶する。これらの特徴点は、画像３５内の画像が共通の特徴を含むか否かを判断するための比較可能でディスティンクティブな特徴量（distinctive feature）に対応する。各特徴点は対応する強度値を有する。以降でより詳細に考察されるように、この実施形態では、類似の強度値を有する特徴点は、ビン３７ａ〜３７ｎに共にグループ化される。
【００２６】
累積器メモリ領域は、ハフ変換累積器３９と、閾値累積器４１とを格納する。ハフ変換累積器３９は、画像３５の対ごとに、類似していると判定される画像対から抽出される特徴量の相対オリエンテーション及びスケールを記録する。類似の相対オリエンテーション及びスケールを有する画像対間の一致する特徴量のクラスタは、対応する画像間の重なりを示す。しかしながら、一致する特徴量の識別は処理集約的であり、そのため、この実施形態では、類似の相対オリエンテーション及びスケールを有する比較的少数の一致が識別されると、さらなる試験が行われて一致の信頼性が評価される。以降でより詳細に考察されるように、閾値累積器４１は、そのようなさらなる試験が実行されるのに先だって識別される必要のある、類似の相対オリエンテーション及びスケールを有する、信頼でき可能性のある一致する特徴量の個数を追跡する。
【００２７】
レジストレーショングラフ２９は、画像メモリ領域２３内の画像３５間の求められた一致を表すデータを記憶する。具体的には、画像対（ｋ1，ｋ2）ごとに、レジストレーショングラフ２９はレジストレーション［ｋ1，ｋ2］及び類似度［ｋ1，ｋ2］値を記憶する。レジストレーション［ｋ1，ｋ2］は３つの値をとることができる。すなわち、画像ｋ1が画像ｋ2と重なり合うことが分かっていることを示すＴＲＵＥ（真）と、画像ｋ1が画像ｋ2と重なり合わないことが分かっていることを示すＦＡＬＳＥ（偽）と、さらなる試験が必要であることを示すＵＮＤＥＦＩＮＥＤ（不明）とをとることができる。類似度［ｋ1，ｋ2］値は、画像ｋ1と画像ｋ2との類似度の質を示す数である。
【００２８】
ワーキングメモリ領域３１は、プロセッサ１１によって処理演算中の中間データを記憶するのに使用される。
【００２９】
ルーチンメモリ領域３３は、プロセッサ１１によってパノラマ認識中に使用されるルーチンを記憶する。この実施形態では、ルーチンメモリ領域は、以下のルーチンを記憶する。
− Master_Control（マスタ制御）ルーチン４３：パノラマ認識プロセスを統合する。
− Initialisation（初期化）サブルーチン４５：ハフ変換累積器３９、閾値累積器４１、及びレジストレーショングラフ２９を初期化する。
− Feature_Matching（特徴量マッチング）サブルーチン４７：反復的特徴量マッチングを実行する。
− Update_RG/PC（ＲＧ／ＰＣ更新）サブルーチン４９：画像の重なりを評価するのに使用されるレジストレーショングラフ及び／又は確率条件を更新するのに使用される。
− Evaluate_Accuracy（精度評価）サブルーチン５１：２つの画像の重なり合っている領域をリンクするホモグラフィ変換を評価及び改善するのに使用される。
− Graph_Closure（グラフ閉包）サブルーチン５３：レジストレーショングラフ２９に新たなエッジが追加されるたびに推移グラフ閉包を実行するのに使用される。
【００３０】
Master_Controlルーチン４３における主要ステップを図３に示す。図示されるように、Ｓ１においてＮ個の入力画像を受けとった後、Master_Controlルーチン４３はInitialisationサブルーチン４５をコールする。
【００３１】
図４に示されるように、Initialisationサブルーチン４５は、Ｓ３１において、画像対ごとにレジストレーショングラフ内の類似度値を−１に設定する。次いで、Initialisationサブルーチン４５は、Ｓ３５において、ハフ変換累積器のすべての要素を０に設定し、Ｓ３７において、閾値累積器のすべての要素をＮminに設定する。ここでＮminは、２つの画像間の重なりの確認を可能にするのに必要な信頼性のある特徴量一致の最小数である。Ｎminの値を計算する方法を下記でより詳細に考察する。
【００３２】
次いで、Initialisationサブルーチン４５は、Ｓ３７において、画像が自身の記録された順序を示す順序情報を含むか否かを調べる。画像が順序付けされている場合、Initialisationサブルーチン４５は、連続する画像のレジストレーションデータをＵＮＤＥＦＩＮＥＤに設定し、他のすべての画像対のレジストレーションデータをＦＡＬＳＥに設定する。これは、少なくとも最初は、連続していない画像間の重なりは調査されないことを意味する。次いでInitialisationサブルーチン４５は、Ｓ４７において終了する。
【００３３】
画像が順序付けされていない場合、Initialisationサブルーチン４５は、Ｓ４１において、画像にタイムスタンプが付されているか否か（すなわち、画像が自身の記録された時刻を含むか否か）を調べる。画像にタイムスタンプが付されている場合、Initialisationサブルーチン４５は、互いが所定時間、たとえば１０秒以内に記録された画像のレジストレーションデータをＵＮＤＥＦＩＮＥＤに設定し、他のすべての画像対のレジストレーションデータをＦＡＬＳＥに設定する。これは、少なくとも最初は、所定時間よりも離れて記録された画像間の重なりは調査されないことを意味する。次いでInitialisationサブルーチン４５は、Ｓ４７において終了する。画像３５がタイムスタンプを付されていない場合、Initialisationサブルーチンは、ステップ４５において、すべての画像対のレジストレーションデータをＵＮＤＥＦＩＮＥＤに設定し、Ｓ４７において終了する。
【００３４】
図３に戻って、Initialisationサブルーチン４５が終了すると、Master_Controlルーチンは、Ｓ５において、画像３５内の特徴点を検出する。この実施形態では、Foerstner及びGulchによる論文「A fast algorithm for detection and precise location of distinct points, corners, and circular features」（Proc. Intercommission Conference on Fast Processing of Photogrammetric Data, Interlaken (1987） pp287-305）（その全内容が参照により本明細書に援用される）に記載されているフェルスター演算子（Foerstner operator）を修正したものが使用される。具体的には、各画素の局所近傍ｎ（ｘ，ｙ）において計算される自己相関行列Ａの行列式とトレースとの比Ｒ（ｘ，ｙ）が、下記の式（１）及び式（２）に示されるように計算される。
【００３５】
【数１】
【００３６】
ここで、
【００３７】
【数２】
【００３８】
式（２）において、ガウシアンＧ（ｘ，ｙ）はウィンドウにわたって総和された導関数を重み付けするのに使用される。特徴点は、２次式をＲ（ｘ，ｙ）のマップ内の各極大点にフィッティングすることによって識別される。極大点の位置は特徴点の位置に対応し、極大点の推定値は特徴強度Ｒmを決定する。各画像内の検出された特徴点は、特徴強度の降順にソートされる。それによって、最も重要な特徴点はリストの上端に配置される。したがって、Ｒ1≧Ｒ2≧．．．≧Ｒm≧．．．≧Ｒnである。
【００３９】
特徴点の検出後、Master_Controlルーチン４３は、Ｓ７において、検出された特徴点を正規化する。この実施形態では、正規化は画像ごとに行われ、画像内の各特徴点ｍの正規化された特徴強度は下記の式（３）によって与えられる。
【００４０】
【数３】
【００４１】
これによって、０〜１の区間内で変化する正規化コーナー強度（normalised corner strength）の範囲が与えられる。次いで、すべての画像からの特徴量が、それらの特徴強度にしたがってビン３７内にソートされる。具体的には、この実施形態では、各ビン３７は区間０〜１の区別可能なパーセンタイル値に対応し、ビン１は０．００〜０．０１をカバーし、ビン２は０．０１〜０．０２をカバーし、ビン１００が範囲０．９９〜１．００をカバーするまで以下同様である。各特徴量ｆは特徴強度の順にすべての画像にわたる大域インデックスｉを付される、そして、特徴量ｆiは以下の情報を記憶する。
【００４２】
【数４】
【００４３】
ここで、ｋiは特徴量が現れる画像を識別し、ｍiはその画像内における特徴量のインデックス番号を識別し、（ｘi，ｙi）は特徴量の画像ｋi内における位置であり、ｄiは比較目的で使用される特徴量記述子である。この実施形態では、特徴量記述子ｄiは、以下の式にしたがって、特徴点を中心とする局所画像領域内における画素値の対数極変換（ＬＰＴ）によって形成される。
【００４４】
【数５】
【００４５】
特徴点を正規化及びソートする理由は、一般に、特徴量が、当該特徴量が現れる種々の画像内において類似のディスティンクティブネス（distinctiveness）を有するためである。しかしながら、特徴強度は倍数的な強度変化に対して不変ではない。したがって、倍数因子を除去するために正規化を行う。
【００４６】
特徴点が正規化及びソートされた後、Master_Controlルーチン４３はFeature_Matchingサブルーチン４７をコールする。
【００４７】
図５に示すように、Feature_Matchingサブルーチン４７は、Ｓ６１において、次に評価される特徴点を選択する。次に評価される特徴点は、対象特徴量（subject feature）と呼ばれることになる。この実施形態では、特徴点は特徴強度の降順に調査される（すなわち、最もディスティンクティブな特徴量が最初に識別される）。したがって、対象特徴量は、まだ評価されていない最高の特徴強度を有する特徴点である。
【００４８】
次いで、Feature_Matchingサブルーチン４７は、Ｓ６３において、対象特徴量が出現する画像に関連して現在レジストレーションされていない（すなわち、２つの画像間のレジストレーションデータがＵＮＤＥＦＩＮＥＤである）他の画像内に出現する、類似の正規化特徴強度を有する複数の特徴量を識別する。具体的には、この実施形態では、対象特徴量の正規化特徴強度の０．１５以内である正規化特徴強度を有する特徴量のみを調査する。換言すれば、対象特徴量の正規化特徴強度の０．１５以内である正規化特徴強度に対応するビン内の特徴量のみを調査する。
【００４９】
対象特徴量の画像に関連してまだレジストレーションされていない他の画像内にある類似の正規化特徴強度を有する複数の特徴量が識別されると、Feature_Matchingサブルーチン４７は、Ｓ６３において、対象特徴量と識別された複数の特徴量との間で最も良く一致するものを見つける。これは、対象特徴量ｆiの記述子ｄiと、識別された複数の特徴量の各記述子とを比較することを含む。類似度は、数値ν、画像領域間の局所的な相対オリエンテーション係数θ及びスケール係数Ｓによって特性化される。
【００５０】
上記で考察したように、各特徴点の記述子ｄiはＬＰＴ変換を使用して生成される。このようにして、軸を中心とするスケーリング及びオリエンテーションは（θ，ｓ）座標におけるシフトによって表される。したがって、２Ｄマッチングの方法を使用することによって、特徴点を中心とする画像領域間の類似度値、局所的な回転、及びスケールが得られる。この実施形態では、はじめに、高速ではあるが信頼性の劣る１Ｄマッチングアルゴリズムを対数極画像の射影に対して適用して、類似していない特徴量対をフィルタリング除去する。続いて、正規化相関又は位相相関２Ｄマッチングアルゴリズムを適用する。
【００５１】
最も良く一致するものが求められると、Feature_Matchingサブルーチン４７は、Ｓ６７において、オリエンテーションパラメータ及びスケールパラメータを整数座標に変換し、ハフ変換累積器３９及び閾値累積器４１を更新する。上記で考察したように、ハフ変換累積器３９は、類似のオリエンテーション値及びスケール値を有する一致の数を追跡する。これは、通常、２つの画像間の真の一致は類似のオリエンテーション値及びスケール値を有し、一方で偽の一致は回転−スケール領域内に均一に分布しているためである。整数座標［ｐ，ｑ］が、（θ，ｌｏｇＳ）領域内に以下のように導入される。
【００５２】
【数６】
【００５３】
ここでｓ＝ｌｏｇＳであり、ｓ0は最小スケール係数の対数であり、Δｓは対数スケール軸の離散的な間隔である。
【００５４】
この実施形態では、別個のハフ変換累積器が各画像対に使用され、Ｎ個の画像に対してＮ（Ｎ−１）／２個のハフ変換累積器が存在することになる。画像ｋi及び画像ｋj（ｋi＞ｋj）内にある特徴点間の一致のためのハフ変換累積器は、Ａij［ｐ，ｑ］によって表される。各ハフ変換累積器は整数の２Ｄ配列である。対象特徴量に関して、最も良く一致すると識別された特徴量がそれぞれ［ｐ，ｑ］座標内にマッピングされ、対象特徴量の画像と、それに最も良く一致する画像とを結びつけるハフ変換器内における対応する［ｐ，ｑ］値が１だけ加算される。
【００５５】
図６は、例示を容易にするために、画像１のうちの４つのみに対して適用したこの投票手法を示す。具体的には、ローマの円形競技場の重なり合っているビューを示す画像１ｅ及び１ｇ、並びに、都市の屋根の光景の重なり合っているビューを示す画像１ｄ及び１ｈに対して適用したこの投票手法を示す。累積器Ａ21が画像１ｈ及び１ｇの対に関連付けられ、累積器Ａ31が画像１ｅ及び１ｇの対に関連付けられ、累積器Ａ41が画像１ｄ及び１ｇの対に関連付けられ、累積器Ａ32が画像１ｅ及び１ｈの対に関連付けられ、累積器Ａ42が画像１ｄ及び１ｈの対に関連付けられ、累積器Ａ43が画像１ｄ及び１ｅの対に関連付けられている。
【００５６】
図６では、各画像からの特徴点のほぼ１０％が処理されている。同じ［ｐ，ｑ］値を有する多数の一致する特徴量を示す大きなピークが累積器Ａ31及びＡ42内に存在している。これは、これらの累積器が重なり合う画像対に関連付けられていることを予想させる。他の累積器内にある小さな雑音の多いピークは、対応する画像対が異なるシーケンスに属し、幾何学的に位置合わせすることができないことを示す。
【００５７】
ハフ変換累積器における特徴量一致の分布は、いずれの画像が重なり合っているかを示すが、幾何学的に整合している一致の数は、ハフ変換累積器におけるピークの高さよりもディスティンクティブな真のクラスタの指標である。これは、通常、ハフ変換累積器におけるピークが多数の誤った一致を含むためである。エラーを低減するために、これらの誤った一致は画像変換を計算する前に除去されるべきである。誤った一致は、ＲＡＮＳＡＣ推定器を適用することによって除去することができる。ＲＡＮＳＡＣ推定器は、画像間のホモグラフィを有する幾何学的に整合している一致する特徴量対（インライア（inlier）と呼ばれる）と、幾何学的に整合していない一致する特徴量対（アウトライア（outlier）と呼ばれる）とを識別する。この実施形態では、下記でより詳細に説明するように、画像が重なり合っているか否かを判断するときにインライアとアウトライアの割合を使用する。
【００５８】
図７に示すように、閾値累積器４１は、ハフ変換累積器３９と同様に、各画像対の［ｐ，ｑ］空間における２Ｄ累積器を含む。上記で考察したように、閾値累積器４１内にあるすべての要素は初期状態ではＮminに設定されている。そして、最も良く一致すると識別された特徴量がそれぞれ［ｐ，ｑ］座標内にマッピングされ、対象特徴量の画像と、それに最も良く一致する画像とを結びつける閾値累積器内における対応する［ｐ，ｑ］値が１だけ減算される。
【００５９】
図３に戻って、対象特徴量の特徴量マッチングを行った後、Master_Controlルーチン４３は、Ｓ１１において、閾値累積器４１の任意の要素がゼロに達したか否かを調べる。達していない場合、Master_Controlルーチン４３は、次の画像特徴量に対して特徴量マッチングを行う。一方、閾値累積器４１の或る要素がゼロに達している場合、Master_Controlルーチンは、Ｓ９において、インライア及び最良の変換を識別するＲＡＮＳＡＣを実行する。具体的には、ＲＡＮＳＡＣは、ハフ変換累積器３９におけるピークに対応する特徴量一致を処理することによって、重なり合っている領域、及び、その重なり合っている領域内における特徴点中のインライアの数を、推定されるホモグラフィに基づいて求める。次いで、ホモグラフィパラメータがすべてのインライアから再推定される。次いで、新しいより正確なホモグラフィパラメータと、隣接するハフ変換累積器要素からの特徴量一致を使用して、拡張されたインライアセットが求められる。このプロセスはインライアの数が安定するか、又は一定回数の反復が行われるまで繰り返される。
【００６０】
次いで、Master_Controlルーチン４３は、Ｓ１５において、ＲＡＮＳＡＣ処理の結果を解析するUpdate_RG/PCサブルーチン４９を実行する。これより、図８を参照してUpdate_RG/PCサブルーチンをより詳細に考察する。
【００６１】
Update_RG/PCサブルーチン４９は、Ｓ７１において、ＲＡＮＳＡＣ処理の結果を受け取った後、Ｓ７３において、画像マッチングの確率閾値が満たされているか否かを調べる。確率閾値はベイズルールに基づき、これによって、画像一致が正しい確率を、インライアの数Ｎ(i)及びアウトライアの数Ｎ(o)から求めることが可能となる。インライアの総数は２項分布を有するものと仮定すると、正しい画像一致の事後確率は、ベイズルールを使用して以下のように推定される。
【００６２】
【数７】
【００６３】
ここで、Ｐ（ｘ｜ｙ）はｙが与えられた場合にｘがＴＲＵＥである確率である。
【００６４】
Ｐ（正しい一致｜Ｎ(i)）がＰminよりも大きいときに画像一致を受け入れる結果として、条件は以下のようになる。
【００６５】
【数８】
【００６６】
ここで、α及びβの数値は、特徴量一致が正しい画像一致に対してインライアである確率、特徴量一致が正しい画像一致に対してアウトライアである確率、Ｐmin、及びＰ（正しい一致）を設定することによって得られる。したがって、Update_RG/PCサブルーチン４９は、式（９）において指定されている条件が満たされるか否かを調べる。
【００６７】
インライアの数が確率閾値を満たさない場合、Update_RG/PCサブルーチン４９は、Ｓ７５において、確率条件を更新すると共に、調査中の閾値累積器４１の要素［ｐ，ｑ］に新たな値を入力する。式（９）から、画像一致を確立するのに必要な最小数Ｎminは、アウトライアの数がゼロである場合に現れ、以下の式によって与えられることが分かる。
【００６８】
【数９】
【００６９】
ここで、［．．．］は実数の整数部分である。Ｎminは、上記で考察したように閾値累積器４１の要素に入力される初期値である。したがって、閾値累積器４１の要素が画像一致を示す最小数の特徴量を含むようになるまで、さらなる試験は行われない。
【００７０】
ＲＡＮＳＡＣ処理において識別されるインライアの数Ｎ(i)とアウトライアの数Ｎ(o)との間の関係が式（９）を満たさない場合、Update_RG/PCサブルーチン４９は、Ｓ７５において、満たされるべき確率条件をＲＡＮＳＡＣ処理が再び行われる前に更新する。これは、画像一致の可能性を示すのに必要な追加の特徴量一致の最小数Ｎmin’が、以下の式（１１）を満たさなければならないという事実に基づく。
【００７１】
【数１０】
【００７２】
これは、以下を意味する。
【００７３】
【数１１】
【００７４】
次いで、調査中の特徴量一致のクラスタに対応する、閾値累積器４１の［ｐ，ｑ］要素の値をＮmin’に設定する。これによって、最小数の追加の特徴量一致が［ｐ，ｑ］要素に追加されて式（９）を満たすことが可能になるまで、これらの特徴量一致のＲＡＮＳＡＣ処理は再び行われない。
【００７５】
式（１２）から、アウトライアの数Ｎ(0)が大きくなるほどＮmin’の値も大きくなることが理解されよう。これを前提とすると、Ｎmin’の値が、式（９）が常に満たされる可能性が統計的に低い値に達する可能性がある。具体的には、各ハフ変換累積器の要素［ｐ，ｑ］の増大速度の推定値は、累積器Ａ(i,j)［ｐ，ｑ］内の一致の数と、現在の画像内でこれまで処理されている特徴量ｍiの数との比によって与えられる。したがって、閾値累積器Ｔ(i,j)の次の要素がゼロに達する前に比較する必要がある特徴量の数を、以下の式によって推定することができる。
【００７６】
【数１２】
【００７７】
画像ｋiにおいて処理されていない特徴量の数が式（１３）によって求められる最小数ΔＮ(i,j)を下回る場合、画像対ｋi，ｋjがレジストレーションされる可能性は統計的に低い。したがって、これが起こるとき、レジストレーション［ｋi，ｋj］はＦＡＬＳＥに設定される。これによって、画像ｋiからの特徴量を画像ｋjからの特徴量とそれ以上比較することが回避される。
【００７８】
図７において、各画像からの約１０％の特徴量が処理されている。累積器Ｔ31内にある要素、及び累積器Ｔ42内にある要素は既にゼロに達しており、これは、画像対（３，１）及び（４，２）は、一致する可能性があることを示している。累積器Ｔ32内に位置する別の要素がゼロに近づいており、これは、対応する特徴量一致のクラスタが、次の数回の反復の後にＲＡＮＳＡＣを使用して処理される可能性があることを示している。この要素がゼロに達すると、ＲＡＮＳＡＣ処理は、ごく少数のインライア及び多数のアウトライアを発見することになる。その結果、その要素に大きな修正閾値がもたらされる。これは、画像３及び２は同じパノラマの一部を形成していないため、期待される結果である。
【００７９】
ＲＡＮＳＡＣ処理において識別されたインライアの数が式（９）によって規定される確率条件を満たす場合、Update_RG/PCサブルーチン４９は、Ｓ７７において、Evaluate_Accuracyサブルーチン５１を実行する。
【００８０】
Evaluate_Accuracyサブルーチン５１は、２つの画像ｋi，ｋjにおける重なり合っている領域の相関解析を行うことによって２つの画像のCurrent_Similarity（現在の類似度）値を計算し、画像ｋiと画像ｋjとの間の最良のホモグラフィを計算する。計算されたCurrent_Similarity値が類似度［ｋi，ｋj］の値よりも大きい場合、類似度［ｋi，ｋj］の値は計算されたCurrent_Similarity値に設定される。Current_Similarity値が所定閾値を上回る場合、レジストレーション［ｋi，ｋj］の値がＴＲＵＥに設定される。これによって画像ｋi及びｋjからの特徴量をそれ以上比較することが回避される。
【００８１】
図８に戻って、Update_RG/PCサブルーチン４９は、Ｓ８１において、Graph_Closureサブルーチン５３を実行する。一般に、Graph_Closureサブルーチン５３は、画像ｋi及びｋjの新たなレジストレーション情報を、任意の他の画像対のレジストレーション情報の改善に使用することができるか否かを調べる。これより、これについて図９を参照してより詳細に説明する。
【００８２】
図９に示すように、Graph_Closureサブルーチンは、いかなる時点においても、調査中である画像ｋk及びｋl（ｌ＞ｋ）の画像対間を反復する。最初に、Ｓ９１においてｋの値が１に設定され、Ｓ９３においてｌの値がｋ＋１に設定される。次いで、Graph_Closureサブルーチン５３は、Ｓ９５において、画像ｋkから画像ｋlへの経路が存在する否かを判断する。経路が存在しない場合、Ｓ９５においてｌがｌ＋１に設定された後、経路が存在するか否かが再び調べられる。経路が存在する場合、画像ｋkと画像ｋlとの間の最短経路に基づいてホモグラフィＨklが計算される。
【００８３】
２つの画像間の最短経路は必ずしも最小数の画像を通る経路ではない。より正確なホモグラフィを有するより長い経路が、正確さの劣るホモグラフィを有するより短い経路よりも好ましい場合がある。グラフ理論において、最短経路問題は、構成エッジの重みの総和が最小になるような、２つの頂点間の最短経路を求めることである。この実施形態では、重み（１−類似度［ｋi，ｋj］）が画像ｋiと画像ｋjとを連結するエッジに適用される。この重みは、画像レジストレーションの精度を考慮に入れる。ただし、重なり合っている領域又はインライアの数は、これらの因子は双方とも良好なレジストレーションにとって重要ではないため、考慮に入れない。
【００８４】
ホモグラフィＨklを計算した後、Ｓ１０５において、画像ｌの境界が画像ｋ上に射影されて、重なり合っている領域が計算される。重なり合っている領域が存在しない場合、Graph_Closureサブルーチンは、Ｓ１０５において、レジストレーション［ｋ，ｌ］をＦＡＬＳＥに設定する。これによって、画像ｋk内の特徴量と画像ｋl内の特徴量とをそれ以上比較することが回避される。重なり合っている領域が存在する場合、Graph_Closureサブルーチンは、Ｓ１０７において、Evaluate_Accuracyサブルーチン５１を実行して、類似度［ｋ，ｌ］及びホモグラフィ［ｋ，ｌ］の最良の値を最適化及び記憶する。類似度［ｋ，ｌ］の値が所定閾値を超える場合、レジストレーション［ｋ，ｌ］をＴＲＵＥに設定し、画像ｋk内の特徴量と画像ｋl内の特徴量とをそれ以上比較することを回避する。
【００８５】
次いで、Graph_Closureサブルーチン５３は、Ｓ１０９において、ｌの値がＮ（画像の総数）に等しいか否かを調べる。等しくない場合、Ｓ９７においてｌの値に１が加算された後、経路の存在が再び調べられる。ｌがＮに等しい場合、Graph_Closureサブルーチン５３は、Ｓ１１１において、ｋがＮ−１に等しいか否かを調べる。等しくない場合、Ｓ１１３においてｋの値に１が加算された後、Ｓ９３においてｌの値がｋ＋１に設定され、経路の存在が再び調べられる。ｋがＮ−１に等しい場合、Graph_Closureサブルーチン５３は、Ｓ１１５において終了する。
【００８６】
図１０Ａ〜図１０Ｄは、レジストレーショングラフが展開する様態を示す。図１０Ａにおいて、約４％の特徴量が処理されており、画像対（３，１）、（４，２）、及び（８，４）がレジストレーションされている（レジストレーショングラフの対応するノード間の実線で示す）。加えて、画像対（２，８）の間に画像４を介する経路が存在し、画像８及び画像４と画像４及び画像２との間の変換に基づいて、画像８と２との間の重なりが識別されている。
【００８７】
図１０Ｂにおいて、約１１％の画像特徴量が処理されており、画像対（５，１）がレジストレーションされている。加えて、画像対（５，１）間に経路が存在しているが、重なりは計算されていない。図１０Ｃにおいて、約４０％の特徴量が処理されており、画像対（７，５）がレジストレーションされている。加えて、画像７と画像１との間、及び画像７と画像３との間に経路が存在しているが、重なりは計算されていない。最後に、図１０Ｄにおいて、約４２％の特徴量が処理されており、画像対（６，４）がレジストレーションされている。加えて、画像対（８，６）間に経路が存在し、重なりが計算されている。また、画像対（６，２）間に経路が存在するが、重なりは計算されていない。
【００８８】
図３に戻って、レジストレーショングラフ及び確率条件の更新後、Master_Controlルーチン４３は、Ｓ１７において、すべての画像対が処理されているか否かを調べる。処理されていない場合、上述のような特徴量マッチングが次の特徴量に対して行われ、このプロセスはすべての画像対がレジストレーションされるまで繰り返される。すべての画像対がレジストレーションされると、接続された画像のグループがレジストレーショングラフから識別され、各グループ内の画像が共に融合されて１組のパノラマである出力が形成される。
【００８９】
変更形態及びさらなる実施形態
主実施形態においては、本発明は、画像の順序付けされていないセットからパノラマを形成するのに使用されている。ディジタルカメラのプロ及びアマチュアのユーザは同じシーンの複数のショットを撮影することが多いため、これはディジタル写真には有用である。これはたとえば、１）同じシーンのパノラマ的なシーケンス、２）フレーム内の最良の構図を発見しようとする複数回の試行、３）最良のカメラパラメータ（シャッタスピード、開口）を求めようとする複数回の試行、４）ディジタルカメラのバーストモード（カメラパラメータのできるだけの変更を伴って短い時間間隔で画像が撮影される）からの画像、５）異なる被写体に合焦した複数のショット、６）フラッシュをたく／たかない複数のショット、７）同じビュー内の異なる複数の人物の複数のショット、を含むことができる。したがって、同じシーンの複数のショットはユーザにとって特別な意味を有し、或るさらなる処理が望ましい場合がある（たとえば、パノラマ的なシーケンスに対してパノラマを作成すること、最良の構図／露出を有するショットを選択すること、最良のポートレートを選択すること等）。
【００９０】
本発明を、同じビューのショットから成るすべてのグループの高速抽出に使用することができる。パノラマ生成に関しては画像合成を自動化することができるが、他の用途においては合成画像は所望の結果ではなく、単に同じビューに関連する画像グループを識別することが所望の結果であることが理解されよう。本発明を写真処理ソフトウェアとして実施することは、ユーザが、そうでなければさらなる注意を必要とする手作業になる画像の作業を自動化するのに役立つ。一実施形態では、写真処理ソフトウェアをディジタルカメラ内に実装することができる。
【００９１】
本発明の別の応用形態は、空中／衛星偵察である。通常、空中偵察及び衛星偵察のセンサは、或るルートに沿って連続的に画像を収集する。これらの画像は順序付けされている。異なるルート又は軌道から撮影された画像をレジストレーションするときに問題が発生する。通常、航空機／衛星の位置に関する情報が、異なる飛跡からの重なり合っている画像を識別するのに役立つ。本発明によって、１つの飛跡に沿った複数の画像（along-track images）、及び、異なる飛跡間の複数の画像（between-track images）のレジストレーションの双方の問題を大幅に単純化することができる。本発明は、飛跡に沿った自然な画像の順序付けに関する情報、及び、飛跡自体の時間又は位置に基づく順序付けに関する情報をレジストレーショングラフ内に均一に組み込む。
【００９２】
本発明のさらなる応用形態は、マルチプロジェクタディスプレイにおけるものである。いくつかの大型マルチメディアディスプレイは、複数のプロジェクタを使用して同じシーンの異なる複数の部分を視覚化することができる。本発明は、複数のプロジェクタからの出力を、投影画像の自動レジストレーションによって同期させるのを支援することができる。この方法の順序付けされていない入力によって、異なるレイアウトのプロジェクタを使用することが可能となる。これによって、精密な手作業の処理又は半自動処理を行うことなくプロジェクタを柔軟に位置決めすることが可能となる。
【００９３】
主実施形態においては、修正されたフェルスター演算子が特徴点の識別に使用されている。特徴点を識別する他のアルゴリズム、例えばモラベック演算子又はハンナ演算子を使用することもできることが理解されよう。主実施形態において、特徴強度が対数関数を使用して０〜１の範囲に正規化されている。（Ｒm−Ｒn）／（Ｒ1−Ｒn）のような他の関数を使用することもできることが理解されよう。加えて、特徴強度を範囲０〜１にわたって正規化するのではなく、任意の範囲にスケーリングすることもできる。
【００９４】
主実施形態においては対数極記述子ｄiが使用されているが、正規化画像パッチ（normalised image patch）又はＳＩＦＴ記述子のような他の種類の記述子を使用することもできる。
【００９５】
主実施形態は、主に４つの技法、すなわち、
１）特徴量マッチングを類似の特徴強度を有する特徴量に限定すること
２）関連しない特徴量対を反復ベースの確率的手法を使用して拒絶すること
３）重なり合っている画像をレジストレーショングラフの反復ベースの推移閉包を使用してレジストレーションすること
４）重なり合っていない画像をレジストレーショングラフの推移閉包を使用して拒絶すること
を使用して必要な特徴量マッチングの演算数を低減する。
【００９６】
これら４つの方式をすべて使用すると最良の結果が得られるが、いくらかの利益を得るためにこれら４つの方式のすべてを使用する必要はないことは理解されよう。代替的な実施形態では、方式１）と２）、又は、方式１）と３）、又は、方式１）と３）と４）を使用することができる。
【００９７】
図面を参照して説明された実施形態は、コンピュータ装置を含む。また、コンピュータ装置において実行されるプロセスを含む。本発明は、コンピュータプログラム、特に本発明を実行に移すようになっている、キャリア上又はキャリア内のコンピュータプログラムにも及ぶ。プログラムはソースコード、オブジェクトコード、部分的にコンパイルされた形態のようなソースコードとオブジェクトコードとの中間のコード、又は本発明によるプロセスの実装において使用するのに適切な任意の他の形態とすることができる。
【００９８】
キャリアは、プログラムを保持することが可能な任意のエンティティ又は装置とすることができる。たとえば、キャリアは、ＲＯＭ、たとえばＣＤ−ＲＯＭ若しくは半導体ＲＯＭ、又は磁気記録媒体、たとえばフロッピー（登録商標）ディスク若しくはハードディスク、又は光記録媒体のような記憶媒体を含むことができる。さらに、キャリアは、電気ケーブル若しくは光ケーブルを介して、又は無線若しくは他の手段によって搬送することができる電気信号又は光信号のような伝送可能キャリアとすることもできる。
【００９９】
キャリアは、プログラムが組み込まれる集積回路とすることができ、当該集積回路は、関連するプロセスを実行するか、又は関連するプロセスの実行に使用されるようになっている。
【０１００】
説明された実施形態において、本発明はソフトウェアによって実施されているが、代替的に、本発明をハードウェア装置、又はハードウェア装置とソフトウェアとの組み合わせによって実施することもできることは理解されよう。
【特許請求の範囲】
【請求項１】
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法であって、
各画像内のディスティンクティブな特徴量を識別することと、
一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、
前記１つ又は複数の画像グループを求めるために、前記可能性のある一致を処理することと
を含み、
前記比較することは、前記或る画像内のディスティンクティブな特徴量を、１つ又は複数の所定基準を満たす前記他の画像内の前記ディスティンクティブな特徴量のサブセットのみと比較することを含む、
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法。
【請求項２】
前記比較することは、前記或る画像から取得される最小数の特徴量が１つ又は複数の所定基準を満たすと停止する、請求項１に記載の方法。
【請求項３】
前記方法は、前記識別されたディスティンクティブな特徴量の特徴強度を計算することをさらに含み、
前記１つ又は複数の所定基準は、前記比較が行われるために満たされるべき特徴強度の類似度のレベルを指定する、請求項１又は２に記載の方法。
【請求項４】
前記特徴強度を計算することは、
極大点における特徴点検出アルゴリズムの値を測定することと、
各画像に関して、測定値を該画像内の該測定値に従ってスケーリングすることと
を含む、請求項３に記載の方法。
【請求項５】
前記スケーリングすることは、極大点における前記測定値の対数を計算することを含む、請求項４に記載の方法。
【請求項６】
前記スケーリングすることは、前記極大点における値をすべての画像に共通する所定範囲内に正規化することを含む、請求項５に記載の方法。
【請求項７】
前記極大点における前記測定値がＲmである画像内におけるディスティンクティブな特徴量の前記特徴強度ｒmは、以下の式によって与えられ、
【数１】
ここで、Ｒ1は、前記識別されたディスティンクティブな特徴量のうち、最もディスティンクティブである特徴量の前記極大点における前記測定値であり、Ｒnは、前記識別されたディスティンクティブな特徴量のうち、最もディスティンクティブでない特徴量の前記極大点における前記測定値である、請求項６に記載の方法。
【請求項８】
前記特徴点検出アルゴリズムは修正されたフェルスター演算子を利用する、請求項４〜７のいずれか一項に記載の方法。
【請求項９】
前記２つの特徴量を比較することは、
オリエンテーションパラメータ及びスケールパラメータを求めるために、各特徴量を中心とする局所領域における画像記述子を比較することと、
前記２つの特徴量に対応する前記画像対に関連付けられる前記求められたオリエンテーションパラメータ及びスケールパラメータを記録することと
を含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
同一の記録されたオリエンテーションパラメータ及びスケールパラメータの数が閾値を超える場合に、該同一の記録されたオリエンテーションパラメータ及びスケールパラメータを有する画像対の比較された特徴量を、大域的整合性に関して解析することをさらに含む、請求項９に記載の方法。
【請求項１１】
前記画像対のレジストレーションを可能にする正しい特徴量一致の最小数の確率的解析に基づいて、初期閾値を計算することをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記大域的整合性の解析はＲＡＮＳＡＣ処理を含む、請求項１０又は１１に記載の方法。
【請求項１３】
前記大域的整合性の解析の結果が否定的である場合に、前記同一の記録されたオリエンテーションパラメータ及びスケールパラメータを有する追加の特徴量一致の数のための新たな閾値を計算することをさらに含む、請求項１０〜１２のいずれか一項に記載の方法。
【請求項１４】
必要な同一のオリエンテーションパラメータ及びスケールパラメータを有する特徴量一致の数が、該オリエンテーションパラメータ及びスケールパラメータに関連付けられる前記閾値に達することが可能であるか否かを、残りの可能性のある特徴量一致の総数と、オリエンテーションパラメータ及びスケールパラメータの各セットに関する推定特徴量一致レートとに基づいて調べることと、
前記調べることが閾値に達することが不可能であることを示す場合に、その画像対を可能性のある画像対として拒絶することと
をさらに含む、請求項１３に記載の方法。
【請求項１５】
前記大域的整合性のチェックの結果が肯定的である場合に、レジストレーショングラフを更新することをさらに含む、請求項１０〜１４のいずれか一項に記載の方法。
【請求項１６】
前記更新することは、推移グラフ閉包を実行することを含む、請求項１５に記載の方法。
【請求項１７】
前記推移グラフ閉包は、
リンクされている画像グループに関して可能性のある追加の画像対を識別することと、
前記リンクされている画像グループ内の他の画像対からのホモグラフィ情報に基づいて、前記追加の画像対内の前記画像が重なり合っているか否かを判断することと、
を含む、請求項１６に記載の方法。
【請求項１８】
前記画像が重なり合っていると判断すると、可能性のある画像対をレジストレーションすることをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記画像が重なり合っていないと判断すると、可能性のある画像対を拒絶することをさらに含む、請求項１７又は１８に記載の方法。
【請求項２０】
前記処理することは、画像対がレジストレーションされるための確率条件を満たすか否かを判断することをさらに含み、
前記１つ又は複数の所定基準は、既にレジストレーションされている特徴量に関しては特徴量比較を行われないことを指定する、
請求項１〜１９のいずれか一項に記載の方法。
【請求項２１】
前記処理することは、画像対がレジストレーションされないための確率条件を満たすか否かを判断することをさらに含み、
前記１つ又は複数の所定基準は、既にレジストレーションすべきでないと判断されている特徴量に関しては特徴量比較を行われないことを指定する、
請求項２０に記載の方法。
【請求項２２】
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法であって、
ｉ）各画像内のディスティンクティブな特徴量を識別することと、
ｉｉ）一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、
ｉｉｉ）前記他の画像のうちの少なくとも１つが前記或る画像と同じ画像グループに属するか否かを判断するために、前記可能性のある一致を処理することと、
ｉｖ）ステップｉｉ）及びｉｉｉ）を新たなディスティンクティブな画像に関して反復的に繰り返すことと
を含み、
前記比較することは、前記新たなディスティンクティブな特徴量と、前記或る画像と同じ画像グループの一部であることが既に判断されている他の画像内のディスティンクティブな特徴量とを比較しない、
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法。
【請求項２３】
前記可能性のある一致を処理することは付加的に、前記他の一致のうちの少なくとも１つが前記或る画像と同じ画像グループに属さないかを判断するように動作可能であり、
前記比較することは、前記新たなディスティンクティブな特徴量と、前記或る画像と同じ画像グループの一部でないことが既に判断されている他の画像内のディスティンクティブな特徴量とを比較しない、
請求項２２に記載の方法。
【請求項２４】
請求項１〜２３のいずれか一項に記載の方法を実行するように動作可能である装置。
【請求項２５】
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求めるように動作可能な画像処理装置であって、
各画像内のディスティンクティブな特徴量を識別する手段と、
一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較する手段と、
前記１つ又は複数の画像グループを求めるために、前記可能性のある一致を処理する手段とを備え、
前記比較する手段は、前記或る画像内のディスティンクティブな特徴量を、１つ又は複数の所定基準を満たす前記他の画像内の前記ディスティンクティブな特徴量のサブセットのみと比較するように動作可能である、画像処理装置。
【請求項１】
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法であって、
各画像内のディスティンクティブな特徴量を識別することと、
一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、
前記１つ又は複数の画像グループを求めるために、前記可能性のある一致を処理することと
を含み、
前記比較することは、前記或る画像内のディスティンクティブな特徴量を、１つ又は複数の所定基準を満たす前記他の画像内の前記ディスティンクティブな特徴量のサブセットのみと比較することを含む、
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法。
【請求項２】
前記比較することは、前記或る画像から取得される最小数の特徴量が１つ又は複数の所定基準を満たすと停止する、請求項１に記載の方法。
【請求項３】
前記方法は、前記識別されたディスティンクティブな特徴量の特徴強度を計算することをさらに含み、
前記１つ又は複数の所定基準は、前記比較が行われるために満たされるべき特徴強度の類似度のレベルを指定する、請求項１又は２に記載の方法。
【請求項４】
前記特徴強度を計算することは、
極大点における特徴点検出アルゴリズムの値を測定することと、
各画像に関して、測定値を該画像内の該測定値に従ってスケーリングすることと
を含む、請求項３に記載の方法。
【請求項５】
前記スケーリングすることは、極大点における前記測定値の対数を計算することを含む、請求項４に記載の方法。
【請求項６】
前記スケーリングすることは、前記極大点における値をすべての画像に共通する所定範囲内に正規化することを含む、請求項５に記載の方法。
【請求項７】
前記極大点における前記測定値がＲmである画像内におけるディスティンクティブな特徴量の前記特徴強度ｒmは、以下の式によって与えられ、
【数１】
ここで、Ｒ1は、前記識別されたディスティンクティブな特徴量のうち、最もディスティンクティブである特徴量の前記極大点における前記測定値であり、Ｒnは、前記識別されたディスティンクティブな特徴量のうち、最もディスティンクティブでない特徴量の前記極大点における前記測定値である、請求項６に記載の方法。
【請求項８】
前記特徴点検出アルゴリズムは修正されたフェルスター演算子を利用する、請求項４〜７のいずれか一項に記載の方法。
【請求項９】
前記２つの特徴量を比較することは、
オリエンテーションパラメータ及びスケールパラメータを求めるために、各特徴量を中心とする局所領域における画像記述子を比較することと、
前記２つの特徴量に対応する前記画像対に関連付けられる前記求められたオリエンテーションパラメータ及びスケールパラメータを記録することと
を含む、請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
同一の記録されたオリエンテーションパラメータ及びスケールパラメータの数が閾値を超える場合に、該同一の記録されたオリエンテーションパラメータ及びスケールパラメータを有する画像対の比較された特徴量を、大域的整合性に関して解析することをさらに含む、請求項９に記載の方法。
【請求項１１】
前記画像対のレジストレーションを可能にする正しい特徴量一致の最小数の確率的解析に基づいて、初期閾値を計算することをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記大域的整合性の解析はＲＡＮＳＡＣ処理を含む、請求項１０又は１１に記載の方法。
【請求項１３】
前記大域的整合性の解析の結果が否定的である場合に、前記同一の記録されたオリエンテーションパラメータ及びスケールパラメータを有する追加の特徴量一致の数のための新たな閾値を計算することをさらに含む、請求項１０〜１２のいずれか一項に記載の方法。
【請求項１４】
必要な同一のオリエンテーションパラメータ及びスケールパラメータを有する特徴量一致の数が、該オリエンテーションパラメータ及びスケールパラメータに関連付けられる前記閾値に達することが可能であるか否かを、残りの可能性のある特徴量一致の総数と、オリエンテーションパラメータ及びスケールパラメータの各セットに関する推定特徴量一致レートとに基づいて調べることと、
前記調べることが閾値に達することが不可能であることを示す場合に、その画像対を可能性のある画像対として拒絶することと
をさらに含む、請求項１３に記載の方法。
【請求項１５】
前記大域的整合性のチェックの結果が肯定的である場合に、レジストレーショングラフを更新することをさらに含む、請求項１０〜１４のいずれか一項に記載の方法。
【請求項１６】
前記更新することは、推移グラフ閉包を実行することを含む、請求項１５に記載の方法。
【請求項１７】
前記推移グラフ閉包は、
リンクされている画像グループに関して可能性のある追加の画像対を識別することと、
前記リンクされている画像グループ内の他の画像対からのホモグラフィ情報に基づいて、前記追加の画像対内の前記画像が重なり合っているか否かを判断することと、
を含む、請求項１６に記載の方法。
【請求項１８】
前記画像が重なり合っていると判断すると、可能性のある画像対をレジストレーションすることをさらに含む、請求項１７に記載の方法。
【請求項１９】
前記画像が重なり合っていないと判断すると、可能性のある画像対を拒絶することをさらに含む、請求項１７又は１８に記載の方法。
【請求項２０】
前記処理することは、画像対がレジストレーションされるための確率条件を満たすか否かを判断することをさらに含み、
前記１つ又は複数の所定基準は、既にレジストレーションされている特徴量に関しては特徴量比較を行われないことを指定する、
請求項１〜１９のいずれか一項に記載の方法。
【請求項２１】
前記処理することは、画像対がレジストレーションされないための確率条件を満たすか否かを判断することをさらに含み、
前記１つ又は複数の所定基準は、既にレジストレーションすべきでないと判断されている特徴量に関しては特徴量比較を行われないことを指定する、
請求項２０に記載の方法。
【請求項２２】
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法であって、
ｉ）各画像内のディスティンクティブな特徴量を識別することと、
ｉｉ）一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較することと、
ｉｉｉ）前記他の画像のうちの少なくとも１つが前記或る画像と同じ画像グループに属するか否かを判断するために、前記可能性のある一致を処理することと、
ｉｖ）ステップｉｉ）及びｉｉｉ）を新たなディスティンクティブな画像に関して反復的に繰り返すことと
を含み、
前記比較することは、前記新たなディスティンクティブな特徴量と、前記或る画像と同じ画像グループの一部であることが既に判断されている他の画像内のディスティンクティブな特徴量とを比較しない、
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求める方法。
【請求項２３】
前記可能性のある一致を処理することは付加的に、前記他の一致のうちの少なくとも１つが前記或る画像と同じ画像グループに属さないかを判断するように動作可能であり、
前記比較することは、前記新たなディスティンクティブな特徴量と、前記或る画像と同じ画像グループの一部でないことが既に判断されている他の画像内のディスティンクティブな特徴量とを比較しない、
請求項２２に記載の方法。
【請求項２４】
請求項１〜２３のいずれか一項に記載の方法を実行するように動作可能である装置。
【請求項２５】
複数の画像を処理して、それぞれが１つのパノラマを形成する１つ又は複数の画像グループを求めるように動作可能な画像処理装置であって、
各画像内のディスティンクティブな特徴量を識別する手段と、
一致する可能性のある特徴量を識別するために、或る画像内のディスティンクティブな特徴量を他の画像内のディスティンクティブな特徴量と比較する手段と、
前記１つ又は複数の画像グループを求めるために、前記可能性のある一致を処理する手段とを備え、
前記比較する手段は、前記或る画像内のディスティンクティブな特徴量を、１つ又は複数の所定基準を満たす前記他の画像内の前記ディスティンクティブな特徴量のサブセットのみと比較するように動作可能である、画像処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２０１０−５１４０４１（Ｐ２０１０−５１４０４１Ａ）
【公表日】平成２２年４月３０日（２０１０．４．３０）
【国際特許分類】
【出願番号】特願２００９−５４２２１７（Ｐ２００９−５４２２１７）
【出願日】平成１９年１２月２０日（２００７．１２．２０）
【国際出願番号】ＰＣＴ／ＧＢ２００７／００４９０７
【国際公開番号】ＷＯ２００８／０７５０６１
【国際公開日】平成２０年６月２６日（２００８．６．２６）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公表日】平成２２年４月３０日（２０１０．４．３０）
【国際特許分類】
【出願日】平成１９年１２月２０日（２００７．１２．２０）
【国際出願番号】ＰＣＴ／ＧＢ２００７／００４９０７
【国際公開番号】ＷＯ２００８／０７５０６１
【国際公開日】平成２０年６月２６日（２００８．６．２６）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]