GPU-based interactive near-regular texture synthesis for digital human models

2.1Per-patch texture synthesis

Compared with other synthesis method, per-pixel texture synthesis method has a low efficiency. So researchers proposed per-patch texture synthesis. Rather than finding the best-matching pixel, the per-patch texture synthesis method finds a block which contains more pixels.

Efros, for instance, suggested an image-quilting texture synthesis method to synthesize texture in a linear order by finding a best-matching patch [2]. Although this method could produce a relative ideal result, the synthesis processing time is longer. Based on Efros’s method, Schlömer proposed a semi-random texture synthesis [3]. Additionally, Cohen designed the Wang-tiles method [4], which combines the image quilting with the Wang tile algorithm. The Wang tiles method using a series of square texture blocks with different colored-edges to synthesis texture. Same color edges could be combined seamlessly. During synthesis, the blocks that meet the color parameters are chosen to synthesis a large texture.

Per-patch texture synthesis method is much faster than per-pixel method, but it is still hard to meet the real-time interaction request.

2.2Interactive texture synthesis

In 2013, in order to control different level elements of texture (structures in high-level and details in low-level), Ma proposed an easy and intuitive method. These controls can be manually specified, while the corresponding geometric and dynamic repetitions can be computed automatically [5].

Yang proposed a method capable of adjusting the sample in a local area. Part of the texture image could be synthesized under the control of the reference sample texture, resulting in an interactive process [6].

Further research was done following Ma and Yang. Sivaks used neighborhood match to optimize the automatic generation of the process control diagram, and to reduce the store and time costs [7]. Sibbing improved the edge-growing algorithm, and applied it to maintain the synthesis feature [8]. Finally, Rosenberger employed control maps to synthesize the non-stationary textures [9].

2.3GPU-based texture synthesis

Texture synthesis is a computation-intensive process. With the development of GPU, desktop parallel computing hardware and software architecture has become more powerful. Implementing texture synthesis in a parallel mode is, by now, a natural and logical next step.

Generally, image pyramids are constructed for sample and target textures. Meanwhile, the image pyramids method can be executed in a parallel way. Lefebvre introduced appearance vector space to handle texture synthesis. The appearance vector could indicate more structure information due to its larger neighborhood. This method is thus useful for pixel matching [10].

A structured image hybrids synthesis method was proposed by Risser. In this kind of synthesis, the stabilization is coordinated and the global structure image is blended [11]. Huang suggested a random searching based large-scale texture synthesis method, which include two-stage process [12]. The first stage is initialization, which fills the target white texture image using random color; the second stage is iteration, which implements texture-patch matching to optimize the whole texture. This method is also implemented in a parallel way on GPU, but the synthesis process still needs seconds to complete.

Chen proposed a GPU based real time algorithm to synthesize large-scale textures [13]. The algorithm first analyzes the periodicity of the sample texture, and then distributes patches and fills in any vacant areas. Later, an improved method was proposed which could generate a larger size patches from the synthesized texture area [14]. Another improvement was the addition of interactive operations to texture synthesis in order to integrate user control information and exemplar structure. To guarantee an interactive computation time, this method was later implemented on GPU [15]. Wang then proposed a just-in-time method to synthesis texture on GPU. This method considers the texture patch as an umbrella shape, which could eliminate the texture distortion and mapping problems in a short time [16].

In order to get a satisfied result, we combine the global optimization algorithm and the patch-based texture synthesis method. A coarse texture is synthesized using the patch-based method, and then the global optimization algorithm was implemented to refine the coarse texture. Since we implemented both steps on GPU, we were able to achieve a common-size texture within one second.

3.1Algorithm

The first step of near-regular texture synthesis is initializing the target texture image with a random color, such as white Gaussian noise. Then select a patch from target texture in linear order, and looking for a best-matching patch in sample texture. When the best-matching patch is found, copy it to the target texture at the right positon. Repeat these steps until all target texture pixels are confirmed. The global optimization algorithm is then employed to erase the border between two patches. All these steps are implemented in a parallel way on GPU.

Since the initialization of target texture is random, the result of first best-matching patch would also be random. The succeeding results of best-matching patches are equally random, due to the accumulation of initial offset. But in local areas, we used patches selected from exemplar to compose the texture, so the appearance of target texture is consistent with the sample texture. This ensue the local similarity and global randomness of the target texture.

