Image segmentation is an essential tool to enhance the ability of computer systems to efficiently perform elementary cognitive tasks such as detection, recognition and tracking. In this thesis we concentrate on the investigation of two fundamental topics in the context of image segmentation: spectral clustering and seeded image segmentation. We introduce two new algorithms for those topics that, in summary, rely on Laplacian-based operators, spectral graph theory, and minimization of energy functionals. The effectiveness of both segmentation algorithms is verified by visually evaluating the resulting partitions against state-of-the-art methods as well as through a variety of quantitative measures typically employed as benchmark by the image segmentation community. Our spectral-based segmentation algorithm combines image decomposition, similarity metrics, and spectral graph theory into a concise and powerful framework. An image decomposition is performed to split the input image into texture and cartoon components. Then, an affinity graph is generated and weights are assigned to the edges of the graph according to a gradient-based inner-product function. From the eigenstructure of the affinity graph, the image is partitioned through the spectral cut of the underlying graph. Moreover, the image partitioning can be improved by changing the graph weights by sketching interactively. Visual and numerical evaluation were conducted against representative spectral-based segmentation techniques using boundary and partition quality measures in the well-known BSDS dataset. Unlike most existing seed-based methods that rely on complex mathematical formulations that typically do not guarantee unique solution for the segmentation problem while still being prone to be trapped in local minima, our segmentation approach is mathematically simple to formulate, easy-to-implement, and it guarantees to produce a unique solution. Moreover, the formulation holds an anisotropic behavior, that is, pixels sharing similar attributes are preserved closer to each other while big discontinuities are naturally imposed on the boundary between image regions, thus ensuring better fitting on object boundaries. We show that the proposed approach significantly outperforms competing techniques both quantitatively as well as qualitatively, using the classical GrabCut dataset from Microsoft as a benchmark. While most of this research concentrates on the particular problem of segmenting an image, we also develop two new techniques to address the problem of image inpainting and photo colorization. Both methods couple the developed segmentation tools with other computer vision approaches in order to operate properly. / Segmentar uma image é visto nos dias de hoje como uma prerrogativa para melhorar a capacidade de sistemas de computador para realizar tarefas complexas de natureza cognitiva tais como detecção de objetos, reconhecimento de padrões e monitoramento de alvos. Esta pesquisa de doutorado visa estudar dois temas de fundamental importância no contexto de segmentação de imagens: clusterização espectral e segmentação interativa de imagens. Foram propostos dois novos algoritmos de segmentação dentro das linhas supracitadas, os quais se baseiam em operadores do Laplaciano, teoria espectral de grafos e na minimização de funcionais de energia. A eficácia de ambos os algoritmos pode ser constatada através de avaliações visuais das segmentações originadas, como também através de medidas quantitativas computadas com base nos resultados obtidos por técnicas do estado-da-arte em segmentação de imagens. Nosso primeiro algoritmo de segmentação, o qual ´e baseado na teoria espectral de grafos, combina técnicas de decomposição de imagens e medidas de similaridade em grafos em uma única e robusta ferramenta computacional. Primeiramente, um método de decomposição de imagens é aplicado para dividir a imagem alvo em duas componentes: textura e cartoon. Em seguida, um grafo de afinidade é gerado e pesos são atribuídos às suas arestas de acordo com uma função escalar proveniente de um operador de produto interno. Com base no grafo de afinidade, a imagem é então subdividida por meio do processo de corte espectral. Além disso, o resultado da segmentação pode ser refinado de forma interativa, mudando-se, desta forma, os pesos do grafo base. Experimentos visuais e numéricos foram conduzidos tomando-se por base métodos representativos do estado-da-arte e a clássica base de dados BSDS a fim de averiguar a eficiência da metodologia proposta. Ao contrário de grande parte dos métodos existentes de segmentação interativa, os quais são modelados por formulações matemáticas complexas que normalmente não garantem solução única para o problema de segmentação, nossa segunda metodologia aqui proposta é matematicamente simples de ser interpretada, fácil de implementar e ainda garante unicidade de solução. Além disso, o método proposto possui um comportamento anisotrópico, ou seja, pixels semelhantes são preservados mais próximos uns dos outros enquanto descontinuidades bruscas são impostas entre regiões da imagem onde as bordas são mais salientes. Como no caso anterior, foram realizadas diversas avaliações qualitativas e quantitativas envolvendo nossa técnica e métodos do estado-da-arte, tomando-se como referência a base de dados GrabCut da Microsoft. Enquanto a maior parte desta pesquisa de doutorado concentra-se no problema específico de segmentar imagens, como conteúdo complementar de pesquisa foram propostas duas novas técnicas para tratar o problema de retoque digital e colorização de imagens.

