Saturday, February 20, 2010

Visualizing RGB, take two


Update: The follow-up post can be found here.

About 3 weeks ago, I wrote about a program I created to transform pictures into all-RGB images (4096x4096 images using each possible RGB colour exactly once). It worked by ordering pixels based on a Hilbert ordering of the 3d colour cube and then re-colouring them in order, and while it produced interesting images, it pretty much failed at the stated goal of “keep[ing] the overall look untouched”. The problem was that the general hue of the pixels was often very shifted from the input, so the overall features were preserved but the colour balance was not. So for the past week or so I’ve been working on a new program, one that will (hopefully!) do a better job of keeping the base look intact. As with last time, I’m using an image I took in Barcelona for testing – let me know if you have a different one you’d like to see.


Original
Result From Take One

Choose the closest colour…

My idea this time was that instead of choosing an ordering of the pixels, it would be better to try to minimize the distance between the source and destination colours overall. The easiest way I could think of was to simply choose pixels at random, and assign them the “closest” colour remaining. Hopefully deviations would occur in all directions equally, so the average colour of a region would be as close as possible to the source. By popular demand, I will try to make this algorithm a little more explicit this time:

  1. Go through the pixels in the source image in a random order.
    1. For each, select the closest remaining unused colour, by Euclidean distance between the coordinates in the colour space.
    2. Assign the found colour as the output colour of the pixel, and mark it used.

But in which colour space?

Sources: one and two

A key question I had was which colour space would be best for preserving hues? There are a number of different “colour solids” that I could use coordinates from, with RGB being only one of many. I had a strong suspicion that something like HSL would do better than using RGB directly, but the easiest way to find out which to do a direct comparison. I tried the RGB cube as well as HSL and HSV cylinders for the comparison. My test images are presented below.


Original
RGB


HSL
HSV

As you can see, HSL and HSV give essentially the same results, which are both much better than RGB (look closely at the wheel wells, or the buildings in the trees on the right to see the differences). I like to think that HSV is slightly better, but I might be imagining differences that really aren’t there. Either way, I chose to use HSV for the final copy.



Looks good! Certainly a lot closer to the source image – I’m satisfied with this one for now.

Postscript

As with last time I am using a conceptually simple algorithm, however this time the implementation was considerably more difficult. The problem is that choosing the closest remaining colour to a source pixel is a hard problem to do efficiently, especially since the set of candidate colours changes at every step. I wrote the code in C# for performance this time, but I have still had to spend quite a few hours optimizing the code to get the program to finish at all. The final version can take 30+ hours to generate an image, and peak at over 4 GB of ram. I based my code around a KD-tree I found online, then rewrote to optimize for the 3D, single-nearest-neighbour case as well as to support branch pruning on delete. The rewritten tree – as well as the rest of my code – is available in a repository on GitHub: http://github.com/EricBurnett/AllRGBv2. Feel free to try it out for yourself - if you do, I’d love to hear about it!

