アルゴリズムの最適化に関する前回の
記事で始めた作業を続けます。 何が行われたか簡単に説明します。 既製の
Javaソースと 、
Viola-Jonesアルゴリズムの実装の1つの
カスケードモデルが採用されました。 このアルゴリズムは、写真内のオブジェクトの検索、特に顔の検索に使用されます。 携帯電話でテストを実施した結果、300 x 400の写真で元のJavaコードが54秒間機能することがわかりました。遅すぎたため、C ++で書き直したコードは14秒の結果を示しました。 コメントでは、次のようにC ++へのJava実装に追いつくことが提案されました。ボトルネックをプロファイリングして見つけ、2次元配列を1次元配列に置き換えます。 また、アルゴリズムをC ++で並列化する計画がありました。 すべてが行われ、調査されました。結果は以下のとおりです。
Javaリリースのプロファイルを作成します。 アルゴリズムの主要部分の動作時に統計を取得します。 このような画像が
表示されます （
ファイル内の結果は誰にとっても興味深いものです）。
リストメソッドは多くの時間を消費します。 この状況では、すべてのリストをC ++で使用される配列に簡単に置き換えることができます。 置換して、次の結果を取得します（
ファイル内 ）：
Math.sqrtに注意してください。実行の割合は6.7から13.5に上昇しました。つまり、他のユーザーが時間消費を削減し、電話での起動が38秒でした。 残りの時間は、配列要素とMath.sqrtの乗算、除算、取得というプリミティブメソッドに費やされます。 したがって、どこで何を変更できるかがわかりません。 C ++はコードを正確に繰り返します。
2次元配列ではなく1次元配列 。 次のコードを変更します。
int[][] grayImage=new int[width][height]; int[][] squares=new int[width][height];
に：
int[] grayImage=new int[width * height]; int[] squares=new int[width * height];
そして、適切な使用場所で：
int total_x = grayImage[(i + w) * height + j + h] + grayImage[i * height + j] - grayImage[i * height + j + h] - grayImage[(i + w) * height + j]; int total_x2 = squares[(i + w) * height + j + h] + squares[i * height + j] - squares[i * height + j + h] - squares[(i + w) * height + j]; ... rect_sum += (int) ((grayImage[rx2 * height + ry2] - grayImage[rx1 * height + ry2] - grayImage[rx2 * height + ry1] + grayImage[rx1 * height + ry1]) * r.weight); }
結果はまったく同じです。 乗算操作の数を減らして、配列の要素を計算してみましょう。 これをしましょう：
int iwh = (i + w) * height; int ih = i * height; int total_x = grayImage[iwh + j + h] + grayImage[ih + j] - grayImage[ih + j + h] - grayImage[iwh + j]; int total_x2 = squares[iwh + j + h] + squares[ih + j] - squares[ih + j + h] - squares[iwh + j]; ... int rx2h = rx2 * height; int rx1h = rx1 * height; rect_sum += (int) ((grayImage[rx2h + ry2] - grayImage[rx1h + ry2] - grayImage[rx2h + ry1] + grayImage[rx1h + ry1]) * r.weight);
結果は変更されていません。 1次元配列はプラスではなく、コードの可読性のマイナスのみでした。
したがって、Javaを使用すると、C ++では38秒でしたが14秒でした。
並列化。 クアッドコアプロセッサを搭載したGT-I9300I電話で、C ++で記述されたアルゴリズムを並列化してみましょう。 Androidでは、ドキュメントに書かれているようにposixスレッドを使用できますが、わずかにトリミングされていますが、スレッドを作成し、パラメーターを渡し、実行を待つだけです。 これはすべて単純に行われます。
#include <pthread.h> ... extern "C" { struct ThreadArgument { void *array; int threadNum; }; void *worker_thread(void *arg) { ThreadArgument *arg1 = (ThreadArgument*) arg; ((Detector*) (arg1->array))->workerTansient(arg1->threadNum); pthread_exit(NULL); } } ... pthread_t m_pt[threadsNum - 1]; if (threadsNum > 1) { res2 = new VectorRects*[threadsNum - 1]; for (int l = 0; l < threadsNum - 1; l++) { ThreadArgument* args = new ThreadArgument; args->array = (void*)this; args->threadNum = l + 1; int success = pthread_create(&m_pt[l], NULL, worker_thread, args); if (success == 0) { __android_log_print(ANDROID_LOG_INFO, "Detector", "thread %d started", l); } } } __android_log_print(ANDROID_LOG_INFO, "Detector", "gettFaces3 baseScale=%f maxScale=%f scale_inc=%f", baseScale, maxScale, scale_inc); ret = getResult(0); if (threadsNum > 1) { for (int l = 0; l < threadsNum - 1; l++) { int success = pthread_join(m_pt[l], NULL); for (int b = 0; b < res2[l]->currIndex; b++) { ret->addRect(res2[l]->rects[b]); } } } ... VectorRects* Detector::workerTansient(int threadNum) { __android_log_print(ANDROID_LOG_INFO, "Detector", "workerTansient thread running %d", threadNum); res2[threadNum - 1] = getResult(threadNum); return NULL; } ...
次の結果が得られます。1つのスレッドで14秒、2つのスレッドで8秒、3つのスレッドで5秒、4つ以上のスレッドで4秒。 シングルコアプロセッサを搭載したNexus S仮想デバイスでは、並列化によって何も起こりませんでした。
入手したアルゴリズムのソースは、
ここからダウンロードでき
ます 。 次のように使用します。
Detector detector = Detector.create(inputHaas); List<Rectangle> res = detector.getFaces(image, 1.2f, 1.1f, .05f, 2, true, useCpp, threadsNum);
ここで、inputHaasはモデルストリーム、つまり 元のアルゴリズムのファイルhaarcascade_frontalface_default.xml、useCpp-C ++を使用するかどうか、threadsNum-C ++コードのスレッド数。 検出器は一度トリガーされると想定されます。
合計 反復で使用されるLinkedListを全体として配列に置き換えると、現在のアルゴリズムでは1.5倍の増加が見られましたが、C ++での実装には2.5倍遅れています。 2次元配列から1次元配列への変換では、変更はありませんでした。 C ++での並列化を使用して、クアッドコアプロセッサでプロセスを3倍高速化することができました。これは、すでにはるかに優れていますが、理想からはほど遠いものです。 RenderScriptに目を向けることができます。これは、ネイティブレベルでの複雑な計算のメカニズムです。