目標

ハフ変換の概念を理解する。
画像内の直線を検出するためにそれを使う方法を学ぶ。
次の関数を学ぶ: cv.HoughLines(), cv.HoughLinesP()

理論

ハフ変換は、形状を数学的な形で表現できれば任意の形状を検出できる、よく使われる手法である。形状が多少欠けていたり歪んでいたりしても検出できる。直線についてどのように機能するかを見ていく。

直線は \(y = mx+c\) と表すことも、媒介変数表示として \(\rho = x \cos \theta + y \sin \theta\) と表すこともできる。ここで \(\rho\) は原点から直線までの垂直距離、\(\theta\) はこの垂線と水平軸がなす角度で、反時計回りに測られる（その向きは座標系の表現方法によって変わる。この表現はOpenCVで用いられている）。下の画像を確認してほしい:

image

したがって、直線が原点の下を通る場合、rho は正で角度は180未満になる。原点の上を通る場合は、180より大きい角度をとる代わりに、角度を180未満にとり、rho を負にとる。垂直な直線はすべて0度になり、水平な直線はすべて90度になる。

では、ハフ変換が直線に対してどのように機能するかを見ていこう。任意の直線はこれら2つの項 \((\rho, \theta)\) で表せる。そこでまず、2つのパラメータの値を保持するための2次元配列、すなわちアキュムレータを作成し、初期値を0に設定する。行を \(\rho\)、列を \(\theta\) とする。配列のサイズは必要な精度に依存する。角度の精度を1度にしたい場合は、180列が必要になる。\(\rho\) については、可能な最大距離は画像の対角線の長さである。したがって1ピクセルの精度をとると、行数は画像の対角線の長さにできる。

中央に水平線がある100x100の画像を考える。直線の最初の点をとる。その (x,y) の値はわかっている。さて直線の式に \(\theta = 0,1,2,....,180\) の値を代入し、得られる \(\rho\) を確認する。各 \((\rho, \theta)\) の組について、アキュムレータ内の対応する \((\rho, \theta)\) セルの値を1増やす。すると今度はアキュムレータ内で、セル (50,90) = 1 となり、他のいくつかのセルも増える。

次に直線上の2番目の点をとる。上記と同じことを行う。得られた \((\rho, \theta)\) に対応するセルの値を増やす。今度はセル (50,90) = 2 となる。実際に行っているのは \((\rho, \theta)\) の値に投票することである。直線上のすべての点についてこの処理を続ける。各点で、セル (50,90) は増分される、つまり投票されていく一方、他のセルは投票されることもされないこともある。こうして最終的に、セル (50,90) が最大の票数を持つことになる。したがってアキュムレータから最大票数を探すと、(50,90) という値が得られ、これはこの画像に原点から距離50、角度90度の位置に直線があることを示す。これは下のアニメーションでよく示されている（画像提供: Amos Storkey ）

これがハフ変換が直線に対して機能する仕組みである。単純である。下はアキュムレータを示す画像である。いくつかの位置にある明るい点は、それらが画像内に存在しうる直線のパラメータであることを示す。（画像提供: Wikipedia ）

OpenCVにおけるハフ変換

上記で説明したすべてはOpenCVの関数 cv.HoughLines() にカプセル化されている。これは単純に ( \((\rho, \theta)\) の値の配列を返す。\(\rho\) はピクセル単位で、\(\theta\) はラジアン単位で測られる。最初のパラメータである入力画像は2値画像でなければならないので、ハフ変換を適用する前にしきい値処理を行うかCannyエッジ検出を用いる。

次の関数を使用する: cv.HoughLines (image, lines, rho, theta, threshold, srn = 0, stn = 0, min_theta = 0, max_theta = Math.PI)

引数

image	8ビット、シングルチャンネルの2値入力画像。この画像は関数によって変更されることがある。
lines	検出された直線の出力ベクトル（cv.32FC2型）。各直線は2要素のベクトル (ρ,θ) で表される。ρ は座標原点 (0,0) からの距離である。θ は直線の回転角度（ラジアン）である。
rho	アキュムレータの距離解像度（ピクセル単位）。
theta	アキュムレータの角度解像度（ラジアン単位）。
threshold	アキュムレータのしきい値パラメータ。十分な票を得た直線のみが返される。
srn	マルチスケールハフ変換の場合、距離解像度 rho に対する除数である。粗いアキュムレータの距離解像度は rho で、正確なアキュムレータの解像度は rho/srn である。srn=0 かつ stn=0 の場合は、古典的なハフ変換が用いられる。それ以外の場合、これら両方のパラメータは正でなければならない。
stn	マルチスケールハフ変換の場合、距離解像度 theta に対する除数である。
min_theta	標準およびマルチスケールハフ変換において、直線を探索する最小角度。0 と max_theta の間でなければならない。
max_theta	標準およびマルチスケールハフ変換において、直線を探索する最大角度。min_theta と CV_PI の間でなければならない。

試してみる

確率的ハフ変換

ハフ変換では、2つの引数を持つ直線であっても多くの計算を要することがわかる。確率的ハフ変換 (Probabilistic Hough Transform) は、先に見たハフ変換の最適化である。すべての点を考慮するわけではない。代わりに、直線検出に十分なだけのランダムな部分集合の点のみをとる。ただししきい値を下げる必要がある。ハフ空間でハフ変換と確率的ハフ変換を比較した下の画像を参照してほしい。（画像提供 : Franck Bettinger's home page ）

image

OpenCVの実装は、Matas, J. と Galambos, C. と Kittler, J.V. による「Robust Detection of Lines Using the Progressive Probabilistic Hough Transform」[192]に基づいている。

次の関数を使用する: cv.HoughLinesP (image, lines, rho, theta, threshold, minLineLength = 0, maxLineGap = 0)

引数

image	8ビット、シングルチャンネルの2値入力画像。この画像は関数によって変更されることがある。
lines	検出された直線の出力ベクトル（cv.32SC4型）。各直線は4要素のベクトル (x1,y1,x2,y2) で表される。ここで (x1,y1) と (x2,y2) は検出された各線分の端点である。
rho	アキュムレータの距離解像度（ピクセル単位）。
theta	アキュムレータの角度解像度（ラジアン単位）。
threshold	アキュムレータのしきい値パラメータ。十分な票を得た直線のみが返される。
minLineLength	直線の最小長さ。これより短い線分は除外される。
maxLineGap	同一直線上の点を連結するために許容される点間の最大ギャップ。