Os efeitos deletérios da perda e fragmentação de habitat são considerados a maior ameaça à manutenção da biodiversidade do planeta. Uma das maneiras de evitar a perda de espécies em paisagens fragmentadas é a restauração ecológica, que propicia tanto o aumento da quantidade quanto a melhoria da qualidade do habitat remanescente. Além de influenciar a persistência de espécies, as condições da paisagem são reconhecidas como importantes para o sucesso das ações de restauração. Entretanto, as diretrizes para incorporação das características da paisagem no planejamento da restauração são ainda ambíguas, não facilitando o processo de tomada de decisão. O presente trabalho teve como objetivo contribuir para o avanço do uso de análises espacialmente explícitas da estrutura da paisagem para o planejamento de ações de restauração. Para isso, foram elaboradas propostas metodológicas embasadas no atual conhecimento da ecologia de paisagens e foram realizadas simulações para comparar os potenciais benefícios para a biodiversidade resultantes de diferentes estratégias para seleção de áreas para restauração. A primeira proposta, apresentada no capítulo 2, utiliza análises de paisagens em múltiplas escalas, baseadas na teoria dos grafos, para estimar a resiliência das paisagens, entendida neste trabalho como a capacidade das paisagens de reverterem extinções locais por processos de migração. Em seguida, as paisagens com condições ideais para restauração são classificadas segundo sua importância como corredores biológicos e gargalos de conectividade. Essa proposta metodológica é aplicada no caso da Mata Atlântica (capítulo 3), a fim de estabelecer diferentes níveis de prioridade para restauração no conjunto deste bioma. No quarto capítulo, é apresentada uma segunda proposta metodológica, também baseada em análises de conectividade com o uso da teoria dos grafos, mas desta vez voltada para a identificação de áreas prioritárias para restauração em escala local. Essa proposta permite ainda a comparação de prioridades entre áreas situadas em paisagens com diferentes condições de cobertura e conectividade de habitat. Por fim, no quinto capítulo, foi realizado um conjunto de simulações de restauração para comparar os efeitos das características da paisagem (e.g. a cobertura e configuração florestal), das espécies (e.g. a capacidade de dispersão) e da estratégia de restauração (e.g. o tamanho das áreas restauradas e a ordem temporal da restauração) no aumento da disponibilidade de habitat em três paisagens reais da Mata Atlântica. Os resultados desta tese permitiram estabelecer prioridades de restauração tanto em escala regional quanto em escala local, reduzindo as áreas a serem visitadas em campo e possibilitando a otimização dos esforços de restauração. Também foi possível concluir que a adoção de estratégias espaciais para a seleção de áreas para restauração deve ser feita considerando tanto as características das espécies quanto as características das paisagens e a forma de implementação da restauração. Na ausência de informações detalhadas sobre a capacidade de dispersão das espécies, abordagens baseadas em múltiplas capacidades de dispersão são recomendadas. O embasamento teórico da ecologia de paisagens e as ferramentas atuais de tratamento e integração de dados espacializados permitem a definição das melhores estratégias de restauração a partir de simulações em computador, reduzindo substancialmente os custos da restauração e aumentando a sua eficácia para a conservação das espécies em paisagens fragmentadas / The deleterious effects of habitat loss and fragmentation are considered the main threats to biodiversity. To avoid species loss due to these deleterious effects, there is an urgent need to conduct restoration actions to increase the quantity and quality of the remaining habitat. Besides influencing species persistence, the landscape structure also influences the results of restoration actions. However, guidelines to adopt a landscape approach during restoration planning are not always consistent, nor easy to apply. The objective of this study was to contribute to advances in the use of spatially explicit landscape analysis during restoration planning. To achieve this goal we developed methodological frameworks based on landscape ecology theory to set priority areas for restoration. We also adopted a simulation approach to analyze the potential benefits of different restoration strategies for biodiversity conservation. The methodological proposal presented in chapter 2 consists in multi-scale landscape analyses, based on graph theory, to estimate landscape resilience. We considered landscape resilience as the capacity to revert local species extinctions through recolonization processes. Then, those landscapes considered ideal targets to restoration actions were classified according to their importance as corridors or bottlenecks for biological flow. In chapter 3, the methodological proposal presented in chapter 2 was applied to the Atlantic Forest Biome to set restoration priorities. Chapter 4 consists in a methodological proposal, also based on graph theory, to set restoration priorities in local scale. This methodological proposal also allows the comparison of local restoration priority between landscapes with different amount and configuration of habitat cover. Finally, in the fith chapter we adopted a simulation approach to analyze the improvement of habitat availability, in three Atlantic Forest landscapes, due to different restoration strategies considering: (i) different species dispersal capabilities, (ii) initial habitat amount in the landscape, (iii) the dynamics of landscapes during restoration implementation, i.e., the changes in habitat availability as new areas were restored, and (iv) size of restored areas. The results of this study allowed us to establish local and regional restoration priorities, thus reducing field visits and optimizing restoration efforts. It was also possible to conclude that spatial strategies to set restoration priorities should be conceived based on species dispersal capacities, landscape structure and also considering the strategies to implement restoration actions. If data on species dispersal characteristics is not available, a multi species approach to set restoration priorities is also recommended. The theoretical background of landscape ecology and the available tools to manage spatial data allow identifying the best restoration strategies, reducing the costs and optimizing the benefits to conserve biodiversity in fragmented landscapes

Le thème central à cette thèse est l'étude des propriétés des classes de graphes définies par sous-structures interdites et leurs applications.La première direction que nous suivons a trait aux beaux ordres. À l'aide de théorèmes de décomposition dans les classes de graphes interdisant une sous-structure, nous identifions celles qui sont bellement-ordonnées. Les ordres et sous-structures considérés sont ceux associés aux notions de contraction et mineur induit. Ensuite, toujours en considérant des classes de graphes définies par sous-structures interdites, nous obtenons des bornes sur des invariants comme le degré, la largeur arborescente, la tree-cut width et un nouvel invariant généralisant la maille.La troisième direction est l'étude des relations entre les invariants combinatoires liés aux problèmes de packing et de couverture de graphes. Dans cette direction, nous établissons de nouvelles relations entre ces invariants pour certaines classes de graphes. Nous présentons également des applications algorithmiques de ces résultats. / The central theme of this thesis is the study of the properties of the classes of graphs defined by forbidden substructures and their applications.The first direction that we follow concerns well-quasi-orders. Using decomposition theorems on graph classes forbidding one substructure, we identify those that are well-quasi-ordered. The orders and substructures that we consider are those related to the notions of contraction and induced minor.Then, still considering classes of graphs defined by forbidden substructures, we obtain bounds on invariants such as degree, treewidth, tree-cut width, and a new invariant generalizing the girth.The third direction is the study of the links between the combinatorial invariants related to problems of packing and covering of graphs. In this direction, we establish new connections between these invariants for some classes of graphs. We also present algorithmic applications of the results.

