Medidas de tendência central (média, mediana, moda, etc.) estão entre os primeiros conceitos que aprendemos em qualquer curso introdutório de estatística. Esses conceitos vêm acompanhados de diversos exemplos como: qual é a média de altura da turma (ou idade, ou coisas mais delicadas como peso), ou a média/mediana dos salários de uma determinada empresa. Esses conceitos são fundamentais para entendermos melhor o mundo ao nosso redor. Neste post, entretanto, o objetivo não é explicar nem os conceitos, nem por que são importantes, mas responder à pergunta: mas e a computação nisso?
Uma aplicação bastante direta é calcular o tempo médio de execução de um determinado algoritmo, o que pode nos ajudar a assimilar os conceitos de notação assintótica (por exemplo, O-grande - O(1), O(N), O(NlogN)), por exemplo. Se você não tem ideia do que significam esses conceitos, não se preocupe. Por ora, gostaria de focar em outra aplicação: processamento de imagens.
Imagens digitais
Antes de apresentar a aplicação propriamente dita, vamos fazer uma breve revisão do que é uma imagem digital. A forma mais comum de se representar uma imagem em um computador é como uma tabela, ou matriz, de pixels. Um pixel é simplesmente uma representação de uma determinada cor, em uma imagem colorida, ou intensidade, em uma imagem em níveis de cinza (popularmente chamadas também de imagem em preto e branco). Por questão de simplicidade vamos trabalhar somente com imagens em níveis de cinza. A maioria das imagens em níveis de cinza possui 256 tons (não, não são 50) variando do preto (0) ao branco (255).
Uma imagem em níveis de cinza é então simplesmente uma tabela de números entre 0 e 255:
Médias em imagens
Voltando às medidas de tendência central. Como a imagem é simplesmente uma tabela de números é possível calcular a sua média. Por exemplo, a média da imagem acima é 91,52. Não diz muito, certo? Ao invés disso, vamos considerar somente uma linha:
Se substituirmos cada pixel pela média de seus vizinhos (os pixels à esquerda e à direita, quando existirem) e o próprio pixel obtemos o seguinte resultado:
A média nesse caso fez com que a diferença entre pixels adjacentes fosse suavizada! O resultado visual é uma suavização das bordas, deixando a imagem mais borrada. Vejamos o que acontece se considerarmos dessa vez 5 pixels na média (2 pixels à esquerda, 2 pixels à direita e o próprio pixel):
O processo de aquisição e armazenamento de imagens não é perfeito. Assim, é comum a ocorrência de ruído na imagem. Vamos considerar um caso simples, com uma linha de pixels pretos. Vamos adicionar ruído aleatoriamente: um dos pixels que deveria ser preto foi registrado como branco.
Vamos repetir o processo de calcular a média para os 5 pixels vizinhos:
Como a maior parte dos pixels é da mesma cor, a média tende a se aproximar à cor da maioria, no caso o preto. Assim, a intensidade do pixel branco é reduzida. Em outras palavras, esse processo pode ser utilizado para reduzir o ruído de uma imagem. Um efeito colateral é que o ruído acaba se “diluindo”, afetando os pixels vizinhos, inicialmente na cor certa. Esse processo de substituição de um pixel pela média dos seus vizinhos é conhecido como filtro de média.
Vamos adicionar uma dimensão extra. Agora a média será calculada entre os todos os vizinhos de cada pixel, ou seja, ao invés de considerar somente os pixels dos lados agora também consideraremos os pixels acima, abaixo e nas diagonais.
Na imagem mostrada acima o pixel 35 será substituído pela média dos seus vizinhos, ou seja, (23 + 233 + 103 + 134 + 35 + 65 + 240 + 123 + 54)/9 = 112,22. O efeito será exatamente o mesmo observado em uma única linha. Vamos voltar à nossa imagem original e adicionar ruído aleatório (pixels brancos e pretos em posições aleatórias - ou ruído sal e pimenta).
Aplicando então o filtro de média usando os 8 vizinhos e o próprio pixel obtemos o seguinte resultado:
O conjunto de pixels considerados na média é chamado de janela. A quantidade de pixels na janela pode ser maior do que 9. Não há limites para o tamanho e nem para a forma da janela. A seguinte imagem mostra a aplicação de um filtro de média com 49 pixels na janela (um quadrado de 7 por 7 pixels).
Inclusive, no caso extremo consideramos uma janela bem grande (maior do que a própria imagem). Assim cada pixel será substituído pela média dos pixels da imagem, que na imagem com ruído é 91,67, produzindo a seguinte imagem com um único tom de cinza:
Medianas em imagens
O que aconteceria se simplesmente trocássemos a média por uma mediana? Vamos primeiro considerar uma propriedade das medianas. A mediana do conjunto {0, 1, 100} é 1. Não importa o quão grande seja o último número e nem o quão pequeno seja o primeiro número. Da mesma forma, o número 255 não faz diferença no cálculo da mediana do conjunto {0, 0, 0, 0, 255}, que continuará sendo 0, independente do que colocarmos no lugar do 255. Isso não é verdade no caso da média. Assim, no exemplo da linha com um pixel branco o resultado da aplicação do filtro de mediana seria (usando uma janela de tamanho 5 - dois à esquerda e dois à direita):
Vejamos o que acontece com a linha metade preta e metade branca:
Esse exemplo mostra uma propriedade interessante dos filtros de mediana. Enquanto o filtro de média borra a imagem inteira, suavizando as bordas, o filtro de mediana preserva as bordas. Vejamos o que acontece ao aplicarmos o filtro de mediana na imagem com ruído (janela de 3 por 3 pixels):
A desvantagem do uso de filtros de mediana ao invés de média é a sua maior complexidade computacional. Enquanto o cálculo da média é linear (O(N)) no número de pixels (basta somar todos os valores e dividir pela quantidade), o cálculo da mediana consome O(NlogN) (é necessário ordenar os valores dos pixels e devolver o central).
Outra explicação para o efeito de filtros de média em uma imagem utiliza a transformada de Fourier. Acho essa explicação particularmente bonita, mas deixo ela para algum post futuro.