Microsoft PowerPoint - sm13_lect03_ all.pptx

Transcription

1 SIFT 特徴 : 顕著点による局所特徴量 意味的マルチメディア処理第 A2 回 (2013 年 10 月 15 日 ) ー視覚メディアの分析, 分類, 比較, 検索 ( 第 1 回 ) ー 教員 : 大渕竜太郎 2013/10/28 意味的マルチメディア処理特論 ( 視覚メディア ) 1 Scale Invariant Feature Transform (SIFT) David Loweによる 顕著な特徴点を抽出し, その点で局所特徴量を計算. 特許あり. 特徴 画像の線形変換に対し頑強 不変性の実現 スケール ( 大きさ ) 不変性 多重解像度解析 線形 ( 回転, スケール, 軽い射影など ) 変換不変性 顕著点の局所特徴 特徴量 Difference of Gaussian (Gabor 特徴量 ) などから抽出 向き, スケール, 位置,... おのおの128 次元ベクトル x 特徴点の数 SIFT 処理のステップ 1. スケールスペースで極値を検出 Difference-of-Gaussians (DoG) を利用. 2. キーポイント ( 顕著点 ) の決定 不安定な顕著点を消去. 3. 明度勾配の向きの検出 顕著点の近傍 ( 位置とスケールについて ) の画像パッチを用いる. 4. 顕著点における記述子の計算 顕著点の近傍 ( 位置とスケールについて ) における輝度勾配の向きとスケールを,128 次元ベクトルで記述. SIFT 特徴 特徴点抽出 元画像をガウスぼかしして多重解像度画像群を作成. 複数のσ 値でフィルタ. スケールスペースの極値を求める. 特徴量計算 特徴点ごとに特徴量を計算する. 位置, スケール, 特徴の向き,... 3/50

2 SIFTにおける多重スケール空間とDoG おける多重 ケ ル空間 SIFTにおける多重スケール空間 おける多重 ケ ル空間 ボケ小 Gaussぼかし ボケ大 大スケール画像 次のオクターブ ダウンサンプリング 次に詳細な画像群 間引き して縮小 ボケ小 より大スケールの 変化のみ残す ボケ大 ダウン サンプリング 1辺の画素数1/2 画像 画素数 Gaussぼかし 画像の画素数1/4 小スケール画像 Gaussぼかし 最初のオクタ ブ 最初のオクターブ Gaussぼかし 最も詳細な画像群 Gaussぼかし ダウン ダウ サンプリング ダウン サンプリング ダウン サンプリング ボケ小 Scale space p スケール スペース ケ ル SIFTにおける多重スケール空間とDoG おける多重 ケ ル空間 スケール 解像度 の階層 ピラミッド ケ 解像度 階層 ピ ド ぼかし low-pass filtering)とダウンサン プリング 画素の間引き で生成 プリング 画素の間引き で生成 ボケ大 大スケール画像 次のオクターブ ダウンサンプリング 次に詳細な画像群 間引き して縮小 ボケ小 より大スケールの 変化のみ残す ボケ大 Gauss ぼかし ぼ 1辺の画素数1/2 画像の画素数1/4 画像 画素数 Gaussぼかし 間引き 間引き 小スケール画像 Gaussぼかし 最初のオクタ ブ 最初のオクターブ Gaussぼかし 最も詳細な画像群 Gaussぼかし ボケ小 間引き 7/50 ボケ大

3 Difference-of-Gaussian DoG ガウス関数の差分 Gaussフィルタ ィルタ ガウス関数の差分は2階微分として働く Gauss ガウス フィルタ Gaussian low-pass filter ガウス低域通過フィ ルタ 等とも呼ばれる x2 g ( x) exp i2 j2 g (i, j ) exp 2 2 2次元だと 縦横で大きさの違うGaussianも ある 低域を通過 より低域を通過 local.wasp.uwa.edu.au/~pbourke/other/functions/ 2013/10/28 9 Difference-of-Gaussian DoG は 帯域通過フィルタ Gaussぼかしは低域通過フ ィルタ その差分 difference は帯 域通過 band-pass フィル タになる 通過度 通過度 通 特定の周波数 細かさ 粗さ またはスケール の成分だけ を抽出できる を抽出できる 10/50 SIFTにおける多重スケール空間とDoG おける多重 ケ ル空間 ボケ大 大スケール画像 次のオクターブ ダウンサンプリング 次に詳細な画像群 間引き して縮小 ボケ小 より大スケールの 変化のみ残す ボケ大 1辺の画素数1/2 画像の画素数1/4 画像 画素数 Gaussぼかし 小スケール画像 Gaussぼかし 最初のオクタ ブ 最初のオクターブ Gaussぼかし 最も詳細な画像群 Gaussぼかし ボケ小 周波数 細かさ 11/50 周波数 細かさ 特定の帯域を通過 特定スケールの輪郭を抽出

