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

ここではC言語における画像処理プログラムの高速化ポイントについて説明します。コンパイルオプションに頼らない高速化を行います。ちょっと気をつけるだけで処理の高速化を行えますのでぜひ参考にしてください。

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

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

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

高速化前プログラム

線形補間による拡大縮小処理のプログラミングが下記です。

jpeg関連のファイルや関数については下記記事で紹介しています。興味ある方やプログラムを使用したい人はぜひ見てみてください。

LibJPEGのインストールとC言語での使用方法・使用例LibJPEGのインストールとC言語での使用方法・使用例

かなり遅く作成しています。これを最適化してどんどん早くしていきましょう。

#include "myJpeg.h"
#include <time.h>

int linear(RAWDATA_t *scaledRaw, RAWDATA_t *raw, int n, int m, int c, double scaleW, double scaleH){

  int m0, m1, n0, n1;
  double originalm, originaln;
  double dm, dn;

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

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

  scaledRaw->data[scaledRaw->ch * (m + n * scaledRaw->width) + c]
    = raw->data[raw->ch * (m1 + n1 * raw->width) + c] * dm * dn
    + raw->data[raw->ch * (m1 + n0 * raw->width) + c] * dm * (1 - dn)
    + raw->data[raw->ch * (m0 + n1 * raw->width) + c] * (1- dm) * dn
    + raw->data[raw->ch * (m0 + n0 * raw->width) + c] * (1 -dm) * (1 - dn);

  return 0;
}

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

  RAWDATA_t raw, scaledRaw;
  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;

  FILE *fo;

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

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

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

  /* ここから画像処理 */
  /* 最近傍彭法で画像を指定された倍率に拡大縮小 */
  scaledRaw.width = scaleW * raw.width;
  scaledRaw.height = scaleH * raw.height;
  scaledRaw.ch = raw.ch;

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

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

  start = clock();

  for(n = 0; n < scaledRaw.height; n++){
    for(m = 0; m < scaledRaw.width; m++){
      for(c = 0; c < scaledRaw.ch; c++){
        linear(&scaledRaw, &raw, n, m, c, scaleW, scaleH);
      }
    }
  }
  /* ここまで画像処理 */
  end = clock();

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

  sprintf(outname, "%s", "linear.jpeg");

  if(jpegFileEncodeWrite(&scaledRaw, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeRawData(&raw);
    return -1;
  }

  freeRawData(&raw);

  return 0;
}

入力画像が3024×4032、拡大率を縦横共に3倍にした場合、処理時間は約15.4秒でした。

計算処理をループの外側に出して高速化

計算処理処理をループが深いところで実行すると実行回数が増えて計算時間も増加します。ループの外側で実行可能な部分はとにかくそれをループの外側に出すことで処理時間の短縮が望めます。

ループ内の処理を下のようにするだけで処理時間が約6.7秒まで縮まりました。

  for(n = 0; n < scaledRaw.height; n++){
    originaln = (double)n / (double)scaleH;
    n0 = (int)originaln;
    dn = originaln - n0;
    n1 = n0 + 1;
    if(n1 == raw.height) n1 = raw.height - 1;

    for(m = 0; m < scaledRaw.width; m++){
      originalm = (double)m / (double)scaleW;
      m0 = (int)originalm;
      dm = originalm - m0;
      m1 = m0 + 1;
      if(m1 == raw.width) m1 = raw.width - 1;

      for(c = 0; c < scaledRaw.ch; c++){
        scaledRaw.data[scaledRaw.ch * (m + n * scaledRaw.width) + c]
          = raw.data[raw.ch * (m1 + n1 * raw.width) + c] * dm * dn
          + raw.data[raw.ch * (m1 + n0 * raw.width) + c] * dm * (1 - dn)
          + raw.data[raw.ch * (m0 + n1 * raw.width) + c] * (1- dm) * dn
          + raw.data[raw.ch * (m0 + n0 * raw.width) + c] * (1 -dm) * (1 - dn);

      }
    }
  }

スポンサーリンク

掛け算や割り算はループ前に計算して高速化

掛け算や割り算は足し算や引き算に比べて処理時間が長いです。ですので、この掛け算や割り算をいかにしてループの外側に出してやるかが高速化のポイントになります。下記のループではcはループするとともに変化しますが、他の要素は変わりません。ですので、cに関わらない部分の掛け算をループの外側であらかじめ計算しておくことで高速化を行います。

      for(c = 0; c < scaledRaw.ch; c++){
        scaledRaw.data[scaledRaw.ch * (m + n * scaledRaw.width) + c]
          = raw.data[raw.ch * (m1 + n1 * raw.width) + c] * dm * dn
          + raw.data[raw.ch * (m1 + n0 * raw.width) + c] * dm * (1 - dn)
          + raw.data[raw.ch * (m0 + n1 * raw.width) + c] * (1- dm) * dn
          + raw.data[raw.ch * (m0 + n0 * raw.width) + c] * (1 -dm) * (1 - dn);
      }

