Ce travail est consacré à certaines classes de systèmes dynamiques ergodiques, munis d'une mesure invariante infinie, telles que des applications de l'intervalle avec un point fixe neutre ou des marches aléatoires. Le comportement asymptotique des sommes de Birkhoff d'observables d'intégrale non nulle est assez bien connu, pour peu que le système ait une certaine forme d'hyperbolicité. Une situation particulièrement intéressante est celle des tours au-dessus d'une application Gibbs-Markov. Nous cherchons dans ce contexte à étudier le cas d'observables d'intégrale nulle. Nous obtenons ainsi une forme de théorème central limite pour des systèmes dynamiques munis d'une mesure infinie. Après avoir introduit l'ensemble des notions nécessaires, nous adaptons des résultats de E. Csáki et A. Földes sur les marches aléatoires au cas des applications Gibbs-Markov. Les théorèmes d'indépendance asymptotique qui en découlent forment le cœur de cette thèse, et permettent de démontrer un théorème central limite généralisé. Quelques variations sur l'énoncé de ce théorème sont obtenues. Ensuite, nous abordons les processus en temps continu, tels que des semi-flots et des flots. Un premier travail consiste à étudier les propriété en temps grand du temps de premier retour et du temps local pour des extensions de systèmes dynamiques, ce qui se fait par des méthodes spectrales. Enfin, par réductions successives, nous pouvons obtenir une version du théorème central limite pour des flots périodiques, et en particulier le flot géodésique sur le fibré tangent unitaire de certaines variétés périodiques hyperboliques. / This work is focused on some classes of ergodic dynamical systems endowed with an infinite invariant measure, such as transformations of the interval with a neutral fixed point or random walks. The asymptotic behavior of the Birkhoff sums of observables with a non-zero integral is well known, as long as the system shows some kind of hyperbolicity. The towers over a Gibbs-Markov map are especially interesting. In this context, we aim to study the case of observables whose integral is zero. We get the equivalent of a central limit theorem for some dynamical systems endowed with an infinite measure. After we introduce the necessary definitions, we adapt some results by E. Csáki and A. Földes on random walks to the case of Gibbs-Markov maps. We derive a theorem on the asymptotic independence of Birhoff sums, which is the core of this thesis, and from this point we work out a generalised central limit theorem. We also prove a few variations on this generalised central limit theorem. Then, we study dynamical systems in continuous time, such as semi-flows and flows. We first work on the asymptotic properties of the first return time and the local time for extensions of dynamical systems; this is done by spectral methods. Finally, step by step, we extend our generalised central limit theorem to cover some periodic flows, and in particular the geodesic flow on the unitary tangent bundle of some hyperbolic periodic manifolds.

University of Macau / Faculty of Science and Technology. / Department of Computer and Information Science

Estudamos sistemas de passeios aleatórios sobre os vértices de um grafo completo. Inicialmente há uma partícula em cada vértice do grafo das quais somente uma está ativa, as outras estão inativas. A partícula ativa realiza um passeio aleatório simples a tempo discreto com tempo de vida que depende do passado do processo, movendo-se ao longo de elos. Quando uma partícula ativa encontra uma inativa, esta se ativa; quando salta sobre um vértice já visitado, morre. O objetivo desta dissertação é estudar a cobertura do grafo completo, ou seja, a proporção de vértices visitados ao fim do processo, quando o número $n$ de vértices tende ao infinito. Analisamos as equações de campo médio para o processo descrito acima, comparando os seus resultados com os do modelo aleatório. Aqui, os resultados do campo médio parecem reproduzir os do modelo aleatório. Depois, apresentamos um estudo similar entre o modelo estocástico e as equações de campo médio para o caso em que cada partícula possui 2 vidas. Finalmente, observamos a cobertura do grafo completo para as equações de campo médio quando o número de vidas por partículas é maior que dois. / We study random walks systems on complete graphs. Initially there is a particle at each vertex of the graph; only one is active and the other are inactive. An active particle performs a discrete-time simple random walk with lifetime depending on the past of the process moving along edges. When an active particle hits an inactive one, the latter is activated. When it jumps on a vertex which has been visited before it dies. The goal of this work is to study the coverage of the complete graph, that is, the proportion of visited vertices at the end of the process, when the number of vertices goes to infinity. We analyze the mean field equations to the process cited above, comparing their results with the ones of the random model. Here the results of the mean field approach seem to reproduce the ones of the random model. After we present a similar study between the stochastic model and mean field approximation to the case that each particle has 2 lifes. Finally we observe the coverage of the complete graph to the mean-field equations when the number of lifes by particle is bigger than two.

