Compresión de video sin pérdida usando filtros Bloom
(github.com/ross39)- Este proyecto de código abierto logra compresión de video sin pérdida usando filtros Bloom
- Introduce el concepto de Rational Bloom Filter para superar las limitaciones de los filtros Bloom existentes y explorar una compresión eficiente
- A diferencia de los códecs comunes, garantiza compresión sin pérdida que restaura perfectamente todos los datos
- En vez de procesar el fotograma completo, se enfoca en las diferencias entre fotogramas para comprimir datos dispersos de manera eficiente
- Los resultados experimentales, los procedimientos de validación y la explicación de los principios le dan un alto nivel de confiabilidad
Resumen del proyecto
Este proyecto de código abierto intenta lograr compresión de video sin pérdida mediante una transformación innovadora del filtro Bloom (una estructura de datos que permite verificar de forma rápida y eficiente si un valor pertenece a un conjunto). Los códecs de video tradicionales como H.264 aumentan la tasa de compresión eliminando información invisible para el ojo humano, pero este método sacrifica la integridad de la información. Este proyecto demuestra una forma de reducir el tamaño de archivo manteniendo la restauración perfecta de los datos. En particular, el uso de una cantidad racional (no entera) de funciones hash en el filtro Bloom y la estructura de compresión basada en Δ entre fotogramas son sus principales rasgos técnicos.
Guía del código fuente principal
- Archivo principal: youtube_bloom_compress.py
- Es posible ejecutar una demo con solo unos cuantos comandos simples
- Todavía hay limitaciones de velocidad con videos largos, y la optimización sigue en curso
Fundamentos del filtro Bloom
Un filtro Bloom usa varias funciones hash y requiere muy poca memoria para comprobar si un valor está en un conjunto. Aunque permite algunos falsos positivos (false positive), nunca produce falsos negativos (false negative), lo que le da una gran ventaja en confiabilidad.
Cambio innovador: Rational Bloom Filter
La cantidad óptima de funciones hash (k) en un filtro Bloom normalmente no es un entero. Por eso, el Rational Bloom Filter aprovecha un k* real:
- Siempre aplica ⌊k*⌋ funciones hash
- Aplica de forma probabilística una función hash adicional según la fracción restante (por ejemplo, si k* = 2.7, usa la tercera función hash con 70% de probabilidad)
- Está diseñado para que esta decisión probabilística se tome de forma consistente para cada elemento
Este método funciona correctamente tanto en la compresión como en la restauración, lo que aumenta la confiabilidad de la compresión.
Expansión del filtro Bloom hacia un compresor
La idea central es que, en cadenas binarias donde los 1 son poco frecuentes (dispersas), si se guarda solo la posición de los 1, es posible registrar los datos usando menos espacio que con el conjunto completo de bits original.
- Etapa de compresión:
- Se indican las posiciones de los 1 en el mapa de bits del filtro Bloom
- Además del filtro Bloom, se almacenan por separado los valores de bits realmente necesarios (datos testigo)
- El análisis teórico muestra que hay ganancia de compresión cuando la proporción de 1 es menor que 0.32453
Fórmulas clave y optimización
- Se presentan fórmulas para k (cantidad de funciones hash) y l (tamaño del mapa de bits) según la dispersión
- Es posible calcular automáticamente los parámetros óptimos con base en la distribución de bits de los datos de entrada
Cómo se aplica a la compresión de video
- Extrae solo los cambios entre fotogramas (valores Δ), convirtiéndolos en una matriz dispersa donde la mayoría de los valores no cambian
- Aplica la técnica de compresión con filtro Bloom a esta matriz dispersa de diferencias
- Mejora de forma importante la eficiencia de almacenamiento frente a guardar fotogramas completos
Procedimiento de validación de compresión y restauración
- Calcula el tamaño de todos los elementos necesarios para la restauración, incluyendo mapa de bits comprimido, datos testigo, metadatos y píxeles modificados
- Tras restaurar por fotograma, verifica si coincide con el original bit por bit
- Realiza visualización y cuantificación de diferencias por fotograma, además de una validación completa de todo el pipeline
- El cálculo de la tasa de compresión está descrito claramente en el código, por lo que cualquiera puede reproducirlo y verificarlo
Estructura de compresión completamente autosuficiente
- No requiere diccionario externo ni tabla de consulta para la restauración
- Conserva dentro del archivo comprimido todos los parámetros del filtro Bloom y la información de color
- Es posible una restauración perfecta usando solo el archivo comprimido
Conclusión y guía de código abierto
Este proyecto aprovecha al máximo la dispersión de los datos mediante filtros Bloom, y es ideal para tareas que requieren restauración perfecta, como datos científicos o imágenes médicas. También permite experimentar directamente con esta nueva estructura algorítmica y su sistema de validación, y dejar sugerencias de mejora.
1 comentarios
Opiniones de Hacker News
Siento que este documento en realidad explica de forma complicada una idea bastante simple
Este método es parecido a guardar la diferencia entre dos frames como x, y, r, g, b, pero en vez de eso comprime muchísimo las coordenadas x, y y guarda un poco más de r, g, b
Como normalmente las posiciones de los píxeles que cambian son parecidas entre frames, parece que en el siguiente frame podría comprimirse aún más si solo se marcan bien esas posiciones y se guardan adicionalmente los nuevos offsets que cambiaron
Justo por comentarios tan claros como este siempre leo primero los comentarios
Y ahora veo que además el autor es quien hizo kilo, muy genial
[edit] Hasta la forma en que edita se siente curiosamente divertida
Me da curiosidad qué tasa de compresión real consigue
Hace tiempo experimenté con compresión de imágenes basada en wavelets
La transformada inversa parte de una imagen pequeña y la va duplicando gradualmente usando coeficientes
La mayor parte de los datos son coeficientes casi en 0, y se comprimen eliminándolos como 0
La clave es codificar eficientemente dónde están las partes distintas de 0, y normalmente esos valores están agrupados, así que muchos algoritmos aprovechan esa característica
Eso muestra propiedades totalmente opuestas a las de las funciones hash usadas en un Bloom filter
Recuerdo que este enfoque terminó topándose con límites porque tanto la transformada como la compresión de coeficientes tenían poca relación espacial y eran lentas
Me pregunto en qué es más ventajoso un Bloom filter frente a una tabla hash
Gran parte de la compresión de video trata sobre el “movimiento”
Tengo curiosidad por cómo maneja el caso de un paneo de cámara, donde el mismo píxel se desplaza 2 píxeles hacia la izquierda
Si solo se guardan los cambios delta entre frames, entonces todos los píxeles que no cambiaron son 0
Comprimir secuencias continuas de 0 es de lo más fácil en compresión con pérdida, pero el enfoque con Bloom filter tiene falsos positivos
Un Bloom filter podría servir como una estrategia subordinada dentro de un compresor más complejo, y mezclar varios métodos seguramente sería mejor, pero en promedio no parece que vaya a mejorar mucho el rendimiento frente a los métodos existentes
Creo que hay una razón por la que este método funciona bien en videos como los de YouTube, que ya fueron comprimidos y luego descomprimidos una vez
En una entrada raw, puede romperse la suposición de que la mayoría de los píxeles casi no cambian entre frames consecutivos
En una escena totalmente limpia, con poco ruido y bien iluminada, podría funcionar, pero las señales normales tienen mucho ruido de más de 1 LSB, así que los bits bajos probablemente cambien seguido
Después de pasar por compresión y descompresión, el ruido disminuye y esa suposición vuelve a cumplirse
En la práctica, este método tampoco es lossless
En el código de video_delta_compress.py, si el cambio promedio en r,g,b es menor que 10, no guarda el cambio
Por ejemplo, incluso si cambia de pure blue(#00ff00) a pure red(#ff0000), se procesaría así, provocando que ambos frames se reconstruyan como pure blue
Así como no se usa PNG para tomar fotos, tampoco suelen usarse códecs lossless para video capturado en campo
El video lossless encaja más con contenido digital como grabaciones de pantalla
En esos casos aparecen pocos píxeles cambiantes entre frames, así que la suposición de este método sí encaja bien
En el código, si la proporción es menor a 32.4%, usa una estrategia de guardar solo las posiciones de los bits en 1
Incluso si los bits bajos cambian con frecuencia, ¿no podría seguir funcionando este enfoque siempre que los bits altos cambien lo suficiente poco?
En general, casi nadie usa video raw
Los teléfonos y cámaras también guardan por defecto en MP4, AV1, etc.
Considerando el tamaño de archivo y la carga de procesamiento, mucha gente ni siquiera sabe que existen formatos raw sin procesar
Por eso, tal como está ahora, este método parece apropiado para animación
Según la gráfica relacionada compression_comparison.png, ¿esto significa que el nuevo método de compresión siempre rinde peor que GZIP?
Aun así, no encontré métricas de rendimiento
Se menciona la idea clave del texto: “una cadena binaria con suficiente baja densidad de 1 puede comprimirse de forma más eficiente que los datos originales guardando solo la posición de los 1”
JPEG, MPEG y otros reorganizan el problema precisamente para que aparezcan largas secuencias de 0, y el método de escaneo de bloques DCT fue muy innovador para este tipo de compresión de video
La DCT y la conversión de color convierten los detalles finos en alta frecuencia y el contenido principal en baja frecuencia
La compresión consiste en descartar sobre todo los componentes de alta frecuencia
JPEG también optimiza el tamaño con una tabla Huffman
En realidad no se usan mucho técnicas especiales para juntar 0, y el hecho de que se agrupen no mejora tanto la eficiencia de compresión
De acuerdo
El mayor problema del enfoque del OP es que descarta activamente la correlación espacial de los cambios de píxeles, algo muy común en video normal
De hecho, más que algo específico para frames de video, parece una generalización de compresión diferencial para cadenas de bits de igual longitud
Solo funciona cuando los datos de entrada tienen predictibilidad, es decir, una estructura de baja aleatoriedad, pero incluso esos datos se mezclan al pasar por una función hash
En especial, los hashes criptográficos cambian el resultado de forma completamente aleatoria, lo cual perjudica la compresión
Hola HN, soy el autor
A partir del feedback, estoy haciendo pruebas más rigurosas enfocadas en video raw y video con ruido
Aún está en una etapa temprana, pero está dando resultados bastante decentes en video raw (aunque con caveats)
Comparación con códecs estándar
Limitaciones actuales y trabajo futuro
El manejo del color no es completamente lossless a nivel de bits y en la conversión YUV-BGR aparecen errores de punto flotante (diferencia promedio por píxel de ~4.7); además, al procesar los canales BGR después de la conversión se pierde precisión
Próximos planes
Quiero intentar demostrar que es perfectamente lossless en sentido matemático
También estoy pensando cómo aplicar esta idea de lossless compression y el uso de Rational Bloom Filter en otras áreas además del video
Me confunde la línea de código de video_delta_compress.py
Por esta parte, parece que cambios como de #ffffff a #fffffa, o de #ff0000 a #00ff00, se descartan todos según el umbral
Puede que yo esté entendiendo mal la función de esa línea, pero parece que los cambios de píxeles con valor 0 ni siquiera se registran en el Bloom filter
Se explica cómo se calcula la tasa de compresión, pero me pregunto si hay ejemplos del peor, promedio y mejor caso
(edición: vi que hay ejemplos de imágenes en el repo, así que estaría bien incluirlos en el README)
El repo está bastante desordenado, pero dentro del código también hay cosas para generar gráficas y demás
Mi plan es ordenar todo mucho más cuando haga pruebas adecuadas y organice los resultados
Sigue siendo una WIP bastante messy por ahora
Códecs como H.264 también pueden usar un modo realmente lossless; no es común, pero se puede
Yo mismo llegué a usar el modo lossless con aceleración por hardware de NVENC
Pero la reproducción era complicada; recuerdo que solo funcionaba con ffplay y casi nada más
Buen concepto, pero me parece que para cadenas binarias sparse quizá los métodos tradicionales de compresión sigan siendo mejores
Viendo el repo, parece que la tasa de compresión se calcula a partir de cuántas diferencias de píxeles se descartaron
Eso es interesante, pero en la práctica lo más importante sería compararlo directamente con el tamaño promedio en bytes de cada frame en un video comprimido por YouTube
Sin eso, es difícil saber si este método realmente mejora el rendimiento actual
Si este algoritmo es con pérdida, entonces como empuja las diferencias pequeñas a 0, sería más apropiado compararlo con métodos de compresión con pérdida