ハフ変換は、画像解析、コンピュータビジョン、パターン認識、およびデジタル画像処理において使用される特徴抽出技術である。その目的は、投票手続きによって、特定のクラスの形状内にある不完全なオブジェクトのインスタンスを見つけることである。この投票手続きはパラメータ空間で実行され、そこからオブジェクト候補が、アルゴリズムによって明示的に構築された累積空間内の局所的最大値として得られる。数学的には、これは平面上のラドン変換であり、少なくとも1917年から知られているが、ハフ変換は特に画像解析での使用を指す。
古典的なハフ変換は画像内の直線を識別することに関係していたが、その後、任意の形状、最も一般的には円や楕円の位置を識別するように拡張されている。今日普遍的に使用されている変換は、1972年にリチャード・デュダとピーター・ハートによって発明され、彼らは関連する1962年のポール・ハフの特許にちなんで「一般化ハフ変換」と呼んだ。これは、1981年のジャーナル記事「一般化ハフ変換による任意形状の検出」を通じて、デイナ・H・バラードによってコンピュータビジョンコミュニティで普及した。
歴史
ハフ変換は、1959年にポール・ハフによって泡箱写真の機械解析のために最初に発明された。これは1962年に米国特許3,069,654として特許取得され、「複雑なパターンを認識するための方法と手段」という名称で米国原子力委員会に譲渡された。この特許は直線に対して傾き切片パラメータ化を使用しており、傾きが無限大になり得るため、変換空間が非有界になるという厄介な問題があった。
今日普遍的に使用されているローシータパラメータ化は、1972年にリチャード・デュダとピーター・ハートによる論文「画像内の直線と曲線を検出するためのハフ変換の使用」で最初に記述され、Communications of the ACMに掲載された。このパラメータ化は、少なくとも1930年代からラドン変換の標準であった。フランク・オゴーマンとM.B.クラウズは、1976年にIEEE Transactions on Computersで「特徴点の共線性による画像エッジの発見」と題する変種を発表した。現代の形式がどのように発明されたかの物語は、ピーター・ハートの2009年のIEEE Signal Processing Magazineの記事「ハフ変換がどのように発明されたか」で詳述されている。
理論
デジタル画像の自動解析では、直線、円、楕円などの単純な形状を検出するサブ問題がしばしば発生する。エッジ検出器は前処理段階として使用され、目的の曲線上にある画像点を取得できる。しかし、画像データやエッジ検出器の不完全性により、理想的な形状とノイズの多いエッジ点との間に欠落点や空間的偏差が存在する可能性がある。ハフ変換は、パラメータ化された画像オブジェクトのセットに対して明示的な投票手続きを実行することでこれに対処し、エッジ点をオブジェクト候補にグループ化することを可能にする。
直線の検出
最も単純なケースは直線の検出である。一般に、直線y = mx + bはパラメータ空間内の点(b, m)として表すことができるが、垂直線は傾きの値が非有界であるため問題を引き起こす。デュダとハートは、ヘッセ標準形を使用することを提案した: r = x cos(θ) + y sin(θ)。ここで、rは原点から直線上の最も近い点までの距離であり、θはx軸と原点をその最も近い点に結ぶ線との間の角度である。直線上のすべてのベクトルは、原点から長さrの線分に垂直である。交点はP0 = (r cos(θ), r sin(θ))にある。直線上の任意の点Pについて、ベクトルP - P0はP0に直交しなければならず、(P - P0)・P0 = 0が強制され、これはr(x cos(θ) + y sin(θ)) = r^2(cos^2(θ) + sin^2(θ))に簡約される。
アルゴリズムと投票手続き
実際には、ハフ変換はパラメータ空間を累積配列に離散化する。画像内の各エッジ点について、アルゴリズムはその点を通る形状に対応し得るすべての可能なパラメータ値（例えば、直線の場合はrとθ）を計算し、対応する累積セルを増分する。すべての点を処理した後、累積内の局所的最大値は可能性のある形状候補を示す。この投票手続きは、形状上のすべての点が完全に整列していることを必要としないため、ノイズや欠落データに対して堅牢である。
拡張と応用
1981年にデイナ・バラードによって導入された一般化ハフ変換は、参照点とエッジ方向のテーブルを使用して、任意の形状に技術を拡張する。これにより、直線、円、楕円を超えた複雑な形状の検出が可能になる。この変換は、自動運転、医用画像、産業検査などの分野で広く応用されている。Computer visionシステムでは、デジタル画像処理パイプライン内のオブジェクトを識別するために、エッジ検出アルゴリズムと組み合わせて使用されることが多い。その数学的基盤であるラドン変換は、Machine learningやArtificial intelligenceアプリケーションで使用されるより広範な画像解析技術と結びついている。
制限と変種
古典的なハフ変換の1つの制限は、特に高次元のパラメータ空間における計算コストである。確率的ハフ変換やハフ円変換などの変種が、効率を改善するために開発されている。確率的バージョンはエッジ点のサブセットをサンプリングして計算を削減し、円変換は3次元パラメータ空間（中心x、中心y、半径）を使用する。これらの変種は、opencvなどのライブラリで一般的に実装されており、自動運転車やRoboticsを含むリアルタイムシステムで使用されている。
関連項目
- radon-transform
- edge-detection
- Computer vision
- image-processing