The focus of this thesis is to investigate the impact of the boundary conditions on configurations in the Abelian sandpile model. We have two main results to present in this thesis. Firstly we give a family of continuous, measure preserving, almost one-to-one mappings from the wired spanning forest to recurrent sandpiles. In the special case of $Z^d$, $d \geq 2$, we show how these bijections yield a power law upper bound on the rate of convergence to the sandpile measure along any exhaustion of $Z^d$. Secondly we consider the Abelian sandpile on ladder graphs. For the ladder sandpile measure, $\nu$, a recurrent configuration on the boundary, I, and a cylinder event, E, we provide an upper bound for $\nu(E|I) − \nu(E)$.

We propose algorithms for organization of images in wide-area sparse-view datasets. In such datasets, if the images overlap in scene content, they are related by wide-baseline geometric transformations. The challenge is to identify these relations even if the images sparingly overlap in their content. The images in a dataset are then grouped into sets of related images with the relations captured in each set as a basal (minimal and foundational) graph structures. Images form the vertices in the graph structure and the edges define the geometric relations between the images. We use these basal graphs for geometric walkthroughs and detection of noisy location (GPS) and orientation (magnetometer) information that may be stored with each image. We have five algorithmic contributions. First, we propose an algorithm BLOGS (Balanced Local and Global Search) that uses a novel hybrid Markov Chain Monte Carlo (MCMC) strategy called 'hop-diffusion' for epipolar geometry estimation between a pair of wide-baseline images that is 10 times faster and more accurate than the state-of-the-art. Hops are global searches and diffusions are local searches. BLOGS is able to handle very wide-baseline views characteristic of wide-area sparse-view datasets. It also produces a geometric match score between an image pair. Second, we propose a photometric match score, the Cumulative Correspondence Score (CCS). The proposed photometric scores are fast approximations of the computationally expensive geometric scores. Third, we use the photometric scores and the geometric scores to find groups of related images and to organize them in the form of basal graph structures using a novel hybrid algorithm we call theCOnnected component DIscovery by Minimally Specifying an Expensive Graph (CODIMSEG). The objective of the algorithm is to minimize the number of geometric estimations and yield results similar to what would be achieved if all-pair geometric matching were done. We compared the performances of the CCS and CODIMSEG algorithms with GIST (means summary of an image) and k-Nearest Neighbor (k-NN) based approaches. We found that CCS and CODIMSEG perform significantly better than GIST and k-NN respectively in identifying visually connected images. Our algorithm achieved more than 95% true positive rate at 0% false positive rate. Fourth, we propose a basal tree graph expansion algorithm to make the basal graphs denser for applications like geometric walk-throughs using the minimum Hamiltonian path algorithm and detection of noisy position (GPS) and orientation (magnetometer) tags. We propose two versions of geometric walkthroughs, one using minimum spanning tree based approximation of the minimum Hamiltonian path on the basal tree graphs and other using the Lin-Kernighan heuristic approximation on the expanded basal graph. Conversion of a non-linear tree structure to a linear path structure leads to discontinuities in path. The Lin-Kernighan algorithm on the expanded basal graphs is shown to be a better approach. Fifth, we propose a vision based geometric voting algorithm to detect noisy GPS and magnetometer tags using the basal graphs. This problem has never been addressed before to the best of our knowledge. We performed our experiments on the Nokia dataset (which has 243 images in the 'Lausanne' dataset and 105 images in the 'Demoset'), ArtQuad dataset (6514 images) and Oxford dataset (5063 images). All the three datasets are very different. Nokia dataset is a very wide-baseline sparse-view dataset. ArtQuad dataset is a wide-baseline dataset with denser views compared to the Nokia dataset. Both these datasets have GPS tagged images. Nokia dataset has magnetometer tags too. ArtQuad dataset has 348 images with the commercial GPS information as well as high precision differential GPS data which serves as ground truth for our noisy tag detection algorithm. Oxford dataset is a wide-baseline dataset with plenty of distracters that test the algorithm's capability to group images correctly. The larger datasets test the scalability of our algorithms. Visually inspected feature matches and image matches were used as ground truth in our experiments. All the experiments were done on a single PC.

