Refactoring Unsafe Code: GIF Image Color Quantizer, Now with Safe Goodness

I’ve had a few requests to create a safe version of the Image Quantization library I’ve blogged about quite a few times: see Use GDI+ to Save Crystal-Clear GIF Images with .NET. It turns out this is quite useful for a lot of people, but the old version contained unsafe code, which wouldn’t run under medium trust with .NET 2.0.

I spent a few hours yesterday creating a safe version of this library.  The re-factoring process was fun, and I found a few cool things you can do with Marshal class with .NET.

Incrementing IntPtrs

I didn’t know you could do this, and there’s probably going to be situations where this doesn’t work, but provided you have used something like the Bitmap’s LockBits method to lock the bits into system memory, you can increment an IntPtr like so:

IntPtr pSourcePixel;

pSourcePixel = (IntPtr)((long)pSourcePixel + _pixelSize);

Pointers To Structures

Never knew about this either, but if you can map a structure to memory by using the Marshal.PtrToStructure method.

(Color32) Marshal.PtrToStructure(pSourcePixel, typeof(Color32));

 

… where Color32 is a structure that looks like this specifying FieldOffset, and pSourcePixel points to a 32-Bit color value

 

 

[StructLayout(LayoutKind.Explicit)]

public struct Color32

{

[FieldOffset(0)]

public byte Blue;

[FieldOffset(1)]

public byte Green;

[FieldOffset(2)]

public byte Red;

[FieldOffset(3)]

public byte Alpha;

}

So, in the end, a method that looked like this (unsafe)

/// <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 unsafe 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++ )

// Now I have the pixel, call the FirstPassQuantize function…

InitialQuantizePixel ( (Color32*)pSourcePixel ) ;

 

// Add the stride to the source row

pSourceRow += sourceData.Stride ;

}

}

Was refactored to this:

/// <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)

IntPtr pSourceRow = sourceData.Scan0;

 

// Loop through each row

for (int row = 0; row < height; row++)

{

// Set the source pixel to the first pixel in this row

IntPtr pSourcePixel = pSourceRow;

 

// And loop through each column

for (int col = 0; col < width; col++)

{

Color32 color = (Color32) Marshal.PtrToStructure(pSourcePixel, typeof(Color32));

// Now I have the pixel, call the FirstPassQuantize function…

InitialQuantizePixel(color);

pSourcePixel = (IntPtr)((long )pSourcePixel + _pixelSize);

}   

 

// Add the stride to the source row

pSourceRow = (IntPtr)((long)pSourceRow + sourceData.Stride);

}

}

So, get the new improved, safe version of the image quantizer here, and the source code here.

About Brendan Tompkins

Brendan runs CodeBetter.Com and Devlicio.Us. He is a former MVP for Microsoft .NET and is president of Port Technology Services, a partner with Port Solution Integrators a provider of hardware and software integration services for the transportation and logistics industry.
This entry was posted in GDI+, Refactoring. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • http://codebetter.com Brendan Tompkins

    License is MIT

  • factormystic

    What’s the source license on this quantizer code?

  • James South

    Was looking at the source code in the download and I stumbled upon PaletteQuantizer.cs

    There’s no example of what it does and how to use it in the demo project though. Could you give an example?

  • Peter

    Thank you for the code! I managed to find a solution for keeping transparency after edit, with the following code (C#)

    public class OctreeQuantizer : Quantizer
    {
          ………………….
            protected override byte QuantizePixel(Color32 pixel)
            {
                byte paletteIndex = (byte)_maxColors;    // The color at [_maxColors] is set to transparent

                // Get the palette index if this non-transparent
                if (pixel.Alpha > 0)
                    paletteIndex = (byte)_octree.GetPaletteIndex(pixel);

                return paletteIndex;
            }

            protected override ColorPalette GetPalette(ColorPalette original)
            {
                // First off convert the octree to _maxColors colors
                ArrayList palette = _octree.Palletize(_maxColors – 1);

                // Then convert the palette based on those colors
                for (int index = 0; index < palette.Count; index++)
                {
                    Color TestColor = (Color)palette[index];
                    //Test set transparent color when color transparency used
                    if (TestColor.ToArgb() == Color.Transparent.ToArgb())
                    {
                        TestColor = Color.FromArgb(0, 0, 0, 0);
                    }
                    original.Entries[index] = TestColor;
                }
                //Clear unused palette entries
                for (int index = palette.Count; index < _maxColors; index++)
                {
                    original.Entries[index] = Color.FromArgb(255, 0, 0, 0);
                }
                // Add the transparent color when alpha transparency used
                original.Entries[_maxColors] = Color.FromArgb(0, Color.Transparent);
                return original;
            }
          ………………….
    }

    public abstract class Quantizer
    {

          ……………………..

    protected virtual void SecondPass(BitmapData sourceData, Bitmap output, int width, int height, Rectangle bounds)
            {
                  ……………………………

      
                            // Check if this is the same as the last pixel. If so use that value
                            // rather than calculating it again. This is an inexpensive optimisation.
                            if (Marshal.ReadInt32(pPreviousPixel) != Marshal.ReadInt32(pSourcePixel))
                            {
                                // Quantize the pixel
                                pixelValue = QuantizePixel(new Color32(pSourcePixel));

                                // And setup the previous pointer
                                pPreviousPixel = pSourcePixel;
                            }

                  ……………………………
           }

          ……………………..

    }

  • Anonymous

    Sure, that woud be great!

    As an FYI – ASP.NET medium trust doesn’t allow the Marshal class to be used. So although the safe version may have many intangible benefits, it doesn’t help with hosting permissions. When you rewrote the safe version, did you notice a decrease in performance?

  • Brendan Tompkins

    Very cool Nathan.. Let me know if it’s ok, and I’ll just send folks your way when they are interested in downloading this.

  • Anonymous

    Yes, IntPtr needs to be cast to (long) for 64-bit support – the above code doesn’t work on 64-bit versions.

    I have a modified/rewritten version with 64-bit support and (optional) adjustable dithering support…. It’s part of the PrettyGifs plugin for http://imageresizing.net/ … You can download the source code at http://imageresizing.net/downloadIt’s in the PluginsPrettyGifs folder.

  • Luigi Grilli

    an amazing job. really helpfull!!!

  • http://twitter.com/QuantumDynamix Quantum Dynamix

    This doesn’t seem to work within Rackspace’s Modified Medium Trust environment (http://cloudsites.rackspacecloud.com/index.php/Overview_of_modified_Medium_Trust). Any clue as to what might be the culprit?

  • http://codebetter.com Brendan Tompkins

    Sorry everyone for the broken link.. I’ve updated the post.

  • http://twitter.com/QuantumDynamix Quantum Dynamix

    REALLY REALLY REALLY need the links to the source code to work. I’m behind on a project and I’m hoping this can save me. PLEASE HELP!!!

  • DrCacho

    Anyone knows where i can gwet the source code? The links takes me tothe home :(

  • http://www.ceptema.org nokia tema

    thanks, good article :)

  • http://www.gmorsecode.com Greg Morse

    Simple fix for VB.NET code above is as follows:
    _paletteIndex = System.Math.Max(System.Threading.Interlocked.Increment(paletteIndex), paletteIndex – 1)
    To:
    _paletteIndex = paletteIndex
    paletteIndex = paletteIndex + 1

  • http://codebetter.com/members/btompkins/default.aspx Brendan Tompkins

    I’m afraid I have checked out to a degree. I’m just not sure when I’m going to have the time to fix the remaining unsafe portion… You should be able to use the same techniques I described to deal with this.

  • http://donnyvblog.blogspot.com Donny V

    To find the unsafe portions just right click the project and go into properties and uncheck “Allow unsafe code”

    The unsafe code is in the BitmapFilter class. I think Brendan has checked out and doesn’t have time to fix this. If someone could please convert this unsafe code to safe code we would all be very grateful.

  • http://donnyvblog.blogspot.com Donny V

    To find the unsafe portions just right click the project and go into properties and uncheck “Allow unsafe code”

    The unsafe code is in the BitmapFilter class. I think Brendan has checked out and doesn’t have time to fix this. If someone could please convert this unsafe code to safe code we would all be very grateful.

  • http://codebetter.com/members/btompkins/default.aspx Brendan Tompkins

    Sorry for the broken links, I’ve updated the download with the latest dll and source, and fixed the ReadByte issue.

    Cheers!

  • http://nathanaeljones.com/ Nathanael Jones

    The download is broke… Object Moved error… loops back to license agreement.

    For the horizontal lines issue, switch Marshal.ReadByte to Marshal.ReadInt32() for both sides of the if() statement in SecondPass.

    Also, follow the comment (from the original post) on moving the transparency color from 255 to 0… definitely works for more images. GDI likes it a 0, for some reason.

  • http://www.ermanspiel.com barbie spiele

    this code is very godd

  • Marc Krawatsky

    I am experiencing the same security exceptions as everyone else.

    See error details below.

    Please advise.

    Required permissions cannot be acquired.
    Exception Details: System.Security.Policy.PolicyException: Required permissions cannot be acquired.

    [FileLoadException: Could not load file or assembly 'ImageQuantization, Version=1.0.3344.17133, Culture=neutral, PublicKeyToken=null' or one of its dependencies. Failed to grant minimum permission requests. (Exception from HRESULT: 0x80131417)]

  • http://www.ozgurdurum.net/haber/69-tuba-buyukustun-tuba-buyukustun-e-dair.html tuba büyüküstün

    I have discovered a problem using your OctreeQuantizer that I fixed by replacing it with the unsafe one from the MSDN article from which you copied it. I haven’t got time to try and figure out exactly what triggers the problem, I’m afraid. What I found was that on certain images I’d generated I got rogue black horizontal lines appearing on my quantized image. If you wish I can send you copies of the original image and the version of the image produced by your quantizer.

  • Anders

    I’m having problem to get your sample run under medium trust. The problem is an Security Exception in the Quantizer constructor. I believe the reason is the use of the Marchal class. On my hosting site this is not allowed. So i can’t run your code in my asp.net hosting. Do you have an easy solution how to remove the use of the Marshal class in your solution?

    Can see in the comments others have been having this problem.

  • Josh

    I can’t get this code to work in medium trust. it seems to have a problem with the marshal calls. any ideas?

    thanks.

    Josh

  • Dan

    dear Mr Tompkins. Thank you for your hard work.

    I have tried to convert your code to VB.NET, (just for the octree qunatitization) , and although it runs, it is not working properly (the palette is all wrong). If you could cast your eye over it, I would be really grateful. There are others who would like to see this great code in VB.NET.

    Thank you.

    Dan

    Public MustInherit Class Quantizer

    ”’

    ”’ Construct the quantizer
    ”’

    ”’ If true, the quantization only needs to loop through the source pixels once
    ”’
    ”’ 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’.
    ”’

    Public Sub New(ByVal singlePass As Boolean)
    _singlePass = singlePass
    _pixelSize = Marshal.SizeOf(GetType(Color32))
    End Sub

    ”’

    ”’ Quantize an image and return the resulting output bitmap
    ”’

    ”’ The image to quantize
    ”’ A quantized version of the image
    Public Function Quantize(ByVal source As System.Drawing.Image) As Bitmap
    ‘ Get the size of the source image
    Dim height As Integer = source.Height
    Dim width As Integer = source.Width

    ‘ And construct a rectangle from these dimensions
    Dim bounds As New Rectangle(0, 0, width, height)

    ‘ First off take a 32bpp copy of the image
    Dim copy As New Bitmap(width, height, PixelFormat.Format32bppArgb)

    ‘ And construct an 8bpp version
    Dim output As New Bitmap(width, height, PixelFormat.Format8bppIndexed)

    ‘ Now lock the bitmap into memory
    Using g As Graphics = Graphics.FromImage(copy)
    g.PageUnit = GraphicsUnit.Pixel

    ‘ Draw the source image onto the copy bitmap,
    ‘ which will effect a widening as appropriate.

    g.DrawImage(source, bounds)
    End Using

    ‘ Define a pointer to the bitmap data
    Dim sourceData As BitmapData = Nothing

    Try
    ‘ Get the source image bits and lock into memory
    sourceData = copy.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 Not _singlePass Then
    FirstPass(sourceData, width, height)
    End If

    ‘ 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 = 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
    copy.UnlockBits(sourceData)
    End Try

    ‘ Last but not least, return the output bitmap
    Return output
    End Function

    ”’

    ”’ Execute the first pass through the pixels in the image
    ”’

    ”’ The source data
    ”’ The width in pixels of the image
    ”’ The height in pixels of the image
    Protected Overridable Sub FirstPass(ByVal sourceData As BitmapData, ByVal width As Integer, ByVal height As Integer)
    ‘ Define the source data pointers. The source row is a byte to
    ‘ keep addition of the stride value easier (as this is in bytes)
    Dim pSourceRow As IntPtr = sourceData.Scan0
    For row As Integer = 0 To height – 1

    ‘ Loop through each row
    ‘ Set the source pixel to the first pixel in this row
    Dim pSourcePixel As IntPtr = pSourceRow
    For col As Integer = 0 To width – 1

    ‘ And loop through each column
    InitialQuantizePixel(New Color32(pSourcePixel))
    pSourcePixel = CType((CType(pSourcePixel, Int32) + _pixelSize), IntPtr)
    Next
    ‘ Now I have the pixel, call the FirstPassQuantize function…
    ‘ Add the stride to the source row
    pSourceRow = CType((CLng(pSourceRow) + sourceData.Stride), IntPtr)
    Next
    End Sub

    ”’

    ”’ Execute a second pass through the bitmap
    ”’

    ”’ The source bitmap, locked into memory
    ”’ The output bitmap
    ”’ The width in pixels of the image
    ”’ The height in pixels of the image
    ”’ The bounding rectangle
    Protected Overridable Sub SecondPass(ByVal sourceData As BitmapData, ByVal output As Bitmap, ByVal width As Integer, ByVal height As Integer, ByVal bounds As Rectangle)
    Dim outputData As BitmapData = Nothing

    Try
    ‘ Lock the output bitmap into memory
    outputData = output.LockBits(bounds, ImageLockMode.[WriteOnly], 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)
    Dim pSourceRow As IntPtr = sourceData.Scan0
    Dim pSourcePixel As IntPtr = pSourceRow
    Dim pPreviousPixel As IntPtr = pSourcePixel

    ‘ Now define the destination data pointers
    Dim pDestinationRow As IntPtr = outputData.Scan0
    Dim pDestinationPixel As IntPtr = pDestinationRow

    ‘ And convert the first pixel, so that I have values going into the loop

    Dim pixelValue As Byte = QuantizePixel(New Color32(pSourcePixel))

    ‘ Assign the value of the first pixel
    Marshal.WriteByte(pDestinationPixel, pixelValue)
    For row As Integer = 0 To height – 1

    ‘ Loop through each row
    ‘ Set the source pixel to the first pixel in this row
    pSourcePixel = pSourceRow

    ‘ And set the destination pixel pointer to the first pixel in the row
    pDestinationPixel = pDestinationRow
    For col As Integer = 0 To width – 1

    ‘ Loop through each pixel on this scan line
    ‘ Check if this is the same as the last pixel. If so use that value
    ‘ rather than calculating it again. This is an inexpensive optimisation.
    If Marshal.ReadByte(pPreviousPixel) <> Marshal.ReadByte(pSourcePixel) Then
    ‘ Quantize the pixel
    pixelValue = QuantizePixel(New Color32(pSourcePixel))

    ‘ And setup the previous pointer
    pPreviousPixel = pSourcePixel
    End If

    ‘ And set the pixel in the output
    Marshal.WriteByte(pDestinationPixel, pixelValue)

    pSourcePixel = CType((CLng(pSourcePixel) + _pixelSize), IntPtr)

    pDestinationPixel = CType((CLng(pDestinationPixel) + 1), IntPtr)
    Next

    ‘ Add the stride to the source row
    pSourceRow = CType((CLng(pSourceRow) + sourceData.Stride), IntPtr)

    ‘ And to the destination row
    pDestinationRow = CType((CLng(pDestinationRow) + outputData.Stride), IntPtr)
    Next
    Finally
    ‘ Ensure that I unlock the output bits
    output.UnlockBits(outputData)
    End Try
    End Sub

    ”’

    ”’ Override this to process the pixel in the first pass of the algorithm
    ”’

    ”’ The pixel to quantize
    ”’
    ”’ This function need only be overridden if your quantize algorithm needs two passes,
    ”’ such as an Octree quantizer.
    ”’

    Protected Overridable Sub InitialQuantizePixel(ByVal pixel As Color32)
    End Sub

    ”’

    ”’ Override this to process the pixel in the second pass of the algorithm
    ”’

    ”’ The pixel to quantize
    ”’ The quantized value
    Protected MustOverride Function QuantizePixel(ByVal pixel As Color32) As Byte

    ”’

    ”’ Retrieve the palette for the quantized image
    ”’

    ”’ Any old palette, this is overrwritten
    ”’ The new color palette
    Protected MustOverride Function GetPalette(ByVal original As ColorPalette) As ColorPalette

    ”’

    ”’ Flag used to indicate whether a single pass or two passes are needed for quantization.
    ”’

    Private _singlePass As Boolean
    Private _pixelSize As Integer

    ”’

    ”’ Struct that defines a 32 bpp colour
    ”’

    ”’
    ”’ This struct is used to read data from a 32 bits per pixel image
    ”’ in memory, and is ordered in this manner as this is the way that
    ”’ the data is layed out in memory
    ”’

    _
    Public Structure Color32

    Public Sub New(ByVal pSourcePixel As IntPtr)
    Dim C As Color32 = Marshal.PtrToStructure(pSourcePixel, GetType(Color32))
    Me.Blue = C.Blue
    Me.Green = C.Green
    Me.Red = C.Red
    Me.Alpha = C.Alpha
    Me.ARGB = C.ARGB
    End Sub

    ”’

    ”’ Holds the blue component of the colour
    ”’

    _
    Public Blue As Byte
    ”’

    ”’ Holds the green component of the colour
    ”’

    _
    Public Green As Byte
    ”’

    ”’ Holds the red component of the colour
    ”’

    _
    Public Red As Byte
    ”’

    ”’ Holds the alpha component of the colour
    ”’

    _
    Public Alpha As Byte

    ”’

    ”’ Permits the color32 to be treated as an int32
    ”’

    _
    Public ARGB As Integer

    ”’

    ”’ Return the color for this Color32 object
    ”’

    Public ReadOnly Property Color() As Color
    Get
    Return Color.FromArgb(Alpha, Red, Green, Blue)
    End Get
    End Property
    End Structure
    End Class

    Public Class OctreeQuantizer
    Inherits Quantizer
    ”’

    ”’ Construct the octree quantizer
    ”’

    ”’
    ”’ The Octree quantizer is a two pass algorithm. The initial pass sets up the octree,
    ”’ the second pass quantizes a color based on the nodes in the tree
    ”’

    ”’ The maximum number of colors to return
    ”’ The number of significant bits
    Public Sub New(ByVal maxColors As Integer, ByVal maxColorBits As Integer)
    MyBase.New(False)
    If maxColors > 255 Then
    Throw New ArgumentOutOfRangeException(“maxColors”, maxColors, “The number of colors should be less than 256″)
    End If

    If (maxColorBits < 1) Or (maxColorBits > 8) Then
    Throw New ArgumentOutOfRangeException(“maxColorBits”, maxColorBits, “This should be between 1 and 8″)
    End If

    ‘ Construct the octree
    _octree = New Octree(maxColorBits)
    _maxColors = maxColors
    End Sub

    ”’

    ”’ Process the pixel in the first pass of the algorithm
    ”’

    ”’ The pixel to quantize
    ”’
    ”’ This function need only be overridden if your quantize algorithm needs two passes,
    ”’ such as an Octree quantizer.
    ”’

    Protected Overloads Overrides Sub InitialQuantizePixel(ByVal pixel As Color32)
    ‘ Add the color to the octree
    _octree.AddColor(pixel)
    End Sub

    ”’

    ”’ Override this to process the pixel in the second pass of the algorithm
    ”’

    ”’ The pixel to quantize
    ”’ The quantized value
    Protected Overloads Overrides Function QuantizePixel(ByVal pixel As Color32) As Byte
    Dim paletteIndex As Byte = CByte(_maxColors)
    ‘ The color at [_maxColors] is set to transparent

    ‘ Get the palette index if this non-transparent
    If pixel.Alpha > 0 Then
    paletteIndex = CByte(_octree.GetPaletteIndex(pixel))
    End If

    Return paletteIndex
    End Function

    ”’

    ”’ Retrieve the palette for the quantized image
    ”’

    ”’ Any old palette, this is overrwritten
    ”’ The new color palette
    Protected Overloads Overrides Function GetPalette(ByVal original As ColorPalette) As ColorPalette
    ‘ First off convert the octree to _maxColors colors
    Dim palette As ArrayList = _octree.Palletize(_maxColors – 1)
    For index As Integer = 0 To palette.Count – 1
    original.Entries(index) = CType(palette(index), Color)
    Next

    ‘ Then convert the palette based on those colors

    ‘ Add the transparent color
    original.Entries(_maxColors) = Color.FromArgb(0, 0, 0, 0)

    Return original
    End Function

    ”’

    ”’ Stores the tree
    ”’

    Private _octree As Octree

    ”’

    ”’ Maximum allowed color depth
    ”’

    Private _maxColors As Integer

    ”’

    ”’ Class which does the actual quantization
    ”’

    Private Class Octree
    ”’

    ”’ Construct the octree
    ”’

    ”’ The maximum number of significant bits in the image
    Public Sub New(ByVal maxColorBits As Integer)
    _maxColorBits = maxColorBits
    _leafCount = 0
    _reducibleNodes = New OctreeNode(8) {}
    _root = New OctreeNode(0, _maxColorBits, Me)
    _previousColor = 0
    _previousNode = Nothing
    End Sub

    ”’

    ”’ Add a given color value to the octree
    ”’

    ”’ Public Sub AddColor(ByVal pixel As Color32)
    ‘ Check if this request is for the same color as the last
    If _previousColor = pixel.ARGB Then
    ‘ If so, check if I have a previous node setup. This will only ocurr if the first color in the image
    ‘ happens to be black, with an alpha component of zero.
    If _previousNode Is Nothing Then
    _previousColor = pixel.ARGB
    _root.AddColor(pixel, _maxColorBits, 0, Me)
    Else
    _previousNode.Increment(pixel)
    ‘ Just update the previous node
    End If
    Else
    _previousColor = pixel.ARGB
    _root.AddColor(pixel, _maxColorBits, 0, Me)
    End If
    End Sub

    ”’

    ”’ Reduce the depth of the tree
    ”’

    Public Sub Reduce()
    Dim index As Integer

    ‘ Find the deepest level containing at least one reducible node
    index = _maxColorBits – 1
    While (index > 0) AndAlso (_reducibleNodes(index) Is Nothing)

    index -= 1
    End While

    ‘ Reduce the node most recently added to the list at level ‘index’
    Dim node As OctreeNode = _reducibleNodes(index)
    _reducibleNodes(index) = node.NextReducible

    ‘ Decrement the leaf count after reducing the node
    _leafCount -= node.Reduce()

    ‘ And just in case I’ve reduced the last color to be added, and the next color to
    ‘ be added is the same, invalidate the previousNode…
    _previousNode = Nothing
    End Sub

    ”’

    ”’ Get/Set the number of leaves in the tree
    ”’

    Public Property Leaves() As Integer
    Get
    Return _leafCount
    End Get
    Set(ByVal value As Integer)
    _leafCount = value
    End Set
    End Property

    ”’

    ”’ Return the array of reducible nodes
    ”’

    Protected ReadOnly Property ReducibleNodes() As OctreeNode()
    Get
    Return _reducibleNodes
    End Get
    End Property

    ”’

    ”’ Keep track of the previous node that was quantized
    ”’

    ”’ The node last quantized
    Protected Sub TrackPrevious(ByVal node As OctreeNode)
    _previousNode = node
    End Sub

    ”’

    ”’ Convert the nodes in the octree to a palette with a maximum of colorCount colors
    ”’

    ”’ The maximum number of colors
    ”’ An arraylist with the palettized colors
    Public Function Palletize(ByVal colorCount As Integer) As ArrayList
    While Leaves > colorCount
    Reduce()
    End While

    ‘ Now palettize the nodes
    Dim palette As New ArrayList(Leaves)
    Dim paletteIndex As Integer = 0
    _root.ConstructPalette(palette, paletteIndex)

    ‘ And return the palette
    Return palette
    End Function

    ”’

    ”’ Get the palette index for the passed color
    ”’

    ”’ ”’
    Public Function GetPaletteIndex(ByVal pixel As Color32) As Integer
    Return _root.GetPaletteIndex(pixel, 0)
    End Function

    ”’

    ”’ Mask used when getting the appropriate pixels for a given node
    ”’

    Private Shared mask As Integer() = New Integer(7) {128, 64, 32, 16, 8, 4, _
    2, 1}

    ”’

    ”’ The root of the octree
    ”’

    Private _root As OctreeNode

    ”’

    ”’ Number of leaves in the tree
    ”’

    Private _leafCount As Integer

    ”’

    ”’ Array of reducible nodes
    ”’

    Private _reducibleNodes As OctreeNode()

    ”’

    ”’ Maximum number of significant bits in the image
    ”’

    Private _maxColorBits As Integer

    ”’

    ”’ Store the last node quantized
    ”’

    Private _previousNode As OctreeNode

    ”’

    ”’ Cache the previous color quantized
    ”’

    Private _previousColor As Integer

    ”’

    ”’ Class which encapsulates each node in the tree
    ”’

    Protected Class OctreeNode
    ”’

    ”’ Construct the node
    ”’

    ”’ The level in the tree = 0 – 7
    ”’ The number of significant color bits in the image
    ”’ The tree to which this node belongs
    Public Sub New(ByVal level As Integer, ByVal colorBits As Integer, ByVal octree As Octree)
    ‘ Construct the new node
    _leaf = (level = colorBits)

    _red = _green = _blue = 0
    _pixelCount = 0

    ‘ If a leaf, increment the leaf count
    If _leaf Then
    octree.Leaves += 1
    _nextReducible = Nothing
    _children = Nothing
    Else
    ‘ Otherwise add this to the reducible nodes
    _nextReducible = octree.ReducibleNodes(level)
    octree.ReducibleNodes(level) = Me
    _children = New OctreeNode(7) {}
    End If
    End Sub

    ”’

    ”’ Add a color into the tree
    ”’

    ”’ The color
    ”’ The number of significant color bits
    ”’ The level in the tree
    ”’ The tree to which this node belongs
    Public Sub AddColor(ByVal pixel As Color32, ByVal colorBits As Integer, ByVal level As Integer, ByVal octree As Octree)
    ‘ Update the color information if this is a leaf
    If _leaf Then
    Increment(pixel)
    ‘ Setup the previous node
    octree.TrackPrevious(Me)
    Else
    ‘ Go to the next level down in the tree
    Dim shift As Integer = 7 – level
    Dim index As Integer = ((pixel.Red And mask(level)) >> (shift – 2)) Or ((pixel.Green And mask(level)) >> (shift – 1)) Or ((pixel.Blue And mask(level)) >> (shift))

    Dim child As OctreeNode = _children(index)

    If child Is Nothing Then
    ‘ Create a new child node & store in the array
    child = New OctreeNode(level + 1, colorBits, octree)
    _children(index) = child
    End If

    ‘ Add the color to the child node
    child.AddColor(pixel, colorBits, level + 1, octree)
    End If

    End Sub

    ”’

    ”’ Get/Set the next reducible node
    ”’

    Public Property NextReducible() As OctreeNode
    Get
    Return _nextReducible
    End Get
    Set(ByVal value As OctreeNode)
    _nextReducible = value
    End Set
    End Property

    ”’

    ”’ Return the child nodes
    ”’

    Public ReadOnly Property Children() As OctreeNode()
    Get
    Return _children
    End Get
    End Property

    ”’

    ”’ Reduce this node by removing all of its children
    ”’

    ”’ The number of leaves removed
    Public Function Reduce() As Integer
    _red = _green = _blue = 0
    Dim children As Integer = 0
    For index As Integer = 0 To 7

    ‘ Loop through all children and add their information to this node
    If _children(index) IsNot Nothing Then
    _red += _children(index)._red
    _green += _children(index)._green
    _blue += _children(index)._blue
    _pixelCount += _children(index)._pixelCount
    children += 1
    _children(index) = Nothing
    End If
    Next

    ‘ Now change this to a leaf node
    _leaf = True

    ‘ Return the number of nodes to decrement the leaf count by
    Return (children – 1)
    End Function

    ”’

    ”’ Traverse the tree, building up the color palette
    ”’

    ”’ The palette
    ”’ The current palette index
    Public Sub ConstructPalette(ByVal palette As ArrayList, ByRef paletteIndex As Integer)
    If _leaf Then
    ‘ Consume the next palette index
    _paletteIndex = System.Math.Max(System.Threading.Interlocked.Increment(paletteIndex), paletteIndex – 1)

    ‘ And set the color of the palette entry
    palette.Add(Color.FromArgb(_red / _pixelCount, _green / _pixelCount, _blue / _pixelCount))
    Else
    For index As Integer = 0 To 7
    ‘ Loop through children looking for leaves
    If _children(index) IsNot Nothing Then
    _children(index).ConstructPalette(palette, paletteIndex)
    End If
    Next
    End If
    End Sub

    ”’

    ”’ Return the palette index for the passed color
    ”’

    Public Function GetPaletteIndex(ByVal pixel As Color32, ByVal level As Integer) As Integer
    Dim paletteIndex As Integer = _paletteIndex

    If Not _leaf Then
    Dim shift As Integer = 7 – level
    Dim index As Integer = ((pixel.Red And mask(level)) >> (shift – 2)) Or ((pixel.Green And mask(level)) >> (shift – 1)) Or ((pixel.Blue And mask(level)) >> (shift))

    If _children(index) IsNot Nothing Then
    paletteIndex = _children(index).GetPaletteIndex(pixel, level + 1)
    Else
    Throw New Exception(“Didn’t expect this!”)
    End If
    End If

    Return paletteIndex
    End Function

    ”’

    ”’ Increment the pixel count and add to the color information
    ”’

    Public Sub Increment(ByVal pixel As Color32)
    _pixelCount += 1
    _red += pixel.Red
    _green += pixel.Green
    _blue += pixel.Blue
    End Sub

    ”’

    ”’ Flag indicating that this is a leaf node
    ”’

    Private _leaf As Boolean

    ”’

    ”’ Number of pixels in this node
    ”’

    Private _pixelCount As Integer

    ”’

    ”’ Red component
    ”’

    Private _red As Integer

    ”’

    ”’ Green Component
    ”’

    Private _green As Integer

    ”’

    ”’ Blue component
    ”’

    Private _blue As Integer

    ”’

    ”’ Pointers to any child nodes
    ”’

    Private _children As OctreeNode()

    ”’

    ”’ Pointer to next reducible node
    ”’

    Private _nextReducible As OctreeNode

    ”’

    ”’ The index of this node in the palette
    ”’

    Private _paletteIndex As Integer

    End Class
    End Class
    End Class

  • marcio

    Any chance this code could be fixed to properly deal with transparencies? I am converting an input GIF (which uses as transparency a color which I don’t know in advance) and when I save the optimized image, it no longer has the transparency. Any chance this bug could be nailed and a patch provided in teh form of a patch file or an updatez src zip? I tried commenting out the optimization code as mentioned above but that did not fix it – it produced an image that was all black. Thanks!!

  • Tucker

    I’d like to add to the stream of thanks – I stumbled my way in here after trying unsuccessfully to write a custom font onto images. I was seeing lots of compression artifacts, and unless I cranked my JPG quality up high to produce very large images, they wouldn’t go away. After trying to write gifs on my own, I found an asp.net forums post linking your original post and then this one, and now I’m spitting out crystal-clear perfect gifs at a mere fraction the size of the fugly jpgs! Thanks again.

  • Jake

    Awesome code, but I think I’m mising something. This code was refactored to be safe, but I still can’t get it to run under medium trust in ASP.NET 2. When the constructor is called for the OctreeQuantizer, I get a System.Security.SecurityException, “The application attempted to perform an operation not allowed by the security policy.” Any ideas?

  • Ben White

    I noticed some black artifacts when Quantizing a transparent image. I was able to track down the issue to the optimization code in the SecondPass method.

    if (Marshal.ReadByte(pPreviousPixel) != Marshal.ReadByte(pSourcePixel))

    After commenting out this optimization, the class worked perfectly…

  • http://www.nokiatema.net nokia tema

    Downloads are not working

  • http://www.nokiatema.net nokia

    thanks for you

  • http://www.picsnwallpapers.com poonam

    Nice trick..
    but i am not sure how and where to use it …
    i’ll definitely find out some way to use it and make my website more attractive..
    Thanks a lot for this trick..

  • Stefan GIbney

    Hi Brendan

    Great work, except both links seem to direct you to the binary.

    Thanks

    Stefan

  • Rosbicn

    I met the same problem where Tim wrote above. Black horizontal lines appears on some result images. And I read all comment here and found Olav and Logon’s note. Their solution was working!!! on line 181, the raw code is “if (Marshal.ReadByte(pPreviousPixel) != Marshal.ReadByte(pSourcePixel))”. It is a small bug. Change it to “if (Marshal.ReadInt32(pPreviousPixel) != Marshal.ReadInt32(pSourcePixel))”. Because the bitwidth of a pixel is 4 as int32, not 1 as byte. Thanks Olav and Tim.

  • Nathan

    Wow, thank you so much for your work. This problem was killing me (literally). Unfortunately this was the last stop after browsing every site on the web related to gif and gdi.

    Thanks.

  • Logan R

    I was having a similar problem to Tim, also confirming the unsafe MS version worked properly. I was just about to dig into the problem when I noticed Olav’s note above about Marshall.ReadInt32. Thanks Olav!

  • http://www.timdown.co.uk Tim Down

    Brendan,

    I have discovered a problem using your OctreeQuantizer that I fixed by replacing it with the unsafe one from the MSDN article from which you copied it. I haven’t got time to try and figure out exactly what triggers the problem, I’m afraid. What I found was that on certain images I’d generated I got rogue black horizontal lines appearing on my quantized image. If you wish I can send you copies of the original image and the version of the image produced by your quantizer.

  • Daniel

    Hi,

    Downloads are not working !!!

    Thanks,
    Daniel

  • http://olav.dk Olav Junker Kjær

    Thank you for the code, it’s very valuable!
    There seem to be a small bug in the source, in the SecondPass method. In the optimization you compare Marshal.ReadByte for previous and current pixel. However this will only compare the first color channel. You should use Marshal.ReadInt32.

  • Brendan Tompkins

    Oh. yes… Ahem.

    I’d like to thank my parents, God, and Greg Young for pointing out a very stupid arithmetic error I was having. Greg is definitely my go-to guy for all things close to the metal.

  • Greg

    Heh no credit? :)

  • Brendan Tompkins

    Ooops, the links were reversed. Fixed now. I’m getting sloppy in my old age.

  • Just Don’t Know

    I think the link to the source code is incorrect – it points to the same url as the binary link…

  • Brendan Tompkins

    Lionel,

    I could probably get rid of the struct altogether in that case. Perhaps I’ll look at that sometime. Thanks!

  • Lionel

    You can also use Marshal.ReadInt32 and Marshal.WriteInt32 if you want something a bit more lightweight than Marshal.PtrToStructure.

    protected void FirstPass(BitmapData sourceData, int width, int height)
    {
    for (int row = 0; row < height; row++)
    {
    for (int col = 0; col < width; col++)
    {
    // Now I have the pixel, call the FirstPassQuantize function…
    int offset = sourceData.Stride + (_pixelSize * col);
    Color color = Color.FromArgb(Marshal.ReadInt32(sourceData.Scan0, offset));
    InitialQuantizePixel(color);
    Marshal.WriteInt32(sourceData.Scan0, offset);
    }
    }
    }

  • Brendan Tompkins

    Sean,

    Good catch, that was a copy-paste error there. You’re absolutely right, x64 IntPtrs are 64 Bit

  • http://geekswithblogs.net/scarpenter Sean Carpenter

    I’m not sure (and I don’t have an x64 machine to try it on here) but will the cast of an IntPtr to an Int32 cause a problem on a 64-bit machine? I thought the size of an IntPtr was dependent on the platform.