Elbrusプラットフォーム用のViola and Jonesメソッドの最適化

Viola and Jones [1]の方法（アルゴリズム）は、画像内のオブジェクトの境界を識別する方法の1つです。 2001年にP. ViolaとM. Jonesによって開発されたアルゴリズムは、当初は画像内の顔をすばやく検索することを目的としていましたが、現在では、この人気のあるアルゴリズムのさまざまなバリエーションが境界を見つけるさまざまな問題でうまく使用されています：

• 歩行者の画像[2]、
• 車の画像[3]、
• 道路標識の画像[4]、

ほぼ同じ角度で画像に存在する他のオブジェクトと同様に。 ヴィオラとジョーンズの方法の修正のこの種の人気は、オブジェクトの検索の高い精度と、幾何学的歪みと輝度変化の両方に対する高い抵抗力によって説明されます。

Viola and Jones Methodの説明

Viola and Jonesアルゴリズムは、画像内のオブジェクトを検出する問題を、画像内の各ポイントでのバイナリ分類問題に減らします。 この方法は、「スライディングウィンドウ」技術に基づいていました。 事前に訓練された分類器（検出器）の助けを借りて、あらゆる種類のシフトとスケールで撮影された画像の各長方形領域について、この領域での検索オブジェクトの有無に関する仮説を確認する必要があります。 すべての地域を完全に調査すると、1つの画像で何十万もの分類器が実行されます。 そのため、分類器には2つの厳密な要件があります：高性能と少数の誤検知です。

この作業では、ViolaとJonesは人間の顔の分類器について説明しました。 トレーニングサンプルは、24x24ピクセルにスケーリングされた4916の顔画像（ 正のサンプル ）と、顔画像がなく、顔のないゾーンがランダムに抽出された9500のフルサイズ画像（ 負のサンプル ）で構成されていました。

特徴空間を構築するために、明るさの特徴的な違いを示すHaar特徴が選択されました。 Haarの符号は、画像の積分表現を使用して簡単に計算されます。 寸法が24x24の画像の場合、1つの属性の構成の数は45396に関連していることが判明しました。

Viola and Jonesメソッドでは、AdaBoostアルゴリズム[5]が使用されました。これにより、最も有益な機能を選択し、バイナリ分類器を構築できます。 これを行うために、著者は各属性に弱い分類器を関連付けました。これは単一レベルの決定ツリーを表し、その後AdaBoostアルゴリズムに供給されます。

Viola and Jonesメソッドの必要な部分は、構築された強力な分類器を結合する手順です。これにより、顔画像を含む可能性のある調査画像の領域をローカライズすることで、顔検出プロセスの生産性を大幅に向上できます。

上記のように、Viola and Jonesアルゴリズムでは、分類子がトレーニングされると、Haarウェーブレットに戻るHaar機能のファミリがオブジェクトの記述に使用されます[6]。 この選択は主に、Haarの特徴が明るさの違いに関連する検出されたオブジェクトの特徴的な特徴を適切に記述するという事実によるものです。 Haarの兆候により、人の顔の画像では、目の部分が鼻の部分よりも暗いことがわかります（図1d）。 説明したアルゴリズムには、2つの長方形の特徴（図1a）、3つの長方形の特徴（図1b）、および4つの長方形の特徴（図1c）の3つのクラスの特徴が含まれていました。

各Haar属性の値は、同じサイズの黒と白の長方形内の画像領域のピクセルの合計の差に等しくなりました。 2長方形および3長方形のHaarサインは、垂直方向（図1を参照）または水平方向に向けることができます。 Haar符号の迅速な計算のために、画像の積分表現が使用されます[7]。

AdaBoostアルゴリズムでは、Viola and Jonesメソッドを学習するときに、1つのブランチと2つのリーフを持つ認識ツリー（ 決定切り株と呼ばれ、対応する属性の値をしきい値と比較する）が弱い分類器として使用されます。 特性f _j 、しきい値θj _、およびパリティp _jに基づく形式的に弱い分類器b _j （ x ）は、次のように定義されます。

