This thesis deals with the application of graph theory in image segmentation. There are specifically presented method utilizing graph cuts and extensions of this method. In the first chapter thera are initially explained basics of graph theory that are essential for understanding of the presented method. It is described in the second chapter, including its extensions that use shape priors. In the third chapter there is presented solution which is used for vertebrae lesion segmentation in the CT data sets. Final function is implemented into the program but it can be used also separately. Success rate is described using sensitivity and specificity in the last chapter, there are also examples of results.

This thesis is a detailed examination of the expressive power of valued constraints and related complexity questions. The valued constraint satisfaction problem (VCSP) is a generalisation of the constraint satisfaction problem which allows to describe a variety of combinatorial optimisation problems. Although most results are stated in this framework, they can be interpreted equivalently in the framework of, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation, or Markov Random Fields. We take a result of Cohen, Cooper and Jeavons that characterises the expressive power of valued constraint in terms of certain algebraic properties, and extend this result by showing yet another connection between the expressive power of valued constraints and linear programming. We prove a decidability result for fractional clones. We consider various classes of valued constraints and the associated cost functions with respect to the question of which of these classes can be expressed using only cost functions of bounded arities. We identify the first known example of an infinite chain of classes of constraints with strictly increasing expressive power. We present a full classification of various classes of constraints with respect to this problem. We study submodular constraints and cost functions. Submodular functions play a key role in combinatorial optimisation and are often considered to be a discrete analogue of convex functions. It has previously been an open problem whether all Boolean submodular cost functions can be decomposed into a sum of binary submodular cost functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of cost functions, we answer this question negatively. Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities that can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the (s,t)-Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

