読者です 読者をやめる 読者になる 読者になる

プログラミングの実験場

Haskell/Webアプリ/画像処理/可視化/ITによる生産性向上 など

関数型言語による画像処理環境の追求 その2 Haskellで画像データを扱うためのアプローチ

Haskellで画像データを扱う際に、いろいろな手法がありうる。

Pure Haskell

Hackageを見てみると、(denseな)行列を扱うpure Haskellの(=外部ライブラリに依存しない)ライブラリで有名なのは、これだろうか。並列化が自動でできるというのが売りのようだ。Simon Peyton JonesもYouTubeに載っている講演で紹介していたと思う。

shelarcyさんによる解説 http://itpro.nikkeibp.co.jp/article/COLUMN/20120605/400424/

ただ、速度は遅く、ちょっと実用には辛いレベルかと思われる。 http://repa.ouroborus.net/wiki/Examples/Fft2dHighpass

やはり、Pure Haskellで大きな数値データを高速に扱うのは未だ難しい(というか、あまり真剣に検討されていない?)という印象だ。

FFIで呼び出し

別にpure Haskellに拘る必要はなく、Cで書かれた外部ライブラリを呼び出すバインディングでも良い。と思って今一度Hackageを探してみたのだが、まともなのは殆ど見つからなかった。OpenCVへのバインディングが2つあるが、以下のものはわりと型もちゃんとついて良い感じに見える。

http://new-hackage.haskell.org/package/CV

それと、画像に特化せず行列のライブラリであれば、以下のようなものがある(GSL, LAPACK, BLASのバインディング)。

http://new-hackage.haskell.org/package/hmatrix 

ただこれらも、ベストではないように思える。というのも、immutableなデータが多く生成されてしまう可能性がある。例えばフィルターを掛けるたびに一時データの画像が生成・コピーされ、メモリとCPUの効率が悪い。FFIを繰り返し呼び出すとそれがパフォーマンス上のネックになる可能性もある。ちなみに、この問題を解決するためには、中間データの生成を無くす方法である、GHCの書換え規則や融合変換などが使えそう。融合変換ってリストだけでなく任意のデータ構造に使えるのだろうか。

(融合変換についての解説:http://itpro.nikkeibp.co.jp/article/COLUMN/20100706/349960/ http://big.freett.com/shelarcy/rewriterules.pdf

HaskellからCのコードを生成

Haskellのプログラムにembedded DSL (EDSL)を埋め込み、EDSLとして記述された画像処理のアルゴリズムからC(あるいはCUDAなど)のソースを出力する方法。2種類が考えられる。

  1. Haskellプログラムの実行時にCソース出力し、それをCコンパイラでコンパイルする。
  2. Template Haskellを使ってコンパイル時にCソースを出力し、それをHaskellからリンクする。

Haskell側でのアルゴリズムの最適化なども可能で、実現できるならこれが一番優れているように思える。ただし、Hackageを見た+軽くウェブ検索した限り、このようなアプローチの実装は殆ど無いようだ。

数少ない例としては、Nikolaという、Haskell内の embedded DSLからCUDAのコードを生成するライブラリがある。上でいう2の方法に当たる。論文が出たのが2010年と結構最近のものなので、たぶんこのような例は多くないことが推測される。

http://www.eecs.harvard.edu/~mainland/projects/nikola/

http://www.eecs.harvard.edu/~mainland/publications/mainland10nikola.pdf 論文

また、画像処理ではないが、Paraisoというライブラリは、Haskellでアルゴリズムを書くと、微分方程式を解くCUDAあるいはC+OpenMPのコードを生成する。これは上でいう1の方法にあたる。Hackage初出が2011年。

http://new-hackage.haskell.org/package/Paraiso

 

まとめ+今度の展望

HaskellのライブラリのすべてがHackageに載っているわけではないので、どこか見落としている可能性はあるが、現状で普通のユーザーに使える本格的なHaskellの画像処理ライブラリはほとんどない、というのが現時点での調査の結論。

これから何らかの画像処理ライブラリを自分で作るとしたら、Haskell内のEDSLからCコードを生成するアプローチが一番有望(大変そうではあるが)のように思えるので、このアプローチについてこれからヒマを見て調べてみようと思う。

Haskellで型付きのDSL(型付きじゃないとHaskellに拘る意味が無くなってしまうので)を作る方法については、以下の資料が参考になりそう。

http://d.hatena.ne.jp/keigoi/20111206/haskell_tagless_dsl

http://okmij.org/ftp/tagless-final/index.html