このような多くの弱い分類器は、トレーニングセットとともに、AdaBoostアルゴリズムの入力に供給されます。

図1-トレーニングで使用される長方形Haarサイン

分類器：a）2-長方形の記号。 b）3-長方形のサイン;

c）4-長方形の記号; d）標識の位置の例

スキャンウィンドウに関連（ソース[7]）

カスケード分類子（ cascade ）は、調査対象の画像について、検索オブジェクトを含まない「ポジティブ」エリアの数が、このオブジェクトを含むエリア（「ネガティブ」エリア）よりも数桁大きいという仮定の下で作成されます。 オブジェクト検出器の速度を上げるには、できるだけ早く画像のネガティブ領域を考慮することを拒否することが有用です。 または、ネガティブエリアを分析するためのフィーチャの数は、ポジティブエリアに対して計算されるフィーチャの数よりも大幅に少なくする必要があります。

検索オブジェクトの存在について分析される各画像領域は、 カスケードレベルと呼ばれる分類器の順序付けられたシーケンスの入力に供給されます 。 分類子のシーケンスを進めるにつれて、レベルの計算の複雑さが増します。 分類子が特定の領域の認識を拒否した場合（つまり、その領域が負として分類された場合）、この領域は残りの分類子によって処理されなくなります。

カスケード分類子の定義によれば、次の関係が有効です。

ここで、 FPRはカスケードの誤検出の割合、 TPRはカスケードの誤検出の割合、 Kはカスケードのレベル数、 fpr _iはカスケードのi番目のレベルの誤検出の割合、 tpr _iはカスケードのi番目のレベルの誤検出の割合です。

各分析領域について計算される計算された特性の推定数は、次の式によって計算されます。

ここで、 n _iはi番目のレベルの弱分類器の数、 pr _iはi番目のレベルの応答の割合です。

分類器のトレーニングアルゴリズムは、最適化の問題を解決し、最適なFPRおよびTPRインジケーターを使用してカスケードを構築し、計算された属性Nの予想数を最小限に抑えるようにします。 FPR 、 TPR 、およびNの値の間に明確なリンクがないため、まずこの問題を解決するのが非常に難しいことは明らかです。

肯定的な例と否定的な例を含む、既存のラベル付きトレーニングサンプルでカスケードをトレーニングする簡単なアイデアが知られています。 事前に3つのパラメーターを選択する必要があります。

• カスケードの各レベルの誤検知の割合、
• カスケードの各レベルの正しい応答の割合、
• カスケード全体の偽陽性率（ FPR ^* ）。

その後、カスケード分類器が反復的に構築され、各反復でAdaBoostアルゴリズムを使用してトレーニングが実行されます。 FPR ^*値で指定された目標品質に達するまで、レベルがカスケードに追加されます。 カスケードの各レベルのトレーニング入力で、そのようなトレーニングサンプルを提出する必要があります。その例は、現時点で既にトレーニングされているカスケード分類器の誤検知です。

パスポートのスキャン画像を検出するタスクでオブジェクト検出器をトレーニングするための説明されたアプローチを研究しました。 トレーニングセットは、2つのセットで構成されました。

• 1302の陽性サンプル（ロシア連邦市民のパスポートの2ページ目のカットサンプル）および2000の陰性サンプル（ロシアのパスポート以外のものを含むフルサイズのFullHD画像）

• 1103の陽性サンプル（ロシア連邦市民のパスポートの3ページ目のサンプルを切り取る）および2000の陰性サンプル（ロシア連邦のパスポート以外のものを含むフルサイズのFullHD画像）

  
  
  
  
  
  
  

  両方の分類子の物理サイズ（ピクセル単位）は201x141を選択しました。 このサイズでは、これがトップまたはボトムページ（つまり、クラスが一意に決定される）であり、クラス内の一意性が消えることを理解できます。

  
  
  
  
  
  
  

  その結果、2つの分類器がトレーニングされました。

  
  
  
  
  
  
  
