Description
For this assignment you will manipulate 2D images and calculate and visualize the distance field from a shape
drawn in a black and white input image.
A distance field is scalar valued function defined for every point in
space (in our case, for every pixel in a simple 2D grid). The value of the distance field at a point in space
is simply the distance from that point to the closest point on the input shape. Distance fields 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 30×30 black and white image (left). The black pixels represent the
shape from which we want to calculate the distance field. All black pixels have distance field value=0.0.
The 4 pixels adjacent to any black pixel (that are not black themselves) have distance field 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 field. 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 files and the implementation of a naive (but very slow) algorithm for computing the distance field. For this assignment you will
analyze the performance of the naive algorithm, and implement a significantly 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.out squiggle_30x30.ppm out.ppm naive_method greyscale
Your first task is to analyze the code and determine the big ‘O’ 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
different size test cases using the naive algorithm and tabulate the running times. On UNIX/Linux/MacOSX
add the “time” function to the front of your command line:
time distancefield.out squiggle_30x30.ppm out.ppm naive_method grey_bands
When the program finishes, you’ll 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 file, 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 file.
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 big ‘O’ notation of the improved version (again in terms of w,
h, and p), and run the same experiments to confirm your predictions.
The Level Sets Fast Marching Method
But wait, there’s more! The problem of calculating the distance field can be completely reformulated. Instead
let’s track or march an advancing front from the input shape outwards. The method is illustrated in a series
of diagrams below for a simple 5×5 pixel input image.
4,0 4,2 4,1 4,3 4,4
0,0 0,1 0,2 0,3 0,4
1,0 1,2 1,3 1,4 1,1
2,0 2,1 2,2 2,3 2,4
3,0 3,1 3,4 3,2 3,3
0 0
0
4,0 4,2 4,1 4,3 4,4
0,0 0,1 0,2 0,3 0,4
1,0 1,2 1,3 1,4 1,1
2,0 2,1 2,2 2,3 2,4
3,0 3,1 3,4 3,2 3,3
0 0
1 1 0
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
1 1
1.4 1
2,4
2,2
0,0
0,2 1,2 3,4 1,4 0,1 2,0
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 first step, we collect all black pixels from the input image and initialize the distance field value for
these pixels to 0. The distance value for all other pixels is initialized to infinity (a very large number works
fine 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 final 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
first 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 pixel’s 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,0 3,1 3,4 3,2 3,3
0 0
1 1 0
1 1
1
1.4
1 1.4
1 1
2.4 1 1.4 2 1.4
1
1.4
1.4 1.4 1
1 1
1.4 1
2,4
2,2
0,0
0,2 1,2 3,4 1,4 0,1
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
1 1
1.4 1
2,4
2,2
0,0
0,2 1,2 3,4 1,4 0,1
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,1 4,3 4,4 4,2
0,0 0,1 0,2 0,3 0,4
1,0 1,2 1,3 1,4 1,1
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 won’t 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 don’t want to
do a linear scan of the data in the heap to find 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, we’ll also use a map that
associates each red pixel coordinate with its current index in the heap.
1.4
3,4
4,0 4,2 4,1 4,3 4,4
0,0 0,1 0,2 0,3 0,4
1,0 1,2 1,3 1,4 1,1
2,0 2,1 2,2 2,3 2,4
3,0 3,1 3,4 3,2 3,3
0 0
0
1.4
1.4
2 2.4
1.4 1.4
2.4 2 2.4
2 2
1 1 1
1 1
1
1
1 1
4,0 4,2 4,1 4,3 4,4
0,0 0,1 0,2 0,3 0,4
1,0 1,2 1,3 1,4 1,1
2,0 2,1 2,2 2,3 2,4
3,0 3,1 3,4 3,2 3,3
after fixing all pixels <= 1 priority queue after fixing all pixels <= 1 final distance field output image
0 0
1 1 1 0
1 1
1
1
1 2.4 1 1.4 2
1.4
1.4
2.4 2 2.4
2 1.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.4 2.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 fixed (black), propagated their distance data to their immediate
neighbors, and been removed from the priority queue.
The third diagram shows the final distance field values
after all pixels have been fixed 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 field. 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 field function. Your task is to complete the implementation, test your code to be
sure it approximately matches the naive algorithm, determine the big ‘O’ 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 field 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 files 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 tmp.ppm tmp.png or convert tmp.ppm tmp.png
Submission
Use the provided template README.txt file 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 file.
3
