Real AdaBoost HOG 2009 3 A Graduation Thesis of College of Engineering, Chubu University Efficient Reducing Method of HOG Features for Human Detection based on Real AdaBoost Chika Matsushima

ITS Graphics Processing Unit (GPU) [1] Large Scale Integration (LSI) Field Prgramble Gate Array (FPGA) [2] Edge of Orientation Histograms (EOH) [3] Histograms of oriented gradients (HOG) [4] Y.Linde Linde-Buzo-Gray (LBG) [6] Real AdaBoost HOG HOG HOG Real AdaBoost iii

3 1 2 Real AdaBoost HOG 3 iv

1 1 1.1... 1 1.1.1 LBG [6]... 2 1.2... 3 1.2.1... 4 1.2.2... 5 2 Real AdaBoost HOG 7 2.1 HOG... 7 2.1.1... 8 2.1.2... 8 2.1.3... 9 2.1.4... 9 2.2 HOG... 10 2.3 HOG... 10 2.4 Real AdaBoost... 11 2.4.1... 13 2.4.2... 13 2.4.3... 14 2.4.4... 16 2.4.5... 16 2.4.6... 16 2.4.7... 17 v

3 19 3.1... 19 3.1.1... 19 3.2 1... 19 3.2.1 1... 20 3.3 2... 20 3.3.1 2... 21 23 25 27 vi

1.1... 2 1.2 LBG... 3 1.3... 4 1.4... 5 2.1 HOG... 8 2.2... 9 2.3 HOG... 10 2.4 1... 11 2.5 Real AdaBoost... 12 2.6 Real AdaBoost... 13 2.7... 15 3.1... 20 3.2... 21 vii

3.1 1... 21 ix

1 1.1 1 3 ( 1.1 ) 1. LBG 2. 3. LBG 1

1 1.1.1 LBG [6] 1.1: LBG Y.Linde [6] 1 LBG LBG ( 1.2 ) 2 1. (M= ) 1 (L ) ( ) k {x 1, x 2,, x k } x (1.1) x = C (x 1, x 2,, x k )=argmin x n 1 1 n i=0 d (x, x i ) (1.1) d (x, x i ) x x i argmin f (x) f (x) x x x 2.

1.2. M 2 2 2 ɛ 2 ɛ 1/100 3. ( ) 4. 5. ( ) 1.2: LBG M 2 1.2 1.3 3

1 1.3: 1.2.1 N d x n = [x n1,x n2,x n3,,x nd ] T M S (1.2) (1.3) M = 1 N S = 1 N N x n (1.2) n=1 N (x n M)(x n M) T (1.3) n=1 2 S 1.3 Su j = λ j u j λ j u j d d (u 1 u 2 u d ) 4

1.2. 1.2.2 1.4 1.4: 5

2 Real AdaBoost HOG Real AdaBoost HOG 2.1 HOG Dalal Histograms of oriented gradients(hog) [4] HOG 2.1 (5 5 ) HOG Step1 Step2 Step3 HOG 2.1 1 30 60 HOG 5 5 3 3 7

2 Real AdaBoost HOG 5 5 2.1: HOG 2.1.1 1 2.1.2 L(x y) m θ (2.1) (2.2) m(x, y) = (L(x +1,y) L(x 1,y)) 2 +(L(x, y +1) L(x, y 1)) 2 (2.1) θ(x, y) = tan 1 ((L(x, y +1) L(x, y 1))/(L(x +1,y) L(x 1,y))) (2.2) 8