• ロシア連邦市民のパスポートの2ページ目の分類子。合計8つのレベルと合計28の弱い分類子で構成されます。
• ロシア連邦市民のパスポートの3ページ目の分類子。8つのレベルと36の弱い分類子で構成されています。

テストサンプルは、300枚の写真とパスポートスキャンで構成されていました（両方のページが同時に画像上に存在していました）。 パスポートのトップページ（2ページ目）の製本品質は0.967でした。 パスポートの下部ページ（3ページ目）の綴じ品質は0.98でした。

Elbrusのアーキテクチャの機能

Elbrusアーキテクチャは、幅広いコマンドワード（Very Long Instruction Word、VLIW）の原則を使用したアーキテクチャのカテゴリに属します。 VLIWアーキテクチャーのプロセッサーでは、コンパイラーはコマンドのグループのシーケンス（広義のコマンドワード）を生成します。各グループ内のチーム間に依存関係はなく、異なるグループのチーム間の依存関係は最小限に抑えられます。 さらに、各グループ内のコマンドは並行して実行され、コマンドレベルで高レベルの並列処理を実現します。

コマンドレベルでの並列化は最適化コンパイラによって完全に提供されるという事実により、たとえばx86アーキテクチャの場合のように、並列化タスクを解決しないため、コマンドを実行するための機器が大幅に簡素化されます。 VLIWプロセッサの消費電力が削減されました。これらのタスクはすべてコンパイラに割り当てられるため、オペランド間の依存関係を分析したり、操作を並べ替えたりする必要がなくなりました。 コンパイラは、ソースコードのハードウェアアナライザよりもはるかに多くのコンピューティングリソースと時間リソースを持っているため、より徹底的な分析を実行し、より独立した操作を見つけることができます[8]。

さらに、Elbrusアーキテクチャの機能は、メモリを操作する方法です。 多くの場合、外部メモリへのアクセスにはかなりの時間がかかり、計算が遅くなります。 キャッシュはこの問題を解決するために使用されますが、キャッシュのサイズは厳密に制限されており、一般的なキャッシュアルゴリズムは頻繁に使用されるデータのみをキャッシュに保存することを目的としているため、欠点があります。

メモリアクセスの効率を高めるもう1つの方法は、データの事前ページング方法を使用することです。 これらの方法により、メモリアクセスを予測し、使用する前にキャッシュまたは他の特別なデバイスにデータを送り込むことができます。 それらはソフトウェアとハ​​ードウェアに分けられます。 ソフトウェア方式では、コンパイル段階で特別な事前ページング命令が計画されています。 通常のメモリアクセスと同じ方法で処理されます。 ハードウェアメソッドは、プログラムの実行中に機能し、メモリアクセスに関する動的情報を使用して予測します。 マイクロプロセッサの一部として追加のモジュールが必要ですが、特別なスワッピング命令を必要とせず、非同期で動作できます。

Elbrusプロセッサは、ハードウェアとソフトウェアのスワップ方式をサポートしています。 同時に、マイクロプロセッサハードウェアにはアレイにアクセスするための特別なデバイス（Array Access Unit、AAU）が含まれていますが、スワッピングの必要性は、特別な命令（AAUの初期化、事前スワッププログラムの開始と停止、非同期事前スワップ命令および同期データ転送命令）を生成するコンパイラによって決定されます配列のスワップバッファー（Array Prefetch Buffer、APB）からレジスタファイルへ）。 キャッシュに配列要素を配置するよりもスワップデバイスを使用する方が効率的です。配列要素はほとんどの場合連続して処理され、2回以上使用されることはめったにないからです[9]。 ただし、Elbrusでプリページングバッファーを使用できるのは、アライメントされたデータを操作する場合のみであることに注意してください。 このため、位置合わせされたデータの読み取り/書き込みは、位置合わせされていないデータの対応する操作よりもはるかに高速に行われます。

また、Elbrusマイクロプロセッサは、コマンドレベルでの並列処理に加えて、いくつかのタイプの並列処理をサポートしています。ベクトル並列処理、制御フローの並列処理、マルチマシンコンプレックスのタスクの並列処理です。

