O método Color Structure Code (CSC) [1,2] foi desenvolvido no Instituto de Visualização Computacional do Departamento de Informática da Universidade de Koblenz, Alemanha. CSC originalmente foi desenvolvido no contexto de um projeto entre a Universidade de Koblenz e Mercedes-Benz para o reconhecimento em tempo real de placas de trânsito a partir de um carro em movimento, mas pode ser utilizado para muitas outras áreas de aplicação [4, 5]. Em meados da década de 1990, era um algoritmo capaz de realizar segmentação a 3 fps rodando em uma workstation Sun Ultra, um feito para a época.

CSC é um algoritmo de segmentação por crescimento de regiões baseado em uma filosofia split-and-merge que emprega uma topologia hierárquica formada por ilhas hexagonais, um modelo topológico introduzido por [3]. Estas ilhas são organizadas em níveis.

CSC foi inspirado em HSC (Hierarquical Structure Code) desenvolvido por G. Hartmann no final da década de 1980.

Uma ilha de nível 0 é um hexágono composto por 7 pixels: os vértices do hexágono e um pixel representando seu centro. Durante o processo de formação da estrutura hierárquica, os níveis são organizados de tal forma que algumas ilhas se sobrepõem a parte de outras. Assim, uma ilha no nível n + 1 é composta de 7 ilhas de nível n parcialmente sorepostas, como mostra de forma abstrata a figura abaixo. Esse processo é repetido até uma única ilha cobrir toda a imagem.

Figura1. Visão abstrata das ilhas (Priese & Rehrmann, 1993/2003)

A operação de uma topologia hexagonal tem maiores dificuldades na prática. O particionamento desta imagem na topologia hexagonal começa pelo nível 0 (zero), ele sendo composto de sete pixels e em seu redor possui seis ilhas vizinhas em exatamente um pixel. A hierarquia é continuada até os altos níveis no mesmo caminho na topologia hexagonal.

O único problema de se aproximar é as diferentes definições de vizinhança de pixels.

Figura 2. Interpretação pseudo-hexagonal de um grid de pixel

Figura 3. Correspondência entre ilhas vistas como círculos com 6+1 pontos (a) e grid pseudo-hexagonal de pixel (b). (Priese & Rehrmann, 1993/2003)

A visão abstrata das ilhas da figura 1 pode ser vista de uma forma mais concreta se imaginarmos que as linhas da imagem são alternadamente deslocadas de 1/2 pixel para a esquerda. Assim podemos formar hexágonos, como na figura abaixo, que ilustra 3 níveis de ilhas hexagonais:

Figura 4. Visão mais próxima da divisão da imagem – supondo deslocamento horizontal alternado de 1/2 pixel na imagem

Para exemplificar o processo de construção das ilhas, vamos considerar uma imagem de dimensões 513×513.

Todas as ilhas são organizadas da mesma forma:

• As coordenadas de uma ilha são as coordenadas de seu pixel central;
• A primeira ilha de cada nível, à exceção do último nível, sempre terá a coordenada (0, 0).

No caso desta imagem-exemplo, o nível onde esta sistemática não é mais aplicada é o nível 7. A partir dele o esquema de construção muda:

• neste nível (nivel 7), sete (7) ilhas são suficientes para cobrir toda a imagem;
• inserimos a primeira ilha na coordenada (128, 0) e assim por diante, cobrindo a imagem com 7 ilhas;
• criamos o último nível e inserimos apenas a ilha-raiz (nível 8);
• esta inserção ocorre no centro da imagem, em (256, 256).

Figura 5. Organização de Ilhas em Nível 0 para uma imagem 513×513. Primeira ilha sempre inicia em (0,0).

Assim, uma hierarquia de ilhas definida em uma malha ortogonal de dimensões  2^m + 1  x  2^m + 1  constitui uma hierarquia de m níveis.

As coordenadas de todas as ilhas de do nível n podem ser calculadas através da função IC(m, n) dada por:

1. Para todos os níveis onde n < m – 2:
   
2. Para o penúltimo nível (n = m – 2):
   
3. Para o último nível (n = m – 1):
   

A título de ilustração da indexação de ilhas, vamos tomar a nossa imagem hipotética 513 x 513 do exemplo anterior:  513 = 2⁹ + 1, logo m = 9 e a imagem, inicializada terá nove níveis hierárquicos.

Os cálculos para n = 0, n = 1 e n = 7 ficam:

