色の類似性に基づいた画像認識の高精度化と高速化に関する研究
指導教授：藤吉 弘亘

後藤 雄飛

1. はじめに本研究では，(1) 色の類似性に基づいた画像認識の高精度化と，(2) 物体検出の高速化に関する研究について取り組んだ．本稿では，(2) の物体検出の高速化に関する研究について述べる．
物体検出は入力画像に対して検出ウィンドウをラスタスキャンし，各検出ウィンドウから抽出した特徴ベクトルを線形 SVM 等の識別器に入力して判定することで実現している (図 1)．VGA の画像に対して，ラスタスキャンにより発生する検出ウィンドウは約 2 万個と多く，物体検出の高速化には特徴抽出と識別の各処理を高速に計算する必要がある．そこで，本研究では線形 SVM の近似計算法 [1] を導入し，識別器の演算量を削減することを目的とする．提案手法では検出ウィンドウに対して，近似計算結果による早期判定を導入することでラスタスキャンの高速化を実現する．また，入力特徴量のバイナリコードにおいて共起表現を用いることで，識別性能の高精度化を実現する．

ここで，入力特徴ベクトル x がバイナリコードである場合，内積 < b+i , x > とノルム |x| は論理積とビットカウントで計算することが可能である．バイナリコードの論理積は実数に比べて高速に演算することができる．また，ビットカウ
ントは SSE4.2 から CPU に直接実装されている POPCNT関数を用いることで，非常に高速な演算が可能である．

2.2 近似計算の打ち切りによるラスタスキャンの高速化
線形 SVM の近似計算では高次元の特徴ベクトルを扱う
場合，基底数 Nb を多く用いる必要がある．基底数 Nb による識別精度と速度はトレードオフの関係にあり，膨大な検出ウィンドウを高速に処理するためには基底数 Nb をできるだけ削減したい．そこで，本研究では近似計算過程における計算結果から早期判定を導入することで，ラスタスキャンの高速化を行う．
少ない基底数 Nb で近似した出力値が関数マージンより離れているサンプルは，基底数 Nb を増やしても識別結果が変わることはない．そこで，図 3 のアルゴリズムにより識別器の近似計算を打ち切り，識別結果の早期判定を行う．



1. 入力画像 I に対して検出ウィンドウをラスタスキャン
For k = 1, · · · , K

図 1 : 物体検出の流れ

2. 物体検出の識別器の高速化

2. 識別器の出力値を算出

本研究では，線形 SVM を近似計算して識別器の高速化と，近似計算の打ち切りによるラスタスキャンの高速化を実現する．

For i = 1, · · · , Nb

線形 SVM により学習した識別器は式 (1) に示すように，重みベクトル w と入力特徴ベクトル x の内積計算により出力値 F (x) を算出する．
F (x) = wT x(1)このような実数ベクトル間の内積計算は計算コストが高い．
そこで，Hare 等によって提案された近似計算法 [1] を利用して線形 SVM の高速な識別を実現する．図 2 に示す近似計算法により，重みベクトル w を実数ベクトル β と基底バイナリコード b に近似する．近似計算法は，ビット演算を利用して識別計算を行うことで高速な識別が可能となる．

1. 初期化 : 線形 SVM の重みベクトル w を実数ベクトル r に格納
r=w
2. w を実数ベクトル β と基底バイナリコード b に近似//Nb : 最大基底数・ 線形 SVM の近似計算

f (xk ) += βi (2 < b+i , xk > −|xk |)2.1 近似計算法による識別器の高速化

For i = 1, · · · , Nb//K : 検出ウィンドウの総数

・ 検出ウィンドウ I(k) から特徴ベクトル xk を抽出

・計算結果を判定

If

f (xk ) > thpos or f (xk ) < thneg
Break//近似計算の打ち切り

End if
End for//Nb まで近似計算

