Đề tài Xử lý ảnh - 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ẽ đượ