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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Heuristics for grey-weighted distance computations
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: Symposium on Image Analysis, Uppsala, March 11-12. Proceedings SSBA 2010., 2010Conference paper, Published paper (Other academic)
Abstract [en]

With new imaging techniques and computing power come increasing demands on the computation cost of image analysis algorithms. Grey-weighted distance transforms are traditionally computed using graph-based region-growing algorithms. These algorithms expand nodes in all directions by evolving an isotropic wave front. When calculating point-to-point distances, the isotropic propagation can be unnecessarily costly since it expands many nodes in directions away from the goal node. By introducing a heuristic to guide the search, the number of excessive nodes can be decreased. Here we introduce heuristics for computing Distance on Curved Spaces and Weighted Distance on Curved Spaces. We also examine the impact of these heuristics together with a heuristic previously proposed for fuzzy distance computations. The results show that the number of nodes expanded in point-to-point grey-weighted distances can be decreased by up to ~79%.

Place, publisher, year, edition, pages
2010.
National Category
Computer and Information Science
Research subject
Computerized Image Analysis
Identifiers
URN: urn:nbn:se:uu:diva-121572OAI: oai:DiVA.org:uu-121572DiVA: diva2:305768
Conference
SSBA 2010
Available from: 2010-03-25 Created: 2010-03-25 Last updated: 2011-03-11Bibliographically approved
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.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 727
Keyword
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
Identifiers
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)
Opponent
Supervisors
Available from: 2010-04-22 Created: 2010-03-25 Last updated: 2015-01-23Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Gedda, Magnus

Search in DiVA

By author/editor
Gedda, Magnus
By organisation
Computerized Image AnalysisCentre for Image Analysis
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 512 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf