gregion.cpp

来自「一个由Mike Gashler完成的机器学习方面的includes neural」· C++ 代码 · 共 1,037 行 · 第 1/2 页

	for(z = 0; z < pVideo->GetFrameCount(); z++)
	{
		for(y = 0; y < pVideo->GetHeight(); y++)
		{
			for(x = 0; x < pVideo->GetWidth(); x++)
			{
				u = x;
				v = y;
				w = z;
				do
				{
					region = pMask->GetFrame(w)->GetPixel(u, v);
					if(region != 0xffffffff)
						break;
					PickTobogganDirection(&gradMag, u, v, w, &du, &dv, &dw);
					u += du;
					v += dv;
					w += dw;
				} while(du != 0 || dv != 0 || dw != 0);
				if(region == 0xffffffff)
				{
					region = AddRegion();
					SetMaskPixel(u, v, w, pVideo->GetFrame(w)->GetPixel(u, v), region);
				}
				u = x;
				v = y;
				w = z;
				do
				{
					if(pMask->GetFrame(w)->GetPixel(u, v) != 0xffffffff)
						break;
					SetMaskPixel(u, v, w, pVideo->GetFrame(w)->GetPixel(u, v), region);
					PickTobogganDirection(&gradMag, u, v, w, &du, &dv, &dw);
					u += du;
					v += dv;
					w += dw;
				} while(du != 0 || dv != 0 || dw != 0);
				if(x > 0)
				{
					other = pMask->GetFrame(z)->GetPixel(x - 1, y);
					if(other != region)
						MakeNeighbors(region, other);
				}
				if(y > 0)
				{
					other = pMask->GetFrame(z)->GetPixel(x, y - 1);
					if(other != region)
						MakeNeighbors(region, other);
				}
				if(z > 0)
				{
					other = pMask->GetFrame(z - 1)->GetPixel(x, y);
					if(other != region)
						MakeNeighbors(region, other);
				}
			}
		}
	}
}

