こんにちは。ディマージシェアの技術担当です。以前の記事でスキャンした書類画像を水平にするプログラムを作りました。そして、こちらの記事で並列処理を用いてプログラムの高速化を行いました。今回は別のアプローチでプログラムの性能を向上させてみようと思います。
計算量の削減
処理するのは書類のスキャン画像と仮定します。その場合、カラー画像やグレースケールの画像として処理する必要はほぼありません。モノクロの2値データとして処理しても結果は同じになるはずです。また、多くの印刷物は黒で塗りつぶされているわけではありません。紙面のうち印字されている面積は高々10%ほどです。なので、ビットマップとしてデータを保持するのではなく、黒の画素がある座標を配列で保持する方法に書き換えることで性能向上が期待できます。
for (i = 0; i < h; i++) {
int32_t d_y_pad = w * i;
cv::Vec3b* ptr = src->ptr<cv::Vec3b>(i);
for (j = 0; j < w; j++) {
cv::Vec3b bgr = ptr[j];
uint8_t v = (uint8_t)(0.2126 * bgr[2] +
0.7152 * bgr[1] +
0.0722 * bgr[0]);
data[d_y_pad + j] = 0;
if ((255 - v) > 110) {
data[d_y_pad + j] = 1;
dot_ct++;
}
}
}
// 黒画素がある座標を配列にする
dots = (dot*)malloc(sizeof(dot) * dot_ct);
dot_ct = 0;
for (i = 0; i < h; i++) {
int32_t d_y_pad = w * i;
for (j = 0; j < w; j++) {
if (data[d_y_pad + j]) {
dots[dot_ct].x = j;
dots[dot_ct].y = i;
dot_ct++;
}
}
}
メモリのアクセス効率の向上
一般的にメモリは連続アクセスは高速であり、不連続なアクセスは時間がかかります。先述のようにデータの持ち方を変えることにより、不連続なメモリアクセスを回避することができます。2次元的なメモリ領域に対して、斜めにアクセスするのは非効率ですが、データの持ち方を変えたことにより、画素がある座標を頭から最後まで読むだけになります。
ベンチマーク
データの持ち方を変える前のプログラムで、1 core 1 threadでは
time = 375.211783 sec
でした。データの持ち方を変えたプログラムでは、
time = 11.472606 sec
となりました。32.7倍の性能向上が実現できました。更に、OpenMPで16 cores 32 threadsで実行したところ、
time = 1.701961 sec
となり、更に6.7倍の性能になりました。扱う画像が2値画像という制約が加わりましたが、GPGPUと肩を並べる性能向上が実現しました。
まとめ
計算量的に重い処理を実装するとき、正面突破を試みると難しい場合でも、少しの制約を加えたり、計算機のアーキテクチャに寄り添った実装を行うことで性能を十数倍に伸ばすことができます。
マルチスレッドやGPGPUを用いた力業で解決する方法もありますが、処理そのものを軽量化、最適化するというアプローチも可能です。重い処理と向き合わなければならないときの選択肢として覚えておきましょう。