<jupyter_start><jupyter_text>In order to successfully complete this assignment you must follow all instructions in this notebook and upload your files with your answers on or before **11:59pm on Friday March 1st**.  Homework 4: Image ProcessingIn this assignment, you are going to modify and improve the processing speed of an edge detector for grayscale PNG images. Edge detection is an image processing technique to find boundaries of objects in images. Here are an example image and the detected edges:**Note:** this homework was motivated and adapted from: https://web.stanford.edu/class/cs315b/assignment1.html    The files necessary for this assignment are found in the following directory of the class git repository:    HW4_Edge_Detection&9989; **DO THIS:** Download the directory to your HPCC account and compile the software.  Note, this program uses the libpng library which is already installed on the HPCC.  Goals for this assignment:By the end of this assignment, you should be able to:* Debug and benchmark existing workflows.* Using OpenMP to run code in parallel.* Practice your technical communication skills though writing.   Code Description and Background There are lots of edge detection algorithms but in this assignment, you will work on an algorithm with the following three steps:1. Image Smoothing2. Gradient calculation (Sobel Filters)3. Edge ThresholdingThe following section describes each step in detail.  Step 1: Smoothing (Average vs Median Filtering)Before starting the actual edge detection, we smooth the image to reduce undesired edges detected due to noise. There are lots of ways to smooth an image. The code provided uses an Average Filter.  Average Filtering approaches uses a "sliding window algorithm".  The input and outputs of a "sliding window algorithm" is an image.  The value of each pixel in the output image is calculated using a "window" of data around the corresponding pixel in the input image.  For the **Average Filter**, all of the pixels in the window for are averaged and the value is stored in the output image at the same location as the center pixel. If you think about it, the sliding window is not fully defined at the edges.  For the Average Filter this is not a problem. The algorithm just takes the media or average of the valid points within the windows. Here is a snip-it from the code: ```C++//Average Filter for(int c=0;c<sz.width;c++)     for(int r=0;r<sz.height;r++)    {        double count = 0;        double tot = 0;        for(int cw=max(0,c-halfwindow); cw<min(sz.width,c+halfwindow+1); cw++)            for(int rw=max(0,r-halfwindow); rw<min(sz.height,r+halfwindow+1); rw++)            {                count++;                tot += (double) img[rw][cw];            }        output[r][c] = (int) (tot/count);    }```  Step 2: Gradient calculation (Sobel Filter)Assuming that each object consists of pixels that do not greatly vary in their brightness, the edges in an image are from the sudden changes of brightness in the pixels.  One way to measure how big the change is to calculate the gradient magnitude at each pixel. The gradient operator we are going to use in this assignment is Sobel operator. Sobel operator is based on the following two 3x3 filters, which calculate x and y component of the gradient, respectively:$$ G_x =\left[\begin{matrix}    -1   & 0 & 1  \\    -2   & 0 & 2  \\    -1   & 0 & 1  \end{matrix} \right] G_y = \left[\begin{matrix}    1   & 2 & 1  \\    0   & 0 & 0  \\    -1 & -2 & -1  \end{matrix} \right]$$Here is a code snip-it that creates the filters: ```c++//Sobel Filtersdouble xfilter[3][3];double yfilter[3][3];xfilter[0][0] = -1;xfilter[1][0] = -2;xfilter[2][0] = -1;xfilter[0][1] = 0;xfilter[1][1] = 0;xfilter[2][1] = 0;xfilter[0][2] = 1;xfilter[1][2] = 2;xfilter[2][2] = 1;for(int i=0;i<3;i++)     for(int j=0;j<3;j++)        yfilter[j][i] = xfilter[i][j];``` Once x and y components of the gradient is computed, the magnitude can be computed by: $$IMG_{Gradient} = \sqrt{G_x^2 + G_y^2}$$ ```C++// Gradient Filterfor(int c=1;c<sz.width-1;c++)    for(int r=1;r<sz.height-1;r++)        {                double Gx = 0;                double Gy = 0;                for(int cw=0; cw<3; cw++)                    for(int rw=0; rw<3; rw++)                        {                                Gx +=  ((double) output[r+rw-1][c+cw-1])*xfilter[rw][cw];                                Gy +=  ((double) output[r+rw-1][c+cw-1])*yfilter[rw][cw];                        }                g_img[r][c] = sqrt(Gx*Gx+Gy*Gy);        }```  Step 3: Edge ThresholdingThe last step in the code provided is edge thresholding.  In this case, edges are defined based on the gradient image ($IMG_{Gradient}$).  Values over the threshold are considered edges and vales under the threshold are not edges.$$IMG_{Edge} = IMG_{Gradient} > thresh$$The threshold (```thresh```) may be varied to get different results.  For the images provided set the threshold to be 50.  ```C++// Thresholdingfor(int c=0;c<sz.width;c++)    for(int r=0;r<sz.height;r++)    if (g_img[r][c] > thresh)        output[r][c] = 255;    else        output[r][c] = 0;```  HW4 AssignmentFor this assignment you will do the following parts:1. Establish Serial Benchmark2. Optimize the Serial Code3. Modify the code to use OpenMP loops4. Final Report5. Deliverables  Part 1: Establish Serial Benchmark&9989; **DO THIS:** Benchmark the code provided using the image files provided in the images directory.  This file should provide a solid baseline.  Make sure your results account for hardware and system variation on the dev-intel18 node.   Part 2: Optimize the Serial CodeThe code provided does not optimized very well.  There are lots of things that could be done to speed up the existing code. For this homework I would like you try and benchmark two optimizations:1. Use different levels of compiler optimization 1. Change the order of the loops (row and column) for the Average Filter, Gradient Filter and Edge Thresholding. See if the change in order will increase speed due to multiple cache hits. &9989; **DO THIS:** Make the updates to the serial code as described above.  Benchmark and compare the time differences between the original version, the modified versions.  Pick the changes that provide for the fastest code.  Make all comparisons on the dev-intel18 node.Make sure you also save a version of your best serial code to turn in.   Part 3: Modify the code to use OpenMP loops&9989; **DO THIS:** Rewrite the code to use OpenMP loops to run the Average Filter, Gradient Filter and Edge Thresholding in parallel.  Make sure you carefully note the types of changes you make and use proper synchronization.  Benchmark your changes with different OMP Loop Scheduling options and compare to the serial benchmarks.  OMP Loop Scheduling OptionsWatch the following video which talks about ways to play around with schedulign options:* &9989; **DO THIS:** Scheduling [Introduction to OpenMP: 10 Discussion 4](https://www.youtube.com/watch?v=8jzHiYo49G0)  >**schedule(static [,chunk])** Deal-out blocks of interations of size "chunk" to each thread> >**schedule(dynamic[,chunk])** Each thread grabs "chunk" Iterations off a queue until all iterations have been handeled.> >**schedule(guided[,chunk])** Threads dynamically grab blocks of iterations. The size of the block starts large and shrinks down to size "chnunk" as the calculation proceeds.> >**schedule(runtime)** Schedule and chunk size taken from OMP_SCHEDULE enviornment variable (or the runtime library).> >**schedule(auto)** Schedule is left up to the runtime to choose (does not have to be any of the above).<jupyter_code># Code for loading png images in python
# feel free to load two different version of an edge file, subtract them and compare the difference
# This can be very good when you try to debug. 
%matplotlib inline
import matplotlib.pylab as plt
import imageio

filename = 'sparty.png'

im = imageio.imread(filename)
    
#Show the image
plt.imshow(im, cmap='gray');
plt.axis('off');<jupyter_output><empty_output><jupyter_text>Part 4: Final Report&9989; **DO THIS:** Write a report describing what you learned.  This report should be in the form of a narrative (story).  Start by describing how the provided serial code performed and what you did to accurately measure that performance. Then talk about what you did to optimize the serial performance. Finally, describe what you did to add in OpenMP and how the different scheduling options changed the speed of the algorithm.  Make sure you include well labeled graphs of all of your benchmarking data and explain the graphs in your report text with a focus on any odd results you may see.  Conclude with a general lessons learned.This is an image algorithm. You should include example images.   Grayscale PNG imagesThe code provided is desinged to work only with grayscale ```*.png```  images. Most PNG images are color and many images are in different formats (ex. TIFF, jpeg).  Fortunatly there is an easy to use command called ```convert``` which comes with the [ImageMagick](https://www.imagemagick.org/) Library. Feel free to download and install the software for your own use or use the software already installed on the HPCC.  The following examples can be used on the HPCC to load ImageMagick into your PATH, download an image from the internet and convert the image to a grayscale ```PNG``` file:```bashmodule load ImageMagickwget https://c1.staticflickr.com/7/6118/6369769483_882a704a38_b.jpgconvert -colorspace Gray 6369769483_882a704a38_b.jpg MSUStadium.png```  Part 5: Deliverables&9989; **DO THIS:** Prepare your files for the instructor.  I recommend having three versions of the code; original serial version, optimized serial version, optimized OMP version.  Update the provided ```Makefile``` to build all three executables. The files should include.When you are done, zip up your entire solution directory into a tgz file using the ```tar``` command with compression.  Watch the following videos for some hints to help streamline your code and benchmarking process:- &9989; &9989; **DO THIS:** Environment Variables in OpenMP [Introduction to OpenMP: 11 part 4 Module 6](https://www.youtube.com/watch?v=WXqicIq68-s)<jupyter_code>from IPython.display import YouTubeVideo
YouTubeVideo("3ELsNs4ERY8",width=640,height=360)<jupyter_output><empty_output><jupyter_text>Part 6: Optional Bonus&9989; **DO THIS:** Create an updated version of the Edge detector which includes some improvement. For example:1. Use a median or Gaussian filter instead of the average filter.2. Use Non-maximum suppression instead of thresholding.Learn more about the above options [here](https://web.stanford.edu/class/cs315b/assignment1.html) or pick be creative and try to make something else. Make sure the updated code also runs using OpenMP and include it in your Makefile with deliverables.  Include the improved edge detection examples in your report. Here is a short video about Median Filters.<jupyter_code>from IPython.display import YouTubeVideo
YouTubeVideo("3ELsNs4ERY8",width=640,height=360)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08283118985520281, 'fraction_numerical': 0.02167461102617142, 'mean_word_length': 4.122063565177338, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 24, 'https://': 6, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '478101', 'license': 'MIT', 'n_tokens_mistral': 3155, 'n_tokens_neox': 2949, 'n_words': 1484, 'path': '0301-HW4-Image_processing.ipynb', 'repo_name': 'colbrydi/CMSE401_Examples', 'size': '11119'}