論文

近似計算を導入した線形識別器の早期判定による高速な識別後藤雄飛† a)

藤吉

弘亘† d)

土屋成光† b)

山内悠嗣† c)

Fast Discrimination by Early Judgment Using Linear Classifier Based on
Approximation Calculation
Yuhi GOTO†a) , Masamitsu TSUCHIYA†b) , Yuji YAMAUCHI†c) ,and Hironobu FUJIYOSHI†d)

あらまし 物体検出は，入力画像を網羅的にラスタスキャンさせて得られる，膨大な数の検出ウィンドウを検出対象か非検出対象に分類する．各検出ウィンドウは，抽出した局所特徴量と統計的学習手法により学習した識別器により出力値を算出し，対象のクラスに分類する．近年では，物体検出に一般的に利用されている線形 SVMにより学習した識別器を，対応点追跡の問題において近似計算をして高速な識別を実現する方法がある．そこで，
本研究では物体検出に対して線形 SVM の近似計算法を導入し，ラスタスキャンに伴い発生する識別処理の高速化を検討する．更に，提案手法では近似計算結果に応じて識別器の出力値を早期判定する．これにより，入力された検出ウィンドウに対して，近似計算に必要な基底数を適応的に判断して分類することで線形 SVM の高速な識別を可能にする．また，提案手法では線形 SVM を近似計算する際に用いる，HOG 特徴量をバイナリコー
ド化した B-HOG 特徴量を共起表現して物体検出の高精度化を行う．人検出による評価実験より，提案手法はHOG 特徴量と線形 SVM による物体検出手法と比較して，約 6.1% 高精度な識別に加えて，約 17 倍高速な識別計算を実現した．
キーワード

早期判定，線形 SVM，内積近似計算，人検出

1. ま え が きンした際に発生する膨大な数の検出ウィンドウを識別処理する必要があり，高速な物体検出を実現するには

物体検出は，学習サンプルから抽出した局所特徴量

各検出ウィンドウの処理である特徴抽出過程と識別過と統計的学習手法を用いて学習した識別器により実程をそれぞれ高速化する必要がある．特徴抽出過程の現されている．代表的な物体検出として，2005 年に高速化としては，HOG 特徴量の算出に積分画像 [6] やDalal らは HOG 特徴量と線形 SVM [1] による人検GPU [7] を利用する手法が提案されている．中でも，

出法 [2] を提案した．HOG 特徴量と線形 SVM の組

GPU で実装された fast HOG [8] は，CPU による特み合わせは，検出対象の隠れの推定 [3], [4] やパーツモ

徴抽出と比較して約 95 倍高速な処理を実現した．識デル [5] 等の物体検出の高精度化に関する研究におい別過程では，AdaBoost [9] をカスケード型に構成し，ても，ベースとなる手法として用いられている．この非検出対象を早期判定することにより高速化する手ような物体検出の実用化には識別性能の高精度化だけ

法 [10] が提案されている．しかし，物体検出に多く利ではなく，検出過程の高速化と省メモリ化が課題であ用されている線形 SVM の高速化に関する検討は従来

る．検出過程では，入力画像を網羅的にラスタスキャ

行われていない．
そこで，本研究では線形 SVM による識別結果の早†中部大学情報工学科，春日井市

期判定を導入して識別器の高速化を検討する．提案手

Department of Computer Science, Chubu University, 1200

法は，検出ウィンドウから抽出した特徴ベクトルに応Matsumoto, Kasugai-shi, 487–8501 Japana) E-mail: yuhi@vision.cs.chubu.ac.jp

じて線形 SVM を近似計算し，識別結果を早期判定すb) E-mail: mtdoll@vision.cs.chubu.ac.jp

ることで高速な識別処理を実現する．このとき，線形c) E-mail: yuu@vision.cs.chubu.ac.jpd) E-mail: hf@cs.chubu.ac.jp294

電子情報通信学会論文誌

SVM の近似計算を高速に求めるために入力特徴ベクc 一般社団法人電子情報通信学会 2014
D Vol. J97–D No. 2 pp. 294–302 

論文／近似計算を導入した線形識別器の早期判定による高速な識別

トルはバイナリコードである必要があるため，提案手法では HOG 特徴量をバイナリコード化した B-HOG
特徴量 [11] を用いる．B-HOG 特徴量は HOG 特徴量と比較して 1/8 のメモリ量で特徴ベクトルを表現することができるが，HOG 特徴量を 2 値化した際の量
子化誤差の影響により，識別精度が低下するという問題がある．そこで，提案手法では B-HOG 特徴量のバ

