antonino

Corte de Grafos (Graph Cuts)

Por
programador
1.1.2.4 – Redes Neurais – Visao Computacional
1.1.2.4.2 – Segmentacao de Imagens
1.1.2.4.2.3 – Crescimento de Regiao (Region Growing)
1.1.2.4.2.4 – Corte de Grafos (Graph Cuts)
1.1.2.4.2.5 – Watershed
LEGENDA
Principal
Ramo
Metodo
Problemas
Modelo
Arquitetura

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.

Crescimento de Região (Region Growing)

Por
programador
1.1.2.4 – Redes Neurais – Visao Computacional
1.1.2.4.2 – Segmentacao de Imagens
1.1.2.4.2.3 – Crescimento de Regiao (Region Growing)
1.1.2.4.2.4 – Corte de Grafos (Graph Cuts)
1.1.2.4.2.5 – Watershed
LEGENDA
Principal
Ramo
Metodo
Problemas
Modelo
Arquitetura

O crescimento de região é uma técnica de segmentação baseada em similaridade. Diferentemente da detecção de bordas, ela agrupa pixels semelhantes. Primeiramente, o algoritmo necessita de “sementes” iniciais. Estas sementes são pixels que claramente pertencem ao objeto. Em seguida, o método agrega pixels vizinhos similares às sementes. A similaridade pode ser medida por intensidade, cor ou textura. Por exemplo, pixels com intensidade próxima à média da região. O processo continua iterativamente até não haver mais pixels similares. Consequentemente, o crescimento de região produz regiões conectadas e homogêneas. Portanto, ele é útil para segmentar objetos com textura uniforme.

critérios de similaridade e conectividade

Dois critérios fundamentais governam o crescimento de região. Primeiramente, a similaridade entre o pixel candidato e a região. Esta similaridade geralmente usa uma diferença de intensidade máxima. Um limiar (threshold) controla o quão rigorosa é a admissão. Valores baixos produzem regiões menores e mais homogêneas. Valores altos, por outro lado, produzem regiões maiores e mais heterogêneas. Além disso, a conectividade espacial é essencial para o processo. Pixels similares mas desconectados não pertencem à mesma região. Por exemplo, utiliza-se conectividade 4 ou 8 entre vizinhos. Portanto, a escolha correta dos critérios é crucial para o sucesso.

vantagens e desafios do método

O crescimento de região oferece várias vantagens importantes. Primeiramente, ele garante que as regiões geradas sejam conectadas. Ao contrário da limiarização, não produz pixels isolados. Além disso, o método é flexível quanto ao critério de similaridade. Pode-se usar intensidade, cor, textura ou múltiplas características. Contudo, o crescimento de região tem desafios significativos. Ele é sensível à escolha das sementes iniciais. Sementes mal posicionadas produzem segmentações incorretas. Outra dificuldade é a definição do limiar de similaridade. Um limiar fixo pode falhar em imagens com variações de iluminação. Portanto, versões adaptativas do algoritmo foram desenvolvidas para mitigar este problema.

quando utilizar crescimento de região

Utilize o crescimento de região quando os objetos forem relativamente homogêneos. Por exemplo, tumores em imagens médicas ou células em microscopia. Outra aplicação é na segmentação de nuvens em imagens de satélite. O método também funciona bem para extrair vasos sanguíneos em angiografias. Contudo, evite o crescimento de região em cenas muito complexas. Objetos com texturas variadas ou ruído excessivo prejudicam o resultado. Nestes casos, prefira métodos como watershed ou graph cuts. Além disso, a necessidade de sementes manuais é uma limitação. Para aplicações totalmente automáticas, combine o método com detecção automática de sementes. Em resumo, escolha esta técnica quando tiver bom conhecimento prévio sobre os objetos de interesse.