# 14007 The Girl I Like Forgot Her Glasses
## Brief
A single-precision-floating-point 3x3 kernel and an wxh grayscale image are given. You are tasked to output the convoluted image.
For detailed explanation, visit [this link](https://acm.cs.nthu.edu.tw/problem/14007/).

## Idea

Let's look at some particular placement of the kernel first. How can we find the value in the convoluted image when the kernel is on the top-left corner? We can use something like

float sum = 0;
for(int y = 0; y < 3; y++) {
    for(int x = 0; x < 3; x++) {
        sum += kernel[x][y] * input_image[x][y];
    }
}

Surely, this won't work when we move the kernel to the right. How to fix this? Well, let us consider the general case where the kernel is **not** on the top-left corner? Well, let's look at the figure below.
What we can see is that the indices within the kernel runs from 0 to 2, so we can get the number inside the kernel with `kernel[x][y]` every round. However, the position from which we want to get the value in the image changes every time the kernel moves, so we need the offset term added to x and y, something like `input_image[x + offset_x][y + offset_y]`.
Therefore, the algorithm for adding calculating the sum for a single placement of the kernel in general is:

float sum = 0;
for(int y = 0; y < 3; y++) {
    for(int x = 0; x < 3; x++) {
        sum += kernel[x][y] * input_image[x + offset_x][y + offset_y];
    }
}
output_image[offset_x][offset_y] = sum;

To calculate the sum for all placement possible, we can simply add two more for loops for `offset_x` and `offset_y`:

for(int offset_y = 0; offset_y < height - 2; offset_y++) {
    for(int offset_x = 0; offset_x < width - 2; offset_x++) {
        float sum = 0;
        for(int y = 0; y < 3; y++) {
            for(int x = 0; x < 3; x++) {
                sum += kernel[x][y] * input_image[x + offset_x][y + offset_y];
            }
        }
        output_image[offset_x][offset_y] = sum;
    }
}

This is the heart of our algorithm. You can try to implement the rest on your own before peeking at the solution.

## Solution
<details>
<summary>Only click here when you're done implementing the algorithm or you have given up.</summary>
So you are finally here, huh? This is the treasure you've been looking for:

#include <stdio.h>

int main() {
    int width, height;
    float kernel[3][3];

    //Scan in the size
    scanf("%d%d", &width, &height);

    //Initialize the image
    int input_image [width][height];
    int output_image [width-2][height-2];

    //Scan in the kernel
    for(int y = 0; y < 3; y++) {
        for(int x = 0; x < 3; x++) {
            scanf("%f", &kernel[x][y]);
        }
    }

    //Scan in the image
    for(int y = 0; y < height; y++) {
        for(int x = 0; x < width; x++) {
            scanf("%d", &input_image[x][y]);
        }
    }

    //Process the data
    for(int offset_y = 0; offset_y < height - 2; offset_y++) {
        for(int offset_x = 0; offset_x < width - 2; offset_x++) {
            float sum = 0;
            for(int y = 0; y < 3; y++) {
                for(int x = 0; x < 3; x++) {
                    sum += kernel[x][y] * input_image[x + offset_x][y + offset_y];
                }
            }
            output_image[offset_x][offset_y] = sum;
        }
    }

    //Output the data
    for(int y = 0; y < height - 2; y++) {
        for(int x = 0; x < width - 2; x++) {
            printf("%4d ", output_image[x][y]);
        }
        printf("\n");
    }
}

</details>

## More Challenges

- In my code, a big image would crash the program. How can you modify the code so that it would support bigger image? (Hint: Scope)
- In this problem, we ignore the cases where kernel is partially outside the image. However, there are more ways to handle this.
- Mirror: The pixels outside the image are the mirrored version of those inside.
- Extend: The outermost pixels are replicated outwards.
- Wrap: The pixels beyond one side is the replica of those on the other.
- Constant: The pixels beyond the borders are all set to a single color.
- Kernel Crop: Ignore the pixels outside and operate only on the pixels inside.

Can you implement these edge handling schema?