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