de.unihalle.informatik.MiToBo.math.graphs

Class DijkstraShortestPixelPathFinder

java.lang.Object

de.unihalle.informatik.Alida.operator.ALDOperator

de.unihalle.informatik.MiToBo.core.operator.MTBOperator

de.unihalle.informatik.MiToBo.math.graphs.DijkstraShortestPixelPathFinder

All Implemented Interfaces:

de.unihalle.informatik.Alida.datatypes.ALDConfigurationValidator, de.unihalle.informatik.Alida.operator.events.ALDOperatorExecutionProgressEventListener, EventListener

@ALDAOperator(genericExecutionMode=ALL,
              level=APPLICATION)
public class DijkstraShortestPixelPathFinder
extends MTBOperator

Search shortest path between two pixels in an image using Dijkstra.

The image is interpreted as a graph with the pixels being the nodes and edges referring to 8-neighborhood relations. Each edge gets as weight the intensity value of the target pixel. Optionally also a power of the intensity value or its exponential function value can be used as weight. The algorithm seeks to minimize path cost, i.e., is looking for path along dark pixels.

The path is found applying the Dijkstra graph search algorithm as implemented in the JGraphT library released under GPL by Barak Naveh and contributors. For details refer to the webpage of the library, https://jgrapht.org/, and to the API documentation of the Dijkstra class.

Author:

moeller

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	DijkstraShortestPixelPathFinder.GraphNode Local class to represent the nodes of the graph.
static class	DijkstraShortestPixelPathFinder.WeightModel Modes how to set the weights.

Nested classes/interfaces inherited from class de.unihalle.informatik.Alida.operator.ALDOperator

de.unihalle.informatik.Alida.operator.ALDOperator.HidingMode, de.unihalle.informatik.Alida.operator.ALDOperator.HistoryConstructionMode

Field Summary

Fields

Modifier and Type	Field and Description
protected Point2D.Double	endPoint End pixel of the path.
protected MTBImage	inImg Input gray-scale image.
protected boolean	invertPixelValues If true image values are inverted, i.e., the algorithm seeks to find a path along bright pixels.
protected double	nodeThreshold Threshold for nodes to be included, nodes with an intensity above the threshold are removed from the graph.
protected double	resultCosts Costs of the result path.
protected MTBImageRGB	resultImg Result image with path overlay, start pixel in green, end pixel in blue.
protected Vector<Point2D.Double>	resultPath Result path represented as point list.
protected Point2D.Double	startPoint Start pixel of the path.
protected DijkstraShortestPixelPathFinder.WeightModel	weightModel Model for the edge weights.
private double	workImgMaxVal Maximum intensity value in working image, i.e. after potential inversion of image intensity values.

Fields inherited from class de.unihalle.informatik.Alida.operator.ALDOperator

completeDAG, name, operatorExecutionEventlistenerList, portHashAccess, verbose, versionProvider

Constructor Summary

Constructors

Constructor and Description
DijkstraShortestPixelPathFinder() Default constructor.

Method Summary

Modifier and Type	Method and Description
double	getResultCosts() Returns the costs of the shortest path.
MTBImageRGB	getResultImage() Returns the result image with path overlay.
Vector<Point2D.Double>	getResultPath() Returns the extracted shortest path as point list.
private double	getWeight(double v1, double v2) Return edge weight for edge between given nodes.
protected void	operate()
void	setEndPixel(Point2D.Double ep) Specify end pixel of path.
void	setInputImage(MTBImage img) Set input image to process.
void	setInvertPixelValues(boolean b) Enable/disable pixel values invertion.
void	setNodeThreshold(double t) Set threshold for filtering nodes.
void	setStartPixel(Point2D.Double sp) Specify start pixel of path.
void	setWeightModel(DijkstraShortestPixelPathFinder.WeightModel w) Select model for choosing edge weights.

Methods inherited from class de.unihalle.informatik.MiToBo.core.operator.MTBOperator

readResolve

Methods inherited from class de.unihalle.informatik.Alida.operator.ALDOperator

addOperatorExecutionProgressEventListener, addParameter, addParameter, addParameterUnconditioned, fieldContained, fireOperatorExecutionProgressEvent, getALDPortHashAccessKey, getConstructionMode, getDocumentation, getHidingMode, getInactiveParameterNames, getInInoutNames, getInInoutNames, getInNames, getInOutNames, getMissingRequiredInputs, getName, getNumParameters, getOutInoutNames, getOutNames, getParameter, getParameterDescriptor, getParameterDescriptorUnconditioned, getParameterNames, getParameterUnconditioned, getSupplementalNames, getVerbose, getVersion, handleOperatorExecutionProgressEvent, hasInOutParameters, hasParameter, isAnnotatedParameter, isConfigured, print, print, print, printInterface, printInterface, readHistory, reinitializeParameterDescriptors, removeOperatorExecutionProgressEventListener, removeParameter, runOp, runOp, runOp, setConstructionMode, setConstructionMode, setConstructionMode, setHidingMode, setName, setParameter, setParameterUnconditioned, setVerbose, toStringVerbose, unconfiguredItems, validate, validateCustom, validateGeneric, writeHistory, writeHistory, writeHistory

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