4 SIFT 顕著点検出 Scale-space における極値検出 スケール スケールスペース ( 多重解像度ピラミッド ) 内で,DoG 画像が極小値 (Minima), 極大値 (Extrema) をとる点を探す : 1) あるスケールで極値を検出. 2) その極値が近くのスケールでも ( 安定に ) 存在するかを, 3 近傍のスケールでチェック.( 合計,3x3x3-1=26 近傍 ) 安定 な顕著点のみを選別. 雑音, 照明の変化, 等の影響を受けにくい, 安定したもの. 閾値を決めて切り捨てる. 高解像度 Gauss ボケ小 Gauss ボケ大 多重解像度の DoG 画像群 13/50 低解像度 14/50 顕著点ごとの特徴の記述子の計算 顕著点ごとの特徴の記述子の計算 明度勾配の強さ 向き キーポイントごとに, 例えば8x8の領域で, 以下を計算 明度勾配の向き 領域内の向きヒストグラムで最大の向きが, その記述子の向き 明度勾配のスケール 明度変化の影響領域の大きさ 記述子は128 次元のベクトル 顕著点周りに 16x16 の窓を設定. その窓を, 計 16 個の 4x4 の小窓に分割. 各小窓で,88 区間 ( 方向 ) の向きヒストグラムを計算. 明度勾配を 8 方向でヒストグラム化. ヒストグラムと勾配の強度を,16 個の小窓全体で補間 最も勾配が強く, 頻度の高い向きが, その顕著点の記述子の向き. 記述子は,16 個の小窓 8 方向 = 128 次元ベクトル. キーポイント 16x16 画素の窓 SIFT 記述子は 8 方向 16 小窓 = 128 次元ベクトル 主要な勾配方向 15/50 16/50

5 顕著点ごとの特徴の記述子の計算 Example 顕著点周りの 16x16 の窓で記述子を計算. 4x4 画素の小窓ごと,8 方向の向きヒストグラムを計算. 顕著点は ( 有る程度 ) 幾何変換不変 顕著点周りの 16x16 画素の窓 8 方向 16 小窓 =128 次元ベクトル キーポイント 17/50 主要な勾配方向 18/50 SIFT 特徴量例 1 グレースケール画像から計算. SIFT 特徴量例 2 特徴点 160 個 特徴点 1,091 個 矢の元が特徴点 長さがスケール 向きが特徴の向き 特徴点 230 個

6 SIFT特徴 マッチングの例(1) SIFT特徴量 マッチングの例 Ｄｄｄ 異なる画像だが 十分類似 ほぼ成功 異なる画像だが 十分類似 ほぼ成功 3次元モデルの深さ画像から抽出した SIFT特徴 (1) 多重解像度の 中心軸 もある程度捉える 特徴 = スケ スケール ル + 向き 窪みの特徴も取る どことマッチングしていいかわ からない 3次元モデルの深さ画像から抽出した SIFT特徴 (1)

7 SIFT 特徴量の例 OpenCV における局所特徴 OpenCV には SIFT もどき の SURF がある! うたい文句は, SIFTより高速で,SIFTなみの性能 Herbert Bay, Tinne Tuytelaars, Luc Van Gool, "SURF: Speeded Up Robust Features", Proceedings of the 9th European Conference on Computer Vision, Springer LNCS volume 3951, part 1, pp , cvextractsurf() 関数. SURFについては,find_obj.cppを参照!...OpenCV OpenCV2.0 samples cp p p に有ります /document/opencvref_cv_gradients.html 局所特徴をどうする? 位置, 大きさ, 形, 等の変化に強い 局所特徴の位置を無視して比較すると, 視点の変化や変形等に不変性を持つ. SIFT は, 回転, スケール, 位置に Yannis Avrithis, et al., ACM MM 2010 不変. しかし... Bag-of-features 法による局所特徴の統合 比較の手間が大変! M 個と N 個の局所特徴の比較 O(MN) 全体でL 組の画像対の比較 O(LMN)

