Thuật toán Zhang-Suen

Một thuật toán làm mảnh dường như là công cụ cho mọi nguời, đó là thuật

cơ sở cho việc so sánh các thuật toán làm mảnh trong nhiều năm, bởi tính ưu việt của thuật toán Zhang-Suen là một thuật toán nhanh, đơn giản khi thực hiện.

Thuật toán Zhang-Suen là một phương pháp song song thuộc lớp các thuật toán làm mảnh song song, có nghĩa là giá trị mới cho bất kỳ điểm ảnh nào có thể được tính toán chỉ dùng các giá trị đã biết từ trong vòng lặp ngay trước đó mà không cần quan tâm đến các giá trị ở các vòng lặp trước nữa.

Do tính chất đó của thuật toán, nếu máy tính xử lý song song có một CPU xử lý cho mỗi điểm ảnh đã được cung cấp trước, nó có thể xác định toàn bộ quá trình lặp tiếp theo một cách đồng thời. Vì hầu hết chúng ta không có một máy tính có kích thước lớn như vậy và do tính chất song song của thuật toán không phải là bắt buộc, do dó chúng ta chỉ xem xét phiên bản của một chương trình mà nó chỉ dùng 1 CPU.

Thuật toán bị bẻ gãy trong hai vòng lặp con, ví dụ thay vì 4 vòng lặp con của thuật toán Stentiford. Trong một vòng lặp con một điểm ảnh I(i,j) được xóa (hay đánh dấu cho thao tác xóa bỏ), nếu 4 điều kiện sau được thỏa mãn:

Giá trị liên kết của nó là 1.

Nó có 2 điểm láng giềng đen nhỏ nhất và không lớn hơn 6.

Một trong các điểm đen nhỏ nhất: I(i, j+1), I(i-1, j) và I(i, j-1) là điểm nền (điểm ảnh màu trắng).

Một trong các điểm nhỏ nhất I(i-1, j), I(i+1, j) và I(i, j-1) là điểm ảnh nền.

Ở cuối vòng lặp con này tất cả các điểm đã đánh dấu được xóa bỏ.

Vòng lặp con tiếp theo sau làm tương tự ngoại trừ bước 3 và 4.

Một trong các điểm đen nhỏ nhất: I(i, j+1), I(i-1, j) và I(i, j-1) là điểm nền (điểm ảnh màu trắng).

Một trong các điểm nhỏ nhất I(i-1, j), I(i+1, j) và I(i, j-1) là điểm ảnh nền.

Quay trở lại, bất kỳ điểm ảnh nào đã đánh dấu lại tiếp tục được xóa bỏ.

Nếu ở cuối vòng lặp con không có điểm nào được xóa thì xương hoàn toàn được xác định và chương trình kết thúc.

Từ các kết quả thu được ta có một số nhận xét và đánh giá sau:

Xương dạng hình chữ T đặc biệt tốt.

Xương dạng hình chữ V không biểu thị dấu hiệu nào của phần đuôi.

Xương hình dạng chữ X vẫn còn thấy necking và xương dạng số 8 cũng vẫn còn thể hiện các đường gấp khúc.

Như vậy, thuật toán Zhang_Suen vẫn còn một số hạn chế khi xử lý các đối tượng dạng đặc biệt như dạng số 8, dạng chữ X,..., các xương kết quả vẫn còn các necking. Chúng ta cần nghiên cứu đưa ra các cải tiến cho thuật toán này nhằm khắc phục các hạn chế đó.

Một cải tiến của thuật toán đã được đề xuất bởi Holt (1987) mà nó nhanh hơn và không liên quan đến vòng lặp con.

Đầu tiên 2 vòng lặp con được viết như một biểu thức logic mà nó sử dụng 3x3 điểm láng giềng về các điểm ảnh quan tâm.

Vòng lặp con ở trên có thể được viết như sau:

