Monografias.com > Tecnología
Descargar Imprimir Comentar Ver trabajos relacionados

Redundancia Temporal y difusión de información multimedia




Enviado por Pablo Turmero



Partes: 1, 2, 3


    Monografias.com

    Redundancia temporal
    Se basa en la similitud de cuadros sucesivos en una secuencia de vídeo.
    Ej.: Secuencias de plano estático.
    Se utilizan técnicas de codificación diferencial o transformada 3D
    Sólo se codificarán las diferencias entre cuadros sucesivos (DPCM).
    La reconstrucción de un cuadro puede estar basado en otro(s) anterior(es).
    Un algoritmo típico de eliminación de redundancia temporal (motion compensation) es el que emplea MPEG.

    Monografias.com

    Redundancia temporal (MPEG-1)
    Cuadros de referencia y cuadros auto-contenidos
    Si F1 lo usamos para construir F2, se dice que F1 es un cuadro de referencia (reference frame).
    Si un cuadro no se construye a partir de ningún otro, se dice que es auto-contenido (intracoded frame)
    Normalmente estos sirven de referencia para otros.
    Macrobloques (macroblocks)
    16×16 pixels (6 bloques de 8×8: 4Y,1U y 1V).
    (Gp:) F1

    (Gp:) F2

    (Gp:) F3

    Monografias.com

    Redundancia temporal (MPEG-1)
    Vectores de movimiento (motion vector)
    Identifican el desplazamiento de un determinado macrobloque en el cuadro actual respecto a la posición que tenía en el cuadro de referencia.
    Los vectores de movimiento se aplican cuando se identifica un macrobloque existente en el cuadro de referencia (matching blocks)

    (Gp:) F1
    (Gp:) F2
    (Gp:) Macrobloques idénticos
    (Gp:) Vector de movimiento
    ?x = -20, ?y = 0
    (Gp:) Cuadro de referencia

    Monografias.com

    Redundancia temporal (MPEG-1)
    Búsqueda de macrobloques.
    Se buscan los macrobloques del cuadro a codificar en el cuadro de referencia.
    Si se encuentra el mismo macrobloque, sólo se codifica el vector de movimiento correspondiente.
    Si no se encuentra exactamente el mismo se elige el más parecido (macrobloque INTER).
    Se codifica el vector de movimiento.
    Se calcula el macrobloque error (las diferencias) aplicándole codificación estilo JPEG (DCT, quant, RLE+VLC en zigzag).
    Si no se encuentra ningún bloque similar (mb. INTRA)
    Se codifica dicho macrobloque con codificación estilo JPEG.

    Monografias.com

    Redundancia temporal (MPEG-1)
    Tipos de cuadros
    I (Intracoded frames): Cuadro codificado usando JPEG (autocontenido).
    P (Predictive frames): Cuadro basado en las diferencias respecto a un cuadro de referencia anterior (tipo I).
    B (Bidirectional frames): Cuadros basados en la interpolación de un cuadro anterior y otro posterior en la secuencia (tipo I o P).
    (Gp:) F1
    (Gp:) F2
    (Gp:) F3
    (Gp:) Cuadro de tipo I
    autocontenido
    (Gp:) Cuadro de tipo B
    basado en F1 y F3
    (Gp:) Cuadro de tipo P
    basado en F1
    (Gp:) Macrobloque
    encontrado!!
    (Gp:) Macrobloque
    encontrado!!

    Monografias.com

    Redundancia temporal (MPEG-1)
    Secuencias de cuadros (Group Of Pictures)
    Los cuadros de tipo I son los menos comprimidos, a continuación los de tipo P y por último los que más compresión obtiene son los de tipo B.
    Secuencias típicas:
    IBBBPBBBI
    IBBPBBPBBI (PAL)
    IBBPBBPBBPBBI (NTSC)
    (Gp:) I
    (Gp:) B
    (Gp:) B
    (Gp:) P
    (Gp:) B
    (Gp:) B
    (Gp:) P
    (Gp:) B
    (Gp:) B
    (Gp:) I

    Monografias.com

    Redundancia temporal (MPEG-1)
    La importancia de los cuadros de tipo I.
    En un sistema de vídeo es habitual el usar los controles de avance, retroceso, pausa, etc.
    Si queremos detener la secuencia de vídeo, necesitamos encontrar el último cuadro I para reconstruir el cuadro donde se ha detenido la imagen.
    Sirven como puntos de sincronización.
    Se estima que deben aparecer al menos un cuadro I cada 300-400 ms.
    Si se está difundiendo una secuencia de vídeo comprimida (TV broadcast, videoconferencia, etc)
    Permite “engancharse” rápidamente y recuperarse ante la recepción de algún cuadro dañado.

    Monografias.com

    Estimación de movimiento: Algoritmos
    La parte más costosa de la estimación de movimiento corresponde a los algoritmos de búsqueda de macrobloques en el cuadro(s) de referencia.
    Provoca codificación asimétrica
    Los algoritmos más conocidos son los siguientes:
    Búsqueda completa (Full-Search).
    TTS (Three-Step Search)
    Búsqueda logarítmica.
    Búsqueda en cruz (Cross-Search)
    OTS (One-at-a-Time Search)
    Vecinos más próximos (Nearest Neighbours Search)
    Búsqueda jerárquica.

    Monografias.com

    Estimación de movimiento.
    Se define una función de coste que calcula el error entre dos macrobloques, por ejemplo, SAE (Sum of Absolute Errors)* :

    (i,j) está definido dentro del área de búsqueda
    (NxM) determina las dimensiones del macrobloque.
    C(i,j) y R(i,j) definen los pixels del macrobloque actual y referencia respectivamente.
    Las coordenadas (i,j) que menor SAE exhiban determinarán el vector de movimiento del macrobloque actual.

    Monografias.com

    Algoritmos: Full Search.
    Examina todos los puntos del área de búsqueda (+/- p)
    Complejidad computacional por macrobloque:
    Número total de posiciones: (2p + 1)2
    Cada posición (i,j), MxN pixels.
    Cada pixel requiere: 1 resta, 1 suma y 1 valor absoluto.

    Complejidad (secuencia IxJ pixels @ F fps)

    Ejemplo:
    Broadcast TV (I=720, J=480, F=30, N=M=16)
    Coste de este algoritmo: 29.89 GOPS (p=15) ó 6.99 GOPS (p=7)

    Monografias.com

    Algoritmos: Three-Step Search.
    Coste:
    Examina puntos
    1.02 GOPS (p=15) ó 770 MOPS (p=7).
    MV: (7,-3)
    (Gp:) (-7,-7)
    (Gp:) (0,-7)
    (Gp:) (7,-7)
    (Gp:) (-7,7)
    (Gp:) (0,7)
    (Gp:) (7,7)

    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1

    (Gp:) 2
    (Gp:) 2
    (Gp:) 2
    (Gp:) 2
    (Gp:) 2
    (Gp:) 2
    (Gp:) 2
    (Gp:) 2

    (Gp:) 3
    (Gp:) 3
    (Gp:) 3
    (Gp:) 3
    (Gp:) 3
    (Gp:) 3
    (Gp:) 3
    (Gp:) 3

    Busca en la posición (0,0)
    S=2N-1 (step size)
    Busca 8 posiciones a +/-S píxeles alrededor de (0,0)
    De las nueva posiciones elige aquella con el SAD menor.
    S=S/2 y el nuevo origen de búsqueda el punto obtenido en 4.
    Repetir pasos 3-5 hasta que S=1.

    Monografias.com

    Algoritmos: Búsqueda logarítmica.
    Coste:
    Examina 20 puntos
    616 MOPS (p=7 y N=2).
    (Gp:) (-7,-7)
    (Gp:) (0,-7)
    (Gp:) (7,-7)
    (Gp:) (-7,7)
    (Gp:) (0,7)
    (Gp:) (7,7)

    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1

    (Gp:) 2
    (Gp:) 2
    (Gp:) 2

    (Gp:) 3
    (Gp:) 3

    (Gp:) 4
    (Gp:) 4

    (Gp:) 5
    (Gp:) 5
    (Gp:) 5
    (Gp:) 5
    (Gp:) 5
    (Gp:) 5
    (Gp:) 5
    (Gp:) 5

    MV: (5,-3)
    Busca en la posición (0,0) y establece S=N (step size)
    Selecciona 4 posiciones a S píxeles del origen en los ejes X e Y.
    Calcula la posición que ofrece el menor SAD, fijándola como el nuevo origen de la búsqueda
    Si esta posición es la central de las 5 seleccionadas S=S/2
    Si S=1 ir al paso 6, sino ir al paso 2.
    Selecciona el origen actual y las 8 posiciones de alrededor, y calcula aquella que minimiza el SAD

    Monografias.com

    Algoritmos: Búsqueda en cruz (Cross Search)
    Coste:
    Examina puntos
    523 MOPS (p=7).
    MV: (-3,-5)
    (Gp:) (-7,-7)
    (Gp:) (0,-7)
    (Gp:) (7,-7)
    (Gp:) (-7,7)
    (Gp:) (0,7)
    (Gp:) (7,7)

    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1

    (Gp:) 4
    (Gp:) 4

    (Gp:) 2
    (Gp:) 2
    (Gp:) 2
    (Gp:) 2

    (Gp:) 3
    (Gp:) 3
    (Gp:) 3
    (Gp:) 3

    Establece el origen en la posición (0,0). S=2N-1 (step size)
    Selecciona 4 posiciones a +/-S píxeles del origen formando una cruz (X) y el propio origen.
    Calcula la posición que ofrece el menor SAE, fijándola como el nuevo origen de la búsqueda
    Si (S>1) entonces S=S/2 y va al punto 2. Sino ir al punto 5.
    Si la mejor posición está en el punto superior izquierda o inferior derecha de la X, evaluar 4 puntos más en forma de X a una distancia de +/-1 pixel. Sino hacer lo mismo pero con los 4 puntos distribuidos en “+”.

    Monografias.com

    Algoritmos: OTS (One-at-a-Time Search)
    Coste:
    Examina 12 puntos
    369 MOP.
    MV: (-4,-3)
    (-7,-7)
    (0,-7)
    (7,-7)
    (-7,7)
    (0,7)
    (7,7)
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1

    2
    3
    4
    5
    Establece el origen en (0,0).
    Selecciona el origen y las dos posiciones vecinas en el eje X
    Calcula la posición que menor SAD exhiba. Si es el origen ir al paso 5.
    Establece el nuevo origen en la posición que ha ofrecido el menor SAD. Ir al paso 2.
    Repetir los pasos 2 al 4 seleccionando las posiciones en el sentido vertical (eje Y).
    (Gp:) 6
    (Gp:) 6

    7
    8
    9
    Puede dar lugar a mínimos locales !

    Monografias.com

    Algoritmos: Vecino más próximo.
    Coste:
    Examina 12 puntos
    369 MOP.
    MV: (-3,-4)
    Calcula el SAD del (0,0).
    Establece el origen de búsqueda a la posición del vector supuesto (predicted vector)
    Selecciona 4 posiciones alrededor del origen en forma de “+”.
    Si el origen de búsqueda (o la posición 0,0 en la primera iteración) ofrece el menor SAD entonces “fin de búsqueda”.
    Sino establece el nuevo origen de búsqueda en la posición que menor SAD ha ofrecido.
    (Gp:) (-7,-7)
    (Gp:) (0,-7)
    (Gp:) (7,-7)
    (Gp:) (-7,7)
    (Gp:) (0,7)
    (Gp:) (7,7)

    0
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1
    (Gp:) 1

    (Gp:) 2
    (Gp:) 2
    (Gp:) 2

    (Gp:) 3
    (Gp:) 3

    Propuesto para H.263 y MPEG-4.

    Monografias.com

    Estimación de movimiento: Otras consideraciones.
    Estimación de movimiento con fracciones de pixel
    Se basa en realizar la estimación de movimiento con mayor precisión, ya que a veces el movimiento real no se ajusta a desplazamientos de píxel enteros.
    Half-Pixel motion estimation
    Se obtiene un imagen de mayor resolución interpolando un punto de la imagen entre cada dos píxeles.

    (Gp:) A
    (Gp:) A
    (Gp:) A
    (Gp:) c
    (Gp:) b
    (Gp:) A
    (Gp:) A
    (Gp:) A
    (Gp:) A
    (Gp:) A
    (Gp:) A
    (Gp:) c
    (Gp:) c
    (Gp:) d
    (Gp:) b
    (Gp:) b
    (Gp:) b
    (Gp:) b
    (Gp:) b
    (Gp:) d
    (Gp:) c
    (Gp:) c
    (Gp:) c
    (Gp:) d
    (Gp:) d

    A: Píxeles reales (Enteros)
    b,c,d: Píxeles interpolados. Las flechas indican la dirección de interpolación.
    Se incrementan notablemente las prestaciones del algoritmo de estimación de movimiento a expensas de un mayor coste computacional.
    H.263 utiliza está técnica, incluso se propone utilizar ¼ y 1/8 de píxel para el estándar H.264

    Partes: 1, 2, 3

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter