Resumo: 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 Ver menos

Abstract: The problem of bacteria colonies segmentation in Petri dishes has some very different characteristics from those found, for example, in segmenting natural images. The main feature is the high number of colonies that can be found on a plate. Thus, it is essential that the segmentation algorithm is capable of performing the image segmentation into a huge number of regions. This extreme scenario is ideal for analyzing segmentation algorithms limitations. In fact, this study showed that the original normalized cut algorithm, which is based on the spectral graph theory, is inappropriate for applications that require that the segmentation be performed on a large number of regions. However, the use of normalized cut criteria for segmenting bacteria colonies images is still possible thanks to a new algorithm that is being introduced in this paper. The new algorithm is based on hierarchical clustering of the graph nodes, instead of using the spectral theory concepts. Experiments also show that the bi-partitioning of a graph by the new algorithm has a normalized cut average value about 40 times lesser than the bi-partitioning by the algorithm based on the spectral theory Ver menos