ハフ変換

ハフ変換（ハフへんかん、Hough変換）は、デジタル画像処理で用いられる特徴抽出法の一つである。古典的には直線の検出を行うものだったが、更に一般化されて様々な形態に対して用いられている。現在広く用いられている変換法はen:Richard Duda及びen:Peter Hartが1972年に発明した「一般化ハフ変換」である。この名は1962年にen:Paul Houghが得た関連する特許に由来する。この変換法は1981年のen:Dana H. Ballardの論文 "Generalizing the Hough transform to detect arbitrary shapes"（「 ハフ変換の一般化による任意の形態の検出」）によってコンピュータビジョンの領域で広く用いられるようになった。

理論

いかなる点をとっても、その点を通る直線は無限個存在し、それぞれが様々な方向を向くが、これがハフ変換の基本原理である。ハフ変換の目的は、それらの直線の中で、画像の「特徴点」を最も多く通るものを決定することにある。すなわち、その画像に最もよく合った直線である。

二つの点が、さまざまな直線のうち、同一のものの上に乗っていることをはっきりさせるためには、直線と直線との比較ができるような方法で直線を表現する必要がある。標準的なハフ変換では、一つの直線を二つのパラメタで表す。パラメタは通常、r 及び θ と呼ばれ、それぞれ原点から問題の直線に引いた法線の長さと角度とを表す。このように表現すると、直線の式は次のようになる:

$r=x\cdot \cos \theta +y\cdot \sin \theta$

そこで、画像上の全ての直線に、(r, θ) の組を対応させることができる。$\theta \in [0,\pi ]$ かつ $r\in \mathbf {R}$ とするか、もしくは $\theta \in [0,2\pi ]$ かつ $r\geq 0$ とすると、ある直線に対する(r, θ) の組は一意に決定する。いいかえれば、θに対して直角で、原点から r の距離にあるものとして直線を表現するわけだ。(r, θ) の組の集合がなす平面を、「ハフ空間」と呼ぶこともある。このような表現を取る点で、ハフ変換はいわゆるラドン変換( en:Radon transform) と概念的に極めて近い。即ち、ハフ変換とは、二値化された画像に対して、ラドン変換を施すことに他ならない。

平面上の一点を通る直線は無限に存在する。問題となる点の画像上での座標を$(x_{0},y_{0})$ としよう。この点を通る全ての直線は、次の式に従う:

$r(\theta )=x_{0}\cdot \cos \theta +y_{0}\cdot \sin \theta$

これは (r, θ) 平面上の一つの正弦曲線に相当し、画像上の点が決まれば一意に決まる。二つの点に対応する曲線を重ね書きした場合、ハフ空間内において二つの曲線が交わる点は、この二つの点を同時に通る直線に対応する。一般化すれば、（画像上における）直線上の点の集合は、その直線に対応するハフ空間内の一点で交わるような正弦曲線の集合を生成する。

実装

ハフ変換に用いる元データは、通常「生の」画像で、通常はそれに輪郭検出を施す。かくして、変換される点の集合は必ずしも全てが適切な画像の輪郭とは限らないことになる。変換処理は任意の数の「ビン」（区切り）に量子化され、それぞれのビンが画像の輪郭になりうる一本の直線を近似的に表す。重要な点（ないしは「特徴点」）の各々は、自分を通る直線を表現するビンの集合に「投票」する。全ての特徴点について「投票」を実行する（各ビンの値を単に加算していく）と、一つの配列ができることになり、その配列から元の画像データにもっともよくあてはまる直線が得られる。

配列の中から大きな値をとったビンを探し出すと、一群の適切な直線とその（近似的な）幾何学的定義が求まる。「ピーク」を求める最も簡単な方法は何らかの閾値を当てはめることだが、場合によっては別の方法を用いるとよりよい結果が得られることもある。この方法では直線の長さの情報が得られないので、次の段階で、どの直線のどの部分が画像にあてはまるかを見つけ出さなければならない。

例

図を見てほしい。ここではデータとして左に示すような5つの点を考える。それぞれの点に対応するハフ空間内の正弦曲線は同じ色を用いて右に示した。これらの正弦曲線を得る方法は次の通りである。緑のデータ点を例にとり、中央の図に示す。

• それぞれの点を通る一連の直線を、角度を変えながらプロットする。ここでは緑の点を例にとって、黒、赤、緑、青の実線を引いた。
• 各々の実線に対して、原点から落とした法線を引く（両端に矢印のある線）。
• 矢印の線の長さと角度を測る。
• 角度対長さのグラフ（ハフ空間グラフ）を作る。
• 全てのデータ点についてこの操作を繰り返す。

