A Fast Alpha-tree Algorithm for Extreme Dynamic Range Pixel Dissimilarities

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

doi:10.1109/TPAMI.2023.3341721

A Fast Alpha-tree Algorithm for Extreme Dynamic Range Pixel Dissimilarities

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

236 Downloads (Pure)

Abstract

The α-tree algorithm is a useful hierarchical representation technique which facilitates comprehension of images
such as remote sensing and medical images. Most α-tree algorithms make use of priority queues to process image edges
in a correct order, but because traditional priority queues are
inefficient in α-tree algorithms using extreme-dynamic-range
pixel dissimilarities, they run slower compared with other related
algorithms such as component tree. In this paper, we propose
a novel hierarchical heap priority queue algorithm that can
process α-tree edges much more efficiently than other stateof-the-art priority queues. Experimental results using 48-bit
Sentinel-2A remotely sensed images and randomly generated
images have shown that the proposed hierarchical heap priority
queue improved the timings of the flooding α-tree algorithm by
replacing the heap priority queue with the proposed queue: 1.68
times in 4-N and 2.41 times in 8-N on Sentinel-2A images, and
2.56 times and 4.43 times on randomly generated images.

Original language	English
Pages (from-to)	3199-3212
Number of pages	14
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	46
Issue number	5
Early online date	12-Dec-2023
DOIs	https://doi.org/10.1109/TPAMI.2023.3341721
Publication status	Published - 5-May-2024

Access to Document

10.1109/TPAMI.2023.3341721

A Fast Alpha-Tree Algorithm for Extreme Dynamic Range Pixel DissimilaritiesFinal publisher's version, 2.08 MBLicence: Taverne

Handle.net

Persistent link

Cite this

@article{d67a0a119ed2412f98a957d9b5c46175,

title = "A Fast Alpha-tree Algorithm for Extreme Dynamic Range Pixel Dissimilarities",

abstract = "The α-tree algorithm is a useful hierarchical representation technique which facilitates comprehension of imagessuch as remote sensing and medical images. Most α-tree algorithms make use of priority queues to process image edgesin a correct order, but because traditional priority queues areinefficient in α-tree algorithms using extreme-dynamic-rangepixel dissimilarities, they run slower compared with other relatedalgorithms such as component tree. In this paper, we proposea novel hierarchical heap priority queue algorithm that canprocess α-tree edges much more efficiently than other stateof-the-art priority queues. Experimental results using 48-bitSentinel-2A remotely sensed images and randomly generatedimages have shown that the proposed hierarchical heap priorityqueue improved the timings of the flooding α-tree algorithm byreplacing the heap priority queue with the proposed queue: 1.68times in 4-N and 2.41 times in 8-N on Sentinel-2A images, and2.56 times and 4.43 times on randomly generated images.",

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

year = "2024",

month = may,

day = "5",

doi = "10.1109/TPAMI.2023.3341721",

language = "English",

volume = "46",

pages = "3199--3212",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

publisher = "IEEE COMPUTER SOC",

number = "5",

}

TY - JOUR

T1 - A Fast Alpha-tree Algorithm for Extreme Dynamic Range Pixel Dissimilarities

AU - Ryu, Jiwoo

AU - Trager, Scott

AU - Wilkinson, M.H.F.

PY - 2024/5/5

Y1 - 2024/5/5

N2 - The α-tree algorithm is a useful hierarchical representation technique which facilitates comprehension of imagessuch as remote sensing and medical images. Most α-tree algorithms make use of priority queues to process image edgesin a correct order, but because traditional priority queues areinefficient in α-tree algorithms using extreme-dynamic-rangepixel dissimilarities, they run slower compared with other relatedalgorithms such as component tree. In this paper, we proposea novel hierarchical heap priority queue algorithm that canprocess α-tree edges much more efficiently than other stateof-the-art priority queues. Experimental results using 48-bitSentinel-2A remotely sensed images and randomly generatedimages have shown that the proposed hierarchical heap priorityqueue improved the timings of the flooding α-tree algorithm byreplacing the heap priority queue with the proposed queue: 1.68times in 4-N and 2.41 times in 8-N on Sentinel-2A images, and2.56 times and 4.43 times on randomly generated images.

AB - The α-tree algorithm is a useful hierarchical representation technique which facilitates comprehension of imagessuch as remote sensing and medical images. Most α-tree algorithms make use of priority queues to process image edgesin a correct order, but because traditional priority queues areinefficient in α-tree algorithms using extreme-dynamic-rangepixel dissimilarities, they run slower compared with other relatedalgorithms such as component tree. In this paper, we proposea novel hierarchical heap priority queue algorithm that canprocess α-tree edges much more efficiently than other stateof-the-art priority queues. Experimental results using 48-bitSentinel-2A remotely sensed images and randomly generatedimages have shown that the proposed hierarchical heap priorityqueue improved the timings of the flooding α-tree algorithm byreplacing the heap priority queue with the proposed queue: 1.68times in 4-N and 2.41 times in 8-N on Sentinel-2A images, and2.56 times and 4.43 times on randomly generated images.

U2 - 10.1109/TPAMI.2023.3341721

DO - 10.1109/TPAMI.2023.3341721

M3 - Article

SN - 0162-8828

VL - 46

SP - 3199

EP - 3212

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 5

ER -

A Fast Alpha-tree Algorithm for Extreme Dynamic Range Pixel Dissimilarities

Abstract

Access to Document

Handle.net

Fingerprint

Cite this