RASW：Viola-Jonesメソッドの改善

翻訳者から：

良い一日！

最近、Viola-Jones検出器の速度を上げる方法を探しましたが、興味深い2013年の記事RASW：Viola-Jonesオブジェクト検出を改善するためのランタイムアダプティブスライディングウィンドウに出会いました。 スキャンウィンドウとカスケード分類子の原理に基づいて検出器のパフォーマンスを改善するための効果的なアプローチを示します。 私はロシア語でこのアプローチの説明を見つけられず、このギャップを埋めることに決めました。 この翻訳では、viola-Jonesアルゴリズムの説明を省略しました。これについては、 habrahabr.ru / post / 133826を含め、すでに多くのことが言われているためです。

RASW：Viola-Jonesオブジェクト検出を改善する実行時適応型スライディングウィンドウ

フランチェスコ・コマスキ、サンダー・スタイク、トゥワン・バステン、ヘンク・コーポラル

オランダ、アイントホーフェン工科大学、電子システムグループ

ff.comaschi、s.stuijk、aabasten、h.corporaalg @ tue.nl

注釈

画像内のオブジェクトを検出するためのアルゴリズムの中で、最も一般的なのは、OpenCVライブラリに実装されているViola-Jonesメソッドです。 それでも、スキャンウィンドウの原理に基づく他の検出器と同様に、必要な計算量は処理された画像のサイズとともに増加します。これは、リアルタイムで画像を処理する場合は良くありません。 この記事では、精度を損なうことなく速度を上げるために、処理中にスキャンウィンドウを移動するステップを変更する効果的なアプローチを提案します。 また、Viola-Jones法を使用して、提案されたアプローチの有効性を示します。 OpenCVライブラリーの検出器の実装と比較すると、精度を損なうことなく最大2.03倍の速度増加（フレーム/ s）が得られました。

はじめに

半導体技術とコンピューターアーキテクチャの分野における革新により、コンピュータービジョンを使用するための真の新しいシナリオが作成されました。このシナリオでは、リアルタイムで状況を分析する能力が不可欠です。 多くの分野でアプリケーションを見つけるリアルタイムタスクの良い例は、画像内のオブジェクトの検出です。 そのようなオブジェクトは、多くの場合、人の顔です[1]。 現時点では、顔を検出するための非常に多様なアプローチがあります。 2001年にViola and Jones [2]によって提案された方法は、この分野における真のブレークスルーでした。 この方法は、その高い精度と深刻な理論的基礎のために非常に人気があります。 ただし、計算が複雑なため、この方法は、強力なプラットフォームでもリアルタイム要件（帯域幅など）を満たせるほど深刻なタスクです。 画像のスキャン速度は、スキャンウィンドウのステップサイズΔ-スキャンウィンドウをシフトするピクセル数に大きく依存します。 ほとんどの利用可能な実装では、ステップは一定であり、コンパイル段階で決定されます。つまり、ウィンドウは一定の値だけシフトされ、画像の内容に依存しません。 この記事では、実行時にスキャンステップを変更することにより、アルゴリズムの精度を損なうことなくスループットを向上させるランタイムアダプティブスライディングウィンドウ（RASW）を提案します。

既存のソリューションの概要

近年、高スループットのViola-Jones顔検出器のハードウェア実装がいくつか提案されています[3]-[5]。 ただし、このようなソリューションには2つの主な欠点があります。

1）多大なエンジニアリング努力が必要です。これは、1回限りの高いコストを意味します。

2）それらは十分な柔軟性がないため、アプリケーションシナリオの変更にシステムを適合させることができません。



アルゴリズムを高速化する別の方法は、GPUで実装を使用することです[6]-[8]。 ただし、GPUが消費するエネルギー量により、このソリューションは組み込みシステムでの使用には実用的ではありません。 ただし、GPU実装は、この記事で提案されている最適化と組み合わせて使用​​できます。 特に、並列化を使用して特徴を計算し、さまざまなサイズのウィンドウをスキャンできます。 これに関する詳細は[6]に書かれています。



