blob.cpp

segmentation sample good luck

// CBlob::MatchBlobs - Return the fraction of points the two blobs
//					   share.
//
// blobOther - match against this blob.
//
//-----------------------------------------------------------------

double CBlob::MatchBlobs(CBlob & blobOther)
{
	// The most stable coordinate in a character image is its
	// centroid. This avoids problems with little blebs that
	// might mis-register the character if we used its rect.

	CPoint ptCentroid = GetCentroid();
	CPoint ptCentroidOther = blobOther.GetCentroid();

	// The worst score happens when both blobs miss.

	int nWorstScorePossible = GetArea() + blobOther.GetArea();

	CLine *pLine = m_pFirstLine;
	CLine *pLineOther = blobOther.m_pFirstLine;

	int nY = pLine->m_nY - ptCentroid.y;
	int nXStart = pLine->m_nXStart - ptCentroid.x;
	int nXEnd = pLine->m_nXEnd - ptCentroid.x;

	int nYOther = pLineOther->m_nY - ptCentroidOther.y;
	int nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
	int nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;

	int nScore = 0;
#ifdef _DEBUG
	std::vector<int> vYSum;
	int nBaseY = (nY < nYOther?nY:nYOther);
	int nYIndex;
#define YCHECK(x,y) \
			nYIndex = (y) - nBaseY; \
			if (vYSum.size() <= nYIndex) { \
				vYSum.resize(nYIndex+1); \
				vYSum[nYIndex] = (x); \
			} else { \
				vYSum[nYIndex] += (x); \
			}
#else
#define YCHECK(x,y)
#endif

	while (pLine && pLineOther) {

		// Here we go into a big mess of conditionals. We could convert
		// the blobs back to bitmaps and run a neat loop to score, bit by bit.
		// This is messier, but faster.

		if (nY < nYOther) {
			// Line is wholly above other's line.
			
			nScore += nXEnd - nXStart + 1;
			YCHECK(nXEnd - nXStart + 1,nY);
			if (pLine = pLine->m_pNextLineSameBlob) {
				nY = pLine->m_nY - ptCentroid.y;
				nXStart = pLine->m_nXStart - ptCentroid.x;
				nXEnd = pLine->m_nXEnd - ptCentroid.x;
			}
		} else if (nYOther < nY) {
			nScore += nXEndOther - nXStartOther + 1;
			YCHECK(nXEndOther - nXStartOther + 1,nYOther);
			if (pLineOther = pLineOther->m_pNextLineSameBlob) {
				nYOther = pLineOther->m_nY - ptCentroidOther.y;
				nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
				nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;
			}
		} else {
			// They're on the same line.

			if (nXEnd < nXStartOther) {
				// Line is wholly before other

				nScore += nXEnd - nXStart + 1;
				YCHECK(nXEnd - nXStart + 1,nY);
				if (pLine = pLine->m_pNextLineSameBlob) {
					nY = pLine->m_nY - ptCentroid.y;
					nXStart = pLine->m_nXStart - ptCentroid.x;
					nXEnd = pLine->m_nXEnd - ptCentroid.x;
				}
			} else if (nXEndOther < nXStart) {
				// Other wholly before line.

				nScore += nXEndOther - nXStartOther + 1;
				YCHECK(nXEndOther - nXStartOther + 1,nY);
				if (pLineOther = pLineOther->m_pNextLineSameBlob) {
					nYOther = pLineOther->m_nY - ptCentroidOther.y;
					nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
					nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;
				}
			} else {
				// One line overlaps the other.

				if (nXStart < nXStartOther) {
					nScore += nXStartOther - nXStart;
					YCHECK(nXStartOther - nXStart,nY);
					if (nXEnd <= nXEndOther) {
						// The whole line after nXStartOther is
						// contained in the other line. Shorten the
						// other line.

						nXStartOther = nXEnd + 1;

						// Move to the next line.

						if (pLine = pLine->m_pNextLineSameBlob) {
							nY = pLine->m_nY - ptCentroid.y;
							nXStart = pLine->m_nXStart - ptCentroid.x;
							nXEnd = pLine->m_nXEnd - ptCentroid.x;
						}
						if (nXStartOther > nXEndOther) {
							ASSERT(nXStartOther == nXEndOther + 1);

							// The other line is done too.
							if (pLineOther = pLineOther->m_pNextLineSameBlob) {
								nYOther = pLineOther->m_nY - ptCentroidOther.y;
								nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
								nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;
							}
						}
					} else {
						// The other ends first.

						nXStart = nXEndOther + 1;

						if (pLineOther = pLineOther->m_pNextLineSameBlob) {
							nYOther = pLineOther->m_nY - ptCentroidOther.y;
							nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
							nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;
						}

						if (nXStart > nXEnd) {
							ASSERT(nXStart == nXEnd + 1);
							if (pLine = pLine->m_pNextLineSameBlob) {
								nY = pLine->m_nY - ptCentroid.y;
								nXStart = pLine->m_nXStart - ptCentroid.x;
								nXEnd = pLine->m_nXEnd - ptCentroid.x;
							}
						}
					}
				} else {
					// The "other" line ends first.

					nScore += nXStart - nXStartOther;
					YCHECK(nXStart - nXStartOther,nY);
					if (nXEndOther <= nXEnd) {
						// The whole line after nXStartOther is
						// contained in the other line. Shorten the
						// other line.

						nXStart = nXEndOther + 1;

						// Move to the next line.

						if (pLineOther = pLineOther->m_pNextLineSameBlob) {
							nYOther = pLineOther->m_nY - ptCentroidOther.y;
							nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
							nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;
						}
						if (nXStart > nXEnd) {
							ASSERT(nXStart == nXEnd + 1);

							// The line is done too.
							if (pLine = pLine->m_pNextLineSameBlob) {
								nY = pLine->m_nY - ptCentroid.y;
								nXStart = pLine->m_nXStart - ptCentroid.x;
								nXEnd = pLine->m_nXEnd - ptCentroid.x;
							}
						}
					} else {
						// The line ends first.

						nXStartOther = nXEnd + 1;

						if (pLine = pLine->m_pNextLineSameBlob) {
							nY = pLine->m_nY - ptCentroid.y;
							nXStart = pLine->m_nXStart - ptCentroid.x;
							nXEnd = pLine->m_nXEnd - ptCentroid.x;
						}

						if (nXStartOther > nXEndOther) {
							ASSERT(nXStartOther == nXEndOther + 1);
							if (pLineOther = pLineOther->m_pNextLineSameBlob) {
								nYOther = pLineOther->m_nY - ptCentroidOther.y;
								nXStartOther = pLineOther->m_nXStart - ptCentroidOther.x;
								nXEndOther = pLineOther->m_nXEnd - ptCentroidOther.x;
							}
						}
					}
				}
			}
		}
	}
	while(pLine) {
		nScore += nXEnd - nXStart + 1;
		YCHECK(nXEnd - nXStart + 1,pLine->m_nY - ptCentroid.y);
		if (pLine = pLine->m_pNextLineSameBlob) {
			nXStart = pLine->m_nXStart;
			nXEnd = pLine->m_nXEnd;
		}
	}
	while(pLineOther) {
		nScore += nXEndOther - nXStartOther + 1;
		YCHECK(nXEndOther - nXStartOther + 1,pLineOther->m_nY - ptCentroidOther.y);
		if (pLineOther = pLineOther->m_pNextLineSameBlob) {
			nXStartOther = pLineOther->m_nXStart;
			nXEndOther = pLineOther->m_nXEnd;
		}
	}

#ifdef _DEBUG
	// When debugging, let's do the algorithm the slow way and
	// see if the result matches.

	// First make two bitmaps containing the characters.

	CRect cr;
	GetRect(cr);
	CRect crOther;
	blobOther.GetRect(crOther);
	cr -= ptCentroid;
	crOther -= ptCentroidOther;

	CRect crBitmap = cr;
	if (crBitmap.left > crOther.left)
		crBitmap.left = crOther.left;
	if (crBitmap.top > crOther.top) 
		crBitmap.top = crOther.top;
	if (crBitmap.bottom < crOther.bottom)
		crBitmap.bottom = crOther.bottom;
	if (crBitmap.right < crOther.right)
		crBitmap.right = crOther.right;

	std::vector<BYTE> vBitmap;
	std::vector<BYTE> vBitmapOther;
	int nSize = crBitmap.Height() * crBitmap.Width();
	vBitmap.resize(nSize);
	vBitmapOther.resize(nSize);
	for (int i = 0; i < nSize; i++) {
		vBitmap[i] = 0;
		vBitmapOther[i] = 0;
	}

	int nOffsetX = ptCentroid.x + crBitmap.left;
	int nOffsetY = ptCentroid.y + crBitmap.top;
	for (pLine = m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
		int nIndex = (pLine->m_nY - nOffsetY) * crBitmap.Width() + pLine->m_nXStart - nOffsetX;
		ASSERT(nIndex >= 0);
		for (int nX = pLine->m_nXStart; nX <= pLine->m_nXEnd; nX++) {
			ASSERT(nIndex < vBitmap.size());
			vBitmap[nIndex++] = 1;
		}
	}

	int nOffsetXOther = ptCentroidOther.x + crBitmap.left;
	int nOffsetYOther = ptCentroidOther.y + crBitmap.top;
	for (pLine = blobOther.m_pFirstLine; pLine; pLine = pLine->m_pNextLineSameBlob) {
		int nIndex = (pLine->m_nY - nOffsetYOther) * crBitmap.Width() + pLine->m_nXStart - nOffsetXOther;
		ASSERT(nIndex >= 0);
		for (int nX = pLine->m_nXStart; nX <= pLine->m_nXEnd; nX++) {
			ASSERT(nIndex < vBitmapOther.size());
			vBitmapOther[nIndex++] = 1;
		}
	}

	int nTestScore = 0;
	int nIndex = 0;
	for (i = 0; i < crBitmap.Height(); i++) {
		int nRasterScore = 0;
		for (int j = 0; j < crBitmap.Width(); j++) {
			if (vBitmap[nIndex] != vBitmapOther[nIndex]) {
				nTestScore++;
				nRasterScore++;
			}
			nIndex++;
		}
		ASSERT(nRasterScore == vYSum[i]);
	}

	ASSERT(nScore == nTestScore);
#endif
	ASSERT(nScore >= 0);
	ASSERT(nScore <= nWorstScorePossible);
	ASSERT(nWorstScorePossible > 0);
	return 1.0 - (double)nScore / (double)nWorstScorePossible;
}

//-----------------------------------------------------------------
//
// CBlob::CQTLocation - The quad tree template requires the class it's
//					    based on to have a function, CQTLocation, that
//					    returns the object's position.
//
//-----------------------------------------------------------------

CPoint CBlob::CQTLocation()
{
	// This returns the coordinates to be used when we put
	// blobs in a CQuadTree<CBlob>

	return GetCentroid();
}


//-----------------------------------------------------------------
//
// CBlob::GetDIBSize - Return the number of elements required to create
//					   a monochrome bitmap of the blob outline.
//
//-----------------------------------------------------------------

int CBlob::GetDIBSize()
{
	CRect cr;
	GetRect(cr);
	return GetDIBRasterWidth() * cr.Height();
}

//-----------------------------------------------------------------
//
// CBlob::GetDIBRasterWidth - Return the number of elements in a
//							  single raster of the monochrome bitmap
//							  of the blob outline.
//
//-----------------------------------------------------------------

int CBlob::GetDIBRasterWidth()
{
	CRect cr;
	GetRect(cr);

	// Figure out how wide a raster is (it's got to be a multiple of 4)

	int nRasterWidth = (cr.Width() + 31) / 32;
	nRasterWidth *= 4;

	return nRasterWidth;
}