O corte de grafos é uma técnica poderosa para segmentação de imagens. Ela modela a imagem como um grafo ponderado. Cada pixel torna-se um nó (vértice) do grafo. Arestas conectam pixels vizinhos com pesos de similaridade. Dois nós especiais representam o objeto (fonte) e o fundo (sumidouro). Primeiramente, o algoritmo encontra o corte de custo mínimo no grafo. Este corte separa a fonte do sumidouro de forma ótima. Consequentemente, os nós de cada lado definem a segmentação final. Portanto, o corte de grafos resolve um problema de otimização global.
modelagem do problema como grafo
A modelagem correta do grafo é crucial para o sucesso. Primeiramente, nós (pixels) conectam-se por arestas neig(h)boças (n-links). O peso destas arestas reflete a similaridade entre pixels vizinhos. Pixels semelhantes (mesma cor/textura) recebem pesos altos. Pixels diferentes, por outro lado, recebem pesos baixos. Além disso, nós conectam-se aos terminais fonte e sumidouro (t-links). O peso dos t-links reflete a probabilidade de pertencer ao objeto ou fundo. Por exemplo, sementes fornecidas pelo usuário definem estas probabilidades. O corte mínimo, portanto, separa o objeto do fundo cortando arestas de baixo peso.
algoritmo de corte mínimo e fluxo máximo
O teorema do fluxo máximo / corte mínimo fundamenta este método. Ele afirma que o corte mínimo equivale ao fluxo máximo no grafo. Primeiramente, o algoritmo envia fluxo da fonte para o sumidouro. O fluxo máximo satura as arestas de menor capacidade. Estas arestas saturadas formam o corte mínimo do grafo. Algoritmos eficientes como Boykov-Kolmogorov resolvem este problema rapidamente. Por exemplo, imagens de até 1 megapixel são segmentadas em segundos. A vantagem é a garantia de encontrar o mínimo global. Diferentemente de métodos iterativos, o corte de grafos não fica preso em mínimos locais. Portanto, a solução é globalmente ótima para a função de energia definida.
vantagens e quando utilizar graph cuts
O corte de grafos oferece várias vantagens significativas. Primeiramente, ele produz segmentações precisas mesmo com bordas fracas. Além disso, o método lida bem com ruído e texturas complexas. A segmentação é globalmente ótima para a função de energia escolhida. Utilize graph cuts quando precisar de segmentações interativas de alta qualidade. Por exemplo, separar o objeto do fundo em fotografias (matting). Outra aplicação é na segmentação de órgãos em imagens médicas. O usuário fornece algumas sementes (pinceladas) no objeto e no fundo. Contudo, o método é computacionalmente mais caro que limiarização simples. Portanto, evite-o em aplicações embarcadas de tempo real. Em resumo, escolha graph cuts quando precisão for mais importante que velocidade.