curvas spline e interpoladores – matemática, implementação

CURVAS SPLINE E INTERPOLADORES – MATEMÁTICA,
IMPLEMENTAÇÃO E ANÁLISE
Prati, Airton(IEAv/ EGI-A); Silva, João Camilo (idem) e Destro, José P B(idem)
RESUMO
Neste trabalho descreve-se a matemática das Splines e de interpoladores para aplicação no software CASA-F, desenvolvido na EGI-A, para processamento de imagens.
Assim, apresentam-se as equações das Splines e dos interpoladores. É feita análise comparativa entre métodos de interpolação (Splines e Lagrange) e de ajuste (Bezier, B
Splines), validando o polinômio interpolador adotado no Software CASA-F, utilizado para registro de imagens, mediante casamento de feições.
INTRODUÇÃO
O programa CASA-F, que objetiva o casamento de feições, foi desenvolvido a partir da expertise
advinda da integração do módulo INT e GEO do AEROGRAF, na Sub-Divisão de Apoio à Decisão (EGIA). Na confecção dos registros, pode-se verificar que havia diferença ligeiramente significativa no
ajuste das figuras (Imagem-base e Imagem-ajuste), quando se aplicavam polinômios de Lagrange, BSplines, ou Splines cúbicas. Logo, correspondeu à razão deste trabalho.
Atualmente, as curvas Spline permitem a solução de problemas de ajustes de curvas, através de
análise numérica, de computação gráfica, entre outros. Spline, em síntese, é a interpolação suave de
pontos através de um polinômio. Na maioria das aplicações, as curvas no grau 3 são suficientes.
Para validar o CASA-F, ou seja, testar o desempenho das funções, foram implementados os
interpoladores em Linguagem C++Builder- versão 6.0, bem como na Linguagem MatLab.
4 Curva de B-Spline
As curvas B-Splines são como as curvas de Bezier no fato que geralmente elas não passam por todos os pontos
dados. Elas podem ser de qualquer grau, mas aqui será abordada somente a forma cúbica.
As cúbicas B-Splines se assemelham as Splines cúbicas ordinárias, no fato que é derivada uma cúbica
separada para cada par de pontos do conjunto. Entretanto, a B-Spline não precisa passar por nenhum dos pontos
usados para sua definição.
A descrição será iniciada pelo estabelecimento da fórmula para a B-Spline cúbica em termos das equações
paramétricas cujo parâmetro é u.
Dados os pontos pi = (xi, yi), i = 0, 1, ..., n, a Spline cúbica para o intervalo (pi, pi+1), i = 1, 2, ..., n-1, é dada
por:
2
Bi (u) = ∑bk pi+k , onde.
k =−1
b−1 =
Definições
1. Interpoladores Spline
Uma curva Spline pode ser comparada a uma corda, que pode ser curvada de forma a passar por um conjunto de
pontos. Em algumas circunstâncias, f(x) pode ser descrita de forma aproximada por partes, composta por
polinômios de grau n, de tal forma que f(x) e suas (n-1) primeiras derivadas sejam contínuas sempre. Tal função é
chamada Spline, e os pontos xi, i = 0, 1, 2, ..., m são chamados nós.
1.1 Interpolador Spline Linear
Escrevendo a função Spline de grau 1 ou linear para o iésimo intervalo, que se situa entre os pontos (xi, yi) e
(xi+1,yi+1), obtém-se:
(x − xi )
(x − x)
Si (x) =
yi+1 + i+1
yi (1), que é válida para todo
i
i +1
hi
(1−u)3
u3
2
u3 u2 u 1
u3
, b0 = −u2 + , b1 = − + + + , b2 = , 0 ≤ u ≤1.
6
2
3
2 2 2 6
6
Como antes, pi refere-se ao ponto (xi, yi) que é um vetor de duas componentes. Os coeficientes, os bk’s,
servem como uma base e não mudam à medida que se passa de um conjunto de pontos para o próximo. A soma
ponderada, à medida que u varia de 0 a 1, gera a curva B-Spline.
Se forem explicitadas as equações para x e y a partir da equação (8), obtém-se:
1
1
1
1
xi (u) = (1−u)3 xi−1 + (3u3 −6u2 +4)xi + (−3u3 +3u2 +3u +1)xi+1 + u3xi+2
6
6
6
6
(9)
1
1
1
1
yi (u) = (1− u)3 yi−1 + (3u3 − 6u2 + 4) yi + (−3u3 + 3u2 + 3u +1) yi+1 + u3 yi+2
6
6
6
6
(10)
x ∈ [ x , x ].
hi
A Spline linear apresenta a desvantagem de ter derivada descontínua nos nós.
1.2 Interpolador Spline Cúbico
A função Spline de grau 3 ou cúbica para a iésima sub-região, entre os pontos ( xi, yi) e (xi+1,yi+1), é:
Si (x) =ai (x−xi )3 +bi (x−xi )2 +ci (x−xi ) +di
(2)
Então, a função Spline cúbica – S(x)=Si(x) no intervalo [xi, xi+1] para i = 0, 1, ..., m-1 - deve satisfazer as condições
de continuidade do gráfico, da inclinação e da curvatura em toda a região dos pontos considerados.
Aplicadas as condições acima, obtém-se:
y −y y −y 
hi −1Zi−1 + (2hi−1 + 2hi ) + hi Zi +1 = 6 i+1 i − i i−1 
hi−1 
 hi
