ハフ変換

ハフ変換は、画像解析、コンピュータビジョン、パターン認識、デジタル画像処理で使用される特徴抽出技術です。^{[1] [2]この技術の目的は、投票手順によって特定の形状クラス内のオブジェクトの不完全なインスタンスを見つけることです。この投票手順は}パラメーター空間で実行され、そこからオブジェクト候補が、ハフ変換を計算するアルゴリズムによって明示的に構築されたいわゆる累積空間内の局所最大値として取得されます。

古典的なハフ変換は画像内の線の識別に関係していましたが、後にハフ変換は任意の形状、最も一般的な円または楕円の位置の識別に拡張されました。今日広く使用されているハフ変換は、 1972年にリチャード・デューダとピーター・ハートによって発明され、彼らは1962年のポール・ハフの関連する特許にちなんで「一般化ハフ変換」^{[3]と呼びました。 [4] [5]この変換は、1981年に}ダナ・H・バラードによって「ハフ変換を一般化して任意の形状を検出」 と題された雑誌記事を通じてコン​​ピュータービジョンコミュニティに普及しました。

当初はバブルチャンバー写真の機械分析のために発明されました(Hough、1959)。

ハフ変換は、 1962 年に米国特許 3,069,654として特許取得され、「複雑なパターンを認識する方法と手段」という名称で米国原子力委員会に譲渡されました。この特許では、直線の傾きと切片のパラメータ化を使用していますが、傾きが無限大になる可能性があるため、変換空間が境界なしになります。

現在広く使用されているロー・シータパラメータ化は、

Duda, RO; Hart, PE (1972 年 1 月)。「ハフ変換を使用した画像内の直線と曲線の検出」。Comm . ACM . 15 : 11–15. doi : 10.1145/361237.361242 . S2CID  1105637。

ただし、少なくとも 1930 年代から ラドン変換の標準となっていました。

オゴーマンとクロウズのバリエーションは、

O'Gorman, Frank; Clowes, MB (1976). 「特徴点の共線性による画像のエッジの検出」IEEE Trans. Comput . 25 (4): 449–456. doi :10.1109/TC.1976.1674627. S2CID  10851078.

ハフ変換の現代的な形がどのように発明されたかについては、

Hart, PE (2009 年 11 月)。「ハフ変換の発明方法」(PDF)。IEEE Signal Processing Magazine。26 ( 6 ): 18–22。doi : 10.1109 /msp.2009.934181。S2CID 16245096。2018年 5 月 16 日の オリジナル(PDF)からアーカイブ。

デジタル画像の自動分析では、直線、円、楕円などの単純な形状を検出するというサブ問題が頻繁に発生します。多くの場合、エッジ検出器は、画像空間内の目的の曲線上にある画像ポイントまたは画像ピクセルを取得するための前処理段階として使用できます。ただし、画像データまたはエッジ検出器のどちらかの不完全性により、目的の曲線上のポイントまたはピクセルが欠落している可能性があり、また、エッジ検出器から取得された理想的な線/円/楕円とノイズの多いエッジポイントとの間に空間的な偏差が生じる可能性があります。これらの理由から、抽出されたエッジ特徴を適切な線、円、または楕円のセットにグループ化することは、多くの場合簡単ではありません。ハフ変換の目的は、パラメーター化された画像オブジェクトのセットに対して明示的な投票手順を実行することによって、エッジポイントをオブジェクト候補にグループ化できるようにすることで、この問題に対処することです (Shapiro および Stockman、304)。

ハフ変換の最も単純なケースは直線の検出である。一般に、直線y = mx + bはパラメータ空間内の点 ( b ,  m ) として表すことができる。しかし、垂直線は問題を引き起こす。垂直線は傾斜パラメータmの無制限の値を生み出す。したがって、計算上の理由から、DudaとHart ^[6]はヘッセ正規形の使用を提案した。

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

ここで、は原点から直線上の最も近い点までの距離であり、は軸と原点とその最も近い点を結ぶ線 との間の角度です。${\displaystyle r}$${\displaystyle \theta }$${\displaystyle x}$

この形式に対する直観は、平面方程式と同様に、直線上のすべてのベクトルが、原点から来る長さの直線に対して垂直（直交）でなければならないということです。関数直線と原点からの垂直直線の交点は にあることがわかります。したがって、直線上の任意の点に対して、ベクトルはベクトル に対して直交する必要があります。したがって、関数直線上の任意の点に対して、方程式が満たされる必要があることがわかります。したがって、 です。およびなので、 になります。 なので、 の最終形式を取得します。 ${\displaystyle r}$${\displaystyle P_{0}=(r\cos \theta ,r\sin \theta )}$${\displaystyle P}$${\displaystyle P-P_{0}}$${\displaystyle P_{0}-0=P_{0}}$${\displaystyle P=(x,y)}$${\displaystyle (P-P_{0})\cdot P_{0}=0}$${\displaystyle P\cdot P_{0}=P_{0}\cdot P_{0}}$${\displaystyle P=(x,y)}$${\displaystyle P_{0}=(r\cos \theta ,r\sin \theta )}$${\displaystyle r(x\cos \theta +y\sin \theta )=r^{2}(\cos ^{2}\theta +\sin ^{2}\theta )}$${\displaystyle \cos ^{2}\theta +\sin ^{2}\theta =1}$${\displaystyle x\cos \theta +y\sin \theta =r}$

したがって、画像の各線にペアを関連付けることができます。平面は、2次元の直線の集合を表すハフ空間と呼ばれることもあります。この表現により、ハフ変換は概念的に2次元ラドン変換に非常に近くなります。実際、ハフ変換は数学的にはラドン変換と同等ですが、2つの変換には伝統的に関連付けられている異なる計算解釈があります。^[7]${\displaystyle (r,\theta )}$${\displaystyle (r,\theta )}$

平面上の1 つの点が与えられた場合、その点を通るすべての直線の集合は、その点に固有の( r ,  θ ) 平面上の正弦曲線に対応します。直線を形成する 2 つ以上の点の集合は、その直線の ( r ,  θ ) で交差する正弦曲線を生成します。したがって、共線上の点を検出する問題は、同時曲線を見つける問題に変換できます。

によってパラメータ化された形状が与えられ、形状空間と呼ばれる集合内の値を取ると、ハフ変換は画像空間上の確率分布の形状空間への逆変換として解釈でき、形状検出は最大尤度推定として解釈できます。 ${\displaystyle (a_{1},...,a_{t})}$${\displaystyle S}$${\displaystyle S}$

明示的には、ハフ変換は近似的なナイーブ ベイズ推論を実行します。形状空間の均一な事前分布から開始します。部分的に遮蔽された形状を検出できるように、肯定的な証拠のみを考慮し、否定的な証拠はすべて無視します。

形状空間の対数尤度を加法定数まで加算します。単純ベイズの仮定は、画像空間のすべてのピクセルが独立した証拠を提供するため、それらの尤度が乗算され、つまり対数尤度が加算されることを意味します。加法定数の自由度により、形状空間の「背景ピクセル」に対して操作を実行する必要がありません。

最後に、形状空間上の対数尤度のピークを選択して最大尤度推定を行う。^[8]

派生語

線形ハフ変換アルゴリズムは、直線を定義する 2 つのパラメータを推定します。変換空間には 2 つの次元があり、変換空間内のすべてのポイントは、によって記述される線を検出または識別するための累算器として使用されます。画像内の検出されたエッジ内のすべてのポイントが累算器に寄与します。 ${\displaystyle r=x\cos \theta +y\sin \theta }$

累算器の次元は、未知のパラメータの数、つまり、ペアのとの量子化された値を考慮すると 2 に等しくなります。 とその近傍の各ピクセルについて、ハフ変換アルゴリズムは、そのピクセルに直線の十分な証拠があるかどうかを判断します。 十分な証拠がある場合、その直線のパラメータを計算し、パラメータが該当する累算器のビンを探して、そのビンの値を増分します。 ${\displaystyle r}$${\displaystyle \theta }$${\displaystyle (r,\theta )}$${\displaystyle (x,y)}$${\displaystyle (r,\theta )}$

最も高い値を持つビンを見つけることによって、通常はアキュムレータ空間で極大値を探すことによって、最も可能性の高い線を抽出し、それらの（おおよその）幾何学的定義を読み取ることができます（Shapiro と Stockman、304）。これらのピークを見つける最も簡単な方法は、何らかの形式のしきい値を適用することですが、状況によっては、どの線が見つかったか、またいくつ見つかったかを判断する他の手法の方が、より良い結果をもたらす場合があります。返された線には長さの情報が含まれていないため、次のステップで、画像のどの部分がどの線と一致するかを見つける必要があることがよくあります。さらに、エッジ検出ステップでの不完全なエラーにより、アキュムレータ空間にエラーが発生するのが通常であり、適切なピーク、ひいては適切な線を見つけるのは簡単ではありません。

線形ハフ変換の最終結果は、累算器に似た2次元配列（行列）です。この行列の1つの次元は量子化された角度で、もう1つの次元は量子化された距離です。行列の各要素の値は、量子化されたパラメータによって表される線上にある点またはピクセルの合計に等しくなります。したがって、最も高い値を持つ要素は、入力画像で最もよく表される直線を示します。^[9]${\displaystyle \theta }$${\displaystyle r}$${\displaystyle (r,\theta )}$

ここで黒い点で示されている 3 つのデータ ポイントを検討します。

• 各データ ポイントには、そのポイントを通過する複数の線がさまざまな角度でプロットされます。これらは、ここではさまざまな色で表示されます。
• ハフ変換は、検出されたエッジのすべてのピクセルからの寄与を蓄積します。各線には、その線に垂直で原点と交差するサポート ラインが存在します。いずれの場合も、そのうちの 1 つが矢印として表示されます。
• 各サポート ラインの長さ (つまり、原点に対する垂直距離) と角度が計算されます。長さと角度は図の下に表形式で示されています。

計算から、どちらの場合も 60° のサポート ラインの長さは同じであることがわかります。したがって、対応する線 (上の図の青い線) は非常に似ていることがわかります。したがって、すべてのポイントが青い線の近くにあると想定できます。

以下は、2 本の太線を含むラスター イメージに対する Hough 変換の結果を示す別の例です。

この変換の結果はマトリックスに保存されました。セル値は、任意の点を通る曲線の数を表します。セル値が高いほど明るく表示されます。2 つのはっきりと明るいスポットは、2 本の線の Hough パラメータです。これらのスポットの位置から、入力画像内の 2 本の線の角度と画像中心からの距離を判断できます。

O'Gorman と Clowes が提案した改善法は、画像強度の局所勾配が必然的にエッジに直交することを考慮すれば、線の検出に使用できます。エッジ検出には通常、強度勾配の大きさの計算が含まれるため、勾配の方向は副次的な効果として見つかることがよくあります。座標 ( x,y ) の特定の点が実際に線上にある場合、勾配の局所方向からその線に対応するθパラメータが得られ、rパラメータがすぐに得られます (Shapiro と Stockman、305)。勾配の方向は 20° 以内で推定できるため、正弦波のトレースが 180° 全体から約 45° に短縮されます。これにより計算時間が短縮され、無駄な投票数が減るという興味深い効果があり、画像内の実際の線に対応するスパイクの視認性が向上します。

Fernandes と Oliveira ^[10]は、ハフ変換の改良投票方式を提案しました。この方式では、比較的大きな画像 (例: 1280×960) でもソフトウェア実装でリアルタイム パフォーマンスを実現できます。カーネル ベースのハフ変換は、Duda と Hart が提案したものと同じパラメーター化を使用しますが、ほぼ共線的なピクセルのクラスターで動作します。各クラスターでは、対応するクラスターに関して最もよく適合する線に関連する不確実性をモデル化する有向楕円ガウス カーネルを使用して投票が行われます。このアプローチは、投票方式のパフォーマンスを大幅に向上させるだけでなく、よりクリーンな累算器を生成し、変換を偽の線の検出に対してより堅牢にします。 ${\displaystyle (r,\theta )}$

Limberger と Oliveira ^{[11] は、}サンプル数にコストがかかる、整理されていないポイント クラウドでの平面検出のための決定論的手法を提案し、比較的大規模なデータ セット ( 3.4 GHz CPU で最大ポイント) に対してリアルタイムのパフォーマンスを実現しています。これは、カーネル ベース ハフ変換 (KHT) にヒントを得た、平面領域に対する高速ハフ変換投票戦略に基づいています。この 3D カーネル ベース ハフ変換 (3DKHT) は、高速で堅牢なアルゴリズムを使用して、ほぼ共平面のサンプルのクラスターをセグメント化し、三変量ガウス カーネルを使用して ( ) 球面累算器で (個々のサンプルではなく) 個々のクラスターに投票します。このアプローチは、 RHTやRANSACなどのポイント クラウドでの平面検出の既存の (非決定論的) 手法よりも数桁高速で、データ セットのサイズに合わせて拡張できます。大規模なデータ セットで平面の特徴を高速に検出する必要があるアプリケーションで使用できます。 ${\displaystyle n\log(n)}$${\displaystyle 10^{5}}$${\displaystyle \theta ,\phi ,\rho }$

上記の変換は直線を見つける場合にのみ適用されますが、同様の変換を使用して、一連のパラメータで表現できる任意の形状を見つけることができます。たとえば、円は、中心と半径を表す 3 つのパラメータのセットに変換できるため、ハフ空間は 3 次元になります。任意の楕円や曲線もこの方法で見つけることができ、パラメータのセットとして簡単に表現できる任意の形状も見つけることができます。

任意の次元を持つ空間で解析形状を検出するためのハフ変換の一般化は、フェルナンデスとオリベイラによって提案されました。^[12]解析形状に対する他のハフ変換ベースのアプローチとは対照的に、フェルナンデスの手法は、検出したい形状や入力データのタイプに依存しません。提案された定式化は変更せずに、データがエンコードされている想定される幾何学モデル（ユークリッド空間、射影空間、等角幾何学など）を変更することで、検出を解析形状のタイプに誘導できます。また、意図した形状が可能な限り少ない数のパラメーターで表現されることが保証され、異なる次元と異なる幾何学的定義を持つ入力エントリセットに最適な異なる種類の形状の同時検出が可能になります（たとえば、点、直線、円のセットに最適な平面と球の同時検出）。

平面上のより複雑な形状（つまり、2次元空間で解析的に表現できない形状）の場合、一般化ハフ変換^[13]が使用されます。これにより、特徴は定義済みのルックアップテーブルを使用して、形状の特定の位置、方向、および/またはスケーリングに投票できます。ハフ変換は、検出されたエッジのすべてのピクセルからの寄与を蓄積します。

線ではなく円形を検出するようにアルゴリズムを変更するのは比較的簡単です。

• まず、各ピクセルのセルで構成されるアキュムレータ スペースを作成します。最初、各セルは 0 に設定されます。
• 画像内の各エッジ ポイント (i, j) について、円の方程式に従って円の中心になる可能性のあるすべてのセルを増分します。これらのセルは、方程式内の文字で表されます。${\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}$${\displaystyle a}$
• 前の手順で見つかったの可能な値ごとに、方程式を満たす の可能な値をすべて見つけます。${\displaystyle a}$${\displaystyle b}$
• 累積空間で局所最大値を検索します。これらのセルは、アルゴリズムによって検出された円を表します。

探している円の半径が事前にわからない場合は、3 次元の累積空間を使用して任意の半径の円を検索できます。当然、計算コストは​​高くなります。

この方法では、十分な円の領域がアキュムレータ スペース内に残っている限り、部分的にアキュムレータ スペースの外側にある円も検出できます。

ハフ変換は、レンジデータまたは 3Dポイントクラウド内の 3D オブジェクトの検出にも使用できます。 従来のハフ変換を平面検出に拡張するのは非常に簡単です。 平面は、、およびに対応する 3D ハフ空間を使用できる明示的な方程式によって表されます。 この拡張は、2D の場合と同じ問題を抱えています。つまり、ほぼ水平な平面は確実に検出できますが、平面の方向が垂直になるとパフォーマンスが低下します (および の値が大きいと、データ内のノイズが増幅されます)。 この平面の定式化は、航空機によるレーザースキャンから取得されたポイントクラウド内の平面の検出に使用されており^[14]、その領域ではすべての平面がほぼ水平であるため、非常にうまく機能します。 ${\displaystyle z=a_{x}x+a_{y}y+d}$${\displaystyle a_{x}}$${\displaystyle a_{y}}$${\displaystyle d}$${\displaystyle a_{x}}$${\displaystyle a_{y}}$

