クロスモーダルな距離尺度学習を用いたスケッチによる3D モデルの検索 利用統計を見る

クロスモーダルな距離尺度学習を用いた

スケッチによる 3D モデルの検索

山梨大学大学院

医学工学総合教育部

博士課程学位論文

2015 年 9 月

古屋 貴彦

目 次

序 論 . . . 1 1 . 1 . 研 究 の 背 景 . . . 1 1 . 2 . 研 究 の 目 的 と 概 要 . . . 3 1 . 3 . 本 論 文 の 構 成 . . . 5 関 連 研 究 . . . 7 2 . 1 . 3 D モ デ ル デ ー タ ベ ー ス へ の 問 い 合 わ せ 手 段 . . . 7 2 . 2 . ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 評 価 用 デ ー タ ベ ー ス . . . 8 2 . 3 . 特 徴 比 較 . . . 1 0 2 . 3 . 1 . ス ケ ッ チ と 3 D モ デ ル の 比 較 ( ス ケ ッ チ に よ る 3 D モ デ ル 検 索 ) . . . 1 1 2 . 3 . 2 . 3 D モ デ ル 相 互 の 比 較 ( 3 D モ デ ル の 例 示 に よ る 3 D モ デ ル 検 索 ) . . . 1 9 2 . 3 . 3 . ス ケ ッ チ 相 互 の 比 較 . . . 2 9 2 . 3 . 4 . 局 所 特 徴 の 統 合 . . . 3 2 2 . 4 . 距 離 尺 度 学 習 . . . 3 6 2 . 4 . 1 . ユ ニ モ ー ダ ル 距 離 尺 度 学 習 . . . 3 6 2 . 4 . 2 . ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 . . . 4 7 ク ロ ス モ ー ダ ル 多 様 体 ラ ン キ ン グ を 用 い た ス ケ ッ チ に よ る 3 D モ デ ル の 検 索 . . . 5 1 3 . 1 . 研 究 の 概 要 . . . 5 1 3 . 2 . 提 案 手 法 . . . 5 2 3 . 2 . 1 . ク ロ ス モ ー ダ ル 多 様 体 ラ ン キ ン グ . . . 5 2 3 . 2 . 2 . イ ン タ ー モ ー ダ ル 特 徴 間 類 似 度 の 計 算 . . . 5 7 3 . 2 . 3 . イ ン ト ラ モ ー ダ ル 特 徴 間 類 似 度 の 計 算 . . . 6 4 3 . 3 . 実 験 と 結 果 . . . 6 5 3 . 3 . 1 . 実 験 条 件 . . . 6 5 3 . 3 . 2 . 実 験 結 果 . . . 6 8 3 . 4 . ま と め . . . 7 7 ク ロ ス モ ー ダ ル 多 様 体 ハ ッ シ ン グ を 用 い た ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の ス ケ ー ラ ブ ル 化 . . . 7 9 4 . 1 . 研 究 の 概 要 . . . 7 9 4 . 2 . 提 案 手 法 . . . 8 0 4 . 2 . 1 . ク ロ ス モ ー ダ ル 多 様 体 ハ ッ シ ン グ . . . 8 1 4 . 2 . 2 . イ ン タ ー モ ー ダ ル 特 徴 間 類 以 度 の 計 算 . . . 8 5 4 . 2 . 3 . イ ン ト ラ モ ー ダ ル 特 徴 間 類 以 度 の 計 算 . . . 8 9 4 . 3 . 実 験 と 結 果 . . . 9 1 4 . 3 . 1 . 実 験 条 件 . . . 9 1 4 . 3 . 2 . 実 験 結 果 . . . 9 3 4 . 4 . ま と め . . . 1 0 1 特 徴 間 類 似 度 の 改 善 . . . 1 0 4

5 . 1 . 研 究 の 概 要 . . . 1 0 4 5 . 2 . 提 案 手 法 . . . 1 0 6 5 . 2 . 1 . D i f f u s i o n - o n - M a n i f o l d ( D M ) 統 合 . . . 1 0 6 5 . 2 . 2 . ス ケ ッ チ 相 互 の 比 較 . . . 1 1 0 5 . 2 . 3 . 3 D モ デ ル 相 互 の 比 較 . . . 1 1 0 5 . 3 . 実 験 と 結 果 . . . 1 1 3 5 . 3 . 1 . 実 験 条 件 . . . 1 1 3 5 . 3 . 2 . 実 験 結 果 . . . 1 1 5 5 . 4 . ま と め . . . 1 2 3 結 論 と 今 後 の 展 望 . . . 1 2 6 6 . 1 . 結 論 . . . 1 2 6 6 . 2 . 今 後 の 展 望 . . . 1 3 0 謝 辞 . . . 1 3 3 参 考 文 献 . . . 1 3 4

図 目 次

図 1 . 1 3 D モ デ ル 検 索 シ ス テ ム に 与 え る 検 索 要 求 の 例 ． . . . 1 図 1 . 2 ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 流 れ ． . . . 3 図 2 . 1 ベ ン チ マ ー ク に 含 ま れ る ス ケ ッ チ と 3 D モ デ ル の 例 ． . . . 1 0 図 2 . 2 G A L I F 特 徴 抽 出 [ 1 8 ] ． . . . 1 2 図 2 . 3 P y r a m i d - o f - P a r t s 法 [ 5 1 ] に よ る 線 画 画 像 の 領 域 分 割 の 例 ． . . . 1 3 図 2 . 4 3 視 点 ス ケ ッ チ 画 像 の 例 [ 6 0 ] ． . . . 1 5 図 2 . 5 Wa n g ら が 得 た 3 D モ デ ル の 代 表 視 点 の 例 [ 8 0 ] ． . . . 1 9 図 2 . 6 A A D 特 徴 の 抽 出 [ 8 5 ] ． . . . 2 0 図 2 . 7 3 D モ デ ル を 球 面 調 和 関 数 で 近 似 し た 例 [ 9 6 ] ． . . . 2 1 図 2 . 8 H e a t K e r n e l S i g n a t u r e の 例 [ 1 0 5 ] ． . . . 2 3 図 2 . 9 s k e l e t a l グ ラ フ [ 1 0 9 ] と R e e b グ ラ フ [ 11 0 ] の 例 ． . . . 2 3 図 2 . 1 0 L F D 法 に よ る 3 D モ デ ル の 比 較 [ 1 0 4 ] ． . . . 2 5 図 2 . 11 B F - D S I F T 法 [ 6 4 ] ． . . . 2 6 図 2 . 1 2 M FA M R 法 に よ る 複 数 特 徴 の 融 合 [ 1 4 2 ] ． . . . 2 9 図 2 . 1 3 手 描 き ス ケ ッ チ の カ テ ゴ リ 内 の 多 様 性 と カ テ ゴ リ 間 の 曖 昧 性 の 例 ． . . . 2 9 図 2 . 1 4 E i t z ら の ス ケ ッ チ コ ー パ ス [ 3 8 ] に 含 ま れ る 手 描 き ス ケ ッ チ の 例 ． . . . 3 0 図 2 . 1 5 局 所 特 徴 の 統 合 法 ． . . . 3 3 図 2 . 1 6 M a n i f o l d R a n k i n g の 例 [ 1 3 9 ] ． . . . 3 9 図 2 . 1 7 L a p l a c i a n E i g e n m a p s に よ る 次 元 削 減 の 例 [ 1 0 2 ] ． . . . 4 2 図 2 . 1 8 I t e r a t i v e Q u a n t i z a t i o n 法 に よ る 特 徴 空 間 の 回 転 の 例 [ 1 8 9 ] ． . . . 4 5 図 3 . 1 C M M R 法 の 概 要 図 ． . . . 5 3 図 3 . 2 イ ン タ ー モ ー ダ ル 特 徴 間 距 離 ， イ ン ト ラ モ ー ダ ル 特 徴 間 距 離 の 計 算 ． . . 5 7 図 3 . 3 向 き が 不 揃 い な ス ケ ッ チ 画 像 と 特 徴 稜 線 画 像 の 例 ． . . . 5 8 図 3 . 4 背 景 色 が 異 な る 特 徴 稜 線 レ ン ダ リ ン グ の 例 ． . . . 5 9 図 3 . 5 ス ケ ッ チ 画 像 と 特 徴 稜 線 画 像 の 回 転 正 規 化 の 例 ． . . . 6 3 図 3 . 6 レ ン ダ リ ン グ 視 点 数 と 検 索 精 度 の 関 係 ( S - P S B ) ． . . . 7 0 図 3 . 7 S - P S B お よ び S - S H 1 3 に お け る 検 索 精 度 の 比 較 ． . . . 7 2 図 3 . 8 半 教 師 あ り C M M R 法 の パ ラ メ ー タ と 検 索 精 度 の 関 係 ． . . . 7 2 図 3 . 9 S - P S B と S - S H 1 3 に お け る 各 手 法 の R e c a l l - P r e c i s i o n 曲 線 ． . . . 7 4 図 3 . 1 0 S - P S B に お け る 検 索 結 果 の 例 ． . . . 7 6 図 4 . 1 C M M H 法 の 概 要 図 ． . . . 8 2 図 4 . 2 C M M グ ラ フ 生 成 に 用 い る 特 徴 ． . . . 8 8 図 4 . 3 S - S H 1 4 X に 含 ま れ る “ 成 り す ま し ” の 3 D モ デ ル の 例 ． . . . 9 2 図 4 . 4 特 徴 統 合 手 法 の 比 較 ( S - P S B t e s t s e t ) ． . . . 9 4 図 4 . 5 S V- M G A L I F 特 徴 を 圧 縮 し た 際 の 検 索 精 度 ( S - P S B t e s t s e t ) ． . . . 9 5 図 4 . 6 特 徴 圧 縮 の 次 元 数 ま た は ビ ッ ト 数 と ， 検 索 精 度 の 関 係 ． . . . 9 6 図 4 . 7 S - P S B と S - S H 1 4 に お け る 各 手 法 の R e c a l l - P r e c i s i o n 曲 線 ． . . . 1 0 0 図 4 . 8 S - P S B に お け る 検 索 結 果 例 ． . . . 1 0 1

図 5 . 1 D i f f u s i o n - o n - M a n i f o l d ( D M ) 統 合 の 流 れ ． . . . 1 0 7 図 5 . 2 P O D 特 徴 抽 出 の 流 れ ． . . . 11 3 図 5 . 3 特 徴 統 合 法 の 検 索 精 度 の 比 較 ． . . . 11 6 図 5 . 4 D M 統 合 の パ ラ メ ー タ ． . . . 11 8 図 5 . 5 距 離 の 公 理 ( 三 角 不 等 式 ) を 満 た さ な い 例 ． . . . 1 2 3

表 目 次