V(c) ^ (~ edge(c) v (V(e) ^ V(s) ^ (V(n) v V(w))) (3. 1)

Đó là điều kiện dưới cho các điểm trung tâm C tồn tại trong vòng lặp con đầu tiên. Hàm V cho giá trị của điểm ảnh (1 = đúng, đối với điểm ảnh thuộc đối tượng, 0 = sai, đối với các điểm ảnh nền), và hàm cạnh là đúng nếu điểm trung tâm C nằm trên biên của đối tượng, sự tương xứng này có giữa 2 và 6 láng giềng và giá trị kết nối là 1. Các ký tự E, S, N và W tương ứng với các điểm ảnh theo một hướng từ điểm ảnh trung tâm C: E nghĩa là hướng đông (tương ứng với điểm ảnh I(i, j+1)), S nghĩa là hướng Nam (tương ứng với điểm ảnh I(i+1, j)),...

Vòng lặp con thứ 2 được viết như sau:

Holt đã kết hợp 2 biểu thức 3. 1 và 3. 2 với một điều kiện kết nối bảo toàn cần thiết cho việc thực hiện tính toán song song và đưa ra các biểu thức dưới đây cho các điểm ảnh còn lại như sau:

V(C) ^ (~edge (C) v (edge (E) ^ V(N) ^ V(S)) v (edge(S) ^ V(W) ^ V (E)) v (edge(E) ^ edge (SE) ^ edge(S)) (3. 3)

Biểu thức này không phải là một sự thuyết phục khi nó được đưa ra các hàm đơn giản là các giá trị điểm ảnh và về công bằng mà nói hàm cạnh phức tạp gần như hàm kết nối dùng trong thuật toán Stentiford. Kết qủa thu được từ thuật toán này là tốt nhất nhưng nó không xác định cho thuật toán Zhang_Suen chuẩn.

Tuy nhiên vẫn có thể được dùng đến.

Đôi lúc, khi quá trình làm mảnh hoàn thành vẫn có các điểm ảnh mà chúng có thể bị xóa bỏ. Chủ yếu là ở giữa các điểm ảnh có dạng hình bậc thang (staircase), một phần nửa các điểm ảnh trong hình bậc thang đó có thể được xóa bỏ, ngoại trừ sự giả mạo hình dạng của các đối tượng toàn diện. Về cơ bản điểm ảnh trung tâm của một trong các cửa sổ dưới đây có thể được xóa bỏ:

nh 3.4

Để tránh tạo ra một lỗ hổng mới, đơn giản chúng ta bổ xung thêm một điều kiện mà một trong các giá trị x = 0.

Đối với các cửa sổ có đường chéo hướng Bắc (2 cửa sổ đầu tiên) biểu thức 0 1 X X 1 0 0 X X X X 0

1 1 X X 1 1 X 1 1 1 1 X X X 0 0 X X X 1 0 0 1 X

V(C) ^ ~edge (N) ^ ( ( V(E) ^ ~ V(NE) ^ ~ V(SW) ^ ( ~V(W) v ~ V(S)) v V (W))^ ~ (V(NW) ^ ~ V (SE) ^ ( ~V(E) v ~ V(S)))))) (3. 4)

Qúa trình duyệt ảnh có đường chéo hướng Nam tương tự như vậy, nhưng với chuyển đổi Bắc và Nam. Không có ảnh nào trong các ảnh ví dụ từ trước tới giờ có số lượng hình dạng bậc thang đáng quan tâm. Phiên bản của xương đã làm mảnh dùng staircase_removal dường như trơn và đối xứng hơn các xương khác.

Các vấn đề cơ bản vẫn còn hiện diện trong thực tế phương pháp này không xử lý các tails tốt như phương pháp Zhang-Suen chuẩn và xương dạng chữ T cũng không tốt bằng.

Nếu tốc độ là vấn đề đơn giản, vấn đề gì là quan trọng thì việc cải tiến thuật toán Holt của Zhang_Seun là thuật toán tốt hơn các thuật toán đã thấy từ trước tới nay vì thuật toán này có tốc độ xử lý cao, xương kết quả tốt.

3.2.3 Thuật toán làm mảnh ảnh nhị phân theo phương pháp song song