blob.cpp

segmentation sample good luck

// Blob.cpp: implementation of the CBlob class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Segment.h"
#include "Blob.h"
#include "Line.h"
#include <vector>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//-----------------------------------------------------------------
//
// CBlob::Merge - UGH! The merge is an expensive operation that entails
//				  combining the lines from two blobs.
//
// pBlobOther - This is the blob which we'll later destroy. Take its lines
//
//-----------------------------------------------------------------

void CBlob::Merge(CBlob *pBlobOther)
{
	// Combine the two blobs' counts.

	m_nOpenLines += pBlobOther->m_nOpenLines;
	m_nLoops += pBlobOther->m_nLoops;

	// We maintain two lists of blobs and interweave.

	CLine *pLine = m_pFirstLine;
	CLine *pLineOther = pBlobOther->m_pFirstLine;

	ASSERT(pLine);
	ASSERT(pLineOther);

	// Top off the end of the line list prematurely.

	*m_ppLastLine = NULL;
	*(pBlobOther->m_ppLastLine) = NULL;

	CLine **ppInsertionPoint = &m_pFirstLine;
	
	while(TRUE) {
		// This loop attaches the next line to the blob.

		if (pLine->m_nY < pLineOther->m_nY) {
			*ppInsertionPoint = pLine;
			ppInsertionPoint = &(pLine->m_pNextLineSameBlob);
			if ((pLine = pLine->m_pNextLineSameBlob)  == NULL) {
				*ppInsertionPoint = pLineOther;

				// We have to run through the "other" list and
				// change each line's blob pointer.

				while(pLineOther = pLineOther->m_pNextLineSameBlob) {
					pLineOther->m_pBlob = this;
				}

				m_ppLastLine = pBlobOther->m_ppLastLine;
				return;
			}
		} else if (pLine->m_nY > pLineOther->m_nY) {
			pLineOther->m_pBlob = this;
			*ppInsertionPoint = pLineOther;
			ppInsertionPoint = &(pLineOther->m_pNextLineSameBlob);
			if ((pLineOther = pLineOther->m_pNextLineSameBlob) == NULL) {
				*ppInsertionPoint = pLine;
				return;
			}
		} else if (pLine->m_nXStart < pLineOther->m_nXStart) {
			*ppInsertionPoint = pLine;
			ppInsertionPoint = &(pLine->m_pNextLineSameBlob);
			if ((pLine = pLine->m_pNextLineSameBlob)  == NULL) {
				*ppInsertionPoint = pLineOther;

				// We have to run through the "other" list and
				// change each line's blob pointer.

				while(pLineOther = pLineOther->m_pNextLineSameBlob) {
					pLineOther->m_pBlob = this;
				}

				m_ppLastLine = pBlobOther->m_ppLastLine;
				return;
			}
		} else {
			pLineOther->m_pBlob = this;
			*ppInsertionPoint = pLineOther;
			ppInsertionPoint = &(pLineOther->m_pNextLineSameBlob);
			if ((pLineOther = pLineOther->m_pNextLineSameBlob) == NULL) {
				*ppInsertionPoint = pLine;
				return;
			}
		}
	}
}


//-----------------------------------------------------------------
//
// CBlob::CBlob() - Constructor: set the rectangle to empty to signal
//				    that we haven't computed it yet
//
//-----------------------------------------------------------------

CBlob::CBlob()
{
	m_cr.SetRectEmpty();
}

//-----------------------------------------------------------------
//
// CBlob::GetRect - compute the bounding rectangle for the blob
//
//	cr - return the rectangle here.
//-----------------------------------------------------------------

void CBlob::GetRect(CRect & cr)
{
	if (m_cr.IsRectEmpty()) {
		// Run through all of the lines to get the min and max X.
		m_cr.left = INT_MAX;
		m_cr.right = INT_MIN;

		CLine *pLine = m_pFirstLine;
		m_cr.top = pLine->m_nY;
		do {
			if (pLine->m_nXStart < m_cr.left) {
				m_cr.left = pLine->m_nXStart;
			}
			if (pLine->m_nXEnd >= m_cr.right) {
				m_cr.right = pLine->m_nXEnd + 1;
			}
			m_cr.bottom = pLine->m_nY + 1;
		} while (pLine = pLine->m_pNextLineSameBlob);
	}
	cr = m_cr;
}

//-----------------------------------------------------------------
//
// CBlob::GetDIB - Create a monochrome DIB of the outline of the blob
//
// bmih - this is the bitmap info header for the DIB (you do the colors)
// pBits - GetDIB puts the bitmap here
//
//-----------------------------------------------------------------

#pragma optimize("",off)

