Hispanopedia Wiki
Articulo de referencia

Algoritmo de coincidencia de bloques

Un algoritmo de coincidencia de bloques es un método para localizar macrobloques coincidentes en una secuencia de fotogramas de vídeo digital con el fin de estimar el movimiento...

Hispanopedia WikiContenido en espanolLectura gratuita

Un algoritmo de coincidencia de bloques es un método para localizar macrobloques coincidentes en una secuencia de fotogramas de vídeo digital con el fin de estimar el movimiento . La premisa fundamental de la estimación de movimiento es que los patrones correspondientes a los objetos y al fondo en un fotograma de la secuencia de vídeo se mueven dentro de este para formar objetos correspondientes en el fotograma siguiente. Esto permite detectar redundancias temporales en la secuencia de vídeo, aumentando la eficacia de la compresión de vídeo entre fotogramas al definir el contenido de un macrobloque en función del contenido de un macrobloque conocido que difiere mínimamente.

Un algoritmo de coincidencia de bloques consiste en dividir el fotograma actual de un vídeo en macrobloques y comparar cada uno de ellos con un bloque correspondiente y sus vecinos adyacentes en un fotograma cercano (a veces, simplemente el anterior). Se crea un vector que modela el movimiento de un macrobloque de una posición a otra. Este movimiento, calculado para todos los macrobloques que componen un fotograma, constituye el movimiento estimado en dicho fotograma.

El área de búsqueda para encontrar una buena coincidencia con un macrobloque viene determinada 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 fotograma anterior. El parámetro de búsqueda mide el movimiento. Cuanto mayor sea el valor de p, mayor será el movimiento potencial y la probabilidad 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 16 píxeles y un área de búsqueda de p = 7 píxeles.

El emparejamiento de bloques y el filtrado 3D utilizan este enfoque para resolver varios 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 .

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, entre fotogramas adyacentes en una secuencia de vídeo. Los vectores de movimiento pueden referirse a la imagen completa (estimación de movimiento global) o a partes específicas, como bloques rectangulares, parches de forma arbitraria o incluso píxeles individuales. Estos vectores pueden representarse mediante un modelo de traslación u otros modelos que permiten aproximar el movimiento de una cámara de vídeo real, como la rotación y la traslación en las tres dimensiones, así como el zoom.

Aplicar los vectores de movimiento a una imagen para predecir su transformación en otra imagen, debido al movimiento de la cámara o del objeto en la imagen, se denomina compensación de movimiento . La combinación de estimación y compensación de movimiento es una parte fundamental de la compresión de vídeo utilizada por MPEG 1, 2 y 4, así como por 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 de diferencia codificadas, que tienen inherentemente menos entropía que enviar un fotograma completamente codificado. Sin embargo, la estimación de movimiento es la operación que requiere mayor capacidad computacional y recursos en todo el proceso de compresión. Por lo tanto, se necesitan algoritmos rápidos y computacionalmente económicos para la estimación de movimiento en la compresión de vídeo.

Métricas de evaluación

Una métrica para emparejar un macrobloque con otro bloque se basa en una función de coste. La más popular en términos de coste computacional es:

Diferencia media o diferencia absoluta media (DAM) =1norte2∑i=0norte−1∑j=0norte−1|doij−Rij|{\displaystyle {\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}|C_{ij}-R_{ij}|}

Error cuadrático medio (ECM) =1norte2∑i=0norte−1∑j=0norte−1(doij−Rij)2{\displaystyle {\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}(C_{ij}-R_{ij})^{2}}

donde N es el tamaño del macrobloque ydoij{\displaystyle C_{ij}}yRij{\displaystyle R_{ij}}son los píxeles que se comparan en el macrobloque actual y en el macrobloque de referencia, respectivamente.

La imagen compensada por movimiento que se crea utilizando los vectores de movimiento y los macrobloques del fotograma de referencia se caracteriza por la relación señal-ruido máxima (PSNR),

PSNR=10registro10⁡(valor pico a pico de los datos originales)2MSE{\displaystyle {\text{PSNR}}=10\log _{10}{\frac {({\text{peak to peak value of original data}})^{2}}{\text{MSE}}}}

Algoritmos

Los algoritmos de coincidencia de bloques se investigan 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 más común.

Este algoritmo calcula la función de coste en cada posible ubicación de la ventana de búsqueda. Esto permite obtener la mejor coincidencia posible entre el macrobloque del fotograma de referencia y un bloque de otro fotograma. La imagen resultante, compensada por movimiento, presenta la mayor relación señal-ruido máxima en comparación con cualquier otro algoritmo de coincidencia de bloques. Sin embargo, este es el algoritmo de coincidencia de bloques que requiere mayor capacidad de cálculo. Una ventana de búsqueda más grande exige un mayor número de cálculos.

