ハフ変換（２）－そもそもハフ変換とは何か

よっぽど完成されたライブラリを使う以外は、 自分で理解できないソースコードは書くべきでないことは言うまでもありませんが、 そもそもハフ変換による直線の抽出はどうゆう理屈かという話の第一ステップを考えてみます。(o^^o)

では、点が４つあったと考えましょう。
これです。

さて点を１点以上通る直線は、無限です。
早い話、点Aを通る直線は、点Aを中心に０～180度
の分だけ、無限に引けるわけです。

点を２点以上通る直線が何本ひけるかというと、
４本です。

  
ここでどういう考え方をするかというと、
【点Aは直線１を通る点である】ということです。

また同様に、
【点Dは直線１を通る点である】ということです。

そうすると逆に、

【直線１を通る点は、A,Dの２点ある】ということです。

また、

【直線５を通る点は、Aの１点ある】ということです。
まぁAを通る直線は無限にあるわけですが、例として書きました。

これらを集計して、
【２点以上通る線のみ有効なものとする】
と判定できれば、直線１～４の４つが集計できるという、こういうわけです。

しかしながら、そもそも【直線１】をどう定義して、
【どのように判定したら点Aを通るとわかるのか？】という話が、本題となります。

ここで、以下の図のような考え方をするわけです。
 
●直線１とは、
・水平とのなす角度が『角度１』
・原点Ｏとの距離が『Ｌ１』
と定義できるのですね。

そうすると、例えば、、100ピクセル×100ピクセルの画像を考えると、
●角度は０～180度まで考えられる
●直線と原点との距離は、最大でも141ピクセルである
ということがわかります。
そうすると、とたえ１度刻みにしたとしても、
141×180=25,380コのデータが必要になります。
0.1度刻みにすれば、253,800コのデータが必要になります。
ようするに、、
data[141][180]
のデータを持って、それぞれいくつの点を通るかを判定するという、
ものすっごくベタなことをする、
それをするのがハフ変換なのです。

つづく