Página 1 dos resultados de 109 itens digitais encontrados em 0.039 segundos

Caracterização e modelagem de redes biológicas geográficas; Characterization and modelling of biological networks

Viana, Matheus Palhares
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 23/03/2011 PT
Relevância na Pesquisa
45.67%
Nesta tese apresentamos uma metodologia de mapeamento capaz de gerar representações em termos de grafos para sistemas biológicos de conectividade complexa. Tais sistemas são inicialmente armazenados na forma de imagens digitais e em seguida submetidos a um pré-processamento com objetivo de padronizar as imagens. As imagens pré-processadas são então utilizadas para gerar modelos tridimensionais dos sistemas de interesse. Um algoritmo de propagação de rótulos é utilizado para extrair os esqueletos dos modelos volumétricos e estes esqueletos são por fim, representados por um grafo, composto por vértices e arestas. Os vértices e arestas desse grafo armazenam propriedades do sistema original, como posição, comprimento e diâmetro, bem como as características topológicas de tais sistemas. Finalmente, os grafos resultantes são estudados através da teoria das redes complexas, dentro de um contexto específico para cada sistema. Nossos procedimentos foram aplicados com sucesso a diferentes sistemas biológicos, como artérias caríotidas, árvores arteriais, estruturas mitocondriais e poros em amostras de solo.; In the present work, we developed a mapping methodology able to build a graph representation for biological branched systems. Initially...

Corte em grafos e segmentação de imagens utilizando um algoritmo aglomerativo de agrupamento hierárquico; Graph cut and image segmentation using an hierarquical agglomerative clustering algorithm

Elaine Ayumi Chiba
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 21/02/2014 PT
Relevância na Pesquisa
55.67%
Representar os elementos de uma imagem em forma de grafos torna a estrutura organizada permitindo formular problemas de forma flexível e ser computacionalmente mais eficiente. Existem muitas técnicas da teoria de grafos sendo utilizadas em processamento digital de imagens. Em particular, o particionamento em grafos ou corte em grafos tem sido estudada por diversos autores como uma ferramenta de segmentação de imagens. Particionamento de um grafo refere-se à sua divisão em vários subgrafos tais que cada um deles representa um objeto de interesse na imagem. Neste trabalho, propomos um algoritmo de agrupamento hierárquico aglomerativo dos nós do grafo com base nas métricas de corte e corte médio. As segmentações foram avaliadas usando o benchmark da Berkeley BSDS500 que compara e classifica as segmentações em relação à outras técnicas existentes na literatura. Os resultados obtidos são promissores e nos permite concluir de que a combinação das métricas de corte e corte médio possibilitou melhores segmentações.; Representing the elements of an image in graphs makes the structure organized allowing to formulate problems in a flexible manner and can be more computationally efficient. There are many techniques of graph theory that are used in digital image processing. In particular...

Robust automatic segmentation of corneal layer boundaries in SDOCT images using graph theory and dynamic programming

LaRocca, Francesco; Chiu, Stephanie J.; McNabb, Ryan P.; Kuo, Anthony N.; Izatt, Joseph A.; Farsiu, Sina
Fonte: Optical Society of America Publicador: Optical Society of America
Tipo: Artigo de Revista Científica
Publicado em 12/05/2011 EN
Relevância na Pesquisa
55.57%
Segmentation of anatomical structures in corneal images is crucial for the diagnosis and study of anterior segment diseases. However, manual segmentation is a time-consuming and subjective process. This paper presents an automatic approach for segmenting corneal layer boundaries in Spectral Domain Optical Coherence Tomography images using graph theory and dynamic programming. Our approach is robust to the low-SNR and different artifact types that can appear in clinical corneal images. We show that our method segments three corneal layer boundaries in normal adult eyes more accurately compared to an expert grader than a second grader—even in the presence of significant imaging outliers.

Automatic segmentation of closed-contour features in ophthalmic images using graph theory and dynamic programming

