[staticVoid]

I've rearranged it a bit just so I won't get confused when I refer to the standard:

c = 1.0;

			if(u == 0) {

			   c *= 1.0/(Math.sqrt(2.0));

			}

			if(v == 0) {

			   c *= 1.0/(Math.sqrt(2.0));

			}

It's the same thing

[Advertisements]

good job!

when all else fails ... follow the standard

I believe the IDCT and huffman are left. You are about 40% done with the coding.

hufman is intense.

Debugging may take awhile, but it may not be too bad ... you are good at java

keep at it ... if you tackle your profession as aggressively as compression/decompression then the sky is the limit. I am impressed.

[bdlt]

good job!

when all else fails ... follow the standard

I believe the IDCT and huffman are left. You are about 40% done with the coding.

hufman is intense.

Debugging may take awhile, but it may not be too bad ... you are good at java

keep at it ... if you tackle your profession as aggressively as compression/decompression then the sky is the limit. I am impressed.

[staticVoid]

I understand Huffman coding fine but I dont know how to read interpret the table. According to every reference I've read It says the huffman table should be a binary number with a character:

char binary 
'a'	 10  
'b'	 11  
'c'	 0100  
'd'	 0101  
'e'	 0110  
'f'	  0111  
'g'	 000  
'h'	 001

but when I extract the huffman table from an image it looks like this(char):

►   ☻ ☺ ♥ ♥ ☻ ♦ ♥ ♣ ♣ ♦ ♦	 ☺ } ☺ ☻ ♥   ♦ ◄ ♣ ↕ ! 1 A ♠ ‼ Q a  " q ¶ 2 ? ? í #
 B ▒ ┴ § R Ð ­ $ 3 b r ?
 ▬ ↨ ↑ ↓ → % & ' ( ) * 4 5 6 7 8 9 : C D E F G H I J S T U V W X Y Z c d e f g h
 i j s t u v w x y z ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ó ú ñ Ñ ª º ¿ ® ¬ ▓ │ ┤ Á
 Â À © ╣ ║ ┬ ├ ─ ┼ ã Ã ╚ ╔ ╩ Ê Ë È ı Í Î Ï ┘ ┌ ß Ô Ò õ Õ µ þ Þ Ú Û ± ‗ ¾ ¶ § ÷ ¸
 ° ¨ ·

(ac values)

??

[bdlt]

just about everything done with huffman is done at the bit level

► ☻ ☺ ♥ ♥ ☻ ♦ ♥ ♣ ♣ ♦ ♦ ☺ } ☺ ☻ ♥ ♦ ◄ ♣ ↕ ! 1 A ♠ ‼ Q a " q ¶

the 'characters' above need to be parsed one bit at a time

are you extracting the table from the file? if so do you have an example to help build the huffman table?

extracting the tables may be done using bytes - there should be 4 FFC4 markers



this wasn't as helpful as expected, but it may be handy later
http://www.impulsead...eg-decoder.html

start with this one
http://www.xpounded....PEGMarkers.html

........................................................
edit for Sep 6

it might be time to dig into the spec: pages 40 41 49-53 89-93 107-112 143-160
www.w3.org/Graphics/JPEG/itu-t81.pdf


reference code can be found below. these may be handy later on. am still looking for a good parsing example.

http://svn.ghostscri...peg-6b/jchuff.c

http://www.codeguru....ad.php?t=376603

Edited by bdlt, 06 September 2007 - 09:18 AM.

[staticVoid]

have you ever written a program that involved all these steps before?

im still not sure on the order of the image data when uncompressed.

[staticVoid]

I've written a method that extracts an array of bits from a character:

public int[] getBits(double c) {

	  int[] temp = new int[8];

	  if((c/128.0)>1) { c -= 128; temp[0] = 1; } else { temp[0] = 0; }
	  if((c/64.0)>1)  { c -= 64;  temp[1] = 1; } else { temp[1] = 0; }
	  if((c/32.0)>1)  { c -= 32;  temp[2] = 1; } else { temp[2] = 0; }
	  if((c/16.0)>1)  { c -= 16;  temp[3] = 1; } else { temp[3] = 0; }
	  if((c/8.0)>1)   { c -= 8;   temp[4] = 1; } else { temp[4] = 0; }
	  if((c/4.0)>1)   { c -= 4;   temp[5] = 1; } else { temp[5] = 0; }
	  if((c/2.0)>1)   { c -= 2;   temp[6] = 1; } else { temp[6] = 0; }
	  if((c/1.0)>1)   { c -= 1;   temp[7] = 1; } else { temp[7] = 0; }

	  return temp;

   }

Is this where I would start with huffman decoding?

Edited by staticVoid, 12 September 2007 - 06:45 AM.

[bdlt]

sorry for the slow reply – am out on travel until Sep 17

post #65 – yes, I worked on a jpeg project in 2001

the huffman code is the most challenging part of working with jpeg.

There are some design considerations to look at now.

Huffman can be encoded/decoded using ints or StringBuffers. I’m not sure if there is any great advantage of one over the other. Run time with ints will probably be faster. You have chosen ints in getBits().

Before we start parsing image data, we need to extract the 4 huffman tables from the header. There should be 4 FFC4 markers in the header. After each marker, we extract 1 huffman table.

Another thing to consider – the image can be read from the file one byte at a time and parsed on the fly. Or you can read the entire file while storing each byte in an array, then parse the bytes in the array after closing the file. Debugging might be easier with the bytes stored in an array, but the choice is yours.

One free tool I find helpful is an irfanview image viewer. It has a hex editor which comes in handy when developing code and during debug.

getBits() – take a look at temp[].
temp[0] is the only one filled. You want to fill temp[1] through temp[7] too.

[staticVoid]

I've got the four huffman tables from almost every file I use but I don't know how to parse them?

Edited by staticVoid, 12 September 2007 - 07:00 AM.

[bdlt]

let's start at page 50(and back to p 40-41) of the spec

we are going to work with BITS, HUFFVAL, and HUFFSIZE

let's parse some bytes:
FFC4 is followed by 2 bytes LH(see p41 of the spec) ... LH is the length of the huffman table

2 bytes follow LH - they are TC (table class) and TH destination ... we will ignore these for now

fill BITS with the next 16 bytes

I believe the remaining bytes go into HUFFVAL ... more reading is required here

time to write some code ... see p51 ... this code will fill HUFFSIZE with BITS as the input
HUFFSIZE is the size table

....................................................................
please post the hex codes starting at the first FFC4 and ending at the 2nd FFC4.
please post the BITS, HUFFSIZE, and HUFFVAL values

if this makes sense, continue on to p 52 and fill HUFFCODE

note - everything we do in the header is with bytes
we parse bits once we get to the image data

[staticVoid]

heres the output I get from jpg.java:

JFIF Marker Identified   255   224


Unknown Marker Identified   255   225


Unknown Marker Identified   255   237


Unknown Marker Identified   255   226


Unknown Marker Identified   255   238


Define Quantization Table Marker Identified   255   219

67
8 6 6 6 6 6 8 6 6 8 12 8 7 8 12 14 10 8 8 10 14 16 13 13 14 13 13 16 17 12 12 12
 12 12 12 17 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 1
2 12 12 12 12 12



0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Define Quantization Table Marker Identified   255   219

67
8 6 6 6 6 6 8 6 6 8 12 8 7 8 12 14 10 8 8 10 14 16 13 13 14 13 13 16 17 12 12 12
 12 12 12 17 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 1
2 12 12 12 12 12



9 8 8 9 10 9 11 9 9 11 14 11 13 11 14 17 14 14 14 14 17 17 12 12 12 12 12 17 17
12 12 12 12 12 12 17 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
 12 12 12 12 12 12 12 12
Start Of Frame Marker Identified   255   192


Define Huffman Table Marker Identified   255   196

0
31
31

1511111100000000	 <---BITS

123456789101125500000000000000000000000000000000000000   <---HUFFVAL
Define Huffman Table Marker Identified   255   196

0
31
31

3111111111000000   <---BITS

123456789101125500000000000000000000000000000000000000  <---HUFFVAL
Start Of Scan Marker Identified   255   218


START OF IMAGE DATA


End Of Image

does that look right for BITS and HUFFVAL?

Attached Files

•  jpg.zip   1.6KB   202 downloads

Edited by staticVoid, 13 September 2007 - 03:39 PM.

[bdlt]

The BITS 1511111100000000 value looks incorrect. That is probably my fault.

The first 2 bytes are the marker FF C4(256 196)
The next 2 bytes are the table length 00 31(from your post)

Is that 31 decimal or 31 hex?

The next byte is TC & TH … 4 bits each, not 2 bytes as I stated earlier.

See what you get if you fill BITS starting after TC & TH.

How do we know BITS is incorrect? BITS indicates there are 5 codes that are 2 bits long. That is impossible. There are only 4 possible 2 bit values(and I believe only 3 are usable).

Can you separate the huff values with a space or comma?

if you can send all of the first huffman table data it would help. (hex or int, your choice)

[staticVoid]

heres the new log:

JFIF Marker Identified   255   224


Unknown Marker Identified   255   225


Unknown Marker Identified   255   237


Unknown Marker Identified   255   226


Unknown Marker Identified   255   238


Define Quantization Table Marker Identified   255   219

67
8 6 6 6 6 6 8 6 6 8 12 8 7 8 12 14 10 8 8 10 14 16 13 13 14 13 13 16 17 12 12 12
 12 12 12 17 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 1
2 12 12 12 12 12



0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Define Quantization Table Marker Identified   255   219

67
8 6 6 6 6 6 8 6 6 8 12 8 7 8 12 14 10 8 8 10 14 16 13 13 14 13 13 16 17 12 12 12
 12 12 12 17 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 1
2 12 12 12 12 12



9 8 8 9 10 9 11 9 9 11 14 11 13 11 14 17 14 14 14 14 17 17 12 12 12 12 12 17 17
12 12 12 12 12 12 17 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12
 12 12 12 12 12 12 12 12
Start Of Frame Marker Identified   255   192


Define Huffman Table Marker Identified   255   196


BITS
------

0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,


HUFFVAL
-------

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,


Define Huffman Table Marker Identified   255   196


BITS
------

0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 125,


HUFFVAL
-------

1, 2, 3, 0, 4, 17, 5, 18, 33, 49, 65, 6, 19, 81, 97, 7, 34, 113, 20, 50, 129, 14
5, 161, 8, 35, 66, 177, 193, 21, 82, 209, 240, 36, 51, 98, 114, 130, 9, 10, 22,
23, 24, 25, 26, 37, 38, 39, 40, 41, 42, 52, 53, 54, 55, 56, 57, 58, 67, 68, 69,
70, 71, 72, 73, 74, 83, 84, 85, 86, 87, 88, 89, 90, 99, 100, 101, 102, 103, 104,
 105, 106, 115, 116, 117, 118, 119, 120, 121, 122, 131, 132, 133, 134, 135, 136,
 137, 138, 146, 147, 148, 149, 150, 151, 152, 153, 154, 162, 163, 164, 165, 166,
 167, 168, 169, 170, 178, 179, 180, 181, 182, 183, 184, 185, 186, 194, 195, 196,
 197, 198, 199, 200, 201, 202, 210, 211, 212, 213, 214, 215, 216, 217, 218, 225,
 226, 227, 228, 229, 230, 231, 232, 233, 234, 241, 242, 243, 244, 245, 246, 247,
 248, 249, 250,


Define Huffman Table Marker Identified   255   196


BITS
------

0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,


HUFFVAL
-------

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,