ハフ変換を用いた一般化された平面検出では、平面をその法線ベクトル（球座標を使用）と原点からの距離でパラメータ化することができ、3次元ハフ空間が得られる。これにより、入力データの各点はハフ空間内の正弦波面を選択する。これらの正弦波面の交点は平面の存在を示す。^[15] 3次元を超えるより一般的なアプローチでは、実行可能な検索ヒューリスティックが必要である。^[16]${\displaystyle n}$${\displaystyle \rho }$

ハフ変換は、2段階のアプローチを使用して点群内の円筒形オブジェクトを見つけるためにも使用されています。最初のステップでは円筒の方向を見つけ、2番目のステップでは位置と半径を見つけます。^[17]

一般的なバリエーションの詳細の 1 つ。つまり、あるステージでカウントが最も高いビンを見つけることで、次のステージで検索される値の範囲を制限できます。

ハフ変換の高次元パラメータ空間は遅いだけでなく、事前に考慮せずに実装すると、使用可能なメモリを簡単にオーバーランする可能性があります。プログラミング環境で、仮想メモリを介して使用可能なメモリ空間よりも大きな配列の割り当てが許可されている場合でも、アキュムレータ配列はランダムアクセス方式で使用され、インデックスからインデックスにスキップするときに連続したメモリで停止することはほとんどないため、これに必要なページスワップの数は非常に多くなります。

800x600 の画像で楕円を見つけるタスクを考えてみましょう。楕円の半径が主軸に沿っていると仮定すると、パラメータ空間は 4 次元になります。( x、y ) は楕円の中心を定義し、aとb は2 つの半径を表します。中心が画像内のどこにあってもかまわないので、制約 0<x<800 および 0<y<600 が追加されます。半径に制約と同じ値が与えられた場合、2,300 億を超える値がまばらに埋め込まれたアキュムレータ配列が残ります。

このように考えられたプログラムでは、十分なメモリを割り当てることはおそらくできません。これは、問題を解決できないという意味ではなく、アキュムレータ配列のサイズを制限する新しい方法が見つかることを意味し、それが実現可能になることを意味します。たとえば、次のようになります。

1. 楕円がそれぞれ画像内に完全に含まれていると想定するのが妥当な場合は、半径の範囲を縮小できます。半径が最大になるのは、楕円の中心が画像の中心にあり、楕円の端が端まで伸びる場合です。この極端なケースでは、半径はそれぞれ、同じ方向を向いた画像サイズの半分の大きさしか取れません。このように a と b の範囲を縮小すると、アキュムレータ配列は 570 億個の値に減ります。
2. 中心の推定では、精度とスペースをトレードオフします。中心が x 軸と y 軸の両方で 3 ずれていると予測される場合、累積配列のサイズは約 60 億の値に縮小されます。
3. 半径の推定におけるスペースと精度のトレードオフ: 半径がそれぞれ 5 ずつずれていると推定された場合、アキュムレータ配列のサイズがさらに約 2 億 5,600 万個削減されます。
4. 画像を関心領域に切り取ります。これは画像に依存しているため予測できませんが、画像内の関心のあるエッジがすべてその画像の左上象限にある場合を想像してください。この場合、4 つのパラメータすべてを 2 倍に制限することで、アキュムレータ配列をさらに縮小でき、合計縮小率は 16 になります。

これらの制約の最初の 3 つを前述の例に適用するだけで、アキュムレータ配列のサイズはほぼ 1000 分の 1 に縮小され、最新のコンピュータのメモリに収まる可能性がはるかに高くなるサイズになります。

