#include ".\contentimresize.h"
#using <mscorlib.dll>
#include <algorithm>
#include <sstream>
#include <set>
#include "EdgeDetection.h"

float CContentImResize::m_enlargeFraction = 0.3f;

CContentImResize::CContentImResize(void)
{
}

CContentImResize::~CContentImResize(void)
{
}

void CContentImResize::ContentAwareImResize(CFloatImage& src, CFloatImage& dst)
{
	CShape srcSh = src.Shape(), dstSh = dst.Shape();
	if((srcSh.width == dstSh.width) && (srcSh.height == dstSh.height))
	{
		Loop_Image(x,y,srcSh.width,srcSh.height)
		{
			for(int c = 0; c < srcSh.nBands; c++)
				dst.Pixel(x,y,c) = src.Pixel(x,y,c);
		}
		return;
	}

	Initialization(src);
	SeamSet seamSet;
	FindHoriSeam(srcSh,seamSet,srcSh.height);
	SaveImageWithSeams(m_originImage,"HorizonSeams.bmp",seamSet);
	
	seamSet.clear();
	FindVertSeam(srcSh,seamSet,srcSh.width);
	SaveImageWithSeams(m_originImage,"VerticalSeams.bmp",seamSet);

	return;

	int r = dstSh.height - srcSh.height, c = dstSh.width - srcSh.width;
	if(r >= 0 && c >= 0)
	{
		EnlargeImage(src,dst,r,c);
		return;
	}

	if(r < 0 || c < 0)
	{
		CFloatImage tmpImg1(srcSh), tmpImg2;
		srcSh = tmpImg2.Shape(), dstSh = dst.Shape();
		CFloatImage gray(srcSh.width, srcSh.height, 1);
		Convert2GrayFloat(tmpImg2,gray);
		vector<TranspotElement> transPath;
		TransPath(gray,dst,transPath);

		ImageClone(tmpImg2,tmpImg1);	//share pixel address
		for (vector<TranspotElement>::iterator iter = transPath.begin();
			iter != transPath.end(); iter++)
		{
			if(iter->seamType == Horizontal)
				ShiftOneHoriSeam(tmpImg1,tmpImg2,iter->seam,iter->zoomType);
			else
				ShiftOneVertSeam(tmpImg1,tmpImg2,iter->seam,iter->zoomType);
			ImageClone(tmpImg2,tmpImg1);
		}
		ImageClone(tmpImg2,dst);
	}
}

void CContentImResize::EnlargeImage(CFloatImage& src, CFloatImage& dst, int r, int c)
{
	CShape sh = src.Shape();
	int rMaxEnlarge = (int)(sh.height * m_enlargeFraction);
	int cMaxEnlarge = (int)(sh.width * m_enlargeFraction);

	vector<Seam> seamSet;
	CShape tmpSh = sh;
	int seamNum = 0;
	CFloatImage tmpImg;
	ImageClone(src,tmpImg);

	for (int i = 0; i <= r / rMaxEnlarge; i++)
	{
		if(r <= 0)
			break;
		seamSet.clear();
		if(i != r / rMaxEnlarge)
		{
			seamNum = rMaxEnlarge;
		}
		else
		{
			seamNum = r - rMaxEnlarge * (r / rMaxEnlarge);
		}
		FindHoriSeam(tmpSh, seamSet, seamNum);
		tmpSh.height = tmpSh.height + seamNum;
		dst.ReAllocate(tmpSh);
		AddSeams(tmpImg,dst,seamSet,Horizontal);
		if(i != r / rMaxEnlarge)
		{
			ImageClone(dst,tmpImg);
			Initialization(tmpImg);
		}
	}

	for (int j = 0; j <= c / cMaxEnlarge; j++)
	{
		if(c <= 0)
			break;
		seamSet.clear();
		if(j != c / cMaxEnlarge)
		{
			seamNum = cMaxEnlarge;
		}
		else
		{
			seamNum = c - cMaxEnlarge * (c / cMaxEnlarge);
		}
		FindVertSeam(tmpSh,seamSet,seamNum);
		tmpSh.width += seamNum;
		dst.ReAllocate(tmpSh);
		AddSeams(tmpImg,dst,seamSet,Vertical);
		if(j != c / cMaxEnlarge)
		{
			ImageClone(dst,tmpImg);
			Initialization(tmpImg);
		}
	}
}

