アフィン変換と行列 (ABC189-E Rotate and Flip)

ABC189のE問題はアフィン変換を合成していく問題でした。今回はこのアフィン変換についてまとめていきたいと思います。

平行移動
行列とベクトルの組によるアフィン変換の表現
- 平行移動を先にすると
- アフィン変換の合成
アフィン変換の行列表現
ABC189-E
余談

アフィン変換はベクトル空間内の一次変換(線型変換)と平行移動の組み合わせのことを言います。一次変換については長くなってしまったので別の記事にしました。
この記事では $\boldsymbol{x}$ は $n$ 次元列ベクトル、 $\boldsymbol{A}$ は $m \times n$ 行列とし、その他の行列やベクトルは文脈から型を決めることとします。また、 $\mathbf{0}_k$ は $k$ 次元列零ベクトル、 $\mathbf{e}_i$ は $i$ 番目の標準基底列ベクトル(次元は適宜)を表します。

平行移動

平行移動は $\boldsymbol{x}$ を $\boldsymbol{x} + \boldsymbol{v}$ に移す変換です。一般にこの変換は一次変換ではありません。 $\boldsymbol{v} \neq \mathbf{0}_n$ であるような平行移動では線型性が成り立ちません。

一次変換だけだと原点以外を中心とした回転や原点を通らない直線を軸とした対称移動を表すことができません。しかし、平行移動と組み合わせることによって表現することが可能になります。このようにこの2つの変換は相性が良いため、組み合わせてアフィン変換と呼んでいるという訳なのです。

行列とベクトルの組によるアフィン変換の表現

アフィン変換は一次変換と平行移動の組み合わせでした。一次変換を表す行列 $\boldsymbol{A}$ と平行移動を表すベクトル $\boldsymbol{v}$ を用いるとアフィン変換は $\boldsymbol{x} \mapsto \boldsymbol{Ax} + \boldsymbol{v}$ と表現することができます。さてここでは、 $\boldsymbol{A}$ と $\boldsymbol{v}$ によるアフィン変換を $f_{\boldsymbol{A}, \boldsymbol{v}}$ と表記します。 $f_{\boldsymbol{A}, \boldsymbol{v}}(\boldsymbol{x}) = \boldsymbol{Ax} + \boldsymbol{v}$ です。平行移動を行わない、言い換えれば $\boldsymbol{v} = \mathbf{0}_m$ の時は、一次変換となります $(f_{\boldsymbol{A}, \mathbf{0}_m} = f_{\boldsymbol{A}})$ 。

平行移動を先にすると

アフィン変換の表現に $f_{\boldsymbol{A}, \boldsymbol{v}}: \boldsymbol{x} \mapsto \boldsymbol{Ax} + \boldsymbol{v}$ というものを採用しています。これは、一次変換を施してから平行移動を行っています。それでは逆に、先に平行移動を行う $g_{\boldsymbol{B}, \boldsymbol{w}}: \boldsymbol{x} \mapsto \boldsymbol{B}(\boldsymbol{x+w})$ を考えてみるのはどうでしょう。この場合 $\boldsymbol{B}(\boldsymbol{x+w}) = \boldsymbol{Bx} + \boldsymbol{Bw}$ となるので $g_{\boldsymbol{B}, \boldsymbol{w}} = f_{\boldsymbol{B}, \boldsymbol{Bw}}$ となります。では、 $f_{\boldsymbol{A}, \boldsymbol{v}}$ を $g_{\boldsymbol{B}, \boldsymbol{w}}$ で表せないでしょうか? $\boldsymbol{Ax} + \boldsymbol{v} = \boldsymbol{A}(\boldsymbol{x} + \boldsymbol{A}^{-1} \boldsymbol{v})$ より $f_{\boldsymbol{A}, \boldsymbol{v}} = g_{\boldsymbol{A}, \boldsymbol{A}^{-1} \boldsymbol{v}}$ としたいところですが、 $\boldsymbol{A}^{-1}$ が存在する、つまり $\boldsymbol{A}$ が正則であるとは限りません*1。つまり $g_{\boldsymbol{B}, \boldsymbol{w}}$ は $f_{\boldsymbol{A}, \boldsymbol{v}}$ に比べ使い勝手が悪いのです。

