一般化ハフ変換

1981年にDana H. Ballardによって導入された一般化ハフ変換（GHT）は、テンプレートマッチングの原理を使用してハフ変換を修正したものです。^{[1]ハフ変換は当初、解析的に定義された形状（}線、円、楕円など）を検出するために開発されました。これらの場合、形状の知識があり、画像内での形状の位置と方向を見つけることが目的です。この修正により、ハフ変換を使用して、モデルで記述された任意のオブジェクトを検出できるようになりました。

画像内のオブジェクト (モデルで記述) を見つける問題は、画像内のモデルの位置を見つけることで解決できます。一般化ハフ変換を使用すると、モデルの位置を見つける問題は、モデルを画像にマッピングする変換パラメータを見つける問題に変換されます。変換パラメータの値を指定すると、画像内のモデルの位置を決定できます。

GHT の元の実装では、エッジ情報を使用して、エッジ ポイントの方向から形状の参照ポイントへのマッピングを定義していました。ピクセルが黒または白のいずれかになるバイナリ画像の場合、画像のすべての黒いピクセルは目的のパターンの黒いピクセルになる可能性があり、これによりハフ空間に参照ポイントの軌跡が作成されます。画像のすべてのピクセルは、対応する参照ポイントに投票します。ハフ空間の最大ポイントは、画像内のパターンの可能な参照ポイントを示します。この最大値は、ハフ空間をスキャンするか、それぞれが黒いピクセルに対応する緩和された方程式のセットを解くことによって見つけることができます。 ^[2]

マーリンとファーバー^{[3]は、望ましい曲線を解析的に記述できない場合にハフアルゴリズムを使用する方法を示しました。これは、}平行移動に制限され、回転やスケールの変更を考慮しなかったバラードのアルゴリズムの前身でした。^[4]

Merlin-Farber アルゴリズムは、エッジ ピクセルが多数ある画像では反復的なピクセル配置により多くの誤検出が発生するため、実際の画像データには実用的ではありません。

Hough アルゴリズムを非解析曲線に一般化するために、Ballard は一般化された形状に対して次のパラメータを定義します: a={y,s,θ}。ここで、yは形状の参照原点、 θはその方向、s = (s _x、 s _y )は 2 つの直交スケール係数を表します。アルゴリズムは、エッジ ピクセル データから特定の形状に対する最適なパラメータ セットを計算できます。これらのパラメータは同じステータスではありません。参照原点の位置yは、可能なエッジ ピクセル方向の R テーブルと呼ばれるテンプレート テーブルで表されます。追加のパラメータsと θの計算は、このテーブルへの直接的な変換によって行われます。任意の形状への重要な一般化は、方向情報の使用です。パラメトリック曲線の代わりに任意の形状とその上の固定参照点が与えられた場合、境界ピクセルによって提供される情報は、変換段階で R テーブルの形式で格納されます。テスト画像上のすべてのエッジ ポイントについて、ポイントのプロパティが R テーブルで検索され、参照ポイントが取得され、アキュムレータ マトリックスと呼ばれるマトリックス内の適切なセルが増分されます。アキュムレータ マトリックス内で最大の「投票」を持つセルは、テスト画像内のオブジェクトの固定参照が存在する可能性のあるポイントである可能性があります。

形状の参照点y を選択します (通常は形状の内側で選択されます)。各境界点xについて、 図に示すようにɸ(x)、勾配方向、およびr = y – xを計算します。r をɸの関数として保存します。ɸ の各インデックスには、 r の値が複数ある場合があることに注意してください。固定参照とエッジ ポイント間の座標差((x _c – x _ij )、(y _c – y _ij ))を保存すること も、それらの間の半径距離と角度(r _ij、α _ij )として保存することもできます。各ポイントに対してこれを行うと、 R テーブルはテンプレート オブジェクトを完全に表すようになります。また、生成フェーズは可逆であるため、これを使用して、画像内の他の場所でのオブジェクトの発生を特定できます。

