Rest Term

Blog

JavaScriptでLSDによる高精度な直線検出

ここ半年くらいは機械学習関連技術のJavaScript実装を行ってきましたが、今回は久しぶりに画像処理関連の要素技術を調べました。

Line Segment Detector (LSD) と呼ばれるアルゴリズムになります。

画像: 東京ガーデンテラス紀尾井町 - Tokyo Garden Terrace Kioicho

LSDによりデジタル画像中から高精度に直線(line segmentなので厳密には線分)を検出することができます。直線検出と言えば、Hough(ハフ)変換と呼ばれる古典的なアルゴリズムが著名かと思いますが、LSDはHough変換よりも検出精度が高い手法となっています。LSDの論文が出たのが2012年のようなので思ってたより新しいですね。直線検出のようなシンプルかつ重要な要素技術もまだ枯れてなくて、地道に発展しているのはなんだか嬉しい感じです。

まとめ

時間がない人のため。

Line Segment Detector (LSD)アルゴリズムをJavaScriptで実装し、評価用の簡単なデモを作りました。

* ソースコード: JavaScript (ES2015) + React + Material-UI

* デモ (Chrome, Firefoxで動作確認)

LSD Demo

LSD Demo

LSD (Line Segment Detector) 概要

LSDのアルゴリズムは以下のようになっています(元論文より画像引用)。

LSDでは以下のFigure 1ような画像中の場所をLevel Line、小さな領域内(2x2画素)での輝度勾配とLevel Lineの角度(LLA: Level Line Angles)を画像全体で計算したものをLevel Line Fieldと定義しています(Figure 2)。そして生成したLevel Line Field内から直線領域候補(Line Support Regions)を計算します。

Algorithm 1 L6: RegionGraw のアルゴリズム詳細は以下の通り、LLAの情報を元に直線の領域をちょっとずつ(8近傍画素を都度見ながら)増やしていく反復処理になっています。

直線領域候補を計算できたら、L7: Rectangle でその領域を矩形に近似することで直線を検出します(Figure 3)。L8: AlignedPixelDensity 以降の処理は L7: Rectangle で求めた矩形の形を整えたり、不要な領域を削除して精度を向上させる処理となっています。

実は、 L12: ImproveRectangle 以降の処理を省略しても精度はそれほど悪くなりません。実際、後述するOpenCVのLSD実装ではデフォルトパラメータでは L12: ImproveRectangle 以降の処理は実行されません。それ以上に L1: ScaleImage 内で前処理として行われるガウシアンフィルタの有無の方が精度に大きな影響を与えるようです。サブピクセル精度を求めたいケースでは全ての処理を行うといった使い方が良いかもしれません。

実装

今回はTypeScriptではなくJavaScript(ES2015)で実装してみました。

その前に既存の実装についていくつか紹介します。一つ目はオリジナルのC言語ソースコード、論文PDFといっしょに公開されています。注意点としては、ソースコードのライセンスがAGPLv3になっていることです。もし業務等で利用する際には十分注意してください。

二つ目はOpenCVのC++実装です。ハードウェアレベルでもいくらか最適化されているため、不都合がなければOpenCV版(C++/Python)の利用をオススメします。今回はこのOpenCV版を参考にJavaScript実装を行いました。

三つ目はnpmのパッケージです。emscriptenでオリジナルのC言語のソースコードをJavaScriptに変換して作成されています。なので処理の実体はオリジナルと同じですね。

emscriptenは便利で僕も好きですけど、バインディングを作っても理論の勉強ができないので今回も素朴にJavaScriptで一から書いています。ソースコード群はいつものようにGitHubにUPしています。

* デモ (Chrome, Firefoxで動作確認)

JavaScriptでの使い方は以下のようにしました。

LSD内部ではたくさんのパラメータがあってあまり吟味できてないんですけど、とりあえず論文に載ってる値やOpenCV実装内部の値をそのまま設定しています。

また、今回作成したデモはReactを使っているので、LSD動作確認用のReactコンポーネントも作ってみました。完全にデモ用なので汎用性は無いですけど。

* Reactコンポーネント使用例

コンポーネントのsrc属性に画像を指定するだけで利用できます。Material-UIを併用しているので、material-uiモジュールが必須になっているのはかっこ悪い気がします。より良いReactコンポーネントの設計方法を学びたいです。

精度評価

古典的手法であるHough変換はJavaScriptで実装していないのでまずはOpenCV実装を使って比較します。左がHough変換、右がLSDによる検出結果です。注意点としては直線ではなく線分検出処理を比較したいので、標準的Hough変換ではなく確率的Hough変換を使っています。

