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

Jiwoo You; Scott Trager; M.H.F. Wilkinson

doi:10.1007/978-3-030-20867-7_20

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

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

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

225 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Mathematical Morphology and Its Applications to Signal and Image Processing
Editors	B. Burgeth , A. Kleefeld , B. Naegel , N. Passat , B. Perret
Place of Publication	Cham
Publisher	Springer
Pages	256-267
ISBN (Electronic)	978-3-030-20867-7
ISBN (Print)	978-3-030-20866-0
DOIs	https://doi.org/10.1007/978-3-030-20867-7_20
Publication status	Published - 31-May-2019
Event	International Symposium on Mathematical Morphology - Saarland University, Saarbrücken, Germany Duration: 8-Jul-2019 → 10-Jul-2019 Conference number: 14 http://ismm.uni-saarland.de/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11564

Conference

Conference	International Symposium on Mathematical Morphology
Abbreviated title	ISMM
Country/Territory	Germany
City	Saarbrücken
Period	08/07/2019 → 10/07/2019
Internet address	http://ismm.uni-saarland.de/

Access to Document

10.1007/978-3-030-20867-7_20

A Fast, Memory-Efficient Alpha-Tree Algorithmusing Flooding and Tree Size EstimationFinal author's version, 497 KBLicence: Taverne

Handle.net

Persistent link

Cite this

You, J., Trager, S., & Wilkinson, M. H. F. (2019). A Fast, Memory-Efficient Alpha-Tree Algorithm using Flooding and Tree Size Estimation. In B. Burgeth , A. Kleefeld , B. Naegel , N. Passat , & B. Perret (Eds.), Mathematical Morphology and Its Applications to Signal and Image Processing (pp. 256-267). (Lecture Notes in Computer Science; Vol. 11564). Springer. https://doi.org/10.1007/978-3-030-20867-7_20

@inproceedings{0bc52b56bc144b2585a85411e2ad8627,

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

abstract = "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.",

author = "Jiwoo You and Scott Trager and M.H.F. Wilkinson",

year = "2019",

month = may,

day = "31",

doi = "10.1007/978-3-030-20867-7_20",

language = "English",

isbn = "978-3-030-20866-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "256--267",

editor = "{Burgeth }, B. and {Kleefeld }, { A.} and {Naegel }, { B.} and { Passat }, N. and {Perret }, { B.}",

booktitle = "Mathematical Morphology and Its Applications to Signal and Image Processing",

note = "International Symposium on Mathematical Morphology, ISMM ; Conference date: 08-07-2019 Through 10-07-2019",

url = "http://ismm.uni-saarland.de/",

}

You, J , Trager, S & Wilkinson, MHF 2019, A Fast, Memory-Efficient Alpha-Tree Algorithm using Flooding and Tree Size Estimation. in B Burgeth , A Kleefeld , B Naegel , N Passat & B Perret (eds), Mathematical Morphology and Its Applications to Signal and Image Processing. Lecture Notes in Computer Science, vol. 11564, Springer, Cham, pp. 256-267, International Symposium on Mathematical Morphology, Saarbrücken, Saarland, Germany, 08/07/2019. https://doi.org/10.1007/978-3-030-20867-7_20

A Fast, Memory-Efficient Alpha-Tree Algorithm using Flooding and Tree Size Estimation. / You, Jiwoo ; Trager, Scott ; Wilkinson, M.H.F.
Mathematical Morphology and Its Applications to Signal and Image Processing. ed. / B. Burgeth ; A. Kleefeld ; B. Naegel ; N. Passat ; B. Perret . Cham: Springer, 2019. p. 256-267 (Lecture Notes in Computer Science; Vol. 11564).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - You, Jiwoo

AU - Trager, Scott

AU - Wilkinson, M.H.F.

N1 - Conference code: 14

PY - 2019/5/31

Y1 - 2019/5/31

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-20867-7_20

DO - 10.1007/978-3-030-20867-7_20

M3 - Conference contribution

SN - 978-3-030-20866-0

T3 - Lecture Notes in Computer Science

SP - 256

EP - 267

BT - Mathematical Morphology and Its Applications to Signal and Image Processing

A2 - Burgeth , B.

A2 - Kleefeld , A.

A2 - Naegel , B.

A2 - Passat , N.

A2 - Perret , B.

PB - Springer

CY - Cham

T2 - International Symposium on Mathematical Morphology

Y2 - 8 July 2019 through 10 July 2019

ER -

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

Abstract

Publication series

Conference

Access to Document

Handle.net

Fingerprint

Cite this