Halide 〜画像処理を高速化する〜

はじめに

今回はHalideを紹介する。

Halideとは

Halideは、画像処理に特化したDomain Specific Language(DSL)である。高速化を目的とした言語であり、C++プログラム内に記述される。現在対応しているプラットフォームは、x86/SSE, ARM v7/NEON, CUDA, OpenCLである。Halideの大きな特長は、アルゴリズムとスケジューリングの記述を分離する点である。ここでスケジューリングとは

  • 並列化
  • ベクトル化(SIMD命令の発行)
  • ブロック化(処理の局所化)

を組み合わせ、効率よくタスクを実行する手順を見つけることである。ハードウェアに依存しないアルゴリズムの記述が可能であり、各ハードウェアごとに最適なスケジューリングを行うことができる。Halideプログラムの実行までの流れは以下のようになる。

  1. C++プログラム内にHalideの提供するクラスや関数(Halide::Func, Halide::Expr, Halide::Varなど)を用いてコードを記述する。
  2. C++コンパイラでオブジェクトファイルを生成する。
  3. Halideのlibファイル(libHalide.a)とリンクする。Halide::Func, Halide::Expr, Halide::Varなどで書かれた部分は、libHalide.aとリンクすることで実行可能になる。
  4. 初めてHalideコードが実行されるとき、動的にHalideコンパイラが起動し、高速なバイナリコードが生成され、画像処理が行われる。2回目以降の計算では既存のバイナリコードが使われる。

HalideコンパイラはCで書かれたプログラムであり、libファイル(静的ライブラリ)とヘッダファイルとして提供される。Halideコンパイラは本体プログラムの実行時に動的に起動すると書いたが、静的にHalideコードを実行する(あらかじめHalideコードをコンパイルしておく)手段も提供されている。これについては後述する。

拡大・縮小処理を例に取り、アルゴリズムの説明のあと実際のコードを示す。

拡大・縮小処理のアルゴリズム

拡大・縮小アルゴリズムの手順を以下に示す(下図参照)。

  1. いま、拡大後のある画素Aを考える。
  2. この画素が元画像ではどこに位置するのかを逆算する。一般的にこの位置座標は浮動小数点で表される(画素B)。
  3. 画素Bの周辺に存在する画素から画素Bに割り振る画素値を計算する。


上図において、格子点は画素に相当する。画素Bへ割り振る画素値の計算の仕方により以下3つの手法が存在する。

  1. nearest neighbor法
  2. bi-linear法
  3. bi-cubic法

記載した順に処理は重くなり、画質は良くなる。ここでは2番目のbi-linearを取り上げる。
bi-linearでは下図に示した面積c_0,c_1,c_2,c_3を求める。図中のd_i,d_jは画素Bと画素p_0の間の水平・垂直方向の距離である。

この面積を用いてBの画素値は次式により計算される。

(1)    \begin{equation*} V(B)=c_0 V(p_0) +c_1 V(p_1) +c_2 V(p_2) +c_3 V(p_3) \end{equation*}

ここでV(x)xにおける画素値を表す。グレー画像ならスカラー量、カラー画像なら3次元のベクトル量となる。また、次式が成り立つことに注意する。

(2)    \begin{equation*} \sum_{i=0}^{3} c_i=1 \end{equation*}

ポインタを用いた実装

あとで比較を行うため、上記のアルゴリズムをHalideを用いず生のポインタを用いて素直に実装する(halide/resize/resize/normal.cpp)。何も特別なことはしていない。

Halideを用いた実装

次に、Halideを用いたコードを示す(halide/resize/resize/halide.cpp)。

特筆すべき点は、アルゴリズムとスケジューリングの記述が完全に分離していることである。そのおかげでアルゴリズムの理解が大変楽になっていることが分かる。Halideのコンパイラが動的に起動する場所は、74行目のdst_image.realizeである。本サンプルではこれを10回繰り返すが、Halideコンパイラが起動するのは最初の1回目だけである。
最初に示したポインタによる実装は手続き型であるが、Halideを用いた実装は宣言型と呼ぶことができる。ロジックを決定したあと実行するスタイルは、「Define and Run」型のアーキテクチャを採用している深層学習ライブラリ(例えばTensorflow, Theano, Caffeなど)と同じである。

スケジューリング

上記コードに記載したスケジューリング

は以下を実現する(下図参照)。

  1. 画像を64\times4のタイルに分割する(処理の局所化)。
  2. 水平方向の計算は16画素単位のベクトル化により行う。
  3. 垂直方向の計算は並列化する。


