はじめに
画像内の直線（道路の白線など）検出には、今回紹介するのはHough変換、またはその発展的手法が使われることがあります。Hough変換とは画像の中から直線や円を見つけるための最も基本的なアルゴリズムの1種でOpenCVなどにも関数が実装されています。
Hough変換のアルゴリズムについて勉強したので、簡単にまとめようと思います。
直線検出
左下図のような2値化（エッジ抽出）された画像上で、直線を探します。
これは、右下図のようなxy平面上の点群から、直線を探すことと同じですね。
直線方程式の変換
上記の問題を解くために、まず直線の方程式について考えてみます。二次元平面上の直線は$y=ax+b$で表すことができます。また、$y=ax+b$の直線が点$(x_i,y_i)$を通る場合、この直線は$y_i=ax_i+b$を満たす必要があります。左下図のようなイメージです。そして、点$(x_i,y_i)$を通る直線方程式のa,bを変数として右下図のようにab平面の上にプロットすると1本の直線になります。
これを複数の点に適用してみると、右下図になります。そして、右下図のab平面について考えてみると、例えばab平面上で2つの直線が交差している点は「そのa,bにより、xy平面上の2つの点を通る直線が引ける」という意味を持っていることが分かります。
同様に、右下図のように4つの直線が交差している場合は、そのa, bを持つ直線はxy平面上で4つの点を通るということです。
つまりab平面上での直線の密度を調べることで、x, y平面上で、あるa,bのパラメータを持つ直線が通る点が何点あるかを知ることができます。
多数決原理
直線を検出するためにab平面上での直線の密度を調べていきます。非常にシンプルな手法で、左下図のように格子を作ってその中を通る直線をカウントするだけです。
この格子の幅は大きすぎると分解能が低くなってしまい、小さすぎると誤検知の原因となるので慎重に決定する必要があります。
※このような方法を用いることから、Hough変換は投票と多数決原理による手法と言われています。
※実際には、傾きaが∞の直線も扱えるように極座標系でHough変換を考えます。また、同様の考え方で、直線ではなく楕円検出のHough変換なども存在します。
参考
最後に
最後まで読んで頂きありがとうございました。