Hacker News Reader

Comment by orlp | Hacker News Reader

The source for many of these images appears to be the 2014 Code Golf Stack Exchange thread "Images With All Colors": https://codegolf.stackexchange.com/questions/22144/images-wi...

Lots of interesting imagery, with source included.

Indeed, here's my version of the implementation, it's what's currently my wallpaper on most of my machines:

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.

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.

[0] https://www.w3.org/TR/PNG/#9Filters

This is the best layman's explanation of JPEG compression that I've ever seen.

I feel it's very much spot on, and true to the math within.

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.

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.

  <?xml version="1.0" encoding="UTF-8"?>
  <svg width="256" height="65536" version="1.1" viewBox="0 0 256 65536" xmlns="http://www.w3.org/2000/svg" xmlns:cc="http://creativecommons.org/ns#" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#">
   <defs>
    <linearGradient id="a" x2="256" y1="32768" y2="32768" gradientUnits="userSpaceOnUse">
     <stop stop-color="#f00" offset="0"/>
     <stop stop-color="#ff0" offset=".166666667"/>
     <stop stop-color="#0f0" offset=".333333333"/>
     <stop stop-color="#0ff" offset=".5"/>
     <stop stop-color="#00f" offset=".666666667"/>
     <stop stop-color="#f0f" offset=".833333333"/>
     <stop stop-color="#f00" offset="1"/>
    </linearGradient>
    <linearGradient id="b" x1="128" x2="128" y1="0" y2="65536" gradientUnits="userSpaceOnUse">
     <stop offset="0"/>
     <stop stop-color="#808080" stop-opacity="0" offset=".5"/>
     <stop stop-color="#fff" offset="1"/>
    </linearGradient>
   </defs>
   <metadata>
    <rdf:RDF>
     <cc:Work rdf:about="">
      <dc:format>image/svg+xml</dc:format>
      <dc:type rdf:resource="http://purl.org/dc/dcmitype/StillImage"/>
     </cc:Work>
    </rdf:RDF>
   </metadata>
   <rect width="256" height="65536" fill="url(#a)" stroke-width="24" style="mix-blend-mode:normal"/>
   <rect width="256" height="65536" fill="url(#b)" stroke-width="24" style="mix-blend-mode:normal"/>
  </svg>

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.

  <svg width="4096" height="16384" version="1.1" viewBox="0 0 4096 16384" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
   <defs>
    <linearGradient id="a" x2="4096" y1="8192" y2="8192" gradientUnits="userSpaceOnUse">
     <stop stop-color="#f00" offset="0"/>
     <stop stop-color="#ff0" offset=".125"/>
     <stop stop-color="#0f0" offset=".25"/>
     <stop stop-color="#0ff" offset=".375"/>
     <stop stop-color="#00f" offset=".5"/>
     <stop stop-color="#f0f" offset=".625"/>
     <stop stop-color="#f00" offset=".75"/>
     <stop stop-color="#000" offset=".875"/>
     <stop stop-color="#fff" offset="1"/>
    </linearGradient>
    <linearGradient id="b" x1="2048" x2="2048" y2="16384" gradientUnits="userSpaceOnUse" xlink:href="#a">
     <stop stop-color="#808080" offset="0"/>
     <stop stop-color="#808080" stop-opacity="0" offset=".25"/>
     <stop stop-color="#fff" offset=".5"/>
     <stop stop-color="#fff" stop-opacity="0" offset=".75"/>
     <stop offset="1"/>
    </linearGradient>
   </defs>
   <rect width="4096" height="16384" fill="url(#a)" stroke-width="24" style="mix-blend-mode:normal"/>
   <rect width="4096" height="16384" fill="url(#b)" stroke-width="24" style="mix-blend-mode:normal"/>
  </svg>

An image with the upper half black and the lower half white can be compressed to a few bytes, regardless of its size.

An image with the same pixels but randomly arranged cannot really be compressed.

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)".

Hope this makes sense and helps.

I apologize for my ignorance on this subject. Please ignore the parent comment.

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.

I'll have to look into it.

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.

> 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.

You can start here: Huffman Coding which gives a really good overview of one kind of coding.

[1] https://en.wikipedia.org/wiki/Huffman_coding

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.

My favourite: https://allrgb.com/order-from-chaos

It uses simulated annealing to arrange the colours smoothly.

Reply on news.ycombinator.com