位置・方向情報付写真群を用いた空間を要約する経路の生成

DEIM Forum 2016 H5-4

位置・方向情報付写真群を用いた空間を要約する経路の生成

相楽 翔太

†

藤田 秀之

†

大森 匡

†

新谷 隆彦

†

†電気通信大学大学院情報システム学研究科 〒182-8585 東京都調布市 調布ケ丘 1 丁目 5-1

E-mail:

†

{sagara.s, fujita, omori, shintani}@hol.is.uec.ac.jp

あらまし：地理空間情報を扱う SNS 等のデータから高価値な空間情報の抽出や可視化を行う研究は，今日のデータ工学にと って重要な課題の一つである．本研究では，対象とする地理空間における位置・方向情報のついた写真データ群を入力として， それらから，当該空間の情報を要約する経路を自動抽出し表示する技法を提案する．具体的には，i) 多数の写真の撮影対象 となっている/そこから多数の写真が撮影されている，特徴的な authority/hub 領域，および，walk-through と呼ぶ断片的な 経路，の 2 種類の情報を写真群の配置パターンに基づいて自動抽出し，ii) それらを組み合わせて，対象空間を要約する経路 （空間要約経路と呼ぶ）を生成する，という枠組みを採用する．本稿では，特に，walk-through と呼ぶ経路抽出のため，位 置・方向情報付写真をノードにした近接グラフを提案し，それを用いた空間要約経路の生成までを述べる． キーワード データストーリーテリング，可視化，位置情報付写真，方向情報，地理情報システム

1． 研 究 背 景 と 目 的

図 1 空 間 要 約 経 路 の 概 念 図 地 理 空 間 情 報 を 扱 う SNS 等 の デ ー タ か ら 高 価 値 な 空 間 情 報 の 抽 出 や 可 視 化 を 行 う 研 究 は 今 日 の デ ー タ 工 学 に と っ て 重 要 な 課 題 の 一 つ で あ る ． な か で も ， 写 真 デ ー タ 集 合 を 用 い て 重 要 な 地 域 を 求 め た り ， 経 路 を 生 成 し た り す る 事 例 は 多 い [1,2,3,4,5,6] ． 一 方 で ， cartography （ 地 図 学 ） の 分 野 で 扱 う 地 図 の 作 成 や 経 路 地 図 作 成 の 水 準 に は 及 ば な い の が 実 情 で あ る ． 具 体 的 に は ， 写 真 デ ー タ 集 合 を 用 い て 抽 出 し た 領 域 や 経 路 を 組 み 合 わ せ て ， 対 象 空 間 の 概 要 を 総 合 的 に 提 示 す る こ と を 目 的 と し た 研 究 は 我 々 の 知 る 限 り 存 在 し な い ． そ こ で 本 稿 で は ， 位 置 （ 撮 影 時 の カ メ ラ の 位 置 ） お よ び ， 方 向 （ 撮 影 時 の カ メ ラ の 方 向 ） の 情 報 を 持 つ 写 真 （ 位 置 ・ 方 向 情 報 付 写 真 と 呼 ぶ ） 群 を 用 い ， 空 間 を 要 約 す る 経 路 を 生 成 し ， 略 地 図 に 相 当 す る 水 準 で ユ ー ザ に 理 解 し や す く 提 示 す る 手 法 を 提 案 す る ． 我 々 の 提 案 す る 枠 組 み は ， 次 の 通 り で あ る ． は じ め に ， 多 数 の 写 真 の 撮 影 対 象 と な っ て い る 領 域 （ Authority spot と 呼 ぶ ）， そ こ か ら 多 く の 写 真 が 撮 影 さ れ て い る 領 域 （ Hub spot と 呼 ぶ ） と い っ た 特 徴 的 な 領 域 を 抽 出 し て お く ． 次 に ， 対 象 空 間 内 の 断 片 的 な 経 路 で 利 用 者 か ら 見 た 視 点 に 連 続 性 を 与 え る よ う な も の (Walk-through と 呼 ぶ ) を 写 真 群 の 配 置 パ タ ー ン に 基 づ い て 抽 出 す る ． そ し て ， 両 者 を 統 合 し た グ ラ フ 構 造 を 作 成 し ， そ こ か ら ， 対 象 空 間 を 要 約 す る 経 路 （空 間 要 約 経 路と 呼 ぶ ） を 生 成 す る ． 生 成 し た 経 路 に 沿 っ て ， 写 真 を 順 番 に 提 示 す る こ と で ， 視 覚 的 な 連 続 性 （ 写 真 同 士 の 位 置 や 方 向 の 連 続 性 ）を で き る だ け 保 ち な が ら ， 逐 次 的 な 情 報 提 示 を 行 う こ と が 可 能 に な る ． authority spot や hub spot の 抽 出 手 法 は ，文 献 [9]に ま と め た ．本 稿 で は 主 に グ ラ フ の 生 成 手 法 に つ い て 論 じ る ．

例 と し て ， 図 1 に 空 間 要 約 経 路 の 概 念 図 を 示 す ． 図 1 の 入 力 デ ー タ で は ， 道 路 に 沿 っ て い く つ か の 経 路 状 に 連 続 し た 写 真 群 が 存 在 し ， authority spot や hub spot が 点 在 し て い る ． 空 間 要 約 経 路 の 例 と し て ， 中 央 下 側 の authority spot を 提 示 し ， 図 の 上 方 に 向 か う walk-through を た ど り ，中 央 上 側 の hub spot を 提 示 し ， 図 の 下 方 に 向 か う walk-through を た ど る ， と い っ た 経 路 が 考 え ら れ る ． 図 2 空 間 要 約 経 路 の 作 成 方 針 本 稿 の 構 成 は 以 下 の 通 り で あ る ． 2 章 で ， 抽 出 す べ き 領 域 や 経 路 の パ タ ー ン を 挙 げ ， そ れ ら を 使 っ た 問 題 の 定 義 と 解 き 方 の 全 体 構 造 を 概 説 す る ． 併 せ て 関 連 す

