May 18th, 2011

Centroidal Voronoi Diagrams (CVDs)

Gradient Fields

Color Sampling

Results

Potential Improvements

The idea of this project is to simulate the processes and final outcome artists go through while making traditional mosaics consisting of tiles. To do this, I utilized a paper known as Simulating Decorative Mosaics. While I attempted to follow the paper as closely as possible, there were many techniques that were out of my reach and thus I had to come up with alternative solutions. I also wanted to attempt to expand upon what the paper had started but due to the difficulties I faced in implementing their techniques using my own methodology and a serious lack of time, I was unsuccessful.

This writeup will take you through the process I took to get to the final results I will display here.

As previously mentioned, the algorithmic basis for this project comes from not only attempting to obtain the result of an artist's time put into creating a mosaic, but rather, to mimic the artist's processes to create the final image that is as visually appealing as possible.

Therefore, the beginnings of the process starts in the construction of a Centroidal Voronoi Diagram (or "CVD" for short) to follow mimic of spacing out the tiles before the artist begins cementing them into place. An artist looks not only at the specific tile he wishes to place, but rather the whole picture - all the tiles around that specific tile, how they interact with the tiles around them, and so forth. The idea with a centroidal voronoi diagram does just that. In opposition to the standard Voronoi Diagram, which looks to define regions based directly on the points it is given, a Centroidal Voronoi Diagram is created from a voronoi diagram to space the regions set by all the points evenly. Considering the placement of the tiles in a mosaic, which do not overlap and take into consideration all of the tiles around its space, the CVD was a useful tool to help construct the bare bones layout of where tiles should be placed.

Voronoi Diagram | Centroidal Voronoi Diagram |

This, however, is where I begin to diverge from the paper. Most techniques spoken about in the paper work primarily on the GPU. For example, the CVD step requires the implementer to take projections of three-dimensional shapes onto a two-dimensional plane to construct the CVD. However, due to my abilities and time budget, I was not able to follow this closely.

Rather, I needed to construct my own CVD in some other way. Looking for other sources, I discovered Lloyd's Algorithm, which takes a voronoi diagram, finds the centroids of its regions, and constructs a voronoi diagram off of these centroids to converge to a CVD after many repetitions. For my implementation, I put an arbitrary set of points into Matlab's Voronoi function to construct the initial diagram, and applied my own rendition of Lloyd's Algorithm to construct my final CVD. You can see the results of my actions in the images above. The CVD is certainly more spaced out, though has some badly clumped sections which can sometimes be apparent in the resultant images. No matter the number of iterations I used or changes I made, I found it difficult to remove these clumps. I found that this caused some clumping of tiles in the final image and as such, I did not allow any overlapping tiles to be placed. This removed much of the clutter I was seeing and improved image quality immensely.

One difficulty I had is that Matlab's voronoi diagrams extend the edge points out to infinity. To get around this fact, I created the initial diagram over an area larger than the original image and truncated the result to the image bounds after this point.

Also, the paper uses a Manhattan Distance heuristic to construct the CVD as this is the most efficient method to fill in space evenly while using square tiles. However, I found this extremely difficult to implement and was unable to include this in my program. Rather, I maintained the Euclidean Distance heuristic that is the default when it comes to voronoi diagram construction. This resulted in somewhat hexagonal regions (rather than the square regions as with Manhattan metric) and this becomes apparent from my final results as well as my CVD image above. It seems that the Manhattan metric would be potentially more visually appealing and reminiscent of traditional mosaics.

The second most important part of mosaic construction was determining the orientation of the tiles to place. This should all be dependent on edge weight and direction as you want your tiles to be placed such that they accentuate image features - namely edges. Initially, I had misunderstood the process and simply utilized the gradient of the image directly. However, this created orientations for tiles explicitly on a particular edge in the image and nowhere else. Rather than on the edge, these tiles should follow *along* the given edge to showcase its location. Needless to say the results were not spectacular, as seen below...

Original Image | First Gradient Outcome | First Gradient Outcome With Color |

After creating the central image, I believed the space to be too dense, so I reduced the number of active tiles while adding in color mapping for the next shot. Notice how all the edge definition comes from the colors themselves - seemingly no better than a regular old fashioned image.

As such, I looked more closely to the paper to find out what I was missing. Thinking back to the algorithm's design philosophy, both the paper and I wanted the mosaic to be made in an artistic style - in particular, all tiles should take into account the weight of all the tiles surrounding them. Looking to my implementation, the only tiles that change orientation are those on the edges! The ones off of the edges make no impact! I needed to rectify this. The algorithm in the paper was not directly feasible for me to implement so I needed to think of alternatives.

My first solution was to apply a gaussian blur to the image and find the gradient of this result. If all worked out according to plan, the edges would be smoothed out to a larger area with a slight falloff. Since the gradient of the image would then take into account this falloff, the orientation of tiles near the edges should be affected by the existence of the edges - essentially, tiles would be placed with consideration to the tiles around them. After tweaking some parameters, this worked really well and gave some interesting images.

