直線を検出するHough変換をやさしく解説

Hough変換は、画像中に含まれる直線を「多数決」で検出する手法です。Hough は人名で「ハフ」と読みます。

以下、直線検出の原理を丁寧に解説し、様々な例を挙げてHough変換の特徴を述べます。

直線の方程式

まず Hough変換でよく使われる直線の方程式を導きましょう。

図1のような直線 \(L\) を考え、 \(L\) 上で原点 \(O\) に最も近い点(垂線の足)を \(\boldsymbol{r}\)、その距離を \(\rho\)、ベクトル \(\boldsymbol{r}\) が \(x\) 軸となす角を \(\theta\) とすると、点 \(\boldsymbol{r}\) の座標は次のように表せます。 \begin{eqnarray} \boldsymbol{r} &=& \rho (\cos\theta, \sin\theta) \label{r} \end{eqnarray}

図 1

\(\boldsymbol{r}\) と同じ向きの単位ベクトル (式 (\ref{r}) から \(\rho\) を取り除いたもの) \begin{eqnarray} \boldsymbol{n} &=& (\cos\theta, \sin\theta) \label{n} \end{eqnarray} と、直線上の点 \begin{eqnarray} \boldsymbol{p} &=& (x,y) \label{p} \end{eqnarray} の間には次式が成り立ちます (図の緑のベクトルと赤のベクトルは直交しているから)。 \begin{eqnarray} \boldsymbol{n}\cdot(\boldsymbol{p}-\boldsymbol{r}) &=& 0 \label{inner} \end{eqnarray}

式(\ref{inner}) に式(\ref{r}),(\ref{n}),(\ref{p}) を代入すると \begin{eqnarray} \boldsymbol{n}\cdot(\boldsymbol{p}-\boldsymbol{r}) &=& (\cos\theta, \sin\theta) \cdot (x-\rho\cos\theta, y-\rho\sin\theta) \\ &=& \cos\theta(x-\rho\cos\theta) + \sin\theta(y-\rho\sin\theta) \\ &=& x\cos\theta-\rho\cos^2\theta + y\sin\theta-\rho\sin^2\theta \\ &=& x\cos\theta + y\sin\theta-\rho(\cos^2\theta+\sin^2\theta) \\ &=& x\cos\theta + y\sin\theta-\rho \\ &=& 0 \end{eqnarray} \(\rho\) を移項すると、直線上の点 \((x,y)\) は次式を満たすことが判ります。 \begin{eqnarray} x\cos\theta + y\sin\theta &=& \rho \label{rho} \end{eqnarray} これが \(\theta,\rho\) で表した直線 \(L\) の方程式です。

なぜ単純に \(y=ax+b\) ではなく、このような面倒な形にするかというと、\(y=ax+b\) の形では \(x\) 軸に垂直な直線は \(a=\infty\) になって厄介だからです。式(\ref{rho})なら、どんな方向の直線でも同じ式で破綻することなく表せます。

基本的なアイデア

点 \((x_0,y_0)\) が、パラメータ \(\theta_T,\rho_T\) で表される直線 \(L\) 上にあれば、式(\ref{rho})から \begin{eqnarray} x_0\cos\theta_T + y_0\sin\theta_T &=& \rho_T \end{eqnarray} が成り立ちます (添字の \({}_T\) は真値 True value を表す)。

同様に他の点 \((x_1,y_2), (x_1,y_2),\cdots (x_{N-1},y_{N-1})\) も、もし直線 \(L\) 上にあるのであれば \begin{eqnarray} x_1\cos\theta_T + y_1\sin\theta_T &=& \rho_T \\ x_2\cos\theta_T + y_2\sin\theta_T &=& \rho_T \\ &\vdots& \nonumber\\ x_{N-1}\cos\theta_T + y_{N-1}\sin\theta_T &=& \rho_T \end{eqnarray} が成り立ち、左辺の計算結果は全て \(\rho_T\) に一致します。

図 2 : 点 \((x_n,y_n)\) が直線 \(L\) 上にある場合は
全点で \(x_n\cos\theta_T + y_n\sin\theta_T = \rho_T\) が成り立つ

そこで、推定角 \(\theta\) を少しずつ動かしながら、画像中の全ての画素 \((x,y)\) に対して \begin{eqnarray} \rho &=& x\cos\theta + y\sin\theta \label{rho2} \end{eqnarray} を計算して \((\theta,\rho)\) 位置に投票すると、図 3 のように真の直線パラメータ \((\theta_T, \rho_T)\) 付近に「得票」のピークができます。

図 3 : 得票を 3D 表示したもの
直線のパラメータ \((\theta_T, \rho_T)\) 位置に得票のピークができる

\(\theta\neq\theta_T\) の場合もある程度の票は得られるのですが、バラバラな位置 (図 3 でピークの左右に広がる扇状の領域) に得票が分散してしまうため、 \(\theta=\theta_T\) の「満場一致」には勝てず、正しい直線パラメータが圧勝します。

