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 de movimiento es que los patrones correspondientes a los objetos y el fondo en un cuadro de secuencia de vídeo se mueven dentro del cuadro para formar los objetos correspondientes en el cuadro siguiente. Esto puede usarse para descubrir la redundancia temporal en la secuencia de video, aumentando la efectividad de la compresión de video entre cuadros definiendo 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 cuadro actual de un video en macrobloques y comparar cada uno de los macrobloques con un bloque correspondiente y sus vecinos adyacentes en un cuadro cercano del video (a veces solo el anterior). Se crea un vector que modela el movimiento de un macrobloque de un lugar a otro. Este movimiento, calculado para todos los macrobloques que componen un cuadro, constituye el movimiento estimado en un cuadro.
El área de búsqueda para una buena coincidencia de macrobloque se decide por 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 hacen uso de este enfoque para resolver varios problemas inversos de restauración de imágenes , como la reducción de ruido [1] y el desvanecimiento [2] tanto en imágenes fijas como en vídeo digital .
Motivación
La estimación de movimiento es el proceso de determinar los vectores de movimiento que describen la transformación de una imagen 2D a otra; generalmente de fotogramas adyacentes en una secuencia de video. Los vectores de movimiento pueden relacionarse con la imagen completa (estimación de movimiento global) o partes específicas, como bloques rectangulares, parches de formas arbitrarias 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 traslación en las tres dimensiones y el zoom.
Aplicar los vectores de movimiento a una imagen para predecir la transformación a otra imagen, debido al movimiento de la cámara u 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 video utilizada por MPEG 1, 2 y 4, así como muchos otros códecs de video .
La compresión de video basada en estimación de movimiento ayuda a ahorrar bits al enviar imágenes diferenciales codificadas que tienen inherentemente menos entropía en lugar de enviar un cuadro completamente codificado. Sin embargo, la operación más costosa desde el punto de vista computacional y con más recursos en todo el proceso de compresión es la estimación de movimiento. Por lo tanto, los algoritmos rápidos y computacionalmente económicos para la estimación del movimiento son una necesidad para la compresión de video.
Métricas de evaluación
Una métrica para hacer coincidir un macrobloque con otro bloque se basa en una función de costo. El más popular en términos de gasto computacional es:
Diferencia media o diferencia media absoluta (MAD) =
Error cuadrático medio (MSE) =
donde N es el tamaño del macrobloque, y y son los píxeles que se comparan en el macrobloque actual y en el macrobloque de referencia, respectivamente.
La imagen de movimiento compensado que se crea utilizando los vectores de movimiento y macrobloques del marco de referencia se caracteriza por la relación pico señal / ruido (PSNR),
Algoritmos
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.
Búsqueda exhaustiva
Este algoritmo calcula la función de costo en cada posible ubicación 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 con compensación de movimiento resultante tiene la relación pico de señal a ruido 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 entre todos. Una ventana de búsqueda más grande requiere un mayor número de cálculos.
Coincidencia de bloques jerárquica optimizada (OHBM)
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]
Búsqueda de tres pasos
Es uno de los primeros algoritmos de coincidencia de bloques rápidos. Funciona de la siguiente manera:
- Comience con la ubicación de búsqueda en el centro
- Configure el tamaño de paso S = 4 y el parámetro de búsqueda p = 7
- Busque 8 ubicaciones +/- S píxeles alrededor de la ubicación (0,0) y la ubicación (0,0)
- Elija entre las 9 ubicaciones buscadas, la que tiene la función de costo mínimo
- Establecer el nuevo origen de búsqueda en la ubicación seleccionada anteriormente
- Establezca el nuevo tamaño de paso como S = S / 2
- Repita el procedimiento de búsqueda hasta que S = 1
La ubicación resultante para S = 1 es la que tiene la función de costo mínimo y el macrobloque en esta ubicación es la mejor combinación.
Hay una reducción en el cálculo por un factor de 9 en este algoritmo. Para p = 7, mientras que ES evalúa el costo de 225 macrobloques, TSS solo evalúa 25 macrobloques.
Búsqueda logarítmica bidimensional
TDLS está estrechamente relacionado con TSS, sin embargo, es más preciso para estimar vectores de movimiento para un tamaño de ventana de búsqueda grande. El algoritmo se puede describir de la siguiente manera,
- Comience con la ubicación de búsqueda en el centro
- Seleccione un tamaño de paso inicial, digamos, S = 8
- Busque 4 ubicaciones a una distancia de S desde el centro en los ejes X e Y
- Encuentre la ubicación del punto con la función de menor costo
- Si un punto que no sea el centro es el mejor punto de coincidencia,
- Seleccione este punto como el nuevo centro
- Repita los pasos 2 a 3.
- Si el mejor punto de coincidencia está en el centro, establezca S = S / 2
- Si S = 1, se buscan las 8 ubicaciones alrededor del centro a una distancia S
- Establezca el vector de movimiento como el punto con la función de menor costo
Nueva búsqueda de tres pasos
TSS utiliza un patrón de verificación asignado uniformemente y es propenso a perder pequeños movimientos. NTSS [4] es una mejora con respecto a TSS, ya que proporciona un esquema de búsqueda con sesgo central y tiene disposiciones para detenerse a la mitad para reducir el costo computacional. Fue uno de los primeros algoritmos rápidos ampliamente aceptados y se utiliza con frecuencia para implementar estándares anteriores como MPEG 1 y H.261.
El algoritmo se ejecuta de la siguiente manera:
- Comience con la ubicación de búsqueda en el centro
- Busque 8 ubicaciones +/- S píxeles con S = 4 y 8 ubicaciones +/- S píxeles con S = 1 alrededor de la ubicación (0,0)
- Elija entre las 16 ubicaciones buscadas, la que tiene la función de costo mínimo
- Si la función de costo mínimo ocurre en el origen, detenga la búsqueda y establezca el vector de movimiento en (0,0)
- Si la función de costo mínimo ocurre en una de las 8 ubicaciones en S = 1, establezca el nuevo origen de búsqueda en esta ubicación.
- Verifique los pesos adyacentes para esta ubicación, dependiendo de la ubicación, puede verificar 3 o 5 puntos
- El que da el peso más bajo es el más cercano, establezca el vector de movimiento en esa ubicación
- Si el peso más bajo después del primer paso fue una de las 8 ubicaciones en S = 4, se sigue el procedimiento normal de TSS
- Elija entre las 9 ubicaciones buscadas, la que tiene la función de costo mínimo
- Establecer el nuevo origen de búsqueda en la ubicación seleccionada anteriormente
- Establezca el nuevo tamaño de paso como S = S / 2
- Repita el procedimiento de búsqueda hasta que S = 1
Por lo tanto, este algoritmo verifica 17 puntos para cada macrobloque y el peor de los casos implica verificar 33 ubicaciones, lo que sigue siendo mucho más rápido que TSS.
Búsqueda simple y eficiente
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 en forma de cuenco de modo que los pesos generados por la función de coste aumentan monótonamente desde el 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 puede modificarse 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 :
• Divida el área de búsqueda en cuatro cuadrantes • Inicie 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 A = 34,0444094, -1177977943; B = 34,043634, -117,7897651; C = 34.04453, -117.7977953 • Encuentre puntos en el cuadrante de búsqueda para la segunda fase usando 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)• Si (MAD (A) = MAD (C)), seleccione puntos en el cuadrante III de la segunda fase
• Segunda fase:
• Encuentra la ubicación con el peso más bajo • Establecer el nuevo origen de búsqueda como el punto que se encuentra arriba
• Establezca el nuevo tamaño de paso como S = S / 2
• Repita el procedimiento de búsqueda de SES hasta que S = 1
• Seleccione la ubicación con el peso más bajo ya que el vector de movimiento SES es computacionalmente muy eficiente en comparación con TSS. Sin embargo, la relación pico de señal a ruido alcanzada es pobre en comparación con TSS, ya que las superficies de error no son estrictamente unimodales en la realidad. 34.0444094
Búsqueda de cuatro pasos
La búsqueda de cuatro pasos es una mejora con respecto a TSS en términos de menor costo computacional y mejor relación señal / ruido de pico. 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 se ejecuta de la siguiente manera:
- Comience con la ubicación de búsqueda en el centro
- Ajuste el tamaño de paso S = 2, (independientemente del parámetro de búsqueda p)
- Busque 8 ubicaciones +/- S píxeles alrededor de la ubicación (0,0) ubicaciones 1 = 34.0460965, -117.7955275;
2 = 34,0464443, -117,7990496; 3 = 34,0446975, -117,7999699; 4 = 34.0438915, -117.7952174
- Elija entre las 9 ubicaciones buscadas, la que tiene la función de costo mínimo
- Si el peso mínimo se encuentra en el centro de la ventana de búsqueda:
- Establezca el nuevo tamaño de paso como S = S / 2 (es decir, S = 1)
- Repita el procedimiento de búsqueda desde los pasos 3 a 4
- Seleccione la ubicación con el menor peso como vector de movimiento
- Si el peso mínimo se encuentra en una de las 8 ubicaciones distintas del centro:
- Establecer el nuevo origen en esta ubicación
- Fije el tamaño del paso como S = 2
- Repita el procedimiento de búsqueda desde los pasos 3 a 4. Dependiendo de la ubicación del nuevo origen, busque entre 5 ubicaciones o 3 ubicaciones
- Seleccione la ubicación con el menor peso 34.043634, -117.7897651
- Si la ubicación de menor peso está en el centro de la nueva ventana, vaya al paso 5, de lo contrario, vaya al paso 6
Búsqueda de diamantes
El algoritmo Diamond Search (DS) [7] utiliza un patrón de puntos de búsqueda de diamantes y el algoritmo funciona exactamente igual que 4SS. Sin embargo, no hay límite en el número de pasos que puede realizar el algoritmo.
Se utilizan dos tipos diferentes de patrones fijos para la búsqueda,
- Patrón de búsqueda de diamantes grandes (LDSP)
- Patrón de búsqueda de diamantes pequeños (SDSP)
El algoritmo se ejecuta de la siguiente manera:
- LDSP:
- Comience con la ubicación de búsqueda en el centro
- Establecer tamaño de paso S = 2
- Busque 8 píxeles de ubicación (X, Y) de modo que (| X | + | Y | = S) alrededor de la ubicación (0,0) utilizando un patrón de punto de búsqueda de diamante
- Elija entre las 9 ubicaciones buscadas, la que tiene la función de costo mínimo
- Si el peso mínimo se encuentra en el centro de la ventana de búsqueda, vaya al paso SDSP
- Si el peso mínimo se encuentra en una de las 8 ubicaciones distintas del centro, establezca el nuevo origen en esta ubicación
- Repetir LDSP
- SDSP:
- Establecer el nuevo origen de búsqueda
- Establezca el nuevo tamaño de paso como S = S / 2 (es decir, S = 1)
- Repita el procedimiento de búsqueda para encontrar la ubicación con el menor peso.
- Seleccione la ubicación con el peso mínimo como la ubicación del vector de movimiento del vector de movimiento con el peso mínimo 34.0444094, -1177977943
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 Diamond Search tiene una relación pico de señal a ruido cercana a la de Exhaustive Search con un gasto computacional significativamente menor.
Búsqueda adaptativa de patrones de vigas
El algoritmo Adaptive Rood Pattern Search (ARPS) [8] hace uso del hecho de que el movimiento general en una trama suele ser coherente , es decir, si los macrobloques alrededor del macrobloque actual se movieron en una dirección particular, existe una alta probabilidad de que el El macrobloque actual también tendrá un vector de movimiento similar . Este algoritmo usa el vector de movimiento del macrobloque a su izquierda inmediata para predecir su propio vector de movimiento.
La búsqueda de patrón de rood adaptativo se ejecuta de la siguiente manera:
- Comience con la ubicación de búsqueda en el centro (origen)
- Encuentre el vector de movimiento predicho para el bloque
- Establecer el tamaño del paso S = max (| X |, | Y |), donde (X, Y) es la coordenada del vector de movimiento predicho
- Busque puntos distribuidos en el patrón de rood alrededor del origen en el tamaño de paso S
- Establecer el punto con menor peso como origen
- Busque utilizando un patrón de búsqueda de diamantes pequeños (SDSP) alrededor del nuevo origen
- Repita la búsqueda de SDSP hasta que el punto menos ponderado esté en el centro de SDSP
La búsqueda de patrón de ruta coloca 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 haciendo LDSP, sino que comienza a usar SDSP directamente. Además, si el vector de movimiento predicho está lejos del centro, entonces ARPS ahorra nuevamente en cálculos saltando directamente a esa vecindad y usando SDSP, mientras que DS se toma su tiempo haciendo LDSP.
Referencias
- ^ Dabov, Kostadin; Foi, Alessandro; Katkovnik, Vladimir; Egiazarian, Karen (16 de julio de 2007). "Eliminación de ruido de imágenes mediante filtrado colaborativo de dominio de transformación 3D disperso". Transacciones IEEE sobre procesamiento de imágenes . 16 (8): 2080–2095. Código Bibliográfico : 2007ITIP ... 16.2080D . CiteSeerX 10.1.1.219.5398 . doi : 10.1109 / TIP.2007.901238 . PMID 17688213 . S2CID 1475121 .
- ^ Danielyan, Aram; Katkovnik, Vladimir; Egiazarian, Karen (30 de junio de 2011). "Marcos BM3D y Deslizamiento de imágenes variacionales". Transacciones IEEE sobre procesamiento de imágenes . 21 (4): 1715–28. arXiv : 1106.6180 . Código bibliográfico : 2012ITIP ... 21.1715D . doi : 10.1109 / TIP.2011.2176954 . PMID 22128008 . S2CID 11204616 .
- ^ Je, Changsoo; Park, Hyung-Min (2013). "Coincidencia de bloques jerárquica optimizada para un registro de imágenes rápido y preciso". Procesamiento de señales: comunicación de imágenes . 28 (7): 779–791. doi : 10.1016 / j.image.2013.04.002 .
- ^ Li, Renxiang; Zeng, Bing; Liou, Ming (agosto de 1994). "Un nuevo algoritmo de búsqueda de tres pasos para la estimación del movimiento de bloques". IEEE Trans. Circuitos y sistemas para tecnología de video . 4 (4): 438–442. doi : 10.1109 / 76.313138 .
- ^ Lu, Jianhua; Liou, Ming (abril de 1997). "Un algoritmo de búsqueda simple y eficiente para la estimación de movimiento de coincidencia de bloques". IEEE Trans. Circuitos y sistemas para tecnología de video . 7 (2): 429–433. doi : 10.1109 / 76.564122 .
- ^ Po, Lai-Man; Ma, Wing-Chung (junio de 1996). "Un algoritmo de búsqueda de cuatro pasos novedoso para la estimación de movimiento de bloque rápido". IEEE Trans. Circuitos y sistemas para tecnología de video . 6 (3): 313–317. doi : 10.1109 / 76.499840 .
- ^ Zhu, Shan; Ma, Kai-Kuang (febrero de 2000). "Un nuevo algoritmo de búsqueda de diamantes para la estimación de movimiento de coincidencia de bloques rápida". EEE Trans. Procesamiento de imágenes . 9 (12): 287–290. doi : 10.1109 / 83.821744 . PMID 18255398 .
- ^ Nie, Yao; Ma, Kai-Kuang (diciembre de 2002). "Búsqueda adaptativa de patrones de vigas para una estimación rápida del movimiento de coincidencia de bloques" (PDF) . IEEE Trans. Procesamiento de imágenes . 11 (12): 1442-1448. doi : 10.1109 / TIP.2002.806251 . PMID 18249712 .
enlaces externos
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