図 1 B-HOG 特徴量
Fig. 1 B-HOG features.

イナリコードにビット演算を用いた共起表現を導入して，セル間の関係性を表現することで計算コストを最小限に抑えながら識別性能の高精度化を行う．このよ

こで，N はこう配方向ヒストグラムの量子化数である．



うに，本研究では識別器の早期判定による識別処理とB-HOG 特徴量の共起表現により，高精度でかつ高速

pc (n) =な物体検出を実現する．

2. ラスタスキャンベースの物体検出

vc (n) > thn

1

if

0

otherwise(1)

しきい値 thn は学習サンプルから得られる HOG 特徴量の各次元ごとの平均値を用いる．B-HOG 特徴量は

物体検出は，局所特徴量と統計的学習手法を用いて学習した識別器を利用する手法が一般的である．物体検出を実現するには入力画像 I に対して検出ウィンド
ウを網羅的にラスタスキャンする．そして，ラスタス
キャンして得られた全ての検出ウィンドウに対して特徴ベクトルを抽出し，事前に統計的学習手法により構築した識別器を用いて，クラス yk を検出対象の場合

1，非検出対象の場合 −1 として判別する．
人を検出対象としたラスタスキャンベースの物体検出手法には，2005 年に Dalal らが提案した HOG 特
徴量と線形 SVM による手法 [2] が多く用いられている．HOG 特徴量を小規模なハードウェアで実装するた
めに，HOG 特徴量を 2 値化した B-HOG 特徴量 [11]が提案されている．本章では，B-HOG 特徴量，線形SVM [1] により構築した識別器とその問題点ついて述
べる．

2. 1 B-HOG 特徴量
Histograms of Oriented Gradients (HOG) 特 徴
量 [2] は，検出ウィンドウからセルと呼ばれる局所

64×128 ピクセルの検出ウィンドウに対して，セルサイ
ズ M = 8 ピクセル，ブロックサイズ R = 2 セルの場合に {(64/M ) − (R − 1)} × {(128/M ) − (R − 1)} = 105
個のブロック領域により正規化処理が行われる．そのため，勾配方向ヒストグラムの量子化数 N = 8 のとき，一つの検出ウィンドウから得られるバイナリコー
ドは 2 × 2 × 8 × 105 = 3, 360 ビットとなり，HOG
特徴量と比べてメモリ量を 1/8 に削減することができる（注 1）．しかし，B-HOG 特徴量は HOG 特徴量と比較して，2 値化の際の量子化誤差の影響により物体検
出の識別精度が低下するという問題がある．

2. 2 線形 SVM による識別器
Support Vector Machine (SVM) [1] は，パターン認識手法において優れた認識性能をもつ統計的学習手法の一つである．コンピュータビジョンの分野においても非常に多くの研究に用いられ，物体検出においては線形 SVM が用いられることが多い．
線形 SVM における識別関数は式 (2) のように定義される．

領域ごとに作成した勾配方向ヒストグラムを特徴量とする．また，複数のセルで構成されるブロック領域ごF (x) = w T xとに特徴量を正規化することで，照明変化の影響を受けにくい特徴量となる．

B-HOG 特徴量 [11] は，図 1 に示すように HOG 特
徴量を 2 値化したバイナリコードで物体形状を表現す
る．HOG 特徴量により作成した勾配方向ヒストグラ
ム V c = {vc (1), vc (2), ..., vc (N )} を式 (1) に示すようにしきい値 thn により 2 値化することによりバイナリ
コード P c = {pc (1), pc (2), ..., pc (N )} を生成する．こ

=

D


wi xi

(2)

i=1

ここで，x は，D 次元の特徴ベクトル，w は特徴ベク（注 1）：予備実験より倍精度浮動小数点型で表現した HOG 特徴量と符号なし 8 ビット整数型で表現した HOG 特徴量の人検出性能は同等であった．本研究では，より実用的な比較として HOG 特徴量を符号なし
8 ビット整数型で表現するため，B-HOG 特徴量は HOG 特徴量よりも1/8 のメモリ量で表現される．

295

電子情報通信学会論文誌 2014/2 Vol. J97–D No. 2

トルに対する重みを表す．物体検出を行うためには，

