ハフ変換による直線検出

目的

このチュートリアルでは
  • ハフ変換の概念を学びます．
  • 画像中から直線検出をするためにハフ変換をどのように使うか学びます．
  • 以下の関数の使い方を学びます: cv2.HoughLines(), cv2.HoughLinesP()

理論

ハフ変換は数式で表現できる形状を検出するための一般的な方法です．形状の一部が破損，劣化していたとしても検出できます．ここでは直線検出のためにどのようにハフ変換を使うかみていきます．

直線は y = mx+c もしくは \rho = x \cos \theta + y \sin \theta と表せrます．ここで \rho は原点から直線までの距離， \theta は直線の法線と横軸の成す角を反時計回りに表します(この方向は座標系の表現次第で変わります．この表現はOpenCVで使われている者です)．以下の画像を確認してください．:

もしも直線が原点の下を通過するのであればrhoは正の値，角度は180度未満になります．原点の上を通過する場合は角度は180より大きい値になるのではなく負の値になります．またrhoは負の値になります．縦軸に平行な直線は角度が0度，横軸に平行な直線は角度が90度になります．

それではハフ変換を直線検出にどのように使うか見ていきましょう．上式が示すように，あらゆる直線は二つのパラメータ (\rho, \theta) を使って表せます．まず初めに，この二つのパラメータを保持するために2次元配列もしくは積算機を用意し，初期値として0を与えます．行は \rho ，列は \theta を意味します．配列のサイズはあなたが必要とする精度に依存します．角度の精度を1度単位で臨むのであれば180列必要になります． \rho については画像の直交方向の長さを最大値とすればよいでしょう．1画素単位での精度が必要であれば行の数を画像の対角方向の長さに設定します．

解像度が100x100の画像の中心に横方向の直線があると想像してください．直線上の最初の点に対して，その座標(x,y)を調べます．直線を表す式にこの座標を代入し， \theta = 0,1,2,....,180 に対して \rho の値を計算します．パラメータの各ペア (\rho, \theta) に対して，2次元配列の対応する (\rho, \theta) のセルをインクリメントします．積算機の中では，セル (50,90) = 1 等となります．

同じ直線上の二つ目の点に対しても上記と同様の処理を行います．計算した (\rho, \theta) に対応するセルをインクリメントします．ここでセル (50,90) = 2 となります．ここで何をしているかと言うと， (\rho, \theta) に対する投票です．この処理を直線上の全点に対して行います．各点でセル(50,90)に対して投票される一方，他のセルへの投票は増えません．このようにして最終的にセル(50,90)が最大投票数を得ます．積算機中の最大投票数を調べれば(50,90)のセルが見つかり，これは距離が50，角度が90度の直線が検出できたことを意味します．この投票処理を以下のアニメーションに示します (画像引用: Amos Storkey )．

Hough Transform Demo

これがハフ変換を使った直線検出の仕組みです．単純なアルゴリズムなので，自分自身で実装する事もできるでしょう．以下の画像は積算機を可視化したものです．明るい場所が画像中の可能性がある直線に対応するパラメータの場所を表しています(画像引用: Wikipedia )．

Hough Transform accumulator

OpenCVを使ったハフ変換

上述したアルゴリズムはOpenCVの cv2.HoughLines() 関数で実装されています．返戻値は (\rho, \theta) の配列です． \rho は画素単位で計測され， \theta はradian単位で計算されます．第1引数は入力画像であり，2値画像でなければなりません．あらかじめ2値化やエッジ検出をした画像を使うと良いでしょう．第2,3引数にはそれぞれ \rho と \theta の精度を指定します．第4引数は，直線とみなされるのに必要な最低限の投票数を意味するしきい値です．投票数は直線上の点の数に依存する点を覚えておいてください．つまり，この引数は検出可能な線の長さの最小値となります．

import cv2
import numpy as np

img = cv2.imread('dave.jpg')
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray,50,150,apertureSize = 3)

lines = cv2.HoughLines(edges,1,np.pi/180,200)
for rho,theta in lines[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))

    cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)

cv2.imwrite('houghlines3.jpg',img)

以下の結果を見てください:

Hough Transform Line Detection

確率的ハフ変換

上記のハフ変換は，たった二つのパラメータを計算するのに大量の計算を必要とします．確率的ハフ変換はハフ変換の最適化を行ったものとみなせるでしょう．全画素を使って計算するのではなく，直線検出をするのに十分な点を画像中からランダムに洗濯して計算します．我々がするべき作業はしきい値を減らすことのみです．以下の画像はハフ空間でハフ変換と確率的ハフ変換を比較した画像になります(画像引用 : Franck Bettinger’s home page )．

Hough Transform and Probabilistic Hough Transform
OpenCVの実装は，Matas, J. and Galambos, C. and Kittler, J.V.らが提案した漸進的確率的ハフ変換を使ってロバストな直線検出を行います．関数は二つの引数を入力とする cv2.HoughLinesP() です．
  • minLineLength - 検出する直線の最小の長さを表します．この値より短い線分は検出されません．
  • maxLineGap - 二つの線分を一つの直線とみなす時に許容される最大の長さを表します．この値より小さいギャップを持つ日本の直線は一つの直線とみなされます．

最良の方法は直線の両端点を返すことです．前の例では直線のパラメータを取得したため，直線上の全点を計算する必要がありました．今回は全てが直接的で単純です．

import cv2
import numpy as np

img = cv2.imread('dave.jpg')
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray,50,150,apertureSize = 3)
minLineLength = 100
maxLineGap = 10
lines = cv2.HoughLinesP(edges,1,np.pi/180,100,minLineLength,maxLineGap)
for x1,y1,x2,y2 in lines[0]:
    cv2.line(img,(x1,y1),(x2,y2),(0,255,0),2)

cv2.imwrite('houghlines5.jpg',img)

以下の結果を見てください．:

Probabilistic Hough Transform

課題