ハフ変換（３）－ソースコードを見てみると。。。

それではググって、サンプルのソ－スでも見てみましょう。
とりあえず、ここあたりがソースとしてはわかりやすいです。
以下、抜粋です。
※＜が漢字になってます。注意。

   //直線の場合 -------------------------------------------------
      int theta,rho;
      //直線検出用頻度カウンタ
      short[][] counter=new short[THETA_MAX][2*RHO_MAX];

      for(y=0;y＜YMAX;y++)
         for(x=0;x＜XMAX;x++)
            if(data[y][x]==1){
               for(theta=0;theta＜THETA_MAX;theta++){
                  rho=(int)(x*cs[theta]+y*sn[theta]+0.5);
                  counter[theta][rho+RHO_MAX]++;
               }
            }

まぁ、中カッコ{}の有無が気に入りませんが、
まず、ＸとＹの２重ＬＯＯＰを回しています。
これは、『画像の全ての点』を対象にしているという意味ですね。

そして、その場所に該当データがあるかどうか、実際には点があるかどうかを判定し、
 点があった場合には、1024回のLOOPを回しています。
※THETA_MAXが1024 cs,snはsin,cosを再計算させるのを防止するため（CPU負荷がかかるから）、あらかじめテーブルにいれてあります。

同じ直線上の点であれば、 counter[角度][距離]が同じなので、
++でインクリメントしていきます。 まぁここまでは、だれが書いても似たようなコードになるでしょうかあｒ、特に問題はありませんですね。(o^^o) 

考えるとすれば、THETA_MAXが1024となっていますが、
この適切な値はどうやって決めるかという問題になりますね。

これには、ターゲットとする画像によって違うわけです。
ここでは、800*1200くらいに考えてみると、、、
ヨコ線が左右の端部で1ピクセル上下にズレた直線と仮定すると、
atan(1/800)→0.072度
180/0.072→2500分割くらい必要になります。

よって、上記のサンプルのTHETA_MAXはdefineされていますが、
本来はここは動的にするべきものとなりますね。 

さて、上記のrhoは、原点と直線の距離になるわけですが、
どのような値をとりえるかというと、実はマイナス値もとることがわけです。
はやい話、、こういう場合です。
 
では実際に、どのような値になるかを、
プログラムで確認してみましょう。

 つづく

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

よっぽど完成されたライブラリを使う以外は、 自分で理解できないソースコードは書くべきでないことは言うまでもありませんが、 そもそもハフ変換による直線の抽出はどうゆう理屈かという話の第一ステップを考えてみます。(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]
のデータを持って、それぞれいくつの点を通るかを判定するという、
ものすっごくベタなことをする、
それをするのがハフ変換なのです。

つづく

ハフ変換（１）－画像の角度を判定する

久々にまともな技術系な話です。
題名はハフ変換ですが、要するにこういうことです。
スキャナでスキャンした画像とかありますよね。
それを角度がついてるときに、戻したいって話です。
つまりこういうことです。
（１）スキャンした画像

（２）なんとなく角度を算定するために直線部分を検出する

（３）検出した角度から、正しい角度を予測して回転させる

まぁこんなことやりたいわけです。

まぁ、【ハフ変換】とかぐぐれば、なんとなくヒントがみつかるわけですが、
そして、サンプルのソースとかのってたりするわけですが、
はたまたＯｐｅｎＣＶあたりのサンプルでも似たようなものがあったりするわけですが、
やってみればわかります。
そんな簡単にはいかないと。
では、どうしましょう。
まぁ元々技術的に無理がある話でもないので、ひとつずつ解決していきましょう。

ってことで、つづく(o^^o)

ベクタ画像を合成（演算）する件。

なぜかはよくわからないけど、図形を演算するロジック、
そう、イラストレータで言えば、『パスファインダ』、
これ↓である。

この機能を作りたかったのだが、どうにもこうにもそれらしい情報が、
ネットを見てもほとんどないのである。
で、かろうじて合ったのはここ。
→http://www7b.biglobe.ne.jp/~garaku/Boolean.html
途中まではわかりやすいのだが、途中以降はよくわからないので、自分流にやってみた。
でも、そもそもなんでこんな基本的なことが出てないんだろうと言う疑問はさておき、
とりあえず、題材を元にロジックをかいてみよう。

【１】題材はこれ。
ピンクの図形と、薄緑の図形。

【２】ベクトル方向
もちろん、緑図形が抜けているのはベクトルの廻りが逆だから。
今回は、右回りを基本とする。
基本というか、最外郭が右回りという前提である。

【３】Y座標の算定
全てのベクトルを見たとき、次の点のY座標を抽出する。
図では横線として表示。
●ベクトルの始点
●ベクトルの終点
●ベクトル同士の交点
-----------------
そして、各ベクトルを横線で分割する。

【４】ベクトルに値を設定
上向きを+1、下向きを-1とする。
--------------------
次に、横線の間の各段（横線の数-1）ごとに、
左側から、値を集計し、記入す。
最後は０になるはず。
０にならなかったら、図形が閉じていないのだ。

【５】今回は、図形をORしてみる。

次に、横線の間の各段（横線の数-1）ごとに、

左側からベクトルをみて、+1（↑）と0（↓）を抽出し、それらのベクトルが離れている場合は右回りになるように、三角形または四角形を作成する。

【６】図形を分割したんだよ。
上記の【５】の作業で作成された、三角形と四角形は、←の図のようになる。
ここからいらないと思われる水平のベクトルを削除していくのだ。

【７】ちょっと説明が難しいので、簡単な例を。
←の図は四角形が３つだが、上の四角形の底辺（＝下の四角形の上辺）の位置の水平のベクトルを考えてみる。

【８】左回り図形になってしまったが、、、
頂点を左から番号をふると、６コある。

【９】頂点が６コということは、間は５コということである。
これの、偶数番目の間にあるベクトルを削除するのである。
上の四角形の底辺のベクトルは、４と３と２なので、２を削除する。
左下の四角形の上面のベクトルは、１と２なので、２を削除する。
右下の四角形の上面のベクトルは、４と５なので、４を削除する。

【１０】ちなみに、頂点がダブったときも、頂点は２コあるということにする。

【１１】残ったベクトルをつなぎ合わせると、左図のような図形ができあがる。

【１２】【６】に戻って、同様の処理を行う。

【１３】水平のベクトルはこのようになる。

【１４】右上部分を拡大すると、こんな感じ。
よって、上部の三角形の底辺は、
１-２-３-４-５-６-７-８なので、２-３，４-５，６-７のベクトルは削除される。
また、１と２、３と４、５と６、７と８は同じ点なので、最終的にはこの三角形の底辺の部分の水平のベクトルは全て削除される。

【１５】残ったベクトルをつなぎ合わせると、このようになる。
※点線部はないよ。

---

あとは、冗長点の削除をすればよいですね。
つづく。