Package net.algart.matrices.skeletons

Interface ThinningSkeleton

All Superinterfaces:
ArrayProcessor, IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
All Known Implementing Classes:
OctupleThinningSkeleton2D, Quadruple3x5ThinningSkeleton2D, StrongQuadruple3x5ThinningSkeleton2D, WeakOctupleThinningSkeleton2D
public interface ThinningSkeleton extends IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>

Common 2-dimensional skeletonization algorithm of binary matrices, based on ≤8 thinning steps, corresponding to all or some from 8 directions with the step 45 degree. The following concrete skeletonization classes implements it:

This interface extends IterativeArrayProcessor interface, iteratively processing some bit matrix (Matrix(UpdatableBitArray)), named result and usually passed to instantiation methods. It is supposed, that in all implementations of this interface:

  • performIteration(ArrayContext) method sequentially calls asThinning(int directionIndex) method and copies its result to the result matrix for directionIndex=0,1,2,3,4,5,6,7. It means, that all "objects" in the matrix (areas filled by 1 elements) are "thinned" 8 times: from left direction, from left-top diagonal direction, etc. Depending on implementation, performIteration(ArrayContext) may skip calling asThinning for some of these directions — you can check this by isThinningRequired(int) method.
  • done() method returns true if the last iteration was unable to change the matrix: all "objects" are already "thin".
  • result() method always returns the reference to the source matrix, passed to instantiation methods of the inheritors.

All classes of this package, implementing this interface, guarantee that 8-connected "objects" (areas filled by 1 elements) always stay 8-connected.

More precisely, let's consider an AlgART bit matrix Matrix<UpdatableBitArray>, processed by this class. The 8-connected object is a connected component of the graph, built on the matrix, where unit matrix elements are vertices, and neighbour unit elements are connected by edges. Neighbour elements are 2 elements with coordinates (x1, y1) and (x2, y2), where max(|x1−x2|, |y1−y2|) = 1, i.e. every matrix element has 8 neighbours. We can consider that the matrix contains images of some objects: unit bits (1) are white pixels, belonging to objects, zero bits (0) are black pixels of the background. Then our term "8-connected objects" describes the white objects, separated by black space.

The state "8-connected objects always stay 8-connected" means the following. Let A is the current result matrix and A' is either the result asThinning(int) method or the new result matrix after calling performIteration(ArrayContext) method. It is guaranteed that:

  1. the set of unit elements of the matrix A' is equal to or is a subset of the set of unit element of the matrix A; in other words, the skeletonization always reduces objects and never expands them;
  2. if C is some 8-connected object in the matrix A and C' is a set of points (unit elements) in the matrix A', belonging to the area C, then C' is an empty set or 8-connected object.

It is obvious that the same state is true if we performs any number of calls of performIteration instead of one call.

For most kinds of skeletons, the 2nd condition is more strong: the 8-connected object C' cannot be an empty set. In other words, connected objects are never removed at all, they are only "thinned". The only skeletons of this package, for which it is not true, are so called topological skeletons, offered by OctupleThinningSkeleton2D and WeakOctupleThinningSkeleton2D classed by the corresponding "topological" argument of the instantiation methods.

The resulting "skeleton" (after finishing IterativeArrayProcessor.process() method) are usually "thin" enough (1-pixel lines), but some little not "thin" areas are possible.

All classes of this package, implementing this interface, suppose that the processed matrix is infinitely pseudo-cyclically continued, as well Matrices.asShifted method supposes it. You can change this behavior by appending the source matrix with zero elements by calling Matrix.subMatrix(long[], long[], Matrix.ContinuationMode) method, where the dimensions of the "submatrix" are greater than dimensions of the source one by 1 and the continuationMode argument is Matrix.ContinuationMode.ZERO_CONSTANT.

The classes, implementing this interface, are usually thread-compatible and can be synchronized manually, if multithread access is necessary.

Author:
Daniel Alievsky

  • Method Details

    • isThinningRequired

      boolean isThinningRequired(int directionIndex)
      Returns true if and only if performIteration(ArrayContext) method really calls asThinning(int directionIndex) for this direction and copies its result to the result matrix. It depends on the implementation of this interface.
      Parameters:
      directionIndex - the direction of thinning, from 0 to 7.
      Returns:
      whether the matrix should be thinned along this direction.
      Throws:
      IllegalArgumentException - if directionIndex is not in 0..7 range.

    • asThinning

      Matrix<BitArray> asThinning(int directionIndex)
      Returns current result() matrix thinned along the given direction. The result is "lazy": it is only a view of the current matrix. It is the basic method, implementing the skeletonization algorithm.

      Generally speaking, the "thinning" means removing elements from the boundary of any "object" (area of the matrix filled by 1). directionIndex specifies the "eroded side" of objects, or the direction of thinning:

      • 0 means removing elements from the left, i.e. from the side (x−1,y),
      • 1 means "diagonal" removal from the side (x−1,y−1),
      • 2 means removal from the side (x,y−1),
      • 3 means "diagonal" removal from the side (x+1,y−1),
      • 4 means removal from the right, i.e. from the side (x+1,y),
      • 5 means "diagonal" removal from the side (x+1,y+1),
      • 6 means removal from the side (x,y+1),
      • 7 means "diagonal" removal from the side (x−1,y+1).

      Some directions may be ignored by an implementation; in this case, the reference to the current result() matrix is returned. Note: there is no guarantee that this method ignores directions, for which isThinningRequired(int directionIndex) method returns false.

      Parameters:
      directionIndex - the direction of thinning, from 0 to 7.
      Returns:
      the thinned view if the current IterativeArrayProcessor.result() matrix.
      Throws:
      IllegalArgumentException - if directionIndex is not in 0..7 range.