4 ms·

I don't think this method has anything to do with Markov Chains. The spatial structure isn't explicitly used at all, and the interpolation/regression is quite a

• dahart 9y ago
  > I don't think this method has anything to do with Markov Chains. Oh, it absolutely does. I think it's fair to say that Efros launched the field of nearest neighbor texture synthesis, and his abstract states: "The texture synthesis process grows a new image outward from an initial seed, one pixel at a time. A Markov random field model is assumed, and the conditional distribution of a pixel given all its neighbors synthesized so far is estimated by querying the sample image and finding all similar neighborhoods. This is the same Markov model that all subsequent texture synthesis papers are implicitly using, including the paper at the top of this thread. Efros' paper implemented directly is really slow, so a huge number of subsequent papers use the same conceptual framework, and are only adding methods for making the method performant and practical. (Sometimes, at the cost of some quality -- many cannot synthesize text, for example.) Note the inspiration for text synthesis, Shannon's paper, also describes the "Markoff Process" explicitly. http://math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf http://math.harvard.edu/~ctm/home/text/others/shannon/entrop... (Efros referenced Shannon, and noted on his web page: "Special thanks goes to Prof. Joe Zachary who taught my undergrad data structures course and had us implement Shannon's text synthesis program which was the inspiration for this project.") > Well, of course almost anything can be interpreted as a Markov process, I don't think it's a very useful abstraction here. It's not an abstraction to build a conditional probability table and then sample from it repeatedly to synthesize a new output. That's what a Markov process is, and that's what the paper posted here is doing. I don't really understand why you feel it's distant and abstract, but if you want to elaborate, I am willing to listen!
  • jampekka 9y ago
    Unless I horribly misread the paper, this is not based on the Efros' quilting method, which indeed uses Markov fields. The method linked here seems to interpolate every pixel independently from its surroundings (neighbor means a close-by pixel in the training set in the feature space, not a spatially close pixel). And I didn't mean that Markov processes are abstract in any "distant" sense, but that they are an abstraction, ie a "perspective" from which to approach and formulate the problem.
    • dahart 9y ago
      I was referring to Efros' "non-parametric sampling" paper, not the quilting one. Efros defined "non-parametric sampling" as another name for "Markov chain" -- almost (see my edit below). This paper (PixelNN) refers directly to "non-parametric sampling" in the same sense as Efros, and it states that they are using "nearest neighbor" to mean "non-parametric sampling". This is talking rather explicitly about a Markov chain -like process. "To address these limitations, we appeal to a classic learning architecture that can naturally allow for multiple outputs and user-control: non-parametric models, or nearest-neighbors (NN). Though quite a classic approach [11, 15, 20, 24], it has largely been abandoned in recent history with the advent of deep architectures. Intuitively, NN works by requiring a large training set of pairs of (incomplete inputs, high-quality outputs), and works by simply matching the an incomplete query to the training set and returning the corresponding output. This trivially generalizes to multiple outputs through K-NN and allows for intuitive user control through on-the-fly modification of the training set..." Note the first reference #11 is Efros' non-parametric sampling, and that the authors state this is the "classic approach" that they apply here. What you call "interpolate every pixel independently from its surroundings" could be another way to describe a Markov chain, because 1: it is sampled according to the conditional probability distribution (which is what you get by using the K nearest matches.) and 2: the process is repeated - one pixel (or patch) is added using the best match, then it becomes part of the neighborhood in the search for the pixel/patch next door. The name for that is "Markov process", or in the discrete case, "Markov chain", if you take an unbiased random sample from the conditional distribution. If you always choose the best sample, then it's the same as a Markov chain, but biased. > (neighbor means a close-by pixel in the training set in the feature space, not a spatially close pixel) That's right, and that's why it's misleading to talk about nearest neighbor interpolation, because that phrase is a graphics phrase that means interpolate from spatially close pixels. Hardly anyone else calls it interpolation, they call it sampling, point sampling, and other terms. *EDIT: I'm going to relax a little bit on this. "Non-parametric sampling" is a tiny bit different from a Markov process in that a Markov process attempts to simulate a distribution in an unbiased way. By using the best match instead of a random sample from the conditional distribution, the output may produce a biased version of the original distribution. This is why it's called non-parametric sampling instead of calling it a Markov chain, but the distinction is pretty small and subtle -- texture synthesis using non parametric sampling is extremely similar to a Markov chain, but not necessarily exactly the same. Side note, it's really unfortunate they used the abbreviation "NN" to talk about "nearest neighbor" in a paper that also builds on "neural networks".