QOI - nén ảnh không mất dữ liệu O(n)

<p>&quot;Quite OK Image&quot; <br /> - Thực hiện nén RGB/RGBA với kích thước tương đương PNG<br /> → Nén nhanh hơn 20x-50x và giải nén nhanh hơn 3~4x <br /> → Mã nguồn mở C dạng tệp header đơn dài 300 dòng <br /> → Triển khai đơn giản, đơn luồng, không sử dụng SIMD <br /> - Chi tiết kỹ thuật <br /> → Mã hóa/giải mã ảnh theo một lượt duy nhất <br /> → Mỗi pixel chỉ được xử lý một lần và mỗi pixel được mã hóa theo một trong 4 cách <br /> ⇨ Nếu giống pixel ngay trước đó thì tăng run-length của pixel trước, nếu khác thì đóng gói pixel mới theo một trong 3 cách bên dưới <br /> ⇨ Nếu giống một pixel đã xử lý trước đó thì dùng chỉ mục của pixel đó. Để làm vậy, nó giữ một mảng cho 64 pixel gần nhất<br /> ⇨ Nếu khác biệt so với pixel trước không nhiều thì lưu giá trị chênh lệch RGBA đó <br /> ⇨ Nếu 3 cách trên đều không phù hợp thì lưu giá trị RGBA của pixel. Tuy nhiên chỉ lưu phần khác với pixel trước đó </p>

[lifthrasiir]

<p>Nói hơi cường điệu một chút, QOI về cơ bản là lấy PNG, bỏ `zlib`, chỉ giữ lại phần lọc rồi cải tiến nó.<br /> <br /> Thuật toán nén `zlib`/`gzip`/`DEFLATE` mà PNG cũng dùng tuy được sử dụng rất rộng rãi, nhưng vì đã quá cũ nên hiệu quả cũng có phần hạn chế; hơn nữa, các thuật toán họ LZ77 như `zlib` dựa trên giả định cơ bản rằng “trong các byte gần đây có nhiều trường hợp một chuỗi byte liên tiếp giống nhau xuất hiện lặp lại” (ví dụ: nếu đầu vào là "to be or not to be" thì có thể tận dụng việc phần "to be" xuất hiện hai lần). Nhưng ảnh là loại dữ liệu mà giả định này không thực sự phát huy tốt, nên PNG trên thực tế chỉ dùng `zlib` như mã hóa entropy (cách tiếp cận nén dựa trên xác suất byte tiếp theo xuất hiện mà không có thêm ngữ cảnh nào khác), đồng thời dùng bước tiền xử lý là một cơ chế lọc đơn giản để cố gắng làm cho dữ liệu đưa vào `zlib` phù hợp hơn với giả định đó; tuy nhiên thực ra cũng không thể nói là quá hiệu quả.<br /> <br /> Trong các định dạng ảnh nén không mất dữ liệu hiện đại, có hai hướng cải thiện lớn cho vấn đề này: một là cải tiến dự đoán pixel tương ứng với phần lọc của PNG (chẳng hạn tăng mạnh số loại lọc, hoặc áp dụng các kiểu lọc khác nhau cho những vùng khác nhau của ảnh), hai là cải tiến phần mã hóa entropy tương ứng với `zlib` của PNG. Cách tiếp cận của QOI cũng tương tự, nhưng để giữ sự đơn giản, nó có hai đặc điểm nổi bật: hoàn toàn không dùng pixel phía trên vị trí hiện tại trong bước dự đoán pixel, và từ bỏ mã hóa entropy để chuẩn bị sẵn nhiều kiểu mã hóa sai khác (delta) dựa trên kinh nghiệm. Đặc biệt, do đặc điểm thứ nhất, xét riêng về tỷ lệ nén thì QOI thường kém hơn cả PNG, bất kể hiệu năng nén/giải nén; tuy vậy có vẻ vẫn có thể cải thiện điều này nếu chấp nhận hy sinh đôi chút tính đơn giản.</p>

[xguru]

<p>Ồ, cảm ơn bạn đã giải thích thêm. Thú vị thật.</p>

[xguru]

<p>Có lẽ khó có thể dùng nó để thay thế các định dạng khác, nhưng vì mã nguồn đơn giản và phần giải thích cách triển khai cũng được viết rất rõ nên có vẻ là một đoạn mã đọc khá thú vị.<br /> https://github.com/phoboslab/qoi/blob/master/qoi.h<br /> </p>