path: root/Software/Visual_Studio/Tango.RemoteDesktop/Quantization/Quantizer.cs

/////////////////////////////////////////////////////////////////////////////////
// Paint.NET                                                                   //
// Copyright (C) dotPDN LLC, Rick Brewster, Tom Jackson, and contributors.     //
// Portions Copyright (C) Microsoft Corporation. All Rights Reserved.          //
// See src/Resources/Files/License.txt for full licensing and attribution      //
// details.                                                                    //
// .                                                                           //
/////////////////////////////////////////////////////////////////////////////////

// Based on: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnaspp/html/colorquant.asp

using Tango.RemoteDesktop.Quantization;
using System;
using System.Drawing;
using System.Drawing.Imaging;
using System.Runtime.InteropServices;

namespace Tango.RemoteDesktop.Quantization
{
    internal unsafe abstract class Quantizer
    {
        /// <summary>
        /// Flag used to indicate whether a single pass or two passes are needed for quantization.
        /// </summary>
        private bool singlePass;
        
        protected int ditherLevel;
        public int DitherLevel
        {
            get
            {
                return this.ditherLevel;
            }

            set
            {
                this.ditherLevel = value;
            }
        }

        /// <summary>
        /// Construct the quantizer
        /// </summary>
        /// <param name="singlePass">If true, the quantization only needs to loop through the source pixels once</param>
        /// <remarks>
        /// If you construct this class with a true value for singlePass, then the code will, when quantizing your image,
        /// only call the 'QuantizeImage' function. If two passes are required, the code will call 'InitialQuantizeImage'
        /// and then 'QuantizeImage'.
        /// </remarks>
        public Quantizer(bool singlePass)
        {
            this.singlePass = singlePass;
        }