Coincidencia de bloques jerárquica optimizada (OHBM)

El algoritmo de coincidencia de bloques jerárquicos optimizado (OHBM) acelera la búsqueda exhaustiva basada en las pirámides de imágenes optimizadas. [ 3 ]

Es uno de los primeros algoritmos rápidos de coincidencia de bloques. Funciona de la siguiente manera:

  1. Comience con la ubicación de búsqueda en el centro
  2. Establezca el tamaño del paso S = 4 y el parámetro de búsqueda p = 7.
  3. Buscar 8 ubicaciones +/- S píxeles alrededor de la ubicación (0,0) y la ubicación (0,0)
  4. Seleccione entre las 9 ubicaciones buscadas la que tenga la función de costo mínimo.
  5. Establezca el nuevo origen de búsqueda en la ubicación seleccionada anteriormente.
  6. Establezca el nuevo tamaño de paso como S = S/2
  7. 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ínima y el macrobloque en esta ubicación es la que mejor se ajusta.

Este algoritmo reduce el tiempo de cálculo en un factor de 9. Para p=7, mientras que ES evalúa el coste para 225 macrobloques, TSS lo evalúa solo para 25 macrobloques.

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:

  1. Comience con la ubicación de búsqueda en el centro.
  2. Seleccione un tamaño de paso inicial, por ejemplo, S = 8.
  3. Buscar 4 ubicaciones a una distancia S del centro en los ejes X e Y.
  4. Encuentra la ubicación del punto con la función de costo mínimo.
  5. Si un punto distinto del centro es el punto que mejor coincide,
    1. Seleccione este punto como el nuevo centro.
  6. Si el punto que mejor coincide está en el centro, establece S = S/2.
  7. Repita los pasos 2 a 3.
  8. Si S = 1, se buscan las 8 ubicaciones alrededor del centro a una distancia S.
  9. Establezca el vector de movimiento como el punto con la función de costo mínimo.

TSS utiliza un patrón de verificación uniformemente distribuido y es propenso a pasar por alto pequeños movimientos. NTSS [ 4 ] representa una mejora con respecto a TSS, ya que proporciona un esquema de búsqueda centrado y cuenta con mecanismos para detenerse a la mitad y así 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:

  1. Comience con la ubicación de búsqueda en el centro
  2. Buscar 8 ubicaciones +/- S píxeles con S = 4 y 8 ubicaciones +/- S píxeles con S = 1 alrededor de la ubicación (0,0)
  3. Seleccione entre las 16 ubicaciones buscadas la que tenga la función de costo mínimo.
  4. Si la función de costo mínimo se produce en el origen, detenga la búsqueda y establezca el vector de movimiento en (0,0).
  5. 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 esa ubicación.
    1. Verifique los pesos adyacentes para esta ubicación; dependiendo de la ubicación, puede verificar 3 o 5 puntos.
  6. El que dé el menor peso es el que mejor se ajusta, establezca el vector de movimiento en esa ubicación.
  7. Si el peso más bajo después del primer paso fue una de las 8 ubicaciones en S = 4, se sigue el procedimiento TSS normal.
    1. Seleccione entre las 9 ubicaciones buscadas la que tenga la función de costo mínimo.
    2. Establezca el nuevo origen de búsqueda en la ubicación seleccionada anteriormente.
    3. Establezca el nuevo tamaño de paso como S = S/2
    4. Repita el procedimiento de búsqueda hasta que S = 1.

Por lo tanto, este algoritmo verifica 17 puntos para cada macrobloque y el peor escenario posible 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 debida 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, por lo que la búsqueda de patrón fijo de 8 puntos de TSS puede modificarse para incorporar esto y ahorrar cálculos. SES [ 5 ] es la extensión de TSS que incorpora esta suposición.

El algoritmo SES mejora el algoritmo TSS ya que cada paso de búsqueda en SES se divide en dos fases:

• Primera fase  :

 • Divide el área de búsqueda en cuatro cuadrantes. • Inicie la búsqueda con tres ubicaciones, una en el centro (A) y las otras (B y C), S=4 ubicaciones de distancia de A en direcciones ortogonales. • Encuentra puntos en el cuadrante de búsqueda para la segunda fase utilizando la distribución de pesos para A, B, C: • Si (MAD(A)>=MAD(B) y MAD(A)>=MAD(C)), seleccione puntos en el segundo cuadrante de la fase IV • Si (MAD(A)>=MAD(B) y MAD(A)<=MAD(C)), seleccione puntos en el segundo cuadrante de fase I • Si (MAD(A)<MAD(B) y MAD(A)<MAD(C)), seleccione puntos en el segundo cuadrante de la fase II • Si (MAD(A)<MAD(B) y MAD(A)>=MAD(C)), seleccione puntos en el segundo cuadrante de la fase III

• Segunda fase:

 • Encuentra la ubicación con el peso más bajo • Establezca el nuevo punto de origen de la 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

• Seleccionar la ubicación con el menor peso como vector de movimiento SES es computacionalmente muy eficiente en comparación con TSS. Sin embargo, la relación señal-ruido máxima alcanzada es baja en comparación con TSS, ya que las superficies de error no son estrictamente unimodales en la realidad.

La búsqueda en cuatro pasos (FSS) supone una mejora con respecto a TSS en términos de menor coste computacional y mejor relación señal-ruido máxima. Al igual que NTSS, FSS [ 6 ] también emplea una búsqueda con sesgo central y dispone de una parada intermedia.

El algoritmo funciona de la siguiente manera:

  1. Comience con la ubicación de búsqueda en el centro
  2. Establezca el tamaño del paso S = 2, (independientemente del parámetro de búsqueda p)
  3. Buscar en 8 ubicaciones +/- S píxeles alrededor de la ubicación (0,0)
  4. Seleccione entre las 9 ubicaciones buscadas la que tenga la función de costo mínimo.
  5. Si el peso mínimo se encuentra en el centro de la ventana de búsqueda:
    1. Establezca el nuevo tamaño de paso como S = S/2 (es decir, S = 1).
    2. Repita el procedimiento de búsqueda de los pasos 3 a 4.
    3. Seleccionar la ubicación con el menor peso como vector de movimiento
  6. Si el peso mínimo se encuentra en uno de los 8 lugares distintos del centro:
    1. Establezca el nuevo origen en esta ubicación.
    2. Fije el tamaño del paso como S = 2
    3. Repita el procedimiento de búsqueda de los pasos 3 a 4. Dependiendo de la ubicación del nuevo origen, busque en 5 ubicaciones o en 3 ubicaciones.
    4. Seleccione la ubicación con el menor peso
    5. Si la ubicación de menor peso se encuentra en el centro de la nueva ventana, vaya al paso 5; de lo contrario, vaya al paso 6.

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 el número de pasos que puede realizar el algoritmo.

Para la búsqueda se utilizan dos tipos diferentes de patrones fijos:

  • Patrón de búsqueda de diamante grande (LDSP)
  • Patrón de búsqueda de diamante pequeño (SDSP)

El algoritmo funciona de la siguiente manera:

  • LDSP:
    1. Comience con la ubicación de búsqueda en el centro
    2. Establecer el tamaño del paso S = 2
    3. Buscar 8 ubicaciones de píxeles (X,Y) tales que (|X|+|Y|=S) alrededor de la ubicación (0,0) utilizando un patrón de búsqueda de puntos en forma de diamante.
    4. Seleccione entre las 9 ubicaciones buscadas la que tenga la función de costo mínimo.
    5. Si se encuentra el peso mínimo en el centro de la ventana de búsqueda, vaya al paso SDSP.
    6. Si el peso mínimo se encuentra en una de las 8 ubicaciones distintas del centro, establezca el nuevo origen en esa ubicación.
    7. Repetir LDSP
  • SDSP:
    1. Establecer el nuevo origen de búsqueda
    2. Establezca el nuevo tamaño de paso como S = S/2 (es decir, S = 1).
    3. Repita el procedimiento de búsqueda para encontrar la ubicación con menor peso.
    4. Seleccionar la ubicación con el menor peso como vector de movimiento

Este algoritmo encuentra el mínimo global con gran 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 similar a la de la búsqueda exhaustiva, con un coste computacional significativamente menor.

El algoritmo de búsqueda adaptativa de patrones de raíz (ARPS) [ 8 ] aprovecha el hecho de que el movimiento general en un marco suele ser coherente ; es decir, si los macrobloques que rodean al macrobloque actual se mueven en una dirección determinada, 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 situado inmediatamente a su izquierda para predecir su propio vector de movimiento.

La búsqueda adaptativa de patrones de raíz se ejecuta de la siguiente manera:

  1. Comience con la ubicación de búsqueda en el centro (origen).
  2. Encuentra el vector de movimiento previsto para el bloque.
  3. Establezca el tamaño del paso S = max (|X|,|Y|), donde (X,Y) es la coordenada del vector de movimiento previsto.
  4. Búsqueda de patrones de raíz con puntos distribuidos alrededor del origen en un paso de tamaño S.
  5. Establezca el punto con menor peso como origen.
  6. Búsqueda utilizando un patrón de búsqueda de diamante pequeño (SDSP) alrededor del nuevo origen.
  7. Repita la búsqueda SDSP hasta que el punto de menor peso se encuentre en el centro de SDSP.