る 研 究 と の 位 置 づ け 比 較 を 述 べ る ． 3 章 で は 位 置 ・ 方 向 つ き 近 接 グ ラ フ と 呼 ぶ グ ラ フ 構 造 を 提 案 し ， こ れ を 用 い た 経 路 生 成 手 法 と authority/hub spot の 埋 め 込 み 手 法 を 述 べ る ．4 章 で は 実 デ ー タ を 用 い て 検 証 を 行 い ，5 章 で 提 案 手 法 の 評 価 を 行 う ． 最 後 に ， 6 章 で 本 稿 の 要 約 を 行 う ．

2． 問 題 の 定 義 と 関 連 研 究

2.1 問 題 の 定 義

本 研 究 で 用 い る 概 念 の 定 義 を 次 に 示 す ． 位 置 ・ 方 向 情 報 付 き 写 真： 撮 影 位 置 ， 撮 影 方 向 の 情 報 を 持 つ 写 真 撮 影 位 置： 写 真 を 撮 影 し た 時 の カ メ ラ の 位 置 撮 影 方 向： 写 真 を 撮 影 し た 時 の カ メ ラ の 方 向 視 線： 撮 影 位 置 か ら 撮 影 方 向 へ の 半 直 線 進 行 方 向： 2 件 の 写 真 デ ー タ に つ い て ， 一 方 を 始 点 と し ， 他 方 を 終 点 と し て 両 者 の 撮 影 位 置 を 結 ん だ 直 線 の 方 向 空 間 要 約 経 路：入 力 さ れ た 空 間 デ ー タ (位 置 情 報 を 持 つ デ ー タ )に よ る 対 象 空 間 の 要 約 を ，対 象 空 間 内 の 経 路 上 の デ ー タ 列 と し て 表 現 し た も の ．本 研 究 で は ， 位 置 ・ 方 向 情 報 付 写 真 デ ー タ を 入 力 と し ， 特 定 の 空 間 配 置 を 持 つ ク ラ ス タ や ， 断 片 的 な 経 路 群 を 組 み 合 わ せ た 経 路 と し て ，空 間 要 約 経 路 を 生 成 す る ． ひ と つ の 入 力 デ ー タ に 対 し ， 複 数 の 空 間 要 約 経 路 を 想 定 す る ． 視 覚 的 連 続 性の あ る 経 路 ： 写 真 の 撮 影 位 置 を 結 ん だ 経 路 で あ り ， 経 路 上 の 連 続 す る 写 真 ど う し の 空 間 関 係 (例 え ば ， 前 進 し た ・ 横 を 向 い た な ど )を 人 間 が 理 解 で き る よ う な も の ． 本 研 究 で は ， 連 続 す る 写 真 に 画 像 と し て の 重 な り が な く て も ， 撮 影 位 置 や 撮 影 方 向 の 変 化 が ， 3 章 で 指 定 す る 条 件 を 満 た す 場 合 ， 視 覚 的 連 続 性 を 持 つ と 定 義 す る ． ス ト ー リ ー 形 式 の 情 報 提 示[7][8]：対 象 デ ー タ か ら 選 択 し た 複 数 の 要 素 に 提 示 順 序 を 決 定 し ， 逐 次 的 に 提 示 す る こ と ． 本 研 究 で は ， 生 成 し た 情 報 要 約 経 路 に 沿 っ て ， 写 真 を 順 番 に 提 示 す る こ と で ， ス ト ー リ ー 形 式 の 情 報 提 示 を 実 現 す る ． 撮 影 位 置 は 緯 度 ・ 経 度 で 与 え ， 撮 影 方 向 と 進 行 方 向 は 東 を 0 度 と し た 角 度 で 与 え る ．本 稿 で は ，撮 影 位 置 ， 撮 影 方 向 と も 二 次 元 平 面 上 で の 値 と し ， 高 さ 方 向 の 値 を 考 慮 し な い ． 以 上 を 用 い て 本 研 究 の 目 的 を 次 の よ う に 定 め る ． ・ 位 置 ・ 方 向 情 報 付 き 写 真 群 を 用 い ， 指 定 さ れ た 領 域 に つ い て の ， 視 覚 的 連 続 性 の あ る 空 間 要 約 経 路 を 生 成 し ， ス ト ー リ ー 形 式 の 情 報 提 示 を 実 現 す る

2.2 問 題 の 解 き 方 の 方 針

写 真 群 の 配 置 パ タ ー ン に 基 づ き 特 徴 的 な 領 域 を 抽 出 し ， そ れ ら を 組 み 込 ん で 空 間 要 約 経 路 を 作 成 す る ． 図 2 に 空 間 要 約 経 路 の 作 成 例 を 示 す ． 円 や 楕 円 で 囲 ま れ た 領 域 は ， 特 徴 的 な 領 域 を 示 す ． 図 3 に 本 研 究 が 対 象 と す る 特 徴 的 な 領 域 の 例 を 示 す ． 図 3 特 徴 的 な 領 域 写 真 群 の 配 置 パ タ ー ン に 基 づ く 特 徴 的 な 領 域 に は ， そ こ か ら 多 く の 写 真 が 撮 影 さ れ て い る 領 域 (図 3(a))や ， 多 数 の 写 真 に 写 っ て い る 領 域 (図 3(b))， 断 片 的 な 経 路 状 の 領 域 (図 3(c))な ど が 知 ら れ て い る [1,6]．本 研 究 で は (a)を hub spot，(b)を authority spot，(c)を walk-through と 呼 ぶ ． ま た ， (a),(b)を ま と め て ス ポ ッ ト と 呼 ぶ ． 本 研 究 で は ， ま ず ， 対 象 の 写 真 デ ー タ 群 か ら (a),(b) の ス ポ ッ ト を 抽 出 す る ． 続 い て ， 対 象 の 写 真 デ ー タ 群 か ら ， 各 写 真 を ノ ー ド と し て ， そ の 位 置 ・ 方 向 情 報 を 考 慮 し た 近 接 グ ラ フ を 作 成 す る ． こ の 近 接 グ ラ フ 上 の 断 片 的 な 経 路 群 は (c)に 対 応 す る ．さ ら に 抽 出 し た ス ポ ッ ト を 構 成 す る 写 真 群 を ， 近 接 グ ラ フ に 部 分 グ ラ フ と し て 組 み 込 む ．最 終 的 に ，近 接 グ ラ フ 上 の 経 路 と し て ， 空 間 要 約 経 路 を 生 成 す る ． こ の 近 接 グ ラ フ の こ と を 本 研 究 で は位 置 ・ 方 向 情 報 近 接 グ ラ フと 呼 ぶ ． ス ポ ッ ト の 抽 出 方 法 に つ い て は 文 献 [9]に ま と め た ． 本 稿 で は 主 に 位 置 ・ 方 向 情 報 近 接 グ ラ フ の 生 成 に つ い て 述 べ る ．

2.3 関 連 研 究 と 本 研 究 の 位 置 付 け

大 量 の 軌 跡 デ ー タ か ら ， 経 路 を 始 め と す る さ ま ざ ま な 要 素 を 抽 出 す る 手 法 が ， 軌 跡 パ タ ー ン マ イ ニ ン グ [10] と し て 体 系 化 さ れ て い る ． し か し ， 対 象 デ ー タ の 性 質 が 異 な る た め ， 本 研 究 に 直 接 適 用 す る こ と は で き な い ． 具 体 的 に は ， 軌 跡 パ タ ー ン マ イ ニ ン グ の 対 象 デ ー タ は 軌 跡 デ ー タ で あ り ， 軌 跡 を 構 成 す る 点 列 は ， 位 置 ・ 方 向 を 持 つ と 言 え る が ， そ の 方 向 は ， 点 と 点 を 結 ぶ 方 向 （ 進 行 方 向 ） で あ る ． ま た ， 各 点 は 軌 跡 上 の 点 列 と い う 構 造 を 持 つ ． 他 方 で ， 本 研 究 の 対 象 デ ー タ の 場 合 ， 各 点 （ 位 置 ・ 方 向 情 報 付 写 真 ） は ， 進 行 方 向 に 加 え ， 進 行 方 向 と は 異 な る 方 向 （ 撮 影 方 向 ） を 持 っ て い る ． ま た ， 各 点 は ， 軌 跡 上 の 点 列 と い う 構 造 を 持 た

な い ． 方 向 を 持 っ た 点 群 を 扱 う 研 究 は 多 く は な い ． ク ラ ス タ リ ン グ 手 法 の 提 案 [11]の 他 ， 位 置 ・ 方 向 情 報 付 写 真 群 を 対 象 と す る 研 究 と し て ， 空 間 検 索 ， 場 所 抽 出 ， 撮 影 対 象 の 位 置 や 形 状 の 推 定 手 法 な ど が 提 案 さ れ て い る [1,2,3,5,6] ． 特 に ， 文 献 [6] は ， 画 像 情 報 を 用 い て 画 像 の 合 成 を 行 う こ と で ， 映 像 に 近 い ， 非 常 に 視 覚 的 連 続 性 の 高 い 情 報 提 示 を 実 現 す る ． そ の た め ， 入 力 デ ー タ と し て ， 互 い に 重 な り の あ る 画 像 群 を 必 要 と す る 点 が 本 研 究 と 異 な る ． 位 置 情 報 付 写 真 群 を 用 い た 経 路 生 成 に 関 し て は ， 旅 行 計 画 問 題 と し て と ら え た 提 案 [4]が あ る ． 情 報 可 視 化 の 分 野 に お い て ， 対 象 と な る デ ー タ を ス ト ー リ ー 形 式 で 提 示 す る ， ナ ラ テ ィ ブ ・ ビ ジ ュ ア ラ イ ゼ ー シ ョ ン [10] や デ ー タ ス ト ー リ ー テ リ ン グ [11]と 呼 ば れ る 手 法 が 提 案 さ れ ， 適 用 分 野 を 広 げ て い る ． 人 間 が 理 解 ・ 把 握 す る こ と が 困 難 な 大 規 模 デ ー タ に 適 用 [12,13]し ， デ ー タ の 理 解 を 支 援 す る 手 法 も 提 案 さ れ て い る ． 本 研 究 は ， 位 置 ・ 方 向 情 報 付 写 真 デ ー タ に 対 す る ， デ ー タ ス ト ー リ ー テ リ ン グ 手 法 の 提 案 と も 位 置 付 け ら れ る ．

3． 位 置 ・ 方 向 情 報 近 接 グ ラ フ

3.1 概 要

