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の空間を表す配列の大きさを計算しなさい。
© Copyright 2024 ExpyDoc