public final class SkeletonScanner extends java.lang.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 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 ndimensional 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 ndimensional space with such coordinates
(x', y', z',...) that
coordinates
(x, y, z,...) corresponds to a pixel (x, y, z,...)
in the ndimensional Euclidean space.
The skeleton nonoriented graph is a set of ndimensional pointsnodes, connected by polylinesedges. Namely:
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.
node pixel type
in the skeleton matrix are different
concepts! Nodes of the graph are points of the ndimensional Euclidean space, namely centers of pixels
(centers of 1x1 squares in 2dimensional case), while node pixel type describes matrix elements,
corresponding to pixels in the space (1x1 squares in 2dimensional case).
And nodes of the graphs are formed not only by node pixel type, but also by
free branch ends
and
isolated pixels
.
usual branch pixels
or
attachable branch ends
by the current skeleton pixel classifier.
Only the first and the last among points E_{1} and E_{m−1}
can correspond to attachable branch ends (but also can be centers of usual branch pixels);
all other points E_{k}, 2≤k≤m−2,
always correspond to usual branch pixels.
attachable branch end
,
then E_{0} pixel is detected as the attached branch node A and
E_{2} pixel is detected as an element of attaching branch B
for this branch end E_{1} 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 E_{1} an index of its neighbour E_{0},
when it is called in the mode
NEIGHBOUR_INDEX_OF_ATTACHED_NODE
,
or an index of its neighbour E_{2},
when it is called in the mode
NEIGHBOUR_INDEX_OF_ATTACHING_BRANCH
.
attachable branch end
,
then E_{m} pixel is detected as the attached branch node A and
E_{m−2} pixel is detected as an element of attaching branch B
for this branch end E_{m−1} by the current skeleton pixel classifier.
attachable branch end
,
then, for this branch end,
either E_{0} pixel is detected as the attached branch node A and
E_{2} pixel is detected as an element of attaching branch B,
or E_{2} pixel is detected as the attached branch node A and
E_{0} 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.
free branch ends
(it is a very simple case of a short 2pixel branch);node
, and another is the center of a pixel, classified as
a free branch end
;nodes
,
when the connecting them with a degenerated branch is not prohibited by
SkeletonPixelClassifier.markNeighbouringNodesNotConnectedViaDegeneratedBranches(int[])
adjacentBranches()
method for the second node).
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.
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 selfloops (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:
nextNodeOrBranch()
— you should call this method to start scanning
the next part of the skeleton;firstStep(int, boolean)
— starts scanning a branch from
a node
(but not
a free branch end
);firstStepFromBranch(boolean)
— starts scanning a branch from a branch pixel
(including free branch end
);nextStep()
— continues scanning the current branch.See comments to nextNodeOrBranch()
about possible strategies of scanning, such as recursive
depthfirst 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 breadthfirst traversal algorithm.
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.
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 breadthfirst 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:
visit()
and visitPreviousBranchPixel()
do nothing;reset()
method
clears this information (makes all pixels "unvisited");pixelVisitRemembered()
and neighbourVisitRemembered(int)
always return false;visit()
or visitPreviousBranchPixel()
;firstStep(int, boolean)
, firstStepFromBranch(boolean)
,
scanBranch(int, boolean, boolean)
, scanBranchFromBranch(boolean, boolean)
methods,
as well as withVisiting argument of
scanBranch(int, boolean, boolean)
, scanBranchFromBranch(boolean, boolean)
methods
do not matter (as if they would be false);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.
Note, that this class, as well as SkeletonPixelClassifier
, supposes
the straightanddiagonal 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 (i_{k}−j_{k})=1
where
Below is a complete example of code, using a remembering skeleton scanner ss for breadthfirst 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()
) // necessary for correct processing degenerated 0pixel branches { Queuequeue = 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 0pixel 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, depthfirst. Note that some applications do not need depthfirst or breadthfirst 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 0pixel branches in a common way, just by assigning
degeneratedBranch=false instead of calling isNeighbourNodeOrFreeBranchEnd
method in the example above.
In this case, breadthfirst 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.
This class is designed for a case of any number of dimensions, though, of course, the most popular case is 2dimensional. You can create an instance of this class by the following basic methods:
getRememberingInstance(ArrayContext, Matrix, SkeletonPixelClassifier)
,getLightweightInstance(ArrayContext, Matrix, SkeletonPixelClassifier)
and also by the following methods, designed for using 2dimensional pixel classifier
BasicSkeletonPixelClassifier2D
:
getRememberingOctupleThinningInstance2D(ArrayContext, Matrix)
,getLightweightOctupleThinningInstance2D(ArrayContext, Matrix)
,getRememberingQuadruple3x5ThinningInstance2D(ArrayContext, Matrix)
,getLightweightQuadruple3x5ThinningInstance2D(ArrayContext, Matrix)
,getRememberingStrongQuadruple3x5ThinningInstance2D(ArrayContext, Matrix)
,getLightweightStrongQuadruple3x5ThinningInstance2D(ArrayContext, Matrix)
.This class supposes that the processed matrix is infinitely pseudocyclically 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)
Matrix.ContinuationMode.ZERO_CONSTANT
.
This class is not threadsafe, but is threadcompatible and can be synchronized manually, if multithread access is necessary.
AlgART Laboratory 2007–2014
SkeletonPixelClassifier
Modifier and Type  Method and Description 

int[] 
adjacentBranches()
On the assumption that the
current pixel is a node ,
returns indexes of all its neighbours, which are the starting pixels of branches, incident with this node. 
int 
adjacentBranches(int[] result)
More efficient version of
adjacentBranches() method, which stores the results
in the passed Java array instead of creating new Java array. 
Matrix<? extends PIntegerArray> 
asPixelTypes(SkeletonPixelClassifier.AttachmentInformation attachmentInformation)
Equivalent to
pixelClassifier() .asPixelTypes (skeleton() , attachmentInformation),
but probably works faster. 
void 
checkInterruption()

ArrayContext 
context()
Returns the current context used by this instance for some operations.

long[] 
currentCoordinates()
Returns the current coordinates (or throws IllegalStateException if the scanner
was not
positioned yet ). 
long 
currentIndexInArray()
Reduced and more efficient version of
currentCoordinates() , designed for indexing
elements of the builtin AlgART array of the skeleton matrix. 
int 
currentPixelTypeOrAttachedNode()
Returns the type of the current pixel of the skeleton matrix or, if it is an attachable branch end,
returns the index of its neighbour, which is a node, which is one of the ends of the branch.

int 
currentPixelTypeOrAttachingBranch()
Returns the type of the current pixel of the skeleton matrix or, if it is an attachable branch end,
returns the index of its neighbour, which lies at the branch, to which this pixel should be attached.

