Pixel-based Non-parametric Sampling

Pixel-based non-parametric sampling [29], proposed by Efros and Leung, constrains pixel sampling using a similarity metric defined with respect to a local neighbourhood system in an MRF.

Figure 5.3: The `L'-shaped neighbourhood in a pixel-based non-parametric sampling (a $3 \times 3$ neighbourhood window in this case). Each square represents a pixel and the arrows indicate the synthesis is performed in a raster scanline order.

The method assumes an MGRF model of textures so that a pixel $i \in {g}$ only depends on the pixels in a local neighbourhood $\mathcal{N}_i \in {g}$. The distance between neighbourhoods $\mathcal{N}_i$ and $\mathcal{N}_j$, e.g., the sum-of-square-difference (SSD), provides a metric of pixel similarity between $i$ and $j$. To synthesise a pixel $i$, the algorithm searches for a pixel $j$ from the training texture that minimises the distance between $\mathcal{N}_i$ and $\mathcal{N}_j$, and then uses the value of pixel $j$ for pixel $i$.

Figure 5.4: Synthesised textures by pixel-based non-parametric sampling [29].

The constraint to pixel selection is very similar to the multi-resolution sampling approach [22], except that this one is based on a local neighbourhood but the previous one on a hierarchical parent structure. In the multi-resolution sampling, the synthesis has to be carried out in a top-down manner, because a parent structure is defined with respect to higher pyramid levels (see Eq. (5.3.4)). In this method, to maximise the number of synthesised pixels in the neighbourhood of current pixel, the synthesis is performed pixel by pixel in a raster scan-line order. Considering the simplest case that the algorithm synthesises an image from top to bottom and left to right, since only the known parts (already synthesised pixels) of the neighbourhoods are involved in computing the distance, the actual neighbourhood has `L' shape, as shown in Fig 5.3.

The synthesis algorithm is outlined in Algorithm 4, where $D(\mathcal{N}_j, \mathcal{N}_i)$ denotes a selected distance function for neighbourhood comparison. Figure 5.4 shows synthesised textures by the pixel-based non-parametric sampling [29].

In this method, Markov property of a texture is preserved in a non-parametric way; it ranks samples of observed pixel neighbourhoods and selects the closest one based on a similarity metric. Essentially, the sampling attempts to maintain local integrity of texture. This method can have several disadvantages. First, the synthesis grows texture pixel by pixel sequentially, which tends to blur features or to grow small local structures (garbage growing) [29]. Second, the synthesis involves exhaustive search for a pixel having the closest neighbourhood, which could be time consuming especially when a large-size texture or neighbourhood window is involved. Although it outperforms model-based synthesis in synthesis speed, pixel-based non-parametric sampling is still far from real-time. Third, selection of the geometric structure for the local neighbourhood (size and shape) is largely heuristic. Figure 5.5 shows the importance of a correct local neighbourhood (only the size in this example) to the synthesis result of a pixel-based non-parametric sampling method [104]. However, because a local neighbourhood is usually texture-dependent, i.e. related to the characteristics of each individual texture, it might be difficult to find a proper structure without texture modelling,

Figure 5.5: Results of pixel-based non-parametric sampling with different sizes of rectangular local neighbourhood [104].

A similar pixel-based non-parametric sampling technique, proposed by Wei and Levoy, exploits tree-structured vector quantisation (TSVQ) to speed up neighbourhood searching [104]. This method involves a similarity measure based on a multi-resolution local neighbourhood structure, consisting of pixels from both the current and the next lower levels of an image pyramid. This structure is a mixture of the parent structure in [22] and the local neighbourhood in [29]. By including pixels from an coarser level, it reduces the size of local neighbourhood and thus saves computation time. To avoid the exhaustive neighbourhood searching, this method builds a binary TSVQ tree in which each pixel neighbourhood for the training texture is coded by a node. Since the TSVQ tree is a data structure providing computationally more feasible nearest-point queries, the problem of neighbourhood matching is solved the nearest-point search that traverses the TSVQ tree [104].

Another variation of pixel-based non-parametric sampling, proposed by Ashikhmin, is for synthesising natural textures [1]. The method modifies the sampling process by explicitly accounting for pixel interdependency in the training image. That is, for a current pixel to be synthesised, instead of from a random location, the neighbourhood search starts from the surrounding areas where already-synthesised neighbouring pixels were sampled in the training image. For example, ``if a pixel two rows above and one column to the right of current position was taken from position $(x=37, y=15)$ in the input sample, the new candidate is pixel $(x=36,y=17)$ in the input sample'' [1]. Since it restricts the search space in a small region, this heuristic greatly reduces the searching time. In addition, it tends to `follow' coherent local structures (e.g., a leaf) appeared in many natural textures. The method does not work well on textures without `any significant amount of high frequency component' [1]. Since this method tends to follow and move a group of connected signals (e.g., a small region) from the training texture onto the synthetic one, the behaviour is similar to a group of block-based non-parametric sampling techniques.