高速な楕円検出アルゴリズムを実装してみた

[1]の論文に書かれている楕円検出アルゴリズムをpythonで実装してみました. 論文ではSamsung Galaxy S2を使っていて, C++実装でJNI経由で呼び出すと, 800×440の画像サイズで10FPSほどの性能が出るそうです. 現行のスマホではもっと性能がでると思います.

python実装なので論文ほどの性能は出ないです. 過度な期待はしないでください.
https://github.com/horiken4/ellipse-detection

以下, 大まかなアルゴリズムを説明したいと思います.

1. 円弧を4つのクラスに分ける
グレースケール画像の入力画像にガウシアンフィルタをかけ, Cannyオペレータによりエッジ検出をします. また, Sobelオペレータにより各画素のx, y方向微分値dX, dYを求めます.

ellipse-preprocess

Cannyオペレータによって検出されたエッジ画素に関して, dY/dX>0なら上図(a)の{2, 4}, dY/dX<0なら上図(a)の{1, 3}の円弧のものだろうと推測できるので, すべての画素をクラス{2, 4}, {1, 3}にクラス分けします.

クラス分けしたあとは8近傍のラベリングを行い, 円弧らしいセグメントを検出します. ここで検出されたセグメントのうち長さが短すぎるものや, 直線に近いものは楕円を構成する円弧ではないと判断し捨てます.

検出されたそれぞれのセグメントについてバウンディングボックスを考え, セグメントの下と上の面積A, Bを求めます(上図(b)). AがBより大きければ上に凸, そうでなければ下に凸であると判断します.

まとめると

  • クラス{2, 4}のセグメントで上に凸→クラス2
  • クラス{2, 4}のセグメントで下に凸→クラス4
  • クラス{1, 3}のセグメントで上に凸→クラス1
  • クラス{1, 3}のセグメントで下に凸→クラス3

となり各セグメントを4つのクラスに分けることができます.

2. セグメントの選択と楕円の検出
セグメントが4つのクラスに分けられましたが, このままではどのセグメントがひとつの楕円を構成するのかわかりません. 楕円のパラメタは3つの円弧があれば推定可能なので, 楕円を構成しそうなセグメントの3つ組(e_i, e_j, e_k)を探します.

セグメントの個数をnに対して\binom{n}{3}の組み合わせをすべて試すのは効率が良くないので, いくつかの制約から探索範囲を狭くします. まず, 上図(a)を見るとわかりやすいですが, (1, 2, 4), (2, 3, 1), (3, 4, 2), (4, 1, 3)のクラスのセグメントの組しか楕円を構成しないことがわかります, また, 例えば(1, 2, 4)の場合はクラス1のセグメントに対して, クラス2のセグメントは左に, クラス4のセグメントは下になければならない, といったような制約があります. これらの条件を満たす3つ組をすべて列挙します.

次に, 3つ組に対して, 楕円の中心を推定します. 3つ組に含まれる2つの隣り合う円弧のをつなぐ線分の中心を通る直線の交点が楕円の中心になるので(下図(a)), 2つのペア(e_i, e_j), (e_i, e_k)から求めた楕円の中心が十分近ければ, この3つ組は楕円を構成する3つ組だと判断し, 下図(b)で示してある様々なパラメタを求めます. そうでない場合, この3つ組は捨てます.

ellipse-triplet

3. 楕円のパラメタの推定
2. で求めたスロープの傾きや楕円の中心候補などから楕円のパラメタを求めます. ごちゃごちゃしているので詳しく知りたい方は論文のParameters Estimationの章を参照してください. パラメタのとりうる範囲を離散化して投票制によってパラメタを決定しています.

最終的な楕円のパラメタが推定されたあと, 検出された楕円のスコアを以下の式で求めます.
score = \frac{number\ of\ points\ lying\ on\ the\ actual\ contour}{|e_i| + |e_j| + |e_k|}
つまり, 推定された楕円にフィットするセグメントの画素数の割合を求めています.

4. 後処理
アルゴリズムの性質上, ひとつの楕円に対して4つ以上のセグメントが検出された場合, 若干パラメタの違う楕円が複数検出されることになるため, これらの楕円をマージします. 楕円の類似度を[2]に記載されている方法で求め, 同じ楕円と判断された場合はスコアの大きい楕円を採用します.

ざっくりと説明しましたが, だれかの助けになれば幸いです. スマホでカメラ自校正させたいとか, メトリック復元したいとかいったときに使えるんじゃないでしょうか。

参考文献

[1] M. Fornaciari and A. Prati, “Very Fast Ellipse Detection for Embedded Vision Applications”
[2] D. Prasad and M. Leung, “Clustering of ellipses based on their distinctiveness: An aid to ellipse detection algorithms”
[3] A. Fernandes, “A Correct Set of Equations for the Real-time Ellipse Hough Transform Algorithm”
広告
カテゴリー: Code, Computer Vision, OpenCV パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中