ハフ変換
ハフ変換 (-へんかん、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"（「
ハフ変換の一般化による任意の形態の検出」）によってコンピュータビジョンの領域で広く用いられるようになった。
実装
ハフ変換に用いる元データは、通常「生の」画像で、通常はそれに輪郭検出を施す。かくして、変換される点の集合は必ずしも全てが適切な画像の輪郭とは限らないことになる。変換処理は任意の数の「ビン」（区切り）に量子化され、それぞれのビンが画像の輪郭になりうる一本の直線を近似的に表す。重要な点（ないしは「特徴点」）の各々は、自分を通る直線を表現するビンの集合に「投票」する。全ての特徴点について「投票」を実行する（各ビンの値を単に加算していく）と、一つの配列ができることになり、その配列から元の画像データにもっともよくあてはまる直線が得られる。
配列の中から大きな値をとったビンを探し出すと、一群の適切な直線とその（近似的な）幾何学的定義が求まる。「ピーク」を求める最も簡単な方法は何らかの閾値を当てはめることだが、場合によっては別の方法を用いるとよりよい結果が得られることもある。この方法では直線の長さの情報が得られないので、次の段階で、どの直線のどの部分が画像にあてはまるかを見つけ出さなければならない。
勾配の方向を用いた投票数の削減
画像強度の局所的な勾配の方向は輪郭に直交するはずである。この点を考慮に入れてO'Gorman と Clowes は、直線の検出における改善法を示唆した。一般的に輪郭検出は画像強度の勾配の大きさを計算する過程を含むので、勾配の方向が副次的に得られることがしばしばである。任意の座標 (x, y) がたまたま実際に直線の上に乗っていたとしよう。このとき局所的な勾配の方向から、問題の直線に対応するパラメータ θ が得られ、即座に r も得られることになる。実際には、真の勾配方向は誤差を込みにして推測するしかなく、±20°程度の精度となる。これは、正弦曲線を誤差分の±20°はトレースする必要があるということを意味する。だが（180°ではなく±20°なので）計算時間の短縮が達成されるだけではなく不必要な投票を抑制することができるので、（真の直線に相当する）配列のピークをはっきり見せる効果がある。
ハフ変換の曲線への応用、一般化ハフ変換
上記の方法は直線を検出するためにしか役立たないが、一組のパラメータで表現しうる形態については全て、類似の変換法が応用できる。例えば（平面上の）円は中心と半径を表す三つのパラメータに変換することができるので、三次元ハフ空間を用いることになる。任意の楕円もパラメータの組で容易に表現できるので同様である。さらに複雑な図形には一般化ハフ変換が用いられる。この方法は事前に用意した参照用のテーブルを利用して、特徴点が事前に用意された形態についてその位置、向き、スケーリングを投票できるようにしたものであり、テンプレートマッチングに近い方法である。
円について応用した例。求める円周上にある（はずの）一点 Xᵢ, Yᵢについて、それを通る無限に多くの円を考えることができる。それらの円の中心座標、半径をパラメータとして、三次元ハフ空間内にプロットすると、一つの曲面が形成される（「投票」）。各データ点について投票を行い、多い票を獲得したハフ空間内の点が、求める円を表現するパラメータである。
重み付き特徴点の利用
よく用いられる変法の一つである。あるステージで最も高い値を得たビンが次の検索における値の範囲を制限するために用いられる。
限界
ハフ変換が有効なのは、正しいビンに数多くの投票が集中し、背景雑音から容易に分離できる場合のみである。従ってビンはある程度の大きさでなければならない。そうしないと、投票が隣接するビンにいってしまう場合があり、主となるビンの見やすさが落ちてしまう。
同様に、パラメータの数が大きいと（即ち、通常3を超える数のパラメータを用いる一般化ハフ変換の場合）ビン一つ当たりの平均投票数がきわめて小さくなってしまい、正しいビンの投票数であっても隣のビンと大差なくなってしまう。このように、直線や円以外に一般化ハフ変換を用いる場合は特に注意する必要がある。
最後に、ハフ変換の有効性はデータの質次第であることを挙げる。輪郭の検出は良好でなければならない。ノイズの多い画像へのハフ変換の適用は極めて微妙なものであって、一般的には事前に雑音低減を行っておく必要がある。