Circle_Hough_Transform
円ハフ変換 (CHT)は、不完全な画像内の円を検出するためにデジタル画像処理で使用される基本的な特徴抽出手法です。円の候補は、ハフ パラメーター空間で「投票」し、アキュムレータ マトリックスで極大値を選択することによって生成されます。
ハフ変換の特殊化です。
コンテンツ
1 仮説
1.1 既知の半径 R を持つパラメーターを見つける 1.2 既知の半径 R を持つ複数の円 1.3 アキュムレータ行列と投票 1.4 半径が不明な円パラメータを見つける
2 例
2.1 靴のプリントで円を見つける
3 制限事項
4 拡張機能
4.1 適応ハフ変換
5 応用
5.1 人数カウント 5.2 脳動脈瘤の検出
6 実装コード
7 こちらもご覧ください
8 参考文献
仮説
2 次元空間では、円は次のように記述できます。(X − a ) 2+(y − b ) 2= r 2( 1 ) { left(xaright)^{2}+left(ybright)^{2}=r^{2} (1)}
ここで、(a，b) は円の中心、r は半径です。2D ポイント (x，y) が固定されている場合、パラメーターは (1) に従って見つけることができます。パラメータ空間は 3 次元 (a、b、r) になります。また、(x， y) を満たすすべてのパラメーターは、頂点が (x， y， 0) にある逆直角円錐の表面上に3D 空間では、円パラメータは、2D 円上の点によって定義される多くの円錐面の交点によって識別できます。このプロセスは 2 つの段階に分けることができます。最初の段階では、半径を固定してから、2D パラメータ空間で最適な円の中心を見つけます。第 2 段階では、1 次元のパラメーター空間で最適な半径を見つけます。
既知の半径 R を持つパラメーターを見つける
半径が固定されている場合、パラメータ スペースは 2D (円の中心の位置) に縮小されます。元の円の各点 (x， y) に対して、(1) に従って半径 R で (x， y) を中心とする円を定義できます。パラメータ空間内のそのようなすべての円の交点は、元の円の中心点に対応します。
元の画像 (左) の円上の 4 つの点を考えてみましょう。円のハフ変換を右に示します。半径は既知であると仮定されていることに注意して元の画像の 4 つの点 (白色点) の (x，y) ごとに、(x， y) を中心とする半径 r のハフ パラメーター空間の円を定義できます。交点を追跡するためにアキュムレータ行列が使用されます。パラメータ空間では、円が通過するポイントの投票数が 1 増加します。すると極大点（右図中央の赤い点）が求まります。最大値の位置 (a， b) は元の円の中心になります。
既知の半径 R を持つ複数の円
同じ手法で同じ半径の複数の円を見つけることができます。
アキュムレータ行列 (右の図) には、少なくとも 3 つの極大点があることに注意して
アキュムレータ行列と投票
実際には、アキュムレータ行列を導入して、パラメーター空間で交点を見つけます。まず、グリッドを使用してパラメータ空間を「バケット」に分割し、グリッドに従ってアキュムレータ行列を生成する必要がアキュムレータ行列の要素は、パラメータ空間内の対応するグリッド セルを通過する、パラメータ空間内の「円」の数を示します。この番号は「投票番号」とも呼ばれます。最初は、行列のすべての要素はゼロです。次に、元の空間の各「エッジ」ポイントに対して、パラメーター空間で円を定式化し、円が通過するグリッドセルの投票数を増やすことができます。このプロセスは「投票」と呼ばれます。
投票後、アキュムレータ行列で極大値を見つけることができます。極大値の位置は、元の空間の円の中心に対応しています。
半径が不明な円パラメータを見つける
パラメータ空間が 3D であるため、アキュムレータ マトリックスも 3D になります。可能な半径を反復できます。半径ごとに、前の手法を使用します。最後に、3D アキュムレータ行列の極大値を見つけます。アキュムレータ配列は、3D 空間の A である必要が投票は各ピクセル、半径、シータ A += 1 に対して行う必要があります
アルゴリズム:
各 A = 0;
画像のフィルタリング アルゴリズムを処理して Gaussian Blurring、画像をグレースケールに変換 ( grayScaling )、Canny operatorを作成します。Canny operator は画像にエッジを与えます。
アキュムレータで可能なすべてのサークルに投票します。
アキュムレータ A の極大投票円は、円にハフ空間を与えます。
Accumulator の最大投票円は円を与えます。
最良の候補のインクリメント :
各 A = 0; // 最初はゼロで埋め、3D マトリックスをインスタンス化します 各セル (x，y)
For each theta t = 0 to 360 // 可能な theta 0 から 360
b = y – r * sin(t * PI / 180); //中心の極座標 (ラジアンに変換)
a = x – r * cos(t * PI / 180); //中心の極座標 (ラジアンに変換)
A +=1; //投票
終わり 終わり
例
靴のプリントで円を見つける
元の画像 (右) は、最初にしきい値とガウス フィルターを使用してバイナリ イメージ (左) に変換されます。次に、キャニー エッジ検出を使用してエッジ (中間) が検出されます。この後、すべてのエッジ ポイントが Circle Hough Transform によって使用され、基になる円構造が検出されます。
制限事項
CHT のパラメータ空間は 3 次元であるため、大量のストレージと計算が必要になる場合がより大きなグリッド サイズを選択すると、この問題を改善できます。
ただし、適切なグリッド サイズを選択するのは困難です。グリッドが粗すぎると、多くのまったく異なる構造が単一のバケットに対応するため、投票の大きな値が誤って取得される可能性がグリッドが細かすぎると、構造が見つからない可能性がこれは、正確に整列されていないトークンから得られた投票が異なるバケットに配置され、バケットに大きな投票がないためです。
また、CHT はノイズに対してあまり堅牢ではありません。
拡張機能
適応ハフ変換
J. Illingworth と J. Kittler は、ハフ変換を効率的に実装するためにこの方法を導入しました。AHT は、小さなアキュムレータ配列と、柔軟な反復的な「粗いものから細かいものへ」の蓄積と検索戦略のアイデアを使用して、ハフ パラメーター空間の重要なピークを識別します。この方法は、ストレージと計算の両方の要件において、標準のハフ変換の実装よりも大幅に優れています。
応用
人数カウント
頭は画像の円に似ているため、CHT を使用して画像内の頭を検出し、画像内の人の数を数えることができます。
脳動脈瘤の検出
修正ハフ円変換 (MHCT) は、デジタル サブトラクション アンギオグラム (DSA) から抽出された画像に使用され、動脈瘤の種類を検出して分類します。
実装コード
標準ハフ変換による円検出 、 Amin Sarafraz、Mathworks (File Exchange)
Hough Circle Transform、OpenCV-Python チュートリアル (archive.org のアーカイブ バージョン)
こちらもご覧ください
ハフ変換
一般化ハフ変換
ランダム化されたハフ変換
講義 10: Hough Circle Transform、Harvey Rhody、Chester F. Carlson Center for Imaging Science、Rochester Institute of Technology （2005 年 10 月 11 日)
参考文献
^ J. Illingworth および J. Kittler、「The Adaptive Hough Transform」、PAMI-9、Issue: 5、1987、pp 690-698 ^ Hong Liu、Yueliang Qian、Shouxun Lin、「監視ビデオでハフ円変換を使用して人を検出」 ^ ミトラ、ジュビンら。エル。「修正ハフ円変換を用いた脳動脈瘤検出のための階層山のピークトレッキング.」ELCVIA コンピューター ビジョンおよび画像解析に関する電子レター 12.1 （2013)。http://elcvia.cvc.uab.es/article/view/v12-n1-mitra-chandra-halder”