Assignment 4 Discrete Cosine Transformation Solution

Introduction

As the key to the JPEG baseline compression process, the Discrete Cosine Transform (DCT) is a mathematical transformation that transforms a signal from spatial representation into frequency representation. In an image, most of the energy will be concentrated in the lower frequencies. So, once an image is transformed into its frequency components, we can treat them selectively, e.g. retaining lower frequency coefficients with high accuracy while squeezing the size of high frequency coefficients, so as to reduce data amount needed to describe the image without sacrificing too much image quality. In practice, a specially configured quantization table will be used to realize such selective operation. In this assignment, you are required to implement a program that performs DCT on a 2D image and quantize its frequency coefficients.



Implementation Guideline

    1. Discrete Cosine Transformation
Given an image    in the spatial domain, the pixel at coordinates (  ,   ) is denoted as   (  ,   ).

To transform    into an image in the frequency domain    , the most straightforward formula is:
  (  ,   ) =   (  )√2    (  ) ∑  −1  =0 ∑  −1  =0  (  , ) cos⁡(     2  +12  )cos⁡(     2  +12  ),

1
      ℎ⁡  (  ) = {√2 ⁡⁡⁡⁡⁡    ⁡   = 0.

1⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡        

However, the implementation above uses four nested loops and has complexity   (  4) for a 2D DCT of size × . Here, you are required to implement a more efficient version. First, the input image ⁡   (with pixel values ranging from 0~255) is preprocessed by shifting pixel value by 128 and get the shifted image ⁡  ̅ (with pixel values ranging from -128~127). Then, it

1

is cut up into blocks of 8 × 8 pixels (e.g. an image of resolution 256 × 256 will be divided into 32 × 32 blocks), and the DCT is applied to each block individually by using row-column decomposition: build a 2D DCT by running a 1D DCT over every row and then every column. Specifically, for each block ̅ with 8 × 8 pixels, the 2D DCT is performed through the following two steps:
•
Apply  1D  DCT  to  row
of
̅
:(  , )=
  (  )
7
̅
2  +1







∑  =0
(  , ) cos (    

),∀   ∈





2


16











{0,1, … ,7}, and repeat it over every row of ̅ .

    • Apply 1D DCT to column of : (u, v) =   (2  ) ∑7  =0 (  , ) cos (     2  +116) , ∀   ∈ {0,1, … ,7}, and repeat it over every column of .


Then, the 8 × 8 frequency coefficient array is obtained. By computing the frequency coefficients for every block, you can get the final DCT result, i.e. a × coefficient array .




    2. Coefficient Quantization

The frequency coefficients generated by DCT are float numbers and many of them have very tiny values. To convert these coefficients into integers while cause less information loss, you are required to quantize the frequency coefficients of every blocks by using the

provided quantization matrix. Specifically, for every element in the coefficient array , the actual formula for quantization is: ̂ (  , ) = ⟦   (  ,  )(  ,  )⟧ , where ⟦⋅⟧ means rounding a float number to the nearest integer, and the 8 × 8 quantization matrix is defined as:


3  5  7  9  11  13  15  17
5  7  9  11  13  15  17  19
7  9  11  13  15  17  19  21

    9  11  13  15  17  19  21  23 11  13  15  17  19  21  23  25 13  15  17  19  21  23  25  27 15  17  19  21  23  25  27  29

17  19  21  23  25  27  29  31
Finally, a    ×    quantized coefficient array ̂ will be achieved.



Basic Requirements: No quantization (80 point)

    1. You are required to implement the Discrete Cosine Transform (DCT) as described in

Section 1 and apply it to the provided testing image.

2
    2. Program must be coded in ANSI C/C++ and uses standard libraries only.

    3. The compiled program must run in Windows 10 command prompt as a console program and accepts source bitmap (.bmp format) with the following syntax and save generated images to the current directory.

C:\> dct <img_path> <apply_quantization>

dct is the executable file of your program, e.g. the command: dct linda.bmp 0 is to transform the input image from spatial domain into frequency domain and output the frequency coefficient array without quantization applied.

<img_path> is the path where the input image is located.

<apply_quantization> specifies whether the obtained frequency coefficients need to be quantized, where 1 means TRUE while 0 means FALSE. Note that basic requirement does NOT require the implementation of the coefficient quantization part.

    4. You are required to submit source code only. We will use Visual Studio 2015 C++ compiler and have your program compiled via Visual Studio command prompt (Tools Command Prompt) with the command line: C:\> cl dct.cpp bmp.cpp (Please ensure your source code gets compiled well with it).




Enhanced Part: With quantization (20 point)

You are further required to implement the coefficient quantization as described in Section 2, which will make the output coefficients be compression-efficient integers.



Submission

We expect the following files zipped into a file named by your SID (e.g. s1234567890.zip)

and have it uploaded to the Blackboard by due date: Apr. 29, 2020 (11:59pm)

    • README.txt (Tell us anything that we should pay attention to)

    • bmp.h & bmp.cpp (No need to change)

    • dct.cpp (write your code in this file only)









3