Figure 1 shows the pseudo code of our algorithm. In our algorithm, Is denotes sample texture, Io denotes output texture, Ps denotes a pixel in Is, Po denotes a pixel in Io, N⁢(po) denotes neighborhood of pixel po.

Figure 1.

Pseudo code of the algorithm.

Furthermore, we summarize the algorithm in the pseudo code can be seen in Fig. 1.

The algorithm’s architecture is flexible and made up of several components. Some of these components are as follows:

3.2Edge extraction

The sample plot’s boundary refers to the half-rule texture image grayscale, according to the grey value after the discretization of the boundary’s hierarchical structure (shown in Fig. 2).

Figure 2.

Near-regular texture edge extraction.

The image is divided into five layers based on the pre-defined threshold value of n. In our method, we always assigned n to stand for 3 or 4.

Layer i masks the other layers’ information to show only its own boundary (shown in Fig. 3).

Figure 3.

Near-regular texture edge extraction result.

In our study, we used an iteration in order to extract the edge of a large area. We started with point p, found p’s adjacent boundary point q, and performed the process iteratively until we found all the boundary points. We were able to finish this process due to the boundary’s circularity.

We then repeated this process for each layer, in order to extract all the boundaries of the sample texture with different grey values.

3.3User input and edge disturbance

After successful edge extraction, the user inputs the control edge. The result is a disturbance in the input edge information, according to the extracted information. Our process ensures that the user input has an appearance that consistently matches the sample texture (shown in Fig. 4).

Figure 4.

Edge disturbance.

Following edge disturbance, and in order to fill the closed area, our method launched the patch-based, parallel texture synthesis process.

3.4Texture patch matching

The texture patch matching process implemented in a linear order. Select an N*N size patch t from target texture, and then traversed each patches si with same size in the sample texture S, and compute the L2 distance between si and t as in Eq. (1), and R,G,B are RGB vectors of each pixel.

A small result of L2 distance indicate small texture patch differences, implying that the adjacent patches usually more similar than patches that far away from each other. When all L2 distance are calculated, the patch with the minimum value is chosen as the best match.

After one best-matching patch confirmed in the target texture, the next undetermined patch is selected in a linear scanning order. The displacement distance D along the scanning direction should be smaller than N, which means the size of patch. The overlap area could guarantee the continuity and the data dependency of subsequent patches. Consequently, the appropriate relation between N and D has the capacity to ensure the stability of the synthesis result. In our particular study, we chose N = 2D.

Figure 5 is a sketch of parallel structure on GPU. Each pixel corresponds to a thread. When computing the best-matching neighborhood, each thread works with the neighborhood whose initial pixel corresponds to that particular thread.

Figure 5.

Parallel structure sketch map.

3.5Self-adaptive global optimization

After the first-pass of synthesis, we could get a coarse texture result. The coarse texture has a similar appearance with the sample texture, but there are obvious borders between any two confirmed patches; which divided the texture into several blocks. A self-adaptive global optimization algorithm was used to erase the border between two patch of the synthesized result. The selected energy function as show in Eq. (2).

In Eq. (2), X indicates the pixels in target texture image; x indicates the result of vectorized X, i.e., x is formed by concatenating the intensity values of all pixels in X; Z indicates the pixels in sample image. Therefore, the global energy of the target texture is the sum of the L2 distance of each pixel.

We add a self-adaptive weight in Eq. (3) to make the energy function convergence fast, so that the high frequency information can be eliminated effectively.

Here, ωp stands for the weight, given by ωp=P⁢(xp)⁢∥xp-zp∥r-2 with r= 0.8. P⁢(xp) stands for the probability of finding the best-matching patch in sample texture for the current patch of target texture, in a high-frequency, successful match region.

After each pass of optimization, the neighborhood’s size is reduced by a quarter. The smaller neighborhood could refine the target texture by erase the slight borders. Figure 6a shows the coarse texture which has sharp borders. Figure 6b shows the one-time-pass optimization which has mild borders. Figure 6c shows the two-time-pass optimization which has no obvious borders. Two-time-pass optimization result is the texture whose quality is able to satisfy the application requirements. Consequently, we selected three as the minimum number of optimization. As shown in Kwatra’s method, in order to get a stable result, r should be set to 0.8.

Figure 6.

Comparison of different optimization passes.

Figure 7.

Near-regular texture synthesis result in LOD.