In this video I explain the purpose and implementation details of a texture synthesis (patch based) algorithm. Texture synthesis is the ability to take a source image and generate a new larger output – this is commonly used in video games or 3D movies where artists can’t manually draw all the scene’s textures, but instead let the computer do some work for them by repeating patterns and stitching sub-samples together.

Towards the end, I might sound a bit confusing towards those without a background on “dynamic programming”. Essentially it is required to implement a path-planner to find the optimal edge placement when merging two overlapping textures. I do this by using the famous Dijkstra’s algorithm. I wrote one a while back for the Penn State Robotics Club, but re-implemented a much nicer and cleaner version for this project. By using back propagation and local minima, I was able to quickly find the best path but overall the algorithm still runes at O(n^2) complexity.

Check out (1) some (2) sample (3) images I uploaded to the server!

Algorithm Details:

My approach is based on a 2001 patch-based texture synthesis; you can find the original paper on the author’s site. The algorithm attempts to create a new texture by taking several smaller sub-sections (called a texton) of the source image (called a kernel) and meshes these images together by testing how similar the edges are, and if they are similar enough, merges them. Testing the similarity of an edge is as simple as looking at the overlapping content and computing each of the paired pixels difference. Usually this is a sample function based on some preferred statistical approach – I chose the sum of differences squared so that even small differences are noticeable. Once I build this “delta” table, I find the path of least value – this path represents where I will merge the two textures. Merging based on an average, blur, or other function doesn’t lead to desired results since many of them either loose data or create visual artifacts. Instead, I look at common merge points (seams of a pattern, edges of an object, lines throughout the image) and attempt to “patch” each texton into the resulting image by only rendering the background (source) image and the new overlapping (texton) cut-out. To find this path I have to use a searching algorithm that runs fast, and this I chose ti implement the dynamic programming Dijkstra algorithm. I back-propagate each pixel’s delta value and only choose the local minima. By doing this, I build a table of summed path values in O(n^2) time and quickly find the path in O(n) linear time. There are smaller implementation details, such as setting up a “maximum” error threshold to ignore patches that really shouldn’t fit, as well as rendering slightly more than what my algorithm’s path-cut is so that edges look slightly smooth, but this is a good general outline of my approach.