Chiu, Stephanie J.; Toth, Cynthia A.; Bowes Rickman, Catherine; Izatt, Joseph A.; Farsiu, Sina
Fonte: Optical Society of America Publicador: Optical Society of America
Tipo: Artigo de Revista Científica
Publicado em 26/04/2012 EN
Relevância na Pesquisa
55.57%
This paper presents a generalized framework for segmenting closed-contour anatomical and pathological features using graph theory and dynamic programming (GTDP). More specifically, the GTDP method previously developed for quantifying retinal and corneal layer thicknesses is extended to segment objects such as cells and cysts. The presented technique relies on a transform that maps closed-contour features in the Cartesian domain into lines in the quasi-polar domain. The features of interest are then segmented as layers via GTDP. Application of this method to segment closed-contour features in several ophthalmic image types is shown. Quantitative validation experiments for retinal pigmented epithelium cell segmentation in confocal fluorescence microscopy images attests to the accuracy of the presented technique.

Disruption of the Cerebral White Matter Network Is Related to Slowing of Information Processing Speed in Patients With Type 2 Diabetes

Reijmer, Yael D.; Leemans, Alexander; Brundel, Manon; Kappelle, L. Jaap; Biessels, Geert Jan;
Fonte: American Diabetes Association Publicador: American Diabetes Association
Tipo: Artigo de Revista Científica
EN
Relevância na Pesquisa
35.63%
Patients with type 2 diabetes often show slowing of information processing. Disruptions in the brain white matter network, possibly secondary to vascular damage, may underlie these cognitive disturbances. The current study reconstructed the white matter network of 55 nondemented individuals with type 2 diabetes (mean age, 71 ± 4 years) and 50 age-, sex-, and education-matched controls using diffusion magnetic resonance imaging–based fiber tractography. Graph theoretical analysis was then applied to quantify the efficiency of these networks. Patients with type 2 diabetes showed alterations in local and global network properties compared with controls (P < 0.05). These structural network abnormalities were related to slowing of information processing speed in patients. This relation was partly independent of cerebrovascular lesion load. This study shows that the approach of characterizing the brain as a network using diffusion magnetic resonance imaging and graph theory can provide new insights into how abnormalities in the white matter affect cognitive function in patients with diabetes.

Identification of the Epileptogenic Zone from Stereo-EEG Signals: A Connectivity-Graph Theory Approach

Panzica, Ferruccio; Varotto, Giulia; Rotondi, Fabio; Spreafico, Roberto; Franceschetti, Silvana
Fonte: Frontiers Media S.A. Publicador: Frontiers Media S.A.
Tipo: Artigo de Revista Científica
Publicado em 06/11/2013 EN
Relevância na Pesquisa
45.57%
In the context of focal drug-resistant epilepsies, the surgical resection of the epileptogenic zone (EZ), the cortical region responsible for the onset, early seizures organization, and propagation, may be the only therapeutic option for reducing or suppressing seizures. The rather high rate of failure in epilepsy surgery of extra-temporal epilepsies highlights that the precise identification of the EZ, mandatory objective to achieve seizure freedom, is still an unsolved problem that requires more sophisticated methods of investigation. Despite the wide range of non-invasive investigations, intracranial stereo-EEG (SEEG) recordings still represent, in many patients, the gold standard for the EZ identification. In this contest, the EZ localization is still based on visual analysis of SEEG, inevitably affected by the drawback of subjectivity and strongly time-consuming. Over the last years, considerable efforts have been made to develop advanced signal analysis techniques able to improve the identification of the EZ. Particular attention has been paid to those methods aimed at quantifying and characterizing the interactions and causal relationships between neuronal populations, since is nowadays well assumed that epileptic phenomena are associated with abnormal changes in brain synchronization mechanisms...

A Parallel Graph Algorithm for Finding Connected Components

Hirschberg, D.S.; Hirschberg, D.S.
Fonte: Universidade Rice Publicador: Universidade Rice
Tipo: Relatório
ENG
Relevância na Pesquisa
55.57%
Tech Report; A parallel program is presented that determines the connected components of an undirected graph in time 0(log2n) using n2 processors. It is assumed that the processors have access to common memory. Simultaneous access to the same location is permitted for fetch, but not store, instructions.