[9]では、著者は組み込みシステム向けに最適化されたOpenCVの実装に基づくソリューションを提案していますが、実装自体は変更されていません。 アルゴリズムの最適化により、精度を損なうことなく必要な計算量を減らすことにより、スループットが向上します。



物体検出システムの最初のステップは、通常、画像候補領域を探してシーンをスキャンすることです。 このステップには多くの計算が含まれます。 [10]のLampertおよびその他は、Efficient Subwindow Searchとして知られる分析アプローチを提案し、オブジェクトのローカライズを確実にします。 ただし、提案されたアプローチは、具体的にはオブジェクトの位置特定に関係します。つまり、画像に存在するオブジェクトの数を事前に知る必要があります。 このようなアプローチは、インターネット上の画像を検索するようなタスクでは非常に効果的ですが、[10]から、対象オブジェクトの複数のインスタンスが画像上に存在する場合に何が起こるかは明確ではありません。 さらに、ESSを適用するには、バウンディング関数を特定の方法で構築する必要があり、カスケード分類器のそのような関数は[10]で提示されていません。 この記事で紹介するアプローチは、カスケード分類器を対象としており、追加の情報（制限関数など）を必要とせず、任意の数のオブジェクトを含む画像に使用できます。



[11]では、著者はオブジェクトの迅速な検出のために、人間モデルでの視覚検索に基づく方法を検討しています。 OpenCVのViola-Jones検出器と比較すると、精度がわずかに低下したため、平均で2倍の加速が得られました。 作業の結果は1つの画像についてのみ表示されるため、より多くの画像のテスト中にインジケータが保存されるかどうかを判断することは困難です。 さらに、このアプローチは1つの顔のみを含む画像で使用するために提案されており、複数の顔を持つ画像にこのアプローチを適用する方法は明確ではありません。 結果はさまざまなスケーリング係数について示されていますが、画像スキャンに対する他のパラメーターの影響は体系的に研究されていません。 私たちのアプローチの結果は、個人の標準ベースに対して提示されており、さまざまなパラメーターの影響が慎重に研究されています。



[12]で、著者は、スキャニングウィンドウのスライディングステップを増やして、検出器のカスケードの検出ミスを減らす興味深い方法を提案しています。 著者は、いくつかの顔のベースで有望な結果を提示しました。 ただし、[12]で提案されているアプローチでは、位置推定のためにオフラインの決定木を学習する必要があります。 さらに、関心のあるポイントを使用すると計算量が増えるため、メモリが制限されている場合は使用が難しくなります。 この記事で紹介するアルゴリズムの最適化は、実行時に利用可能な情報に基づいています。 追加のトレーニングを必要とせず、標準的なスキャンウィンドウの原則に重要な計算を追加しません。

RASW

通常、Viola-Jonesメソッドの実装では、スキャンウィンドウ（または画像）のサイズが変更されるたびに、このウィンドウはスキャンステップΔで画像に沿って移動します。 x軸とy軸に沿ったステップサイズ、つまりそれぞれΔXと_ΔYを区別します。 簡単にするために、ΔX =ΔYの場合、表記をΔのままにします_。 影響のスキャン手順は、検出精度とスループットの両方に影響します。 値を大きくするとスループットが向上しますが、同時に一部のオブジェクトがスキップされる可能性があるため、認識品質が低下します。 スキャンウィンドウを移動するために、オブジェクトを含まない領域ではウィンドウが速く移動し、オブジェクトのすぐ近くでは遅くなるという基準を見つけた場合、品質を損なうことなく画像全体のスキャン速度を上げることができます。 さらに、画像の均一な領域でウィンドウをより速く動かすと、分類器が背景画像内の目的のオブジェクトを誤って検出する可能性が減ります。ほとんどの既存の実装では、ステップサイズはΔ= 1またはΔ= 2の固定値です。 値を大きくすると、品質が低下します。



