Processamento Digital de Imagens

Universidade Estadual de Campinas – UNICAMP
Centro Superior de Educação Tecnológica – CESET
Processamento Digital de Imagens - ST061
Prof.: Marco Antonio Garcia de Carvalho
Agosto 2004
Campinas, SP - Brasil
Sumário
1 Introdução ao processamento digital de imagens
1.1 Fundamentos . . . . . . . . . . . . . . . . . . . .
1.2 Representação de imagens digitais . . . . . . . . .
1.3 Sistema de processamento de imagens digitais . .
1.3.1 Aquisição . . . . . . . . . . . . . . . . . .
1.3.2 Armazenamento . . . . . . . . . . . . . . .
1.3.3 Processamento . . . . . . . . . . . . . . .
1.3.4 Comunicação . . . . . . . . . . . . . . . .
1.3.5 Exibição . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
3
4
4
6
6
6
6
2 Fundamentos de Imagens Digitais
2.1 Relacionamento básico entre pixels . . . . . . . . . . . . .
2.1.1 Vizinhos de um pixel . . . . . . . . . . . . . . . . .
2.1.2 Conectividade . . . . . . . . . . . . . . . . . . . . .
2.1.3 Rotulação de componentes conexos . . . . . . . . .
2.1.4 Medidas de distância . . . . . . . . . . . . . . . . .
2.2 Modelo de câmera . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Modelo de câmera - transformações de perspectiva .
2.2.2 Modelo de câmera - Imageamento estéreo . . . . . .
2.3 Transformações geométricas . . . . . . . . . . . . . . . . .
2.3.1 Translação . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Rotação - Eixo z . . . . . . . . . . . . . . . . . . .
2.3.3 Mudança de escala . . . . . . . . . . . . . . . . . .
2.3.4 Ampliação e redução (zoom in e zoom out) . . . . .
2.3.5 Espelhamento (flip) . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
7
7
7
8
9
9
10
11
11
11
11
11
11
3 Processamento de histograma
3.1 Cálculo do histograma de uma imagem . . . . . . . . . . . . . . . . . . . .
3.2 Equalização de histograma . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
13
15
4 Realce de Imagens
4.1 Introdução . . . . . . . . . . . .
4.2 Fundamento matemáticos . . .
4.2.1 Convolução . . . . . . .
4.2.2 Transformada de Fourier
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
17
17
17
18
5 Filtragem de imagens via operação de convolução
5.1 Filtragem passa-baixa . . . . . . . . . . . . . . . .
5.2 Filtragem por mediana . . . . . . . . . . . . . . . .
5.3 Filtragem passa-alta . . . . . . . . . . . . . . . . .
5.4 Detecção de pontos . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
20
20
21
22
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.5
Detecção de bordas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 Estatı́sticas
6.1 Máximo e mı́nimo . . . . .
6.2 Média . . . . . . . . . . .
6.3 Desvio padrão e variância
6.4 Mode . . . . . . . . . . . .
6.5 Correlação . . . . . . . . .
6.6 Relação Sinal-Ruı́do . . .
22
.
.
.
.
.
.
23
23
23
23
23
23
24
.
.
.
.
.
.
25
25
25
25
26
26
27
8 Representação e descrição de imagens
8.1 Representação: Esqueleto de uma região . . . . . . . . . . . . . . . . . . .
8.2 Descrição: descritores simples de fronteiras e regiões . . . . . . . . . . . . .
29
29
30
Bibliografia
32
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Segmentação de imagens
7.1 Detecção de descontinuidade . .
7.1.1 Detecção de pontos . . .
7.1.2 Detecção de linhas . . .
7.2 Limiarização . . . . . . . . . . .
7.3 Segmentação orientada a regiões
7.3.1 Crescimento de regiões .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ST061
1
Introdução ao processamento digital de imagens
1.1
Fundamentos
• As técnicas de PDI tem por objetivo melhorar a informação visual para a análise e
interpretação humanas.
• Primeiras técnicas de PI: melhoramento de imagens digitalizadas para jornais enviadas de Londres para New York (década de 20).
• Melhora da qualidade visual das imagens: impressão e distribuição de nı́veis de brilho.
• Processamento digital: iniciado pelo Jet Propulsion Lab, 1964, com imagens da Lua.
• Aplicações na medicina (raios X, MRI), geografia (clima, poluição), arqueologia
(correção de imagens borradas, montagem de quebra-cabeças com o objetivos antigos), fı́sica, biologia, aplicações industriais etc.
• A Figura 1 apresenta alguns exemplos de aplicações de diversas técnicas de processamento digital de imagens
• O processamento digital de imagens abrange uma ampla escala de hardware, software
e fundamentos teóricos.
1.2
Representação de imagens digitais
• Uma imagem é uma função bidimensional de intensidade da luz f (x, y), onde x
e y denotam as coordenadas espaciais e o valor de f em qualquer ponto (x, y) é
proporcional ao brilho (nı́vel de cinza) da imagem naquele ponto.
• A convenção é atribuir proporcionalmente valores mais altos para áreas de maior
brilho.
• Uma imagem digital pode ser considerada uma matriz cujos ı́ndices de linhas e colunas
identificam um ponto na imagem, como mostra a Figura 2, e o correspondente valor
do elemento identifica o nı́vel de cinza naquele ponto.
• Os elementos dessa matriz são chamados de pixels ou pels (pictures elements).
• O tamanho das imagens varia de acordo com a aplicação. Contudo, é interessante
trabalhar com matrizes quadradas com nı́veis de cinza que sejam potências inteiras
de 2.
Processamento Digital de Imagens
3
ST061
(a)
(b)
(c)
(d)
(e)
(f)
Figura 1: Aplicações em processamento digital de imagens.
1.3
Sistema de processamento de imagens digitais
• Uma seqüência tı́pica de procedimentos em um sistema de processamento de imagens
é mostrada na Figura 3[4].
• Os elementos de um sistema de propósito geral capaz de desempenhar as operações
de PDI são: aquisição, armazenamento, processamento, comunicação e exibição.
1.3.1
Aquisição
• Converte a imagem para uma representação numérica adequada às etapas posteriores
do sistema.
• É necessário um sensor para imageamento (sensı́vel a uma banda do espectro de
energia eletromagnética) e de um digitalizador (converta o sinal fı́sico para a forma
digital).
Processamento Digital de Imagens
4
ST061
Figura 2: Convenção dos eixos para representação de imagens digitais.
Figura 3: Uma seqüência de passos em sistemas de processamento digital de imagens.
Processamento Digital de Imagens
5
ST061
• Por exemplo, em um sistema de raios X, o meio que recebe a fonte de raios X que passa
por um corpo ou objeto é um filme (poderia ser um CCD — Dispositivo de Carga
Acoplada). Uma imagem digital é obtida ao se permitir apenas valores discretos de
intensidade de luz e de posição.
1.3.2
Armazenamento
• Uma das classificações na forma de armazenamento é: curto tempo (uso durante o
processamento), on-line (acesso rápido) e em arquivo (acesso menos freqüente).
• O armazenamento é medido em bytes. Por exemplo, uma imagem de 8 bits com
resolução de 1024 x 1024 pixels, requer um milhão de bytes para seu armazenamento.
• Frame-buffer é um tipo de memória computacional de curto tempo, na qual uma
imagem pode ser acessada de forma rápida, em taxas de tempo de vı́deo.
1.3.3
Processamento
• Envolve procedimentos que são geralmente expressos em forma algorı́tmica; a maioria, implementada em software.
• O processamento de imagens é caracterizado por soluções especı́ficas. Técnicas que
funcionam bem em uma área podem se mostrar inadequadas em outra área. Portanto,
há espaço para bastante pesquisa.
1.3.4
Comunicação
• Comunicação entre sistemas — transmissão: desafio quanto à velocidade de transmissão e qualidade das imagens enviadas.
• O problema torna-se ainda mais complicado quando deseja-se transmitir seqüências
de vı́deo (imagens em movimento com áudio associado).
1.3.5
Exibição
• Os principais dispositivos de saı́da são os monitores de computadores. A resolução
espacial dos monitores é normalmente especificada em pontos por polegada (dots per
inch — dpi). Um valor tı́pico de resolução é 72dpi, sendo que uma tela de TV tem
resolução na faixa de 40dpi [2].
• Existem diversas formas de reprodução em papel. A melhor é a reprodução fotográfica. Uma alternativa é o uso da técnica de halftoning que consiste, basicamente, em imprimir pontos escuros de diferentes tamanhos espaçados de tal maneira
a reproduzir a ilusão de tons de cinza.
Processamento Digital de Imagens
6
ST061
2
Fundamentos de Imagens Digitais
2.1
Relacionamento básico entre pixels
• Nas seções seguintes, uma imagem será representada por I (i, j).
2.1.1
Vizinhos de um pixel
• Um pixel p de coordenadas (i, j), tem quatro vizinhos horizontais e verticais cujas
coordenadas são
(i + 1, j) , (i − 1, j) , (i, j + 1) , (i, j − 1)
• O conjunto de vizinhos acima é denominado de vizinhança-4 de p e representado por
N4 (p). Acrescentando os vizinhos das diagonais, determina-se a vizinhança-8 de p,
denotado por N8 (p).
2.1.2
Conectividade
• Para dizer que dois pixels são conectados é preciso determinar se eles são adjacentes
(vizinhança-4, por exemplo) e se seus nı́veis de cinza satisfazem um certo critério de
similaridade (se são iguais, por exemplo).
• Por exemplo, em uma imagem binária com intensidades 0 e 1, dois pixels podem ser
N4 (p), mas eles não são conectados (precisariam ter o mesmo valor).
2.1.3
Rotulação de componentes conexos
• A habilidade de atribuir rótulos diferentes a componentes conexos disjuntos de uma
imagem é de fundamental importância em visão computacional.
• Um algoritmo simples e seqüencial de rotulação de uma imagem é explicado abaixo
através de um conjunto de passos.
1. A imagem deve ser percorrida pixel por pixel, da esquerda para direita e de
cima para baixo.
2. Assumiremos vizinhança N4 (p).
3. Sejam os vizinhos superior e esquerdo de p representados por s e e, respectivamente.
4. Se o valor de p é 0, siga para a próxima posição.
5. Se o valor de p é 1, examine s e e: (a) se ambos forem iguais a zero, atribua a
p um novo rótulo; (b) se apenas um dos vizinhos de p for igual a 1, atribua a p
o seu rótulo; (c) se ambos forem 1 e possuem o mesmo rótulo, atribua a p este
rótulo; (d) se ambos forem 1, mas possuem rótulo diferentes, atribua um dos
rótulos a p e anote que os dois rótulos são equivalentes (os pontos s e e estão
conectados por p).
Processamento Digital de Imagens
7
ST061
6. Ao final da varredura, todos os pixels com valor 1 terão sido rotulados, mas alguns destes rótulos poderão ser equivalentes. Portanto, é necessário reorganizar
os rótulos equivalentes em valores iguais.
• A Figura 4 mostra um processo de rotulação para uma imagem sintética de 7 linhas
e 6 colunas.
Figura 4: Processo de rotulação: (a) imagem original com blobs; (b) imagem digital; (c)
imagem rotulada.
2.1.4
Medidas de distância
• Seja três pixels p, q e z, D é uma função distância (ou métrica) se:
(a) D (p, q) ≥ 0 (D (p, q) = 0 se p = q)
(b) D (p, q) = D (q, p)
(c) D (p, z) ≤ D (p, q) + D (q, z)
• A distância D4 , também chamada de quarteirão, entre p e q é definida como
D4 (p, q) = |x − s| + |y − t|
(1)
onde (x, y) e (s, t) são as coordenadas de p e q, respectivamente. Por exemplo, se
pegarmos os pixels com D4 ≤ 2 a seguinte figura é formada (com relação a um ponto
central)
2
2 1 2
2 1 0 1 2
2 1 2
2
• Outra medida de distância conhecida como xadrez ou D8 , é definida como:
D8 (p, q) = max (|x − s| , |y − t|)
Processamento Digital de Imagens
(2)
8
ST061
Por exemplo, se pegarmos os pixels com D8 ≤ 2 a seguinte figura é formada (com
relação a um ponto central)
2
2
2
2
2
2.2
2.2.1
2
1
1
1
2
2
1
0
1
2
2
1
1
1
2
2
2
2
2
2
Modelo de câmera
Modelo de câmera - transformações de perspectiva
• Uma transformação perspectiva projeta pontos 3D em um plano, como mostra a
Figura 5. Observe que o sistema de coordenadas da câmera está alinhado com o
sistema de coordenadas do mundo.
Figura 5: Modelo básico de processamento de imagens. Apresenta os sistemas de coordenadas da câmera (x, y, z) e do mundo (X, Y, Z) [1].
• A relação que fornece as coordenadas (x, y) da projeção do ponto (X, Y, Z) sobre o
plano da imagem é dada por semelhança de triângulos.
x
X
=−
d
Z −d
y
Y
=−
d
Z −d
Processamento Digital de Imagens
(3)
(4)
9
ST061
Portanto, as equações acima podem ser escritas da seguinte forma
2.2.2
x=
dX
d−Z
(5)
y=
dY
d−Z
(6)
Modelo de câmera - Imageamento estéreo
• No modelo de transformação perspectiva visto na seção anterior, a informação de
profundidade é perdida quando o ponto (X, Y, Z) é imageado no plano da imagem.
• Entretanto, essa informação pode ser recuperada através do uso de técnicas de imageamento estéreo, com base no modelo mostrado na Figura 6.
Figura 6: Modelo do processo de imageamento estéreo[1].
• O procedimento consiste em se obter duas vistas para um mesmo objeto (ponto w,
neste exemplo). A distância entre os centros das lentes B é chamada de linha de
base. O objetivo é determinar as coordenadas (X, Y, Z) do ponto w, tendo (x1 , y1 ) e
(x2 , y2 ).
• Assume-se que as câmeras são idênticas e que os sistemas de coordenadas coordenadas
de ambas as câmeras estejam alinhados.
• As equações de X, Y seguem diretamente deduzidas como na seção anterior. Para
X, as equações são:
x1
X1 =
(d − Z1 )
(7)
d
x2
X2 =
(d − Z2 )
(8)
d
Processamento Digital de Imagens
10
ST061
• A coordenada Z é a mesma para ambos os sistemas de coordenadas e dada por:
dB
Z =d−
(9)
x2 − x1
• A tarefa mais difı́cil no uso da equação acima consiste em determinar dois pontos
correspondentes em imagens diferentes da mesma cena.
2.3
Transformações geométricas
• Trabalharemos com coordenadas homogêneas. As operações são feitas da seguinte
forma: P1 = O · P , onde O é a transformação que se deseja efetuar, P e P1 correspondem as coordenadas do ponto antes e após a transformação, respectivamente.
2.3.1
Translação