Algorithm 1 Decomposition of the weight vector

ラスタスキャンにより得られた検出ウィンドウから抽w [12].

出した特徴ベクトル x に対して，識別器 F (x) の出力値を求め，しきい値処理することでクラスを判定する．

2. 3 問 題 点
VGA サイズ (640 × 480 ピクセル) の入力画像 I に対して横幅 lw ，縦幅 lh の検出ウィンドウをスケール

ls ，ずらし幅 lm にてラスタスキャンしたとき，発生する検出ウィンドウの数 K は次式により求めること
ができる．

K=

S


ﬂoor((640−lw ×ls −1) / lm )

ls =1
S


+

(3)
ﬂoor((480−lh ×ls −1) / lm )ls =1

Require: weight vector w, number of bases, Nb
1. Initialization: Store the weight vector w of the linear
SVM in real vector r.
r=w
Nb
2. Analyze w into a real vector {βi }i=1
and binary codeNb{bi }i=1//Nb : number of bases
for i = 1 to Nb do
2.1 Quantize real vector r to {-1,1}
and calculate base binary code bi .
bi = sign(r)2.2 Take the inner product of real vector r and basebinary code bi .
<r ,bi >βi =||bi ||2
2.3 Substitute the residual from the approximation into
the real vector r.
r ← r − βi bi
end forNbNb
return {βi }i=1
, {bi }i=1

ここで，ﬂoor() は床関数であり，入力された実数の小数点以下を切り捨てた整数を出力する．例えば，検出ウィンドウのサイズ (lw , lh ) = (64, 128) をマルチス

式 (2) に示すように特徴ベクトル x と重み w の内積

ケール S = 2 (ls = 1, 2) でずらし幅 lm = 4 としてラであり，膨大な数の検出ウィンドウを処理すると時間

スタスキャンした場合，検出ウィンドウは約 2 万個とを要するという問題がある．そこで，本研究では Hare

なる．これら全ての検出ウィンドウから特徴抽出を行らによって提案された近似計算法 [12] を利用して，実い，識別器 F (xk ) の出力値を求める必要があり，物体

数ベクトル間の内積をバイナリコード間の内積に置検出をリアルタイムに実現するためには，特徴抽出過

き換えることで，線形 SVM の高速な識別処理を実現

程と識別過程をそれぞれ高速化する必要がある．特徴する．

抽出過程の高速化としては，積分画像を用いた HOG

線形 SVM の近似計算法では，重みベクトル w を特徴量の高速化 [6] が提案されている．識別過程では，

実数ベクトル β と基底バイナリコード b ∈ {−1, 1}D

膨大な数の検出ウィンドウを処理する際に，線形 SVMに分解する．Algorithm 1 に重みベクトル w の分の実数ベクトル間の内積にかかる計算コストが高いと

解アルゴリズム [12] を示す．線形 SVM による識別いう問題がある．そこで，GPU を用いた線形 SVM

器 F (x) は，重みベクトル w を分解して求めた実数における内積計算の並列処理による高速化手法が提案

ベクトル β と基底バイナリコード b を用いることで，されている [8]．しかし，この高速化手法は GPU 等のF (x) ≈ f (x) =数百個規模の並列演算ユニットを別途必要とする．

きる．ここで，基底バイナリコード b を b

3. 提 案 手 法
本研究では，識別処理の高速化として線形 SVM に

と b̄

+

の共起性を表現することで，物体検出の高精度化を行

すように線形 SVM の近似計算を内積 < b+
i , x > とノ
ルム |x| により計算することができる．

f (x) =

3. 1 線形 SVM の近似計算
線形 SVM により学習した識別器 F (x) の計算は，
296

Nb


βi b T
i x

i=1

=

Nb


+

βi (< b+i , x > − < b̄i , x >)i=1

う．以下に提案手法による識別処理の高速化とバイナ
リコードにおける共起表現について述べる．

∈ {0, 1}+

トルのバイナリ化に伴う性能低下を解決するために，

HOG 特徴量をバイナリコード化した B-HOG 特徴量T
i=1 βi bi x と近似計算することがで+Dに分解 (b = b+ − b̄ ) することで，式 (4) に示

近似計算による早期判定を導入する．また，線形 SVMの近似計算に基づく高速化に必要となる入力特徴ベク

Nb

=

Nb


βi (2 < b+
i , x > −|x|)

(4)

