1.2.1 Movimiento 2D. Estimación de flujo óptico: Consiste en estimar la correspondencia entre dos frames d(x,t;l?t)= v(x,t) l?t para velocidad constante. Si las componentes de desplazamiento o velocidad de cada píxel son tratadas como variables independientes, entonces el número de ecuaciones es igual al número de píxeles, donde cada vector tiene dos componentes. Problemas: Existencia de una solución (oclusión): Una región del objeto del cual pretendemos estimar su movimiento queda oculto en el frame siguiente. Existencia de solución única (apertura): La solución al problema de estimación de movimiento no siempre es única. Existencia de situaciones donde no hay sensación de movimiento. Solo puede estimarse el movimiento que es ortogonal al gradiente espacial de la imagen en cada píxel (vector normal). Continuidad de la solución: La estimación es altamente sensitiva a la existencia de ruido en las observaciones. Pequeños incrementos de ruido pueden suponer desviaciones importantes en la estimación. Múltiples modelos de movimiento.
1.2.1 Movimiento 2D. Podemos distinguir dos tipos de modelos de movimiento: paramétricos y no-parametricos. Modelos paramétricos: Son aquellos descritos mediante proyección en perspectiva u ortográficos sobre el plano imagen. Si el movimiento 2D es resultante del movimiento rígido 3D en proyección ortográfica solo son necesarios 6 parámetros (modelo afín). Bajo proyección en perspectiva son necesarios 8 parámetros (modelo proyectivo u homografía).
Modelos no-paramétricos: El objeto en movimiento no tiene que ser rígido. Podemos distinguir las siguientes aproximaciones: Basados en la ecuación de flujo óptico (OFE): Se basan en el uso de gradientes espacio-temporal de la intensidad de la imagen. Es necesario una suavidad en la variación espacio-temporal entre vecinos. Esta necesidad causa imprecisión ante la existencia de oclusión en la frontera. En color se analizan las tres bandas de color por separado.
1.2.1 Movimiento 2D. Modelos por bloques: Se asume que la imagen esta compuesta por bloques. Se plantean dos enfoques para determinar el desplazamiento de los bloques : Correlación de fase: El termino linear de diferencia de fase entre dos frames consecutivos en la transformada de fourier, determina el movimiento estimado. Correspondencia entre bloques: Se busca el mejor bloque de tamaño fijo entre los dos frames con un criterio de distancia. A menudo el bloque se puede deformar. Métodos recursivos: Están basados en estimadores de desplazamiento de tipo predictor-corrector. La predicción puede tomar como valor de estimación de movimiento la localización del píxel previo o una combinación de la vecindad en el píxel actual. La actualización de la predicción esta basada en minimizar el gradiente de desplazamiento de diferencia de frame (DFD) en ese píxel. Métodos bayesianos: Utilizan una restricción probabilística de probabilidad en forma de campos aleatorios de Gibbs para estimar el desplazamiento de campo.
1.2.2 Transformación en perspectiva. Dado un conjunto de puntos en un plano que llamaremos plano de referencia, se busca su correspondencia en el plano imagen a un plano homográfico, también conocida como transformación proyectiva en el plano. Una homografía es descrita mediante una matriz H de rango 3 x 3 llamada matriz homográfica. Mediante esta matriz se determina la transformación de los puntos en el plano de referencia a puntos en el plano imagen.
1.2.2 Transformación en perspectiva. Se define al matriz homográfica Hs como:
donde Hs es una matriz que describe la homografía. Sistema de coordenadas del mundo X = (Xw, Yw, W)T ,con Zw = 0. Sistema de coordenadas imagen x = (xc, yc, w)T. Si trabajamos con el proceso inverso, podemos llegar a la siguiente expresión:
donde W nos queda: . Si sustituimos en la expresión anterior nos queda:
1.2.2 Transformación en perspectiva. En forma no matricial sería las siguientes expresiones:
Multiplicando el denominador en ambos lados tenemos:
Si despejamos Xw e Yw y añadimos ceros tenemos:
El problema se reduce a n correspondencias entre puntos de los dos sistemas, donde se tienen 2n ecuaciones con 8 variables desconocidas. Así si n = 4, la solución es exacta, mientras que si n > 4, H está sobredeterminada y puede ser estimada mediante un esquema sobredeterminado. Ej: Descomposición en valores singulares (SVD).
1.2.2 Transformación en perspectiva. Para n= 4 tenemos:
1.2.2 Transformación en perspectiva.
1.2.2 Transformación en perspectiva Antonio Criminisi, “Accurate Visual Metrology from Single and Multiple Uncalibrated Images. Tesis Doctoral.
1.3 Modelos no paramétricos.
1.3.1 Métodos (OFE). Ecuación de flujo óptico: Sea sc(x1, x2, t) la distribución de intensidad en el continuo espacio-tiempo. Si la intensidad es constante a lo largo de la trayectoria tenemos:
donde x1 y x2 varían con t de acuerdo al movimiento. Esta derivada es una derivada total que denota el cambio de intensidad a lo largo de la trayectoria de movimiento. Pasando a derivada parciales:
donde v1(x,t) = dx1/dt y v2(x,t) = dx2/dt son las componentes del vector velocidad. Esta ecuación es conocida como ecuación de flujo óptico. Alternativamente:
donde ?sc(x,t) son los dos gradientes y ??,?? es el producto escalar.
1.3.1 Métodos (OFE). Los dos valores desconocidos de OFE son los escalares v1 y v2. Nosotros podemos estimar la componente del flujo en la dirección espacial del gradiente de imagen llamado vector normal de flujo:
La componente del vector de flujo esta en la dirección del gradiente espacial de la intensidad de imagen y es consistente con el problema de apertura. En la búsqueda de otras restricciones para determinar las componentes de flujo, diversos autores sugieren la conservación del gradiente espacial de la imagen:
Una estimación del flujo óptico puede darse a partir de la siguiente expresión:
1.3.1 Métodos (OFE). Lucas-Kanade: Una forma de resolver el problema de apertura es asumir que el movimiento no cambia en un particular bloque de píxeles denotado para x ? B (Lucas–Kanade). Aunque este modelo no es adecuado para movimientos rotacionales, es posible estimar movimientos de traslación pura si el tamaño del bloque es suficientemente grande y cuenta con suficiente variación. Definimos el error de la ecuación de flujo sobre el bloque:
Computando el error respecto a v1 y v2 e igualando a cero podemos obtener las siguientes estimaciones:
1.3.1 Métodos (OFE). Horn-Schunk: Este método satisface las variaciones entre píxeles y es menos restrictivo que el método anterior. Denotamos el error del flujo:
En presencia de ruido y oclusión, el objetivo es minimizar el cuadrado de ese error. La variación de los vectores velocidad píxel a píxel puede cuantificarse como la suma al cuadrado de los gradientes espaciales de las componentes del vector velocidad:
donde asumimos que las coordenadas espaciales y temporales son continuas. El método minimiza el promedio de la suma del error de OFE y la medida de la variación del campo de velocidades:
1.3.1 Métodos (OFE). “A” denota el soporte continuo de la imagen. El parámetro ?2, es utilizado como control del grado de suavidad de cambio del flujo. Minimizando la funcional en la expresión anterior tenemos:
donde ?2 es la laplaciana. En la implementación del método se utiliza la iteración de Gauss-Seidel para llegar a la siguiente expresión:
1.3.1 Métodos (OFE). Estimación de gradientes mediante diferencias finitas: Consideremos una imagen discreta s(n1, n2, k) en el frame k y n1 y n2 las coordenadas de la imagen. Entonces podemos aplicar las siguientes expresiones:
Estimación de gradientes mediante ajuste polinómico: En este caso se busca aproximar sc(x1, x2, t) mediante un polinomio de bajo orden.
1.3.1 Métodos (OFE). donde ?i(x1, x2, t) son las bases del polinomio y ai son los coeficientes. Ej (cuádricas): ?i(x1, x2, t)=1, x1, x2, t, x12, x22, x1x2, x1t, x2t El método de Horn-Shunck impone restricción de suavidad sobre la imagen. Esto tiene dos efectos no deseados. La restricción de suavidad no se da en la dirección perpendicular a la frontera de oclusión. Puede haber cambios bruscos en la frontera de los objetos (motion edges). La solución esta en imponer solo suavidad en la dirección donde la frontera no tiene cambios significativos (restricción de suavidad direccional). Estos métodos de restricción adaptativa pueden aplicarse mediante la expresión:
donde W es una matriz de pesos que penaliza la variación del campo de movimiento en función de los cambios espaciales(Ver Tekalp pag 87-88).
1.3.1 Métodos OFE. Evaluación de la bondad de una estimación de movimiento: Proporción de picos debidos a señal de ruido (PSNR): Se calcula a partir del desplazamiento de diferencia de frames DFD.
donde d1 y d2 son los desplazamientos estimados en cada píxel. Entropía ‘H’ del campo de movimiento estimado:
donde P(d1) y P(d2) denotan la frecuencia relativa de ocurrencia en las componentes horizontal y vertical del vector de movimiento d. Es una medida de la suavidad del campo de movimiento, y tiene especial interés en compresión de vídeo basado en estimación de movimiento. Es de destacar que la media absoluta de DFD no da una medida de la bondad de la estimación.
1.3.2 Métodos por bloques. Modelo de movimiento: Son muy utilizados en compresión de vídeo (H.261 y MPEG 1-2). Se usan también en filtros de compensación de movimiento para conversiones estándar. Los movimientos basados en bloques, asumen que la imagen está compuesta por dos tipos de movimiento: 1) Simple movimiento en traslación 2D. 2) Deformaciones 2D en los bloques. (Sección 6.5, Tekalp) En el primer caso el movimiento de cada bloque consiste en una traslación pura. Sea uno de los N X N bloques B en el frame k centrado en n = (n1, n2) modelados con desplazamiento del mismo tamaño a k + l.
d1 y d2 son las coordenadas de desplazamiento. Por tanto la cuestión se reduce a encontrar una correlación entre bloques en los frames k y k+l. En este proceso puede darse superposición de bloques como se ve en la figura. Cuando no hay superposición al bloque entero se asigna un vector de movimiento. En el otro caso se calcula el movimiento promedio en la región de solapamiento.
1.3.2 Métodos por bloques.
a) Sin superposición. b) con superposición Estos métodos requieren sólo necesitan un movimiento por bloque. Fallan para procesos con zoom, movimiento rotacional y deformaciones locales. Además, la división en bloques no se ajusta a la forma de los objetos.
1.3.2 Métodos por bloques. Método de correlación de fase: La idea es recoger ese movimiento discreto del que hemos hablado en la ecuación anterior en el espacio de frecuencias con l =1.
(1)
donde Sk(f1,f2) denota la transformada de fourier del frame k para las variables espaciales x1 y x2. La diferencia de fase en el plano de frecuencias f1 y f2 vendrá dado por 2? (d1f1+d2f2). Un problema que aparece en el plano imagen es que a veces este movimiento queda oculto. En otras situaciones aparecen varios objetos moviéndose dentro del bloque y no es fácil su identificación. El método de correlación de fase, facilita estas tareas por medio del desplazamiento relativo de bloques mediante una función de correlación computada en el espacio de frecuencias. El poder espectral entre los frames k y k+1 es definida como:
1.3.2 Métodos por bloques. Esta operación corresponde a una convolución o más simplemente el producto de sus respectivas transformadas (ver Gonzalez-Wintz 87). Normalizando el poder espectral CN, obtenemos su fase y sustituyendo la eq. (1), llegamos a la siguiente expresión:
El proceso a seguir sería el siguiente: Calculamos una DFT para cada bloque de los frames k y k+1. Computamos la fase del poder espectral. Computamos una DFT inversa de CNk,k+1(f1,f2) para obtener la función correlación de fase cNk,k+1(n1,n2). Localizamos los picos de la función correlación de fase. Problemas: Pueden afectar las discontinuidades en la frontera apareciendo picos falsos. Es deseable que los desplazamientos se correspondan a un entero múltiple del intervalo de cambio en el dominio de frecuencias. El tamaño del bloque debe ser grande para detectar el desplazamiento, y no demasiado para que el desplazamiento sea constante en el bloque.
1.3.2 Métodos por bloques.
Función de correlación de fase.
1.3.2 Métodos por bloques. Correspondencias entre bloques: Criterio de correspondencia. Estrategia de búsqueda. Determinación del tamaño del bloque.
Mínimo error cuadrático medio (MSE):
se busca el bloque de tamaño N1 y N2 que minimice ese error. Mínima diferencia en valor absoluto(MAD):
El segundo es más utilizado en operaciones realizadas con hardware. Estos métodos pueden realizar una estimación errónea ante la existencia de mínimos locales.
1.3.2 Métodos por bloques. Estrategia de búsqueda:
(left) Three-step search. (right) Cross-search
1.3.2 Métodos por bloques. Estimación jerárquica:
(left) Representación jerárquica. (right) Búsqueda jerárquica.
1.3.2 Métodos por bloques. (Malo et al, 99): Exploiting perceptual feedback in multigrid motion estimation for video coding an improved DCT quantization scheme.
1.3.2 Métodos por bloques. Modelos de bloques deformables: a) Segmentar el frame actual en bloques de rectángulos o triángulos. b) Utilizaremos una función de transformación que perturbaremos. Ej: transformación afín, transformación en perspectiva y transformación bilineal. c) Transformaremos los píxels del frame actual sobre el nuevo frame calculando la correspondencia entre puntos. d) Elegiremos aquella transformación espacial que minimice MSE o MAD.
Modelo basado en bloque deformables.
1.3.2 Métodos por bloques.
Modelo de bloques regular y adaptativo
1.3.3 Métodos recursivos. Los métodos recursivos realizan estimaciones del tipo predicción-corrección de la forma:
donde d(x,t,?t) denota el vector de movimiento estimado en la localización de x y tiempo t, di(x,t,?t) denota la estimación de movimiento predicho y u(x,t,?t) denota la actualización entre los dos términos. Generalmente, el mejor estimador encontrado en el paso previo es tomado como predicción en el siguiente de forma que se minimice la diferencia de desplazamiento entre los dos frames (DFD). Así, el DFD entre los instantes de tiempo t y t’=t+?t se define como:
donde sc(x1,x2,t) denota la variación de intensidad a medida que cambia t. Si expandimos por series de Taylor sc(x+d(x),t+?t) para d(x) y ?t pequeñas,
1.3.3 Métodos recursivos. Sustituyendo (3) en (2) y eliminando los términos de orden superior tenemos:
Vemos que dicha expresión en muy parecida a la ecuación de flujo OFE. Si ?t ? 0 se obtiene OFE:
Si ?t es finito, es necesario estimar el vector desplazamiento d(x) entre los dos frames: (a) Mediante estrategia de correspondencia entre bloques. (b) Usando una estrategia de optimización por descenso de gradiente (aproximación recursiva). (c) Tomando t=1 y dfd(x,d)=0 y solucionando la ecuación (4) usando un bloque de píxeles.
1.3.3 Métodos recursivos. Algoritmo de Netravali-Robbins: Consiste en encontrar una estimación del vector desplazamiento que minimice la siguiente función:
Mediante el método por descenso de gradiente podemos hacer la siguiente iteración:
Para resolver el gradiente a partir de la expresión (2) tenemos:
Y expandiendo la intensidad sc en torno a un punto arbitrario x + d en series de Taylor alrededor de x + di, tenemos:
1.3.3 Métodos recursivos. Sustituyendo esta última expresión en la anterior nos queda:
Como ?x sc(x-d,t-?t)|d=di = ?x sc(x-di,t-?t), podemos expresar el gradiente de la DFD con respecto de d en términos de gradiente espacial de la intensidad de imagen:
Así, el proceso de iteración nos queda:
En esta última expresión, el primer y segundo término son la predicción y el término de actualización. Con el parámetro ? establecemos la rapidez con que converge el algoritmo.
1.3.3 Métodos recursivos. Algoritmo de Walker-Rao: En la vecindad de una zona de alto gradiente donde |?sc(x1,x2,t)| es alto, el parámetro ? debería ser pequeño si la DFD queremos que sea pequeña a fin de asegurar una buena convergencia. Análogamente, en imágenes con áreas uniformes donde |?sc(x1,x2,t)| es pequeño necesitamos el proceso inverso. Para este fin proponen la siguiente expresión:
Además, introducen las siguientes reglas heurísticas: a) Si el DFD es menor que un cierto umbral el término de actualización es igual a cero y el proceso se para. b) Si la DFD excede el umbral pero el gradiente espacial es cero, el término de actualización es igual a cero y el proceso se para. c) Si el valor absoluto del término de actualización para cada componente es menor que 1/16 se le asigna al término ?1/16. d) Si el valor absoluto del término de actualización para cada componente en mayor que 2 se le asigna al término ? 2.
1.3.3 Métodos recursivos. Caffario y Roca también desarrollan una expresión similar:
donde el término ?2, impide una división por cero en el caso de áreas con intensidad constante donde el gradiente espacial es casi cero. Un típico valor de ?2 = 100. Experimentalmente se comprueba que con 5 iteraciones los resultados suelen ser satisfactorios. Extensión a un modelo de bloques: La cuestión consiste en dado un píxel x, crear partiendo de los píxeles vecinos un bloque B de forma variable, tal que se minimice la siguiente DFD:
Siguiendo un proceso como antes llegamos a la siguiente expresión de iteración:
1.3.3 Métodos recursivos.
Soporte causal de x para N = 7. Estimación de Wiener: Supone una extensión del algoritmo de Netravali-Robbins sobre bloques basado en mínimos cuadrados . Se trata de minimizar el error en el término de actualización partiendo de la expresión (1):
donde d(x) es el vector desplazamiento real del bloque. Sea un bloque con N vecindades del píxel x, entonces a partir de la expresión (6) podemos obtener la siguiente forma matricial:
1.3.3 Métodos recursivos Sin considerar el vector n y usando el principio de ortogonalidad puede llegarse a la siguiente expresión del mínimo lineal error cuadrático medio: Donde ? es un parámetro regulador que depende de las varianzas de intensidad en las dos componentes de la imagen. Sustituyendo en (6) llegamos al siguiente proceso iterativo:
1.3.4 Métodos bayesianos. Estimación 2D basada en máxima probabilidad a posteriori (MAP): Requiere dos funciones de densidad de probabilidad (pdf): La probabilidad condicional pdf de la intensidad de imagen observada dado el campo de movimiento, también llamado modelo likelihood o modelo de observaciones. La probabilidad a priori pdf de los vectores de movimiento o modelo de campo de movimiento. Sea la intensidad de campo en un píxel x y el frame k, sk(x) y d(x)=(d1(x),d2(x)) denota el vector desplazamiento. En general, cuando observamos vídeo, este esta corrompido por la adición de ruido de la forma gk(x) = sk(x) + vk(x). El básico MAP para dos frames gk(x) y gk-1(x) es:
Utilizando el teorema de bayes:
1.3.4 Métodos bayesianos. donde p(gk|d1,d2,gk-1) es la probabilidad condicional o medida de consistencia que mide como de bien es estimado el desplazamiento d1, d2 sobre gk dado gk-1, y p(d1,d2|gk-1) es la pdf a priori del campo de movimiento reflejado en el conocimiento que tenemos del estado actual en gk-1. El denominador no dependen de d1 , d2 y puede considerarse constante en el propósito de la estimación.
El cambio de la intensidad en un píxel a lo largo de una trayectoria de movimiento verdadera es debido a la observación de ruido. Asumiendo que la observación de ruido es ‘blanco’, este puede considerarse una gaussiana de media cero y varianza ?2. Entonces la pdf condicional puede modelarse como:
donde d(?) denota el determinante de ?, el cual viene dado por la densidad de muestreo de la imagen (resolución de la imagen).
1.3.4 Métodos bayesianos. La pdf a priori viene dada por el campo de movimiento en el frame gk-1, que puede ser modelizado mediante muestreo de Gibbs GRF, donde la función de potencial viene impuesto por la variación de contraste píxel a píxel:
Qd es llamada función de partición y Ud es la energía interna de Gibbs.
Cd es el conjunto de todos los clichés para el campo de desplazamiento y Vcd() representa la función de potencial del cliché para c?Cd y ?d es una constante positiva. El potencial del cliché variara asignando probabilidades en función de las variaciones existentes píxel a píxel. Ej:
Demostración del modelo de Gibbs Este modelo de potencial para 4-vecinos viene definido por
1.3.4 Métodos bayesianos Campos aleatorios de Gibbs. Dado un sistema de vecindades N asignado al conjunto de clichés C, definimos un campo aleatorio de valores discretos:
donde ?i es la delta de dirac, y normalizando constante Q llamada función partición, queda:
Para valores continuos en campos aleatorios
donde la función partición es
y U(z) es la energía interna de Gibbs definido por
1.4 Nociones sobre compresión de vídeo (H.261, MPEG-1 y MPEG-2).
(left) Digital video studio standards. (Right) Wold standards for image compression.
1.4 Nociones sobre compresión de vídeo (H.261, MPEG-1 y MPEG-2). Estándar H.261 (1990): Desarrollo de vídeo compresión estándar para facilitar servicios de vídeo-conferencia y vídeo-teléfono. Información p X 64 kbps, p= 1,…,30. Para p=1, es usado en vídeo-teléfono donde 48 kbps es señal de vídeo y 16 kbps es señal de audio. Para p>=6, 384 kbps o más, es usado en vídeo-conferencia. Para p=30, 1.92 Mbps, es suficiente para imágenes con calidad VHS o mejores. Proyecto COST(CoOperation in the field of Scientific and Technical reseach) 1983-1990. En 1985, sale el estándar H.120, n x 384 kbps, n= 1..5. Características: Perdida máxima de codificación 150 msec. Pensado para un sistema bidireccional. Sensible a implementaciones VLSI de bajo costo y aplicable a sistemas comerciales de vídeo-teléfono y tele-conferencia. Acceso secuencial en el almacenamiento de la información. Formatos de imagen: Common Intermediate Format (CIF) y QCIF (one-quarter of the CIF).
1.4 Nociones sobre compresión de vídeo (H.261, MPEG-1 y MPEG-2).
Tabla 23.1. H.261 input image formats. Compresión similar a JPEG basado en block-by-block DCT: Estimación de movimiento (desplazamiento) de cada bloque macroblocks (MB) Selección del modo de compresión en cada MB basada en el desplazamiento. Para cada MB se genera una cabecera con el modelo elegido.
1.4 Nociones sobre compresión de vídeo (H.261, MPEG-1 y MPEG-2). Estándar MPEG-1: (1992) Compresión/Descompresión de CIF vídeo con 1.5 Mbps. Soporta operaciones de estimación de movimiento, predición, DCT, cuantización y codificación de longitud variable. Análogamente al H.261, no tiene un modelo estandar de compresión o estimación. Propiedades: Acceso aleatorio en aplicaciones de almacenaje de vídeo. Búsqueda rápida para selección de determinados frames. Permite pérdidas de codificación de hasta 1 segundo. 720 pels/line, 576 lines/pic, 30 pic/sec, 396 MB/pic, 9900 MB/sec Group of pictures (GOP). I-picture: Intra-frame DCT encoded. P-picture: inter-frame encoded pictures for forward prediction. B-picture: inter-frame encoded pictures for forward, backward, or bidirectional relative to other I- or P-pictures. D-picture: contain only the DC component of each block.
1.4 Nociones sobre compresión de vídeo (H.261, MPEG1 y MPEG2).
23.5 Group of pictures in MPEG-1
1.4 Nociones sobre compresión de vídeo (H.261, MPEG-1 y MPEG-2). Estándar MPEG-2: Permite entradas interlazadas, definir alta definición y alternativos submuestreos del canal chroma. Mejora la cuantización y opciones de codificación. Ofrece un bitstream escalable: Escalabilidad espacial (resolución píxel), Escalabilidad SNR (diferentes pasos para cuantizar los coeficientes DCT) y Escalabilidad temporal (decodificar diferentes tamaño de frame sin tener que hacerlo frame a frame).
23.11. A GOP for an interlanced video
| Página siguiente |