Edited at

ImageMagick リサイズ補間アルゴリズム


はじめに

ImageMagick は画像の拡大や縮小、いわゆるリサイズ処理を制御するオプションが幾つもあります。

-resize, -thumbnail, -scale, -sample, -resample, -geometry。

これらのオプションと、リサイズのちょっとだけ細かい話をします。


説明しないオプション

少し特殊なリサイズとして、-liquid, -magnify(pixel art scaling), -adaptive-resize 等がありますが、今回は扱いません。


画像のリサイズとは?

ここではビットマップ画像の拡大や縮小処理の事とします。

画像処理的にはビットマップのグリッドの仕切り直しと捉える事もできます。 (主流は点光源を波でサンプリングした信号ですが、ここでは置いておく)


  • 拡大

src
resample
dst



画像の拡大を行うと、元のピクセルの位置から広げて配置し直します。

この図の空白の部分をどう埋めるのかが、補間(Interpolation)アルゴリズムです。


4隅の扱い (2018/06/14 追記)

上記の拡大イメージはよく見ると、右はじ1列と、下はじ1行が余ってますよね。

実は、ImageMagick は画像の4隅をあわせるので、これと少し異なります。

具体的にはこうです。

src
resample
dst



ただし、この方式だと画像の縦横サイズの拡大率と、ピクセルの広がり方が違ってきます。

以下の例では縦横サイズは2倍で、ピクセルの広がりは 2.5倍です。

src
align_corners=False
align_corners=True




通常の使い方だとどちらでも困りませんが、画像をぴったり 200% 引き伸ばしたいといった場合に、align_corners=True だとキリの悪い広がり方をするので、元の色をあまり維持できないデメリットがあります。

ちなみに、TensorFlow の tf.image.resize_images がデフォルトで前者(厳密なスケールでピクセルを広げる)の動きをします。align_corners=True を指定すると ImageMagick と同じく後者(4隅をあわせる為に1pixel多めにピクセルを広げる)に合わせます。


左上寄せ、右下寄せ

align_corners=False 相当の画像は ImageMagick だと distort で再現できます。

左上(←↑)を基準にするので右下(→↓)に隙間が出来るのですが、折角なので逆に右下基準バージョンも作ってみます。

$ convert 3x3primary.png -filter triangle -set option:distort:viewport 6x6 \

-distort SRT "0,0 1.66 0 0,0" left_top-aligned.png
$ convert 3x3primary.png -filter triangle -set option:distort:viewport 6x6 \
-distort SRT "0,0 1.66 0 1,1" right_bottom-aligned.png

left_top-aligned.png

right_bottom-aligned.png




補間アルゴリズム

ピクセルを広げた隙間を埋める補間アルゴリズムを ImageMagick はオプションで細かく指定出来ます。

縮小を行う際にも、どのようにピクセルを削除するか、又は混ぜるかで同様の補間処理があります。


サンプル画像

比較用サンプルとして、ドット単位のテスト画像と、実際のイラスト画を用います。

% echo  P3  3 3  9 \

9 2 3 9 7 1 9 9 0 \
7 4 7 7 7 4 7 9 0 \
0 6 9 0 8 6 0 9 0 | convert - 3x3colors.png

3x3colors.png (+ ドット拡大x16)

また、水緑様のイラストから髪飾りの画像を使わせて頂きます。


-sample (最速)

Nearest Neighbor と呼ばれる、単純で速いアルゴリズムで処理します。

引き延ばす時には隣のピクセルをコピーし、縮小する時には単にピクセルを削除するだけです。新しい色を作らなくて済むのも大きな特徴です。

あえてドット絵のような画像を作りたい場合や、GIF や PNG8 のように色数が増えると面倒な時に便利です。


拡大

% concert 3x3colors.png -sample 200% 3x3colors-sample200.png

% convert ornament.png -sample 200% ornament-sample200.png

original
-sample 200%


斜めの線にドット絵のようなカクカクが付き易いです。よく、ジャギーといった表現を使います。

また、元の画像にない人工的な歪みが出るのを、アーチファクトと呼びます。医療画像だと誤診を誘発する致命的なやつです。


縮小

% concert 3x3colors.png -sample 50% 3x3colors-sample50.png

% convert ornament.png -sample 50% ornament-sample50.png

original
-sample 50%


こちらも斜めの線がジャギーになり易いです。


-scale (次に速い)


拡大

% convert 3x3colors.png -scale 200% 3x3colors-scale200.png