上に示したスケジューリングが最良のものとは限らない。スケジューリングは試行錯誤を伴う作業になる。

速度比較

実行環境

  • MacBook Pro (15-inch, Late 2016)
  • OS: macOS Sierra
  • CPU: 2.9GHz Intel Core i7
  • Core数: 4
  • Memory: 16GB
  • Xcode Version 9.2 (9C40b)
  • C++ Language Dialect: C++17[-std=c++17]

結果

下記コマンドで入力画像を拡大する。exeは実行ファイル名、それに渡す最初の引数は入力画像、次の引数は出力先、最後の2つの引数は拡大後の画像サイズである。(src_width,src_height)が元画像のサイズ、(dst_width,dst_height)が拡大後のサイズである。最初の10個が生のポインタの結果、後の10個がHalideの結果である。

[kumada]resize(543)$> ./exe ../images/inputs/src_image_2.jpg ../images/outputs/dst_image.png 4999 3499
(src_width, src_height) = (500, 350)
(dst_width, dst_height) = (4999, 3499)

raw access[0]: 279 msec
raw access[1]: 237 msec
raw access[2]: 230 msec
raw access[3]: 236 msec
raw access[4]: 244 msec
raw access[5]: 255 msec
raw access[6]: 239 msec
raw access[7]: 248 msec
raw access[8]: 258 msec
raw access[9]: 242 msec

halide access[0]: 505 msec
halide access[1]: 28 msec
halide access[2]: 37 msec
halide access[3]: 33 msec
halide access[4]: 40 msec
halide access[5]: 34 msec
halide access[6]: 44 msec
halide access[7]: 32 msec
halide access[8]: 40 msec
halide access[9]: 39 msec

初回を除けば高速化されていることが分かる。初回の遅さはHalideコンパイラの起動に起因する。これが受け入れられないタスクもあるだろう。これを回避するのが次に示す、処理のライブラリ化である。

処理のライブラリ化

以下のコードにより、Halideコードをコンパイルした後のバイナリを静的ライブラリとして保存することができる(halide/make_halide_static_library_for_resize/make_halide_static_library_for_resize/halide.cpp)。

中身は先に示したコードとほぼ同じである。ただし以下の箇所が異なる。

  1. 7行目: 入力画像を引数にするためのコードである。
  2. 16行目から19行目: 入力画像のサイズ、出力画像のサイズを引数にするためのコードである。
  3. 64行目: ライブラリとヘッダファイルの出力先
  4. 69行目: 関数の引数は5つ。
  5. 72行目: 関数名はresize。

出力された静的ライブラリとヘッダファイルを用いた実行コードは以下のようになる(halide/resize_using_halide_static_library/resize_using_halide_static_library/main.cpp)。

  1. 4行目: 入力画像を読み込む。
  2. 10行目: 出力画像のバッファを用意する。
  3. 19行目: ライブラリの提供するresize関数を呼び出す。引数は5つである。

実行結果は以下の通り。

[kumada]resize_using_halide_static_library(555)$> ./exe ../images/inputs/src_image_2.jpg ../images/outputs/dst_image.png 4999 3499
500, 350
4999, 3499
halide access[0]: 55 msec
halide access[1]: 33 msec
halide access[2]: 37 msec
halide access[3]: 30 msec
halide access[4]: 37 msec
halide access[5]: 30 msec
halide access[6]: 38 msec
halide access[7]: 31 msec
halide access[8]: 38 msec
halide access[9]: 32 msec

改善されていることが分かる。この場合の初回の遅さは、キャッシュメモリにオブジェクトが載っているか否かの差であろう。

まとめ

今回は、画像処理に特化したDSLであるHalideを紹介した。アルゴリズムとスケジューリングの記述を切り離した宣言型の言語であることをコード例により示した。スケジューリングは試行錯誤を伴う作業であり、ある程度の慣れが必要である。しかし、SIMD命令を直接呼び出す煩雑さに比べればかなり楽な試行錯誤である。
Halideを使う際に注意しなければならないことは、動的にHalideコンパイルを行うことは、かなり大きなオーバヘッドを伴うということである。静的ライブラリを作ることでこれを回避できることを示した。
Halideは現在も活発に開発が続けられているプロジェクトである。FPGAやスマートフォンなどへも積極的に組み込まれているようだ。これからも注視していきたい。

ソースコード

今回のソースコードはここにある。

参考文献

Kumada Seiya

Kumada Seiya

仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP