public class OctupleThinningSkeleton2D extends AbstractIterativeArrayProcessor<Matrix<? extends UpdatableBitArray>> implements ThinningSkeleton
Algorithm of 2dimensional skeletonization of binary matrices based on 8 thinning steps, corresponding to 8 directions with the step 45 degree, based on analysis of 3x3 aperture.
More precisely, this class is an implementation of ThinningSkeleton
interface,
iteratively processing some bit matrix (Matrix
(UpdatableBitArray
)), named
result and passed to the getInstance
method.
In this implementation:
performIteration(ArrayContext)
method sequentially calls
asThinning(int directionIndex)
method and copies its result to
the result matrix for directionIndex=0,1,2,3,4,5,6,7.
It means, that all "objects" in the matrix (areas filled by 1 elements)
are "thinned" 8 times: from left direction, from lefttop diagonal direction, etc.
Depending on the argument of an instantiation method, performIteration(ArrayContext)
may skip
calling asThinning
for odd directions (1,3,5,7).
done()
method returns true if the last iteration was unable to change the matrix:
all "objects" are already "thin".result()
method always returns the reference to the source matrix, passed to
getInstance
method.The algorithm, implemented by this class, guarantees that 8connected "objects"
(areas filled by 1 elements) always stay 8connected;
see ThinningSkeleton
interface about the precise sense of this state.
The resulting "skeleton" are usually "thin" enough (1pixel lines),
but some little not "thin" areas are possible.
An example of resulting skeleton:
. . . . . . . . . 1 1 . . . . . . . . 1 . . . . . . . 1 . . . . . . . . 1 . . . . . . . . 1 . . . . . . . . 1 . . . . . . . . .
Examples of the result in the "bad" cases, when some areas cannot be "thinned" by this algorithm:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . 1 . 1 . . . . . . . . . . . . . . 1 . . . . 1 . . 1 . . 1 . . . 1 . 1 . 1 . . . . . . . . . . 1 . . 1 . . 1 . . 1 . 1 . 1 . . . 1 . 1 1 1 . 1 . . . 1 . . 1 . . . 1 . 1 . 1 . . . . 1 1 1 . . . . . 1 1 1 1 1 . . . . . 1 1 . . . . . 1 1 1 . . . 1 1 1 1 1 1 1 . . 1 . 1 1 1 . 1 . . . . 1 1 . . . . . 1 1 1 . . . . . 1 1 1 . . . . . 1 . 1 . 1 . . . . 1 . . 1 . . . 1 . 1 . 1 . . . 1 . 1 . 1 . . . . . 1 . 1 . . . . . . . . . . . 1 . . 1 . . 1 . 1 . . 1 . . 1 . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . 1 . . . .
The left example can have any size: it is possible to construct very large area filled by 1, which cannot
be skeletonized. But it can be excluded by little
closing
of the source matrix by the rectangle 2x1 before running skeletonization.
As an alternative, the left case can be processed by Quadruple3x5ThinningSkeleton2D
algorithm,
performed after this skeletonization.
This class is based on Matrices.asShifted
method
with some elementwise logical operations (AND, OR, NOT).
So, the matrix is supposed to be 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 may be applied to a matrix with any number of dimensions, but it is designed for 2dimensional case: all other dimensions will be ignored.
This class is not threadsafe, but is threadcompatible and can be synchronized manually, if multithread access is necessary.
AlgART Laboratory 2007–2014
WeakOctupleThinningSkeleton2D
context, memoryModel
Modifier and Type  Method and Description 

Matrix<BitArray> 
asThinning(int directionIndex)
Returns current
result() matrix thinned along the given direction. 
boolean 
done()
Returns true if and only if the algorithm was successfully finished and there is
no sense to perform further iterations.

long 
estimatedNumberOfIterations()
Estimates the number of iterations, that should be performed from this moment to finish the algorithm.

void 
freeResources(ArrayContext context)
If there are some resources, allocated by this object, which are not controlled
by Java garbage collectors — files, streams, sockets, locks, etc. —
this method tries to release them (for example, to close any files).

static OctupleThinningSkeleton2D 
getInstance(ArrayContext context,
Matrix<? extends UpdatableBitArray> matrix)
Creates new instance of this class.

static OctupleThinningSkeleton2D 
getInstance(ArrayContext context,
Matrix<? extends UpdatableBitArray> matrix,
boolean diagonalThinning,
boolean topological)
Creates new instance of this class.

boolean 
isThinningRequired(int directionIndex)
Returns true if and only if
performIteration(ArrayContext) method
really calls ThinningSkeleton.asThinning(int directionIndex) for this direction
and copies its result to the result matrix. 
void 
performIteration(ArrayContext context)
Performs the next iteration of the iterative algorithm.

Matrix<? extends UpdatableBitArray> 
result()
Returns the result of the previous iteration.

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

