NearestNeighbor(ニアレストネイバー法)

今が何時だかもよくわからない　フラフラに疲れ部屋に辿り着く～
『Room』 song by surface

みたいな残業の日々が続き燃え尽きそう。。。

忙しいけど一応なんか更新しないとね。
と、思って今回は画像の補間処理としてもっと簡単なニアレストネイバー（最近傍補間）を紹介しておこう。

ニアレストネイバーとは非常に単純で画質は低いが高速であるという特徴の補間方法。
要は拡大・縮小の比率を縦、横に掛けて割り出した座標に最も近い位置にあるピクセルを採用するもの。
色を混ぜたりしないので単純明快。

とりあえず、Delphiでニアレストネイバーな関数を作ってみた。

function ResizeNearest(Bmp: TBitmap; Width, Height: Integer): TBitmap;
type
    PRGBArray = ^TRGBArray;
    TRGBArray = array[0..32767] of TRGBTriple;
var
    ix, iy :Integer;
    sy, sx :Integer;
    srgb, drgb :PRGBArray;
    tmp :TBitmap;
    wfactor, hfactor:Double;
    w, h :Integer;
begin
    w := Bmp.Width;
    h := Bmp.Height;

    tmp := TBitmap.Create;
    tmp.Width := Width;
    tmp.Height := Height;
    tmp.PixelFormat := pf24bit;

    wfactor := w/Width;

    for iy := 0 to Height-1 do
    begin
        for ix := 0 to Width-1 do
        begin
            sy := Min(Round(hfactor*iy), h-1);
            sx := Min(Round(wfactor*ix), w-1);
            srgb := bmp.ScanLine[sy];
            drgb := tmp.ScanLine[iy];
            drgb[ix] := srgb[sx];
        end;
    end;

    Result := tmp;
end;

関数の引数に元画像ビットマップ画像と出力サイズを渡す。
すると新しく生成されたビットマップ画像が戻ってくる。（戻り値のデータは使い終わったらちゃんと開放してやろう）

こいつを使ってテストプログラムを作った。ボタンをクリックするとウィンドウの内域一杯にビットマップ画像を表示する。
この関数の処理に掛かっている時間を計測してフォームのキャプションに表示してみた。
使った画像はWindowsXPに付属する『Water lilies.jpg』を24bitビットマップに変換したもの。

最大化（LCD解像度1280×1024px）して描画してみる・・・おそっ！
なんと平均840msほどかかっている。これではまったくメリットがない。
ちょっくら高速化。

改良高速化

どこが遅い原因か？それはいたって簡単。座標計算の回数が必要以上に多い為である。
プログラムをさらっと見れば分かるが、Y座標は同じ行を処理している間は変わらないのに全ピクセルに対して計算を行っている。
まずはさくっとここら辺を変えてみる。

for iy := 0 to Height-1 do
begin
    sy := Min(Round(hfactor*iy), h-1);
    srgb := bmp.ScanLine[sy];
    drgb := tmp.ScanLine[iy];

    for ix := 0 to Width-1 do
    begin
        sx := Min(Round(wfactor*ix), w-1);
        drgb[ix] := srgb[sx];
    end;
end;

さてごらんのとおり、全ピクセル計算していたY座標を行単位に変更し、ScanLineもそれにともなって位置を変えた。
キーボードはまったく使わなくてもできる改造。

さて、結果のほどは･･･平均90ms
いかがだろうか？たったこれだけでもものすごい差が出た。

実はもっと高速化する手段がある。
毎行行っているX座標の計算だが、実は毎行同じパターンであることが分かるはずだ。
それならば、1回計算してしまえばもう計算する必要はなくなる。
そこで先にX座標を計算して保持し、あとは取り出すだけという形に変えてみた。

function ResizeNearest(Bmp: TBitmap; Width, Height: Integer): TBitmap;
type
    PRGBArray = ^TRGBArray;
    TRGBArray = array[0..32767] of TRGBTriple;
var
    ix, iy :Integer;
    sy :Integer;
    sx :TIntegerDynArray;
    srgb, drgb :PRGBArray;
    tmp :TBitmap;
    wfactor, hfactor:Double;
    w, h :Integer;
begin
    w := Bmp.Width;
    h := Bmp.Height;

    tmp := TBitmap.Create;
    tmp.Width := Width;
    tmp.Height := Height;
    tmp.PixelFormat := pf24bit;

    wfactor := w/Width;
    hfactor := h/Height;

    SetLength(sx, Width);

    for ix := 0 to Width - 1 do begin
        sx[ix] := Min(Round(wfactor*ix), w-1);
    end;

    for iy := 0 to Height-1 do
    begin
        sy := Min(Round(hfactor*iy), h-1);
        srgb := bmp.ScanLine[sy];
        drgb := tmp.ScanLine[iy];

        for ix := 0 to Width-1 do
        begin
            drgb[ix] := srgb[sx[ix]];
        end;
    end;

    Result := tmp;
end;

このコードだと平均40msとかなり速くなった。
事前にX座標を計算してしまいTIntegerDynArray（可変長配列型）のsxに保持する形にした。
これでピクセル単位の計算ではなくなり、まさにWidth×Height分だけ計算すればよい事になのだ。
これくらい速ければ実用化できるであろう。
ちなみにTIntegerDynArrayはTypesユニットに定義されている。

あまりにどうでも良いネタだとは思うが、どうだったろうか？
今後も同様のネタを出してみようと思う。次回はBilinear（1次線形補間）を紹介したい。