5 ms·

SVD Image Compression

141 points by dmicz 3y ago

kroll 3y ago
It may be off topic... but, does anyone know how this compares to Lossy WebP compression used by Google Photos?
- teruakohatu 3y ago
  SVD is not going to compare with state of the art compression, but it has many uses and is very simple to implement.
- gfody 3y ago
  svd is not as good as dct for compression, but it's a good explainer setup
- derf_ 3y ago
  The author talks about JPEG, and says the principle is surprisingly similar, but the connection between the two is actually pretty direct. I will link a previous comment of mine from another discussion of SVD image compression to explain: https://news.ycombinator.com/item?id=34732922 https://news.ycombinator.com/item?id=34732922 To go from JPEG to lossy WebP (really, VP8 intra frames), the main differences are (a) using smaller (4x4) transform blocks instead of 8x8, (b) noticing that if you take just the first coefficient in each block, it looks like a lower resolution of the original image, and applying another 4x4 transform to those coefficients, (c) adding more sophisticated prediction between blocks (e.g., subtract the pixel on the right edge of the previous block from all the pixels in the same row of the current block before transforming them, or something similar to predict in other directions), (d) filtering along block edges to reduce blocking artifacts (many JPEG decoders do this, but WebP/VP8 make it a mandatory part of the standard), and (e) using arithmetic coding instead of Huffman coding. There are of course other minor differences in the details. But the main mechanism that underlies both is a transform that can be derived from the SVD if one assumes a simple statistical model of natural image data.
  - peter_d_sherman 3y ago
    Hi derf_! Those are some very interesting comments! I'd be interested (and this is purely "academic" curiousity) IF there was: Something mathematical -- which would underly all image compression algorithms; that is, if all image compression algorithms could be shown ("proven" I guess -- I am not a professional Mathematician, only armchair, so bear with me!) to belong to a specific class of generalized compression algorithms or (ideally!) a single "parent" (for lack of a better word) image compression algorithm -- that would give rise to all other image compression algorithms, no matter how diverse or not mathematically related they would all seem... The use of Matrices (which model systems of linear equations, which in turn, enumerate/list/make clear/table -- relationships between factors in those equations) -- would seems to be a good starting point for this Mathematical inquiry, should it be made... Maybe I should phrase this a little bit better... Maybe it's something like (as a future goal for the Mathematicians of the world), "for every image compression algorithm X, show/prove that X is related to <parent Mathematical principle involving matrices>"... Or something like that... Sort of like a grand unifying theory of image compression... Anyway, your comments are highly interesting. It seems like you might be part of the way there for something like a rigorously mathematically unified (and proven!) future understanding of image compression!
    - wiml 3y ago
      I don't think that it's truly universal, but quite a few image compression schemes have a similar structure if you stand back and squint: 1. Use a reversible linear transform to transform the image into some other space. (It'll still require the same amount of data to represent) 2. Throw away a bunch of the values (set them to zero, or round them to low precision, etc) 3. Now that there are some repetitive zeroes or whatever, a conventional data compression algorithm (like LZW, Huffman, or interval/arithmetic) can make it smaller Even simple things like resizing an image smaller can be fit into this framework: step 1 is a simple blur, step 2 sets a bunch of pixels to zero, step 3 discards them. (I don't think fractal compression can be fit into this framework, but I could be wrong. That's the only exception I can think of offhand.)
      - 3y ago
- deleted 3y ago
  [deleted]
jeffrallen 3y ago
I would just like to say to linear algebra students today: you are so lucky to have explanations like this, and the Wikipedia article on eigenvalues available to you. In 1990 when I studied linear algebra, I had the book and my professor's explanations and neither were good enough. What a time to be a student!
- nerdponx 3y ago
  Not to mention this contains good examples of effective Numpy and Matplotlib usage. It can be really hard to figure out how to do that stuff on your own.
- deleted 3y ago
  [deleted]
- Mandelmus 3y ago
  As a current compsci masters student at ETH Zurich: yes, having those explanations is wonderful, but that just means that topics like SVD and PCA are taken for granted now, and the things that we need to chew on are things for which no nice canonical explainers have been created (and that likely weren’t taught in 1990). Personally I think that innovation in explanation/illustration of abstract mathematical topics is one of the most valuable kinds of progress, but it’s rarely talked about as such. When someone comes up with the right framework, visualisation, or metaphor for explaining a complex and abstract subject in a way that induces “the right” mental model, and this new teaching “tool” proliferates, that is just a beautiful thing to see.
- LoganDark 3y ago
  The problem is that since explanations like this exist, I don't know how to figure this kind of stuff out like how you did!
radioactivist 3y ago
One small point: since the original image was 1 byte per pixel this SVD is storing the singular values and vectors in 8 byte double precision floats. Using doubles the SVD data is ~ 2.7x larger than the original image at n=60 (2*60+1 = 121 vectors stored vs. the original 360 is a factor of 1/3 then going from 1 to 8 bytes per element), so to get any compression at all you'd need to go to ~ 1-2 bytes per element. I think for a fair comparison for any actual compression you'd need to consider the effects of quantization of the SVD output itself (in say the rows/columns of U,V alone, since you can keep the singular values at high-precision w/o appreciable cost). [I'd guess they'd be ok for 2 bytes/element, but 1 byte might be a problem].
vitus 3y ago
This is hinted at very briefly in one code comment [0] in the article, but this application of SVD is a well-known (to the point that it's even taught in university) method for dimensionality reduction, and typically referred to as Principal Components Analysis (PCA) [1]. [0] Said code comment is "# Plotting the principal components". [1] https://en.wikipedia.org/wiki/Principal_component_analysis https://en.wikipedia.org/wiki/Principal_component_analysis
- secret-noun 3y ago
  I was just looking back into my 8-year-old repo of my university project for this.
hyperific 3y ago
See also https://timbaumann.info/svd-image-compression-demo/ https://timbaumann.info/svd-image-compression-demo/
- _kb 3y ago
  And another great resource here for the same principles (so to speak…) but an audio context: https://www.isik.dev/posts/Eigentechno.html https://www.isik.dev/posts/Eigentechno.html
yuji_itadori 3y ago
SVD is also the back bone for DMRG in the study of quantum groundstates
dgreensp 3y ago
I played with this stuff in high school and college. Principle Component Amalysis (PCA), as another commenter said. One small quibble, with JPEG you don’t “lose” the “high-frequency” data; that would blur the image. You approximate it, so you could argue you “lose” some of it. JPEG is not very good at compressing high-frequency data, which is basically the edges of things, so if your JPEG has sharp edges, you are not losing much high-frequency data, just compressing everything else.

141 points by dmicz 3y ago

kroll 3y ago

It may be off topic... but, does anyone know how this compares to Lossy WebP compression used by Google Photos?

teruakohatu 3y ago
SVD is not going to compare with state of the art compression, but it has many uses and is very simple to implement.
gfody 3y ago
svd is not as good as dct for compression, but it's a good explainer setup
derf_ 3y ago
The author talks about JPEG, and says the principle is surprisingly similar, but the connection between the two is actually pretty direct. I will link a previous comment of mine from another discussion of SVD image compression to explain: https://news.ycombinator.com/item?id=34732922 https://news.ycombinator.com/item?id=34732922 To go from JPEG to lossy WebP (really, VP8 intra frames), the main differences are (a) using smaller (4x4) transform blocks instead of 8x8, (b) noticing that if you take just the first coefficient in each block, it looks like a lower resolution of the original image, and applying another 4x4 transform to those coefficients, (c) adding more sophisticated prediction between blocks (e.g., subtract the pixel on the right edge of the previous block from all the pixels in the same row of the current block before transforming them, or something similar to predict in other directions), (d) filtering along block edges to reduce blocking artifacts (many JPEG decoders do this, but WebP/VP8 make it a mandatory part of the standard), and (e) using arithmetic coding instead of Huffman coding. There are of course other minor differences in the details. But the main mechanism that underlies both is a transform that can be derived from the SVD if one assumes a simple statistical model of natural image data.
- peter_d_sherman 3y ago
  Hi derf_! Those are some very interesting comments! I'd be interested (and this is purely "academic" curiousity) IF there was: Something mathematical -- which would underly all image compression algorithms; that is, if all image compression algorithms could be shown ("proven" I guess -- I am not a professional Mathematician, only armchair, so bear with me!) to belong to a specific class of generalized compression algorithms or (ideally!) a single "parent" (for lack of a better word) image compression algorithm -- that would give rise to all other image compression algorithms, no matter how diverse or not mathematically related they would all seem... The use of Matrices (which model systems of linear equations, which in turn, enumerate/list/make clear/table -- relationships between factors in those equations) -- would seems to be a good starting point for this Mathematical inquiry, should it be made... Maybe I should phrase this a little bit better... Maybe it's something like (as a future goal for the Mathematicians of the world), "for every image compression algorithm X, show/prove that X is related to <parent Mathematical principle involving matrices>"... Or something like that... Sort of like a grand unifying theory of image compression... Anyway, your comments are highly interesting. It seems like you might be part of the way there for something like a rigorously mathematically unified (and proven!) future understanding of image compression!
  - wiml 3y ago
    I don't think that it's truly universal, but quite a few image compression schemes have a similar structure if you stand back and squint: 1. Use a reversible linear transform to transform the image into some other space. (It'll still require the same amount of data to represent) 2. Throw away a bunch of the values (set them to zero, or round them to low precision, etc) 3. Now that there are some repetitive zeroes or whatever, a conventional data compression algorithm (like LZW, Huffman, or interval/arithmetic) can make it smaller Even simple things like resizing an image smaller can be fit into this framework: step 1 is a simple blur, step 2 sets a bunch of pixels to zero, step 3 discards them. (I don't think fractal compression can be fit into this framework, but I could be wrong. That's the only exception I can think of offhand.)
    - 3y ago
deleted 3y ago
[deleted]

jeffrallen 3y ago

I would just like to say to linear algebra students today: you are so lucky to have explanations like this, and the Wikipedia article on eigenvalues available to you. In 1990 when I studied linear algebra, I had the book and my professor's explanations and neither were good enough. What a time to be a student!

nerdponx 3y ago
Not to mention this contains good examples of effective Numpy and Matplotlib usage. It can be really hard to figure out how to do that stuff on your own.
deleted 3y ago
[deleted]
Mandelmus 3y ago
As a current compsci masters student at ETH Zurich: yes, having those explanations is wonderful, but that just means that topics like SVD and PCA are taken for granted now, and the things that we need to chew on are things for which no nice canonical explainers have been created (and that likely weren’t taught in 1990). Personally I think that innovation in explanation/illustration of abstract mathematical topics is one of the most valuable kinds of progress, but it’s rarely talked about as such. When someone comes up with the right framework, visualisation, or metaphor for explaining a complex and abstract subject in a way that induces “the right” mental model, and this new teaching “tool” proliferates, that is just a beautiful thing to see.
LoganDark 3y ago
The problem is that since explanations like this exist, I don't know how to figure this kind of stuff out like how you did!

radioactivist 3y ago

One small point: since the original image was 1 byte per pixel this SVD is storing the singular values and vectors in 8 byte double precision floats. Using doubles the SVD data is ~ 2.7x larger than the original image at n=60 (2*60+1 = 121 vectors stored vs. the original 360 is a factor of 1/3 then going from 1 to 8 bytes per element), so to get any compression at all you'd need to go to ~ 1-2 bytes per element. I think for a fair comparison for any actual compression you'd need to consider the effects of quantization of the SVD output itself (in say the rows/columns of U,V alone, since you can keep the singular values at high-precision w/o appreciable cost). [I'd guess they'd be ok for 2 bytes/element, but 1 byte might be a problem].

vitus 3y ago

This is hinted at very briefly in one code comment [0] in the article, but this application of SVD is a well-known (to the point that it's even taught in university) method for dimensionality reduction, and typically referred to as Principal Components Analysis (PCA) [1]. [0] Said code comment is "# Plotting the principal components". [1] https://en.wikipedia.org/wiki/Principal_component_analysis https://en.wikipedia.org/wiki/Principal_component_analysis

secret-noun 3y ago
I was just looking back into my 8-year-old repo of my university project for this.

hyperific 3y ago

See also https://timbaumann.info/svd-image-compression-demo/ https://timbaumann.info/svd-image-compression-demo/

_kb 3y ago
And another great resource here for the same principles (so to speak…) but an audio context: https://www.isik.dev/posts/Eigentechno.html https://www.isik.dev/posts/Eigentechno.html

yuji_itadori 3y ago

SVD is also the back bone for DMRG in the study of quantum groundstates

dgreensp 3y ago

I played with this stuff in high school and college. Principle Component Amalysis (PCA), as another commenter said. One small quibble, with JPEG you don’t “lose” the “high-frequency” data; that would blur the image. You approximate it, so you could argue you “lose” some of it. JPEG is not very good at compressing high-frequency data, which is basically the edges of things, so if your JPEG has sharp edges, you are not losing much high-frequency data, just compressing everything else.