gregion.cpp

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

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include "GRegion.h"
#include "GArray.h"
#include "GImage.h"
#include "GHashTable.h"
#include "GVideo.h"
#include "GFourier.h"
#include "GBits.h"
#include <math.h>

struct GRegion;


struct GRegionEdge
{
	int m_nRegion1;
	int m_nRegion2;
	GRegionEdge* m_pNext1;
	GRegionEdge* m_pNext2;

	int GetOther(int n)
	{
		if(n == m_nRegion1)
			return m_nRegion2;
		else if(n == m_nRegion2)
			return m_nRegion1;
		else
		{
			GAssert(false, "That region doesn't share this edge");
			return -1;
		}
	}

	struct GRegionEdge* GetNext(int nRegion)
	{
		if(nRegion == m_nRegion1)
			return m_pNext1;
		else if(nRegion == m_nRegion2)
			return m_pNext2;
		else
		{
			GAssert(false, "That region doesn't share this edge");
			return NULL;
		}
	}
};

struct GRegion
{
	int m_nPixels;
	int m_nSumRed;
	int m_nSumGreen;
	int m_nSumBlue;
	struct GRegionEdge* m_pNeighbors;
};




GRegionAjacencyGraph::GRegionAjacencyGraph()
{
	m_pRegions = new GPointerArray(128);
	m_pNeighbors = new GPointerArray(256);
	m_pHeap = new GStringHeap(2048);
}

GRegionAjacencyGraph::~GRegionAjacencyGraph()
{
	delete(m_pRegions);
	delete(m_pNeighbors);
	delete(m_pHeap);
}

int GRegionAjacencyGraph::AddRegion()
{
	int nRegion = m_pRegions->GetSize();
	struct GRegion* pNewRegion = (struct GRegion*)m_pHeap->Allocate(sizeof(struct GRegion));
	pNewRegion->m_nPixels = 0;
	pNewRegion->m_nSumRed = 0;
	pNewRegion->m_nSumGreen = 0;
	pNewRegion->m_nSumBlue = 0;
	pNewRegion->m_pNeighbors = NULL;
	m_pRegions->AddPointer(pNewRegion);
	return nRegion;
}

int GRegionAjacencyGraph::GetRegionCount()
{
	return m_pRegions->GetSize();
}

void GRegionAjacencyGraph::GetAverageColor(int nRegion, float* pRed, float* pGreen, float* pBlue)
{
	struct GRegion* pRegion = (struct GRegion*)m_pRegions->GetPointer(nRegion);
	*pRed = (float)pRegion->m_nSumRed / pRegion->m_nPixels;
	*pGreen = (float)pRegion->m_nSumGreen / pRegion->m_nPixels;
	*pBlue = (float)pRegion->m_nSumBlue / pRegion->m_nPixels;
}

bool GRegionAjacencyGraph::AreNeighbors(int nRegion1, int nRegion2)
{
	GAssert(nRegion1 != nRegion2, "same region");
	struct GRegion* pRegion1 = (struct GRegion*)m_pRegions->GetPointer(nRegion1);
	struct GRegionEdge* pEdge;
	for(pEdge = pRegion1->m_pNeighbors; pEdge; pEdge = pEdge->GetNext(nRegion1))
	{
		if(pEdge->GetOther(nRegion1) == nRegion2)
			return true;
	}
	return false;
}

void GRegionAjacencyGraph::MakeNeighbors(int nRegion1, int nRegion2)
{
	if(AreNeighbors(nRegion1, nRegion2))
		return;
	struct GRegion* pRegion1 = (struct GRegion*)m_pRegions->GetPointer(nRegion1);
	struct GRegion* pRegion2 = (struct GRegion*)m_pRegions->GetPointer(nRegion2);
	struct GRegionEdge* pNewEdge = (struct GRegionEdge*)m_pHeap->Allocate(sizeof(struct GRegionEdge));
	pNewEdge->m_nRegion1 = nRegion1;
	pNewEdge->m_nRegion2 = nRegion2;
	pNewEdge->m_pNext1 = pRegion1->m_pNeighbors;
	pNewEdge->m_pNext2 = pRegion2->m_pNeighbors;
	pRegion1->m_pNeighbors = pNewEdge;
	pRegion2->m_pNeighbors = pNewEdge;
	m_pNeighbors->AddPointer(pNewEdge);
}

int GRegionAjacencyGraph::GetAjacencyCount()
{
	return m_pNeighbors->GetSize();
}

void GRegionAjacencyGraph::GetAjacency(int nEdge, int* pRegion1, int* pRegion2)
{
	struct GRegionEdge* pEdge = (struct GRegionEdge*)m_pNeighbors->GetPointer(nEdge);
	*pRegion1 = pEdge->m_nRegion1;
	*pRegion2 = pEdge->m_nRegion2;
}

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

G2DRegionGraph::G2DRegionGraph(int nWidth, int nHeight)
 : GRegionAjacencyGraph()
{
	m_pRegionMask = new GImage();
	m_pRegionMask->SetSize(nWidth, nHeight);
	m_pRegionMask->Clear(0xffffffff);
}

G2DRegionGraph::~G2DRegionGraph()
{
	delete(m_pRegionMask);
}

void G2DRegionGraph::SetMaskPixel(int x, int y, GColor c, int nRegion)
{
	GAssert(x >= 0 && x < (int)m_pRegionMask->GetWidth() && y >= 0 && y < (int)m_pRegionMask->GetHeight(), "out of range");
	GAssert(m_pRegionMask->GetPixel(x, y) == 0xffffffff, "This pixel is already set");
	m_pRegionMask->SetPixel(x, y, nRegion);
	struct GRegion* pRegion = (struct GRegion*)m_pRegions->GetPointer(nRegion);
	pRegion->m_nSumRed += gRed(c);
	pRegion->m_nSumGreen += gGreen(c);
	pRegion->m_nSumBlue += gBlue(c);
	pRegion->m_nPixels++;
}

int MaxChan(GColor c)
{
	//return MAX(gRed(c), MAX(gGreen(c), gBlue(c)));
	return c;
}

void PickTobogganDirection(GImage* pGradMagImage, int u, int v, int* pdu, int* pdv)
{
	int cand;
	int grad = MaxChan(pGradMagImage->GetPixel(u, v));
	int du = 0;
	int dv = 0;
	if(u > 0)
	{
		cand = MaxChan(pGradMagImage->GetPixel(u - 1, v));
		if(cand < grad)
		{
			grad = cand;
			du = -1;
			dv = 0;
		}
	}
	if(v > 0)
	{
		cand = MaxChan(pGradMagImage->GetPixel(u, v - 1));
		if(cand < grad)
		{
			grad = cand;
			du = 0;
			dv = -1;
		}
	}
	if(u < (int)pGradMagImage->GetWidth() - 1)
	{
		cand = MaxChan(pGradMagImage->GetPixel(u + 1, v));
		if(cand < grad)
		{
			grad = cand;
			du = 1;
			dv = 0;
		}
	}
	if(v < (int)pGradMagImage->GetHeight() - 1)
	{
		cand = MaxChan(pGradMagImage->GetPixel(u, v + 1));
		if(cand < grad)
		{
			grad = cand;
			du = 0;
			dv = 1;
		}
	}
	*pdu = du;
	*pdv = dv;
}

void G2DRegionGraph::MakeWatershedRegions(const GImage* pImage)
{
	GImage gradMag;
	gradMag.MakeGradientMagnitudeImage(pImage);
	GImage* pMask = GetRegionMask();
	int x, y, u, v, du, dv;
	unsigned int region, other;
	for(y = 0; y < pImage->GetHeight(); y++)
	{
		for(x = 0; x < pImage->GetWidth(); x++)
		{
			u = x;
			v = y;
			do
			{
				region = pMask->GetPixel(u, v);
				if(region != 0xffffffff)
					break;
				PickTobogganDirection(&gradMag, u, v, &du, &dv);
				u += du;
				v += dv;
			} while(du != 0 || dv != 0);
			if(region == 0xffffffff)
			{
				region = AddRegion();
				SetMaskPixel(u, v, pImage->GetPixel(u, v), region);
			}
			u = x;
			v = y;
			do
			{
				if(pMask->GetPixel(u, v) != 0xffffffff)
					break;
				SetMaskPixel(u, v, pImage->GetPixel(u, v), region);
				PickTobogganDirection(&gradMag, u, v, &du, &dv);
				u += du;
				v += dv;
			} while(du != 0 || dv != 0);
			if(x > 0)
			{
				other = pMask->GetPixel(x - 1, y);
				if(other != region)
					MakeNeighbors(region, other);
			}
			if(y > 0)
			{
				other = pMask->GetPixel(x, y - 1);
				if(other != region)
					MakeNeighbors(region, other);
			}
		}
	}
}

double MeasureRegionDifference(struct GRegion* pA, struct GRegion* pB)
{
	double dSum = 0;
	double d;
	d = (double)pA->m_nSumRed / pA->m_nPixels - (double)pB->m_nSumRed / pB->m_nPixels;
	dSum += (d * d);
	d = (double)pA->m_nSumGreen / pA->m_nPixels - (double)pB->m_nSumGreen / pB->m_nPixels;
	dSum += (d * d);
	d = (double)pA->m_nSumBlue / pA->m_nPixels - (double)pB->m_nSumBlue / pB->m_nPixels;
	dSum += (d * d);
	return dSum;
}

