株式会社ヘキサドライブ | HEXADRIVE

こんにちは。

 

シュンスケです

 

前回、どれがキレイ(元画像に近い)なのかをプログラムで判断できれば、

数あるパターンから最適なものが見つけられるのではといった話がありました

 

そこで、今回のアプローチは、GA

 

ガーディアンエンジェルではありません。

ギャラクシーエンジェルでもありません。

 

Genetic Algorithmつまり、「遺伝的アルゴリズム」です

 

大まかに説明すると、とある解を求めるにあたって、生物の進化のように、

解候補たちを組み替えながら、正解に近いものは残して、遠いものを淘汰し、

時には突然変異を起こすといった感じで、多くのパターンからより良いものを

導き出す処理方法です

 

と、ここまで来て気付く方も多いと思いますが、正解に近いかどうか、それが今回でいうと、

元画像に近いかどうかということです。

 

その比較方法でお手軽なのがPSNR値を使うものなようなので、今回はそうします。

(ただし、人間の目を相手にするとなると、問題は多いようです)

 

そして今回、果敢にも全ピクセルの全チャンネルに関して、組み換え対象として

実装しました。

つまり、膨大なパターンがあるということです

 

さて、以下実装です。

using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.Windows.Forms;
using System.IO;
using System.Runtime.InteropServices;

namespace Pic32bitTo16bitGA
{
	class Program : Form
	{
		struct Gene
		{
			public static void cross(ref Gene a, ref Gene b)
			{
				if( a.buf == null || b.buf == null ) return;

				// 2点交叉
				var r = new Random();
				var index1 = r.Next(0, (a.buf.Length - 1) / PIXEL_BYTES);
				var index2 = r.Next((index1 + 1) / PIXEL_BYTES, b.buf.Length / PIXEL_BYTES);
				for( int i = index1; i < index2; ++i ) {
					var tmp0 = a.buf[i + 0];
					var tmp1 = a.buf[i + 1];
					var tmp2 = a.buf[i + 2];
					var tmp3 = a.buf[i + 3];
					a.buf[i + 0] = b.buf[i + 0];
					a.buf[i + 1] = b.buf[i + 1];
					a.buf[i + 2] = b.buf[i + 2];
					a.buf[i + 3] = b.buf[i + 3];
					b.buf[i + 0] = tmp0;
					b.buf[i + 1] = tmp1;
					b.buf[i + 2] = tmp2;
					b.buf[i + 3] = tmp3;
				}
			}

			// コンストラクタ
			public Gene(int w, int h)
			{
				buf = new byte[w * h * PIXEL_BYTES];
				psnr = -1;
			}

			// ランダムで埋める
			public void fillRand()
			{
				// ランダムで色を埋める
				var r = new Random();
				r.NextBytes(buf);
			}

			// PSNRを算出して保持
			public void calcPSNR(byte[] org)
			{
				psnr = -1;
				if( org == null || buf == null || org.Length != buf.Length || org.Length == 0 ) return;

				// MSE算出
				ulong mse = 0;
				for( int i = 0; i < org.Length; ++i ) {
					long d = (buf[i] - org[i]);
					mse += (ulong)(d * d);
				}
				mse /= (ulong)org.Length;
				if( mse <= 0 ) return;

				// PSNR算出
				psnr = (10 * Math.Log10((double)(255 * 255) / (double)mse));
			}

			// 突然変異
			public void mutation()
			{
				if( buf == null ) return;

				var r = new Random();
				var index = r.Next(0, buf.Length / PIXEL_BYTES);
				buf[index + 0] = (byte)r.Next(0, 256);
				buf[index + 1] = (byte)r.Next(0, 256);
				buf[index + 2] = (byte)r.Next(0, 256);
				buf[index + 3] = (byte)r.Next(0, 256);
			}

