3
$\begingroup$

Suppose that we have an $m\times n$ matrix $A$ of rank $n$, whose entries are 8-bit unsigned integers obtained from a grayscale image. Now we want to apply SVD to $A$ and to use the first $k$ singular values to construct the the best rank-$k$ approximation of $A$ to accomplish compression for data storage.

I understand that for a floating-point image, the compression rate for SVD is

$$\frac{mn}{k(m+n+1)},\tag{1}$$

as mentioned in a lot of places including some textbooks. For example, a quick internet search gives us this article and this convenient demo link.

Coming back to our case, the entries of $A$ are 8-bit unsigned integers, while we still need to use floating points (32 bits or 64 bits) for the storage of the singular values and vectors (because 8-bits do not seem enough for the precision), it would seem that the compression rate for this case should become

$$\frac{mn}{4k(m+n+1)}, \quad\text {or} \quad \frac{mn}{8k(m+n+1)}.\tag{2}$$

This would render this compression scheme not practical in most cases. For example, using the demo link above, for that default image there, we need at least the first 100 singular values for a less-than-satisfactory compressed image. Using Formula $(1)$, that is assuming the original image is using the floating point data type, the compression rate is $2.40$; but assuming the original image is using the 8-bit unsigned integer data type, using Formula $(2)$, the compressed image becomes at least $0.6$ times bigger than the original one.

Does SVD compression only work for floating point images? What am I missing here?

$\endgroup$
  • $\begingroup$ dsp.stackexchange.com $\endgroup$ – Rodrigo de Azevedo Mar 26 at 6:48
  • $\begingroup$ Where are you getting these expressions for the compression rate from? $\endgroup$ – D.W. Mar 26 at 8:06
  • $\begingroup$ @D.W. The first formula shows up in a lot of places talking about this topic, including some textbooks. A quick search on the internet gives academia.edu/6024031/… and timbaumann.info/svd-image-compression-demo $\endgroup$ – Peradventure Mar 26 at 9:36
  • 1
    $\begingroup$ Right! uint8 to be exact, economically used for storing integers in the ranger of [0,255]. $\endgroup$ – Peradventure Mar 26 at 11:48
  • 1
    $\begingroup$ If you'd like us to check the correctness of your reasoning, it would be helpful to provide your reasoning and your assumptions in the question. For example, why do you conclude that it is not practical? Don't just put clarifications into the comments -- please edit the question to incorporate them there, so people don't have to read the comments to understand your question. P.S. Please don't cross-post on more than one SE site. $\endgroup$ – D.W. Mar 26 at 19:01
1
$\begingroup$

Does SVD compression only work for floating point images?

It seems quite obvious that it works for arbitrary images. Whether you are satisfied with the amount of compression or not doesn't really change the fact that it works.

I think looking at the compression ratio is going to lead to misleading results. Suppose you take two images: $I_1$ uses 8-bit RGB, and $I_2$ is the same image but captured using 24-bit RGB. Note that it is often fairly challenging to distinguish between two such images, and the differences are often perceptually minor. Now suppose you compress both with lossy compression. Suppose that both compressed images happen the same size. Then the compression ratio of $I_1$ is 3x worse than the compression ratio of $I_2$. Does that mean that compression doesn't work for 8-bit RGB images? No, it means that $I_2$ has a bunch of extra information that isn't semantically relevant. Thus, a compression algorithm that throws away this irrelevant information will achieve a higher compression ratio. That's not because the compression algorithm is better; it's just a reflection of the fact that $I_2$ has more irrelevant information (or information with low relevance).

And this is exactly the situation you're in. There is no way that the low 8 bits of those 32-bit floating point numbers are perceptually meaningful; no human is going to be able to perceive those. So, if you're capturing an image with 32-bit floats, then some of the bits of those floats are pure noise that are perceptually completely irrelevant. So, of course a compression algorithm that throws away that irrelevant information is going to achieve a higher compression ratio. Does that mean that compression on 8-bit images doesn't work? No, it just means there was less irrelevant information to throw away. This phenomenom is not specific to SVD-based compression; it will likely be true for any form of good lossy compression.

I can always make the compression ratio arbitrarily good by appending a bunch of irrelevant useless information to the input, and then modifying my compression algorithm to throw away the irrelevant information. That doesn't mean I have a better compression algorithm, or that the compression algorithm doesn't work or is unacceptable on the original images.

For all of these reasons, I think a better way to compare the two schemes is by the size of the compressed image, not by the compression ratio. And both variants you describe achieve the same size compressed image, so the apparent difference evaporates.

Second, when you're doing your comparison, there is no reason why you need to hold $k$ fixed. Usually we think of lossy compression as a tradeoff between the size of the compressed image vs the perceptual quality. You have two tunable parameters: $k$, and the number of bits of precision that use for the entries of the outputs of the compression. You are free to choose those arbitrarily to maximize the perceptual quality of the image, for a given image. For instance, instead of using one value of $k$ and 32-bit floats, you might do better to double $k$ and use 16-bit floats. Probably only empirical experiments can help you set those parameters in the optimal way... but you shouldn't assume what the optimal setting will be, or that it will necessarily be the same for both settings (both 8-bit inputs vs 32-bit inputs).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for writing up such a long answer! However, I think our definitions of 'compression' don't agree. My understanding of SVD compression is that it is intended to save storage space while producing negligible visual differences. If the compressed image costs more storage space, then it is not a compression. Wikipedia seems to agree on this: en.wikipedia.org/wiki/Image_compression. I in fact tried it on Matlab, and didn't find the SVD compression scheme able to achieve the compression goal for uint8 images. $\endgroup$ – Peradventure Mar 27 at 2:34
  • $\begingroup$ The compression rate of the original file vs the compressed one remains unchanged if you add in redundant information, so you don't actually make it arbitrarily good doing that. $\endgroup$ – Peradventure Mar 27 at 2:38
  • $\begingroup$ @Peradventure, it might be helpful to describe the details of the experiments you did in the question. Ultimately how well a compression algorithm works is an empirical matter, so the details of those experiments may matter. Your second comment (about the compression rate) is not accurate. If I take a 2KB byte and compress it to 1 KB, the compression ratio is 2; then add 1 MB of irrelevant information to the original, and compress it to 1 KB, the compression ratio is about 1000. $\endgroup$ – D.W. Mar 27 at 3:29
  • $\begingroup$ We are interested in compressing File 1, which is of size 2KB, compressing it into File 2, which is of size 1KB. Now we add 1MB of irrelevant information to File 1, we obtain File 3, which is then compressed to File 2 again. The compression ratio of File 1 into File 2 is still 2. We are interested in compressing File 1, not File 3. Not matter what you do, we always start at 2KB and end up at 1KB, hence the compression rate remains the same. What I was saying in the question is: if File 1 is using uint8, then the File 2 we obtained using SVD in most cases becomes bigger than File 1. $\endgroup$ – Peradventure Mar 27 at 4:51
  • $\begingroup$ @Peradventure, I don't agree, and I don't think you understood my point. I suggest that you be specific: identify a specific image, and its size with 8-bit RGB and with 32-bit float RGB, and the size of the compressed version of each. If SVD-compression applied to the 8-bit RGB image yields an image that is larger than the original, I suspect you may find that rounding the 32-bit floats to 8-bit RGB may be a better compression algorithm than SVD-compressing the 32-bit floats. That would lend a different interpretation on things. But that needs you to do that measurement. $\endgroup$ – D.W. Mar 27 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.