Transform Coding
by Erol Seke
For the course “Data Compression”
ESKİŞEHİR OSMANGAZİ UNIVERSITY
What we mean by Orthogonal Linear Transform
Assume that 𝑥 is a sequence of numbers, presumably with high correlation within.
𝑥𝑛 = 𝑥0 , 𝑥1 , ⋯ , 𝑥𝑁−1, 𝑛 = 0, 1, ⋯ , 𝑁 − 1
than, an orthogonal linear transform can be written as.
𝑁−1
𝑦𝑘 = 𝑓𝑘𝑛 𝑥𝑛 , 𝑘 = 0, 1, ⋯ , 𝑁 − 1
𝑛=0
where 𝑓𝑘𝑛 is called the transform kernel and for 𝑖 ≠ 𝑗
𝑁−1
𝑓𝑖𝑛 𝑓𝑗𝑛 = 0 (orthogonality)
𝑛=0
𝑓𝑘𝑛 spans the 𝑁 dimensional space ℝ𝑁 , that is …
…any possible set 𝑥0 , 𝑥1 , ⋯ , 𝑥𝑁−1 can be constructed by a weighted sum of 𝑓𝑘𝑛 as
𝑁−1
𝑥𝑘 = 𝑎𝑛 𝑓𝑘𝑛 where 𝑎𝑛 are the weights
𝑛=0
In matrix form
𝑥0 𝑓0,0 𝑓0,1 … 𝑓0,𝑁−1
𝑥1 𝑓1,0 𝑓1,1 … 𝑓1,𝑁−1
𝑋= 𝐹=
⋮ ⋮ ⋮ ⋱ ⋮
𝑥𝑁−1 𝑓𝑁−1,0 𝑓𝑁−1,1 … 𝑓𝑁−1,𝑁−1
𝑌 = 𝐹𝑋
For orthogonality and ℝ𝑁 spanning presumptions to hold, 𝑟𝑎𝑛𝑘 𝐹 = 𝑁
Inverse
If 𝐹 −1 is possible ( it should be because 𝑟𝑎𝑛𝑘 𝐹 =𝑁)
𝐺 = 𝐹 −1 is called inverse of the transform kernel, and
𝑋 = 𝐺𝑌 is called the inverse transform
𝑁−1
𝑥𝑛 = 𝑔𝑛𝑘 𝑦𝑘
𝑘=0
𝑁−1
𝑦𝑘 = 𝑓𝑘𝑛 𝑥𝑛 Forward orthogonal linear transform
𝑛=0
𝑁−1
𝑥𝑛 = 𝑔𝑛𝑘 𝑦𝑘 Inverse transform
𝑘=0
2D
For 2D datasets, the same properties must hold
𝑁−1 𝑁−1
𝑦𝑘,𝑙 = 𝑥𝑚,𝑛 𝑓𝑘𝑛,𝑙𝑚
𝑚=0 𝑛=0
If the above summations can be written as
𝑁−1 𝑁−1
𝑦𝑘,𝑙 = 𝑥𝑚,𝑛 𝑢𝑘,𝑛 𝑣𝑙,𝑚
𝑚=0 𝑛=0
the transform is called separable
If 𝑢𝑖,𝑗 = 𝑣𝑖,𝑗 , then the transform is called symmetric
Separable and Symmetric
If the transform is both separable and symmetric, then
The same 1D transform can be applied on the rows of the input data,
followed by the application on the columns of the resulting data
to calculate a 2D transform
1D transform on rows
2D input
1D transform on columns
2D transform result
Discrete Fourier Transform
1D 2D
𝑁−1 𝑀−1 𝑁−1
𝑘𝑛 𝑘𝑛 𝑙𝑚
−𝑗2𝜋 −𝑗2𝜋 +
𝑦𝑘 = 𝑥𝑛 𝑒 𝑁 𝑦𝑘,𝑙 = 𝑥𝑚,𝑛 𝑒 𝑁 𝑀
𝑛=0 𝑚=0 𝑛=0
Inverse 1D Inverse 2D
𝑁−1 𝑀−1 𝑁−1
𝑘𝑛 𝑘𝑛 𝑙𝑚
𝑗2𝜋 𝑁 𝑗2𝜋 𝑁 + 𝑀
𝑥𝑛 = 𝑦𝑘 𝑒 𝑥𝑚,𝑛 = 𝑦𝑘,𝑙 𝑒
𝑘=0 𝑙=0 𝑘=0
What we want from a Transform
to be useful in data compression applications
1. Simplicity in implementation
2. Availability of fast calculation algorithms
3. Possibility of implementation via hardware
4. Usefulness in separating redundant data
We want the transform to be simple enough to be implemented easily (not difficult at least)
For real time applications, the transform must be performed in real time. Read this as “low complexity”.
Hardware implementation is a huge plus, for real time applications.
It should present a reason for employing the transform in compression.
We would not use it just because it is implementable & fast & has inverse.
Discrete Cosine Transform
There exists at least 5 different formulations for DCT
Below is the one used in JPEG compression
2D DCT
𝑀−1 𝑁−1
𝑦𝑘,𝑙 = 𝛼 𝑚 𝛼 𝑛 𝑥𝑚,𝑛 𝑐𝑜𝑠 2𝑛 + 1 𝑘 𝜋Τ2 𝑁 𝑐𝑜𝑠 2𝑚 + 1 𝑙 𝜋Τ2 𝑀
𝑚=0 𝑛=0
1
,𝑠 = 0
𝑁
𝛼 𝑠 =
2
𝑠≠0
𝑁
1D DCT
𝑁−1
1
𝑦𝑘 = 𝑥𝑛 𝑐𝑜𝑠 𝑛+ 𝑘 𝜋Τ𝑁
2
𝑛=0
2D DCT Kernel
What we want from a Transform
Original image DCT coefficients image Inverse transform of this part
The rest are assumed zero
I log(C{I}+1) scaled C-1{Ix}
DCT collects energy towards lower frequency components.
Higher frequency components represent detail and edges.
When HF are removed we loose sharpness and get a blurred image
END