画像から直線を検出するために用いられるHough(ハフ)変換ですが、その意味を理解していこうと思います。一般的には説明が省略されるような式の変換も真面目にやってみようと思います。
ハフ変換
ハフ変換は、デジタル画像処理で用いられる直線の検出を行うための変換になります。直線だけでなく、円や任意の形態の検出にも使えるらしい。が今回は直線を検出するための処理に関して解説をしようと思います。
とある座標上の1点を通る直線は無限に存在します。そりゃそうですよね、角度を変えれば無限に存在しえます。
一つ一つの直線に一意の(a,b)による\(y=ax+b\)の式が与えられます。無限だとわかりにくいので例えば図のように12本としてみます。
別の点を考えます。
同じように12本の直線が引けますが、2点を通る直線は1つだけになります。その(a,b)がこの2点を通る直線を表す式になります。他の11本では共通の(a,b)が現れません。
直線の候補となる点群すべてに対して(a,b)を求めると、共通して通る(a,b)がその点群の数だけ求まります。10個の点で計算すると同じ(a,b)が10回現れ、逆にそれ以外の(a,b)は1度きりしか現れません。
1つの(a,b)のペアで表現できる直線は1種類しかありません。最頻の(a,b)で最も多くの点を通る1本の直線が選ばれます。
このようにすべての直線候補点において、12本の(a,b)のカウントを行い、ヒストグラムを取り最大値を求めれば画像の中の直線を求めることができる。というわけです。（このカウントの事を投票とか言ったりもします。）
概念としてはこんなところです。
直線の式はここで説明したような、いわゆる\(y=ax+b\)の形が一般的ですが、ハフ変換では少し形を変えた式が用いられています。
$$\rho＝ｘ\cos\theta＋ｙ\sin\theta$$
a/bの代わりに、ρ（ロー）とθ（シータ）を定数にして式が表現されています。それぞれの値の意味は以下の図。
原点からρの距離にあり、そのなす角がθとなる直線。と定義されています。
多分どんな式の表現でもいいんだと思います。ただこの表現の方がθで投票箱を刻めるので、投票する値の刻みが自然になります。例えば0.1度毎直線を探していく。といった指定がa/bを使うより自然にできます。
あとゼロ割とか発散もしにくいのかなと思います。
ちょっと小難しい式になっていますが、別になんてことはないので、相似と、yの増加量/xの増加量、この中学数学を使った展開と、ベクトルの内積を使った高校数学で展開してみます。
中学数学を使った式の展開
すでにsin/cosが中学数学ではない気もしますが…。直線の傾きをa,y切片を bと置くとそれぞれの長さは相似sin/cosの定義からそれぞれ
のように求まります。その値をy=ax+bに代入すると、上述の式になります。簡単です。
高校数学を使った式の展開
直交するベクトルの内積はゼロ。これを展開するとやはり同じ式になります。
こっちの方がわかりやすいですかね。
Pythonにて検算
Python＋OpenCVにはこのハフ変換をやってくれる関数が用意されています。自分でコーディングする必要はありません。OpenCVの cv2.HoughLines()で実装されています。使い方は色々なサイトで紹介されているので細かくは解説しません。
ここでもやはりρとθが出てきます。
白黒2値の画像を入力として、白の点すべてに対してρとθの投票を行って行きます。ρとθの刻みは引数で指定できます。もちろん細かく刻めば厳密な角度、距離が求まりますが、点群がキレイに並んでいないと投票箱が埋まりません。
閾値を設定し、閾値以上の投票数があったρとθをListで返してくれます。返ってくるのがρとθなのでちょっとわかりにくいです。
ハフ変換はそれなりに重たい処理になります。例えばθを1度刻みに指定すると、すべての点に対して360回の計算が発生することになります。とても遅いです。前処理の2値化では、直線候補の画素数は極力絞っておいた方がよいです。
今回適当な直線を書いた2値画像をサンプルにテストしてみます。
64×64画素のグレースケール。斜めの直線はおよそρ＝28pixel、角度θは20°程度です。白の画素数は54pixelあるので、それより小さい値を閾値としてみます。ついでに水平線もひいときます。
コードです。短っ！
import cv2
import numpy as np
img = cv2.imread('hough.png', cv2.IMREAD_GRAYSCALE)
lines = cv2.HoughLines(img, 1, np.pi/180, 50)
print(lines)
処理の結果です。
[[[47. 1.5707964]]]
ρ=47pix、θ=π/2、90°水平線です。20°の線は見つかっていません。閾値を50から40にしてみます。
[[[47. 1.5707964]] [[28. 1.2217305]]]
もう一本見つかりました。θ = 1.22 = 70°直線への垂線の角度なので正しそうです。googleさんに「ラジアン 度 変換」と検索するだけで簡単に角度に変換できるのはとても便利…。
このリストにはいくつカウントされたものかは残っていません。ただリストは昇順になってそうです。カウントの高い、より直線らしいものから順に格納されてそうです。
まとめ
ハフ変換による線検出の仕組みについて色々書いてみました。あまりここまで細かく書いたサイトが見つからなかったので自分で書いてみました。多分間違ってはいないと思います。
OpenCVでの動作確認もしてみましたが、かなり機能としては隠蔽されている印象です。まぁ線を見つけたいのであればこんなところでよいのでしょうけど。
コメント