Nyare teoriar om demensomsorg

A programac¸˜ao dinˆamica pode ser aplicada a diversos problemas de otimizac¸˜ao. Problemas dessa natureza geralmente apresentam muitas soluc¸˜oes poss´ıveis, onde cada soluc¸˜ao apre- senta um valor de custo diferente. Dessa forma, estamos interessados em encontrar um valor ´otimo para a soluc¸˜ao referente a um valor de custo m´ınimo ou m´aximo (dependendo de como a func¸˜ao de custo for definida), dentre todas as soluc¸˜oes poss´ıveis.

A.2 Programa¸c˜ao Dinˆamica 111

Em geral, o desenvolvimento de um algoritmo de programac¸˜ao dinˆamica pode ser divi- dido em uma seq¨uˆencia de quatro etapas [Cormem et al., 1999]:

1. Caracterizar a estrutura de uma soluc¸˜ao ´otima;

2. Definir recursivamente o valor de uma soluc¸˜ao ´otima;

3. Calcular o valor de uma soluc¸˜ao ´otima em um processo bottom-up; 4. Construir uma soluc¸˜ao ´otima a partir de informac¸˜oes calculadas.

As etapas de 1 a 3 acima formam a base para a soluc¸˜ao de um problema utilizando programac¸˜ao dinˆamica. A etapa 4 pode ser omitida se apenas o valor de uma soluc¸˜ao ´otima ´e exigido, n˜ao a soluc¸˜ao em si.

Podemos transformar o problema da correspondˆencia em vis˜ao est´ereo em um problema de minimizac¸˜ao de uma func¸˜ao de custo. A Programac¸˜ao Dinˆamica nos oferece uma forma de minimizar func¸˜oes compostas por um grande n´umero de vari´aveis discretas. Ela funciona como um m´etodo de divis˜ao e conquista, ou seja, resolve problemas combinando as soluc¸˜oes dos diversos subproblemas envolvidos. Entretanto, ao contr´ario dos m´etodos de divis˜ao e conquista, a Programac¸˜ao Dinˆamica ´e aplic´avel quando os subproblemas s˜ao interdepen- dentes, ou seja, compartilham soluc¸˜oes. Dessa forma, ao inv´es de tentarmos casar pares de pixels independentemente nas imagens, um conjunto de pixels em uma imagem pode ser associado, com base em um crit´erio adotado, a um conjunto de pixels correspondentes na outra imagem.

Assumindo que as imagens usadas est˜ao retificadas, o problema de obtermos a corres- pondˆencia entre dois perfis de caracter´ısticas pode ser formulado como um problema de encontrar um caminho ´otimo em um grid bidimensional. Na FiguraA.3o eixo vertical re- presenta o perfil de caracter´ısticas de uma linha na imagem da esquerda enquanto que, o eixo horizontal exibe o perfil de uma linha na imagem da direita. Um pontoP (i, j) no caminho

exibido representa o custo da correspondˆencia entre os pontosi e j, nas imagens da esquerda

e da direita, respectivamente.

T´ecnicas de Programac¸˜ao Dinˆamica s˜ao usadas para, eficientemente, encontrar o cami- nho de custo ´otimo dentre os v´arios caminhos poss´ıveis. Da observac¸˜ao da Figura A.3, percebe-se que, se a superf´ıcie da cena observada ´e cont´ınua e toda parte da superf´ıcie pode ser vista em ambas as imagens, o caminho gerado ´e cont´ınuo e monotonicamente crescente. Vamos assumir queD(i, j) representa a diferenc¸a de intensidade entre dois pixels i e j,

A.2 Programa¸c˜ao Dinˆamica 112 caminho imagem da direita imagemdaesquer da p j i

Figura A.3: Correspondˆencia via Programac¸˜ao Dinˆamica. Representac¸˜ao do caminho de custo ´otimo na computac¸˜ao da correspondˆencia entre linhas epipolares correspondentes nas imagens de entrada.

pode ent˜ao ser definido como a integral dessas diferenc¸as ao longo do caminho. SejaF (i, j)

o custo m´ınimo associado a um caminho ´otimo do ponto inicial at´e o ponto(i, j). Podemos

definir um algoritmo de Programac¸˜ao Dinˆamica para calcular o caminho m´ınimo com base no Algoritmo8, onden corresponde ao n´umero de pixels em uma linha da imagem.

Algoritmo 8 Algoritmo para resolver o problema da correspondˆencia a partir de t´ecnicas de Programac¸˜ao Dinˆamica. { PASSO (1) } F (i, 1) ← D(i, 1) F (1, j) ← D(1, j) { PASSO (2) } para 2 < i, j < n fac¸a

F (i, j) ← D(i, j) + min{D(i − 1, j − 1), F (i − 2, j − 1) + D(i − 1, j), F (i − 1, j − 2) + D(i, j − 1)}

fim para ´

E importante notarmos que no Algoritmo8, somente 3 arcos s˜ao poss´ıveis de serem ge- rados em cada passo da iterac¸˜ao, veja Figura A.4. Essa ´e uma restric¸˜ao intencional, pois poder´ıamos permitir a gerac¸˜ao de arcos em todas as direc¸˜oes poss´ıveis, entretanto, em qual- quer caso, por restringirmos a direc¸˜ao, a ´area de busca tamb´em fica severamente restrin- gida. Essas restric¸˜oes s˜ao conseq¨uˆencias das restric¸˜oes de continuidade e ordem que o al- goritmo imp˜oe, que ´e equivalente a dizer que somente caminhos estritamente monotˆonicos

A.2 Programa¸c˜ao Dinˆamica 113

s˜ao admiss´ıveis [Faugeras, 1993]. Como conseq¨uˆencia, a correspondˆencia est´ereo usando Programac¸˜ao Dinˆamica ´e mais adequada quando, por exemplo, as imagens s˜ao relativas a fotos a´ereas de terrenos planos [Huguet et al., 2004].

i

j

Figura A.4: Arcos poss´ıveis que levam `a correspondˆencia (i, j) na correspondˆencia via

Programac¸˜ao Dinˆamica.

Vale ressaltar que, se as cenas incluem descontinuidades nas superf´ıcies, o passo (2) do algoritmo de programac¸˜ao dinˆamica acima deve ser modificado para se adequar ao problema. Da mesma forma, se uma parte da superf´ıcie observada est´a vis´ıvel somente na imagem da esquerda ou na da direita, o Algoritmo8tamb´em deve ser modificado de forma que no primeiro caso (vis´ıvel na imagem da esquerda), o arco correspondente a esta parte da imagem seja vertical, e em caso contr´ario ele ser´a horizontal. A dificuldade dessa abordagem ´e a definic¸˜ao de uma func¸˜ao de custo adequada, uma vez que em regi˜oes parcialmente oclusas a diferenc¸a entre as regi˜oes correspondentes n˜ao pode ser calculada. Assim, alguns trabalhos tˆem sido propostos procurando estabelecer a correspondˆencia neste tipo de situac¸˜ao como em [Belhumeur e Mumford, 1992].

Outra observac¸˜ao que deve ser considerada ´e que at´e o momento, cada par de linhas cor- respondentes entre as duas imagens foi tratado independentemente das demais linhas. Entre- tanto, se uma aresta se prolonga atrav´es de v´arias linhas nas imagens, as correspondˆencias em uma linha de varredura sofrem uma forte influˆencia das correspondˆencias em sua vizinhanc¸a. Forc¸ar a consistˆencia entre as linhas epipolares ´e equivalente a aplicar uma restric¸˜ao de con- tinuidade entre elas [Cox et al., 1996].