Página 1 dos resultados de 15 itens digitais encontrados em 0.042 segundos

Graph Laplacian for spectral clustering and seeded image segmentation; Estudo do Laplaciano do grafo para o problema de clusterização espectral e segmentação interativa de imagens

Casaca, Wallace Correa de Oliveira
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 05/12/2014 EN
Relevância na Pesquisa
116.4%
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...

Propriedades espectrais de um grafo

Fritscher, Eliseu
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Dissertação Formato: application/pdf
POR
Relevância na Pesquisa
45.83%
Associadas a um grafo G, temos a matriz de adjacência A(G) e a matriz laplaciana L(G). Este trabalho descreve algumas propriedades dessas matrizes e de seus autovalores em relação a características estruturais do grafo. Veremos que, em geral, somente o espectro de G, isto é, conjunto de autovalores de A(G), não é capaz de revelar todas as informações a respeito do grafo. Apresentaremos também uma nova cota superior para a soma dos k maiores autovalores laplacianos de uma árvore com n vértices, para k {1, . . . , ng}. Esse limite nos permitirá demonstrar que, dentre todas as árvores de n vértices, a árvore com energia laplaciana máxima é a estrela Sn, o que foi conjecturado por Radenkovi¢ e Gutman [18].; Associated with a graph G, we have the adjacency matrix A(G) and the Laplacian matrix L(G). This work relates properties of these matrices and their eigenvalues to structural characteristics of the graph. We will see that, in general, the spectrum of G, namely the set of eigenvalues of A(G), does not reveal all the information about the graph. We will also present a new upper bound on the sum of the k largest Laplacian eigenvalues of a tree with n vertices, where k {1, . . . , ng}. This result is used to establish that the n-vertex star Sn has the highest Laplacian energy over all n-vertex trees...

Teoria Espectral de Grafos

Borsato, Luísa Bürgel
Fonte: Universidade Federal do Rio Grande do Sul Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Conferência ou Objeto de Conferência Formato: application/pdf
POR
Relevância na Pesquisa
45.8%

Receptores iterativos para canais de acesso múltiplo ruidosos com N frequências e T usuários; Iterative receivers for an N frequency T users multiple acess channel with noise

Manish Sharma
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 23/09/2010 PT
Relevância na Pesquisa
45.84%
O objetivo deste trabalho é analisar o desempenho da recepção e detecção conjunta e iterativa para canais de acesso múltiplo. A análise se concentrou em torno de um canal ruidoso com N frequências compartilhado por T usuários. Encontramos valores para a capacidade do canal para detecção conjunta e individual. Embora a eficiência espectral do sistema seja relativamente baixa, a combinação deste fator com uma grande faixa de frequências permite altas taxas de transmissão com baixa relação sinal ruído. O receptor foi modelado como um grafo de fatores e foi analisado através de curvas EXIT, que também são utilizadas para otimizar os códigos corretores de erro dos usuários. Propomos alguns sistemas baseados nesta técnica e simulamos a sua probabilidade de erro de bit. Os resultados indicam que é possível transmitir informação com taxas próximas da capacidade do canal. Tanto o grafo do receptor como as análises subsequentes podem ser aplicadas para outros canais de acesso múltiplo, especialmente para sistemas com N símbolos de transmissão ortogonais.; The aim of this work is to analyze the performance of iterative joint reception and detection for multi-user channels. The analysis is centered around an N-frequency MFSK noisy channel shared by T users. Channel capacity values are obtained for joint and single user detection. Although the system’s spectral efficiency is low...

Corte normalizado em grafos : um algoritmo aglomerativo para segmentação de imagens de colonias de bactérias= Normalized cut on graphs: an aglomerative algorithm for bacterial colonies image segmentation; Normalized cut on graphs : an aglomerative algorithm for bacterial colonies image segmentation

André Luís da Costa
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 22/02/2013 PT
Relevância na Pesquisa
76.31%
O problema de segmentação de colônias de bactérias em placas de Petri possui algumas características bem distintas daquelas encontradas, por exemplo, em problemas de segmentação de imagens naturais. A principal característica é o alto número de colônias que podem ser encontradas em uma placa. Desta forma, é primordial que o algoritmo de segmentação seja capaz de realizar a segmentação da imagem em um grande número de regiões. Este cenário extremo é ideal para analisar limitações dos algoritmos de segmentação. De fato, neste trabalho foi verificado que o algoritmo de corte normalizado original, que se fundamenta na teoria espectral de grafos, é inadequado para aplicações que exigem que a segmentação seja realizada em um grande número de regiões. Contudo, a utilização do critério de corte normalizado para segmentar imagens de colônias de bactérias ainda é possível graças a um novo algoritmo que está sendo introduzido neste trabalho. O novo algoritmo fundamenta-se no agrupamento hierárquico dos nós do grafo, ao invés de utilizar conceito da teoria espectral. Experimentos mostram também que o biparticionamento de um grafo pelo novo algoritmo apresenta um valor de corte normalizado médio cerca de 40 vezes menor que o biparticionamento pelo algoritmo baseado na teoria espectral.; The problem of bacteria colonies segmentation in Petri dishes has some very different characteristics from those found...

Segmentação de imagens digitais combinando watershed e corte normalizado em grafos; Digital image segmentation combining watershed and normalized cut

Tiago Willian Pinto
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 26/02/2014 PT
Relevância na Pesquisa
76.02%
Em Visão Computacional, a importância da segmentação de imagens é comparável apenas à sua complexidade. Interpretar a semântica de uma imagem com exatidão envolve inúmeras variáveis e condições, o que deixa um vasto campo em aberto aos pesquisadores. O intuito deste trabalho é implementar um método de segmentação de imagens através da combinação de quatro técnicas de computação: A Transformação Watershed, o Watershed Hierárquico, o Contextual Spaces Algorithm e o Corte Normalizado. A Transformação Watershed é uma técnica de segmentação de imagens do campo da Morfologia Matemática baseada em crescimento de regiões e uma forma eficiente de implementá-la é através da Transformada Imagem-Floresta. Esta técnica produz uma super-segmentação da imagem, o que dificulta a interpretação visual do resultado. Uma das formas de simplificar e reduzir essa quantidade de regiões é através da construção de um espaço de escalas chamado Watershed Hierárquico, que agrupa regiões através de um limiar que representa uma característica do relevo. O Contextual Spaces Algorithm é uma técnica de reclassificação utilizada no campo de Busca de Imagens Baseado em contexto, e explora a similaridade entre os diferentes objetos de uma coleção através da análise do contexto entre elas. O Corte Normalizado é uma técnica que explora a análise do grau de dissimilaridade entre regiões e tem suas bases na teoria espectral dos grafos. O Watershed Hierárquico é uma abordagem multiescala de análise das regiões do watershed...

Resultados espectrais relacionados com a estrutura dos grafos

