///////////////////////////////////////////////////////////////////////////////
// Bryce Mercado
// CS370 Digital Image Processing 
// Homework #8 
// 03/08/06
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <assert.h>
#include "Thinning.h"
#include "StatisticsEnhancement.h"	// for DetermineBoundaries()

///////////////////////////////////////////////////////////////////////////////
// Thinning function:
//		Write C/C++ program to read image (thinme.bmp as an example), perform 
// thinning algorithm as specified in 11.1.5. Save the result as bitmap image. 
//
//	Params: 
//		CS230Bitmap & currBitmap
//			A reference to the bitmap that's being thinned.
//		string &filename
//			A string containing the name of the image file.
///////////////////////////////////////////////////////////////////////////////
void Thinning( CS230Bitmap &currBitmap, std::string &filename )
{
	// create buffer bitmap
	CS230Bitmap newBitmap;
	// Initialize newBitmap to same size as currBitmap, but
	// with every pixel as (0,0,0).
	newBitmap.SetSize( currBitmap.GetWidth(),
					   currBitmap.GetHeight(),
					   currBitmap.GetChannels() );
	// Do thinning
	ApplyThinning(currBitmap, newBitmap);

	// save bitmap
	// Add GlobalThresholded to filename for the name of the new bitmap
	filename.insert(filename.length()-4,"Thinned");

	if( SaveBMPFile(filename.c_str(),&currBitmap) )
	{
		std::cout<<"Thinned bitmap saved as file "<<filename<<"\n";
	}
	else
	{
		std::cout<<"Bitmap failed to save. Oops!\n";
	}
}

///////////////////////////////////////////////////////////////////////////////
// ApplyThinning function:
//		Assumes that the current bitmap given is comprised of binary regions
//	where backgrounds have a value of 255 and objects have a value of 0. It
//	then applies this thinning algorithm:
//	Given this arrangement of pixels: P9 P2 P3
//									  P8 P1 P4
//									  P7 P6 P5
//	Step 1:
//	--------------------------------------------------------------
//	Pixel P1 is to be marked for deletion if (a) 2 <= N(P1) <= 6
//											 (b) T(P1) = 1
//											 (c) P2*P4*P6 = 0
//											 (d) P4*P6*P8 = 0
//	Where N(P1) is the number of nonzero neighbors of P1 and T(P1) is the
//  number of 0-1 transitions in the sequence P2, P3,...,P8,P9,P2.
//
//  Step 2:
//  --------------------------------------------------------------
//	Delete pixels marked for deletion.
//
//	Step 3:
//  --------------------------------------------------------------
//  Similar to Step 1. Conditions (a) and (b) are the same, but
//	now (c) P2*P4*P8 = 0
//		(d) P2*P6*P8 = 0
//
//	Step 4:  
//  --------------------------------------------------------------
//	Delete pixels marked for deletion.
//
//  Repeat these four steps until no more pixels are flagged for deletion.
//
//	Params: 
//		CS230Bitmap & currBitmap
//			A reference to the bitmap that's being thinned.
//		CS230Bitmap & markedBitmap
//			This bitmap just holds the info for whether a pixel is marked
//		to be deleted or not.
///////////////////////////////////////////////////////////////////////////////
void ApplyThinning(CS230Bitmap &currBitmap, CS230Bitmap &markedBitmap)
{
	// Flag to check whether any pixel was marked for deletion
	bool wasMarked = true;

	// Apply Steps 1-4 to each pixel in the bitmap. 
	// Do so until no value was marked for deletion
	while( wasMarked )
	{
		wasMarked = false;
		// Step 1: Mark pixels for deletion
		ThinPass(currBitmap,markedBitmap,wasMarked,pass1);
		// Step 2: Delete any marked pixels
		if( wasMarked == true )
		{
			DeletePixels(currBitmap,markedBitmap);
		}
		// Step 3: Thin again, with different conditions
		ThinPass(currBitmap,markedBitmap,wasMarked,pass2);
		// Step 4: Delete any more pixels marked
		if( wasMarked == true )
		{
			DeletePixels(currBitmap,markedBitmap);
		}
	}
}

