Brushfire Algorithm (30 points)
Implement a brushfire algorithm for a
Euclidean distance transform: given a binary input image, return a
floating array containing, for each pixel, the distance to the
closest non-zero pixel in the input image.
The algorithm should perform the same
computation as the Python implementation given here:
But instead of using global array
updates, maintain a queue of pixels that need to be accessed and
updated. Roughly, your code should look like:
queue = all boundary pixels
while queue is not empty:
take pixel from queue
propagate distances from pixel to
add neighboring pixels to queue if
their distances have been changed in the previous update
Morphological Identity (20 points)
Prove that if , then
Differences between Gaussian and Closing (50 points)
Write code to compute the difference between Gaussian convolution with thresholding and closing in mathematical morphology.
The inputs are an image A
and a radius r
for the structuring element.
write a function bin_gauss(A,sigma,n) that performs Gaussian smoothing
of binary images. This function takes as input a binary image, a
standard deviation , and a target pixel count n. It convolves the input image with a 2D Gaussian of the given , then finds a threshold that results in a binary image with the given number n of non-zero pixels.
- Next, compute the morphological closing of A with a circular structuring element of radius r using the morphology operations in scipy.ndimage.
- Then, for
in r*logspace(-1,1,100) (using the pylab logspace function), compute
the Gaussian smoothing of the binary image whose pixel count matches
that of the output of the morphological operation.
- Compute the number of pixel differences between the Gaussian smoothing and the morphological operation.
- Tabulate for r in range(1,20) which gives the closest result.
For the image A
, use the test image from the improc - Binary Images and Morphology