Tạo ảnh dithering bằng phương pháp khuyếch tán sai số lượng tử hóa

Computer Vision

11

Ngoc Dao viết ngày 20/03/2016

Ảnh dithering là ảnh trong đó chỉ sử dụng vài ba màu, nhưng lại có thể tạo ảo giác về các màu trung gian giữa các màu được sử dụng. Kĩ thuật này thường được sử dụng để in báo vì sử dụng càng ít màu thì chi phí càng giảm.

Ở dưới là ví dụ dùng 4 màu. Ảnh đầu là ảnh gốc, ảnh thứ hai là ảnh dithering chưa được khuyếch tán sai số, ảnh thứ ba được khuyếch tán sai số, vẫn chỉ dùng 4 màu nhưng lại tạo được cảm giác về độ xám biến thiên liên tục. Để ảnh càng xa mắt, thì hiệu ứng về độ xám càng mạnh.

Thay vì dùng 4 cấp độ sáng, nếu dùng 4 màu sắc khác nhau (ví dụ dùng HSV để tính ra 4 màu đặc trưng nhất trong ảnh gốc), ảnh sẽ rực rỡ hơn, không phải dạng vừa đâu.

Có kĩ thuật liên quan gọi là halftone, thường để tạo poster vì trông nghệ thuật hơn.

Giải thuật Floyd-Steinberg

Có nhiều giải thuật, bài viết này trình bày giải thuật Floyd-Steinberg. Lí do của việc chọn giải thuật này là nó hàm chứa khái niệm khuyếch tán sai số lượng tử hoá rất sâu sắc.

Sai số lượng tử hóa

Quá trình biến đổi từ tín hiệu tương tự sang tín hiệu số gọi là lượng tử hóa. Quá trình này không thể tránh sai số. Tín tương tự là liên tục nên độ chính xác vô hạn, trong khi độ chính xác của tín hiệu số phụ thuộc vào số bit dùng để mã hóa, mà số này có giới hạn. Đối với mỗi kênh ảnh (ví dụ R hoặc G hoặc B), thường người ta dùng 8 bit (256 mức độ).

Như vậy, tín hiệu số chỉ là tín hiệu xấp xỉ của tín hiệu tương tự ban đầu. Hiệu của giá trị của tín hiệu tương tự ban đầu và giá trị của tín hiệu số được xấp xỉ được gọi là sai số lượng tử hóa.

Khuyếch tán sai số lượng tử hóa

Floyd là nhà khoa học máy tính cực kì nổi tiếng với giải thuật Floyd để tìm tất cả đường đi ngắn nhất trong đồ thị. Năm 1978 ông nhận giải Turing, được coi là giải Nobel của khoa học máy tính.

Năm 1976, Floyd và Steinberg công bố giải thuật Floyd-Steinberg dithering. Mấu chốt của giải thuật này là xử lí các điểm ảnh từ trái sang phải, từ trên xuống dưới, khuyếch tán sai số lượng tử hoá của điểm đang được xử lí sang 4 điểm xung quanh chưa được xử lí (1 điểm bên phải và 3 điểm ở hàng tiếp theo). Do đó, tính trung bình trên cả tấm ảnh thu được, thì sai số gần như bằng 0.

Demo bằng JavaScript