A Fast, Memory-Efficient Alpha-Tree Algorithm using Flooding and Tree Size Estimation

Jiwoo You*, Scott Trager, M.H.F. Wilkinson

*Bijbehorende auteur voor dit werk

OnderzoeksoutputAcademicpeer review

73 Downloads (Pure)


The alpha-tree represents an image as hierarchical set of alpha-connected components. Computation of alpha-trees suffers from high computational and memory requirements compared with similar component tree algorithms such as max-tree. Here we introduce a novel alpha-tree algorithm using 1) a flooding algorithm for computational efficiency and 2) tree size estimation (TSE) for memory efficiency. In TSE, an exponential decay model was fitted to normalized tree sizes as a function of the normalized root mean squared deviation (NRMSD) of edge-dissimilarity distributions, and the model was used to estimate the optimum memory allocation size for alpha-tree construction. An experiment on 1256 images shows that our algorithm runs 2.27 times faster than Ouzounis and Soille's thanks to the flooding algorithm, and TSE reduced the average memory allocation of the proposed algorithm by 40.4%, eliminating unused allocated memory by 86.0% with a negligible computational cost.
Originele taal-2English
TitelMathematical Morphology and Its Applications to Signal and Image Processing
RedacteurenB. Burgeth , A. Kleefeld , B. Naegel , N. Passat , B. Perret
Plaats van productieCham
ISBN van elektronische versie978-3-030-20867-7
ISBN van geprinte versie978-3-030-20866-0
StatusPublished - 31-mei-2019
EvenementInternational Symposium on Mathematical Morphology - Saarland University, Saarbrücken, Germany
Duur: 8-jul-201910-jul-2019
Congresnummer: 14

Publicatie series

NaamLecture Notes in Computer Science


ConferenceInternational Symposium on Mathematical Morphology
Verkorte titelISMM
Internet adres

Citeer dit