本 章 で は ， 位 置 ・ 方 向 情 報 を 考 慮 し た 近 接 グ ラ フ を 提 案 す る ． 提 案 す る グ ラ フ を ， 位 置 ・ 方 向 情 報 近 接 グ ラ フ と 呼 ぶ ． 位 置 ・ 方 向 情 報 付 写 真 を ， 位 置 ・ 方 向 情 報 を 持 つ 空 間 上 の 点 と し て 扱 い ， グ ラ フ の ノ ー ド と す る ． グ ラ フ は 有 向 グ ラ フ と す る ． グ ラ フ 作 成 の た め の 入 力 情 報 は 次 の 通 り で あ る ． ・ 対 象 領 域 （ 地 図 上 の 矩 形 領 域 と し て 与 え る ） ・ 対 象 領 域 内 の 位 置 ・ 方 向 情 報 付 写 真 群 （ 撮 影 位 置 と 撮 影 方 向 を 利 用 す る ） 目 的 は ， グ ラ フ 上 の ノ ー ド を た ど る 際 に ， 写 真 の 撮 影 方 向 や ，ノ ー ド 間 の 方 向（ 進 行 方 向 ）と 撮 影 方 向 が ， な だ ら か に 変 化 す る よ う な グ ラ フ で あ る ． グ ラ フ の 要 件 を 以 下 に ま と め る ． 図 4 位 置 ・ 方 向 情 報 近 接 グ ラ フ の 概 念 図 位 置 関 係 に 関 す る 要 件 ・ ノ ー ド の 位 置 関 係 や 方 向 関 係 を 考 慮 し て ， 2 ノ ー ド 間 に 中 継 点 と な る よ う な ノ ー ド が 存 在 す る 場 合 ， 2 ノ ー ド を 直 接 接 続 せ ず ， 中 継 点 を 経 由 す る よ う に 接 続 す る 方 向 関 係 に 関 す る 要 件 ・ グ ラ フ 上 で 接 続 さ れ た 2 ノ ー ド の 方 向（ 撮 影 方 向 ） が 変 化 し す ぎ な い よ う に す る ・ グ ラ フ 上 で 接 続 さ れ た 2 ノ ー ド 間 を エ ッ ジ に 沿 っ て 移 動 す る 際 に ， 始 点 ノ ー ド の 方 向 と 大 き く 変 わ ら な い 方 向 に 進 む （ 後 ろ 向 き に 進 ま な い ） よ う に す る 位 置 関 係 に 関 す る 要 件 を 図 4 で 説 明 す る ．赤 色 の 矢 印 p，q，r が 位 置 ・方 向 情 報 付 写 真（ 撮 影 位 置 か ら 撮 影 方 向 へ の 矢 印 ）で あ り ，こ れ ら を グ ラ フ の ノ ー ド と す る ．青 色 の 線 を グ ラ フ の エ ッ ジ ，緑 の 矢 印 を 経 路 と す る ．図 4(a)は ，対 象 と す る 3 ノ ー ド 間 す べ て に エ ッ ジ を 生 成 し た グ ラ フ で あ り ，図 4(b)は 目 的 と す る グ ラ フ で あ る ．今 ，ノ ー ド p か ら ノ ー ド r へ の 最 短 経 路 を 考 え る ． 図 4(a)の 場 合 ， p と r を 直 接 結 ぶ 経 路 が 生 成 さ れ る ． し か し ， q を 中 継 点 と し て 経 由 す る 方 が ， ノ ー ド 間 の 距 離 が 小 さ い ， よ り な だ ら か な 経 路 と な る ． そ こ で 本 研 究 で は ， 図 4(b)の よ う に ， q を 経 由 す る 経 路 を 生 成 す る グ ラ フ を 目 的 と す る ． 以 降 ， 3.2 節 で ， 位 置 向 関 係 に 関 す る 要 件 の 実 現 に 応 用 す る 関 連 技 術 と し て ，ガ ブ リ エ ル グ ラ フ に つ い て 説 明 す る ． 3.3 節 で ， 方 向 関 係 に 関 す る 要 件 を ， 具 体 的 な 条 件 と し て 定 義 す る ． 3.4 節 で ， グ ラ フ の 生 成 手 法 を ， ノ ー ド の 接 続 条 件 と し て 定 義 す る ．

3.2 ガ ブ リ エ ル グ ラ フ

[14] 図 5 ラ ン ダ ム な 100 点 に よ る ガ ブ リ エ ル グ ラ フ (出 典 ： wikipedia)

近 接 グ ラ フ は ， 位 置 情 報 を 持 つ 点 群 デ ー タ を 対 象 と し ， 各 点 を ノ ー ド と し ， 点 の 位 置 の 近 接 性 に 基 づ い て エ ッ ジ を 生 成 す る グ ラ フ の 総 称 で あ る ． 近 接 グ ラ フ の 一 種 と し て ， ガ ブ リ エ ル グ ラ フ [14]が 存 在 す る ． 例 を 図 5 に 示 す ． ガ ブ リ エ ル グ ラ フ の 構 築 方 法 は ， 任 意 の 2 ノ ー ド 間 の エ ッ ジ の 生 成 条 件 と し て 定 義 さ れ る ． す な わ ち ， 任 意 の 2 ノ ー ド を 直 径 と し た 円 内 に 他 の ノ ー ド が 存 在 し な い 場 合 に 2 ノ ー ド 間 に エ ッ ジ を 生 成 す る ． 本 研 究 で は ， ノ ー ド の 位 置 関 係 に 関 す る 要 件 に 対 応 す る た め ，ガ ブ リ エ ル グ ラ フ の 構 築 手 法 を 参 考 に す る ． た だ し ， ガ ブ リ エ ル グ ラ フ は 本 来 方 向 情 報 を 考 慮 し な い た め ， 本 研 究 で は ， 後 述 の と お り ， 方 向 情 報 を 考 慮 し た エ ッ ジ 生 成 条 件 を 用 い る ．

3.3 方 向 情 報 に 関 す る 連 続 性 の 条 件

