Dan Byström’s Bwain

Blog without an interesting name

Archive for the ‘.NET’ Category

Thumbnails with glass table reflection in GDI+

Posted by Dan Byström on January 12, 2009

vistathumbnailsI’ve been playing around with image processing lately and since my last post about loading thumbnail images from files I couldn’t help myself from trying to roll my own “Web 2.0 reflection effect” directly in .NET 2.0 with no 3D support whatsoever. Actually, I think was more inspired by Windows Vista’s thumbnails (to the right) than the web.

This is what I eventually came up with:

reflectionsamples1

Although this is all easy – since there were a few things that couldn’t be done in “pure” GDI+ and then some uncommon approaches involved in my solution, I think that there may be some people out there who don’t find this totally trivial. So I thought that it might be worth writing this down.

From the original picture I work through four steps:

reflectionsteps2

1. The first step merely shrinks the original picture to the desired size and puts a frame around it. This is trivial:

	protected virtual Bitmap createFramedBitmap( Bitmap bmpSource, Size szFull )
	{
		Bitmap bmp = new Bitmap( szFull.Width, szFull.Height );
		using ( Graphics g = Graphics.FromImage( bmp ) )
		{
			g.FillRectangle( FrameBrush, 0, 0, szFull.Width, szFull.Height );
			g.DrawRectangle( BorderPen, 0, 0, szFull.Width - 1, szFull.Height - 1 );
			g.InterpolationMode = System.Drawing.Drawing2D.InterpolationMode.HighQualityBicubic;
			g.DrawImage(
				bmpSource,
				new Rectangle( FrameWidth, FrameWidth, szFull.Width - FrameWidth * 2, szFull.Height - FrameWidth * 2 ),
				new Rectangle( Point.Empty, bmpSource.Size ),
				GraphicsUnit.Pixel );
		}
		return bmp;
	}

(Note the InterpolationMode property. It is important in order to resize the image with good quality!)

2. The second step is substantially more involved. It takes the result from step 1 and does this, all in one go:

  1. Flip the image upside down (omitting the upper and lower parts of frame, since we don’t want them to be present in the reflection).
  2. Apply a Gaussian blur convolution effect to make the image look…, well, blurred… 🙂
  3. Wash out some color to make the reflection a little bit grayish.
  4. Apply an alpha blend fall out.

Flipping the image and the color wash-out can both be done directly in GDI+. Flip either with Bitmap.RotateFlip or with a transformation matrix and use a ColorMatrix to alter the colors. But since neither a blur effect nor an alpha blend can be done without direct pixel manipulation I did it all in one go. For the blur effect, see Christian Graus excellent article series Image Processing for Dummies with C# and GDI+. I’ve blogged earlier on how to perform alpha blending previously by drawing the blend using a PathGradientBrush or a LinearGradientBrush in Soft edged images in GDI+. This time I will calculate the alpha value instead. The calculation is done once for every scan line and is located in a virtual function so that this formula can be overridden.

All four “effects” are handled in this loop:

	for ( int y = height-1 ; y >= 0 ; y-- )
	{
		byte alpha = (byte)(255 * calculateAlphaFallout( (double)(height - y) / height ));
		Pixel* pS = (Pixel*)bdS.Scan0.ToPointer() + bdS.Width * (bdS.Height - y - FrameWidth - 1);
		Pixel* pD = (Pixel*)bdD.Scan0.ToPointer() + bdD.Width * y;
		for ( int x = bdD.Width ; x > 0 ; x--, pD++, pS++ )
		{
			int R = gaussBlur( &pS->R, nWidthInPixels );
			int G = gaussBlur( &pS->G, nWidthInPixels );
			int B = gaussBlur( &pS->B, nWidthInPixels );
			pD->R = (byte)((R * 3 + G * 2 + B * 2) / 7);
			pD->G = (byte)((R * 2 + G * 3 + B * 2) / 7);
			pD->B = (byte)((R * 2 + G * 2 + B * 3) / 7);
			pD->A = alpha;
		}
	}

Flipping happens on line 4, blurring on lines 8-10 (the gaussBlur function is just a one-liner). Color wash-out is done on lines 11-13 and the alpha fall-out on lines 3 and 14.

The very observant reader will notice that I let the blurring wrap from one edge to another. This is a hack, but it works since the left and right edges are always exactly identical. In production code, it might be a good idea to make the blurring optional (or even to provide a user-defined convolution matrix) and also to do the same from the color wash-out which currently uses hard-coded values.

3. Create the “half sheared” bitmap:

This transform cannot be accomplished using a linear transformation, but (after taking quite a a detour on this) I realized that it can be done embarrassingly simple:

	using ( Graphics g = Graphics.FromImage( Thumbnail ) )
		for ( int x = 0 ; x < sz.Width ; x++ )
			g.DrawImage(
				bmpFramed,
				new RectangleF( x, 0, 1, sz.Height - Skew * (float)(sz.Width - x) / sz.Width ),
				new RectangleF( x, 0, 1, sz.Height ),
				GraphicsUnit.Pixel );
&#91;/sourcecode&#93;

I simply use DrawImage to draw each column by its own, transferring one column from the framed image from step 1 to a column of different height. Note that it is extremely important that we pass <strong>float</strong>s and not <strong>int</strong>s - in the latter case the result will be a disaster.

