(57)【要約】【課題】複数の画像源から得られた画像を同期化する、コンピュータベースの画像シーケンス整列方法を提供する。【解決手段】この方法では、２つ以上の画像源からの画像と関連するメタデータを受信し（１０２）、このメタデータからタイムスタンプを抽出し（１０４）、少なくとも部分的に画像源に基づいて画像をシーケンス毎に分類し（１０６）、異なるシーケンスからの画像の類似性を測定し（１０８）、この類似性が既定の閾値よりも高い、異なるシーケンスからの画像ペアを識別し（１１０）、画像ペアの不整合を最小化することによって、画像シーケンスを整列させる（１１２）。【選択図】図１
2010130695.tif 000002
【特許請求の範囲】
【請求項１】
２つ以上の画像源からの画像と関連するメタデータを受信し、
前記メタデータからタイムスタンプを抽出し、
少なくとも部分的に前記画像源に基づいて、前記画像をシーケンス毎に分類し、
異なるシーケンスからの画像の類似性を測定し、
前記異なるシーケンスからの画像のペアであって、前記類似性が既定の閾値よりも高い画像のペアを識別し、
前記画像のペアの不整合を最小化することによって、画像シーケンスを整列させる、
コンピュータベースの画像シーケンス整列方法。
【請求項２】
前記画像ペアの不整合が、費用関数によって最小化される、請求項１に記載の方法。
【請求項３】
２つ以上の画像源からの画像と関連するメタデータを受信し、
少なくとも部分的に前記画像源に基づいて、前記画像をシーケンス毎に分類し、
異なるシーケンスからの画像の類似性を測定し、
少なくとも部分的に前記類似性に基づいて、クラスタを識別し、
クラスタの大域的集中を最大化することによって、画像シーケンスを整列させる、
コンピュータベースの画像シーケンス整列方法。
【請求項４】
それぞれが画像を撮影する、複数の撮像装置と、
前記複数の撮像装置それぞれからの各画像と関連するタイムスタンプを抽出する、タイムスタンプ抽出器と、
前記撮像装置のそれぞれと関連する画像シーケンスを分類する、シーケンス分類器と、
異なるシーケンスからの画像それぞれの類似性を測定する、測定部と、
画像ペア及び／又はクラスタの類似性を評価することによって、前記類似性が既定の閾値よりも高いことを確かめる、ペア／クラスタ評価器と、
類似性情報を利用して画像の不整合を最小化することによって、適切なシーケンス整列をもたらす、シーケンス整列部と、
を備える、画像シーケンス整列システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明に係る実施形態は、複数の異なる画像源からの画像を同期化することに広く関する。これらの実施形態は、特に、類似した画像を識別してシーケンスの不整合を最小化することに関して適用される。一実施形態では、費用関数を利用することによって、画像シーケンスが適切に整列される。しかし、本発明に係る実施形態は、その他同様の用途にも適していることに留意されたい。
【背景技術】
【０００２】
特定のイベントの画像は、カメラ、携帯電話、ＰＤＡ、又はその他の手段によって撮影することができる。しかし、画像及びカメラによって角度、照明、被写体などが異なる可能性があるため、撮影した画像を適切なシーケンスに整理することは困難であり得る。この問題は、撮影時間が分からない場合深刻となる。このような困難を克服するために、各画像と関連するタイムスタンプを判別すべくメタデータを分析してもよい。しかし、このような情報は、不正確であり得る外部の設定値に依存している。例えば、タイムスタンプは、ユーザが設定した現在の日時に依存し得る。このような設定値は、現在の時間帯(time zone)や夏時間などに更新されていない場合、信頼できない可能性がある。結果として、撮像の時系列若しくはシーケンスが、不完全であるか又は誤っている可能性がある。
【０００３】
従来、専門的環境では、同期信号を送信する１台のコンピュータに全てのカメラをつなぐことによって、複数のカメラを同期化している。しかしながら、１人の人が全てのカメラを利用できることは滅多になく、この様な状況は、画像同期化用のコンピュータ・ソフトウェアを有する人にとっては尚更稀である。尚、ビデオ整合に関しては、多くの科学的研究が行われている。ここでは、２つ（又はそれ以上）のカメラが同じ被写体／場面の異なる映像を撮影しているため、これらの映像が１コマ毎に整合され得ると仮定している。しかし、一般的には、各写真シーケンスのうちの少数の画像だけが、同じ被写体／場面に対応する。ゆえに、一般的な映像整合アルゴリズムを適用することはできない。
【０００４】
カメラ画像の適切な順番付け(sequencing)を特定するべく他の方法も取られてきた。一方法が、ブリーズ・システムズ(Breeze Systems)社によるオンライン記事（http:／／www.breezesys.com／articles／multiple#cameras.htm.）に記載されている。この方法は、各カメラを用いて同じ時計を撮影することによって（イベント前、イベント中、又はイベント後のいずれでも良い）基準時間を得ることを含む。しかし、これは、１人の人が全てのカメラにアクセスできる場合限られ、上記の通りこれは困難を生じる。
【０００５】
別の方法が、イーストマン・コダック(Eastman Kodak)社に付与された米国特許出願公開第２００６／０２００４７５号に記載されている。この特許出願は、複数の新規画像を既存の時間順画像データベースに組み入れる方法に関する。データベース画像は、時間差閾値に基づいてイベント・グループに分類され、このイベント・グループ内では類似性測度に基づいてイベント・サブグループに分類されている。まず、各新規画像の１以上の画像特徴が評価される。次に、新規画像は画像特徴に基づいてクラスタ毎に整理され、各クラスタにおける代表画像が選択される。そして、前記データベース画像のうちの新規画像と時間的に重なるセグメントが指定される。このセグメントにおいて、データベース画像のうちの、各前記代表画像に類似している１以上のセットが識別されて検索画像セットが得られる。前記検索画像のうちの１以上を含む異なるイベント・サブグループが各前記クラスタと関連付けられることによって、適合サブグループがもたらされる。新規画像は、それぞれのクラスタと関連する適合サブグループに割り当てられる。
【０００６】
しかしながら、この方法にはいくつかの欠点がある。第１に、新しい画像が、データベース内の画像クラスタに割り当てられるため、複数のカメラによって撮影された画像シーケンスを同期化するという課題を考慮していない。第２に、時間順画像データベースが事前に存在すると想定されているが、この順序付けは、異なる画像源から画像が収集された場合には存在しないため、画像の順番付けを助けるのには適用できない。最後に、全ての画像（例えば、データベース画像及び新規画像）が同期化されることを想定しているが、このような同期化は、複数の画像源からの画像に関しては行われない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許出願公開第２００６／０２００４７５号明細書
【特許文献２】米国特許出願第１１／９４７，８５９号
【特許文献３】国特許出願第１２／１０９，４９６号
【非特許文献】
【０００８】
【非特許文献１】[online]、ブリーズ・システムズ(Breeze Systems)、インターネット＜ＵＲＬ：http:／／www.breezesys.com／articles／multiple#cameras.htm.＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従って、複数の画像源から得られた画像に関する時間知識がほとんど又は全くない状態でこれらの画像を同期化するシステム及び方法が必要とされている。
【課題を解決するための手段】
【００１０】
本発明の第１の態様は、２つ以上の画像源からの画像と関連するメタデータを受信し、前記メタデータからタイムスタンプを抽出し、少なくとも部分的に前記画像源に基づいて、前記画像をシーケンス毎に分類し、異なるシーケンスからの画像の類似性を測定し、前記異なるシーケンスからの画像のペアであって、前記類似性が既定の閾値よりも高い画像のペアを識別し、前記画像のペアの不整合を最小化することによって、画像シーケンスを整列させる、コンピュータベースの画像シーケンス整列方法である。
【００１１】
本発明の第２の態様によれば、本発明の第１の態様において、前記画像ペアの不整合が、費用関数によって最小化される。
【００１２】
本発明の第３の態様は、２つ以上の画像源からの画像と関連するメタデータを受信し、少なくとも部分的に前記画像源に基づいて、前記画像をシーケンス毎に分類し、異なるシーケンスからの画像の類似性を測定し、少なくとも部分的に前記類似性に基づいて、クラスタを識別し、クラスタの大域的集中を最大化することによって、画像シーケンスを整列させる、コンピュータベースの画像シーケンス整列方法である。
【００１３】
本発明の第４の態様は、それぞれが画像を撮影する、複数の撮像装置と、前記複数の撮像装置それぞれからの各画像と関連するタイムスタンプを抽出する、タイムスタンプ抽出器と、前記撮像装置のそれぞれと関連する画像シーケンスを分類する、シーケンス分類器と、異なるシーケンスからの画像それぞれの類似性を測定する、測定部と、画像ペア及び／又はクラスタの類似性を評価することによって、前記類似性が既定の閾値よりも高いことを確かめる、ペア／クラスタ評価器と、類似性情報を利用して画像の不整合を最小化することによって、適切なシーケンス整列をもたらす、シーケンス整列部と、を備える、画像シーケンス整列システムである。
【図面の簡単な説明】
【００１４】
【図１】本実施形態の一態様による、画像ペアの不整合を最小化することにより画像シーケンスを整列させる方法を示す図である。
【図２】本実施形態の一態様による、画像クラスタの大域的集中を最大化することにより画像シーケンスを整列させる方法を示す図である。
【図３】本実施形態の一態様による、異なる画像源からの画像シーケンスを整列させるシステムを示す図である。
【図４】本実施形態の一態様による、複数の画像を含む４つのシーケンスを有する、例示的システムを示す図である。
【図５】本実施形態の一態様を用いて順番付けする複数の例示的画像を示す図である。
【発明を実施するための形態】
【００１５】
本明細書の記載において、Ｎ個の異なる撮像装置（例えば、カメラ）によって撮影されたＮ個の画像シーケンスを整合させるべく画像内容を利用することを想定する。一仮定として、異なるカメラによってほぼ同時刻に類似した写真が撮影されるとする。このような仮定の真偽は、そのイベントに関わるカメラ数及び撮影写真の数の増加に従って高まる。従って、画像の類似性に基づく適切な費用関数又はその他の目的関数を利用することにより、適切な画像シーケンスを確定してユーザに提示することができる。
【００１６】
図１は、画像シーケンスを整列するために用いられる方法１００を示している。１０２において、２つ以上の画像源からの画像と関連するメタデータが受信される。一実施形態では、これらの画像源は、デジタル撮像装置（例えば、カメラ、携帯電話、携帯端末（ＰＤＡ）など）である。これらの画像源からの画像と関連するメタデータは、実質的に如何なるフォーマットであってもよく、例えば、Ｅｘｉｆ(exchangeable image file format)が挙げられる。周知のように、Ｅｘｉｆとは、デジタルカメラによって用いられる、画像ファイル・フォーマットの規格である。この規格は、特定のメタデータ・タグを加えた、既存のＪＰＥＧ、ＴＩＦＦ  Ｒｅｖ．６．０、及びＲＩＦＦ  ＷＡＶファイル・フォーマットを利用することができる。このように、日時情報が、デジタル撮像装置によって記録され、メタデータと共に保存される。このＥｘｉｆデータは、その画像ファイル自体に埋め込まれる。
【００１７】
１０４において、各画像に対するメタデータから、タイムスタンプが抽出される。このような抽出は、当該技術分野では周知の標準ソフトウェア・アプリケーションを利用することによって、容易に行うことができる。一例では、このソフトウェア・アプリケーションは、Ｅｘｉｆヘッダ内の日時フィールドを識別して、これと関連する値フィールドから数値表現を抽出する。１０６において、少なくとも部分的に画像源に基づいて、画像がシーケンス毎に分類される。再度、Ｅｘｉｆヘッダをポーリングし、デジタル撮像装置に関する情報（例えば、型、製造業者など）を抽出することによって、これと関連する画像の順番付けを確定することができる。これに替えて、又はこれに加えて、ユーザは、既知のパラメータ（例えば、カメラ所有者のＩＤ）に基づいて、画像を整理してもよい。
【００１８】
１０８において、異なるシーケンスからの画像の類似性が測定される。２つの画像間における類似性を測定するには、実質的にどんな既知のツールを用いてもよい。このようにして、２つの異なるシーケンスに属し既定の閾値を満たす、全ての画像ペアを検出することができる。画像の類似性を検出する１つの方法が、発明の名称が、「画像を検索してカテゴリー化するように構成された混合モデル(Adapted Mixture Models for Image Retrieval and Categorization)」である米国特許出願第１１／９４７，８５９号に説明されている。当然のことながら、本明細書中に記載の実施形態に関し、画像の類似性を確定するには、実質的にどんな測定ツールを使用してもよい。
【００１９】
１１０において、異なるシーケンスからの、類似性が既定の閾値よりも高い画像ペアが識別される。参照番号１０８から得られた類似性測定値を利用することにより、各画像ペアに対して類似性スコアを付けることができる。ある所定の閾値よりもこのスコアが高い場合には、一方の画像を他方の画像と関連付けることができる。ペア付けされなかった画像（例えば、関連する画像スコアが既定の閾値よりも高くない）は、これ以降方法１００の対象から外される。一例において、Ｐをペアのセット、即ちＰ＝｛ｐi，ｉ＝１…Ｍ｝とする。各シーケンスにおいて、少なくとも１つの画像が別のシーケンスにおける別の画像とペア付けされる、と想定する（これにより、Ｍ≧Ｎ−１となる）。各ペアｐiは、「画像１」及び「画像２」を含み、これらの画像のタイムスタンプ（それぞれ、ｔi,1及びｔi,2）並びに対応するシーケンス指標（それぞれ、ｓi,1及びｓi,2）によって特徴付けられる。
【００２０】
１つの目的は、異なるシーケンスにおける、同じイベントの絶対時間に対応する画像を関連付けることである。画像類似性を利用すると、視覚的には非常に似ているが異なるイベントの時間に対応する写真を関連付けてしまうことがある。夕食の例を挙げてみよう。異なる２人の人が、同じ人たちがいる同じテーブルの写真を撮り、１人は１品目のときに、もう１人は（それから１時間以上経ったであろう）デザートのときに撮ったとする。画像には、２つの写真が同じ時間に対応していないことを示す手掛かり（テーブル上の料理）が含まれ得るが、このような微細な手掛かりは、最新式の画像類似性システムが識別できないことがある。従って、一実施形態では、システムによって検出された類似画像を、ユーザが確認するようにしてもよい。
【００２１】
別の例では、各ペアに対して信頼性測度を関連付けることができる。この場合、各ペアｐiは、２つの写真が同じ時間に対応しているかどうかに関する信頼性を示す関連値ωiを有し得る。このような信頼性測度は、画像間の類似性測度に基づいていてもよいし、画像ペアをユーザが確認したか否かに基づいていてもよい。信頼性測度が画像ペアと関連付けられていない場合には、全ての値を１又はその他何らかの同等値に等しいと想定してもよい。
【００２２】
１１２において、ペアの不整合を最小化することによって、画像シーケンスが整列される。まず、１つの画像シーケンスを、基準シーケンスとして適宜選択する。この基準シーケンスを、ｓ0と示す。残りのＮ−１個のシーケンス（ｓn，ｎ＝１…Ｎ−１）は、基準シーケンスから時間δ（ｎ）だけずれている（当然δ（０）＝０）、と想定する。すると、以下に示す費用関数を最小化する。
【００２３】
【数１】
2010130695.tif 000003
【００２４】
上記式は、画像ペアの不整合の度合いの二乗平均を表している。δに関する偏微分を求めてこれを０と等しいと仮定すると、Ｎ−１個の変数を有すＮ−１個の一次方程式からなる連立方程式が導出される。この連立方程式が一意解を有する場合には、候補の整合が見つかる。算出されたδの値を利用することによって、費用関数Ｃの値を算出することができる。Ｃが所定の閾値よりも低い場合、整合は成功と見なすことができる。反対に、費用関数スコアＣが所定の閾値よりも高い場合には、いくつかの画像ペアが同じ時間に対応していないことを示している。高い値のＣiと関連するペアｐiは、誤ったペアに対応している可能性が最も高い。従って、最初にユーザはこのようなペアを検討して確認及び／又は修正すべきである。
【００２５】
当然のことながら、費用関数の代わりに、他の目的関数を利用してもよい。この方法の成功率は、画像ペアの数よりも質に依存し得る。例えば、Ｎ−１個の画像ペアが同じ瞬間にぴったりと対応すれば、完璧に近い結果がもたらされる。
【００２６】
画像の整合の際に、実時間の識別に関して更に考察してもよい。ここまでは、複数のシーケンスの整合についてのみ考察してきた。しかしながら、選択された基準が「実」時間に関して同期化されている、という保証はない。この「実時間」は、以下のようにして概算することができる。基準は「実時間」に関してΔだけずれる、と想定する。そして、以下に示す絶対時間ずれの平均を最小化するΔを求めることができる。
【００２７】
【数２】
2010130695.tif 000004
【００２８】
異なるカメラが著しく同期化されていない場合には二乗値に対して絶対値のほうがロバスト性がより高いため、（二乗値ではなく）絶対値を求める。上記のように、この方法１００を用いた実時間の概算に関して、他の目的関数を考察してもよい。
【００２９】
コンピュータ１５０は、本明細書中で説明するシステム及び方法（上記方法１００を含む）をサポートするのに可能な、１つのハードウェア構成を示している。独立型アーキテクチャが示されているが、当然のことながら、本実施形態によれば、あらゆる適切なコンピューティング環境を利用してもよい。例えば、本実施形態によれば、独立型、マルチプロセッサ、分散型、クライアント／サーバ、ミニコンピュータ、メインフレーム、スーパーコンピュータ、デジタル、及びアナログのような、コンピューティング・アーキテクチャを利用してもよいが、これらに限定されない。
【００３０】
コンピュータ１５０は、処理装置（図示せず）と、システム・メモリ（図示せず）と、システム・メモリを含む様々なシステム・コンポーネントを処理装置につなぐシステム・バス（図示せず）とを含み得る。処理装置は、市販されている様々なプロセッサのいずれであってもよい。また、デュアル・マイクロプロセッサ及びその他のマルチプロセッサ・アーキテクチャを処理装置として用いてもよい。
【００３１】
システム・バスは、市販されている様々なバス・アーキテクチャのいずれかを用いる、いくつかのタイプのバス構造（例えば、メモリ・バス若しくはメモリ・コントローラ、周辺バス、及びローカル・バス）のいずれであってもよい。コンピュータ・メモリとしては、読み取り専用メモリ（ＲＯＭ）及びランダム・アクセス・メモリ（ＲＡＭ）が挙げられる。ＲＯＭには、例えば起動中にコンピュータ内のエレメント間における情報転送を助ける基本ルーチンを含む、基本入出力システム（ＢＩＯＳ）が記憶されている。
【００３２】
コンピュータ１５０は、ハードディスク・ドライブ、（例えば、取り外し可能ディスクに対して読み出し若しくは書き込みするための）磁気ディスク・ドライブ、及び、（例えば、ＣＤ−ＲＯＭディスクに対して読み出しするための、又は、その他の光媒体に対して読み出し若しくは書き込みするための）光ディスク・ドライブを更に含み得る。このコンピュータ１５０は、一般的には、少なくとも何らかの形態のコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータがアクセスすることのできる媒体であれば、いずれの利用可能な媒体であってもよい。例として、コンピュータ可読媒体は、コンピュータ記憶媒体と通信媒体とから構成され得るが、これに限定されない。コンピュータ記憶媒体には、情報（例えば、コンピュータ可読命令、データ構造、プログラム・モジュール、若しくはその他のデータ）を記憶するあらゆる方法又は技術で実施される、揮発性媒体、不揮発性媒体、取り外し可能媒体、及び取り外し不可能媒体が含まれる。このようなコンピュータ記憶媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ、若しくはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、若しくはその他の磁気記憶装置、又は、所望の情報を記憶するのに用いることができると共にコンピュータがアクセスすることができるその他あらゆる媒体が挙げられるが、これらに限定されない。
【００３３】
通信媒体は、一般的には、変調データ信号（例えば、搬送波、若しくはその他の移送機構）においてコンピュータ可読命令、データ構造、プログラム・モジュール、又はその他のデータを具体化すると共に、あらゆる情報送達媒体を含む。「変調データ信号」とは、特徴のうちの１つ以上がその信号において情報を符号化するように設定又は変更された信号のことを言う。例として、通信媒体には、有線媒体（例えば、有線ネットワーク、又は直接有線接続）及び無線媒体（例えば、音響媒体、無線周波（ＲＦ）媒体、赤外線媒体、及びその他の無線媒体）が含まれるが、これらに限定されない。上記のいずれの組み合わせも、コンピュータ可読媒体の範囲内に含まれ得る。
【００３４】
ドライブ及びＲＡＭには、多くのプログラム・モジュール（例えば、オペレーティング・システム、１つ以上のアプリケーション・プログラム、その他のプログラム・モジュール、及び、プログラム非割り込みデータ）が記憶され得る。コンピュータ１５０におけるオペレーティング・システムは、市販されている多くのオペレーティング・システムのいずれであってもよい。
【００３５】
ユーザは、キーボード（図示せず）及びポインティング・デバイス（図示せず）（例えば、マウス）によって、コマンド及び情報をコンピュータに入力し得る。その他の入力装置（図示せず）としては、マイク、赤外線リモコン、ジョイスティック、ゲーム・パッド、パラボラ・アンテナ、スキャナなどが挙げられる。これらの及びその他の入力装置は、システム・バスにつながれたシリアルポート・インタフェース（図示せず）を介して処理装置に接続されることが多いが、その他のインタフェース（例えば、パラレルポート、ゲームポート、ユニバーサル・シリアル・バス（ＵＳＢ）、赤外線インタフェースなど）によって接続されてもよい。
【００３６】
モニタ又はその他のタイプの表示装置も、インタフェース（例えば、ビデオ・アダプタ（図示せず））を介してシステム・バスに接続される。コンピュータは、一般的には、モニタに加えて、他の周辺出力装置（図示せず）（例えば、スピーカ、プリンタなど）も含む。コンピュータ１５０と共にモニタを利用することによって、１つ以上の異なる画像源から電子的に受信されるデータを提示することができる。例えば、モニタは、データを電子的に提示する、液晶ディスプレイ（ＬＣＤ）、プラズマ、ブラウン管（ＣＲＴ）などのタイプであり得る。或いは若しくは更に、モニタは、受信データをハードコピー・フォーマット（例えば、プリンタ、ファクシミリ、プロッタなど）で表示することができる。モニタは、あらゆる色でデータを提示することができると共に、コンピュータ１５０からあらゆる無線プロトコル及び／又は規格或いは有線プロトコル及び／又は規格を介してデータを受信することができる。
【００３７】
コンピュータ１５０は、１つ以上のリモート・コンピュータへの論理的及び／又は物理的接続を用いるネットワーク環境において作動し得る。このリモート・コンピュータは、ワークステーション、サーバ・コンピュータ、ルータ、パーソナル・コンピュータ、マイクロプロセッサに基づいた娯楽機器、ピア装置、又はその他の共通ネットワーク・ノードであってよく、一般的には、コンピュータに関して説明した前記エレメントの多く又は全部を含む。ここに示す論理的接続としては、ローカルエリア・ネットワーク（ＬＡＮ）及び広域ネットワーク（ＷＡＮ）が挙げられる。このようなネットワーク環境は、オフィス、企業規模のコンピュータ・ネットワーク、イントラネット、及びインターネットでは当たり前である。
【００３８】
コンピュータは、ＬＡＮ環境において用いられる場合、ネットワーク・インタフェース若しくはアダプタを介してローカル・ネットワークに接続される。ＷＡＮ環境において用いられる場合には、コンピュータは、一般的に、モデムを含むか、ＬＡＮ上の通信サーバに接続されるか、ＷＡＮ上で通信を行うためのその他の手段（例えば、インターネット）を有する。ネットワーク環境において、コンピュータに関して示した前記プログラム・モジュール又はその一部は、リモート記憶装置に記憶されてもよい。当然のことながら、本明細書中で説明したネットワーク接続は例であって、コンピュータ間における通信リンクをもたらすその他の手段を用いてもよい。
【００３９】
図２は、クラスタの大域的集中(global concentration)を最大化することによって画像シーケンスを整列させるのに利用される方法２００を示している。この方法２００は、上述した方法１００を一般化したものであり、この方法では、画像ペアの代わりに画像クラスタが考察される。概して、モード（若しくはクラスタ）は、画像セット全体において検出されるが、クラスタは、画像空間の高密度領域に対応している。次に、このようなクラスタの大域的集中を最大化することによって、画像シーケンスが整列される。
【００４０】
参照番号２０２において、２つ以上の画像源からの画像と関連するメタデータが受信される。上記のように、これらの画像源は、実質的にどんな撮像装置（例えば、カメラ、携帯電話、携帯端末（ＰＤＡ）など）であってもよい。２０４において、各画像に対するメタデータ（例えば、Ｅｘｉｆヘッダ）から、タイムスタンプが抽出される。２０６において、少なくとも部分的に画像源に基づいて、画像がシーケンス毎に分類される。一例では、５つのカメラそれぞれから得られた画像は、それぞれの画像を撮影した各カメラと関連付けられ得る。メタデータに基づいて且つ／或いはユーザを介してこのような処理を行うことによって、既知のパラメータ（例えば、カメラ所有者のＩＤ）に基づいて画像を整理することができる。
【００４１】
２０８において、上記方法１００で述べたように、異なるシーケンスからの画像の類似性が測定される。場合によっては、１つの画像が他のシーケンスにおける複数の画像にリンクされることによって、クラスタ構造が形成されることもある。ゆえに、上述したように、画像ペアの代わりに画像クラスタを考察することは有益であり得る。このような場合には、主な想定として、イベント中に「ピーク・イベント」（例えば、サッカーの試合中におけるペナルティ・キックのような、短時間続いて急激に関心を高めるサブイベント）があるとする。このような「ピーク・イベント」は、視覚空間及び時間の両方において、画像セットのモードに対応すべきである。モード（若しくはクラスタ）は、高密度領域に対応する一般的に小さなクラスタとして識別することができる。小さな高密度クラスタリングの一例は、発明の名称が「スパース・グラフに対して非負行列因子分解を用いる大規模クラスタリング(Large Scale Clustering Using Non-Negative Matrix Factorization on Sparse Graphs)」である米国特許出願第１２／１０９，４９６号で述べたようなゼロックス(Xerox)・クラスタリング・アルゴリズムによって識別することができる。
【００４２】
図５に示されているような集合写真が、クラスタリング・アルゴリズムで特定されるようなピーク・イベントに対応する。画像の類似性は、発明の名称が「画像を検索してカテゴリー化するように構成された混合モデル」である米国特許出願第１１／９４７，８５９号に説明されているような、適切な類似性測度によって識別することができる。検出されたモード／クラスタがピーク・イベントに対応するかどうかを決定するのに、ユーザ・インタラクションが使用され得る。例えば、ピーク・イベントに対応しない様々な時間に撮影された様々な人のポートレートを含む、非常に密度の高いクラスタを識別することができる。２１０において、少なくとも部分的に画像類似性に基づいて、画像が同じクラスタにグループ化される。
【００４３】
２１２において、各クラスタ内の画像が識別される。再度図５を参照すると、クラスタ５００は、１０の異なる画像を含む。図示されているように、画像５０４、５０６、５０８、５１２、５１４、及び５１８は、所定の閾値よりも大きく、クラスタ内に含まれる。一方、画像５０２、５１０、５１６、及び５２０は、既定の類似性閾値よりも大きくないため、クラスタ５００に含まれない。モードｉ（例えば、モード５００）における画像ｊのタイムスタンプをｔi,jと示し、対応するシーケンスの指標をｓi,jと示すことができる。方法１００における画像ペアの場合と同様に、クラスタの密度又はクラスタをユーザが確認した否かに基づいて、クラスタｉに重みωiを付けることができる。
【００４４】
２１４において、クラスタの大域的集中を最大化することによって、画像シーケンスが整列される。この整列に関し、画像ペアの場合と同様に、１つの基準シーケンスが選択され、残りのＮ−１個のシーケンスには、δ変数が関連付けられる。以下のような二次目的関数（クラスタ差異の合計）を最小化することが目的である。
【００４５】
【数３】
2010130695.tif 000005
【００４６】
同じく、偏微分を求めて０に等しいと仮定すると、Ｎ−１個の変数を有すＮ−１個の方程式からなる連立方程式が導出される。このような連立方程式を作るためには、その他の費用関数Ｃi（例えば、最大エントロピーや正規化エントロピーなどのようなエントロピーに基づいた関数、冪指標関数、ハーフィンダール(Herfindahl)関数、正規化ハーフィンダール関数、ジニ(Gini)係数関数、又はその他あらゆる集中係数関数）を利用してもよい。Ｃが所定の閾値よりも低い場合、整合は成功と見なすことができる。反対に、Ｃが所定の閾値よりも高い場合には、いくつかの画像が同じ時間に対応していないことを意味している。「実時間」は、上記数２の式を利用して概算することができる。このようにして、シーケンス整合を「実時間」に関して同期化することができる。
【００４７】
図３は、ペア又はクラスタ内の画像シーケンスを整列させるシステム３００を示している。このシステム３００は、タイムスタンプ抽出器３０４に画像を提供する複数の画像源３０２を含む。これらの画像源は、カメラ、携帯電話、ＰＤＡ、又は撮像可能なあらゆる装置のうちの１つ以上であってよい。タイムスタンプ抽出器３０４は、各画像源３０２からの各画像と関連するメタデータを分析し、各画像と関連するタイムスタンプを抽出する。一例では、タイムスタンプ抽出器は、Ｅｘｉｆヘッダを調査して、このＥｘｉｆヘッダに含まれている適切なデータ／時間フィールドから情報を抽出する。
【００４８】
シーケンス分類器３０６は、タイムスタンプ抽出器３０４からタイムスタンプ情報を受信し、少なくとも部分的に画像源３０２に基づいて画像をシーケンス毎に分類する。メタデータを分析してデジタル撮像装置に関する情報（例えば、型、製造業者など）を抽出することによって、これと関連する画像の順番付けを確定することができる。更に、既知のパラメータ（例えば、撮像装置所有者のＩＤ）に基づいて、画像を整理してもよい。
【００４９】
測定部３０８は、異なるシーケンスからの画像の類似性を測定する。一例では、発明の名称が「画像を検索してカテゴリー化するように構成された混合モデル」である米国特許出願第１１／９４７，８５９号が利用される。当然のことながら、実質的にどんな測定ツールを使用してもよい。ペア／クラスタ評価器３１０は、測定部３０８から情報を受信して、類似性が既定の閾値よりも高い、異なるシーケンスからの画像ペアを識別したり、少なくとも部分的に画像類似性に基づいて、クラスタ内の画像を識別したりする。測定部３０８は、画像ペア又はクラスタと関連する類似性スコアを出力することができ、この類似性スコアを利用して既定の閾値と比較することによって、それらの画像の類似性が十分であるかどうかが確定される。
【００５０】
一例において、Ｐをペアのセット、即ちＰ＝｛ｐi，ｉ＝１…Ｍ｝とする。各シーケンスにおいて、少なくとも１つの画像が別のシーケンスにおける別の画像とペア付けされる、と想定する（これにより、Ｍ≧Ｎ−１となる）。この条件に合わない場合、そのシーケンスは方法１００の残部において考察されない。各ペアｐiは、「画像１」及び「画像２」を含み、これらの画像のタイムスタンプ（それぞれ、ｔi,1及びｔi,2）並びに対応するシーケンス指標（それぞれ、ｓi,1及びｓi,2）によって特徴付けられる。
【００５１】
各クラスタ内の画像は、ペア／クラスタ評価器３１０がクラスタ（例えば、クラスタ５００）内の画像を調査することによって識別することができる。Ｍ個のモード／クラスタがペア／クラスタ評価器３１０によって識別され、１つのモードｉはＭi個の画像を含む、と想定することができる。画像ｊ及びモードｉのタイムスタンプをｔi,jと示し、対応するシーケンスの指標をｓi,jと示す。更に、クラスタの密度、ペアの類似性、又は、ペア／クラスタをユーザが確認したか確認していないかに基づいて、各ペア／クラスタに重みを付けることができる。
【００５２】
シーケンス整列部３１２は、目的関数（例えば、費用関数）を利用して、撮像装置３０２から受信した画像に対して適切な画像シーケンスを決定する。一例において、費用関数は以下のように表される。
【００５３】
【数４】
2010130695.tif 000006
【００５４】
上記式は、画像ペアの平均不整合を表している。δに関する偏微分を求めてこれを０に等しいと仮定すると、Ｎ−１個の変数を有すＮ−１個の一次方程式からなる連立方程式が導出される。この連立方程式が一意解を有する場合には、候補整合が見つかる。算出されたδの値を用いることによって、費用関数Ｃの値を算出することができる。Ｃが所定の閾値よりも低い場合、整合は成功と見なすことができる。Ｃが所定の閾値よりも高い場合には、いくつかの画像ペアが同じ時間に対応していないことを意味している。高い値のＣiと関連するペアｐiは、誤ったペアに対応している可能性が最も高い。従って、最初にユーザ又はその他の手段によってこのようなペアを検討して確認及び／又は修正すべきである。
【００５５】
別の例では、画像クラスタが整列を必要とし、１つの基準シーケンスが選択され、残りのＮ−１個のシーケンスにはΔが関連付けられる。以下のような二次目的関数（クラスタ差異の合計を含む）を最小化することが目的である。
【００５６】
【数５】
2010130695.tif 000007
【００５７】
シーケンス整列部３１２は、実質的な目的関数（例えば、エントロピーに基づいた関数、最大エントロピーに基づいた関数、正規化エントロピーに基づいた関数、冪指標関数、ハーフィンダール関数、正規化ハーフィンダール関数、ジニ係数関数、及び／又はあらゆる集中係数関数）を利用することができる。受信した画像に対して適切なシーケンスが特定されると、そのシーケンスがシーケンス整列部３１２によって出力される。
【００５８】
図４は、複数のシーケンス４０２、４０４、４０６、及び４０８を含むシステム４００を示している。これらのシーケンスはそれぞれ、水平線によって識別される。シーケンス４０２は、画像４２０、４２２、４２４、及び４２６を含む。シーケンス４０４は、画像４３０及び４３２を含む。シーケンス４０６は、画像４４０及び４４２を含む。シーケンス４０８は、画像４５０及び４５２を含む。当然のことながら、ｘ軸は、時間（各撮像装置内又は各シーケンス内における撮像時間）を表している。異なるシーケンスからの画像を結ぶ線は、評価に利用される類似ペア又はクラスタを表している。このように、類似性情報を利用して、画像４２０〜４５２全体を適切なシーケンスに整列することができる。図示されているように、画像４２０、４３０、及び４４０は、類似性が所定の閾値よりも高いので、同じクラスタに含まれる。更に、画像４２２及び４４２はペアにされ、同様に、画像４２４及び４３２、並びに、画像４２６及び４５２もペアにされる。同じペア又はクラスタ内で識別された画像をシステム３００によって処理することにより、これらの画像と関連する適切なシーケンス整列を確定することができる。
【符号の説明】
【００５９】
１００、２００    画像シーケンス整列方法
１５０    コンピュータ
３００    画像シーケンス整列システム
３０２    画像源（撮像装置）
４００    システム
４０２、４０４、４０６、４０８    シーケンス
５００    クラスタ（モード）
４２０、４２２、４２４、４２６、４３０、４３２、４４０、４４２、４５０、４５２、５０２、５０４、５０６、５０８、５１０、５１２、５１４、５１６、５１８、５２０    画像
【図１】
2010130695.tif 000008
【図２】
2010130695.tif 000009
【図３】
2010130695.tif 000010
【図４】
2010130695.tif 000011
【図５】
2010130695.tif 000012