画像スケーリングアルゴリズムと速度最適化――(一)最近接補間

画像スケーリングアルゴリズムは、デジタル画像処理アルゴリズムでよく発生する問題である.私たちはよくあるサイズの画像を他のサイズの画像に変換します.例えば、画像を拡大したり縮小したりします.OpenCVのResize()関数は非常に便利で効率的です.OPENCVが提供するcvResize関数のプロトタイプを次に示します.

/****************************************************************************************************/
       
void cvResize( const CvArr* src, CvArr* dst, int interpolation=CV_INTER_LINEAR );
src 
    . 
dst 
    . 
interpolation 
    : 
CV_INTER_NN -      , 
CV_INTER_LINEAR -       (    ) 
CV_INTER_AREA -          。       ，           。      ，    CV_INTER_NN   .. 
CV_INTER_CUBIC -     . 
   cvResize     src         dst     。    ROI，         ROI.
/****************************************************************************************************/

Opencvを使用したことがある人は、この関数の使い方を知っていると信じています.以下、私自身の理解に基づいて、VC++で画像スケーリングアルゴリズムを実現し、画像スケーリングアルゴリズムの原理を理解してほしい.
第1節最近接補間
 
最も簡単な画像スケーリングアルゴリズムは、近隣補間です.その名の通り、対象画像の各点の画素値をソース画像において最も近い点とする.ソース画像の幅と高さがそれぞれw 0とh 0であり、スケーリング後のターゲット画像の幅と高さがそれぞれw 1とh 1であると仮定すると、スケールはfloat fw=float(w 0)/w 1である.float fh = float(h0)/h1; ターゲット画像における(x,y)点座標は、ソース画像における(x 0,y 0)点に対応する.ここで、x 0=int(x*fw)、y 0=int(y*fh).
例1:670*503のBMP画像を200*160にスケールし、コードと効果は以下の通りです.

void ResizeNear01(CImage &src, CImage &dst)
{
    int w0 = src.GetWidth();
    int h0 = src.GetHeight();

    int w1 = dst.GetWidth();
    int h1 = dst.GetHeight();

    float fw = float(w0) / w1;
    float fh = float(h0) / h1;

    int x0, y0;
    for(int y=0; y<h1; y++)
    {
        y0 = int(y * fh);
        for(int x=0; x<w1; x++)
        {
            x0 = int(x * fw);
            dst.SetPixel(x, y, src.GetPixel(x0, y0));
        }
    }
}

解析:このプログラムでは、ResizeNear 01関数の文にforループを加えて100回実行し、速度を見てみましょう.

#include <time.h>
void CResizeDemoDlg::OnBnClickedButton1()
{
    // TODO: Add your control notification handler code here
    CImage src, dst;
    src.Load(L"d:\\1.bmp");
    dst.Create(200, 160, 24);

    clock_t start = clock();
    for(int i=0; i<100; i++)
    {
        ResizeNear01(src, dst);
    }
    float end = float(clock() - start)/CLOCKS_PER_SEC;
    CString str;
    str.Format(L"%6.2f", end);
    MessageBox(str);


    dst.Save(L"d:\\rs.jpg");
}

表示プログラムの実行にかかる時間は20.59秒で、平均1回に0.2秒かかります.時間の複雑さが低いため、速度はまあまあです.ターゲット画像のサイズは200*160です.
例2:例1のアルゴリズムで速度を向上させることができる点は2つある.第1に、最近隣接補間アルゴリズムによるソース画像の座標は固定されているため、各ターゲットxとyに対応する値を1回のループで先に求め、二重ループに有利に入ることができる.第二に、ポインタを使用すると効率が高く、CImageで提供されるGetPixelとSetPixelを使用すると時間がかかる.

//           
void ResizeNear02(CImage &src, CImage &dst)
{
    int w0 = src.GetWidth();
    int h0 = src.GetHeight();
    int pitch0 = src.GetPitch();

    int w1 = dst.GetWidth();
    int h1 = dst.GetHeight();
    int pitch1 = dst.GetPitch();

    float fw = float(w0) / w1;
    float fh = float(h0) / h1;

    int *arr_x = new int[w1];
    int *arr_y = new int[h1];
    for(int y=0; y<h1; y++)
    {
        arr_y[y] = int(y*fh);
    }
    for(int x=0; x<w1; x++)
    {
        arr_x[x] = int(x*fw);
    }

    BYTE* pSrc = (BYTE*)src.GetBits();
    BYTE* pDst = (BYTE*)dst.GetBits();
    BYTE* p0, *p1;
    for(int y=0; y<h1; y++)
    {
        p0 = pSrc + pitch0 * arr_y[y];
        p1 = pDst + pitch1 * y;
        for(int x=0; x<w1; x++)
        {
            //dst.SetPixel(x, y, src.GetPixel(arr_x[x], arr_y[y]));
            memcpy(p1 + 3*x, p0 + arr_x[x]*3, 3);
        }
    }

    delete []arr_x;
    delete []arr_y;
}

同様に例1のテストプログラムを実行し、ResizeNear 02も100回ループさせ、私のマシンでテストした結果0.05秒で400倍の速度が向上したなんて、どんなにワクワクすることだろう.