The automatic design of batch processing systems

Dwyer, Barry
Fonte: Universidade de Adelaide Publicador: Universidade de Adelaide
Tipo: Tese de Doutorado Formato: 1067141 bytes; 27125 bytes; application/pdf; application/pdf
Publicado em //1999 EN
Relevância na Pesquisa
35.65%
Batch processing is a means of improving the efficiency of transaction processing systems. Despite the maturity of this field, there is no rigorous theory that can assist in the design of batch systems. This thesis proposes such a theory, and shows that it is practical to use it to automate system design. This has important consequences; the main impediment to the wider use of batch systems is the high cost of their development and intenance. The theory is developed twice: informally, in a way that can be used by a systems analyst, and formally, as a result of which a computer program has been developed to prove the feasibility of automated design. Two important concepts are identified, which can aid in the decomposition of any system: 'separability', and 'independence'. Separability is the property that allows processes to be joined together by pipelines or similar topologies. Independence is the property that allows elements of a large set to be accessed and updated independently of one another. Traditional batch processing technology exploits independence when it uses sequential access in preference to random access. It is shown how the same property allows parallel access, resulting in speed gains limited only by the number of processors. This is a useful development that should assist in the design of very high throughput transaction processing systems. Systems are specified procedurally by describing an ideal system...

Energy Minimization of Discrete Protein Titration State Models Using Graph Theory

Hogan, Emilie; Monson, Kyle; Baker, Nathan A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/07/2015
Relevância na Pesquisa
45.65%
There are several applications in computational biophysics which require the optimization of discrete interacting states; e.g., amino acid titration states, ligand oxidation states, or discrete rotamer angles. Such optimization can be very time-consuming as it scales exponentially in the number of sites to be optimized. In this paper, we describe a new polynomial-time algorithm for optimization of discrete states in macromolecular systems. This algorithm was adapted from image processing and uses techniques from discrete mathematics and graph theory to restate the optimization problem in terms of "maximum flow-minimum cut" graph analysis. The interaction energy graph, a graph in which vertices (amino acids) and edges (interactions) are weighted with their respective energies, is transformed into a flow network in which the value of the minimum cut in the network equals the minimum free energy of the protein, and the cut itself encodes the state that achieves the minimum free energy. Because of its deterministic nature and polynomial-time performance, this algorithm has the potential to allow for the ionization state of larger proteins to be discovered.

A Spectral Graph Uncertainty Principle

Agaskar, Ameya; Lu, Yue M.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.73%
The spectral theory of graphs provides a bridge between classical signal processing and the nascent field of graph signal processing. In this paper, a spectral graph analogy to Heisenberg's celebrated uncertainty principle is developed. Just as the classical result provides a tradeoff between signal localization in time and frequency, this result provides a fundamental tradeoff between a signal's localization on a graph and in its spectral domain. Using the eigenvectors of the graph Laplacian as a surrogate Fourier basis, quantitative definitions of graph and spectral "spreads" are given, and a complete characterization of the feasibility region of these two quantities is developed. In particular, the lower boundary of the region, referred to as the uncertainty curve, is shown to be achieved by eigenvectors associated with the smallest eigenvalues of an affine family of matrices. The convexity of the uncertainty curve allows it to be found to within $\varepsilon$ by a fast approximation algorithm requiring $O(\varepsilon^{-1/2})$ typically sparse eigenvalue evaluations. Closed-form expressions for the uncertainty curves for some special classes of graphs are derived, and an accurate analytical approximation for the expected uncertainty curve of Erd\H{o}s-R\'enyi random graphs is developed. These theoretical results are validated by numerical experiments...

Sampling of graph signals with successive local aggregations

Marques, Antonio G.; Segarra, Santiago; Leus, Geert; Ribeiro, Alejandro
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.66%
A new scheme to sample signals defined in the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Most of the works that have looked at this problem have focused on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, which is critical to guarantee recovery when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover...

Sparse Signal Processing with Frame Theory

