結論

本 研 究 で は ， 実 用 的 な (即 ち ， ユ ー ザ に と っ て 使 い や す く ， 高 精 度 で ， か つ ， 高 速

な) 3 D モ デ ル 検 索 の 実 現 を 目 指 し ，2 D 手 描 き ス ケ ッ チ を 検 索 要 求 と し た 3 D モ デ ル 検

索 に 取 り 組 ん だ ． ス ケ ッ チ に よ る 3 D モ デ ル 検 索 で は ， モ ー ド が 異 な る デ ー タ を い か に 効 果 的 に 比 較 す る か が 課 題 と な る ． 手 描 き ス ケ ッ チ は ， 描 画 ス タ イ ル の 多 様 性 ， 形 状 の 抽 象 化 ， ス ケ ッ チ 線 の 揺 ら ぎ や 途 切 れ 等 の ノ イ ズ を 含 む た め ，3 D モ デ ル の 多 視 点 線 画 画 像 と の 特 徴 比 較 に し ば し ば 失 敗 す る ． こ の た め ， ス ケ ッ チ と 3 D モ デ ル の 多 視 点 線 画 画 像 を 直 接 的 に 特 徴 比 較 す る 既 存 の 検 索 ア ル ゴ リ ズ ム は ， 検 索 精 度 が 不 十 分 で あ り ， 実 用 的 な 水 準 で は な い ． ま た 既 存 手 法 は ， ス ケ ッ チ と 3 D モ デ ル の 多 視 点 画 像 群 と の 比 較 コ ス ト が 高 い た め に ， 大 規 模 な デ ー タ ベ ー ス (例 え ば ，1 0 万 個 の 3 D モ デ ル を 含 む デ ー タ ベ ー ス)の 検 索 が 遅 い 問 題 が あ る ．

本 研 究 で は ， ス ケ ッ チ 検 索 の 精 度 と 速 度 の 双 方 を 改 善 す る た め に ， ク ロ ス モ ー ダ ル な 距 離 尺 度 学 習 を 用 い た ス ケ ッ チ に よ る 3 D モ デ ル の 検 索 手 法 を 提 案 し た ． ク ロ ス モ ー ダ ル な 距 離 尺 度 学 習 で は ， ス ケ ッ チ と 3 D モ デ ル の 互 い の 関 係 性 を 学 習 し ， こ れ ら 異 種 デ ー タ の 比 較 に 適 し た 距 離 尺 度 を 獲 得 す る ． 本 研 究 で は ， ス ケ ッ チ と 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 グ ラ フ の 生 成 処 理 で は ， ま ず ， ス ケ ッ チ 相 互 を 特 徴 比 較 す る こ と で ， ス ケ ッ チ の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 を 生 成 す る ． 同 様 に ，3 D モ デ ル 相 互 を 特 徴 比 較 す る こ と で ，3 D モ デ ル の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 を 生 成 す る ． 次 い で ， こ れ ら 2 つ の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 を ， ス ケ ッ チ と 3 D モ デ ル の 特 徴 間 類 似 度 お よ び 意 味 ラ ベ ル 間 類 似 度 を 用 い て 接 続 す る こ と で ， 単 一 の 多 様 体 グ ラ フ ( C M M グ ラ フ)に 統 合 す る ．

C M M を 用 い る こ と の 利 点 は ， 学 習 後 の 距 離 尺 度 に ， ス ケ ッ チ と 3 D モ デ ル 間 の 関 係 性

だ け で な く ， 複 数 の ス ケ ッ チ 相 互 の 関 係 性 と ， 複 数 の 3 D モ デ ル 相 互 の 関 係 性 を 反 映 で き る こ と で あ る ． こ れ に よ り ， ス ケ ッ チ と 3 D モ デ ル 間 の 関 係 性 だ け を 用 い る 既 存 手 法 よ り も ， 高 い 検 索 精 度 が 得 ら れ る ．

本 研 究 で は C M M を 用 い た ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 手 法 と し て ，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 )法 と ， そ の ス ケ ー ラ ビ リ テ ィ 改 善 を 狙 っ た 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 )法 を 提 案 し た ．

