4. AKTUELLE EKSAMENSSETT
4.9 EKSAMEN I OAL151 IT SOM LEDELSESVERKTØY, DESEMBER 2008
Este cap´ıtulo apresenta a generaliza¸c˜ao do conceito de dimens˜ao fractal. Inicialmente, s˜ao apresentadas as limita¸c˜oes do uso direto da dimens˜ao e a motiva¸c˜ao para o desenvolvimento de alternativas para a an´alise de imagens por modelagem fractal. Em seguida, s˜ao mostra- das abordagens para a extra¸c˜ao de um conjunto de medidas do objeto analisado a partir da geometria fractal, no lugar do valor ´unico da dimens˜ao.
4.1
Dimens˜ao Escalar versus Medidas Vetoriais
Nas ´ultimas d´ecadas, sobretudo ap´os o trabalho de Mandelbrot (1), que formalizou a geo- metria fractal, a literatura vem apresentando um n´umero crescente de trabalhos que empregam conceitos desta geometria nos mais variados campos da ciˆencia (2, 67–74). Uma grande parte destas aplica¸c˜oes faz uso da dimens˜ao fractal pura e simples, geralmente associada a outras medidas cl´assicas, para caracterizar e identificar os objetos de interesse (texturas, formas, contornos, curvas de fun¸c˜oes, etc.). Os bons resultados obtidos pelo uso da dimens˜ao s˜ao explicados, do ponto de vista te´orico, pela pr´opria defini¸c˜ao desta m´etrica, que caracteriza o n´ıvel de irregularidade do objeto ou ainda seu grau de ocupa¸c˜ao do espa¸co ao seu redor. Essas s˜ao propriedades que determinam por si o aspecto geral do objeto, que ´e usado pelo pr´oprio sistema visual humano na identifica¸c˜ao daquela estrutura. Assim, ´e natural que esta abordagem apresente resultados interessantes quando empregada em um sistema autom´atico como o de vis˜ao computacional.
Ocorre, entretanto, que a dimens˜ao fractal por si s´o ´e apenas um valor real e, em cen´arios mais complexos, com maior n´umero de objetos analisados e na presen¸ca de situa¸c˜oes adversas, como ru´ıdos e objetos transformados geometricamente, a dimens˜ao n˜ao ´e suficiente, sendo necess´ario ent˜ao o desenvolvimento de metodologias que permitam a extra¸c˜ao de uma in-
forma¸c˜ao mais rica acerca do objeto de interesse. De fato, n˜ao ´e raro que se encontrem dois objetos de topologia e aspecto totalmente distintos, mas com a mesma dimens˜ao. A Figura 4.1 mostra duas formas distintas com a mesma dimens˜ao, enquanto a Figura 4.2 exibe duas texturas com o mesmo comportamento.
DF = 1.672
DF = 1.672
Figura 4.1 – Duas formas de aspecto totalmente distinto, mas com a mesma dimens˜ao fractal.
DF = 1.327
DF = 1.327
Figura 4.2 – Duas texturas de aspecto diferente, mas com a mesma dimens˜ao fractal.
Ainda um outro problema, que ´e frequentemente encontrado na an´alise de imagens pela dimens˜ao fractal, ´e que os objetos do mundo real representados nestas imagens n˜ao apresentam
4.1 Dimens˜ao Escalar versus Medidas Vetoriais 75
uma ´unica medida global da dimens˜ao. Em vez disso, este valor varia, em algumas situa¸c˜oes severamente, dependendo do intervalo de escalas no qual a medida ´e tomada. Este problema ocorre tanto com formas bimensionais quanto com texturas, representadas em imagens de superf´ıcies de intensidade. A Figura 4.3 ilustra tal fato para formas e a Figura 4.4 mostra o mesmo fenˆomeno em texturas.
0 0.2 0.4 0.6 0.8 1 12 12.5 13 13.5 14 14.5 log(r) log(A(r))
Figura 4.3– Curva de fractalidade de uma forma exibindo a existˆencia de diferentes valores da dimens˜ao fractal dependendo do intervalo de escala tomado.
1.840 1.86 1.88 1.9 1.92 1.94 1.96 1.98 5 10 15 20 25 30 log(V(r)) log(r)
Figura 4.4– Curva de fractalidade de uma textura exibindo a existˆencia de diferentes valores da dimens˜ao fractal dependendo do intervalo de escala tomado.
Partindo destas constata¸c˜oes, a literatura vem propondo ent˜ao novas solu¸c˜oes que per- mitam uma an´alise mais robusta e precisa baseada na geometria fractal. Neste sentido, a
primeira t´ecnica mais conhecida a ser proposta ´e a teoria de multifractais (18, 75–78).
4.2
Multifractais
Nesta abordagem, incialmente aplica-se algum tipo de categoriza¸c˜ao pr´e-definida, que atribui uma classe a cada pixel da imagem original. Em seguida, calcula-se a dimens˜ao fractal de cada conjunto de pontos que perten¸cam `a mesma classe na imagem. Este conjunto de valores de dimens˜ao fractal ´e chamado ent˜ao de espectro multifractal e comp˜oe o vetor de caracter´ısticas a ser usado para a descri¸c˜ao do objeto representado na imagem.
Na pr´atica, costuma-se fazer a categoriza¸c˜ao por meio de uma fun¸c˜ao de densidade, que garante maior robustez, por exemplo, a ru´ıdos e varia¸c˜oes de ilumina¸c˜ao. Considere-se ent˜ao µ uma medida de Borel regular finita (51) em ℜ2 e B(x, r) uma bola com centro em x ∈ ℜ2
e raio r > 0, tal que:
µ(x, r) = krD(x), (4.2.1)
sendo k uma constante real. Define-se ent˜ao a fun¸c˜ao de densidade D(x) por: D(x) = lim
r→0
log µ(B(x, r))
log r . (4.2.2)
Assim, a fun¸c˜ao de densidade mede a velocidade de crescimento local da medida µ, que por sua vez corresponde ao grau de uniformidade da imagem naquele ponto. A seguir, s˜ao definidos ent˜ao os conjuntos categ´oricos Eα:
Eα = {x ∈ ℜ2 : D(x) = α}, (4.2.3)
ou seja, Eα ´e o conjunto de pontos x da imagem para os quais a fun¸c˜ao de densidade vale
α. Finalmente, o espectro multifractal f (α) ´e dado pelos valores de dimens˜ao fractal de cada conjunto Eα:
f (α) = dim(Eα) : α ∈ ℜ. (4.2.4)
Entre as fun¸c˜oes de densidade usadas na literatura, pode se citar, por exemplo, a con- volu¸c˜ao com uma fun¸c˜ao gaussiana (78) ou a chamada wavelets leaders (77), que correspon- dem a m´aximos tomados dentro de uma vizinhan¸ca e em determinado intervalo de escalas da transformada wavelet multin´ıvel. A dimens˜ao fractal mais usada na literatura ´e a de Box- counting, embora qualquer outro m´etodo de estimativa possa ser empregado.
4.3 Dimens˜ao Fractal Multiescala 77
4.3
Dimens˜ao Fractal Multiescala
Uma alternativa aos multifractais ´e a chamada Dimens˜ao Fractal Multiescala (DFM) (19, 21, 79). Este m´etodo consiste em se aplicar uma transforma¸c˜ao multiescala (espa¸co-escala) `a curva logar´ıtmica da dimens˜ao fractal descrita nas se¸c˜oes anteriores e extrair algumas medidas desta curva transformada para compor o vetor de caracter´ısticas.
Esse tipo de transforma¸c˜ao multiescala ser´a definido posteriormente. Por ora, pode-se considerar que a curva multiescala, como definida em (19), que usa a dimens˜ao de Bouligand- Minkowski em duas dimens˜oes, ´e obtida pela seguinte express˜ao:
DF M = 2 − d(log(A(r)))d(log(r)) ∗ ga, (4.3.1)
em que A(r) ´e a ´area de dilata¸c˜ao de raio r e ga ´e uma fun¸c˜ao Gaussiana com parˆametro de
suaviza¸c˜ao a definido empiricamente.
Por uma quest˜ao de otimiza¸c˜ao computacional, a ´area de dilata¸c˜ao ´e calculada por meio de um m´etodo chamado Transformada Exata da Distˆancia (TED) (55). Esta transforma¸c˜ao atribui, a cada pixel de um objeto de interesse em uma imagem bin´aria, a distˆancia deste pixel ao fundo da imagem (regi˜ao fora do objeto de interesse). Neste caso, usa-se a distˆancia Euclidiana d, que entre dois pixels de coordenadas p = (x, y) e p′ = (x′, y′) ´e dada por:
d(p, p′) = kp − p′k =p(x − x′)2+ (y − y′)2. (4.3.2)
Assim, a ´area de dilata¸c˜ao A(r) corresponde ao n´umero de pontos para os quais a transformada da distˆancia apresente valor menor ou igual a r.
A Gaussiana tem o papel de suavizar a derivada, que naturalmente real¸ca qualquer tipo de ru´ıdo eventualmente presente na curva logar´ıtmica. A derivada num´erica empregada neste caso ainda possui um s´erio problema, que ´e seu car´ater fortemente local, que pode gerar artefatos que n˜ao s˜ao relevantes para o papel dos descritores. Assim, esta derivada ´e calculada usualmente pelo m´etodo de Fourier.
Sabe-se que a derivada pode ser obtida por uma transforma¸c˜ao de Fourier seguida de uma multiplica¸c˜ao no plano complexo e da invers˜ao desta multiplica¸c˜ao (80). Assim, considerando- se a curva log(A(r)) × log(r) como u(t), para efeitos de simplifica¸c˜ao, a derivada pode ser calculada pela seguinte express˜ao:
du dt = T
em que i ´e o n´umero imagin´ario, T ´e a transformada de Fourier e f ´e a frequˆencia. Associando- se a Gaussiana:
du dt = T
−1{T{u(t)}T{g(t, a)}(i2πf)}, (4.3.4)
em que a multiplica¸c˜ao T{u(t)}T{g(t, a)} representa a convolu¸c˜ao u(t) ∗ g(t, a) no dom´ınio da frequˆencia.
Na pr´atica, dois problemas ainda precisam ser resolvidos. O primeiro ´e que a transformada de Fourier exige uma boa amostragem para um resultado significativo. Como neste caso essa amostragem ´e logar´ıtmica, os primeiros pontos s˜ao mais espa¸cados e, em fun¸c˜ao disso, devem ser eliminados da curva para garantir um resultado mais preciso. Outro problema ´e que a transformada de Fourier diverge nas descontinuidades, fato este chamado de fenˆomeno de Gibbs (81). Para solucionar esta anomalia, a curva ´e replicada e espelhada `a direita e `a esquerda e o resultado da derivada ´e extra´ıdo apenas da parte intermedi´aria da curva replicada (82).
Em (19), os autores comp˜oem o vetor de atributos com medidas geom´etricas da curva DFM, como m´aximo, m´ınimo, ´area sob a curva do gr´afico, etc. Naquele trabalho, os autores aplicam essa t´ecnica `a an´alise de express˜ao gˆenica, obtendo bons resultados. J´a em (21), ´e observado que a curva DFM apresenta dois picos e uma depress˜ao bem definidos. Assim, naquele trabalho foram usadas as coordenadas destes pontos para compor o vetor descritivo e assim obter excelentes resultados em um problema de identifica¸c˜ao de esp´ecies vegetais a partir da imagem da folha.
4.4
Descritores fractais
Como abordado anteriormente, a dimens˜ao fractal por si s´o ´e insuficiente para caracterizar objetos e, particularmente, texturas em problemas mais complexos, uma vez que esta ´e apenas uma medida global da complexidade da imagem. Al´em disso, os cen´arios do mundo real representados nessas imagens n˜ao apresentam um n´ıvel constante de auto-similaridade como ocorre com fractais matem´aticos. Isso pode ser observado quando se analisa a curva de fractalidade log(M) × log(ǫ). Enquanto para um fractal cl´assico, esta curva apresenta o aspecto de uma reta perfeita, para uma imagem real ela cont´em v´arias irregularidades, apenas se aproximando de uma reta. Essa observa¸c˜ao sugere que a curva log − log como um todo possa ser usada para descrever com maior riqueza a complexidade de um objeto em diferentes escalas de an´alise.
4.4 Descritores fractais 79
O m´etodo de DFM visto anteriormente j´a faz uso desta curva, embora use apenas poucos pontos de interesse para compor o vetor de caracter´ısticas. Esta ainda n˜ao ´e uma abordagem ideal, sobretudo na an´alise de texturas, quando se apresentam muitos detalhes e micro-padr˜oes em todos os n´ıveis de escala e o uso de valores tomados apenas em escalas espec´ıficas n˜ao ´e suficiente na maioria dos casos. Al´em disso, o m´etodo DFM depende fortemente da estrat´egia usada para a identifica¸c˜ao dos pontos de interesse na curva multiescala e a obten¸c˜ao destes pontos pode ser dif´ıcil em muitas situa¸c˜oes, al´em de poder fornecer informa¸c˜oes redundantes entre si. Assim sendo, em (20, 83), propˆos-se o conceito de descritores fractais, no qual toda a curva log − log ´e usada diretamente para compor o vetor de caracter´ısticas.
O conceito de descritores de imagens n˜ao ´e algo recente, mas j´a ´e usado amplamente na literatura, por exemplo, quando se fala de descritores de Fourier (12) ou descritores de wavelets (84). O conceito geral ´e de que descritores s˜ao os conjuntos de valores de uma fun¸c˜ao que ´e obtida de algum tipo de modelagem da imagem original. Assim, descritores de Fourier e wavelets s˜ao os valores da fun¸c˜ao de espectro/energia da transformada respectiva. Em uma analogia simples, os descritores fractais podem ser entendidos como o conjunto de valores da fun¸c˜ao log − log da dimens˜ao fractal.
A ideia ent˜ao ´e extrair caracter´ısticas (descritores) relevantes de um objeto a partir da curva log − log do m´etodo de estimativa da dimens˜ao fractal daquele objeto. Como observado, na descri¸c˜ao dos m´etodos de estimativa de dimens˜ao, de um modo geral, todos esses m´etodos s˜ao baseados na rela¸c˜ao logar´ıtmica entre algum tipo de medida M e a escala ǫ em que essa medida ´e analisada. Assim, a dimens˜ao D pode ser representada por uma express˜ao gen´erica:
D ∝ log(M)log(ǫ) . (4.4.1)
Os descritores s˜ao ent˜ao obtidos a partir da seguinte rela¸c˜ao:
u : log(ǫ) → log(M). (4.4.2)
Para simplificar a nota¸c˜ao, a vari´avel independente log(ǫ) ´e substitu´ıda por t. Assim, os descritores correspondem a valores obtidos a partir da fun¸c˜ao u(t).
Na pr´atica, os descritores fractais conseguem efetuar um mapeamento completo da com- plexidade da textura na imagem. Assim, os primeiros descritores (valores pequenos de ǫ) fornecem a complexidade de microestruturas presentes na imagem, enquanto os ´ultimos forne- cem a complexidade global. Desta forma, os descritores apresentam um alto n´ıvel de eficiˆencia na caracteriza¸c˜ao e discrimina¸c˜ao de texturas, mesmo aquelas que apresentam estruturas que s˜ao dif´ıceis de ser analisadas at´e mesmo a olho nu. Em seguida, s˜ao mostradas duas figuras
que ilustram a efic´acia dos descritores fractais. A Figura 4.5 exibe as imagens de duas formas j´a exibidas na Figura 4.1 e cujas dimens˜oes s˜ao idˆenticas. Abaixo das imagens, os descritores fractais discriminam visualmente as formas, apresentando uma informa¸c˜ao significativamente mais rica do que a dimens˜ao. O mesmo ocorre na Figura 4.6, neste caso com duas imagens de texturas.
DF = 1.672
Imagem 1
Imagem 2
DF = 1.672
1.5 2 2.5 3 3.5 4 4.5 5 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 k D(k) Imagem 1 Imagem 2Figura 4.5 – Duas formas com dimens˜oes fractais idˆenticas sendo discriminadas pelos descritores fractais.
Qualquer um dos m´etodos de estimativa de dimens˜ao fractal descritos no cap´ıtulo anterior pode ser usado para gerar descritores fractais, assim como qualquer outra abordagem que gere uma curva de fractalidade seguindo uma lei de potˆencia. Os descritores assim definidos podem ser usados diretamente, concatenados entre diferentes abordagens ou empregados ap´os algum
4.4 Descritores fractais 81
DF = 1.327
Imagem 1
Imagem 2
DF = 1.327
0 0.5 1 1.5 2 2.5 12 12.5 13 13.5 14 14.5 15 15.5 16 16.5 k D(k) Imagem 1 Imagem 2Figura 4.6– Duas texturas com dimens˜oes fractais idˆenticas sendo discriminadas pelos descritores fractais.
83