3. 閾値 th により判定{1if f (xk ) > thyk =−1
otherwise
End for//ラスタスキャン終了
Return y1 , y2 , ..., yK

図 3 : 提案手法による物体検出アルゴリズム

近似計算を打ち切る閾値 thpos ，thneg には，学習により求めた線形 SVM の識別境界 th から ±1.0 の出力を持つサポートベクタを使用する．提案手法は，図 4 に示すように，識別器の出力が関数マージンから離れたサンプルの近似計算を打ち切り，関数マージン内の識別が困難なサンプルは基底数 Nb を増やし近似計算を継続する．これにより，膨大な検出ウィンドウに対して線形 SVM の性能を維持しつつ高速な識別計算が可能となる．

//Nb : 基底数・ 実数ベクトル r を {-1,1} に 2 値化して基底バイナリコード bi を算出

bi = sign(r)・ 実数ベクトル r と基底バイナリコード bi の内積< r, bi >βi =||bi ||2・ 近似による残差を実数ベクトル r に代入r ← r − βi bi
End forNbNbReturn {βi }i=1，{bi }i=1

図 2 : 重みベクトル w の近似アルゴリズム

線形 SVM は重みベクトル w を近似した実数ベクトル
β と基底バイナリコード b を用いて，F (x) ≈ f (x) =∑Nb
β b x と近似することができる．さらに，式 (2) にi=1 i i+示すように基底バイナリコード b を b+ ∈ {0, 1}N と b̄+に分解 (b = b+ − b̄ ) することで，内積 < b+i , x > とノルム |x| を利用した式に変形できる．

f (x) =Nb∑i=1βi bi x =Nb∑i=1βi (2 < b+i , x > −|x|)(2)図 4 : 線形 SVM の近似計算の打ち切り

2.3 B-HOG 特徴量の共起表現による高精度化提案手法では，バイナリコードの特徴ベクトルに B-HOG特徴量を利用する．B-HOG 特徴量は閾値処理により HOG
特徴量を 2 値化したバイナリコードで物体形状を表現する．
B-HOG 特徴量は HOG 特徴量の 1/8 のメモリ量で特徴表現が可能であるが，2 値化の際の量子化誤差の影響により表現能力が低下する問題がある．そこで，図 5 に示すように，ブロック領域で論理演算を用いて共起表現したコードを追加して特徴表現能力を向上を目指す．2 つのセルの

図 6 : DET カーブのときの近似計算法は，提案手法と同じ処理時間となるが検出率は低下する．
表 1 : 各識別器の検出率 [%] と処理時間 [ms]図 5 : 論理演算による B-HOG 特徴量の共起表現
バイナリコードを論理演算することで，セル間の勾配の関係性を表現することが可能となる．論理演算子には論理積 (AND)，論理和 (OR)，排他的論理和 (XOR) を用いる．
例えば XOR の場合，2 つのセルに共通しない勾配を 1のビットで表現する．共起表現を追加した特徴量は 3,360ビットの B-HOG 特徴量に対して 5,040 ビットのバイナリコードを結合するため，8,400 ビットのバイナリコードとなる．本研究では，近似計算法により高速な識別を行うた
め，B-HOG 特徴量を共起表現したバイナリーコードを入力特徴ベクトル x として用いる．

3. 評価実験
提案手法の有効性を示すために識別精度と処理時間を従来法と比較する．

識別器

検出率 [%]

処理時間 [ms]線形 SVM
近似計算法 (Nb =16)
近似計算法 (Nb =2)
提案手法

95.05
94.96
92.76
94.96

0.034
0.013
0.0020.002

図 7 は，近似計算の打ち切りの割合を示している．図 7 より，近似計算の打ち切りにより基底数 Nb が 5 までに約 5割のポジティブサンプルが早期判定されている．また，ネガティブサンプルは基底数 Nb が 1 のときに約 9 割のサンプルが早期判定されている．図 7 に示す画像は，任意の基底数にて早期判定されたサンプル例と平均勾配画像である．
基底数が少ない段階では，各クラスらしいサンプルの識別結果が早期判定され，異なったクラスに分類されやすいような識別が困難なサンプルは最大まで (Nb = 16) 継続して近似計算が行われる．このように，提案手法は入力サンプルに応じて適応的に識別結果を早期判定することで，線形SVM の性能を維持しつつ高速な識別を実現した．

3.1 実験概要
データセットには INRIA Person Dataset を使用する．
学習サンプルにはポジティブサンプル 2,416 枚，ネガティブサンプル 13,161 枚を使用する．評価サンプルにはポジティブサンプル 1,126 枚，ネガティブサンプル 9,060 枚を使用する．識別精度の評価には Detection Error Tradeoﬀ(DET) カーブを用いる．DET カーブは横軸に誤検出率，縦軸に未検出率を表しており，原点に近いほど高精度であることを表す．実験環境は，OS:Windows Server
2008 Enterprise x64，CPU:Intel Xeon CPU X7542 @2.67GHz，RAM:256GB を用いる．評価実験では予備実験の結果より，基底数 Nb は 16 とする．

3.2 実験結果 : 識別精度の比較

実験結果の DET カーブを図 6 に示す．DET カーブより，線形 SVM を用いた B-HOG 特徴量は HOG 特徴量と比較して識別精度が低下している．一方，提案手法 (AND)及び (OR) は B-HOG 特徴量と同様のバイナリコードの特徴量であるが，HOG と同等の識別率を得た．さらに，提案手法 (XOR) は誤検出率 0.1% において従来法 (HOG 特徴量+線形 SVM) と比較して約 8.1% 識別精度が向上している．これは，XOR による 2 つのセルに共通しない勾配の表現が人検出に効果的に働いたためと考えられる．

3.3 実験結果 : 処理速度の比較
表 1 に，共起表現 (XOR) した特徴ベクトルを用いたときの各識別器の検出率と処理時間を示す．近似計算法は基底数 Nb = 16 のとき，線形 SVM の検出精度と同等である．
処理時間を比較すると，近似計算法は線形 SVM よりも約3 倍高速な演算が可能である．提案手法は近似計算法よりもさらに速く，線形 SVM と比較して約 17 倍高速な演算を実現した．このとき，提案手法は平均で 2.17 回の基底数で近似計算を打ち切り早期判定している．基底数 Nb = 2

図 7 : 近似計算の打ち切りの割合

4. おわりに本研究では，入力サンプルに応じて適応的に線形 SVMを近似計算して識別結果を早期判定することで，線形 SVMの性能を維持しつつ高速な識別を実現した．今後は，バイナリコードによる特徴ベクトルの抽出過程を高速化し，特徴量と提案手法の識別器を組み合わせてリアルタイムな処理が可能な物体検出器を設計する予定である．

参考文献[1] S. Hare, A. Saﬀari and P. H. S. Torr, Eﬃcient online structured output learning for keypoint-based object tracking ,Computer Vision and Pattern Recognition, pp.1894–1901,
2012.

研究業績
[1] Yuhi Goto, Yuji Yamauchi and Hironobu Fujiyoshi.
CS-HOG : Color Similarity-based HOG”, 19th KoreaJapan Joint Workshop on Frontiers of Computer Vision(FCV2013), GO2-2, pp.299–304, 2013.
（他 学会口頭発表 2 件，研究会技術報告 1 件）

受賞
[1] SSII2012 オーディエンス賞，優秀学術賞