Elbrusプラットフォームでプログラムコードのパフォーマンスを改善するためのツール

ベクトル並列処理を実装する高性能EMLライブラリと組み込み関数を使用して、Elbrusアーキテクチャプロセッサで開発されたアルゴリズムの速度を上げることができます。

EMLライブラリは、ユーザーに信号、画像、ビデオ、および数学関数と演算を処理するためのさまざまな方法のセットを提供する高性能ライブラリです[10]。 C / C ++で書かれたプログラムで使用するためのものです。 EMLライブラリには、次の機能グループがいくつか含まれています。

- Vector —      () ; - Algebra —   ; - Signal —   ; - Image —   ; - Video —   ; - Volume —    ; - Graphics —    .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

データ配列の場合、たとえば、加算、要素ごとの乗算、配列の平均値の計算など、最も要求される操作が決定されます。

開発者は、Elbrusプラットフォームでベクトル並列処理を直接使用できます。つまり、複数のデータ要素を含む単一のレジスタで同じ操作を一度に実行できます。 このために、組み込み関数が使用され、その呼び出しは、このプラットフォーム用の高性能コードを備えたコンパイラーによって置き換えられます。 Elbrus-4Cマイクロプロセッサは、レジスタサイズが64ビットであるバージョン3の命令セットをサポートしています。 64ビットレジスタを使用すると、2つの実32ビット数、4つの16ビット整数、または8つの8ビット整数を同時に処理できるため、パフォーマンスが向上します。 Elbrusマイクロプロセッサの組み込み関数のセットは、組み込み関数SSE、SSE2のセットにほぼ類似しており、データ変換、ベクトル要素の初期化、算術演算、ビットごとの論理演算、ベクトル要素の置換などの操作が含まれます。

Elbrusアーキテクチャー向けのViolaおよびJones分類器の最適化

ヴィオラとジョーンズの開発された分類アルゴリズムの実験的検証は、ロシア連邦のパスポートの番号とシリーズ、およびロシア連邦の市民の姓、名前、ミドルネーム、性別、日付と出生地を含むロシア連邦のパスポートの3ページ目を検出するタスクで実行されました。 この問題を解決するために、バイナリ分類器がトレーニングされ、その入力はグレー画像を受け取り、480 x 360ピクセルのサイズに縮小されました。 このサイズに縮小しても入力画像の比率が維持されない場合、画像の最小寸法は対応するサイズに縮小され、比率は維持されたまま2番目のサイズが縮小されます。 分類子の出力は、パスポートページの有無として解釈され、その側面がフレームの端に平行になるように方向付けられます。

開発された分類器は、積分画像に基づいて計算された修正Haar二重長方形記号で動作します。

ここで、 Iは積分画像、 W 、 Hは合計を計算する長方形の幅と高さ、（ x 、 y ）はサブウィンドウの左上隅の座標、（ p 、 q ）は合計を計算する2番目の長方形のシフト、 rは属性の計算結果です。 従来のHaarのバイセントラル機能とは対照的に、このような機能は元の画像の明るさの変化に対してより耐性があります。

検出中、これらの計算はソース画像の各サブウィンドウに対して実行されます。 分類器の場合、これらのサブウィンドウが使用されるステップは水平および垂直の両方で1に等しいため、ソースイメージの各行のフォーム（1）の操作は、次のようなベクトルEML操作を使用して簡単に実装できます。

 - eml_Status eml_Vector_AddShift_32S(const eml_32s *pSrc1, const eml_32s *pSrc2, eml_32s *pDst, eml_32s len, eml_32s len) -       32-  Src1  pSrc2    2^shift      pDst. - eml_Status eml_Vector_SubShift_32S(const eml_32s *pSrc1, const eml_32s *pSrc2, eml_32s *pDst, eml_32s len, eml_32s len) -       32-  Src1  pSrc2    2^shift      pDst. - eml_Status eml_Vector_AddCShift_32S(const eml_32s *pSrc, eml_32s val, eml_32s *pDst, eml_32s len, eml_32s shift) -    val      32-  pSrc    2^shift      pDst. - eml_Status eml_Vector_DivShift_32S(const eml_16s *pSrc1, const eml_16s *pSrc2, eml_16s *pDst, eml_32s len, eml_32s shift) -       32-  Src1  pSrc2    2^shift      pDst.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、2-rectangular Haar特徴の計算はベクトル化されました。 図2は、分類器の水平アプリケーションの数に応じた、このような機能の計算時間を示しています。 実験は、Elbrus-4Cプロセッサを搭載したマシンで実行されました。 EMLを使用すると、オブジェクトを検出するプロセスで2長方形Haar機能を計算する時間を最大10倍高速化できることがわかります。これは、64以上の分類アプリケーションの数を計算するときに最も効果的です。

