This software implements a dynamic programming approach for the general task of finding diverse shortest paths between two end-points. It is not linked to a specific biological problem and can be applied to a large variety of images.
The present software relies on a modified dynamic programming algorithm for finding a collection of diverse shortest paths in images between user-defined source and target locations. It is implemented to leaves a lot of freedom in the definition of path diversity, such as imposing a minimal Euclidean distance between paths, or enforcing that the different paths accumulate a certain amount of diversity. The plugin only requires the specification of the source and target locations and of the dynamic programming potential map in addition to data-independent parameters (number of desired shortest paths and minimum amount of desired diversity between paths). It can thus be used alone or integrated as part of larger image analysis pipelines.
For developers, we also provide the core processing units of DiversePathsJ as an SDK, without any user interface elements. DiversePathsSDK is available as a .jar library and can be instantiated as shown in this code snippet. Note that the SDK depends on the libraries contained in the following archive file.
Conditions of use
You'll be free to use this software for research purposes, but you must not transmit and distribute it without our consent. In addition, you undertake to include a citation to the associated papers whenever you present or publish results that are based on it. EPFL makes no warranties of any kind on this software and shall in no event be liable for damages of any kind in connection with the use and exploitation of this technology.
The software provided here is a plugin for ImageJ or Fiji, a general purpose image-processing and image-analysis package. ImageJ and Fiji are both open-source and free and do not take more than a couple of minutes to install.
Users are strongly encouraged to send bug reports, comments, praise and love letters at DiversePathsJ support address.
Download and install
Fiji users: DiversePathsJ is available through Fiji's built-in updater using http://sites.imagej.net/Vuhlmann/ as update site URL.
To install the plugin download the DiversePathsJ_.jar file and put it in the plugins folder of ImageJ (ImageJ/plugins/). DiversePathsJ also requires some external libraries that have been regrouped in the following archive file. The archive should be uncompressed, and the elements it contains should be placed into the jars folder of the plugins folder of ImageJ (ImageJ/plugins/jars/).
The plugin can be started from the Plugins tab of the ImageJ menu (see Figure 1).
Figure 1. ImageJ plugin menu featuring ChromosomeJ.
Before or directly after launch but in any case before running the diverse shortest paths search, a start and an end points must be selected. This is done using the point tool from ImageJ highlighted in Figure 2. The first point can be set by simply clicking on the image. To set the second one, maintain the shift key pressed and click at the desired location on the image.
Figure 2. Point selection tool of ImageJ used to set path extremities.
Figure 3 displays proper initial conditions for the diverse paths search. The two user-selected end-points are overlaid on the input image as blue crosses with labels "1" and "2". By convention, "1" is used as source and "2" as target points. DiversePathsJ requires exactly two selected points. Starting the plugin with less or more selected points will throw an error.
Figure 3. User-defined path extremities overlaid on an input image (appearing as blue crosses with labels "1" and "2").
Several input parameters can be set in DiversePathsJ GUI (Figure 4). Hereafter, we describe each of them.
Figure 4. DiversePathsJ GUI.
Figure 5. Search areas of the available algorithms for shortest paths search (left: Dijkstra, right: Viterbi).
Figure 6. Example of shortest paths search requiring Dijkstra. The Viterbi search area (right) does not cover the object on which shortest paths between the two end-points must be searched.
The paths searching procedure is started by hitting the button at the bottom of the GUI.
The cost function implemented in DiversePathsJ is very general to remain flexible enough to accommodate a wide range of use-cases. The cost between two successive nodes is computed as a convex combination of a data-fidelity term (the integral of the input cost map under the edge linking the nodes) and a regularization term (the distance between their states). Paths of low cost therefore tend to follow dark areas on the input cost map and to remain locally smooth.
Once paths searching is done, different outputs are available.
Figure 7. Browsing through the collection of shortest paths.
Figure 8. Example of input cost map for the shortest path algorithm.
Figure 9. Cost values for the collection of shortest paths.
Figure 10. Collection of shortest paths in ImageJ's ROI Manager.
Sample dataWe provide an example image and corresponding settings for DiversePathsJ. The end-points are saved as Multipoint ROIs and must be loaded through ImageJ/Fiji's ROI Manager interface (More >> -> Open...).