* 左: Hough変換(cv::HoughLinesP) 右: LSD(cv::LineSegmentDetector)

今回実装したJavaScript版のLSDの検出結果は以下の通りです。OpenCV版とほぼ同じ出力結果になりましたが細部の結果は異なっています。実はOpenCV内部ではatan2などの数学関数を高速化の為に近似処理(cv::fastAtan2など)をしているのですが、僕のJS実装ではMathモジュールの数学関数をそのまま利用しています。さらに、JavaScriptだとC/C++と異なり、単一の整数値(charやint型)を直接扱えないのでその影響が積もって多少精度に差がでているようです。

* 今回実装したJavaScript版の検出結果

検出難易度が高そうな画像で比較すると差は歴然です。確率的Hough変換が苦手とするタイプの画像でもLSDなら大きな精度低下はなく安定しています。

* 左: Hough変換(cv::HoughLinesP) 右: LSD(cv::LineSegmentDetector)

JavaScript版の検出結果は以下の通り、細かい線分がたくさんある画像だとOpenCV版との検出精度の差が大きくなるようです。近似処理をしていない分、JS版の方が精度が高いような気もしますけど、まぁ気のせいです。

* 今回実装したJavaScript版の検出結果

いずれにせよ確率的Hough変換と比べてLSDの方が精度が高いことが確認できました。LSDの方が複雑な処理をしているので精度が高いのは当然だよなぁという印象です。パラメータを吟味すればさらに精度は上がるのかもしれませんけど、元論文には「It is designed to work on any digital image without parameter tuning.」とあるので論文内のパラメータをそのまま使うのが適切なんでしょう。確率的Hough変換は投票値の閾値や同一の直線とみなす画素間隔などのパラメータ調整が面倒ですから、精度だけでなく使い勝手の点においてもLSDが勝っていると言えそうですね。

処理速度の点においては確率的Hough変換の方に分がありそうですが、これは実装の質にかなり依存するようです。OpenCV実装では確率的Hough変換よりLSDの方が高速でしたが、オリジナルのC実装はかなり遅かったです。

おわりに

LSDはたぶん僕が今までJavaScriptで実装したアルゴリズムの中でも一番実装が大変だった気がします。ここ数回は機械学習アルゴリズムを実装・公開してきましたけど、それと比べたら遙かに面倒でした。ただ、機械学習と違って学習データを集めたりする雑務が不要だったのは救いです。古い手法と比較したい場合は、新しい手法から先に実装してしまうと古い手法を実装するモチベーションが湧かなくなってしまうので今後は注意して取り組みたいです。LSDを先に実装してしまったらHough変換はもう作らなくていいかってなってしまったので。ちなみに、特徴量ベースのアプローチとして Line Band Descriptor (LBD) という手法も提案されています。時間を作ってまた調べておこうと思います。

 

Tags: , ,

PCパーツ新調メモ 2017/01

このお正月にOSとSSDを新調しました。前回のエントリーからの差分をメモ(記載価格は購入当時の価格)。

OS Windows10 Pro \13,824
SSD PLEXTOR M8Pe PX-512M8PeG-08 512GB SSD \31,900
VIDEO GeForce® GTX 1070 GAMING X 8G \61,775

PCパーツは値動きが激しいので欲しいと思った時が買い時。1万円未満の価格差なら誤差と考えると気楽に買い物できるのでオススメです。

ねんがんのNVMe SSDをてにいれたぞ。

USBフラッシュメモリと並べてみるとコンパクトさがよくわかります。

容量単価は高いですが性能も高いです。ただし、M.2接続のSSDを使う際には発熱によるサーマルスロットリングを避けるためにも温度管理には気を遣いたいところ。室温20℃の環境においてCrystalDiskInfoで計測すると人の体温と同程度の温度。SATA接続のHDDよりも8 ~ 10℃前後高かったです。ヒートシンク付きモデルなのでこの程度で済んでいるのかどうか、夏場は一層注意したいです。

あとはNASとしてQNAP TS-251+も去年秋頃に購入し、ユーザーデータは全てNAS上に置くようにしました。もちろん外部からもアクセスできるようにVPN環境も整えています。クラウドストレージのAmazon DriveとMicrosoft OneDriveも併用していますが、速度面を考慮するとNASの方がストレスが少ないです。

