Package net.algart.matrices.skeletons

Class SkeletonPixelClassifier

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

Classifier of pixels of skeletons (bit matrices, generated by skeletonization algorithms), separating them into "nodes", "branch pixels" and other groups. This class can be used together with SkeletonScanner class, providing a full solution of analysing the structure of a skeleton.

Note, that every type of skeletonization algorithm, generally speaking, requires a specific pixel classifier, which "knows" all pixel configuration, that can appear in the results of that algorithm. The class BasicSkeletonPixelClassifier2D offers ready pixel classifiers for OctupleThinningSkeleton2D, Quadruple3x5ThinningSkeleton2D and StrongQuadruple3x5ThinningSkeleton2D algorithms.

Pixel types

The main purpose of this class is detecting the type of each skeleton pixel: is it a node, a branch pixel, an isolated pixel, or, maybe, an "illegal" pixel which cannot appear in a correct skeleton. More precisely:

  1. we call a pixel (a unit element of the skeleton matrix) usual branch pixel, if this element of the skeleton has strictly 2 unit neighbour elements;
  2. we call a pixel free branch end, if this element of the skeleton has strictly 1 unit neighbour element;
  3. we call a pixel isolated, if this element of the skeleton has no neighbour elements;
  4. we call a pixel "illegal", if analysis of some close neighbourhood of this pixel (usually 3x3 or 5x5) allows to conclude, that this pixel cannot belong to a skeleton of the concrete analysed kind;
  5. in other cases, i.e. if a unit pixel has k≥3 neighbours and is not "illegal", we call it either node, or an attachable branch end. The concrete implementation of this abstract class defines, which of such pixels are considered to be nodes, and which are considered to be attachable branch ends. For each attachable branch end E, this class also detects two from its k neighbours with special roles:
    1. the 1st of them, A, is always node and is called "attached node" (so there is a guarantee that an attachable branch end is always have a node among neighbours),
    2. the 2nd, B, is called "an element of attaching branch" and it is:
          — either really a branch pixel: usual, free end or attachable (that means: this branch is "extended" with this attachable pixel E to achieve the node A),
          — or another node (that means: we have 1-pixel branch A–E–B, connecting nodes A and B).
    (Note that if the skeleton contains "illegal" pixels, they also may be detected as "attached node" and "an element of attaching branch");
  6. the last possible case is trivial: zero element of the skeleton matrix.

Nodes, branches, degenerated branches

As a result of detecting pixel types, this class separates all unit pixels of the correct skeleton, generated by some skeletonization algorithm (and, so, not containing "illegal" pixels), into the following categories:

If two nodes or free branch ends are neighbours (in straight-and-diagonal connectivity terms, see below), then they may be considered to be connected with a degenerated branch, consisting of 0 pixels. If at least one of them is a free branch end, then we always consider them to be connected with a degenerated branch. If both are nodes, then the decision, whether these neighbouring nodes are connected with a degenerated branch, is made by markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[]) method; it is used in SkeletonScanner.adjacentBranches() method.

About the nonoriented graph, formed by the skeleton

This class guarantees that if the skeleton is correct (contains no "illegal" pixels), then the nodes and branches form a correct skeleton nonoriented graph, with skeleton nodes, free branch ends and isolated pixels in a role of graph nodes, and skeleton branches (excluding free branch ends) in a role of graph edges. "Correct" graph means that:

  1. each connected component of the skeleton (bit matrix) corresponds to a connected component of this graph;
  2. any branch is a connected series of 0, 1 or more unit pixels, connecting strictly 2 different nodes or free branch ends (playing the role of graph nodes: ends of the corresponding graph edge). For nondegenerate branches (containing at least 1 pixel between ending nodes or free branch ends), all their pixels belong to "usual branch pixels" type (strictly 2 unit neighbours) or "attachable branch end" type (having 3 or more unit neighbours), and only the first and the last among them can be attachable ends. If the first or the last pixel, really, is an attachable end, then it is considered that the attached node A, defined above in the description of group 5 of pixel types, plays the role of the corresponding graph node, incident with the given branch/edge. The pixel B (see the description of group 5) plays the role of the second graph node, incident with the given branch/edge, if it is a node or a free branch end: it means that we have 1-pixel branch;
  3. there is the only possible exception from the rules I and II: if a skeleton contains cyclic branches, i.e. connected components consisting of usual branch pixels only (thin 1-pixel closed lines, where every pixel has strictly 2 unit neighbours), then such branches do not connect any nodes and do not form any elements of the graph (SkeletonScanner class recognizes such branches separately);
  4. nodes of the graph have 0, 1 or ≥3 incident edges, but never have 2 incident edges.