void CContentImResize::AddSeams(CFloatImage& src, CFloatImage& dst, const vector<Seam>& seamSet, SeamType seamType)
{
	CShape sh1 = src.Shape(), sh2 = dst.Shape();
	SetLabelImage(sh1, -1);
	SetLabelImage(seamSet, 1);

	set<int> supvSet;
	if(seamType == Horizontal)
	{
		int seamNum = sh2.height - sh1.height;
		for(int x = 0; x < sh1.width; x++)
		for(int y1 = 0, y2 = 0; y1 < sh1.height; y1++, y2++)
		{
			if(m_labelImg.Pixel(x,y1,0) < 0)
			{
				for(int c = 0; c < sh1.nBands; c++)
					dst.Pixel(x,y2,c) = src.Pixel(x,y1,c);
			}
			else
			{
				for(int c = 0; c < sh1.nBands; c++)
					dst.Pixel(x,y2,c) = src.Pixel(x,y1,c);
				y2++;
				int t = x * LargeNum + y1;
				int dy = 0;
				while(supvSet.find(t) != supvSet.end())
				{
					dy++;
					t = x * LargeNum + y1 + dy;
				}
				supvSet.insert(t);
				for(int c = 0; c < sh1.nBands; c++)
					dst.Pixel(x,y2,c) = 0.5f * (src.Pixel(x,y1+dy,c) + src.Pixel(x,y1+dy+1,c));
			}
		}
	}
	else if(seamType == Vertical)
	{
		int seamNum = sh2.width - sh1.width;
		for(int y = 0; y < sh1.height; y++)
		for(int x1 = 0, x2 = 0; x1 < sh1.width; x1++, x2++)
		{
			if(m_labelImg.Pixel(x1,y,0) < 0)
			{
				for(int c = 0; c < sh1.nBands; c++)
					dst.Pixel(x2,y,c) = src.Pixel(x1,y,c);
			}
			else
			{
				for(int c = 0; c < sh1.nBands; c++)
					dst.Pixel(x2,y,0) = src.Pixel(x1,y,c);
				x2++;
				int t = y * LargeNum + x1;
				int dx = 0;
				while (supvSet.find(t) != supvSet.end())
				{
					dx++;
					t = y * LargeNum + x1 + dx;
				}
				supvSet.insert(t);
				for(int c = 0; c < sh1.nBands; c++)
					dst.Pixel(x2,y,c) = 0.5f * (src.Pixel(x1+dx,y,c) + src.Pixel(x1+dx+1,y,c));
			}
		}
	}
}

void CContentImResize::SetLabelImage(CShape& sh, int label)
{
	m_labelImg.ReAllocate(sh);
	Loop_Image(x,y,sh.width,sh.height)
	{
		m_labelImg.Pixel(x,y,0) = label;
	}
}

void CContentImResize::SetLabelImage(const SeamSet& seamSet, int label)
{
	for(SeamSet::const_iterator iter = seamSet.begin(); iter != seamSet.end(); iter++)
		for(Seam::const_iterator seamIt = iter->begin(); seamIt != iter->end(); seamIt++)
		{
			m_labelImg.Pixel(seamIt->first, seamIt->second,0) = label;
		}
}

void CContentImResize::TransPath(CFloatImage& gray, CFloatImage& dst, vector<TranspotElement>& transPath)
{
	CShape srcSh = gray.Shape(), dstSh = dst.Shape();
	int r = abs(srcSh.height - dstSh.height);
	int c = abs(srcSh.width - dstSh.width);
	TransMap transMap;
	TranspotMap(gray,dst,transMap);

	transPath.resize(r + c);
	int rIndex = r, cIndex = c;
	transPath[r+c-1] = transMap[rIndex][cIndex];
	for (int i = r + c - 2; i >= 0; i--)
	{
		TranspotElement& elem = transPath[i+1];
		if(elem.seamType == Vertical)
			cIndex -= 1;
		else
			rIndex -= 1;
		transPath[i] = transMap[rIndex][cIndex];
	}
}