これまではメインのWindowsマシンをゲーミングPC兼開発機として運用するべくいろいろ調整してきましたが、Windows7以前の環境ではなかなか上手くいきませんでした。Windows10 ProではHyper-Vが利用できるので、Docker for Windowsを導入することでLinuxの開発環境を整えやすいです。Windows7以前のようにVirtualBox等を併用しなくて済むので構築のハードルが低くなっています。Bash on Ubuntu on Windowsはまだ安定したプロダクトではないようなので、こちらはもうすこし様子見をしようと思います。

 

Tags: ,

JavaScriptで機械学習の実装 4 SCW

前回 JavaScriptで機械学習の実装 3 AROW に引き続きオンライン学習アルゴリズムを試しています。Node.js勉強中なのでJavaScriptを使ってこつこつ学んでいきましょう。

今回は SCW (Soft Confidence Weighted Learning) と呼ばれるアルゴリズムを扱います。

SCW (Soft Confidence Weighted Learning)

2012年に提案された、CW (Confidence Weighted Learning)と前回紹介したAROW (Adaptive Regularization of Weight Vectors)の特徴を備え持つ手法です。SCWはCWと同様に重みベクトルの各重みが正規分布に従って生成されていると考えます。

SCWのアルゴリズムは以下のようになっています(元論文から引用)。
scw_algorithm

μが信頼している重み、Σが各重みの信頼度・自信(confidence)を表しており、ハイパーパラメータCでどの程度の誤りを許容するか(損失関数を常に0にするという制約を緩める)を調整しています。
scw_update_kld

損失関数は以下のように定義されており、信頼度が低いパラメータは重視されないようになっています。
scw_loss_function

また、αとβはどちらもCWと同様に閉じた形で更新式が表されます。αの計算式は二通りあり、それぞれSCW-IとSCW-IIと呼ばれています。具体的な式については論文などを参照。

SCWの特性として論文の最後で以下の4つが挙げられています。

  1. large margin training
  2. confidence weighting
  3. adaptive margin
  4. capability of handling non-separable data

性能面ではCWやAROWと比べて多くのケースにおいて高精度で効率が良い(収束が速い)とされているようです。

検証

今回はLIBSVM Data: Classificationの a9a データセットで分類精度や収束速度などを確認してみます。a9a は世帯収入が一定以上かどうかの二値、線形分離不可能なデータになっています。

SCW実装の本体やデータ読み込み用モジュール、動作確認用のテストコード一式はこれまで通りGitHubに置いておきます。今回もAROWと同様にTypeScriptとJavaScriptの両方のコードを上げてあります。

疎ベクトル用に最適化してないナイーブな実装なので、1,355,191次元もある news20.binary データセットを用いたAROWとの比較は難しいです。ということで a9a を使って動作確認をします。

データファイルの読み込み部分は前回作ったLIBSVMフォーマットファイルをStream APIで読み込むモジュールを使い回しました。Node.js環境において以下のような感じで学習とテストを実行できます。

SCWの2つのハイパーパラメータは適当に設定し、データは1巡のみで84.6%の分類精度となりました。AROWの時もそうでしたが、やはりオンライン学習は収束が速くて助かります。

オンライン学習の性質を確認するため、学習データを1件ずつ与えて学習する毎に精度確認を行いました。データを与える順番を変えるためにデータをシャッフルして合計3回試行しています。
result_a9a_scw
a9aなら5,000サンプルくらい与えてやれば十分なようです。

線形SVMのscikit-learn実装(sklearn.svm.LinearSVC)でも試してみました。グリッドサーチして学習した結果、こちらも84%の分類精度となりました。a9a データセットにおいては線形SVMと精度面での違いはそこまでないようです。

SCWはAROWよりもパラメータが一つ多いので調整がめんどくさそうに思えますが、適当に設定しても高い精度が出るのでそんなに悩まなくても大丈夫です。とりあえず動作確認はできたと思うので今回はこの辺で。次はそろそろ分散学習アルゴリズム周りを学んでいきたいです。

参考

 

Tags: , , ,

GTC Japan 2016 参加レポート

GTC Japan 2016が10月5日にヒルトン東京お台場で開催されました。今回で参加は2回目ですが、前回(2014年)より参加者はとても増えていたように思います。ゆりかもめでは小さすぎる。

dsc07402

dsc07447

基調講演

NVIDIA ジェンスン・ファン(Jen-Hsun Huang)CEOの基調講演に関するレポートは大手ネットメディアがたくさん書いてるのでそちらを見た方が詳細が分かると思いますが、ここでもメモ書き程度におさらい。

続きを読む »

 

Tags: ,