図 6 方 向 情 報 と 進 行 方 向 の 概 念 図 方 向 情 報 に 関 す る 接 続 条 件 を 次 の よ う に 定 義 す る ． 図 6 に 示 す と お り ，任 意 の 2 ノ ー ド 𝑖, 𝑗を そ れ ぞ れ 始 点 ， 終 点 と し ， そ れ ぞ れ の 持 つ 方 向 情 報 を 𝑖. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛, 𝑗. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛と す る ． ま た ， 𝑖か ら 𝑗に 向 か う 直 線 の 方 向 を 進 行 方 向 と 呼 び ， 𝑒𝑖𝑗. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛と 表 す ． こ こ で ，以 下 の 条 件 を 満 た す 時 ，始 点 ノ ー ド 𝑖と 終 点 ノ ー ド 𝑗は「 方 向 情 報 に 関 す る 連 続 性 の 条 件 を 満 た す 」と 定 め る ． (1)𝑖. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛と 𝑗. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛の 差 ≤ α か つ (2)𝑖. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛と 𝑒_𝑖𝑗. 𝑑𝑖𝑟𝑒𝑐𝑡𝑖𝑜𝑛の 差 ≤ α こ こ で ， αは 角 度 の 閾 値 で あ る ． 図 7 に 例 を 示 す ． 図 7(a)は 方 向 情 報 に 関 す る 連 続 性 の 条 件 を 満 た す ．図 7(b)は ，条 件 (2)は 満 た し て い る が ， 条 件 (1)を 満 た し て い な い た め ，方 向 情 報 に 関 す る 連 続 性 の 条 件 を 満 た さ な い ．図 7(c)は 条 件 (1)は 満 た し て い る が ，条 件 (2)を 満 た し て い な い た め ，方 向 情 報 に 関 す る 連 続 性 の 条 件 を 満 た さ な い ．

3.4 位 置 ・ 方 向 近 接 グ ラ フ の 構 築 手 法

任 意 の 異 な る 2 ノ ー ド 𝑖, 𝑗(順 序 を 考 慮 す る )に つ い て ， 以 下 の 条 件 (1)(2)の 両 者 が 成 り 立 つ 場 合 ， 𝑖を 始 点 ， 𝑗を 終 点 と し て 接 続 し ， エ ッ ジ を 生 成 す る ． (1) 始 点𝑖， 終 点 𝑗が ， 方 向 情 報 に 関 す る 接 続 条 件 を 満 た す ． (2) 𝑖, 𝑗を 直 径 と す る 円 内 に ，以 下 い ず れ か を 満 た す ノ ー ド 𝑚が 存 在 し な い (2.1) 始 点𝑖， 終 点 𝑚が ， 方 向 情 報 に 関 す る 接 続 条 件 を 満 た す (2.2) 始 点𝑚， 終 点 𝑗が ， 方 向 情 報 に 関 す る 接 続 条 件 を 満 た す 例 を 図 8 に 示 す ． 図 8 2 ノ ー ド の 接 続 条 件 図 8(a)の ノ ー ド 𝑖. 𝑗は 接 続 条 件 を 満 た す ．一 方 ，図 8(b) の 場 合 ， 条 件 (2-1)， (2-2)を 満 た す ノ ー ド 𝑚が 𝑖, 𝑗を 直 径 と す る 円 内 に 存 在 す る た め ， 位 置 関 係 に 関 す る 接 続 条 件 を 満 た さ な い ．

3.5 位 置 ・ 方 向 近 接 グ ラ フ の 作 成 事 例

人 工 デ ー タ を 用 い て 位 置 ・ 方 向 情 報 近 接 グ ラ フ の 作 成 実 験 を 行 っ た ． 人 工 デ ー タ は ， 位 置 ・ 方 向 情 報 付 写 真 デ ー タ と 同 じ く ， 位 置 情 報 ， 方 向 情 報 を 持 つ ． ノ ー ド の 接 続 条 件 に お け る αの 値 は 90 度 と し た ． 経 路 状 に グ ラ フ を 作 成 す る こ と が で き た 例 を 図 9 に 示 す ． 図 7 方 向 に 関 す る 連 続 性 の 条 件 の 例

図 9 位 置 ・ 方 向 情 報 近 接 グ ラ フ の 成 功 例 経 路 状 に 配 置 さ れ た デ ー タ 群 の 場 合 ， 2 つ の 接 続 条 件 に よ っ て 位 置 ・ 方 向 ・ 進 行 方 向 に 従 っ て な だ ら か な 経 路 状 の グ ラ フ が 作 成 で き て い る ． こ の 近 接 グ ラ フ を 探 索 し た 場 合 ， デ ー タ の 持 つ 位 置 ・ 方 向 ・ 進 行 方 向 に つ い て 連 続 性 を 持 つ 経 路 を 作 成 で き る ． 一 方 ， 意 図 し た と お り に 作 成 で き な か っ た 例 を 図 10 に 示 す ． 図 10 位 置 ・ 方 向 情 報 近 接 グ ラ フ の 失 敗 例 図 10 の よ う に ， 分 岐 や 交 差 が 発 生 す る 場 合 ， 意 図 せ ず グ ラ フ の エ ッ ジ が 欠 落 す る 場 合 が あ る ． こ の エ ッ ジ の 欠 落 の 原 因 と し て ， 次 の よ う な 理 由 が 考 え ら れ る ． あ る ノ ー ド か ら の エ ッ ジ を 形 成 す る 際 は ， 撮 影 方 向 ・ 進 行 方 向 の 差 異 が 閾 値 内 の 対 象 ノ ー ド 群 の う ち ， 最 も 距 離 の 近 い も の だ け に エ ッ ジ が 形 成 さ れ る ． そ の た め ，条 件 を 満 た し て エ ッ ジ を 形 成 し た ノ ー ド の 他 に ， そ の ノ ー ド と 同 様 に 撮 影 方 向 ・ 進 行 方 向 の 差 異 が 小 さ く ， そ の ノ ー ド と 大 き く 変 わ ら な い 距 離 に あ る ノ ー ド と の エ ッ ジ が 形 成 さ れ な い ． 概 念 図 を 図 11 に 示 す ． 図 11 エ ッ ジ 欠 損 の 概 念 図

