(57)【要約】  データベースは、時間差閾値に基づきイベントグループに分類され、類似度に基づきサブグループに分類される時間的に順序付けされた画像を有する。新たな画像をこのようなデータベースに合成する方法及びシステムでは、新たな画像が評価された画像特徴に基づきクラスタに順序付けされる。各クラスタにおいて、代表画像が選択される。新たな画像に時間的に重複するデータベースセグメントが指定され、各代表画像に類似するデータベース画像セットがセグメントにおいて特定される。１以上の抽出された画像を含む異なるサブグループが、一致したサブグループを提供するため各クラスタに関連付けされる。新たな画像が、各クラスタに係る一致したサブグループに割り当てられる。
2008532180.tif 000002
【特許請求の範囲】
【請求項１】
時間的に順序付けされた画像の既存のデータベースに複数の新たな画像を合成する方法であって、前記データベースの画像は、時間差閾値に基づきイベントグループに分類され、イベントグループ内では、類似度に基づきイベントサブグループに分類され、
当該方法は、
前記新たな画像のそれぞれの１以上の画像特徴を評価するステップと、
前記画像特徴に基づき、前記新たな画像をクラスタに順序付けするステップと、
前記クラスタのそれぞれにおいて代表画像を選択するステップと、
前記新たな画像に時間的に重複する前記データベースの画像のセグメントを指定するステップと、
前記セグメントにおいて、抽出された画像セットを提供するため、前記代表画像のそれぞれに類似する前記データベースの画像の１以上のセットを特定するステップと、
一致したサブグループを提供するため、前記抽出された画像の１以上を含む異なるイベントサブグループを前記クラスタのそれぞれに関連付けるステップと、
前記各クラスタに係る一致したサブグループに前記新たな画像を割り当てるステップと、
を有する方法。
【請求項２】
時間的に順序付けされた画像の既存のデータベースに複数の新たな画像を合成する方法であって、前記データベースの画像は、時間差閾値に基づきイベントグループに分類され、イベントグループ内では、類似度に基づきイベントサブグループに分類され、
当該方法は、
前記新たな画像のそれぞれの１以上の画像特徴を決定するステップと、
前記新たな画像の時間的順序を確認するステップと、
前記画像特徴に基づき、前記新たな画像をクラスタに順序付けするステップと、
前記クラスタのそれぞれにおける代表画像を選択するステップと、
前記新たな画像に時間的に重複する前記データベースの画像のセグメントを指定するステップと、
前記セグメントにおいて、抽出された画像セットを提供するため、前記代表画像のそれぞれに類似する前記データベースの画像の１以上のセットを特定するステップと、
一致したサブグループを提供するため、前記抽出された画像の１以上を含む異なるイベントサブグループを前記クラスタのそれぞれに関連付けるステップと、
前記各クラスタに係る一致したサブグループに前記新たな画像を割り当てるステップと、
前記割当て中に、前記新たな画像の時間的順序を維持するステップと、
を有する方法。
【請求項３】
前記確認するステップはさらに、前記新たな画像に係るメタデータに基づき、前記新たな画像に時間的順序を割り当てるステップを有する、請求項２記載の方法。
【請求項４】
前記メタデータは、ファイル発生の自動生成日である、請求項３記載の方法。
【請求項５】
前記新たな画像は、前記時間的順序を規定するメタデータを含む一意的なファイル名を有し、
前記確認するステップはさらに、前記メタデータを抽出するステップを有する、請求項３記載の方法。
【請求項６】
前記確認するステップはさらに、記録媒体上の前記画像の物理的順序に基づき、前記新たな画像に時間的順序を割り当てるステップを有する、請求項２記載の方法。
【請求項７】
前記確認するステップはさらに、前記時間的順序を指定するユーザ入力を受け付けるステップを有する、請求項２記載の方法。
【請求項８】
前記データベースは、最も最近のデータベースの画像日時を規定し、
前記指定するステップはさらに、前記最も最近のデータベースの画像日時より以降のものでない前記新たな画像の最後の日時を決定するステップを有する、請求項２記載の方法。
【請求項９】
前記決定するステップはさらに、前記新たな画像の開始日時を確認するステップを有し、
前記指定するステップはさらに、前記開始日時と前記最後の日時との又は間の前記セグメントをデータベースの画像に限定するステップを有する、請求項８記載の方法。
【請求項１０】
前記確認するステップはさらに、前記開始日時を指定するユーザ入力を受け付けるステップを有する、請求項９記載の方法。
【請求項１１】
前記関連付けの間に、前記一致したサブグループの累積時間期間を最小化するため、前記一致したサブグループを選択するステップを有する、請求項２記載の方法。
【請求項１２】
前記選択するステップはさらに、グリーディーアルゴリズムを利用するステップを有する、請求項１１記載の方法。
【請求項１３】
前記関連付けの間に、前記代表画像と前記各データベース画像セットとの類似性を最大化するため、前記一致したサブグループを選択するステップを有する、請求項２記載の方法。
【請求項１４】
前記関連付けするステップの前に、前記一致したサブグループの累積時間期間を最小化するよう前記一致したサブグループを選択するステップと、前記各画像と前記各データベース画像セットとの類似性を最大化するよう前記一致したサブグループを選択するステップとの１つを採用するステップと、
前記関連付け中に前記採用された選択するステップを適用するステップと、
をさらに有する、請求項２記載の方法。
【請求項１５】
前記選択するステップはさらに、
各類似度を提供するため、前記代表画像と前記各抽出された画像との相対的な類似性を決定するステップと、
前記類似度の分散を評価するステップと、
前記分散が所定の閾値未満であるとき、前記第１の選択するステップを使用するステップと、
前記分散が前記所定の閾値未満でないとき、前記第２の選択するステップを使用するステップと、
を有する、請求項２記載の方法。
【請求項１６】
前記評価するステップはさらに、残りの前記抽出された画像より前記各代表画像により高い類似性を有する所定数の前記抽出された画像の分散を計算するステップを有する、請求項２記載の方法。
【請求項１７】
前記セグメントは、前記新たな画像の最後の日時より時間的に以前の前記データベース画像のすべてを有する、請求項２記載の方法。
【請求項１８】
前記新たな画像の特徴を決定するステップは、自動的なものである、請求項２記載の方法。
【請求項１９】
時間的に順序付けされた画像の既存のデータベースに複数の新たな画像を合成するシステムであって、前記データベースの画像は、時間差閾値に基づきイベントグループに分類され、イベントグループ内では、類似度に基づきイベントサブグループに分類され、
当該システムは、
前記新たな画像のそれぞれの１以上の画像特徴を決定する手段と、
前記新たな画像の時間的順序を確認する手段と、
前記画像特徴に基づき、前記新たな画像をクラスタに順序付けする手段と、
前記クラスタのそれぞれにおける代表画像を選択する手段と、
前記新たな画像に時間的に重複する前記データベースの画像のセグメントを指定する手段と、
前記セグメントにおいて、抽出された画像セットを提供するため、前記代表画像のそれぞれに類似する前記データベースの画像の１以上のセットを特定する手段と、
一致したサブグループを提供するため、前記抽出された画像の１以上を含む異なるイベントサブグループを前記クラスタのそれぞれに関連付ける手段と、
前記新たな画像の時間的順序を維持しながら、前記各クラスタに係る一致したサブグループに前記新たな画像を割り当てる手段と、
を有するシステム。
【請求項２０】
時間的に順序付けされた画像の既存のデータベースに複数の新たな画像を合成するコンピュータプログラムプロダクトであって、前記データベースの画像は、時間差閾値に基づきイベントグループに分類され、イベントグループ内では、類似度に基づきイベントサブグループに分類され、
当該コンピュータプログラムプロダクトは、
前記新たな画像のそれぞれの１以上の画像特徴を決定するステップと、
前記新たな画像の時間的順序を確認するステップと、
前記画像特徴に基づき、前記新たな画像をクラスタに順序付けするステップと、
前記クラスタのそれぞれにおける代表画像を選択するステップと、
前記新たな画像に時間的に重複した前記データベース画像のセグメントを指定するステップと、
前記セグメントにおいて、抽出された画像セットを提供するため、前記代表画像のそれぞれに類似する前記データベースの画像の１以上のセットを特定するステップと、
一致したサブグループを提供するため、前記抽出された画像の１以上を含む異なるイベントサブグループを前記クラスタのそれぞれに関連付けるステップと、
前記各クラスタに係る一致したサブグループに前記新たな画像を割り当てるステップと、
前記割当て中に、前記新たな画像の時間的順序を維持するステップと、
を実行するためのコンピュータプログラムを格納したコンピュータ可読記憶媒体を有するコンピュータプログラムプロダクト。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の分野］
本発明は、画像を自動的に分類するデジタル画像処理に関し、より詳細には、個別のキャプチャ日時情報が欠落した画像の加算的クラスタリングに関する。
［発明の背景］
デジタルカメラやカメラフォトなどのデジタル家電キャプチャ装置の広範な利用によって、消費者の画像コレクションのサイズは大変急速に増大し続けている。自動化された画像管理及び整理が、これら大きなコレクションの容易なアクセス、サーチ、抽出及びブラウジングに重要となる。
【０００２】
日時情報と画像間のカラー類似性とに基づき画像をイベント及びサブイベントに自動的にグループ化する方法が、Ｌｏｕｉ及びＰａｖｉｅの米国特許第６，６０６，４１１Ｂ１号に記載されている（参照することによりここに含まれる）。イベントクラスタリングアルゴリズムは、イベントを判断するためキャプチャ日時情報を利用する。当該方法は、極めて大きな画像セットのクラスタリングにはかなりの時間を要するという欠点を有している。特に、一度にいくつか追加が行われ、またそれは比較的に頻繁であるため、新たな画像が消費者の画像コレクションに追加される毎に、イベント及びサブイベントが再計算される必要がある場合に問題となる。他の問題には、消費者が中断することのないアクセスを可能にするため、複数のパーソナルコンピュータ、モバイル装置、画像装置、ネットワークサーバ及びオンラインレポジトリに分散される画像のコレクションをマージすることができる必要があるということである。各マージの後にイベント及びサブイベントを再計算することは非効率的である。
【０００３】
米国特許第６，６０６，４１１Ｂ１号に記載されているイベントクラスタリングアルゴリズムは、それがデジタルカメラキャプチャメタデータからの日時情報を利用するという制約を有する。これは、データベースに追加される画像が正確な日時情報を欠いている場合に問題となる。このような画像の具体例として、スキャンされた画像、フィルムキャプチャからのデジタル画像ＣＤ、ビデオカムコーダからのスチル、又は正確でない日時設定を有するデジタルカメラからの画像があげられる。多くのケースでは、これらの画像は、画像キャプチャ日時でなく、スキャン若しくは他の処理の後のデジタルファイルのソースに関する関連する日時を有している。
【０００４】
コンテンツベース画像分類に基づく多くの方法は、メタデータが利用可能でない画像について提案されてきた。２００１年５月２５日に刊行されたＰＣＴ特許出願ＷＯ０１／３７１３１Ａ２では、顕著な画像領域の視覚特性が画像を分類するのに利用される。視覚特性の数値測定に加えて、“空”や“肌”などのセマティックな用語を使用して、領域の一部を分類するためニューラルネットワークが利用される。コレクションの画像の領域ベースの特性が、所与のクエリ画像の特性に一致した他の画像を検出することを容易にするためインデックス処理される。２００１年５月２９日に発行された米国特許第６，２４０，４２４Ｂ１号は、画像内のプライマリオブジェクトをクラスタリングセンターとして使用して画像を分類及びクエリする方法を開示する。所与の未分類の画像に適合した画像が、所与の画像のプライマリオブジェクトに基づき適切なクエリを定式化することによって検出される。２００２年１１月５日に発行された米国特許第６，４７７，２６９Ｂ１号は、ユーザがイグザンプルクエリを用いてカラー若しくは形状に基づく類似画像を検出することを可能にする方法を開示している。各種技術を用いて画像データベースからの画像抽出を提供することが知られている。２００２年１１月１２日に発行されたＺｈｕ及びＭｅｈｒｏｔｒａの米国特許第６，４８０，８４０号は、カラー、テクスチャ、カラー構成などの低レベル特徴を用いたコンテンツベースの画像抽出を開示している。
【０００５】
これらのコンテンツベースの方法は、画像により共通して利用可能な他のタイプの情報である時間的順序を考慮しないという欠点を有する。画像は、通常は時間的順序によりメディアに格納されている。例えば、フィルムキャプチャから導出されるＫｏｄａｋ  ＰｉｃｔｕｒｅＣＤＴＭの画像は、キャプチャ順によるものとなっている。時間表をもたらす数列若しくは他のシーケンスを利用して、画像のファイル名がしばしば作成される。例えば、いくつかのキャプチャされたデジタル画像は、生成順序を示すファイル名の数値サフィックスを有している。
【０００６】
従って、データベース全体を再クラスタリングすることなく、新たな画像がデータベースにおいて追加的にクラスタリングされる方法及びシステムを提供することが所望される。
【０００７】
さらに、時間順序が追加的クラスタリングにおいて考慮することが可能な方法及びシステムを提供することが所望される。
［発明の概要］
本発明は、請求項により規定される。本発明は、より広範な側面において、時間差閾値に基づきイベントグループに分類された時間的に順序付けされた画像を有するデータベースと、類似度に基づきサブグループとに新たな画像を組み合わせる方法及びシステムを提供する。本方法及びシステムでは、新たな画像が評価された画像特徴に基づきクラスタに順序付けされる。各クラスタにおいて、代表的な画像が選択される。新たな画像に時間的にオーバーラップするデータベースセグメントが指定され、各代表画像に類似したデータベース画像セットが、セグメントにおいて特定される。１以上の抽出された画像を含む各サブグループが、一致したサブグループを提供するため各クラスタに関連付けされる。新たな画像は、各クラスタに係る一致したサブグループに割り当てられる。
【０００８】
本発明の有利な効果は、新たな画像がデータベース全体を再クラスタリングすることなく、データベースにおいて追加的にクラスタリングされる改良された方法及びシステムが提供されることである。
【０００９】
本発明のさらなる効果は、キャプチャ日付／時間情報が欠落しているときでさえ、時間的順序が追加的クラスタリングにより維持される改良された方法及びシステムが提供されることである。
［発明の詳細な説明］
本方法では、画像が、画像データベースの既存のイベントグループ及びサブグループに追加的にクラスタリングされる。これらのグループは、日時情報に基づき整理される。データベースのサブグループは、日時情報以外の類似度に基づく。ここでは、“日時”という用語は、通常の標準に対する経過日付及び時間又は実際の日付又は時間の形式による時間情報を参照するのに使用される。
【００１０】
以下の説明では、本発明のいくつかの実施例が、通常はソフトウェアプログラムとして実現される用語により記載される。当業者は、このようなソフトウェアに等価なものがハードウェアによっても構成可能であることを容易に認識するであろう。画像処理アルゴリズム及びシステムは周知であるため、本記載は、特に本発明による方法の一部を構成し、若しくはそれとより直接的に協働するアルゴリズム及びシステムに関する。このようなアルゴリズム及びシステム並びにそれに関係する画像信号を生成及び処理するハードウェア及び／又はソフトウェアの他の側面は、ここでは具体的に図示若しくは説明されないが、当該技術において知られているこのようなシステム、アルゴリズム、コンポーネント及び要素から選択されてもよい。以下において本発明による記載されるようなシステムが与えられると、本発明の実現のため有用なここでは具体的に図示、示唆又は記載されないソフトウェアは、従来技術によるものであり、当該技術の通常の知識の範囲内である。
【００１１】
ここに使用されるように、コンピュータプログラムは、例えば、磁気ディスク（ハードドライブ若しくはフロッピー（登録商標）ディスクなど）若しくは磁気テープなどの磁気記憶媒体、光ディスク、光テープ若しくはマシーン可読バーコードなどの光記憶媒体、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）若しくはＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などのソリッドステート電子記憶装置、又はコンピュータプログラムを格納するのに使用される他の何れかの物理装置若しくは媒体などを含むコンピュータ可読記憶媒体に格納されてもよい。
【００１２】
本発明は、コンピュータハードウェアにより実現可能である。図２を参照するに、本発明を実現するためのシステムが記載される。好適な実施例を説明するためコンピュータシステムが示されているが、本発明は、図示されたシステムに限定されず、パーソナルコンピュータやデジタル画像を処理するための他のシステムなどにおける何れかの電子処理システム上で利用可能である。このため、コンピュータシステムはここでは詳細には説明されない。ここで使用される画像は、コンピュータシステムに直接入力可能であるか（例えば、デジタルカメラなどにより）、又はコンピュータシステムへの入力前にデジタル化することが可能である（例えば、ハロゲン化銀フィルムなどのオリジナルのスキャンによって）。
【００１３】
図２を参照するに、コンピュータシステム１１０は、ソフトウェアプログラムを受付及び処理し、他の処理機能を実行するマイクロプロセッサベースユニット１１２を有する。ディスプレイ１１４は、例えば、グラフィカルユーザインタフェースなどによって、ソフトウェアに係るユーザ関連情報を表示するため、マイクロプロセッサベースユニット１１２に電気的に接続される。キーボード１１６はまた、ユーザがソフトウェアに情報を入力することを可能にするため、マイクロプロセッサベースユニット１１２に接続される。入力のためキーボード１１６を使用する代わりに、当該技術において周知なように、マウス１１８がディスプレイ１１４上のセレクタ１２０を移動させ、セレクタ１２０が置かれたアイテムを選択するため利用されてもよい。
【００１４】
典型的にはソフトウェアプログラムを有するＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２４が、ソフトウェアプログラム及び他の情報をマイクロプロセッサベースユニット１１２に入力する手段を提供するため、マイクロプロセッサベースユニットに挿入される。さらに、フロッピー（登録商標）ディスク１２６はまたソフトウェアプログラムを有し、ソフトウェアプログラムを入力するため、マイクロプロセッサベースユニット１１２に挿入される。あるいは、ＣＤ−ＲＯＭ１２４又はフロッピー（登録商標）ディスク１２６が、マイクロプロセッサベースユニット１１２に接続される外部に配置されたディスクドライブユニット１１２に挿入されてもよい。さらに、マイクロプロセッサベースユニット１１２は、当該技術において周知なように、ソフトウェアプログラムを内部的に格納するためプログラムされてもよい。マイクロプロセッサベースユニット１１２はまた、ローカルエリアネットワークやインターネットなどの外部ネットワークとの電話線などのネットワーク接続１２７を有するかもしれない。プリンタ１２８はまた、コンピュータシステム１１０からの出力のハードコピーを印刷するマイクロプロセッサベースユニット１１２に接続されてもよい。
【００１５】
画像はまた、従来知られているように、カード１３０において電気的に実現されるデジタル画像を含むＰＣＭＣＩＡカード（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｍｅｍｏｒｙ  Ｃａｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎの仕様に基づく）などのパーソナルコンピュータカード（ＰＣカード）１３０を介しディスプレイ１１４上に表示されてもよい。ＰＣカード１３０は、最終的にはディスプレイ１１４への画像の視覚表示を可能にするため、マイクロプロセッサベースユニット１１２に挿入される。あるいは、ＰＣカード１３０は、マイクロプロセッサベースユニット１１２に接続された外部的に配置されたＰＣカードリーダ１３２に挿入可能である。画像はまた、ＣＤ１２４、フロッピー（登録商標）１２６又はネットワーク接続１２７を介し入力されてもよい。ＰＣカード１３０、フロッピー（登録商標）ディスク１２６若しくはＣＤ１２４に格納され、又はネットワーク接続１２７を介し入力される画像は、デジタルカメラ（図示せず）やスキャナ（図示せず）などの各種ソースから取得されたものであってもよい。画像はまた、マイクロプロセッサベースユニット１１２に接続されるカメラドッキングポート１３６を介しデジタルカメラから直接的に、又はデジタルカメラ１３４から直接的にケーブル接続１３８を介しマイクロプロセッサベースユニット１１２に若しくは無線接続１４０を介しマイクロプロセッサベースユニット１１２に入力されてもよい。
【００１６】
出力装置は、変換を受けた最終的な画像を提供する。出力装置は、紙や他のハードコピー最終画像を提供するプリンタ若しくは他の出力装置とすることが可能である。出力装置はまた、最終的な画像をデジタルファイルとして提供する出力装置とすることが可能である。出力装置はまた、プリントされた画像などの出力と、ＣＤ若しくはＤＶＤなどのメモリユニット上のデジタルファイルの組み合わせを含むことが可能である。
【００１７】
本発明は、デジタル画像を生成する複数のキャプチャ装置と共に利用可能である。例えば、図２は、画像キャプチャ装置の１つがカラーネガ又はリバーサルフィルムのシーンをキャプチャするための従来の写真フィルムカメラと、フィルム上の現像された画像をスキャンし、デジタル画像を生成するフィルムスキャナー装置であるシステムを表すことが可能である。他のキャプチャ装置は、電子イメージャを有するデジタル放射性キャプチャユニット（図示せず）とすることが可能である。電子キャプチャユニットは、電子イメージャから信号を受信し、当該信号をデジタル形式に増幅及び変換し、画像信号をマイクロプロセッサベースユニットに伝送するアナログ・デジタルコンバータ／アンプを有することが可能である。
【００１８】
マイクロプロセッサベースユニット１１２は、意図した出力装置又はメディア上に満足いくように見える画像を生成するため、デジタル画像を処理する手段を提供する。本発明は、以下に限定されるものではないが、デジタル写真プリンタ及びソフトコピーディスプレイを含むことが可能な各種出力装置と共に利用可能である。マイクロプロセッサベースユニット１１２は、有用な画像が画像出力装置によって生成されるように、デジタル画像の全体的な明るさ、トーンスケール、画像構成などを調整するため、デジタル画像を処理するのに利用可能である。当業者は、本発明が、上述した画像処理機ののみに限定されないことを認識するであろう。
【００１９】
図２に示される一般的な制御コンピュータは、例えば、磁気ディスク（フロッピー（登録商標）ディスクなど）若しくは磁気テープ、光ディスク、光テープ若しくはマシーン可読バーコードなどの光記憶媒体、ＲＡＭ若しくはＲＯＭなどのソリッドステート電子記憶装置などを含むコンピュータ可読記憶媒体に格納されたプログラムを有するコンピュータプログラムプロダクトとして本発明を格納することが可能である。本発明の係るコンピュータプログラムの実現形態はまた、オフライン記憶装置によって示されるコンピュータプログラムを格納するため利用される他の何れかの物理装置若しくは媒体に格納されてもよい。本発明を説明する前に、本発明が好ましくは、パーソナルコンピュータなどの何れか周知のコンピュータシステム上で利用されることを示すことが理解を容易にする。
【００２０】
また、本発明がソフトウェア及び／又はハードウェアの組み合わせにより実現可能であり、同一の物理位置内に物理的に接続及び／又は配置される装置に限定されない。図２に示される装置の１以上が、リモートに配置され、ネットワークを介し接続可能である。これらの装置の１以上が、無線周波数リンクなどによって、直接的に又はネットワークを介し無線接続可能である。
【００２１】
本発明は、各種コンテクスト及び環境において利用されるかもしれない。特に各種モダリティからの画像を合成することに関連する一例となるコンテクスト及び環境は、限定することなく、医療イメージング、リモートセンシング、個人や物品の輸送に関連するセキュリティイメージングを含む。可視光をキャプチャするモダリティに特に関連する他の一例となるコンテクスト及び環境は、限定することなく、ホールセールデジタル写真加工（フィルム若しくはデジタル画像イン、デジタル処理、プリントアウトなどの一例となる処理ステップ若しくはステージに関する）、リテールデジタル写真加工（フィルム若しくはデジタル画像イン、デジタル処理、プリントアウト）、ホームプリンティング（ホームスキャンされたフィルム若しくはデジタル画像イン、デジタル処理、プリントアウト）、デスクトップソフトウェア（アルゴリズムをデジタル画像に適用するソフトウェア）、他のデジタルフルフィルメント（メディア若しくはウェブからのデジタル画像イン、デジタル処理、メディア上のデジタル形式による画像アウト、ウェブを介したデジタル形式、又はハードコピープリント上のプリント）、キオスク（デジタル若しくはスキャン入力、デジタル処理、デジタル若しくはスキャン出力）、モバイル装置（処理ユニット、ディスプレイユニット若しくは処理命令を与えるユニットとして利用可能なＰＤＡ若しくは携帯電話など）及びワールドワイドウェブを介し提供されるサービスを含む。
【００２２】
ここで図１を参照するに、本方法では、複数の新たな画像が時間的に順序付けされた画像の既存のデータベースに合成され、時間差閾値に基づきイベントグループに分類され、イベントグループ内において類似度に基づきイベントサブグループに分類される。新たな画像の特徴が評価され（１０）、新たな画像がこれらの特徴に基づきクラスタに順序づけ又はグループ化される（１２）。代表的な画像が、各クラスタにおいて選択される（１４）。新たな画像と時間的に重複したデータベースのセグメントが指定される（１６）。代表的な各画像に類似した１以上の抽出されたデータベース画像セットが、データベースに問い合わせることによって特定される（１８）。抽出された画像を含む異なるサブグループが、各クラスタに関連付けされ、新たな画像が関連するサブグループに割り当てられる（２２）。
【００２３】
データベースがイベントグループに分類された方法は、重要ではなく、イベントクラスタリングアルゴリズム若しくはマニュアル又は両者の組み合わせを利用して自動化することが可能である。同様のことが、イベントグループのサブグループへの分類に適用される。マニュアル分類は、自動分類に従って時間差閾値を当該閾値を利用してヒューリスティックに決定するのに利用可能である。ある実施例は、データベース画像は、Ｌｏｕｉ及びＰａｖｉｅによる米国特許第６，６０６，４１１Ｂ１に記載されるように、画像間のカラー類似度及び日時情報に基づき、イベント及びサブイベントに自動的に分類されている。
【００２４】
データベースは、類似度の基礎となる同一の特徴を用いたコンテンツベース画像抽出をサポートする。ある実施例では、Ｌｏｕｉ及びＰａｖｉｅによる２００２年２月１６日に発行された米国特許第６，３５１，５５６号に記載されるように（参照することによりここに含まれる）、小さなブロックに分割された各画像ブロックにおいて計算されるヒストグラムに基づくカラーマッチングが、画像間の類似性を計算するのに利用される。この類似度はまた、Ｌｏｕｉ及びＰａｖｉｅによる米国特許第６，６０６，４１１Ｂ１に記載される自動的なイベントクラスタリング方法におけるサブイベント境界を決定するのに利用された。あるいは、カラー、テクスチャ及びカラー構成などの低レベル特徴が、類似性を計算するのに利用可能である。カラー及びテクスチャ表現並びに類似性ベース抽出のための手順が、２００２年１１月１２日に発行されたＺｈｕ及びＭｅｈｒｏｔｒａの米国特許第６，４８０，８４０号に記載されている（参照することによりここに含まれる）。当該特許では、画像の主要なカラーが決定され、各主要カラーが、セグメント内のカラーレンジ、モーメント及び分布を含む属性セットによって記述される。テクスチャは、コントラスト、スケール及びアングルに関して記述される。２つの画像の間の類似度は、基礎となる特徴の類似性の加重合成として計算される。
【００２５】
受信時、新たな画像はキャプチャ日時情報を欠落し、又は信頼性の低い日時情報を有している。これら新たな画像は、１以上のソースから取得可能である。例えば、新たな画像は、キャプチャメタデータが偶然に消去されている写真加工中のフィルムネガ、スキャンされたプリントからの画像ファイル又は編集されたデジタル画像をスキャンすることによって取得されるＰｉｃｔｕｒｅＣＤ上にある可能性がある。新たな画像は、誤ってセットされた日付及び／又は時間を有するデジタルカメラからのものである可能性がある。これは、自動的に又は手動により決定可能である。例えば、以降の日時を示す日時情報は、自動的に無視することが可能である。
【００２６】
図３を参照するに、本方法の信頼性は、新たな画像に関する時間的順序情報が使用される場合に向上する。この場合、後述されるように、新たな画像の特徴が決定され（２１０）、新たな画像の時間的順序が確認される（２１１）。新たな画像の時間的順序は、新たな画像のエントリとデータベースへの分類に従って維持される。すなわち、新たな画像の時間に関する相対的なシーケンスに関する情報が利用され、当該相対的なシーケンスが、新たな画像のエントリ後にデータベースの時間順に維持される。（データベースへの挿入後、新たな画像は先に含まれたデータベース画像と共に分散される可能性がある。新たな画像のエントリ後、データベースは時間的な順序付けが維持される。）
新たな画像の時間的順序がまず確認される。これは、新たな画像に係るメタデータを抽出することによって実行可能である。例えば、ファイル発生の自動生成された日付が新たな画像に設けることが可能であり、又は新たな画像は相対的な時間的順序を規定するメタデータを含む一意的なファイル名を有するかもしれない。時間的順序はまた、記憶媒体の画像の物理的順序に基づき、又は順序を指定するユーザ入力を受け付けることによって確認することが可能である。入力画像の順序付けが、追加処理を通じて維持される。
【００２７】
新たな画像が受信された後、新たな各画像の１以上の画像特徴が決定される。この決定は、手動、半自動又は自動によるものとすることが可能である。使用される特徴が類似度の基礎となるものと同一であることが強く好まれる。ある実施例では、これらの特徴は、Ｌｏｕｉ及びＰａｖｉｅによる２００２年２月１６日に発行された米国特許第６，３５１，５５６号に記載されたブロックレベルカラーヒストグラムである。
【００２８】
新たな画像が、画像特徴に基づきクラスタに順序づけ／グループ化される。この順序付け／グループ化は、各種方法により実行可能であるが、当該グループ化はデータベースにおけるイベントグループのサブグループへの分類と同一の基礎に基づくことが大変好ましい。同一の分類手順の利用は、異なる分類手順の利用から生じる可能性がある異常分類の可能性に対する保証をするのに役立つ。ある実施例では、クラスタリングは、Ｌｏｕｉ及びＰａｖｉｅによる米国特許第６，３５１，５５６号に記載されるような近接画像のカラー類似性に基づき、画像の順序付けを維持する。
【００２９】
各クラスタの代表的な画像が選択される。この代表画像は、クラスタの他の画像と高い類似性を有し、新たな画像のグループ化に用いられる特徴に基づき選択することが可能である。代表画像は、クラスタのすべてのメンバーについて同一の指標の平均若しくはほぼ平均にある類似度の値を有する可能性がある。あるいは、代表画像は、時間的に順序付けされたグループの中間点における画像とすることが可能である。さらなる他の実施例は、各クラスタの代表画像の手動による選択である。
【００３０】
新たな画像に時間的に重複したデータベースのセグメントが指定される。当該セグメントはデータベース全体とすることが可能であるが、好ましくは、データベースの一部に限定される。セグメントの時間的な長さは、新たな画像に関連する利用可能な日時情報に基づき限定することが可能である。大部分のケースにおいて、これら新たな画像は、新たな画像の最後の日時と最も最近のデータベースの画像日時との間のデータベース部分をセグメントから排除するのに利用可能な最後の日時を有するであろう。最後の日時は、プリント若しくはフィルムからスキャンされたデジタル画像の作成日、電子メールによる新たな画像の受信日、又は直近のファイル作成日などとすることが可能である。最後の日時はまた、例えば、自動生成された質問への応答としてユーザにより供給可能である。（ユーザは、例えば、データベースの時間的なエンドに画像を追加するのでなく、本方法を利用することを選択することによって最後の日時を非明示的に供給することが可能である。）
本方法では、最後の日時は最も最近のデータベース画像日時より以降のものではない。最後の日時が以降である場合、本方法は利用されず、又は最も最近のデータベース画像日時より以前の最後の日時が確定可能となるまで新たな画像が収集される。この収集は、ユーザ入力に基づき行うことが可能である。
【００３１】
データベースの時間的に順序付けされたセグメントは、新たな画像の最後の日時より以前のすべての画像を含む可能性があるが、計算要求を低減するため、新たな画像の開始日時がまた確認されることが好ましい。開始日時がデータベースの最も以前の時間的なエンドより以降のものである場合、開始日時と最後の日時の又はそれらの間の日時を有するデータベース画像にセグメントを限定することによって、セグメントを縮小することが可能である。開始日時は、最後の日時と同様に確認することができる。
【００３２】
各クラスタからの代表画像は、類似画像についてデータベースをクエリするのに利用される。クエリ画像の順序付けは、最も最近のものを最初にすることにより維持される。各代表画像に類似するデータベース画像の１以上のセットがセグメントにおいて特定され、図４に示されるように、各代表画像の１以上の抽出された画像のセットを生じさせる。ここで使用される類似度は、任意のタイプのものとすることが可能であり。クラスタの順序付けとデータベースのサブグループの分類に使用されるものと同一のものとすることが可能である。ある実施例では、Ｌｏｕｉ及びＰａｖｉｅによる２００２年２月１６日に発行された米国特許第６，３５１，５５６号に記載されたブロックレベルカラーヒストグラムに基づく類似性が利用される。
【００３３】
クラスタとサブグループとの関連付けが取るに足らないものであるが、これがそのケースとなる可能性が低くなるように、各代表画像が新たなクラスタと同一の時間的順序により異なるサブグループの抽出された画像と一致する可能性がある。一般に、クラスタの時間的順序を維持しながら、新たなクラスタを既存のサブグループに割り当てるという問題は、コンフリクトを解消するためアルゴリズム的に解かれる必要がある。アルゴリズムは、画像類似度が低い識別力しか有しないと考えられる場合には、一致したサブグループの累積的な時間的期間を最小化するよう一致するサブグループを選択するか（図３の（２０１））、又は画像類似度が高い識別力を有すると考えられるときには、代表画像と各データベース画像セットの類似性を最大化するよう一致したサブグループを選択する（図３の（２０３））ことが現在好ましい。これら代替について以下で説明される。
【００３４】
本方法が利用されるかについての判定（図３の（２０５））は、合成されるすべての代表画像について上位ｍ個の画像の一致スコアの分布に基づく。代表画像と抽出された各画像の相対的な類似性が決定され、各類似度を生成する。類似度の分散は、残りの抽出画像より大きな各代表画像との類似性を有するすべての又は所定数の抽出画像を利用して評価される。分散が所定の閾値未満であるとき、グリーディーアルゴリズムアプローチが利用される。なぜなら、一致スコアは、それらが平均値の周囲にタイトにクラスタリングされている場合には識別できないためである。分散が所定の閾値以上であるとき、他方のアプローチが利用される。なぜなら、上位の抽出されたセットの画像についての一致レベルの間には大きな相違があるため、このケースでは、最適化ステップが順序付け制約に加えて一致スコアを考慮する必要がある。
【００３５】
これら２つの目標をバランスさせ、又はユーザがそれらの間の判断をするため他の出力を提供するなどの他の代替が可能である。
【００３６】
ここで図４を参照するに、ある実施例では、抽出したデータベース画像と新たな各画像クラスタとを関連付けるのにグリーディーアルゴリズムが利用される。“グリーディー”アルゴリズムは、直接的な又はローカルな情報のみに基づき、与えられた各ステップにおいてベストな代替を常に選択するアルゴリズムである。グリーディーアルゴリズムの利用は、低レベル（カラー、テクスチャ、カラー構成）特徴により生成される一致スコアが、画像間の精密な識別に利用可能でないという仮定に基づくものであり、すなわち、一致スコアの大きな相違のみが重要である。
【００３７】
Ｎ個の抽出されたセットのそれぞれからのデータベースセグメント内の上位ｍ個の画像に対応するサブイベントが、タイムスタンプを減少させることによってソートされる（最も最近のものを最初に）。ｍの値は、好ましくは３〜２０の範囲内の整数であり、例えば、５である。Ｎは、クラスタの新たな画像の個数である。図４は、アルゴリズムが処理するデータのセットアップを示す。
【００３８】
グリーディーアルゴリズムは、新たなグループを割り当てる際、より最近のサブイベントに古いサブイベントよりも高い優先度を与えるという基準を保証するため、新たなグループを既存のサブイベントに割り当てるのに利用される。このアルゴリズムは、新たな画像の順序付けを維持する最短のスタート・ツー・エンド（ｓｔａｒｔ  ｔｏ  ｅｎｄ）時間（新たなグループが追加される最初のサブイベントから最後のサブイベントにスタートする時間）が選択されることを保証する。新たな画像を既存のサブイベントに割り当てるグリーディーアルゴリズムは、以下の通りである。
【００３９】
ｊに対応するサブイベントにｉに対応する新たなクラスタの画像を、ｊの日時が新たなクラスタ（ｉ−１）からの画像が割り当てられたサブイベントの日時より以前のものである（ｉ＝０の日時が現在の日時であるとみなされる）場合に割当て、ｉ＝１〜Ｎ及びｊ＝１〜ｍについて繰り返される。（ただし、ｊは、抽出した画像グループを時間の降順により表し、ｉは、最後から始まり最初に続く新たなクラスタの代表画像を表す。）ｊ＞ｍの（従って、割当てが不可であった）場合、番号ｉは未割当てと記され、続けられる。セグメントに適合し得ないクエリは、解法リストの一部である最も近い近傍に隣接した挿入された新たなイベントに割り当てられる。
【００４０】
第２の代替は、順序付け制約を満たすことに加えて一致スコアが重要であるという仮定に基づき、一致スコアを最大化するダイナミックプログラミングアルゴリズムを有する。図５は、当該アルゴリズムのデータ構造を示す。
【００４１】
１．後述されるように、長さＮｍのセルのアレイＡを生成する時間の降順により上位ｍ個の抽出画像を配置する。各セルｉは以下のデータを格納している。
【００４２】
ａ）Ｑ（ｉ）：当該画像が抽出されたクエリ画像のシーケンス番号（この番号のため、セルラベルという用語が使用される。）シーケンス番号は、最も最近の画像から始まる挿入される新たなグループの時間順序付けを維持することに留意されたい。
【００４３】
ｂ）Ｓ（ｉ）：クエリ画像とのＡのｉ番目の抽出画像の類似度
ｃ）Ｌ（ｉ，ｊ）：長さｊのリスト（ただし、ｊ＝１，２，．．．，Ｎは、Ａのアレイインデックスを含む。）Ｌｋ（ｉ，ｊ）をリストｌ（ｉ，ｊ）のｋ番目の要素を表すとする。リストを有効にするため、各要素は、Ｌｋ（ｉ，ｊ）＞Ｌｋ−１（ｉ，ｊ）の基準を充足する必要がある。各リストＬ（ｉ，ｊ）は、Ａの最初のｉ個のセルが考慮されるとき、長さｊの抽出画像のベストな有効な選択（最も高い累積類似度を生成するもの）を与える。有効なより大きなリストを生成することは不可能である可能性があるため、多数のセルがＮ個未満のリストを有することに留意されたい。リストの長さは、位置ｉ（ｉ＜Ｎ）などにおけるアレイ位置によって制限される。リストの最大長は、高々ｉとすることが可能である。
【００４４】
ｄ）Ｍ（ｉ，ｊ）：
【００４５】
【数１】
2008532180.tif 000003
により与えられるリストＬ（ｉ，ｊ）の累積スコア
目的は、最大累積一致スコアを生成するセルラベル１〜Ｎによる順序によりセルセットを検出することである。
【００４６】
２．Ｌ（１，１）＝１の初期化
各リストを以下の順序により構成する。
【００４７】
【表１】
2008532180.tif 000004
３．生成される最長のリストが、クエリ画像の抽出画像へのベストな割当てを提供する。複数の候補が存在する場合、より低いインデックス番号を有するセルからのリストが解法となる（これらの割当ては現在の時間により近いため）。クエリｑに対応するクラスタに属する新たな画像が、抽出画像Ｌｋ（ｉ，ｊ）に対応するサブイベントに割り当てられる。（ただし、Ｑ（Ｌｋ（ｉ，ｊ））＝ｑである。）
４．解法リストの長さがＮ未満である場合、すべての順序付け制約に適合する割当ては検出されなかった。この場合、タイムラインに適合不可なクエリが、解法リストの一部である最も近い近傍に隣接して挿入される新たなイベントに割り当てられる。
【図面の簡単な説明】
【００４８】
【図１】図１は、本方法の実施例のフローチャートである。
【図２】図２は、本システムの実施例の図解図である。
【図３】図３は、本方法の他の実施例のフローチャートである。
【図４】図４は、図３の方法のデータベースをクエリする図である。
【図５】図５は、図４の方法のサブグループ関連付けアルゴリズムの選択されたものに対するデータ構造の図である。
【図１】
2008532180.tif 000005
【図２】
2008532180.tif 000006
【図３】
2008532180.tif 000007
【図４】
2008532180.tif 000008
【図５】
2008532180.tif 000009
【国際調査報告】
2008532180.tif 000010
2008532180.tif 000011
2008532180.tif 000012