i=1

ここで，入力特徴ベクトル x が B-HOG 特徴量のよ論文／近似計算を導入した線形識別器の早期判定による高速な識別

Fig. 2図 2 基底数 Nb による w の近似精度
Approximation accuracy of w by number ofbases Nb .
Fig. 3

うなバイナリコード x ∈ {0, 1}D である場合，内積

図 3 線形 SVM の近似計算結果
Results of linear SVM approximation calculations.

< b+
i , x > とノルム |x| は，それぞれ論理積とビットカウントからなるビット演算で計算することが可能で分けるような識別器のしきい値 th を設定する．そのある．このような，バイナリコード間の論理積は実数ため，線形 SVM の近似計算時に，少ない基底数 Nb間の積に比べて高速に演算することができる．また，

で関数マージンから離れた出力値をもつサンプルは，

ビットカウントは SSE4.2 から CPU に直接実装され基底数 Nb を増加してもしきい値 th による識別結果ている POPCNT 関数を用いることで高速な演算が可が変わることはないといえる．

3. 3 近似計算結果の早期判定による識別処理の高能である．

3. 2 基底数 Nb と近似計算結果

速化

我々は，線形 SVM の近似計算過程における基底数

基底数 Nb による識別精度と速度はトレードオフ

Nb と近似計算結果に着目する．図 2 は，近似計算のの関係にあり，膨大な検出ウィンドウを高速に処理す

基底数 Nb と誤差の関係をグラフで表したものである．

るためには基底数 Nb をできるだけ削減したい．そこ

誤差は重みベクトル w を実数ベクトル β 及び基底バ

で，提案手法では関数マージンを利用して近似計算

イナリコード b により近似した結果

Nbi=1 βi bi と重み過程における計算結果から早期判定を導入すること

ベクトル w との 2 乗誤差である．重みベクトル w ので，識別器の性能を維持したまま識別処理の高速化

近似精度は，基底数 Nb が増加するにつれて高くなっを行う．Algorithm 2 に近似計算結果の早期判定にていることがわかる．線形 SVM の識別精度を維持す

よる識別処理の高速化アルゴリズムを示す．ここで，るためには，基底数 Nb を多く用いて識別器を近似計

thpos 及び thneg はそれぞれ +1 及び −1 とした．ま

算する必要がある．その反面，高速な識別処理を行う

た，thpos < f (x) < thneg は関数マージン内を示してためには基底数 Nb をできるだけ削減して，識別器をおり，サポートベクタの出力値よりも識別境界に近い近似計算することが求められる．

値を表している．図 3 に示すように，正と負の方向に

図 3 は，データセットのサンプルを例に基底数 Nb

大きな値を出力した場合に線形 SVM の近似計算を打による線形 SVM の近似計算結果をグラフ化したもの

ち切り，識別結果を早期判定することが可能となる．

である．図 3 より，線形 SVM の近似計算では基底数関数マージン内の識別が困難な入力サンプルは，多く

Nb が少ない段階では，おおまかに識別器の出力値をの基底数 Nb を用いて線形 SVM との誤差の少ない近算出している．基底数 Nb が多くなるにつれて，線形似計算を行い判定をする．これにより，線形 SVM のSVM との誤差を埋めるように識別器の出力値が変化

識別精度を維持しつつ，検出ウィンドウによっては早している．また，図 3 の二つのサンプルは基底数が少期判定することで高速な識別処理が可能となる．

ない段階で，線形 SVM の関数マージンから離れた出

3. 4 バイナリコードにおける共起表現

力値となっている．精度の良い物体検出を行うために本研究では，3. 1 で述べたようにビット演算を利は，この関数マージン内で二つのクラス y を最も多く用して近似計算を高速化するために，HOG 特徴量297電子情報通信学会論文誌 2014/2 Vol. J97–D No. 2

Algorithm 2 Fast discrimination by early judgment.
Require: input image I
1. Raster scan the detection windows for image I//K: Total number of detection
for k = 1 to K do
windows
2. Extract binary coded feature vectors xk from detection window I(k).
3. Initializef (xk ) ← 0
4. Obtain the classiﬁer output value with the approximation calculation.
//Nb : Maximum number offor i = 1 to Nb do
bases
4.1 Linear SVM approximation calculation: βi (2 <b+i , xk > −|xk |).
f (xk ) += βi (2 POPCNT(b+i & xk )−POPCNT(xk ))4.2 Judge the calculation result.
if f (xk ) > thpos or f (xk ) < thneg thenbreak//End the approximation calculation.
end ifend for //Approximation calculation up to Nb
5. Judge label y for the target from threshold th.
1
if f (xk ) > thyk =−1otherwiseend for //End raster scanning.
return y1 , y2 , ..., yK

図 4 DET カーブ (HOG 特徴量の共起表現)
Fig. 4 DET curve (Co-occurrence of HOG features).

図 4 は，HOG 特徴量の共起の有効性を評価するた
めに人検出による実験結果を DET カーブにより比較したものである．DET カーブより，実数ベクトルの

HOG 特徴量では特徴量間の差の絶対値による共起表
現は，高精度な物体検出が可能であることを確認した．

3. 4. 2 ビット演算を利用した B-HOG 特徴量の共起表現

をバイナリコード化した B-HOG 特徴量を利用する．

3. 4. 1 で有効とされた共起表現をバイナリコードで

B-HOG 特徴量は HOG 特徴量と比較して，2 値化の実現する．提案手法によるバイナリコードの共起表現

際の量子化誤差の影響により物体検出の識別精度が低方法は，ブロックに属する二つのセルの B-HOG 特徴

下する問題がある．B-HOG 特徴量の高精度化として

量 P ci と P cj から式 (8)〜式 (10) に示すビット演算

は，複数領域の勾配の関係を捉える R-HOG 特徴量がにより勾配方向ヒストグラムにおけるバイナリコード

提案され，勾配の共起表現により高精度な物体検出を間の関係性を表現する．ここで，論理演算子には論理実現できることが報告されている [11]．そこで，提案

積 (AND)，論理和 (OR)，排他的論理和 (XOR) のい

手法では B-HOG 特徴量間のビット演算により共起性

ずれかを用いる．

を表現することで，バイナリコードの特徴ベクトルによる識別精度の高精度化を行う．

3. 4. 1 HOG 特徴量の共起表現
実数ベクトルで表現される HOG 特徴量の共起表現

P and
ci ,cj = P ci & P cj

(8)

P or
ci ,cj= P ci | P cj

(9)

P xor
ci ,cj= P ci ˆ P cj

(10)による特徴表現の効果を確認するために予備実験を行

1 ブロックが 4 セルから構成されているとき，6 パターン

う．HOG 特徴量の共起表現としては，Boosting アルの共起バイナリコード P operator = {P c1 ,c2 , P c1 ,c3 ,ゴリズム [13] を利用した手法 [14], [15] などが提案さP c1 ,c4 , P c2 ,c3 , P c2 ,c4 , P c3 ,c4 } が生成される．このとれている．本研究では，共起表現による特徴表現の有き，論理演算子が AND の場合，二つのセルに共通

効性を確認するために，特徴量間で下記の式 (5)〜式

して勾配が存在するときを “1” のビットで表現する．

(7) に示す演算により共起を表現した．このように，OR の場合，二つのセルでどちらかに勾配があるとき

積，和，差の絶対値により HOG 特徴量を共起表現しを “1” のビットで表現し，二つのセルに共通して勾配たものを HOG 特徴量の特徴量ベクトルに結合する．

が存在しないときを “0” のビットで表現する．XORの場合，二つのセルに共通しない勾配を “1” のビット

V mul
ci ,cj = V ci · V cj

(5)

V sum
ci ,cj = V ci + V cj

(6)

存在しないときを “0” のビットで表現する．このようV sub
ci ,cj(7)に，ビット演算を利用して共起表現することでセル間

298= |V ci − V cj |で表現し，二つのセルに共通して勾配が存在する及び

論文／近似計算を導入した線形識別器の早期判定による高速な識別

Fig. 5図 5 B-HOG 特徴量の共起表現
Co-occurrence representation of B-HOG features.

Fig. 6図 6 DET カーブ (提案手法の有効性の評価)
DET curve (Eﬀectiveness of proposed method).

出対象を含む INRIA Person Dataset の評価用画像を288 枚使用する．
の勾配の関係性を捉えることが可能となり，バイナリ
コードによる物体検出の高精度化が期待できる．バイ
ナリコード間の共起には，ビット演算を用いるため低4. 2 実 験 概 要
提案手法の有効性を評価ために，以下の特徴量と識別器の組み合わせについて識別精度を比較する．

•

