Publication

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

You, J., Trager, S. & Wilkinson, M. H. F., 31-May-2019, Mathematical Morphology and Its Applications to Signal and Image Processing. Burgeth, B., Kleefeld, A., Naegel, B., Passat, N. & Perret, B. (eds.). Cham: Springer, p. 256-267 (Lecture Notes in Computer Science; vol. 11564).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Copy link to clipboard

Documents

  • A Fast, Memory-Efficient Alpha-Tree Algorithmusing Flooding and Tree Size Estimation

    Final author's version, 497 KB, PDF-document

    Request copy

DOI

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.
Original languageEnglish
Title of host publicationMathematical Morphology and Its Applications to Signal and Image Processing
EditorsB. Burgeth , A. Kleefeld , B. Naegel , N. Passat , B. Perret
Place of PublicationCham
PublisherSpringer
Pages256-267
ISBN (Electronic)978-3-030-20867-7
ISBN (Print)978-3-030-20866-0
Publication statusPublished - 31-May-2019
EventInternational Symposium on Mathematical Morphology - Saarland University, Saarbrücken, Germany
Duration: 8-Jul-201910-Jul-2019
Conference number: 14
http://ismm.uni-saarland.de/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11564

Conference

ConferenceInternational Symposium on Mathematical Morphology
Abbreviated titleISMM
CountryGermany
CitySaarbrücken
Period08/07/201910/07/2019
Internet address

Event

International Symposium on Mathematical Morphology

08/07/201910/07/2019

Saarbrücken, Germany

Event: Conference

View graph of relations

ID: 93414662