まずあらかじめ計算した結果を格納しておく変数を宣言しておき、

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

ループの手間で計算結果を格納しておきます。

      d11 = dm * dn;
      d10 = dm * (1 - dn);
      d01 = (1 - dm) * dn;
      d00 = (1 - dm) * (1 - dn);

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

これによりループ内での掛け算を大幅に削減することができます。

      for(c = 0; c < scaledRaw.ch; c++){
        scaledRaw.data[byte + c]
          = raw.data[byte11 + c] * d11
          + raw.data[byte10 + c] * d10
          + raw.data[byte01 + c] * d01
          + raw.data[byte00 + c] * d00;
      }

これにより計算時間がさらに短くなり、約5.9秒になりました。

double型をint型に変換して高速化

double型の計算は処理時間がかかります。なのでループ内でのdouble型の使用は高速化を考える際には控える方が良いです。 ただどうしても小数点以下の値を考慮する必要がある場合があります。今回の線形補間でもdmやdnは1より小さい数字になりますので、小数点以下が無視されるint型等を使うと画質が悪くなってしまいます。 こうういったときによくやるのが下記のような処理です。

  1. 一旦double型の値を掛け算をして大きくしてやる
  2. 大きくしてやった値を用いて本来の計算処理を行う
  3. 本来の計算処理で得られた値を、1. で掛けた値で割る

具体的にみてみましょう。例えば0.05に200を掛ける計算を考えてみましょう。結果は当然10になります。

int main(void){
  double a = 0.05;
  int ia;
  int ans;

  ia = a * 100;

  ans = (ia * 200) / 100;

  return 0;
}

このプログラムでは、aをまず100倍しています。これによりiaに5が格納されます。

さらにそのiaを用いて本来の計算処理のx200を実行しています。さらにその結果をiaを求める際に掛けた100で割っています。結果は10になるはずですし、計算がdouble型を用いずに実行することができており、計算処理も早くなることが期待できます。

要は、double型の小数点以下何桁までを考慮した計算を実行したいかを考え、その桁数が整数部にまで上がってくるように掛け算で値を大きくしてやってから、本来の計算を行うことでdouble型を使用せずに計算処理を実行します。

ではこの高速化手法を線形補間のプログラムに適用させましょう。今回は計算精度を小数点以下3桁までとします。

MEMO

doubleをint型に変換するのですから当然変換時に誤差が出ます。ですので画質にも影響がありますので、画質を取るか高速化を取るかは要検討ポイントです。

また、計算精度を小数点以下何桁にするかは重要なポイントです。

変換時の誤差を小さくするためには桁数を大きくするべきです。ただし桁数を大きくする場合は掛ける数字が大きくなるので桁あふれに注意が必要です。

桁数が小さいとこの誤差が大きくなります画質への影響が大きくなります。

注意点は上記の考えを2次元的に考えてやる必要がある点です。

今までのプログラムでdouble型で宣言していた変数をここではint型で宣言します。

  int dm, dn;
  int d11, d10, d01, d00;

dmやdnは本来であれば1以下の値になりますが、ここで1000倍してやることで小数点以下3桁までの数字がdnとdmに格納されます。

    dn = (originaln - n0) * 1000;
      dm = (originalm - m0) * 1000;

下記ではdmやdnを使って計算しています。dmやdnが1000倍されていますので、この値を用いて計算する場合はその他の値も1000倍して計算をしてやる必要があります。

なので(1 – dn)、(1 – dm)だった箇所は(1000 – dn)、(1000 – dm)としています。

      d11 = dm * dn;
      d10 = dm * (1000 - dn);
      d01 = (1000 - dm) * dn;
      d00 = (1000 - dm) * (1000 - dn);

ループ内の処理は下記のようになります。本来行いたかった計算を通常通り行った後に割り算を行なっています。

      for(c = 0; c < scaledRaw.ch; c++){
        scaledRaw.data[byte + c]
          = (raw.data[byte11 + c] * d11
          + raw.data[byte10 + c] * d10
          + raw.data[byte01 + c] * d01
          + raw.data[byte00 + c] * d00) / 1000000;
      }

なぜ除数が1000ではなく、1000000なのかというと、d00〜d11が1000倍をしたdmやdn等の値を2つ掛け合わせた数字だからです。もとの値から1000 x 1000倍された数字になりますのでここでも1000 x 1000で割り算を行います。2次元のデータに対しての線形補間処理・精度保証なのでこういったことの考慮も必要になります。3次元データに対しての処理に対しても同様の考えが必要です(1000 x 1000 x 1000になる)。

