Counting Stars
 |
Hello, and welcome to the second episode of the Software Carpentry lecture on multimedia programming. In this episode, we’ll look at how to count how many stars there are in a picture of the night sky. |
 |
As we saw in the previous episode, we can use the Python Imaging Library, or PIL, to convert a color image like this… |
 |
…into a monochrome image like this, where black represents bright pixels and white represents background. |
 |
Our question is, how many stars are there? Counting the number of black pixels would be easy, but we want to know how many joined-up blobs of black pixels we have. |
 |
A blob is just a set of pixels that are adjacent to one another. |
 |
We could use several rules to determine what “adjacent” means, but the simplest is 4-way connectivity: pixels are adjacent if they are directly above, below, left, or right from each other, not if they are touching diagonally. |
 |
We want to count each such blob once. |
 |
So we’ll scan the image left to right, top to bottom |
 |
Each time we find a new blob, we’ll increment our count. |
 |
But how do we tell whether the pixel we’re looking at is part of a new blob or not? |
 |
One way is to mark the pixels we’ve already seen by turning them red. |
 |
If the pixel we’re looking at touches one that has already been turned red, then it’s part of a blob we have already counted. We’ll turn it red to show that we have looked at it, but we won’t count it as a star, since it belongs to a star we’ve already counted. |
 |
A picture will make this clearer. We scan the image until we find a black pixel… |
 |
…and mark it as seen by turning it red. |
 |
Nothing above it or to its left is already red. It must be the first pixel in a new blob, so we increment our star counter. |
 |
And keep scanning. |
 |
This pixel does have a red predecessor (the one we just colored in), so it’s not the start of a new star. |
 |
Eventually, we have colored in all of this star, and we move on to the next. |
 |
But there’s a problem: the pixel shown here is definitely part of our second star, but neither of the pixels above it or to its left has already been colored in—the pixel that connects it to the rest of its star is to its right. |
 |
We can fix this by looking in more directions, as shown here: if there are any colored pixels in the row above this one, or to its right, it isn’t the start of a new star. |
 |
But our new rule still gives the wrong answer in cases like this one, where two stars touch on a diagonal corner. |
 |
We could try to patch our algorithm again by changing our rule and considering blobs that are connected on diagonals as part of a single star… |
 |
But this still gives the wrong answer in cases like this. In fact, any algorithm that only looks at the immediate neighbors of a pixel will give the wrong answer in some cases: we have to back up and reconsider our approach entirely. |
 |
Instead of trying to decide whether pixels are connected one by one, let’s use flood fill to color in all the pixels in a star when it is first encountered. |
 |
As before, we scan the image until we find a black pixel, then mark it red. |
 |
Instead of continuing our scan right away, we look at the newly-filled pixel’s four neighbors. |
 |
For each one that is currently black—i.e., that is part of this star, but hasn’t yet been colored in—we fill it in… |
 |
…then immediately look at its neighbors to find other pixels that need coloring in. |
 |
We keep doing this until the whole star is colored… |
 |
…and only then re-start our scan to find other blobs. |
 |
Here’s our main function. As before, it scans the image top to bottom and left to right using a nested loop. |
 |
When it finds a black pixel… |
 |
…it increments the count of the number of stars seen… |
 |
…then calls ‘fill’ to fill in all the pixels connected to that one. |
 |
The ‘fill’ function works by keeping a list of pixels that need to be looked at, but haven’t yet been filled in. Such a list is often called a job list or work queue. |
 |
It is simply a list of the (x,y) coordinates of pixels that are neighbors of ones we have already examined. |
 |
The ‘fill’ function keeps looping until there’s nothing left in this list. |
 |
On each pass through the loop, it takes the (x,y) coordinates of a pixel from the queue… |
 |
If that pixel is black, ‘fill’ colors it red and adds its neighbors to the queue. |
 |
Here’s what the function looks like. |
 |
It begins by putting the (x,y) coordinates of the first pixel into the queue. |
 |
While there are still pixels to process… |
 |
…it gets the (x,y) coordinates of the next pixel in the queue and removes that pair from the queue. |
 |
If the pixel is currently black, ‘fill’ turns it red to mark it as having been seen. |
 |
Then adds the pixel to its left to the work queue (unless this pixel is on the left border of the image). |
 |
‘fill’ then does the same for the pixel to the right, above, and below the current one. This ensures that everything next to this pixel will eventually be looked at. |
 |
Here’s the ‘fill’ algorithm in action. Our initial pixel is (1, 2). We turn it red… |
 |
…and put its four neighbors in the queue. |
 |
The next three loops aren’t very interesting, since the pixels left, above, and right of our starting point aren’t black. On the fourth pass, though, when our queue only contains one lonely pixel, we find that it is black, so we fill it in… |
 |
…and put its neighbors in the queue. |
 |
The next time around the loop, we will look at our starting point (1, 2) a second time. |
 |
This is wasteful, so as an exercise, rewrite ‘fill’ so that it never examines a pixel twice. There are at least two ways to do this; see if you can find and implement both. |
 |
Another way to write flood fill is to use a recursive algorithm. |
 |
This keeps the work to be done on the call stack, instead of maintaining an explicit work queue. |
 |
Here’s the recursive version of fill. |
 |
It starts by checking the pixel it has been asked to look at. If that pixel is not black, this ‘fill’ returns immediately: there is nothing for it to do. |
 |
If the pixel is black, ‘fill’ turns it red… |
 |
…and then calls ‘fill’ on its left-hand neighbor (if it has one). |
 |
It then goes on to call ‘fill’ for the right-hand, top, and bottom neighbors as well. |
 |
This has the same effect as using an explicit work queue; each call to ‘fill’ takes care of one pixel, then calls ‘fill’ again to take care of the neighbors. While novices find the work queue approach more intuitive, experienced programmers tend to prefer recursion, since it is usually simpler to reason about. We’ll have a closer look at recursive algorithms in future episodes. |
What a great video!
Although on the internet there is an abundance of materials on Python’s syntax and general usage, there are comparatively few like this video which offer insight into creative ways to solve problems, which for me is what computing is all about.
Thanks very much.
As an algorithmic point, using a Python list like this to implement a queue gives an O(n**2) performance for some large blobs because of the queue = queue[1:]. (BTW, x,y=queue.pop(0) would also work, and collections.deque().popleft() would be even better.) Since the algorithm works equally well with a queue or a stack, then using the list as a stack and doing a stack.pop() would give you the expected amortized O(1) performance and would map directly to the call stack version. On the other hand, pictures of stars are rarely more than a few pixels in size, so this isn’t a real concern for this problem.