分析の結果、画像領域内の顔の存在と、このウィンドウが拒否されるカスケード内の分類子番号との関係が見つかりました（この番号を終了ステップと呼びます）。 特に、背景のみを含む領域では、カスケードの初期段階でウィンドウが拒否されます。一般的に、顔が近くなるほど、出口レベルが高くなります。



図1





図1にはテストイメージが含まれており、このイメージの出力ステージ値は各スキャンウィンドウについて記録されています。 ウィンドウの左上隅に座標（x、y）がある場合、ピクセルは出力ステップに反比例する明るさで表示されます。 つまり、出力ステップが高いほど、ピクセルは暗くなります。



ほとんどの場合、これは、この領域に目的のオブジェクトが含まれていないことを意味するため、ウィンドウは、出口ステップが低い大きなステップに簡単にシフトできることを示しています。 また、出力ステップを最大値に近づけるときは、目的のオブジェクトを見逃さないようにスキャンステップを減らすことは理にかなっています。 主なアイデアは、目的のオブジェクトが含まれていない可能性が高い画像の領域に費やす時間を減らすことです。 提案されたアプローチにより、空間データの局所性を使用して絶望的な領域を破棄することができます。 破棄された領域が最も計算コストが高くない場合でも、ウィンドウの数を大幅に削減すると、品質に影響を与えることなく各画像の処理が高速化されます。 これは特に有益です ウィンドウを直接ドロップすることにより、サブウィンドウの画像の予備的な正規化を避けることができます。これはかなり高価な操作です。 この正規化は、Viola-Jonesメソッド[2]、[9]でさまざまな照明条件の影響を最小限に抑えるために必要です。



図2





図2は、RASWアプローチの利点を図解したものです。 図面を読みやすくするために、x軸（左）とy（右）に沿った方向を分離します。 灰色のブロックは、図に示す画像の204から213（x軸）および114から122（y軸）の拡大ピクセルです。 3（右）。 位置（209、117）の黒いピクセルは、図1にある右下の面に対応します。図4に示す各アプローチでは、対応する幾何学的形状がスキャンウィンドウが配置されているピクセルに配置されます。 図2（左）では、一定のステップΔX = 2またはΔX = 3をとると、検出器は顔が存在する場所にスキャンウィンドウを配置できません。 RASWアプローチでは、顔に近づくとステップサイズΔXが自動的に小さくなり、ウィンドウを適切に配置できます。 同じ振る舞いが図に見られます。 4（右）、この場合は一定のステップ_ΔY = 3でもウィンドウを適切に配置できるという違いがあります。



アルゴリズム1





アルゴリズム1は、RASWの実装を表しています。 スキャンウィンドウが移動するたびに、カスケード分類子が起動され、出力分類が返されます（行7）。 出力ステップがn-カスケードの分類子の数-に等しい場合、目的のオブジェクトが見つかり（8行目）、位置、現在のウィンドウのサイズがベクトルVに配置されます（10行目）。 ウィンドウのステップは、ウィンドウの前の位置の出力ステップに応じて、Δx _、max 、Δx _、minおよびΔx _、nomの 3つの異なる値を取ることができます（これはy方向にも当てはまります）。 値ΔXおよび_Δyを正しい値に割り当てるには、ウィンドウの前の位置の出力レベルに関する情報を保存する必要があります。 この情報は、変数ΔXおよび_Δyに直接保存できます。 実装では、ウィンドウは左から右、上から下に移動するため、x方向に関する情報は整数変数ΔXに格納できます_。 一方、ウィンドウが行の最後に達すると、y軸に沿ったステップに関する情報が行全体について保存されます。つまり、 _Δyは整数の配列です。 アルゴリズムの各反復で、ΔXと_Δy [x]は1ずつ減少し、両方の変数がゼロに等しくなると、現在のウィンドウが分類器の入力に供給されます。 1つのステップ値のみがこの条件に達した場合、この変数は最小値で初期化されます（20行目と22行目）。 1つのΔ値から別のΔ値への遷移（両方向）は、実行時に4つのしきい値_Δx、t1 、Δx _、t2 、 _Δy、t1 、 _Δy、t2に基づいて決定されます。 これらのパラメーターはコンパイル時に設定され_、0〜n + 1の値をとることができます。Δx _、t1 <Δx _、t2および_Δy、t1 < _Δy、t2です。 ステップΔxが一定で、 _Δx、min （Δx _、t1 =Δx _、t2 = 0）、Δx _、nom （Δx _、t1 = 0、Δx _、t2 = n +に等しい特定のケースを考慮します1）またはΔx _、最大 Δx _、t1 = n + 1）。 ステップ_Δyについても同様です。 簡潔にするために、アルゴリズム1の12〜18行目では、x軸に関連するコードのみを示していますが、y軸にいくつかの修正を加えた同様のコードを適用する必要があります。 異なるしきい値は、異なるスループット精度比を提供します。 他の比率もこれらの比率に影響します：スケーリング係数s、マージしきい値γ。 次の値を選択しました：値が高いほど検出器の品質が低下するため、Δx _、max = 3、Δx _、nom = 2、Δx _、min = 1。