Define Huffman Table Marker Identified   255   196


BITS
------

0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 119,


HUFFVAL
-------

0, 1, 2, 3, 17, 4, 5, 33, 49, 6, 18, 65, 81, 7, 97, 113, 19, 34, 50, 129, 8, 20,
 66, 145, 161, 177, 193, 9, 35, 51, 82, 240, 21, 98, 114, 209, 10, 22, 36, 52, 2
25, 37, 241, 23, 24, 25, 26, 38, 39, 40, 41, 42, 53, 54, 55, 56, 57, 58, 67, 68,
 69, 70, 71, 72, 73, 74, 83, 84, 85, 86, 87, 88, 89, 90, 99, 100, 101, 102, 103,
 104, 105, 106, 115, 116, 117, 118, 119, 120, 121, 122, 130, 131, 132, 133, 134,
 135, 136, 137, 138, 146, 147, 148, 149, 150, 151, 152, 153, 154, 162, 163, 164,
 165, 166, 167, 168, 169, 170, 178, 179, 180, 181, 182, 183, 184, 185, 186, 194,
 195, 196, 197, 198, 199, 200, 201, 202, 210, 211, 212, 213, 214, 215, 216, 217,
 218, 226, 227, 228, 229, 230, 231, 232, 233, 234, 242, 243, 244, 245, 246, 247,
 248, 249, 250,


Start Of Scan Marker Identified   255   218


START OF IMAGE DATA


End Of Image

the 31 is in decimal


here's what im getting for the first huffman table(decimal):

0, 0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
 10, 11,

this is the full huffman table excluding the length

Edited by staticVoid, 14 September 2007 - 01:32 AM.

[bdlt]

That looks better. The BITS values of 119 & 125 look somewhat unusual, but there are corresponding HUFFVALs that indicate that everything is ok. We won’t know for sure until we start parsing the image data.

There are at least 3 more arrays to create and fill: HUFFCODE, EHUFCO, and EHUFSI.

See page 52 of the spec for HUFFCODE.

See page 53 for EHUFCO and EHUFSI.

Jumping ahead a little:
Eventually(soon), we start parsing image data(bits). The most common cause of crashing is due to invalid Huffman codes. Keep this in mind when parsing image data. We are just about done extracting the Huffman tables and arrays. We will use these arrays as ‘lookup tables’. To improve the debug process, it helps to have information such as bit location and the errant Huffman code. This will be more clear once the image data parsing code is tested.

[staticVoid]

heres what I got for HUFFSIZE:

1, 2, 2, 2, 2, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0, 0,

using:

int K = 0;
					 int I = 1; 
					 int J = 1;


					 for(int x = 0; x < 16; x++) {

						if(J > BITS[I]) {
						   I++;
						   J = 1;
						}

						else {
						   HUFFSIZE[K] = I;
						   K++;
						   J++;
						}

					 }

					 HUFFSIZE[K] = 0;

Does that look right?
I don't want to go onto HUFFCODE if HUFFSIZE table is wrong

I'm just going to polish up my jpg class , does it matter if you use methods to process markers by passing the fileinputstream as a parameter?

Edited by staticVoid, 14 September 2007 - 07:47 AM.

[bdlt]

I see one gotcha … exit the loop when I > 16(to prevent an out of range error with BITS). Consider using a while loop … while(I <= 16) … instead of the for loop.

There is another gotcha. The spec uses BITS(1..16), instead of BITS(0..15). Make sure that BITS is filled starting at BITS[1].

We can retrieve LASTK at anytime by getting the size of HUFFSIZE, so that omission is ok.

Passing the filestream should not cause any problems. It’s just ‘another’ object. I prefer opening the file, grabbing all bytes, and closing the file right away. The big disadvantage of doing it my way is the storage space used with the image data. Another disadvantage is tracking the ‘byte’ location in the large array. Passing the filestream is cleaner and more efficient. I don’t anticipate any problems with passing the filestream. Good idea.