Nous déterminons d’abord l’impact d’un plan infini réfléchissant sur l’espace occupé par une marche brownienne bidimensionnelle à un temps fixé, que nous caractérisons par le périmètre moyen de son enveloppe convexe (plus petit polygone convexe contenant toute la trajectoire). Nous déterminons également la longueur moyenne de la portion du plan visitée par le marcheur, et la probabilité de survie d’un marcheur brownien dans un secteur angulaire absorbant.Nous étudions ensuite le temps mis par un marcheur sur réseau pour visiter tous les sites d’un volume, ou une partie d’entre eux. Nous calculons la moyenne de ce temps, dit de couverture, à une dimension pour une marche aléatoire persistante. Nous déterminons également la distribution du temps de couverture et d’autres observables assimilées pour la classe des processus non compacts, qui décrivent un large spectre de recherches aléatoires.Dans un troisième temps, nous calculons et analysons la probabilité de sortie conditionnelle d’un marcheur brownien évoluant dans un intervalle se dilatant ou se contractant à vitesse constante.Enfin, nous étudions plusieurs aspects du modèle du marcheur aléatoire “affamé”, qui meurt si les visites de nouveaux sites, grâce auxquelles il engrange des ressources, ne sont pas suffisamment regulières. Nous en proposons un traitement de type champ moyen à deux dimensions, puis nous déterminons l’impact de la régénération des ressources sur les propriétés de survie du marcheur. Nous considérons finalement un modèle d’exploitation de parcelles de nourriture prenant explicitement en compte le mouvement du marcheur, qui se ramène de manière naturelle au modèle du marcheur aléatoire affamé. / We first determine the impact of an infinite reflecting wall on the space occupied by a planar Brownian motion at a fixed observation time. We characterize it by the mean perimeter of its convex hull, defined as the minimal convex polygon enclosing the whole trajectory. We also determine the mean length of the visited portion of the wall, and the survival probability of a Brownian walker in an absorbing wedge.We then study the time needed for a lattice random walker to visit every site of a confined volume, or a fraction of them. We calculate the mean value of this so-called cover time in one dimension for a persistant random walk. We also determine the distribution of the cover time and related observables for the class of non compact processes, which describes a wide range of random searches.After that, we calculate and analyze the splitting probability of a one-dimensional Brownian walker evolving in an expanding or contracting interval.Last, we study several aspects of the model of starving random walk, where the walker starves if its visits to new sites, from which it collects resources, are not regular enough. We develop a mean-field treatment of this model in two dimensions, then determine the impact of regeneration of resources on the survival properties of the walker. We finally consider a model of exploitation of food patches taking explicitly into account the displacement of the walker in the patches, which can be mapped onto the starving random walk model.

Estudamos sistemas de passeios aleatórios sobre os vértices de um grafo completo. Inicialmente há uma partícula em cada vértice do grafo das quais somente uma está ativa, as outras estão inativas. A partícula ativa realiza um passeio aleatório simples a tempo discreto com tempo de vida que depende do passado do processo, movendo-se ao longo de elos. Quando uma partícula ativa encontra uma inativa, esta se ativa; quando salta sobre um vértice já visitado, morre. O objetivo desta dissertação é estudar a cobertura do grafo completo, ou seja, a proporção de vértices visitados ao fim do processo, quando o número $n$ de vértices tende ao infinito. Analisamos as equações de campo médio para o processo descrito acima, comparando os seus resultados com os do modelo aleatório. Aqui, os resultados do campo médio parecem reproduzir os do modelo aleatório. Depois, apresentamos um estudo similar entre o modelo estocástico e as equações de campo médio para o caso em que cada partícula possui 2 vidas. Finalmente, observamos a cobertura do grafo completo para as equações de campo médio quando o número de vidas por partículas é maior que dois. / We study random walks systems on complete graphs. Initially there is a particle at each vertex of the graph; only one is active and the other are inactive. An active particle performs a discrete-time simple random walk with lifetime depending on the past of the process moving along edges. When an active particle hits an inactive one, the latter is activated. When it jumps on a vertex which has been visited before it dies. The goal of this work is to study the coverage of the complete graph, that is, the proportion of visited vertices at the end of the process, when the number of vertices goes to infinity. We analyze the mean field equations to the process cited above, comparing their results with the ones of the random model. Here the results of the mean field approach seem to reproduce the ones of the random model. After we present a similar study between the stochastic model and mean field approximation to the case that each particle has 2 lifes. Finally we observe the coverage of the complete graph to the mean-field equations when the number of lifes by particle is bigger than two.