1
 0
T =
 0
0
2.3.2
0
1
0
0

0 dx
0 dy 

1 dz 
0 1
Rotação - Eixo z


cosθ −senθ 0 0
 senθ cosθ 0 0 

Rz (θ) = 
 0
0
1 0 
0
0
0 1
2.3.3
Mudança de escala

Sx 0 0
 0 Sy 0
S=
 0 0 Sz
0 0 0
2.3.4

0
0 

0 
1
Ampliação e redução (zoom in e zoom out)
• As dimensões de uma imagem são aumentadas ou diminuı́das para efeito de visualização. por exemplo, para um fator 2, o processo de ampliação pode ser demonstrado
pela Figura 7.
2.3.5
Espelhamento (flip)
• Combina rotações por ângulos múltiplos de 90◦ sob a imagem transposta:
(a) Flip horizontal - Rotação de 90◦ (AH) sob a transposta;
(b) Flip vertical - Rotação de 90◦ (H) sob a transposta
Processamento Digital de Imagens
11
ST061
Figura 7: Ampliação por um fator 2. Cada pixel na imagem (a) corresponde a 4 na imagem
(b)[2]. O processo inverso produz a redução da imagem.
Figura 8: Exemplo de espelhamento: (a) imagem original; (b) flip horizontal de (a); (c)
Flip vertical de (a)[2].
Processamento Digital de Imagens
12
ST061
3
Processamento de histograma
• O histograma de uma imagem com nı́veis de cinza no intervalo entre [0, L − 1] é
uma função discreta p (rk ) = nk /n, em que rk é o k-ésimo nı́vel de cinza (k =
0, 1, 2, . . . L − 1), nk é o número de pixels na imagem com este nı́vel de cinza e n
corresponde ao número total de pixels na imagem.
• Um gráfico dessa função fornece uma descrição global da aparência desta imagem,
como mostra a Figura 9. É possı́vel obter uma indicação da qualidade do contraste
e brilho médio (imagem predominantemente clara ou escura).
Figura 9: Exemplos de histogramas de imagens: (a) Imagem original Pout e seu histograma; (b) Imagem original Tire e seu histograma; (c) Imagem original Bone marrow e seu
histograma.
3.1
Cálculo do histograma de uma imagem
• Um exemplo de obtenção do histograma de uma imagem de 8 × 8 com 8 nı́veis de
cinza é dado na Figura 10 e Tabela 1.
Processamento Digital de Imagens
13
ST061
Nı́vel de cinza rk
0
1
2
3
4
5
6
7
Nı́vel de cinza normalizado nk
0
28
1/7
12
2/7
8
3/7
8
4/7
4
5/7
2
6/7
2
1
0
Total
64
p (rk )
0,4375
0,1875
0,125
0,125
0,0625
0,03125
0,03125
0
1
Tabela 1: Valores para o cálculo do histograma da imagem mostrada na Figura 10.
Figura 10: Cálculo do histograma de uma imagem:(a) imagem original; (b) histograma
correspondente.
Processamento Digital de Imagens
14
ST061
3.2
Equalização de histograma
• Técnica a partir da qual se procura redistribuir os valores de tons de cinza dos pixels
em uma imagem de modo a obter um histograma mais uniforme.
• Utiliza-se o conceito de transformação de intensidade. Seja um nı́vel de cinza rk ,
usaremos uma transformação do tipo
sk = T (rk )
(10)
onde sk é o novo tom de cinza na imagem destino. A transformação mais usual para
se equalizar um histograma é através da função de distribuição acumulada (cdf cumulative distribution function) [2], expressa por:
sk =
k
X
p (rj )
(11)
j=0
onde 0 ≤ rk ≤ 1 e k = 0, 1, 2, . . . , L − 1.
• No exemplo numérico da Figura 10, aplicando-se a transformação de intensidade da
Equação 11, produz-se a equalização apresentada na Figura 11.
Figura 11: Equalização do histograma da imagem da Figura 10:(a) imagem após transformação; (b) histograma equalizado.
• A Figura 12 apresenta alguns exemplos de equalização para as imagens da Figura 9.
Processamento Digital de Imagens
15
ST061
Figura 12: Exemplos de equalização de histogramas para as imagens da Figura 9: (a)
Imagem Pout e seu histograma equalizado; (b) Imagem Tire e seu histograma equalizado;
(c) Imagem Bone marrow e seu histograma equalizado.
Processamento Digital de Imagens
16
ST061
4
Realce de Imagens
4.1
Introdução
• O objetivo é processar uma imagem de modo que o resultado seja mais adequado
para a aplicação em questão.
• Um classificação ampla das técnicas de realce de imagens consiste em: métodos no
domı́nio espacial e métodos no domı́nio espectral.
• As técnicas classificadas no domı́nio espacial operam diretamente sobre a matriz dos
pixels que representa a imagem. Podem ser divididas em técnicas de procssamento
ponto-a-ponto e de processamento por máscara.
• As técnicas classificadas como de domı́nio da freqüência são baseadas na modificação
da transformada de Fourier da imagem.
4.2
4.2.1
Fundamento matemáticos
Convolução
• Uma relação entre entrada-saı́da é chamada de sistema se existe uma única saı́da
para uma dada entrada. Essa relação é dada na Figura 13.
Figura 13: Um sistema: relação entre a entrada x (n1 , n2 ) e a saı́da y (n1 , n2 ). T [] representa
uma transformação qualquer.
• A relação entre entrada e saı́da é dada por
y (n1 , n2 ) = T [x (n1 , n2 )]
(12)
• Para sistemas lineares invariantes no tempo (SLIT), a equação acima pode ser reescrita da seguinte forma
∞
X
y (n1 , n2 ) =
∞
X
x (k1 , k2 ) T [δ (n1 − k1 , n2 − k2 )]
(13)
x (k1 , k2 ) h (n1 − k1 , n2 − k2 )
(14)
k1 =−∞ k2 =−∞
ou
y (n1 , n2 ) =
∞
X
∞
X
k1 =−∞ k2 =−∞
Processamento Digital de Imagens
17
ST061
onde
h (n1 − k1 , n2 − k2 ) = T [δ (n1 − k1 , n2 − k2 )]
(15)
e δ (n1 , n2 ) é a função impulso definida abaixo.
1, n1 = n2 = 0
δ (n1 , n2 ) =
0, caso contrario
• A Equação 16 é conhecida como convolução e denotada pelo operador *, ou seja
y (n1 , n2 ) = x (n1 , n2 ) ∗ h (n1 , n2 )
(16)
• Exemplo 1 — Fazer a convolução entre x e h dados na Figura 14.
Figura 14: Exemplo de convolução. Determine o valor da saı́da y (n1 , n2 ).
4.2.2
Transformada de Fourier
• A operação que transforma um sinal para sua representação via componentes de
freqüência é denominada de Transformada (Fourier, wavelet, Z).
• O par de transformadas discretas de Fourier para o caso 2D é dado por
M −1 N −1
1 XX
F (u, v) =
f (x, y) exp [−j2π (ux/M + vy/N )]
M N x=0 y=0
(17)
onde u = 0, 1, 2, . . . , M − 1 e v = 0, 1, 2, . . . , N − 1 e
f (x, y) =
M
−1 N
−1
X
X
F (u, v) exp [j2π (ux/M + vy/N )]
(18)
u=0 v=0
• Freqüentemente, a transformada de Fourier é expressada na forma exponencial, ou
seja,
F (u, v) = |F (u, v)| ejθ(u,v)
Processamento Digital de Imagens
(19)
18
ST061
• A função magnitude |F (u, v)| é chamada de espectro de Fourier e θ (u, v), ângulo de
fase.
• O quadrado do espectro |F (u, v)|2 é chamado de espectro de potência ou densidade
espectral.
• A imagem mostrada na Figura 15 apresenta um exemplo de transformada de Fourier.
Figura 15: Exemplo de transformada de Fourier: (a) imagem original lena; (b) espectro
de Fourier de (a).
• Existe uma relação básica entre a transformada de Fourier e a convolução, importante
para a compreensão das técnicas de PDI:
f (x, y) ∗ h (x, y) ⇔ F (u, v) H (u, v)
(20)
• Transformada Rápida de Fourier (FFT - Fast Fourier Transform) — A
FFT é um algoritmo que reduz a quantidade de operações necessárias para o cálculo
da Transformada de Fourier. A complexidade cai de N 2 para N log2 N . Por exemplo,
suponha que se deseja calcular a Transformada de Fourier de um vetor de 8192
elementos: se o tempo de processamento em uma máquina qualquer fosse 5s usando
a FFT, a mesma máquina levaria cerca de 600 vezes mais tempo para realizar o
mesmo cálculo sem esta técnica.
Processamento Digital de Imagens
19
ST061
5
Filtragem de imagens via operação de convolução
• A operação é feita diretamente sobre os valores dos pixels na imagem (chamado de
filtragem no domı́nio espacial).
• A metodologia básica consiste na operação de convolução, estudada no Capı́tulo
anterior.
5.1
Filtragem passa-baixa
• São filtros que suavizam os contornos das imagens. São usados para borramento e
redução de ruı́do.
• O filtro tem que possuir todos os coeficiente positivos. Exemplos de máscaras de dois
tamanhos diferentes são dadas abaixo.