Andelic, Milica
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Tese de Doutorado
POR
Relevância na Pesquisa
66.21%
Nesta tese são estabelecidas novas propriedades espectrais de grafos com estruturas específicas, como sejam os grafos separados em cliques e independentes e grafos duplamente separados em independentes, ou ainda grafos com conjuntos (κ,τ)-regulares. Alguns invariantes dos grafos separados em cliques e independentes são estudados, tendo como objectivo limitar o maior valor próprio do espectro Laplaciano sem sinal. A técnica do valor próprio é aplicada para obter alguns majorantes e minorantes do índice do espectro Laplaciano sem sinal dos grafos separados em cliques e independentes bem como sobre o índice dos grafos duplamente separados em independentes. São fornecidos alguns resultados computacionais de modo a obter uma melhor percepção da qualidade desses mesmos extremos. Estudamos igualmente os grafos com um conjunto (κ,τ)-regular que induz uma estrela complementar para um valor próprio não-principal $. Além disso, é mostrado que $=κ-τ. Usando uma abordagem baseada nos grafos estrela complementares construímos, em alguns casos, os respectivos grafos maximais. Uma caracterização dos grafos separados em cliques e independentes que envolve o índice e as entradas do vector principal é apresentada tal como um majorante do número da estabilidade dum grafo conexo.; In this thesis new spectral properties of graphs with a specific structure (as split graphs...

Majorantes para a ordem de subgrafos induzidos k-regulares

Pinheiro, Sofia Alexandra Marques Jorge
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Tese de Doutorado
POR
Relevância na Pesquisa
66.16%
Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.; Many optimization problems on graphs are reduced to the determination of a subset of vertices of maximum cardinality inducing a k-regular subgraph. Since the determination of the order of a k-regular induced subgraph of highest order is in general a NP-hard problem...

Energia dos grafos

Collao Morales, Macarena Alessandra
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Dissertação de Mestrado
POR
Relevância na Pesquisa
66.25%
Uma das aplicações mais importantes da Teoria Espetral dos Grafos na área da Química está relacionada com a correspondência muito estreita existente entre a energia _ electron de uma molécula e os valores próprios do grafo que a representa. Esta correspondência por si só é motivação suficiente para o estudo da energia dos grafos. Nesta dissertação, para além de se introduzirem os conceitos e terminologia básicos da Teoria dos Grafos necessários para o estudo da energia (que se define como sendo a soma dos valores absolutos dos valores próprios de um grafo), determinam-se as expressões para a energia de algumas classes de grafos. Adicionalmente, apresentam-se vários majorantes e minorantes para energia dos grafos e, por último estudam-se os grafos hiperenergéticos e hipoenergéticos.; One of the most important applications of Spectral Graph Theory in Chemistry is related with the thin correspondence between the _ electron energy of a molecule and the eigenvalues of the graph which represents the molecule. This correspondence is a sufficient motivation for the study of graph energy. In this work, besides the introduction of concepts and the basic terminology of Graph Theory needed for the study of the energy (which is defined as the sum of the absolute values of the eigenvalues of a graph)...

Recuperação de imagens: similaridade parcial baseada em espectro de grafo e cor

Santos, Dalí Freire Dias dos
Fonte: Universidade Federal de Uberlândia Publicador: Universidade Federal de Uberlândia
Tipo: Dissertação
POR
Relevância na Pesquisa
86.02%
Tradicionalmente, descritores de forma, ou descritores baseados em cor e textura, são utilizados para descrever o conteúdo visual das imagens. Embora essas abordagens apresentem bons resultados, elas não são capazes de diferenciar adequadamente imagens que contêm objetos com as mesmas cores, mas com organização espacial diferente ou não suportam a pesquisa parcial de imagens. Neste trabalho focamos em um caso particular da pesquisa parcial de imagens, que é encontrar objetos em imagens que contenham vários objetos, não deixando de lado a pesquisa total (encontrar imagens similares à original). Dado que a cor é uma das propriedades visuais mais discriminativas, propomos um novo descritor baseado somente em cor capaz de encontrar imagens de objetos que estão contidos em outras imagens. Embora tenha apresentado melhores resultados quando comparado a trabalhos correlatos, esse novo descritor de cor não é capaz de discriminar objetos topologicamente diferentes mas que possuam as mesmas cores. Com o intuito de resolver esse problema, também propomos uma nova abordagem para a recuperação parcial de imagens que combina características topológicas e de cor em um único descritor. Esse novo descritor primeiramente realiza um processo de simplificação da imagem original...

Alianzas en grafos

Sigarreta Almira, José María
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Tese de Doutorado Formato: application/pdf
SPA
Relevância na Pesquisa
76.1%
En este trabajo estudiamos propiedades matemáticas de las k-alianzas en grafos y prestamos especial interés a la relación que existe entre el número de k-alianza (defensiva, ofensiva y dual) y otros parámetros conocidos como, por ejemplo, el orden, la medida, el cuello, el diámetro, el número de independencia, el número de dominación, la conectividad algebraica y el radio espectral. En algunos casos obtenemos el valor exacto del número de k-alianza y, en general, obtenemos cotas tensas no triviales para dicho parámetro. En el caso del grafo línea, se obtienen resultados sobre el número de alianza (defensiva y ofensiva) en función de parámetros conocidos del grafo original. A lo largo de toda la memoria particularizamos al caso de grafos planares y de grafos cúbicos. Estudiamos, además, la relación entre alianzas defensivas y ofensivas, así como las principales propiedades de los conjuntos libres de k-alianzas y de los cubrimientos de k-alianzas. Otra de las aportaciones de esta memoria es el inicio del estudio de las k-alianzas conexas y de las k-alianzas independientes, as´ı como el estudio de la relación entre los conjuntos k-dominantes totales y las k-alianzas (defensivas, ofensivas y duales). Esta memoria está estructurada en tres capítulos. Los dos primeros...

Análisis de imágenes faciales basado en propiedades espectrales de grafos

Pérez Orr, Julio Daniel
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: info:eu-repo/semantics/bachelorThesis; info:eu-repo/semantics/masterThesis Formato: application/pdf
SPA
Relevância na Pesquisa
86.17%
La proliferación de diferentes fuentes de información de texto, imágenes y video en formato digital hace interesante la investigación de tecnologías de procesado de datos que puedan aplicarse independientemente del tipo de información permitiendo, eventualmente, un procesado integrado de múltiples fuentes de una manera que cupiera denominar semántica; por su nivel de abstracción y su potencial acercamiento a la forma en que el ser humano maneja la información. Este proyecto fin de carrera hace un análisis preliminar del empleo del análisis espectral de grafos definidos a partir de imágenes con el propósito anterior. Los resultados de esta investigación muestran que los espectros de los grafos definidos son mayormente degenerados, imposibilitando su uso para la categorización de imágenes, y que es necesaria una reorientación en la definición de los mismos.

Um estudo comparativo de segmentação de imagens por aplicações do corte normalizado em grafos; A comparative study of image segmentation by application of normalized cut on graphs

Anselmo Castelo Branco Ferreira
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 17/01/2011 PT
Relevância na Pesquisa
86.12%
O particionamento de grafos tem sido amplamente utilizado como meio de segmentação de imagens. Uma das formas de particionar grafos é por meio de uma técnica conhecida como Corte Normalizado, que analisa os autovetores da matriz laplaciana de um grafo e utiliza alguns deles para o corte. Essa dissertação propõe o uso de Corte Normalizado em grafos originados das modelagens por Quadtree e Árvore dos Componentes a fim de realizar segmentação de imagens. Experimentos de segmentação de imagens por Corte Normalizado nestas modelagens são realizados e um benchmark específico compara e classifica os resultados obtidos por outras técnicas propostas na literatura específica. Os resultados obtidos são promissores e nos permitem concluir que o uso de outras modelagens de imagens por grafos no Corte Normalizado pode gerar melhores segmentações. Uma das modelagens pode inclusive trazer outro benefício que é gerar um grafo representativo da imagem com um número menor de nós do que representações mais tradicionais; The graph partitioning has been widely used as a mean of image segmentation. One way to partition graphs is through a technique known as Normalized Cut, which analyzes the graph's Laplacian matrix eigenvectors and uses some of them for the cut. This work proposes the use of Normalized Cut in graphs generated by structures based on Quadtree and Component Tree to perform image segmentation. Experiments of image segmentation by Normalized Cut in these models are made and a specific benchmark compares and ranks the results obtained by other techniques proposed in the literature. The results are promising and allow us to conclude that the use of other image graph models in the Normalized Cut can generate better segmentations. One of the structures can also bring another benefit that is generating an image representative graph with fewer graph nodes than the traditional representations

A soma dos maiores autovalores da matriz laplaciana sem sinal em famílias de grafos; The sum of the largest eigenvalues of singless Laplacian matrix on graphs families

Bruno Dias Amaro
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 05/12/2014 PT
Relevância na Pesquisa
116.39%
A Teoria Espectral de Grafos é um ramo da Matemática Discreta que se preocupa com a relação entre as propriedades algébricas do espectro de certas matrizes associadas a grafos, como a matriz de adjacência, laplaciana ou laplaciana sem sinal e a topologia dos mesmos. Os autovalores e autovetores das matrizes associadas a um grafo são os invariantes que formam o autoespaço de grafos. Em Teoria Espectral de Grafos a conjectura proposta por Brouwer e Haemers, que associa a soma dos k maiores autovalores da matriz Laplaciana de um grafo G com seu número de arestas mais um fator combinatório (que depende do valor k adotado) é uma das questões interessantes e que está em aberto na literatura. Essa mostra diversos trabalhos que tentam provar tal conjectura. Em 2013, Ashraf et al. estenderam essa conjectura para a matriz laplaciana sem sinal e provaram que ela é válida para a soma dos 2 maiores autovalores e que também é válida para todo k, caso o grafo seja regular. Nosso trabalho aborda a versão dessa conjectura para a matriz laplaciana sem sinal. Conseguimos obter uma família de grafos que satisfaz a conjectura para a soma dos 3 maiores autovalores da matriz laplaciana sem sinal e a família de grafos split completo mais uma aresta satisfaz a conjectura para todos os autovalores. Ainda...

Introdução à teoria espectral de grafos com aplicações

Fonte: SBMAC Publicador: SBMAC
Tipo: Livro Formato: pdf
Publicado em //2012 PT
Relevância na Pesquisa
45.8%
Não disponível.