///////////////////////////////////////////////////////////////////////////////
// ThinPass function:
//		Performs Step 1 or 3 of the thinning algorithm on the current bitmap.
//	Stores deletion flags in marked. Sets wasMarked to true if a pixel was
//	marked for deletion.
//		Assumes marked has already been resized to the same dimensions as
//	currBitmap and been zeroed out.
//
//	Step 1:
//	--------------------------------------------------------------
//	Pixel P1 is to be marked for deletion if (a) 2 <= N(P1) <= 6
//											 (b) T(P1) = 1
//											 (c) P2*P4*P6 = 0
//											 (d) P4*P6*P8 = 0
//
//	Step 3:
//	--------------------------------------------------------------
//	Pixel P1 is to be marked for deletion if (a) 2 <= N(P1) <= 6
//											 (b) T(P1) = 1
//											 (c') P2*P4*P8 = 0
//											 (d') P2*P6*P8 = 0
//
//	Where N(P1) is the number of nonzero neighbors of P1 and T(P1) is the
//  number of 0-1 transitions in the sequence P2, P3,...,P8,P9,P2.
//
//	Params: 
//		CS230Bitmap & currBitmap
//			A reference to the bitmap that's being thinned.
//		CS230Bitmap & marked
//			A bitmap to hold the deletion flags.
//		bool  &wasMarked
//			A bool which is set to true if a pixel gets marked for deletion
//			and is left alone if not.
//		int pass
//			Determines which of the sets of conditions to use. Uses an enum
//			defined in the header file: pass1 and pass2
///////////////////////////////////////////////////////////////////////////////
void ThinPass( CS230Bitmap &currBitmap, CS230Bitmap &marked, 
			   bool &wasMarked, int pass)
{
	// This only handles two values of pass
	assert(pass == pass1 || pass == pass2);

	// Array to hold values of the nine pixels
	// So as not to confuse myself, I'm not using P[0] and setting it's value
	// to an obviously incorrect value.
	int P[10] = {-1000};

	// values for traversing the bitmap
	const int channels	= currBitmap.GetChannels();
    const int width		= currBitmap.GetWidth();
    const int height	= currBitmap.GetHeight();

	// go through the bitmap
    for (int y = 0; y < height; ++y)
    {
		// get starting pixel of the bitmap
		uint8_t* markPixel = marked.GetLinePtr(y);

		// go over the width of the bitmap
        for (int x = 0; x < width; ++x)
        {
			FindPixelValues(currBitmap,P,x,y);

			// if there is an object at this pixel, then do conditions
			if( P[1] == 1 )
			{
				// Made a temp var. for debugging purposes
				int np = N(P);
				// Condition (a)
				if( np >= 2 && np <= 6 )
				{
					// Made a temp var. for debugging purposes
					int tp = T(P);
					// Condition (b)
					if( tp == 1 )
					{
						// if pass1 use (c) and (d)
						if( pass == pass1 )
						{
							if( (P[4] == 0 || P[6] == 0 ) ||
								(P[2] == 0 && P[8] == 0 ) )
							{
								// mark pixel for deletion
								// Don't need to set each color value, but 
								// doing it anyway to be on the safe side
								markPixel[kRedOffset] = deleteThis;
								markPixel[kGreenOffset] = deleteThis;
								markPixel[kBlueOffset] = deleteThis;
								// notify loop, pixel was marked for deletion
								wasMarked = true;
							}
						}
						// if pass2 use (c') and (d')
						else if( pass == pass2 )
						{
							if( (P[2] == 0 || P[8] == 0) ||
								(P[4] == 0 && P[6] == 0) )
							{
								// mark pixel for deletion
								markPixel[kRedOffset] = deleteThis;
								markPixel[kGreenOffset] = deleteThis;
								markPixel[kBlueOffset] = deleteThis;
								// notify loop, pixel was marked for deletion
								wasMarked = true;
							}
						}
					}// Condition (b)
				}// Condition (a)
			}
			// increment pointer to next pixel
			markPixel += channels;
        }
	}
}