1 1 1
1 
1 1 1 
×
9
1 1 1



1
×
25 

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1






• Um exemplo de filtragem passa-baixa é dado na Figura 16.
Figura 16: (a) imagem original; (b) imagem filtrada via passa-baixa (observe que as raias
ficaram borradas).
5.2
Filtragem por mediana
• Quando deseja-se reduzir o ruı́do, uma opção mais adequada é a filtragem por mediana. A operação consiste em substituir o nı́vel de cinza de cada pixel pela mediana
dos nı́veis de cinza da vizinhança daquele pixel (esse tipo de filtro é não-linear).
Processamento Digital de Imagens
20
ST061
• A mediana m de um conjunto de valores é tal que metade dos valores no conjunto
são menores que m e na outra metade, maiores do que m.
• Ex.: Qual a mediana do conjunto {10, 20, 20, 20, 15, 20, 20, 25, 100}?
• Um exemplo de filtragem por mediana é dado na Figura 17.
Figura 17: (a) imagem original; (b) imagem corrompida; (c) imagem filtrada (mediana vizinhança 3 × 3).
5.3
Filtragem passa-alta
• Enfatiza detalhes finos ou realça imagens que tenham sido borradas.
• A imagem poderá vir a ter alguns nı́veis de cinza negativo, de modo que é ncessário
um cliping ou uma mudança de escala. Um exemplo de filtro passsa-alta é dado
abaixo.


−1 −1 −1
1 
−1 8 −1 
×
9
−1 −1 −1
• Um exemplo de filtragem passa-alta é dado na Figura 18.
Figura 18: (a) imagem original saturno; (b) imagem filtrada via passa-alta.
Processamento Digital de Imagens
21
ST061
5.4
Detecção de pontos
• A máscara abaixo destacará pixels brilhantes rodeados de pixels mais escuros.


−1 −1 −1
 −1 8 −1 
−1 −1 −1
5.5
Detecção de bordas
• Borda é a fronteira entre duas regiões, cujos nı́veis de cinza predominantes são consideravelmente diferentes. A seguir, são apresentados diversas máscaras para detecção
de bordas horizontais e verticais.
Sobel (vertical e horizontal)

 

−1 0 1
−1 −2 −1
 −2 0 2  ,  0
0
0 
−1 0 1
1
2
1
Prewitt (vertical e horizontal)

 

−1 0 1
−1 −1 −1
 −1 0 1  ,  0
0
0 
−1 0 1
1
1
1
Roberts (vertical e horizontal)

 

−1 0 0
0 0 −1
 0 1 0 , 0 1 0 
0 0 0
0 0 0
• Um exemplo de detecção de borda usando Sobel é dado na Figura 19.
Figura 19: (a) imagem original; (b) detecção de borda via Sobel.
Processamento Digital de Imagens
22
ST061
6
Estatı́sticas
• Em processamento de imagens, é muito comum usar estatı́stica para descrever imagens ou partes de uma imagem. A seguir, apresento algumas estatı́sticas bastante
usadas em PDI.
• Um exemplo da utilização de alguns parâmetros estatı́sticos é dado na Figura 20.
6.1
Máximo e mı́nimo
• Maiores e menores valores de intensidade de luz presentes na imagem.
6.2
Média
• A luminosidade média m de uma imagem I é definida como
m = E [I (i, j)] =
1 X
I (i, j)
N i,j∈<
(21)
Onde N é o número total de pixels da imagem. Alternativamente, pode-se usar o
histograma para calcular a média.
6.3
Desvio padrão e variância
• Variação da intensidade luminosa com relação à média. Dá uma idéia do contraste
na imagem.
σ 2 = E |I (i, j) − m|2
(22)
6.4
Mode
• O valor de intensidade de luz mais freqüente na imagem.
6.5
Correlação
• A correlação entre duas funções f (i, j) e g (i, j), denotada por f (i, j) ◦ g (i, j), é dada
por:
M −1 N −1
1 XX ∗
f (i, j) ◦ g (i, j) =
f (m, n) g (i + m, j + n)
M N m=0 n=0
(23)
• A operação de correlação é semelhante à convolução. A diferença é que g (i, j) não é
refletida em torno da origem.
• Se f (i, j) e g (i, j) forem iguais, a operação passa a ser chamada de autocorrelação.
Para funções diferentes, o termo correlação cruzada também é utilizado na literatura.
Processamento Digital de Imagens
23
ST061
6.6
Relação Sinal-Ruı́do
• A relação sinal-ruı́do (SNR — Signal-to-Noise Ratio) pode ter várias definições.
Abaixo, apresento duas definições: A primeira, utilizada quando se conhece que
o sinal pertence à faixa amin ≤ a ≤ amax ; A segunda, caso o sinal não seja limitado
e se possua a distribuição estatı́stica do mesmo.
e
amax − amin
SN R = 20log10
σ
m
SN R = 20log10
σ
(24)
(25)
Figura 20: (a) imagem original; (b) alguns parâmetros estatı́sticos para a imagem completa
e para a região de interesse (ROI — region of interest) circulada.
Processamento Digital de Imagens
24
ST061
7
Segmentação de imagens
• Geralmente, o primeiro passo em análise de imagens é a segmentação. A segmentaçaõ subdivide uma imagem em suas parte ou objetos constituintes. Veja algumas
definições de segmentação:
- Segmentação é o processo de dividir a imagem em regiões conexas e homogêneas
(Salembier,1993),(Vachier,1995);
- O objetivo da segmentação é de reagrupar em regiões elementos que possuem atributos similares (Agnus, 2001);
- As técnicas de segmentação têm como finalidade produzir uma partição da imagem
tão próxima quanto possı́vel daquela feita pelo olho humano (Gomila,2001).
• Os algoritmos de segmentação são baseados em duas propriedades: descontinuidade
(detecção de pontos isolados, linhas e bordas) e similaridade (limiarização e crescimento de regiões).
7.1
Detecção de descontinuidade
A teoria envolvendo este tópico foi discutida no capı́tulo sobre Filtragem de imagens. A
seguir, acrescento alguns tipos de filtros e conceitos.
7.1.1
Detecção de pontos
• Após usada a máscara de filtragem, um ponto é detectado se:
|R| > T
onde T é um limiar não-negativo e R é dado pela equação:
R = w1 z1 + w2 z2 + · · · w9 z9 =
9
X
wi zi
(26)
i=1
tal que wi são os coeficientes do filtro 3 × 3 e zi , os nı́veis de cinza da imagem.
7.1.2
Detecção de linhas
• Abaixo, exemplos de máscaras para detecção de linhas a +45◦ e −45◦, respectivamente.

 