結果

このセクションでは、実装を固定および適応ステップと比較することにより、アプローチの有効性を示します。 実験は、クロック周波数3.07 GHzのクアッドコアIntel Core i7で実施されました。 人のベースCMU + MITが使用されました[15]。



次の実装が検討されました。（I）静的：ΔXおよび_ΔYは一定で、1、2、または3（合計9つの組み合わせ）に等しい。 （II）OpenCV 1：前のステップで顔が検出されなかった場合、画像全体でΔX =2。そうでない場合、ΔXは1に減少します。ΔYは一定で1のままです。 （III）OpenCV 2：現在のサムネイルのサイズが元の画像のサイズの2倍未満の場合はΔ= 1、それ以外の場合はΔ= 2。 ΔXと_ΔYの両方が_変化します。



比較に使用した最初の2つのアプローチ（静的およびOpenCV 1）は、RASWアプローチの特殊なケースであることに注意してください。 特に、静的アプローチの各組み合わせは、Δt2とΔ_t1を対応する値に割り当てることにより、アルゴリズム1から取得できます。 2番目のアプローチ（OpenCV 1）は、Δx _、t1 = 0、Δx _、t2 = n、 _Δy、t1 = _Δy、t1 = 0を設定することで取得できます。



RASWの利点を説明するために、スケーリングファクターsとマージしきい値γの2つの他のパラメーターのいくつかの値について、さまざまなアプローチをテストしました。 次のパラメーターを選択しました：s∈{1.1、1.2、1.3、1.4、1.5}およびγ∈{1、2、3、4、5}。 これらのパラメーターの値が大きいと、精度が低下します。 xに5つの値、γに5つの値、Δを選択する11の異なるアプローチ（9つの静的な組み合わせと2つのOpenCVアプローチ）により、選択したアプローチには最終的に275の異なる構成があります。 RASWについては、しきい値パラメーターΔx _、t1 、Δx _、t2 、 _Δy、t1 、 _Δy、t2のさまざまなオプションがあります。 選択した分類器のステップ数はn = 25であるため、妥当な時間内にメソッドの厳密なテストを実行するために、範囲[0;のパラメーター値を取得します。 n + 1]。 特に、Δx _、t1 、Δx _、t2 、 _Δy、t1 、 _Δy、t2∈ { _{0、5、10、15、20、25、26} }で、各方向に28通りの組み合わせが可能です。 sおよびγの可能な値を考えると、合計19,600の構成が得られます。



提案されたアルゴリズムのパフォーマンスを分析するために、オブジェクト検出アルゴリズムを比較するときによく使用される2つのメトリック、リコールと精度を使用します。 それらは次のように定義されます。



;



