K-D Tree-Based Texture Synthesis With Its Applications

The texture includes surface structure distributing and important information of the relation between the surface and background, because it has important application in the pattern recognition and computer vision. It has already made a lot of research results in this respect in recent years, and obtained more and more application in every field. Developing a robust and general texture synthesis algorithm has been proved difficult by the great number of various approaches already done without successfully solving the problem. Here are briefly presented some of those methods. Certain textures can be synthesized by simulating their physical generation process when it is well known. This is only possible for restrained textures classes as biological or natural patterns (fur, scales, skin, cloud and mineral…). Markov Random Fields (or Gibbs sampling in a different mathematical form) model textures in many algorithms, and generate textures by probability sampling. Since Markov Random Fields have been proven to be a good approximation for a wide range of texture types, these algorithms are general and some of them produce good results. However, the Markov Random Field sampling is computationally very expensive. Some algorithms model textures as a set of features, and generate new images by matching the features in a texture sample. Heeger and Bergen model textures by matching marginal histograms of image pyramids. Their technique succeeds on highly stochastic textures but fails on more structured ones. De Bonet synthesizes new images by randomizing an input texture sample while preserving the cross-scale dependencies. This method works well, but it can produce boundary artifacts if the input texture is not tileable. Simoncelli and Portilla generate textures by matching the joint statistics of the image pyramids. Their method can successfully capture global textural structures but fails to preserve local patterns. Markov Random Field methods model a texture as a realization of a local and stationary random process. That is, each pixel of a texture image is characterized by a small set of spatially neighborhood pixels, and this characterization is the same for all pixels. Sliding a small movable window through an image to observe it, the image is said stationary if, under a proper window size, the observable portion always appears similar independently of the window position. The image is local if each pixel is predictable from a small set of neighborhood pixels and is independent of the rest of the image. Based on these locality and stationarity assumptions, the W-L algorithm synthesizes a new texture so that it is locally similar to an example texture patch. The new texture is generated pixel by pixel, and each pixel is determined so that local similarity is preserved between the example texture and the result image. Since the cost of those operations is high, an acceleration process has been developed too. The inputs consist of an example texture patch and a random noise image with the size of the output image set by the user. The algorithm modifies this random noise to make it look like the given example. This technique is flexible and easy to use, since only an example texture patch is required. The algorithm is quite easy to implement; the two major components are a multi-resolution pyramid and a searching algorithm. Studying also parallel studies during my work in order to enrich it, there is an interesting work realized by Michael Ashikhmin. Its main points of interest were the following. It derives from the algorithm by W-L and then was very near and gives to discuss that one. It highly improves the results produced for a rich and familiar class of textures, the natural textures that consist of an arrangement of distinct objects, of irregular but familiar shapes and sizes. Such arrangements are often encountered in nature; examples are grass, tree branches and leafs, pebbles, blossoming flowers, bushes, and forest undergrowth. This algorithm presents also the property of being much faster. The coding complexity is about the same as the basic W-L algorithm, only more introducing the notion of ancestor of an already synthesized pixel. Since both the methods implementations were functioning well, this paper began studying the synthesis user control. That is, how adding a new parameter imposing the output image to obey to some new rule. On the basis of W-L algorithm, this paper firstly proposes another texture of algorithm based on bin-tree weighting algorithms. This algorithm is also pixel-based algorithm of texture synthesis. It has made full use of the dependence principle of texture and characteristic of bin-trees. The main thought of this algorithm is that to calculate the average RGB value of the input texture at first, and to add weight to the distance between the L-shaped neighborhood within the input texture and the average RGB, then construct a bin-tree with those values. In order to simplify the calculation, therepeated nodes will be removed from the bin-tree. When these steps are down well, the bin-tree's height will be controlled efficiently and the searching time will be shorted sharply. According to the properties of texture, we need only the pixel whose L-shaped neighborhood is totally in the input texture without the pixels on the input texture's boundary. When the current pixel is started to fill into the output texture, we just need to calculate the L-shaped neighborhood of the current pixel. And calculate the difference between this value and the average RGB, weighting the difference, and get the result of current pixel. To search the result value into the bin-tree built, and to find the minimum difference and this will be the best position for the current pixel. To return the position of its coordinates, and take the RGB of that point and fill into the output texture. To obtain the great similarity between the input texture and the output texture, many synthesis processes are required. The result of pre-process is the basis of the nest process. After completing the first synthesis processes, the L-shaped neighborhood has been changed to the square ones. While calculating the error of matching, the match region is changed to the whole square neighborhood, and it is necessary to calculate its similarity. Then the current pixel is dependent on the whole match region, and the output texture is most similar to the input ones. When synthesizing the output texture, there will be some pixel fill into it which is not corresponding to the neighborhood, because the distance is calculated by square root, which will produce some differences of two pixel's neighborhood which are same figures with different sign. Actually the result output texture must be affected by it. Although this algorithm is not good at synthesizing the texture with strong structure, the advantages of the computing cost on the L-shaped neighborhood when producing the output texture and the limitation of one dimension when searching the bin-tree's data are very attractive to me. As the result, the speed of computing and searching is more promoted the W-L's algorithm. For solve the limitation of the algorithm mentioned above, this paper study the further research on multi-dimension searching data structure to be the solution of texture synthesis. By studying the advantages and disadvantages of some of the multi-dimension techniques, such as R-tree, quad-tree, and K-D tree, etc, I decided to promote the algorithm above with the K-D tree. This algorithm is absorbed the advantages written in [EF01][LLXGS01][Ash01], and makes of the multi-dimension searching and efficiency and accuracy of K-D tree, the height of searching in K-D tree...