射影変換の計算方法を求める

長方形の頂点が、カメラの相対的な移動によって、別の４点に移動することを考える

https://gyazo.com/901e7c1933780c02e568ebede417c2d2

このときの変換の計算方法を求める

画像の上では、これらはすべて二次元の平面上の移動である

しかし、計算する上では３次元を考える必要がある

x,yとは別の一つ上の次元zも含めた３次元上で、線形変換と平行移動

そのあと、z=1の平面へ、原点方向の射影

の２段階に分けられる

これは、「カメラを動かしたときに長方形がカメラに対して相対的にどのように動くのか」という考えを、素朴に数学的な表現にしたものである

補足

ところで、射影変換行列というと前者の変換のみを指すような気がするが、どうだったっけか

以上の２段階の変換を

(x,y,0) -> (u,v,w) -> (X,Y,1)とする

https://gyazo.com/11fe0539495c2c6f6807bd7da28d2b6f

条件１　線形変換と平行移動

y = Ax+B

条件２　原点に向けて、z=1上に射影

後者の射影の方は、ただ単にz成分で割ることで、z=1の平面に落とすこと

X = u/w

Y = v/w

---.icon

条件１

(u,v,w) = M (x,y,0) + C

補足

z=0なのでMの左２列だけが有効

Cは平行移動

これを書き換えると

$ u = ax+by+c

$ v = dx+ey + f

$ w = gx+hy+i

Mは線形変換としていて、それ以上の仮定をしていない。

上記で述べている前者の変換を、現実のカメラの相対的な配置とみなすなら、

Mは任意回転のみであり、

せん断とスケールが無いことを仮定として数式に反映されていない

しかし、今回は未知数が（上記のa~iの９でなく）８つとなり、４点の座標のx,yで、定まる

一つ消えるのは、後述の条件２を合わせることで消える

これだけで十分ということ

なので行列Mに対して直接何らかの制約は与えていない

そもそもz=0で右１列が消えている

なぜなら

これは図形的には、u,v,wを定数倍することにあたり、

前者の変換結果を原点方向に拡大縮小することに当たる

この拡大縮小は、後者の原点方向の射影で消えることを意味する

---.icon

以上より、全体の変換は

$ X = \frac{ax+by+c}{gx+hy + 1}

$ Y = \frac{dx+ey+f}{gx+hy+1}

となる

分母を払い整理すると

$ X = ax + by+ c - gx X - hy X

$ Y = dx + ey+ f - gx Y - hy Y

ここで、

以下の８つの式が得られる

$ X_0 = ax_0 + by_0+ c - gx_0 X_0 - hy_0 X_0

$ Y_0 = dx_0 + ey_0+ f - gx_0 Y_0 - hy_0 Y_0

$ X_1 = ax_1 + by_1+ c - gx_1 X_1 - hy_1 X_1

$ Y_1 = dx_1 + ey_1+ f - gx_1 Y_1 - hy_1 Y_1

$ X_2 = ax_2 + by_2+ c - gx_2 X_2 - hy_2 X_2

$ Y_2 = dx_2 + ey_2+ f - gx_2 Y_2 - hy_2 Y_2

$ X_3 = ax_3 + by_3+ c - gx_3 X_3 - hy_3 X_3

$ Y_3 = dx_3 + ey_3+ f - gx_3 Y_3 - hy_3 Y_3

これは、特定の条件下で解くことができる

４点が直線状に並んだりすると解けない

連立方程式を解く

まずは、変換元の点が(0,0)(1,0)(0,1)(1,1)の４点の場合を考える

この４点から任意の４点への計算方法がわかれば、任意の４点→任意の４点の場合も解ける

$ x_0=0, y_0=0,

$ x_1=1, y_1=0,

$ x_2=0, y_2=1,

$ x_3=1, y_3=1,

とする

このとき、上の連立方程式は

$ X_0 = c

$ Y_0 = f

$ X_1 = a + c - g X_1

$ Y_1 = d + f - g Y_1

$ X_2 = b + c - h X_2

$ Y_2 = e + f - h Y_2

$ X_3 = a + b+ c - g X_3 - h X_3

$ Y_3 = d + e+ f - g Y_3 - h Y_3

となる

最初の２行より、すでにc,fについては解けている

残りの式のc,fにこれを代入し

$ X_1 = a + X_0 - g X_1

$ Y_1 = d + Y_0 - g Y_1

$ X_2 = b + X_0 - h X_2

$ Y_2 = e + Y_0 - h Y_2

$ X_3 = a + b+ X_0 - g X_3 - h X_3

$ Y_3 = d + e+ Y_0 - g Y_3 - h Y_3

a,b,d,eについて消去して、

$ X_3 - X_1 - X_2

$ = (a + b+ X_0 - g X_3 - h X_3) - (a + X_0 - g X_1) - (b + X_0 - h X_2)

$ = g (X_1 -X_3) + h (X_2 - X_3) - X_0

$ Y_3 - Y_1 - Y_2

$ = (d + e+ Y_0 - g Y_3 - h Y_3) - (d + Y_0 - g Y_1) - (e + Y_0 - h Y_2)

$ = g (Y_1 -Y_3) + h (Y_2 - Y_3) - Y_0

よって

$ X_0 - X_1 - X_2 + X_3 = g (X_1 -X_3) + h (X_2 - X_3)

$ Y_0 - Y_1 - Y_2 + Y_3 = g (Y_1 -Y_3) + h (Y_2-Y_3)

<=>

簡単のため、以下のように置くと　（これはプログラムで計算する場合にも使える

$ s_x = X_0 - X_1 - X_2 + X_3

$ s_y = Y_0 - Y_1 - Y_2 + Y_3

$ dx_1 = X_1-X_3

$ dx_2 = X_2-X_3

$ dy_1 = Y_1-Y_3

$ dy_2 = Y_2-Y_3

すると上の式は簡単に以下のように書ける

よって

$ g= \frac{ dy_2 s_x - dx_2 s_y }{z}

$ h = \frac{dx_1 s_y - dy_1 s_x}{z}

あとはa,d,b,eについても

$ a = X_1-X_0 + g X_1

$ d = Y_1 - Y_0 + g Y_1

$ b = X_2 - X_0 + h X_2

$ e = Y_2 - Y_0 + h Y_2

となり、g,hを代入すればよい

（プログラムに置いては、先にg,hを計算し変数において、上の式をそのまま書いてadbeを求めればいい

以上より、a-hが全て、X_i,Y_iで表された

これは４点を時計回りにやっているので上で書いているものと、2,3が逆なのに注意

code:cs

var system:Array = new Array( 8 );

var z:Number = (dx1*dy2)-(dy1*dx2);

var g:Number = ((sx*dy2)-(sy*dx2))/z;

var h:Number = ((sy*dx1)-(sx*dy1))/z;

$ \left( \begin{array} { l } { u } \\ { v } \\ { w } \end{array} \right) = \left( \begin{array} { l l l } { a } & { b } & { c } \\ { d } & { e } & { f } \\ { g } & { h } & { 1 } \end{array} \right) \left( \begin{array} { l } { x } \\ { y } \\ { 1 } \end{array} \right)

$ X = u/w

$ Y = v/w

srcを0,1の四角形じゃない場合は、逆行列を前にあわせればいい