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

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

   //直線の場合 -------------------------------------------------
      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)

新しいことを始めるときは。

新しいことを始めるとき。
今回は、AppMethodに挑戦なのですが、
プログラミングに限らず、新しいことを始めるときは、
大きく２つの方法があると思ってます。
（１）基礎から徹底的に学ぶ
（２）何かの目標をつくって、その最短距離を学ぶ。

もちろん、子供が勉強するかのごとく、（１）は良い方法というか、王道です。
しかし、大人がピアノを習うときは、（１）だと絶対めげちゃうんですよ。
だから、（２）なのです。
ハノンもやらず、『ピアノのテクニック』もやらず、
【弾きたい曲をなんとか仕上げる】
という方法をとるべきです。

ということで、【つくってみたいアプリをとにかく完成させる】ことを目標とし、
（２）の方法でAppMethodを学びます。
そして、都度、必要に迫られたときに、基本的なことを学びます。

ツール類は、最低条件として、ひととおりつかえることが大前提なので、

●STEP１
Wizardにでてくるものは、ひととおり、何もせずに（追加をね）、BUILDして実行してみる。
これです↓↓


●STEP２
『サンプル』として提供されてるものから、明らかに興味を引かないもの以外を、
BUILDして実行してみる、
これです↓↓


そこらへんを前準備としてやった後に、作りたいものを開始です。

私の場合は、最初に設計することをしません。
最後まで見通せるほど、普通の人間は、頭がよくないからです。

よく、SIerさんで、【要件定義】-【設計】-【詳細設計】-【実装】-
なんていうSTEPを、全て違う責任者がいたりして、
文書を書いてハンコをもらわないと進めなかったりして、
挙句の果てに、設計ミスがあっても戻れずに、
結果、ぐでぐでになるなんていうのは、
大きな企業ほどありがちです。
っていうか、あります。
っていうか、ありすぎます。

技術も流行りもめまぐるしくかわってる時代に、
いい年のおっちゃんがハンコを押したって、何もなりません。

まぁ結論から言えば、
設計書というのは、アプリが出来上がってから書くものなのです。

っと、話はそれましたが、
若い人には、
『常に美しい方法を選択し、感性でプログラムを書きながら、全体像を設計』
してほしいと思いますですね。
これでいいのです。
絵にすれば、こうです。(o^^o)

画像を縮小する（平均化）する件。

アルファチャンネルにアルファチャンネルを重ねる件とも似通った話ですが、画像を縮小化する場合の処理を考えてみます。
簡単に考えるために、２ピクセルを１ピクセルにすることを考えます。
もちろん、□と■を平均化すれば、中間のグレイになるだろうことはだれでも予想がつきます。
では、R1G1B1A1とR2G2B2A2を平均するにはどうすればよいか。

正しい方法ではないですが、特殊解から一般解を導くとたいてい合っている！
という方法があります。
そうすると、
0ｘ00FFFFFF　と　0ｘFFFFFFFF　を混合すれば、、
0ｘ80FFFFFF　と　なりそうなことは容易に想像できます。
※または、0ｘ7FFFFFFF
ということは、、アルファの値は単純に平均をとるだけでいいような気がするので、
いいということにしましょう。

問題は、RGB部分のFFFFFFというところです。
これだけみると間違った方法をとってしまいそうなので、
別の特殊解を考えて見ます。そう、
0ｘ00FF0000　と　0ｘFFFFFFFF　を混合しても、、
0ｘ80FFFFFF　と、同じ結果となります。
当然と言えば当然で、アルファが０であれば、RGBが何であっても
表示上は何も無いので同じわけです。

さぁ、ここで、これらを黒地に置いた場合を考えると、
0ｘ00FF0000　→　0ｘFF000000
0ｘFFFFFFFF　→　0ｘFFFFFFFF

そうすると、前回と同じように、V1、α１、V2、α２とすると、
V1=100、α１=0
V2=100、α２=1.0
結果→α３=0.5、V3=100
とすると、どうやら、（V1α１+V2α２）/2　が、黒地に置いたときの実際の値と思われるので、
V3＝（（V1α１+V2α２）/2）/α３
　　＝（（0*100）/2）/0.5＝50/0.5＝100　という感じと予測できます。
V1＝100、α1＝0.5とすれば、
V3＝（150/2）/0.75＝75/0.75＝100　となり、V３=100、α３＝0.75となるので、
これでもあってるっぽいですね。

で、結論としては、
●αは単純に平均化するのみ
●RGBはそれぞれの要素に関して、αをかけたR´G´B´を足し合わせて平均化し、
平均化されたαで割り返す
となります。

アルファチャンネルにアルファチャンネルにを重ねる件（3）

で、前回、こんなことを書いたわけです。

--------------------------------------------------

●元ピクセル

値V1、α：alp1

●のせる方のピクセル

値V2、α：alp2

としたとき合成したピクセルの値（B）は、

A = (0xff * (1-alp1) + V1 * alp1) * (1-alp2) + V2 * alp2

alp3 = alp2 + alp1*(1-alp2)

B = (A - 0xff*(1-alp3))/alp3

--------------------------------------------------

しかし、ハタと気づくわけです。

または感じるわけです。

何かが美しくないと。(o^^o)

そうです。白（0xff）の上に画像を置いた揚句、

あとからその部分を取り除くような考え方をしているわけです。

