補間と画像処理

はじめに

　今回は補間を説明し、それを応用した画像処理（拡大・縮小）について説明する。目次は以下の通り。

線形（Linear）補間

双線形（Bilinear）補間

Cubic補間

Bicubic補間

画像処理への応用

線形（Linear）補間

　最初に1次元の線形補間を考える。2次元空間内に曲線 $y=f(x)$ が存在し、 $x$ が $x_0,x_1$ の時の $y$ の値 $y_0,y_1$ が既知であるとする。このとき $x_0\leq x\leq x_1$ を見たす $x$ に対応する $y$ の値を求めたい（下図参照）。

線形補間では、領域内（ $x_0\leq x\leq x_1$ ）の曲線を次式で近似する。

(1) $\begin{align*} f(x)&=\sum_{n=0}^1 a_n x^n\\ &=a_0 + a_1 x \ \end{align*}$

$y_0=f(x_0),y_1=f(x_1)$ より

(2) $\begin{equation*} \begin{pmatrix} 1 & x_0 \\ 1 & x_1 \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \end{pmatrix} \end{equation*}$

したがって

$\begin{align*} \begin{pmatrix} a_0 \\ a_1 \end{pmatrix} &=\dfrac{1}{x_1-x_0} \begin{pmatrix} x_1 & -x_0 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} y_0 \\ y_1 \end{pmatrix} \\ &=\dfrac{1}{x_1-x_0} \begin{pmatrix} x_1y_0-x_0y_1 \\ -y_0+y_1 \end{pmatrix} \end{align*}$

を得る。これらの値を式(1)に代入すると

$\begin{align*} y=\dfrac{y_1-y_0}{x_1-x_0}(x-x_0)+y_0 \end{align*}$

を得る。この式は傾き $(y_1-y_0)/(x_1-x_0)$ を持つ $(x_0,y_0)$ を通る直線であり、わざわざ行列を持ち出して解くまでもない。しかし、このあと説明する補間の式変形と統一するため行列を用いた。

双線形（Bilinear）補間

　次に上の線形補間を曲面に拡張する（下図参照）。

既知の値は $(x_0,y_0),(x_0,y_1),(x_1,y_0),(x_1,y_1)$ 上の値 $z_{00},z_{01},z_{10},z_{11}$ である。曲面の近似式を次式で与える。

(3) $\begin{align*} f(x,y)&=\sum_{m=0}^1\sum_{n=0}^1 a_{mn} x^my^n\\ &=a_{00} + a_{10}x+a_{01}y+a_{11}xy \ \end{align*}$

4つの式

$\begin{align*} z_{00}&=f(x_0,y_0)\\ z_{10}&=f(x_1,y_0)\\ z_{01}&=f(x_0,y_1)\\ z_{11}&=f(x_1,y_1) \end{align*}$

より

(4) $\begin{align*} \begin{pmatrix} 1 & x_0 & y_0 & x_0y_0 \\ 1 & x_1 & y_0 & x_1y_0 \\ 1 & x_0 & y_1 & x_0y_1 \\ 1 & x_1 & y_1 & x_1y_1 \end{pmatrix} \begin{pmatrix} a_{00} \\ a_{10} \\ a_{01} \\ a_{11} \end{pmatrix} = \begin{pmatrix} z_{00} \\ z_{10} \\ z_{01} \\ z_{11} \end{pmatrix} \end{align*}$

を得る。これを解けば $a_{mn}$ を求めることができる。このまま解くのは面倒なので $x_0=0,y_0=0,x_1=1,y_1=1$ として解いてみる。このとき式(4)は

$\begin{equation*} \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} a_{00} \\ a_{10} \\ a_{01} \\ a_{11} \end{pmatrix} = \begin{pmatrix} z_{00} \\ z_{10} \\ z_{01} \\ z_{11} \end{pmatrix} \end{equation*}$

となる。この式は掃き出し法（覚えてますか？）を使えば容易に解くことができる。

$\begin{align*} \begin{pmatrix} a_{00} \\ a_{10} \\ a_{01} \\ a_{11} \end{pmatrix} = \begin{pmatrix} z_{00} \\ z_{10}-z_{00} \\ z_{01}-z_{00} \\ z_{00}+z_{11}-z_{01}-z_{10} \end{pmatrix} \end{align*}$

これらを式(3)に代入し整理すると

(5) $\begin{align*} f(x,y)=x\left\{yz_{11}+(1-y)z_{10}\right\}+(1-x)\left\{yz_{01}+(1-y)z_{00}\right\} \end{align*}$

を得る。この式は $x$ 軸上の比と $y$ 軸上の比から補間することを表している。（下図参照）。

Cubic補間

　ここまでは線形補間を考えてきた。次に3次式の補間を考える。まず最初に1次元の場合である（下図参照）。

補間したい点 $x$ の両隣に2つずつ既知の点 $x_0,x_1,x_2,x_3$ を取る。それぞれに対する $y$ の値も既知である（ $y_0,y_1,y_2,y_3$ ）。近似式として次を考える。

$\begin{align*} f(x)&=\sum_{n=0}^{3}a_nx^n \\ &=a_0+a_1x+a_2x^2+a_3x^3 \end{align*}$

$y_i=f(x_i),i=0,1,2,3$ を使えば

(6) $\begin{align*} \begin{pmatrix} 1 & x_0 & x_0^2 & x_0^3 \\ 1 & x_1 & x_1^2 & x_1^3 \\ 1 & x_2 & x_2^2 & x_2^3 \\ 1 & x_3 & x_3^2 & x_3^3 \end{pmatrix} \begin{pmatrix} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{pmatrix} = \begin{pmatrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \end{pmatrix} \end{align*}$

を得る。これを $a_n$ について解けば良い。式(2)や式(6)の左辺に現れる行列は線形代数ではヴァンデルモンド行列と呼ばれる。

Bicubic補間

　最後に、Cubic補間を曲面の場合に拡張する（下図参照）。

既知の点は図の黄色の座標上にある16個の点である（ $z_{ij}=f(x_i,y_j),0\leq i\leq3,0\leq j\leq3$ ）。この時の近似式は

$\begin{align*} f(x,y)&=\sum_{m=0}^3\sum_{n=0}^3a_{nm}x^my^n \\ &=a_{00}+a_{10}x+\cdots+a_{33}x^3y^3 \end{align*}$

である。これまでと同じことを繰り返せば、16個の式から16行16列の行列で記述される連立方程式を作ることができる。ここまでくると方程式を書き下ろすのもさすがに憚られる。

画像処理への応用

　上で説明したBilinear補間とBicubic補間は画像処理における拡大・縮小に使われている。拡大・縮小の手順は以下の通りである（下図参照）。

元画像を $s$

倍することを考える。

結果画像の各画素の座標 $(x_t,y_t)$

を $1/s$

倍し、その座標が元画像のどこに対応するかを計算する。

結果画像における画素の座標値は常に整数値であるが、それを元画像に戻した位置は一般に実数値で与えられる座標 $(x,y)$

である。

$(x,y)$

近傍の4つの画素とそこでの画素値を使いBilinear補間により $(x,y)$

での画素値を計算し、その値を結果画像の $(x_t,y_t)$

での画素値とする。

周辺16個の画素を使えばBicubic補間を行うことができる。

補間を行う際、画像を3次元空間内の曲面であると考えていることに注意する（下図参照）。

実装

　Bicubic補間は大変なので、Bilinear補間をRustで実装する。式(5)を使うことができる（以下に再掲した）。

$\begin{align*} f(x,y)=x\left\{yz_{11}+(1-y)z_{10}\right\}+(1-x)\left\{yz_{01}+(1-y)z_{00}\right\} \end{align*}$

すなわち、補間したい座標を囲む4つの画素を使い、 $x$ 軸に沿う比 $x:1-x$ と $y$ 軸に沿う比 $y:1-y$ を用いて計算すれば良い。ソースコードはここ。ソースの一部は以下の通り。

// Bilinear補間
pub fn resize_with_bilinear(src: &image::Rgb32FImage, scale: f32) -> image::RgbImage {
    let (src_w, src_h) = src.dimensions();
    let dst_w = (src_w as f32 * scale) as u32;
    let dst_h = (src_h as f32 * scale) as u32;
    
    let mut dst = image::RgbImage::new(dst_w, dst_h);
    for j in 0..dst_h {
        let fy = j as f32 / scale; // 元画像における位置を計算(不動小数点)
        let mut y0 = fy as u32;
        y0 = cap(y0, src_h);
        let y = fy - (y0 as f32);
        let mut y1 = y0 + 1;
        y1 = cap(y1, src_h);
        for i in 0..dst_w {
            let fx = i as f32 / scale; // 元画像における位置を計算(不動小数点)
            let mut x0 = fx as u32;
            x0 = cap(x0, src_w);
            let x = fx - x0 as f32;
            let mut x1 = x0 + 1;
            x1 = cap(x1, src_w);
            let dp = make_color_by_bilinear(y0, y1, x0, x1, y, x, src);
            dst.put_pixel(i, j, dp);
        }
    }    
    return dst;
}

// Bilinear補間

pub fn resize_with_bilinear(src: &image::Rgb32FImage, scale: f32) -> image::RgbImage {

let (src_w, src_h) = src.dimensions();

let dst_w = (src_w as f32 * scale) as u32;

let dst_h = (src_h as f32 * scale) as u32;

let mut dst = image::RgbImage::new(dst_w, dst_h);

for j in 0..dst_h {

let fy = j as f32 / scale; // 元画像における位置を計算(不動小数点)

let mut y0 = fy as u32;

y0 = cap(y0, src_h);

let y = fy - (y0 as f32);

let mut y1 = y0 + 1;

y1 = cap(y1, src_h);

for i in 0..dst_w {

let fx = i as f32 / scale; // 元画像における位置を計算(不動小数点)

let mut x0 = fx as u32;

x0 = cap(x0, src_w);

let x = fx - x0 as f32;

let mut x1 = x0 + 1;

x1 = cap(x1, src_w);

let dp = make_color_by_bilinear(y0, y1, x0, x1, y, x, src);

dst.put_pixel(i, j, dp);

}

return dst;

}

呼び出し元は以下の通り。

fn main() {
    
    let image_path = "c:/Users/seiya.kumada/Pictures/firefox_logo.png";
    let scale = 2.1;
    
    let img = image::open(image_path).unwrap().to_rgb8();
    let dst = imgproc::resize_with_nearest_neighbor(&img, scale); 
    dst.save("./outputs/nearest.jpg").unwrap();

    let img = image::open(image_path).unwrap().to_rgb32f();
    let dst = imgproc::resize_with_bilinear(&img, scale); 
    dst.save("./outputs/bilinear.jpg").unwrap();
}

fn main() {

let image_path = "c:/Users/seiya.kumada/Pictures/firefox_logo.png";

let scale = 2.1;

let img = image::open(image_path).unwrap().to_rgb8();

let dst = imgproc::resize_with_nearest_neighbor(&img, scale);

dst.save("./outputs/nearest.jpg").unwrap();

let img = image::open(image_path).unwrap().to_rgb32f();

let dst = imgproc::resize_with_bilinear(&img, scale);

dst.save("./outputs/bilinear.jpg").unwrap();

}

Rustには画像を扱うためのcrate「image」があるのでこれを利用する。Bilinear補間で浮動小数点を扱いたいので画像を読み込む際に画素値を[0,1]の範囲の浮動小数点に変換している（10行目）。また、補間したい画素値を最近傍の画素値に置き換える処理も合わせて実装した（最近傍補間）。倍率 $s=2.1$ のときの結果は以下の通り。

Bilinear補間の方が色の境界線におけるギザギザが抑制されていることが分かる（アンチエイリアスが効いている）。

まとめ

　今回はいくつかの補間方法を紹介し、その中の一つを画像処理に応用した例を示した。

Kumada Seiya

仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

最小二乗法とその周辺

正多面体が5種類しかないことの証明

補間と画像処理

はじめに

線形（Linear）補間

双線形（Bilinear）補間

Cubic補間

Bicubic補間

画像処理への応用

実装

まとめ

Kumada Seiya

最近の記事

顔認証（DeepFace vs GPT4o）

時系列解析再訪

πの新しい公式

中心極限定理

DBSCANを用いたクラスタリング

レイアウト解析

混合ガウスモデルと最尤推定法

OpenCVのcv::Matに関する小ネタ集

Halide 〜画像処理を高速化する〜

点群からの法線の導出

Homography変換

K-meansクラスタリング

Google Vision APIでOCR

アーカイブ

カテゴリー