DEIM Forum 2015 B5-1 図 形 群 の 意 味 と 階 層 構 造 を 用 いた プレゼンテーションスライド 検 索 システムの 提 案 櫻 木 優 輝 1 青 山 敦 2 木 村 文 則 3 前 田 亮 1 立 命 館 大 学 情 報 理 工 学 研 究 科 525-8577 滋 賀 県 草 津 市 野 路 東 1-1-1 2 立 命 館 大 学 MOT 大 学 院 テクノロジー マネジメント 研 究 科 525-8577 滋 賀 県 草 津 市 野 路 東 1-1-1 3 立 命 館 大 学 衣 笠 総 合 研 究 機 構 603-8577 京 都 府 京 都 市 北 区 等 持 院 北 町 56-1 4 立 命 館 大 学 情 報 理 工 学 部 525-8577 滋 賀 県 草 津 市 野 路 東 1-1-1 E-mail: is0018ke@ed.ritsumei.ac.jp,aoyama@mot.ritsumei.ac.jp fkimura@is.ritsumei.ac.jp,amaeda@media.ritsumei.ac.jp 4 あらまし 本 論 文 では,プレゼンテーションスライドに 含 まれる 各 図 形 間 の 配 置 や 関 係 性 などを 分 析 することで 図 形 群 の 意 味 や 階 層 構 造 を 推 定 し,それらを 用 いた 図 形 に 着 目 したプレゼンテーションスライド 検 索 システムを 提 案 すまた, 図 形 群 を 階 層 構 造 で 表 し, 図 形 群 の 階 層 構 造 および 各 要 素 の 類 似 度 を 考 慮 することにより, 図 形 群 同 士 の 類 似 度 を 測 ることが 可 能 にな 本 論 文 で 提 案 した 索 引 作 成 における 図 形 群 の 意 味 推 定 手 法 や 階 層 構 造 推 定 手 法,スライド 検 索, 図 形 群 の 類 似 度 計 算 手 法 の 有 効 性 を 評 価 するために 実 験 を 行 った. 索 引 作 成 における 図 形 群 の 意 味 推 定 では, 適 合 率 0.9408, 再 現 率 0.9392, 図 形 群 の 階 層 構 造 推 定 では, 正 解 率 0.89 の 結 果 が 得 られた.スラ イド 検 索 の 利 用 者 評 価 では, 求 める 図 形 群 が 検 索 結 果 の 10 位 以 内 に 含 まれれば 正 解 としたときの 平 均 正 解 率 が 0.87 という 結 果 が 得 られた.また, 図 形 群 の 類 似 度 計 算 手 法 の 利 用 者 評 価 では, 検 索 結 果 の 順 位 と 評 価 値 に 相 関 係 数 0.86 の 正 の 相 関 が 見 られた. キーワード PowerPoint,OpenXML, 図 形 検 索 1. はじめに PowerPoint などのプレゼンテーションツールは, 大 学 の 講 義 や 研 究 発 表, 企 業 の 会 議 の 場 など 様 々な 場 面 で 利 用 されていプレゼ ンテーション 資 料 は 年 々 増 加 し, 有 用 な 知 識 資 源 となり 得 その ような 知 識 資 源 から, 資 料 の 洗 い 出 しや 再 利 用 をしたいというニー ズもあり,プレゼンテーション 資 料 に 対 するスライド 検 索 への 注 目 が 高 まってい プレゼンテーションスライドには,テキストだけでなく 図 が 多 用 されていそのような 図 は,スライドの 内 容 を 簡 潔 に, 視 覚 的 に わかりやすく 表 現 している 場 合 が 多 く,スライドの 内 容 を 簡 潔 に 理 解 することができしかし,そのような 図 形 の 作 成 には 大 きな 手 間 がかかるため, 過 去 に 作 成 した 図 形 の 再 利 用 や,Web 上 で 公 開 さ れているスライドの 図 形 を 利 用 したいというニーズが 存 在 すし かし, 従 来 の 文 字 列 マッチングによるスライド 検 索 では, 図 形 を 文 字 列 で 表 現 することができず, 図 形 群 自 体 の 検 索 が 困 難 であるとい う 問 題 が 存 在 す 田 中 らは, 図 形 に 着 目 したプレゼンテーションスライド 検 索 シス テムの 研 究 [1][2]を 行 った.この 研 究 の 課 題 であった, 入 力 クエリ 作 成 の 手 間 の 問 題 や, 図 形 の 階 層 性 が 考 慮 されていない 問 題 を 解 決 す るために, 我 々はプレゼンテーションスライドに 含 まれる 図 形 の 階 層 構 造 や 意 味 を 推 定 する 研 究 [3]を 行 なってきた.この 研 究 の 課 題 と して, 推 定 できる 意 味 が 3 つと 少 ないことや, 階 層 構 造 推 定 の 精 度, また, 図 形 に 着 目 したプレゼンテーションスライド 検 索 システムが 実 現 できていないことが 挙 げられ 本 論 文 では,そのような 課 題 を 解 決 し, 図 形 群 の 意 味 や 階 層 構 造 を 利 用 したプレゼンテーションスライド 検 索 システムを 提 案 す 図 形 に 着 目 したスライド 検 索 が 実 現 することで,プレゼンテーショ ンスライドに 含 まれる 図 形 群 の 再 利 用 に 役 立 つ. 本 論 文 では, 図 形 とは, 矩 形 や 楕 円, 矢 印 といった 基 本 図 形 を 指 し, 図 形 群 とは, 提 案 手 法 でグループ 化 された 図 形 の 塊 で あり, 何 らかの 意 味 を 持 つと 定 義 す 2. 関 連 研 究 画 像 処 理 の 分 野 で,プレゼンテーションスライドに 関 する 研 究 が ある[4][5]. Wang らは, 写 真 ではないイメージ 画 像 の 分 類 システムを 提 案 し た[4]. 彼 らは,NPIC システムを 用 いて,イメージ 画 像 をブロック 図,テーブル,グラフ,および 円 グラフへの 分 類 を 行 った.NPIC システムとは,イメージ 画 像 毎 にコンテンツに 応 じた 画 像 の 特 徴 と メタデータのテキストを 抽 出 し, 機 械 学 習 させ, 入 力 イメージ 画 像 を 分 類 するシステムであ Liew らは,スライドを 写 真 とみなし, 画 像 処 理 技 術 を 使 ったスラ イド 検 索 の 方 法 を 提 案 した[5]. 彼 らはスライドの 特 徴 をテキスト, 画 像 イメージ,プレゼンテーションの 機 能 の 3 つの 特 徴 からなると 定 義 した.9 人 の 協 力 者 に,サンプルテキストと 複 数 の 図 を 提 示 し, テキストに 関 連 の 高 い 図 を 最 大 5 位 まで 選 択 してもらうといったア ンケートを 行 った.アンケート 結 果 から 線 形 モデルを 作 成 し,あら
たなデータセットにも 対 応 するスライド 検 索 システムを 構 築 した. この 線 形 モデルを 作 成 するためには, 多 く 学 習 データを 要 す[5] では, 実 験 協 力 者 に 10 個 のサンプルクエリに 対 して 120 個 の 図 の 評 価 を 行 っていたが,より 多 くの 学 習 データを 用 意 するのは 大 変 手 間 であ 本 研 究 では,このような 学 習 データを 必 要 としないことや, 図 の 階 層 構 造 も 考 慮 している 点 で[5]とは 異 なまた, 背 景 と 背 景 や 挿 入 物 の 分 離 の 問 題 についても 言 及 されていMin らの 研 究 で は 背 景 や 挿 入 物 の 識 別 に 画 像 認 識 を 用 いてい 複 雑 な 背 景 を 持 つ スライドでは, 分 離 が 行 われていないため, 検 索 システムの 影 響 を 与 えてい 本 研 究 ではスライドの 構 成 情 報 を 用 いるため, 背 景 や 挿 入 物 の 区 別 や, 挿 入 物 の 種 類 などでも 正 確 に 判 別 することが 可 能 であるため,このような 問 題 は 発 生 しない. Wang らは,プレゼンテーションスライド 間 の 意 味 的 関 係 や 構 造 を 一 般 化 する 手 法 を 提 案 した[6]. 彼 らは,スライドに 含 まれるテキス トのインデントのレベルに 着 目 して,スライド 間 の 意 味 的 関 係 や 構 造 を 抽 出 した.これらの 手 法 は,テキストの 特 徴 を 用 いてスライド の 構 造 を 抽 出 する 手 法 であるが, 私 たちの 手 法 はスライドに 含 まれ る 図 形 の 特 徴 を 用 いて 図 形 の 階 層 構 造 を 推 定 するという 点 で 異 な 有 熊 ら[7]は 企 業 内 で 利 用 するスライド 検 索 手 法 を 提 案 してい 有 熊 らの 手 法 では,プレゼンテーション 資 料 間 でのスライドの 流 用 性 に 基 づき, 高 再 利 用 スライドの 検 索 を 行 ってい 有 熊 らは,ス ライドの 流 用 性 を 推 定 しており,スライド 同 士 の 類 似 度 から 流 用 性 の 高 いスライドの 集 合 を 探 し, 検 索 キーワードと 関 連 のあるスライ ドを 検 出 していしかし, 他 のプレゼンテーション 資 料 に 多 く 流 用 されているスライドであっても,ユーザのプレゼンテーション 資 料 が 同 様 に 流 用 できるとは 限 らない.この 手 法 では, 作 成 日 時 が 古 いプレゼンテーション 資 料 ほどスライドの 流 用 性 が 高 くなその ため, 新 規 のプレゼンテーション 資 料 で 再 利 用 に 適 したスライドが ある 場 合, 過 去 に 再 利 用 された 回 数 が 少 ないため 推 薦 されず, 別 の 古 いスライドが 推 薦 される 可 能 性 があ 本 論 文 の 手 法 では,プレ ゼンテーション 資 料 の 作 成 日 時 の 経 過 といった 時 間 的 要 因 に 依 存 し ないため,このような 問 題 は 発 生 しない. 3. 提 案 手 法 の 概 要 提 案 するシステムは,プレゼンテーションスライドに 含 まれる 図 形 間 の 配 置 関 係 や 関 係 性 を 分 析 することで, 図 形 群 の 意 味 や 階 層 構 造 を 推 定 し, 検 索 のための 索 引 を 作 成 すそして, 推 定 した 図 形 群 の 意 味 や 階 層 構 造 を 用 いたプレゼンテーションスライド 検 索 シス テムを 提 案 す 図 1 にシステム 概 要 図 を 示 す. 図 1 システム 概 要 図 索 引 作 成 では,プレゼンテーション 資 料 から 図 形 の 情 報 を 抽 出 し, 図 形 のグループ 化 を 行 い, 図 形 群 の 意 味 や 階 層 構 造 を 推 定 す る 処 理 の 流 れを, 検 索 時 の 流 れ では,ユーザが 検 索 を 行 い, 入 力 されたクエリを 用 いて 各 スライドの 図 形 群 にスコアをつけ,ランキ ングされた 結 果 が 返 ってくるまでの 処 理 の 流 れを 示 してい また, 提 案 するスライド 検 索 システムでは, 検 索 結 果 の 図 形 群 と 似 た 図 形 群 を 再 検 索 する 機 能 があその 再 検 索 の 流 れを 図 2 に 示 す.この 機 能 を 実 現 するためには, 図 形 群 同 士 の 類 似 度 をはかる 必 要 があ 4 章 でプレゼンテーションスライドに 含 まれる 図 形 群 の 意 味 や 階 層 構 造 を 推 定 する 索 引 作 成,5 章 で 図 形 に 着 目 した スライド 検 索 システム,6 章 で 図 形 群 の 類 似 度 計 算 手 法 について 説 明 す 図 2 図 形 群 の 再 検 索 の 流 れ 4. 索 引 作 成 索 引 作 成 では,プレゼンテーションスライドに 含 まれる 図 形 群 の 意 味 や 階 層 構 造 を 推 定 す 索 引 作 成 の 流 れは,まず PowerPoint ファイルから 図 形 情 報 を 抽 出 す 図 形 情 報 の 抽 出 は,[3]の 図 形 情 報 の 抽 出 方 法 を 用 い 次 に 図 形 間 の 包 含 関 係 を 抽 出 すそして, 形 状 でのグループ 化 を 行 い, グループ 化 された 図 形 群 の 意 味 を 推 定 す 最 後 に 矢 印 図 形 を 用 い たグループ 化 を 行 い,グループ 化 された 図 形 群 の 意 味 を 推 定 す 図 形 群 の 階 層 構 造 は, 図 形 間 の 包 含 関 係 抽 出 形 状 でのグルー プ 化 矢 印 でのグループ 化 の 各 処 理 ごとに 随 時 更 新 し 推 定 す ここで 推 定 した 図 形 群 の 意 味 や 階 層 構 造 の 情 報 を 索 引 として,5 章
で 述 べるスライド 検 索 システムに 用 い 4.1. 図 形 間 の 包 含 関 係 抽 出 先 行 研 究 [3]の 図 形 間 の 包 含 関 係 抽 出 手 法 は,ある 図 形 が 別 の 図 形 を 完 全 に 包 含 している 場 合 にのみ 包 含 関 係 にあると 判 定 していた. しかし, 図 4 に 示 すような 図 形 群 は, 人 間 は 4 つの 矩 形 が 1 つの 楕 円 の 上 にのっていると 認 識 するが, 従 来 手 法 は 少 しのはみ 出 しでも 許 容 しないため 人 間 の 認 識 と 同 様 に 判 定 することができないという 課 題 があった. 図 3 従 来 手 法 で 包 含 関 係 を 正 しく 判 定 できない 図 形 群 の 例 このような 課 題 を 改 善 するために,より 柔 軟 な 包 含 関 係 の 判 定 を 行 う 必 要 があそこで 本 論 文 では, 図 形 間 の 重 なり 具 合 を 分 析 す る 手 法 を 提 案 す 図 形 間 の 重 なり 具 合 を 用 いた 包 含 関 係 抽 出 のア ルゴリズムは 以 下 の(1)~(4)の 手 順 で 行 う. (1) 図 5 で 示 すように,2 つの 図 形 のうち, 面 積 が 小 さい 図 形 を 1 ピクセル 1 点 の 点 集 合 とす 4.2.1. 形 状 でのグループ 化 の 方 法 以 下 のすべての 条 件 を 満 たす 図 形 同 士 をグループ 化 す 同 形 状 同 領 域 ( 同 じ 図 形 に 包 含 されている) 近 距 離 図 形 間 に 矢 印 図 形 がない 本 論 文 では, 近 距 離 であると 判 定 する 図 形 間 の 距 離 の 閾 値 を 50~100 ピクセルの 10 ピクセル 単 位 で 比 較 実 験 を 行 った. 4.2.2. 意 味 推 定 形 状 でのグループ 化 によりグループ 化 された 図 形 群 の 意 味 を 推 定 すグループ 化 された 図 形 群 が 重 なっていれば 重 なり, 縦 また は 横 に 整 列 されていれば リスト, 縦 に 整 列 されていれば 縦 リス ト, 横 に 整 列 されていれば 横 リスト,3 つ 以 上 連 続 する 包 含 関 係 であれば 包 含 関 係,いずれにも 該 当 しない 場 合 は 集 合 関 係 という 意 味 を 推 定 すここで 推 定 する 意 味 には, 表 1 で 示 すよう に 上 位 下 位 関 係 があると 定 義 し,すべての 意 味 の 図 形 群 の 例 を 挙 げ 表 1 形 状 でのグループ 化 での 意 味 推 定 上 位 概 念 下 位 概 念 集 合 関 係 重 なり 包 含 関 係 図 4 図 形 を 点 集 合 とみなす (2) 各 点 が 面 積 の 大 きい 図 形 に 含 まれるかどうかを 調 べ, 図 形 間 の 重 なり 具 合 を 算 出 す (3) 面 積 が 小 さい 図 形 が 任 意 一 定 の 割 合 以 上 重 なっている 場 合 に, 包 含 関 係 にあると 判 定 す (4) 包 含 関 係 にあると 判 定 された 場 合, 図 6 で 示 すように 面 積 の 大 きい 図 形 の 階 層 番 号 に1を 足 した 階 層 を 面 積 の 小 さい 図 形 に 割 り 当 てどの 図 形 にも 包 含 されない 図 形 の 階 層 番 号 は 1 とす 図 5 階 層 番 号 の 割 当 て 本 論 文 では, 予 備 実 験 の 結 果, 小 さい 面 積 の 図 形 の 点 集 合 のうち 7 割 の 点 が 大 きい 面 積 の 図 形 に 含 まれているとき, 包 含 関 係 にある と 判 定 した. 4.2. 形 状 でのグループ 化 形 状 でのグループ 化 では, 図 形 間 の 配 置 関 係 や, 形 状 などの 特 徴 を 用 いて 図 形 のグループ 化 を 行 い, 図 形 群 の 意 味 を 推 定 すその 後, 図 形 間 の 包 含 関 係 抽 出 で 推 定 した 図 形 群 の 階 層 構 造 の 更 新 を 行 う. リスト 縦 リスト or 横 リスト 4.2.3. 図 形 の 階 層 構 造 の 更 新 形 状 でのグループ 化 の 結 果 を 用 いて, 図 形 の 階 層 構 造 を 更 新 す グループ 化 された 図 形 群 には, 図 7 で 示 すように,その 図 形 群 の 構 成 要 素 の 図 形 に 割 り 当 てられていた 階 層 番 号 を 割 り 当 て, 図 形 群 の 構 成 要 素 の 図 形 や 構 成 要 素 の 図 形 より 下 の 階 層 の 図 形 の 階 層 番 号 を ひとつ 増 やし, 図 形 の 階 層 構 造 を 更 新 す 図 6 図 形 群 の 階 層 番 号 の 更 新 4.3. 矢 印 でのグループ 化 矢 印 でのグループ 化 では, 矢 印 図 形 がどの 図 形 群 からどの 図 形 群 を 指 すかを 分 析 し,グループ 化 を 行 う.その 後,グループ 化 の 結 果 を 統 合 し, 図 形 群 の 意 味 を 推 定 すその 後, 形 状 でのグループ 化
で 推 定 した 図 形 群 の 階 層 構 造 の 更 新 を 行 う. 4.3.1. 矢 印 でのグループ 化 の 方 法 まず, 矢 印 図 形 が 指 し 示 す 図 形 の 探 索 を 行 う. 探 索 範 囲 は, 図 8 で 示 すように 矢 印 図 形 の 始 点 から 終 点 方 向 に,それぞれ±90 度 の 角 度 内 にある 図 形 に 対 象 を 絞 ってい 表 2 矢 印 でのグループ 化 での 意 味 推 定 上 位 階 層 下 位 階 層 流 れ 図 2 分 岐 拡 散 循 環 図 7 矢 印 でのグループ 化 での 探 索 範 囲 図 9 で 示 すように, 矢 印 と 図 形 の 距 離 を, 矢 印 の 基 点 と 図 形 の 中 心 点 を 結 んだ 線 分 と 図 形 の 境 界 の 交 点 と, 矢 印 の 基 点 の 2 点 間 の 距 離 とす 集 中 相 互 関 係 図 8 矢 印 図 形 と 図 形 の 距 離 また, 矢 印 と 図 形 群 の 距 離 は, 図 10 で 示 すように, 図 形 群 をその 要 素 の 各 図 形 を 包 含 する 最 小 の 矩 形 と 見 立 てて, 矢 印 と 図 形 群 の 距 離 を 算 出 す 統 合 された 図 形 群 に 含 まれる 全 矢 印 図 形 に 着 目 すそれぞれの 矢 印 が, 上 記 で 挙 げたどの 意 味 をなす 図 形 群 の 要 素 か 判 定 し, 集 計 す 該 当 しない 要 素 は 流 れ 図 として 数 え 表 3 に 含 まれる 図 形 群 は, 拡 散 の 要 素 となる 矢 印 が 最 も 多 いことから,この 図 形 群 の 意 味 は 拡 散 となり,この 図 形 群 の 階 層 構 造 は 図 11 のようにな 表 3 図 形 群 の 意 味 推 定 図 形 群 の 例 矢 印 ID 意 味 の 一 部 1 拡 散 2 拡 散 3 拡 散 4 流 れ 図 9 矢 印 図 形 と 図 形 群 の 距 離 探 索 対 象 となる 全 図 形 との 距 離 を 算 出 し, 距 離 が 最 も 短 い 図 形 を 矢 印 図 形 と 同 一 グループとみなす. 矢 印 図 形 が 指 し 示 す 先 の 図 形 判 定 と 同 様 に, 矢 印 図 形 の 後 方 についても 同 じアルゴリズムで 判 定 す すべての 矢 印 のグループ 化 の 後, 矢 印 のグループ 化 の 結 果 の 統 合 を 行 う. 4.3.2. 意 味 推 定 矢 印 でのグループ 化 の 結 果 により 統 合 された 図 形 群 の 意 味 を 推 定 す2 つの 矢 印 の 後 方 図 形 が 一 致 する 場 合 2 分 岐,3 つ 以 上 の 矢 印 の 後 方 図 形 が 一 致 する 場 合 拡 散,2 つ 以 上 の 矢 印 の 前 方 図 形 が 一 致 する 場 合 集 中, 循 環 している 場 合 は 循 環, 矢 印 が 両 端 にある 場 合 は 相 互 関 係 という 意 味 を 推 定 すここで 推 定 する 意 味 は, 表 2 で 示 すように 上 位 下 位 関 係 があると 定 義 し, 図 形 群 の 意 味 とその 例 を 挙 げ 図 10 図 形 群 の 階 層 構 造 4.3.3. 図 形 の 階 層 構 造 の 更 新 矢 印 でのグループ 化 の 結 果 を 用 いて 図 形 の 階 層 構 造 の 更 新 を 行 う. 矢 印 の 前 後 の 図 形 の 階 層 が 一 致 する 場 合 は,グループ 化 された 図 形 群 に 構 成 要 素 の 階 層 番 号 を 割 当 て, 構 成 要 素 の 図 形 の 階 層 番 号 をひ とつ 増 やす.また, 矢 印 の 前 後 の 図 形 の 階 層 が 一 致 しない 場 合 は, 図 12 で 示 すように,グループ 化 された 図 形 群 に 構 成 要 素 の 階 層 番 号 のうち 最 下 層 の 階 層 番 号 を 割 り 当 て, 構 成 要 素 の 図 形 の 階 層 は 図 形 群 の 階 層 番 号 に 1 足 した 階 層 番 号 を 割 り 当 て
と 流 れ 図 は 異 なる 概 念 階 層 にあるので 50 点 の 減 点 を 行 う. 図 13 図 形 群 の 意 味 の 階 層 概 念 図 11 矢 印 の 前 後 で 階 層 が 一 致 しない 場 合 5. スライド 検 索 システム 4 章 で 推 定 した 図 形 群 の 意 味 や 階 層 構 造 を 用 いて, 図 形 に 着 目 し たスライド 検 索 システムを 提 案 す5.1 節 で 入 力 クエリ,5.2 節 で 出 力,5.3 節 では 入 力 されたクエリに 図 形 群 がどれだけマッチしてい るかを 計 算 するスコアリング 手 法 を 説 明 す 5.1. 入 力 クエリ 入 力 クエリは, 図 形 群 の 意 味, 図 形 群 の 要 素 の 形 状, 図 形 群 の 要 素 の 数, 入 れ 子 図 形 群 の 意 味, スライドに 含 まれるテキス ト の 5 つであ 例 えば, 図 13 で 示 す 図 形 群 を 探 したい 場 合 の 入 力 クエリは, 図 形 群 の 意 味 : 流 れ 図, 図 形 群 の 要 素 の 形 状 : 四 角 形, 図 形 群 の 要 素 の 数 :3, 入 れ 子 図 形 群 の 意 味 :リスト とな 5.3.2. 図 形 群 の 要 素 の 形 状 によるスコアリング 手 法 図 形 の 形 状 を, 三 角 形, 四 角 形, ひし 形, 多 角 形, 楕 円, 円 柱, 星 型 に 汎 化 す 図 形 の 形 状 は 図 15 で 示 す 概 念 階 層 で あると 定 義 す 図 14 図 形 の 形 状 の 概 念 階 層 定 義 した 概 念 階 層 を 使 用 して, 入 力 された 図 形 群 の 要 素 の 形 状 と 検 索 対 象 のスライドに 含 まれる 図 形 群 の 要 素 の 形 状 の 距 離 を 各 形 状 ノード 間 の 距 離 と 定 義 し, 距 離 1 ごとに 5 点 の 減 点 を 行 う. 図 12 探 したい 図 形 群 の 例 5.2. 出 力 出 力 は, 入 力 クエリにマッチする 図 形 群 を 含 むスライドのパスで あり,これをクリックするとスライドのプレビューを 見 ることがで きるインタフェースになってい 5.3. スコアリング 手 法 入 力 クエリとマッチする 順 にランキング 表 示 するためのスコアリ ング 手 法 を 提 案 すスライドに 含 まれる 全 図 形 群 に 対 しスコアを つけ, 最 も 高 いスコアをスライドのスコアとす 各 図 形 群 は, 初 期 値 が 100 点 であり, 内 訳 は 図 形 群 の 意 味 が 50 点, 図 形 群 の 要 素 の 形 状 が 30 点, 図 形 群 の 要 素 の 数 が 20 点 とし, 入 力 クエリと 検 索 対 象 の 図 形 群 に 差 異 がある 場 合,それぞれの 要 素 で 減 点 を 行 う. 5.3.1. 図 形 群 の 意 味 によるスコアリング 手 法 図 形 群 の 意 味 は 図 14 で 示 す 概 念 階 層 であると 定 義 す 定 義 した 概 念 階 層 を 使 用 して, 入 力 された 図 形 群 の 意 味 と 検 索 対 象 のスライ ドに 含 まれる 図 形 群 の 意 味 の 距 離 を 各 意 味 ノード 間 の 距 離 と 定 義 し, 距 離 1 ごとに 15 点 の 減 点 を 行 う. 例 えば, 入 力 された 図 形 群 の 意 味 が 重 なり で 検 索 対 象 の 図 形 群 の 意 味 が リスト の 場 合, 距 離 2 なので 30 点 の 減 点 を 行 う.ま た, 入 力 された 図 形 群 の 意 味 と 検 索 対 象 の 図 形 群 の 意 味 が 異 なる 概 念 階 層 に 存 在 する 場 合 は,50 点 の 減 点 を 行 う. 例 えば, リスト 5.3.3. 図 形 群 の 要 素 の 個 数 によるスコアリング 手 法 入 力 クエリでは, 図 形 群 の 要 素 の 個 数 の 範 囲 指 定 をすることがで き 指 定 した 数 と 検 索 対 象 の 図 形 群 の 要 素 の 数 の 差 が 1 つごとに 5 点 の 減 点 を 行 う. 5.3.4. 入 れ 子 図 形 群 の 意 味 によるスコアリング 手 法 入 れ 子 図 形 群 の 意 味 とは, 指 定 した 図 形 群 の 中 にさらに 存 在 する 図 形 群 の 意 味 のことであ 図 16 に 図 形 群 の 入 れ 子 の 意 味 の 入 力 例 を 示 す. 図 15 入 れ 子 図 形 群 の 意 味 の 入 力 例 検 索 対 象 の 図 形 群 の 階 層 構 造 から, 指 定 した 図 形 群 の 意 味 より 下 の 階 層 に 含 まれるすべての 図 形 群 の 意 味 に 着 目 す5.3.1 節 の 図 形 群 の 意 味 によるスコアリング 手 法 を 用 いてそれぞれスコアを 計 算 し, 最 も 高 いスコアを 採 用 す 階 層 を 考 慮 し, 図 17 で 示 すように 算 出 したスコアを 階 層 差 に 1 を 足 した 数 値 で 割 った 値 を 入 れ 子 図 形 群 の 意 味 のスコアとし,5.3.1~5.3.3 節 の 手 法 で 算 出 したスコアに 加 点 す
図 16 入 れ 子 図 形 群 の 意 味 のスコアリング 手 法 6. 図 形 群 の 類 似 度 の 計 算 手 法 検 索 結 果 の 図 形 群 と 似 た 図 形 を 探 したい 場 合, 図 形 群 同 士 の 類 似 度 を 測 る 必 要 があ4 章 で 図 形 群 の 階 層 構 造 を 推 定 する 手 法 を 提 案 した.ここで 図 形 群 同 士 の 階 層 構 造 の 類 似 度 を 測 る 手 法 を 提 案 す 図 13 の 図 形 群 の 階 層 構 造 を 図 18 に 示 す. 赤 い 四 角 形 は 図 形 群 を 示 し, 青 い 四 角 形 は 図 形 群 に 含 まれる 個 々の 図 形 を 表 す. 図 17 図 形 群 の 階 層 構 造 6.1. 木 構 造 の 類 似 度 に 関 する 研 究 本 論 文 ではプレゼンテーションスライドに 含 まれる 図 形 群 を 木 構 造 で 表 現 しており, 図 形 群 同 士 の 類 似 度 として 木 構 造 同 士 の 類 似 度 を 用 いてい 木 構 造 の 類 似 度 に 関 する 研 究 として, 小 柳 らは,XML データ 同 士 の 類 似 度 を XML の 木 構 造 とテキストノードのラベルの 情 報 テキストの 類 似 度 の 二 面 から 類 似 度 を 求 める 手 法 を 提 案 してい る[9]. 本 論 文 では, 図 形 群 の 意 味 の 類 似 度 や 図 形 の 形 状 の 類 似 度, 階 層 構 造 の 深 さを 考 慮 して, 木 構 造 の 類 似 度 を 求 める 手 法 を 提 案 す 6.2. 木 構 造 の 類 似 度 木 構 造 の 類 似 度 は, 一 般 的 に 木 編 集 距 離 [11]を 用 いることが 多 い. 木 編 集 距 離 とは 木 構 造 に 対 する 距 離 の 指 標 の 一 種 で,ある 一 方 の 木 に 対 しノードの 変 更, 追 加, 削 除 などの 操 作 を 行 い,もう 一 方 の 木 と 同 じ 構 造 に 変 形 させるのに 必 要 な 操 作 のコストをその 二 つの 木 の 距 離 とする 手 法 であ 各 操 作 におけるコストにはあらかじめ 適 当 な 値 を 設 定 しておく 必 要 があ 例 えば 各 操 作 のコストをそれぞれ1とすると, 図 19で 示 す 木 の 木 編 集 距 離 は, 以 下 の(1)~(3)のコスト 3 とな (1) A を B に 変 更 (2) を 削 除 (3) を 追 加 6.2.1. ノード 操 作 のコスト 図 18 木 編 集 距 離 の 例 提 案 手 法 では, 木 構 造 のノードのタイプとして 図 形 ノードと 図 形 群 ノードの 2 種 類 が 存 在 す 同 じノードのタイプのみノード 変 更 可 能 とす 図 形 群 から 図 形 群 に 変 更 する 場 合 は, 図 形 群 の 意 味 に 着 目 し, 図 13 の 図 形 群 の 意 味 の 概 念 階 層 から 距 離 を 計 算 し, 距 離 1 ごとにコストを 15 とす 比 較 する 図 形 群 の 意 味 が 異 なる 概 念 階 層 にある 場 合,コストは 50 とす 図 形 から 図 形 への 変 更 も 同 様 に, 図 形 の 形 状 に 着 目 し, 図 14 の 図 形 の 形 状 の 概 念 階 層 を 用 いて 距 離 1 ごとにコスト 5 とす 図 形 群 ノードの 追 加 削 除 のコストは 50 とし, 図 形 ノードの 追 加 削 除 のコストは 5 とす 6.2.2. 階 層 の 深 さを 考 慮 したコスト 計 算 図 形 や 図 形 群 は 階 層 が 上 位 であればあるほど, 人 間 の 記 憶 にも 残 りやすく,スライドで 大 きな 役 割 を 果 たしていこのことから, 上 位 ノードの 操 作 のコストは 下 位 ノードの 操 作 のコストより 重 みを 大 きくする 必 要 があそこで, 階 層 を 考 慮 し,ノード 操 作 のコス トにノードの 階 層 番 号 で 割 った 値 をコストとす 例 えば, 図 形 群 の 第 2 階 層 のノードの 操 作 をするとき,ノード 操 作 のコストを 階 層 番 号 である 2 で 割 った 値 を 操 作 のコストとす 7. 実 験 提 案 手 法 の 索 引 作 成,スライド 検 索 システム, 図 形 群 の 類 似 度 の 有 効 性 を 検 証 するために 実 験 を 行 った. 7.1. 索 引 作 成 の 実 験 索 引 作 成 の 実 験 では, 包 含 関 係 抽 出, 形 状 でのグループ 化, 矢 印 でのグループ 化, 階 層 構 造 推 定 のそれぞれの 有 効 性 を 検 証 す 正 解 データは,[4]で 行 った 図 形 のアンケート 結 果 から 作 成 した. 使 用 したスライドは 30 枚 で 419 個 の 図 形 が 含 まれ 7.1.1. 索 引 作 成 の 実 験 結 果 包 含 関 係 抽 出 は 平 均 正 解 率 で, 形 状 でのグループ 化 と 矢 印 でのグ ループ 化 での 図 形 群 の 意 味 推 定 を 適 合 率 再 現 率 で 評 価 を 行 う. 表 4 に 包 含 関 係 抽 出 の 平 均 正 解 率, 表 5 に 形 状 でのグループ 化 での 図 形 群 の 意 味 推 定 の 実 験 結 果, 表 6 に 矢 印 でのグループ 化 での 図 形 群 の 意 味 推 定 の 実 験 結 果 を 示 す. 重 なり 具 合 (%) 平 均 正 解 率 表 4 包 含 関 係 抽 出 の 実 験 結 果 50 60 70 80 90 100 0.996 1.000 0.999 0.998 0.995 0.985
表 5 形 状 でのグループ 化 の 実 験 結 果 意 味 集 合 関 係 重 なり リスト 縦 リスト 横 リスト 適 合 率 0.89 1.00 0.83 0.81 0.90 再 現 率 0.86 1.00 0.83 0.89 0.75 表 6 矢 印 でのグループ 化 での 実 験 結 果 意 味 流 れ 循 環 分 岐 拡 散 集 中 相 互 関 係 適 合 率 0.95 1.00 0.91 1.00 1.00 1.00 再 現 率 0.94 1.00 1.00 1.00 1.00 1.00 7.1.2. 索 引 作 成 の 実 験 結 果 の 考 察 索 引 作 成 では, 包 含 関 係 抽 出 形 状 でのグループ 化 矢 印 でのグ ループ 化,すべてにおいてよい 結 果 を 得 ることができた. 矢 印 での グループ 化 において, 形 状 でのグループ 化 の 結 果 を 用 いるので, 表 7 に 含 まれる 各 図 形 群 は,3 つの 矩 形 から 1 つの 矩 形 に 流 れると 判 定 され しかし, 矢 印 は 必 ずしも 図 形 群 を 指 すとは 限 らない. 矢 印 図 形 の 幅 や 指 向 性, 矢 印 図 形 の 前 後 の 図 形 の 類 似 度 などを 分 析 する ことでよりよい 結 果 が 得 られると 考 えられ 表 7 構 造 が 似 た 図 形 群 の 比 較 7.2. スライド 検 索 システムの 評 価 実 験 被 験 者 に, 提 案 したスライド 検 索 システムを 用 いて 図 形 群 を 検 索 してもらい, 求 める 図 形 群 が 含 まれるスライドが 上 位 に 存 在 するか どうかで 評 価 を 行 う. 実 際 にこのスライド 検 索 システムを 使 うユー ザは, 過 去 にこのような 図 形 群 を 作 ったな あったな, 前 に Web でこのような 図 形 群 を 見 た と 図 形 群 を 思 い 浮 かべながら,スライ ド 検 索 システムを 使 用 すつまり,ユーザは 過 去 に 1 度 以 上 その 図 形 群 を 見 たことがあり,その 図 形 群 を 含 むスライドが 存 在 し,ま た 過 去 の 記 憶 を 思 い 起 こすため,うろ 覚 えである 可 能 性 が 高 い.こ のような 状 況 と 近 似 する 状 況 を 作 り, 評 価 実 験 を 行 う. 7.2.1. 実 験 データ 本 実 験 では, 所 属 研 究 室 の 学 生 10 名, 及 び 企 業 で 作 成 されたスラ イドの 中 から 181 件 のスライドを 検 索 対 象 として 用 いた. 利 用 者 評 価 実 験 には, 本 研 究 室 と 他 研 究 室 の 学 生 と 教 員 の 合 計 10 名 に 協 力 し てもらい,1 名 あたり 3 つの 図 形 群 を 検 索 してもらい 検 索 システム の 評 価 を 行 った. 7.2.2. スライド 検 索 システムの 評 価 実 験 の 手 順 被 験 者 に 検 索 対 象 のフォルダに 含 まれているスライドの 一 部 のス ライド 40 枚 を 提 示 す 被 験 者 がスライドを 見 てから 6 時 間 以 上 経 過 した 後 に 評 価 実 験 を 行 う.これは, 被 験 者 の 記 憶 がうろ 覚 えにな る 時 間 であると 考 えたからであユーザには,この 時 間 に, 記 憶 が 曖 昧 になるように 他 の 作 業 を 行 ってもらう.ユーザは 探 し 出 した い 図 形 群 を 思 い 浮 かべ, 提 案 するスライド 検 索 システムを 用 いて 検 索 を 行 い, 評 価 す 検 索 結 果 の 上 位 10 位 のスライドのうち,ユー ザが 探 し 出 したい 図 形 群 が 含 まれるスライドを 正 解 スライド, 代 用 できる 図 形 群 や, 少 し 改 修 すれば 利 用 できる 図 形 群 が 含 まれるス ライドを 準 正 解 スライド として 評 価 をつけ 7.2.3. スライド 検 索 システムの 評 価 実 験 の 結 果 システムの 評 価 では, 平 均 正 解 率 を 用 いて,システムの 有 効 性 を 検 証 す 平 均 正 解 率 は, 求 める 図 形 群 が 検 索 結 果 の 一 定 の 順 位 以 上 に 含 まれれば 正 解, 含 まれなければ 不 正 解 としてシステムの 評 価 を 行 う. 正 解 不 正 解 の 閾 値 は,3 位 5 位 10 位 の 3 パターンを 用 意 し, 正 解 スライド のみを 扱 う 場 合 と 準 正 解 スライド を 正 解 スライド に 含 める 場 合 と 2 パターンで 評 価 を 行 う. 表 8 スライド 検 索 システムの 実 験 結 果 正 解 スライド + 準 正 解 スライド 3 位 以 上 0.77 0.83 5 位 以 上 0.80 0.87 10 位 以 上 0.87 0.93 7.2.4. スライド 検 索 システムの 評 価 実 験 の 考 察 表 8 より, 平 均 正 解 率 はよい 結 果 が 得 られたと 考 えられこの スライド 検 索 システムでは, 入 力 図 形 群 に 対 する 出 力 結 果 として, 10 枚 のスライドのキャプションが 表 示 されるため, 求 める 図 形 群 が 含 まれるかどうかの 確 認 が 視 覚 的 に 容 易 にできこのことから, 表 11 の 10 位 以 内 に 求 める 図 形 群 が 含 まれれば 正 解 とした 平 均 正 解 率 の 値 からも, 検 索 システムが 有 効 であると 考 えられ 提 案 手 法 では, 図 形 群 の 意 味 は 図 13 の 概 念 階 層 があるとし, 入 力 された 図 形 群 の 意 味 と 検 索 対 象 のスライドに 含 まれる 図 形 群 の 意 味 の 距 離 を 計 算 し, 距 離 1 ごとに 一 律 15 点 の 減 点 を 行 っていた.しか し, 利 用 者 は 流 れ と 分 岐 より, 分 岐 と 発 散 がより 似 ていると 感 じるため, 図 形 群 の 概 念 階 層 に 適 切 な 距 離 やコストを 設 定 する 必 要 があると 考 えられ また, 検 索 結 果 に 似 た 図 形 群 が 多 くの 割 合 を 占 めることがあり, 似 ている 図 形 群 よりもさまざまなバリエーションが 欲 しいといった 利 用 者 の 声 もあった. 例 えば 図 52 の 3 つのスライドは, 図 形 群 の 意 味, 図 形 群 の 要 素 の 形 状, 図 形 群 の 要 素 の 個 数 がすべて 一 致 するため, 検 索 結 果 で 同 時 に 出 現 すしかし, 利 用 者 はいずれ か 1 つのみ 検 索 結 果 に 出 現 すればよいと 考 えることから, 似 ている 図 形 群 のクラスタリングをする 必 要 があると 考 えられ 図 19 類 似 した 図 形 群 が 検 索 結 果 として 返 される 例 7.3. 図 形 群 の 類 似 度 計 算 手 法 の 評 価 実 験 提 案 手 法 の 有 効 性 を 評 価 するために, 利 用 者 評 価 のアンケートを 行 なった.アンケートは, 入 力 図 形 群 とそれに 対 する 類 似 図 形 群 の 検 索 結 果 から 上 位 10 件 の 各 スライドに 含 まれる 図 形 群 を 比 較 し,5 段 階 評 価 で 似 ているかどうかを 評 価 するといったものであ5 段
階 評 価 は,5 は 似 ている,4 は おおよそ 似 ている,3 は 少 し 似 ている,2 は あまり 似 ていない,1 は 似 てない として 評 価 す 7.3.1. 実 験 データ 7.2.1 節 で 説 明 したデータを 実 験 データとして 用 い 利 用 者 評 価 のアンケートは, 入 力 図 形 群 を 含 むスライドと 類 似 図 形 群 の 検 索 結 果 から 上 位 10 件 のスライドを1つの 組 み 合 わせとする6 件 分 のデー タを 用 い 利 用 者 評 価 のアンケートは, 大 学 生 ( 理 系 文 系 ), 社 会 人 ( 技 術 職 )の 合 計 18 人 に 評 価 を 依 頼 した.18 人 分 の 評 価 デー タを 集 計 し, 各 順 位 の 平 均 評 価 値 で 有 効 性 を 調 査 す 7.3.2. 図 形 群 の 類 似 度 計 算 手 法 の 評 価 実 験 の 結 果 18 人 分 の 入 力 図 形 群 1~6 の 評 価 データから,1 位 ~10 位 の 各 順 位 の 平 均 評 価 値 を 算 出 した. 全 入 力 図 形 群 の 平 均 評 価 値 を 図 19 に 示 す. 全 入 力 図 形 群 の 平 均 評 価 値 5 4 3 2 1 0 1 位 2 位 3 位 4 位 5 位 6 位 7 位 8 位 9 位 10 位 平 均 評 価 値 図 20 全 入 力 図 形 群 の 平 均 評 価 値 7.3.3. 図 形 群 の 類 似 度 計 算 手 法 の 評 価 実 験 の 考 察 図 20 から, 検 索 結 果 の 順 位 と 評 価 値 に 相 関 係 数 0.8580 の 正 の 相 関 が 見 られたことから, 提 案 手 法 が 有 効 であると 考 えられ 図 20 の 10 位 の 評 価 値 が 少 し 上 がっている 理 由 として, 図 21 で 示 すように, 利 用 者 が 索 引 作 成 で 推 定 していない 木 構 造 意 味 をユ ーザが 認 識 したからと, 矢 印 でのグループ 化 で 推 定 する 階 層 構 造 が 理 由 として 考 えられ が 得 られると 考 えられ 8. まとめ 本 論 文 では,プレゼンテーションスライドに 含 まれる 図 形 群 の 意 味 や 階 層 構 造 を 推 定 し,それらを 用 いた 図 形 に 着 目 したスライド 検 索 システムを 提 案 した. 索 引 作 成 では, 実 験 結 果 から 提 案 手 法 が 有 効 であることが 分 かった. しかし,スライド 検 索 システムではいくつか 課 題 が 残 ユーザ が 図 形 群 をシステムの 入 力 クエリに 変 換 することに 慣 れが 必 要 でる ことがわかった.このことより,より 直 観 的 でインタラクティブな インタフェースを 考 案 する 必 要 があまた, 検 索 対 象 となる PowerPoint ファイルが 多 くなると,ランキング 結 果 に 同 じような 図 形 群 が 上 位 に 現 れ,クエリに 少 しでも 誤 りがあると 求 める 図 形 群 が なかなか 現 れないという 問 題 も 存 在 すこの 解 決 策 として, 似 て いる 図 形 群 のクラスタリングを 行 う 方 法 が 考 えられ 参 考 文 献 [1] 田 中 清 太 朗, 手 塚 太 郎, 青 山 敦, 木 村 文 則, 前 田 亮. 図 形 の 形 状 と 配 置 に 着 目 したスライド 検 索 手 法 の 提 案. 第 4 回 デ ータ 工 学 と 情 報 マネジメントに 関 するフォーラム(DEIM2012) 論 文 集, Mar. 2012. [2] Seitaro Tanaka, Taro Tezuka, Atsushi Aoyama, Fuminori Kimura, and Akira Maeda. Slide Retrieval Technique Using Features of Figures. In Proceedings of the International MultiConference of Engineers and Computer Scientists 2013 (IMECS2013). pp. 424-429, Hong Kong, China, Mar. 2013. [3] 櫻 木 優 輝, 青 山 敦, 木 村 文 則, 前 田 亮. 階 層 的 意 味 を 考 慮 したプレゼンテーションスライド 図 形 の 構 造 化 手 法 の 提 案. 第 5 回 データ 工 学 と 情 報 マネジメントに 関 するフォーラム (DEIM2014) 論 文 集, Mar. 2014. [4] Wang, F. and Kan, M.-Y. 2006. NPIC: Hierarchical Synthetic Image Classification using Image Search and Generic Features. In Proceedings of the 5th International Conference on Image and Video Retrieval (CIVR2006) (Tempe, Arizona, USA), 473-482 [5] Liew, G. M. and Kan, M.-Y. 2008. Slide image retrieval: a preliminary study, In Proceedings of the 8th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL2008) (Pittsburgh, Pennsylvania, June 16-20, 2008), 359-362. [6] Wang, Y. and Sumiya, K. 2012. A Generation Method of Presentation Slides based on Expression Styles using Slide Structure. In Proceedings of the 4th International Workshop with Mentors on Databases, Web and Information Management for Young Researchers (idb Workshop 2012), (Nagoya, Japan, August 1, 2012). [7] 有 熊 威, 白 石 展 久. スライドの 流 用 性 に 着 目 した 企 業 内 スラ イド 検 索 手 法 の 提 案, 情 報 処 理 学 会 第 71 回 全 国 大 会 論 文 集, pp.489-490, 2009. [8] 小 柳 涼 介, 天 笠 俊 之, 北 川 博 之.テキストおよび 類 似 度 に 基 づいた XML データに 対 する 効 率 的 な 類 似 検 索, 第 5 回 デー タ 工 学 と 情 報 マネジメントに 関 するフォーラム(DEIM2014) 論 文 集, Mar. 2014. [9] Philip Bille. A survey on tree edit distance and related problems. Theor. Comput. Sci., Vol. 337, No. 1-3, pp. 217 239, June 2005. 今 後, 図 形 群 により 適 切 な 意 味 を 推 定 することや, 階 層 構 造 をど こまで 使 用 するかといった 情 報 の 選 択, 図 18 で 示 した 図 形 群 の 意 味 の 概 念 階 層 の 枝 の 距 離 やコスト 設 定 を 見 直 すことで,よりよい 結 果