Análise de Deformação por Thin Plate Splines Fernando J. Von Zuben [email protected] Departamento de Engenharia de Computação e Automação Industrial

Análise de Deformação por Thin Plate Splines

Fernando J. Von [email protected]

Departamento de Engenharia de Computação e Automação IndustrialDCA/FEEC/Unicamp

2

Que atributos adotar para realizar a classificação de formas?

3

Exemplo: análise de contornos

4

Exemplo: análise de contornos

5

Variabilidade de formas

6

Uma vez definidos os atributos, resultam problemas de análise multivariada (extração de informação a partir de

pontos distribuídos num espaço multidimensional)

7

Atributo escolhido: número de lados

8

Problemas quando os atributos não discriminam as classes (Iris)

9

A forma da esquerda é mais próxima de qual forma da direita?

10

Comparar apenas aquilo que é comparável.

11

Quando há a possibilidade de definição de homologias, adotam-se pontos de referência (marcos)

12

Medir a deformação a partir do

deslocamento relativo de marcos

homólogos.

13

Critérios para a definição de marcos

14

Transformações de similaridade para uma forma específica com marcos já definidos

15

Transformação afim

16

Técnicas para casamento de marcos homólogos entre duas formas

17

Transformações com deformação nula

18

Como medir deformações a partir

do deslocamento relativo de marcos

homólogos?

19

Mecânica contínua:

deformação em uma lâmina.

20

Deforme uma lâmina inicialmente plana para que ela interpole os 5 pontos

21

Solução e energia de deformação associada

22

Quatro pontos em distribuição planar

23

Adição de um quinto ponto

24

Adição de um sexto ponto

25

Adição de um sétimo ponto

26

O que a deformação de uma lâmina para se ajustar a

pontos em 3 dimensões tem a ver com a deformação

envolvendo marcos homólogos em duas

dimensões?

27

Este é o slide mais importante da apresentação

Mapeia cada marco à esquerda no valor de x do marco homólogo à direita

Mapeia cada marco à esquerda no valor de y do marco homólogo à direita

28

Níveis de suavidade de

interpolações e aproximações

29

30

31

32

Mapeamentos com parâmetros de suavidade distintos

33

Qual é a diferença entre interpolação e aproximação?

34

-5 0 50

1

2

3

4

5

x

y

Solução encontrada

Exemplo de interpolação

35

Exemplos de aproximação a partir de dados amostrados com ruído

36

Aproximação a partir de dados amostrados com ruído

37

Retorno ao problema de medida de

deformação a partir de marcos

homólogos.

38

Deformação expressa na

forma de um “esgarçamento”

de uma grade inicialmente

uniforme

39

Spatial Normalisation

Original image

Templateimage

Spatially normalised

Deformation field

40

Deformation-based Morphometrylooks at absolute displacements.

Tensor-based Morphometry looksat local shapes

Morphometric approaches based on deformation fields

41

Quem deformou

mais?

42

Tópicos da Apresentação• O método dos quadrados mínimos

para modelos lineares nos parâmetros

• thin plate splines - 2D


• os limites da interpolação polinomial

• splines polinomiais suavizantes

• análise de componentes principais (PCA)

43

O método dos quadrados mínimos para modelos lineares nos parâmetros

• Problema a ser resolvido:

A partir de um conjunto de amostras de dados de entrada-saída, propor uma função que

mapeie os dados de entrada nos respectivos dados de saída.

44


• Modelo de regressão linear

• Dados de entrada-saída

m

jjjhwf

1)()( xx

Niii s 1, x

45


• Problema de otimização resultante

• Estratégia de Solução:Método dos Quadrados Mínimos (LMS)

N

i

m

jijji

N

iii hwsfsJ

1

2

11

2 )(min)(min)(min xxwwww

46


• do Cálculo Elementar sabe-se que a aplicação da condição de otimalidade (restrições atendidas pelos pontos de máximo e mínimo de uma função diferenciável) permite obter a solução ótima do problema de otimização , na forma:

– diferencie a função em relação aos parâmetros ajustáveis;

– iguale estas derivadas parciais a zero;

– resolva o sistema de equações resultante.

47


• no caso em questão, os parâmetros livres são os coeficientes da combinação linear, dados na forma do vetor de pesos

• o sistema de equações resultante é dado na forma:

, j=1,...,m.

Tmj www 1w

0)()(2)(211

N

iijii

N

i jii

jhfs

wffs

wJ xxx

48


• separando-se os termos que envolvem a incógnita f(), resulta:

, j=1,...,m.

• portanto, existem m equações para obter as m incógnitas

N

iiji

N

iij

m

rirr

N

iiji hshhwhf

11 11)()()()()( xxxxx

49


• para encontrar esta solução única do sistema de equações lineares, é interessante recorrer à notação vetorial:

)(

)( 1

Nj

j

j

h

h

x

xh

m

rNrr

m

rrr

N hw

hw

f

f

1

11

1

)(

)(

)(

)(

x

x

x

xf

Ns

s1

s

50


• como existem m equações, resulta:

• definindo a matriz H, com sua j-ésima coluna dada por hj, temos:

sh

sh

fh

fh

Tm

T

Tm

T

11

sf TT HH

51


)()()(

)()()()()()(

21

22221

11211

21

NmNN

m

m

m

hhh

hhhhhh

H

xxx

xxxxxx

hhh

52


• o i-ésimo componente do vetor f pode ser apresentado na forma:

• permitindo expressar f em função da matriz H, de modo que:

f = Hw

wxxxxx

m

rimiiirrii hhhhwff

121 )()()()()(

53


• substituindo no sistema de equações lineares, resulta a solução ótima para o vetor de coeficientes da combinação linear:

• esta equação de solução do problema dos quadrados mínimos é conhecida como equação normal. Para que exista a inversa de HTH, basta que a matriz H tenha posto completo, já que m N.

swsw TTTT HHHHHH1

54


• o modelo de regressão linear mais simples é a reta, aplicada nos casos em que a entrada é escalar:

)()()( 2211 xhwxhwxf

1)(1 xh xxh )(2

55


• suponha que foram amostrados, na presença de ruído, três pontos da curva y = x, gerando o conjunto de amostragem:

• obviamente, não se conhece a equação da curva, mas apenas estes três pontos amostrados.

)1.3,3(),8.1,2(),1.1,1(),( 31 iii sx

56


• para estimar w1 e w2, vamos proceder de acordo com os passos do método dos quadrados mínimos.

312111

)()()()()()(

3231

2221

1211

xhxhxhxhxhxh

H

1.38.11.1

s

101

sw TT HHH

57


• para o mesmo conjunto de dados amostrados, suponha agora que:

• enquanto no caso anterior tínhamos m < N, agora temos m = N.

)()()()( 332211 xhwxhwxhwxf

1)(1 xh xxh )(22

3 )( xxh

58


• o efeito da adição da função-base extra h3(x) representa a adição de uma coluna junto à matriz H, e a solução assume a forma:

941

)()()(

33

23

13

3

xhxhxh

h

3.02.0

1w

0 1 2 3 40

0.5

1

1.5

2

2.5

3

3.5

4

x

y

59


• observe que ambos os modelos (com 2 ou 3 funções-base) são lineares nos parâmetros (daí a denominação de regressão linear), embora para m = 3 tenhamos um modelo não-linear.

• modelo não-linear, mas linear nos parâmetros.

60


• funções de base radial como funções-base

Pontos amostrados: (1,2); (3,7); (5,6)

0 2 4 6 8 100

0.2

0.4

0.6

0.8

1

61


0 2 4 6 8 100

1

2

3

4

5

6

0 2 4 6 8 100

1

2

3

4

5

6

7

8


62


• funções de base radial como funções-base

Pontos amostrados: (1,2); (3,7); (5,6); (8,1)

0 2 4 6 8 100

0.2

0.4

0.6

0.8

1

63



0 2 4 6 8 100

1

2

3

4

5

6

0 2 4 6 8 100

1

2

3

4

5

6

7

8

64


determinação dos centros e aberturas das funções de base radial

modelo não-linear nos parâmetros

),,(),,(),,()( 333322221111 xachwxachwxachwxf

65

Tópicos da Apresentação• O método dos quadrados mínimos para modelos

lineares nos parâmetros

• thin plate splines - 2D• thin plate splines - 3D




66

Thin Plate Splines - 2D

-3 -2 -1 0 1 2 30

2

4

6

8

10

x

f(x)

f(x) = r2(x) = x2

-3 -2 -1 0 1 2 3-6

-5

-4

-3

-2

-1

0

1

2

x

g(x)

g(x)=log(r) = log(|x|)

67


-3 -2 -1 0 1 2 3-2

0

2

4

6

8

10

x

U(x)

U(x) = r2log(r) = x2log(|x|)

68


-3 -2 -1 0 1 2 3-2

0

2

4

6

8

10

x

U(x 1)

U(x 1)=(x 1)2log(|x 1|)

-3 -2 -1 0 1 2 3-2

0

2

4

6

8

10

x

U(x+1)

U(x+1)=(x+1)2log(|x+1|)

69


• Interpole os pontos pi, i=1,...,5, apresentados a seguir, de tal modo que a função interpolada seja totalmente plana para |x| e minimize o seguinte critério:

X

dxdx

hd2

2

2

)3,5();2,3();4,1()1,1();2,4(:),(

543

21

pppppyxp iii

70


-5 0 50

1

2

3

4

5

x

y

Pontos a serem interpolados

71


• função de interpolação que minimiza o critério:

• superfície planar para |x| :

5

110 )(

iii xxUwxaay

5

10

iiw

5

10

iii xw

72


• resulta, então, o seguinte sistema de equações lineares, a ser resolvido em

• modelo não-linear, mas linear nos parâmetros.

5432110 ,,,,,, wwwwwaa

73


5

5

15510

4

5

14410

3

5

13310

2

5

12210

1

5

11110

)(

)(

)(

)(

)(

yxxUwxaa

yxxUwxaa

yxxUwxaa

yxxUwxaa

yxxUwxaa

iii

iii

iii

iii

iii

00

5544332211

54321

xwxwxwxwxwwwwww

74

Thin Plate Splines - 2D• o sistema linear pode ser expresso em uma forma mais condensada, tomando-

se os vetores y e w e matriz L a seguir:

Tyyyyy 0054321y

Twwwwwaa 5432110w

54321

55453525155

54443424144

53433323133

52423222122

51413121111

001111100

)()()()()(1)()()()()(1)()()()()(1)()()()()(1)()()()()(1

xxxxx

xxUxxUxxUxxUxxUxxxUxxUxxUxxUxxUxxxUxxUxxUxxUxxUxxxUxxUxxUxxUxxUxxxUxxUxxUxxUxxUx

L

yLwyLw 1

75


5

110 )(

iii xxUwxaay

T

Twwwwwaa

1199.04036.05867.03958.00928.00743.02511.05432110

w

-5 0 50

1

2

3

4

5

x

y

Solução encontrada

76




• thin plate splines - 3D• os limites da interpolação polinomial



77


222 ),(),( yxyxryxf 22log),(log),( yxyxryxg

78


22222 log),(log),(),( yxyxyxryxryxU

79

Thin Plate Splines - 3D• Interpole os pontos pi, i=1,...,4, apresentados a seguir, de

tal modo que a função interpolada seja totalmente plana para (|x|,|y|) (,) e minimize o seguinte critério:

X YX Ydxdy

yh

yxh

xhdxdyyxh

yx

2

2

2222

2

22

2

2

2

22),(

);1,0,1();1,0,1();1,1,0();1,1,0(:),,(

43

21

ppppzyxp iiii

80


• função de interpolação que minimiza o critério:

• superfície planar para (|x|,|y|) (,):

4

1210 ,

iiii yyxxUwyaxaaz

4

10

iiw

4

10

iii xw

4

10

iii yw

81


• resulta, então, o seguinte sistema de equações lineares, a ser resolvido em 4321210 ,,,,,, wwwwaaa

4

4

14442410

3

4

13332310

2

4

12222210

1

4

11112110

,

,

,

,

zyyxxUwyaxaa

zyyxxUwyaxaa

zyyxxUwyaxaa

zyyxxUwyaxaa

iiii

iiii

iiii

iiii

00

0

44332211

44332211

4321

ywywywywxwxwxwxw

wwww

82

Thin Plate Splines - 3D• pode ser expresso em uma forma mais condensada, tomando-se

os vetores z e w e matriz L a seguir: Tzzzz 0004321z

Twwwwaaa 4321210w

4321

4321

444434342424141444

434333332323131333

424232322222121222

414131312121111111

000000

1111000),(),(),(),(1),(),(),(),(1),(),(),(),(1),(),(),(),(1

yyyyxxxx

yyxxUyyxxUyyxxUyyxxUyxyyxxUyyxxUyyxxUyyxxUyxyyxxUyyxxUyyxxUyyxxUyxyyxxUyyxxUyyxxUyyxxUyx

L

zLwzLw 1

83


4

1210 ,

iiii yyxxUwyaxaaz

TTwwwwaaa

7213.07213.07213.07213.00004321210

w

84

Thin Plate Splines - 3D tem-se agora uma ferramenta poderosa para gerar superfícies

de interpolação que minimizam uma dada medida de deformação;

isto implica que, sob o ponto de vista da medida de deformação adotada, a superfície obtida é a mais suave possível, dentre aquelas que interpolam pontos no 3;

sendo assim, é possível empregar estas superfícies de interpolação para explicar deformações produzidas por deslocamentos em marcos, os quais constituem um conjunto finito de pontos no 2;

85

Thin Plate Splines - 3D• conjunto de n marcos de consenso:

• conjunto arbitrário de marcos homólogos:

• como explicar o que ocorre com todos os demais pontos no 2 quando se desloca os marcos de consenso até que eles coincidam com os marcos arbitrários (ou vice-versa)?

nn yxyxyx ,,...,,,, 2211

nn yxyxyx ,,...,,,, 2211

86

Thin Plate Splines - 3D• este mapeamento do 2 para o 2 será decomposto em

dois mapeamentos do 2 para o 1 tal que:

– mapeamento 1: é tal que deve realizar os mapeamentos, i=1,...,n, além de minimizar a mesma medida de deformação considerada acima

– mapeamento 2: é tal que deve realizar os mapeamentos, i=1,...,n, além de minimizar a mesma medida de deformação considerada acima

iii xyx ,

iii yyx ,

87

Thin Plate Splines - 3D sendo assim, os dois mapeamentos acima vão produzir as mais

suaves dentre as superfícies que interpolam pontos no 3, sob o ponto de vista da medida de deformação adotada;

os pontos a serem interpolados certamente vão indicar o quanto a superfície no 3 deve se deformar para ser capaz de realizar a interpolação;

sendo assim, é intuitivo que qualquer medida de deformação que indique o que acontece quando se desloca os marcos de consenso até que eles coincidam com os marcos arbitrários (ou vice-versa) seja dada pela soma da deformação nas 2 superfícies no 3;

88

Thin Plate Splines - 3D• marcos de consenso:

• marcos homólogos:

• Observa-se que não houve deslocamento no eixo x, mas apenas no eixo y. É evidente, portanto, que o mapeamento 1, definido acima, vai produzir um hiperplano, enquanto o mapeamento 2 vai apresentar uma deformação para possibilitar a correspondente interpolação.

0,1,1,0,0,1,1,0

25.0,1,25.1,0,25.0,1,75.0,0

89


X YX Ydxdy

yh

yxh

xhdxdyyxh

yx

2

2

2222

2

22

2

2

2

22),(

TTwwwwaaa 00000104321210 w

);1,0,1();0,1,0();1,0,1();0,1,0(:),,(

43

21

ppppzyxp iiii

90


91


X YX Ydxdy

yh

yxh

xhdxdyyxh

yx

2

2

2222

2

22

2

2

2

22),(

);25.0,0,1();25.1,1,0();25.0,0,1();75.0,1,0(:),,(

43

21

ppppzyxp iiii

T

Twwwwaaa

1803.01803.01803.01803.01004321210

w

92


93





• os limites da interpolação polinomial• splines polinomiais suavizantes


94

Os limites da interpolação polinomial

• Considere uma função f C[a,b] e um polinômio pn(x) que interpole f(x) exatamente em n+1 pontos no intervalo [a,b]. Tomando uma seqüência de polinômios pn(x), com n , não é possível garantir que pn(x) convirja para f(x) em [a,b].

• Repare que, quando se toma n , o que se busca é interpolar todos os pontos de f, o que equivale à tentativa de se aproximar a função f pelo polinômio de ordem infinita pn.

95






• splines polinomiais suavizantes• análise de componentes principais (PCA)

96

Splines polinomiais suavizantes

• para aumentar a flexibilidade de processos de aproximação utilizando polinômios, é interessante trabalhar com polinômios de ordem reduzida e dividir o intervalo de aproximação em subintervalos menores. Apesar de permitir um ganho natural de flexibilidade, a aproximação polinomial por partes não mais assegura a suavidade, nem mesmo a continuidade da aproximação.

• splines polinomiais suavizantes:

b

a

n

jjjf

duu

ufxfyn

f2

2

2

1

2 )()(1minarg

97








98

Análise de Componentes Principais (PCA)

• a seqüência de componentes principais de um conjunto de dados no p fornecem as melhores aproximações lineares para os dados.

• tomando q < p componentes principais de um conjunto de N pontos no p, representados na forma , então a melhor aproximação linear destes N pontos é dada por:

• onde p é um vetor deslocamento, os componentes principais são ortonormais entre si, e q.

qipiv 1

Nipix 1

qqqq fvvvf V)(),...,,( 221121

qipiv 1

qpq

V

99


• f() é a representação paramétrica de um hiperplano no q.

• as figuras a seguir ilustram, para q = 1 e q = 2, as melhores aproximações lineares para p = 2 (pontos distribuídos no 2) e p = 3 (pontos distribuídos no 3), respectivamente.

100


101


• nas figuras acima, os hiperplanos minimizam a soma do quadrado da distância de cada um dos N pontos no p ao respectivo hiperplano.

• isto implica que os componentes principais, ainda não obtidos, resolvem o seguinte problema de quadrados mínimos:

• Problema: como obter os componentes principais de uma distribuição de pontos ?

N

iiqix

qi 1

2

,,min V

V

Nipix 1

102


1. expresse os N pontos no p na forma de uma matriz

2. obtenha a decomposição em valores singulares de X, dada por

3. para qualquer q < p, os q componentes principais correspondem às q primeiras colunas de V.

Exemplo: Redução de dimensão e compressão de dados

Considere um conjunto de dados composto por N = 130 números ‘3’ escritos à mão e armazenados em escala de cinza num grid 1616.

pNX

TUDVX

103


104


• cada uma das imagens pode ser entendida como um ponto no

• calculando os 2 primeiros componentes principais, resulta:

256ix

Documents

Análise de Deformação por Thin Plate Splines Fernando J. Von Zuben [email protected] Departamento de Engenharia de Computação e Automação Industrial