CODEWITHSUNDEEP
cimageoptimization
JOKKINATOR
JOKKINATOR

Reputation: 410

Fast image smoothing in C

Problem: Given a square matrix, A, whose dimension, N, is a divisor of 64, find a fast way to smoothe A by letting a 3 x 3 grid slide over the A, s.t. for each entry A_{ij}, we replace this with the average of the 8 nearby neighbors.

My solution: Let's assume A is a 4x4 matrix, we initialize as:

int A[NxN] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

Which is equivalent to:

In the first iteration, we see A_ij is equivalent to 0, which is in the center of the 3x3 matrix. We realize that indices (0,0), (0,1), (0,2), (1,0), (1,3) of the 3x3 matrix is trying to find numbers not existing. Therefore, we see that the result must be that if $A_{ij}$ = 0, then we must replace it by $0+1+4+5 = \frac{10}{4}$.

Next iteration, we see A_ij is equivalent to 1, which is now the new center of the 3x3 matrix, and we see that the numbers to be included in the averaging is: 0,1,2,4,5,6.

So when we are in a corner of our matrix, A, we need 4 numbers for averaging, in the top of the matrix, we need 6 numbers, and if A_{ij} = 6, meaning in the middle of the matrix, we will need 9 numbers.

What I am trying to find is a general pattern for these sequences of needed numbers in order to do this in hopefully a single \texttt{for loop}.

I found that when i % dim == 0, we are in the left side of the matrix, when i % dim == 3 we are in the left side, but I have tried to find a general index pattern to define my averaging functions to pair with my if conditions.

#include <stdio.h> 

int smooth(int dim);

int main() {

    smooth(4);
}


int smooth(int dim) {
    int A[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    int K[dim*dim]; // Replacement array, otherwise we average averages
    

    for (int i = 0; i < dim; i++) {
        for (int j = 0; j < dim; j++) 
        {
            // Corner cases
            if ((i % dim == 0 && j % dim == 0) || (i % dim == dim - 1 && j % dim == 0) || (i % dim == 0 && j % dim == dim -1) || (i % dim == dim -1 && j % dim == dim-1))
            { 
                // Average function on corners
            }

            // else if not corner and in "edge row", top/bottom {
                  // Average 6 numbers  

            }

        

        }

    }
    return 0;
}

Upvotes: 1

Views: 294

Answers (1)

Yunnosch
Yunnosch

Reputation: 26763

Your mre is a bit theoretical, I will leave all parts which are not practically plausible out of this. They obviously only serve to provide a MRE quick.

Interpret your input as 2D.

 0  1  2  3
 4  5  6  7
 8  9 10 11
12 13 14 15

More abstractly as

 0              ...  (      0*dim + (dim-1))
(1       * dim) ...  (      1*dim + (dim-1))
(2       * dim) ...  (      2*dim + (dim-1))
                 .
                 .
                 .
((dim-1) * dim) ...  ((dim-1)*dim + (dim-1))

Here is the structure I propose for your function

int smooth(int dim)
{
    int A[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; //obvious MRE weirdness, ignored
    int K[dim*dim]; // Replacement array, otherwise we average averages
    
    // Corner cases
    K[0]            = A[0];           /* dummy, to be calculated */
    K[dim-1]        = A[dim-1];       /* dummy, to be calculated */
    K[dim*(dim-1)]  = A[dim*(dim-1)]; /* dummy, to be calculated */
    K[dim*dim-1]    = A[dim*dim-1];   /* dummy, to be calculated */

    for (int i = 0; i < dim-2; i++)
    {
        // edge cases
        {
            K[1+i]             = A[1+i];             /* dummy, average to be calculated */
            K[dim*(1+i)]       = A[dim*(1+i)];       /* dummy, average to be calculated */
            K[dim*(1+i)+dim-1] = A[dim*(1+i)+dim-1]; /* dummy, average to be calculated */
            K[dim*(dim-1)+i+1] = A[dim*(dim-1)+i+1]; /* dummy, average to be calculated */ 
        }

        // center part
        for (int j = 0; j < dim-2; j++) 
        {
            K[(i+1)*dim+1+j] = A[(i+1)*dim+1+j]; /* dummy, average to be calculated */
        }
    }
    return 0;
}

For all cases of A[...]; /* dummy, average to be calculated */ you can use the same index for reading from A as for writing into K and

  • subtract 1 to get to the pixel to the left
  • add one to get to the pixel to the right
  • add dim to get to the pixel below
  • subtract dim to get to the pixel above
  • do that for all neigbouring pixels you decide to use
  • sum the values up to determine the average

In all cases where you need a neighbour pixel you will always arrive at a valid pixel, because either there is one or you are not going to need it.

(Note: I strictly practice starting for loops from 0 and count up with <needed_length. There is an alternative to start from 1 and count up to needed length +1. It will in this case here make the index calculations read easier. This is a matter of habits. I come from an environment where you have to prepare strong reasoning for loops not starting at 0. Habits are hard to shed. Going through the alternative concept will probably provide you with some helpful learning opportunity.)

Upvotes: 1

Related Questions