4 ms·

You can't generate information from nothing. Compression based on sparsity seems to be making assumptions about the level of detail in a picture[1]. If you stor

You can't generate information from nothing. Compression based on sparsity seems to be making assumptions about the level of detail in a picture[1]. If you stored 20% of the pixels in Obama's face you may miss a spot of acne. I can't imagine trusting to this technique for pictures of the galaxy. After spending a bazillion dollars on a space telescope we aren't going to "throw away 80% of the pixels". [1] - I'm not certain of this deduction. Can somebody with more background confirm or deny?

dutchflyboy 17y ago
Isn't this a case where entropy shows it isn't possible? Once you degrade the quality/quantity of the information, you can't get it back. You can find a clever way to hide what you did, but this doesn't add information, you're just interpolating. This isn't bad however, as we normally don't use all data we could (do you look at your pictures with 400% zoom factor?), and a rescaled image can highlight some detail you would have missed. By the way, those bazillion dollars aren't wasted, because if you take the image, don't throw away pixels, but do as if it were a bigger image which had lost pixels, you can get something useful out of it.
- ars 17y ago
  > Isn't this a case where entropy shows it isn't possible? Most real world pictures are not random. So you can guess what it looks like from areas near it.
  - yummyfajitas 17y ago
    More precisely, the entropy of real world pictures is considerably lower than the entropy of all pictures (the vast majority of pictures are static).
- deleted 17y ago
  [deleted]
- iskander 17y ago
  This is more of a case where you aren't actually using all the information-bearing capacity of your pixels but are actually sampling from a much lower dimensional manifold. This isn't just interpolation and information need not be lost.
iskander 17y ago
The article focuses on "missing pixels" which doesn't have much to do with the original Candes paper. The usual setup for compressed sensing is that you're sampling the entire image one coefficient at a time in some "incoherent" basis (ie, noiselets). Thus, every little spot of Obama's acne may very well be reconstructed-- though more generally you're right, if the image is too sharp then something gets lost.
lmkg 17y ago
You're not exactly making assumptions about the level of detail. You're making assumptions about the compressibility and entropy of the data. A circle requires the same amount of data to represent whether its radius is R or 2R[1]. L1-minimization tries to find the smallest number of circles regardless of size, whereas traditional compression methods look for the largest circles regardless of number. It attempts to minimize the entropy of the result image (roughly), and all real pictures that aren't literally static have low entropy. A saw a presentation on this technique in college. Some of the details I saw escaped me, but one thing I remember is that the L1 decompression is optimal when it is "orthogonal" to the compression that it is reversing. Fourier-based compression schemes (including JPEG and MPEG, and even MP3) are "orthogonal" in the correct sense because they select based on size, preserving large structures better. Random sampling is "orthogonal" to basically all compression schemes, and tends to select more information from large structures as well. With a high-res bazilion-dollar space telescope, you're not going to throw away 80% of the pixels and reconstruct an approximation. Rather, you'll take all of the recorded pixels, and then reconstruct even more impressive astronomer porn at five times the resolution! [1] Well, close enough. If you store the circle as the (x,y) of the center and an integer radius R, then 2R takes 1 more bit. Storing R as floating-point means no difference. I don't know about other representations. Anyways, the point is, the image size of the feature is not strongly coupled to data size of the feature.
- messel 17y ago
  "more impressive astronomer porn at five times the resolution!" As long as we keep in mind that the filled in regions of space or background match the assumed entropy, I think it's worth doing. The applications of L1 appear to be limited to cases where the structure and assumptions match the dataset. Maybe there's an underlying pattern we're recreating? Something inherent to physical laws, fractal replication, etc. Your comment helped me to see that L1 isn't just a matter of interpolation but an assumed underlying pattern that is used to fill in or estimate the unknown data. Thanks.

dutchflyboy 17y ago

Isn't this a case where entropy shows it isn't possible? Once you degrade the quality/quantity of the information, you can't get it back. You can find a clever way to hide what you did, but this doesn't add information, you're just interpolating. This isn't bad however, as we normally don't use all data we could (do you look at your pictures with 400% zoom factor?), and a rescaled image can highlight some detail you would have missed. By the way, those bazillion dollars aren't wasted, because if you take the image, don't throw away pixels, but do as if it were a bigger image which had lost pixels, you can get something useful out of it.

ars 17y ago
> Isn't this a case where entropy shows it isn't possible? Most real world pictures are not random. So you can guess what it looks like from areas near it.
- yummyfajitas 17y ago
  More precisely, the entropy of real world pictures is considerably lower than the entropy of all pictures (the vast majority of pictures are static).
deleted 17y ago
[deleted]
iskander 17y ago
This is more of a case where you aren't actually using all the information-bearing capacity of your pixels but are actually sampling from a much lower dimensional manifold. This isn't just interpolation and information need not be lost.

iskander 17y ago

The article focuses on "missing pixels" which doesn't have much to do with the original Candes paper. The usual setup for compressed sensing is that you're sampling the entire image one coefficient at a time in some "incoherent" basis (ie, noiselets). Thus, every little spot of Obama's acne may very well be reconstructed-- though more generally you're right, if the image is too sharp then something gets lost.

lmkg 17y ago

You're not exactly making assumptions about the level of detail. You're making assumptions about the compressibility and entropy of the data. A circle requires the same amount of data to represent whether its radius is R or 2R[1]. L1-minimization tries to find the smallest number of circles regardless of size, whereas traditional compression methods look for the largest circles regardless of number. It attempts to minimize the entropy of the result image (roughly), and all real pictures that aren't literally static have low entropy. A saw a presentation on this technique in college. Some of the details I saw escaped me, but one thing I remember is that the L1 decompression is optimal when it is "orthogonal" to the compression that it is reversing. Fourier-based compression schemes (including JPEG and MPEG, and even MP3) are "orthogonal" in the correct sense because they select based on size, preserving large structures better. Random sampling is "orthogonal" to basically all compression schemes, and tends to select more information from large structures as well. With a high-res bazilion-dollar space telescope, you're not going to throw away 80% of the pixels and reconstruct an approximation. Rather, you'll take all of the recorded pixels, and then reconstruct even more impressive astronomer porn at five times the resolution! [1] Well, close enough. If you store the circle as the (x,y) of the center and an integer radius R, then 2R takes 1 more bit. Storing R as floating-point means no difference. I don't know about other representations. Anyways, the point is, the image size of the feature is not strongly coupled to data size of the feature.

messel 17y ago
"more impressive astronomer porn at five times the resolution!" As long as we keep in mind that the filled in regions of space or background match the assumed entropy, I think it's worth doing. The applications of L1 appear to be limited to cases where the structure and assumptions match the dataset. Maybe there's an underlying pattern we're recreating? Something inherent to physical laws, fractal replication, etc. Your comment helped me to see that L1 isn't just a matter of interpolation but an assumed underlying pattern that is used to fill in or estimate the unknown data. Thanks.