Package net.algart.matrices.skeletons

Class ApertureBasedSkeletonPixelClassifier

java.lang.Object
net.algart.matrices.skeletons.SkeletonPixelClassifier
net.algart.matrices.skeletons.ApertureBasedSkeletonPixelClassifier
Direct Known Subclasses:
BasicSkeletonPixelClassifier2D
public abstract class ApertureBasedSkeletonPixelClassifier extends SkeletonPixelClassifier

A skeletal implementation of the SkeletonPixelClassifier abstract class, minimizing the effort required to implement its abstract methods.

Namely, the main asPixelTypes method is implemented in this class via the following 2 abstract methods:

The methods neighbourOffset(long[], int) and reverseNeighbourIndex(int) are implemented on the base of the array of offsets of all neighbours of a random element. This array should be passed to the constructor. The constructor analyses the passed array, checks that it really contains offsets of all neighbours, copies this array into an internal field, which is used by neighbourOffset(long[], int), and also automatically finds, for every neighbour, the reverse neighbour index, which will be returned by reverseNeighbourIndex(int).

The method markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[]) is implemented here in some reasonable way for 2-dimensional case, as specified in comments to this method. For other number of dimensions, this method does nothing. It is a good solution for the degenerated case dimCount()=1; for 3-dimensional case, this method probably should be overridden.

So, it is enough to implement pixelTypeOrAttachingBranch(int) and pixelTypeOrAttachedNode(int) methods and, maybe, override markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[]) method to create a full implementation of the skeleton pixel classifier on the base of this class.

This class can be used in 1-, 2- and 3-dimensional cases only. One of the reasons of this restriction is that the argument of pixelTypeOrAttachingBranch(int) and pixelTypeOrAttachedNode(int) (int type) can represent the values of, maximally, 32 neighbours. It is enough for 3-dimensional case, where the number of neighbours is 33−1=26<32, but not enough already for 4-dimensional case, where the number of neighbours is 34−1=80 (and even 64-bit long type would have been insufficient).

This class is immutable and thread-safe: there are no ways to modify settings of the created instance.

