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

• Processo: 19/08759-2
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Data de Início da vigência: 01 de outubro de 2021
• Data de Término da vigência: 31 de março de 2023
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Metodologia e Técnicas da Computação
• Acordo de Cooperação: Uppsala University
• Proposta de Mobilidade: SPRINT - Projetos de pesquisa - Mobilidade
• Pesquisador responsável: Alexandre Xavier Falcão
• Beneficiário: Alexandre Xavier Falcão
• Pesquisador Responsável no exterior: Filip Malmberg
• Instituição Parceira 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)
• Palavra(s)-Chave do Pesquisador: algoritmos em grafos | Processamento de Imagem | segmentação de imagem | Visão Computacional | Análise 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)