A segmentação de imagens e, em visão computacional, uma tarefa de grande importância, para a qual existem várias abordagem. A complexidade de tais abordagens está relacionada à natureza da imagem e também ao grau de precisão da segmentação, que e um conceito bastante subjetivo, normalmente associado a semelhança que apresenta a segmentaçã produzida pela visão humana. Na segmentação de imagens baseada em algoritmos de agrupamento em grafos, geralmente os pixels da imagem compôem os nós do grafo e as arestas representam a similaridade entre estes nós. Assim, a segmentação pode ser obtida por meio do agrupamento dos nós do grafo. É importante salientar, no entanto, que as técnicas de agrupamento em grafos surgiram no contexto de reconhecimento de padrões, cujo objetivo primario era o tratamento de dados diversos que não envolviam imagens. O uso de tais tecnicas para a segmentação de imagens e relativamente recente e revela alguns problemas desaadores. O primeiro deles é a deficiente escalabilidade de alguns métodos, o que impede o seu uso efetivo em imagens de altas dimensões. Outra questão é a falta de estudos que avaliam as medidas de similaridade na montagem do grafo e critérios que aferem a qualidade do agrupamento para a área específica de segmentação de imagens. Em outras palavras, faltam na literatura análises mais específicas que indiquem quais algoritmos de agrupamento em grafos são mais efetivos para a segmentação de imagens e que procurem associar (ou correlacionar) as várias medidas de similaridade e métricas de qualidade de agrupamento que produzam segmentações mais precisas. Neste trabalho é apresentada a avaliação de 6 algoritmos de agrupamento em grafos formulados em base a 3 categorias identificadas (agrupamento espectral, algoritmos de particionamento multinível e algoritmos para detectar comunidades) e aplicadas na segmentação automática de imagens de cenas naturais com grandes dimensões. Esta avaliação objetiva aferir, sobretudo, a qualidade da segmentação, a escalabilidade, o desempenho de 7 funções de similaridade formuladas, e também visa corroborar a existência da correlação entre a qualidade do agrupamento e a qualidade da segmentação. Para reduzir o esforço computacional e contribuir com a escalabilidade dos algoritmos formulados é utilizado um algoritmo de pré-processamento (SLIC) que agrupa váarios pixels da imagem em uma unica região (superpixels), o que contribui para reduzir o tamanho do grafo e, consequentemente, reduzindo o custo computacional do agrupamento. Os resultados demostram que os algoritmos formulados LP (Label Propagation) e FG (Fast Greedy) apresentam boa escalabilidade e boa qualidade de segmentação. Seis das sete funções de similaridade avaliadas apresentam um bom desempenho, independentemente do algoritmo de agrupamento empregado. É mostrado também que exites correlação entre a medida de qualidade de agrupamento conhecido como índice de silhueta e a qualidade de segmentação, ou seja, quanto maior o valor de silhueta, melhor a segmentação. A qualidade de segmentação foi avaliada quantitativamente, utilizando-se um conjunto de imagens segmentadas manualmente / Image segmentation is an important task within computer vision for which many approaches are available. The complexity of such approaches are intrinsically related with the nature of the image and also the desired accuracy aimed at. Image segmentation accuracy, however, is a subjective concept and is normally associated with how much it resembles segmentation produced by the human vision system. In graphbased clustering image segmentation algorithms, pixels are normally represented as nodes and edges convey the similarity between such nodes. Hence, segmentation may be attained by means of grouping node of a graph. It is important, though, to point out that graph-based clustering techniques rst appeared in the context of pattern recognition and its primary data source were not images. The usage of such techniques for image segmentation is a recent trend and poses some challenge issues. The first is the poor scalability that many methods exhibit, impairing its application in images of larger dimensions. Another issues is that lack of studies that assess the goodness of similarity measures employed in graph computation and also clustering quality criteria assessments for the specic area of image processing. In other words, there is no evidences in the literature on how effective graph-based clustering algorithms are for image segmentation and no studies that associate similarity functions and clustering quality metrics with image processing quality. This work presents an evaluation of six graph-based clustering algorithms according to three major categories found in the literature (spectral clustering, multi layer partitioning algorithms and community detectors) applied to automatic segmentation of image of larger dimensions. This evaluation takes into account segmentation quality, scalability, the performance of seven similarity functions and, nally, bring some insights on the correlation between clustering and segmentation quality. To reduce computational costs and enhance scalability of the methods we employ a pre processing algorithm (SLIC) which combines many pixels into one single region (superpixel). This contributes to reduce the graph size and, consequently, the cost of clustering. Results have shown that the LP (Label Propagation) and FG (Fast Greedy) algorithms exhibit good scalability and good segmentation. Six out of the seven similarity functions presented good performance, regardless the clustering algorithm. We also have shown that there is correlation between clustering quality and image segmentation quality, when the Silhouette measure is employed. That is, the higher the Silhouette values, the better the segmentation. Image segmentation quality has been quantitatively assessed by means of ground-truth data or user segmented images

A segmentação de imagens e, em visão computacional, uma tarefa de grande importância, para a qual existem várias abordagem. A complexidade de tais abordagens está relacionada à natureza da imagem e também ao grau de precisão da segmentação, que e um conceito bastante subjetivo, normalmente associado a semelhança que apresenta a segmentaçã produzida pela visão humana. Na segmentação de imagens baseada em algoritmos de agrupamento em grafos, geralmente os pixels da imagem compôem os nós do grafo e as arestas representam a similaridade entre estes nós. Assim, a segmentação pode ser obtida por meio do agrupamento dos nós do grafo. É importante salientar, no entanto, que as técnicas de agrupamento em grafos surgiram no contexto de reconhecimento de padrões, cujo objetivo primario era o tratamento de dados diversos que não envolviam imagens. O uso de tais tecnicas para a segmentação de imagens e relativamente recente e revela alguns problemas desaadores. O primeiro deles é a deficiente escalabilidade de alguns métodos, o que impede o seu uso efetivo em imagens de altas dimensões. Outra questão é a falta de estudos que avaliam as medidas de similaridade na montagem do grafo e critérios que aferem a qualidade do agrupamento para a área específica de segmentação de imagens. Em outras palavras, faltam na literatura análises mais específicas que indiquem quais algoritmos de agrupamento em grafos são mais efetivos para a segmentação de imagens e que procurem associar (ou correlacionar) as várias medidas de similaridade e métricas de qualidade de agrupamento que produzam segmentações mais precisas. Neste trabalho é apresentada a avaliação de 6 algoritmos de agrupamento em grafos formulados em base a 3 categorias identificadas (agrupamento espectral, algoritmos de particionamento multinível e algoritmos para detectar comunidades) e aplicadas na segmentação automática de imagens de cenas naturais com grandes dimensões. Esta avaliação objetiva aferir, sobretudo, a qualidade da segmentação, a escalabilidade, o desempenho de 7 funções de similaridade formuladas, e também visa corroborar a existência da correlação entre a qualidade do agrupamento e a qualidade da segmentação. Para reduzir o esforço computacional e contribuir com a escalabilidade dos algoritmos formulados é utilizado um algoritmo de pré-processamento (SLIC) que agrupa váarios pixels da imagem em uma unica região (superpixels), o que contribui para reduzir o tamanho do grafo e, consequentemente, reduzindo o custo computacional do agrupamento. Os resultados demostram que os algoritmos formulados LP (Label Propagation) e FG (Fast Greedy) apresentam boa escalabilidade e boa qualidade de segmentação. Seis das sete funções de similaridade avaliadas apresentam um bom desempenho, independentemente do algoritmo de agrupamento empregado. É mostrado também que exites correlação entre a medida de qualidade de agrupamento conhecido como índice de silhueta e a qualidade de segmentação, ou seja, quanto maior o valor de silhueta, melhor a segmentação. A qualidade de segmentação foi avaliada quantitativamente, utilizando-se um conjunto de imagens segmentadas manualmente / Image segmentation is an important task within computer vision for which many approaches are available. The complexity of such approaches are intrinsically related with the nature of the image and also the desired accuracy aimed at. Image segmentation accuracy, however, is a subjective concept and is normally associated with how much it resembles segmentation produced by the human vision system. In graphbased clustering image segmentation algorithms, pixels are normally represented as nodes and edges convey the similarity between such nodes. Hence, segmentation may be attained by means of grouping node of a graph. It is important, though, to point out that graph-based clustering techniques rst appeared in the context of pattern recognition and its primary data source were not images. The usage of such techniques for image segmentation is a recent trend and poses some challenge issues. The first is the poor scalability that many methods exhibit, impairing its application in images of larger dimensions. Another issues is that lack of studies that assess the goodness of similarity measures employed in graph computation and also clustering quality criteria assessments for the specic area of image processing. In other words, there is no evidences in the literature on how effective graph-based clustering algorithms are for image segmentation and no studies that associate similarity functions and clustering quality metrics with image processing quality. This work presents an evaluation of six graph-based clustering algorithms according to three major categories found in the literature (spectral clustering, multi layer partitioning algorithms and community detectors) applied to automatic segmentation of image of larger dimensions. This evaluation takes into account segmentation quality, scalability, the performance of seven similarity functions and, nally, bring some insights on the correlation between clustering and segmentation quality. To reduce computational costs and enhance scalability of the methods we employ a pre processing algorithm (SLIC) which combines many pixels into one single region (superpixel). This contributes to reduce the graph size and, consequently, the cost of clustering. Results have shown that the LP (Label Propagation) and FG (Fast Greedy) algorithms exhibit good scalability and good segmentation. Six out of the seven similarity functions presented good performance, regardless the clustering algorithm. We also have shown that there is correlation between clustering quality and image segmentation quality, when the Silhouette measure is employed. That is, the higher the Silhouette values, the better the segmentation. Image segmentation quality has been quantitatively assessed by means of ground-truth data or user segmented images

Cone Beam Computed Tomography (CBCT) is a medical imaging technique routinely employed for diagnosis and treatment of patients with cranio-maxillo-facial defects. CBCT 3D reconstruction and segmentation of bones such as mandible or maxilla are essential procedures in orthodontic treatments. However, CBCT images present characteristics that are not desirable for processing, including low contrast, inhomogeneity, noise, and artifacts. Besides, values assigned to voxels are relative Hounsfield Units (HU), unlike traditional Computed Tomography (CT). Such drawbacks render CBCT segmentation a difficult and time-consuming task, usually performed manually with tools designed for medical image processing. We introduce two interactive two-stage methods for 3D segmentation of CBCT data: i) we first reduce the CBCT image resolution by grouping similar voxels into super-voxels defining a graph representation; ii) next, seeds placed by users guide graph clustering algorithms, splitting the bones into mandible and skull. We have evaluated our segmentation methods intensively by comparing the results against ground truth data of the mandible and the skull, in various scenarios. Results show that our methods produce accurate segmentation and are robust to changes in parameter settings. We also compared our approach with a similar segmentation strategy and we showed that it produces more accurate segmentation of the mandible and skull. In addition, we have evaluated our proposal with CT data of patients with deformed or missing bones. We obtained more accurate segmentation in all cases. As for the efficiency of our implementation, a segmentation of a typical CBCT image of the human head takes about five minutes. Finally, we carried out a usability test with orthodontists. Results have shown that our proposal not only produces accurate segmentation, as it also delivers an effortless and intuitive user interaction. / Tomografia Computadorizada de Feixe Cônico (TCFC) é uma modalidade para obtenção de imagens médicas 3D do crânio usada para diagnóstico e tratamento de pacientes com defeitos crânio-maxilo-faciais. A segmentação tridimensional de ossos como a mandíbula e a maxila são procedimentos essências em tratamentos ortodônticos. No entanto, a TCFC apresenta características não desejáveis para processamento digital como, por exemplo, baixo contraste, inomogeneidade, ruído e artefatos. Além disso, os valores atribuídos aos voxels são unidades de Hounsfield (HU) relativas, diferentemente da Tomografia Computadorizada (TC) tradicional. Esses inconvenientes tornam a segmentação de TCFC uma tarefa difícil e demorada, a qual é normalmente realizada por meio de ferramentas desenvolvidas para processamento digital de imagens médicas. Esta tese introduz dois métodos interativos para a segmentação 3D de TCFC, os quais são divididos em duas etapas: i) redução da resolução da TCFC por meio da agrupamento de voxels em super-voxels, seguida da criação de um grafo no qual os vértices são super-voxels; ii) posicionamento de sementes pelo usuário e segmentação por algoritmos de agrupamento em grafos, o que permite separar os ossos rotulados. Os métodos foram intensamente avaliados por meio da comparação dos resultados com padrão ouro da mandíbula e do crânio, considerando diversos cenários. Os resultados mostraram que os métodos não apenas produzem segmentações precisas, como também são robustos a mudanças nos parâmetros. Foi ainda realizada uma comparação com um trabalho relacionado, gerando melhores resultados tanto na segmentação da mandíbula quanto a do crânio. Além disso, foram avaliadas TCs de pacientes com ossos faltantes e quebrados. A segmentação de uma TCFC é realizada em cerca de 5 minutos. Por fim, foram realizados testes com usuarios ortodontistas. Os resultados mostraram que nossa proposta não apenas produz segmentações precisas, como também é de fácil interação.

