縮小のアルゴリズム

縮小専用のアルゴリズム

実のところバイリニア法、バイキュービック法、ランチョス法、どの方法を利用しても縮小に対しては実は十分ではない。この方法では縮小率があがるほど元の画像との乖離が酷くなる。

特に線画ではっきりするのであるが、縮小していくと線が途切れたり、モアレが登場してしまうのである。

そのため現実には縮小用のアルゴリズムも実装しないといけないのである。

拡大のアルゴリズムは4点もしくは9点程度しか使わないが、縮小の場合、全ての加重平均を計算するので縮小率が多くなるほど関係する点数が増え、その計算量は多くなる。

拡大アルゴリズムだけで縮小をすると文字や線は潰れるどころかかすれたりかけたりする。

と言うわけで、この部分を改善するために縮小時には該当するピクセルをすべて加重平均することにする。

Pixel Mixing

このアルゴリズム、単純な割に計算が面倒だ。ところが画像処理の教科書でも縮小だけのアルゴリズムの説明をあまりみない。拡大のアルゴリズムに比べて泥臭いので大体、拡大のアルゴリズムだけで片付けられてしまう。

例えば、2/5倍に縮小する場合、実際には以下の16点から計算する必要があるのだ。

$$\begin{bmatrix}p_{(i,j)} & p_{(i,j+1)} & p_{(i,j+2)} & p_{(i,j+3)} \\p_{(i+1,j)} & p_{(i+1,j+1)} & p_{(i+1,j+2)} & p_{(i+1,j+3)} \\p_{(i+2,j)} & p_{(i+2,j+1)} & p_{(i+2,j+2)} & p_{(i+2,j+3)} \\p_{(i+3,j)} & p_{(i+3,j+1)} & p_{(i+3,j+2)} & p_{(i+3,j+3)} \\\end{bmatrix}$$

から　${ P_{(I.J)} }$ を計算するわけだ。図にするとこんな感じ

ところがそう簡単にいかないのである。このケースでは、P(X,Y)の逆変換p(x,y)に端数がでているがこの端数が無い場合、必要な点は9点に減るのである。すなわち必要な元の点は3x3,3x4,4x3,4x4のどれかになるのである。

$${ P_{(I,J)} = \sum\limits_{y=j}^{j+3} \sum\limits_{x=i}^{i+3} p_{(x,y)} w_{(x,y)} }$$

${ w }$はウェイト。よく見ると単純に面積を計算していることに気がつくだろうか？しかも内側は全て面積分の1で計算できるので、外枠の部分を計算すれば良いのである。

このアルゴリズムを取りあえずPixel Mixingと呼んでいるが特に名前はない気もする（他にもpixel averaging、 area mapなどの名前がみられた）。大体、拡大縮小をやろうとして最初に思いつくのはバイリニア法とこのアルゴリズムで、このアルゴリズムは画像縮小だけではなく、ノイズ除去にも使われる。

実はかなりいい加減な実装でもそこそこ使えて例えば1/4.5に縮小する場合、5x5で計算し、各ピクセルに1/25をかけて加えるだけでもわりと効果がある。このアルゴリズム厳密に実装するとわりと面倒なので妥協したいところだが実際に計算してみる。

スケールを $s$としたとき（ただし ${ s < 0.5 }$)

${ d = \frac{1.0} {s} }$ とし 面積は ${ S= d^2 }$ となる

このとき計算に使う元画像のピクセル数 ${n_x,n_y}$ は以下になる。

ただし縮小前の座標をp、縮小後をPとしたとき　${ dP(X,Y) = p(x,y)}$ とする(${X,Y}$は整数)

${ n_x = d}$ (${\lfloor{d}\rfloor = d }$のとき)

${ n_x = \lfloor{d}\rfloor + 1}$ ( ${ x = \lfloor{x}\rfloor }$のとき)

${ n_x = \lfloor{d}\rfloor + 2}$ ( ${ x \ne \lfloor{x}\rfloor }$ のとき)

${ n_y = d}$ (${\lfloor{d}\rfloor = d }$のとき)

${ n_y = \lfloor{d}\rfloor + 1}$ ( ${ y = \lfloor{y}\rfloor }$ のとき)

${ n_y = \lfloor{d}\rfloor + 2}$ ( ${ y \ne \lfloor{y}\rfloor }$ のとき)

以上の時、

$$x_i = dX , y_j = dY , x_{n_x} = d(X + 1) , y_{n_y} = d(Y + 1) \\[16pt] err_{x_0} = 1 - (x_i - \lfloor{x_i}\rfloor) \\[8pt] err_{y_0} = 1 - (y_j - \lfloor{y_j}\rfloor) \\[8pt] err_{x_n} = x_n - \lfloor{x_n}\rfloor \\[8pt] err_{y_n} = y_n - \lfloor{y_n}\rfloor \\[8pt]$$

多分これで良いはず。そうすると

$$w_{(s,t)} = \frac{1}{S} \\[8pt] w_{(0,0)} = \frac{err_{x_0} err_{y_0}} {S}\\[8pt] w_{(n_x,0)} = \frac{err_{x_n} err_{y_0}} {S}\\[8pt] w_{(0,n_y)} = \frac{err_{x_0} err_{y_n}} {S}\\[8pt] w_{(n_x,n_y)} = \frac{err_{x_n} err_{y_n}} {S}\\[8pt] w_{(0,t)} = \frac{err_{x_0}} {S} \\[8pt] w_{(s,0)} = \frac{err_{y_0}} {S} \\[8pt] w_{(n_x,t)} = \frac{err_{x_n}} {S} \\[8pt] w_{(s,n_y)} = \frac{err_{y_n}} {S} \\[8pt] ( 2 \le s \le n_x - 1 ,2 \le t \le n_y - 1)\\$$

ただしこの計算は、0.5倍以下しか想定しないので0.5倍まではバイリニア法を使ったほうが良い。そもそも0.5から1.0の間のバイリニア法とPixel Mixingのアルゴリズムは大体同じ。アスペクト比変換ならバイリニア法で十分である。また拡大縮小を同時にする場合、2つのアルゴリズムをミックスしたり、全体的にぼやけるので更にシャープネスフィルタをかけたりする。