In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Os métodos incrementais pertencem a uma classe de métodos iterativos que divide o conjunto de dados em subconjuntos ordenados, e que atualiza a imagem ao processar cada subconjunto (sub-iterações). Isso acelera a convergência das reconstruções, e imagens de qualidade são obtidas em menos iterações. No entanto, a cada sub-iteração é necessário calcular os operadores de projeção e retroprojeção, resultando no custo computacional de ordem O(n3) para a reconstrução de imagens de dimensão × . Por outro lado, algumas alternativas baseadas na interpolação em uma grade regular no espaço de Fourier ou em transformadas rápidas não-uniformes, dentre outras ideias, foram desenvolvidas a fim de aliviar esse custo computacional. Além disso, diversas abordagens foram bem sucedidas em acelerar o cálculo das iterações de algoritmos clássicos, mas nenhuma havia sido utilizada em conjunto com os métodos incrementais. Neste trabalho é proposta uma nova abordagem em que a técnica de transformada rápida de Fourier não uniforme (NFFT) é utilizada nas sub-iterações de métodos incrementais com o objetivo de efetuar de forma eficiente os cálculos numericamente mais intensos: a projeção e a retroprojeção, resultando em métodos incrementais com complexidade O(n2 log n ). Os métodos propostos são aplicados à tomografia por radiação síncrotron e os resultados da pesquisa mostram um bom desempenho. / Incremental methods belong to a class of iterative methods that divide the data set into ordered subsets, and which update the image when processing each subset (sub-iterations). It accelerates the reconstruction convergence and quality images are obtained in fewer iterations. However, it is necessary to compute the projection and backprojection operators in each sub-iteration, resulting in the computational cost of O(n3) flops for × images. On the other hand, some alternatives based on interpolation over a regular grid on the Fourier space or on nonequispaced fast transforms, among other ideas, were developed in order to alleviate the computational cost. In addition, several approaches substantially speed up the computation of the iterations of classical algorithms, but the incremental methods had not been benefited from these techniques. In this work, a new approach is proposed in which the nonequispaced fast Fourier transform (NFTT) is used in each subiteration of incremental methods in order to perform the numerically intensive calculations efficiently: the projection and backprojection, resulting in incremental methods with complexity O(n2 log n ). The proposed methods are applied to the synchrotron radiation tomography and the results show a good performance.

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

Os métodos incrementais pertencem a uma classe de métodos iterativos que divide o conjunto de dados em subconjuntos ordenados, e que atualiza a imagem ao processar cada subconjunto (sub-iterações). Isso acelera a convergência das reconstruções, e imagens de qualidade são obtidas em menos iterações. No entanto, a cada sub-iteração é necessário calcular os operadores de projeção e retroprojeção, resultando no custo computacional de ordem O(n3) para a reconstrução de imagens de dimensão × . Por outro lado, algumas alternativas baseadas na interpolação em uma grade regular no espaço de Fourier ou em transformadas rápidas não-uniformes, dentre outras ideias, foram desenvolvidas a fim de aliviar esse custo computacional. Além disso, diversas abordagens foram bem sucedidas em acelerar o cálculo das iterações de algoritmos clássicos, mas nenhuma havia sido utilizada em conjunto com os métodos incrementais. Neste trabalho é proposta uma nova abordagem em que a técnica de transformada rápida de Fourier não uniforme (NFFT) é utilizada nas sub-iterações de métodos incrementais com o objetivo de efetuar de forma eficiente os cálculos numericamente mais intensos: a projeção e a retroprojeção, resultando em métodos incrementais com complexidade O(n2 log n ). Os métodos propostos são aplicados à tomografia por radiação síncrotron e os resultados da pesquisa mostram um bom desempenho. / Incremental methods belong to a class of iterative methods that divide the data set into ordered subsets, and which update the image when processing each subset (sub-iterations). It accelerates the reconstruction convergence and quality images are obtained in fewer iterations. However, it is necessary to compute the projection and backprojection operators in each sub-iteration, resulting in the computational cost of O(n3) flops for × images. On the other hand, some alternatives based on interpolation over a regular grid on the Fourier space or on nonequispaced fast transforms, among other ideas, were developed in order to alleviate the computational cost. In addition, several approaches substantially speed up the computation of the iterations of classical algorithms, but the incremental methods had not been benefited from these techniques. In this work, a new approach is proposed in which the nonequispaced fast Fourier transform (NFTT) is used in each subiteration of incremental methods in order to perform the numerically intensive calculations efficiently: the projection and backprojection, resulting in incremental methods with complexity O(n2 log n ). The proposed methods are applied to the synchrotron radiation tomography and the results show a good performance.

Segmentação de objetos em imagens é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. O conhecimento de alto nível e específico do usuário é frequentemente requerido no processo de segmentação, devido à presença de fundos heterogêneos, objetos com bordas fracamente definidas, inomogeneidade de campo, ruído, artefatos, efeitos de volume parcial e seus efeitos conjuntos. Propriedades globais do objeto de interesse, tais como conexidade, restrições de forma e polaridade de borda, são conhecimentos prévios de alto nível úteis para a sua segmentação, permitindo a customização da segmentação para um objeto alvo. Nesse trabalho, apresentamos um novo método chamado Transformada Imagem-Floresta Orientada Conexa (COIFT, Connected Oriented Image Foresting Transform), que fornece soluções ótimas globais de acordo com uma medida de corte em grafo, incorporando a restrição de conexidade na Transformada Imagem-Floresta Orientada (OIFT, Oriented Image Foresting Transform), com o fim de garantir a geração de objetos conexos, bem como permitir o controle simultâneo da polaridade de borda. Enquanto o emprego de restrições de conexidade em outros arcabouços, tais como no algoritmo de corte-mínimo/fluxo-máximo (min-cut/max-flow), leva a um problema NP-difícil, a COIFT conserva o baixo custo computacional da OIFT. Experimentos mostram que a COIFT pode melhorar consideravelmente a segmentação de objetos com partes finas e alongadas, para o mesmo número de sementes em segmentação baseada em marcadores. / Object segmentation is one of the most fundamental and challenging problems in image processing and computer vision. The high-level and specific knowledge of the user is often required in the segmentation process, due to the presence of heterogeneous backgrounds, objects with poorly defined boundaries, field inhomogeneity, noise, artifacts, partial volume effects and their joint effects. Global properties of the object of interest, such as connectivity, shape constraints and boundary polarity, are useful high-level priors for its segmentation, allowing the customization of the segmentation for a given target object. In this work, we introduce a new method called Connected Oriented Image Foresting Transform (COIFT), which provides global optimal solutions according to a graph-cut measure in graphs, subject to the connectivity constraint in the Oriented Image Foresting Transform (OIFT), in order to ensure the generation of connected objects, as well as allowing the simultaneous control of the boundary polarity. While the use of connectivity constraints in other frameworks, such as in the min-cut/max-flow algorithm, leads to a NP-Hard problem, COIFT retains the low computational cost of OIFT. Experiments show that COIFT can considerably improve the segmentation of objects with thin and elongated parts, for the same number of seeds in segmentation based on markers.

Segmentação de objetos em imagens é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. O conhecimento de alto nível e específico do usuário é frequentemente requerido no processo de segmentação, devido à presença de fundos heterogêneos, objetos com bordas fracamente definidas, inomogeneidade de campo, ruído, artefatos, efeitos de volume parcial e seus efeitos conjuntos. Propriedades globais do objeto de interesse, tais como conexidade, restrições de forma e polaridade de borda, são conhecimentos prévios de alto nível úteis para a sua segmentação, permitindo a customização da segmentação para um objeto alvo. Nesse trabalho, apresentamos um novo método chamado Transformada Imagem-Floresta Orientada Conexa (COIFT, Connected Oriented Image Foresting Transform), que fornece soluções ótimas globais de acordo com uma medida de corte em grafo, incorporando a restrição de conexidade na Transformada Imagem-Floresta Orientada (OIFT, Oriented Image Foresting Transform), com o fim de garantir a geração de objetos conexos, bem como permitir o controle simultâneo da polaridade de borda. Enquanto o emprego de restrições de conexidade em outros arcabouços, tais como no algoritmo de corte-mínimo/fluxo-máximo (min-cut/max-flow), leva a um problema NP-difícil, a COIFT conserva o baixo custo computacional da OIFT. Experimentos mostram que a COIFT pode melhorar consideravelmente a segmentação de objetos com partes finas e alongadas, para o mesmo número de sementes em segmentação baseada em marcadores. / Object segmentation is one of the most fundamental and challenging problems in image processing and computer vision. The high-level and specific knowledge of the user is often required in the segmentation process, due to the presence of heterogeneous backgrounds, objects with poorly defined boundaries, field inhomogeneity, noise, artifacts, partial volume effects and their joint effects. Global properties of the object of interest, such as connectivity, shape constraints and boundary polarity, are useful high-level priors for its segmentation, allowing the customization of the segmentation for a given target object. In this work, we introduce a new method called Connected Oriented Image Foresting Transform (COIFT), which provides global optimal solutions according to a graph-cut measure in graphs, subject to the connectivity constraint in the Oriented Image Foresting Transform (OIFT), in order to ensure the generation of connected objects, as well as allowing the simultaneous control of the boundary polarity. While the use of connectivity constraints in other frameworks, such as in the min-cut/max-flow algorithm, leads to a NP-Hard problem, COIFT retains the low computational cost of OIFT. Experiments show that COIFT can considerably improve the segmentation of objects with thin and elongated parts, for the same number of seeds in segmentation based on markers.

A segmentação de imagens é um problema muito importante em visão computacional, no qual uma imagem é dividida em regiões relevantes, tal como para isolar objetos de interesse de uma dada aplicação. Métodos de segmentação baseados na transformada imagem-floresta (IFT, Image Foresting Transform), com funções de conexidade monotonicamente incrementais (MI) têm alcançado um grande sucesso em vários contextos. Na segmentação interativa de imagens, na qual o usuário pode especificar o objeto desejado, novas sementes podem ser adicionadas e/ou removidas para corrigir a rotulação até conseguir a segmentação esperada. Este processo gera uma sequência de IFTs que podem ser calculadas de modo mais eficiente pela DIFT (Differential Image Foresting Transform). Recentemente, funções de conexidade não monotonicamente incrementais (NMI) têm sido usadas com sucesso no arcabouço da IFT no contexto de segmentação de imagens, permitindo incorporar informações de alto nível, tais como, restrições de forma, polaridade de borda e restrição de conexidade, a fim de customizar a segmentação para um dado objeto desejado. Funções não monotonicamente incrementais foram também exploradas com sucesso na geração de superpixels, via sequências de execuções da IFT. Neste trabalho, apresentamos um estudo sobre a Transformada Imagem-Floresta Diferencial no caso de funções NMI. Nossos estudos indicam que o algoritmo da DIFT original apresenta uma série de inconsistências para funções não monotonicamente incrementais. Este trabalho estende a DIFT, visando incorporar um subconjunto das funções NMI em grafos dirigidos e mostrar sua aplicação no contexto da geração de superpixels. Outra aplicação que é apresentada para difundir a relevância das funções NMI é o algoritmo Bandeirantes para perseguição de bordas e rastreamento de curvas. / Image segmentation is a problem of great relevance in computer vision, in which an image is divided into relevant regions, such as to isolate an object of interest for a given application. Segmentation methods with monotonically incremental connectivity functions (MI) based on the Image Foresting Transform (IFT) have achieved great success in several contexts. In interactive segmentation of images, in which the user is allowed to specify the desired object, new seeds can be added and/or removed to correct the labeling until achieving the expected segmentation. This process generates a sequence of IFTs that can be calculated more efficiently by the Differential Image Foresting Trans- form (DIFT). Recently, non-monotonically incremental connectivity functions (NMI) have been used successfully in the IFT framework in the context of image segmentation, allowing the incorporation of shape, boundary polarity, and connectivity constraints, in order to customize the segmentation for a given target object. Non-monotonically incremental functions were also successfully exploited in the generation of superpixels, via sequences of IFT executions. In this work, we present a study of the Differential Image Foresting Transform in the case of NMI functions. Our research indicates that the original DIFT algorithm presents a series of inconsistencies for non-monotonically incremental functions. This work extends the DIFT algorithm to NMI functions in directed graphs, and shows its application in the context of the generation of superpixels. Another application that is presented to spread the relevance of NMI functions is the Bandeirantes algorithm for curve tracing and boundary tracking.

A segmentação de imagens é um problema muito importante em visão computacional, no qual uma imagem é dividida em regiões relevantes, tal como para isolar objetos de interesse de uma dada aplicação. Métodos de segmentação baseados na transformada imagem-floresta (IFT, Image Foresting Transform), com funções de conexidade monotonicamente incrementais (MI) têm alcançado um grande sucesso em vários contextos. Na segmentação interativa de imagens, na qual o usuário pode especificar o objeto desejado, novas sementes podem ser adicionadas e/ou removidas para corrigir a rotulação até conseguir a segmentação esperada. Este processo gera uma sequência de IFTs que podem ser calculadas de modo mais eficiente pela DIFT (Differential Image Foresting Transform). Recentemente, funções de conexidade não monotonicamente incrementais (NMI) têm sido usadas com sucesso no arcabouço da IFT no contexto de segmentação de imagens, permitindo incorporar informações de alto nível, tais como, restrições de forma, polaridade de borda e restrição de conexidade, a fim de customizar a segmentação para um dado objeto desejado. Funções não monotonicamente incrementais foram também exploradas com sucesso na geração de superpixels, via sequências de execuções da IFT. Neste trabalho, apresentamos um estudo sobre a Transformada Imagem-Floresta Diferencial no caso de funções NMI. Nossos estudos indicam que o algoritmo da DIFT original apresenta uma série de inconsistências para funções não monotonicamente incrementais. Este trabalho estende a DIFT, visando incorporar um subconjunto das funções NMI em grafos dirigidos e mostrar sua aplicação no contexto da geração de superpixels. Outra aplicação que é apresentada para difundir a relevância das funções NMI é o algoritmo Bandeirantes para perseguição de bordas e rastreamento de curvas. / Image segmentation is a problem of great relevance in computer vision, in which an image is divided into relevant regions, such as to isolate an object of interest for a given application. Segmentation methods with monotonically incremental connectivity functions (MI) based on the Image Foresting Transform (IFT) have achieved great success in several contexts. In interactive segmentation of images, in which the user is allowed to specify the desired object, new seeds can be added and/or removed to correct the labeling until achieving the expected segmentation. This process generates a sequence of IFTs that can be calculated more efficiently by the Differential Image Foresting Trans- form (DIFT). Recently, non-monotonically incremental connectivity functions (NMI) have been used successfully in the IFT framework in the context of image segmentation, allowing the incorporation of shape, boundary polarity, and connectivity constraints, in order to customize the segmentation for a given target object. Non-monotonically incremental functions were also successfully exploited in the generation of superpixels, via sequences of IFT executions. In this work, we present a study of the Differential Image Foresting Transform in the case of NMI functions. Our research indicates that the original DIFT algorithm presents a series of inconsistencies for non-monotonically incremental functions. This work extends the DIFT algorithm to NMI functions in directed graphs, and shows its application in the context of the generation of superpixels. Another application that is presented to spread the relevance of NMI functions is the Bandeirantes algorithm for curve tracing and boundary tracking.