What in this post is actually part of my computational photography homework, because I’m recently preparing for interviews, so for reviewing it, I re-implemented this method.
WHAT IS IT
Texture synthesis is another very interesting application of image processing. What it does is, given a texture sample, generate new texture that is similar with the given sample, similar here means for human observer, the new generated texture appears to be the same kind of texture.
For example, if we have the following image.
what we want is to fill the black region using the same texture with middle part. A trivial solution is just copy the whole image (or part of it), and put it into the unfilled region, and the output image is something like this.
Actually we feel not that happy with this result, the blockiness is clearly perceivable, and looks like some tiles in the bathroom. We want the texture expands automatically.
This image looks better, although it is also kind of weird, but we can hardly tell that this image is made by tiling some tiles, it is more likely that to be a whole image. This is exactly what texture synthesis does.
function FindMatches(Template,SampleImage) ValidMask = 1s where Template is filled, 0s otherwise GaussMask = Gaussian2D(WindowSize,Sigma) TotWeight = sum i,j GaussiMask(i,j)*ValidMask(i,j) for i,j do for ii,jj do dist = (Template(ii,jj)-SampleImage(i-ii,j-jj))^2 SSD(i,j) = SSD(i,j) + dist*ValidMask(ii,jj)*GaussMask(ii,jj) end SSD(i,j) = SSD(i,j) / TotWeight end PixelList = all pixels (i,j)where SSD(i,j)<=min(SSD)*(1+ErrThreshold) return PixelList end
function GrowImage(SampleImage,Image,WindowSize) while Image not filled do progress = 0 PixelList = GetUnfilledNeighbors(Image) foreach Pixel in PixelList do Template = GetNeighborhoodWindow(Pixel) BestMatches = FindMatches(Template, SampleImage) BestMatch = RandomPick(BestMatches) if (BestMatch.error < MaxErrThreshold) then Pixel.value = BestMatch.value progress = 1 end end if progress == 0 then MaxErrThreshold = MaxErrThreshold * 1.1 end return Image end
Something need to pay attention:
- Window size is manually selected, if the texture repeats, then we can use the unit size of the texture.
- Function GetUnfilledNeighbors() returns a list of all unfilled pixels that have filled pixels as their neighbors. The list is randomly permuted and then sorted by decreasing number of filled neighbor pixels.
- When calculating neighbors, we use the 8-direction neighbors.
- If the current pixel is at the edge of image (one or some of its neighbors doesn’t exist), then just flag the non-exist neighbors, and calculate regularly.
- GetNeigborhoodWindow() returns a window of size WindowSize around a given pixel (returns flagged windows when at edges).
- RandomPick() picks an element randomly from the list.
- Gaussian2D() generates a 2D Gaussian in a window of given a size centered in the center and with a given standard deviation (in pixels).
- The recommended constant values are: ErrThreshold = 0.1, MaxErrThreshold = 0.3, Sigma = WindowSize/6 (3sigma for each side).
RESULTS AND MORE
Some results (including using former code)
1. radishes (100 * 100) VS expanded radishesss (111 * 111)
2. black hole filling
3. barbed wire fence (75 * 75) VS expanded baaaaarbed wire fence (225 * 225)
For testing this algorithm, you can use the Brodatz Textures, which includes 112 gray scale texture images.
Because the above github version code is today’s new implemented code, I didn’t include something like hole or foreground object removal or multi-channel image processing.
For implementing foreground object removal, just alter the map generating part, no matter hole removal or image expansion, all we need to do is set the part of we want to be zero in map.
For implementing 3-channel image texture synthesis, just split the image into 3 different channels, and do what we do with single channel image 3 times, and then merge the 3 channels result as the final result image.
Lastly, there are some people use image pyramid to do texture synthesis, although I never tried it, but I believe it is a good idea to synthesis the information of images on each layer of whatever pyramid, maybe I’ll try this the other day 🙂