Image segmentation is a critical step in building a computer vision algorithm that is able to distinguish between separate objects in an image scene. Image segmentation is based on two fundamentally intertwined components: pixel comparison and pixel grouping. In the pixel comparison step, pixels are determined to be similar or different from each other. In pixel grouping, those pixels which are similar are grouped together to form meaningful regions which can later be processed. This thesis makes original contributions to both of those areas. First, given a Markov Random Field framework, a Stochastic Nested Aggregation (SNA) framework for pixel and region grouping is presented and thoroughly analyzed using a Potts model. This framework is applicable in general to graph partitioning and discrete estimation problems where pairwise energy models are used. Nested aggregation reduces the computational complexity of stochastic algorithms such as Simulated Annealing to order O(N) while at the same time allowing local deterministic approaches such as Iterated Conditional Modes to escape most local minima in order to become a global deterministic optimization method. SNA is further enhanced by the introduction of a Graduated Models strategy which allows an optimization algorithm to converge to the model via several intermediary models. A well-known special case of Graduated Models is the Highest Confidence First algorithm which merges pixels or regions that give the highest global energy decrease. Finally, SNA allows us to use different models at different levels of coarseness. For coarser levels, a mean-based Potts model is introduced in order to compute region-to-region gradients based on the region mean and not edge gradients. Second, we develop a probabilistic framework based on hypothesis testing in order to achieve color constancy in image segmentation. We develop three new shading invariant semi-metrics based on the Dichromatic Reflection Model. An RGB image is transformed into an R'G'B' highlight invariant space to remove any highlight components, and only the component representing color hue is preserved to remove shading effects. This transformation is applied successfully to one of the proposed distance measures. The probabilistic semi-metrics show similar performance to vector angle on images without saturated highlight pixels; however, for saturated regions, as well as very low intensity pixels, the probabilistic distance measures outperform vector angle. Third, for interferometric Synthetic Aperture Radar image processing we apply the Potts model using SNA to the phase unwrapping problem. We devise a new distance measure for identifying phase discontinuities based on the minimum coherence of two adjacent pixels and their phase difference. As a comparison we use the probabilistic cost function of Carballo as a distance measure for our experiments.

La différenciation cellulaire et la spécification des tissus biologiques dépendent en partie de l'établissement de programmes d'expression génétique caractéristiques. Ces programmes sont le résultat de l'interprétation de l'information génomique par des Facteurs de Transcription (TFs) se fixant à des séquences d'ADN spécifiques. Décoder cette information dans les génomes séquencés est donc un enjeu majeur. Dans une première partie, nous étudions l'interaction entre les TFs et leurs sites de fixation sur l'ADN. L'utilisation d'un modèle de Potts inspiré de la physique des verres de spin et de données de fixation à grande échelle pour plusieurs TFs de la drosophile et des mammifères permet de montrer que les sites de fixation exhibent des corrélations entre nucléotides. Leur prise en compte permet d'améliorer significativement la prédiction des sites de fixations sur le génome. Nous présentons ensuite Imogene, l'extension au cas des mammifères d'un algorithme bayésien utilisant la phylogénie afin d'identifier les motifs et modules de cis-régulation (CRMs) contrôlant l'expression d'un ensemble de gènes co-régulés, qui a précédemment été appliqué au cas de la régulation chez les drosophiles. Partant d'un ensemble d'apprentissage constitué d'un petit nombre de CRMs chez une espèce de référence, et sans connaissance a priori des TFs s'y fixant, l'algorithme utilise la sur-représentation et la conservation des sites de fixation chez des espèces proches pour prédire des régulateurs putatifs ainsi que les CRMs génomiques sous-tendant la co-régulation. Nous montrons en particulier qu'Imogene peut distinguer des modules de régulation conduisant à différents motifs d'expression génétique sur la seule base de leur séquence ADN. Enfin, nous présentons des applications de ces outils de modélisation à des cas biologiques réels : la différenciation des trichomes chez la drosophile, et la différenciation musculaire chez la souris. Dans les deux cas, les prédictions ont été validées expérimentalement en collaboration avec des équipes de biologistes, et pointent vers une grande flexibilité des processus de cis-régulation.