表 3 . 1 C M M R ( F + L ) , U M R , C C A , K C C A の パ ラ メ ー タ ． . . . 6 8 表 3 . 2 特 徴 稜 線 レ ン ダ リ ン グ の 視 点 数 と カ メ ラ の 位 置 ． . . . 6 9 表 3 . 3 既 存 手 法 と の 検 索 精 度 の 比 較 ． . . . 7 3 表 3 . 4 検 索 1 回 あ た り の 計 算 時 間 [ s ] ． . . . 7 5 表 3 . 5 S - P S B と S - S H 1 3 に お け る WU M と WC M Mの 行 列 サ イ ズ ( Nv= 2 0 ) ． . . . 7 5 表 4 . 1 C M M H 法 の パ ラ メ ー タ ( 特 徴 セ ッ ト は F S 2 ) ． . . . 9 2 表 4 . 2 検 索 1 回 当 た り の 計 算 時 間 [ s ] ． . . . 9 8 表 4 . 3 C M M H 法 を 用 い た 検 索 の メ モ リ 消 費 量 [ M B y t e ] ． . . . 9 8 表 4 . 4 C M M グ ラ フ の 固 有 値 分 解 手 法 の 比 較 ． . . . 9 8 表 4 . 5 既 存 手 法 と の 検 索 精 度 の 比 較 ． . . . 9 9 表 5 . 1 D M 統 合 の パ ラ メ ー タ ． . . . 11 4 表 5 . 2 F S 3 の 教 師 な し C M M R と 教 師 な し C M M H の パ ラ メ ー タ ． . . . 11 4 表 5 . 3 特 徴 量 と 特 徴 統 合 の 組 み 合 わ せ の 比 較 ( M A P [ % ] ) ． . . . 11 6 表 5 . 4 多 様 体 グ ラ フ の ノ ー ド の 重 み 付 け の 効 果 ( M A P [ % ] ) ． . . . 11 7 表 5 . 5 特 徴 統 合 の 計 算 時 間 の 比 較 [ s ] ． . . . 11 9 表 5 . 6 ス ケ ッ チ 相 互 の 検 索 精 度 [ % ] ． . . . 11 9 表 5 . 7 3 D モ デ ル 相 互 の 検 索 精 度 [ % ] ． . . . 1 2 0 表 5 . 8 ス ケ ッ チ 検 索 の 精 度 ( S - P S B t e s t s e t ) [ % ] . . . 1 2 1 表 5 . 9 C M M 距 離 行 列 に お け る 距 離 の 公 理 ( 三 角 不 等 式 ) の 違 反 回 数 ． . . 1 2 3

1

序論

1.1. 研究の背景

3 次 元 ( 3 D ) 形 状 モ デ ル は ， 医 療 ， 工 業 製 品 設 計 ， 建 築 設 計 ， 映 画 や ゲ ー ム 等 の 娯 楽 作 品 等 ， 幅 広 い 分 野 で 利 用 さ れ て い る ． 近 年 で は ， 安 価 な 3 D レ ン ジ ス キ ャ ナ や 3 D プ リ ン タ の 普 及 に よ り ， 我 々 の 日 常 生 活 に お い て も ， 3 D モ デ ル を 扱 う 機 会 が 増 加 し つ つ あ る ． ま た ， 車 両 の 自 動 運 転 や ロ ボ ッ ト ナ ビ ゲ ー シ ョ ン と い っ た ， 実 世 界 の 情 報 に 基 づ い て 機 械 を 走 行 さ せ る 技 術 の 多 く は ， 深 さ セ ン サ や ス テ レ オ カ メ ラ 等 で 獲 得 し た 実 世 界 の 3 D 形 状 を 解 析 す る こ と で ， 機 械 の 走 行 を 制 御 す る ． こ れ ら 多 く の 分 野 で 日 々 ， 3 D 形 状 モ デ ル が 大 量 に 生 成 さ れ 続 け て お り ， 3 D 形 状 モ デ ル の 数 は 急 激 に 増 加 し て い る ． そ し て ， こ れ ら 3 D 形 状 モ デ ル は ， そ れ ら の 再 利 用 ， 流 通 ， 解 析 の た め に ， 社 内 や イ ン タ ー ネ ッ ト 上 の デ ー タ ベ ー ス に 蓄 積 さ れ て 続 け て い る ． デ ー タ ベ ー ス に 蓄 積 さ れ た 多 数 の 3 D モ デ ル を 効 率 良 く 管 理 す る た め に ， 3 D モ デ ル の 形 状 類 似 検 索 の 技 術 が 必 要 で あ る ． 3 D モ デ ル の 検 索 で は ， ユ ー ザ が 検 索 要 求 を 検 索 シ ス テ ム に 与 え る と ， シ ス テ ム は 検 索 要 求 に 類 似 し た 3 D モ デ ル 群 を デ ー タ ベ ー ス の 中 か ら 探 し 出 し ， 検 索 結 果 と し て ユ ー ザ に 返 す ． 実 用 的 な 3 D モ デ ル 検 索 シ ス テ ム は ， ( 1 ) 高 精 度 で あ る こ と ， ( 2 ) 高 速 で あ る こ と ， ( 3 ) 問 い 合 わ せ が ユ ー ザ に と っ て 手 軽 で あ る こ と ， の 3 つ の 要 件 を 全 て 満 た す 必 要 が あ る ． 検 索 精 度 と 検 索 速 度 は ， 3 D モ デ ル を 比 較 ・ 検 索 す る ア ル ゴ リ ズ ム に 大 き く 依 存 す る ． 精 度 と 速 度 を 改 善 さ せ る ア プ ロ ー チ と し て ， 検 索 要 求 と 検 索 対 象 3 D モ デ ル の 比 較 に 用 い る 特 徴 量 の 改 善 や ， 特 徴 間 の 距 離 計 算 方 法 の 改 善 が 挙 げ ら れ る ． 一 方 で ， ユ ー ザ に と っ て の 検 索 の 手 軽 さ は ， 検 索 要 求 と し て 何 を 用 い る か に 依 存 す る ． 図 1 . 1 に 示 す よ う に ， 検 索 要 求 の 例 に は ， キ ー ワ ー ド ， 3 D モ デ ル の 例 示 ， 手 描 き ス ケ ッ チ 等 が あ る ． 図 1.1 3D モデル検索システムに与える検索要求の例．

…

3 D モ デ ル デ ー タ ベ ー ス a i r p l a n e 検 索 キ ー ワ ー ド 手 書 き ス ケ ッ チ レ ン ジ ス キ ャ ン モ デ ル ( 単 一 視 点 の 深 さ 画 像 ) 再 構 成 3 D モ デ ル 自 然 画 像 3 D モ デ ル の 例 示

キ ー ワ ー ド は ， ウ ェ ブ ペ ー ジ や 写 真 等 ， 多 く の マ ル チ メ デ ィ ア デ ー タ の 検 索 シ ス テ ム で 採 用 さ れ て い る 検 索 要 求 で あ る ． キ ー ワ ー ド は ユ ー ザ に と っ て 手 軽 な 問 い 合 わ せ 手 段 で あ る が ， 検 索 を 行 う た め に は 予 め デ ー タ ベ ー ス 中 の 3 D モ デ ル 群 に キ ー ワ ー ド タ グ を 付 与 す る 必 要 が あ る ． し か し な が ら ， 多 数 の 3 D モ デ ル に 対 し て 手 作 業 で キ ー ワ ー ド タ グ を 付 与 す る の は 大 変 手 間 が か か る ． 機 械 学 習 を 用 い て 半 自 動 的 に 3 D モ デ ル に タ グ 付 与 を 行 う こ と は 可 能 で あ る [ 1 ] , [ 2 ] が ， こ の 場 合 に も か な り の 数 の 有 ラ ベ ル 3 D モ デ ル が 必 要 と な る ． ま た ， ユ ー ザ が 欲 す る 3 D 形 状 に よ っ て は ， そ の 形 状 や そ の 形 状 に 関 連 す る 意 味 カ テ ゴ リ を 表 現 す る 単 語 が 存 在 し な い た め に キ ー ワ ー ド に よ る 検 索 が 困 難 な 場 合 が あ る ． さ ら に は ， 検 索 シ ス テ ム が ユ ー ザ の 使 用 言 語 に 対 応 し て い な い 可 能 性 も あ る ． 3 D モ デ ル の 例 示 は ， 最 も 代 表 的 な 検 索 要 求 の 提 示 方 法 で あ る ． こ れ ま で に 数 多 く の 手 法 が 提 案 さ れ て お り [ 3 ] – [ 5 ] ， 用 途 や デ ー タ セ ッ ト に よ っ て は ， 実 用 的 な 検 索 精 度 と 速 度 を 示 す ． 3 D モ デ ル の 例 示 に よ る 検 索 は ， 検 索 要 求 と 検 索 対 象 が 同 種 の デ ー タ で あ る た め ， キ ー ワ ー ド や 手 描 き ス ケ ッ チ 等 の 検 索 要 求 と 比 べ て ， 検 索 要 求 と 検 索 対 象 と の 比 較 が 行 い や す い ． し か し ， 検 索 要 求 と し て 与 え る 3 D モ デ ル を ユ ー ザ が 所 持 し て い る と は 限 ら な い た め ， 3 D モ デ ル の 例 示 に よ る 問 い 合 わ せ は ， 多 く の 利 用 シ ー ン に お い て 実 用 的 で は な い ． 本 研 究 で は ， 手 描 き の 2 次 元 ( 2 D ) ス ケ ッ チ を 検 索 要 求 と し て 3 D モ デ ル を 検 索 す る 手 法 を 検 討 す る ． 手 描 き ス ケ ッ チ に よ る 3 D モ デ ル 検 索 ( 図 1 . 2 ) [ 6 ] – [ 9 ] は ， タ ブ レ ッ ト 等 の 手 描 き 入 力 に 対 応 し た 端 末 の 普 及 に よ り ， 近 年 ， 有 用 性 が 高 ま り つ つ あ る ． 手 描 き ス ケ ッ チ に よ る 問 い 合 わ せ は ， 誰 に と っ て も 使 い や す く ， 欲 す る 形 状 を 直 感 的 に 指 定 で き る 利 点 が あ る ． ま た ， ユ ー ザ の 使 用 す る 言 語 に 影 響 を 受 け な い こ と も ， 手 描 き ス ケ ッ チ に よ る 問 い 合 わ せ の 利 点 で あ る ． し か し ， 現 状 ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 精 度 と 速 度 は い ず れ も 不 十 分 で あ る ． 検 索 精 度 不 足 の 原 因 の 1 つ は ， 手 描 き ス ケ ッ チ と 3 D モ デ ル の デ ー タ の 形 態 ( モ ー ド , m o d e ) が 異 な る こ と で あ る ． そ の た め ， こ れ ら 2 つ の デ ー タ の モ ー ド を 跨 ぐ ク ロ ス モ ー ダ ル ( c r o s s - m o d a l ) な 比 較 は 困 難 と さ れ ， そ の 比 較 の 精 度 は 低 い ． 多 く の ス ケ ッ チ と 3 D モ デ ル の 比 較 ア ル ゴ リ ズ ム で は ， 3 D モ デ ル を 多 視 点 の 線 画 画 像 に 変 換 し ， こ れ ら 線 画 画 像 か ら 抽 出 さ れ た 画 像 特 徴 を ， 線 画 で あ る 手 描 き ス ケ ッ チ の 画 像 特 徴 と 比 較 す る ． し か し ， 手 描 き ス ケ ッ チ と 3 D モ デ ル の 線 画 画 像 が 視 覚 的 に 異 な る た め に ， し ば し ば 特 徴 比 較 に 失 敗 す る ． 手 描 き ス ケ ッ チ は ， 描 画 様 式 の 多 様 性 や ， 形 状 の 抽 象 化 ， 意 味 の 影 響 ， ス ケ ッ チ 線 の 揺 ら ぎ を 含 む た め で あ る ． 国 際 的 な 3 D モ デ ル 検 索 コ ン テ ス ト で あ る S H a p e R E t r i e v a l C o n t e s t ( S H R E C ) で は ， 2 0 1 2 年 度 ， 2 0 1 3 年 度 ， 2 0 1 4 年 度 に ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 部 門 が 開 か れ た [ 6 ] – [ 8 ] ． し か し ， い ず れ の 年 度 に お い て も ， 検 索 精 度 1 位 の 手 法 の 精 度 は 実 用 に 届 か な い 水 準 で あ る ． 例 え ば ， 2 0 1 4 年 度 の S H R E C ス ケ ッ チ 検 索 部 門 に お い て 最 も 高 精 度 で あ っ た 手 法 の 検 索 精 度 M e a n Av e r a g e P r e c i s i o n ( M A P ) は ， 1 3 . 1 % で あ る ． 実 用 的 な 検 索 シ ス テ ム で は ， M A P = 6 0 % 程 度 ， 即 ち ， 検 索 結 果 の 少 な く と も 半 分 以 上 が 正 解 で あ る こ と が 望 ま し い と 言 わ れ る ． 検 索 の 速 度 不 足 は ， ス ケ ッ チ と 3 D モ デ ル の 比 較 の 計 算 コ ス ト が 大 き い こ と に 起 因 す る ． 3 D モ デ ル は 多 視 点 の 線 画 画 像 に 変 換 さ れ る た め ， ス ケ ッ チ の 特 徴 を ， こ れ ら 多 視

