Nén video không mất dữ liệu bằng bộ lọc Bloom
(github.com/ross39)- Dự án mã nguồn mở này hiện thực hóa nén video không mất dữ liệu bằng cách tận dụng bộ lọc Bloom
- Dự án đưa vào khái niệm Rational Bloom Filter để vượt qua các giới hạn của bộ lọc Bloom truyền thống và khám phá khả năng nén hiệu quả
- Khác với các codec thông thường, phương pháp này đảm bảo nén không mất dữ liệu với khả năng khôi phục hoàn toàn mọi dữ liệu
- Thay vì toàn bộ khung hình, phương pháp tập trung vào sự khác biệt giữa các khung hình để nén hiệu quả dữ liệu thưa
- Kết quả thực nghiệm, quy trình kiểm chứng và phần giải thích nguyên lý giúp củng cố độ tin cậy cao
Tổng quan dự án
Dự án mã nguồn mở này thử nghiệm nén video không mất dữ liệu bằng cách biến đổi một cách sáng tạo bộ lọc Bloom (cấu trúc dữ liệu dùng để kiểm tra nhanh và hiệu quả xem một giá trị có thuộc một tập hợp hay không). Các codec video truyền thống như H.264 tăng tỷ lệ nén bằng cách loại bỏ thông tin mà mắt người khó nhận ra, nhưng cách này làm mất tính toàn vẹn của dữ liệu. Dự án này trình diễn một phương pháp giảm kích thước tệp mà vẫn giữ được khôi phục dữ liệu hoàn hảo. Đặc biệt, cách sử dụng số lượng hàm băm hợp lý (không nguyên) của bộ lọc Bloom và cấu trúc nén dựa trên Δ khung hình (sai khác) là những điểm nổi bật về mặt kỹ thuật.
Hướng dẫn mã nguồn chính
- Tệp cốt lõi: youtube_bloom_compress.py
- Có thể chạy bản demo chỉ với các lệnh đơn giản
- Với video dài, vẫn còn giới hạn về tốc độ và hiện đang được tối ưu hóa liên tục
Cơ bản về bộ lọc Bloom
Bộ lọc Bloom sử dụng nhiều hàm băm và chỉ cần rất ít bộ nhớ để kiểm tra xem một giá trị có nằm trong tập hợp hay không. Nó cho phép một số trường hợp dương tính giả (false positive), nhưng tuyệt đối không có âm tính giả (false negative), nên có ưu thế lớn về độ tin cậy.
Đổi mới quan trọng: Rational Bloom Filter
Số lượng hàm băm tối ưu (k) của bộ lọc Bloom thường không phải số nguyên. Vì vậy, Rational Bloom Filter sử dụng giá trị thực k*:
- Luôn áp dụng ⌊k*⌋ hàm băm
- Áp dụng thêm một hàm băm theo xác suất tương ứng với phần còn lại (ví dụ: nếu k* = 2.7 thì dùng hàm băm thứ ba với xác suất 70%)
- Được thiết kế để quyết định ngẫu nhiên theo xác suất này diễn ra nhất quán cho từng phần tử
Cách làm này hoạt động chính xác cả khi nén lẫn khi khôi phục, từ đó nâng cao độ tin cậy của quá trình nén
Mở rộng từ bộ lọc Bloom sang bộ nén
Ý tưởng cốt lõi là với chuỗi nhị phân có ít bit 1 (dữ liệu thưa), chỉ cần lưu thông tin vị trí của các bit 1 thì có thể ghi dữ liệu bằng dung lượng nhỏ hơn toàn bộ chuỗi bit ban đầu.
- Giai đoạn nén:
- Ghi rõ vị trí các bit 1 trong bitmap của bộ lọc Bloom
- Ngoài bộ lọc Bloom, lưu riêng các giá trị bit thực sự cần thiết (dữ liệu witness)
- Phân tích lý thuyết cho thấy sẽ có lợi ích nén khi tỷ lệ bit 1 nhỏ hơn 0.32453
Công thức kỹ thuật cốt lõi và tối ưu hóa
- Đưa ra công thức cho k (số lượng hàm băm) và l (kích thước bitmap) theo độ thưa
- Có thể tự động tính ra các tham số tối ưu dựa trên phân bố bit của dữ liệu đầu vào
Cách áp dụng cho nén video
- Chỉ trích xuất thay đổi giữa các khung hình (giá trị Δ), rồi chuyển thành ma trận thưa vì phần lớn không có thay đổi
- Áp dụng kỹ thuật nén bộ lọc Bloom lên ma trận sai khác thưa này
- Hiệu quả lưu trữ được cải thiện đáng kể so với lưu toàn bộ khung hình
Quy trình kiểm chứng nén và khôi phục
- Tính toán dung lượng của mọi thành phần cần cho việc khôi phục như bitmap đã nén, dữ liệu witness, metadata, pixel thay đổi, v.v.
- Sau khi khôi phục theo từng khung hình, kiểm tra mức trùng khớp từng bit với dữ liệu gốc
- Tiến hành trực quan hóa và định lượng sai khác theo từng khung hình, đồng thời kiểm chứng đầy đủ toàn bộ pipeline
- Cách tính tỷ lệ nén được mô tả rõ ràng trong mã nguồn để bất kỳ ai cũng có thể tái lập và kiểm chứng
Cấu trúc nén hoàn toàn tự chứa
- Không cần từ điển hay bảng tra cứu riêng khi khôi phục
- Mọi tham số bộ lọc Bloom và thông tin màu sắc đều được chứa ngay trong tệp nén
- Chỉ với tệp nén là có thể khôi phục hoàn hảo
Kết luận và thông tin mã nguồn mở
Dự án này tận dụng tối đa tính thưa của dữ liệu bằng bộ lọc Bloom và đặc biệt phù hợp với các bài toán cần khôi phục hoàn hảo (như dữ liệu khoa học, hình ảnh y tế, v.v.). Bạn có thể trực tiếp thử nghiệm cấu trúc thuật toán mới và hệ thống kiểm chứng này, đồng thời để lại ý kiến cải tiến.
1 bình luận
Ý kiến trên Hacker News
Tôi có cảm giác tài liệu này thực ra đang giải thích một ý tưởng đơn giản theo cách quá phức tạp
Cách này tương tự việc lưu phần khác biệt giữa hai frame dưới dạng x, y, r, g, b, nhưng thay vì lưu tọa độ x, y theo cách thông thường thì nén chúng rất mạnh, đổi lại phải lưu r, g, b nhiều hơn một chút
Thông thường vị trí các pixel thay đổi giữa các frame khá giống nhau, nên có vẻ ở frame tiếp theo còn có thể nén thêm bằng cách chỉ cần đặt cờ đúng cho các vị trí đó rồi lưu bổ sung các offset mới thay đổi
Đây đúng là kiểu bình luận chất lượng cao khiến tôi lúc nào cũng đọc phần bình luận trước
Với lại nhìn ra thì tác giả cũng là người làm ra kilo, thật sự rất ngầu
[edit] Cả chuyện chỉnh sửa bổ sung nữa cũng có cảm giác khá thú vị
Tôi tò mò tỷ lệ nén thực tế đạt được là bao nhiêu
Trước đây tôi từng thử nghiệm nén ảnh dựa trên wavelet
Biến đổi ngược bắt đầu từ ảnh nhỏ, rồi dùng các hệ số để phóng to dần lên gấp đôi
Phần lớn dữ liệu là các hệ số gần như bằng 0, và nén bằng cách loại bỏ các giá trị 0 này
Mấu chốt là mã hóa hiệu quả vị trí của các phần khác 0, mà thường những giá trị này lại có xu hướng gom cụm nên các thuật toán tận dụng đặc tính đó rất nhiều
Đây là đặc tính hoàn toàn trái ngược với các hàm băm dùng trong Bloom filter
Tôi nhớ kiểu này cuối cùng đụng phải giới hạn vì cả bản thân phép biến đổi lẫn việc nén hệ số đều kém về tính liên hệ không gian và chậm
Tôi muốn biết Bloom filter có lợi thế gì hơn so với hash table
Rất nhiều phần của nén video xoay quanh “chuyển động”
Tôi thắc mắc khi có kiểu như camera pan, cùng một pixel bị dịch sang trái 2 pixel thì xử lý thế nào
Nếu chỉ lưu delta thay đổi giữa các frame thì mọi pixel không đổi đều là 0
Nén các chuỗi 0 liên tiếp là phần dễ nhất trong nén mất dữ liệu, nhưng cách dùng Bloom filter thì lại có false positive
Có vẻ Bloom filter có thể dùng như một chiến lược con trong một bộ nén tổ hợp, và trộn nhiều phương pháp sẽ tốt hơn, nhưng trung bình thì tôi không nghĩ Bloom filter sẽ cải thiện hiệu năng quá nhiều so với các cách sẵn có
Tôi nghĩ có lý do khiến cách này hoạt động tốt với video kiểu YouTube, tức video đã qua một vòng nén-giải nén
Với đầu vào raw, giả định rằng phần lớn pixel gần như không đổi giữa các frame liên tiếp có thể bị phá vỡ
Nếu là cảnh rất sạch, ít nhiễu, sáng rõ thì có thể áp dụng được, nhưng tín hiệu thông thường có khá nhiều nhiễu vượt quá 1 LSB nên các bit thấp sẽ thay đổi thường xuyên
Sau khi qua quá trình nén-giải nén thì nhiễu giảm đi, nên giả định đó mới trở nên đúng hơn
Thực tế thì cách này cũng không phải lossless
Trong mã video_delta_compress.py, nếu mức thay đổi trung bình của r,g,b nhỏ hơn 10 thì sẽ không lưu thay đổi
Ví dụ kể cả khi đổi từ pure blue(#00ff00) sang pure red(#ff0000) thì vẫn có thể bị xử lý như vậy, dẫn tới cả hai frame đều được khôi phục thành pure blue
Cũng giống như việc người ta không dùng PNG để chụp ảnh, video quay thực tế hiếm khi dùng codec lossless
Video lossless phù hợp hơn với nội dung số như quay màn hình
Trong các trường hợp này, số pixel thay đổi giữa các frame ít hơn nên giả định của phương pháp này hợp lý hơn
Trong mã thì nếu tỷ lệ dưới 32.4% sẽ dùng chiến lược chỉ lưu vị trí các bit 1
Nên tôi tự hỏi liệu ngay cả khi các bit thấp thay đổi thường xuyên, nếu các bit cao thay đổi đủ ít thì cách này vẫn có thể hoạt động được không?
Nói chung hầu như không ai dùng video raw
Điện thoại và máy ảnh mặc định cũng lưu bằng MP4, AV1 v.v.
Xét tới kích thước file và chi phí xử lý, tôi nghĩ có nhiều người thậm chí còn không biết đến sự tồn tại của các định dạng raw chưa qua xử lý
Vậy nên cách hiện tại có vẻ phù hợp cho hoạt hình
Theo biểu đồ liên quan compression_comparison.png, có phải phương pháp nén mới này lúc nào cũng kém hơn GZIP không?
Nhưng tôi không tìm thấy số liệu hiệu năng
Có nhắc đến insight then chốt trong bài là: “chuỗi nhị phân có mật độ số 1 đủ thấp thì chỉ cần lưu vị trí của các số 1 cũng có thể nén hiệu quả hơn dữ liệu gốc”
JPEG, MPEG v.v. vốn dĩ sắp xếp lại bài toán sao cho xuất hiện nhiều dải 0 dài, và cách quét khối DCT chính là đổi mới rất quan trọng trong kiểu nén video này
DCT và biến đổi màu sắc chuyển chi tiết nhỏ thành thành phần tần số cao, còn nội dung chính thành tần số thấp
Việc nén diễn ra theo kiểu chỉ loại bỏ các thành phần tần số cao
JPEG còn tối ưu kích thước bằng Huffman table
Thực ra không có nhiều kỹ thuật đặc biệt chỉ để gom các số 0 lại, và việc gom 0 cũng không làm hiệu quả nén tăng mạnh đến vậy
Đồng ý
Vấn đề lớn nhất trong cách tiếp cận của OP là chủ động vứt bỏ tính liên hệ không gian của các thay đổi pixel vốn rất phổ biến trong video thông thường
Thậm chí đây không hẳn là thứ dành riêng cho frame video, mà giống một dạng tổng quát của nén sai khác giữa các chuỗi bit có cùng độ dài
Nó chỉ hiệu quả khi dữ liệu đầu vào có tính dự đoán được, tức có cấu trúc ít ngẫu nhiên, nhưng ngay cả loại dữ liệu đó cũng sẽ bị trộn lẫn thông tin sau khi đi qua hàm băm
Đặc biệt, hash mang tính mật mã sẽ làm đầu ra trở nên hoàn toàn ngẫu nhiên nên rất bất lợi cho nén
Xin chào HN, tôi là tác giả
Sau khi nhận phản hồi, tôi đang tiến hành kiểm thử nghiêm ngặt hơn với trọng tâm là video raw và video có nhiễu
Vẫn còn ở giai đoạn đầu, nhưng trên video raw tôi đang thấy kết quả khá ổn (dù có caveat)
So sánh với codec tiêu chuẩn
Giới hạn hiện tại và công việc sắp tới
Việc xử lý màu hiện chưa lossless hoàn toàn ở mức bit, và trong quá trình chuyển đổi YUV-BGR có sai số dấu phẩy động (chênh lệch pixel trung bình ~4.7), thêm vào đó còn mất độ chính xác khi xử lý kênh BGR sau chuyển đổi
Kế hoạch tiếp theo
Tôi muốn thử chứng minh rằng nó lossless hoàn hảo về mặt toán học
Tôi cũng đang suy nghĩ về việc áp dụng ý tưởng lossless compression này và Rational Bloom Filter sang các lĩnh vực khác ngoài video
Tôi thấy bối rối với dòng mã trong video_delta_compress.py
Vì đoạn này nên có vẻ như những thay đổi từ #ffffff sang #fffffa, hoặc từ #ff0000 sang #00ff00, đều sẽ bị bỏ qua tùy theo ngưỡng
Có thể là tôi hiểu sai vai trò của dòng mã này, nhưng trông như các thay đổi pixel bằng 0 sẽ hoàn toàn không được ghi vào Bloom filter
Có giới thiệu cách tính tỷ lệ nén, nhưng tôi tò mò liệu có ví dụ về tỷ lệ nén tệ nhất/trung bình/tốt nhất hay không
(sửa: tôi thấy có ví dụ ảnh trong repo rồi, nên ý tôi là sẽ tốt hơn nếu đưa vào README)
Repo hiện khá bừa bộn, nhưng trong code cũng có phần tạo biểu đồ và các thứ tương tự
Tôi dự định sẽ làm bài bản hơn với kiểm thử phù hợp và tổng hợp kết quả cho gọn gàng
Hiện tại vẫn là một WIP khá lộn xộn
Các codec như H.264 thực ra cũng có thể chạy ở chế độ lossless, dù ít dùng nhưng vẫn làm được
Tôi từng chạy chế độ lossless có dùng tăng tốc phần cứng NVENC
Nhưng phía phát lại khá vất vả, tôi nhớ là chỉ chạy được bằng ffplay, còn ngoài ra gần như không hoạt động
Ý tưởng hay, nhưng tôi nghĩ với chuỗi nhị phân thưa thì các phương pháp nén truyền thống hiện có có thể vẫn tốt hơn
Nhìn vào repo thì có vẻ tỷ lệ nén được tính bằng số lượng sai khác pixel đã bị loại bỏ trong phần sai khác
Điều này thú vị, nhưng điều thực sự quan trọng hơn là so sánh trực tiếp kích thước byte trung bình của từng frame với video nén kiểu YouTube
Nếu không có điều đó thì khó biết liệu cách hiện tại có thực sự cải thiện hiệu năng hay không
Nếu thuật toán này là nén mất dữ liệu thì vì nó đẩy mọi khác biệt nhỏ về 0, so với các phương pháp nén mất dữ liệu sẽ phù hợp hơn nhiều