Clojureで、いくつかのコンピュータビジョン・画像処理のアルゴリズムを実装してみました。
画像をClojureのシーケンスとして表現することで、画像処理のアルゴリズムの本質的な部分の記述に注力できて、面白いのではないかと思ったのが事始まりです。ですので、すべてをPure Clojureで実装しています。
(基本的に画像処理は長さの2乗で計算量が増えていくので、普通は速度重視でC/C++で実装すると思います。)
この記事には、OpenCVなどの画像処理・コンピュータビジョンのライブラリをClojureから利用する等の話は出てきません。 ご注意下さい。
TL;DR
- Pure Clojureでいくつかの画像処理のアルゴリズムを実装してみました
- Pure ClojureなのでClojureScriptでも簡単に動かせます (https://federkasten.github.io/vijion/)
- cljxでClojure/ClojureScriptでのコードの共有も出来ます
- ただしC/C++で実装したものよりも、かなり遅いです
vijion
画像をClojureのシーケンスとして表現し、Pure Clojureで画像処理を行うvijionというプジェクトを作成しました。
GitHub上にコードをホストしています。
https://github.com/federkasten/vijion
適宜参照ください。
画像のI/O
画像のI/Oについては、本線から外れるので、手短に。
JVMの方はjavax.imageio.ImageIOを使いました。
https://github.com/federkasten/vijion/blob/master/src/clj/vijion/core.clj
JavaScriptの方は、HTML5 Canvasを使って画像のI/Oを行いました。
https://github.com/federkasten/vijion/blob/master/src/cljs/vijion/core.cljs
下記のようなハッシュマップで画像を表現することにしました。
{:width 1024
:heigt 768
:color :rgb
:data [[123 87 45] [198 92 200] .....]}
:dataのところが画像データの生データで、遅延シーケンスで読み込みます。
シーケンスにはRGBの順に、各ピクセルの値が入っています。
グレースケール
画像処理の第一歩として、まず画像をグレースケール(白黒)に変換します。
https://github.com/federkasten/vijion/blob/master/src/cljx/vijion/gray.cljx
グレースケールのやり方は、RGBの平均値や最大値など色々なやり方があります。今回は最大値をとる方法で実装します。
(defn rgb->gray
[image]
(assoc image
:color :gray
:data (mapv (fn [[r g b]] (max r g b)) (:data image))))
説明の必要もなくシンプルです。
ポイントとしては、画像のシーケンスはmapvを使ってベクタとして持っています。
様々な画像処理のアルゴリズムを考えると、nthなどを使ったシーケンスへのランダムアクセスが必ず必要になってきます。シーケンスへのランダムアクセスを、Clojureで高速に行うためにベクタとしてデータを保持します。
Lennaさんの画像をグレースケールに変換すると、下のようになります。
線型フィルタ
次に、線型フィルタの処理を実装しました。
https://github.com/federkasten/vijion/blob/master/src/cljx/vijion/filter.cljx
説明するまでもないですが、線型フィルタとは、入力画像の全ピクセルに対して、奇数のサイズの行列(カーネルとも呼ぶ)を下図のように対象ピクセルとその近傍ピクセルに対して適用し、新しい画像を計算するものです。この計算のことを畳み込み(convolve)と呼びます。
Laplacianフィルタ(2次微分フィルタ)のClojureで素直に書くと、下のような実装になります。
(defn simple-laplacian
[gray-image]
(let [mat [1 1 1
1 -8 1
1 1 1]
width (:width gray-image)
data (doall (:data gray-image))
len (count data)]
(assoc gray-image :data
(loop [idx 0
res []]
(if (< idx len)
(recur (inc idx)
(conj res (let [p00 (pick data len width idx -1 -1)
p01 (pick data len width idx 0 -1)
p02 (pick data len width idx 1 -1)
p10 (pick data len width idx -1 0)
p11 (pick data len width idx 0 0)
p12 (pick data len width idx 1 0)
p20 (pick data len width idx -1 1)
p21 (pick data len width idx 0 1)
p22 (pick data len width idx 1 1)]
(if (some nil? [p00 p01 p02 p10 p11 p12 p20 p21 p22])
0
(-> (int (+ (* (nth mat 0) p00)
(* (nth mat 1) p01)
(* (nth mat 2) p02)
(* (nth mat 3) p10)
(* (nth mat 4) p11)
(* (nth mat 5) p12)
(* (nth mat 6) p20)
(* (nth mat 7) p21)
(* (nth mat 8) p22)))
abs
(min 255))))))
res)))))
線型フィルタを実装する際は、画像の境界部分の処理が問題で、面倒くさいのですが、このコードでは(if (some nil? [p00 ... p22]) ...)として例外として扱っています。つまり対象の近傍ピクセルのなかでnilが含まれていたら0と評価するようにしています。この辺りの処理は、もう少しスマートに書きたいところです。
(pick data length width index offset-x offfset-y)は、入力の画像シーケンスの指定されたインデクスからオフセット分だけずらしたピクセルの値を返す関数です。
このLaplacianフィルタの実装を一般化して、少し最適化すると下のようになります。
(defn gray-convolve
[image-filter gray-image]
(when (odd? (:size image-filter))
(let [w (:width gray-image)
d (doall (:data gray-image))
s (:size image-filter)
mat (:matrix image-filter)
hs (quot s 2)
ws (* s s)
indices (range (- hs) (inc hs))
offsets (doall (vec (for [oy indices
ox indices]
[(long ox) (long oy)])))
len (count d)
px (pick-fn d len w)]
(assoc gray-image :data
(loop [idx 0
res []]
(if (< idx len)
(recur (inc idx)
(conj res (let [wp (map (fn [[ox oy]] (px idx ox oy)) offsets)]
(if (some nil? wp)
0
(-> (long (reduce + (map * wp mat)))
abs
(min 255))))))
res))))))
畳み込みの計算が(reduce + (map * ピクセルのシーケンス フィルタの行列のシーケンス))と書けて、すごくシンプルです。またフィルタの行列のサイズに依存しないコードで、分かりやすいですね！
また、スレッディングマクロを使うと、複数のフィルタの適用が、下の様にすごく直感的に書けます。
(-> img
vijion.gray/rgb->gray
vijion.filter/gradient
vijion.filter/laplacian
vijion.gray/gray->rgb)
平滑化フィルタを適用しノイズリダクションをした後、Laplacianフィルタを適用すると下のようになります。
Image Segmentation
線型フィルタだけでは味気ないので、Image Segmentationの実装を行いました。
https://github.com/federkasten/vijion/blob/master/src/cljx/vijion/segment.cljx
Image Segmentationは画像を、領域に分割する方法です。
下のように色が似た部分で領域ごとに分割される画像を計算します。
画像の認識のベースとなるもので、この後に、領域ごとに特徴ベクトルを作成して、機械学習させ、画像から対象を認識させて・・・など、様々な応用ができます。
Image Segmentationには色々なアルゴリズムが提案されていますが、今回はグラフカットの使ったEfficient Graph Based Image Segmentationのアルゴリズムを実装しました。
アルゴリズム全体についてコードとその説明を書くと長くなってしまうので、ポイントだけ紹介します。実装とアルゴリズムの詳細については、コードと元論文を参照してください。
画像のシーケンスから無向グラフを計算する部分については下のように書けます。無向グラフも画像のデータ同様、エッジのシーケンスとして表現することにしました。
(defn make-edges
[image]
(let [width (:width image)
data (:data image)
len (count data)]
(loop [idx 0
res []]
(if (< idx len)
(recur (inc idx)
(conj res
(edge data len width idx 1 0)
(edge data len width idx 0 1)
(edge data len width idx 1 1)
(edge data len width idx 1 -1)))
res))))
各エッジは
{:a 123 ;ノードA
:b 128 ;ノードB
:w 0.123} ;エッジのweight
の様にハッシュマップで表現しています。
このエッジのシーケンスをweightでソートして、Disjoint-Set Forestを使って、グラフカットを行います。Disjoint-Set ForstのClojureでの実装については、Jordan Lewisさんのdata.union-findを参考にしました。
https://github.com/federkasten/vijion/blob/master/src/cljx/vijion/util/disjoint.cljx
グラフもシーケンスと扱うことで、とてもシンプルに実装できたと思います。
ClojureScriptで動かす
Pure Clojureなので、cljxを使って、Clojure/ClojureScriptでコードを共通化しました。
グレースケール変換、線形フィルタ、Image Segmentationについて、ほとんど変更を加える必要なく動きました。
下のURLのGitHub Pagesでホストしているので試してみてください。(ClojureScriptでのImage Segmentationの計算はすごく時間がかかるので、下のページでは無効にしています。)
https://federkasten.github.io/vijion/
注意すべき点としては、pmapなどを使った並列処理の部分がJavaScriptエンジンでは動かないので気を付けないといけない、という点ぐらいでしょうか。
本当に、ほとんど手を加えること無く共通化できてしまったので、これについては書くことがありません・・・。
パフォーマンス考察
Pure Clojureによるコンピュータビジョン・画像処理のパフォーマンスについてです。
一言で言うと、かなり遅いです。私の実装が悪いのかもしれません。早くする方法があればご教授願いたいです。(Type Hintsやuncheck-については、既に確認しました。)
実行環境に依存するので一概には言えないのですが、C/C++の実装では線形フィルタの処理が数ミリ秒で終わりますが、同じことをこのClojureのコードで実行すると数秒から数十秒かかります・・・。
また、JVM/JavaScriptのどちらの環境でも、素のJavaやJavaScriptの配列を使った実装に比べると、かなり遅いです。この辺りはClojureのシーケンスに変換したことによる、不要な関数コールやリフレクションが行われているせいだと推測出来ますが、詳細はまだ調べきれていません。
現在のコードでは、パフォーマンス上は実用的ではないので注意してください。
おわりに
Pure Clojureで、グレースケール変換、線形フィルタ、Image Segmentationを実装してみました。
画像をClojureのシーケンスとして表現することで、画像処理のアルゴリズムの部分に注力して、非常にシンプルに書くことが出来ました。C/C++で実装するときのように余計なことに頭を使わず、アルゴリズムに集中して実装することが出来ました。改めてClojureの表現力の高さを感じました。
実装はシンプルに出来て満足なのですが、パフォーマンスが著しく悪かったです。このままだとめちゃくちゃ悔しいので、C/C++あるいはPure Java並みの速度は出せるように、今後改善していきたいと思います。
告知
告知です。
弊社、株式会社テンクーでは、共にプロダクト開発を行うメンバーの募集をしています。
Clojureをメインのプログラミング言語としてシステム開発を行っています。
詳しくは、弊社の採用情報のページを見ていただければ幸いです。
弊社で運営しているサービスでClojureを使っているものには、
- Chrovis : ゲノム解析クラウドサービス
- Hacker News Hack : Y CombinatorのHacker Newsのコメント数によるリランキングとアーカイブを提供するサービス
- news.async : インターネットニュースをTVのように視聴するサービス (ClojureCup 2014で開発)
- AstroCats : 複数人で対戦できるゲーム (ClojureCup 2014で開発/ニコニコ自作ゲームフェス敢闘賞)
など色々あります。
何卒よろしくお願い致します。