Split & Merge

Visão Geral do Algoritmo do Método de Dividir e Unir

O algoritmo é muito simples.

Funciona dividindo a imagem recursivamente em uma quadtree, até que um nodo não possua mais diferenças enre seus pixels (de acordo com um critério pré-definido). Estes são nodos-folha e possuem a cor (ou cor média) dos pixels que contém. Nodos intermediários não possuem cor associada.

Em seguida, usando algum critérios de similaridade de pixel, retornamos subindo pela árvore, usando a própria estrutura da árvore como informação de topologia (não há necessidade de matriz de adjacência), e rerotulamos nodos adjacentes em um mesmo nível e nodos avô/pai/filho que possuam cores similares de acordo com o critério de similaridade escolhido.

Podemos usar o critério de similaridade que desejarmos.

Simulação de uma Execução de Split&Merge

Fase 1: Split

Iniciamos com uma árvore onde toda a imagem é rpresentada pela Raiz. Em seguida dividimos a imagem em quatro quadrantes:
arv1

A divisão de pixels, nestes dois passos, fica assim:
segmentation-10

Continuando a divisão recursiva, descemos mais um nível, em seguida procuramos algum nodo que seja homogêneo. Vamos encontrar 8:
arv2

Mais uma descida já nos fornece os nodos homogêneo restantes, todos unitários:
arv3

Estes dois passos recursisvos, vistos sobre a imagem ficam assim:

segmentation-11

Fase 2: Merge

Agora devemos retornar, subindo na árvore, colorindo:

  • Nodos-folha já possuem cor
  • Estrutura da árvore informa sobre adjacências

arv4

segmentation-12

Links

Externos

  1. Códigos de Split&Merge e CSC da Universidade de Koblenz
  2. Manual da Implementação de Split&Merge da Universidade de Koblenz
  3. Toques sobre o uso da Implementação de Split&Merge da Universidade de Koblenz
  4. Material de Imagem: The Berkeley Segmentation Dataset and Benchmark

Sobre o Autor

possui graduação em Ciências da Computação pela Universidade Federal de Santa Catarina (1989) e Doutorado Acadêmico (Dr. rer.nat.) em Ciências da Computação pela Universidade de Kaiserslautern (1996). Atualmente é professor Associado da Universidade Federal de Santa Catarina, onde é professor do Programa de Pós-graduação em Ciência da Computação e dos cursos de graduação em Ciências da Computação e Sistemas de Informação. É também professor e orientador de doutorado do Programa de Pós-Graduação em Ciências da Computação da Universidade Federal do Paraná - UFPR. Tem experiência nas áreas de Produção de Conteúdo para TV Digital Interativa, Informática em Saúde, Processamento e Análise de Imagens e Engenharia Biomédica, com ênfase em Telemedicina, Telerradiologia, Sistemas de Auxílio ao Diagnóstico por Imagem e Processamento de Imagens Médicas, com foco nos seguintes temas: analise inteligente de imagens, DICOM, CBIR, informática médica, visão computacional e PACS. Coordena o Instituto Nacional de Ciência e Tecnologia para Convergência Digital - INCoD. É também Coordenador Técnico do Sistema Integrado Catarinense de Telemedicina e Telessaúde (STT/SC), coordenador do Grupo de Trabalho Normalização em Telessaúde do Comitê Permanente de Telessaúde/Ministério da Saúde e membro fundador e ex-coordenador da Comissão Informática em Saúde da ABNT - ABNT/CEET 00:001.78. Atualmente também é membro da comissão ISO/TC 215 - Health Informatics. Foi coordenador da RFP6 - Conteúdo - do SBTVD - Sistema Brasileiro de TV Digital/Ministério das Comunicações. Foi o criador e primeiro Coordenador do Núcleo de Telessaúde de Santa Catarina no âmbito do Programa Telessaúde Brasil do Ministério da Saúde e da OPAS - Organização Pan-Americana de Saúde e criador do Núcleo Santa Catarina da RUTE - Rede Universitária de Telemedicina.