Image quantization

    Quantization - reducing the color of the image ( wiki ). Of course, now few people need it, but the task itself is interesting.


    Quantized Lena attracts attention.

    For example, the good old GIF format uses a palette with a maximum of 256 colors. If you want to save a series of your selfies as gif-animation (whoever needs it), then the first thing you, or rather the program that you will use for this, will need to do this - create a palette. You can use a static palette, for example web-safe colors , the quantization algorithm will turn out to be very simple and fast, but the result will be "not very". You can create the optimal palette based on the colors of the image, which will give the result most visually similar to the original.

    Алгоритмов создания оптимальной палитры несколько, каждый имеет свои плюсы и минусы. Я не стану утруждать читателя нудной теорией и формулами, во первых мне лень, во вторых большинству это не интересно – статью просто пролистают, рассматривая картинки.

    Далее вас ждёт скучное и непонятное повествование о методе медианного сечения, алгоритму рассеивания ошибок (шума квантизации) по Флойду-Стейнбергу (и не только), особенностях цветового восприятия человеческого глаза, а так же немного говнокода.

    Предыстория
    Давным-давно, когда Nokia была тёплой и ламповойdominated the smartphone market, and smartphone owners proudly called themselves “smartphones”, in those ancient times I wrote simple little programs on python for series60. The other day I came across a digging in the archives. GifTool - a program for creating gif-animations from a set of pictures. In it, I implemented quantization using the median section method, the LZW compression algorithm, the entire file structure was created independently, transparency was used for the pixels that did not change on the next slide, to reduce the final file size. I wanted to refresh my memory, see how it worked. I opened the code and ... It’s a feeling when you can’t figure out your ten-year-old shit. I didn’t know about PEP8 at that time, so the readability of the code was slightly less than no (then I liked minimalism, like many novice programmers). He cried, spat, refactored in PyCharm, figured out how he implemented the median section method, quickly threw a “dirty” script. Works! A palette is created, the output image is tolerable. And then I was bitten - can I achieve better results so that the picture visually is as close as possible to the original.

    So - the median section method. He is simple to disgrace. First of all, you need to make an RGB cube from all the unique colors of the image. Next, cut it along the longest side. For example, we have a range of red from 7 to 231 (length 231-7 = 224), green from 32 to 170 (length 170-32 = 138), blue from 12 to 250 (length 250-12 = 238), which means we will "Cut" the cube on the blue side. The resulting segments are also cut along the long side, etc. until we get 256 segments. For each segment, calculate the average color - this is how we get the palette.

    A couple of pictures almost in topic, for clarity


    What can be improved here? The first thing that comes to mind is to calculate the average color by not stupidly adding up all the colors and dividing them by [sum (color) / count (color)], but taking into account how many times each color occurs in the image. That is, we multiply each color by the number of occurrences in the image, add the obtained values, divide the result by the number of occurrences in the image of all colors in this segment [sum (color * total) / sum (total)]. As a result, the most common colors take precedence in the calculation, but rare colors also make their adjustments, so the palette is better, the visual color deviation is less. For best results, it is still desirable to take into account the gamut, but I left it for later. The second is not so obvious - the median section does not at all take into account the peculiarities of color perception by the human eye. We perceive shades of green much better than shades of blue. I decided to correct this misunderstanding and “flattened” the cube - I multiplied the lengths of the sides by the coefficients fromthis article . As a result, there are more sections on the green and red sides, less on the blue. I have never met such a solution anywhere (maybe I was looking badly), but the result is obvious.

    Now we have an optimal palette, not perfect of course (I know that it can still be improved), but good enough. The next step is indexing the colors of the image. The easiest option - in which segment is the color, such and the index. Quick and easy. But there is one but, and not even one, so we will return to this step.

    There is another way to improve the quality of the resulting image - error dispersion. Here, too, everything is quite simple - we subtract the corresponding color from the palette from the indexed color, we get an error, scatter it by neighboring pixels in accordance with a certain formula (template), the most famous Floyd-Steinberg formula, I used it. When dispersing errors, sharp transitions between colors are blurred, and visually it seems that the image contains more shades (colors). If it’s interesting, you can read about error dispersal in detail and interesting here.. I also decided to finish this algorithm, multiplying the error by all the same coefficients, as it turned out, it was a very good idea - since the cross sections in the blue range became smaller, it produced a significant error, and without correcting the error with the coefficients, the scattering made a lot of noise ".

    Now you can return to indexing again. By diffusing errors, we change the colors of the pixels and get those that are not in our RGB cube (recall, it is made up exclusively of image colors). Now you can’t just look at what segment the color is in to assign an index. There was a solution right away - finding the nearest color in the palette. In this formula, I substituted all the same coefficients. Comparing the results of selecting the color of the palette by the index of the segment that includes the source color and the search results for the closest color, I clearly saw that the closest color often appears in the adjacent segment. If the source color is closer to the center of the segment, then the segment index corresponds to the color index in the palette, but the closer the source color to the edges of the segment, the more likely it is that the nearest color will be in the adjacent segment. In general, the only correct way to index is to find the closest color in the palette. But the search has a minus - it is slow, very slow. Writing a python grinder is a bad idea.

    Well, I wanted to explain in a nutshell, but I got a whole bunch of strange writing. I hope the code I write is better than explaining, so here is a link togithub . The code was rewritten several times, at first the algorithm was improved until the result satisfactory to me, then it turned out that it eats too much RAM when processing photos (first tested on small pictures), I had to transfer the RGB cube, median section and pixel map to the database ( sqlite). The script works very slowly, but the result is better than quantization using PIL / Pillow and GIMP (in it this operation is called indexing).

    Visual demonstration:
    Original


    GIMP quantization result, the optimal palette for 256 colors + color blur according to Floyd-Stenberg (normal)


    PIL / Pillow quantization result
    image.convert(mode='P', dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, colors=256)



    The result of quantization by my code


    What to look for: GIMP's error dispersion makes a lot of noise, PIL / Pillow creates a not-so-optimal palette and practically doesn't diffuse errors (sharp transitions between colors).
    If you don’t see the difference, check out other examples on github .

    PS: there is a wonderful program Color Quantizer , which copes with this task better and faster, so my script does not have practical meaning, it is made solely from "sports" interest.
    UPD: updated the project on github . Added Octree quantization algorithm (octree tree), popular error dispersion formulas, search for the closest color by the average value of red.

    Also popular now: