Unencoding the Nikon Images - Part 3

Astrophotography Part 3 - Unencoding the Nikon D90 Images

I don't have much time other than weekends and metro rides where I can read source code on my Kindle Fire so this is going slowly...

Anyway, there is some code out there written by Dave Coffin to decode most image formats. It's wonderfully written, but it's quite terse and not commented too often. Anyway, the images for the Nikon D90 are huffman encoded, and the decoding tree is well... not in the F*$&@$G file!


Dave Coffin's code contains the decoding tree which is as follows:
 { 0,1,5,1,1,1,1,1,1,2,0,0,0,0,0,0,    /* 12-bit lossy */
      5,4,3,6,2,7,1,0,8,9,11,10,12, ?? } //ignore the "??" for now

There are two pieces to this code:

1. The occurences: The first 16 numbers are a separate quantity in themself. The nth position refers to the number of occurrences of an n-length code. 
2. The leaves : The rest of the data are the leaves. Notice that the sum of the for 16 numbers should equal the number of leaves. Also note that this describes 12 bit data and that there are 12 leaves (there seems to be a typo in Dave Coffin's code so there is a missing leaf, hence the "??").

Anyway, making the tree, you should find that the code goes as follows:

00 - 5
010 - 4
011 - 3
100 - 6
101 - 2
110 - 7
1110 - 1
11110 - 0
111110 - 8
1111110 - 9
11111110 - 11
111111110 - 10
1111111110 - 12
1111111111 - ??
I have no clue what the last value is because it seems that his source code doesn't have it. In either case, I have checked and this value never occurs in my image so we're all good. But it would be a good idea to have an error message returned it this value is ever found.

What these values mean

It turns out that this code does not give you the image itself. It actually gives you the number of bytes to read after the code for each pixel. So the decoding pattern would be (at iteration n):

1. Find the next huffman code
2. Decode it and read that number of bits. This value will be used for the nth pixel
3. repeat for n+1

Before continuing, we can make the following remark. In the huffman encoding scheme, the length of the bit pattern is more or so inversely related to the frequency. So we see the number of bits returned is usually in the ballpark of 2-7 bits, with 0,1,8 being rarer.
Also, the order in which you read the pixels is obviously important. The array dimensions should be 2868x4352. So, in this case that an nth pixel is located in position (assuming 0 based indexing. For 1-based, subtract 1 from n first then add 1 after the operation to result):
n/2868 + n%2868 4352


Anyway, that's the basic idea for now. The next step is to understand the color matrix, which I'll get to when I find time. The next image I will show will be a very bad (false color) plot of the raw pixels, so you are warned. After this maybe some discussions on code. There is a fast technique Dave Coffin uses to decode a huffman table (and took some time thinking about it on the metro while reading it) that is pretty neat. I could not find documentation on this anywhere.

False Color plot of the image so far. This one is of the moon.

A zoom on the plot. Notice the periodicity in x and y.