ランダム化ハフ変換

ハフ変換は物体検出、コンピュータ ビジョンの多くの実装における重要なステップ、または画像からのデータ マイニングのための手法です。具体的には、ランダム化ハフ変換は古典的なハフ変換の確率的変形であり、曲線 (直線、円、楕円など) の検出によく使用されます^{[ 1 ]。}ハフ変換 (HT) の基本的な考え方は、画像内のすべての潜在的な曲線に対して投票手順を実装することであり、アルゴリズムの終了時に、画像内に存在する曲線は比較的高い投票スコアを持ちます。ランダム化ハフ変換 (RHT) は、解析曲線の幾何学的特性を利用して画像内のすべての非ゼロ ピクセルに対する計算コストの高い投票処理の実行を回避しようとする点で HT と異なり、そのため時間効率が向上し、元のアルゴリズムのストレージ要件が削減されます。

モチベーション

ハフ変換（HT）は曲線検出において広く用いられていますが、2つの大きな欠点があります。^{[ 2 ]}まず、画像内の非ゼロピクセルごとに、投票処理中に既存の曲線と冗長な曲線の両方のパラメータが累積されます。次に、累積配列（またはハフ空間）は経験的に事前に定義されます。より高い精度が求められるほど、より高いパラメータ解像度を定義する必要があります。これらの2つの要件は、通常、実際のアプリケーションでは大きなストレージ要件と低速化をもたらします。そこで、この問題に対処するためにRHTが考案されました。

実装

HTと比較すると、RHTは、一部の解析曲線が曲線上の特定の点数によって完全に決定できるという事実を活用します。例えば、直線は2点、楕円（または円）は3点によって決定できます。楕円検出の例は、RHTの基本的な考え方を説明するのに有用です。RHTのプロセス全体は、一般的に以下の3つのステップで構成されます。

1. ランダムに選択された点を楕円にフィットさせます。
2. 累積配列と対応するスコアを更新します。
3. 事前に定義されたしきい値よりも高いスコアを持つ楕円を出力します。

楕円フィッティング

楕円を定義する一般的な方程式は次のとおりです。 ${\displaystyle a(xp)^{2}+2b(xp)(yq)+c(yq)^{2}=1}$

制限付き：${\displaystyle ac-b^{2}>0}$

ただし、楕円は、楕円上の 3 つの点とそれらの点の 接線がわかっていれば、完全に決定できます。

RHTは、楕円上の3点をランダムに選択することから始まります。それらを、 、とします。最初のステップは、これらの3点の接線を求めることです。接線は、隣接するピクセルの小さなウィンドウに対して 最小二乗法を用いて直線を当てはめることで求められます。${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{3}}$

次のステップは、接線の交点を求めることです。これは、前のステップで求めた直線の方程式を解くことで簡単に行うことができます。交点を と、線分の中点をと ととします。すると、楕円の中心はとの交点に位置します。ここでも、交点の座標は直線の方程式を解くことで決定できます。ここでは簡潔にするため、詳細な手順は省略します。 ${\displaystyle T_{12}}$ ${\displaystyle T_{23}}$ ${\displaystyle X_{1}X_{2}}$ ${\displaystyle X_{2}X_{3}}$ ${\displaystyle M_{12}}$ ${\displaystyle M_{23}}$ ${\displaystyle T_{12}M_{12}}$ ${\displaystyle T_{23}M_{23}}$

前のステップで求めた楕円の中心の座標を とします。すると、中心は と を用いて原点に移動できるため、楕円方程式は次のように簡略化されます。 ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle x'=x-x_{0}}$ ${\displaystyle y'=y-y_{0}}$

${\displaystyle ax'^{2}+2bx'y'+cy'^{2}=1}$

ここで、、、の座標を上記の式に代入して、楕円 の残りのパラメータ、、を解くことができます。${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{3}}$

蓄積する

前の段階で決定された楕円パラメータを使用して、累積器配列をそれに応じて更新できます。従来のハフ変換とは異なり、RHTは「バケットのグリッド」を累積器配列として保持しません。代わりに、最初に新しく検出された楕円と累積器配列に既に保存されている楕円との類似度を計算します。類似度の計算には、さまざまな指標を使用できます。類似度が事前定義されたしきい値を超えている場合、累積器内の楕円を両方の楕円の平均に置き換え、スコアに1を加算します。そうでない場合は、この楕円を累積器内の空の位置に初期化し、スコアに1を割り当てます。

終了

候補楕円のスコアが閾値を超えると、その楕円は画像内に存在すると判断され（つまり、この楕円は検出された）、アルゴリズムが他の可能性のある楕円をより速く検出できるように、画像とアキュムレータ配列からその楕円を削除します。アルゴリズムは、反復回数が上限に達するか、すべての楕円が検出されると終了します。

RHTの擬似コード: ^{[ 3 ]}

while (楕円が見つかる、かつ最大エポックに達していない) { for (一定回数の反復) { 潜在的な楕円を見つけます。 （楕円がアキュムレータ内の楕円に似ている場合） 累計器内の 1 を 2 つの楕円の平均に置き換え、スコアに 1 を追加します。 それ以外 楕円をアキュムレータの空き位置にスコア 1 で挿入します。 } 最高のスコアを持つ楕円を選択し、それをベスト楕円テーブルに保存します。 画像から最適な楕円のピクセルを除去します。 アキュムレータを空にします。 } 

参考文献

1. DH Ballard、「ハフ変換の一般化による任意形状の検出」、パターン認識、第13巻、第2号、p.111-122、1981年
2. L. Xu、E. Oja、P. Kultanan、「新しい曲線検出方法：ランダム化ハフ変換（RHT）」、 Pattern Recog. Lett. 11、1990、331-338。
3. S. Inverso、「ランダム化ハフ変換を用いた楕円検出」、www.saminverso.com/res/vision/EllipseDetectionOld.pdf、2002年5月20日