View
155
Download
0
Category
Preview:
Citation preview
1
CODIFICACION LHE ULTRARRÁPIDA PARA CLOUD GAMING
Jose Javier García ArandaMarina Gonzalez Casquete
2
Agenda
0| Introducción
2| LHE básico3| LHE avanzado4| Video LHE5| Conclusiones y trabajo futuro
1| Estado del arte
Codificación LHE ultrarrápida para cloud gaming
0| Introducción: online gaming vs cloud gamingcloud gaming concept
23
4 5 6Video Encoding
network
Video Decoding
Game server 1
4
Huyes, pero no huyes realmente hasta 130ms +80ms =210ms después de que te disparasen
80ms
El disparo sale realmente 20 ms después
Te enteras de que te han disparado 40+80+10=130ms después de que lo han hecho
20ms 80ms + video decoding
40ms Video encoding
Cuanto Tiempo tienes para huir?
0| Introducción: problemática cloud gaming
5
Recursos Costes
0| Introducción: ¿merece la pena el progreso?
Demanda
Cloud gaming
6
0| Introducción: motivación
Problema no resuelto : latencia de codificación en “cloud gaming” limita el despegue comercial de estos servicios.
Retos:
El “time-memory” trade-off.
La mejora de la calidad.
El problema de las patentes que afecta a la difusión de los
algoritmos.
LHE: nuevo algoritmo de baja complejidad computacional (lineal) y sin patentes ,
con calidad superior a JPEG.
7
Agenda
2| LHE básico3| LHE avanzado4| Video LHE5| Conclusiones y trabajo futuro
Codificación LHE ultrarrápida para cloud gaming
0| Introducción1| Estado del arte
8
J. Cooley y J. W. Tukey, «An Algorithm for the Machine Calculation of Complex Fourier Series,»Mathematics of Computation, vol. 19, nº 90, p. 297–301, 1965.
JPEG 1986 -1994
JPEG 2000
H264 intra 2003
JPEGXR 2009
WebP ( VP8 intraframe) 2010
Mp3 (audio) 1993
MPEG1 Intraframe ( JPEG) 1992
MPEG2 Intraframe ( JPEG) 1994
H265 intraframe “HEVC” 2013
GIF 1987
1| Estado del arte: transform compressors
Transform compressors(dominan la compresión con
pérdidas)
Non- Transform compressors(dominan la compresión sin
pérdidas)G721 (ADPCM speech codec) 1984
Lossless JPEG (1993)
PNG 1996
JPEG- LS (2003)
…
…
vsFLAC (audio) 2000
9
Espacio-tiempo
Paralelización
Selección y diseño de algoritmos
Calidad del resultado
Típico diagrama R-D No muestra la complejidad, sólo el resultado
1| Estado del arte: complejidad
calidad
Bit-rate
criterios
10
JPEG
JPEG XR
JPEG 2000
PNGGIF WEBP
FRACTAL RNA
BMP LHE
H264 intra
tiempo
espacio
Usan algoritmos de diccionario
Usan DCT
Usa convolución
Usa RLE
Usan predicción espacial
Usa Ley de weber
Aun no viables
Usa DCT jerárquica
Sin pérdidas
Espacio: memoria RAM consumida durante la ejecuciónTiempo: tiempo consumido durante la ejecución
Esta gráfica muestra la complejidad computacional y no cuanto comprime cada formato ni cuanta calidad proporciona.
1| Estado del arte: algoritmos/formatos
11
0| Introducción
2| LHE básico3| LHE avanzado4| Video LHE5| Conclusiones y trabajo futuro
1| Estado del arte
AgendaCodificación LHE ultrarrápida para cloud gaming
12
Basado en modelado del ojo humano
•La respuesta logarítmica al estímulo luminoso (ley de Weber)
•El umbral mínimo de contraste lumínico para detectar cambios
•El proceso de acomodación del ojo al brillo medio local
2| LHE básico
Diagrama de bloques del compresor LHE básico
13
2| LHE básico: respuesta logarítmica al estímulo luminoso
(Información sensorial)
Modelado de la respuesta logarítmica del ojo humano
(Información perceptuall)
14
2| LHE básico: respuesta logarítmica al estímulo luminoso
15
2| LHE básico: umbral de detección h1
Fracción de Weber:
penumbra deslumbramiento
16
Los valores que se alejan del brillo medio “local” se interpretan con menos precisión, ya sea por exceso (izquierda) o por defecto (derecha)
2| LHE básico: acomodación al brillo medio local
h1 min=4
h1 max
Zona lisa o suaveborde
X
Rango de variación de h1
Acomodación del ojo al brillo medio
17
¿Cuántos hops diferentes usar?
2| LHE básico: número de hops
Ejemplo de asignación de hops y reconstrucción realizada por LHE
18
Por último se calculan códigos binarios de longitud variable mediante Huffman estático
hop SímboloRedundancia espacial
Huffman estático Código binario
2| LHE básico: codificador entrópico
Hop Orden de comprobación
h0 1Up 2h1 3h-1 4h2 5h-2 6h3 7h-3 8h4 9h-4 10
Símbolo: número de comprobaciones [1..9]Distribución estadística de hops
19
2| LHE básico: resultados
•Estrictamente lineal O(N)•Bit-rate no elegible
20
3| LHE básico: modelo de color
Aplicación de YUV a LHE: • Métricas sólo sobre Y ( U, V no consumen estos cálculos)
• Sub-muestreado de U,V más intenso que Y
Modelos de color: CIE, RGB, HSB, CMYK, YUVYUV: es el modelo de los “lossy compresors” (JPEG, JP2K, h264 intra, webp…)
YUV prioriza la resolución vertical porque el ojo posee mas sensibilidad vertical que horizontal
21
6| LHE básico: validación modelo de color
22
6| LHE básico: validación modelo de color
23
0| Introducción
2| LHE básico3| LHE avanzado4 | Video LHE5 | Conclusiones y trabajo futuro
1| Estado del arte
AgendaCodificación LHE ultrarrápida para cloud gaming
LHE avanzado está basado en:• LHE básico
• Métrica de relevancia perceptual (PR)
• Downsampling elástico
Necesidad: El LHE básico ofrece un solo ratio de compresión, que además no podemos elegir
3| LHE avanzado
1st LHE
PR metric
Elastic Downsampling
2nd LHE
From Hops to signal
Elastic Interpolation
Encoder Decoder
25
Sub-muestreado elástico
cada bloque de la imagen es sub-muestreado con diferente intensidad
Dentro de un bloque la cadencia de muestras es variable entre sus 4 esquinas
3| LHE avanzado
26
3| LHE avanzado: PPP (Pixels Per Pixel)
27
3| LHE avanzado: Relevancia Perceptual
muestra
Muestra Interpolable
Distintas percepciones en fragmentos de una imagen Interpolabilidad de la señal
Información sensorial y perceptual
28
Al ser una media, esta métrica es independiente de la resolución.
Menos relevante Más relevante
3| LHE avanzado: Relevancia Perceptual
Relevancia es independiente del número de bordes
29
3| LHE avanzado: Relevancia PerceptualMétricas de PR en los vértices de la malla
30
Malla de bloques sin tamaño fijo: numero de bloques constante (sin precedentes)La información de malla es la misma en SD, HD o UHD
Malla de bloques sin tamaño fijo
3| LHE avanzado: malla
24 + 44 imágenes
Diferentes resultados con kodim21 usando diferente número de bloques en la malla
Umbral de saturaciónPR=0.5
31
3| LHE avanzado: Saturación de PR
Igual número de muestras
Nuestros sentidos se llegan a saturar
Histograma de valores de la métrica de PRx y PRy para dos imágenes diferentes
Resultados sin topar y topando la PR en 0.5. Ambas imágenes igualmente reducidas al 10%
32
3| LHE avanzado: expansión de PR
Expansión del histograma de PR antes de cuantizar
33
3| LHE avanzado: traducción de PR’ a PPP
Máxima compresión
1st LHE
PR metric
Elastic Downsampling
2nd LHE
From Hops to signal
Elastic Interpolation
Encoder Decoder
hops PPP luminancias hops luminancias
luminancias
34Dos imágenes con el mismo valor de QL tendrán la misma “calidad equivalente”
3| LHE avanzado: traducción de PR’ a PPP
Un valor de QL define una “calidad equivalente”Una misma Relevancia perceptual (PR) se transforma en los mismos PPP
23,8dB 16,4dB
Dos imágenes con igual nivel de calidad (QL) y distinto PSNR y tasa de bit
Nivel de calidad (“QL” o “Quality Level”) y reformulación de PPP
35
Restricción rectangularEl resultado debe ser un rectángulo para poder ser traducido a hops
3| LHE avanzado: traducción de PR’ a PPP
Ajuste de gradiente de PPPLos lados deben tener un numero entero de pixels
36
Separabilidad3| LHE avanzado: Downsampling Elástico
Downsampling Elástico separable
Media o mediana
37
3| LHE avanzado: Downsampling Elástico
38
3| LHE avanzado: Downsampling Elástico
39
3| LHE avanzado: Downsampling ElásticoComparación de Downsampling Elástico vs Downsampling homogéneo
40
3| LHE avanzado: segundo LHE
Píxels frontera necesarios para estimar el color de fondo
Interpolar es adaptar longitud pero también adaptar los PPP
41
3| LHE avanzado: paralelización del segundo LHE
16 veces (63 pasos frente a 1024)
Incremento de velocidad ( lado =32 bloques)
bloque
sin usar fronteras, se pueden paralelizar todos los bloques 1024 veces
Usando fronteras
N : número de bloques de lado
42
3| LHE avanzado: codificadores entrópicos
Las dos etapas del codificador binario de hops
43
3| LHE avanzado: complejidad y paralelización
1st LHE
PR metric
Elastic Downsampling
2nd LHE
From Hops to signal
Elastic Interpolation
Encoder
Decoder
hops PPP luminancias hops luminancias
luminancias
Todos los bloques son paralelizables al 100% incluido el segundo LHE, el cual gana algo de calidad si se paraleliza de forma limitada
O(N/4) O(1) O(N) O(N’)
44
3| LHE avanzado: decodificador
Recuperación de la Señal
no solo son de diferente tamaño sino que tienen diferente PPP
45
3| LHE avanzado: decodificador
Interpolación
Nuestra Interpolación debe ser “elástica”
46
Interpolación por vecino cercano (separable)3| LHE avanzado: decodificador
• El brillo de cada pixel sub-muestreado se traslada a todos los pixels finales que cubre.
• Los pixels cubiertos parcialmente se calculan mezclando.
Interpolación de un bloque por vecino cercano
47
Interpolación bilineal Pixeles parcialmente cubiertos. Dos opciones:• Pintar si se recubre mas del x% ( óptimo con 25%)• Interpolar su luminancia
3| LHE avanzado: decodificador
Área pintada por una interpolación bilineal Estrategia de interpolación con píxels ya interpolados
Resultado de la interpolación
48
Interpolación bilineal de costuras
3| LHE avanzado: decodificador
Interpolación horizontal de costuras
Interpolación de costuras
49
3| LHE avanzado: resultados
24 imágenes
44 imágenes
50
3| LHE avanzado: resultados
El mayor beneficio es computacional
51
3| LHE avanzado: resultados
Diagrama de distorsión PSNR para la imagen “Lena”
52
3| LHE avanzado: resultados
53
3| LHE avanzado: resultados
54
Lena @ 0.1bpp JPEG, LHE, JP2K
3| LHE avanzado: resultados
55
No hay efecto de bloques en LHE porque los bloques comparten los PPP en las esquinas y no hay saltos de resolución
No hace falta deblocking filter como se hace en h264 intraframe
JPEG y LHE a 0.3bpp3| LHE avanzado: resultados
hay efecto de bloques en JPEGporque hay saltos de cuantización de las componentes de las distintas frecuencias entre bloques
56
0| Introducción
2| LHE básico3| LHE avanzado4| Video LHE5| Conclusiones y trabajo futuro
1| Estado del arte
AgendaCodificación LHE ultrarrápida para cloud gaming
4| Video LHE
1st LHE
New frame(Y2)
PR metric
Elastic Downsampling
DifferentialFrame info
2nd LHE
Δy
Interpol (Y1’’)
Vector computation
Y2’Δy= y2’- interp(y1’’)
Y2’’
Y1’’
{wi}
Bloque de Frame Y2
Bloque de Frame Y1
Antes de calcular la info diferencial debemos adaptar resoluciones con una interpolación por vecino (sin coste)
Δy= y2’- interp(y1’)
Yi’: submuestreada sin cuantizarYi’’: submuestreada cuantizada
58
4| Video LHE: error de cuantización
Fracción de weber
Valor de la función dy
La función inversa de dy
59Cuanto mas se saca partido de los vectores, mas se aleja h264
4| Video: resultados
Una efecto general observable y mejorable son los bordes difuminados de LHE, sobre todo a bajos bit-rates, debidos a los algoritmos de downsampling e interpolación utilizados. Es esperable que con el uso de la mediana en downsampling y algoritmos “pixel-art” en interpolación se puedan conseguir bordes bien definidos a cualquier ratio de compresión
Otra característica interesante es el paralelismo de la tendencia de la curva de distorsión PSNR entre h264 y LHE. Son paralelas, lo cual es prometedor. Esto no siempre ocurre entre diferentes algoritmos, como es el caso de las curvas de PSNR de JPEG y JPEG2000
15 Videos licencia creative commons
60
football LHE @ 1000kbps football h264 @ 1000kbps
H264 fast: solo frames P
H264 normal: P y B
4| Video: resultados
61
Soccer LHE @ 930kbps Soccer h264 @ 930kbps
H264 fast: solo frames P
H264 normal: P y B
4| Video: resultados
62
0| Introducción
2| LHE básico3| LHE avanzado4| Video LHE5| Conclusiones y trabajo futuro
1| Estado del arte
AgendaCodificación LHE ultrarrápida para cloud gaming
63
Conclusiones:• Es posible comprimir en el dominio del espacio reduciendo la complejidad algorítmica,
mediante un modelado fisiológico del ojo• La información sensorial es equiparable a hops logarítmicos, siendo 9 el número óptimo• LHE permite aplicar el modelo de color YUV• La relevancia perceptual se puede medir mediante el análisis de los hops de un modo
independiente de la resolución de la imagen• Es posible traducir analíticamente la métrica de PR a valores de PPP que permitan un sub-
muestreado elástico, permitiendo así que la métrica sea el criterio de asignación de PPP.• El sub-muestreado elástico es superior en calidad al sub-muestreado convencional• El sub-muestreado elástico funciona de forma óptima con un número fijo (malla) de bloques • La calidad de dos imágenes puede ser considerada equivalente cuando los mismos valores de
relevancia perceptual son traducidos a los mismos PPP (parámetro “QL” de LHE)• LHE permite aplicar el modelo de color YUV• LHE no presenta efecto de bloques aunque procese la imagen dividiéndola en bloques debido
a que los bloques comparten valores similares de PPP en sus esquinas• LHE produce bordes difuminados a bajos bit-rates• LHE permite compresiones de hasta 0.05 bpp• LHE es apto para comprimir información diferencial temporal , base del codificador de video.• La compresión de video LHE (sin compensación de movimiento) genera diagramas de
distorsión paralelos a H264 y muy cercanos a h264 sin frames B
5| Conclusiones y trabajo futuro
LHELHE BASICO LHE AVANZADO VIDEO LHE
64
Diseminación (artículos)Revista: IET Image Processing. Titulo “Logarithmical hopping encoding: a low computational complexity algorithm for image compression”.Autores: J. J. Garcia Aranda, M. Gonzalez, M. Cao, J. Navarro y F. Gonzalez.Accepted on 10th December 2014Published: Volume 9, Issue 8, August 2015, p. 643 – 651DOI: 10.1049/iet-ipr.2014.0421 , Print ISSN 1751-9659, Online ISSN 1751-9667http://digital-library.theiet.org/content/journals/10.1049/iet-ipr.2014.0421
Revista: IET Image Processing. Titulo “Logarithmical Hopping Encoding: physiological fundamentals”.Autores: J. J. Garcia Aranda, M. Gonzalez, M. Cao, J. Navarro y F. Gonzalez.Submited on 29 August 2015
Published
Submitted
5| Conclusiones y trabajo futuro
65
Diseminación (conferencias)2014 Universidad de Valladolid. Master universitario de investigación en TIC. marzo de
2014Titulo: “LHE: una nueva tecnología de codificación de imagen y video”
2013 Evento “GameMe5” organizado por HTML5 Spain , Diciembre 2013 (lugar campus UPM Vallecas). titulo :”LHE: una nueva tecnología de codificación para cloud gaming”
2013 UPM , Escuela superior de telecomunicación, Octubre 2013.Máster Universitario en Ingeniería de Redes y Servicios Telemáticos Programa de Doctorado en Ingeniería de Sistemas TelemáticosTitulo :” Codificación logarítmica: calidad wavelet a precio de DPCM”http://www.dit.upm.es/~doct/SI/2013-2014/2013-10-22-LHE_v003.pdf
5| Conclusiones y trabajo futuro
66
“VIRTUOSE” programa CELTIC, 2015 (ganado sello condicional)Convocatorias a proyectos futuros presentados con tecnología LHE
Las ideas y contribuciones de esta tesis han sido de gran utilidad en el desarrollo del proyecto de investigación “VideoXperience: Mejora Efectiva de la Experiencia de Usuario en la Nueva Era de Servicios Digitales mediante la Provisión de nuevas Tecnologías de Supercompresión en Streaming”. Este proyecto forma parte del subprograma INNPACTO del Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica 2008-2011, y está financiado por el Ministerio de Ciencia e Innovación, actual Ministerio de Economía y Competitividad
Proyectos de I+D realizados con tecnología LHE
Proyectos en curso de I+D con tecnología LHE“VINTAGE” convocatoria MINETUR-RETOS 2015“ARQUEOPTERIX”. Convocatoria CDTI- CIEN 2015 (7 empresas, 4 OPIs)
5| Conclusiones y trabajo futuro
67
• Mejora de velocidad en el primer LHE: mediante un sub-muestreo por SPS. HD y UHD • Mejora de la predicción en el segundo LHE usando las metricas PR: al estilo PNG•Capacidad de transparencias: • Compresión sin pérdidas: capas de hops• Mejora de la interpolación: con algoritmos pixel art basados en XBR• Compensación de movimiento basada en evolución de la métrica de Relevancia Perceptual • Difusión: impulsar el algoritmo en organismos de estandarización como W3C• Audio LHE
5| Conclusiones y trabajo futuro
• Proyecto Github https://github.com/magonzalezc/LHE branch: lhe_develop• Articulo IET image processing Journal: http://digital-library.theiet.org/content/journals/10.1049/iet-ipr.2014.0421
5| Conclusiones y trabajo futuro
Enlaces de interés
Recommended