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.

The jellybeans didn’t turn out so good along the bottom, maybe you could use smaller patches from the sample? Care to post your pseudocode?

The jellybeans image was definitely one of the hardest ones to get right because, as you said, I didn’t choose a good texton diameter to start with. Another issue is that my edge-comparison function has a hard time comparing edges that have image artifacts – the jellybeans source image is a low-resolution highly distorted JPG-compressed image. Also, as per your request Zach, I wrote a general outline of my approach. Email me if you want the source-code, I’m happy to share!

can you hepl me… your code is amazing and I look for this thing for a long thin=me but can’t find a source code. Can you help me

can you hepl me please… I have to need the code of texture synthesis for my mini project developed in matlab for college event.I can’t find a source code. Can you help me.

Hello Jeremy,

are you still working on this theme “Image Growing” We are very interested.

Please send me a mail to get in contact.

Thank you very much