3.6 後 ろ 向 き 探 索 に よ る 再 接 続 手 法

エ ッ ジ の 欠 落 を 改 善 す る た め ，後 ろ 向 き 探 索 に よ る 再 接 続 手 法 を 提 案 す る ．他 の ノ ー ド か ら 接 続 さ れ て い な い (そ の ノ ー ド を 終 点 と し た エ ッ ジ が 生 成 さ れ て い な い )終 点 ノ ー ド を 𝑘と し ， 各 𝑘に つ い て 後 述 の 条 件 を 満 た す 始 点 ノ ー ド 𝑖の う ち ，𝑘と の 距 離 が 最 短 の も の を 接 続 す る ． 𝑖の 条 件 を 次 に 示 す ． ・ 𝑖と𝑘が 方 向 に 関 す る 連 続 性 の 条 件 を 満 た す and ・ 𝑖と𝑘の 距 離 ≤ 𝑖を 始 点 と す る 全 エ ッ ジ の 長 さ の 平 均 ×1.5 概 念 図 を 図 12 に 示 す ． 図 12 後 ろ 向 き 探 索 に よ る 再 接 続 手 法 の 概 念 図 提 案 す る 再 接 続 手 法 を 図 10 の 例 に 対 し て 適 用 し た 結 果 を 図 13 に 示 す ． 図 13 再 接 続 の 例 再 接 続 の 手 続 き を 行 っ た 後 で は ，分 岐 や 交 差 に お い て エ ッ ジ の 欠 落 が 起 こ ら な い こ と が わ か る ．

3.7 Authority/Hub spot の グ ラ フ へ の 組 み 込 み

authority spot や hub spot を 部 分 グ ラ フ と し て 位 置 ・ 方 向 情 報 近 接 グ ラ フ に 組 み 込 む ． 例 と し て authority spot を 対 象 と し た 組 み 込 み 手 法 の 概 念 図 を 図 14 に 示 す ．ス ポ ッ ト 内 は ガ ブ リ エ ル グ ラ フ の 接 続 条 件 で 双 方 向 の エ ッ ジ を 生 成 す る ． ス ポ ッ ト 外 の 1 ノ ー ド と ス ポ ッ ト 内 の 複 数 の ノ ー ド が 接 続 す る 場 合 ， エ ッ ジ は 最 短 の エ ッ ジ 以 外 は 削 除 す る ． hub spot に つ い て も 同 様 の 方 針 で グ ラ フ に 組 み 込 む ．

4． 検 証

実 デ ー タ に よ る 検 証 を 行 っ た ． 入 力 デ ー タ を 次 に ま と め る ． ・ 対 象 領 域 ： 柴 又 駅 ～ 帝 釈 天 周 辺 ・ 写 真 デ ー タ ： 対 象 領 域 内 の 位 置 ・ 方 向 情 報 付 写 真 デ ー タ 72 件 図 15~18 に 検 証 を 行 っ た 図 を 示 す ． 図 15 位 置 ・ 方 向 情 報 付 写 真 デ ー タ 群 図 15 は 位 置 ・ 方 向 情 報 付 写 真 デ ー タ を 地 図 上 に 表 示 し た も の で あ る ． 赤 い 点 が 各 撮 影 位 置 ， 点 か ら 伸 び る 矢 印 が 撮 影 方 向 で あ る ． 図 16 ス ポ ッ ト の 抽 出 図 16 は ス ポ ッ ト を 抽 出 し た 図 で あ る ． A,B,C,D は authority spot ， X,Y は hub spot で あ る ．

図 17 位 置 ・ 方 向 情 報 近 接 グ ラ フ の 作 成 図 17 は 対 象 の デ ー タ に 対 し て ， 位 置 ・ 方 向 情 報 近 接 グ ラ フ を 作 成 し ， ス ポ ッ ト を 組 み 込 ん だ 図 で あ る ． 青 い 矢 印 が グ ラ フ の 有 向 エ ッ ジ ， 橙 色 の 線 が ス ポ ッ ト 内 の エ ッ ジ を 示 す ． 図 18 空 間 要 約 経 路 の 例 図 18 は 各 ス ポ ッ ト を 始 点 ・ 終 点 と し て 指 定 し ， 最 短 経 路 探 索 を 繰 り 返 し て 作 成 し た 空 間 要 約 経 路 の 例 で あ る ． 黄 緑 色 の 線 が 経 路 を 示 す ．

5． 評 価

生 成 し た グ ラ フ か ら 空 間 要 約 経 路 に あ た る 巡 回 路 の 自 動 生 成 を 行 う 手 法 は 今 回 の 提 案 に 含 ま な い ． そ こ で ， 提 案 手 法 の 評 価 を ， 任 意 の 2 ノ ー ド を 始 点 と 終 点 と す る 最 短 経 路 群 を 対 象 と し た 定 量 的 評 価 と ， 任 意 の 2 ス ポ ッ ト を 始 点 と 終 点 と す る 最 短 経 路 群 を 対 象 と し た 定 性 的 評 価 に よ っ て 行 っ た ．

5.1 定 量 的 評 価

任 意 の 2 ノ ー ド を 始 点 と 終 点 と し て 生 成 し た 各 最 短 経 路 を 対 象 と し ， 経 路 の 視 覚 的 連 続 性 に つ い て の 評 価 を 行 っ た ． 評 価 指 標 は 連 続 す る 2 ノ ー ド の 撮 影 方 向 の 差 の 平 均 と し た ． 比 較 対 象 を 以 下 に ま と め る ． 図 14 ス ポ ッ ト の 組 み 込 み

