- Rational Bloom Filter Video Compression implementa un flujo de trabajo sin pérdida que comprime video sin procesar y exige que el resultado restaurado sea idéntico al original bit a bit
- La clave es una estructura que aplica una cantidad no entera de funciones hash al filtro de Bloom, con el objetivo teórico de lograr una mejor tasa de compresión que los métodos existentes
- Está orientado a raw video content como Y4M, YUV y HDR, y afirma ofrecer un ahorro de espacio del 40 al 50% en videos comunes
- La implementación está basada en Python 3.7+ y requiere dependencias como
numpy, opencv-python, xxhash, Pillow, scikit-image y pyexr para HDR
- Incluye benchmarks comparativos con FFV1, HuffYUV y el modo sin pérdida de H.264, por lo que antes de usarlo en la práctica el flujo es revisar los resultados y el procedimiento de reproducción en
results.md
Descripción general de Rational Bloom Filter Video Compression
- Este proyecto implementa un método de compresión de video sin pérdida basado en rational Bloom filter
- El filtro de Bloom se usa como una estructura de datos probabilística para representar datos binarios de forma eficiente
- Su diferencia es que usa una rational hash function no entera en el filtro de Bloom
- El objetivo es que el resultado restaurado tras la compresión coincida con el original de forma bit-exact
Soporte y funciones de compresión
- El sistema de compresión está orientado a raw video content como Y4M, YUV y HDR
- Las funciones que ofrece son las siguientes
- true lossless compression, que garantiza una restauración idéntica bit a bit
- Ahorro de espacio del 40 al 50% en contenido de video común
- Codificación y decodificación con soporte multihilo
- Soporte para varios color space, como RGB, BGR y YUV
- Soporte para procesar contenido HDR
- El procesamiento HDR tiene la limitación de que “hace falta más trabajo para que sea rápido y utilizable”
Requisitos de instalación
- El entorno de ejecución es Python 3.7+
- Los paquetes necesarios son los siguientes
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr: para soporte HDR
- Las dependencias se instalan con el siguiente comando
pip install -r requirements.txt
Uso básico
- En código Python, se importa
ImprovedVideoCompressor y se inicializa el compresor
- La configuración de ejemplo incluye
noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True y verbose=True
compress_video() comprime el video de entrada en un archivo .bfvcdecompress_video() restaura el archivo .bfvc- Con
verify_lossless() se verifica si los frames originales y los restaurados son sin pérdida
from improved_video_compressor import ImprovedVideoCompressor
compressor = ImprovedVideoCompressor(
noise_tolerance=10.0,
keyframe_interval=30,
use_direct_yuv=True,
verbose=True
)
compressor.compress_video(
input_file="input_video.y4m",
output_file="compressed.bfvc"
)
compressor.decompress_video(
input_file="compressed.bfvc",
output_file="decompressed.mp4"
)
original_frames = compressor.extract_frames_from_video("input_video.y4m")
decompressed_frames = compressor.decompress_video("compressed.bfvc")
verification = compressor.verify_lossless(original_frames, decompressed_frames)
print(f"Lossless: {verification['lossless']}")
Uso desde la línea de comandos
- La compresión de video se ejecuta así
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
- Los archivos raw YUV se procesan especificando también ancho, alto y formato
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444
Benchmarks y comparaciones
- El proyecto incluye un sistema de benchmarks que compara la compresión Rational Bloom Filter con otros métodos de compresión sin pérdida
- Los métodos de comparación son FFV1, HuffYUV y el modo sin pérdida de H.264
- El comando para ejecutar el benchmark completo es el siguiente
python benchmark_compression.py
- También se puede ejecutar especificando solo ciertos datasets y métodos
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
- Los resultados detallados del benchmark y el método de reproducción están en results.md
Flujo de funcionamiento del método de compresión
- El esquema de compresión funciona con los siguientes pasos
- Frame Extraction: extrae frames del video de entrada
- Keyframe Selection: guarda los keyframes como frames comprimidos directamente con zlib
- Bloom Filter Compression: comprime los interframes como mapas de diferencias mediante rational Bloom filter
- Lossless Verification: verifica durante la decodificación la restauración bit-exact
- El rational Bloom filter usa una cantidad no entera de funciones hash
k* para optimizar el equilibrio entre espacio y precisión
- La implementación usa de forma determinista
⌊k*⌋ funciones hash y aplica una función hash adicional con probabilidad k* - ⌊k*⌋
Estructura de archivos del proyecto
improved_video_compressor.py: main implementation del algoritmo de compresiónverify_true_lossless.py: script que verifica la restauración sin pérdidabenchmark_compression.py: sistema de benchmarks que compara varios métodos de compresióndownload_*.py: scripts para descargar datasets de pruebaresults.md: resultados detallados y análisis de los benchmarks
Licencia y cita
- La licencia es MIT License y los detalles se pueden consultar en el archivo
LICENSE
- Si se usa el código en una investigación, se indica usar la cita en formato BibTeX incluida en el README
1 comentarios
Opiniones en Hacker News
Siento que el documento no explica bien una idea bastante simple. Si entendí correctamente, primero se crea un mapa de bits en el que cada bit se ve como un píxel de la imagen, y al pasar del frame 0 al frame 1 se pone 1 si el píxel cambió, o 0 si no
Luego se hashean los offsets de las posiciones que valen 1 y se meten en un Bloom filter. Así, esos índices y cierto porcentaje de índices falsos positivos salen como positivos
Después se consulta el Bloom filter para encontrar todos los índices positivos y, para esos píxeles, se guardan los datos de píxel sin procesar que cambiaron; así se puede reconstruir fácilmente el siguiente frame
Se puede ver como guardar el delta entre dos frames con x,y,r,g,b de todos los píxeles que cambiaron, pero comprimiendo mucho la parte x,y y guardando un poco más de r,g,b de lo necesario
Como las ubicaciones de los píxeles que cambiaron del frame 0→1 suelen parecerse a las ubicaciones que cambiarán del frame 1→2, parece que habría margen para comprimir más si en el siguiente frame se activa un flag adecuado y se guardan tal cual solo los offsets adicionales que difieren respecto de antes
La transformada inversa empieza con una imagen pequeña de píxeles y la convierte en una imagen con el doble de ancho o alto usando la misma cantidad de coeficientes, y repite eso
La clave es que la mayor parte de los datos son coeficientes, y la mayoría están cerca de 0, así que se pueden empujar a 0. Entonces el problema pasa a ser cómo codificar las posiciones que no son 0, y se obtiene una estructura como un mapa de bits y un arreglo de valores no nulos
Los algoritmos para codificar valores no nulos variaban en qué tan conservadores eran, pero en general aprovechaban la propiedad de que esos valores suelen estar bastante agrupados. Eso es exactamente lo contrario de las funciones hash típicas que se usan en un Bloom filter
Este tipo de compresión de imágenes era lenta porque tenía muy mala localidad, tanto en la propia transformada como en la compresión de coeficientes, así que se sentía como un callejón sin salida
Creo que un Bloom filter podría usarse como parte de una estrategia híbrida de compresión compleja. En un compresor así, mientras más herramientas haya, mejor, pero en promedio no parece que vaya a mejorar mucho
Parece funcionar mejor porque el video de entrada ya es un video comprimido y luego reconstruido desde YouTube
Si la entrada fuera el video original, probablemente se rompería la suposición de que “entre frames consecutivos la mayoría de los píxeles cambia poco o nada, generando una matriz de diferencias dispersa”
Con una señal muy limpia, por ejemplo un sensor de bajo ruido y una escena bien iluminada, podría ser posible, pero en la mayoría de las señales reales el ruido es mayor que 1 LSB, así que esperaría que al menos la mitad de los bits inferiores cambien
Si se hace que el video pase una vez por el proceso de compresión y reconstrucción, ese ruido tiende a eliminarse, creando un video artificialmente estático en el que esa suposición sí se cumple
Parece que no guarda la diferencia para píxeles cuyo cambio promedio en r,g,b es menor que 10. Entonces, aunque un píxel cambie de azul puro (#00ff00) a rojo puro (#ff0000) en frames consecutivos, ambos frames podrían reconstruirse como azul puro
El video sin pérdida encaja mucho mejor con contenido digital como grabaciones de pantalla. La suposición de que pocos píxeles cambian entre frames consecutivos también es más válida ahí
A menos que alguien lo active explícitamente y acepte el tamaño de archivo y la carga de procesamiento, puede que ni siquiera sepa que todavía existe el concepto de datos originales o sin procesar
Nunca lo había pensado así antes
O comprar una cámara y grabar personalmente video 8K original de escenas cotidianas
Según el gráfico [1], ¿este nuevo método de compresión no es siempre estrictamente peor que usar simplemente GZIP?
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
“Idea clave: si la densidad de 1 en una cadena binaria es baja, especialmente si está por debajo de p* ≈ 0.32453, es más eficiente codificar solo las posiciones de los 1 que almacenar la cadena original.”
Gran parte de lo que hacen JPEG/MPEG es reorganizar el problema para poder crear largas secuencias de 0. La forma en que se escanean los bloques DCT según la posición de los componentes AC/DC podría ser una de las partes más innovadoras en varias técnicas de compresión de video e imagen
Dicho de una mejor manera, esta técnica no tiene nada específico para cuadros de video. La misma idea podría usarse para comprimir la diferencia entre dos secuencias de bits de la misma longitud.
Aun así, es poco probable que este problema sea mejor que los métodos de compresión existentes, por ejemplo concatenar dos bloques y aplicarles gzip. Para que haya compresión, la distribución de entrada —en este caso, el conjunto de distintas posiciones de bits— debe ser muy predecible y no aleatoria, pero al pasar los datos por una función hash se rompe esa propiedad. En especial, el objetivo de un hash criptográficamente fuerte es hacer que la salida sea indistinguible de lo aleatorio
Lo que hacen DCT y la conversión de representación de color es convertir los detalles finos en altas frecuencias, y los detalles principales en bajas frecuencias. Luego, la calidad de imagen y la tasa de compresión se simplifican a cuánto se descarta de la representación de alta frecuencia.
Además de eso, JPEG usa tablas Huffman para reducir aún más el tamaño de la imagen.
Hasta donde sé, no hace nada especial para reducir largas secuencias de 0. Por eso alinear los 0 en una fila no ayuda demasiado
Esta línea me confunde: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
Con esto, la compresión se vuelve con pérdida, y por ejemplo parecería descartar una transición de #ffffff a #fffffa. La línea justo anterior, donde se promedian los datos de píxeles, también parecería descartar una transición de #ff0000 a #00ff00 independientemente del umbral.
No sé si estoy entendiendo mal el papel de esa línea de código. Lo que queda en 0 en la máscara resultante parece no codificarse en el Bloom filter
Está escrito cómo se calcula la tasa de compresión, pero me pregunto si también hay ejemplos de tasa de compresión en el peor caso, promedio y mejor caso.
Edit: vi que hay una imagen en el repositorio. Sería útil ponerla en el README
Planeo hacerlo mucho más concreto con bastantes pruebas adecuadas. Por ahora se parece más a un trabajo en curso bastante desordenado
Soy el autor. Recibí muchos buenos comentarios, así que por un tiempo decidí concentrarme en pruebas más rigurosas con video original y videos con ruido. Voy a seguir actualizando el repositorio con frecuencia.
Todavía está en una etapa muy temprana, pero en pruebas con video original obtuvo resultados bastante buenos, con algunas pistas: tasa de compresión de 4.8%, es decir, reducción de tamaño de 95.2%, velocidad de compresión de 8.29fps, velocidad de descompresión de 9.16fps, solo se necesitan keyframes para el 4% de los cuadros, y una salida perceptualmente sin pérdida (PSNR 31.10dB).
Comparado con códecs estándar: Rational Bloom Filter 4.8%, JPEG2000 sin pérdida 3.7%, FFV1 sin pérdida 36.5%, H.265/HEVC con pérdida 9.2%, H.264 con pérdida 0.3%.
También hay limitaciones actuales y trabajo futuro. Aunque los resultados de compresión son prometedores, el procesamiento de canales de color todavía no es verdaderamente sin pérdida. La implementación actual tiene dificultades en la conversión de espacio de color de YUV a BGR, y debido a la precisión de la conversión de espacio de color se generan pequeños errores de redondeo, dejando una diferencia promedio de alrededor de 4.7 en los valores de píxel.
Además, la implementación actual procesa los canales de color en formato BGR después de la conversión, lo que provoca pérdida adicional de precisión.
De aquí en adelante planeo procesar YUV directamente sin conversión a BGR, tratar los datos de color con exactitud a nivel de bits, ajustar los parámetros del Bloom filter según los patrones de submuestreo de croma y crear un sistema dedicado que verifique cada canal de color de forma independiente.
Quiero demostrar matemáticamente que es sin pérdida, pero todavía falta mucho. Planeo seguir investigando esta idea de compresión sin pérdida, y también tengo algunas ideas para usar Rational Bloom Filter en otras áreas
Códecs como H.264 también pueden ejecutarse en un modo verdaderamente sin pérdida. Solo que casi nadie los usa así
Es un concepto simpático, pero si tienes una cadena binaria dispersa, es muy probable que puedas hacerlo mejor con métodos tradicionales
Es difícil seguir el repositorio, pero parece que la tasa de compresión se calcula viendo cuántas diferencias de píxeles se pudieron descartar.
Es interesante, pero la comparación más importante sería el tamaño promedio en bytes de cada cuadro en un video comprimido de YouTube. Sin esa comparación, es difícil juzgar si mejora los métodos actuales.
Si el algoritmo es con pérdida, es decir, si aplasta a 0 las diferencias pequeñas, entonces no es sin pérdida y creo que habría que compararlo con otros algoritmos con pérdida