Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-17T11:47:27Z (GMT). No. of bitstreams: 1 Ferreira_AnselmoCasteloBranco_M.pdf: 7338510 bytes, checksum: 593cb683d0380e0c894f0147a4129c77 (MD5) Previous issue date: 2011 / Resumo: 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 / Abstract: 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 / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-24T15:15:13Z (GMT). No. of bitstreams: 1 Chiba_ElaineAyumi_M.pdf: 5856831 bytes, checksum: f9d4b4bea391d9b772f2c53ce2466420 (MD5) Previous issue date: 2014 / Resumo: 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 / Abstract: 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, the graph partitioning or graph cut has been studied by several authors as a tool for image segmentation. Partitioning a graph refers to its division into several subgraphs such that each of them represents a meaningful object of interest in the image. In this work we propose a algorithm based on hierarchical agglomerative clustering of the graph nodes driven by the cut and mean cut criteria. The segmentati- ons results were evaluated using the benchmark of Berkeley BSDS500 that compares and classifies the results in relation to other existing techniques in the literature. The results obtained are promising and allows us to conclude that the combination of the cut and mean cut criteria possible best segmentations / Mestrado / Tecnologia e Inovação / Mestra em Tecnologia

Orientadores: Marco Antonio Garcia de Carvalho, Paulo Sérgio Martins Pedro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-25T02:01:02Z (GMT). No. of bitstreams: 1 Pinto_TiagoWillian_M.pdf: 4501631 bytes, checksum: fd8dab16452e93b1ceec36bc90f085b9 (MD5) Previous issue date: 2014 / Resumo: 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, que possibilita a extração de métricas que podem servir de subsídio para aplicação do Corte Normalizado. A proposta deste projeto é combinar estas técnicas, implementando um método de segmentação que explore os benefícios alcançados por cada uma, variando entre diferentes métricas do Watershed Hierárquico com o Corte Normalizado e comparando os resultados obtidos / Abstract: In computer vision , the importance of image segmentation is comparable only by its complexity. Interpreting the semantics of an image accurately involves many variables and conditions, which leaves a vast field open to researchers. The purpose of this work is to implement a method of image segmentation by combining four computing techniques: The Watershed Transform, the Hierarchical Watershed, Contextual Spaces Algorithm and Normalized Cut. The Watershed Transform is a technique for image segmentation from the field of Mathematical Morphology based on region growing and an efficient way to implement it is through the Image Foresting Transform. This technique produces an over-segmentated image, which makes the visual interpretation of the result be very hard. One way to simplify and reduce the quantity of regions is by constructing a space of scales called Hierarchical Watershed, grouping regions through a threshold that represents a characteristic of the relief. The Contextual Spaces Algorithm is a reranking technique used in the field of Context Based Image Retrieval, and explores the similarity between different objects in a collection by analyzing the context between them. Normalized Cut is a technique that exploits the analysis of the degree of dissimilarity between regions and has its foundations in the spectral graph theory. The Hierarchical Watershed is a multiscale approach for analyzing regions of the watershed, which enables the extraction of metrics that can serve as a basis for applying the Normalized Cut. The purpose of this project is to combine these techniques, implementing a segmentation method that exploits the benefits achieved by each one, varying between different metrics of Hierarchical Watershed with Normalized Cut and comparing the results / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2017-09-04T16:56:52Z No. of bitstreams: 2 Dissertação - Lais Cândido Rodrigues da Silva Lopes - 2017.pdf: 3651786 bytes, checksum: 544801154cf6cd32456e6887eaa09b85 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-15T13:52:55Z (GMT) No. of bitstreams: 2 Dissertação - Lais Cândido Rodrigues da Silva Lopes - 2017.pdf: 3651786 bytes, checksum: 544801154cf6cd32456e6887eaa09b85 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-15T13:52:55Z (GMT). No. of bitstreams: 2 Dissertação - Lais Cândido Rodrigues da Silva Lopes - 2017.pdf: 3651786 bytes, checksum: 544801154cf6cd32456e6887eaa09b85 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-03 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / The capture of images by multiple positions allows to recover the three-dimensional information of the environment applying the knowledge about the geometry of the cameras and the correspondences between the points of the images. The correspondence of characteristics in images is the task of relating regions of different images to the same point of interest, being considered a problem of difficult solution, since it suffers with ambiguities, occlusions, variation of illumination, besides local distortions. For having so many challenges, this subject is one of the most investigated in the field of computer vision cite Scharstein2001. The present dissertation aims to generate dense disparity maps, using graph cutting, from search spaces constructed with matching metrics based on laws of the Gestalt theory. A hybrid approach was developed, consisting of a local algorithm to construct the image disparity space (EDI), and a global algorithm used to optimize the disparities. The results were maps of disparities close to the expected maps ( textit groundtruth). It was also perceived the best performance of the methodology proposed in relation to the separate methods that compose it. / A captura de imagens por múltiplas posições permite recuperar a informação tridimensional do ambiente aplicando o conhecimento sobre a geometria das câmeras e as correspondências entre os pontos das imagens. A correspondência de características em imagens é a tarefa de relacionar regiões de imagens diferentes a um mesmo ponto de interesse, sendo considerado um problema de difícil solução, uma vez que, sofre com ambiguidades, oclusões, variação de iluminação, além de distorções locais. Por contar com tantos desafios, este tema é um dos mais investigados na área de visão computacional [Scharstein e Szeliski 2002]. A presente dissertação tem por objetivo gerar mapas de disparidade densos, usando corte de grafos, a partir de espaços de busca construídos com métricas de correspondência baseadas em leis da teoria Gestalt. Foi desenvolvida uma abordagem híbrida, composta de um algoritmo local para construir o espaço de disparidades da imagem (EDI), e um algoritmo global utilizado para otimizar as disparidades. Os resultados foram mapas de disparidades próximos dos mapas esperados (ground-truth). Percebeu-se a melhor performance da metodologia proposta em relação aos métodos em separado que a compõe.

