Microsoft PowerPoint - sm13_lect03_ all.pptx

Similar documents
Microsoft PowerPoint - pr_12_template-bs.pptx

SICE東北支部研究集会資料(2013年)

LBP 2 LBP 2. 2 Local Binary Pattern Local Binary pattern(lbp) [6] R

ビジュアル情報処理

画像認識性能を改善する高精度な特徴量抽出手法の検討 A Study on Feature-Extraction Methods for Improvement of Image-Recognition Performance 井上俊明 Toshiaki Inoue 要旨 各種のカメラ搭載機器の急速な

2. 30 Visual Words TF-IDF Lowe [4] Scale-Invarient Feature Transform (SIFT) Bay [1] Speeded Up Robust Features (SURF) SIFT 128 SURF 64 Visual Words Ni

スライド 1

0 21 カラー反射率 slope aspect 図 2.9: 復元結果例 2.4 画像生成技術としての計算フォトグラフィ 3 次元情報を復元することにより, 画像生成 ( レンダリング ) に応用することが可能である. 近年, コンピュータにより, カメラで直接得られない画像を生成する技術分野が生

画像工学入門

スライド 1

(b) BoF codeword codeword BoF (c) BoF Fergus Weber [11] Weber [12] Weber Fergus BoF (b) Fergus [13] Fergus 2. Fergus 2. 1 Fergus [3]

画像処理工学

す 局所領域 ωk において 線形変換に用いる係数 (ak 画素の係数 (ak bk ) を算出し 入力画像の信号成分を bk ) は次式のコスト関数 E を最小化するように最適化 有さない画素に対して 式 (2) より画素値を算出する される これにより 低解像度な画像から補間によるアップサ E(

(MIRU2008) HOG Histograms of Oriented Gradients (HOG)

(VKIR) VKIR VKIR DCT (R) (G) (B) Ward DCT i

Microsoft PowerPoint - dm1_3.pptx

時空間特徴を用いた Web動画からの特定動作対応ショットの 自動抽出

Microsoft PowerPoint - Lec15 [互換モード]

PowerPoint プレゼンテーション

BDH Cao BDH BDH Cao Cao Cao BDH ()*$ +,-+.)*$!%&'$!"#$ 2. 1 Weng [4] Metric Learning Weng DB DB Yang [5] John [6] Sparse Coding sparse coding DB [7] K

tottori2013-print.key

Microsoft PowerPoint - H17-5時限(パターン認識).ppt

MATLAB ではじめる画像処理とロボットビジョン ~ 機械学習による物体認識と SLAM~ MathWorks Japan アプリケーションエンジニアリング部信号処理 通信 木川田亘 2015 The MathWorks, 1Inc.

l10

Microsoft PowerPoint - SSII_harada pptx

nlp1-12.key

Microsoft PowerPoint - dm1_5.pptx

Microsoft PowerPoint - CV04.ppt [互換モード]

Microsoft PowerPoint - mp11-06.pptx

コンピュータグラフィックス第8回

画像類似度測定の初歩的な手法の検証

Microsoft PowerPoint - DigitalMedia2_3b.pptx

Microsoft PowerPoint - DigitalMedia2_2.pptx

1 (PCA) 3 2 P.Viola 2) Viola AdaBoost 1 Viola OpenCV 3) Web OpenCV T.L.Berg PCA kpca LDA k-means 4) Berg 95% Berg Web k-means k-means

Microsoft PowerPoint - 統計科学研究所_R_主成分分析.ppt

Microsoft PowerPoint - ip02_01.ppt [互換モード]

Microsoft PowerPoint - H21生物計算化学2.ppt

Microsoft Word - 卒論レジュメ_最終_.doc

Microsoft PowerPoint - mp11-02.pptx

画像解析論(2) 講義内容

色の類似性に基づいた形状特徴量CS-HOGの提案

Microsoft PowerPoint PresentationPRMU2008Nov.ppt [互換モード]

Microsoft PowerPoint - DigitalMedia2_12.pptx

Microsoft PowerPoint - 10.pptx

PowerPoint Presentation

IS2-06 第21回画像センシングシンポジウム 横浜 2015年6月 画像をスーパーピクセルに変換する手法として SLIC[5] を用いる Achanta らによって提案された SLIC 2.2 グラフマッチング は K-means をベースにした手法で 単純な K-means に いる SPIN

Microsoft PowerPoint - comprog11.pptx

混沌系工学特論 #5

Microsoft PowerPoint - descriptor.ppt [互換モード]

連続講座 断層映像法の基礎第 34 回 : 篠原 広行 他 放射状に 線を照射し 対面に検出器の列を置いておき 一度に 1 つの角度データを取得する 後は全体を 1 回転しながら次々と角度データを取得することで計測を終了する この計測で得られる投影はとなる ここで l はファンビームのファンに沿った

[1] SBS [2] SBS Random Forests[3] Random Forests ii

画像解析論(7) 講義内容

図 5 一次微分 図 6 コントラスト変化に伴う微分プロファイルの変化 価し, 合否判定を行う. 3. エッジ検出の原理ここでは, 一般的なエッジ検出の処理内容と, それぞれの処理におけるパラメータについて述べる. 3.1 濃度投影検出線と直交する方向に各画素をスキャンし, その濃度平均値を検出線上

