71
Extração de Características cap 4 – Trucco e Verri

Extração de Características

Embed Size (px)

DESCRIPTION

Extração de Características. cap 4 – Trucco e Verri. Características de uma imagem. Globais : histograma, conteúdo de freqüências, etc... Locais : regiões com determinada propriedade, arestas, cantos, curvas, etc. Arestas e cantos. Locais de mudanças significativas na intensidade da imagem. - PowerPoint PPT Presentation

Citation preview

Page 1: Extração de Características

Extração de Características

cap 4 – Trucco e Verri

Page 2: Extração de Características

Características de uma imagem

• Globais: histograma, conteúdo de freqüências, etc...

• Locais: regiões com determinada propriedade, arestas, cantos, curvas, etc...

Page 3: Extração de Características

Arestas e cantos

• Locais de mudanças significativas na intensidade da imagem

Page 4: Extração de Características

Edgedels = edge elements

Page 5: Extração de Características

Tipos de arestasdegrau(step) rampa(ramp)

cume(roof) impulso(spike)

Page 6: Extração de Características

Gráfico sem e com ruído

Page 7: Extração de Características

Derivadas e arestas

f(x) f(x)+n(x) | f'(x)+n'(x) | f"(x)+n"(x)

Page 8: Extração de Características

Série de Taylor

)()(2

)()()()()( 3"2

' xOxfxxfxxfxxf

iiii ffff "'1 2

1

Com x=1, f(x)=fi e f(x+x)=fi+1

Com x=-1, f(x)=fi e f(x+x)=fi-1

iiii ffff "'1 2

1

(a)

(b)

Page 9: Extração de Características

Aproximações para derivadas

(a-b) 2/)( 11'

iii fff

(a+b) )2( 11"

iiii ffff

f(x)

x

fi-1fi fi+1

i+1ii-1

Page 10: Extração de Características

Em 2D

y

fx

fyxf ),(

Gradiente

Laplaciano

2

2

2

22 ),(

yf

xfyxf

x

yxfyxfx

yxf mnmn

,,, 1

x

yxfyxfy

yxf mnmn

,,, 1

11

11

Convolution Kernels

1414204141

Page 11: Extração de Características

Laplaciano

)2( 11"

iiii ffff

•Sometimes we are interested only in changing magnitude without regard to the changing orientation.

•A linear differential operator called the Laplacian may be used.

•The Laplacian has the same properties in all directions and is therefore invariant to rotation in the image.

http://www.cee.hw.ac.uk/hipr/html/log.html

http://ct.radiology.uiowa.edu/~jiangm/courses/dip/html/node83.html

Page 12: Extração de Características

Finite differences

11* II x

1

1*II y

IKhurram Hassan-Shafique

Page 13: Extração de Características

Classical Operators

Prewitt’s Operator

111111

11

11

Smooth Differentiate

101101101

111000111

111111

Khurram Hassan-Shafique

Page 14: Extração de Características

Classical Operators

Sobel’s Operator

112211

11

11

SmoothDifferentiate

101202101

121000121

121121

Khurram Hassan-Shafique

Page 15: Extração de Características

• Sobel Edge Detector

Detecting Edges in Image

Image I

101202101

121000121

*

*

Idxd

Idyd

22

I

dydI

dxd

ThresholdEdges

Khurram Hassan-Shafique

Page 16: Extração de Características

Sobel Edge Detector

Idxd

Idyd

I

Khurram Hassan-Shafique

Page 17: Extração de Características

Sobel Edge Detector

I

22

I

dydI

dxd

100 ThresholdKhurram Hassan-Shafique

Page 18: Extração de Características

Marr and Hildreth Edge Operator

• Smooth by Gaussian

• Use Laplacian to find derivatives

IGS * 2

22

2

21

yx

eG

Sy

Sx

S 2

2

2

22

Khurram Hassan-Shafique

Page 19: Extração de Características

Marr and Hildreth Edge Operator

IGIGS ** 222

2

22

22

22

32 2

21

yx

eyxG

Khurram Hassan-Shafique

Page 20: Extração de Características

Marr and Hildreth Edge Operator

2

22

22

22

32 2

21

yx

eyxG

0.0008 0.0066 0.0215 0.031 0.0215 0.0066 0.00080.0066 0.0438 0.0982 0.108 0.0982 0.0438 0.00660.0215 0.0982 0 -0.242 0 0.0982 0.0215

0.031 0.108 -0.242 -0.7979 -0.242 0.108 0.0310.0215 0.0982 0 -0.242 0 0.0982 0.02150.0066 0.0438 0.0982 0.108 0.0982 0.0438 0.00660.0008 0.0066 0.0215 0.031 0.0215 0.0066 0.0008

X

Y

Khurram Hassan-Shafique

Page 21: Extração de Características

Marr and Hildreth Edge Operator

Zero CrossingsDetection

I ImageG2*

IG *2 Edge Image

IG *2 Zero Crossings

Khurram Hassan-Shafique

Page 22: Extração de Características

1

6

3

Khurram Hassan-Shafique

Page 23: Extração de Características

Quality of an Edge Detector

• Robustness to Noise• Localization• Too Many/Too less Responses

Poor robustness to noise Poor localization Too many responses

True Edge

Khurram Hassan-Shafique

Page 24: Extração de Características

Canny Edge Detector• Criterion 1: Good Detection: The optimal

detector must minimize the probability of false positives as well as false negatives.

• Criterion 2: Good Localization: The edges detected must be as close as possible to the true edges.

• Single Response Constraint: The detector must return one point only for each edge point.

Khurram Hassan-Shafique

Page 25: Extração de Características

Hai Tao

Page 26: Extração de Características

The result– General form of the filter (N.B. the filter is odd so h(x) = -h(-x) the

following expression is for x < 0 only)

h x e a x a x e a x a xx x( ) ( sin cos ) ( sin cos ) / 1 2 3 4 1 2

2 052202 91540156939

.

..

aaaa

1

2

3

4

1

014867687170 208755347612446539390 79124465312

....

Camillo J. Taylor

Page 27: Extração de Características

Approximation– Canny’s filter can be approximated by the derivative of a Gaussian

h x ddx

e x ex x

( ) ( )

2

2

2

222

2

Camillo J. Taylor

Derivative of GaussianCanny

Page 28: Extração de Características

Canny Edge Detector

• Convolution with derivative of Gaussian• Non-maximum Suppression• Hysteresis Thresholding

Khurram Hassan-Shafique

Page 29: Extração de Características

Algorithm Canny_Enhancer• Smooth by Gaussian

IGS * 2

22

2

21

yx

eG

Tyx

T

SSSy

Sx

S

22yx SSS

x

y

SS1tan

Khurram Hassan-Shafique

• Compute x and y derivatives

• Compute gradient magnitude and orientation

Page 30: Extração de Características

Canny Edge Operator

IGIGS ** T

yG

xGG

T

Iy

GIx

GS

**

Khurram Hassan-Shafique

Page 31: Extração de Características

Canny Edge Detector

xS

yS

I

Khurram Hassan-Shafique

Page 32: Extração de Características

Canny Edge Detector

I

22yx SSS

25 ThresholdSKhurram Hassan-Shafique

Page 33: Extração de Características

We wish to mark points along the curve where the magnitude is biggest.We can do this by looking for a maximum along a slice normal to the curve(non-maximum suppression). These points should form a curve. There arethen two algorithmic issues: at which point is the maximum, and where is thenext one?

Algorithm Non-Maximum Suppression

Khurram Hassan-Shafique

Page 34: Extração de Características

Non-Maximum Suppression

• Suppress the pixels in ‘Gradient Magnitude Image’ which are not local maximum

edgean tonormaldirection thealong

in of neighbors theare and Sx,yy,xy,x

otherwise0,,&

,, if,, yxSyxS

yxSyxSyxSyxM

yx ,

yx,

yx ,

Khurram Hassan-Shafique

Page 35: Extração de Características

Non-Maximum Suppression

0

12

3

41420tan41422- :3

41422tan :241422tan41420 :1

41420tan41420 :0

.θ.

.θ.θ.

.θ.-

x

y

SS

θ tan

Khurram Hassan-Shafique

Page 36: Extração de Características

Non-Maximum Suppression

22yx SSS M

25ThresholdM

Khurram Hassan-Shafique

Page 37: Extração de Características

Hysteresis Thresholding

Khurram Hassan-Shafique

Page 38: Extração de Características

Hysteresis Thresholding

• If the gradient at a pixel is above ‘High’, declare it an ‘edge pixel’

• If the gradient at a pixel is below ‘Low’, declare it a ‘non-edge-pixel’

• If the gradient at a pixel is between ‘Low’ and ‘High’ then declare it an ‘edge pixel’ if and only if it is connected to an ‘edge pixel’ directly or via pixels between ‘Low’ and ‘ High’

Khurram Hassan-Shafique

Page 39: Extração de Características

Hysteresis Thresholding

M 25ThresholdM

15 35

LowHigh

Khurram Hassan-Shafique

Page 40: Extração de Características

Resultado de algoritmo de histerese

Page 41: Extração de Características

Subpixel Localization– One can try to further localize the position of the edge within a pixel by

analyzing the response to the edge enhancement filter– One common approach is to fit a quadratic polynomial to the filter

response in the region of a maxima and compute the true maximum.

abx

yyya

yyb

cbaycbay

cycbxaxxy

2

);0())1()1((21

));1()1((21)1(

;)1(;)0(

)(

max

2

0 1-1

Page 42: Extração de Características

Derivadas direcionais

yn

yf

xn

xf

nf

x

y

f(x,y)

y

x

nn

n

hpfnhpf

npf

h

)()(lim)(0

yx nyfn

xf

nf

nfnf

y

xyx n

nyf

xf

yfxf

nnnf

nf

nf

2

Page 43: Extração de Características

Detecting corners

– If Ex and Ey denote the gradients of the intensity image, E(x,y), in the x and y directions then the behavior of the gradients in a region around a point can be obtained by considering the following matrix

2

2

yyx

yxxyx

y

x

EEEEEE

EEEE

C

Camillo J. Taylor

Page 44: Extração de Características

Examining the matrix– One way to decide on the presence of a corner is to

look at the eigenvalues of the 2 by 2 matrix C.• If the area is a region of constant intensity we would expect

both eigenvalues to be small• If it contains a edge we expect one large eigenvalue and one

small one• If it contains edges at two or more orientations we expect 2

large eigenvalues

Camillo J. Taylor

Page 45: Extração de Características

Finding corners

– One approach to finding corners is to find locations where the smaller eigenvalue is greater than some threshold

– We could also imagine considering the ratio of the two eigenvalues

Page 46: Extração de Características

Computing Image Gradients

Page 47: Extração de Características

Corner Analysis– The ellipses indicate the eignvalues and eigenvectors

of the C matrices

Page 48: Extração de Características

Juiz Virtual

Tese de Flávio Szenberg

Page 49: Extração de Características

Modelos

F1

F6 F2

F3

F4 F5 F7

F8 F9

F1

F6 F2

F3

F4

F5

F8

F7

F9

Os modelos utilizados na tese:

Modelo de um campo de futebol

Modelo sem simetria

Page 50: Extração de Características

Filtragem para realce de linhas O filtro Laplaciano da Gaussiana (LoG) é aplicado à

imagem, baseado na luminância.

010141

010

121242121

161

filtro gaussiano

filtro laplaciano

Page 51: Extração de Características

Filtragem para realce de linhas Problemas com linhas duplas

Page 52: Extração de Características

Filtragem para realce de linhas A transformação negativa é aplicada entre o cálculo da

luminância e o filtro LoG.

Page 53: Extração de Características

Filtragem para realce de linhas Resultado de uma segmentação (threshold) feita na

imagem filtrada.

(em negativo para visualizar melhor)

Page 54: Extração de Características

Extração de segmentos de retas longos

O objetivo é localizar segmentos de retas longos candidatos a serem linhas da imagem do modelo.

O procedimento é dividido em dois passos:1. Eliminação de pontos que não estão sobre

nenhum segmento de reta. 2. Determinação de segmentos de retas.

Page 55: Extração de Características

Eliminando pontos que não estão sobre um segmento de reta

A imagem é dividida, por uma grade regular, em células retangulares.

Page 56: Extração de Características

Eliminando pontos que não estão sobre um segmento de reta

Para cada célula, os autovalores 1 e 2 (1 2) da matriz de covariância, dada abaixo, são calculados.

Se 2 = 0 ou 1/ 2 > M (dado) então

o autovetor de 1 é a direção predominante

senãoa célula não tem uma direção predominante

n

ii

n

iii

n

iii

n

ii

vvvvuu

vvuuuu

n1

2

1

11

2

1

1

2

vu ,

Page 57: Extração de Características

Eliminando pontos que não estão sobre um segmento de reta

Podemos atribuir pesos i aos pontos (resultado do LoG).

n

ii

n

iii

n

iii

n

ii

vvvvuu

vvuuuu

n1

2

1

11

2

1

n

iii

n

iiii

n

iiii

n

iii

n

ii vvvvuu

vvuuuu

1

2

1

11

2

1

1

Page 58: Extração de Características

Eliminando pontos que não estão sobre um segmento de reta

Células com pontos formando segmentos de retas:

Page 59: Extração de Características

Determinando segmentos de reta

As células são percorridas de modo que as linhas são processadas de baixo para cima e as células em cada coluna são processadas da esquerda para direita. Um valor é dado para cada célula: Se não existe uma direção predominate na célula, o valor é zero. Caso contrário, verifica-se os três vizinhos abaixo e o vizinho à

esquerda da célula corrente. Se algum deles tem uma direção predominante similar ao da célula corrente, quando unidos, então a célula corrente recebe o valor da célula que tem a direção mais similar; senão, um novo valor é usado para a célula corrente.

Page 60: Extração de Características

Determinando segmentos de reta São formados grupos com células de mesmo valor,

representados na figura abaixo por cores distintas.

Page 61: Extração de Características

Extração de segmentos de retaCada grupo fornece um segmento de reta.

A reta de equação v=au+b é encontrada por método de mínimos quadrados:

O segmento é obtido limitando a reta pela caixa envoltória dos pontos usados.

n

iii

n

iiii

n

ii

n

iii

n

iii

n

iii

v

vu

u

uu

ba

1

1

1

11

11

2

v

u

Page 62: Extração de Características

Extração de segmentos de retaOs segmentos de reta que estão sobre a mesma reta suporte são unidos, formando segmentos longos, usando mínimos quadrados.

No final do processo, tem-se um conjunto de segmentos de reta.

a

b

c

d

e

f

f1

f2f3

f4

f5f6

f7

Page 63: Extração de Características

Extração de segmentos de retaSobrepondo as linhas extraída na imagem, temos o seguinte resultado:

Page 64: Extração de Características

Reconhecimento dos segmentos

A partir do conjunto de segmentos, as linhas do modelo são detectadas e o modelo reconhecido [Grimson90].

Método baseado na Transformada de Hough.

Método de reconhecimento baseado em modelo.• Conjunto de restrições

Page 65: Extração de Características

Reconhecimento dos segmentos

F1 F7 F6F5F4F3F2f1:

f2:

F1

F6F2

F3

F4

F5 F7

Modelo

F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2

Árvore de Interpretaçãof1

f2f3

f4

f5f6

f7

Visualização

Método de Reconhecimento baseado em Modelo

Page 66: Extração de Características

O nó {f1: F1, f2:F6 , f3:F3} é discardado por que viola a restrição:

A linha representante de F6 deve estar entres as linhas que representam F1 e F3, na visualização.

F1 F7 F6F5F4F3F2

F1 F7 F6F5F4F3F2f1:

f2:

Árvore de Interpretação

F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2 F1 F7 F6F5F4F3F2

f3:

Reconhecimento dos segmentosDiscardando nós

F1

F6F2

F3

F4

F5 F7

Modelo

f1

f2

f3

f4

f5

Visualização

f6

f7

Page 67: Extração de Características

Reconhecimento dos segmentosProblema relacionado com a perspectiva

2

1222

122

1222

12

12122

1212

)()()()(

))(())((

vvuuvvuu

vvvvuuuu

ttttssss

ttssttss

8.0121

Page 68: Extração de Características

Reconhecimento dos segmentosProblema relacionado com a perspectiva

f1

f2

f3

Page 69: Extração de Características

Reconhecimento dos segmentosEscolhendo a melhor solução

F1

F6F2

F3

F4

F5 F7

Modelo

• Em geral, existem diversas interpretações possíveis;

• Escolhemos a interpretação onde a soma dos comprimentos dos segmentos representativos é máxima.

f1 : F4 f2 : F3 f3 : f4 : f5 : F6 f6 : F7 f7 : F1 Vencedor

f1

f2f3

f4

f5f6

f7

Visualização

f1 : F4 f2 : f3 : f4 : F3 f5 : F6 f6 : F7 f7 : F1

Page 70: Extração de Características

f1 : F2 f2 : F3 f3 : f4 : f5 : F6 f6 : F5 f7 : F1

f1 : F4 f2 : F3 f3 : f4 : f5 : F6 f6 : F7 f7 : F1

f1

f2f3

f4

f5

f6

f7

Visualização

Reconhecimento dos segmentos

F1

F6F2

F3

F4

F5 F7

ModeloResultado final

F7F1

F6F2

F3

F4

F5

Modelo

ou

Page 71: Extração de Características

Cálculo da transformação projetiva planar Uma transformação projetiva planar H (homografia) correspondente

às linhas reconhecidas é encontrada (usando pontos de interseção e pontos de fuga como pontos de referência).

Modelo reconstruído

H

pontos de interseção

pontos de fuga