COMPSCI 210: Computer Organisation - C Programming Assignment: 2D Convolution
COMPSCI 210 S1 – C Programming Assignment
Due: 11:59 pm Tues day 6 June 2023 Worth: 6 marks (6 % of the final mark ) Late Submission 30% penalty Introduction
- Convolution Convolution is the most fundamental concept in signal processing and analysis. By using convolution, we can construct the output of the system for any arbitrary input signal, if we know the impulse response of the system.
- Convolution in 2D 2D convolution is just an extension of previous 1D convolution by convolving both horizontal and vertical directions in a 2-dimensional spatial domain. Convolution is frequently used for image processing, such as smoothing, sharpening, and edge detection o f images. The impulse (delta) function is also in 2D space . The impulse response in 2D is usually called "kernel" or "filter" in image processing. The second image is the 2D matrix representation of the impulse function. The shaded centre point is the orig in where m=n=0. Once again, a signal can be decomposed into a sum of scaled and shifted impulse (delta) functions;
Notice that the kernel (impulse response) in 2D is cent re-originated in most cases, which means the cent re point of a kernel is h[0, 0] . For example, if the kernel size is 5, then the array index of 5 elements will be -2, -1, 0, 1, and 2. The origin is located in the middle of the kernel.
COMPSCI 210 S1 – C Programming Assignment Examine an example to clarify how to convolve in 2D space. Let's say that the size of the impulse response (kernel) is 3x3, and its values are a, b, c, d,.. ., i. Notice the origin (0,0) is located in the cent re of the kernel. Let's pick the simplest sample and compute convolution, for instance, the output at (1, 1) will be :
It results in a sum of 9 elements of scaled and shifted impulse responses. The following image shows the graphical representation of 2D convolution.
Notice that the kernel matrix is flipped in both horizontal and vertical direction s before multiplying the overlapped input data because x[0,0] is multiplied by the last sample of the impulse response, h[1,1]. And x[2,2] is multiplied by the first sample, h[ -1,-1]. Exercise a little more about 2D convolution with another example. Suppose we have 3x3 input and 3x3 kernel matri ces as follow s.
Input Kernel Output
COMPSCI 210 S1 – C Programming Assignment The ou tput at (1, 1) for this example will be :
C Programming In this assignment, you are ask ed to write a C program to implement the 2D convolution. In this program, 1024x1024 data and 5x5 filter s are read from the files based on the command line argument. After the completion of the calculation, the results matrix (1024x1024) is written into a fil e based on the command line argument.
-
Command line arguments The command line arguments should include the following items in the correct sequence: Executable (convolution1 or convolution2) “data file” “filter file” “output file” “number of convolutions ” Example: ./convolution2 . /data1.txt . /filter1.txt temp2 12 • “./convolution2” is the executable file. • “./data1.txt” is the data file for the data matrix. • “./filter1.txt” is the filter file for the filter matrix. • “temp2” is the output file for the output matrix. • “12” is the number of convolutions. Timing the execution time of the programme : Example : time ./convolution2 . /data1.txt . /filter1.txt temp2 12
-
Two data structure s for the data and filter You are asked to use two different data structu res to implement the convolution. For the first one (named as convolution1.c) , you should use “struct” to store the data (o_val) and the output (n_val) matrices such as below:
In the second one (named as convolution2.c) , you can use two separate arrays to store the data (data[]) and the output (rlt []) matrices.
struct matrix { int o_val; int n_val; }; typedef struct matrix Matrix;
int main(int argc, char argv[]) { FILE file1, file2, file3; int i = 0; int filter[5][5]; Matrix** data; int j, k, l, m; int val; int iter;
data = (Matrix**) malloc(sizeof(Matrix*)*1024);
for (i = 0; i < 1024; i++) {
data[i] = (Matrix*) malloc(sizeof(Matrix)*1024);
}
file1 = fopen(argv[1], "r");
file2 = fopen(argv[2], "r");
file3 = fopen(argv[3], "w");
iter = atoi(argv[4]);int main(int argc, char argv[]) { FILE file1, file2, file3; int i = 0; int filter[5][5]; int data; int rlt; int j, k, l, m; int val; int iter;
data = (int**) malloc(sizeof(int*)*1024);
rlt = (int**) malloc(sizeof(int*)*1024);
for (i = 0; i < 1024; i++) {
data[i] = (int*) malloc(sizeof(int)*1024);
rlt[i] = (int*) malloc(sizeof(int)*1024);
}
file1 = fopen(argv[1], "r");
file2 = fopen(argv[2], "r");
file3 = fopen(argv[3], "w");
iter = atoi(argv[4]);COMPSCI 210 S1 – C Programming Assignment
-
Implementation details In the implementation, you need to do saturation and scaling in addition to convolution. You can follow the steps below.
-
𝑦[𝑝,𝑞]=∑∑𝑥[𝑝+𝑖,𝑞+𝑗]×ℎ[0−𝑖,0−𝑗]𝑖 𝑗
-
𝑦′[𝑝,𝑞]=𝑦[𝑝,𝑞] 16
-
𝑦"[𝑝,𝑞]={16,𝑖𝑓 𝑦′[𝑝,𝑞]>16 𝑦′[𝑝,𝑞],𝑖𝑓−16≤𝑦′[𝑝,𝑞]≤16 −16,𝑖𝑓 𝑦′[𝑝,𝑞]<−16 In the first step, you can do the convolution between the data matrix (x[p, q]) and the filter matrix (h[i,j]). The results of each convolution should be stored in the output matrix (y[p, q]). This is used as the data matrix in the next convolution. Notice that the size of the data matrix is not the s ame as the filter matrix. T he array index (i and j) of 5 elements in the above equations will be -2, -1, 0, 1, and 2 . You can see an example in the appendix for the details of convolution. In the second step, the values are required to scale down to avoid the values becoming too large or too small. In the final step, the values are saturated to keep the range of values between -16 and 16.
-
Report Writing Write a report (maximum 2 pages) to explain the performance using those two different data structures . You can consider cache -conscious programmes such as merging array and loop interchange to explain how your programmes have influenced the cache operations respectively.
-
Submission You can make more than one submission. However, every submission that you make replaces your previous submission. Submit ALL your files in every submi ssion. Only your very latest submission will be marked. Please double -check that you have included all the files required to run your program. No marks will be awarded if your program does not compile and run. You are to electronically submit all the follo wing files: • convolution1.c • convolution2.c • report.pdf
-
Grading • Report (3 marks) o Clear d escription about the memory management on convolution1.c (1 mark) o Clear d escription about the memory management on convolution 2.c (1 mark) o Clear analysis about the memory management between convolution1.c and convolution2.c (1 mark) o You are suggested to use more convolutions to show the time difference. Example: “ time ./convolution2 ./data1.txt ./filter1.txt temp 1 00” • Programme correctness (3 marks) o 20 test cases will be tested. 1 2 of the results files will be available on Canvas. o ./convolution 1 ./data1.txt ./filter1.txt temp 111 1 o ./convolution 1 ./data1.txt ./filter 2.txt temp 121 1 o ./convolution 1 ./data1.txt ./filter 3.txt temp 131 1 o ./convolution 1 ./data1. txt ./filter 4.txt temp 141 1 o ./convolution 1 ./data1.txt ./filter 5.txt temp 151 1 o ./convolution 2 ./data1.txt ./filter1.txt temp 211 1 o ./convolution 2 ./data1.txt ./filter 2.txt temp 221 1 o ./convolution 2 ./data1.txt ./filter 3.txt temp 231 1 o ./convolution 2 ./data1.txt ./filter 4.txt temp 241 1 o ./convolution 2 ./data1.txt ./filter 5.txt temp 251 1 o ./convolution 1 ./data1.txt ./filter1.txt temp 112 2 o ./convolution 1 ./data1.txt ./filter 2.txt temp 122 2 o ./convolution 1 ./data1.txt ./filter 3.txt temp 132 2 o ./convolution 1 ./data1.txt ./filter 4.txt temp 142 2 o ./convolution 1 ./data1.txt ./filter 5.txt temp 152 2 o ./convolution 2 ./data1.txt ./filter1.txt temp 212 2 o ./convolution 2 ./data1.txt ./filter 2.txt temp 222 2 o ./convolution 2 ./data1.txt ./filter 3.txt temp 232 2 o ./convolution 2 ./data1.txt ./filter 4.txt temp 242 2 o ./convolution 2 ./data1.txt ./filter 5.txt temp 252 2
