CS 791: Project - Greco-Roman Mosaics


Overview

This web page describes my project for CS 791 (non-photorealistic rendering) which was a simulation of Greco-Roman style mosaics.

The report is organized as follows:

Implementation

The implementation for this project was coded in C++ using openGL for rendering and Gtk for the user interface. The application framework was based on the skeleton code provided for A3 in CS 488.

Algorithm

The algorithm implemented to create the mosaics is based on that described in the paper “Artificial Mosaic” by Di Blasi and Gallo, outlined in the sections below.

Directional Guidelines

Di Blasi and Gallo begin by processing an input image to produce what they refer to as the directional guidelines which are lines that mosaicists use to guide the placement of tiles in the mosaic. They apply some image processing techniques to generate these guidelines; an example is shown below.

(Above-left): input image; (above): after applying some image processing we end up with automatically generated guidelines; (left): a distance transform is applied to the guideline image which is then used to produce the "level line" matrix which guides tile placement. Tiles are placed along the green lines in the image while the black lines are used to define the shape of objects in the mosaic.

After the guidelines are generated, a distance transform of the guidelines is created. This calculates, for every pixel in the image, the distance to the closest guideline. From this we create the "level line" matrix. A size for each tile can be specified via the UI (with a default of 5 pixels). For each pixel in the distance transform, we evaluate the distance modulo twice the tile size. If this value is 0, the corresponding pixel in the level line matrix is "black", if the value is the tile size, the corresponding pixel in the level line matrix is "green" and everywhere else is "white" as shown in the above image.

The green lines in the level line matrix are where tiles are allowed to be placed. The black lines are supposed to represent the shape of important features in the mosaic and when tiles are placed they are trimmed so that they do not cross the black lines.

Tile Placement

As mentioned, tiles are placed along the green lines in the level line matrix. In order to do this, it is necessary to extract the green lines as ordered chains of pixels. I describe my approach for handling this below.

Given a distance transform of the guidelines and the level line matrix, the following algorithm is used to position tiles:

  1. Set the current distance to a single tile width.
  2. Extract the pixels belonging to the level line(s) that corresponds to the current distance within the distance transform matrix
  3. Convert the unordered pixels into chains of connected pixels (described below)
  4. Starting at a random pixel, place tiles so that there are no closer than the current defined tile length (which can be set via the UI) until all pixel chains have been processed
  5. Size and cut tiles (more details below)
  6. Move to the next tile distance and repeat until no more pixel chains can be found
Given an unordered set of pixels corresponding to green level line pixels of a set distance, the following algorithm converts them into a set of pixel chains:
  1. Start with the first pixel found in step 2 above and add it to the current pixel chain, this becomes the current pixel
  2. Search through all remaining pixels until one is found that is adjacent to the current pixel
  3. If no such pixel is found, look for the closest pixel within a threshold (about 1 tile length is used) – this helps to deal with cusps where we might get stuck in step 2
  4. If a pixel was found in either step 2 or 3, add it to the current chain and make it the current pixel
  5. Otherwise, start a new chain and pick the first remaining pixel as the new current pixel
  6. Repeat until all pixels have been added to a chain

Cutting Tiles

After tiles have been placed they must be sized and cut so that they do not overlap each other and so that they do not cross the black lines in the level line matrix. I use openGL to assist with this by rendering each tile to the back buffer as rectangular pyramids (similar to creating a voronoi diagram using Manhattan distance) and use the depth test to automatically handle trimming tiles to each other. To handle crossing black lines, the following algorithm is used:
  • For each pixel in the back buffer:
    1. If the pixel's distance (in the distance transform matrix) is outside the distances corresponding to the two black lines on either side of the current green line, discard it
    2. 1.Otherwise, get the tile index encoded in the current pixel colour and add the pixel to that tile
  • When all pixels have been processed, for each tile, create the convex hull of the tile's pixels (using the algorithm in "Computational Geometry: Algorithms and Applications 2nd Edition" by de Berg et. al); the vertices of the convex hull become the tile vertices
The algorithm as described will generate a mosaic-like image such as the one below:

Extensions

Extensions and additions to the basic algorithm are discussed in on the extensions page.

Results

Some images are viewable on the results page.