Made available in DSpace on 2015-03-04T18:57:40Z (GMT). No. of bitstreams: 1 Dissertacao_Klaus.pdf: 1117417 bytes, checksum: fa3282de1497f164dc8fc979216ed0e1 (MD5) Previous issue date: 2012-03-05 / Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior / The last decade or so has witnessed an ever-increasing growth in the study of very large complex networks related to different areas, such as biology, sociology, and the Internet. In this broad context, the concept of centrality offers a measure of the relative importance of nodes within a given complex network and is thus crucially important to network analysis. There are many different definitions of network centrality, which rank the relative importance of nodes using different criteria, depending on the targeted analysis. Among these, the traditional closeness centrality ranks the nodes by how close each node is to all other nodes in the network. In other words, the most central nodes according to a ranking based on closeness centrality are those best positioned for efficient diffusion processes, such as information or goods distribution as well as disease or rumor spreading, and so on. Nevertheless, computing closeness centrality in large complex networks is costly because it is necessary to determine the distance between all pairs of nodes in the network, thus requiring full knowledge of the network's topology. In centrality-based network analysis, the position of each node in the centrality ranking is typically more important than the particular centrality value associated to each node. Here, we present a fully distributed method capable of yielding different kinds of centrality, among them one which node ranking correlates strongly with the closeness centrality ranking, but being much cheaper than the traditional algorithm and not requiring full knowledge of the network's topology. Overall, our method is a simple yet efficient alternative for distributively determining the closeness centrality ranking, enabling a centrality-based analysis of large scale-free complex networks. / Os últimos anos tem mostrado um crescimento contínuo no estudo de redes complexas de grande porte relacionadas com diversas áreas de conhecimento, tais como Biologia, Sociologia, Economia, Internet, entre outras. Nesse contexto, o conceito de centralidade oferece uma medida da importância relativa dos nós que compõem uma rede complexa, sendo portanto de fundamental importância para a análise e estudo destas redes. Existem várias definições diferentes para centralidade em redes segundo a aplicação que pretendem, usando critérios distintos para ordenar a importância dos nós. Entre essas diferentes definições de centralidade, Closeness Centrality é uma das mais tradicionais e afere a importância de cada nó pela sua proximidade com todos os demais nós da rede. Dessa maneira, essa forma de centralidade avalia os nós melhor posicionados para realizar processos de difusão de forma eficiente na rede, sendo portanto de grande valia para análise de redes complexas com aplicações em diversas áreas. Entretanto, o cálculo deste tipo de centralidade apresenta um alto custo computacional, uma vez que é necessário que se calcule a distância entre todos os pares de nós da rede. Isso faz ainda que seja necessário conhecer completamente a topologia da rede para que seja possível calcular as distâncias entre os nós. Em virtude disso, o uso de Closeness Centrality se torna impraticável para redes de grande porte, comumente encontradas em diversas áreas do conhecimento. No entanto, em termos práticos, a ordem dos nós em função de sua centralidade é mais relevante do que os valores de centralidade em si. Assim, este trabalho apresenta um método distribuído que pode ser utilizado para calcular vários tipos de centralidades, entre elas uma cuja ordenação dos nós tem um alto grau de correlação com a ordenação obtida pelo uso de Closeness Centrality. O método proposto funciona de maneira totalmente distribuída, baseando-se em conhecimento local não necessitando do conhecimento completo da topologia da rede, e é computacionalmente menos custoso que o método tradicional. Estas características fazem com que o método proposto seja aplicável a redes complexas scale-free de grande porte, possibilitando uma aproximação eficiente da ordenação de Closeness Centrality a estas redes, como analisado nos resultados da dissertação.

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas. / A rectangular representation of a plane graph G is a representation of G, where each vertex is drawn as a rectangle, such as two rectangles have to share some boundary if and only if exist an edge in G between the corresponding vertices. Also, the representation of G must form a rectangle and does not contain any holes, in other words, every point inside the formed rectangle must correspond to some vertex of G. A rectangular drawing of a plane graph H is a drawing of H, where all edges are drawn either in vertical or in horizontal. Also, every internal face is a rectangle and the edges which are incident in the external face define a rectangle. In this dissertation, we present the main studies in the literature for problems associated with the rectangular representation. We also present results for problems associated with rectangular drawing. Finally, we present the algorithm we developed to determine the coordinates of the vertices of a rectangular drawing when the orientation of the edges have been determined.

Esta pesquisa lidou com a unificação de grafos aplicada ao problema das redes haplotípicas. A partir da baixa confiabilidade encontrada nas redes geradas pelos algoritmos tradicionais, foi necessário introduzir uma nova proposição para melhorar o resultado obtido. Para esta avaliar o resultado obtido pelo novo algoritmo, desenvolveu-se um arcabouço teórico-formal possibilitando a generalização de soluções relativas a redes haplotípicas através de aplicação de funções parametrizáveis, facilmente representadas através de linguagens funcionais no estilo LISP. Para aplicação em problemas reais, desenvolveu-se estrutura de simulação e testes que constrói cadeias genéticas de maneira aleatória ou ainda parametrizável. Os testes gerados permitiram observar a melhoria esperada no algoritmo, especialmente para os casos de baixa mutação. O arcabouço de simulação e testes mostrou-se extremamente propício e de fácil utilização, o que o torna, em si mesmo, uma ferramenta a ser disponibilizada para a comunidade acadêmica da área de Biologia. / This research dealt with the unification of graphs applied to the problem of haplotype networks. From the low reliability found in networks generated by the traditional algorithms, it was necessary to introduce a new proposition to improve the outcome. For proper evaluation of the results obtained by the new algorithm, a formal-theoretical framework for generalization of haplotype networks related solutions, making use of parameterized functions easily represented through LISP-like functional languages. Seeking for real case application of the theory developed, a structure of simulation and testing were developed to build genetic code strings randomly or even parameterized. The generated tests have allowed to observe the expected improvement in the algorithm, especially for cases of low mutation. The framework for simulation and testing was extremely useful and easy to use, making itself a product to be distributed to the academic Biology community.

