【C言語】画像処理プログラムの高速化方法を解説

画像処理の高速化方法解説ページのアイキャッチ

ここではC言語における画像処理プログラムの高速化ポイントについて説明します。

コンパイルオプションで高速化することも可能ですが、このページではコンパイルオプションに頼らず、プログラムを変更することで高速化を行います。

ちょっと気をつけるだけで処理の高速化を行えますのでぜひ参考にしてください。

画像処理でもよく用いられる線形補間による拡大縮小のプログラムを例に、処理高速化のポイントや、それがどれくらい効果あるかをみていきたいと思います。

線形補間による拡大縮小は下記の記事で紹介しています。

C言語で画像の拡大縮小(線形補間編)

高速化前プログラム

まずは高速化を行う前のプログラムを紹介したいと思います。

スポンサーリンク

ソースコード

下記が高速化を行う前の「線形補間による拡大縮小処理を行う」プログラムのソースコードになります。

下記ページで紹介しているものとほぼ同じで、処理時間を計測できるようにだけ変更しています。

C言語で画像の拡大縮小(線形補間編)

これを最適化してどんどん早くしていきます!

高速化前のプログラム
#include "myJpeg.h"
#include <time.h>

int main(int argc, char *argv[]){

  BITMAPDATA_t bitmap, scaledBitmap;
  int m, n, c;
  int m0, m1, n0, n1;
  double originalm, originaln;
  double dm, dn;
  double scaleW, scaleH;
  char outname[256];
  clock_t start, end;

  if(argc != 4){
    printf("ファイル名、幅方向拡大率、高さ方向拡大率の3つを引数に指定してください\n");
    return -1;
  }

  scaleW = atof(argv[2]);
  scaleH = atof(argv[3]);

  if(jpegFileReadDecode(&bitmap, argv[1]) == -1){
    printf("jpegFileReadDecode error\n");
    return -1;
  }

  /* ここから画像処理 */
  /* 画像を指定された倍率に拡大縮小 */
  scaledBitmap.width = scaleW * bitmap.width;
  scaledBitmap.height = scaleH * bitmap.height;
  scaledBitmap.ch = bitmap.ch;

  if(scaledBitmap.width == 0 || scaledBitmap.height == 0){
    printf("拡大縮小後の幅もしくは高さが0です\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  scaledBitmap.data = (unsigned char*)malloc(sizeof(unsigned char) * scaledBitmap.width * scaledBitmap.height * scaledBitmap.ch);
  if(scaledBitmap.data == NULL){
    printf("malloc scaledBitmap error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  /* ここから拡大縮小 */
  start = clock();

  for(n = 0; n < scaledBitmap.height; n++){
    for(m = 0; m < scaledBitmap.width; m++){
      for(c = 0; c < scaledBitmap.ch; c++){

        originalm = (double)m / (double)scaleW;
        m0 = (int)originalm;
        dm = originalm - m0;
        m1 = m0 + 1;
        if(m1 == bitmap.width) m1 = bitmap.width - 1;

        originaln = (double)n / (double)scaleH;
        n0 = (int)originaln;
        dn = originaln - n0;
        n1 = n0 + 1;
        if(n1 == bitmap.height) n1 = bitmap.height - 1;

        scaledBitmap.data[scaledBitmap.ch * (m + n * scaledBitmap.width) + c]
          = bitmap.data[bitmap.ch * (m1 + n1 * bitmap.width) + c] * dm * dn
          + bitmap.data[bitmap.ch * (m1 + n0 * bitmap.width) + c] * dm * (1 - dn)
          + bitmap.data[bitmap.ch * (m0 + n1 * bitmap.width) + c] * (1- dm) * dn
          + bitmap.data[bitmap.ch * (m0 + n0 * bitmap.width) + c] * (1 -dm) * (1 - dn);
      }
    }
  }
  /* ここまで拡大縮小 */
  end = clock();

  printf("processing time:%.3f[sec]\n", ((double)end - (double)start) / CLOCKS_PER_SEC);
  
  sprintf(outname, "%s", "linear.jpeg");

  if(jpegFileEncodeWrite(&scaledBitmap, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  freeBitmapData(&bitmap);

  return 0;
}

プログラムの解説は下記ページで行っていますので、不明点などあればこのページを参考にしていただければと思います。

C言語で画像の拡大縮小(線形補間編)

処理時間は、実際に画像の拡大縮小を行う部分だけ計測しています。

スポンサーリンク

コンパイルと実行

最初なので、コンパイルと実行方法についても解説しておきます。

今後このページではいくつかソースコードを紹介しますが、コンパイルや実行方法は全て同じになります。

コンパイル

コンパイルして実行可能ファイルを作成するためには下記の4つが必要です。

  1. このページで紹介するソースコード(main.c
  2. libjpeg のインストール
  3. myJpeg.c
  4. myJpeg.h

1. に関してはこのページで紹介しているソースコードをコピペして main.c という名前で保存すれば良いです。

2. 3. 4. に関しては下記ページで紹介しています。 myJpeg.cmyJpeg.h についてはコピペしてきて main.c と同じフォルダに設置してください。

libjpegの使い方解説ページアイキャッチ【C言語】libjpegのインストールと使用方法・使用例

準備が整えば、下記コマンドでコンパイルを行なって実行可能ファイル main.exe を得ることができます。

gcc fast.c myJpeg.c -ljpeg -o main.exe

-ljpeg は libjpeg をリンクするためのオプションになります。

実行

プログラムは下記の3つの引数を受け取るようにしています。

  1. JPEG 画像のファイルパス
  2. 横方向の拡大率
  3. 縦方向の拡大率

例えば実行可能ファイル main.exe と同じフォルダにある input.jpg を横方向と縦方向それぞれ 3 倍に拡大したい場合は下記のように引数を指定して実行します。

./main.exe input.jpg 3 3

引数が足りないと実行時にエラーになるので注意してください。

プログラムを実行すると、拡大後の画像 linear.jpg が同じフォルダに作成され、さらに計測した処理時間が表示されます。

スポンサーリンク

スポンサーリンク

処理時間

前置きが終わったところで本題の処理時間について見てみましょう。

処理時間は拡大縮小処理を行なっている部分のみ計測しています(JPEG を読み込んだりしている時間は含んでいません)。

入力画像のサイズが 3024 x 4032、拡大率を縦横共に 3 倍にしたの処理時間は下記のようになりました。

17.891[sec]

下記で紹介する高速化を行うことで、この処理時間を短くしていきます!

MEMO

今後の処理時間計測においては引数について特に説明しませんが、今回と同じ画像 & 拡大率を指定してプログラムを実行しています

処理をループの浅い位置に移動する

まずはループの一番深いところに注目し、そこで行う必要のない処理をループの外側に出すことで高速化を図ります。

スポンサーリンク

スポンサーリンク

考え方

最初にお見せしたソースコードのように、ループが何重にもなって処理を行っているようなプログラムの場合、高速化を行うべき箇所はループの一番深いところ(ループの一番内側)の処理になります。

具体的には変数 c に対するループの部分ですね。

一番深いところのループの中の処理が一番たくさん実行されため、ここの処理を減らすことで得られる高速化の効果が高いためです。

例えば 3024 x 4032 の画像を縦横ともに 3 倍に拡大した場合、それぞれのループの中の処理が実行される回数は下記のようになります。

  • n のループ:12096
  • m のループ:1097349129072 * 12096) 
  • c のループ:329204736109734912 * 3

つまり、一番深いところのループで処理を行うと、その分処理が行われる回数が爆発的に増えて処理時間が長くなるというわけです。

特に計算処理においては掛け算や割り算は足し算や引き算に比較して処理に要する時間が長いです。

逆にループの浅いところで処理を行ってもループの深いところで行う場合に比べて処理時間にはそこまで影響しません。

スポンサーリンク

高速化

上記の理由の通り、ループの深いところで処理を行うと処理時間が長くなります。

なので、とにかくループの深いところで行っている処理を、もっとループの浅いところに移すことでプログラムの高速化を行うことができます。

例えば高速化前プログラムで紹介したソースコードの変数 c に対するループに注目してみましょう。

下記の処理が依存するのは m の値だけなので(ループの変数の中だと)、m のループの中で行う必要はありますが、わざわざ c のループの中で行う必要はありません。

変数mにのみ依存する処理
originalm = (double)m / (double)scaleW;
m0 = (int)originalm;
dm = originalm - m0;
m1 = m0 + 1;
if(m1 == bitmap.width) m1 = bitmap.width - 1;

また下記の処理が依存するのは n の値だけなので(ループの変数の中だと)、n のループの中で行う必要はありますが、これも c のループの中で行う必要はありません。

変数nにのみ依存する処理
originaln = (double)n / (double)scaleH;
n0 = (int)originaln;
dn = originaln - n0;
n1 = n0 + 1;
if(n1 == bitmap.height) n1 = bitmap.height - 1;

これらを一番深いところにある c のループから外側に追い出すだけで、プログラムの高速化を行うことができます。

スポンサーリンク

ソースコード

下記がその高速化後のプログラムのソースコードになります。

高速化1
#include "myJpeg.h"
#include <time.h&g;t

int main(int argc, char *argv[]){

  BITMAPDATA_t bitmap, scaledBitmap;
  int m, n, c;
  int m0, m1, n0, n1;
  double originalm, originaln;
  double dm, dn;
  double scaleW, scaleH;
  char outname[256];
  clock_t start, end;

  if(argc != 4){
    printf("ファイル名、幅方向拡大率、高さ方向拡大率の3つを引数に指定してください\n");
    return -1;
  }

  scaleW = atof(argv[2]);
  scaleH = atof(argv[3]);

  if(jpegFileReadDecode(&bitmap, argv[1]) == -1){
    printf("jpegFileReadDecode error\n");
    return -1;
  }

  /* ここから画像処理 */
  /* 画像を指定された倍率に拡大縮小 */
  scaledBitmap.width = scaleW * bitmap.width;
  scaledBitmap.height = scaleH * bitmap.height;
  scaledBitmap.ch = bitmap.ch;

  if(scaledBitmap.width == 0 || scaledBitmap.height == 0){
    printf("拡大縮小後の幅もしくは高さが0です\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  scaledBitmap.data = (unsigned char*)malloc(sizeof(unsigned char) * scaledBitmap.width * scaledBitmap.height * scaledBitmap.ch);
  if(scaledBitmap.data == NULL){
    printf("malloc scaledBitmap error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  /* ここから拡大縮小 */
  start = clock();

  for(n = 0; n < scaledBitmap.height; n++){

    /* 変数nのみに依存する処理をループの外側へ */
    originaln = (double)n / (double)scaleH;
    n0 = (int)originaln;
    dn = originaln - n0;
    n1 = n0 + 1;
    if(n1 == bitmap.height) n1 = bitmap.height - 1;

    for(m = 0; m < scaledBitmap.width; m++){

      /* 変数mのみに依存する処理をループの外側へ */
      originalm = (double)m / (double)scaleW;
      m0 = (int)originalm;
      dm = originalm - m0;
      m1 = m0 + 1;
      if(m1 == bitmap.width) m1 = bitmap.width - 1;

      for(c = 0; c < scaledBitmap.ch; c++){

        scaledBitmap.data[scaledBitmap.ch * (m + n * scaledBitmap.width) + c]
          = bitmap.data[bitmap.ch * (m1 + n1 * bitmap.width) + c] * dm * dn
          + bitmap.data[bitmap.ch * (m1 + n0 * bitmap.width) + c] * dm * (1 - dn)
          + bitmap.data[bitmap.ch * (m0 + n1 * bitmap.width) + c] * (1- dm) * dn
          + bitmap.data[bitmap.ch * (m0 + n0 * bitmap.width) + c] * (1 -dm) * (1 - dn);
      }
    }
  }
  /* ここまで拡大縮小 */
  end = clock();

  printf("processing time:%.3f[sec]\n", ((double)end - (double)start) / CLOCKS_PER_SEC);
  
  sprintf(outname, "%s", "linear.jpeg");

  if(jpegFileEncodeWrite(&scaledBitmap, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  freeBitmapData(&bitmap);

  return 0;
}

スポンサーリンク

スポンサーリンク

処理時間

では処理時間はどのように変化するでしょうか?

プログラムを実行して計測した処理時間は下記のようになります。

7.044[sec]

高速化前プログラムに比較してかなり処理時間が短くなり、処理を行う場所をちょっと変更するだけで高速化できていることが確認できると思います。

めちゃめちゃ速くなっててビックリ!

いかにループの深い位置での処理が処理速度に影響するかが確認できる結果になったね

処理を行う位置を変更するだけでこれだけ高速化できるんだから、このテクニックは是非覚えておくと良いよ!

ループの浅い位置で処理が行えるように計算式を変更する

次は単に処理の位置を変更するだけでなく、計算式を変更することで高速化を図ります。

スポンサーリンク

スポンサーリンク

考え方

考え方の基本的な部分はループの浅い位置に移動すると同じです。

とにかくループの深いところで実行する処理をループの浅い位置に移動させます。

ただし、今回は単に処理の位置を移動させるだけでなく処理の位置を移動できるように計算式を変更します。

そして、計算式を変更した結果、ループの浅い位置に移動させることができる処理をループの浅い位置に移動させます。

特に処理時間のかかる掛け算や割り算をループの深い位置からループの浅い位置に移動できるように計算式を変更します。

要は計算式を分割して、ループの浅い位置に移動できる処理を移動させます。

計算式を変更することで、拡大縮小結果が変わったりしないの?
結果が変わったりしないように変更するというところが重要だね!

計算式の変更は、あくまでも計算結果が変わらないように行う必要があります。

計算結果が変わってしまうように計算式を変更してしまうと拡大縮小結果にも影響が出てしまうので注意してください。

スポンサーリンク

高速化

特にループの深い位置での処理に注目し、その処理を分割することでループの外側に追い出せないかを考えます。

例えば c のループの中で行っている下記の処理に注目してみましょう。

元々の計算式
bitmap.data[bitmap.ch * (m1 + n1 * bitmap.width) + c] * dm * dn

一番深いループである c のループの中の処理なので、c を利用する部分以外はループの外側で計算することが可能なはずです。

なので、上の処理を下記のように変更します。

元々の計算式
byte11 = bitmap.ch * (m1 + n1 * bitmap.width);
d11 = dm * dn;
bitmap.data[byte11 + c] * d11

このように処理を変更することで、byte11 の計算と d11 の計算は変数 c には依存しなくなるため、c のループの外側に追い出すことができます。

byte11 の計算と d11 の計算両方ともに掛け算がありますので、これらをループの外側に追い出すことでそれなりに高速化の効果を期待することができます。

ただし外に追い出せる処理が足し算や引き算のみの場合はあまり効果がないので注意しましょう。

スポンサーリンク

ソースコード

上記の考え方で高速化を行ったプログラムのソースコードは下記になります。

高速化2
#include "myJpeg.h"
#include <time.h&g;t

int main(int argc, char *argv[]){

  BITMAPDATA_t bitmap, scaledBitmap;
  int m, n, c;
  int m0, m1, n0, n1;
  double originalm, originaln;
  double dm, dn;
  double scaleW, scaleH;
  char outname[256];
  clock_t start, end;

  /* 計算途中結果を格納するための変数を用意 */
  int byte, byte11, byte10, byte01, byte00;
  double d11, d10, d01, d00;

  if(argc != 4){
    printf("ファイル名、幅方向拡大率、高さ方向拡大率の3つを引数に指定してください\n");
    return -1;
  }

  scaleW = atof(argv[2]);
  scaleH = atof(argv[3]);

  if(jpegFileReadDecode(&bitmap, argv[1]) == -1){
    printf("jpegFileReadDecode error\n");
    return -1;
  }

  /* ここから画像処理 */
  /* 画像を指定された倍率に拡大縮小 */
  scaledBitmap.width = scaleW * bitmap.width;
  scaledBitmap.height = scaleH * bitmap.height;
  scaledBitmap.ch = bitmap.ch;

  if(scaledBitmap.width == 0 || scaledBitmap.height == 0){
    printf("拡大縮小後の幅もしくは高さが0です\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  scaledBitmap.data = (unsigned char*)malloc(sizeof(unsigned char) * scaledBitmap.width * scaledBitmap.height * scaledBitmap.ch);
  if(scaledBitmap.data == NULL){
    printf("malloc scaledBitmap error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  /* ここから拡大縮小 */
  start = clock();

  for(n = 0; n < scaledBitmap.height; n++){

    originaln = (double)n / (double)scaleH;
    n0 = (int)originaln;
    dn = originaln - n0;
    n1 = n0 + 1;
    if(n1 == bitmap.height) n1 = bitmap.height - 1;

    for(m = 0; m < scaledBitmap.width; m++){

      originalm = (double)m / (double)scaleW;
      m0 = (int)originalm;
      dm = originalm - m0;
      m1 = m0 + 1;
      if(m1 == bitmap.width) m1 = bitmap.width - 1;

      /* cに依存しない計算をここで実行 */
      d11 = dm * dn;
      d10 = dm * (1 - dn);
      d01 = (1 - dm) * dn;
      d00 = (1 - dm) * (1 - dn);

      byte11 = bitmap.ch * (m1 + n1 * bitmap.width);
      byte10 = bitmap.ch * (m1 + n0 * bitmap.width);
      byte01 = bitmap.ch * (m0 + n1 * bitmap.width);
      byte00 = bitmap.ch * (m0 + n0 * bitmap.width);
      byte = scaledBitmap.ch * (m + n * scaledBitmap.width);

      for(c = 0; c < scaledBitmap.ch; c++){
        /* 掛け算を外に追い出せるように計算式変更 */
        scaledBitmap.data[byte + c]
          = bitmap.data[byte11 + c] * d11
          + bitmap.data[byte10 + c] * d10
          + bitmap.data[byte01 + c] * d01
          + bitmap.data[byte00 + c] * d00;
      }
    }
  }
  /* ここまで拡大縮小 */
  end = clock();

  printf("processing time:%.3f[sec]\n", ((double)end - (double)start) / CLOCKS_PER_SEC);
  
  sprintf(outname, "%s", "linear.jpeg");

  if(jpegFileEncodeWrite(&scaledBitmap, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  freeBitmapData(&bitmap);

  return 0;
}

スポンサーリンク

スポンサーリンク

処理時間

プログラムを実行して計測した処理時間は下記のようになります。

6.181[sec]

処理をループの浅い位置に移動するで紹介したプログラムと比較するとちょっと処理時間が短くなってますね。

処理時間が 13 % 程度削減できていると考えるとまぁまぁの効果とも言えそうです。

スポンサーリンク

浮動小数点数の利用をやめる

ここまでの高速化により、ループの一番深いところ(つまり c のループ)の中の処理が下記のようになりました。

変数cのループ
for(c = 0; c < scaledBitmap.ch; c++){
  scaledBitmap.data[byte + c]
  = bitmap.data[byte11 + c] * d11
  + bitmap.data[byte10 + c] * d10
  + bitmap.data[byte01 + c] * d01
  + bitmap.data[byte00 + c] * d00;
}

かなり処理を少なくできましたが、まだ掛け算処理が残っています。

今度はこの掛け算を高速化していきます。

スポンサーリンク

スポンサーリンク

考え方

浮動小数点数型(double 型や float 型)の変数では小数点以下の値も扱えて便利なのですが、実は整数型に比較して、浮動小数点数は演算に使用すると処理時間が長くなるというデメリットがあります。

なので、特にループの深い位置では浮動小数点数型の変数を用いた計算を行うと処理時間が長くなってしまいます。

逆に、浮動小数点数方の変数を整数型に置き換えることで高速化を図ることが可能です。

ただし、整数型では小数点以下の値を扱うことができません。

例えば今回紹介しているソースコードでは、d11d10d01d00 などは 1 以下の値(特に小数点以下の値)を扱いたいため、double 型の変数にしています。

単にこれらを整数型の変数に置き換えると線形補間がうまく行えません。

このような場合には、下記のような手順を踏むことで浮動小数点数型を整数型に置き換えることができます。

  1. double 型などの浮動小数点数型の変数に掛け算をして大きな値に変換する
  2. 大きな値に変換した値を int 型などの整数型の変数に代入する
  3. その整数型の変数を用いて計算処理を実行する
  4. その計算処理の結果を 1. で掛けた値で割る

具体的にみてみましょう。例えば 0.05200 を掛ける計算を上記の手順を踏まえて実行してみます。

整数型への置き換え
int main(void){
  double a = 0.05;
  int ia;
  int ans;

  ia = a * 100;

  ans = (ia * 200) / 100;

  return 0;
}

このプログラムでは、まず double 型の変数 a100 を掛け、その結果を int 型変数の ia に代入しています(つまり 5 が格納されます)。

さらに、この ia を用いて本来の計算処理の x 200 を実行しています。

さらにその結果を ia を求める際に掛けた 100 で割っています。結果は 10 になります。

このように上記のような手順を踏むことで、計算処理は浮動小数点数型を用いずに実行することができるようになります。

では手順 1. で具体的に何をかければ良いかというと、これは10進数で考えて小数点以下何桁までを扱いたいかによります。

扱いたい小数点以下の値が全て整数部にまで上がってくるように掛け算で値を大きくします。例えば 100 をかければ、小数点以下 2 桁までは扱えますが、それよりも下の値は切り捨てられることになります。

double 型を int 型に置き換えたりすると誤差が発生したりするんじゃないの?

発生するね…

なので、元々の拡大縮小結果と比べると差分が出る点には注意が必要だよ

だけど、手順 1. で掛ける値(手順 4. で割る値)を十分大きくしてあげればそこまで誤差は気にならないと思うよ

逆に大きな値をかけて型で扱える値の最大値を超えたりしないように注意は必要だよ

なるほど…

確かに写真画像なんかだと誤差発生しても目立たないかもね!

とはいえ、誤差は確かに発生するので、高速化を優先するか画質を優先するかをしっかり考えて、どこまで高速化するかを決めることは重要だよ!

スポンサーリンク

高速化

先程示した手順を元々のソースコードで使用している浮動小数点数型の変数に適用することで高速化することができます。

今回は特に一番深いループの中の計算で使用されている d11d10d01d00 を整数型に置き換えることで高速化していきます。

まず d11d10d01d00 を整数型の変数として宣言します。

整数型の変数の宣言
/* 整数型に置き換え */
int d11, d10, d01, d00;

さらに、これらの変数に浮動小数点数型の変数の値を代入する際、1000000 を掛けてから代入するように式を変更します。

整数型への変換
d11 = dm * dn * 1000000; /* 整数化 */
d10 = dm * (1 - dn) * 1000000; /* 整数化 */
d01 = (1 - dm) * dn * 1000000; /* 整数化 */
d00 = (1 - dm) * (1 - dn) * 1000000; /* 整数化 */

さらに、これらの変数を用いて計算を行なった後に、先程掛けた 1000000 で割るように変更します。

元の単位への変換
/* 最後に1000000で割って元の単位に戻す */
scaledBitmap.data[byte + c]
  = (bitmap.data[byte11 + c] * d11
  + bitmap.data[byte10 + c] * d10
  + bitmap.data[byte01 + c] * d01
  + bitmap.data[byte00 + c] * d00) / 1000000;

これにより、c のループの中の計算では浮動小数点数型の変数が使用されなくなります。

スポンサーリンク

ソースコード

この考え方で高速化を行なったプログラムのソースコードは下記のようになります。

高速化3
#include "myJpeg.h"
#include <time.h>

int main(int argc, char *argv[]){

  BITMAPDATA_t bitmap, scaledBitmap;
  int m, n, c;
  int m0, m1, n0, n1;
  double originalm, originaln;
  double dm, dn;
  double scaleW, scaleH;
  char outname[256];
  clock_t start, end;

  int byte, byte11, byte10, byte01, byte00;

  /* 整数型に置き換え */
  int d11, d10, d01, d00;

  if(argc != 4){
    printf("ファイル名、幅方向拡大率、高さ方向拡大率の3つを引数に指定してください\n");
    return -1;
  }

  scaleW = atof(argv[2]);
  scaleH = atof(argv[3]);

  if(jpegFileReadDecode(&bitmap, argv[1]) == -1){
    printf("jpegFileReadDecode error\n");
    return -1;
  }

  /* ここから画像処理 */
  /* 画像を指定された倍率に拡大縮小 */
  scaledBitmap.width = scaleW * bitmap.width;
  scaledBitmap.height = scaleH * bitmap.height;
  scaledBitmap.ch = bitmap.ch;

  if(scaledBitmap.width == 0 || scaledBitmap.height == 0){
    printf("拡大縮小後の幅もしくは高さが0です\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  scaledBitmap.data = (unsigned char*)malloc(sizeof(unsigned char) * scaledBitmap.width * scaledBitmap.height * scaledBitmap.ch);
  if(scaledBitmap.data == NULL){
    printf("malloc scaledBitmap error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  /* ここから拡大縮小 */
  start = clock();

  for(n = 0; n < scaledBitmap.height; n++){

    originaln = (double)n / (double)scaleH;
    n0 = (int)originaln;
    dn = (originaln - n0);
    n1 = n0 + 1;
    if(n1 == bitmap.height) n1 = bitmap.height - 1;

    for(m = 0; m < scaledBitmap.width; m++){

      originalm = (double)m / (double)scaleW;
      m0 = (int)originalm;
      dm = (originalm - m0);
      m1 = m0 + 1;
      if(m1 == bitmap.width) m1 = bitmap.width - 1;

      d11 = dm * dn * 1000000; /* 整数化 */
      d10 = dm * (1 - dn) * 1000000; /* 整数化 */
      d01 = (1 - dm) * dn * 1000000; /* 整数化 */
      d00 = (1 - dm) * (1 - dn) * 1000000; /* 整数化 */

      byte11 = bitmap.ch * (m1 + n1 * bitmap.width);
      byte10 = bitmap.ch * (m1 + n0 * bitmap.width);
      byte01 = bitmap.ch * (m0 + n1 * bitmap.width);
      byte00 = bitmap.ch * (m0 + n0 * bitmap.width);
      byte = scaledBitmap.ch * (m + n * scaledBitmap.width);

      for(c = 0; c < scaledBitmap.ch; c++){
        /* 最後に1000000で割って元の単位に戻す */
        scaledBitmap.data[byte + c]
          = (bitmap.data[byte11 + c] * d11
          + bitmap.data[byte10 + c] * d10
          + bitmap.data[byte01 + c] * d01
          + bitmap.data[byte00 + c] * d00) / 1000000;
      }
    }
  }
  /* ここまで拡大縮小 */
  end = clock();

  printf("processing time:%.3f[sec]\n", ((double)end - (double)start) / CLOCKS_PER_SEC);
  
  sprintf(outname, "%s", "linear.jpeg");

  if(jpegFileEncodeWrite(&scaledBitmap, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  freeBitmapData(&bitmap);

  return 0;
}

スポンサーリンク

スポンサーリンク

処理時間

プログラムを実行して計測した処理時間は下記のようになります。

5.992[sec]

実はループの浅い位置で処理が行えるように計算式を変更するで紹介したプログラムよりもほぼ処理時間は同じです。環境によっては長くなる場合もあると思います。

これは浮動小数点数型を使わなくすることで軽減された負荷と、下記で行うようになった割り算の負荷がほぼ同じだからと考えられます。

追加した割り算
/* 最後に1000000で割って元の単位に戻す */
scaledBitmap.data[byte + c]
  = (bitmap.data[byte11 + c] * d11
  + bitmap.data[byte10 + c] * d10
  + bitmap.data[byte01 + c] * d01
  + bitmap.data[byte00 + c] * d00) / 1000000;

苦労してプログラム変更した割には効果が薄いね…

最後の割り算の処理が結構重いんだよね…

だけど、この浮動小数点数型の整数型への置き換えを行ったことで、実はこの割り算も高速化することができるんだ!

ということで、次はこの割り算を高速化することで、最終的な高速化プログラムに仕立てていきたいと思います。

シフト演算を利用する

前述のとおり、浮動小数点数型を整数型に置き換えると、むしろ割り算が必要になってプログラムが遅くなってしまいました。

実は、この整数型への置き換えは、ここで解説するシフト演算を利用するための布石です。

スポンサーリンク

スポンサーリンク

考え方

このページでも何回も言っているとおり、掛け算や割り算の負荷は高く、特にループの深い位置で使用すると処理時間が長くなってしまいます。

一方で、2の冪乗での掛け算や割り算はシフト演算で実現することも可能です。

シフト演算に関しては下記ページで詳しく解説していますので是非こちらを参考にしていただければと思います。

ビット演算解説ページのアイキャッチC言語のビット演算(論理演算)について解説

さらに、シフト演算は単に掛け算や割り算を行うよりも遥かに高速です。

つまり、2の冪乗の掛け算や割り算をシフト演算に置き換えることでプログラムの高速化が可能です。

ただし、C言語においては浮動小数点数型の変数に対してシフト演算を行うことができないことに注意してください。

整数型に対してはシフト演算を行うことが可能なので、ここで浮動小数点数の利用をやめるで解説したことが活きてくるというわけです!

スポンサーリンク

高速化

浮動小数点数の利用をやめるで、浮動小数点数型は下記の手順で整数型に変換できると解説しました。

  1. double 型などの浮動小数点数型の変数に掛け算をして大きな値に変換する
  2. 大きな値に変換した値を int 型などの整数型の変数に代入する
  3. その整数型の変数を用いて計算処理を実行する
  4. その計算処理の結果を 1. で掛けた値で割る

ここで特に演算をシフト演算に置き換えたいのは 4. の割り算です。

ですので、1. で掛ける値を「2の冪乗」に置き換え、4. で割る値もその「2の冪乗」に置き換えます。

今回は、整数型に変換を行う際に掛ける値を2の20乗の値である 1048576 にしたいと思います。

整数型への変換
d11 = dm * dn * 1048576; /* 整数化 */
d10 = dm * (1 - dn) * 1048576; /* 整数化 */
d01 = (1 - dm) * dn * 1048576; /* 整数化 */
d00 = (1 - dm) * (1 - dn) * 1048576; /* 整数化 */

2の20乗を掛けているので、最後に行う割り算は下記のように 20 ビットの左シフトに置き換えることができます。

割り算のシフト演算への置き換え
scaledBitmap.data[byte + c]
  = (bitmap.data[byte11 + c] * d11
  + bitmap.data[byte10 + c] * d10
  + bitmap.data[byte01 + c] * d01
  + bitmap.data[byte00 + c] * d00) >> 20;

この >> 20 を行うことで、1048576 での割り算と同じ結果を得ることができます。

なるほど!

2の冪乗の掛け算・割り算を行うように変更すればシフト演算できるようになるんだね!

そういうこと!

シフト演算があるから2の冪乗の計算はコンピュータは得意なんだ

このシフト演算は、特に処理速度を追究することの多いC言語ユーザーは覚えておくと良いと思うよ!

スポンサーリンク

ソースコード

ここまで解説してきた内容を踏まえて高速化を行ったプログラムのソースコードは下記のようになります。

高速化4
#include "myJpeg.h"
#include <time.h>

int main(int argc, char *argv[]){

  BITMAPDATA_t bitmap, scaledBitmap;
  int m, n, c;
  int m0, m1, n0, n1;
  double originalm, originaln;
  double dm, dn;
  double scaleW, scaleH;
  char outname[256];
  clock_t start, end;

  int byte, byte11, byte10, byte01, byte00;
  int d11, d10, d01, d00;

  if(argc != 4){
    printf("ファイル名、幅方向拡大率、高さ方向拡大率の3つを引数に指定してください\n");
    return -1;
  }

  scaleW = atof(argv[2]);
  scaleH = atof(argv[3]);

  if(jpegFileReadDecode(&bitmap, argv[1]) == -1){
    printf("jpegFileReadDecode error\n");
    return -1;
  }

  /* ここから画像処理 */
  /* 画像を指定された倍率に拡大縮小 */
  scaledBitmap.width = scaleW * bitmap.width;
  scaledBitmap.height = scaleH * bitmap.height;
  scaledBitmap.ch = bitmap.ch;

  if(scaledBitmap.width == 0 || scaledBitmap.height == 0){
    printf("拡大縮小後の幅もしくは高さが0です\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  scaledBitmap.data = (unsigned char*)malloc(sizeof(unsigned char) * scaledBitmap.width * scaledBitmap.height * scaledBitmap.ch);
  if(scaledBitmap.data == NULL){
    printf("malloc scaledBitmap error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  /* ここから拡大縮小 */
  start = clock();

  for(n = 0; n < scaledBitmap.height; n++){

    originaln = (double)n / (double)scaleH;
    n0 = (int)originaln;
    dn = (originaln - n0);
    n1 = n0 + 1;
    if(n1 == bitmap.height) n1 = bitmap.height - 1;

    for(m = 0; m < scaledBitmap.width; m++){

      originalm = (double)m / (double)scaleW;
      m0 = (int)originalm;
      dm = (originalm - m0);
      m1 = m0 + 1;
      if(m1 == bitmap.width) m1 = bitmap.width - 1;

      /* 1048576は2の20乗 */
      d11 = dm * dn * 1048576; /* 整数化 */
      d10 = dm * (1 - dn) * 1048576; /* 整数化 */
      d01 = (1 - dm) * dn * 1048576; /* 整数化 */
      d00 = (1 - dm) * (1 - dn) * 1048576; /* 整数化 */

      byte11 = bitmap.ch * (m1 + n1 * bitmap.width);
      byte10 = bitmap.ch * (m1 + n0 * bitmap.width);
      byte01 = bitmap.ch * (m0 + n1 * bitmap.width);
      byte00 = bitmap.ch * (m0 + n0 * bitmap.width);
      byte = scaledBitmap.ch * (m + n * scaledBitmap.width);

      for(c = 0; c < scaledBitmap.ch; c++){
        /* 最後に20ビット左シフトして元の単位に戻す */
        scaledBitmap.data[byte + c]
          = (bitmap.data[byte11 + c] * d11
          + bitmap.data[byte10 + c] * d10
          + bitmap.data[byte01 + c] * d01
          + bitmap.data[byte00 + c] * d00) >> 20;
      }
    }
  }
  /* ここまで拡大縮小 */
  end = clock();

  printf("processing time:%.3f[sec]\n", ((double)end - (double)start) / CLOCKS_PER_SEC);
  
  sprintf(outname, "%s", "linear.jpeg");

  if(jpegFileEncodeWrite(&scaledBitmap, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeBitmapData(&bitmap);
    return -1;
  }

  freeBitmapData(&bitmap);

  return 0;
}

スポンサーリンク

スポンサーリンク

処理時間

このソースコードのプログラムを実行した際の処理時間は下記のようになりました。

5.362[sec]

若干ですが効果はありますね!

浮動小数点数型の演算が苦手な CPU(FPU)などを使用している場合はもうちょっと効果はあるかもしれないです。

まとめ

このページでは画像の拡大縮小の例を用いてプログラムを高速化する方法について解説しました。

具体的には下記の4つの高速化の施策の考え方や具体的な変更方法について解説しました。

  • 処理をループの浅い位置に移動する
  • ループの浅い位置で処理が行えるように計算式を変更する
  • 浮動小数点数の利用をやめる
  • シフト演算を利用する

この4つのを行うことで、もともと 17.8 秒程度かかっていた処理を 5.3 秒程度まで短縮することができました。約 3 倍高速化できています。

しかし、高速化前と高速化後のプログラムを見てみると、プログラムを読みにくくなったと感じる人もいると思います。高速化を行うとプログラムの可読性が下がることがあります。

また、浮動小数点数型を整数型に置き換えることで、元々の拡大縮小結果に対して誤差が発生することもあります。

「どこまで高速化を行うか」と、そのために「何を犠牲にするか(可読性?誤差?)」をよく考慮し、適切な高速化を行うことが重要です。

ちなみにこのページ以外の方法でもプログラムの高速化を行うことが可能です。

例えば配列へのアクセス順(画像データへのアクセス順)を変更するだけで処理速度が大きく変わります。

また、並列実行可能な CPU を利用しているのであれば、マルチスレッド で並列処理することで高速化を行うようなことも可能です。

それぞれ下記のページで解説していますので、興味のある方は是非こちらも合わせてお読みください!

【C言語】配列へのアクセス順序による処理速度の違い【キャッシュ】 【C言語】マルチスレッドで画像の拡大縮小を高速化

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です