画像リサイズのうんちく (補間フィルタ)

- 画像リサイズのうんちく
   - https://qiita.com/yoya/items/95c37e02762431b1abf0

こちらの記事からの派生です。

# 補間フィルタ

ビットマップ画像のリサイズ/縮小拡大は、各ピクセルの仕切り直しと考える事もできます。(主流は点光源の波の組み合わせですが、ここでは分かりやすいグリッドの方で説明します。

| | src | resample  | dst |
| ---| --- | --- | --- |
|拡大 |![3x3colors-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/86962af4-8a9c-83a8-169a-1c854d1be697.png) |![3x3-3x3-dot16.png](https://qiita-image-store.s3.amazonaws.com/0/1798/72943b4a-b21c-b67a-d613-1c012986977b.png) | ![3x3-3x3-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/a5a927a2-6257-e34b-7357-7ba2d4a7d147.png) | ![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/ae79a269-dbf0-b94a-e341-7fd8dbc97e93.png)|
|縮小| ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/884650ab-e0a9-e310-8a49-2495e5cb936c.png) | ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/c1d31172-28cc-cd57-8242-5ee156be02ce.png) | ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/4d7cb289-535d-9490-42d0-30940b79dcab.png) |

近傍の色を参考にこの白い隙間を埋める処理方式によって、リサイズ処理の結果が変わってきます。
色を埋める処理を補間フィルタ、その具体的なアルゴリズムを補間メソッドと呼びます。
レガシーな印象もありますが今でもよく使われる代表的な補間メソッドを紹介します。

# 補間カーネル

拡大でも縮小でも周囲のピクセルを適度な割合で混ぜて補間を行います。その混ぜ方は１次元の重み付け数列で表現できて、補間カーネルと呼びます。参考までに代表的なメソッドを並べます。


|Nearest-Neighbor|Bi-Linear|
|---|---|
|![nearest.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/c14acf3d-aecf-6b54-b67e-e3f5ec899008.png)| ![bilinear.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/1d68c4e2-d9ac-fe32-9d1b-56b46b51fc78.png) |
Bi-Cubic (b:1/3,c:1/3, mitchell)|Lanczos (lobe:4, lanczos4)|
| ![mitchell.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/8a338454-b186-05d9-f1ea-1834c12ba6d5.png) | ![lanczos4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/9fe2d999-967f-ef5f-8e5a-618e9d84f7b4.png) |

形状から、Nearest を Point フィルタ、Bi-Linear を Triangle フィルタ、Tent フィルタ、又は 2D だと Cone フィルタと呼ぶ事もあります。ちなみに、ImageMagick のフィルタ名は、この point, triangle を採用しています。
これら以外にも沢山の補間メソッドが提唱されています。

# Nearest-Neighbor

実用的な補間メソッドとして最も単純で最速です。隣からピクセルをコピーしてくるだけです。

