射影変換って結局なにすればええんや #JavaScript

モチベーション

Photoshopの自由変形(ctrl+T)みたいなのを実装したかった
なぜかJSでネイティブで書きたかった

概略

要件定義

input : 射影前の画像および射影後の4点
output : 変形した画像

実装

射影前後の座標の変化から射影関数を求める
output画像のピクセルの位置に相当する、input画像上の点を上記射影関数の逆写像から求める
その点は確率1で格子点上にないので、周囲のピクセルから補間を行う

射影関数

射影変換の一般系は、$f:(x,y)\rightarrow(X,Y)$とすると

(X,Y) = f(x, y) = \bigg(\frac{Ax+By+C}{Gx+Hy+1}, \frac{Dx+Ey+F}{Gx+Hx+1}\bigg)

である。
定数は$A\dots H$の8個であるので連立8元一次方程式となるが、4点およびその移動先、合計8点を指定してやれば解けるはずである。

計算量削減のため、遠近法の射影変換パラメータ計算の高速化を参考にし、$4*4$の行列計算に落とし込む。($E$の式にtypoがあるので注意)
式$(11)$の$G,H$の部分について、

G = a - Cb\\
H = c - Cd\\
G = e - Ff\\
H = g - Fh

とした時に、

  \left\{
    \begin{array}{l}
      C =\frac{h(a-e)-f(c-g)}{bh-fd}\\
      F =\frac{d(a-e)-b(c-g)}{bh-fd}
    \end{array}
  \right.

と解ける。$A,B,D,E,G,H$はこれらから簡単に求まる。

場合分け

色々と考えていくと、移動先の点に$(0,0)$が含まれる場合などで、情報量が減って逆行列が求められなくなる。適宜 "うまい場所に変形→平行移動" のように対策をしてやる必要があると思う。

私の場合は、左上の点と右下の点の中心に原点が来るように変形してから移動した。(これでももちろんバグり得る)

画素補間

射影変換に限らず、ほとんどの変形では(格子点→格子点)となるとは限らない。
そのため、像の格子点は始閾からのサンプリングによって得る。これを**補間(interpolation)**という。

Dst(X, Y) = Interpolation \big(Src,  f^{-1}(X, Y) \big)

出力の際はBicubic法を用いればいいが、メタメタに重いのでプレビューにおいてはNearest Neighborを用いると良いと思う(めっちゃジャギるけど)。

境界処理

Bicubicは周辺16画素を参照するので、縁の場合にundefinedになる。

もっとも縁のピクセルで埋めたり、鏡像(折り返し)扱いにしたり、周りに透明なピクセルを配置したりするなど様々にやりようはあるので、目的によって実装仕分ければ良い。

コード(概略だけ)

projection.js

function projection(img, dst_pts, output_size) { // counterclockwise from upperleft

  let src_pts = [[0, 0], [0, img.height], [img.width, img.height], [img.width, 0]];
  const [A, B, C, D, E, F, G, H] = calc_proj_params(src_pts, dst_pts);
  const [w, h] = output_size;
  let output = new ImageData(w, h);
  let dw = parseInt((src_pts[2][0] - src_pts[0][0]) / 2);
  let dh = parseInt((src_pts[2][1] - src_pts[0][1]) / 2);

  for (let i = 0; i < w * h; i += 1) {
    let [X, Y] = [i % w + dw, parseInt(i / w) + dh];
    let x = (A * X + B * Y + C) / (G * X + H * Y + 1);
    let y = (D * X + E * Y + F) / (G * X + H * Y + 1);
    if (1 < x && x < img.width - 1 && 0 < y && y < img.height - 1) {
      let b = nearest_neignbor(img, x, y);
      //let b = bicubic(img, x, y);
      output.data[4 * i] = b[0];
      output.data[4 * i + 1] = b[1];
      output.data[4 * i + 2] = b[2];
      output.data[4 * i + 3] = b[3];
    }
  }
  return output;
}

まとめ

処理は煩雑だがアルゴリズム自体は割と単純
補間アルゴリズムは普通に他の場所でも使えそう