% convert ornament.png -scale 200% ornament-scale200.png

拡大は -sample と同じです。


縮小

% convert 3x3colors.png -scale 50% 3x3colors-scale50.png

% convert ornament.png -scale 50% ornament-scale50.png

Pixel Mixing アルゴリズムを使います。Pixel Averaging, Area map とも呼ばれます。

縮小前のピクセルは数が多いので、それらの色の平均を使います。中途半端に重なるピクセルはカバー率で重み付けします。

original
-sample 50%


曲線が -sample の縮小よりも少し滑らかですが、少しボヤけます。

ジャギーさも少し残ります。


-resize (お勧め)

深く考えずに画像のサイズを変えたいときは、-resize を使うと良いでしょう。


拡大

% convert 3x3colors.png -resize 200% 3x3colors-resize200.png

% convert ornament.png -resize 200% ornament-resize200.png

Bi-Cubic Family の中でバランスの良いと言われる Mitchell フィルタを用います。

original
-resize 200%


滑らかに拡大出来ます。ただし結構ボヤけます。


縮小

% convert 3x3colors.png -resize 50% 3x3colors-resize50.png

% convert ornament.png -resize 50% ornament-resize50.png

Lanzcos フィルタを用います。(ただし、パレット画像 or 透明度がついてる場合には縮小でも Mitchell を適用)

エイリアシング対策のされたフィルタです。アーチファクトノイズが乗りにくいのが特徴です。

original
-sample 50%


滑らかに縮小しますが、こちらも画像がボヤけます。


-resize & -unsharp

-resize のボケ対策には unsharp を併せて使うと良いです。

% convert ornament.png  -resize 200% -unsharp 10x5+0.7+0  ornament-resize200-unsharp.png

% convert ornament.png -resize 50% -unsharp 10x5+0.7+0 ornament-resize50-unsharp.png

unsharp のパラメータは自分の好みもありますが、ここでは分かりやすいよう少し強めにしてます。2015年当時の GIMP は 12x6+0.5+0 だそうです > http://freeparticle.hatenablog.com/entry/2015/01/16/230956


拡大

original
-resize 200%
-unsharp 10x5+0.5+0




縮小

original
-resize 50%
-unsharp 10x5+0.5+0




unsharp について

なお、シャープ(sharpness)にするのに unsharp を使うのは、アナログ写真の時代からある unsharp-masking (USM) に由来します。ぼかした上で反転した画像のマスクを作り、それを合成する事でボケを相殺します。

https://en.wikipedia.org/wiki/Unsharp_masking


-thumbnail (メタデータ削除)

画像の変換アルゴリズムは -resize と同じですが、Exif 等のメタデータを削除します。

Exif には撮影位置や(画像上書き前の)サムネール画像が入る事もあるので、不特定多数に公開する、又は漏れる可能性のある写真では削った方が身の為です。自宅の位置とか他人に知られたく無いですよね。


-resample (dpi合わせ)

メタデータの dpi を指定した値で上書きすると同時に、印刷上の画像サイズが dpi 上書き前と変わらないように画像データをリサイズします。


dpi って?

dpi は物理的な解像度で、1 inch に何pixel 詰めるかの単位です。

例えば、画像をプリンタで印刷するときは dpi に応じて大きさが決まりますし、

WYSIWYG(ウィジウィグ) 環境ではモニタ表示にも影響します。


具体例

macOS だと Retina ディスプレイでスクリーンショットをとると、解像度が既存の倍の 144 dpi で記録されます。

% identify ss.png

ss.png PNG 1064x560 1064x560+0+0 8-bit sRGB 120732B 0.000u 0:00.000
% identify -verbose ss.png | grep -A 2 Resol
Resolution: 56.69x56.69
Print size: 18.7687x9.87829
Units: PixelsPerCentimeter

Resolution が cm 単位なので inch に変換すると、56.69[px/cm] * 2.54 [cm/inch] = 144 [px/inch]

-resample オプションを使うと、これを既存モニタ向けの 72dpi 相当に簡単に変換できます。inch 指定、デフォルトの cm指定、 どちらでも良いです。

% convert ss.png -resample 28.35  ss2.png

% convert ss.png -units PixelsPerInch -resample 72 ss3.png
% identify ss2.png ss3.png
ss2.png PNG 532x280 532x280+0+0 8-bit sRGB 43726B 0.000u 0:00.000
ss3.png PNG 532x280 532x280+0+0 8-bit sRGB 43726B 0.000u 0:00.000


-geometry