点 の 画 像 特 徴 群 の 各 特 徴 と 全 対 で 比 較 す る 必 要 が あ る ． こ の た め ， 既 存 手 法 の 多 く は ， 多 数 ( 例 え ば 1 0 万 個 ) の 検 索 対 象 3 D モ デ ル を 含 む 大 規 模 な デ ー タ セ ッ ト に お い て ， 実 用 的 な 時 間 内 ( 例 え ば 3 秒 以 内 ) で 検 索 を 行 う こ と が 困 難 で あ る ． 図 1.2 スケッチによる 3D モデル検索の流れ．

1.2. 研究の目的と概要

本 研 究 の 目 的 は ， 実 用 的 な 3 D モ デ ル 検 索 を 実 現 す る こ と で あ る ． 1 . 1 節 で も 述 べ た 通 り ， 実 用 的 な 検 索 シ ス テ ム は ， ユ ー ザ に と っ て 使 い や す く ， 高 精 度 で ， か つ ， 高 速 で あ る 必 要 が あ る ． 本 研 究 で は ， ユ ー ザ に と っ て の 使 い や す さ を 念 頭 に ， 手 描 き ス ケ ッ チ を 検 索 要 求 と し た 3 D モ デ ル 検 索 を 扱 う ． ま た ， 高 精 度 か つ 高 速 な 検 索 を 実 現 す る た め に ， ク ロ ス モ ー ダ ル な 距 離 尺 度 学 習 ( c r o s s m o d a l d i s t a n c e m e t r i c l e a r n i n g ) を 提 案 し ， こ れ を 用 い て ， モ ー ド が 異 な る 2 D ス ケ ッ チ と 3 D モ デ ル を 効 果 的 に 比 較 す る ． ク ロ ス モ ー ダ ル な 距 離 尺 度 学 習 で は ， ス ケ ッ チ と 3 D モ デ ル の 間 で モ ー ド を 超 え た 関 係 性 を 学 習 し ， こ れ ら 異 種 デ ー タ の 比 較 に 適 し た 距 離 尺 度 を 獲 得 す る こ と を 目 標 と す る ． 本 研 究 で は ， 多 く の デ ー タ 解 析 に 効 果 的 で あ る と さ れ る 多 様 体 学 習 ( m a n i f o l d l e a r n i n g ) を ク ロ ス モ ー ダ ル 拡 張 し た ， ク ロ ス モ ー ダ ル 多 様 体 学 習 ( c r o s s - m o d a l m a n i f o l d l e a r n i n g ) を 行 う ． ス ケ ッ チ と 3 D モ デ ル の 間 に ク ロ ス モ ー ダ ル 多 様 体 ( C r o s s -M o d a l -M a n i f o l d , C -M -M ) を 生 成 し ， C -M -M を 解 析 す る こ と で ， ス ケ ッ チ と 3 D モ デ ル 間 の 比 較 に 適 し た 距 離 尺 度 を 学 習 す る ． C M M の 生 成 で は ， ま ず ， ス ケ ッ チ 相 互 の 特 徴 比 較 を 行 う こ と で ， ス ケ ッ チ 集 合 の イ ン ト ラ モ ー ダ ル ( i n t r a - m o d a l ) 特 徴 多 様 体 を 生 成 す る ． 同 様 に ， 3 D モ デ ル 相 互 の 特 徴 比 較 を 行 う こ と で ， 3 D モ デ ル 集 合 の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 を 生 成 す る ． 次 い で ， こ れ ら 2 つ の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 を ， ス ケ ッ チ と 3 D モ デ ル の 特 徴 間 類 似 度 お よ び 意 味 ラ ベ ル 間 類 似 度 を 用 い て 接 続 す る こ と で ， 単 一 3 D モ デ ル の 多 視 点 線 画 画 像 3 D モ デ ル デ ー タ ベ ー ス 特 徴 比 較 ユ ー ザ に よ る ス ケ ッ チ 入 力 検 索 結 果 の 提 示 … 手 描 き ス ケ ッ チ … 検 索 結 果 ユ ー ザ …

の ク ロ ス モ ー ダ ル 多 様 体 ( C M M ) に 統 合 す る ． C M M を 用 い る こ と の 利 点 は ， C M M か ら 学 習 さ れ る 距 離 尺 度 に ， ス ケ ッ チ と 3 D モ デ ル 間 の 関 係 性 だ け で な く ， 複 数 の ス ケ ッ チ 相 互 の 関 係 性 と ， 複 数 の 3 D モ デ ル 相 互 の 関 係 性 を 反 映 で き る こ と で あ る ． こ れ に よ り ， ス ケ ッ チ と 3 D モ デ ル 間 の 関 係 性 だ け を 用 い る 既 存 手 法 よ り も ， 本 提 案 手 法 の 方 が ， 高 い 検 索 精 度 を 得 ら れ る と 期 待 で き る ． ま た ， 多 様 体 グ ラ フ に 対 し て 比 較 的 容 易 に 意 味 ラ ベ ル を 反 映 す る こ と で き る た め ， C M M を 用 い た ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 ア ル ゴ リ ズ ム は ， 意 味 ラ ベ ル の 有 無 や そ の 量 ( デ ー タ ベ ー ス 中 の 有 ラ ベ ル デ ー タ の 割 合 ) に 応 じ て ， 教 師 な し ， 教 師 あ り ， 半 教 師 あ り ， の い ず れ の 場 合 に お い て も 用 い る こ と が で き る ． 本 研 究 で は ， C M M を 利 用 し た ク ロ ス モ ー ダ ル 距 離 尺 度 の 学 習 法 と し て ， 2 つ の ア ル ゴ リ ズ ム を 提 案 す る ． 1 つ 目 の ア ル ゴ リ ズ ム は ， C M M グ ラ フ 上 の 類 似 度 拡 散 を 利 用 し て ス ケ ッ チ と 3 D モ デ ル を 比 較 す る C r o s s - M o d a l M a n i f o l d R a n k i n g ( C M M R ) 法 [ 1 0 ] , [ 11 ] で あ る ． C M M R 法 は ， 検 索 要 求 ス ケ ッ チ に 対 応 す る ノ ー ド か ら 類 似 度 を C M M グ ラ フ 上 に 拡 散 さ せ る ． 類 似 度 は ， C M M グ ラ フ 上 の 辺 を 介 し て 他 の ス ケ ッ チ 群 と 3 D モ デ ル 群 へ 伝 播 す る ． 類 似 度 拡 散 の 結 果 に 基 づ い て ， デ ー タ ベ ー ス 中 の 3 D モ デ ル 群 を 順 位 付 け し ， 検 索 結 果 を 生 成 す る ． 類 似 度 は C M M グ ラ フ 上 の あ ら ゆ る 辺 を 介 し て 拡 散 す る た め ， C M M グ ラ フ 上 の シ ョ ー ト カ ッ ト や 穴 と い っ た 位 相 的 ノ イ ズ に 対 す る 頑 強 性 が 得 ら れ る ． 評 価 実 験 で は ， C M M R 法 を 利 用 す る こ と で ， 既 存 の 検 索 手 法 の 精 度 が 有 意 に 改 善 す る こ と を 示 す ． し か し ， C M M R 法 は ， 類 似 度 拡 散 の 計 算 量 が 大 き い た め に ， 大 規 模 な ( 例 え ば 1 0 万 個 の 検 索 対 象 3 D モ デ ル を 含 む ) デ ー タ ベ ー ス に ス ケ ー ル し な い 問 題 が あ る ． 2 つ 目 の ア ル ゴ リ ズ ム は ， C M M R 法 の ス ケ ー ラ ビ リ テ ィ 改 善 を 狙 っ た ， C r o s s - M o d a l M a n i f o l d H a s h i n g ( C M M H ) 法 [ 1 2 ] で あ る ． C M M H 法 は ， C M M グ ラ フ を ノ ー ド 間 の 類 似 性 が で き る だ け 保 存 さ れ る よ う な 低 次 元 H a m m i n g 空 間 に 潰 し 込 む こ と で ， ス ケ ッ チ と 3 D モ デ ル の 特 徴 を コ ン パ ク ト な バ イ ナ リ コ ー ド と し て 表 現 す る ． バ イ ナ リ コ ー ド 間 の 距 離 は 大 変 高 速 に 計 算 可 能 で あ る た め ， C M M H 法 は 大 規 模 な デ ー タ ベ ー ス を 効 率 良 く 検 索 で き る ． ま た ， 検 索 精 度 の 改 善 の た め に ， C M M グ ラ フ 生 成 に 用 い る 特 徴 を 改 善 す る ． C M M R 法 で は ， ス ケ ッ チ お よ び 3 D モ デ ル か ら 密 に 抽 出 さ れ た 局 所 特 徴 を B a g o f -F e a t u r e s ( B -F ) 法 [ 1 3 ] , [ 1 4 ] を 用 い て 統 合 す る ． C M M H 法 で は ， 近 年 提 案 さ れ た 高 精 度 な 特 徴 統 合 手 法 で あ る S u p e r Ve c t o r ( S V ) c o d i n g 法 [ 1 5 ] と L o c a l i t y - c o n s t r a i n e d L i n e a r ( L L ) c o d i n g 法 [ 1 6 ] を 利 用 す る ． こ れ ら の 統 合 法 を 用 い て 生 成 さ れ た 統 合 特 徴 を 比 較 す る こ と で ， よ り 高 精 度 な C M M グ ラ フ を 生 成 す る ． 評 価 実 験 で は ， 1 0 万 個 の 検 索 対 象 3 D モ デ ル か ら 成 る デ ー タ ベ ー ス を 作 成 し ， C M M H 法 が こ の 大 規 模 デ ー タ ベ ー ス に ス ケ ー ル す る こ と を 示 す ． ま た ， 高 精 度 な 特 徴 を 用 い る こ と で 検 索 精 度 が 改 善 す る こ と を 示 す ． C M M R 法 お よ び C M M H 法 の 検 索 精 度 は ， C M M グ ラ フ の 生 成 に 用 い る 特 徴 に 依 存 す る ． 本 論 文 で は さ ら な る 検 索 精 度 の 向 上 を ね ら っ て ， C M M グ ラ フ 生 成 に 用 い る 特 徴 間 類 似 度 の 改 善 を 行 う ． S V 法 お よ び L L 法 よ り も 高 精 度 な 特 徴 統 合 手 法 と し て ， D i f f u s i o n - o n - M a n i f o l d ( D M ) 統 合 法 [ 1 7 ] を 提 案 す る ． D M 統 合 法 は ， 局 所 特 徴 の 統 合 に 多 様 体 学 習 の 考 え を 導 入 し ， 従 来 の 特 徴 統 合 法 よ り も 情 報 損 失 の 少 な い 統