(a) 初 等 的 手 法 (b) 位 置 ・ 方 向 情 報 近 接 グ ラ フ か ら 作 成 し た 経 路 こ こ で ， 初 等 的 手 法 と は ， 入 力 デ ー タ か ら ガ ブ リ エ ル グ ラ フ を 作 成 後 ， エ ッ ジ が 張 ら れ て い る 2 ノ ー ド に つ い て ，2 ノ ー ド 間 の 方 向 の 差 異 が 90 度 以 上 の エ ッ ジ を 切 断 す る 手 法 で 作 成 し た グ ラ フ で あ る ．図 15 の 入 力 デ ー タ に 対 し て 初 等 的 手 法 で 作 成 し た グ ラ フ を 図 19 に 示 す ． 図 19 初 等 的 手 法 に よ る グ ラ フ 評 価 の 結 果 を グ ラ フ に ま と め て 示 す ． x 軸 は 任 意 の 2 ノ ー ド を 始 点 と 終 点 と し て 生 成 し た 各 最 短 経 路 を 経 路 の 長 さ (経 路 に 含 ま れ る ノ ー ド 数 )ご と に 集 約 し た も の で あ る ． ま た ， y 軸 は 連 続 す る 2 ノ ー ド の 撮 影 方 向 の 差 の 平 均 を 示 す ． 単 位 は rad で あ る ． 図 20 連 続 す る 2 ノ ー ド の 方 向 の 差 異 の 平 均 図 20 は(a)初 等 的 手 法 と (b)提 案 手 法 (α = 90)を 比 較 し た グ ラ フ で あ る ．(a)の 初 等 的 手 法 は (b)の 提 案 手 法 か ら 作 成 し た 経 路 に 比 べ て 長 い 経 路 が 存 在 し な い ． ま た ， 提 案 手 法 は 方 向 の 差 が 約 60 度 に 収 ま る ，よ り 長 い 経 路 を 生 成 で き て い る と 言 え る ．

5.2 定 性 的 評 価

提 案 手 法 に よ る グ ラ フ 上 の ス ポ ッ ト 間 を 結 ぶ 各 経 路 を 評 価 対 象 と し て ， 経 路 構 造 に 対 す る 定 性 的 評 価 を 行 っ た ． 図 21 に ， 入 力 デ ー タ か ら 提 案 手 法 で 抽 出 さ れ た ス ポ ッ ト と グ ラ フ を 示 す ． A,B,C,D は authority spot で あ

り ， X,Y は hub spot で あ る ． こ こ か ら ， 地 図 な ど の 情 報 を 用 い て 目 視 で 確 認 し た ， 正 解 と し て 想 定 さ れ る 経 路 構 造 を 図 22 に 示 す ． 図 21 抽 出 さ れ た ス ポ ッ ト と グ ラ フ 図 22 正 解 と し て 想 定 さ れ る 経 路 構 造 提 案 手 法 が 正 解 と し て 想 定 さ れ る 経 路 構 造 を ど の 程 度 再 現 す る か に つ い て の 評 価 を 行 っ た ． 評 価 項 目 を 次 に ま と め る ． (a) ス ポ ッ ト 間 が 到 達 可 能 (b) 正 解 と し て 想 定 さ れ る 経 路 に お い て ，ス ポ ッ ト 間 の 経 路 上 に 他 の ス ポ ッ ト が 存 在 す る 場 合 ，そ の ス ポ ッ ト を 経 由 す る (例 え ば ， B か ら D に 向 か う 経 路 の 場 合 ， C,Y を 経 由 す る ) (c) ス ポ ッ ト 間 の 経 路 が 他 の ス ポ ッ ト を 迂 回 し な い (例 え ば ，A か ら B に 向 か う 経 路 の 場 合 ，X を 経 由 せ ず に 経 路 が つ な が る ) 提 案 手 法 に よ る グ ラ フ か ら ス ポ ッ ト 間 の 経 路 構 造 を 抽 出 し た 図 を 図 23 に 示 す ． 図 23 抽 出 さ れ た ス ポ ッ ト 間 の 経 路 構 造

図 23 は ， 始 点 ス ポ ッ ト か ら 終 点 ス ポ ッ ト へ の 経 路 を 作 成 し た 際 に ，評 価 項 目 を 満 た し て い た 場 合 に 始 点 ス ポ ッ ト か ら 終 点 ス ポ ッ ト へ 向 か う 矢 印 を ひ い て 作 成 し た 図 で あ る ． 正 解 と し て 想 定 さ れ る 経 路 構 造 に 対 す る ，提 案 手 法 に よ る グ ラ フ か ら 抽 出 し た ス ポ ッ ト 間 の 経 路 構 造 の 再 現 率 を 次 の よ う に 定 め る ． 再 現 率 =評 価 項 目 を 満 た す 経 路 数 全 経 路 数 図 23 か ら ，評 価 項 目 を 満 た す 経 路 数 は 22 で あ り ，全 経 路 数 は 30 で あ る ． し た が っ て ， 再 現 率 は 約 73%で あ り ，任 意 の 2 ス ポ ッ ト を 始 点・終 点 と し て 入 力 す る 場 合 ，約 73%の 確 率 で 妥 当 な 経 路 を 生 成 し て い る こ と が わ か っ た ．

6． ま と め

