In this article, we design an incremental method for computing seeded watershed cuts for interactive image segmentation. We propose an algorithm based on the hierarchical image representation called the binary partition tree to compute a seeded watershed cut. Additionally, we leverage properties of minimum spanning forests to introduce a parallel method for labeling a connected component. We show that those algorithms fits perfectly in an interactive segmentation process by handling user interactions, seed addition or removal, in linear time with respect to the number of affected pixels. Run time comparisons with several state-of-the-art interactive and non-interactive watershed methods show that the proposed method can handle user interactions much faster than previous methods with a significant speedup ranging from 10 to 60 on both 2D and 3D images, thus improving the user experience on large images.
@inproceedings{lebon2024prl,author={Lebon, Quentin and Lef{\`e}vre, Josselin and Cousty, Jean and Perret, Benjamin},title={Incremental Watershed Cuts: Interactive Segmentation Algorithm with Parallel Strategy},journal={Pattern Recognition Letters},booktitle={Pattern Recognition Letters},year={2024},issn={0167-8655},keywords={Interactive segmentation, Watershed, Binary partition tree, Minimum spanning tree, Parallel labeling},}
Binary Partition Hierarchies (BPHs) and Minimum Spanning Trees are key structures in hierarchical image analysis. However, the explosion in the size of image data poses a new challenge, as the memory available in conventional workstations becomes insufficient to execute classical algorithms. To address this problem, specific algorithms have been proposed for out-of-core computation of BPHs, where a BPH is actually represented by a collection of smaller trees, called a distribution, thus reducing the memory footprint of the algorithms. In this article, we address the problem of designing efficient out-of-core algorithms for computing classical attributes in distributions of BPHs, which is a necessary step towards a complete out-of-core hierarchical analysis workflow that includes tasks such as connected filtering and the generation of other representations such as hierarchical watersheds. The proposed algorithms are based on generic operations designed to propagate information through the distribution of trees, enabling the computation of attributes such as area, volume, height, minima and number of minima.
@inproceedings{lefevre2024dgmm,author={Lefèvre, Josselin and Cousty, Jean and Perret, Benjamin and Phelippeau, Harold},title={Out-of-core Attribute Algorithms for Binary Partition Hierarchies},booktitle={Discrete Geometry and Mathematical Morphology},editor={Brunetti, Sara and Frosini, Andrea and Rinaldi, Simone},publisher={Springer Nature Switzerland},year={2024},pages={298--311},}
In this article, we propose an incremental method for computing seeded watershed cuts for interactive image segmentation. We propose an algorithm based on the hierarchical image representation called the binary partition tree to compute a seeded watershed cut. We show that this algorithm fits perfectly in an interactive segmentation process by handling user interactions, seed addition or removal, in time linear with respect to the number of affected pixels. Run time comparisons with several state-of-the-art interactive and non-interactive watershed methods show that the proposed method can handle user interactions much faster than previous methods achieving significant speedup from 15 to 90, thus improving the user experience on large images.
@inproceedings{lebon2023iws,author={Lebon, Quentin and Lef{\`e}vre, Josselin and Cousty, Jean and Perret, Benjamin},editor={Vasconcelos, Ver{\'o}nica and Domingues, In{\^e}s and Paredes, Sim{\~a}o},title={Interactive Segmentation with Incremental Watershed Cuts},booktitle={Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications},year={2023},publisher={Springer Nature Switzerland},address={Cham},pages={189--200},isbn={978-3-031-49018-7},award={CIARP Best Student Paper Award}}
Binary Partition Hierarchies (BPH) and minimum spanning trees are fundamental data structures involved in hierarchical analysis such as quasi-flat zones or watershed. However, classical BPH construction algorithms require to have the whole data in memory, which prevent the processing of large images that cannot fit entirely in the main memory of the computer. To cope with this problem, an algebraic framework leading to a high level calculus was introduced allowing an out-of-core computation of BPHs. This calculus relies on three operations: select, join, and insert. In this article, we introduce three efficient algorithms to perform these operations providing pseudo-code and complexity analysis.
@inproceedings{lefevre2022dgmm,title={Join, Select, and Insert: Efficient Out-of-core Algorithms for Hierarchical Segmentation Trees},author={Lefèvre, Josselin and Cousty, Jean and Perret, Benjamin and Phelippeau, Harold},year={2022},doi={10.1007/978-3-031-19897-7_22},pages={274-286},booktitle={Discrete Geometry and Mathematical Morphology},editor={Baudrier, Étienne and Naegel, Benoît and Krähenbühl, Adrien and Tajine, Mohamed},volume={13493},series={Lecture Notes in Computer Science},publisher={Springer},isbn={978-3-031-19897-7},award={DGMM Best Student Paper Award}}
Posters
2023
JNIM
Join, Select, and Insert: Efficient Out-of-core Algorithms for Hierarchical Segmentation Trees
Binary Partition Hierarchies (BPH) and minimum spanning trees are fundamental data structures involved in hierarchical analysis such as quasi-flat zones or watershed. However, classical BPH construction algorithms require to have the whole data in memory, which prevent the processing of large images that cannot fit entirely in the main memory of the computer. To cope with this problem, an algebraic framework leading to a high level calculus was introduced allowing an out-of-core computation of BPHs. This calculus relies on three operations: select, join, and insert. In this article, we introduce three efficient algorithms to perform these operations providing pseudo-code and complexity analysis.
Incremental Watershed Cuts: Interactive Segmentation Algorithm with Parallel StrategyIn Pattern Recognition Letters, 2024
Join, Select, and Insert: Efficient Out-of-core Algorithms for Hierarchical Segmentation TreesJosselin Lefèvre, Jean Cousty, Benjamin Perret, and Harold Phelippeau2023