|src | resample  | enlarge | interpolate | dst |
| --- | --- | --- | --- | ---- |
|![3x3colors-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/86962af4-8a9c-83a8-169a-1c854d1be697.png) |![3x3-3x3-dot16.png](https://qiita-image-store.s3.amazonaws.com/0/1798/72943b4a-b21c-b67a-d613-1c012986977b.png) | ![3x3-3x3-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/a5a927a2-6257-e34b-7357-7ba2d4a7d147.png) | ![68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f313739382f61356139323761322d363235372d653334622d373335372d3762613264346137643134372e706e67.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/ac83b09d-209d-e36b-d10b-ac16f83d47af.png) |  ![3x3colors-sample200-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/8255f1b8-ea02-5c6c-0b07-cdebaea0e68b.png) |


実用的には、画像ビューア(ブラウザ含む)のウィンドウ枠をマウスで掴みグリグリ画像のサイズを変える時だけ Nearest-Neighbor で素早く表示し、マウスが止まってサイズが変わくなった時に改めて重たいけど画質が良い補間メソッドで表示し直す。といった使われ方をよくされます。

あと、色が変わらないといった稀有な特徴があり、GIF や PNG8 等のパレット画像のリサイズでは、この補間方式が使われる事も多いです。

分かりやすい欠点として、Nearest-Neighbor は拡大するにつれ、ピクセルが四角いまま膨らみドット絵のような表示になります。ジャギーといった表現をよくします。
逆に縮小する時はピクセルをところどころ読み飛ばすので、運次第で見た目と全然違う色、いわゆる偽色に変わったり、特定パターンによる模様が現れたりします。

Bi-Linear はそれらの問題をある程度解決します。

# Bi-Linear

空白ピクセルの上下左右に１つしか色のピクセルが存在しない場合はそれをコピーしますが、左右又は上下にある場合はその二つの平均 (a+b)/2、上下左右４つある場合はその４つを平均 (a+b+c+d)/4 、といった具合に色を混ぜます。

|src | resample  | enlarge | interpolate | dst |
| --- | --- | --- | --- | ---- |
|![3x3colors-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/86962af4-8a9c-83a8-169a-1c854d1be697.png) |![3x3-3x3-dot16.png](https://qiita-image-store.s3.amazonaws.com/0/1798/72943b4a-b21c-b67a-d613-1c012986977b.png) | ![3x3-3x3-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/a5a927a2-6257-e34b-7357-7ba2d4a7d147.png) | ![bi-linear.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/1043bff6-cded-20a3-5a65-ae54e70741cf.png) | ![bi-linear-3x3x2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/c7a0744a-6ac5-f405-7784-e59f871ecf90.png) |

Bi-Linear の欠点として、ジャギーが軽減される代わりに全体的にピンボケたように見えます。
また、テントの形をした補間フィルタは C1 連続でない為に、部分部分急激な色の変化をもたらし偽の輪郭が発生する事があります。

![ダウンロード.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/7c8c1aae-d69e-337c-e729-0065f1fbe9ad.png)

# Bi-Cubic B,Cパラメータ

Bi-Linear に無かった C1 連続を導入して不自然さをある程度軽減します。隣の更に隣のピクセルまで参照します。

| ![Bi-Cubic.png](https://qiita-image-store.s3.amazonaws.com/0/1798/f29a47fe-4c61-bfad-ce46-6e7b0ed7d544.png) |
|---|
|転載元) https://en.wikipedia.org/wiki/Bicubic_interpolation|

三次式の計算で処理はそこそこ重たいですが、"質"の良い補間メソッドです。

2つの自由度があり、B (Basis?),C(Cardinal) パラメータを組み合わせる事で、色んなフィルタを作り出せます。Cubic Family という呼び方もされます。

代表的な Cubic フィルタを並べます。

| Hermite  B:0, C:0  | General B:1, C:0|
|:--|:--|
|![hermite.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/b7111b2d-877b-aa60-415e-e194350d6916.png) | ![general.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/9e9e0915-53c2-cbb1-12dd-f557c8c51bad.png) |
| Catmull-Rom B:0, C:1/2| Mitchell B:1/3, C:1/3|
| ![catmul.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/d4b78898-fdea-9295-2de2-2174ceedec8c.png) | ![mitchell.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/0385ea8e-977c-54f8-1023-52279d20768d.png) |

なお、実験にて Mitchell がバランスが良いとされてます。

|![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/4cfbe918-c300-e73f-95a3-a23e3b4b4e9d.png)|
|---|
| 転載元) http://www.imagemagick.org/Usage/filter/#mitchell - [論文](https://www.cs.utexas.edu/~fussell/courses/cs384g-fall2013/lectures/mitchell/Mitchell.pdf) |


## 計算方法

まず B,C を元に3次方程式の係数を算出します。

```js
function cubicBCcoefficient(b, c) {
    var p = 2 - 1.5*b - c;
    var q = -3 + 2*b + c;
    var r = 0;
    var s = 1 - (1/3)*b;
    var t = -(1/6)*b - c;
    var u = b + 5*c;
    var v = -2*b - 8*c;
    var w = (4/3)*b + 4*c;
    return [p, q, r, s, t, u, v, w];
}
```

この係数を使って Cubic の数列を計算できます。

```js
function cubicBC(x, coeff) {
    var [p, q, r, s, t, u, v, w] = coeff;
    var y = 0;
    var ax = Math.abs(x);
    if (ax < 1) {
      //y = p*(ax*ax*ax) + q*(ax*ax) + r*(ax) + s;
        y = ((p*ax + q)*ax + r)*ax + s;
    } else if (ax < 2) {
      //y = t*(ax*ax*ax) + u*(ax*ax) + v*(ax) + w;
        y = ((t*ax + u)*ax + v)*ax + w;
    }
    return y;
}
```

# Lanczos lobeパラメータ

信号処理で大変便利な Sinc 窓というものがあります。

|![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/a0d01b24-648c-5779-b03c-b7a4eb418fb3.png)|
|---|
|(c) https://en.wikipedia.org/wiki/Sinc_filter |

これは永遠に横(x軸方向)に広がる関数なので、更に
![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/c40f811f-13f5-43a0-5ba1-ef2c3ab48da4.png)
を計算することで、波の広がりを一定区間に抑えたのが Lanczos 窓です。

以下のグラフは分母の n が 2,3,4 の Lanczos 窓です。

|lobe|グラフ|
|---|---|
| lobe:2 | ![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/6a035f51-85d8-788c-cec4-25e968f7ef02.png) |
| lobe:3 | ![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/c1bb5c57-8b3c-a4ee-4154-c8eb745d5086.png) |
| lobe:4|  ![image.png](https://qiita-image-store.s3.amazonaws.com/0/1798/ba88ae9c-df61-b7ed-1d69-384b477f64ed.png)|

n でどこ区間まで波を広げるのか調整できます。パラメータ名として Lobe がよく使われるのと、n:3 を lanczos3, n:4 を lanczos4 のように呼称する事もあります。

Sinc は LPF(低域通過フィルタ)の性質もある為、Lanczos は縮小リサイズに向いています。ただし、sin関数を多用するのと実用的にカーネル窓を広めにとるので大変重たいメソッドです。

Lobe 値を増やすほど良い結果を期待できますが、その分処理が重たくなります。よく使われるのは Lobe:3 か 4 です。

## 計算方法

sinc は sin を使います。

```js
function sinc(x) {
    var pi_x = Math.PI * x;
    return Math.sin(pi_x) / pi_x;
}
```

sinc 関数は無限に広がるので、そのまま使うと補間カーネルが無限の大きさを持ってしまいます。lanczos はこれを一定幅で抑える工夫をします。この一定区間に収まる事をコンパクトサポートといった表現をします。

```js
function lanczos(x, lobe) {
    if (x === 0) {
        return 0;
    }
    if (Math.abs(x) < lobe) {
        return sinc(x) * sinc(x/lobe);
    }
    return 0;
}
```

sinc を2回呼ぶので結果的に sin を2回使います。sin はまともに計算すると大変重たい関数です。

# Pixel Mixing

これは上記の補間メソッドとは一風変わっていて、グリッドを仕切り直した時に、ピクセルの面積比で足し混みます。

|src| 3x3=>2x2 |
|---|---|
|![3x3colors-dot32.png](https://qiita-image-store.s3.amazonaws.com/0/1798/86962af4-8a9c-83a8-169a-1c854d1be697.png)  |![3x3colors-dot32-grid2x2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/4e7a0d4c-eb7a-bc57-755e-b3a36bc3d4c1.png) |

左上のピクセルの混ぜ方

|src| A | B | C | D | (A*4 + B*2 + B*2 + D*1) / 9 | dst|
|---|---|---|---|---|---|---|
| ![3x3colors-dot32-grid2x2-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/e50be53e-9882-8353-35ce-2e3efe93735e.png) |![3x3colors-dot32-grid2x2-piece1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/4f6ef984-0ef7-b54a-2877-8ff4cb8ff7cf.png) | ![3x3colors-dot32-grid2x2-piece2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/47bc2d1f-37a3-b103-11dd-a647e4012668.png) | ![3x3colors-dot32-grid2x2-piece3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/49a91967-73d4-ca79-bbc4-afe294f804b4.png) | ![3x3colors-dot32-grid2x2-piece4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/e522c8a1-d861-eed3-7d93-2ca4141604c9.png) | ![3x3colors-dot32-grid2x2-00のコピー.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/28f456b4-9399-31a5-4c82-20e125c34e85.png) | ![3x3colors-dot32-grid2x2-00のコピー2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1798/aa38e2ac-104d-dc0c-354e-6eb2d2f6a3c7.png) |
# 参考URL

- ImageMagick リサイズ補間アルゴリズム
  -  https://qiita.com/yoya/items/b1590de289b623f18639
- https://en.wikipedia.org/wiki/Kernel_(image_processing)#Edge_Handling