masonium.com

CS 176 Project 2: Texture Synthesis

Introduction

Procedural texture generation, in general, is a collection of techniques used to produce new textures from "scratch" or some small input. Texture synthesis, as used here, is meant to produce larger versions of a texture based on a smaller exemplar texture. One of the pioneering techniques, described by Wei and Levoy, is to generate the new texture incremenetally, choosing each new pixel by comparing its neighborhood to neighborhoods of pixels in the original image.

My program implements this basic method with some enhancements, namely Ahshikmin's acceleration as well as k-coherent neighbors.

Running the Program

You can download the source here. You can download a Linux binary here. The program options are listed here:

Required options:
  -e [ --exemplar ] arg           exemplar texture for synthesis

General options:
  -h [ --help ]                   print help message
  -t [ --time ]                   print the synthesis time for the texture
  -s [ --output-size ] arg (=256) size of output texture, ignored when bias 
                                  image is provided

Rendering options:
  -n [ --neighborhood ] arg (=7) neighborhood size for comparisons, must be odd
  --no-texture                   Suppress the synthesis of the texture

K-coherence options:
  -k [ --k-coherence-neighbors ] arg (=0) Number of nearest neighbors to use 
                                          for k-coherence
  --k-exhaustive                          Exhaustively search for the 
                                          k-coherence neighbors, rather than 
                                          sampling
  -o [ --output-k-coherence ] arg         Output the k-coherence map to use in 
                                          later program executions
  -i [ --k-coherence-input ] arg          Use an input coherence map for 
                                          quicker synthesis

In typical usage, the program displays the newly generated texture in a popup window after synthesis is complete.

Implementation

The output texture is initially seeded with random locations in the original image. During the algorithm's execution, the output texture is stored in coordinate form, for easier comparisons.

Edge Cases

For the output texture, I used toroidal wrapping for the neighborhood lookups. For the exemplar, Wei and Levoy suggested two methods. The first was to only used interior points in the exemplar (points that have a full neighbor). The other suggestion was to use a reflected version of the exemplar at the boundaries. I tried both methods and ended up using only the first. The reflection method generated noticeable and unsightly seams in most examples.

K-coherence

The k-coherence neighbors algorithm is implemented largely as described in the Microsoft Asia research paper by Tong et. al. Neighbors are only found and used for interior pixels. I decided to use only a random sampling of the points, rather than using a full search. The sampling size is O( (w + h) * k^0.5 ), where (w, h) are the image dimensions and k is the number of coherence neighbors found. I also include the options of using an exhaustive search, but in the pictures where k-coherence was actually an improvement, the difference was minimal.

Results

Examples of the program output are given here. The first picture is the exemplar. The middle column is from using the program with 11x11 neighborhoods. Running times are roughly 7 seconds to produce a 256x256 image. The last column is from using 11-coherence neighbors with from a sampling search with 9x9 neighborhoods. Running times are roughly 41 seconds for building the coherence map for a 192x192 exemplar (fairly large) and 39 seconds after that to synthesize the 256x256 texture using the coherence map.

NOTE: One small thing you may notice is that the pictures are all upside down. This was an unfortunate result of the screenshot process, not a reflection of the algorithm.

Discussion

In general, using Ashikmin's alone tends to produce better results (sometimes much better) than using k-coherence neighbors. In some since, this isn't terribly surprising. Ashikmin noted in his paper that Wei and Levoy's original algorithm, which search the entire space for neighbors, often blurred results, particulary in images with smaller features that had distinct but hard-to-discern edges.

In general, kCN tends to blur or spread features across the image unreasonably. This smearing is most evident in the water, pebbles, and bark textures. Blurring is very evident in the purple flowers and red rock textures. The one exception where this seems to be more useful is the first picture. In this case, using kCN preserves the smoothness of the resulting texture much more than Ashikmin's alone.

Both methods fail in some cases. The most notable is the cracked rock example. This is most likely because the neighborhood size was too small to fully contain the features of the image.