こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

ハフ変換(Hough変換)の原理について

現在、ハフ変換の原理について下記サイトなどを参考に調べていますが
いまいち原理がよくわかりません。
そこで2つ質問があります。
http://www.allisone.co.jp/html/Notes/image/Hough/index.html

【質問1】
 ハフ変換の原理は以下の認識であっていますでしょうか。

[直線を検出するハフ変換の原理]
10個のピクセルで構成される画像があり、各々のピクセルの座標を
(x1, y1)、(x2, y2)、(x3, y3)・・・(x10, y10) とする場合。

また、画像上の直線の式は p = xcosθ + ysinθで表すことができるため、
様々なpとθの組み合わせの式を作成(例えば下記3つの式)

(1) 2 = xcos10 + ysin10
(2) 4 = xcos20 + ysin20
(3) 6 = xcos30 + ysin30

(1)の式に10個のピクセルの各々の座標(x1, y1)、(x2, y2)・・・(x10, y10)
を代入 → 2つのピクセルの座標が(1)式を満たす

同様に(2)の式に10個のピクセルの各々の座標を代入
→ 8つのピクセルの座標が(2)式を満たす

同様に(3)の式に10個のピクセルの各々の座標を代入
→ 3つのピクセルの座標が(3)式を満たす

(2)式を満たすピクセルが多数存在するためこの画像には
4 = xcos20 + ysin20 で表す直線が存在する

【疑問2】
上記の認識でよい場合、もう1つ疑問があります。
直線の式 p = xcosθ + ysinθ において様々な(p, θ)の組み合わせの式を作成
することになると思うのですがその(p, θ)はどのように決めるのでしょうか。
考えうる限りすべての(p, θ)の組み合わせの式を作成するとものすごい量の
種類の式ができると思います。これをプログラムで行うとハフ変換はかなり
重い処理ということになるのでしょうか。

投稿日時 - 2020-05-27 14:11:41

QNo.9753795

すぐに回答ほしいです

質問者が選んだベストアンサー

ざっくりいうと、
1. 質問者の方のやり方だと、
- 考えられうる直線(つまり、全ての(θ,p)の組み合わせ)各々に対して、
- それぞれのデータ点が通るかを、データ点毎に計算する
為、計算量として (θの取りうる値)×(pの取りうる値)×(データの個数)分の計算が必要です。

2. それに対して、私が書いた方法では、
- 一つのデータに対して、θの取りうる値をすべて試し、それぞれのθに対応するpの値を(各θに対して)計算する
- この計算を、全てのデータに対して行う
為、計算量としては(θの取りうる値)×(データの個数)となります。

投稿日時 - 2020-05-27 20:30:22

お礼

ご回答ありがとうございます。
一つのデータ点に対して、θの取りうる値とそれぞれに対応するpを計算。
それを全てのデータ点に対して行うというのが肝ですね。
大変助かりました。丁寧な解説ありがとうございました。

投稿日時 - 2020-05-27 21:18:27

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(2)

ANo.1

そういう考え方(やり方)もあるのですが、その考え方(やり方)だと【疑問2】の通り重い処理になってしまうので、そういうやり方は普通しません。

どうするかというと、例えばデータ点 P[1] (x[1], y[1])を通る直線を考えた時に、仮にθを一つ決めると、p = x[1]cos(θ) + y[1]sin(θ)という関係式から、pの値は決まってしまいます。なので、普通は投票するべきθの範囲が決まっている時、例えば0≦θ≦πの範囲、π/6刻みで調べる、とかいう場合を考えた時に、θの値を 0, π/6, 2π/6, 3π/6, 4π/6, 5π/6, 6π/6と変え、それに対して p = x[1]cos(θ) + y[1]sin(θ)の関係式からpの値を(各々のθに対して)計算し、計算した6つの(θ, p)の組の所にそれぞれ一つずつ投票する、という方針でやります。これを、全てのデータ点 P[j]に対して計算するのです。

そうして(θ, p)平面に投票を繰り返したとき、もっとも得票を集めた(θ, p)の組み合わせに対応する直線が、もっともらしい直線として選ばれる、ということになります。

いずれにせよ、調べるべき(θ, p)平面の大きさが大きかったり、メッシュの刻み幅が細かかったりする場合には、Hough変換は重い計算になります。

投稿日時 - 2020-05-27 20:10:53

お礼

ご回答ありがとうございます。
丁寧な解説ありがとうございました。

投稿日時 - 2020-05-27 21:20:35