Mixon, Dustin G.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/04/2012
Relevância na Pesquisa
45.65%
Many emerging applications involve sparse signals, and their processing is a subject of active research. We desire a large class of sensing matrices which allow the user to discern important properties of the measured sparse signal. Of particular interest are matrices with the restricted isometry property (RIP). RIP matrices are known to enable efficient and stable reconstruction of sufficiently sparse signals, but the deterministic construction of such matrices has proven very difficult. In this thesis, we discuss this matrix design problem in the context of a growing field of study known as frame theory. In the first two chapters, we build large families of equiangular tight frames and full spark frames, and we discuss their relationship to RIP matrices as well as their utility in other aspects of sparse signal processing. In Chapter 3, we pave the road to deterministic RIP matrices, evaluating various techniques to demonstrate RIP, and making interesting connections with graph theory and number theory. We conclude in Chapter 4 with a coherence-based alternative to RIP, which provides near-optimal probabilistic guarantees for various aspects of sparse signal processing while at the same time admitting a whole host of deterministic constructions.; Comment: PhD thesis

On some sufficient conditions for distributed Quality-of-Service support in wireless networks

Ganesan, Ashwin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/06/2009
Relevância na Pesquisa
35.64%
Given a wireless network where some pairs of communication links interfere with each other, we study sufficient conditions for determining whether a given set of minimum bandwidth Quality of Service (QoS) requirements can be satisfied. We are especially interested in algorithms which have low communication overhead and low processing complexity. The interference in the network is modeled using a conflict graph whose vertices are the communication links in the network. Two links are adjacent in this graph if and only if they interfere with each other due to being in the same vicinity and hence cannot be simultaneously active. The problem of scheduling the transmission of the various links is then essentially a fractional, weighted vertex coloring problem, for which upper bounds on the fractional chromatic number are sought using only localized information. We present some distributed algorithms for this problem, and discuss their worst-case performance. These algorithms are seen to be within a bounded factor away from optimal for some well known classes of networks and interference models.; Comment: Submitted to First Workshop on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks (GRAPH-HOC 09)

GSPBOX: A toolbox for signal processing on graphs

Perraudin, Nathanaël; Paratte, Johan; Shuman, David; Kalofolias, Vassilis; Vandergheynst, Pierre; Hammond, David K.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/08/2014
Relevância na Pesquisa
45.67%
In this document we introduce a Matlab toolbox called the Graph Signal Processing toolbox (GSPBox). This toolbox is based on spectral graph theory, more specifically graph filtering. It includes fast filtering routines using Chebychev polynomials as presented in [4]. This document is automatically generated from the source files and includes the complete documen- tation of the toolbox. However the most up-to-date documentation can be found on the official website http://lts2research.epfl.ch/gsp/doc.

Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies

Anis, Aamir; Gadde, Akshay; Ortega, Antonio
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 01/10/2015
Relevância na Pesquisa
35.67%
We study the problem of selecting the best sampling set for bandlimited reconstruction of signals on graphs. A frequency domain representation for graph signals can be defined using the eigenvectors and eigenvalues of variation operators that take into account the underlying graph connectivity. Smoothly varying signals defined on the nodes are of particular interest in various applications, and tend to be approximately bandlimited in the frequency basis. Sampling theory for graph signals deals with the problem of choosing the best subset of nodes for reconstructing a bandlimited signal from its samples. Most approaches to this problem require a computation of the frequency basis (i.e., the eigenvectors of the variation operator), followed by a search procedure using the basis elements. This can be impractical, in terms of storage and time complexity, for real datasets involving very large graphs. We circumvent this issue in our formulation by introducing quantities called graph spectral proxies, defined using the powers of the variation operator, in order to approximate the spectral content of graph signals. This allows us to formulate a direct sampling set selection approach that does not require the computation and storage of the basis elements. We show that our approach also provides stable reconstruction when the samples are noisy or when the original signal is only approximately bandlimited. Furthermore...

Discrete Signal Processing on Graphs: Sampling Theory

Chen, Siheng; Varma, Rohan; Sandryhaila, Aliaksei; Kovačević, Jelena
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.8%
We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for Erd\H{o}s-R\'enyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification on online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.; Comment: To appear in IEEE T-SP

