---
_id: '833'
abstract:
- lang: eng
text: We present an efficient algorithm to compute Euler characteristic curves of
gray scale images of arbitrary dimension. In various applications the Euler characteristic
curve is used as a descriptor of an image. Our algorithm is the first streaming
algorithm for Euler characteristic curves. The usage of streaming removes the
necessity to store the entire image in RAM. Experiments show that our implementation
handles terabyte scale images on commodity hardware. Due to lock-free parallelism,
it scales well with the number of processor cores. Additionally, we put the concept
of the Euler characteristic curve in the wider context of computational topology.
In particular, we explain the connection with persistence diagrams.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Hubert
full_name: Wagner, Hubert
id: 379CA8B8-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
citation:
ama: 'Heiss T, Wagner H. Streaming algorithm for Euler characteristic curves of
multidimensional images. In: Felsberg M, Heyden A, Krüger N, eds. Vol 10424. Springer;
2017:397-409. doi:10.1007/978-3-319-64689-3_32'
apa: 'Heiss, T., & Wagner, H. (2017). Streaming algorithm for Euler characteristic
curves of multidimensional images. In M. Felsberg, A. Heyden, & N. Krüger
(Eds.) (Vol. 10424, pp. 397–409). Presented at the CAIP: Computer Analysis of
Images and Patterns, Ystad, Sweden: Springer. https://doi.org/10.1007/978-3-319-64689-3_32'
chicago: Heiss, Teresa, and Hubert Wagner. “Streaming Algorithm for Euler Characteristic
Curves of Multidimensional Images.” edited by Michael Felsberg, Anders Heyden,
and Norbert Krüger, 10424:397–409. Springer, 2017. https://doi.org/10.1007/978-3-319-64689-3_32.
ieee: 'T. Heiss and H. Wagner, “Streaming algorithm for Euler characteristic curves
of multidimensional images,” presented at the CAIP: Computer Analysis of Images
and Patterns, Ystad, Sweden, 2017, vol. 10424, pp. 397–409.'
ista: 'Heiss T, Wagner H. 2017. Streaming algorithm for Euler characteristic curves
of multidimensional images. CAIP: Computer Analysis of Images and Patterns, LNCS,
vol. 10424, 397–409.'
mla: Heiss, Teresa, and Hubert Wagner. Streaming Algorithm for Euler Characteristic
Curves of Multidimensional Images. Edited by Michael Felsberg et al., vol.
10424, Springer, 2017, pp. 397–409, doi:10.1007/978-3-319-64689-3_32.
short: T. Heiss, H. Wagner, in:, M. Felsberg, A. Heyden, N. Krüger (Eds.), Springer,
2017, pp. 397–409.
conference:
end_date: 2017-08-24
location: Ystad, Sweden
name: 'CAIP: Computer Analysis of Images and Patterns'
start_date: 2017-08-22
date_created: 2018-12-11T11:48:45Z
date_published: 2017-07-28T00:00:00Z
date_updated: 2023-09-26T16:10:03Z
day: '28'
department:
- _id: HeEd
doi: 10.1007/978-3-319-64689-3_32
editor:
- first_name: Michael
full_name: Felsberg, Michael
last_name: Felsberg
- first_name: Anders
full_name: Heyden, Anders
last_name: Heyden
- first_name: Norbert
full_name: Krüger, Norbert
last_name: Krüger
external_id:
isi:
- '000432085900032'
intvolume: ' 10424'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.02045
month: '07'
oa: 1
oa_version: Submitted Version
page: 397 - 409
publication_identifier:
issn:
- '03029743'
publication_status: published
publisher: Springer
publist_id: '6815'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Streaming algorithm for Euler characteristic curves of multidimensional images
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10424
year: '2017'
...
---
_id: '84'
abstract:
- lang: eng
text: The advent of high-throughput technologies and the concurrent advances in
information sciences have led to a data revolution in biology. This revolution
is most significant in molecular biology, with an increase in the number and scale
of the “omics” projects over the last decade. Genomics projects, for example,
have produced impressive advances in our knowledge of the information concealed
into genomes, from the many genes that encode for the proteins that are responsible
for most if not all cellular functions, to the noncoding regions that are now
known to provide regulatory functions. Proteomics initiatives help to decipher
the role of post-translation modifications on the protein structures and provide
maps of protein-protein interactions, while functional genomics is the field that
attempts to make use of the data produced by these projects to understand protein
functions. The biggest challenge today is to assimilate the wealth of information
provided by these initiatives into a conceptual framework that will help us decipher
life. For example, the current views of the relationship between protein structure
and function remain fragmented. We know of their sequences, more and more about
their structures, we have information on their biological activities, but we have
difficulties connecting this dotted line into an informed whole. We lack the experimental
and computational tools for directly studying protein structure, function, and
dynamics at the molecular and supra-molecular levels. In this chapter, we review
some of the current developments in building the computational tools that are
needed, focusing on the role that geometry and topology play in these efforts.
One of our goals is to raise the general awareness about the importance of geometric
methods in elucidating the mysterious foundations of our very existence. Another
goal is the broadening of what we consider a geometric algorithm. There is plenty
of valuable no-man’s-land between combinatorial and numerical algorithms, and
it seems opportune to explore this land with a computational-geometric frame of
mind.
article_processing_charge: No
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Patrice
full_name: Koehl, Patrice
last_name: Koehl
citation:
ama: 'Edelsbrunner H, Koehl P. Computational topology for structural molecular biology.
In: Toth C, O’Rourke J, Goodman J, eds. Handbook of Discrete and Computational
Geometry, Third Edition. Handbook of Discrete and Computational Geometry.
Taylor & Francis; 2017:1709-1735. doi:10.1201/9781315119601'
apa: Edelsbrunner, H., & Koehl, P. (2017). Computational topology for structural
molecular biology. In C. Toth, J. O’Rourke, & J. Goodman (Eds.), Handbook
of Discrete and Computational Geometry, Third Edition (pp. 1709–1735). Taylor
& Francis. https://doi.org/10.1201/9781315119601
chicago: Edelsbrunner, Herbert, and Patrice Koehl. “Computational Topology for Structural
Molecular Biology.” In Handbook of Discrete and Computational Geometry, Third
Edition, edited by Csaba Toth, Joseph O’Rourke, and Jacob Goodman, 1709–35.
Handbook of Discrete and Computational Geometry. Taylor & Francis, 2017. https://doi.org/10.1201/9781315119601.
ieee: H. Edelsbrunner and P. Koehl, “Computational topology for structural molecular
biology,” in Handbook of Discrete and Computational Geometry, Third Edition,
C. Toth, J. O’Rourke, and J. Goodman, Eds. Taylor & Francis, 2017, pp. 1709–1735.
ista: 'Edelsbrunner H, Koehl P. 2017.Computational topology for structural molecular
biology. In: Handbook of Discrete and Computational Geometry, Third Edition. ,
1709–1735.'
mla: Edelsbrunner, Herbert, and Patrice Koehl. “Computational Topology for Structural
Molecular Biology.” Handbook of Discrete and Computational Geometry, Third
Edition, edited by Csaba Toth et al., Taylor & Francis, 2017, pp. 1709–35,
doi:10.1201/9781315119601.
short: H. Edelsbrunner, P. Koehl, in:, C. Toth, J. O’Rourke, J. Goodman (Eds.),
Handbook of Discrete and Computational Geometry, Third Edition, Taylor & Francis,
2017, pp. 1709–1735.
date_created: 2018-12-11T11:44:32Z
date_published: 2017-11-09T00:00:00Z
date_updated: 2023-10-16T11:15:22Z
day: '09'
department:
- _id: HeEd
doi: 10.1201/9781315119601
editor:
- first_name: Csaba
full_name: Toth, Csaba
last_name: Toth
- first_name: Joseph
full_name: O'Rourke, Joseph
last_name: O'Rourke
- first_name: Jacob
full_name: Goodman, Jacob
last_name: Goodman
language:
- iso: eng
month: '11'
oa_version: None
page: 1709 - 1735
publication: Handbook of Discrete and Computational Geometry, Third Edition
publication_identifier:
eisbn:
- '9781498711425'
publication_status: published
publisher: Taylor & Francis
publist_id: '7970'
quality_controlled: '1'
scopus_import: '1'
series_title: Handbook of Discrete and Computational Geometry
status: public
title: Computational topology for structural molecular biology
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '909'
abstract:
- lang: eng
text: We study the lengths of curves passing through a fixed number of points on
the boundary of a convex shape in the plane. We show that, for any convex shape
K, there exist four points on the boundary of K such that the length of any curve
passing through these points is at least half of the perimeter of K. It is also
shown that the same statement does not remain valid with the additional constraint
that the points are extreme points of K. Moreover, the factor ½ cannot
be achieved with any fixed number of extreme points. We conclude the paper with
a few other inequalities related to the perimeter of a convex shape.
article_processing_charge: No
article_type: original
author:
- first_name: Arseniy
full_name: Akopyan, Arseniy
id: 430D2C90-F248-11E8-B48F-1D18A9856A87
last_name: Akopyan
orcid: 0000-0002-2548-617X
- first_name: Vladislav
full_name: Vysotsky, Vladislav
last_name: Vysotsky
citation:
ama: Akopyan A, Vysotsky V. On the lengths of curves passing through boundary points
of a planar convex shape. The American Mathematical Monthly. 2017;124(7):588-596.
doi:10.4169/amer.math.monthly.124.7.588
apa: Akopyan, A., & Vysotsky, V. (2017). On the lengths of curves passing through
boundary points of a planar convex shape. The American Mathematical Monthly.
Mathematical Association of America. https://doi.org/10.4169/amer.math.monthly.124.7.588
chicago: Akopyan, Arseniy, and Vladislav Vysotsky. “On the Lengths of Curves Passing
through Boundary Points of a Planar Convex Shape.” The American Mathematical
Monthly. Mathematical Association of America, 2017. https://doi.org/10.4169/amer.math.monthly.124.7.588.
ieee: A. Akopyan and V. Vysotsky, “On the lengths of curves passing through boundary
points of a planar convex shape,” The American Mathematical Monthly, vol.
124, no. 7. Mathematical Association of America, pp. 588–596, 2017.
ista: Akopyan A, Vysotsky V. 2017. On the lengths of curves passing through boundary
points of a planar convex shape. The American Mathematical Monthly. 124(7), 588–596.
mla: Akopyan, Arseniy, and Vladislav Vysotsky. “On the Lengths of Curves Passing
through Boundary Points of a Planar Convex Shape.” The American Mathematical
Monthly, vol. 124, no. 7, Mathematical Association of America, 2017, pp. 588–96,
doi:10.4169/amer.math.monthly.124.7.588.
short: A. Akopyan, V. Vysotsky, The American Mathematical Monthly 124 (2017) 588–596.
date_created: 2018-12-11T11:49:09Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-10-17T11:24:57Z
day: '01'
department:
- _id: HeEd
doi: 10.4169/amer.math.monthly.124.7.588
ec_funded: 1
external_id:
arxiv:
- '1605.07997'
isi:
- '000413947300002'
intvolume: ' 124'
isi: 1
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1605.07997
month: '01'
oa: 1
oa_version: Submitted Version
page: 588 - 596
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
publication: The American Mathematical Monthly
publication_identifier:
issn:
- '00029890'
publication_status: published
publisher: Mathematical Association of America
publist_id: '6534'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the lengths of curves passing through boundary points of a planar convex
shape
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 124
year: '2017'
...
---
_id: '1149'
abstract:
- lang: eng
text: 'We study the usefulness of two most prominent publicly available rigorous
ODE integrators: one provided by the CAPD group (capd.ii.uj.edu.pl), the other
based on the COSY Infinity project (cosyinfinity.org). Both integrators are capable
of handling entire sets of initial conditions and provide tight rigorous outer
enclosures of the images under a time-T map. We conduct extensive benchmark computations
using the well-known Lorenz system, and compare the computation time against the
final accuracy achieved. We also discuss the effect of a few technical parameters,
such as the order of the numerical integration method, the value of T, and the
phase space resolution. We conclude that COSY may provide more precise results
due to its ability of avoiding the variable dependency problem. However, the overall
cost of computations conducted using CAPD is typically lower, especially when
intervals of parameters are involved. Moreover, access to COSY is limited (registration
required) and the rigorous ODE integrators are not publicly available, while CAPD
is an open source free software project. Therefore, we recommend the latter integrator
for this kind of computations. Nevertheless, proper choice of the various integration
parameters turns out to be of even greater importance than the choice of the integrator
itself. © 2016 IMACS. Published by Elsevier B.V. All rights reserved.'
acknowledgement: "MG was partially supported by FAPESP grants 2013/07460-7 and 2010/00875-9,
and by CNPq grants 305860/2013-5 and 306453/2009-6, Brazil. The work of HK was partially
supported by Grant-in-Aid for Scientific Research (Nos.24654022, 25287029), Ministry
of Education, Science, Technology, Culture and Sports, Japan. KM was supported by
NSF grants NSF-DMS-0835621, 0915019, 1125174, 1248071, and contracts from AFOSR
and DARPA. TM was supported by Grant-in-Aid for JSPS Fellows No. 245312. A part
of the research of TM and HK was also supported by JST, CREST.\r\n\r\nResearch conducted
by PP has received funding from Fundo Europeu de Desenvolvimento Regional (FEDER)
through COMPETE – Programa Operacional Factores de Competitividade (POFC) and from
the Portuguese national funds through Fundação para a Ciência e a Tecnologia (FCT)
in the framework of the research project FCOMP-01-0124-FEDER-010645 (Ref. FCT PTDC/MAT/098871/2008);
from the People Programme (Marie Curie Actions) of the European Union's Seventh
Framework Programme (FP7/2007-2013) under REA grant agreement No. 622033; and from
the same sources as HK.\r\n\r\nThe authors express their gratitude to the Department
of Mathematics of Kyoto University for making their server available for conducting
the computations described in the paper, and to the reviewers for helpful comments
that contributed towards increasing the quality of the paper."
author:
- first_name: Tomoyuki
full_name: Miyaji, Tomoyuki
last_name: Miyaji
- first_name: Pawel
full_name: Pilarczyk, Pawel
id: 3768D56A-F248-11E8-B48F-1D18A9856A87
last_name: Pilarczyk
- first_name: Marcio
full_name: Gameiro, Marcio
last_name: Gameiro
- first_name: Hiroshi
full_name: Kokubu, Hiroshi
last_name: Kokubu
- first_name: Konstantin
full_name: Mischaikow, Konstantin
last_name: Mischaikow
citation:
ama: Miyaji T, Pilarczyk P, Gameiro M, Kokubu H, Mischaikow K. A study of rigorous
ODE integrators for multi scale set oriented computations. Applied Numerical
Mathematics. 2016;107:34-47. doi:10.1016/j.apnum.2016.04.005
apa: Miyaji, T., Pilarczyk, P., Gameiro, M., Kokubu, H., & Mischaikow, K. (2016).
A study of rigorous ODE integrators for multi scale set oriented computations.
Applied Numerical Mathematics. Elsevier. https://doi.org/10.1016/j.apnum.2016.04.005
chicago: Miyaji, Tomoyuki, Pawel Pilarczyk, Marcio Gameiro, Hiroshi Kokubu, and
Konstantin Mischaikow. “A Study of Rigorous ODE Integrators for Multi Scale Set
Oriented Computations.” Applied Numerical Mathematics. Elsevier, 2016.
https://doi.org/10.1016/j.apnum.2016.04.005.
ieee: T. Miyaji, P. Pilarczyk, M. Gameiro, H. Kokubu, and K. Mischaikow, “A study
of rigorous ODE integrators for multi scale set oriented computations,” Applied
Numerical Mathematics, vol. 107. Elsevier, pp. 34–47, 2016.
ista: Miyaji T, Pilarczyk P, Gameiro M, Kokubu H, Mischaikow K. 2016. A study of
rigorous ODE integrators for multi scale set oriented computations. Applied Numerical
Mathematics. 107, 34–47.
mla: Miyaji, Tomoyuki, et al. “A Study of Rigorous ODE Integrators for Multi Scale
Set Oriented Computations.” Applied Numerical Mathematics, vol. 107, Elsevier,
2016, pp. 34–47, doi:10.1016/j.apnum.2016.04.005.
short: T. Miyaji, P. Pilarczyk, M. Gameiro, H. Kokubu, K. Mischaikow, Applied Numerical
Mathematics 107 (2016) 34–47.
date_created: 2018-12-11T11:50:25Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2021-01-12T06:48:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.apnum.2016.04.005
ec_funded: 1
intvolume: ' 107'
language:
- iso: eng
month: '09'
oa_version: None
page: 34 - 47
project:
- _id: 255F06BE-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '622033'
name: Persistent Homology - Images, Data and Maps
publication: Applied Numerical Mathematics
publication_status: published
publisher: Elsevier
publist_id: '6209'
quality_controlled: '1'
scopus_import: 1
status: public
title: A study of rigorous ODE integrators for multi scale set oriented computations
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 107
year: '2016'
...
---
_id: '1216'
abstract:
- lang: eng
text: 'A framework fo r extracting features in 2D transient flows, based on the
acceleration field to ensure Galilean invariance is proposed in this paper. The
minima of the acceleration magnitude (a superset of acceleration zeros) are extracted
and discriminated into vortices and saddle points, based on the spectral properties
of the velocity Jacobian. The extraction of topological features is performed
with purely combinatorial algorithms from discrete computational topology. The
feature points are prioritized with persistence, as a physically meaningful importance
measure. These feature points are tracked in time with a robust algorithm for
tracking features. Thus, a space-time hierarchy of the minima is built and vortex
merging events are detected. We apply the acceleration feature extraction strategy
to three two-dimensional shear flows: (1) an incompressible periodic cylinder
wake, (2) an incompressible planar mixing layer and (3) a weakly compressible
planar jet. The vortex-like acceleration feature points are shown to be well aligned
with acceleration zeros, maxima of the vorticity magnitude, minima of the pressure
field and minima of λ2.'
acknowledgement: "The authors acknowledge funding of the German Re-\r\nsearch Foundation
\ (DFG) via the Collaborative Re-\r\nsearch Center (SFB 557) \\Control of
\ Complex Turbu-\r\nlent Shear Flows\" and the Emmy Noether Program.\r\nFurther
\ funding was provided by the Zuse Institute\r\nBerlin (ZIB), the DFG-CNRS
\ research group \\Noise\r\nGeneration in Turbulent Flows\" (2003{2010), the Chaire\r\nd'Excellence
'Closed-loop control of turbulent shear ows\r\nusing reduced-order models' (TUCOROM)
of the French\r\nAgence Nationale de la Recherche (ANR), and the Eu-\r\nropean Social
\ Fund (ESF App. No. 100098251). We\r\nthank the Ambrosys Ltd. Society
\ for Complex Sys-\r\ntems Management and the Bernd R. Noack Cybernet-\r\nics
\ Foundation for additional support. A part of this\r\nwork was performed
using HPC resources from GENCI-[CCRT/CINES/IDRIS] supported by the Grant 2011-\r\n[x2011020912"
author:
- first_name: Jens
full_name: Kasten, Jens
last_name: Kasten
- first_name: Jan
full_name: Reininghaus, Jan
id: 4505473A-F248-11E8-B48F-1D18A9856A87
last_name: Reininghaus
- first_name: Ingrid
full_name: Hotz, Ingrid
last_name: Hotz
- first_name: Hans
full_name: Hege, Hans
last_name: Hege
- first_name: Bernd
full_name: Noack, Bernd
last_name: Noack
- first_name: Guillaume
full_name: Daviller, Guillaume
last_name: Daviller
- first_name: Marek
full_name: Morzyński, Marek
last_name: Morzyński
citation:
ama: Kasten J, Reininghaus J, Hotz I, et al. Acceleration feature points of unsteady
shear flows. Archives of Mechanics. 2016;68(1):55-80.
apa: Kasten, J., Reininghaus, J., Hotz, I., Hege, H., Noack, B., Daviller, G., &
Morzyński, M. (2016). Acceleration feature points of unsteady shear flows. Archives
of Mechanics. Polish Academy of Sciences Publishing House.
chicago: Kasten, Jens, Jan Reininghaus, Ingrid Hotz, Hans Hege, Bernd Noack, Guillaume
Daviller, and Marek Morzyński. “Acceleration Feature Points of Unsteady Shear
Flows.” Archives of Mechanics. Polish Academy of Sciences Publishing House,
2016.
ieee: J. Kasten et al., “Acceleration feature points of unsteady shear flows,”
Archives of Mechanics, vol. 68, no. 1. Polish Academy of Sciences Publishing
House, pp. 55–80, 2016.
ista: Kasten J, Reininghaus J, Hotz I, Hege H, Noack B, Daviller G, Morzyński M.
2016. Acceleration feature points of unsteady shear flows. Archives of Mechanics.
68(1), 55–80.
mla: Kasten, Jens, et al. “Acceleration Feature Points of Unsteady Shear Flows.”
Archives of Mechanics, vol. 68, no. 1, Polish Academy of Sciences Publishing
House, 2016, pp. 55–80.
short: J. Kasten, J. Reininghaus, I. Hotz, H. Hege, B. Noack, G. Daviller, M. Morzyński,
Archives of Mechanics 68 (2016) 55–80.
date_created: 2018-12-11T11:50:46Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2021-01-12T06:49:09Z
day: '01'
department:
- _id: HeEd
intvolume: ' 68'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://am.ippt.pan.pl/am/article/viewFile/v68p55/pdf
month: '01'
oa: 1
oa_version: Published Version
page: 55 - 80
publication: Archives of Mechanics
publication_status: published
publisher: Polish Academy of Sciences Publishing House
publist_id: '6118'
quality_controlled: '1'
scopus_import: 1
status: public
title: Acceleration feature points of unsteady shear flows
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 68
year: '2016'
...