ρ-θパラメータ空間への射影による直線検出

先日pythonを使って研究を楽にする画像認識アプリを作っていましたが、その中でhough変換を行い図形を検出する必要が出てきたので、改めて変換アルゴリズムについて考えてみようと思います。

hough変換による直線検出の原理

簡単に説明すると、hough変換では孤立した全ての点の直交座標をρ-θパラメータ空間に射影しグラフが交差する点を探します。

直交座標を極座標変換した場合ρ-θの組み合わせは無限に出てくるため、ρ-θパラメータ空間上ではそれぞれ点固有の曲線が描けることになります。

hough変換では点の数だけ曲線が現れ、それらの曲線が一番多く交差するところがもっともらしい直線であると判断します。

Pythonで可視化

まずは直交座標系からρ-θパラメータ空間に射影する様子を可視化してみようと思います。

とりあえずモジュールをインポートして、グラフのインスタンスを生成しておきます。

import numpy as np
import matplotlib.pyplot as plt
import math 
import random
import itertools
fig = plt.figure()

numpyでは角度にラジアンを用いるため、πを定義しておきます。

PI = np.pi

初めは、全ての点が一直線上に存在するように直交座標系の(x,y)を生成します。

x = [20*i + 10 for i in range(15)]
y = [i - 20 for i in range(len(x))]

以下が得られた線形グラフです。

これらの点を射影していきます。

θ = np.linspace(0,PI,100)
for i in range(len(x)):
    ρ = x[i]*np.cos(θ) + y[i]*np.sin(θ)
    plt.scatter(θ,ρ,color = "black",s=8)
plt.grid()
plt.xlabel('θ')
plt.ylabel('ρ')
fig.savefig('img_rth.jpg',dpi = 500)

対称性から考えて、0<θ≦πまでを100分割してグラフにプロットします。

以下が、上記の(x,y)に対するρ-θパラメータ空間上の曲線になります。

このグラフは、線形的なグラフを元に射影した結果なのでもちろんただ一つの点で交わります。

試しに、任意の２つの曲線をピックアップしてみます。

θ = np.linspace(0,PI,100)
ρ1 = x[5]*np.cos(θ) + y[5]*np.sin(θ)
plt.scatter(θ,ρ1,color = "red",s=8)
ρ2 = x[2]*np.cos(θ) + y[2]*np.sin(θ)
plt.scatter(θ,ρ2,color = "blue",s=8)

これらの直線が交わる座標を求めるには、θかρに関する方程式を作れば求めることができそうです。

ρについての方程式は変換がめんどくさいので、θについて方程式を作成しsympyで解いてみます。

import sympy as sym
θ = sym.symbols('θ')
sin = sym.sin(θ)
cos = sym.cos(θ)
a = (x[2] - x[5])*cos+ (y[2]-y[5])*sin
ans = sym.solve(a)[0]
print(-round(x[2]*sym.cos(ans)+(y[2]*sym.sin(ans)),3))

以下が計算結果です。

θ ＝1.621
ρ = -20.474

２つのパラメータが特定できたので、あとは直交座標系に戻してあげると直線の式になります。

hough変換によって推定された直線
y = 0.05x -20.474
元の直線の式
y = 0.05x -20.50

少しずれているのは、量子化誤差が生じているためです。

次回は、ランダムな座標を作り出しその中から一番直線らしいものを推定するアルゴリズムを作っていきます。