			// 値を設定
			public void set(Gene g)
			{
				if( g.buf == null ) return;

				if( buf == null || buf.Length != g.buf.Length ) {
					buf = new byte[g.buf.Length];
				}

				Array.Copy(g.buf, buf, buf.Length);
				psnr = g.psnr;
			}

			public byte[]	buf;
			public double	psnr;
		}

		private const int PIXEL_BYTES				= 4;								//!< 1ピクセルあたりのバイト数

		// エントリポイント
		static void Main(string[] args)
		{
			// 入力受付
			Console.WriteLine("please input picture path...");
			var srcPath = Console.ReadLine();

			// ファイル存在確認
			if( !File.Exists(srcPath) ) {
				Console.WriteLine("file not exists.");
				return;
			}

			// 画像読み込み
			byte[] buf = null;
			int width = 0;
			int height = 0;
			using( var img = Image.FromFile(srcPath, true) as Bitmap ) {
				if( img == null ) {
					Console.WriteLine("file type is not support.");
					return;
				}
				// メモリに保持
				var dat = img.LockBits(new Rectangle(Point.Empty, img.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
				width = img.Width;
				height = img.Height;
				buf = new byte[width * height * PIXEL_BYTES];
				Marshal.Copy(dat.Scan0, buf, 0, buf.Length);

				// 解放
				img.UnlockBits(dat);
			}
			if( buf == null ) {
				Console.WriteLine("buf load failed.");
				return;
			}

			// フォーム開始
			Application.Run(new Program(ref buf, width, height));
		}

		// コンストラクタ
		public Program(ref byte[] buf, int w, int h)
		{
			if( buf == null ) return;

			_org = buf;
			_buf = new byte[buf.Length];
			_img = new Bitmap(w, h);

			// 第1世代生成
			for( int i = 0; i < _curGen.Length; ++i ) {
				_curGen[i] = new Gene(w, h);
				_curGen[i].fillRand();
			}

			// フォームのサイズ設定
			ClientSize = new Size(w, h * 2);

			// フォント作成
			_font = new Font(Font.Name, 10);
			_fontBrush = new SolidBrush(ForeColor);

			// 描画更新開始
			_sec = 0;
			_refreshTimer.Interval = 1000;
			_refreshTimer.Tick += new EventHandler(refresh);
			_refreshTimer.Start();

			// 処理更新開始
			_updateTimer.Interval = 1;
			_updateTimer.Tick += new EventHandler(update);
			_updateTimer.Start();
		}

		// 描画時処理
		protected override void OnPaint(PaintEventArgs e)
		{
			base.OnPaint(e);
			if( _img == null ) return;

			// 元画像描画
			if( _org != null ) {
				var newDat = _img.LockBits(new Rectangle(Point.Empty, _img.Size), ImageLockMode.WriteOnly, PixelFormat.Format32bppArgb);
				Marshal.Copy(_org, 0, newDat.Scan0, _org.Length);
				_img.UnlockBits(newDat);
				e.Graphics.DrawImage(_img, 0, 0);
			}

			// 生成画像描画
			if( _buf != null ) {
				var newDat = _img.LockBits(new Rectangle(Point.Empty, _img.Size), ImageLockMode.WriteOnly, PixelFormat.Format32bppArgb);
				Marshal.Copy(_buf, 0, newDat.Scan0, _buf.Length);
				_img.UnlockBits(newDat);
				e.Graphics.DrawImage(_img, 0, _img.Size.Height);
			}

			// フレーム数表示
			e.Graphics.DrawString("sec : " + _sec, _font, _fontBrush, 0, 0);

			// 世代数表示
			e.Graphics.DrawString("gen : " + _genCnt, _font, _fontBrush, 100, 0);
		}

		// 描画更新
		private void refresh(object sender, EventArgs e)
		{
			// 保持したトップを描画バッファに設定
			if( _topGen.buf != null ) {
				Array.Copy(_topGen.buf, _buf, _buf.Length);
			}

			// 画面をリフレッシュ
			++_sec;
			Invalidate();
		}

		// 処理更新
		private void update(object sender, EventArgs e)
		{
			// 評価値算出
			for( int i = 0; i < _curGen.Length; ++i ) {
				_curGen[i].calcPSNR(_org);
			}

			// 評価値でソート
			Array.Sort(_curGen, (a, b) => {
				if( a.psnr == b.psnr ) return 0;

				return (b.psnr > a.psnr) ? 1 : -1;
			});

			// 1位を保持
			_topGen.set(_curGen[0]);

			// 上位いくつかはそのまま残す
			var newIndex = 0;
			for( int i = 0; i < 2; ++newIndex, ++i ) {
				_nextGen[newIndex].set(_curGen[i]);
			}

			while( newIndex < _nextGen.Length ) {
				// 交叉対象1を選出(上位が選ばれやすいように)
				_cross1Buf.set(_curGen[0]);
				for( int i = 1; i < _curGen.Length; ++i ) {
					var rate = _selectRnd.Next(0, 100);
					if( rate < 10 ) {
						_cross1Buf.set(_curGen[i]);
						break;
					}
				}

				// 交叉対象2を選出(上位が選ばれやすいように)
				_cross2Buf.set(_curGen[1]);
				for( int i = 2; i < _curGen.Length; ++i ) {
					var rate = _selectRnd.Next(0, 100);
					if( rate < 10 ) {
						_cross2Buf.set(_curGen[i]);
						break;
					}
				}

				// 交叉
				Gene.cross(ref _cross1Buf, ref _cross2Buf);
				_nextGen[newIndex].set(_cross1Buf);
				++newIndex;
				if( _nextGen.Length <= newIndex ) break;

				_nextGen[newIndex].set(_cross2Buf);
				++newIndex;
				if( _nextGen.Length <= newIndex ) break;

				// 突然変異対象を選出
				var mutIndex = _selectRnd.Next(0, _curGen.Length);
				_nextGen[newIndex].set(_curGen[mutIndex]);
				_nextGen[newIndex].mutation();
				++newIndex;
				if( _nextGen.Length <= newIndex ) break;

				// そのままコピー
				var copyIndex = _selectRnd.Next(0, _curGen.Length);
				_nextGen[newIndex].set(_curGen[copyIndex]);
				++newIndex;
				if( _nextGen.Length <= newIndex ) break;
			}

			// 次世代を現世代に移す
			for( int i = 0; i < _nextGen.Length; ++i ) {
				_curGen[i].set(_nextGen[i]);
			}
			++_genCnt;
		}

		private Bitmap	_img			= null;
		private byte[]	_org			= null;
		private byte[]	_buf			= null;

		private Timer	_refreshTimer	= new Timer();
		private Timer	_updateTimer	= new Timer();
		private Font	_font			= null;
		private Brush	_fontBrush		= null;
		private int		_sec			= 0;
		private int		_genCnt			= 0;

		private Gene[]	_curGen			= new Gene[64];
		private Gene[]	_nextGen		= new Gene[64];
		private Random	_selectRnd		= new Random();
		private Gene	_cross1Buf		= new Gene();
		private Gene	_cross2Buf		= new Gene();
		private Gene	_topGen			= new Gene();
	}
}

 

このままでは処理速度に難がありそうですが、実行してみます

 

ウィンドウの中で、上が目指す画像で、下が完全ランダム値からはじめて、

最終的には同じ絵になって欲しい部分です。

はじめの方

：

：

 

約50分後

 

う、うーん…ダメだ

さすがにパターンが多すぎたようです。

それに、交叉や突然変異の確率、評価処理もかなー、 見直しが必要そうです。

というか、そもそも全ピクセルランダムスタートで辿り着けるのか。。。

 

ただ、薄っすらと緑っぽく近づいてきてはいるので、アプローチの方向はまだ捨てずに

おこうと 思いますが、今回はここまで

 

では