ES2276696T3

ES2276696T3 - Metodo de estimacion de movimiento global.

Info

Publication number: ES2276696T3
Application number: ES00965961T
Authority: ES
Inventors: Michel Bonnet; Cecile Dufour
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1999-09-21
Filing date: 2000-09-11
Publication date: 2007-07-01
Anticipated expiration: 2020-09-11
Also published as: DE60032452T2; EP1131955A1; US6707854B1; WO2001022733A1; KR100798283B1; CN1164121C; KR20010080523A; DE60032452D1; EP1131955B1; JP2003510910A; CN1322443A

Abstract

Método para estimar movimiento entre un fotograma F(n) entrante de una secuencia de fotogramas y una gran imagen M(n-1) estática, siendo dicha gran imagen estática un sprite o mosaico construido de fotogramas F(1)... F(n-1) anteriores de dicha secuencia, usando dicho método de estimación de movimiento un modelo de movimiento basado en una transformación de perspectiva en dos dimensiones que contiene ocho parámetros de movimiento y que comprende una etapa de optimización de una función coste, caracterizado porque dichos ocho parámetros de movimiento son las coordenadas de los cuatro vértices del fotograma entrante, moviéndose cada uno de dichos vértices sucesivamente e iterativamente en dos direcciones para encontrar una estimación de los parámetros de movimiento correspondientes a un máximo de la función coste.

Description

Método de estimación de movimiento global.

Campo de la invención

La presente invención se refiere a un método y a su correspondiente dispositivo para estimar movimiento entre un fotograma F(n) entrante de una secuencia de fotogramas y una gran imagen M(n-1) estática, construyéndose dicha gran imagen estática de fotogramas F(1)...F(n-1) anteriores de dicha secuencia, usando dicho método de estimación de movimiento un modelo de movimiento basado en una transformación de perspectiva en dos dimensiones que contiene ocho parámetros de movimiento y que comprende una etapa de optimización de una función coste.

Tal invención puede ser útil para aplicaciones que se refieren a MPEG-4 y, más especialmente, al estándar MPEG-7, tal como una generación de sprites o formación de mosaicos.

Antecedentes de la invención

Se conoce un método del tipo mencionado anteriormente por la solicitud de patente WO 98/59497. Esta solicitud de patente describe un método usado en codificación de vídeo para generar un sprite de los objetos de vídeo en el fotograma de una secuencia de vídeo. El método estima el movimiento global entre un objeto de vídeo en un fotograma actual y un sprite construido de objetos de vídeo de fotogramas anteriores. En concreto, el método de estimación de movimiento global calcula coeficientes de movimiento de una transformación en dos dimensiones que minimiza los errores de intensidad entre píxeles en el objeto de vídeo y los píxeles correspondientes en el sprite. El método de Levenberg-Marquardt se emplea para la etapa de minimización, que consiste en la minimización de una función analítica que se refiere a los errores de intensidad, y permite seleccionar los puntos más representativos y rechazar los otros como valores atípicos.

Sin embargo, el método de estimación de movimiento global descrito anteriormente tiene varios inconvenientes. El principal es que es muy sensible a los valores atípicos, que son píxeles que no siguen el movimiento global y que corresponden a objetos que tienen su propio movimiento. Esto significa que el método de estimación de movimiento global puede a veces fallar con algunas secuencias de vídeo particulares. Otra desventaja es también su incapacidad para converger de manera eficiente y rápida para cierto tipo de secuencias de vídeo.

Sumario de la invención

Es por lo tanto un objetivo de la presente invención proponer otro método de estimación de movimiento global que sea muy robusto frente a los valores atípicos pero que también pueda permitir una eficiente y rápida convergencia.

Para este fin, el método según la invención se caracteriza porque los ocho parámetros de movimiento son las coordenadas de los cuatro vértices del fotograma entrante, moviéndose dichos vértices sucesivamente en dos direcciones para encontrar una estimación de los parámetros de movimiento correspondientes a un máximo de la función coste.

El método de estimación de movimiento se basa en un planteamiento geométrico que trata sucesivamente e iterativamente los ocho parámetros de movimiento mediante la optimización de una función numérica mientras que el planteamiento de la técnica anterior, basada en el algoritmo de Levenberg-Marquardt, trata los ocho parámetros simultáneamente mediante la minimización de una función analítica. Como consecuencia, el método de estimación de movimiento basado en el desplazamiento de los cuatro vértices ha resultado ser más robusto frente a valores atípicos que el utilizado en la técnica anterior.

