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 Faster, Unbiased Path Opening by Upper Skeletonization and Weighted Adjacency Graphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Visual Information and Interaction. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computerized Image Analysis and Human-Computer Interaction.ORCID iD: 0000-0002-0612-558X
Flagship Biosci Inc, Westminster, CO 80021 USA.
2016 (English)In: IEEE Transactions on Image Processing, ISSN 1057-7149, E-ISSN 1941-0042, Vol. 25, no 12, p. 5589-5600Article in journal (Refereed) Published
Abstract [en]

The path opening is a filter that preserves bright regions in the image in which a path of a certain length L fits. A path is a (not necessarily straight) line defined by a specific adjacency relation. The most efficient implementation known scales as O(min(L, d, Q)N) with the length of the path, L, the maximum possible path length, d, the number of graylevels, Q, and the image size, N. An approximation exists (parsimonious path opening) that has an execution time independent of path length. This is achieved by preselecting paths, and applying 1D openings along these paths. However, the preselected paths can miss important structures, as described by its authors. Here, we propose a different approximation, in which we preselect paths using a grayvalue skeleton. The skeleton follows all ridges in the image, meaning that no important line structures will be missed. An H-minima transform simplifies the image to reduce the number of branches in the skeleton. A graph-based version of the traditional path opening operates only on the pixels in the skeleton, yielding speedups up to one order of magnitude, depending on image size and filter parameters. The edges of the graph are weighted in order to minimize bias. Experiments show that the proposed algorithm scales linearly with image size, and that it is often slightly faster for longer paths than for shorter paths. The algorithm also yields the most accurate results- as compared with a number of path opening variants-when measuring length distributions.

Place, publisher, year, edition, pages
2016. Vol. 25, no 12, p. 5589-5600
Keywords [en]
graph theory, image filtering, transforms, 1D openings, H-minima transform, filter parameters, graph edges, grayvalue skeleton, image analysis, image filtering, image size, unbiased path opening, upper skeletonization, weighted adjacency graphs, Approximation algorithms, Gray-scale, Image edge detection, Length measurement, Periodic structures, Skeleton, Transforms, Path opening, granulometry, image analysis, length distribution, line segment, mathematical morphology, unbiased
National Category
Other Computer and Information Science
Research subject
Computerized Image Processing
Identifiers
URN: urn:nbn:se:uu:diva-309087DOI: 10.1109/TIP.2016.2609805ISI: 000388205100007OAI: oai:DiVA.org:uu-309087DiVA, id: diva2:1051614
Funder
Swedish Research Council, 2014-5983Available from: 2016-12-02 Created: 2016-12-02 Last updated: 2019-10-17Bibliographically approved
In thesis
1. Precise Image-Based Measurements through Irregular Sampling
Open this publication in new window or tab >>Precise Image-Based Measurements through Irregular Sampling
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[sv]
Noggranna bildbaserade mätningar via irreguljär sampling
Abstract [en]

Mathematical morphology is a theory that is applicable broadly in signal processing, but in this thesis we focus mainly on image data. Fundamental concepts of morphology include the structuring element and the four operators: dilation, erosion, closing, and opening. One way of thinking about the role of the structuring element is as a probe, which traverses the signal (e.g. the image) systematically and inspects how well it "fits" in a certain sense that depends on the operator.

Although morphology is defined in the discrete as well as in the continuous domain, often only the discrete case is considered in practice. However, commonly digital images are a representation of continuous reality and thus it is of interest to maintain a correspondence between mathematical morphology operating in the discrete and in the continuous domain. Therefore, much of this thesis investigates how to better approximate continuous morphology in the discrete domain. We present a number of issues relating to this goal when applying morphology in the regular, discrete case, and show that allowing for irregularly sampled signals can improve this approximation, since moving to irregularly sampled signals frees us from constraints (namely those imposed by the sampling lattice) that harm the correspondence in the regular case. The thesis develops a framework for applying morphology in the irregular case, using a wide range of structuring elements, including non-flat structuring elements (or structuring functions) and adaptive morphology. This proposed framework is then shown to better approximate continuous morphology than its regular, discrete counterpart.

Additionally, the thesis contains work dealing with regularly sampled images using regular, discrete morphology and weighting to improve results. However, these cases can be interpreted as specific instances of irregularly sampled signals, thus naturally connecting them to the overarching theme of irregular sampling, precise measurements, and mathematical morphology.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2019. p. 63
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1869
Keywords
image analysis, image processing, mathematical morphology, irregular sampling, adaptive morphology, missing samples, continuous morphology, path opening.
National Category
Signal Processing Other Computer and Information Science
Research subject
Computerized Image Processing
Identifiers
urn:nbn:se:uu:diva-395205 (URN)978-91-513-0783-1 (ISBN)
Public defence
2019-12-06, Room 2446, ITC, Lägerhyddsvägen 2, Uppsala, 13:00 (English)
Opponent
Supervisors
Funder
Swedish Research Council, 2014-5983
Available from: 2019-11-13 Created: 2019-10-17 Last updated: 2019-11-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

By author/editor
Asplund, Teo
By organisation
Division of Visual Information and InteractionComputerized Image Analysis and Human-Computer Interaction
In the same journal
IEEE Transactions on Image Processing
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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