2016. 5.14.
石立 喬

OpenMPとVisual C++による並列処理(9)

――― テンプレートマッチングでは、OpenMPの効果が大きい -----

 テンプレートマッチングは、探す対象の画像の上にテンプレート(検索画像)を重ね、テンプレートを移動させながら、互いのピクセル値が一致するかどうかを確かめる作業で、処理量の多い演算であるので、OpenMPによる並列化に向いていると考え、試してみた。

テンプレートマッチングと処理時間
 テンプレートは型紙のことで、この型紙を、検索したい対象画像の上を全面に亘って移動させ、この型紙と一致する場所を探す方法を言う。ここでは、被探索画像として、0〜9の数字の並んだものを使用し、テンプレート(型紙、検索画像)には「3」の文字を使用する。
 テンプレートマッチングは、「OpenCVとVisual C++による画像処理と認識(12)」でも扱っており、ここでの試みと類似の内容が含まれている。
◎テンプレートマッチングは繰り返しの多い処理で、時間がかかる
 テンプレートマッチングは、4重のforループから成る実行時間のかかる処理である。被検索画像の幅をWIDTH、高さをHEIGHTとし、検索画像の幅をTWIDTH、高さをTHEIGHTとすると(Tはテンプレートの意)、
    for(j = 0; j < HEIGHT - THEIGHT; j++)
      for(i = 0; i < HEIGHT - THEIGHT; i++)
        for(q = 0; q < THEIGHT; q++)
          for(p = 0; p < TWIDTH; p++)
のforループを回すことになる。
 ここで使用するWIDTH = 512、HEIGHT = 384、TWIDTH = 32、THEIGHT = 64の場合には、最も内側の処理は、約3 x 108回実行される。
◎テンプレートマッチングの実行時間は if 文の中の一致判定時間が大部分を占める
 forループの最も内側では、被探索画像のピクセルの値と、対応する探索画像のピクセルの値が一致しているかどうかの判定が行われる。具体的には、
    if(data[(i + p) + (j + q) * WIDTH] == tdata[p + q * TWIDTH])
である。dataは被検索画像のピクセル情報の一次元配列、pdataは同じく検索画像のものである。ピクセル情報として、どのような型(type)を使って一致を判定するかで、実行時間に大きな差が出ることが分かった。

作成したプログラム
 「・・・による並列処理(4)」を基礎にしている。図1に示すように、プロジェクトの最初の部分で、複数の関数で使用する定数を宣言し、ユーザ関数のプロトタイプを宣言している。
 実行時間測定用の関数をUserProgramから呼び出す方法は従来通りであるので省略する。


図1 プロジェクトの最初の部分でグローバル定数とユーザ関数を宣言する

COLORREFデータをそのまま使うdetectMatching関数
 被検索画像、検索画像ともに、ピクセルデータはCOLORREF型の一次配列dataとtdataとして受け取る。これをそのまま比較するのが、図2に示すdetectMatching関数である。
 検索画像(テンプレート)の全てのピクセル数は2048(32 x 64)であるので、ほぼすべてのピクセルが一致するとして、sum > 2000を用いて、一致か不一致かを判定している。もし一致していれば、太さ2の赤色のペンと空白の(NULL)ブラシを用いて32 x 64の枠を描く。
 OpenMPを使用しないVC++デフォルトの場合は、#pragma文をコメントアウトする。
 この関数を使って、dataとpdataをそのまま使うのではなく、GetRValueマクロでR成分を取り出してから比較する試みも行った。


図2 detectMatching関数は元のデータを直接比較する


二次元 1/0 データに変換して使うdetectMatching1関数
 COLORREF型はDWORD型であり、32ビットの符号なし整数である。これを直接比較するよりは、あらかじめ1と0の単純な型に変換して(ついでに一次元配列から二次元配列への変換も行う)から一致判定を行うと高速化できるのではないかと考え、図3のdetectMatching1関数を作成した。
 図3は、0または1のみのINT型の二次元配列data2とtdata2に変換した例を示す。実際には、INT型の他に、INT16、INT8、BYTE、BOOLも確かめた。



図3 detectMatching1関数は 1/0 の値に変換してから比較する


detectMatching関数とdetectMatching1関数の実行結果
 Release構成のdetectMatching関数でOpenMPを使用した結果の例を図4に示す。右上にはテンプレート画像(検索画像)、下には被検索画像を表示してある。被検索画像上には、テンプレートと一致した場所が、赤い枠で描かれている。


図4 Release構成でdetectMatching関数を用い、COLORREF型のデータを直接比較した場合