void G3DRegionGraph::MakeCoarserRegions(G3DRegionGraph* pFineRegions)
{
	// Find every region's closest neighbor
	GVideo* pFineRegionMask = pFineRegions->GetRegionMask();
	GVideo* pCoarseRegionMask = GetRegionMask();
	GAssert(pCoarseRegionMask->GetWidth() == pFineRegionMask->GetWidth() && pCoarseRegionMask->GetHeight() == pFineRegionMask->GetHeight(), "size mismatch");
	int* pBestNeighborMap = new int[pFineRegions->GetRegionCount()];
	Holder<int*> hBestNeighborMap(pBestNeighborMap);
	int i, j;
	for(i = 0; i < pFineRegions->GetRegionCount(); i++)
	{
		struct GRegion* pRegion = (struct GRegion*)pFineRegions->m_pRegions->GetPointer(i);
		struct GRegionEdge* pEdge;
		double d;
		double dBestDiff = 1e200;
		int nBestNeighbor = -1;
		for(pEdge = pRegion->m_pNeighbors; pEdge; pEdge = pEdge->GetNext(i))
		{
			j = pEdge->GetOther(i);
			struct GRegion* pOtherRegion = (struct GRegion*)pFineRegions->m_pRegions->GetPointer(j);
			d = MeasureRegionDifference(pRegion, pOtherRegion);
			if(d < dBestDiff)
			{
				dBestDiff = d;
				nBestNeighbor = j;
			}
		}
		GAssert(nBestNeighbor != -1 || pFineRegions->GetRegionCount() == 1, "failed to find a neighbor");
		pBestNeighborMap[i] = nBestNeighbor;
	}

	// Create a mapping to new regions numbers
	int* pNewRegionMap = new int[pFineRegions->GetRegionCount()];
	Holder<int*> hNewRegionMap(pNewRegionMap);
	memset(pNewRegionMap, 0xff, sizeof(int) * pFineRegions->GetRegionCount());
	int nNewRegionCount = 0;
	for(i = 0; i < pFineRegions->GetRegionCount(); i++)
	{
		int nNewRegion = -1;
		j = i;
		while(pNewRegionMap[j] == -1)
		{
			pNewRegionMap[j] = -2;
			j = pBestNeighborMap[j];
		}
		if(pNewRegionMap[j] == -2)
			nNewRegion = nNewRegionCount++;
		else
			nNewRegion = pNewRegionMap[j];
		j = i;
		while(pNewRegionMap[j] == -2)
		{
			pNewRegionMap[j] = nNewRegion;
			j = pBestNeighborMap[j];
		}
	}

	// Make the new regions
	int k;
	for(i = 0; i < pFineRegions->GetRegionCount(); i++)
	{
		struct GRegion* pRegion = (struct GRegion*)pFineRegions->m_pRegions->GetPointer(i);
		j = pNewRegionMap[i];
		if(GetRegionCount() <= j)
		{
			GAssert(GetRegionCount() == j, "how'd it get two behind?");
			AddRegion();
		}
		struct GRegion* pCoarseRegion = (struct GRegion*)m_pRegions->GetPointer(j);
		pCoarseRegion->m_nSumRed += pRegion->m_nSumRed;
		pCoarseRegion->m_nSumGreen += pRegion->m_nSumGreen;
		pCoarseRegion->m_nSumBlue += pRegion->m_nSumBlue;
		pCoarseRegion->m_nPixels += pRegion->m_nPixels;
	}
	for(i = 0; i < pFineRegions->GetRegionCount(); i++)
	{
		struct GRegion* pRegion = (struct GRegion*)pFineRegions->m_pRegions->GetPointer(i);
		j = pNewRegionMap[i];
		struct GRegionEdge* pEdge;
		for(pEdge = pRegion->m_pNeighbors; pEdge; pEdge = pEdge->GetNext(i))
		{
			k = pNewRegionMap[pEdge->GetOther(i)];
			if(j != k)
				MakeNeighbors(j, k);
		}
	}

	// Make the fine region mask
	unsigned int nOldRegion;
	int x, y, z;
	GImage* pCurrentFine;
	GImage* pCurrentCoarse;
	for(z = 0; z < pFineRegionMask->GetFrameCount(); z++)
	{
		if(pCoarseRegionMask->GetFrameCount() <= z)
			pCoarseRegionMask->AddBlankFrame();
		pCurrentFine = pFineRegionMask->GetFrame(z);
		pCurrentCoarse = pCoarseRegionMask->GetFrame(z);
		for(y = 0; y < pFineRegionMask->GetHeight(); y++)
		{
			for(x = 0; x < pFineRegionMask->GetWidth(); x++)
			{
				nOldRegion = pCurrentFine->GetPixel(x, y);
				pCurrentCoarse->SetPixel(x, y, pNewRegionMap[nOldRegion]);
			}
		}
	}
}

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

#define START_DIRECTION 1

GRegionBorderIterator::GRegionBorderIterator(GImage* pImage, int nSampleX, int nSampleY)
{
	m_pImage = pImage;
	m_nRegion = pImage->GetPixel(nSampleX, nSampleY);
	m_x = nSampleX;
	m_y = nSampleY;
	m_direction = START_DIRECTION;
	while(Look())
		Leap();
	m_endX = m_x;
	m_endY = m_y;
	m_bOddPass = false;
}

GRegionBorderIterator::~GRegionBorderIterator()
{
}

bool GRegionBorderIterator::Look()
{
	switch(m_direction)
	{
		case 0:
			if(m_x < (int)m_pImage->GetWidth() - 1)
				return(m_pImage->GetPixel(m_x + 1, m_y) == m_nRegion);
			else
				return false;
		case 1:
			if(m_y > 0)
				return(m_pImage->GetPixel(m_x, m_y - 1) == m_nRegion);
			else
				return false;
		case 2:
			if(m_x > 0)
				return(m_pImage->GetPixel(m_x - 1, m_y) == m_nRegion);
			else
				return false;
		case 3:
			if(m_y < (int)m_pImage->GetHeight() - 1)
				return(m_pImage->GetPixel(m_x, m_y + 1) == m_nRegion);
			else
				return false;
		default:
			GAssert(false, "unexpected direction");
	}
	return false;
}