A posição de um conjunto de sub-ilhas em relação à sua ilha-mãe é sempre dada pela relação da tabela adiante:

CSC em 3D

Alternativamente, CSC pode ser utilizado para segmentação 3D de volumes, como Tomografias Computadorizadas ou Ressonâncias Magnéticas. Nesse caso utilizamos vizinhanças denominadas S15-CSC (a) eC19-CSC (b):

Uma aplicação é a segmentação de tomografias por ressonância magnética do crânio, para o qual foi desenvilvida uma pipeline especial, como descrito em [4] e na seção sobre ressonância magnética, mais abaixo.

Código de Estrutura de Cores

A geração do Código de Estrutura de Cores (CSC) ocorre em quatro fases:

1. Pré-Processamento: É realizada uma filtragem da imagem para suavizá-la.
2. Inicialização: A imagem é particionada em pequenas regiões de cor atômicas. Ocorre dentro de ilhas de nível 0.
3. Ligação: Essas regiões pequenas crescem de forma hierárquica, formando segmentos de cor. Nesta fase é possível detectar regiões conectadas por uma cadeia de cores com modificações suaves entre si, que deveriam ser desconectadas novamente.
4. Partição: Grandes cadeias de segmentos de cor, erroneamente conectadas na fase de ligação, são separadas.

Fase de Pré-Processamento

Na fase de pré-processamento são usados técnicas apropriadas como filtros lineares simples que repassam o centro do pixel para um peso médio com os pixels da vizinhança que tem desvantagem de borrar as bordas. Para proteger as bordas das borradas enquanto um filtro é usado para adaptar-se a mudança de local na estrutura para o sinal da imagem subjacente. Ele passa por três filtros com as propriedades desejadas: o filtro médio (median-filter), o knn (k-nearest-neighbor filter) e o snn (Symmetric nearest neighbor filter).

Fase de Inicialização

Na fase de inicialização regiões homogêneas coloridas no nível 0 das ilhas de sete pixels são detectadas e mapeadas para os elementos de nível 0 (zero) das ilhas de sete pixels são detectadas e mapeadas para os elementos códigos iniciais. Assim um elemento de código inicial consiste nos seus pixels de nível 0 das ilhas que são vizinhos e cuja distância das cores mútuas ficam abaixo a um certo limiar. Os pixels são ligados no mesmo caminho a um esquema de crescimento de região de ligação simples. Um elemento de código é uma descrição da estrutura de dados de regiões coloridas como uma ilha.

A figura abaixo ilustra este processo: Uma ilha por onde passa uma borda na imagem resulta em dois elemntos de código que descrevem duas pequenas regiões coloridas dentro desta ilha. Assim, um elemento de código de nível 0 descreve uma pequena região colorida dentro de uma ilha de nível 0. Observe que esta é uma operação puramente local e o processamento pode ser realizado em parelelo, de forma completamente independente sobre todas as ilhas.

Na fase de ligação os elementos de código do nível n são ligados a novos elementos de código do nível n + 1 para cada conjunto de sete ilhas-irmãs da estrutura hexagonal.  Ilhas-irmãs são ilhas que se encontram imediatamente abaixo de uma ilha no nível superior.

São conectados elementos de cor com coloração similar de acordo com a métrica de similaridade que houver sido definida. CSC permite o uso de métricas customizadas. Esse processo de ligação ocorre de forma independente para cada ilha do nível n + 1 e pode ser paralelizado. Assim todas as operações de uma ilha podem ser inicializadas independentemente das outras ilhas. Os resultados das segmentações não dependem de outros para executar. Todas as pequenas regiões coloridas da fase de inicialização são crescimento concorrentes de um nível.

Figura 7a. Ligação de elementos de código de cores (regiões) em uma visão abstrata (Priese & Rehrmann, 1993/2003)

Figura 7b. Ligação de elementos de código de cores (regiões) em uma visão hexagonal (v.Wangenheim et.al. 2008)

Dois elementos de código são conectados se eles compartilham uma sub-região comum. No nível 1 isso significa que basta que compartilhem um único pixel, nos níveis subseqüentes o que deve ser compartilhado são elementos de código.  No nível mais alto uma única ilha cobre toda a imagem .

O processo de ligação de elementos de código similares cria uma árvore de elementos de código. Um novo eleemnto de código que é criado no nível n é armazenado com ponteiros para os seus subelementos no nível n – 1, a partir dos quais foi formado. Elementos de código que não conseguem mais ser ligados a nenhum outro elemento em um determinado nível, são denominados elementos-raiz e forma a raiz de uma sub-árvore de elementos de código de uma determinada faixa de cor. Assim, uma região em CSC é sempre representada por uma árvore.  Quanto maior ela for, tão mais alto se encontrará a sua raiz na estrutura de ilhas.  A raiz contém informação acerca do tamanho, localização e cor média da região.

Fase de Partição

Um bom algoritmo de segmentação deve usar as informações locais e as globais. Isso resolve o problema para adicionar cores similares checadas entre elementos de código conectados em todos os níveis de ligação. Se a distância da cor está acima de um certo limiar de dois códigos de elementos não serão ligados embora eles sejam conectados por uma cadeia de cores similares de pixels.

Figura 8.

Figura 9. A divisão de dois elementos de codificação de imagem c1 e c2. Ambos compartilham um sub-elemento s.

Se a distância global (médias) entre as cores de c1 e c2 é muito grande, eles não precisam ser ligados, embora todas as suas sub-regiões no nível n – 1 sejam localmente homogêneas.

Exemplos de CSC (gerados com a implementação original para SunOS 4.0.1 – 1996)

Cenas de Trânsito em Florianópolis segmentadas com Color Structure Code.

Aplicação de CSC em Segmentação de Ressonância Magnética [4]

CSC é flexível e pode ser estendido e ampliado de diferentres maneiras. Uma delas é dada pelolo desenho abaixo, descrito em detalhes em [4].

Resultados:

Comparação de Resultados utilizando RGB e Distância de Mahalanobis

CSC pode ser estendido através do Weighted Color Structure Code (WCSC):

         Imagem Original             Padrão para Mahalanobis       CSC original(melhor resultado)       WCSC (melhor resultado)

Links

Referências Bibliográficas do Texto

1. Rehrmann, V. ,Priese, L.: Fast and Robust Segmentation of Natural Color Scenes. ACCV (1), 1998: 598-606 [ResearchGate].
2. L. Priese, V. Rehrmann. A Fast Hybrid Color Segmentation Method. In: S.J. Pöppl and H.Handels, editors, Mustererkennung 1993, pages 297-304. Springer Verlag, 1993. 15. DAGM-Symposium, Lübeck.27-29.Sept. 1993 [ResearchGate].
3. Hartmann, G. Recognition of hierarchically encoded images by technical recognition of hierarchically encoded images by technical and biological systems. Biological Cybernetics, v. 57, n. 1–2, p. 73–84, August 1987.
4. Schmitt, Frank; Priese, Lutz (2008): Recent advances in 3D-CSC based MR brain image segmentation. In: Reinhardt, Joseph M.; Pluim, Josien P. W.: Medical Imaging 2008: Image Processing. Bd. 6914.
5. Schmitt, Frank; Priese, Lutz (2009): Sky detection in CSC-segmented color images. In: Fourth International Conference on Computer Vision Theory and Applications (VISAPP) 2009, Lisboa, Portugal. Bd. 2. S. 101-106.

Internos

1. Trabalho de CSC de Eros Comunello (1998)
2. Página do Weighted Color Structure Code (WCSC) no LAPIX
3. von Wangenheim, Aldo; Bertoldi, Rafael Floriani ; Abdala, D. D. ; Richter, Michael M. ; Priese, L. ; Schmitt, F. . Fast Two-Step Segmentation of Natural Color Scenes using Hierarchical Region-Growing and a Color-Gradient Network. Journal of the Brazilian Computer Society (Impresso), v. 14, p. 29-40, 2008  [ResearchGate].
4. Carvalho, L. E. ; Mantelli Neto, S. L. ; von Wangenheim, A. ; Sobieranski, A. C. ; Coser, L. ; Comunello, E. . Hybrid Color Segmentation Method Using a Customized Nonlinear Similarity Function. International Journal of Image and Graphics, v. 14, p. 1450005-145025, 2014 [ResearchGate].

Externos

1. Lutz Priese, Patrick Sturm. Introduction to the Color Structure Code and its Implementation. Relatório Técnico. March 24, 2003
2. Códigos de Split&Merge e CSC da Universidade de Koblenz
3. Manual do CSC na Universidade de Koblenz
4. Pàgina de Pesquisa do CSC na Universidade de Koblenz
5. Página da GUI para CSC 3D e 2D