# Supplementary material
## Faster Multi-Object Segmentation using Parallel Quadratic Pseudo-Boolean Optimization

This folder contains a PDF file with a supplementary **proof of equivalent labeling** and some **notes on the performance of parallel EIBFS** and a set of **Jupyter notebooks and code** used for benchmarks in the ICCV 2021 paper *Faster Multi-Object Segmentation using Parallel Quadratic Pseudo-Boolean Optimization* by Jeppesen et al. Check [10.5281/zenodo.5201620](http://doi.org/10.5281/zenodo.5201620) for the latest version.

## Content
```
├───benchmark
│   ├───nerve_benchmarks
│   └───nuclei_benchmarks
│       ├───all
│       ├───peibfs
│       └───qpbo
├───notebooks
│   ├───figures
│   └───nuclei_comparison_data
├───originals
├───shrdr
│   └───shrdr
│       └───src
│           └───core
└───slgbuilder
    └───slgbuilder
```

### PDF file
`Supplementary__Faster_Multi_Object_Segmentation_using_Parallel_Quadratic_Pseudo_Boolean_Optimization__ICCV_.pdf`

This PDF file contain a proof of equivalent labelling in the case that QPBO and P-QPBO finds different min-cut solutions. Furthermore, it contains a short explanation for the poor performance of parallel EIBFS in the results presented in our paper.

### `shrdr`
This folder contains our own Python package named `shrdr` wrapping our P-QPBO and M-QPBO C++ implementations. The P-QPBO implementation can be found in the `parallel_qpbo.h` file and the M-QPBO implementation in the `qpbo.h` file, located in the `core` folder. The `shrdr` package can be installed locally using `pip install .` in terminal. Installing the package requires `Cython` and well as a C++ compiler (usually Microsoft Visual C++ for Windows and GCC for Linux). The code has been tested on both Windows and Linux systems. Make sure to leave this folder after the package is installed. If you start Python from this directory, you will get an error when importing the module.

### `slgbuilder`
This folder contains a modified version of the publicly available [`slgbuilder`](https://github.com/Skielex/slgbuilder) Python package for building sparse layered graphs. We've specificly modified the package to support our new P-QPBO and M-QPBO implementations through the `shrdr` package described above. Again, the package can be installed using `pip install .` in the terminal.

### `notebooks`
This folder contains Jupyter notebooks for preparing data used in our benchmarks, running the benchmarks and generating results, used in our paper.

- **`ParallelNerveSegmentation3DPart1.ipynb`** This notebook runs the benchmarks for the *N1* and *N2* nerve segmentation tasks. It is based on the `NerveSegmentation3D.ipynb` by [Jeppesen et. al](http://doi.org/10.11583/DTU.12016941).

- **`ParallelNerveSegmentation3DPart2.ipynb`** This notebook is used to analyze the benchmark results and create figures for the *N1* and *N2* segmentation tasks. 

- **`NucleiSegmentationPart1.ipynb`** This notebook is an unmodified copy of the notebooks by [Jeppesen et. al](http://doi.org/10.11583/DTU.12016941). It is used to prepare the nuclei data and is included for convenience.

- **`ParallelNucleiSegmentationPart2.ipynb`** This notebook runs the benchmark for nuclei segmentation task. It is based on the `NucleiSegmentationPart2b.ipynb` by [Jeppesen et. al](http://doi.org/10.11583/DTU.12016941).

- **`ParallelNucleiSegmentationPart3.ipynb`** This notebook is used to analyze the benchmark results and create figures for the nuclei segmentation tasks. 

### `benchmark`
This folder contains the benchmark result CSV files generated and used by the notebooks. All results for the QPBO algorithms tested can be recreased using the included notebooks. Results for the other algorithms require separate benchmark code, which is available on [GitHub](https://github.com/patmjen/maxflow_algorithms).

### `originals`
Folder to place nerve data `NT32_tomo3_.raw` and center lines `NT32_cLineLabel_scale4_preSegm_v3.nii.gz` files from [10.11583/DTU.12462143](http://doi.org/10.11583/DTU.12462143).

### `nuclei_comparison_data`
Folder to place the `stage1_train.zip` file from [BBBC038v1](https://bbbc.broadinstitute.org/BBBC038).