I started picking up Go recently because when you’re a recent college graduate without a job, you’ve got plenty of extra time. Go always looked flippin sweet, but almost anything I write is easy and fast enough in Python that it never made a whole lot of sense to learn another language to solve my problem.
But in every coder’s life there comes a problem that would take Real Amounts Of Time to solve in a “fast” language, and using Python would be out of the question. That problem for me was filling in every RGB colour in one image. I originally encountered the problem through a hackernews posting to Joco’s blog (and he in turn found the problem on the StackExchange code puzzles site) where he describes the problem and his solution in detail. His post is certainly worth reading, but I’m going to talk about my own solution (I like my pictures better ☺). If you’re not interested in the technical details and just want to look at the pictures, there is a gallery of a few of the generated images at the bottom of the article.
The easy way to paint every RGB colour is just to iterate over them and paint them in an image one by one. But, like Joco before me, I wanted to fill them in based on nearby colours, so the final product would have a semblance of beauty. For my solution, I used 24 bit colour representation (8 bits per channel) for a grand total of 256 * 256 * 256 colours, which leaves something like 16777216 pixels (and a 4096 * 4096 png image) that needs to be filled in with unique colours. Long story short, I did it, and Go made it pretty easy.
Basically, my algorithm for filling the square is as follows:
- Enqueue the initial point (that is, some x, y point on the image)
- Pop a point off of the queue
- If it’s the first point, colour it the starting colour and note that that colour has been consumed (then goto step 7)
- If it’s not the first point, calculate its “target colour” by averaging the colours of the 8 adjacent points (they only contribute to the average if they themselves have been coloured)
- Using that target colour, search the space of unused colours for the nearest match (this is done by treating the RGB space as a voxel cube [see image below] which is searched in expanding spheres about the target colour point)
- Colour the popped point with the matched colour and note that that colour has been consumed
- In either case, enqueue the uncoloured, unqueued points adjacent to the point popped off the queue (this is done using a goroutine so as not to suspend the main thread’s search for viable colours)
- Continue popping and filling points until done
Easy enough, right?
This algorithm was not super easy to implement, and while it accomplishes the goal of filling in all of the RGB colours, there are still certain issues which I would like to correct if it’s possible and reasonable to do so.
The first major problem was how do you quickly search the 16.777 million available colours for a colour close to the one you’re looking for? I had lots of ideas for simulating locality and then searching smaller data structures (what if we searched by the sum of the vector components?) but I was never able to convince to myself that they would be better than searching the RGB colour space in spheres of increasing radius about the target colour. I did this by dividing the RGB search sphere up along the R axis, so for n distinct possible R values, I’d have n GB circles of varying sizes to search. Similarly, you can divide up those circles along the G axis, allowing you to iterate along just B at the lowest level. This was the absolute best solution I could come up with, and it still requires many maths for each expanding iteration.
Luckily, there are some nice optimisations that can be used here and there. Some square root calculations are necessary for establishing the RGB coordinates to start searching, but once you start down a row that you’re fairly certain is in the outer shell, you can use distance squared metrics to verify that a given RGB point wasn’t searched in the previous spherical shell. When you encounter voxels that would have been searched in the previous shell (that is to say distance from target < search radius -1) you can simply reflect over to the other end of the row and search only those points you know to exist in between the search radius and search radius -1.
Another problem (that still exists) is darkness bias. Several of my algorithmic choices tend, all other things being equal, to select colours closer to black (#000000). Specifically, when find the average colour of the neighbours of the point to be coloured, integer averaging trends down. For example, the average colour of the three points #010100, #000101, and #010001 would be #000000 (for red, green and blue channels : 2/3 = 0). This is probably the main source of darkness bias, and it can potentially be eliminated by changing how the averaging is calculated, but I don’t want to sacrifice a lot of speed on this routine that must run for (almost) 256^3 pixels.
The other source of darkness bias comes from the spherical search itself. The algorithm records only the RGB voxel closest to the target colour, not the set of all valid voxels at that distance. If searched voxel has the same distance from the centre as the current minimum, it will be completely disregarded. The spherical search always starts with negative offsets relative to the target point, which again causes a bias towards #000000. This could be eliminated by maintaining the set of voxels at the closest distance to the target and then choosing randomly amongst them, but the voxel set data structure would in all likelihood need to be dumped and regenerated at least a few times for non-trivial search radii.
Update (23 June): After going and thinking about the problem some more, I’ve made some progress against the forces of darkness. I went ahead and changed the pixel averaging to float values which are then rounded to get their int approximates. The performance hit doesn’t seem to be so bad; in fact it execution seems to speed up in certain cases. This can be attributed to the algorithm more evenly choosing colour values, resulting in less time spent searching for available colours in the endgame when the colour space is more sparsely populated. The predicted bias from the colour searching algorithm is still in effect, and darkness bias is still visible, but the resultant images now look much better.
I’ll probably keep tweaking my code and modifying initial conditions to generate new images. They’re beautiful and I made them and it’s as close as I’ll ever get to painting rainbows. But I really think that more coders who like pretty things should attempt this project. Pick your favourite language and implement your own version of an RGB filling algorithm. Joco’s source code is linked in his post and mine is on github. But there are a lot of different ways to approach this problem, and I would love to see the sorts of art that other nerds can generate.
All pictures were generated with some version of my code.
Questions? Comments? Ideas?
Hit me up on twitter @KapuraMax