じゃぁ、黒の上に置いたらどうなるか。

そうすると、0ｘFFの部分が０になるわけなので、

A = (V1 * alp1) * (1-alp2) + V2 * alp2

= V1 * alp1 + V2 * alp2　- V1 * alp1 * alp2(式1)

alp3 = alp1 + alp2 - alp1*alp2(式2)

B = A /alp3

と、こうなるわけですね。
式がそれっぽくなりました。

で、検算してみると、うん。正しいようです。


ここで、式を見てみます。
式2を見ると、最終的なアルファの値は重ねる順序に関係な無いことがわかります。
式1を見ると、最終的なピクセルの値は、順序と関係する事がわかります。
そりゃあそうです。
白100%の上に赤100%を乗せれば赤になるし、逆なら白になるに決まってますよね。

アルファチャンネルにアルファチャンネルにを重ねる件（２）

で、色が違うときの話です。
まず、サンプル。

では、重なり部分のR成分の計算。
0xff * 0.5 + 0xff * 0.5 = 0xff
0x80*0.3 + 0xff * 0.7 = 0xD9
では、重なり部分は、
(0xff * 0.5 + 0xff * 0.5) * (1-0.3) + 0x80 * 0.3=0xD9
うんうん。ここまではあってますね。

では、前回と同じように合成後のアルファを考えると、
0.3　+　0.5　*　（1-0.3）→0.65となる。
0.5　+　0.3　*　（1-0.5）→0.65.もちろん同じ。

0xff * 0.35 + A * 0.65 = 0xD9
よって、
0ｘD9-0ｘｆｆ*（1-0.65）→0ｘC5
これをRGB要素全てに適用すればできる。。ハズ。

また重なってない部分を考えると、
0.3　+　0　*　（1-0.3）　→0.3
0ｘｆｆ*0.7　+　A　*　0.3　＝　0ｘD9
A＝0xff、アルファ：0.3
うん。できてるな。(o^^o)

ということで、
●元ピクセル
値V1、α：alp1
●のせる方のピクセル
値V2、α：alp2

としたとき合成したピクセルの値（B）は、

A = (0xff * (1-alp1) + V1 * alp1) * (1-alp2) + V2 * alp2
alp3 = alp2 + alp1*(1-alp2)
B = (A - 0xff*(1-alp3))/alp3

となります。
地道に展開したらもしかして簡単になるのでしょうか。。。
やってみますわー。

っといましたが、かここであることに気付くわけです。
で、それは次回で(o^^o)

アルファチャンネルにアルファチャンネルを重ねる件。

アルファチャンネル付き画像に、
アルファチャンネル付き画像を乗せたときの結果が、

思わしくない状況に遭遇することがあります。

では、何が正しいのかをちゃんと考えてみます。
PHP画像合成のバグもこの範疇に入ると思われます。
ということで、計算しやすくするため、以下の画像を考えます。
これは、イラレで矩形を透過属性付きで作成したもので、
黒白はα=1、
右の赤の矩形はα=80%
左と中央の赤の矩形はα=40%

としました。

そして画面キャプチャをとって、ピクセルの値を調べた値を＃テキスト表示しています。


■白の上に赤40％→#FF9999。
R要素→　FF*60%+FF*40%　→　0xff
GB要素→　FF*60%+00*40%　→　153　→　0x99
よって、FF9999

■黒の上に赤40％→#660000。
R要素→　00*60%+FF*40%　→　0x66
GB要素→　00*60%+00*40%　→　0x00
よって、660000

■白の上に赤40％、さらに赤40％→#FF5C5C
さてここの考え方が、全てのポイントである。
GB要素→　FF*A%+00*40%　→　92　→　0x5C
よって、Aは36%である。
ということは、明らかに、60％*60%である。

ようするに、アルファ：40%の画像の上に、アルファ30%の画像を載せたときの
アルファは、
30%　+　40%　*　（100-30）%　→　30+28　→　58%　となる。
逆にすると、
40%　+　30%　*　（100-40）%　→　40+18　→　58%　となり、やっぱり同じである。

シンプルな話なんですけどね。。。。。。(o^^o)
ただし、サンプルは同じ色のアルファだけ変えたサンプルなので、
色が違うときは、、、次回で。（－＿－；）

PHPの画像合成のバグ

PHPで画像の合成なのですが、、 もちろん、
imagesavealphaと
imageAlphaBlendingを設定して、
imagecopyしたものを、
imagepng したわけですが、
こんな結果です。
●１

●２

●３


全て、中央の画像に右の画像を合成したものが左の画像なので、
本来は全て同じハズです。
違いは、中央の画像のα＝0のピクセルのRGBの値が３つとも違い、
上から、0ｘ000000(黒)　0ｘｆｆ0000（赤）　0ｘｆｆｆｆｆｆ（白）です。
要するにBLENDするときに、α＝0の部分ももってきてしまって、
BLENDした挙句、αの値の平均でもとっているのでしょうかね。
どっちにしても、ダメっすねー。
まぁきちんと解明してみますです。(o^^o)
とりあえず、こういうバグがあるということでした。

---

追記
本来はこうあるべきというの作成。

上段がイラレで作成、
下段が自前のプログラムで作成。
残念ながら、僅かな誤差がありましたが（3Fと40とか^^;）、
基本的にはあっています。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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