DiversePathsJ Plugin

Image analysis tool

Written by Virginie Uhlmann at the Biomedical Image Group (BIG), EPFL, Switzerland

Outline

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.

References

• V. Uhlmann, C. Haubold, F. Hamprecht, M. Unser, "DiversePathsJ: Diverse Shortest Paths for Bioimage Analysis," Bioinformatics, in press.
• C. Haubold, V. Uhlmann, M. Unser, F.A. Hamprecht, "Diverse M-Best Solutions by Dynamic Programming," Proceedings of the Thirty-Ninth German Conference on Pattern Recognition (GCPR'17), Basel BS, Swiss Confederation, September 13-15, 2017, in press.

Technical Explanations

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.

Software Installation

ImageJ prerequirement

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/).

User Manual

Launch

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").

Settings

Several input parameters can be set in DiversePathsJ GUI (Figure 4). Hereafter, we describe each of them.

Figure 4. DiversePathsJ GUI.

• Algorithm: Path finding algorithm used to search for shortest paths. The options are Dijkstra and Viterbi. These two algorithms do not search shortest paths over the same area. From a user point of view, the important difference between the two is that Dijkstra searches for paths in a rounded rectangle around the straight line linking the two input points, while Viterbi only searches for paths around this line. This is schematically illustrated in Figure 5. As a consequence, Viterbi won't be able to find proper paths on some objects because the search area will not cover them properly (see Figure 6 for an example). The price to pay is however that, for large images, Dijkstra results in longer processing times than Viterbi. A good rule of thumb is to rely on Viterbi whenever possible.
• Number of diverse paths: Number of diverse paths to be computed.
• Size of exclusion corridor [px]: Distance (in pixels) that any new shortest paths must have to all previous ones, at least at one point, to be considered as valid (see Figure 1c in DiversePathsJ paper).
• Accumulated diversity threshold [px]: Minimal amount of diversity (in pixels) that any new solution must accumulate with respect to all previous ones. The diversity of each pixel here corresponds to its Euclidean distance to the unions of all previously computed paths (see Figure 2 in the supplementary material of DiversePathsJ paper).
• Target type: Type of object on which the shortest paths have to be searched (bright on dark background or dark on bright background).
• Processing filter: Options for processing the input image and highlight features of interest prior to the shortest path search. The options are none (no processing), EDM (Euclidean distance transform, highlights the centerline of objects), edge filter (highlights edges), ridge filter (highlights ridges), and external (custom processing). The edge and ridge filters are implemented as steerable filters based on the work of Jacob et al.
• Gaussian blur [px]: This option is only available when the edge and ridge processing filters are selected. It should be set as the approximate size (in pixels) of the edge or ridge object to be highlighted.
• External cost map:Path to a file path containing a processed version of the input image to be used as input cost map. This option is only available when the external processing filter is chosen. It allows the user to select a custom input cost map to be used by the shortest paths finding algorithm.

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.

Outputs

Once paths searching is done, different outputs are available.

• Explore paths manually: Displays the first shortest path as an overlay on the original input image. Upon clicking on the left and right arrow keys of the keyboard, the overlay is updated with the next (right) or previous (left) shortest path (see Figure 7 for an example). The complete collection of computed paths can thus be browsed swiftly without any mouse click. Upon clicking on the space bar, the currently displayed path is validated and exported as a Polyline ROI into ImageJ/Fiji's ROI Manager. This option is selected by default.
• Display cost map: Displays the cost map image used by the shortest path finding algorithm in a new image window (see Figure 8 for an example).
• Display cost values: Displays the value of the cost of each computed path in ImageJ/Fiji's log window (see Figure 9 for an example).
• Export all paths as ROIs: Exports the entire collection of computed paths as Polyline ROIs into ImageJ/Fiji's ROI Manager. (see Figure 10 for an example)
• Export all paths as images: For each element in the collection of computed paths, creates and displays the path as overlayed on a copy of the original image. Warning: this option creates as many new image windows as there are computed diverse shortest paths!

Once exported in ImageJ/Fiji's ROI Manager, paths can be handled, measured or used for further processing like any standard ImageJ/Fiji ROIs.

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 data

We 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...).

1. C. elegans (data courtesy of M. Cornaglia, Laboratory of Microsystems (LMIS2), EPFL, Switzerland)
   • Raw data: .tif image
   • Settings: Algorithm=Viterbi, Number of diverse paths=3, Size of exclusion corridor=25, Accumulated diversity threshold=40, Target type=Dark on bright background, Processing filter=Ridge filter, Gaussian blur=6
   • Inputs: top nematode, bottom nematode
   • Expected output: correct paths correspond to the first (top nematode) and third (bottom nematode) diverse shortest paths in the collection

Additional resources

• Supplementary material of the DiversePathsJ software paper, including a technical description of the algorithm as well as a description of the interface of the plugin.
• Supplementary material of the general diverse M-best theory paper.

Related Works

• NeuronJ, Erik Meijering, EPFL, 2004.

© 2018 EPFL • webmaster.big@epfl.ch • 18.03.2018