IS2-26 第 19 回 画 像 センシングシンポジウム, 横 浜,2013 年 6 月 SVM E-mail: yuhi@vision.cs.chubu.ac.jp Abstract SVM SVM SVM SVM HOG B-HOG HOG SVM 6.1% 17 1 Intelligent Transport System(ITS: ) 2005 Dalal HOG SVM[1] [2] HOG SVM [3][4] [5] HOG [6] GPU[7] GPU fast HOG[8] CPU 95 AdaBoost[9] [10] SVM SVM SVM SVM HOG B-HOG [11] B-HOG HOG 1/8 HOG 2 B-HOG B-HOG 2 Algorithm 1 IS2-26-1
第19回画像センシングシンポジウム 横浜 2013年6月 図1 ラスタスキャンベースの物体検出 Algorithm 1 ラスタスキャンによる物体検出 Require: 入力画像 I 1. 画像 I に対して検出ウィンドウをラスタスキャン for k = 1 to K do //K : 検出ウィンドウの総数 2. 検出ウィンドウ I(k) から特徴ベクトル xk を抽出 3. 識別器 F (xk ) の出力値を算出 4. 閾値 th により対象のラベル y に判定 yk = 1 1 if F (xk ) > th otherwise 図2 end for //ラスタスキャン終了 return y1, y2,..., yk HOG 特徴量 θ(x, y) = tan 1 を示す 物体検出を実現するには図 1 に示すように 入 力画像 I に対して検出ウィンドウを網羅的にラスタス キャンする そして ラスタスキャンして得られた全て Ly (x, y) Lx (x, y) Lx (x, y) = L(x + 1, y) L(x 1, y) Ly (x, y) = L(x, y + 1) L(x, y 1) (2) (3) の検出ウィンドウに対して特徴ベクトルを抽出し 事前 算出した勾配方向 θ は 0 360 の値で算出されるが に統計的学習手法により構築した識別器を用いて ク 180 より大きくなる方向は 180 引いて 0 180 と ラス yk を検出対象の場合 1 非検出対象の場合-1 とし する これにより 検出対象と背景領域の輝度の明暗 て判別する 関係に依存しない勾配方向を得ることができる 次に 人を検出対象としたラスタスキャンベースの物体検 算出した勾配強度 m と勾配方向 θ を用いて 式 (4) に 出手法には 2005 年に Dalal らが提案した HOG 特徴 よりセル c (M M ピクセル) における勾配方向ヒス 量と線形 SVM による手法 [2] が多く用いられている トグラム V c = {vc (1), vc (2),..., vc (N )} を作成する HOG 特徴量を小規模なハードウェアで実装するために vc (n) = M M m(x, y)δ[f (θ(x, y)), n] (4) HOG 特徴量を 2 値化した B-HOG 特徴量 [11] が提案 されている 本章では HOG 特徴量 B-HOG 特徴量 線形 SVM[1] により構築した識別器とその問題点つい ここで n = 1, 2,..., N はヒストグラムのビンの番号 て述べる f (θ) は勾配方向 θ を N 方向に量子化した値 δ[ ] はク 2.1 x y ロネッカーのデルタ関数を表しており 二つの要素が HOG 特徴量 等しい場合は 1 それ以外は 0 を出力する関数である Histograms of Oriented Gradients(HOG) 特徴量 [2] このように セル c 毎にヒストグラム化することによ は図 2 に示すように 検出ウィンドウからセルと呼ば り 局所領域内の微小な幾何学的変化に対して頑健な れる局所領域毎に作成した勾配方向ヒストグラムを特 特徴量となる 最後に 式 (5) を用いて各セル c で作成 徴量とする また 複数のセルで構成されるブロック した勾配方向ヒストグラム V c を 複数のセルで構成 領域毎に特徴量を正規化することで 照明変化や幾何 されるブロック領域 (R R セル) ごとに正規化する 学的変化の影響を受けにくい特徴量となる vc (n) vc (n) = q vc (k)2 + 算出手順は はじめに検出ウィンドウ中の各ピクセ ルの輝度値 L(x, y) の勾配強度 m と勾配方向 θ を式 (1) 式 (3) より算出する m(x, y) = Lx (x, y)2 + Ly (x, y)2 ( = 1) (5) k=1 (1) ここで q はブロック領域内の勾配方向の数 (R R N ) は分母が 0 になることを防ぐための定数である ブロッ IS2-26-2
x sv x SVM F (x) x (D ) w = J j=1 y jα j x sv j (8) 3 B-HOG 1 V c V c = {v c(1),v c(2),..., v c(q)} 64 128 {(64/M ) (R 1)} {(128/M ) (R 1)} M =8 R =2 N =8 105 HOG 2 2 8 105 = 3, 360 x 2.2 B-HOG B-HOG [11] 3 HOG 2 HOG V c (6) th bhog 2 P c = {p c(1),p c(2),..., p c(q)} p c(n) = { 1 if v c(n) >th bhog 0 otherwise (6) th bhog HOG B-HOG M =8 R =2 N =8 3,360 HOG 1/8 B-HOG HOG 2 2.3 SVM Support Vector Machine(SVM)[1] SVM SVM (7) F (x) F (x) = J j=1 y j α j < x sv j, x > (7) J α y < x sv, x > F (x) = w T x (8) D = w i x i (9) x k F (x k ) y k 2.4 VGA (640 480 ) I l w l h l s l m K K = (640 l w l s 1) (480 l h l s 1) l 2 m (10) (l w,l h ) = (64, 128) l s =1.0 2.0 l m =4 2 F (x k ) GPU HOG [8] SVM SVM SVM 3 SVM SVM HOG B-HOG IS2-26-3
3.1 SVM SVM F (x) (8) x w Hare [12] SVM SVM w β b { 1, 1} D Algorithm 2 w Algorithm 2 w 4 N b w Require: w N b 1. : SVM w r r = w 2. w β b for i =1toN b do //N b : 2.1 r {-1,1} 2 b i b i = sign(r) 2.2 r b i β i = < r, bi > b i 2 2.3 r r r β i b i end for return {β i} N b {bi}n b SVM F (x) w β b F (x) f(x) = N b β ib T i x b b + {0, 1} D b + (b = b + b + ) (11) SVM < b + i, x > x f(x) = = = N b N b N b β i b T i x β i (< b + i, x > < b + i, x >) β i (2 < b + i, x > x ) (11) x B-HOG x {0, 1} D < b + i, x > x 5 SVM SSE4.2 CPU POPCNT 3.2 N b SVM N b 4 w β b N b w N b SVM N b N b 5 N b SVM 5 SVM N b N b SVM IS2-26-4
5 2 SVM 2 y th SVM N b N b th 3.3 N b N b Algorithm 3 Algorithm 3 Require: I 1. I for k =1toK do //K : 2. I(k) x k 3. f(x k ) 0 4. for i =1toN b do //N b : 4.1 SVM : β i(2 < b + i, x k > x k ) f(x k )+=β i(2 POPCNT(b + i & x k ) POPCNT(x k )) 4.2 if f(x k ) >th pos or f(x k ) <th neg then break // end if end for //N b 5. th y { 1 if f(xk ) >th y k = 1 otherwise end for // return y 1,y 2,..., y K th pos th neg y =1 y = 1 ( ±1.0) th pos <f(x) <th neg 6 SVM N b SVM 6 SVM SVM 3.4 3.1 HOG B-HOG B-HOG HOG 2 B-HOG 2 B-HOG P c1 P c2 (12) (14) (AND) (OR) (XOR) P and c 1,c 2 = P c1 & P c2 (12) P or c 1,c 2 = P c1 P c2 (13) P xor c 1,c 2 = P c1 ˆ P c2 (14) R =2 6 P operator = {P c1,c 2, P c1,c 3, P c1,c 4, P c2,c 3, P c2,c 4, P c3,c 4 } AND 2 1 OR 2 1 2 0 XOR 2 1 2 IS2-26-5
7 B-HOG 0 7 B-HOG M =8 R =2 N =8 3,360 B-HOG 5,040 8,400 B-HOG 8,400 x 4 4.1 INRIA Person Dataset[2] 2,416 13,161 1,126 453 1,306,029 64 128 INRIA Person Dataset 433 8 DET 4.2 HOG + SVM B-HOG + SVM ( ) B-HOG SVM B-HOG AND OR XOR Detection Error Trade-off(DET) DET OS:Windows Server 2008 Enterprise x64 CPU:Intel Xeon CPU X7542 @ 2.67GHz RAM:256GB PC SVM SVM Light[13] M =8 R =2 N =8 SVM N b =16 4.3 DET 8 DET SVM B-HOG HOG (AND) (OR) B-HOG HOG (XOR) 0.1% HOG + SVM 6.1% XOR B-HOG 9 B-HOG IS2-26-6
9 1 [%] [ms] [%] [ms] SVM 94.16 0.034 (N b =16) 94.08 0.013 (N b =2) 91.07 0.002 94.08 0.002 XOR AND OR 27 AND OR 19 XOR 0 AND OR 1 4.4 10 1 XOR 1 N b =16 SVM SVM 3 SVM 17 7.78 1.46 N b =2 VGA (640 480 ) (l w,l h ) = (64, 128) l s =1.0 2.0 l m =4 SVM 674.2[ms](1.48[fps]) 39.66[ms](25.21[fps]) 11 10 (a) (b) (c) (d) (N b = 16) 9 1 ( ) ( ) 11 N b SVM SVM IS2-26-7
2 [Byte] [%] [ms] [Byte] [%] [ms] HOG 3360 3360 88.69 1.554 B-HOG 3360 420 84.89 1.561 (XOR) 8400 1050 94.08 1.576 3360 420 86.57 50.989 Random Projection 8400 1050 87.63 128.059 23520 2940 88.69 360.219 1/3 GPU fast HOG[8] 12 Random Projection 4.5 Random Projection[14] 12 Random Projection HOG Random Projection HOG 23,520 2 (XOR) 6.1% 8,400 (XOR) 1.576[ms] HOG 1.554[ms] 5 2 1. SVM 2. B-HOG 1. SVM 17 2. B-HOG [1] C.Cortes and V.Vladimir, Support-Vector Networks, Machine Learning, vol.20, no.3, pp.273 297, 1995. [2] N. Dalal, and B. Triggs, Histograms of Oriented Gradients for Human Detection, Computer Vision and Pattern Recognition, vol.1, pp.886 893, 2005. [3] X.Wang, T. X. Han and S. yan, An HOG-LBP human detector with partial occlusion handling, International Conference on Computer Vision, pp.32 39, 2009. [4] C.Wojek, S. Walk, S. Roth and B. Schiele, Monocular 3D scene understanding with explicit occlusion reasoning, Computer Vision and Pattern Recognition, pp.1993 2000, 2011. [5] P.F.Felzenszwalb, R.B. Girshick, D.McAllester, and D.Ramanan, Object Detection with Discriminatively Trained Part Based Models, Pattern Analysis and Machine Intelligence, vol.32, no.9, pp.1627 1654, 2010. [6] Q.Zhu, S.Avidan, M.Yeh and K.Cheng, Fast Human Detection Using a Cascade of Histograms of Oriented Gradients, Computer Vision and Pattern Recognition, pp.1491 1498, 2006. [7] V.Prisacariu and I.Reid, Fast Human Detection with Cascaded Ensembles on the GPU, Intelligent Vehicles Symposium, pp.325 332, 2010. [8] V.Prisacariu and I.Reid, fasthog - a real-time GPU implementation of HOG, Departmentof Engineering Science, no.2310/9, 2009. [9] Y. Freund, and R. E. Schapire, Experiments with a new boosting algorithm, International Conference on Machine Learning, pp.148 156, 1996. [10] P. Viola and M. Jones, Rapid object detection using a boosted cascade of simple features, Computer Vision and Pattern Recognition, vol.1, pp.511 518, 2001. [11],,,, Relational HOG, D, vol.j94-d, no.8, pp.1172 1182, 2011. [12] S. Hare, A. Saffari and P. H. S. Torr, Efficient online structured output learning for keypoint-based object tracking, Computer Vision and Pattern Recognition, pp.1894 1901, 2012. [13] T. Joachims, SVM light, http://svmlight.joachims.org [14] M.X.Goemans, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, vol.42, pp.1115 1145, 1995. IS2-26-8