<span style="font-size:x-large;">4.</span> Draw the reflection image through a shear transform, like this:


	using ( Graphics g = Graphics.FromImage( Thumbnail ) )
	{
		System.Drawing.Drawing2D.Matrix m = g.Transform;
		m.Shear( 0, (float)Skew / sz.Width);
		m.Translate( 0, sz.Height - Skew - 1 );
		g.Transform = m;
		g.DrawImage( bmpReflection, Point.Empty );
	}
 

Download demo source code

A Lesson Learned

At first, I tried to do the shearing in both step 3 & 4 myself using code similar to this (still one column at a time):

	// this was a bad idea
	private static void paintRowWithResize(
		BitmapData bdDst,
		BitmapData bdSrc,
		int nDstColumn,
		int nSrcColumn,
		int nDstRow,
		double dblSrcRow,
		int nRows,
		double dblStep )
	{
		unchecked
		{
			unsafe
			{
				Pixel* pD = (Pixel*)bdDst.Scan0.ToPointer() + nDstColumn + nDstRow * bdDst.Width;
				Pixel* pS = (Pixel*)bdSrc.Scan0.ToPointer() + nSrcColumn;
				while ( nRows -- > 0 )
				{
					int nYSrc = (int)dblSrcRow;
					Pixel p1 = pS[nYSrc * bdSrc.Width];
					Pixel p2 = p2 = pS[(nYSrc + 1) * bdSrc.Width];
					double frac2 = dblSrcRow - nYSrc;
					double frac1 = 1.0 - frac2;
					pD->R = (byte)(p1.R * frac1 + p2.R * frac2);
					pD->G = (byte)(p1.G * frac1 + p2.G * frac2);
					pD->B = (byte)(p1.B * frac1 + p2.B * frac2);
					pD->A = (byte)(p1.A * frac1 + p2.A * frac2);

					dblSrcRow += dblStep;
					pD += bdDst.Width;
				}
			}
		}
	}

The result looked perfectly good, but after thinking about it for awhile I realized that this piece of code actually is completely and utterly wrong in the general case: it only works when the alpha values of the two adjacent pixels are very close. In other cases the result will be poor.

Perhaps the easiest way to see this is to think about what happens when we want a 50% mix of a completely transparent pixel and a completely opaque while pixel. Intuitively I think it’s clear that we want the result to be a white pixel with 50% transparency. However, if we represent the transparent pixel with (0,0,0,0) (the most common value I’d guess, although (0,x,x,x) is transparent regardless of the value of x) we get a gray half transparent pixel instead (127,127,127,127). Not right at all. The reason I thought my attempt looked good in the first place was just because I had a gray border around the images!

So how do we mix pixels with alpha values? Obviously “normal” alpha blending is not sufficient when we have alpha values on both pixels… after thinking about this for a few minutes,  I said to myself “why not ask someone who knows instead?”. That someone is of course Graphics.DrawImage, and so I ended up with much cleaner code. And although I never bothered to figure out how to mix and blend pixels when both pixels contain alpha values I ended up realizing this:

Graphics.DrawImage has quite a bit of work to do when we draw a 32-bit bitmap on top of another. If we have some a-priori knowledge of the nature of the bitmaps we’re working with (are any of them totally opaque?) then it is actually possible to do this ourselves much faster than Graphics.DrawImage has a chance to, because it is forced to work with the general case: both bitmaps may be semi-transparent.

I will get back on how we in some cases can outperform Graphics.DrawImage (when it comes to speed), and hopefully a real life case when we actually bother. Stay tuned. Ekeforshus

Posted in .NET, GDI+, Programming | 12 Comments »

Image.GetThumbnailImage and beyond

Posted by Dan Byström on January 5, 2009

Once I tried to use Image.GetThumbnailImage because I wanted to fire up small thumbnails as fast as possible. So I tried:

	// totally and completely, utterly useless
	private Bitmap getThumbnailImage( string filename, int width, int height )
	{
		using ( Image img = Image.FromFile( filename ) )
			return (Bitmap)img.GetThumbnailImage( width, height, null, IntPtr.Zero );
	}

This turned out to be completely useless, since Image.FromFile first loads the full image so that no performance is gained whatsoever. Trying to google after a solution only resulted in tons of articles saying that Image.GetThumbnailImage is pretty useless and shouldn’t be used. So I dropped it and solved my problem in a completely different way. Now I just stumbled across an overloaded version Image.FromStream which I haven’t noticed before:

Image.FromStream( Stream stream, bool useEmbeddedColorManagement, bool validateImageData )

This opens up for some interesting usages. For example it means that we really can get a thumbnail fast:

	// way, way faster, but still pretty useless
	private Bitmap getThumbnailImage( string filename, int width, int height )
	{
		using ( FileStream fs = new FileStream( filename, FileMode.Open ) )
		using ( Image img = Image.FromStream( fs, true, false ) )
			return (Bitmap)img.GetThumbnailImage( width, height, null, IntPtr.Zero );
	}

This is still pretty useless, since this way we really don’t know how to get a proportional thumbnail. This is something that seems to be lacking in GDI+: an easy way to rescale images proportionally. Quite frankly: how often are we interested in non-proportional rescales? Not that often, I’d say! Here’s a better version:

	// actually works...
	private Bitmap getThumbnailImage( string filename, int width )
	{
		using ( FileStream fs = new FileStream( filename, FileMode.Open ) )
		using ( Image img = Image.FromStream( fs, true, false ) )
			return (Bitmap)img.GetThumbnailImage(
				width,
				width * img.Height / img.Width,
				null,
				IntPtr.Zero );
	}

