shepseg

Python implementation of the image segmentation algorithm described by Shepherd et al

Shepherd, J., Bunting, P. and Dymond, J. (2019).

Operational Large-Scale Segmentation of Imagery Based on Iterative Elimination. Remote Sensing 11(6).

https://www.mdpi.com/2072-4292/11/6/658

Implemented using scikit-learn’s K-Means algorithm, and using numba compiled code for the other main components.

Main entry point is the doShepherdSegmentation() function.

Basic usage

from pyshepseg import shepseg

# Read in a multi-band image as a single array, img,
# of shape (nBands, nRows, nCols).
# Ensure that any null pixels are all set to a known
# null value in all bands. Failure to correctly identify
# null pixels can result in a poorer quality segmentation.

segRes = shepseg.doShepherdSegmentation(img, imgNullVal=nullVal)

The segimg attribute of the segRes object is an array of segment ID numbers, of shape (nRows, nCols).

Resulting segment ID numbers start from 1, and null pixels are set to zero.

Efficient segment location

After segmentation, the location of individual segments can be found efficiently using the object returned by makeSegmentLocations().

E.g.

segSize = shepseg.makeSegSize(segimg)
segLoc = shepseg.makeSegmentLocations(segimg, segSize)

This segLoc object is indexed by segment ID number (must be of type shepseg.SegIdType), and each element contains information about the pixels which are in that segment. This information can be returned as a slicing object suitable to index the image array

E.g.

segNdx = segLoc[segId].getSegmentIndices()
vals = img[0][segNdx]

This example would give an array of the pixel values from the first band of the original image, for the given segment ID.

This can be a very efficient way to calculate per-segment quantities. It can be used in pure Python code, or it can be used inside numba jit functions, for even greater efficiency.

class pyshepseg.shepseg.RowColArray(length)
append()
getSegmentIndices()
class pyshepseg.shepseg.SegmentationResult

Results of the segmentation process

segimg

Segment image, as numpy array (nRows, nCols) Elements are segment ID numbers (starting from 1)

kmeans

The sklearn KMeans object, after fitting

maxSpectralDiff

The value used to limit segment merging

singlePixelsEliminated

Number of single pixels merged to adjacent segments

smallSegmentsEliminated

Number of small segments merged into adjacent segments

kmeans = None
maxSpectralDiff = None
segimg = None
singlePixelsEliminated = None
smallSegmentsEliminated = None
pyshepseg.shepseg.applySpectralClusters(kmeansObj, img, imgNullVal)

Use the given KMeans object to predict spectral clusters on a whole image array.

The kmeansObj is an instance of sklearn.cluster.KMeans, as returned by fitSpectralClusters().

The img array is a numpy array of the image to predict on, of shape (nBands, nRows, nCols).

Any pixels in img which have value imgNullVal will be set to SEGNULLVAL (i.e. zero) in the output cluster image.

Return value is a numpy array of shape (nRows, nCols), with each element being the segment ID value for that pixel.

pyshepseg.shepseg.autoMaxSpectralDiff(km, maxSpectralDiff, distPcntile)

Work out what to use as the maxSpectralDiff.

If current value is ‘auto’, then return the median spectral distance between cluster centres from the KMeans clustering object km.

If current value is None, return 10 times the largest distance between cluster centres (i.e. too large ever to make a difference)

Otherwise, return the given current value.

pyshepseg.shepseg.buildSegmentSpectra(seg, img, maxSegId)

Build an array of the spectral statistics for each segment. Return an array of shape

(numSegments+1, numBands)

where each row is the entry for that segment ID, and each column is the sum of the spectral values for that band. The zero-th entry is empty, as zero is not a valid segment ID.

pyshepseg.shepseg.clump(img, ignoreVal, fourConnected=True, clumpId=1)

Implementation of clumping using Numba.

Parameters
  • img – should be an integer 2d array containing the data to be clumped.

  • ignoreVal – should be the no data value for the input

  • fourConnected – If True, use 4-way connected, otherwise 8-way

  • clumpId – is the start clump id to use

Returns

a 2d uint32 array containing the clump ids and the highest clumpid used + 1

pyshepseg.shepseg.diagonalClusterCentres(xSample, numClusters)

Return an array of initial guesses at cluster centres. This will be given to the KMeans constructor as the init parameter.

The given array xSample is the (numPoints, numBands) array ready to be used for fitting.

The centres are evenly spaced along the diagonal of the bounding box of the data. The end points are placed 1 step in from the corners.

pyshepseg.shepseg.doMerge(segId, nbrSegId, seg, segSize, segLoc, spectSum)

Carry out a single merge. The segId segment is merged to the neighbouring nbrSegId. Modifies seg, segSize, segLoc and spectSum in place.

pyshepseg.shepseg.doShepherdSegmentation(img, numClusters=60, clusterSubsamplePcnt=1, minSegmentSize=50, maxSpectralDiff='auto', imgNullVal=None, fourConnected=True, verbose=False, fixedKMeansInit=False, kmeansObj=None, spectDistPcntile=50)

Perform Shepherd segmentation in memory, on the given multi-band img array.

The img array has shape (nBands, nRows, nCols).

numClusters and clusterSubsamplePcnt are passed through to fitSpectralClusters().