このオプションでも -resize と同じアルゴリズムでリサイズ出来ますが、利用はおすすめ出来ません。

ImageMagick は convert 以外にも色んなコマンドがあって、各々で -geometry が違う意味を持たされている多義的なオプションなのと、歴史的な都合で残してるだけで出来る限り使うのは避けてね。と公式にもあります。

Geometry is a very special option.

The operator behaves slightly differently in every IM command, and often in special and magical ways.
The reasons for this is mostly due to legacy use and should be avoided if at all possible.


-filter 付きで -resize

-filter で任意の補間フィルタを適用できます。


-point, -scale, -resize と -filter 〜 の関係

option
-filter (enlarge/reduce)

-sample
point

-scale
point / triangle(と似てる pixel mixing)

-resize
mitchell / lanczoc


補間フィルタ一覧

-list filter でフィルタの一覧が出るので、全種類を簡単に試せます。

for f in `convert -list filter` ; do convert koishi.png -filter $f -resize 10%  filter/$f.png ; done

これを見るだけでも、縮小には Lanczos が良さそうな感じがします。


filter:verbose=1

-define filter:verbose=1 をつけると、実際に適用されるアルゴリズム名や詳細なパラメータ、実際に補間する時の重み付け数列を確認出来ます。

% convert in.png -define filter:verbose=1 -filter box -resize 100x100 out.png

# Resampling Filter (for graphing)
#
# filter = Box
# window = Box
# support = 0.5
# window-support = 0.5
# scale-blur = 1
# practical-support = 0.5

0.00 1
0.01 1
0.02 1
<略>
0.49 1
0.50 1
0.50 0


グラフ

出力された数列は補間する際の重み付けで使う値です。

アルゴリズム別にグラフにしてみます。

% # Nearest Neighbor

% convert logo: -define filter:verbose=1 -filter box -resize 100% null:
% # Bi-Linear
% convert logo: -define filter:verbose=1 -filter triangle -resize 100% null:
% # Bi-Cubic (B:1/3,C:1/3 - Mitchell)
% convert logo: -define filter:verbose=1 -filter mitchell -resize 100% null:
% # Lanczos (Lobe:3)
% convert logo: -define filter:verbose=1 -filter lanczos -resize 100% null:



  • ■ box は 0 か 1 か。ピクセルを混ぜない。


  • ■ triangle は線形でピクセルを混ぜる。0 と 1 で傾きが急に変化するのが欠点。


  • ■ mitchell は更に一個外のピクセルまで考慮して triangle の欠点を補う。


  • ■ lanczos は mitchell の更に。と言いたいけど、そこは本質でなく sinc で LPF をかけてる。

詳しくはこちらの解説が図付きで分かりやすいです。


-filter cubic

cubic フィルタを指定すると Bi-Cubic として知られるアルゴリズムで補間します。

box(Nearest-Neighbor) や triangle(Bi-Linear) は2点の輝度値から計算しますが、Bi-Cubic は更にもう一つ外を含め4点を使う事で滑らかに補間できます。

転載元) https://en.wikipedia.org/wiki/Bicubic_interpolation

Bi-Cubic は B(b-spline) と C(cardinal) のパラメータを 0〜1 の間で調整して色々なフィルタを作り出せます。

Cubic ファミリーといった呼び方もされ、B,C に応じて以下のようなフィルタが存在します。

name
B
C

Hermite
0
0

General
1
0

Catmull-Rom
0
1/2

Mitchell
1/3
1/3

対応するソースコードは、MagickCore/resize.c にあります。

B,C の 0,1 を組み合わせた、重み付け数列のグラフです。

Bi-Cubic は B:0, C:0 だと Nearest-Neighbor と Bi-Liner の合いの子位の性能で、あまりジャギーを隠せません。そこで B や C の値を上げて調整します。


B (b-spline)

B:1 のグラフです。



青い線が B:1, C:0 に対応します。

convert ornament.png  -filter cubic \

-define filter:b=1 \
-define filter:c=0 \
-resize 200% ornament-cubic-1-0-200.png

単純にぼやけてますね。


C (cardinal)

C:1 のグラフです。



緑の線が B:0, C:1 に対応します。

convert ornament.png  -filter cubic \

-define filter:b=0 \
-define filter:c=1 \
-resize 200% ornament-cubic-0-1-200.png

こちらは絵がくっきりしますが、本物の輪郭と平行してニセの輪郭が現れています。

太くて黒い線の隣に元には無かった白い線が追加されてますね。

