Possible to reproduce the "resize image" quality of Paint.NET?

Question

I have been having a tough time creating a thumbnail that is not horrible quality. So far the best code i've come up with is:

Bitmap bmp = new Bitmap(width, height);
Graphics graphic = Graphics.FromImage(bmp);
graphic.InterpolationMode = InterpolationMode.HighQualityBicubic;
graphic.SmoothingMode = SmoothingMode.HighQuality;
graphic.PixelOffsetMode = PixelOffsetMode.HighQuality;
graphic.CompositingQuality = CompositingQuality.HighQuality;
graphic.DrawImage(photo, 0, 0, width, height);
return imageToByteArray(bmp);

Which produces this gem:

If I resize the same image in Paint.NET i get this:

Which is WAY better. Everything I've found on line points me to some variation of the code I have above. I know Paint.NET was open source at one point. Does anyone know what magic they were doing to create such nice resize functionality and if that functionality can be reproduced in C#?

UPDATE:

The original image from this example was a jpg

Answer 1

GIFs

I recalled reading that .NET has issues with palette-based formats, like GIF, so I dug up a few articles.

This article describes how to quantize (pick an optimum palette) to improve quality: http://msdn.microsoft.com/en-us/library/aa479306.aspx, as does this (badly formatted) article.

In brief, I believe GDI+ picks a non-optimum palette when performing the resize.

PNGs

PNGs are palette-based, so they may be prone to the same issues as GIFs. I'm not sure if it matters that the palette can be much larger.

JPEG-friendly example

This code should work fine on JPEGs (but does not render GIFs smoothly). If you try it and it pixelates a JPEG, then there is probably something else going on.

private static byte[] GetScaledImage( byte[] inputBytes, int width, int height ) {
    Image img = null;

    using( MemoryStream ms = new MemoryStream() ) {
        ms.Write( inputBytes, 0, inputBytes.Length );
        img = Image.FromStream( ms );
    }

    using( MemoryStream ms = new MemoryStream() ) {
        using( Image newImg = new Bitmap( width, height ) ) {
            using( Graphics g = Graphics.FromImage( newImg ) ) {
                g.InterpolationMode = InterpolationMode.HighQualityBicubic;
                g.DrawImage( img, 0, 0, width, height );

                newImg.Save( ms, img.RawFormat );
                return ms.GetBuffer();
            }
        }
    }
}

Answer 2

since Bitmap(int,int) is effectively Bitmap(int,int,PixelFormat.Format32bppArgb) I think the problem is in source image. Try to create another intermediate copy of the image of the same size as source image if using palette, then use that 32bppArgb image source for your resize function.