Predictive coding

As natural signals are highly correlated, the difference between neighboring samples is usually small. The value of a pixel x can be therefore predicted by its neighbors a, b, c, and d with a small error:

$$e_1=x-a,\;\;\;\;e_2=x-b,\;\;\;\;e_3=x-\frac{a+b+c+d}{4}$$

In general, the predicted value $\hat{x}_0$ for a pixel $x_0$ is a linear combination of all available neighbors $a_i,\;(i=1,\cdots,n)$:

$$\hat{x}_0=\sum_{j=1}^n a_j x_j$$

The entropy of the histogram of the error image hist(e) is much smaller than that of the histogram of the original image hist(x), therefore Huffman coding will be much more effective for the error image than the original one.

Optimal predictive coding

The mean square error of the predictive error is:

$$E(e^2)=E[ (x_0-\hat{x}_0)^2 ]=E(x_0^2)-2E(x_0 \hat{x}_0)+E(\hat{x}^2_0)$$

where

$$\hat{x}_0=\sum_{j=1}^n a_j x_j$$

To find the optimal coefficients $a_i$ so that $E(e^2) \rightarrow min$ is minimized, we let

$$\frac{\partial}{\partial a_i} E(e^2) =\frac{\partial}{\parti... ...E(\hat{x}^2_0)-2\frac{\partial}{\partial a_i}E(x_0\hat{x}_0) =0$$

but as

$$2\frac{\partial}{\partial a_i}E(x_0\hat{x}_0)= 2E(x_0\frac{\partial}{\partial a_i}\sum_{j=1}^n a_j x_j)=2E(x_0 \cdot x_i)$$

and

$$\frac{\partial}{\partial a_i}E(\hat{x}^2_0) =2E(\hat{x}_0 \f... ...j=1}^n a_j x_j \cdot x_i) =2\sum_{j=1}^n a_j E(x_j \cdot x_i)$$

we have

$$E(x_0 \cdot x_i)=\sum_{j=1}^n a_j E(x_j \cdot x_i)$$

Here

$$E(x_i x_j)=r_{ij}$$

is the correlation between $x_i$ and $x_j$ which can be estimated from data obtained from multiple trials:

$$\hat{r}_{ij}=\hat{E}(x_i x_j)=\frac{1}{K}\sum_{k=1}^K x_i^{(k)} x_j^{(k)}$$

Now the optimal prediction above can be written as

$$r_{0i}=\sum_{j=1}^n a_j r_{ij},\;\;\;\;\;(j=1,\cdots,n)$$

which can be expressed in vector form:

$${\bf r}_0=R {\bf a}$$

where

$${\bf r}_0=\left[ \begin{array}{c}r_{01} \cdots r_{0n} \... ... ... & r_{ij} & ... \\ ... & ... & ... \end{array} \right]$$

Then the coefficients can be found as

$${\bf a} = R^{-1}{\bf r}_0$$

To prevent predictive error from being accumulated, we require

$$\sum_{j=1}^n a_j< 1$$

so that the errors will not propagate.

Examples

$$\hat{x}(i,j)=0.9\;x(i,j-1)$$

$$\hat{x}(i,j)=0.9\;x(i-1,j)$$

$$\hat{x}(i,j)=0.7\;x(i,j-1)+0.7\;x(i-1,j)-0.5\;x(i-1,j-1)$$

$$\hat{x}(i,j)=\left\{ \begin{array}{ll} 0.9 \; x(i,j-1) & \m... ...angle v \\ 0.9 \; x(i-1,j) & \mbox{else} \end{array} \right.$$

where

$$\triangle h=\vert x(i-1,j)-x(i-1,j-1)\vert,\;\;\;\;\triangle v=\vert x(i,j-1)-x(i-1,j-1)\vert$$