Conference paper
Faster Multi-Object Segmentation using Parallel Quadratic Pseudo-Boolean Optimization
Visual Computing, Department of Applied Mathematics and Computer Science, Technical University of Denmark1
Department of Applied Mathematics and Computer Science, Technical University of Denmark2
Statistics and Data Analysis, Department of Applied Mathematics and Computer Science, Technical University of Denmark3
We introduce a parallel version of the Quadratic PseudoBoolean Optimization (QPBO) algorithm for solving binary optimization tasks, such as image segmentation. The original QPBO implementation by Kolmogorov and Rother relies on the Boykov-Kolmogorov (BK) maxflow/mincut algorithm and performs well for many image analysis tasks.
However, the serial nature of their QPBO algorithm results in poor utilization of modern hardware. By redesigning the QPBO algorithm to work with parallel maxflow/mincut algorithms, we significantly reduce solve time of large optimization tasks. We compare our parallel QPBO implementation to other state-of-the-art solvers and benchmark them on two large segmentation tasks and a substantial set of small segmentation tasks.
The results show that our parallel QPBO algorithm is over 20 times faster than the serial QPBO algorithm on the large tasks and over three times faster for the majority of the small tasks. Although we focus on image segmentation, our algorithm is generic and can be used for any QPBO problem. Our implementation and experimental results are available at DOI: 10.5281/zenodo.5201620
Language: | English |
---|---|
Publisher: | IEEE |
Year: | 2021 |
Pages: | 6260-6269 |
Proceedings: | 2021 International Conference on Computer Vision |
ISBN: | 1665428120 and 9781665428125 |
ISSN: | 23807504 and 15505499 |
Types: | Conference paper |
DOI: | 10.1109/ICCV48922.2021.00620 |
ORCIDs: | Jensen, Patrick Møller , Christensen, Anders Nymark , Dahl, Anders Bjørholm and Dahl, Vedrana Andersen |