The subject of this thesis is a class of fast inpainting methods (image or video) based on the idea of filling the inpainting domain in successive shells from its boundary inwards. Image pixels (or video voxels) are filled by assigning them a color equal to a weighted average of either their already filled neighbors (the ``direct'' form of the method) or those neighbors plus additional neighbors within the current shell (the ``semi-implicit'' form). In the direct form, pixels (voxels) in the current shell may be filled independently, but in the semi-implicit form they are filled simultaneously by solving a linear system. We focus in this thesis mainly on the image inpainting case, where the literature contains several methods corresponding to the {\em direct} form of the method - the semi-implicit form is introduced for the first time here. These methods effectively differ only in the order in which pixels (voxels) are filled, the weights used for averaging, and the neighborhood that is averaged over. All of them are very fast, but at the same time all of them leave undesirable artifacts such as ``kinking'' (bending) or blurring of extrapolated isophotes. This thesis has two main goals. First, we introduce new algorithms within this class, which are aimed at reducing or eliminating these artifacts, and also target a specific application - the 3D conversion of images and film. The first part of this thesis will be concerned with introducing 3D conversion as well as Guidefill, a method in the above class adapted to the inpainting problems arising in 3D conversion. However, the second and more significant goal of this thesis is to study these algorithms as a class. In particular, we develop a mathematical theory aimed at understanding the origins of artifacts mentioned. Through this, we seek is to understand which artifacts can be eliminated (and how), and which artifacts are inevitable (and why). Most of the thesis is occupied with this second goal. Our theory is based on two separate limits - the first is a {\em continuum} limit, in which the pixel width →0, and in which the algorithm converges to a partial differential equation. The second is an asymptotic limit in which h is very small but non-zero. This latter limit, which is based on a connection to random walks, relates the inpainted solution to a type of discrete convolution. The former is useful for studying kinking artifacts, while the latter is useful for studying blur. Although all the theoretical work has been done in the context of image inpainting, experimental evidence is presented suggesting a simple generalization to video. Finally, in the last part of the thesis we explore shell-based video inpainting. In particular, we introduce spacetime transport, which is a natural generalization of the ideas of Guidefill and its predecessor, coherence transport, to three dimensions (two spatial dimensions plus one time dimension). Spacetime transport is shown to have much in common with shell-based image inpainting methods. In particular, kinking and blur artifacts persist, and the former of these may be alleviated in exactly the same way as in two dimensions. At the same time, spacetime transport is shown to be related to optical flow based video inpainting. In particular, a connection is derived between spacetime transport and a generalized Lucas-Kanade optical flow that does not distinguish between time and space.

This thesis studies connections between disorder type in tree polymers and the branching random walk and presents an application to swarm site-selection. Chapter two extends results on tree polymers in the infinite volume limit to critical strong disorder. Almost sure (a.s.) convergence in the infinite volume limit is obtained for weak disorder by standard theory on multiplicative cascades or the branching random walk. Chapter three establishes results for a simple branching random walk in connection with a related tree polymer. A central limit theorem (CLT) is shown to hold regardless of polymer disorder type, and a.s. connectivity of the support is established in the asymmetric case. Chapter four contains a model for site-selection in honeybee swarms. Simulations demonstrate a trade-off between speed and accuracy, and strongly suggest that increasing the quorum threshold at which the process terminates usually improves decision performance. / Graduation date: 2013