こ れ ら の 提 案 手 法 を ， 複 数 の 評 価 用 デ ー タ ベ ー ス を 用 い て 評 価 し た 結 果 ， ク ロ ス モ ー ダ ル 距 離 尺 度 学 習 が ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の 精 度 向 上 に 効 果 的 で あ る こ と が 分 か っ た ． 例 え ば ， 代 表 的 な 既 存 手 法 で あ る B F - G A L I F 法 の 検 索 精 度 は ，S - P S B ベ ン チ マ ー ク で M A P = 1 7 . 4 %，S - S H 1 4 ベ ン チ マ ー ク で 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 法 の 検 索 精 度 も 実 用 的 な 水 準 で は な い も の の ， 既 存 手 法 と 比 較 し て 大 幅 に 検 索 精 度 が 向 上 し た ． ま た ， 大 規 模 デ ー タ ベ ー ス に お け る 検 索 が 大 幅 に 高 速 化 さ れ た ．C M M H 法 を 用 い る こ と

で ，1 0 万 個 の 検 索 対 象 3 D モ デ ル か ら 成 る デ ー タ ベ ー ス を ， 検 索 1 回 当 た り 約 1 秒 で 処 理 で き た ． 本 研 究 は ， ス ケ ッ チ に よ る3 D モ デ ル 検 索 を 実 用 的 な 水 準 に 一 歩 近 づ け る こ と に 成 功 し た と 言 え る ．

以 下 で は ， 各 章 に お い て 提 案 し た 手 法 と ， 得 ら れ た 知 見 を 振 り 返 る ．

ク ロ ス モ ー ダ ル 多 様 体 ラ ン キ ン グ を 用 い た ス ケ ッ チ に よ る 3 D モ デ ル の 検 索 ( 3 章) 3 章 で 提 案 し た C M M R 法 は ，C M M グ ラ フ 上 の 類 似 度 拡 散 を 利 用 し て ス ケ ッ チ と 3 D モ デ ル を 比 較 す る ．C M M R 法 で は ， 検 索 要 求 ス ケ ッ チ に 対 応 す る ノ ー ド か ら 類 似 度 を 拡 散 さ せ ，C M M グ ラ フ の 辺 を 介 し て 他 の ス ケ ッ チ 群 と 3 D モ デ ル 群 に 類 似 度 を 伝 播 さ せ る ． 類 似 度 拡 散 の 結 果 に 基 づ い て デ ー タ ベ ー ス 中 の 3 D モ デ ル 群 を 順 位 付 け し ， 検 索 結 果 が 生 成 さ れ る ．C M M R 法 の 特 長 は ， 以 下 の 通 り で あ る ．

 C M M グ ラ フ は ， 各 デ ー タ 間 の 比 較 に 適 し た 特 徴 を 用 い て 生 成 す る こ と が で き る ．

即 ち ， ス ケ ッ チ 相 互 の 比 較 ，3 D モ デ ル 相 互 の 比 較 ， ス ケ ッ チ と 3 D モ デ ル の 比 較 ， の そ れ ぞ れ に お い て ， 最 適 な 比 較 ア ル ゴ リ ズ ム を 利 用 可 能 で あ る ( C M M H 法 も 本 特 長 を 持 つ)．

 意 味 ラ ベ ル の 有 無 に 応 じ て ， 教 師 な し ， 教 師 あ り ， 半 教 師 あ り の い ず れ の 枠 組 み に お い て も 用 い る こ と が で き る ( C M M H 法 も 本 特 長 を 持 つ)．

 類 似 度 が C M M グ ラ フ 上 の あ ら ゆ る 辺 を 介 し て 拡 散 す る た め ，C M M R 法 は C M M グ ラ フ 上 の シ ョ ー ト カ ッ ト や 穴 と い っ た 位 相 的 ノ イ ズ に 対 し て 頑 強 で あ る ．

 C M M R 法 は ， ス ケ ッ チ の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 上 の 類 似 度 拡 散 に よ っ て ，

検 索 要 求 ス ケ ッ チ と 類 似 し た ス ケ ッ チ 群 が 第 2 の 検 索 要 求 と し て 振 る 舞 う (即 ち ，

C M M R 法 は 自 動 ク エ リ 拡 張 を 行 う)． ま た ，3 D モ デ ル の イ ン ト ラ モ ー ダ ル 特 徴 多