Author:
Daniel Alievsky

  • Constructor Details

    • ApertureBasedSkeletonPixelClassifier

      protected ApertureBasedSkeletonPixelClassifier(int dimCount, long[][] neighbourOffsets)
      Creates new instance of this class, allowing to process skeletons with the given number of dimensions, with the order of neighbours, specified in the second argument. The number of dimensions must be 1, 2 or 3.

      The argument neighbourOffsets must contain offsets of all neighbours, in terms of the straight-and-diagonal connectivity kind, of any matrix element, in some order. More precisely, this array must contain numberOfNeighbours()=3dimCount-1 elements (2, 8 or 26 for 1-, 2-, 3-dimensional cases) in 3/3x3/3x3x3-aperture, and each its element neighbourOffsets[k] must be equal to the result of neighbourOffset(k) call.

      The passed neighbourOffsets array is deeply cloned by the constructor: no references to it or its elements are maintained by the created object.

      Parameters:
      dimCount - the number of dimensions, which will be returned by dimCount() method.
      neighbourOffsets - offsets of all neighbours of any matrix element, in terms of neighbourOffset(int) method.
      Throws:
      NullPointerException - if neighbourOffsets or one of its elements is null.
      IllegalArgumentException - if dimCount is not in 1..3 range, or if neighbourOffsets.length!=3dimCount-1, or if neighbourOffsets[k].length!=dimCount for some k, or if neighbourOffsets does not contain, in some order, the offsets of all 3dimCount-1 neighbours (in particular, if some elements neighbourOffsets[k][j] are not in -1..+1 range or if offsets of some neighbours are equal).

  • Method Details

    • neighbourOffset

      public void neighbourOffset(long[] coordinateIncrements, int neighbourIndex)
      Description copied from class: SkeletonPixelClassifier
      More efficient version of neighbourOffset(int) method, which stores the results in the passed Java array instead of creating new Java array. This method is equivalent to calling that method and copying its result into coordinateIncrements argument, but does not allocate any arrays. It is a better solution if we need to calculate neighbour offsets in a long loop, because allows to avoid allocating a lot of short arrays.

      The length of the passed array must be equal to the number of dimensions of processed matrices.

      Specified by:
      neighbourOffset in class SkeletonPixelClassifier
      Parameters:
      coordinateIncrements - Java array for storing the differences of all coordinates of the neighbour #neighbourIndex of some (central) element and the coordinates of this central element.
      neighbourIndex - an index if the neighbour of some central element of the matrix.
      See Also:

    • reverseNeighbourIndex

      public int reverseNeighbourIndex(int neighbourIndex)
      Description copied from class: SkeletonPixelClassifier
      Returns an index of such neighbour B of some element A of a skeleton matrix, so that the element A is the neighbour with the specified index neighbourIndex of its neighbour B. Both neighbour indexes are considered in terms of neighbourOffset(int) method. It means, that if k1 is the argument of this method and k2 is the result of this method, offset1=neighbourOffset(k1) and offset2=neighbourOffset(k2), then
      offset2[i] = -offset1[i] for all i.

      For example, in BasicSkeletonPixelClassifier2D class (which enumerates 8 neighbours along the perimeter of 3x3 square) this method returns (neighbourIndex+4)%8.

      Specified by:
      reverseNeighbourIndex in class SkeletonPixelClassifier
      Parameters:
      neighbourIndex - an index of some neighbour B of some central element A.
      Returns:
      an index of the central element A as a neighbour of the element B.

    • asPixelTypes

      public Matrix<? extends PIntegerArray> asPixelTypes(Matrix<? extends BitArray> skeleton, SkeletonPixelClassifier.AttachmentInformation attachmentInformation)
      Description copied from class: SkeletonPixelClassifier
      Returns an immutable view of the passed skeleton matrix, where each element is an integer, specifying the type of the corresponding pixel of the skeleton. The number of dimensions of the passed matrix must be equal to dimCount().

      More precisely, let's consider that skeleton matrix is the result of some skeletonization algorithm (chosen while creating an instance of this class). The resulting matrix will contain the following values:

      1. SkeletonPixelClassifier.TYPE_ZERO, if the corresponding element of the skeleton is zero (no pixel);
      2. SkeletonPixelClassifier.TYPE_ILLEGAL, if here is an impossible configuration for a correct result of the given skeletonization algorithm (probable case, if the passed matrix is really not a skeleton);
      3. SkeletonPixelClassifier.TYPE_USUAL_NODE, if the corresponding element of the skeleton is a node, where 3 or more branches meet;
      4. SkeletonPixelClassifier.TYPE_ISOLATED, if the corresponding element of the skeleton is an isolated unit pixel, having no unit neighbour elements;
      5. SkeletonPixelClassifier.TYPE_FREE_BRANCH_END, if the corresponding element of the skeleton is an end of some branch, having 1 unit neighbour elements;
      6. SkeletonPixelClassifier.TYPE_USUAL_BRANCH, if the corresponding element of the skeleton has 2 unit neighbour elements;
      7. some non-negative value in 0..numberOfNeighbours()-1 range, if the corresponding element of the skeleton has ≥3 unit neighbour elements, but this class recommends to consider this pixel not a node, but an additional "attached" element of some branch. In this case, this value means the following:
        1. if attachmentInformation argument is SkeletonPixelClassifier.AttachmentInformation.NEIGHBOUR_INDEX_OF_ATTACHED_NODE, this value specifies the direction (neighbour index) towards the neighbouring node, which is one of the ends of this branch; there is a guarantee that this neighbour is either really node or, maybe, SkeletonPixelClassifier.TYPE_ILLEGAL;
        2. if attachmentInformation argument is SkeletonPixelClassifier.AttachmentInformation.NEIGHBOUR_INDEX_OF_ATTACHING_BRANCH, this value specifies the direction (neighbour index) towards the branch, to which this pixel should be attached as its ending element; there is no guarantee that this neighbour is really a branch element, but it cannot be zero or isolated, and if it is a node, it is supposed that we have a short branch to it, consisting of 1 pixel.
        See also the comments to SkeletonPixelClassifier, section "Pixel types", group 5.
        The direction is specified in terms of neighbourOffset(int) method. In BasicSkeletonPixelClassifier2D, it can be 0,1,2,3,4,5,6,7, corresponding to the following diagram: 
         0 1 2
 7 C 3
 6 5 4

        (the x-axis is directed rightward, the y-axis is directed downward). Namely, if the current element has coordinates (x,y), then "0" value means attaching of the node with coordinates (x−1,y−1) (the case A) or attaching of the node to the branch containing the pixel (x−1,y−1) (the case B), "1" value means attaching of the node / to the branch (x,y−1), "2" value means attaching of the node / to the branch (x+1,y−1), "3" value means attaching of the node / to the branch (x+1,y), "4" value means attaching of the node / to the branch (x+1,y+1), "5" value means attaching of the node / to the branch (x,y+1), "6" value means attaching of the node / to the branch (x−1,y+1), "7" value means attaching of the node / to the branch (x−1,y).

      Note, that the situation, when some neighbouring elements are out of ranges of the matrix coordinates, is processed according to the model of infinite pseudo-cyclical continuation — see the end of the comments to SkeletonPixelClassifier.

      Note, that all values, specified by constants of this class (all cases 1-6 above, excepting the last case 7), are different negative integers. Then, note that SkeletonPixelClassifier.TYPE_USUAL_NODE, SkeletonPixelClassifier.TYPE_ISOLATED and SkeletonPixelClassifier.TYPE_FREE_BRANCH_END are adjacent integers -3..-1. Then, note that two constants, corresponding to branches and their ends — SkeletonPixelClassifier.TYPE_FREE_BRANCH_END and SkeletonPixelClassifier.TYPE_USUAL_BRANCH — are also adjacent integers -4..-3. Then, note that two constants, corresponding to nodes and isolated pixels — SkeletonPixelClassifier.TYPE_USUAL_NODE and SkeletonPixelClassifier.TYPE_ISOLATED — are also adjacent integers -2..-1. This can be useful for extracting special kinds of skeleton pixels into bit matrices.

      Specified by:
      asPixelTypes in class SkeletonPixelClassifier
      Parameters:
      skeleton - the skeleton matrix that should be processed.
      attachmentInformation - what should this method return for attachable pixels.
      Returns:
      the matrix of integer codes with the same sizes, describing the types of all skeleton pixels.

    • markNeighbouringNodesNotConnectedViaDegeneratedBranches

      public void markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[] pixelTypesOfAllNeighbours)
      Description copied from class: SkeletonPixelClassifier
      Finds and marks, by assigning Integer.MIN_VALUE to corresponding elements of the passed Java array, all neighbours of some node, which are also nodes and are considered to be not connected with this node via a degenerated 0-pixel branch. Neighbouring nodes, which are considered to be connected with the central node via 0-pixel branch, stay unchanged.

      More precisely, this method analyses the Java array pixelTypesOfAllNeighbours, which contains the pixel types of all neighbours of some "central" pixel, which is supposed to be a node, in the order, defined by neighbourOffset(int) method. This method finds among them all values, equal to SkeletonPixelClassifier.TYPE_USUAL_NODE, and, if this class considers that they should not be connected with the central node via degenerated branches, such values are replaced with Integer.MIN_VALUE (which means "removing" these neighbours from candidates to connection with the central node). So, if some elements of the passed array are SkeletonPixelClassifier.TYPE_USUAL_NODE after calling this method as before, it means that such neighbouring nodes should be considered as connected with the central node via degenerated branches.

      This method is used in SkeletonScanner.adjacentBranches() to correctly find all degenerated branches, originating in the current node.

      The passed array must contain at least numberOfNeighbours() elements. If it contains more elements, this method processes only first numberOfNeighbours() elements and ignores others.

      In ApertureBasedSkeletonPixelClassifier for 2-dimensional case and, in particular, in BasicSkeletonPixelClassifier2D, the neighbouring node Q of the central node P is not marked for removing (not replaced with Integer.MIN_VALUE), if the segment PQ is not diagonal (4-connected neighbour) or if it is diagonal, but the two adjacent pixels, which are 4-connected neighbours of both P and Q, are not nodes: 

           . . * . . .      . . . * . .
     . . * . . .      . . . * . .
     * * . * * *      . . . Q * *
     . . P Q . .  or  * * P . . .
     . . * . * .      . . * . . .
     . . * . . *      . . * . . .
      In other situations, a diagonal degenerated branch between P and Q would be extra, because they are connected via two horizontal and vertical degenerated 0-pixel branches. (In ApertureBasedSkeletonPixelClassifier class for the number of dimensions, other than 2, the implementation of this method does nothing.)
      Specified by:
      markNeighbouringNodesNotConnectedViaDegeneratedBranches in class SkeletonPixelClassifier
      Parameters:
      pixelTypesOfAllNeighbours - an array of the pixel types of all neighbours of some given element, supposed to be a node; this method will replace some SkeletonPixelClassifier.TYPE_USUAL_NODE values in this array with Integer.MIN_VALUE.

    • asNeighbourhoodBitMaps

      public final Matrix<? extends PIntegerArray> asNeighbourhoodBitMaps(Matrix<? extends BitArray> skeleton)
      Returns an immutable view of the passed skeleton matrix, where each element is an integer, containing, in its low bits, the bit values of the corresponding element C of the source skeleton and of all its neighbours (in terms of the straight-and-diagonal connectivity kind).

      More precisely, each integer element w of the resulting matrix will contain:

      • in the bit #0 (in other words, w&1): the value of the corresponding element C of the source skeleton bit matrix;
      • in the bit #k+1, 0≤k<numberOfNeighbours() (in other words, (w>>>(k+1))&1): the value of the neighbour #k of the central element C, in terms of neighbourOffset(int) method;
      • all other bits of the elements if the resulting matrix will be zero.

      In particular, in BasicSkeletonPixelClassifier2D implementation, the lower 9 bits in the elements of the returned matrix correspond to elements of 3x3 aperture of the source skeleton according the following diagram: 

       1 2 3
 8 0 4
 7 6 5

      (the x-axis is directed rightward, the y-axis is directed downward).

      The implementation of asPixelTypes method in this class is based on this method and pixelTypeOrAttachingBranch(int) and pixelTypeOrAttachedNode(int) methods: the results w, returned by this method for unit central elements C of the source skeleton, are shifted to the right and passed as apertureBits=w>>>1 argument to pixelTypeOrAttachingBranch(int) or pixelTypeOrAttachedNode(int) to form the elements of the resulting matrix.

      Note, that the situation, when the neighbouring elements are out of ranges of the matrix coordinates, is processed according to the model of infinite pseudo-cyclical continuation — see the end of the comments to SkeletonPixelClassifier.

      Parameters:
      skeleton - the skeleton matrix that should be processed.
      Returns:
      the matrix of integer values with the same sizes, containing the bit maps of the neighbourhoods of all skeleton pixels.
      Throws:
      NullPointerException - if skeleton is null.
      IllegalArgumentException - if skeleton.dimCount()!=SkeletonPixelClassifier.dimCount().

    • pixelTypeOrAttachingBranch

      protected abstract int pixelTypeOrAttachingBranch(int apertureBits)
      Calculates and returns the value of an element C' in the resulting matrix, produced by asPixelTypes method with NEIGHBOUR_INDEX_OF_ATTACHING_BRANCH value of attachmentInformation argument, on the base of bit values of all neighbours (in terms of the straight-and-diagonal connectivity kind) of the corresponding unit element C in the source skeleton bit matrix.

      More precisely, the bit values of the neighbours of this skeleton element C are passed via the low m=numberOfNeighbours() bits of apertureBits argument. The bit #k of this argument, 0≤k<m (its value is (apertureBits>>>k)&1), is equal to the value of the neighbour #k in terms of neighbourOffset(int) method. In particular, in BasicSkeletonPixelClassifier2D implementation, the order of neighbours is described by the following diagram: 

       0 1 2
 7 C 3
 6 5 4

      So, 8 low bits of apertureBits contain the values of the corresponding neighbouring elements in anticlockwise order (the x-axis is directed rightward, the y-axis is directed downward).

      It is supposed that the central element (C) of the skeleton is unit (for zero elements ot the skeleton matrix, asPixelTypes method of this class returns SkeletonPixelClassifier.TYPE_ZERO without calling this method).

      Note, that the situation, when the neighbouring elements are out of ranges of the matrix coordinates, is processed according to the model of infinite pseudo-cyclical continuation — see the end of the comments to SkeletonPixelClassifier.

      Parameters:
      apertureBits - the values of all 8 neighbours of the current unit element of the source skeleton bit matrix.
      Returns:
      the type of this pixel of the skeleton.

    • pixelTypeOrAttachedNode

      protected abstract int pixelTypeOrAttachedNode(int apertureBits)
      Calculates and returns the value of an element C' in the resulting matrix, produced by asPixelTypes method with NEIGHBOUR_INDEX_OF_ATTACHED_NODE value of attachmentInformation argument, on the base of bit values of all neighbours (in terms of the straight-and-diagonal connectivity kind) of the corresponding unit element C in the source skeleton bit matrix.

      More precisely, the bit values of the neighbours of this skeleton element C are passed via the low m=numberOfNeighbours() bits of apertureBits argument. The bit #k of this argument, 0≤k<m (its value is (apertureBits>>>k)&1), is equal to the value of the neighbour #k in terms of neighbourOffset(int) method. In particular, in BasicSkeletonPixelClassifier2D implementation, the order of neighbours is described by the following diagram: 

       0 1 2
 7 C 3
 6 5 4

      So, 8 low bits of apertureBits contain the values of the corresponding neighbouring elements in anticlockwise order (the x-axis is directed rightward, the y-axis is directed downward).

      It is supposed that the central element (C) of the skeleton is unit (for zero elements ot the skeleton matrix, asPixelTypes method of this class returns SkeletonPixelClassifier.TYPE_ZERO without calling this method).

      Note, that the situation, when the neighbouring elements are out of ranges of the matrix coordinates, is processed according to the model of infinite pseudo-cyclical continuation — see the end of the comments to SkeletonPixelClassifier.

      Parameters:
      apertureBits - the values of all 8 neighbours of the current unit element of the source skeleton bit matrix.
      Returns:
      the type of this pixel of the skeleton.