Randomized Trees
CV 1: [Lepetit et al., 2006]
CV 2: [Shotton et al., 2008]
CV 3: [Amit & Geman, 1997] [Moosmann et al., 2006] [ et al., 2010]
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
D 1 1. 0.8 1.2 3.4... 3.2 2. 0.2 2.3 4.2... 4.2 3. 1.1 4.1 2.6... 6.7 4. 4.2 1.3 2.1... 2.4 2 1. 2.3 5.2 1.2... 6.2 2. 0.2 5.2 3.4... 7.2 3. 1.1 2.5 5.2... 3.2 4. 1.2 3.6 6.2... 6.3 C 1. 2.1 1.2 2.5... 2.6 2. 1.2 2.7 7.4... 3.2 3. 2.1 3.1 3.3... 8.5 4. 1.7 4.2 8.2... 2.1 0 1 2 3 tree1 treet
Randomized Trees I T tt J jjj j j
I i I vi ci T I I1 I2 IT
I I1 I2 IT
Randomized Trees I T tt J jjj j j
p S i!"#$%&i&'"($)&*+,-.&p (21!21 "#!$%&'#('$!"$)#*$(+&,' f(p) = P x1,y 1,c 1 f(p) = P x1,y 1,c 1 + P x2,y 2,c 2 f(p) = P x1,y 1,c 1 P x2,y 2,c 2 f(p) = P x1,y 1,c 1 P x2,y 2,c 2 S(v) = left f(v) <t right otherwise f : t : J. Shotton ICVSS tutorial
ft 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 tt J jjj j j
I l = {i I n f j (v i ) <t j } Il : I r = I n \ I l Ir : ΔE E j = I l I n E(I l) I r I n E(I r) E :
1 2 y : 4 3 : 4 33 x
1 y 2 1 3 0.01 0.50 0.49 0 0.49 0 0.01 0.50 y Il 1 Ir x Pl (c) Pr (c) n : E(I) = P i log 2 P i i=1 E(I l )=1.10 E(I r )=1.10 : E = I l I n E(I l) I r I n E(I r) = 1.10 x
2 y 2 1 3 0.500.50 0.50 0.50 0 0 0 0 x y 2 Pl (c) Pr (c) n : E(I) = P i log 2 P i E(I l )=1.0 Il Ir E(I r )=1.0 i=1 : E = I l I n E(I l) I r I n E(I r) = 1.0 x
3 1 y 2 3 0 0.460.51 0.03 0.490.04 0 0.46 y 3 Ir x Pl (c) Pr (c) n : E(I) = P i log 2 P i i=1 E(I l )=1.16 E(I r )=1.21 Il : E = I l I n E(I l) I r I n E(I r) = 1.185 x
4 y 1 2 : 4 3 : 4 33 E 1 = 1.10 E 2 = 1.0 max E 3 = 1.185 x
Randomized Trees I T tt J jjj j j
Ir Il y Il 1.0 1.0 Ir x Pl (c) : E(I) = E(I l )=0.0 E(I r )=0.0 Pr (c) n P i log 2 P i i=1 : E = I l I n E(I l) I r I n E(I r) =0.0
y 0 1 2 x 3
Pn (c) In IT C
Randomized Trees I T tt J jjj j j
T v v tree t 1 tree t T P 1 (c v) Average + + C i P t (c v) P (c v) = 1 T = arg max c i T 8 T P t (c v) t=1 1 P (c i v) 4 5 2 3 7 6
I i Ici ξ c = [c = c i ] i I 1 C
RTs 480 3 2 1 25 4 0 640
480 ΔE 0.68 x 393 0 393 640
480 0 233 640 ΔE 0.04 x 233
480 212 0 640 ΔE 0.23 y 227
() 480 0 256 640 ΔE 0.0 x 256
SIFT Sinha, Sudipta: SIFT-GPU 2006 Bay et al.: SURF Lowe: SIFT 1999 2006 Ke, Sukthankar: PCA-SIFT 2004 Mikolajczyk, Schmid: GLOH 2005
SIFT SURF SIFT http://vision.ucla.edu/~vedaldi/code/siftpp/siftpp.html SURF OpenCV2.1 SIFT-GPU http://cs.unc.edu/~ccwu/siftgpu/
SIFT Lepetit, Fua: RTs 2006 Sinha, Sudipta: SIFT-GPU 2006 Bay et al.: SURF Lowe: SIFT 1999 2006 Ke, Sukthankar: PCA-SIFT 2004 Mikolajczyk, Schmid: GLOH 2005
Keypoint Recognition using Randomized Trees [Lepetit et al., 2006]
LoG
Iσ R R
R LoG 50 R [pixel] 100
x, y : x, y :
Randomized Trees N
32 32 入 力力 1 2 N = c
2 m P Iσ
4 m P Iσ
SIFT v u o u,v 4 4 o
SIFT 18 5
SiftGPU 19 6
SURF 25 13
Randomized Trees 38 38
Randomized Trees
[, et al., 2010] ViewpointKeypointRandomized Trees
:Randomized Trees
:Randomized Trees
z
Viewpoint
1 :Viewpoint Randomized Trees
1 :Viewpoint Randomized Trees
1Viewpoint
1Viewpoint
2 :Keypoint Randomized Trees 1 1 1 T 2 1 1 1 1 Viewpoint 1 2 2 2 T2 2 1 2 2 2 Viewpoint 2 K K K T2 2 1 K K K Viewpoint K
2 : Keypoint
100 95 2RTs ASIFT 90 85 80 RTs SURF SIFT 75 70 10 100 1000 10000 100000
Fast Keypoint Recognition using Random Ferns [Özuysal et al.,2010] 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 2 3 4 5 6 7 0 1 1 (011)2 = 3 ci
Ferns 2 Ferns c1 c2 c3 Fern 1 Fern 2 Fern T
Ferns Ferns c1 c2 c3 (010)2 (110)2 (011)2
Randomized Trees
1
2
3