- O Rational Bloom Filter Video Compression implementa um fluxo de trabalho sem perdas que comprime vídeo bruto e exige que o resultado restaurado seja idêntico ao original bit a bit
- O ponto central é uma estrutura que aplica um número não inteiro de funções hash ao filtro de Bloom, buscando teoricamente uma taxa de compressão melhor que a dos métodos existentes
- É voltado a conteúdo de vídeo bruto, como Y4M, YUV e HDR, e afirma oferecer economia de espaço de 40% a 50% em vídeos comuns
- A implementação é baseada em Python 3.7+ e exige dependências como
numpy, opencv-python, xxhash, Pillow, scikit-image e pyexr para HDR
- Inclui benchmarks comparando com FFV1, HuffYUV e o modo sem perdas do H.264; antes do uso prático, o fluxo é conferir os resultados e os procedimentos de reprodução em
results.md
Visão geral do Rational Bloom Filter Video Compression
- Este projeto implementa um método de compressão de vídeo sem perdas baseado em rational Bloom filter
- O filtro de Bloom é usado como uma estrutura de dados probabilística para representar dados binários de forma eficiente
- O diferencial é usar uma rational hash function no filtro de Bloom, em vez de uma quantidade inteira
- O objetivo é que o resultado restaurado após a compressão corresponda ao original de forma bit-exact
Alvos suportados e recursos de compressão
- O sistema de compressão é voltado a conteúdo de vídeo bruto, como Y4M, YUV e HDR
- Os recursos oferecidos são os seguintes
- true lossless compression, garantindo restauração idêntica bit a bit
- economia de espaço de 40% a 50% em conteúdos de vídeo comuns
- Codificação e decodificação com suporte a multithreading
- Suporte a vários color spaces, como RGB, BGR e YUV
- Suporte ao processamento de conteúdo HDR
- O processamento HDR tem a limitação de que “é preciso mais trabalho para torná-lo rápido e utilizável”
Requisitos de instalação
- O ambiente de execução é Python 3.7+
- Os pacotes necessários são os seguintes
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr: para suporte a HDR
- As dependências são instaladas com o seguinte comando
pip install -r requirements.txt
Modo básico de uso
- No código Python, importa-se
ImprovedVideoCompressor e inicializa-se o compressor
- A configuração de exemplo inclui
noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True e verbose=True
compress_video() comprime o vídeo de entrada em um arquivo .bfvcdecompress_video() restaura o arquivo .bfvcverify_lossless() verifica se os frames originais e restaurados são sem perdas
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 pela linha de comando
- A compressão de vídeo é executada assim
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
- Arquivos raw YUV são processados especificando também largura, altura e formato
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444
Benchmarks e métodos comparados
- O projeto inclui um sistema de benchmarks que compara a compressão Rational Bloom Filter com outros métodos de compressão sem perdas
- Os métodos comparados são FFV1, HuffYUV e o modo sem perdas do H.264
- O comando para executar o benchmark completo é o seguinte
python benchmark_compression.py
- Também é possível executar especificando apenas um dataset e métodos específicos
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
- Os resultados detalhados dos benchmarks e o método de reprodução estão em results.md
Fluxo de funcionamento do método de compressão
- O esquema de compressão opera nas seguintes etapas
- Frame Extraction: extrai frames do vídeo de entrada
- Keyframe Selection: os keyframes são armazenados diretamente como frames comprimidos com zlib
- Bloom Filter Compression: os inter frames têm seus mapas de diferença comprimidos com um rational Bloom filter
- Lossless Verification: verifica a restauração bit-exact durante a decodificação
- O rational Bloom filter usa um número não inteiro de funções hash
k* para otimizar o equilíbrio entre espaço e precisão
- A implementação usa deterministamente
⌊k*⌋ funções hash, e uma função hash adicional é aplicada com probabilidade k* - ⌊k*⌋
Estrutura de arquivos do projeto
improved_video_compressor.py: main implementation do algoritmo de compressãoverify_true_lossless.py: script que verifica a restauração sem perdasbenchmark_compression.py: sistema de benchmarks que compara vários métodos de compressãodownload_*.py: scripts para baixar datasets de testeresults.md: resultados detalhados dos benchmarks e análise
Licença e citação
- A licença é MIT License, e os detalhes podem ser conferidos no arquivo
LICENSE
- Se o código for usado em pesquisa, a orientação é usar a citação em formato BibTeX incluída no README
1 comentários
Comentários do Hacker News
Acho que o documento não explicou muito bem uma ideia bastante simples. Se entendi corretamente, primeiro se cria um bitmap vendo cada bit como um pixel da imagem e, ao ir do frame 0 para o frame 1, pixels que mudaram ficam com 1; caso contrário, 0.
Depois, os offsets das posições que são 1 são hasheados e inseridos em um Bloom filter. Assim, esses índices e uma certa proporção de índices falso-positivos passam a ser positivos.
Em seguida, consulta-se o Bloom filter para encontrar todos os índices positivos e, para esses pixels, salvam-se os dados brutos dos pixels alterados, permitindo reconstruir facilmente o próximo frame.
Dá para ver isso como armazenar o delta entre dois frames como x,y,r,g,b de todos os pixels alterados, mas comprimindo bastante a parte x,y e armazenando um pouco mais de r,g,b do que o necessário.
Como as posições dos pixels alterados do frame 0→1 muitas vezes são parecidas com as posições que mudarão do frame 1→2, parece haver espaço para comprimir ainda mais no frame seguinte, marcando uma flag adequada e armazenando literalmente apenas os offsets que mudaram adicionalmente em relação ao anterior.
A transformação inversa começava com uma imagem pequena em pixels e a convertia em uma imagem com o dobro da largura ou da altura usando o mesmo número de coeficientes, repetindo isso.
O ponto principal é que a maior parte dos dados são coeficientes, e a maioria deles fica perto de 0, podendo ser empurrada para 0. A questão então passa a ser como codificar as posições não zero, virando algo como um bitmap e um array de valores não zero.
Os algoritmos para codificar valores não zero variavam no grau de conservadorismo, mas em geral aproveitavam o fato de esses valores ficarem bastante agrupados. Isso é exatamente o oposto das funções de hash normalmente usadas em um Bloom filter.
Esse tipo de compressão de imagem era lento porque a localidade era muito ruim tanto na transformação em si quanto na compressão dos coeficientes, então parecia um beco sem saída.
Consigo imaginar um Bloom filter sendo usado como parte de uma estratégia híbrida de compressão complexa. Nesse tipo de compressor, quanto mais ferramentas, melhor, mas não acho que em média traga uma grande melhoria.
Parece funcionar melhor porque o vídeo de entrada já é um vídeo comprimido e depois restaurado pelo YouTube.
Se a entrada fosse o vídeo original, a premissa de que “entre frames consecutivos, a maioria dos pixels muda só um pouco ou não muda nada, gerando uma matriz de diferenças esparsa” provavelmente cairia por terra.
Com um sinal muito limpo, por exemplo um sensor de baixo ruído e uma cena bem iluminada, talvez seja possível; mas, na maioria dos sinais reais, o ruído é maior que 1 LSB, então eu esperaria que pelo menos cerca de metade dos bits inferiores mudasse.
Quando o vídeo passa uma vez por compressão e restauração, esse ruído tende a ser removido, criando um vídeo artificialmente estático no qual essa premissa vale.
Parece que pixels cuja mudança média nos valores r,g,b é menor que 10 não têm a diferença armazenada. Assim, mesmo que um pixel mude de azul puro (#00ff00) para vermelho puro (#ff0000) em frames consecutivos, ambos os frames poderiam ser restaurados como azul puro.
Vídeo sem perdas combina muito mais com conteúdo digital, como gravações de tela. A suposição de que poucos pixels mudam entre frames consecutivos também é mais plausível nesse contexto.
A menos que você ative isso diretamente e assuma o tamanho dos arquivos e a carga de processamento, talvez nem saiba que ainda existe o conceito de dados originais ou não processados.
Eu nunca tinha pensado nisso dessa forma antes.
Ou então comprar uma câmera e gravar você mesmo vídeos 8K brutos de cenas do dia a dia.
Pelo gráfico [1], esse novo método de compressão não é sempre estritamente pior do que simplesmente usar GZIP?
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
“Insight central: se a densidade de 1s em uma string binária for baixa, especialmente abaixo de p* ≈ 0,32453, é mais eficiente codificar apenas as posições dos 1s do que armazenar a string bruta.”
Boa parte do que JPEG/MPEG fazem é reorganizar o problema para conseguir criar longas sequências de 0s. A forma como blocos DCT são varridos conforme a posição dos componentes AC/DC talvez seja uma das partes mais inovadoras de várias técnicas de compressão de vídeo e imagem
Para dizer de forma mais favorável, não há nada nessa técnica que seja específico para quadros de vídeo. A mesma ideia poderia ser usada para comprimir a diferença entre duas sequências de bits de mesmo tamanho
Ainda assim, é pouco provável que esse problema seja melhor do que métodos de compressão existentes, por exemplo concatenar dois blocos e passar gzip. Para que haja compressão, a distribuição de entrada — aqui, o conjunto de diferentes posições de bits — precisa ser muito previsível e não aleatória, mas passar os dados por uma função hash destrói essa propriedade. Em especial, o objetivo de um hash criptograficamente forte é tornar a saída indistinguível de aleatória
O que a DCT e a conversão de representação de cores fazem é transformar detalhes finos em altas frequências e detalhes essenciais em baixas frequências. Depois disso, a qualidade da imagem e a taxa de compressão se reduzem a quanto da representação de altas frequências você descarta
Além disso, o JPEG usa tabelas de Huffman para reduzir ainda mais o tamanho da imagem
Até onde sei, ele não faz nada especial para reduzir longas sequências de 0s. Por isso, alinhar 0s em sequência não ajuda tanto assim
Esta linha me confundiu: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
Isso tornaria a compressão com perdas e, por exemplo, parece que descartaria uma transição de #ffffff para #fffffa. A linha logo acima, que calcula a média dos dados dos pixels, também parece descartar uma transição de #ff0000 para #00ff00 independentemente do limiar
Talvez eu esteja entendendo mal o papel dessa linha de código. O que vira 0 na máscara resultante parece não ser codificado no Bloom filter
Está descrito como calcular a taxa de compressão, mas fiquei curioso se há exemplos de taxa de compressão no pior caso, média e melhor caso
Edit: vi que há imagens no repositório. Seria útil colocá-las no README
Pretendo deixá-lo muito mais concreto depois de fazer bastante teste adequado. Por enquanto, ainda está mais para um trabalho em andamento bem bagunçado
Sou o autor. Recebi muito feedback bom, então decidi me concentrar por enquanto em testes mais rigorosos com vídeo original e vídeos com ruído. Vou continuar atualizando o repositório com frequência
Ainda está em estágio muito inicial, mas nos testes com vídeo original obtive resultados bem razoáveis, com algumas ressalvas. Taxa de compressão de 4,8%, ou seja, redução de 95,2% no tamanho, velocidade de compressão de 8,29 fps, velocidade de descompressão de 9,16 fps, keyframes necessários em apenas 4% dos quadros e saída perceptualmente sem perdas (PSNR de 31,10 dB)
Comparando com codecs padrão: Rational Bloom Filter 4,8%, JPEG2000 sem perdas 3,7%, FFV1 sem perdas 36,5%, H.265/HEVC com perdas 9,2%, H.264 com perdas 0,3%
Também há limitações atuais e trabalhos futuros. Embora os resultados de compressão sejam promissores, o tratamento dos canais de cor ainda não é verdadeiramente sem perdas. A implementação atual tem dificuldades na conversão de espaço de cores de YUV para BGR, e a precisão dessa conversão gera pequenos erros de arredondamento, deixando uma diferença média de cerca de 4,7 nos valores dos pixels
Além disso, a implementação atual processa os canais de cor no formato BGR depois da conversão, causando perda adicional de precisão
Daqui em diante, planejo processar YUV diretamente sem conversão para BGR, tratar os dados de cor com exatidão em nível de bit, ajustar os parâmetros do Bloom filter aos padrões de subamostragem de croma e criar um sistema dedicado que valide cada canal de cor de forma independente
Quero provar matematicamente que é sem perdas, mas ainda há um longo caminho. Pretendo continuar explorando essa ideia de compressão sem perdas e também tenho algumas ideias para usar o Rational Bloom Filter em outras áreas
Codecs como H.264 também podem ser executados em modo realmente sem perdas. Só que quase ninguém usa assim
É um conceito simpático, mas, se você tem uma string binária esparsa, é bem provável que métodos tradicionais façam melhor
É difícil acompanhar o repositório, mas a taxa de compressão parece ser calculada observando quantas diferenças de pixels puderam ser descartadas
É interessante, mas a comparação mais importante provavelmente seria o tamanho médio em bytes de cada quadro em um vídeo comprimido do YouTube. Sem essa comparação, é difícil avaliar se há melhora em relação aos métodos atuais
Se o algoritmo for com perdas, isto é, se ele zera pequenas diferenças, então não é sem perdas e acho que deveria ser comparado com outros algoritmos com perdas