ハフ変換とは？ わかりやすく解説

ハフ変換（ハフへんかん、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 及び θ と呼ばれ、それぞれ原点から問題の直線に引いた法線の長さと角度とを表す。このように表現すると、直線の式は次のようになる:

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

図を見てほしい。ここではデータとして左に示すような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)

が初出である。

参考文献・外部リンク

参考文献

1. ^ 国際電気通信基礎技術研究所による特開平05-012438[1]
2. ^ (新エネルギー・産業技術総合開発機構)即効型地域新生コンソーシアム研究開発 柔軟変形物ハンドリング用ビジョンチップの研究開発報告書 [2]および、立命館大学講義ノート [3]
3. ^ MATLAB解説記事より[4]
4. ^ [5]

外部リンク

• 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