Change search
ReferencesLink to record
Permanent link

Direct link
Graph-based Methods for Interactive 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.
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 [en]
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: urn:nbn:se:uu:diva-149261ISBN: 978-91-554-8037-0OAI: oai:DiVA.org:uu-149261DiVA: diva2:405534
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
List of papers
1. A 3D live-wire segmentation method for volume images using haptic interaction
Open this publication in new window or tab >>A 3D live-wire segmentation method for volume images using haptic interaction
2006 (English)In: DISCRETE GEOMETRY FOR COMPUTER IMAGERY, PROCEEDINGS 4245, 2006, 663-673 p.Conference paper (Refereed)
Abstract [en]

Designing interactive segmentation methods for digital volume images is difficult, mainly because efficient 3D interaction is much

harder to achieve than interaction with 2D images. To overcome this issue, we use a system that combines stereo graphics and haptics to facilitate efficient 3D interaction. We propose a new method, based on the 2D live-wire method, for segmenting volume images. Our method consists of two parts: an interface for drawing 3D live-wire curves onto the boundary of an object in a volume image, and an algorithm for connecting two such curves to create a discrete surface.

Identifiers
urn:nbn:se:uu:diva-19901 (URN)0302-9743 (ISBN)
Available from: 2006-12-04 Created: 2006-12-04 Last updated: 2011-05-05
2. Minimal Cost-Path for Path-Based Distances
Open this publication in new window or tab >>Minimal Cost-Path for Path-Based Distances
2007 (English)In: Proceedings of 5th International Symposium on Image and Signal Processing and Analysis (ISPA 2007), 2007, 379-384 p.Conference paper (Refereed)
Abstract [en]

Distance functions defined by the minimal cost-path using weights and neighbourhood sequences (n.s.) are considered for the constrained distance transform (CDT). The CDT is then used to find one minimal cost-path between two points. The behaviour of some path-based distance functions is analyzed and a new error function is introduced. It is concluded that the weighted n.s.-distance with two weights (3 x 3 neighbourhood) and the weighted distance with three weights (5 x 5 neighbourhood) have similar properties in terms of minimal cost-path computation, while the former is more efficient to compute.

National Category
Computer Vision and Robotics (Autonomous Systems)
Identifiers
urn:nbn:se:uu:diva-12585 (URN)doi:10.1109/ISPA.2007.4383723 (DOI)978-953-184-116-0 (ISBN)
Available from: 2008-01-07 Created: 2008-01-07 Last updated: 2011-05-05
3. Sub-pixel Segmentation with the Image Foresting Transform
Open this publication in new window or tab >>Sub-pixel Segmentation with the Image Foresting Transform
2009 (English)In: Proceedings of International Workshop on Combinatorial Image Analysis: IWCIA 2009, Springer , 2009, 201-211 p.Conference paper (Refereed)
Abstract [en]

The Image Foresting Transform (IFT) is a framework forimage partitioning, commonly used for interactive segmentation. Givenan image where a subset of the image elements (seed-points) have beenassigned user-defined labels, the IFT completes the labeling by computingminimal cost paths from all image elements to the seed-points. Eachimage element is then given the same label as the closest seed-point. Inits original form, the IFT produces crisp segmentations, i.e., each imageelement is assigned the label of exactly one seed-point. Here, we proposea modified version of the IFT that computes region boundaries withsub-pixel precision by allowing mixed labels at region boundaries. Wedemonstrate that the proposed sub-pixel IFT allows properties of thesegmented object to be measured with higher precision.

Place, publisher, year, edition, pages
Springer, 2009
Series
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5852
Keyword
Image foresting transform, Interactive image segmentation, Sub-pixel precision
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computerized Image Analysis
Identifiers
urn:nbn:se:uu:diva-111261 (URN)10.1007/978-3-642-10210-3_16 (DOI)978-3-642-10208-0 (ISBN)
Available from: 2009-12-08 Created: 2009-12-08 Last updated: 2016-01-08Bibliographically approved
4. Relaxed Image Foresting Transforms for Interactive Volume Image Segmentation
Open this publication in new window or tab >>Relaxed Image Foresting Transforms for Interactive Volume Image Segmentation
Show others...
2010 (English)In: MEDICAL IMAGING 2010: IMAGE PROCESSING / [ed] Dawant BM, Haynor DR, 2010, Vol. 7623Conference paper (Refereed)
Abstract [en]

The image Foresting (IFT) is a framework for image partitioning, commonly used for interactive segmentation. Given an image where a subset of the image elements (seed-points) have been assigned correct segmentation labels, the IFT completes the labeling by computing minimal cost paths from all image elements to the seed-points. Each image element is then given the same label as the closest seed-point. Here, we propose the relaxed IFT (RIFT). This modified version of the IFT features an additional parameter to control the smoothness of the segmentation boundary. The RIFT yields more intuitive segmentation results in the presence of noise and weak edges, while maintaining a low computational complexity. We show an application of the method to the refinement of manual segmentations of a thoracolumbar muscle in magnetic resonance images. The performed study shows that the refined segmentations are qualitatively similar to the manual segmentations, while intra-user variations are reduced by more than 50%.

