#!/usr/bin/perl
#
# JpegEnc   
# Perl based JPEG encoder. 
# Version 0.11
# 3/18/2004
#
#
# Version History
# -----------------
# + Updated input code to use Matrices to 
#   store the data instead of nested hashes. 
# Currently this code is triumphantly broken. At 
# This point it's serving more as a framework for 
# future work than as any sort of functional piece
# of software. The To-Do list is large, and below
# for your amusement. 
#
# To-Do
# --------
# - Look through jpeg include file at 
#   http://www.riverrock.org/~howard/jpeg_marker.perl
#   and figure out how to load and write JPEG data without
#   using GD.pm.
# - get rid of the super nested hash's and use Matrices for
#   all of this stuff.
# - Chrominance Sampling
# - Nail down the Level shifting
# - Figure out the correct way to apply the DCT to the data,
#   might be using them on Luminance AND Chrominance at same time.
# - Fix Block seperating loop
# - find a better way to do the zig-zag re-ordering
# - Finish the code : 
#	+ Run Length Coding
#	+ Huffman Coding
#	+ Jpeg headers and organization
#
#
# That's just to get this code functional, eventually this will use
# Perl/TK to do realtime conversions of images so that the user can
# tweak everything possible to get the right mix of quality and compression.
# I don't even know what that'll entail at this point, so I don't have a to-do
# on that.
# 
# -Sam Heller
#  sheller@marlboro.edu
#  
########

use GD; 
use Math::MatrixReal;
use Math::FFT;

my %yuv = {};
my $pic = 'pic/squares.png';
my $truecolor = '1'; 
my $img = GD::Image->newFromPng($pic, $truecolor);
my ($width, $height) = $img->getBounds();
my $wblock = ($width / 8);
my $hblock = ($height / 8);
my $blocks = ($wblock * $hblock);

##########
# Step 1 : Color Conversion
#  Get all the color values for each pixel, 
#  convert them into YUV colorspace, and 
#  stick the values into seperate matrices that
#  can be used later for fun and games.
###########


my $YVals  = new Math::MatrixReal($width, $height);
my $CbVals = new Math::MatrixReal($width, $height);
my $CrVals = new Math::MatrixReal($width, $height);

for ($xct = 1; $xct != $width; $xct++)
        {
        for ($yct = 1; $yct != $height; $yct++)
                {
                my ($r,$g,$b) = $img->rgb($img->getPixel($x,$y));
                my $Y  = ( 0.299  * $r +   0.587 * $g + 0.114  * $b +   0);
                my $Cb = (-0.1687 * $r - 0.03313 * $g + 0.5    * $b + 128);
                my $Cr = ( 0.5    * $r - 0.4187  * $g - 0.0813 * $b + 128);
                $y++;
                $xrow = ($x + 1);
                $yrow = ($y + 1);
   
                $YVals ->assign($xrow, $yrow, $r );
                $CbVals->assign($xrow, $yrow, $Cb);
                $CrVals->assign($xrow, $yrow, $Cr);
	
#                $YVals ->assign($xrow, $yrow, $Y );
#                $CbVals->assign($xrow, $yrow, $Cb);
#                $CrVals->assign($xrow, $yrow, $Cr);
               }
        $y = 0;
        $x++;
        }


##########
# Step 1.5: Sample 
#  I'm not totally clear on what to do here, to 
#  achieve good compression I need to figure out
#  how to get an average of the chrominance for 
#  each two by two block of pixels. Not quite sure
#  how I would do that yet, much less how that would
#  alter how I've stored my values. I'm gonna skip this
#  until I'm more solid, and then deal with it. for now it
#  shouldn't be a problem. In lieu of code, here's a picture
#  of Skippy McGee, the boy wonder.  
###########


          ###### ######
          # -- # # -- #
          ###### ######
                #
                 #
               ####   

           ##       ##
            ##     ##
             #######



#############
# Step 2 : Level Shift
#   Different kind of not sure here, I think
#   I'm supposed to subtract 128 from each of
#   the values, so that's what I'll do. It doesn't
#   feel right though, so this step might be completely off.
#   This is basically the same code as used to assign the 
#   values in the first place.
#############
for ($x = 0; $x != $width; $x++)
        {
        for ($y = 0; $y != $height; $y++)
                {
                   $$$yuv{Y}{$x}{$y}  -= 128;
                   $$$yuv{Cb}{$x}{$y} -= 128;
                   $$$yuv{Cr}{$x}{$y} -= 128;
		}
	}

##########
# Step 3 : DCT Transform
#   This is where it gets exceptionally tricky, we have to 
#   apply a Discrete Cosine Transform to each component of
#   pixel of the picture. I'm using Math:FFT here because
#   I've only got the vaugest idea about how to apply this 
#   formula, so I'm using all the help I can get. Once again, as
#   soon as I get more solid on this I'll try to hard-code the
#   transform.
##########                                                                                                                                             