次に、元の画像の長さに応じて、1つのサブウィンドウの分類時間を推定します（図3を参照）。 EMLの使用により、ロシア連邦のパスポートのページの検出時間が30倍に短縮されたことがわかります。

図2-修正された2長方形Haar属性Tの計算時間のアプリケーション数への依存性

図3-分類器nの水平方向の適用回数に対する分類Tの計算時間の依存性

同様の結果は予想をはるかに超えていました。 どうやら、この理由は、STL実装（基本実装で使用）の機能とElbrusでメモリを操作する特性（たとえば、配列交換デバイス（特別なElbrusチップ）を使用するためのアライメントの必要性）です。 EMLライブラリの操作はこれらの状況を考慮し、開発者がアーキテクチャのニュアンスを「深く掘り下げる」必要なく、低レベルの操作をクールに加速できることを明らかにしました。

！ Elbrusコンピューターと製品はChipEXPO-2017でご覧いただけます

使用されたソースのリスト

1. Viola P.、Jones M. Robust Real-time Object Detection // International Journal of Computer Vision。 2001. [7]
2. Viola P.、Jones M.、Snow D.動きと外観のパターンを使用した歩行者の検出// Int。 J.計算 ヴィス 2005. Vol。 63、No。2。P.153–161。 [30]
3. Moutarde F.、Stanciulescu B.、Breheret A.新しい効率的なadaBoost機能を使用した車両と歩行者のリアルタイム視覚検出// 2008 IEEE International Conference on Intelligent RObots Systems（IROS 2008）。 2008. [33]
4. Chen S.、Hsieh J.道路標識の検出と認識を強化// 2008 Int。 確認 マッハ。 学ぶ。 サイバーン。 2008年。7月。 P. 3823–3826。 [36]
5. Freund Y.、Schapire REオンライン学習の決定理論的一般化と後押しへの応用// Journal of Computer and System Sciences、No. 55. Issue 1、August 1997、P. 119-139
6. Papageorgiou CP、Oren M.、Poggio T.オブジェクト検出の一般的なフレームワーク// Sixth Int。 確認 計算。 ヴィス IEEEカタログNo98CH36271。 1998. Vol。 6、1月号。 P. 555-562 [47]
7. テクスチャマッピング用のCrow FC Summed-areaテーブル// ACM SIGGRAPH Computer Graphics。 1984。 18、No. 3. P. 207–212 [49]
8. キムA.K.、ビチコフI.N. およびパーソナルコンピューター、サーバー、スーパーコンピューター向けのその他のロシア技術「エルブラス」//現代の情報技術とIT教育、M .:インターネットメディア開発のための基金、IT教育、人間の可能性「インターネットメディアリーグ」、2014年、番号10。39-50。
9. Kim A.K.、Perekatov V.I.、Ermakov S.G. Elbrusファミリーのマイクロプロセッサーおよびコンピューティングシステム。 -サンクトペテルブルク：ピーター、2013年-272 S.
10. Ishin P.A.、Loginov V.E.、Vasiliev P.P. Elbrusアーキテクチャ向けの高性能な数学およびマルチメディアライブラリを使用した計算の高速化//航空宇宙防衛のヘラルド、M。：Scientific and Production Association "Diamond"それら。 Acad。 A.A. Raspletina、2015年、No。4（8）。 64-68。