Quadrados Mı́nimos Lineares
e Deformações de Imagens
Bruno Henrique Cervelin∗
Depto de Matemática Aplicada, IMECC, UNICAMP,
13083-859,Campinas, SP
E-mail: [email protected],
Maria Aparecida Diniz Ehrhardt
Depto de Matemática Aplicada, IMECC, UNICAMP,
13083-859,Campinas, SP
E-mail: [email protected].
RESUMO
O método dos Quadrados Mı́nimos Lineares é uma das técnicas de aproximação mais popular.
Isto se deve à sua simplicidade e ao fato de que ao aplicarmos a aproximação a uma função,
f (x), dada, por exemplo, por medidas fı́sicas, a uma outra função, ϕ(x) =
m
P
αi gi (x), onde gi (x)
i=1
são conhecidos, reduzimos o erro associado às medidas, pois, geralmente, o número de pontos
que serão aproximados pela função aproximante é muito maior que m, o número de parâmetros
que devem ser estimados. Uma de suas grandes aplicações é na deformação de imagens [3]. Este
problema é amplamente estudado devido a suas aplicações como, por exemplo, na área médica
[5] e em animação [2].
A aproximação por quadrados mı́nimos é baseada em uma função que é a soma dos quadrados
das distâncias dos pontos a serem aproximados aos valores das medidas nos pontos. O objetivo
é que esta soma seja mı́nima.
Para o problema de deformações de imagens estamos interessados em encontrar uma transformação lv (p) para cada ponto v da imagem, de modo que lv (p) satisfaça
min
X
(wi )klv (pi ) − qi k22 ,
(1)
i
onde pi (posição dos pontos de controle na imagem original) e qi (posição dos pontos de controle
na imagem deformada) são vetores-linha e wi são pesos com a forma:
wi =
1
.
kpi − vk2α
2
(2)
e α pode ser considerado como um coeficiente de deformação (α > 1). Definindo a função de
deformação f como f (v) = lv (v), podemos ver que as três propriedades a seguir são satisfeitas:
• interpolação: f (pi ) = qi , para todo i = 1, · · · , m;
• suavidade: f deve produzir deformações suaves;
• identidade: se os pontos qi da imagem deformada são iguais a pi , então, neste caso, f deve
ser a função identidade (isto é: qi = pi → f (v) = v).
∗
bolsista de Iniciação Cientı́fica FAPESP
986
A função lv (x) é uma transformação afim e pode ser definida como:
lv (x) = xM + T,
(3)
onde M é uma matriz de transformação e T , uma translação. Com alguma manipulação
algébrica, a translação T pode ser removida. A escolha da matriz M se dá de acordo com
o tipo de deformação que queremos adotar. Entre as escolhas propostas em [3], optamos por
duas delas: deformações de similaridade e deformações rı́gidas.
• Deformações de similaridade:
Nestas deformações, além de satisfazer as propriedades explicitadas acima queremos que f
produza somente translações, rotações e mudanças uniformes de escala. Para isso devemos
limitar a escolha da matriz M em (3), de modo que M T M = λ2 I, com λ ∈ IR. Esse
método possui vantagens em relação a outras deformações como explicitado em [3], pois
preserva os ângulos da figura original, nos dando assim uma transformação mais real.
Porém pode haver mudanças de escala em algumas partes da figura, deformando assim a
figura de maneira não desejada.
• Deformações rı́gidas:
Para corrigir a mudança de escala limitamos ainda mais a escolha de M ; usamos agora
M tal que M T M = I. Esse tipo de deformação é chamado de deformação rı́gida e gera
imagens realı́sticas, pois mantém os ângulos e não faz mudanças de escala, mas seu custo
computacional é maior que a deformação de similiridade.
Apresentamos experimentos com deformações de imagens usando ambas as técnicas descritas acima.
Palavras-chave: Quadrados Mı́nimos Lineares, Deformação de Imagens, Deformação rı́gida e
de similaridade
Referências
[1] J.E. Dennis, R.B. Schnabel, Numerical Methods for Unconstrained Optimization and
Nonlinear Equations. SIAM, Philadelphia, PA, 1996.
[2] P. Fua, C. Miccio, Animated heads from ordinary images: a least squares approach.
Computer Vision and Image Understanding, Vol. 75, Nr. 3, pp. 247 - 259, 1999.
[3] S. Schaefer, T. McPhail, J. Warren, Image deformation using moving least squares.
ACM SIGGRAPH, pp. 533-540, 2006.
[4] G. Strang, Linear Algebra and its Applications. Third Edition, Harcourt Brace & Company International Edition, 1988.
[5] J. Warren, T. Ju, G. Eichele, C. Thaller, W. Chiu, J. Carson, A geometric
database for gene expression data. SGP’03: Proceedings of the 2003 Eurographics/ACM
SIGGRAPH symposium on Geometry processing, pp. 166 - 176, 2003
987