4) In this problem, you will investigate a more efficient way to implement spati

Question

4) In this problem, you will investigate a more efficient way to implement spatial filtering when all the filter coefficients have the same value. The motivation comes from the observation that as you slide the filter one pixel at a time over the image and compute the sum-of-products of image and filter values, you can use the results from the previous computation in the current computation Although the method can be generalized, we will consider the case in which all the filter coefficients have the value 1. And, we will also ignore the 1/n2 scaling factor that typically accompanies an averaging filter of size nxn. (a) Describe the algorithm you would use to compute the output value at location (x,y) given that you have already computed the result for location (x- 1.y), for example, for an averaging filter of size nxn (think about what changes when you shift the filter by one pixel) (b) How many additions (in terms of n) does this require for each output pixel. Count subtractions as additions. cNow, let's compare this with the standard approach of not using previous results. How many additions are required for each output pixel in this case. This should be in terms of n. d) Compute the computational advantage of the more efficient approach. This is simply the ratio of the number of additions required by the standard approach to the number of additions required by the more efficient approach. Again, this should be in terms of n.

Explanation / Answer

Lets assume image to be a matrix of size N*M where N and M both are greater then n.

And We are moving filter from left to right and calculating "sum of product" of image and filter value.

a) Algorithm of efficient method.

   // let output value at (x-1, y) coordinate is prev_sum;

    int new_sum ; // where new_sum will store output vlaue at (x, y) coordinate.

    int Image[N][M] ; // a matrix of int type, which represents an Image

    int Filter[n][n] ; // a matrix of int type, which represents filter.

// I am assuming the origin is at top-left (0,0) and our X-axis is increasing from top-left to top-right and Y-axis is increasing from top-left to bottom-left.

// We have to subtract the (x-n-1)th column "sum of product" of image and filter values.

    int sum_of_product_of_previous_col =0; // (x-n-1)th column "sum of product"

   // calculating sum of product of previous column ;

    for ( int i = y ; i >= ( y- n+1) ; i-- )

    {

          // here you need to understand the indexing of these matrices

         // We are iterating from bottom-left ( x-n-1, y) to top-left ( x-n-1, y-n+1) so these index are for image matrix and for filter matrix we have to move from bottom-left ( 1, n) { where n can be written as ( n - ( y - i ) ) when i=y } to top-left ( 1, 1 ) { y equals to 1, when i = y-n+1}

            sum_of_product_of_previous_col + = Image [ x - n -1][ i ] * Filter [1][ n - ( y - i )] ;

     }

// Now we will calculate "sum of product" of image and filter values for (x) th column.

    int sum_of_product_of_new_col =0;

   // calculating sum of product of new coloumn ;

// here we are moving from

    for ( int i = y ; i >= ( y- n+1 ) ; i-- )

    {

          // here you need to understand the indexing of these matrices

         // We are iterating from bottom-right ( x, y) to top-right ( x, y-n+1) so these index are for image matrix and for filter matrix we have to move from bottom-right ( n, n) { where n can be written as ( n - ( y - i ) ) when i=y } to top-right ( n, 1 ) { y equals to 1, when i = y-n+1 }

            sum_of_product_of_new_col + = Image [ x][ i ] * Filter [n][ n - ( y - i )] ;

     }

     new_sum = prev_sum - sum_of_product_of_previous_col + sum_of_product_of_new_col

   b)   Number of additions it will take can be calculated as follow .

   As you can see from above solution that we used plus n times for two times and one minus and one plus for final calculations

   total_number_of_plus = n + n + 2 = 2*n+2

   c) We the computation is done using standard approach then you will be using many more number of plus operator , let check it here.

          we know that our filter matrix is of size n*n, which means there are n2 cells in this matrix so we will be doing n2 cells of filter multiplication with n2 cells of image and result of these cells will be n2 terms and these all terms will be added . Therefore n2 plus operators will be used.

   Total_plus_operator = n2

d) Now we have to calculate "Computational Advantage" which is equal to the ratio of number of plus operators required by the standard approach and number of plus operators required by the efficient approach.

        Computational Advantage = n2/ (2*n+2)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.