様 体 上 の 類 似 度 拡 散 に よ っ て ， よ り 多 く の 正 解 3 D モ デ ル を 検 索 す る こ と が で き る ．

ま た 3 章 で は ， ス ケ ッ チ と 3 D モ デ ル の 画 像 比 較 の 精 度 を 向 上 さ せ る た め ， 画 像 の 回 転 正 規 化 法 R N - G a b o r を 提 案 し た ．R N - G a b o r 法 は ， 線 画 画 像 に 対 し て 複 数 方 向 の

G a b o r フ ィ ル タ を 適 用 し ， 得 ら れ た 反 応 画 像 の 画 素 値 を ， 方 向 ヒ ス ト グ ラ ム に 投 票 す る こ

と で ， 線 画 画 像 の 回 転 方 向 を 求 め る ．G a b o r フ ィ ル タ は ， あ る 程 度 大 域 的 に 線 の 向 き を 捉 え ら れ る た め ， ス ケ ッ チ 線 の 揺 ら ぎ や ス ト ロ ー ク ノ イ ズ に 対 し て 頑 強 に 画 像 の 回 転 正 規 化 を 行 う こ と が で き る ．

評 価 実 験 で は ，C M M R 法 と ， 距 離 尺 度 学 習 を 用 い な い 従 来 法 と の 精 度 比 較 を 行 っ た ． そ の 結 果 ，C M M R 法 に よ っ て 検 索 精 度 が 有 意 に 改 善 す る こ と が 分 か っ た ． 例 え

ば ，S - P S B デ ー タ ベ ー ス に お け る 教 師 な し C M M R 法 の 検 索 精 度 は M A P = 2 7 . 9 %と ，

E i t z ら の B F - G A L I F 法 の M A P = 1 7 . 4 %よ り も 1 0 %程 度 高 い 精 度 を 示 し た ． ま た ， 意 味 ラ ベ ル の 密 度 が 異 な る 2 つ の 評 価 用 デ ー タ ベ ー ス に お い て ， 教 師 あ り C M M R と 半 教 師

あ り C M M R の 振 る 舞 い を 比 較 し た ． そ の 結 果 ， デ ー タ ベ ー ス の 意 味 ラ ベ ル 付 け が 疎 で ，

か つ ， 偏 り が あ る 場 合 に ， 教 師 あ り C M M R 法 が 過 適 合 を 起 こ し て 精 度 低 下 し た ． 一 方

で ， 半 教 師 あ り C M M R は ， 疎 な ラ ベ ル 付 け で あ っ て も 精 度 が 向 上 し た ． デ ー タ ベ ー ス の 意 味 ラ ベ ル 付 け が 密 な 場 合 に は ， 教 師 あ り C M M R と 半 教 師 あ り C M M R の 双 方 が 高 い 精 度 を 示 し た ． ま た ，R N - G a b o r 法 に よ る 画 像 の 回 転 正 規 化 が 効 果 的 で あ る こ と が 示 さ れ た ． 局 所 的 な 画 素 勾 配 を 用 い た 回 転 正 規 化 法 ( R N - S o b e l )と 比 較 し て ， 少 な い レ ン ダ リ ン グ 視 点 数 に お け る 検 索 精 度 が 改 善 し た ． 検 索 速 度 に 関 し て は ， デ ー タ ベ ー ス の 規 模 が 大 き く な る と ，C M M R 法 に よ る 検 索 が 急 激 に 遅 く な る こ と が 分 か っ た ．

こ れ ら の 実 験 結 果 か ら ， 以 下 の 知 見 が 得 ら れ る ．

 ク ロ ス モ ー ダ ル な 距 離 尺 度 学 習 は ， ス ケ ッ チ に よ る 3 D モ デ ル 検 索 に 効 果 的 で あ る ．

 半 教 師 あ り C M M R は ， 疎 な ラ ベ ル 付 け に 対 し て 頑 強 な ク ロ ス モ ー ダ ル 距 離 尺 度 を 獲 得 す る こ と が で き る ．

 ス ケ ッ チ 画 像 と 3 D モ デ ル の 多 視 点 線 画 画 像 の 回 転 正 規 化 は ， 特 徴 比 較 の 改 善 に 効 果 的 で あ る ．

 C M M R 法 は ，C M M グ ラ フ 上 の 類 似 度 拡 散 の 計 算 量 が 大 き い た め に ， ス ケ ー ラ

