Upload
internet
View
111
Download
3
Embed Size (px)
Citation preview
Processamento de Imagens
Representação e Descrição
Contexto
Processamento baixo nível
Realce de imagem, restauração, transformações
Nível intermediário
Representação e descrição
Processamento alto nível (reconhecimento e interpretação)
reconhecimento de objetos, classificação, etc
Reconhecimento de Regiões
• Descrição das regiões de forma adequada para um classificador– vetor de características (numérico)– descrição sintática não-numérica
• Caracterizar propriedades (Forma - Shape) de uma região.
• Aplicável a objetos 2D e 3D (necessidade de + de um viewpoint)
Importância
• OCR (Optical Character Recognition)• ECG (Electro-Cardiogram)• EEG(Electro-Encephalogram)• Classificação de células• Reconhecimento de cromossomos• Inspeção automática• CBIRS (Content-based Image Retrieval System)• Inúmeras outras aplicações
Alongado?
Fourier
Textura
I.A.
Reconhecer o que é visto
Tópicos importantes
• Identificação da Região
• Descrição e representação baseadas em contornos
• Descrição e representação baseadas em regiões
• Descritores de cor
Representação de regiões
• Características externas– Contorno
• Características internas– pixels que compõem a região.
• Região representada por seu contorno, por sua vez descrito por características como comprimento, nro de concavidades, etc.
Representação de regiões
• Normalmente uma representação externa enfoca as características da Forma
• Representação interna enfoca aspectos como cor e textura.
• Importante: em ambos os casos devem ser considerados a invariabilidade quanto ao tamanho, rotação, translação !– P(T(I)) = T(P(I))
• P = propriedade T = transformação
Definir a Forma
• Tarefa difícil– alongada, arredondada, com arestas salientes,
etc.
• Não há metodologia genericamente aceita
• Nem sempre se sabe o que é importante na forma
• Suficiente para a maioria das aplicações
Identificação de regiões
• É preciso identificar a região p/ descrevê-la.
• Como ?– Rotulação (connected component labelling)
• input: imagem segmentada
• definir grau de conectividade entre pixels
• rotular as regiões (1..N), N é o nro total de regiões.
Identificação de regiões
Dois componentes conectados, considerando-se pixels 4-conectados
Algoritmo de CCLConnected Component Labeling
Imagem binária Rotulagem de 1-8
Atribuição de cores distintas a cada um dos rótulos
Quantos perus há na imagem?
Original Thresholded
Rotulagem Coloração (196 regiões)
Representação de forma por contorno
• Chain Codes
• Representações geométricas– comprimento– curvatura– bending energy (energia de “modelagem”)– assinatura– distribuição de chords (linha que une qq dois
pontos de uma borda)
Representação de forma por contorno
• Descritores de Fourier
• Seqüências de segmentos
• B-Spline
• Redes Neurais
• Transformada de Hough
Chain Codes• Representam um contorno por uma seqüência
conectada de segmentos de retas com comprimento e direções específicas.
• Depende da conectividade, ponto inicial, rotação
• Torná-lo independente do ponto inicial
• Torná-lo independente da rotação.
• pode-se normalizar o chain code para rotação usando a derivada anti-horária à 90o (derivative)
Chain Codes• Depende da conectividade, ponto inicial,
rotação
• Torná-lo independente do ponto inicial– Procurar a representação que gera o menor nro
• Torná-lo independente da rotação.– derivada anti-horária à 90o (derivative)
Chain Codes
Representações Geométricas(Representações sensíveis à resolução da imagem)
• Comprimento do contorno– derivado do chain code:
• passos horizontais e verticais = 1
• passos diagonais: sqrt(2).
– Precisão 8-conectividade > 4-conectividade– Também conhecido por perímetro
• closed-boundary length
– Considerar a outer-border
• Curvatura– caso contínuo: taxa de mudança na inclinação– caso discreto: razão entre nro total de pixel da
borda (comprimento) e nro de pixel da borda que muda significativamente.
– Quanto menos mudanças, mais “reto” é o contorno.
– Como avaliar?• Interprete o ângulo distante de b pixels a partir de
um pixel de bordo qualquer.
• Através dos chain codes
Representações Geométricas
Representações Geométricas
• Bending Energy (BE)– Energia armazenada no formato
– Energia necessária p/ dobrar uma vara até uma forma desejável
Representações Geométricas
c2(k) é o quadrado da curvaturaL é o comprimento da borda
Bending Energy
• Assinatura– representação funcional 1-D de um contorno– Como ?
• por exemplo, a distância do centróide com relação ao ângulo
• mínima distância de A a B (A e B contorno e são opostos)
Representações Geométricas
AssinaturasDistância entre A e um pontoperpendicular B no ponto tangente a A
• Chord Distribution– Chord: linha que une dois pontos de um contorno.
Seja b(x,y)=1 pontos do contorno; e b(x,y)=0, outros pontos.
– A distribuição dos comprimentos e ângulos de todos os chords formam um descritor
Representações Geométricas
• Descritores de Fourier– Suponha uma curva fechada no plano dos
complexos. Percorrendo-a no sentido anti-horário, veloc. constante, obtém-se uma função complexa z(t). Uma volta completa leva tempo 2. Função periódica. Isso permite uma representação de Fourier para z(t).
Representações por Contorno
Comprimento da curva
Descritores
Como construir DFs a partir de um contorno
• Suponha que a borda (contorno fechado) de um “shape” tenha N pixeis numerados 0 – N-1
• O pixel k-th do contorno tem a posição (xk,yk). Podemos descrever o contorno como duas equações pararétricas: – x(k) = xk
– y(k) = yk
• Podemos extrair TF de cada funcao:– ax(ν) = F (x(k)) – ay(ν) = F (y(k))
• Estes dois espectros são os Descritores de Fourier
Como construir DFs a partir de um contorno
• Alternativamente, podemos considerar as coordenadas (x,y) do ponto não como coord. Cartesianas, mas no plano complexo:s(k) = x(k) + iy(k)
• Portanto,
Como construir DFs a partir de um contorno
a(ν) = F (s(k)) = F (x(k) + iy(k)) = F (x(k)) + iF (y(k)) = ax(ν) + iay(ν) = [(ax(ν))−(ay(ν))] + i [(ax(ν)) + (ay(ν))]
Propriedades
• Suponha que o espectro contenha altas freqüências– Mudanças bruscas em x e y.– Contorno irregular
• Suponha que o sinal tenha poucas altas freqüências– Mudanças suaves em x e y.– Contorno suave
Propriedades (2)• Se fizermos um low-pass nos FDs ?
– Suavização
– Os componentes de baixa freqüência capturam a forma geral do objeto
– Se não usarmos todos os k componentes de a(v), mas somente m < k ?
• Quem é o primeiro k ??? (lembre fourier ...)
– Se reconstruíssemos o sinal com estes m componentes ?
• Compressão !
– Pensando assim, FDs agem como momentos:• Termos de ordem baixa/menores momentos dão a forma
aproximada
• Adicao de termos adicionais, refinam a forma !
Respostas a transformações
• Vamos usar propriedades da FT
• Translação: significa adicionar uma constante a cada coordenada (x,y).– Portanto, só mudamos o componente de
freqüência zero F(0,0) -> (DC) ! • Nada sobre a forma em si
– Portanto, exceto para F(0,0), FDs são invariantes à translação.
Respostas a transformações
• Rotação – Da análise de Fourier, rotação no plano
complexo por um ângulo θ é multiplicação por eiθ
– Portanto, rotação sobre a origem do sistema de coordenadas, apenas multiplica os FDs por eiθ
Respostas a transformações
• Escala – Suponha que mudemos o tamanho do objeto.
– Tire suas conclusões comparando esta operação com translação !!
• Ponto de inicio:– Isso não é translação do sinal 1D s(k) ao longo
de k ?– Translação no domínio espacial (k) corresponde
a mudança de fase na transformada !
Descritores (qtd)
Original: M=64 M=2 M=4 M=8
M=61 M=62
• Seqüências de segmentos (segment sequences)
– aproximação de uma região por um polígono• É preciso encontrar os vértices do polígono
– contorno representado por segmentos de formas variadas
• apropriado para reconhecimento sintático.
Representações por Contorno
Seqüências de segmentos
• Determinando os vértices– utilizar medida de curvatura. – Tolerância de intervalo
Determinando os vértices• Divisão recursiva do contorno
– dividir até satisfazer um certo critério• defina reta entre pontos extremos
• encontre ponto mais distante
• se distância for maior que um threshold, estabeleça novo ponto e continue recursivamente.
Segmentos de formas variadas• Defina “primitivas”: representados por polinômios
de 2a ordem (círculos, parábolas)• Utilizados em procedimentos sintáticos de
classificação de cromossomos: cada primitiva têm um grau de curvatura, concavidade, etc.
Representação de forma por região
• Descritores escalares– Área– Número de Euler– Projeção– Ecentricidade– Elongatedness, Rectangularity, Compactness, – Direção
Representação de forma por região
• Momentos
• Convex Hull
• Esqueletonização
• Decomposição de Regiões
• Descritores Escalares– calculo baseado em heurística– não funcionam bem para formas muito
complexas
• Área: nro de pixels que compõem a região
Representações por Região
Descritores Escalares
• Número de Euler: propriedade topológica– topologia: estudo das propriedades de uma
imagem que não são afetadas por qualquer deformação (a não ser separação ou união de partes da figura)
– Nro de Euler: E = C - H• C: Componente conectados na figura
• H: Nro de buracos (Holes)
Descritores Escalares• Projeção
– Horizontal ph(i)e Vertical ph(j)
– processamento de imagens binárias
Descritores Escalares• Excentricidade
– razão entre o chord de comprimento máximo A e chord B (A e B perpendiculares)
A B
• Alongamento (elongatedness)– Razão entre comprimento e largura do
retângulo que circunscreve o contorno• este critério não se aplica a regiões curvas, caso em
que deve se aplicar o critério de espessura máxima
Descritores Escalares
Nro erosões
• Retangularidade
Descritores Escalares
(Fk) Razão da área da região e a área do bounding box ao contorno
Direção do retângulo
• Compactness– a região mais compacta num espaço euclidiano
é um círculo
Descritores Escalares
• Momentos– propriedades estatísticas que descrevem formas– imagens binárias ou de tons de cinza– depende da escala, translação, rotação.– A média, a variância de uma função f(x) são
exemplos de momento desta função.– Para uma imagem, o momento de ordem (p+q) é
definido:
Representações por Região
i,j são coordenadas dos pixels da região
Momentos• O momento da fórmula anterior foi definido
sobre o ponto zero
• Se o definirmos sobre a média, teremos um momento invariante à translação, conhecido como momento central
onde xc e yc são os centros de gravidade
(centróides) [médias] dados por
Valor total imagem
• Momentos podem ser invariantes com relação a escala e há também propriedades que garantem independência da rotação e translação. [Sonka]
Momentos
• Convex Hull (casco convexo)– O que é convexo?
Representações por Região
• Seja R uma região. H é um convex hull se ela é a menor região convexa que satisfaça R H
A partir de Pk (no sentido anti-horário) encontre pq = minn n .Pq será um vértice do convex hull.
• Uma forma de representação da forma de uma região plana é a redução a um grafo
• Essa redução pode ser feita obtendo-se o esqueleto (skeleton) através de um algoritmo de “afinamento” (thinning)
Representações por Região
Thinning
• O esqueleto por ser definido pela Medial Axis Transformation (MAT)– A MAT de uma região R com borda B
• p/ cada ponto p em R. encontre seu vizinho mais próximo (qq medida de distância). Se p tem mais de um vizinho, então, ele pertence ao eixo medial (medial axis) ou esqueleto da região.
– Cuidados dos algoritmos:• manter conectividade
• não remover os pontos extremos (end points)
Transformada da distância
Coloque fogo na borda da imagem: quanto tempo leva para o fogoatingir todos os pixels internos...?
Exemplos
Exemplo de MAT