◎detectMatching関数を用いてCOLORREF型の一次元配列dataとtdataで直接比較した場合
 COLORREF型の一次元配列をそのまま使用して画像の一致度合いを比較すると、図5に示すように、Release構成でのOpenMPによる短縮率は、初回が44%、平均で24%であった。OpenMPの場合、初回近辺に時間がかかり、次第に短縮率が下がり(実行時間が短くなり)、一定値に落ち着く傾向がある。


図5 detectMatching関数での測定結果の例、OPenMPは次第に速くなる


◎detectMatching関数を用いて、GetRValueマクロでBYTE型にしてから比較した場合
 画像の一致度合いをCOLORREFで直接行うより、R成分を抜き出して行う方が高速化できるかもしれないと考え、
   if(GetRValue(data[(i + p) + (j + q) * WIDTH]) == GetRValue(tdata[p + q * TWIDTH]))
のように判定条件を書き換えた。しかし、結果は逆で、比較するビット数を減らした方が、かえって実行時間を長くした。図6に結果を示すように、VC++デフォルトで約4.5倍、OpenMP使用の平均値でで約2.9倍に実行時間が多くかかった。図で、VC++のグラフは長くなりすぎるので、途中で切ってある。
 OpenMP使用による短縮度を求めると、初回が33%、平均で16%であった。初回近辺の33%は理解できるが、平均の16%は、スレッド数4を考えると不可解な数字で、VC++に対しては行われず、OpenMPのみに行われる、何らかの高速化処理が働くものと考えられる。


図6 detectMatching関数で、GetRValueマクロを使用した例、OpenMPが速すぎる?


◎detectMatching1関数を用いて、あらかじめ 1/0 の二次元配列にしてから比較した場合
 図3に示したプログラムによって、あらかじめ 1/0 に変換してから比較した結果を、detectMatching関数の結果と共に下の表1に示す。表1は、100回ずつのプログラムを5回実行して平均したもので、図5、図6の結果と完全には一致しない。

表1 Relese構成での色々な場合の実行時間測定結果(500回の平均)


結果をまとめると
 1)INT型とBOOL型が速く、detectMaching関数のCOLORREF型と同等である。
      INT ----------- 32ビット、符号あり整数
      BOOL --------- 同上
      COLORREF ----- 32ビット、符号なし整数
   これらはすべて32ビットの整数である。
 2)次いでINT8型とBYTE型が速く、detectMatching関数のGetRValueマクロ使用より若干速い。
      INT8 ----------- 8ビット、符号あり整数
      BYTE ---------- 8ビット、符号なし整数
   いずれも8ビット整数である。
 3)INT16型が一番遅く、detectMatching関数のGetRValueマクロ使用と同等である。
      INT16は16ビットの符号あり整数である。
 4)VC++デフォルトと比べたOpenMPによる短縮率は、平均で比較すると、
      32ビット ---------- 24%
       8ビット ---------- 16〜18%
      16ビット ---------- 16%
   となり、スレッド数4としては考えられない、良すぎる数字である。
 5)OpenMPでの一回目の実行時間と比較すると、速い方から順に、短縮率が46%〜51%、34%〜35%、32%となり、オーバーヘッドを考慮に入れても、こちらは理解できる数字である。

結 論
 テンプレートマッチングに要する時間のほとんどは、被検索画像と検索画像との比較である。比較にCOLORREF型をそのまま使うのか、そこから抽出した別の単純なデータを使うのかによって、時間が変わった。
 画像から簡単に得られるピクセル情報のCOLORREF型は32ビットの符号なし整数である。これをそのまま比較するのが最も速く、あえて他の型に変換してから比較する必要はない。32ビットのCPUを使用する場合、それより短いビット数の単位で処理を行うと、かえって時間がかかることが分かった(8ビットデータを複数個一度にキャッシュして、そこから持ってくると高速化できると考えたが、そうでなかった)。
 VC++デフォルトの場合には、同じテンプレートマッチング処理を繰り返しても、実行速度はほとんど変わらなかった。しかし、OpenMP使用の場合には、第一回目は実行時間が長く、次第に下がっていって、あとは一定値に安定する傾向が見られた。
 OpenMP使用の第一回目とVC++デフォルトで比較すると、短縮率が約50%であり、OpenMPの効果はそれほど大きくない。しかし、同じ処理の繰り返しを重ねた後の安定状態では、短縮率が約25%となり、オーバーヘッドも考慮すると、良すぎる数値である。この原因はわからない。
 絶対的な実行時間が長くなるので使用は考えられないが、8ビットや16ビットのデータを用いた比較では、OpenMPによる短縮効果がさらに大きくなり、約16%程度まで短縮されるという、スレッド数4からは考えられない驚異的な結果になった。
 同一テンプレートの使用でなく、繰り返しごとに検索画像を変えながら実行時間を測定したが、この傾向は変わらなかった。






「Visual C++の勉強部屋」(目次)