///////////////////////////////////////////////////////////////////////////////
// FindPixelValues function:
//		Find the values of the pixels including and surrounding the pixel at
//	(xPos,yPos) and stores them in the array P. It considers background pixels
//	to be of value 255 and stores them as 0. Pixel values of 0 are object and
//	are stored as 1.
//		*NOTE* - P has 10 elements and P[0] is never used.
//		This is the order in which they're stored:
//		P[9] P[2] P[3]
//		P[8] P[1] P[4]
//		P[7] P[6] P[5]
//
//	Params: 
//		CS230Bitmap & currBitmap
//			A reference to the bitmap that's being thinned.
//		int P[]
//			An array that holds the values of the pixels surrounding the pixel
//			at (xPos,yPos)
//		int xPos
//			The x position of the pixel in question.
//		int yPos
//			The y position of the pixel in question.
///////////////////////////////////////////////////////////////////////////////
void FindPixelValues( CS230Bitmap &currBitmap, int P[], int xPos, int yPos )
{
	// This function should never get called on a pixel that is past the
	// bounds of the bitmap.
	assert( xPos < currBitmap.GetWidth() );
	assert( yPos < currBitmap.GetHeight() );

    const int width		= currBitmap.GetWidth();
    const int height	= currBitmap.GetHeight();
	const int channels	= currBitmap.GetChannels();

	// Zero out P (but not P[0]. it's not used)
	for( int i = 1; i < 10; ++i )
	{
		P[i] = background;
	}
	
	// Used for getting pixel values from the bitmap.
	uint8_t *pixel;

	// if the x position of the pixel is along the left boundary of the image
	if( xPos == 0 )
	{
		// if the y position is at the top of the image,
		// only set X   X   X
		//			X  P1, P4,
		//			X  P6, P5
		if( yPos == 0 )
		{
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P4
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[4] = object;
			// P6
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[6] = object;
			// P5
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[5] = object;
		}
		// if the y position is at the bottom of the image,
		// only set X  P2  P3
		//			X  P1, P4,
		//			X   X   X
		else if( yPos == (height - 1) )
		{
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P4
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[4] = object;
			// P2
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[2] = object;
			// P3
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[3] = object;
		}
		// Otherwise, set:	X  P2  P3
		//					X  P1, P4
		//					X  P6, P5
		else
		{
			// P2
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[2] = object;
			// P3
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[3] = object;

			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P4
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[4] = object;

			// P6
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[6] = object;
			// P5
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[5] = object;			
		}
	}
	// if the x position of the pixel is along the right side of the image
	else if( xPos == (width - 1) )
	{
		// if the y position is at the top of the image,
		// only set X    X   X
		//			P8  P1,  X
		//			P7  P6,  X
		if( yPos == 0 )
		{
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P8
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[8] = object;
			// P6
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[6] = object;
			// P7
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[7] = object;
		}
		// if the y position is at the bottom of the image,
		// only set P9  P2   X
		//			P8  P1,  X
		//			 X   X   X
		else if( yPos == (height-1) )
		{
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P8
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[8] = object;
			// P2
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[2] = object;
			// P9
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[9] = object;
		}
		// Otherwise, set: P9  P2  X
		//				   P8  P1  X
		//				   P7  P6  X
		else
		{
			// P2
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[2] = object;
			// P9
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[9] = object;

			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P8
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[8] = object;

			// P6
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[6] = object;
			// P7
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[7] = object;
		}
	}
	// If x position not at either side, now check top and bottom
	else
	{
		// if y at top of the image,
		// only set X    X   X
		//			P8  P1,  P4
		//			P7  P6,  P5
		if( yPos == 0 )
		{
			// P8
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[8] = object;
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P4
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[4] = object;
			// P7
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[7] = object;
			// P6
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[6] = object;
			// P5
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[5] = object;
		}
		// if y at top of the image,
		// only set P9  P2   P3
		//			P8  P1,  P4
		//			 X   X    X
		else if( yPos == (height-1) )
		{
			// P9
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[9] = object;
			// P2
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[2] = object;
			// P3
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[3] = object;
			// P8
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[8] = object;
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P4
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[4] = object;
		}
		// Otherwise, set them all
		//          P9  P2   P3
		//			P8  P1,  P4
		//			P7  P6,  P5
		else
		{
			// P9
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[9] = object;
			// P2
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[2] = object;
			// P3
			pixel = currBitmap.GetLinePtr(yPos-1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[3] = object;
			// P8
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[8] = object;
			// P1
			pixel = currBitmap.GetLinePtr(yPos) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[1] = object;
			// P4
			pixel = currBitmap.GetLinePtr(yPos) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[4] = object;
			// P7
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos-1);
			if( pixel[kRedOffset] == black )
				P[7] = object;
			// P6
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*xPos;
			if( pixel[kRedOffset] == black )
				P[6] = object;
			// P5
			pixel = currBitmap.GetLinePtr(yPos+1) + channels*(xPos+1);
			if( pixel[kRedOffset] == black )
				P[5] = object;
		}
	}
}

