CSCI 576 Assignment 2

Theory Questions: (50 points)

Question 1: Color Theory (15 points)

One of uses of chromaticity diagrams is to find the gamut of colors given the primaries. It can

also be used to find dominant and complementary colors – Dominant color of a given color D (or

dominant wavelength in a color D) is defined as the spectral color which can be mixed with

white light in order to reproduce the desired D color. Complementary colors are those which

when mixed in some proportion create the color white. Using these definitions and the

understanding of the chromaticity diagram that you have, answer the following.

• In the side image, find the dominant wavelength of

color D. Show this wavelength. (2 points)

• Do all colors have a dominant wavelength? Explain

your reasoning (2 points).

• Find the color which is complimentary to the color

C. Show this color (2 points).

In the next few questions, you are asked to reason about

colors in the chromaticity space that have a specific amount

of R (2 + 2 + 5 points)

• Show the locus of all points or colors that have R=0

• Show the locus of all points or colors that have R=1

• Show the locus of all points or colors that have R=0.5

Question 2: Generic Compression (10 points)

Consider a source that emits an alphabet with three symbols A, B, C having probability

distributions as follows – P(A) = 0.625, P(B) = 0.125, P(C) = 0.25

• Construct a Huffman code and calculate its average code length. (2 points)

• For this three-symbol vocabulary, how many Huffman codes are possible. What are

they? (2 points)

• Is the code you have defined optimal – give reasons! If not, what can you do to

improve upon this. Show a solution by an example computing the avg. code length. (6

points)

D . C .

Question 3: Arithmetic Compression (10 points)

Consider two symbols, A and B, with the probability of occurrence of 0.8 and 0.2, respectively. The

coding efficiency can be improved by combining N symbols at a time (called “symbol blocking”). Say N

= 3, so you are grouping symbols of 3 and giving them a unique code. (Assume that each symbol

occurrence is independent of previous symbol occurrences).

• How many types of different outcomes are there and what are their probabilities? (2 points)

• Show the arrangement of symbols on the unit interval [0, 1] and determine the arithmetic

code for the three-symbol sequence. (6 points)

• What is the average code word length? (2 points)

Question 4: Image Dithering (15 points)

Let’s say that we have an original 12×8 image represented as 8 bits per pixel. In the normalized

representation shown below, assume that 0 corresponds to white and 9 corresponds to black.

Answer the following questions You may want to code/script a process to generate the final

outputs, but only final outputs are expected. Also, we have asked you to plot this 12×8 image

block as a gray color image, and its processed outputs as binary black/white images. For reasons

of visible clarity (because a 12×8 image block is very small) you may want to show a zoomed or

magnified picture.

• Plot the image as an 8-bit gray scale map, that is – create a 12×8 image to show the

original gray image block. (2 points)

• If you thresholded the above 12×8 image block such that all values below 4.5 were 0 and

above 4.5 were 9, how does your output image B/W block look? Plot an image (3 points)

• We can create a better binary image output by using a dithering matrix. Compute the

binary output of a dithering operation on the gray level 12×8 image using the dithering

matrix D given below. Assume that the image top left coordinate indexes are [0, 0].

Show a graphical binary image plot of the dithered output. (5 points)

D =

ú

ú

ú

û

ù

ê

ê

ê

ë

é

5 2 7

1 0 3

6 8 4

• What if the image block’s top left coordinate indexes start with [1, 1]. Show a graphical

binary image plot of the dithered output. (5 points)

Programming on DCT based streaming (150 points)

This programming assignment will help you to understand the working of DCT and how

it is used by standard compression algorithms like JPEG and MPEG. Specifically, you

will implement a DCT based coder-decoder for compressing an image and simulate

decoding using the baseline mode as well as progressive modes of data delivery. Your

program will take as input 4 parameters and be invoked as

myProgram InputImage quantizationLevel DeliveryMode Latency

where the parameters are defined as :

• InputImage – is the image to input to your coder-decoder (you may assume a fixed size

and format that will be described on the class website).

• QuantizationLevel – a factor that will decrease/increase compression as explained below.

This value will range from 0 to 7.

• DeliveryMode – an index ranging from 1, 2, 3. A 1 implies baseline delivery, a 2 implies

progressive delivery using spectral selection, a 3 implies progressive delivery using

successive bit approximation.

• Latency – a variable in milliseconds, which will give a suggestive “sleep” time between

data blocks during decoding. This parameter will be used to “simulate” decoding as data

arrives across low and high band width communication networks.

Your program should display two images – the original on the left and the decoded

version on the right. Here are some example input parameter invocations

1. myProgram Example.rgb 0 1 0

Here you are encoding Example.rgb and using a 0 quantization level, which means no

quantization. You are using the baseline mode and there is no latency so you should see

the whole output image almost instantaneously, taking into account computational time.

2. myProgram Example.rgb 3 1 100

Here you are encoding Example.rgb and using a 3 quantization level. You are using the

baseline mode and there is a latency while decoding and so you should see the output

data blocks appear as they get decoded.

3. myProgram Example.rgb 1 2 100

Here you are encoding Example.rgb and using a 1 quantization level. You are using the

progressive spectral selection mode and there is a latency while decoding and so you

should see the output appear in stages.

And now for the details of each part –

The Encoder

You will have to start, with an RGB image file (images will be kept on the class website).

Implement jpeg-like compressor. Here you will do almost all of the JPEG compression

steps except the entropy coding part (RLE for AC or DPCM for DC, entropy coding) and

producing the actual formatted bit stream. Also, the JPEG pipeline contains chroma

subsampling, but I am not insisting that you convert to YCrCb and subsample Cr,Cb. The main

objective here is to study the DCT and its use in encoding and decoding. So, start with the RGB

image.

• For each component (R, G and B) break it into 8×8 blocks

• For each block, do a DCT on the blocks to compute the DC and AC coefficients. You

will start with 64 f(x,y) pixels and obtain 64 F(u,v) frequency coefficients.

• Quantize the DC and AC coefficients with a uniform quantization table, all of whose

entries are 2N

, where N is the quantization level given as a parameter above. Each table

entry is the same. Quantization works by

F'[u, v] = round ( F[u, v] / 2N

).

An entry here specifies the range of each interval. So if N = 0, then 2N = 1 and hence

every interval has range 1, In this case F'[u, v] is the same as F[u, v] and there is no

quantization effect.

Now you have the DCT coefficients for all the blocks for all the components computed

and quantized. This is the output of the encoder.

The Decoder

The next step is to write a decoder. To decode each image block

• Dequantize all the coefficients. This is done as

F[u, v] = F'[u, v] * 2N

• Do an Inverse DCT on the de-quantized AC and DC coefficients to recover the image

block signal. The recovered image is of course with some loss depending on N.

Simulating various modes of encoding-decoding

The main modes that you will be simulating are baseline, progressive encoding using

spectral selection and progressive encoding using successive bit approximation explained

in class. To better understand the results of this step, you will need to use the last two

parameters – Delivery Mode and Latency. Latency simulates communication at different

bandwidths. You may assume that all the data is not available at once for decoding but

data is available in limited amounts for decoding and display depending on the latency

and the mode used.

For this step you need to implement a display loop, which displays the currently decoded

data. The latency parameter simulates communication for different bandwidths. This

parameter simply controls the time delay (in milliseconds) between packets arriving

during communication. You are not implementing any networked communication as yet,

so this simulation would amount to inserting a “sleep(time)” statement as you are

decoding your data blocks. This means you will have to decode data, display it, sleep for

required latency time and repeat these decode-display-sleep steps for every iteration.

Here is how the decoding should proceed depending on the mode used.

1. Sequential Mode

Each image block is encoded in a single left-to-right, top-to-bottom scan. You may

assume that each latency iteration pertains to ONE BLOCK. So the process progresses as

Decode data of first block and display …sleep

Decode data of second block and display …sleep

…

2. Progressive Mode – Spectral Selection

The DC coefficients of every image blocks is decoded first and displayed. Next the first

AC coefficients is added for all the blocks and decoded. This goes on till all the

coefficients are added to the decoding process. You may assume that each latency

iteration occurs after EVERY SPECIFIC DCT COFFICIENT for all blocks. So the

process progresses as

Decode all blocks using only DC coefficient (set rest to zero) …sleep

Decode all blocks using only DC, AC1 coefficient …. sleep

Decode all blocks using only DC, AC1, AC2 coefficient …. sleep

…

3. Progressive Mode – Successive Bit Approximation

All DC and AC coefficients of all image blocks are decoded first and displayed in a

successive-bit manner. So you will decode all blocks using the all the DC and AC

coefficients, but only using the first significant bit of all coefficients Next, you will

decode all DC and AC coefficients using the first two significant bits of all coefficients

and so on. You may assume that each latency iteration occurs at EACH SIGNIFICANT

BIT usage. So the process progresses as

Decode all blocks using 1st significant bit of all coefficients …sleep

Decode all blocks using 1st , 2nd significant bit of all coefficients …. sleep

Decode all blocks using 1st , 2nd , 3rd significant bit of all coefficients …. sleep

Here is the dataflow pipeline of the encoding and decoding,

Decod

1.Read Input

Image

Display Input

Image

2. Break each

channel into 8×8

blocks

3. Discrete Cosine

Transform

4. Quantize based

on table

5. Dequantize

based on the same

table

Display

Output Image

This code is already provided to you,

if you choose to make use of it

Before DCT, each channel of image

should be divided into 8×8-sized blocks

You need to use DCT function in the

Lecture notes

6. Inverse DCT

and decode

based on

delivery mode

Quantize DC and ACs based on uniform

quantization table

Dequantize DC and ACs based on

uniform quantization table

Encod

Do Inverse DCT and display image

based on mode parameter