How are matrices stored in memory?

Question

Note. Perhaps this is more related to the computer organization than to the software, but not sure.

I am trying to understand something related to data compression, for example, for jpeg photos. Essentially a very dense matrix is ​​transformed (via discrete cosine transforms) into a much more sparse matrix. Presumably, this small matrix is ​​preserved. Take a look at this link:

http://en.wikipedia.org/wiki/JPEG

Comparison of the original example image of the 8x8 subunit with the “B” matrix, which is converted to have common values ​​of lower magnitude and much more zeros. How is matrix B stored so that it saves a lot more memory over the original matrix?

The original matrix clearly needs 8x8 (number of records) x 8 bits / record, since the values ​​can vary randomly from 0 to 255. OK, so I think it's pretty clear that we need 64 bytes of memory for this. On the other hand, the matrix B, hmm. The best random scenario that I can think of is that the values ​​range from -26 to +5, so in most cases writing (e.g. -26) requires 6 bits (5 bits to form 26, 1 bit for sign, which I guess). So you can store 8x8x6 bits = 48 bytes.

Another possibility that I see is that the matrix is ​​stored in zig zag order in the upper left. Then we can specify the start and end address and just store it diagonally until we are left with zeros. Let's say this is a 32-bit machine; then 2 addresses (start + end) will be 8 bytes; for other non-zero entries of 6 bits each, say, we need to go through almost all the upper diagonals to save a sum of 28 elements. In total, this scheme will occupy 29 bytes.

To summarize my question: if JPEG and other image encoders require space saving, using algorithms to make the image matrix less dense, how is this extra space implemented on my hard drive?

Greetings

Answer 1

As stated in Entropy Coding, a zigzag pattern is used, as well as RLE, which in many cases will already reduce size. However, as far as I know, DCT does not produce a sparse matrix as such. But it usually enhances the entropy of the matrix. This is the point at which compression becomes unprofitable: the input matrix is ​​transmitted with DCT, then the values ​​are quantized, and then huffman encoding is used.

Answer 2

Dct should be accompanied by other compression schemes that take advantage of the zeros / treble. A simple example is run length coding.

JPEG uses the Huffman encoding option.

Answer 3

The simplest compression will use repeating sequences of characters (zeros). The matrix in memory may look like this (suppose in the dec system)

0000000000000100000000000210000000000004301000300000000004 

After compression, it may look like this:

 (0,13)1(0,11)21(0,12)43010003(0,11)4 (Symbol,Count)... 

Answer 4

Like my stand, JPEG is only for compression, it also discards data. After transferring the 8x8 block to a frequent domain, it discards significant (high-frequency) data, which means that it should only save important data of 6x6 or even 4x4 size. That it may have a higher compression rate and then no lost method (e.g. gif)