Publications will be filled in within the next few days.

Claude E. Shannon, Noshirwan Petigara and Satwiksai Seshasai
Bibtex entry: Shannon48
Commentary: In Section 2 of Part I of his seminal publicaton, Shannon describes a stochastic discrete source of information. In Section 3, he demonstrates that when we base our emission frequencies on a natural language, this stochastic source functions as an approximation whose verisimilitude improves with the order of the conditional probability function.

While in Shannon's time, using this algorithm to generate text was tedious at best, modern computers make rapid large-scale synthesis entirely feasible, and emission frequencies are easily learned from any body of text.

This is a very useful algorithm which forms a basis for most of my work. It is also important to note that there is no reason the domain has to be discrete – emission probabilities may easily be formulated for series of real numbers, or real-valued vectors.

Rupert Paget and I. D. Longstaff
Bibtex entry: Paget98texturesynthesis
Commentary: Paget and Longstaff propose a robust model for representation of textures and demonstrate that their model synthesises even highly structured textures reliably.

Their approach is based on sampling a Markov Random Field with locally-conditioned PDFs inferred from a source image. To capture even high-order features even with lower-order neighbourhoods, they synthesize on a multigrid – that is, a coarse resolution image is first synthesized from a downsampled example, and this information is then used on lower, more refined levels.

To that end, they propose a histogram LCPDF that is easily acquired and a pixel temperature function that controls when synthesis should advance to the next level.

Their approach is not without problems, however. A discrete histogram function, while easily learned and compared (comparison of different models is in fact the point of their method), suffers from combinatorial explosion even on a low number of value levels and low neighbourhoods, and has to be ammended by gaussian kernel interpolation. A more sophisticated LCPDF model for continuous domains would be preferable.

Furthermore, their pixel temperature function does not, in fact, take the LCPDF values into account – it only calculates the new pixel temperature from the neighbouring pixel temperatures and a constant. Thus, it is merely a very roundabout way of simply directly specifying how many times should each pixel be sampled. It merely adds complexity without actually providing any information on the rate of convergence of the MRF, which would help tremendously in determining when to go over to the next level.

Vivek Kwatra, Irfan Essa, Aaron Bobick and Nippun Kwatra
Bibtex entry: Kwatra05
Commentary: Kwatra et al. present a new approach to example based texture synthesis. They describe it as a hybrid between patch-based and pixel-based methods that updates areas rather than single pixels, but individual pixels are allowed to deviate individually. They achieve this by formulating a texture energy function. Given a metric distance between two pixel neighbourhoods, the energy of the entire texture is defined as $\sum_{p} ||x_p-z_x||^2$, where $p$ is a set of all output pixel neighbourhoods (that is, of all pixels in the image and their respective neighbourhoods $x_p$) and $z_p$ is the nearest neighbourhood to $x_p$ from the source image, given the neighbourhood distance metric.

To synthesize an image, they would repeatedly select a neighbourhood from the output image, find its nearest neighbour in the input and solve a set of equations to minimize this energy. They further propose to modify the energy by using different exponents and coefficients, and finally demonstrate how their approach can be used to visualize dynamic flow fields.

Their approach lends itself quite well to multiscale synthesis, either by resampling the image as in Paget's method, or iteratively decreasing the neighbourhood size. There is, however, a problem with their optimization algorithm itself. Kwatra et al. state that to minimize energy, one has to either solve a set of quadratic equations, or calculate the equivalent of a mean of an exponential distribution. A key point they neglect to consider is that however a distance metric is defined, it is trivially minimized when $x_p = z_p$, making the entire EM algorithm superfluous.

Still, the algorithm produces visually pleasing and plausible results, and the energy minimization approach has potential. If it could be demonstrated that the energy measure correlates with image verisimilitude, and if it could be efficiently calculated (or estimated), it could become a basis for more computationally efficient approaches. Unfortunately, it does not appear that this approach would lend itself well to synthesis from weighted examples. It would be possible to formulate a metric that could assign lower ditance values to points from a certain subset, but this could enormously complicate k-NN computation.

Amir Rosenberger, Daniel Cohen-Or and Dani Lischinski
Bibtex entry: Rosenberger09
Commentary: Rosenberger et al. tackle the problem of synthesizing inhomogeneous layered textures using their own shape synthesis algorithm. This algorithm synthesizes shapes from example by iteratively optimizing a similarity measure defined on shape boundaries. Synthesized layer texture then forms a basis for texture synthesis, preserving properties predominantly exhibited by textures generated by certain natural processes, such as paint peeling.

While this algorithm generates more plausible results than general synthesis methods, it has its own limitations imposed by the formulation of the shape synthesis algorithm. For example, in row 5 of figure 8, it is clearly visible that the assumption of rotational invariance of shape features is often violated even in layered models. Furthermore, the algorithm is still inhomogeneous with respect to pixel position, resulting in out-of-place features.

A more subtle, but still rather disruptive problem is that their method only works on boundaries and does not attempt to optimize internal areas of a layer. This becomes visible when shapes in the example have a low area to circumference ratio, or more plainly have holes. This is visible for instance in the first row of the same figure, where the yellow layer in the example is punctuated by patches of blue, while in the output it is more often solid. One could attempt to remedy this by using more scale levels of synthesis, but this still has the same fundamental limitations and can only be completely removed by also considering the inside of the shape for optimization. This may, however, drive the computational cost too high.

An interesting question might be whether the same results could not be achieved using a hidden Markov model. It certainly has greater expressive power and can easily be made inhomogeneous, but the computational requirements for learning and synthesis could be too high. Additionally, some clustering-based method could attempt to determine the number of layers automatically, rather than having them specified by the user or fixed.