I've been following the recent lectures on Coursera for image processing. In the lecture on the use of the discrete cosine transform (DCT) for image compression, he says that for images that are "Markovian", the DCT has the same properties as the Karhunen-Loeve Transform. He uses this argument to support the use of the DCT in general image compression, since small subsets of natural images usually have this property. What does "Markovian" mean in this context? Is he referring to Markov Random Fields where the graph is constructed by pixels as nodes and edges between neighboring pixels? What are some examples of images that violate this property?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ You shoudl look at the paper: A.K. Jain, “A Fast Karhunen-Loeve Transform for a Class of Random Processes”, IEEE Trans. Comm. Vol 24, Iss. 9, pp. 1023-1029, 1976 $\endgroup$– BatmanJan 27, 2015 at 1:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
It's a probabilistic model that is assumed to generate the image. To make theoretical computations on the performance of certain image processing tasks such as DCT transforming the image for data compression, the image is modelled with a simple mathematical equation.
The Markov image generation model, is used to produce images where there will be high enough correlation between neighbouring samples. This high correlation is therefore efficiently utilized by a transform such as DCT to achieve compression ratios that is close to the maximum available with a nonpractical KLT (Karhunen Loeve Transform)
As far as I know, it is not much related with markovian fields. The simplest 1-D example of such a markov source model, assuming linear dependence between samples, is like: $$x[n] = \rho x[n-1] + {\omega}[n]$$
This simple dependency clearly shows the fact that current sample x[n] is produced from past sample x[n-1] plus a white noise sample w[n], where $\rho$ is the correlating factor and as it is close to 1, samples are highly correlated, when it is close to zero, samples become more noisy and uncorrelated.
For a real image, such a model can only predict samples in a very short duration, because of the non-stationarity of the image. This is one of the reasons why DCT based transforms are applied for short lengths of blocks such as 8x8 pixels.
-
$\begingroup$ The model is often called an AR(1) model. You can write it as a trivial MRF. $\endgroup$– BatmanJan 26, 2015 at 23:35
-
$\begingroup$ Yes an AR-1, Auto-Regressive model of first order is also described like that. Markov models are more general and has a lot of variants such as markov chains used in lossy and lossless coding as well as speech recognition. Here the aim is on the mathematical representation of a correlated set of pixels. $\endgroup$– Fat32Jan 27, 2015 at 0:04
-
$\begingroup$ A point that people may find confusing: Markov models are often taught with time-varying signals. In Image Processing context, images are space-varying signals instead (well, as long as you don't have video). Hence, the Markovian assumption applied to images means that the value/class of a pixel (spatial location) depends only on the values of its close (spatial) neighbours (for example the pixels directly North, South East, West). $\endgroup$– sansuisoJan 27, 2015 at 7:58
-
$\begingroup$ Mathematically speaking, time or space does not make any difference. They are just variables t and x or s and r or a and b. However, when solving a problem, you may use equations based on principles of physics, which will differentiate certain time dynamics from that of space. $\endgroup$– Fat32Jan 27, 2015 at 9:06
-
$\begingroup$ I'm still a bit confused what the constraints are on the dependencies between neighboring samples. In the equation in this answer what are the constraints on
pandw[n]? $\endgroup$– MokoshaJan 28, 2015 at 21:28