合 ベ ク ト ル を 生 成 す る ． 評 価 実 験 で は ， D M 統 合 法 を 用 い る こ と で ， 特 徴 間 の 比 較 が 改 善 す る こ と を 示 す ． し か し ， D M 統 合 特 徴 か ら 生 成 し た C M M グ ラ フ に 対 し て C M M H 法 を 適 用 す る と 精 度 が 低 下 す る 実 験 結 果 を 得 た た め ， そ の 理 由 を 考 察 す る ． 考 察 に お い て ， C M M H 法 の 高 精 度 化 の 条 件 と し て ， C M M グ ラ フ 生 成 に 用 い る 特 徴 を 改 善 さ せ る だ け で は な く ， C M M グ ラ フ が 距 離 の 公 理 を 満 た す こ と が 必 要 で あ ろ う と い う 見 解 を 得 た ． 本 研 究 の 貢 献 は ， 以 下 の 通 り で あ る ．  ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 精 度 の 大 幅 な 改 善 ． ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 を 用 い る こ と で ， 困 難 な 問 題 と さ れ る ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 精 度 が 大 き く 改 善 し た ． ス ケ ッ チ と 3 D モ デ ル の 比 較 の 困 難 さ か ら ， 現 状 ， ど の 既 存 手 法 も 検 索 精 度 が 不 十 分 で あ る ． 例 え ば ， 代 表 的 な 既 存 手 法 で あ る B F G A L I F 法 [ 1 8 ] の 検 索 精 度 は ， S P S B ベ ン チ マ ー ク [ 1 8 ] で M A P = 1 7 . 4 % ， S -S H 1 4 ベ ン チ マ ー ク [ 8 ] で M A P = 4 . 4 % で あ る ． 本 研 究 の 評 価 実 験 を 通 し て ， 特 徴 と 意 味 ラ ベ ル の 双 方 を 学 習 し た 半 教 師 あ り C M M H 法 の 検 索 精 度 は ， S - P S B で M A P = 4 2 . 7 % ， S - S H 1 4 で M A P = 2 7 . 9 % ま で 改 善 し た ． C M M H 法 の 検 索 精 度 も 実 用 に は 届 か な い 水 準 で あ る も の の ， 本 研 究 は ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 を 実 用 に 一 歩 近 づ け る こ と に 成 功 し た ．  ク ロ ス モ ー ダ ル 多 様 体 を 用 い た 距 離 尺 度 学 習 ア ル ゴ リ ズ ム C M M R 法 お よ び C M M H 法 の 提 案 ． C M M R 法 と C M M H 法 は ， ス ケ ッ チ と 3 D モ デ ル ， ス ケ ッ チ 相 互 ， 3 D モ デ ル 相 互 ， の 複 数 の 関 係 性 を 学 習 し て ， こ れ ら デ ー タ の 比 較 に 適 応 し た 距 離 尺 度 を 学 習 す る ． C M M H 法 は 1 0 万 オ ー ダ ー の 大 規 模 デ ー タ ベ ー ス を 実 用 的 な 時 間 で 検 索 可 能 で あ る ． こ れ ら の ア ル ゴ リ ズ ム は ， 意 味 ラ ベ ル の 有 無 や そ の 量 に 応 じ て ， 教 師 な し ， 教 師 あ り ， 半 教 師 あ り の い ず れ の 場 合 に お い て も 用 い る こ と が で き る ． ま た ， 本 提 案 手 法 群 は ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 に 限 ら ず ， 他 種 の ク ロ ス モ ー ダ ル 検 索 に も 適 用 可 能 で あ る ．  局 所 特 徴 の 統 合 ア ル ゴ リ ズ ム D i f f u s i o n - o n - M a n i f o l d ( D M ) 法 の 提 案 ． D M 統 合 法 は ， 局 所 特 徴 の 統 合 処 理 に 多 様 体 学 習 の 考 え を 導 入 し ， 従 来 の 特 徴 統 合 法 よ り も 情 報 損 失 の 少 な い 統 合 ベ ク ト ル を 生 成 す る ． D M 法 で 得 た 統 合 特 徴 を 比 較 す る こ と で ， 3 D モ デ ル 相 互 の 検 索 精 度 が 有 意 に 改 善 す る ． 局 所 特 徴 の 統 合 は ， 検 索 や 識 別 等 の 多 く の タ ス ク で 頻 繁 に 用 い ら れ る ア プ ロ ー チ で あ る た め ， D M 法 に よ っ て 多 く の タ ス ク の 精 度 が 改 善 す る 可 能 性 が あ る ．

1.3. 本論文の構成

本 論 文 の 構 成 に つ い て 述 べ る ． 1 章 で は ， 本 研 究 の 背 景 ， 目 的 ， 概 要 を 述 べ た ． 2 章 で は ， 関 連 研 究 に つ い て 述 べ る ． 2 . 1 節 で は 3 D モ デ ル デ ー タ ベ ー ス へ の 問 い 合

わ せ 手 段 ， 2 . 2 節 で は ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 評 価 用 デ ー タ ベ ー ス に つ い て 述 べ る ． 2 . 3 節 で は 特 徴 の 比 較 手 法 に つ い て 述 べ る ． 2 . 3 . 1 節 で は ， ス ケ ッ チ と 3 D モ デ ル の 特 徴 比 較 法 ， 即 ち ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 既 存 手 法 を 説 明 す る ． ま た ， 本 研 究 で 提 案 す る ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 は ， ス ケ ッ チ 相 互 の 類 似 性 と 3 D モ デ ル 相 互 の 類 似 性 も 考 慮 す る こ と か ら ， 2 . 3 . 2 節 で ス ケ ッ チ 相 互 の 特 徴 比 較 ， 2 . 3 . 3 節 で 3 D モ デ ル 相 互 の 特 徴 比 較 に つ い て 述 べ る ． 2 . 3 . 4 節 で は 局 所 特 徴 統 合 の 既 存 手 法 を 説 明 す る ． 2 . 4 節 で は ， 距 離 尺 度 学 習 に つ い て 述 べ る ． ま ず 2 . 4 . 1 節 で ユ ニ モ ー ダ ル ( u n i m o d a l ) ， 即 ち 単 一 の 特 徴 空 間 に 対 す る 距 離 尺 度 学 習 法 に つ い て 述 べ ， 次 い で ， 2 . 4 . 2 節 で ク ロ ス モ ー ダ ル の 距 離 尺 度 学 習 法 を 説 明 す る ． 3 章 で は ， 1 つ 目 の ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 ア ル ゴ リ ズ ム で あ る C M M R 法 を 説 明 す る ． C M M R 法 は ， C M M グ ラ フ 上 の 類 似 度 拡 散 に よ っ て ， ス ケ ッ チ の モ ー ド と 3 D モ デ ル の モ ー ド を 跨 ぐ ， ク ロ ス モ ー ダ ル な 距 離 尺 度 を 学 習 す る ． 4 章 で は ， 2 つ 目 の ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 ア ル ゴ リ ズ ム で あ る C M M H 法 を 説 明 す る ． C M M H 法 は C M M R 法 の 精 度 と 効 率 の 双 方 の 改 善 を 狙 う ． C M M H 法 は ， C M M グ ラ フ を 低 次 元 の H a m m i n g 空 間 に 潰 し 込 む こ と で ， ス ケ ッ チ と 3 D モ デ ル の 双 方 を コ ン パ ク ト な バ イ ナ リ コ ー ド で 表 現 し ， 効 率 良 く 比 較 す る ． ま た ， ス ケ ッ チ お よ び 3 D モ デ ル の 視 覚 特 徴 を 改 良 す る こ と で ， 検 索 精 度 の 改 善 を ね ら う ． 5 章 で は ， C M M グ ラ フ 生 成 に 用 い る 特 徴 間 類 似 度 の 改 善 に つ い て 述 べ る ． 4 章 で 用 い る 特 徴 統 合 法 よ り も 高 精 度 な D M 統 合 法 を 提 案 し ， こ れ を C M M グ ラ フ 生 成 に 利 用 し た 場 合 の 検 索 精 度 を 評 価 す る ． 6 章 で は ， 本 論 文 の 結 論 と 今 後 の 展 望 に つ い て 述 べ る ．

関連研究

2.1. 3D モデルデータベースへの問い合わせ手段

検 索 要 求 と し て 何 を 3 D モ デ ル の デ ー タ ベ ー ス に 提 示 す る か は ， ユ ー ザ に と っ て の 使 い や す さ に 大 き く 影 響 す る ． こ れ ま で に 数 多 く の 検 索 要 求 の 提 示 方 法 が 提 案 さ れ て き た ． 例 え ば ， 3 D モ デ ル の 例 示 ， キ ー ワ ー ド ， 3 D ス ケ ッ チ ， 2 D 手 描 き ス ケ ッ チ ， 2 D 自 然 画 像 ， 単 一 視 点 の 深 さ 画 像 ， 等 が あ る ( 図 1 . 1 ) ． こ れ ら の 問 い 合 わ せ 手 段 の 中 で ， 最 適 な 問 い 合 わ せ 手 段 は ， ユ ー ザ や 利 用 シ ー ン ， デ ー タ ベ ー ス に よ っ て 異 な る ． 最 も 代 表 的 な 検 索 要 求 の 提 示 方 法 は ， 3 D モ デ ル の 例 示 で あ る ． こ れ ま で に 数 多 く の 手 法 が 提 案 さ れ て お り [ 3 ] – [ 5 ] ， 用 途 や デ ー タ セ ッ ト に よ っ て は ， 実 用 的 な 検 索 精 度 と 速 度 を 示 す ． 3 D モ デ ル の 例 示 に よ る 検 索 は ， 検 索 要 求 と 検 索 対 象 が 同 種 の デ ー タ で あ る た め ， 他 の 検 索 要 求 と 比 べ て ， 検 索 要 求 と 検 索 対 象 と の 比 較 が 行 い や す い ． し か し ， 検 索 要 求 と し て 与 え る 3 D モ デ ル を ユ ー ザ が 所 持 し て い る と は 限 ら な い た め ， 3 D モ デ ル の 例 示 に よ る 問 い 合 わ せ は ， 多 く の 利 用 シ ー ン に お い て 実 用 的 で は な い ． ユ ー ザ が 3 D モ デ ル を 所 持 し て い な い 場 合 ， 3 D ス ケ ッ チ 技 術 に よ っ て 3 D モ デ ル を 作 成 し ， こ れ を 検 索 要 求 と し て 用 い る こ と が 可 能 で あ る ． 3 D ス ケ ッ チ の 作 成 法 と し て ， 例 え ば ， I g a r a s h i ら の Te d d y [ 1 9 ] , K a r p e n k o r ら の S m o o t h S k e t c h [ 2 0 ] 等 が あ る ． し か し ， こ れ ら の 3 D ス ケ ッ チ 作 成 シ ス テ ム を 使 い こ な す に は “ コ ツ ” が 必 要 で あ り ， 多 く の ユ ー ザ に と っ て 簡 便 な 問 い 合 わ せ 方 法 と は 言 え な い ． キ ー ワ ー ド は ， ウ ェ ブ ペ ー ジ や 動 画 等 ， 多 く の 情 報 検 索 シ ス テ ム で 採 用 さ れ て い る 問 い 合 わ せ 方 法 で あ る ． 文 字 入 力 は ほ ぼ 全 て の 情 報 端 末 で 可 能 で あ る た め ， ユ ー ザ に と っ て 簡 便 で あ る ． キ ー ワ ー ド に よ る 3 D モ デ ル 検 索 [ 1 ] , [ 2 ] を 行 う た め に は ， 予 め デ ー タ ベ ー ス 中 の 3 D モ デ ル 群 に キ ー ワ ー ド タ グ を 付 与 す る 必 要 が あ る ． し か し な が ら ， 多 数 の 3 D モ デ ル に 対 し て 手 作 業 で キ ー ワ ー ド タ グ を 付 与 す る の は 大 変 手 間 が か か る ． 機 械 学 習 を 用 い て 半 自 動 的 に タ グ 付 与 を 行 う こ と は 可 能 で あ る が ， こ れ に は か な り の 数 の 有 ラ ベ ル 3 D モ デ ル が 必 要 と な る ． ま た ， ユ ー ザ が 欲 す る 3 D 形 状 に よ っ て は ， 形 状 や そ の 意 味 カ テ ゴ リ を 表 現 す る キ ー ワ ー ド が 存 在 し な い た め に ， 検 索 要 求 を 指 定 で き な い 場 合 が あ る ． さ ら に は ， 検 索 シ ス テ ム が ユ ー ザ の 使 用 言 語 に 対 応 し て い な い 可 能 性 も あ る ． 2 D 手 描 き ス ケ ッ チ に よ る 3 D モ デ ル 検 索 [ 6 ] – [ 9 ] は ， 近 年 ， タ ブ レ ッ ト 等 の 手 描 き ス ケ ッ チ 入 力 に 対 応 し た 端 末 の 普 及 に よ り ， 有 用 性 が 高 ま り つ つ あ る ． 手 描 き ス ケ ッ チ に よ る 問 い 合 わ せ は ， 誰 に と っ て も 使 い や す く ， 欲 す る 形 状 を 直 感 的 に 指 定 で き る 利 点 が あ る ． 手 描 き ス ケ ッ チ は 3 D モ デ ル 検 索 以 外 に も ， 2 次 元 画 像 や 動 画 等 の 視 覚 マ ル チ メ デ ィ ア デ ー タ 検 索 の 問 い 合 わ せ 手 段 と し て 用 い ら れ て い る [ 2 1 ] – [ 2 4 ] ． し か し ， モ ー ド が 異 な る 手 描 き ス ケ ッ チ と 3 D モ デ ル の 比 較 は 困 難 と さ れ ， そ の 精 度 は 低 い ． 手 描 き ス ケ ッ チ は 描 画 様 式 の 多 様 性 や ， 形 状 の 抽 象 化 ， ス ケ ッ チ 線 の 揺 ら ぎ を 含 む た め で あ る ． 2 D 自 然 画 像 は ， カ メ ラ 付 き 携 帯 端 末 等 の 普 及 に よ り ， 有 用 か つ 簡 便 な 問 い 合 わ せ 手 段 と な っ た ． 自 然 画 像 に よ る 3 D モ デ ル 検 索 で は ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 と 同 様 ， 異 な る モ ー ド の デ ー タ を 効 果 的 に 比 較 す る こ と が 課 題 と な る ． こ の 課 題 解 決 の た め に ， こ れ ま で に 提 案 さ れ た 自 然 画 像 に よ る 3 D モ デ ル 検 索 手 法 [ 2 5 ] , [ 2 6 ] は ， 自 然 画