My second technique followed the paper's algoritm much more closely (though with a different implementation). Essentially, I created a mapping from a given pixel in the image to the distance to its closest edge in the image. Since this would cause gradual changes away from edges, I could take the gradient of this result to find the necessary orientations of the tiles. This method, however, due to its brute force nature, is quite slow (particularly for Matlab since I use so much iteration). It is a difference between a matter of seconds for the blurring method, to minutes for this gradient mapping method (15 minutes is probably the average on a medium-sized image - on the order of 500x500 pixels). In terms of tiles acknowledging other tiles when being placed, it seems to produce much more accurate results. However, in terms of visual appeal, it seems to produce arguably the same results as the blurring method, which is a bit disappointing considering the time investment for computation.

Original Image | Simulating Decorative Mosaic's Result | My Result (Gaussian) | My Result (Gradient Mapping) |

Note that for the above examples, I was unable to find the original image the *Simulating Decorative Mosaics* paper used for their examples and so I found another, similar image in their paper that has dimmer (and less appealing) colors with the edges outlined in yellow. This provides some less than stellar results for my mosaics, but this is just here for comparison purposes.

As for comparisons between my two results, notice how in the sections away from the edges, the gaussian result has many tiles oriented straight up rather than towards some edge. This creates some inconsistencies in the general flow of the mosaic though it does not necessarily make the result any less appealing.

Once the gradient was found, it was simply a matter of applying these values to the orientation of a tile to place, in combination with the tile locations and color, to get the result.

Doing the color sampling for each tile was fairly straight-forward. There were two methods I saw to figure out the color values - either by point sampling (taking the color directly from the pixel where the center of the tile would be placed) or averaging the colors underneath the tile to be placed. After trying both methods, I found I prefered point sampling as it seemed to accentuate image features and edges better - though the difference could be considered negligible. See the images below for example.

Original Image | Point Sampling | Area Sampling |

Notice how some definition is lost, particularly around the nose of the horse. This loss of detail was noticable in other cases as well. In general, area sampling seemed to cause the image to lose definition - which makes sense when you think about it. I chose to use point sampling for all of the remaining images because of this.

In general, I think the results came out fairly well. The algorithm doesn't seem to do too well with details (which is something that could be improved upon). However, artwork with broad brush strokes where the details are not essential to the piece's definition seem to do really well.

Again, details are lost, making images of people seem particularly souless (see myself for reference) - this is probably due to the loss of detail in the eyes. The results from my implementation, both good and bad, can be found below. Keep in mind that the placement of tiles is somewhat arbitrary with my algorithm (the initial Voronoi Diagram is set up with arbitrary points) and so theoretically, recomputing the mosaic could potentially give more or less appealing results. Also, due to the required computation time, some images were resized to smaller sizes from their original to make the process faster.

Two notable good standouts are the Zerg logo (first image below), and van Gogh's Starry Night.

Original Image | Gaussian Blur Mosaic | Gradient Map | Area Sampling |

Original Image | Gaussian Blur Mosaic | Gradient Map | Area Sampling |

Original Image | Gaussian Blur Mosaic | Gradient Map | Area Sampling |

Original Image | Gaussian Blur Mosaic | Gradient Map | Area Sampling |

Original Image | Gaussian Blur Mosaic | Gradient Map | Area Sampling |

While I was working, I noticed some particularly gaping issues in my algorithm that I was either unsure of how to implement the fix or I just didn't have enough time. These will be listed here.

In the *Simulating Decorative Mosaics* paper, they discussed their technique of "edge avoidance." This entailed creating Voronoi Diagrams that knew where the edges were located in an image and avoided them, expanding those Voronoi regions. After the several iterations required to produce the CVD, this would result in tile placements being pulled away from the edges, allowing the edges to shine through really well. It acted as a great reinforcement to the other elements left in place to show image features such as the tile orientation. I was really unsure of how to add this functionality to my implementation but I feel it could be the most beneficial change to the end-results.

As was previously mentioned, I was not sure how to include the Manhattan Distance heuristic in my Voronoi Diagram calculations. As such, the tiles are not spaced as closely as they can be, leading to awkward breaks in the image as tiles split in rather arbitrary locations.

I also had the issue of clumping in my CVD. Taking this out would provide a uniform surface to place tiles, resulting in a much more consistent and soothing result.

The paper also took into account tile rotation when computing the Voronoi Diagram for the initial image (and subsequent iterations to the CVD). This allowed the spacing to be dependent on the image itself rather than just some somewhat arbitrary uniform spacing, which is how my algorithm works. Taking the image into account during tile placement should theoretically produce a much more edge-accentuating image, which is something I have been striving for throughout this process.

Also, tile sizes can change both their aspect ratio and size to accomodate increased detail in the image. One particularly good example mentioned in the paper would be elongated tiles that represent strands of human hair. Changing the tile size in certain locations where detail is needed could result in better fine mosaics - meaning we can represent things my current implementation can't do well such as human features. Again, see the image of me for a good example. This method could help accentuate these finer image features and edges really well which would allow the algorithm to be useful for many more types of images.