Image Compression with Singular Value Decomposition
timbaumann.info
Image Compression with Singular Value Decomposition
1–10 of 47 posts
Re: Image Compression with Singular Value Decomposition
#2Very interesting. I will be digging into this one. The first thing that popped out at me:
> We can decompose a given image into the three color channels red, green and blue. Each channel can be represented as a (m × n)‑matrix with values ranging from 0 to 255. We will now compress the matrix A representing one of the channels.
I wonder if the author considered converting to YCbCr colorspace first. The luminance component (Y) is substantially more important to the human visual system than the Cb/Cr components. Some subsampling of the chrominance components would probably work well in these schemes.
Re: Image Compression with Singular Value Decomposition
#3Mmh, compression ratio doesnt seem super high. I wonder how the values are stored, perhaps floats? Some thoughts:
Maybe using yuv would be better than rgb?
Maybe values could be represented as 0..1, and the values itself could be stored as 0.16 fixed point numbers.
Use some generic compression on top.
Is there a smart way to store the basis vectors? Something about angles somehow (analogue to quaternions)? Also, once U is known, isnt the inverse implied? Also, if U is approximated and fixed, perhaps the singular values can be adjusted again to minimize errors.
Re: Image Compression with Singular Value Decomposition
#4Fun fact, you can also do it with various flavors of tensor decomposition[1].
1. http://tensorly.org/stable/auto_examples/decomposition/plot_...
Re: Image Compression with Singular Value Decomposition
#5A great primer to SVD from AMS:
Re: Image Compression with Singular Value Decomposition
#6For those that don't know about it already, Steve Brunton has some good videos on many math topics, including image compression using SVD [0].
Re: Image Compression with Singular Value Decomposition
#7Mmh, compression ratio doesnt seem super high. I wonder how the values are stored, perhaps floats? Some thoughts: Maybe using yuv would be better than rgb? Maybe values could be represented as 0..1, and the values itself could be stored as 0.16 fixed point numbers. Use some generic compression on top. Is there a smart way to store the basis vectors? Something about angles somehow (analogue to quaternions)? Also, once…
I’m guessing there’s just a lot left on the table—
> Maybe values could be represented as 0..1, and the values itself could be stored as 0.16 fixed point numbers. Use some generic compression on top.
Codecs like JPEG use a variable amount of quantization. You quantize by scaling the 0..1 float by some scalar, putting it in the range 0..k, and then truncating it to an integer, and encoding the integer. The integer value is encoded using an entropy coder like Huffman. The parameter k must also be encoded somehow, or fixed.
Look up “JPEG coefficient quantization” for how JPEG does it.
Codecs for audio and images are often made up of understandable parts that fit together: transformations, quantization, entropy coding. If you come up with a new transformation, you can make a whole codec by putting together the remaining pieces—but something like a new transformation is itself interesting, because somebody else can always assemble it into a codec if it shows promise.
Re: Image Compression with Singular Value Decomposition
#8I remember doing this in uni 14 years ago. Can't remember it being very efficient.
Re: Image Compression with Singular Value Decomposition
#9Funny enough, I did this same project (minus the fancy web interface) for a numerical linear algebra course in college—except I had to do it in Matlab.
It's worse than just about any "real" image compression algorithm, but it works! (Plus you get lossless compression if your image is low-rank.)
Re: Image Compression with Singular Value Decomposition
#10Mmh, compression ratio doesnt seem super high. I wonder how the values are stored, perhaps floats? Some thoughts: Maybe using yuv would be better than rgb? Maybe values could be represented as 0..1, and the values itself could be stored as 0.16 fixed point numbers. Use some generic compression on top. Is there a smart way to store the basis vectors? Something about angles somehow (analogue to quaternions)? Also, once…
I’m guessing there’s just a lot left on the table— > Maybe values could be represented as 0..1, and the values itself could be stored as 0.16 fixed point numbers. Use some generic compression on top. Codecs like JPEG use a variable amount of quantization. You quantize by scaling the 0..1 float by some scalar, putting it in the range 0..k, and then truncating it to an integer, and encoding the integer. The integer val…
> Codecs like JPEG use a variable amount of quantization
The reason quantization works so well in JPEG is because of the DCT step and its energy compaction properties. This gets most of the coefficients near zero. I think without this transform you would be introducing a lot more noise in the final result.
At some point, we are going to end up re-implementing a thing approximating jpeg here. Colorspace convert, subsampling & DCT+quantization is most of the magic sauce.