ハフ変換 (Hough Transform) による直線・円の検出

1. ハフ変換 (Hough Transform) による直線・円の検出とは [概要]

ハフ変換 (Hough Transform)とは，画像上のパラメトリックな基本図形(直線・円など)の輪郭検出を，パラメータ空間上の投票問題に置き換えることで上手く行う手法である [Hough, 1962], [Duda and Hart, 1972], [Hart, 2009]．図形の検出を，元の画像の空間上では行わず，代わりに「図形パラメータ空間」上で投票をおこない，最頻パラメータ値を探すことにより，元の画像上の基本図形(のパラメータ)を検出する．パラメータ空間でフィッティングをおこなうおかげで，画像上の直線・円のエッジが断片的であったり，ノイズ交じりであっても，頑健に基本図形(のパラメータ)を検出できるのが，利点である．

この記事では，ハフ変換の最もよく使う例である，ハフ変換による直線の検出の基本的な仕組みを紹介する(2節)．その類似形である円・楕円の検出についても簡単にだけ述べる(3節)．最後に一般化ハフ変換とハフフォレストについて，概要だけ述べる(4節)．

まずは，ハフ変換による『直線』の検出（2節）について，概要を述べたい（図１）．図形パラメータ$(a,b)$の空間を，累積空間（accumulator space）もしくはハフ空間（Hough space）とよぶ．

ハフ空間ではハフ投票（Hough voting）とよばれる累積処理を行う（2.3節）．エッジ画像上の直線の出現頻度を，ハフ空間上で対応する変換された関数（直線(2.2.1), 正弦関数(2.2.2)）の全座標に累積していく（図1-b）．累積配列の極値（最頻値）は，元画像側において，沢山のエッジ候補点を貫いている「画像上で尤も存在していそうな直線」のパラメータである．よって，累積配列の局所的な極値を検出することで，最終的な直線検出結果（のパラメータ）として推定できる．（※ 直線検出の場合，直線パラメータを推定するだけなので，端点までは推測しないことに注意）

図1は，直線ハフ変換の入出力と，検出を行う累積空間を離散化した累積配列を可視化したものである(※)．

※ 使用した入力画像は，直線が多く含まれる『嵐電の嵐山駅駅前の交差点』を，筆者が撮影した画像である．

このように『パラメータ空間の最頻値として，画像上の図形を検出する』仕掛けが，ハフ変換の肝となるアイデアである．直線はパラメータ2個であったが，円・楕円だとパラメータが3個・4個に増える．しかし，それらの場合も，直線検出と同様に，ハフ変換を実行できる (3節)．

ハフ変換の応用例としては，画像上の直線検出が特によく用いられてきた．例えば，屋外画像群からの建築物の3D再構成で，直線検出が関心点 (Interest point)と組み合わせて「(人工的な)物体・壁の輪郭と境界」を検出するための『前処理』に活躍する．逆に言うと，古典的ハフ変換は直線・円・楕円など，人がつくった輪郭を持たない図形は，検出しづらいかった．

そこに，一般化ハフ変換(Hough Transform)が登場し，テンプレートマッチングを用いて『任意の図形』を検出できるアルゴリズムに拡張化・一般化がされた [Ballard, 1981]．一般化ハフ変換により，ハフ投票で検出可能図形のバリエーションが一気に増えたことにより，コンピュータビジョンでは，ハフ変換および一般化ハフ変換が，更に広く応用・研究されていくようになる（4節）

この記事では，一般化ハフ変換やその後の展開については，概要の紹介にとどめて別の記事へと分割する．また「機械学習を用いたハフ投票 (ハフフォレストなど)」についても，この記事では対象外とし，概要のみ述べる (4節)．

1.1 記事の構成

2節以降は，以下の構成で，ハフ変換による直線と円・楕円の検出手法を紹介する：

2節ハフ変換による直線の検出
- 2.1　ハフ変換の全体像
- 2.2 モデル
  - 2.2.1 元の『傾き-切片』モデル
  - 2.2.2 標準的な『角度-半径』モデル
- 2.3 アルゴリズム（離散的な累積配列による標準的手法）
- 2.4 アルゴリズムの改善（サブピクセル化）
3節ハフ変換による円・楕円の検出
4節一般化ハフ変換(の概要)と，その後の機械学習をもちいた応用
5節まとめ

