Finding Bright Stars with Region Growing

What does it mean for a piece of software to 'find' a star in an image?  The star is already there in the image isn't it?

No, there is no star in the image.  The image has nothing but pixels in it.  To find a star, a program must build a data structure that makes knowledge about the star's existence and location explicit.  There are no stars but what we make.
 

There is no star in this image.

To make knowledge about stars explicit in my program, I will use a region-growing algorithm.  We will start out with a vanilla region-growing algorithm.  Later, we will add something strange and wonderful.

Here is a quick sketch of how it works:

1. select a threshold.  We will make regions out of pixels whose values are greater than or equal to that threshold, and ignore all others.  Let's call pixels bright if they are >= threshold.
2. Find a pixel in the image that is bright.  Start a new region with it.
3. Look at all its neighbors.  If any are bright, add them to the region.
4. For all the ones you just added, look at all their neighbors.  Add to the region any that are bright.
5. Keep doing this, until you get to a point where you don't add any new pixels to the region.  Then stop.

Here's an illustration.



This is the image we will be using.  I've outlined all the pixels in red so you can see them.  All the bright pixels have been set to white, while all non-brights have been set to gray.

To find the first bright pixel, scan the image top to bottom, left to right, testing the value of every pixel until you find a bright one.

Start a new region, and add that pixel to it.

Actually, I will have several different groups of pixels in this region.  Let's call them current generation, region, and new generation.  I will color-code them.  Right now the pixel we just found is the only one in the new generation.

Now we can get started.
For all the pixels in the current generation, look at their 8 neighbors.  If any of those neighbors are bright, add them to the new generation.

After finishing checking the neighbors for all of the current generation, move all of the current generation to region.  Move all new generation pixels into current generation.  Then repeat the process.

I have numbered the generations here, so you can see how they get added to the region in layers.

Finally, you reach a point where, when you check all the current pixels, you find no new ones.  So you put the current generation into the region, and you're done.  There is nothing more to check.

Now we know explicitly where a star is.  We know how many pixels are in it, we know its centroid X and Y.  We can look at the original image, before thresholding, and know its average gray value.  We know all kinds of stuff.

That's how we find a bright star.