= 6( f [ xi , xi+1 ] − f [ xi −1 , xi ]) (3)
Observe a notação aqui: xi(u) e yi(u) são funções de u e xi, yi são componentes do ponto pi.
Como um conjunto de quatro pontos é necessário para gerar somente uma porção da B-Spline, aquela
associada com os dois pontos internos, será necessário considerar como obter a B-Spline para mais do que quatro
pontos e também como estender a curva para a região fora do par intermediário. Será usado aqui um método
análogo ao das Splines cúbicas, avançando um ponto de cada vez, formando assim um novo conjunto de quatro
pontos. Será abandonado o primeiro ponto do conjunto anterior, quando um novo ponto é adicionado.
As condições que serão impostas sobre as B-Splines são exatamente as mesmas das Splines ordinárias –
continuidade da curva e de sua primeira e segunda derivadas. O resultado é tal que as equações para os fatores
de ponderação (os polinômios em u, os bk) são tais que esses requisitos são atendidos.
2. Comparação Gráfica dos Interpoladores e Curvas de Ajuste
Zi+1 − Zi
6hi
bi =
Zi
2
ci =
yi+1 − yi 2hi Zi + hi Zi+1
−
hi
6
(b)
(a)
Onde, Zi = Si′′(xi )
para i = 0, 1, ..., m-1 e Zm = Sm′ −1(xm) , e f [xi , xi+1] é a diferença dividida de ordem 1 de f(x).
A Equação (3) se aplica a cada um dos pontos internos, desde i = 1 até i = m-1, havendo um total de m+1 pontos.
Isto dá m-1 equações relacionando m+1 valores de Zi. Existem mais duas equações adicionais envolvendo Z0 e Zm,
ao se aplicar as condições específicas pertencentes aos extremos do intervalo da curva toda. Até certa extensão,
estas condições dos extremos são arbitrárias.
As condições de extremidade, Z0 = 0, Zm = 0, que fazem com que as cúbicas dos extremos se aproximem
linearmente nas suas extremidades, geram a chamada aproximação natural da curva Spline.
Depois de obtidos os valores Zi, deve-se obter os coeficientes ai, bi, ci e di para as cúbicas em cada intervalo.
ai =
(8)
di = yi , i = 0,1,L, m-1
A partir destas funções cúbicas, pode-se obter os pontos na interpolação da curva.
2. Interpolador de Lagrange
Seja x0, x1, ..., xn, (n+1) pontos distintos e yi = f(xi) para todo i = 0,1, ..., n. Seja p3(x), o polinômio de grau 3
que interpola f(x) em x0, x1, ..., xn. Então, podemos representar p3 (x) na forma de Lagrange por:
p3 ( x) = y0 L0 ( x) + y1 L1 ( x)+ y2 L2 ( x) + y3 L3 ( x)
Onde,
L0 ( x) =
( x − x1 )( x − x2 )( x − x3 )
( x − x0 )( x − x2 )( x − x3 )
( x − x0 )( x − x1 )( x − x3 )
( x − x0 )( x − x1 )( x − x2 )
; L1 ( x ) =
; L2 ( x) =
; L3 ( x) =
.
( x0 − x1 )( x0 − x2 )( x0 − x3 )
( x1 − x0 )( x1 − x2 )( x1 − x3 )
( x2 − x0 )( x2 − x1 )( x2 − x3 )
( x3 − x0 )( x3 − x1 )( x3 − x2 )
Como o interpolador cúbico de Lagrange necessita de três intervalos, ou seja, quatro pontos, o número de
subintervalos deve ser múltiplo de 3, para que seja possível gerar todos os polinômios cúbicos para interpolar o
intervalo desejado.
3. Curva de Bezier
As curvas de Bezier são muito utilizadas em computação gráfica. Essas curvas não são exatamente curvas de
interpolação, já que elas normalmente não passam por todos os pontos experimentais. São mais semelhantes às
curvas de ajuste dos mínimos quadrados.
Aqui será considerada apenas a versão cúbica dessas curvas. Para o seu desenvolvimento, será expresso y =
f(x) na forma paramétrica. A forma paramétrica representa uma relação entre x e y por duas outras equações, x =
f1(u), y = f2(u). A variável independente u é chamada de parâmetro. Quando x e y são expressos em termos de um
parâmetro u, (x(u), y(u)), 0 ≤ u ≤ 1, definem um conjunto de pontos (x, y), associados com os valores de u.
Suponha que foi dado um conjunto de pontos de controle, pi = (xi, yi), i = 0, 1, ..., n. Estes pontos podem ser
escolhidos sobre a tela do computador, usando um mouse. Os pontos não se sucedem necessariamente da esquerda
para a direita. Tratam-se as coordenadas de cada ponto como um vetor de duas componentes, ou seja,
 xi 
pi =  .
 yi 
O conjunto de pontos na forma paramétrica, é dado por
 x(u) 
P(u) = 
 , 0 ≤ u ≤1
 y(u)
O polinômio de grau n de Bezier determinado por n+1 pontos é dado por
n
n
n
n!
P(u) = ∑ (1−u)n−i ui pi , onde   =
i=0  i 
 i  i!(n −i)!
(4)
Para n = 3, (4) representaria a equação cúbica definida pelos quatro pontos, p0, p1, p2 e p3:
3
2
2
3
P(u) = (1−u) p0 +3(1−u) u p1 +3(1−u)u p2 +u p3 ,
Resultados
Neste ponto, fez-se análise matemática, para balizar cientificamente a comparação entre as curvas de
interpolação, validando a análise visual direta.
A aderência é quantificada mediante a estatística da diferença entre os valores obtidos pelas curvas de
interpolação contra os valores de referência, pelo cômputo do Desvio Médio Quadrático (RMS). Foram utilizados
50 pontos em cada subintervalo da função analisada.
Os resultados estão na Tabela 1 abaixo:
Tabela 1 Valores RMS das curvas de interpolação em relação à referência.
Curva
Desvio Médio Quadrático (RMS)
6 Intervalos
9 Intervalos
12 Intervalos
15 Intervalos
Spline Linear
0,46214
0,22374
0,12901
0,08348
Spline Cúbica Natural
0,33694
0,09364
0,04092
0,02229
B-Spline Cúbica
0,85139
0,52807
0,24261
0,27608
Bezier Cúbica
0,99622
0,75931
0,61254
0,51269
Lagrange Cúbica
0,55908
0,13910
0,09981
0,10500
Considerando os valores RMS como indicativos da aderência, a Curva Spline Cúbica Natural é a mais indicada,
pois exibe menor dispersão. Logo, é a recomendada para interpolação de valores característicos da curva de
referência, em síntese o tipo de feição a ser registrada pelo software CASA-F, quais sejam: contornos naturais,
rios, estradas, fronteiras etc. Na medida em que são aumentados os pontos escolhidos (à semelhança dos pontos de
contorno ou feições escolhidos para registro no software), ou seja, aumentando os intervalos, o desempenho entre
os métodos continua favorável à Spline Cúbica Natural.
Portanto, o método adotado pelo CASA-F - Spline Cúbica Natural – é o mais recomendado para interpolação dos
pontos escolhidos para registro de imagens..
CONCLUSÃO
(6)
A Spline cúbica natural reproduz as curvas com mais fidelidade, logo garantindo precisão superior do
registro. Adotando a condição de contorno – derivada segunda zero nos extremos – devem ser escolhidos dois
pontos de início e fim próximos, para garantir a precisão do ajuste nas extremidades. O custo computacional da
curva adotada tem pouca diferença das demais. A interpolação é feita apenas uma vez para cada registro. Para
modelagens livres, é recomendada a B-Spline, por sua flexibilidade.
(7)
Referências
(5)
A equação (5) representa o par de equações escalares seguinte:
x(u) =(1−u)3 x0 +3(1−u)2ux1 +3(1−u)u2x2 +u3x3
y(u) =(1−u)3 y0 +3(1−u)2uy1 +3(1−u)u2y2 +u3y3
Figura 1. Curva de referência: f(x) = 0,27∗
∗x + x∗
∗sen2(x) e interpoladas para: 6 intervalos (a), 9 intervalos (b).
Observe novamente que (x(0), y(0)) = p0 e (x(1), y(1)) = p3, e que a curva não irá geralmente passar pelos
pontos intermediários.
[1] RUGGIERO, M. A. e LOPES, V. L. R., Cálculo Numérico – Aspectos Teóricos e Computacionais, McGraw-Hill, São Paulo, 1988.