学習を用いたキーポイントマッチングの高速化

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 を変化させたときの応答値を探索

‒ 最大値をとる半径をキーポイントのスケールとする

半径

R [pixel]

近似

LoG

応答値

50 100

キーポイント検出結果例

オリエンテーションの決定

• 注目画像とスケール上（赤円）のピクセルの差が 最大となる角度を探索 

：平滑化画像のピクセル座標

キーポイント判定

• 3点のピクセルを用いて下記の条件を満たす キーポイント候補点は削除

：平滑化画像のピクセル座標

学習画像の生成

• 見えの変化に対応するためテンプレートをアフィン変換

‒ ランダムなパラメータでアフィン変換行列を作成

• 回転，スキュー，平行移動，スケール

（ x , y ）:

テンプレート上の座標

（ x’ , y’ ）:

アフィン変換後の座標

アフィン変換に頑健なキーポイント選択

• 学習画像すべてからキーポイントを抽出

‒ 逆行列によりテンプレート上の対応するキーポイント算出

‒ 同一位置のキーポイント数をカウント

‒ 多くの画像から検出されたキーポイントを検出（例：200）

→ノイズおよびひずみに安定したキーポイントを選択

Randomized Trees の構築

学習画像

・・・

キーポイント

 

キーポイント

キーポイント

・・・

・・・

・・・

・・・

サブセット1 サブセット2 サブセットN

≦ ＞

≦ ＞

ピクセルの位置はランダムに選択

キーポイントの分類

テンプレート ⼊入⼒力力画像

32×32

＋ ＋

（

^＋

）

 

Average 

・・・ =

・・・

Tree

1

Tree

2

Tree

N

≦ ＞ ≦ ＞ ≦ ＞

c

ノードに利用する特徴量

• 2ピクセルを用いた手法

• 4ピクセルを用いた手法

• SIFT特徴量を用いた手法

≦ ＞

−

− ≦ − ＞ −

≦ ＞

• 2ピクセル間の輝度差を特徴量とする

ノードにおける特徴（ 2 ピクセルを用いた手法）

m

：ピクセル

P

：パッチ

I^σ

：平滑化後の画像

≦ ＞

−

−

• 2つのピクセル対の関係性を特徴量とする

ノードにおける特徴（ 4 ピクセルを用いた手法）

m

：ピクセル

P

：パッチ

I^σ

：平滑化後の画像

≦ − ＞ −

ノードにおける特徴（ SIFT 特徴量を用いた手法）

• パッチから得られるSIFT特徴量を使用

u,v

：

4×4

の領域の座標

o

：勾配方向

u

v o

≦ ＞

• 実験データ

‒ Title

• タイトルの部分のキーポイント100個

‒ Eyes

• 絵(目)の部分のキーポイント100個

• 比較手法

‒ C2:2ピクセルを用いた手法

‒ C4:4ピクセルを用いた手法

‒ Cｈ:SIFT特徴量を用いた手法

特徴量の評価実験

特徴量の評価結果

C4はC2より精度は悪い

CｈはC2より良いが計算コストが高い

→精度も良く計算コストが小さいC2を選択

C2 C4 Ch

Title set

depth10  depth12 depth15

60.7%

69.2%

77.0%

57.7%

65.1%

73.7%

66.6%

75.0%

82.4%

Eyes set

depth10 depth12 depth15

72.7%

78.6%

84.7%

70.0%

76.1%

81.4%

74.5%

84.2%

84.2%

マッチング精度

評価実験：対応点マッチング

• テンプレート（猫のマウスパッド）と入力画像の マッチング

テンプレート 入力画像

結果：マッチング（ SIFT ）

対応点数：

18

正解点数：

5

結果：マッチング（ SiftGPU ）

対応点数：

19

正解点数：

6

結果：マッチング（ SURF ）

対応点数：

25

正解点数：

13

結果：マッチング（ Randomized Trees ）

対応点数：

38

正解点数：

38

3. 学習を用いたキーポイントマッチングの高速化

-  Randomized Treesを用いたキーポイントマッチング

- ２段階Randomized Treesによる高精度化

- Ferns

Randomized Trees によるマッチング精度

検出例（70度）：1/4  (25%) 検出例（40度）：217/217  (100%)

射影変化が大きいと精度が低下