Pang Suet-Yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 85-87). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.1.1 --- Survival Analysis --- p.2 / Chapter 1.1.2 --- Tree、-structured Statistical Method --- p.2 / Chapter 1.1.3 --- Mortality Study --- p.3 / Chapter 1.2 --- Motivation --- p.3 / Chapter 1.3 --- Background Information --- p.4 / Chapter 1.4 --- Data Content --- p.7 / Chapter 1.5 --- Thesis Outline --- p.8 / Chapter 2 --- Imputation and File Splitting --- p.10 / Chapter 2.1 --- Imputation of Missing Values --- p.10 / Chapter 2.1.1 --- Purpose of Imputation --- p.10 / Chapter 2.1.2 --- Procedure of Hot Deck Imputation --- p.11 / Chapter 2.1.3 --- List of Variables for Imputation --- p.12 / Chapter 2.2 --- File Splitting --- p.14 / Chapter 2.2.1 --- Splitting by Gender --- p.14 / Chapter 2.3 --- Splitting for Validation Check --- p.1G / Chapter 3 --- Cox Hazard Model --- p.17 / Chapter 3.1 --- Basic Idea --- p.17 / Chapter 3.1.1 --- Survival Analysis --- p.17 / Chapter 3.1.2 --- Survivor Function --- p.18 / Chapter 3.1.3 --- Hazard Function --- p.18 / Chapter 3.2 --- The Cox Proportional Hazards Model --- p.19 / Chapter 3.2.1 --- Kaplan-Meier Estimate and Log-Rank Test --- p.20 / Chapter 3.2.2 --- Hazard Ratio --- p.23 / Chapter 3.2.3 --- Partial Likelihood --- p.24 / Chapter 3.3 --- Extension of the Cox Proportional Hazards Model for Time-dependent Variables --- p.25 / Chapter 3.3.1 --- Modification of the Cox's Model --- p.25 / Chapter 3.4 --- Results of Model Fitting --- p.26 / Chapter 3.4.1 --- Extract the Significant Covariates from the Models --- p.31 / Chapter 3.5 --- Model Interpretation --- p.32 / Chapter 4 --- CART --- p.37 / Chapter 4.1 --- CART Procedure --- p.38 / Chapter 4.2 --- Selection of the Splits --- p.39 / Chapter 4.2.1 --- Goodness of Split --- p.39 / Chapter 4.2.2 --- Type of Variables --- p.40 / Chapter 4.2.3 --- Estimation --- p.40 / Chapter 4.3 --- Pruning the Tree --- p.41 / Chapter 4.3.1 --- Misclassification Cost --- p.42 / Chapter 4.3.2 --- Class Assignment Rule --- p.44 / Chapter 4.3.3 --- Minimal Cost Complexity Pruning --- p.44 / Chapter 4.4 --- Cross Validation --- p.47 / Chapter 4.4.1 --- V-fold Cross-validation --- p.47 / Chapter 4.4.2 --- Selecting the right sized tree --- p.49 / Chapter 4.5 --- Missing Value --- p.49 / Chapter 4.6 --- Results of CART program --- p.51 / Chapter 4.7 --- Model Interpretation --- p.53 / Chapter 5 --- Model Prediction --- p.58 / Chapter 5.1 --- Application to Test Sample --- p.58 / Chapter 5.1.1 --- Fitting test sample to Cox's Model --- p.59 / Chapter 5.1.2 --- Fitting test sample to CART model --- p.61 / Chapter 5.2 --- Comparison of Model Prediction --- p.62 / Chapter 5.2.1 --- Misclassification Rate --- p.62 / Chapter 5.2.2 --- Misclassification Rate of Cox's model --- p.63 / Chapter 5.2.3 --- Misclassification Rate of CART model --- p.64 / Chapter 5.2.4 --- Prediction Result --- p.64 / Chapter 6 --- Conclusion --- p.67 / Chapter 6.1 --- Comparison of Results --- p.67 / Chapter 6.2 --- Comparison of the Two Statistical Techniques --- p.68 / Chapter 6.3 --- Limitation --- p.70 / Appendix A: Coding Description for the Health Factors --- p.72 / Appendix B: Log-rank Test --- p.75 / Appendix C: Longitudinal Plot of Time Dependent Variables --- p.76 / Appendix D: Hypothesis Testing of Suspected Covariates --- p.78 / Appendix E: Terminal node report for both gender --- p.81 / Appendix F: Calculation of Critical Values --- p.83 / Appendix G: Distribution of Missing Value in Learning sample and Test Sample --- p.84 / Bibliography --- p.85

