---
tags: Digital Image Processing
disqus: hackmd
---
# Part 8

In the last part, the concepts of Fourier Transfrom were being discussed. In this part, the generalized form will be addressed first and other types of transformations will be addressed. The forwards and reverse transformations with kernels can be defined as,
\begin{equation}
T(u,v) = \sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1}f(x,y)g(x,y,u,v)
\end{equation}
\begin{equation}
f(x,y) = \sum_{u = 0}^{N - 1} \sum_{v = 0}^{N - 1}T(u,v)h(x,y,u,v)
\end{equation}
$g$ is the forwards transformation kernel, whereas $h$ is the inverse transformation kernel. The transformation kernel can be separable, say, in case of $g$ if, $g(x,y,u,v) = g_1(x,u)g_2(y,v)$. If $g_1$ and $g_2$ are functionally same, $g(x,y,u,v) = g_1(x,u)g_1(y,v)$. In accordance with the last part, the Fourier Transform kernels can be represented as,
\begin{equation}
g(x,y,u,v) = e^{-j\frac{2\pi}{N}(ux + vy)}, h(x,y,u,v) = g(x,y,u,v) = e^{j\frac{2\pi}{N}(ux + vy)}
\end{equation}
These transformations are symmetric and separable. The separability is shown as,
\begin{equation}
g(x,y,u,v) = g_1(x,u)g_1(y,v) = \frac{1}{\sqrt{N}}e^{-j\frac{2\pi}{N}ux}.\frac{1}{\sqrt{N}}e^{-j\frac{2\pi}{N}vy}
\end{equation}

## Discrete Cosine Transform (DCT)

The kernels for DCT can be defined as,
\begin{equation}
g(x,y,u,v) = \alpha(u)\alpha(v)\cos{\bigg[\frac{(2x + 1)u\pi}{2N} \bigg]}\cos{\bigg[\frac{(2y + 1)v\pi}{2N} \bigg]} = h(x,y,u,v)
\end{equation}
The kernels are symmetric and separable, as can be seen easily. The other unknown parameters are defined as,
\begin{equation}
\alpha(u) =
\begin{cases}
\sqrt{\frac{1}{N}}, u = 0 \\ \sqrt{\frac{2}{N}}, u = 1,2,...,N - 1
\end{cases}
\end{equation}
Similarly,
\begin{equation}
\alpha(v) =
\begin{cases}
\sqrt{\frac{1}{N}}, v = 0 \\ \sqrt{\frac{2}{N}}, v = 1,2,...,N - 1
\end{cases}
\end{equation}
Now that we have the kernel, the DCT expression can be written as,
\begin{equation}
C(u,v) = \alpha(u)\alpha(v)\sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1} f(x,y)\cos{\bigg[\frac{(2x + 1)u\pi}{2N} \bigg]}\cos{\bigg[\frac{(2y + 1)v\pi}{2N} \bigg]}
\end{equation}
Similarly, the inverse transform is defined as,
\begin{equation}
f(x,y) = \sum_{u = 0}^{N - 1} \sum_{v = 0}^{N - 1} \alpha(u)\alpha(v)C(u,v)\cos{\bigg[\frac{(2x + 1)u\pi}{2N} \bigg]}\cos{\bigg[\frac{(2y + 1)v\pi}{2N} \bigg]}
\end{equation}
It has some properties, which will be written down later.

## Walsh Transformation

In one dimension,
\begin{equation}
g(x,u) = \frac{1}{N}\prod_{i = 0}^{n - 1}(-1)^{b_i(x)b_{n - 1 - i}(u)}
\end{equation}
$N$ gives the number of samples and $n$ is the number of bits needed to represent $x$ and $u$.
Here, $b_k(z)$ represents k$^{th}$ bit in the digital or binary representation of $z$.
So, for 1D, the Walsh transformation can be written as,
\begin{equation}
w(u) = \frac{1}{N}\sum_{x = 0}^{N - 1}f(x)\prod_{i = 0}^{n - 1}(-1)^{b_i(x)b_{n - 1 - i}(u)}
\end{equation}
The inverse kernel is the same as the forward kernel. Therefore, the inverse transformation can be written as,
\begin{equation}
f(x) = \frac{1}{N}\sum_{u = 0}^{N - 1}w(u)\prod_{i = 0}^{n - 1}(-1)^{b_i(x)b_{n - 1 - i}(u)}
\end{equation}

In case of images, we have the forward as well as the inverse kernel as,
\begin{equation}
g(x,y,u,v) = \frac{1}{N}\prod_{i = 0}^{n - 1}(-1)^{{b_i(x)b_{n - 1 - i}(u)} + b_i(y)b_{n - 1 - i}(v)}
\end{equation}
Therefore, the forward transformation can be written as,
\begin{equation}
w(u,v) = \sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1}f(x,y)\frac{1}{N}\prod_{i = 0}^{n - 1}(-1)^{{b_i(x)b_{n - 1 - i}(u)} + b_i(y)b_{n - 1 - i}(v)}
\end{equation}
The inverse transformation can be written as,
\begin{equation}
f(x,y) = \sum_{u = 0}^{N - 1} \sum_{v = 0}^{N - 1}w(u,v)\frac{1}{N}\prod_{i = 0}^{n - 1}(-1)^{{b_i(x)b_{n - 1 - i}(u)} + b_i(y)b_{n - 1 - i}(v)}
\end{equation}

To understand the output, the basis images for $4 \times 4$ image can be seen as,
This also has energy compaction property, however it is not as strong as DCT. Note that the kernel is symmetric and separable. It is also possible to perform this method in a fast way, like FFT. So,
\begin{equation}
w(u) = \frac{1}{2}[w_{even}(u) + w_{odd}(u)]
\end{equation}
Similarly,
\begin{equation}
w(u + M) = \frac{1}{2}[w_{even}(u) - w_{odd}(u)]
\end{equation}
Where, $u = 0,1,...,N/2 - 1$ and $M = N/2$.

## Hadamard Transformation

For 1D case,
\begin{equation}
g(x,u) = \frac{1}{N}(-1)^{\sum_{i = 0}^{n - 1}b_i(x)b_i(u)}
\end{equation}
The Hadamard transformation can be written as,
\begin{equation}
H(u) = \frac{1}{N}\sum_{x = 0}^{N - 1}f(x)(-1)^{\sum_{i = 0}^{n - 1}b_i(x)b_i(u)}
\end{equation}
The inverse kernel is same as the forward kernel. Therefore, inverse transformation can be written as,
\begin{equation}
f(x) = \frac{1}{N}\sum_{u = 0}^{N - 1}H(u)(-1)^{\sum_{i = 0}^{n - 1}b_i(x)b_i(u)}
\end{equation}
In case of two dimension, it can be written as,
\begin{equation}
H(u,v) = \frac{1}{N}\sum_{x = 0}^{N - 1}\sum_{y = 0}^{N - 1}f(x,y)(-1)^{\sum_{i = 0}^{n - 1}b_i(x)b_i(u) + b_i(y)b_i(v)}
\end{equation}
The inverse transformation can be written as,
\begin{equation}
f(x,y) = \frac{1}{N}\sum_{u = 0}^{N - 1}\sum_{v = 0}^{N - 1}H(u,v)(-1)^{\sum_{i = 0}^{n - 1}b_i(x)b_i(u) + b_i(y)b_i(v)}
\end{equation}
If $\frac{1}{N}$ is removed, then the transformation leads to a matrix called Hadamard Matrix. Example, for $N = 8$ is,
The matrix is made up of smaller $2 \times 2$ matrix. For a $2 \times 2$ bracket inside the matrix, it is seen that the first, second and third element are the same matrix, whereas the fourth one is the negation of the other three. This pattern is repeated for the entire matrix.

For $N = 2$, the Hadamard matrix is,
\begin{bmatrix}
1 & 1 \\ 1 & -1
\end{bmatrix}
This can be generalized for $N = 2N$ as,
\begin{equation}
H_{2N} =
\begin{bmatrix}
H_N & H_N \\ H_N & H_{-N}
\end{bmatrix}
\end{equation}
Another important property of Hadamard transformation is that if each column sign changes are seen, it forms a sequence. In case of $N = 8$, the sequence is $0,7,3,4,1,6,2,5$. Here, the sequence looks random, unlike DCT and DFT. To make this sequence logical, another kernel needs to be used. So,
\begin{equation}
g(x,u) = \frac{1}{N}(-1)^{\sum_{i = 0}^{n - 1}b_i(x)p_i(u)}
\end{equation}
Where, $p_0(u) = b_{n - 1}(u)$, $p_1(u) = b_{n - 1}(u) + b_{n - 2}(u)$, $p_2(u) = b_{n - 2}(u) + b_{n - 3}(u)$$,...,$$p_{n - 1}(u) = b_1(u) + b_0(u)$.
So, the new matrix obtained for $N = 8$ (say) is,
The sequence is now $0,1,2,3,4,5,6,7$. This is Ordered Hadamard Transformation. If it is compared with the Walsh Transformation, we have,
They look almost identical, except for the ordering of basis images. Energy compaction property is more than the Walsh transformation.

The final comparison for 'Lena' is,
Here, we can see that DCT has much more energy compaction unlike other cases, and therefore it is used in data compression techniques.