for ($x = 0; $x != $width; $xt++)
	{
	for ($y = 0; $y != $height; $y++)
		{

		#
		# I highly doubt that this works, but what
		# I want it to be doing is running the transform
		# over each individual component of the YUV colorspace
		#
		my $YData = $$$yuv{Y}{$x}; 
 		my $fft = new Math::FFT($YData);
		$$$yuv{$x}{$y}{Y} = $fft->ddct;

                my $CbData = $$$yuv{Cb}{$x};
                my $fft = new Math::FFT($CbData);
                $$$yuv{$x}{$y}{Y} = $fft->ddct;

                my $CdData = $$$yuv{Cr}{$x};
                my $fft = new Math::FFT($CdData);
                $$$yuv{$x}{$y}{Y} = $fft->ddct;

		}
	}


##########
# Step 4 : Break it into Chunks
#   Now that we've got everything all transformed, 
#   we have to break the data down into 8x8 chunks 
#   so that they can be re-ordered and then Quantized.
#   at this point the xy coordinates don't matter anymore
#   because we're about to re-order their position. this
#   makes life a whole heluva lot easier. This step may actually
#   come before the DCT transform, in which case, my bad.
##########
my %block = {};
$x = 0;
$y = 0;

#
# Kind of a weird series of nested for loops. I'm setting
# up $blocknum to be able to keep track of seperate blocks
# and ending it when it reaches the actual number of blocks
# in the picture. 
#

#
# !!! - On a last second lookover, I think that this doesn't - !!!
# !!! - actually get all the blocks, I think it skips the    - !!! 
# !!! - blocks in the corner, but I'm not sure. I'll fix     - !!!
# !!! - this when I have a little more time.                 - !!!
#

for ($blocknum = 1; $blocknum != $blocks+1; $blocknum++)
	{
	my $pixel = 1;
	for ($ct1 = 0; $ct1 != 8; $ct1++)
		{
		for ($ct2 = 0; $ct2 != 8; $ct2++)
			{
			$$$block{$blocknum}{$pixel}{Y}  = $$$yuv{$x}{$y}{Y};
			$$$block{$blocknum}{$pixel}{Cb} = $$$yuv{$x}{$y}{Cb};
			$$$block{$blocknum}{$pixel}{Cr} = $$$yuv{$x}{$y}{Cr};				
			$x++;
			$pixel++;
			}
		$y++;
		}
	}



#############
# Quantize BEFORE re-ordering!!!!!!!!!!!!!!
# Step 5 : Zig-Zag Re-ordering
#   Now that we've got the chunks, we need re-order
#   them zig-zag style from lowest to highest. This
#   has something to do with ascending order of 
#   "spatial frequencies" which I'm fairly sure is what
#   the DCT transform gave us. 
#############