8 Object Bag of words ords Bag-of-featuresモデル g デル 局所特徴群 を袋詰め Fei-Fei Li, Rob Fergus, and Antonio Torralba のスライドからもらってきた Bag-of-features法 概要 g 法 概要 1 1. 特徴抽出 画像の局所から特徴を抽出する 物体の部分部分の特徴を捉えた特徴 物体の部分部分の特徴を捉えた特徴 Bag-of-features法 概要 g 法 概要 特徴抽出 visual vocabulary 視覚的ボキャブラリ を学習

9 Bag-of-features 法 : 概要 1. 特徴抽出 2. visual vocabulary ( 視覚的ボキャブラリ ) を学習. 3. 視覚的ボキャブラリに基づき, 特徴を量子化する. Vector quantization ( ベクトル量子化 ) 音信号の量子化は, 振幅方向の1 次元で量子化. ここでは, 多次元の特徴を, 多次元空間 ( ベクトル空間 ) で量子化するため, ベクトル量子化と呼ぶ. Bag-of-features 法 : 概要 1. 特徴抽出 2. visual vocabulary ( 視覚的ボキャブラリ ) を学習. 3. 視覚的ボキャブラリに基づき, 特徴を量子化する. 4. 画像を visual words ( 視覚単語 ) の頻度で表現 画像 局所特徴 コードブック 視覚単語 ヒストグラム BF 集合 集合 特徴ベクトル ベクトル量子化 画像 1 画像 2 画像 3 画像の物体認識と Bag-of-features 法 ある画像を, その構成要素の集合として記述する. その要素がどのくらいの頻度で現れるか, だけを気にする. 要素の位置は無視する. Bag-of-features 法は物体認識に効果的! Bag-of-features features 法は物体認識に効果的! 星座モデル (Parts-and-shapeモデル) より性能が良かった bag of features bag of features Parts-and-shape model 顔, 花, 植物, 建物 Csurka et al. (2004), Willamowski et al. (2005), Grauman & Darrell (2005), Sivic et al. (2003, 2005) Caltech6 データセットで評価

10 1. 特徴抽出 1. 特徴抽出 局所特徴の記述子を計算 例 :SIFT [Lowe 04], 画像そのまま, 等. 局所特徴抽出の場所 領域を選択 検出したパッチ 検出した顕著点 正規格子点 ランダム点 Slide credit: Josef Sivic 特徴群 ( 集合 ) 1. 特徴抽出 1. 特徴抽出 規則格子 Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 規則格子 Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 顕著点 Csurka et al Fei-Fei & Perona, 2005 Sivic et al. 2005

11 1. 特徴抽出 局所特徴を抽出する Regular grid Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 Interest point detector Csurka et al Fei-Fei & Perona, 2005 Sivic et al その他 ランダムサンプリング (Vidal-Naquet & Ullman, 2002) セグメンテーションした領域ンした領域 (Barnard, Duygulu, Forsyth, de Freitas, Blei, Jordan, 2003) Furuya, CIVR2009 特徴の配置 格子?, ランダム?, 顕著点?, それとも組み合わせ? どんな局所特徴? テクスチャ系? SIFT 系 (SURF 等 )? やHOG?, それとも, 小画像そのもの? 色? 逆効果の場合もある.( 色の異なる自転車, 花,...) Discriminative Training for Object Recognition Using Image Patches, Thomas Deselaers, Pascal Workshop 2006 クラスタリングの例 : 色空間のクラスタリングによる画像の減色 減色 画像を表現する色の数を減らす. 減色後の画像が, 極力, 元の画像に近いように. 元の画像 4 色の画像 クラスタリングの例 : 色空間のクラスタリングによる画像の減色 1. 元画像の色空間を学習して代表色を決定. 元の画像の全ての画素の色ベクトルをクラスタリング. 減色後の色数がクラスタ ( 領域, 類 ) 数. 色は3 次元の特徴ベクトル! 代表色の集合が, 符号表 ( コードブック ) 通常, 減色後の色数 ( 例えば,16 色 ) は与えられる. 2. 元画像の各画素の色をベクトル量子化. 与えられた色を, それに一番近い代表色で近似. 基本アルゴリズム 与えられた画素の色と, 代表色全ての間の距離を計算し, 最も距離の小さい代表色を代表ベクトル ( 符号 ) として選択.

