Un algoritmo de coincidencia de bloques es una forma de localizar macrobloques coincidentes en una secuencia de fotogramas de vídeo digital con el fin de estimar el movimiento . La suposición subyacente detrás de la estimación del movimiento es que los patrones correspondientes a los objetos y al fondo en un fotograma de una secuencia de vídeo se mueven dentro del fotograma para formar objetos correspondientes en el fotograma siguiente. Esto se puede utilizar para descubrir redundancia temporal en la secuencia de vídeo, lo que aumenta la eficacia de la compresión de vídeo entre fotogramas al definir el contenido de un macrobloque por referencia al contenido de un macrobloque conocido que es mínimamente diferente.
Un algoritmo de coincidencia de bloques implica dividir el fotograma actual de un vídeo en macrobloques y comparar cada uno de los macrobloques con un bloque correspondiente y sus vecinos adyacentes en un fotograma cercano del vídeo (a veces, solo el anterior). Se crea un vector que modela el movimiento de un macrobloque de una ubicación a otra. Este movimiento, calculado para todos los macrobloques que componen un fotograma, constituye el movimiento estimado en un fotograma.
El área de búsqueda para una buena coincidencia de macrobloque se decide mediante el "parámetro de búsqueda", p, donde p es el número de píxeles en los cuatro lados del macrobloque correspondiente en el cuadro anterior. El parámetro de búsqueda es una medida de movimiento. Cuanto mayor sea el valor de p, mayor será el movimiento potencial y la posibilidad de encontrar una buena coincidencia. Sin embargo, una búsqueda completa de todos los bloques potenciales es una tarea computacionalmente costosa. Las entradas típicas son un macrobloque de tamaño 16 píxeles y un área de búsqueda de p = 7 píxeles.
La coincidencia de bloques y el filtrado 3D utilizan este enfoque para resolver diversos problemas inversos de restauración de imágenes , como la reducción de ruido [1] y el desenfoque [2] tanto en imágenes fijas como en vídeo digital .
La estimación de movimiento es el proceso de determinar vectores de movimiento que describen la transformación de una imagen 2D a otra; generalmente a partir de fotogramas adyacentes en una secuencia de vídeo. Los vectores de movimiento pueden estar relacionados con toda la imagen (estimación de movimiento global) o con partes específicas, como bloques rectangulares, parches de forma arbitraria o incluso por píxel. Los vectores de movimiento pueden representarse mediante un modelo de traslación o muchos otros modelos que pueden aproximarse al movimiento de una cámara de vídeo real, como la rotación y la traslación en las tres dimensiones y el zoom.
La aplicación de vectores de movimiento a una imagen para predecir la transformación en otra imagen, debido al movimiento de la cámara o de un objeto en la imagen, se denomina compensación de movimiento . La combinación de estimación de movimiento y compensación de movimiento es una parte clave de la compresión de vídeo , tal como la utilizan MPEG 1, 2 y 4, así como muchos otros códecs de vídeo .
La compresión de vídeo basada en la estimación de movimiento ayuda a ahorrar bits al enviar imágenes diferenciales codificadas que tienen inherentemente menos entropía en comparación con el envío de un fotograma totalmente codificado. Sin embargo, la operación más costosa en términos computacionales y que requiere más recursos en todo el proceso de compresión es la estimación de movimiento. Por lo tanto, los algoritmos rápidos y de bajo costo computacional para la estimación de movimiento son una necesidad para la compresión de vídeo.
Una métrica para hacer coincidir un macrobloque con otro bloque se basa en una función de costo. La más popular en términos de gasto computacional es:
Diferencia media o diferencia absoluta media (DMA) =
Error cuadrático medio (MSE) =
donde N es el tamaño del macrobloque, y son los píxeles que se comparan en el macrobloque actual y el macrobloque de referencia, respectivamente.
La imagen compensada por movimiento que se crea utilizando los vectores de movimiento y los macrobloques del marco de referencia se caracteriza por la relación señal-ruido máxima (PSNR),
Los algoritmos de coincidencia de bloques se han investigado desde mediados de la década de 1980. Se han desarrollado muchos algoritmos, pero a continuación solo se describen algunos de los más básicos o de uso común.
Este algoritmo calcula la función de costo en cada ubicación posible en la ventana de búsqueda. Esto conduce a la mejor coincidencia posible del macrobloque en el marco de referencia con un bloque en otro marco. La imagen compensada por movimiento resultante tiene la relación señal-ruido máxima más alta en comparación con cualquier otro algoritmo de coincidencia de bloques. Sin embargo, este es el algoritmo de coincidencia de bloques más extenso desde el punto de vista computacional de todos. Una ventana de búsqueda más grande requiere una mayor cantidad de cálculos.
El algoritmo de coincidencia de bloques jerárquicos optimizados (OHBM) acelera la búsqueda exhaustiva basada en las pirámides de imágenes optimizadas. [3]
Es uno de los primeros algoritmos de coincidencia rápida de bloques. Funciona de la siguiente manera:
La ubicación resultante para S=1 es la que tiene la función de costo mínima y el bloque macro en esta ubicación es la que mejor coincide.
En este algoritmo, el cálculo se reduce en un factor de 9. Para p=7, mientras que ES evalúa el costo para 225 macrobloques, TSS evalúa solo para 25 macrobloques.
El TDLS está estrechamente relacionado con el TSS, pero es más preciso para estimar vectores de movimiento para una ventana de búsqueda de gran tamaño. El algoritmo se puede describir de la siguiente manera:
El TSS utiliza un patrón de verificación asignado de manera uniforme y es propenso a perder pequeños movimientos. El NTSS [4] es una mejora con respecto al TSS, ya que proporciona un esquema de búsqueda centrado y tiene disposiciones para detenerse a mitad de camino para reducir el costo computacional. Fue uno de los primeros algoritmos rápidos ampliamente aceptados y se utilizó con frecuencia para implementar estándares anteriores como MPEG 1 y H.261.
El algoritmo funciona de la siguiente manera:
Por lo tanto, este algoritmo verifica 17 puntos para cada macrobloque y, en el peor de los casos, implica verificar 33 ubicaciones, lo que sigue siendo mucho más rápido que TSS.
La idea detrás de TSS es que la superficie de error debido al movimiento en cada macrobloque es unimodal . Una superficie unimodal es una superficie con forma de cuenco tal que los pesos generados por la función de costo aumentan monótonamente a partir del mínimo global. Sin embargo, una superficie unimodal no puede tener dos mínimos en direcciones opuestas y, por lo tanto, la búsqueda de patrón fijo de 8 puntos de TSS se puede modificar aún más para incorporar esto y ahorrar cálculos. SES [5] es la extensión de TSS que incorpora este supuesto.
El algoritmo SES mejora el algoritmo TSS ya que cada paso de búsqueda en SES se divide en dos fases:
• Primera fase:
• Dividir el área de búsqueda en cuatro cuadrantes • Iniciar la búsqueda con tres ubicaciones, una en el centro (A) y otras (B y C), S=4 ubicaciones alejadas de A en direcciones ortogonales • Encuentre puntos en el cuadrante de búsqueda para la segunda fase utilizando la distribución de peso para A, B, C: • Si (MAD(A)>=MAD(B) y MAD(A)>=MAD(C)), seleccione puntos en el cuadrante IV de la segunda fase • Si (MAD(A)>=MAD(B) y MAD(A)<=MAD(C)), seleccione puntos en el cuadrante I de la segunda fase • Si (MAD(A)<MAD(B) y MAD(A)<MAD(C)), seleccione puntos en el cuadrante II de la segunda fase • Si (MAD(A)<MAD(B) y MAD(A)>=MAD(C)), seleccione puntos en el cuadrante III de la segunda fase
• Segunda Fase:
• Encuentra la ubicación con menor peso • Establezca el nuevo origen de búsqueda como el punto encontrado anteriormente
• Establezca el nuevo tamaño de paso como S = S/2
• Repita el procedimiento de búsqueda SES hasta que S=1
• Seleccione la ubicación con el peso más bajo como vector de movimiento. SES es computacionalmente muy eficiente en comparación con TSS. Sin embargo, la relación señal-ruido máxima lograda es deficiente en comparación con TSS, ya que las superficies de error no son estrictamente unimodales en la realidad.
La búsqueda en cuatro pasos es una mejora con respecto a TSS en términos de menor costo computacional y mejor relación señal-ruido pico. De manera similar a NTSS, FSS [6] también emplea búsqueda con polarización central y tiene una disposición de parada a mitad de camino.
El algoritmo funciona de la siguiente manera:
El algoritmo Diamond Search (DS) [7] utiliza un patrón de puntos de búsqueda en forma de diamante y funciona exactamente igual que 4SS. Sin embargo, no hay límite en la cantidad de pasos que puede realizar el algoritmo.
Se utilizan dos tipos diferentes de patrones fijos para la búsqueda,
El algoritmo funciona de la siguiente manera:
Este algoritmo encuentra el mínimo global con mucha precisión, ya que el patrón de búsqueda no es ni demasiado grande ni demasiado pequeño. El algoritmo de búsqueda Diamond tiene una relación señal-ruido máxima cercana a la de la búsqueda exhaustiva con un gasto computacional significativamente menor.
El algoritmo de búsqueda de patrones de rood adaptativo (ARPS) [8] aprovecha el hecho de que el movimiento general en un marco suele ser coherente , es decir, si los macrobloques alrededor del macrobloque actual se movieron en una dirección particular, entonces existe una alta probabilidad de que el macrobloque actual también tenga un vector de movimiento similar . Este algoritmo utiliza el vector de movimiento del macrobloque a su izquierda inmediata para predecir su propio vector de movimiento.
La búsqueda de patrones de ruta adaptativos se ejecuta de la siguiente manera:
La búsqueda de patrones de Rood ubica directamente la búsqueda en un área donde hay una alta probabilidad de encontrar un buen bloque coincidente. La principal ventaja de ARPS sobre DS es que si el vector de movimiento predicho es (0, 0), no pierde tiempo computacional al hacer LDSP, sino que comienza directamente a usar SDSP. Además, si el vector de movimiento predicho está lejos del centro, ARPS nuevamente ahorra cálculos al saltar directamente a esa vecindad y usar SDSP, mientras que DS se toma su tiempo para hacer LDSP.
1. http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation
2. https://www.ece.cmu.edu/~ee899/project/deepak_mid.htm