boolean 
currentPixelValue()
Returns the value of the element of the skeleton matrix at
the
current coordinates . 
int 
dimCount()
Equivalent to
skeleton() .dimCount() . 
boolean 
firstStep(int neighbourIndex,
boolean onlyToUnvisited)
On the assumption that the
current pixel is a
node or isolated pixel ,
checks whether we have a skeleton branch, originating at this node and going towards its neighbour
with the index neighbourIndex, and, if so, moves the current position to this neighbour and
returns true, if not, does nothing and returns false. 
boolean 
firstStepFromBranch(boolean onlyToUnvisited)
On the assumption that the
current pixel is
some branch pixel ,
moves the current position to a neighbour along this skeleton branch and returns true. 
int 
firstStepFromBranchNeighbourIndex(boolean onlyToUnvisited)
Returns the index of the neighbour, to which
firstStepFromBranch(boolean onlyToUnvisited) moves
when called with the same onlyToUnvisited argument. 
SkeletonScanner 
getCompatibleLightweightInstance()
Creates new instance of this class with the identical behaviour, excepting
that the returned object is always lightweight skeleton scanner (not remembering visits of pixels).

SkeletonScanner 
getCompatibleRememberingInstance()
Creates new instance of this class with the identical behaviour, excepting
that the returned object is always remembering skeleton scanner (remembering visits of pixels).

static SkeletonScanner 
getLightweightInstance(ArrayContext context,
Matrix<? extends BitArray> skeleton,
SkeletonPixelClassifier pixelClassifier)
Creates new remembering skeleton scanner, which will process the given skeleton matrix
on the base of the given pixel classifier.

static SkeletonScanner 
getLightweightOctupleThinningInstance2D(ArrayContext context,
Matrix<? extends BitArray> skeleton)
Creates new remembering skeleton scanner, which will process the given skeleton matrix,
supposed to be the final result of skeletonization by
OctupleThinningSkeleton2D algorithm. 
static SkeletonScanner 
getLightweightQuadruple3x5ThinningInstance2D(ArrayContext context,
Matrix<? extends BitArray> skeleton)
Creates new remembering skeleton scanner, which will process the given skeleton matrix,
supposed to be the final result of skeletonization by
Quadruple3x5ThinningSkeleton2D algorithm. 
static SkeletonScanner 
getLightweightStrongQuadruple3x5ThinningInstance2D(ArrayContext context,
Matrix<? extends BitArray> skeleton)
Creates new remembering skeleton scanner, which will process the given skeleton matrix,
supposed to be the final result of skeletonization by
StrongQuadruple3x5ThinningSkeleton2D algorithm. 
static SkeletonScanner 
getRememberingInstance(ArrayContext context,
Matrix<? extends BitArray> skeleton,
SkeletonPixelClassifier pixelClassifier)
Creates new remembering skeleton scanner, which will process the given skeleton matrix
on the base of the given pixel classifier.

static SkeletonScanner 
getRememberingOctupleThinningInstance2D(ArrayContext context,
Matrix<? extends BitArray> skeleton)
Creates new remembering skeleton scanner, which will process the given skeleton matrix,
supposed to be the final result of skeletonization by
OctupleThinningSkeleton2D algorithm. 
static SkeletonScanner 
getRememberingQuadruple3x5ThinningInstance2D(ArrayContext context,
Matrix<? extends BitArray> skeleton)
Creates new remembering skeleton scanner, which will process the given skeleton matrix,
supposed to be the final result of skeletonization by
Quadruple3x5ThinningSkeleton2D algorithm. 
static SkeletonScanner 
getRememberingStrongQuadruple3x5ThinningInstance2D(ArrayContext context,
Matrix<? extends BitArray> skeleton)
Creates new remembering skeleton scanner, which will process the given skeleton matrix,
supposed to be the final result of skeletonization by
StrongQuadruple3x5ThinningSkeleton2D algorithm. 
void 
goTo(long... newCurrentCoordinates)
Sets the current position in the skeleton matrix to the specified coordinates.

void 
goToIndexInArray(long newIndexInArray)
Reduced and more efficient version of
goTo(long...) , designed for indexing
elements of the builtin AlgART array of the skeleton matrix. 
void 
goToNeighbour(int neighbourIndex)
Moves the current position in the skeleton matrix to the given neighbour of the current element.

boolean 
isAttachableBranchEnd()
Returns true if the
current element of the skeleton
is 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. 
boolean 
isBranch()
Returns true if the
current element of the skeleton
is a branch element: usual
(where isUsualBranch()
returns true), free branch end
(where isFreeBranchEnd() returns true)
or attachable branch end
(where isAttachableBranchEnd()
returns true). 
boolean 
isFreeBranchEnd()
Returns true if the
current element of the skeleton
is a free branch end ,
i.e. a unit pixel having exactly 1 unit neighbour. 
boolean 
isIllegal()
Returns true if the
current element of the skeleton
is "illtegal ", i.e. a center of
an impossible configuration for a correct result of the given skeletonization algorithm. 
boolean 
isInitialized()
Returns true if and only if this instance was positioned to some coordinates in the skeleton matrix.

boolean 
isNeighbourNodeOrFreeBranchEnd(int neighbourIndex)
Returns true if the neighbour with the given index of
the
current element of the skeleton
is a node
or a free branch end . 
boolean 
isNode()
Returns true if the
current element of the skeleton
is a node , i.e. a unit element
where 3 or more thin connected 1pixel branches meet or, as a degenerated case,
an isolated pixel :
a unit element having no unit neighbours. 
boolean 
isNodeOrFreeBranchEnd()
Returns true if the
current element of the skeleton
is a node
(isNode() returns true)
or a free branch end
(isFreeBranchEnd() returns true). 
boolean 
isRemembering()
Returns true if this scanner is remembering or false if it is lightweight.