−1 −1 2
2 −1 −1
 −1 2 −1  e  −1 2 −1 
2 −1 −1
−1 −1 2
• Após a convolução, deve ser feita a limiarização, como descrita na Seção anterior e
melhor definida na próxima Seção.
Processamento Digital de Imagens
25
ST061
7.2
Limiarização
• Na Figura 21 são mostrados 2 diferentes histogramas Qual a análise que pode ser
feita com base nesses histogramas?
Figura 21: Limiarização — análise de histogramas.
• A limiarização é uma operação que envolve testes de uma função f (x, y). A limiarização de uma imagem g (x, y) é definida como:
g (x, y) =
1 se f (x, y) > T
0 se f (x, y) ≤ T
• Um exemplo de binarização de imagens é dada na Figura 22. De que forma poderı́amos
remover os pequenos pontos brancos?
(a)
(b)
Figura 22: Exemplo de limiarização: (a) imagem original; (b) imagem binarizada com
T = 180.
7.3
Segmentação orientada a regiões
• Define as regiões diretamente na imagem, sem antes realizar outra operação (binarização, por exemplo).
Processamento Digital de Imagens
26
ST061
7.3.1
Crescimento de regiões
• Agrupa pixels ou sub-regiões em regiões maiores. O processo mais simples começa
com um conjunto de pontos sementes, anexando paulatinamente os outros pixels da
imagem, caso alguma propriedade destes seja similar à da semente.
• Exemplos de critérios de similaridade: nı́vel de cinza, cor e textura. A quantidade
de regiões da imagem corresponderá a quantidade de sementes.
• Veja um exemplo da técnica de crescimento de região mostrada na Tabela 2 abaixo.
1
2
3
4
5
1
0
1
0
2
0
2
0
1
1
0
1
3
5
5
6
7
5
4
6
8
7
6
6
5
7
7
7
6
5
Tabela 2: Imagem I — aplicação da técnica de crescimento de regiões utilizando o critério
da diferença absoluta entre os nı́veis de cinza do pixel e da semente menor que um dado
limiar T : (a) para T = 3; (b) para T = 8. Defina que qualquer pixel que satisfaça essa
propriedade para ambas a sementes, será atribuı́do à Região R1 . As sementes são os pontos
(3, 2) e (3, 4).
• Dois problemas enfrentados por este tipo de técnica são: a escolha da(s) semente(s)
e a escolha da(s) propriedade(s).
• A seleção de critérios de similaridade e das sementes dependem do problema e do
tipo de imagem disponı́vel. Por exemplo, para imagens provenientes de satélite para
levantamento de terrenos, a cor é um aspecto importante. Em aplicações militares
de imageamento infravermelho (ou de controle de temperatura para detecção da
Febre Asiática), a escolha de pixels mais claros é uma maneira natural de iniciar um
algoritmo de crescimento de regiões.
• Sejam as imagens dadas na Figura 23, analise a segmentação com base em algoritmos
de crescimento de regiões.
Processamento Digital de Imagens
27
ST061
(a)
(b)
(c)
(d)
(e)
(f)
Figura 23: Exemplos de segmentação de imagens: (a),(b) imagem de levedura original
e segmentada; (c),(d) imagem cameraman original e segmentada; (e) grãos de arroz; (f)
bifão.
Processamento Digital de Imagens
28
ST061
8
Representação e descrição de imagens
• Após a segmentação, o passo seguinte consiste na representação e descrição do conteúdo para permitir o processamento subsequente.
• As regiões são representadas através de suas caracterı́sticas externas (fronteiras) ou
internas (pixels que compõem a região). A descriçao refere-se, por exemplo, à escolha
de uma caracterı́stica da fronteira da região (tamanho, número de concavidades).
8.1
Representação: Esqueleto de uma região
• A redução da representação estrutural de uma região planar é realizada obtendo-se
o esqueleto da região através de um algoritmo de afinamento (esqueletização).
• A esqueletização cumpre um papel importante em visão computacional, sobretudo
nas tarefas de reconhecimento de padrões. Exemplos incluem o reconhecimento de
impressões digitais e de caracteres.
• O esqueleto de uma região é definido pela transformação do eixo médio (Medial
Axis Transform — MAT — Blum,1967). O esqueleto é obtido sobre a imagem da
transformada distância da região R a ser afinada. Dado um pixel p de R, se ele
for eqüidistante da borda B da imagem, ele pertence ao eixo médio (esqueleto).
A Figura 24 apresenta alguns esqueletos de imagens (trabalharemos somente com
imagens binárias).
Figura 24: Esqueletos de imagens: (a) exemplos; (b) calcular o esqueleto desta imagem
digital.
• A implementação direta do MAT é muito custosa computacionalmente. Portanto,
novos algoritmos surgiram a fim de calcular o esqueleto de uma imagem. O processo
consiste em apagar paulatinamente os pontos de borda, respeitando as caracterı́sticas:
(a) não deve remover pontos extremos; (b) não deve quebrar da conectividade; (c)
ter cuidado com a erosão excessiva da região.
• A seguir é descrito um algoritmo para o afinamento de regiões binárias (vizinhança 8,
conforme ilustra a Figura 25(a)). O algoritmo consiste na aplicação, a cada iteração,
de duas etapas:
Processamento Digital de Imagens
29
ST061
1a. etapa: O ponto de contorno p1 deve ser eliminado se as seguintes condições
forem satisfeitas:
(a) 2 ≤ N (p1 ) ≤ 6; (número de vizinhos não nulos de p1 )
(b) S (p1 ) = 1; (número de transições 0-1 na seqüência ordenada p2 , p3 , . . . p9 , p2 )
(c) p2 · p4 · p6 = 0
(d) p4 · p6 · p8 = 0
2a. etapa: As condições (a) e (b) continuam as mesmas, mas (c) e (d) mudam para:
(cc) p2 · p4 · p8 = 0
(dd) p2 · p6 · p8 = 0
• A 1a. etapa deve ser aplicada a cada pixel da borda. Caso o ponto da borda
satisfaça às 4 condições, ele será apagado. Em seguida, a 2a. etapa deve ser aplicada,
consistindo em uma iteração do algoritmo.
Figura 25: (a) Vizinhança 8 - notação; (b) aplicar o algoritmo de afinamento para esta
letra.
8.2
Descrição: descritores simples de fronteiras e regiões
Processamento Digital de Imagens
30
ST061
Fronteiras
• Descritores simples: comprimento do contorno; eixos maiores e menores; curvatura
(taxa de inclinação).
• Código da cadeia: baseia-se na conectividade 4 ou 8 (Figura 26(a),(b)); efetua a
análise dos segmentos de reta que compõem o contorno.
Figura 26: Direções do código da cadeia: (a) Vizinhança 4; (b) Vizinhança 8; (c) qual o
código da cadeia deste contorno?.
Regiões
• Descritores simples: área, perı́metro, compacidade (definida como o quadrado do
perı́metro sobre a área), eixos principais, fator de forma, estatı́sticas dos nı́veis de
cinza.
• Descritores topológicos (propriedades que não se alteram após deformações ou outro
processamento): número de buracos, número de componentes conexos, número de
Euler E (veja a Figura 27).
• Também podem ser usados como descritores as texturas, Transformada de Fourier,
algumas operações de morfologia matemática etc.
Figura 27: Descritores tópológicos.
Processamento Digital de Imagens
31
ST061
Referências
[1] R.C. Gonzalez, R.E. Woods. Processamento de imagens digitais (versão traduzida).
São Paulo: Editora Edgard Blücher, 2000.
[2] O. M. Filho, H. V. Neto. Processamento Digital de Imagens. Rio de Janeiro: Editora
Brasport, 1999.
[3] J. S. Lim. Two Dimensional Signal and Image Processing, New Jersey: Prentice Hall,
1990.
[4] A. K. Jain. Fundamentals of Digital Image Processing. New Jersey, Prentice Hall,
1989.
[5] J. Serra. Image Analysis and Mathematical Morphology. Editora Academic Press,
1982.
[6] C. M. Thompson, L. Shure. Image Processing Toolbox for use with MATLAB, The
Math Works, 1995.
[7] J. Gomes, L. Velho. Computação Gráfica : Imagem, Rio de Janeiro: IMPA/SBM,
1994.
Processamento Digital de Imagens
32