はじめに
下記の記事では,日本の領土面積と沖ノ鳥島を中心した EEZ 円の面積を比較するため,両者の高精細地図を作成し,ピクセル数をカウントして比較した。
この際,ピクセル数をカウントするプログラムを速攻で作成したが,高精細地図(14244×12642 ピクセル)ということもあって永遠に近い時間が流れたような気がした・・・実際には1画像あたり約2分だったが。今後,遺恨を残さないためにもプログラムの改善を図っておきたい。
改めて仕様を整理する
背景が白色のグレイスケール画像において,黒いピクセル数をカウントする。ピクセルの明るさが真っ黒 00h のときカウント1,真っ白 FFh のときカウント0とする。中間値,たとえば 80h のときはカウント $(255 - 128) / 255 = 0.498$ とする。万が一,グレイスケール画像でなかった場合は RGB の平均値とする。αプレーンは無視しよう。
画像フォーマットは PNG, BMP, JPEG など GDI+ がサポートしている形式を対象とする。
開発言語は C#,しかも Windows 内蔵の C# コンパイラでビルドできること,すなわち言語仕様としては .NET Framework までとする。
実装コード
GetPixel 版
前回作成したコードである。一番手軽な方法だが,クッソ遅い。
using System;
using System.IO;
using System.Drawing;
class PixelCount {
static int Main( string[] args ) {
if( args.Length < 1 ) {
Console.Error.WriteLine( "Usage: PixelCount(.exe) [画像ファイル名]" );
return -1;
}
if( !File.Exists( args[0] ) ) {
Console.Error.WriteLine( "ファイル {0} は存在しません!!", args[0] );
return -1;
}
Bitmap bitmap = new Bitmap( args[0] );
long count = 0;
for( int y = 0; y < bitmap.Height; y++ ) {
for( int x = 0; x < bitmap.Width; x++ ) {
var color = bitmap.GetPixel( x, y );
int value = color.G + color.B + color.R;
count += 3 * 255 - value;
}
}
Console.WriteLine( (double)count / ( 3 * 255 ) );
return 0;
}
}
LockBits & Marshal.Copy 版
まず Bitmap.LockBits
によって画像をビットマップに展開した後,同サイズのバイト配列にコピーしてアクセスする方法。コピーする際にはアンマネージド/マネージド領域を渡る際の専用のコピー手段 Marshal.Copy
を使用する必要があるが,コピー後はバイト配列を自由にアクセスできる。C# は多次元配列がサポートされた便利な言語だが,C# の多次元配列は遅くて有名なので一次元配列とする。
画像によっては Bitmap.Stride
が負の場合もあるので要注意。ただし,本ケースは画像全体をスキャンできればトップダウンであろうとボトムアップであろうと方向は気にしないので絶対値 stride
として一様に取り扱っている。
using System;
using System.IO;
using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;
class PixelCount {
static int Main( string[] args ) {
if( args.Length < 1 ) {
Console.Error.WriteLine( "Usage: PixelCount2(.exe) [画像ファイル名]" );
return -1;
}
if( !File.Exists( args[0] ) ) {
Console.Error.WriteLine( "ファイル {0} は存在しません!!", args[0] );
return -1;
}
Bitmap bitmap = new Bitmap( args[0] );
int width = bitmap.Width;
int height = bitmap.Height;
var rect = new Rectangle( 0, 0, width, height );
var format = PixelFormat.Format24bppRgb;
var data = bitmap.LockBits( rect, ImageLockMode.ReadOnly, format );
int stride = Math.Abs( data.Stride );
int size = stride * height;
byte[] bytes = new byte[size];
Marshal.Copy( data.Scan0, bytes, 0, size );
bitmap.UnlockBits( data );
bitmap.Dispose();
long count = 0;
for( int i = 0; i < size; i += stride ) {
for( int x = 0, j = i; x < width; x++, j += 3 ) {
int value = bytes[j] + bytes[j + 1] + bytes[j + 2];
count += 3 * 255 - value;
}
}
Console.WriteLine( (double)count / ( 3 * 255 ) );
return 0;
}
}
LockBits & unsafe ポインタ版
Bitmap.LockBits
によって確保された領域を直接アクセスするため,コピーの無駄がなく最速と言われる方法。アクセスにはポインタを使用するためコンパイル時にはオプション -unsafe
を付ける必要がある。
using System;
using System.IO;
using System.Drawing;
using System.Drawing.Imaging;
class PixelCount {
static int Main( string[] args ) {
if( args.Length < 1 ) {
Console.Error.WriteLine( "Usage: PixelCount3(.exe) [画像ファイル名]" );
return -1;
}
if( !File.Exists( args[0] ) ) {
Console.Error.WriteLine( "ファイル {0} は存在しません!!", args[0] );
return -1;
}
Bitmap bitmap = new Bitmap( args[0] );
int width = bitmap.Width;
int height = bitmap.Height;
var rect = new Rectangle( 0, 0, width, height );
var format = PixelFormat.Format24bppRgb;
var data = bitmap.LockBits( rect, ImageLockMode.ReadOnly, format );
int stride = Math.Abs( data.Stride );
int size = stride * height;
long count = 0;
unsafe {
byte* ptr = (byte*)data.Scan0;
for( int i = 0; i < size; i += stride ) {
for( int x = 0, j = i; x < width; x++, j += 3 ) {
int value = ptr[j] + ptr[j + 1] + ptr[j + 2];
count += 3 * 255 - value;
}
}
}
bitmap.UnlockBits( data );
bitmap.Dispose();
Console.WriteLine( (double)count / ( 3 * 255 ) );
return 0;
}
}
実行時間の比較
題材は下記の画像ファイルである。14244×12642 ピクセルもある。
実行時間の比較結果を表1に示す。
LockBits
& Marshal.Copy
にすることにより,100 倍以上の高速化を実現した。unsafe
ポインタにすればさらに 1.5 倍速くなり,元のプログラムの約 200 倍の高速化を実現した。
No. | 方式 | 時間[秒] | 速度比[-] |
---|---|---|---|
1 | GetPixel | 119.28 | 1 |
2 | LockBits & Marshal.Copy | 1.01 | 118 |
3 | LockBits & unsafe ポインタ | 0.62 | 192 |
延長戦
以上はよくある高速化手段である。参考文献にも書かれているが,十年以上前から行われているいわば常識的なテクニックに近い。
ここまで来ると,処理時間の大半は Bitmap.LockBits
が占めており,しかも PNG ファイルのデコードよりも Format24bppRgb
形式への変換時間のほうが支配的である。であれば,元画像の形式 Bitmap.PixelFormat
をそのまま利用したほうが余分な変換を行わなくて済むので,格段の高速化が期待できるはずだ。
ただし,画像の形式毎に処理が分かれるのでコーディングはひたすら面倒なことになる。とくに Format1bppIndexed
や Format4bppIndexed
の場合は画像の右端の処理が面倒である。
using System;
using System.IO;
using System.Drawing;
using System.Drawing.Imaging;
class PixelCount {
static int Main( string[] args ) {
if( args.Length < 1 ) {
Console.Error.WriteLine( "Usage: PixelCount4(.exe) [画像ファイル名]" );
return -1;
}
if( !File.Exists( args[0] ) ) {
Console.Error.WriteLine( "ファイル {0} は存在しません!!", args[0] );
return -1;
}
Bitmap bitmap = new Bitmap( args[0] );
int width = bitmap.Width;
int height = bitmap.Height;
var rect = new Rectangle( 0, 0, width, height );
var format = bitmap.PixelFormat;
var data = bitmap.LockBits( rect, ImageLockMode.ReadOnly, format );
int stride = Math.Abs( data.Stride );
int size = stride * height;
long count = 0;
unsafe {
byte* ptr = (byte*)data.Scan0;
switch( format ) {
case PixelFormat.Format1bppIndexed:
{
var a = new int[2];
for( int i = 0; i < bitmap.Palette.Entries.Length; i++ ) {
var color = bitmap.Palette.Entries[i];
int value = color.R + color.G + color.B;
a[i] = 3 * 255 - value;
}
var b = new int[256];
for( int i = 0; i < 256; i++ ) {
int value = 0;
for( int mask = 0x80; mask > 0; mask >>= 1 )
value += ( i & mask ) != 0 ? a[1] : a[0];
b[i] = value;
}
for( int i = 0; i < size; i += stride ) {
int x, j;
for( x = 0, j = i; x < width - 7; x += 8, j++ )
count += b[ptr[j]];
for( int mask = 0x80; x < width; x++, mask >>= 1 )
count += ( ptr[j] & mask ) != 0 ? a[1] : a[0];
}
}
break;
case PixelFormat.Format4bppIndexed:
{
var a = new int[16];
for( int i = 0; i < bitmap.Palette.Entries.Length; i++ ) {
var color = bitmap.Palette.Entries[i];
int value = color.R + color.G + color.B;
a[i] = 3 * 255 - value;
}
var b = new int[256];
for( int i = 0; i < 16; i++ )
for( int j = 0; j < 16; j++ )
b[i * 16 + j] = a[i] + a[j];
for( int i = 0; i < size; i += stride ) {
int x, j;
for( x = 0, j = i; x < width - 1; x += 2, j++ )
count += b[ptr[j]];
if( x < width )
count += a[ptr[j]];
}
}
break;
case PixelFormat.Format8bppIndexed:
{
var a = new int[256];
for( int i = 0; i < bitmap.Palette.Entries.Length; i++ ) {
var color = bitmap.Palette.Entries[i];
int value = color.R + color.G + color.B;
a[i] = 3 * 255 - value;
}
for( int i = 0; i < size; i += stride )
for( int x = 0, j = i; x < width; x++, j++ )
count += a[ptr[j]];
}
break;
case PixelFormat.Format24bppRgb:
{
for( int i = 0; i < size; i += stride ) {
for( int x = 0, j = i; x < width; x++, j += 3 ) {
int value = ptr[j] + ptr[j + 1] + ptr[j + 2];
count += 3 * 255 - value;
}
}
}
break;
case PixelFormat.Format32bppRgb:
{
for( int i = 0; i < size; i += stride ) {
for( int x = 0, j = i; x < width; x++, j += 4 ) {
int value = ptr[j] + ptr[j + 1] + ptr[j + 2];
count += 3 * 255 - value;
}
}
}
break;
default:
Console.Error.WriteLine( "フォーマット {0} に対応していません!!", format );
break;
}
}
bitmap.UnlockBits( data );
bitmap.Dispose();
Console.WriteLine( (double)count / ( 3 * 255 ) );
return 0;
}
}
ただ,面倒なコーディングの成果は如実に現れて,なんと元のプログラムの約 800 倍の高速化を達成した。なお,今回の題材の画像形式は Format4bppIndexed
であった。
No. | 方式 | 時間[秒] | 速度比[-] |
---|---|---|---|
1 | GetPixel | 119.28 | 1 |
2 | LockBits & Marshal.Copy | 1.01 | 118 |
3 | LockBits & unsafe ポインタ | 0.62 | 192 |
4 | LockBits & unsafe ポインタ & format 無変換 | 0.15 | 795 |
計測環境は ThinkPad X280 Core i7-8550U, Windows10 22H2 である。C# コンパイラは Visual Studio 2022 Commnunity Edition のものを使用した。