void GRegionBorderIterator::Leap()
{
	switch(m_direction)
	{
		case 0:
			m_x++;
			break;
		case 1:
			m_y--;
			break;
		case 2:
			m_x--;
			break;
		case 3:
			m_y++;
			break;
		default:
			GAssert(false, "unexpected direction");
	}
}

bool GRegionBorderIterator::GetNext(int* pX, int* pY, int* pDirection)
{
	*pX = m_x;
	*pY = m_y;
	*pDirection = m_direction;
	if(m_x == m_endX && m_y == m_endY && m_direction == START_DIRECTION)
		m_bOddPass = !m_bOddPass;
	if(++m_direction >= 4)
		m_direction = 0;
	if(Look())
	{
		Leap();
		if(--m_direction < 0)
			m_direction = 3;
		if(Look())
		{
			Leap();
			if(--m_direction < 0)
				m_direction = 3;
		}
	}
	return m_bOddPass;
}

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

GRegionAreaIterator::GRegionAreaIterator(GImage* pImage, int nSampleX, int nSampleY)
{
	m_pImage = pImage;
	m_nRegion = pImage->GetPixel(nSampleX, nSampleY);

	// Find the bounding rectangle
	m_left = pImage->GetWidth() - 1;
	m_top = pImage->GetHeight() - 1;
	m_right = 0;
	m_bottom = 0;
	GRegionBorderIterator ittBorder(pImage, nSampleX, nSampleY);
	int x, y, d;
	while(ittBorder.GetNext(&x, &y, &d))
	{
		if(x < m_left)
			m_left = x;
		if(x > m_right)
			m_right = x;
		if(y < m_top)
			m_top = y;
		if(y > m_bottom)
			m_bottom = y;
	}
	m_x = m_left;
	m_y = m_top;
}

GRegionAreaIterator::~GRegionAreaIterator()
{
}

bool GRegionAreaIterator::GetNext(int* pX, int* pY)
{
	while(m_y <= m_bottom && m_pImage->GetPixel(m_x, m_y) != m_nRegion)
	{
		if(++m_x > m_right)
		{
			m_x = m_left;
			m_y++;
		}
	}
	if(m_y > m_bottom)
		return false;
	*pX = m_x;
	*pY = m_y;
	if(++m_x > m_right)
	{
		m_x = m_left;
		m_y++;
	}
	return true;
}

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

