| Processo: | 19/08759-2 |
| Linha de fomento: | Auxílio à Pesquisa - Regular |
| Vigência: | 01 de outubro de 2020 - 31 de março de 2022 |
| Área do conhecimento: | Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação |
| Convênio/Acordo: | Uppsala University |
| Proposta de Mobilidade: | SPRINT - Projetos de pesquisa - Mobilidade |
| Pesquisador responsável: | Alexandre Xavier Falcão |
| Beneficiário: | Alexandre Xavier Falcão |
| Pesq. responsável no exterior: | Filip Malmberg |
| Instituição no exterior: | Uppsala University (UU), Suécia |
| Instituição-sede: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil |
| Vinculado ao auxílio: | 14/12236-1 - AnImaLS: Anotação de Imagem em Larga Escala: o que máquinas e especialistas podem aprender interagindo?, AP.TEM |
| Assunto(s): | Visão computacional Análise de imagens Teoria dos grafos Processamento de imagens Segmentação (processamento de imagem) |
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)