Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Comparison of Image Compression Techniques: SVD and DCT
63
Comparison of Image Compression Techniques: SVD and DCT
Introduction
- What is Data compression theory useful for?
- How do we define it?
Introduction
Overview of Data Compression
- Reducing bits to represent data
- Saves storage capacity, speeds up file transfer, and decreases storage hardware and network bandwidth costs.
- Encoding data reduces the file size
- Two kinds of compression techniques:
- Lossless compression
- Lossy Compression
Data Compression
Lossless Compression
Lossless Compression
- Encode data without compromising its integrity
- Used in applications intolerant of differences between original and reconstructed data
- Example use: Radiology
Lossy Compression
- Involve some loss of information
- Can obtain a much higher compression ratio
- Example use: Audios/Videos
Lossy
Compression
Singular Value
Decomposition
- Used to decompose a given matrix into three matrices denoted as, U, ∑, and V
- U and V are orthogonal and ∑ is a diagonal matrix containing the sorted singular values of the input matrix in descending order.
- The equation below shows the size of the U, ∑, and V matrices for a given mxn input matrix:
SVD
Example
Consider the 3×2 matrix show below:
Matrix
Calculate (A^T)A
Yields the matrix below:
Step 1
Use matrix in step 1 to form V
Eigenvector for A^T A is calculated
Step 2
The eigenvalues of matrix A are given by
Eigenvector for
Eigenvector formation
Eigenvector for
Continuation
Calculating
V and V^T
Calculating V
Using the formula for ui,
we find u1 and u2
Step 3
For u3
Finding u3
Combining
u1, u2 and u3
Calculating U
- Singular values computed by taking the square root of eigenvalues
- Arranged in descending order in the diagonal matrix
Step 4
Finally:
Result
Applying SVD in image compression
Image
- SVD rewrites original matrix as a sum of simpler matrices of rank one
- When applied to an image matrix, SVD decomposes it into three different matrices
- Application of SVD does not imply compression
- After SVD, most of the singular values will be discarded
- Singular values are arranged in descending order of the diagonal matrix
Example
Discrete Cosine Transform
- Designed to discard information that the human eye cannot easily see
- Separates images into components of different frequencies
- Less important frequencies are discarded
- Important frequencies used to retrieve the image during decompression
DCT
The DCT Equation
Equation
- This equation computes the i, jth entry of the transformed image from the pixel values of the original matrix
- N is the size of the block
- p(x, y) is the x, yth element of the image represented by the matrix p
- Standard 8×8 block that JPEG compression uses means that N would be 8 and x and y would range from 0 to 7
Matrix form of the DCT equation
Matrix of DCT Equation
Example of DCT
The 8×8 block represented below is a segment of a black and white image. The pixel values for a grayscale image range from 0 to 255, where pure black is represented by 0, and pure white by 255
Matrix
Leveling off
Because DCT is designed to work on pixel values ranging from -128 to 127, the original block needs to be “leveled off”. This is done by substracting 128 from each entry. The resulting matrix is shown below
Step 1
DCT performed, accomplished by matrix multiplication
D = TMT'
Step 2
Quantization
- 8×8 block of DCT coefficients is now compressed by quantization
- Varying levels of quality and image compression obtained through the selection of specific quantization matrices
- Allows decision on quality levels to be made
- JPEG standard quantization matrix is set at Q50
Step 3
Quantization achieved by using
Result of Quantization
Coding
The quantized matrix C is then coded to a stream of binary data. Since most of the coefficients equal to zero, JPEG takes advantage of this fact and encodes in the zig-zag sequence shown below.
Step 4
Applying DCT in image compression
Image
Summary of the overall process:
- The image is broken into 8×8 blocks of pixels
- Working from left to right and top to bottom, Discrete Cosine Transform (DCT) is applied to each of the 8×8 blocks.
- Each block is compressed through Quantization
- The array of compressed blocks that constitute the image is stored in a drastically reduced amount of space.
- When desired, the image is reconstructed through decompression using Inverse Discrete Cosine Transform (IDCT)
Example
Result
The table above shows the result of SVD, while the table below shows DCT
Result and Conclusion
Maximum Compression
Comparison of Result
Similar Size
Similar Size
Conclusion
Conclusion
- Report examines difference between two lossy compression techniques, SVD and DCT
- Each technique is unique
- Difference in image quality
- Difference in distortion
- SVD had higher compression ratio than DCT compression, along with better image quality