monochromebitmap.cpp

segmentation sample good luck

// MonochromeBitmap.cpp: implementation of the CMonochromeBitmap class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Segment.h"
#include "MonochromeBitmap.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif


//-----------------------------------------------------------------
//
// CMonochromeBitmap::CMonochromeBitmap - Constructor
//
//-----------------------------------------------------------------

CMonochromeBitmap::CMonochromeBitmap()
{
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::~CMonochromeBitmap() - Destructor
//
//-----------------------------------------------------------------

CMonochromeBitmap::~CMonochromeBitmap()
{
	DeallocateMemoryForBitmap();
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::DeallocateMemoryForBitmap - This erases any
//							stored resources including the quad tree,
//							the blobs and the lines.
//
//-----------------------------------------------------------------

void CMonochromeBitmap::DeallocateMemoryForBitmap()
{
	m_quadTree.RemoveAll();

	// Clear all vectors and release all blobs.

	for (int i = 0; i < m_pBlob.size(); i++) {
		delete m_pBlob[i];
	}
	m_pBlob.resize(0);
	
	for (i = 0; i < m_clvpvAllocatedVector.size(); i++) {
		delete m_clvpvAllocatedVector[i];
	}
	m_clvpvAllocatedVector.resize(0);
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::AllocateLineBlock - This allocates another
//								block of lines and saves the pointer
//								to the block for easy deletion later.
//
// clviStart - iterator marking start of the allocated block of lines.
//             Get lines by dereferencing this pointer.
// clviEnd - iterator marking end of the allocated block of lines.
//-----------------------------------------------------------------

void CMonochromeBitmap::AllocateLineBlock(CLineVectorIterator &clviStart,CLineVectorIterator &clviEnd)
{
	// Add another vector of lines to the end of the meta-vector.

	m_clvpvAllocatedVector.push_back(new CLineVector);
	CLineVector &clvLast = **(m_clvpvAllocatedVector.end() - 1);

	// Make it a fixed size and retrieve its boundaries.

	clvLast.resize(eMaxLinesPerVector);
	clviStart = clvLast.begin();
	clviEnd = clvLast.end();
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::BuildBlobList - Segment the bitmap into blobs.
//
//-----------------------------------------------------------------

void CMonochromeBitmap::BuildBlobList()
{
	CLineVectorIterator clviNew,clviEnd;
	AllocateLineBlock(clviNew,clviEnd);
	m_pBlob.reserve(eBlobsPerBlock);

	// Create two vectors of pointers to lines to hold the new line list
	// and the old line list. We initialize them to hold Width()/2 members.
	// This is the maximum possible number of lines.

	CLinePointerVector clpvRaster[2];
	clpvRaster[0].reserve(Width()/2);
	clpvRaster[1].reserve(Width()/2);

	int nOldLineIndex = 0;
	int nNewLineIndex = 1;

	// At the start, the old line list has no members.
	CLinePointerVectorIterator clpviOldEnd = clpvRaster[nOldLineIndex].begin();

	for (int nY = 0; nY < Height(); nY++) {

		CLinePointerVector &clpvOld = clpvRaster[nOldLineIndex];
		CLinePointerVector &clpvNew = clpvRaster[nNewLineIndex];
		nOldLineIndex = nOldLineIndex ^ 1;
		nNewLineIndex = nNewLineIndex ^ 1;

		CLinePointerVectorIterator clpviOld = clpvOld.begin();
		CLine *pLineOld;
		if (clpviOld == clpviOldEnd) {
			pLineOld = NULL;
		} else {
			pLineOld = *clpviOld++;
		}

		CLinePointerVectorIterator clpviNew = clpvNew.begin();

		// Get the raster to process and set up for the first byte
		const BYTE *pRaster = GetRaster(nY);
		BYTE bBit = 0x80;
		BYTE bByte = *pRaster++;

		//  Set up the X extents.
		int nX = 0;
		const int nXEnd = Width();


		while(nX < nXEnd) {
			CBlob *pBlobOld;
			// Search for the start of a line.

			while((bByte & bBit) == 0) {
				if (++nX == nXEnd) goto linedone;
				bBit = bBit >> 1;
				if (bBit == 0) {
					bBit = 0x80;
					bByte = *pRaster++;
				}
			}

			// Start a line.

			if (clviNew == clviEnd) {
				// need more memory for lines.

				AllocateLineBlock(clviNew,clviEnd);
			}

			CLine &lineNew = *clviNew++;
			lineNew.m_nXStart = nX;
			lineNew.m_pNextLineSameBlob = 0;
			lineNew.m_nY = nY;
			
			// Put it on the new list.

			*clpviNew++ = &lineNew;

			// Find the extent of the line.

			do {
				if (nX == nXEnd) break;
				bBit = bBit >> 1;
				if (bBit == 0) {
					bBit = 0x80;
					bByte = *pRaster++;
				}
				nX++;
			} while (bBit & bByte);

			lineNew.m_nXEnd = nX - 1;

			// Now finish all old lines wholly before our new line

			if (pLineOld) {
				while (pLineOld->m_nXEnd < lineNew.m_nXStart) {

					pBlobOld = pLineOld->m_pBlob;
					if (--(pBlobOld->m_nOpenLines) == 0) {
						AddBlob(pBlobOld);
					}
					if (clpviOld == clpviOldEnd) {
						pLineOld = NULL;
						break;
					} else {
						pLineOld = *clpviOld++;
					}
				}
			}

			// Do the first line that overlaps our new line

			if (pLineOld && pLineOld->m_nXStart <= lineNew.m_nXEnd) {
				pBlobOld = pLineOld->m_pBlob;
				lineNew.m_pBlob = pBlobOld;
				*(pBlobOld->m_ppLastLine) = &lineNew;
				pBlobOld->m_ppLastLine = &(lineNew.m_pNextLineSameBlob);

				// See if the new line ends the old line or vice-versa.

				if (pLineOld->m_nXEnd > lineNew.m_nXEnd) {
					// the old line extends past the new line.
					// the new line gives the old line's blob another open line.

					pBlobOld->m_nOpenLines++;
					continue;
				} else {
					// we close the old line and extend the blob at the
					// same time. We continue to close old lines.

					if (clpviOld == clpviOldEnd) {
						pLineOld = NULL;
					} else {
						pLineOld = *clpviOld++;
						while(pLineOld->m_nXEnd <= lineNew.m_nXEnd) {
							// End this line too. We have two cases:
							CBlob *pBlobOther;
							if ((pBlobOther = pLineOld->m_pBlob) == pBlobOld) {
								// the old line is part of the new line's blob.
								// This is just a loop.

								pBlobOld->m_nLoops++;
								pBlobOld->m_nOpenLines--;
							} else {
								// This is the merge case

								pBlobOld->Merge(pBlobOther);
								delete pBlobOther;
								pBlobOld->m_nOpenLines--;
							}
							if (clpviOld == clpviOldEnd) {
								pLineOld = NULL;
								break;
							} else {
								pLineOld = *clpviOld++;
							}
						}
						if (pLineOld && pLineOld->m_nXStart <= lineNew.m_nXEnd) {
							// This last old line overlaps and ends the new line.

							CBlob *pBlobOther = pLineOld->m_pBlob;
							if (pBlobOther == pBlobOld) {
								pBlobOld->m_nLoops++;
							} else {
								pBlobOld->Merge(pBlobOther);
								delete pBlobOther;
							}
						}
					}
				}
			} else {
				// This is the case where no line overlaps the new line.
				// Start a blob with this line.

				CBlob *pBlobNew = lineNew.m_pBlob = new CBlob;
				pBlobNew->m_nOpenLines = 1;
				pBlobNew->m_pFirstLine = &lineNew;
				pBlobNew->m_ppLastLine = &(lineNew.m_pNextLineSameBlob);
				pBlobNew->m_nLoops = 0;
			}
		}
linedone:
		if (pLineOld) {
			while (TRUE) {
				// Finish all old lines.
				CBlob *pBlobOld = pLineOld->m_pBlob;
				if (--(pBlobOld->m_nOpenLines) == 0) {
					AddBlob(pBlobOld);
				}
				if (clpviOld == clpviOldEnd) break;
				pLineOld = *clpviOld++;
			}
		}

		// Finally, record the end of the new list as the
		// end of the old list to be.

		clpviOldEnd = clpviNew;
	}

	// At the end, we've got one last raster of lines to finish.

	CLinePointerVector &clpvLast = clpvRaster[nOldLineIndex];
	for (CLinePointerVectorIterator clpvi = clpvLast.begin();
	clpvi != clpviOldEnd;) {
		// Finish all old lines.
		CBlob *pBlobOld = (*clpvi++)->m_pBlob;
		if (--(pBlobOld->m_nOpenLines) == 0) {
			AddBlob(pBlobOld);
		}
	}

	// and finally, segmentation is complete
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::GetBrightnessHistogram - The base class returns
//							a null histogram. Derived classes will return
//							histograms in which each element is a count
//							of the number of pixels with that brightness.
//
// a: The elements of this histogram are ranked from lowest brightness
//    to highest. The value at each index is the relative number of pixels
//    with that brightness.
// aBrightness: this maps the color index onto the histogram - i.e.
//              aBrightness[nIndex] gives the brightness ranking of the
//				indexed color, nIndex. a[aBrightness[nIndex]] tells you
//				how many pixels have that brightness.
//-----------------------------------------------------------------

void CMonochromeBitmap::GetBrightnessHistogram(vector<int> &a,vector<int> &aBrightness)
{
	a.resize(0);
	aBrightness.resize(0);
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::AddBlob - Add the incoming blob to the list
//								of finished blobs. The monochrome
//								bitmap is responsible for deleting
//								elements of this list.
//
// pBlob - add this blob to the list.
//
//-----------------------------------------------------------------

void CMonochromeBitmap::AddBlob(CBlob *pBlob)
{
	*(pBlob->m_ppLastLine) = NULL;
	if (m_pBlob.size() == m_pBlob.capacity()) {
		m_pBlob.reserve(m_pBlob.size() + eBlobsPerBlock);
	}
	m_pBlob.push_back(pBlob);
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::GetBlobCount - Return the number of finished blobs
//
//-----------------------------------------------------------------

int CMonochromeBitmap::GetBlobCount() const
{
	return m_pBlob.size();
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::GetBlob - Return the indexed blob
//
// nIndex - zero based index of blob to retrieve.
//
//-----------------------------------------------------------------

CBlob *CMonochromeBitmap::GetBlob(int nIndex)
{
	return m_pBlob[nIndex];
}

const CBlob *CMonochromeBitmap::GetBlob(int nIndex) const
{
	return m_pBlob[nIndex];
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::ClearBlobList - Call this to insure that you've
//									  got an empty blob list before
//									  segmentation
//-----------------------------------------------------------------

void CMonochromeBitmap::ClearBlobList()
{
	DeallocateMemoryForBitmap();
}

//-----------------------------------------------------------------
//
// CMonochromeBitmap::GetQuadTree - This builds a quad tree out of
//						the blobs in the list. A quad tree is a
//						sort of binomial list that extends in the
//						X and Y directions. You can search a quad
//						tree in log(N) time. They're really useful
//						for ordering objects in images.
//
//-----------------------------------------------------------------

CQuadTree<CBlob> &CMonochromeBitmap::GetQuadTree()
{
	if (m_quadTree.IsEmpty()) {
		for (CBlobPtrVector::iterator i = m_pBlob.begin(); i != m_pBlob.end();i++) {
			m_quadTree.Insert(*i);
		}
	}
	return m_quadTree;
}