マッチング精度低下の原因

• 学習画像の生成

‒ 2次元上の回転の変形のみで3次元の回転の変形を表現できない

‒ アフィンパラメータをランダムで決定するためViewpointの 偏りが生じる

• 決定木の構築

‒ 多くの見えの変化を決定木1つで表現するのは困難

・・・

学習画像

学習画像 Tree

提案手法のアプローチ

_[

西村

,

清水

et al., 2010]

• 学習画像の生成

‒ 3次元上の回転を表現

• 決定木の構築

‒ Viewpoint変化とKeypointを同じRandomized Treesで表現

→ Viewpoint

の変化と

Keypoint

を別々の

Randomized Trees

で表現

2段階にRandomized Treesを構築

＠shiyou1

提案手法 : ２段階の Randomized Trees

Keypoint 分類結果

学習画像

Viewpointクラス3に分類

Tree 1 Tree 2 Tree N1

・・・

Viewpoint分類のためのRandomized Trees 入力画像

Viewpointクラス3 Viewpointクラス2 Viewpointクラス1

Tree 1 Tree 2 Tree N2

・・・

Keypoint分類のためのRandomized Trees

提案手法 : ２段階の Randomized Trees

Keypoint 分類結果

学習画像

Viewpointクラス1に分類

Tree 1 Tree 2 Tree N1

・・・

Viewpoint分類のためのRandomized Trees 入力画像

Viewpointクラス3 Viewpointクラス2 Viewpointクラス1

Tree 1 Tree 2 Tree N2

・・・

Keypoint分類のためのRandomized Trees

• オイラー角を用いて3次元上の回転を表現

‒ Viewpointをψθφ回転角で定義

前処理：学習画像の生成

Viewpoint

z

学習画像の生成例

0 36 72 108 144 180 216 251 288 324

45

60

70 φ

ψ=90 θ

Viewpoint のクラスタリング

  Keypoint   Keypoint

・・・

・・・

  Keypoint

^・・・

学習画像

・・・

：1

：1

：1

：1

：1

：1 Viewpointクラス1   

：1

：1

：1

：1

：1

：1

：2

：2

：2

：2

：2

：2 Viewpointクラス2   

：2

：2

：2

：2

：2

：2

：K

：K

：K

：K

：K

：K ViewpointクラスK  

・・・

：K

：K

：K

：1

：1

：2 ：2

：K ：K

：1

：2

：K ：K ：K ：K

：1

：2

：1 ：1

：2

：2 ・・・

：K ：K ：K

：1 ：1 ：1

：2 ：2 ：2

Viewpoint

クラス

1 2 … K

≦ ＞

≦ ＞

サブセット2

サブセット1 サブセットN 1

1 段階目 :Viewpoint の Randomized Trees の構築

：1

：1

：2 ：2

：K ：K

：1

：2

：K ：K ：K ：K

：1

：2

：1 ：1

：2

：2 ・・・

：K ：K ：K

：1 ：1 ：1

：2 ：2 ：2

サブセット2

サブセット1 サブセットN 1

Tree N1

・・・

Tree 1 Tree 2

1 段階目 :Viewpoint の Randomized Trees の構築

1 段階目： Viewpoint の分類例

入力画像

セントロイド画像

Viewpointクラス

1 10 20 30

クラス1に分類

1 段階目： Viewpoint の分類例

入力画像

セントロイド画像

Viewpointクラス

1 10 20 30

クラス12に分類

・・・

サブセットT サブセット2 サブセット1

：1

：1

：1

：1

：1

：1

Viewpointクラス1

サブセットT2

サブセット2 サブセット1

：2

：2

：2

：2

：2

：2

Viewpointクラス2

サブセットT2

サブセット2 サブセット1

：K

：K

：K

：K

：K

：K

ViewpointクラスK

Tree 1 Tree 2 Tree N²

・・・

Tree 1 Tree 2 Tree N²

・・・

Tree 1 Tree 2 Tree N2

・・・

2 段階目 :Keypoint 分類の Randomized Trees の構築

2 段階目 : Keypoint の分類結果

提案手法：38/45  (84%) Randomized Trees： 5/7  (71%)

キーポイントマッチング結果の比較

ドキュメント内 スライド 1 (ページ 48-87)