ここで、TPは正しく定義されたオブジェクトの数、FNは見逃されたオブジェクトの数、FPは誤検知の数です。 作成されたすべての構成のうち、いわゆるパレート点のみを表示します。これは、プロジェクト空間のすべての最適な妥協点を修正するローカル最適ソリューションです[17]（結果を従来のパレート点定義[17]に対応させるため、1-リコールの代わりにリコール、1-精度の代わりに精度。したがって、理論的には、最適な構成が原点に一致します。 各インジケータで少なくとも悪化していない場合、構成は他の構成よりも優先されます。 他の構成が優先されない構成のみを考慮します。 このような構成のセットは最小限のパレートです。 このセットのすべての要素はパレートポイントです。



図3





図 図3（a）は、2次元呼び出し/精度（呼び出し/精度）空間での基本（静的、OpenCV 1、OpenCV 2）およびRASWアプローチで得られたパレート点を示しています。 基本実装の構成のパレート最小セットには27個のパレートポイントが含まれていますが、RASWアプローチのパレート最小セットには48個のパレートポイントが含まれています。 図 3（a）基本的なアプローチのパレート最小構成ごとに、同じ精度と同じ（またはより良い）レビューでRASW構成を見つけることができることがわかります。



画像をリアルタイムで処理する必要がある組み込みシステムでは、スループットが最も重要です-1秒あたりの処理フレーム数（FPS）。スループットを考慮するときにパレート最小解を視覚化するために、精度とフィードバックの両方を組み合わせた頻繁に使用されるメトリックであるF1スコアを使用します[18]。 F1スコアは、フィードバックと精度の加重平均値と見なすことができます。最良の場合は1の値をとり、最悪の場合は0を取ります







図3（b）は、2次元空間F1スコア/スループットで基本アプローチとRASWアプローチで得られたパレート点を示します（理論的に最適な解が軸の始点と一致するように、1-F1スコアと1 /スループット帯域幅を使用します）。基本実装の構成のパレート最小セットには16個のパレートポイントが含まれ、RASWセットが含まれます。図から3（b）所定の精度に対して、RASWアプローチは常に、同じ（またはより良い）精度で基本実装からの構成と少なくとも同じスループットを提供する少なくとも1つの構成を提供することがわかります。

図3の結果は、RASWが基本実装の構成に優先する新しい構成を提供することを示しています。これは、同じ（またはより良い）応答がより高い精度で達成でき、同じ（またはより良い）精度がより少ない計算で達成できることを意味します。たとえば、パラメーターs = 1.2およびγ= 4のOpenCV 1の実装のパレート最小構成（図3（b）の上から2番目のX文字）。このようなポイントの結果、F1-スコア= 87.9、スループット= 6.1フレーム/秒になります。Δx _、t1 = 5、Δx _、t2 = 10、_Δy、t1 = 5、_{Δy、t2の選択}= 5、s = 1.3およびγ= 4の場合、RASWアプローチは精度の向上（F1-score = 88.4）および2.03倍の加速（スループット= 12.4フレーム/秒）につながります。図中の黒い丸のついた点 3（b）。



RASWアプローチのパフォーマンス向上は永続的ではありません。プロジェクト空間内の位置に応じて変化します。この作業の目的は、RASWを使用して、オブジェクト検出器の設計者がターゲットアプリケーションに最適なポイントを選択できることを示すことです。たとえば、ターゲットアプリケーションが少なくとも10フレーム/秒の帯域幅を必要とし、リコールが80％を超え、精度が95％を超えるとします。次に、RASWについて上記のパラメーターのセットを選択すると、設計者は図1の黒い丸に対応する条件付きポイントを受け取ります。 3（b）、リコール= 82.4％、精度= 95.2％、生産性= 12.で特徴付けられます。システムの要件に対応する4フレーム/秒。この点は、基本実装では達成できません。

結論

