Recursive Clustering#

Goal#

There are several ways to establish clusters in an image. None is perfect. In this project, you will try to implement an alternative algorithm, using recursivity.

Principle#

An image is a 2D array of pixels. We want to identify all regions of this image, made of contiguous pixels. These regions are associated with celestial objects we want to characterize. To identify the contiguous pixels, only the pixels with a luminosity value greater or equal to a threshold are considered. A pixel is considered contiguous if it has at least one side in common with another pixel above (or equal to) the threshold (which means that pixels only adjacent by their corners are not considered as contiguous)

To isolate and identify all these regions, we decompose the algorithm in two levels:

1. We start with a linear scan of the image grid, at the top-left corner of the image. The scan is done line by line: the first line is scanned, then the second one…

2. When an interesting pixel is found (a pixel whose value is greater or equal to the threshold), explore recursively all immediate contiguous neighbours until all the contiguous pixels have been found (this set of pixels is called a cluster).

Once a cluster has been completed, restart the linear scan until the whole image has been processed. It is very important to ensure that any pixel is visited only once.

_images/ClusterFinding-01.png

A presentation is available explaining in details how the Recursive Clustering is working.

Algorithm#

One way to implement an algorithm as described in the previous section is to exploit the recursion (or recursivity). This requires two functions.

Main function :

  1. Mark all the pixels as “not done”.

  2. Start from the top left corner of the image.

3. While the current pixel is “done” or below the threshold, move to the next pixel.

  1. Create an object of type PixelsSet and call the recursive function below.

  2. If the pixels set has more than one pixel, create and store the corresponding object of type Cluster.

  3. Go to 3. until all the image has been scanned.

Recursive function :

  1. If pixel is done or below the threshold, return.

  2. Add the current pixel to the current pixels set, and mark the pixel as done.

  3. For any immediate contiguous neighbour pixel (right, top, left, bottom) which is not outside the image, call the recursive function for this pixel.

Note

It may happen that when you execute your code you get an error message maximum recursion depth exceeded. This is generally the sign of a bug in your program or an incorrect threshold but to help diagnosing the problem, you may temporarily increase the limit by adding the following line into your program:

sys.setrecursionlimit(5000)
_images/ClusterFinding-02.png

Implementation Details#

The main program for this project must be in a file called pjb_recursive_clustering.py, which you can initially create as a clone of ex5_stars.py. The program must do the same steps as the exercise 5, except using an alternative clustering algorithm. The clusters made by the new algorithm may be slightly differents than the original ones.

So to help you, we provide the file npac/pixels.py, which define the class PixelsSet. You can create such an object and add progressively all the pixels which pertain to the same cluster. The class knows how to compute the characteristics that you need when finally creating a cluster (get_peak(), get_top() and get_integral()). So to check that you have more than one pixel before creating a cluster, use get_len().

We suggest to use the usual threshold value:

background + (6.0 * dispersion)

Result#

For your common and specific input images, do you get the same bigger cluster as before, in exercise 4 ? Do you finally identify the same celestial objects, as in exercise 5 ?

Warning

Do not apply your program to the so-called global image (too long).