void CContentImResize::TranspotMap(CFloatImage& gray, CFloatImage& dst, TransMap& transMap)
{
	CShape srcSh = gray.Shape(), dstSh = dst.Shape();
	int r = srcSh.height - dstSh.height, c = srcSh.width - dstSh.width; 

	ZoomType rowZoom, columZoom;
	rowZoom = r > 0 ? Shrink : Enlarge;
	columZoom = c > 0 ? Shrink : Enlarge;
	
	r = abs(r);
	c = abs(c);
	
	transMap.resize(r+1);
	for(int i = 0; i < r+1; i++)
		transMap[i].resize(c+1);

	vector<CFloatImage> vTopImg;
	TranspotElement elem;
	CFloatImage leftImg,tmpImg;
	CShape tmpSh;
	
	vTopImg.resize(c+1);
	for(int i = 0; i < r + 1; i++)
	{
		for(int j = 0; j < c + 1; j++)
		{
			if((i==0) && (j==0))
			{
				elem.cumValue = 0.0f;
				transMap[i][j] = elem;
				ImageClone(gray,vTopImg[j]);
			}
			else if(i == 0)
			{
				Initialization(vTopImg[j-1]);
				vector< VertSeam > Vseams;
				elem.cumValue = transMap[i][j-1].cumValue + FindVertSeam(vTopImg[j-1].Shape(),Vseams,1);
				elem.seam = Vseams[0];
				elem.seamType = Vertical;
				elem.zoomType = columZoom;
				transMap[i][j] = elem;
				ShiftOneVertSeam(vTopImg[j-1],leftImg,transMap[i][j].seam,columZoom);
				ImageClone(leftImg,vTopImg[j]);
			}
			else if(j == 0)
			{
				Initialization(vTopImg[j]);
				vector< HorizonSeam > Hseams;
				elem.cumValue = transMap[i-1][j].cumValue + FindHoriSeam(vTopImg[j].Shape(),Hseams,1);
				elem.seam = Hseams[0];
				elem.seamType = Horizontal;
				elem.zoomType = rowZoom;
				transMap[i][j] = elem;
				ShiftOneHoriSeam(vTopImg[j], leftImg, transMap[i][j].seam, rowZoom);
				ImageClone(leftImg,vTopImg[j]);
			}
			else
			{
				vector< HorizonSeam > Hseams;
				vector< VertSeam > Vseams;
				Initialization(vTopImg[j]);
				float tVal1 = transMap[i-1][j].cumValue + FindHoriSeam(vTopImg[j].Shape(),Hseams,1);
				Initialization(leftImg);
				float tVal2 = transMap[i][j-1].cumValue + FindVertSeam(leftImg.Shape(),Vseams,1);
				elem.cumValue = min(tVal1, tVal2);
				elem.seam = tVal1 < tVal2 ? Hseams[0] : Vseams[0];
				elem.seamType = tVal1 < tVal2 ? Horizontal : Vertical;
				elem.zoomType = tVal1 < tVal2 ? rowZoom : columZoom;
				transMap[i][j] = elem;
				if(tVal1 < tVal2)
					ShiftOneHoriSeam(vTopImg[j],tmpImg,transMap[i][j].seam,rowZoom);
				else
					ShiftOneVertSeam(leftImg,tmpImg,transMap[i][j].seam,columZoom);
				ImageClone(tmpImg,vTopImg[j]);
				ImageClone(tmpImg,leftImg);
			}
		}
		/*
		int index = 0;
		for(vector<CFloatImage>::iterator iter = vTopImg.begin();
			iter != vTopImg.end(); iter++,index++)
		{
			string name, stmp;
			stringstream stream;
			stream.clear();
			stream<<i;
			stream>>name;
			stream.clear();
			stream<<index;
			stream>>stmp;
			name = "images\\" + name + stmp + ".bmp";
			SaveFloatImage(*iter,name, true);
		}
*/
	}
}

