Luận văn Thạc sĩ Công nghệ thông tin: Nghiên cứu một số phương pháp phát hiện biên

Chia sẻ: Vo Danh | Ngày: | Loại File: PDF | Số trang:77

Thêm vào BST

Báo xấu

195
lượt xem 71
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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, chương II - Các phương pháp phát hiện biên cổ điển, chương III - Các phương pháp phát hiện biên nâng cao, chương IV - Một số nhận xét đánh giá các phương pháp phát hiện biên. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: 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
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 2
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 3
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. 4
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 5
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 6
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. 7
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 8
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. Ảnh tốt hơn Xử lý ảnh Ảnh đầu vào 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). 9
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: Biểu diễn và Phân đoạn mô tả ảnh Tiền xử lý ảnh CƠ SỞ Nhận dạng và TRI THỨC nội suy Thu nhận ảnh (Scaner, sensor, camera) 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. 10
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:  x' = hx ( x, y )   y ' = hy ( x , y ) 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ụ 11
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 12
đặ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. 13
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). 14
Đ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. 15
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 (x-1,y-1) (x,y-1) (x+1,y-1) Nam (x-1,y) (x,y) (x+1,y) y (x-1,y+1) (x,y+1) (x+1,y+1) Bắc 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 : 16
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 |) 17
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). 18
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: v ( m, n ) = ∑ ∑ a ( k , l ) y ( m − k , n − l) ( k ,l )∈W 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: 1 ∑ ∑ y ( m − k , n − l) v ( m, n ) = N ( k ,l )∈W Với : y(m,m): ảnh đầu vào v(m,n): ảnh đầu ra a(k,l): là cửa sổ lọc 1 với ak,l= và Nw là số điểm ảnh trong cửa sổ lọc W N 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 H = 1 1  9 1 1 1   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: 4 7 3 7 1 5 7 1 7 1   I = 6 6 1 8 3   5 7 5 7 1 5 7 6 1 2   Ảnh số thu được bởi lọc trung bình Y = H⊗I có dạng: 19
23 26 31 19 16  35 39 46 31 27  1  Y = 36 43 49 34 27  9  36 48 48 34 22 24 35 33 22 11    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: 0 1 0  1 Htl = 1 2 1  8 0 1 0    1 b 1    1 b b 2 b Hb = 2 ( b + 2) 1 b 1    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ó: 1 Y[m, n ] = (m − k , n − l) + η[m, n ] ∑ ∑X qs Nw k ,l∈W σ2 1 Y[m, n ] = ∑ ∑ X qs (m − k, n − l) + n Nw Nw k ,l∈W 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 20