このように、B と C は単に大きくすれば良い訳ではありません。


Mitchell

拡大する時にフィルタ窓の関係で発生するブロックノイズ(Blocking)を消したいのですが、B を増やすとブラー(Blur)でボヤけ、C を増やすとリンギング(Ringing)が発生し、B,C 両方でエイリアシング(Aliasing)が目立ってくるので、それらのバランスをとって B:1/3, C:1/3 の値を採用したのが Mitchell-Netravali フィルタです。

当てずっぽうに決めたのでなく、実際に主観的テストであらわれた傾向を元に決めています。



- 転載元) http://www.imagemagick.org/Usage/filter/#mitchell

- 論文) https://www.cs.utexas.edu/~fussell/courses/cs384g-fall2013/lectures/mitchell/Mitchell.pdf

いい感じに変換出来たパラメータを点線で示していて、そのうち Mitchell と矢印で示されたポイントが B:1/3, C:1/3 です。


計算方法

MagickCore/resize.c のコメントで説明されています。

    Coefficents are determined from B,C values:

P0 = ( 6 - 2*B )/6 = coeff[0]
P1 = 0
P2 = (-18 +12*B + 6*C )/6 = coeff[1]
P3 = ( 12 - 9*B - 6*C )/6 = coeff[2]
Q0 = ( 8*B +24*C )/6 = coeff[3]
Q1 = ( -12*B -48*C )/6 = coeff[4]
Q2 = ( 6*B +30*C )/6 = coeff[5]
Q3 = ( - 1*B - 6*C )/6 = coeff[6]

which are used to define the filter:

P0 + P1*x + P2*x^2 + P3*x^3 0 <= x < 1
Q0 + Q1*x + Q2*x^2 + Q3*x^3 1 <= x < 2

先に、JavaScript で書き直したサンプルを示します。

まず、B,C から8つの係数を算出します。(尚、ImageMagick を真似して上記の式をはじめから 1/6 します)

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];
}

その8つの係数を3次方程式に当てはめて、Cubic を計算します。

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;
}

それでは、ImageMagick での実際の処理です。

B,C から8つの係数を算出するのがこちら。

        const double

twoB = B+B;

/*
Convert B,C values into Cubic Coefficents. See CubicBC().
*/
resize_filter->coefficient[0]=1.0-(1.0/3.0)*B;
resize_filter->coefficient[1]=-3.0+twoB+C;
resize_filter->coefficient[2]=2.0-1.5*B-C;
resize_filter->coefficient[3]=(4.0/3.0)*B+4.0*C;
resize_filter->coefficient[4]=-8.0*C-twoB;
resize_filter->coefficient[5]=B+5.0*C;
resize_filter->coefficient[6]=(-1.0/6.0)*B-C;

3次方程式の計算はこちら。

  if (x < 1.0)

return(resize_filter->coefficient[0]+x*(x*
(resize_filter->coefficient[1]+x*resize_filter->coefficient[2])));
if (x < 2.0)
return(resize_filter->coefficient[3]+x*(resize_filter->coefficient[4]+x*
(resize_filter->coefficient[5]+x*resize_filter->coefficient[6])));
return(0.0);

重たいといっても四則演算なので、次に紹介する lanczos ほどでは無いです。


-filter lanczos

lanczos フィルタを指定すると、Lanczos(ランチョス、ランツォシュ)窓を使って補間します。

ImageMagick でフィルタを指定せずに縮小リサイズを動かすと、多くの場合 Lanczos で動作します。(パレット形式だったり透明度が含まれる場合は拡大と同じく michell を使います)

ちなみに、Lanczos アルゴリズムと言うと行列変換の方がメジャーっぽいので、区別する為にも、この記事では窓フィルタである事を強調してます。


Lanczos と Sinc窓

Sinc窓という LPF(ローパスフィルタ)の窓関数があります。

Lanczos はこの Sinc の LPF 特性を受け継ぐので、(少ないサンプル数でサンプリングし直す)縮小処理に都合がよいです。





(c) https://en.wikipedia.org/wiki/Sinc_filter

見ての通り、波が左右方向に永遠に続きます。無限の大きさを持つフィルタなので、畳み込みの計算量が膨大になり扱い辛いです。

Lancos 窓はこの Sinc窓を更に計算して 2,3,4の範囲で抑えます。

グラフを見た方が早いですね。

n=2

n=3

n=4

このように、n の値で区間を自由に変えられます。

この窓フィルタを一定区間に収める事。別の言い方だとカーネルを有限の大きさにする事を、コンパクトサポートと表現します。