void CContentImResize::Initialization(CFloatImage& src)
{
	CShape sh = src.Shape();
	CFloatImage gx(sh),gy(sh);
	float mask[2] = {-1.0f, 1.0f};
	ImageClone(src,m_originImage);
	MaskProcessing(src,gx,mask,2,1);
	MaskProcessing(src,gy,mask,1,2);
	EnergyGradient(gx,gy);
	ComputeHoriCumEnMap();
	ComputeVertCumEnMap();	
}

void CContentImResize::ShiftOneVertSeam(CFloatImage& src, CFloatImage& dst, VertSeam& Vseam, ZoomType zoomType)
{
	CShape sh = src.Shape();
	switch(zoomType)
	{
	case Shrink:
		sh.width -= 1;
		dst.ReAllocate(sh);
		Loop_Image(x,y,sh.width,sh.height)
		{
			for(int nBand = 0; nBand < sh.nBands; nBand++)
			{
				if(x < Vseam[y].first)
					dst.Pixel(x,y,nBand) = src.Pixel(x,y,nBand);
				else
					dst.Pixel(x,y,nBand) = src.Pixel(x+1,y,nBand);
			}
		}
		break;
	case Enlarge:
		sh.width += 1;
		dst.ReAllocate(sh);
		Loop_Image(x,y,sh.width,sh.height)
		{
			for(int nBand = 0; nBand < sh.nBands; nBand++)
			{
				if(x <= Vseam[y].first)
					dst.Pixel(x,y,nBand) = src.Pixel(x,y,nBand);
				else if(x == Vseam[y].first + 1)
					dst.Pixel(x,y,nBand) = 0.5f * (src.Pixel(x,y,nBand) + src.Pixel(x-1,y,nBand));
				else
					dst.Pixel(x,y,nBand) = src.Pixel(x-1,y,nBand);
			}
		}
		break;
	default:
		cout<<"ShiftOneVertSeam Error!"<<endl;
		exit(0);
	}
}

void CContentImResize::ShiftOneHoriSeam(CFloatImage& src, CFloatImage& dst, HorizonSeam& Hseam, ZoomType zoomType)
{
	CShape sh = src.Shape();
	switch(zoomType)
	{
	case Shrink:
		sh.height -= 1;
		dst.ReAllocate(sh);
		Loop_Image(x,y,sh.width,sh.height)
		{
			for (int nBand = 0; nBand < sh.nBands; nBand++)
			{
				if(y < Hseam[x].second)
					dst.Pixel(x,y,nBand) = src.Pixel(x,y,nBand);
				else
					dst.Pixel(x,y,nBand) = src.Pixel(x,y+1,nBand);
			}
		}
		break;
	case Enlarge:
		sh.height += 1;
		dst.ReAllocate(sh);
		Loop_Image(x,y,sh.width,sh.height)
		{
			for (int nBand = 0; nBand < sh.nBands; nBand++)
			{
				if(y <= Hseam[x].second)
					dst.Pixel(x,y,nBand) = src.Pixel(x,y,nBand);
				else if(y == Hseam[x].second + 1)
					dst.Pixel(x,y,nBand) = 0.5f * (src.Pixel(x,y,nBand) + src.Pixel(x,y-1,nBand));
				else
					dst.Pixel(x,y,nBand) = src.Pixel(x,y-1,nBand);
			}
		}
		break;
	default:
		cout<<"ShiftOneHoriSeam Error!"<<endl;
		exit(0);
	}
}

float CContentImResize::FindHoriSeam(CShape& sh, vector< HorizonSeam >& Hseams, int seamNum)
{
	sort(m_lastColum.begin(),m_lastColum.end());
	
	HorizonSeam seam;
	for(int n = 0; n < seamNum; n++)
	{
		int minIndex = m_lastColum[n].second;
		int yPre = minIndex;
		int xPre = sh.width - 1;
		seam.resize(sh.width);
		for (int i = sh.width - 1; i >= 0; i--)
		{
			seam[i] = make_pair(xPre,yPre);
			xPre = m_HCumEnMap[i][yPre].xPrevious;
			yPre = m_HCumEnMap[i][yPre].yPrevious;
		}
		Hseams.push_back(seam);
	}

	int minIndex = m_lastColum[0].second;
	return m_HCumEnMap[sh.width-1][minIndex].cumEnergy;
}

