Exercício 06
Cálculo de dimensão fractal utilizando box counting
Introdução
O objetivo deste exercício é implementar a extração de dimensão fractal de
formas através dos métodos de box counting e derivação por Fourier. Em algumas
aplicações, a dimensão fractal pode ser usada como característica para se fazer
a classificação de formas.
O método de box counting, em linhas gerais, consiste em dividir a imagem em
quadrados e contar quantos quadrados contêm pixels da forma a ser analisada.
Aumenta-se progressivamente o tamanho dos quadrados e repete-se a contagem.
Assim, produz-se um gráfico relacionando log(L) com log(N(L)), onde L é o
tamanho do lado dos quadrados e N(L) é o número de quadrados de lado L que
contêm algum pixel da forma. O gráfico é bastante semelhante a uma reta, sendo
que a dimensão fractal pode ser obtida através da derivada da reta.
Tal derivada pode ser feita no domínio da freqüência após a utilização da
transformada de Fourier sobre o sinal que representa o gráfico citado acima,
para converter seus valores do domínio do tempo para valores no domínio da
freqüência. Em seguida faz-se uma multiplicação ponto a ponto com uma reta de
valores j * 2 * pi * f, onde j = sqrt(-1), para obter a derivada. Finalmente,
a transformada inversa de Fourier é aplicada para obtermos os valores no
domínio do tempo.
Método Utilizado
A implementação do algoritmo realizada consiste em realizar a contagem descrita
acima iniciando com um quadrado que cobre a imagem inteira, e dividindo
progressivamente o lado do quadrado por dois.
Tendo então o sinal que representa o gráfico que relaciona log(L) com
log(N(L)), realiza-se a derivação deste sinal no domínio da freqüência. Porém,
a derivada obtida no domínio da freqüência apresenta muitas oscilações. Para
contornar este problema, foi feita uma filtragem gaussiana da derivada antes
de se fazer a FFT inversa, permitindo assim uma estimação mais precisa do valor
da derivada.
O programa foi desenvolvido usando a linguagem C. Como no exercício 3,
foi utilizada a biblioteca FFTW versão
2.1.3 para o cálculo da FFT.
O código do EP com as imagens de teste em formato PGM pode ser obtido
aqui.
Resultados
Para testar o programa, utilizei as imagens da seção "practice problems" da
página http://classes.yale.edu/fractals/FracAndDim/BoxDim/BoxDim.html.
| Imagem |
Valor Obtido |
Valor Esperado |
 |
1.55427 |
1.46497 |
 |
1.4533 |
1.26186 |
 |
1.46716 |
1.26186 |
 |
1.637 |
1.63093 |
Conclusão
Nos testes realizados, o programa mostrou-se capaz de obter a dimensão fractal
aproximada dos fractais presentes nas imagens. Como conseqüência da
discretização dos sinais inerente à representação destes no computador,
problemas numéricos interferem no resultado. A utilização da filtragem
Gaussiana sobre a derivada obtida no domínio da freqüência permitiu amenizar
parte dos efeitos decorrentes da discretização, mas mesmo assim pode-se notar
uma diferença entre os valores obtidos e os esperados. Outro fator que
influencia no resultado é o fato de em geral termos poucos pontos no gráfico
gerado pelo box counting, o que faz com que grande parte do sinal da derivada
seja afetado por grandes oscilações devido ao efeito de periodicidade da
Discrete Fourier Transform (o final da reta "concatena-se" com o começo da
reta produzindo uma grande descontinuidade).
Bibliografia
R. M. Cesar Jr e L. F. Costa. Shape analysis and classification: Theory and Practice. CRC Press, 2001.
Daniel André Vaquero
daniel at linux.ime.usp.br
Sat, 22 Nov 2003 23:50:21 -0200