More Imaging: Filters and Flood Fill¶

11/15/2022¶

print view

Woof¶

Single Pixel Modification¶

As a reminder, we can use the point method to apply an arbitrary function to each pixel.

Filters¶

A filter applies a convolution kernel to an image.

Although this sounds fancy, this is just a generalization of the point method where the function takes as input the neighborhood of the pixels.

The kernel is represented by an $n$x$n$ matrix where the target pixel is in the center.

The output of the filter is the sum of the products of the matrix elements with the corresponding pixels.

Examples, from Wikipedia):


Identity	Blur	Edge Detection

Filters¶

The PIL ImageFilter module includes a number of built-in convolution kernels that can be applied using the image filter method.

((3, 3), 13, 0, (1, 1, 1, 1, 5, 1, 1, 1, 1))

[[1 1 1]
 [1 5 1]
 [1 1 1]] 13

The output is the sum of the product of the coefficients and the corresponding pixels divided by the denominator and incremented by the offset.

BLUR¶

[[1 1 1 1 1]
 [1 0 0 0 1]
 [1 0 0 0 1]
 [1 0 0 0 1]
 [1 1 1 1 1]] 16

SMOOTH¶

[[1 1 1]
 [1 5 1]
 [1 1 1]] 13

FIND_EDGES¶

[[-1 -1 -1]
 [-1  8 -1]
 [-1 -1 -1]] 1

SHARPEN¶

[[-2 -2 -2]
 [-2 32 -2]
 [-2 -2 -2]] 16

Non-linear Filters¶

There are also non-linear filters that don't compute sums of products. Instead, they compare the values of the neighboring pixels (e.g., max value, min value, median value).

Recursion - It's as easy as 1,1,2,3¶

Recursion is when a function calls itself on a small version of the problem to compute the answer.

It is a very useful way to think about complex, but decomposable, problems.

A recursive function must have a base case, an input that is eventually reached that does not require any further calls to the function ($n \le 1$ above).

What happens if you forget the base case?

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-16-aba404ac2c91> in <module>
      2     return brokenfib(n-1)+brokenfib(n-2)
      3 
----> 4 brokenfib(5)

<ipython-input-16-aba404ac2c91> in brokenfib(n)
      1 def brokenfib(n):
----> 2     return brokenfib(n-1)+brokenfib(n-2)
      3 
      4 brokenfib(5)

... last 1 frames repeated, from the frame below ...

<ipython-input-16-aba404ac2c91> in brokenfib(n)
      1 def brokenfib(n):
----> 2     return brokenfib(n-1)+brokenfib(n-2)
      3 
      4 brokenfib(5)

RecursionError: maximum recursion depth exceeded

The Call Stack¶

Every time you call a function, the function and its arguments are placed on the call stack.

The call stack will eventually run out of memory.

Python limits how many calls can be on the call stack.

Recursive Functions¶

Must have base case - can provide the answer without further recursive calls (if n <= 1: return 1)
Must make progress towards base case (n-1, n-2)
Must make recursive call(s) (fib(n-1), fib(n-2))
Must compute current (n) answer using recursive calls (fib(n-1)+fib(n-2))
Must return answer

accumulator: 5, n: 5
accumulator: 20, n: 4
accumulator: 60, n: 3
accumulator: 120, n: 2
accumulator: 120, n: 1
factorial 5 = 120

accumulator: 1, n: 5
accumulator: 5, n: 4
accumulator: 20, n: 3
accumulator: 60, n: 2
accumulator: 120, n: 1
factorial 5 = 120

Flood Fill - Implementing the Paint Bucket¶

Click on a pixel, fill that pixel and all touching pixels of the same color with the fill color.

Flood-fill (pixel, target-color, replacement-color)

What is/are the recursive step(s)?

What is the base case?

The Algorithm (from Wikipedia)¶

Flood-fill (pixel, target-color, replacement-color):

If target-color is equal to replacement-color, return.
If the color of pixel is not equal to target-color, return.
Set the color of pixel to replacement-color.
Perform Flood-fill (one step to the west of pixel, target-color, replacement-color).
Perform Flood-fill (one step to the east of pixel, target-color, replacement-color).
Perform Flood-fill (one step to the north of pixel, target-color, replacement-color).
Perform Flood-fill (one step to the south of pixel, target-color, replacement-color).
Return.

Counting Cells (or at least blobs of light)¶

The idea is to threshold the image and then count the number of white blobs.

Project¶

Implement a flood fill function.
- There's some details missing from the algorithm...
- You will need to load the pixel map with load
- You will need to pass the width and height of the image to avoid going off the edge
- You will likely need to increase the recursion limit
For every pixel in the image, if it is white (255) flood fill it with gray (128)
Count the number of times you do this
Display the final image
Display the average cell size. Its distribution.