void CBlob::GetDIB(BITMAPINFOHEADER &bmih,void *pBits)
{
	CRect cr;
	GetRect(cr);

	// Deal with the header.

	bmih.biSize = sizeof(BITMAPINFOHEADER);
	bmih.biWidth = cr.Width();
	bmih.biHeight = cr.Height();
	bmih.biPlanes = 1;
	bmih.biBitCount = 1;
	bmih.biCompression = BI_RGB;
	bmih.biSizeImage = 0;
	bmih.biXPelsPerMeter = 1000;
	bmih.biYPelsPerMeter = 1000;
	bmih.biClrUsed = 0;
	bmih.biClrImportant = 0;

	int nRasterWidth = GetDIBRasterWidth();

	// Here's the size of the whole bitmap in bytes.

	int nSize = GetDIBSize();

	BYTE *pPrimary = (BYTE *)pBits;

	// Here's a secondary bitmap.
	CByteArray bSecondary;
	bSecondary.SetSize(nSize);
	BYTE *pSecondary = bSecondary.GetData();
	CByteArray bTertiary;
	bTertiary.SetSize(nSize);
	BYTE *pTertiary = bTertiary.GetData();



	// Now here's the plot: there are four ways a pixel can get colored:
	//
	// 1) no line is on top of it
	// 2) no line is below it
	// 3) it is the leftmost pixel of a line
	// 4) it is the rightmost pixel of a line.
	//
	// It's easy to do #3 and 4. We just turn those pixels on.
	// # 1 and 2 are slightly more difficult. We start by clearing the
	// bitmaps. We then set all bits within the blob. We then clear
	// all bits above each line on one bitmap and below each line on
	// the other.

	memset(pPrimary,0,nSize);

	for (CLine *pLine = m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
		int nYRaster = cr.bottom - pLine->m_nY - 1;
		int nX = pLine->m_nXStart - cr.left;
		int nXEnd = pLine->m_nXEnd - cr.left;

		int nXByte = nX >> 3;
		int nXByteEnd = nXEnd >> 3;
		BYTE *ptr = pPrimary + nYRaster * nRasterWidth + nXByte;
		int nStartMod8 = nX & 7;
		BYTE bMask = 0xFF >> nStartMod8;
		*ptr |= bMask;
		while (nXByte < nXByteEnd) {
			ptr++;
			*ptr = 0xFF;
			nXByte++;
		}
		int nEndMod8 = nXEnd & 7;
		bMask = ~ (0xFF >> nEndMod8);
		*ptr &= bMask; // This assumes that lines are ordered right to left.
	}

	memcpy(pSecondary,pPrimary,nSize);
	memcpy(pTertiary,pPrimary,nSize);

	// Now offset the bitmap by one raster, negate and AND it. This crosses
	// out lines that overlap below.

	int nRasterWidthInDWords = nRasterWidth / 4;
	DWORD *dwTop = ((DWORD *)pPrimary) + nRasterWidthInDWords;
	DWORD *dwData = (DWORD *)pTertiary;
	for (int i = (cr.Height() - 1) * nRasterWidthInDWords ; i > 0; i--) {
		*dwTop++ &= ~ *dwData++;
	}

	dwData = ((DWORD *)pTertiary) + nRasterWidthInDWords;
	DWORD *dwBot = ((DWORD *)pSecondary);

	for (i = (cr.Height() - 1) * nRasterWidthInDWords ; i > 0; i--) {
		*dwBot++ &= ~ *dwData++;
	}

	// We OR the two maps together.

	dwData = (DWORD *)pPrimary;
	dwTop = (DWORD *)pSecondary;

	for (i = cr.Height() * nRasterWidthInDWords ; i > 0; i--) {
		*dwData++ |= *dwTop++;
	}

	// Finally, we run through another time, setting the left and right
	// edge bits.

	for (pLine = m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
		int nYRaster = cr.bottom - pLine->m_nY - 1;
		
		int nX;
		nX = pLine->m_nXStart - cr.left;
		BYTE *ptr = pPrimary + nYRaster * nRasterWidth;
		ptr[nX >> 3] |= 0x80 >> (nX & 7);
		nX = pLine->m_nXEnd - cr.left;
		ptr[nX >> 3] |= 0x80 >> (nX & 7);
	}
}

//-----------------------------------------------------------------
//
// CBlob::PtInBlob - This function determines whether the given point
//					 is within the blob.
//
//-----------------------------------------------------------------

BOOL CBlob::PtInBlob(const CPoint &pt)
{
	CRect crBlob;
	GetRect(crBlob);
	if (crBlob.PtInRect(pt)) {
		// We'll do a detailed analysis now, line by line.

		for (CLine *pLine = m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
			if (pt.y == pLine->m_nY &&
				pt.x >= pLine->m_nXStart &&
				pt.x <= pLine->m_nXEnd) return TRUE;
		}
	}
	return FALSE;
}

//-----------------------------------------------------------------
//
// CBlob::GetCentroid - The centroid is the mean X and Y value for
//						the blob; you can visualize it as the blob's
//						center of gravity.
//
//-----------------------------------------------------------------

CPoint CBlob::GetCentroid()
{
	int nXSumTimesTwo = 0;
	int nYSum = 0;
	int nCount = 0;
	int nXPixels = 0;

	// The sum of X pixels is (m_nXStart + m_nXEnd) * (m_nXEnd - m_nXStart + 1) / 2
	// but we're better served by doing one divide per blob
	// rather than one per line...

	for (CLine *pLine = m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
		int nXLength = pLine->m_nXEnd - pLine->m_nXStart + 1;
		nXSumTimesTwo += (pLine->m_nXStart + pLine->m_nXEnd) * nXLength;
		nXPixels += nXLength;
		nYSum += pLine->m_nY;
		nCount++;
	}

	// Round it.

	return CPoint((nXSumTimesTwo + nCount) / (2 * nXPixels),(nYSum + nCount / 2) / nCount);
}

//-----------------------------------------------------------------
//
// CBlob::GetArea - return the number of pixels in the blob.
//
//-----------------------------------------------------------------

int CBlob::GetArea() const
{
	int nArea = 0;
	for (CLine *pLine = m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
		nArea += pLine->m_nXEnd - pLine->m_nXStart + 1;
	}
	return nArea;	
}

//-----------------------------------------------------------------
//