Hough変換 投票と多数決原理に基づく図形の検出

Presentation on theme: "Hough変換 投票と多数決原理に基づく図形の検出"— Presentation transcript:

1 Hough変換 投票と多数決原理に基づく図形の検出

2 １．問題の設定 　エッジ抽出などで得られたのは、特徴点の集合（点群）である。 　点群の中に、多くの点は長い直線を形成している。 　我々は、これらの長い直線の方程式を知りたい。　

3 ２．二つのアプローチ (a) すべての可能の直線を１本ずつチェッ 　クして、その直線に載っている特徴点の数 　を数える。 数が多かった直線は、我々がほしいものである。 (b) すべての特徴点を一個ずつチェックして、 　その点を通る直線を求める。 たくさんの特徴点が共通に通る直線は我々がほしいものである。

4 平面上の直線は、２個のパラメータを用いて表現できる。
平面上の直線の表現 　平面上の直線は、２個のパラメータを用いて表現できる。 y=kx+b Y k b O 1 X

5 rは原点から直線に垂線を引いたときの長さ qはx軸とのなす角 R>=0 qの範囲は0<= q <2p
直線の方程式 rは原点から直線に垂線を引いたときの長さ qはx軸とのなす角 R>=0 qの範囲は0<= q <2p

6 ２．二つのアプローチ（つづき） 処理する直線の数
２．二つのアプローチ（つづき） 　処理する直線の数 (a) の場合、すべての可能の直線 　　y=kx+b 仮に、k=tanq, q=[-90°90°],一度刻み 　　　　b=[-500,500], 1刻み とすると、直線は　180x1000=18万本 仮に、q=[0°360°],一度刻み 　　　　r=[0,500], 1刻み とすると、直線は　360x500=18万本

7 ２．二つのアプローチ（つづき） 処理する直線の数
２．二つのアプローチ（つづき） 　処理する直線の数 (b) の場合、各特徴点を通る直線 　　この場合、変化できる直線のパラメータは1個だけなので、 　直線の数＝特徴点の数ｘ180 あるいは 　　直線の数＝特徴点の数ｘ360

8 ２．二つのアプローチ（つづき） 処理する点の回数
２．二つのアプローチ（つづき） 　処理する点の回数 の場合、直線の本数ｘ特徴点の数 (b) の場合、180（或いは360）ｘ特徴点の数 明らかに、bのほうが少ない。

9 Hough変換は、bのほうのアプローチである

10 ある一点(x, y)を通る直線群は無限に存在し、
それぞれに対し(r, q)が一義的に決まる

11 ２点を通る直線群 共通の直線

12 = xcosq + ysinq を用いて計算すれば、
一点を通る直線群 = xcosq + ysinq を用いて計算すれば、 それぞれの点に対するr-qパラメータ空間の曲線が求まる

13 ２点を通る直線群 直線上の点１，２に対する曲線は、ある１点（ r0, q0）で交差している この（ r0, q0）が点１，２を共通に通る直線を表している

14 r-q空間 = xcosq + ysinq では、 角度qは有界であり、画像の大きさが有限であるため、rも有界となる

15 アルゴリズム１ 「Ｐ[ r][q]）とする」を用意する 原画像（ｘ-ｙ空間）のサイズをＷ*Ｗとすると、 rの取り得る範囲は である。
(a) r-q空間を離散化し、 r-qに関する2次元配列 　　　「Ｐ[ r][q]）とする」を用意する 　　原画像（ｘ-ｙ空間）のサイズをＷ*Ｗとすると、 　　rの取り得る範囲は である。 r、qの離散化間隔をそれぞれ　　　　　　　　　　　とすると、 2次元配列の大きさは　　　　　　　　である

16 アルゴリズム２ (b) 2値化された原画像をラスタ走査し、 画素値が１であればその(x, y)に対し、 r= xcosq + ysinq
　　Ｐ[ r][q]の値を１だけ増加します 　　(Ｐ[ r][q] ++;)（投票）

17 (c) Ｐ（ r、q ）が最大となる（ r、q ）を求める （開票） 直線が複数本ある場合は、極大点を求めることになる
アルゴリズム３ (c) Ｐ（ r、q ）が最大となる（ r、q ）を求める 　　（開票） 直線が複数本ある場合は、極大点を求めることになる

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48 入力画像（例1）

49 エッジ画像

50 ハーフ変換

51 ハーフ変換によって抽出した直線

52 r,qの空間を表す配列の大きさを計算しなさい。
練習問題： 画像の横幅＝２５６画素 画像の縦幅＝２５６画素 rの量子化単位は0.5画素、 qの量子化単位は２度とする。 r,qの空間を表す配列の大きさを計算しなさい。