Texture Synthesis using TSVQ and Target Re-synthesisAnteneh Addis Anteneh∗CMSC 635 - ProjectFigure 1: Texture synthesis through TSVQ and re-synthesis.AbstractThis paper presents a simple texture synthesis method that is fast,efficient, and optimized. Given an input texture, the algorithm willsynthesize a texture image of specified size by matching outputimage pixel neighborhoods with input pixel neighborhoods. Thepixel-neighborhood matching will be aided by the use of a Tree-Structured Vector Quantization (TSVQ) method which will allowthe algorithm to avoid exhaustively searching the input image pix-els. TSVQ method allows the algorithm to construct a binary treethat will serve as a codeword for the pixel types in the input im-age. Re-synthesis will be performed on output textures a numberof times to measure its effectiveness as an optimizing option. Thepresented method combines ideas of synthesis by example with afast texturing algorithm.Keywords: texture synthesis, re-synthesis1 IntroductionThis paper presents a method for efficient texture synthesis thatcombines a number of different approaches in texture synthesiswith Wei and Levoy’s fast texturing algorithm at its core. Themethod will implement a variation of the tree structured vectorquantization method as described in [Wei and Levoy 2000]. Themethod will build the search tree based on the neighborhood value,NV(pxy), for each pixel pxyin the sample texture. The neighbor-hood value will be completed as a vector norm of the RGB valuesin each neighborhood picture. Based on these values, the search∗e-mail: [email protected] will be constructed along the lines of the median cut algo-rithm [Heckbert 1982]. An initial target image, It, will be synthe-sized on an input image of white noise. A second round of synthesiswill be performed using image Itas the input instead of white noise,producing the target image T. The image T will be re-synthesizeda number of times in the experimental phase to see the effects ofre-synthesis as an effective optimizing option.The motivation for this work is to combine different aspects of syn-thesis and vector quantization to have an algorithm that is both fastand also produces quality synthesized images. The re-synthesis ofthe initial target image aids in iteratively improving the similarity ofthe target texture to the sample texture while preserving its differ-ence/randomness that was dictated by the initial input noise image.The next section of this paper will go over some of the related workin this area with an emphasis on their importance to this work.2 Related WorkThis section will summarize previous work that this paper builds onand other related papers.Color Vector Quantization: Vector quantization is a process ofmapping vectors of the same size into a group of representativevectors called code words to build a code map for the whole vectorspace. The median-cut algorithm presented in [Heckbert 1982] isa quantizing method that subdivides color space into smaller andsmaller bins from which a binary search tree is built from. Theoriginal bin is the color space containing all pixels, and this bin issplit into two bins of more or less equal size based on the medianvalue of a range of color values. Wie and Levoy’s algorithm usesthe Tree-Structured Vector Quantization as defined in [Gresho andGray 1992] and uses the nearest point algorithm to match neighbor-hoods [Nene and Nayar 1997].Mutiresolution/Pyramid-Based Sampling: Heeger and Bergenpresent a method for texture synthesis by matching the textural fea-tures of an input texture to an input noise image [1995]. The algo-rithm analyzes the input to get a number of texture parameter valuesand store them in an image pyramid. DeBonet presents a synthesismethod through multiresolution pyramids to capture details of theimage at different levels [DeBonet 1997].Pixel Based Synthesis: Wei and Levoy extend earlier exhaus-tive search algorithms [Efros and Leung 1999] by implementinga multi-resolution synthesis pyramid to allow the use of smallerneighborhood sizes [Wei and Levoy 2000]. They also use tree-structured vector quantization (TSVQ) to accelerate the runtimeof the algorithm. They have shown that synthesis results us-ing TSVQ are comparable in quality to the exhaustive searchmethod but with a synthesis time magnitudes faster than the lat-ter. Ashikhmin [2001] reduces the search state by using informa-tion from earlier neighborhood comparisons. Hertzmann et. al.present a synthesis method by which an input image is synthesizedthrough image analogies of input texture-synthesized texture exam-ple sets [2001].PatchBased Synthesis: These methods perform synthesis by usingpatches from the sample texture. Kwatra et. al. present a method ofsynthesis where irregular patches are copied to the target image andseams are corrected through a graphcut algorithm [2003]. Praunet. al. present a similar method where an arbitrary surface mesh iscovered by repeatedly pasting texture patches from the input[2000].Seams are corrected using alpha blending.Pixel-Patch/Hybrid Synthesis: Patch-based synthesis methodshave proved to be fast and efficient algorithms for texture syn-thesis. Pixel-based searches are in most cases slower put pro-vide the advantage of optimal target images. Pixel-based im-ages have the disadvantage of blurring fine detail, while patch-based methods usually produce unwanted textures along overlap-ping seams. Nealen and Alexa’s method presents a patch-basedsynthesis method that uses pixel-based re-synthesis to eliminate er-rors in overlapped patch regions [2003]. Ashikhmin’s pixel-basedmethod also includes the use of irregular shaped patches to elimi-nate synthesis errors [2001].3 ImplementationAs mentioned above, this work will be a variation on the TSVQmethod of the WL algorithm. The method has three differentphases: 1) the binary search tree is constructed from the input im-age, 2) a white noise image is converted into the initial synthesizedimage Itby using the search tree, 3) re-synthesis is implementedonce, and repeated if necessary.3.1 Tree Construction and SynthesisThe completed search tree is a binary tree that is used as the code-book to classify all of the pixels in the sample image with respectto its neighborhood. This section will first look at initial attemptsat tree construction. Then a working implementation for the searchtree will be discussed.3.1.1 Initial Attempts at Tree ConstructionInitial attempts of tree