双三次補間 - bicubic interpolation

はじめに

画像の拡大・縮小・回転などの操作をする場合、もとの画像に存在しないピクセルを追加する必要がある。そのようなピクセルの追加を補間(interpolation)と呼ぶ。

最近傍補間

最近傍補間(nearest neighbor interpolation)は元の画像のなかで一番近い位置のピクセルの色を、その位置のピクセルの色とする方法だ。

縦横3倍に拡大する例だ。大きい円が元の画像にあるピクセルで小さい円が補間されたピクセルだ。周囲に元画像の1ピクセルぶん余分なピクセルを表示しているのは、双三次補間で必要になるためだ。中央の元画像の3x3ピクセルについて補間して、7x7ピクセルに増やしている。新しく補間されたピクセルの色は一番近いピクセルと同じ色になっている。画像の真ん中を横に切ってRGB値の合計を縦軸とするグラフは以下のようになる。

上の図の左下の部分について元の画像のピクセルについて以下のようになるようにXY座標を設定する。

そして、それぞれのピクセルの色を$c_{00}$, $c_{10}$, $c_{01}$, $c_{11}$とする。そうすると新しい画像のピクセルについて、その座標を(x, y)とするとつぎのようになる。

$$c_{x0} = k_{x0}c_{00} + k_{x1}c_{10} \\ c_{x1} = k_{x0}c_{01} + k_{x1}c_{11}$$

$$c_{xy} = k_{y0}c_{x0} + k_{y1}c_{x1}$$

$$\begin{cases} k_{x0} = 1 & (x \le 0.5)\\ k_{x0} = 0 & (x > 0.5) \end{cases}$$

$$\begin{cases} k_{x1} = 0 & (x \le 0.5) \\ k_{x1} = 1 & (x > 0.5) \end{cases}$$

$$\begin{cases} k_{y0} = 1 & (y \le 0.5)\\ k_{y0} = 0 & (y > 0.5) \end{cases}$$

$$\begin{cases} k_{y1} = 0 & (y \le 0.5)\\ k_{y1} = 1 & (y > 0.5) \end{cases}$$

$c_{xy}$の式に$c_{x0}$, $c_{x1}$の値を代入して展開すると次のようになる。

$$c_{xy} = k_{x0}k_{y0}c_{00} + k_{x1}k_{y0}c_{10} + k_{x0}k_{y1}c_{01} + k_{x1}k_{y1}c_{11}$$

双線形補間

最近傍補間による補間は、それぞれのドットが単一色の正方形として拡大されるので、出来上がった画像は正方形をよせ集めたような画像になる。もうすこし、ましな補間として双線形補間がある。補間する位置の周囲の4点について、それぞれの色の値について近い点の影響がより大きくなるように重みづけして平均を取った値を、その位置の色の値とする。

中央を横に切って縦軸をRGB値のそれぞれの値の合計としてグラフにすると次のようになる。

色の値がx軸上の位置に対して直線的に変化していることがわかる。最近傍補間のときと同じようにXY座標を取る。

同じように4点の色の値を$c_{00}$, $c_{10}$ $c_{01}$, $c_{11}$とすると次のようになる。

$$c_{x0} = k_{x0}c_{00} + k_{x1}c_{10} \\ c_{x1} = k_{x0}c_{01} + k_{x1}c_{11}$$

$$c_{xy} = k_{y0}c_{x0} + k_{y1}c_{x1}$$

$$\begin{aligned} &k_{x0} = 1 - x \\ &k_{x1} = x \\ &k_{y0} = 1 - y \\ &k_{y1} = y \end{aligned}$$

ここで次のようにX成分とY成分とのそれぞれについての、それぞれの点からの距離を定義する。

$$\begin{aligned} &d_{x0} = x \\ &d_{x1} = 1 - x \\ &d_{y0} = y \\ &d_{y1} = 1 - y \end{aligned}$$

すると、上の4つの式はひとつの式にまとめられる。

$$k_{vn} = 1 - d_{vn} (v \in \{x, y\}, n \in \{0, 1\})$$

双三次補間

双線形補間によって生成された画像は、元画像におけるとくに明るいピクセルの周囲が、それ以外の部分よりも目立って白くなってしまう。双線形補間の「線形」の部分に注目してほしい。直線的に補間しているということだ。複数の直線のつなぎ目はなめらかではなく角ばってしまう。色の変化のしかた、つまり色の値の微分値が不連続になる。そこが角になり、その角の部分は変に目立つ。この問題を解決するために色の値の微分値も連続になるように補間するのが双三次補間だ。

中央の白っぽいピクセルの周辺が明るくなり、中央のピクセルだけが目立たないようになっている。中央で横に切って縦軸をRGB値の合計としたグラフを示す。

このように「なめらかな三次式による曲線」上に乗るようにピクセルの色が補間されている。双三次補間に使う式を導く、導入となる式は単純で、結果として導かれる式も単純だ。ただ、はじめの式から最終的にプログラムで使用する式を導出する過程は難しくはないが、ややこしい。

まず「双三次補間」の「双」の部分だ。これはx方向とy方向とあるので「双」となっている。上のふたつの補間で見たように「単」から「双」にするのは、まずx方向について計算し、その結果を使ってy方向について計算すればいい。なので、まずは「単」三次補間について考えればよい。x方向について考えてみよう。

色の値と色の変化の値

基本的な考えかたとしては、補間したいピクセルの左右にある「元画像のピクセル」の色の値と色の変化の値(微分値)とが指定されていて、それを満たす三次式を求めればいいということだ。補間したいピクセルの左右にある「元画像のピクセル」のx座標の値を、それぞれ0, 1とする。左右のピクセルのさらに両隣りのピクセルも含めて、それらのピクセルの色の値を$c_{-1}$, $c_{0}$, $c_{1}$, $c_{2}$とする。そして求める三次式を次のように置く。

$$c_{x} = a + bx + cx^2 + dx^3$$

補間するピクセルの左右のピクセルの色の値がそれぞれ$c_0$, $c_1$なので次の式が成り立つ。

$$\begin{cases} c_0 = a \\ c_1 = a + b + c + d \end{cases}$$

で、両端の色の変化の値をどうするか。色の変化の値を左右の点のそれぞれについて、それらの点の左右の点についての色の変化のしかたから求めることにする。つまり$x = 0$, $x = 1$のそれぞれの点における色の変化の値を次のようにする。

$$c_0' = \frac{c_1 - c_{-1}}{2} \\ c_1' = \frac{c_2 - c_0}{2}$$

上の定義では左右の点における色の変化のしかたを「そのまま」その点での色の変化のしかたとして採用したが、ソフトウェアによって傾きを1.5倍にするなど、バリエーションがある。そのようなバリエーションを表現するために変数$s$を導入する。

$$c_0' = s (c_{-1} - c_1) \\ c_1' = s (c_0 - c_2)$$

下の式で$s = - 0.5$とすると上の式が導ける。ここで$c_{x}$を微分する。

$$c_{x}' = b + 2cx + 3dx^2$$

ここまでの話をまとめると次のような4つの式を導くことができる。

$$\begin{cases} a &= c_0 \\ a + b + c + d &= c_1 \\ b &= s (c_{-1} - c_1) \\ b + 2c + 3d &= s (c_0 - c_2) \end{cases}$$

これを行列で表現するとつぎのようになる。

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 2 & 3 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} = \begin{pmatrix} c_0 \\ c_1 \\ s (c_{-1} - c_1) \\ s (c_0 - c_2) \end{pmatrix}$$

xの三次式の係数を求める

掃き出し法によって逆行列を求める。もとの行列の横に単位行列を並べた行列の左半分が単位行列になるように行基本変形を加えた結果の行列の右半分が元の行列の逆行列になる。行基本変形とは「2つの行の入れ替え」「ある行の0でない定数倍」「ある行に他の行の定数倍を加える」の3つだ。

$$\begin{aligned} \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 2 & 3 & 0 & 0 & 0 & 1 \end{pmatrix} &= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & -1 & 1 & -1 & 0 \\ 0 & 0 & 2 & 3 & 0 & 0 & -1 & 1 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & -3 & 3 & -2 & -1 \\ 0 & 0 & 0 & 1 & 2 & -2 & 1 & 1 \end{pmatrix} \end{aligned}$$

よって次のようになる。

$$\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ -3 & 3 & -2 & -1 \\ 2 & -2 & 1 & 1 \end{pmatrix} \begin{pmatrix} c_0 \\ c_1 \\ s (c_{-1} - c_1) \\ s (c_0 - c_2) \end{pmatrix}$$

つまり次のような4つの式が成り立つ。

$$\begin{cases} a = c0 \\ b = s(c_{-1} - c_1) \\ c = -3c_0 + 3c_1 - 2s(c_{-1} - c_1) - s(c_0 - c_2) \\ d = 2c_0 - 2c_1 + s(c_{-1} - c_1) + s(c_0 - c_2) \end{cases}$$

$c_{-1}$, $c_0$, $c_1$, $c_2$について、まとめると次のようになる。

$$\begin{cases} a = c0 \\ b = sc_{-1} - sc_1 \\ c = -2sc_{-1} - (s + 3)c_0 + (2s + 3)c_1 + sc_2 \\ d = sc_{-1} + (s + 2)c_0 - (s + 2)c_1 - sc_2 \end{cases}$$

行列で表現すると次のようになる。

$$\begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ s & 0 & -s & 0 \\ -2s & -(s+3) & 2s+3 & s \\ s & s + 2 & -(s + 2) & -s \end{pmatrix} \begin{pmatrix} c_{-1} \\ c_0 \\ c_1 \\ c_2 \end{pmatrix}$$

元のピクセルの色の値にかかる係数を求める

ここで求める色の値は$c_x = a + bx + cx^2 + dx^3$なので次のように表すことができる。

$$\begin{align} c_x &= \begin{pmatrix} 1 & x & x^2 & x^3 \end{pmatrix} \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} \\ &= \begin{pmatrix} 1 & x & x^2 & x^3 \end{pmatrix} \begin{pmatrix} 0 & 1 & 0 & 0 \\ s & 0 & -s & 0 \\ -2s & -(s+3) & 2s+3 & s \\ s & s + 2 & -(s + 2) & -s \end{pmatrix} \begin{pmatrix} c_{-1} \\ c_0 \\ c_1 \\ c_2 \end{pmatrix} \\ &= \begin{pmatrix} k_{-1} & k_0 & k_1 & k_2 \end{pmatrix} \begin{pmatrix} c_{-1} \\ c_0 \\ c_1 \\ c_2 \end{pmatrix} \end{align}$$

$$\begin{align} k_{-1} &= sx - 2sx^2 + sx^3 \\ k_0 &= 1 - (s + 3)x^2 + (s + 2)x^3 \\ k_1 &= -sx + (2s + 3)x^2 - (s + 2)x^3 \\ k_2 &= sx^2 - sx^3 \end{align}$$

ここで、つぎのように置く。$d_n$は補間される点から、4つのそれぞれの点へのX成分についての距離になっている。

$$\begin{align} d_{-1} &= x + 1 \\ d_0 &= x \\ d_1 &= 1 - x \\ d_2 &= 2 - x \end{align}$$

すると4つの係数$k_{-1}$, $k_0$, $k_1$, $k_2$はそれぞれ次のように表すことができる。

$$\begin{align} k_{-1} &= s(d_{-1} - 1) - 2s(d_{-1} - 1) ^ 2 + s(d_{-1} - 1) ^ 3 \\ &= -4s + 8sd_{-1} - 5sd_{-1}^2 + sd_{-1}^3 \\ k_0 &= 1 - (s + 3)d_0^2 + (s + 2)d_0^3 \\ k_1 &= -s(1 - d_1) + (2s + 3)(1 - d_1)^2 - (s + 2)(1 - d_1)^3 \\ &= 1 - (s + 3)d_1^2 + (s + 2)d_1^3 \\ k_2 &= s(2 - d_2)^2 - s(2 - d_2)^3 \\ &= -4s + 8sd_2 - 5sd_2^2 + sd_2^3 \end{align}$$

これは次のようにまとめることができる。

$$\begin{cases} k_n = 1 - (s + 3)d_n^2 + (s + 2)d_n^3 & (n \in \{0, 1\}) \\ k_n = -4s + 8sd_n - 5sd_n^2 + sd_n^3 & (n \in \{-1, 2\}) \end{cases}$$

x方向とy方向

y方向についても同じように係数を求めることができる。ここで新たに、つぎのように置く。

$$\begin{align} d_{x,-1} &= x + 1 \\ d_{x0} &= x \\ d_{x1} &= 1 - x \\ d_{x2} &= 2 - x \\ d_{y,-1} &= y + 1 \\ d_{y0} &= y \\ d_{y1} &= 1 - y \\ d_{y2} &= 2 - y \end{align}$$

すると、つぎのようにx方向とy方向について、それぞれ4つの係数が求まる。

$$\begin{cases} k_{vn} = 1 - (s + 3)d_{vn}^2 + (s + 2)d_{vn}^3 & (v \in \{x, y\}, n \in \{0, 1\}) \\ k_{vn} = -4s + 8sd_{vn} - 5sd_{vn}^2 + sd_{vn}^3 & (v \in \{x, y\}, n \in \{-1, 2\}) \end{cases}$$

そして、$c_{-1-1}$, $c_{0-1}$, $c_{1-1}$, $c_{2-1}$, $c_{-10}$, $c_{00}$, ..., $c_{22}$の16のピクセルについて、$c_{ab}$について、$k_{xa}k_{yb}$をかけたものの総和を取れば(x, y)の位置におけるピクセルの色の値が求められる。

まとめ

双三次補間について「色の変化をなめらかにする」という目的から始めて実際にコードで使える式を導いた。ややこしいが、本質的に難しい部分はない。「色の値」と「色の値の変化」を指定することで、xに対する三次多項式を求めたうえで、それを変形することで「元画像のそれぞれのピクセルに対する係数」を求めた。ここまで求めれば、あとはそのままコードにするだけだ。