chương 1 đã đề cập: rất nhiều loại hình công việc đếm trong thực tiễn phải dùng phương pháp đếm bằng xử lý ảnh. Đếm số đối tượng trong ảnh là một trong các công việc cơ bản của xử lý ảnh. Trong đó bài toán kinh điển đếm các đối tượng tách rời nhau được mô tả qua thuật toán sau: Thuật toán đếm kinh điển: Input: Ảnh số nhị phân. Output: Số đối tượng cần đếm trong ảnh Thực hiện với ảnh gốc I có kích thước MxN 1.
Tạo các điểm ảnh biên của ảnh I = 0; // sau khi tạo có ảnh mới I1 có kích thước (M+2) x (N+2) Số đối tượng = 0; Hình 2.1 Tạo các điểm ảnh biên cho ảnh I 2.1 Bắt đầu từ điểm bất kỳ (chẳng hạn điểm top-left) Xem điểm ảnh đó có phải điểm đen không? + Nếu điểm ảnh là điểm trắng không làm gì + Nếu điểm ảnh đó là điểm đen thì: gán nhãn cho điểm đó là "2" rồi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 + Kiểm tra xem 8 điểm ảnh xung quanh có là điểm đen không? Nếu điểm nào trong số 8 điểm đó là đen thì gán chúng là "2". Nếu không thì chúng vẫn bằng "0". Cập nhật vị trí các điểm "2". Cập nhật các vị trí đã kiểm tra (Đánh số từ "2" để không lẫn với giá trị "1").2 Loại trừ điểm đen đầu tiên (điểm "2" đầu tiên).
làm tiếp với từng điểm "2" lân cận với bước 2.1 để tìm các điểm "2" mới tức là tìm các điểm ảnh mới liên kết với các điểm "2" cũ.3 Khi không còn có điểm "2" mới nào thì: + Số đối tượng = Số đối tượng + 1; + Tìm trong số tất cả các điểm ảnh còn lại chưa kiểm tra có điểm đen nào thì lại thực hiện 2. Tìm đến điểm ảnh cuối cùng của ảnh thì sẽ tìm được số đối tượng trong ảnh. Số điểm ảnh có cùng nhãn "2", "3",. sẽ là diện tích (độ lớn) của mỗi đối tượng.
a) Các nhóm điểm đen được gán nhãn (hình b) Hình 2.2 Minh họa phương pháp đếm kinh điển Trên hình 2.2 các nhãn được đánh số từ 2 đến 7 và số đối tượng N là số thứ tự nhãn lớn nhất -1 tức là N=7-1=6.2 Đếm sai khi có các đối tượng chạm nhau Theo cách thức của thuật toán đếm kinh điển chúng ta thấy dựa trên sự gán nhãn các nhóm điểm ảnh liên thông nhau. Mỗi nhóm điểm ảnh là một đối tượng. Như vậy khi có hai đối tượng chạm nhau trong thực tế thì ảnh của chúng cũng có các điểm liên thông như là cùng trong một đối tượng. Áp dụng thuật toán đếm kinh LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 điển trong trường hợp này mà không có xử lý tách hai (hoặc nhiều đối tượng dính nhau ra) sẽ cho kết quả đếm sai.3 a) ảnh nguyên bản b) ảnh nhị phân Trên hình 2.3 nguyên bản có 5 đồng xu trong đó có hai nhóm đồng xu bị chồng lên nhau.
Trên ảnh nhị phân khi đếm dùng thuật toán đếm kinh điển chúng ta chỉ đếm được 3 nhóm đối tượng (mà lẽ ra phải là 5).2 Đếm đối tượng có ảnh dính nhau dùng hình thái học kinh điển 2.1 Hình thái học kinh điển Thuật ngữ thực hiện phép toán hình thái học bao gồm một lớp các thuật toán xử lý ảnh biến đổi ảnh khi thực hiện biến đổi ảnh qua phần tử cấu trúc. Hình thái học có thể được thực hiện với ảnh nhị phân và cả ảnh đa cấp xám. Nó được rất hữu ích trong nhiều công việc xử lý ảnh như tìm xương ảnh, tìm biên, phục hồi và phân tích kết cấu ảnh. Hai phép toán hình thái học cơ bản là dilation và erotion.
Với ảnh nhị phân: Phép biến đổi erosion & dilation ảnh nhị phân thường được dùng để biến đổi ảnh như sau: Hình 2.4 Thực hiện phép co và phép dãn nở ảnh nhị phân Ta có một ảnh P như hình 2.4 Thực hiện phép erosion và dilation ảnh bằng cách tuỳ theo việc thực hiện phép xử lý nào mà tạo ra các tập phần tử có cấu trúc LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 (mặt nạ) tương ứng, sau đó rê mặt nạ đi khắp ảnh và tính giá trị điểm ảnh bởi các điểm lân cận với motip của mặt nạ. Các phép thực hiện có thể là hội, tuyển hoặc liên hợp. Dilation: Rê mặt nạ S đi khắp ảnh và tại mỗi điểm kiểm tra nếu bít có giá trị 1 thì thực hiện phép tuyển với bit mặt nạ quanh điểm ảnh đó. Kết quả được D(P,S).
Erosion: Rê mặt nạ S đi khắp ảnh và tại mỗi điểm kiểm tra nếu bít có giá trị 1 thì thực hiện phép hội với bit mặt nạ quanh điểm ảnh đó. Kết quả được E(P,S); a) b) c) Hình 2.5 a) Ảnh nguyên bản b) Sau khi co ảnh c) Sau khi dãn ảnh Khi kết hợp phép dãn ảnh và phép co ta có thêm các phép hình thái học, toán tử đóng (closing) và toán tử mở (opening) Closing: Toán tử đóng của một ảnh A với một phần tử cấu trúc B được thực hiện theo luật sau: AB=(AB)ΘB (2.1) trong đó và Θ ký hiệu của phép dilation và erosion. Thuộc tính: Tính chắc chắn (Imdepotence): (AB)B=AB Tính tăng: Nếu A C thì AB CB Tính mở rộng: A AB Closing thay đổi bất biến. Opening: toán tử mở của một ảnh A với một phần tử cấu trúc B được thực hiện theo luật sau: AB=(AΘB)B (2.2) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 trong đó và Θ ký hiệu của phép dilation và erosion.
Thuộc tính: Tính chắc chắn (Imdepotence): (AB)B=AB Tính tăng: Nếu A C thì AB CB Chống mở rộng: AB A Toán tử mở thay đổi bất biến. Toán tử mở và toán tử đóng đáp ứng tính nhị nguyên: AB=(AcBs)c. Trong xử lý ảnh closing được dùng để loại bỏ các lỗ nhỏ và opening được dùng để loại các đối tượng nhỏ của ảnh. Các kỹ thuật này cũng còn được dùng để tìm các hình dạng đặc tả trong ảnh.6 Ảnh nhị phân nguyên bản và sau khi thực hiện các phép hình thái học Hình thái học với ảnh đa cấp xám: Phép co với ảnh xám được thực hiện bởi bộ lọc cực tiểu còn phép dãn nở thì được thực hiện bởi bộ lọc cực đại.
Trong một bộ lọc cực tiểu 3 x 3 = pixel trung tâm thì được thay thế bởi giá trị nhỏ nhất của các pixel trong cửa sổ. Trong một bộ lọc cực đại pixel trung tâm thì được thay thế bởi giá trị lớn nhất của các pixel trong cửa sổ. Sự thực hiện của các bộ lọc cực tiểu và bộ lọc cực đại giống như sự thực hiện của bộ lọc median. Phép hình thái học dãn nở của ảnh xám LUAN VAN CHAT LUONG download : add luanvanchat@agmail.7 Hình thái học trên ảnh xám Hình 2.8 Thực hiện hình thái học trên ảnh xám.2 Hạn chế khi đếm các đối tượng dính nhau Khi thực hiện hình thái học để tách các đối tượng dính nhau ra thành đối tượng độc lập để đếm có thể xảy ra các trường hợp [4]: Tách được các đối tượng ra đúng đắn và đếm chính xác LUAN VAN CHAT LUONG download : add luanvanchat@agmail.9 Dùng phép co để tách các đối tượng Tách đối tượng không hết vẫn còn có đối tượng dính nhau nên đếm sai Hình 2.10 Do phép co chưa đủ số lần thực hiện nên vẫn còn các nhóm đối tượng dính nhau Thực hiện hình thái học với số lần lặp lớn quá mức dẫn đến đối tượng bị biến mất.
Khi đó cũng bị đếm sai.3 Phối hợp biến đổi Watershed và biến đổi khoảng cách.1 Biến đổi khoảng cách (DT - Distance Transform) Biến đổi khoảng cách là một toán tử thường áp dụng cho hình ảnh nhị phân (cũng có áp dụng cả với ảnh xám). Kết quả của phép biến đổi là một hình ảnh LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 18 Graylevel trông tương tự như hình ảnh đầu vào, ngoại trừ cường độ mức xám của các điểm gần các vùng biên được thay đổi. Một số ví dụ trong bảng 2.1 Một số ví dụ biến đổi khoảng cách Ảnh sau biến đổi Ảnh nguyên bản khoảng cách Công thức biến đổi khoảng cách Công thức biến đổi khoảng cách: Một tập các điểm P, số đo khoảng cách DT(P)[x] = min y ∈ P dist(x, y). Đối với mỗi vị trí x khoảng cách đến điểm y gần nhất trong P LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 19 - Có thể nghĩ về “hình nón” gốc ở mỗi y ∈ P – và cực tiểu (min) trên tất cả các hình nón (đường bao thấp hơn Ba loại biến đổi khoảng cách dựa trên ba kiểu khoảng cách được sử dụng Khoảng cách Euclidean (L2 norm) sqrt(( x1-y1)2 + (x2-y2)2 + … ) Khoảng cách Mahattan (city block distance - L1 norm) |x1- y1| + |x2-y2| + …ƒ Khoảng cách Chebyshev (L norm) max(|x1 - y1|, |x2 - y2|, …) Hình 2.11 Tác dụng của ba kiểu biến đổi khoảng cách a) ảnh gốc b) dùng khoảng cách Ơ clit c) Dùng khoảng cách Mahatan d) dùng khoảng cách Chessboard 2.2 Phân vùng Watershed (WS-Watershed Segmentation) Khái niệm) Hình 2.12 Nguyên lý biến đổi lưu vực sông (watershed transform) nơi các giá trị cường độ xác định đồi và lưu vực.
Đối với mục đích phân vùng, các lưu vực có thể bị ngập để kết hợp các vùng tương ứng. Thuật toán Watershed [5], [6] cho phép người dùng đánh dấu những vùng hình ảnh chứa đối tượng, nền và cả những vùng không chắc chắn. Sau khi thuật toán kết thúc, những vùng không chắc chắn sẽ được gắn nhãn tiền cảnh hoặc nền, các đường ranh giới giữa các vùng cũng sẽ được phát hiện. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 Đầu tiên, thuật toán Watershed xem bức ảnh chứa “Gradient of the Intensity” như là một tấm bản đồ địa hình, trong đó các vùng sáng là các ngọn núi, còn các vùng tối là các thung lũng, hình 2.13 Địa hình khi chưa bị ngập nước Giả sử có một trận mưa cực lớn xuất hiện, ban đầu nước sẽ nhấn chìm toàn bộ các thung lũng, sau đó mực nước tăng dần để nhấn chìm từng ngọn núi, lúc này nước ở trong các thung lũng sẽ gặp nhau, vị trí mà chúng gặp nhau chính là biến đổi watershed (hình 2.15) và đó cũng chính là ranh giới giữa các vùng mà chúng ta cần phân tách.
Nước lũ ở từng thung lũng được tô màu khác nhau để dễ hình dung.14 Bắt đầu cho ngập các thung lũng Hình 2.15 Vị trí của Watershed Hình 2.16 Xây dựng bức tường ngăn cách tại vị trí Watershed LUAN VAN CHAT LUONG download : add luanvanchat@agmail.