A segmentação de imagens consiste em dividir uma imagem em regiões ou objetos que a compõem, como, por exemplo, para isolar os pixels de um objeto alvo de uma dada aplicação. Em segmentação de imagens médicas, o objeto de interesse comumente apresenta transições em suas bordas predominantemente do tipo claro para escuro ou escuro para claro. Métodos tradicionais por região, como a conexidade fuzzy relativa (RFC - Relative Fuzzy Connectedness), não distinguem bem entre essas bordas similares com orientações opostas. A especificação da polaridade de contorno pode ajudar a amenizar esse problema, o que requer uma formulação matemática em grafos dirigidos. Uma discussão sobre como incorporar essa propriedade no arcabouço do RFC é apresentada neste trabalho. Uma prova teórica da otimalidade do novo algoritmo, chamado conexidade fuzzy relativa com orientação (ORFC - Oriented Relative Fuzzy Connectedness), em termos de uma função de energia em grafos dirigidos sujeita as restrições de sementes é apresentada, bem como a sua apli- cação em poderosos métodos híbridos de segmentação. O método híbrido proposto ORFC &Graph Cut preserva a robustez do ORFC em relação à escolha de sementes, evitando o problema do viés de encolhimento do método de Corte em Grafo (GC - Graph Cut), e mantém o forte controle do GC no delineamento de contornos de bordas irregulares da imagem. Os métodos propostos são avaliados usando imagens médicas de ressonáncia magnética (RM) e tomografia computadorizada (TC) do cérebro humano e de estudos torácicos. / Image segmentation consists of dividing an image into its composing regions or objects, for example, to isolate the pixels of a target object of a given application. In segmentation of medical images, the object of interest commonly presents transitions at its border predominantly from bright to dark or dark to bright. Traditional region-based methods of image segmentation, such as Relative Fuzzy Connectedness (RFC), do not distinguish well between similar boundaries with opposite orientations. The specification of the boundary polarity can help to alleviate this problem but this requires a mathematical formulation on directed graphs. A discussion on how to incorporate this property in the RFC framework is presented in this work. A theoretical proof of the optimality of the new algorithm, called Oriented Relative Fuzzy Connectedness (ORFC), in terms of an energy function on directed graphs subject to seed constraints is presented, and its application in powerful hybrid segmentation methods. The hybrid method proposed ORFC&Graph Cut preserves the robustness of ORFC respect to the seed choice, avoiding the shrinking problem of Graph Cut (GC), and keeps the strong control of the GC in the contour delination of irregular image boundaries. The proposed methods are evaluated using magnetic resonance medical imaging (MR) and computed tomography (CT) of the human brain and thoracic studies.

A segmentação de imagens consiste em dividir uma imagem em regiões ou objetos que a compõem, como, por exemplo, para isolar os pixels de um objeto alvo de uma dada aplicação. Em segmentação de imagens médicas, o objeto de interesse comumente apresenta transições em suas bordas predominantemente do tipo claro para escuro ou escuro para claro. Métodos tradicionais por região, como a conexidade fuzzy relativa (RFC - Relative Fuzzy Connectedness), não distinguem bem entre essas bordas similares com orientações opostas. A especificação da polaridade de contorno pode ajudar a amenizar esse problema, o que requer uma formulação matemática em grafos dirigidos. Uma discussão sobre como incorporar essa propriedade no arcabouço do RFC é apresentada neste trabalho. Uma prova teórica da otimalidade do novo algoritmo, chamado conexidade fuzzy relativa com orientação (ORFC - Oriented Relative Fuzzy Connectedness), em termos de uma função de energia em grafos dirigidos sujeita as restrições de sementes é apresentada, bem como a sua apli- cação em poderosos métodos híbridos de segmentação. O método híbrido proposto ORFC &Graph Cut preserva a robustez do ORFC em relação à escolha de sementes, evitando o problema do viés de encolhimento do método de Corte em Grafo (GC - Graph Cut), e mantém o forte controle do GC no delineamento de contornos de bordas irregulares da imagem. Os métodos propostos são avaliados usando imagens médicas de ressonáncia magnética (RM) e tomografia computadorizada (TC) do cérebro humano e de estudos torácicos. / Image segmentation consists of dividing an image into its composing regions or objects, for example, to isolate the pixels of a target object of a given application. In segmentation of medical images, the object of interest commonly presents transitions at its border predominantly from bright to dark or dark to bright. Traditional region-based methods of image segmentation, such as Relative Fuzzy Connectedness (RFC), do not distinguish well between similar boundaries with opposite orientations. The specification of the boundary polarity can help to alleviate this problem but this requires a mathematical formulation on directed graphs. A discussion on how to incorporate this property in the RFC framework is presented in this work. A theoretical proof of the optimality of the new algorithm, called Oriented Relative Fuzzy Connectedness (ORFC), in terms of an energy function on directed graphs subject to seed constraints is presented, and its application in powerful hybrid segmentation methods. The hybrid method proposed ORFC&Graph Cut preserves the robustness of ORFC respect to the seed choice, avoiding the shrinking problem of Graph Cut (GC), and keeps the strong control of the GC in the contour delination of irregular image boundaries. The proposed methods are evaluated using magnetic resonance medical imaging (MR) and computed tomography (CT) of the human brain and thoracic studies.

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.

Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação, como para isolar um objeto de interesse no domínio de uma imagem. A segmentação é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. Ela tem desempenhado um papel importante, por exemplo, na pesquisa em neurologia, envolvendo imagens de Ressonância Magnética (RM), para fins de diagnóstico e tratamento de doenças relacionadas com alterações na anatomia do cérebro humano. Métodos de segmentação baseados na transformada imagem- floresta (IFT, Image Foresting Transform), com funções de conexidade suaves, possuem resultados ótimos, segundo o critério da otimalidade dos caminhos descrito no artigo original da IFT, e têm sido usados com sucesso em várias aplicações, como por exemplo na segmentação de imagens RM de 1.5 Tesla. No entanto, esses métodos carecem de restrições de regularização de borda, podendo gerar segmentações com fronteiras muito irregulares e indesejadas. Eles também não distinguem bem entre bordas similares com orientações opostas, e possuem alta sensibilidade à estimativa dos pesos das arestas do grafo, gerando problemas em imagens com efeitos de inomogeneidade. Nesse trabalho são propostas extensões da IFT, do ponto de vista teórico e experimental, através do uso de funções de conexidade não suaves, para a segmentação interativa de imagens por região. A otimalidade dos novos métodos é suportada pela maximização de energias de corte em grafo, ou como o fruto de uma sequência de iterações de otimização de caminhos em grafos residuais. Como resultados principais temos: O projeto de funções de conexidade mais adaptativas e flexíveis, com o uso de pesos dinâmicos, que permitem um melhor tratamento de imagens com forte inomogeneidade. O uso de grafos direcionados, de modo a explorar a polaridade de borda dos objetos na segmentação por região, e o uso de restrições de forma que ajudam a regularizar a fronteira delineada, favorecendo a segmentação de objetos com formas mais regulares. Esses avanços só foram possíveis devido ao uso de funções não suaves. Portanto, a principal contribuição desse trabalho consiste no suporte teórico para o uso de funções não suaves, até então evitadas na literatura, abrindo novas perpectivas na pesquisa de processamento de imagens usando grafos. / Segmenting an image consist in to partition it into relevant regions for a given application, as to isolate an object of interest in the domain of an image. Segmentation is one of the most fundamental and challenging problems in image processing and computer vision. It has played an important role, for example, in neurology research, involving images of Magnetic Resonance (MR), for the purposes of diagnosis and treatment of diseases related to changes in the anatomy of the human brain. Segmentation methods based on the Image Foresting Transform (IFT), with smooth connectivity functions, have optimum results, according to the criterion of path optimality described in the original IFT paper, and have been successfully used in many applications as, for example, the segmentation of MR images of 1.5 Tesla. However, these methods present a lack of boundary regularization constraints and may produce segmentations with quite irregular and undesired boundaries. They also do not distinguish well between similar boundaries with opposite orientations, and have high sensitivity to the arc-weight estimation of the graph, producing poor results in images with strong inhomogeneity effects. In this work, we propose extensions of the IFT framework, from the theoretical and experimental points of view, through the use of non-smooth connectivity functions for region-based interactive image segmentation. The optimality of the new methods is supported by the maximization of graph cut energies, or as the result of a sequence of paths optimizations in residual graphs. We have as main results: The design of more adaptive and flexible connectivity functions, with the use of dynamic weights, that allow better handling of images with strong inhomogeneity. The use of directed graphs to exploit the boundary polarity of the objects in region-based segmentation, and the use of shape constraints that help to regularize the segmentation boundary, by favoring the segmentation of objects with more regular shapes. These advances were only made possible by the use of non-smooth functions. Therefore, the main contribution of this work is the theoretical support for the usage of non-smooth functions, which were until now avoided in literature, opening new perspectives in the research of image processing using graphs.

Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação, como para isolar um objeto de interesse no domínio de uma imagem. A segmentação é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. Ela tem desempenhado um papel importante, por exemplo, na pesquisa em neurologia, envolvendo imagens de Ressonância Magnética (RM), para fins de diagnóstico e tratamento de doenças relacionadas com alterações na anatomia do cérebro humano. Métodos de segmentação baseados na transformada imagem- floresta (IFT, Image Foresting Transform), com funções de conexidade suaves, possuem resultados ótimos, segundo o critério da otimalidade dos caminhos descrito no artigo original da IFT, e têm sido usados com sucesso em várias aplicações, como por exemplo na segmentação de imagens RM de 1.5 Tesla. No entanto, esses métodos carecem de restrições de regularização de borda, podendo gerar segmentações com fronteiras muito irregulares e indesejadas. Eles também não distinguem bem entre bordas similares com orientações opostas, e possuem alta sensibilidade à estimativa dos pesos das arestas do grafo, gerando problemas em imagens com efeitos de inomogeneidade. Nesse trabalho são propostas extensões da IFT, do ponto de vista teórico e experimental, através do uso de funções de conexidade não suaves, para a segmentação interativa de imagens por região. A otimalidade dos novos métodos é suportada pela maximização de energias de corte em grafo, ou como o fruto de uma sequência de iterações de otimização de caminhos em grafos residuais. Como resultados principais temos: O projeto de funções de conexidade mais adaptativas e flexíveis, com o uso de pesos dinâmicos, que permitem um melhor tratamento de imagens com forte inomogeneidade. O uso de grafos direcionados, de modo a explorar a polaridade de borda dos objetos na segmentação por região, e o uso de restrições de forma que ajudam a regularizar a fronteira delineada, favorecendo a segmentação de objetos com formas mais regulares. Esses avanços só foram possíveis devido ao uso de funções não suaves. Portanto, a principal contribuição desse trabalho consiste no suporte teórico para o uso de funções não suaves, até então evitadas na literatura, abrindo novas perpectivas na pesquisa de processamento de imagens usando grafos. / Segmenting an image consist in to partition it into relevant regions for a given application, as to isolate an object of interest in the domain of an image. Segmentation is one of the most fundamental and challenging problems in image processing and computer vision. It has played an important role, for example, in neurology research, involving images of Magnetic Resonance (MR), for the purposes of diagnosis and treatment of diseases related to changes in the anatomy of the human brain. Segmentation methods based on the Image Foresting Transform (IFT), with smooth connectivity functions, have optimum results, according to the criterion of path optimality described in the original IFT paper, and have been successfully used in many applications as, for example, the segmentation of MR images of 1.5 Tesla. However, these methods present a lack of boundary regularization constraints and may produce segmentations with quite irregular and undesired boundaries. They also do not distinguish well between similar boundaries with opposite orientations, and have high sensitivity to the arc-weight estimation of the graph, producing poor results in images with strong inhomogeneity effects. In this work, we propose extensions of the IFT framework, from the theoretical and experimental points of view, through the use of non-smooth connectivity functions for region-based interactive image segmentation. The optimality of the new methods is supported by the maximization of graph cut energies, or as the result of a sequence of paths optimizations in residual graphs. We have as main results: The design of more adaptive and flexible connectivity functions, with the use of dynamic weights, that allow better handling of images with strong inhomogeneity. The use of directed graphs to exploit the boundary polarity of the objects in region-based segmentation, and the use of shape constraints that help to regularize the segmentation boundary, by favoring the segmentation of objects with more regular shapes. These advances were only made possible by the use of non-smooth functions. Therefore, the main contribution of this work is the theoretical support for the usage of non-smooth functions, which were until now avoided in literature, opening new perspectives in the research of image processing using graphs.