HOG 特徴量+線形 SVM

提案手法は図 5 に示すように，ブロック領域内の•

B-HOG 特徴量+線形 SVM

セルを組み合わせて共起表現したバイナリコードを•提案手法 (“論理演算子”)

コストで共起表現をすることができる．

B-HOG 特徴量のバイナリコードに追加する．共起表

B-HOG 特徴量の共起表現と線形 SVM の近似計算に現を追加した特徴量は，M = 8，R = 2，N = 8 のとよる早期判定き 3,360 ビットの B-HOG 特徴量に 5,040 ビットのバ提案手法は，B-HOG 特徴量を共起表現するための論理

イナリコードを追加するため，8,400 ビットのバイナ演算子に，AND，OR，XOR のそれぞれを評価して比リコードとなる．提案手法では，この B-HOG 特徴量較する．評価には Detection Error Trade-oﬀ (DET)

を共起表現した 8,400 ビットのバイナリーコードを入

カーブを用いる．DET カーブは横軸に誤検出率，縦力特徴ベクトル x として用いる．

軸に未検出率を表しており，原点に近いほど高精度で4. 評 価 実 験
提案手法の有効性を評価するために評価実験により識別精度及び識別過程の処理時間の比較を行う．

あることを表す．処理時間の比較では，OS: Windows

Server 2008 Enterprise x64，CPU: Intel Xeon CPU
X7542 @ 2.67GHz，RAM: 256GB の PC を用いる．
全ての実験において線形 SVM は SVM Light [16] を

4. 1 データセット

用いて学習を行う．各特徴量のパラメータは M = 8，

評価実験には，人検出のベンチマークとして広く利R = 2，N = 8 とする．また，評価実験では予備実用されている INRIA Person Dataset [2] を使用する．

験の結果より，線形 SVM の近似計算における基底数

学習サンプルには，ポジティブサンプルを 2,416 枚，

Nb = 16 とする．

ネガティブサンプルを 12,180 枚を使用する．識別精4. 3 識別精度の評価

度を評価するためのテストサンプルには，ポジティブ

実験結果の DET カーブを図 6 に示す．DET カー

サンプルを 1,132 枚，ネガティブサンプルは背景画像

ブより，線形 SVM を用いた B-HOG 特徴量は HOG

453 枚から網羅的にラスタスキャンさせて切り出した

特徴量と比較して識別精度が低下している．一方，提画像 1,306,029 枚を使用する．学習サンプル，テスト

案手法 (AND)，提案手法 (OR) は B-HOG 特徴量とサンプルの画像サイズはそれぞれ 64 × 128 ピクセル

同様のバイナリコードの特徴量であるが，HOG と同の大きさに正規化して使用する．また，識別器の処理等の識別率を得た．更に，提案手法 (XOR) は誤検出

時間を評価するための入力画像には，検出対象と非検率 0.1% において HOG 特徴量+線形 SVM と比較し299

電子情報通信学会論文誌 2014/2 Vol. J97–D No. 2

図 7 検出可能になったポジティブサンプル
Fig. 7 Positive sample that was detected.

表 1 各識別器の検出率 (DR) [%] と処理時間 (PT) [ms]Table 1 Detection rate (DR) [%] and processing time(PT) [ms] for each classiﬁer.
Classiﬁer
SVM without appr. comp.
SVM with appr. comp.(Nb =2)
SVM with appr. comp.(Nb =16)
SVM with appr. comp. and early judg.

DR
94.16
91.07
94.08
94.08

PT
0.034
0.002
0.013
0.002

て約 6.1% 向上させることができた．これは，ビット演算後のバイナリが出力される割合に起因するためである．AND と OR により演算して求めたバイナリ

Fig. 8図 8 識別結果が早期判定されたサンプル
Samples for which early judgment was madein the classiﬁcation results.

コードの “0” と “1” の割合は偏りが発生するため，ポジティブとネガティブの両方で同じバイナリが観測さき，提案手法は平均でポジティブサンプルは 7.78 個，れることが多い．しかし，XOR のバイナリコードのネガティブサンプルは 1.46 個の基底数による近似計“0” と “1” の割合は等しく無駄のないバイナリコード

算結果から早期判定している．基底数 Nb = 2 のときが生成できるためだと考えられる．

の近似計算法は，提案手法と同じ処理時間となるが検XOR による B-HOG 特徴量の共起表現の有効性を