アフィン変換の合成

2つのアフィン変換を合成するとどうなるでしょうか? $f_{\boldsymbol{A}, \boldsymbol{a}}$ を作用させたあとに $f_{\boldsymbol{B}, \boldsymbol{b}}$ を作用させる変換を考えます。

$\begin{align} (f_{\boldsymbol{B}, \boldsymbol{b}} \circ f_{\boldsymbol{A}, \boldsymbol{a}})(\boldsymbol{x}) & = f_{\boldsymbol{B}, \boldsymbol{b}}(f_{\boldsymbol{A}, \boldsymbol{a}}(\boldsymbol{x})) = f_{\boldsymbol{B}, \boldsymbol{b}}(\boldsymbol{Ax}+\boldsymbol{a}) \\ & = \boldsymbol{B}(\boldsymbol{Ax}+\boldsymbol{a}) + \boldsymbol{b} = (\boldsymbol{BA})\boldsymbol{x} + (\boldsymbol{Ba} + \boldsymbol{b}) \end{align}$

となることから $f_{\boldsymbol{B}, \boldsymbol{b}} \circ f_{\boldsymbol{A}, \boldsymbol{a}} = f_{\boldsymbol{BA}, \boldsymbol{Ba} + \boldsymbol{b}}$ となることが分かりました。

アフィン変換の行列表現

さてアフィン変換が行列とベクトルで表現されることが分かりました。これを何とかして1つの行列で表せないでしょうか?実は各ベクトル、行列に余分な1次元を加えることで表現することができます。座標 $\boldsymbol{x}$ に対して $\begin{pmatrix} \boldsymbol{x} \\ 1 \end{pmatrix}$ というベクトルを考えます。するとアフィン変換 $f_{\boldsymbol{A}, \boldsymbol{v}}$ は $\begin{pmatrix} \boldsymbol{A} & \boldsymbol{v} \\ \mathbf{0}_n^{\top} & 1 \end{pmatrix}$ という行列で表すことができます。実際に計算して $\begin{pmatrix} \boldsymbol{A} & \boldsymbol{v} \\ \mathbf{0}_n^{\top} & 1 \end{pmatrix} \begin{pmatrix} \boldsymbol{x} \\ 1 \end{pmatrix} = \begin{pmatrix} \boldsymbol{Ax}+\boldsymbol{v} \\ 1 \end{pmatrix} = \begin{pmatrix} f_{\boldsymbol{A}, \boldsymbol{v}}(\boldsymbol{x}) \\ 1 \end{pmatrix}$ となることが確認できます。
合成も $\begin{pmatrix} \boldsymbol{B} & \boldsymbol{b} \\ \mathbf{0}_m^{\top} & 1 \end{pmatrix} \begin{pmatrix} \boldsymbol{A} & \boldsymbol{a} \\ \mathbf{0}_n^{\top} & 1 \end{pmatrix} = \begin{pmatrix} \boldsymbol{BA} & \boldsymbol{Ba}+\boldsymbol{b} \\ \mathbf{0}_n^{\top} & 1 \end{pmatrix}$ と行列積で計算できます。
行列で表せることから一次変換であるように思うかもしれませんが、始域がベクトル空間ではない*2ため一次変換ではありません。

ABC189-E

ここでABC189-EのRotate and Flipについて考えてみます。実は与えられる4種類の操作はアフィン変換となっています。また、2次元平面の問題ですので $n = m = 2$ です。一次変換の行列についてはこちらの記事を参考にしてください。

$ \mathrm{op}_i = $ `1`の時