Orientador: Alexandre Xavier Falcão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-27T14:45:13Z (GMT). No. of bitstreams: 1 Moya_Nikolas_M.pdf: 5706960 bytes, checksum: 9304544bfe8a78039de8b62562531865 (MD5) Previous issue date: 2015 / Resumo: Segmentação de imagens médicas é crucial para extrair medidas de objetos 3D (estruturas anatômicas) que são úteis no diagnóstico e tratamento de doenças. Nestas aplicações, segmentação interativa é necessária quando métodos automáticos falham ou não são factíveis. Métodos por corte em grafo são considerados o estado da arte em segmentação interativa, mas diversas abordagens utilizam o algoritmo min-cut/max-flow, que é limitado à segmentação binária, sendo que segmentação de múltiplos objetos pode economizar tempo e esforço do usuário. Este trabalho revisita a transformada imagem floresta diferencial (DIFT, em inglês) -- uma abordagem por corte em grafo adequada para segmentação de múltiplos objetos -- resolvendo problemas relacionados a ela. O algoritmo da DIFT executa em tempo proporcional ao número de voxels nas regiões modificadas em cada execução da segmentação (sublinear). Tal característica é altamente desejável em segmentação interativa de imagens 3D para responder as ações do usuário em tempo real. O algoritmo da DIFT funciona da seguinte forma: o usuário desenha marcadores (traço com voxels de semente) rotulados dentro de cada objeto e o fundo, enquanto o computador interpreta a imagem como um grafo, cujos nós são os voxels e os arcos são definidos por pixels vizinhos, produzindo como resultado uma floresta de caminhos ótimos (partição na imagem) enraizada nos nós sementes do grafo. Nesta floresta, cada objeto é representado pela floresta de caminhos ótimos enraizado em suas sementes internas. Tais árvores são pintadas com a mesmo cor associada ao rótulo do marcador correspondente. Ao adicionar ou remover marcadores, é possível corrigir a segmentação até o mapa de rótulo de objeto representar o resultado desejado. Para garantir consistência na segmentação, métodos baseados em semente sempre devem manter a conectividade entre os voxels e suas sementes. Entretanto, isto não é mantido em algumas abordagens, como Random Walkers ou quando o mapa de rótulos é filtrado para suavizar a fronteira dos objetos. Esta conectividade é primordial para realizar correções sem recomeçar o processo depois de cada intervenção do usuário. Todavia, foi observado que a DIFT falha em manter consistência da segmentação em alguns casos. Consertamos este problema tanto no algoritmo da DIFT, quanto após a suavização dos objetos. Estes resultados comparam diversas estruturas anatômicas 3D de imagens de ressonância magnética e tomografia computadorizada / Abstract: Medical image segmentation is crucial to extract measures from 3D objects (body anatomical structures) that are useful for diagnosis and treatment of diseases. In such applications, interactive segmentation is necessary whenever automated methods fail or are not feasible. Graph-cut methods are considered the state of the art in interactive segmentation, but most approaches rely on the min-cut/max-flow algorithm, which is limited to binary segmentation while multi-object segmentation can considerably save user time and effort. This work revisits the differential image foresting transform (DIFT) ¿ a graph-cut approach suitable for multi-object segmentation in linear time ¿ and solves several problems related to it. Indeed, the DIFT algorithm can take time proportional to the number of voxels in the regions modified at each segmentation execution (sublinear time). Such a characteristic is highly desirable in 3D interactive segmentation to respond the user's actions as close as possible to real time. Segmentation using the DIFT works as follows: the user draws labeled markers (strokes of connected seed voxels) inside each object and background, while the computer interprets the image as a graph, whose nodes are the voxels and arcs are defined by neighboring voxels, and outputs an optimum-path forest (image partition) rooted at the seed nodes in the graph. In the forest, each object is represented by the optimum-path trees rooted at its internal seeds. Such trees are painted with same color associated to the label of the corresponding marker. By adding/removing markers, the user can correct segmentation until the forest (its object label map) represents the desired result. For the sake of consistency in segmentation, similar seed-based methods should always maintain the connectivity between voxels and seeds that have labeled them. However, this does not hold in some approaches, such as random walkers, or when the segmentation is filtered to smooth object boundaries. That connectivity is also paramount to make corrections without starting over the process at each user intervention. However, we observed that the DIFT algorithm fails in maintaining segmentation consistency in some cases. We have fixed this problem in the DIFT algorithm and when the obtained object boundaries are smoothed. These results are presented and evaluated on several 3D body anatomical structures from MR and CT images / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Vários métodos tradicionais de segmentação de imagens, como a transformada de watershed de marcado- res e métodos de conexidade fuzzy (Relative Fuzzy Connectedness- RFC, Iterative Relative Fuzzy Connected- ness - IRFC), podem ser implementados de modo eficiente utilizando o método em grafos da Transformada Imagem-Floresta (Image Foresting Transform - IFT). No entanto, a carência de termos de regularização de fronteira em sua formulação fazem com que a borda do objeto segmentado possa ser altamente irregular. Um modo de contornar isto é por meio do uso de restrições de forma do objeto, que favoreçam formas mais regulares, como na recente restrição de convexidade geodésica em estrela (Geodesic Star Convexity - GSC). Neste trabalho, apresentamos uma nova restrição de forma, chamada de Faixa de Restrição Geodésica (Geodesic Band Constraint - GBC), que pode ser incorporada eficientemente em uma sub-classe do fra- mework de corte em grafos generalizado (Generalized Graph Cut - GGC), que inclui métodos pela IFT. É apresentada uma prova da otimalidade do novo algoritmo em termos de um mínimo global de uma função de energia sujeita às novas restrições de borda. A faixa de restrição geodésica nos ajuda a regularizar a borda dos objetos, consequentemente melhorando a segmentação de objetos com formas mais regulares, mantendo o baixo custo computacional da IFT. A GBC pode também ser usada conjuntamente com um mapa de custos pré estabelecido, baseado em um modelo de forma, de modo a direcionar a segmentação a seguir uma dada forma desejada, com grau de liberdade de escala e demais deformações controladas por um parâmetro único. Essa nova restrição também pode ser combinada com a GSC e com as restrições de polaridade de borda sem custo adicional. O método é demonstrado em imagens naturais, sintéticas e médicas, sendo estas provenientes de tomografias computadorizadas e de ressonância magnética. / In this work, we present a novel boundary constraint, which we denote as the Geodesic Band Constraint (GBC), and we show how it can be efficiently incorporated into a subclass of the Generalized Graph Cut framework (GGC). We include a proof of the optimality of the new algorithm in terms of a global minimum of an energy function subject to the new boundary constraints. The Geodesic Band Constraint helps regularizing the boundary, and consequently, improves the segmentation of objects with more regular shape, while keeping the low computational costs of the Image Foresting Transform (IFT). It can also be combined with the Geodesic Star Convexity prior, and with polarity constraints, at no additional cost.

