はい、Haar属性に基づくカスケード分類子（Viola-Jonesメソッド）は、カスケードLBP分類子よりも速度が劣ります。 これは、HOG機能に基づく検出器、さらには畳み込みニューラルネットワークに基づく検出器よりも精度が低くなります。 さらに、LBPカスケードの精度よりも高い精度が必要な場合、特定のニッチがありますが、より正確な検出器の速度は十分に高くありません。 同様に重要な要素は、カスケードHaar分類器には、 OpenCVライブラリの標準パッケージを含む、すでに訓練された多数のカスケードがあることです。 したがって、このアルゴリズムの速度は非常に重要です。 そのため、著者は一時的に最適化に取り組むようになりました。
さて、顔の検出に関する記事はレナの写真なしで何ができますか？
生産性の方法
Habrahabrを含む、Viola-Jonesメソッドの動作に関する詳細な説明がかなりあります： ソース1 、 ソース2 。 したがって、私は彼の詳細な説明には触れません。上記の情報源でこれを読むことに興味があるでしょう。 Viola-Jonesの方法を高速化する方法について、少しお話したいと思います。
- Viola-Jonesメソッドは、ある種の厳格な固定アルゴリズムではありません。 そのカスケードは、トレーニングの結果として形成されます。 したがって、作業の速度は、オブジェクトの複雑さと検出するオブジェクトのサイズに応じて大きく異なります。 作業を高速化する最も簡単な方法は、最小オブジェクトに制限を設定するか、ピラミッドのステップを増やすことです。 ただし、これらの方法には、精度の低下や誤検知の数の増加という副作用があります。 カスケードの再トレーニングは、作業の精度と速度の点で非常に重要な影響を与える場合があります。 ただし、これは大規模なトレーニングサンプルの収集に関連するかなりコストのかかるプロセスです。 そして、トレーニング自体は非常に高速なプロセスを言うことではありません。
- 加速するかなり明白な方法は、画像のさまざまな部分を並列ストリームで処理することです。 このメソッドはすでにOpenCVに実装されているため、ここでは何もしません。
- 並列処理にはグラフィックアクセラレータを使用します。 ここでも、OpenCVにはすでに実装があります。 欠点は、グラフィックアクセラレータの要件です。
- SIMDプロセッサのベクトル命令を使用して、アルゴリズムを高速化します。 ベクター命令は、ほとんどすべての最新のプロセッサーに搭載されています。 残念ながら、それらはプロセッサごとに異なるため、プロセッサごとに異なる実装が必要です。 さらに、ベクトル命令を効果的に使用するには、アルゴリズムを大幅に変更する必要があります。 この方法は、この記事専用です。
アルゴリズムの元の（スカラー）バージョン
このアルゴリズムのソースコードを OpenCVから取得すると、さまざまなSIMD（SSE、AVX、NEON）命令を使用して、このアルゴリズムを高速化する試みが数多く見られます。 これらの試みがどれほど成功したかについての正確な数値的推定値はありません。 ただし、ソースコードから判断すると、ベクトル命令（スカラーアナログのみ）は最適化に使用されないか、データがベクトルレジスタbitwiseにロードされるため、アルゴリズムの全体的なパフォーマンスに致命的な影響を及ぼすため、加速はほとんど重要ではありませんでした。
そのため、特定のスケールに対して、カスケードHaar分類アルゴリズムのスカラーバージョン （その簡易バージョンを以下に示します）を検討します。
void HaarDetect(const HaarCascade & hid, const Image & mask, const Rect & rect, int step, Image & dst) { for (ptrdiff_t row = rect.top; row < rect.bottom; row += step) { size_t p_offset = row * hid.sum.stride / sizeof(uint32_t); size_t pq_offset = row * hid.sqsum.stride / sizeof(uint32_t); for (ptrdiff_t col = rect.left; col < rect.right; col += step) { if (mask.At<uint32_t>(col, row) == 0) continue; float norm = Norm(hid, pq_offset + col); if (Detect(hid, p_offset + col, 0, norm) > 0) dst.At<uint32_t>(col, row) = 1; } } }
ここでは、すべてのポイントについて画像がスキャンされます（加速のために、原則として、画像は2段階でスキャンされます）。 各ポイントに対して、正規化係数が計算されます（このポイントの近くの画像の明るさとコントラストに依存します）：
uint32_t Sum(uint32_t * const ptr[4], size_t offset) { return ptr[0][offset] - ptr[1][offset] - ptr[2][offset] + ptr[3][offset]; } float Norm(const HaarCascade & hid, size_t offset) { float sum = float(Sum(hid.p, offset)); float sqsum = float(Sum(hid.pq, offset)); float q = sqsum*hid.windowArea - sum *sum; return q < 0.0f ? 1.0f : sqrtf(q); }
また、分類自体：
float WeightedSum(const WeightedRect & rect, size_t offset) { int sum = rect.p0[offset] - rect.p1[offset] - rect.p2[offset] + rect.p3[offset]; return rect.weight*sum; } int Detect(const HaarCascade & hid, size_t offset, int startStage, float norm) { const HaarCascade::Stage * stages = hid.stages.data(); const HaarCascade::Node * node = hid.nodes.data() + stages[startStage].first; const float * leaves = hid.leaves.data() + stages[startStage].first * 2; for (int i = startStage, n = (int)hid.stages.size(); i < n; ++i) { const HaarCascade::Stage & stage = stages[i]; const HaarCascade::Node * end = node + stage.ntrees; float stageSum = 0.0; for (; node < end; ++node, leaves += 2) { const HaarCascade::Feature & feature = hid.features[node->featureIdx]; float sum = WeightedSum(feature.rect[0], offset) + WeightedSum(feature.rect[1], offset); if (feature.rect[2].p0) sum += WeightedSum(feature.rect[2], offset); stageSum += leaves[sum >= node->threshold*norm]; } if (stageSum < stage.threshold) return -i; } return 1; }
ここでは、事前に計算された積分画像を使用して、Haarサインが計算されます 。
アルゴリズムのベクトル化方法
上記のアルゴリズムの分析は、主要な計算リソースが加重積分の計算に費やされていることを示しています（ WeightedSum関数）。 したがって、まずベクトル化する必要があります。 これを行うには2つの方法しかありません。
- 1つのSIMDベクトルで複数のHaar符号を同時に計算しようとしています。
- 1つのSIMDベクトルで複数の画像ポイントを一度に同時に計算しようとしています。
注目のベクトル化
一見、Haar符号の計算をベクトル化するのが最適です（ちなみに、これはOpenCVで行われました）。 ただし、1つだけあります。計算する必要があるデータは、メモリ内にランダムに散在しています。 したがって、まずスカラー読み取り操作を使用してそこから収集し、次にスカラー書き込み操作を使用して計算結果を分散させる必要があります。 ギャザースキャッター操作（AVX2とAVX-512にあります）は確かに使用できますが、速度はスカラーコードを使用する場合に比べて同等であり、場合によっては遅くなります。
点ベクトル化
画像ポイントによるベクトル化はそれほど明白ではありません（実際、ベクトル化は実際に最も外側のループに沿って実行されます）。 ただし、隣接するポイントの統合画像のデータは近くにあるため、ベクトル演算を使用して効率的に読み込むことができます。 さらに、この方法は、SIMDベクトルのさまざまな長さに合わせて簡単にスケーリングできます。 これで、プラスが終了し、次に問題のリストが表示されます。
- Viola-Jonesアルゴリズムの有効性は、各段階で明らかに間違ったポイントが破棄されるという事実に基づいています。 破棄されたポイントの割合は、トレーニングパラメーターによって異なり、デフォルトでは50％です。 複数のポイントを持つSIMDベクトルを処理する場合、すべての要素が破棄されるまでステージの計算を続行する必要があります。 これにより、後続のステージの計算におけるメソッドの有効性が低下します。 幸いなことに、隣接するポイントが破棄される段階は非常に強く相関しています。 さらに、ベクトルに検証用のポイントが1つしか残っていない場合は、アルゴリズムのスカラーバージョンに進むことができます。この場合、より効率的です。
- 小規模に最適化するために、OpenCVの元のアルゴリズムはステップ2でポイントをチェックします。これにより、スカラーコードは高速になりますが、最初の段階では何もしないで半分の計算を行う必要があるため、ベクトル命令の効率が低下します。 幸いなことに、この問題にはかなりエレガントな解決策があります。 しかし、後で詳しく説明します。
アルゴリズムのSIMDバージョン
この記事では、 SSE4.1のアルゴリズムの簡易バージョン、 AVX2 、 AVX-512 、およびNEONのバージョンで同じアプローチを使用します。
まず、画像のすべてのポイントを隙間なくスキャンする場合を考えます。
void DetectionHaarDetect32fp(const HidHaarCascade & hid, const Image & mask, const Rect & rect, Image & dst) { size_t rightAligned = rect.left + Simd::AlignLo(rect.Width(), 4); for (ptrdiff_t row = rect.top; row < rect.bottom; row += 1) { size_t p_offset = row * hid.sum.stride / sizeof(uint32_t); size_t pq_offset = row * hid.sqsum.stride / sizeof(uint32_t); size_t col = rect.left; for (; col < rightAligned; col += 4) { __m128i result = _mm_loadu_si128((__m128i*)(mask.Row<uint32_t>(row) + col)); if (_mm_testz_si128(result, _mm_set1_epi32(1))) continue; __m128 norm = Norm32fp(hid, pq_offset + col); Detect32f(hid, p_offset + col, norm, result); _mm_storeu_si128((__m128i*)(dst.Row<uint32_t>(row) + col), result); } for (; col < rect.right; col += 1) { if (mask.At<uint32_t>(col, row) == 0) continue; float norm = Norm32f(hid, pq_offset + col); if (Detect(hid, p_offset + col, 0, norm) > 0) dst.At<uint32_t>(col, row) = 1; } } }
ここでは、スカラーバージョンとは対照的に、画像は単一のポイントではなく、4ポイントのブロックでスキャンされます（エッジポイントのみがスカラーで処理されます）。 4点のブロックの正規化係数は、次のように計算されます。
inline __m128 ValidSqrt(__m128 value) { return _mm_blendv_ps(_mm_set1_ps(1.0f), _mm_sqrt_ps(value), _mm_cmpgt_ps(value, _mm_set1_ps(0.0f))); } inline __m128i Sum32ip(uint32_t * const ptr[4], size_t offset) { __m128i s0 = _mm_loadu_si128((__m128i*)(ptr[0] + offset)); __m128i s1 = _mm_loadu_si128((__m128i*)(ptr[1] + offset)); __m128i s2 = _mm_loadu_si128((__m128i*)(ptr[2] + offset)); __m128i s3 = _mm_loadu_si128((__m128i*)(ptr[3] + offset)); return _mm_sub_epi32(_mm_sub_epi32(s0, s1), _mm_sub_epi32(s2, s3)); } inline __m128 Norm32fp(const HidHaarCascade & hid, size_t offset) { __m128 area = _mm_set1_ps(hid.windowArea); __m128 sum = _mm_cvtepi32_ps(Sum32ip(hid.p, offset)); __m128 sqsum = _mm_cvtepi32_ps(Sum32ip(hid.pq, offset)); return ValidSqrt(_mm_sub_ps(_mm_mul_ps(sqsum, area), _mm_mul_ps(sum, sum))); }
4ポイントのブロックの分類自体：
inline int ResultCount(__m128i result) { uint32_t SIMD_ALIGNED(16) buffer[4]; _mm_store_si128((__m128i*)buffer, _mm_sad_epu8(result, _mm_setzero_si128())); return buffer[0] + buffer[2]; } inline __m128 WeightedSum32f(const WeightedRect & rect, size_t offset) { __m128i s0 = _mm_loadu_si128((__m128i*)(rect.p0 + offset)); __m128i s1 = _mm_loadu_si128((__m128i*)(rect.p1 + offset)); __m128i s2 = _mm_loadu_si128((__m128i*)(rect.p2 + offset)); __m128i s3 = _mm_loadu_si128((__m128i*)(rect.p3 + offset)); __m128i sum = _mm_sub_epi32(_mm_sub_epi32(s0, s1), _mm_sub_epi32(s2, s3)); return _mm_mul_ps(_mm_cvtepi32_ps(sum), _mm_set1_ps(rect.weight)); } inline void StageSum32f(const float * leaves, float threshold, const __m128 & sum, const __m128 & norm, __m128 & stageSum) { __m128 mask = _mm_cmplt_ps(sum, _mm_mul_ps(_mm_set1_ps(threshold), norm)); stageSum = _mm_add_ps(stageSum, _mm_blendv_ps(_mm_set1_ps(leaves[1]), _mm_set1_ps(leaves[0]), mask)); } void Detect32f(const HidHaarCascade & hid, size_t offset, const __m128 & norm, __m128i & result) { typedef HidHaarCascade Hid; const float * leaves = hid.leaves.data(); const Hid::Node * node = hid.nodes.data(); const Hid::Stage * stages = hid.stages.data(); for (int i = 0, n = (int)hid.stages.size(); i < n; ++i) { const Hid::Stage & stage = stages[i]; if (stage.canSkip) continue; const Hid::Node * end = node + stage.ntrees; __m128 stageSum = _mm_setzero_ps(); if (stage.hasThree) { for (; node < end; ++node, leaves += 2) { const Hid::Feature & feature = hid.features[node->featureIdx]; __m128 sum = _mm_add_ps(WeightedSum32f(feature.rect[0], offset), WeightedSum32f(feature.rect[1], offset)); if (feature.rect[2].p0) sum = _mm_add_ps(sum, WeightedSum32f(feature.rect[2], offset)); StageSum32f(leaves, node->threshold, sum, norm, stageSum); } } else { for (; node < end; ++node, leaves += 2) { const Hid::Feature & feature = hid.features[node->featureIdx]; __m128 sum = _mm_add_ps(WeightedSum32f(feature.rect[0], offset), WeightedSum32f(feature.rect[1], offset)); StageSum32f(leaves, node->threshold, sum, norm, stageSum); } } result = _mm_andnot_si128(_mm_castps_si128(_mm_cmpgt_ps(_mm_set1_ps(stage.threshold), stageSum)), result); int resultCount = ResultCount(result); if (resultCount == 0) // , : { return; } else if (resultCount == 1) // 1 , : { uint32_t SIMD_ALIGNED(16) _result[4]; float SIMD_ALIGNED(16) _norm[4]; _mm_store_si128((__m128i*)_result, result); _mm_store_ps(_norm, norm); for (int j = 0; j < 4; ++j) { if (_result[j]) { _result[j] = Detect32f(hid, offset + j, i + 1, _norm[j]) > 0 ? 1 : 0; break; } } result = _mm_load_si128((__m128i*)_result); return; } } }
ご覧のとおり、アルゴリズムはスカラーバージョンとほぼ同じです（もちろん、通常の実数の代わりにSSEベクトルを使用するように調整されています）。
ここで、ステップ2で同じアルゴリズムを実行する必要がある状況を考えてみましょう。最も簡単なオプションは、4つの数値の2つのベクトルをメモリからロードし、そのうちの1つを形成することです（偶数のみを残す）。 ただし、完全に不満足なパフォーマンスを示しています。 幸いなことに、元のデータを並べ替えるちょっとしたトリックを行うことができます。元の統合画像では、偶数ポイントを行の先頭に、奇数ポイントを行の最後に移動します。 次に、偶数/奇数要素を持つベクトルをロードすると、簡単な操作になります。 さらに、同じコードをスキャンに使用できます。
最適化データは、異なるベクトルサイズ（ AVX2の場合は 8、 AVX-512の場合は 16）および他のプラットフォーム（ARMプラットフォームの場合はNEONなど）に対しても同様に簡単に実装できます。
最適化結果
次の表は、アルゴリズムのさまざまな実装に対する画像のスキャン時間（ミリ秒単位）を示しています。 テストでは、1920x1080サイズの画像が使用されました。 元の画像を拡大縮小せずにスキャンを実行しました。
| 機能 | スカラー | SSE4.1 | AVX2 | AVX-512 |
|---|---|---|---|---|
| 共通 | 227.499 | 111.509 | 74.952 | 54.579 |
| DetectionHaarDetect32fi（0） | 84.792 | 45.771 | 32.716 | 25.961 |
| DetectionHaarDetect32fi（1） | 162.779 | 79.007 | 50.996 | 36.841 |
| DetectionHaarDetect32fp（0） | 329.904 | 159.355 | 109.725 | 80.862 |
| DetectionHaarDetect32fp（1） | 588.270 | 268.298 | 172.396 | 114.735 |
次の表は、ベース（スケーラブル）バージョンと比較して達成された加速を示しています。
| 機能 | SSE4.1 /スカラー | AVX2 /スカラー | AVX-512 /スカラー |
|---|---|---|---|
| 共通 | 2.04 | 3.04 | 4.17 |
| DetectionHaarDetect32fi（0） | 1.85 | 2.59 | 3.27 |
| DetectionHaarDetect32fi（1） | 2.06 | 3.19 | 4.42 |
| DetectionHaarDetect32fp（0） | 2.07 | 3.01 | 4.08 |
| DetectionHaarDetect32fp（1） | 2.19 | 3.41 | 5.13 |
| 機能 | SSE4.1 /スカラー | AVX2 / SSE4.1 | AVX-512 / AVX2 |
|---|---|---|---|
| 共通 | 2.04 | 1.49 | 1.37 |
| DetectionHaarDetect32fi（0） | 1.85 | 1.40 | 1.26 |
| DetectionHaarDetect32fi（1） | 2.06 | 1.55 | 1.38 |
| DetectionHaarDetect32fp（0） | 2.07 | 1.45 | 1.36 |
| DetectionHaarDetect32fp（1） | 2.19 | 1.56 | 1.50 |
ソフトウェア実装
結論として、上記のアルゴリズムのソフトウェア実装について、少しお話したいと思います。 Simdプロジェクトのフレームワークでは、C ++クラスSimd :: Detectionが実装されました。 その内部では、SimdライブラリライブラリAPIを使用した低レベルの作業が行われています。 重要な利点の1つは、使用されているカスケード（HAARおよびLBP）とOpenCVのカスケードとの互換性、および使いやすさです。 以下は、このフレームワークを使用した顔検出の例です。
#include <iostream> #include <string> #include "opencv2/opencv.hpp" #define SIMD_OPENCV_ENABLE #include "Simd/SimdDetection.hpp" #include "Simd/SimdDrawing.hpp" int main(int argc, char * argv[]) { if (argc < 2) { std::cout << "You have to set video source! It can be 0 for camera or video file name." << std::endl; return 1; } std::string source = argv[1]; cv::VideoCapture capture; if (source == "0") capture.open(0); else capture.open(source); if (!capture.isOpened()) { std::cout << "Can't capture '" << source << "' !" << std::endl; return 1; } typedef Simd::Detection<Simd::Allocator> Detection; Detection detection; detection.Load("../../data/cascade/haar_face_0.xml"); bool inited = false; const char * WINDOW_NAME = "FaceDetection"; cv::namedWindow(WINDOW_NAME, 1); for (;;) { cv::Mat frame; capture >> frame; Detection::View image = frame; if (!inited) { detection.Init(image.Size(), 1.2, image.Size() / 20); inited = true; } Detection::Objects objects; detection.Detect(image, objects); for (size_t i = 0; i < objects.size(); ++i) Simd::DrawRectangle(image, objects[i].rect, Simd::Pixel::Bgr24(0, 255, 255)); cv::imshow(WINDOW_NAME, frame); if (cvWaitKey(1) == 27)// "press 'Esc' to break video"; break; } return 0; }