Cone Beam Computed Tomography (CBCT) is a medical imaging technique routinely employed for diagnosis and treatment of patients with cranio-maxillo-facial defects. CBCT 3D reconstruction and segmentation of bones such as mandible or maxilla are essential procedures in orthodontic treatments. However, CBCT images present characteristics that are not desirable for processing, including low contrast, inhomogeneity, noise, and artifacts. Besides, values assigned to voxels are relative Hounsfield Units (HU), unlike traditional Computed Tomography (CT). Such drawbacks render CBCT segmentation a difficult and time-consuming task, usually performed manually with tools designed for medical image processing. We introduce two interactive two-stage methods for 3D segmentation of CBCT data: i) we first reduce the CBCT image resolution by grouping similar voxels into super-voxels defining a graph representation; ii) next, seeds placed by users guide graph clustering algorithms, splitting the bones into mandible and skull. We have evaluated our segmentation methods intensively by comparing the results against ground truth data of the mandible and the skull, in various scenarios. Results show that our methods produce accurate segmentation and are robust to changes in parameter settings. We also compared our approach with a similar segmentation strategy and we showed that it produces more accurate segmentation of the mandible and skull. In addition, we have evaluated our proposal with CT data of patients with deformed or missing bones. We obtained more accurate segmentation in all cases. As for the efficiency of our implementation, a segmentation of a typical CBCT image of the human head takes about five minutes. Finally, we carried out a usability test with orthodontists. Results have shown that our proposal not only produces accurate segmentation, as it also delivers an effortless and intuitive user interaction. / Tomografia Computadorizada de Feixe Cônico (TCFC) é uma modalidade para obtenção de imagens médicas 3D do crânio usada para diagnóstico e tratamento de pacientes com defeitos crânio-maxilo-faciais. A segmentação tridimensional de ossos como a mandíbula e a maxila são procedimentos essências em tratamentos ortodônticos. No entanto, a TCFC apresenta características não desejáveis para processamento digital como, por exemplo, baixo contraste, inomogeneidade, ruído e artefatos. Além disso, os valores atribuídos aos voxels são unidades de Hounsfield (HU) relativas, diferentemente da Tomografia Computadorizada (TC) tradicional. Esses inconvenientes tornam a segmentação de TCFC uma tarefa difícil e demorada, a qual é normalmente realizada por meio de ferramentas desenvolvidas para processamento digital de imagens médicas. Esta tese introduz dois métodos interativos para a segmentação 3D de TCFC, os quais são divididos em duas etapas: i) redução da resolução da TCFC por meio da agrupamento de voxels em super-voxels, seguida da criação de um grafo no qual os vértices são super-voxels; ii) posicionamento de sementes pelo usuário e segmentação por algoritmos de agrupamento em grafos, o que permite separar os ossos rotulados. Os métodos foram intensamente avaliados por meio da comparação dos resultados com padrão ouro da mandíbula e do crânio, considerando diversos cenários. Os resultados mostraram que os métodos não apenas produzem segmentações precisas, como também são robustos a mudanças nos parâmetros. Foi ainda realizada uma comparação com um trabalho relacionado, gerando melhores resultados tanto na segmentação da mandíbula quanto a do crânio. Além disso, foram avaliadas TCs de pacientes com ossos faltantes e quebrados. A segmentação de uma TCFC é realizada em cerca de 5 minutos. Por fim, foram realizados testes com usuarios ortodontistas. Os resultados mostraram que nossa proposta não apenas produz segmentações precisas, como também é de fácil interação.