Explicação da segmentação de imagens usando o deslocamento médio

107

Alguém poderia me ajudar a entender como a segmentação Mean Shift realmente funciona?

Aqui está uma matriz 8x8 que acabei de criar

  103  103  103  103  103  103  106  104   
  103  147  147  153  147  156  153  104   
  107  153  153  153  153  153  153  107   
  103  153  147  96   98   153  153  104   
  107  156  153  97   96   147  153  107   
  103  153  153  147  156  153  153  101   
  103  156  153  147  147  153  153  104   
  103  103  107  104  103  106  103  107

Usando a matriz acima, é possível explicar como a segmentação do deslocamento médio separaria os 3 níveis diferentes de números?

Sharpie
fonte
Três níveis? Vejo números em torno de 100 e 150.
John
2
Bem, como é uma segmentação, pensei que os números do meio estariam muito longe dos números da borda para serem incluídos nessa seção do limite. É por isso que eu disse 3. Posso estar errado, pois não entendo realmente como funciona esse tipo de segmentação.
Sharpie
Oh ... talvez estejamos considerando níveis com significados diferentes. Tudo bom. :)
João
1
Gosto da resposta aceita, mas acho que não mostra o quadro todo. IMO, este pdf explica melhor a segmentação de deslocamento médio (usar um espaço de dimensão maior como exemplo é melhor do que 2d, eu acho). eecs.umich.edu/vision/teaching/EECS442_2012/lectures/…
Helin Wang

Respostas:

204

O básico primeiro:

A segmentação por deslocamento médio é uma técnica de homogeneização local muito útil para amortecer diferenças de sombreamento ou tonalidade em objetos localizados. Um exemplo é melhor do que muitas palavras:

insira a descrição da imagem aqui

Ação: substitui cada pixel pela média dos pixels em uma vizinhança de alcance r e cujo valor está dentro de uma distância d.

A mudança média leva geralmente 3 entradas:

  1. Uma função de distância para medir distâncias entre pixels. Normalmente a distância euclidiana, mas qualquer outra função de distância bem definida pode ser usada. A distância de Manhattan é outra escolha útil às vezes.
  2. Um raio. Todos os pixels dentro deste raio (medidos de acordo com a distância acima) serão contabilizados para o cálculo.
  3. Uma diferença de valor. De todos os pixels dentro do raio r, tomaremos apenas aqueles cujos valores estão dentro desta diferença para calcular a média

Observe que o algoritmo não está bem definido nas bordas, portanto, diferentes implementações fornecerão resultados diferentes lá.

NÃO discutirei os detalhes matemáticos sangrentos aqui, pois eles são impossíveis de mostrar sem a notação matemática adequada, não disponível no StackOverflow, e também porque podem ser encontrados em boas fontes em outros lugares .

Vejamos o centro de sua matriz:

153  153  153  153 
147  96   98   153 
153  97   96   147   
153  153  147  156  

Com opções razoáveis ​​de raio e distância, os quatro pixels centrais obterão o valor de 97 (sua média) e serão diferentes dos pixels adjacentes.

Vamos calcular no Mathematica . Em vez de mostrar os números reais, exibiremos um código de cores, para que seja mais fácil entender o que está acontecendo:

O código de cores para sua matriz é:

insira a descrição da imagem aqui

Em seguida, tomamos uma mudança média razoável:

MeanShiftFilter[a, 3, 3]

E nós temos:

insira a descrição da imagem aqui

Onde todos os elementos centrais são iguais (a 97, BTW).

Você pode iterar várias vezes com Mean Shift, tentando obter uma coloração mais homogênea. Depois de algumas iterações, você chega a uma configuração não isotrópica estável:

insira a descrição da imagem aqui

Neste momento, deve ficar claro que você não pode selecionar quantas "cores" deseja obter após aplicar o deslocamento médio. Então, vamos mostrar como fazer, porque essa é a segunda parte da sua pergunta.

O que você precisa para ser capaz de definir o número de clusters de saída com antecedência é algo como cluster de Kmeans .

Funciona assim para sua matriz:

b = ClusteringComponents[a, 3]

{{1, 1, 1, 1, 1, 1, 1, 1}, 
 {1, 2, 2, 3, 2, 3, 3, 1}, 
 {1, 3, 3, 3, 3, 3, 3, 1}, 
 {1, 3, 2, 1, 1, 3, 3, 1}, 
 {1, 3, 3, 1, 1, 2, 3, 1}, 
 {1, 3, 3, 2, 3, 3, 3, 1}, 
 {1, 3, 3, 2, 2, 3, 3, 1}, 
 {1, 1, 1, 1, 1, 1, 1, 1}}  

Ou:

insira a descrição da imagem aqui

Que é muito semelhante ao nosso resultado anterior, mas como você pode ver, agora temos apenas três níveis de saída.

HTH!

Dr. belisarius
fonte
Existe uma implementação Matlab de mudança média para imagem?
Kaushik Acharya,
2
@KaushikAcharya Veja shawnlankton.com/2007/11/mean-shift-segmentation-in-matlab
Dr. belisarius
164

Uma segmentação de deslocamento médio funciona mais ou menos assim:

Os dados da imagem são convertidos em espaço de recurso espaço de recurso

No seu caso, tudo que você tem são valores de intensidade, então o espaço de recursos será apenas unidimensional. (Você pode calcular alguns recursos de textura, por exemplo, e então seu espaço de recurso seria bidimensional - e você estaria segmentando com base na intensidade e textura)

As janelas de pesquisa são distribuídas no espaço de recursos insira a descrição da imagem aqui

O número de janelas, tamanho da janela e locais iniciais são arbitrários para este exemplo - algo que pode ser ajustado dependendo de aplicativos específicos

Iterações de deslocamento médio:

1.) Os MEANs das amostras de dados em cada janela são calculados insira a descrição da imagem aqui

2.) As janelas são deslocadas para os locais iguais aos seus meios calculados anteriormente insira a descrição da imagem aqui

As etapas 1.) e 2.) são repetidas até a convergência, ou seja, todas as janelas se fixaram nas localizações finais insira a descrição da imagem aqui

As janelas que terminam nos mesmos locais são mescladas insira a descrição da imagem aqui

Os dados são agrupados de acordo com as travessias de janela insira a descrição da imagem aqui

... por exemplo, todos os dados que foram percorridos por janelas que terminaram, digamos, no local “2”, formarão um cluster associado a esse local.

Portanto, essa segmentação (coincidentemente) produzirá três grupos. Visualizar esses grupos no formato de imagem original pode parecer algo como a última imagem na resposta de belisarius . A escolha de tamanhos de janela e locais iniciais diferentes pode produzir resultados diferentes.

mlai
fonte
o espaço de recursos não pode ser tridimensional, levando em consideração a posição de cada pixel?
Helin Wang,
@HelinWang Sim, poderia.
mlai
Eu entendo como a janela está posicionada em um espaço de recurso 1D, mas não vejo como sua explicação pode ser aplicada para significar algoritmos de deslocamento que incluem uma distância de busca espacial (por exemplo, em pixels) e distância espectral (diferença de valor), por exemplo como na resposta do Dr. belisarius. Você poderia esclarecer isso?
Lennert de
@Lennert Se entendi sua pergunta corretamente, essencialmente o que você faria é adicionar as localizações dos pixels (x, y) como recursos, ou adicionar outros recursos baseados em localização, ao espaço de agrupamento. Parece que a resposta de Belisarius faz referência a uma implementação específica no Mathematica que pode fazer algo um pouco mais sofisticado. Isso ajuda?
mlai
1
@Lennert Sim, acho que entendeu. Posso entender por que você achou minha resposta confusa. Eu meio que desenhei minhas 'janelas' como bidimensionais, mas na verdade eu estava tentando representar o agrupamento apenas nos valores espectrais de uma dimensão. Seria muito legal visualizar o cluster de deslocamento médio em um espaço tridimensional com um desenho ou animação (talvez um dia desses, se eu tiver tempo)
mlai