2.1. HOG 2.1.3 0 360 0 180 22.5 8 2.2 2.2: 2.1.4 i j (i, j) (8 ) F ij =[f 1 f 1 f 8 ] k (72 V k =[F ij F i+1j F i+2j F ij+1 F i+1j+1 F i+2j+1 F ij+2 F i+1j+2 F i+2j+2 ] L2-norm (2.3) Vf = f V 2 2 + ɛ 2 (2.3) 8 3 3 6 2 12 2 = 2880 1 8 ( ) 1 HOG 23,040 (22.5 ) 9

2 Real AdaBoost HOG 2.2 HOG 1 HOG 2.3 HOG 2.3: HOG 1 0 8 1 360 1 1 ( ) 64 1 2.3 HOG Real AdaBoost 2.4(a) 8 1 (256 = 2 8 ) 2 1 W +,W 0 (2.10) h(x) 10

2.4. Real AdaBoost 2.4: 1 2 2.4 A B C 2.4 Real AdaBoost Real AdaBoost Real AdaBoost 2.5 Real AdaBoost Real AdaBoost 2.3 Real- AdaBoost 2.4(b) 11

2 Real AdaBoost HOG 2.5: Real AdaBoost 1 h(x) 2 2 2.4(a) A B C 2.7 RealAdaBoost 12

2.4. Real AdaBoost 2.6: Real AdaBoost 2.4.1 D D 1,i = 1 N (2.4) 1 2.4.2 W + W W ± 1 D t W+ = D t (i) (2.5) W = i: J y i =+1 i: J y i = 1 D t (i) (2.6) 13

2 Real AdaBoost HOG t i j y i y {1, 1} i j D t (i) W ± W ± 1 2.4.3 2.7 h j (x) (2.10) j = arg max 0 j bin ( h j(x) ) arg min 0 j bin ( W j + W j ) max ( h j(x) ) 2 0 j bin otherwise (2.7) j W +,W h j (x) (2.14) H(x) 14

2.4. Real AdaBoost r j = W j + W j (2.8) j j 2.3 8 HOG 8 1 (2.8) 2.7: j j 0 j j = arg min 0 j <8 (r j r j ) (2.9) j j 15

2 Real AdaBoost HOG 2.4.4 W + W h(x) x j W ± h(x) h(x) = 1 2 ln W + + ɛ W + ɛ (2.10) ɛ 0 ɛ =10 10 2.4.5 W ± Z Z =2 j W j +W j (2.11) Z Z t h t = arg min Z t,m (2.12) 2.4.6 (2.13) D t+1 (i) =D t (i)exp[ y i h t (x i )] (2.13) 16

2.4. Real AdaBoost 2.4.7 2.4.2 2.4.6 T H(x) = sign( h t (x)) (2.14) t=1 t h(x) 17

3 3.1 2 1 2 3.1.1 Positive 2,053 Negative 6,253 Positive 5 3.1 3.2 1 HOG 1,000 1,234 (Miss Rate) (False Positive Rate) Detection Error Tradeoff(DET) 19

3 3.1: 3.2.1 1 HOG 3.2 3.2 0.025 0.03 5% 30% 3.3 2 HOG (VQ) 5.0% 1 (720 480 ) 1 50000 20

3.3. 2 3.2: 3.3.1 2 3.1 64 3.1 256 64 12.0% 98.0% 3.1: 1 [%] [MB] HOG [4]( ) 74.3 1098.63 HOG(64 VQ) 63.8 198.75 256 63.8 128 76.4 17.17 64 76.4 32 74.3 21

HOG Real AdaBoost HOG 2.0% 23

25

[1] L.Zhang and R.Nevatia: Efficient Scan-Window Based Object Detection using GPGPU, Computer Vision and Pattern Recognition 2004. [2] N.Vinod, L.Pierre-Olivier, and C.James J.: An FPGA-Based People Detection System, EURASIP Journal on Applied Signal Processing, Vol.2005, pp.1047-1061, 2005. [3] K.Levi and Y.Weiss: Learning Object Detection from a Small Number of Examples: the Importance of Good Features, In Proc. IEEE Conf. on Computer Vision and Pattern Recognition 2004, Vol.2, pp.53-60, 2004. [4] N.Dalal and B.Triggs: Histograms of Oriented Gradients for Human Detection, In Proc. IEEE Conf. on Computer Vision and Pattern Recognition 2005, Vol.1, pp.886-893, 2005. [5] B.M.Oliver, J.R.Pierce, and C.E.Shannon: The Philosophy of PCM, Proceedings of the Institute of Radio Engineers, vol.36, no.11, pp.1324-1331, 1948. [6] Y.Linde, A.Buzo, and R.M.Gray: An Algorithm for Vector Quantizer Design, IEEE Trans. on Communications, vol.28, no.1, pp.84-95, 1980. 27

Real AdaBoost HOG ( ) 2009 3