ループ内で割り算を行うようになったので遅くなりそうなものですが、double型を使用しないようにすることで処理時間は5.4秒程度になりました。

実はこのdouble型を単に使用しないだけだとあまり旨味はありません。しかしint型に変換してやればシフト演算が使用可能になり、次の高速化ポイントである「シフト演算を使用する」を適用可能になります。

シフト演算を使用して高速化

高速化ポイント「double型を使わない」の応用になります。むしろ「double型を使わない」はこのシフト演算を使用するために行う実装といっても過言ではありません。double型はビット演算使用できませんので。

シフト演算とはビット演算の内の1つの演算方法です。ビットシフトと呼ぶこともあります。プログラムにおいてはシフト演算処理はかなり高速です。ですのでループ内で掛け算や割り算を行う際にはできるだけシフト演算を行うようにする方が良いです。

上のプログラムだとループ内で最後に割り算を行う必要があり、そこに計算時間がかかってしまっています。ここではそこをシフト演算により実行することで高速化を行います。

dnやdmは1000ではなく1024を用いて掛け算を行います。我々人間は10のべき乗数の方が馴染みあるのでちょっと抵抗あるかもしれません。

1024は1を10ビット分シフトした値になります。ですのでここで1024倍するのであれば最終的なループの中では1024 x 1024で割ってやれば所望の結果が得られることになります。

    dn = (originaln - n0) * 1024;
      dm = (originalm - m0) * 1024;

 

下記でも同様に1000ではなく1024を用います。

      d11 = dm * dn;
      d10 = dm * (1024 - dn);
      d01 = (1024 - dm) * dn;
      d00 = (1024 - dm) * (1024 - dn);

ループ内の処理は下記のようになります。

      for(c = 0; c < scaledRaw.ch; c++){
        scaledRaw.data[byte + c]
          = (raw.data[byte11 + c] * d11
          + raw.data[byte10 + c] * d10
          + raw.data[byte01 + c] * d01
          + raw.data[byte00 + c] * d00) >> 20;
      }

「>> 20」は計算結果を20ビット分右へシフトすることになります。

これは1024 x 1024で割るのと同じ計算結果になり、割り算を行うことなく高速なシフト演算で計算を行うことができます。シフト演算を行う、シフト演算を行うために2の冪乗数を使うことは高速化において重要なポイントになります。

このシフト演算への置き換えにより計算時間は約4.8秒にまで短縮されました!

スポンサーリンク

高速化後プログラム

#include "myJpeg.h"
#include <time.h>

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

  RAWDATA_t raw, scaledRaw;
  int m, n, c;
  int m0, m1, n0, n1;

  double originalm, originaln;
  double scaleW, scaleH;
  char outname[256];
  clock_t start, end;
  FILE *fo;

  int dm, dn;
  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(&raw, argv[1]) == -1){
    printf("jpegFileReadDecode error\n");
    return -1;
  }

  /* ここから画像処理 */
  /* 最近傍彭法で画像を指定された倍率に拡大縮小 */
  scaledRaw.width = scaleW * raw.width;
  scaledRaw.height = scaleH * raw.height;
  scaledRaw.ch = raw.ch;

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

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

  start = clock();

  for(n = 0; n < scaledRaw.height; n++){
    originaln = (double)n / (double)scaleH;
    n0 = (int)originaln;
    dn = (originaln - n0) * 1024;
    n1 = n0 + 1;
    if(n1 == raw.height) n1 = raw.height - 1;

    for(m = 0; m < scaledRaw.width; m++){
      originalm = (double)m / (double)scaleW;
      m0 = (int)originalm;
      dm = (originalm - m0) * 1024;
      m1 = m0 + 1;
      if(m1 == raw.width) m1 = raw.width - 1;

      d11 = dm * dn;
      d10 = dm * (1024 - dn);
      d01 = (1024 - dm) * dn;
      d00 = (1024 - dm) * (1024 - dn);

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

      for(c = 0; c < scaledRaw.ch; c++){
        scaledRaw.data[byte + c]
          = (raw.data[byte11 + c] * d11
          + raw.data[byte10 + c] * d10
          + raw.data[byte01 + c] * d01
          + raw.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(&scaledRaw, outname) == -1){
    printf("jpegFileEncodeWrite error\n");
    freeRawData(&raw);
    return -1;
  }

  freeRawData(&raw);

  return 0;
}

 

まとめ

プログラムにおいては下記の4つのポイントによりループ内の処理高速化を行うことが可能です。

  • 処理をループの外側に出す
  • ループに入る前に計算しておく
  • double型を使わない
  • シフト演算を使用する

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

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

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

コメントを残す

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