Image segmentation is a critical step in building a computer vision algorithm that is able to distinguish between separate objects in an image scene. Image segmentation is based on two fundamentally intertwined components: pixel comparison and pixel grouping. In the pixel comparison step, pixels are determined to be similar or different from each other. In pixel grouping, those pixels which are similar are grouped together to form meaningful regions which can later be processed. This thesis makes original contributions to both of those areas. First, given a Markov Random Field framework, a Stochastic Nested Aggregation (SNA) framework for pixel and region grouping is presented and thoroughly analyzed using a Potts model. This framework is applicable in general to graph partitioning and discrete estimation problems where pairwise energy models are used. Nested aggregation reduces the computational complexity of stochastic algorithms such as Simulated Annealing to order O(N) while at the same time allowing local deterministic approaches such as Iterated Conditional Modes to escape most local minima in order to become a global deterministic optimization method. SNA is further enhanced by the introduction of a Graduated Models strategy which allows an optimization algorithm to converge to the model via several intermediary models. A well-known special case of Graduated Models is the Highest Confidence First algorithm which merges pixels or regions that give the highest global energy decrease. Finally, SNA allows us to use different models at different levels of coarseness. For coarser levels, a mean-based Potts model is introduced in order to compute region-to-region gradients based on the region mean and not edge gradients. Second, we develop a probabilistic framework based on hypothesis testing in order to achieve color constancy in image segmentation. We develop three new shading invariant semi-metrics based on the Dichromatic Reflection Model. An RGB image is transformed into an R'G'B' highlight invariant space to remove any highlight components, and only the component representing color hue is preserved to remove shading effects. This transformation is applied successfully to one of the proposed distance measures. The probabilistic semi-metrics show similar performance to vector angle on images without saturated highlight pixels; however, for saturated regions, as well as very low intensity pixels, the probabilistic distance measures outperform vector angle. Third, for interferometric Synthetic Aperture Radar image processing we apply the Potts model using SNA to the phase unwrapping problem. We devise a new distance measure for identifying phase discontinuities based on the minimum coherence of two adjacent pixels and their phase difference. As a comparison we use the probabilistic cost function of Carballo as a distance measure for our experiments.

Cette thèse présente de manière synthétique mes travaux de recherche dont les deux thématiques principales sont le comportement critique du modèle de Potts en présence de désordre et le vieillissement de modèles de spin lors d'une trempe.

Cette thèse s'inscrit dans l'étude mathématique de la percolation, qui regroupe une famille de modèles présentant une transition de phase. Des avancées majeures au cours des quinze dernières années, notamment l'invention du SLE et la preuve de l'invariance conforme de la percolation de Bernoulli critique, nous permettent aujourd'hui d'avoir une image très complète de la percolation de Bernoulli sur le réseau triangulaire. Cependant, de nombreuses questions demeurent ouvertes, et ont motivé notre travail.La première d'entre elle est l'universalité de la percolation plane, qui affirme que les propriétés macroscopiques de la percolation plane critique ne devraient pas dépendre du réseau sous-jacent à sa définition. Nous montrons, dans le cadre de la percolation Divide and Color, un résultat qui va dans le sens de cette universalité et identifions, dans ce contexte, des phénomènes macroscopiques indépendants du réseau microscopique. Une version plus faible d'universalité est donnée par la théorie de Russo-Seymour-Welsh (RSW), et sa validité est connue pour la percolation de Bernoulli (sans dépendance) sur les réseaux plans suffisamment symétriques. Nous étudions de nouveaux arguments de type RSW pour des modèles de percolation avec dépendance. La deuxième question que nous avons abordée est celle de l'absence d'une composante connexe ouverte infinie au point critique, une question importante du point de vue physique, puisqu'elle traduit la continuité de la transition de phase. Dans deux travaux en collaboration avec Hugo Duminil-Copin et Vladas Sidoravicius, nous montrons que la transition de phase est continue pour la percolation de Bernoulli sur le graphe Z^2x{0,...,k}, et pour la percolation FK sur le réseau carré avec paramètre q inférieur ou égal à 4. Enfin, la dernière question qui nous a guidés est la localité du point critique : la donnée des boules de grands rayons d'un graphe suffit-elle à identifier avec une bonne précision la valeur du point critique? Dans un travail en collaboration avec Sébastien Martineau, nous répondons de manière affirmative à cette question dans le cadre des graphes de Cayley de groupes abéliens.

Es werden physikallische Eigenschaften von Quasikristallen anhand von quasiperiodischen Ising- und Tight-Binding-Modellen auf dem fuenfzaehligen Penrose- und achtzaehligen Amman-Beenker-Muster untersucht. Bei den Ising-Modellen wird eine graphische Hochtemperaturentwicklung der freien Energie ausgerechnet und die kritischen Parameter des ferromagnetischen Phasenueberganges abgeschaetzt. Weiterhin wird mittels eines analytischen Resultates die freie Energie auf den periodischen Approximanten quasiperiodischer Muster exakt ausgerechnet und zur Bestimmung der Verteilung komplexer (Fisher-)Nullstellen herangezogen. Letztendlich wird noch ein Ising-Modell mit einem verschiedenen, nicht-Onsager kritischen Verhalten konstruiert und untersucht. Im zweiten Kapitel werden kritische, nichtnormierbare Eigenzustaende eines quasiperiodischen Tight-Binding-Modells exakt berechnet. Es stellt sich heraus, dass die Eigenzustaende eine selbstaehnliche, fraktale Struktur aufweisen die in Details untersucht wird.