inImg

@Parameter(label="Input Image",
           required=true,
           dataIOOrder=-10,
           direction=IN,
           description="Input image.")
protected transient MTBImage inImg

Input gray-scale image.

By default, intensity values are directly interpreted as costs, i.e., the algorithm is searching for paths along dark pixels. If this is not intended, select option. invertPixelValues to invert values.

invertPixelValues

@Parameter(label="Invert Pixel Values?",
           required=true,
           dataIOOrder=-1,
           direction=IN,
           description="Invert pixel values, i.e., favor bright pixels.")
protected boolean invertPixelValues

If true image values are inverted, i.e., the algorithm seeks to find a path along bright pixels.

weightModel

@Parameter(label="Weight Model",
           required=true,
           dataIOOrder=0,
           direction=IN,
           description="Edge weight model.")
protected DijkstraShortestPixelPathFinder.WeightModel weightModel

Model for the edge weights.

startPoint

@Parameter(label="Start Pixel",
           required=true,
           dataIOOrder=1,
           direction=IN,
           description="Start pixel.")
protected Point2D.Double startPoint

Start pixel of the path.

endPoint

@Parameter(label="End Pixel",
           required=true,
           dataIOOrder=2,
           direction=IN,
           description="Result image.")
protected Point2D.Double endPoint

End pixel of the path.

nodeThreshold

@Parameter(label="Node Threshold",
           required=true,
           dataIOOrder=3,
           direction=IN,
           description="Only intensities below threshold (or above if inverted mode is active) are considered.")
protected double nodeThreshold

Threshold for nodes to be included, nodes with an intensity above the threshold are removed from the graph.

By default the threshold is Double.MAX_VALUE and all nodes are considered. Omitting nodes (and corresponding edges) has a positive effect on runtime.

resultImg

@Parameter(label="Result image",
           direction=OUT,
           dataIOOrder=1,
           description="Result image with path overlay.")
protected transient MTBImageRGB resultImg

Result image with path overlay, start pixel in green, end pixel in blue.

resultPath

@Parameter(label="Result path",
           direction=OUT,
           dataIOOrder=2,
           description="Result path represented as point list.")
protected Vector<Point2D.Double> resultPath

Result path represented as point list.

resultCosts

@Parameter(label="Result costs",
           direction=OUT,
           dataIOOrder=3,
           description="Costs of result path.")
protected double resultCosts

Costs of the result path.

workImgMaxVal

private double workImgMaxVal

Maximum intensity value in working image, i.e. after potential inversion of image intensity values.

Constructor Detail

DijkstraShortestPixelPathFinder

public DijkstraShortestPixelPathFinder()
                                throws de.unihalle.informatik.Alida.exceptions.ALDOperatorException

Default constructor.

Throws:

de.unihalle.informatik.Alida.exceptions.ALDOperatorException - Thrown in case of failure.

Method Detail

setInputImage

public void setInputImage(MTBImage img)

Set input image to process.

Parameters:

img - Input image to process.

setInvertPixelValues

public void setInvertPixelValues(boolean b)

Enable/disable pixel values invertion.

Parameters:

b - If true, pixel intensities are inverted.

setWeightModel

public void setWeightModel(DijkstraShortestPixelPathFinder.WeightModel w)

Select model for choosing edge weights.

Parameters:

w - Model to apply.

setStartPixel

public void setStartPixel(Point2D.Double sp)

Specify start pixel of path.

Parameters:

sp - Start pixel.

setEndPixel

public void setEndPixel(Point2D.Double ep)

Specify end pixel of path.

Parameters:

ep - End pixel.

setNodeThreshold

public void setNodeThreshold(double t)

Set threshold for filtering nodes.

Parameters:

t - Threshold to apply.

getResultImage

public MTBImageRGB getResultImage()

Returns the result image with path overlay.

Returns:

Overlay image.

getResultPath

public Vector<Point2D.Double> getResultPath()

Returns the extracted shortest path as point list.

Returns:

Result path with minimal cost, null if none was found.

getResultCosts

public double getResultCosts()

Returns the costs of the shortest path.

Returns:

Costs of optimal path, NaN in case that no path was found.

operate

protected void operate()

Specified by:

operate in class de.unihalle.informatik.Alida.operator.ALDOperator

getWeight

private double getWeight(double v1,
                         double v2)

Return edge weight for edge between given nodes.

We assume here that small intensity values of the target node are good, i.e., the edge towards the pixel should ge a small weight.

Parameters:

v1 - Source node of edge.

v2 - Target node of edge.

Returns:

Weight for edge according to selected weight model.