前回の記事を書いてから半年以上経ってしまいました。
最近のアクセスランキング見ると圧倒的に画像処理の記事の人気が高いので、そろそろ更新しておきます。
ネタ自体はもう2年くらい前の事です。。。
さて、前回はバイリニア法の実装を検証しました。ニアレストネイバーと比べると画質が良くなるかわりに、処理時間が大幅に増えることがわかりました。
今回は速度をあげる工夫についてご紹介します。
固定小数点演算とは
今回紹介する『固定小数点演算』とは画像処理のプログラムでは一般的によく使われる高速化の技法です。前回用いた『浮動小数点演算』と比べると、読んで字のごとくですが小数点位置を固定して計算をすることで表現可能な値の範囲が狭い代わりに高速に計算ができます。
詳しくはとりあえずWikipediaを参考にしてください。
固定小数点演算では和算や加算は普通にできます。ですが、乗算や除算の場合精度を一定にするにはビットシフトの必要があります
たとえば2進数のQ1フォーマットで表した1.5は『11』と表現できます、2は『100』となります。これらの乗算は以下のように表せます。
11
* 100
------
1100
この計算結果はこのままだと期待する答えの『110』(10進数で3)にはなりません。
計算に用いた数値はどちらもQ1フォーマットの固定小数点数であり、これらを乗算することでQ1+Q1=Q2というようにQ2フォーマットの状態になります。なのでQ1フォーマットに戻すには右に1ビットシフトしてやります。そうすることで期待する『110』の形になります。
除算の場合は逆のビットシフトが必要になります。例として3(110)を1.5(11)で割ってみます。Q1フォーマットで期待する答えは『100』ですね。
10
------
11) 110
110
------
0
単に割っただけでは答えは『10』（10進数で1）になります。これはQ1-Q1=Q0ということになっています。なので左に1ビットしてやればQ1になり『100』になります。
最終的な計算結果を整数で得るときは最後にQ0になるようにビットシフトしてやればいいので、演算の度に必ずビットシフトする必要はないのですが、放っておくとオーバーフローやアンダーフローを起こしてしまい、正しい結果が得られないことがあるので、適切なタイミングでシフトを実行する必要があります。
プログラム
前回のプログラムと同じロジックを固定小数点演算にして組みなおしたものです。演算はすべて整数型で行うので除算はdivを使います。
慣れていないので多少雑な作りになってしまった気がします。
procedure ResizeBilinearFix(SrcBmp, DstBmp :TBitmap; Width, Height: LongWord);
const
FIX_SHIFT = 15;
FIX_DEC_MASK = (1 shl FIX_SHIFT) - 1;
FIX_ONE = 1 shl FIX_SHIFT;
type
PRGBQuadArray = ^TRGBQuadArray;
TRGBQuadArray = array[0..32767] of TRGBQuad;
var
wfactor, hfactor: LongWord;
x0, x1, y0, y1: LongWord;
cx0, cx1, cy0, cy1: LongWord;
ix, iy: LongWord;
srcWidth, srcHeight: LongWord;
d, d00, d01, d10, d11: PRGBQuad;
dst, src1, src2: PRGBQuadArray;
r0, r1, g0, g1, b0, b1: LongWord;
x, y: LongWord;
xp, xc: TLongWordDynArray;
begin
if (Width < 1) or (Height < 1) then Exit;
if (DstBmp.PixelFormat <> pf32bit)
or (SrcBmp.PixelFormat <> pf32bit) then Exit;
DstBmp.Width := Width; srcWidth := SrcBmp.Width;
DstBmp.Height := Height; srcHeight := SrcBmp.Height;
hfactor := (srcHeight shl FIX_SHIFT) div Height;
wfactor := (srcWidth shl FIX_SHIFT) div Width;
SetLength(xp, Width); SetLength(xc, Width);
for ix := 0 to Width - 1 do
begin
x := wfactor*ix;
xp[ix] := Min(x shr FIX_SHIFT, srcWidth - 1);
xc[ix] := x and FIX_DEC_MASK;
end;
for iy:= 0 to Height - 1 do
begin
y := hfactor * iy; // Q15
y0 := Min(y shr FIX_SHIFT, srcHeight - 1); // 四捨五入
y1 := Min(y0 + 1, srcHeight - 1);
cy1 := y and FIX_DEC_MASK; // Q15
cy0 := FIX_ONE - cy1; // Q15
dst := DstBmp.ScanLine[iy];
src1 := SrcBmp.ScanLine[y0];
src2 := SrcBmp.ScanLine[y1];
for ix := 0 to Width - 1 do
begin
x0 := xp[ix]; x1 := Min(x0 + 1, srcWidth - 1);
cx1 := xc[ix]; cx0 := FIX_ONE - cx1; // Q15
d := @dst[ix];
d00 := @src1[x0]; d01 := @src2[x0];
d10 := @src1[x1]; d11 := @src2[x1];
r0 := ((d00^.rgbRed*cx0) + (d10^.rgbRed*cx1)) shr FIX_SHIFT;
r1 := ((d01^.rgbRed*cx0) + (d11^.rgbRed*cx1)) shr FIX_SHIFT;
g0 := ((d00^.rgbGreen*cx0) + (d10^.rgbGreen*cx1)) shr FIX_SHIFT;
g1 := ((d01^.rgbGreen*cx0) + (d11^.rgbGreen*cx1)) shr FIX_SHIFT;
b0 := ((d00^.rgbBlue*cx0) + (d10^.rgbBlue*cx1)) shr FIX_SHIFT;
b1 := ((d01^.rgbBlue*cx0) + (d11^.rgbBlue*cx1)) shr FIX_SHIFT;
d^.rgbRed := Min($FF, (r0*cy0 + r1*cy1) shr FIX_SHIFT);
d^.rgbGreen := Min($FF, (g0*cy0 + g1*cy1) shr FIX_SHIFT);
d^.rgbBlue := Min($FF, (b0*cy0 + b1*cy1) shr FIX_SHIFT);
end;
end;
end;
実行結果
上記のプログラムで前回同様、サンプル画像を1280×960に拡大してみました。
処理時間は90ms程度まで減りました。浮動小数点演算に比べるとかなり速くなりました。まだチューニングの余地はあると思いますが、かなり改善されたのではないでしょうか。
それでもまだニアレストネイバーの10倍以上の時間が掛かっています。
次回はさらに踏み込んで、究極の最適化手段であるアセンブラによるプログラムとMMXを併用した高速化を図りたいと思います。
コメント