このような投票を Hough変換 といい、直線のパラメータ \(\theta_T, \rho_T\) を多数決で推定することができます。

様々な例

直線が複数ある場合

直線が 2 本ある場合は 2 箇所にピークが現れ、それぞれのピーク位置から 2 本の直線パラメータを推定できます。

図 4 : 直線が 2 本の場合の Hough変換

直線が 3 本以上ある場合も同様です。

破線の場合

切れぎれになった破線も検出できます (点線でも可能)。

図 5-1 : 破線

図 5-2 : 破線の Hough変換

検出された直線を緑で重ね描きしたものを以下に示します。

図 5-3 : 破線から推定された直線(緑)

この例からもわかるように、Hough変換によって得られるのは無限に続く「直線」であり、有限な長さの「線分」ではありません。このため破線を破線として認識するには、線がある部分と無い部分を判別する処理が別途必要になります。

ノイズがある場合

ノイズがある場合はどうでしょう?

図 6-1 : ノイズ混じりの画像

図 6-2 : Hough変換

ノイズが無い場合に比べるとHough変換全体に荒れが見られますが、線分が十分に長ければ問題なく直線を検出できます。多数決原理で直線を決定するため、ノイズに強いのです。

図 6-3 : 検出された直線(緑)

ただし線分が短い場合は得票のピークが低く、検出が難しくなりますので、事前に何らかのノイズ除去が必要になります。

直線のまわりに点がバラつく場合

実験では測定結果にノイズが乗るのはよくあることです。図 7-1 のように直線のまわりに点がバラつく場合はどうなるでしょう?

図 7-1 : 直線のまわりに点がバラつく場合

図 7-2 : Hough変換

Hough変換はピークが緩く広がった分布になりますが、点の数が十分あれば、図 7-3 のように、もっともらしい直線が推定されます。

図 7-3 : 検出された直線(緑)

応用例

横断歩道のペイントを検出してみましょう。

図 8-1 : 横断歩道

舗装面がザラザラしているためノイズ除去を施し、エッジ強調してから Hough変換すると、以下のようになります。

図 8-2 : Hough変換
横方向:\(\theta\), 奥行き方向:\(\rho\), 高さ:得票数

この画像では横断歩道のペイントが水平に近い角度で並んでいるため、得票ピークは \(\theta=90^\circ\) 付近に偏在しています (\(\theta\) は \(x\) 軸に対する直線の角度ではなく、直線の法線の角度であることに注意)。検出された直線を入力画像に重ね描きすると、次のようになります。

図 8-3 : 検出されたペイント輪郭線(緑)

歩行者の陰になっている部分があっても、ペイントの境界線をもっともらしく推定できています。

参考

Hough変換は直線だけでなく、少し書き換えれば、円、楕円、放物線など推定パラメータが少ない曲線の推定にも適用できます。

OpenCV には Hough変換のための HoughLines 関数が提供されていますので、OpenCV を使えば簡単に直線検出の実験ができます。

付録

\(y=ax+b\) の形にしたい場合

式(\ref{rho})を変形して \begin{eqnarray} y\sin\theta &=& \rho - x\cos\theta \\ \end{eqnarray} \(\theta\neq 0,\pi\) の場合は \begin{eqnarray} y &=& \frac{\rho}{\sin\theta} - x\frac{\cos\theta}{\sin\theta} \\ &=& - x \cot\theta + \rho\csc\theta \\ \end{eqnarray} \(\theta=0,\pi\) の場合は、式(\ref{rho})で \(\cos\theta=\pm1,\ \sin\theta=0\) だから \begin{eqnarray} \rho &=& x\underbrace{\cos\theta}_{\pm 1} + y\underbrace{\sin\theta}_{0} \end{eqnarray} より \begin{eqnarray} x &=& \pm\rho \end{eqnarray} と表せます。

\(x=ay+b\) の形にしたい場合

式(\ref{rho})を変形して \begin{eqnarray} x\cos\theta &=& \rho - y\sin\theta \\ \end{eqnarray} \(\theta\neq \pm\frac{\pi}{2}\) の場合は \begin{eqnarray} x &=& \frac{\rho}{\cos\theta} - y\frac{\sin\theta}{\cos\theta} \\ &=& - y \tan\theta + \rho\sec\theta \\ \end{eqnarray} \(\theta=\pm\frac{\pi}{2}\) の場合は、式(\ref{rho})で \(\cos\theta=0,\ \sin\theta=\pm 1\) だから \begin{eqnarray} \rho &=& x\underbrace{\cos\theta}_{0} + y\underbrace{\sin\theta}_{\pm 1} \end{eqnarray} より \begin{eqnarray} y &=& \pm\rho \end{eqnarray} と表せます。