Click here to Skip to main content
Click here to Skip to main content
Articles » Multimedia » GDI » General » Downloads
 
Add your own
alternative version

QuickFill: An efficient flood fill algorithm.

, 12 Mar 2004
Design and implimentation of efficient flood fill algorithms.
quickfilldemo_demo.zip
quickfilldemo_src.zip
CDibData
Doxygen.dat
CQuantize
QuickFill
test.bmp
QuickFillDemo
Debug
QuickFillDemo.clw
QuickFillDemo.dsp
QuickFillDemo.dsw
Release
res
bitmap1.bmp
bmp00001.bmp
bmp00002.bmp
bmp00003.bmp
bmp00004.bmp
checker.bmp
checker2.bmp
circle.bmp
clubs.bmp
cross.bmp
dchecker.bmp
diamon.bmp
dimonds.bmp
hart.bmp
it.bmp
ldiag.bmp
ne.bmp
nw.bmp
QuickFillDemo.ico
QuickFillDemoDoc.ico
rdiag.bmp
schecker.bmp
scircle.bmp
se.bmp
spades.bmp
square.bmp
sw.bmp
x.bmp
xsquare.bmp
// Quantize.cpp
//
// CQuantizer Class : MSJ : Wicked Code 1997 : By Jeff Prosise
//
// Modified By John R. Shaw
// Minor format change (my style) for easier reading
// and changed most (++) increments from post to pre
// since post is a bad habit [ok in C(?) but can lead to
// unexpected over-head in C++]
//
#include "stdafx.h"
#include "Quantize.h"

CQuantizer::CQuantizer(UINT nMaxColors, UINT nColorBits)
{
    ASSERT(nColorBits <= 8);

    m_pTree = NULL;
    m_nLeafCount = 0;
    for( UINT i = 0; i <= nColorBits; ++i )
        m_pReducibleNodes[i] = NULL;
    m_nMaxColors = nMaxColors;
    m_nColorBits = nColorBits;
}

CQuantizer::~CQuantizer ()
{
    if( m_pTree != NULL )
        DeleteTree(&m_pTree);
}