f:id:Flkanjin:20210206133744p:plain:left:w421 原点中心で時計回りに $90 ^{\circ}$ 回転なので
$\boldsymbol{A} = \boldsymbol{R}\,(-90^{\circ}) = \begin{pmatrix} 0 & 1 \\ -1 & 0 \\ \end{pmatrix},$ $\boldsymbol{v} = \begin{pmatrix} 0 \\ 0 \\ \end{pmatrix}$ となります。

$ \mathrm{op}_i = $ `2`の時

f:id:Flkanjin:20210206140659p:plain:left:w417 原点中心で反時計回りに $90 ^{\circ}$ 回転なので
$\boldsymbol{A} = \boldsymbol{R}\,(90^{\circ}) = \begin{pmatrix} 0 & -1 \\ 1 & 0 \\ \end{pmatrix},$ $\boldsymbol{v} = \begin{pmatrix} 0 \\ 0 \\ \end{pmatrix}$ となります。

$ \mathrm{op}_i = $ `3 p`の時

f:id:Flkanjin:20210206135256p:plain:left:w417 直線 $x=p$ を軸とした対称移動で、 $y$ 座標はそのままであり、 $x$ 座標が $x'$ になるとすると、移動前後の点を結んだ線分の中点が直線 $x=p$ 上に来るので $\displaystyle\frac{x+x'}{2} = p$ より $x' = 2p - x$ となります。つまり $\begin{pmatrix} x \\ y \\ \end{pmatrix}$ は $\begin{pmatrix} 2p-x \\ y \\ \end{pmatrix}$ に移りますが、これは $y$ 軸対称に移動させたのち、 $2p$ だけ $x$ 方向に平行移動させるアフィン変換となるので $\boldsymbol{A} = \begin{pmatrix} -1 & 0 \\ 0 & 1 \\ \end{pmatrix},$ $\boldsymbol{v} = \begin{pmatrix} 2p \\ 0 \\ \end{pmatrix}$ となります。また、この操作は「 $x$ 方向に $-p$ 平行移動 → $y$ 軸対称移動 → $x$ 方向に $p$ 平行移動」となり、
$\boldsymbol{A} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} -1 & 0 \\ 0 & 1 \\ \end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} -1 & 0 \\ 0 & 1 \\ \end{pmatrix},$ $\boldsymbol{v} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \left[\begin{pmatrix} -1 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} -p \\ 0 \\ \end{pmatrix} + \begin{pmatrix} 0 \\ 0 \\ \end{pmatrix} \right] + \begin{pmatrix} p \\ 0 \\ \end{pmatrix} = \begin{pmatrix} 2p \\ 0 \\ \end{pmatrix}$ *3 と合成によっても同じ行列、ベクトルが求まります。

$ \mathrm{op}_i = $ `4 p`の時

f:id:Flkanjin:20210206140112p:plain:left:w333 直線 $y=p$ を軸とした対称移動で、 $x$ 座標はそのままであり、 $y$ 座標が $y'$ になるとすると、移動前後の点を結んだ線分の中点が直線 $y=p$ 上に来るので $\displaystyle\frac{y+y'}{2} = p$ より $y' = 2p - y$ となります。つまり $\begin{pmatrix} x \\ y \\ \end{pmatrix}$ は $\begin{pmatrix} x \\ 2p-y \\ \end{pmatrix}$ に移りますが、これは $x$ 軸対称に移動させたのち、 $2p$ だけ $y$ 方向に平行移動させるアフィン変換となるので $\boldsymbol{A} = \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \end{pmatrix},$ $\boldsymbol{v} = \begin{pmatrix} 0 \\ 2p \\ \end{pmatrix}$ となります。また、この操作は「 $y$ 方向に $-p$ 平行移動 → $x$ 軸対称移動 → $y$ 方向に $p$ 平行移動」となり、 $\begin{pmatrix} \boldsymbol{A} & \boldsymbol{v} \\ \mathbf{0}_2^{\top} & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & p \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & -p \\ 0 & 0 & 1 \\ \end{pmatrix} =\begin{pmatrix} 1 & 0 & 0 \\ 0 & -1 & 2p \\ 0 & 0 & 1 \\ \end{pmatrix}$ と合成によっても同じ行列、ベクトルが求まります。

