Algorithm
Sourav De and Partha Bhowmick, Digital Circlism as Algorithmic Art, 9th International Symposium on Visual Computing (ISVC 2013), July 29-31, 2013, Rethymnon, Crete, Greece, LNCS 8033, pp. 69-78.The Idea
It is an algorithmic solution to digital circlism, which is a contemporary rendition style in the media of digital art. The algorithmic artwork is processed within a few minutes by our algorithm, which makes it computationally attractive in comparison with its manual counterpart that requires tremendous diligence and apt craftsmanship throughout its hour-long processing. We show how the problem is mapped to circle packing in discrete space, once the segmentation is done. A greedy technique similar to the dynamic programming approach for solving the coin denomination problem is used to achieve the packing result. To aid the greedy technique, progressive Euclidean distance transform is resorted to. Variability of the denomination set and color rendition based on mapping the original color range to Macbeth color chart add to its further appeal. Results on different kinds of images speak about further possibilities of this new style of algorithmic art.Basic Steps
Shown aside are the algorithm snapshots for the dog image.1. Input image.
2. After segmentation.
3. After parsing.
4. Euclidean distance transform (EDT).
5-7. Circle packing using progressive EDT.
8-10. Final renditions (with D2, D1, D3).
This set is obtained with the radius denomination set D2 = {2, 3, 5, 10, 20}. For its actual size and results with two other denominations (D1 = {2, 3, 5, 10, 20, 50, 100, 200} and D3 = {2, 3, 5}), click on the respective images (8, 9, 10).
The image M contains the EDT values, the image L contains the segment label corresponding to each pixel, and the (ordered) set D contains the radius denomination in decreasing order of the radii. C(p,r) is the digital circle centered at p and having radius r.
Circle packing is a classical geometric problem. It studies the arrangement of circles of equal or varying radii inside a given region, usually of a regular shape and defined in real space, such that no overlapping occurs. The associated packing density of the arrangement is the proportion of the region covered by packing the circles, and it forms the maximization criterion. The problem of circle packing has been studied by many researchers in different contexts and only a few problems have been solved for packing circles inside geometric primitives like squares, circles, triangles, etc. In fact, it is known that many packing problems are NP-hard. In our work, circle packing relates to packing circles in discrete space instead of real space, where the circles are defined by a finite and small set of radii. We first compute Euclidean distance transform (EDT) and use the EDT values of the pixels to pack the circles in different segments. For each segment, the packing follows the dynamic programming technique of solving the coin denomination problem.
Time complexity of the algorithm is O(kn2/rk2), where n = total number of pixels constituting the image, k = size of the denomination set, rk = minimum radius in the denomination set.
Average CPU time to process a 1 MP image varies from 1 min. to 5 mins.
