I implemented the texture synthesis algorithm described both in class on 3 October and in Image Quilting for Texture Synthesis and Transfer by Efros and Freeman. For the SSD method, I calculate the sum of squared differences between the overlapped areas (with edge cases so that the top and left edges aren't compared to black (since they don't overlap anything on the top and left, respectively) which would choose darker patches at the edges if it weren't corrected) and choose, out of 1000 random patches, the patch with the least SSD. I decided to choose from among 1000 random patches so that repeated patches would be less common and because exhaustively considering every patch took far longer but produced similar results. The minimum cut version of the algorithm picks the best SSD match but then proceeds to find the minimum cut between this patch and the overlap regions.
Here're the final synthesized patches, with the original texture on the left, and then in order: random, ssd, and min-cut.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
As you can see in the apple, brick, and most notably the polygonal grid textures, although it does do the best job of the three algorithms, even the min cut version has trouble matching straight lines. However, the algorithm works wonderfully on more random textures, like the grass, rice, and toast.
I subsequently extended the min-cut algorithm for texture transfer. It is identical to the min-cut synthesis algorithm, except that when determining the best SSD match, the SSD with the corresponding patch on the target image is also considered in addition to the usual overlapping SSD. I decided to set the alpha value to .5, that is, the SSD with the overlaps and the SSD with the target patch are weighted equally. I'd certainly be interested in further tests to determine the importance of this value.
Here're the final texture transfer images, with the source texture on the left, the target in the middle, and the result on the right.
|
|
|
|
|
|
|
As the Romney example shows, if the target image doesn't have much of a range of intensity values, then the final image won't be very recognizable.
I unfortunately didn't implement anything above and beyond for extra credit.