TBBによる処理の並列化と高速化
OpenCV2.1から，それまでのOpenMPに（一部取って）代わり，Intel Threading Building Blocks（TBB）を利用した並列化が導入されました．OSS 版 TBB のライセンスは GPL v2 with Runtime Exception ですが，商用ライセンスの商品版も存在します．
OpenMP はコンパイラに対するディレクティブでしたが，TBB ではライブラリの関数を呼び出します．つまり，OpenCV をコンパイルする際に，OpenMP の場合は OpenMP に対応したコンパイラが必要で，TBB の場合は TBB ライブラリをインストールする必要があります．この辺りの話やOpenMP，TBBの導入方法は，インストールに関する記事で簡単に触れました．
前述のように，すべての OpenMP 対応の関数が TBB に書き直されたわけではありませんが，現在の OpenCV では，以下のような関数で TBB の恩恵を受けることができます．
findStereoCorrespondenceBM
StereoBM::operator()(…)
cvExtractSURF
SURF::operator()(…)
cvDistTransform
cv::distanceTransform
CVDTree::find_best_split
CvForestTree::find_best_split
cvHaarDetectObjects
CascadeClassifier::detectMultiScale
HOGDescriptor::detectMultiScale
CvCascadeBoostTrainData::precalculate
cvCalcOpticalFlowPyrLK
cvEstimateRigidTransform
cv::estimateRigidTransform
これらの並列化は， cvinternal.h，または internal.hpp 内部で宣言される， parallel_for，parallel_do，parallel_reduce の切り替えによって実現されています．
#ifdef HAVE_TBB
namespace cv
{
typedef tbb::blocked_range<int> BlockedRange;
template<typename Body> static inline
void parallel_for( const BlockedRange& range, const Body& body )
{
tbb::parallel_for(range, body);
}
template<typename Iterator, typename Body> static inline
void parallel_do( Iterator first, Iterator last, const Body& body )
{
tbb::parallel_do(first, last, body);
}
typedef tbb::split Split;
template<typename Body> static inline
void parallel_reduce( const BlockedRange& range, Body& body )
{
tbb::parallel_reduce(range, body);
}
typedef tbb::concurrent_vector<Rect> ConcurrentRectVector;
}
#else
namespace cv
{
class BlockedRange
{
public:
BlockedRange() : _begin(0), _end(0), _grainsize(0) {}
BlockedRange(int b, int e, int g=1) : _begin(b), _end(e), _grainsize(g) {}
int begin() const { return _begin; }
int end() const { return _end; }
int grainsize() const { return _grainsize; }
protected:
int _begin, _end, _grainsize;
};
template<typename Body> static inline
void parallel_for( const BlockedRange& range, const Body& body )
{
body(range);
}
template<typename Iterator, typename Body> static inline
void parallel_do( Iterator first, Iterator last, const Body& body )
{
for( ; first != last; ++first )
body(*first);
}
class Split {};
template<typename Body> static inline
void parallel_reduce( const BlockedRange& range, Body& body )
{
body(range);
}
typedef std::vector<Rect> ConcurrentRectVector;
}
#endif
では，どの程度の高速化が見込めるのでしょうか．もちろん，並列化の度合いはアルゴリズムに大きく依存しますが，今回は，SURF，HOG，OpticalFlowPyrLK の３つの例について計測してみます．SURFとHOGは，OpenCV 付属のサンプルプログラムであり，計測対象となる処理も同様のものを利用しています．OpticalFlowPyrLKは，新たに書き起こしたプログラムで，計測対象とする関数は cvCalcOpticalFlowPyrLK です． これらのプログラムは，
SURF：最初に検出されたキーポイント（候補）の数
HOG：HOG 特徴量を利用して，異なるスケールの物体を検出する際の，（異なるスケールの）画像数
OpticalFlowPyrLK：フローを計算する（疎な）特徴点の数
の範囲に対して，それぞれ並列化を行います．例えば，HOG特徴を用いた「人検出（peopledetect.exe）」の例で言えば，異なるサイズのオブジェクトを検出するために，入力画像を複数（今回はおよそ５０）種類のサイズに縮小するわけですが，TBBによりこれらの画像それぞれに対して並列に処理を行うことができます．当然，この値がコア数よりも小さければ（４つの処理画像に，８コアで掛っても４コアは遊んでしまうので）並列化の恩恵は受けにくくなります．よって，以下のテストでは，十分に並列化可能な値になるように，パラメータや画像サイズを調整しています．今回は，2933×1081 の画像を利用し，（cvCalcOpticalFlowPyrLK の場合は）200×200の探索範囲を与えました．
TBB2.2以降（現在のバージョンは3.0）は，明示的なTBBの初期化が不要になりましたが，（必要ならば）以前と同様に初期化時に利用するスレッド数を指定することが可能です．ここでは，その機能を利用し，スレッド数を変化させながら処理時間を計測しました．
#include <tbb/task_scheduler_init.h> ... tbb::task_scheuler_init init(thread_num);
結果を以下のグラフに示します．ここで，横軸：利用スレッド数，縦軸：シングルスレッド時を1とした場合の処理速度比，を表しています．また，利用したCPUは，「Core 2 Duo ：２コア２スレッド」，「Core i5 ：２コア４スレッド（HT)」，「Core i7 ：４コア8スレッド（HT）」 です．それぞれの処理速度が，おおよそ論理コア数（2，4，8）のスレッドで頭打ちになっている様が分かります．
基本的には，明示的な初期化を行わずとも適切なスレッド数が選択されますので，ユーザや開発者がスレッド数を決定する必要はありません．OpenCV コンパイル時に導入するだけで，それなりの高速化が見込めますし，TBBを用いて自分のプログラムを別途並列化することも可能です．ぜひ，利用してみてはいかがでしょうか．
[左] SURF，[中] HOG.detectMultiScale，[右] opticalflow
