DEIM Forum 2016 E4-1
SIFT 特徴量のクラスタリングに基づく特定物体認識手法
大関 陽裕
†大野 将樹
‡獅々堀 正幹
‡†徳島大学
先端技術科学教育学部 システム創生工学専攻 知能情報システム工学コース
‡徳島大学
大学院ソシオテクノサイエンス研究部
〒
770-8506 徳島県徳島市南常三島町 2-1
あらまし 近年，スマートフォンやデジタルカメラの普及に伴い，多くの画像データを高速かつ正確に処理する ことが一般的となってきた．本研究では，局所特徴量のクラスタリングを行う事で，大量の画像から特定の物体が 写った画像を検索する手法を提案する．特定物体の検索には，通常Bag of Features のような手法が一般的に用いら れるが，対象の物体以外とマッチングしてしまう点が問題点とされる．そこで本手法では局所特徴点は物体ごとに 集中して出現すると仮説を立て，局所特徴点にクラスタリングを施し，その結果を元に検索対象の画像を細かく分 割することで認識精度を向上させる．約50 万枚の画像を対象とした実験を行い，結果の考察と本手法の有用性を示 す． キーワード 画像処理，画像検索，特定物体認識，クラスタリング，局所特徴量1. は じ め に
近 年 ， ス マ ー ト フ ォ ン や デ ジ タ ル カ メ ラ の 普 及 に 伴 い ，画 像 デ ー タ を 取 り 扱 う こ と が 一 般 的 と な っ て き た ． 大 規 模 な 画 像 デ ー タ を 効 率 的 に 扱 う 方 法 は ， 画 像 認 識 と し て 広 く 研 究 さ れ て お り ， 大 き く 特 定 物 体 認 識 と 一 般 物 体 認 識 に 分 か れ る ． 特 に 特 定 物 体 認 識 は ， 人 物 認 識 や 欠 陥 検 出 ， 画 像 ラ イ ブ ラ リ の 構 築 ， 画 像 検 索 な ど 様 々 な 分 野 の 改 善 に つ な が る こ と か ら ， 本 研 究 で は 特 定 物 体 認 識 を 取 り 上 げ ， 改 善 に 取 り 組 む ． 特 定 物 体 認 識 で は ，SIFT 特 徴 量 [1]な ど の 局 所 特 徴 量 を 用 い ，Bag-of-Features[2]の よ う な ベ ク ト ル 量 子 化 手 法 を 用 い て 認 識 を す る の が 一 般 的 で あ る[3]．し か し ， 対 象 と な る 物 体 以 外 の 特 徴 点 と マ ッ チ ン グ す る こ と が 問 題 と な る ． そ こ で 本 研 究 で は ， あ ら か じ め 局 所 特 徴 量 を 出 現 位 置 に よ っ て ク ラ ス タ リ ン グ し ， 局 所 特 徴 量 の 出 現 位 置 の 分 布 に 基 づ い て 検 索 対 象 画 像 を 分 割 し ， 分 割 画 像 毎 に 特 徴 点 と の マ ッ チ ン グ を 行 う こ と で ， 誤 検 出 を 減 ら す ． 特 定 物 体 認 識 は ， 一 般 物 体 認 識 よ り 容 易 で あ る と さ れ て い る が ，交 通 道 路 標 識 の 認 識[4]や 機 械 用 基 板 に お い て の 物 体 認 識[5]な ど ，需 要 は 様 々 で あ り ，画 像 認 識 分 野 に お い て 幅 広 く 研 究 さ れ て い る ．[3]に お い て は ， 特 徴 点 の 位 置 に 着 目 し た 手 法 を 用 い て お り ， 対 応 点 と 基 準 と な る 特 徴 点 の 位 置 関 係 を 比 較 し ， 誤 検 出 を 減 ら す 工 夫 が な さ れ て い る ． 認 識 率 も 89%と 高 く ， 実 用 化 が 期 待 さ れ て い る ．2. 提 案 手 法
提 案 手 法 の 流 れ を 図1 に 示 す ． 動 画 か ら 抽 出 し た キ ー フ レ ー ム 画 像 か ら 特 徴 量 を 抽 出 し ， デ ー タ ベ ー ス に 登 録 す る ． ク エ リ 画 像 か ら も 特 徴 量 を 抽 出 し ， デ ー タ ベ ー ス に 登 録 さ れ た 特 徴 量 と の 比 較 を 行 う ． 提 案 手 法 で は 局 所 特 徴 量 を 画 像 か ら 検 出 し ， 特 定 物 体 の 写 っ て い る 画 像 の 検 索 を 行 う ． そ の 際 に ， 画 像 ご と に 類 似 度 を 決 め る 必 要 が あ る が ， 本 手 法 で は 物 体 領 域 を 分 割 す る た め に ， 検 出 し た 特 徴 点 を 出 現 分 布 に よ っ て ク ラ ス タ リ ン グ す る ． そ の 結 果 を 元 に 画 像 を 分 割 す る こ と で ， 一 つ の 画 像 を 局 所 特 徴 量 の 集 ま っ た 物 体 ご と に 分 割 す る(図 2)． ク ラ ス タ リ ン グ 手 法 と し て は ， デ ー タ マ イ ニ ン グ の 分 野 に お い て 広 く 用 い ら れ て い る K-Means++法 [6]を 用 い て 行 う ． 図 1:提 案 手 法 の 流 れ 図 2:ク ラ ス タ リ ン グ の イ メ ー ジ デ ー タ ベ ー ス に は 分 割 し た ク ラ ス タ ご と に 局 所 特 徴 量 を 登 録 す る ． 登 録 部 の イ メ ー ジ 図 を 図 3 に 示 す ． 局所 特 徴 量 に はSIFT 特 徴 量 を 用 い る た め ，画 像 数 ×ク ラ ス タ 数 ×128 次 元 で 構 成 さ れ る ． 図 3:デ ー タ ベ ー ス 登 録 の イ メ ー ジ 類 似 度 と し て ，SIFT 特 徴 量 の ユ ー ク リ ッ ド 距 離 の 合 計 を 計 算 し た 数 値 を 用 い る ． 最 終 的 な 結 果 と し て ， シ ス テ ム に よ っ て 類 似 度 が 高 い と 出 力 さ れ た 画 像 に 検 索 物 体 が 写 っ て い る か ど う か が 精 度 の 基 準 と な る ．
3. 評 価
3.1. 実 験 方 法 精 度 比 較 の た め ，2 種 類 の 実 験 を 行 っ た ． ・ 実 験 1(既 存 手 法 ) ク ラ ス タ リ ン グ を 施 さ ず ， そ の ま ま デ ー タ ベ ー ス に 登 録 し 1 枚 の 画 像 ご と に 類 似 度 を 求 め る ． ・ 実 験 2(提 案 手 法 ) ク ラ ス タ リ ン グ に よ る 画 像 分 割 を 行 い ， 分 割 画 像 ご と に 類 似 度 を 求 め る ． ク ラ ス タ リ ン グ 時 に 用 い るK-Means++法 に お い て は K=8，K=10 と し て デ ー タ ベ ー ス を 作 成 し た ．な お ，ク ラ ス タ の 個 数 は あ ら か じ め 予 備 実 験 を 行 い ， 比 較 的 分 割 が 上 手 く な さ れ る と 予 想 し た 個 数 を 用 い て 行 っ て い る ． 実 験 に 使 用 す る ク エ リ 画 像 は ， 以 下 の 4 種 類 と し ， 種 類 ご と に 写 り 方 と 大 き さ の 異 な る 4 枚 を 用 意 し ， 計 16 枚 の 画 像 を ク エ リ 画 像 と す る ．実 際 に 使 用 し た ク エ リ 画 像 4 種 類 の 例 を 図 4～ 図 7 に 示 す ． ク エ リ 画 像 に は そ れ ぞ れ マ ス ク 画 像 を 用 意 し ， ク エ リ 画 像 に マ ス ク 画 像 を 適 用 す る ． マ ス ク 画 像 内 か ら 得 ら れ た 特 徴 点 の み を 入 力 し ， 検 索 す る ． デ ー タ ベ ー ス 画 像 と し て ， 映 像 コ ン テ ン ツ の 解 析 や 検 索 の 高 度 化 を 目 的 と し た 競 争 型 プ ロ ジ ェ ク ト で あ る TRECVID[7]で 用 い ら れ る 動 画 を 短 い 時 間 で 分 割 し た 画 像 を 用 い る ．TRECVID で は 様 々 な タ ス ク が 与 え ら れ る が ， 本 手 法 で 用 い た デ ー タ ベ ー ス は イ ン ス タ ン ス サ ー チ タ ス ク で 実 際 に 使 用 さ れ る 動 画 デ ー タ ベ ー ス を 元 に 作 成 し て い る ．画 像 デ ー タ ベ ー ス の 枚 数 は お よ そ50 万 枚 と な り ， 対 象 と な る 物 体 が 写 っ て い て も ， 画 質 や 角 度 が 異 な っ て い る ． 図 4:ク エ リ 画 像 1 図 5:ク エ リ 画 像 2 図 6:ク エ リ 画 像 3 図 7:ク エ リ 画 像 4 評 価 方 法 と し て ， シ ス テ ム に よ っ て 類 似 度 が 高 い と 出 力 し た 上 位 200 件 の 再 現 率 と 適 合 率 を 元 に 評 価 を 行 う ． 使 用 し た 計 算 式 を 以 下 に 示 す ． 適 合 率 ％ =正 解 画 像 枚 数 検 索 結 果 中 200 ×100 再 現 率 ％ = 正 解 画 像 枚 数(検 索 結 果 中 ) 正 解 画 像 枚 数(デ ー タ ベ ー ス 中 )×1003.2. 実 験 結 果 全 画 像 の 再 現 率 と 適 合 率 の 平 均 値 を 図 8 に 示 す ． ま た ，4 種 類 の ク エ リ 画 像 ご と の 再 現 率 と 適 合 率 の 平 均 値 を 図 9， 図 10 に 示 す ． 図 8:適 合 率 と 再 現 率 の 平 均 図 9:再 現 率 の 平 均 図 10:適 合 率 の 平 均 従 来 手 法 と 提 案 手 法 を 比 較 す る と ，適 合 率 を 最 大 で 25％ ， 再 現 率 を 6％ 向 上 さ せ る こ と が で き た ． こ の こ と よ り ，従 来 手 法 と 比 較 し て 特 徴 点 の 誤 対 応 は 減 っ た と 考 え ら れ る ． 精 度 の 良 か っ た 例 と し て ，ク エ リ 画 像2 は 検 索 対 象 が は っ き り 写 っ て お り ，更 に 比 較 的 大 き な 物 体 で あ っ た た め 適 合 率 の 向 上 が 見 ら れ た ． 精 度 低 下 の 原 因 と し て は ，ク ラ ス タ が 検 索 対 象 そ の も の を 分 割 し た り ，ク ラ ス タ を 大 き く と り す ぎ て し ま っ た り と い っ た 例(図 11)が 見 ら れ た こ と が 原 因 と し て 考 え ら れ る ．現 シ ス テ ム で は K-means++法 で は ク ラ ス タ 数 は 静 的 に 決 め る し か な く ，更 に ク ラ ス タ 数 を 経 験 的 に 決 め て お り ，ク エ リ ご と に 調 整 し て い く こ と は で き て い な い ．以 上 の よ う な こ と が 精 度 低 下 の 理 由 で あ る と 考 え る ． ま た ，適 合 率 と 再 現 率 を プ ロ ッ ト し た グ ラ フ を 参 照 し ， 考 察 し て い く ． ク エ リ 画 像 2 の 結 果 を 図 12， ク エ リ 画 像 3 の 結 果 を 図 13 に 示 す ． 全 体 の 画 像 サ イ ズ に 対 し て ク エ リ の サ イ ズ が 比 較 的 大 き い ク エ リ 画 像2 に 関 し て ， ク ラ ス タ の サ イ ズ が 大 き い K=8 の 結 果 が 優 れ て い る 事 が 分 か る ．ま た ，ク エ リ サ イ ズ の 小 さ い ク エ リ 画 像 3 の 結 果 を 見 て み る と ，ク ラ ス タ の 細 か い K=10 の 結 果 の 方 が 優 れ て い る 事 が 分 か る ． こ の よ う な 傾 向 が ク エ リ 画 像 全 体 と し て 見 ら れ る こ と か ら ，ク ラ ス タ の 大 き さ が 検 索 対 象 の 大 き さ に 比 例 し て い る と 考 え る ． ま た ，ク エ リ 画 像 ご と に 精 度 が 大 き く 異 な っ て い る が ，特 徴 量 の 性 質 上 ク エ リ の 大 き さ や 向 き ，画 質 の 差 に 大 き く 依 存 し て い る た め ，色 情 報 の 追 加 や 特 徴 量 の 見 直 し を 行 う 必 要 が あ る ． 図 11:分 割 ミ ス の 例 図 12:ク エ リ 画 像 2 の 結 果 図 13:ク エ リ 画 像 3 の 結 果
4. 改 善 手 法 の 提 案
上 記 の 問 題 点 を 解 決 す る た め ，階 層 的 ク ラ ス タ リ ン グ 手 法 で あ る 完 全 連 結 法 を 用 い て ク ラ ス タ リ ン グ を 行 い ， 実 験 を 行 っ た ． 4.1. 階 層 的 ク ラ ス タ リ ン グ 階 層 的 ク ラ ス タ リ ン グ は ，ユ ー ク リ ッ ド 距 離 や ミ ン コ フ ス キ ー 距 離 な ど の 距 離 尺 度 を 類 似 度 と し ，類 似 度 の 高 い 順 に 融 合 し て い く ク ラ ス タ リ ン グ 手 法 で あ る ． 融 合 の 手 法 に 関 し て も ，ク ラ ス タ 内 の メ ン バ ー 間 距 離 を 元 に 融 合 す る 最 近 隣 法 や 最 遠 隣 法 ，全 て の デ ー タ 対 間 の 距 離 の 平 均 を 用 い て 融 合 し て い く 群 平 均 法 が あ る ． 最 終 的 に は ク ラ ス タ が 1 つ に な る ま で 処 理 を 施 し て い き ，融 合 の 過 程 が デ ン ド ロ グ ラ ム と し て 得 ら れ る ． デ ン ド ロ グ ラ ム(図 14)の 枝 の 高 さ や ク ラ ス タ の 個 数 を 指 定 し て 区 切 る 事 で 処 理 の 途 中 結 果 も 得 ら れ る ． K-means の よ う な 非 階 層 的 ク ラ ス タ リ ン グ で は ，デ ー タ 全 体 の バ ラ ン ス を 考 慮 し て ク ラ ス タ リ ン グ を 行 う の に 対 し て ，階 層 的 ク ラ ス タ リ ン グ は デ ー タ 間 の 距 離 を よ り 重 視 し て 分 割 で き る と 考 え ，実 際 に 予 備 実 験 を 行 っ た ． 図 14:デ ン ド ロ グ ラ ム の 例 4.2. 評 価 実 験 3 章 で 使 用 し た 画 像 デ ー タ ベ ー ス に 対 し て 以 下 の 実 験 を 行 い ，異 な る ク ラ ス タ リ ン グ 手 法 の 結 果 の 比 較 を 行 う ． ・ 実 験 1(既 存 手 法 ) ク ラ ス タ リ ン グ を 施 さ ず ， そ の ま ま デ ー タ ベ ー ス に 登 録 し 1 枚 の 画 像 ご と に 類 似 度 を 求 め る ． ・ 実 験2(非 階 層 的 ク ラ ス タ リ ン グ ) K-means++法 を 用 い て ク ラ ス タ リ ン グ を 行 う ． ・ 実 験3(階 層 的 ク ラ ス タ リ ン グ ) 完 全 連 結 法 を 用 い て ク ラ ス タ リ ン グ を 行 う ． 階 層 的 ク ラ ス タ リ ン グ 手 法 に お い て ，最 近 隣 法 の よ う な 手 法 は 一 定 方 向 に ク ラ ス タ が 長 く な っ て し ま い ， チ ェ ー ン 状 の ク ラ ス タ が 形 成 さ れ や す く な る こ と が 分 か っ て い る た め ，今 回 は ク ラ ス タ 融 合 の 基 準 と し て ク ラ ス タ 間 の 最 遠 隣 距 離 を 用 い る 完 全 連 結 法 を 用 い ， 距 離 尺 度 に は ユ ー ク リ ッ ド 距 離 を 用 い た ．非 階 層 的 ク ラ ス タ リ ン グ 手 法 に は K-means++法 を 用 い た ． ま た ， 使 用 す る ク エ リ 画 像 に 関 し て も 3 章 と 同 じ も の (ク エ リ 画 像 1～ 4)を 用 い て 比 較 を 行 う ． K-means++法 に お け る ク ラ ス タ 数 は ，ク エ リ 画 像 3 に お い て 最 も 精 度 が 優 れ て い た 8 個 を 指 定 し た ．完 全 連 結 法 に お け る ク ラ ス タ 数 は ，最 遠 隣 距 離 の 和 に 閾 値 を 設 け ，閾 値 を 超 え た 時 点 で 融 合 を 止 め る こ と で 決 め る ． 評 価 に 関 し て は ，3 章 で 行 っ た 実 験 と 同 じ 式 を 用 い て 計 算 し た 適 合 率 と 再 現 率 を 元 に 行 う ． 4.3. 実 験 結 果 全 画 像 の 再 現 率 と 適 合 率 の 平 均 値 を 図 15 に 示 す ． ま た ，4 種 類 の ク エ リ 画 像 ご と の 再 現 率 と 適 合 率 の 平 均 値 を 図 16， 図 17 に 示 す ． 結 果 を 見 る と ，比 較 的 階 層 的 ク ラ ス タ リ ン グ の 結 果 が 良 く ，上 手 く 分 割 で き て い る こ と が わ か る ．階 層 的 ク ラ ス タ リ ン グ の 中 で も 完 全 連 結 法 は 最 遠 隣 距 離 を 元 に ク ラ ス タ リ ン グ す る た め ，距 離 が 離 れ た ク ラ ス タ が 生 成 さ れ や す い ．精 度 が 良 い 事 か ら も ，ク ラ ス タ が 物 体 を 分 割 す る よ う な 例 は 完 全 連 結 法 を 適 用 す る こ と で 解 消 さ れ た と 考 え る ． 非 階 層 的 ク ラ ス タ リ ン グ は ， 分 散 や 重 心 を 元 に ク ラ ス タ リ ン グ を 行 っ て お り ，全 体 の バ ラ ン ス を 考 慮 し な が ら ク ラ ス タ リ ン グ す る た め ，離 れ た オ ブ ジ ェ ク ト で あ っ て も 同 じ ク ラ ス タ で あ る と 判 断 し て し ま う 事 が 多 く あ っ た(図 18)．特 に K-means 法 は 超 球 に か つ 各 ク ラ ス タ が 同 じ サ イ ズ に な る よ う に ク ラ ス タ リ ン グ す る と う い 性 質 が あ り ，K-means++法 で も そ の 性 質 は 維 持 し た ま ま で あ る た め ，イ メ ー ジ 通 り に ク ラ ス タ リ ン グ で き な い 事 が 多 か っ た こ と が 精 度 低 下 の 原 因 で あ る と 考 え る ． ま た ，今 回 の 実 験 で も 経 験 則 的 に 閾 値 を 決 め る 必 要 が あ る た め ， 引 き 続 き 十 分 な 検 討 が 必 要 で あ る ． 図 15:適 合 率 と 再 現 率 の 平 均 図 16:再 現 率 の 平 均図 17:適 合 率 の 平 均 図 18:分 割 方 法 の 違 い
5. ま と め
特 定 物 体 認 識 手 法 と し て ，局 所 特 徴 量 の ク ラ ス タ リ ン グ に よ っ て 画 像 を 分 割 し ，分 割 し た 画 像 に 対 し て 特 定 物 体 の 検 索 を 行 い ， 従 来 手 法 と の 比 較 を 行 っ た 所 ， 精 度 の 向 上 が 見 ら れ た ．ク ラ ス タ の 大 き さ と 検 索 対 象 の 大 き さ に 相 関 が 表 れ る 傾 向 に あ る 事 も 示 し た ． ま た ，階 層 的 手 法 と 非 階 層 的 手 法 の 比 較 と し て 実 験 を 行 い ， 階 層 的 手 法 の 可 能 性 も 示 し た ． 今 後 は ク ラ ス タ 数 の 動 的 決 定 手 法 に 関 し て 更 な る 検 討 を 行 う と 共 に ，色 情 報 の 追 加 な ど の 特 徴 量 に 関 す る 考 察 を 深 め る 事 で ，よ り 精 度 の 高 い 認 識 手 法 を 目 指 し た い ．参 考 文 献
[1] D.G.Lowe, “Object recognition from local scale-invariant features”, Proc.of IEEE International Conference on Computer Vision (ICCV), pp.1150-1157, 1999.
[2] J.Zhang, M.Marszalek, S.Lazebnik and C.Schmid， “Local features and kernels for classification of texture and object categories: A comprehensive study”, International Journal of Computer Vision ， 2006. [3] Z.Zhao, Y.Zhao, Y.Hua, W.Wang, D.Wan, G.Jia, Z.Li, F.Su and A. Cai: “Bupt-mcprl at trecvid 2012”, TRECVID 2012 Workshop Notebook, 2012. [4] 高 木 雅 成 , 藤 吉 弘 亘 , “SIFT 特 徴 量 を 用 い た 交 通 道 路 標 識 認 識”, 第 13 回 画 像 セ ン シ ン グ シ ン ポ ジ ウ ム SSII07, LD2-06, 2007. [5] 三 吉 建 尊 ， 越 野 亮 ， 木 村 春 彦 , “HOG と Bag of Keypoints を 用 い た 工 作 機 械 用 制 御 盤 内 に お け る 物 体 認 識 に 関 す る 研 究”， 第 27 回 フ ァ ジ ィ シ ス テ ム シ ン ポ ジ ウ ム 講 演 論 文 集 ，pp.1183-1188, 2011．
[6]Arthur,D. and Vassilvitskii,S. ， ”K-means++:the advantages of careful seeding”， Proc. of the eighteenth annual ACM-SIAM symposium on Discrete algorithm, 1027-1035, 2007
