Course Information‎ > ‎Übungen‎ > ‎

Exercise 6

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 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.