像 の 領 域 分 割 を 行 う ． 即 ち ， 検 索 要 求 画 像 を ， 検 索 要 求 を 含 む 前 景 と そ れ 以 外 の 背 景 に 自 動 的 に 分 割 し ， 前 景 か ら 抽 出 し た 画 像 特 徴 と 3 D モ デ ル の 見 か け か ら 抽 出 し た 画 像 特 徴 を 比 較 す る ． し か し ， 自 然 画 像 が 複 数 の 物 体 を 含 む 場 合 や ， 背 景 散 ら か り ( b a c k g r o u n d c l u t t e r ) が 多 い 場 合 に は 前 景 と 背 景 の 分 割 に 失 敗 し て 精 度 が 低 下 す る 問 題 が あ る ． 近 年 で は ， 深 さ セ ン サ 付 き の 端 末 が 普 及 し つ つ あ り ， 単 一 視 点 の 深 さ 画 像 ( レ ン ジ ス キ ャ ン モ デ ル ) や 深 さ 画 像 群 か ら 再 構 成 し た 3 D モ デ ル を 検 索 要 求 と し て 用 い る こ と が 可 能 で あ る ． レ ン ジ ス キ ャ ン モ デ ル に よ る 3 D モ デ ル 検 索 手 法 の 多 く [ 2 7 ] – [ 3 0 ] は ， 検 索 要 求 の 深 さ 画 像 と デ ー タ ベ ー ス 中 の 3 D モ デ ル の 見 か け 画 像 を ， 画 像 特 徴 を 用 い て 比 較 す る ． こ の 問 い 合 わ せ 法 で は ， 深 さ 画 像 が し ば し ば 高 周 波 ノ イ ズ や 面 の 欠 損 等 を 含 む た め ， こ れ ら の ノ イ ズ に 対 し て 頑 強 に ， 検 索 要 求 と 検 索 対 象 を 特 徴 比 較 す る こ と が 課 題 と な る ． 深 さ 画 像 群 か ら 再 構 成 し た 3 D 形 状 に よ る 3 D モ デ ル 検 索 [ 3 1 ] , [ 3 2 ] で は ， K i n e c t 等 の 深 さ セ ン サ を 利 用 し て 取 得 し た 3 D 形 状 を 検 索 要 求 と し ， 3 D モ デ ル の 例 示 に よ る 検 索 と 同 様 の 手 法 を 用 い て デ ー タ ベ ー ス 中 の 3 D モ デ ル と 比 較 す る ． I c h i d a ら [ 3 3 ] は ， ユ ー ザ が 実 世 界 で 複 数 の 立 方 体 を 結 合 さ せ て 3 D 形 状 を 作 成 し ， こ れ を 計 算 機 内 に 取 り 込 ん で 検 索 要 求 と し て 用 い た ． 検 索 シ ス テ ム は ， ユ ー ザ が 作 成 し た 3 D 形 状 を ボ ク セ ル 化 し ， デ ー タ ベ ー ス 中 の ボ ク セ ル デ ー タ と 比 較 し て 検 索 結 果 を 返 す ． こ の 問 い 合 わ せ 方 法 は ， ユ ー ザ が 直 感 的 に 3 D 形 状 を 指 定 す る こ と が 可 能 で あ る ． し か し ， 使 用 で き る 立 方 体 の 数 が 少 な い た め に ， 表 現 で き る の は 大 ま か な 3 D 形 状 に 限 ら れ ， 詳 細 な 形 状 を 指 定 で き な い 欠 点 が あ る ． 以 上 の 問 い 合 わ せ 方 法 は ， い ず れ も 1 種 類 の 検 索 要 求 を 用 い て 3 D モ デ ル を 検 索 す る ． こ れ に 対 し ， 複 数 種 類 の 検 索 要 求 に 対 応 し た ， 3 D モ デ ル の 複 合 検 索 シ ス テ ム が 提 案 さ れ た [ 3 4 ] – [ 3 7 ] ． 中 で も F u n k h o u s e r ら が 作 成 し た 3 D モ デ ル 検 索 シ ス テ ム [ 3 4 ] は ， 3 D モ デ ル の 例 示 ， キ ー ワ ー ド ， 3 視 点 の 手 描 き ス ケ ッ チ ， 3 D ス ケ ッ チ ( Te d d y [ 1 9 ] ) 等 の 複 数 種 類 の 検 索 要 求 に 対 応 し て お り ， 検 索 精 度 は 不 十 分 な が ら も ， ユ ー ザ に と っ て 簡 便 な 3 D モ デ ル 検 索 を 可 能 と す る ．

2.2. スケッチによる 3D モデル検索の評価用データベース

検 索 ア ル ゴ リ ズ ム の 精 度 お よ び 効 率 を 評 価 す る に は ， 含 ま れ る デ ー タ の 各 々 に 正 解 カ テ ゴ リ 情 報 が 付 与 さ れ た 評 価 用 デ ー タ ベ ー ス が 必 要 で あ る ． こ れ ま で に ， 複 数 の ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 評 価 用 デ ー タ ベ ー ス が 作 成 さ れ た [ 6 ] – [ 8 ] , [ 1 8 ] ． 図 2 . 1 に ， 各 評 価 用 デ ー タ ベ ー ス に 含 ま れ る 検 索 要 求 ス ケ ッ チ と 検 索 対 象 3 D モ デ ル の 例 を 示 す ． E i t z ら [ 1 8 ] は ， ス ケ ッ チ 検 索 の 評 価 用 デ ー タ ベ ー ス ( S - P S B ) を 作 成 し た ． S - P S B に 含 ま れ る 1 , 8 1 4 枚 の 検 索 要 求 ス ケ ッ チ は ， E i t z ら の 先 の 研 究 で 作 成 し た 2 D 手 描 き ス ケ ッ チ コ ー パ ス [ 3 8 ] の 部 分 集 合 で あ る ． 1 , 8 1 4 個 の 検 索 対 象 3 D モ デ ル は ， P r i n c e t o n S h a p e B e n c h m a r k ( P S B ) [ 3 9 ] と 同 一 で あ る ． S - P S B は t e s t s e t と t r a i n s e t の 2 つ に 分 割 さ れ ， そ れ ぞ れ が 9 0 7 枚 の ス ケ ッ チ と 9 0 7 個 の 3 D モ デ ル を 含 む ． S - P S B の ス ケ ッ チ お よ び 3 D モ デ ル は ， 人 ， 動 物 ， 植 物 ， 乗 り 物 ， 家 具 等 の 多 様 な 意 味 カ テ ゴ リ に 分 類 さ れ て お り ， 意 味 カ テ ゴ リ の 数 は t e s t s e t が 9 0 ， t r a i n s e t が 9 2 で あ る ． t e s t s e t と t r a i n

s e t で 共 通 の 意 味 カ テ ゴ リ 数 は 2 1 で あ る ． 各 カ テ ゴ リ に 属 す る デ ー タ 数 に は ば ら つ き が あ り ， そ の 範 囲 は カ テ ゴ リ あ た り 4 ～ 5 0 で あ る ． S H R E C 2 0 1 2 の ス ケ ッ チ 検 索 部 門 に お い て 用 い ら れ た 評 価 用 デ ー タ ベ ー ス [ 6 ] ( S -S H 1 2 ) は ， 2 6 2 枚 の 検 索 要 求 ス ケ ッ チ と ， 4 0 0 個 の 検 索 対 象 3 D モ デ ル か ら 成 る ． 検 索 要 求 ス ケ ッ チ は 2 5 0 枚 の 手 描 き ス ケ ッ チ 群 ( “ H a n d - d r a w n ” ) と ， 1 2 枚 の プ ロ が 描 い た よ う な “ 精 確 な ” ス ケ ッ チ 群 ( “ S t a n d a r d l i n e ” ) か ら 成 り ， 蟻 ， カ ッ プ ， 椅 子 ， 人 ， 飛 行 機 等 の 1 3 カ テ ゴ リ の い ず れ か に 分 類 さ れ る ． 検 索 対 象 3 D モ デ ル は ， S H R E C 2 0 0 7 w a t e r t i g h t m o d e l s t r a c k [ 4 0 ] に 含 ま れ る 4 0 0 個 の w a t e r t i g h t な 3 D メ ッ シ ュ で あ る ． こ れ ら 4 0 0 個 の 3 D モ デ ル は ， 2 0 カ テ ゴ リ ( 内 1 3 カ テ ゴ リ は 検 索 要 求 ス ケ ッ チ と 同 じ ) に 分 類 さ れ ， 各 カ テ ゴ リ に は 2 0 個 の 3 D モ デ ル が 属 す る ． 検 索 対 象 3 D モ デ ル 集 合 は 2 つ あ り ， 1 つ 目 は 検 索 要 求 ス ケ ッ チ と 同 じ 1 3 カ テ ゴ リ に 属 す る 2 6 0 個 の 3 D モ デ ル 集 合 ( B a s i c v e r s i o n ) ， 2 つ 目 は ， B a s i c v e r s i o n に 他 7 カ テ ゴ リ の 3 D モ デ ル を 加 え た 4 0 0 個 の 3 D モ デ ル 集 合 ( E x t e n d e d v e r s i o n ) で あ る ． こ の ベ ン チ マ ー ク を 用 い た S H R E C 部 門 で は ， 検 索 要 求 ス ケ ッ チ ( H a n d - d r a w n ま た は S t a n d a r d l i n e ) と 検 索 対 象 3 D モ デ ル ( B a s i c v e r s i o n ま た は E x t e n d e d v e r s i o n ) の 全 て の 組 み 合 わ せ ( 4 通 り ) の そ れ ぞ れ に つ い て ， 検 索 精 度 が 評 価 さ れ た ． S H R E C 2 0 1 3 の ス ケ ッ チ 検 索 部 門 に お い て 用 い ら れ た 評 価 用 デ ー タ ベ ー ス [ 7 ] ( S -S H 1 3 ) は ， 9 0 個 の 多 様 な カ テ ゴ リ に 分 類 さ れ た 7 , 2 0 0 枚 の 検 索 要 求 ス ケ ッ チ と ， 同 じ 9 0 カ テ ゴ リ に 分 類 さ れ た 1 , 2 5 8 個 の 検 索 対 象 3 D モ デ ル か ら 成 る ． 検 索 要 求 ス ケ ッ チ は ， E i t z ら の 手 描 き ス ケ ッ チ コ ー パ ス [ 3 8 ] の 部 分 集 合 で あ り ， 1 カ テ ゴ リ 当 た り 8 0 枚 の ス ケ ッ チ を 含 む ． こ れ ら 検 索 要 求 ス ケ ッ チ は ， 2 , 7 0 0 枚 の ス ケ ッ チ を 含 む t e s t s e t と ， 4 ， 5 0 0 枚 の ス ケ ッ チ を 含 む t r a i n s e t に 分 割 さ れ ， t e s t s e t は カ テ ゴ リ 当 た り 3 0 枚 の ス ケ ッ チ ， t r a i n s e t は カ テ ゴ リ 当 た り 5 0 枚 の ス ケ ッ チ を 含 む ． 一 方 で 検 索 対 象 3 D モ デ ル は P S B の 部 分 集 合 で あ る ． 検 索 対 象 3 D モ デ ル 群 は ， t e s t s e t と t r a i n s e t に 分 割 さ れ て お ら ず ， 1 , 2 5 8 個 の 3 D モ デ ル 全 て が 検 索 対 象 で あ る ． S H R E C 2 0 1 4 の ス ケ ッ チ 検 索 部 門 に お い て 用 い ら れ た 評 価 用 デ ー タ ベ ー ス ( S -S H 1 4 ) [ 8 ] は ， 1 7 1 個 の 多 様 な カ テ ゴ リ に 分 類 さ れ た 1 3 , 6 8 0 枚 の 検 索 要 求 ス ケ ッ チ と ， 同 じ 1 7 1 個 の カ テ ゴ リ に 分 類 さ れ た 8 , 9 8 7 個 の 検 索 対 象 3 D モ デ ル か ら 成 る ． 検 索 要 求 ス ケ ッ チ は ， S H R E C 2 0 1 3 の ス ケ ッ チ 検 索 ベ ン チ マ ー ク と 同 様 ， E i t z ら の 手 描 き ス ケ ッ チ コ ー パ ス の 部 分 集 合 で あ り ， 1 カ テ ゴ リ 当 た り 8 0 枚 の ス ケ ッ チ を 含 む ． こ れ ら 検 索 要 求 ス ケ ッ チ は ， 5 , 1 3 0 枚 の ス ケ ッ チ か ら 成 る t e s t s e t と ， 8 , 5 5 0 枚 の ス ケ ッ チ か ら 成 る t r a i n s e t に 分 割 さ れ ， t e s t s e t は カ テ ゴ リ 当 た り 3 0 枚 の ス ケ ッ チ ， t r a i n s e t は カ テ ゴ リ 当 た り 8 0 枚 の ス ケ ッ チ を 含 む ． 一 方 で 検 索 対 象 3 D モ デ ル は P S B に 加 え ， E n g i n e e r i n g S h a p e B e n c h m a r k ( E S B ) [ 4 1 ] ， M c G i l l S h a p e B e n c h m a r k ( M S B ) [ 4 2 ] ， To y o h a s h i S h a p e B e n c h m a r k ( T S B ) [ 4 3 ] 等 複 数 の デ ー タ セ ッ ト か ら 合 計 8 , 9 8 7 個 選 び 出 さ れ た ． S - S H 1 3 [ 7 ] と 同 様 ， 検 索 対 象 3 D モ デ ル 群 は t e s t s e t と t r a i n s e t に 分 割 さ れ て お ら ず ， 8 , 9 8 7 個 の 3 D モ デ ル 全 て が 検 索 対 象 で あ る ． S - S H 1 4 は ， 現 存 す る 中 で は 最 大 規 模 の ス ケ ッ チ に よ る 3 D モ デ ル 検 索 ベ ン チ マ ー ク で あ る ．

