This repository contains implementations of local-search algorithms for the multi-separator problem that were presented in [1]. It also contains the source code to reproduce the experiments that are conducted in that paper.
The multi-separator algorithms can be installed as a python package by executing
pip install multi-separator-algorithms/
from the root directory of this repository.
To reproduce the experiments from Section 5 of the article, proceed as follows:
- Navigate to the
experimentsdirectory. - run
pip install -r requirements.txtto install all required packages. This will, in particular, install the custom packagesmulti-separator-algorithmsandpartition-comparisionthat are included in this supplementary material. - run
mkdir resultsto create a directory where the results can be saved. - for a given type of image (either
img_type=filamentorimg_type=cell) runpython experiments.py img_type. This will:- Create a hdf5 file to store all the results
- Generate synthetic images for different levels of noise
- Compute segmentations with the multi-separator algorithms and the watershed algorithm
- Evaluate the quality of the segmentations by computing various metrics
- Produce figures that summarize the results.
Running the experiments takes several hours as many segmentations will be computed
(10 seeds, 21 levels of noise, 51 bias parameters for the multi-separator algorithm, more than 1000 parameters for the watershed algorithm).
Within the main function of the experiments.py file several functions are called in sequence.
To speed up the evaluation of all experiments some of these function can be called in parallel (for example, it is possible to evaluate the experiments for all 21 different noise levels in parallel).
To evaluate the runtime performance of the GSS and GSG algorithm run
python performance_analysis.py.
To evaluate the effect of long-range interactions, run
python interaction_length_comparison.py img_type
with either img_type=filament or img_type=cell.
The data for reproducing the neuron segmentation experiments can be downloaded from here. This data includes the membrane estimates and affinities that are computed by a CNN. The implementation of this CNN is publicly available here.
If you use any of this data in your work, please cite Kasthure et al. (2015) and Lee et al. (2021).
To run the experiments, create a directeory results/connectomics for storing the results and then execute python connectomics_experiments.py.
[1] Irmai, J., Zhao, S., Schöne, M. et al. A Graph Multi-separator Problem for Image Segmentation. J Math Imaging Vis (2024). https://doi.org/10.1007/s10851-024-01201-1