Compressão de vídeo sem perdas com filtros de Bloom
(github.com/ross39)- Este projeto open source usa filtros de Bloom para viabilizar compressão de vídeo sem perdas
- Introduz o conceito de Rational Bloom Filter para superar limitações dos filtros de Bloom tradicionais e explorar compressão eficiente
- Diferentemente dos codecs comuns, garante compressão sem perdas com restauração perfeita de todos os dados
- Em vez do frame inteiro, foca nas diferenças entre frames para comprimir dados esparsos com eficiência
- Resultados experimentais, procedimentos de verificação e explicações do princípio aumentam bastante a confiabilidade
Visão geral do projeto
Este projeto open source tenta realizar compressão de vídeo sem perdas ao modificar de forma inovadora o filtro de Bloom (uma estrutura de dados que verifica de forma rápida e eficiente se um determinado valor pertence a um conjunto). Codecs de vídeo tradicionais, como H.264, aumentam a taxa de compressão removendo informações invisíveis ao olho humano, mas esse método perde a integridade completa das informações. Este projeto demonstra uma forma de reduzir o tamanho dos arquivos mantendo a restauração perfeita dos dados. Em particular, o uso de uma quantidade racional (não inteira) de funções de hash no filtro de Bloom e a estrutura de compressão baseada em Δ de frame (diferença) são seus destaques técnicos.
Guia do código-fonte principal
- Arquivo principal: youtube_bloom_compress.py
- É possível executar a demonstração com comandos simples
- Ainda há limitações de velocidade para vídeos longos, e a otimização contínua está em andamento
Fundamentos do filtro de Bloom
O filtro de Bloom usa várias funções de hash e requer pouquíssima memória para verificar se um valor está presente em um conjunto. Ele permite alguns falsos positivos (false positive), mas nunca gera falsos negativos (false negative), o que lhe dá uma forte vantagem em confiabilidade.
Mudança inovadora: Rational Bloom Filter
O número ótimo de funções de hash (k) em um filtro de Bloom normalmente não é inteiro. Por isso, o Rational Bloom Filter utiliza um k* real:
- sempre aplica ⌊k*⌋ funções de hash
- aplica probabilisticamente uma função de hash adicional na proporção restante (ex.: se k* = 2.7, a terceira hash é usada com 70% de probabilidade)
- foi projetado para que essa decisão probabilística ocorra de forma consistente para cada elemento
Esse método funciona com precisão tanto na compressão quanto na restauração, aumentando a confiabilidade da compressão
Expansão do filtro de Bloom para um compressor
A ideia central é que, em uma string binária esparsa, onde 1s são raros, registrar apenas as posições dos 1s pode permitir gravar os dados com menos espaço do que armazenar todos os bits originais.
- Etapa de compressão:
- indicar as posições dos 1s no bitmap do filtro de Bloom
- além do filtro de Bloom, armazenar separadamente os valores de bits realmente necessários (dados-testemunha)
- A análise teórica mostra que há ganho de compressão quando a proporção de 1s é menor que 0.32453
Fórmulas e otimização das técnicas centrais
- São apresentadas fórmulas para k (número de funções de hash) e l (tamanho do bitmap) de acordo com a esparsidade
- É possível calcular automaticamente parâmetros ótimos com base na distribuição de bits dos dados de entrada
Como a técnica é aplicada à compressão de vídeo
- Extrai apenas as mudanças entre frames (valores de Δ), convertendo-as em uma matriz esparsa na qual quase nada muda
- Aplica a técnica de compressão com filtro de Bloom a essa matriz de diferenças esparsas
- Melhora significativamente a eficiência de armazenamento em comparação com guardar frames completos
Procedimento de verificação da compressão e restauração
- Calcula o tamanho de todos os itens necessários para restauração, como bitmap comprimido, dados-testemunha, metadados e pixels alterados
- Após restaurar por frame, verifica se há correspondência bit a bit com o original
- Realiza visualização e quantificação das diferenças por frame, além de validação completa de todo o pipeline
- O cálculo da taxa de compressão está claramente descrito no código, permitindo reprodução e verificação por qualquer pessoa
Estrutura de compressão totalmente autossuficiente
- Não requer dicionário externo nem tabela de consulta para restauração
- Todos os parâmetros do filtro de Bloom e informações de cor ficam armazenados no próprio arquivo comprimido
- A restauração perfeita é possível apenas com o arquivo comprimido
Conclusão e informações sobre o open source
Este projeto usa filtros de Bloom para explorar ao máximo a esparsidade dos dados e é ideal para tarefas que exigem restauração perfeita, como dados científicos e imagens médicas. Também é possível experimentar diretamente a nova estrutura algorítmica e o sistema de validação, além de deixar sugestões de melhoria.
1 comentários
Comentários no Hacker News
Acho que este documento, na prática, dá uma explicação complicada para uma ideia simples
Isso é parecido com armazenar as diferenças entre dois frames como x, y, r, g, b, mas comprimindo muito as coordenadas x e y em troca de armazenar um pouco mais de r, g, b
Como normalmente as posições dos pixels que mudam em cada frame são parecidas, parece até haver a possibilidade de comprimir ainda mais no frame seguinte configurando bem os flags dessas posições e armazenando adicionalmente só os novos offsets que mudaram
É exatamente para ver comentários assim, com alto nível de compreensão, que eu sempre leio os comentários primeiro
E agora vi que o autor também é a pessoa que fez o kilo, muito legal
[edit] Até o jeito de editar parece divertido por algum motivo
Fiquei curioso para saber qual é a taxa de compressão real
No passado experimentei compressão de imagem baseada em wavelet
A transformada inversa começa com uma imagem pequena e vai dobrando de tamanho aos poucos usando os coeficientes
A maior parte dos dados são coeficientes quase zero, e a compressão vem de zerar isso
O ponto central é codificar de forma eficiente onde estão as partes diferentes de zero, e normalmente esses valores ficam agrupados, então muitos algoritmos exploram bastante essa característica
Isso é exatamente o oposto da característica das funções de hash usadas em Bloom filters
Lembro que essa abordagem acabou esbarrando em limites porque tanto a transformação quanto a compressão dos coeficientes tinham pouca relação espacial e eram lentas
Fiquei curioso sobre em que aspecto um Bloom filter seria mais vantajoso do que uma hash table
Boa parte da compressão de vídeo tem a ver com “movimento”
Fico me perguntando como isso lida com situações como um pan de câmera, em que o mesmo pixel é deslocado 2 pixels para a esquerda
Se você armazenar apenas as mudanças delta entre frames, então todos os pixels que não mudaram serão 0
Comprimir sequências contínuas de 0 é uma das partes mais fáceis da compressão com perdas, mas na abordagem com Bloom filter existem false positives
Bloom filter talvez possa servir como uma estratégia subordinada dentro de um compressor composto, e misturar várias técnicas provavelmente é melhor, mas em média não parece que ele vá melhorar muito o desempenho em relação às abordagens existentes
Acho que existe um motivo para essa técnica funcionar bem em vídeos já comprimidos e depois descomprimidos, como vídeos do YouTube
Em entrada raw, a suposição de que a maioria dos pixels quase não muda entre frames consecutivos pode falhar
Em cenas totalmente limpas, com pouco ruído e bem iluminadas, isso pode funcionar, mas em sinais comuns há muito ruído acima de 1 LSB, então os bits menos significativos devem mudar com frequência
Depois de passar por compressão e descompressão, o ruído diminui e essa suposição passa a valer
Na prática, isso também não é lossless
No código de video_delta_compress.py, mudanças não são armazenadas se a variação média de r,g,b for menor que 10
Por exemplo, até uma mudança de pure blue (#00ff00) para pure red (#ff0000) seria tratada assim, e os dois frames acabariam sendo reconstruídos como pure blue
Assim como não se usa PNG para tirar fotos, codecs lossless raramente são usados em vídeo do mundo real
Vídeo lossless combina mais com conteúdo digital como gravação de tela
Nesses casos, poucos pixels mudam entre os frames, então a suposição desse método se encaixa bem
No código, quando a proporção é menor que 32,4%, é usada uma estratégia de armazenar apenas as posições dos bits 1
Mesmo que os bits menos significativos mudem com frequência, será que isso ainda não poderia funcionar se os bits mais significativos mudarem pouco? É o que fico pensando
Em geral, quase ninguém usa vídeo raw
Celulares e câmeras já salvam em MP4, AV1 etc. por padrão
Considerando o tamanho dos arquivos e o custo de processamento, muita gente talvez nem saiba da existência de formatos raw sem processamento
Então, do jeito atual, isso parece adequado para animação
Pelo gráfico relacionado compression_comparison.png, a dúvida é se esse novo método de compressão sempre fica atrás do GZIP
Só não encontrei números de desempenho
Foi mencionada a principal sacada do texto: “uma string binária com densidade de 1s suficientemente baixa pode ser comprimida com mais eficiência do que os dados originais armazenando apenas as posições dos 1s”
JPEG, MPEG etc. reorganizam o problema justamente para que apareçam longas sequências de 0, e o método de varredura de blocos DCT foi extremamente inovador para compressão de vídeo desse tipo
DCT e transformação de cor convertem detalhes finos em altas frequências e o conteúdo principal em baixas frequências
A compressão então joga fora principalmente os componentes de alta frequência
JPEG também otimiza tamanho com tabela Huffman
Não se usa muito alguma técnica especial só para juntar 0s, e o fato de os 0s ficarem agrupados não aumenta tanto assim a eficiência da compressão
Concordo
O maior problema da abordagem do OP é que ela descarta ativamente a correlação espacial das mudanças de pixel, algo muito comum em vídeo normal
Na prática, nem é algo específico para frames de vídeo, mas uma generalização de compressão por diferenças entre sequências de bits de mesmo tamanho
Ela só funciona quando os dados de entrada têm previsibilidade, ou seja, uma estrutura pouco aleatória, mas até esses dados acabam embaralhados ao passar por uma função de hash
Especialmente hashes criptográficos tornam o resultado completamente aleatório, o que é ruim para compressão
Olá HN, sou o autor
Com base no feedback, estou fazendo testes mais rigorosos focados em vídeo raw e em vídeos com ruído
Ainda está em estágio inicial, mas estou vendo resultados razoavelmente bons em vídeo raw (com ressalvas)
Comparação com codecs padrão
Limitações atuais e trabalho futuro
O tratamento de cor ainda não é perfeitamente lossless em nível de bit, e o processo de conversão YUV-BGR introduz erro de ponto flutuante (diferença média por pixel ~4,7), além de haver perda de precisão ao tratar os canais BGR após a conversão
Próximos passos planejados
Quero tentar provar matematicamente que isso é perfeitamente lossless
Também estou pensando em formas de aplicar essa ideia de lossless compression e o uso de Rational Bloom Filter em outras áreas além de vídeo
Fiquei confuso com essa linha do video_delta_compress.py
Por causa disso, parece que mudanças como de #ffffff para #fffffa, ou de #ff0000 para #00ff00, acabam todas descartadas dependendo do limiar
Talvez eu tenha entendido mal o papel dessa linha, mas parece que mudanças de pixel que resultam em 0 nem chegam a ser registradas no Bloom filter
Foi explicado como a taxa de compressão é calculada, mas fiquei curioso para ver exemplos de pior, média e melhor taxa de compressão
(edição: vi que há exemplos com imagens no repositório, então a sugestão é colocar isso no README)
O repositório está bem bagunçado, mas também há código lá para gerar gráficos e afins
Pretendo organizar melhor com testes adequados e um resumo mais claro dos resultados
Ainda está numa fase de WIP bastante bagunçada
Codecs como H.264 na verdade também podem operar em modo lossless, e isso é possível embora pouco usado
Já usei inclusive aceleração por hardware com NVENC para rodar esse modo lossless
O problema maior era a reprodução: se não me engano, só funcionava no ffplay e quase nada mais
É um bom conceito, mas tenho a impressão de que, para strings binárias esparsas, métodos tradicionais de compressão provavelmente funcionam melhor
Pelo repositório, parece que a taxa de compressão é calculada com base em quantas diferenças de pixel foram descartadas entre os deltas
Isso é interessante, mas o que realmente importa mais é comparar diretamente com o tamanho médio em bytes por frame em vídeos comprimidos do YouTube
Sem isso, fica difícil saber se a abordagem atual realmente traz ganho de desempenho na prática
Se esse algoritmo for com perdas, já que diferenças pequenas são todas levadas para 0, então faz mais sentido compará-lo com compressão com perdas