El método según la invención también se caracteriza porque el método de estimación de movimiento incluye un primer método iterativo que comprende, en cada iteración, la etapa de optimización para determinar una estimación de los ocho parámetros de movimiento, seguida de una etapa de cálculo de las dos direcciones de movimiento de cada uno de los cuatro vértices teniendo en cuenta la última alteración, realizándose dicho método iterativo hasta que se alcanza un criterio definido.

El método iterativo se basa en el algoritmo de Powell que mejora la convergencia de dicho método.

El método según la invención se caracteriza finalmente porque la etapa de optimización comprende un segundo método iterativo que realiza, en cada iteración, una operación de interpolación parabólica de valores de la función coste para estimar sucesivamente los parámetros de movimiento.

El uso de una operación de interpolación parabólica hace la convergencia del método de estimación de movimiento más rápida, especialmente en el caso de un movimiento grande.

Como consecuencia, el presente método de estimación de movimiento podría incluirse ventajosamente en un método para generar una gran imagen estática, tal como un sprite o un mosaico, e implementarse en un dispositivo para generar una gran imagen estática de este tipo.

Estos y otros aspectos de la invención serán aparentes a partir de, y se aclararán con referencia a, las realizaciones descritas a continuación

Breve descripción de los dibujos

La presente invención se describirá ahora, a modo de ejemplo, con referencia a los dibujos que acompañan, en los que:

la figura 1 muestra una representación geométrica de la etapa de optimización para la primera iteración,

la figura 2 es un diagrama de flujo para el proceso usado para realizar la inicialización automática de los parámetros de movimiento para las dos imágenes,

la figura 3 es un diagrama de flujo para el proceso iterativo usado para optimizar los parámetros de movimiento,

la figura 4 muestra una representación geométrica de la etapa de optimización para la iteración (I+1),

la figura 5 muestra un esquema de un dispositivo de generación de grandes imágenes estáticas.

Descripción de la invención

La presente invención propone un nuevo método de estimación de movimiento global entre un fotograma F(n) entrante de una secuencia de fotogramas y una gran imagen M(n-1) estática, que se construye de fotogramas F(1), F(2)..., F(n-1) anteriores de la secuencia de vídeo.

El principio del método de estimación de movimiento se representa en la figura 1. Dicho método de estimación de movimiento usa un modelo de movimiento basado en una transformación de perspectiva en dos dimensiones, que se llama también el modelo de perspectiva, con el fin de caracterizar el movimiento entre dos fotogramas. Este modelo contiene ocho parámetros de movimiento y se elige preferiblemente porque permite más posibilidades de movimiento de cámara que los otros, tales como, por ejemplo, traslación, zoom, o rotación. El uso del modelo de perspectiva es válido en los siguientes casos:

-: Todas las vistas comparten el mismo centro óptico. Este es más o menos el caso cuando se fija una cámara en un trípode giratorio: el eje de rotación puede pasar a través o muy cerca del centro óptico de la cámara. Si los objetos captados están muy lejos de la cámara, esta suposición siempre se verifica.

-: La escena captada corresponde a una superficie plana.

: Una proyección de perspectiva transforma un rectángulo en un cuadrilátero. Las coordenadas en dos dimensiones de los cuatro vértices del cuadrilátero definen completamente los ocho parámetros de movimiento a_{0} a a_{7} de la proyección de perspectiva. Por lo tanto, los ocho parámetros de movimiento son, en la presente invención, las coordenadas en dos dimensiones de los cuatro vértices, que al principio del proceso son A(0)(a_{0}(0), a_{1}(0)), B(0)(a_{2}(0), a_{3}(0)), C(0)(a_{4}(0), a_{5}(0)) y D(0)(a_{6}(0), a_{7}(0)).