Series
, Proceedings of SPIE-The International Society for Optical Engineering, ISSN 0277-786X ; 7623
Keyword
Seeded segmentation, Interactive segmentation, Minimum cost paths, Image Foresting Transform
National Category
Medical and Health Sciences Computer Science
Identifiers
urn:nbn:se:uu:diva-140957 (URN)10.1117/12.840019 (DOI)000285048800137 ()978-0-8194-8024-8 (ISBN)
Conference
Conference on Medical Imaging 2010 - Image Processing San Diego, CA, FEB 14-16, 2010
Available from: 2011-01-10 Created: 2011-01-10 Last updated: 2016-01-08Bibliographically approved
5. A Graph-based Framework for Sub-pixel Image Segmentation
Open this publication in new window or tab >>A Graph-based Framework for Sub-pixel Image Segmentation
2011 (English)In: Theoretical Computer Science, ISSN 0304-3975, 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.

Keyword
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:nbn:se:uu:diva-149256 (URN)10.1016/j.tcs.2010.11.030 (DOI)000288420900005 ()
Available from: 2011-03-16 Created: 2011-03-16 Last updated: 2011-07-18Bibliographically approved
6. Image Foresting Transform: On-the-fly Computation of Segmentation Boundaries
Open this publication in new window or tab >>Image Foresting Transform: On-the-fly Computation of Segmentation Boundaries
2011 (English)In: Image Analysis: 17th Scandinavian Conference, SCIA 2011, Springer , 2011Conference paper (Refereed)
Abstract [en]

The Image Foresting Transform (IFT) is a framework for seeded image segmentation, based on the computation of minimal cost paths in a discrete representation of an image. In two recent publications, we have shown that the segmentations obtained by the IFT may be improved by refining the segmentation locally around the boundariesbetween segmented regions. Since these methods operate on a small subset of the image elements only, they may be implemented efficiently if the set of boundary elements is known. Here, we show that this set maybe obtained on-the-fly, at virtually no additional cost, as a by-product of the IFT algorithm.

Place, publisher, year, edition, pages
Springer, 2011
Series
, Lecture notes in computer science
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computerized Image Analysis; Computerized Image Processing
Identifiers
urn:nbn:se:uu:diva-149260 (URN)
Available from: 2011-03-16 Created: 2011-03-16 Last updated: 2011-05-05Bibliographically approved
7. Generalized Hard Constraints for Graph Segmentation
Open this publication in new window or tab >>Generalized Hard Constraints for Graph Segmentation
2011 (English)In: Image Analysis, 17th Scandinavian Conference. SCIA 2011., Springer , 2011Conference paper (Refereed)
Abstract [en]

Graph-based methods have become well-established tools for image segmentation. Viewing the image as a weighted graph, these methods seek to extract a graph cut that best matches the image content.Many of these methods are interactive, in that they allow a human operator to guide the segmentation process by specifying a set of hard constraints that the cut must satisfy. Typically, these constraints are given in one of two forms: regional constraints (a set of vertices that must be separated by the cut) or boundary constraints (a set of edges that must be included in the cut). Here, we propose a new type of hard constraints,that includes both regional constraints and boundary constraints as special cases. We also present an efficient method for computing cuts that satisfy a set of generalized constraints, while globally minimizing a graph-cut measure.

Place, publisher, year, edition, pages
Springer, 2011
Series
, Lecture Notes in Computer Science
National Category
Computer Vision and Robotics (Autonomous Systems)
Research subject
Computerized Image Analysis; Computerized Image Processing
Identifiers
urn:nbn:se:uu:diva-149259 (URN)
Available from: 2011-03-16 Created: 2011-03-16 Last updated: 2016-01-08Bibliographically approved

Open Access in DiVA

fulltext(2482 kB)1845 downloads
File information
File name FULLTEXT01.pdfFile size 2482 kBChecksum SHA-512
1f0f1230176ce7d3b13fc83271a47edcb1fe3f75bbefe1be127e30fb03f9a4804bcf9f77f7f5a1ba6d15b3fd8874f9d84b2cea860bd6f41de344155f2a5e90f2
Type fulltextMimetype application/pdf
Buy this publication >>

Search in DiVA

By author/editor
Malmberg, Filip
By organisation
Centre for Image AnalysisComputerized Image Analysis and Human-Computer Interaction
Computer Vision and Robotics (Autonomous Systems)

Search outside of DiVA

GoogleGoogle Scholar
Total: 1845 downloads
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: 1283 hits
ReferencesLink to record
Permanent link

Direct link