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 voor dit werk

Onderzoeksoutput › Academic › peer review

1 Citaat (Scopus)

225 Downloads (Pure)

Samenvatting

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-2	English
Titel	Mathematical Morphology and Its Applications to Signal and Image Processing
Redacteuren	B. Burgeth , A. Kleefeld , B. Naegel , N. Passat , B. Perret
Plaats van productie	Cham
Uitgeverij	Springer
Pagina's	256-267
ISBN van elektronische versie	978-3-030-20867-7
ISBN van geprinte versie	978-3-030-20866-0
DOI's	https://doi.org/10.1007/978-3-030-20867-7_20
Status	Published - 31-mei-2019
Evenement	International Symposium on Mathematical Morphology - Saarland University, Saarbrücken, Germany Duur: 8-jul.-2019 → 10-jul.-2019 Congresnummer: 14 http://ismm.uni-saarland.de/

Publicatie series

Naam	Lecture Notes in Computer Science
Uitgeverij	Springer
Volume	11564

Conference

Conference	International Symposium on Mathematical Morphology
Verkorte titel	ISMM
Land/Regio	Germany
Stad	Saarbrücken
Periode	08/07/2019 → 10/07/2019
Internet adres	http://ismm.uni-saarland.de/

Toegang tot 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 KBLicentie: Taverne

Handle.net

Permanente koppeling

Citeer dit

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 (editors), Mathematical Morphology and Its Applications to Signal and Image Processing (blz. 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 (uitgave), Mathematical Morphology and Its Applications to Signal and Image Processing. Lecture Notes in Computer Science, vol. 11564, Springer, Cham, blz. 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. uitgave / B. Burgeth ; A. Kleefeld ; B. Naegel ; N. Passat ; B. Perret . Cham: Springer, 2019. blz. 256-267 (Lecture Notes in Computer Science; Vol. 11564).

Onderzoeksoutput › 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 -

You J , Trager S , Wilkinson MHF. A Fast, Memory-Efficient Alpha-Tree Algorithm using Flooding and Tree Size Estimation. In Burgeth B, Kleefeld A, Naegel B, Passat N, Perret B, redacteurs, Mathematical Morphology and Its Applications to Signal and Image Processing. Cham: Springer. 2019. blz. 256-267. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-20867-7_20

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

Samenvatting

Publicatie series

Conference

Toegang tot document

Handle.net

Vingerafdruk

Citeer dit