But if we arm ourselves with a way to rescale images proportionally, something Microsoft apparently decided to leave as an exercise for each and every programmer who wants to do even the simplest things with images in GDI+:

	public static Size adaptProportionalSize(
		Size szMax,
		Size szReal )
	{
		int nWidth;
		int nHeight;
		double sMaxRatio;
		double sRealRatio;

		if ( szMax.Width < 1 || szMax.Height < 1 || szReal.Width < 1 || szReal.Height < 1 )
			return Size.Empty;

		sMaxRatio = (double)szMax.Width / (double)szMax.Height;
		sRealRatio = (double)szReal.Width / (double)szReal.Height;

		if ( sMaxRatio < sRealRatio )
		{
			nWidth = Math.Min( szMax.Width, szReal.Width );
			nHeight = (int)Math.Round( nWidth / sRealRatio );
		}
		else
		{
			nHeight = Math.Min( szMax.Height, szReal.Height );
			nWidth = (int)Math.Round( nHeight * sRealRatio );
		}

		return new Size( nWidth, nHeight );
	}
&#91;/sourcecode&#93;

With that, we can fire up a thumbnail image fast, with a given maximum allowed size while still proportional:

&#91;sourcecode language='csharp'&#93;
	// even better...
	private Bitmap getThumbnailImage( string filename, Size szMax )
	{
		using ( FileStream fs = new FileStream( filename, FileMode.Open ) )
		using ( Image img = Image.FromStream( fs, true, false ) )
		{
			Size sz = adaptProportionalSize( szMax, img.Size );
			return (Bitmap)img.GetThumbnailImage(
				sz.Width,
				sz.Height,
				null,
				IntPtr.Zero );
		}
	}
&#91;/sourcecode&#93;

So, it appears that <strong>Image.GetThumbnailImage</strong> had its use after all! But there's more we can do with this.

Even though we managed to load thumbnail images fast and proportionally, the quality isn't particularly good. That's seems to be the main concern among those who advocate not using Image.GetThumbnailImage at all. If a thumbnail is found in the image file it has already been resized once, and resizing a resized image once more certainly won't improve the quality, especially if a crappy resizing algorithm is being used. Let's see what we can do about this. If we're working with JPG images coming from a digital camera, we can most probably find the "real" thumbnail image like this:


	private Bitmap getExifThumbnail( string filename )
	{
		using ( FileStream fs = new FileStream( filename, FileMode.Open ) )
		using ( Image img = Image.FromStream( fs, true, false ) )
		{
			foreach ( PropertyItem pi in img.PropertyItems )
				if ( pi.Id == 20507 )
					return (Bitmap)Image.FromStream( new MemoryStream( pi.Value ) );
		}
		return null;
	}

If we can retrieve a thumbnail this way, it will be in its original size and so we can skip an implicit resize. If we want to rescale it anyway, we can do it in a high quality fashion. I don’t know if this is something everybody knows – I had worked with GDI+ for quite some time before I found it – but fact is that resizing an image like this give good performance but crappy result:

	// poor image quality
	Bitmap bmpResized = new Bitmap( bmpOriginal, newWidth, newHeight );

Instead, try the following:

	// superior image quality
	Bitmap bmpResized = new Bitmap( newWidth, newHeight );
	using ( Graphics g = Graphics.FromImage( bmpResized ) )
	{
		g.InterpolationMode = InterpolationMode.HighQualityBicubic;
		g.DrawImage(
			bmpOriginal,
			new Rectangle( Point.Empty, bmpResized.Size ),
			new Rectangle( Point.Empty, bmpOriginal.Size ),
			GraphicsUnit.Pixel );
	}

With these code pieces glued together I can now get a thumbnail from a JPG image both faster and with better quality than with my original Image.ImageFromThumbnail attempt!

UPDATE: This technique is used “live” in the demo source code accompanying this post: Thumbnails with glass table reflection in GDI+.

Finally, one more thing that I just come to think of while I was typing this. I have complained in earlier posts that Image.FromFile for some obscure reason keeps the file locked until disposed of. I just realized that there is an easy way around his:

	using ( FileStream fs = new FileStream( filename, FileMode.Open ) )
		bmp = (Bitmap)Image.FromStream( fs );

Behold – now the image is loaded and the file is NOT locked! 🙂 Ekeforshus

Posted in .NET, GDI+, Programming | 17 Comments »

Optimizing away II.3

Posted by Dan Byström on January 1, 2009

Oh, the pain, the pain and the embarrassment…

I just came to realize that although a “long” in C# is 64 bits, in C++ it is still 32 bits. In order to get a 64 bit value in MSVC++ you must type either “long long” or “__int64”. I didn’t know that. 😦

This means that although the assembler function I just presented correctly calculates a 64 bit value, it will be truncated to 32 bits because the surrounding C++ function is declared as a long.

This in turn means that for bitmaps larger than 138 x 138 pixels – the correct result cannot be guaranteed. (With 64 bit values, the bitmap can instead be 9724315 x 9724315 pixels in size before an overflow can occur.)

Unfortunately, although I had unit test to verify the correctness of the function, I only tested with small bitmaps.

I have uploaded a new version. Ekeforshus

Posted in .NET, Programming | 3 Comments »

Optimizing away II.2

