22
Using dynamic Using dynamic programming for programming for solving solving variational variational problems in vision problems in vision Amir A. Amini, Terry E. Weymouth, Ramesh C. Jain Amir A. Amini, Terry E. Weymouth, Ramesh C. Jain IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE. 1990 INTELLIGENCE. 1990 Grupo de Discussões SINFO-UPD Grupo de Discussões SINFO-UPD Monica Matsumoto Monica Matsumoto 25/04/2008 25/04/2008

Using dynamic programming for solving variational problems in vision

Embed Size (px)

DESCRIPTION

Using dynamic programming for solving variational problems in vision. Amir A. Amini, Terry E. Weymouth, Ramesh C. Jain IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE. 1990 Grupo de Discussões SINFO-UPD Monica Matsumoto 25/04/2008. 1 - Cálculo Variacional. - PowerPoint PPT Presentation

Citation preview

Page 1: Using dynamic programming for solving variational problems in vision

Using dynamic Using dynamic programming for programming for

solving variational solving variational problems in visionproblems in vision

Amir A. Amini, Terry E. Weymouth, Ramesh C. JainAmir A. Amini, Terry E. Weymouth, Ramesh C. Jain

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE. 1990INTELLIGENCE. 1990

Grupo de Discussões SINFO-UPDGrupo de Discussões SINFO-UPDMonica Matsumoto Monica Matsumoto

25/04/200825/04/2008

Page 2: Using dynamic programming for solving variational problems in vision

1 - Cálculo Variacional1 - Cálculo Variacional

Problemas com funções de desempenho ou Problemas com funções de desempenho ou custocusto Controle: CUSTO Dispêndio de combustível ou de Controle: CUSTO Dispêndio de combustível ou de

energia para realizar uma dada tarefa, tempo para energia para realizar uma dada tarefa, tempo para transferir o sistema de um estado para o outro, transferir o sistema de um estado para o outro, RECOMPENSA lucro auferido com venda, massa da RECOMPENSA lucro auferido com venda, massa da carga transportada, tempo médio entre falhascarga transportada, tempo médio entre falhas

Visão: Encontrar superfície suave desejada, Visão: Encontrar superfície suave desejada, preservar descontinuidades, detecção de contornos, preservar descontinuidades, detecção de contornos, contornos ativoscontornos ativos

Problema de Maximização ou Minimização, Problema de Maximização ou Minimização, transformação por troca de sinal do funcionaltransformação por troca de sinal do funcional

Page 3: Using dynamic programming for solving variational problems in vision

1.1 - Cálculo Variacional – 1.1 - Cálculo Variacional – Um pouco de históriaUm pouco de história

Problema de Dido (850 ac)Problema de Dido (850 ac) Euclides, Arquimedes Euclides, Arquimedes

(287-212 ac)(287-212 ac) Apolônio (262-190 ac)Apolônio (262-190 ac) Fermat (1601-1665)Fermat (1601-1665) Isaac Newton (1642-1727)Isaac Newton (1642-1727) Leibniz (1646-1716)Leibniz (1646-1716) Lagrange (1736-1813)Lagrange (1736-1813) Galileu Galilei (1564-1643)Galileu Galilei (1564-1643) Johan Bernoulli (1667-Johan Bernoulli (1667-

1748)1748) James Bernoulli (1654-James Bernoulli (1654-

1705)1705) Leonard EulerLeonard Euler

Legendre (1752-1833)Legendre (1752-1833) Jacobi (1804-1851)Jacobi (1804-1851) Weierstrass (1815-1897)Weierstrass (1815-1897) Carl Gauss (1777-1855)Carl Gauss (1777-1855) Pierre Bonnet (1819-1892)Pierre Bonnet (1819-1892) Gaston Darboux (1819-Gaston Darboux (1819-

1892)1892) David Hilbert (1862-1943)David Hilbert (1862-1943) Willian Hamilton (1805-Willian Hamilton (1805-

1865)1865) Oscar Bolza (1857-1942)Oscar Bolza (1857-1942) Jacques Hadamard (1865-Jacques Hadamard (1865-

1963)1963)

...

Page 4: Using dynamic programming for solving variational problems in vision

1.2 - Cálculo Variacional: 1.2 - Cálculo Variacional: Problemas ClássicosProblemas Clássicos

Problema da braquistócronaProblema da braquistócrona Problemas isoperimétricosProblemas isoperimétricos GeodésicasGeodésicas Superfície de revolução com área Superfície de revolução com área

mínimamínima

Page 5: Using dynamic programming for solving variational problems in vision

1.2.1 – Problema da 1.2.1 – Problema da BraquistócronaBraquistócrona

Sejam A e B dois pontos dados em um plano vertical. Sejam A e B dois pontos dados em um plano vertical. O problema consiste em encontrar uma curva que O problema consiste em encontrar uma curva que uma partícula M precisa descrever para sair de A e uma partícula M precisa descrever para sair de A e chegar em B no menor tempo possível, somente sob chegar em B no menor tempo possível, somente sob ação da gravidade. John Bernoulli, 1696.ação da gravidade. John Bernoulli, 1696.

Page 6: Using dynamic programming for solving variational problems in vision

1.2.2 – Problemas 1.2.2 – Problemas IsoperimétricosIsoperimétricos

Quando queremos minimizar ou Quando queremos minimizar ou maximizar uma função impondo maximizar uma função impondo alguma restrição, como por exemplo alguma restrição, como por exemplo que uma outra função se mantenha que uma outra função se mantenha constante.constante.

Ex. Problema de DidoEx. Problema de Dido

Fundação de CartagoFundação de Cartago

Page 7: Using dynamic programming for solving variational problems in vision

1.2.3 - Geodésicas1.2.3 - Geodésicas

Dados dois pontos na superfícieDados dois pontos na superfície

g(x,y,z) = 0g(x,y,z) = 0

Qual é a equação do arco pertencente Qual é a equação do arco pertencente à superfície e ligando estes pontos, à superfície e ligando estes pontos, que tem o menor comprimento?que tem o menor comprimento?

Page 8: Using dynamic programming for solving variational problems in vision

1.2.4 – Superfície de 1.2.4 – Superfície de revolução de área mínimarevolução de área mínima

Dados dois pontos (xDados dois pontos (x11,y,y11) e (x) e (x22, y, y22) ) buscamos passar de um para o outro ao buscamos passar de um para o outro ao longo de um arco y=y(x) tal que a longo de um arco y=y(x) tal que a rotação desse arco sobre o eixo x gere rotação desse arco sobre o eixo x gere uma superfície de revolução cuja área uma superfície de revolução cuja área incluída em xincluída em x11≤x ≤x≤x ≤x22 seja mínima. seja mínima.

dxyyIx

x 2

1

2'12

Page 9: Using dynamic programming for solving variational problems in vision

Problema: minimização do funcionalProblema: minimização do funcional

2 - Método Variacional 2 - Método Variacional na Visãona Visão

1

´),,()(x

xo

dxyyxFyJ

Page 10: Using dynamic programming for solving variational problems in vision

2.1 – Condições 2.1 – Condições NecessáriasNecessárias

Condição de Euler-LagrangeCondição de Euler-Lagrange

Necessária, porém não suficienteNecessária, porém não suficiente

0´ yy FFdx

d

Page 11: Using dynamic programming for solving variational problems in vision

2.1 – Condições 2.1 – Condições NecessáriasNecessárias

Condição de LegendreCondição de Legendre

Elimina máximos relativos fracos das Elimina máximos relativos fracos das possíveis soluções.possíveis soluções.

0´´ yyF

Page 12: Using dynamic programming for solving variational problems in vision

2.1 – Condições 2.1 – Condições NecessáriasNecessárias

Condição de JacobiCondição de Jacobi

0)()´()´´()( ´´´´

xvFF

dx

dxvF

dx

dxvF yyyyyyyý

Page 13: Using dynamic programming for solving variational problems in vision

2.1 – Condições 2.1 – Condições NecessáriasNecessárias

Método de LagrangeMétodo de Lagrange Equação de Euler-Lagrange modificadaEquação de Euler-Lagrange modificada

FuncionalFuncional

hhii(x,y)=0, para i=1,2,...,m são restrições, têm de ser (x,y)=0, para i=1,2,...,m são restrições, têm de ser diferenciáveisdiferenciáveis

ii(x) são os multiplicadores de Lagrange(x) são os multiplicadores de Lagrange

0´ yydx

d

m

iii yxhxF

1

),()(

Page 14: Using dynamic programming for solving variational problems in vision

2.2 - Ressalvas2.2 - Ressalvas Equação de Euler-Lagrange é apenas Equação de Euler-Lagrange é apenas

necessárianecessária para otimalidade. Não para otimalidade. Não garante otimalidade absoluta ou relativa. garante otimalidade absoluta ou relativa.

Outras condições de ordem maior (e.g., Outras condições de ordem maior (e.g., Jacobi, Weierstrass) Jacobi, Weierstrass) geralmente difícil de testar, e geralmente difícil de testar, e não são suficientes para o caso geral. não são suficientes para o caso geral.

Teoria de cálculo variacional não descreve Teoria de cálculo variacional não descreve propriedades de minimizadores absolutos. propriedades de minimizadores absolutos. Garante solução para mínimo relativo do Garante solução para mínimo relativo do tipo fraco. tipo fraco.

Page 15: Using dynamic programming for solving variational problems in vision

2.2 - Continuação... 2.2 - Continuação... RessalvasRessalvas

A second issue of concern is to enforce possibly A second issue of concern is to enforce possibly nondifferentiable constraints on the solution. In many nondifferentiable constraints on the solution. In many vision applications, the ability to enforce vision applications, the ability to enforce hard hard constraintsconstraints on the solution is required. on the solution is required.

Lagrangian-based methods could turn the constrained Lagrangian-based methods could turn the constrained problem into an unconstrained problem. However, require problem into an unconstrained problem. However, require 1) higher dimensional spaces, since now there are 1) higher dimensional spaces, since now there are more more unknownsunknowns that must be dealt with, and that must be dealt with, and 2) 2) the constraints the constraints themselves must be differentiable. With dynamic themselves must be differentiable. With dynamic programming, constraints simply limit the set of programming, constraints simply limit the set of admissible solutions and in fact reduce the computational admissible solutions and in fact reduce the computational complexity.complexity.

