Viola-Jonesアルゴリズムの計算量削減効果
1. はじめに
OpenCVに実装されているViola-Jonesアルゴリズムは、2001年に発表された物体検知アルゴリズムであり、深層学習が2014年から爆発的な発展を続けている今日においては、先進性はないものの、枯れた技術として広く利用されている。同アルゴリズムは、少ない計算量で、高い精度を得られるようさまざまな工夫がなされており、先進的なアルゴリズムに比べて、少ない計算リソースで実用的な精度を得ることができる。このことが、同アルゴリズムが現在でも広く活用されている理由と考えられる。以下では、Viola-Jones アルゴリズムの特徴を説明するとともに、OpenCVを利用して、計算量削減効果を数値的に明らかにすることを試みる。
2. アルゴリズム
Viola-Jonesアルゴリズムは、Paul ViolaとMichael Jonesによる”Rapid Object Detection using a Boosted Cascade of Simple Features” [1] で提案されたもので、その表題からも、また、序文冒頭の「本論文では、非常に高速に画像を処理し、高い検出率を達成することができる、仮想物体検出のための機械学習アプローチについて述べる。」[1] との記載からも、高速な処理を志向したアルゴリズムであることがわかる。
同アルゴリズムの特徴は、(1) Haar-Like 特徴量と名付けられたシンプルな特徴量を用いること、(2) 特徴量計算を対象画素のサイズによらず一定の計算量で計算可能とする積分画像を用いること、(3) 分類器の学習には、精度の低い弱分類器を効率的に組み合わせて精度の高い強学習器を構築するアンサンブル学習手法の AdaBoostを用いること、(4) 複数の分類器を直列に接続する際に、カスケード分類器という、いくつかの分類器をまとめたステージを設け、ステージごとの閾値に満たないデータは、引き続く処理を棄却する手法を用いることの４点である。以下では、それぞれの内容を述べる。
2.1 Haar-Like特徴量
Haar-Like特徴量は、Constantine Papageorgiouによる”A Trainable System for Object Detection in Images and Video Sequences” [3] で、物体検知に Haar wavelets を用いたことから着想を得て考案された特徴量で、そのため、Haar-Like と名付けられた。
同特徴量は、図１に示すHaar-Like パターンと呼ばれる、同じサイズの白、黒の長方形が互いに境界を接しているパターンを用意し、相対的な位置を保った形でサイズを変化させて、物体検知対象とする画像に当てはめ、黒・白、各領域の画素値合計の差を特徴量とするものである。
Haar-Like パターンはシンプルだが、サイズを変更しながら対象画像に適用していくため、生成される特徴量は膨大なものとなる。図１の各パターンのピクセルサイズ(width, height)は、左から (2, 1), (3, 1), (1, 2), (1, 3), (2, 2) であるが、これを縦横20ピクセルの画像に適用した場合に生成される特徴量は、図２ の計算により78,460となる。
2.2 積分画像
Haar-Like特徴量の計算は、Haar-Likeパターンと対象画像の画素値の間の演算によるものであるため、その計算量は画素のサイズに比例して増える。積分画像は、この計算量を削減するために考案されたもので、元の画像の上、左にパディング（0埋め）を行い、左上からの画素値の和を画素値とする積分画像を用いることで、図３に示すように、画素のサイズによらず、４隅の画素値の加減算で画素値の和を計算可能とする手法である。
図３ 左のグレーの領域の画素の和 S は、右の積分画像の４隅 S1 から S4 の画素値を使って、以下の式から計算できる。
S = S1 — S2 — S3 — S4
2.3 AdaBoost
AdaBoostは、複数の弱分類器を直列に繋ぐアンサンブル学習のうち、各学習器の予測結果に基づいて、データの重みづけを変えて学習する手法である。Haar-Like特徴量のような精度の低い弱学習器の組み合わせであっても、精度の高い強学習器を作り出すことができる。
学習過程での重みは、データ i の学習器における重みを D(i)、学習器の重みを αとした時、以下の数式によって更新される。
2.4 カスケード分類器
カスケード分類器は、強分類器を１つのステージとし、ステージを複数直列に連結したもので、ステージごとに結果を評価し、正解でなければ残りの処理を棄却し、直ちに処理を終了する手法である。前段の分類器ほど誤検出を多くするよう調整することで偽陰性を減らし、後段の分類器で対象とならない領域を早めに削除することで、計算量を削減できる。
本アルゴリズムでは、学習の過程ではステージごとに最小の検出率と最大の誤検出率を設定し、それらを満足するよう AdaBoost で学習していく。この時、前段のステージでは最大の誤検出率を高めに設定する。
3. 実験
以下の実験では、OpenCVに実装された Viola-Jonesアルゴリズムを使って、顔認識を行い、カスケード分類器による判定の回数、すなわち計算量がどの程度削減されているかを調べる。
3.1 訓練済みモデルの分析
実験では、OpenCVが提供する顔識別用のhaarcascade_frontalface_alt.xml を訓練済みモデルとして使用することとした。このモデルは、パターンサイズが 20 x 20、ステージ数が 22、特徴量数が 2,135である。
2.1 で示した通り、パターンサイズが 20 x 20 の場合、生成される特徴量は 78,460 であることから、本モデルでは、全体数の 2.721% の特徴量だけが使われている。また、ステージごとの特徴量をプロットした図５から、各ステージには、ほぼ、ステージが小さいほど少ない特徴量が割り振られていることがわかる。
3.2 ログ出力機能の追加
OpenCVで物体検知を行うには、detectMultiScaleメソッドを用いるが、カスケード分類器による評価は、その内部で定義されている predictOrderedStump メソッドで行われている。そこで、同メソッドにログ出力機能を追加し、物体検知を行う各検索窓がどのステージまで到達しているかをログに記録するようにした。
3.3 データーセット
実験に使うデータセットは、Labeled Faces in the Wild Home [4] を用いることとした。同データセットは、13,000人程度の顔画像を顔認識の研究用に公開しているもので、すべての画像のサイズが250 x 250 ピクセルであり、傾きが調整され、画像に一人の顔だけが含まれることから、今回の実験に適当と判断した。また、条件を揃えるため、実験で用いるプログラムで顔が識別できないものを除外し、13,164 の画像を対象とした。
3.4 ログの収集と集計
ログ出力機能を追加したOpenCVを使って、上記データセットのうち、顔が識別できる13,164 画像を対象に顔識別を行った。出力されたログをステージごとに集計した結果は、以下の通りである。
表１において、度数はそのステージで処理が棄却された回数、特徴量および特徴量（累積）はそのステージの強学習器に割り当てられている特徴量数および累積数、評価された特徴量はそのステージまでに評価された特徴量の数、棄却された特徴量はカスケード分類器を使わない場合に計算すべき特徴量から、実際に計算された特徴量を引いたものである。
まず、集計結果を特徴量の評価割合、すなわち 評価された特徴量 / (評価された特徴量 + 棄却された特徴量) をy軸に、ステージを x軸にしてプロットした（図８）。2.4 で述べた通り、前段のステージで、後段のステージで関係のない、つまり顔が検知できない処理をいち早く棄却するよう、カスケード分類器が構築されている。
次に、どのステージで処理が棄却されているかを、棄却した度数と累積割合を y軸に、ステージをx軸にしてプロットした（図９）。オレンジの水平線は、累積割合 85%、95%、青の垂直線はステージ３とステージ6である。水平線、垂直線の交点を見ると、ステージ３で85%、ステージ６で95%の処理が棄却されており、早いステージでほとんどの処理が棄却されていた。
棄却の割合は、棄却された特徴量評価の総数が、カスケード分類器を使わない場合に想定される特徴量評価数数に占める割合から97.067% となり、わずかな処理で判定が行われていた。
最後に、１回の画像識別処理で、何回、特徴量の評価が行われたかを、頻度を y軸、評価回数を x軸にプロットした（図１０）。全体はK-S検定の結果、正規分布(μ= 2,712,404 σ= 306,255)に従うと考えられ、平均は 2,712,404 回であった。
4 おわりに
OpenCVに物体検知機能として実装されている Viola-Jonesアルゴリズムが、高速な物体検知が行えるよう、さまざまな工夫がなされていることを説明し、サンプルデータセットを使った顔の検知処理のログを集計し、提供されている訓練済みモデルの計算量を調べた。調査および実験から、以下にまとめる通り、Viola-JonesアルゴリズムおよびそのOpenCVでの実装は、大幅な計算量の削減を達成していたことが確認できた。
- 積分画像により、Haar-Like特徴量を計算するための画素値の和の計算を、画素の面積に比例した計算量から、積分画像の４点の画素値の加減算での計算に削減した。
- 顔識別用のhaarcascade_frontalface_alt.xmlは、AdaBoostで学習した強学習器を組み合わせたカスケード分類器を構築することで、20 x 20ピクセルの画像で生成される78,460 の特徴量のうち、有効な 2,135 だけからモデルが構築されていた。採用された特徴量の割合は、2.721% である。
- サンプル画像（250 x 250 ピクセル）を使った実験では、カスケード分類器の効果により、検索窓の 85% を４ステージ（特徴量数 78）で、95% を７ステージ（特徴量数 205）で棄却し計算量を削減していた。画像単位では、カスケード分類器がない場合に想定される評価すべき特徴量数の2.933% にあたる2,712,404回の評価で顔認識が行われた。
- 250 x 250 ピクセルの画像の識別に必要な平均判定処理回数 2,712,404で Raspberry PI 4のクロック周波数 1.8G を割ると、712/secとなる。１回の判定処理に必要なクロック数と、より大きい画像の処理、リアルタイム処理、識別後の後処理など、アプリケーション実装に必要な処理を考えると、本アルゴリズムによる識別処理は、計算量が削減されてもなお、実行時間の考慮が必要な処理量であると考えられる。
参考文献
[1] Paul Viola, Michael Jones, Rapid Object Detection Using a Boosted Cascade of Simple Features (2001)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.415.8118 (2022/7/26 URL確認)
[2] Yi-Qing Wang, An Analysis of the Viola-Jones Face Detection Algorithm (2013)
https://www.ipol.im/pub/art/2014/104/article.pdf
(2012/7/26 URL確認)
[3] Constantine P. Papageorgiou, A Trainable System for Object Detection in Images and Video Sequences (2000)
https://core.ac.uk/download/pdf/4382757.pdf
(2022/7/26 URL確認)
[4] Labeled Faces in the Wild Home, All images aligned with deep funneling
http://vis-www.cs.umass.edu/lfw/
(2022/7/26 URL確認)