void G2DRegionGraph::MakeCoarserRegions(G2DRegionGraph* pFineRegions)
{
	// Find every region's closest neighbor
	GImage* pFineRegionMask = pFineRegions->GetRegionMask();
	GImage* 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;
	for(y = 0; y < (int)pFineRegionMask->GetHeight(); y++)
	{
		for(x = 0; x < (int)pFineRegionMask->GetWidth(); x++)
		{
			nOldRegion = pFineRegionMask->GetPixel(x, y);
			pCoarseRegionMask->SetPixel(x, y, pNewRegionMap[nOldRegion]);
		}
	}
}

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

G3DRegionGraph::G3DRegionGraph(int nWidth, int nHeight)
 : GRegionAjacencyGraph()
{
	m_pRegionMask = new GVideo(nWidth, nHeight);
}

G3DRegionGraph::~G3DRegionGraph()
{
	delete(m_pRegionMask);
}

void G3DRegionGraph::SetMaskPixel(int x, int y, int z, GColor c, int nRegion)
{
	GAssert(x >= 0 && x < m_pRegionMask->GetWidth() && y >= 0 && y < m_pRegionMask->GetHeight() && z >= 0 && z < m_pRegionMask->GetFrameCount(), "out of range");
	GAssert(m_pRegionMask->GetFrame(z)->GetPixel(x, y) == 0xffffffff, "This pixel is already set");
	m_pRegionMask->GetFrame(z)->SetPixel(x, y, nRegion);
	struct GRegion* pRegion = (struct GRegion*)m_pRegions->GetPointer(nRegion);
	pRegion->m_nSumRed += gRed(c);
	pRegion->m_nSumGreen += gGreen(c);
	pRegion->m_nSumBlue += gBlue(c);
	pRegion->m_nPixels++;
}

void PickTobogganDirection(GVideo* pGradMagVideo, int u, int v, int w, int* pdu, int* pdv, int* pdw)
{
	unsigned int cand;
	GImage* pFrame = pGradMagVideo->GetFrame(w);
	unsigned int grad = pFrame->GetPixel(u, v);
	int du = 0;
	int dv = 0;
	int dw = 0;
	if(w > 0)
	{
		pFrame = pGradMagVideo->GetFrame(w - 1);
		cand = pFrame->GetPixel(u, v);
		if(cand < grad)
		{
			grad = cand;
			du = 0;
			dv = 0;
			dw = -1;
		}
	}
	if(w < pGradMagVideo->GetFrameCount() - 1)
	{
		pFrame = pGradMagVideo->GetFrame(w + 1);
		cand = pFrame->GetPixel(u, v);
		if(cand < grad)
		{
			grad = cand;
			du = 0;
			dv = 0;
			dw = 1;
		}
	}
	if(u > 0)
	{
		cand = pFrame->GetPixel(u - 1, v);
		if(cand < grad)
		{
			grad = cand;
			du = -1;
			dv = 0;
			dw = 0;
		}
	}
	if(v > 0)
	{
		cand = pFrame->GetPixel(u, v - 1);
		if(cand < grad)
		{
			grad = cand;
			du = 0;
			dv = -1;
			dw = 0;
		}
	}
	if(u < pGradMagVideo->GetWidth() - 1)
	{
		cand = pFrame->GetPixel(u + 1, v);
		if(cand < grad)
		{
			grad = cand;
			du = 1;
			dv = 0;
			dw = 0;
		}
	}
	if(v < pGradMagVideo->GetHeight() - 1)
	{
		cand = pFrame->GetPixel(u, v + 1);
		if(cand < grad)
		{
			grad = cand;
			du = 0;
			dv = 1;
			dw = 0;
		}
	}
	*pdu = du;
	*pdv = dv;
	*pdw = dw;
}

void G3DRegionGraph::MakeWatershedRegions(GVideo* pVideo)
{
	GVideo gradMag(pVideo->GetWidth(), pVideo->GetHeight());
	gradMag.MakeGradientMagnitudeVideo(pVideo, false);
	GVideo* pMask = GetRegionMask();
	GAssert(pVideo->GetWidth() == pMask->GetWidth() && pVideo->GetHeight() == pMask->GetHeight(), "size mismatch");
	int x, y, z, u, v, w, du, dv, dw;
	unsigned int region, other;
	while(pMask->GetFrameCount() < pVideo->GetFrameCount())
	{
		pMask->AddBlankFrame();
		pMask->GetFrame(pMask->GetFrameCount() - 1)->Clear(0xffffffff);
	}