[Solved] SOLVED:Distance Fields & Priority Queues solution

For this assignment you will manipulate 2D images and calculate and visualize the distance eld from a shape drawn in a black and white input image. A distance eld is scalar valued function dened for every point in space (in our case, for every pixel in a simple 2D grid). The value of the distance eld at a point in space is simply the distance from that point to the closest point on the input shape. Distance elds are useful in many applications including collision detection in 3D simulations, shape modeling and registration/similarity detection, motion planning for robotics, and computer vision and image processing. In the example above we start with a 3030 black and white image (left). The black pixels represent the shape from which we want to calculate the distance eld. All black pixels have distance eld value=0.0. The 4 pixels adjacent to any black pixel (that are not black themselves) have distance eld value=1, the 4 diagonal neighbors have distance value=2, pixels 2 units in the horizontal or vertical direction have distance value=2.0, etc. In the middle image we see a visualization of this distance eld. Pixels with distance value=0 are colored red=<255,0,0. The remaining distance values are mapped to shades of grey such that smaller values are darker and the largest distance value is colored white=<255,255,255. The right image above shows an alternate visualization where the same distance values are mapped to a more colorful scale. We provide you with a simple Image class that loads and saves (uncompressed) .ppm les and the implementation of a naive (but very slow) algorithm for computing the distance eld. For this assignment you will analyze the performance of the naive algorithm, and implement a signicantly faster algorithm using a priority queue. Be sure to read the entire handout before beginning your implementation. Naive Distance Field Algorithm The naive algorithm consists of nested loops that compare every pixel to every other pixel and computes the distance between each pair of pixels. Each pixel remembers the shortest distance to a black pixel. The provided code implements this algorithm and can be run with the following command line: distancefield.exe squiggle_30x30.ppm out.ppm naive_method greyscale Your rst task is to analyze the code and determine the order notation of the algorithm in terms of w & h, the width and height of the input image, and p, the number of black pixels in the input image. Run a variety of dierent size test cases using the naive algorithm and tabulate the running times. On UNIX/Linux/MacOSX/Cygwin add the time function to the front of your command line: time distancefield.exe squiggle_30x30.ppm out.ppm naive_method grey_bands When the program nishes, youll be given an estimated breakdown of the running time of your program: real (the total time), user (just your program), and sys (time when your program is waiting for resources, e.g., writing to a le, or waiting for the CPU when other programs are running simultaneously). Once you have collected the data, analyze the results. Do they match your predicted order notation? Record your order notation, running time data, and discuss in your README.txt le. Improvement on the Naive Algorithm Rather than comparing every pixel to every other pixel, we can compare every pixel to every black pixel. The change in implementation is minor, but will likely have a rather large impact on the performance. Go ahead and make the change to the code, predict the order notation of the improved version (again in terms of w, h, and p), and run the same experiments to conrm your predictions. The Level Sets Fast Marching Method But wait, theres more! The problem of calculating the distance eld can be completely reformulated. Instead lets track or march an advancing front from the input shape outwards. The method is illustrated in a series of diagrams below for a simple 55 pixel input image. 4,0 4,1 4,2 4,3 4,4 0,0 0,1 0,2 0,3 0,4 1,01,11,21,31,4 2,0 2,1 2,2 2,3 2,4 3,1 3,3 3,4 3,03,2 0 0 0 4,0 4,1 4,2 4,3 4,4 0,0 0,1 0,2 0,3 0,4 1,01,11,21,31,4 2,0 2,1 2,2 2,3 2,4 3,1 3,3 3,4 3,03,2 0 0 011 1 1 1 1.4 1 1 1.4 1 1.4 1 1.4 1 2,1 1 1.4 1.4 1.4 1 11 1.41 2,4 2,2 0,0 0,12,03,41,40,21,2 1,3 3,3 3,2 1 1 1 input image initialization of the signed distance field propagating initial values initial priority queue of pixels In the rst step, we collect all black pixels from the input image and initialize the distance eld value for these pixels to 0. The distance value for all other pixels is initialized to innity (a very large number works ne too). Next, for each black pixel, b, we consider each of the 8 neighbor pixels, n. If the current distance value of n is greater than the distance value of b + the distance between b & n, we update the distance value of n to be the distance value of b + the distance between b & n. We call this propagating the distance data from one pixel to its neighbors. Note that the calculated distance is not necessarily the correct nal answer for the distance of the pixel n, but it is a conservative upper bound on that value. The collection of newly-updated pixels (labeled in red in the third diagram above) are placed into a priority queue, using the distance value as the priority value. Smaller distance values will percolate up to the top of the heap. The heap contains only the advancing front of estimated distance value pixels (marked red), not the known values (marked black) or the unknown values (marked blue). Now the real fun happens. To continue progressing this front of estimated values across the image, we will rst grab the top pixel from the priority queue, (2,1). Because no other pixel in the priority queue has smaller distance value, we can guarantee that its distance will not change when information is propagated from its red-marked neighbors. Therefore, we can set this pixels distance value as known (mark it black), remove it from the priority queue, and propagate its distance information to its neighbors, as shown below: 2,1 2,2 2,3 2,4 3,1 3,3 3,4 3,03,2 0 0 011 1 1 1 1.4 1 1.4 11 21.4 2.4 1 1.4 1 1.4 1.4 1.4 1 11 1.41 2,4 2,2 0,0 1,40,11,23,40,2 1,3 3,3 3,2 1 1 1 2,0 2 3,1 2.4 3,0 1 1.4 1.4 1.4 1 11 1.41 2,4 2,2 0,0 1,40,11,23,40,2 1,3 3,3 3,2 1 1 1 2,0 2,0 1 1 2,1 propagate fixed value to neighbors adjust existing values & add new values to the priority queue after popping & fixing the top value, 4,0 grab the last leaf & percolate down 4,14,24,34,4 0,0 0,1 0,2 0,3 0,4 1,01,11,21,31,4 2,0 2 So we need to propagate the data from pixel (2,1) to its 8 neighbors. Two of the neighbors have known (black) distance values and can be ignored since their values wont change with this new information. Two of the neighbors had previously unknown distance estimates (marked blue) and are switched to be red pixels and added to the queue (shown with red boxes). Finally, four of the neighbors already have estimated distance values and if their values change through the propagation of distance data (the estimated distance value may only decrease), their position in the heap may also need to be adjusted (by calling percolate up). To do so, we will need to quickly locate the position of that pixel within the heap. We certainly dont want to do a linear scan of the data in the heap to nd that pixel. One solution is to use a map. In the priority queue representation, in addition to having a vector that stores the heap elements, well also use a map that corresponds each red pixel coordinate to its current index in the heap. 1.4 3,4 4,0 4,1 4,2 4,3 4,4 0,0 0,1 0,2 0,3 0,4 1,01,11,21,31,4 2,0 2,1 2,2 2,3 2,4 3,1 3,3 3,4 3,03,2 0 0 0 1.4 1.4 2 2.4 1.4 1.4 22.42.4 22 111 1 1 1 1 11 4,0 4,1 4,2 4,3 4,4 0,0 0,1 0,2 0,3 0,4 1,01,11,21,31,4 2,0 2,1 2,2 2,3 2,4 3,1 3,3 3,4 3,03,2 after fixing all pixels <= 1priority queue after fixing all pixels <= 1 final distance fieldoutput image 0 0 10 1 1 1 1 1 1 112.4 1.42 1.4 1.4 22.42.4 21.4 3 2 2 2.8 0,3 3,0 2 1.4 0,2 1.4 3,2 2 3,1 4,4 2.4 0,4 1.42.4 1,4 2 4,3 2.4 4,2 The two leftmost images above show an intermediate state of the algorithm for this example: after all pixels with distance value <= 1 have been marked xed (black), propagated their distance data to their immediate neighbors, and been removed from the priority queue. The third diagram shows the nal distance eld values after all pixels have been xed and the queue is empty and the fourth image shows the output image, in which each distance value is translated into an appropriate color in the rainbow scale. Note: This advancing front method produces an approximation of the true distance eld. Because exact pairwise distances are only calculated for the 8 neighbors of a particular pixel, the calculated distance values of points far from the input shape may only be an upper bound of the true value. We have provided starter code for the implementation of the Fast Marching Method using a priority queue for calculating the distance eld function. Your task is to complete the implementation, test your code to be sure it approximately matches the naive algorithm, determine the order notation, and collect and analyze runtime data for a variety of input images. For extra credit you may implement alternate visualization strategies for the distance eld data (include sample images in your submission). Another option for extra credit is to use a hash table instead of a map to store the pixel to index correspondence within the priority queue. Collect and analyze data comparing the algorithm using a map to the algorithm using a hash table. Viewing .ppm Images The input and output les are stored in the simple uncompressed standard Portable Pixel Map format (with magic number P6), .ppm. Many standard image viewing programs (Photoshop, GIMP, and xv) will load and display these images. On UNIX/Linux/MacOSX/Cygwin, ImageMagick can be used to convert between image formats, such as the popular Portable Network Graphics format, .png. For example: convert.exe tmp.ppm tmp.png or convert tmp.ppm tmp.png Submission Use the provided template README.txt le for your algorithm analysis and any notes you want the grader to read. You must do this assignment on your own, as described in the Academic Integrity for Homework handout. If you did discuss the problem or error messages with anyone, please list their names in your README.txt le.