Yonghong XieとQiang Jiは、メモリの問題を克服することで、楕円検出のためのハフ変換を実装する効率的な方法を示しています。^[18]アルゴリズム（論文の2ページ目）で説明されているように、このアプローチでは、画像内の楕円を検出するために、1次元の累算器（短軸用）のみを使用します。画像内の非ゼロ点の数に対する複雑さはO(N ³ )です。

ハフ変換は、多くの投票が正しいビンに入る場合にのみ効率的であり、背景ノイズの中でもビンを簡単に検出できます。つまり、ビンは小さすぎてはならず、さもないと一部の投票が隣接するビンに入り、メインのビンの可視性が低下します。^[19]

また、パラメータの数が多い場合 (つまり、通常 3 つ以上のパラメータで Hough 変換を使用している場合)、単一のビンに投じられる平均投票数は非常に少なく、画像内の実際の図形に対応するビンは、必ずしも隣接するビンよりも投票数が非常に多いようには見えません。複雑性は、パラメータが追加されるたびに の割合で増加します。ここで、は画像空間のサイズ、 はパラメータの数です。 (Shapiro および Stockman、310) したがって、線や円以外のものを検出するには、Hough 変換を細心の注意を払って使用する必要があります。 ${\displaystyle {\mathcal {O}}\left({A^{m-2}}\right)}$${\displaystyle A}$${\displaystyle m}$

最後に、ハフ変換の効率性は入力データの品質に大きく依存します。ハフ変換を効率的に行うには、エッジが適切に検出される必要があります。ノイズの多い画像にハフ変換を使用するのは非常にデリケートな問題であり、通常は、その前にノイズ除去段階を使用する必要があります。レーダー画像の場合のように、画像がスペックルによって破損している場合は、加算によってノイズを減衰させるため、 ラドン変換が線の検出に好まれることがあります。

• 一般化ハフ変換
• ランダム化ハフ変換
• ラドン変換
• フーリエ変換

• hough_transform.cpp – C++ コード – CImg ライブラリの例 (オープンソースライブラリ、C++ソース コード、グレースケール画像)
• ハフ変換の基礎に関するインタラクティブなデモンストレーション
• https://web.archive.org/web/20070827233423/http://www.rob.cs.tu-bs.de/content/04-teaching/06-interactive/Hough.html –傾きと切片の形式でのハフ変換を学習するためのJava アプレット+ ソース
• https://web.archive.org/web/20070827191440/http://www.rob.cs.tu-bs.de/content/04-teaching/06-interactive/HNF.html –正規形でのハフ変換を学習するためのJava アプレット+ ソース
• http://www.sydlogan.com/deskew.html 2010-02-09 にWayback Machineでアーカイブ– Hough 変換を使用した画像の傾き補正 (グレースケール画像、C++ソース コード)
• https://web.archive.org/web/20070922090216/http://imaging.gmse.net/articledeskew.html – ハフ変換を使用した画像の傾き補正 ( Visual Basicソース コード)
• http://www.mitov.com/products/visionlab –線、円、線分のハフ変換コンポーネントを含む、教育目的の無料Delphi、C++、. NETライブラリ。
• Tarsha-Kurdi, F.、Landes, T.、Grussenmeyer, P.、2007a。LIDAR データから 3D 建物屋根面を自動検出するための Hough 変換および拡張 RANSAC アルゴリズム。ISPRS Proceedings。レーザー スキャン ワークショップ。エスポー、フィンランド、2007 年 9 月 12 ～ 14 日。
• Into には、C++ での線形および円形ハフ変換のオープンソース実装が含まれています。
• http://www.vision.ime.usp.br/~edelgado/defesa/code/hough.html 2012-12-05 にarchive.todayにアーカイブされました。楕円検出のための Hough 変換。Cで実装されています。
• scikit-image 線、円、楕円のハフ変換。Python で実装されています。
• [1] ウェーブレットフィルタリングに基づくハフ変換。特定の半径の円を検出します。（Matlabコード）
• MATLAB を使用した直線のハフ変換 2014-04-13 にWayback Machineでアーカイブされました
• MATLAB での円のハフ変換
• KHT – C++ ソースコード。
• 3DKHT – C++ ソースコードとデータセット。
• Python での直線ハフ変換