O problema da partição de pontos com pesos em grades de quadriláteros

• Processo: 15/17948-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de janeiro de 2016
• Data de Término da vigência: 30 de abril de 2016
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Mateus Augusto Bellomo Agrello Ruivo
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Heurística Pontos quânticos Quadrilátero Ferrífero Meta-heurística Processamento de imagens Modelagem de partição bayesiana
• Palavra(s)-Chave do Pesquisador: equalização de histogramas | Grasp | heuristicas | partição de quadriláteros | Algoritmos heurísticos

Resumo

Este projeto investigará o problema de partição de um conjunto de pontos do plano com pesos em uma grade de quadriláteros de modo a otimizar uma função dada. O problema está diretamente relacionado com equalização de histogramas de imagens em mais de uma escala de cor. Essa tecnica e utilizada na área de processamento de imagens com o intuito de melhor distribuir as cores em uma imagem através do aumento do contraste. Não existe um algoritmo eficiente capaz de solucionar o problema e, possivelmente, este não será encontrado tendo em vista que uma versão de decisão j[ foi provada estar em NP-difícil. Assim, o objetivo deste projeto é o desenvolvimento de uma metaheurística GRASP para resolver uma variante do problema da partição de pontos com peso em uma grade de quadriláteros. Por ser relevante na aplicação em processamento de imagens citada anteriormente, a função escolhida para minimizar será o desvio máximo em torno da média da soma dos pesos dos pontos em cada quadrilátero da grade.