I was inspired by a recent lecture I took at Uni. In said lecture we discussed different matrix decompositions. This repo will be used to visualize semi-discread matrix decompositions (SDD) on images and provide a visual idea of the compression as well as concreate compression rates.
Look the result using some example pictures on my website
A semi-discrete matrix decomposition is a sum of rank one matrices. Every summand is constructed by
We can represent any matrix A exatly as the sum
when choosing k large enough.
Since x and y can only take three differnt values we can store their values very efficently, needing only 2 Bits per entry. Additionaly x and y are expected to be (very) sparse for bigger k. This could be used with hamming codes to further compress images lossless.
My examples are based on 512 * 512 rgb pictures. That means in a raw format we have 512*512 Bytes ~ 786kb
The compression rates will always be in relation to k. In one byte we are able to store 4 entries of x (or y). So we need 2 * 512/4 = 128 Bytes to store x and y and one additional byte for d. Since we have three layers (red, green, blue) we will need 129 * 3 = 387 Bytes per layer. So in total the SDD approximation of the picture will take 387*k Bytes. To match the raw format we could calculate around 2.000 layers.
My visualization will take a maximum of 250 layers into account.
The output images will be .jsdd files. A custom data type which is than interpreted by the javaScript code.
Pick a picture on the website and use the slider to select the number of layers. The canvas shows the state of the SDD approximation based of the selected value of k. Additionally the .jsdd file size is displayed.
Place your pictures in examples/in and run python sdd.py --FILENAME. If you want the json output as well, add --json
%TODO add algo references, literature, thank you words, contact