boolean 
isUsualBranch()
Returns true if the
current element of the skeleton
is a usual branch pixel ,
i.e. a unit pixel having exactly 2 unit neighbours. 
long[] 
neighbourCoordinates(int neighbourIndex)
Returns the coordinates of the element of the skeleton matrix, which is a neighbour with the given index
of the
current element . 
long 
neighbourIndexInArray(int neighbourIndex)
Reduced and more efficient version of
neighbourCoordinates(int) , designed for indexing
elements of the builtin AlgART array of the skeleton matrix. 
long 
neighbourOffsetInArray(int neighbourIndex)
Reduced and more efficient version of
neighbourOffset(int) method of the pixel classifier ,
designed for indexing elements of the builtin AlgART array of the skeleton matrix. 
int 
neighbourTypeOrAttachedNode(int neighbourIndex)
Returns the type of the pixel of the skeleton matrix, which is a neighbour with the given index
of the
current element , or, if it is an attachable branch end,
returns the index of a neighbour of this neighbour, which is a node, which is one of the ends of the branch. 
int 
neighbourTypeOrAttachingBranch(int neighbourIndex)
Returns the type of the pixel of the skeleton matrix, which is a neighbour with the given index
of the
current element , or, if it is an attachable branch end,
returns the index of a neighbour of this neighbour, which lies at the branch,
to which this neighbour should be attached. 
boolean 
neighbourValue(int neighbourIndex)
Returns the value of the element of the skeleton matrix, which is a neighbour with the given index
of the
current element . 
boolean 
neighbourVisitRemembered(int neighbourIndex)
Returns true if this scanner is
remembering and
the neighbour of the current element with the given index
was already visited by visit() or visitPreviousBranchPixel() method. 
boolean 
nextNodeOrBranch()
Finds the next unit element in the skeleton matrix (in natural order of elements) after
the
current position , the type of which is
node , isolated
or some branch pixel , and moves the current position to this element. 
java.lang.Integer 
nextNodeOrBranchPixelType()
Enhanced version of
nextNodeOrBranch() , which returns the type of the successfully found element
in the result or return null if the required element is not found. 
boolean 
nextStep()
Continues movement along the skeleton branch, started by
firstStep(int, boolean) or
firstStepFromBranch(boolean) method, and returns true,
if the end of the current branch is not reached yet, or does nothing and returns false
if we have reached the end of the branch (usually a node or
free branch end ). 
int 
numberOfNeighbours()
Equivalent to
pixelClassifier() .numberOfNeighbours() . 
SkeletonPixelClassifier 
pixelClassifier()
Returns a reference to the pixel classifier, used by this object.

boolean 
pixelVisitRemembered()
Returns true if this scanner is
remembering and
the current element was already visited by
visit() or visitPreviousBranchPixel() method. 
int 
previousBranchStepDirection()
Returns an index of the neighbour, towards which the current position was moved
by the previous change of the current position via
firstStep(int, boolean) , firstStepFromBranch(boolean) or nextStep() method,
or 1 if the previous change of the current position was performed by some other method
like goTo(long...) or nextNodeOrBranch() . 
long[] 
previousCoordinates()
Returns the coordinates of the neighbour of the current element, which was current before the last change
of the current position, if this change was performed via
firstStep(int, boolean) , firstStepFromBranch(boolean) or nextStep() method,
or throws IllegalStateException if the previous change of the current position was performed
by some other method like goTo(long...) or nextNodeOrBranch() . 
long 
previousIndexInArray()
Reduced and more efficient version of
previousCoordinates() , designed for indexing
elements of the builtin AlgART array of the skeleton matrix. 
void 
reset()
Clears the state of this scanner: resets the current position to
not positioned state
and, in remembering scanners, resets the state of all pixels to
unvisited . 
void 
scanBranch(int neighbourIndex,
boolean onlyToUnvisited,
boolean withVisiting)
On the assumption that the
current pixel is a
node or isolated pixel ,
completely scans the branch, originating at this node and going towards its neighbour with the given index. 
void 
scanBranchFromBranch(boolean onlyToUnvisited,
boolean withVisiting)
On the assumption that the
current pixel is
some branch pixel ,
scans the part of this branch towards one of the sides of the current pixel. 
Matrix<? extends BitArray> 
skeleton()
Returns a reference to the skeleton, scanned by this object.

java.lang.String 
toString()
Returns a brief string description of this object.

void 
updateProgress()
Calls
context() .updateProgress(event)
with an event, created by the following operator:
currentIndexInArray() , skeleton() .size() )context() ==null. 
void 
visit()
In
remembering scanners,
marks the current element of the skeleton matrix as "visited". 
void 
visitPreviousBranchPixel()
In
remembering scanners,
marks the previous visited element of the skeleton matrix as "visited". 
public static SkeletonScanner getRememberingInstance(ArrayContext context, Matrix<? extends BitArray> skeleton, SkeletonPixelClassifier pixelClassifier)
comments to this class
about remembering and lightweight skeleton scanners.
The passed matrix is supposed to be a final result of some skeletonization algorithm, for example,
provided by this package. If it is not so, the passed pixel classifier scanner will probably consider many
unit pixels of this matrix as "illegal
", so
the branches and nodes found by this class will not form a correct skeletal graph.
The same situation is also possible if the passed pixel classifier does not match the algorithm,
used for skeletonization.
context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.pixelClassifier
 the pixel classifier
, which will be used by this scanner
for detecting types of all pixels.java.lang.NullPointerException
 if matrix or pixelClassifier argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=pixelClassifier.dimCount()
.public static SkeletonScanner getRememberingOctupleThinningInstance2D(ArrayContext context, Matrix<? extends BitArray> skeleton)
OctupleThinningSkeleton2D
algorithm.
Equivalent togetRememberingInstance
(context, skeleton,
BasicSkeletonPixelClassifier2D.getOctupleThinningInstance()
).context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.java.lang.NullPointerException
 if matrix argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=2.public static SkeletonScanner getRememberingQuadruple3x5ThinningInstance2D(ArrayContext context, Matrix<? extends BitArray> skeleton)
Quadruple3x5ThinningSkeleton2D
algorithm.
Equivalent togetRememberingInstance
(context, skeleton,
BasicSkeletonPixelClassifier2D.getQuadruple3x5ThinningInstance()
).context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.java.lang.NullPointerException
 if matrix argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=2.public static SkeletonScanner getRememberingStrongQuadruple3x5ThinningInstance2D(ArrayContext context, Matrix<? extends BitArray> skeleton)
StrongQuadruple3x5ThinningSkeleton2D
algorithm.
Equivalent togetRememberingInstance
(context, skeleton,
BasicSkeletonPixelClassifier2D.getStrongQuadruple3x5ThinningInstance()
).context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.java.lang.NullPointerException
 if matrix argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=2.public static SkeletonScanner getLightweightInstance(ArrayContext context, Matrix<? extends BitArray> skeleton, SkeletonPixelClassifier pixelClassifier)
comments to this class
about remembering and lightweight skeleton scanners.
The passed matrix is supposed to be a final result of some skeletonization algorithm, for example,
provided by this package. If it is not so, the passed pixel classifier scanner will probably consider many
unit pixels of this matrix as "illegal
", so
the branches and nodes found by this class will not form a correct skeletal graph.
The same situation is also possible if the passed pixel classifier does not match the algorithm,
used for skeletonization.
context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.pixelClassifier
 the pixel classifier