A fundamental understanding of the kinetics and mechanisms of the catalytic reaction steps involved in the process of converting a fuel into hydrogen rich stream suitable for a fuel cell, as well as the electro-catalytic reactions within a fuel cell, is not only conceptually appealing, but could provide a sound basis for the design and development of efficient fuel processor/fuel cell systems. With the quantum chemical calculations on kinetics of elementary catalytic reaction steps becoming rather commonplace, and with increasing information now available in terms of electronic structures, vibration spectra, and kinetic data (activation energy and pre-exponential factors), the stage is set for development of a comprehensive approach. Toward this end, we have developed a framework that can utilize this basic information to develop a comprehensive understanding of catalytic and electrocatalytic reaction networks. The approach is based on the development of Reaction Route (RR) Graphs, which not only represent the reaction pathways pictorially, but are quantitative networks consistent with the Kirchhoff's laws of flow networks, allowing a detailed quantitative analysis by exploiting the analogy with electrical circuits. The result is an unambiguous portrayal of the reaction scheme that lays bare the dominant pathways. Further, the rate-limiting steps are identified rationally with ease, based on comparison of step resistances, as are the dominant pathways via flux analysis. In fact, explicit steady-state overall reaction (OR) rate expression can also be derived in an Ohm's law form, i.e. OR rate = OR motive force/OR resistance of an equivalent electric circuit, which derives directly from the RR graph of its mechanism. This approach is utilized for a detailed analysis of the catalytic and electro-catalytic reaction systems involved in reformer/fuel cell systems. The catalytic reaction systems considered include methanol decomposition, water gas shift, ammonia decomposition, and methane steam reforming, which have been studied mechanistically and kinetically. A detailed analysis of the electro-catalytic reactions in connection to the anode and cathode of fuel cells, i.e. hydrogen electrode reaction and the oxygen reduction reaction, has also been accomplished. These reaction systems have not so far been investigated at this level of detail. The basic underlying principles of the RR graphs and the topological analysis for these reaction systems are discussed.

The standard grid bracing problem has a nice solution via the brace graph. If we introduce a window by removing an interior vertex of the grid, this solution comletely breaks down. We examine a 6 x 10 unit grid with a 2 x 2 window and provide an optimal solution via the Rigidity Matrix.

Les objectifs de cette thèse étaient de caractériser les corrélats neuronaux fonctionnels et structurels de l'abolition de la conscience observés pendant le coma et d'identifier les signatures neuronales précoces de la récupération neurologique à partir de cet état. Pour atteindre ce but, nous avons étudié des patients cérébrolésés, recrutés au stade aigu du coma, à l'aide de l'IRM fonctionnelle au repos et IRM structurale. Nos résultats indiquent une réorganisation topologique globale du cerveau des patients, reflétée par une dédifférenciation et une réduction de la résilience des réseaux fonctionnels au repos d'ordre élevé. Ces anomalies sont accompagnées d'une perte de connexions fronto-pariétales à longue distance. Au niveau régional, nous avons observé un schéma complexe de diminution et d'augmentation de la densité de connexion fonctionnelle entre le cortex postéromédial et le cortex préfrontal médial : régions précédemment décrites pour avoir un rôle critique dans la conscience. De manière intéressante, ces modifications de densité de connexion étaient significativement liées à la récupération des patients trois mois après le coma. Enfin, l'analyse multimodale a permis de démontrer une association significative entre la connectivité fonctionnelle et l'intégrité structurelle cérébrales antéro-postérieure, fournissant des informations importantes sur le lien structure/fonction au décours de ces troubles acquis de la conscience. / The aim of the present thesis was to characterize the functional and structural neural correlates of acute consciousness abolition induced by severe brain injury and identify early neural signatures of long-term neurological recovery. To do so, we studied brain-injured patients, recruited in the acute stage of coma, using resting-state functional and structural MRI. Our findings indicated a global topological brain reorganization in coma patients, reflected in dedifferentiated and less resilient high-order resting-state functional networks, paralleled with a loss of long-range fronto-parietal connections. On a regional level, we found a complex pattern of voxel-wise decrease and increase in functional connection density between the posteromedial cortex and the medial prefrontal cortex, regions previously described to have a critical role in conscious processing. These connection density patterns seemed to permit outcome prediction in patients, assessed three months post-coma. Furthermore, the multi-modal MRI analysis demonstrated a significant association between antero-posterior functional connectivity and structural integrity, providing further insights into the pathological underpinning of conscious processing.