The goal of this work is to describe an efficient algorithm for finding a binary segmentation of an image such that: the indicated object satisfies a novel high-level prior, called Local Band, LB, constraint; the returned segmentation is optimal, with respect to an appropriate graph cut measure, among all segmentations satisfying the given LB constraint. The new algorithm has two stages: expanding the number of arcs of a standard edge-weighted graph of an image; applying to this new weighted graph an algorithm known as an Oriented Image Foresting Transform, OIFT. In our theoretical investigations, we discuss the theoretical relationships of LB with other shape constraints and prove that OIFT algorithm belongs to a class of General Fuzzy Connectedness algorithms and so, has several good theoretical properties, like robustness for seed placement. The extension of the graph constructed in the first stage ensures, as we prove, that the resulted object indeed satisfies the given LB constraint. For purposes of computational efficiency, we consider the least number of arcs needed to guarantee the constraint. This graph construction is flexible enough to allow combining it with other high-level constraints. For the particular case of LB with infinite radius, this case called Band constraint, we also present an efficient algorithm, with proof of correctness, which can be applied directly to the original image graph. Finally, we experimentally demonstrate that the LB constraint gives competitive results as compared to Geodesic Star Convexity, Boundary Band, and Hedgehog Shape Prior, all implemented within OIFT framework and applied to various scenarios involving natural and medical images.

O objetivo deste trabalho é descrever um algoritmo eficiente para encontrar uma segmentação binária de uma imagem tal que: o objeto indicado satisfaz uma nova restrição de alto nível, chamada restrição de banda local, LB; a segmentação devolvida é ótima, em respeito a uma medida de corte em grafos apropriada, entre todas as segmentações que satisfaçam a restrição LB dada. O novo algoritmo tem dois estágios: expandir o número de arcos de um grafo tradicional de imagem; aplicando a este novo grafo com pesos, um algoritmo conhecido como Transformada Imagem-Floresta Orientada, OIFT. Em nossos trabalhos teóricos, discutimos as relações teóricas da LB com outras restrições de forma e provamos que o algoritmo da OIFT pertence a uma classe de algoritmos gerais de conexão difusa (\textit{General Fuzzy Connectedness}) e, portanto, possui várias propriedades teóricas, como robustez ao posicionamento de sementes. A extensão do grafo construído no primeiro estágio garante, como provamos, que o objeto resultante realmente satisfaz a restrição LB dada. Para efeitos de eficiência computacional, consideramos o menor número de arcos possível necessário para garantir a restrição. Esta construção de grafo é flexível o suficiente para permitir combiná-la com outras restrições de alto nível. Para o caso particular da LB com raio infinito, caso este chamado de restrição de banda, também apresentamos um algoritmo eficiente, com prova de corretude, que pode ser aplicado diretamente sobre o grafo de imagem original. Finalmente, demonstramos experimentalmente que a restrição LB possui resultados competitivos quando comparada com a convexidade geodésica em estrela, restrição de banda de borda e \textit{Hedgehog Shape Prior}, todos implementados dentro do arcabouço da OIFT e aplicados a vários cenários envolvendo imagens naturais e médicas.