Concatenate nested array to vector?

Question

Given I have an array like this:

array = [Array[8], Array[8], Array[8], ...]
# array.length is 81; each octet represents a point on a 9x9 grid

where each nested array contains 8 numeric elements ranging from -2 to 2, how would I apply the following step to get a vector in Javascript?

Step 5. The signature of an image is simply the concatenation of the 8-element arrays corresponding to the grid points, ordered left-to-right, top-to-bottom. Our signatures are thus vectors of length 648. We store them in 648-byte arrays, but because some of the entries for the first and last rows and columns are known to be zeros and because each byte is used to hold only 5 values, signatures could be represented by as few as ⌈544 log₂ 5⌉ = 1264 bits.

(Towards the end, those are supposed to be ceiling notations; best I could do given SO's lack of Latex formatting)

I have the array ready to go and ordered properly, but my knowledge of matricies and vectors is a little rusty, so I'm not sure how to tackle this next step. I'd appreciate any clarifications!

---

Background: I'm trying to create a JS implementation of an image processing algorithm published by the Xerox Palo Alto Research Center for a side-project I'm currently working on.

Answer 1

Conceptually you could convert this to a single 1264 bit number using the following algorithm:

1. Initialize an accumulator variable to zero
2. Iterate over all elements, but skipt those which you know to be zero
3. For the other elements, add 2 to obtain values in the range [0,1,2,3,4]
4. For each such value, multiply the accumulator by 5 then add the corresponding value
5. When you have processed all elements, the accumulator will encode your arrays

To reverse that encoding, youd do this:

1. Read the encoded value into the accumulator
2. Iterate over all elements, in reverse order, but skipt those which you know to be zero
3. For each element, you obtain the corresponding value as the accumulator modulo 5
4. Subtract 2 from that value
5. Divide the accumulator by 5 using a truncating division

The problem with all of this is the fact that JS doesn't provide 1264 bit numbers out of the box. You might try one of the libraries suggested in How to deal with big numbers in javascript.

But unless you absolutely requre an extremely small representation, I'd suggest an alternative approach: you can encode up to 13 such values in a 32 bit signed integer, since 5¹³=1,220,703,125 < 2,147,483,648=2³¹. So after encoding 13 values I'd write out the result using such a number, then reset the accumulator to zero. This way you'll need ⌈544/13⌉∙32=1376 bits, which is not that much worse in terms of space requirements, but will be a lot faster to implement.

Instead of iterating once in forward and once in reverse direction, it might be easier to not multiply the accumulator by 5, but instead multiply the value you add to that by a suitable power of 5. In other words, you maintain a factor which you initialize to 1, and multiply by 5 every time you add a value. So in this case, first data values will have less significant positions than later data values, both for encoding and decoding, which means you can use the same iteration order for both.

See the ideone link mentioned in my comment below for an example of this latter approach. It encodes the full 9*9*8 values in 50 integers, each of them using no more than 31 bits. It then decodes the original matrix from that encoded form, to show that all the information is still present. The example does not use any fixed zeros, in your case ⌈544/13⌉=42 integers should be enough.