( a ) S - P S B ( 約 9 0 カ テ ゴ リ ， 1 , 8 1 4 ス ケ ッ チ ， 1 , 8 1 4 モ デ ル ) ( b ) S - S H 1 2 ( 1 3 カ テ ゴ リ ， 2 6 2 ス ケ ッ チ ， 4 0 0 モ デ ル ) ( c ) S - S H 1 3 ( 9 0 カ テ ゴ リ ， 7 , 2 0 0 ス ケ ッ チ ， 1 , 2 5 8 モ デ ル ) ( d ) S - S H 1 4 ( 1 7 1 カ テ ゴ リ ， 1 3 , 6 8 0 ス ケ ッ チ ， 8 , 9 8 7 モ デ ル ) 図 2.1 ベンチマークに含まれるスケッチと 3D モデルの例．

2.3. 特徴比較

ス ケ ッ チ に よ る 3 D モ デ ル 検 索 等 の ク ロ ス モ ー ダ ル 検 索 で は ， 異 な る 種 類 の デ ー タ を ， 各 デ ー タ の モ ー ド を 跨 い で 効 果 的 に 比 較 す る こ と が 課 題 で あ る ． 高 精 度 な ク ロ ス モ ー ダ ル 検 索 を 実 現 す る に は ， 異 種 デ ー タ 間 で 計 算 さ れ る イ ン タ ー モ ー ダ ル ( i n t e r - m o d a l ) 類 似 度 に 加 え ， モ ー ド 毎 に 同 種 デ ー タ 間 で 計 算 さ れ る イ ン ト ラ モ ー ダ ル ( i n t r a - m o d a l ) 類 似 度 を 考 慮 す る こ と が 重 要 で あ る ． ス ケ ッ チ に よ る 3 D モ デ ル 検 索 で は ， ス ケ ッ チ と 3 D モ デ ル 間 の 類 似 度 が イ ン タ ー モ ー ダ ル 類 似 度 ， ス ケ ッ チ 相 互 の 類 似 度 お よ び 3 D モ デ ル 相 互 の 類 似 度 が イ ン ト ラ モ ー ダ ル 類 似 度 に 相 当 す る ． ま た ， ス ケ ッ チ や 3 D モ デ ル の 特 徴 比 較 で は ， こ れ ら の デ ー タ の 姿 勢 変 化 や 大 域 的 変 形 に 対 し て 頑 強 な 比 較 を 行 う た め に ， 局 所 特 徴 が 用 い ら れ る こ と が 多 い ． 局 所 特 徴 は ， ス ケ ッ チ や 3 D モ デ ル の 局 所 領 域 か ら 抽 出 さ れ る た め ， 姿 勢 変 化 や 大 域 的 変 形 に 影 響 を 受 け に く い 性 質 が あ る ． ス ケ ッ チ 画 像 お よ び 3 D モ デ ル ま た は そ の 見 か け 画 像 か ら ， 多 数 の 局 所 特 徴 が 抽 出 さ れ る ． こ れ ら 多 数 の 局 所 特 徴 か ら 成 る 局 所 特 徴 集 合 を デ ー タ 間 で 効 率 良 く 比 較 す る た め に ， 特 徴 統 合 が 用 い ら れ る ． 高 精 度 な イ ン タ ー モ ー ダ ル 類 H a n d - d r a w n S t a n d a r d l i n e

似 度 お よ び イ ン ト ラ モ ー ダ ル 類 似 度 を 得 る に は ， 精 度 良 く 局 所 特 徴 集 合 を 統 合 す る 必 要 が あ る ． 本 節 で は ま ず ， ス ケ ッ チ と 3 D モ デ ル の 特 徴 比 較 に 関 す る 先 行 研 究 を 述 べ る ( 2 . 3 . 1 節 ) ． 次 い で ， ク ロ ス モ ー ダ ル な 距 離 尺 度 学 習 に と っ て 重 要 な ， 3 D モ デ ル 相 互 の 特 徴 比 較 に 関 す る 先 行 研 究 ( 2 . 3 . 2 節 ) と ， ス ケ ッ チ 相 互 の 特 徴 比 較 に 関 す る 先 行 研 究 ( 2 . 3 . 3 節 ) に つ い て 述 べ る ． さ ら に ， 局 所 特 徴 集 合 の 統 合 手 法 ( 2 . 3 . 4 節 ) に つ い て 述 べ る ． 2.3.1. スケッチと 3D モデルの比較 (スケッチによる 3D モデル検索) デ ー タ の モ ー ド が 異 な る ス ケ ッ チ と 3 D モ デ ル を 特 徴 比 較 す る に は ， こ れ ら を 何 ら か の 方 法 で 同 種 デ ー タ に 変 換 す る 必 要 が あ る ． そ の た め の ア プ ロ ー チ は 大 き く 2 つ あ る ． 1 つ 目 は ， 3 D モ デ ル を 2 D の 線 画 画 像 に 多 視 点 レ ン ダ リ ン グ し て ， 画 像 特 徴 を 用 い て ス ケ ッ チ と 特 徴 比 較 す る 方 法 で あ る ． 2 つ 目 は ， 2 D ス ケ ッ チ か ら 3 D 形 状 を 復 元 し て ， 3 D モ デ ル 相 互 の 特 徴 比 較 を 行 う 方 法 で あ る ． こ れ ま で に 提 案 さ れ て き た ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 手 法 群 の ほ と ん ど は ， 1 つ 目 の ア プ ロ ー チ を 採 用 す る ． 一 方 で 2 つ 目 の ア プ ロ ー チ を 採 用 し た 手 法 は 少 な い も の の ， 例 え ば C a o ら [ 4 4 ] は ， ユ ー ザ が 描 い た 2 D の 線 画 か ら L i p s o n ら の 手 法 [ 4 5 ] を 用 い て 3 D 形 状 を 復 元 し ， こ の 3 D 形 状 か ら 3 D 幾 何 特 徴 量 を 抽 出 し て デ ー タ ベ ー ス 内 の 3 D モ デ ル 群 と 比 較 し た ． た だ し ， [ 4 5 ] の 手 法 で 3 D 形 状 に 復 元 で き る の は 単 純 な 人 工 物 に 限 ら れ る た め ， 複 雑 な 形 状 や 動 植 物 を 検 索 す る こ と が で き な い 欠 点 が あ る ． 1 つ 目 の ア プ ロ ー チ で あ る ， 画 像 特 徴 を 用 い た ス ケ ッ チ と 3 D モ デ ル の 比 較 で は ， 如 何 に し て 高 精 度 に ， か つ ， 高 速 に ス ケ ッ チ 画 像 と 3 D モ デ ル の レ ン ダ リ ン グ 画 像 を 比 較 す る か ， が 問 題 と な る ． ス ケ ッ チ は 多 様 な 描 画 ス タ イ ル や 形 状 の 抽 象 化 ， ス ト ロ ー ク ノ イ ズ を 多 く 含 み ， ま た 3 D モ デ ル の 線 画 レ ン ダ リ ン グ 手 法 は 3 D モ デ ル の 形 状 表 現 や メ ッ シ ュ の 解 像 度 に よ っ て は 上 手 く 機 能 し な い 場 合 が あ る ． さ ら に ， 3 D モ デ ル は 大 抵 ， 多 視 点 か ら レ ン ダ リ ン グ さ れ る た め に ス ケ ッ チ と 比 較 す べ き 画 像 の 数 が 増 え ， 特 徴 比 較 の 計 算 量 が 増 大 す る 問 題 が あ る ． 以 下 で は ま ず ， 画 像 特 徴 を 用 い た ス ケ ッ チ と 3 D モ デ ル の 特 徴 比 較 に 関 す る 先 行 研 究 に つ い て 述 べ ， 次 い で ス ケ ッ チ 検 索 の 高 速 化 を 狙 っ た 先 行 研 究 を 述 べ る ． ス ケ ッ チ と 3 D モ デ ル の 特 徴 比 較 ア ル ゴ リ ズ ム Yo o n ら [ 4 6 ] は ， D e C a r l o ら の S u g g e s t i v e C o n t o u r 法 [ 4 7 ] を 用 い て 3 D モ デ ル を 特 徴 稜 線 画 像 に レ ン ダ リ ン グ し ， ス ケ ッ チ 画 と 比 較 し た ． Yo o n ら の 手 法 は ， ま ず 検 索 対 象 3 D モ デ ル を 1 4 視 点 ( 3 D モ デ ル を 囲 む 立 方 体 の 頂 点 お よ び 面 の 重 心 ) か ら 特 徴 稜 線 レ ン ダ リ ン グ し て 2 D 線 画 画 像 に 変 換 す る ． 各 線 画 画 像 を 拡 散 テ ン ソ ル 解 析 に 基 づ く 大 域 特 徴 H O G - D T F で 記 述 し ， 検 索 要 求 ス ケ ッ チ の 特 徴 と 比 較 す る ． H O G - D T F 特 徴 の 抽 出 法 は 次 の 通 り で あ る ． ま ず 画 素 毎 に ， そ の 画 素 を 中 心 と し た 小 さ な 局 所 領 域 内 に お い て 画 素 値 の 共 分 散 行 列 を 計 算 し ， こ の 行 列 の 固 有 値 解 析 を 行 う ． 互 い に 直 交 す る 2 本 の 固 有 ベ ク ト ル は 拡 散 方 向 ， 固 有 値 は 拡 散 強 度 を 示 す ． 全 画 素 に つ い