BOOL CQuantizer::ProcessImage (HANDLE hImage)
{
    DWORD rmask, gmask, bmask;
    int rright, gright, bright;
    int rleft, gleft, bleft;
    BYTE* pbBits;
    WORD* pwBits;
    DWORD* pdwBits;
    BYTE r, g, b;
    WORD wColor;
    DWORD dwColor;
    int i, j;
    HDC hdc;
    BYTE* pBuffer;
    BITMAPINFO bmi;

    DIBSECTION ds;
    ::GetObject(hImage, sizeof (ds), &ds);
    int nPad = ds.dsBm.bmWidthBytes -
		( ( (ds.dsBmih.biWidth * ds.dsBmih.biBitCount) + 7 ) / 8 );

    switch( ds.dsBmih.biBitCount )
	{

    case 1: // 1-bit DIB
    case 4: // 4-bit DIB
    case 8: // 8-bit DIB
        //
        // The strategy here is to use ::GetDIBits to convert the
        // image into a 24-bit DIB one scan line at a time. A pleasant
        // side effect of using ::GetDIBits in this manner is that RLE-
        // encoded 4-bit and 8-bit DIBs will be uncompressed.
        //
        hdc = ::GetDC(NULL);
        pBuffer = new BYTE[ds.dsBmih.biWidth * 3];

        ::ZeroMemory (&bmi, sizeof (bmi));
        bmi.bmiHeader.biSize = sizeof (BITMAPINFOHEADER);
        bmi.bmiHeader.biWidth = ds.dsBmih.biWidth;
        bmi.bmiHeader.biHeight = ds.dsBmih.biHeight;
        bmi.bmiHeader.biPlanes = 1;
        bmi.bmiHeader.biBitCount = 24;
        bmi.bmiHeader.biCompression = BI_RGB;

        for( i=0; i<ds.dsBmih.biHeight; ++i )
		{
            ::GetDIBits (hdc, (HBITMAP) hImage, i, 1, pBuffer, &bmi,
                DIB_RGB_COLORS);
            pbBits = pBuffer;
            for( j=0; j<ds.dsBmih.biWidth; ++j )
			{
                b = *pbBits++;
                g = *pbBits++;
                r = *pbBits++;
                AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
                    m_pReducibleNodes);
                while( m_nLeafCount > m_nMaxColors )
                    ReduceTree (m_nColorBits, &m_nLeafCount,
                        m_pReducibleNodes);
            }
        }

        delete pBuffer;
        ::ReleaseDC(NULL, hdc);
        break;

    case 16: // 16-bit DIB
        if( ds.dsBmih.biCompression == BI_BITFIELDS )
		{
            rmask = ds.dsBitfields[0];
            gmask = ds.dsBitfields[1];
            bmask = ds.dsBitfields[2];
        }
        else
		{
            rmask = 0x7C00;
            gmask = 0x03E0;
            bmask = 0x001F;
        }

        rright = GetRightShiftCount (rmask);
        gright = GetRightShiftCount (gmask);
        bright = GetRightShiftCount (bmask);

        rleft = GetLeftShiftCount (rmask);
        gleft = GetLeftShiftCount (gmask);
        bleft = GetLeftShiftCount (bmask);

        pwBits = (WORD*) ds.dsBm.bmBits;
        for( i=0; i<ds.dsBmih.biHeight; ++i )
		{
            for( j=0; j<ds.dsBmih.biWidth; ++j )
			{
                wColor = *pwBits++;
                b = (BYTE) (((wColor & (WORD) bmask) >> bright) << bleft);
                g = (BYTE) (((wColor & (WORD) gmask) >> gright) << gleft);
                r = (BYTE) (((wColor & (WORD) rmask) >> rright) << rleft);
                AddColor(&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
                    m_pReducibleNodes);
                while( m_nLeafCount > m_nMaxColors )
                    ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
            }
            pwBits = (WORD*)( ((BYTE*)pwBits) + nPad );
        }
        break;

    case 24: // 24-bit DIB
        pbBits = (BYTE*)ds.dsBm.bmBits;
        for( i=0; i<ds.dsBmih.biHeight; ++i )
		{
            for( j=0; j<ds.dsBmih.biWidth; ++j )
			{
                b = *pbBits++;
                g = *pbBits++;
                r = *pbBits++;
                AddColor (&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
                    m_pReducibleNodes);
                while( m_nLeafCount > m_nMaxColors )
                    ReduceTree (m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
            }
            pbBits += nPad;
        }
        break;

    case 32: // 32-bit DIB
        if( ds.dsBmih.biCompression == BI_BITFIELDS )
		{
            rmask = ds.dsBitfields[0];
            gmask = ds.dsBitfields[1];
            bmask = ds.dsBitfields[2];
        }
        else
		{
            rmask = 0x00FF0000;
            gmask = 0x0000FF00;
            bmask = 0x000000FF;
        }

        rright = GetRightShiftCount(rmask);
        gright = GetRightShiftCount(gmask);
        bright = GetRightShiftCount(bmask);

        pdwBits = (DWORD*) ds.dsBm.bmBits;
        for( i=0; i<ds.dsBmih.biHeight; ++i )
		{
            for( j=0; j<ds.dsBmih.biWidth; ++j )
			{
                dwColor = *pdwBits++;
                b = (BYTE)((dwColor & bmask) >> bright);
                g = (BYTE)((dwColor & gmask) >> gright);
                r = (BYTE)((dwColor & rmask) >> rright);
                AddColor(&m_pTree, r, g, b, m_nColorBits, 0, &m_nLeafCount,
                    m_pReducibleNodes);
                while( m_nLeafCount > m_nMaxColors )
                    ReduceTree(m_nColorBits, &m_nLeafCount, m_pReducibleNodes);
            }
            pdwBits = (DWORD*)(((BYTE*) pdwBits) + nPad);
        }
        break;

    default: // Unrecognized color format
        return FALSE;
    }
    return TRUE;
}

int CQuantizer::GetLeftShiftCount(DWORD dwVal)
{
    int nCount = 0;
    for( int i=0; i<sizeof(DWORD) * 8; ++i )
	{
        if( dwVal & 1 )
            ++nCount;
        dwVal >>= 1;
    }
    return( 8 - nCount );
}

int CQuantizer::GetRightShiftCount(DWORD dwVal)
{
    for( int i=0; i<sizeof(DWORD) * 8; ++i )
	{
        if( dwVal & 1 )
            return i;
        dwVal >>= 1;
    }
    return -1;
}

void CQuantizer::AddColor(PNODE* ppNode, BYTE r, BYTE g, BYTE b,
    UINT nColorBits, UINT nLevel, UINT* pLeafCount, PNODE* pReducibleNodes)
{
    static BYTE mask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };

    //
    // If the node doesn't exist, create it.
    //
    if( *ppNode == NULL )
        *ppNode = CreateNode (nLevel, nColorBits, pLeafCount,
            pReducibleNodes);

    //
    // Update color information if it's a leaf node.
    //
    if( (*ppNode)->bIsLeaf )
	{
        (*ppNode)->nPixelCount++;
        (*ppNode)->nRedSum   += r;
        (*ppNode)->nGreenSum += g;
        (*ppNode)->nBlueSum  += b;
    }

    //
    // Recurse a level deeper if the node is not a leaf.
    //
    else
	{
        int shift = 7 - nLevel;
        int nIndex = ( ( ( r & mask[nLevel] ) >> shift ) << 2 ) |
            ( ( ( g & mask[nLevel] ) >> shift ) << 1 ) |
            ( ( b & mask[nLevel] ) >> shift );
        AddColor(&( (*ppNode)->pChild[nIndex] ), r, g, b, nColorBits,
            nLevel + 1, pLeafCount, pReducibleNodes);
    }
}