12 OpenCVサンプルクラスタリングによる減色処理 cvkmeans 万色 4 色 2. 視覚辞書 (visual vocabulary) の学習 特徴集合 特徴空間 2. 視覚辞書 (visual vocabulary) の学習 2. 視覚辞書 (visual vocabulary) の学習 Visual vocabulary 視覚辞書 符号ベクトル = クラスタの代表点 クラスタリング Clustering; グループに分類 Slide credit: Josef Sivic クラスタリング Slide credit: Josef Sivic

13 クラスタリングとは データの類似性に基づいたグループ ( クラスタ ) 化 クラスタリングとは データの類似性に基づいたグループ ( クラスタ ) 化 クラスタを代表する特徴 クラスタリングの結果のコードブック ( 符号化辞書 ) を用いてベクトル量子化 (VQ) 視覚ボキャブラリをクラスタリングで ( 教師無し ) 学習 クラスタを代表する特徴がベクトル量子化の符号ベクトル code vector( 符号ベクトル ), 代表ベクトル, などと呼ぶ 例 : クラスタをなす特徴集合の重心を符号ベクトルとするを符す. 視覚ボキャブラリ (visual vocabulary), コードブック ( 符号化表, codebook) などと呼ぶ. 視覚ボキャブラリは, 識別 検索対象以外のデータから学んでも良い. ただし, 教示データが識別対象と十分に似ているのが条件. コードブックを用い, 特徴をベクトル量子化. Vector quantizer( ベクトル量子化器 ) で, 与えられた特徴ベクトルを, その特徴に最も近い符号ベクトル ( 視覚単語,visual word) に量子化. 特徴の多次元空間における最近点探索. その符号ベクトルの符号 ( 単語 ) を出力. 視覚ボキャブラリ ( コードブック ) の例 これら視覚単語を張り合わせると, いろんな画像が近似できる. Fei-Fei et al. 2005

14 画像を単語群 ( 符号語群 ) の頻度で表現 画像を単語群 ( 符号語群 ) の頻度で表現 局所特徴の位置は無視してヒストグラム化 頻度 頻度.... 符号語 ( 視覚単語 ) 符号語 ( 視覚単語 ) ちなみに... ジガゾーパズル は視覚単語のパズル? 視覚単語が画像の部分である例 自分の顔 ができる不思議なパズル ジガゾーパズル パズル 手順 携帯電話 ( など ) で自分の顔を撮影, 専用 Webサイトに送信. 300ピースで顔を表現する. それぞれのピースには視覚単語のような模様が... 顔画像の部分をベクトル量子化して, 最も類似したピースに対応付け. 携帯電話 (PC) に返送された設計図の記号の通りにピースを並べる. Sivic et al. 2005