Posted by Dan Byström on December 30, 2008

I was asked to upload the source and binary for my last post.

Posted in .NET, Programming | 2 Comments »

Optimizing away II

Posted by Dan Byström on December 22, 2008

Continued from Optimizing away. Ok, now I have worked up the courage.

Prepare yourself for a major disappointment. I really do not know how to tweak that C#-loop to run a nanosecond faster. But I can do the same calculation much faster. How? Just my old favorite party trick. It goes like this:

1. Add a new project to your solution

2. Chose Visual C++ / CLR / Class Library

3. Insert the following managed class:

	public ref class FastImageCompare
	{
	public:
		static double compare( void* p1, void* p2, int count )
		{
			return NativeCode::fastImageCompare( p1, p2, count );
		}
		static double compare( IntPtr p1, IntPtr p2, int count )
		{
			return NativeCode::fastImageCompare( p1.ToPointer(), p2.ToPointer(), count );
		}
	};

4. Insert the following function into an unmanaged class (which I happened to call NativeCode):

unsigned long long NativeCode::fastImageCompare( void* p1, void* p2, int count )
{
	int high32 = 0;

	_asm
	{
		push	ebx
		push	esi
		push	edi

		mov		esi, p1
		mov		edi, p2
		xor		eax, eax
again:
		dec		count
		js		done

		movzx	ebx, [esi]
		movzx	edx, [edi]
		sub		edx, ebx
		imul	edx, edx

		movzx	ebx, [esi+1]
		movzx	ecx, [edi+1]
		sub		ebx, ecx
		imul	ebx, ebx
		add		edx, ebx

		movzx	ebx, [esi+2]
		movzx	ecx, [edi+2]
		sub		ebx, ecx
		imul	ebx, ebx
		add		edx, ebx

		add		esi, 4
		add		edi, 4

		add		eax, edx
		jnc		again

		inc		high32
		jmp		again
done:
		mov		edx, high32

		pop		edi
		pop		esi
		pop		ebx
	}

}

Yeah. That’s it. Hand tuned assembly language within a .NET Assembly. UPDATE 2009-01-01: return type of the function changed from “unsigned long” to “unsigned long long”, see here.

I guess that’s almost cheating. And we will be locked inside the Intel platform. Most people won’t mind I guess, but other may have very strong feelings about it. If we really would like to exploit this kind of optimizations while still be portable (to Mono/Mac for example) one possibility would be to load the assembly with native code dynamically. If it fails we could fall back to an alternative version written in pure managed code.

