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

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

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

LSD: a Line Segment Detector (元論文PDF)

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

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

まとめ

時間がない人のため。

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

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

imageprocessing-labs/cv/lsd/ – GitHub

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

Line Segment Detector Demo

LSD (Line Segment Detector) 概要

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

LSDでは以下のFigure 1ような画像中の場所をLevel Line、小さな領域内(2×2画素)での輝度勾配と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になっていることです。もし業務等で利用する際には十分注意してください。

LSD: a Line Segment Detector

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

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

line-segment-detector – npmjs.com

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

imageprocessing-labs/cv/lsd/ – GitHub

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

Line Segment Detector Demo

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

import LSD from './lsd';
import SampleImage from './sample.jpg';

const image = new Image();
image.src = SampleImage;
image.onload = () => {
    const width = image.width;
    const height = image.height;
    const canvas = document.createElement('canvas');
    const context = canvas.getContext('2d');
    canvas.width = width;
    canvas.height = height;
    context.drawImage(image, 0, 0, width, height);
    document.getElementById('content').appendChild(canvas);
    const imageData = context.getImageData(0, 0, width, height);
    const detector = new LSD();
    const lines = detector.detect(imageData);
    console.log('lines: ' + lines.length.toString());
    detector.drawSegments(context, lines);
};

import LSD from './lsd';

import SampleImage from './sample.jpg';

const image = new Image();

image.src = SampleImage;

image.onload = () => {

const width = image.width;

const height = image.height;

const canvas = document.createElement('canvas');

const context = canvas.getContext('2d');

canvas.width = width;

canvas.height = height;

context.drawImage(image, 0, 0, width, height);

document.getElementById('content').appendChild(canvas);

const imageData = context.getImageData(0, 0, width, height);

const detector = new LSD();

const lines = detector.detect(imageData);

console.log('lines: ' + lines.length.toString());

detector.drawSegments(context, lines);

};

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

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

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

import React from 'react';
import ReactDOM from 'react-dom';
import MuiThemeProvider from 'material-ui/styles/MuiThemeProvider';
import LSDComponent from './lsd_component';
import SampleImage from './sample.jpg';

ReactDOM.render(
    <MuiThemeProvider>
        <LSDComponent src={SampleImage} />
    </MuiThemeProvider>,
    document.getElementById('content')
);

import React from 'react';

import ReactDOM from 'react-dom';

import MuiThemeProvider from 'material-ui/styles/MuiThemeProvider';

import LSDComponent from './lsd_component';

import SampleImage from './sample.jpg';

ReactDOM.render(

</MuiThemeProvider>,

document.getElementById('content')

);

コンポーネントの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) という手法も提案されています。時間を作ってまた調べておこうと思います。

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

まとめ

LSD (Line Segment Detector) 概要

実装

精度評価

おわりに

あわせて読む:

コメントを残す