chain, context, limitIterations, part, process
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
isThinningRequired
chain, done, freeResources, limitIterations, performIteration, process, result
context
public static OctupleThinningSkeleton2D getInstance(ArrayContext context, Matrix<? extends UpdatableBitArray> matrix, boolean diagonalThinning, boolean topological)
If the diagonalThinning argument is false, the algorithm will skip thinning along diagonal directions (directionIndex=1,3,5,7). The result will be still correct, but the lines of the skeleton will be not so even.
If the topological is true, the algorithm doesn't stop when all objects in the matrix become "thin" (1pixel thickness), but continues shortening all "free ends" of all skeleton lines, while there is at least one "free end". As a result, objects that have no "holes" will be removed at all, objects that have 1 hole will be transformed into 1pixel closed line ("ring"), etc. This mode essentially slows down the algorithm.
context
 the context
that will be used by this object;
may be null, then it will be ignored.matrix
 the bit matrix that should be processed and returned by result()
method.diagonalThinning
 whether the algorithm will perform diagonal thinning; usually true.topological
 whether the algorithm will shorten isolated thin lines with "free ends".java.lang.NullPointerException
 if matrix argument is null.public static OctupleThinningSkeleton2D getInstance(ArrayContext context, Matrix<? extends UpdatableBitArray> matrix)
getInstance(context, matrix, true, false)
.public long estimatedNumberOfIterations()
IterativeArrayProcessor
This method may require some time for its execution.
You usually don't need to call this method: it is automatically called from time to time by
IterativeArrayProcessor.process()
method.
It is used for creating subcontexts, describing a part
of the full task.
This method must be implemented while creating a new iterative arrayprocessing algorithm.
estimatedNumberOfIterations
in interface IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
public Matrix<BitArray> asThinning(int directionIndex)
result()
matrix thinned along the given direction.
The result is "lazy": it is only a view of the current matrix.
The precise algorithm of thinning is not documented. Generally speaking, the "thinning" means removing elements from the boundary of any "object" (area of the matrix filled by 1). directionIndex specifies the "eroded side" of objects, or the direction of thinning:
Though the algorithm is not documented, there are the following guarantees:
asThinning
in interface ThinningSkeleton
directionIndex
 the direction of thinning, from 0 to 7.result()
matrix.java.lang.IllegalArgumentException
 if directionIndex is not in 0..7 range.public java.lang.String toString()
toString
in class java.lang.Object
public final void performIteration(ArrayContext context)
IterativeArrayProcessor
IterativeArrayProcessor.done()
, the results are unspecified:
please never call this method if IterativeArrayProcessor.done()
returns true.
You usually don't need to call this method: please call
IterativeArrayProcessor.process()
instead.
If you need to perform only one or n iterations, you may use
limitIterations(n)
call.
Warning: this method should ignore the current execution context
of this object.
Instead, this method should use the context of execution specified by context argument.
This method is called by IterativeArrayProcessor.process()
method with the argument,
describing a subtrask
of the full algorithm.
The context argument may be null:
this method should work properly in this case (ignore the context).
This method must be implemented while creating a new iterative arrayprocessing algorithm.
performIteration
in interface IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
performIteration
in class AbstractIterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
context
 the context used by this instance for all operations; may be null.public final boolean done()
IterativeArrayProcessor
This method usually does not perform actual calculations and works very quickly (just returns and internal flag). However, this condition is not strict.
You usually don't need to call this method: it is automatically called by
IterativeArrayProcessor.process()
method.
This method must be implemented while creating a new iterative arrayprocessing algorithm.
done
in interface IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
done
in class AbstractIterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
public final Matrix<? extends UpdatableBitArray> result()
IterativeArrayProcessor
UpdatableArray
or
Matrix
<? extends UpdatableArray
>.
This method returns valid result even if no iterations were performed yet.
If IterativeArrayProcessor.done()
method returns true, the result of this method
is the final result of iterative processing performed by this instance.
This method may return null. In this case, the concrete implementation of this interface should provide additional methods for returning calculation results.
This method does not perform actual calculations and works very quickly.
This method must be implemented while creating a new iterative arrayprocessing algorithm.
result
in interface IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
result
in class AbstractIterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
public final void freeResources(ArrayContext context)
IterativeArrayProcessor
Usually, this method just calls
Array.freeResources(context)
and
Matrix.freeResources(context)
for all temporary arrays and matrices, allocated by this object for storing work data.
If IterativeArrayProcessor.result()
method returns AlgART array or matrix (typical situation),
this method calls Array.freeResources(context)
/
Matrix.freeResources(context)
methods
for this array / matrix.
This method may be used in situations when the instance of this object has long time life and will be reused in future.
This method must be implemented while creating a new iterative arrayprocessing algorithm.
freeResources
in interface IterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
freeResources
in class AbstractIterativeArrayProcessor<Matrix<? extends UpdatableBitArray>>
context
 the context of execution; may be null, then it will be ignored.public final boolean isThinningRequired(int directionIndex)
ThinningSkeleton
performIteration(ArrayContext)
method
really calls ThinningSkeleton.asThinning(int directionIndex)
for this direction
and copies its result to the result matrix.
It depends on the implementation of this interface.isThinningRequired
in interface ThinningSkeleton
directionIndex
 the direction of thinning, from 0 to 7.