-define filter:lobes

区間 n は -define filter:lobes で指定できます。

フィルタの上下に出っ張る形を lobe(耳たぶ、または葉)と呼ぶので、それに合わせた命名です。

convert ornament.png  -filter lanczos \

-define filter:lobes=2 \
-resize 50% ornament-lanczos2-50.png
convert ornament.png -filter lanczos \
-define filter:lobes=3 \
-resize 50% ornament-lanczos3-50.png
convert ornament.png -filter lanczos \
-define filter:lobes=4 \
-resize 50% ornament-lanczos4-50.png

original
lobe:2
lobe:3
lobe:4




Lanczos2, Lanczos3, Lanczos4 と呼ぶ場合、この n=2,3,4 の Lanczos を指します。

lobe の n が大きいほど Sinc に近付き、アーチファクトが出にくくなります。が、この例だと違いが分かりませんね。。(後でサンプル探します)

ちなみに、ImageMagick の Lanczos lobe デフォルトは 3 です。(2017年12月の時点で)


計算方法

ImageMagick の Lanczos の処理はそれ以外のフィルタも共通化して使えるよう抽象化されたルーチンで動作していて、一見さんには分かりにくいです。先に JavaScript で書き直したサンプルを示します。こんな感じで計算できます。

function sinc(x) {

var pi_x = Math.PI * x;
return Math.sin(pi_x) / pi_x;
}
function lanczos(x, lobe) {
if (x === 0) {
return 0;
}
if (Math.abs(x) < lobe) {
return sinc(x) * sinc(x/lobe);
}
return 0;
}

さて、ImageMagick の処理も紹介しておきます。

まず、Sinc はこちらです。単純に sin(a)/a の計算です。

static double Sinc(const double x,

const ResizeFilter *magick_unused(resize_filter))
{
magick_unreferenced(resize_filter);

/*
Scaled sinc(x) function using a trig call:
sinc(x) == sin(pi x)/(pi x).
*/

if (x != 0.0)
{
const double alpha=(double) (MagickPI*x);
return(sin((double) alpha)/alpha);
}
return((double) 1.0);
}

Lanczos の lobe 指定はフィルタの support として扱います。

  artifact=GetImageArtifact(image,"filter:lobes");

if (artifact != (const char *) NULL)
{
ssize_t
lobes;

lobes=(ssize_t) StringToLong(artifact);
if (lobes < 1)
lobes=1;
resize_filter->support=(double) lobes;
}

この support を元に重み付けをします。

contribution[n].weight=GetResizeFilterWeight(resize_filter,scale*

((double) (start+n)-bisect+0.5));


SincFact

Sinc 窓は sin 関数を使ったり、割り算をしたりと結構重たいので、この近似として SincFast 関数が用意されています。こちらだと掛け算と足し算だけで済みます。

ImageMagick の画像縮小で Lanczos フィルタが適用される際、この SincFast の lobes:3 (結果として support:3) 扱いで動作するようです。


-colorspace RGB (ガンマ補正の考慮)

一般的なファイル画像の RGB 値は物理的な輝度(明るさ)とリニアな関係にはなく、ガンマ補正のかかった関係にあります。

極端な例だと輝度100%(R,G,B:255,255,255)と0%(R,G,B:0,0,0)が隣り合う時に画像をリサイズしてピクセルを補間した時に算出するピクセルの輝度は以下の暗さになります。

半分以下ですね。これは極端で稀なケースと思いきや。星空撮影を含め夜間の撮影題材に当てはまるケースが結構あります。


Resizing with Colorspace Correction

sRGB のままリサイズ
gamma:1 にしてリサイズ


一度 -colorspace RGB でガンマ補正を解除して、リサイズを行い、改めてまた -colorspace sRGB でガンマ補正をかけ直すと、良い結果が得られます。

% convert earth_lights_4800.tif -colorspace RGB     -resize 500    \

-colorspace sRGB earth_lights_colorspace.png

なお、ImageMagick では RGB を輝度リニアな RGB、sRGB をガンマ補正(sRGB相当でなくても gamma:1 以外は全て含む)がかかった RGB として区別するので、それを利用しています。


最後に

フィルタについて語りたい事が山ほどありますが、エントリが更に倍以上に膨らむのでもし需要があれば別エントリで書きます。window や lobe と、それらに絡む計算式はもう少し詳しく解説したいですし、 sample:offset に言及してないのも中途半端な気がしてます。


参考