２. ハフ変換(Hough Transform)による直線検出

2節では，ハフ変換による『直線』の検出について述べていきたい．次の3節で，その類似例としてハフ変換をもちいた『円』の検出について述べる．

まず2.1節でハフ変換のアイデアを述べることで，まずおおまかな全体像を捉える．その後，2.2節で『直線モデル』について，2.3節では累積配列へのハフ投票を用いる『アルゴリズム』について，それぞれ分離して述べる．また 2.4節では，古典的なハフ投票（2.3節）の，『サブピクセル精度への改善』について述べる．

2.1 ハフ変換のアイデアと全体像

まず先に，1960年代や70年代の当時の目線で，画像から直線を検出することを考えてみたい．画像の空間フィルタリングや，Cannyエッジ検出で得た『エッジ画像』を入力として，直線を検出したい．しかし，エッジ画像上のエッジ（境界線）は，エッジ間がよく途切れて断片的であり，直線周辺には関係のない細かなノイズも多い．そのせいで，例えば最適化手法で直線を当てはめるアプローチでは，安定して直線検出することができない．また，RANSAC(1981年に考案)もまだ登場してもいない時代である．よって，画像から直線を安定して検出するには，何か新しいアイデアが必要であった．

そんな中，ハフ変換 [Hough, 1962], [Hart, 2009]では，エッジ（境界）上の直線候補の点を，直線パラメータ空間上の直線へ変換して投票し，最も頻度の高い直線パラメータを見つけることにより，直線・円を検出するという発想を考案した(図2)．これは端的に言えば「空間軸と図形パラメータの入れ替えによる，図形と点の相互変換」である．

ハフ変換 [Hough, 1962]では，直線のパラメータ$(a,b)$「切片-傾き」のパラメータ空間を用意し，(青色の直線上の全点に)投票を行う(図2-a,b)．投票をおこなうパラメータ空間のことを，ハフ空間(Hough space)もしくは 累積空間(accumulator space)と呼ぶ．ただし実際は，ハフ空間が連続空間のままだと計算しづらいので，2軸とも離散化を行ってグリッド化した累積配列(accumulator array)(図1-c)の各座標において，最頻パラメータを見つけるための投票を行う(※ 詳しくは2.3 節)．

ハフ変換では，エッジ画像上の点を候補点$(x_i, y_i)$として，それらの$(x_i, y_i)$をパラメータ空間側の値$(a,b)$に変換する（図2 -a）そして，候補点に対応したパラメータ候補$(a,b)$による関数 $b = f(a) = – x_i a + y_i$（直線）の全点に，登場回数（頻度）を累積していく（図2-b）．最後に，候補が全て投票され終わった累積配列から，極大点を検出することで，直線パラメータを確定して終了する（図2-c）．図2では，画像空間における座標変数$(\textcolor{blue}{x},\textcolor{blue}{y})$を青色で，パラメータ空間の座標変数$(\textcolor{red}{a},\textcolor{red}{b})$を赤色で，それぞれ表記することで，2者を区別しやすいように描いた．

元の画像空間における『直線』が，ハフ空間では『点』に対応する．ハフ空間での投票を行うと，同一の直線上の各点におけるエッジ点をハフ空間で，一定以上の投票があった点を，画像上にある直線（のパラメータ）として最終的に出力できる．

2.2 モデル：直線の表現

元の [Hough 1962] では素直な「傾き-切片」の直線モデルを用いていた（図3）．しかし素直な直線モデルには，後述（2.2.1 節）のような問題もあるので，[Duda and Hart, 1972] では「角度-半径（angle-radius）」で直線を表現することで，改善された．

これは『アルゴリズム的な理由』によるパラメータ空間の変更なのであるが，その話を2.2節でのちほど分離して紹介したい．よってこの 2.2節では，先に2つの直線モデルだけを紹介する．その後，2.3節でアルゴリズムについてだけ紹介した．

2.2.1 元の「傾き-切片」直線モデル

オリジナルのハフ変換 [Hough 1962] では，画像平面$(x,y)$上の直線のモデルとして，傾き$a$と切片$b$の２つのパラメータから構成される（素直な）「傾き−切片」直線モデルを用いた（図3 左側）：

\[
y_i = a x_i +b　\tag{2.1}
\]