float CContentImResize::FindVertSeam(CShape& sh, vector< VertSeam >& Vseams, int seamNum)
{
	sort(m_lastRow.begin(),m_lastRow.end());

	VertSeam seam;
	for(int n = 0; n < seamNum; n++)
	{
		int minIndex = m_lastRow[n].second;
		int xPre = minIndex;
		int yPre = sh.height - 1;
		seam.resize(sh.height);
		for (int i = sh.height - 1; i >= 0; i--)
		{
			seam[i] = make_pair(xPre,yPre);
			xPre = m_VCumEnMap[i][xPre].xPrevious;
			yPre = m_VCumEnMap[i][xPre].yPrevious;
		}
		Vseams.push_back(seam);
	}

	int minIndex = m_lastRow[0].second;
	return m_VCumEnMap[sh.height-1][minIndex].cumEnergy;
}

void CContentImResize::ComputeHoriCumEnMap()
{
	m_HCumEnMap.clear();

	CShape sh = m_enMap.Shape();
	CumEnergyElement enElem;
	vector<CumEnergyElement> enVec;

	for(int x = 0; x < sh.width; x++)
	{
		enVec.clear();
		for(int y = 0; y < sh.height; y++)
		{
			if(x == 0)
			{
				enElem.cumEnergy = m_enMap.Pixel(x,y,0);
				enElem.xPrevious = x;
				enElem.yPrevious = y;
				enVec.push_back(enElem);
			}
			else
			{
				float leftTop = OutOfImage(x-1,y-1,sh.width,sh.height) ? 1000000000.0f : m_HCumEnMap[x-1][y-1].cumEnergy;
				float left = OutOfImage(x-1,y,sh.width,sh.height) ? 1000000000.0f : m_HCumEnMap[x-1][y].cumEnergy;
				float leftDown = OutOfImage(x-1,y+1,sh.width,sh.height) ? 1000000000.0f : m_HCumEnMap[x-1][y+1].cumEnergy;
				float tmin = minABC(leftTop,left,leftDown);
				enElem.cumEnergy = tmin + m_enMap.Pixel(x,y,0);
				enElem.xPrevious = x - 1;
				if(isEqual(tmin,leftTop))
				{			
					enElem.yPrevious = y - 1;
				}
				else if (isEqual(tmin,left))
				{
					enElem.yPrevious = y;
				}
				else if (isEqual(tmin, leftDown))
				{
					enElem.yPrevious = y + 1;
				}
				enVec.push_back(enElem);
			}
			if(x == sh.width - 1)
			{
				m_lastColum.push_back(make_pair(enElem.cumEnergy, y));
			}
		}
		m_HCumEnMap.push_back(enVec);
	}
}

void CContentImResize::ComputeVertCumEnMap()
{
	m_VCumEnMap.clear();

	CShape sh = m_enMap.Shape();
	CumEnergyElement cumEnElem;
	vector<CumEnergyElement> cumEnVec;

	for(int y = 0; y < sh.height; y++)
	{
		cumEnVec.clear();
		for(int x = 0; x < sh.width; x++)
		{
			if(y == 0)
			{
				cumEnElem.cumEnergy = m_enMap.Pixel(x,y,0);
				cumEnElem.xPrevious = x;
				cumEnElem.yPrevious = y;
				cumEnVec.push_back(cumEnElem);
			}
			else
			{
				float topLeft = OutOfImage(x-1,y-1,sh.width,sh.height) ? 1000000000.0f : m_VCumEnMap[y-1][x-1].cumEnergy;
				float top = OutOfImage(x,y-1,sh.width,sh.height) ? 1000000000.0f : m_VCumEnMap[y-1][x].cumEnergy;
				float topRight = OutOfImage(x+1,y-1,sh.width,sh.height) ? 1000000000.0f : m_VCumEnMap[y-1][x+1].cumEnergy;
				float tmin = minABC(topLeft,top,topRight);
				cumEnElem.cumEnergy = tmin + m_enMap.Pixel(x,y,0);
				cumEnElem.yPrevious = y - 1;
				if(isEqual(tmin,topLeft))
				{
					cumEnElem.xPrevious = x - 1;
				}
				else if (isEqual(tmin,top))
				{
					cumEnElem.xPrevious = x;
				}
				else if (isEqual(tmin, topRight))
				{
					cumEnElem.xPrevious = x + 1;
				}
				cumEnVec.push_back(cumEnElem);
			}
			if(y == sh.height - 1)
			{
				m_lastRow.push_back(make_pair(cumEnElem.cumEnergy, x));
			}
		}
		m_VCumEnMap.push_back(cumEnVec);
	}
}

void CContentImResize::EnergyGradient(CFloatImage& Hsrc, CFloatImage& Vsrc)
{
	CShape sh = Hsrc.Shape();
	m_enMap.ReAllocate(sh);
	Loop_Image(x,y,sh.width,sh.height)
	{
		float t1 = Hsrc.Pixel(x,y,0), t2 = Vsrc.Pixel(x,y,0);
		m_enMap.Pixel(x,y,0) = abs(t1) + abs(t2);
	}
}

void CContentImResize::Convert2GrayFloat(CFloatImage& image, CFloatImage& grayFloatImage)
{
	CShape sh = image.Shape();
	Loop_Image(x,y,sh.width,sh.height)	
	{
		if(sh.nBands < 3)
		{
			grayFloatImage.Pixel(x,y,0) = image.Pixel(x,y,0);
		}
		else
		{
			float R, G, B;
			R = image.Pixel(x,y,0);
			G = image.Pixel(x,y,1);
			B = image.Pixel(x,y,2);
			grayFloatImage.Pixel(x,y,0) = 0.2989f * R + 0.5870f * G + 0.1140f * B; 
		}
	}	
}

void CContentImResize::MaskProcessing(CFloatImage& src, CFloatImage& dst, float *mask, int mkW, int mkH)
{
	if(src.Shape().nBands != dst.Shape().nBands)
	{
		cout<<"src and dst are supposed to have the same bands!!"<<endl;
		exit(0);
	}

	CShape sh = src.Shape();
	#define mask(x,y) mask[(y) * mkW + (x)]
	
	int dx = mkW / 2, dy = mkH / 2;
	Loop_Image(x,y,sh.width,sh.height)		
	{
		for(int c = 0; c < sh.nBands; c++)
		{
			float sum = 0.f, sumKer = 0.f;
			for(int m = -dy; m <= dy; m++)
			for(int n = -dx; n <= dx; n++)
			{
				if((x + n < 0) || (x + n > sh.width - 1) || (y + m < 0) || (y + m > sh.height - 1))
				{
					continue;
				}
				sum += src.Pixel(x + n, y + m, c) * mask(n + dx, m + dy);
				sumKer += mask(n + dx, m + dy);
			}
			dst.Pixel(x,y,c) = sum / (isZero(sumKer) ? 1.0f : sumKer);
		}
	}
}

void CContentImResize::SaveFloatImage(CFloatImage& image, const string& name, bool needNorm /* = false*/)
{
	CByteImage byteImg;
	convertToByteImage(image,byteImg,needNorm);
	writeByteImageToBMP(byteImg,name.c_str());
}

void CContentImResize::SaveImageWithSeams(CFloatImage& src, const string& name, const SeamSet& seamSet)
{
	CShape sh = src.Shape();
	CFloatImage image(sh.width, sh.height, 3);
	
	Loop_Image(x,y,sh.width,sh.height)
	for(int c = 0; c < 3; c++)
	{
		float pixelVal;
		if(sh.nBands < 3)
			pixelVal = src.Pixel(x,y,0);
		else
			pixelVal = src.Pixel(x,y,c);
		image.Pixel(x,y,c) = pixelVal;
	}

	for(SeamSet::const_iterator iter = seamSet.begin(); iter != seamSet.end(); iter++)
		for(Seam::const_iterator seamIt = iter->begin(); seamIt != iter->end(); seamIt++)
		{
			int x = seamIt->first, y = seamIt->second;
			image.Pixel(x,y,0) = 1.0f;
			image.Pixel(x,y,1) = 0.0f;
			image.Pixel(x,y,2) = 0.0f;
		}

	SaveFloatImage(image,name);
}