View
213
Download
0
Category
Preview:
Citation preview
Análise de Deformação por Thin Plate Splines
Fernando J. Von Zubenvonzuben@dca.fee.unicamp.br
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
• thin plate splines - 3D
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• Modelo de regressão linear
• Dados de entrada-saída
m
jjjhwf
1)()( xx
Niii s 1, x
45
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
)()()(
)()()()()()(
21
22221
11211
21
NmNN
m
m
m
hhh
hhhhhh
H
xxx
xxxxxx
hhh
52
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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 método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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 método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
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
)()()()( 332211 xhwxhwxhwxf
62
O método dos quadrados mínimos para modelos lineares nos parâmetros
• 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
O método dos quadrados mínimos para modelos lineares nos parâmetros
)()()()( 332211 xhwxhwxhwxf
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
O método dos quadrados mínimos para modelos lineares nos parâmetros
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
• os limites da interpolação polinomial
• splines polinomiais suavizantes
• análise de componentes principais (PCA)
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
Thin Plate Splines - 2D
-3 -2 -1 0 1 2 3-2
0
2
4
6
8
10
x
U(x)
U(x) = r2log(r) = x2log(|x|)
68
Thin Plate Splines - 2D
-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
Thin Plate Splines - 2D
• 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
Thin Plate Splines - 2D
-5 0 50
1
2
3
4
5
x
y
Pontos a serem interpolados
71
Thin Plate Splines - 2D
• 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
Thin Plate Splines - 2D
• 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
Thin Plate Splines - 2D
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
Thin Plate Splines - 2D
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
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• os limites da interpolação polinomial
• splines polinomiais suavizantes
• análise de componentes principais (PCA)
77
Thin Plate Splines - 3D
222 ),(),( yxyxryxf 22log),(log),( yxyxryxg
78
Thin Plate Splines - 3D
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
Thin Plate Splines - 3D
• 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
Thin Plate Splines - 3D
• 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
Thin Plate Splines - 3D
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
Thin Plate Splines - 3D
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
Thin Plate Splines - 3D
91
Thin Plate Splines - 3D
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
Thin Plate Splines - 3D
93
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
• os limites da interpolação polinomial• splines polinomiais suavizantes
• análise de componentes principais (PCA)
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
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
• os limites da interpolação polinomial
• 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
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
• os limites da interpolação polinomial
• splines polinomiais suavizantes
• análise de componentes principais (PCA)
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
Análise de Componentes Principais (PCA)
• 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
Análise de Componentes Principais (PCA)
101
Análise de Componentes Principais (PCA)
• 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
Análise de Componentes Principais (PCA)
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
Análise de Componentes Principais (PCA)
104
Análise de Componentes Principais (PCA)
• cada uma das imagens pode ser entendida como um ponto no
• calculando os 2 primeiros componentes principais, resulta:
256ix
Recommended