PNODE CQuantizer::CreateNode(UINT nLevel, UINT nColorBits, UINT* pLeafCount,
    PNODE* pReducibleNodes)
{
    PNODE pNode;

    if( ( pNode = (PNODE)HeapAlloc( GetProcessHeap (), HEAP_ZERO_MEMORY,
        sizeof (NODE) ) ) == NULL )
	{
        return NULL;
	}

    pNode->bIsLeaf = (nLevel == nColorBits) ? TRUE : FALSE;
    if( pNode->bIsLeaf )
        ++(*pLeafCount);
    else
	{
        pNode->pNext = pReducibleNodes[nLevel];
        pReducibleNodes[nLevel] = pNode;
    }
    return pNode;
}

void CQuantizer::ReduceTree (UINT nColorBits, UINT* pLeafCount,
    PNODE* pReducibleNodes)
{
    //
    // Find the deepest level containing at least one reducible node.
    //
    for( int i=nColorBits - 1; (i>0) && (pReducibleNodes[i] == NULL); --i )
	{;}

    //
    // Reduce the node most recently added to the list at level i.
    //
    PNODE pNode = pReducibleNodes[i];
    pReducibleNodes[i] = pNode->pNext;

    UINT nRedSum   = 0;
    UINT nGreenSum = 0;
    UINT nBlueSum  = 0;
    UINT nChildren = 0;

    for( i=0; i<8; ++i )
	{
        if( pNode->pChild[i] != NULL )
		{
            nRedSum   += pNode->pChild[i]->nRedSum;
            nGreenSum += pNode->pChild[i]->nGreenSum;
            nBlueSum  += pNode->pChild[i]->nBlueSum;
            pNode->nPixelCount += pNode->pChild[i]->nPixelCount;
            HeapFree( GetProcessHeap(), 0, pNode->pChild[i] );
            pNode->pChild[i] = NULL;
            ++nChildren;
        }
    }

    pNode->bIsLeaf   = TRUE;
    pNode->nRedSum   = nRedSum;
    pNode->nGreenSum = nGreenSum;
    pNode->nBlueSum  = nBlueSum;
    *pLeafCount -= (nChildren - 1);
}

void CQuantizer::DeleteTree(PNODE* ppNode)
{
    for( int i=0; i<8; ++i )
	{
        if( (*ppNode)->pChild[i] != NULL )
            DeleteTree( &((*ppNode)->pChild[i]) );
    }
    HeapFree( GetProcessHeap(), 0, *ppNode );
    *ppNode = NULL;
}

void CQuantizer::GetPaletteColors(PNODE pTree, RGBQUAD* prgb, UINT* pIndex)
{
    if (pTree->bIsLeaf)
	{
        prgb[*pIndex].rgbRed =
            (BYTE)( (pTree->nRedSum)   / (pTree->nPixelCount) );
        prgb[*pIndex].rgbGreen =
            (BYTE)( (pTree->nGreenSum) / (pTree->nPixelCount) );
        prgb[*pIndex].rgbBlue =
            (BYTE)( (pTree->nBlueSum)  / (pTree->nPixelCount) );
        prgb[*pIndex].rgbReserved = 0;
        ++(*pIndex);
    }
    else
	{
        for( int i=0; i<8; ++i )
		{
            if( pTree->pChild[i] != NULL )
                GetPaletteColors(pTree->pChild[i], prgb, pIndex);
        }
    }
}

UINT CQuantizer::GetColorCount()
{
    return m_nLeafCount;
}

void CQuantizer::GetColorTable(RGBQUAD* prgb)
{
    UINT nIndex = 0;
    GetPaletteColors(m_pTree, prgb, &nIndex);
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

John R. Shaw
Software Developer
United States United States
I am a senior software engineer who has been designing and developing software for many years, mostly in C/C++. You might say that I think in code; which is why I am passionate about my first rule of coding: “First do no harm”. So if I get carried away in my explanations, please realize that it is just part of my personality. I enjoy learning new things and, when I have the time, passing that knowledge onto others.

| Advertise | Privacy | Mobile
Web02 | 2.8.140814.1 | Last Updated 13 Mar 2004
Article Copyright 2004 by John R. Shaw
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid