COMPSCI 210 S1 – C Programming Assignment
Due: 11:59 pm Tuesday 6 June 2023
Worth: 6 marks (6% of the final mark)
Late Submission 30% penalty
Introduction
1. 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.
2. 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 of 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 origin 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 centre-originated in most cases,
which means the centre 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
Computer
Science
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 centre 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 directions 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 matrices as follows.
Input Kernel Output
COMPSCI 210 S1 – C Programming Assignment
The output at (1, 1) for this example will be:
C Programming
In this assignment, you are asked to write a C program to implement the 2D
convolution. In this program, 1024x1024 data and 5x5 filters 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 file based on the command line argument.
1. 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
COMPSCI 210 S1 – C Programming Assignment
2. Two data structures for the data and filter
You are asked to use two different data structures 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
3. Implementation details
In the implementation, you need to do saturation and scaling in addition to convolution.
You can follow the steps below.
1. 𝑦[𝑝, 𝑞] = ∑ ∑ 𝑥[𝑝 + 𝑖, 𝑞 + 𝑗] × ℎ[0 − 𝑖, 0 − 𝑗] 𝑗 𝑖
2. 𝑦′[𝑝, 𝑞] =
𝑦[𝑝,𝑞]
16
3. 𝑦"[𝑝, 𝑞] = {
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 same as the filter matrix. The 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.
4. 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.
5. Submission
You may electronically submit your assignment through the Web Dropbox
(https://adb.auckland.ac.nz/) at any time from the first submission date up until the final
date. You can make more than one submission. However, every submission that you
make replaces your previous submission. Submit ALL your files in every submission.
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 following files:
• convolution1.c
• convolution2.c
• report.pdf
COMPSCI 210 S1 – C Programming Assignment
6. Grading
• Report (3 marks)
o Clear description about the memory management on convolution1.c (1
mark)
o Clear description about the memory management on convolution2.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 100”
• Programme correctness (3 marks)
o 20 test cases will be tested. 12 of the results files will be available on
Canvas.
o ./convolution1 ./data1.txt ./filter1.txt temp111 1
o ./convolution1 ./data1.txt ./filter2.txt temp121 1
o ./convolution1 ./data1.txt ./filter3.txt temp131 1
o ./convolution1 ./data1.txt ./filter4.txt temp141 1
o ./convolution1 ./data1.txt ./filter5.txt temp151 1
o ./convolution2 ./data1.txt ./filter1.txt temp211 1
o ./convolution2 ./data1.txt ./filter2.txt temp221 1
o ./convolution2 ./data1.txt ./filter3.txt temp231 1
o ./convolution2 ./data1.txt ./filter4.txt temp241 1
o ./convolution2 ./data1.txt ./filter5.txt temp251 1
o ./convolution1 ./data1.txt ./filter1.txt temp112 2
o ./convolution1 ./data1.txt ./filter2.txt temp122 2
o ./convolution1 ./data1.txt ./filter3.txt temp132 2
o ./convolution1 ./data1.txt ./filter4.txt temp142 2
o ./convolution1 ./data1.txt ./filter5.txt temp152 2
o ./convolution2 ./data1.txt ./filter1.txt temp212 2
o ./convolution2 ./data1.txt ./filter2.txt temp222 2
o ./convolution2 ./data1.txt ./filter3.txt temp232 2
o ./convolution2 ./data1.txt ./filter4.txt temp242 2
o ./convolution2 ./data1.txt ./filter5.txt temp252 2
COMPSCI 210 S1 – C Programming Assignment
Appendix
Input Kernel Output
COMPSCI 210 S1 – C Programming Assignment
COMPSCI 210 S1 – C Programming Assignment