ビ リ テ ィ に 限 界 が あ る ．

ク ロ ス モ ー ダ ル 多 様 体 ハ ッ シ ン グ を 用 い た ス ケ ッ チ に よ る 3 D モ デ ル 検 索 の ス ケ ー ラ ブ ル 化 ( 4 章)

4 章 で 提 案 し た C M M H 法 は ， ま ず ，L a p l a c i a n E i g e n m a p s ( L E )法 を 用 い て C M M グ ラ フ を ノ ー ド 間 の 類 似 性 が で き る だ け 保 存 さ れ る よ う な 低 次 元 実 数 値 空 間 に 非 線 形 写 像 す る ． 次 い で ，I t e r a t i v e Q u a n t i z a t i o n ( I T Q )法 を 用 い て ， バ イ ナ リ 化 に よ る 情 報 損 失 が 最 小 と な る よ う に 低 次 元 特 徴 空 間 を 回 転 さ せ ， そ の 後 ， 特 徴 空 間 の 閾 値 処 理 に よ

っ て H a m m i n g 空 間 に 潰 し 込 む ． ス ケ ッ チ と 3 D モ デ ル の 特 徴 は ， コ ン パ ク ト な (例 え ば

5 1 2 b i t の)バ イ ナ リ コ ー ド と し て 表 現 さ れ る ． ス ケ ッ チ と 3 D モ デ ル の バ イ ナ リ コ ー ド は ，

H a m m i n g 距 離 を 用 い て 比 較 さ れ る ．H a m m i n g 距 離 は ，C P U 実 行 サ イ ク ル 数 が 少 な い

た め に 効 率 良 く 計 算 可 能 で あ る ． ノ ー ド 数 1 0 万 以 上 の 大 規 模 な C M M グ ラ フ に 対 す る L E を 現 実 的 な 時 間 内 に 計 算 す る た め ，R a n d o m i z e d S V D ( R S V D )法 を 用 い て 大 規 模

C M M グ ラ フ の 固 有 ベ ク ト ル を 効 率 良 く 近 似 し た ．C M M H 法 の 特 長 は ， 以 下 の 通 り で あ

る ．

 バ イ ナ リ コ ー ド 間 の H a m m i n g 距 離 比 較 は 大 変 効 率 が 良 い た め ， 大 規 模 な デ ー タ ベ ー ス を 高 速 に 検 索 で き る ．

 大 規 模 な C M M グ ラ フ で あ っ て も ，R S V D 法 の 利 用 に よ り ， 現 実 的 な 時 間 内 で

C M M グ ラ フ を 低 次 元 実 数 値 空 間 に 埋 め 込 む こ と が で き る ．

ま た 4 章 で は ， 検 索 精 度 の 改 善 の た め に ，C M M グ ラ フ 生 成 に 用 い る 特 徴 を 改 善 し た ．3章 で 用 い た B a g - o f - F e a t u r e s ( B F )法 に 代 え て ， 近 年 提 案 さ れ た 高 精 度 な 特 徴 統 合 手 法 で あ る S u p e r Ve c t o r ( S V ) c o d i n g 法 と 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 法 を 利 用 し た ． こ れ ら の 統 合 法 を 用 い て 生 成 さ れ た 統 合 特 徴 を 比 較 す る こ と で ， よ り 高 精 度 な C M M グ ラ フ を 生 成 し た ．

評 価 実 験 で は ，1 0 万 個 の 検 索 対 象 3 D モ デ ル か ら 成 る デ ー タ ベ ー ス を 生 成 し ，

C M M H 法 の ス ケ ー ラ ビ リ テ ィ を 評 価 し た ． そ の 結 果 ，C M M R 法 は ，1 0 万 モ デ ル の デ ー タ

ベ ー ス を 検 索 1 回 当 た り 約 1 秒 で 処 理 で き る こ と が 分 か っ た ． ま た ， 十 分 な ビ ッ ト 数

( 5 1 2 b i t 程 度)を 用 い た 場 合 ，C M M グ ラ フ の ハ ッ シ ン グ は ，L E 法 だ け を 用 い て C M M グ