In normal everyday viewing, we perform large eye movements (saccades) and miniature or fixational eye movements. Most of our visual perception occurs while we are fixating. However, our eyes are perpetually in motion. Properties of these fixational eye movements, which are partly controlled by the brainstem, change depending on the task and the visual conditions. Currently, fixational eye movements are poorly understood because they serve the two contradictory functions of gaze stabilization and counteraction of retinal fatigue. In this dissertation, we investigate the spatial and temporal properties of time series of eye position acquired from participants staring at a tiny fixation dot or at a completely dark screen (with the instruction to fixate a remembered stimulus); these time series were acquired with high spatial and temporal resolution. First, we suggest an advanced algorithm to separate the slow phases (named drift) and fast phases (named microsaccades) of these movements, which are considered to play different roles in perception. On the basis of this identification, we investigate and compare the temporal scaling properties of the complete time series and those time series where the microsaccades are removed. For the time series obtained during fixations on a stimulus, we were able to show that they deviate from Brownian motion. On short time scales, eye movements are governed by persistent behavior and on a longer time scales, by anti-persistent behavior. The crossover point between these two regimes remains unchanged by the removal of microsaccades but is different in the horizontal and the vertical components of the eyes. Other analyses target the properties of the microsaccades, e.g., the rate and amplitude distributions, and we investigate, whether microsaccades are triggered dynamically, as a result of earlier events in the drift, or completely randomly. The results obtained from using a simple box-count measure contradict the hypothesis of a purely random generation of microsaccades (Poisson process). Second, we set up a model for the slow part of the fixational eye movements. The model is based on a delayed random walk approach within the velocity related equation, which allows us to use the data to determine control loop durations; these durations appear to be different for the vertical and horizontal components of the eye movements. The model is also motivated by the known physiological representation of saccade generation; the difference between horizontal and vertical components concurs with the spatially separated representation of saccade generating regions. Furthermore, the control loop durations in the model suggest an external feedback loop for the horizontal but not for the vertical component, which is consistent with the fact that an internal feedback loop in the neurophysiology has only been identified for the vertical component. Finally, we confirmed the scaling properties of the model by semi-analytical calculations. In conclusion, we were able to identify several properties of the different parts of fixational eye movements and propose a model approach that is in accordance with the described neurophysiology and described limitations of fixational eye movement control. / Während des alltäglichen Sehens führen wir große (Sakkaden) und Miniatur- oder fixationale Augenbewegungen durch. Die visuelle Wahrnehmung unserer Umwelt geschieht jedoch maßgeblich während des sogenannten Fixierens, obwohl das Auge auch in dieser Zeit ständig in Bewegung ist. Es ist bekannt, dass die fixationalen Augenbewegungen durch die gestellten Aufgaben und die Sichtbedingungen verändert werden. Trotzdem sind die Fixationsbewegungen noch sehr schlecht verstanden, besonders auch wegen ihrer zwei konträren Hauptfunktionen: Das stabilisieren des Bildes und das Vermeiden der Ermüdung retinaler Rezeptoren. In der vorliegenden Dissertation untersuchen wir die zeitlichen und räumlichen Eigenschaften der Fixationsbewegungen, die mit hoher zeitlicher und räumlicher Präzision aufgezeichnet wurden, während die Versuchspersonen entweder einen sichtbaren Punkt oder aber den Ort eines verschwundenen Punktes in völliger Dunkelheit fixieren sollten. Zunächst führen wir einen verbesserten Algorithmus ein, der die Aufspaltung in schnelle (Mikrosakkaden) und langsame (Drift) Fixationsbewegungen ermöglicht. Den beiden Typen von Fixationsbewegungen werden unterschiedliche Beiträge zur Wahrnehmung zugeschrieben. Anschließend wird für die Zeitreihen mit und ohne Mikrosakkaden das zeitliche Skalenverhalten untersucht. Für die Fixationsbewegung während des Fixierens auf den Punkt konnten wir feststellen, dass diese sich nicht durch Brownsche Molekularbewegung beschreiben lässt. Stattdessen fanden wir persistentes Verhalten auf den kurzen und antipersistentes Verhalten auf den längeren Zeitskalen. Während die Position des Übergangspunktes für Zeitreihen mit oder ohne Mikrosakkaden gleich ist, unterscheidet sie sich generell zwischen horizontaler und vertikaler Komponente der Augen. Weitere Analysen zielen auf Eigenschaften der Mikrosakkadenrate und -amplitude, sowie Auslösemechanismen von Mikrosakkaden durch bestimmte Eigenschaften der vorhergehenden Drift ab. Mittels eines Kästchenzählalgorithmus konnten wir die zufällige Generierung (Poisson Prozess) ausschließen. Des weiteren setzten wir ein Modell auf der Grundlage einer Zufallsbewegung mit zeitverzögerter Rückkopplung für den langsamen Teil der Augenbewegung auf. Dies erlaubt uns durch den Vergleich mit den erhobenen Daten die Dauer des Kontrollkreislaufes zu bestimmen. Interessanterweise unterscheiden sich die Dauern für vertikale und horizontale Augenbewegungen, was sich jedoch dadurch erklären lässt, dass das Modell auch durch die bekannte Neurophysiologie der Sakkadengenerierung, die sich räumlich wie auch strukturell zwischen vertikaler und horizontaler Komponente unterscheiden, motiviert ist. Die erhaltenen Dauern legen für die horizontale Komponente einen externen und für die vertikale Komponente einen internen Kontrollkreislauf dar. Ein interner Kontrollkreislauf ist nur für die vertikale Kompoente bekannt. Schließlich wird das Skalenverhalten des Modells noch semianalytisch bestätigt. Zusammenfassend waren wir in der Lage, unterschiedliche Eigenschaften von Teilen der Fixationsbewegung zu identifizieren und ein Modell zu entwerfen, welches auf der bekannten Neurophysiologie aufbaut und bekannte Einschränkungen der Kontrolle der Fixationsbewegung beinhaltet.

Thesis (Ph.D.) - Carleton University, 2005. / Includes bibliographical references (p. 168-173). Also available in electronic format on the Internet.

Thèse (M.Eng.) -- Université du Québec à Chicoutimi, 2004. / Bibliogr.: f. [70]-76. Document électronique également accessible en format PDF. CaQCU