Bag-of-keypoints による カテゴリー認識 第 14 回画像センシングシンポジウム (SSII2008) 2008 年 6 月 13 日 電気通信大学 柳井啓司 情報工学科
2 アウトライン 1. イントロダクション 2. Bag-of-keypoints アプローチ その具体的な方法の詳細 3. Bag-of-keypoints アプローチの拡張 位置情報, 色情報の利用 4. 確率的言語モデルの画像への適用 5. 今後の方向 1. シーンの階層的理解, コンテキストの利用 2. 言語階層との対応
1. イントロダクション 参考文献 柳井啓司. 一般物体認識の現状と今後. 情報処理学会論文誌 : コンピュータビジョン イメージメディア, Vol.48, No. SIG16 (CVIM19), pp. 1-24, 2007.
6 一般物体認識とは? 一般的な 実世界画像の認識 デジカメや Web の画像を自動認識. 画像内容を言語 ( 記号 ) で記述. 意味理解. クマ ( 草の上の ) トラ ( 草を食べる ) ゾウ 静止画像に対して, その中に含まれる物体もしくはシーンの一般名称 ( カテゴリー ) を認識 究極的には人間以上にあらゆる画像を認識
物体の認識 空 7 建物 / ビル 木 / 桜 木 / 桜 信号機 木 / 桜外灯 建物バス 自転車 道路 自動車 / バン
シーン ( コンテキスト ) 認識 場所について 屋外 街 以下は 固有名詞 日本 東京都多摩市 聖蹟桜ヶ丘 京王百貨店 緯度 :N35.653488 経度 :E139.44564 時間について 春 4 月 日中 晴天... 8
9 一般物体認識の困難性 認識対象が多様 ( カテゴリー内変化が大 ) 同一種類 ( カテゴリー ) の物体でも形は様々. 変形も. 撮影時の条件が多様 ( 視点位置, 向き, 変形, スケール, 照明 ( 天候 ), 背景, オクルージョン ) 認識対象が多い.( カテゴリー数が多い.) 辞書に出ている名詞の数だけある! 数万? 何を認識するべきか? レベルは? 動物 or ライオン? 様々な ライオン
カテゴリー内変化 (1): 10 いろいろな 椅子
カテゴリー内変化 (1): 11 いろいろな 椅子 どんな 椅子 が認識できればいい? (1) 世の中の 椅子 すべて? (2) 典型的なもののみ? (3) 座る 機能を提供する物体すべて?
カテゴリー内変化 (2): 12 いろいろな視点からの見え方 [P.Yan, S. M. Khan and M. Shah: 3D Model The University based of Object Electro-Communications Class Detection in An Arbitrary View, Tokyo, CVPR JAPAN 2007] (UEC) より
カテゴリー内変化 (2): 13 いろいろな視点からの見え方 どこからみた バイク が認識できればいい? (1) すべての方向? 360 度. 下からも上からも? (2) 典型的な見え方のみ? 真横, 斜め前方. canonical view (3) 状況によって異なる. 地上からみた場合. 高層ビルや飛行機から. [P.Yan, S. M. Khan and M. Shah: 3D Model The University based of Object Electro-Communications Class Detection in An Arbitrary View, Tokyo, CVPR JAPAN 2007] (UEC) より
カテゴリー数が多い : 14 多様なカテゴリー
カテゴリー数が多い : 15 多様なカテゴリー 一体, 何種類認識できればいい? (1) 世の中の物体すべて! シーン, イベントも製品やランドマークなどの固有名詞も! basic-level/entry-level category (2) 典型的なもの 1000 種類! 典型的 って? (3) 用途に応じて. 花だけ. 食べ物だけ.
2 種類の認識 :Identification と 16 classification( カテゴリー分類 ) Identification : DB 中の特定物体の検出. モデル物体は点で表現. クラス内変動はなし. 特定の 椅子 DB 中のもっとも近い画像を探す. Classification : 物体の分類 ( カテゴリ / クラス ) を区別. 分類名 ( 一般名称 ) で認識. クラス内変動大. すべての 椅子 認識カテゴリーの定義が難しい. 椅子 とは何か? 厳密な定義がない!! 人間は classification が得意. 椅子 という概念に対応した物体の認識 計算機は identification の方が得意. 一般物体認識では, classification が目的. The chairs 特定の 椅子 の認識 A chair
17 厳密な定義がない認識カテゴリー : どのような 認識 をするべきか? 多くの人間が行う認識 みんなが机だと思うものは机と認識して欲しい. 日本の家 と アフリカの家. 文化による認識対象の違い. 基本認識レベル (E.Rosch,1976) で物体を認識 ぱっと見た時に最初に思い付く ( 一般 ) 名称. 机 ライオン 犬 自動車 アザラシ 形状の類似性 人工物 動物 家具 乗り物 ぽち タマちゃん 人間のような認識 を行うには? 概念 机 机モデル 画像 モデル化照合 一般的な 事例から, モデルを学習により構築. 特定物体認識 一般物体認識においては学習データ構築も重要.
19 一般画像認識の歴史 研究者の知識がすべて! 70 年代線画解釈.( 画像処理が中心.) 80 年代前半知識ベース型システム. 人手によるルール記述に一般性がない. 知識爆発. 80 年代後半 3 次元の復元. モデルベースト. Identification のみ. 形状既知. 実世界でうまくいかない. 90 年代学習による認識. 顔画像や identification 中心. 顔画像認識 (Eigenface) の成功. 固有空間法. 画像 DBにおける画像の意味的分類. 00 年代局所特徴 + 機械学習により大きく進歩 90 年代までは, 画像認識においてはマイナーな研究分野.
20 2000 年以降の発展突然ブレイク! 2000 年 Constellation model ( 確率モデル ) 2001 年確率手法による単語と画像の対応付け 2002 年 Word-image translation model 2003 年 Video Google (image search by visual words) 2004 年 Bag-of-keypoints(BoK)+SVM 2004 年 Caltech101 (101 カテゴリーのデータセット ) 登場 2005 年 ~ BoK + probabilistic graphical model (PLSA, LDA, HDP, their modifications) BoK + SVM with modified kernel BoK + MRF for semantic region segmentation 2007 年 Caltech256 (256 カテゴリーのデータセット ) 登場
2.Bag-of-keypoints アプローチ 参考文献 [Low99] Lowe, D.G.: Object recognition from local scale invariant features, Proc. of IEEE International Conference on Computer Vision, pp. 1150 1157 (1999). [Siv03] Sivic, J. and Zisserman, A.: Video Google: A Text Retrieval Approach to Object Matching in Videos, Proc. of IEEE International Conference on Computer Vision, pp.1470 1477 (2003). [Csu04] Csurka, G., Bray, C., Dance, C. and Fan, L. Visual categorization with bags of keypoints, in Proc. of ECCV Workshop on Statistical Learning in Computer Vision, pp. 59 74 (2004).
frequency 22 全体特徴から局所特徴へ 従来の認識 : 認識対象の全体を利用 固有空間法, 領域分割を用いた方法 オクルージョンや変形に弱い. Part-based 手法の登場 : 複数の部分の組み合わせで認識 局所パターンの分布に基づく認識 (bag-of-keypoints) visual words
局所特徴量による 23 identification SIFT [Low99] 回転およびスケール変化に丌変な局所特徴量ただし,D.Lowe が想定したのは identification Video Google [Siv03] SIFT 特徴ベクトルをベクトル量子化し, 画像を visual words の集合とみなす. テキスト検索の手法 (Google) を応用し, 高速画像検索を実現. ( 同一部分の検索 )
Bag-of-keypoints [Csu04]: 24 visual word の classification への適用 Visual words の集合として画像を表現 Visual words のヒストグラムを画像特徴とする 単語出現頻度によりテキストを表現する方法の bag-of-words の考え方を画像に応用. 語順を無視するのと同様に, 位置を無視. Bag-of-keypoints によって表現された特徴ベクトルを Naive Bayes, SVM などの機械学習手法で分類. テキスト分類と同じ! Bag-of-visual-words (BoVW), Bag-of-features (BoF) とも言うことがある.
frequency Bag-of-keypoints のアルゴリズム : bag-of-keypoints 表現への変換 画像を visual word の出現頻度ヒストグラムで表現 1. 各画像について, 数千個の特徴点を抽出. 2. SIFT 記述子により特徴点周辺パターンを SIFT 特徴ベクトルとして抽出. 3. 予め求められた visual words (codebook) に基づいて SIFT 特徴ベクトルをベクトル量子化. 4. 画像毎にヒストグラムを作成. SIFT 法 ( 特徴点抽出 + 記述 ) visual words
特徴点のサンプリングの方法 主な 3 つの方法 SIFT 法の方法 Difference of Gaussian(DoG) sparse sampling と呼ぶ Random sampling Grid sampling dense sampling と呼ぶ DoG (sparse) random(dense) grid(dense) カテゴリー分類 (classification) においては, パターンのない部分の情報も重要.
Visual words の求め方 学習画像 ( 正例, 負例 ) を用意し,SIFT 特徴ベクトルを全画像から抽出 ( 枚数が多い場合は, ランダムサンプリング ) k-means クラスタリングを実行 各クラスタの中心が visual words v v i i v i v i v i v i v i v i v i v i SIFT vectors Visual words は, 代表的な局所パターンに相当する.
frequency Bag-of-keypoints 表現 28 Visual words の出現頻度 ( ヒストグラム ) によって画像を表現... Visual words ( 数百 ~ 数千個 ) 次元は, 数百 ~ 数千次元. スパースなベクトルになる.
Bag-of-keypoints 表現を用いた 30 画像認識 あとは, 多次元ベクトルの分類問題 最初の論文 [Csu04] では, 以下の 2 つの手法で実験 SVM (support vector machine) Naive Bayes 従来手法の結果を大きく改善 例 :Web 画像の分類 10 種類のキーワードについて, 平均適合率 従来手法 ( 領域分割 +GMM): 73.5% BoK + SVM : 82.4%
3.Bag-of-keypoints の改良 参考文献 [Laz06] Lazebnik, S., Schmid, C. and Ponce, J.: Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories, Proc. of IEEE Computer Vision and Pattern Recognition, pp.2169 2178 (2006). [Var07] M. Varma and D. Ray. Learning the discriminative powerinvariance trade-off. In Proc. of IEEE International Conference on Computer Vision, pp.1150 1157 (2007). [Rab07] A. Rabinovich, A.Vedaldi, C. Galleguillos, E. Wiewora and S. Belongie: Objects in context, In Proc. of IEEE International Conference on Computer Vision, pp.1150 1157 (2007).
Bag-of-keypoints の問題点と 32 提案された解決法 ヒストグラムのため位置情報を利用しない ブロック分割して, サブヒストグラムを作成 Spatial pyramid kernel SIFT を利用するので, 色情報を利用しない RGB や HSV, Lab など,3 つの色成分ごとに SIFT で特徴抽出 (128 次元 3) Color SIFT 色情報や形状情報, テクスチャ情報を統合 重み付き線形和カーネルによる統合 どこに物体があるか分からない. 物体検出.
位置情報の導入 Spatial pyramid kernel [Laz06] BoK をグリッド分割して階層的に local BoK を作成 各レベルごとにヒストグラムインターセクションを求め, レベルごとに異なる重みで統合.SVM のカーネル関数とする. l I I I I Y X I Y X I Y X k l l L l l L L : Histogram intersetion in level 2) L (in case of 2 1 4 1 4 1 ), ( 2 1 ), ( 2 1 ), ( 2 1 0 1 1 0 ), ( 2 Y X I ), ( 1 Y X I ), ( 0 Y X I
34 色情報の利用 :Color SIFT 各特徴点について RGB(HSV, Lab) の 3 つの SIFT ベクトルを計算し,1 つに結合. R v R G B v G v B v RGB Color SIFT ベクトル (128*3 次元 )
他の種類の特徴との統合 35 [Var07] (linear combination of kernels) 多種類特徴を統合する SVM のカーネル関数 重み付き線形和カーネル関数による, Bag-of-keypoints, 色, 形の統合. + 重みの自動推定. 各特徴のカーネルをとすると, 統合カーネルは, ただし, d i 1,.., N ) は最適化問題を解いて求める. i( k カーネルの重みを求めるのは, 機械学習の研究では近年よく研究されている. 認識精度を上げるには,BoKのみでなく, 様々な特徴量を カテゴリーに応じて選択的に利用することが重要 Tokyo, JAPAN.(UEC) Caltech-101, 256 の分類で, 最高の約 90%, 約 60% を達成
[Var07] 特徴重みの推定結果 36 (1-vs-1 の場合 ) [Var07] より図を引用 両方とも黄色 色の記述子はいらないしかし形状は有効重み形状 :3.94 色 :0 テクスチャ :0 クロッカスは形状のクラス内の変化が大きい 形状に識別力がない色は比較的識別力がある重み形状 :0.42 色 :2.46 テクスチャ :0 2 つを分ける主な特徴がない 3つの特徴をバランス良く組み合わせる必要がある重み形状 :1.48 色 :2.00 テクスチャ :1.36
対象の検出への BoK の利用 : 37 領域分割との組み合わせ [Rab07] 領域分割し, 領域毎に BoK ベクトルを作成, 領域毎に分類. 最後に共起関係より修正. [Rab07] より図を引用 領域分割は, Normalized Cuts. を利用. 共起関係は確率モデル (MRF) によって表現.
4. 確率的テキスト 解析手法の導入 参考文献 [Hof99 ] T. Hofmann, Probabilistic Latent Semantic Indexing, Proc. of ACM SIGIR (1999). [Ble03] D. Blei, A. Ng, and M. Jordan. Latent Dirichlet allocation. Journal of Machine Learning Research, No.3, pp.993 1022, (2003). [Teh06] Y. Teh, M. Jordan, M. Beal, and D. Blei. Hierarchical Dirichlet Processes. Journal of the American Statistical Association, Vol.101, No.476, pp1566-1581 (2006).
39 テキスト解析手法の導入 文書 : 単語の集合 bag-of-words 画像 :VW の集合 bag-of-visual-words Video Google [Siv03] キーワード検索手法 ( 転置インデックス ) の画像検索への応用 確率トピックモデルの画像への応用 : 元々はテキスト解析用 bag-of-words を前提とする PLSA (Probabilistic Latent Analysis) LDA (Latent Dirichlet Allocation) HDP (Hierarchical Dirichlet Process)
高次元でスパースな BoK 向けの確率的 クラスタリング : PLSA と LDA テキスト解析向けの確率トピックモデル Bag-of-words 表現された文書を確率的にトピック分類する トピック数は, 事前に指定する.K-means と同じ. トピックを z, 文書 ( 画像 ) を d とすると, 各文書について P(z d) が求まる Probabilistic Latent Semantic Analysis ( ヒストグラムは離散なので ) 混合多項分布によるモデル P ( w, d) P( d) p( w z) P( z d) を EM でパラメータ推定 z Latent Dirichlet Allocation ( 判別分析ではありません!) PLSAを改良. 多項分布の代わりに混合ディリクレ分布. オーバーフィッティングを解消.
例 : Mountain 10 topics 正例 負例 GMM による認識と同じことができる P(Mountain topic) P(pos topic) 0.112 0.661 0.167 0.186 0.407 0.023 0.761 0.334 0.949 0.987
5. 今後の方向 1. シーンの階層的理解, コンテキストの利用 2. 言語階層との対応
コンテキストの利用 : 47 人間は 常識 として持っている知識 共起関係 : 共起の強さを確率で表現 机 ライオン 階層的認識 : シーン認識 + 物体認識 (+ 領域分割 ) 風景 part-of 関係 ディスプレイキーボード本棚床 草原 空 自動車 道路 机 本棚 室内 キーボード サバンナ ディスプレイ 床 ライオン 屋外 草原 空 路上 自動車 道路
言語の階層的分類 ( タクソノミー ) との関係 物体 member-of 関係 動物 植物 無生物.. ほ乳類 脊椎動物 鳥類 自然物 人工物 どのレベルで認識するか? バク イノシシ ライチョウ カメラ
49 解決すべき課題 多種類化と認識クラス ( カテゴリー ) の決め方 1000 種類分類はもうすぐ実現.1 万種類も数年先? どうやって, 有用な 1000 種類選ぶか? Caltech-101 は, かなり偏っている. 認識し易い. クラス内変化への対応. 例えば, バイクは, 横や斜め前方から見た場合に対応. 真上, 真下は? 壊れたバイクは? どこまで対応すべきか? 椅子 は難しい. 細分化したサブクラスで認識? どこまでできれば, 実用化できるか? 機械翻訳の例 : 翻訳を前提に文章を書けば使える 認識し易いように撮影すれば, 現時点でも実用化可能?
おわり
パネル (1): 51 高精度化にむけて何をすべきか 101, 256 種類分類 : 約 90%, 約 60% を達成 画像全体を分類する場合は, 既にかなりできている. 画像の部分認識 ( 対象物体の検出 ) はまだまだこれから. 良質な知識 ( 学習画像 + コンテキスト ) を大量に用意 自動 テキスト情報を手がかりに Web から収集. Flickr, Youtube などのタグを利用 手動 一般ユーザにフィードバックしてもらう. Game であつめる (Human computation by CMU Prof. L.Ahn). 複数種類の特徴量の組み合わせ もちろん, 分類アルゴリズムの改良
パネル (2): 52 未解決問題 (1) 多種類化と認識カテゴリーの決め方 何種類認識できればいいのか? 1000 種類? 応用次第?? 応用を想定しない一般物体認識システムも実現したい! 人間の高次視覚機能の計算機による実現のためには何種類? 有用な一般認識システムを実現するには, どのように 1000 種類選ぶべきか? クラス内変化への対応. 例えば, バイクは, 横や斜め前方から見た場合に対応. 真上, 真下は? 壊れたバイクは? どこまで対応すべきか? どこまでできれば, 実用化できるか? 機械翻訳の例 : 翻訳を前提に文章を書けば使える. 認識を前提に撮影すれば, そこそこ使えるのでは?
パネル (2): 53 未解決問題 コンテキストの利用 共起関係 相対位置関係, 相対スケール,( 重力に対する ) 支持関係 背景と前景の関係 一般動作 イベント認識 動画像 / 静止画像からの動詞の認識 シーン認識, 物体認識との組み合わせ. コンテキストの利用. ライオンが草を食べている. 人間が草を食べている. 草を刈っている.
パネル (3): 54 一般物体認識のアプリケーション 画像をテキストへ変換する技術と考えると.. すでにある画像を認識する場合 写真へのキーワード付け, 自動整理アルバム Web 画像検索の精度向上, 言葉による画像検索 認識を前提に撮影する場合 撮影条件がよければ, かなり認識可能なので, 現時点の技術で, アイデア次第で実用化可能!? カメラ付き携帯による画像による情報入力 画像で調べる Web 検索, 百科事典 /wikipedia 検索 自動ブログ / 日記生成,
パネル おわり