GSubImageFinder::GSubImageFinder(GImage* pHaystack)
{
	m_nHaystackWidth = GBits::GetBoundingPowerOfTwo(pHaystack->GetWidth());
	m_nHaystackHeight = GBits::GetBoundingPowerOfTwo(pHaystack->GetHeight());
	m_nHaystackX = (m_nHaystackWidth - pHaystack->GetWidth()) / 2;
	m_nHaystackY = (m_nHaystackHeight - pHaystack->GetHeight()) / 2;
	int nSize = m_nHaystackWidth * m_nHaystackHeight;
	m_pHaystackRed = new struct ComplexNumber[9 * nSize];
	m_pHaystackGreen = &m_pHaystackRed[nSize];
	m_pHaystackBlue = &m_pHaystackRed[2 * nSize];
	m_pNeedleRed = &m_pHaystackRed[3 * nSize];
	m_pNeedleGreen = &m_pHaystackRed[4 * nSize];
	m_pNeedleBlue = &m_pHaystackRed[5 * nSize];
	m_pCorRed = &m_pHaystackRed[6 * nSize];
	m_pCorGreen = &m_pHaystackRed[7 * nSize];
	m_pCorBlue = &m_pHaystackRed[8 * nSize];
	int x, y, xx, yy;
	GColor c;
	int pos = 0;
	for(y = 0; y < m_nHaystackHeight; y++)
	{
		yy = y - m_nHaystackY;
		for(x = 0; x < m_nHaystackWidth; x++)
		{
			xx = x - m_nHaystackX;
			if(xx >= 0 && xx < pHaystack->GetWidth() && yy >= 0 && yy < pHaystack->GetHeight())
			{
				c = pHaystack->GetPixel(xx, yy);
				m_pHaystackRed[pos].real = gRed(c) - 128;
				m_pHaystackRed[pos].imag = 0;
				m_pHaystackGreen[pos].real = gGreen(c) - 128;
				m_pHaystackGreen[pos].imag = 0;
				m_pHaystackBlue[pos].real = gBlue(c) - 128;
				m_pHaystackBlue[pos].imag = 0;
			}
			else
			{
				m_pHaystackRed[pos].real = 0;
				m_pHaystackRed[pos].imag = 0;
				m_pHaystackGreen[pos].real = 0;
				m_pHaystackGreen[pos].imag = 0;
				m_pHaystackBlue[pos].real = 0;
				m_pHaystackBlue[pos].imag = 0;
			}
			pos++;
		}
	}
	GFourier::FFT2D(m_nHaystackWidth, m_nHaystackHeight, m_pHaystackRed, true);
	GFourier::FFT2D(m_nHaystackWidth, m_nHaystackHeight, m_pHaystackGreen, true);
	GFourier::FFT2D(m_nHaystackWidth, m_nHaystackHeight, m_pHaystackBlue, true);
}

GSubImageFinder::~GSubImageFinder()
{
	delete[] m_pHaystackRed;
}

