BIG > DiversePathsJ
Graphic STI
logo EPFL
Text EPFL
english only
Biomedical Imaging Group
Algorithms
BIG > Algorithms > DiversePathsJ
CONTENTS

BIG homepage

Research

Publications

Demos

Algorithms

Teaching

DiversePathsJ

Outline

References

Technical Explanations

Software Installation

User manual

Additional resources

Related Works

Download

DiversePathsJ_.jar

Plugin for ImageJ

[Version 23.01.2018]

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

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.

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

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

ImageJ plugin menu featuring DiversePathsJ.

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.

Point selection tool of ImageJ used to set path extremities.

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.

User-defined path extremities overlaid on an input image.

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.

DiversePathsJ GUI.

Figure 4. DiversePathsJ GUI.

Algorithms for shortest paths search.

Figure 5. Search areas of the available algorithms for shortest paths search (left: Dijkstra, right: Viterbi).

Example of shortest path search requiring Dijkstra.

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 run 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.

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

Browsing through the collection of shortest paths.

Figure 7. Browsing through the collection of shortest paths.

Example of input cost map for the shortest path algorithm.

Figure 8. Example of input cost map for the shortest path algorithm.

Cost values for the collection of shortest paths.

Figure 9. Cost values for the collection of shortest paths.

Collection of shortest paths in ImageJ's ROI Manager.

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

Related Works

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