/*
	SeamCarving.as
	Lee Felarca
	http://www.zeropointnine.com/blog
	9-1-2007
	v0.8
	
	Source code licensed under a Creative Commons Attribution 3.0 License.
	http://creativecommons.org/licenses/by/3.0/
	Some Rights Reserved.

	Note: Data-structure-wise, a "seam" here is defined as an array of 8-connected Points
*/

package
{
	import flash.display.BitmapData;
	import flash.geom.Point;
	
	public class SeamCarving
	{
		public static function getBrightness($c:uint) : uint
		{	
			var r:uint = $c >> 16;
			var g:uint = $c >> 8 & 0xff;
			var b:uint = $c & 0xff;
			
			return r + g + b; 
			
			// Note, range of returned value is 0 to 765, not 0 to 255!
			// (Retains precision while avoiding use of Number)
		}
		
		public static function getAverage($c1:uint, $c2:uint) : uint
		{
			// Returns the averaged color of two color values
			
			var r1:uint = $c1 >> 16;
			var g1:uint = $c1 >> 8 & 0xff;
			var b1:uint = $c1 & 0xff;

			var r2:uint = $c2 >> 16;
			var g2:uint = $c2 >> 8 & 0xff;
			var b2:uint = $c2 & 0xff;
			
			var r3:uint = int( (r1+r2)/2 );
			var g3:uint = int( (g1+g2)/2 );
			var b3:uint = int( (b1+b2)/2 );
			
			return (r3 << 16) | (g3 << 8) | b3;
		}

		public static function getEnergy($b:BitmapData, $x:int, $y:int) : uint
		{
			// Return the 'energy' of a given pixel in an image
			
			// 5 1 7
			// 3 0 4
			// 8 2 6
			
			var g0:int=0, g1:int=-1, g2:int=-1, g3:int=-1, g4:int=-1, g5:int=-1, g6:int=-1, g7:int=-1, g8:int=-1;
			var num:int = 8;
			var sum:uint = 0;
			
			g0 = getBrightness($b.getPixel($x, $y) );
			
			if ($x > 0) 							
				g3 = getBrightness( $b.getPixel($x-1,$y) );
			else
				num--;
			if ($x < $b.width-2)					
				g4 = getBrightness( $b.getPixel($x+1,$y) );
			else
				num--;
			if ($y > 0) 							
				g1 = getBrightness( $b.getPixel($x,$y-1) );
			else
				num--;
			if ($y < $b.height-2)					
				g2 = getBrightness( $b.getPixel($x,$y+1) );
			else
				num--;
			if ($x > 0 && $y > 0)
				g5 = getBrightness( $b.getPixel($x-1,$y-1) );
			else
				num--;
			if ($x > 0 && $y < $b.height-2)
				g8 = getBrightness( $b.getPixel($x-1,$y+1) );
			else
				num--;
			if ($x < $b.width-2 && $y > 0)
				g7 = getBrightness( $b.getPixel($x+1,$y-1) );
			else
				num--;
			if ($x < $b.width-2 && $y < $b.height-2)
				g6 = getBrightness( $b.getPixel($x+1,$y+1) );
			else
				num--;
			
			if (g1 != -1) sum += ((g0-g1)*(g0-g1));
			if (g2 != -1) sum += ((g0-g2)*(g0-g2));
			if (g3 != -1) sum += ((g0-g3)*(g0-g3));
			if (g4 != -1) sum += ((g0-g4)*(g0-g4));
			if (g5 != -1) sum += ((g0-g5)*(g0-g5));
			if (g6 != -1) sum += ((g0-g6)*(g0-g6));
			if (g7 != -1) sum += ((g0-g7)*(g0-g7));
			if (g8 != -1) sum += ((g0-g8)*(g0-g8));
												
			return int( sum/num );
		}
		
		public static function makeGradientMagnitudeMap($b:BitmapData) : BitmapData
		{
			// Creates gradient magnitude map whose values are stored in a BitmapData
			
			var b:BitmapData = new BitmapData($b.width, $b.height);
			var energy:uint = 0;
			
			for (var y:int = 0; y < $b.height; y++) {
				for (var x:int = 0; x < $b.width; x++) {
					energy = getEnergy($b, x,y);
					b.setPixel( x,y, energy );
				}
			}
			
			return b
		}
		

		public static function getSeamSum($originX:int, $originY:int, $b:BitmapData):uint
		{
			// pseudo-overloading
			return getSeam( $originX, $originY, $b, true );
		}
		
		public static function getSeam($originX:int, $originY:int, $b:BitmapData, $sumOnly:Boolean=false):*
		{
			// Returns an array of x/y values which make up the horizontal seam that begins at a given point
			// When $sumOnly = true, returns the sum of gradient magnitudes of the pixels in the seam 

			var seam:Array = new Array();
			var sum:int, y:int, yMinus1:uint, yAt:uint, yPlus1:uint;
			
			if (!$sumOnly) seam.push( {x:$originX, y:$originY} );
			
			// Parse to the right
			y = $originY;
			for (var x1:int = $originX+1; x1 < $b.width; x1++) {
				findMin(x1);
			}
			
			// Parse to the left
			y = $originY;
			for (var x2:int = $originX-1; x2 >= 0; x2--) {
				findMin(x2);
			}
			
			if ($sumOnly) return sum; else return seam;
			
			// ----------------------------
			
			function findMin(x:int):void
			{
				// updates local variables y and sum, and adds to the seam array
				
				if (y > 0)					
					yMinus1 = $b.getPixel(x,y-1);
				else						
					yMinus1 = 0xFFFFFFFF;
				
				yAt = $b.getPixel(x,y);
				
				if (y < $b.height-2)		
					yPlus1 = $b.getPixel(x,y+1);
				else						
					yPlus1 = 0xFFFFFFFF;
				
				// find lowest:				
				if (yAt <= yMinus1 && yAt <= yPlus1) {
					sum += yAt;
					y = y;
				}
				else if (yMinus1 <= yAt && yMinus1 <= yPlus1) {
					sum += yMinus1;
					y = y - 1;
				}
				else { // yPlus1 is the lowest
					sum += yPlus1;
					y = y + 1;
				}
				
				if (!$sumOnly) seam.push( new Point(x, y) );
			}
		}
		
		public static function getMinSeam($b:BitmapData, $yStep:uint=1, $xStep:uint=75):Array
		{
			// Returns the seam whose pixels have the lowest cumulative gradient magnitude
			
			// $yStep and $xStep determine how comprehensive (and time consuming) to search will be.
			// Don't cheat on the $yStep (keep it at 1), but cheat a lot on the $xStep (maybe 10, 20, or 100...)
			
			var lowestX:uint, lowestY:uint, lowestSum:uint = 0xFFFFFFFF;
			
			for (var y:int = 0; y < $b.height; y += $yStep) {
				for (var x:int = 0; x < $b.width; x += $xStep) {
					var sum:int = getSeamSum(x + y % $xStep, y, $b);
					if (sum < lowestSum) {
						lowestSum = sum;
						lowestX = x;
						lowestY = y;
					}
				}
			}
			var a:Array = getSeam(lowestX, lowestY, $b);
			return a;
		}
		
		public static function shrinkImage($b:BitmapData, $seam:Array):BitmapData
		{
			// 'Carves' a seam out of an image, resulting in an image which is 1px shorter
			
			var b1:BitmapData = new BitmapData($b.width, $b.height);
			b1.draw($b);
			
			for (var i:int = 0; i < $seam.length; i++) {
				var x:int = $seam[i].x;
				var y:int = $seam[i].y;
				var ht:int = b1.height - y - 1;
				
				// ! This could be quicker with BitmapData.draw()
				for (var h:int = 0; h < ht; h++)  {
					var col:uint = b1.getPixel(x,y+h+1);
					b1.setPixel( x, y+h, col);
				}
			}
			var b2:BitmapData = new BitmapData(b1.width, b1.height-1);
			b2.draw(b1);
			return b2;
		}


		public static function expandImage($b:BitmapData, $seam:Array):BitmapData
		{
			// Expands image by 1px at the seam
			
			var b1:BitmapData = new BitmapData($b.width, $b.height+1);
			b1.draw($b);
			
			var x:uint, y1:uint, y2:uint, h:uint, y:uint;
			for (var i:int = 0; i < $seam.length; i++) {
				x = $seam[i].x;
				y1 = $seam[i].y + 1;
				y2 = b1.height - 1;
				
				for (h = y2; h >= y1; h--) {
					b1.setPixel( x, h,  b1.getPixel(x,h-1) );
				}
				
				y = $seam[i].y;
				b1.setPixel(x, y, getAverage( b1.getPixel(x,y-1), b1.getPixel(x,y) ) );
				b1.setPixel(x, y, getAverage( b1.getPixel(x,y+1), b1.getPixel(x,y+2) ) );
			}			
			return b1;
		}
	}
}