て 計 算 し た 方 向 と 強 度 を ， H O G 特 徴 [ 4 8 ] と 同 様 の 向 き ヒ ス ト グ ラ ム に 投 票 す る こ と で ， H O G - D T F 特 徴 ベ ク ト ル を 生 成 す る ． H O G 特 徴 が 隣 接 画 素 か ら 計 算 さ れ る 勾 配 を 用 い る た め に ス ケ ッ チ 線 の 揺 ら ぎ に 影 響 を 受 け や す い 欠 点 が あ る の に 対 し ， H O G - D T F 特 徴 は ， あ る 程 度 広 い 範 囲 か ら 線 の 向 き を 計 算 す る た め に ， 線 の 揺 ら ぎ に 対 し て 頑 強 で あ る 利 点 が あ る ． S h a o ら [ 4 9 ] は ， 検 索 対 象 3 D モ デ ル を P C A で 向 き あ わ せ し た 後 ， 7 視 点 ( 正 面 ， 側 面 ， 上 面 ， さ ら に 3 D モ デ ル を 囲 む 立 方 体 の 上 4 頂 点 ) か ら 特 徴 稜 線 レ ン ダ リ ン グ し て ス ケ ッ チ 画 と 特 徴 比 較 し た ． 特 徴 比 較 で は ， ス ケ ッ チ 線 お よ び 特 徴 稜 線 上 に 1 0 0 個 程 度 の 点 を サ ン プ ル し ， 点 群 間 の マ ッ チ ン グ を 取 る こ と で ， ス ケ ッ チ と 3 D モ デ ル の 稜 線 画 像 を 比 較 す る ． た だ し 点 群 マ ッ チ ン グ に よ る 特 徴 比 較 の 計 算 量 が 大 き い た め ， ス ケ ッ チ と デ ー タ ベ ー ス 中 の 全 3 D モ デ ル の 全 特 徴 稜 線 画 像 と の 比 較 が 遅 い 問 題 が あ る ． E i t z ら の B F - G A L I F 法 [ 1 8 ] は ， ス ケ ッ チ 画 お よ び 3 D モ デ ル の 特 徴 稜 線 画 像 ( 2 0 2 視 点 ) か ら 密 に 局 所 画 像 特 徴 を 抽 出 し ， B a g - o f - F e a t u r e s ( B F ) 法 [ 1 3 ] を 用 い て 画 像 あ た り 1 つ の 特 徴 ベ ク ト ル に 統 合 し ， 比 較 す る ． 線 画 画 像 向 け の 局 所 特 徴 と し て G A b o r l o c a l L I n e - b a s e d F e a t u r e ( G A L I F ) 特 徴 が 提 案 さ れ た ． G A L I F 特 徴 抽 出 ア ル ゴ リ ズ ム ( 図 2 . 2 ) は ， 入 力 さ れ た 線 画 画 像 に 複 数 方 向 ( [ 1 8 ] で は 4 方 向 ) の G a b o r フ ィ ル タ を 適 用 し ， 複 数 方 向 の 反 応 画 像 を 得 る ． 局 所 領 域 内 の 各 方 向 の 反 応 値 を 特 徴 ベ ク ト ル 化 す る ． ス ケ ッ チ と 3 D モ デ ル の 特 徴 比 較 で は ， G A L I F 特 徴 集 合 を B F 統 合 す る こ と で 得 た ス ケ ッ チ 画 の B F - G A L I F 特 徴 と ， 3 D モ デ ル の 各 視 点 の B F - G A L I F 特 徴 と を C o s i n e 類 似 度 で 比 較 し ， そ れ ら の 最 大 類 似 度 を ， ス ケ ッ チ と 3 D モ デ ル 間 の 類 似 度 と し た ． 図 2.2 GALIF 特徴抽出 [18]． L i u ら [ 5 0 ] は ， 工 業 製 品 の 設 計 者 が 描 く “ 精 確 な ” 手 描 き ス ケ ッ チ を 検 索 要 求 と し て 用 い ， 機 械 C A D モ デ ル を 検 索 す る 手 法 を 提 案 し た ． 検 索 要 求 ス ケ ッ チ ま た は 3 D モ デ ル の 線 画 画 像 上 に 準 乱 数 を 用 い て 一 様 に 5 0 0 個 の 特 徴 点 を 配 置 し ， 各 特 徴 点 に お

…

G a b o r フ ィ ル タ リ ン グ 線 画 画 像 G a b o r フ ィ ル タ 反 応 画 像 局 所 領 域 R の G A L I F 特 徴 ベ ク ト ル 特 徴 記 述 局 所 領 域 R

…

い て 回 転 不 変 な 局 所 特 徴 を 抽 出 す る ． L i u ら が 用 い た 局 所 特 徴 は ， 特 徴 点 を 中 心 と し た 同 心 円 で 特 徴 領 域 を 部 分 領 域 に 分 割 し ， 各 部 分 領 域 に 含 ま れ る ス ケ ッ チ 画 素 数 を カ ウ ン ト し て 得 た ヒ ス ト グ ラ ム で あ る ． 画 像 あ た り 5 0 0 個 の 局 所 特 徴 集 合 を B F 法 で 画 像 あ た り 1 個 の 特 徴 ベ ク ト ル に 統 合 し ， 効 率 良 く 比 較 す る ． さ ら に L i u ら は ， ユ ー ザ 毎 の ス ケ ッ チ の ス タ イ ル や 検 索 の 好 み に 適 応 し た 検 索 シ ス テ ム を 構 築 し た ． ユ ー ザ の 過 去 の 検 索 履 歴 を 解 析 す る こ と で ， 検 索 に 寄 与 し た 視 覚 単 語 に 対 し て 重 み 付 け を 行 い ， 特 徴 比 較 に 反 映 さ せ た ． Z o u ら の P y r a m i d - o f - P a r t s 法 [ 5 1 ] は ， 線 画 ス ケ ッ チ と 3 D モ デ ル の 特 徴 稜 線 と の マ ッ チ ン グ 精 度 を 向 上 さ せ る た め に マ ル チ ス ケ ー ル 特 徴 を 採 用 し た ． P y r a m i d - o f - P a r t s 法 で は ま ず ， ス ケ ッ チ 画 も し く は 特 徴 稜 線 画 像 を ， 正 規 格 子 で 3 × 3 の セ ル に 分 割 す る ． 3 × 3 の セ ル か ら ， 複 数 の サ イ ズ の 正 方 領 域 を サ ン プ ル す る こ と で ， 多 重 解 像 度 ピ ラ ミ ッ ド を 構 成 す る ( 図 2 . 3 ) ． 各 正 方 領 域 を G A L I F 特 徴 [ 1 8 ] で 記 述 し ， 全 正 方 領 域 の G A L I F 特 徴 を 連 接 す る こ と で ， 線 画 画 像 の 特 徴 ベ ク ト ル を 得 る ． 単 純 な 手 法 で は ス ケ ッ チ 画 の 線 は 正 規 格 子 の 境 界 で 分 断 さ れ る が ， Z o u ら は ， ス ケ ッ チ と 3 D モ デ ル の 部 分 マ ッ チ ン グ を よ り 高 精 度 化 す る 工 夫 を 施 し た ． 具 体 的 に は ， ユ ー ザ が ス ケ ッ チ を 描 く 際 ， ユ ー ザ に 複 数 の 意 味 の あ る 部 分 ( s e m a n t i c p a r t s ， 例 え ば ス ト ロ ー ク ) を 指 定 さ せ ， 1 つ の s e m a n t i c p a r t は 1 つ の 正 方 領 域 に 属 す よ う な 制 約 を 加 え て P y r a m i d - o f - P a r t s 特 徴 を 抽 出 す る ． 一 方 で ， 検 索 対 象 は セ グ メ ン テ ー シ ョ ン 済 み の 3 D モ デ ル と し ， 特 徴 稜 線 画 像 に セ グ メ ン テ ー シ ョ ン 情 報 を 転 移 さ せ ， ス ケ ッ チ と 同 様 ， 1 つ の s e m a n t i c p a r t は 1 つ の 正 方 領 域 に 属 す よ う な 制 約 を 加 え た P y r a m i d - o f - P a r t s 特 徴 を 計 算 す る ． ス ケ ッ チ 画 と 特 徴 稜 線 画 像 の P y r a m i d - o f - P a r t s 特 徴 を 比 較 す る こ と で ， 従 来 法 よ り も 高 い 検 索 精 度 を 示 し た ． さ ら に Z o u ら は ， ユ ー ザ に と っ て の 利 便 性 を 向 上 さ せ る た め ， P y r a m i d - o f - P a r t s 法 を 利 用 し て ， “ 不 完 全 な ” ス ケ ッ チ に よ る 3 D モ デ ル 検 索 を 行 っ た ． こ の 検 索 の 枠 組 み で は ， ユ ー ザ は 欲 す る 3 D モ デ ル の 一 部 を 描 く だ け で 検 索 結 果 が 得 ら れ る ． 図 2.3 Pyramid-of-Parts 法 [51]による線画画像の領域分割の例． 線 画 画 像 は ユ ー ザ の 指 定 に よ り ， 例 え ば ス ト ロ ー ク 単 位 に 分 割 済 み と す る ． Yo o n ら [ 5 2 ] は ス パ ー ス コ ー デ ィ ン グ を 利 用 し た 特 徴 比 較 に よ り ， H O G - D T F 法 [ 4 6 ] の 検 索 精 度 を 改 善 し た ． こ の 手 法 で は ま ず ， 検 索 対 象 3 D モ デ ル を 1 4 視 点 か ら レ ン ダ リ ン グ し て 得 た 特 徴 稜 線 画 像 群 の そ れ ぞ れ を ， H O G - D T F 特 徴 で 記 述 す る ． オ リ ジ ナ ル の H O G - D T F 法 で は ス ケ ッ チ 画 と 特 徴 稜 線 画 像 群 の H O G - D T F 特 徴 を C o s i n e 類 似 線 画 画 像 P y r a m i d - o f - P a r t s

