ロボットビジョン特論

Hough変換
投票と多数決原理に基づく図形の検出
1.問題の設定
エッジ抽出などで得られたのは、特徴点の
集合(点群)である。
点群の中に、多くの点は長い直線を形成し
ている。
我々は、これらの長い直線の方程式を知り
たい。
2.二つのアプローチ
(a) すべての可能の直線を1本ずつチェッ
クして、その直線に載っている特徴点の数
を数える。
数が多かった直線は、我々がほしいものであ
る。
(b) すべての特徴点を一個ずつチェックして、
その点を通る直線を求める。
たくさんの特徴点が共通に通る直線は我々が
ほしいものである。
平面上の直線の表現
平面上の直線は、2個のパラメータを用いて表
現できる。
y=kx+b
Y
k
b
O
1
X
直線の方程式
rは原点から直線に垂線を引いたときの長さ
qはx軸とのなす角
R>=0
qの範囲は0<= q <2p
2.二つのアプローチ(つづき)
処理する直線の数
(a) の場合、すべての可能の直線
y=kx+b
仮に、k=tanq, q=[-90°90°],一度刻み
b=[-500,500], 1刻み
とすると、直線は 180x1000=18万本
仮に、q=[0°360°],一度刻み
r=[0,500], 1刻み
とすると、直線は 360x500=18万本
2.二つのアプローチ(つづき)
処理する直線の数
(b) の場合、各特徴点を通る直線
この場合、変化できる直線のパラメータ
は1個だけなので、
直線の数=特徴点の数x180
あるいは
直線の数=特徴点の数x360
2.二つのアプローチ(つづき)
処理する点の回数
(a)の場合、直線の本数x特徴点の数
(b) の場合、180(或いは360)x特徴点の数
明らかに、bのほうが少ない。
Hough変換は、bのほうのアプ
ローチである
ある一点(x, y)を通る直線群は無限に存在し、
それぞれに対し(r, q)が一義的に決まる
2点を通る直線群
共通の直線
一点を通る直線群
r= xcosq + ysinq を用いて計算すれば、
それぞれの点に対するr-qパラメータ空間の曲
線が求まる
2点を通る直線群
直線上の点1,2に対する曲線は、ある1点( r0, q0)で
交差している
この( r0, q0)が点1,2を共通に通る直線を表している
r-q空間
r= xcosq + ysinq では、
角度qは有界であり、画像の大きさが有限であるた
め、rも有界となる
ほとんどの直線検出用ハフ変換ではr-qパラメータ
空間が用いられている
アルゴリズム1
(a) r-q空間を離散化し、 r-qに関する2次元配列
「P[ r][q])とする」を用意する
原画像(x-y空間)のサイズをW*Wとすると、

2 
rの取り得る範囲は 0,
w である。
 2 
r、qの離散化間隔をそれぞれ r = 1, q = 10 とすると、
2次元配列の大きさは
2
w  360 である
2
アルゴリズム2
(b) 2値化された原画像をラスタ走査し、
画素値が1であればその(x, y)に対し、
r= xcosq + ysinq
によって q 間隔でrを計算して整数化し、
P[ r][q]の値を1だけ増加します
(P[ r][q] ++;)(投票)
アルゴリズム3
(c) P( r、q )が最大となる( r、q )を求める
(開票)
直線が複数本ある場合は、極大点を求める
ことになる
1
1
1
1
1
1
1
1
2
2
1
3
1
1 1
2
2
1
1 1
1
1
1
1
入力画像(例1)
エッジ画像
ハーフ変換
ハーフ変換によって抽出した直線
練習問題:
画像の横幅=256画素
画像の縦幅=256画素
rの量子化単位は0.5画素、
qの量子化単位は2度とする。
r,qの空間を表す配列の大きさを計算しなさい。