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

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

Edgedels = edge elements

Tipos de arestasdegrau(step) rampa(ramp)

cume(roof) impulso(spike)

Gráfico sem e com ruído

Derivadas e arestas

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

Série de Taylor

)()(2

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

2' xOxf

xxfxxfxxf

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)

Aproximações para derivadas

(a-b) 2/)( 11'

iii fff 2/)( 11'

iii fff

(a+b) )2( 11"

iiii ffff )2( 11"

iiii ffff

f(x)

x

fi-1fi fi+1

i+1ii-1

Em 2D

y

fx

f

yxf ),(

Gradiente

Laplaciano

2

2

2

22 ),(

y

f

x

fyxf

x

yxfyxf

x

yxf mnmn

,,, 1

x

yxfyxf

y

yxf mnmn

,,, 1

11

1

1

Convolution Kernels

141

4204

141

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

Finite differences

11* II x

1

1*II y

IKhurram Hassan-Shafique

Classical Operators

Prewitt’s Operator

11

11

11

1

1

11

Smooth Differentiate

101

101

101

111

000

111

111

111

Khurram Hassan-Shafique

Classical Operators

Sobel’s Operator

11

22

11

1

1

11

SmoothDifferentiate

101

202

101

121

000

121

121

121

Khurram Hassan-Shafique

• Sobel Edge Detector

Detecting Edges in Image

Image I

101

202

101

121

000

121

*

*

Idx

d

Idy

d

22

Idy

dI

dx

d

ThresholdEdges

Khurram Hassan-Shafique

Sobel Edge Detector

Idx

d

Idy

d

I

Khurram Hassan-Shafique

Sobel Edge Detector

I

22

I

dy

dI

dx

d

100 ThresholdKhurram Hassan-Shafique

Marr and Hildreth Edge Operator

• Smooth by Gaussian

• Use Laplacian to find derivatives

IGS * 2

22

2

2

1

yx

eG

Sy

Sx

S2

2

2

22

Khurram Hassan-Shafique

Marr and Hildreth Edge Operator

IGIGS ** 222

2

22

22

22

3

2 22

1

yx

eyx

G

Khurram Hassan-Shafique

Marr and Hildreth Edge Operator

2

22

22

22

3

2 22

1

yx

eyx

G

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

Marr and Hildreth Edge Operator

Zero CrossingsDetection

I ImageG2*

IG *2 Edge Image

IG *2 Zero Crossings

Khurram Hassan-Shafique

1

6

3

Khurram Hassan-Shafique

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

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

Hai Tao

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 05220

2 91540

156939

.

.

.

a

a

a

a

1

2

3

4

1

01486768717

0 2087553476

1244653939

0 7912446531

2

.

.

.

.

Camillo J. Taylor

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

h xd

dxe

xe

x x

( ) ( )

2

2

2

222

2

Camillo J. Taylor

Derivative of GaussianCanny

Canny Edge Detector

• Convolution with derivative of Gaussian

• Non-maximum Suppression

• Hysteresis Thresholding

Khurram Hassan-Shafique

Algorithm Canny_Enhancer• Smooth by Gaussian

IGS * 2

22

2

2

1

yx

eG

Tyx

T

SSSy

Sx

S

22yx SSS

x

y

S

S1tan Khurram Hassan-Shafique

• Compute x and y derivatives

• Compute gradient magnitude and orientation

Canny Edge Operator

IGIGS ** T

y

G

x

GG

T

Iy

GI

x

GS

**

Khurram Hassan-Shafique

Canny Edge Detector

xS

yS

I

Khurram Hassan-Shafique

Canny Edge Detector

I

22yx SSS

25 ThresholdS

Khurram Hassan-Shafique

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

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

yxSyxSyxS

yxM

yx ,

yx,

yx ,

Khurram Hassan-Shafique

Non-Maximum Suppression

0

12

3

41420tan41422- :3

41422tan :2

41422tan41420 :1

41420tan41420 :0

.θ.

.θ

.θ.

.θ.-

x

y

S

Sθ tan

Khurram Hassan-Shafique

Non-Maximum Suppression

22yx SSS M

25ThresholdM

Khurram Hassan-Shafique

Hysteresis Thresholding

Khurram Hassan-Shafique

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

Hysteresis Thresholding

M 25ThresholdM

15

35

Low

High

Khurram Hassan-Shafique

Resultado de algoritmo de histerese

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.

a

bx

yyya

yyb

cbay

cbay

cy

cbxaxxy

2

);0())1()1((2

1

));1()1((2

1

)1(

;)1(

;)0(

)(

max

2

0 1-1

Derivadas direcionais

y

n

y

f

x

n

x

f

n

f

x

y

f(x,y)

y

x

n

nn

h

pfnhpf

n

pfh

)()(lim

)(0

yx ny

fn

x

f

n

f

nfn

f

y

xyx n

n

y

f

x

f

y

fx

f

nnn

f

n

f

n

f

2

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

EEE

EEEEE

E

EC

Camillo J. Taylor

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

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

Computing Image Gradients

Corner Analysis– The ellipses indicate the eignvalues and eigenvectors

of the C matrices

Juiz Virtual

Tese de Flávio Szenberg

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

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

imagem, baseado na luminância.

010

141

010

121

242

121

16

1

filtro gaussiano

filtro laplaciano

Filtragem para realce de linhas Problemas com linhas duplas

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

luminância e o filtro LoG.

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

imagem filtrada.

(em negativo para visualizar melhor)

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.

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

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

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ão

a célula não tem uma direção predominante

n

ii

n

iii

n

iii

n

ii

vvvvuu

vvuuuu

n

1

2

1

11

2

1

1

2

vu ,

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

n

1

2

1

11

2

1

n

iii

n

iiii

n

iiii

n

iii

n

ii vvvvuu

vvuuuu

1

2

1

11

2

1

1

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

Células com pontos formando segmentos de retas:

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.

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

representados na figura abaixo por cores distintas.

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

b

a

1

1

1

11

11

2

v

u

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

f5

f6

f7

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

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

Reconhecimento dos segmentos

F1 F7 F6F5F4F3F2

f1:

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

f5

f6

f7

Visualização

Método de Reconhecimento baseado em Modelo

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 F6F5F4F3F2

f1:

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

Reconhecimento dos segmentosProblema relacionado com a perspectiva

2

1222

122

1222

12

12122

1212

)()()()(

))(())((

vvuuvvuu

vvvvuuuu

ttttssss

ttssttss

8.01

21

Reconhecimento dos segmentosProblema relacionado com a perspectiva

f1

f2

f3

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

f5

f6

f7

Visualização

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

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

F7

F1

F6F2

F3

F4

F5

Modelo

ou

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