Luận văn Nghiên cứu một số phương pháp phát hiện biên

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN QUANG SƠN NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÁT HIỆN BIÊN Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS NGÔ QUỐC TẠO Thái Nguyên - 2008 2 MỤC LỤC Trang MỤC LỤC ...................................................................................................................................................... 2 LỜI CẢM ƠN............................................................................................................................................... 4 DANH SÁCH CÁC HÌNH ẢNH........................................................................................................ 5 MỞ ĐẦU......................................................................................................................................................... 7 CHƯƠNG I: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN ................................................ 9 1.1. Tổng quan về xử lý ảnh............................................................................................................. 9 1.1.1. Xử lý ảnh................................................................................................................................. 9 1.1.2. Các bước cơ bản trong xử lý ảnh ..............................................................................10 1.1.3. Một số vấn đề cơ bản trong xử lý ảnh ....................................................................14 1.2. Toán tử không gian với xử lý ảnh ......................................................................................18 1.2.1. Làm trơn nhiễu bằng lọc tuyến tính.........................................................................18 1.2.2. Làm trơn nhiễu bằng lọc phi tuyến ..........................................................................21 1.2.3. Lọc thông thấp, thông cao và lọc dải thông.........................................................22 1.3. Tổng quan về biên......................................................................................................................23 1.3.1. Biên và các kiểu biên cơ bản.......................................................................................23 1.3.2. Vai trò của biên trong nhận dạng..............................................................................26 CHƯƠNG II: CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN CỔ ĐIỂN...................28 2.1. Phân loại các kỹ thuật phát hiện biên ...............................................................................28 2.1.1. Phương pháp phát hiện biên trực tiếp .....................................................................28 2.1.2. Phương pháp phát hiện biên gián tiếp.....................................................................28 2.1.3. Quy trình phát hiện biên................................................................................................29 2.2. Kỹ thuật phát hiện biên Gradient........................................................................................29 2.2.1. Pixel difference..................................................................................................................30 2.2.2. Separated Pixel Difference...........................................................................................31 2.2.3. Toán tử Robert (1965)....................................................................................................32 2.2.4. Toán tử Prewitt ..................................................................................................................33 3 2.2.5. Toán tử (mặt nạ) Sobel...................................................................................................33 2.2.6. Toán tử Frie-Chen ............................................................................................................34 2.2.7. Toán tử Boxcar ..................................................................................................................34 2.2.8. Toán tử Truncated Pyramid .........................................................................................35 2.3 Các toán tử la bàn ........................................................................................................................36 2.3.1. Toán tử la bàn Kirsh........................................................................................................37 2.3.2. Toán tử la bàn Prewitt ....................................................................................................38 2.3.3. Robinson 3 - Level...........................................................................................................39 2.3.4. Robinson 5 - Level...........................................................................................................40 2.4. Kỹ thuật phát hiện biên Laplace..........................................................................................41 CHƯƠNG III: CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN NÂNG CAO ..........45 3.1. Phương pháp Canny..................................................................................................................45 3.1.1. Cơ sở lý thuyết thuật toán.............................................................................................45 3.1.2. Hoạt động của thuật toán ..............................................................................................47 3.2. Phương pháp Shen - Castan ..................................................................................................52 3.2.1. Xây dựng bộ lọc tối ưu...................................................................................................52 3.2.2. Hoạt động của thuật toán .............................................................................................54 3.3. Phát hiện biên dựa vào Wavelet ..........................................................................................56 CHƯƠNG IV: MỘT SỐ NHẬN XÉT VÀ ĐÁNH GIÁ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN ................................................................................................................................62 4.1. Phương pháp phát hiện biên dựa vào kỹ thuật Gradient .........................................62 4.2. Phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai ...................66 4.3. Đánh giá nhận xét về phương pháp Canny....................................................................69 4.4. Các phương pháp phát hiện biên (phương pháp Gadient, phương pháp Laplace, phương pháp Canny) ......................................................................................................71 4.5. Đánh giá nhận xét về phương pháp Wavelet ................................................................73 KẾT LUẬN..................................................................................................................................................75 TÀI LIỆU THAM KHẢO.....................................................................................................................76 4 LỜI CẢM ƠN Trước hết tôi muốn gửi lời cảm ơn đến các thầy cô giáo ở Viện công nghệ thông tin và Khoa công nghệ thông tin - Đại học Thái Nguyên đã quan tâm tổ chức chỉ đạo và trực tiếp giảng dạy khóa cao học của chúng tôi. Đặc biệt tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo hướng dẫn PGS.TS Ngô Quốc Tạo về những chỉ dẫn khoa học và tận tình hướng dẫn cho tôi trong suốt quá trình làm luận văn. Nếu không có sự giúp đỡ của thầy thì tôi khó có thể hoàn thành bản luận văn này. Cũng qua đây, tôi xin chân thành cảm ơn lãnh đạo Trung tâm ứng dụng tiến bộ Khoa học và Công nghệ - Sở Khoa học và Công nghệ Thái Nguyên, nơi tôi công tác, đã tạo mọi điệu kiện thuận lợi cho tôi trong thời gian hoàn thành các môn học cũng như trong suốt thời gian làm luận văn tốt nghiệp. Cuối cùng, tôi xin cảm gia đình, những người đã luôn ủng hộ và động viên để tôi yên tâm nghiên cứu và hoàn thành luận văn. 5 DANH SÁCH CÁC HÌNH ẢNH Hình 1.1: Quá trình xử lý ảnh.............................................................................................................. 9 Hình 1.2: Các bước trong quá trình xử lý ảnh...........................................................................10 Hình 1.3: Lân cận các điểm ảnh của tọa độ (x,y) ....................................................................16 Hình 1.4: Đường biên lý tưởng.........................................................................................................24 Hình 1.5: Đường biên dốc...................................................................................................................25 Hình 1.6: Đường biên không trơn ...................................................................................................26 Hình 2.1: Biên ảnh với Pixel Difference......................................................................................31 Hình 2.2: Biên ảnh với Separated Pixel Difference ...............................................................32 Hình 2.3: Biên ảnh với toán tử Robert ..........................................................................................33 Hình 2.4: Biên ảnh với toán tử Prewitt .........................................................................................33 Hình 2.5: Biên ảnh với toán tử Sobel ............................................................................................34 Hình 2.6: Biên ảnh với toán tử Frie-Chen...................................................................................34 Hình 2.7: Biên ảnh với toán tử Boxcar .........................................................................................35 Hình 2.8: Biên ảnh với toán tử Truncated Pyramid................................................................36 Hình 2.9: Biên ảnh với toán tử Kirsh.............................................................................................38 Hình 2.10: Biên ảnh với toán tử la bàn Prewitt ........................................................................39 Hình 2.11: Biên ảnh với toán tử Robinson 3 level..................................................................40 Hình 2.12: Biên ảnh với toán tử Robinson 5 level..................................................................41 Hình 2.13: Biên ảnh với kỹ thuật Laplace...................................................................................42 Hình 2.14: Bộ lọc Laplace of Gauss ..............................................................................................42 Hình 2.15: Biên ảnh với kỹ thuật Laplace of Gauss...............................................................44 Hình 3.1: Đạo hàm hàm Gauss theo hai hướng (x,y) ............................................................48 Hình 3.2: Hình mô tả các điểm biên lân cận..............................................................................50 6 Hình 3.3: Biên ảnh theo phương pháp Canny ...........................................................................52 Hình 3.4: Biên ảnh theo phương pháp Shen-Castan ..............................................................55 Hình 3.5: Dùng DWT cho biến đổi Neurite ...............................................................................56 Hình 3.6 Biên ảnh của một cái hộp đơn .......................................................................................57 Hình 3.7: Biên ảnh con chó nằm ở bậc thang............................................................................57 Hình 3.8: Sử dụng 3 tiêu chuẩn cho ảnh con cho nằm bậc thang ....................................58 Hình 3.9: Sử dụng 3 tiêu chuẩn cho ảnh của Filopodia........................................................59 Hình 3.10: Sử dụng liên kết tự động trong ảnh hộp đơn......................................................59 Hình 3.11: Sử dụng liên kết tự động trong ảnh con cho nằm bậc thang.......................60 Hình 3.12: Sử dụng liên kết tự động trong ảnh của Filopodia ..........................................60 Hình 4.1: Hình mô phỏng kết quả tìm biên theo kỹ thuật Gradient ...............................65 Hình 4.2: Biên ảnh theo đạo hàm bậc nhất và bậc hai ..........................................................68 Hình 4.3: Phát hiện biên với Canny ngưỡng cố định.............................................................69 Hình 4.4: Phát hiện biên với Canny ngưỡng thay đổi σ =1................................................70 Hình 4.5: Biên ảnh theo Gradient, Laplace, Canny................................................................71 Hình 4.6: Phát hiện biên theo phương pháp Wavelet ............................................................72 7 MỞ ĐẦU Thời đại công nghệ thông tin phát triển như vũ bão đã đi vào từng ngõ ngách của cuộc sống. Hiện nay, bất cứ sự phát triển của ngành công nghiệp nào đều có sự hiện diện và đóng góp rất to lớn của công nghệ thông tin. Xử lý ảnh là một trong những chuyên ngành quan trọng và lâu đời của Công nghệ thông tin. Xử lý ảnh được áp dụng trong nhiều lĩnh khác nhau như y học, vật lý, hoá học, tìm kiếm tội phạm, trong quân sự và trong một số lĩnh vực khác.... Phần lớn con người thu nhận thông tin bằng thị giác, cụ thể đó là các hình ảnh. Vì vậy xử lý ảnh là vấn đề không thể thiếu và hết sức quan trọng để thu được hình ảnh tốt hơn, đẹp hơn, nhằm đáp ứng yêu cầu thông tin khác nhau của người nhận. Trong xử lý ảnh, việc nhận dạng và phân lớp đối tượng cần trải qua các quá trình và các thao tác khác nhau. Phát hiện biên là một giai đoạn rất quan trọng vì các kỹ thuật phân đoạn ảnh chủ yếu dựa vào giai đoạn này. Mục đích của việc dò biên sẽ đánh dấu những điểm trong một ảnh số mà có sự thay đổi đột ngột về độ xám, tập hợp nhiều điểm biên tạo nên một đường bao quanh ảnh (đường biên). Nhờ có đường biên mà chúng ta có thể phân biệt giữa đối tượng và nền, phân biệt giữa các vùng khác nhau và định vị được đối tượng từ đó mà nhận dạng đối tượng. Đây là cơ sở quan trọng trong việc ứng dụng phương pháp này vào thực tiễn của cuộc sống, đặc biệt là trong điều kiện đất nước ta đang từng bước phát triển và đi lên nên việc nghiên cứu các ứng dụng vấn đề này cần được quan tâm và phát triển. Xuất phát từ thực tế đó, luận văn lựa chọn đề tài " Nghiên cứu một số phương pháp phát hiện biên". Mục đích chính của đề tài là hệ thống hóa kiến thức về các phương pháp phát hiện biên, từ các kỹ thuật dò biên cài đặt chương trình để đưa ra các nhận xét, so sánh, đánh giá về các phương pháp phát hiện biên. Qua đó có cái nhìn tổng quát về các phương pháp phát hiện biên. 8 Ngoài phần mở đầu và kết luận luận văn được chia làm 4 chương, nội dung cụ thể của các chương như sau: Chương I: Tổng quan về xử lý ảnh và biên Trong chương này trình bày sơ lược về xử lý ảnh, giới thiệu các bước xử lý trong một hệ thống xử lý ảnh. Một số thành phần cốt tử trong xử lý ảnh, như điểm ảnh, mức xám, biên,…được trình bày như là các khái niệm. Chương II: Các phương pháp phát hiện biên cổ điển Nội dung của chương này sẽ đề cập đến một số phương pháp phát hiện biên trong phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai. Chương III: Các phương pháp phát hiện biên nâng cao Trong chương này đề cập đến phương pháp phát hiện biên Canny, phương pháp Shen-Castan và phương pháp Wavelet. Chương IV: Một số nhận xét đánh giá các phương pháp phát hiện biên Qua việc cài đặt thử nghiệm các phương pháp phát hiện biên đã trình bày trong các chương trước, từ các kết quả mô phỏng thực nghiệm khi chạy chương trình, trong chương này đưa ra các nhận xét đánh giá, so sánh các phương pháp phát hiện biên. Chỉ ra phương pháp phát hiện biên phù hợp với loại ảnh cần xử lý. Tuy nhiên, việc nghiên cứu một vấn đề khoa học đi đến kết quả là một khó khăn và nhiều thách thức do vậy luận văn chắc còn nhiều thiếu sót. Rất mong nhận được ý kiến đóng gópquý báu của các thầy cô và đồng nghiệp. Học viên Nguyễn Quang Sơn 9 CHƯƠNG I TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN 1.1. Tổng quan về xử lý ảnh 1.1.1. Xử lý ảnh Con người thu nhận thông tin qua các giác quan trong đó thị giác đóng vai trò quan trọng nhất. Sự phát triển nhanh của phần cứng máy tính, xử lý ảnh và đồ hoạ đã phát triển mạnh mẽ và ngày càng có nhiều ứng dụng trong cuộc sống. Xử lý ảnh đóng một vai trò quan trọng trong tương tác người máy. Quá trình xử lý nhận dạng ảnh là một quá trình thao tác nhằm biến đổi một ảnh đầu vào để cho ra một kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh "tốt hơn" hoặc một kết luận. Hình 1.1: Quá trình xử lý ảnh Như vậy mục tiêu của xử lý ảnh có thể chia làm ba hướng như sau: - Xử lý ảnh ban đầu để cho ra một ảnh mới tốt hơn theo một mong muốn của người dùng (ví dụ: ảnh mờ cần xử lý để được rõ hơn). - Phân tích ảnh để thu được thông tin nào đó giúp cho việc phân loại và nhận biết ảnh (ví dụ: phân tích ảnh vân tay để trích chọn các đặc trưng vân tay). - Từ ảnh đầu vào mà có những nhận xét, kết luận ở mức cao hơn, sâu hơn (ví dụ: ảnh một tai nạn giao thông phác hoạ hiện trường tai nạn). Ảnh đầu vào Xử lý ảnh Ảnh tốt hơn Kết luận 10 1.1.2. Các bước cơ bản trong xử lý ảnh Quá trình xử lý một ảnh đầu vào nhằm thu được một ảnh đầu ra mong muốn thường phải trải qua rất nhiều bước khác nhau. Các bước cơ bản của một quá trình xử lý ảnh được thể hiện thông qua hình sau: Hình 1.2: Các bước cơ bản trong quá trình xử lý ảnh 1.1.2.1 Thu nhận ảnh Đây là bước đầu tiên trong quá trình xử lý ảnh. Để thực hiện điều này, ta cần có bộ thu ảnh và khả năng số hoá những tín hiệu liên tục được sinh ra bởi bộ thu ảnh đó. Bộ thu ảnh ở đây có thể là máy chụp ảnh đơn sắc hay màu, máy quét ảnh, máy quay... Trong trường hợp bộ thu ảnh cung cấp chưa phải là dạng số hoá ta còn phải chuyển đổi hay số hoá ảnh. Quá trình chuyển đổi ADC (Analog to Digital Converter) để thu nhận dạng số hoá của ảnh. Mặc dù đây chỉ là công đoạn đầu tiên song kết quả của nó có ảnh hưởng rất nhiều đến công đoạn kế tiếp. Phân đoạn ảnh Biểu diễn và mô tả Tiền xử lý ảnh Thu nhận ảnh (Scaner, sensor, camera) Nhận dạng và nội suy CƠ SỞ TRI THỨC 11 1.1.2.2 Tiền xử lý Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khôi phục ảnh, nắn chỉnh hỉnh học... Với mục đích làm cho chất lượng ảnh trở lên tốt hơn nữa, chuẩn bị cho các bước xử lý phức tạp kế tiếp sau đó. * Khử nhiễu: Nhiễu được chia thành hai loại: nhiễu hệ thống và nhiễu ngẫu nhiên. Đặc trưng của nhiễu hệ thống là tính tuần hoàn. Do vậy, có thể khử nhiễu này bằng việc sử dụng phép biến đổi Fourier và loại bỏ các đỉnh điểm. Đối với nhiễu ngẫu nhiên, trường hợp đơn giản là các vết bẩn tương ứng với các điểm sáng hay tối, có thể khử bằng phương pháp nội suy, lọc trung vị và trung bình. * Chỉnh mức xám: Đây là kỹ thuật nhằm chỉnh sửa tính không đồng đều của thiết bị thu nhận hoặc độ tương phản giữa các vùng ảnh. * Chỉnh tán xạ: Ảnh thu nhận được từ các thiết bị quang học hay điện tử có thể bị mờ, nhoè. Phương pháp biến đổi Fourier dựa trên tích chập của ảnh với hàm tán xạ cho phép giải quyết việc hiệu chỉnh này. * Nắn chỉnh hình học: Những biến dạng hình học thường do các thiết bị điện tử và quang học gây ra. Do đó, phương pháp hiệu chỉnh ảnh dựa trên mô hình được mô tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng f(x',y') như sau:   = = ),(' ),(' yxhy yxhx y x Trong đó hx, hy là các phương trình tuyến tính (biến dạng do phối cảnh) hay bậc hai (biến dạng do ống kính camara). 1.1.2.3 Phân đoạn ảnh Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần khác nhau hay còn gọi là các đối tượng để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận dạng chữ (hoặc mã vạch) trên phong bì thư cho mục đích phân loại bưu phẩm, cần chia các câu, chữ về địa chỉ hoặc tên người thành các từ, các chữ, các số (hoặc các vạch) riêng biệt để nhận dạng. Đây là phần phức tạp khó khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ 12 thuộc rất nhiều vào công đoạn này. Kết quả của bước phân đoạn ảnh thường được cho dưới dạng dữ liệu điểm ảnh thô, trong đó hàm chứa biên của một vùng ảnh hoặc tập hợp tất cả các điểm ảnh thuộc về chính vùng ảnh đó. Trong cả hai trường hợp, sự chuyển đổi dữ liệu thô này thành một dạng thích hợp hơn cho việc xử lý trong máy tính là hết sức cần thiết, nghĩa là nên biểu diễn một vùng ảnh dưới dạng biên hay dưới dạng một vùng hoàn chỉnh gồm tất cả những điểm ảnh thuộc về nó. - Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan tâm đến các đặc trưng hình dạng bên ngoài của đối tượng, ví dụ như các góc cạnh và điểm uốn trên biên. - Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính chất bên trong của đối tượng. Ví dụ như vân ảnh hoặc cấu trúc xương của nó. Và trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết. 1.1.2.4 Biểu diễn và mô tả a) Biểu diễn Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã phân đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số liệu này thành dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính chất để thể hiện ảnh gọi là trích chọn đặc trưng (Feature Selection) gắn với việc tách các đặc tính của ảnh dưới dạng các thông tin định lượng hoặc làm cơ sở để phân biệt lớp đối tượng này với đối tượng khác trong phạm vi ảnh nhận được. Ví dụ: trong nhận dạng ký tự trên phong bì thư, chúng ta miêu tả các đặc trưng của từng ký tự giúp phân biệt ký tự này với ký tự khác. b) Mô tả Ảnh sau khi số hoá sẽ được lưu vào bộ nhớ, hoặc chuyển sang các khâu tiếp theo để phân tích. Nếu lưu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lượng bộ nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông thường, các ảnh thô đó được đặc tả (biểu diễn) lại (hay đơn giản là mã hoá) theo các 13 đặc điểm của ảnh được gọi là các đặc trưng ảnh như: biên ảnh, vùng ảnh. Một số phương pháp biểu diễn thường dùng: • Biểu diễn bằng mã chạy: Phương pháp này thường biểu diễn cho vùng ảnh và áp dụng cho ảnh nhị phân. • Biểu diễn bằng mã xích: Phương pháp này thường dùng để biểu diễn đường biên ảnh. • Biểu diễn bằng mã tứ phân: Phương pháp này được dùng để mã hoá cho vùng ảnh. 1.1.2.5 Nhận dạng và nội suy ảnh Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thường thu được bằng cách so sánh với mẫu chuẩn đã được lọc (hoặc lưu) từ trước. Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ số và nét gạch ngang trên phong bì thư có thể được nội suy thành mã điện thoại. Có nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình toán học về ảnh được phân theo hai loại nhận dạng ảnh cơ bản: - Nhận dạng theo tham số. - Nhận dạng theo cấu trúc. Một số đối tượng nhận dạng khá phổ biến hiện nay đang được áp dụng trong khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay, chữ ký điện tử), nhận dạng văn bản (Text), nhận dạng vân tay, nhận dạng mã vạch, nhận dạng mặt người… 1.1.2.6 Cơ sở tri thức Ảnh là một đối tượng khá phức tạp về đường nét, độ sáng tối, dung lượng điểm ảnh, môi trường để thu ảnh phong phú kéo theo nhiễu. Trong nhiều khâu xử lý và phân tích ảnh ngoài việc đơn giản hóa các phương pháp toán học đảm bảo tiện lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử lý ảnh theo cách của con người. Trong các bước xử lý đó, nhiều khâu hiện nay đã xử lý theo các phương pháp trí tuệ con người. Vì vậy, ở đây các cơ sở tri thức được phát huy. 14 1.1.2.7 Trích chọn đặc điểm Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong cuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn đặt ra những yêu cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc điểm đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải được trích chọn dựa trên các thủ tục phân tích dữ liệu. Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm xuống. Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây: - Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm uốn v.v.. - Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực hiện lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc điểm” (feature mask) thường là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn v.v..) - Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối tượng và do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử Gradient, toán tử la bàn, toán tử Laplace, toán tử “chéo không” (zero crossing) .. 1.1.3. Một số vấn đề cơ bản trong xử lý ảnh 1.1.3.1 Điểm ảnh (Picture Element) Gốc của ảnh là ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính, ảnh cần phải được số hoá. Số hoá ảnh là sự biến đổi gần đúng một ảnh liên tục thành một tập điểm phù hợp với ảnh thật về vị trí (không gian) và độ sáng (mức xám). Khoảng cách giữa các điểm ảnh đó được thiết lập sao cho mắt người không phân biệt được ranh giới giữa chúng. Mỗi một điểm như vậy gọi là điểm ảnh (PEL: Picture Element) hay gọi tắt là Pixel. Trong khuôn khổ ảnh hai chiều, mỗi pixel ứng với cặp tọa độ (x, y). 15 Điểm ảnh (Pixel) là một phần tử của ảnh số tại toạ độ (x, y) với độ xám hoặc màu nhất định. Kích thước và khoảng cách giữa các điểm ảnh đó được chọn thích hợp sao cho mắt người cảm nhận sự liên tục về không gian và mức xám (hoặc màu) của ảnh số gần như ảnh thật. Mỗi phần tử trong ma trận được gọi là một phần tử ảnh. 1.1.3.2 Độ phân giải của ảnh Độ phân giải (Resolution) của ảnh là mật độ điểm ảnh được ấn định trên một ảnh số được hiển thị. Khoảng cách giữa các điểm ảnh phải được chọn sao cho mắt người vẫn thấy được sự liên tục của ảnh. Việc lựa chọn khoảng cách thích hợp tạo nên một mật độ phân bố, đó chính là độ phân giải và được phân bố theo trục x và y trong không gian hai chiều. 1.1.3.3 Mức xám của ảnh Một điểm ảnh (Pixel) có hai đặc trưng cơ bản là vị trí (x, y) của điểm ảnh và độ xám của nó. Dưới đây chúng ta xem xét một số khái niệm và thuật ngữ thường dùng trong xử lý ảnh. - Mức xám của điểm ảnh là cường độ sáng của nó được gán bằng giá trị số tại điểm đó. - Các thang giá trị mức xám thông thường: 16, 32, 64, 128, 256 (mức 256 là mức phổ dụng. Lý do từ kỹ thuật máy tính dùng 1 byte (8 bit) để biểu diễn mức xám. Mức xám dùng 1 byte biểu diễn: 28=256 mức, tức là từ 0 đến 255). - Ảnh đen trắng: là ảnh có hai màu đen, trắng (không chứa màu khác) với mức xám ở các điểm ảnh có thể khác nhau. - Ảnh nhị phân: ảnh chỉ có 2 mức đen trắng phân biệt tức dùng 1 bit mô tả 21 mức khác nhau. Nói cách khác mỗi điểm ảnh của ảnh nhị phân chỉ có thể là 0 hoặc 1. - Ảnh màu: Trong hệ màu RGB (Red, Blue, Green) để tạo nên thế giới màu, người ta thường dùng 3 byte để mô tả mức màu, khi đó các giá trị màu: 28*3 = 224 ≈ 16,7 triệu màu. 16 1.1.3.4 Quan hệ giữa các điểm ảnh Một ảnh số giả sử được biểu diễn bằng hàm f(x, y). Tập con các điểm ảnh là S, cặp điểm ảnh có quan hệ với nhau ký hiệu là p, q. Chúng ta nêu một số các khái niệm sau. a) Các lân cận của điểm ảnh (Image Neighbors) * Giả sử có điểm ảnh p tại toạ độ (x, y). p có 4 điểm lân cận gần nhất theo chiều đứng và ngang (có thể coi như lân cận 4 hướng chính: Đông, Tây, Nam, Bắc). {(x-1, y); (x, y-1); (x, y+1); (x+1, y)} = N4(p) trong đó: số 1 là giá trị logic; N4(p) tập 4 điểm lân cận của p. Đông x Tây Nam (x-1,y-1) (x,y-1) (x+1,y-1) y (x-1,y) (x,y) (x+1,y) Bắc (x-1,y+1) (x,y+1) (x+1,y+1) Hình 1.3: Lân cận các điểm ảnh của tọa độ (x,y) * Các lân cận chéo: Các điểm lân cận chéo NP(p) (Có thể coi lân cận chéo là 4 hướng: Đông-Nam, Đông-Bắc, Tây-Nam, Tây-Bắc) Np(p) = { (x+1, y+1); (x+1, y-1); (x-1, y+1); (x-1, y-1)} * Tập kết hợp: N8(p) = N4(p) + NP(p) là tập hợp 8 lân cận của điểm ảnh p. * Chú ý: Nếu (x, y) nằm ở biên (mép) ảnh, một số điểm sẽ nằm ngoài ảnh. b) Các mối liên kết điểm ảnh Các mối liên kết được sử dụng để xác định giới hạn (Boundaries) của đối tượng vật thể hoặc xác định vùng trong một ảnh. Một liên kết được đặc trưng bởi tính liền kề giữa các điểm và mức xám của chúng. Giả sử V là tập các giá trị mức xám. Một ảnh có các giá trị cường độ sáng từ thang mức xám từ 32 đến 64 được mô tả như sau : 17 V={32, 33, … , 63, 64}. Có 3 loại liên kết: * Liên kết 4: Hai điểm ảnh p và q được nói là liên kết 4 với các giá trị cường độ sáng V nếu q nằm trong một các lân cận của p, tức q thuộc N4(p) * Liên kết 8: Hai điểm ảnh p và q nằm trong một các lân cận 8 của p, tức q thuộc N8(p) * Liên kết m (liên kết hỗn hợp): Hai điểm ảnh p và q với các giá trị cường độ sáng V được nói là liên kết m nếu. 1. q thuộc N4(p) hoặc 2. q thuộc NP(p) c) Đo khoảng cách giữa các điểm ảnh Khoảng cách D(p, q) giữa hai điểm ảnh p toạ độ (x, y), q toạ độ (s, t) là hàm khoảng cách (Distance) hoặc Metric nếu: 1.D(p,q) ≥ 0 (Với D(p,q)=0 nếu và chỉ nếu p=q) 2.D(p,q) = D(q,p) 3.D(p,z) ≤ D(p,q) + D(q,z); z là một điểm ảnh khác. Khoảng cách Euclide: Khoảng cách Euclide giữa hai điểm ảnh p(x, y) và q(s,t) được định nghĩa như sau: De(p, q) = [(x - s)2 + (y - t)2]1/2 Khoảng cách khối: Khoảng cách D4(p, q) được gọi là khoảng cách khối đồ thị và được xác định như sau: D4(p,q) = | x - s | + | y - t | Giá trị khoảng cách giữa các điểm ảnh r: giá trị bán kính r giữa điểm ảnh từ tâm điểm ảnh đến tâm điểm ảnh q khác. Khoảng cách D8(p, q) còn gọi là khoảng cách bàn cờ giữa điểm ảnh p, q được xác định như sau: D8(p,q) = max (| x-s | , | y-t |) 18 1.2. Toán tử không gian với xử lý ảnh Thông thường ảnh thu nhận được có nhiễu cần phải loại bỏ hay không sắc nét bị mờ hoặc cần làm tõ các chi tiết như đường biên ảnh. Các toán tử không gian dùng trong kỹ thuật tăng cường ảnh được phân nhóm theo công dụng: làm trơn nhiễu, nổi biên. Để làm trơn nhiễu hay tách nhiễu, người ta sử dụng các bộ lọc tuyến tính (lọc trung bình, thông thấp) hay lọc phi tuyến (trung vị, giả trung vị, lọc đồng hình). Từ bản chất của nhiễu (thường tương ứng với tần số cao) và từ cơ sở lý thuyết lọc là: bộ lọc chỉ cho tín hiệu có tần số nào đó thông qua do đó, để lọc nhiễu người ta thường dùng lọc thông thấp (theo quan điểm tần số không gian) hay lấy tổ hợp tuyến tính để san bằng (lọc trung bình). Để làm nổi cạnh (ứng với tần số cao), người ta dùng các bộ lọc thông cao, lọc Laplace. Trước khi xem xét chi tiết các kỹ thuật áp dụng, cần phân biệt các loại nhiễu hay can thiệp trong quá trình xử lý ảnh. Trên thực tế tồn tại nhiều loại nhiễu, tuy nhiên người ta thường xem xét 3 loại nhiễu chính: nhiễu cộng, nhiễu nhân và nhiễu xung. - Nhiễu cộng Nhiễu cộng thường phân bố khắp ảnh. Nếu gọi ảnh quan sát (ảnh thu được) là Xqs, ảnh gốc là Xgốc, nhiễu là η, ảnh thu được có thể biểu diễn bởi: Xqs = Xgốc + η - Nhiễu nhân Nhiễu nhân thường phân bố khắp ảnh và ảnh thu được sẽ biểu diễn với công thức: Xqs = Xgốc * η - Nhiễu xung Nhiễu xung thường gây đột biến tại một số điểm ảnh. 1.2.1. Làm trơn nhiễu bằng lọc tuyến tính Do có nhiều loại nhiễu can thiệp vào quá trình xử lý ảnh nên cần có nhiều bộ lọc thích hợp. Với nhiễu cộng và nhiễu nhân ta dùng các bộ lọc thông thấp, trung bình và lọc đồng hình (Homomorphie), với nhiễu xung ta dùng lọc trung vị, giả trung vị, lọc ngoài (Outlier). 19 a) Lọc trung bình không gian Với lọc trung bình, mỗi điểm ảnh được thay thế bằng trung bình trọng số của các điểm lân cận và được định nghĩa như sau: ∑∑ ∈ −−= W)l,k( )ln,km(y)l,k(a)n,m(v Nếu trong kỹ thuật lọc trên, ta chọn các trọng số bằng nhau, phương trình trên sẽ có dạng: ∑∑ ∈ −−= W)l,k( )ln,km(y N 1)n,m(v Với : y(m,m): ảnh đầu vào v(m,n): ảnh đầu ra a(k,l): là cửa sổ lọc với ak,l= N 1 và Nw là số điểm ảnh trong cửa sổ lọc W Lọc trung bình có trọng số chính là thực hiện chập ảnh đầu vào với nhân chập H. Nhân chập H trong trường hợp này có dạng:         = 1 1 1 1 1 1 1 1 1 9 1H Trong lọc trung bình, thường người ta ưu tiên cho các hướng để bảo vệ biên của ảnh khỏi bị mờ khi làm trơn ảnh. Các kiểu mặt nạ được sử dụng tùy theo các trường hợp khác nhau. Các bộ lọc trên là bộ lọc tuyến tính theo nghĩa là điểm ảnh ở tâm cửa số sẽ được thay bởi tổ hợp các điểm lân cận chập với mặt nạ. Giả sử ảnh đầu vào biểu diễn bởi ma trận:           = 2 1 6 7 5 1 7 5 7 5 3 8 1 6 6 1 7 1 7 5 1 7 3 7 4 I Ảnh số thu được bởi lọc trung bình Y = H⊗I có dạng: 20           = 11 22 33 35 24 22 34 48 48 36 27 34 49 43 36 27 31 46 39 35 16 19 31 26 23 9 1Y Lọc trung bình trọng số là một trường hợp riêng của lọc thông thấp. b) Lọc thông thấp Lọc thông thấp thường được sử dụng để làm trơn nhiễu. Trong kỹ thuật này người ta sử dụng một số nhân chập có dạng sau: Htl =         0 1 0 1 2 1 0 1 0 8 1 Hb =         + 1 b 1 b b b 1 b 1 )2b( 1 2 2 Ta dễ dàng nhận thấy khi b = 1, Hb chính là Htl (lọc trung bình). Để hiểu rõ hơn bản chất khử nhiễu cộng của các bộ lọc này, ta viết phương trình thu nhận ảnh dưới dạng: Xqs [m,n] = Xgốc [m,n] + η[m,n] Trong đó η[m,n] là nhiễu cộng có phương sai σ2n. Như vậy, theo cách tính lọc trung bình ta có: [ ] [ ] [ ] w 2 n Wl,k qs w Wl,k qs w N )ln,km(X N 1n,mY n,m)ln,km(X N 1n,mY σ+−−= η+−−= ∑ ∑ ∑ ∑ ∈ ∈ Như vậy, nhiễu cộng trong ảnh đã giảm đi Nw lần. c) Lọc đồng hình (Homomorphie Filter) Kỹ thuật lọc này hiệu quả với ảnh có nhiễu nhân. Thực tế, ảnh quan sát được 21 gồm ảnh gốc nhân với hệ số nhiễu. Gọi )n,m(X là ảnh thu được, X(m,n) là ảnh gốc và η(m,n) là nhiễu như vậy: X(m,n) = )n,m(X * η(m,n) Lọc đồng hình thực hiện lấy logarit của ảnh quan sát. Do vậy ta có kết quả sau: Log(X(m, n)) = log( X ( ,m n) ) + log( η(m, n)) Rõ ràng, nhiễu nhân có trong ảnh sẽ bị giảm. Sau quá trình lọc tuyến tính, ta chuyển về ảnh cũ bằng phép biến đổi hàm e mũ. 1.2.2. Làm trơn nhiễu bằng lọc phi tuyến Các bộ lọc phi tuyến cũng hay được dùng trong kỹ thuật tăng cường ảnh. Trong kỹ thuật này, người ta dùng bộ lọc trung vị, giả trung vị, lọc ngoài. Với lọc trung vị, điểm ảnh đầu vào sẽ được thay thế bởi trung vị các điểm ảnh còn lọc giả trung vị sẽ dùng trung bình cộng của 2 giá trị “trung vị” (trung bình cộng của max và min). a) Lọc trung vị Trung vị được viết với công thức: v(m,n) = Trungvi(y(m-k,n-l)) với {k,l} ∈ W Kỹ thuật này đòi hỏi giá trị các điểm ảnh trong cửa sổ phải xếp theo thứ tự tăng hay giảm dần so với giá trị trung vị. Kích thước cửa số thường được chọn sao cho số điểm ảnh trong cửa số là lẻ. Các cửa sổ hay dùng là cửa sổ có kích thước 3x3, hay 5x5 hay 7x7. Thí dụ: Nếu y(m) = {2, 3, 8, 4, 2} và cửa sổ W=(-1, 0, 1), ảnh thu được sau lọc trung vị sẽ là: v(m) = (2, 3, 4, 4, 2). do đó: v[0]= 2 ; v[1]=Trungvi(2,3,8)=3; v[2]=Trungvi(3,4,8)=4; v[3]= Trungvi(8,4,2)=4; v[4]= 2 . 22 * Tính chất của lọc trung vị: - Lọc trung vị là loại lọc phi tuyến. Điều này dễ nhận thấy từ: Trungvi(x(m)+y(m)) ≠ Trungvi(x(m)) + Trungvi(y(m)). - Có lợi cho việc loại bỏ các điểm ảnh hay các hàng mà vẫn bảo toàn độ phân giải. - Hiệu quả giảm khi số điểm trong cửa sổ lớn hay bằng một nửa số điểm trong cửa sổ. Điều này dễ giải thích vì trung vị là (Nw+1)/2 giá trị lớn nhất nếu Nw lẻ. Lọc trung vị cho trường hợp 2 chiều coi như lọc trung vị tách được theo từng chiều. b) Lọc ngoài (Outlier Filter) Giả thiết có ngưỡng nào đó cho các mức nhiễu (có thể dựa vào lược đồ xám). Tiến hành so sánh giá trị độ xám của một điểm ảnh với trung bình số học 8 lân cận của nó. Nếu sai lệch lớn hơn ngưỡng, điểm ảnh này được coi như nhiễu. Trong trường hợp đó, thay thế giá trị của điểm ảnh bằng giá trị trung bình 8 lân cận vừa tính được. Bộ lọc ngoài có thể diễn tả bằng công thức sau: Y(m,n) =   ≠ αα )n,m(u )w( - n)u(m, khi )w( với α(w) là trung bình cộng các điểm trong lân cận w; δ là ngưỡng ngoài Các cửa sổ tính toán thường chọn là 3x3. Tuy nhiên, cửa sổ có thể mở rộng đến 5x5 hay 7x7 để đảm bảo tính tương quan giữa các điểm ảnh. Vấn đề quan trọng là xác định ngưỡng để loại nhiễu mà vẫn không làm mất thông tin của ảnh. 1.2.3. Lọc thông thấp, thông cao và lọc dải thông Toán tử trung bình không gian là lọc thông thấp. Nếu hLP(m, n) biểu diễn bộ lọc thông thấp. FIR (Finite Impulse Response) thì bộ lọc thông cao hHP(m, n) có thể được định nghĩa: hHP(m, n) = δ(m, n) - hLP(m, n) Bộ lọc dải thông có thể định nghĩa như sau: HHP(m, n)= hL1(m, n) – hL2(m, n) 23 với hL1 và hL2 là các bộ lọc thông thấp. Bộ lọc thông thấp thường dùng làm trơn nhiễu và nội suy ảnh. Bộ lọc thông cao dùng nhiều trong trích chọn biên và làm trơn ảnh, còn bộ lọc dải thông có hiệu quả làm nổi cạnh. Về biên sẽ được trình bày kỹ trong các phần sau. Tuy nhiên, dễ nhận thấy, biên là điểm có độ biến thiên nhanh về giá trị mức xám theo quan điểm về tần số tín hiệu. Như vậy, các điểm biên ứng với các thành phần tần số cao. Từ đó, có thể dùng bộ lọc thông cao để cải thiện nhiễu nghĩa là có thể lọc các thành phần tần số thấp và giữ lại các thành phần tần số cao. Vì thế, lọc thông cao thường được dùng làm trơn biên trước khi tiến thành các thao tác với biên ảnh. Dưới đây là một số mặt nạ dùng trong lọc thông cao:        − 1- 1- 1- 1- 9 1- 1- 1- 1 )1(         0 1- 0 1- 5 1- 0 1- 0 )2(         1 2- 1 2- 5 2- 1 2- 1 )3( Các nhân chập thông cao có đặc tính chung là tổng các hệ số của bộ lọc bằng 1. Nguyên nhân chính là ngăn cản sự tăng quá giới hạn của các giá trị mức xám (các giá trị điểm ảnh vẫn giữ được giá trị của nó một cách gần đúng không thay đổi quá nhiều với giá trị thực). 1.3. Tổng quan về biên 1.3.1. Biên và các kiểu biên cơ bản Các đặc trưng của ảnh thường bao gồm các thành phần như: mật độ xám, phân bố xác suất, phân bố không gian, biên ảnh. Biên là một vấn đề chủ yếu và đặc biệt quan trọng trong phân tích ảnh vì các kĩ thuật phân đoạn ảnh chủ yếu dựa vào biên. Hiện nay có nhiều định nghĩa về biên ảnh và mỗi định nghĩa được sử dụng trong một số trường hợp nhất định. Song nhìn chung, ta có thể hiểu là: Một điểm ảnh có thể coi là biên nếu ở đó có sự thay đổi đột ngột về mức xám. Ví dụ: Đối với ảnh đen trắng, một điểm được gọi là điểm biên nếu nó là điểm đen có ít nhất một điểm trắng bên cạnh. 24 Tập hợp các điểm biên tạo thành biên, hay còn gọi là đường bao của ảnh (boundary). Chẳng hạn, trong một ảnh nhị phân, một điểm có thể được gọi là biên nếu đây là một điểm đen và có ít nhất một điểm trắng nằm trong lân cận điểm đó. Mỗi một biên là một thuộc tính gắn liền với một điểm riêng biệt và được tính toán từ những điểm lân cận nó. Đó là một biến Vector bao gồm hai thành phần: - Độ lớn của Gadient. - Hướng φ được quay đối với hướng Gradient ψ. 1.3.1.1 Biên lý tưởng Việc phát hiện biên một cách lý tưởng là việc xác định được tất cả các đường bao trong đối tượng. Biên là sự thay đổi đột ngột về mức xám nên sự thay đổi cấp xám giữa các vùng trong ảnh càng lớn thì càng dễ dàng nhận ra biên. Hình minh hoạ điểm ảnh có sự biến đổi mức xám u(x) một cách đột ngột: Hình1.4: Đường biên lý tưởng Một biên được coi đó là biên lý tưởng khi mà có sự thay đổi cấp xám lớn giữa các vùng trong ảnh. Biên này thường chỉ xuất hiện khi có sự thay đổi cấp xám qua một điểm ảnh. 1.3.1.2 Biên dốc Biên dốc xuất hiện khi sự thay đổi cấp xám trải rộng qua nhiều điểm ảnh. Vị trí của cạnh được xem như vị trí chính giữa của đường dốc nối giữa cấp xám thấp và cấp xám cao. Tuy nhiên đây chỉ là đường dốc trong toán học, từ khi ảnh được kỹ u x 25 thuật số hoá thì đường dốc không còn là đường thẳng mà thành những đường lởm chởm, không trơn. Hình 1.5: Đường biên dốc 1.3.1.3 Biên không trơn Trên thực tế, ảnh thường có biên không lý tưởng, các điểm ảnh trên ảnh thường có sự thay đổi mức xám đột ngột và không đồng nhất, đặc biệt là ảnh nhiễu. Trong trường hợp không nhiễu (biên lý tưởng), bất cứ một sự thay đổi cấp xám nào cũng thông báo sự tồn tại của một biên. Trường hợp đó khó có khả năng xảy ra, ảnh thường là không lý tưởng, có thể là do các nguyên nhân sau: - Hình dạng không sắc nét. - Nhiễu: do một loạt các yếu tố như: kiểu thiết bị nhập ảnh, cường độ ánh sáng, nhiệt độ, hiệu ứng áp suất, chuyển động, bụi…, chưa chắc rằng hai điểm ảnh có cùng giá trị cấp xám khi được nhập lại có cùng cấp xám đó trong ảnh. Kết quả của nhiễu trên ảnh gây ra một sự biến thiên ngẫu nhiên giữa các điểm ảnh. Sự xuất hiện ngẫu nhiên của các điểm ảnh có mức xám chênh lệch cao làm cho các đường biên dốc trở lên không trơn chu mà trở thành các đường biên gồ ghề, mấp mô, không nhẵn, đây chính là đường biên trên thực tế. Ngày nay, những phương pháp phát hiện biên hiện đại thường kết hợp nhiễu vào trong mô hình của bài toán và trong quá trình phát hiện biên cũng được tính đến. Còn khái niệm về biên nêu ở trên được sử dụng để xây dựng các phương pháp phát hiên biên trong quá khứ, những mô hình về cách này được coi là đơn giản và sơ sài. u x 26 Hình1.6: Đường biên không trơn 1.3.2. Vai trò của biên trong nhận dạng Đường biên là một loại đặc trưng cục bộ tiêu biểu trong phân tích nhận dạng ảnh. Người ta sử dụng đường biên làm phân cách các vùng xám (màu) cách biệt. Ngược lại, người ta cũng dùng các vùng ảnh để tìm đường phân cách. Như đã đề cập tới ở phần tổng quan về một hệ thống nhận dạng và xử lý ảnh, quá trình nhận dạng có hai giai đoạn cần thực hiện: - Giai đoạn học: Các đặc điểm của đối tượng mẫu được lưu trữ (gọi là học mẫu) và tập các phần tử mẫu được chia thành các lớp. - Giai đoạn nhận dạng: Khi có đối tượng cần nhận dạng, các đặc điểm của đối tượng sẽ được trích chọn và sử dụng hàm quyết định để xác định đối tượng cần nhận dạng thuộc lớp nào. Như vậy, việc nhận dạng sẽ chính xác nếu các đặc điểm được trích chọn chính xác. Trong thực tế, các đặc điểm trích chọn phục vụ cho việc nhận dạng thường là các bất biến [7,8,18,26,30,38,45], bởi vì vấn đề cơ bản trong bài toán nhận dạng ảnh là xác định các đối tượng không phụ thuộc vào vị trí, kích thước và hướng quay. * Có nhiều loại bất biến được trích chọn như: - Bất biến thống kê: Các mô men, độ lệch chuẩn của tập ảnh hay các độ đo thống kê khác không phụ thuộc các phép biến đổi tuyến tính. - Bất biến hình học: Số đo kích thước của các đối tượng ảnh. u x 27 - Bất biến tô-pô: Biểu diễn các cấu trúc tô-pô của các ảnh như số điểm đỉnh, số lỗ hổng v.v.. - Bất biến đại số: Chu tuyến, phân bố của các điểm ảnh, v.v.. dựa vào các việc tổ hợp các hệ số của đa thức mô tả đối tượng ảnh. Các bất biến dùng trong nhận dạng thường được trích chọn từ biên, xương của đối tượng [3,5,8,18,33,38,39,45,46,48]. Do vậy, việc nhận dạng có hiệu quả hay không phụ thuộc nhiều vào cách biểu diễn hình dạng và mô tả của vật thể. 28 CHƯƠNG II CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN CỔ ĐIỂN Biên là một phần đặc biệt quan trọng trong xử lý ảnh, hầu như trước khi sử dụng các thuật toán phát hiện biên phải trải qua một bước tiền xử lý, đó là quá trình loại bỏ nhiễu. Cơ sở của các phép toán phát hiện biên đó là quá trình biến đổi về giá trị độ sáng của các điểm ảnh. Tại điểm biên sẽ có sự biến đổi đột ngột về mức xám. Đây chính là cơ sở của kỹ thuật phát hiện biên. Xuất phát từ cơ sở này, có hai phương pháp phát hiện biên tổng quát, đó là phương pháp phát hiện biên trực tiếp và phương pháp phát hiện biên gián tiếp. 2.1. Phân loại các kỹ thuật phát hiện biên 2.1.1. Phương pháp phát hiện biên trực tiếp Phương pháp phát hiện biên này nhằm làm nổi biên dựa vào sự biến thiên về giá trị độ sáng của điểm ảnh. Kỹ thuật chủ yếu dùng phát hiện biên ở đây là kỹ thuật đạo hàm. - Nếu lấy đạo hàm bậc nhất của ảnh ta có phương pháp Gradient. Phương pháp này bao gồm kỹ thuật Gradient và kỹ thuật la bàn. - Nếu lấy đạo hàm bậc hai của ảnh ta có phương pháp Laplace. 2.1.2. Phương pháp phát hiện biên gián tiếp Là quá trình phân vùng dựa vào phép xử lý kết cấu đối tượng, cụ thể là dựa vào sự biến thiên nhỏ và đồng đều độ sáng của các điểm ảnh thuộc một đối tượng. Nếu các vùng của ảnh được xác định thì đường phân ranh giữa các vùng đó chính là biên ảnh cần tìm. Việc phát hiện biên và phân vùng đối tượng là hai bài toán đối ngẫu. Từ phát hiện biên ta có thể tiến hành phân lớp đối tượng, như vậy là đã phân 29 vùng được ảnh. Và ngược lại, khi đã phân vùng được ảnh nghĩa là đã phân lập được thành các đối tượng, từ đó có thể phát hiện được biên cần tìm. Tuy nhiên, phương pháp tìm biên trực tiếp thường sử dụng có hiệu quả vì ít chịu ảnh hưởng của nhiễu. Song nếu sự biến thiên độ sáng của ảnh là không cao thì khó có thể phát hiện được biên, trong trường hợp này việc tìm biên theo phương pháp trực tiếp tỏ ra không đạt được hiệu quả tốt. Phương pháp tìm biên gián tiếp dựa trên các vùng, đòi hỏi áp dụng lý thuyết về xử lý kết cấu đối tượng phức tạp, vì thế khó cài đặt, song đạt hiệu quả cao khi sự biến thiên về cường độ sáng là nhỏ. Trong khuôn khổ bản luận văn này ta đề cập nghiên cứu chủ yếu phương pháp phát hiện biên trực tiếp. 2.1.3. Quy trình phát hiện biên Bước 1: Do ảnh ghi được thường có nhiễu, bước một là phải lọc nhiễu theo các phương pháp đã tìm hiểu ở các phần trước. Bước 2: Làm nổi biên sử dụng các toán tử phát hiện biên. Bước 3: Định vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây nhiễu làm một số biên giả xuất hiện do vậy cần loại bỏ biên giả. Bước 4: Liên kết và trích chọn biên. 2.2. Kỹ thuật phát hiện biên Gradient Kỹ thuật Gradient là kỹ thuật dò biên cục bộ dựa vào cực đại của đạo hàm. Đây là phép toán lấy đạo hàm bậc nhất trong không gian hai chiều. Theo định nghĩa Gradient là một véctơ có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh, ta có: dy )y,x(f)dxy,x(f)y(f y )y,x(f dx )y,x(f)y,dxx(f)x(f x )y,x(f −+≈=∂ ∂ −+≈=∂ ∂ Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x, y tương ứng (thực tế chọn dx= dy=1). Đây là phương pháp dựa theo đạo hàm riêng bậc nhất theo 30 hướng x, y. Theo định nghĩa về Gradient, nếu áp dụng nó vào xử lý ảnh, việc tính toán sẽ rất phức tạp. Để đơn giản mà không mất tính chất của phương pháp Gradient, người ta sử dụng kỹ thuật Gradient dùng cặp mặt nạ H1, H2 trực giao (theo 2 hướng vuông góc). Việc xấp xỉ đạo hàm bậc nhất theo các hướng x và y được thực hiện thông qua 2 mặt nạ nhân chập tương ứng sẽ cho ta các kỹ thuật phát hiện biên khác nhau. 2.2.1. Pixel difference Đây là bộ lọc cơ bản dựa theo kỹ thuật Gradient, bộ lọc này áp dụng phương thức so sánh giữa điểm ảnh đang xét với một điểm lân cận nó (sự khác nhau giữa các điểm ảnh). Vì thế mặt nạ được sử dụng ở đây là hai mặt nạ Hx và Hy biểu thị theo hai hướng dọc (mặt nạ theo hướng x) và ngang (mặt nạ theo hướng y) như sau:         −= 0 0 0 1 1 0 0 0 0 Hx         = 0 0 0 0 1 0 0 1- 0 Hy Như vậy kỹ thuật phát hiện biên theo phương pháp này được thực hiện như sau: Sử dụng phép nhân cuộn di chuyển 2 mặt nạ trên ảnh cần tìm biên sao cho tâm chính giữa của mặt nạ trùng với điểm ảnh đang xét. Độ lớn Gradient tại điểm (i,j) được tính theo công thức: [ ] 2y2x GG)j,i(fG += Để giảm thời gian tính toán và độ phức tạp ta có xấp xỉ: G[f(i,j)] ≈ Gx + Gy ⇔ G[f(i,j)] = f(i,j) - f(i+1,j) + f(i,j) - f(i,j-1) Ta có kết quả tìm biên theo kỹ thuật này như sau: 31 a) Ảnh gốc b) Ảnh biên Hình 2.1: Biên ảnh với Pixel difference 2.2.2. Separated Pixel Difference Đây cũng là một bộ lọc cơ bản dựa theo kỹ thuật Gradient, song bộ lọc này có khác một chút so với bộ lọc Pixel diference, nó so sánh sự khác nhau giữa các điểm ảnh và ở đây là hai điểm ảnh ở hai bên của điểm ảnh đang xét. Toán tử này sử dụng mặt nạ 3 x 3, bao gồm hai mặt nạ H1 (theo chiều x) và H2 (theo chiều y) biểu thị theo hai hướng dọc và ngang như sau:         −= 0 0 0 1 0 1 0 0 0 Hx         = 0 1 0 0 0 0 0 1- 0 Hy Sử dụng phép nhân cuộn di chuyển 2 mặt nạ trên ảnh cần tìm biên sao cho tâm chính giữa của mặt nạ trùng với điểm ảnh đang xét. Giá trị điểm ảnh mới sau khi thực hiện Gradient tại điểm (i,j) được tính theo công thức: [ ] 2y2x GG)j,i(fG += G[f(i,j)] ≈ Gx + Gy ⇔ G[f(i,j)] = f(i-1,j) - f(i+1,j) + f(i,j+1) - f(i,j-1) Ta có kết quả tìm biên theo kỹ thuật này như sau: 32 a) Ảnh gốc b) Ảnh biên Hình 2.2: Biên ảnh với Separated Pixel difference 2.2.3. Toán tử Robert (1965) Trong phương pháp này hai mặt nạ được sử dụng để nhân xoắn là Hx và Hy. Phương pháp này gần giống với phương pháp Pixel difference nhưng phương pháp này thực hiện theo hai hướng -45 độ và +45 độ, chứ không theo hai hướng x và y.   = 0 1 1- 0 Hx   = 1 0 0 1- Hy Chiều dài đường biên ảnh có thể rút ra bằng cách dùng bất kỳ phép xử lý tuyến tính nào sau đây: 2 2 2 1 )j,i(y)j,i(y)j,i(y += { } { })j,i(y)j,i(y)j,i(y )j,i(y,)j,i(ymax)j,i(y 21 21 += = Trong đó: y1(i,j) và y2(i,j) là đáp ứng rút ra từ mẫu Hx và Hy Các phần tử trong mặt nạ gọi là trọng số. Di chuyển lần lượt các mặt nạ trên ảnh đang xét sao cho phần tử đầu tiên của mặt nạ trùng với phần tử (i,j) đang xét trên ảnh. Từ đó cho ra kết quả của ảnh mới theo phương pháp này. Như vậy, ta có kết quả Gradient tại một điểm ảnh (i,j): y(i,j)= |y(i,j+1)- y(i+1,j)| + |y(i,j)+y(i+1,j+1)| Kết quả của toán tử Robert sau khi tiến hành tách biên: 33 a) Ảnh gốc b) Ảnh biên Hình 2.3: Biên ảnh với toán tử Robert 2.2.4. Toán tử Prewitt Toán tử được Prewitt đưa ra vào năm 1970 có dạng:         = 1 0 1- 2 0 2 - 1 0 1- Hx         = 1 2 1 0 0 0 1- 2- 1- Hx a) Ảnh gốc b) Ảnh biên Hình 2.4: Biên ảnh với toán tử Prewitt 2.2.5. Toán tử (mặt nạ) Sobel Toán tử Sobel được Duda và Hart đặt ra năm 1973 với các mặt nạ tương tự như của Robert nhưng khác cấu hình: 34         = 1 0 1- 1 0 1- 1 0 1- Hx         = 1 1 1 0 0 0 1- 1- 1- Hy a) Ảnh gốc b) Ảnh biên Hình 2.5: Biên ảnh với toán tử Sobel 2.2.6. Toán tử Frie-Chen Phương pháp Frie-Chen được thiết kế xấp xỉ đạo hàm Gradient rời rạc. Mặt nạ Frie-Chen xử lý có hình dạng như sau:         = 1- 0 1 2 - 0 2 1- 0 1 Hx         = 1 2 1 0 0 0 1- 2- 1- Hy a) Ảnh gốc b) Ảnh biên Hình 2.6: Biên ảnh với toán tử Frie-Chen 2.2.7. Toán tử Boxcar 35 Một hạn chế chung đối với toán tử Gradient là không có khả năng phát hiện biên trong môi trường nhiều nhiễu. Điều này đặt ra vấn đề làm giảm bớt bằng việc mở rộng thêm kích thước của toán tử ra các khu lân cận thông qua vi phân đường dốc.               = 1- 1- 1- 0 1 1 1 1- 1- 1- 0 1 1 1 1- 1- 1- 0 1 1 1 1- 1- 1- 0 1 1 1 1- 1- 1- 0 1 1 1 1- 1- 1- 0 1 1 1 1- 1- 1- 0 1 1 1 Hx               = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- 1- Hy a) Ảnh gốc b) Ảnh biên Hình 2.7: Biên ảnh với toán tử Boxcar 2.2.8. Toán tử Truncated Pyramid Abdou đã đưa ra ý tưởng dùng thao tác hình chóp nón cụt cho bộ lọc tuyến tính. Toán tử được đưa ra ứng với hai chiều x và y như sau: 36               = 1- 1- 1- 0 1 1 1 1- 2- 2- 0 2 2 1 1- 2- 3- 0 3 2 1 1- 2- 3- 0 3 2 1 1- 2- 3- 0 3 2 1 1- 2- 2- 0 2 2 1 1- 1- 1- 0 1 1 1 Hx               = 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 2 3 3 3 2 1 0 0 0 0 0 0 0 1- 2- 3- 3- 3- 2- 1- 1- 2- 2- 2- 2- 2- 1- 1- 1- 1- 1- 1- 1- 1- Hy a) Ảnh gốc b) Ảnh biên Hình 2.8: Biên ảnh với toán tử Truncated Pyramid 2.3. Các toán tử la bàn Trong phương pháp Gradient, người ta chia nhỏ thành hai kỹ thuật (do dùng hai toán tử khác nhau). Đó là kỹ thuật Gradient và kỹ thuật la bàn. - Kỹ thuật Gradient như đã trình bày ở phần trước, kỹ thuật này dùng toán tử Gradient lấy đạo hàm theo một hướng. - Kỹ thuật la bàn dùng toán tử la bàn lấy đạo hàm theo tám hướng: Bắc, nam, đông , tây, đông bắc, tây bắc, đông nam, tây nam. 37 Toán tử la bàn do Gradient dựa trên sự đánh giá tất cả các hướng có thể của một đường biên ảnh trong một ảnh rời rạc. Bởi vậy thay vì chỉ áp dụng hai mặt nạ như các toán tử trong kỹ thuật Gradient ở trên, tám mặt nạ đã được dùng, mỗi cái cung cấp một cạnh đường biên dọc theo một trong tám hướng có thể của vòng. Như vậy, mỗi điểm ảnh đầu ra là giá trị lớn nhất trong tám kết quả nhân xoắn của mặt nạ với ma trận ảnh. Sau mỗi lần nhân xoắn, ta quay mặt nạ này đi một góc 450 ngược chiều kim đồng hồ : 00, 450, 900, 1350, 1800, 2250, 2700, 3150. 2.3.1 Toán tử la bàn Kirsh Phép toán này được xem như là các toán tử thuần nhất. Nó tạo ra một sự thay đổi nhỏ trong Gradient và tạo ra các sự so sánh lần lượt như các phương pháp trên. Các mặt nạ được sử dụng như sau: HĐông-Bắc =         3- 3- 3- 5 0 3- 5 5 3- HBắc =         3- 3- 3- 3- 0 3- 5 5 5 HĐông=         5 3- 3- 5 0 3- 5 3- 3- HĐông-Nam =         5 5 3- 5 0 3- 3- 3- 3- HNam =         5 5 5 3- 0 3- 3- 3- 3- HTây =         3- 3- 5 3- 0 5 3- 3- 5 HTây-Nam =         3- 5 5 3- 0 5 3- 3- 3- HTây-Bắc =         3- 3- 3- 3- 0 5 3- 5 5 Để tìm ra biên ảnh, mỗi điểm ảnh được nhân xoắn với tất cả các mặt nạ (tâm của mặt nạ trùng với điểm ảnh đang xét). Kết quả của toán tử tại mỗi điểm là giá trị lớn nhất trong tám kết quả của việc nhân xoắn. Ký hiệu Ai; i = 1,2,....,8 là Gradient theo 8 hướng như 8 mặt nạ kể trên, khi đó biên độ Gradient tại điểm ảnh (x,y) được tính theo: A(x,y) = Max(gi(x,y)) i = 1,2,...,8 38 a) Ảnh gốc b) Ảnh biên Hình 2.9: Biên ảnh với toán tử Kirsh 2.3.2 Toán tử la bàn Prewitt Cũng giống như toán tử la bàn Kirsh, toán tử la bàn Prewitt đưa ra các mặt nạ nhân cuộn theo 8 hướng khác nhau. Giá trị độ lớn của điểm ảnh mới được thực hiện như Kirsh. Các mặt nạ có dạng như sau: HĐông-Bắc =         1 1 1 1- 2- 1 1- 1 - 1 HBắc =         1 1 1 1 2- 1 1- 1 - 1- HĐông =         1- 1 1 1- 2- 1 1- 1 1 HĐông-Nam =         1- 1- 1 1- 2- 1 1 1 1 HNam =         1- 1- 1 - 1 2- 1 1 1 1 HTây =         1 1 1 - 1 2- 1 - 1 1 1- HTây-Nam =         1 1 1 - 1 2- 1 - 1 1 1- HTây-Bắc =         1 1 1 1 2- 1 - 1 1 - 1- 39 a) Ảnh gốc b) Ảnh biên Hình 2.10: Biên ảnh với toán tử la bàn Prewitt 2.3.3. Robinson 3 - Level Cũng giống như các toán tử la bàn ở trên. Robinson 3 - Level được phát triển từ toán tử Prewitt. Các mặt nạ có dạng như sau: HĐông-Bắc =         1- 1- 0 1- 0 1 0 1 1 HBắc =         1 1 1 0 0 0 1- 1- 1 - HĐông =         1- 0 1 1- 0 1 1- 0 1 HĐông-Nam =         0 1 1 1- 0 1 1- 1 - 0 HNam =         1- 1- 1 - 0 0 0 1 1 1 HTây =         1 1 0 1 0 1 - 0 1- 1- HTây-Nam =         1 0 1- 1 0 1- 1 0 1 - HTây-Bắc =         0 1- 1- 0 1 1 1 1 0 Do tính đối xứng nên trong bộ mặt nạ trên ta chỉ cần sử dụng 4 mặt nạ là đủ. 40 a) Ảnh gốc b) Ảnh biên Hình 2.11: Biên ảnh với toán tử Robinson 3 - level 2.3.4. Robinson 5 - Level Toán tử Robinson 5 - Level được phát triển từ toán tử Sobel. Các mặt nạ có dạng như sau: HĐông-Bắc =         2- 1- 0 1- 0 1 0 1 2 HBắc =         1 2 1 0 0 0 1- 2- 1 - HĐông =         1- 0 1 2- 0 2 1- 0 1 HĐông-Nam =         0 1 2 1- 0 1 2- 1 - 0 HNam =         1- 2- 1 - 0 0 0 1 2 1 HTây =         2 1 0 1 0 1 - 0 1- 2- HTây-Nam =         2 0 1- 1 0 2- 1 0 1 - HTây-Bắc =         0 1- 2- 0 1 1- 2 1 0 Do tính đối xứng nên trong bộ mặt nạ này ta cũng chỉ cần sử dụng 4 mặt nạ là đủ. 41 a) Ảnh gốc b) Ảnh biên Hình 2.12: Biên ảnh với toán tử Robinson 5 - level 2.4. Kỹ thuật phát hiện biên Laplace Để khắc phục hạn chế và nhược điểm của phương pháp Gradient, trong đó sử dụng đạo hàm riêng bậc nhất người ta nghĩ đến việc sử dụng đạo hàm riêng bậc hai hay toán tử Laplace. Phương pháp dò biên theo toán tử Laplace hiệu quả hơn phương pháp toán tử Gradient trong trường hợp mức xám biến đổi chậm, miền chuyển đổi mức xám có độ trải rộng. Toán tử Laplace được xác định như sau: 2 2 2 2 2 y f x ff ∂ ∂+∂ ∂=∇ Toán tử Laplace dùng một số kiểu mặt nạ khác nhau nhằm tính gần đúng đạo hàm riêng bậc hai. Các dạng mặt nạ theo toán tử Laplace bậc 3x3 có thể: )1y,x(f)1y,x(f)y,x(f2 y f )y,1x(f)y,1x(f)y,x(f2 x f 2 2 2 2 +−−−=∂ ∂ +−−−=∂ ∂ )1y,x(f)y,1x(f)1y,x(f)y,1x(f)y,x(f4 y f x ff 2 2 2 2 2 +−+−−−−−=∂ ∂+∂ ∂=∇ Từ đó ta đưa ra được mặt nạ nhân chập của phương pháp đạo hàm bậc hai. Kết quả này cho ra mặt nạ thứ ba gọi là phương pháp Four - neighbor Laplace (sử dụng bốn láng giềng). 42 Toán tử Laplace dùng nhiều kiểu mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm bậc hai. Dưới đây là ba kiểu mặt nạ hay dùng: H1 =         0 1- 0 1- 4 1- 0 1- 0 H2 =         1- 1- 1- 1- 8 1- 1- 1- 1- H3 =         1 2- 1 2- 4 2- 1 2- 1 Giả sử có ảnh I, khi đó tìm biên ảnh bằng cách lấy đạo hàm bậc 2 của ảnh I (phương pháp Laplace) nghĩa là nhân cuộn ảnh I với một trong 3 mặt nạ trên: Ikq = I ⊗ H Kết quả mô phỏng được thể hiện như hình sau: a) Ảnh gốc b) Ảnh biên Hình 2.13: Biên ảnh với kỹ thuật Laplace Tuy nhiên kết quả thực nghiệm cho thấy, do thực hiện phương pháp đạo hàm bậc hai cho nên kết quả rất nhạy cảm với nhiễu, để khắc phục nhược điểm này người ta mở rộng toán tử Laplace. Dùng hàm Gauss để giảm nhiễu cho ảnh (làm trơn ảnh). * Phương pháp Laplace of Gauss: Hình 2.14: Bộ lọc Laplace of Gauss Smooth Laplacian O(x,y) I(x,y) 43 Phương pháp này thực hiện như sau: - Làm trơn ảnh với bộ lọc Gauss - Tìm điểm cắt không (áp dụng bộ lọc Laplace) Ảnh kết quả: ))y,x(G*)y,x(I()y,x(O 2∇= - Hàm Gauss: + Trong 1D 2 2 2 x - e (x)g σ= Đạo hàm bậc nhất của Gauss: 2 2 2 2 2 x 2 2 x 2 e xxe2 2 1- (x)'g σ −σ− σ=σ= Đạo hàm bậc nhất của Gauss: g"(x) = 2 2 2 x 3 2 e)1x( σ − σ−σ + Trong 2D: g(x,y) = 2 22 2 yx e 2 1 σ +− σπ logσ= 2 22 2 yx 2 22 4 e2 yx11 σ +−    σ +−πσ Quá trình thực hiện: Bước 1: Làm trơn ảnh Để giảm bớt nhiễu cho ảnh, ta tiến hành làm trơn ảnh bằng bộ lọc Gauss. Việc làm trơn ảnh được thực hiện bằng cách tiến hành nhân xoắn ảnh với bộ lọc Gauss. S = I * g(x,y) = g(x,y) * I Bộ lọc Gauss có thể được xấp xỉ là các bộ lọc với kích thước ma trận khác nhau với các σ khác nhau. Như vậy để thực hiện bước 1: Ta tiến hành nhân xoắn ảnh cần xử lý với bộ lọc Gauss giống như cách thức nhân xoắn của các toán tử ta đã thực hiện ở trên. Kết quả sau khi tiến hành bước này ảnh được làm trơn. Điều này đặc biệt có tác dụng tốt 44 với ảnh nhiễu, bước này làm mờ đi ảnh cần xử lý, nghĩa là các điểm nhiễu cũng bị làm mờ đi trong khi những cạnh chính thì vẫn tồn tại. Bước 2: Tiến hành đạo hàm bậc hai Kết quả nhận được ở bước 1 là ảnh sau khi làm trơn đã loại bỏ bớt được nhiễu. Để thực hiện phương pháp Laplace of Gauss, ta tiến hành đạo hàm bậc hai kết quả ở bước 1. Việc đạo hàm kết quả này tương tự như việc ta tiến hành nhân xoắn ảnh kết quả ở bước 1 với một mặt nạ nhân xoắn được tính toán từ phương pháp Laplace. Đạo hàm bậc 2 theo hướng x Đạo hàm bậc 2 theo hướng y ∆2S = S x 2 2 ∂ ∂ + S y2 2 ∂ ∂ ∆2S =∆2(g* I) = (∆2g)* I ∆2g = 2 22 2 yx 2 22 3 e 2 yx2 2 1 σ +−    σ +−σπ Song ở bước thứ nhất ta tiến hành nhân ảnh với bộ lọc Gauss, nên ở đây ta chỉ phải đạo hàm ảnh S (không sử dụng công thức đạo hàm Gauss). Vì vậy, ta tiến hành nhân ảnh sau khi làm trơn với một trong ba mặt nạ nhân xoắn của Laplace. a) Ảnh gốc b) Ảnh biên Hình 2.15: Biên ảnh với kỹ thuật Laplace of Gauss 45 CHƯƠNG III CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN NÂNG CAO 3.1. Phương pháp Canny Phương pháp này do John Canny ở phòng thí nghiệm MIT khởi xướng vào năm 1986. Canny đã đưa một tập hợp các ràng buộc mà một phương pháp phát hiện biên phải đạt được. Ông đã trình bày một phương pháp tối ưu nhất để thực hiện được các ràng buộc đó. Và phương pháp này được gọi là phương pháp Canny. 3.1.1. Cơ sở lý thuyết thuật toán Ý tưởng thuật toán: Ý tưởng của phương pháp này là định vị đúng vị trí bằng cách cực tiểu hoá phương sai δ2 của vị trí các điểm cắt "Zero" hoặc hạn chế số điểm cực trị cục bộ để chỉ tạo ra một đường bao. Các ràng buộc mà phương pháp phát hiện biên Canny đã thực hiện được đó là: mức lỗi, định vị và hiệu suất. Trong đó: - Mức lỗi: có ý nghĩa là một phương pháp phát hiện biên chỉ và phải tìm tất cả các biên, không biên nào được tìm bị lỗi. - Định vị: Điều này nói đến độ chênh lệch cấp xám giữa các điểm trên cùng một biên phải càng nhỏ càng tốt. - Hiệu suất: là làm sao cho khi tách biên không được nhận ra nhiều biên trong khi chỉ có một biên tồn tại. Ràng buộc mức lỗi và định vị được dùng để đánh giá các phương pháp phát hiện biên. Còn ràng buộc về hiệu suất thì tương đương với mức lỗi dương. Canny đã giả thiết rằng nhiễu trong ảnh tuân theo phân bố Gauss và đồng thời ông cũng cho rằng một phương pháp phát hiện biên thực chất là một bộ lọc nhân xoắn có khả năng làm mịn nhiễu và định vị được cạnh. Vấn đề là tìm một bộ lọc sao 46 cho thoả mãn tối ưu nhất các ràng buộc ở trên. Dưới đây là việc xây dựng một bộ lọc tối ưu f được xấp xỉ bằng đạo hàm. Bộ lọc f được giả thiết f=0 ngoài đoạn (-w,+ w). Ba ràng buộc trên tương ứng với ba điều kiện như sau: 0n w w 2 0 w dx)x(f dx)x(fA SNR ∫ ∫ − −= Localization = 0n w w 2dxf )0(fA ∫ − Xzc = ∫ ∫ ∞ ∞− ∞ ∞−    π dx)x('f dx)x(f 2 2 Trong đó: SNR: (mức lỗi) nhằm tìm một hàm f(x) phản đối xứng sao cho tỷ số giữa tín hiệu và nhiễu là cực đại. Các giá trị Localization đại diện cho nghịch đảo chênh lệch mức xám giữa các điểm trong cùng một biên và càng lớn càng tốt. XZC: ràng buộc này nhằm hạn chế điểm cực trị cục bộ với mục đích cung cấp chỉ một đường bao. Canny cố gắng tìm ra bộ lọc f làm cực đại tích: SNR * Localization. Nhưng cuối cùng thì một sự sấp xỉ có hiệu quả của f lại chính là đạo hàm bậc nhất của hàm Gauss. Khi đó G có đạo hàm theo cả hai hướng x và y. Sự xấp xỉ với bộ lọc tối ưu của thuật toán phát hiện biên Canny chính là G’ và do vậy, bằng phép nhân xoắn ảnh vào với G’ ta thu được ảnh E đã được tách biên ngay cả trong trường hợp ảnh có nhiều nhiễu. Phép nhân xoắn thực hiện một cách dễ dàng trong khi việc tính toán khá phức 47 tạp, đặc biệt là nhân xoắn với mảng hai chiều. Tuy nhiên một phép nhân xoắn với mảng hai chiều Gauss có thể được chia thành hai phép nhân xoắn với mặt nạ Gauss một chiều. Việc vi phân cũng có thể được thực hiện bằng phép nhân xoắn ở mảng một chiều tạo nên hai ảnh: ảnh một là việc nhân xoắn thành phần của x với mảng một chiều, ảnh hai là việc nhân xoắn thành phần của y. 3.1.2. Hoạt động của thuật toán a)Thuật toán Thuật toán được tiến hành qua bốn bước cơ bản sau: - Đọc ảnh I cần xử lý: tiến hành làm trơn ảnh bằng cách nhân xoắn ảnh với bộ lọc Gauss. - Đạo hàm bậc nhất kết quả trên theo hai hướng x và y: Điều này tương ứng với việc nhân xoắn ảnh kết quả ở bước 1 theo hai hướng (x và y) với một bộ lọc dựa trên đạo hàm bậc nhất (các bộ lọc của kỹ thuật Gradient). Từ đó đưa ra kết quả đạo hàm ảnh sau khi tiến hành nhân xoắn với Gauss. - Cho ảnh kết quả ở bước trên tiến hành “Non-maximum Suppression” Nghĩa là loại bỏ bớt các điểm cạnh (loại bỏ bớt nhiễu), chỉ giữ lại điểm có mức xám cao. - Tiến hành thực hiện áp dụng ngưỡng (ngưỡng cao và ngưỡng thấp) để loại bỏ một số cạnh xấu. b) Giải thích thuật toán Bước thứ nhất : Tiến hành làm trơn ảnh Ở bước này chúng ta tiến hành nhân ảnh với bộ lọc Gauss. Cách thức tiến hành giống như tiến hành ở Laplace of Gauss Bước thứ hai: Tiến hành đạo hàm kết quả ở bước 1 Sau khi làm trơn ảnh ảnh ở bước 1 (nhân ảnh với bộ lọc Gauss) ta tiến hành đạo hàm bậc nhất kết quả đó. Kết quả đạo hàm S là đạo hàm của tích ảnh I và hàm Gauss (x,y). Điều này tương ứng với đạo hàm của hàm Gauss sau đó nhân với ảnh I. I*)g()I*g(S ∇=∇=∇ 48 Với:   =         ∂ ∂ ∂ ∂ =∇ y x g g y g x g g Như vậy, kết quả ảnh bước hai chính là sự tổng hợp của đạo hàm của Gauss theo hướng x nhân với ảnh I và đạo hàm của Gauss theo hướng y nhân với ảnh I. Nghĩa là ta có thể đạo hàm hàm Gauss theo hai hướng rồi mới tiến hành nhân xoắn với ảnh thay vì nhân xoắn ảnh với hàm Gauss rồi mới đạo hàm. Có thể minh hoạ như sau đạo hàm hàm Gauss theo hai hướng x và y như sau: Hình 3.1: Đạo hàm hàm Gauss theo hai hướng (x,y) Như vậy cách thức thực hiện bước thứ hai như sau: Sau khi tiến hành nhân xoắn ảnh I với bộ lọc Gauss ở bước 1 ta có một ảnh mới S được làm trơn. Tiến hành thực hiện bước hai bằng cách lấy đạo hàm ảnh mới đó theo hai hướng x và y rồi tổng hợp kết quả lại. g(x,y) gx(x,y) gy(x,y) 49 Như đã biết, phương pháp Gradient là phương pháp dò biên cục bộ dựa vào cực đại của đạo hàm, đó chính là phương pháp đạo hàm bậc nhất. Chính vì vậy ta có thể thực hiện việc đạo hàm ở bước 2 bằng cách nhân ảnh kết quả S ở bước 1 với các mặt nạ trong phương pháp Gradient dựa theo các toán tử như Sobel, Pixel Difference. Ở đây ta tiến hành nhân xoắn ảnh S với hai mặt nạ của phương pháp Sobel theo hai hướng x và y như sau: Hx =         1- 0 1 2- 0 2 1- 0 1 Hy =         1- 2- 1- 0 0 0 1 2 1 Sau khi tiến hành nhân xoắn ảnh theo hai hướng x và y ta được hai ảnh theo hai hướng là Sx và Sy, ta tiến hành tổng hợp hai kết quả đó để cho ra kết quả cuối cùng S': S' = )SS( 2y 2 x + Hướng của biên θ như sau: x y1 S S tan −=θ Ảnh S’ tìm được là kết quả của bước thứ hai. Bước thứ 3: Tiến hành Non-maximum Suppression Tức là loại bỏ một số cạnh dư thừa: Đối với mỗi điểm ảnh trên ảnh S’ ta tiến hành so sánh giá trị của điểm đó với giá trị của hai điểm lân cận điểm đó. Hai điểm lân cận này là hai điểm nằm trên đường thẳng chứa hướng của đường biên θ. Công thức tính hướng của đường biên θ nằm ở bước 2. Giả sử ta có điểm biên đang xét là tại vị trí (x,y), ta có 8 điểm biên lân cận điểm biên này như hình dưới: 50 (x-1,y-1) (x,y-1) (x+1,y-1) (x-1,y) (x,y) (x+1,y) (x- 1,y+1) (x,y+1) (x+1,y+1) Hình 3.2: Hình mô tả các điểm biên lân cận Tại điểm biên đó ta tiến hành tính giá trị góc của hướng đường biên θ. Nếu hướng của đường biên θ≤ 22.50 hoặc θ > 157.50 thì đặt giá trị của θ= 00 và khi đó hai điểm biên lân cận điểm biên này tại vị trí (x-1, y) và (x+1, y) Tương tự ta có kết quả hai điểm biên lân cận theo các hướng biên khác nhau như bảng dưới đây: Giá trị θ Phương hướng Điểm ảnh θ ≤ 22,50 hoặc θ > 157,50 θ = 00 (x-1,y) (x+1,y) 22,50 < θ ≤ 67,50 θ = 450 (x-1,y-1) (x+1,y+1) 67,50 < θ ≤ 112,50 θ = 900 (x-1,y-1) (x+1,y-1) 112,50 < θ ≤ 157,50 θ = 1350 (x,y+1) (x,y-1) Ta tiến hành thực hiện: - Tại mỗi điểm ảnh ta tiến hành tính toán hướng của đường biên, sau đó so -67,50-112,50 -157,50 -22,50 x y 22,50 67,50112,50 157,50 51 sánh kết quả đó tìm ra hai điểm biên lân cận. - So sánh giá trị điểm ảnh đang xét với hai điểm biên trên: Nếu điểm ảnh này là lớn nhất thì giữ lại điểm biên này (đánh dấu điểm biên này), ngược lại nếu nó nhỏ hơn một trong hai điểm biên lân cận thì điểm biên này bị loại đi (cho giá trị điểm biên này bằng 0) Ta được kết quả ảnh sau khi đã loại đi một số điểm biên không phù hợp, Lúc này số lượng biên trên ảnh nhìn thấy sẽ ít đi. Điều này đặc biệt có giá trị tốt để loại bỏ một số biên dư thừa đặc biệt với ảnh có nhiều nhiễu. Bước thứ tư : Tiến hành áp dụng ngưỡng: Sau khi tiến hành bước 3 ta tiến hành áp dụng ngưỡng: sử dụng hai ngưỡng, ngưỡng cao Th và ngưỡng thấp Tl . Những điểm biên được đánh dấu (không bị loại) ta tiếp tục tiến hành áp dụng ngưỡng cao và ngưỡng thấp: - Xét điểm ảnh I tại vị trí (x,y) - So sánh I(x,y) với hai ngưỡng Th và Tl + Nếu I(x,y) ≥ Th: đánh dấu và giữ lại điểm biên này (đặt giá trị bằng 1) + Nếu I(x,y) < Tl: Loại bỏ điểm biên này (đặt giá trị bằng 0) + Nếu Tl ≤ I(x,y) < Th: ta tiến hành so sánh giá trị I(x,y) với giá trị của các của 8 điểm lân cận : Nếu một trong 8 điểm lân cận có giá trị > Th: Tiến hành đánh dấu và giữ lại điểm biên này. Ngược lại: Loại bỏ điểm biên này (đặt giá trị bằng 0) Sau đây là kết quả sau khi thực hiện phương pháp phát hiện biên Canny: 52 a) Ảnh gốc b) Ảnh biên Hình 3.3: Biên ảnh theo phương pháp Canny 3.2. Phương pháp Shen - Castan Shen và Castan có cùng quan điểm với Canny về một mẫu chung trong việc tách các đường biên. Đó là: nhân xoắn ảnh với một mặt nạ làm mịn, sau đó tìm ra điểm biên. Tuy nhiên trong những phân tích của họ lại tạo ra một hàm khác để tối ưu, đó là việc đề xuất cực tiểu hoá hàm sau trong không gian một chiều: )0(f dx)x(f.dx)x(f4 C 4 0 2' 0 2 2 N ∫∫ ∞∞ = Nói một cách khác là hàm mà làm cực tiểu ở trên là bộ lọc mịn tối ưu cho việc tách biên. Tuy nhiên, Shen và Castan lại không đề cập đến việc thuật toán sẽ nhận ra được nhiều cạnh trong khi chỉ có một cạnh tồn tại. 3.2.1. Xây dựng bộ lọc tối ưu Hàm lọc tối ưu được đưa ra là bộ lọc số mũ đối xứng vô cùng Infinite Symmetric Exponential Filter (ISEF) xe 2 p)x(f = Shen - Castan cho rằng bộ lọc này đem lại tỷ lệ giữa tín hiệu và nhiễu tốt hơn bộ lọc của Canny và cung cấp sự định vị tốt hơn. Điều này có thể là đúng bởi vì trong thuật toán Canny bộ lọc tối ưu bằng xấp xỉ đạo hàm của bộ lọc Gauss, trong 53 khi đó Shen và Castan lại sử dụng bộ lọc tối ưu một cách trực tiếp, hoặc có thể do những tiêu chuẩn tối ưu mà Canny đề xuất không có tính thực tế. Tuy nhiên Shen - Castan lại không đưa ra tiêu chuẩn để đáp ứng, nên rất có thể phương pháp của họ sẽ sinh ra nhiễu và làm mờ biên. Trong không gian hai chiều, ISEF là : f(x,y) = a.e-p(|x| + |y|) Hàm lọc này là hàm thực liên tục. Công thức này có thể được áp dụng vào ảnh theo cách tương tự đã làm với đạo hàm của bộ lọc Gauss, như là lọc theo hướng x và theo hướng y. Tuy nhiên Shen-Castan đã cải tiến thêm một bước khi đưa ra bộ lọc của họ như một hàm lọc đệ quy một chiều. Trong trường hợp không liên tục, hàm học có dạng: [ ] b1 b)b1(j,if yx + −= + với b là tham số lọc (0<b<1) Để nhân xoắn một ảnh cùng với hàm lọc này thì việc lọc đệ quy được làm trước tạo r(i,j) [ ] [ ] [ ] M...1i,N...1j,1j,ibyj,iI b1 )b1(j,iy 11 ==−++ −= [ ] [ ] [ ] [ ] [ ] [ ]j,iyj,iyj,ir M...1i,N...1j,1j,ibyj,iI b1 )b1(bj,iy 21 12 += ==+++ −= Cùng với các điều kiện sau: [ ] [ ] [ ] 01M,iy 00,iy 00,iI 2 1 =+ = = Sau đó việc lọc được thực hiện theo hướng y và những tính toán trên r(i,j) sẽ tạo ra kết quả y(i,j) [ ] [ ] [ ] M...1i,N...1j,j,1ibyj,iI b1 )b1(j,iy 11 ==−++ −= 54 [ ] [ ] [ ] [ ] [ ] [ ]j,iyj,iyj,iy M...1i,N...1j,j,1ibyj,iI b1 )b1(bj,iy 21 12 += ==+++ −= Cùng với các điều kiện sau: [ ] [ ] [ ] 0j,1Ny 0j,0y 0j,0I 2 1 =+ = = Sử dụng lọc đệ quy làm tăng tốc độ nhân xoắn lên nhiều. Sau khi nhận được ảnh lọc, vấn đề đặt ra là phải phát hiện được các điểm biên. Biên được nhận dạng bằng việc tìm các giao điểm không trong đạo hàm bậc hai (của toán tử Laplace), những điểm ảnh tai vị trí này được đánh dấu. Giao điểm không tại điểm ảnh P có nghĩa rằng hai điểm láng giềng đối nhau qua giao điểm không có tín hiệu khác nhau. Ví dụ, nếu biên đi qua P là dọc thì điểm ảnh bên trái P sẽ có tín hiệu khác so với điểm ảnh ở bên phải P. Vì thế, có 4 trường hợp để kiểm tra đó là: trên/dưới, trái/ phải và hai đường chéo. Sự kiểm tra này được thực hiện bằng hàm Zezo-cross. Sau đó quá trình phân ngưỡng được thực hiện. 3.2.2. Hoạt động của thuật toán a) Thuật toán Dựa trên những phân tích ở trên, ta có thể đưa ta một thuật toán phát hiện biên Shen-Castan gồm các bước xử lý như sau: 1. Đọc ảnh từ tệp để xử lý 2. Lọc ảnh bằng phương pháp lọc đệ quy 3. Tìm các giao điểm không sau khi áp dụng toán tử Laplace 4. Thực hiện quá trình phân ngưỡng b) Giải thích thuật toán Đọc ảnh cần xử lý, rồi tiến hành lọc ảnh theo bước 2 bằng đệ quy hàm ISEF. Việc lọc được thực hiện theo chiều dọc và cả theo chiều ngang, giá trị b là tham số để lọc và được nhập bởi người sử dụng. 55 Để tìm ra được biên ảnh (bước thứ 3) ta áp dụng toán tử Laplace rồi tìm các giao điểm không. Tuy nhiên theo Shen-Castan thì sự xấp xỉ toán tử Laplace có thể thu được một cách nhanh chóng bằng việc lấy ảnh gốc trừ đi ảnh đã được làm mịn và tạo ảnh nhị phân. Nếu S là ảnh lọc và I là ảnh gốc, ta có: [ ] [ ] [ ] [ ]j,if..j,iI a4 1j,iIj,iS 22 ∇≈− Ảnh kết quả B=S-I được nhị phân hoá bằng cách đặt các điểm có giá trị dương trong ảnh B là 1 và các điểm khác là 0, các điểm nằm trên đường biên giữa các vùng có thể được coi là những điểm cạnh. Tuy nhiên, ta có thể nâng cao chất lượng việc nhận dạng các điểm biên bằng các phương pháp khác nhau như: - Phương pháp loại bỏ giao điểm không lỗi. Phương pháp này tương đương với nonmax_suppress trong Canny: tại mỗi điểm được coi là biên, đạo hàm bậc hai tại điểm này sẽ là giao điểm không. Tức là Gradient tại điểm đó hoặc là Max hoặc Min. Nếu lấy dấu đạo hàm bậc hai thay đổi từ (+) sang (-) thì giao điểm không đó là giao điểm không âm, giả thiết rằng những giao điểm không dương sẽ có Gradient dương, những giao điểm không âm sẽ có Gradient âm. Tất cả các giao điểm không khác đều là sai và không được coi là điểm biên. - Bước thứ tư trong thuật toán là phân ngưỡng: áp dụng phân ngưỡng trễ tương tự như trong thuật toán của Canny a) Ảnh gốc b) Ảnh biên Hình 3.4: Biên ảnh theo phương pháp Shen-Castan 56 3.3. Phát hiện biên dựa vào Wavelet Phương pháp này sử dụng biến đổi Wavelet rời rạc (DWT) để phân tích ảnh thành nhiều ảnh có đặc điểm và xấp xỉ. Xấp xỉ giống như ảnh gốc, theo tỷ lệ ¼, hình 3.5. Hình 3.5: Dùng DWT cho biến đổi Neurite. Xem hình 3.5 cho thấy, đặc điểm ảnh chứa thông tin biên. Ngoài ra xấp xỉ chứa nhiều thông tin biên hơn. Câu hỏi đặt ra: Tại sao không dùng xấp xỉ như là ảnh và áp dụng đệ quy DWT hai hoặc ba lần, bởi xấp xỉ cũng chứa thông tin biên, ta áp dụng đệ quy DWT cho sáu mức phân giải. Kỹ thuật nổi trội nhất là đa phân giải. Trong đó: output[n] = ∑− = 1M 0m input[n-m] x coefficient[m] Đầu vào sẽ thông báo, nó có thể tính toán với phép nhân và phép cộng. Bộ lọc liên quan với mỗi hệ số thỏa mãn tiêu chuẩn khôi phục lại đầy đủ. Đó là, bộ lọc hiện tại hủy bỏ biệt hiệu và không chia tỷ lệ cần. Hướng tín hiệu biến đổi chậm là duy trì trong kênh qua bộ lọc mức thấp, trong khi một số biến đổi nhanh là tuân theo kênh qua bộ lọc mức cao. Biên trong ảnh xuất hiện như sự biến đổi đột ngột, vì vậy lúc này quy trình là riêng biệt, tín hiệu có thể khôi phục lại bởi sự biến đổi. Xấp xỉ giống như ảnh gốc, khi đó ta bổ sung thêm nội dung, ta quay lại nơi ta bắt đầu. 57 • Với biến đổi 2-D, ta có thể lọc theo hàng, thành hai ảnh phụ tương tự, mỗi phần là nửa ảnh gốc. Chiều cao như ảnh gốc nhưng ảnh phụ có độ rộng bằng nửa. Ta lọc ảnh phụ bộ lọc thấp và cao dọc theo cột, tạo ra hai ảnh nữa thành bốn ảnh phụ. Ta gắn nhãn kết quả ảnh phụ từ tiêu chuẩn của DWT là LL(xấp xỉ), LH, HL và HH, theo bộ lọc dùng tạo ra ảnh phụ. Ví dụ, KL nghĩa là ta sử dụng qua bộ lọc cao theo hàng và qua bộ lọc thấp theo cột, cứ thế có thể lặp lại với LL, ta làm với sáu tiêu chuẩn, kiểm tra phương pháp, đặc điểm với tiêu chuẩn tiếp theo là một đến bốn kích thước của tiêu chuẩn liền trước. Quan sát hình 3.7 là một hình phụ là tìm được biên ngang, trong khi cần tìm một biên dọc nữa và đặc điểm cuối ảnh phụ là đường chéo, ta kết hợp ba đặc điểm ảnh phụ của mỗi tiêu chuẩn để xây dựng toàn bộ đặc điểm ảnh cho tiêu chuẩn. Thực hiện việc đồng dạng chứa nội dung ảnh mang lại cho ta đường biên tốt của đối tượng nội dung ảnh. Dữ liệu thể hiện ở hình 3.5 đã biến đổi từ quan sát ảnh phụ. Trước ứng dụng DWT dữ liệu là không rõ ràng, không thay đổi mức xám thì ta thường dùng chuẩn độ lệnh gán giá trị điểm ảnh như hình 3.6 và hình 3.7. Màu đen miêu tả năm độ lệnh chuẩn từ giá trị trung bình và màu trắng dùng cho giá trị còn lại. Hình 3.6: Biên ảnh của một hộp đơn Hình 3.7: Biên ảnh con chó nằm ở bậc thang 58 Qua thực nghiệm ta thấy rằng năm độ lệch chuẩn cung cấp kết quả tốt, những điểm ảnh trong phạm vi lớn tương ứng với đặc điểm ảnh phụ trong trị số lớn. Như vậy, độ lệch chuẩn được giữ lại ở phạm vi lớn. • Khi dùng DWT, ở đó một số sóng được chọn (Ta thay đổi sóng đơn bằng thay đổi hệ số bộ lọc). Ảnh gốc nhằm mục đích là thực thi DWT và tỷ lệ liên quan dò tìm biên, sau đó dùng sóng Daubechies và tìm kết quả tốt nhất, ngoài ra ta sử dụng sóng Biorthogonal. Bởi vậy, ta sử dụng Wavelet hệ số 4 Daubechies và Wavelet Biorthogonal. Bởi vì việc biến đổi sóng sử dụng nhiều giải pháp, cũng có các giải pháp kết hợp được lựa chọn để tìm ra giá trị thực của phương pháp. Điều này dường như rất tự nhiên tổng hợp kết quả đầu ra từ nhiều tiêu chuẩn. Một phương pháp đã tìm ra bản đồ n-kind: ví dụ thông qua hàng ngang, gọi 6 tiêu chuẩn và tìm nhiều hơn (n) hoặc trong trường hợp này thông thường là 2 hoặc 3 điểm ảnh. Như vậy sẽ thu được biên rõ nét, hình 3.8 và hình 3.9 chỉ ra kết quả của phương pháp này. Hình 3.8: Sử dụng 3 tiêu chuẩn cho ảnh con chó nằm bậc thang. 59 Hình 3.9: Sử dụng 3 tiêu chuẩn cho ảnh của Filopodia Một phương pháp khác đã được kiểm nghiệm thì liên kết tự động trong phương pháp này các biên rõ nét trong mỗi ảnh được phóng đại, cho phép tự động nhận dạng các vùng cần thiết. Hình 3.9, 3.10, 3.11 minh họa ảnh kết quả từ việc kết hợp ba tiêu chuẩn sử dụng liên kết tự động. Phương pháp này đưa ra hầu hết các kết quả trong các ảnh. Bởi vì sóng được phân li trong tự nhiên, số các tiêu chuẩn được giải quyết một cách phù hợp. Trong thực nghiệm, tiêu chuẩn đầu tiên chứa nhiều thông tin chi tiết nhưng chỉ một số ít được sử dụng, tiêu chuẩn thứ 2 và thứ 3 dường như chỉ phù hợp riêng với ứng dụng, từ khi chúng chứa các thông tin chi tiết thì nó chưa đề cập tới hầu hết các thay đổi nhỏ. Hình 3.10: Sử dụng liên kết tự động trong ảnh hộp đơn. 60 Hình 3.11: Sử dụng liên kết tự động trong ảnh con chó nằm bậc thang Hình 3.12: Sử dụng liên kết tự động trong của Filopodia Thực tế, công việc là biến đổi DWT thành 6 tiêu chuẩn tuy nhiên chỉ cần 3 tiêu chuẩn là đủ. Mỗi ảnh được chọn có một nguyên nhân khác nhau, hình chiếc hộp đơn, nó được chọn bởi vì thẳng và phẳng. Nó cũng được sử dụng để kiểm tra kết quả mã nguồn thực hiện có đúng và chính xác không. Hơn nữa ảnh hộp đơn đưa ra đường biên chính xác, cả hai ảnh này được xây dựng bởi chương trình. Ảnh hộp đơn và ảnh kết quả có kích cỡ 640 x 480 pixel. Khi một tiêu chuẩn của DWT đưa ra 4 ảnh con có chiều cao và chiều rộng bằng một nửa của tiêu chuẩn bên trên, kích cỡ phù hợp của ảnh con là 20 x15 tại 6 tiêu chuẩn. Ảnh tiếp theo con chó trên bậc 61 thang được chọn vì nó đổ bóng và chi tiết. Đường biên chính xác của ảnh được tạo bằng tay. Ảnh này có kích cỡ là 256 x256 và kích cỡ phù hợp của ảnh con tại 6 tiêu chuẩn là 8 x8. Hiện thời phép đo được thực hiện thông dụng cho một ảnh. Một nhà sinh vật học đã đưa ra ảnh trả lời chính xác. Trong ảnh này chỉ có filopodia phù hợp được thể hiện. Ảnh trả lời có kích thước là 480 x 640 pixel. Trong tất cả các ảnh được sử dụng bởi 6 tiêu chuẩn thì các thông tin hữu ích là ảnh mờ hoàn chỉnh. Trên thực tế, ta tìm thấy bằng thực nghiệm kết quả tốt chỉ bằng ba tiêu chuẩn đầu tiên. Thông tin biên dường như là tín hiệu của những biến đổi chính trong ảnh nó đã được đưa ra trong các tiêu chuẩn trước đó. 62 CHƯƠNG IV MỘT SỐ NHẬN XÉT VÀ ĐÁNH GIÁ CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN Để có được những đánh giá một cách khách quan, có những minh chứng cụ thể bằng hình ảnh, từ các phương pháp phát hiện biên đã trình bày ta tiến hành cài đặt chương trình thử nghiệm các phương pháp phát hiện biên. Trên cơ sở đó đưa ra các nhận xét đánh giá về phương pháp đã trình bày trong luận văn. Bằng cách tìm hiểu những lỗi mà thuật toán phát hiện biên có thể mắc phải ta có thể rút ra phương pháp phát hiện biên phù hợp nhất. Thông thường những lỗi mà một thuật toán phát hiện biên có thể phạm phải là: Lỗi âm: Một thuật toán phát hiện biên có thể không thông báo một cạnh trong khi nó tồn tại. Lỗi dương: Một thuật toán phát hiện biên có thể thông báo về một cạnh trong khi nó không tồn tại. Điều này có thể do nhiễu hoặc do việc thiết kế thuật toán sơ sài hoặc do quá trình phân ngưỡng. Vì thế vị trí của một điểm biên có thể bị nhầm. Sau đây sẽ là đánh giá về một số phương pháp phát hiện biên dựa theo các kết quả thực nghiệm: 4.1. Phương pháp phát hiện biên dựa vào kỹ thuật Gradient Các phương pháp sử dụng trong kỹ thuật Gradient giống nhau về cách thức thực hiện song các toán tử dùng để nhân xoắn lại khác nhau. So sánh các kết quả từ các phương pháp: Kỹ thuật này sử dụng nhiều toán tử đạo hàm khác nhau với các kích thước ma trận khác nhau. 63 a) Ảnh gốc không nhiễu b) Ảnh gốc nhiễu c) Kết quả phát hiện biên với Pixel Difference d) Kết quả phát hiện biên với Separated Pixel Difference e) Kết quả phát hiện biên với Robert 64 f) Kết quả phát hiện biên với Sobel g) Kết quả phát hiện biên với Prewitt h) Kết quả phát hiện biên với Frie -Chen i) Kết quả phát hiện biên với Boxcar 65 j) Kết quả phát hiện biên với Truncated-Pyramid Hình 4.1: Hình mô phỏng kết quả tìm biên theo kỹ thuật Gradient Qua hình ảnh kết quả mô phỏng ở trên ta thấy: - Phương pháp Pixel Difference: Phương pháp này cho kết quả xấu nhất trong các kết quả. Đây là phương pháp phát hiện biên cơ bản nhất trong các phương pháp. Do ma trận dùng để nhân xoắn trong phương pháp này có kích thước nhỏ và đối với mỗi điểm ảnh chỉ sử dụng trung bình cục bộ của điểm đó với hai điểm lân cận (một theo hướng x và một theo hướng y). Chính vì thế mà phương pháp này cho kết quả kém. - Phương pháp Robert: Cũng giống như phương pháp phát hiện biên Pixel Difference, phương pháp này cũng sử dụng ma trận nhân xoắn nhỏ, song cho kết quả tốt hơn phương pháp trên là do phương pháp này nhân xoắn ảnh với hai ma trận theo hai hướng +450 và -450 (hai đường chéo của ma trận 2*2). Nghĩa là giá trị tại mỗi điểm ảnh sẽ là kết quả trung bình cục bộ của bốn điểm ảnh (điểm ảnh đó và 3 điểm lân cận). Vì thế, phương pháp phát hiện biên này cho kết quả tốt hơn phương pháp phát hiện biên Pixel Difference. Phương pháp phát hiện biên Separated Pixel Difference cho kết quả tốt hơn phương pháp Pixel Difference. Cũng giống như phương pháp Pixel Difference, nhưng phương pháp này sử dụng hai điểm lân cận. - Các phương pháp phát hiện biên như Sobel, Prewitt, Frie-chen cho kết quả 66 tương đối như nhau và tốt hơn ba phương pháp trên. Ba phương pháp này sử dụng mặt nạ 3* 3 để nhân xoắn. - Tuy nhiên các phương pháp vừa nêu trên (Robert, Pixel, Sobel...) đều cho kết quả không tốt đối với ảnh nhiễu. Còn phương pháp Boxcar và Truncated Pyramid lại cho kết quả rất tốt đối với ảnh nhiễu. Nhưng đối với ảnh ít nhiễu (không nhiễu) thì hai phương pháp phát hiện biên này lại cho kết quả không được tốt lắm . Hai phương pháp Boxcar và Truncated Pyramid sử dụng mặt nạ nhân cuộn là 7*7. Đây là ma trận tương đối lớn, một điểm ảnh phải xét đến 48 điểm lân cận nó. Chính vì thế mà đối với ảnh không nhiễu thì số lượng các biên trong ảnh sẽ tăng lên, biên nhìn thấy thường lớn hơn bình thường và ta thường thấy ảnh nhoè đi. Còn đối với ảnh có nhiễu thì chính nhờ xét đến 48 điểm ảnh lân cận điểm ảnh đang xét mà các điểm nhiễu bị làm mờ đi, do đó mà ảnh thu được từ phương pháp này cho kết quả rất tốt, các điểm nhiễu bị loại bớt. - Tuy nhiên, mỗi phương pháp có những ưu và nhược điểm riêng. Mặc dù phương pháp Robert, Pixel Difference.. cho kết quả không tốt nhưng lợi thế của nó lại là có tốc độ xử lý nhanh. Còn hai phương pháp Boxcar và Truncated Pyramid thì cho kết quả tốt với ảnh nhiễu nhưng lại có tốc độ xử lý chậm hơn. Chính vì vậy tuỳ điều kiện chất lượng ảnh đầu vào, tuỳ yêu cầu về chất lượng hay tốc độ xử lý mà ta có sự lựa chọn các phương pháp phát hiện biên phù hợp. 4.2. Phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai So sánh sự khác nhau của phương pháp đạo hàm bậc nhất (Sobel) và phương pháp đạo hàm bậc hai (Laplace) ta có: Ảnh ở dưới đây bao gồm một ảnh tốt (có thể coi là không nhiễu), và một ảnh bị nhiễu. 67 a) Ảnh gốc không nhiễu b) Ảnh gốc nhiễu c) Kết quả phát hiện biên với Pixel Difference d) Kết quả phát hiện biên với Sobel e) Kết quả phát hiện biên với Four - Neighbor Laplace 68 f)Kết quả phát hiện biên với Eight - Neighbor Laplace Hình 4.2: Biên ảnh theo đạo hàm bậc nhất và bậc hai Để nhận xét sự khác nhau của hai phương pháp, đối với đạo hàm bậc nhất ta chọn kết quả của phương pháp Pixel Difference (là phương pháp cho kết quả kém nhất trong các phương pháp đạo hàm bậc nhất) và Sobel (là phương pháp cho kết quả rất tốt trong phương pháp đạo hàm bậc nhất), còn đối với phương pháp đạo hàm bậc hai thì ta sử dụng hai kết quả của Four - Neighbor Laplace và Eight-neighbor Laplace. * Đối với ảnh không nhiễu: - Các kết quả ở cả hai phương pháp cho kết quả tương đối tốt. Tuy nhiên cả hai phương pháp có sự khác nhau. Các biên ở phía ngoài, độ sáng thay đổi rõ nét thì phương pháp Gradient làm việc khá tốt, còn biên ở phía bên trong, mức xám thay đổi chậm, miền chuyển tiếp trải rộng thì phương pháp đạo hàm bậc hai cho biên rõ nét hơn. - Ngoài ra, ta nhận thấy ảnh kết quả nhận được ở phương pháp đạo hàm bậc hai cho kết quả biên mảnh hơn phương pháp đạo hàm bậc nhất. Nguyên nhân của điều này là trong kỹ thuật Laplace, điểm biên được xác định bởi điểm cắt điểm không, và do đây là phương pháp đạo hàm bậc hai nên điểm không là duy nhất, do đó kỹ thuật này cho đường biên mảnh. * Đối với ảnh nhiễu: - Kết quả cho thấy cả hai toán tử ta sử dụng trong phương pháp Gradient cho kết quả tốt hơn trong hai kết quả của phương pháp Laplace (mặc dù phương pháp Pixel Difference hoạt động rất kém), phương pháp Sobel cho kết quả tốt nhất, còn hai kết quả của phương pháp Laplace thì cho kết quả rất xấu, hầu như không nhìn thấy biên. 69 Phương pháp đạo hàm bậc hai rất nhạy cảm với nhiễu và tạo nên biên kép vì thế đối với ảnh nhiễu thì phương pháp đạo hàm bậc nhất hoạt động hiệu quả hơn. Đối với ảnh không nhiễu, mức xám thay đổi đột ngột thì cả hai phương pháp đạo hàm bậc nhất và đạo hàm bậc hai đều cho độ chính xác cao. Còn khi mức xám trải rộng thì phương pháp đạo hàm bậc hai hoạt động tốt hơn. Đối với ảnh nhiễu: Phương pháp đạo hàm bậc hai cho kết quả không tốt. Trong trường hợp này, ta nên sử dụng phương pháp đạo hàm bậc nhất (phương pháp Sobel) 4.3. Đánh giá nhận xét về phương pháp Canny Phương pháp Canny được sử dụng rất nhiều trong các ứng dụng của xử lý ảnh do đây là phương pháp có khả năng loại bỏ nhiễu rất tốt. Ở đây ta đánh giá phương pháp Canny với độ lệch tiêu chuẩn σ khác nhau và các ngưỡng khác nhau: Khi ta thay đổi σ, ngưỡng cao và ngưỡng thấp vẫn giữ nguyên: Th=100 và Tl =30 ta có kết quả : a) Ảnh gốc b) σ = 0,8 c) σ = 1 d) σ = 1,4 Hình4.3: Phát hiện biên với Canny ngưỡng cố định Th=100 và Tl =30 70 Qua kết quả ở trên ta có thể đưa ra một số nhận xét sau: - Khi ta thay đổi độ lệch tiêu chuẩn σ thì ảnh kết quả cũng thay đổi. Ảnh kết quả (b), (c), (d) với độ lệch tiêu chuẩn tương ứng là 0,8; 1,0 và 1,4 cho ra các điểm biên khác nhau. Ảnh (b) có số lượng điểm biên cao nhất, còn ảnh (d) có số lượng điểm biên thấp nhất. - Càng tăng độ lớn của độ lệch tiêu chuẩn thì số lượng các điểm biên xác định được ngày càng giảm. Nghĩa là đối với ảnh có nhiều nhiễu thì càng tăng độ lệch tiêu chuẩn thì số lượng điểm nhiễu cũng giảm đi, khi đó chỉ những biên rõ nét mới phát hiện ra. a) Th =50; Tl =30 b) Th =200; Tl =100 c) Th =200; Tl =30 d) Th =250; Tl =200 Hình 4.4: Phát hiện biên với Canny ngưỡng thay đổi, σ = 1 - Khi thay đổi ngưỡng thấp và ngưỡng cao thì số lượng biên được phát hiện cũng thay đổi. Do các điểm ảnh có giá trị nhỏ hơn ngưỡng thấp thì loại điểm đó và lớn hơn ngưỡng cao thì xác định đó là điểm biên (giữa hai ngưỡng thì còn tuỳ thuộc 71 vào các điểm biên lân cận). Nên ta thấy: - Khi ngưỡng thấp và ngưỡng cao đều thấp thì số lượng biên phát hiện ra rất nhiều . - Khi cả hai ngưỡng đều cao thì số lượng điểm biên được phát hiện là rất ít, chỉ những điểm có mức xám cao mới có thể thành biên. Khi ngưỡng rất thấp và ngưỡng rất cao, tức là khoảng cách giữa hai ngưỡng là lớn thì điểm biên phụ thuộc vào các điểm lân cận. Tuỳ từng ảnh cụ thể và tuỳ từng cách lấy ngưỡng khác nhau mà ta có các kết quả khác nhau. 4.4. Các phương pháp phát hiện biên (phương pháp Gadient, phương pháp Laplace, phương pháp Canny) Sau đây là đánh giá tổng hợp về các phương pháp phát hiện biên: Để so sánh sự khác nhau giữa các phương pháp phát hiện biên, chúng ta sử dụng kết quả của phương pháp phát Sobel đại diện cho phương pháp đạo hàm bậc nhất, sử dụng kết quả của Eight-neighbor Laplace đại diện cho phương pháp phát hiện biên Laplace (phương pháp đạo hàm bậc hai) và sử dụng σ =1,4; Th=100, Tl=50 đại diện cho phương pháp Canny. Từ các kết quả thu được ở hình trên, ta có một số nhận định về các phương pháp phát hiện biên như sau: * Đối với ảnh không nhiễu: Cả ba phương pháp đều cho kết quả tốt. Song phương pháp phát hiện biên Sobel cho biên rõ nét nhưng lớn, còn phương pháp Laplace cho kết quả rõ nét, biên mảnh. Riêng phương pháp Canny do quá trình làm trơn ảnh nên từ một ảnh không nhiễu, các biên mờ bớt đi và to ra. Do vậy biên ảnh trong phương pháp Canny lớn nhưng lại không đầy đủ. Đối với loại ảnh này khi tìm biên nên áp dụng phương pháp Laplace, tiếp đến là phương pháp đạo hàm bậc nhất (Sobel, Kirsh, Prewitt...). Không nên sử dụng phương pháp Canny trong trường hợp này. 72 a) Ảnh gốc không nhiễu b) Ảnh gốc nhiễu c)Kết quả phát hiện biên với Sobel d) Kết quả phát hiện biên với Laplace e) Kết quả phát hiện biên với Canny σ =1,4; Th =250; Tl =200 Hình 4.5: Biên ảnh theo Gradient, Laplace, Canny 73 * Đối với ảnh có nhiều cạnh: Khi phát hiện biên, các cạnh không quan trọng nên được loại bỏ. Ở đây, phương pháp Sobel vẫn phát hiện được biên nhưng các biên mờ, không được rõ nét, do trong ảnh có những vùng có mức xám thấp, sự thay đổi giữa các mức xám nhỏ . Chính vì vậy mà ảnh qua phương pháp Laplace cho kết quả rõ nét hơn (do phương pháp này sử dụng phương pháp đạo hàm bậc hai, các điểm biên là các điểm cắt không). Tuy vậy do ảnh có rất nhiều điểm biên nhỏ nên các biên ảnh ở trên qua phương pháp này rất nhiều và rối, chúng ta nên loại bỏ các điểm biên thừa. Còn đối với phương pháp Canny, do quá trình “Non-maximum Suppression” và do quá trình áp dụng ngưỡng mà các điểm biên phụ bị loại bớt đi, các biên chính được giữ lại nên biên rõ nét hơn. Đối với ảnh có nhiều có mức xám nhỏ, sự biến thiên các mức xám là thấp ta nên sử dụng phương pháp Laplace, song nếu ảnh đó có quá nhiều biên thì ta nên sử dụng phương pháp Canny để loại bỏ bớt các cạnh không cần quan tâm đi. * Đối với ảnh có nhiều nhiễu: Phương pháp đạo hàm bậc nhất cho biên ảnh với nhiều điểm biên phụ. Còn phương pháp Laplace thì tạo biên kép nên hoàn toàn không xác định được biên. Còn đối với phương pháp Canny thì do quá trình làm trơn ảnh cho bớt nhiễu và quá trình “Non-maximum Suppression” để giảm bớt các biên phụ nên ảnh kết quả của phương pháp này rất rõ nét. Vì vậy đối với ảnh có nhiều nhiễu thì ta nên sử dụng phương pháp Canny để loại bỏ nhiễu và các điểm biên phụ không cần quan tâm, chỉ giữ lại các điểm biên chính theo mục đích sử dụng khác nhau. 4.5. Đánh giá nhận xét về phương pháp Wavelet Chúng ta tạo ra phương pháp được miêu tả trong phần này để so sánh với các phương pháp phát hiện biên. Các ảnh kết quả chính xác thu được bằng cách bắt đầu từ các ảnh gốc và được đánh dấu các cạnh bằng tay bởi con người. Tất cả các tỉ lệ được lấy từ các điểm ảnh chính xác này. Sự quyết định được tốc độ là rất chi tiết 74 bởi vì chúng ta cần các thông tin thừa hơn là thiếu thông tin. Bất cứ thông tin kết quả này thừa bên ngoài ảnh có thể cực tiểu hóa bằng cách định vị nhiễu và loại bỏ nó. Chúng ta sẽ không đổ lỗi cho thuật toán khi kết quả tìm được không nằm trong vùng mà chúng ta mong muốn. * Đánh dấu đường biên Như đã trình bày, phát triển một chương trình sử dụng DWT để tìm biên của một ảnh. Do đó, như kết quả của công việc này, một thuật toán đánh dấu đường biên được phát triển để thiết lập biên xung quanh đối tượng. Sau đó chúng ta xác định đối tượng có quan trọng hay không (thông qua một hàm ngưỡng). Một số điểm nhỏ được tìm thấy và chương trình sẽ đánh dấu một cách cẩn thận theo các biên. Khi một điểm được đánh dấu xong, mối liên hệ kích cỡ của đối tượng được xác định từ đường biên này. Hình 4.6: Phát hiện biên theo phương pháp Wavelet Với việc phát hiện biên sử dụng phương pháp Wavelet và sự kết hợp giữa chúng đạt được kết quả rất tốt. Khi sử dụng chức năng lọc nó cân bằng với việc nhận ra biên của phương pháp Canny. Thuật toán của sự biến đổi Wavelet giống sự biến đổi biên của Canny. Bằng những hình ảnh thực tế ta thấy phát hiện biên sử dụng Wavelet có thể thu được rất nhiều thông tin về biên. Bên cạnh việc phát hiện tìm ra biên tốt thì phương pháp này cũng bộ lộ nhược điểm là mức độ tính toán phức tạp. Tốc độ xử lý chậm hơn so với các phương pháp đã trình bày. 75 KẾT LUẬN Trong quá trình nghiên cứu tài liệu và thực hiện luận văn dưới sự định hướng của thầy hướng dẫn luận văn đã đạt được một số kết quả như sau: - Tìm hiểu được một cách tổng quan các vấn đề về XLA và phát hiện biên ảnh. Hệ thống hoá các phương pháp phát hiện biên. Đưa ra nhận xét, đánh giá các phương pháp phát hiện biên và có lựa chọn phương pháp phù hợp với từng loại ảnh. - Đặc biệt việc phát hiện biên sử dụng phương pháp Wavelet và sự kết hợp giữa chúng đã phần nào đạt kết quả tốt hơn trong việc phát hiện biên nhưng chúng vẫn còn bộc lộ một số nhược điểm cần phải khắc phục. - Bằng cách hiểu bản chất của từng phương pháp, tôi đã cài đặt và chạy thử nghiệm đối với một số phương pháp phát hiện biên. - Ngoài ra, trong quá trình nghiên cứu tôi cũng tự tích lũy thêm cho mình các kiến thức về toán học, về kỹ thuật lập trình,…Và quan trọng là rèn luyện kỹ năng để thực hiện một nghiên cứu khoa học. Tuy mới chỉ là bước đầu, nhưng những kết quả này sẽ giúp ích cho tôi trong những nghiên cứu sau này để thu được những kết quả tốt hơn Dựa trên những kết quả bước đầu đã đạt được trong luận văn, tiếp tục nghiên cứu đề xuất một số cải tiến phương pháp phát hiện biên hiệu quả hơn trong tương lai. - Đối với phương pháp Wavelet sẽ tiếp tục nghiên cứu để giảm độ phức tạp tính toán của phương pháp Wavelet. Vấn đề này có thể được giải quyết bởi việc chỉ sử dụng những cặp điểm liên quan nhất trong quá trình so sánh. Tiếp tục nghiên cứu các đặc điểm về hình dạng, các đặc điểm màu sắc và kết cấu để tăng hiệu quả cho đánh dấu tìm đường biên. - Xây dựng một ứng dụng xử lý ảnh hoàn chỉnh dựa theo các phương pháp phát hiện biên đã trình bày trong luận văn. 76 TÀI LIỆU THAM KHẢO Tiếng việt [1] Lương Mạnh Bá, Nguyễn Thanh Thuỷ (1999), “Nhập môn xử lý ảnh số”, Nxb KH&KT. [2] Phạm Việt Bình (2006) "Phương pháp xử lý biên và ứng dụng trong nhận dạng đối tượng ảnh", Luận án tiến sỹ. [3] Võ Đức Khánh, Hoàng Văn Kiếm. "Giáo trình xử lý ảnh số". Nhà xuất bản Đại học Quốc gia Thành phố Hồ Chi Minh. [4] Hoàng Kiếm, Nguyễn Ngọc Kỷ và các tác giả (1992), "Nhận dạng các phương pháp và ứng dụng", Nhà xuất bản thống kê . [5] Kỉ yếu hội thảo quốc gia (2000), “Một số vấn đề chọn lọc của công nghệ thông tin”, Nxb KH&KT. [6] Nguyễn Kim Sách (1997), "Xử lý ảnh và Video số", Nhà xuất bản Khoa học và Kỹ thuật. [7] Ngô Quốc Tạo (1996), “Nâng cao hiệu quả của một số thuật toán nhận dạng ảnh”, Luận án Phó tiến sỹ. [8] Ngô Quốc Tạo (2003), “Bài giảng môn Xử lý ảnh, dành cho lớp Cao học Công nghệ Thông tin”, Khoa Công nghệ Thông tin - Đại học Thái Nguyên. [9] Ngô Quốc Tạo, Đỗ Năng Toàn (2001), “Tách bảng dựa trên tập các hình chữ nhật rời rạc”, chuyên san Các công trình nghiên cứu và triển khai Công nghệ thông tin và viễn thông, Tạp chí Bưu chính viễn thông. [10] Đỗ Năng Toàn (2000), "Một thuật toán phát hiện vùng và ứng dụng của nó trong quá trình véc tơ hoá tự động", Tạp chí Tin học và Điều khiển học. [11] Đỗ Năng Toàn (2002), "Biên ảnh và một số tính chất", Tạp chí Khoa học Công nghệ, Tập 40, số ĐB, tr 41-48. [12] Đỗ Năng Toàn, Ngô Quốc Tạo (1998), "Kết hợp các phép toán hình thái học và làm mảnh để nâng cao chất lượng ảnh đường nét", Tạp chí Tin học và Điều khiển học, Tập 14, số 3, tr 23-29. 77 [13] Nguyễn Quốc Trung (2004), "Xử lý tín hiệu và lọc số", Nhà xuất bản Khoa học và Kỹ thuật. [14] Một số địa chỉ khác trên internet... Tiếng Anh [15] Adnan Amin, Stephen FischerTony Pakinson and Ricky Shiu (1998), “Fast Algorithm for skew detection”, School of Computer Sience and Engineering University of New Shouth Wales, NSW, Sydney, 2052, Australia. [16] Anil K. Jain (1989), Fundamental of Digital Image Processing. Prentice Hall, Engwood cliffs. [17] H.-F.Jiang, C.-C.Han, and K.-C.Fan (1997), “A fast approach to the detection and correction of skew documents”. Pattern Recognition Letters, Vol.18, No.7, pp.675-686, 1997. [18] Joannis Pitas (1992), "Digital Image Processing Algorithms", Prentice Hall, New York. [19] Lu Y and C L Tan (2003), “A nearest-neighbor-chain based approach to skew estimation in document images”, Pattern Recognition Letters, vol.24, pp.2315-2323. [20] Toumazet J.J., Traitement de l’Image par Exemple, Symbex, Chaptre 5, "Images Binaires Operateurs Morphologiques", pp 117-139, 1990.