概要

画像の中の直線を検出する古典的な方法として，ハフ変換が有名です． ハフ空間上の点は直線の式に相当するものになります．

たとえば，上のような写真の中から四角形の物体の頂点を取り出したい場合，ハフ空間上の点から求めた直線の式を連立して，直線どうしの交点を求める必要があります． とても簡単なことなのですが，巷の記事ではわざわざ $y=ax+b$ の形に直してから解いていたり，数値的に交点が求められていたりして若干微妙に感じるポイントがあります． いちいち解説している記事が見当たらない割によく使うため，書くことにします．

ハフ空間上で表示された直線

ハフ空間上の点 $(\rho, \theta)$ は，つぎの直線を表すものになっています． $$ \rho = x \cos\theta + y \sin\theta $$

$y=ax+b$ にせずに交点を求める

いま，$(\rho_1, \theta_1),\ (\rho_2, \theta_2)$ で表現される2本の直線を考えます． これらが交点をもつということは， $$ \rho_1 = x \cos\theta_1 + y \sin\theta_1\\ \rho_2 = x \cos\theta_2 + y \sin\theta_2 $$ の両方が同一の $(x,y)$ に対して成り立つということなので， $$ \begin{bmatrix} \cos\theta_1 & \sin\theta_1\\ \cos\theta_2 & \sin\theta_2 \end{bmatrix} \begin{bmatrix} x\\ y \end{bmatrix} = \begin{bmatrix} \rho_1\\ \rho_2 \end{bmatrix} $$ と書けます． これを単純に $(x,y)$ について解くことで， $$ \begin{bmatrix} x\\ y \end{bmatrix} = \begin{bmatrix} \cos\theta_1 & \sin\theta_1\\ \cos\theta_2 & \sin\theta_2 \end{bmatrix}^{-1} \begin{bmatrix} \rho_1\\ \rho_2 \end{bmatrix} $$ と計算できます．

ただし，傾きが同一の2直線に対しては行列部分が特異となり，この方法は使用できません． この場合はそもそも交点をもたないので，行列式の値の大きさを確認する例外処理を入れると良いでしょう．

線形代数に祈りを．