circle packing algorithm used by Percolator

Question

I was admiring this rendition of the Mona Lisa from quasimondo's Flickr account. He says:

Combining circle packing with data visualization. The pie charts show the distribution of the dominant colors under the circle area.

The circle packing technique used here is a combination of an image segmentation with a distance transform and the first one who came up with it is John Balestrieri: www.flickr.com/photos/tinrocket/

I have traced it to an app called Percolator

How are such circle packings calculated? How are the pie charts calculated from the image?

Answer 1

Since I created this I probably can explain it best ;-):

• the first step is to calculate an image segmentation which will combine small areas of similar colors into bigger chunks. The tolerance values of that segmentation will influence how big the biggest circles can become (higher tolerance => bigger areas => bigger circles)

• You proceed by processing each of the found areas individually: calculate an euclidean distance map for the area. This map will tell for every pixel the distance to the nearest edge. Find the maximum value in that map. This is the pixel that has the furthest distance from an edge. Conveniently that distance will be the radius of the biggest circle that you can fit into that area. Add that circle (center position + radius) to a list. Now you subtract that circle from the area - subtract in this case means that if the original area is all white pixels surrounded by a black border you simply draw a black circle over it. Recalculate the distance map for the remaining white area pixels repeat the above process until there are no more distances bigger than some chosen threshold (the smallest radius you want to display).

• the last part is to calculate the pie charts for all the circles you have collected. In order to do that you accumulate all the pixel colors of the original image that are lying under a circle and calculate a color quantization for them. In the Mona Lisa example all the colors are reduced to the 7 most representative. In order to calculate the pie ratios you simply count for each of the 7 representative colors how many of the original colors are their nearest neighbors. The only thing left to do is to draw a pie chart using the ratios and colors at the stored circle position.