エッジ画像上の候補点 $(x_i, y_i)$ を，逆にパラメータ空間（ハフ空間）では，直線の傾き$x_i$と切片$y_i$に用いる（図２右側）：

\[
b = – x_i a + y_i　\tag{2.2}
\]

この，式(2.2)による$(a,b)$ハフ空間において，各候補点$(x_i,y_i)$ (図２左の青の点)をハフ変換した直線（図2 右図の青の直線）を用いて，ハフ投票を（2.2節）をおこなうことで直線の検出が達成できる．

Houghによる直線モデルの課題

「傾き-切片」の直線表現には，傾き$a$が無限大になってしまうなど，$(a,b)$がunboundな表現であることから生まれる問題があった．$ – \infty \geq a \geq \infty$であるので，累積配列も大きくなり，メモリを大量に確保する必要がある．よって，代わりに「角度-半径」直線モデル [Duda and Hart] によるハフ変換をもちいれば，パラメータが2個ともが bound な値になり，なおかつ，狭い値の範囲に限定できる利点が出てくる．

また，「傾き-切片」直線モデルには，ハフ空間も直線なので，空間軸と並行となった場合に，複数の対応づけできる直線候補が同時に存在してしまい，一つの点に定めることができなくなる問題があった．それが次節の「角度-半径」モデルの登場にｙり，パラメータ空間上の表現が sinカーブ（図3 右図）に変わったおかげで，常に一対一で対応づけできるようになる．

2.2.2 標準的な「角度-半径」直線モデル

ハフ変換「角度−半径」直線モデル — 図4. DudaとHartによる直線のパラメータ化「角度−半径」

[Duda and Hart, 1972] は，画像上の直線を「角度-半径」直線モデルによりパラメータ化をおこなうハフ変換をあらたに提案した（図4）．[Duda and Hart, 1972] では，以下の式のように，原点から直線へ下ろした垂線の「角度-半径」$(\rho, \theta)$を用いた極座標表現で表す直線のモデルを，画像の$x-y$空間上の直線表現として用いる（図4 左図）：

\begin{equation}
x_i \cos(\theta)-y_i \sin(\theta) + \rho = 0 \tag{2.3}
\end{equation}

式(2.3) の表現は，積分幾何における「ヘッセの標準形 (Wikipedia)」に相当する [Hart, 2009]（[Duda and Hart, 1972]は「半径」と論文中で表現しているが，半径のことを「距離（distance）」と呼ぶ人も多い）

この際に， $\theta \in [0, \pi ), r \leq 0$ にそれぞれ制限すれば，画像上の特定の１つの直線に対応した $(\rho, \theta)$ を一意に定めることができ，[Hough 1962]のように対応づけの曖昧性が生まれなくて済む．言い換えると，ハフ投票で求まったパラメータ空間の1点を，元の画像空間における１つの直線のみへ対応づけできるようになった．

パラメータ空間で使用する際は，以下のように$\theta$が引数となる$(\theta,\rho)$空間における正弦関数型に変形し，その曲線上の累積配列の各点$(\rho, \theta)$に，頻度を投票する（図4 右図）：

\begin{equation}
\rho = -x_i \cos(\theta) + y_i \sin(\theta)　\tag{2.4}
\end{equation}

画像上のハフ変換による直線検出では，[Duda and Hart, 1972] 登場以降は，この式(2.3)，式(2.4)の「角度-半径」直線モデルが，標準的に使われるようになった．例えばOpenCVのcv2.HoughLines() では，この [Duda and Hart, 1972] の直線モデルが用いられている．

2.3 アルゴリズム：ハフ投票と非極大値抑制（最頻値の検出）

まず，$\bm{I}[x,y]$ を入力画像とし，$\bm{H}[\rho, \theta]$ は累積配列（投票結果を入れる2次元配列．図1-c）とする．$\bm{H}[\rho, \theta]$ は離散グリッドであるので画像として用意し，横軸$\theta$の範囲を$[\theta_{\min} = 0 , \theta_{\max})$とし，縦軸$\rho$の範囲を$[0° , 180°)$とする．

このときハフ変換では，以下の2段階の手順「1. ハフ投票 -> 2. 非極大値抑制（Non maximal suppression）」を通じて，画像上の直線を検出できる：

投票（図4-a）(図1-a,b)：エッジ画像において，N個のエッジ上の点$(x_i, y_i)$から式(2.3)で計算できる直線パラメータ$(\rho, \theta)$を，パラメータ候補として，ハフ空間上の対応する離散グリッド$(\rho, \theta)$に投票する．
非極大値抑制（図4-b）：投票が終わった累積配列（=ハフ空間の画像）から，非極大値抑制をおこなう．その結果，局所的な最大値$(\rho_{max}, \theta{_max})$が最頻パラメータであるので，これが元画像の直線パラメータとして出力できる．

上記の手順を，疑似アルゴリズムとして表すと，以下のようになる：

累積配列 $\bm{H}[\rho, \theta]$ の全要素を，0で初期化．
投票（図3-a）の実施．
- for $Ｎ$個の各エッジ点 $\bm{I}[x_i,y_i]$ において：
  - for 各 $\theta = \{ \theta_{\min} ,\ldots, \theta_{\max} \}$ において：
    1. $\rho = x \cos(\theta) + y \sin(\theta)$ 式(2.3)
    2. $\bm{H} [\rho ,\theta] += 1$ （式2.3の曲線上にある各グリッドに，1票を投票）
NMS(非極大値抑制) (図3-b)：
- 累積配列から $H[\rho, \theta]$ の極大点をNMS(非極大値抑制)で検出し，出力結果とする．

以上の手順で，累積配列から得られた最頻値（局所のピーク値）である $(\rho, \theta)$の集合が，出力の直線として検出できる（図1-d）．

2.3.1 効率化：エッジ傾きを直接使用

[Duda and Hart 1972]では，上の手順のように，$\rho$の値を式(2.3)により毎回変換して算出していた．それを，[Gorman and Clowes, 1976]では，式(2.3)は用いずに，エッジ画像$\bm{E}(x,y)$（の候補点$(x,y)$におけるの傾きを直接 $\rho $ の値として使う効率化が提案された．

エッジ画像の各画素における傾きの値は，前処理のCannyエッジ検出で取得済みなので，式(2.3)の処理が不必要になり，計算高速化が達成でできる

3. ハフ変換 (Hough Transform)による円の検出

ハフ変換では円・楕円の検出も可能である．パラメタライズできる図形であれば，2節の直線検出と全く同じの手続きで，円と楕円も検出できる．（2節と同様の描き方で）図５には，円のハフ変換における画像空間上の円のモデルと，その円上にある候補点$(x_i, y_i)$と（図５左図），それに対応する3次元ハフ空間における投票の様子を示した（図５右図）．

直線検出と異なるのは，図形のモデルが円になるのと，そのパラメータ数が円なので3個に増える点だけである．ハフ空間が3次元空間になる（図５）．円のパラメータは，中心$(a,b)$と半径$r$で表せるので，ハフ空間の累積配列は3次元の配列$\bm{H}[a,b,r]$ を用意する．

ちなみに楕円を検出する場合は，楕円のパラメータは4つなので，4次元の累積配列で行う（この記事では省略）

そして，ハフ空間では，画像空間の座標$(x,y)$を中心とした半径$r$の円に変換して，あとは直線検出と同様のハフ投票をおこなう．ただ，画像上のある候補点$(x_i,y_i)$に対して処理を行いたいが，半径$r$の値が未知であるので，累積空間では$(x_i,y_i)$を中心とした半径$r$の円周上のすべての点に投票することになる（図5 右図）．すなわち，図$(x_i,y_i)$を先端とする逆さの円すいの表面の全点に投票する（= 中心を$(x_i,y_i)$とした半径$r$の円周上の点を，全$r$の値においてたどった円すい表面）．投票が終わったあとは，最頻値 $(a,b,r)$を検出すれば，円が検出できる．

円検出の場合の累積配列への投票の様子は，以下の動画で見ることができる：

4. 一般化ハフ変換 (Generalized Hough Transform)とその後の機械学習をもちいた応用

[Ballard 1981]は，ハフ変換を，テンプレートマッチングにより任意の図形を検出できる手法へ一般化した一般化ハフ変換（Generalized Hough Transform）を提案した．この手法の登場により，これまでは「直線」や「円・楕円」に限られていたハフ変換の適応可能図形が，『任意の図形』に広がり，ハフ変換を応用できる幅が一気に広まった（※ 一般化ハフ変換について，詳しくは別の記事にて述べる）．