3 2 2 (1) (2) (3) (4) 4 4 AdaBoost 2. [11] Onishi&Yoda [8] Iwashita&Stoica [5] 4 [3] 3. 3 (1) (2) (3)

28 TCG SURF Card recognition using SURF in TCG play video

以下 変数の上のドットは時間に関する微分を表わしている (ex. 2 dx d x x, x 2 dt dt ) 付録 E 非線形微分方程式の平衡点の安定性解析 E-1) 非線形方程式の線形近似特に言及してこなかったが これまでは線形微分方程式 ( x や x, x などがすべて 1 次で なおかつ

Microsoft Word - 卒業論文.doc

0 スペクトル 時系列データの前処理 法 平滑化 ( スムージング ) と微分 明治大学理 学部応用化学科 データ化学 学研究室 弘昌

コンピュータグラフィックス第6回

ディジタル信号処理

Microsoft PowerPoint - 第3回2.ppt

Microsoft PowerPoint - Lec21 [互換モード]

Microsoft PowerPoint - Lec11 [互換モード]

Microsoft Word - CMS_Colorgraphy_Color_Space_Calc.doc

0 部分的最小二乗回帰 Partial Least Squares Regression PLS 明治大学理 学部応用化学科 データ化学 学研究室 弘昌

Microsoft PowerPoint - CV10.ppt [互換モード]

パソコンシミュレータの現状

Microsoft PowerPoint - qcomp.ppt [互換モード]

Transcription:

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

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 ボケ大

Difference-of-Gaussian DoG ガウス関数の差分 Gaussフィルタ ィルタ ガウス関数の差分は2階微分として働く Gauss ガウス フィルタ Gaussian low-pass filter ガウス低域通過フィ ルタ 等とも呼ばれる 2 4 1 2 x2 g ( x) exp 2 2 1 2 2 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 周波数 細かさ 特定の帯域を通過 特定スケールの輪郭を抽出

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

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

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

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 404--417, 2006. cvextractsurf() 関数. SURFについては,find_obj.cppを参照!...OpenCV OpenCV2.0 samples cp p p に有ります. http://opencv.jp/opencv- 1.1.0/document/opencvref_cv_gradients.html http://gihyo.jp/dev/feature/01/opencv/0004 局所特徴をどうする? 位置, 大きさ, 形, 等の変化に強い 局所特徴の位置を無視して比較すると, 視点の変化や変形等に不変性を持つ. SIFT は, 回転, スケール, 位置に Yannis Avrithis, et al., ACM MM 2010 不変. しかし... Bag-of-features 法による局所特徴の統合 比較の手間が大変! M 個と N 個の局所特徴の比較 O(MN) 全体でL 組の画像対の比較 O(LMN)

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 法 概要 1 1. 2. 特徴抽出 visual vocabulary 視覚的ボキャブラリ を学習

Bag-of-features 法 : 概要 1. 特徴抽出 2. visual vocabulary ( 視覚的ボキャブラリ ) を学習. 3. 視覚的ボキャブラリに基づき, 特徴を量子化する. Vector quantization ( ベクトル量子化 ) 音信号の量子化は, 振幅方向の1 次元で量子化. ここでは, 多次元の特徴を, 多次元空間 ( ベクトル空間 ) で量子化するため, ベクトル量子化と呼ぶ. Bag-of-features 法 : 概要 1. 特徴抽出 2. visual vocabulary ( 視覚的ボキャブラリ ) を学習. 3. 視覚的ボキャブラリに基づき, 特徴を量子化する. 4. 画像を visual words ( 視覚単語 ) の頻度で表現 画像 局所特徴 コードブック 視覚単語 ヒストグラム BF 集合 集合 特徴ベクトル ベクトル量子化 3 1 2 画像 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 データセットで評価

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. 2004 Fei-Fei & Perona, 2005 Sivic et al. 2005

1. 特徴抽出 局所特徴を抽出する Regular grid Vogel & Schiele, 2003 Fei-Fei & Perona, 2005 Interest point detector Csurka et al. 2004 Fei-Fei & Perona, 2005 Sivic et al. 2005 その他 ランダムサンプリング (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. 元画像の各画素の色をベクトル量子化. 与えられた色を, それに一番近い代表色で近似. 基本アルゴリズム 与えられた画素の色と, 代表色全ての間の距離を計算し, 最も距離の小さい代表色を代表ベクトル ( 符号 ) として選択.

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

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

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

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 http://chir.ag/phernalia/preztags/ US Presidential Speeches Tag Cloud http://chir.ag/phernalia/preztags/

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 http://chir.ag/phernalia/preztags/ 画像 検索 画像の検索 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

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

代表色の選択 ベクトルとしての特徴量 画像の色の分布を解析して代表色を選択. 解析対象となる多数の画像を解析して偏りをなくす. 教師無し学習アルゴリズム, と見ることもできる. 特徴は多次元ベクトル 特徴点は多次元空間の点. 例 :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 を繰り返す.

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

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

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

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

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