Modélos Matemáticos en Visión por Ordenador

Luis Alvarez

Mayo 2009

Métodos algebraícos

Método de Cholesky para factorizar matrices simétricas y definidas positivas

$A=B\cdot B^{T}$

$\bigskip $

MATH

Algoritmo


Para $i=1,...,N$

MATH

Para $j=i+1,...,N$

MATH

Fin Para $j$

Fin Para $i$

Utilidades del método de Cholesky

  1. Verificar si una matriz simétrica es definida positiva

  2. Resolver el sistema $A\bar{u}=\bar{b}$ resolviendo los 2 sistemas triangulares MATH

  3. Calcular el determinante de una matriz simétrica y definida positivaMATH

André-Louis Cholesky

AndreCholesky.png

André-Louis Cholesky (1875 - 1918), matemático francés. Estudió en l'École Polytechnique y trabajó en geodesia y cartografía además de desarrollar la descomposición matricial que lleva su nombre. Sirvió en el ejército francés como oficial de ingeniería y murió en una batalla durante la Primera Guerra Mundial, siendo su trabajo publicado póstumamente.

Sistemas con mayor número de ecuaciones que de incógnitas

Sistemas con mayor número de ecuaciones que de incógnitas MATH

Estimación por mínimos cuadrados Se minimiza el error :

MATH



cuya solución lleva a la ecuación normal MATH

Pseudoinversa de una matriz

La matriz MATH es semidefinida positiva, es decir : MATHpor tanto todos sus autovalores $\lambda $ son mayores o iguales que cero y para cualquier $\epsilon >0$ la matriz MATH es invertible.

Solución generaliza de la ecuación normal Definimos la solución generalizada de la ecuación normal MATHcomoMATH

Representación algebráica de las rotaciones utilizando cuaterniones

El espacio de los cuaterniones MATHcon la operación producto MATH

Representación de una rotación en base a los cuaterniones Dada una matriz de rotación $R$ de eje MATH y ángulo $\theta .$ Si llamamosMATHentonces MATH MATH

Representación algebráica de las rotaciones utilizando cuaterniones

El espacio de los cuaterniones MATHcon la operación producto MATH

Representación de una rotación en base a los cuaterniones MATH

Cálculo de autovalores / autovectores

Método de la potencia (Valoración impacto páginas Web Google) Sea una matriz $A$ que posee una base de autovectores tal que en módulo su autovalor máximo $\lambda _{\max }$ es único. Sea un vector $u^{1} $ no ortogonal al subespacio engendrado por los autovectores del autovalor $\lambda _{\max }$, entonces, si definimos la secuencia MATHse verifica que

MATH

MATH

Métodos de optimización

Minimización por mínimos cuadrados no-lineales Dado un vector de parámetros $\bar{x}$ de tamaño $N$ y una función MATH a minimizar, se plantea la busqueda del mínimo de la función

MATH

Aproximación local de la función $E(\bar{x}).$ MATH

Método de gradiente descendente MATH

Minimización por mínimos cuadrados no-lineales

Método de Newton-Raphson MATHSi MATH entonces el mínimo de $\tilde{E}(\bar{x})$ se alcanza en $\bar{x}_{n+1}$ donde MATH

Combinación de métodos de primer y segundo orden Si MATH ó MATH hacemos MATH

Sir Isaac Newton

IsaacNewton.png

Sir Isaac Newton (1643 - 1727), "el científico universal". Tuvo una infancia difícil, su padre falleció antes de que naciera, su madre quería que fuese granjero, pero el director del Colegio King's School, Henry Stokes, la convenció para que estudiase. En 1661, fue admitido en el Trinity College, Cambridge como becario. No fué un estudiante brillante pues era muy autodidacta. Sufrió crisis psicológicas. Tenía un interés muy profundo por la alquimia y la religión.

Método de Levenberg--Marquardt

Expresión de las derivadas de $E(\bar{x})$ en función del Jacobiano Dada MATH se tiene que MATH

MATH

Combinación de métodos de primer y segundo orden Si MATH ó MATH hacemos MATH

Método de Levenberg--Marquardt

Expresión de las derivadas de $E(\bar{x})$ en función del Jacobiano Dada MATH se tiene que MATH

MATH

Método de Levenberg-Marquardt MATH

Historia del método de Levenberg--Marquardt

El método de Levenberg-Marquardt ha tenido una enorme trascendencia práctica en problemas de ajuste de parámetros y es el algoritmo de referencia para optimizar la calibración de cámaras. Fué publicado en primer lugar por Kenneth Levenberg (trabajó en la empresa Frankford Arsenal (diseño y producción de munición de armas)) en 1944 y redescubierto por Donald Marquardt ( estadístico que trabajó en la empresa Dupont (empresa química)) en 1963.

La transformada rápida de Fourier

La transformada rápida de Fourier

Transformada de Fourier discreta de MATH MATH

Algoritmo de Cooley and Tukey (1965). Lema de Danielson and Lanczos (1942) MATHEs decir la transformada de una señal de tamaño $N$ se puede descomponer en 2 transformadas de señales de tamaño $N/2.$

John Tukey

JohnTukey.png

John Tukey (1915 - 2000), hijo de profesores, científico americano, estudio Químicas en la Universidad de Brown e hizo el doctorado en matemáticas en la Universidad de Princeton, donde trabajó como profesor compartiendo este trabajo con sus actividades en los laboratorios Bell. Es conocido principalmente por sus actividades en el area de estadística y por el algoritmo de FFT. Trabajo para el ejercito durante la segunda guerra mundial

Discretización de EDP's

Métodos de diferencias finitas

Ecuaciones Euler-Lagrange Regularización de funciones MATH

Discretización por diferencias finitas MATH MATH

Si $\mu ,\nu >0$ los métodos iterativos standard son convergentes MATH

Métodos multimalla (multigrid methods) para acelerar la convergencia

MATHMATH

MATHMATH

MATH

MATH

Conclusiones del curso de doctorado

Modélos Matemáticos en Visión por Ordenador

  1. Abordar los problemas actuales que se presentan en visión por ordenador requiere de una sólida formación matemática.

  2. Dicha formación matemática tiene un caracter multidisciplinar : Algebra, Análisis, Geometría, Ecuaciones diferenciales, Análisis Numérico, Optimización, Modelos Estadísticos, Análisis Discriminante, Arboles de Decisión, etc..

  3. El area científica de la Visión por Ordenador no para de crecer estimulada por los problemas y aplicaciones que van surgiendo constantemente con el desarrollo de nuevas tecnologías.

  4. Para hacerse una idea del volumen de actividades puede visitarse el sitio web http://lists.diku.dk/mailman/listinfo/imageworld que utilizan muchos laboratorios para anunciar cursos, congresos, ofertas de trabajo,etc..