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.

Propomos o estudo do meio desordenado onde a caminhada determinista parcialmente autorrepulsiva (CDPA) é desenvolvida e o estudo da caminhada aleatória autorrepulsiva (SAW) em rede regular. O meio desordenado na CDPA, gerado por um processo Poissônico espacial, é caracterizado pela estatística de vizinhança e de distâncias. A estatística de vizinhança mede a probabilidade de um ponto ser $m$-ésimo vizinho mais próximo de seu $n$-ésimo vizinho mais próximo. A estatística de distâncias mede a distribuição de distância de um ponto ao seu $k$-ésimo vizinho mais próximo. No problema da estatística de distâncias, calculamos a função densidade de probabilidade (pdf) e estudamos os casos limites de alta ordem de vizinhança e alta dimensionalidade. Um caso particular dessa pdf pode verificar se um conjunto de pontos foi gerado por um processo Poissônico. Na SAW em rede regular, um caminhante escolhe aleatoriamente um sítio adjacente para ser visitado no próximo passo, mas é proibido visitar um sítio duas ou mais vezes. Desenvolvemos uma nova abordagem para estudar grandezas conformacionais por meio do produto escalar entre o vetor posição e vetor deslocamento no $j$-ésimo passo: $\\langle\\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}$. Mostramos que para $j=N$ o produto escalar é igual ao comprimento de persistência (projeção do vetor posição na direção do primeiro passo) e que converge para uma constante. Calculamos a distância quadrática média ponta-a-ponta, $\\langle \\vec{R}_{N}^{2}angle_{N}\\sim N^{2 u_{0}}$, como o somatório de $1\\leq j \\leq N$ do produto escalar. Os dados gerados pelo algoritmo de simulação Monte Carlo, codificado em linguagem C e paralelizado em MPI, fornecem o expoente $ u_{0}$ da regra de escala $\\langle \\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}\\sim j^{2 u_{0}-1}$, para $1\\leq j \\leq \\Theta(N)$, próximo ao valor esperado. A partir de $\\Theta(N)\\approx N/2$ para rede quadrada e $\\Theta(N)\\approx N/3$ para rede cúbica, a caminhada torna-se mais flexível devido ao maior número de graus de liberdade disponível nos últimos passos. / We propose the study of disordered media where the deterministic partially self-avoiding walk (DPSW) is developed and the study of self-avoiding random walk (SAW) in regular lattices. The disordered media in the DPSW, generated by a spatial Poissonian process, is characterized by neighborhood and distance statistics. Neighborhood statistics quantifies the probability of a point to be the $m$th nearest neighbor of its $n$th nearest neighbor. Distance statistics quantifies the distance distribution of a given point to its $k$th nearest neighbor. For the distance statistics problem, we obtain the probability density function (pdf) and study the high dimensionality and high neighborhood order limits. A particular case of this pdf can verify if a points set is generated by a Poissonian process. In a SAW in regular lattice, the walker randomly chooses an adjacent site to be visited in the next step, but is forbidden to visit a site two or more times. We developed a new approach to study conformational quantities of SAW by means of the scalar product between the position vector and the displacement vector in the $j$th step: $\\langle\\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}$. We show that for $j=N$ the scalar product is equal to the persistence length (projection of position vector in the direction of the first step) and that converges to a constant. We compute the square end-to-end distance, $\\langle \\vec{R}_{N}^{2}angle_{N}\\sim N^{2 u_{0}}$, as the summation $1\\leq j \\leq N$ of scalar product. The data generated by Monte Carlo simulation algorithm, coded in C language and parallelized in MPI, provides the exponent $ u_{0}$ of the scaling law $\\langle \\vec{R}_{j}\\cdot\\vec{u}_{j}angle_{N}\\sim j^{2 u_{0}-1}$, for $1\\leq j \\leq \\Theta(N)$, close to the expected value. Starting from $\\Theta(N)\\approx N/2$ for square lattice and $\\Theta(N)\\approx N/3$ for cubic lattice, the walk becomes more flexible due to the large number of degrees of freedom available in the last steps.

No description available.

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.

This dissertation explores how children communicate their experiences of place. It focuses on the qualitative methods of group interviews, walks, drawings and photographs, and asks how children communicate different aspects of place. Drawing on feminist theory and qualitative methodology, the importance of situated knowledge for understanding children’s narratives is argued. Through studies in Sweden and England, it is shown how children’s place experiences are multi-dimensional, consisting of both concrete and abstract processes, places and objects. The different methods reveal different aspects of these dimensions and the children provided rich evidence of their experience of place in regard to physical, social and cultural aspects. It is found that children’s individuality affects the success of the methods, rather than factors such as gender, age or nationality. The methods’ different characteristics, such as creative and interactive aspects, and how power relations are reflected through them are determining factors as to how and what children communicate. Place-interactive methods allow children to communicate the direct experience of place and include subconscious actions as communication occurs through movement and play. The creative aspects of the methods allow children to focus more on their abstract experiences and to include experiences based on a wider time perspective than the present. Walking is discussed as a critical method for the researcher to include place as an active and multi-sensuous phenomenon. As it is shown that the methods reveal different aspects of the children’s place experiences, it is also discussed how this can be used from an adult perspective.