, which will be used by this scanner
for detecting types of all pixels.java.lang.NullPointerException
 if matrix or pixelClassifier argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=pixelClassifier.dimCount()
.public static SkeletonScanner getLightweightOctupleThinningInstance2D(ArrayContext context, Matrix<? extends BitArray> skeleton)
OctupleThinningSkeleton2D
algorithm.
Equivalent togetLightweightInstance
(context, skeleton,
BasicSkeletonPixelClassifier2D.getOctupleThinningInstance()
).context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.java.lang.NullPointerException
 if matrix argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=2.public static SkeletonScanner getLightweightQuadruple3x5ThinningInstance2D(ArrayContext context, Matrix<? extends BitArray> skeleton)
Quadruple3x5ThinningSkeleton2D
algorithm.
Equivalent togetLightweightInstance
(context, skeleton,
BasicSkeletonPixelClassifier2D.getQuadruple3x5ThinningInstance()
).context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.java.lang.NullPointerException
 if matrix argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=2.public static SkeletonScanner getLightweightStrongQuadruple3x5ThinningInstance2D(ArrayContext context, Matrix<? extends BitArray> skeleton)
StrongQuadruple3x5ThinningSkeleton2D
algorithm.
Equivalent togetLightweightInstance
(context, skeleton,
BasicSkeletonPixelClassifier2D.getStrongQuadruple3x5ThinningInstance()
).context
 the context
that will be used by this object;
may be null, then it will be ignored.skeleton
 the skeleton
: a bit matrix that should be processed by this scanner.java.lang.NullPointerException
 if matrix argument is null.java.lang.IllegalArgumentException
 if skeleton.dimCount()
!=2.public ArrayContext context()
scanBranch(int, boolean, boolean)
and
scanBranchFromBranch(boolean, boolean)
methods.context
in interface ArrayProcessor
public SkeletonScanner getCompatibleRememberingInstance()
comments to this class
about remembering and lightweight skeleton scanners.
The returned scanner is always newly created instance (in particular,
not positioned
), even if this instance is remembering.
So, this method usually leads to allocating necessary amount of memory.
public SkeletonScanner getCompatibleLightweightInstance()
comments to this class
about remembering and lightweight skeleton scanners.
The returned scanner is always newly created instance (in particular,
not positioned
), even if this instance is lightweight.
public Matrix<? extends BitArray> skeleton()
public SkeletonPixelClassifier pixelClassifier()
public int dimCount()
public int numberOfNeighbours()
pixelClassifier()
.numberOfNeighbours()
.public long neighbourOffsetInArray(int neighbourIndex)
neighbourOffset(int)
method of the pixel classifier
,
designed for indexing elements of the builtin AlgART array
of the skeleton matrix.
This method is equivalent to
skeleton()
.pseudoCyclicIndex
(pixelClassifier()
.neighbourOffset
(neighbourIndex))neighbourIndex
 an index if the neighbour of some central element of the matrix.public Matrix<? extends PIntegerArray> asPixelTypes(SkeletonPixelClassifier.AttachmentInformation attachmentInformation)
pixelClassifier()
.asPixelTypes
(skeleton()
, attachmentInformation),
but probably works faster.attachmentInformation
 what should this method return for attachable pixels.scanned skeleton matrix
, describing the types of all skeleton pixels.java.lang.NullPointerException
 if attachmentInformation is null.public boolean isInitialized()
nextNodeOrBranch()
, nextNodeOrBranchPixelType()
,
goTo(long...)
, goToIndexInArray(long)
methods were called yet,
or true in all other cases.
If this object is not positioned, most of methods, processing pixels in the current position,
throw IllegalStateException.nextNodeOrBranch()
/ nextNodeOrBranchPixelType()
or goTo(long...)
/ goToIndexInArray(long)
methods.public long[] currentCoordinates()
positioned yet
).
The returned array is always a newly allocated Java array.
Its length is always equal to dimCount()
.
The returned coordinates are always in ranges
0 ≤ result[k] <where result[k] is the element #k in the returned array.skeleton()
.dim
(k),
java.lang.IllegalStateException
 if this scanner was not positioned yet
.goTo(long...)
,
currentIndexInArray()
public long currentIndexInArray()
currentCoordinates()
, designed for indexing
elements of the builtin AlgART array
of the skeleton matrix.
This method is equivalent to
skeleton()
.index
(currentCoordinates()
)currentCoordinates()
calculates results on the base on this value.
The result of this method is always in range
0..skeleton()
.size()
1.
java.lang.IllegalStateException
 if this scanner was not positioned yet
.goToIndexInArray(long)
public boolean currentPixelValue()
current coordinates
.
Equivalent to skeleton()()
.array()
.getBit
(currentIndexInArray()
)java.lang.IllegalStateException
 if this scanner was not positioned yet
.public int currentPixelTypeOrAttachingBranch()
array()
.getInt
(currentIndexInArray()
)m =but probably works faster. See comments toasPixelTypes
(SkeletonPixelClassifier.AttachmentInformation.NEIGHBOUR_INDEX_OF_ATTACHING_BRANCH
)
asPixelTypes
method for more details.java.lang.IllegalStateException
 if this scanner was not positioned yet
.currentPixelTypeOrAttachedNode()
,
neighbourTypeOrAttachingBranch(int)
,
neighbourTypeOrAttachedNode(int)
public int currentPixelTypeOrAttachedNode()
array()
.getInt
(currentIndexInArray()
)m =but probably works faster. See comments toasPixelTypes
(SkeletonPixelClassifier.AttachmentInformation.NEIGHBOUR_INDEX_OF_ATTACHED_NODE
)
asPixelTypes
method for more details.java.lang.IllegalStateException
 if this scanner was not positioned yet