(I know from experience that some people with lesser programming skills react to this with a “what? it must be a crappy compiler if you can write faster code by yourself”. Let me assure you that this is not the case. On the contrary: I’m amazed about the quality of the code emitted by the C# + .NET JIT compilers.)

Posted in .NET, Programming | 13 Comments »

Optimizing away

Posted by Dan Byström on December 16, 2008

Follow-up on Improving performance…  and Genetic Programming: Evolution of Mona Lisa.
I just tested that I can optimize this loop:

unchecked
{
    unsafe
    {
        fixed ( Pixel* psourcePixels = sourcePixels )
        {
            Pixel* p1 = (Pixel*)bd.Scan0.ToPointer();
            Pixel* p2 = psourcePixels;
            for ( int i = sourcePixels.Length ; i > 0 ; i--, p1++, p2++ )
            {
                int r = p1->R - p2->R;
                int g = p1->G - p2->G;
                int b = p1->B - p2->B;
                error += r * r + g * g + b * b;
            }
        }
    }
}

so that it runs even 60% faster. Don’t dare to tell you how, however.

EDIT: Continued here Ekeforshus

Posted in .NET, Programming | 4 Comments »

Improving performance…

Posted by Dan Byström on December 14, 2008

…of the fitness function in the EvoLisa project. In case you managed to miss it, EvoLisa is an already world famous project created by Roger Alsing earlier this week.

Continued from this post.

With just a few changes, we can actually make the original fitness function run 25 times faster. I’ll start by presenting the original code and then directly the improved version. After that I’ll discuss my reasoning behind each one of the changes.

Original code:

	public static class FitnessCalculator
	{
		public static double GetDrawingFitness( DnaDrawing newDrawing, Color[,] sourceColors )
		{
			double error = 0;

			using ( var b = new Bitmap( Tools.MaxWidth, Tools.MaxHeight, PixelFormat.Format24bppRgb ) )
			using ( Graphics g = Graphics.FromImage( b ) )
			{
				Renderer.Render(newDrawing, g, 1);

				BitmapData bmd1 = b.LockBits(
					new Rectangle( 0, 0, Tools.MaxWidth, Tools.MaxHeight ),
					ImageLockMode.ReadOnly,
					PixelFormat.Format24bppRgb );

				for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
				{
					for ( int x = 0 ; x < Tools.MaxWidth ; x++ )
					{
						Color c1 = GetPixel( bmd1, x, y );
						Color c2 = sourceColors&#91;x, y&#93;;

						double pixelError = GetColorFitness( c1, c2 );
						error += pixelError;
					}
				}

				b.UnlockBits( bmd1 );
			}

			return error;
		}

		private static unsafe Color GetPixel( BitmapData bmd, int x, int y )
		{
			byte* p = (byte*)bmd.Scan0 + y * bmd.Stride + 3 * x;
			return Color.FromArgb( p&#91;2&#93;, p&#91;1&#93;, p&#91;0&#93; );
		}

		private static double GetColorFitness( Color c1, Color c2 )
		{
			double r = c1.R - c2.R;
			double g = c1.G - c2.G;
			double b = c1.B - c2.B;

			return r * r + g * g + b * b;
		}

	}
&#91;/sourcecode&#93;

Optimized code, 25 times as fast:

&#91;sourcecode language='csharp'&#93;
	public struct Pixel
	{
		public byte B;
		public byte G;
		public byte R;
		public byte A;
	}

	public class NewFitnessCalculator : IDisposable
	{
		private Bitmap _bmp;
		private Graphics _g;

		public NewFitnessCalculator()
		{
			_bmp = new Bitmap( Tools.MaxWidth, Tools.MaxHeight );
			_g = Graphics.FromImage( _bmp );
		}

		public void Dispose()
		{
			_g.Dispose();
			_bmp.Dispose();
		}

		public double GetDrawingFitness( DnaDrawing newDrawing, Pixel&#91;&#93; sourcePixels )
		{
			double error = 0;

			Renderer.Render(newDrawing, g, 1);

			BitmapData bd = _bmp.LockBits(
				new Rectangle( 0, 0, Tools.MaxWidth, Tools.MaxHeight ),
				ImageLockMode.ReadOnly,
				PixelFormat.Format32bppArgb );

			unchecked
			{
				unsafe
				{
					fixed ( Pixel* psourcePixels = sourcePixels )
					{
						Pixel* p1 = (Pixel*)bd.Scan0.ToPointer();
						Pixel* p2 = psourcePixels;
						for ( int i = sourcePixels.Length ; i > 0 ; i--, p1++, p2++ )
						{
							int r = p1->R - p2->R;
							int g = p1->G - p2->G;
							int b = p1->B - p2->B;
							error += r * r + g * g + b * b;
						}
					}
				}
			}
			_bmp.UnlockBits( bd );

			return error;
		}

	}

First of all we notice that each time the fitness function is called, a new bitmap is constructed, used and then destroyed. This is fine for a function that seldom gets called. But for a function that is repeatedly called, we’ll be far better off if we reuse the same Bitmap and Graphics objects over and over.

Therefore I have changed the class from being static into one that muct be instantiated. Of course, that requires some minor changes to the consumer of this class, but in my opinion this will only be for the better. Although convenient, static methods (and/or singletons) are very hostile to unit testing and mocking, so I’m trying to move away from them anyway.

To my surprise, this first optimization attempt only buys us a few percent performance increase. I’m somewhat surprised at this, but anyway, it’s a start, and now it will get better. Read on.

So, once we’ve added a constructor to create the bitmap and graphics objects once and for all (as we’ll as making the class disposable so that the two GDI+ objects can be disposed) we move on to the real performance issues:

	for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
	{
		for ( int x = 0 ; x < Tools.MaxWidth ; x++ )
		{
			Color c1 = GetPixel( bmd1, x, y );
			Color c2 = sourceColors&#91;x, y&#93;;

			double pixelError = GetColorFitness( c1, c2 );
			error += pixelError;
		}
	}
&#91;/sourcecode&#93;

This code looks pretty innocent, eh? It is not.

Even for a moderately sized bitmap, say 1,000 by 1,000 pixels, the code in the inner loop is executed 1,000,000 times. Thats a pretty big number. This means that each tiny little "error", performance-wise, is multiplied by 1,000,000 so every little tiny tiny thing will count in the end.

So for example, just each method call will consume time compared to having the method's code inline within the loop. Above we find two method calls GetPixel and GetColorFitness which will be far better off moved inside the loop, but as I will end up explaining is that the worst performance hog here is really the innocent looking line "Color c2 = sourceColors&#91;x, y&#93;;". Anyway, off we go:

&#91;sourcecode language='csharp'&#93;
			unchecked
			{
				unsafe
				{
					for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
					{
						for ( int x = 0 ; x < Tools.MaxWidth ; x++ )
						{
							byte* p = (byte*)bmd1.Scan0 + y * bmd1.Stride + 3 * x;
							Color c1 = Color.FromArgb( p&#91;2&#93;, p&#91;1&#93;, p&#91;0&#93; );
							Color c2 = sourceColors&#91;x, y&#93;;

							int R = c1.R - c2.R;
							int G = c1.G - c2.G;
							int B = c1.B - c2.B;

							error += R * R + G * G + B * B;
						}
					}
				}
			}
&#91;/sourcecode&#93;

The above changes, including changing the variables R, G &amp; B from double into int will buy us approximately a 30% speed increase. Ain't much compared to 25 times but still we're moving on. Then we can look at the "Color c1" and notice that we can get rid of it completely by simply changing the inner code like so:

&#91;sourcecode language='csharp'&#93;
			byte* p = (byte*)bmd1.Scan0 + y * bmd1.Stride + 3 * x;
			Color c2 = sourceColors&#91;x, y&#93;;

			int R = p&#91;2&#93; - c2.R;
			int G = p&#91;1&#93; - c2.G;
			int B = p&#91;0&#93; - c2.B;

			error += R * R + G * G + B * B;
&#91;/sourcecode&#93;

Now we actually have code that executes TWICE as fast as our original code. And now we must turn our attention to the first two. The rest I don't think we can do much about.

Think about it. What we want to to is loop over each and every pixel in the image. Why then do we need to <em><strong>calculate </strong></em>the memory address for <em><strong>each pixel</strong></em> when we want to move to the <em><strong>next pixel</strong></em>? For each pixel we do completely unnecessary calculations. First "(byte*)bmd1.Scan0 + y * bmd1.Stride + 3 * x"; this contains four variables, two additions and two multiplications when really a single increment is all we need.

Then "sourceColors[x, y]". Fast enough and nothing we can improve here, right? No, no no, this is far WORSE! It looks completely harmless, but not only is a <strong>similar formula as the previous one</strong> taking place behind the scenes; for each pixel, the <em><strong>x and y parameters are being bounds checked</strong></em>, ensuring that we do not pass illegal values to the array-lookup!!!

So this innocent-looking expression will cause someting like this to happen somewhere around a million times for each fitness calculation:


			// pseudo-code
			if ( x < sourceColors.GetLowerBound( 0 ) || y < sourceColors.GetLowerBound( 1 ) || x > sourceColors.GetUpperBound( 0 ) || y > sourceColors.GetUpperBound( 1 ) )
				throw new IndexOutOfRangeException( "(Index was outside the bounds of the array." );
			Color c2 = *( &sourceColors + x * ( sourceColors.GetUpperBound( 1 ) + 1 ) + y );

Now we’re in for a little heavier refactoring. Unfortunately the sourcePixel matrix is laid out column-by-row instead of row-by-column which would have been better, so in order to solve this issue I’ll even change it into a vector of type “Pixel” instead. This requires change to the method signature and to the construction of the the matrix/vector itself of course, but once in place:

			unchecked
			{
				unsafe
				{
					fixed ( Pixel* psourceColors = sourceColors )
					{
						Pixel* pc = psourceColors;
						for ( int y = 0 ; y < Tools.MaxHeight ; y++ )
						{
							byte* p = (byte*)bmd1.Scan0 + y * bmd1.Stride;
							for ( int x = 0 ; x < Tools.MaxWidth ; x++, p += 3, pc++ )
							{
								int R = p&#91;2&#93; - pc->R;
								int G = p[1] - pc->G;
								int B = p[0] - pc->B;

								error += R * R + G * G + B * B;
							}
						}
					}
				}
			}

we´re actually in for a performance improvement of 15 times!!!

Yeah, that’s actually how bad (performance-wise) the innocent looking line “Color c2 = sourceColors[x, y];” was. Bet some of you didn’t know that!!! 🙂

In order to change sourceColors from a matrix of Color into a vector of Pixel (declared as in the second code window above) I did this:

		public static Pixel[] SetupSourceColorMatrix( Bitmap sourceImage )
		{
			if ( sourceImage == null )
				throw new NotSupportedException( "A source image of Bitmap format must be provided" );

			BitmapData bd = sourceImage.LockBits(
			new Rectangle( 0, 0, Tools.MaxWidth, Tools.MaxHeight ),
			ImageLockMode.ReadOnly,
			PixelFormat.Format32bppArgb );
			Pixel[] sourcePixels = new Pixel[Tools.MaxWidth * Tools.MaxHeight];
			unsafe
			{
				fixed ( Pixel* psourcePixels = sourcePixels )
				{
					Pixel* pSrc = (Pixel*)bd.Scan0.ToPointer();
					Pixel* pDst = psourcePixels;
					for ( int i = sourcePixels.Length ; i > 0 ; i-- )
						*( pDst++ ) = *( pSrc++ );
				}
			}
			sourceImage.UnlockBits( bd );

			return sourcePixels;
		}

Probably a little overkill… but what the heck… Now I guess many people who are familiar with LockBits and direct pixel manipulation will cry out HEY YOU CAN’T DO THAT! YOU MUST TAKE THE “STRIDE” INTO ACCOUNT WHEN YOU MOVE TO A NEW SCAN LINE.

Well, yes… and no. Not when I use the PixelFormat.Format32bppArgb! Go figure! 🙂

So our new changes means that we process each ROW in the bitmap blindingly fast, as compared to the original version and combined with our caching of the bitmap we have gained a performance boost of 20 times!

Now for my final version I have rendered the drawing in PixelFormat.Format32bppArgb, which is the default format for bitmaps in GDI+. In that format each pixel will be exactly four bytes in size, which in turn means that GDI+ places no “gap” between the last pixel in one row and the first pixel in the next row and so we are actually able to treat the whole image as a single vector, processing it all in one go.

To conclude: in c# we can use unsafe code and pointer arithmetic to access an array far faster than the normal indexer, because we short-circuit the bounds checking. If we iterate over several consecutive elements in the array our gain is even larger, because we just increment the pointer instead of recalculating the memory address of the cells of the array over and over.

Normally we don’t want to bother with this because the gain of safe and managed code is bigger than the performance gain. But when it comes to image processing this perspective may not be as clear.

BTW, I wrote a post on a similar topic a few months ago: Soft Edged Images in GDI+.

EDIT: Continued here Ekeforshus

Posted in .NET, GDI+, Programming | 15 Comments »

Soft edged images in GDI+

Posted by Dan Byström on August 24, 2008

Last week I felt a sudden urge to create bitmaps with rounded corners and soft edges. Partly because I thought it would look nice, but mostly just as an intellectual exercise. (And also, according to Joel Spolsky, much of the success behind the iPod and iPhone can be attributed to their rounded corner design. That’s the best explanation I have come across, anyway!!! So, rounded corners sell! 🙂 )

Here are some sample pictures:

  1. Ordinary Graphics.DrawImage
  2. We can use a ColorMatrix to draw a semi-transparent image. However, I can’t figure out a way to use this technique to achieve the result I’m after.
  3. This is what I’m trying to achieve. What shall I call it? Smooth edges? Soft edges? Fluffy edges?
  4. In order to achieve 3) I’m about to inject this mask into the original image’s alpha channel.
  5. Although not discussed anymore in the article, we can use Graphics.SetClip to draw an image with round corners, but note the jaggedness at the corners. There may be some way to create anti-aliased clipping regions. If so, please drop a comment and tell me!
  6. Here I have used the technique which I’m discussing here (which produced 3) but without the “fluff” (a PathGradientBrush to be exact). Notice the smooth corners.

After spending way to much time figuring out a “pure” way to do this in GDI+, I gave up and decided to use LockBits to directly manipulate the pixels in the image. This is actually very straightforward and easy, but I can’t help feeling that there ought to be another way. If you know one, please drop a comment here. Using LockBits will result in an IntPtr pointing to the actual bits, leaving us with some different ways to access them:

  1. System.Runtime.InteropServices.Marshal.Copy. We can copy the pixels into a byte array, manipulate them and then copy them back. Unless we´re batch processing large amount of 16 mega pixels images I’ll guess we won’t notice much performance degradation, but it feels a little backward. If we’re going for a pure VB.NET solution, this is our only option I guess.
  2. The unsafe keyword in C#. This is just perfect, if it wasn’t for my previous traumatic experience with how .NET restricts unsafe assemblies. Anyway, this is what I’ll use in the sample code below.
  3. C++ with Managed Extensions. I suspect that most .NET programmers feel uneasy with this, but I think this is a much underestimated option. I’m not kidding you when I say that it actually takes less than ten minutes to add a new C++ project to your Visual Studio solution and write a C++ version of the unsafe code that I’m about to use. A few years ago I wrote a short tutorial on this.

The strategy I decided to go for is simple:

  1. Create a mask like the one in picture 4). This is done by the methods createRoundRect and createFluffyBrush below. The meaning of this mask is simple: the darker a pixel is, the more transparent shall the real image become in that particular place. And vice versa: the lighter a pixel is, the more opaque shall the image become in that part. Is is no coincidence that this is just the way the alpha channel works. 🙂
  2. Then I create a new bitmap as an exact copy of the original image (if I have more use of the original image that is, otherwise this can be skipped).
  3. Finally, I take one of the red, blue or green channels (irrelevant which one) from the mask and copy it into the new bitmap’s alpha channel! This is done by transferOneARGBChannelFromOneBitmapToAnother (surprise!).
  4. Done

So, here are the three helper methods:


        static public GraphicsPath createRoundRect( int x, int y, int width, int height, int radius )
        {
            GraphicsPath gp = new GraphicsPath();

            if (radius == 0)
                gp.AddRectangle( new Rectangle( x, y, width, height ) );
            else
            {
                gp.AddLine( x + radius, y, x + width - radius, y );
                gp.AddArc( x + width - radius, y, radius, radius, 270, 90 );
                gp.AddLine( x + width, y + radius, x + width, y + height - radius );
                gp.AddArc( x + width - radius, y + height - radius, radius, radius, 0, 90 );
                gp.AddLine( x + width - radius, y + height, x + radius, y + height );
                gp.AddArc( x, y + height - radius, radius, radius, 90, 90 );
                gp.AddLine( x, y + height - radius, x, y + radius );
                gp.AddArc( x, y, radius, radius, 180, 90 );
                gp.CloseFigure();
            }
            return gp;
        }


		public static Brush createFluffyBrush(
			GraphicsPath gp,
			float[] blendPositions,
			float[] blendFactors )
		{
			PathGradientBrush pgb = new PathGradientBrush( gp );
			Blend blend = new Blend();
			blend.Positions = blendPositions;
			blend.Factors = blendFactors;
			pgb.Blend = blend;
			pgb.CenterColor = Color.White;
			pgb.SurroundColors = new Color[] { Color.Black };
			return pgb;
		}

		public enum ChannelARGB
		{
			Blue = 0,
			Green = 1,
			Red = 2,
			Alpha = 3
		}

		public static void transferOneARGBChannelFromOneBitmapToAnother(
			Bitmap source,
			Bitmap dest,
			ChannelARGB sourceChannel,
			ChannelARGB destChannel )
		{
			if ( source.Size!=dest.Size )
				throw new ArgumentException();
			Rectangle r = new Rectangle( Point.Empty, source.Size );
			BitmapData bdSrc = source.LockBits( r, ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb );
			BitmapData bdDst = dest.LockBits( r, ImageLockMode.ReadWrite, PixelFormat.Format32bppArgb );
			unsafe
			{
				byte* bpSrc = (byte*)bdSrc.Scan0.ToPointer();
				byte* bpDst = (byte*)bdDst.Scan0.ToPointer();
				bpSrc += (int)sourceChannel;
				bpDst += (int)destChannel;
				for ( int i = r.Height * r.Width; i > 0; i-- )
				{
					*bpDst = *bpSrc;
					bpSrc += 4;
					bpDst += 4;
				}
			}
			source.UnlockBits( bdSrc );
			dest.UnlockBits( bdDst );
		}

I’m not about to explain how any of the above methods work. If you don’t understand… just google for any of the keywords and you’ll find tons of tutorials. If something is still unclear, drop a comment here and I’ll see what I can do. The purpose of this article is the simple idea that you can inject a mask created with normal GDI+ operations into an image’s alpha channel, making that image transparent, semi-transparent or opaque exactly where you want it to. So now we just put it all together:

			Bitmap bmpFluffy = new Bitmap( bmpOriginal );
			Rectangle r = new Rectangle( Point.Empty, bmpFluffy.Size );

			using ( Bitmap bmpMask = new Bitmap( r.Width, r.Height ) )
			using ( Graphics g = Graphics.FromImage( bmpMask ) )
			using ( GraphicsPath path = createRoundRect(
				r.X, r.Y,
				r.Width, r.Height,
				Math.Min( r.Width, r.Height ) / 5 ) )
			using ( Brush brush = createFluffyBrush(
				path,
				new float[] { 0.0f, 0.1f, 1.0f },
				new float[] { 0.0f, 0.95f, 1.0f } ) )
			{
				g.FillRectangle( Brushes.Black, r );
				g.SmoothingMode = SmoothingMode.HighQuality;
				g.FillPath( brush, path );
				transferOneARGBChannelFromOneBitmapToAnother(
					bmpMask,
					bmpFluffy,
					ChannelARGB.Blue,
					ChannelARGB.Alpha );
			}
			// bmpFluffy is now powered up and ready to be used

The code above is sprinkled with magic numbers, so you can tell that it’s not production code! 🙂

  • Math.Min( r.Width, r.Height ) / 5. This is just may way of saying that I want the size of the rounded corners to be 20% the size of the shortest bitmap side.
  • new float[] { 0.0f, 0.1f, 1.0f } and float[] { 0.0f, 0.95f, 1.0f } this controls how much “fluff” I want at the edges. For example, you may find that new float[] { 0.0f, 0.1f, 0.2, 1.0f } and float[] { 0.0f, 0.9f, 1.0f, 1.0f } suits you better!
  • The arguments to transferOneARGBChannelFromOneBitmapToAnother. Why do I copy the blue channel??? Well, red or green will just just fine too! Since we have painted only gray scale values to bmpMask, the red, green and blue channels will be identical!

And of course, the mask doesn’t have to be created this way. Among other things, you could save a predefined Edge from Paint Shop Pro’s Picture Frames and load it into your app.

Happy coding! Ekeforshus

Posted in .NET, GDI+, Programming | 9 Comments »

VB.NET as a DSL

Posted by Dan Byström on July 4, 2008

The other day I got a glimpse of something that could turn out to be really useful. Or maybe a Pandora’s Box. I really don’t know until I investigated it more. 🙂

I was asked to add some simple string manipulation functions (to something that we for simplicity can think of as a report generator).

After thinking about the problem I decided that I would violate the YAGNI (you ain’t gonna need it) principle and give the customer the full Monty directly. Why? Because I realized that it was so incredibly easy to give them the possibility to write full fledged VB.NET code directly that it would probably take the same amount of time to code as some basic string manipulation functions together with a UI!

Consider the following facts:

  1. It is extremely easy (and fast) to compile a piece of VB.NET (or C#) code into an in-memory assembly and execute that code. It takes roughly 20 lines of code.
  2. This dynamically compiled code can easily be given access to any specified part of the application or it’s business objects (just by adding the appropriate assemblies).
  3. Of course the code to be compiled can be preprocessed first, in order to provide the user with a syntax as simple as possible.

I think that these facts taken together implies that opening up parts of the business logic code to the user / customer / domain expert could be worthwhile.

So, the next time I feel that:

  1. I am just transforming the domain expert’s words into executable code
  2. I may not have fully understood the intention of the domain expert
  3. the code I’m writing is likely to change in the future

Then I will definitely consider making that code modifiable by both the domain experts and me (or most likely: read by the domain experts and modified by me and them together). The choice of VB.NET over C# seems obvious; novices read Basic easier – it is no coincidence that “B” in BASIC stands for Beginner. Many users have also encountered VBA while playing around with macros in Word and Excel. Ekeforshus

Posted in .NET, Programming | Leave a Comment »

The åäö Ghost Strikes… AGAIN!

Posted by Dan Byström on July 25, 2007

Just when I thought we were out of the dark ages… something hit me right out of the blue.

During the summer something strange has happened, which I suspect happened because of some Microsoft security update. That is at least more probable than an ill-willing gnome in my machine fiddling with some bits. But you never know.

What has happened is that the

System.Windows.Forms.Application.ExecutablePath

property all of a sudden returns an incorrect result if the path contains a “non-ASCII” character like our swedish charaters åäö!!!

Replacing it with a

System.Reflection.Assembly.GetExecutingAssembly().Location

fixes the problem.

Demonstration:

  1. Fire up a new windows forms project and add “MessageBox.Show( Application.ExecutablePath );” to the default form’s constructor.
  2. Compile and place the exe in a folder called “c:\Our Application”.
  3. Run and you get “C:\Our Application\WindowsApplication1.exe”.
  4. Now rename the folder to “c:\Vår Applikation”.
  5. Run and you get “C:\V�r Applikation\WindowsApplication1.exe”. Where the “�” character is #65533.

The scary thing is that this behavior just changed over night.

Posted in .NET, Uncategorized | Leave a Comment »