Package net.algart.matrices.skeletons

Class SkeletonScanner

java.lang.Object
net.algart.matrices.skeletons.SkeletonScanner
All Implemented Interfaces:
ArrayProcessor
public final class SkeletonScanner extends Object implements ArrayProcessor

Scanner of skeletons (bit matrices, generated by skeletonization algorithms), allowing to scan a skeleton, find and traverse all its structural elements like nodes and branches. This class works on the base of results of classifying skeleton pixels, performed by SkeletonPixelClassifier class, and requires an object of that class for creating an instance.

The nonoriented graph, formed by the skeleton

The base goal of this class is building and scanning the skeleton nonoriented graph, formed by nodes and branches of the given skeleton (bit matrix). Below is the formal definition of this graph for some n-dimensional skeleton bit matrix (or, briefly, skeleton) and some skeleton pixel classifier: an instance of SkeletonPixelClassifier class, used by this class (it is returned by pixelClassifier() method).

Let's define a pixel with integer coordinates (x, y, z,...) as a set of points of the n-dimensional space with such coordinates (x', y', z',...) that x−0.5≤x'≤x+0.5, y−0.5≤y'≤y+0.5, z−0.5≤z'≤z+0.5, ... In other words, pixel is a hypercube with the center (x, y, z,...) and the edge 1.0 (in 2-dimensional case, it is a square 1x1). Every unit element of the skeleton matrix with coordinates (x, y, z,...) corresponds to a pixel (x, y, z,...) in the n-dimensional Euclidean space.

The skeleton nonoriented graph is a set of n-dimensional points-nodes, connected by polylines-edges. Namely:

  1. The nodes of the graph are geometrical centers of all pixels of the skeleton, classified as nodes, free branch ends and isolated pixels by the current skeleton pixel classifier. Such types of nodes have correspondingly ≥3, 1 and 0 incident edges.
     
    Warning: nodes of the graph and node pixel type in the skeleton matrix are different concepts! Nodes of the graph are points of the n-dimensional Euclidean space, namely centers of pixels (centers of 1x1 squares in 2-dimensional case), while node pixel type describes matrix elements, corresponding to pixels in the space (1x1 squares in 2-dimensional case). And nodes of the graphs are formed not only by node pixel type, but also by free branch ends and isolated pixels.
     
  2. The edges of the graph are polylines E0E1...Em, m≥1, connecting some pairs of graph nodes E0 and Em. Every such edge consists of a sequences of segments Ei Ei+1 with length 1, √2, ... or √n, connecting geometrical centers of 2 pixels Ei and Ei+1, corresponding to 2 neighbouring unit matrix elements (in straight-and-diagonal connectivity terms, see below). Both ends E0 and Em of each edge are always nodes of the graph.
     
    The sequence of skeleton pixels, corresponding to points E1, E2, .., .Em−1, is also called a skeleton branch. In a case m=1, we also say that the nodes of the graph E0 and Em are connected with a degenerated 0-pixel skeleton branch (or, briefly, a degenerated branch).
     
  3. If an edge E0E1...Em consist of more than 1 segment (m≥2), then all points E1, E2, ..., Em−1 are geometrical centers of the pixels of the skeleton, classified as usual branch pixels or attachable branch ends by the current skeleton pixel classifier. Only the first and the last among points E1 and Em−1 can correspond to attachable branch ends (but also can be centers of usual branch pixels); all other points Ek, 2≤k≤m−2, always correspond to usual branch pixels.
     
    Every skeleton pixel, classified as a usual branch pixel or an attachable branch end by the current skeleton pixel classifier, is always an element of some skeleton branch, i.e. its center is a point Ek with 1≤k≤m−1 for some graph edge. There is the only exception from this rule, described below in the paragraph 7.
     
  4. If m≥3 and the point E1 corresponds to a pixel, classified as an attachable branch end, then E0 pixel is detected as the attached branch node A and E2 pixel is detected as an element of attaching branch B for this branch end E1 by the current skeleton pixel classifier — see comments to SkeletonPixelClassifier, section "Pixel types", group 5. In other words, the main classifying method SkeletonPixelClassifier.asPixelTypes returns for pixel E1 an index of its neighbour E0, when it is called in the mode NEIGHBOUR_INDEX_OF_ATTACHED_NODE, or an index of its neighbour E2, when it is called in the mode NEIGHBOUR_INDEX_OF_ATTACHING_BRANCH.
     
    Analogously, if m≥3 and the point Em−1 corresponds to a pixel, classified as an attachable branch end, then Em pixel is detected as the attached branch node A and Em−2 pixel is detected as an element of attaching branch B for this branch end Em−1 by the current skeleton pixel classifier.
     
  5. If m=2 and the only "internal" point E1 corresponds to a pixel, classified as an attachable branch end, then, for this branch end, either E0 pixel is detected as the attached branch node A and E2 pixel is detected as an element of attaching branch B, or E2 pixel is detected as the attached branch node A and E0 pixel is detected as an element of attaching branch B by the current skeleton pixel classifier — see comments to SkeletonPixelClassifier, section "Pixel types", group 5.
     
  6. In addition to the situations 4 and 5, this graph contains edges without "internal" points (m=1), corresponding to degenerated 0-pixel branches. Such edges connect:
    • any pairs of neighbouring graph nodes, where both nodes are the centers of pixels, classified as free branch ends (it is a very simple case of a short 2-pixel branch);
    • any pairs of neighbouring graph nodes, where one node is the center of a pixel, classified as a node, and another is the center of a pixel, classified as a free branch end;
    • any pairs of neighbouring graph nodes, where both nodes are the centers of pixels, classified as nodes, when the connecting them with a degenerated branch is not prohibited by SkeletonPixelClassifier.markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[]) method (and, so, when each from these 2 nodes appears in the list of neighbour indexes, returned by adjacentBranches() method for the second node).
       
  7. The skeleton can also contain specific kind of branches, called cyclic branches, consisting of usual branch pixels only and containing no nodes; such branches do not correspond to any elements of the graph and are recognized separately by this class.
     
  8. We can conclude from statements 1, 2 and 3, that each connected component of the skeleton, excepting cyclic branches, corresponds to a connected component of the graph, and vice versa.