La búsqueda de patrones de raíz sitúa directamente la búsqueda en un área con alta probabilidad de encontrar un bloque coincidente. La principal ventaja de ARPS sobre DS es que, si el vector de movimiento predicho es (0, 0), no desperdicia tiempo computacional en realizar LDSP, sino que comienza directamente con SDSP. Además, si el vector de movimiento predicho está lejos del centro, ARPS también ahorra tiempo computacional saltando directamente a esa zona y utilizando SDSP, mientras que DS tarda más en realizar LDSP.

Referencias

  1. ↑ Dabov, Kostadin; Foi, Alessandro; Katkovnik, Vladimir; Egiazarian, Karen (16 de julio de 2007). "Image denoising by sparse 3D transform-domain collaborative filtering". IEEE Transactions on Image Processing . 16 (8): 2080– 2095. Bibcode : 2007ITIP...16.2080D . CiteSeerX 10.1.1.219.5398 . doi : 10.1109/TIP.2007.901238 . PMID 17688213 . S2CID 1475121 .   
  2. ↑ Danielyan, Aram; Katkovnik, Vladimir; Egiazarian, Karen (30 de junio de 2011). "Marcos BM3D y desenfoque de imágenes variacional". IEEE Transactions on Image Processing . 21 (4): 1715– 28. arXiv : 1106.6180 . Bibcode : 2012ITIP...21.1715D . doi : 10.1109/TIP.2011.2176954 . PMID 22128008. S2CID 11204616 .  
  3. ↑ Je, Changsoo; Park, Hyung-Min (2013). "Optimized hierarchical block matching for fast and accurate image registration". Signal Processing: Image Communication . 28 (7): 779– 791. doi : 10.1016/j.image.2013.04.002 .
  4. ↑ 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 Transactions on Circuits and Systems for Video Technology . 4 (4): 438– 442. doi : 10.1109/76.313138 .
  5. ↑ Lu, Jianhua; Liou, Ming (abril de 1997). "Un algoritmo de búsqueda simple y eficiente para la estimación de movimiento por coincidencia de bloques". IEEE Transactions on Circuits and Systems for Video Technology . 7 (2): 429– 433. doi : 10.1109/76.564122 .
  6. ↑ Po, Lai-Man; Ma, Wing-Chung (junio de 1996). "Un nuevo algoritmo de búsqueda de cuatro pasos para la estimación rápida del movimiento de bloques". IEEE Transactions on Circuits and Systems for Video Technology . 6 (3): 313– 317. doi : 10.1109/76.499840 .
  7. ↑ Zhu, Shan; Ma, Kai-Kuang (febrero de 2000). "Un nuevo algoritmo de búsqueda de diamante para la estimación rápida del movimiento por coincidencia de bloques". IEEE Transactions on Image Processing . 9 (12): 287– 290. Bibcode : 2000ITIP....9..287Z . doi : 10.1109/83.821744 . PMID 18255398 . 
  8. ↑ Nie, Yao; Ma, Kai-Kuang (diciembre de 2002). "Búsqueda adaptativa de patrones de raíz para estimación rápida de movimiento por coincidencia de bloques" (PDF) . IEEE Transactions on Image Processing . 11 (12): 1442– 1448. Bibcode : 2002ITIP...11.1442N . doi : 10.1109/TIP.2002.806251 . PMID 18249712 . 

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

Obtenido de " https://en.wikipedia.org/w/index.php?title=Block-matching_algorithm&oldid=1320938267 "
Lecturas relacionadas
6 articulos
MacrobloqueEl macrobloque es una unidad de procesamiento en formatos de compresión de imagen y vídeo basada en transformaciones de bloques lineales, típicamen...Vídeo digitalVídeo digitalEl vídeo digital es una representación electrónica de imágenes visuales en movimiento ( vídeo ) en forma de datos digitales codificados . Esto cont...Estimación de movimientoEstimación de movimientoEn visión artificial y procesamiento de imágenes , la estimación de movimiento es el proceso de determinar vectores de movimiento que describen la ...Compresión de datosCompresión de datosEn teoría de la información , la compresión de datos , codificación de fuente [1] o reducción de la tasa de bits es el proceso de codificar informa...Fotograma de la películaFotograma de la películaEn la producción cinematográfica , de vídeo , de animación y campos relacionados, un fotograma es una de las muchas imágenes fijas que componen la ...Vector (matemáticas y física)Vector (matemáticas y física)En matemáticas y física , vector es un término que se refiere a cantidades que no pueden expresarse mediante un único número (un escalar ), o a ele...