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

Direct link
Algorithms for Grey-Weighted Distance Computations
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

With the increasing size of datasets and demand for real time response for interactive applications, improving runtime for algorithms with excessive computational requirements has become increasingly important. Many different algorithms combining efficient priority queues with various helper structures have been proposed for computing grey-weighted distance transforms. Here we compare the performance of popular competitive algorithms in different scenarios to form practical guidelines easy to adopt. The label-setting category of algorithms is shown to be the best choice for all scenarios. The hierarchical heap with a pointer array to keep track of nodes on the heap is shown to be the best choice as priority queue. However, if memory is a critical issue, then the best choice is the Dial priority queue for integer valued costs and the Untidy priority queue for real valued costs.

Keyword [en]
Grey-weighted distance, Geodesic time, Geodesic distance, Fuzzy distance, Algorithms, Region growing
Research subject
Computerized Image Analysis
URN: urn:nbn:se:uu:diva-121578OAI: oai:DiVA.org:uu-121578DiVA: diva2:305777
Available from: 2010-03-25 Created: 2010-03-25 Last updated: 2010-03-25
In thesis
1. Contributions to 3D Image Analysis using Discrete Methods and Fuzzy Techniques: With Focus on Images from Cryo-Electron Tomography
Open this publication in new window or tab >>Contributions to 3D Image Analysis using Discrete Methods and Fuzzy Techniques: With Focus on Images from Cryo-Electron Tomography
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

With the emergence of new imaging techniques, researchers are always eager to push the boundaries by examining objects either smaller or further away than what was previously possible. The development of image analysis techniques has greatly helped to introduce objectivity and coherence in measurements and decision making. It has become an essential tool for facilitating both large-scale quantitative studies and qualitative research. In this Thesis, methods were developed for analysis of low-resolution (in respect to the size of the imaged objects) three-dimensional (3D) images with low signal-to-noise ratios (SNR) applied to images from cryo-electron tomography (cryo-ET) and fluorescence microscopy (FM). The main focus is on methods of low complexity, that take into account both grey-level and shape information, to facilitate large-scale studies. Methods were developed to localise and represent complex macromolecules in images from cryo-ET. The methods were applied to Immunoglobulin G (IgG) antibodies and MET proteins. The low resolution and low SNR required that grey-level information was utilised to create fuzzy representations of the macromolecules. To extract structural properties, a method was developed to use grey-level-based distance measures to facilitate decomposition of the fuzzy representations into sub-domains. The structural properties of the MET protein were analysed by developing a analytical curve representation of its stalk. To facilitate large-scale analysis of structural properties of nerve cells, a method for tracing neurites in FM images using local path-finding was developed. Both theoretical and implementational details of computationally heavy approaches were examined to keep the time complexity low in the developed methods. Grey-weighted distance definitions and various aspects of their implementations were examined in detail to form guidelines on which definition to use in which setting and which implementation is the fastest. Heuristics were developed to speed up computations when calculating grey-weighted distances between two points. The methods were evaluated on both real and synthetic data and the results show that the methods provide a step towards facilitating large-scale studies of images from both cryo-ET and FM.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2010. 70 p.
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 727
digital image analysis, 3D, fuzzy, algorithms, grey-weighted distance, region growing, electron tomography, tracing, fluorescence microscopy
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computerized Image Analysis
urn:nbn:se:uu:diva-121579 (URN)978-91-554-7768-4 (ISBN)
Public defence
2010-05-20, Polhemsalen, Lägerhyddsvägen 1, Uppsala, 10:15 (English)
Available from: 2010-04-22 Created: 2010-03-25 Last updated: 2015-01-23Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Gedda, Magnus
By organisation
Computerized Image Analysis

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

Total: 219 hits
ReferencesLink to record
Permanent link

Direct link