ハフ変換
いいかえれば、θに対して直角で、原点から r の距離にあるものとして直線を表現するわけだ。(r, θ) の組の集合がなす平面を、「ハフ空間」と呼ぶこともある。このような表現を取る点で、ハフ変換はいわゆるラドン変換( en:Radon transform) と概念的に極めて近い。即ち、ハフ変換とは、二値化された画像に対して、ラドン変換を施すことに他ならない。
平面上の一点を通る直線は無限に存在する。問題となる点の画像上での座標を ( x 0 , y 0 ) {\displaystyle (x_{0},y_{0})} としよう。この点を通る全ての直線は、次の式に従う:
r ( θ ) = x 0 ⋅ cos  θ + y 0 ⋅ sin  θ {\displaystyle r(\theta )=x_{0}\cdot \cos \theta +y_{0}\cdot \sin \theta }
これは (r, θ) 平面上の一つの正弦曲線に相当し、画像上の点が決まれば一意に決まる。二つの点に対応する曲線を重ね書きした場合、ハフ空間内において二つの曲線が交わる点は、この二つの点を同時に通る直線に対応する。一般化すれば、(画像上における)直線上の点の集合は、その直線に対応するハフ空間内の一点で交わるような正弦曲線の集合を生成する。
ハフ変換に用いる元データは、通常「生の」画像で、通常はそれに輪郭検出を施す。かくして、変換される点の集合は必ずしも全てが適切な画像の輪郭とは限らないことになる。変換処理は任意の数の「ビン」(区切り)に量子化され、それぞれのビンが画像の輪郭になりうる一本の直線を近似的に表す。重要な点(ないしは「特徴点」)の各々は、自分を通る直線を表現するビンの集合に「投票」する。全ての特徴点について「投票」を実行する(各ビンの値を単に加算していく)と、一つの配列ができることになり、その配列から元の画像データにもっともよくあてはまる直線が得られる。
配列の中から大きな値をとったビンを探し出すと、一群の適切な直線とその(近似的な)幾何学的定義が求まる。「ピーク」を求める最も簡単な方法は何らかの閾値を当てはめることだが、場合によっては別の方法を用いるとよりよい結果が得られることもある。この方法では直線の長さの情報が得られないので、次の段階で、どの直線のどの部分が画像にあてはまるかを見つけ出さなければならない。