See more detailed and formal definition of the nonoriented graph, formed by the skeleton, in the comments to SkeletonScanner class.

Base functions of this class

One instance of this class can process different skeletons (bit matrices), but all they must have the fixed number of dimensions, returned by dimCount() method.

The main method of this class is

asPixelTypes(Matrix, SkeletonPixelClassifier.AttachmentInformation),

which performs classification of pixels of the given skeleton matrix. The second important method of this class is

markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[]),

which allows to decide, whether two neighbouring nodes should be considered as connected with a degenerated 0-pixel branch. (It is the only situation, when the results of asPixelTypes are not enough to recognize, whether two nodes of skeleton nonoriented graph should be connected with an edge.) This class also provides neighbourOffset(int) method, which specifies some order of the 3n−1 neighbours, n=dimCount(), of each matrix element and is necessary for interpretation of non-negative values, returned by asPixelTypes method.

Connectivity model (straight-and-diagonal) and "neighbour" term

Note that this class, as well as SkeletonScanner, supposes the straight-and-diagonal connectivity kind: see ConnectivityType.STRAIGHT_AND_DIAGONAL. It means, that all skeletons are supposed to be connected in terms of this connectivity: every connected component of the skeleton matrix is a "carcass" or "skeleton" of some connected component of the original matrix, for which this skeleton was built.

So, the term "neighbour" of some pixel (matrix element) in this class and in SkeletonScanner always means another pixel (matrix element), so that

max (|ik−jk|)=1

where i0, i1, ..., in-1 are coordinates of the first pixel and j0, j1, ..., jn-1 are coordinates of the second pixel (a neighbour of the first one). In 2-dimensional case, such connectivity kind is also called 8-connectivity.

Example of results

Below is a simple example of 2-dimensional skeleton, the pixels of which are classified by this class into nodes (N), usual branch pixels (b), free branch ends (E), attachable branch ends (a) and isolated pixels (I):

 . . . . . . . . . . . . . . . . .
 . . . . . . E . . . . . . . . . .
 . . E . . . b . . E . . I . E E .
 . . . b a N . . b . . . . . . . .
 . . . . . a . . a . b E . . . I .
 . . . . . . b a N N . . . . . . .
 . . . . . . . . a . . . . E . . .
 . . b b . . . . b . . . . b . . .
 . b . . b . . E . . . . . E . . .
 . b . . . b . . . . . . . . . E .
 . b . . . b . . . . . . . b b . .
 . . b b b . . . . E b b b . . . .
 . . . . . . . . . . . . . . . . .

In the left bottom part you can see an example of a cyclic branch, consisting only of usual branch pixels (b).

Creating instances of this class

This class is designed for a case of any number of dimensions, though, of course, the most popular case is 2-dimensional. This package provides the following 2-dimensional full implementation of this class:

You can also extend the skeletal implementation of this class: ApertureBasedSkeletonPixelClassifier.

Pseudo-cyclic continuation

This class supposes 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.

Multithread compatibility

This class and its inheritors from this package are immutable and thread-safe: there are no ways to modify settings of the created instance.