15 Bag-of-Words法の起源 1 テクスチャ識別 1 テクスチャ識別 Bag-of-Words法の起源 1 テクスチャ識別 1 テクスチャ識別 テクスチャはtextonと呼ばれる基本要素の反復 テクスチャはtextonと呼ばれる基本要素の反復 統計的テクスチャでは 個々のtextonの性質が重要 histogram 複数のtextonがどう並ぶのか は重要ではない 複数 がどう並ぶ か は重 はな Universal texton dictionary Julesz, 1981; Cula & Dana, 2001; Leung & Malik 2001; Mori, Belongie & Malik, 2001; Schmid 2001; Varma & Zisserman, 2002, 2003; Lazebnik, Schmid & Ponce, 2003 Bag-of-Words法の起源 2 テキスト検索におけるBag of wordsモデル 2 テキスト検索におけるBag-of-wordsモデル 辞書にある単語の出現頻度で文書を表現する [Salton 辞書にある単語の出現頻度で文書を表現する [S lt & McGill,1983] Julesz, 1981; Cula & Dana, 2001; Leung & Malik 2001; Mori, Belongie & Malik, 2001; Schmid 2001; Varma & Zisserman, 2002, 2003; Lazebnik, Schmid & Ponce, 2003 Bag-of-Words法の起源 2 テキスト検索におけるBag of wordsモデル 2 テキスト検索におけるBag-of-wordsモデル 辞書にある単語の出現頻度で文書を表現する [Salton 辞書にある単語の出現頻度で文書を表現する [S lt & McGill,1983] US Presidential Speeches Tag Cloud US Presidential Speeches Tag Cloud

16 Bag-of-Words法の起源 2 テキスト検索におけるBag of wordsモデル 2 テキスト検索におけるBag-of-wordsモデル 辞書にある単語の出現頻度で文書を表現する [Salton 辞書にある単語の出現頻度で文書を表現する [S lt 画像 識別 画像の識別 & McGill,1983] Bag-of-features表現 統合した ヒストグラム特徴 Bag of features表現 統合した ヒストグラム特徴 から どうやって ある画像を識別する ある画像のBag ある画像のBag-of-features表現を特徴ベクトルと考えて こ of features表現を特徴ベクトルと考えて こ れを識別器にかける ベクトル空間モデルによる比較 で識別 例 1クラスを識別するSupport Vector Machineを利用 US Presidential Speeches Tag Cloud 画像 検索 画像の検索 Bag-of-features表現 統合した 特徴 から どうやっ Bag of features表現 統合した 特徴 から どうやっ て類似した画像を見つける 得られた 得られたBoW特徴 ヒストグラム の使い方 特徴 グラ 使 方 大域BoW特徴ベクタ 画像全体から 画像の識別 K-NN Support pp Vector Machine,, 等で判別 画像の検索 距離 類似度 の昇順 降順 に表示 ある画像のBag ある画像のBag-of-features表現を特徴ベクトルと考え そ of features表現を特徴ベクトルと考え そ れと近い順に画像を検索し提示する Pascal VOC 2005 局所BoW特徴ベクタ 画像の一部から 画像の一部に窓を設定し その窓でBoWを計算 窓ごとにBoW特徴ベクタを類別し 物体検出 detection に使う 物体検出 detection に使う 藤吉 PCSJ/IMPS2008 位置を検出 部品 顔 タイヤ 手 等 を検出 階層モデル 後 後出 に使う 使 Pascal VOC 2007

17 クラスタリングの例 : 色空間のクラスタリングによる画像の減色 減色 画像を表現する色の数を減らす. 減色後の画像が, 極力, 元の画像に近いように. 元の画像 4 色の画像 クラスタリングの例 : 色空間のクラスタリングによる画像の減色 1. 元画像の色空間を学習して代表色を決定. 元の画像の全ての画素の色ベクトルをクラスタリング. 減色後の色数がクラスタ ( 領域, 類 ) 数. 色は3 次元の特徴ベクトル! 代表色の集合が, 符号表 ( コードブック ) 通常, 減色後の色数 ( 例えば,16 色 ) は与えられる. 2. 元画像の各画素の色をベクトル量子化. 与えられた色を, それに一番近い代表色で近似. 基本アルゴリズム 与えられた画素の色と, 代表色全ての間の距離を計算し, 最も距離の小さい代表色を代表ベクトル ( 符号 ) として選択. OpenCVサンプルクラスタリングによる減色処理 cvkmeans 万色 4 色 減色の例 色空間を, 非連続なクラスタ ( 小領域 ) に分ける. クラスタの中心が, 代表色.

18 代表色の選択 ベクトルとしての特徴量 画像の色の分布を解析して代表色を選択. 解析対象となる多数の画像を解析して偏りをなくす. 教師無し学習アルゴリズム, と見ることもできる. 特徴は多次元ベクトル 特徴点は多次元空間の点. 例 :3 次元色特徴ベクトル (R,G,B) G 色の3 次元ベクタの特徴空間でクラスタリング. 分割型 (partitioning clustering) k-means 法,Mean-shift 法 パラメトリック学習 階層型 (hierarchical clustering) 凝集型 (agglomerative clustering) 分割型 (divisive clustering) n 個のデータ x i (i = 1,, n) ) X = {x 1, x 2,, x n } x i は m 次元ベクトル x i = ( w i1, w i2,, w im ) w ij : ベクトルi の j 番目の要素 B R k-means 法による特徴点のクラスタリング k-means 法による特徴点のクラスタリング 1. 特徴点を ( ランダムに )k 個のクラスタ C={c 1, c 2,, c k } に分け, それらのクラスタiの重心 m 1 i x を求める. c i x c i 2. すべての特徴点 x D について a. その点 xから各クラスタの重心への距離 d(x, m i ) を求める. b. その点 xを距離 d(x, m i) が最小のクラスタ i に追加. 3. 新たなクラスタの重心を計算しなおす. 4. クラスタ ( に属する点 ) や重心に変化がなくなるまで ( つまり, 局所最適解に達するまで ) 上記 2, 3を繰り返す. 1. 特徴点を ( ランダムに )k 個のクラスタ C={c 1, c 2,, c k } に分け, それらのクラスタiの重心 m 1 i x を求める. c i x c i 2. すべての特徴点 x D について a. その点 xから各クラスタの重心への距離 d(x, m i ) を求める. b. その点 xを距離 d(x, m i) が最小のクラスタ i に追加. 3. 新たなクラスタの重心を計算しなおす. 4 クラスタ ( に属する点 ) や重心に変化がなくなるまで ( つまり 4. クラスタ ( に属する点 ) や重心に変化がなくなるまで ( つまり, 局所最適解に達するまで ) 上記 2, 3 を繰り返す.

19 k-means 法による特徴点のクラスタリング k-meansクラスタリング 実現するには... クラスタ数 Kを決める. 事前にクラスタ数を選ぶ必要があるのは,k-means k 法の弱点でもある. 特徴ベクトルを決める. ここでは, 画素の色. 画像の分割なら, 模様, 位置, 向き, 等. 画像から抽出したSURF 特徴 ( 例えば64 次元 ) かも. 特徴ベクトル間の距離 ( 類似度 ) 尺度を決める. L2 距離 (Euclid 距離 ),L1 距離 (Manhattan 距離 ), 等. k-means 法を特徴ベクトルに適用. k-meansクラスタリング k-meansクラスタリング

20 k-meansクラスタリング k-meansクラスタリング k-meansクラスタリング k-meansクラスタリング

21 k-meansクラスタリング k-meansのクラスタ重心の軌跡 2 次元特徴空間におけるクラスタ重心の軌跡の例 Duda et al. k-meansクラスタリングによる画像の減色 K-meansクラスタリングによる, 減色の例 減色, Color Quantization( 色量子化 ) 例 :GIF 画像のルックアップテーブル. k-meansで少数の代表色を選ぶ. 色空間 ( 例えば RGB) で K-means クラスタリングする. 例 :1600 万色から256 色に減色. ある画像に含まれる色 (>>256 色 ) をK= 256でK-meansクラスタリング. 256 個のクラスタの重心を減色後の256 代表色とする. 256 個の代表色をカラールックアップテーブルに登録する. 色空間を, 非連続なクラスタ ( 小領域 ) に分ける. クラスタの中心が, 代表色. 2 k-means 法では右の目的関数を最小化 x j i i clusters j elements of i'th cluster

22 OpenCVサンプルクラスタリングによる減色処理 cvkmeans 万色 4 色 OpenCVサンプルクラスタリングによる減色処理 cvkmeans 万色 16 色 OpenCVサンプルクラスタリングによる減色処理 cvkmeans 万色 32 色 k-meansクラスタリングによる画像分割色だけを使用 例 画像の色によるセグメンテーション ( 分割 ) = 減色処理 元画像 K=5 K=11

23 k-meansクラスタリングによる画像分割色のみ k-meansクラスタリングによる画像分割色と座標 色 色 + 座標 色のみによるセグメンテーション 特徴ベクトルは (R,G,B) の 3 次元. K=20 で得られた 20 個のクラスタのうち,4 クラスタを表示. 距離と色によるセグメンテーション 特徴ベクトルは (R,G,B,X,Y) K=20で得られた20 個のクラスタのうち,4クラスタを表示.