Thuật toán tô màu cải tiến trong đồ họa máy tính

Bài toán tô màu một vùng trong kỹ thuật đồ họa hay bài toán tìm một vùng liên thông thỏa mãn điều kiện liền kề trong xử lý ảnh đã được nghiên cứu từ lâu; những đề xuất điển hình là giải thuật tô màu dựa trên đường biên, giải thuật tô màu dựa trên dòng quét. Bài báo này đề xuất một thuật toán cho bài toán nêu trên với một số cải tiến nhằm khắc phục những hạn chế của những đề xuất trước đây, nâng cao hiệu quả thuật toán. Kết quả thử nghiệm cho thấy thuật toán được đề xuất sử dụng ít bộ nhớ, tốc độ xử lý nhanh hơn từ 3 đến 5 lần thuật toán tô màu dựa trên đường biên.

1. Giới thiệu

Bài toán tô màu một vùng: Vùng A được xác định bởi đường biên có màu B, xuất phát từ điểm p có tọa độ (x,y) nằm trong A (hình 1), hãy tô A với màu C

vùng cần tô A
Hình 1 – Vùng cần tô A và điểm bắt đầu p

Bài toán tô màu một vùng giới hạn bởi tập các điểm “biên”, hay bài toán tìm vùng liên thông với điều kiện liền kề được xác định trước giữa các điểm ảnh gần nhau (hình 2) đã được biết đến từ lâu và đã có nhiều thuật toán được đề xuất, hai dạng điển hình là thuật toán tô màu dựa theo đường biên và thuật toán tô màu dựa theo dòng quét. Thuật toán tô màu dựa theo đường biên thể hiện cách giải quyết vấn đề khá tự nhiên và dễ hiểu, tuy nhiên một trong những yếu điểm lớn nhất của thuật toán này là sử dụng nhiều bộ nhớ, đặc biệt là khi cài đặt theo giải thuật đệ qui. Thuật toán quét dòng không sử dụng nhiều bộ nhớ, tuy nhiên biên của vùng cần tô phải được mô tả dạng danh sách cạnh, điều này là tương đối phức tạp khi xử lý đối tượng trên ảnh bitmap.

vùng liên thông D
Hình 2 – Vùng liên thông D là phần não bị chấn thương qua ảnh chụp CT

2. Thuật toán

Thông tin vào: Vùng A được bao bởi đường biên kín có màu B;
p1(x, y) – Tọa độ điểm nhân (seed point) đầu tiên, nằm trong A;
C là màu cần tô.
w là độ rộng khung ảnh chứa A.
Kết quả ra: Vùng A được tô với màu C.
Kí hiệu P là tập các điểm nhân; khi khởi tạo P nhận một phần tử là p1, và các điểm nhân khác được thêm vào trong tiến trình thực hiện thuật toán.
Thuật toán AreaFilling2 (AF2)

Trong đó MAU(p) là hàm cho phép xác định màu của điểm ảnh p.
Một số tính chất
Tính xác định: Thuật toán AF2 như mô tả ở trên đảm bảo sự rõ ràng, có thể dễ dàng chuyển thành chương trình trên máy tính.
Tính hữu hạn: Vùng A bị giới hạn bởi biên kín; số điểm cần xét – tương ứng với 1 đoạn thẳng được tô ở mỗi bước là hữu hạn, độ dài các đoạn cần tô là hữu hạn; do vậy thuật toán luôn luôn dừng sau hữu hạn bước.
Tính đúng: Thuật toán AF2 cho kết quả đúng, đảm bảo tô kín vùng A với hình dạng bất kỳ.
Tính phổ dụng: Lớp bài toán tô màu và tìm vùng liên thông là một lớp bài toán quan trọng trong nhiều lĩnh vực như xử lý ảnh, kỹ thuật đồ họa, mô phỏng …
Độ phức tạp tính toán
Giả sử A là một vùng có biên kín và lồi. Hình chữ nhật có các cạnh song song với các trục tọa độ nhỏ nhất chứa A có chiều rộng là W và chiều cao H như hình 3.
Từ mô tả thuật toán ta thấy, trường hợp xấu nhất, số vòng lặp theo pha tiến và pha lùi bằng W. Khi A lồi, mỗi bước 2 (không tính bước 2 đầu tiên có 1 điểm nhân) có 4 điểm nhân (hình 3), tuy nhiên vì các điểm (1) và (3), (2) và (4) có cùng tọa độ y; thêm nữa (1) và (3), (2) và (4) cùng nằn trên 1 đoạn cần tô nên thực chất ở bước 2 chỉ có nhiều nhất 2 dòng được tô màu. Theo thuật toán ta có số lần lặp của bước 2 bằng H. Như vậy, số “phép tính” tối đa của thuật toán bằng WxH.


vùng A lồi
Hình 3 – Vùng A lồi và các điểm nhân

Trường hợp A lõm (hình 4), số phép tính tối đa của thuật toán là WxH. Số điểm nhân tối đa phải lưu trữ ở bước 2 bằng hai lần tổng số lớn nhất các đoạn có thể tạo ra bởi 2 đường thẳng nằm ngang và A.


vùng A lõm
Hình 4 – Vùng A lõm

Như vậy độ phức tạp tính toán được đánh giá là O(n), n= WxH; bộ nhớ cần dùng cỡ 2xK, K là số đoạn lớn nhất có thể tạo ra bởi 2 đường nằm ngang và A, có thể thấy K nhỏ hơn rất nhiều so với W.

3. Kết luận

Thuật toán được đề xuất ở đây cho phép giải bài toán tô màu một vùng với biên là tập điểm ảnh có màu phân biệt; khắc phục được hạn chế của những đề xuất trước đây như giới hạn diện tích của vùng, biên phải được mô tả dạng danh sách cạnh; thuật toán được mô tả dễ dàng chuyển thành chương trình, đảm bảo tính dừng, tính đúng. Thuật toán có thể được áp dụng để giải bài toán xác định một miền liên thông với quan hệ liền kề được xác định trước từ điểm nhân ban đầu.