This write-up has 3 parts. The first part provides an explanation of your implementation tasks. It refers to code that is provided in the appendices in the third part. The second part lists the tasks for you to do. It contains space for you to enter your solutions to some of the problems. The third part lists code which is referred to in the first part.
You have to fill in the solutions in the second part, and complete the code files in the accompanying src/ folder as described in Part 1. Please work in this file, hw1.tex, and not in a copy. When submitting, please remove the first and third parts from this file.
Part I Explanation
In this assignment, we will implement an ArrayList to represent a List. We will use the List to implement an image and will write operations for the image.
1 Image Operations
We will work with RGB images and perform four operations on them–channel suppression, rotations, mask application, and resize. None of these operations is destructive. That is, the operations do not alter the original image, rather they return a new image containing the result of the operation.
1.1 Channel Suppression
An image is said to contain color values in different channels. In an RGB image, the channels are Red, Blue, and Green. Each channel contains the intensities for that color for every pixel in the image. The values from all three channels at a pixel yield the RGB value at the pixel. A channel suppression operation switches off a specific channel. That is, all intensities in that channel are turned to zero, or turned off. Figure 1 shows an original image and two modifications, one with the blue channel turned off, and the other with only the blue channel turned on, i.e. the red and green channels turned off.
1.2 Rotation
Given a square image, i.e. one whose width is equal to its height, this operation generates a new image that contains rotations of the original image. Figure 2 shows an example of applying the operation. The resulting image has twice the dimensions of the original image, i.e. twice the width and twice the height. It contains 4 appropriately placed sub-images which, going anti-clockwise are the original image rotated anti-clockwise by increments of 90◦.
(a) An RGB image of a swimming (b) The image with the blue chan- (c) The original image with only
pool.
nel turned off. the blue channel turned on.
Figure 1: Example of channel suppression.
1.3
Applying a Mask
(a) A square image.
(b) The image obtained as a result of ap- plying rotations to the original image.
Figure 2: Example of rotation.
A mask specifies certain weights and applying the mask to an image entails replacing the value at each pixel in the image with a weighted sum or weighted average of the values of its neighbors. The weights and the neighbors to consider for the average are specified by the mask.
A mask is an n × n array of integers representing weights. For our purposes, n must be odd. This means that the n × n array has a well defined center–the origin. The weights in the mask can be arbitrary integers–positive, negative, or zero.
For each pixel in the input image, think of the mask as being placed on top of the image so its origin is on the pixel we wish to examine. The intensity value of each pixel under the mask is multiplied by the corresponding value in the mask that covers it. These products are added together. Always use the original values for each pixel for each mask calculation, not the new values that you compute as you process the image.
For example, refer to Figure 3a, which shows the 3 × 3 mask,
131 353 131
and an image on which we want to perform the mask computation. Suppose we want to compute the result of the mask computation for pixel e. This result would be:
a+3b+c+3d+5e+3f +g+3h+i
Some masks require a weighted average instead of a weighted sum. The weighted average in the case of Figure 3a for pixel e would be:
a+3b+c+3d+5e+3f +g+3h+i 1+3+1+3+5+3+1+3+1
(a) Overlay the 3×3 mask over the image so it is centered on pixel e to compute the new value for pixel e.
Figure 3: Applying a mask to an image.
Instead of doing this calculation for each channel individually at a pixel, for the purpose of this calculation, replace the value of each channel at the pixel with the average channel value at the pixel. For example, if the pixel is given by (r, g, b) = (107, 9, 218), then apply the mask to the average value (107 + 9 + 218)//3 = 111 (integer division) and copy the result to each channel of the corresponding pixel in the output image. This effectively converts the output image to grayscale.
Note that sometimes when you center the mask over a pixel, the mask will hang over the edge of the image. In this case, compute the weighted sum of only those pixels that the mask covers. For the example shown in Figure 3b, the weighted sum for the pixel e is given by:
and the weighted average is as follows.
3b+c+5e+3f +3h+i
3b+c+5e+3f +3h+i 3+1+5+3+3+1
(b) If the mask hangs over the edge of the image, use only those mask values that cover the image in the weighted sum.
Integer division is used when computing averages in order to ensure that pixel intensities are integers.
1.3.1 Applications of Masks
Applying different masks leads to different properties. For example, applying the following mask leads to blurring of the image. Figures 4a and 4b show the blurring effect of this mask. Note that color information
is lost as mentioned above.
24542 4 9 12 9 4 5 12 15 12 5. 4 9 12 9 4
24542
Another application we use is an implementation of Canny Edge Detection using Sobel Operators. Once the image has been blurred as above, two more filters, or masks, (the Sobel operators) are applied in succession to the blurred image. These filters determine the change in intensity, which approximates the
(a) An image with sharp details and several lines.
(b) Result of applying the blur mask (c) Result of applying the Sobel fil- to the original image. ters to the blurred image.
Figure 4: Blurring and detection of edges in an image using masks. horizontal and vertical derivatives.
−1 0 1 −1 −2 −1 Gx=−2 0 2, Gy= 0 0 0 .
−1 0 1 1 2 1
After these operations are applied one after the other to the blurred image, the values obtained are used to search for edges based on the magnitude and direction of the change in intensity. An example of the final result is shown in Figure 4c.
1.4 Resize
Given an image, this operation generates a new image that has twice the dimensions of the original image i.e, twice the width and twice the height. Figure 5 shows a 4×3 image which is resized to twice its size. The resized image has 4 times as many pixels and some of them take on the values from the original image as shown. For the pixels shown to be blank, color values are not known and have to be computed from the known values. Consider the labeled pixels in the resized image below. One way to fill in the missing color information is as follows.
P = 21 ( A + B ) , T = 12 ( C + D ) , Q = 21 ( A + C ) , S = 12 ( B + D ) Page 4 of 20
Figure 5: Bilinear Interpolation
There are various ways to compute R, all of which are ultimately equivalent.
R= 12(P+T)= 12(S+Q)= 14(A+B+C+D)= 14(P+Q+S+T)= 18(A+B+C+D+P+Q+S+T)
The boundary pixels pose a problem as some of the neighboring pixels required for the average do not exist. In such cases, only the existing neighbors are used for the average.
Notice how all the above expressions are affine combinations. Furthermore, the colors for P, Q, S, and T are linearly interpolated from their horizontal or vertical neighbors. The color for R is a bilinear interpolation: it is a linear interpolation of P and T, or Q and S, which are themselves linear interpolations.
Note: All divisions in the above expressions are integer divisions.
2 Image
We treat an image as a grid of pixels where each pixel is represented as an RGB value indicating the red, green, and blue intensities of the pixel. An image has dimensions, namely width and height, which determine the number of rows and columns in the image. Every pixel in the image is at a unique combination of row and column numbers which can therefore be used as a coordinate system in the image. An image with width w and height h is said to be of size w×h. Figure 6a shows the column and row numbers in a w×h image along with the resulting pixel coordinates. Note that the coordinate is just a means to locate a pixel in the image, it is not the value stored at the pixel. The value stored at a pixel is a triplet denoting the red, green, and blue intensities respectively.
We will work with a flattened representation of an image. That is, we will store the pixel values in a 1-dimensional list structure as opposed to a 2-dimensional structure (programming languages generally store multi-dimensional arrays in their flattened form) . The list stores pixel values as they appear in the image from left to right and top to bottom. Figure 6b shows a 5 × 5 image with some supposed RGB values. Note that each value would be a triplet of integers, each integer between 0 and 255 inclusive. Using our representation, the image in Figure 6b will be represented as the list:
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y]
Spring 2023
- 0 (0,0)
- 1 (1,0)
- 2 (2,0)
(0,1) (0,2) … (1,1) (1,2) … (2,1) (2,2) …
(0,w − 1) (1,w − 1) (2,w − 1)
Columns
0 1 2 … (w−1)
abcde fghij klmno pqrst uvwxy
……. ……
(h − 1) (h − 1, 0) (h − 1, 1) (h − 1, 2) . . . (h − 1, w − 1)
(a) Row and column numbers of an image with width w and height h. Pixel (b) A 5 × 5 image with supposed
coordinates are also shown. pixel values.
Figure 6: Image dimensions and pixel coordinates.
3 Implementation Details and Tasks
We will be working with a MyImage class as shown in Listing 1 on Page 9, also included in the accompanying file src/myimage.py. Its implementation is complete but requires a concrete implementation of MyList which is our implementation of the List interface. The implementation to be used is specified in the constructor of MyImage.
An implementation of MyList is shown in Listing 2 on Page 12, also included in the accompanying file src/mylist.py. The implementation is mostly complete except for the segments marked as pass. These are to be implemented appropriately in the subclasses of MyList which are indicated at the end of the listing and whose implementation is completely missing. Writing their implementations is one of your tasks in this assignment.
Once you are done implementing MyList subclasses, the MyImage class is ready to be operated on. Functions corresponding to the operations described in Section 1 are shown in Listing 3 on Page 16 and included in the accompanying file src/image operations.py. None of the operations is destructive. That is, each operates on a MyImage instance and returns the result as a new MyImage instance. The functions are missing implementations. Writing their implementations is another of your tasks in this assignment.
3.1 Tasks
- Go over the provided files thoroughly in order to understand what they do or are expected to do.
- Provide implementations for unimplemented methods, i.e. those that have pass in their body.
- Derive ArrayList class from MyList and provide its implementation in the same file. ArrayList implements the list using python arrays.
3.2 Requirement
You will need to install Pillow which will prove the PIL module used in the provided code. 3.3 Tips
Below are some tips to avoid the errors that have previously caused tests to fail. Following these may save you many frustrating hours of debugging!
- Delay division as much as possible and perform int division wherever needed.
- When writing gray values to file, make sure to clamp them to [0,255].
- Take care about imagine indexing.
- Be careful when creating a copy of the image. Use the copy where needed and the original where needed.
Do not forget to average the RGB values when the corresponding flag in apply_mask is enabled.
Take care about efficiency. Some structures are slow. If, on top, your code is inefficient, the automated tests may fail due to time out.
3.4 Testing
Once you have successfully implemented the subclasses and image operations, you can test your code by creating an image and performing operations on it. Your submission will be tested automatically by GitHub using the accompnaying pytest file, test image.py.
4 Credits
This homework is adapted from Homework 3 of the Fall 2014 offering of 15-122: Principles of Imperative Computation at Carnegie Mellon University (CMU).
Part II
Problems
The grading is defined in the accompanying rubric file.
1. Implementation
Complete the tasks listed in Section 3.1 by providing the implementations in the indicated files.
2. Amortized Analysis
Consider an ArrayStack implementation of the List interface with a slightly altered resize() operation. Instead of reserving space for 2n elements in the new array, it reserves space for n + ⌈ n4 ⌉ elements. Prove that the append() operation still takes O(1) time in the amortized sense.
Data Structures II
Part III Appendices
A MyImage
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
|
from PIL import Image |
|
class MyImage: |
|
methods to allow iteration over this image. “”” |
|
def __init__(self, size: (int, int)) -> None: |
|
“””Initializes a black image of the given size. |
|
Parameters: |
|
– size: (width, height) specifies the dimensions to create. |
|
Returns: none |
|
“”” |
|
width , height = self.size = size |
|
value=(0, 0, 0)) |
|
def __iter__(self) -> ‘MyImage’: |
|
this image. |
|
Parameters: |
|
Returns: |
|
an iterator (self) that allows iteration over this image. ”’ |
|
# Initialize iteration indexes. self._iter_r: int = 0 |
|
self._iter_c: int = 0 return self |
|
def __next__(self): |
|
Image pixels are iterated over in a left-to-right, top-to-bottom order. |
|
Parameters: |
|
– self: mandatory reference to this object |
|
Returns: |
|
”’ |
|
if self._iter_r < self.size[1]: # Iteration within image bounds. # Save current value as per iteration variables. Update the |
|
# variables for the next iteration as per the iteration # order. Return saved value. |
|
value = self.get(self._iter_r , self._iter_c) self._iter_c += 1 |
|
if self._iter_c == self.size[0]: |
Page 9 of 20
59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
CS 201 Data Structures II
Homework 1: Lists
Spring 2023
|
self._iter_c = 0 |
|
self._iter_r += 1 return value else: # Image bounds exceeded, end of iteration. |
|
# Reset iteration variables , end iteration. self._iter_r = self._iter_c = 0 |
|
raise StopIteration |
|
def _get_index(self, r: int, c: int) -> int: |
|
This is an internal function for use in class methods only. It should |
|
not be used or called from outside the class. |
|
Parameters: |
|
– r: the row coordinate |
|
Returns: |
|
the list index corresponding to the given row and column coordinates “”” |
|
# Confirm bounds, compute and return list index. width , height = self.size |
|
assert 0 <= r < height and 0 <= c < width, “Bad image coordinates: “\ f”(r, c): ({r}, {c}) for image of size: {self.size}” |
|
return r*width + c |
|
def open(path: str) -> ‘MyImage’: |
|
The image format is inferred from the file name. The read image is |
|
converted to RGB as our type only stores RGB. |
|
Parameters: |
|
Returns: |
|
the image created using the information from file path. “”” |
|
# Use PIL to read the image information and store it in our instance. img: Image = Image.open(path) |
|
myimg: MyImage = MyImage(img.size) |
|
img: Image = img.convert(‘RGB’) |
|
# copy to our instance and return it. for i, rgb in enumerate(list(img.getdata())): |
|
myimg.pixels.set(i, rgb) return myimg |
|
def save(self , path: str) -> None: |
|
“””Saves the image to the given file path. |
|
The image format is inferred from the file name. |
|
Parameters: |
|
– path: the image has to be saved here. |
|
Returns: none |
|
“”” |
|
img: Image = Image.new(“RGB”, self.size) img.putdata([rgb for rgb in self.pixels]) |
|
img.save(path) |
|
def get(self, r: int, c: int) -> (int, int, int): |
|
Parameters: |
|
– self: mandatory reference to this object – r: the row coordinate |
|
– c: the column coordinate |
|
Returns: |
|
“”” return self.pixels[self._get_index(r, c)] |
|
def set(self, r: int, c: int, rgb: (int, int, int)) -> None: |
|
“””Write the rgb value at the pixel at the given row and column coordinates. |
|
Parameters: |
|
– r: the row coordinate |
|
– rgb: the rgb value to write |
|
Returns: none |
|
“”” self.pixels[self._get_index(r, c)] = rgb |
|
def show(self) -> None: |
|
“””Display the image in a GUI window. |
|
Parameters: |
|
Returns: none |
|
“”” |
|
img: Image = Image.new(“RGB”, self.size) img.putdata([rgb for rgb in self.pixels]) |
|
img.show() |
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
Code Listing 1: Image Type
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
import array as arr |
|
class MyList: |
|
”’A list interface. Also implements Iterator functions in order to support iteration over this list. |
|
def __init__(self, size: int, value=None) -> None: |
|
“””Creates a list of the given size, optionally intializing elements to value. |
|
The list is static. It only has space for size elements. |
|
Parameters: |
|
– size: size of the list; space is reserved for these many elements. – value: the optional initial value of the created elements. |
|
Returns: |
|
none “”” |
|
self.lst_arr = [value] * size |
|
def __len__(self) -> int: |
|
Ref: https://stackoverflow.com/q/7642434/1382487 |
|
Parameters: |
|
– self: mandatory reference to this object |
|
Returns: |
|
”’ return len(self.lst_arr) |
|
def __getitem__(self, i: int): |
|
”’Returns the value at index, i. Allows indexing syntax. |
|
Ref: https://stackoverflow.com/a/33882066/1382487 |
|
Parameters: |
|
– i: the index from which to retrieve the value. |
|
Returns: |
|
”’ # Ensure bounds. |
|
assert 0 <= i < len(self),\ |
|
return self.lst_arr[i] |
|
def __setitem__(self, i: int, value) -> None: |
|
Ref: https://stackoverflow.com/a/33882066/1382487 |
|
Parameters: |
|
– self: mandatory reference to this object – i: the index of the elemnent to be set |
|
– value: the value to be set |
|
Returns: none |
Page 12 of 20
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130
|
”’ |
|
# Ensure bounds. assert 0 <= i < len(self),\ |
|
self.lst_arr[i] = value |
|
def __iter__(self) -> ‘MyList’: |
|
this list. |
|
Parameters: |
|
Returns: |
|
an iterator (self) that allows iteration over this list. ”’ |
|
# Initialize iteration index. self._iter_index: int = 0 |
|
return self |
|
def __next__(self): |
|
Parameters: |
|
– self: mandatory reference to this object |
|
Returns: |
|
”’ if self._iter_index < len(self): |
|
value = self.get(self._iter_index) self._iter_index += 1 |
|
return value else: |
|
# End of Iteration self._index = 0 |
|
raise StopIteration |
|
def get(self, i: int): |
|
Alternate to use of indexing syntax. |
|
Parameters: |
|
– self: mandatory reference to this object |
|
Returns: |
|
the value at index i. ”’ |
|
return self[i] |
|
def set(self, i: int, value) -> None: |
|
Alternate to use of indexing syntax. |
|
Parameters: |
|
– self: mandatory reference to this object – i: the index of the elemnent to be set |
|
– value: the value to be set |
|
Returns: none |
|
”’ self[i] = value |
Page 13 of 20
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
|
class ArrayList(MyList): |
|
iteration over this list. ”’ |
|
def __init__(self, size: int, value=None) -> None: |
|
“””Creates a list of the given size, optionally intializing elements to value. |
|
The list is static. It only has space for size elements. |
|
Parameters: |
|
– size: size of the list; space is reserved for these many elements. – value: the optional initial value of the created elements. |
|
Returns: |
|
none “”” |
|
self.arr_red = arr.array(‘i’, [value[0] for i in range(size)]) self.arr_green = arr.array(‘i’, [value[1] for i in range(size)]) |
|
self.arr_blue = arr.array(‘i’, [value[2] for i in range(size)]) |
|
def __len__(self) -> int: |
|
Ref: https://stackoverflow.com/q/7642434/1382487 |
|
Parameters: |
|
– self: mandatory reference to this object |
|
Returns: |
|
”’ return len(self.arr_blue) |
|
def __getitem__(self, i: int): |
|
”’Returns the value at index, i. Allows indexing syntax. |
|
Ref: https://stackoverflow.com/a/33882066/1382487 |
|
Parameters: |
|
– i: the index from which to retrieve the value. |
|
Returns: |
|
”’ # Ensure bounds. |
|
assert 0 <= i < len(self),\ |
|
return ((self.arr_red[i], self.arr_green[i], self.arr_blue[i])) |
|
def __setitem__(self, i: int, value) -> None: |
|
Ref: https://stackoverflow.com/a/33882066/1382487 |
|
Parameters: |
|
– self: mandatory reference to this object – i: the index of the elemnent to be set |
|
– value: the value to be set |
|
Returns: none |
Page 14 of 20
CS 201 Data Structures II
Homework 1: Lists
Spring 2023
|
”’ |
|
# Ensure bounds. assert 0 <= i < len(self),\ |
|
self.arr_red[i] = value[0]; self.arr_green[i] = value[1]; self.arr_blue[i] = value[2 ] |
197 198 199 200 201
Code Listing 2: List Type
Page 15 of 20
CS 201 Data Structures II
Homework 1: Lists
Spring 2023
C Image Operations
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
|
from src.myimage import MyImage |
|
def remove_channel(src: MyImage, red: bool = False, green: bool = False, |
|
blue: bool = False) -> MyImage: |
|
Suppresses the red channel if no channel is indicated. src is not modified. |
|
Args: |
|
– red: suppress the red channel if this is True. |
|
– blue: suppress the blue channel if this is True. |
|
Returns: |
|
“”” src_copy = MyImage(src.size) |
|
rows = src.size[1] cols = src.size[0] |
|
for row in range(rows): |
|
src_copy.set(row, col, src.get(row, col)) |
|
if red == False and green == False and blue == False: for row in range(rows): |
|
for col in range(cols): |
|
else: src_copy.set(row, col, tuple(temp)) |
|
for row in range(rows): |
|
temp = list(src_copy.get(row, col)) if red == True: temp[0] = 0 |
|
if green == True: temp[1] = 0 if blue == True: temp[2] = 0 |
|
src_copy.set(row, col, tuple(temp)) return src_copy |
|
def convert_to_matrix(lst, m, n): #converts a flattened representation into an mxn matrix |
|
mat = [] such that m and n are known |
|
for i in range(0, len(lst), n): mat.append(lst[i:i+n]) |
|
return mat[:m] |
|
def rotate_90(matrix): #Rotates a given m x n matrix 90 degress clockwise res = [] |
|
for i in range(len(matrix[0])): lst = [] |
|
for j in range(len(matrix)): lst.append(matrix[j][i]) |
|
# Reversing the matrix for 90 degree lst.reverse() |
|
res.append(lst) return res |
|
def rotations(src: MyImage) -> MyImage: |
|
“””Returns an image containing the 4 rotations of src. |
|
The new image has twice the dimensions of src. src is not modified. |
|
Args: |
Page 16 of 20
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
CS 201 Data Structures II
Homework 1: Lists
Spring 2023
|
Returns: |
|
rows = src.size[1] cols = src.size[0] |
|
src_copy = MyImage((cols * 2, rows * 2)) rot_90_lst = [] |
|
rot_180_lst = [] rot_270_lst = [] |
|
rot_360_lst = [] temp = [] |
|
for row in range(rows): |
|
for col in range(cols): temp.append(src.get(row, col)) |
|
rot_360_lst = convert_to_matrix(temp, rows, cols) #Og image # 90 degree clockwise rotation |
|
rot_90_lst = rotate_90(rot_360_lst) #Image – 180 |
|
rot_180_lst = rotate_90(rot_90_lst) #Image – 90 anticlockwise |
|
rot_270_lst = rotate_90(rot_180_lst) src_copy_lst = [] |
|
for i in range(rows * 2): if i < rows: |
|
for x in range(len(rot_270_lst[i])): src_copy_lst.append(rot_270_lst[i][x]) |
|
for x in range(len(rot_360_lst[i])): src_copy_lst.append(rot_360_lst[i][x]) |
|
else: |
|
src_copy_lst.append(rot_180_lst[i % rows][x]) for x in range(len(rot_90_lst[i % rows])): |
|
src_copy_lst.append(rot_90_lst[i % rows][x]) lst1 = convert_to_matrix(src_copy_lst , rows*2, cols*2) |
|
for row in range(rows*2): |
|
src_copy.set(row, col, lst1[row][col]) return src_copy |
|
def resize(src: MyImage) -> MyImage: |
|
“””Returns an image which has twice the dimensions of src. |
|
The new image has twice the dimensions of src. src is not modified. |
|
Args: |
|
Returns: |
|
an image twice the size of src. “”” |
|
rows = src.size[1] cols = src.size[0] |
|
src_copy = MyImage((cols * 2, rows * 2)) for row in range(rows): |
|
for col in range(cols): |
|
for row in range(cols*2): |
|
if row % 2 == 0: #All even rows – not black rows if col % 2 == 1: |
|
if col == (cols * 2) – 1: #The last column – edge case pix = src_copy.get(row, col – 1) |
|
src_copy.set(row, col, pix) else: |
Page 17 of 20
130 131 132
133 134 135 136 137 138 139 140 141 142 143
144 145 146 147 148 149 150 151 152 153 154 155
156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
174 175 176 177 178
179 180 181 182 183
CS 201 Data Structures II
Homework 1: Lists
Spring 2023
|
pix1 = src_copy.get(row, col-1) |
|
pix2 = src_copy.get(row, col+1) pix2[2]) // 2) |
|
src_copy.set(row, col, pix) else: pass |
|
if row % 2 == 1: #Black rows |
|
if row == (rows * 2) – 1: #Last row – edge case pix = src_copy.get(row – 1, col) |
|
src_copy.set(row, col, pix) else: |
|
pix1 = src_copy.get(row – 1, col) pix2 = src_copy.get(row + 1, col) |
|
pix = ((pix1[0] + pix2[0]) // 2, (pix1[1] + pix2[1]) // 2, (pix1[2] + pix2[2]) // 2) |
|
src_copy.set(row, col, pix) if col % 2 == 1: |
|
if col == (cols * 2) – 1: |
|
src_copy.set(row, col, pix) else: |
|
if row != (rows * 2) – 1: |
|
pix2 = src_copy.get((row – 1), (col + 1)) pix3 = src_copy.get((row + 1), (col + 1)) |
|
pix4 = src_copy.get((row + 1), (col – 1)) |
|
pix2[1] + pix3[1] + pix4[1]) // 4, ( |
|
pix1[2] + pix2[2] + pix3[2] + pix4[2 |
|
src_copy.set(row, col, pix) ]) // 4) |
|
for row in range(rows * 2): |
|
for col in range(cols * 2): |
|
if col == (cols * 2) – 1: #Edge case – last col pix = src_copy.get(row, col – 1) |
|
src_copy.set(row, col, pix) |
|
pix = src_copy.get(row – 1, col) src_copy.set(row, col, pix) |
|
else: |
|
pix1 = src_copy.get((row – 1), (col – 1)) pix2 = src_copy.get((row – 1), (col + 1)) |
|
pix3 = src_copy.get((row + 1), (col + 1)) pix4 = src_copy.get((row + 1), (col – 1)) |
|
pix = ((pix1[0] + pix2[0] + pix3[0] + pix4[0])//4, (pix1[1] + pix2[1 ] + pix3[1] + pix4[1]) |
|
// 4, (pix1[2] + pix2 [2] + pix3[2] + pix4[2 |
|
src_copy.set(row, col, pix) ]) // 4) |
|
else: |
|
pix2 = src_copy.get(row, col + 1) |
|
src_copy.set(row, col, pix) + pix2[2]) // 2) |
|
return src_copy |
|
def maskreader(maskfile): #Reads the maskfile and returns a list with values of maskfile ”’ |
Page 18 of 20
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
228 229
230 231 232 233 234 235 236
237 238 239
240 241 242 243 244 245
CS 201 Data Structures II
Homework 1: Lists
Spring 2023
|
Returns a tuple of mask list and length. |
|
This is a helper function that is used in apply_mask function to read the mask file and return a list of n by n. |
|
maskfile is a text file containing n by n mask. |
|
Args: |
|
Returns: |
|
Tuple of lst of n by n and length ”’ |
|
f = open(maskfile , ‘r’); lst = [] |
|
for i in f: lst.append(int(i)) |
|
mat_len = lst[0]; mask_lst = lst[1::] f.close() |
|
return (mask_lst , mat_len) |
|
def apply_mask(src: MyImage, maskfile: str, average: bool = True) -> MyImage: “””Returns an copy of src with the mask from maskfile applied to it. |
|
maskfile specifies a text file which contains an n by n mask. It has the |
|
following format: |
|
– the next n^2 lines contain 1 element each of the flattened mask |
|
Args: |
|
– maskfile: path to a file specifying the mask to be applied |
|
Returns: |
|
an image which the result of applying the specified mask to src. “”” |
|
rows = src.size[1]; cols = src.size[0] src_copy = MyImage(src.size) |
|
# for row in range(rows): |
|
# src_copy.set(row, col, src.get(row, col)) vals = maskreader(maskfile) |
|
mask_lst = vals[0]; n = vals[1] |
|
for i , pixels in enumerate(src): mask_lst[center]}”) |
|
row, col = divmod(i,cols) #gives row index with corresponding column index to iterate over |
|
# print(row, col) val = 0; total = 0 |
|
for x in range(n): |
|
mask_row = x – (n // 2) #Computing row mask mask_col = y – (n // 2) #Computing col mask |
|
if row + mask_row >= 0 and row + mask_row < rows and col + mask_col >= 0 and col + mask_col < cols: |
|
total += mask_lst[n * x + y] |
|
# print(f”Row {row} Col {col} RowMask {mask_row} ColMask {mask_col} pixel {pix}”) |
|
val += ((pix[0] + pix[1] + pix[2])) // 3 * mask_lst[n * x + y] if average == True: val = val // total |
|
if val > 255: val = 255 if val < 0: val = 0 |
|
src_copy.set(row, col, (val,val,val)) return src_copy |