.currentPixelTypeOrAttachingBranch()
,
neighbourTypeOrAttachingBranch(int)
,
neighbourTypeOrAttachedNode(int)
public long[] neighbourCoordinates(int neighbourIndex)
current element
.
Equivalent to skeleton()
.coordinates
(index, null)index = (Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates. This situation is processed according to the model of infinite pseudocyclical continuation — see the end of thecurrentIndexInArray()
+neighbourOffsetInArray
(neighbourIndex)) %skeleton()
.size()
comments to this class
.
The returned array is always a newly allocated Java array.
Its length is always equal to dimCount()
.
The returned coordinates are always in ranges
0 ≤ result[k] <where result[k] is the element #k in the returned array.skeleton()
.dim
(k),
neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.goTo(long...)
,
neighbourIndexInArray(int)
public long neighbourIndexInArray(int neighbourIndex)
neighbourCoordinates(int)
, designed for indexing
elements of the builtin AlgART array
of the skeleton matrix.
Equivalent to
(Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates. This situation is processed according to the model of infinite pseudocyclical continuation — see the end of thecurrentIndexInArray()
+neighbourOffsetInArray
(neighbourIndex)) %skeleton()
.size()
comments to this class
.
The result of this method is always in range
0..skeleton()
.size()
1.
neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.goToIndexInArray(long)
public boolean neighbourValue(int neighbourIndex)
current element
.
Equivalent to skeleton()
.array()
.getBit
(index)index = (Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates. This situation is processed according to the model of infinite pseudocyclical continuation — see the end of thecurrentIndexInArray()
+neighbourOffsetInArray
(neighbourIndex)) %skeleton()
.size()
comments to this class
.neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public int neighbourTypeOrAttachingBranch(int neighbourIndex)
current element
, or, if it is an attachable branch end,
returns the index of a neighbour of this neighbour, which lies at the branch,
to which this neighbour should be attached.
Equivalent to array()
.getInt
(index)m =Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates. This situation is processed according to the model of infinite pseudocyclical continuation — see the end of theasPixelTypes
(SkeletonPixelClassifier.AttachmentInformation.NEIGHBOUR_INDEX_OF_ATTACHING_BRANCH
) index = (currentIndexInArray()
+neighbourOffsetInArray
(neighbourIndex)) %skeleton()
.size()
comments to this class
.neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.currentPixelTypeOrAttachingBranch()
,
currentPixelTypeOrAttachedNode()
,
neighbourTypeOrAttachedNode(int)
public int neighbourTypeOrAttachedNode(int neighbourIndex)
current element
, or, if it is an attachable branch end,
returns the index of a neighbour of this neighbour, which is a node, which is one of the ends of the branch.
Equivalent to array()
.getInt
(index)m =Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates. This situation is processed according to the model of infinite pseudocyclical continuation — see the end of theasPixelTypes
(SkeletonPixelClassifier.AttachmentInformation.NEIGHBOUR_INDEX_OF_ATTACHED_NODE
) index = (currentIndexInArray()
+neighbourOffsetInArray
(neighbourIndex)) %skeleton()
.size()
comments to this class
.neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.currentPixelTypeOrAttachingBranch()
,
currentPixelTypeOrAttachedNode()
,
neighbourTypeOrAttachingBranch(int)
public boolean isNode()
current element
of the skeleton
is a node
, i.e. a unit element
where 3 or more thin connected 1pixel branches meet or, as a degenerated case,
an isolated pixel
:
a unit element having no unit neighbours.
Equivalent both to SkeletonPixelClassifier.isNodePixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isNodePixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is a node,
including the degenerated case of an isolated pixel.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isUsualBranch()
current element
of the skeleton
is a usual branch pixel
,
i.e. a unit pixel having exactly 2 unit neighbours.
Equivalent both to SkeletonPixelClassifier.isUsualBranchPixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isUsualBranchPixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is
a usual (nonending) branch pixel.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isFreeBranchEnd()
current element
of the skeleton
is a free branch end
,
i.e. a unit pixel having exactly 1 unit neighbour.
Equivalent both to SkeletonPixelClassifier.isFreeBranchEndPixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isFreeBranchEndPixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is
a free branch end.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isAttachableBranchEnd()
current element
of the skeleton
is 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 both to SkeletonPixelClassifier.isAttachableBranchEndPixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isAttachableBranchEndPixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is
an attachable branch end.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isNodeOrFreeBranchEnd()
current element
of the skeleton
is a node
(isNode()
returns true)
or a free branch end
(isFreeBranchEnd()
returns true).
Equivalent both to SkeletonPixelClassifier.isNodeOrFreeBranchEndPixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isNodeOrFreeBranchEndPixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is
a node or a free branch end.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isBranch()
current element
of the skeleton
is a branch element: usual
(where isUsualBranch()
returns true), free branch end
(where isFreeBranchEnd()
returns true)
or attachable branch end
(where isAttachableBranchEnd()
returns true).
Equivalent both to SkeletonPixelClassifier.isBranchPixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isBranchPixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is
some element of a branch.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isIllegal()
current element
of the skeleton
is "illtegal
", i.e. a center of
an impossible configuration for a correct result of the given skeletonization algorithm.
Equivalent both to SkeletonPixelClassifier.isIllegalPixelType
(currentPixelTypeOrAttachingBranch()
)
and to SkeletonPixelClassifier.isIllegalPixelType
(currentPixelTypeOrAttachedNode()
).current element
of the skeleton is
a part of pixel configuration which is incorrect for the given type of skeleton.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean isNeighbourNodeOrFreeBranchEnd(int neighbourIndex)
current element
of the skeleton
is a node
or a free branch end
.
Equivalent both to SkeletonPixelClassifier.isNodeOrFreeBranchEndPixelType
(neighbourTypeOrAttachingBranch(neighbourIndex)
)
and to SkeletonPixelClassifier.isNodeOrFreeBranchEndPixelType
(neighbourTypeOrAttachedNode(neighbourIndex)
).
This method is helpful when isNodeOrFreeBranchEnd()
method returns true,
i.e. the current position is a node or a free branch end (and corresponds to a node in the nonoriented graph,
formed by the skeleton), and we need to check, is it connected via a degenerated 0pixel branch with
a possible neighbouring node or free branch end (also corresponding to a node in the nonoriented graph).
It is necessary in algorithms which process degenerated 0pixel branches in some special way,
like an algorithm, given in the comments to this class
.
neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public void goTo(long... newCurrentCoordinates)
In simple applications, you do not need this method: it is enough to implement a loop of calls of
nextNodeOrBranch()
method.
newCurrentCoordinates
 new current coordinates: the currentCoordinates()
method will return
an identical array after this call.java.lang.NullPointerException
 if newCurrentCoordinates argument is null.java.lang.IllegalArgumentException
 if the length of newCurrentCoordinates array is not equal to
dimCount()
.java.lang.IndexOutOfBoundsException
 if one of new coordinates newCurrentCoordinates[k]
is out of range 0..skeleton()
.dim
(k)1.currentCoordinates()
,
goToIndexInArray(long)
public void goToIndexInArray(long newIndexInArray)
goTo(long...)
, designed for indexing
elements of the builtin AlgART array
of the skeleton matrix.
This method is equivalent to
goto
(skeleton()
.coordinates
(newIndexInArray, null))newIndexInArray
 new current index in the builtin AlgART array of the skeleton matrix.java.lang.IndexOutOfBoundsException
 if newIndexInArray is out of range
0..skeleton()
.size()
1.currentIndexInArray()
public void goToNeighbour(int neighbourIndex)
pixelClassifier()
.neighbourOffset(int)
goToIndexInArray(index)
index = (Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates. This situation is processed according to the model of infinite pseudocyclical continuation — see the end of thecurrentIndexInArray()
+neighbourOffsetInArray
(neighbourIndex)) %skeleton()
.size()
comments to this class
.neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean nextNodeOrBranch()
current position
, the type of which is
node
, isolated
or some branch pixel
, and moves the current position to this element.
If this scanner was not positioned yet
, finds the first such element.
Returns true if this method has successfully found the required element, or false
if there is no required position, i.e. if the matrix scanning is finished. In the second case,
the current position is not changed.
More precisely, this method finds the minimal k, so that
isInitialized()
? 0 : currentIndexInArray()
+1)asPixelTypes(...)
.array()
.getInt
(k)TYPE_ZERO
or
TYPE_ILLEGAL
(the argument of
asPixelTypes
is not important here).If this index k exists, this method performs
goToIndexInArray
(k)
Note, that if this scanner was not positioned yet
, it becomes positioned
if this method returns true, but stays not positioned if it returns false.
After successful call of this method, you can be sure that the current position corresponds:
node
or, maybe,
isolated pixel
(as a degenerated case of the node),free branch end
).In the first case, i.e. if isNode()
, you can find all branches, originating at this node,
by adjacentBranches()
method, which returns indexes of all corresponding neighbours.
Then you can scan all these branches in a loop, starting the scanning of each branch by
firstStep(int neighbourIndex, boolean onlyToUnvisited)
method, where neighbourIndex is an element of the array — result of adjacentBranches()
.
If necessary, you can scan each branch until its end by a loop of nextStep()
calls,
like in scanBranch(int, boolean, boolean)
node
again, for example,
recursively process this node in the same manner (that means deapthfirst graph traversal).
Note, that the recursion should be used only
if you remember all visited nodes (to avoid infinite recursion), for example, by using
a remembering
scanner with the argument onlyToUnvisited=true.
Also note, that even remembering scanner does not allow to remember a fact of visiting
degenerated 0pixel branches: you should keep this in mind and process degenerated branches,
if necessary, by some other mechanism.
In the second case, i.e. if isBranch()
, you should start scanning the found branch by
firstStepFromBranch(boolean onlyToUnvisited)
method. But here it is important to distinguish two situations:
free branch end
and all other variants (usual branch elements and attachable branch ends).
The first situation is similar to the first case (a node): it is a node of the skeleton
nonoriented graph (see the comments to this class
), having only one incident edge (branch).
In the second situation, you can try to move to some node
/ free branch end
(one of 2 ends of this branch),
for example, by scanBranchFromBranch
method with
withVisiting=false argument, but you should remember, that it can be also a cyclic branch
(the case 7 in the comments to this class
). This case can be identified
via the current pixel type after scanBranchFromBranch
call:
it will be usual branch pixel
only in a case of a cyclic branch.
Generally speaking, we do not recommend using Java recursion for graph traversal, because the internal JVM stack can be not enough for processing complex skeletons. Another approach is using breadthfirst algorithm, based on some form of queue.
A full example of implementation of the breadthfirst algorithm,
with correct processing degenerated 0pixel branches and cyclic branches,
is given in the comments to this class
.
nextNodeOrBranchPixelType()
public java.lang.Integer nextNodeOrBranchPixelType()
nextNodeOrBranch()
, which returns the type of the successfully found element
in the result or return null if the required element is not found.
More precisely, it is equivalent to
nextNodeOrBranch()
? Integer.valueOf(currentPixelTypeOrAttachedNode()
) : null
public int[] adjacentBranches() throws java.lang.IllegalStateException
current pixel
is a node
,
returns indexes of all its neighbours, which are the starting pixels of branches, incident with this node.
In particular, if some of neighbours of this node are also nodes, this method detects and returns
in the result the indexes of such from them, which are connected with this node by degenerated
branches (consisting of 0 pixels).
If the current pixel is not a node (or isolated pixel), this method throws IllegalStateException.
More precisely, the neighbour index k is an element of the returned array, if and only if:
firstStep
(k,false) call, performed at this position,
would be successful (would return true and successfully move the position to that neighbour);node
,
this neighbour is not marked (set to Integer.MIN_VALUE) by
pixelClassifier()
.markNeighbouringNodesNotConnectedViaDegeneratedBranches
The returned array is always a newly allocated Java array.
Its length is always not greater than numberOfNeighbours()
;
it can be also empty, if the current element is an isolated pixel
.
The returned indexes specify neighbours in terms of
pixelClassifier()
.neighbourOffset(int)
adjacentBranches(int[])
method.
java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isNode()
.public int adjacentBranches(int[] result) throws java.lang.IllegalStateException
adjacentBranches()
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
the beginning of result Java array, but does not allocate any arrays.
It is a better solution if we need to calculate adjacent branches in a long loop,
because allows to avoid allocating a lot of short arrays.
The length of the passed array must be greater than or equal to numberOfNeighbours()
.
result
 Java array for storing the results.java.lang.NullPointerException
 if result argument is null.java.lang.IllegalArgumentException
 if result.length<numberOfNeighbours()
.java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isNode()
.public boolean firstStep(int neighbourIndex, boolean onlyToUnvisited) throws java.lang.IllegalStateException
current pixel
is a
node or isolated pixel
,
checks whether we have a skeleton branch, originating at this node and going towards its neighbour
with the index neighbourIndex, and, if so, moves the current position to this neighbour and
returns true, if not, does nothing and returns false.
The neighbour index is specified in terms of
pixelClassifier()
.neighbourOffset(int)
nextStep()
calls:
see an example in comments to scanBranch
method.
Warning: unlike adjacentBranches()
and in violation of the definition of the nonoriented graph,
formed by the skeleton, this method works as if every neighbouring node (when such nodes exist)
is connected with this one via a degenerated 0pixel branch.
So, you should use it together with adjacentBranches()
.
More precisely, this method checks the type of the given neighbour:
neighbourTypeOrAttachingBranch(neighbourIndex)
.
node
,
this method always moves the current position to that node and returns true
(it can lead to extra degenerated branches, but you can use adjacentBranches()
method
to avoid this);usual branch element
or a free branch end
,
this method moves the current position to this neighbour and returns true.attachable branch end
, this method checks its attached node A (returned by
neighbourTypeOrAttachedNode(neighbourIndex)
)neighbourTypeOrAttachingBranch(neighbourIndex)
)comments to SkeletonPixelClassifier
.
If one of pixels A or B is the current node, this method moves the current position to
this neighbour and returns true, in other case if does nothing and returns false.illegal
" unit element),
this method does nothing and returns false.The rules, listed above, are used as described if the argument onlyToUnvisited is false.
If it is true and if this scanner is remembering
, this method also checks,
whether the given neighbour was already visited, i.e. checks the result of
neighbourVisitRemembered(neighbourIndex)
Note, that even if this scanner is remembering
, this method does not store
information about visiting pixels. If you want, you should do this manually by
visitPreviousBranchPixel()
method.
Note, that we allow a situation when the neighbouring elements are out of ranges of the matrix coordinates.
This situation is processed according to the model of infinite pseudocyclical continuation —
see the end of the comments to this class
.
neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
onlyToUnvisited
 whether this method should go only to neighbours, which were never be visited before
