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.
- 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
- 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 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