本 稿 で は ， 位 置 ・ 方 向 情 報 付 写 真 デ ー タ を 用 い て ， 対 象 空 間 か ら 特 徴 的 な 領 域 を 抽 出 し ，経 路 を 作 成 し て 総 合 的 に 対 象 空 間 の 概 要 を 提 示 す る こ と を 目 的 と し ， 空 間 要 約 経 路 を 定 義 し て そ の 作 成 手 法 を 提 案 し た ． 視 覚 的 連 続 性 の 制 約 を 満 た す 空 間 要 約 経 路 を 作 成 す る た め ，写 真 デ ー タ を ノ ー ド と し ，ノ ー ド の 位 置 情 報 と 方 向 情 報 を 考 慮 し た 近 接 グ ラ フ で あ る ，位 置 ・方 向 情 報 近 接 グ ラ フ を 提 案 し た ．具 体 的 に は ，グ ラ フ の 作 成 手 法 を ， 2 ノ ー ド の 接 続 条 件 と し て 定 義 し ， 2 ノ ー ド の 間 に 中 継 点 と な る よ う な ノ ー ド が 存 在 す る か を 条 件 判 定 の 基 準 と し た ． 実 デ ー タ に よ り 提 案 手 法 を 評 価 し ，以 下 を 確 認 し た ． ・ 提 案 し た グ ラ フ は ，任 意 の ノ ー ド を 始 点 ・ 終 点 と す る 最 短 路 と し て ，視 覚 的 連 続 性 を 持 つ 経 路 を 生 成 可 能 で あ る ． ・ 提 案 し た グ ラ フ は ，写 真 デ ー タ の 存 在 す る 領 域 に お い て は ，実 世 界 の 経 路 構 造 に 対 し て 高 い 再 現 率 を 持 つ ． 本 稿 で は ，作 成 し た 近 接 グ ラ フ 上 で の 巡 回 路 生 成 手 法 等 は 提 案 し て い な い が ， 以 上 の 結 果 か ら ， 提 案 し た 近 接 グ ラ フ は ， 既 存 の さ ま ざ ま な 巡 回 路 生 成 手 法 を 適 用 可 能 で あ り ， 視 覚 的 連 続 性 の 高 い 空 間 要 約 経 路 を 生 成 す る と 考 え ら れ る ．

参 考 文 献

[1] 藤 田 秀 之 ， 有 川 正 俊 ，“ 空 間 関 係 に 基 づ く 写 真 と 注 釈 の デ ー タ 相 補 発 展 ”， 情 報 処 理 学 会 論 文 誌 ， Vol.35 ， No.5 ， pp.63-76， 2006．

[2] Hideyuki Fujita, Masatoshi Arikawa, “Animation of mapped photo collections for storytelling,” IEICE Transactions on Information and Systems, Vol.E91 -D, No.6, pp.1681-1692, 2008.

[3] Noah Snavely, Rahul Garg, Steven M. Seitz, Richard Szeliski, “Finding Paths through the World's Photos,” ACM Transactions on Graphics (SIGGRAPH 2008),

pp.11-21, 2008.

[4] Xin Lu, Changhu Wang, Jiang-Ming Yang, Yanwei Pang, Lei Zhang, “Photo2Trip Generating Travel Routes from Geo-Tagged Photos for Trip Planning,” In Proceedings of the 18th ACM international conference on Multimedia (MM 2010), pp.143 -152, 2010.

[5] Bart Thomee, “Localization of Points of Interest from Georeferenced and Oriented Photographs,” In Proceedings of the 2nd ACM international workshop on Geotagging and its applications in multimedia (GeoMM 2013), pp.19 -24, 2013.

[6] 白 井 元 浩 ， 廣 田 雅 春 ， 石 川 博 ， 横 山 昌 平 ，“ ジ オ タ グ 付 き 写 真 を 用 い た 関 心 領 域 と 撮 影 ス ポ ッ ト の 発 見 ”， 電 子 情 報 通 信 学 会 論 文 誌 ， Vol.J97-D, No.4, pp.835-844， 2014.

[7] Edward Segel, Jeffrey Heer, “Narrative Visualization Telling Stories with Data,” IEEE Transactions on Visualization and Computer Graphics (InfoVis 20 10), pp.1139-1148, 2010.

[8] Visualizing Data: A Harvard Business Review Insight Center Report, 2013.

[9] 相 楽 翔 太 ，藤 田 秀 之 ，大 森 匡 ，新 谷 隆 彦 ，“ 位 置 ・ 方 向 情 報 付 写 真 群 を 用 い た Data storytelling に 向 け た Storyline 構 成 手 法 ”，第 14 回 情 報 科 学 技 術 フ ォ ー ラ ム (FIT 2015)， D-029，2015.

[10] Fosca Giannotti, Mirco Nanni, Fabio Pinelli, Dino Pedreschi, “Trajectory pattern mining. ” In Proceedings of the 13th ACM SIGKDD international conference on Knowled ge discovery and data mining (KDD 2007), pp.330 -339, 2007.

[11] Jing Wang, Xin Wang, “ A Spatial Clustering Method for Points-with-Directions, ” In Proceedings of the 7th international conference on Rough Sets and Knowledge Technology (RSKT 2012), pp.194 -199, 2012.

[12] M. Shahriar Hossain, Patrick Butler, Arnold P. Boedihardjo, Naren Ramakrishnan, “Storytelling in Entity Networks to Support Intelligen ce Analysts,” In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD 2012), pp.1375 -1383, 2012.

[13] Gunhee Kim, Eric P. Xing, “Reconstructing Storyline Graphs for Image Recommendation from Web Community Photo s,” In Proceedings of the 27th IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2014), pp.3882 -3889, 2014. [14] K. Ruben Gabriel, Robert R. Sokal. “A New

Statistical Approach to Geographic Variation Analysis,” Systematic Zoology, Vol.18, No.3, pp.259-278, 1969.