この記事では、適応型スキャンウィンドウモーション（RASW）を使用してオブジェクトの検出プロセスを改善することを提案しています。 Viola-Jones顔検出器の実装結果が表示されますが、この最適化は、スキャンウィンドウとカスケード分類器を使用する任意のオブジェクト検出アルゴリズムに適用できます。既存のアプローチと比較して、RASWはリコール/精度およびF1-スコア/スループットスペースで優れたパフォーマンスを提供します。これは、リアルタイムアプリケーションにとって特に重要です。提案された最適化により、既存の実装よりも高い精度を達成できますが、同時に計算量が少なく、パフォーマンスを向上させるために並列化と組み合わせて使用​​することもできます。今後の作業では、最適なパラメータを見つけるためのアルゴリズムを開発する予定です。指定された要件を満たす。提案されたアルゴリズムは、データの局所性を使用して顔認識を改善します。ビデオから画像をキャプチャする場合、計算量をさらに削減するために時間的不均一性も考慮することができます。

文学

[1] C. ZhangおよびZ. Zhang、「顔検出の最近の進歩に関する調査」、テクニカルレポートMSR-TR-2010-66、2010。

[2] P. ViolaおよびM. Jones、「高速物体検出

[3] J. Cho、B。Benson、S。Mirzaei、およびR. Kastner、「顔検出のための複数の分類器の並列化アーキテクチャ」、ASAP、2009年。

[4] M. Hiromoto、H。S. Sugano、およびR. Miyamoto、「Haarのような機能を備えたAdaboostベースの検出のための部分並列アーキテクチャ」、IEEE Trans。回路システムVideo Technol。、Vol。 19、pp。 41-52、2009.

[5] B. Brousseau及びJ.ローズ、 " FPTでOpenCVの互換オブジェクト検出のためのエネルギー効率の高い、高速FPGAハードウェアアーキテクチャ、"、 2012。

[6] D. Hefenbrock、J。Oberg、N。Thanh、R。Kastner、およびS. Baden、「GPUを使用したViola-Jones顔検出のFPGAレベルへの加速」、FCCM、2010年。

[7] D. Oro 、C。Fern´andez、JR Saeta、X。Martorell、およびJ. Hernando、「HDビデオシーケンスでのリアルタイムGPUベースの顔検出」

、ICCVワークショップ、2011年。

[8] SC TekおよびM. Gokmen、 2012年、VISAPPの「GPUは、修正されたセンサス変換を使用して、高解像度ビデオのリアルタイムオブジェクト検出を加速しました。」

[9] L. AcasandreiおよびA. Barriga、「組み込みおよびSoC環境のViola-Jones顔検出の加速」 、2011。

[10] C. Lampert、M。Blaschko、およびT. Hofmann、「スライディングウィンドウを超えて：効率的なサブウィンドウ検索によるオブジェクトのローカリゼーション」

、CVPR、2008年。

[11] NJ ButkoとJR Movellan、「オブジェクト検出を高速化するための最適なスキャン」、CVPR、2009年。

[12] VB SubburamanとS. Marcel、「位置推定とバイナリ機能を使用した顔検出の代替検索技術」Comput。 Vision Image Understanding、vol。 117、いいえ。 5、pp。 551–570、2013。

[13] V. JainおよびE. Learned-Miller、「FDDB：制約のない環境での顔検出のベンチマーク」、マサチューセッツ大学、アマースト、Tech。

担当者UM-CS-2010-009、2010。

[14] G. Bradski、「The OpenCV Library」、Dr。ドブのJ.ソフトウTools、2000。

[15] H. Rowley、S。Baluja、およびT. Kanade、「ニューラルネットワークベースの顔検出」IEEE Trans。パターンアナル。マッハ。 Intell、vol。 20、pp。 1998年23–38。

[16] M.エヴァリンガム、LJVグール、CKIウィリアムズ、JMウィン、およびA.ジサーマン、「パスカルビジュアルオブジェクトクラス（VOC）チャレンジ」、Int。J.計算 ビジョン、vol。88、いいえ。2、pp。303から338、2010.

[17] M. Geilen、T.バステン、BD Theelen、及びR.オッテン、 "パレート点の代数、" Fundam。Inform。、Vol。78、いいえ。1

pp。35–74、2007。

[18] C. Goutte and ´E. Gaussier、「精度、再現率、fスコアの確率的解釈、評価への影響」

、ECIR、2005年。