(57)【要約】【課題】データファイルをイベントベースでクラスタリングする。【解決手段】タイムスタンプ、ＧＰＳデータ、ファイル名、サイズ、及びタイプ、テキスト注釈、音声注釈、各データファイルのメタデータタグヘッダ又は内容の低レベル特徴から選択される１つ以上の要素を抽出し、少なくとも１つのデータファイルの抽出された１つ以上の要素を、そのデータファイル又は１つ以上の隣接するデータファイルから抽出された要素との比較に基づいて１つ以上の類似性マトリックスを生成し、異なる範囲Ｌの１つ以上のカーネル関数を類似性マトリックスに適用することにより１つ以上の初期境界区分を決定し、決定された境界から１つ以上の境界を選択するために１つ以上のアルゴリズムを使用し、さらに、選択された境界に基づいてデータファイルを編成することにより、データファイルの集合の時間的イベントクラスタリングを実行する。【選択図】図１
2006216026.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）タイムスタンプ、全地球測位衛星データ、ファイルサイズ、ファイルタイプ、ファイル名、テキスト注釈、音声注釈、データ・ファイルのそれぞれのメタデータ・タグ・ヘッダ若しくは内容からの低レベル特徴から選択される１つ以上の要素を抽出し、
（ｂ）少なくとも１つのデータ・ファイルの抽出された１つ以上の要素を、そのデータ・ファイル若しくは１つ以上の隣接するデータ・ファイルからの抽出された要素と比較することに基づいて１つ以上の類似性マトリックスを生成し、
（ｃ）異なる範囲Ｌの１つ以上のカーネル関数を類似性マトリックスに適用することによって、１つ以上の初期境界区分を決定し、
（ｄ）１つ以上のアルゴリズムを使用して前記ステップ（ｃ）において決定された境界から１つ以上の境界を選択し、
（ｅ）選択された境界に基づいてデータ・ファイルを編成すること、
を含む、データ・ファイルのコレクションの時間的イベント・クラスタリングのための方法。
【請求項２】
前記ステップ（ｄ）における１つ以上のアルゴリズムのうちの少なくとも１つが動的計画法アルゴリズムである、請求項１に記載の方法。
【請求項３】
前記ステップ（ｄ）における動的計画法が、最適数のクラスタを決定するために、以下の方程式（１３）によって示されるようなコスト測度Ｌ*を利用する、請求項２に記載の方法。
2006216026.tif 000017
【請求項４】
ステップ（ｄ）における１つ以上のアルゴリズムの少なくとも１つがベイズ情報量規準アルゴリズムである、請求項１に記載の方法。
【請求項５】
前記データ・ファイルがディジタル写真を含む、請求項２又は請求項４に記載の方法。
【請求項６】
前記抽出された要素がタイムスタンプである、請求項５に記載の方法。
【請求項７】
各ディジタル写真から抽出されるタイムスタンプが時系列に基づいてこれら写真を順序付けるために使用される、請求項６に記載の方法。
【請求項８】
前記ベイズ情報量規準が各境界を繰り返し試験するために使用される、請求項４に記載の方法。
【請求項９】
各ディジタル写真から抽出されるタイムスタンプが、時系列に基づいてこれら写真を順序付けるために使用される、請求項６に記載の方法。
【請求項１０】
（ａ）写真ｔn、ここでＮはコレクション内の写真の数でありｎ＝１，．．．，Ｎである、のそれぞれに対しタイムスタンプ（ｔ）を抽出することと、
（ｂ）ｔ1＜ｔ2＜ｔ3＜．．．＜ｔNになるように、時系列のタイムスタンプに基づいて写真を順序付けることと、
（ｃ）ディジタル写真若しくは１つ以上の隣接するディジタル写真から抽出されたタイムスタンプと比較して、ディジタル写真のそれぞれから抽出されるタイムスタンプに基づいて１つ以上の類似性値を算出することと、
（ｄ）類似性値に基づいて１つ以上の類似性マトリックスを生成することと、
（ｅ）異なる範囲Ｌの１つ以上のカーネル関数を類似性マトリックスに適用して、それぞれのＬに対し１つ以上の新規性スコアを生成することと、
（ｆ）新規性スコアから１つ以上の初期区分を決定することと、
（ｇ）前記ステップ（ｅ）及び（ｆ）において決定された境界から１つ以上の境界を選択するために１つ以上のアルゴリズムを使用することと、
（ｈ）前記選択された境界に基づいて写真を少なくとも２つのクラスタに編成することと、
を含む、複数のディジタル写真の時間的イベント・クラスタリングのための方法。
【請求項１１】
ステップ（ｇ）における１つ以上のアルゴリズムの少なくとも１つが動的計画法アルゴリズムである、請求項１０に記載の方法。
【請求項１２】
ステップ（ｇ）におけるアルゴリズムの少なくとも１つは、
（ｉ）写真のコレクションを２つのクラスタに分類する区分を構築し、
（ｊ）更なる境界線が写真のコレクションをＬ個のクラスタ、ここでＬ＞２、に分類するように更なる境界を生成し、
（ｋ）ｍ−１境界及び更なる境界による最適区分に基づいてｍ個の境界を備えた最適区分を選択し、
（ｌ）Ｌ、ここでＬ＜Ｎ、を増加させるためにステップ（ｊ）及び（ｋ）を繰り返し、
（ｍ）最適数のクラスタＬ*を選択し、
（ｎ）最適数のクラスタに対する最適区分から元にトレースすることによって１つ以上の境界を識別すること、
を含む、請求項１０に記載の方法。
【請求項１３】
ステップ（ｍ）における最適数のＬ*が以下の式のように算出される、請求項１２に記載の方法。
2006216026.tif 000018
【請求項１４】
ステップ（ｇ）における１つ以上のアルゴリズムの少なくとも１つがベイズ情報量規準アルゴリズムである、請求項１０に記載の方法。
【請求項１５】
前記ベイズ情報量規準が各境界を反復的に試験するために使用される、請求項１４に記載の方法。
【請求項１６】
ステップ（ｇ）における１つ以上のアルゴリズムのうちの少なくとも１つは、
（ｊ）以下の式を生成し、
2006216026.tif 000019
（ｋ）項、L(bl-1,bl)+L(b,bl+1)、が項、L(bl-1,bl+1)+λ/2(log(bl+1,bl-1))、より大きい場合、選択された最適境界区分の集合における境界区分を選択すること、
を含む、請求項１０に記載の方法。
【請求項１７】
（ａ）写真のそれぞれの少なくとも１つのメタデータ・タグ要素からタイムスタンプを抽出することと、
（ｂ）タイムスタンプに基づいてディジタル写真のコレクションを順序付けすることと、
（ｃ）１つ以上の写真のタイムスタンプを、その写真のタイムスタンプ若しくは写真のコレクション内の１つ以上の隣接する写真のタイムスタンプと比較することに基づいて写真のコレクション内の１つ以上の境界を計算することと、
（ｄ）アルゴリズムを使用してステップ（ｃ）において計算された境界のサブセットを選択することと、
（ｅ）選択された境界線に基づいて写真のコレクションを順序付けすることと、
を含む、ディジタル写真のコレクションを順序付けする機能を実行することをコンピュータによって実行可能なプログラム。
【請求項１８】
動的計画法アルゴリズムがステップ（ｄ）において使用される、請求項１７に記載のプログラム。
【請求項１９】
ベイズ情報量規準アルゴリズムがステップ（ｄ）において使用される、請求項１７に記載のプログラム。
【請求項２０】
前記方法は、ディジタル写真のコレクションを順序付けるための装置を使用して実行され、該装置が、
（ａ）１つ以上のプロセッサを含み、該プロセッサが、
（ｉ）各ディジタル写真データ・ファイルからタイムスタンプを抽出し、
（ｉｉ）年代順にタイムスタンプを順序付け、
（ｉｉｉ）写真コレクションをクラスタリングするための初期境界を生成し、
（ｉｖ）少なくとも１つのアルゴリズムを用いてステップ（ａ）の（ｉｉｉ）において生成された境界のリストのサブセットを選択し、
（ｖ）境界の選択されたサブセットに基づいてディジタル写真のコレクションを順序付けることが可能であり、
（ｂ）前記１つ以上のプロセッサによって処理されるとき、前記装置に以下のステップ（ｉ）乃至（ｖ）のステップを実行させる操作を記憶させた機械可読媒体を含み、
（ｉ）写真のリストを作成し、
（ｉｉ）年代順に写真のリストを順序付け、
（ｉｉｉ）写真コレクションをクラスタリングするための最初の境界を作成し、
（ｉｖ）少なくとも１つのアルゴリズムを用いてステップ（ｂ）の（ｉｉｉ）において生成された境界のリストのサブセットを選択し、
（ｖ）選択された境界に基づいてディジタル写真のコレクションを分類する、
請求項１０に記載の方法。
【請求項２１】
少なくとも１つのアルゴリズムで境界のリストを選択することが動的計画法アルゴリズムを用いて達成される、請求項２０に記載の方法。
【請求項２２】
少なくとも１つのアルゴリズムで境界のリストを選択することがベイズ情報量規準を計算することによって達成される、請求項２０に記載の方法。
【請求項２３】
ディジタル写真コレクションを順序付けるための装置であって、該装置は、
ディジタルカメラから前記写真コレクションのデータストリームを入力したりユーザからの指示を入力する入力部と、
前記入力した写真コレクションのデータストリームに対する処理を実行する少なくとも１つのプロセッサと、
該プロセッサによる実行の際の作業領域を形成すると共にプログラムや処理対象としての前記入力した写真コレクションのデータストリーム、及び処理されたデータを格納する記憶部と、
処理内容や処理結果を表示画面上に表示する表示部と、
データを出力する出力部とを含み、
前記プロセッサは、前記記憶部に格納した処理対象のデータストリームに対し、
（１）前記データストリームに含まれる各写真に対するタイムスタンプの抽出して、抽出した時系列のタイムスタンプに基づいて写真を順序付け、
（２）１つ以上の隣接するディジタル写真から抽出されたタイムスタンプと比較して、ディジタル写真のそれぞれから抽出されるタイムスタンプに基づいて１つ以上の類似性値を算出し、該類似性値に基づいて１つ以上の類似性マトリックスを生成し、
（３）異なる範囲の１つ以上のカーネル関数を類似性マトリックスに適用して、それぞれの範囲に対し１つ以上の新規性スコアを生成し、
（４）前記新規性スコアに基づき、前記写真コレクション内の境界を決定し、
（５）該決定した境界に基づき写真コレクションの編成を行う、
前記装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はディジタル写真コレクションをクラスタリングするための方法に関する。すなわち、本発明は、データ・ファイルのコレクションの時間的イベント・クラスタリングのための方法、複数のディジタル写真の時間的イベント・クラスタリングのための方法、及び、ディジタル写真のコレクションを順序付けする機能を実行することをコンピュータによって実行可能なプログラムに関する。
【背景技術】
【０００２】
ディジタルカメラは広範囲に使用されるようになり、その結果、消費者はディジタル写真のコレクションをますます大きく蓄積させている。こうしたコレクションを管理し、編成し、ブラウジング（走査検索）するのに役立つ自動ツールが必要である。消費者が写真を管理するための多数のツールが今では存在するが、その大部分はサムネイルのライト・テーブルを年代順に特徴づける。しかしながら、ユーザは一般に、「イベント」ベースで写真を年代順にクラスタに分類するものである。
【０００３】
「イベント」ベースで年代順に写真をクラスタリングすることは、写真を撮影した時間間隔を区分化することに相当する。イベント境界の階層的集合から単一レベルにある境界を選択することは、写真の数の計算に二次関数的な複雑性をもたらす結果になることがある。ゆえに、多数の写真コレクションを区分化するために処理時間が何秒もかかったり、又は数分にもなることがある。このことは、対話形式用途に対するこうした方法の適合性を制限する。
そこで、ディジタルカメラの多数の写真コレクションを、処理時間を増加させることなく簡易な方法でイベントベースで区分する方法が望まれる。
本発明に関連する文献には以下のものがある。
特許文献１は、音声信号内の変化点の決定に関する。重要変化が生じる点が過去あるいは未来との類似性を有することの着目するものであり、ベクトルパラメータ化が用いられる。
特許文献２は、メディアの要約システムと方法に関する。そこでは、順序付けされた情報（例えば、音声、ビデオ、テキストデータなど）のストリームがパラメータ化され、パラメータ化されたストリームとウィンドウ化されたストリームの類似性が決定されマトリックス化される。そして、その類似性マトリックスに確率論的なマトリックス分解が行われてセグメント化され、その主要セグメントにより情報の主要成分を取得する。
しかし、いずれの文献に開示された技術によっても、上記問題点は解決されていない。
【特許文献１】米国特許第６，５４２，８６９Ｂ１号
【特許文献２】米国特許公開第２００３／００４８９４６Ａ１号
【非特許文献１】マシュー・クーパー(Matthew Cooper)他著、「ディジタル写真コレクションのための時間的イベント・クラスタリング(Temporal Event Clustering for Digital Photo Collections)」、ＭＭ'０３、２００３年１１月２日−８日、米国カリフォルニア州バークリー、ｐ．１０
【非特許文献２】マシュー・クーパー(Matthew Cooper)他著、「時間及び内容を用いたディジタル写真の自動編成(Automatically Organizing Digital Photographs Using Time and Content)」、画像処理に関するＩＥＥＥ国際会議議事録、２００３年９月１４日、ｐ．４
【非特許文献３】マシュー・クーパー(Matthew Cooper)他著、「ビデオ自己類似性分析によるシーン境界検出(Scene Boundary Detection via Video Self-Similarity Analysis)」、画像処理に関するＩＥＥＥ国際会議議事録、２００１年、p．３７８−３８１
【非特許文献４】Ｐ．フラグクー(P. Fragkou)他著、「リニア・テキスト・セグメンテーションのための動的計画アルゴリズム(A Dynamic Programming Algorithm for Linear Text Segmentation)」、http://citeseer.ist.psu.edu/fragkou02dynamic.html、ｐ．１−１４、図面５枚
【非特許文献５】アンドレアス・ギルゲンゾーン(Andreas Girgensohn)他著、「大きな写真コレクションの管理の簡略化(Simplifying the Management of Large Photo Collections)」、人間／コンピュータ・インタラクション(Human-Computer Interaction)、ＩＮＴＥＲＡＣＴ'０３、ＩＯＳプレス、２００３年、p．１９６−２０３
【非特許文献６】マイケルＭ．ゴドイン(Michael M. Goodwin)他著、「線形判別分析及び動的計画法を用いた特徴／空間クラスタリングによる音声セグメンテーション(Audio Segmentation by Feature-Space Clustering Using Linear Discriminant Analysis and Dynamic Programming)」、信号処理の音声及び音響効果への応用に関する２０００ＩＥＥＥセミナー(2000 IEEE Workshop on Application of Signal Process to Audio and Acoustics)、２００３年１０月１９日−２２日、ニューヨーク州ニューパルツ、ｐ．１３１−１３４
【非特許文献７】エイドリアン・グラハム(Adrian Graham)他著、「パーソナル・ディジタル・ライブラリ内の写真ブラウジング用の要素としての時間(Time as Essence for Photo Browsing Through Personal Digital Libraries)」、ディジタル・ライブラリに関する合同会議議事録、２００２年７月１３日−１７日、米国オレゴン州ポートランド、ｐ．１０
【非特許文献８】マークＨ．ハンセン(Mark H. Hansen)他著、「モデル選択及び最短記述長の原理(Model Selection and the Principle of Minimum Description Length)」、米国統計協会のＪ、２００１年、９６（４５４）：７４６−７４、ｐ．１−５０
【非特許文献９】ジョン・ハーティガン(John Hartigan)著、「完全最適化による区画(Partition by Exact Optimization)」、第６章、「クラスタリング・アルゴリズム(Clustering Algorithms)」、ウィリー・アンド・サンズ(Wily & Sons)、１９７５年、ｐ．１３０−１４２
【非特許文献１０】アレハンドロ・ジェームス(Alejandro Jaimes)他著、「消費者の写真における反復性ビジュアル・セマンティクスの発見(Discovering Recurrent Visual Semantics in Consumer Photographs)」、画像処理に関するＩＥＥＥ国際会議議事録、２０００年、ｐ．４
【非特許文献１１】シャン・チー(Xiang Ji)他著、「異方性拡散及び動的計画法を用いた領域独立のテキスト・セグメンテーション(Domain-independent Text Segmentation Using Anisotropic Diffusion and Dynammic Programming)」、ＡＣＭ  ＳＩＧＩＲ議事録、２００３年、ｐ．３２２−３２９
【非特許文献１２】アレキサンダーＣ．ルイ(Alexander C. Loui)他著、「自動化イベント・クラスタリング及びディジタル・アルバム化のための消費者写真の品質スクリーニング(Automated Event Clustering and Quality Screening of Consumer Pictures for Digital Albuming)」、マルチメディアに関するＩＥＥＥトランザクション、第５巻第３号、２００３年９月、ｐ．３９０−４０２
【非特許文献１３】アレキサンダーＣ．ルイ(Alexander C. Loui)他著、「自動画像イベント・セグメンテーション及びアルバム化応用のための品質スクリーニング(Automatic Image Event Segmentation and Quality Screening for Albuming Applications)」、マルチメディア及びエクスポに関するＩＥＥＥ国際会議、２０００年７月、ニューヨーク州ニューヨーク市、ｐ．４
【非特許文献１４】アレキサンドラ・モジュシロウィック(Aleksandra Mosjsilovic)他著、「ＩＳｅｅ：画像ライブラリ・ナビゲーション用の知覚機能(ISee: Perceptual Features for Image Library Navigation)」、ＳＰＩＥヒューマン・ビジョン及び電子画像化の議事録、２００２年、ｐ．１２
【非特許文献１５】モル・ネイアマン(Mor Naaman)他著、「地理座標を備えたディジタル写真用の自動編成(Automatic Organization for Digital Photographs with Geographic Coordinates)」、ＪＣＤＬ'０４、２００４年６月７日−１１日、米国アリゾナ州タスコン、ｐ．５３−６２
【非特許文献１６】ステファン・ライター(Stephan Reiter)他著、「多数の選別器フュージョン及び動的計画法を用いた会合イベントのセグメンテーション及び分類(Segmentation and Classification of Meeting Events using Multiple Classifier Fusion and Dynamic Programming)」、ヒューマン・マシン・コミュニケーション協会(Institute of Human-Machine-Communication)、ミュンヘン工業大学(Technische Universitat Munchen)、ドイツ、ミュンヘン、ｐ．４
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、スケール・スペース分析、ならびに、テキスト及びビデオストリームのセグメント化に対しこの分析を適用することに関連している。スケール・スペース分析において、差分特徴はデータ・セットから抽出され、可変標準偏差のガウス型カーネル関数でスムージングした後に検査される。多数のスムージング・フィルタが変動スケールで境界を示す。こうした境界は検出され、微細スケールから粗スケールまでトレースされる。最終セグメント境界は、スケールを越える最大量の強度及び範囲を含む異なる基準に従って選択される。この情報は、（コンテキストが変化したデータ内の点のみを識別する）最終平面、又は（イベントのみならず、そのイベント内のサブ・イベントも検出する）階層的セグメント化を構築するために使用できる。
【課題を解決するための手段】
【０００５】
本発明において、データ・ファイルのイベントベースのクラスタリングは、動的計画法（ＤＰ）及びベイズ情報量規準（ＢＩＣ）に基づく方法を使用してアドレス指定できる。データ・ファイルは、メタデータ・タグ情報と共に格納される固有情報から構成され、このメタ・タグは固有情報を格納するために使用されるパラメータに関係がある。例えば、ディジタル写真のデータ・ファイルは、写真を構成する画素、ならびに、ファイルのタイプ、ファイルのサイズ、タイムスタンプ、及び写真を撮影した場所を示す全地球測位衛星位置データを含み得るメタデータ・タグを含んでいる。ディジタル写真の場合、ＤＰ及びＢＩＣの各方法は、例えば、類似性マトリックスを使用する類似性に基づくクラスタリング基準よりもかなり高速に作業を実行する。類似性分析が潜在的なイベント境界の集合を識別するための前処理に使用されることもできるが、どんな方法も前処理に使用することができる。
【０００６】
候補イベント境界の集合が与えられると、こうした方法は、写真のタイムスタンプを必要とするにすぎない。あるいはまた、順位づけ基準として、メタデータ・タグ又は内容に基づく特徴が使用できる。メタデータ・タグが、例えばタイムスタンプ若しくは全地球測位衛星位置データを含み得る一方で、内容に基づく特徴は、カラーヒストグラムや下位離散的コサイン変換係数などの低レベル特徴を含むことがある。さらに、非タイムスタンプベースの要素（例えば、メタデータ特徴又は内容に基づく特徴）に従って写真が順序づけできるが、一方、タイムスタンプに基づく比較もまだ可能であり、その逆の場合も同じである。
【０００７】
タイムスタンプが抽出される発明の実施の形態において、順序付けは、時間順位を上下させることに基づいて実行することができる。英数字ストリングを抽出することができる発明の実施の形態において、順序付けは、英数字ストリングの第１、第２、若しくは最後の文字のアルファベット順に基づくこともできる。あるいはまた、順序付けは、英数字ストリングにおける文字の数、及び、このストリングのサイズの増減若しくはこのストリングの長さとストリングにおける文字のアルファベット順の組み合わせに基づいていることもある。ファイルのサイズを抽出することができる発明の実施の形態において、順序付けは、ファイルのサイズの増減だけで、又は、上記の他の順序付け規則の一部との組み合わせに基づいていることもある。複数の要素を抽出することができる発明の実施の形態において、順序付けは上記の順序付け規則の組み合わせに基づいていることもある。
【０００８】
本発明は上記の事情を鑑みてなされたものであり、ＤＰ若しくはＢＩＣに基づいてクラスタ境界を決定するためにディジタル写真を分析し、ブラウジング若しくは検索するための方法を提供する。このようにして、ディジタル写真のコレクションは、さらに高速に且つ効率的にコレクションに編成されることができる。この方法は、ディジタル写真だけでなく、ビデオ及び音声ストリームを含む他の形式の媒体のセグメント化にも適用されることができる。こうした実施の形態において、ビデオ若しくは音声媒体のストリーム内の各フレームが、データ・ファイルをデータ・ファイルの集合に構成することができる。
【０００９】
本発明によるシステム及び方法の種々の例示的な実施の形態において、データ・ファイルの望ましい集合は、タイムスタンプを検査し、そのタイムスタンプに基づいてデータ・ファイルの順序付けをし、データ・ファイルのそれぞれのタイムスタンプを比較し、さらに、写真コレクションのクラスタリングに伴う計算の複雑性を軽減する方法を使用することによって編成されることができる。一実施の形態において、ＢＩＣは、計算ステップを加速させ、これによって、写真のコレクションを編成する際に伴う計算の複雑性を軽減するために使用することができる。他の例示的な実施の形態において、ＤＰ方法は、計算ステップを加速し、写真のコレクションを編成する際に伴う計算の複雑性を軽減するために使用できる。
【００１０】
本発明の請求項１に記載の発明は、（ａ）タイムスタンプ、全地球測位衛星データ、ファイルサイズ、ファイルタイプ、ファイル名、テキスト注釈、音声注釈、データ・ファイルのそれぞれのメタデータ・タグ・ヘッダ若しくは内容からの低レベル特徴から選択される１つ以上の要素を抽出し、（ｂ）少なくとも１つのデータ・ファイルの抽出された１つ以上の要素を、そのデータ・ファイル若しくは１つ以上の隣接するデータ・ファイルからの抽出された要素と比較することに基づいて１つ以上の類似性マトリックスを生成し、（ｃ）異なる範囲Ｌの１つ以上のカーネル関数を類似性マトリックスに適用することによって、１つ以上の初期境界区分を決定し、（ｄ）１つ以上のアルゴリズムを使用して上記ステップ（ｃ）において決定された境界から１つ以上の境界を選択し、（ｅ）選択された境界に基づいてデータ・ファイルを編成すること、を含む、データ・ファイルのコレクションの時間的イベント・クラスタリングのための方法である。
【００１１】
本発明の請求項２に記載の発明は、請求項１に記載の方法において、上記ステップ（ｄ）における１つ以上のアルゴリズムのうちの少なくとも１つが動的計画法アルゴリズムであることを特徴とする。
【００１２】
本発明の請求項３に記載の発明は、請求項２に記載の方法において、上記ステップ（ｄ）における動的計画法が、最適数のクラスタを決定するために、以下の方程式（１３）によって示されるようなコスト測度Ｌ*を利用することを特徴とする。
2006216026.tif 000003
【００１３】
本発明の請求項４に記載の発明は、請求項１に記載の方法において、上記ステップ（ｄ）における１つ以上のアルゴリズムの少なくとも１つがベイズ情報量規準アルゴリズムであることを特徴とする。
【００１４】
本発明の請求項５に記載の発明は、請求項２又は請求項４に記載の方法において、上記データ・ファイルがディジタル写真を含むことを特徴とする。
【００１５】
本発明の請求項６に記載の発明は、請求項５に記載の方法において、上記抽出された要素がタイムスタンプであることを特徴とする。
【００１６】
本発明の請求項７に記載の発明は、請求項６に記載の方法において、各ディジタル写真から抽出されるタイムスタンプが時系列に基づいてこれら写真を順序付けるために使用されることを特徴とする。
【００１７】
本発明の請求項８に記載の発明は、請求項４に記載の方法において、上記ベイズ情報量規準が各境界を繰り返し試験するために使用されることを特徴とする。
【００１８】
本発明の請求項９に記載の発明は、請求項６に記載の方法において、各ディジタル写真から抽出されるタイムスタンプが、時系列に基づいてこれら写真を順序付けるために使用されることを特徴とする。
【００１９】
本発明の請求項１０に記載の発明は、（ａ）写真ｔn、ここでＮはコレクション内の写真の数でありｎ＝１，．．．，Ｎである、のそれぞれに対しタイムスタンプ（ｔ）を抽出することと、（ｂ）ｔ1＜ｔ2＜ｔ3＜．．．＜ｔNになるように、時系列のタイムスタンプに基づいて写真を順序付けることと、（ｃ）ディジタル写真若しくは１つ以上の隣接するディジタル写真から抽出されたタイムスタンプと比較して、ディジタル写真のそれぞれから抽出されるタイムスタンプに基づいて１つ以上の類似性値を算出することと、（ｄ）類似性値に基づいて１つ以上の類似性マトリックスを生成することと、（ｅ）異なる範囲Ｌの１つ以上のカーネル関数を類似性マトリックスに適用して、それぞれのＬに対し１つ以上の新規性スコアを生成することと、（ｆ）新規性スコアから１つ以上の初期区分を決定することと、（ｇ）上記ステップ（ｅ）及び（ｆ）において決定された境界から１つ以上の境界を選択するために１つ以上のアルゴリズムを使用することと、（ｈ）上記選択された境界に基づいて写真を少なくとも２つのクラスタに編成することと、を含む、複数のディジタル写真の時間的イベント・クラスタリングのための方法である。
【００２０】
本発明の請求項１１に記載の発明は、請求項１０に記載の方法において、ステップ（ｇ）における１つ以上のアルゴリズムの少なくとも１つが動的計画法アルゴリズムであることを特徴とする。
【００２１】
本発明の請求項１２に記載の発明は、請求項１０に記載の方法において、ステップ（ｇ）におけるアルゴリズムの少なくとも１つは、（ｉ）写真のコレクションを２つのクラスタに分類する区分を構築し、（ｊ）更なる境界線が写真のコレクションをＬ個のクラスタ、ここでＬ＞２、に分類するように更なる境界を生成し、（ｋ）ｍ−１境界及び更なる境界による最適区分に基づいてｍ個の境界を備えた最適区分を選択し、（ｌ）Ｌ、ここでＬ＜Ｎ、を増加させるためにステップ（ｊ）及び（ｋ）を繰り返し、（ｍ）最適数のクラスタＬ*を選択し、（ｎ）最適数のクラスタに対する最適区分から元にトレースすることによって１つ以上の境界を識別すること、を含むことを特徴とする。
【００２２】
本発明の請求項１３に記載の発明は、請求項１２に記載の方法において、ステップ（ｍ）における最適数のＬ*が以下の式のように算出されることを特徴とする。
2006216026.tif 000004
【００２３】
本発明の請求項１４に記載の発明は、請求項１０に記載の方法において、ステップ（ｇ）における１つ以上のアルゴリズムの少なくとも１つがベイズ情報量規準アルゴリズムであることを特徴とする。
【００２４】
本発明の請求項１５に記載の発明は、請求項１４に記載の方法において、上記ベイズ情報量規準が各境界を反復的に試験するために使用されることを特徴とする。
【００２５】
本発明の請求項１６に記載の発明は、請求項１０に記載の方法において、ステップ（ｇ）における１つ以上のアルゴリズムのうちの少なくとも１つは、（ｊ）以下の式を生成し、
2006216026.tif 000005
（ｋ）項、L(bl-1,bl)+L(b,bl+1)、が項、L(bl-1,bl+1)+λ/2(log(bl+1,bl-1))、より大きい場合、選択された最適境界区分の集合における境界区分を選択すること、を含むことを特徴とする。
【００２６】
本発明の請求項１７に記載の発明は、（ａ）写真のそれぞれの少なくとも１つのメタデータ・タグ要素からタイムスタンプを抽出することと、（ｂ）タイムスタンプに基づいてディジタル写真のコレクションを順序付けすることと、（ｃ）１つ以上の写真のタイムスタンプを、その写真のタイムスタンプ若しくは写真のコレクション内の１つ以上の隣接する写真のタイムスタンプと比較することに基づいて写真のコレクション内の１つ以上の境界を計算することと、（ｄ）アルゴリズムを使用してステップ（ｃ）において計算された境界のサブセットを選択することと、（ｅ）選択された境界線に基づいて写真のコレクションを順序付けすることと、を含む、ディジタル写真のコレクションを順序付けする機能を実行することをコンピュータによって実行可能なプログラムである。
【００２７】
本発明の請求項１８に記載の発明は、請求項１７に記載のプログラムにおいて、動的計画法アルゴリズムがステップ（ｄ）において使用されることを特徴とする。
【００２８】
本発明の請求項１９に記載の発明は、請求項１７に記載のプログラムにおいて、ベイズ情報量規準アルゴリズムがステップ（ｄ）において使用されることを特徴とする。
【００２９】
本発明の請求項２０に記載の発明は、請求項１０に記載の方法において、上記方法は、ディジタル写真のコレクションを順序付けるためのシステム若しくは装置を使用して実行され、該システム若しくは装置が、
（ａ）１つ以上のプロセッサを含み、該プロセッサが、
（ｉ）各ディジタル写真データ・ファイルからタイムスタンプを抽出し、
（ｉｉ）年代順にタイムスタンプを順序付け、
（ｉｉｉ）写真コレクションをクラスタリングするための初期境界を生成し、
（ｉｖ）少なくとも１つのアルゴリズムを用いてステップ（ａ）の（ｉｉｉ）において生成された境界のリストのサブセットを選択し、
（ｖ）境界の選択されたサブセットに基づいてディジタル写真のコレクションを順序付けることが可能であり、
（ｂ）上記１つ以上のプロセッサによって処理されるとき、システムに以下のステップ（ｉ）乃至（ｖ）のステップを実行させる操作を記憶させた機械可読媒体を含み、
（ｉ）写真のリストを作成し、
（ｉｉ）年代順に写真のリストを順序付け、
（ｉｉｉ）写真コレクションをクラスタリングするための最初の境界を作成し、
（ｉｖ）少なくとも１つのアルゴリズムを用いてステップ（ｂ）の（ｉｉｉ）において生成された境界のリストのサブセットを選択し、
（ｖ）選択された境界に基づいてディジタル写真のコレクションを分類することを特徴とする。
【００３０】
本発明の請求項２１に記載の発明は、請求項２０に記載の方法において、少なくとも１つのアルゴリズムで境界のリストを選択することが動的計画法アルゴリズムを用いて達成されることを特徴とする。
【００３１】
本発明の請求項２２に記載の発明は、請求項２０に記載の方法において、少なくとも１つのアルゴリズムで境界のリストを選択することがベイズ情報量規準を計算することによって達成されることを特徴とする。
【００３２】
本発明の請求項２３に記載の発明は、ディジタル写真コレクションを順序付けるための装置であって、該装置は、ディジタルカメラから前記写真コレクションのデータストリームを入力したりユーザからの指示を入力する入力部と、前記入力した写真コレクションのデータストリームに対する処理を実行する少なくとも１つのプロセッサと、該プロセッサによる実行の際の作業領域を形成すると共にプログラムや処理対象としての前記入力した写真コレクションのデータストリーム、及び処理されたデータを格納する記憶部と、処理内容や処理結果を表示画面上に表示する表示部と、データを出力する出力部とを含み、前記プロセッサは、前記記憶部に格納した処理対象のデータストリームに対し、
（１）前記データストリームに含まれる各写真に対するタイムスタンプの抽出して、抽出した時系列のタイムスタンプに基づいて写真を順序付け、
（２）１つ以上の隣接するディジタル写真から抽出されたタイムスタンプと比較して、ディジタル写真のそれぞれから抽出されるタイムスタンプに基づいて１つ以上の類似性値を算出し、該類似性値に基づいて１つ以上の類似性マトリックスを生成し、
（３）異なる範囲の１つ以上のカーネル関数を類似性マトリックスに適用して、それぞれの範囲に対し１つ以上の新規性スコアを生成し、
（４）前記新規性スコアに基づき、前記写真コレクション内の境界を決定し、
（５）該決定した境界に基づき写真コレクションの編成を行うことを特徴とする。
【発明の効果】
【００３３】
上記本発明によれば、タイムスタンプ等の特徴から選択される要素を抽出し、抽出された要素を、そのデータ・ファイル若しくは隣接するデータ・ファイルから抽出された要素と比較することで類似性マトリックスを生成し、異なる範囲のカーネル関数を類似性マトリックスに適用することによって初期境界区分を決定し、アルゴリズムを使用して上記決定された境界から１つ以上の境界を選択し、選択された境界に基づいてデータ・ファイルを編成することにより、データ・ファイルのコレクションの時間的イベント・クラスタリングを行うので、ディジタルカメラの多数の写真コレクションを、処理時間を増加させることなく簡易な方法によりイベントベースで区分することができる。
【発明を実施するための最良の形態】
【００３４】
本発明の好ましい実施の形態は、以下の図面に基づいて詳細に述べられる。これらの図面は、発明の詳細な説明において十分に記載される。
【００３５】
図１は、類似性分析に基づいてディジタル写真コレクションの時間的クラスタリングのための方法を概説するブロック図式フローチャートである。
図１に概略図示されるように、時間的イベント・クラスタリング方法は、類似性分析に基づいていることもある。本発明は、ディジタル写真コレクションの時間的イベント・クラスタリングのための加速方法を示している。
具体的には、以下のような処理が行われる。図１のステップ１０１で抽出されたタイムスタンプにより時系列による写真コレクションの分類が行われる（ステップ１０２）。次に、スケールパラメータＫ（図２に関して後述）に対する類似度マトリックスＳKが生成される（ステップ１０３）。これに基づいてＫに対する新規性スコアＶKが決定され（ステップ１０４）、Ｋに対する境界ＢKが決定される（ステップ１０５）。その後、ステップ１０６で全てのＫが選択されれたか否かが判定され、否定された場合には上記ステップが繰り返される。全てのＫに対する上記ステップが完了すると、全てのＫに対する信頼性スコアＣ（ＢK）が計算される（ステップ１０７）。そして、Ｃ（ＢK）を最大化するための境界リストが決定され（ステップ１０８）、決定した境界リストに基づいて写真が編成される（ステップ１０９）。
【００３６】
尚、本発明は、例えば、パーソナル・コンピュータ、ＰＤＡなどのコンピュータ・システムにおいて実施されることができる。該コンピュータ・システムは、例えば、ディジタルカメラから上記写真コレクションのデータストリームを入力したりユーザからの指示情報（命令）を入力する入力部、プロセッサによる実行の際の作業領域を形成すると共にプログラムや処理対象としての上記入力した写真コレクションのデータストリーム、及び各ステップで処理されたデータを格納する記憶部（メモリ）、処理内容や処理結果を表示画面上に表示する表示部（表示装置）、およびデータをインターネットやイントラネットなどの通信網（ネットワーク）などに出力する出力部などを含む。そして、プロセッサは、記憶部に格納したプログラム（ソフトウェア）を読み出し実行することにより、処理対象のデータストリーム等に対し、当該プログラムの処理手順、すなわち、タイムスタンプの抽出（上記ステップ１０２）、類似度マトリックスの計算（上記ステップ１０３）、新規性スコアの決定（上記ステップ１０４）、境界の決定（上記ステップ１０５）、信頼性スコアの計算（上記ステップ１０７）、信頼性スコアを最大化する境界リストの決定（上記ステップ１０８）、決定した境界リストに基づく写真コレクションの編成（上記ステップ１０９）に対応した処理を当該コンピュータ・システムに実行させる。
また、プロセッサは、上記処理に限らず、以下に詳述される実施形態での各処理をコンピュータシステムに実行させる点に留意されたい。
尚、プロセッサは複数であってもよい。さらに、上記プログラムは、コンピュータにより読取可能な記憶媒体（マシン可読媒体）に格納され、処理実行時にプロセッサによりアクセスされて読み出され、一時的に上記記憶部に格納されて実行される構成でもよい。
各処理手順の詳細については、以下の説明から明らかになるであろう。
図２は、時間的クラスタリングの計算の複雑性を軽減させるためのＤＰ方法又はＢＩＣ方法を導入するための実施の形態を概略的に示している。
【００３７】
本発明の一実施の形態において、ディジタル写真のコレクションの類似性分析は、最初の境界を決定するために使用されることができる。類似性分析において、ディジタル写真のコレクションは、スケール・パラメータＫのマトリックスによって表示されることができる。
図３は、類似性マトリックスＳK（ｉ，ｊ）のタイムスタンプに基づくディジタル写真類似性測定基準を組み込むプロセス（方程式（１）を参照）を示している。
【００３８】
2006216026.tif 000006
【００３９】
ＳK（ｉ，ｊ）では、「ｉ」は、マトリックスの行を示し、「ｊ」は、ｉ番目の写真のスカラ・タイムスタンプをｊ番目の写真のスカラ・タイムスタンプと比較する項目に対応するマトリックスの列を示す。すなわち、図３は、写真「ｉ」及び写真「ｊ」に対応するスカラ・タイムスタンプに基づいて写真類似性測定基準を組み込んでいることを示す図であり、ｔi及びｔjは、類似性マトリックスＳK（ｉ，ｊ）内の行「ｉ」及び「ｊ」にそれぞれ記憶される。このようにして、マトリックスのファミリーは、離散的集合κにわたってスケール・パラメータＫを変化させることによって構築されることができる（ここで、|κ|＝Ｍ、即ち、スケールの総数である）。
【００４０】
図１に示したように、類似性マトリックスは、写真インデックス付きカーネル相関新規性スコアを計算するために使用される。新規性スコアの極大値は、それぞれのＫに対する起こり得る写真境界として検出される。図１に示すように、境界の集合、スケールＫに対応するＢKが与えられると、類似性に基づく信頼性スコア（ＣS）が方程式（２）に従って計算することができる。
【００４１】
2006216026.tif 000007
【００４２】
方程式（２）の第１の項は、写真間の平均的クラスタ内類似性を定量化し、第２の項は、隣接するクラスタ内の写真間の平均的クラスタ間類似性を定量化する。方程式（２）の第２の項を無視（ネゲート）することによって、信頼性スコアは、各クラスタの平均的類似性、及び隣接クラスタ間の相違点を組み合わせる。
図４は、この考えをグラフ表示している。すなわち、図４は、（横線で陰影が付けられた）クラスタ類似性に寄与する類似性マトリックスＳK（ｉ，ｊ）の領域、及び、（縦線で陰影が付けられた）隣接するクラスタ間の相違点に寄与する領域を示している。クラスタ内類似性の項は、主対角線に沿って水平線が引かれた領域の項の平均である。クラスタ間の項は、非対角線垂直線領域の平均である。最後に、信頼性スコアの最大値を決定することによって、最適化境界のリストを導き出すことができる。
【００４３】
図２は、本発明に従ってデータを編成するための方法の実施の形態に対するフローチャートを概略的に示した図である。種々の例示的な実施の形態において、抽出されたタイムスタンプが年代順にデータを編成するために使用できることを認識すべきである。あるいはまた、例えば、抽出された要素がメタデータ要素であり、メタデータの少なくとも１つの抽出された要素がファイル名若しくは何か別のテキスト・ストリングを含む場合、そのデータは、メタデータを使用してアルファベット順に編成され、又は、何か別の所定の規則に従って編成されることもできる。
【００４４】
本発明の一実施の形態の図２に示すように、本発明の方法の動作は、ディジタル写真のコレクションにおける写真ごとのＥＸＩＦヘッダからタイムスタンプを抽出することから開始する。ＥＸＩＦ情報が利用できない場合、ディジタル画像ファイルの変更時間を代わりに使用することができる。コレクションにおけるＮ個の写真は、時間的に順序付けられるので、結果として生じるタイムスタンプ、｛tn:n=1, ..., N｝は、t1≦t2≦...≦tNを満たす。全体にわたって、タイムスタンプ、及び類似性マトリックスの行列は、絶対時間ではなく、時系列にある写真によって索引が付けられる。したがって、各写真は、そのスカラ・タイムスタンプによって表示されることができる。
【００４５】
方程式（２）のスコアの計算は、写真の数の二次計算コストを招く可能性がある。図２は、時間的イベント・クラスタリングのための境界のリストを決定する計算の複雑性を軽減する２つの代替方法を詳述している。ＤＰ又はＢＩＣを導入することは、類似性分析の計算の複雑性を軽減し、それにより、写真コレクションを編成するために最適化境界リストをより迅速に決定する。
図２において、左側のフローがＤＰを導入することによる方法を示し、右側のフローがＢＩＣを導入することによる方法を示す。ＤＰを導入することによる方法はその詳細が図５に示されて後述され、ＢＩＣを導入することによる方法はその詳細が図６に示されて後述される。すなわち、図２のステップ２０４、２０５、２０６、２０７は図５のステップ５０２、５０３、５０４、５０５に各々対応し、図２のステップ２０９、２１０、２１１は図６のステップ６０１、６０４、６０５に各々対応し、図２のステップ２０８は図５のステップ５０６及び図６のステップ６０６に対応している。そのため、ここでは図２のフローの詳細な説明は省略する。
【００４６】
本発明の一実施の形態において、計算の複雑性はＤＰを使用して軽減することができる。検出された境界の全体集合はB＝(b1, ..., bNk)によって示され、これは、すべての離散的スケールＫで検出された潜在的境界の組み合わせ集合である可能性がある。Ｂは、濃度β＝|B|<<Nを有する。写真ｂi及びｂj間のクラスタのコストは、方程式（３）による対応するタイムスタンプの経験的分散であるように定義されることができる。
【００４７】
2006216026.tif 000008
【００４８】
図５は、区分を決定し、それによって、本発明によるＤＰを使用してディジタル写真コレクションの最適数のクラスタを決定するための方法を概説するブロック図式フローチャートである。
図５に示すように、この周知の境界b1, ..., bNkの集合から開始して（ステップ５０１）、ＤＰアルゴリズムは、ｍ−１境界を有する最適区画に基づいて、ｍ個の境界を有する最適区分を連続的に構築する。第１に、最適区分は、方程式（４）に従って２つのクラスタで計算される（ステップ５０２）。
【００４９】
2006216026.tif 000009
【００５０】
ここで、ＥF（ｊ，ｍ）は、濃度ｍを有する指数１, ..., ｂjによる写真の最適区分であってよい。次に、この手順は、方程式（５）に従ってＥF（ｊ，Ｌ）を計算するために繰り返されてもよい（ステップ５０３）。
【００５１】
2006216026.tif 000010
【００５２】
結果は、濃度３, ..., βを有する最適区分の集合となり得る。トレース・バックステップは、最適区分のそれぞれを構成する境界を識別する。クラスタの数が増加するにつれて、区分の全コストは単調に減少する。全区分コストに基づいてクラスタ（Ｌ*）の最適数を選択する（ステップ５０４）ための基準は、方程式（６）に示すことができる
【００５３】
2006216026.tif 000011
【００５４】
当業者がＬ*を決定するための他の種々の基準を利用できることが想定される。
【００５５】
本発明の一実施の形態において、計算の複雑性は、図２に示すようなＢＩＣを使用して軽減することができる。ＢＩＣはモデル順位選択のための方法であり、モデル順位はイベントクラスタの数であってもよい。ＢＩＣ分析において、イベント内のタイムスタンプがイベント平均値周辺に正規分布することを仮定することができる。
図６は、本発明によるＢＩＣを使用してディジタル写真コレクションの最適境界を決定するための方法を概説するブロック図式フローチャートである。図６に示すように、本発明の一実施の形態において、スカラ・パラメータＫを決定することができる（ステップ６０１）。次に、類似性マトリックスの集合は、Ｋの異なる値に対して構築されることができる（ステップ６０２）。新規性スコアの集合は、カーネル相関を経て決定することができる（ステップ６０３）。新規性スコアから、境界の集合を決定することができる（ステップ６０４）。基本的ＢＩＣプロセスは、モデル可能性の増加が更なるセグメントを記載するために使用される更なるパラメータを正しいとするかどうかを判断するために各境界ｂ∈Ｂをテストすることができる（ステップ６０５）。この結果、式（７）に示すようにそれぞれのbl に対し簡単なテストに帰着する。
【００５６】
2006216026.tif 000012
【００５７】
式（７）の左辺は、２セグメント・モデルのログ尤度項である。２セグメント・モデルは、bl+1及びbl-1の間の写真を、境界blによって分離される２つのクラスタに分割する。式（７）の右辺は、単一セグメント・モデルのログ尤度、及び２セグメント・モデルの更なるパラメータに対するペナルティ項を表示する。単一セグメント・モデルは、写真bl-1, ..., bl+1の単一クラスタであればよい。式（７）において、λは、セグメントを表示するために必要とされるパラメータの数であればよい。２つのセグメントに対する個々のモデルに対応付けられる可能性ゲインが更なるパラメータに対するペナルティを越える場合、blは最終的イベント区分に含まれることができる。各セグメントがサンプル平均値（μ1）、及び方程式（８）による写真タイムスタンプの分散量（σ1）を用いて記載できるので、λ＝２となる。
【００５８】
2006216026.tif 000013
【００５９】
方程式（８）は、方程式（９）に更に簡略化されることができる。
【００６０】
2006216026.tif 000014
【００６１】
境界選択のためのＢＩＣは、粗調整から微細調整へのフレームワークに（即ち、Ｋが減少するにつれて）適用されることができる。各スケールＫで、新しく検出された境界は式（７）を使用してテストされ、式（７）の左辺が同式の右辺より大きい境界は、図６に示されるような選択された境界に加えられる。
【００６２】
当業者が、ディジタル写真の時間的クラスタリング又はセグメンテーションに対してＢＩＣの有効性を更に高めるために改良された濃度推定値を利用できることは想定される。例えば、ＢＩＣは、混合モデルを含む、より高機能であり、若しくはより正確な他の確率的なモデルと関連して使用することができる。
【００６３】
表１は、Ｎの幾つかの数値に対して、ＤＰ及びＢＩＣの各方法と比較されたマルチスケール類似性分析（信頼性）を処理するための計算実行時間を比較する。さらに、表１は、この表に含まれる候補イベント境界、Ｂ（検出）、の集合を構築するのに必要な実行時間を示している。
【００６４】
【表１】
2006216026.tif 000015
【００６５】
表１は、異なるサイズの写真コレクションに対する文書実行時間の変化を示し、イベント・クラスタリングはＪａｖａ（登録商標）において実行され、この場合の時間は２．６６ＧＨｚのペンティアム（登録商標）（Ｐｅｎｔｉｕｍ（登録商標））４型プロセッサを備えたパーソナルコンピュータを使用してもたらされた。処理された写真の数（Ｎ）を２倍にした後で、境界検出のための時間は線形に増加するが、「信頼性」が二次費用を負うことを含む。表１における時間は、２５度の実行にわたる平均である。短期間の計算を考慮に入れたタイミングの不正確さが、表１におけるＮ＝５００に対する結果をもたらし、ＤＰ又はＢＩＣ処理は、「検出」だけの処理より時間がかからない。
【００６６】
マルチスケール類似性分析（信頼性）を使用して境界を構築する計算の複雑性は、ＤＰ及びＢＩＣ方法と比較されることができる。一般的に、類似性マトリックスの要素は、メイン対角線から離れたゼロであり、すなわち、|i-j|が大きい場合である。したがって、記憶及び計算要件を低減するために、メイン対角線の周囲の類似性マトリックスの一部のみが計算される。Ｋの変動する特定値を備えた類似性マトリックスを使用して計算された新規性スコアの集合が次に算出される。しかしながら、「信頼性」の評価が類似性マトリックス全体の計算を潜在的に必要とするのは、イベントの範囲を前もって想定することができないからである。最悪の場合、これは、類似性マトリックスのすべてのＮ2項を含む。時間差が大きくなるにつれて時間的類似性測定基準が指数関数的に減衰することから、マスクを使用することによって複雑性は軽減されることができ、このことは、時間的に離れて撮影された写真対に対応するマトリックスの要素を省略する。他の発見的方法はまた、一対の写真の間に撮影された写真の数に基づいてマスクを構築するために使用することもできる。それでもなお、「信頼性」を使用する０（Ｎ2）の最悪ケース複雑性は、境界検出のそれよりも実質的に大きい。
【００６７】
ＤＰ及びＢＩＣに基づく方法は、双方ともに計算の複雑性を大きく軽減することをもたらす。ＤＰベースのピーク選択は、β＜Ｎの場合の０（β2）であればよく、βはＫの最小スケールによって決定される。表１は、ＤＰがテストされたすべての値Ｎに対する類似性ベースのピーク選択よりも約１０倍速いことを教示している。方程式（３）の計算コストは、ＤＰベース方法の全体処理時間の３分の２を占める。ＢＩＣベースの方法は、さらに多くの計算省力化を提供し、式（７）を使用する０（β）試験が実行される。０（Ｎ．Ｍ）のサンプル平均値及び分散量の計算は、全体のＢＩＣ方法コストを決定する。
【００６８】
ＤＰ及びＢＩＣの各方法は、オリジナルの類似性ベースの信頼性スコアと競合的に実行する。
図７は、時間的類似性（ＴＳ）、又は共同の時間的及び内容に基づく類似性（ＪＳ）を使用して、類似性に基づく信頼性（Ｃ）、ＢＩＣ、及びＤＰを備えた異なるアルゴリズムに対して精度、リコール、及びＦ−スコア間における比較を示す図である。具体的には、図７は、個々の撮影者により手作業でクラスタリングされる２つの写真コレクションを用いて、さらに方程式（１０）、（１１）及び（１２）に示された測定基準を用いて、実験的試験の累積結果を示している。
精度＝正確に検出された境界／検出した境界の総数          ・・・方程式（１０）
リコール＝正確に検出された境界／グラウンド・トゥルース境界の総数
・・・方程式（１１）Ｆスコア＝（２×精度×リコール）／（精度＋リコール）        ・・・方程式（１２）
【００６９】
時間的類似性（ＴＳ）、ならびに共同の時間的及び内容に基づく類似性（ＪＳ）に対するイベント・クラスタリング性能は、３つの境界選択技術（類似性に基づく信頼性、ＤＰ、及びＢＩＣ）のそれぞれによって記録される。したがって、ＪＳは、類似性分析に基づく境界を生成するためにファイルサイズなどの内容に基づくパラメータと共に、時間などのメタデータ・タグの両方を使用する。ここに記録されたＪＳ結果に対して、内容に基づく特徴として下位離散的コサイン変換（ＤＣＴ）係数を使用した。類似性に基づく信頼性結果は、ＴＳ−Ｃ及びＪＳ−Ｃによって示され、ＤＰベースの結果は、ＴＳ−ＤＰ及びＪＳ−ＤＰによって示され、ＢＩＣベースの結果は、ＴＳ−ＢＩＣ及びＪＳ−ＢＩＣによって示される。時間的アルゴリズムのＤＰ及びＢＩＣ加速バージョンが高レベルで機能するが、時間的類似性に基づく信頼性（ＴＳ−Ｃ）は、表２に示されるように、検査された方法のすべての最大累積Ｆ−Ｓｃｏｒｅを達成する。加速方法の中で、特に正確性（Precision）に関して、ＤＰは、ＢＩＣベースのピーク選択よりも優れているように見える。３つの境界選択方法は、このようにして計算の複雑性及び性能の交換条件を証明する。
【００７０】
表２は、時間的類似性（ＴＳ）、ならびに、共同の時間的及び内容に基づく類似性（ＪＳ）を使用して、類似性に基づく信頼性（Ｃ）、ＢＩＣ、及びＤＰで境界選択性能を示している。
【００７１】
【表２】
2006216026.tif 000016
【図面の簡単な説明】
【００７２】
【図１】図１は、類似性分析に基づいてディジタル写真コレクションの時間的クラスタリングのための方法を概説するブロック図式フローチャートである。
【図２】図２は、本発明にしたがってＤＰ及びＢＩＣのいずれかを使用して類似性分析に基づくディジタル写真コレクションの時間的クラスタリングのための方法を概説するブロック図式フローチャートである。
【図３】図３は、写真「ｉ」及び写真「ｊ」に対応するスカラ・タイムスタンプに基づいて写真類似性測定基準を組み込んでいることを示す図であり、ｔi及びｔjは、類似性マトリックスＳK（ｉ，ｊ）内の行「ｉ」及び「ｊ」にそれぞれ記憶される。
【図４】図４は、（横線で陰影が付けられた）クラスタ類似性に寄与する類似性マトリックスＳK（ｉ，ｊ）の領域、及び、（縦線で陰影が付けられた）隣接するクラスタ間の相違点に寄与する領域を示している。
【図５】図５は、区分を決定し、それによって、本発明によるＤＰを使用してディジタル写真コレクションの最適数のクラスタを決定するための方法を概説するブロック図式フローチャートである。
【図６】図６は、本発明によるＢＩＣを使用してディジタル写真コレクションの最適境界を決定するための方法を概説するブロック図式フローチャートである。
【図７】図７は、時間的類似性（ＴＳ）、又は共同の時間的及び内容に基づく類似性（ＪＳ）を使用して、類似性に基づく信頼性（Ｃ）、ＢＩＣ、及びＤＰを備えた異なるアルゴリズムに対して精度、リコール、及びＦ−スコア間における比較を示す図である。
【図１】
2006216026.tif 000020
【図２】
2006216026.tif 000021
【図３】
2006216026.tif 000022
【図４】
2006216026.tif 000023
【図５】
2006216026.tif 000024
【図６】
2006216026.tif 000025
【図７】
2006216026.tif 000026