Los canales múltiple-entrada-múltiple-salida (MIMO) han sido ampliamente propuestos para superar los desvanecimientos aleatorios de canal en comunicaciones inalámbricas no selectivas en frecuencia. Basados en equipar tanto transmisores como receptores con múltiple antenas, sus ventajas son dobles. Por un lado, permiten al transmisor: i) concentrar la energía transmitida en una dirección-propia determinada, o ii) codificar entre antenas con el fin de superar desvanecimientos no conocidos de canal. Por otro lado, facilitan al receptor el muestreo de la señal en el dominio espacial. Esta operación, seguida por la combinación coherente de muestras, aumenta la relación señal a ruido de entrada al receptor. De esta forma, el procesado multi-antena es capaz de incrementar la capacidad (y la fiabilidad) de la transmisión en escenarios con alta dispersión.Desafortunadamente, no siempre es posible emplazar múltiples antenas en los dispositivos inalámbricos, debido a limitaciones de espacio y/o coste. Para estos casos, la manera más apropiada de explotar el procesado multi-antena es mediante retransmisión, consistente en disponer un conjunto de repetidores inalámbricos que asistan la comunicación entre un grupo de transmisores y un grupo de receptores, todos con una única antena. Con la ayuda de los repetidores, por tanto, los canales MIMO se pueden imitar de manera distribuida. Sin embargo, la capacidad exacta de las comunicaciones con repetidores (así como la manera en que este esquema funciona con respeto al MIMO equivalente) es todavía un problema no resuelto. A dicho problema dedicamos esta tesis.En particular, la presente disertación tiene como objetivo estudiar la capacidad de canales Gaussianos asistidos por múltiples repetidores paralelos. Dos repetidores se dicen paralelos si no existe conexión directa entre ellos, si bien ambos tienen conexión directa con la fuente y el destino de la comunicación. Nos centramos en el análisis de tres canales ampliamente conocidos: el canal punto-a-punto, el canal de múltiple-acceso y el canal de broadcast, y estudiamos su mejora de funcionamiento con repetidores. A lo largo de la tesis, se tomarán las siguientes hipótesis: i) operación full-duplex en los repetidores, ii) conocimiento de canal tanto en transmisión como en recepción, y iii) desvanecimiento sin memoria, e invariante en el tiempo.En primer lugar, analizamos el canal con múltiples repetidores paralelos, en el cual una única fuente se comunica con un único destino en presencia de N repetidores paralelos. Derivamos límites inferiores de la capacidad del canal por medio de las tasas de transmisión conseguibles con distintos protocolos: decodificar-y-enviar, decodificar-parcialmente-y-enviar, comprimir-y-enviar, y repetición lineal. Asimismo, con un fin comparativo, proveemos un límite superior, obtenido a través del Teorema de max-flow-min-cut. Finalmente, para el número de repetidores tendiendo a infinito, presentamos las leyes de crecimiento de todas las tasas de transmisión, así como la del límite superior.A continuación, la tesis se centra en el canal de múltiple-acceso (MAC) con múltiples repetidores paralelos. El canal consiste en múltiples usuarios comunicándose simultáneamente con un único destino en presencia de N repetidores paralelos. Derivamos una cota superior de la región de capacidad de dicho canal utilizando, de nuevo, el Teorema de max-flow-min-cut, y encontramos regiones de tasas de transmisión conseguibles mediante: decodificar-y-enviar, comprimir-y-enviar, y repetición lineal. Asimismo, se analiza el valor asintótico de dichas tasas de transmisión conseguibles, asumiendo el número de usuarios creciendo sin límite. Dicho estudio nos permite intuir el impacto de la diversidad multiusuario en redes de acceso con repetidores.Finalmente, la disertación considera el canal de broadcast (BC) con múltiples repetidores paralelos. En él, una única fuente se comunica con múltiples destinos en presencia de N repetidores paralelos. Para dicho canal, derivamos tasas de transmisión conseguibles dado: i) codificación de canal tipo dirty paper en la fuente, ii) decodificar-y-enviar, comprimir-y-enviar, y repetición lineal, respectivamente, en los repetidores. Además, para repetición lineal, demostramos que la dualidad MAC-BC se cumple. Es decir, la región de tasas de transmisión conseguibles en el BC es igual a aquélla del MAC con una limitación de potencia suma. Utilizando este resultado, se derivan algoritmos de asignación óptima de recursos basados en teoría de optimización convexa. / Multiple-input-multiple-output (MIMO) channels are extensively proposed as a means to overcome the random channel impairments of frequency-flat wireless communications. Based upon placing multiple antennas at both the transmitter and receiver sides of the communication, their virtues are twofold. On the one hand, they allow the transmitter: i) to concentrate the transmitted power onto a desired eigen-direction, or ii) tocode across antennas to overcome unknown channel fading. On the other hand, they permit the receiver to sample the signal on the space domain. This operation, followed by the coherent combination of samples, increases the signal-to-noise ratio at the input of the detector. In fine, MIMO processing is able to provide large capacity (and reliability) gains within rich-scattered scenarios.Nevertheless, equipping wireless handsets with multiple antennas is not always possible or worthwhile. Mainly, due to size and cost constraints, respectively. For these cases, the most appropriate manner to exploit multi-antenna processing is by means of relaying. This consists of a set of wireless relay nodes assisting the communication between a set of single-antenna sources and a set of single-antenna destinations. With the aid of relays, indeed, MIMO channels can be mimicked in a distributed way. However, the exact channel capacity of single-antenna communications with relays (and how this scheme performs with respect to the equivalent MIMO channel) is a long-standing open problem. To it we have devoted this thesis.In particular, the present dissertation aims at studying the capacity of Gaussian channels when assisted by multiple, parallel, relays. Two relays are said to be parallel if there is no direct link between them, while both have direct link from the source and towards the destination. We focus on three well-known channels: the point-to-point channel, the multi-access channel and the broadcast channel, and study their performance improvement with relays. All over the dissertation, the following assumptions are taken: i) full-duplex operation at the relays, ii) transmit and receive channel state information available at all network nodes, and iii) time-invariant, memory-less fading.Firstly, we analyze the multiple-parallel relay channel, where a single source communicates to a single destination in the presence of N parallel relays. The capacity of the channel is lower bounded by means of the achievable rates with different relaying protocols, i.e. decode-and-forward, partial decode-and-forward, compress-and-forward and linear relaying. Likewise, a capacity upper bound is provided for comparison, derived using the max-flow-min-cut Theorem. Finally, for number of relays growing to infinity, the scaling laws of all achievable rates are presented, as well as the one of the upper bound.Next, the dissertation focusses on the multi-access channel (MAC) with multiple-parallel relays. The channel consists of multiple users simultaneously communicating to a single destination in the presence of N parallel relay nodes. We bound the capacity region of the channel using, again, the max-flow-min-cut Theorem and find achievable rate regions by means of decode-and-forward, linear relaying and compress-and-forward. In addition, we analyze the asymptotic performance of the obtained achievable sum-rates, given the number of users growing without bound. Such a study allows us to grasp the impact of multi-user diversity on access networks with relays.Finally, the dissertation considers the broadcast channel (BC) with multiple parallel relays. This consists of a single source communicating to multiple receivers in the presence of N parallel relays. For the channel, we derive achievable rate regions considering: i) dirty paper encoding at the source, and ii) decode-and-forward, linear relaying and compress-and-forward, respectively, at the relays. Moreover, for linear relaying, we prove that MAC-BC duality holds. That is, the achievable rate region of the BC is equal to that of the MAC with a sum-power constraint. Using this result, the computation of the channel's weighted sum-rate with linear relaying is notably simplified. Likewise, convex resource allocation algorithms can be derived.

No description available.

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

Dans cette thèse, les réseaux coopératifs sont étudiés sous cette hypothèse que la source est incertain par rapport le canal en opération. Dans le premier chapitre, des stratégies coopératives sont développées pour les canaux à relais simultanés (SRC) lesquelles se composent d'un ensemble de deux canaux à relais parmi lesquels le canal en opération est choisi. Cela est équivalent au canal de diffusion à relais (BRC). Les bornes sur la région de capacité de BRC général sont dérivées. Les résultats de capacité sont obtenus pour les cas particuliers du canal à relais simultané semi-dégradé et dégradé Gaussien. Dans le deuxième chapitre, le canal à relais composite est considéré où le canal est tiré aléatoirement d'un ensemble de la distribution conditionnelle. Le débit est fixé en dépit du canal actuel et la probabilité d'erreur (EP) asymptotique est caractérisée. Une nouvelle stratégie de codage sélectif (SCS) est introduit permettant aux relais de choisir -selon leur mesurage du canal – la meilleur schéma de codage entre Décoder-et-Transmettre (DF) et Comprimer-et-Transmettre (CF). Les théorèmes de codage de réseau bruit généralisées sont démontrés pour le cas de réseau unicast général où les relais utilisent soit DF soit CF. Dans le troisième chapitre, le spectre asymptotique de EP est introduit en tant que nouvelle mesure de performance pour réseaux composites. Il est démontré que chaque code avec le débit hors de la borne cut-set, abouti à EP égal à un et le spectre asymptotique de EP coïncide avec la probabilité d'outage pour les réseaux satisfaisant la converse forte. / In this thesis, cooperative networks are studied under the assumption that the source is uncertain about the channel in operation. In the first chapter, cooperative strategies are developed for simultaneous relay channels (SRC) which consist of a set of two single relay channels out of which the channel in operation is chosen. This is equivalent to the broadcast relay channel (BRC). Bounds on the capacity region of the general BRC with two helper relays are derived. Capacity results are obtained for specific cases of semi-degraded and degraded Gaussian simultaneous relay channels. In the second chapter, the composite relay channel is considered where the channel is randomly drawn from a set of conditional distributions according to a given distribution. The transmission rate is fixed regardless of the current channel and the asymptotic error probability (EP) is characterized. A novel selective coding strategy (SCS) is introduced which enables relays to select –based on their channel measurement– the best coding scheme between Compress-and-Forward (CF) and Decode-and-Forward (DF). Generalized Noisy Network Coding theorems are shown for the case of unicast general networks where the relays use either DF or CF scheme. In the third chapter, the asymptotic behavior of EP is studied for composite multiterminal networks. The asymptotic spectrum of EP is introduced as a novel performance measure for composite networks. It is shown that every code with rate outside cut-set bound, yields EP equal to one and for the networks satisfying strong converse condition, the asymptotic spectrum of EP coincides with the outage probability.