for ($blocknum = 1; $blocknum != $blocks+1; $blocknum++)
	{
	for ($pixel = 1; $pixel != 65; $pixel++)
		{
		push (@Ytemp, $$$block{$blocknum}{$pixel}{Y});
		push (@Crtemp, $$$block{$blocknum}{$pixel}{Cr});
		push (@Cdtemp, $$$block{$blocknum}{$pixel}{Cd});
		}
		@Ys  = sort { $a <=> $b } @Ytemp;
		@Crs = sort { $a <=> $b } @Crtemp;
		@Cbs = sort { $a <=> $b } @Cbtemp;



my @YBlock;
my @CrBlock;
my @CbBlock;
#
# This is the really scary part, The best way I could think
# to so specifically re-order the block was to stick it in a 
# matrix. This is probably not the easiest way to do it, but it
# works okay for now. 
 
$YBlock[$blocknum] = Math::MatrixReal->new_from_rows(
[
[ $Ys[0] , $Ys[1] , $Ys[5] , $Ys[6] , $Ys[14], $Ys[15], $Ys[27], $Ys[28] ],
[ $Ys[2] , $Ys[4] , $Ys[7] , $Ys[13], $Ys[16], $Ys[26], $Ys[29], $Ys[42] ],  
[ $Ys[3] , $Ys[8] , $Ys[12], $Ys[17], $Ys[25], $Ys[30], $Ys[41], $Ys[43] ],
[ $Ys[9] , $Ys[11], $Ys[18], $Ys[24], $Ys[31], $Ys[40], $Ys[44], $Ys[53] ],
[ $Ys[10], $Ys[19], $Ys[23], $Ys[32], $Ys[39], $Ys[45], $Ys[52], $Ys[54] ],
[ $Ys[20], $Ys[22], $Ys[33], $Ys[38], $Ys[46], $Ys[51], $Ys[55], $Ys[60] ],
[ $Ys[21], $Ys[34], $Ys[37], $Ys[47], $Ys[50], $Ys[56], $Ys[59], $Ys[61] ],
[ $Ys[35], $Ys[36], $Ys[48], $Ys[49], $Ys[57], $Ys[58], $Ys[62], $Ys[63] ],
]);

$CrBlock[$blocknum] = Math::MatrixReal->new_from_rows(
[
[ $Crs[0] , $Crs[1] , $Crs[5] , $Crs[6] , $Crs[14], $Crs[15], $Crs[27], $Crs[28] ],
[ $Crs[2] , $Crs[4] , $Crs[7] , $Crs[13], $Crs[16], $Crs[26], $Crs[29], $Crs[42] ],
[ $Crs[3] , $Crs[8] , $Crs[12], $Crs[17], $Crs[25], $Crs[30], $Crs[41], $Crs[43] ],
[ $Crs[9] , $Crs[11], $Crs[18], $Crs[24], $Crs[31], $Crs[40], $Crs[44], $Crs[53] ],
[ $Crs[10], $Crs[19], $Crs[23], $Crs[32], $Crs[39], $Crs[45], $Crs[52], $Crs[54] ],
[ $Crs[20], $Crs[22], $Crs[33], $Crs[38], $Crs[46], $Crs[51], $Crs[55], $Crs[60] ],
[ $Crs[21], $Crs[34], $Crs[37], $Crs[47], $Crs[50], $Crs[56], $Crs[59], $Crs[61] ],
[ $Crs[35], $Crs[36], $Crs[48], $Crs[49], $Crs[57], $Crs[58], $Crs[62], $Crs[63] ],
]);


$CbBlock[$blocknum] = Math::MatrixReal->new_from_rows(
[
[ $Cbs[0] , $Cbs[1] , $Cbs[5] , $Cbs[6] , $Cbs[14], $Cbs[15], $Cbs[27], $Cbs[28] ],
[ $Cbs[2] , $Cbs[4] , $Cbs[7] , $Cbs[13], $Cbs[16], $Cbs[26], $Cbs[29], $Cbs[42] ],
[ $Cbs[3] , $Cbs[8] , $Cbs[12], $Cbs[17], $Cbs[25], $Cbs[30], $Cbs[41], $Cbs[43] ],
[ $Cbs[9] , $Cbs[11], $Cbs[18], $Cbs[24], $Cbs[31], $Cbs[40], $Cbs[44], $Cbs[53] ],
[ $Cbs[10], $Cbs[19], $Cbs[23], $Cbs[32], $Cbs[39], $Cbs[45], $Cbs[52], $Cbs[54] ],
[ $Cbs[20], $Cbs[22], $Cbs[33], $Cbs[38], $Cbs[46], $Cbs[51], $Cbs[55], $Cbs[60] ],
[ $Cbs[21], $Cbs[34], $Cbs[37], $Cbs[47], $Cbs[50], $Cbs[56], $Cbs[59], $Cbs[61] ],
[ $Cbs[35], $Cbs[36], $Cbs[48], $Cbs[49], $Cbs[57], $Cbs[58], $Cbs[62], $Cbs[63] ],
]);

}




###########
# Step 6 : Quantify me Baby!
#   Here's where we seriously start to weed out frequencies 
#   that we don't really need. I'm using a quantization table
#   that I got from http://www.cs.cf.ac.uk/Dave/Multimedia/node237.html
#
###########



$QuantizationTable = Math::MatrixReal->new_from_rows(
	[
		[16,  11,  10,  16,  24,   40,   51,   61 ],   
		[12,  12,  14,  19,  26,   58,   60,   55 ],  
		[14,  13,  16,  24,  40,   57,   69,   56 ],   
		[14,  17,  22,  29,  51,   87,   80,   62 ],  
		[18,  22,  37,  56,  68,   109,  103,  77 ],  
		[24,  35,  55,  64,  81,   104,  113,  92 ],  
		[49,  64,  78,  87,  103,  121,  120,  101],  
		[72,  92,  95,  98,  112,  100,  103,  99 ],   
	]);



# I can't find a chrominance quantization table, keep looking for that.
# in the meantime, let's at least quantize what we can. 
my @Yfinal;
for ($blocknum = 1; $blocknum != $blocks+1; $blocknum++)
	{
	$Yfinal[$blocknum] = ($Yblock[$blocknum] / $QuantizationTable + 0.5);
	}


###########
#  Here's where I get rather annoyingly stuck. I need to get the rest of 
#  the code functional before I can even figure out how to start encoding the
#  end data. After this I need to implement Run Length and Huffman encoding 
#  in order to finish the compression. After that I could just pipe the image
#  data to GD and have it write out the headers for me. The end goal is to 
#  free this from GD, but as an interim step it's not a bad one. So basically
#  at this point I need some more research, time to hack away at the code and 
#  make it workable, and a large bed with super fluffy pillows.
#
#
#  Ice cream would also be nice.
###########