出率は低下する．

実験的に確認する．図 7 に B-HOG 特徴量で未検出

VGA サイズ (640 × 480 ピクセル) の入力画像にのテストサンプルに対して，共起表現により検出可能

対して検出ウィンドウのサイズ (lw , lh ) = (64, 128)となった全てのポジティブサンプルを示す．XOR でを マ ル チ ス ケ ー ル S = 2 (ls = 1, 2) で ず ら し 幅

共起表現した場合，AND と OR で検出可能となった

lm = 4 としてラスタスキャンした場合，全ての検27 枚と，AND と OR では検出することが不可能な

出ウィンドウの識別処理に要する時間は，線形 SVM

19 枚のサンプルを検出できたことがわかる．

では 674.2[ms](1.48[fps]) なのに対して，提案手法は

4. 4 処理速度の評価

39.66[ms](25.21[fps]) と高速にラスタスキャンをする

表 1 に，XOR を用いて共起表現した特徴ベクトルをことが可能となる．

用いたときの検出率と一つの検出ウィンドウの識別に

図 8 に提案手法により識別結果が早期判定されたサ要する処理時間を示す．近似計算法は基底数 Nb = 16

ンプルの割合とそのサンプル例を示す．基底数が少なのとき，線形 SVM と同等の識別精度である．処理時

い段階では，早期判定されたサンプルの平均勾配画像

間を比較すると，近似計算法は線形 SVM よりも約 3(a)，(b) から確認できるように，人と背景に分離しや倍高速な演算が可能である．提案手法は早期判定を行すいサンプルであることがわかる．一方，困難なサンうため近似計算法よりも更に速く，線形 SVM と比較

プル (c)，(d) は最大基底数まで (Nb = 16) 継続してして約 17 倍高速な識別器の演算を実現した．このと近似計算が行われる．また，ネガティブサンプルの 9300

論文／近似計算を導入した線形識別器の早期判定による高速な識別

Table 2Features
HOG features
B-HOG features
Proposed method (XOR)
Random Projection

表 2 各特徴量のメモリと検出率，処理時間
Feature memory size, detection rate, and processing time.
Dimensionality
3360
3360
8400
3360
8400
23520

Memory [bytes]
3360
420
1050
420
1050
2940

Detection rate[%]
88.69
84.89
94.08
86.57
87.63
88.69

Processing time[ms]
1.554
1.561
1.576
50.989128.059360.219図 9 検出結果例と早期判定された領域の可視化
Fig. 9 Examples of detection results and visualization of early judgment regions.
Fig. 10

図 10 Random Projection の識別精度
Random projection classiﬁcation accuracy.

割以上は基底数が 1 の時点で早期判定することで，高速な識別処理が可能となる．一般的な物体検出シーン(入力画像) では，多くの領域が背景 (非検出対象) であるため，図 9 に示すように提案手法は多くの検出ウィンドウにて少ない基底数 Nb で線形 SVM を近似計算していることがわかる．以上より，提案手法は検出ウィンドウに応じて適応的に識別結果を早期判定することで，線形 SVM の性能を維持しつつ高速な識別処理を実現した．

4. 5 特徴量のメモリサイズと処理時間の評価
提案手法のバイナリコードによる特徴表現に必要なメモリ量を調査する．ここでは，特徴ベクトルの距離関係を保持したままバイナリコード化することのできる Random Projection [17] を用いて，提案手法の共起表現した特徴量のメモリサイズを評価する．図 10に，Random Projection により HOG 特徴量を任意のビット数のバイナリコードで空間写像した際の識別精度を示す．Random Projection では，実数ベクト
ルの HOG 特徴量と同等の識別精度を再現するには

23,520 ビット必要である．一方，表 2 に示すように，
提案手法 (XOR) は検出率を約 6.1% 向上させつつそ5. む す び
本論文では，物体検出における識別過程の高速化について取り組み，本研究の貢献は以下の 2 点である．

1. 線形 SVM に早期判定を導入することによる識別処
理の高速化．2. B-HOG 特徴量を共起表現したバイナ
リコードの特徴量による物体検出の高精度化．1. では，
線形 SVM を近似計算し，検出ウィンドウに応じて適応的に識別結果を早期判定することで，識別過程において識別精度を維持しつつ約 17 倍高速な識別処理を実現した．2. では，B-HOG 特徴量のバイナリコードに対してビット演算を用いた共起表現により高速かつ効率の良いバイナリコード化を行い，メモリサイズを
約 1/3 にしつつ識別精度の高精度化を実現した．今後は，HOG 特徴量の高速化手法を提案手法に導入して特徴抽出過程を高速化することで，検出手法全体において高速な物体検出を実現する予定である．
文[1]

