- Rational Bloom Filter Video Compression triển khai quy trình không mất dữ liệu, trong đó video thô được nén và kết quả khôi phục phải giống bản gốc đến từng bit
- Điểm cốt lõi là áp dụng số lượng hàm băm không nguyên cho bộ lọc Bloom, một cấu trúc về mặt lý thuyết hướng tới tỷ lệ nén tốt hơn so với các phương pháp hiện có
- Nhắm đến nội dung video thô như Y4M, YUV, HDR, và được mô tả là có thể giảm 40–50% dung lượng đối với video thông thường
- Phần triển khai dựa trên Python 3.7+ và cần các phụ thuộc như
numpy, opencv-python, xxhash, Pillow, scikit-image, pyexr cho HDR
- Có kèm benchmark so sánh với FFV1, HuffYUV và chế độ không mất dữ liệu của H.264, nên trước khi sử dụng thực tế, quy trình là kiểm tra kết quả và cách tái lập trong
results.md
Tổng quan về Rational Bloom Filter Video Compression
- Dự án này triển khai phương pháp nén video không mất dữ liệu dựa trên rational Bloom filter
- Bộ lọc Bloom được dùng như một cấu trúc dữ liệu xác suất để biểu diễn dữ liệu nhị phân một cách hiệu quả
- Điểm khác biệt là bộ lọc Bloom sử dụng rational hash function, tức hàm băm không phải số nguyên
- Mục tiêu là kết quả sau khi nén rồi khôi phục phải khớp với bản gốc ở mức bit-exact
Đối tượng hỗ trợ và tính năng nén
- Hệ thống nén nhắm đến nội dung video thô như Y4M, YUV, HDR
- Các tính năng cung cấp gồm
- true lossless compression, bảo đảm khôi phục giống hệt đến từng bit
- Giảm 40–50% dung lượng với nội dung video thông thường
- Mã hóa và giải mã với hỗ trợ đa luồng
- Hỗ trợ nhiều color space như RGB, BGR, YUV
- Hỗ trợ xử lý nội dung HDR
- Xử lý HDR có giới hạn là “cần thêm công việc để làm cho nó nhanh và dùng được”
Yêu cầu cài đặt
- Môi trường chạy là Python 3.7+
- Các gói cần thiết gồm
numpyopencv-pythonmatplotlibpandastqdmrequestsxxhashPillowscikit-imagepyexr: dùng để hỗ trợ HDR
- Cài đặt các phụ thuộc bằng lệnh sau
pip install -r requirements.txt
Cách sử dụng cơ bản
- Trong mã Python, import
ImprovedVideoCompressor và khởi tạo bộ nén
- Cấu hình ví dụ gồm
noise_tolerance=10.0, keyframe_interval=30, use_direct_yuv=True, verbose=True
compress_video() nén video đầu vào thành tệp .bfvcdecompress_video() khôi phục tệp .bfvc- Dùng
verify_lossless() để xác minh tính không mất dữ liệu giữa khung hình gốc và khung hình đã khôi phục
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']}")
Sử dụng dòng lệnh
- Nén video được chạy như sau
python -m improved_video_compressor compress input_video.y4m output.bfvc --max-frames 30
- Tệp raw YUV được xử lý bằng cách chỉ định kèm chiều rộng, chiều cao và định dạng
python -m improved_video_compressor process-yuv input.yuv output.bfvc --width 1920 --height 1080 --format YUV444
Benchmark và đối tượng so sánh
- Dự án bao gồm hệ thống benchmark để so sánh nén Rational Bloom Filter với các phương pháp nén không mất dữ liệu khác
- Các đối tượng so sánh là FFV1, HuffYUV và chế độ không mất dữ liệu của H.264
- Lệnh chạy benchmark đầy đủ như sau
python benchmark_compression.py
- Cũng có thể chỉ định dataset và phương pháp cụ thể để chạy
python benchmark_compression.py --datasets y4m --methods bloom ffv1 --max-frames 10
- Kết quả benchmark chi tiết và cách tái lập nằm trong results.md
Luồng hoạt động của phương pháp nén
- Sơ đồ nén hoạt động theo các bước sau
- Frame Extraction: trích xuất khung hình từ video đầu vào
- Keyframe Selection: keyframe được lưu dưới dạng khung hình nén trực tiếp bằng zlib
- Bloom Filter Compression: các inter-frame được nén bằng rational Bloom filter dưới dạng bản đồ sai khác
- Lossless Verification: xác minh khôi phục bit-exact trong quá trình giải mã
- Rational Bloom filter dùng số lượng hàm băm không nguyên
k* để tối ưu cân bằng giữa dung lượng và độ chính xác
- Phần triển khai sử dụng xác định
⌊k*⌋ hàm băm, và áp dụng hàm băm bổ sung với xác suất k* - ⌊k*⌋
Cấu trúc tệp của dự án
improved_video_compressor.py: main implementation của thuật toán nénverify_true_lossless.py: script xác minh khôi phục không mất dữ liệubenchmark_compression.py: hệ thống benchmark so sánh nhiều phương pháp néndownload_*.py: script tải dataset kiểm thửresults.md: kết quả benchmark chi tiết và phân tích
Giấy phép và trích dẫn
- Giấy phép là MIT License, có thể xem chi tiết trong tệp
LICENSE
- Nếu sử dụng mã trong nghiên cứu, README hướng dẫn dùng citation ở định dạng BibTeX được bao gồm trong đó
1 bình luận
Các ý kiến trên Hacker News
Có vẻ tài liệu đã không giải thích tốt một ý tưởng rất đơn giản. Nếu tôi hiểu đúng, trước hết ta tạo một bitmap xem mỗi bit như một pixel của ảnh, rồi khi đi từ frame 0 sang frame 1, pixel nào thay đổi thì đặt là 1, nếu không thì là 0
Sau đó băm offset của các vị trí có giá trị 1 và đưa vào Bloom filter. Khi đó các chỉ mục đó cùng một tỷ lệ nhất định các chỉ mục dương tính giả sẽ cho kết quả dương tính
Tiếp theo, truy vấn Bloom filter để tìm tất cả chỉ mục dương tính, rồi lưu dữ liệu pixel thô đã thay đổi cho các pixel đó, như vậy có thể dễ dàng tái tạo frame tiếp theo
Có thể xem đây là cách lưu delta giữa hai frame dưới dạng x,y,r,g,b của tất cả pixel đã thay đổi, nhưng nén mạnh phần x,y và lưu thêm một chút r,g,b quá mức cần thiết
Vị trí các pixel thay đổi từ frame 0→1 thường khá giống với vị trí sẽ thay đổi từ frame 1→2, nên có vẻ vẫn còn dư địa nén thêm bằng cách đặt một cờ phù hợp ở frame tiếp theo và chỉ lưu nguyên các offset khác thêm so với trước đó
Phép biến đổi ngược bắt đầu từ một ảnh pixel nhỏ, dùng cùng số lượng hệ số để biến nó thành ảnh có chiều rộng hoặc chiều cao gấp đôi, rồi lặp lại quá trình đó
Điểm cốt lõi là phần lớn dữ liệu là các hệ số, và đa số trong đó gần bằng 0 đến mức có thể đẩy về 0. Khi đó vấn đề trở thành làm sao mã hóa các vị trí khác 0, và cấu trúc sẽ giống như bitmap cùng mảng các giá trị khác 0
Các thuật toán mã hóa giá trị khác 0 khác nhau về mức độ bảo thủ, nhưng nhìn chung đều tận dụng tính chất là các giá trị đó khá tụ lại với nhau. Điều này hoàn toàn trái ngược với các hàm băm thông thường dùng trong Bloom filter
Kiểu nén ảnh như vậy rất chậm vì tính cục bộ rất kém cả ở bản thân phép biến đổi lẫn nén hệ số, nên tôi cảm thấy đó là một ngõ cụt
Tôi nghĩ Bloom filter có thể được dùng như một phần của chiến lược nén lai phức tạp. Với một bộ nén như vậy, càng nhiều công cụ càng tốt, nhưng trung bình có lẽ sẽ không cải thiện lớn
Có vẻ nó hoạt động tốt hơn vì video đầu vào vốn đã là video được nén rồi khôi phục từ YouTube
Nếu đầu vào là video gốc, giả định “giữa các frame liên tiếp, phần lớn pixel chỉ thay đổi rất ít hoặc không thay đổi, tạo ra một ma trận sai khác thưa” có lẽ sẽ bị phá vỡ
Với tín hiệu rất sạch, chẳng hạn cảm biến ít nhiễu và cảnh sáng, thì có thể, nhưng với phần lớn tín hiệu thực tế, nhiễu lớn hơn 1 LSB nên tôi dự đoán ít nhất khoảng một nửa các bit thấp sẽ thay đổi
Khi cho video đi qua một lần nén và khôi phục, loại nhiễu đó có xu hướng bị loại bỏ, tạo ra một video tĩnh một cách nhân tạo khiến giả định này đúng
Có vẻ các pixel có mức thay đổi trung bình của giá trị r,g,b nhỏ hơn 10 thì không lưu sai khác. Như vậy ngay cả khi một pixel trong các frame liên tiếp đổi từ xanh lục thuần (#00ff00) sang đỏ thuần (#ff0000), cả hai frame vẫn có thể được khôi phục thành xanh lục thuần
Video không mất dữ liệu phù hợp hơn nhiều với nội dung số như ghi màn hình. Giả định rằng ít pixel thay đổi giữa các frame liên tiếp cũng hợp lý hơn ở trường hợp đó
Trừ khi tự bật tùy chọn đó và chấp nhận kích thước tệp cùng gánh nặng xử lý, họ thậm chí có thể không biết rằng vẫn còn khái niệm dữ liệu gốc hay chưa xử lý
Trước đây tôi chưa từng nghĩ theo cách này
Hoặc mua một chiếc camera và tự quay video 8K gốc các cảnh đời thường
Theo biểu đồ [1], chẳng phải phương pháp nén mới này luôn tệ hơn một cách nghiêm ngặt so với chỉ dùng GZIP sao?
[1] https://github.com/ross39/new_bloom_filter_repo/blob/main/co...
“Nhận định cốt lõi: nếu mật độ bit 1 trong chuỗi nhị phân thấp, đặc biệt là dưới p* ≈ 0.32453, thì việc chỉ mã hóa vị trí của các bit 1 sẽ hiệu quả hơn lưu chuỗi thô.”
Phần lớn những gì JPEG/MPEG làm là sắp xếp lại bài toán để có thể tạo ra các dãy dài toàn 0. Cách quét các khối DCT theo vị trí của các thành phần AC/DC có thể là một trong những phần sáng tạo nhất trong nhiều kỹ thuật nén video và hình ảnh
Nói tích cực hơn, kỹ thuật này không có gì đặc thù cho khung hình video. Có thể dùng cùng ý tưởng để nén phần sai khác giữa hai chuỗi bit có cùng độ dài
Dù vậy, bài toán này khó có khả năng tốt hơn các phương pháp nén hiện có, chẳng hạn nối hai khối lại rồi gzip. Để nén được, phân phối đầu vào — ở đây là tập hợp các vị trí bit khác nhau — phải rất dễ dự đoán và không ngẫu nhiên, nhưng khi đưa dữ liệu qua hàm băm thì tính chất đó bị phá vỡ. Đặc biệt, mục tiêu của một hàm băm mạnh về mật mã học là làm cho đầu ra không thể phân biệt với ngẫu nhiên
Việc DCT và chuyển đổi biểu diễn màu làm là biến các chi tiết nhỏ thành tần số cao, còn chi tiết cốt lõi thành tần số thấp. Sau đó, chất lượng ảnh và tỉ lệ nén được đơn giản hóa thành việc bỏ đi bao nhiêu phần biểu diễn tần số cao
Ngoài ra, JPEG dùng bảng Huffman để giảm thêm kích thước ảnh
Theo hiểu biết của tôi, nó không làm gì đặc biệt để giảm các dãy dài toàn 0. Vì vậy việc xếp các số 0 thành hàng không giúp được nhiều
Dòng này khiến tôi bối rối: https://github.com/ross39/new_bloom_filter_repo/blob/4798d90...
Như vậy thì nén trở thành nén mất dữ liệu, và có vẻ sẽ bỏ qua, chẳng hạn, chuyển đổi từ #ffffff sang #fffffa. Dòng ngay phía trên lấy trung bình dữ liệu pixel cũng có vẻ sẽ bỏ qua chuyển đổi từ #ff0000 sang #00ff00, bất kể ngưỡng là gì
Không rõ có phải tôi hiểu sai vai trò của dòng code đó không. Những phần thành 0 trong mask kết quả trông như không được mã hóa vào Bloom filter
Có ghi cách tính tỉ lệ nén, nhưng tôi tò mò liệu có ví dụ về tỉ lệ nén xấu nhất, trung bình và tốt nhất không
Sửa: tôi thấy trong kho có hình ảnh. Có lẽ đưa vào README sẽ hữu ích
Tôi dự định sẽ chạy nhiều bài kiểm thử đúng nghĩa hơn để làm cho nó cụ thể hơn nhiều. Hiện tại nó vẫn giống một bản đang làm dở và rất bừa bộn
Tôi là tác giả. Nhận được nhiều phản hồi tốt nên trong thời gian tới tôi quyết định tập trung vào các kiểm thử nghiêm ngặt hơn với video gốc và video có nhiễu. Tôi sẽ tiếp tục cập nhật kho thường xuyên
Dù vẫn còn rất sớm, các thử nghiệm trên video gốc đã cho kết quả khá ổn cùng vài manh mối: tỉ lệ nén 4,8%, tức giảm kích thước 95,2%, tốc độ nén 8,29fps, tốc độ giải nén 9,16fps, chỉ cần keyframe cho 4% số khung hình, và đầu ra gần như không mất dữ liệu về cảm nhận (PSNR 31,10dB)
So với các codec chuẩn: Rational Bloom Filter 4,8%, JPEG2000 không mất dữ liệu 3,7%, FFV1 không mất dữ liệu 36,5%, H.265/HEVC mất dữ liệu 9,2%, H.264 mất dữ liệu 0,3%
Cũng có các giới hạn hiện tại và hướng làm tiếp theo. Kết quả nén hứa hẹn, nhưng xử lý kênh màu hiện vẫn chưa thật sự không mất dữ liệu. Bản triển khai hiện tại gặp khó khăn trong quá trình chuyển đổi không gian màu từ YUV sang BGR, và do độ chính xác của chuyển đổi không gian màu nên phát sinh lỗi làm tròn nhỏ, để lại chênh lệch giá trị pixel trung bình khoảng 4,7
Ngoài ra, bản triển khai hiện tại xử lý các kênh màu ở định dạng BGR sau khi chuyển đổi, gây thêm mất mát độ chính xác
Sắp tới tôi dự định xử lý trực tiếp YUV mà không chuyển sang BGR, xử lý dữ liệu màu chính xác đến từng bit, tinh chỉnh tham số Bloom filter theo mẫu chroma subsampling, và xây dựng một hệ thống chuyên dụng để kiểm chứng từng kênh màu một cách độc lập
Tôi muốn chứng minh về mặt toán học rằng nó không mất dữ liệu, nhưng vẫn còn một chặng đường dài. Tôi dự định tiếp tục đào sâu ý tưởng nén không mất dữ liệu này, và cũng có vài ý tưởng dùng Rational Bloom Filter trong các lĩnh vực khác
Các codec như H.264 cũng có thể chạy ở chế độ thật sự không mất dữ liệu. Chỉ là hầu như chẳng ai dùng như vậy
Ý tưởng dễ thương đấy, nhưng nếu có chuỗi nhị phân thưa, khả năng cao là các phương pháp truyền thống sẽ làm tốt hơn
Khó theo dõi kho này, nhưng tỉ lệ nén có vẻ được tính dựa trên việc có thể bỏ đi bao nhiêu sai khác pixel
Dù thú vị, đối tượng so sánh quan trọng hơn có lẽ là kích thước byte trung bình của mỗi khung hình trong video YouTube đã nén. Nếu không có so sánh này thì khó đánh giá liệu nó có cải thiện so với cách hiện hành không
Nếu thuật toán là dạng mất dữ liệu, tức ép các sai khác nhỏ về 0, thì nó không phải không mất dữ liệu và có lẽ nên được so với các thuật toán mất dữ liệu khác