Third issue of numerical stability and accuracy. In using Third issue of numerical stability and accuracy. In using variational approaches, there is a need for estimates of variational approaches, there is a need for estimates of higher order derivatives of discrete data. Computing high higher order derivatives of discrete data. Computing high order derivatives of discrete, noisy data leads to order derivatives of discrete, noisy data leads to numerical instabilitynumerical instability due to amplification of high due to amplification of high frequency noise content.frequency noise content.

Page 16: Using dynamic programming for solving variational problems in vision

3 - Relações entre Cálculo 3 - Relações entre Cálculo Variacional e Programação Variacional e Programação

DinâmicaDinâmica Princípio da Otimalidade (Bellman)Princípio da Otimalidade (Bellman)

Considere um ponto C pertencente a Considere um ponto C pertencente a uma trajetória AB. Se a trajetória AB uma trajetória AB. Se a trajetória AB for ótima partindo de A, então CB é for ótima partindo de A, então CB é ótima partindo de C.ótima partindo de C.

A

C

B

Page 17: Using dynamic programming for solving variational problems in vision

3 - Relações entre Cálculo 3 - Relações entre Cálculo Variacional e Programação Variacional e Programação

DinâmicaDinâmica Solução NuméricaSolução Numérica

]).,,([min)(1 vcxFcS v

)]().,,([min)( 1 vcSvcxFcS NvN

Page 18: Using dynamic programming for solving variational problems in vision

Custo baseado em energias internas e Custo baseado em energias internas e externasexternas

ondeonde

4 – Minimização de Energia 4 – Minimização de Energia em Contornos Ativosem Contornos Ativos

dssvEsvEsvEE conimagetotal ))](())(())(([1

0

int*

))(())(())(())(( svEwsvEwsvEwsvE termtermedgeedgelinelineimage

))()()(())((22

int svsvssvE sss

221 )())(( xxksvEcon

Page 19: Using dynamic programming for solving variational problems in vision

4 – Minimização de Energia 4 – Minimização de Energia em Contornos Ativosem Contornos Ativos

Iterativamente:Iterativamente:

ondeonde

t

iit

iio

tt CBxBx

0

111 )(

1)(

),(

IAB

yxfC ttxt

Page 20: Using dynamic programming for solving variational problems in vision

4 – Minimização de Energia 4 – Minimização de Energia em Contornos Ativosem Contornos Ativos

Page 21: Using dynamic programming for solving variational problems in vision

4 – Minimização de Energia 4 – Minimização de Energia em Contornos Ativosem Contornos Ativos

Na programação dinâmica, o Na programação dinâmica, o contorno ativo converge em um contorno ativo converge em um número finito de interações, já que a número finito de interações, já que a energia decresce monotonicamente energia decresce monotonicamente com o tempo.com o tempo.

Page 22: Using dynamic programming for solving variational problems in vision

5 - Conclusão5 - Conclusão

Dynamic programming is an attractive methodology for optimization since it bypasses local minima and allows for enforcement of hard constraints on the solution within a natural and straightforward structure.

Convergence of the algorithm is guaranteed, and so is the optimality of the solution. *