Graph States, Pivot Minor, and Universality of (X,Z)-measurements

Mhalla, Mehdi; Perdrix, Simon
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 29/02/2012
Relevância na Pesquisa
35.64%
The graph state formalism offers strong connections between quantum information processing and graph theory. Exploring these connections, first we show that any graph is a pivot-minor of a planar graph, and even a pivot minor of a triangular grid. Then, we prove that the application of measurements in the (X,Z)-plane over graph states represented by triangular grids is a universal measurement-based model of quantum computation. These two results are in fact two sides of the same coin, the proof of which is a combination of graph theoretical and quantum information techniques.

Markov chain Monte Carlo on the GPU

Dumont, Michael
Fonte: Rochester Instituto de Tecnologia Publicador: Rochester Instituto de Tecnologia
Tipo: Tese de Doutorado
EN_US
Relevância na Pesquisa
45.52%
Markov chains are a useful tool in statistics that allow us to sample and model a large population of individuals. We can extend this idea to the challenge of sampling solutions to problems. Using Markov chain Monte Carlo (MCMC) techniques we can also attempt to approximate the number of solutions with a certain confidence based on the number of samples we use to compute our estimate. Even though this approximation works very well for getting accurate results for very large problems, it is still computationally intensive. Many of the current algorithms use parallel implementations to improve their performance. Modern day graphics processing units (GPU's) have been increasing in computational power very rapidly over the past few years. Due to their inherently parallel nature and increased flexibility for general purpose computation, they lend themselves very well to building a framework for general purpose Markov chain simulation and evaluation. In addition, the majority of mid- to high-range workstations have graphics cards capable of supporting modern day general purpose GPU (GPGPU) frameworks such as OpenCL, CUDA, or DirectCompute. This thesis presents work done to create a general purpose framework for Markov chain simulations and Markov chain Monte Carlo techniques on the GPU using the OpenCL toolkit. OpenCL is a GPGPU framework that is platform and hardware independent...

Algorithms for bounding Folkman numbers

Coles, Jonathan
Fonte: Rochester Instituto de Tecnologia Publicador: Rochester Instituto de Tecnologia
Tipo: Masters Project Formato: 418299 bytes; 119066 bytes; application/pdf; application/pdf
EN_US
Relevância na Pesquisa
35.69%
For an undirected, simple graph G, we write G -> (a_1,...,a_k)^v (G -> (a_1,...,a_k)^e) if for every vertex (edge) k-coloring, a monochromatic K_(a_i) is forced in some color i in {1,...,k}. The vertex (edge) Folkman number is defined as F_v(a_1,...,a_k;p) = min{|V(G)| : G -> (a_1,...,a_k;p)^v, K_p not in G} F_e(a_1,...,a_k;p) = min{|V(G)| : G -> (a_1,...,a_k;p)^e, K_p not in G} for p > max{a_1,...,a_k}. Folkman showed in 1970 that these numbers always exist for valid values of p. This thesis concerns the computation of a new result in Folkman number theory, namely that F_v(2,2,3;4)=14. Previously, the bounds stood at 10 <= F_v(2,2,3;4) <= 14, proven by Nenov in 2000. To achieve this new result, specialized algorithms were executed on the computers of the Computer Science network in a distributed processing effort. We discuss the mathematics and algorithms used in the computation. We also discuss ongoing research into the computation of the value of F_e(3,3;4). The current bounds stand at 16 <= F_e(3,3;4) <= 3e10^9. This number was once the subject of an Erd s prize---claimed by Spencer in 1988.

Finding the most vital edge for graph minimization problems on meshes and hypercubes

Liang, Weifa; Shen, Xiaojun; Hu, Qing
Fonte: ACT Press Publicador: ACT Press
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.57%
Let G(V, E, w) be an undirected, weighted, connected simple graph. Let P be a minimization problem in G. Edge e*∈E is called the most vital edge if its removal from G maximizes the value of P in G(V, E-{e*}, w). This paper considers the most vital edge