All said above is correct only if the processed skeleton matrix does not contain "illegal" unit elements. If it contains them, the skeleton nonoriented graph can be partially incorrect.

It is easy to note, that this graph does not contain nodes with 2 incident edges and has no self-loops (though we could interpret the case 7 in this manner).

This class contains methods, allowing to scan this graph, i.e. to find all branches, incident with some node of the graph, i.e. node or free branch end pixel type, and to scan any branch from one its end (node of the graph) to another. Thus, you can use this class to vectorize a skeleton by transforming this graph into some geometrical vector model, consisting of points (nodes) and curves (lines connecting nodes). The main methods, which you need to use for full scanning the graph, are the following:

See comments to nextNodeOrBranch() about possible strategies of scanning, such as recursive depth-first search. See also comments to scanBranch(int, boolean, boolean) and scanBranchFromBranch(boolean, boolean) methods to understand, how to fully scan every branch. And see below a full example of breadth-first traversal algorithm.

Skeleton matrix, pixel classifier, current position

This class always processes some fixed bit matrix, which is called the scanned skeleton and can be retrieved by skeleton() method, and uses some fixed skeleton pixel classifier, which has the same number of dimensions and can be retrieved by pixelClassifier() method. Inside the scanned skeleton, this class always supports some current position: it is just some set of coordinates, which can be set by goTo(long...) or retrieved by currentCoordinates(). After creation or calling reset() method, this object is considered to be not positioned, that is the current position is considered to be not set yet and most methods throw IllegalStateException.

Remembering and lightweight skeleton scanners

In addition to storing the current position, this class may support storing information about visiting some pixels (probably in a form of an internal bit matrix, allocated while instantiation of this object). Instances of this class, that support storing this information, are called remembering skeleton scanners; instances, that do not support this, are called lightweight skeleton scanners.

Lightweight skeleton scanners do not occupy a lot of memory and can be created quickly, and their functionality is enough for scanning a concrete skeleton branch or for classifying all skeleton pixels by their types (asPixelTypes(SkeletonPixelClassifier.AttachmentInformation) method). But they do not allow to scan the nonoriented graph, formed by the skeleton, without additional efforts for storing visited nodes and branches in some external data structures.

Remembering skeleton scanners is what you should use in most cases. They allow to correctly build a nonoriented graph from nodes and branches, described above, while a single pass through the skeleton, for example, by a simple loop or by a breadth-first search, as shown in the example of usage below. The main feature of a remembering scanner is that it allocates additional memory (probably a bit matrix with the same sizes as the scanned skeleton), where it can store the fact of visiting some pixels by visit() and visitPreviousBranchPixel() methods, and this information is used by some other methods (see the following list of differences in behaviour of the methods).

You can find out, is a skeleton scanner lightweight or remembering, by isRemembering() method. Besides this, the following methods work differently in lightweight and remembering skeleton scanners:

Note, that in remembering scanners the only ways to mark some pixels as "visited" are explicit direct calls of the corresponding methods visit() and visitPreviousBranchPixel(). You should call these methods manually: this class does not try to mark pixels as "visited" indirectly, inside other methods, scanning the skeleton. The only exception from this is scanBranch / scanBranchFromBranch methods, which calls visitPreviousBranchPixel() when their withVisiting argument is true.

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

Note, that this class, as well as SkeletonPixelClassifier, 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 usage