In this thesis we study the application of a novel sampling technique to building fully-dynamic randomized graph algorithms. We present the following results: \begin{enumerate} \item A randomized algorithm to estimate the size of a cut in an undirected graph $G = (V, E)$ where $V$ is the set of nodes and $E$ is the set of edges and $n = |V|$ and $m = |E|$. Our algorithm processes edge insertions and deletions in $O(\log^2n)$ time. For a cut $(U, V\setminus U)$ of size $K$ for any subset $U$ of $V$, $|U| < |V|$ our algorithm returns an estimate $x$ of the size of the cut satisfying $K/2 \leq x \leq 2K$ with high probability in $O(|U|\log n)$ time. \item A randomized distributed algorithm for maintaining a spanning forest in a fully-dynamic synchronous network. Our algorithm maintains a spanning forest of a graph with $n$ nodes, with worst case message complexity $\tilde{O}(n)$ per edge insertion or deletion where messages are of size $O(\text{polylog}(n))$. For each node $v$ we require memory of size $\tilde{O}(degree(v))$ bits. This improves upon the best previous algorithm with respect to worst case message complexity, given by Awerbuch, Cidon, and Kutten, which has an amortized message complexity of $O(n)$ and worst case message complexity of $O(n^2)$. \end{enumerate} / Graduate / 0984 / b_mountjoy9@hotmail.com

Les techniques de segmentation de graphe sont souvent utilisées en traitement d’images puisque ces dernières peuvent être vues comme des graphes valués. Dans cette thèse, nous montrons des liens existant entre plusieurs paradigmes de segmentation de graphes valués. Nous présentons tout d’abord différentes définitions de ligne de partage des eaux et sélectionnons celle dont le cadre permet la comparaison avec des forêts couvrantes particulières. Nous montrons qu’une telle ligne de partage des eaux relative à des marqueurs arbitraires est équivalente à une coupe induite par une forêt couvrante de chemins de moindre altitude. Ensuite, les coupes induites par des forêts couvrantes de poids minimum sont démontrées comme étant des cas particuliers ayant l’avantage d’éviter certaines segmentations non souhaitées. Enfin, nous montrons qu’une coupe minimale coïncide avec une coupe induite par une forêt couvrante de poids maximum pour certaines fonctions de poids particulières. Dans une seconde partie, nous présentons deux applications utilisant la segmentation de graphe : la renaissance d’images et le mélange de textures pour la reconstruction 3D / Graph segmentation techniques are often used in image processing since an image can be seen as a weighted graph. In this thesis, we show some links existing between several weighted graph segmentation paradigms. We first present different definitions of watersheds and select the one which framework allows comparison with specific spanning forests. We show that such a watershed relative to arbitrary markers is equivalent to a cut induced by a shortest path spanning forest. Then, cuts induced by minimum spanning forests are demonstrated as being particular cases which advantageously avoid some undesirable results. Finally, we show that minimum cuts coincide with cuts induced by maximum spanning forests for some particular weight functions. In a second part, we present two applications using graph segmentation : image renaissance and texture blending for 3D reconstruction

Orientador: Roberto de Alencar Lotufo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T08:32:02Z (GMT). No. of bitstreams: 1 Audigier_RomaricMatthiasMichel_D.pdf: 1753584 bytes, checksum: 1d31eb6f095099ffb5c3ec8d0a96a9cf (MD5) Previous issue date: 2007 / Resumo: Esta tese introduz o novo conceito de transformada de zona de empate que unifica as múltiplas soluções de uma transformada de watershed, conservando apenas as partes comuns em todas estas, tal que as partes que diferem constituem a zona de empate. A zona de empate aplicada ao watershed via transformada imagem-floresta (TZ-IFT-WT) se revela um elo inédito entre transformadas de watershed baseadas em paradigmas muito diferentes: gota d'água, inundação, caminhos ótimos e floresta de peso mínimo. Para todos esses paradigmas e os algoritmos derivados, é um desafio se ter uma solução única, fina, e que seja consistente com uma definição. Por isso, propõe-se um afinamento da zona de empate, único e consistente. Além disso, demonstra-se que a TZ-IFT-WT também é o dual de métodos de segmentação baseados em conexidade nebulosa. Assim, a ponte criada entre as abordagens morfológica e nebulosa permite aproveitar avanços de ambas. Em conseqüência disso, o conceito de núcleo de robustez para as sementes é explorado no caso do watershed. / Abstract: This thesis introduces the new concept of tie-zone transform that unifies the multiple solutions of a watershed transform, by conserving only the common parts among them such that the differing parts constitute the tie zone. The tie zone applied to the watershed via image-foresting transform (TZ-IFTWT) proves to be a link between watershed transforms based on very different paradigms: drop of water, flooding, optimal paths and forest of minimum weight. For all these paradigms and the derived algorithms, it is a challenge to get a unique and thin solution which is consistent with a definition. That is why we propose a unique and consistent thinning of the tie zone. In addition, we demonstrate that the TZ-IFT-WT is also the dual of segmentation methods based on fuzzy connectedness. Thus, the bridge between the morphological and the fuzzy approaches allows to take benefit from the advance of both. As a consequence, the concept of cores of robustness for the seeds is exploited in the case of watersheds. / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica