Sorry for the stupid question, I understand so little about image encoding. If each image has ALL the RGB colors ("not one color missing, and not one color twice") how can they be so different in size? How does JPG/PNG encode a pixel of information, isn't it always the same size?
For PNG, it can support what's known as "filtering" [0], where it's based on the difference between the pixel and the one to the left/top of it. So if you have the values { 1, 2, 3, 4, 5, 6 }, then the differences will be { 1, 1, 1, 1, 1, 1 }, which is very compressible to DEFLATE (analogy in English, "6 1's" is shorter than "1 1 1 1 1 1").
JPEG uses a very different technology; it breaks the image into 8x8 blocks, and tries to fit the resulting 64 pixels to a gradient (yes, I know I'm simplifying). So pixels that tend to be "smooth" and "gradient-like" will compress much better than random noise.
This is why I like things like svg for pure gradient graphics. Uncompressed plaintext can be used to render all RGB colors with a similar filesize as png.
I'll see if I can come up with a clever way do it without having to resort to tricks that move the goalposts (such as having repeated colors).
Okay I think I got pretty close. The png export doesn't have 16.7 million colors, so there must be some error in my logic.
Okay okay okay. I got up to 10.7 million unique colors in a 67 MP raster. I expect at least about 30% overlap because the vertical gradient wastes 25% of space and the rightmost nodes of the horizontal gradient are mostly replicated in other places. As for why it doesn't have full coverage and why there are so many repeated colors: idk yet and have to stop for today.
A lot of encoders try to exploit patterns in the data, and so instead of saving the "raw" data, they save the "pattern", with the idea being that the pattern will be smaller. Different encoding formats use different patterns, so you get different file sizes
I'd imagine with a compression such as saving things like 255,255,255 as 3255 or a series such as #98DEEE and #EEEE89 as 98D(7E)89, only not those examples and more sophisticated
In short, image files don't include all RGB colors. They basically include a line like "usesColorSpace: 'RGB'". Only the decoder needs to know how to interpret the RGB colorspace.
When you save in image in JPG, it's compressed using an algorithm that gets it "pretty close" to the source image. The software doing the JPG decoding (browser, image viewer, etc.) basically reverses this algorithm to display the image back to you. For JPG, this compression is "lossy" and so you've lost detail from the original source image.
PNG is a lossless image format, but it basically works the same way without sacrificing the source image's quality.
The "standard" for an image format dictates how an encoder creates the image and how a decoder displays the image. Since everyone is "on the same page," the individual image files only need to contain what they need to -- basically, "this pixel = RGB(0,1,2)".
Imagine how small the file would be if it were a couple of for loops. Compression can take advantage of the colors of adjacent/near by pixels, adjacent pixels in time (for video), less bits for more common situations, removing differences that are invisible, etc.
Gotta ask. Has anyone worked on image compression using machine learning? (that sounds like an obvious thing to do). It would be funny to end up with an algorithm no one understands.
Yup. Consider that all compression boils down to some form of a model that can predict the next bits of information, and then an encoding that only includes the deviation of the actual data from the prediction. Machine learning gives us new ways of making predictions.
Given both the financial value of image compression (given the amount of video shoved down the net) and the asymmetry of codec (it's OK to use resources to compress, not so much for decompress), I'd expect some real money to be spent in this area.
> Has anyone worked on image compression using machine learning?
Dunno about the state of the art, but pretty much every ml tutorial has a section titled "Image Compression Using Autoencoders" right at the beginning. It's the Hello World of ml. The perceptual quality vs file size curve for such a simple network is pretty mediocre, but I'm sure you could do better if that was your goal.
A lot of old video games with impressive graphics were implemented sort of like that. Rather than storing bitmap data, the algorithm to render the artwork would be executed on the fly. It was actually faster than doing otherwise, since hard drives were so slow and the algorithm itself could fit in ram.
Tangentially related is the crash bandicoot game on the playstation. The developers figured out that untextured polygons were way faster to draw than textured polygons, and so they made the player character model out of tons of
tiny colored polygons rather than fewer larger textured polygons. The result was a significantly better looking graphic for the same rendering time.
Both PNG and JPG use compression (lossless in case of PNG, lossy in case of JPG) to store the image.
Now your question is basically reduced to "how can text files with same number of bytes, each having ALL the ascii codes, compress to files of such different size". The answer is that it MUST necessarily be so. You can't have a one-to-one map from [2]^N to [2]^K where K < N.
As a human analog, just think about how you would write down instructions for someone to recreate the image.
For the ordered image:
"Make a 16 by 16 grid of boxes, each getting redder from left to right and top to down. Inside each box make a 16x16 grid of boxes getting greener, and inside each of those boxes make a 16x16 grid of pixels getting bluer". Done.
Vs. the random image:
"Make a blueish red pixel with a bit of green. Then make a reddish blue pixel with a a moderate amount of green. Then make a brownish pixel. Then make a greenish pixel..." That will go on for about 16 million sentences!
Image compression is simply coming up with a language that's good for describing images, and then an algorithm for writing succinct descriptions in that language. Rather than being human friendly languages (a modest number of complex words made from an alphabet), they are computer friendly languages (a ton of simple words made from 0s and 1s.)
JPEG compression separates out the image into "component" images. One component is brightness, another is hue, and a third is saturation. Each of those components map nicely to how human vision works. In particular, brightness needs high resolution and precision. Hue needs high precision but resolution doesn't matter. Saturation doesn't need high resolution or precision. Therefore, each component can be compressed differently and independently from each other. The component images are further broken up into a grid of 8x8 boxes, and then each of those boxes are approximated via a weighted sum of reference box images (the encoder and decoder have a dictionary of reference boxes they both agree to use.) For each box, only the weights are saved. The weights themselves can have varying precision, and that's basically you're controlling when you set the "jpeg quality". Higher quality jpegs have more precision in their weights, and lower quality jpegs have less precision in their weights.
If you consider the image in terms of the differences between adjacent pixels you can get the same value almost across the entire image.
PNG works like this. You can run each horizontal row through any one of a variety of delta encoders that are suitable for different situations. The goal is to minimize the range of values and maximize the repetition before you pass the encoded deltas through a dictionary based compressor. Pictures like this are near optimal for this approach.
It's quite simple actually. If you have 8 bits per color channel, you can have 256 values per channel (or 16777216 in total if you look at it as a 24 bit value).
A rectangle of 256*256 pixels can display all possible combinations for two color channels, with the third one held constant. If you step through every possible value of the third channel, you end up with 256 of those pictures, which can be arranged neatly in a 16*16 grid (16*16 = 256).
Because each image has 256*256 pixels, and we have 16*16 of them, we end up with a 4096*4096 pixel image (because 16*256 = 4096), which now holds every possible combination of the 3 color channels.
Because this systematic approach creates neatly ascending rows of color values, the resulting image compresses quite well.
I think you missed my attempt at humor - as did my downvoters. Digital color storage approximates the real world, which has an infinite number of colors for a given portion of the EM spectrum. So "All" suggests "we got 'em all!" as opposed to 2^24.
I was with my cousin in law at the Getty a few years ago and we were talking about how much information is lost when you look at a screen. The world is a lot richer than a mere 16,777,216 colors. I think there are things about our sensation of colors that don't have names yet -- there are just things that greens and browns do that I have not been able to find words to describe. There are interactions light has with materials that we have not separated out into "colors" or "textures" yet.
If I hadn't been told what this is, I would never have guessed that it's a representation of all colors. I know it's all the colors -- I can zoom in and see lots of different colors -- but why doesn't it look like that? My initial description would have been "purple and green squares". I might elaborate that it's "purple and green squares with a bit of blue separating the rows". But why doesn't it feel like all colors? Because of the way it's organized? For the same reason that his randomized pixels looks like a grey blob?
You can't see the individual pixels. This is illustrated better by the second image, in which the same pixels occur in a random order. It is mostly a uniform gray, despite the fact that almost all of the pixels are not gray.
With RGB, a lot of values are wasted encoding colors that are perceptually very similar. Many colors that are “interesting” to humans are encoded in a narrow slice of the RGB cube. Much of the cube is a deep ocean of indistinguishable bluish shades.
Video traditionally uses various luminance+chroma color spaces, which are more perpetually effective than RGB and allow for easy subsampling to save bandwidth on the less important color data.
I want to do a kind of bubble sort on the pixels and see what it looks like.
To be specific, let's say we take two pixels at random and compare each to their 8 neighbors. If they are closer to the surrounding pixels when swapped, then swap them. Repeat.
I may try this, but I'm lazy, so in case someone else wants to...
I actually just did try it! I'm finding that random pixels don't really get swapped. Except along comparatively uncommon borders between squares, pixels are already very similar to their immediate neighbors. Creating a video with 10000 swaps per frame, I found no successful swaps in 50 frames.
That said, I bet there's some other criterion that would have the desired effect.
I don't think this has a stable "end" it can reach. Diagonals of pixels of the same x,y coordinates in linearly adjacent (green incrementation) cells would trigger a swap as the diagonal is +-1 in both the red and blue channel but the same pixel offset in a different cell is +-1 only in the green channel. I can't think of any 2d arrangement where the difference of a pixel in a cell to all 8 of it's neighbors could be 1 for every pixel so this "sort" would really just cycle pixels around based on the order your random number generator happens to pick swappable diagonals by chance. As such it'd never converge and look like slowly adding distance capped noise over time. The seams between cells would only seek to increase the cap on this noise from 2 to 255. 255 being the minimal maximum distance I can imagine for a sorted grid of 2d pixels (i.e. I think this image is a min-max optimal ordering).
It'd also take a ridiculous number of iterations to really notice the noise being added. Perhaps unfeasibly many if you're wanting to go deep and truly rely on random comparisons.
The process would have to stop eventually, because each swap reduces the sum over all pixels of the distances to adjacent pixels, and there is no infinite descending sequence of positive whole numbers.
That's similar to the process used to generate https://allrgb.com/order-from-chaos except that the pixels used in that algorithm weren't chosen entirely at random, and they sometimes randomly allow a swap even when it increases the difference, in order to escape from local optima ('simulated annealing').
The reason it specifically looks like "purple and green" squares is because of how it's organized.
Each of those smaller squares is made by having red at 0 and blue at 0 at the top left corner, then increasing each along one of the x/y axes until you have red 255 and blue 255 at the bottom right corner. The "green" value is constant for each square, and just increases by one for each subsequent square packed in. At distant/normal viewing you're not going to resolve all those individual colors but more see the averages (to say nothing of the computer itself averaging things to make a zoomed out view or a smaller-dimension rendering).
So you basically have subsquares that start, on average, as "purple" (or let's say magenta). They have no or very little green and mostly are mixtures of red and blue. As you go toward the bottom, green increasingly dominates as what were once the darkest parts of each sub-square become just green and what were the magenta parts tend toward white. Blur your vision a little and the image just looks like a magenta-to-green gradient.
You would be able to construct this image so it would still contain "all the RGB colors" but looked from afar instead like "yellow and blue squares" or "cyan and red squares" instead, just by changing your method for constructing/organizing it. There'll be variation in how well these different variants "blend" and so on just based on how we perceive the different colors, of course.
In terms of that perceptual variation, take for example this: https://allrgb.com/thingy , in particular the little preview in the left. This is what would be the "yellow to blue" kind of ordering, but it doesn't really "blend" as much. The bottom subsquares in particular read as "cyan/magenta/blue" combinations rather than just "blue", and in the top "yellow" isn't really as dominant either. Blur your vision again though and it's a yellow-to-blue gradient.
If you just think about it as a cube of colour with redness (0-255) on one axis, same with green and blue on the others and then taking 256 slices of that cube it all makes sense intuitively.
I assume it's because the image follows very specific patterns that the PNG algorithm is able to compress it so much? Each individual square has a set green value, the pixel to the right is red + 1, and the pixel below is blue + 1.
I was trying to figure out how it's possible to store 16 million separate colors in 58,000 bytes. Looks like it's storing information about the gradient patterns, and not each individual color.
I crafted a PNG image that squeezes all 16777216 colors into just 49131 bytes. This comes very close to the 1032:1 maximum compression ratio that DEFLATE compression can achieve on any data.
This is fantastic! The actual image in the post looks almost like <hr> so linking it here: https://i.stack.imgur.com/hPcJr.png (it also gzip -9's to just 253 bytes and to 241 bytes with bzip2 -9)
Why is it that the image with the scrambled pixels looks mostly grey, even though it contains all the colors, just scrambled? Even the effect is amplified when the image is zoomed out
To add to this, the amount of energy actually being sent out of your screen isn't a linear function of the RGB values. So to find what the mixture will look like you have to convert them to linear values using the formula here https://en.wikipedia.org/wiki/SRGB, then take the average, then convert back. So '50% gray' is actually #979797.
This should match the level of grey which the image appears to be if you view it at full resolution. It will only match the zoomed out image if your computer also uses the correct averaging formula.
The small image on the main page is a 256x256 version of a full-size... 4096x4096 image.
So each pixel in the small version is going to actually be an averaging of a 16x16 block of original pixels. Because they're randomly distributed, mostly that averaging is going to result in medium gray. Zooming out is going to do something similar (though the exact effect would depend on how the zoom algorithm works).
Plus, your eyes/brain are going to do some smoothing/averaging of their own even where the screen is able to display individual 1:1 source pixels (consider for example that every pixel on what's probably an LCD you're viewing the image on is itself some combination of red, green and blue subpixels).
The image data is stored such that downloading the first section of the file gets you enough information to display a low-resolution version of the image, and continuing the download allows for progressive refinement of the image.
> Edit 2011-06-30: Was inspired by one of the comments to try and compress the 58 kB png file. IzArc can create a 7z file which is only 705 bytes large! That is 1/71436th the size of the uncompressed image in Tiff format. That’s pretty impressive stuff!
This is hard to believe. An already compressed PNG can be substantially re-compressed by a generic lossless process?
> And how about a little mathematical challenge: What are the chances that, by randomizing the pixels in the (randomized) image above, I would get the (ordered) version at the top?
If I'm not mistaken, this would be `(2^24) permutation (2^24)`, aka `(2^24)!`, an unbelievably large number!
77 comments
[ 2.8 ms ] story [ 145 ms ] threadLots of interesting imagery, with source included.
My background, I took a bit of liberty with the colors: https://imgur.com/a/OFcsjZn
And an animated version: https://youtu.be/mO7VuqLNK1w
Fun use case to play around with Octrees to try and speed it all up.
JPEG uses a very different technology; it breaks the image into 8x8 blocks, and tries to fit the resulting 64 pixels to a gradient (yes, I know I'm simplifying). So pixels that tend to be "smooth" and "gradient-like" will compress much better than random noise.
[0] https://www.w3.org/TR/PNG/#9Filters
I feel it's very much spot on, and true to the math within.
I'll see if I can come up with a clever way do it without having to resort to tricks that move the goalposts (such as having repeated colors).
Okay I think I got pretty close. The png export doesn't have 16.7 million colors, so there must be some error in my logic.
1370 bytes as a human readable plaintext file.
711 bytes as a 7-zip.
658 bytes as a usable compressed svgz file.
159936 bytes as a png.
An image with the same pixels but randomly arranged cannot really be compressed.
When you save in image in JPG, it's compressed using an algorithm that gets it "pretty close" to the source image. The software doing the JPG decoding (browser, image viewer, etc.) basically reverses this algorithm to display the image back to you. For JPG, this compression is "lossy" and so you've lost detail from the original source image.
PNG is a lossless image format, but it basically works the same way without sacrificing the source image's quality.
The "standard" for an image format dictates how an encoder creates the image and how a decoder displays the image. Since everyone is "on the same page," the individual image files only need to contain what they need to -- basically, "this pixel = RGB(0,1,2)".
Hope this makes sense and helps.
Gotta ask. Has anyone worked on image compression using machine learning? (that sounds like an obvious thing to do). It would be funny to end up with an algorithm no one understands.
Given both the financial value of image compression (given the amount of video shoved down the net) and the asymmetry of codec (it's OK to use resources to compress, not so much for decompress), I'd expect some real money to be spent in this area.
Dunno about the state of the art, but pretty much every ml tutorial has a section titled "Image Compression Using Autoencoders" right at the beginning. It's the Hello World of ml. The perceptual quality vs file size curve for such a simple network is pretty mediocre, but I'm sure you could do better if that was your goal.
Tangentially related is the crash bandicoot game on the playstation. The developers figured out that untextured polygons were way faster to draw than textured polygons, and so they made the player character model out of tons of tiny colored polygons rather than fewer larger textured polygons. The result was a significantly better looking graphic for the same rendering time.
Now your question is basically reduced to "how can text files with same number of bytes, each having ALL the ascii codes, compress to files of such different size". The answer is that it MUST necessarily be so. You can't have a one-to-one map from [2]^N to [2]^K where K < N.
Except that you've already noted that JPG is a lossy compression scheme, so it doesn't matter that a one-to-one map isn't possible.
[1] https://en.wikipedia.org/wiki/Huffman_coding
For the ordered image: "Make a 16 by 16 grid of boxes, each getting redder from left to right and top to down. Inside each box make a 16x16 grid of boxes getting greener, and inside each of those boxes make a 16x16 grid of pixels getting bluer". Done.
Vs. the random image: "Make a blueish red pixel with a bit of green. Then make a reddish blue pixel with a a moderate amount of green. Then make a brownish pixel. Then make a greenish pixel..." That will go on for about 16 million sentences!
Image compression is simply coming up with a language that's good for describing images, and then an algorithm for writing succinct descriptions in that language. Rather than being human friendly languages (a modest number of complex words made from an alphabet), they are computer friendly languages (a ton of simple words made from 0s and 1s.)
JPEG compression separates out the image into "component" images. One component is brightness, another is hue, and a third is saturation. Each of those components map nicely to how human vision works. In particular, brightness needs high resolution and precision. Hue needs high precision but resolution doesn't matter. Saturation doesn't need high resolution or precision. Therefore, each component can be compressed differently and independently from each other. The component images are further broken up into a grid of 8x8 boxes, and then each of those boxes are approximated via a weighted sum of reference box images (the encoder and decoder have a dictionary of reference boxes they both agree to use.) For each box, only the weights are saved. The weights themselves can have varying precision, and that's basically you're controlling when you set the "jpeg quality". Higher quality jpegs have more precision in their weights, and lower quality jpegs have less precision in their weights.
PNG works like this. You can run each horizontal row through any one of a variety of delta encoders that are suitable for different situations. The goal is to minimize the range of values and maximize the repetition before you pass the encoded deltas through a dictionary based compressor. Pictures like this are near optimal for this approach.
It uses simulated annealing to arrange the colours smoothly.
A rectangle of 256*256 pixels can display all possible combinations for two color channels, with the third one held constant. If you step through every possible value of the third channel, you end up with 256 of those pictures, which can be arranged neatly in a 16*16 grid (16*16 = 256).
Because each image has 256*256 pixels, and we have 16*16 of them, we end up with a 4096*4096 pixel image (because 16*256 = 4096), which now holds every possible combination of the 3 color channels.
Because this systematic approach creates neatly ascending rows of color values, the resulting image compresses quite well.
The 3 colours are 100% on one surface and 0% on the opposite. The cube being 256x256x256 pixels in size.
Then in that image you’re showing slices of that cube.
Turns out, it’s also the way everyone else likes to visualise colours. That’s why it’s called a colour space I guess.
For png, you end up with a variety of settings all the way from "very weak" up to "weak".
Color selector where you pick the color from the randomized image with an eyedropper tool.
The colors are all in there, what's there to complain about?
https://colornames.org/
I was bummed to realize that the api and the zip file only expose the top name for any color at one time. It’d be cool to have access to all the data.
https://davidbuckley.ca/post/colour-sort/
Edit: Yes: https://allrgb.com (should have googled)
If you zoom in further, you'd soon realize your screen is nothing but pure red, green and blue subpixels at varying intensities.
Because RGB is not a perceptual color space.
With RGB, a lot of values are wasted encoding colors that are perceptually very similar. Many colors that are “interesting” to humans are encoded in a narrow slice of the RGB cube. Much of the cube is a deep ocean of indistinguishable bluish shades.
Video traditionally uses various luminance+chroma color spaces, which are more perpetually effective than RGB and allow for easy subsampling to save bandwidth on the less important color data.
I want to do a kind of bubble sort on the pixels and see what it looks like.
To be specific, let's say we take two pixels at random and compare each to their 8 neighbors. If they are closer to the surrounding pixels when swapped, then swap them. Repeat.
I may try this, but I'm lazy, so in case someone else wants to...
That said, I bet there's some other criterion that would have the desired effect.
It'd also take a ridiculous number of iterations to really notice the noise being added. Perhaps unfeasibly many if you're wanting to go deep and truly rely on random comparisons.
Each of those smaller squares is made by having red at 0 and blue at 0 at the top left corner, then increasing each along one of the x/y axes until you have red 255 and blue 255 at the bottom right corner. The "green" value is constant for each square, and just increases by one for each subsequent square packed in. At distant/normal viewing you're not going to resolve all those individual colors but more see the averages (to say nothing of the computer itself averaging things to make a zoomed out view or a smaller-dimension rendering).
So you basically have subsquares that start, on average, as "purple" (or let's say magenta). They have no or very little green and mostly are mixtures of red and blue. As you go toward the bottom, green increasingly dominates as what were once the darkest parts of each sub-square become just green and what were the magenta parts tend toward white. Blur your vision a little and the image just looks like a magenta-to-green gradient.
You would be able to construct this image so it would still contain "all the RGB colors" but looked from afar instead like "yellow and blue squares" or "cyan and red squares" instead, just by changing your method for constructing/organizing it. There'll be variation in how well these different variants "blend" and so on just based on how we perceive the different colors, of course.
In terms of that perceptual variation, take for example this: https://allrgb.com/thingy , in particular the little preview in the left. This is what would be the "yellow to blue" kind of ordering, but it doesn't really "blend" as much. The bottom subsquares in particular read as "cyan/magenta/blue" combinations rather than just "blue", and in the top "yellow" isn't really as dominant either. Blur your vision again though and it's a yellow-to-blue gradient.
If you just think about it as a cube of colour with redness (0-255) on one axis, same with green and blue on the others and then taking 256 slices of that cube it all makes sense intuitively.
I was trying to figure out how it's possible to store 16 million separate colors in 58,000 bytes. Looks like it's storing information about the gradient patterns, and not each individual color.
https://codegolf.stackexchange.com/a/217544/39242
This should match the level of grey which the image appears to be if you view it at full resolution. It will only match the zoomed out image if your computer also uses the correct averaging formula.
So each pixel in the small version is going to actually be an averaging of a 16x16 block of original pixels. Because they're randomly distributed, mostly that averaging is going to result in medium gray. Zooming out is going to do something similar (though the exact effect would depend on how the zoom algorithm works).
Plus, your eyes/brain are going to do some smoothing/averaging of their own even where the screen is able to display individual 1:1 source pixels (consider for example that every pixel on what's probably an LCD you're viewing the image on is itself some combination of red, green and blue subpixels).
The image data is stored such that downloading the first section of the file gets you enough information to display a low-resolution version of the image, and continuing the download allows for progressive refinement of the image.
This is hard to believe. An already compressed PNG can be substantially re-compressed by a generic lossless process?
If I'm not mistaken, this would be `(2^24) permutation (2^24)`, aka `(2^24)!`, an unbelievably large number!