ここから $\mathrm{op}_i$ の累積積のようなものを求めてそれを動かしたい点に施して答えを得ることができます。行列計算のある言語を使っていたり、自作の行列計算ライブラリがある場合は1つの行列で表す方法で、そうではなく自分でクラスを作る場合は行列とベクトルの組で表す方法で実装するのが楽なのではないかと思います。

余談

このブログでは西洋の人名に由来するアルゴリズム等の名前はラテン文字で書いたりしているのですが、アフィン変換のアフィン(affine)とはラテン語のaffīnis/affīne(関連)に由来する英単語ですのでカタカナで書いています。

また、 $n$ 次元のベクトル空間に対するアフィン変換は線型独立な $n$ 個のベクトルと始点の変換結果がわかれば一意に決まりますし、始点を原点(零ベクトル)、 $n$ 個のベクトルを標準基底ベクトルにすれば、他の点に対する変換が簡単に求まります。
例えば、ABC189-Eについては $(0,\,0),$ $(1,\,0)$ $(0,\,1)$ の3点の移動先 $f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_2),$ $f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_1),$ $f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_2)$ が分かれば十分です。 $f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_2) = \boldsymbol{A}\mathbf{0}_2 + \boldsymbol{v} = \boldsymbol{v}$ であり、

$\begin{align} f_{\boldsymbol{A}, \boldsymbol{v}}(\boldsymbol{x}) & = f_{\boldsymbol{A}, \boldsymbol{v}}(x\mathbf{e}_1 + y\mathbf{e}_2) = \boldsymbol{A}(x\mathbf{e}_1 + y\mathbf{e}_2) + \boldsymbol{v} = x\boldsymbol{A}\mathbf{e}_1 + y\boldsymbol{A}\mathbf{e}_2 + \boldsymbol{v} \\ & = x(\boldsymbol{A}\mathbf{e}_1+ \boldsymbol{v} - \boldsymbol{v} ) + y(\boldsymbol{A}\mathbf{e}_2 + \boldsymbol{v} - \boldsymbol{v})+ \boldsymbol{v} \\ & = x[f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_1) - f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_2)] + y[f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_2) - f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_2)] + f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_2) \end{align}$

となることからも確かめられます。また、4項目の $x\boldsymbol{A}\mathbf{e}_1 + y\boldsymbol{A}\mathbf{e}_2 + \boldsymbol{v}$ から計算してもいいでしょう。一般の $n$ 次元については $f_{\boldsymbol{A}, \boldsymbol{v}}(\boldsymbol{x}) = \displaystyle\sum_{i=1}^{n}\,x_i \boldsymbol{A}\mathbf{e}_i + \boldsymbol{v} = \sum_{i=1}^{n}\,x_i[f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_i) - f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_n)] + f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_n)$ となります。 $f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_i) - f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_n) = f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{e}_i) - \boldsymbol{v} = f_{\boldsymbol{A}}(\mathbf{e}_i)$ の部分は各基底 $\mathbf{e}_i$ に一次変換のみを施したもので、それらの線型結合に $\boldsymbol{v} = f_{\boldsymbol{A}, \boldsymbol{v}}(\mathbf{0}_n)$ という平行移動を施すとアフィン変換後の位置が得られる、即ち $f_{\boldsymbol{A}, \boldsymbol{v}}(\boldsymbol{x}) = \displaystyle \sum_{i=1}^{n}\,x_i f_{\boldsymbol{A}}(\mathbf{e}_i) + \boldsymbol{v}$ というように解釈できます。

*1:そもそも正方行列であるとも限りません。

*2:ダミー次元の要素が $1$ であるため始域に零ベクトル $\mathbf{0}_{n+1}$ が属さないためです。この条件を無視すれば一次変換と見做せます。

*3:少し複雑な式ですが上の $\boldsymbol{Ba} + \boldsymbol{b}$ を繰り返し適応することでこの式が出てきます。