Comments
Description
Transcript
Randomized Trees
Randomized Trees http://www.vision.cs.chubu.ac.jp/RTs/ 藤吉研究室 中部大学工学部情報工学科 D3：永橋知行 グラフカットセグメンテーションを用いた前景と背景の共起性に基づく画像分類の高精度化 に関する研究 M2：福田考晃 Randomized Treesを用いた位置同定とシーン分割に関する研究 藤吉弘亘（Hironobu Fujiyoshi) 所属：中部大学工学部情報工学科 E-mail：[email protected] 藤吉研究室 構成：ドクター4人、マスター6人、学部生8人、研究生1人、秘書1人 Twitter：@FLAB 1. Randomized Treesについて - 学習アルゴリズム 2. SIFTベースのキーポイントマッチング - SIFT, SURF, GPU-SIFT 3. 学習を用いたキーポイントマッチングの高速化 - Randomized Treesを用いたキーポイントマッチング ２段階Randomized Treesによる高精度化 Ferns Randomized Trees [Breiman, 2001] • アイデア ‒ 決定木学習 + アンサンブル学習 + ランダム学習 • 類似手法：AdaBoost • 別名 ‒ Random ForestsTM(Leo Breiman and Adele Cutler) ‒ Randomized Forests ‒ Randomized Decision Forests ‒ (Random) Ferns • できること ‒ マルチクラス識別 ‒ クラスタリング • 特徴 ‒ シンプルかつ高速な学習と識別 CVへの応用例1: キーポイントマッチング [Lepetit et al., 2006] CVへの応用例2:物体認識＆セグメンテーション [Shotton et al., 2008] CVへの応用例3: • 文字認識[Amit & Geman, 1997] • visual word クラスタリング[Moosmann et al., 2006] • 行動認識＆姿勢推定[山下 et al., 2010] ＠takayosiy CVへの応用例4: ＠TomokazuMitsui • パーツベースの人検出 [三井 et al., 2011] ‒ 人の領域をパーツに分割し、RTsによるマルチクラス識別器を構築 図 3提案手法における学習と識別の流れ のサブセットに分ける．ネガティブサンプルについては， 提案手法 N 個のパーツ全てにネガティブクラスとして N 番目のクラ スを与える．提案手法では，N=6 であるため，ポジティ ブクラスの各パーツには 0 5，ネガティブクラスには 6 のクラスが与えられる．これらのサンプルを用いて，2 章 で示す Randomized Trees のアルゴリズムに従いマルチ 図 2 提案手法における学習サンプルの分割 従来法 クラス識別器を構築する．決定木の各末端ノードは 7 ク れる．以下より提案手法によるパーツベースへの拡張と， 学習，識別について述べる． 3.1 パーツベースへの拡張 図 8 人検出例 ラスの分布を持つこととなる． 3.3 識別 識別の流れを図 3(b)に示す．入力された未知サンプ Randomized Treesの特徴 • メリット ‒ 高速な学習・識別 • ランダム学習により高次元特徴(数万∼)でも効率的な学習が可能 • 選択された特徴量のみで識別 ‒ 教師信号のノイズに強い • 学習データのランダム選択によりノイズの影響を抑制 • デメリット ‒ オーバーフィッティングになりやすい • パラメータが多い(木の数，木の深さ，サブセット) • 学習データ数が少ないとうまく学習できない → 大量の学習データを取得 or 生成する工夫が必要 マルチクラス識別器の比較（思いっきり主観です！） SVM Boosting Randomized Trees (one-vs-rest) (Joint Boosting) 学習データの数 少 中 多 ノイズの影響 少 大 少 学習時間 中 遅い 速い 識別時間 遅い 中 速い 学習アルゴリズム 木構造を利用した識別器 学習サンプル カテゴリ1 1. 0.8 1.2 3.4 2. 0.2 2.3 4.2 3. 1.1 4.1 2.6 4. 4.2 1.3 2.1 カテゴリ2 ... 3.2 ... 4.2 ... 6.7 ... 2.4 1. 2.3 5.2 1.2 ... 2. 0.2 5.2 3.4 ... 3. 1.1 2.5 5.2 ... 4. 1.2 3.6 6.2 ... カテゴリC 6.2 7.2 3.2 6.3 1. 2.1 1.2 2.5 ... 2. 1.2 2.7 7.4 ... 3. 2.1 3.1 3.3 ... 4. 1.7 4.2 8.2 ... 2.6 3.2 8.5 2.1 分岐ノード 末端ノード 0 深さD 1 2 3 tree1 treeT 決定木の数 学習アルゴリズム ・前処理 Randomized Treesの学習アルゴリズム − データ集合 I から T 個のサブセット作成 ・For t = 1, 2, …, T サブセットの数だけ木を作成 分岐ノード候補をランダムに J 個選択 For j = 1, 2, …, J J 個の分岐ノード候補数 1. 候補 j を用いてサンプルの分割 2. 候補 j の情報利得算出 最も情報利得が高い候補を選択 IF 情報利得 = 0 or 指定した深さに達した ・末端ノード作成 ELSE ・分岐を続ける ・単純ベイズ識別器作成 サブセットの作成 • サンプル集合 I を用意 ‒ サンプルi ∈ I には特徴ベクトル vi, 教師信号 ci が付与 • サブセットの作成 ‒ T 個のサブセットをランダムに作成 サンプル集合 I サブセット I1 サブセット I2 サブセット IT サブセット作成のポイント • サブセット間のサンプルの数は統一 ‒ 木の数と密接な関係 • 完全なランダム選択 ‒ サブセット間でのサンプルの重複を許容 ‒ 学習に利用されないサンプルも許容 サンプル集合 I サブセット I1 サブセット I2 サブセット IT 学習アルゴリズム ・前処理 Randomized Treesの学習アルゴリズム − データ集合 I から T 個のサブセット作成 ・For t = 1, 2, …, T サブセットの数だけ木を作成 分岐ノード候補をランダムに J 個選択 For j = 1, 2, …, J J 個の分岐ノード候補数 1. 候補 j を用いてサンプルの分割 2. 候補 j の情報利得算出 最も情報利得が高い候補を選択 IF 情報利得 = 0 or 指定した深さに達した ・末端ノード作成 ELSE ・分岐を続ける ・単純ベイズ識別器作成 分岐ノードの決定方法 • 一般的には２つの方法が取られる ‒ 情報量を基準として複数の候補から良いものを選択 • Random Forests[ L. Breiman 01 ] • Semantic Texton Forests[ J. Shotton 08 ] ‒ 単純にランダム選択 • Extremely Randomized Trees[ P. Geurts 06 ] • Keypoint Matching [ V.Lepetit 08 ] 分岐ノードの設計 • 基本的に設計は自由 ‒ しきい値，特徴量の大小関係 • Semantic Texton Forests[ J. Shotton et al., CVPR2008 ]では しきい値を利用 ‒ p i 分岐ノードをSとすると !"#$%&i&'"($)&*+,-.&p (21!21 "#!$%&'#('$!"$)#*$(+&,' S(v) = � left f (v) < t right otherwise f : 分岐関数 t : しきい値 f (p) f (p) f (p) = = = f (p) = Px1 ,y1 ,c1 Px1 ,y1 ,c1 + Px2 ,y2 ,c2 Px1 ,y1 ,c1 − Px2 ,y2 ,c2 |Px1 ,y1 ,c1 − Px2 ,y2 ,c2 | J. Shotton ICVSS tutorial より抜粋 分岐ノード候補の選択 • 学習サンプルの特徴ベクトルから候補を選出 ‒ 分岐関数 f と しきい値 t の組み合わせをランダムに選択 • 例：1000次元の特徴ベクトル 1.0 Freq 1 2 3 4 5 6 7 8 993 994 995 996 997 998 9991000 特徴次元 { (2, 0.1)1, ( 993, 0.3 )2, ( 6, 0.2 )3, ( 999, 0.2 )4, ... , ( 4, 0.3 )J } 候補数 J = √(特徴次元数1000) ≒ 32 が推奨されている[Breiman ’01] 学習アルゴリズム ・前処理 Randomized Treesの学習アルゴリズム − データ集合 I から T 個のサブセット作成 ・For t = 1, 2, …, T サブセットの数だけ木を作成 分岐ノード候補をランダムに J 個選択 For j = 1, 2, …, J J 個の分岐ノード候補数 1. 候補 j を用いてサンプルの分割 2. 候補 j の情報利得算出 最も情報利得が高い候補を選択 IF 情報利得 = 0 or 指定した深さに達した ・末端ノード作成 ELSE ・分岐を続ける ・単純ベイズ識別器作成 サンプルの分割と情報利得の算出 • 分岐ノード候補を用いてサンプルを分割 Il = Ir = {i ∈ In |fj (vi ) < tj } In \ Il Il : 左に分岐するサンプル Ir : 右に分岐するサンプル • 情報利得ΔEにより候補を評価 |Il | |Ir | ∆Ej = − E(Il ) − E(Ir ) |In | |In | E : 情報エントロピー 分岐ノード決定過程 • 分岐ノード決定シミュレーション ‒ 分岐関数：２次元空間を分割する一次関数 ‒ 3つの分岐関数から最適なものを見つける 2 y 1 カテゴリ数 : 4 3 サンプル数 : 4 × 33 x 分岐ノード決定過程1 • 分岐関数候補１ 2 y 1 0.50 0.49 0.01 0 3 0.49 0 0.01 Pl (c) x Il 情報量 : E(I) = − n � Pr (c) Pi log2 Pi i=1 E(Il ) = 1.10 1 y 0.50 E(Ir ) = 1.10 Ir 情報利得 : ∆E = − |Il | |Ir | E(Il ) − E(Ir ) |In | |In | = −1.10 x 分岐ノード決定過程2 • 分岐関数候補2 2 y 1 0.500.50 3 0 0.50 0 0 0 Pl (c) x y 情報量 : E(I) = − n � Pr (c) Pi log2 Pi i=1 E(Il ) = 1.0 2 Il 0.50 E(Ir ) = 1.0 Ir 情報利得 : ∆E = − |Il | |Ir | E(Il ) − E(Ir ) |In | |In | = −1.0 x 分岐ノード決定過程3 • 分岐関数候補3 2 y 1 0.46 0.51 3 0 0.49 0.46 0.04 0 0.03 Pl (c) x 情報量 : E(I) = − n � Pr (c) Pi log2 Pi i=1 E(Il ) = 1.16 y 3 E(Ir ) = 1.21 Ir 情報利得 : ∆E = − Il |Il | |Ir | E(Il ) − E(Ir ) |In | |In | = −1.185 x 分岐ノード決定過程4 • 分岐ノード決定シミュレーション ‒ 分岐関数：２次元空間を分割する一次関数 ‒ 3つの分岐関数から最適なものを見つける 2 y 1 カテゴリ数 : 4 サンプル数 : 4 × 33 3 ∆E1 = −1.10 ∆E2 = −1.0 max ∆E3 = −1.185 x →分岐関数候補 2 を選択 学習アルゴリズム ・前処理 Randomized Treesの学習アルゴリズム − データ集合 I から T 個のサブセット作成 ・For t = 1, 2, …, T サブセットの数だけ木を作成 分岐ノード候補をランダムに J 個選択 For j = 1, 2, …, J J 個の分岐ノード候補数 1. 候補 j を用いてサンプルの分割 2. 候補 j の情報利得算出 最も情報利得が高い候補を選択 IF 情報利得 = 0 or 指定した深さに達した ・末端ノード作成 ELSE ・分岐を続ける ・単純ベイズ識別器作成 分岐の終了条件 • 情報利得が０になった時 ‒ 分岐がこれ以上出来ないので終わる • 指定した深さまで学習が進んだ時 ‒ 過学習を防ぐため 情報利得が０になる例 • 分岐ノード作成を繰り返す ‒ Ir と Il に単一カテゴリのサンプルが属する状態になる → 情報利得が 0 になる 1.0 1.0 y Il Pl (c) 情報量 : E(I) = − Pr (c) n � Pi log2 Pi i=1 E(Il ) = 0.0 Ir x E(Ir ) = 0.0 |Il | |Ir | E(Il ) − E(Ir ) 情報利得 : ∆E = − |In | |In | = 0.0 指定した深さに達する例 • 木が深くなるほど過学習になる → 木の深さを制限して対応 例：最大の深さ３で学習 y 0 1 2 3 → 指定した深さに成長したため x 末端ノード 末端ノード作成 • カテゴリ分布ヒストグラムPn (c) ‒ サンプル集合Inに付与された教師信号を投票 頻度 サブセット IT カテゴリ C 学習アルゴリズム ・前処理 Randomized Treesの学習アルゴリズム − データ集合 I から T 個のサブセット作成 ・For t = 1, 2, …, T サブセットの数だけ木を作成 分岐ノード候補をランダムに J 個選択 For j = 1, 2, …, J J 個の分岐ノード候補数 1. 候補 j を用いてサンプルの分割 2. 候補 j の情報利得算出 最も情報利得が高い候補を選択 IF 情報利得 = 0 or 指定した深さに達した ・末端ノード作成 ELSE ・分岐を続ける ・単純ベイズ識別器作成 単純ベイズ識別器の作成 • T 個の決定木をトラバーサル v v tree tT tree t1 …… 1 Average + …… + P1 (c|v) 識別結果の統合： 単純ベイズ識別器： Pt (c|v) T ＝ 8 4 523 7 6 T � 1 P (c|v) = Pt (c|v) T t=1 Ci� = arg max P (ci |v) ci 実装上の注意点 • 学習サンプルの各クラスのサンプル数が不均等の場合 → Inverse Label Frequencyが必要 • 学習サンプル I すべてを用いてクラスの頻度分布を作成 ξc = � � i∈I �−1 [c = ci ] 頻度 ‒ あるサンプル i ∈ I に付けられているラベルを ciを利用 カテゴリ C • カテゴリの頻度分布作成時に重み付け RTsによる学習過程 • トイプロブレムを利用して学習過程を観察 480 ・3クラス ・2次元空間 ・学習パラメータ 木の数 1 分岐候補 25 深さ 4 0 640 学習過程１ • 深さ1 480 ノード ΔE ：−0.68 特徴量 ：x しきい値 ：393 0 393 640 学習過程２ • 深さ2 480 ノード ΔE ：−0.04 特徴量 ：x しきい値 ：233 0 233 640 学習過程３ • 深さ3 480 212 ノード ΔE 0 640 ：−0.23 特徴量 ：y しきい値 ：227 学習過程４ (終了) • 深さ4 480 0 256 ノード 640 ΔE ：0.0 特徴量 ：x しきい値 ：256 パラメータ調整のコツ • 過学習を回避するためには ‒ 深さを浅く設定する • 表現能力をあげるためには ‒ 木の数を増やす • 分岐ノード候補数 ‒ 特徴次元数 が推奨 • サブセットに分けるデータの数 ‒ サブセット間で若干重複がある程度の数 2. SIFTベースのキーポイントマッチング 高速 SIFTアプローチの変遷 GPU を用いた 高速化 Sinha, Sudipta: 2006 SIFT-GPU 学習なし 手法の高速化 Bay et al.: 2006 SURF Lowe: 1999 SIFT 頑健性の向上 頑健性の向上 Ke, Sukthankar: 2004 PCA-SIFT Mikolajczyk, Schmid: 2005 GLOH 高精度 速度の比較1 SIFT(PC) SURF 速度の比較2 SURF(PC) SiftGPU まとめ：速度の比較 SIFTとSURFの処理速度の比較 ハード 手法 処理時間（FPS） PC SIFT 1 PC SURF 9 GPU1（GeForce GT220 ） SiftGPU 16 GPU2（Tesla C1060） SiftGPU 22 SIFT ：http://vision.ucla.edu/~vedaldi/code/siftpp/siftpp.html SURF ：OpenCV2.1 SIFT-GPU：http://cs.unc.edu/~ccwu/siftgpu/ 高速 SIFTアプローチの変遷 高速・高精度化 GPU を用いた 高速化 Lepetit, Fua: 2006 RTs Sinha, Sudipta: 2006 SIFT-GPU 学習なし 学習あり 手法の高速化 Bay et al.: 2006 SURF Lowe: 1999 SIFT 頑健性の向上 頑健性の向上 Ke, Sukthankar: 2004 PCA-SIFT Mikolajczyk, Schmid: 2005 GLOH 高精度 3. 学習を用いたキーポイントマッチングの高速化 - Randomized Treesを用いたキーポイントマッチング - ２段階Randomized Treesによる高精度化 - Ferns Keypoint Recognition using Randomized Trees [Lepetit et al., 2006] • 決定木を用いたキーポイントの分類 ‒ 学習 • テンプレートをアフィン変換して学習画像を作成 • 学習画像すべてからキーポイントを検出 • キーポイントを中心とした32 32のパッチを作成 • 決定木の構築 ‒ 分類によるマッチング • 入力画像からキーポイント検出 • キーポイントを中心とした32 32のパッチを作成 • 決定木によりキーポイントをマッチング キーポイント検出 • SIFTのキーポイント検出 ‒ DoG( LoG)の極値探索 → 近似計算による高速化 ex. SURF:boxフィルタによるHessian-Laplaceの近似 • LoGの近似計算による高速なキーポイント検出 ‒ キーポイント候補点の検出 ‒ 円上の輝度値を用いたスケールとオリエンテーションの探索 ‒ キーポイントの判定 LoGの近似 • LoGのピーク値のみを用いることで計算コストを削減 ：平滑化画像のピクセル座標 キーポイント候補点の検出 • ノイズの影響を抑制するため入力画像を平滑化(Iσ) • 注目画素の近似LoG（R=固定）の応答値が近傍で最大 ‒ キーポイントの候補点として検出 R キーポイントのスケール探索 • 近似LoGの半径Rを変化させたときの応答値を探索 近似LoG応答値 ‒ 最大値をとる半径をキーポイントのスケールとする 50 半径R [pixel] 100 キーポイント検出結果例 オリエンテーションの決定 • 注目画像とスケール上（赤円）のピクセルの差が 最大となる角度を探索 ：平滑化画像のピクセル座標 キーポイント判定 • 3点のピクセルを用いて下記の条件を満たす キーポイント候補点は削除 ：平滑化画像のピクセル座標 学習画像の生成 • 見えの変化に対応するためテンプレートをアフィン変換 ‒ ランダムなパラメータでアフィン変換行列を作成 • 回転，スキュー，平行移動，スケール （ x , y ）:テンプレート上の座標 （ x’ , y’ ）:アフィン変換後の座標 アフィン変換に頑健なキーポイント選択 • 学習画像すべてからキーポイントを抽出 ‒ 逆行列によりテンプレート上の対応するキーポイント算出 ‒ 同一位置のキーポイント数をカウント ‒ 多くの画像から検出されたキーポイントを検出（例：200） →ノイズおよびひずみに安定したキーポイントを選択 Randomized Treesの構築 学習画像 ・・・ キーポイント ・・・ キーポイント ・・・ キーポイント ・・・ ・・・ サブセット1 サブセット2 ≦ サブセットN ＞ ピクセルの位置はランダムに選択 ≦ ＞ キーポイントの分類 32×32 テンプレート ⼊入⼒力力画像 Tree1 Tree2 ≦ ＞ ≦ TreeN ＞ ≦ ＞ ・・・ （ Average ＋ ＋ ・・・ ＋ ） = c ノードに利用する特徴量 • 2ピクセルを用いた手法 ≦ ＞ • 4ピクセルを用いた手法 − ≦ − − ＞ − • SIFT特徴量を用いた手法 ≦ ＞ ノードにおける特徴（2ピクセルを用いた手法） • 2ピクセル間の輝度差を特徴量とする m：ピクセル P：パッチ Iσ：平滑化後の画像 ≦ ＞ ノードにおける特徴（4ピクセルを用いた手法） • 2つのピクセル対の関係性を特徴量とする m：ピクセル P：パッチ Iσ：平滑化後の画像 − ≦ − − ＞ − ノードにおける特徴（SIFT特徴量を用いた手法） • パッチから得られるSIFT特徴量を使用 u u,v：4×4の領域の座標 o：勾配方向 v o ≦ ＞ 特徴量の評価実験 • 実験データ ‒ Title • タイトルの部分のキーポイント100個 ‒ Eyes • 絵(目)の部分のキーポイント100個 • 比較手法 ‒ C2:2ピクセルを用いた手法 ‒ C4:4ピクセルを用いた手法 ‒ Cｈ:SIFT特徴量を用いた手法 特徴量の評価結果 マッチング精度 Title set C2 C4 Ch 60.7% 57.7% 66.6% 69.2% 65.1% 75.0% 77.0% 73.7% 82.4% depth10 72.7% 70.0% 74.5% depth12 78.6% 76.1% 84.2% depth15 84.7% 81.4% 84.2% depth10 depth12 depth15 Eyes set C4はC2より精度は悪い CｈはC2より良いが計算コストが高い →精度も良く計算コストが小さいC2を選択 評価実験：対応点マッチング • テンプレート（猫のマウスパッド）と入力画像の マッチング テンプレート 入力画像 結果：マッチング（SIFT） 対応点数：18 正解点数： 5 結果：マッチング（SiftGPU） 対応点数：19 正解点数： 6 結果：マッチング（SURF） 対応点数：25 正解点数：13 結果：マッチング（Randomized Trees） 対応点数：38 正解点数：38 3. 学習を用いたキーポイントマッチングの高速化 - Randomized Treesを用いたキーポイントマッチング - ２段階Randomized Treesによる高精度化 - Ferns Randomized Treesによるマッチング精度 検出例（40度）：217/217 (100%) 検出例（70度）：1/4 (25%) 射影変化が大きいと精度が低下 マッチング精度低下の原因 • 学習画像の生成 ‒ 2次元上の回転の変形のみで3次元の回転の変形を表現できない ‒ アフィンパラメータをランダムで決定するためViewpointの 偏りが生じる ・・・ 学習画像 • 決定木の構築 ‒ 多くの見えの変化を決定木1つで表現するのは困難 学習画像 Tree 提案手法のアプローチ [西村, 清水 et al., 2010] • 学習画像の生成 ＠shiyou1 ‒ 3次元上の回転を表現 • 決定木の構築 ‒ Viewpoint変化とKeypointを同じRandomized Treesで表現 → Viewpointの変化とKeypointを別々のRandomized Treesで表現 2段階にRandomized Treesを構築 提案手法:２段階のRandomized Trees 入力画像 Viewpoint分類のためのRandomized Trees ・・・ Viewpointクラス1 Tree 1 Viewpointクラス2 Tree N1 Tree 2 Viewpointクラス3に分類 Keypoint分類のためのRandomized Trees ・・・ Viewpointクラス3 学習画像 Tree 1 Tree 2 Keypoint分類結果 Tree N2 提案手法:２段階のRandomized Trees 入力画像 Viewpoint分類のためのRandomized Trees ・・・ Viewpointクラス1 Tree 1 Viewpointクラス2 Tree N1 Tree 2 Viewpointクラス1に分類 Keypoint分類のためのRandomized Trees ・・・ Viewpointクラス3 学習画像 Tree 1 Tree 2 Keypoint分類結果 Tree N2 前処理：学習画像の生成 • オイラー角を用いて3次元上の回転を表現 ‒ Viewpointをψθφ回転角で定義 z Viewpoint 学習画像の生成例 θ φ 0 36 72 108 144 180 216 251 288 324 45 60 70 ψ=90 Viewpointのクラスタリング ・・・ 学習画像 Keypoint ：1 ：2 ：1 ：2 ・・・ ：K Keypoint ：1 ：2 ：1 ：2 ・・・ ：K Keypoint ：1 ：2 ：1 ：2 ・・・ ：K ：1 ：1 ：2 ：2 ：1 ：1 ：2 ：2 ：1 ：1 ：2 ：2 Viewpointクラス1 Viewpointクラス2 ・・・ ：K ：K ：K ：K ：K ：K ViewpointクラスK 1段階目:ViewpointのRandomized Treesの構築 ：1 ：1 ：1 ：1 ：1 ：1 ：2 ：2 ：2 ：2 ：2 ：2 ：K ：K ：K ：K ：K ：K サブセット1 ・・・ サブセット2 ≦ ：1 ：1 ：1 ：2 ：2 ：2 ：K ：K ：K サブセットN 1 ＞ ≦ 1 2… K Viewpointクラス ＞ 1段階目:ViewpointのRandomized Treesの構築 ：1 ：1 ：1 ：1 ：1 ：1 ：2 ：2 ：2 ：2 ：2 ：2 ：K ：K ：K ：K ：K ：K サブセット1 ・・・ サブセット2 ：1 ：1 ：1 ：2 ：2 ：2 ：K ：K ：K サブセットN 1 ・・・ Tree 1 Tree 2 Tree N1 1段階目：Viewpointの分類例 入力画像 1 10 20 Viewpointクラス クラス1に分類 セントロイド画像 30 1段階目：Viewpointの分類例 入力画像 1 10 20 Viewpointクラス クラス12に分類 セントロイド画像 30 2段階目:Keypoint分類のRandomized Treesの構築 サブセットT サブセット2 サブセット1 ：1 ：1 ：1 ：1 ：1 ：1 Viewpointクラス1 ・・・ Tree 1 Tree N2 Tree 2 サブセットT2 サブセット2 サブセット1 ：2 ：2 ：2 ：2 ：2 ：2 Viewpointクラス2 ・・・ Tree 1 Tree N2 Tree 2 ・・・ サブセットT2 サブセット2 サブセット1 ：K ：K ：K ：K ：K ：K ViewpointクラスK ・・・ Tree 1 Tree 2 Tree N2 2段階目: Keypointの分類結果 Randomized Trees： 5/7 (71%) 提案手法：38/45 (84%) キーポイントマッチング結果の比較 SIFT：0/1 (0%) ASIFT：276/276 (100%) RTs ：1/4 (25%) 2段階RTs：23/26 (88%) キーポイントマッチング手法の比較 100 2段階RTs ASIFT マッチング精度 [%] 95 90 85 RTs SURF 80 SIFT 75 70 10 100 1000 処理時間 [ms] 10000 100000 3. 学習を用いたキーポイントマッチングの高速化 - Randomized Treesを用いたキーポイントマッチング - ２段階Randomized Treesによる高精度化 - Ferns Fast Keypoint Recognition using Random Ferns [Özuysal et al.,2010] • キーポイント識別に特化させたRandomized Trees ‒ 決定木のメモリ容量を削減 ‒ 同じ階層で共通の分岐関数を使用 → 各分岐関数の出力でリーフノードを表現可能 Ferns (シダ植物) Fernsの構築1 • 分岐関数の出力パターンからクラスの頻度分布を作成 ‒ 分岐関数はランダムで決定 Fern カテゴリciの学習画像 0 1 1 (011)2 = 3 1 0 1 (101)2 = 5 0 1 0 (010)2 = 2 0 1 1 (011)2 = 3 01234567 カテゴリciの 頻度分布 Fernsの構築2 Ferns カテゴリc1 ・・・ ・・・ • 分岐関数の出力パターンからクラスの頻度分布を作成 カテゴリc2 カテゴリc3 Fern 1 Fern T ・・・ ・・・ Fern 2 Fernsの識別 • 各Fernの出力パターンのクラスの頻度分布を ‒ 分岐関数はランダムで決定 Ferns クラスc1 クラスc2 クラスc3 × × × × × × (010)2 未知入力 (011)2 × ・・・ × ・・・ ・・・ ・・・ (110)2 × まとめ: Randomized Trees • Randomized Trees ‒ 決定木を用いたマルチクラス識別器 ‒ 高速な学習・識別 • 学習を用いたキーポイントマッチングの高速化 ‒ Randomized Treesを用いたキーポイントマッチング • SIFTベースの手法より高速・高精度化 ‒ ２段階Randomized Treesによる高精度化 • Viewpontに分けてから分類 ‒ Ferns • Randomized Treesの軽量化 参考文献1 1. Randomized Treesについて ‒ [Breiman, 2001] L. Breiman, "Random Forests.", Machine Learning 45 (1): 5‒32, 2001. ‒ [Lepetit et al., 2006] V. Lepetit and P. Fua, Keypoint Recognition using Randomized Trees , IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 28, Nr. 9, pp. 1465-1479, 2006. ‒ [Shotton et al., 2008] J. Shotton, M. Johnson, R. Cipolla, Semantic Texton Forests for Image Categorization and Segmentation. , In Proc. IEEE CVPR 2008. ‒ [Amit & Geman, 1997] Y. Amit and D. Geman Y, Shape Quantization and Recognition with Randomized Trees , Neural Computation, vol. 9, pp. 1545-1588, 1996 ‒ [Moosmann et al., 2006] F. Moosmann, B. Triggs, and F. Jurie, Fast Discriminative Visual Codebooks using Randomized Clustering Forests. , In NIPS, 2006. ‒ [山下 et al., 2010] 山下隆義, 山内悠嗣, 藤吉弘亘, "Boosted Randomized Trees による人 物検出と行動の同時認識", 第13回画像の認識・理解シンポジウム(MIRU2010), 2010. ‒ [Geurts et al., 2006] P. Gurts, D. Ernst, and L. Wehenkel, Extremely Randomized Trees , Machine Learning, vol. 63, issue 1, pp. 3-42, 2006. 参考文献2 2. SIFTベースのキーポイントマッチング ‒ [Lowe 04] David G.Lowe, Distinctive image features from scale-invariant keypoints , Int.Journal of Computer Vision,Vol.60, No.2, pp.91-110, 2004． ‒ [Ke 04] Yan Ke, Rahul Sukthankar, PCA-SIFT: A more distinctive representation for local image descriptors , Proc. of CVPR, pp.506-503, 2004. ‒ [Mikolajczyk 05] Krystian Mikolajczyk and Cordelia Schmid, GLOH A performance evaluation of local descriptors , IEEE tran. On Pattern Analysis and Machine Intelligence, pp.1615-1630, 2005. ‒ [Bay 06] H. Bay, T. Tuytelaars, and L. Van Gool, SURF: Speeded Up Robust. Features , In ECCV , pp.404-417, 2006. ‒ [Sinha 06] Sudipta N Sinha, Jan-Michael Frahm, Marc Pollefeys and Yakup Genc, GPU-Based Video Feature Tracking and Matching , EDGE 2006, workshop on Edge Computing Using New Commodity Architectures, Chapel Hill, 2006. 参考文献3 3. 学習を用いたキーポイントマッチングの高速化 ‒ [西村 et al., 2010] 西村孝, 清水彰一, 藤吉弘亘, "2段階のRandomized Treesを用いたキー ポイントの分類", 第13回画像の認識・理解シンポジウム(MIRU2010), 2010. ‒ [Özuysal et al.,2010] M. Özuysal, M. Calonder, V. Lepetit, P. Fua, Fast Keypoint Recognition using Random Ferns IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, Nr. 3, pp. 448 - 461, 2010.