Breuß Michael - Innovations for Shape Analysis: Models and Algorithms

Innovations for Shape Analysis: Models and Algorithms — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "Innovations for Shape Analysis: Models and Algorithms" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

1234567...148

Part 1
Discrete Shape Analysis

Michael Breu , Alfred Bruckstein and Petros Maragos (eds.) Mathematics and Visualization Innovations for Shape Analysis 2013 Models and Algorithms 10.1007/978-3-642-34141-0_1 Springer-Verlag Berlin Heidelberg 2013

1. Modeling Three-Dimensional Morse and Morse-Smale Complexes

Lidija omi 1

(1)

Faculty of Technical Sciences, University of Novi Sad, Trg D. Obradovia 6, Novi Sad, Serbia

(2)

Department of Computer Science, University of Genova, via Dodecaneso 35, Genova, Italy

Lidija omi (Corresponding author)

Email:

Leila De Floriani

Email:

Federico Iuricich

Email:

Abstract

Morse and Morse-Smale complexes have been recognized as a suitable tool for modeling the topology of a manifold M through a decomposition of M induced by a scalar field f defined over M . We consider here the problem of representing, constructing and simplifying Morse and Morse-Smale complexes in 3D. We first describe and compare two data structures for encoding 3D Morse and Morse-Smale complexes. We describe, analyze and compare algorithms for computing such complexes. Finally, we consider the simplification of Morse and Morse-Smale complexes by applying coarsening operators on them, and we discuss and compare the coarsening operators on Morse and Morse-Smale complexes described in the literature.

1.1 Introduction

Topological analysis of discrete scalar fields is an active research field in computational topology. The available data sets defining the fields are increasing in size and in complexity. Thus, the definition of compact topological representations for scalar fields is a first step in building analysis tools capable of analyzing effectively large data sets. In the continuous case, Morse and Morse-Smale complexes have been recognized as convenient and theoretically well founded representations for modeling both the topology of the manifold domain M , and the behavior of a scalar field f over M . They segment the domain M of f into regions associated with critical points of f , which encode the features of both M and f .

Morse and Morse-Smale complexes have been introduced in computer graphics for the analysis of 2D scalar fields []. Morse complexes of the distance function have been used in shape matching and retrieval.

Scientific data, obtained either through measurements or simulation, is usually represented as a discrete set of vertices in a 2D or 3D domain M , together with function values given at those vertices. Algorithms for extracting an approximation of Morse and Morse-Smale complexes from a sampling of a (continuous) scalar field on the vertices of a simplicial complex triangulating M have been extensively studied in 2D [].

Although Morse and Morse-Smale complexes represent the topology of M and the behavior of f in a much more compact way than the initial data set at full resolution, simplification of these complexes is a necessary step for the analysis of noisy data sets. Simplification is achieved by applying the cancellation operator on f [], a cancellation eliminates critical points of f , reduces the incidence relation on the Morse complexes, and eliminates cells from the Morse-Smale complexes. In higher dimensions, surprisingly, a cancellation may introduce cells in the Morse-Smale complex, and may increase the mutual incidences among cells in the Morse complex.

Simplification operators, together with their inverse refinement ones, form a basis for the definition of a multi-resolution representation of Morse and Morse-Smale complexes, crucial for the analysis of the present-day large data sets. Several approaches for building such multi-resolution representations in 2D have been proposed []. In higher dimensions, such hierarchies are based on a progressive simplification of the initial full-resolution model.

Here, we briefly review the well known work on extraction, simplification, and multi-resolution representation of Morse and Morse-Smale complexes in 2D. Then, we review in greater detail and compare the extension of this work to three and higher dimensions. Specifically, we compare the data structure introduced in [] implements only a well-behaved subset of cancellation operators, which still forms a basis for the set of operators that modify Morse and Morse-Smale complexes on M in a topologically consistent manner. These operators also form a basis for the definition of a multi-resolution representation of Morse and Morse-Smale complexes.

1.2 Background Notions

We review background notions on Morse theory and Morse complexes for C 2 functions, and some approaches to discrete representations for Morse and Morse-Smale complexes.

Morse theory captures the relationships between the topology of a manifold M and the critical points of a scalar (real-valued) function f defined on M [].

Let f be a C 2 real-valued function (scalar field) defined over a manifold M . A point p M is a critical point of f if and only if the gradient (in some local coordinate system around p ) of f vanishes at p . Function f is said to be a Morse function if all its critical points are non-degenerate (the Hessian matrix Hess p f of the second derivatives of f at p is non-singular). For a Morse function f , there is a neighborhood of each critical point p =( p 1, p 2,, p n ) of f , in which [ illustrates a neighborhood of a critical point in three dimensions.

Fig. 1.1

Classification of non-degenerate critical points in the 3D case. Arrowed lines represent integral lines , green regions contain points with the lower function value. ( a ) A regular point, ( b ) a local maximum, ( c ) a local minimum, ( d ) a 1-saddle and ( e ) a 2-saddle

An integral line of a function f is a maximal path that is everywhere tangent to the gradient f of f . It follows the direction in which the function has the maximum increasing growth. Two integral lines are either disjoint, or they are the same. Each integral line starts at a critical point of f , called its origin , and ends at another critical point, called its destination . Integral lines that converge to a critical point p of index i cover an i -cell called the stable (descending) cell of p . Dually, integral lines that originate at p cover an ( n i )-cell called the unstable (ascending) cell of p . The descending cells (or manifolds) are pairwise disjoint, they cover M , and the boundary of every cell is a union of lower-dimensional cells. Descending cells decompose M into a cell complex d , called the descending Morse complex of f on M . Dually, the ascending cells form the ascending Morse complex a of f on M . Figures a, b show an example of a descending and dual ascending Morse complex in 2D and 3D, respectively.

Fig. 1.2

A portion of ( a ) a descending Morse complex; ( b ) the dual ascending Morse complex; ( c ) the Morse-Smale complex; ( d ) the 1-skeleton of the Morse-Smale complex in 2D

Next page

1234567...148

Light

Font size:

↓

↑

Georgia Tahoma Arial Verdana

Reset

Interval:

↓

↑

Bookmark:

Make

Similar books «Innovations for Shape Analysis: Models and Algorithms»

Look at similar books to Innovations for Shape Analysis: Models and Algorithms. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.

Steven Taylor

Markov Models: An Introduction to Markov Models

Dr. Michael Breus

Energize!: Go from shattered to smashing it in 30 days

Dr. Michael Breus

Beauty Sleep: Look Younger, Lose Weight, and Feel Great Through Better Sleep

Alfio Quarteroni

Algorithms for a New World: When Big Data and Mathematical Models Meet

Michael Arnheim

Two Models of Government

Michael Breus

Energize!

Michael N. Rychagov

Smart Algorithms for Multimedia and Imaging

Michael E. Levin

Innovations in Acceptance and Commitment Therapy: Clinical Advancements and Applications in ACT

Michael Oberguggenberger

Analysis for Computer Scientists: Foundations, Methods, and Algorithms

Michael Breus

22 May

Breus Michael

The power of when : discover your chronotype--and the best time to eat lunch, ask for a raise, have sex, write a novel, take your meds, and more

Mehmed Kantardzic

Data Mining: Concepts, Models, Methods, and Algorithms

Discussion, reviews of the book Innovations for Shape Analysis: Models and Algorithms and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.