ラ フ を 実 数 値 特 徴 に 圧 縮 し た 場 合 と 比 較 し て ， 検 索 精 度 が ほ と ん ど 低 下 し な い こ と が 示 さ れ た ． さ ら に ，C M M グ ラ フ 生 成 に 用 い る 特 徴 を 改 善 さ せ る こ と で ，C M M R 法 お よ び

C M M H 法 の 検 索 精 度 が 有 意 に 改 善 し た ． こ れ ら の 実 験 結 果 か ら ， 以 下 の 知 見 が 得 ら

れ る ．

 C M M グ ラ フ の ハ ッ シ ン グ は ， 大 規 模 デ ー タ ベ ー ス に お け る 高 速 か つ 高 精 度 な ス

ケ ッ チ 検 索 に 効 果 的 で あ る ．

 C M M グ ラ フ 生 成 に 用 い る 特 徴 を 改 善 さ せ る こ と で ， よ り 良 い ク ロ ス モ ー ダ ル 距 離

尺 度 を 学 習 で き る (可 能 性 が あ る)．

特 徴 間 類 似 度 の 改 善 ( 5 章)

5 章 で は ，4 章 の 実 験 で 得 た 知 見 に 基 づ き ，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 )統 合 法 を 提 案 し た ．D M 法 は ， 特 徴 統 合 処 理 に 多 様 体 学 習 の 考 え を 導 入 し ， 従 来 の 特 徴 統 合 法 よ り も 情 報 損 失 の 少 な い 統 合 ベ ク ト ル を 生 成 す る ． 従 来 の 統 合 法 の 多 く ( B F法 ，V L A D 法 ，S V 法 ，L L 法 ， 等) は ， コ ー ド ワ ー ド 周 囲 の 局 所 特 徴 の 分 布 が 線 形 で あ る と 仮 定 す る た め に ， 局 所 特 徴 群 の 非 線 形 な 分 布 構 造 を 統 合 特 徴 に 反 映 さ せ る こ と が 困 難 で あ る ． ま た ， こ れ ら 従 来 法 は 局 所 特 徴 の 特 徴 空 間 を ク ラ ス タ リ ン グ す る こ と で 得 た 少 数 の コ ー ド ワ ー ド を 用 い る た め ， 統 合 時 に 局 所 特 徴 の 多 様 体 構 造 を 考 慮 で き な い ． 一 方 で D M 法 は ， 多 数 の 局 所 特 徴 群 か ら 直 接 的 に 多 様 体 グ ラ フ を 生 成 し ， 多 様 体 グ ラ フ 上 の 類 似 度 拡 散 を 利 用 し て 特 徴 統 合 を 行 う ．D M 法 の 特 長 は ， 以 下 の 通 り で あ る ．

 局 所 特 徴 の 空 間 の 非 線 形 性 を 統 合 特 徴 に 反 映 さ せ る こ と が で き る ．

 既 存 の 特 徴 統 合 法 と 異 な り コ ー ド ブ ッ ク 学 習 の 必 要 が な い た め ， 前 処 理 時 間 が 短 い (た だ し 統 合 処 理 は G M M ク ラ ス タ リ ン グ に 基 づ く S V 法 と 同 程 度)．

ま た ， 多 数 の 有 ラ ベ ル 自 然 画 像 を 学 習 済 み の 畳 み 込 み ニ ュ ー ラ ル ネ ッ ト ワ ー ク ( C N N )か ら 抽 出 さ れ る ス ケ ッ チ 特 徴 C A F， 局 所 3 D幾 何 特 徴 P o s i t i o n a n d O r i e n t a t i o n D i s t r i b u t i o n ( P O D )を 提 案 し た ．C A F 特 徴 は ， 有 ラ ベ ル 自 然 画 像 の 大 規 模 コ ー パ ス を 用 い て 学 習 済 み の C N N に ， ス ケ ッ チ 画 像 を 入 力 し ，C N N の 中 間 層 か ら 取 り 出 し た 特 徴 で あ る ．C A F 特 徴 は D M 法 に よ っ て エ ン コ ー ド さ れ ， エ ン コ ー ド さ れ た C A F 特 徴 を 比 較 す る こ と で ， ス ケ ッ チ の イ ン ト ラ モ ー ダ ル 特 徴 多 様 体 が 生 成 さ れ る ．P O D 特 徴 は ，3 D