Below is a complete example of code, using a remembering skeleton scanner ss for breadth-first traversal of the nonoriented graph, formed by the skeleton.

 while (ss.nextNodeOrBranch()) {
     ss.checkInterruption();
     ss.updateProgress();
     long saveBaseIndex = ss.currentIndexInArray();
     if (ss.isUsualBranch()) { // should check cyclic loops here
         ss.scanBranchFromBranch(true, false);
         boolean cyclicBranch = ss.isUsualBranch(); // in particular, not TYPE_ILLEGAL
         if (cyclicBranch) {
             assert ss.currentIndexInArray() == saveBaseIndex; // should return to the same position
             if (ss.firstStepFromBranch(true)) { // can be false if this pixel or its neighbour was visited
                 do {
                     // some processing the cyclic branch segment
                     // from ss.previousCoordinates() to ss.currentCoordinates()...
                     ss.visitPreviousBranchPixel();
                 } while (ss.nextStep());
             }
             continue;
         } // else we shall now start from the nearest node, but after all return to saveBaseIndex
     }

     if (ss.isNodeOrFreeBranchEnd() // necessary check: it is also possible an attached or illegal pixel
         && !ss.pixelVisitRemembered()) // for correct processing degenerated 0-pixel branches
     {
         Queue queue = new LinkedList();
         ss.visit();
         queue.add(ss.currentIndexInArray());
         while (!queue.isEmpty()) {
             long saveIndex = queue.poll();
             ss.goToIndexInArray(saveIndex);
             if (ss.isIllegal()) {
                 continue; // why not?
             }
             assert ss.isNodeOrFreeBranchEnd() : ss;
             int[] adjacentBranches = ss.isNode() ? ss.adjacentBranches() : new int[]{-1};
             for (int nb : adjacentBranches) {
                 ss.goToIndexInArray(saveIndex);
                 int dnb = nb == -1 ? ss.firstStepFromBranchNeighbourIndex(false) : nb;
                 boolean degeneratedBranch = ss.isNeighbourNodeOrFreeBranchEnd(dnb);
                 // Special case: we cannot mark 0-pixel degenerated branches between 2 neighbouring nodes
                 // as "visited", because they contain no internal pixels, and we can store visiting
                 // information in the remembering scanner for pixels only.
                 // However, we still need to process degenerated branches, and only 1 time for each branch.
                 // Let's scan such a branch if and only if the neighbour:
                 // 1) is not visited yet or
                 // 2) is inside the queue.
                 // Then every degenerated branch PQ will be processed strictly 1 time.
                 // Proof.
                 // Note that pixels are visited at the moment when they are added to the queue.
                 // Let's suppose that P appears the first in this loop (as the pixel at "saveIndex").
                 // At this moment, Q is either not visited, or added to the queue, but not removed
                 // from it yet (because P appears here before it). So, we'll really process PQ branch.
                 // On the other hand, when Q will appear in this loop (as the pixel at "saveIndex"),
                 // P will be already removed from the queue, so we'll not process PQ branch twice.
                 // This completes the proof.
                 if (degeneratedBranch && (
                     !ss.neighbourVisitRemembered(dnb) || queue.contains(ss.neighbourIndexInArray(dnb))))
                 {
                     // some processing the degenerated branch
                     // from ss.currentCoordinates() to ss.neighbourCoordinates(nb)...
                 }
                 if (!(nb == -1 ? ss.firstStepFromBranch(true) : ss.firstStep(nb, true))) {
                     continue;
                 }
                 if (!degeneratedBranch) {
                     do {
                         // some processing the branch segment
                         // from ss.previousCoordinates() to ss.currentCoordinates()...
                         ss.visitPreviousBranchPixel();
                     } while (ss.nextStep());
                 }
                 if (!ss.pixelVisitRemembered()) {
                     ss.visit();
                     queue.add(ss.currentIndexInArray());
                 }
             }
         }
     }
     ss.goToIndexInArray(saveBaseIndex);
 }

Of course, you can use another order of graph traversal, for example, depth-first. Note that some applications do not need depth-first or breadth-first order at all: it can be enough to find and detect nodes and edges in any order. In this case, you can just remove all operations with the queue.

Also note: you can process degenerated 0-pixel branches in a common way, just by assigning degeneratedBranch=false instead of calling isNeighbourNodeOrFreeBranchEnd method in the example above. In this case, breadth-first traversal algorithm will form slightly incorrect graph, namely, some degenerated branches will not be processed, and it can lead to appearing graph nodes with 2 incident edges (with low probability). However, the resulting graph will still be good enough, with connected components corresponding to connected components of the skeleton, maybe even better than the full correct graph with all degenerated branches in a role of edges.

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. You can create an instance of this class by the following basic methods:

and also by the following methods, designed for using 2-dimensional pixel classifier BasicSkeletonPixelClassifier2D:

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 is not thread-safe, but is thread-compatible and can be synchronized manually, if multithread access is necessary.

Author:
Daniel Alievsky
See Also: