Finalmente tomei coragem e escrevi. Esta é uma tentativa de explicar o Mean Shift. Venho adiando isso há tempos porque é um tema complexo, mas na semana passada escrevi um tutorial, e o leitor JanKees Poel deu a cutucada que faltava… (Obrigada!)

Fundamentos

O trabalho original, de Fukunaga e Hostetler em 1975 não está disponível on-line. Há outros trabalhos científicos, com explicações matemáticas completas, mas não eles não deixam nada fácil de entender, então vou partir de uma definição simples e depois explicar melhor.

Definição da wikipedia:

Mean shift is a procedure for locating the maxima of a density function given discrete data sampled from that function.

:Mean shift é um processo para localizar a máxima densidade de uma função, dada uma amostra discreta desta.
Eu trocaria máxima por moda, nesta definição, mas por enquanto está bom.

Tradução corrigida pelo Juca (muito obrigada!):

Mean shift é um procedimento para localizar OS MÁXIMOS de um função densidade a partir de dados discretos amostrados desta função.
Saindo do inglês para a matemática, observe que a idéia é mesmo uma busca NO PLURAL por todos os máximos existentes na função densidade de pontos no espaço de características (clusters of sampled data).

Mais simples

Procurando no meu material de pesquisa de uns dois anos atrás, achei uma apresentação que fez sucesso na aula porque conseguia explicar isso tudo de uma forma simples e bem visual. Infelizmente ela não estava assinada, e eu não encontrei uma versão on-line para citar aqui, mas me baseei fortemente nela para a animação abaixo (se o autor reconhecer, por favor entre em contato para que eu possa atribuir os devidos créditos).

A animação parte de uma amostra de duas dimensões para facilitar, mas não há um limite de dimensões para este método. Imagine que estes pontos são o gráfico de dispersão de pontos de um conjunto de dados qualquer.

O algoritmo parte de cada ponto (a animação mostra apenas um), delimita uma região em torno dele e calcula o centro de massa. Este é um conceito físico, que se transfere para este exemplo com a média aritmética dos valores de cada variável nos pontos que estão dentro do kernel (representado por um círculo).

Encontrado o centro de massa, ele “move” o centro de sua região para o centro de massa calculado, e calcula o novo centro de massa para o conjunto de dados que agora está dentro do kernel. Encontrado o centro de massa, ele move o centro novamente, e assim segue em passos até que o centro de massa passe a “cair” sempre no mesmo lugar.

Este é um exemplo simples quem tem o objetivo de elucidar o conceito. Ele usa um conjunto de dados em duas dimensões, ou seja, dados descritos por duas variáveis. Mas é possível executar a mesma rotina com um número ilimitado de dimensões.

Além disso, o exemplo tem apenas uma moda, ou seja, apenas uma região em que se concentram mais pontos, que é a região para onde vão convergir todos os pontos. Em imagens reais há várias modas (e não apenas uma máxima), e cada moda “atrai” uma parte dos pontos para si.

Uso em segmentação de imagens

Como vimos no artigo sobre cores, imagens podem ter três ou mais dimensões. Assim, o mean-shift realizado em uma imagem RGB usa o processo descrito acima em um conjunto de dados tridimensional, formado pelas intensidades dos pixels nos três canais de cor. Veja os gráficos no link sobre cores para entender como isso fica.

Além disso, a maioria dos trabalhos que li entendem que o componente espacial da imagem não deve ser negligenciado – o que acontece quando usa-se só as 3 dimensões de cor.

Comaniciu propõe que depois de realizado todo o processo com os canais de cor, despreze-se as regiões de tamanhos muito pequenos. Isso foi mais ou menos o que eu fiz com o filtro de mediana no tutorial do Mean-shift, na semana passada.

Já a implementação usada no plugin do ImageJ que usei neste mesmo artigo ,adiciona as duas dimensões espaciais ao processo, usando um kernel para as dimensões de cor (Color Distance, no diálogo do plugin) e outro diferente para as dimensões espaciais (Spacial Radius). Alterar o tamanho do Color Distance tem o efeito que se pode esperar olhando a animação acima – mais pontos convergem para a mesma moda. Já o Spacial Radius, quando usado em um tamanho próximo ao tamanho das estruturas que se procura encontrar na imagem, força a atração de pontos a modas mais próximas espacialmente, formando regiões (obs: esta é a minha opinião, já que o autor da implementação não documentou duas decisões).

Este mesmo plugin também seque uma das tendências das publicações: não usa a imagem no espaço de cor RGB, e sim no YIQ. Isto melhora os resultados em muitas situações, embora, como tudo em processamento de imagens, não tenha o mesmo resultado para todas as aplicações.

Vou parar por aqui…

porque já ficou longo demais. Se tiver perguntas, por favor use a área de comentários, quem sabe respondo em um post “parte II”…

Até mais!