void GSubImageFinder::FindSubImage(int* pOutX, int* pOutY, GImage* pNeedle, GRect* pNeedleRect, GRect* pHaystackRect)
{
	// Copy into the array of complex numbers
	GAssert(GBits::IsPowerOfTwo(pNeedleRect->w) && GBits::IsPowerOfTwo(pNeedleRect->h), "Expected a power of 2");
	int x, y;
	int pos = 0;
	GColor c;
	for(y = 0; y < pNeedleRect->h; y++)
	{
		for(x = 0; x < pNeedleRect->w; x++)
		{
			c = pNeedle->GetPixel(pNeedleRect->x + x, pNeedleRect->y + y);
			m_pNeedleRed[pos].real = gRed(c) - 128;
			m_pNeedleRed[pos].imag = 0;
			m_pNeedleGreen[pos].real = gGreen(c) - 128;
			m_pNeedleGreen[pos].imag = 0;
			m_pNeedleBlue[pos].real = gBlue(c) - 128;
			m_pNeedleBlue[pos].imag = 0;
			pos++;
		}
	}

	// Convert to the Fourier domain
	GFourier::FFT2D(pNeedleRect->w, pNeedleRect->h, m_pNeedleRed, true);
	GFourier::FFT2D(pNeedleRect->w, pNeedleRect->h, m_pNeedleGreen, true);
	GFourier::FFT2D(pNeedleRect->w, pNeedleRect->h, m_pNeedleBlue, true);

	// Multiply m_pHaystack with the complex conjugate of m_pNeedle
	double r, i, mag;
	int xx, yy;
	pos = 0;
	for(y = 0; y < m_nHaystackHeight; y++)
	{
		yy = (y * pNeedleRect->h / m_nHaystackHeight) * pNeedleRect->w;
		for(x = 0; x < m_nHaystackWidth; x++)
		{
			xx = x * pNeedleRect->w / m_nHaystackWidth;
			r = m_pNeedleRed[yy + xx].real * m_pHaystackRed[pos].real + m_pNeedleRed[yy + xx].imag * m_pHaystackRed[pos].imag;
			i = m_pNeedleRed[yy + xx].real * m_pHaystackRed[pos].imag - m_pNeedleRed[yy + xx].imag * m_pHaystackRed[pos].real;
			mag = sqrt(r * r + i * i);
			m_pCorRed[pos].real = r / mag;
			m_pCorRed[pos].imag = i / mag;
			r = m_pNeedleGreen[yy + xx].real * m_pHaystackGreen[pos].real + m_pNeedleGreen[yy + xx].imag * m_pHaystackGreen[pos].imag;
			i = m_pNeedleGreen[yy + xx].real * m_pHaystackGreen[pos].imag - m_pNeedleGreen[yy + xx].imag * m_pHaystackGreen[pos].real;
			mag = sqrt(r * r + i * i);
			m_pCorGreen[pos].real = r / mag;
			m_pCorGreen[pos].imag = i / mag;
			r = m_pNeedleBlue[yy + xx].real * m_pHaystackBlue[pos].real + m_pNeedleBlue[yy + xx].imag * m_pHaystackBlue[pos].imag;
			i = m_pNeedleBlue[yy + xx].real * m_pHaystackBlue[pos].imag - m_pNeedleBlue[yy + xx].imag * m_pHaystackBlue[pos].real;
			mag = sqrt(r * r + i * i);
			m_pCorBlue[pos].real = r / mag;
			m_pCorBlue[pos].imag = i / mag;
			pos++;
		}
	}

	// Convert to the Spatial domain
	GFourier::FFT2D(m_nHaystackWidth, m_nHaystackHeight, m_pCorRed, false);
	GFourier::FFT2D(m_nHaystackWidth, m_nHaystackHeight, m_pCorGreen, false);
	GFourier::FFT2D(m_nHaystackWidth, m_nHaystackHeight, m_pCorBlue, false);

	// Find the max
	*pOutX = 0;
	*pOutY = 0;
	double d;
	double dBest = -1e200;
	for(y = 0; y < pHaystackRect->h; y++)
	{
		yy = m_nHaystackY + pHaystackRect->y + y;
		if(yy < 0 || yy >= m_nHaystackHeight) // todo: precompute range instead
			continue;
		yy *= m_nHaystackWidth;
		for(x = 0; x < pHaystackRect->w; x++)
		{
			xx = m_nHaystackX + pHaystackRect->x + x;
			if(xx < 0 || xx >= m_nHaystackWidth) // todo: precompute range instead
				continue;
			xx += yy;
			d = m_pCorRed[xx].real * m_pCorGreen[xx].real * m_pCorBlue[xx].real;
			if(d > dBest)
			{
				dBest = d;
				*pOutX = pHaystackRect->x + x;
				*pOutY = pHaystackRect->y + y;
			}
		}
	}
/*
	// Save correlation image
	GImage corr;
	corr.SetSize(m_nHaystackWidth, m_nHaystackHeight);
	pos = 0;
	for(y = 0; y < m_nHaystackHeight; y++)
	{
		for(x = 0; x < m_nHaystackWidth; x++)
			corr.SetPixel(x, y, gFromGray(MAX((int)0, (int)(m_pCorrelation[pos++].real * 255 * 256 / dBest))));
	}
	corr.SavePNGFile("correlat.png");
*/
}

#ifndef NO_TEST_CODE
// static
void GSubImageFinder::Test()
{
	// Make some random image
	GImage foo;
	foo.SetSize(256, 256);
	foo.Clear(0xff000000);
	foo.FillBox(13, 8, 12, 17, 0xff808030);
	foo.FillBox(8, 13, 10, 9, 0xff407040);
	foo.FillBox(20, 20, 220, 220, 0xffffffee);

	// Make the finder
	GSubImageFinder finder(&foo);

	// Make a sub-image
	GRect r2(0, 0, 256, 256);
	GRect r;
	r.x = 13;
	r.y = 17;
	r.w = 32;
	r.h = 32;
	GImage bar;
	bar.SetSize(32, 32);
	bar.Blit(0, 0, &foo, &r);

	// Find the sub-image
	r.x = 0;
	r.y = 0;
	int x, y;
	finder.FindSubImage(&x, &y, &bar, &r, &r2);
	if(x != 13 || y != 17)
		throw "wrong answer";
}
#endif // NO_TEST_CODE