: El método de estimación de movimiento según la invención permite cualquier desplazamiento de las cuatro esquinas de la imagen rectangular original para adecuarse a la siguiente mediante optimización de una función coste. Partiendo de una posición inicial para estos cuatro vértices, correspondientes a un establecimiento inicial de los parámetros de movimiento, el método intenta optimizar la función coste mediante desplazamientos leves de los cuatro vértices. Cada vértice se desplaza en una pequeña cantidad alrededor de su posición inicial con el fin de encontrar un máximo local para la función coste. Por ejemplo, A(0), se mueve a lo largo de la dirección d_{1}(0), que es en este caso particular una dirección horizontal, con el fin de encontrar un máximo de la función coste. Entonces, el punto obtenido se mueve a lo largo de la dirección d_{2}(0), que es en este caso particular una dirección vertical, hasta que se encuentra otro máximo dando un nuevo vértice A(1)((a_{0}(1), a_{1}(1)). Esta operación se realiza entonces sucesivamente para los otros vértices y se obtiene una nueva imagen cuadrilátera.

: En la realización preferida la función coste se refiere a la Diferencia de Fotogramas Desplazados (DFD). La medida DFD se calcula en los píxeles pertenecientes al área S que se solapa tanto con el fotograma F(n) entrante como con la gran imagen M(n-1) estática actual según sigue:

DFP = \sum\limits_{S} \ r_{p}{}^{2},

: siendo r_{p} una diferencia entre los valores originales y predichos de un píxel p, definida como sigue:

r_{p} = L(x,y)-L(x',y')

\newpage

: en la que:

-: L(x, y) es el valor de luminancia de la señal de vídeo correspondiente al píxel p(x, y) del fotograma F(n) entrante,

-: L(x', y') es el valor de luminancia de la señal de vídeo correspondiente al píxel p(x', y') de la gran imagen M(n-1) estática.

: (x', y') son el valor de punto flotante del píxel p' que ha de extraerse de la gran imagen estática. El valor de luminancia correspondiente a este píxel se calcula con respecto a las cuatro coordenadas enteras más cercanas en la imagen, que son (x_{0}, y_{0}), (x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}) con valores de luminancia respectivos L0, L1, L2 y L3, usando una interpolación bilineal:

L(x', y') = L0 + (x'-x_{0})(L1-L0) + (y'-y_{0})(L2-L0) + (x'-x_{0})(y'-y_{0}) (L3-L2-L1+L0)

La optimización de la función coste es, en este caso, una minimización de la diferencia de fotogramas desplazados. La DFD se calcula aquí con los valores de luminancia de las señales de vídeo pero también se pueden calcular con los valores de crominancia de las señales de vídeo.

En otra realización, la función coste se refiere a la Correlación de Fotogramas Desplazados (CFD). La medida CFD se calcula en los píxeles pertenecientes al área S que se solapa tanto con el fotograma F(n) entrante como con la gran imagen M(n-1) estática actual como sigue:

1

La optimización de la función coste es, en este caso, una maximización de la correlación de fotogramas desplazados. La CFD se calcula aquí con los valores de luminancia de las señales de vídeo pero también puede calcularse con los valores de crominancia de las señales de vídeo.

El método de estimación de movimiento según la invención comprende dos etapas principales:

-: Se realiza una primera etapa para inicializar los parámetros de movimiento automáticamente para los dos primeros fotogramas.

-: Durante una segunda etapa, cada parámetro de movimiento es optimizado independientemente, mediante minimización de una función coste que se refiere a la DFD. Esta función coste cost() es, en la realización preferida, un error cuadrático medio ponderado que se define como sigue:

2

en la que w_{p} es un coeficiente de ponderación, que se define como sigue:

3

en la que p es una función definida positiva, simétrica con un único máximo en r_{p}=0.

La función p se elige con el fin de reducir la influencia de los valores atípicos. En la realización preferida, la función p es una función lorentziana definida como sigue:

100 en la que \sigma es un factor de escala.

Otras funciones p pueden ser adecuadas para la presente invención tales como, por ejemplo, la función de German y McClure, que se define como sigue:

4

En una segunda realización, la función coste es otro error cuadrático medio ponderado, teniendo en cuenta una información del gradiente de un píxel p (grad_{p}) como sigue:

5

en la que T es un umbral cercano a 0 y en la que el coeficiente de ponderación w_{p} se define como sigue:

6

En esta segunda realización, el coeficiente de ponderación w_{p} del error cuadrático medio se normaliza dividiéndolo por la suma de todos los pesos en cada ubicación de píxel para favorecer pequeños desplazamientos con pequeños errores más que grandes desplazamientos con grandes errores. Además, la introducción de una información del gradiente permite:

-: dar más importancia a regiones en las que el gradiente es mayor que el umbral T, siendo estas regiones más apropiadas para propósitos de correspondencia,

-: rechazar regiones en las que el gradiente está por debajo del umbral T, permitiendo de este modo aumentar la velocidad de la estimación de coste.

La figura 2 es un diagrama de flujo que muestra el método usado para realizar la inicialización automática de los parámetros de movimiento para los dos primeros fotogramas.

En la realización preferida, una transformación de traslación, que sólo necesita dos parámetros de movimiento, se usa para conseguir una primera aproximación de los desplazamientos entre los dos primeros fotogramas de una secuencia de vídeo, en la que no se dispone de predicción.

La etapa de inicialización automática comprende:

-: una sub-etapa (INI) de inicialización de la posición del píxel xx_min correspondiente al mínimo de la función coste en una dirección horizontal: xx_min=0,

-: una sub-etapa (CALC) de cálculo del valor j de la posición del píxel correspondiente al mínimo de la función coste cost() cuando se aplican traslaciones al fotograma entrante en una dirección horizontal, estando la amplitud i del vector de traslación comprendida entre -5 y +5 píxeles: 101 siendo Argmin la función que devuelve la abcisa correspondiente al mínimo de la función coste, dando aquí el desplazamiento entre dos fotogramas para la dirección considerada.

-: una comprobación (Cj)del valor de j,

-: si la comprobación no se cumple (j no es igual a cero), una sub-etapa (INC) de recálculo del valor xx_min: xx_min=xx_min+j,

-: si la comprobación se cumple (j=0), el fin (RES) del proceso que da la traslación final xx_min en la dirección horizontal.

Se aplica el mismo algoritmo en la dirección vertical con el fin de encontrar la traslación yy_min que debe realizarse.

La figura 3 es un diagrama de flujo que muestra el proceso iterativo usado para optimizar los parámetros de movimiento. Este método se basa en el método de convergencia de Powell.

El conjunto de ocho parámetros de movimiento, correspondientes a las coordenadas de los cuatro vértices, se inicializa en los valores dados por la predicción de movimiento global, en a_{k}=0 con 0\leqk\leq7.

La etapa de optimización de los parámetros de movimiento comprende:

-: una sub-etapa (INIkI) de inicialización de k y de un contador 1: k=I=0;

-: una comprobación (Ck) del valor de k

-: si el valor de k es estrictamente menor que 8(y), una sub-etapa (PI) de cálculo del valor de los parámetros de movimiento a_{k}(I+1), que corresponde a un mínimo de la función coste cost();

102

: seguida por una sub-etapa (INCk) de incrementación en uno de k.

-: en el caso contrario (n), una segunda comprobación (Ca) del máximo M, para los diferentes valores de k, del valor absoluto de la diferencia entre a_{k}(I+1) y a_{k}(I):

103

-: si el valor de M es inferior a un umbral (y), el fin (RESa) del proceso que da los valores de a_{k}(I+1),

-: en el caso contrario (n), una sub-etapa (DIR) de cálculo de nuevas direcciones de minimización, seguida de una sub-etapa (INCI) de incrementación en uno de I y una sub-etapa (INIk) de reinicialización de k.

La sub-etapa (PI) de cálculo del valor a_{k}(I+1) se realiza usando interpolaciones parabólicas. Se realiza una primera interpolación parabólica en los valores de la función coste correspondientes a tres píxeles consecutivos. Entonces, se realiza una nueva interpolación parabólica en los tres píxeles más cercanos al mínimo de la parábola encontrada previamente. El proceso termina cuando el mínimo de la parábola está comprendido en la ventana definida por los píxeles examinados. Tal método de cálculo aumenta la convergencia de la etapa de optimización. Cuando una operación de interpolación parabólica no es posible (es decir, cuando la parábola tiene un máximo en vez de un mínimo), el cálculo del valor de a_{k}(I+1) se realiza usando un descenso del gradiente, que consiste en comparaciones sucesivas de valores de la función coste de píxeles consecutivos hasta que se alcanza un mínimo de la función coste.

Cuando I=0, las direcciones seguidas por los ochos parámetros para minimizar la función coste son horizontales para abcisas o verticales para ordenadas, tal como se describe en la figura 1. Cuando I>1, las direcciones seguidas para optimización se revisan dada la última alteración, tal como se describe en la figura 4. La dirección de optimización se define como la dirección d_{1}(I) que va desde el vértice A(I-1) al vértice A(I) y su perpendicular d_{2}(I) y así sucesivamente para los otros tres vértices.

Este método de estimación de movimiento puede usarse en un método y su correspondiente dispositivo para generar una gran imagen M(n) estática, tal como un sprite o un mosaico. Dicho método se describe en la figura 5.

Tres etapas principales pueden componer una generación de una gran imagen M(n) estática. Primero, tiene que realizarse la etapa (ME) de estimación de movimiento global según la invención con el fin de combinar el fotograma F(n) entrante con la gran imagen M(n-1) estática ya compuesta de los fotogramas F(1), F(2)..., F(n-1) anteriores. Dicha etapa (ME) de estimación de movimiento global da los parámetros de movimiento a_{k}. El fotograma actual se compensa entonces usando los parámetros de movimiento; esta segunda etapa también se llama distorsión (WAR). El actual fotograma F(n) distorsionado se combina (BLE) finalmente con la gran imagen M(n-1) estática con el fin de formar una nueva gran imagen M(n-1) estática aumentada proporcionando una vista panorámica de la escena, que se guarda en una memoria (MEM) con el fin de combinarse con el siguiente fotograma F(n+1) entrante, y así sucesivamente.

Claims

1. Método para estimar movimiento entre un fotograma F(n) entrante de una secuencia de fotogramas y una gran imagen M(n-1) estática, siendo dicha gran imagen estática un sprite o mosaico construido de fotogramas F(1)... F(n-1) anteriores de dicha secuencia, usando dicho método de estimación de movimiento un modelo de movimiento basado en una transformación de perspectiva en dos dimensiones que contiene ocho parámetros de movimiento y que comprende una etapa de optimización de una función coste, caracterizado porque dichos ocho parámetros de movimiento son las coordenadas de los cuatro vértices del fotograma entrante, moviéndose cada uno de dichos vértices sucesivamente e iterativamente en dos direcciones para encontrar una estimación de los parámetros de movimiento correspondientes a un máximo de la función coste.

2. Método de estimación de movimiento según la reivindicación 1, caracterizado porque la función coste se define por \sum\limits_{p}\frac{1}{2} w_{p}r_{p}^{2}, en la que r_{p} es una diferencia entre los valores originales y predichos de un píxel p y w_{p} es un coeficiente de ponderación.

3. Método de estimación de movimiento según la reivindicación 2, caracterizado porque el coeficiente de ponderación w_{p} es una función de la inversa de r_{p} y la derivada de p(r_{p}) en la que p es una función definida positiva, simétrica con un único máximo en r_{p}=0.

4. Método de estimación según la reivindicación 1, caracterizado porque la función coste se define por,
cost(r_{p}) = \frac{\sum\limits_{p/(grad_{p} \geq T)} w_{p}r_{p}{}^{2}}{\sum\limits_{p/(grad_{p} \geq T)} w_{p}}, en la que r_{p} es una diferencia entre los valores predichos y originales de un píxel p, T es un umbral y w_{p} es un coeficiente de ponderación.

5. Método de estimación de movimiento según la reivindicación 4, caracterizado porque el coeficiente de ponderación w_{p} se define por w_{p} = \frac{2}{2 + \frac{r_{p}{}^{2}}{1 + grad_{p}{}^{2} \sigma^{2}}}, en la que grad_{p} es un gradiente de un píxel p y \sigma es un factor de escala.

6. Método de estimación de movimiento según la reivindicación 1, caracterizado porque dicho método de estimación de movimiento incluye una etapa de inicialización automática de dichos parámetros de movimiento para los dos primeros fotogramas utilizando una transformación de traslación en dos dimensiones.

7. Método de estimación de movimiento según la reivindicación 1, caracterizado porque dicho método de estimación de movimiento incluye un primer método iterativo que comprende, en cada iteración, dicha etapa de optimización para determinar una estimación de los ocho parámetros de movimiento, seguida de una etapa de cálculo de las dos direcciones de movimiento de cada uno de los cuatro vértices teniendo en cuenta la última alteración, realizándose dicho método iterativo hasta que se alcanza un criterio definido.

8. Método de estimación de movimiento según la reivindicación 7, caracterizado porque dicha etapa de optimización comprende un segundo método iterativo que realiza, en cada iteración, una operación de interpolación parabólica de valores de dicha función coste para estimar sucesivamente los parámetros de movimiento.

9. Método para generar una gran imagen M(n) estática, tal como un sprite o un mosaico, que comprende un método para estimar movimiento según cualquiera de las reivindicaciones 1 a 8.

10. Dispositivo para generar una gran imagen M(n) estática, tal como un sprite o un mosaico, que comprende un circuito de estimación de movimiento que implementa un método de estimación de movimiento según cualquiera de las reivindicaciones 1 a 8.