Topographical Tools for Filtering and Segmentation 1: Watersheds on Node- or Edge-weighted Graphs
()
About this ebook
Mathematical morphology has developed a powerful methodology for segmenting images, based on connected filters and watersheds. We have chosen the abstract framework of node- or edge-weighted graphs for an extensive mathematical and algorithmic description of these tools.
Volume 1 is devoted to watersheds. The topography of a graph appears by observing the evolution of a drop of water moving from node to node on a weighted graph, along flowing paths, until it reaches regional minima. The upstream nodes of a regional minimum constitute its catchment zone.
The catchment zones may be constructed independently of each other and locally, in contrast with the traditional approach where the catchment basins have to be constructed all at the same time. Catchment zones may overlap, and thus, a new segmentation paradigm is proposed in which catchment zones cover each other according to a priority order. The resulting partition may then be corrected, by local and parallel treatments, in order to achieve the desired precision.
Related to Topographical Tools for Filtering and Segmentation 1
Related ebooks
Topographical Tools for Filtering and Segmentation 2: Flooding and Marker-based Segmentation on Node- or Edge-weighted Graphs Rating: 0 out of 5 stars0 ratingsTurbulent Fluid Flow Rating: 0 out of 5 stars0 ratingsDiscrete Mechanics: Concepts and Applications Rating: 0 out of 5 stars0 ratingsSolving Partial Differential Equation Applications with PDE2D Rating: 0 out of 5 stars0 ratingsAdvances in Contact Angle, Wettability and Adhesion, Volume 3 Rating: 0 out of 5 stars0 ratingsFluid Mechanics: Analytical Methods Rating: 0 out of 5 stars0 ratingsBasic Geological Mapping Rating: 2 out of 5 stars2/5Foundations of Image Science Rating: 0 out of 5 stars0 ratingsCommunication Systems Principles Using MATLAB Rating: 0 out of 5 stars0 ratingsFluid Mechanics in Channel, Pipe and Aerodynamic Design Geometries 2 Rating: 0 out of 5 stars0 ratingsModern Aerodynamic Methods for Direct and Inverse Applications Rating: 0 out of 5 stars0 ratingsThe Mediterranean Sea: Temporal Variability and Spatial Patterns Rating: 0 out of 5 stars0 ratingsBridge Design: Concepts and Analysis Rating: 5 out of 5 stars5/5The Topology of Chaos: Alice in Stretch and Squeezeland Rating: 0 out of 5 stars0 ratingsMaterials Science and Technology of Optical Fabrication Rating: 0 out of 5 stars0 ratingsAdvanced Topological Insulators Rating: 0 out of 5 stars0 ratingsSeismic Inversion: Theory and Applications Rating: 0 out of 5 stars0 ratingsDesign and Analysis of Centrifugal Compressors Rating: 0 out of 5 stars0 ratingsAn Introduction to Synchrotron Radiation: Techniques and Applications Rating: 0 out of 5 stars0 ratingsAdvanced Graph Theory and Combinatorics Rating: 0 out of 5 stars0 ratingsThematic Cartography, Cartography and the Impact of the Quantitative Revolution Rating: 0 out of 5 stars0 ratingsIntroduction to Detonation Theory Rating: 0 out of 5 stars0 ratingsSoils as a Key Component of the Critical Zone 3: Soils and Water Circulation Rating: 0 out of 5 stars0 ratingsResistivity Modeling: Propagation, Laterolog and Micro-Pad Analysis Rating: 0 out of 5 stars0 ratingsInteractions on Digital Tablets in the Context of 3D Geometry Learning Rating: 0 out of 5 stars0 ratingsDiscrete Fourier Analysis and Wavelets: Applications to Signal and Image Processing Rating: 0 out of 5 stars0 ratingsQGIS and Applications in Water and Risks Rating: 0 out of 5 stars0 ratingsInfrared Observation of Earth's Atmosphere Rating: 0 out of 5 stars0 ratings3D Modeling of Nonlinear Wave Phenomena on Shallow Water Surfaces Rating: 0 out of 5 stars0 ratingsMulti-modality Cardiac Imaging: Processing and Analysis Rating: 0 out of 5 stars0 ratings
Technology & Engineering For You
The Big Book of Hacks: 264 Amazing DIY Tech Projects Rating: 4 out of 5 stars4/5The Big Book of Maker Skills: Tools & Techniques for Building Great Tech Projects Rating: 4 out of 5 stars4/5Electrical Engineering 101: Everything You Should Have Learned in School...but Probably Didn't Rating: 5 out of 5 stars5/5The Art of War Rating: 4 out of 5 stars4/5The ChatGPT Millionaire Handbook: Make Money Online With the Power of AI Technology Rating: 0 out of 5 stars0 ratingsThe Insider's Guide to Technical Writing Rating: 0 out of 5 stars0 ratingsUltralearning: Master Hard Skills, Outsmart the Competition, and Accelerate Your Career Rating: 4 out of 5 stars4/5Smart Phone Dumb Phone: Free Yourself from Digital Addiction Rating: 0 out of 5 stars0 ratingsThe 48 Laws of Power in Practice: The 3 Most Powerful Laws & The 4 Indispensable Power Principles Rating: 5 out of 5 stars5/580/20 Principle: The Secret to Working Less and Making More Rating: 5 out of 5 stars5/5My Inventions: The Autobiography of Nikola Tesla Rating: 4 out of 5 stars4/5The CIA Lockpicking Manual Rating: 5 out of 5 stars5/5Artificial Intelligence: A Guide for Thinking Humans Rating: 4 out of 5 stars4/5U.S. Marine Close Combat Fighting Handbook Rating: 4 out of 5 stars4/5How to Disappear and Live Off the Grid: A CIA Insider's Guide Rating: 0 out of 5 stars0 ratingsLogic Pro X For Dummies Rating: 0 out of 5 stars0 ratingsUnderstanding Media: The Extensions of Man Rating: 4 out of 5 stars4/5The Systems Thinker: Essential Thinking Skills For Solving Problems, Managing Chaos, Rating: 4 out of 5 stars4/5The Total Motorcycling Manual: 291 Essential Skills Rating: 5 out of 5 stars5/5The Fast Track to Your Technician Class Ham Radio License: For Exams July 1, 2022 - June 30, 2026 Rating: 5 out of 5 stars5/5The Invisible Rainbow: A History of Electricity and Life Rating: 4 out of 5 stars4/5Broken Money: Why Our Financial System is Failing Us and How We Can Make it Better Rating: 5 out of 5 stars5/5The Official Highway Code: DVSA Safe Driving for Life Series Rating: 3 out of 5 stars3/5The Art of War Rating: 4 out of 5 stars4/5Ghost Rider: Travels on the Healing Road Rating: 4 out of 5 stars4/5
Reviews for Topographical Tools for Filtering and Segmentation 1
0 ratings0 reviews
Book preview
Topographical Tools for Filtering and Segmentation 1 - Fernand Meyer
Notations
Volume 1
Mathematical notions
Weighted graphs
Subtracting an erosion from a dilation produces various gradient operators:
Flowing graphs
The topography of digraphs
Measuring the steepness of flowing paths
Pruning a flow digraph
Constructing an ∞ – steep digraph by flooding
Creating steep watershed partitions
An historical intermezzo
Encoding the digraph associated with an image
Volume 2
Modeling flooding
Lakes and regional minima
Among all flooding, choosing one
Flooding and flooding distances
Graph flooding via dendrograms
Minimum spanning forests and watershed partitions
Marker-based segmentation
Introduction
General organization
This book is divided into two volumes, which are dedicated to morphological segmentation. Morphological segmentation mainly relies on the watershed transform. The contours of an image to be segmented appear as the watershed lines of its gradient image. However, as each regional minimum of the gradient image is surrounded by a watershed line, the image is often oversegmented and the segmentation has to be regularized. Another operator floods
the gradient image and allows some regional minima to disappear. The new watershed lines of the flooded surface are less numerous, and if the flooding is appropriate, they will adequately represent the contours of the image. This book analyzes in depth watersheds and the flooding of images, and shows how to combine them in order to produce meaningful segmentations.
Any gray tone image may be considered as a topographic surface, with the altitude at each location of the surface being equal to the gray tone at the same location in the image. The highest points of the surface then correspond to the brightest points in the image. Thanks to this analogy several topographic concepts, such as regional minima and catchment zones, may be transposed to images. Quite similarly to topographic surfaces, images may be flooded.
All concepts and algorithms of this work derive from a physical model for flows and floods on a topographic surface. A drop of water deposited on a surface glides down until reaching a regional minimum and belongs to the catchment zone of this minimum. The physical model enables us to describe the possible trajectories of a drop of water. Similarly, flooding a topographic surface creates lakes, which are flat zones under which the underlying surface characteristics have completely vanished. The topography of a flooded surface thus differs from the initial topography with less minima and fewer catchment zones.
Now, instead of modeling these phenomena on gray tone images, we have chosen the abstract framework of weighted graphs, which open a large field of applications. Comparing and confronting the properties of node-weighted and edge-weighted graphs will be an endless source of inspiration and of new ideas and algorithms.
Each of the two volumes of this book broadly covers one physical model: the first deals with flows, while the second deals with floods.
Topographical Tools for Filtering and Segmentation 1: Watersheds on Node- or Edge-weighted Graphs analyzes the topography of a surface by observing the possible trajectories of a drop of water on the surface. From the observation of flows, it derives the notions of regional minima, catchment zones, upstream and downstream, etc. The volume ends by showing catchment zones that may be used for segmenting images.
Part 1 of Topographical Tools for Filtering and Segmentation 2: Floodings and Marker-based Segmentation on Node- or Edge weighted Graphs analyzes the evolution of a topographic surface when it is flooded. Part 2 of the volume is devoted to real-life applications, involving both flows and floods. The first application explores whether the rather abstract concepts and algorithms developed on graphs successfully describes a real hydrographic basin represented by a digital elevation model. The floods help correct the measurement errors of the model, and the flows enable us to detect and describe the structure of the rivers. The second application deals with marker-based segmentation, which corresponds to the everyday practice of morphological segmentation. Several markers are defined in an image and the associated segmentation creates a partition in which each region contains a marker and corresponds to the catchment basin of a flooded surface.
Let us now give an overview of both volumes.
Outline of volume 1
The Introduction gives an outline of both volumes and is followed by four main parts.
Part 1. Getting started
Part 1 primes the topic incorporating a literature review and some useful mathematical concepts.
Chapter 1 presents a primer for non-specialists in mathematical morphology, explaining why watersheds and flooding are so valuable in image processing. Chapter 2 explains how the practice of morphological segmentation progressively emerged and evolved over the last 50 years. Chapter 3 presents several useful mathematical definitions which will be used later. This chapter focuses on the adjunction, which is the cornerstone of mathematical morphology, linking erosion and dilation and generating closings and openings. Throughout the book, we will encounter an adjunction between the node and edge weights on weighted graphs. This adjunction plays a crucial role in proving the equivalence of both types of graphs with respect to watersheds and to some extent with respect to flooding.
Part 2. The topography of weighted graphs
This part contains Chapters 4–6. It describes the topography of graphs and digraphs in relation to the possible trajectories of a drop of water evolving from node to node.
Chapter 4 revises weighted graphs. The keyword of the book is topography. In order to deal with watersheds, we study the topography of a graph in relation to its node or edge weights. In order to deal with flooding, we study the topography at several levels: the topography of the graphs themselves and the topography of flooded graphs in relation to the topography of the graph. More importantly, we study the topography of the highest flooding below a ceiling function, and how it relates to the topography of the graph, on the one hand, and that of the ceiling function, on the other hand. Chapter 4 separately studies the topography of node- and edge-weighted graphs, defining for each the flowing edges, flowing paths, regional minima and catchment zones. It turns out that the behavior of a drop of water is highly similar in both node-and edge-weighted graphs.
Chapter 5 explores the deep similarities between the two types of graphs with regard to the watersheds. In a node-weighted graph, a flowing edge links each node with its neighbors whose weight is lower or equal. Hence, each edge is the flowing edge of one of its extremities, or of both; it may then unambiguously take the weight of this extremity. The operator that assigns nodes to each edge the weight of its highest extremity is a dilation, which is denoted by δen. The adjunct erosion appears for an edge-weighted graph, in which the nodes are not initially weighted. The flowing edges of a node are its adjacent edges with the smallest weight. Each node has at least one flowing edge, and may be unambiguously assigned the weight of this edge. This second operator is an erosion, which is denoted by εne, between the edge and node weights, with each node being assigned the weight of its lowest edges.
However, in an edge-weighted graph, edges may exist that are not the lowest edge of one of their extremities. Such edges are not flowing edges of the graph and do not belong to the trajectory of a drop of water deposited at one of the nodes. In a node-weighted graph, nodes may exist for which all neighbors have higher weights. Such nodes are isolated regional minima. If we add a self-loop linking an isolated regional minimum with itself, we can produce a graph in which all nodes are the origin of a flowing edge. After such edit operations, we obtain, for both initially node-weighted graphs and initially edge-weighted graphs, a graph in which each node is the origin of a flowing edge and in which each edge is the flowing edge of one of its extremities. Thus, we can obtain a perfect coupling between nodes and edges. The nodes of an edge-weighted graph are then weighted by eroding the edge weights with the erosion εne. Similarly, the edges of a node-weighted graph are then weighted by the dilation δen of its node weights. In both cases, we obtain a node- and edge-weighted graph, in which the nodes are obtained by dilating the edge weights, and simultaneously the edges are obtained by eroding the node weights. Such a graph is called a flowing graph. It has the same flowing paths, regional minima and catchment zones, regardless of whether we consider only the node weights or only the edge weights.
At this stage, we have associated to each node- or edge-weighted graph a node and edge weighted graph, called flowing graph and sharing the same topographical features as the graphs it is derived from: flowing paths, regional minima and catchment zones. We remark that the absolute values of the node or edge weights do not matter at all for determining the direction of the flow in a flowing edge. Only their relative values are taken into account.
We now go one step further and completely drop the node or edge weights. We start from a flowing graph, in which all edges are flowing edges, and substitute to each flowing edge an arc oriented in the direction of the flow. One obtains like that a directed graph or digraph. A flowing path of the initial graph simply becomes a directed path in the digraph.
A flowing path in a weighted graph represents the motion of a drop of water. A drop of water never moves upwards. A flowing path can for this reason never close itself, forming a cycle, except in the case where it belongs to a flat zone. Such a flowing cycle is then bidirectional as a drop of water may move in both directions. This translates to the derived digraph: a directed cycle can only exist if all its arcs are bidirectional. We call such digraphs gravitational digraphs
.
Chapter 6 first studies the topography of completely general unweighted digraphs, in which directional cycles are permitted even if they are not bidirectional. It turns out that their topographical features are poorer but not without interest. They may offer an interesting framework for future developments. The remaining part of chapter 6 analyzes the topography of gravitational digraphs, which is much richer. Weights are indeed not necessary for defining their major topographic structures. In a flat zone any couple of nodes are connected by a bidirectional path. It is impossible to leave a black holes by an outgoing arc, just like the black holes in the universe do not let out light. Finally, catchment zones of a black hole are all nodes at the origin of a directed path leading into this black hole. The chapter concludes by presenting the algorithms able to extract all the these topographical features from an unweighted gravitational digraph.
Part 3. Reducing the overlapping of catchment zones
This part contains Chapters 7–11. It plays a very important role in the applicability of the whole theory. Indeed, a node may be linked by a flowing path with several regional minima. It then belongs to several catchment zones. To avoid any arbitrary assignment to one of these catchment zones rather than to another, we have to find objective criteria for comparing flowing paths with the same origin in order to keep, as often as possible, only one of them. Thus, we reduce or, in some cases, completely suppress the overlapping of catchment zones.
Chapter 7 explains how to measure and compare the steepness of flowing paths.
Chapter 8 presents a method for pruning node-weighted digraphs. Two simple neighborhood operators are applied in sequence. At each new iteration, the steepness of the remaining flowing paths increases by one. At convergence, only ∞ – steep flowing paths remain.
Chapter 9 presents an alternative method for selecting the ∞ – steep flowing paths in a node-weighted graph or digraph. This algorithm floods the topographic surface, starting from the minima, and propagates