アフィン変換について
アフィン変換は、回転、移動、変形、拡大、縮小、移動を一発で変換することが可能なアルゴリズムである。アフィン変換は以下の3x3の行列式で表す事が出来る。三番目の列は実際には使わない。このアルゴリズムは三次元に展開できるがそれはおいておく。
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
x_0 & x_1 & x_2 \\
y_0 & y_1 & y_2 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
この式を展開すると以下の用になる。そのため実際にインプリメントするときは行列を使わないことが多い(特に拡大縮小だけの場合)
X = x_0 x + x_1 y + x_2\\
Y = y_0 x + y_1 y + y_2
拡大・縮小
拡大・縮小は以下の用にあらわされる。
\begin{bmatrix}
X \\
Y \\
1
\end{bmatrix}
=
\begin{bmatrix}
S_x & 0 & 0 \\
0 & S_y & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
展開すると以下の用になる。
アフィン変換を使うまでも無いので拡大、縮小の場合は何も考えなくても実装可能である。そのためWeb上にいくらでもサンプルが転がっている。
移動
移動は以下の式であらわされる
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & T_x \\
0 & 1 & T_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
この式はこう展開される
X = x + T_x\\
Y = y + T_Y
このあたりはアフィン変換を考えなくても実装できる。
回転
回転は以下の用になる。
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
\cos\theta & - \sin\theta & 0 \\
\sin\theta & \cos\theta & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
一気に行列式になった。
X = x\cos \theta - y\sin \theta\\
Y = x\sin \theta + y\cos \theta
せん断(Shear/Skew)
平行四辺形に変形するやつである。なおアフィン変換では台形への変形できない。
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & S_x & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
S_y & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
などと表記される。なお S_x,S_y$ を \tan\theta で表記する場合もある。
組み合わせる
アフィン変換が本領を発揮するのがこれらを同時変換したいときである。
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
S_x & 0 & 0 \\
0 & S_y & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
\cos\theta & - \sin\theta & 0 \\
\sin\theta & \cos\theta & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & T_x \\
0 & 1 & T_y \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
すなわち上記の様な変換を行いたい時である。この式の意味するところは、まずTx,Ty移動し、θだけ回転し、Sx,Syにリサイズすると言う意味である。
このようなケースにアフィン変換が有効なのである。三回計算する必要があるのだが、先に行列式を計算することで1回でおわる。上記式の3x3の行列式を先に演算した結果を以下にしよう。
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
x_0 & x_1 & x_2 \\
y_0 & y_1 & y_2 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
そうすると、どんな複雑な転写をしようとも
X = x_0 x + x_1 y + x_2\\
Y = y_0 x + y_1 y + y_2
を計算するだけで座標の変換が終わるのである。
しかし実際には
コンピュータグラフィックは、離散なので変換時に座標軸の抜け落ちがでるのである。
上記が回転しただけのケースである。黒い部分は、変換前からの写像に存在しない点なので抜け落ちしてしまうのである。
そのため、補間を行う必要がある。
補間アルゴリズム
補間アルゴリズムとしては大きく4つが使われる。
- ニアレストネイバー法
- バイリニア法
- バイキュービック法
- Lanczos法
である。これらのアルゴリズムには一長一短あるのでどれが一番良いとは言えない(計算量が少なく、そこそこの結果が得られるバイリニア法を使うケースが一番多いと思うが)
アフィン変換における補間アルゴリズム
先述の問題があるためアフィン変換を行う時は補間アルゴリズムを利用しないといけない。
しかし、補間アルゴリズムについて説明していても拡大縮小のケースしか書いて居ないことが多く、回転や変形が起きた場合の補間について記載しているケースは少ない。
アフィン変換をした後、補間を行うには変形後の画像から、変形前の色データを取得すると言う処理を行う必要がある。
つまりアフィン変換の逆変換(アフィン逆変換)を行う必要があるのである。アフィン逆変換は逆行列をかけるだけなので以下の様あらわされる。
A =
\begin{bmatrix}
x_0 & x_1 & x_2 \\
y_0 & y_1 & y_2 \\
0 & 0 & 1 \\
\end{bmatrix}
のとき
\\
\\[16pt]
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
=
A^{-1}
\begin{bmatrix}
X \\
Y \\
1 \\
\end{bmatrix}
ここで、逆行列 A^{-1} を計算する必要がある。これが面倒くさい……。
展開すると以下の用になる(はずである)。まともに計算しているサイトがどこにもないので検証ができなっかたりする。
\begin{bmatrix}
x \\
y \\
1 \\
\end{bmatrix}
=
\frac{1}{x_0 y_1 - x_1 y_0}
\begin{bmatrix}
y_1 & -x_0 & x_1 y_2 - y_1 x_2 \\
-y_0 & x1 & y_0 x_2 - x_0 y_2 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
X\\
Y\\
1\\
\end{bmatrix}
アフィン逆変換の仕方
アフィン変換の対象は矩形で、変換後も四角形になる。
上の様に変形しても結局のところ四角形である。アフィン変換はかならず、四点をつないだ閉空間に写像される。したがって、頂点の四点をアフィン変換で計算し、直線で囲んだ閉空間を塗りつぶしの要領で残りの座標をアフィン逆変換の計算していけば良いことになる。つまりアフィン変換はを4回だけすれば後はアフィン逆変換を変換するだけである(したがってアフィン変換と計算量はさほどかわらない)
所詮、四角形であることを利用して以下の様に上からラインスキャンしていけば大丈夫なはずである。
-
y_0..y_1 線分 (x_0,y_0) - (x_1,y_1) と (x_0,y_0) - (x_2,y_2)
-
y_1..y_2 線分 (x_0,y_0) - (x_2,x_2) と (x_1,y_1) - (x_3,y_3)
-
y_2..y_3 線分 (x_1,y_1) - (x_3,y_3) と (x_2,y_2) - (x_3,y_3)
捻れた場合も恐らく大丈夫のはず。
Discussion