画像内の各エッジ ピクセルxについて、勾配ɸを見つけ、アキュムレータ配列A (画像の最大サイズに初期化)内のすべての対応するポイントx+rを増分します。ここで、 r はɸでインデックス付けされたテーブル エントリ、つまりr(ɸ)です。これらのエントリ ポイントは、参照ポイントの可能な位置を示します。いくつかの偽のポイントが計算される場合もありますが、オブジェクトが画像内に存在する場合、最大値は参照ポイントで発生します。A の最大値は、形状の可能なインスタンスに対応します。

形状の向きが固定されている場合、アキュムレータ配列は参照点座標で 2 次元です。任意の向きθとスケールsの形状を検索するには、これら 2 つのパラメータを形状の説明に追加します。アキュムレータ配列は、パラメータ(y、s、θ)に対応する 4 つの次元で構成されます。さまざまな向きとスケールはテーブルの簡単に計算できる変換に対応するため、R テーブルを使用してこの大きな次元空間を増やすこともできます。形状Sの特定の R テーブルをR(ɸ)で表します。このテーブルを簡単に変換すると、同じ形状の拡大縮小または回転したインスタンスを検出できます。たとえば、形状が s で拡大縮小され、この変換がT _sで表される場合、 T _s [R(ɸ)] = sR(ɸ)となり 、すべてのベクトルがsで拡大縮小されます。また、オブジェクトがθ回転し、この変換がT _θで表される場合、 T _θ [R(ɸ)] = Rot{R[(ɸ-θ)mod2π],θ}となります。 つまり、すべてのインデックスが – θ剰余 2π で増分され、適切なベクトルrが見つかり、次にそれらがθ回転されます。一般化ハフ変換の構成を説明するのに役立つもう 1 つの特性は、参照点の変更です。y -ỹ = zとなるように新しい参照点ỹ を選択する場合、R テーブルへの変更はR(ɸ)+ zで与えられます。つまり、テーブル内の各ベクトルに zが追加されます。

一対のエッジ ピクセルを使用して、パラメーター空間を縮小できます。R テーブルと上記のプロパティを使用して、各エッジ ピクセルは、a = (y, s, θ)の 4 次元累積空間で表面を定義します。異なる方向にある 2 つのエッジ ピクセルは、 θに対して同じ量だけ回転した同じ表面を表します。これらの 2 つの表面が交差する場合、交差する点は、形状の可能なパラメーターaに対応します。したがって、画像空間の 2 つの点を使用して、パラメーター空間の軌跡を 1 つの点に縮小することは理論的に可能です。ただし、パラメーター空間で 2 つの表面の交点を見つけるのは困難なため、ほとんどの場合、この方法は実行不可能です。

形状 S がサブパーツS ₁、S ₂、.. S _Nからなる複合構造を持ち、形状S、S ₁、S ₂、.. S _Nの参照点がそれぞれy、y ₁、y ₂、.. y _nである場合、スケーリング係数sと方向θに対して、一般化ハフ変換R _s (ɸ)は で与えられます。この変換に関する懸念は、参照の選択が精度に大きく影響する可能性があることです。これを克服するために、Ballard は、結果として得られるアキュムレータを複合スムージング テンプレートでスムージングすることを提案しました。複合スムージング テンプレートH(y)は、サブ形状の個々のスムージング テンプレートの 複合畳み込みとして与えられます。すると、改善されたアキュムレータはA _s = A*Hで与えられ、 A _sの最大値は形状の可能なインスタンスに対応します。 ${\displaystyle R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}}$${\displaystyle H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})}$

^{Heather と Yang [5]}は、グローバル Hough 変換は、互いに素なサブ領域のローカル Hough 変換の合計によって得られることに注目し、画像をサブ画像に再帰的に分割し、それぞれに独自のパラメータ空間を持たせ、 4 分木構造に編成する方法を提案しました。これにより、メモリのコストがわずかに増加しますが、線分の端点を見つける効率が向上し、ノイズの多い状況で線を抽出する際の堅牢性と信頼性が向上します。

実装では次の式を使用します。^[6]

${\displaystyle x=x_{c}+x'\ \ または\ \ x_{c}=xx'}$

${\displaystyle y=y_{c}+y'\ \ または\ \ y_{c}=yy'}$

${\displaystyle \cos(\pi -\alpha )=x'/r\ \ {\text{または}}\ \ x'=r\cos(\pi -\alpha )=-r\cos(\alpha )}$

