Homework 7.1: Digital Image Processing
Author: Qifan Zhang
Get Started
To get started, please simply fork this GitLab repository and follow the structure and submissions guidelines below. Remember to change your repo to a private one before you commit to it.
Kind Reminder:
The following tasks are arranged from easy to hard. Arrange your coding plan well.
This homework takes 15% of the programming part, so take it seriously and start as early as possible We have offered a big bonus (up to 8% of the programming part), which is called Homework 7.2. Of course, the higher the bonus is, the more you need to pay. Start early and be “wealthy”.
Repository Structure 10_Huffman_coding.pdf/ppt
This is the slide file for Huffman coding, which could be a reference for Task 8
04_imgproc.pdf
This is the slide file of Lecture 4 of CS148 in Stanford, which will help you understand the concept of convolution in Task 7.
README.md/pdf
Problem description and requirements.
DIP.py
A basic template for this homework. It also includes some simple testing codes.
Submit
You should check in DIP.py to Gitlab.
First, make a commit and push your own DIP.py . From the root of this repo, run:
Then add a tag to request grading on your current submission:
1 2 3
git add DIP.py
git commit -m”{Your commit message}”
git push origin master
1
git tag {tagname} && git push origin {tagname}
Beware that all of your tag names should be distinguished among one homework repo. Therefore, remember to use a new tag name {tagname} in each submission.
Every submission will create a new Gitlab issue, where you can track the progress.
Regulations
Due: 23:59:59, June 1 (Saturday), 2019, CST
No late submission will be accepted.
You could only import and use built-in modules.
You have 30 chances of grading (i.e. git tag ) in this homework (i.e. Homework 7.1. Homework 7.1 and 7.2 will separately be counted). You are able to require grading at most 10 times every 24 hours. If you hand in more 30 times, each extra submission will lead to 10% deduction.
Hard code is strictly forbidden. Once found, your score of this homework will be set as 0.
We enforce academic integrity strictly. If you participate in any from of cheating, you will fail this course immediately. You can view full edition on Piazza.
If you have any question about this homework, please ask on Piazza first.
Overall Description
Alice and Bob are good friends. They have classes together, do homework together, study cryptology together and so on. Once, they shared their Gitlab accounts and then both got punished, which made them very angry, especially at a TA called Mr. Sailboat.
In order to relax themselves and forget that awkward incident, during Labor Day holiday, they went out for sightseeing and got some raw pictures (i.e. without being processed by image processing algorithms). However, raw images are always far from satisfaction. Mr. Sailboat now invites you to help them finish this job by performing some ‘magic’ on some images.
All images provided by Mr. Sailboat are gray scale images.
Task 1.1: Load in an Image
In order to process an image, you first need to load it in.
The basic element for an image is pixel , which is stored by a non-negative integer. In computer, an integer is stored by several bits . When we call an image ” an n-bit image “, n tells us how many bits will be used to store one pixel. In the other word, given , a valid pixel value will be an integer in the range of . Of course, should be a positive integer or it will be meaningless.
Mr. Sailboat will now give you an -bit image in the form of a matrix expression. The expression is defined using EBNF form below.
1 2 3 4 5
Matrix = “[“, {blank}, Rows, {blank}, “]” | “[“, {blank}, “]”;
Rows = {blank}, Row, {blank} | {blank}, Row ,{blank}, “;”, {blank}, Rows, {blank};
Row = {blank}, pixel, {blank} | {blank}, pixel, {blank}, “,”, {blank}, Row, {blank};
pixel = int | float | complex;
blank = ” ” | “\n” | “\r” | “\t”;
However, Mr. Sailboat is such a careless guy. As you have observed above, Mr Sailboat may give an invalid image matrix. If you meet an mistake, you need raise an exception. All possible exceptions are listed below:
PixelSyntaxError
As stated above, a valid syntax should be an integer in the range of ( is 8 by default if it is not given).
Once you found this property is not held in the given image matrix, you should raise PixelSyntaxError . MatrixSizeError
Each row of the given matrix must have the same number of columns. In the other word, the number of elements in each row of the matrix should be the same.
Once you found this property is not held in the given image matrix, you should raise MatrixSizeError . PixelBitError
As stated above, should be a positive integer or it will be meaningless.
Once you found this property is not held in the given , you should raise PixelBitError .
All the given matrices will have at most one of the above 3 exceptions.
Note: You should first judge whether is valid before handling other exceptions. Once is invalid, you should
directly raise PixelBitError and do not care about other possible exceptions. Once you finish your implementation, test it in console by:
Task 1.2: Print out the Image
In this task, you should implement your class Image() in order to make it possible to print the image matrix out via function print() .
The printing format is quite similar with the input one. The only difference is that there should be no redundant characters in your output. The output is defined using EBNF form below.
1 2 3 4 5
>>> imageInput = ‘[1,2,3,4;5,6,7,8;9,10,11,12]’
>>> n = 8
>>> img = Image(ImageInput, n)
>>> # or
>>> img = Image(ImageInput) # n is not given, then see the image as 8-bit image by
default
1 2 3 4
Matrix = “[” Rows “]” | “[” “]” ;
Rows = Row | Row “;” Rows ;
Row = pixel | pixel “,” Row ;
pixel = int | float | complex;
Once you finish your implementation, test it in console by:
Task 2: Image Addition and Equalization
Sometimes, you may need to synthesize two (or even more) images together in order to get a better one. Also, you need to know whether it is the 2 images are the same.
In this task you need to realize this feature.
For addition, there are 2 images which has the same number of rows and columns. You need add values of 2 pixels with the same coordinates in 2 images.You may meet the following 3 errors:
PixelSyntaxError
When adding two images together, there may be one or a few pixels exceeding the storage range of the given bits. When you meet this error, you should raise PixelSyntaxError .
BitUnmatchedError
Two images should have the same . If they are not the same, you should raise BitUnmatchedError . ImageSizeUnmatchedError
Two images that is added together should has the same number of rows and columns. Otherwise All the given test cases will have at most one of the above 3 exceptions.
For equalization, you should return True while the images are the same. If not, return False . Notice that if s of two images are not the same, they are definitely not the same.
Once you finish your implementation, test it in console by:
1 2 3
>>> x = Image(“[1,2,3; 4,5,6; 7,8,9]”)
>>> print(x)
[1,2,3;4,5,6;7,8,9]
Task 3: Gray Scale Reversion
In this task, you will need to reverse their color into its opposite one in gray scale. To be more explicit, for each pixel , it should be transferred into with the relationship:
The task should be implemented as a method of Image named reverse() . There will be no possible exception.
Once you finish your implementation, test it in console by:
Task 4: Bit Extension and Compression
Storage space is also a big issue for an image. Sometimes we need to allocate more bits (i.e. extension) for each pixel in order to store an image with higher quality while sometimes we need to shrink the current bits (i.e. compression) into fewer bits. In this task, you should implement it in method bitChange() .
To be more explicit, for each pixel , it should be transferred into with the relationship:
is the new given while is the initial . If is not given, set it as 8 by default.
Just like Task 1, you may meet PixelBitError . The property of the new given is the same as what has been
stated in Task 1. Once you found this property is not held in the given , you should raise PixelBitError . Once you finish your implementation, test it in console by:
1 2 3 4
>>> a = Image(‘[1,2,3,4;5,6,7,8]’)
>>> b = a.reverse()
>>> b == Image(‘[254,253,252,251;250,249,248,247]’)
True
1 2 3 4 5 6 7 8 9
>>> a = ‘[1,2,3,4;5,6,7,8;9,10,11,12]’
>>> b = ‘[5,6,4,7;1,2,3,4;10,10,10,10]’
>>> img1 = Image(a)
>>> img2 = Image(b)
>>> img3 = img1 + img2
>>> img3 == Image(‘[6,8,7,11;6,8,10,12;19,20,21,22]’)
True
>>> img3 == Image(‘[0,0,0,0]’)
False
1 2 3 4 5 6 7 8 9
Task 5: Image Indexing
During processing, you may want to get part of the image or a particular pixel. Also, you may want to replace a particular pixel or part of the image with a new one. In this task, you need to finish this task in order to index the image just like using a list.
The following are tasks you need to do ( x is a given Image() class): x[i] returns the i -th row (starting at 0 ) which also is a matrix
If is invalid, raise
returns the element at the -th row and j -th column
i
IndexSyntaxError
x[i,j]
i
If or or both are invalid, raise replaces the element
If or j or both are invalid, raise If is invalid, raise
replaces the row
and the row are identical, otherwise raise the exception
. by in
. .
i
j
IndexSyntaxError
x[i,j] = k
k
i
k
x[i] = Image(..)
PixelSyntaxError
x[i,j]
x
IndexSyntaxError
by the row Image(..) in
if the lengths of the row x[i]
x[i]
x
Image(..)
If i is invalid, raise IndexSyntaxError
If the Image() which replaces the original one does not have the same n with the original one, raise BitUnmatchedError .
returns the image , such that is the element x[start1+i*step1,start2+j*step2] if it exists and ,
IndexSyntaxError
x[start1:stop1:step1,start2:stop2:step2]
If
If
If the
raise BitUnmatchedError .
Once you finish your implementation, test it in console by:
start1:stop1:step1,start2:stop2:step2
start1+i*step1
>>> a1 = a.bitChange()
>>> b = Image(‘[1,2,3,4;5,6,7,8]’, 4)
>>> b1 = b.bitChange(8)
>>> a1 == b1
True
>>> b2 = b.bitChange(7)
>>> a1 == b2
False
x[start1+i*step1,start2+j*step2]
IndexSyntaxError
Image(..)
is invalid, raise
which replaces the original one does not have the same with the original one,
start1:stop1:step1,start2:stop2:step2
IndexSyntaxError
Image()
n
>>> x = Image(“[1,2,3; 4,5,6; 7,8,9]”)
>>> y = Image(“[0,1,2; 3,4,5; 6,7,8]”)
Task 6.1: Histogram
First, if you do not know a histogram, you could go to Histogram for details.
In this task, you need to calculate the distribution of pixel values of the given image. To replace an image version of histogram, you need to store your result in a list , where . is an integer in the range of which represents value of pixel, should be the times of the related pixel value appearing in the given image matrix.
This task is implemented in the method his() . There should be no exception in task.
Once you finish implementation, test it in console by:
Task 6.2: Histogram Equalization
Histogram equalization usually increases the global contrast of many images, especially when the usable data of the image is represented by close contrast values. Through this adjustment, the intensities can be better distributed on the histogram. This allows for areas of lower local contrast to gain a higher contrast. Histogram equalization accomplishes this by effectively spreading out the most frequent intensity values.
1 2 3 4
>>> x = Image(“[1,2,3; 4,5,6; 7,8,9]”, 4)
>>> h = x.his()
>>> h == [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
True
3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
>>> z = x[2]
>>> print(z)
[7,8,9]
>>> x[2,1] 8
>>> z = x[1:3:1,0:3:2]
>>> print(z)
[4,6;7,9]
>>> x[2] = Image(“[17,18,19]”)
>>> print(x)
[1,2,3;4,5,6;17,18,19]
>>> x[1,2] = 0
>>> print(x)
[1,2,3;4,5,0;17,18,19]
>>> x[1:3:1,0:3:2] = Image(“[14,16;7,9]”)
>>> print(x)
[1,2,3;14,5,16;7,18,9]
For more information, you could go to Wikipedia.
In this task, you need to implement a method hiseq() to do histogram equalization on an image i .
Algorithm
Here is the algorithm for this task: 1. Calculate i_his = i_1.his()
2. Calculate probability of occurrence for each valid value. using i_his , while is:
where , is the total number of all the pixels.
Notice that here you should keep 4 decimals for each . If there are more than 4 decimals, you
should round it using function round(x,4) ( ).
3. Calculate Cumulative Probability Density function (a.k.a. CDF) for each . You can get CDF by the formula:
where
4. Get the new value of the pixel. After calculating CDF out, each value was transformed from initial value into new value with transformation:
Once you finish implementation, test it in console by:
Homework 7.2 (Bonus): Advanced Digital Image Processing
Get Started
To get started, please simply fork this GitLab repository and follow the structure and submissions guidelines below. Remember to change your repo to a private one before you commit to it.
Kind Reminder: Please do not try to do this homework without Homework 7.2 is accepted. Tough there are only 2 tasks, they are much more difficult than Task 1-6 since you need to spend some time learning some basic linear algebra (Task 7) and some data structure (Task 8) first.
Repository Structure
1 2 3 4
>>> x = Image(“[1,1,3; 4,4,5; 7,7,7]”, 4)
>>> x_hiseq = x.hiseq()
>>> print(x_hiseq)
[3,3,4;8,8,9;14,14,14]
10_Huffman_coding.pdf/ppt
This is the slide file for Huffman coding, which could be a reference for Task 8
04_imgproc.pdf
This is the slide file of Lecture 4 of CS148 in Stanford, which will help you understand the concept of convolution in Task 7.
README.md
Problem description and requirements.
DIP.py
A basic template for this homework. It also includes some simple testing codes.
Submit
You should check in DIP.py to Gitlab.
First, make a commit and push your own DIP.py . From the root of this repo, run:
Then add a tag to request grading on your current submission:
Beware that all of your tag names should be distinguished among one homework repo. Therefore, remember to use a new tag name {tagname} in each submission.
Every submission will create a new Gitlab issue, where you can track the progress.
Regulations
Due: 23:59:59, June 3 (Monday), 2019, CST
No late submission will be accepted.
You could only import and use built-in modules.
You have 30 chances of grading (i.e. git tag ) in this homework. You are able to require grading at most 10 times every 24 hours. If you hand in more 30 times, each extra submission will lead to 10% deduction. Hard code is strictly forbidden. Once found, your score of this homework will be set as 0.
We enforce academic integrity strictly. If you participate in any from of cheating, you will fail this course immediately. You can view full edition on Piazza.
If you have any question about this homework, please ask on Piazza first.
Overall Description
1 2 3
git add DIP.py
git commit -m”{Your commit message}”
git push origin master
1
git tag {tagname} && git push origin {tagname}
Alice and Bob are good friends. They have classes together, do homework together, study cryptology together and so on. Once, they shared their Gitlab accounts and then both got punished, which made them very angry, especially at a TA called Mr. Sailboat.
In order to relax themselves and forget that awkward incident, during Labor Day holiday, they went out for sightseeing and got some raw pictures (i.e. without being processed by image processing algorithms). However, raw images are always far from satisfaction. Mr. Sailboat now invites you to help them finish this job by performing some ‘magic’ on some images.
All images provided by Mr. Sailboat are gray scale images.
Task 7: Convolution Between Image and Kernel
Convolution is a very important operation in Signal Processing domain. For digital image processing, it is often used in spatial filtering, which will optimize the image in a fast and easy way but still get good results. In Task 7 you need to implement an operation * , i.e. method __mul__() to utilize this operation.
Kernel
Suppose we do convolution on Matrix with Matrix , denoted as A*B , then B is called a kenerel . A kernel is a matrix which holds following properties:
1. It is a squared matrix, i.e. is an matrix
2. is an odd number
3. To make it simple, all valid elements in should be integers
Of course, when one of the properties is not held, an exception should be raised. There are 3 possible exceptions:
MatrixSizeError
If property 1 or/and 2 is not held, raise this error
KenelElementError
If property 3 is not held, raise this error.
PixelNegError
If any pixel has a negative value after convolution, then raise this error.
Notes:
Notice that does not always exist, so you have 2 options: Zero-padding
Extend A into a larger size with 0
Do a check whether exists for each and
How to Calculate
For detailed introduction to 2D convolution, you could see CS148 Lecture 4 Slides, which has been included in this repo as 04_imgproc.pdf . It will also be covered in discussion of Week 14.
Input and Output
You need to implement Image.__mul__(self, kernel) method
To simplify your task, the kernel is given in the form of a matrix in string same as the form in Task 1.1. The
expression is defined using EBNF form below.
You should return an Image class which has been convolved with the kernel.
Task 8: Advanced Image Compression – Huffman Coding
In Task 4, we have implemented a naive image compression method using bit changing. However, it will damage quality of the image too much. In this task, you will implement another compression algorithm, which compresses the image a lot but without loss of image quality. The algorithm is Huffman Coding .
For Huffman Coding, you could see the slides 10_Huffman_coding.pdf/ppt attached in this repository (also available on Piazza. Link: here) to have a detailed view. This will also be covered in the discussion on Week 14.
In this task, you need to generate Huffman Codes for pixel values and finally encode them with Huffman Codes you have gotten.
Specification
Priority will not be the main topic in this task. So Mr. Sailboat will carefully construct test cases in order to avoid same priority when sorting in priority queue. Therefore, feel free to use built-in sorting function such as
sort() when dealing with sorting issue.
Input and Output
You need to implement Image.huffman()
There is no input.
You should return a string s which stores Huffman-coded pixels row by row and column by column. Suppose is an matrix. If written in formula, it is:
(P.S. the + for s is the same with the + for type str in Python) Example:
1 2 3 4 5
Matrix = “[“, {blank}, Rows, {blank}, “]” | “[“, {blank}, “]”;
Rows = {blank}, Row, {blank} | {blank}, Row ,{blank}, “;”, {blank}, Rows, {blank};
Row = {blank}, pixel, {blank} | {blank}, pixel, {blank}, “,”, {blank}, Row, {blank};
pixel = int | float | complex;
blank = ” ” | “\n” | “\r” | “\t”;
1 2 3
>>> img1 = Image(‘[1,2,2,3,5,3;3,3,4,4,5,3;4,4,5,5,5,3]’)
>>> print(img1.huffman())
000001001111011111101011011010110101011