Vários métodos tradicionais de segmentação de imagens, como a transformada de watershed de marcado- res e métodos de conexidade fuzzy (Relative Fuzzy Connectedness- RFC, Iterative Relative Fuzzy Connected- ness - IRFC), podem ser implementados de modo eficiente utilizando o método em grafos da Transformada Imagem-Floresta (Image Foresting Transform - IFT). No entanto, a carência de termos de regularização de fronteira em sua formulação fazem com que a borda do objeto segmentado possa ser altamente irregular. Um modo de contornar isto é por meio do uso de restrições de forma do objeto, que favoreçam formas mais regulares, como na recente restrição de convexidade geodésica em estrela (Geodesic Star Convexity - GSC). Neste trabalho, apresentamos uma nova restrição de forma, chamada de Faixa de Restrição Geodésica (Geodesic Band Constraint - GBC), que pode ser incorporada eficientemente em uma sub-classe do fra- mework de corte em grafos generalizado (Generalized Graph Cut - GGC), que inclui métodos pela IFT. É apresentada uma prova da otimalidade do novo algoritmo em termos de um mínimo global de uma função de energia sujeita às novas restrições de borda. A faixa de restrição geodésica nos ajuda a regularizar a borda dos objetos, consequentemente melhorando a segmentação de objetos com formas mais regulares, mantendo o baixo custo computacional da IFT. A GBC pode também ser usada conjuntamente com um mapa de custos pré estabelecido, baseado em um modelo de forma, de modo a direcionar a segmentação a seguir uma dada forma desejada, com grau de liberdade de escala e demais deformações controladas por um parâmetro único. Essa nova restrição também pode ser combinada com a GSC e com as restrições de polaridade de borda sem custo adicional. O método é demonstrado em imagens naturais, sintéticas e médicas, sendo estas provenientes de tomografias computadorizadas e de ressonância magnética. / In this work, we present a novel boundary constraint, which we denote as the Geodesic Band Constraint (GBC), and we show how it can be efficiently incorporated into a subclass of the Generalized Graph Cut framework (GGC). We include a proof of the optimality of the new algorithm in terms of a global minimum of an energy function subject to the new boundary constraints. The Geodesic Band Constraint helps regularizing the boundary, and consequently, improves the segmentation of objects with more regular shape, while keeping the low computational costs of the Image Foresting Transform (IFT). It can also be combined with the Geodesic Star Convexity prior, and with polarity constraints, at no additional cost.