isep Processamento de Imagem Mestrado ISEP/IST em Eng. Electrotécnica e Computadores António Costa ([email protected]) Índice isep • • • • • • • • Maio 2004 Introdução Definições Ferramentas Amostragem Algoritmos Técnicas Conclusão Informação Adicional Processamento de Imagem 2 Introdução isep • Processamento Digital de Imagem – Desde circuitos simples até sistemas computacionais • Enquadramento do Processamento de Imagem Designação Síntese de Imagem Entrada Descrição Saída Imagem Processamento de Imagem Imagem Imagem Análise de Imagem Imagem Medidas Compreensão de Imagem Imagem Descrição • Domínio de aplicação 2D (mais comum) Maio 2004 Processamento de Imagem 3 Definições isep • Imagem – É uma função escalar a(x,y): intensidade de qualquer coisa traduzida num valor inteiro, real ou complexo – Uma imagem digital a[m,n] resulta de imagem analógica a(x,y) através de amostragem - digitalização – Uma imagem é formada por N linhas e M colunas, sendo cada elemento de imagem a[m,n] um pixel – Na realidade a função a() é a(x,y,z,t,,...), mas será abordado apenas o caso 2D, estático e monocromático Maio 2004 Processamento de Imagem 4 Definições isep • Exemplo Linhas Colunas Valor = a(x,y,z,t,) – Imagem de 16 linhas e 16 colunas – Pixel em a[10,3] tem valor inteiro 110 (gama 0-255) Maio 2004 Processamento de Imagem 5 Definições isep • Valores mais comuns – – – – Nº de linhas N: 256, 512, 525, 625, 768, 1024, 1035 Nº de colunas M: 256, 512, 768, 1024, 1320 Nº de intensidades: 2, 64, 256, 1024, 65536, 224, 232 Casos mais comuns: M=N=2K (K=8,9 ou 10) devido a tecnologias de hardware ou algoritmos (FFT) – O número máximo de intensidades é geralmente potência de 2 • Caso =2: imagem binária (“preto e branco”) • Caso >2: imagem “em tons de cinzento” Maio 2004 Processamento de Imagem 6 Definições isep • Tipos de operações sobre imagens – Transformação de imagem a[m,n] em imagem b[m,n] • Pontual: o resultado num pixel apenas depende do valor do pixel de entrada correspondente • Local: o resultado num pixel depende dos valores da vizinhança de pixels de entrada próximos • Global: o resultado num pixel depende de todos os valores dos pixels de entrada • Exemplos Pontual Maio 2004 Processamento de Imagem Global Local 7 Definições isep • Tipos de vizinhança de pixels – O conceito de vizinhança de pixels é muito importante – No caso mais comum de amostragem rectangular as vizinhanças mais usadas são a viz4 e a viz8 – Em alguns dispositivos é possível efectuar amostragem hexagonal, de que resulta a vizinhança viz6 – Exemplos Maio 2004 Processamento de Imagem 8 Ferramentas isep • Convolução – Obedece ao princípio da sobreposição – Permite descrever a saída de um sistema linear, conhecidas a entrada e a função de transferência – Versão “discreta” c[m,n] = a[m,n] b[m,n] = j k a[j,k] b[m-j,n-k] • Correlação – Mede o grau de “similaridade” entre dois sinais – Versão “discreta” c[m,n] = a[m,n] b[m,n] = j k a[j,k] b[m+j,n+k] Maio 2004 Processamento de Imagem 9 Ferramentas isep • Transformada de Fourier – Versão “discreta” (DFT) A(,) = m n a[m,n] e-j(m + n) a[m,n] = 1/42 A(,) e+j(m + n) d d – A transformada de uma imagem pode ser complexa – Exemplo log(|A(,)|) Reconstrução com (,)=0 a[m,n] (,) Maio 2004 Processamento de Imagem Reconstrução com log(|A(,)|)=k 10 Ferramentas isep • Estatísticas – É comum o uso de descrições estatísticas simples – A função densidade de probabilidade p(a) de uma região de pixels pode ser estimada por contagem das ocorrências de intensidade nessa região – Essa contagem pode ser descrita pelo histograma h[a] a[m,n] Maio 2004 P(a) - Intensidade Processamento de Imagem h[a] - Intensidade 11 Ferramentas isep • Estatísticas – Média ma = 1/P j,k a[j,k] (P - nº de pixels da região) – Desvio padrão sa = 1/(P-1) j,k(a[j,k] - ma)2 – Relação sinal/ruído SNR = 20log10((amax - amin) / sn) (sn - desvio padrão do ruído) – Exemplo Média: 219.3 Desvio padrão: 4.0 Mínimo: 202 Mediana: 220 Máximo: 226 Moda: 220 SNR: 33.3 Maio 2004 Processamento de Imagem 12 Ferramentas isep • Representações de contorno – Chain codes • Seguimento do contorno em sentido horário com anotação das mudanças de direcção entre pixels sucessivos - exemplo Pi +7076666544556... – Crack codes • Seguimento da linha entre objecto e fundo (crack) Maio 2004 Processamento de Imagem 13 Ferramentas isep • Uma nota de aviso – Não é possível ainda modelar o sistema visual humano através das técnicas correntes de análise de sistemas – As ilusões ópticas não se enquadram nesses modelos Indução de visualização de valores “cinzentos” que se sabe não existem e noção de dinamismo na imagem Indução de visualização de contornos inexistentes e contraste exagerado URL: http://www.city.ac.uk/optics/BVTutor/html/ocular_movements_i.html Maio 2004 Processamento de Imagem 14 Amostragem isep • Amostragem de imagem – Ideal bideal[m,n] = m n a(mX0,nY0) (x-mX0,y-nY0) – “Real” breal[m,n] = (a(x,y) p(x,y)) m n (x-mX0,y-nY0) – A função de abertura p(x,y) depende da tecnologia usada na captura da informação e é frequentemente: • Circular; Quadrada; Gaussiana – Deve escolher-se a densidade de amostragem com base na teoria de sinal clássica (teoria de Nyquist) Maio 2004 Processamento de Imagem 15 Algoritmos isep Baseados em operações de histograma • Alargamento do contraste – Muitas imagens são geradas com intensidades que não aproveitam a gama máxima de intensidades – Corrige-se através do alargamento da gama da imagem b[m,n] = (2B-1) (a[m,n] - plow%) / (phigh% - plow%) se plow% < a[m,n] < phigh% ; senão 0 ou 2B-1 • plow% - intensidade baixa no histograma (0%, 1%, 5%) • phigh% - intensidade alta no histograma (100%, 99%, 95%) contraste alargado original Maio 2004 Processamento de Imagem 16 Algoritmos isep Baseados em operações de histograma • Equalização de histogramas – Normaliza-se o histograma da imagem para um histograma “padrão” (comparação de imagens, etc) – O objectivo ideal é obter ocorrências iguais para todas as intensidades - histograma plano – Pode obter-se algo aproximado usando a função distribuição de probabilidade (normalizada de 0 a 2B-1) como índice de acesso ao histograma “padrão”... histograma equalizado original Maio 2004 Processamento de Imagem 17 Algoritmos Baseados em operações matemáticas isep • Operações binárias – Baseadas nas operações booleanas pixel a pixel – Exemplo Imagem a NOT(b) OR(a,b) Imagem b AND(a,b) XOR(a,b) • Operações “aritméticas” SUB(a,b) [ AND(a,NOT(b)) ] – a+b a/b log(a) exp(a) sqrt(a) sin(a) (2B-1)-a, etc Maio 2004 Processamento de Imagem 18 Algoritmos Baseados em convolução isep • Enquadramento – Baseia-se na noção de uma janela finita h() operando sobre a imagem a(), produzindo uma nova imagem c() – O pixel de saída é igual à soma pesada dos pixels de entrada dentro da janela, em que os pesos são os valores específicos do filtro de convolução h() • Convolução no domínio espacial – Pode gerar acessos “fora” da imagem a[m,n] c[m,n] = a[m,n] h[m,n] = j k h[j,k] a[m-j,n-k] • Note-se que m-j ou n-k podem ser negativos • Solução: extender artificialmente a imagem Maio 2004 Processamento de Imagem 19 Algoritmos Baseados em suavização isep • Objectivos gerais – Tipicamente usados para reduzir o ruído e/ou preparar imagens para outros processamentos mais complexos • Filtros lineares Rectangular (J=K=5) Circular (J=K=5) Piramidal (J=K=5) Cónico (J=K=5) – Filtro uniforme: – Filtro triangular: – Filtro gaussiano: cada vez mais utilizado (versatilidade) Maio 2004 Processamento de Imagem 20 Algoritmos Baseados em suavização isep • Filtros não-lineares – Estes filtros não podem ser alvo de análises de Fourier – Filtro de mediana: em cada aplicação da janela h() usa-se a intensidade mediana dentro da referida janela – Filtro Kuwahara: preserva bem os contornos • Em cada uma das 4 regiões calcula-se a média e a variância • O valor atribuído ao pixel central é o valor médio da região que Região 4 possui menor variância Região 1 Região 2 Pixel central Região 3 Maio 2004 Processamento de Imagem 21 Algoritmos Baseados em suavização isep • Exemplos de vários filtros de suavização Histograma Imagem original Maio 2004 Filtro linear Uniforme 5x5 Filtro linear Gaussiano (=2.5) Filtro não-linear Mediana 5x5 Filtro não-linear Kuwahara 5x5 Processamento de Imagem 22 Algoritmos Baseados em derivação isep • Enquadramento – Os algoritmos apresentados são uma aproximação – Tendem a aumentar o ruído de alta frequência, pelo que geralmente são combinados com filtros de suavização • Primeira derivada – Filtros de gradiente a[m,n] = (hx a[m,n])ix + (hy a[m,n])iy • Básicos: • Prewitt: Maio 2004 Processamento de Imagem 23 Algoritmos Baseados em derivação isep • Primeira derivada – Filtros de gradiente (continuação) a[m,n] = (hx a[m,n])ix + (hy a[m,n])iy • Sobel: • Construídos à medida: • Gaussianos: Maio 2004 Processamento de Imagem 24 Algoritmos Baseados em derivação isep • Primeira derivada – Exemplos de filtros de gradiente Imagem original Básico Maio 2004 Sobel Processamento de Imagem Gaussiano (=1.5) 25 Algoritmos Baseados em derivação isep • Segunda derivada – Desempenham um papel muito importante – Filtros de Laplaciano 2a[m,n] = (h2x a[m,n])ix + (h2y a[m,n])iy • Básicos: • Gaussiano: • Construídos à medida: • SDGD: Maio 2004 (2ª derivada na direcção do gradiente) Processamento de Imagem 26 Algoritmos Baseados em derivação isep • Segunda derivada – Exemplos de filtros de Laplaciano Imagem original Básico Maio 2004 Gaussiano (=1.5) À medida Processamento de Imagem SDGD (=1.0) 27 Algoritmos Baseados em derivação isep • Outros filtros – Há uma infinidade de filtros lineares e não-lineares – Para se medir a resposta de filtros não convencionais usam-se imagens de teste (padrões sinusoidais, etc) – Permite avaliar os efeitos em termos de frequências – Exemplos de resultados com padrão de teste sinusoidal Filtro passa-baixo Maio 2004 Filtro passa-banda Processamento de Imagem Filtro passa-alto 28 Algoritmos Baseados em morfologia isep • Enquadramento – Uma definição alternativa do conceito de imagem baseia-se na noção de conjunto de coordenadas que fazem parte dos objectos da imagem – Exemplo A Imagem binária com dois objectos A e B B – Os pixels do objecto A partilham uma propriedade Objecto - A = { a | propriedade(a) = Verdade } Fundo - Ac = { a | a A } Maio 2004 Processamento de Imagem 29 Algoritmos Baseados em morfologia isep • Enquadramento – A noção de objecto implica conectividade de pixels fundo de A objecto A - O objecto A tem conectividade 4 - O fundo tem conectividade 12-4(=8) • Definições – As operações fundamentais sobre objectos são: • • • • Maio 2004 Translação: A + x = { a + x | a A } Adição/subtracção: A B = bB(A+b) ; A B = bB(A+b) Complemento (fundo) Simetria: -A = { -a | a A } Processamento de Imagem 30 Algoritmos Baseados em morfologia isep • Dilatação e Erosão – A dilatação D(A,B) corresponde à adição A B – A erosão E(A,B) corresponde à subtracção A (-B ) – Exemplos D(A,B) E(A,B) B -B – Tipicamente A é uma imagem e B é um “estruturante” (equivale ao núcleo de convolução dos filtros lineares) – Exemplos de estruturantes comuns N4 Maio 2004 Processamento de Imagem N8 31 Algoritmos Baseados em morfologia isep • Dilatação e Erosão – Teorema da Decomposição • Para um estruturante B finito, simétrico, sem buracos e contendo o seu centro ([0,0] B), verifica-se que D(A,B) = A (A B) [nota: A é o contorno de A] • Resulta que apenas basta processar os pixels do contorno de A, não sendo necessário processar os pixels do seu interior • Algoritmo “rápido” de dilatação: para cada pixel do objecto, todos os seus pixels vizinhos (vizC) de fundo passam a pertencer ao objecto • Algoritmo “rápido” de erosão: cada pixel do objecto que possua um pixel vizinho (vizC) de fundo passa a fundo Maio 2004 Processamento de Imagem 32 Algoritmos Baseados em morfologia isep • Dilatação e Erosão – Exemplos “rápidos” Dilatação com estrututante N4 Dilatação com estrututante N8 – Importante: D(E(A,B),B) A E(D(A,B),B) • Abertura e Fecho – Abertura: O(A,B) = D(E(A,B),B) • Tende a suavizar o contorno pelo interior – Fecho: C(A,B) = E(D(A,-B),-B) • Tende a suavizar o contorno pelo exterior Maio 2004 Processamento de Imagem 33 Algoritmos Baseados em morfologia isep • HitAndMiss – Operador de alto nível HitMiss(A,B) = E(A,B1) EC(AC,B2) – B1 e B2 são estruturantes finitos e disjuntos entre si – Este operador é o equivalente morfológico do template matching (técnica usada para comparar padrões com base na sua correlação) • B1 funciona como template para o objecto • B2 funciona como template para o fundo Maio 2004 Processamento de Imagem 34 Algoritmos Baseados em morfologia isep • Exemplos – Estruturantes Imagem A Dilatação com 2B Erosão com 2B Abertura com 2B (separa objectos) Fecho com 2B (preenche buracos) HitAndMiss com B1 e B2 [ A = A - E(A,N8) ] Maio 2004 Processamento de Imagem 35 Algoritmos Baseados em morfologia isep • Esqueleto – Quando realizavel, é uma polilinha que: • Tem largura de 1 pixel • Passa pelo “meio” do objecto • Preserva a topologia do objecto – Pode ser obtido por um processo iterativo baseado no B8, não se alterando o pixel central para “fundo” se • 1) o pixel estiver isolado • 2) a remoção do pixel alterar a conectividade • 3) a remoção do pixel encurtar a linha Maio 2004 Processamento de Imagem 36 Algoritmos isep Baseados em morfologia • Propagação (Reconstrução) – Visa reconstruir um objecto parcialmente erodido ou preencher um objecto definido pelo seu contorno – Algoritmo iterativo baseado numa imagem “semente” S(0), uma imagem máscara A e um estruturante B S(k) = D(S(k-1),B) A ; repetir até S(k) = S(k-1) • Em cada iteração a semente cresce dentro dos limites de A • As conectividades da fronteira de A e de B devem ser iguais • A implementação iterativa é ineficiente, mas existe uma implementação recursiva muito mais eficiente Maio 2004 Processamento de Imagem 37 Algoritmos Baseados em morfologia isep • Exemplos E(A,6N8) Imagem A Semente Máscara (a preto) Esqueleto de A Esqueleto de A Propagação com N8 (sem condição 3) Maio 2004 Processamento de Imagem 38 Algoritmos Baseados em morfologia isep • Tratamento de imagens “em tons de cinzento” – Os algoritmos anteriores podem ser extendidos para imagens com mais de dois níveis (16, 64, 256, etc) – Formulações para “tons de cinzento” • • • • • • • Maio 2004 Dilatação: DG(A,B) = max[j,k]B { a[m-j,n-k] + b[j,k] } Erosão: EG(A,B) = min[j,k]B { a[m+j,n+k] - b[j,k] } Abertura: OG(A,B) = DG(EG(A,B),B) Fecho: CG(A,B) = -OG(-A,-B) Suavização: MSmooth(A,B) = CG(OG(A,B),B) Gradiente: MGradient(A,B) = 1/2 [DG(A,B) - EG(A,B)] Laplaciano: MLaplacian(A,B) = 1/2 [DG(A,B) + EG(A,B) - 2A] Processamento de Imagem 39 Algoritmos Baseados em morfologia isep • Exemplos de filtros “em tons de cinzento” “Morfológicos” Clássicos Suavização Imagem A Gradiente Dilatação de A Maio 2004 Erosão de A Processamento de Imagem Laplaciano 40 Técnicas isep • Enquadramento – Os algoritmos apresentados anteriormente podem ser usados para resolver problemas complexos de processamento de imagem • Correcção de sombreamento – Os métodos de geração de imagem podem fazer com que as imagens exibam artefactos de sombreamento • Imagem “brilhante” no centro e “escura” nos limites • Imagem a “escurecer” da esquerda para a direita • Efeitos de lentes sujas, iluminação não uniforme, etc Maio 2004 Processamento de Imagem 41 Técnicas Correcção de sombreamento isep • Artefactos de sombreamento – Geralmente indesejados, mas difíceis de evitar – A sua eliminação é necessária em algumas aplicações • Estimação do sombreamento – A posteriori • Filtragem passa-baixo: ae[m,n] = a[m,n] - LowPass(a[m,n])+K • Filtragem morfológica: ae[m,n] = a[m,n] - MSmooth(a[m,n])+K – A priori • Recurso a imagens de calibração: Preto[m,n] e Branco[m,n] ae[m,n] = K (a[m,n]-Preto[m,n]) / (Branco[m,n]-Preto[m,n]) Maio 2004 Processamento de Imagem 42 Técnicas Correcção de sombreamento isep • Exemplos 1. O sombreamento indesejado manifesta-se através de uma rampa linear a crescer da esquerda para a direita 2. Os picos são objectos Linha da imagem original Passa-baixo Homomórfica Morfológica Calibrada (a melhor) Maio 2004 Processamento de Imagem 43 Técnicas Melhoria e restauro isep • Enquadramento – O processo de aquisição de imagem geralmente envolve degradação da imagem (inadvertidamente) • Desfocagem; Movimento da câmara; Ruído; etc – Objectivos • Melhoria visa “embelezar” a imagem • Restauro visa “repor a verdade” na imagem – Medição do erro • Usa-se frequentemente uma métrica de erro tipo RMS E{ae,a} = 1/MN m n | ae[m,n] - a[m,n] |2 Maio 2004 Processamento de Imagem 44 Técnicas Melhoria e restauro isep • Aumento de nitidez – Melhorar as silhuetas de uma imagem pode contribuir para aumentar a sua qualidade visual • Isolam-se as silhuetas de uma imagem • Amplificam-se essas silhuetas • Adicionam-se à imagem original – O Laplaciano é adequado para isolar as silhuetas ae[m,n] = a[m,n] - (K 2a[m,n]) Original Maio 2004 Processamento de Imagem Melhorada (K=1) 45 Técnicas Melhoria e restauro isep • Supressão de ruído – Pode ser conseguida através de suavização espacial, levando contudo a perda de nitidez – Os algoritmos de suavização são os mais adequados • Exemplos Wiener Gaussiano (=1) Imagem original (SNR = 20 dB) Kuwahara 5x5 Maio 2004 Processamento de Imagem Mediana 3x3 MSmooth 3x3 46 Técnicas Melhoria e restauro isep • Supressão de distorsão – Um modelo simples assume o ruído como única fonte de distorsão, mas existem modelos mais realistas – O filtro Wiener (domínio das frequências) é uma boa solução para distorsões baseadas em ruído – Exemplo Imagem distorcida (SNR = 30 dB) Wiener Mediana 3x3 • A imagem Wiener é mais nítida mas exibe artefactos • A imagem Mediana é mais esbatida mas disfarça artefactos Maio 2004 Processamento de Imagem 47 Técnicas Segmentação isep • Enquadramento – Designa as diversas técnicas capazes de distinguir “objectos de interesse” do resto (fundo) • Não há uma técnica de segmentação universal ou perfeita • Limiarização • Recorre a um limiar de intensidade para definir o objecto • A escolha do limiar de intensidade adequado é fulcral – Escolha do limiar via histograma • Exemplo Limiar=155 Imagem a segmentar Maio 2004 Processamento de Imagem Histograma de intensidades 48 Técnicas Segmentação isep • Limiarização – Escolha do limiar pelo algoritmo do triângulo • Exemplo Limiar=152 Imagem a segmentar • Determinação de fronteiras Histograma de intensidades – Uma alternativa à limiarização consiste em encontrar os pixels que definem as fronteiras do objectos – Gradiente • Exemplo Maio 2004 Processamento de Imagem 49 Técnicas Segmentação isep • Determinação de fronteiras – Cruzamento do zero (método LoG) • Consiste em usar o filtro Laplaciano e processar os “cruzamentos do zero” da 2ª derivada (mudança de sinal) • Requer suavização para evitar o excesso de ruído gerado – Método PLUS • Também baseado no “cruzamento o zero” do Laplaciano e no filtro de suavização SDGD(a) – Método geral Maio 2004 Processamento de Imagem 50 Técnicas Segmentação isep • Exemplos Imagem original (SNR = 20 db) LoG PLUS – Nota: após se encontrar a fronteira dos objectos, podem usar-se algoritmos de propagação para preenchimento Maio 2004 Processamento de Imagem 51 Técnicas Segmentação isep • Morfologia binária – Filtragem “sal” e “pimenta” (remoção de pixels isolados) – Determinação de objectos com furos • Exemplo Imagem segmentada Esqueleto após filtro “sal” e “pimenta” – Preenchimento de furos em objectos Imagem final após propagação • Exemplo Máscara Imagem segmentada e invertida Maio 2004 Processamento de Imagem Imagem final após propagação e inversão 52 Técnicas Segmentação isep • Morfologia binária – Remoção de objectos nos limites da imagem • Exemplo Máscara Imagem segmentada Imagem após propagação e XOR com a imagem máscara – Geração de exoesqueleto • Exemplo Imagem segmentada e invertida Maio 2004 Imagem após geração de esqueleto Processamento de Imagem 53 Técnicas Segmentação isep • Morfologia binária – Separação de objectos “que se tocam” • • • • • Segmentar imagem inicial para obter imagem binária Efectuar um número “pequeno” de erosões da imagem (N4) Calcular o exoesqueleto da imagem erodida Inverter a imagem do exoesqueleto erodido Combinar imagem final através de AND da imagem inicial com a imagem invertida do exoesqueleto erodido! Imagem inicial Maio 2004 Erosões Exoesqueleto Processamento de Imagem Pormenor da imagem final 54 Técnicas Segmentação isep • Morfologia de “tons de cinzento” – É uma extensão das técnicas de morfologia binária – Permite abordar os problemas a alto nível – Exemplo: método local de alargamento de contraste • Processa informação de contraste a nível local • Consegue-se obter uma solução mais satisfatória • Exemplos Antes | Depois Maio 2004 Antes | Depois Processamento de Imagem Antes | Depois 55 Conclusão isep • Presente – O processamento de imagem cada vez está mais embebido em aplicações sofisticadas e intuitivas – Ainda há problemas por resolver satisfatoriamente • Futuro – O processamento de imagem tenderá a evoluir para processamento de sequências de imagem (vídeo, etc) – Irão surgir mais implementações em hardware – A investigação deslocar-se-á para temas de mais alto nível, que usarão o P. I. como mais uma ferramenta Maio 2004 Processamento de Imagem 56 Informação Adicional isep • Sugestões – Tutoriais • http://www.google.pt/search?q=image+processing+tutorial – Softwares livres • VIPS - http://www.vips.ecs.soton.ac.uk/ (MS-Windows: http://www.vips.ecs.soton.ac.uk/vips-7.8/nip-7.8.14.zip) • GIMP - http://www.gimp.org/ (MS-Windows:http://www.gimp.org/~tml/gimp/win32) – Sítios web e documentos • Processamento de imagem em GPU’s (placas gráficas) – http://www.gpgpu.org/ (seguir ligação “Image and Volume Processing”) – http://www.vis.uni-stuttgart.de/eng/research/pub/pub2000/vmv00-hopf.pdf Maio 2004 Processamento de Imagem 57 isep FIM Maio 2004 Processamento de Imagem 58