Course Information‎ > ‎Übungen‎ > ‎

### 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:

https://sage.cs.uni-kl.de:8000/home/pub/104/

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 neighboring pixels
add neighboring pixels to queue if their distances have been changed in the previous update

### Morphological Identity (20 points)

Prove that if $A \subseteq B$, then $A \bullet C \subseteq B \bullet C$

### 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.
• First, 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 $\sigma$, and a target pixel count n. It convolves the input image with a 2D Gaussian of the given $\sigma$, 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 $\sigma$ 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 $\sigma$ gives the closest result.
For the image A, use the test image from the improc - Binary Images and Morphology worksheet.