(this argument affects only if this scanner is remembering
).java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isNode()
.java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.scanBranch(int, boolean, boolean)
public boolean firstStepFromBranch(boolean onlyToUnvisited) throws java.lang.IllegalStateException
current pixel
is
some branch pixel
,
moves the current position to a neighbour along this skeleton branch and returns true.
If the current pixel is not a branch pixel, this method throws IllegalStateException.
In a case of success (this method successfully changes the position and returns true),
the previous current position is internally stored: it will be used in nextStep()
method
to finish scanning a cyclic branch.
The movement along the branch, started by this method, can be continued by a loop of nextStep()
calls:
see an example in comments to scanBranchFromBranch
method.
More precisely:
free branch end
,
this method moves the current position to its only unit neighbour Q;usual branch element
,
this method moves the current position to some of 2 its unit neighbours
Q_{1} and Q_{2};attachable branch end
,
this method moves the current position to some of 2 its neighbours
Q_{1} and Q_{2}, indexes of which
are returned by currentPixelTypeOrAttachingBranch()
and
currentPixelTypeOrAttachedNode()
methods.The rules, listed above, are used as described if the argument onlyToUnvisited is false.
If it is true and if this scanner is remembering
, this method also checks,
whether the neighbours were already visited, i.e. checks the result of
neighbourVisitRemembered(...)
Note, that even if this scanner is remembering
, this method does not store
information about visiting pixels. If you want, you should do this manually by
visitPreviousBranchPixel()
method.
Note, that it is undocumented, which of two neighbours Q_{1} and Q_{2} is selected in cases 2 and 3 (if one of them is not disabled because onlyToUnvisited=true and it was already visited).
Note, that we allow a situation when the neighbouring elements are out of ranges of the matrix coordinates.
This situation is processed according to the model of infinite pseudocyclical continuation —
see the end of the comments to this class
.
This method is implemented in the following way:
int nextNeighbourIndex =firstStepFromBranchNeighbourIndex
(onlyToUnvisited); if (nextNeighbourIndex == 1) { return false; } this.startIndexInArray =currentIndexInArray()
; //  an internal field; it will be used innextStep()
to finish scanning a cyclic branchgoToNeighbour
(nextNeighbourIndex); this.previousBranchStepDirection = nextNeighbourIndex; //  an internal field, returned bypreviousBranchStepDirection()
method return true;
onlyToUnvisited
 whether this method should go only to neighbours, which were never be visited before
(this argument affects only if this scanner is remembering
).java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isBranch()
.scanBranchFromBranch(boolean, boolean)
public int firstStepFromBranchNeighbourIndex(boolean onlyToUnvisited) throws java.lang.IllegalStateException
firstStepFromBranch(boolean onlyToUnvisited)
moves
when called with the same onlyToUnvisited argument.
If that method returns false and does not move anywhere, this method returns 1.
If that method throws IllegalStateException, this method also throws this exception.
Unlike firstStepFromBranch(boolean)
, this method does not change anything in the internal state
of the object.
See comments to firstStepFromBranch(boolean)
method for more details.
onlyToUnvisited
 whether this method should check only neighbours, which were never be visited before
(this argument affects only if this scanner is remembering
).firstStepFromBranch(boolean)
will move if it will be called.java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isBranch()
.public boolean nextStep() throws java.lang.IllegalStateException
firstStep(int, boolean)
or
firstStepFromBranch(boolean)
method, and returns true,
if the end of the current branch is not reached yet, or does nothing and returns false
if we have reached the end of the branch (usually a node
or
free branch end
).
This method may be called only if the previous change of the current position was performed
by firstStep(int, boolean)
, firstStepFromBranch(boolean)
or this method.
In other case (for example, if the last change of the current position was performed by goTo(long...)
or nextNodeOrBranch()
), this method throws IllegalStateException.
More precisely:
firstStepFromBranch(boolean)
call, this method does nothing and returns false
(it means that we've finished scanning of this cyclic branch and returned to the original position);free branch end
,
this method does nothing and returns false
(it means that we've reached the free end of this branch);usual branch element
,
this method moves the current position to that from its 2 unit neighbours
Q_{1} and Q_{2},
which was not current before the previous change of the current position via
firstStep(int, boolean)
, firstStepFromBranch(boolean)
or this method,
and returns true;attachable branch end
,
this method finds 2 its neighbours Q_{1} and Q_{2}, indexes of which
are returned by currentPixelTypeOrAttachingBranch()
and
currentPixelTypeOrAttachedNode()
methods,
and moves the current position to that from Q_{1} and Q_{2},
which was not current before the previous change of the current position via
firstStep(int, boolean)
, firstStepFromBranch(boolean)
or this method,
and returns true;node
or an
"illegal
" pixel, this method does nothing
and returns false (it means that we've reached the node at the end of this branch
or we cannot continue scanning because this pixel cannot belong to a correct skeleton);zero
,
this method throws IllegalStateException.Note, that this method does not use information about possible previous visits of the pixels, probably
remembered if this scanner is remembering
.
Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates.
This situation is processed according to the model of infinite pseudocyclical continuation —
see the end of the comments to this class
.
java.lang.IllegalStateException
 if this scanner was not positioned yet
,
or if the previous change of the current position was performed not by
this method and not by firstStep(int, boolean)
or
firstStepFromBranch(boolean)
.public void scanBranch(int neighbourIndex, boolean onlyToUnvisited, boolean withVisiting) throws java.lang.IllegalStateException
current pixel
is a
node or isolated pixel
,
completely scans the branch, originating at this node and going towards its neighbour with the given index.
If onlyToUnvisited argument is true, this method does not try to scan a branch,
the first pixel of which was already visited.
If withVisiting argument is true, this method marks all visited and left pixels
(including the starting node, but excluding the finish pixel) by visitPreviousBranchPixel()
method.
Both arguments onlyToUnvisited and withVisiting have no effect if this
scanner is not remembering
.
More precisely, this method is equivalent to the following code:
if (with the only addition that this method also callsfirstStep
(neighbourIndex, onlyToUnvisited)) { do { if (withVisiting) {visitPreviousBranchPixel()
; } } while (nextStep()
); }
context()
.checkInterruption()
method from time to time (if context()
!=nullneighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
onlyToUnvisited
 whether this method should go only to neighbours, which were never be visited before
(this argument affects only if this scanner is remembering
).withVisiting
 whether this method should call visitPreviousBranchPixel()
after each step
(this argument affects only if this scanner is remembering
).java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isNode()
.java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.public void scanBranchFromBranch(boolean onlyToUnvisited, boolean withVisiting) throws java.lang.IllegalStateException
current pixel
is
some branch pixel
,
scans the part of this branch towards one of the sides of the current pixel.
If the current pixel is a free branch end
or if this branch is cyclic (consists of usual branch pixels
only), this method completely scans whole this branch.
If onlyToUnvisited argument is true, this method does not try to scan a branch,
if the first scanned pixel was already visited.
If withVisiting argument is true, this method marks all visited and left pixels
(including the starting pixel, but excluding the finish one) by visitPreviousBranchPixel()
method.
Both arguments onlyToUnvisited and withVisiting have no effect if this
scanner is not remembering
.
More precisely, this method is equivalent to the following code:
if (with the only addition that this method also callsfirstStepFromBranch
(onlyToUnvisited)) { do { if (withVisiting) {visitPreviousBranchPixel()
; } } while (nextStep()
); }
context()
.checkInterruption()
method from time to time (if context()
!=nullonlyToUnvisited
 whether this method should go only to neighbours, which were never be visited before
(this argument affects only if this scanner is remembering
).withVisiting
 whether this method should call visitPreviousBranchPixel()
after each step
(this argument affects only if this scanner is remembering
).java.lang.IllegalStateException
 if this scanner was not positioned yet
or
if !isBranch()
.public int previousBranchStepDirection()
firstStep(int, boolean)
, firstStepFromBranch(boolean)
or nextStep()
method,
or 1 if the previous change of the current position was performed by some other method
like goTo(long...)
or nextNodeOrBranch()
.
This neighbour index is specified in terms of
pixelClassifier()
.neighbourOffset(int)
pixelClassifier()
.reverseNeighbourIndex(direction)
firstStep(int, boolean)
, firstStepFromBranch(boolean)
or nextStep()
method, or 1 if the last movement was performed by another method.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public long[] previousCoordinates()
firstStep(int, boolean)
, firstStepFromBranch(boolean)
or nextStep()
method,
or throws IllegalStateException if the previous change of the current position was performed
by some other method like goTo(long...)
or nextNodeOrBranch()
.
The returned array is always a newly allocated Java array.
Its length is always equal to dimCount()
.
The returned coordinates are always in ranges
0 ≤ result[k] <where result[k] is the element #k in the returned array.skeleton()
.dim
(k),
java.lang.IllegalStateException
 if this scanner was not positioned yet
,
or if the previous change of the current position was performed not by
not by firstStep(int, boolean)
, firstStepFromBranch(boolean)
or nextStep()
.previousIndexInArray()
public long previousIndexInArray()
previousCoordinates()
, designed for indexing
elements of the builtin AlgART array
of the skeleton matrix.
This method is equivalent to
skeleton()
.index
(previousCoordinates()
)The result of this method is always in range
0..skeleton()
.size()
1.
java.lang.IllegalStateException
 if this scanner was not positioned yet
,
or if the previous change of the current position was performed not by
not by firstStep(int, boolean)
, firstStepFromBranch(boolean)
or nextStep()
.public boolean isRemembering()
comments to this class
about remembering and lightweight skeleton scanners.public boolean pixelVisitRemembered()
remembering
and
the current element
was already visited by
visit()
or visitPreviousBranchPixel()
method.
If this scanner is lightweight, this method always returns false.
java.lang.IllegalStateException
 if this scanner was not positioned yet
.public boolean neighbourVisitRemembered(int neighbourIndex)
remembering
and
the neighbour of the current element
with the given index
was already visited by visit()
or visitPreviousBranchPixel()
method.
The result will be the same as if we would call
goToNeighbour
(neighbourIndex) and then call
pixelVisitRemembered()
, but this method does not change the current position.
If this scanner is lightweight, this method always returns false.
Note, that we allow a situation when the neighbouring element is out of ranges of the matrix coordinates.
This situation is processed according to the model of infinite pseudocyclical continuation —
see the end of the comments to this class
.
neighbourIndex
 the index of the neighbour, in terms of
pixelClassifier()
.neighbourOffset(int)
java.lang.IndexOutOfBoundsException
 if neighbourIndex is out of range
0..numberOfNeighbours()
1.java.lang.IllegalStateException
 if this scanner was not positioned yet
.public void visit()
remembering
scanners,
marks the current element
of the skeleton matrix as "visited".
In lightweight scanners, this method does nothing.
Note that the only way to "unmark" the visited element (i.e. to change its state back to "unvisited")
is calling reset()
method.
java.lang.IllegalStateException
 if this scanner was not positioned yet
.public void visitPreviousBranchPixel()
remembering
scanners,
marks the previous visited element
of the skeleton matrix as "visited".
In lightweight scanners, this method does nothing.
The "previous visited element" means the neighbour of the current element, coordinates of which
are returned by previousCoordinates()
method.
Note that the only way to "unmark" the visited element (i.e. to change its state back to "unvisited")
is calling reset()
method.
This methods is useful in loops of scanning skeleton branches: see examples of such loops
in comments to scanBranch(int, boolean, boolean)
and scanBranchFromBranch(boolean, boolean)
methods.
java.lang.IllegalStateException
 if this scanner was not positioned yet
,
or if the previous change of the current position was performed not by
not by firstStep(int, boolean)
, firstStepFromBranch(boolean)
or nextStep()
.public void reset()
not positioned
state
and, in remembering
scanners, resets the state of all pixels to
unvisited
.public void updateProgress()
context()
.updateProgress(event)
with an event, created by the following operator:
currentIndexInArray()
, skeleton()
.size()
)context()
==null.
The method can be useful while sequentially scanning the skeleton via a usual loop of
nextNodeOrBranch()
calls.
public void checkInterruption()
context()
.checkInterruption()
or does nothing if context()
==null.
The method can be useful while sequentially scanning the skeleton via a usual loop of
nextNodeOrBranch()
calls.
public java.lang.String toString()
The result of this method may depend on implementation and usually contains a short description of the current state of the scanner.
toString
in class java.lang.Object
Кружки с именами на 23 февраля Кружки с именами на 23 февраля everestprint.ru 