Um algoritmo eficiente para segmentação de imagem, campos aleatórios de Markov e problemas relacionados

Problemas de inferência estatística envolvem o ajuste de observações amostrais para que se adequem a alguns requisitos de classificação a priori ou restrições de ordem. Nesses problemas, o objetivo é minimizar a função de custo de desvio que depende da distância entre o valor observado e o valor modificado. Em problemas de campo aleatório de Markov, também existe uma relação par-a-par entre os objetos. O objetivo no problema de campo aleatório de Markov é minimizar a soma da função de custo de desvio e uma função de penalidade que cresce com a distância entre os valores de pares relacionados---função de separação. Discutimos problemas de campos aleatórios de Markov no contexto de uma aplicação representativa---o problema de segmentação de imagem. Nesse problema, a meta é modificar os tons de cor atribuídos aos pixels de uma imagem de modo que a função de penalidade, composta por um termo devido ao desvio do tom de cor inicial e um segundo termo que penaliza diferenças nos valores atribuídos a pixels vizinhos, seja minimizada. Apresentamos aqui um algoritmo que resolve o problema em tempo polinomial quando a função de desvio é convexa e a função de separação é linear; e em tempo polinomial forte quando a função de custo de desvio é linear, quadrática ou convexa linear por partes com poucas peças (onde “poucas” significa um número exponencial em uma função polinomial do número de variáveis e restrições). A complexidade do algoritmo para um problema com n pixels ou variáveis, m relações de adjacência ou restrições, e intervalo de valores de variáveis (cores) U, é O(T(n,m) + n log U), onde T(n,m) é a complexidade de resolver o problema do corte mínimo s,t em um grafo com n nós e m arcos. Além disso, outros algoritmos mostram resolver o problema com desvio convexo e separação convexa em tempo de execução O(mn log n log nU) e o problema com desvio não convexo e separação convexa em tempo de execução O(T(nU, mU)). O problema de separação não convexa é NP-difícil mesmo para valores fixos de U. Para a família de problemas com funções de desvio convexas e função de separação linear, o algoritmo descrito aqui funciona em tempo polinomial, sendo demonstrado que é o mais rápido possível.