Springer Complexity Springer Complexity is an interdisciplinary program publishing the best research and academic- level teaching on both fundamental and applied aspects of complex systems – cutting across all traditional disciplines of the natural and life sciences, engineering, economics, medicine, neuroscience, social and computer science. Complex Systems are systems that comprise many interacting parts with the ability to gener- ate a new quality of macroscopic collective behavior the manifestations of which are the sponta- neous formation of distinctive temporal, spatial or functional structures. Models of such systems can be successfully mapped onto quite diverse “real-life” situations like the climate, the coherent emission of light from lasers, chemical reaction–diffusion systems, biological cellular networks, the dynamics of stock markets and of the Internet, earthquake statistics and prediction, freeway traffic, the human brain, or the formation of opinions in social systems, to name just some of the popular applications. Although their scope and methodologies overlap somewhat, one can distinguish the follow- ing main concepts and tools: self-organization, nonlinear dynamics, synergetics, turbulence, dy- namical systems, catastrophes, instabilities, stochastic processes, chaos, graphs and networks, cellular automata, adaptive systems, genetic algorithms and computational intelligence. The two major book publication platforms of the Springer Complexity program are the mono- graph series “Understanding Complex Systems” focusing on the various applications of com- plexity, and the “Springer Series in Synergetics”, which is devoted to the quantitative theoretical and methodological foundations. In addition to the books in these two core series, the program also incorporates individual titles ranging from textbooks to major reference works. Editorial and Programme Advisory Board P ´ eter ´ Erdi Center for Complex Systems Studies, Kalamazoo College, USA and Hungarian Academy of Sciences, Budapest, Hungary Karl Friston National Hospital, Institute for Neurology, Wellcome Dept. Cogn. Neurology, London, UK Hermann Haken Center of Synergetics, University of Stuttgart, Stuttgart, Germany Janusz Kacprzyk System Research, Polish Academy of Sciences, Warsaw, Poland Scott Kelso Center for Complex Systems and Brain Sciences, Florida Atlantic University, Boca Raton, USA J ¨ urgen Kurths Nonlinear Dynamics Group, University of Potsdam, Potsdam, Germany Linda Reichl Department of Physics, Prigogine Center for Statistical Mechanics, University of Texas, Austin, USA Peter Schuster Theoretical Chemistry and Structural Biology, University of Vienna, Vienna, Austria Frank Schweitzer System Design, ETH Z ¨ urich, Z ¨ urich, Switzerland Didier Sornette Entrepreneurial Risk, ETH Z ¨ urich, Z ¨ urich, Switzerland Understanding Complex Systems Founding Editor: J.A. Scott Kelso Future scientific and technological developments in many fields will necessarily depend upon coming to grips with complex systems. Such systems are complex in both their composition – typically many different kinds of components interacting simultaneously and nonlinearly with each other and their environments on multiple levels – and in the rich diversity of behavior of which they are capable. The Springer Series in Understanding Complex Systems series (UCS) promotes new strategies and paradigms for understanding and realizing applications of com- plex systems research in a wide variety of fields and endeavors. UCS is explicitly transdisciplinary. It has three main goals: First, to elaborate the concepts, methods and tools of complex systems at all levels of description and in all scientific fields, especially newly emerging areas within the life, social, behavioral, economic, neuro- and cognitive sciences (and derivatives thereof); second, to encourage novel applica- tions of these ideas in various fields of engineering and computation such as robotics, nano-technology and informatics; third, to provide a single forum within which com- monalities and differences in the workings of complex systems may be discerned, hence leading to deeper insight and understanding. UCS will publish monographs, lecture notes and selected edited contributions aimed at communicating new findings to a large multidisciplinary audience. R. Dahlhaus · J. Kurths · P. Maass · J. Timmer (Eds.) Mathematical Methods in Signal Processing and Digital Image Analysis With 96 Figures and 20 Tables Volume Editors Rainer Dahlhaus Universit ¨ at Heidelberg Inst. Angewandte Mathematik Im Neuenheimer Feld 294 69120 Heidelberg Germany dahlhaus@statlab.uni-heidelberg.de Peter Maass Universit ¨ at Bremen FB 3 Mathematik/Informatik Zentrum Technomathematik 28334 Bremen Germany pmaass@uni-bremen.de J ¨ urgen Kurths Universit ¨ at Potsdam Inst. Physik, LS Theoretische Physik Am Neuen Palais 19 14469 Potsdam Germany jkurths@agnld.uni-potsdam.de Jens Timmer Universit ¨ at Freiburg Zentrum Datenanalyse Eckerstr. 1 79104 Freiburg Germany jens.timmer@fdm.uni-freiburg.de ISBN: 978-3-540-75631-6 e-ISBN: 978-3-540-75632-3 Understanding Complex Systems ISSN: 1860-0832 Library of Congress Control Number: 2007940881 c  2008 Springer-Verlag Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover Design: WMXDesign GmbH, Heidelberg Printed on acid-free paper 987654321 springer.com Preface Interest in time series analysis and image processing has been growing very rapidly in recent years. Input from different scientific disciplines and new the- oretical advances are matched by an increasing demand from an expanding diversity of applications. Consequently, signal and image processing has been established as an independent research direction in such different areas as electrical engineering, theoretical physics, mathematics or computer science. This has lead to some rather unstructured developments of theories, meth- ods and algorithms. The authors of this book aim at merging some of these diverging directions and to develop a consistent framework, which combines these heterogeneous developments. The common core of the different chap- ters is the endavour to develop and analyze mathematically justified methods and algorithms. This book should serve as an overview of the state of the art research in this field with a focus on nonlinear and nonparametric models for time series as well as of local, adaptive methods in image processing. The presented results are in its majority the outcome of the DFG-priority program SPP 1114 “Mathematical methods for time series analysis and digital image processing”. The starting point for this priority program was the consid- eration, that the next generation of algorithmic developments requires a close cooperation of researchers from different scientific backgrounds. Accordingly, this program, which was running for 6 years from 2001 to 2007, encompassed approximately 20 research teams from statistics, theoretical physics and math- ematics. The intensive cooperation between teams from different specialized disciplines is mirrored by the different chapters of this book, which were jointly written by several research teams. The theoretical findings are always tested with applications of different complexity. We do hope and expect that this book serves as a background reference to the present state of the art and that it sparks exciting and creative new research in this rapidly developing field. This book, which concentrates on methodologies related to identifica- tion of dynamical systems, non- and semi-parametric models for time series, VI Preface stochastic methods, wavelet or multiscale analysis, diffusion filters and math- ematical morphology, is organized as follows. The Chap. 1 describes recent developments on multivariate time series analysis. The results are obtained from combinig statistical methods with the theory of nonlinear dynamics in order to better understand time series measured from underlying complex network structures. The authors of this chapter emphasize the importance of analyzing the interrelations and causal influences between different processes and their application to real-world data such as EEG or MEG from neurological experiments. The concept of de- termining directed influences by investigating renormalized partial directed coherence is introduced and analyzed leading to estimators of the strength of the effect of a source process on a target process. The development of surrogate methods has been one of the major driv- ing forces in statistical data analysis in recent years. The Chap. 2 discusses the mathematical foundations of surrogate data testing and examines the statistical performance in extensive simulation studies. It is shown that the performance of the test heavily depends on the chosen combination of the test statistics, the resampling methods and the null hypothesis. The Chap. 3 concentrates on multiscale approaches to image processing. It starts with construction principles for multivariate multiwavelets and in- cludes some wavelet applications to inverse problems in image processing with sparsity constraints. The chapter includes the application of these methods to real life data from industrial partners. The investigation of inverse problems is also at the center of Chap. 4. Inverse problems in image processing naturally appear as parameter identi- fication problems for certain partial differential equations. The applications treated in this chapter include the determination of heterogeneous media in subsurface structures, surface matching and morphological image matching as well as a medically motivated image blending task. This chapter includes a survey of the analytic background theory as well as illustrations of these specific applications. Recent results on nonlinear methods for analyzing bivariate coupled sys- tems are summarized in Chap. 5. Instead of using classical linear methods based on correlation functions or spectral decompositions, the present chap- ter takes a look at nonlinear approaches based on investigating recurrence features. The recurrence properties of the underlying dynamical system are investigated on different time scales, which leads to a mathematically justified theory for analyzing nonlinear recurrence plots. The investigation includes an analysis of synchronization effects, which have been developed into one of the most powerfull methodologies for analyzing dynamical systems. Chapter 6 takes a new look at strucutred smoothing procedures for denois- ing signals and images. Different techniques from stochastic kernel smoother to anisotropic variational approaches and wavelet based techniques are ana- lyzed and compared. The common feature of these methods is their local and Preface VII adaptive nature. A strong emphasize is given to the comparison with standard methods. Chapter 7 presents a novel framework for the detection and accurate quantification of motion, orientation, and symmetry in images and image sequences. It focuses on those aspects of motion and orientation that can- not be handled successfully and reliably by existing methods, for example, motion superposition (due to transparency, reflection or occlusion), illumina- tion changes, temporal and/or spatial motion discontinuities, and dispersive nonrigid motion. The performance of the presented algorithms is character- ized and their applicability is demonstrated by several key application areas including environmental physics, botany, physiology, medical imaging, and technical applications. The authors of this book as well as all participants of the SPP 1114 “Math- ematical methods for time series analysis and digital image processing” would like to express their sincere thanks to the German Science Foundation for the generous support over the last 6 years. This support has generated and sparked exciting research and ongoing scientific discussions, it has lead to a large diversity of scientific publications and – most importantly- has allowed us to educate a generation of highly talented and ambitious young scientists, which are now spread all over the world. Furthermore, it is our great pleasure to acknowledge the impact of the referees, which accompangnied and shaped the developments of this priority program during its different phases. Finally, we want to express our gratitude to Mrs. Sabine Pfarr, who prepared this manuscript in an seemingly endless procedure of proof reading, adjusting im- ages, tables, indices and bibliographies while still keeping a friendly level of communication with all authors concerning those nasty details scientist easily forget. Bremen, Rainer Dahlhaus, J¨urgen Kurths, November 2007 Peter Maass, Jens Timmer Contents 1 Multivariate Time Series Analysis Bj¨orn Schelter, Rainer Dahlhaus, Lutz Leistritz, Wolfram Hesse, B¨arbel Schack, J¨urgen Kurths, Jens Timmer, Herbert Witte 1 2 Surrogate Data – A Qualitative and Quantitative Analysis Thomas Maiwald, Enno Mammen, Swagata Nandi, Jens Timmer 41 3 Multiscale Approximation Stephan Dahlke, Peter Maass, Gerd Teschke, Karsten Koch, Dirk Lorenz, Stephan M¨uller, Stefan Schiffler, Andreas St¨ampfli, Herbert Thiele, Manuel Werner 75 4 Inverse Problems and Parameter Identification in Image Processing Jens F. Acker, Benjamin Berkels, Kristian Bredies, Mamadou S. Diallo, Marc Droske, Christoph S. Garbe, Matthias Holschneider, Jaroslav Hron, Claudia Kondermann, Michail Kulesh, Peter Maass, Nadine Olischl¨ager, Heinz-Otto Peitgen, Tobias Preusser, Martin Rumpf, Karl Schaller, Frank Scherbaum, Stefan Turek 111 5 Analysis of Bivariate Coupling by Means of Recurrence Christoph Bandt, Andreas Groth, Norbert Marwan, M. Carmen Romano, Marco Thiel, Michael Rosenblum, J¨urgen Kurths 153 6 Structural Adaptive Smoothing Procedures J¨urgen Franke, Rainer Dahlhaus, J¨org Polzehl, Vladimir Spokoiny, Gabriele Steidl, Joachim Weickert, Anatoly Berdychevski, Stephan Didas, Siana Halim, Pavel Mr´azek, Suhasini Subba Rao, Joseph Tadjuidje 183 X Contents 7 Nonlinear Analysis of Multi-Dimensional Signals Christoph S. Garbe, Kai Krajsek, Pavel Pavlov, Bj¨orn Andres, Matthias M¨uhlich, Ingo Stuke, Cicero Mota, Martin B¨ohme, Martin Haker, Tobias Schuchert, Hanno Scharr, Til Aach, Erhardt Barth, Rudolf Mester, Bernd J¨ahne 231 Index 289 List of Contributors Til Aach RWTH Aachen University, Aachen, Germany Til.Aach@lfb.rwth-aachen.de Jens F. Acker University of Dortmund, Dortmund, Germany jens.acker@math.uni-dortmund.de Bj¨orn Andres University of Heidelberg, Heidelberg, Germany bjoern.andres @iwr.uni-heidelberg.de Christoph Bandt University of Greifswald, Greifswald, Germany bandt@uni-greifswald.de Erhardt Barth University of L¨ubeck, L¨ubeck, Germany barth@inb.uni-luebeck.de Anatoly Berdychevski Weierstraß-Institut Berlin, Berlin, Germany berdichevski@wias-berlin.de Benjamin Berkels University of Bonn, Bonn, Germany benjamin.berkels@ins.uni-bonn.de Martin B¨ohme University of L¨ubeck, L¨ubeck, Germany boehme@inb.uni-luebeck.de Kristian Bredies University of Bremen, Bremen, Germany kbredies@math.uni-bremen.de Rainer Dahlhaus University of Heidelberg, Heidelberg, Germany dahlhaus@statlab.uni-heidelberg.de Stephan Dahlke University of Marburg, Marburg, Germany dahlke@mathematik.uni-marburg.de Mamadou S. Diallo ExxonMobil, Houston, TX, USA mamadou.s.diallo@exxonmobil.com Stephan Didas Saarland University, Saarland, Germany didas@mia.uni-saarland.de [...]... series analysis being able to distinguish direct and indirect, in some cases the directions of interactions in linear as well as nonlinear systems 2 B Schelter et al 1.2 Introduction In this chapter the spectrum of methods developed in the fields ranging from linear stochastic systems to those in the field of nonlinear stochastic systems is discussed Similarities and distinct conceptual properties in both... certain definition of a Granger-causality index Such models are e.g time-variant autoregressive models or self-exciting threshold autoregressive (SETAR) models The first one results in a definition of a time-variant Granger-causality index, the second one provides the basis for a state-dependent Granger-causality index Time-Variant Granger-Causality Index To introduce a Granger-causality index in the time-domain... arrows) The interrelation between the thalamic leads remains significant for the multivariate analysis given in Fig 1.6 (c) and (d) The directed in uence from POC to LD and RTN 1 Multivariate Time Series Analysis 21 Fig 1.6 Investigation of directed interrelations during the occurrence of burst patterns using the Granger-causality index in the time domain Gray-colored regions indicate significant in uences... between direct and indirect interactions Thus, the GCI, PDC, and PC are sensitive in distinguishing direct from indirect in uences Despite the high sensitivity in general, there might be some situations in which this characteristic is restricted, for instance in nonlinear, non-stationary systems Direction of in uences: All multivariate methods are capable of detecting the direction of in uences Partial... during interburst periods leading to a functional state of unconsciousness [1], SEP analysis indicates that even during this particular functional state a signal transduction appears from peripheral skin sensors via thalamo-cortical networks up to cortical structures leading to signal processing Hence in principle, a subthalamically generated continuous input could be responsible for the pronounced in uence... Series Analysis 3 Fig 1.1 (a) Graph representing the true interaction structure Direct interactions are only present between signals X1 and X2 and X1 and X3 ; the direct interaction between X2 and X3 is absent (b) Graph resulting from bivariate analysis, like cross-spectral analysis From the bivariate analysis it is suggested that all nodes are interacting with one another The spurious edge between signals... representing the true interaction structure Signal X1 is the sum of two signals X2 and X3 , which are independent processes, i.e the direct interaction between X2 and X3 is absent (b) Graph resulting from multivariate analysis From the multivariate analysis it is suggested that all nodes are interacting with one another The spurious edge between signal X2 and X3 is due to the so-called marrying parents... between intrathalamic, thalamo-cortical and corticothalamic networks Patterns were induced by propofol infusion in juvenile pigs and derived from cortical and thalamic electrodes The analysis was performed to clarify a suggested time-dependent directed in uence between the above mentioned brain structures known to be essentially involved in regulation of the physiological variation in consciousness during... filter; Fa Schwind, Erlangen) before sampled continuously (125 Hz) with a digital data acquisition system (GJB Datentechnik GmbH, Langewiesen) Four linked screw electrodes inserted into the nasal bone served as reference ECoG and EThG recordings were checked visually to exclude artifacts 1.4.2 Analysis of Time-Variant and Multivariate Causal In uences Within Distinct Thalamo-Cortical Networks In order to... autoregressive models Since a vector autoregressive process is linear by construction, only linear Granger-causality can be inferred by this methodology In the following, we will use the notion causality in terms of linear Granger-causality although not explicitly mentioned The parametric analysis techniques introduced in the following are based on modeling the multivariate system by stationary n-dimensional . disciplines and new the- oretical advances are matched by an increasing demand from an expanding diversity of applications. Consequently, signal and image processing has been established as an independent. adaptive methods in image processing. The presented results are in its majority the outcome of the DFG-priority program SPP 1114 Mathematical methods for time series analysis and digital image processing Potsdam Germany jkurths@agnld.uni-potsdam.de Jens Timmer Universit ¨ at Freiburg Zentrum Datenanalyse Eckerstr. 1 79104 Freiburg Germany jens .timmer@ fdm.uni-freiburg.de ISBN: 97 8-3 -5 4 0-7 563 1-6 e-ISBN: 97 8-3 -5 4 0-7 563 2-3 Understanding