Week 3 Project (Efros-Leung Texture Synthesis)

In case you are not familiar with it, the Efros-Leung Texture Synthesis algorithm takes a large region of a texture as input, and produces "more of that" given the input region. It operates on a per-pixel basis (one pixel at a time) and even with all four of my CPU cores crunching away at it, it's fairly expensive, so many of the segments in the video are sped-up in editing. Many of the textures herein are from the nice Free Textures website: http://www.textures.com/ The first two textures (the grayscale text and bricks) are from the Efros-Leung paper itself: Texture Synthesis by Non-parametric Sampling (Efros 1999) For all of the synthesis results shown here, a filter-width of 15x15 pixels was used for simplicity of not having to change the filter between runs. Some of the textures with larger-scale details (such as the grayscale bricks and the multicolored thing at the end) would have had better synthesis if a larger filter-width were used (the filter-width must be larger than the largest feature in an image in order for the Efros-Leung Texture Synthesis algorithm to be able to account for that feature). That's why the bricks don't exactly line up. Both "Hole-Filling mode" and "Border Expansion" modes were implemented, but the "Synthesis Mode" from the Efros-Leung paper that grows a new texture given a tiny sample of it was not implemented. Also, the hole-filling algorithm does support arbitrary shapes, but it just so happened that rectangles were the simplest thing to support from the command-line input. I wanted to spend more time to GPU-accelerate this one (because it's easy when you have 28,400 completely independent floating-point-heavy tasks to do at the same time), but it would've been a lot more work to do that. Instead, I implemented multi-threading and just threw an arbitrary number of CPU cores at it (5 worker-threads seems to be the magic number for my 4-core system while I'm running FRAPS at the same time). Also an interesting tidbit (interesting to me anyway) was that when performing either hole-filling or border-expansion, the order in which empty pixels are filled-in is based on sorting all available empty pixels by the number of empty and full pixel neighbors they have and then selecting the one with the most full neighbors (this is as-described in the Efros-Leung paper). It seemed cool to me to find that this order turned out to be always circular (inwards circles for "hole fill" mode, and outwards circles for "border-expand" mode). I'm not sure why, but I had guessed that the fill order would've been rectangular before I started this project. Optimizing away the fill-ordered sort took awhile too, but I eventually did the average case down from having to do an evaluation + sort of all empty pixels (expensive expensive!) to being a constant-time lookup and maintaining some state between pixel-synths. I guess we all learn stuff from doing these after all! If you want to read up more about Efros-Leung Texture Synthesis, check out Efros' website here: http://graphics.cs.cmu.edu/people/efros/research/EfrosLeung.html You can find a Powerpoint summary of the paper here: http://graphics.cs.cmu.edu/people/efros/research/NPS/efros-iccv99.ppt And you can find the paper itself here: http://graphics.cs.cmu.edu/people/efros/research/NPS/efros-iccv99.pdf