ハフ直線変換

目標

本章では、

• ハフ変換の概念を理解する。
• 画像から直線を検出するために、それをどのように使うかを見ていく。
• 次の関数を見ていく: 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 )

これが直線に対するハフ変換の仕組みである。単純なので、Numpy を使って自分で実装することもできるだろう。下の画像はアキュムレータを示している。いくつかの位置にある明るい点は、それらが画像中の直線になりうる引数であることを表している。(画像提供: Wikipedia )

OpenCVにおけるハフ変換

上で説明したことはすべて OpenCV の関数 cv.HoughLines() にカプセル化されている。これは単に :math:(rho, theta)` 値の配列を返す。\(\rho\) はピクセル単位、\(\theta\) はラジアン単位で測られる。第1引数の入力画像は二値画像でなければならないため、ハフ変換を適用する前にしきい値処理を行うか Canny エッジ検出を使うこと。第2、第3引数はそれぞれ \(\rho\) と \(\theta\) の精度である。第4引数はしきい値で、直線とみなされるために得る必要のある最小票数を意味する。票数は直線上の点の数に依存することを覚えておくこと。したがってこれは検出すべき直線の最小長を表す。

import cv2 as cv
import numpy as np
 
img = cv.imread(cv.samples.findFile('sudoku.png'))
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
edges = cv.Canny(gray,50,150,apertureSize = 3)
 
lines = cv.HoughLines(edges,1,np.pi/180,200)
for line in lines:
    rho,theta = line[0]
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))
 
 cv.line(img,(x1,y1),(x2,y2),(0,0,255),2)
 
cv.imwrite('houghlines3.jpg',img)

以下の結果を確認すること:

image

確率的ハフ変換

ハフ変換では、2つの引数を持つ直線であっても多くの計算を要することがわかる。確率的ハフ変換は、これまで見てきたハフ変換の最適化版である。すべての点を考慮するのではなく、直線検出に十分なランダムな点の部分集合だけを取る。しきい値を下げるだけでよい。ハフ空間においてハフ変換と確率的ハフ変換を比較した下の画像を参照すること。(画像提供 : 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() である。新たに2つの引数を持つ。

• minLineLength - 直線の最小長。これより短い線分は除外される。
• maxLineGap - 線分を1本の直線とみなすために許容される線分間の最大間隔。

最も良い点は、直線の2つの端点を直接返すことである。前の場合は直線の引数しか得られず、すべての点を求める必要があった。ここではすべてが直接的で単純である。

import cv2 as cv
import numpy as np
 
img = cv.imread(cv.samples.findFile('sudoku.png'))
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
edges = cv.Canny(gray,50,150,apertureSize = 3)
lines = cv.HoughLinesP(edges,1,np.pi/180,100,minLineLength=100,maxLineGap=10)
for line in lines:
    x1,y1,x2,y2 = line[0]
 cv.line(img,(x1,y1),(x2,y2),(0,255,0),2)
 
cv.imwrite('houghlines5.jpg',img)

以下の結果を参照:

image

補足資料

1. Wikipedia のハフ変換