ハフ変換

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

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

${\displaystyle r=x\cdot \cos \theta +y\cdot \sin \theta }$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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