marchingsquares: Marching squares

This module provides implementations based on marching squares algorithms.

The main implementation is done by MarchingSquaresMergeImpl. It was designed to speed up the computation of iso surface using Cython and OpenMP. It also provides features like support of mask, and cache of min/max per tiles which is very efficient to find many iso contours from image gradient.

Utilitary functions are provided as facade for simple use. find_contours() to find iso contours from an image and using the same main signature as find_contours from skimage, but supporting mask. And find_pixels() which returns a set of pixel coords containing the points of the iso contours.

silx.image.marchingsquares.find_pixels(image, level, mask=None)[source]

Find the pixels following the iso contours at the given level.

These pixels are localized by the bound of the segment generated by the iso contour algorithm.

The result is returned as a numpy array storing a list of coordinates y/x.

# Example using a mask
shape = 100, 100
image = numpy.random.random(shape)
mask = numpy.random.random(shape) < 0.01
pixels = silx.image.marchingsquares.find_pixels(image, 0.5, mask=mask)
Parameters:
  • image (numpy.ndarray) – Image to process
  • level (float) – Level of the requested iso contours.
  • mask (numpy.ndarray) – An optional mask (a non-zero value invalidate the pixels of the image)
Returns:

An array of coordinates in y/x
Return type:

numpy.ndarray
silx.image.marchingsquares.find_contours(image, level, mask=None)[source]

Find the iso contours at the given level.

The result is returned as a list of polygons.

# Example using a mask
shape = 100, 100
image = numpy.random.random(shape)
mask = numpy.random.random(shape) < 0.01
polygons = silx.image.marchingsquares.find_contours(image, 0.5, mask=mask)
Parameters:
  • image (numpy.ndarray) – Image to process
  • level (float) – Level of the requested iso contours.
  • mask (numpy.ndarray) – An optional mask (a non-zero value invalidate the pixels of the image)
Returns:

A list of array containing y-x coordinates of points
Return type:

List[numpy.ndarray]
class silx.image.marchingsquares.MarchingSquaresMergeImpl(image, mask=None, group_size=256, use_minmax_cache=False)

Marching squares implementation based on a merge of segements and polygons.

The main logic is based on the common marching squares algorithms. Segments of the iso-valued contours are identified using a pattern based on blocks of 2*2 pixels. The image is read sequencially and when a segment is identified it is inserted at a right place is a set of valid polygons. This process can grow up polygons on bounds, or merge polygons together.

The algorithm can take care of a mask. If a pixel is invalidated by a non-zero value of the mask at it’s location, the computation of the pattern cancelled and no segements are generated.

This implementation based on merge allow to use divide and conquer implementation in multi process using OpenMP.The image is subdivised into many tiles, each one is processed independantly. The result is finally reduced by consecutives polygon merges.

The OpenMP group size can also by used to skip part of the image using pre-computed informations. use_minmax_cache can enable the computation of minimum and maximum pixel levels available on each tile groups. It was designed to improve the efficiency of the extraction of many contour levels from the same gradient image.

Finally the implementation provides an implementation to reach polygons (find_contours()) or pixels (find_pixels()) from the iso-valued data.

# Example using a mask
shape = 100, 100
image = numpy.random.random(shape)
mask = numpy.random.random(shape) < 0.01
ms = MarchingSquaresMergeImpl(image, mask)
polygons = ms.find_contours(level=0.5)
for polygon in polygons:
    print(polygon)

# Example using multi requests
shape = 1000, 1000
image = numpy.random.random(shape)
ms = MarchingSquaresMergeImpl(image)
levels = numpy.arange(0, 1, 0.05)
for level in levels:
    polygons = ms.find_contours(level=level)

# Efficient cache using multi requests
shape = 1000, 1000
image = numpy.arange(shape[0] * shape[1]) / (shape[0] * shape[1])
image.shape = shape
ms = MarchingSquaresMergeImpl(image, use_minmax_cache=True)
levels = numpy.arange(0, 1, 0.05)
for level in levels:
    polygons = ms.find_contours(level=level)
Parameters:
  • image (numpy.ndarray) – Image to process. If the image is not a continuous array of native float 32bits, the data will be first normalized. This can reduce efficiency.
  • mask (numpy.ndarray) – An optional mask (a non-zero value invalidate the pixels of the image) If the image is not a continuous array of signed integer 8bits, the data will be first normalized. This can reduce efficiency.
  • group_size (int) – Specify the size of the tile to split the computation with OpenMP. It is also used as tile size to compute the min/max cache
  • use_minmax_cache (bool) – If true the min/max cache is enabled.
find_contours(self, level=None)

Compute the list of polygons of the iso contours at this level.

Parameters:level (float) – Level of the requested iso contours.
Returns:A list of array containg y-x coordinates of points
Return type:List[numpy.ndarray]
find_pixels(self, level)

Compute the pixels from the image over the requested iso contours at this level. Pixels are those over the bound of the segments.

Parameters:level (float) – Level of the requested iso contours.
Returns:An array of y-x coordinates.
Return type:numpy.ndarray