画像認識分野において，パターン認識・機械学習の隆盛以降も，『機械学習と組み合わせた一般化ハフ投票』の活用・研究が継続している．まず，画像からの物体検出手法であるハフフォレスト（Hough Forest） [Gall and Lempitsky, 2013] が提案された．ハフフォレストでは，各パーツからの相対的中心位置ベクトルをハフ投票し，ランダムフォレストに学習済みの前景物体を検出する（歩行者検出など）．他の物体検出手法はBoundingboxを出力するが，ハフフォレスト系統の手法は，一般化ハフ変換と同じく図形の境界を検出する手法なので，「物体境界」と「おおまかなパーツマスク集合」を出力できることは利点である．パーツ手法なので，遮蔽にも強い．

またディープラーニング登場後も，ハフフォレストを3D点群処理に発展した『ディープ3Dハフ投票 による3D物体検出』（[Charles et al., 2019] など）などが，引き続き研究・応用されている．とりわけ，CT・MRIなどの医用3D画像処理や，3Dデプスセンサーを入力としたロボットビジョン点群処理での研究・応用が盛んである．

5. まとめ

この記事では，古典的なハフ変換(Hough Transform)による直線検出と，円検出について主に述べた．ハフ変換では直線・円の輪郭候補であるエッジ画像上の候補点のパラメータを，パラメータ空間側で累積配列に投票することで，図形の最頻パラメータを発見する．元画像で直線・円が断片的なエッジであったり，周辺にノイズのエッジが多くとも，頑健に図形を検出できるので，実用的なアルゴリズムである．とりわけ，前処理として直線検出が必要なコンピュータビジョン処理全般で，古典的なハフ変換が用いられてきた．今日でも(線や円の検出機会が未だに多い) ロボットビジョン・マシンビジョンなどにおいて，有用な仕組みであり続けている．

その後，一般化ハフ変換の登場で，テンプレートマッチングを用いて任意の図形をハフ投票で検出できるようになり，適用対象の幅が広がった．ただしハフ変換は，古典的なルールベースの手法であるので，画像環境ごとにパラメータ調整は必要であり，連続的に環境変化するリアルタイム処理環境には通用しないことがある．

また，ハフ投票を機械学習と組み合わせた手法も登場し，物体検出・前景セグメンテーション目的の研究 (特に3D点群が対象)が行われている．

参考書籍

Computer vision: models, learning, and inference, Prince, Simon JD., Cambridge University Press, 2012.
Concise Computer Vision: An Introduction into Theory and Algorithms , Reinhard Klette, 2014.
ディジタル画像処理 [改訂第二版], ディジタル画像処理編集委員会, 2020.
- 11-5 図形要素検出
  - 11-5-1 ハフ変換 (p252)

References

[Ballard, 1981] D.H. Ballard, “Generalizing the Hough Transform to Detect Arbitrary Shapes”, Pattern Recognition, Vol.13, No.2, p.111-122, 1981
[Duda and Hart, 1972] Duda, Richard O., and Peter E. Hart. “Use of the Hough transformation to detect lines and curves in pictures.” Communications of the ACM 15.1 (1972): 11-15.
[Charles et al., 2019] Qi, Charles R., Or Litany, Kaiming He, and Leonidas J. Guibas. “Deep hough voting for 3d object detection in point clouds.” In CVPR 2019.
[Gall and Lempitsky, 2013] Gall, J., & Lempitsky, V. (2013). Class-specific hough forests for object detection. In Decision forests for computer vision and medical image analysis (pp. 143-157). Springer, London.
[Hart, 2009] Hart, Peter E. “How the Hough transform was invented [DSP History].” IEEE Signal Processing Magazine 26.6 (2009): 18-22.
[Hough 1962] P. V. C. Hough, “Method and means for recognizing complex patterns,” U.S. Patent 3 069 654, Dec. 18, 1962.
[Gorman and Clowes, 1976] O’gorman, Frank, and M. B. Clowes. “Finding picture edges through collinearity of feature points.” IEEE Transactions on computers 25.04 (1976): 449-456.

CVMLエキスパートガイド

「探求力の向上」を支援する拠点サイト