${\displaystyle \sin(\pi -\alpha )=y'/r\ \ {\text{or}}\ \ y'=r\sin(\pi -\alpha )=r\sin(\alpha )}$

上記の式を組み合わせると次のようになります。

${\displaystyle x_{c}=x+r\cos(\alpha )}$

${\displaystyle y_{c}=y+r\sin(\alpha )}$

Rテーブルの構築

（0） Cannyエッジ検出器のようなエッジ検出アルゴリズムを使用してサンプル形状画像をエッジ画像に変換する

（１）参照点を選択する（例：（x _c、y _c））

（２）基準点から境界線まで線を引く

（３）ɸを計算する

（４）参照点（_xc、yc _）をɸの関数としてR(ɸ)テーブルに格納する。

検出：

（0） Cannyエッジ検出器のような任意のエッジ検出アルゴリズムを使用して、サンプル形状画像をエッジ画像に変換します。

（１）アキュムレータテーブルを初期化する：A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ]

（２）各エッジポイント（x,y）について

（2.1）勾配角ɸを使用して、Rテーブルからɸでインデックス付けされたすべての（α、r）値を取得します。

（２．２）各（α、ｒ）について、候補参照点を計算する。

x _c = x + r cos(α)

y _c = y + r sin(α)

（2.3）カウンターを増やす（投票）：

++A([[x _c ]][y _c ])

（３）物体輪郭の可能な位置はA[x _c ][y _c ]の極大値によって与えられる。

A[x _c ][y _c ] > Tの場合、物体の輪郭は(x _c , y _c )に位置する。

一般的なケース:

オブジェクトが回転Θと均一なスケーリングsを受けたと仮定します。

(x ' , y ' ) → (x '', y '')

x'' = (x ′ cos(Θ) – y ′ sin(Θ))s

y'' = (x ' sin(Θ) + y ' cos(Θ))s

x ′ をx″ に、y ′ をy″ に置き換えます。

x _c = x – x″ または x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y – y'' または y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

（１）アキュムレータテーブルを初期化する：A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ][q _min . . . q _max ][s _min . . . s _max ]

（２）各エッジポイント（x,y）について

(2.1) 勾配角ɸを用いて、R表からすべての(α,r)値を取得する。

（２．２）各（α、ｒ）について、候補参照点を計算する。

x ′ = r cos(α) の式

y ′ = r sin(α)

for( Θ = Θ _min ; Θ ≤ Θ _max ; Θ++ )

( s = s_最小; s ≤ s_最大; s++ ) の場合

x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

++(A[x _c ][y _c ][Θ][s])

（３）物体輪郭の可能な位置は、 A[x _c ][y _c ][Θ][s]の極大値によって与えられる。

A[x _c ][y _c ][Θ][s] > Tの場合、物体の輪郭は(x _c , y _c )に位置し、 Θ回転し、sだけ拡大縮小されています。

• 部分的またはわずかに変形した形状に対して堅牢です（つまり、遮蔽下での認識に対して堅牢です）。
• 画像内に追加の構造が存在しても堅牢です。
• ノイズに耐性があります。
• 同じ処理パス中に、図形の複数の出現を見つけることができます。

• オブジェクトの方向性とスケールを考慮する必要がある場合は、計算とストレージの要件が深刻になります。

Ballardは、エッジの方向情報を使用して計算コストを削減することを提案しました。SC-GHT（傾斜と曲率をローカルプロパティとして使用）など、多くの効率的なGHT手法が提案されています。^[7] DavisとYam ^[8]も、方向とスケール不変マッチングのためのMerlinの研究の拡張を提案しました。これはBallardの研究を補完しますが、Ballardのエッジ傾斜情報と複合構造の利用は含まれていません。

• ハフ変換
• ランダム化ハフ変換
• ラドン変換
• テンプレートマッチング
• 物体認識の概要

• 一般化ハフ変換のOpenCV実装 http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html
• 一般化ハフ変換のチュートリアルと実装 http://www.itriacasa.it/generalized-hough-transform/default.html
• 実用的な一般化ハフ変換の実装 http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html
• 一般化ハフ変換の FPGA 実装、IEEE デジタル ライブラリ https://ieeexplore.ieee.org/document/5382047/
• 一般化ハフ変換のMATLAB実装 http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform