Articles /

ハフ変換

勾配方向を利用して投票数を減らすEdit

O’Gorman と Clowes が提案した改良は、画像強度の局所勾配が必ず縁に直交することを考慮すれば、線の検出に利用することが可能である。 一般にエッジ検出は強度勾配の大きさを計算するため、勾配の方向は副次的な効果として求められることが多い。 ある座標（x,y）の点がたまたま直線上にあった場合、その局所的な勾配の方向がその直線に対応するθパラメータとなり、rパラメータがすぐに求まる。 (Shapiro and Stockman, 305) 勾配の方向は20°以内に推定することができ、正弦波トレースは180°から約45°に短縮される。 これは計算時間を短縮し、無駄な投票数を減らすという興味深い効果をもたらし、画像中の実線に対応するスパイクの視認性を高める。

Kernel-based Hough transform (KHT)Edit

Fernandes and Oliveiraは、比較的大きな画像（例えば1280×960）でも実時間性能を実現するソフトウェア実装を可能にするHough変換の投票スキームを改善し提案している。 Kernel-based Hough変換は、同じ( r , θ ) {displaystyle (r,\theta )}を使用する。

(r,\theta )

DudaとHartが提案したパラメータ化ですが、ほぼ平行な画素のクラスタに対して動作します。 各クラスタについて、対応するクラスタに関して最も適合する線に関連する不確実性をモデル化する配向楕円ガウスカーネルを使用して投票が行われる。 このアプローチは、投票スキームの性能を大幅に向上させるだけでなく、よりクリーンなアキュムレータを生成し、スプリアスラインの検出に対して変換をより堅牢にする。

3D Kernel-based Hough transform for plane detection (3DKHT) 編集

Limberger とOliveira は、コストが n log ( n ) {displaystyle nlog(n)} である未組織点群における平面検出の決定性手法を提案した。

nlog(n)

in number of samples, achieving real-time performance for relatively large datasets (up to 10 5 {displaystyle 10^{5}}}).

10^{5}

ポイント（3.4GHzのCPU使用時）。 これは，Kernel-based Hough変換（KHT）にヒントを得た，平面領域に対する高速なHough変換の投票戦略に基づいています． この3D Kernel-based Hough変換（3DKHT）は、高速で堅牢なアルゴリズムを用いて、ほぼ同一平面上にあるサンプルのクラスタを分割し、（個々のサンプルではなく）個々のクラスタに対して投票を行うもので、( θ , φ , ρ {displaystyle \theta ,\phi ,\rho }) 上で行われます。

\theta ,\phi ,\rho

) spherical accumulator using trivariate Gaussian kernelを使用しています。 この手法は、RHTやRANSACのような点群中の平面検出のための既存の（非決定論的）手法よりも数桁速く、データセットの大きさに応じてより良くスケールします。 大規模データセットにおける平面特徴の高速検出を必要とするあらゆるアプリケーションで利用することができる。

曲線のハフ変換、および解析的および非解析的形状に対するその一般化編集

上述の変換のバージョンは直線を見つけることにのみ適用されるが、同様の変換はパラメータのセットによって表現できる任意の形状を見つけるために使用することができる。 例えば円は、その中心と半径を表す3つのパラメータの集合に変換することで、ハフ空間は3次元になります。 2191>

FernandesとOliveiraは、任意の次元の空間における解析的な形状を検出するためのハフ変換の一般化を提案した。 他のハフ変換に基づく解析的形状に対するアプローチとは対照的に，Fernandesの手法は検出したい形状や入力データの種類に依存しない． データが符号化されている幾何学のモデルを変更することにより（ユークリッド空間、射影空間、共形幾何学など）、提案する定式化はそのままに、検出を分析的形状の種類に誘導することができる。 また、意図した形状を最小のパラメータ数で表現することが保証され、異なる次元と異なる幾何学的定義を持つ入力エントリ集合に最も適合する異なる種類の形状を同時に検出できる（例えば、点、直線、円の集合に最も適合する平面と球の同時検出）

平面のより複雑な形状に対して（すなわち、。 ハフ変換は検出されたエッジのすべてのピクセルからの寄与を蓄積する。

円検出プロセス編集

主要記事 円ハフ変換

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

  • まず、各画素のセルで構成されるアキュムレータ空間を作成します。 初期状態では各セルは0に設定されている。
  • 画像中の各エッジ点（i, j）に対して、円（i – a ）2 +（j – b ）2 = r 2 {displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}} の等式に従って、すべてのセルを増加させる。
    {displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}

    は円の中心になり得る。

  • 前のステップで見つけたa {displaystyle a}
    a

    の各可能値について、式を満たすb {displaystyle b}

    b

    の全ての可能値を求める。

  • アキュムレータ空間に局所最大値を探索する。 これらのセルはアルゴリズムによって検出された円を表す。

探そうとする円の半径があらかじめ分からない場合は、3次元のアキュムレータ空間を使って任意の半径を持つ円を探すことができる。 当然、計算量は多くなる。

