uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Revisiting priority queues for image analysis
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Centre for Image Analysis.
2010 (English)In: Pattern Recognition, ISSN 0031-3203, E-ISSN 1873-5142, Vol. 43, no 9, 3003-3012 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2010. Vol. 43, no 9, 3003-3012 p.
National Category
Engineering and Technology
URN: urn:nbn:se:uu:diva-125547DOI: 10.1016/j.patcog.2010.04.002ISI: 000279271800001OAI: oai:DiVA.org:uu-125547DiVA: diva2:320105
Available from: 2010-05-21 Created: 2010-05-21 Last updated: 2011-02-25Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Luengo Hendriks, Cris L.
By organisation
Computerized Image AnalysisCentre for Image Analysis
In the same journal
Pattern Recognition
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 197 hits
ReferencesLink to record
Permanent link

Direct link