度 で 比 較 す る の に 対 し ， Yo o n ら の 手 法 は ス パ ー ス コ ー デ ィ ン グ を 用 い て ， H O G - D T F 特 徴 空 間 に 適 応 し た 類 似 度 比 較 を 行 う ． 具 体 的 に は ， ま ず デ ー タ ベ ー ス の 全 3 D モ デ ル の 特 徴 稜 線 画 像 か ら 抽 出 し た H O G - D T F 特 徴 群 を 基 底 と し た 辞 書 を 生 成 す る ． 次 に こ の 辞 書 を 用 い て 検 索 要 求 ス ケ ッ チ の H O G - D T F 特 徴 を 疎 な 係 数 ベ ク ト ル に ス パ ー ス 符 号 化 す る ． 係 数 ベ ク ト ル の 要 素 の 絶 対 値 を ， ス ケ ッ チ と 特 徴 稜 線 画 像 間 の 類 似 度 と し ， こ の 類 似 度 を 元 に し て デ ー タ ベ ー ス 中 の 3 D モ デ ル 群 を 順 位 付 け る ． Yo o n ら は ス パ ー ス 符 号 化 の 際 に ， 広 く 用 い ら れ る L A S S O 法 [ 5 3 ] の 代 わ り に ， よ り 高 精 度 な 係 数 ベ ク ト ル が 得 ら れ る と さ れ る E l a s t i c n e t 法 [ 5 4 ] を 用 い た ． L A S S O 法 は 係 数 ベ ク ト ル の L 1 ノ ル ム 最 小 化 問 題 を 解 く こ と で ， 特 徴 を ス パ ー ス 符 号 化 す る ． 一 方 で ， E l a s t i c n e t は 係 数 ベ ク ト ル の L 1 ノ ル ム と L 2 ノ ル ム の 双 方 を 同 時 に 最 小 化 す る 最 適 化 問 題 を 解 く こ と で ， 特 徴 を ス パ ー ス 符 号 化 す る ． E l a s t i c n e t で は ， ス パ ー ス 符 号 化 に 用 い ら れ る 基 底 が そ の 特 徴 空 間 に お い て 互 い に 近 く な る 効 果 ( い わ ゆ る g r o u p i n g e f f e c t ) が 得 ら れ る ． 基 底 群 の 局 所 性 が 高 ま る こ と で ， よ り 正 確 に H O G - D T F 特 徴 の 位 置 を ス パ ー ス 符 号 化 で き る ． 実 験 で は ， ス パ ー ス コ ー デ ィ ン グ に よ る 特 徴 比 較 は ， C o s i n e 距 離 に よ る 特 徴 比 較 よ り も 有 意 に 高 い 検 索 精 度 を 示 し た ． Yo o n ら [ 5 5 ] と We n ら [ 5 6 ] は ， 複 数 種 類 の 特 徴 ( 大 域 画 像 特 徴 と 局 所 画 像 特 徴 ) を 用 い て ， ス ケ ッ チ 画 像 と 特 徴 稜 線 画 像 の マ ッ チ ン グ 精 度 を 向 上 さ せ た ． Yo o n ら [ 5 5 ] は ， 検 索 対 象 3 D モ デ ル を 6 視 点 か ら レ ン ダ リ ン グ し て 得 た 特 徴 稜 線 画 像 を ， 大 域 特 徴 H O G - D T F [ 4 6 ] と 局 所 特 徴 B F - S I F T で 記 述 す る ． B F - S I F T は ， 画 像 か ら 2 D 平 面 内 の 回 転 に 不 変 な S I F T 特 徴 [ 5 7 ] を 多 数 抽 出 し ， 画 像 毎 に B F 統 合 す る こ と で 得 ら れ る ． H O G - D T F と B F - S I F T を 連 接 し た 特 徴 ベ ク ト ル を ， [ 5 2 ] と 同 様 に ス パ ー ス コ ー デ ィ ン グ を 利 用 し て 精 度 良 く 比 較 し た ． We n ら [ 5 6 ] は ， 検 索 対 象 3 D モ デ ル を 1 6 2 視 点 か ら 多 視 点 レ ン ダ リ ン グ し て 得 た 特 徴 稜 線 画 像 上 に 特 徴 点 を 一 様 に サ ン プ ル し ， 各 特 徴 点 を 局 所 特 徴 と 大 域 特 徴 で 記 述 し た ． 局 所 特 徴 と し て H O G 特 徴 [ 4 8 ] を 元 に 新 た に 提 案 し た H S O 特 徴 ( 線 の 向 き の 頻 度 ヒ ス ト グ ラ ム ) を 用 い ， 大 域 特 徴 と し て S h a p e C o n t e x t 特 徴 [ 5 8 ] を 抽 出 す る ． 次 い で ， こ れ ら 局 所 特 徴 集 合 と 大 域 特 徴 集 合 を 別 々 に ， B F 法 を 用 い て 画 像 あ た り 1 つ の 特 徴 ベ ク ト ル に 統 合 す る ． ス ケ ッ チ と 特 徴 稜 線 画 像 間 の 距 離 は ， こ れ ら 2 種 の B F 統 合 特 徴 間 の 距 離 の 重 み 付 き 総 和 に 等 し い ． We n ら は ， さ ら に ス ケ ッ チ 検 索 の 精 度 を 改 善 す る た め に ， 適 合 度 フ ィ ー ド バ ッ ク を 行 っ た ． 1 回 目 の 検 索 の 後 ， ユ ー ザ か ら 与 え ら れ た 正 例 と 負 例 に 基 づ い て ， 局 所 特 徴 と 大 域 特 徴 の 重 み の 調 整 を 行 う ． ま た ， ク エ リ 拡 張 ( ク エ リ と 正 例 の 特 徴 群 の 平 均 ベ ク ト ル を 新 た な ク エ リ と す る ) も 行 う ． P u ら [ 5 9 ] ， K u r i t a ら [ 6 0 ] ， K a n g ら [ 6 1 ] ， L e i ら [ 6 2 ] は ， 3 視 点 ス ケ ッ チ に よ る 3 D モ デ ル 検 索 を 行 い ， 検 索 精 度 を 改 善 さ せ た ． 3 視 点 ス ケ ッ チ と は ， ユ ー ザ が 欲 す る 3 D 形 状 の 3 つ の 視 点 ( 例 え ば ， 正 面 ， 側 面 ， 上 面 ) か ら の 見 か け を 描 い た 3 枚 の ス ケ ッ チ 画 を 指 す ． 図 2 . 4 に K u r i t a ら が 用 い た 3 視 点 ス ケ ッ チ の 例 を 示 す ． 3 視 点 ス ケ ッ チ は ， 1 視 点 ス ケ ッ チ よ り も ユ ー ザ が 欲 す る 形 状 の 手 が か り が 増 え る た め ， 検 索 精 度 の 向 上 が 期 待 で き る ． し か し そ の 一 方 で ， ユ ー ザ は 3 枚 の ス ケ ッ チ を 描 く 必 要 が あ る た め ， ユ ー ザ に と っ て の 手 間 が 増 加 す る 問 題 が あ る ．

図 2.4 3 視点スケッチ画像の例 [60]． P u ら は ， 3 視 点 ス ケ ッ チ 入 力 と 適 合 度 フ ィ ー ド バ ッ ク を 組 み 合 わ せ た ， 機 械 C A D モ デ ル の ス ケ ッ チ 検 索 シ ス テ ム を 提 案 し た ． P u ら の 手 法 は ， 面 の 法 線 分 布 に 対 し て P C A を 適 用 し て 3 D モ デ ル を 向 き あ わ せ し た 後 ， 3 D モ デ ル を 3 視 点 ( 正 面 ， 側 面 ， 上 面 ) か ら 線 画 レ ン ダ リ ン グ す る ． ス ケ ッ チ 画 像 と 3 D モ デ ル の 線 画 画 像 は ， 2 D 平 面 内 の 回 転 に 不 変 な 大 域 特 徴 で 記 述 さ れ る ． こ の 大 域 特 徴 は ， 3 D モ デ ル の 特 徴 で あ る D 2 特 徴 [ 6 3 ] を 2 D 化 し た 特 徴 で ， 即 ち ， 線 画 画 像 の 線 上 に 多 数 の 点 を ラ ン ダ ム に 配 置 し ， 全 点 対 間 の 距 離 を ヒ ス ト グ ラ ム 化 す る こ と で 計 算 さ れ る ． K u r i t a ら [ 6 0 ] は ， シ ル エ ッ ト 化 さ れ た 3 視 点 ス ケ ッ チ 画 像 ， お よ び ， 3 D モ デ ル の シ ル エ ッ ト 画 像 か ら B F - D S I F T 特 徴 [ 6 4 ] を 抽 出 し て 比 較 し た ． さ ら に K u r i t a ら は ， ス ケ ッ チ 検 索 の 高 精 度 化 の た め 多 様 体 学 習 を 導 入 し た ． 画 像 毎 に 抽 出 さ れ た B F - D S I F T 特 徴 に 対 し ， 多 様 体 学 習 を 用 い た 非 線 形 次 元 削 減 手 法 で あ る L L E 法 [ 6 5 ] を 用 い ， 5 0 次 元 の 低 次 元 空 間 に 埋 め 込 み ， 高 精 度 な 特 徴 比 較 を 行 っ た ． L L E の 計 算 を 高 速 化 さ せ る た め に K u r i t a ら は ， L L E の 学 習 サ ン プ ル と な る B F - D S I F T 特 徴 の 数 の 削 減 し た ． 全 モ デ ル の 全 視 点 の B F - D S I F T 特 徴 か ら 成 る 特 徴 空 間 ， ま た は ， 1 モ デ ル の 全 視 点 の B F - D S I F T 特 徴 か ら 成 る 特 徴 空 間 に 対 し て ク ラ ス タ リ ン グ を 行 い ， 各 ク ラ ス タ の 代 表 ベ ク ト ル を L L E の た め の 学 習 サ ン プ ル と し て 用 い た ． K a n g ら [ 6 1 ] は ， E i t z ら の B F - G A L I F 法 [ 1 8 ] を 改 良 し ， 3 視 点 ス ケ ッ チ を 検 索 要 求 と し た 3 D モ デ ル 検 索 を 行 っ た ． 検 索 対 象 3 D モ デ ル は 3 視 点 ( 正 面 ， 側 面 ， 上 面 ) か ら の み レ ン ダ リ ン グ さ れ ， 各 画 像 か ら B F - G A L I F 特 徴 を 抽 出 す る ． し か し ， K a n g ら の 手 法 は 3 D モ デ ル の 回 転 正 規 化 を 行 わ な い た め ， 3 D モ デ ル に ラ ン ダ ム 回 転 が 加 わ る と 特 徴 比 較 に 失 敗 す る 可 能 性 が あ る ． L e i ら [ 6 2 ] は ， ス ケ ッ チ 検 索 の 精 度 向 上 の た め ， 3 視 点 ス ケ ッ チ と 多 様 体 学 習 を 用 い た 3 D モ デ ル 検 索 手 法 を 提 案 し た ． 検 索 対 象 3 D モ デ ル は ， ま ず P C A で 向 き 合 わ せ さ れ た 後 ， 正 面 ， 側 面 ， 上 面 の 3 視 点 レ ン ダ リ ン グ に よ っ て 3 枚 の シ ル エ ッ ト 画 像 に 変 換 さ れ る ． 各 ス ケ ッ チ 画 お よ び 各 シ ル エ ッ ト 画 像 は ， 大 域 画 像 特 徴 で あ る F o u r i e r 特 徴 と H O G 特 徴 で 記 述 さ れ る ． ス ケ ッ チ と 3 D モ デ ル 間 の 距 離 は ， 対 応 す る 視 点 ( 正 面 ， 側 面 ， 上 面 ) の 画 像 特 徴 を 比 較 し ， 得 ら れ た 距 離 の 総 和 に よ り 求 め る ． さ ら に 検 索 精 度 を 改 善 さ せ る た め ， 3 D モ デ ル 特 徴 空 間 の 距 離 尺 度 学 習 を 導 入 し た ． ス ケ ッ チ と 3 D モ デ ル 間 の 比 較 手 法 と ， こ れ と 同 様 の 3 D モ デ ル 間 の 比 較 手 法 を 用 い て ， 検 索 要 求 ス ケ ッ チ と 3 D モ デ ル 群 か ら 成 る 特 徴 多 様 体 グ ラ フ を 生 成 す る ． こ の 特 徴 多 様 体 グ ラ フ に 対 し て P a g e R a n k 法 [ 6 6 ] を 適 用 し ， 多 様 体 グ ラ フ 上 の 拡 散 距 離 に 基 づ い て 3 D モ デ ル の 順 位 付 け を 行 う ． な お ， L i u ら の 距 離 尺 度 学 習 手 法 は ， Ta t s u m a ら が 用 い た S C M R 法 [ 3 7 ] と ほ ぼ 同 一 で あ る ．