        /// <summary>
        /// Quantize an image and return the resulting output bitmap
        /// </summary>
        /// <param name="source">The image to quantize</param>
        /// <returns>A quantized version of the image</returns>
        public Bitmap Quantize(Image source)
        {
            // Get the size of the source image
            int height = source.Height;
            int width = source.Width;

            // And construct a rectangle from these dimensions
            Rectangle bounds = new Rectangle(0, 0, width, height);

            // First off take a 32bpp version of the image
            Bitmap img32bpp;
            
            if (source is Bitmap && source.PixelFormat == PixelFormat.Format32bppArgb)
            {
                img32bpp = (Bitmap)source;
            }
            else
            {
                img32bpp = new Bitmap(width, height, PixelFormat.Format32bppArgb);

                // Now lock the bitmap into memory
                using (Graphics g = Graphics.FromImage(img32bpp))
                {
                    g.PageUnit = GraphicsUnit.Pixel;

                    // Draw the source image onto the copy bitmap,
                    // which will effect a widening as appropriate.
                    g.DrawImage(source, 0, 0, bounds.Width, bounds.Height);
                }
            }

            // And construct an 8bpp version
            Bitmap output = new Bitmap(width, height, PixelFormat.Format8bppIndexed);

            // Define a pointer to the bitmap data
            BitmapData sourceData = null;

            try
            {
                // Get the source image bits and lock into memory
                sourceData = img32bpp.LockBits(bounds, ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

                // Call the FirstPass function if not a single pass algorithm.
                // For something like an octree quantizer, this will run through
                // all image pixels, build a data structure, and create a palette.
                if (!singlePass)
                {
                    FirstPass(sourceData, width, height);
                }

                // Then set the color palette on the output bitmap. I'm passing in the current palette 
                // as there's no way to construct a new, empty palette.
                output.Palette = this.GetPalette(output.Palette);

                // Then call the second pass which actually does the conversion
                SecondPass(sourceData, output, width, height, bounds);
            }

            finally
            {
                // Ensure that the bits are unlocked
                img32bpp.UnlockBits(sourceData);
            }

            if (img32bpp != source)
            {
                img32bpp.Dispose();
                img32bpp = null;
            }

            // Last but not least, return the output bitmap
            return output;
        }

        /// <summary>
        /// Execute the first pass through the pixels in the image
        /// </summary>
        /// <param name="sourceData">The source data</param>
        /// <param name="width">The width in pixels of the image</param>
        /// <param name="height">The height in pixels of the image</param>
        protected virtual void FirstPass(BitmapData sourceData, int width, int height)
        {
            // Define the source data pointers. The source row is a byte to
            // keep addition of the stride value easier (as this is in bytes)
            byte* pSourceRow = (byte*)sourceData.Scan0.ToPointer();
            Int32* pSourcePixel;

            // Loop through each row
            for (int row = 0; row < height; row++)
            {
                // Set the source pixel to the first pixel in this row
                pSourcePixel = (Int32*)pSourceRow;

                // And loop through each column
                for (int col = 0; col < width; col++, pSourcePixel++)
                {
                    InitialQuantizePixel((ColorBgra *)pSourcePixel);
                }

                // Add the stride to the source row
                pSourceRow += sourceData.Stride;
            }
        }

        /// <summary>
        /// Execute a second pass through the bitmap
        /// </summary>
        /// <param name="sourceData">The source bitmap, locked into memory</param>
        /// <param name="output">The output bitmap</param>
        /// <param name="width">The width in pixels of the image</param>
        /// <param name="height">The height in pixels of the image</param>
        /// <param name="bounds">The bounding rectangle</param>
        protected virtual void SecondPass(BitmapData sourceData, Bitmap output, int width, int height, Rectangle bounds)
        {
            BitmapData outputData = null;
            Color[] pallete = output.Palette.Entries;
            int weight = ditherLevel;

            try
            {
                // Lock the output bitmap into memory
                outputData = output.LockBits(bounds, ImageLockMode.ReadWrite, PixelFormat.Format8bppIndexed);

                // Define the source data pointers. The source row is a byte to
                // keep addition of the stride value easier (as this is in bytes)
                byte* pSourceRow = (byte *)sourceData.Scan0.ToPointer();
                Int32* pSourcePixel = (Int32 *)pSourceRow;

                // Now define the destination data pointers
                byte* pDestinationRow = (byte *)outputData.Scan0.ToPointer();
                byte* pDestinationPixel = pDestinationRow;

                int[] errorThisRowR = new int[width + 1];
                int[] errorThisRowG = new int[width + 1];
                int[] errorThisRowB = new int[width + 1];

                for (int row = 0; row < height; row++)
                {
                    int[] errorNextRowR = new int[width + 1];
                    int[] errorNextRowG = new int[width + 1];
                    int[] errorNextRowB = new int[width + 1];

                    int ptrInc;

                    if ((row & 1) == 0)
                    {
                        pSourcePixel = (Int32*)pSourceRow;
                        pDestinationPixel = pDestinationRow;
                        ptrInc = +1;
                    }
                    else
                    {
                        pSourcePixel = (Int32*)pSourceRow + width - 1;
                        pDestinationPixel = pDestinationRow + width - 1;
                        ptrInc = -1;
                    }

                    // Loop through each pixel on this scan line
                    for (int col = 0; col < width; ++col)
                    {
                        // Quantize the pixel
                        ColorBgra srcPixel = *(ColorBgra *)pSourcePixel;
                        ColorBgra target = new ColorBgra();

                        target.B = Utility.ClampToByte(srcPixel.B - ((errorThisRowB[col] * weight) / 8));
                        target.G = Utility.ClampToByte(srcPixel.G - ((errorThisRowG[col] * weight) / 8));
                        target.R = Utility.ClampToByte(srcPixel.R - ((errorThisRowR[col] * weight) / 8));
                        target.A = srcPixel.A;

                        byte pixelValue = QuantizePixel(&target);
                        *pDestinationPixel = pixelValue;
                    
                        ColorBgra actual = ColorBgra.FromColor(pallete[pixelValue]);

                        int errorR = actual.R - target.R;
                        int errorG = actual.G - target.G;
                        int errorB = actual.B - target.B; 

                        // Floyd-Steinberg Error Diffusion:
                        // a) 7/16 error goes to x+1
                        // b) 5/16 error goes to y+1
                        // c) 3/16 error goes to x-1,y+1
                        // d) 1/16 error goes to x+1,y+1

                        const int a = 7;
                        const int b = 5;
                        const int c = 3;

                        int errorRa = (errorR * a) / 16;
                        int errorRb = (errorR * b) / 16;
                        int errorRc = (errorR * c) / 16;
                        int errorRd = errorR - errorRa - errorRb - errorRc;

                        int errorGa = (errorG * a) / 16;
                        int errorGb = (errorG * b) / 16;
                        int errorGc = (errorG * c) / 16;
                        int errorGd = errorG - errorGa - errorGb - errorGc;

                        int errorBa = (errorB * a) / 16;
                        int errorBb = (errorB * b) / 16;
                        int errorBc = (errorB * c) / 16;
                        int errorBd = errorB - errorBa - errorBb - errorBc;

                        errorThisRowR[col + 1] += errorRa;
                        errorThisRowG[col + 1] += errorGa;
                        errorThisRowB[col + 1] += errorBa;

                        errorNextRowR[width - col] += errorRb;
                        errorNextRowG[width - col] += errorGb;
                        errorNextRowB[width - col] += errorBb;

                        if (col != 0)
                        {
                            errorNextRowR[width - (col - 1)] += errorRc;
                            errorNextRowG[width - (col - 1)] += errorGc;
                            errorNextRowB[width - (col - 1)] += errorBc;
                        }

                        errorNextRowR[width - (col + 1)] += errorRd;
                        errorNextRowG[width - (col + 1)] += errorGd;
                        errorNextRowB[width - (col + 1)] += errorBd;

                        // unchecked is necessary because otherwise it throws a fit if ptrInc is negative.
                        unchecked
                        {
                            pSourcePixel += ptrInc;
                            pDestinationPixel += ptrInc;
                        }
                    }

                    // Add the stride to the source row
                    pSourceRow += sourceData.Stride;

                    // And to the destination row
                    pDestinationRow += outputData.Stride;

                    errorThisRowB = errorNextRowB;
                    errorThisRowG = errorNextRowG;
                    errorThisRowR = errorNextRowR;
                }
            }
            
            finally
            {
                // Ensure that I unlock the output bits
                output.UnlockBits(outputData);
            }
        }

        /// <summary>
        /// Override this to process the pixel in the first pass of the algorithm
        /// </summary>
        /// <param name="pixel">The pixel to quantize</param>
        /// <remarks>
        /// This function need only be overridden if your quantize algorithm needs two passes,
        /// such as an Octree quantizer.
        /// </remarks>
        protected virtual void InitialQuantizePixel(ColorBgra *pixel)
        {
        }

        /// <summary>
        /// Override this to process the pixel in the second pass of the algorithm
        /// </summary>
        /// <param name="pixel">The pixel to quantize</param>
        /// <returns>The quantized value</returns>
        protected abstract byte QuantizePixel(ColorBgra *pixel);

        /// <summary>
        /// Retrieve the palette for the quantized image
        /// </summary>
        /// <param name="original">Any old palette, this is overrwritten</param>
        /// <returns>The new color palette</returns>
        protected abstract ColorPalette GetPalette(ColorPalette original);
    }
}