ハフ空間に描かれた正弦曲線の交点から、一つの長さと角度の組が求まる。この長さと角度はテストに用いた点を結ぶ一本の直線を示す。この例では交点はr0の指す点であり、黒の実線に対応する。この線は5点を結んでいる。

以下の別例は、二本の太線を含むラスター画像に対するハフ変換の結果を示す。

この結果は行列に格納される。各要素の値はそこを通った正弦曲線の数を表す。値が大きいほど明るく表示してある。明るい個点が二つ見え、これが二本の直線を表す二つの交点である。これらの点の座標から、画像中心から見た二本の直線の距離と角度が得られる。

変法と拡張

勾配の方向を用いた投票数の削減

画像強度の局所的な勾配の方向は輪郭に直交するはずである。この点を考慮に入れてO'Gorman と Clowes は、直線の検出における改善法を示唆した。一般的に輪郭検出は画像強度の勾配の大きさを計算する過程を含むので、勾配の方向が副次的に得られることがしばしばである。任意の座標 (x, y) がたまたま実際に直線の上に乗っていたとしよう。このとき局所的な勾配の方向から、問題の直線に対応するパラメータ θ が得られ、即座に r も得られることになる。実際には、真の勾配方向は誤差を込みにして推測するしかなく、±20°程度の精度となる。これは、正弦曲線を誤差分の±20°はトレースする必要があるということを意味する。だが（180°ではなく±20°なので）計算時間の短縮が達成されるだけではなく不必要な投票を抑制することができるので、（真の直線に相当する）配列のピークをはっきり見せる効果がある。

ハフ変換の曲線への応用、一般化ハフ変換

上記の方法は直線を検出するためにしか役立たないが、一組のパラメータで表現しうる形態については全て、類似の変換法が応用できる。例えば（平面上の）円は中心と半径を表す三つのパラメータに変換することができるので、三次元ハフ空間を用いることになる。任意の楕円もパラメータの組で容易に表現できるので同様である。さらに複雑な図形には一般化ハフ変換が用いられる。この方法は事前に用意した参照用のテーブルを利用して、特徴点が事前に用意された形態についてその位置、向き、スケーリングを投票できるようにしたものであり、テンプレートマッチングに近い方法である。

円について応用した例。求める円周上にある（はずの）一点 X_i, Y_iについて、それを通る無限に多くの円を考えることができる。それらの円の中心座標、半径をパラメータとして、三次元ハフ空間内にプロットすると、一つの曲面が形成される（「投票」）。各データ点について投票を行い、多い票を獲得したハフ空間内の点が、求める円を表現するパラメータである。

重み付き特徴点の利用

よく用いられる変法の一つである。あるステージで最も高い値を得たビンが次の検索における値の範囲を制限するために用いられる。

限界

ハフ変換が有効なのは、正しいビンに数多くの投票が集中し、背景雑音から容易に分離できる場合のみである。従ってビンはある程度の大きさでなければならない。そうしないと、投票が隣接するビンにいってしまう場合があり、主となるビンの見やすさが落ちてしまう。

同様に、パラメータの数が大きいと（即ち、通常3を超える数のパラメータを用いる一般化ハフ変換の場合）ビン一つ当たりの平均投票数がきわめて小さくなってしまい、正しいビンの投票数であっても隣のビンと大差なくなってしまう。このように、直線や円以外に一般化ハフ変換を用いる場合は特に注意する必要がある。

最後に、ハフ変換の有効性はデータの質次第であることを挙げる。輪郭の検出は良好でなければならない。ノイズの多い画像へのハフ変換の適用は極めて微妙なものであって、一般的には事前に雑音低減を行っておく必要がある。

歴史

最初の主な用途は泡箱写真の自動分析であった。

ハフ変換は1962年にアメリカ合衆国特許を得ている（"Method and Means for Recognizing Complex Patterns" 「複雑なパタンを認識する手法」）。この特許は直線を傾きと切片でパラメタ化することを内容としており、傾きは無限大になりうる（縦軸に平行な場合）ので、無限の変換空間が必要である場合があるという難点があった。

本項目で例示した (r, θ) の組によるパラメタ化は傾き無限大の場合を考慮する必要がないので、どのような場合でも適用可能である。これを最初に記載したのは、

Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972).

であった。O'Gorman と Clowes の変法は

Frank O'Gorman, MB Clowes: Finding Picture Edges Through Collinearity of Feature Points. IEEE Trans. Computers 25(4): 449-456 (1976)

が初出である。

参考文献・外部リンク

外部リンク

• http://www.cs.tu-bs.de/rob/lehre/bv/Hough.html - Java Applet + Source for learning the Hough transformation in slope-intercept form
• http://www.cs.tu-bs.de/rob/lehre/bv/HNF.html - Java Applet + Source for learning the Hough-Transformation in normal form
• http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm