Xử lý ảnh bằng phương pháp Morphology

ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP. HỒ CHÍ MINH KHOA TOÁN – TIN HỌC PHƯƠNG PHÁP MORPHOLOGY Đề Tài Môn Xử Lý Ảnh Giáo Viên Hướng Dẫn: TS. Phạm Thế Bảo Nhóm Thực Hiện: Vũ Văn Trọng Nghĩa 0811098 Nguyễn Hồng Quy 0811137 Bùi Quang Vinh 0811198 Nguyễn Hoàng Quốc 0811300 Tp. Hồ Chí Minh, tháng 12 năm 2010 2 Lời Nói Đầu Nhóm làm đề tài chúng tôi xin mạn phép dành những dòng đầu tiên để tỏ lòng cảm ơn, cũng những sự kính trọng đối với thầy Phạm Thế Bảo, người đã dìu dắt nhóm chúng tôi những bước đi chập chững đầu tiên. “Chúng em cám ơn thầy và chúc thầy dồi dào sức khoẻ”. Đây là báo cáo của nhóm chúng tôi về phương pháp Morphology, chúng được chúng tôi trình bày trong 3 phần chính đó là: Cơ Sở Lý Thuyết, Các Công Cụ Bổ Sung, Trên Ảnh Xám. Cuối cùng, để minh hoạ cho việc sử dụng phương pháp này, chúng tôi có viết mã chương trình để chạy thử nghiệm. Chương trình này dung để đếm những đối tượng có hình tròn trong một bức ảnh trắng đen. Ở đây chúng tôi chỉ mới dừng lại ý tưởng thực hiện bài toán này và chứng minh cho người đọc thấy { tưởng có vẻ đúng. Chúng tôi xin dành bài báo cáo sau về bài toán này tường minh và hoàn thiên hơn. Song song bên cạnh cái làm được, chúng tôi cũng làm những thứ chưa được. Chúng tôi chưa tìm hiểu nhiều phương pháp mới hơn nhưng cùng cho ra kết quả như những phép toán trong phương pháp này. Tuy vậy, với những phần chúng tôi tìm hiểu và liên hệ ra ngoài, chúng tôi đã tích cực làm rõ và so sánh với phép toán trong phương pháp Morphology. Nhóm Làm Đề Tài 3 Mục Lục Chương 1: Khái Niệm Cơ Bản. ........................................................................................................................ 4 Lịch sử hình thành. [1] ................................................................................................................................ 4 Lý thuyết tập hợp được sử dụng. ............................................................................................................... 4 Phép toán Dilation và Erosion. ................................................................................................................... 6 Phép toán Opening và Closing. ................................................................................................................... 9 Phép toán . ................................................................................................................. 10 Chương 2: Các Công Cụ Bổ Sung. ................................................................................................................. 13 Trích biên (Boundary extraction). ............................................................................................................. 13 Tô miền (Region filling). ............................................................................................................................ 13 Trích các thành phần liên thông. .............................................................................................................. 14 Tìm bao lồi (Convex hull). ......................................................................................................................... 16 Làm mỏng (Thinning). ............................................................................................................................... 16 Làm dày (Thickening). ............................................................................................................................... 19 Lấy khung (Skeletons). .............................................................................................................................. 20 Cắt xén (Pruning). ..................................................................................................................................... 24 Chương 3: Phương Pháp Morphology Cho Ảnh Xám. .................................................................................. 27 Khái niệm về ảnh xám............................................................................................................................... 27 Phép Dilation cho ảnh xám. ...................................................................................................................... 27 Phép Erosion cho ảnh xám. ...................................................................................................................... 28 Phép Opening và Closing cho ảnh xám. .................................................................................................... 30 Một số ứng dụng của morphology trên ảnh xám. .................................................................................... 32 Chương 4: Ứng Dụng Chạy Thử .................................................................................................................... 41 Tài Liệu Tham Khảo ....................................................................................................................................... 44 4 Chương 1: Khái Niệm Cơ Bản. Lịch sử hình thành. [1] Khái niệm Morphology trong xử lý ảnh số khởi nguồn từ một ngành của sinh học, nghiên cứu về hình thể và cấu trúc của động thực vật. Đây là một công cụ giúp rút trích các thành phần trong ảnh nhị phân, biễu diễn và mô tả chúng dưới dạng các vùng hoặc dạng như các đường biên, xương và bao lồi. Kỹ thuật morphology cũng được áp dụng trên ảnh xám cho các công đoạn tiền/hậu xử lý ảnh (pre or post processing). Các phép toán đầu tiên trong Morphology được phát triển vào những năm 1964 bởi Georges Matheron (1930 - 2000) và Jean Serra (1940) tại trường đại học École des Mines de Paris, Pháp. Matheron là tiến sĩ hướng dẫn của Jean, họ cố gắng xác định số lượng đặc tính của khoáng sản thông qua “thin cross section” và công việc cho ra kết quả là một phương pháp tiếp cận mới, cũng như sự tiến bộ trong hình học tích phân và tô pô. Từ đó đến hết năm 1970, Morphology xử l{ cơ bản với các ảnh nhị phân, tạo ra các phép toán và kĩ thuật như: Hit-or-miss, Dilation, Erosion, Opening, Closing…. Từ giữa 1970 đến giữ 1980, Morphology xử lý thêm ảnh xám và có nhiều kết quả khả quan trong việc tạo ra các phép toán mới như Morphology Gradients… Lý thuyết tập hợp được sử dụng. Số hóa một ảnh từ không gian thực 2D là động tác lấy mẫu mặt phẳng 2D ấy trên một lưới 2 chiều, với tọa độ x và y lần lượt là các số nguyên trong tập . Như vậy ta có một ánh xạ hàm ảnh giữa giá trị độ sang của điểm ảnh và tọa độ . Nếu giá trị độ sáng của ảnh là số nguyên, ta có định nghĩa về một hàm ảnh với tọa độ và giá trị độ sáng đều nguyên. Cho A là 1 tập con trong . Nếu là phần tử của A thì ta viết ngược lại chúng ta viết là . Tập hợp mà không có phần tử nào là tập hợp rỗng kí hiệu . Hội cả 2 tập hơp A và B là tập hợp , tương tự hợp của A và B là tập . Hai tập hợp A, B rời nhau nếu như . Phần bù của tập hợp A là những phần tử không thuộc A kí hiệu bởi . Hiệu giữa tập hợp A và B là những phần tử thuộc A nhưng không thuộc B, kí hiệu . 5 Phản xạ của tập hợp B kí hiệu là . Tịnh tiến tập A theo điểm kí hiệu là . Bảng liệt kê các toán tử trong Matlab Toán Tử Biểu Thức Matlab A&B A|B -A A&~B Các toán tử logic trong ảnh nhị phân (NOT, AND, XOR, OR) Hình 1-1: minh họa các phép toán trên tập hợp. Hình 1-2: minh họa phép tịnh tiến và phản xạ 6 Hình 1-3: minh họa các phép toán luận lý Phép toán Dilation và Erosion. 1. Nhân tạo hình (Structuring Element). [2] Là một tập hợp nhỏ được dùng để dò tìm hay tương tác với hình được cho, theo ông Georges Matheron, đặc điểm đặc trưng của đối tượng dựa vào cách ta đoán hay nhìn nhận nó. Từ đó ta chọn nhân tạo ảnh tùy thuộc vào { đồ của những phép toán Morphology muốn đạt được. Có 2 yếu tố chính cần lưu tâm khi ta chọn nhân tạo ảnh: i. Hình dạng của nó: hình tròn, hình vuông… ii. Kích cỡ của nó: 3X3, 5X5 … Cứ mỗi nhân tạo ảnh, ta xác định một cái tâm (origin). Trong Matlab,chương trình giả định rằng điểm ở giữa là tâm. 2. Phép toán Dilation. Phép toán Dilation là thao tác giãn nỡ/phình to các đối tượng ảnh đơn sắc A và B là hai tập hợp con trong , thực hiện phép toán Dilation trong A theo B, kí hiệu là và được xác định như sau . Trong Matlab, ta có hàm Dilation như sau: . Ví dụ về cách sử dụng hàm . Hình 1-4: minh họa nhân tạo ảnh 7 chính là nhân tạo hình. Trong Matlab, chương trình cũng cung cấp cho ta nhiều nhân tạo hình khác nhau, để biết thêm chi tiết gõ . Trong thực tế, người ta chọn những nhân tạo ảnh sao cho , tức là sử dụng những nhân tạo ảnh có các phần tử trong nhân tạo ảnh đối xứng qua chính tâm của nó. Bên cạnh đó, với việc ta lê những cái tâm của nhân tạo ảnh đi khắp và tìm những điểm nào mà thì ta có thể hiểu như với là những khu vực mà thỏa . Có thể xem hình minh họa dưới đây: Hình 1-5: đối tượng cần phình A và nhân tạo ảnh B Hình 1-6: minh họa quét các khắp A 3. Phép toán Erosion. Phép toán Erosion là thao tác xói mòn/co hẹp các đối tượng ảnh đơn sắc. A và B là hai tập hợp con trong , thực hiện phép toán Erosion trong A theo B, kí hiệu là và được xác định như sau . Tương tự, trong Matlab ta cũng có hàm Erosion như sau: và cách sử dụng hàm này như sau: Hình 1-7: kết quả đạt được 8 Để minh họa cách thức phép toán hoạt động có thể xem hình phía dưới với và tương tự như ví dụ ở phép toán Dilation. 4. Nhận xét i. Hai thuật toán Erosion và Dilation có mối tương quan với nhau: Thật vậy ta có suy ra suy ra tức là hay ta có điều sau . Từ đó, ta kết luận: Mặc khác ta cũng có: Chọn ta có điều phải chứng minh. ii. Tính chất cần lưu { là khi ta chọn những mặt nạ khác nhau thì kết quả thu được cũng khác nhau. Hình 1-8: minh họa kết quả của phép toán Hình 1-9: sự tương quan giữa 2 phép toán 9 Hình 1-10: phép toán với 2 nhân tạo ảnh khác nhau Hình 1-11: phép toán với 2 nhân tạo ảnh khác nhau Phép toán Opening và Closing. 1. Phép toán Openning. Phép toán Opening của hình theo nhân tạo hình kí hiệu là: . Theo một định nghĩa khác tương đương dựa vào hình học ta có: . Tác dụng của phép toán Opening là loại bỏ những đối tượng không đủ lớn để chứa nhân tạo hình (góc), làm trơn biên, tách rời mấu liên kết với những đối tượng lớn và loại bỏ nhánh con. Trong Matlab hàm hỗ trợ phép toán này là . Một số tính chất đáng lưu tâm: i. ii. với thì iii. 2. Phép toán Closing. Phép toán Closing của hình theo nhân tạo hình kí hiệu là: . Hình 1-12 10 Tương tự trên về mặt hình học ta cũng có định nghĩa tương đương: Tác dụng của phép toàn này là làm trơn biên, nối liền những mẫu rời nhau, lắp đầy các lỗ nhỏ. Trong Matlab hàm để xử dụng là imclose. Ngoài ra ta còn có một số tính chất cần lưu tâm sau đây: i. ii. với thì iii. 3. Nhận xét. i. Có thể so sánh cảm giác ràng nếu như Opening làm trơn biên ở phía trong thì Closing làm trơn biên ở phía ngoài. ii. Giữa hai phép toán Opening và Closing có hai mối tương quan: . Thật vậy, ta có: Phép toán . 1. Giới thiệu. Phép toán là một trong những phép toán cơ bản nhất của Morphology được phát triển bởi chính 2 cha đẻ của Morphology là Matheron (1975) và Serra (1982). Khi mới được tạo ra, nó chỉ có thể xử dụng cho ảnh nhị phân, sau đó được phát triển thêm cho ảnh xám tuy nhiên điều này phức tạp. Thật vậy, chỉ có duy nhất một lý thuyết (theoretical framework) được phát triển cho ảnh xám bởi Naegel Hình 1-13: phép toán Hình 1-14: phép toán Closing 11 et al. (2007). Hiện nay, thuật toán này đã được phát triển để dùng cho hình đa biến ngẫu nhiên (multivariate images) [3]. 2. Vấn đề chính. Công dụng của là tìm vị trí của một vài hình thù (shapes) trong tập hợp của những hình thù (set of shapes) mà ta còn có thể gọi nó là “template matching”. Ta tổng quát hóa cho và đặt và thì công thức trên trở thành: . Do và còn do sự tương quan giữa 2 phép toán Opening, Closing nên ta cũng có điều sau đây: . Dựa vào định nghĩa của phép toán trên, ta lưu { trong việc chọn như sau: . Đồng thời, để hiểu rõ hơn về thuật toán này, chúng ta có thể tạm hiểu các thức hoạt động của nó là “kiểm tra xem có giống đối tượng cần tìm có giống không và kiểm tra luôn có không giống đối tượng tìm kiếm hay nói cách khác kiểm tra xem có giống phần bên ngoài của đối tượng không”. Để dễ hiểu hơn ta nhìn hình minh họa phía dưới. Hình 1-16: đang tìm vị trí qua 2 phép toán Erosion và Dilation Hình 1-15: minh họa ý tưởng 12 Hàm sử dụng phép toán trong Matlab là , để biết thêm chi tiết gõ lệnh . Hình 1-17: ảnh mẫu và kết quả 13 Chương 2: Các Công Cụ Bổ Sung. Trích biên (Boundary extraction). Biên là phần phân ra rạch ròi giữa những phần tử thuộc đối tượng và không thuộc đối tượng. Theo đó, { tưởng trích biên dễ dàng có được là thu nhỏ đối tượng một chút, sau đó lấy những phần từ nào thuộc vào đối tượng nhưng không thuộc vào phần đối tượng đã thu nhỏ. Thuật toán trích biên được xác định như sau: , trong đó là kí hiệu của biên đối tượng cần xét. Tô miền (Region filling). Phép toán này dùng để tô một miền A bị chận bởi . Thuật toán này bắt đầu từ một điểm cho trước và này nằm trong . Phép toán xác định qua: Và thuật toán này dừng nếu thỏa: . Nhận xét: do ta chỉ tô miền A bị chận bởi nên số lượng pixel trong miền tô hữu hạn là số . Mặc khác, ta cũng có do . Vì thế, ta có điều sau: Vậy nên giả sử với thì , thì và do miền tô bị chận cho nên , thuật toán tới đây dừng. Hình 2-1: bên trái là đối tượng, bên phải đường màu trắng là biên Hình 2-2: cách thức hoạt động 14 Trích các thành phần liên thông. Trích thành phần liên thông Thuật toán được xác định như sau: Tương tự như cách thức hoạt động của thuật toán tô miền , thuật toán cũng dừng khi . Hiện để trích thành phần liên thông, chúng ta còn có thuật toán Label Segmentation. Để tiện so sánh, ta sẽ tìm hiểu về thuật toán Label Segmentation. [4] i. Bước 1: những điểm ảnh là nền đánh dấu là 0, ngược lại đánh dấu là . ii. Bước 2: lần lượt xét từng điểm ảnh thuộc đối tượng cần xét từ góc trên bên trái xuống góc dưới bên phải. Hình 2-3: tô miền Hình 2-4: thuật toán tô miềm 15 Nếu chưa được đánh dấu và những hàng xóm của nó cũng vậy thì dán nhãn mới. Nếu chưa được đánh dấu và một trong những hàng xóm của nó được đánh dấu thì dán nhãn của hàng xóm cho nó. Nếu được đánh dấu khác nhãn của 1 trong những hàng xóm của nó thì ghi nhận vào bảng equality table. i. Bước 3: cập nhật lại bảng equatity table, và lần chạy thứ hai, cập nhật lại nhãn. Mathematical morphology Connected component labeling  Sử dụng phép toán Dilation và tập hợp giao nhau  Dựa vào kích thước và hình dạng của những phần góc (hold) ta muốn lấy, cần khởi tạo nhân tạo ảnh.  Sử dụng kĩ thuật đánh dấu  Cần ít nhất 2 lần quét toàn bộ bức ảnh Hình 2-5: sau khi chạy xong bước 1 Hình 2-6: chạy xong bước 3 và lập lại thuật toán thêm lần nữa để ta có bảng bên phải 16 Tìm bao lồi (Convex hull). Miền được gọi là tập lồi nếu như có đường thẳng nối 2 điểm nằm trong . Bao lồi nhỏ nhất là tập lồi nhỏ nhất chứa . Ý tưởng cơ bản để tìm ra bao lồi nhỏ nhất là đếm những hàng xóm của từng điểm ảnh của đối tượng, điểm nào có số lượng hàng xóm bằng 3 thì đánh dấu lại, lặp lại cho đến khi không còn tìm ra điểm ảnh nào có số hàng xóm nhiều hơn 3. Từ đó, thuật toán tìm bao lồi như sau: với . Thuật toán dừng ở và bao lồi . Ta cần lưu { đều sau thì ta có . Thật vậy do . Sự tồn tại của bao lồi theo định nghĩa sau: Gọi là tập hợp con của không gian thực , được chứa trong ít nhất một tập lồi (ví dụ như cả không gian ). Giao của những tập lồi chứa đều là tập lồi chứa . Gọi giao của tất cả những tập chứa X là bao lồi nhỏ nhất của . Trong thực tế, khi dùng phép toán này vẫn chưa tìm ra được bao lồi nhỏ nhất, nhưng ta có thể lấy tối ưu bằng cách tìm cực ở phía trên/dưới, bên trái/phải rồi loại bỏ những phần nằm ngoài đường thẳng vuông góc từ trên xuống đi qua cực. Làm mỏng (Thinning). Phép toán này giúp làm gọn vật thể bởi bộ nhân tạo ảnh cho trước sử dụng nền tảng của phương pháp hit – or – miss đã trình bày trên. Định nghĩa phép toán : Nếu ta chọn nhân tạo hình có dạng : Hình 2-7: màu xám là đối tượng tìm, màu đỏ là lần tìm thứ nhất, xanh lá, xanh dương, đen lần lượt là các lần tìm thứ hai, ba tư. Hợp của tất cả ta có bao lồi nhỏ nhất. 17 Với là hình xoay (phiên bản xoay) một góc alpha nào đó của . Khi này phép làm mỏng được định nghĩa: Với thuộc khoảng [ 1,8] và thuộc . Khi thì sẽ quay lại giá trị 1. Phép toán sẽ lặp lại cho tới khi kết quả vế trái không còn thay đổi nữa giữa khi lần lượt dùng hết bộ ( đến ) kết quả không thay đổi. Trong bộ nhân tạo ảnh trên thì ta không ta không quan tâm đến những phần được đánh dấu “X”,trên matlab thì những phần “X” luôn bằng 0 ngay cả khi lấy phần bù. Vd: Nhận xét 1: phép toán luôn có tính dừng. Đặt Vậy : Do vậy , (*) Xét: Hình 2-8 18 với . Đặt : = . Vậy Tương tự với . Với = hữu hạn , nếu dấu bằng xảy ra thì phép toán sẽ dừng, ta chỉ xét trường hợp dấu bằng không xảy ra tức là dãy giảm ngặt và . Vậy khi thì Khi số pixel bằng 0 bài toán dừng. Kết Luận: bài toán luôn có tính dừng. Nhận xét 2: phép toán dừng lại khi A không thỏa tính chất sau : Trong số pixel là 8-kề của một pixel tồn tại 3 pixel là 8-kề lẫn nhau. Xét công thức : Giả sử sao cho . Suy ra: . Vậy: Giả sử sao: , , .... , Vậy: . Điều này có nghĩa phép toán dừng lại. Vậy để A phải không thỏa các điều chung của là điều kiện trình bày ở nhận xét 2. Trong bộ công cụ toolboxs của matlab hổ trợ phép hàm mỏng trong hàm . Với inf là giá trị mà tại điểm mà ảnh không thể làm mỏng hơn nữa . khi thì kết quả vẫn không thay đổi so với trạng thái làm mỏng tối đa (chỉ áp dụng với bộ nhân tạo ảnh trên). 19 Làm dày (Thickening). Trái ngược với phép toán , là phép toán làm dày đối tượng được định nghĩa qua biểu thức sau Trong đó là mặt nạ phù hợp cho . Và tương tự với phép , mặt nạ có thể là một chuỗi các mặt nạ Do đó: Ta thấy thực chất chỉ là phép với .Ta biểu diễn lại công thức trên như sau: Hình sau sẽ mô tả cách hoạt dộng của biểu thức trên: Lưu {: Nếu dựa vào công thức trên thì ta chỉ thu được kết quả là hình (d). Để có được hình (e) ta phải thực hiện thêm một bước hậu xử lý xóa những điểm không liên thông nữa. Sau đây là một hàm mô tả việc xóa những điểm không liên thông trong một hình : Hình 2-10: (a) lúc ban đầu A (b) phần bù của A (c) kết quả với phần bù của A (d) tiếp tục lấy phần bù của (c) (e) kết quả sau khi lấy thành phần liên thông Hình 2-9: (từ trái sang) ảnh ban đầu, g2, ginf 20 Thư viên matlab cho ta sẵn hàm để làm dày đối tượng trong ảnh. Sau đây là vd minh họa : Lấy khung (Skeletons). 1. Định nghĩa – công dụng. Xương là một biểu diễn dạng đường của một đối tượng, trong đó: i. Đường này có độ rộng 1 điểm ảnh. ii. Đường này đi qua phần giữa của đối tượng đó. Công dụng của phép toán lấy xương làm giảm kích thước ảnh. Những điều kiện nói trên không phải lúc nào cũng thực hiện được. Chúng ta có thể chỉ ra một tình huống như vậy trong hình dưới. Hình 2-11: hình ban đầu Hình 2-12: sau khi làm dày với n=15 21 Trong ví dụ đầu tiên ở hình (a), để sinh ra một đường thể hiện sự đơn giản của đối tượng, chúng ta không thể nào tạo ra một đường thẳng có độ dày của một điểm ảnh và nằm ở tâm của đối tượng. Trong hình (b), chúng ta lại không thể loại bỏ bất kz điểm ảnh nào của đối tượng của liên thông 8 có trong hình. 2. Công thức. Trong đó – được gọi là tập con xương (với ; A ảnh gốc; B là mặt nạ). là giá trị lớn nhất trước khi A trở thành tập rỗng qua phép “làm xói mòn “ (erosion) bởi mặt nạ B.Ta biểu diễn K dưới dạng toán học như sau: Trong matlab ta có hàm sau dùng để xương hóa một ảnh Trong đó là ảnh nhị phân gốc, là số lần thực hiện hàm Lưu {: nếu hàm sẽ được thực hiện lần sao cho kết quả của lần giống với kết quả lần . Ngoài ra, mặt nạ được sử dụng trong hàm trên là mặt nạ 3x3 ( ). 3. Tái xây dựng đối tượng bị xương hóa. Từ một ảnh bị xương hóa, chúng ta có thể tái xây dựng lại ảnh gốc bằng cách dung phép giãn hình (Dilation) lần với Công thức: Hình 2-13: 22 4. Ví dụ minh họa. Ta thấy trong hình 2-14, tập bị xương hóa đã không còn liên thông nữa. Đây là một nhược điểm khá lớn trong phép lấy xương trong Morphology. Tiếp theo là ví dụ minh họa cho ham trong matlab: Hình 2-14: cột từ 1 đến 4 mô tả việc tạo xương của A, cột 5 và 6 mô tả việc tái cấu trúc A từ xương trong lần. Hình 2-15: ảnh gốc A Hình 2-16: Phần bù của ảnh nhị phân 23 Nhận xét: Ta thấy hình 2-19 cho kết quả tốt hơn hình 2-17 vì ảnh đầu vào của hình 2-17 (hình 2-16) xuất hiện một số lỗ gây “nhiễu” nên ta phải làm thêm công đoạn làm đầy ảnh (fill holes) để cho ảnh đầu vào mượt hơn. Tuy nhiên với những ảnh bị nhiễu nặng như hình 2-20 thì kết quả của phép lấy xương sẽ không như mong đợi Hình 2-17: Ảnh sau khi được xương hóa Hình 2-18: Ảnh sau khi được làm đầy Hình 2-19: Ảnh sau khi được xương hóa Hình 2-20: 24 Do đó, việc khử nhiễu trước khi lấy xương đối tượng là cần thiết. 5. Một số phép lấy xương khác. i. Thuật toán làm mảnh của Toumazet: bảo toàn tất cả các điểm cụt không gây đứt nét đối tượng. Tuy nhiên, thuật toán có nhược điểm là rất chậm, rất nhạy cảm với nhiễu, xương chỉ là 4-liên thông và không làm mảnh được với một số cấu hình phức tạp ii. Thuật toán làm mảnh của Ching Y Suen: dựa trên đường biên của đối tượng, có thể cài đặt theo cả phương pháp song song và tuần tự. Tốc độ của thuật toán rất nhanh. Nó có nhược điểm là gây đứt nét, xương tạo ra là xương giả (có độ dày là 2 phần tử ảnh). iii. Thuật toán làm mảnh của N.J.Naccache và R.Shinghal : ưu điểm là nhanh, xương tạo ra có khả năng khôi phục ảnh ban đầu của đối tượng. Nhược điểm chính của thuật toán là rất nhạy với nhiễu, xương nhận được phản ánh cấu trúc của đối tượng thấp. iv. Thuật toán làm mảnh của H.E.Lu P.S.P Wang : tương đối nhanh, giữ được tính liên thông của ảnh, nhưng lại có nhược điểm là xương tạo ra là xương 4-liên thông và xoá mất một số cấu hình nhỏ. v. Thuật toán làm mảnh của P.S.P Wang và Y.Y.Zhang dựa trên đường biên của đối tượng, có thể cài đặt theo phương pháp song song hoặc tuần tự, xương là 8- liên thông, ít chịu ảnh hưởng của nhiễu. Nhược điểm chính của thuật toán là tốc độ chậm. Cắt xén (Pruning). Đây là phương pháp dựa trên nền tảng của phương pháp làm mỏng và phương pháp lấy khung xương. Phương pháp giúp ta loại bỏ những thành phần dư thừa trong ảnh. Nhân tạo ảnh thường được sử dụng như hình bên dưới. Phương pháp này chi thành 4 bước. Hình 2-21: minh họa kết quả không mong đợi 25 + Đầu tiên ta sữ dụng phép làm mỏng đối với vật mẫu ban đầu là A, ta chỉ thực hiện phép làm mỏng qua n chu trình. + Ta thực hiện phép lấy hội của phép hiss-or-miss trong một chu trình : + Bước tiếp theo ta phình lần: + Kết quả cuối cùng là hội của và Phép toán qua lần lượt 4 bước trên và là kết quả của phép tỉa xén Trong các phép toán trên đã phải định trước được để sử dụng cho phép làm mỏng của phương trình . Thường thì trong các ứng dụng đều cho phép người dụng ước lượng giá trị của sao cho phù hợp. Trường hợp thì kết quả thu được sẽ là tập chỉ có 1 pixel. Ta minh họa bằng hình sau với : Hàm hổ trợ: với operation là ‘spur’ Hình 2-22 26 Ở đây người dùng xác định giá trị phù hợp là 3 theo phương pháp xác định trực quan. Hình 2-23: nguyên mẫu a Hình 2-24: g1 Hình 2-25: g2 Hình 2-26: gn 27 Chương 3: Phương Pháp Morphology Cho Ảnh Xám. Khái niệm về ảnh xám. Ta có một ảnh xám, ảnh xám này có thể được biểu diễn bởi một hàm không liên tục , với và biểu diễn cho mức xám tại pixel có vị trí trong ảnh , nếu giá trị mức xám là một số nguyên thì . Tương tự như trong ảnh nhị phân, ta cũng có khái niệm phần bù và phản xạ của một ảnh xám : : phần bù của : phản xạ của Phép Dilation cho ảnh xám. Những phép toán mà ta đã đề cập ở phần trên đều có thể áp dụng vào ảnh xám. Tất nhiên ngoại trừ . Ta nói được phình bởi nhân (mặt nạ) , kí hiệu được định nghĩa như sau : với và . Trong đó và là miền giá trị của và . Ta nên quan niệm là một hàm hơn là một tập hợp. Công thức trên còn có thể được định nghĩa theo một biến : Lưu {: miền giá trị tùy thuộc vào nhân tạo ảnh mà ta lựa chọn để sử dụng. Cụ thể có thể tùy thuộc vào vị trí của tâm của nhân tạo ảnh, nếu tâm của nhân tạo ảnh nằm giữa thì có thể tồn tại giá tri âm hoặc dương, giá trị của hàm sẽ nằm bên phải nếu s dương và ngược lại. Ta có thể mô tả phép toán như sau: xem kết quả xoay của nhân tạo ảnh như một mặt nạ, đặt tâm của mặt nạ lên tất cả các vị trí của ảnh lần lượt từ trên xuống dưới từ trái qua phải. Tại mỗi tọa độ trên ảnh, ta đi tìm tổng mức xám của và tại từng vị trí trong vùng mặt nạ được phủ lên, kế đến ta gán mức xám tại tọa độ ra ảnh mới là ảnh kết quả bằng max của tất cả các giá trị vừa tính. Vùng điều kiện , được mô tả khi ta phủ mặt nạ lên vùng tương tác , những tọa độ trong mặt nạ lọt ra vùng ngoài của ảnh xem như không có Hình 3-1: hình minh họa phép toán dilation 28 giá trị và không được tính. i. Nhận xét 1: nếu trong thành phần của nhân tạo ảnh b , mức xám (độ sáng ) càng lớn tức là chứa những giá trị dương thì sau khi qua phép phình ảnh thì ảnh sẽ càng sáng hơn và các phần tối sẽ càng bị thu nhỏ lại hoặc mất hẳn đi. ii. Nhận xét 2: là ảnh sáng lên và những vùng tối có kích thước nhỏ hơn nhân tạo ảnh bị xóa hoàn toàn. Trong Matlab xử dụng hàm với là nhân tạo ảnh dùng cho phép phình. Phép Erosion cho ảnh xám. Ta nói được phình bởi nhân (mặt nạ), kí hiệu được định nghĩa như sau: với và . và có vai trò tương tự như trong phép phình ảnh. Giống như phép phình ảnh ta cũng có thể mô tả công thức bởi hàm một biến: Hình 3-2: phình ảnh sử dụng nhân flat-top Hình 3-3: phình ảnh với nhân tạo hình 3x3 29 Mô tả phép toán: ta lấy nhân tạo ảnh làm mặt nạ , lần lượt phủ mặt nạ này lên các vị trí trên ảnh, tại mỗi vị trí trên ảnh , ta tính hiệu mức xám của và tại từng vị trí bị mặt nạ bao phủ sau đó tạo ra một ảnh mới gán giá trị tại vị trí tương ứng trong ảnh bằng của tất cả các giá trị nằm trong vùng xác định vừa tính. Và lưu ý, Vùng điều kiện , mô tả việc khi ta phủ mặt nạ lên vùng tương tác những tọa độ trong mặt nạ lọt ra vùng ngoài của ảnh xem như không có giá trị và không được tính. Ngược lại với phép phình , kết quả co ảnh sẽ cho ta được một bức ảnh tối hơn và những vàng sáng nhẹ hoặc ít sẽ bị loại bỏ hoàn toàn hoạc thu nhỏ lại tùy thuộc vào nhân tạo ảnh ma ta sữ dụng. Nếu kích thước của những vùng sáng nhỏ hơn kích thước của nhân tạo ảnh thì những vùng sau này sẽ biến mất hẳn trong quá co ảnh. Trong Matlab: tương tự với phép phình, ta dùng hàm Hình 3-4: co rút sử dụng nhân flat-top 30 Phép Opening và Closing cho ảnh xám. Cũng tương tự như trong ảnh nhị phân: Phép Opening được mô tả bằng công thức: Phép Closing : Tương quan: Phép Opening và Closing được giải thích theo hình học một cách rất đơn giản. Ta tưởng tượng hình có thể được biểu diễn trong không gian 3 chiều với vệ trục tọa độ , và chiều thứ 3 là mức xám tại pixel đó. Khi đó hình được biểu diễn giống như một mặt, mức độ lồi lõm tại một điểm phụ thuộc vào giá trị mức xám tại điểm đó. Và nhân tạo ảnh b cũng có cách biểu diễn tương tự. Có thể ví nhân tạo ảnh như một quả bóng lăn tròn bên trong hoặc bên ngoài vật thể. Đối với Opening có thể hiểu một cách đơn giản là nhân tạo ảnh b sẽ như một quả cầu lăn tròn bên dưới mặt bức ảnh . Những vùng có kích thước tương đối nhỏ và mức xám cao sẽ bị hạ mức xám xuống. Hình 3-5: co rút xử dụng nhân 3x3 Hình 3-6: minh họa phép toán Opening trên ảnh xám 31 Đối với Closing có thể hiểu một cách đơn giản là nhân tạo ảnh b sẽ như một quả cầu lăn tròn bên mặt ngoài bức ảnh . Những vùng có kích thước nhỏ hơn quả cầu và mức xám thấp được nâng mức xám lên. Hình 3-8: ảnh gốc Hình 3-9: ảnh bên trái sau Opening, bên phải sau Closing Nhận xét : ở bức ảnh sau Opening thì những vùng nào sáng (mức xám cao) một cách khác thường so với những vùng xung quanh sẽ được hạ mức xám xuống gần với những vùng khác. ở bức ảnh sau Closing những vùng nào tối (có mức xám thấp) một cách khác thường so với những vùng xung quanh khác thì sẽ được nâng mức xám lên gần bằng những vùng khác. Ứng dụng trong matlab: i. Ta viết thân hàm cho Opening: ii. Ta viết thân hàm cho Closing: Hình 3-7: minh họa phép toán Closing cho ảnh xám 32 Một số ứng dụng của morphology trên ảnh xám. 1.1. Làm trơn ảnh xám. Một ứng dụng khá đơn giản là ta có thể làm trơn mờ những ảnh bị nhiễu những hạt ảnh nhỏ khá chênh lệch về mức xám đối với những vùng xung quanh bằng cách sữ dụng hai phép Closing và Opening. Hình 3-10: ảnh gốc bị nhiễu Hình 3-11: sau khi Opening Hình 3-12: sau khi Closing Kết quả thu được còn tùy thuộc vào nhân tạo ảnh mà ta chọn . Cách chọn nhân tạo ảnh thích hợp là dựa trên trực quan. Ứng dụng trong matlab: 1.2. Phép biến đổi Gradient. Ta nói là biến đổi Gradient của ảnh , được định nghĩa như sau : Hình 3-13: làm trơn mờ ảnh 33 Kết quả sau phép biến đổi Gradient , nhận xét thấy do phép phình ảnh đã tác động làm cho những vùng sáng của bức ảnh được mở rộng . Với phép co rút ảnh đã làm cho những vùng tối được mở rộng và vùng sáng hẹp lại, Vì vậy tại những vị trí là biên của vật thể ( nơi có độ biến thiên đột ngột về mức xám ) thì khi đi trừ ảnh kết quả của phép phình ảnh cho kết quả của phép co rút sẽ làm nổi bật lên những đường biên của vật thể. Vì lẽ đó phép biến đổi Gradient còn có thể sử dụng để trích biên trong ảnh xám . Trong trường hợp này thì tùy chọn về nhân tạo ảnh. Nhân tạo ảnh có kích thước càng lớn và càng có nhiều pixel có mức xám cao thì đường biên càng rõ, càng đậm. Ứng dụng trong matlab: 1.3. Biến đổi Top – Hat. Ta gọi h là biến đổi Top – hat của một ảnh, người ta định nghĩa phép toán như sau: – Hình 3-14: ảnh ban đầu Hình 3-15: sau khi dùng 34 Nhận xét: sau khi ta phình ảnh th như ng phần co mư c xa m cao nổi lên trong ảnh se bi ma t hoặc mư c xa m bị giảm. Vì vậy khi qua phép trừ và phép Opening ta thu được những vùng nổi bật trong bức ảnh. Ứng dụng trong matlab: 1.4. Tách ảnh theo nội dung ảnh. Ta có một hình khi ta muốn tách bức ảnh ra nhiều vùng mà muốn giữ nguyên vẹn các đối tượng trong ảnh. Phương pháp sau đưa ra một hướng giải quyết cho việc này. Để tách thành hai vùng và giữ nguyên vẹn đối tượng trong ảnh ta dùng thuật giải sau : i. Bước 1: ta xem những hình tròn bên trái là những đối tượng nhiễu và khử đi bằng phép Closing, ta chọn nhân tạo ảnh có kích thước lớn hơn những hình tròn này để xóa chúng đi. Cách xác định nhân tạo ảnh cũng do trực quan. Hình 3-18: hình có nhiều hình tròn nhỏ Hình 3-17: sử dụng nhân tạo ảnh 3x3 với mức xám cao Hình 3-16: hình ban đầu 35 ii. Bước 2: Ta khoanh vùng các đối tượng hình tròn bên phải bằng phép Opening, ta chọn nhân tạo ảnh phải lớn hơn khoảng các các hình tròn sau cho khi kết quả thu được ta được một vùng đầy đã fill. Ta cũng xác định nhân tạo ảnh bằng trực quan. iii. Bước 3: sau khi đã phân biệt hóa thành 2 vùng rõ ràng ta tiến hành lấy biên của 2 vùng này bằng phép biến đổi Gradient. Lưu { khi ta dùng phép biến đổi Gradient ta phải chọn nhân tạo ảnh thật sáng và đủ lớn để nổi bật vùng biên. Hoặc chúng ta có thể dùng vài phép biến đổi đơn giản để làm nổi bật vùng biên lên như ví dụng trong hình sau: Hình 3-21 Hình 3-22 Hình 3-23 Kết quả thu được cuối cùng ta lấy những vùng sáng thay thế vào vị trí các pixel trong ảnh gốc và ta được 2 vùng riêng biệt như trên hình. 1.5. Phép đo độ hạt. Hình 3-19 Hình 3-20 36 Trong phép này ta có thể thống kê được các đối tượng có những kích cỡ khác nhau bằng phương pháp Opening ảnh gốc với một nhân tạo ảnh có kích thước tăng dần. Như ảnh bên, ta thấy có nhiều loại kích thước của các đối tượng tròn cụ thể là 3 kích cỡ. Ta sẽ tìm cách thống kê sự phân bổ của các đối tượng có các kích cỡ như nhau. Ta tiến hành Opening với nhân tạo ảnh có kích thước tăng dần. Ở phương pháp này ta nên quy nhân tạo ảnh về dạng hình vuông hoặc hình tròn có kích thước tăng dần. Hình 3-24 Hình 3-25: sử dụng hàm và nhân tạo ảnh 4x4 chứa các giá trị 1 Hình 3-26: sử dụng hàm và nhân tạo ảnh 5x5 chứa các giá trị 1 37 Ta thấy khi từ Opening ma trận 7x7 sang Opening ma trận 8x8 có sự thay đổi nhiều trong ảnh. Điều này có nghĩa là các hình tròn nhỏ có kích thước cỡ 7x7 Hình 3-27: sử dụng hàm và nhân tạo ảnh 6x6 chứa các giá trị 1 Hình 3-28: sử dụng hàm và nhân tạo ảnh 7x7 chứa các giá trị 1 Hình 3-29: sử dụng hàm và nhân tạo ảnh 8x8 chứa các giá trị 1 Hình 3-30: sử dụng hàm và nhân tạo ảnh 9x9 chứa các giá trị 1 38 và khi Opening với ma trận 8x8 thì phần lớn các đối tượng tròn này biến mất. Điều này cũng có nghĩa là khi ta biết sự biến thiên qua các bước thì ta sẽ nắm được sự phân bổ đối tượng trong ảnh. Để có được điều này ta tiến hành trừ ảnh qua các bước. Hình 3-31 – Hình 3-32: – Hình 3-33: – 39 Các hình trên cho thấy sự thay đổi các mật độ phân bố của các đối tượng trên ảnh. Công việc tiếp theo là ta số hóa những bức ảnh này. Tức là đếm được phân bổ các đối tượng. Ta thiết lập một hàm như histogram nhưng thay vì đếm mức độ xám ta đếm số đối tượng có các kích cở từ 1 đến n pixel. Ta chọn n=150. Tùy theo mức độ kích cỡ của các đối tượng mà ta xác định n. Ta có hàm Matlab sau: Hình 3-35: – Hình 3-34: – 40 Hình 3-36: Hình kế bên là kết quả thống kê sự phân bổ. Dựa vào hình ta thấy số lượng các đối tượng khoảng 7 đế 8 pixel là nhiều nhất. Và đối tượng lớn nhất thống kê được là 64 pixel. 41 Chương 4: Ứng Dụng Chạy Thử Để hiểu hơn về các phép toán trong phương pháp này, ta sẽ tìm hiểu ứng dụng “đếm những đối tượng là hình tròn trong một hình cho trước”, với hướng tiếp cận ban đầu chỉ mang tính { tưởng của nhóm làm đề tài. Nhóm đề tài xin liệt kê ra đây các bước thực hiện qua các bước như sau: 1. Tô đầy các thành phần liên thông khép kín. 2. Tách biên các thành phần liên thông. Hình 4-1: Hình ban đầu Hình 4-2: Chuyển sang nền đen Hình 4-3: Tô cách thành phần lien thông khép kín 42 3. Đánh dấu các thành phần liên thông. 4. Tìm trọng tâm vật thể bằng cách tính dựa trên tọa độ dòng và tọa đô cột. 5. So sánh các khoảng cách từ biên tới tâm. Theo khoảng cách xa nhất và gần nhất để xác định xem đó có phải là đối tượng tròn hay không. Cho một sai số để kiểm định. Thực nghiệm ban đầu cho ra sai số là 3,5. Hàm cdistance(): Khoảng cách Euclide giữa hai điểm trong không gian 2D. Hàm originfinding():Tìm trọng tâm của một đối tượng. Input tọa độ dòng của tất cả các dòng và tất cả các cột của đối tượng. Output xuất ra tọa độ dòng và cột của trọng tâm. Hàm countcircle():Hàm chính để đếm số đối tượng tròn. ô ầ ữ à ầ ê ô é í á ê à ầ ê ô Đá ấ à ầ ê ô ì ừ à ầ ê ô ã ượ á ấ ạ ộ ả ứ á ả Hình 4-4: Ảnh tách biên 43 á ừ ừ ể ê ê ế ọ â ậ ể á ả á à ả ượ ậ ở ê ì ò ẽ à ì ó ộ ệ ữ à ô ượ á ố ã Kết quả sau khi gõ ta có như sau 44 Tài Liệu Tham Khảo [1] [2] A Hit-or-Miss Transform for Multivariate Images - E. Aptoula, S. Lefèver *, C. Ronse - LSIIT UMR-7005 CNRS-ULP, Pôle API, Blvd Sébastien Brant, PO Box 10413, 67412 Illkirch Cedex, France [3] [4] Amin Allalou - Centre for Image Analysis Uppsala University – Ngoài ra còn ở: [1] EE368: Digital Image Processing Prof. Bernd Girod [2] Gonzalez and Woods, Digital Image Processing, Prentice Hall, New Jersey, 2002.