この方法は、円の面積がアキュムレータ空間の中に十分残っていれば、部分的にアキュムレータ空間の外にある円も検出できる。

3D オブジェクト（平面と円柱）の検出編集

ハフ変換はレンジデータや3D点群中の3Dオブジェクトの検出にも使用することができる。 古典的なハフ変換の平面検出への拡張は非常に簡単である。 平面はz = a x x + a y y + d {displaystyle z=a_{x}x+a_{y}y+d} という明示的な式で表される。

z=a_{x}x+a_{y}y+d

では、a x {displaystyle a_{x}}に対応する3D Hough空間を使用することができます。

a_{x}

, a y {displaystyle a_{y}}.

a_{y}

and d {displaystyle d}.

d

. この拡張は，2次元のものと同じ問題，すなわち，水平に近い面は確実に検出できるが，面の方向が垂直になると性能が低下する（a x {displaystyle a_{x}} の値が大きい），という問題を抱えている。

a_{x}

と a y {displaystyle a_{y}} がある。

a_{y}

はデータのノイズを増幅させる）。 この定式化は、空中レーザースキャンから取得した点群における平面の検出に使用されており、その領域ではすべての平面がほぼ水平であるため、非常によく機能する。

ハフ変換を用いた一般的な平面検出では、平面はその法線ベクトルn {displaystyle n} によってパラメトリック化されることができる。

n

（球座標を使用）、原点からの距離ρ {displaystyle \rho }を表示する。

rho

となり、3次元のHough空間となる。 この結果、入力データの各点はハフ空間において正弦波に投票することになる。 これらの正弦波曲面の交点は平面の存在を示す。 3次元以上の一般的なアプローチでは、実現可能性を維持するために探索ヒューリスティックが必要となる。

ハフ変換はまた、2段階のアプローチを使って、点群から円筒形のオブジェクトを見つけるために使われてきた。 最初のステップでは円柱の向きを見つけ、2番目のステップでは位置と半径を見つける。

Using weighted featuresEdit

1つの一般的なバリエーションの詳細。

慎重に選択されたパラメータ空間編集

Hough変換の高次元のパラメータ空間は遅いだけでなく、熟考せずに実装すると、利用可能なメモリを簡単にオーバーしてしまう。 プログラミング環境が仮想メモリを介して利用可能なメモリ領域よりも大きな配列を割り当てることができたとしても、インデックスからインデックスへスキップするように連続したメモリに止まることはほとんどなく、アキュムレータ配列はランダムにアクセスされて使用されるため、これに必要なページスワップの回数は非常に厳しいものになるでしょう。 楕円の半径が主軸に沿って配向していると仮定すると、パラメータ空間は4次元となる。 (x,y) は楕円の中心を、a と b は2つの半径を表す。 中心が画像のどこにあってもよいようにすると、0<x<800と0<y<600という制約が追加される。 半径に制約と同じ値を与えると、2300億以上の値がまばらに詰まったアキュムレータ配列が残る。

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

  1. 楕円がそれぞれ完全に画像内に含まれると仮定するのが妥当な場合、半径の範囲を小さくすることができます。 半径が最も大きくなるのは、楕円の中心が画像の中心にあり、楕円の縁が縁に伸びる場合です。 この場合、半径は同じ方向の画像の大きさの半分にしかなりません。 この方法で a と b の範囲を縮小すると、アキュムレータ配列は 570 億の値に減少します。
  2. Hough 変換の推定における空間と交換する精度は、検出されたエッジ内のすべてのピクセルからの寄与を累積します。 ハフ変換は、検出されたエッジのすべてのピクセルからの寄与を蓄積します。 中心がx軸とy軸の両方で3ずれると予測される場合、アキュムレータ配列のサイズは約60億値に減少します。
  3. Trade accuracy for space in the estimation of the radii: 半径がそれぞれ5つずれていると推定される場合、アキュムレータ配列のサイズがさらに縮小され、約2億5,600万個の値が使用されます。 これは画像に依存するので予測できませんが、ある画像で注目するエッジがすべてその画像の左上四分円にある場合を想像してみてください。 この場合、4 つのパラメーターすべてに 2 倍の制約をかけることで、アキュムレータ配列をさらに縮小し、合計で 16 倍にすることができます。

前述の例にこれらの制約の最初の 3 つだけを適用すると、アキュムレータ配列のサイズはほぼ 1000 倍になり、最新のコンピューターのメモリにはるかに収まりやすいサイズまで縮小します。

Efficient ellipse detection algorithmEdit

Yonghong XieとQiang Jiは、メモリの問題を克服して楕円を検出するためのハフ変換を実装する効率的な方法を与えています。 アルゴリズム（論文の2ページ目）で述べられているように、この方法は、画像中の楕円を検出するために、（短軸用の）1次元アキュムレータのみを使用します。 その複雑さは、画像中の非ゼロ点の数でO(N3)となります

。

Leave a Reply