Busca avançada
Ano de início
Entree

Algoritmos eficientes para a otimização da norma-máximo em análise de imagem e visão computacional

Resumo

Esta proposta é parte de uma iniciativa maior de estudar uma classe específica de problemas de otimização onde a função objetivo é definida como "normamáxima" sobre um conjunto de variáveis. Tais problemas de otimização são frequentes em processamento de imagem (e.g., em filtragem, segmentação e registro de imagens). Também é conhecido que para muitos desses problemas, existem soluções ótimas globais eficientes que executam em tempo quasi-linear. Apesar do sucesso desses métodos, suas limitações e potencial em resolver o problema geral de normamáxima são ainda desconhecidos. Portanto, nossa meta a longo prazo é provê uma caracterização detalhada e sistemática de problemas de otimização de normamáxima que podem ser resolvidos eficientemente em tempo polinomial de baixa ordem. Nesta proposta, o foco será em um dos subproblemas da classe "normamáxima". A proposta é baseada em uma recente descoberta: a conexão teórica entre problemas de otimização de "normamáxima" e satisfatibilidade booleana. Esta nova e previamente inexplorada conexão provê um arcabouço no qual algoritmos existentes e novos podem ser (re)formulados e comparados. Como consequência direta desta conexão, o grupo já apresenta resultados preliminares que provam que a classe de problemas de normamáxima que pode ser resolvida em tempo polinomial é bem maior do que a conhecida, muito embora a prova não leve ainda a algoritmos eficientes. A meta deste projeto, portanto, é formular e implementar, com base em resultados teóricos, algoritmos para resolver problemas de otimização de normamáxima em processamento de imagem de forma eficiente em complexidade assintótica e na prática. (AU)