Previously, I wrote about Texture Synthesis which is the process of taking a sample image and extrapolating patterns so that new images can be generates. This is a common algorithm used by video game developers to create better-looking textures on large surfaces.

My patch-based approach is similar to procedural texture synthesis, but instead of creating new image data we are simply intelligently repeating sub-sections (textons) of the image – why do more work when you can seamlessly repeat the image? The following text goes through the general approach to my algorithm.

At the start of the algorithm, all you need to do is take a sample (texton) from the source image and try and fit it into the current output position. I started with an output set to all black, and set my texton sizes to 65 pixels by 65 pixels. Since my overlap was 10% I calculated that there would be ceil(65 * 10%) = 7 pixels of overlapping, thus on my output I would actually be placing my images 65 – 8 =  58 pixels appart. That way, every-time I place a texton to my output, at most two sides (depending on how you place them – see next sentence) overlapping. My placement was done from left-to-right, top-to-bottom, meaning I placed the first texton on output position (0, 0), then placed my next texton on (58, 0). Notice again that there are 7 pixels overlapping on the left-side of this second image. If you repeat this pattern, all the textons placed on the far-left don’t have left overlap, and all the images placed on the far-top don’t have top overlap, but everything else should be overlapping both up-top and on the left.

So, before actually placing your texton to the source image what you have to do is figure out how “good” is this overlap. You should be taking the current output image and the texton image, figure out the overlapping zones, and apply some sort of per-pixel function and sum up the generated number. From there, you can apply some sort of threshold and figure out if it’s a “good” fit. I used a sum-squared different function and sorted out of a dozen randomly selected textons based on the “best” fit values. I then chose the best one out of that last and placed that onto the output scene. But… there is a very big issue here that will the difference between a “decent” result and a “good” result: finding the best edge!

Finding the best edge requires path planning over the “comparison overlap grid”, which is normally computationally expensive. There are a few options to do this for you but the best option would be to use the O(n^2) dynamic algorithm for short path: Dijkstras. Don’t worry about the “dynamic programming” aspect of it – it’s not that hard to implement! The reason why it’s important is that when you finally do find a good texton to use, just “pasting” it onto the image won’t look good at all. The output will very clearly have the edges.. so the next best option are the find the pixels that match the best and then draw parts of the original image with the new image. This is slightly confusing when explained by text, but imagine the following: you are attempting to merge a left-overlap. You can’t just past the texton’s pixels to the output location simply because it’ll look bad, instead what you have to do is find the “seam” where you can leave certain parts of the original image un-changed, while only drawing certain parts of the texton. That way, when the seam is drawn it’s only at the most similar pixels and is very hard to see.

You can visualize this specific process with the (poorly) mouse-drawn image below. I need to find my Wacom tablet.

To do this, I allocated a two-dimensional boolean array to represent a transparency map for each of the two overlapping sides. For the first one (left overlap) I allocated 7 pixels (width of the overlap) by 65 (texton height) and default every element to true (do render). From there, I applied Dijkstra’s algorithm that found me the best path from top to bottom in O(n^2) time. This path is the seam which represents the pixels in the image that are the most similar. If you want to see how I implemented this algorithm, check out my pseudo-code below: (Important note: Remember this path has to be adjacent to each pixel, meaning you can’t have paths that jump from pixel 0 row 0, to pixel 10 row 1, simply because pixel 10 in row 1 is 9 pixels away from pixel 0 row 0; i.e. the path’s pixels must be adjacent).

1. Compute all of the variance values for each pixel; i.e. apply your comparison function to the pixel pairs for each location in your overlap
2. Apply the Dijkstra’s algorithm: (In essence, this is a back-propagation local-minima algorithm)
   1. For each row, from top to bottom of the image, starting at row 1 (the second top-most row)
      1. For each element in this row
         1. Find the smallest of the three adjacent numbers in the above row, i.e. the number left-up, up, and right-up
         2. Add this number to the current location
3. Find the actual seam path: (Now working from bottom to top!)
   1. Find the index of the lowest value at the bottom-most row
   2. Mark this location as “part of the path”
   3. For each row, from the second to last row to the top row
      1. Find the smallest of the three adjacent numbers in the above row from the current path’s end, i.e. the number left-up, up, and right-up from what we last marked as “part of the path”
      2. Mark that number as “the path”
4. Merge the images
   1. Ignore the pixels to the left of the path; they are not to be drawn – the source image should be left alone
   2. Draw all the pixels to the right of this path, including the path; these are from the textons

I hope this clears up any confusion – I’ve been asked by a few readers to explain how I got my output to patch so well. The core of this problem is both a fast path planner and also a food comparison function. The sum-of-squares difference wasn’t too effective; others may be used to create even better outputs, but be warned that these functions are per-pixel comparisons and thus shouldn’t be too computationally complex if you care about speed.