Luengo, Cris
- Centre for Image Analysis, Sveriges lantbruksuniversitet
Sammanfattning
Many algorithms in image analysis require a priority queue, a data structure that holds pointers to pixels in the image, and which allows efficiently finding the pixel in the queue with the highest priority. However, very few articles describing such image analysis algorithms specify which implementation of the priority queue was used. Many assessments of priority queues can be found in the literature, but mostly in the context of numerical simulation rather than image analysis. Furthermore, due to the ever-changing characteristics of computing hardware, performance evaluated empirically 10 years ago is no longer relevant. In this paper I revisit priority queues as used in image analysis routines, evaluate their performance in a very general setting, and come to a very different conclusion than other authors: implicit heaps are the most efficient priority queues. At the same time. I propose a simple modification of the hierarchical queue (or bucket queue) that is more efficient than the implicit heap for extremely large queues. (C) 2010 Elsevier Ltd. All rights reserved.
Nyckelord
Image analysis; Priority queue; Heap; Binary search tree; AVL tree; Splay tree; Red-black tree; Ladder queue; Hierarchical heap; Grey-weighted distance transform; Watershed
Publicerad i
Pattern Recognition
2010, volym: 43, nummer: 9, sidor: 3003-3012
Utgivare: ELSEVIER SCI LTD
SLU författare
UKÄ forskningsämne
Datavetenskap (datalogi)
Publikationens identifierare
- DOI: https://doi.org/10.1016/j.patcog.2010.04.002
Permanent länk till denna sida (URI)
https://res.slu.se/id/publ/60779