Segmentação I
Paulo Sérgio Rodrigues
PEL205
Conceito Formal de
Segmentação de Imagens
Aristóteles (384-322 a.C.), em um tratado sobre os sentidos humanos,
definiu o que seria a diferença entre Sensação e Razão.
Segundo o Filósofo, sensação é o processo de captura de sinais
externos através de órgãos sensitivos de um ser.
Ao generalizar sinais externos, órgãos sensitivos e ser, Aristóteles
define a sensação como um processo inerente a qualquer ser vivo.
Conceito Formal de
Segmentação de Imagens
Por outro lado, define razão como o processo de interpretar o sinal
sensitivo como tendo alguma finalidade dentro de um contexto:
“.. Um Leão percebe uma Gazela correndo mas não reconhece que
ela está correndo ...”
Assim, podemos definir o processo de Segmentação como sendo
simplesmente a idéia de percepção de elementos em uma cena.
Diferença entre Segmentação e Reconhecimento
Por outro lado, o processo de reconhecimento é o processo de
interpretação dos elementos percebidos pelos órgãos sensitivos.
Assim, fica bem clara a diferença ente segmentação e reconhecimento
de imagens, que também podem ser chamadas de detecção e análise.
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Diferença entre Segmentação e Reconhecimento
A interpretação, no entanto, depende do contexto, da base de
conhecimento e conseqüentemente, do observador
Segmentação de Imagens
Segmentação de Imagens
Segmentação de Imagens
Segmentação de Imagens
Segmentação de Imagens
Segmentação Baseada em Histograma
Segmentação de Imagens
Segmentação de Imagens
117
93
147
127 169 185
81 116 145 178
Técnicas de Segmentação
• Limiarização Interativa (AJUSTE MANUAL)
• Limiarização Iterativa
• Clusterizadores
• Baseada em Entropia
• Baseada em Características Locais
• Movimento
• Modelos Deformáveis
Limiarização Iterativa
Algoritmo Iterativo para Determinação do Limiar
Entrada: Imagem monocromática I;
Saída: Limiar T de binarização;
1 - Inicialize o limiar T como a média das intensidades;
2 - Binarize a Imagem de Entrada I usando o limiar T;
3 - Calcule o novo limiar como:
1 n A 1 m B
Ti   T j

n i 1
m j 1
Tn 
2
4 = Se Tn = T fim,
caso contrário faça T = Tn e volte ao passo 2;
Técnicas de Segmentação por
Clusterização
• K-Means
• Crescimento de região
• Self Organize Maps
K-means Clustering Segmentation
Dado um Conjunto de n pontos no espaço ddimensional em um inteiro k
Queremos encontrar um conjunto de k pontos
no espaço d-dimensional que minimiza a
distância media quadrática de csada ponto para
seu centro mais próximo.
Não existe algoritmo polinomial para esse
problema
“A Local Search Approximation Algorithm for k-Means Clustering” by Kanungo et. al
K-means Algorithm
 O KM converge para
uma solução local
ótima.
Data Points
Optimal
Centers
 Mas pode convergir
para uma solução
arbitrária ruim
 Por que ?
Heuristic
Centers
K=3
K-means Algorithm
Formalmente ..
K-means Algorithm
1 – Escolha k pontos iniciais aleatoriamente
2 – Clusterize os dados usando uma distância qualquer (a
mais usada é a distância euclidiana)
3 – Compute novos centros para cada cluster usando
apenas pontos dentro de cada cluster
4 – Re-compute todos os dados usando os novos centros
(esse passo pode provocar mudança de cluster de um ponto)
5 – Repita os passos 3 e 4 até que nenhum ponto no
passo quatro tenha mudado de cluster ou outro
critério de convergência.
From “Data Analysis Tools for DNA Microarrays” by Sorin Draghici
Exemplo para k=2
1. Escolha k=2
2. Clusterize os
pontos em torno
de K=2
controides
K-means para k=2
3. Recalcule os
centroides
4. Redistribua os
pontos ao pelos
dois clusters,
considerando os
novos centroides
K-means para k=2
3. Recalcule os
centroides
4. Redistribua os
pontos ao pelos
dois clusters,
considerando os
novos centroides
K-means para k=2
5.
Repita os dois ultimos passos
até que nenhum ponto mude
de cluster
Características do k-means
Selecionar aleatoriamente os pontos na fase
inicial gera as seguinte propriedades
 Não-Determinismo
 Pode produzir clusters vazios
Uma solução é escolher os centros
aleatoriamente a partir de padrões conhecidos
From “Data Analysis Tools for DNA Microarrays” by Sorin Draghici
Complexidade
 O Algoritmo é linear no númeor de
pontos da base
Pode-se mostrar que o tempo de
execução é da ordem de cN
c não depende de N, mas depende muito do
número de clusters, k
 Possui baixa complexidade computacional
 É muito rápido
Exemplos
Exemplos
Estudo do K-Means
Estudo do K-Means
Estudo do K-Means
Se somente as amplitudes e os desvios-padrões forem iguais?
Estudo do K-Means
Se somente as amplitudes e os desvios-padrões forem iguais?
Estudo do K-Means
Se somente as medias fixas e os desvios-padrões forem iguais?
Estudo do K-Means
Se somente as medias fixas e os desvios-padrões forem iguais?
Estudo do K-Means
Se somente as medias fixas e os desvios-padrões forem iguais?
Estudo do K-Means
Se somente as medias fixas e amplitudes iguais?
Estudo do K-Means
Se somente as medias fixas e amplitudes iguais?
Estudo do K-Means
Se somente as medias fixas e amplitudes iguais?
Estudo do K-Means
Transformando uma Equação em Imagem
Estudo do K-Means
Transformando uma Equação em Imagem
Métodos de Segmentação Menos Sensíveis aos
parâmetros de iluminação da distribuição
Mátodos Baseados em Entropia
Entropia Tradicional de Boltzmann, Gibbs e
Shannon
Entropia Não-Extensiva de Tsallis
Segmentação de Imagens
Crescimento de Região
8
12
6
12
8
12
6
14
6
12
8
12
6
16
6
14
6
12
8
12
6
14
6
12
8
12
4
14
6
14
6
12
8
12
4
16
4
14
6
14
6
12
8
12
6
4
18
16
4
14
6
14
6
12
8
12
4
16
4
14
6
14
6
12
8
12
4
14
6
14
6
12
8
12
2
14
4
14
6
14
6
12
8
12
2
16
2
14
4
14
6
14
6
12
8
12
2
14
4
14
6
14
6
12
8
12
4
14
6
14
6
12
8
12
6
14
6
12
8
12
6
12
8
12
8
12
8
10
8
12
8
12
10
8
8
12
8
12
12
6
8
12
10
6
12
6
8
12
12
6
8
12
8
12
14
6
8
12
14
4
14
6
8
12
14
6
8
12
16
4
14
6
8
12
16
2
16
4
14
6
8
12
14
2
16
2
16
4
14
6
8
12
16
2
16
4
14
6
8
12
16
0
16
2
16
4
14
6
8
12
14
0
16
0
16
2
16
4
14
6
8
12
16
0
16
2
16
4
14
6
8
12
16
2
16
4
14
6
8
12
18
0
16
2
16
4
14
6
8
12
16
2
16
4
14
6
8
12
20
2
16
2
16
4
14
6
8
12
20
0
20
2
16
2
16
4
14
6
8
12
20
2
16
2
16
4
14
6
8
12
16
2
16
4
14
6
8
12
20
4
16
2
16
4
14
6
8
12
16
2
16
4
14
6
8
12
18
6
16
2
16
4
14
6
8
12
16
2
16
4
14
6
8
12
16
4
14
6
8
12
14
6
8
12
8
12