アフィン変換の続き（画素補間とアフィン逆変換）

　そういうわけで補完をしなければならないのであるが、実は補完アルゴリズムより座標計算がやたらと面倒くさい訳である。画像処理の教科書では座標軸の変わった座標アフィン逆変換はあまり書かれている気がしない。

1.回転時の座標ずれの補正

　2Dのコンピュータグラフィックは一般的に左上(0,0)としているのでアフィン変換のままで回転すると座標軸からはみ出してしまう。

　そこで、座標系を一度中央(ox,oy)に移動させ、最後に戻す。

　|1　0 -ox||a00 a01 a02||x||1  0  ox|   |a00x+a01y+a02-ox|1 0 ox|  
　|0  1 -oy||a10 a11 a12||y||0  1  oy| = |a10x+a11y+a12-oy|0 1 oy|
　|0　0   1||  0  0    1||1||0　0   1|   |     1          |0 0  1| 

X = a00*(x-ox) + a01(y-oy) + a02 + ox
Y = a10*(x-ox) + a11(y-oy) + a12 + oy

を計算することで、座標軸は中央のままで回転する。

2.色補間簡略化の戦略

2.1 計算法

最初に頂点のみを計算し、直線を計算し、その中にある点をアフィン逆変換し補完する。最初に角四点求めることで計算量を減らす。矩形かつ変形で捻れないのが前提。

(x,y) = A-1 (X,Y)

|x - ox|           1            | a11   -a01  a01a12 - a02a11|| X - ox - a02 |
|y - oy| = ----------------     |-a10    a00 -a00a12 + a02a10|| Y - oy - a12 |
|   1  |   a00a11 - a01a10 = t  |   0     0   a00a11 - a01a10||        1     |

a00a11 - a01a10 = tのとき、

x = (  a11 * (X - ox - a02) - a01 * ( Y - oy -a12)*a01a12 - a02a11)/t + ox
y = (- a01 * (X - ox - a02) + a00 * ( Y - oy -a12)-a00a12 + a02a10)/t + oy

　――で、変換後の座標系からオリジナルの座標が計算出来る。アフィン逆変換を行う事でアフィン変換地獄絵図のドット抜けは避けられる。

　アフィン変換を使うのは最初の4回だけで残りは全部アフィン逆変換だった……。インターネットネットに載っている式が大体間違っている。3x3の逆行列の公式から計算しなおした。

2. 探索法

　矩形から矩形にマッピングされるのでL1 (X0, Y0) - (X1, X1) L2 (X1, Y1) - (X2, Y2) L3 (X2, Y2) - (X3, Y3) L4 (X3,  Y3) - (X0, Y0)の4つの直線に囲まれた空間内の点か判定するだけで良い。

min(Y) - max(Y) の点Y' のときの X0' - X1' の間を計算する（整数で）

まずY0≦Y1≦Y2≦Y3にソートする。(Y' = Y''のときX'<X'')

これにより3stepで計算可能になる。このソートした座標をp0, p1, p2, p3とする。

1. L(p0,p1) L(p0,p2) の Xの範囲を計算 Y0 ≦  y < Y1

2. L(p0,p2) L(p1,p3) の Xの範囲を計算 Y1 ≦  y < Y2

3. L(p1,p3) L(p2,p3) のXの範囲を計算 Y2 ≦ y  < Y3
   直線は、dx/dy * (Y - SY)+ SX で求まる。ただし、dy = 0 の場合は SX ～ EX を一回だけ回す。

　難しく書いているけど、単なる力技。因み矩形でない時は強引に矩形にすれば良いのである（アルファチャネルを使う）

これで動くはずなんだけどな……（デバッグすること数時間……）

アフィン逆変換

　取りあえず動いた。整数演算と小数点演算が交互に出てくる悪魔だ……（まだバグ有りそう……）

 拡大・縮小アルゴリズムの選定

　拡大か縮小かは　以下で計算　mx √(a00^2 + a01^2) my √a(10^2 + a11^2) >1なら拡大　< 1なら縮小

　0.5までは縮小アルゴリズムは想定しなくて良い

1. ニアレストネイバー法　最短の座標から色を取得　縮小も同じ。実装済み

2. バイリニア法　(x,y)(x+1,y)(x,y+1)(x+1,y+1)の　4ドットの加重平均
   　<0.5 の時の縮小アルゴリズムは 1/mx x 1/my ドットの平均
   　両方が混じる場合は、ミックス

3. バイキュービック法 16ドットにフィルタ　縮小もバイキュービック
   x' - x = dとしたとき (xは整数) つまり計算に用いるのは(x - 1, x, x+1, x+2)(y-1,..,y+2) の16ドット
   (α + 2)d^3 - (α + 3)d^2 + α d ≦ 1.0
   αd^3 - 5αd^2 - 8α*d - 4α 1.0 < d < 2.0
   0 d ≧ 2.0
   ただし、α = -0.5～-0.75 または  - 1 が多い
   

4. Lanzcos法 縮小もLanzcos　中身はフーリエ変換
   　sincと言う関数が出てくる 中身はsin　sinc(x) = sin(πx)/πx
   計算式 α = 3の場合、16ドットで計算(Lanzcos3)
   f(d) = 1   (d = 0)
   f(d) = αsin(dπ) sin(dπ/α)/π^2x^2 0  (|d| < α)
   f(d) = 0  (|d| > α)

高速化戦略： sinの計算量をいかに減らすか

2.4アルゴリズム使用時の注意

　端のドットの扱い。

#日記 #プログラミング #数学 #行列 #Rust #WebAssembly  #画像処理