Author:
Daniel Alievsky
See Also:

  • Field Details

    • TYPE_USUAL_NODE

      public static final int TYPE_USUAL_NODE
      Node pixel type for a skeleton matrix. (This value can appear in the result of asPixelTypes method.)

      Such matrix element is always unit and also has ≥3 unit neighbours, but these conditions are not enough: unit element with ≥3 unit neighbours may be not only a node, but also an attachable branch end. Strict definition of node pixels may depend on the implementation of asPixelTypes method, — but it is chosen in such a way, that the nodes and branches form a correct skeleton nonoriented graph, as written in the comments to this class. Informally, this pixel type indicates the situation when 3 or more thin connected 1-pixel branches meet.

      In the nonoriented graph, formed by the skeleton, such pixel is treated as a node of the graph, where 3 or more edges meet.

      Below are typical examples for 2D case: 

       . . . . 1      . . 1 . .
 1 1 . 1 .      . . 1 . .
 . . 1 . .  or  1 1 1 1 1
 . . 1 . .      . . 1 . .
 . . 1 . .      . . 1 . .

      This constant is -1.

      See Also:

    • TYPE_ISOLATED

      public static final int TYPE_ISOLATED
      Isolated pixel type for a skeleton matrix. (This value can appear in the result of asPixelTypes method.)

      Formal definition: a matrix element is an isolated pixel if and only if this element is unit and has no unit neighbours.

      In the nonoriented graph, formed by the skeleton, such pixel is treated as a special degenerated case of a node.

      This situation is shown below for 2D case: 

       . . . . .
 . . . . .
 . . 1 . .
 . . . . .
 . . . . .

      This constant is -2.

      See Also:

    • TYPE_FREE_BRANCH_END

      public static final int TYPE_FREE_BRANCH_END
      Free branch end pixel type for a skeleton matrix. (This value can appear in the result of asPixelTypes method.)

      Formal definition: a matrix element is a free branch end if and only if this element is unit and has exactly 1 unit neighbour.

      In the nonoriented graph, formed by the skeleton, such pixel is treated as a node of the graph, having 1 incident edge.

      Below is a typical example for 2D case: 

       . . . . .
 1 1 . . .
 . . 1 . .
 . . . . .
 . . . . .

      This constant is -3.

      See Also:

    • TYPE_USUAL_BRANCH

      public static final int TYPE_USUAL_BRANCH
      Usual branch pixel type for a skeleton matrix. (This value can appear in the result of asPixelTypes method.)

      Formal definition: a matrix element is a usual branch pixel if and only if this element is unit and has exactly 2 unit neighbours.

      In the nonoriented graph, formed by the skeleton, such pixel is treated as an internal pixel of an edge of the graph.

      Below is a typical example for 2D case: 

       . . . . .
 1 1 . . .
 . . 1 1 .
 . . . . 1
 . . . . .

      This constant is -4.

      See Also:

    • TYPE_ILLEGAL

      public static final int TYPE_ILLEGAL
      "Illegal" pixel type for a skeleton matrix. (This value can appear in the result of asPixelTypes method.)

      Strict definition of "illegal" pixels may depend on the implementation of asPixelTypes method, — but it is chosen in such a way, that the unit elements of a correct skeleton, built by the corresponding skeletonization algorithm (on which this implementation of this class is oriented), cannot be "illegal". Informally, this pixel type indicates an impossible configuration for a correct result of the given skeletonization algorithm, where it is impossible to decide, is it a node or an element of a branch.

      Below is a possible example for 2D case: 

       1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 . . . . .
 . . . . .

      (in most skeletonization algorithms, the bottom row of unit pixels should be removed here).

      This value is negative; the concrete value is undocumented and can be changed in future versions.

      See Also:

    • TYPE_ZERO

      public static final int TYPE_ZERO
      Zero element type for a skeleton matrix. (This value can appear in the result of asPixelTypes method.)

      Formal definition: any zero matrix element.

      Obviously, such pixels are not used while forming the skeleton nonoriented graph.

      This value is negative; the concrete value is undocumented and can be changed in future versions.

      See Also:

    • TYPE_NODE_OR_BRANCH_END_MIN

      public static final int TYPE_NODE_OR_BRANCH_END_MIN
      Minimal from 3 adjacent values TYPE_USUAL_NODE, TYPE_ISOLATED and TYPE_FREE_BRANCH_END. This constant is -3.
      See Also:

    • TYPE_NODE_OR_BRANCH_END_MAX

      public static final int TYPE_NODE_OR_BRANCH_END_MAX
      Maximal from 3 adjacent values TYPE_USUAL_NODE, TYPE_ISOLATED and TYPE_FREE_BRANCH_END. This constant is -1.
      See Also:

    • TYPE_BRANCH_MIN

      public static final int TYPE_BRANCH_MIN
      Minimal from 2 adjacent values TYPE_FREE_BRANCH_END, TYPE_USUAL_BRANCH. This constant is -4.
      See Also:

    • TYPE_BRANCH_MAX

      public static final int TYPE_BRANCH_MAX
      Maximal from 2 adjacent values TYPE_FREE_BRANCH_END, TYPE_USUAL_BRANCH. This constant is -3.
      See Also:

    • dimCount

      protected final int dimCount
      The number of dimensions, returned by dimCount() method.

    • numberOfNeighbours

      protected final int numberOfNeighbours
      The number of neighbours of each matrix element, returned by numberOfNeighbours() method. Equal to 3n−1, n=dimCount (the number of elements of 3x3x...x3 hypercube without the central element).

  • Constructor Details

    • SkeletonPixelClassifier

      protected SkeletonPixelClassifier(int dimCount)
      Creates new instance of this class, allowing to process skeletons with the given number of dimensions. The number of dimensions must not be greater than (int)log3(231−1)=19: this condition provides a guarantee that the number of neighbours, returned by numberOfNeighbours() method, can be represented by int Java type.
      Parameters:
      dimCount - the number of dimensions, which will be returned by dimCount() method.
      Throws:
      IllegalArgumentException - if dimCount ≤ 0 or if 3dimCount > Integer.MAX_VALUE=231−1.

  • Method Details

    • isNodePixelType

      public static boolean isNodePixelType(int pixelType)
      Returns true if this pixel type is indicates a node, i.e. a unit element where 3 or more thin connected 1-pixel branches meet or, as a degenerated case, an isolated pixel: a unit element having no unit neighbours. Equivalent to pixelType == TYPE_USUAL_NODE || pixelType == TYPE_ISOLATED.

      Note that all unit pixels in the skeleton, excepting "illegal", are separated into 2 groups: nodes (including isolated pixels as a degenerated case), for which this method returns true, and branch pixels, for which isBranchPixelType(int) returns true.

      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates a node, including the degenerated case of an isolated pixel.

    • isUsualBranchPixelType

      public static boolean isUsualBranchPixelType(int pixelType)
      Returns true if this pixel type indicates a usual branch pixel, i.e. a unit pixel having exactly 2 unit neighbours. Equivalent to pixelType == TYPE_USUAL_BRANCH.
      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates a usual (non-ending) branch pixel.

    • isFreeBranchEndPixelType

      public static boolean isFreeBranchEndPixelType(int pixelType)
      Returns true if this pixel type indicates a free branch end, i.e. a unit pixel having exactly 1 unit neighbour. Equivalent to pixelType == TYPE_FREE_BRANCH_END.
      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates a free branch end.

    • isAttachableBranchEndPixelType

      public static boolean isAttachableBranchEndPixelType(int pixelType)
      Returns true if this pixel type indicates an attachable branch end, i.e. a unit pixel having 3 or more unit neighbours, which this class considers to be not a node, but an ending pixel of some branch. Equivalent to pixelType >= 0. (The value of pixelType argument can appear in the result of asPixelTypes method.)

      Such matrix element is always unit and also has ≥3 unit neighbours, as nodes, but it is not considered to be a node. Strict definition of attachable branch ends may depend on the implementation of asPixelTypes method, — but it is chosen in such a way, that the nodes and branches form a correct skeleton nonoriented graph, as written in the comments to this class. Informally, this pixel type indicates an ending pixel of a thin connected 1-pixel branch, which approaches a node, when the number of neighbours of this pixel is greater than 2.

      In the nonoriented graph, formed by the skeleton, such pixel is treated as an internal pixel of an edge of the graph, as well as usual branch pixels.

      Below is a typical example for 2D case: 

       . . 1 . .
 . . 1 . .
 1 1 1 1 1
 . . 1 . .
 . . 1 . .

      4 unit pixels near the center can be considered as attachable branch ends. All they have 4 unit neighbours, but it is clear that there is no sense to consider them as nodes — unlike the center, which also has 4 unit neighbours and is an obvious node.

      Another example: 

       1 1 . . . 1 1
 . . 1 . 1 . .
 . . . 1 1 . .
 . . . . . 1 .
 . . . . . . 1

      The central unit pixel and its right diagonal neighbour (marked out by bold font) can be considered as attachable branch ends. They have 3 unit neighbours, but it is clear that they may be treated as end elements of the corresponding branches — unlike the true node to the right from the center (marked out by italic font).

      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates an attachable branch end, i.e. if it is non-negative.

    • isNodeOrFreeBranchEndPixelType

      public static boolean isNodeOrFreeBranchEndPixelType(int pixelType)
      Returns true if this pixel type is indicates a node (isNodePixelType(pixelType) returns true) or a free branch end (isFreeBranchEndPixelType(pixelType) returns true). Equivalent to
      pixelType >= TYPE_NODE_OR_BRANCH_END_MIN && pixelType <= TYPE_NODE_OR_BRANCH_END_MAX.

      Note that all such pixels (nodes and free branch ends) corresponds to nodes of a graph, describing the geometric structure of the skeleton (branches correspond to edges in that graph).

      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates a node or a free branch end.

    • isBranchPixelType

      public static boolean isBranchPixelType(int pixelType)
      Returns true if this pixel type is indicates a branch element: usual (where isUsualBranchPixelType(pixelType) returns true), free branch end (where isFreeBranchEndPixelType(pixelType) returns true) or attachable branch end (where isAttachablePixelType(pixelType) returns true). Equivalent to
      pixelType >= 0 || (pixelType >= TYPE_BRANCH_MIN && pixelType <= TYPE_BRANCH_MAX).

      Note that all unit pixels in the skeleton, excepting "illegal", are separated into 2 groups: nodes (including isolated pixels as a degenerated case), for which isNodePixelType(int) returns true, and branch pixels, for which this method returns true.

      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates some element of a branch.

    • isIllegalPixelType

      public static boolean isIllegalPixelType(int pixelType)
      Returns true if this pixel type indicates that the pixel is a center of an impossible configuration for a correct result of the given skeletonization algorithm. Equivalent to pixelType == TYPE_ILLEGAL.
      Parameters:
      pixelType - pixel type: possible element of the result of asPixelTypes method.
      Returns:
      true if this type indicates an incorrect configuration of the pixel's neighbours.

    • dimCount

      public final int dimCount()
      Returns the number of dimensions of the matrices, which can be processed by this object. In SkeletonScanner, equivalent to skeleton().dimCount().
      Returns:
      the number of dimensions of the matrices, which can be processed by this object.

    • numberOfNeighbours

      public final int numberOfNeighbours()
      Returns the number of neighbours of each element of a skeleton matrix, in terms of straight-and-diagonal connectivity kind. Equal to 3n−1, n=dimCount() (the number of elements of 3x3x...x3 hypercube without the central element). In particular, in 2-dimensional case this method returns 32-1=8, and in 3-dimensional case this method returns 33-1=26.
      Returns:
      the number of neighbours of every element.

    • neighbourOffset

      public final long[] neighbourOffset(int neighbourIndex)
      Returns the differences of all coordinates of the neighbour of some (central) element with the given index and the coordinates of this central element. In other words, if i0, i1, ..., in-1 are coordinates of the some element of a skeleton matrix (n=dimCount()), and we need to find the coordinates j0, j1, ..., jn-1 of its neighbour #k, 0≤k<numberOfNeighbours(), we should use the following formula:
      ji = ii + offset[i],

      where offset is the result of calling this method with neighbourIndex=k.

      The returned array is always a newly allocated Java array. Its length is always equal to dimCount(). Its elements will be always same while different calls of this method for the same object (implementing this class) with the same neighbourIndex argument. The elements of the returned array are always equal to -1, 0 or +1, and all they cannot be 0 simultaneously.

      This method defines some order of enumerating neighbours. This order can be different in different implementations. In BasicSkeletonPixelClassifier2D implementation, the order of neighbours is described by the following diagram: 

       0 1 2
 7 C 3
 6 5 4

      (the x-axis is directed rightward, the y-axis is directed downward). It means that the results of this method in BasicSkeletonPixelClassifier2D are the following: for neighbourIndex=0 it returns two-element array {-1,-1}, for neighbourIndex=1 it returns two-element array {0,-1}, for neighbourIndex=2 it returns two-element array {1,-1}, for neighbourIndex=3 it returns two-element array {1,0}, for neighbourIndex=4 it returns two-element array {1,1}, for neighbourIndex=5 it returns two-element array {0,1}, for neighbourIndex=6 it returns two-element array {-1,1}, for neighbourIndex=7 it returns two-element array {-1,0}. In other words, BasicSkeletonPixelClassifier2D class enumerates the neighbours along the perimeter of 3x3 square.

      This method is completely implemented via neighbourOffset(long[], int) method.

      Parameters:
      neighbourIndex - an index if the neighbour of some central element of a matrix.
      Returns:
      shifts along all coordinates from the central element to this neighbour.
      Throws:
      IndexOutOfBoundsException - if neighbourIndex is out of range 0..numberOfNeighbours()-1.
      See Also:

    • neighbourOffset

      public abstract void neighbourOffset(long[] coordinateIncrements, int neighbourIndex)
      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.

      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.
      Throws:
      NullPointerException - if coordinateIncrements argument is null.
      IllegalArgumentException - if coordinateIncrements.length!=dimCount().
      IndexOutOfBoundsException - if neighbourIndex is out of range 0..numberOfNeighbours()-1.
      See Also:

    • reverseNeighbourIndex

      public abstract int reverseNeighbourIndex(int neighbourIndex)
      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.

      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.
      Throws:
      IndexOutOfBoundsException - if neighbourIndex is out of range 0..numberOfNeighbours()-1.

    • asPixelTypes

      public abstract Matrix<? extends PIntegerArray> asPixelTypes(Matrix<? extends BitArray> skeleton, SkeletonPixelClassifier.AttachmentInformation attachmentInformation)
      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. TYPE_ZERO, if the corresponding element of the skeleton is zero (no pixel);
      2. 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. TYPE_USUAL_NODE, if the corresponding element of the skeleton is a node, where 3 or more branches meet;
      4. TYPE_ISOLATED, if the corresponding element of the skeleton is an isolated unit pixel, having no unit neighbour elements;
      5. TYPE_FREE_BRANCH_END, if the corresponding element of the skeleton is an end of some branch, having 1 unit neighbour elements;
      6. 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, 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 TYPE_USUAL_NODE, TYPE_ISOLATED and TYPE_FREE_BRANCH_END are adjacent integers -3..-1. Then, note that two constants, corresponding to branches and their ends — TYPE_FREE_BRANCH_END and TYPE_USUAL_BRANCH — are also adjacent integers -4..-3. Then, note that two constants, corresponding to nodes and isolated pixels — TYPE_USUAL_NODE and TYPE_ISOLATED — are also adjacent integers -2..-1. This can be useful for extracting special kinds of skeleton pixels into bit matrices.

      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.
      Throws:
      NullPointerException - if skeleton or attachmentInformation is null.
      IllegalArgumentException - if skeleton.dimCount()!=dimCount().

    • markNeighbouringNodesNotConnectedViaDegeneratedBranches

      public abstract void markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[] pixelTypesOfAllNeighbours)
      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 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 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.)
      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 TYPE_USUAL_NODE values in this array with Integer.MIN_VALUE.
      Throws:
      NullPointerException - if the argument is null.
      IllegalArgumentException - if the length of the passed array is less than numberOfNeighbours().