package  
{

	/*
	 * seam carving original java version by pseudocode
	 * 
	 * http://www.developpez.net/forums/d418823/autres-langages/algorithmes/contribuez/image-seam-carving/
	 * 
	 */
	import flash.display.*;
	import flash.filters.*;
	import flash.geom.*;
	
	public class Carving
	{
		//energy map refreshment rate 
		static public var refreshRate:int = 10;
		
		//filter type
		static public var filterType:String = 'PREWITT';
		
		
		//threshold value 
  		static public var threshold:Number = -1;
		
		//filtre blur (optionnal)
  		static public var blur:BlurFilter = new BlurFilter( 4, 4, 3 );
		
		
		// image current dimension
		public var height:int =0, width:int=0;
	 
		//bitmapDatas:
		//reference
		private var bd:BitmapData;
		//clone
		private var original:BitmapData;
		
		//energy computation
		private var bmpd:BitmapData;
		public var out:BitmapData;
		
		// input image 
		private var input:Array;
		// energy map
		private var energy:Array;
		
		//chemins possibles en XY
		private var hpath:Array;
		private var vpath:Array;
		
		//bornes pour redessiner seulement une partie du bitmapData
		private var cropX:int;
		private var cropY:int;
		private var cropW:int;
		private var cropH:int;
		
		private var ticker:int;
		
		public function Carving ( img:BitmapData )
		{
			
			if( img != null ) init( img );
			
		}
		
		/*
		 * initialises the class
		 * @param img:BitmapData the image to carve 
		 */
		public function init( img:BitmapData ):void
		{
			
			// initialize arrays
			cropX = 0;
			cropY = 0;
			cropW = width = img.width;
			cropH = height 	= img.height;
			
			bd = img;
			original = img.clone();
			
		
			bmpd = img.clone();
			out = img.clone();
			
			input = [];
			energy = [];
			
			hpath = [];
			vpath = [];
			
			//collecte les infos couleur
			computeImage( bd );
			
			//collecte les intensites
			computeEnergyMap( bd );
			
		}
		
		/*
		 * scans the bitmapdata according to the current width / height and stores its values into a 2D array
		 * @param bd:BitmapData the BitmapData to scane
		 */
		private function computeImage( img:BitmapData ):void
		{
			
			var x:int;
			var y:int;
			
			img.lock();
			for ( x=0; x<width; x++)
			{
				input.push( new Array( height ) );
				energy.push( new Array( height ) );
				
				for ( y = 0; y < height; y++)
				{
					input[ x ][ y ] = img.getPixel(x, y);
				}
			}
			
		}
		
		/*
		 * draws the image being processed to a given BitmapData
		 * @param bmpd:BitmapData the BitmapData to draw to.
		*/
		public function getImage( bmpd:BitmapData ):void
		{
			var x:int;
			var y:int;
			bmpd.lock();
			
			for ( x=0; x < width; x++)
			{
				for ( y = 0; y < height; y++)
				{
					bmpd.setPixel( x, y, input[x][y] );
				}
			}
			bmpd.unlock();
		}
		
		/*
		 * computes the energy map of a given picture. takes the original bitmapData if nothing is passed as a parameter
		 * @param img:BitmapData the image to compute the energy map of
		 */
		public function computeEnergyMap( img:BitmapData = null ):void
		{
			
			img = ( img == null ) ? original : img;
			
			switch ( filterType )
			{
				
				case 'PREWITT':
				findPrewittEdges( img );
				//thresholding
				if( threshold != -1 )
				{
					out.threshold( out, out.rect, new Point( 0, 0 ) , '>=', threshold, 0xFFFFFFFF );
					out.threshold( out, out.rect, new Point( 0, 0 ) , '!=', 0xFFFFFFFF, 0xFF000000 );
				}
				//noise reduction: optionnal but it can help 
				//out.applyFilter(out, out.rect, new Point( 0,0 ),blur);
				break;
			
				case 'SOBEL':
				findSobelEdges( img );
				//noise reduction: optionnal but it can help
				//out.applyFilter(out, out.rect, new Point( 0,0 ),blur);
				break;
				
			}
			
			
			var x:int;
			var y:int;
			var r:int;
			var g:int;
			var b:int;
			var c:int;
			
			
			// computes the luminance of each pixel of the energy map
			out.lock();
			for ( x=0; x<out.width; x++)
			{
				for ( y = 0; y < out.height; y++)
				{
					
					c = out.getPixel( x, y );
					r = ( c >>16 ) & 0xFF;
					g = ( c >> 8 ) & 0xFF;
					b = c & 0xFF;
					energy[ x ][ y ] = ( ( 299*r + 587*g + 114*b )/1000 );  
					
				}
			}
			out.unlock();
		}
		
		/*
		 * applies a Sobel edge detector to compute the energy map
		 * fast but not necessarily accurate( 2 * 3*3 kernels )
		 * @param img:BitmapData the image to compute the energy map of
		 */
		private function findSobelEdges( img:BitmapData ):void
		{
			
			
			bmpd.fillRect( bmpd.rect, 0x00000000 );
			out.fillRect( out.rect, 0x00000000 );
			
			var rect:Rectangle = bmpd.rect;
			var pt:Point = new Point( 0,0 );
			var matrix:Array;

			var filter:ConvolutionFilter;
			var bias:Number = 0;
			var div:Number = 4;
			var preserveAlpha:Boolean = true;
			
	        var matrixCols:Number = 3;
	        var matrixRows:Number = 3;
				
			matrix = [ 
					 -1,-2,-1,
					  0, 0, 0,
					  1, 2, 1
					  ];
			
	        filter = new ConvolutionFilter(matrixCols, matrixRows, matrix, div, bias, preserveAlpha );
		   	bmpd.applyFilter( img, rect, pt, filter );
	        out.draw( bmpd );
			matrix = [ 
					 -1, 0,1,
					 -2, 0,2,
					 -1, 0,1
					  ];
					  
			filter = new ConvolutionFilter(matrixCols, matrixRows, matrix, div, bias, preserveAlpha);
		   	bmpd.applyFilter( img, rect, pt, filter );
	        out.draw( bmpd, null, null, "add" );
			
			
		}
		
		/*
		 * applies a Prewitt edge detector to compute the energy map
		 * more accurate yet more expensive ( 4 * 3*3 kernels )
		 * @param img:BitmapData the image to compute the energy map of
		*/
		private function findPrewittEdges( img:BitmapData ):void
		{
			
			var rect:Rectangle = bmpd.rect;
			var pt:Point = new Point( 0,0 );
			var matrix:Array;
			
			
			bmpd.fillRect( rect, 0x00000000 );
			out.fillRect( rect, 0x00000000 );
			
			
			var mode:String = BlendMode.ADD;

			var filter:ConvolutionFilter;
			var bias:Number = 0;
			var div:Number = 3;
			var preserveAlpha:Boolean = true;
			
	        var matrixCols:Number = 3;
	        var matrixRows:Number = 3;
				
			matrix = [ 
					  1, 0, -1,
					  1, 0, -1,
					  1, 0, -1
					  ];
			
	        filter = new ConvolutionFilter(matrixCols, matrixRows, matrix, div, bias, preserveAlpha );
	        bmpd.applyFilter( img, rect, pt, filter );
	        out.draw( bmpd );
	        
			
			matrix = [ 
					  1,  1,  0,
					  1,  0, -1,
					  0, -1, -1
					  ];
					  
			filter = new ConvolutionFilter(matrixCols, matrixRows, matrix, div, bias, preserveAlpha);
		   	bmpd.applyFilter( img, rect, pt, filter );
	        out.draw( bmpd, null, null, mode );
			
			matrix = [ 
					   1,  1,  1,
					   0,  0,  0,
					  -1, -1, -1
					  ];
					  
			filter = new ConvolutionFilter(matrixCols, matrixRows, matrix, div, bias, preserveAlpha);
		   	bmpd.applyFilter( img, rect, pt, filter );
	        out.draw( bmpd, null, null, mode );
			
			matrix = [ 
					   1,  1,  1,
					  -1,  0,  1,
					  -1, -1,  0
					  ];
					  
			filter = new ConvolutionFilter(matrixCols, matrixRows, matrix, div, bias, preserveAlpha);
		   	bmpd.applyFilter( img, rect, pt, filter );
	        out.draw( bmpd, null, null, mode );
			
			
		}
		
		/*
		 * draws the energy map to a given BitmapData
		 * @param bmpd:BitmapData the BitmapData to draw to.
		*/
		public function getEnergyMap( bmpd:BitmapData ):void//BitmapData
		{
			var x:int;
			var y:int;
			bmpd.lock();
			for ( x=0; x < width; x++)
			{
				for (y=0; y < height; y++)
				{
					bmpd.setPixel(x, y, energy[x][y] );
				}
			}
			bmpd.unlock();
		}
		
		/*
		 * computes a horizontal seam to remove.
		*/
		private function computeHorizontalPath():void
		{
			
			//HORIZONTAL
			hpath = [];
			var end:Array =[];
			var i:int;
			var j:int;
		
			var myE:int;
			var up:int;
			var left:int;
			var down:int;
			
			var _y:int;
			
			var minE:Number = Number.MAX_VALUE;
			var curE:Number = 0;
			var E:int;

			for (i = 1; i < height - 1; i++ )
			{
			
				_y = i;
				
				j = 0;
				myE = 0;
				end = [];
				while( j++ < width -1 )
				{
					
					curE = energy[ j ][ _y ];
					myE += curE; 
					
					if( myE < minE )
					{
						E = curE;
						
						//checks which pixel has the lowest energy value
						up = energy[ j ][ _y-1 ];
						left = energy[ j ][ _y ];
						down = energy[ j ][ _y+1 ];
						
						curE = E + left;
						
						if( up < left && down > up )
						{
							_y = _y-1;
							curE = E + up;
						}
						
						if( down < left  && up > down  )
						{
							_y = _y+1;
							curE = E + down;
						}
						
						//bounds it inside the image
						_y = ( _y < 1) ? 1  :( _y > height-2 ) ? ( height-2 ) : _y;
						
						end.push( _y );
						
						myE += curE;
						
					}
				}
				if( myE < minE )
				{
					
					minE = myE;
					hpath = end.concat();
					
				}
			}
			
		}
		
		/*
		 * computes a verticla seam to remove.
		*/
		private function computeVerticalPath():void
		{
			
			//VERTICAL
			vpath = [];
			var end:Array =[];
			var i:int;
			var j:int;
		
			var myE:int;
			var left:int;
			var down:int;
			var right:int;
			
			var _x:int;
			
			var minE:Number = Number.MAX_VALUE;
			var curE:Number = 0;
			var E:int;
			
			minE = Number.MAX_VALUE;
				
			for (i = 1; i < width - 1; i++ )
			{
			
				_x = i;
				j = 0;
				myE = 0;
				end = [];
				while( j++ < height -1)
				{
				
					curE = energy[ _x ][ j ];
					myE += curE; 
						
					if( myE < minE )
					{
						E = curE;
						
						//checks which pixel has the lowest energy value
						left 	= energy[ _x - 1 ][ j ];
						down 	= energy[   _x   ][ j ];
						right 	= energy[ _x + 1 ][ j ];
						
						curE = E + down;
						
						if( left < down && right > left )
						{
							_x = _x-1;
							curE = E + left;
						}
						
						if( right < down  && left > right  )
						{
							_x = _x+1;
							curE = E + right;
						}
						
						//bounds it inside the image
						_x = ( _x < 1) ? 1 : ( _x > width-1 ) ? ( width-1 ) : _x;
						
						end.push( _x );
						myE += curE;
						
					}
					
				}
				if( myE < minE )
				{
					
					minE = myE;
					vpath = end.concat();
					
				}
				
			}
				
			
		}
		
		/*
		 * scales the original picture to new dimensions 
		 * @param W:int the target width
		 * @param H:int the target height
		 */
		public function resize( W:int = 0, H:int = 0 ):void
		{
			
			var w:int = W-width;
			var h:int = H-height;
			var x:int;
			var _x:int;
			var y:int;
			var _y:int;
			var it:int;
			
			
			if( w < 0 && width > 2 )
			{
				for ( it = 0; it < -w; it++ )
				{
					
					width--;
					computeVerticalPath();
					
					for ( x = 0; x < width; x++ )
					{
						for ( y= 0; y < height; y++ )
						{
						
							_x = vpath[ y ];
							input[ x ][ y ] = ( _x > x ) ? input[ x ][ y ] : input[ x + 1 ][ y ];
							energy[ x ][ y ] = ( _x > x ) ? energy[ x ][ y ] : energy[ x + 1 ][ y ];
							
						}
					}
						
					//recomputes the energy map every # passes
					ticker++;
					if( ticker % refreshRate == 0 )
					{
						redrawBitmapData();
						computeEnergyMap( bd );
					}
				}
				redrawBitmapData();
			}
			
			if( h < 0 && height > 2 )
			{
				for ( it = 0; it < -h; it++ )
				{
					
					height--;
					computeHorizontalPath();
					
					for ( x = 0; x < width; x++ )
					{
						for ( y= 0; y < height; y++ )
						{
						
							_y = hpath[ x ];
							input[ x ][ y ] = ( _y > y ) ? input[ x ][ y ] : input[ x ][ ( y+1 ) ];
							energy[ x ][ y ] = ( _y > y ) ? energy[ x ][ y ] : energy[ x ][ ( y+1 ) ];
							
						}
					}
					//recomputes the energy map every # passes
					ticker++;	
					if( ticker % refreshRate == 0 )
					{
						redrawBitmapData();
						computeEnergyMap( bd );
					}
				}
				redrawBitmapData();
			} 
		}
		
		/*
		 * refreshes the bitmap
		 */
		public function redrawBitmapData():void
		{
			bd.fillRect( bd.rect, 0);
			getImage( bd );
		}
	
		/*
		 * cleaning up: deletes all resources , bitmaps, arrays aso.
		 */
		public function dispose():void
		{
			
			this.bd.dispose();
			this.original.dispose();
			this.out.dispose();
			this.bmpd.dispose();
			
			input = null;
			energy = null;
			hpath = null;
			vpath = null;
			
		}
			
	}
}