works,” Machine Learning, vol.20, no.3, pp.273–297,のビット数は 8,400 ビットであり，効率の良いバイナ
リ表現ができているといえる．更に，提案手法 (XOR)

1995.
[2]

を行うことができた．

N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” Computer Vision andの共起抽出に要する時間は 1.576[ms]，HOG 特徴量は 1.554[ms] とわずかな時間が増えるだけで特徴抽出

献

C. Cortes and V. Vladimir, “Support-vector net-

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,” Inter-301電子情報通信学会論文誌 2014/2 Vol. J97–D No. 2national 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 Recognit.,
pp.1993–2000, 2011.

[5]

P.F. Felzenszwalb, R.B. Girshick, D. McAllester, and

後藤 雄飛

（正員）

2012 年画像センングシンポジウムオー
ディエンス賞．2013 年中部大学大学院博士前期課程修了．2013 年より株式会社ホンダエレシス入社．同年，画像センングシ
ンポジウム優秀学術賞．

D. Ramanan, “Object detection with discriminatively trained part based models,” IEEE Trans. Pattern Anal. Mach. Intell., vol.32, no.9, pp.1627–1654,
2010.
[6]

Q. Zhu, S. Avidan, M. Yeh, and K. Cheng, “Fasthuman detection using a cascade of histograms oforiented gradients,” Computer Vision and Pattern
Recognition, pp.1491–1498, 2006.

[7]

土屋 成光

（正員）

2008 年中部大学大学院博士前期課程修了．2011 年同博士課程満期退学．2011 年
より同大学研究員，パターン認識・理解，
機械学習の研究に従事．

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,” Department of 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]

山内 悠嗣

（正員）

2012 年中部大学大学院博士後期課程修了．2012 年より同大学院博士研究員．2010
年独立行政法人日本学術振興会特別研究員
DC．コンピュータビジョン，パターン認識の研究に従事．

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,

[11]

2001.

藤吉 弘亘

松島千佳，山内悠嗣，山下隆義，藤吉弘亘，“物体検出のための Relational HOG 特徴量とワイルドカードを用いた” 信学論（D），vol.J94-D, no.8,
バイナリーのマスキング，

1997 年中部大学大学院博士後期課程修了．1997〜2000 年米カーネギーメロン大pp.1172–1182, Aug. 2011.
[12]

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.

[13]

R.E. Schapire and Y. Singer, “Improved boostingalgorithms using conﬁdence-rated predictions,” Machine Learning, vol.37, no.3, pp.297–336, 1999.

[14]

三井相和，山内悠嗣，藤吉弘亘，“Joint 特徴量を用いた 2
段階 Boosting による物体検出，” 信学論（D），vol.J92-D,
no.9, pp.1591–1601, Sept. 2009.

[15]

山内悠嗣，山下隆義，藤吉弘亘，“Boosting に基づく特徴量の共起表現による人検出,” 信学論（D），vol.J92-D,[16]

T. Joachims, SVM light,[17]

M.X. Goemans,

no.8, pp.1125–1134, Aug. 2009.
http://svmlight.joachims.org“Improved approximation algo-rithms for maximum cut and satisﬁability problems
using semideﬁnite programming,” J. ACM, vol.42,
pp.1115–1145, 1995.

（平成 25 年 4 月 16 日受付，8 月 28 日再受付）

302

（正員）

学ロボット工学研究所 Postdoctoral Fellow．2000 年中部大学講師，2004 年同大准教授を経て 2010 年より同大教授．2005〜
2006 年米カーネギーメロン大学ロボット
工学研究所客員研究員計算機視覚，動画像処理，パターン認識・理解の研究に従事．2005 年ロボカップ研究賞．2009 年情報処理学会論文誌コンピュータビジョンとイメージメディア優秀論文賞，2009 年山下記念研究賞．2010 年，2013 年画像センシ
ングシンポジウム優秀学術賞．2013 年電子情報通信学会情報・システムソサイエティ論文賞．博士 (工学)．情報処理学会，電子情報通信学会，電気学会，IEEE 各会員．