///////////////////////////////////////////////////////////////////////////////
// N function:
//		Finds the number of nonzero neighbors of P1.
//		That is, P2 + P3 + ... + P9.
//		*NOTE* - P has 10 elements and P[0] is never used.
//		This is the order in which they're stored:
//		P[9] P[2] P[3]
//		P[8] P[1] P[4]
//		P[7] P[6] P[5]
//
//	Params: 
//		int P[]
//			An array that holds the values of nine pixels 
///////////////////////////////////////////////////////////////////////////////
int N( int P[] )
{
	int sum = 0;
	for( int i = 2; i < 10; ++i )
	{
		sum += P[i];
	}
	return sum;
}

///////////////////////////////////////////////////////////////////////////////
// T function:
//		Returns the number of 0-1 transitions in the sequence P2,P3,..,P9,P2
//		*NOTE* - P has 10 elements and P[0] is never used.
//		This is the order in which they're stored:
//		P[9] P[2] P[3]
//		P[8] P[1] P[4]
//		P[7] P[6] P[5]
//
//	Params: 
//		int P[]
//			An array that holds the values of nine pixels 
///////////////////////////////////////////////////////////////////////////////
int T( int P[] )
{
	int count = 0;

	for( int i = 2; i < 10; ++i )
	{
		int currPixel = P[i];
		int nextPixel;
		// Sequence wraps from P9 to P2
		if( i == 9 )
			nextPixel = P[2];
		else
			nextPixel = P[i+1];

		// only count transitions from 0 to 1
		if( currPixel == background &&
			nextPixel == object )
		{
			count++;
		}
	}

	return count;
}

///////////////////////////////////////////////////////////////////////////////
// FindPixelValues function:
//		Goes through the pixels of both bitmaps. If the value of the pixel in
//	marked is DeleteThis, the corresponding pixel in the current bitmap is set
//	to white.
//
//	Params: 
//		CS230Bitmap & currBitmap
//			A reference to the bitmap that's having the median filter applied.
//		CS230Bitmap & marked
//			A reference to the bitmap that's having the median filter applied.
///////////////////////////////////////////////////////////////////////////////
void DeletePixels( CS230Bitmap &currBitmap, CS230Bitmap &marked )
{
		// values for traversing the bitmap
	const int channels	= currBitmap.GetChannels();
    const int width		= currBitmap.GetWidth();
    const int height	= currBitmap.GetHeight();

	// go through the bitmap
    for (int y = 0; y < height; ++y)
    {
		// get starting pixel of the bitmap
		uint8_t* currPixel = currBitmap.GetLinePtr(y);
		uint8_t* markPixel = marked.GetLinePtr(y);

		// go over the width of the bitmap
        for (int x = 0; x < width; ++x)
        {
			// if the flag in mark is set, 
			// set pixel value of currBitmap to white
			if( markPixel[kRedOffset] == deleteThis )
			{
				currPixel[kRedOffset] = white;
				currPixel[kGreenOffset] = white;
				currPixel[kBlueOffset] = white;
			}

			// increment pointer to next pixel
			currPixel += channels;
			markPixel += channels;
        }
	}
}