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
A Graph-based Framework for Sub-pixel Image Segmentation
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Centre for Image Analysis. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis and Human-Computer Interaction.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Centre for Image Analysis.
Faculty of Technical Sciences, University of Novi Sad.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Centre for Image Analysis. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis and Human-Computer Interaction.
2011 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 412, no 15, 1338-1349 p.Article in journal (Refereed) Published
Abstract [en]

Many image segmentation methods utilize graph structures for representing images, where the flexibility and generality of the abstract structure is beneficial. By using a fuzzy object representation, i.e., allowing partial belongingness of elements to image objects, the unavoidable loss of information when representing continuous structures by finite sets is significantly reduced,enabling feature estimates with sub-pixel precision.This work presents a framework for object representation based on fuzzysegmented graphs. Interpreting the edges as one-dimensional paths betweenthe vertices of a graph, we extend the notion of a graph cut to that of a located cut, i.e., a cut with sub-edge precision. We describe a method for computing a located cut from a fuzzy segmentation of graph vertices. Further,the notion of vertex coverage segmentation is proposed as a graph theoretic equivalent to pixel coverage segmentations and a method for computing such a segmentation from a located cut is given. Utilizing the proposed framework,we demonstrate improved precision of area measurements of synthetic two-dimensional objects. We emphasize that although the experiments presented here are performed on two-dimensional images, the proposed framework is defined for general graphs and thus applicable to images of any dimension.

Place, publisher, year, edition, pages
2011. Vol. 412, no 15, 1338-1349 p.
Keyword [en]
Image segmentation, Graph labeling, Graph cuts, Coverage segmentation, Sub-pixel segmentation, Feature estimation
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computerized Image Analysis; Computerized Image Processing
Identifiers
URN: urn:nbn:se:uu:diva-149256DOI: 10.1016/j.tcs.2010.11.030ISI: 000288420900005OAI: oai:DiVA.org:uu-149256DiVA: diva2:404323
Available from: 2011-03-16 Created: 2011-03-16 Last updated: 2017-12-11Bibliographically approved
In thesis
1. Graph-based Methods for Interactive Image Segmentation
Open this publication in new window or tab >>Graph-based Methods for Interactive Image Segmentation
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The subject of digital image analysis deals with extracting relevant information from image data, stored in digital form in a computer. A fundamental problem in image analysis is image segmentation, i.e., the identification and separation of relevant objects and structures in an image. Accurate segmentation of objects of interest is often required before further processing and analysis can be performed.

Despite years of active research, fully automatic segmentation of arbitrary images remains an unsolved problem. Interactive, or semi-automatic, segmentation methods use human expert knowledge as additional input, thereby making the segmentation problem more tractable. The goal of interactive segmentation methods is to minimize the required user interaction time, while maintaining tight user control to guarantee the correctness of the results. Methods for interactive segmentation typically operate under one of two paradigms for user guidance: (1) Specification of pieces of the boundary of the desired object(s). (2) Specification of correct segmentation labels for a small subset of the image elements. These types of user input are referred to as boundary constraints and regional constraints, respectively.

This thesis concerns the development of methods for interactive segmentation, using a graph-theoretic approach. We view an image as an edge weighted graph, whose vertex set is the set of image elements, and whose edges are given by an adjacency relation among the image elements. Due to its discrete nature and mathematical simplicity, this graph based image representation lends itself well to the development of efficient, and provably correct, methods.

The contributions in this thesis may be summarized as follows:

  • Existing graph-based methods for interactive segmentation are modified to improve their performance on images with noisy or missing data, while maintaining a low computational cost.
  • Fuzzy techniques are utilized to obtain segmentations from which feature measurements can be made with increased precision.
  • A new paradigm for user guidance, that unifies and generalizes regional and boundary constraints, is proposed.

The practical utility of the proposed methods is illustrated with examples from the medical field.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2011. 61 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 813
Keyword
Digital image analysis, Interactive image segmentation, Fuzzy image segmentation, Image foresting transform, Graph labeling, Graph cuts
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computerized Image Processing
Identifiers
urn:nbn:se:uu:diva-149261 (URN)978-91-554-8037-0 (ISBN)
Public defence
2011-05-06, Häggsalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 10:15 (English)
Opponent
Supervisors
Available from: 2011-04-14 Created: 2011-03-16 Last updated: 2014-07-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Malmberg, FilipLindblad, JoakimNyström, Ingela

Search in DiVA

By author/editor
Malmberg, FilipLindblad, JoakimNyström, Ingela
By organisation
Centre for Image AnalysisComputerized Image Analysis and Human-Computer Interaction
In the same journal
Theoretical Computer Science
Computer Vision and Robotics (Autonomous Systems)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 514 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