読者です 読者をやめる 読者になる 読者になる

デジタル・デザイン・ラボラトリーな日々

アラフィフプログラマーが数学と物理を基礎からやり直す

射影変換(ホモグラフィ)について理解してみる

2D 射影変換

3Dを基礎から勉強する フラットシェーディング」の記事を書いて、次は立方体のテクスチャマッピングに取り掛かろうと思ったんですが、ふとアフィン変換で台形は出来ないってことを書いたことを思い出したんです。テクスチャマッピングについては、「テクスチャマッピングを理解してみる」で三角形に分割することで台形にすることが出来たのですが、分割しなくても台形にするには「射影変換(ホモグラフィ)」すれば出来ることが分かりました。
早速、射影変換の調査に取り掛かったのですが、これが自分の理解度が足りないのか1ヶ月以上経って、やっとこうして記事を書こうと思うところまで理解が進んだところです。

まだ理解が途中段階であるため、理解した現状まで書いていきます。
射影変換(ホモグラフィ)には、下記の変換式があります。

変換式

変換式は以下の通り。
u = (x*a + y*b + c) / (x*g + y*h + 1)
v = (x*d + y*e + f) / (x*g + y*h + 1)

各変数の説明は以下の通り。
x, y 変換前のX座標、Y座標
a, b, c, d, e, f, g, h 変換係数
u, v 変換後の座標

変換係数(a,b,c,d,e,f,g,h)の算出

各係数を算出するには、最低8個の変換式が必要になる。
4つの対応点があれば8個の変換式(X,Yそれぞれ4つ)を生成できる。
8個の変換式から連立方程式を解くことにより、各係数を算出する。

しかし、射影変換式のままだと分数を含んでしまうので、
分母を払い一次多項式に展開する。(↓)
u = x*a + y*b + c - x*g*u - y*h*u
v = x*d + y*e + f - x*g*v - y*h*v

この多項式に各点(x,y,u,v)を代入し、連立方程式を解く。

miraiware.net

調べた当初は、意味が分からなかったんですが、いろいろ調べていくうちに理解しました。

平面図形の射影変換の考え方のサイトに式があります。
\array{x'=\frac{a1x+b1y+c1}{a0x+b0y+c0}\\y'=\frac{a2x+b2y+c2}{a0x+b0y+c0}}

下記の変換式は、上記式をx'→u,y'→v,a1→a,a1→b,c1→c,a2→d,b2→e,c2→f,a0→g,b0→h,c0→1に置き換えたものです。
u = (x*a + y*b + c) / (x*g + y*h + 1)
v = (x*d + y*e + f) / (x*g + y*h + 1)

分母を払い一次多項式に展開します。
分母を払うには、両辺に分母の(x*g + y*h + 1)を掛ければいいので

u = (x*a + y*b + c) / (x*g + y*h + 1)
v = (x*d + y*e + f) / (x*g + y*h + 1)
        ↓
(x*g + y*h + 1)u = (x*a + y*b + c)
(x*g + y*h + 1)v = (x*d + y*e + f)
        ↓
x*g*u + y*h*u + u = x*a + y*b + c
x*g*v + y*h*v + v = x*d + y*e + f
        ↓
u = x*a + y*b + c - x*g*u - y*h*u
v = x*d + y*e + f - x*g*v - y*h*v

※c0→1としているのは、行列で表現した時にパラメータは3x3の正方行列となります。有効パラメータは8個なので9個目は単位行列的に1となります。
\begin{pmatrix}u\\v\\1\end{pmatrix}=
\begin{pmatrix}a&b&c\\d&e&f\\g&h&1\end{pmatrix}
\begin{pmatrix}x'\\y'\\1\end{pmatrix}



この変換係数(a,b,c,d,e,f,g,h)の8個の未知数を、変換前の4点の座標と変換後の4点の座標から8次元連立一次方程式を解いて求める必要があるわけです。

変換前の座標 左上から時計回り
(x1,y1),(x2,y2)
(x4,y4),(x3,y3)
変換後の座標 左上から時計回り
(X1,Y1),(X2,Y2)
(X4,Y4),(X3,Y3)

8次元連立一次方程式
X1 = x1 \times a + y1 \times b + c - x1 \times g \times X1 - y1 \times h \times X1
Y1 = x1 \times d + y1 \times e + f - x1 \times g \times Y1 - y1 \times h \times Y1
X2 = x2 \times a + y2 \times b + c - x2 \times g \times X2 - y2 \times h \times X2
Y2 = x2 \times d + y2 \times e + f - x2 \times g \times Y2 - y2 \times h \times Y2
X3 = x3 \times a + y3 \times b + c - x3 \times g \times X3 - y3 \times h \times X3
Y3 = x3 \times d + y3 \times e + f - x3 \times g \times Y3 - y3 \times h \times Y3
X4 = x4 \times a + y4 \times b + c - x4 \times g \times X4 - y4 \times h \times X4
Y4 = x4 \times d + y4 \times e + f - x4 \times g \times Y4 - y4 \times h \times Y4

数が多いので難しく思われるのですが、これは先程の式(分母を払い一次多項式に展開)を、u→X1,v→Y1,x→x1,y→y1に置き換えて、4点分(2x4=8)繰り返しただけです。
u = x*a + y*b + c - x*g*u - y*h*u
v = x*d + y*e + f - x*g*v - y*h*v

でも、式が分かったとして、どうやって8次元連立一次方程式を解くのか?ってことなんですよね。
早速、「射影変換 javascript」や「射影変換 actionscript」で検索してみました。

4つのソースを解析してみたのですが、先頭サイトのソースを参考にしているようです。

static private function getSystem( P:Array ):Array 
{
	var system:Array = new Array( 8 );
	var sx:Number = (P[0].x-P[1].x)+(P[2].x-P[3].x);
	var sy:Number = (P[0].y-P[1].y)+(P[2].y-P[3].y);
	
	var dx1:Number = P[1].x-P[2].x;
	var dx2:Number = P[3].x-P[2].x;
	var dy1:Number = P[1].y-P[2].y;
	var dy2:Number = P[3].y-P[2].y;
 
	var z:Number = (dx1*dy2)-(dy1*dx2);
	var g:Number = ((sx*dy2)-(sy*dx2))/z;
	var h:Number = ((sy*dx1)-(sx*dy1))/z;
 
	system[0]=P[1].x-P[0].x+g*P[1].x;
	system[1]=P[3].x-P[0].x+h*P[3].x;
	system[2]=P[0].x;
	system[3]=P[1].y-P[0].y+g*P[1].y;
	system[4]=P[3].y-P[0].y+h*P[3].y;
	system[5]=P[0].y;
	system[6]=g;
	system[7]=h;
 
	return system;
}

8次元連立一次方程式がすごく簡単な計算式になっているわけです。
方程式と照らし合わせても、どうしてこうなるのかが分からないですが、最終的には8個のパラメータが求まっているんですよね。
調べたところでは、これは歪んだ四角形の画像を正方形(長方形)画像に補正する用途に特化しているから短く出来ているんだと思っています。
射影変換の用途としては、平面画像への補正によく使われるので、OpenCVのライブラリを使わないで作成するにはこれだけで問題ないんでしょうね。
下記サイトはOpenCVを使って射影変換している。


ただ、私としては台形に変形させたいので、8次元連立一次方程式を解いた方式をさらに模索していた中で、下記サイトを見つけました。

内容的には私が目指していたものですが、残念なのは中身はCSSなんですよね。

次回の記事で、この中身を解析していきます。

あと、下記サイトも調べる上で参考になりました。