minSegmentSize is the minimum segment size (in pixels) which will be left after eliminating small segments (except for segments which cannot be eliminated).

maxSpectralDiff sets a limit on how different segments can be and still be merged. It is given in the units of the spectral space of img. If maxSpectralDiff is ‘auto’, a default value will be calculated from the spectral distances between cluster centres, as a percentile of the distribution of these (spectDistPcntile). The value of spectDistPcntile should be lowered when segementing an image with a larger range of spectral distances.

Default values are mostly as suggested by Shepherd et al.

If fourConnected is True, then use 4-way connectedness when clumping, otherwise use 8-way connectedness.

If imgNullVal is not None, then pixels with this value in any band are set to zero (SEGNULLVAL) in the output segmentation. If there are null values in the image array, it is important to give this null value, as it can strongly affect the initial spectral clustering, which in turn strongly affects the final segmentation.

If fixedKMeansInit is True, then choose a fixed set of cluster centres to initialize the KMeans algorithm. This can be useful to provide strict determinacy of the results by avoiding sklearn’s multiple random initial guesses. The default is to allow sklearn to guess, which is good for avoiding local minima.

By default, the spectral clustering step will be fitted using the given img. However, if kmeansObj is not None, it is taken to be a fitted instance of sklearn.cluster.KMeans, and will be used instead. This is useful when enforcing a consistent clustering across multiple tiles (see the pyshepseg.tiling module for details).

Segment ID numbers start from 1. Zero is a NULL segment ID.

The return value is an instance of SegmentationResult class.

pyshepseg.shepseg.eliminateSinglePixels(img, seg, segSize, minSegId, maxSegId, fourConnected)

Approximate elimination of single pixels, as suggested by Shepherd et al (section 2.3, page 6). This step suggested as an efficient way of removing a large number of segments which are single pixels, by approximating the spectrally-nearest neighbouring segment with the spectrally-nearest neighouring pixel.

Parameters
  • img – the original spectral image, of shape (nBands, nRows, nCols)

  • seg – the image of segments, of shape (nRows, nCols)

  • segSize – Array of pixel counts for every segment

  • minSegId – Smallest segment ID

  • maxSegId – Largest segment ID

  • fourConnected – If True use 4-way connectedness, otherwise 8-way

Segment ID numbers start at 1 (i.e. 0 is not valid)

Modifies seg array in place.

pyshepseg.shepseg.eliminateSmallSegments(seg, img, maxSegId, minSegSize, maxSpectralDiff, fourConnected, minSegId)

Eliminate small segments. Start with smallest, and merge them into spectrally most similar neighbour. Repeat for larger segments.

minSegSize is the smallest segment which will NOT be eliminated

pyshepseg.shepseg.findMergeSegment(segId, segLoc, seg, segSize, spectSum, maxSpectralDiff, fourConnected)

For the given segId, find which neighboring segment it should be merged with. The chosen merge segment is the one which is spectrally most similar to the given one, as measured by minimum Euclidean distance in spectral space.

pyshepseg.shepseg.findNearestNeighbourPixel(img, seg, i, j, segSize, fourConnected)

For the (i, j) pixel, choose which of the neighbouring pixels is the most similar, spectrally.

Returns tuple (ii, jj) of the row and column of the most spectrally similar neighbour, which is also in a clump of size > 1. If none is found, return (-1, -1)

pyshepseg.shepseg.fitSpectralClusters(img, numClusters, subsamplePcnt, imgNullVal, fixedKMeansInit)

First step of Shepherd segmentation. Use K-means clustering to create a set of “seed” segments, labelled only with their spectral cluster number.

The img array has shape (nBands, nRows, nCols). numClusters is the number of clusters for the KMeans algorithm to find (i.e. it is ‘k’). subsamplePcnt is the percentage of the pixels to actually use for KMeans clustering. Shepherd et al find that only a very small percentage is required.

If imgNullVal is not None, then pixels in img with this value in any band are set to segNullVal in the output.

if fixedKMeansInit is True, then use a simple algorithm to determine the fixed set of initial cluster centres. Otherwise allow the sklearn routine to choose its own initial guesses.

Return a fitted object of class sklearn.cluster.KMeans. This is suitable to use with the applySpectralClusters() function.

pyshepseg.shepseg.makeSegSize(seg)

Return an array of segment sizes, from the given seg image. The returned array is indexed by segment ID. Each element is the number of pixels in that segment.

pyshepseg.shepseg.makeSegmentLocations(seg, segSize)

Create a data structure to hold the locations of all pixels in all segments.

pyshepseg.shepseg.mergeSinglePixels(img, seg, segSize, segToElim, fourConnected)

Search for single-pixel segments, and decide which neighbouring segment they should be merged with. Finds all to eliminate, then performs merge on all selected. Modifies seg and segSize arrays in place, and returns the number of segments eliminated.

pyshepseg.shepseg.relabelSegments(seg, segSize, minSegId)

The given seg array is an image of segment labels, with some numbers unused, due to elimination of small segments. Go through and find the unused numbers, and re-label segments above these so that segment labels are contiguous.

Modifies the seg array in place. The segSize array is not updated, and should be recomputed.