(57)【特許請求の範囲】
【請求項１】
プロセッサを用いて、
境界識別手段により、１以上の属性の第１の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第１のグループを形成し、
前記境界識別手段により、１以上の属性の第２の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第２のグループを形成し、
クラスタ決定手段により、前記第１の集合と前記第２の集合の結合からクラスタＲの集合を取得し、
前記クラスタ決定手段により、前記クラスタＲの集合から、クラスタＳの集合を、ＲとＳとの間の正規化相互情報（ＮＭＩ）の値が最大になるように、動的計画法を用いて決定する、
方法。
【請求項２】
前記正規化相互情報の値は、
【数１】
0005962244.tif 000024
によって計算され、
ここで、
【数２】
0005962244.tif 000025
【数３】
0005962244.tif 000026
であり、かつ
Ｎはファイルの総数である、請求項１に記載の方法。
【請求項３】
前記第１の集合と前記第２の集合の１つは時間情報であり、かつ前記第１の集合と前記第２の集合の１つは空間情報である、請求項１に記載の方法。
【請求項４】
前記第１の集合と前記第２の集合の１つは色類似性である、請求項３に記載の方法。
【請求項５】
前記ファイルは写真である、請求項３に記載の方法。
【請求項６】
グループ化手段により、前記複数のファイルをイベントに基づいてグループ化することを更に含み、前記グループ化はクラスタＳの集合に基づいて行われる、請求項１に記載の方法。
【請求項７】
ｂｉとｂｊを候補境界とし、Ｓｉｊをｂｉとｂｊとの間のクラスタとしたとき、
【数４】
0005962244.tif 000027
により計算されるコストＣＮＭＩ（ｂｉ、ｂｊ）を動的計画法により最大化することで、クラスタＳの集合を決定する、請求項１に記載の方法。
【請求項８】
プロセッサに、
１以上の属性の第１の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第１のグループを形成し、
１以上の属性の第２の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第２のグループを形成し、
前記第１の集合と前記第２の集合の結合からクラスタＲの組を取得し、
前記クラスタＲの集合から、クラスタＳの集合を、ＲとＳとの間の正規化相互情報（ＮＭＩ）の値が最大になるように、動的計画法を用いて決定する、
ことを含む処理を実行させるコンピュータプログラム。
【請求項９】
前記正規化相互情報の値は、
【数１】
0005962244.tif 000028
によって計算され、
ここで、
【数２】
0005962244.tif 000029
【数３】
0005962244.tif 000030
であり、かつ
Ｎはファイルの総数である、請求項８に記載のコンピュータプログラム。
【請求項１０】
前記第１の集合と前記第２の集合の１つは時間情報であり、かつ前記第１の集合と前記第２の集合の１つは空間情報である、請求項８に記載のコンピュータプログラム。
【請求項１１】
前記第１の集合と前記第２の集合は色類似性である、請求項８に記載のコンピュータプログラム。
【請求項１２】
前記ファイルは写真である、請求項１０に記載のコンピュータプログラム。
【請求項１３】
前記プロセッサに、前記複数のファイルをイベントに基づいてグループ化する処理を実行させることを更に含み、前記グループ化はクラスタＳの集合に基づいて行われる、請求項８に記載のコンピュータプログラム。
【請求項１４】
ｂｉとｂｊを候補境界とし、Ｓｉｊをｂｉとｂｊとの間のクラスタとしたとき、
前記プロセッサに、
【数４】
0005962244.tif 000031
により計算されるコストＣＮＭＩ（ｂｉ、ｂｊ）を動的計画法により最大化する処理を実行させることで、クラスタＳの集合を決定する、請求項８に記載のコンピュータプログラム。
【請求項１５】
プロセッサと、
前記プロセッサを用いて、１以上の属性の第１の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第１のグループを形成し、かつ１以上の属性の第２の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第２のグループを形成する境界識別手段と、
前記プロセッサを用いて、前記第１の集合と前記第２の集合の結合からクラスタＲの集合を取得し、前記クラスタＲの集合から、クラスタＳの集合を、ＲとＳとの間の正規化相互情報（ＮＭＩ）の値が最大になるように、動的計画法を用いて決定するクラスタ決定手段と、
を備えるシステム。
【請求項１６】
前記クラスタ決定手段は前記正規化相互情報の値を、
【数１】
0005962244.tif 000032
によって計算され、
ここで、
【数２】
0005962244.tif 000033
【数３】
0005962244.tif 000034
であり、かつ
Ｎはファイルの総数である、請求項１５に記載のシステム。
【請求項１７】
前記第１の集合と前記第２の集合の１つは時間情報であり、かつ前記第１の集合と前記第２の集合の１つは空間情報である、請求項１５に記載のシステム。
【請求項１８】
前記第１の集合と前記第２の集合は色類似性である、請求項１５に記載のシステム。
【請求項１９】
前記ファイルは写真である、請求項１７に記載のシステム。
【請求項２０】
前記プロセッサを用いて、前記複数のファイルをイベントに基づいてグループ化するグループ化手段を更に含み、前記グループ化はクラスタＳの集合に基づいて行われる、請求項１５に記載のシステム。
【請求項２１】
ｂｉとｂｊを候補境界とし、Ｓｉｊをｂｉとｂｊとの間のクラスタとしたとき、
前記プロセッサに、
【数４】
0005962244.tif 000035
により計算されるコストＣＮＭＩ（ｂｉ、ｂｊ）を動的計画法により最大化する処理を実行させることで、クラスタＳの集合を決定する、請求項１５に記載のシステム。
【発明の詳細な説明】
【背景技術】
【０００１】
デジタル写真が爆発的な成長を続けているが、それに伴い収集写真を個人レベルで管理するためのより進歩したツールが望まれている。写真撮影時に地理情報を記録することが次第に可能となってきており、これが既存ツールの強化の機会となっている。デジタルカメラおよび、より一般的にはスマートフォンはいずれも、その写真の、緯度、経度の座標を記録する。位置情報は、既存の時間ベースの編成の改良に寄与すると共に、編成と検索に関して既存のものに替わるフレームワークを提供するために用いることが出来る。
【０００２】
当技術分野では、写真の時間的なクラスタリングに動的計画法（ＤＯ）を利用する方法がある。このフレームワークでは、時間情報または位置情報を個別に利用して検出される潜在的なクラスタ境界を統合することが可能である。この方法では、時系列の写真をコスト最適化のためのクラスタに分割する境界を選択している。
【０００３】
このような方法は、一連のステップに沿って、写真のクラスタリングのための時間情報と空間情報を結合することもできる。先ず、時間のみを利用して写真を閾値基準で細かくセグメント化する。次に、記録された位置は独立してクラスタに階層グループ分けされる。ここでクラスタの数は自動的に決定される。その次に、同一場所のクラスタに所属する時間ベースのセグメントが統合される。この最後のセグメント化は、位置クラスタの名前を引き出すとか、時間と位置をベースとするイベントに名前を付けるとかのような、追加処理に利用される。
【０００４】
そのような方法は拡張されて、小さなディスプレイで閲覧ができるように設計された。この方法には、クラスタ数を評価するためのモデル複合手段を有する、混合モデルフレームワークが利用される。例えば、粗いクラスタリングをするためにカルバックーライブラー（ＫＬ）情報量を利用して計算機処理を単純化した階層構造増強を行った研究がある。第１のパスとして、時間データと位置データを一緒にして学習した混合データを用いてクラスタリングを実行する、端末同士間の方法も可能である。モデル順に対処するためには、変分法を用いる。これは、ガウス分布と低次元（３次元）特徴量空間とを仮定するので、思ったほど解析的に厄介なものではない。第２のパスで、ＫＬ尺度と混合パラメータを利用してクラスタがグループ化される。
【０００５】
イベントクラスタリングを利用する階層的画像注釈もシステムによっては利用される。データにはジオタグが含まれていて、イベントクラスタリングはシフトクラスタリング手法によって行なわれる。この方法は、最初に時間処理をし、次に位置処理をする複数パスで行われる。
【０００６】
ある方法では、メディアの種類およびユーザにまたがって、イベントベースの解析をするために、正規化相互情報（ＮＭＩ）も利用される。そのタスクは、ＴＲＥＣ（Ｔｅｘｔ  Ｒｅｔｒｉｅｖａｌ  Ｃｏｎｆｅｒｅｎｃｅ）において評価されるイベント検出とトラッキングタスク（ＴＤＴ）に類似している。これは、異種の情報ストリームの数が与えられたとして、イベントを識別し、そのイベントに従って文書をグループ化することが目標である。このために、ｕｐｃｏｍｉｎｇ．ｏｒｇに入ったイベントと、Ｆｌｉｃｋｒの複数のユーザのジオタグ付き写真を含むデータストリームとにより、イベントのグランドトルースが確立された。アンサンブル・クラスタリングに基づく予備的な結果によれば、タグと位置は建設的な指標となっていることがわかり、これらの組合せにより更なる進歩が与えられた。その手法は、管理された学習と分類化によってクラスタリングのためにＮＭＩ尺度を閾値化することに依拠している。
【０００７】
しかし、現状技術に関しては改良の余地がある。特にイベントベースのクラスタリングに関してそうである。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第７，６４０，２１８号公報
【非特許文献】
【０００９】
【非特許文献１】Ｈ．Ｂｅｃｋｅｒらによる、”Ｅｖｅｎｔ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｉｎ  Ｓｏｃｉａｌ  Ｍｅｄｉａ”、Ｔｗｅｌｆｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  ｔｈｅ  Ｗｅｂ  ａｎｄ  Ｄａｔａｂａｓｅｓ（ＷｅｂＤＢ  ２００９)，プロビデンス，  アメリカ合衆国
【非特許文献２】Ｐ．  Ｂｒｕｎｅａｕらによる、”Ｇｅｏ−ｔｅｍｐｏｒａｌ  ｓｔｒｕｃｔｕｒｉｎｇ  ｏｆ  ａ  ｐｅｒｓｏｎａｌ  ｉｍａｇｅ  ｄａｔａｂａｓｅ  ｗｉｔｈ  ｔｗｏ−ｌｅｖｅｌ  ｖａｒｉａｔｉｏｎａｌ−Ｂａｙｅｓ  ｍｉｘｔｕｒｅ  ｅｓｔｉｍａｔｉｏｎ”、２００８、Ａｄａｐｔｉｖｅ  Ｍｕｌｔｉｍｅｄｉａ  Ｒｅｔｒｉｅｖａｌ  ｗｏｒｋｓｈｏｐ（ＡＭＲ’０８），ベルリン，ドイツ
【非特許文献３】Ｌ．Ｃａｏらによる、”Ｉｍａｇｅ  Ａｎｎｏｔａｔｉｏｎ  Ｗｉｔｈｉｎ  ｔｈｅ  Ｃｏｎｔｅｘｔ  ｏｆ  Ｐｅｒｓｏｎａｌ  Ｐｈｏｔｏ  Ｃｏｌｌｅｃｔｉｏｎｓ  Ｕｓｉｎｇ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｅｖｅｎｔ  ａｎｄ  Ｓｃｅｎｅ  Ｍｏｄｅｌｓ”、２００９年２月、２０８〜２１９頁、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  第１１巻２号
【非特許文献４】Ｍ．Ｃｏｏｐｅｒらによる、”Ｔｅｍｐｏｒａｌ  Ｅｖｅｎｔ  Ｃｌｕｓｔｅｒｉｎｇ  ｆｏｒ  Ｄｉｇｉｔａｌ  Ｐｈｏｔｏ  Ｃｏｌｌｅｃｔｉｏｎｓ”、２００５年８月、２６９〜２８８頁、ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｍｐｕｔｉｉｎｇ，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｉｎｓ  第１巻３号
【非特許文献５】Ｂ．  ＦｒｅｙおよびＤ．  Ｄｕｅｃｋによる、”Ｃｌｕｓｔｅｒｉｎｇ  ｂｙ  Ｐａｓｓｉｎｇ  Ｍｅｓｓａｇｅｓ  Ｂｅｔｗｅｅｎ  Ｄａｔａ  Ｐｏｉｎｔｓ”、９７２〜９７６頁、２００７年２月１６日、ｗｗｗ．ｓｃｉｅｎｃｅｍａｇ．ｏｒｇ  第３１５巻
【非特許文献６】Ｗ．  Ｆｉｓｈｅｒによる、”Ｏｎ  Ｇｒｏｕｐｉｎｇ  Ｆｏｒ  Ｍａｘｉｍｕｍ  Ｈｏｍｏｇｅｎｅｉｔｙ”、１９５８年１２月、７８９〜７９８頁、Ａｍｅｒｉｃａｌ  Ｓｔａｔｉｓｔｉｃａｌ  Ａｓｓｏｃｉａｔｉｏｎ  Ｊｏｕｒｎａｌ
【非特許文献７】Ｍ．  Ｎａａｍａｎらによる、”Ａｕｔｏｍａｔｉｃ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  Ｄｉｇｉｔａｌ  Ｐｈｏｔｏｇｒａｐｈｓ  ｗｉｔｈ  Ｇｅｏｇｒａｐｈｉｃ  Ｃｏｏｒｄｉｎａｔｅｓ”、２００４年６月７日〜６月１１日、ＡＣＭ、アリゾナ、アメリカ合衆国
【非特許文献８】Ａ．ＰｉｇｅａｕおよびＭ．Ｇｅｌｇｏｎによる、”Ｂｕｉｌｄｉｎｇ  ａｎｄ  Ｔｒａｃｋｉｎｇ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｇｅｏｇｒａｐｈｉｃａｌ  ＆  Ｔｅｍｐｏｒａｌ  Ｐａｒｔｉｔｉｏｎｓ  ｆｏｒ  Ｉｍａｇｅ  Ｃｏｌｌｅｃｔｉｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｎ  Ｍｏｂｉｌｅ  Ｄｅｖｉｃｅｓ”、２００５年１１月６日〜１１月１２日、１４１〜１５０頁、ＡＣＭ、シンガポール
【非特許文献９】Ａ．Ｐｉｇｅａｕによる、”Ｆａｓｔ  Ｔｒａｃｋｉｎｇ  Ｏｆ  Ｈｉｅｒａｒｃｈｉｃａｌ  Ｐａｒｔｉｔｉｏｎｓ  Ｗｉｔｈ  Ａｐｐｒｏｘｉｍａｔｅ  ＫＬ−ｄｉｖｉｅｒｇｅｎｃｅ  ｆｏｒ  Ｇｅｏ−ｔｅｍｐｏｒａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｏｆ  Ｐｅｒｓｏｎａｌ  Ｉｍａｇｅｓ”、２００７年３月１１日〜３月１５日、１０８８〜１０８９頁、ＡＣＭ、ソウル、韓国
【非特許文献１０】Ａ．ＳｔｒｅｈｌおよびＪ．Ｇｈｏｓｈらによる、”Ｃｌｕｓｔｅｒ  Ｅｎｓｅｍｂｌｅｓ−Ａ  Ｋｎｏｗｌｅｄｇｅ  Ｒｅｕｓｅ  Ｆｒａｍｅｗｏｒｋ  ｆｏｒ  Ｃｏｍｂｉｎｉｎｇ  Ｍｕｌｔｉｐｌｅ  Ｐａｒｔｉｔｉｏｎｓ”、２００２年、５８３〜６１７頁、Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  Ｒｅｓｅａｒｃｈ  ３
【非特許文献１１】Ｎ．Ｖｉｎｈらによる、”Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｅｔｉｃ  Ｍｅａｓｕｒｅｓ  ｆｏｒ  Ｃｌｕｓｔｅｒｉｎｇｓ  Ｃｏｍｐａｒｉｓｏｎ：Ｖａｒｉａｎｔｓ，  Ｐｒｏｐｅｒｔｉｅｓ，Ｎｏｒｍａｌｉｚａｔｉｏｎ  ａｎｄ  Ｃｏｒｒｅｃｔｉｏｎｓ  ｆｏｒ  Ｃｈａｎｃｅ”、２０１０年、２８３７〜２８５４頁、Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  Ｒｅｓｅａｒｃｈ  １１
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明の方法の様々な実施態様は、デジタル写真の管理に関係する従来の技術についての１つ又は複数の前記及びその他の問題を実質的に取り除くための方法及びシステムに係わる。
【課題を解決するための手段】
【００１１】
本発明の第１の態様は、プロセッサを用いて、境界識別手段により、１以上の属性の第１の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第１のグループを形成し、前記境界識別手段により、１以上の属性の第２の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第２のグループを形成し、クラスタ決定手段により、前記第１の集合と前記第２の集合の結合からクラスタＲの集合を取得し、前記クラスタ決定手段により、前記クラスタＲの集合から、クラスタＳの集合を、ＲとＳとの間の正規化相互情報値（ＮＭＩ）が最大になるように、動的計画法を用いて決定する、ことを含む方法を提供する。
【００１２】
本発明の第２の態様は、コンピュータに、１以上の属性の第１の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第１のグループを形成し、１以上の属性の第２の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第２のグループを形成し、前記第１の集合と前記第２の集合の結合からクラスタＲの組を取得し、前記クラスタＲの集合から、クラスタＳの集合を、ＲとＳとの間の正規化相互情報値（ＮＭＩ）が最大になるように、動的計画法を用いて決定する、ことを含む処理を実行させるコンピュータプログラムを提供する。
【００１３】
本発明の第３の態様は、プロセッサと、前記プロセッサを用いて、１以上の属性の第１の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第１のグループを形成し、かつ１以上の属性の第２の集合に基づいて複数のファイルをグループ化するための複数の境界を識別して、複数の第２のグループを形成する境界識別手段と、前記プロセッサを用いて、前記第１の集合と前記第２の集合の結合からクラスタＲの集合を取得し、前記クラスタＲの集合から、クラスタＳの集合を、ＲとＳとの間の正規化相互情報値（ＮＭＩ）が最大になるように、動的計画法を用いて決定するクラスタ決定手段と、を備えるシステムを提供する。
【００１４】
本発明の第４の態様によれば、本発明の第１〜３のいずれかの態様において、前記正規化相互情報のスコアを、
【数１】
0005962244.tif 000002
によって計算し、
ここで、
【数２】
0005962244.tif 000003
【数３】
0005962244.tif 000004
であり、かつ
Ｎはファイルの総数である、ようにしてもよい。
【００１５】
本発明の第５の態様によれば、本発明の第１〜３のいずれかの態様において、前記第１の集合と前記第２の集合の１つは時間情報であり、かつ前記第１の集合と前記第２の集合の１つは空間情報であるようにしてもよい。
【００１６】
本発明の第６の態様によれば、本発明の第１〜３のいずれかの態様において、前記第１の集合と前記第２の集合の１つは色類似性であるようにしてもよい。
【００１７】
本発明の第７の態様によれば、本発明の第１〜３のいずれかの態様において、前記ファイルは写真であるようにしてもよい。
【００１８】
本発明の第８の態様によれば、本発明の第１〜３のいずれかの態様において、前記複数のファイルをイベントに基づいてグループ化してもよく、前記グループ化はクラスタＳの集合に基づいて行うようにしてもよい。
【００１９】
本発明に関するその他の態様は、以下の説明で部分的に説明され、また説明から部分的に明白であり、又は本発明の実行により習得することができる。本発明の態様は、以下の詳細な説明及び添付の特許請求の範囲において特に指摘された要素、及び種々の要素と態様との組合せによって実現及び達成することができる。
【００２０】
上記及び以下の記述はいずれも単に例示及び説明を目的とするものであり、特許請求の範囲に記載の発明もしくはその適用をいかなる形であれ限定することは全く意図していないことを理解されたい。
【発明の効果】
【００２１】
本発明の実施形態では、１以上の属性の第１の集合と、１以上の属性の第２の集合と、を用いて検出した候補境界を結合し、前記候補境界の結合に基づくクラスタに対してＤＰを利用して正規化相互情報値（ＮＭＩ）が最大となるクラスタを決定することにより、複数の属性がより効率的に結合されたクラスタリングを得ることができる。
【図面の簡単な説明】
【００２２】
本明細書に組み込まれ本明細書の一部をなす添付図面は、本発明の実施形態を例示し、説明と相俟って本発明技術の原理説明及び例示に供する。
【００２３】
【図１】本発明の実施形態による例示的フローチャートを示す図である。
【図２】本発明の実施形態による別の例示的フローチャートを示す図である。
【図３】本発明の実施形態による例示的機能図である。
【図４】本発明のシステムを実装するコンピュータプラットフォームの実施形態を示す図である。
【発明を実施するための形態】
【００２４】
本発明の実施形態は位置情報を活用して、イベントを基にした写真のクラスタリングを強化する。これは例えば、写真を時系列に整列して、時間的および空間的に整合したクラスタに写真をグループ化することで実現される。さらに本発明の実施形態は、類似性ベースのイベント境界検出と境界選択のための動的計画法とを結合した方法を用いる。さらに、写真をクラスタリングするために情報尺度を利用する一変形も示す。
【００２５】
イベントベースのクラスタリングは、アンサンブル・クラスタリングによって改良することができる。そこでは最終の（写真の）クラスタリングは、利用可能なクラスタリングの集合から決定されなければならない。例えば、信頼スコアを使って、異なるスケールで実行される時間クラスタリングをランク分けすることができる。本発明の実施形態は更にこの手法を、空間クラスタリングへ拡張して実験における比較の基準ラインとして使用する。動的計画法（ＤＰ）がそこで関連スコアの直接最適化に利用される。
【００２６】
相互情報は２つのクラスタリングの整合性の尺度を与える。有効なクラスタリングがそれぞれの写真を厳密に１つのクラスタに割り当てるとし、かつクラスタの結合は元々のＮ個の写真の集合を成すと仮定する。２つのクラスタリングＳ＝｛Ｓ１，．．．，ＳＡ｝とＲ＝｛ｒ１，．．．，ｒＢ｝を考えてみる。ＲとＳとの間の相互情報は、次のようになる。
【数１】
0005962244.tif 000005
（１）
【００２７】
相互情報を直接適用すると分割し過ぎとなりやすい。これに対抗するために、正規化形式を利用してもよい。
【００２８】
写真を位置でクラスタリングするために、本発明の実施形態は適切な空間距離尺度を利用した時間ベースの境界検出を適用する。本発明の実施形態は、次の２つの方法によって動的計画法（ＤＰ）クラスタリングの概念を拡張する。利用される１つの方法は、時間および空間情報を利用して検出される境界の組合せをＤＰ手順への入力とすることに向けられる。使用されるもう一つの方法は、時間情報と空間情報とを結合した新コスト関数を利用する位置情報を組み込む。これらの方法はノンパラメトリックであり、ＤＰを利用してクラスタの適合尺度を直接最適化する。
【００２９】
本発明の実施形態は、正規化相互情報（ＮＭＩ）：
【数２】
0005962244.tif 000006
（２）
を用いる。ここで、
【数３】
0005962244.tif 000007
はクラスタリングＲのエントロピーである。
【００３０】
動的計画法を利用して、利用可能なクラスタリング全体で平均化したＮＭＩを最大化するようにクラスタリングを構築する。
【００３１】
図１は本発明の実施形態による方法の例示的フローチャートを示す。ここには、境界検出１０２と境界選択１０３の２つの基本ステップがある。ｉ番目の写真が関連する時間と位置（ｔｉ，ｌｉ）を有し（１０１）、１つのクラスタＣｋに割り当てられている（１０４）。境界の検出と選択のステップを様々な可能な選択で組み合わせることにより、違う構成の系が形成される。
【００３２】
例えば、境界検出１０２は、時間または空間の属性に従った、またはその両者の組み合わせに従った類似性ベースの検出に基づくものであってもよい。境界検出１０２は、空間属性を解析するための親和性伝搬（ａｆｆｉｎｉｔｙ  ｐｒｏｐａｇａｔｉｏｎ）に基づくものでもよい。
【００３３】
境界選択１０３は、類似性またはＮＭＩに基づいて境界を選択するために動的計画法を利用してもよい。類似性またはＮＭＩ選択は、時間または空間属性、あるいはその両者の組み合わせに基づくことが可能である。
【００３４】
図２は、本発明の実施形態による例示的フローチャートを示す。複数のファイル２００が解析されて、１つまたは複数の属性の第１の集合に基づいて境界を特定し、複数の第１のグループが生成される（２０１）。また、１つまたは複数の属性の第２の集合に基づいて複数の第２のグループが生成される（２０２）。前述したように、属性はファイルの内容に依存して時間属性であっても空間属性であってもよい。それ以外の属性、例えば写真の色類似性、使用データ、オーディオファイルに対するオーディオ属性等も、イベントまたはコンテンツ基準の順序付けに対して可能である。２つの属性から、第１のグループと第２のグループの和の部分集合であってＮＭＩ値を最大化する部分集合を表す、ファイルのクラスタリングが特定される（２０３）。順序付けの種類によって、その次にイベントをクラスタに基づいて特定することができる（２０４）。
【００３５】
最初のステップでは、時系列の写真の流れを区分するイベント境界の候補の集合を形成する。最終クラスタを画定する候補の部分集合が選択される。時間境界の検出には、本発明の実施形態は、写真同士の類似性尺度として下に示した指数関数群を利用して、階層的時間セグメンテーションを構築する。
【数４】
0005962244.tif 000008
（３）
【００３６】
τが変化してセグメンテーションの集合を形成する。位置に基づくイベント境界検出をするために、本発明の実施形態では、写真位置間の近似距離：
【数５】
0005962244.tif 000009
（４）
を利用する。ここで、ｄｇは地球が球であることを仮定して算出される適切な測地線を利用した距離である。
【００３７】
時間とは異なり、位置は、本来は順序付け出来ない。さらに、通常仮定する共通元のない隣接したクラスタとは違って、写真家は時間が経過するとその場所を再訪することもあり得る。従ってより自然な位置のクラスタリングのために、本発明の実施形態では境界検出に親和性伝搬を利用する。この手法はデータの順序は何も仮定しない。ただし、ペアとなる写真間の完全な距離マトリックスを必要とするために計算上は不利である。クラスタリングの粒度は、マルチスケールの空間クラスタリングの集合を生成するために広範囲をスイープする“優先”パラメータによって決定される。
【００３８】
境界検出ステップの目的は、候補境界の集合を生成することである。“結合された”セグメンテーションでは、独立した空間的および時間的セグメンテーションからの境界を単純に結合して、候補集合を形成する。
【００３９】
境界選択のための動的計画法（ＤＰ）は、それぞれの潜在的写真クラスタのコストに関係する。本発明の実施形態では、次に総合コストを最適化するための最終区分を決定する。順序付けされたオブジェクトの集合をグループ化するためのＤＰ手順が、区分を実装するために利用されてもよい。先ず、Ｂで表わされる、前のステップで検出された境界の集合から始める。一般的に、Ｎを写真の数とすると、β＝｜Ｂ｜＜＜Ｎである。境界のインデックスがｂｉとｂｊにある写真の間のクラスタのコストは、そのクラスタ内の写真同士のペア距離であると定義すると、次のようになる：
【数６】
0005962244.tif 000010
（５）
【００４０】
距離の尺度として以下の３つを考える：
｜ｔｍ−ｔｎ｜                                 （時間選択）
ｄ（ｍ，ｎ）＝  ｄｇ（ｌｍ，ｌｎ）                             （空間選択）
ｍａｘ（｜ｔｍ−ｔｎ｜，ｄｇ（ｌｍ，ｌｎ））          （結合選択）
【００４１】
結合選択として単純に最大を選ぶと、時間と位置の両方において整合のとれないクラスタに対しては不利になる。本発明の実施形態では、ｍ−１個の境界を有する最小コスト区分を基にして、次にｍ個の境界の場合についての最小コスト区分を求める。先ず、１，．．．，ｂｊでインデックスされた写真の、２つのクラスタセグメンテーションに対する最小コストを計算する。
【数７】
0005962244.tif 000011
（６）
【００４２】
ＥＦ（ｊ，ｍ）は、濃度ｍのインデックス１，．．．ｂｊを有する写真の最適区分である。この手順を繰り返して次の計算をする。
【数８】
0005962244.tif 000012
(７)
【００４３】
その結果は、濃度３，…，βを有する最小コスト区分の集合となる。ステップをトレースバックすることで、各最適区分の境界が特定される。クラスタの数が増えるに従って、区分の全体コストは単調減少する。全体の区分コストに基づく最適クラスタ数Ｋの選択に関しては、種々の基準が提案されている。ヒューリスティックを利用すると、
【数９】
0005962244.tif 000013
（８）
となる。ここで、
【数１０】
0005962244.tif 000014
（９）
である。
【００４４】
コストＣＦの計算の複雑さは、相対的効率を与える新規スコア中の検出ピーク数であるβの２次式である。
【００４５】
正規化相互情報の利用
【００４６】
本発明の実施形態では、ＮＭＩコストを直接最大化するためにもＤＰを利用する。このために、本発明の実施形態では、時間または特定のスケールの位置を利用して、検出された境界の集合を対応するクラスタリングへ変換する（つまり、検出された境界を整列して、各セグメントに離散準位を割り当てる）。境界は、時間と空間には無関係にある範囲のスケールに亘って検出されるので、結果はそのようなクラスタリングの集合となる。
この集合をΓで表す。最大化するための全コストは、任意の提案されたクラスタリングＳと、各クラスタリングＲ∈Γとの間の平均ＮＭＩである。
【数１１】
0005962244.tif 000015
【００４７】
考え方は、それぞれがある特定のスケールでの空間または時間的な写真集団における構造を捉えるものである、Ｒにおけるすべてのクラスタリングでの平均ＮＭＩを最大化するクラスタリングＳを特定することである。Ｓに可能なクラスタを含むコストを定義しよう。先ず、上記の和の１つの項を（２）の定義を用いて分解する。
【数１２】
0005962244.tif 000016
（１０）
【数１３】
0005962244.tif 000017
（１１）
【００４８】
Ｉ（ｓ；Ｒ）は、（１０）の右端の和である。この式は、与えられたクラスタＳのＮＭＩ（Ｒ；Ｓ）への寄与の度合いを示す。Ｓｉｊを候補境界ｂｉとｂｊとの間の写真のクラスタであるとする。最大化のためのコストを（５）のようにＤＰによって定義すると、次のようになる。
【数１４】
0005962244.tif 000018
（１２）
【００４９】
このコストは、最小化を最大化に置き替えて、（６）と（７）で表現した前述の手順に代入することができる。但し、下記する（１３）のコストでは、（１０）式中のＨ（Ｓ）項は無視する。これは主として解析上の都合によるものであるが、結果的に有効な指標が得られることに変わりはない。クラスタＳｉｊのこのローカルなコストに、グローバルクラスタリングのエントロピーを含める単純な方法はない。最終的なクラスタリングの選択でこれは補正することができる。このように、ＤＰ手順により平均ＮＭＩの拡大縮小形が最大化される。
【数１５】
0005962244.tif 000019
（１３）
【００５０】
Ｈ（Ｒ）の項は、各クラスタリングＲに陰の重み付けを与える。一般的にこれは少数クラスタのクラスタリングに優先的に重み付けする。これは、粗い縮尺で検出される境界がより重要である、という直感にも合っている。前と同様に、最終クラスタリングを決定するためには、クラスタの最終的な数Ｋを選択する必要がある。これは、先ず平均ＮＭＩを計算してそれを最大化することで達成される。次に、候補境界の数により決定されるＫの可能な値の範囲として、３＜＝Ｋ＜＝βが検討される。それぞれに関して、トレースバックのステップが実行されて、（１３）のコストを最大化する境界が選択される。対応するクラスタリングをＳＫで表し、エントロピーを計算する。トレースバックのステップで生じる最終誤差を次に拡大縮小して、平均ＮＭＩを決定する。最終クラスタリングのクラスタ数が次式のように選択される。
【００５１】
【数１６】
0005962244.tif 000020
（１４）
【００５２】
実験結果
【００５３】
４組の写真（８２＜Ｎ＜２４５）を使用した。この中には評価のための写真家のグランドトルースのイベントクラスタリングも含まれている。幾つかの実験を行い、結果を４つの集団に対する平均的性能指標を付してここにまとめた。適合率と再現率および幾何平均、Ｆ１スコアが、本発明の異なる実施形態の評価に利用された。このテストセットの態様は難易度の高いものである。ラベル付けされたイベントクラスタのサイズは写真２枚だけである。そして１つのデータセットはバスツアーに関するもので、時間的には狭い時間範囲で撮られているが、写真と写真とでは場所が大きく変わっている。
【００５４】
類似性ベースのクラスタリング
【００５５】
類似性ベースの方法は、従来のフレームワークに基づいており、本発明のＤＰ手法をテストする際の基準ラインとした。表１に幾つかの変形に対する結果が示されている。フィットネス・スコア（適応性スコア）を用いて、セグメンテーション階層木の１つのレベルを最終クラスタリングとして選択した。空間類似性に基づくクラスタフィットネススコアを利用した時間境界検出が、最もよい結果を示した。このことは、イベントクラスタリングに対しては、位置と時間は相補的な情報を提供することを示している。クラスタ数の列は、グランドトルース平均（ＧＴ）と、４つのテストセットに対する検出された平均（ＤＥＴ）とを表している。
【００５６】
【表１】
0005962244.tif 000021
【００５７】
ＤＰによるクラスタリング−時間と位置の直接利用
【００５８】
表２はＤＰを用いた結果を示す。候補境界を集めるために、本発明の実施形態では、前述したものと同様に、時間情報または空間情報、またはその両方を利用する類似性ベースの手法を適用する。境界の選択には、この実施形態では、（５）式のコストを求めるために３つの写真間距離、すなわち時間距離と空間距離とその結合した（最大）距離とを考慮する。空間情報と時間情報とを用いて検出した候補境界を結合し、時間コストまたは結合コストのいずれかを選択するためにＤＰを利用することで、すべての基準ライン上で性能は向上した。ＤＰ手順は、クラスタリングのために位置情報と時間情報とをより効率的に結合させることができる。結合境界集合を有する空間コスト関数を利用すると、過度のセグメンテーションとなり、性能が劣化する。
【００５９】
【表２】
0005962244.tif 000022
【００６０】
ＤＰによるクラスタリング−ＮＭＩの利用
【００６１】
表３は、（１３）の拡大縮小したＮＭＩコストを有するＤＰを利用した結果を示す。前と同様に境界が検出される。最終クラスタリングは、クラスタリングの集合Γに対して平均ＮＭＩを最大化するように選択される。Γを生成するために使用される境界はΓの見出しの列に示されている。表１の基準ラインに対して性能は向上する。特筆することではないが、集合Γ中の利用可能なクラスタリングの数が増えるに従い、ＮＭＩ手法は改善される。従って、Γの構成にマルチスケールの空間及び時間クラスタリングを使用し、Γの列が“結合”となっている行が最高の性能を示す。検出されたすべての境界を候補として選択に利用することで、“結合”／“結合”の系が最高の性能となり、これは表２のＤＰシステムのベストにほぼ匹敵する。Γに含まれているクラスタリングを生成するのに位置ベースの親和性伝搬を利用する変形方式も含まれている。これらの系の性能は相対的に低く、この問題に関しては時間的な順序が重要であることを示唆している。
【００６２】
【表３】
0005962244.tif 000023
【００６３】
図３は、本発明の実施形態による例示的機能図である。ファイルはメモリ３０１に格納されて、境界検出のために境界ユニット３０２に送られてもよい。その後、クラスタ決定ユニット３０３を利用して、境界検出に基づくクラスタ決定がなされてもよい。その結果はディスプレイ３０４に表示されてもよい。
【００６４】
図４は、本発明による方法の実施形態を実装することが可能なコンピュータ／サーバシステム４００の実施形態を示すブロック図である。システム４００は、当業者には周知のように、コンピュータプログラムの実行に作用するプロセッサ４０２とメモリ４０３を含むコンピュータ／サーバプラットフォーム４０１を含む。本明細書で用いられる「コンピュータ可読媒体」という用語は、プロセッサ４０２にコンピュータプログラムの実行命令を与えることに関与する任意の媒体を指す。さらに、コンピュータプラットフォーム４０１は、キーボード、マウス、タッチデバイスなどの複数の入力装置４０４、または音声命令からの入力を受信する。コンピュータプラットフォーム４０１はさらに、ポータブルハードディスク装置、光学媒体（ＣＤまたはＤＶＤ）、ディスク媒体、またはコンピュータが実行可能なコンピュータプログラムコードを読み込むことができるその他の任意の媒体などのリムーバブル記憶装置４０５に接続されていてもよい。コンピュータプラットフォームはさらに、インターネットやその他のローカルな公共または私的なネットワーク部品に繋がるネットワークリソース４０６に接続されていてもよい。ネットワークリソース４０６は、ネットワーク４０７上のリモートロケーションから命令およびデータをコンピュータプラットフォームへ供給してもよい。ネットワークリソース４０６への接続は、８０２．１１標準やブルートゥース（登録商標）やセルラープロトコル等の無線プロトコル経由で、または、電線やファイバ光学部品などの物理的伝送媒体経由であってもよい。ネットワークリソースは、コンピュータプラットフォーム４０１から遠隔の0場所にデータ及び実行可能な命令を格納するための記憶装置を含んでいてもよい。コンピュータはディスプレイ４０８と相互作用して、データおよびその他の情報をユーザへ出力したり、ユーザからの追加の指示と入力を要求したりする。従ってディスプレイ４０８は、ユーザと対話するための入力装置４０４としてさらに作用してもよい。
【００６５】
さらに、ここに開示した本発明の明細書を考察し、本発明を実施すれば、本発明の他の実装が当業者には明らかとなるであろう。前述の実施態様の様々な態様及び／又は構成要素は、ファイルグループ分けシステムに単独もしくは任意の組み合わせで使用することが可能である。明細書及び実施例は例示としてのみ理解されるべきであり、本発明の真の範囲と精神は添付の特許請求の範囲によって示されるものとする。
【符号の説明】
【００６６】
３０１  メモリ
３０２  境界ユニット（境界識別手段）
３０３  クラスタ決定ユニット（クラスタ決定手段）
３０４  ディスプレイ
４０２  プロセッサ
４０３  メモリ
４０４  入力装置
４０５  リムーバブル記憶装置
４０６  ネットワークリソース
４０７  ネットワーク
４０８  ディスプレイ
【図１】
0005962244.tif 000036
【図２】
0005962244.tif 000037
【図３】
0005962244.tif 000038
【図４】
0005962244.tif 000039