(57)【要約】      （修正有）【課題】イメージのセットからコンポジット・イメージを生成するための方法および装置を提供する。【解決手段】イメージのセットから基準イメージが選択される。セット内の残りのイメージが、基準イメージに対して直接、もしくは先行して位置合わせ済みの中間イメージを介して位置合わせされる。先行して位置合わせ済みの中間イメージを介したイメージの位置合わせは、そのイメージから先行して位置合わせ済みの中間イメージを通って基準イメージに至る最短パスの長さを少なくとも部分的に基礎とする。基準イメージに対して残りのイメージのマッピングが行われ、それによってコンポジット・イメージが生成される。【選択図】図３
2007048290.tif 000002
【特許請求の範囲】
【請求項１】
画像のセットから合成画像を生成する方法であって、以下のことを備える、
前記セットから基準画像を選択すること、
前記セットにおける残りの画像を、前記基準画像に対して、直接、又は先に位置合わせされた中間画像を介して、位置合わせすること、ここで、先に位置合わせされた中間画像を介した画像の位置合わせは、該画像から先に位置合わせされた中間画像を経由して前記基準画像に至るまでの最短のパスの長さに、少なくとも部分的に基づいて行われる、
位置合わせされた画像を、前記基準画像に対して配置して、前記合成画像を生成すること。
【請求項２】
前記最短のパスの長さは、前記最短のパスに沿って経由する画像の数によって評価される、請求項１に記載の方法。
【請求項３】
前記残りの画像は、サイクル的に、位置合わせのために選択される、請求項２に記載の方法。
【請求項４】
各サイクルにおいて、画像が、段階的に、位置合わせのために選択される、請求項３に記載の方法。
【請求項５】
初期位置合わせサイクルの第１段階において、水平または垂直のパスに沿って前記基準画像に隣接する画像が選択され、前記基準画像に対して位置合わせされる、請求項４に記載の方法。
【請求項６】
前記初期位置合わせサイクルに続く各段階Ｓにおいては、
水平要素及び垂直要素のみを含む位置合わせパスに沿った、Ｓ−１個の位置合わせされた画像によって前記基準画像から分離されている画像が選択され、且つ位置合わせされる、請求項５に記載の方法。
【請求項７】
前記初期位置合わせサイクルの完了時に、位置合わせされていない画像が存在するときには、追加の位置合わせサイクルが実行され、前記位置合わせされていない画像を、隣接する先に位置合わせされた画像に位置合わせする、請求項６に記載の方法。
【請求項８】
前記追加の位置合わせサイクルは、前記位置合わせされていない画像のそれぞれが位置合わせされるか、位置合わせできないと判断されるまで実行される、請求項７に記載の方法。
【請求項９】
前記画像は、全体として行および列をなして配列されており、前記基準画像は、前記セットの中心に配置された画像である、請求項１に記載の方法。
【請求項１０】
前記画像は、前記基準画像の周囲に同心リングを形成し、第１のリングにおける、位置合わせされていない画像は、前記第１のリングより大きい第２のリングにおける、位置合わせされていない画像より先に分析される、請求項９に記載の方法。
【請求項１１】
前記配置がなされる際に、位置合わせがなされた画像それぞれを、前記基準画像に対して変換する変換行列が決定される、請求項１に記載の方法。
【請求項１２】
前記変換行列は、誤差が修正される、請求項１１に記載の方法。
【請求項１３】
画像のセットから合成画像を生成する方法であって、前記セット内の画像の１つが基準画像に指定され、前記方法が、以下のことを備える、
前記基準画像に隣接する、前記基準画像に位置合わせされていない画像を、選択すること、
前記選択された画像を分析して、前記基準画像に直接位置合わせすることが可能か否かを決定し、当該選択された画像を、前記基準画像に位置合わせすること、
前記基準画像に位置合わせされていない他の画像を選択すること、
前記選択された他の画像を分析して、先に位置合わせされた画像に位置合わせすることが可能か否かを決定し、当該選択された他の画像を前記基準画像に位置合わせすること、
前記選択すること、分析すること、および位置合わせすることを、前記画像のそれぞれが位置合わせされるか、又は位置合わせできないと判断されるまで繰り返すこと。
【請求項１４】
前記他の画像は、当該画像から先に位置合わせされた画像を経由して前記基準画像に至るまでの最短のパスの長さに少なくとも部分的に基づく優先順位でもって選択される、請求項１３に記載の方法。
【請求項１５】
前記最短のパスの長さは、前記最短のパスに沿って経由するところの、先に位置合わせされた画像の数によって評価される、請求項１４に記載の方法。
【請求項１６】
さらに、位置合わせされた画像を、前記基準画像に対して変換する、請求項１５に記載の方法。
【請求項１７】
前記変換を行う際には、位置合わせされた画像のそれぞれを、前記基準画像に対して変換する変換行列が決定される、請求項１６に記載の方法。
【請求項１８】
前記変換行列は、誤差が修正される、請求項１７に記載の方法。
【請求項１９】
画像のセットから合成画像を生成する方法であって、以下のことを備える、
前記セットから基準画像を選択すること、
前記セット内の残りの画像が、前記基準画像又は前記基準画像に対して先に位置合わせされた隣接画像に位置合わせできるか否かを判定して、それらの画像を位置合わせすること、を繰り返し実行すること、
前記位置合わせされた画像を、前記基準画像に対して変換すること。
【請求項２０】
前記判定及び位置合わせは、前記画像の、前記基準画像に対する近接度合いに、少なくとも部分的に基づいて段階的に行われる、請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してイメージ処理に関し、詳細に述べれば、イメージ（画像）のセットからコンポジット・イメージ（合成画像）を生成するための方法および装置に関する。
【背景技術】
【０００２】
静止イメージのセットまたはビデオ・フレームのシーケンス（集合的に『イメージ』）からパノラマまたはコンポジット・イメージを生成することは周知である。このようにして、イメージのセットから複数の異なる時間的な瞬間、視点、視野、および解像度等における同一の物理的なシーンに関連する情報を融合して単一のより広角のイメージを形成する。
【０００３】
コンポジット・イメージを生成するために、種々のイメージが幾何学的に、かつ比色学的に位置合わせされ、整列された後に、互いに併合されるか、あるいは縫い合わされて、単一のコヒーレントなイメージとしてシーンの光景が形成される。位置合わせの間は、各イメージが分析されて、それが先行するイメージと整合できるか否かについて決定される。イメージの間のオフセットを表す変位フィールドが決定され、続いてそのイメージがほかのそのイメージに対してワープされてオフセットが除去もしくは最小化される。
【０００４】
コンポジット・イメージをコヒーレントにするためには、コンポジット・イメージ内のポイントがシーン内のポイントと１対１で対応しなければならない。したがって、イメージがワープされ、結合される表面の上の基準座標系が与えられるとき、当該基準座標系内のポイントと各イメージのピクセルの間の正確な空間マッピングを決定することが必要になる。
【０００５】
コンポジット・イメージを生成するための多くのテクニックが考えられてきた。たとえばフシュー（Ｈｓｕ）ほかの特許文献１は、イメージのセットからコンポジット・イメージを組み立てる方法を開示しており、それにおいては、トポロジ決定モジュールが、空間的にオーバーラップするイメージの部分または『近隣』を識別する。局所的な粗い位置合わせが使用されて、近隣の間における複雑性の低い近似的空間マッピングの評価が行われる。最終的な局所的位置合わせが使用され、近隣の間もしくはイメージとモザイクの現在の評価の間における複雑性のより高いマッピングが評価される。位置合わせプロセスは、それぞれのイメージが別のイメージと位置合わせされるまで、あるいはほかのイメージに対する位置合わせが可能でないソース・イメージだけが整列されずに残るまで反復的に行われる。包括的一貫性モジュールは、すべてのマッピングを同時に最適化することによってすべての基準対イメージのマッピングを、それらがすべての局所的な位置合わせ情報、および選択された基準表面形状（たとえば平面または球面）と最大の一貫性を有するように推論する。イメージが整列された後は、カラー・マッチング／ブレンド・モジュールがそれらのイメージを結合し、コンポジット・イメージを形成する。
【０００６】
バート（Ｂｕｒｔ）ほかの特許文献２は、イメージのセットからコンポジット・イメージを組み立てる方法を開示しており、それにおいては各イメージがいくつかの修正されたイメージに分解される。分解された修正済みイメージは、単方向に敏感なオペレータを使用して分析されて、オリジナルのイメージの情報コンテントの有向基底関数の特性のセットが生成される。その後、コンポジット・イメージ用の有向基底関数が選択されて、コンポジット・イメージが組み立てられる。
【０００７】
ハーマン（Ｈｅｒｍａｎ）ほかの特許文献３は、イメージのセットからコンポジット・イメージを組み立てる方法を開示している。イメージは、イメージのプールから選択される。最初に、これらのイメージが結合されてサブモザイクが形成される。続いてこのサブモザイクが結合されてコンポジット・イメージが形成される。サブモザイクの形成の間に、選択されたイメージが、幾何学的変換または『ワーピング』を決定することによって互いに整列され、それらは、選択されたすべてのイメージに対する適用の後に、それらのイメージを共通座標系に引き入れる。オーバーラップするそれぞれのイメージのペアについて整列誤りが計算される。この整列誤りは、オーバーラップしているエリア内のイメージ強度における差の平方の合計と等しくセットされる。整列誤りが使用されて、イメージ間の整列を調整することを目的とした測度が提供される。整列プロセスは、イメージ間において所望のレベルの整合が達成されるまで反復的に実行することができる。その後、コンポジット・イメージ内における包含のためにオーバーラップしている整列後のイメージの部分領域が選択される。部分領域の選択の間に、近隣イメージの間において、ロケーションを基礎としてマニュアルもしくは自動のいずれかで適切な切断線が見つけ出される。それに代えて、オーバーラップしている領域を平均するか、互いに融合することも可能である。イメージの残りの部分のそれぞれは、その後、強化されてシャープネスもしくはコントラストが改善され、あるいはそれらの特性が近隣イメージと類似となるように何らかのそのほかの方法を用いて調整される。その後、これらのイメージが互いに併合される。併合、フェザリング、多解像度併合、平均、および融合が使用されて、イメージ間の視認可能な継ぎ目が低減される。この生コンポジット・イメージは、その後、望ましければ新しい座標系にワープされる。このプロセスが反復されてサブモザイクがコンポジット・イメージに結合される。
【０００８】
トヨダ（Ｔｏｙｏｄａ）の特許文献４は、各ピクセルに識別データを追加するための中間処理セクション、および各ピクセル用の整合データを生成するための整合データ生成セクションを含むイメージ処理デバイスを開示している。識別データは、各ピクセルが帰属する領域の種類を示す。この識別データは、スキャナから取り込まれた複数のソース・イメージの多値イメージ・データを基礎とする。プロセッサは、接続処理セクションによって識別データ・メモリ内にストアされた各ピクセルの識別データに基づいて各ソース・イメージが帰属する領域の種類を分類する。整合データ・メモリ内にストアされている整合データが、領域の種類に応じて適切に処理された後に比較される。その後プロセッサが、ソース・イメージの整合ポイントを抽出し、抽出した整合ポイントを基準ポイントとして使用してソース・イメージのバイナリ・イメージ・データを接続する。その結果、正確に接続されることによって、そのソース・イメージがピクチャであるか、シャドウまたは背景のイメージであるかによらず、複数のソース・イメージを単一のイメージに復元することが可能になる。
【０００９】
クマール（Ｋｕｍａｒ）ほかの特許文献５は、複数のイメージを生成する３次元シーンのイメージングのためのシステムおよび複数のイメージのイメージ処理を開示している。このイメージ処理は、メモリから、もしくは直接イメージ・ソースから複数のソース・イメージを取り出すこと、それらのイメージをモザイク・イメージに結合すること、そのシーンの新しい視点を選択すること、およびその新しい視点からのシーンの合成イメージのレンダリングを行うことを含む。この合成イメージは、その後、第２のイメージと結合される。第２のイメージとこの合成イメージの結合は、それら２つのイメージのリアルな結合を含むコンポジット・イメージを生成する。
【００１０】
カトラー（Ｃｕｔｌｅｒ）の特許文献６は、ディジタル全方向カメラの較正方法、およびイメージを互いにコンポジット・イメージに縫い合わせるコンテキスト特有の方法を開示している。イメージのそれぞれは、ラジアルひずみについて訂正される。続いて各イメージは、円柱座標系にマップされる。その後、平行移動、変倍、および回転がその後使用されて、各イメージが近隣イメージと整列される。その後、オーバーラップしている領域のブレンドによって、あるいはコンテキストに敏感な縫い合わせによってこれらのイメージがコンポジット・イメージに縫い合わされる。
【００１１】
シェフナー（Ｓｃｈｅｃｈｎｅｒ）ほかの特許文献７は、解像度の増強されたデータを生成する方法を開示している。ターゲットの異なる部分のイメージを取り込むためにカメラが回転される。カメラは、カメラの視角全体にわたって非一様なイメージング感度特性を有することができる。このイメージング感度特性は、露出、感色性、偏光感度、焦点距離、およびそのほかのイメージ検出の側面を含むことができる。カメラがイメージ取り込みの間に平行移動されることから、ターゲットの各部分が、カメラの感度プロファイルの複数の部分によって取り込まれる。
【００１２】
ネイルソン（Ｎｅｉｌｓｏｎ）の特許文献８は、複数のカメラを使用してコンポジット・イメージを組み立てる方法を開示している。イメージ内の対応するポイントが、投影平面上に投影された光ビーム・ベクトルの間の誤差を基礎とし、それらの対応するポイントにおけるピクセル値の間の比較を実行することなくサーチされる。オリジナルの拾い上げられたイメージは、光ビーム・ベクトルの間における誤差を基礎として出力コンポジット・イメージに直接貼り付けられ、コンポジット・イメージ内に一度貼り付けられた後のあらゆるイメージの変換を伴わないことから、ピクセルの劣化が抑圧される。
【００１３】
アーマド（Ａｈｍｅｄ）ほかの特許文献９は、コンポジット・イメージを組み立てる方法およびそれに対してイメージの強化を実行する方法を開示している。イメージは、イメージング・エレメントのセットを使用して獲得される。イメージング・エレメントのいくつかは、オーバーラップしているか回転された視野を有する。これらのイメージは、結合されてコンポジット・イメージが組み立てられる。コンポジット・イメージの組み立ての間に、イメージのオーバーラップしている領域から特徴が抽出されてマッチングが行われる。これらの特徴は、エッジとすることができる。それに代えて、イメージ・マッチングおよびロケーション・テクニックを介し、より大きなイメージに関して各イメージの位置決めを行うことによって再結合を行うことができる。
【００１４】
ミラー（Ｍｉｌｌｅｒ）ほかの特許文献１０は、複数の時間的に連続する高解像度イメージから高解像度コンポジット・イメージを組み立てる方法を開示している。時間的に連続する高解像度イメージから低解像度イメージが生成される。その後、低解像度イメージからのピクセルが結合されて、高解像度コンポジット・イメージが組み立てられる。
【特許文献１】米国特許第６，０７８，７０１号
【特許文献２】米国特許第５，３２５，４４９号
【特許文献３】米国特許第６，０７５，９０５号
【特許文献４】米国特許第６，３８１，３７６号
【特許文献５】米国特許第６，５２２，７８７号
【特許文献６】米国特許出願公開第２００３／０２３４８６６号
【特許文献７】米国特許出願公開第２００４／００５６９６６号
【特許文献８】米国特許出願公開第２００４／００７６３４０号
【特許文献９】米国特許出願公開第２００４／０１６９８７０号
【特許文献１０】米国特許出願公開第２００４／０１７５０５５号
【発明の開示】
【発明が解決しようとする課題】
【００１５】
上記の文献はコンポジット・イメージを生成する方法を開示しているが、その種のコンポジット・イメージの生成を向上させる必要がある。したがって、本発明は、イメージのセットからコンポジット・イメージを生成するための新しい方法および装置を提供することをその目的とする。
【課題を解決するための手段】
【００１６】
したがって１つの側面においては、画像のセットから合成画像を生成する方法が提供され、当該方法は、以下のことを備える、
前記セットから基準画像を選択すること、
前記セットにおける残りの画像を、前記基準画像に対して、直接、又は先に位置合わせされた中間画像を介して、位置合わせすること、ここで、先に位置合わせされた中間画像を介した画像の位置合わせは、該画像から先に位置合わせされた中間画像を経由して前記基準画像に至るまでの最短のパスの長さに、少なくとも部分的に基づいて行われる、
位置合わせされた画像を、前記基準画像に対して配置して、前記合成画像を生成すること。
【００１７】
一実施態様においては、前記最短のパスの長さは、前記最短のパスに沿って経由する画像の数によって評価される。前記残りの画像は、サイクル的に、位置合わせのために選択される。各サイクルにおいて、画像が、段階的に、位置合わせのために選択される。初期位置合わせサイクルの第１段階において、水平または垂直のパスに沿って前記基準画像に隣接する画像が選択され、前記基準画像に対して位置合わせされる。前記初期位置合わせサイクルに続く各段階Ｓにおいては、水平要素及び垂直要素のみを含む位置合わせパスに沿った、Ｓ−１個の位置合わせされた画像によって前記基準画像から分離されている画像が選択され、且つ位置合わせされる。  前記初期位置合わせサイクルの完了時に、位置合わせされていない画像が存在するときには、追加の位置合わせサイクルが実行され、前記位置合わせされていない画像を、隣接する先に位置合わせされた画像に位置合わせする。前記追加の位置合わせサイクルは、前記位置合わせされていない画像のそれぞれが位置合わせされるか、位置合わせできないと判断されるまで実行される。
【００１８】
別の側面によれば、画像のセットから合成画像を生成する方法が提供され、前記セット内の画像の１つが基準画像に指定され、前記方法が、以下のことを備える、
前記基準画像に隣接する、前記基準画像に位置合わせされていない画像を、選択すること、
前記選択された画像を分析して、前記基準画像に直接位置合わせすることが可能か否かを決定し、当該選択された画像を、前記基準画像に位置合わせすること、
前記基準画像に位置合わせされていない他の画像を選択すること、
前記選択された他の画像を分析して、先に位置合わせされた画像に位置合わせすることが可能か否かを決定し、当該選択された他の画像を前記基準画像に位置合わせすること、
前記選択すること、分析すること、および位置合わせすることを、前記画像のそれぞれが位置合わせされるか、又は位置合わせできないと判断されるまで繰り返すこと。
【００１９】
さらに別の側面によれば、画像のセットから合成画像を生成する方法が提供され、当該方法は、以下のことを備える、
前記セットから基準画像を選択すること、
前記セット内の残りの画像が、前記基準画像又は前記基準画像に対して先に位置合わせされた隣接画像に位置合わせできるか否かを判定して、それらの画像を位置合わせすること、を繰り返し実行すること、
前記位置合わせされた画像を、前記基準画像に対して変換すること。
【００２０】
さらに別の側面によれば、イメージのセットからコンポジット・イメージを生成するための装置が提供され、当該装置は：
前記セットから基準イメージを選択し、前記基準イメージに対して前記セット内の残りのイメージを直接、もしくは先行して位置合わせ済みの中間イメージを介して位置合わせするレジストラであって、それにおいて先行して位置合わせ済みの中間イメージを介したイメージの位置合わせが、前記イメージから前記先行して位置合わせ済みの中間イメージを通って前記基準イメージに至る最短パスの長さを少なくとも部分的に基礎とするレジストラ；および、
前記基準イメージに対して位置合わせ済みのイメージをマッピングし、それによって前記コンポジット・イメージを生成するイメージ変換器；
を包含する。
【００２１】
さらに別の側面によれば、イメージのセットからコンポジット・イメージを生成するための装置が提供され、それにおいては前記セット内のイメージの１つが基準イメージに指定され、前記方法が：
前記基準イメージに隣接する、前記基準イメージとの位置合わせが未済のイメージを選択するための手段；
前記選択されたイメージを前記基準イメージに直接位置合わせすることが可能か否かを決定するべくそれらの選択されたイメージを分析するため、およびそれらの選択されたイメージを前記基準イメージに位置合わせするための手段；
前記基準イメージとの位置合わせが未済のほかのイメージを選択するための手段；
前記選択されたほかのイメージを先行して位置合わせ済みのイメージに位置合わせすることが可能か否かを決定するべくそれらの選択されたほかのイメージを分析するため、およびそれらの選択されたほかのイメージを前記基準イメージに位置合わせするための手段；および、
これらの選択、分析、および位置合わせを、前記イメージのそれぞれが位置合わせされるか、位置合わせ不能と判断されるまで反復するための手段；
を包含する。
【００２２】
さらに別の側面によれば、イメージのセットからコンポジット・イメージを生成するためのコンピュータ・プログラムを具体化したコンピュータ可読メディアが提供され、前記コンピュータ・プログラムは：
前記セットから基準イメージを選択するためのコンピュータ・プログラム・コード；
前記基準イメージに対して前記セット内の残りのイメージを直接、もしくは先行して位置合わせ済みの中間イメージを介して位置合わせするための、先行して位置合わせ済みの中間イメージを介したイメージの位置合わせが、前記イメージから前記先行して位置合わせ済みの中間イメージを通って前記基準イメージに至る最短パスの長さを少なくとも部分的に基礎とするコンピュータ・プログラム・コード；および、
前記基準イメージに対して位置合わせ済みのイメージをマッピングし、それによって前記コンポジット・イメージを生成するためのコンピュータ・プログラム・コード；
を包含する。
【００２３】
さらに別の側面によれば、イメージのセットからコンポジット・イメージを生成するためのコンピュータ・プログラムを具体化したコンピュータ可読メディアが提供され、前記コンピュータ・プログラムは：
前記セットから基準イメージを選択するためのコンピュータ・プログラム・コード；
前記セット内のほかのイメージが前記基準イメージ、もしくは前記基準イメージに対して先行して位置合わせ済みの隣接イメージに位置合わせすることが可能か否かを反復的に決定するため、およびそれらのイメージを位置合わせするためのコンピュータ・プログラム・コード；および、
位置合わせ済みのイメージを基準イメージに対して変換するためのコンピュータ・プログラム・コード；
を包含する。
【００２４】
位置合わせ未済のイメージの位置合わせを、先行して位置合わせ済みの中間イメージを経由してその位置合わせ未済のイメージから基準イメージに至る最短パスの長さを少なくとも部分的に基礎とする優先度において反復的に試みることによって、位置合わせパスを縮小することが可能になる。
【００２５】
以下、添付図面を参照して実施態様をより完全に説明する。
【発明を実施するための最良の形態】
【００２６】
以下の説明においては、イメージのセットからコンポジット・イメージを生成するための方法および装置の実施態様が提供されている。この方法の間に、セットから基準イメージが選択される。セット内の残りのイメージは、この基準イメージに対して、直接もしくは先行して位置合わせ済みの中間イメージを介して位置合わせされる。先行して位置合わせ済みの中間イメージを介した位置合わせは、先行して位置合わせ済みの中間イメージを介してそのイメージから基準イメージに至る最短パスの長さを少なくとも部分的に基礎とする。位置合わせされたイメージは、その後、基準イメージに対してマッピングされ、それによってコンポジット・イメージが生成される。
【００２７】
図１は、結合してコンポジット・イメージを生成することのできる一例のイメージのセットを例示している。この例においては、これらのイメージが家の異なる部分であり、各隣接ペアが共通イメージ・エリアを共有しており、言い換えるとそれらがオーバーラップしている。イメージを互いに整列させ、その後それらを互いに縫い合わせることによって、家全体のコンポジット・イメージを生成することが可能になる。
【００２８】
ここで図２を参照すると、イメージのセットからコンポジット・イメージを生成するためのコンピューティング・デバイス２０が示されている。これからわかるとおり、コンピューティング・デバイス２０は、処理ユニット２４、ランダム・アクセス・メモリ（『ＲＡＭ』）２８、不揮発性メモリ３２、入力インターフェース３６、出力インターフェース４０、およびネットワーク・インターフェース４４を包含しており、それらすべてはローカル・バス４８を介して通信する。処理ユニット２４は、不揮発性メモリ３２から、コンポジット・イメージを生成するためのコンポジット・イメージ生成アプリケーションをＲＡＭ  ２８内に取り出す。不揮発性メモリ３２は、コンポジット・イメージが生成されることになるイメージをストアすること、および生成されたコンポジット・イメージ自体をストアすることが可能である。入力インターフェース３６は、キーボードおよびマウスを含み、またイメージを受け取るための通信またはビデオ・インターフェースも含むことができる。出力インターフェース４０は、コンピューティング・デバイス２０のユーザに対して情報を呈示し、コンポジット・イメージ生成アプリケーションとのインタラクションを可能にするためのディスプレイを含むことができる。ネットワーク・インターフェース４４は、コンピューティング・デバイス２０が結合されている通信ネットワークを介してビデオ・フレームおよびコンポジット・イメージが送信され、受信されることを可能にする。
【００２９】
図３は、ｍ行ｎ列の配列で整えられたイメージのセットからコンポジット・イメージを生成する方法１００の概要を例示している。最初に、配列内のイメージがグレイスケールに変換され、そのグレイスケール・イメージが試験され、コーナ検出アルゴリズムの使用によってコーナが検出される（ステップ１１０）。コーナは、輪郭に沿った、少なくともあらかじめ決定済みの角度を伴う方向の変化として定義される。各イメージ内のコーナが検出された後、このイメージのセットから基準イメージが選択される（ステップ１２０）。この例においては、配列のもっとも中心にあるイメージが基準イメージとして自動的に選択される。これは、基準イメージと配列内のそのほかのイメージとの間の最大距離を短縮するために行われる。
【００３０】
基準イメージが選択されると、基準イメージに対する配列内のほかのすべてのイメージの位置合わせを試みる初期位置合わせサイクルが実行される（ステップ１３０）。セット内のイメージが行および列に整えられていることから、それらは基準イメージの周りに同心リングを形成する。初期位置合わせの間に、基準イメージを取り囲むイメージが、それらのイメージが配置されているリング、および垂直もしくは水平ステップまたはパスで表される基準イメージからのそれらのイメージの距離に従って、一連の段階の中で選択される。最初に、位置合わせサイクルの第１段階において、最初のリング、つまり基準イメージにもっとも近いリング内の、基準イメージの上、下、および両側のイメージ、すなわち基準イメージから水平または垂直ステップが１つのイメージが選択され、基準イメージに対するそれらのイメージの位置合わせが試行される。次に、初期位置合わせサイクルの第２段階において、最初のリング内の、基準イメージから水平または垂直ステップが２つのイメージが選択され、基準イメージに対するそれらのイメージの位置合わせが試行される。最初のリング内のイメージの処理が完了すると、セットの残りのリング内のイメージが、それらが存在すれば、その後に続く段階において類似の態様で処理され、先行して位置合わせ済みの隣接するイメージに対するそれらのイメージの合わせが試行され、その後、この初期位置合わせサイクルが完了する。初期位置合わせサイクルの完了に続いてチェックが行われ、基準イメージに対する位置合わせが未済のイメージが残っているか否かについて決定される。そのような位置合わせ未済のイメージが存在するときには、基準イメージに対してそれらのイメージの位置合わせを試みる追加の位置合わせサイクルが行われる。この追加の位置合わせサイクルは、それらの位置合わせ未済の各イメージが、先行して位置合わせ済みの隣接するイメージに位置合わせされるか、あるいは位置合わせ不能と判断されるまで続けられる。
【００３１】
図４は、初期位置合わせの第１段階を図１のイメージのセットについて例示している。この例において、イメージＩ５がセット内の中心に配置されたイメージであることから、それが基準イメージになる。初期位置合わせサイクルの第１段階の間に、基準イメージＩ５の上、下、左、および右に隣接する４つのイメージＩ２、Ｉ８、Ｉ４、Ｉ６が基準イメージＩ５を取り囲むイメージの第１のリング内であり、かつ基準イメージから垂直または水平のいずれかに１ステップであることから、それらが基準イメージとの位置合わせのために選択される。
【００３２】
セットからイメージの第１のシリーズが選択されると、基準イメージＩ５に対する選択されたイメージのそれぞれの位置合わせが試みられる。図５は、隣接するイメージのペアを位置合わせするときに行われるステップを示している。最初に、局所的近隣が相互相関されて、隣接するイメージ内のコーナの整合が行われる（ステップ２１０）。整合スコアは、各コーナの近隣内のシフトおよび回転の整合性を決定することによって計算される（ステップ２２０）。次に、１対１で整合しないコーナが、整合の制約を緩和することによって、あいまい性が除かれる（ステップ２３０）。隣接イメージ間における変換は、あらかじめ定義済みの回数にわたって評価され、結果として得られるイメージ当て嵌めが計算される（ステップ２４０）。それぞれの変換を評価するために、これらのイメージから４ペアのコーナがランダムに選択されて、８つの線形方程式のセットの解決に使用される。続いて評価済みの各変換が、イメージ内のすべての整合しているコーナのペアに適用され、類似の変換をもたらすイメージ内のコーナのペアの数が決定されて、それによってイメージ当て嵌めが決定される。最良当て嵌めをもたらす評価済みの変換が次に選択され（ステップ２５０）、選択された変換が洗練される（ステップ２６０）。その洗練を行う間、選択された変換によって支持されるイメージ内のほかの整合コーナが結合されて、制約過多線形方程式のセットが形成される。その後、これらの線形方程式が解決されて、選択された変換が洗練される。
【００３３】
上記の位置合わせサイクルの第１段階の間に、第１のシリーズのイメージのうちの１ないしは複数が、基準イメージと直接位置合わせできないということがあり得る。選択された変換を支持するコーナの数があらかじめ定義済みの値より小さいときには、イメージが位置合わせ不能と判断される。
【００３４】
位置合わせサイクルの第１段階が完了すると、位置合わせサイクルの第２段階が実行される。この場合、第１のリング内の残りの、基準イメージから垂直または水平のステップが２つのイメージが選択される。図６は、図１のイメージのセットについての位置合わせの第２段階の間におけるイメージの選択を例示している。この段階の間に、選択された各イメージを、１つの中間イメージを介し、等しい長さの２つの位置合わせパスに沿って基準イメージにマップすることができる。たとえば、イメージＩ１に注目すると、このイメージは、イメージＩ２またはイメージＩ４を通って基準イメージにマップすることが可能である；すなわち：
１→２→５；および
１→４→５である。
これらのイメージが選択された後、中間イメージが基準イメージに対して首尾よく位置合わせされていることを前提すれば、それぞれの選択されたイメージが、選択されたイメージを基準イメージにマップする中間イメージに対して同時に位置合わせされる。両方の中間イメージを用いる、それぞれの選択されたイメージの位置合わせは、そのイメージと基準イメージの間における最短位置合わせパスの決定を可能にする。
【００３５】
図７は、位置合わせサイクルの第２の段階の間に選択されるイメージを、先行して位置合わせ済みの２つの中間イメージに対して同時に位置合わせするために行われるステップを示している。参照を容易にするため、中間イメージＩ２およびＩ４を用いるイメージＩ１の位置合わせについて説明する。しかしながら当業者であれば認識することになろうが、この考察は、位置合わせサイクルの第２段階の間に選択されるほかのイメージに対しても同等に適用される。この方法の間においては、イメージＩ１およびＩ２内のコーナのための整合ポイント・リストＱ１が、当初、空にセットされる（ステップ３１０）。イメージＩ１およびＩ４内のコーナのための整合ポイント・リストＱ２もまた空にセットされる（ステップ３２０）。続いてイメージＩ１とＩ２がペア態様で互いに位置合わせ可能か否かについて決定される（ステップ３３０）。イメージＩ１とＩ２の位置合わせは、図５を参照して上に述べた態様で実行される。イメージＩ１とＩ２がペア態様で互いに位置合わせ可能な場合には、イメージＩ１とＩ２の間の整合ポイントが使用されて、リストＱ１内が埋められる（ステップ３４０）。その後、イメージＩ１とＩ４がペア態様で互いに位置合わせ可能か否かについて決定される（ステップ３５０）。この場合においても、イメージＩ１とＩ４の位置合わせが図５を参照して前述した態様で実行される。イメージＩ１とＩ４がペア態様で互いに位置合わせ可能な場合には、イメージＩ１とＩ４の間の整合ポイントが使用されて、リストＱ２内が埋められる（ステップ３６０）。これらの整合ポイント・リストＱ１およびＱ２は、その後、制約過多線形方程式のセットを設定し、解決することによって結合され、それによってイメージＩ１についての位置合わせ情報がもたらされる（ステップ３７０）。イメージＩ１を、すでに基準イメージに対して首尾よく位置合わせされている２つの近隣イメージに対して位置合わせすることによって、イメージＩ１の、隣接イメージと相対的なポジションに関する追加の情報が獲得され、それが整列誤りの回避を補助する。
【００３６】
基準イメージに対するイメージの位置合わせが段階的に実行されることから、イメージの間の位置合わせ情報を示す位置合わせグラフを組み立てることが可能である。位置合わせグラフは、コンポジット・イメージのダイレクト・グラフであり、それにおいては各イメージがグラフ内のノードによって表現され、イメージの隣接するエッジがノードを結合するリンクによって表現される。
【００３７】
図８Ａ〜８Ｄは、初期位置合わせサイクルの種々の段階の間における一例の位置合わせグラフを図１のセットのイメージについて示している。詳細に述べれば、図８Ａは、初期位置合わせサイクルの第１段階の後の位置合わせグラフを例示している。この例においては、イメージＩ２およびＩ８が基準イメージＩ５に対して位置合わせされている。この位置合わせグラフは、イメージＩ４およびＩ６が基準イメージＩ５に対する位置合わせに成功しなかったことも示している。
【００３８】
図８Ｂは、初期位置合わせサイクルの第２段階の完了後の位置合わせグラフを例示している。これから理解されるとおり、この位置合わせグラフは、イメージＩ１およびＩ３が、すでに位置合わせされているイメージＩ２だけに対して首尾よく位置合わせされたことを示している。同様にこの位置合わせグラフは、イメージＩ７が、すでに位置合わせされているイメージＩ８だけに対して首尾よく位置合わせされたことも示している。イメージＩ９は、基準イメージＩ５に対して位置合わせされている唯一の近隣であるイメージＩ８に対して位置合わせ不能であるとして示されている。ここで気付くことになろうが、イメージＩ４が基準イメージＩ５に対して先行して位置合わせ済みのイメージでなかったことから、イメージＩ４に対してイメージＩ１およびＩ７の位置合わせが試みられていない。同様にイメージＩ６が基準イメージＩ５に対して先行して位置合わせ済みのイメージでなかったことから、イメージＩ６に対するイメージＩ３およびＩ９の位置合わせが試みられていない。
【００３９】
上記の例から気付くとおり、初期位置合わせサイクルの第１および第２段階の完了後に、リング内のすべてのイメージが、基準イメージもしくは先行して位置合わせ済みのイメージに対して首尾よく位置合わせされるわけではない。その場合には、追加の位置合わせサイクルが実行されて、基準イメージに対して首尾よく位置合わせされたイメージに対する位置合わせ未済のイメージの位置合わせが試みられる。これらの追加の位置合わせサイクルの間に、位置合わせ未済のイメージが、最短の位置合わせパスを通って、すなわち水平および垂直のステップ数が最小のパスを通って基準イメージに対してその位置合わせ未済のイメージをマップする先行して位置合わせ済みのイメージに対して位置合わせされると望ましい。
【００４０】
ステップ１４０の追加の位置合わせサイクルの間に、初期位置合わせサイクルの間に位置合わせされなかった各イメージが、初期位置合わせサイクルの間に使用された順序と同じ順序で分析される。言い換えると、それぞれの追加の位置合わせサイクルの間に、残存している位置合わせ未済のイメージが、それらの位置合わせ未済のイメージが配置されているリング、および垂直もしくは水平ステップのいずれかにおいて表される基準イメージからのそれらの位置合わせ未済のイメージの距離に従って、一連の段階の中で分析される。この順序は、それらの位置合わせ未済のイメージから先行して位置合わせ済みのイメージを通って基準イメージに至る最短パスの長さを少なくとも部分的に基礎としている。このようにして、先行して位置合わせ済みのイメージに対して首尾よく位置合わせされた、より基準イメージに近い位置合わせ未済のイメージは、より遠いほかの位置合わせ未済のイメージのための位置合わせパスの一部を潜在的に形成することが可能である。さらに、特定の長さのすべての潜在的な位置合わせパスが、比較的長い位置合わせパスに沿ってイメージの位置合わせを試みる前に調査される。その結果として、それぞれのイメージについて決定された位置合わせパスが最短可能パスとなる。
【００４１】
フロイド・ウォーシャル全ペア最短パス・アルゴリズムが使用されて、位置合わせグラフ内の位置合わせ未済の各イメージと基準イメージの間の最短位置合わせパスが決定される。２つのイメージの間の位置合わせを表すノード間の各リンクには、１のコストが割り当てられ、互いに位置合わせができなかったイメージのペアを表すノード間のリンクには、それらの使用を実質的に防止するために大きな値のコストが割り当てられる。２つのノードｖとｗの間のリンクは（ｖ，ｗ）によって表され、そのリンクのコストは、Ｃ［ｖ，ｗ］によって表される。
【００４２】
フロイド・ウォーシャルのアルゴリズムは、出力として２つの行列、すなわちノードｖからノードｗに至る最低コスト位置合わせパスのコストを含む距離行列Ｄ［ｖ，ｗ］、およびＤ［ｖ，ｗ］内にストアされているコストに導いたｖとｗの間の最小コスト位置合わせパス上の中間ノードｋを識別するパス行列Ｐ［ｖ，ｗ］を生成する。当初は、Ｄ［ｖ，ｗ］＝Ｃ［ｖ，ｗ］である。ｋをインデクスとして使用し、行列Ｄの上でＮ回の反復が行われる。ｋ番目の反復において、行列Ｄが最短位置合わせパス問題に対する解を提供し、それにおいては位置合わせパスが１．．．ｋの番号が振られたノードだけを使用する。次の繰り返しにおいては、１．．．ｋの番号が振られたノード（ｋ番目の反復時にＤ［ｉ，ｊ］にストアされる）だけを使用するｉからｊに至る位置合わせパスのコストが、中間ステップとして（ｋ＋１）番目のノードを使用するコストを用いて計算され、それは、Ｄ［ｉ，ｋ＋１］（ｉからｋ＋１に至るまで）にＤ［ｋ＋１，ｊ］（ｋ＋１からｊに至るまで）を加えたものとなる。この結果が、よりコストの低い位置合わせパスをもたらすときには、それが記録される。Ｎ回の反復の後、必要であればすべてのノードを使用するｖからｗに至る最低コスト位置合わせパスのコストを含むＤ［ｖ，ｗ］を用いてすべての可能位置合わせパスが調べられる。
【００４３】
ノードｕおよびｖの各ペアのための行列Ｐは、ｕからｖに至る最小コスト位置合わせパス上の中間ノードを含む。このｕからｖに至る最小コスト位置合わせパスは、ｕからＰ［ｕ，ｖ］に至る最小コスト位置合わせパス、およびそれに続くＰ［ｕ，ｖ］からｖに至る最小コスト位置合わせパスである。
【００４４】
位置合わせ未済のイメージのための最短位置合わせパスが、その位置合わせパスに沿った隣接イメージとともに決定された後、その位置合わせ未済のイメージとその隣接イメージの間における位置合わせが、図５を参照して説明を前述した態様で試みられる。位置合わせに成功すると、位置合わせグラフが更新されて、適切なリンクが含められる。すべてのイメージが首尾よく位置合わせされるか、あるいは位置合わせ未済のイメージを、隣接する先行して位置合わせ済みのイメージ、すなわち中間イメージを通って基準イメージにマップされているイメージに位置合わせする方法がなくなるまで追加の位置合わせサイクルが実行される。
【００４５】
図８Ｃは、第１の追加の位置合わせサイクルの第１段階の完了後における図８Ｂの位置合わせグラフを示している。イメージＩ４は、基準イメージＩ５に直接位置合わせが可能でないが、この位置合わせグラフは、イメージＩ４がイメージＩ１に位置合わせされ、続いてそれが中間イメージＩ２を通って基準イメージＩ５にマップされることを示している。同様にイメージＩ６は、基準イメージＩ５に直接位置合わせが可能でないが、位置合わせグラフは、イメージＩ６がイメージＩ３に位置合わせされ、続いてそれが中間イメージＩ２を通って基準イメージＩ５にマップされることを示している。ここで認識されることになろうが、この位置合わせ段階の開始時においては、イメージＩ９が位置合わせ済みのイメージと隣接してなく、したがって位置合わせが可能でない。
【００４６】
図８Ｄは、第１の追加の位置合わせサイクルの第２段階の完了後における位置合わせグラフを示している。イメージＩ６が第１の追加の位置合わせサイクルの第１段階の間に位置合わせされたことから、すなわち先行して位置合わせ済みのイメージであることから、それまで位置合わせ未済であったイメージＩ９をイメージＩ６に位置合わせすることが可能となり、この位置合わせグラフに示されているとおりに位置合わせされる。イメージＩ９の位置合わせにより、イメージのすべてが基準イメージＩ５と位置合わせされ、変換のための準備が整う。
【００４７】
上に示した例においては、位置合わせ未済のイメージが残らないことから、追加の位置合わせサイクルが１つだけ行われ、位置合わせプロセスが完了する。位置合わせ未済のイメージが残った場合には、第１の追加の位置合わせサイクルの実行後に、追加の位置合わせサイクルが、すべてのイメージが位置合わせされるか、最後に実行される位置合わせサイクルの間に追加のイメージが位置合わせされず、残りの位置合わせ未済のイメージを隣接する先行して位置合わせ済みのイメージに対して位置合わせできないことが示されるまで実行される。
【００４８】
各イメージと基準イメージの間の最短位置合わせパスが決定されると、基準イメージに対して各イメージを変換する変換行列が決定される。この変換行列は、イメージの、初期ポジションから基準イメージに関するそれらのポジション（すなわち、絶対ポジション）への変換を表す。特定のイメージのための変換行列は、そのイメージから基準イメージに至る最短位置合わせパスに沿った位置合わせ済みのイメージの間の各リンクのための変換行列の積に等しい。
【００４９】
ここで図９を参照すると、位置合わせ済みのイメージの変換の間に実行されるステップが示されている。最初に、基準イメージに対して直接位置合わせされているイメージが、決定済みの変換を使用して変換される（ステップ４１０）。続いて、変換が行われていない位置合わせ済みのイメージが残っているか否かの決定がなされる（ステップ４２０）。まだ変換されていない位置合わせ済みのイメージが存在するときには、位置合わせ済みのイメージが選択され、変換されて、共通コーナが先行して変換の済んでいるイメージと整列される（ステップ４３０）。これが、すべての位置合わせ済みのイメージが変換されるまで反復される。
【００５０】
図１０は、基準イメージＩ５に関するイメージＩ１およびＩ２の変換について図９の方法を例示している。図１のイメージの位置合わせの間に、イメージＩ２が基準イメージＩ５に直接位置合わせされ、イメージＩ１が、先行して位置合わせ済みの中間イメージＩ２を介して基準イメージＩ５に対して位置合わせされる。言い換えると、イメージＩ１から基準イメージＩ５に至る最短位置合わせパスが次のとおりに決定されている。
１→２→５
【００５１】
イメージＩ２が基準イメージＩ５に対して直接位置合わせ可能であることから、ステップ４１０の間にそれの変換が行われる。イメージＩ２は、位置合わせの間に決定された変換に従って基準イメージＩ５内のポイントＳとして解釈される第１のポイントＲを有することが示されている。しかしながらイメージＩ１は、先行して位置合わせ済みの中間イメージＩ２を経由して基準イメージＩ５に位置合わせされる。イメージＩ１からイメージＩ５に至る変換のための変換行列Ｍ［１］［５］は、イメージＩ１をイメージＩ２に対して、さらにその後にイメージＩ５に対して変換するための変換行列の積である。すなわち、次のとおりとなる。
Ｍ［１］［５］＝Ｍ［２］［５］×Ｍ［１］［２］      （１）
これらの行列Ｍ［２］［５］およびＭ［１］［２］のそれぞれは、イメージＩ２とイメージＩ５の位置合わせ、およびイメージＩ１とイメージＩ２の位置合わせの決定の間に導出される。
【００５２】
基準イメージに至る位置合わせパスに沿った行列の乗算によって獲得された変換行列は正確でないこともある。いくつかの場合において、各ペアの間の変換行列内に非常に小さい誤差が存在する。したがって：
2007048290.tif 000003
となるが、これにおいて
2007048290.tif 000004
は正しい変換行列であり、Ｍ［２］［５］およびＭ［１］［２］は、イメージＩ２とＩ５、およびイメージＩ１とＩ２それぞれの間において評価された変換行列である。したがって、Ｍδ１５、Ｍδ２５、およびＭδ１２は、対応する誤差行列である。
【００５３】
式１にこれらの値を代入することによって、累積変換が次のように決定される：
2007048290.tif 000005
正しい累積変換行列が、個別の正しい行列の積であることから、すなわち：
2007048290.tif 000006
であることから次式を得る：
2007048290.tif 000007
【００５４】
行列乗算の結果として、累積誤差Ｍδ１５が累積されて増幅されることがあり得る。この累積誤差は、乗算シーケンスがより長くなるとき（つまり位置合わせパスがより長くなるときに該当する）さらに大きくなる。最短位置合わせパスを決定することによって、この累積誤差の効果を縮小することができる。しかしながら、多数のイメージの列および／または行が存在する場合には、累積誤差が有意に大きくなり得る。
【００５５】
ステップ４３０における位置合わせ済みのイメージの変換の間に累積誤差の効果を縮小するために、位置合わせ済みのイメージから基準イメージに至る位置合わせパスに沿った整合ポイントのリストがリマップされる。図１０に示されている例において、イメージＩ１が、先行して位置合わせ済みのイメージＩ２に関して位置合わせされ、またそれが基準イメージＩ５に関して位置合わせされる。イメージＩ１内のポイントＰは、イメージＩ２内のポイントＱに対応し、イメージＩ２内のポイントＲは基準イメージＩ５内のポイントＳに対応する。
【００５６】
イメージＩ１とＩ２の間における変換行列Ｍ［１］［２］、およびイメージＩ２とＩ５の間における変換行列Ｍ［２］［５］は、対応する整合ポイント・リストを解決することによって評価される。Ｍ［２］［５］を使用して基準イメージに対して変換された後のポイントＱに対応するポイントＱ＊は計算することが可能である。Ｍ［２］［５］×Ｍ［１］［２］を使用して基準イメージに対して変換された後のポイントＰに対応するポイントＰ＊もまた計算することが可能である。ポイントＰ＊およびＱ＊は、基準イメージＩ５の内側もしくは外側のロケーションとして解釈できる。
【００５７】
理論上はＰ＊がＱ＊と同じポイントに配置される必要がある。しかしながら、一般的な場合にはそのようにならない。Ｑ＊はＭ［２］［５］から計算されるが、Ｐ＊はＭ［２］［５］×Ｍ［１］［２］を使用して計算されることから、Ｐ＊とＱ＊が異なる。前述したとおり、累積誤差は、１ないしは複数の行列の乗算の結果として生じ得る。その結果、Ｑ＊は、Ｐ＊より正確になり得る。変換行列Ｍ［１］［５］は、イメージＩ１のオーバーラップしている部分内のコーナと、イメージＩ２から解釈された対応するコーナの間の変換を決定することによって
2007048290.tif 000008
に訂正することが可能であり、それによって、複数の個別の変換を使用して決定されたＭ［１］［５］内に存在する追加の誤差がキャンセルされる。この訂正が、３もしくはそれを超える数のイメージを含むすべての位置合わせパスについて反復される。
【００５８】
ここで例示を目的として、イメージＩ１からイメージＩ２に、さらにいくつかを経てイメージＩＮに至り、イメージＩ１がイメージＩＮに整列されるとする。ＰｉおよびＰｊは、それぞれイメージＩｉおよびＩｊの整合ポイントの座標である。変換行列Ｍ［１］［Ｎ］を調整し、次のアプローチを使用することによって累積誤差の影響を軽減することができる：
ステップ１：  ｉ←Ｎ−２，ｊ←ｉ＋１
ステップ２：  Ｐｊ’←Ｍ［ｊ］［Ｎ］Ｐｊ
ステップ３：  Ｍ［ｉ］［Ｎ］Ｐｉ＝Ｐｊ’を解き、Ｍ［ｉ］［Ｎ］を求める
ステップ４：  ｉ←ｉ−１，ｊ←ｉ＋１
ステップ５：  ｉ≧１であればステップ２に戻る
ステップ６：  エンド
【００５９】
ステップ２の間においては、基準イメージＩＮに関してＰｊが変換される。ステップ３の間においては、基準イメージＩＮに対してイメージＩｉを変換する変換Ｍ［ｉ］［Ｎ］が、Ｐｊの変換済みのポジションに対するポイントＰｉの変換に必要な変換に等しく再決定される。詳細に述べれば、線形方程式のセットを解くことによってＭ［ｉ］［Ｎ］が決定される。ステップ２〜４は、ｉが１に達するまで反復され、その時点においてＭ［１］［Ｎ］が決定される。
【００６０】
基準イメージに対する整列および累積誤差の訂正が済むと、基準イメージに関して首尾よく位置合わせされたすべてのイメージのポジションが既知となり、各位置合わせ済みのイメージのための、基準イメージに対するそれらのイメージの変換またはマップを行う評価済み変換行列が結果として得られる。
【００６１】
図１１は、図１のイメージから生成されるコンポジット・イメージの一例を示しており、それにおいては各イメージが基準イメージに関する絶対ポジションに変換されている。ここで理解することになろうが、多くの場合に個別のイメージは、コンポジット・イメージに組み立てられたときに互いからオフセットされることがある。
【００６２】
上記の考察は、基準イメージを取り囲む単一のイメージのリングを含むイメージのセットに言及しているが、当業者であれば基準イメージを取り囲む複数のイメージのリングを含むイメージを使用してコンポジット・イメージを形成できることに気付くことになろう。位置合わせサイクルの種々の段階をより良好に例示する目的で図１２Ａ〜１２Ｆに、初期位置合わせサイクルの段階の間に選択されるイメージを５行５列に配列された２５のイメージのセットについて示す。図１２Ａには、中心に配置された基準イメージがドットによって識別されている。図１２Ｂには、この初期位置合わせサイクルの第１段階において選択される水平および垂直のパスに沿って基準イメージに隣接する第１のリング内の４つのイメージが矢印によって示されている。図１２Ｃには、初期位置合わせサイクルの第２段階において選択される４つのイメージが矢印によって示されている。
【００６３】
基準イメージの周囲の第１のリング内のイメージが選択され、位置合わせされると、基準イメージの周囲の第２のリング内のイメージが選択される。図１２Ｄに示されている初期位置合わせサイクルの第３段階においては、矢印によって示されているとおり、基準イメージに対する位置合わせパスが最短の（すなわち、基準イメージから直線で垂直または水平に離れている）第２のリング内のイメージが選択される。図１２Ｅに示されている初期位置合わせサイクルの第４段階においては、矢印によって示されているとおり、第２のリング内にあり、かつ先行する段階において選択されたイメージに隣接するイメージが選択される。図１２Ｆに示されている初期位置合わせサイクルの第５段階においては、矢印によって示されているとおり、第２のリング内にあり、かつ先行する段階において選択されたイメージに隣接するイメージが選択され、それによって位置合わせサイクルが完了する。位置合わせ未済のイメージが存在するときには、上記の選択パターンが追加の位置合わせサイクルの間に反復される。
【００６４】
上記の実施態様は、基準イメージの周囲に矩形のリングを形成するイメージのセットから形成されるコンポジット・イメージを示しているが、当業者であればイメージの分析がこのほかの順序でも可能なことを認識するであろう。たとえば菱形の分析パターンを使用することができる。
【００６５】
１つのイメージを１ないしは複数の隣接イメージに位置合わせする別の方法も使用することが可能である。たとえば、イメージ内のエッジを使用してイメージを互いに位置合わせすることができる。位置合わせの後には、位置合わせパスに沿った累積誤差の訂正のために、選択されたポイントの整合リストを作成することができる。
【００６６】
基準イメージは、その中心位置に基づいて自動的に選択されるとして説明されているが、当業者であれば、基準イメージを選択するための別の方法が使用可能なことを認識するであろう。たとえば、イメージが不規則にレイアウトされている場合には、密度アプローチを使用して基準イメージを選択し、イメージの変換に必要な変換の数を低減することが可能である。それに代えて、基準イメージがマニュアルで選択されるようにしてもよい。
【００６７】
種々の最短パス・アルゴリズムをフロイド・ウォーシャル全ペア最短パス・アルゴリズムに代えて採用することができる。たとえば、大きなまばらなグラフが存在するときには、ダイクストラ・アルゴリズムを使用してもよい。当業者であれば、このほかの最短パス・アルゴリズムを思いつくこともできよう。
【００６８】
このコンポジット・イメージ生成方法および装置は、パーソナル・コンピュータ等の処理ユニットまたはそのほかのコンピューティング・システム環境によって実行されるコンピュータ実行可能インストラクションを含むソフトウエア・アプリケーションとして具体化することができる。ソフトウエア・アプリケーションは、スタンドアロン・ディジタル・イメージ編集ツールとして実行されるようにしてもよく、あるいはほかの利用可能なディジタル・イメージ編集アプリケーション内に組み込み、強化された機能をそれらのディジタル・イメージ編集アプリケーションに提供するようにしてもよい。このソフトウエア・アプリケーションは、ルーチン、プログラム、オブジェクト・コンポーネント、データ構造等を含むプログラム・モジュールを含み、コンピュータ可読メディア上にストアされるコンピュータ可読プログラム・コードとして具体化することができる。コンピュータ可読メディアは、データをストアすることの可能な任意のデータ・ストレージ・デバイスであり、その後、コンピュータ・システムによってそれを読み出すことができる。コンピュータ可読メディアの例としては、読み出し専用メモリ、ランダム・アクセス・メモリ、ＣＤ−ＲＯＭ、磁気テープ、および光データ・ストレージ・デバイス等が挙げられる。コンピュータ可読プログラム・コードは、結合されたコンピュータ・システムを含むネットワークにわたって分散されることも可能であり、その結果、コンピュータ可読プログラム・コードが分散態様でストアされ、実行されることになる。
【００６９】
以上、特定の実施態様について説明してきたが、当業者であれば、付随する特許請求の範囲によって定義されるとおりのその精神ならびに範囲から逸脱することなし変形および修正を行い得ることを認識するであろう。
【図面の簡単な説明】
【００７０】
【図１】コンポジット・イメージの生成に使用される一例のイメージのセットを例示した説明図である。
【図２】コンポジット・イメージを生成するためのコンピューティング・デバイスを略図的に表現した説明図である。
【図３】コンポジット・イメージ生成の間に実行される包括的なステップを示したフローチャートである。
【図４】図１のイメージのための最初の位置合わせサイクルの段階を示した説明図である。
【図５】２つのイメージ間における位置合わせの間に実行されるステップを示したフローチャートである。
【図６】図１のイメージのための２番目の位置合わせサイクルの段階を示した説明図である。
【図７】２つの隣接イメージを伴うイメージの位置合わせの間に実行されるステップを示したフローチャートである。
【図８】８Ａ〜８Ｄは位置合わせグラフを示した説明図である。
【図９】イメージの変換の間に実行されるステップを示したフローチャートである。
【図１０】イメージのための変換調整を例示した説明図である。
【図１１】変換後のイメージの最終的なポジションを例示した説明図である。
【図１２】１２Ａ〜１２Ｆはより大きなイメージのセットのための位置合わせサイクルを例示した説明図である。
【符号の説明】
【００７１】
２０  コンピューティング・デバイス
２４  処理ユニット
２８  ランダム・アクセス・メモリ
３２  不揮発性メモリ
３６  入力インターフェース
４０  出力インターフェース
４４  ネットワーク・インターフェース
４８  ローカル・バス
【図２】
2007048290.tif 000009
【図３】
2007048290.tif 000010
【図４】
2007048290.tif 000011
【図５】
2007048290.tif 000012
【図６】
2007048290.tif 000013
【図７】
2007048290.tif 000014
【図８】
2007048290.tif 000015
【図９】
2007048290.tif 000016
【図１０】
2007048290.tif 000017
【図１１】
2007048290.tif 000018
【図１２】
2007048290.tif 000019
【図１】
2007048290.tif 000020