Automatic Organization for Digital Photographs with Geographic Coordinates
Mor Naaman, Yee Jiun Song, Andreas Paepcke, Hector Gracia-Molina
JSDL'04, pp.53--62, June, 2004.
You can get the paper from ACM Digital Library
PhotoCompasというシステムの提案をした論文
この論文で行ったことをかいつまむと以下の通り
- 写真の(撮影)位置と時刻を写真群のグループ化に利用し，自動的に写真群をイベント&位置毎に分類する
- 写真閲覧のためにイベント情報(写真群情報)と位置情報を階層化する
- さらにこの階層化された写真群に地理的な名称を自動で付与していく
時刻や位置情報で写真を自動的にクラスタ化(グループ化)するのが"はやり"のようである．ただ，多くの人はイベント毎にディレクトリを作り，その中にそのときの写真をまとめて保存しているとも考えられると，こういう手法が必要なのかどうかも疑問ではある．ただし閲覧時の利便性を追求した，データ (写真)の管理方法と言われれば，それは必要なのかもしれない．ただし，閲覧のためのシステムはこの論文ではまったくふれられてはいない．
撮影時刻を利用して写真群をクラスター化(グループ化)する論文はいくつかあるようだが，位置情報を利用したのはこの論文が初めてなのでは? と著者も言っている．
要点(になってない!?)をかいつまむと以下の通り
■ Introduction
- 位置情報は強力な記憶の手がかり(memory cue)のひとつ．
- 写真に位置情報を付与するのは不可能ではなくなってきつつある
- 位置情報は写真群の閲覧や整理にとって有用である．
- 位置情報を使った写真の整理法(組織化法)を提案
- 写真には撮影時刻と位置情報がついていることを仮定する
- より効率的な写真の検索や閲覧のため
- 地図の利用は考えない
- 地図を使うことは"画面領域の無駄使い"
- 小さな画面(PDA, 携帯電話)では表示不可能
- 写真は散見しており，操作が面倒になる
- 小さな画面(PDA, 携帯電話)では操作性の低下
- PhotoCompasでは主に2つの目標を挙げる
- 写真群を自動的にグループ化 (イベント(すなわち時刻)と位置情報)
- イベントと位置によるグループ化
- 2つの手法の組合せにより実装
- 時刻ベースのイベント発見手法
- 時間-位置によるクラスタリング
- 著者の知る限りでは，時刻の他に位置情報を使ってイベント検出アルゴリズムを提案した世界初の論文
- 生成されたグループに対して直感的に理解可能な地理名称を自動的に付与
- それぞれのイベントや位置に対して意味のある地名を生成
- 地図がなくても位置を同定できるようにする
-行政区データとGoogleなどのWebサーチエンジンを使った手法を提案
■ Discovering the Structure of an Image Collection
- ある個人の写真(または1つのカメラで撮影された写真)を想定
- 第一カテゴリは位置情報，第二カテゴリがイベント(時刻ベース)
- 位置情報にも，時刻も情報は階層化されている．
- 位置情報は行政区 (国，都道府県，市区町村)
- 時刻は年月日，時分秒
- なぜこれらの階層情報を使わないのか?
- ユーザにとってはあまりにも固定的で扱いにくい
- 時にそれらの分類は詳細すぎる
- よって別の階層情報を提供する
- それらの値の実数を使って新たな(代わりの)階層情報を提供
- 以降では使う，2つの言葉を定義する
- cluster
- 位置情報に関する階層情報内のノードを表す
- 複数の写真(同一位置情報の)がこのノードに含まれる
- segment
- 連続した写真群(時刻に基づく)
- これはユーザのイベントを表す(ハワイ旅行，運動会 etc?)
■ Requirement for Event Category
- 写真群はイベントとして定義できるだろう (例: 結婚式，休暇，誕生日 etc)
- 時間順に写真を見れば，イベント毎に写真を分類することは，写真撮影者本人なら容易にできるだろう
- この処理を自動化する
- StoryLineを仮定
- 単一撮影者の写真 / または単一カメラにより撮影された写真
- burst性を仮定
- あるイベントで多数の写真を撮ったかと思えば，しばらくは何も撮らない期間がある
- つまり写真撮影には時刻的に見ると大きな偏りがあるはず，これをイベント検知に利用
- イベントカテゴリは平坦な構造か? 階層構造か?
- 基本的に階層構造化が可能
- 誕生日を考えてみよう．Topレベルのイベントは「我が誕生日」だろう
- が，サブイベントとして，以下のようなイベント分類もできるだろう
- 乾杯
- ケーキ入刀
- プレゼントを開けた
- しかし，本研究では最上位のイベントしか抽出しないこととする
- よってrequirementとは以下の4つとする
[i.] 連続した写真がひとつのイベントに含まれる
[ii.] ある一定期間以上の間が写真間にあった場合には，以降の写真は新しいイベントだと判断する．この閾値は，位置情報のクラスタリングに基づき動的に変わるべき
[iii.] イベント内写真の類似性(burst性を利用)，写真間の時間間隔は安定した(?)間隔内であるはず
[iv.] 連続した写真の距離は，イベント境界を示す一つの指針だろう．
■ Requirement for Location Category
- 位置情報階層は，User interfaceとイベント分割の双方で使用する
- ユーザは徐々に位置を絞りこみ，希望の写真にたどり着けるようにしたい．
- 階層は無限の深さを持てるが，今回の実装では2 or 3階層に制限する
- 最上位の階層は「国名」とする
- 誰でも付与可能で，これを忘れることはまれであろう．
- 第二階層は"cluster(定義は上述)"とする．
- clusterを(細)分割するのは，その場所にて撮影した写真の枚数がある閾値を超えた時
[v.] 階層木は繁雑にならないようにする
[vi.] ノードは冗長にならないよう，一つしか子ノードを持たないノードは存在しない
さらに，階層は以下のガイドラインにも従うよう努める
[vii.] 数枚の写真しかないノードは他のノードに集約される．ただし位置的にかなり違う場合はこの例外とする
[viii.] 階層内のどのレベルでも，写真pは地理的にもっとも近いlocationノードに含まれる．ここでいう距離は，写真の位置情報と，clusterの中心位置との距離とする．
[ix.] ほぼ同じ時間帯(時刻)に撮影された写真は同じ位置clusterに属する．
これにより，異なる位置clusterとして分割されそうな場合も一つの位置clusterとすることが可能
[x.] 葉ノードとなるclusterは写真を過剰に含まないようにする．もしそうなりそうならば，clusterを分割する．
- これらのガイドラインはしばしば矛盾するかもしれないし，これらに従うことができないこともあるかもしれない．
■ A Three-Pass Algorithm for Genrating Location and Event Categorization
- イベントと位置情報の階層構造を生成するアルゴリズムの説明
- 時間と位置を別々に処理するのではなく，ハイブリッド型の処理
- 第一段階
- 連続した写真間の時間間隔と距離を計算
- これらによりlow-levelの"segment"を生成
- 第二段階
- 地理的クラスタリングによってクラスタ(群)を生成
- 生成されたクラスタは，重複しない特定の位置情報(地区)を表す
- 全ての"segment"はそれぞれ一つの"cluster"に属する
- 第三段階
- 別の時間ベースの処理でイベントに分割(集約?)
- 生成された位置情報clusterを基に近接した"segment"を集約する
- 詳細は以下に説明する
■ Step 1: Computing Mover
- 写真群を時刻ベースで分割
- burst性を利用，two-passで処理
- One-Pass
- 写真を撮影時刻順に並べる
- 連続した写真間の時間差を算出
- ある閾値以上かどうかを判定
- 現在の閾値は12時間
- Two-Pass
- さらに細かなsegmentに分割
- 生成されたsegment内の連続した写真の時間差と距離差を利用
- 統計的手法により閾値を決定して分割 (参考文献 7)
- 閾値は，分割しすぎにならないよう控えめに設定
■ Step 2: Computing the Location Clusters
- "SegmentCluster"というアルゴリズムを使用 (参考文献 5)
- 個々のsegmentは特定の地区の写真のみを持つと仮定
- 位置クラスタの各位置と，segment内の写真の撮影位置との一致確率を求める
- 位置クラスタ内の全ての位置と，セグメント内の全ての写真の一致を確認すると計算量が膨大になる可能性があるため，クラスタ内からいくつの位置情報を選択して一致するかを試験するらしい．その個数選択のためのBIC(Bayesian Information Criterion)という理論が出てくるらしいが，そこはパス
- "SegmentCluster"を終了すると，階層構造のない地理クラスタリストが得られる
- これらは地区の大きさ，含まれるセグメントや写真数が異なる(偏りがある)
- 多数のセグメントが含まれるclusterは，ユーザに馴染みのある(居住?)地区である可能性がある
- そういったclusterに対しては，"SegmentCluster"を再帰的に行なう
- こうすることで階層化ができる
■ Step 3: Towards Moptimal
- 位置の同定はできたが，イベントの同定はできていない
- ユーザが分割するように，イベント分割を実現する
- 方法としては同じclusterに属する似通ったsegmentを併合する
- ただしsegment間の時間差はある時間未満であること
- この閾値はclusterの要素数の逆関数によって決定される
- つまり多数のsegmentがclusterに含まれていれば，閾値となる時間差は小さくなる
- つまり(2)，めったに来ない場所ではおおまかにclusterが生成される
- これらの結果により，位置情報の階層構造clusterと，イベント分割が得られる．
■ Naming Geographic Locations
- イベント分割と階層化位置clusterが得られた，次はこれをユーザに提示する
- が，地図を使わずに効率的な写真ブラウジングができるようにしたい．
- 文字による適切な題名を個々のグループにつけてやることが重要
- イベントにも位置clusterにも「地名」をつけることとする
- イベントの題目は位置clusterよりも一般に詳細(特定された)情報となる
- 例: 位置クラスタ上では"Sanfrancisco Bayarea"だが，イベント題目は"Stanford Univ."となる
- 一般的に要求される用件は以下の通り
[i.] 適切な意味を持つ，かつ正確な情報．
[ii.] 認識可能なこと
[iii.] 唯一であること．同じ場所で撮影されたのでない限り，異なる名称であること
[iv.] 可能な限り，短いこと．
■ Naming a set of Geographic Coordinates
- 座標点群から"いい名称"の候補を探すために我々がとった方法
- 3つの段階
- 1段階: 州，市，公園毎の緯度経度値を取得しておく (administrative regions (管理区域 = 行政区域?))．その上でデータの各座標点がどの領域に含まれるかを検査し，頻度表を生成．最終的に包含表(containment table)を得る
- 2段階: 近隣の街を探し，その街への距離を算出する．すると"40KM south of San Francisco"といった名称が生成できる．この街の選択には人口数と"Google count"による"重力"法を用いる．ここでいう"Google count"とは街名をキーとしてGoogle検索を行ったときに得られる検索結果数のことを指す．つまりその街がどれだけ知られているかを示すことになり，著明であれば，参照名としても有用であると言えるからである．例えば"30KM north of San Jose"と"40KM south of San Francisco"というふたつの候補が得られた場合，Google countではSan Franciscoの方が著名であると結果となるので，距離としてはSan Joseの方が近いのだが，参照名としてはSan Franciscoの方を使用する．この処理の結果として名称と頻度からなる近隣都市表(nearby-cities table)が生成される．
- 3段階: これまでに得られた表から1-3単語を選択する．例としては，containment tableからとnearby-cities tableからもっとも頻度の高い単語を選んでくる方法である．この方法については次章で説明する．
■ Naming Location Clusters and Events
- 名前付けに関するいろいろな戦略
- イベントの名称，位置情報階層の中の葉ノードなのか内部ノードかによって方法は異なる
- 位置情報階層の葉ノードの場合．非常に難しいが，重要でもある．
- 1. containment tableの最頻度単語を使う
- 2. containment tableの第二の単語をくっつける
- 3. クラスタ内のセグメントが少ないまたは上位2つの単語がスコアが低い場合，都市名を付与する
- 位置情報階層の内部ノードの場合．国名だったりして，比較的容易?
- 詳細な位置名称を並べず，大まかだが短い位置名にする
- イベント名称への付与
- そのイベントに関して訪れた位置はごく少数であると仮定 = 位置情報はかなり特定される
- Containment tableの最頻度単語を使う，必要であれば時間(期間)情報(例: Dec 31(3 hours))を付加する
■ EXPERIMENTS and RESULTS
- 本システムで生成される出力は3つ
- イベント分割 (event segmentation)
- 位置情報階層 (location hierarchy)
- 名称候補 (suggested names)
- 被験者は二人，あと開発者本人
- アメリカ国外の写真が少なかったため，アメリカ国内の写真のみで行った．
■ Evaluation of Event Segmentation
- まずはじめに写真所有者に手作業でイベント分割してもらう(ground truth(Moptimal))
- はじめに提示したガイドラインになかなか従わない分割もある．
- 複数日にわたった写真を一つのイベントとして分割している(This was my trip to New York)．
- 同日の写真を別のイベントとして分割
- 我々の評価目標は次の通り
- 1. 正確か?
- 2. パラメータの変更による分割結果の効果
- 3. Mover(3.2.1)が本当に望んだイベント分割よりも細分化されているか確認
- 数値指標として2つの値を使用．
- precision (精度?)
= (意図通りに発見された境界の数 / 発見された境界の総数)
- recall (不良/取り消し?)
= (意図通りに発見された境界の数 / 正解である境界の総数)
- しかし，これらの値だけでは問題有り (きちんと評価できない場合も)
- さらに2つの指標を用いる
- Pk metrics
Windowをslideし，連続した写真が同じイベントに含まれるかどうかで判断
- Window Diff
Windowをslideさせ，そのWindow内の境界数を数える．それと正解である境界の数と差分を調べ，その値に応じてペナルティを与えるという手法
- どちらも値域は[0, 1]であり，値が小さいほど良い値であることを示す
- 方法としては4つの方法を用いて，その結果を比較
- PC: PhotoCompasアルゴリズムを使用
- TB: 時間ベースのアルゴリズムを使用 (参考文献7)
- FT: 固定時間間隔によるイベント分割
- FS: 時間と距離による固定閾値のイベント分割
- 結果としてはrecall, precision, Pkmetrics, Window DiffのすべてにおいてPhotoCompassがよい結果となった
- 境界が検知されにくい場合
- 位置がほとんど変わらず，かつ数時間内に数枚の写真だけで成り立っているイベント
- 分割しすぎてしまう場合:
- Road tripの場合．数日に渡って写真が撮影されており，移動範囲も広い．
- 街中での出来事．なので位置はそれほど変わらないが，時間間隔はずいぶん開いている場合．ユーザはこれを同じイベントとして "くくりたい" という事象があった．
■ Evaluation of Location Hierarchy
- 生成された位置情報階層を写真の所有者にインタビューすることで質的評価を行った
- 二人とも，写真の多くは数都市にまとまっていた．
- 確認項目は以下の通り
- 写真所有者に受け入れられるか?
- 現実の地理情報と，生成された位置階層構造が似ているか?
- 写真が間違った位置に割り当てされていないか?
- 既存の階層構造(州/市)より好ましいか?
- 階層構造の上位部分は大体受け入れられた．
- しかし，いろいろとコメントもある
- 一つの位置ノードを州を単位としたふたつのノードに分割
- 違う州の位置ノードを一つに統合
- 低レベルのノードでユーザの意図と異なることが多い．
- 写真の位置ノードへの割り当ては難しい．Road Tripに行った場合などは位置が広範囲になる．しかし，クラスタとしては一つにまとまって欲しいという要求がでる．すると位置クラスタのノード間で「重なり」ができてしまう．
- 現実の行政区域と生成された位置情報階層との比較は，一長一短である．なじみのないところで行政区域を使用するのは難しいこともある．
■ Evaluation of Naming
- 写真所有者によるインタビューで評価
- 位置階層情報につけられた名称のみを評価対象とした (イベントにつけられた名前は無視した)
- 所有者にとって有益か? = つけられた位置名がそのノードがカバーする領域を理解するのに端的な名前か?
- 写真所有者がつけた名前と生成された名前が似ているか?
- 76%のノードの地名は，ユーザが位置候補名から選んで生成した名称の地名と一部と一致していた．
- 残りの24%も大体有用であるという意見を得た
- 問題点もあり
- 3つの都市の写真が含まれていたのだが，East Coast，XXXというふうに3つの都市の一つの都市名だけがついていた
- 公園または市の名前だけがついていたクラスターがあったが，その名前は知られていなかった．
- その名称は，クラスター内の一部の写真を適切に表していなかった．
- とはいえ，評価者は大体満足していた．
■ 結論と今後の課題
Photo collection(写真群)を意味のあるグループに自動分類する手法を提案
- イベントに基づき写真を分類
- 位置情報の階層化
- 各イベントへの名前付け(位置に基づく名称)
PDA上でのUser Interfaceを構築しているらしい(別論文)
地図ベース(geo-referenced)のインタフェースと我々のインタフェースとの比較も予定
問題としては複数年にわたった写真群をうまく扱えるかや，名前付けアルゴリズムの改良などがあると考えている．