Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

（補講）沖ノ鳥島のEEZが日本の領土より広いって本当？面積計測プログラムを800倍高速化した

Posted at

はじめに

下記の記事では，日本の領土面積と沖ノ鳥島を中心した EEZ 円の面積を比較するため，両者の高精細地図を作成し，ピクセル数をカウントして比較した。

この際，ピクセル数をカウントするプログラムを速攻で作成したが，高精細地図（14244×12642 ピクセル）ということもあって永遠に近い時間が流れたような気がした・・・実際には１画像あたり約２分だったが。今後，遺恨を残さないためにもプログラムの改善を図っておきたい。

改めて仕様を整理する

背景が白色のグレイスケール画像において，黒いピクセル数をカウントする。ピクセルの明るさが真っ黒 00h のときカウント１，真っ白 FFh のときカウント０とする。中間値，たとえば 80h のときはカウント $(255 - 128) / 255 = 0.498$ とする。万が一，グレイスケール画像でなかった場合は RGB の平均値とする。αプレーンは無視しよう。

画像フォーマットは PNG, BMP, JPEG など GDI+ がサポートしている形式を対象とする。

開発言語は C#，しかも Windows 内蔵の C# コンパイラでビルドできること，すなわち言語仕様としては .NET Framework までとする。

実装コード

GetPixel 版

前回作成したコードである。一番手軽な方法だが，クッソ遅い。

PixelCount.cs
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 として一様に取り扱っている。

PixelCount2.cs
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 を付ける必要がある。

PixelCount3.cs
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 ピクセルもある。

実行時間の比較結果を表１に示す。

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 の場合は画像の右端の処理が面倒である。

PixelCount4.cs
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 のものを使用した。

参考文献

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?