9 comments

  1. Hi, is that the full size image you were using? If not can you the share original image?

    ReplyDelete
  2. If you mean the source image, yeah the linked image is the one I used. The source is scaled dynamically to the required size, so as long as it is square and decently sized things work fine.

    If you are talking about the final result, I have linked to it at allRGB.com - there is nowhere else to host an image that size easily.

    Does that help?

    ReplyDelete
  3. I thought I'd give your picture a try, so I did a low res render that took about 1.5 hrs. It did 30 iterations of optimally swapping pixel sets of size 4, using YCrBr color distance (with 4*Yd). Generally though larger pixel sets (8, 32, 128) produce better color mappings.

    I am not happy with the results. There is much more detail in the picture that is for sure but the sky is a great example of not quite overfitting but just something not that tasteful. Those smearing fuzzy edges really bother me. Also I wish there was a bit more definition in the decoration.

    I think you should try HSL against except weight L higher. Luminence is main component in our perception in an image, this is why videos are often encoded at 4:2:2 or 4:1:1, because the brightness and darkness is more important to our perception than the color. That said in both of our cases we're left with very "hot" colors.

    A sample: http://churchturing.org/y/quarter.lowly-programmer-scaled.png.4.0.4096.29.png

    The real big deal: (48 mb) http://churchturing.org/y/lowly-programmer-scaled.png.4.0.4096.29.png

    The software: http://churchturing.org/y/24bit-randomschedule-ycbcr

    ReplyDelete
  4. Thanks for the render! I do like how yours comes out a lot smoother - I assume it's the same basic algorithm you described on http://allrgb.com/high-quality-render-of-wedding-photos ? I'm definitely going to have to sit down and think about it a lot more.

    I hadn't realized luminance was the dominant component in human perception - I would have thought hue would be. I will try generating a couple low-res versions with my program tomorrow when I get home using different luminance multipliers, so we'll see how much difference that makes. Although I will note that I tried changing the hue multiplier on a different image without much luck, so it may be that luminance works the same way. Part of the problem is simply having a constant set of colours to work with.

    ReplyDelete
  5. This one took a few hours, I really don't like what it did with the sky.

    http://churchturing.org/y/lowly-programmer-scaled.png.8.0.4096.29.png

    If you want to display photos the problem is how to do take a fixed set of pixels and present the photo in such a way that is perceptually similar. In most cases it can't be exact. If you look at a lot of the AllRGB entries you'll see that they get away with it because they simply resized the image so the small details are not needed. If you want small details to be important then you'll have to be more careful where you hide the noise.

    This is like the MP3 problem, you have so much signal to share, but what part of the signal do you really need and can you hide the error. If it is piano music there's no where to hide the error.

    You could try error diffusion or a dithering algorithm. It'll have to be changed a little to deal with permutations.

    ReplyDelete
  6. Ok, I tried varying the luminance as you suggested:

    1/8: 2_allRGBv2_L1%8.png
    1/4: 2_allRGBv2_L1%4.png
    1/2: 2_allRGBv2_L1%2.png
    1: 2_allRGBv2_L1.png
    2: 2_allRGBv2_L2.png
    4: 2_allRGBv2_L4.png
    4: 2_allRGBv2_L8.png

    At low values in either direction there is not too much change, and at higher values the increase in noise kills off any gains there might be. However, I'm interested in your idea of adding error diffusion, which after looking into it I think has a lot of promise for this algorithm. I will try it out next, and assuming it does as well as expected, I will re-run the luminance experiments with it turned on.

    I agree about the sky, in your image and mine as well. It is just too large in area for the current algorithms to have a hope with, I suspect. We'll see how it changes with error diffusion.

    ReplyDelete
  7. Quick update (I'll post the pictures and explain better when I have some real time): I implemented error diffusion, and it makes a huge difference, especially with the 4096x4096 images. Capping the error terms lets me trade off uniform noise and graying-out with the "hot" colours, which turns out to be a good trade-off to make. It can reproduce the original image considerably better now and the sky becomes a uniform noise in the places it was going psychedelic before, which I think is an improvement.

    A version with the sky masked as low priority is generating now as well, so I'll see if that makes a difference as well tomorrow or so.

    I'll try it against Mona Lisa next, for comparison to http://allrgb.com/mona-lisa-ycrbr.

    ReplyDelete
  8. Ok, the follow-up post is now up detailing the results of adding error diffusion. Sorry for the delay!

    Adding a priority mask turned out to be a bad idea, as it didn't really change the image perceptually except by making a hard division between the sky and buildings.

    Re-running the luminance experiments with the new version gives results similar to before - I'm thinking that my algorithm is not really equipped to deal with minor variations in the colour scheduling algorithm like that. Still, it was worth a try.

    ReplyDelete
  9. Dacia Logan from Romania. Nice

    ReplyDelete