Abordagens analíticas de um problema combinatório de descodificação de imagens

Abstract

Apresenta-se um modelo de codificação de imagens, bem como duas formulações para o problema da respectiva descodificação. A primeira formulação e baseada em programação inteira e a segunda é baseada na determinação de um estável máximo de um certo grafo associado. Em todos os casos se recorre a m6todos analíticos para a resolução do problema. No caso da formulação no contexto da teoria dos grafos, recorre-se a programação semidefinida e a programação quadrática convexa combinadas com branch-and-bound. Fizeram-se as respectivas implementações e compararam-se os diferentes resultados obtidos. Finalmente, analisaram-se alguns casos em que a codificação não determina univocamente as respectivas imagens.

A coding scheme of images is presented, as well as two formularizations for the problem of the respective decoding. The first formularization is based on integer programming and second it is based on the determination of a maximum stable set of a certain associated graph. In all the cases analytical rnethods are used for the resolution of the problern. In the case of the formularization in the context of the theory of the graphs, the sernidefinite programming and the convex quadratic programming are used combined with branch-and-bound. After the respective implementations the different gotten results had been compared. Finally, some cases had been analyzed where the codification does not determine the respective images.