›

Đồ án Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu - Đặng Thị Thương

pdf 61 trang huongle 1730
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu - Đặng Thị Thương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_tim_hieu_phuong_phap_phat_hien_bien_cho_anh_da_cap_xam.pdf

Nội dung text: Đồ án Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu - Đặng Thị Thương

  1. Đề tài: Tìm hiểu phƣơng pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu. Giáo viên hƣớng dẫn: PGS. TS. Ngô Quốc Tạo Sinh viên thực hiện: Đặng Thị Thƣơng.
  2. 2 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu LỜI CẢM ƠN Đầu tiên em xin gửi lời cảm ơn chân thành và trân trọng nhất tới PQS TS Ngô Quốc Tạo, người đã trực tiếp hướng dẫn, giúp đỡ em trong việc hình thành, phát triển và hoàn thành đồ án tốt nghiệp này. Em cũng xin gửi lời cảm ơn trân trọng tới các thầy cô giáo trong khoa Công nghệ thông tin – Đại học Dân lập Hải Phòng, những người đã tân tình dạy dỗ và dìu dắt em trong suốt bốn năm học vừa qua để chúng em có những kinh nghiệm, kiến thức vững chắc để hoàn thành đồ án tốt nghiệp này. Em xin chân thành cảm ơn gia đình, bạn bè đã luôn động viên, giúp đỡ em về mọi mặt trong quá trình học tập và nghiên cứu, cũng như góp ý cho đồ án tốt nghiệp. Em rất mong nhận được sự khích lệ, quan tâm, giúp đỡ của các quý thầy cô và các bạn trong quá trình học tập và công tác sau này, em rất mong muốn được mang một công sức, kiến thức của mình để xây dựng xã hội, xứng đáng với sự giúp đỡ và tình cảm mà mọi người đã dành cho em. Em xin chân thành cảm ơn! Hải Phòng, tháng năm 2011 Sinh viên Đặng Thị Thương Sinh viên: Đặng Thị Thương – Lớp CT1101
  3. 3 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu MỤC LỤC MỤC LỤC 3 DANH SÁCH CÁC HÌNH ẢNH 5 MỞ ĐẦU 6 CHƢƠNG I: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN 8 1.1. Tổng quan về xử lý ảnh 8 1.1.1 Xử lý ảnh là gì ? 8 1.1.2 Các quá trình cơ bản trong hệ thống xử lý ảnh 8 1.1.3 Một số vấn đề cơ bản trong xử lý ảnh 11 1.2 Nâng cao chất lượng ảnh và toán tử không gian 15 1.2.1 Làm trơn nhiễu bằng lọc tuyến tính 16 1.2.2 Làm trơn nhiễu bằng lọc phi tuyến 18 1.2.3 Lọc thông thấp, thông cao và lọc giải thông 19 1.3 Tổng quan về biên 20 1.3.1 Biên và các kiểu biên cơ bản 20 1.3.2 Vai trò của biên trong nhận dạng 21 CHƢƠNG II: PHƢƠNG PHÁP PHÁT HIỆN BIÊN CHO ẢNH ĐA MỨC XÁM 23 2.1 Giới thiệu 23 2.2 Quy trình phát hiện biên 23 2.3 Phương pháp phát hiện biên cơ bản 24 2.3.1 Phương pháp phát hiện biên Gradient 24 2.3.2 Phương pháp phát hiện biên Laplace 26 2.4 Phương pháp phát hiện biên nâng cao 29 2.4.1 Phương pháp phát hiện biên Canny 29 2.4.2 Phương pháp phát hiện biên Wavelet 32 CHƢƠNG III: PHƢƠNG PHÁP PHÁT HIỆN BIÊN CHO ẢNH MÀU 34 3.1 Cơ sở phát hiện biên ảnh màu 34 3.2 Mô hình ba màu 34 3.3 Các phương pháp phát hiện biên ảnh màu 37 3.3.1 Toán tử Vector Gradient 37 Sinh viên: Đặng Thị Thương – Lớp CT1101
  4. 4 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 3.3.2 Phương pháp Vector Field 39 3.3.3 Bộ dò biên Vector Order-Statistic 40 CHƢƠNG IV: PHƢƠNG PHÁP PHÁT HIỆN BIÊN THEO WAVELET 43 4.1 Giới thiệu 43 4.2 Biến đổi Wavelet liên lục (The Continuous Wavelet Transform – CWT) 44 4.3 MRA – Multi-resolution Analysis 45 4.4 Xây dựng một Wavelet 46 4.5 Phân hoạch và tái thiết wavelet 46 4.3 Biến đổi Wavelet rời rạc (DWT – Discrete Wavelet Transform ) 47 4.4 Phương pháp phát hiện biên DWT 49 CHƢƠNG V: CÀI ĐẶT THỬ NGHIỆM VÀ NHẬN XÉT ĐÁNH GIÁ CÁC PHƢƠNG PHÁP 51 4.1 So sánh các phương pháp phát hiện biên (Gradient. Laplace, Canny) 51 4.2 Cài đặt thử nghiệm chương trình Wavelet Transform 52 KẾT LUẬN 60 TÀI LIỆU THAM KHẢO: 61 Sinh viên: Đặng Thị Thương – Lớp CT1101
  5. 5 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu DANH SÁCH CÁC HÌNH ẢNH Hình 1.1: Quá trình xử lý ảnh Hình 1.2: Các bước cơ bản trong một quá trình xử lý ảnh Hình 1.3 Một ví dụ về điểm ảnh Hình 1.4 Biểu diễn ảnh với độ phân giải Hình 1.5: Lân cận các điểm ảnh của P(x,y) Hình 1.6: Đường bao của ảnh Hình 2.1: Quy trình phát hiện biên Hình 2.2: Hình mô tả các điểm biên lân cận của P Hình 3.1: Các màu quang phổ theo tiêu chuẩn CIE Hình 3.2: Biểu diễn mô hình màu RGB trên trục tọa độ Hình 3.3: Biểu diễn mô hình màu CMY trên trục tọa độ Hình 4.1: Sơ đồ kim tự tháp Laplace phát triển bởi Burt và Adelson Hình 4.2: DWT của hai chiều tín hiệu Hình 5.1: Biên ảnh theo Gradient, Laplace, Canny. Hình 5.2: Biến đổi ảnh với tỉ lệ 1 và bộ lọc daub1. Hình 5.3: DWT hai chiều tín hiệu. Hình 5.4: Loại bỏ thành phần tần số thấp. Hình 5.5: Ảnh biến đổi sau khi xây dựng lại Hình 5.6: Ảnh sau khi được làm nổi biên. Hình 5.7: Biên ảnh sau khi được khuếch đại. Sinh viên: Đặng Thị Thương – Lớp CT1101
  6. 6 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu MỞ ĐẦU Trong hai thập kỷ qua, chúng ta đã chứng kiến một sự tăng trưởng bùng nổ trong đa dạng cả về kỹ thuật và phạm vi của các ứng dụng xử lý ảnh. 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. Tuy nhiên biên cạnh việc xử lý ảnh xám, phạm vi xử lí ảnh màu thỉnh thoảng vẫn còn được che phủ, mặc dù đã trở thành phổ biến, người tiêu dùng lựa chọn các tiện ích trong ảnh màu hơn ảnh xám truyền thống. Với những tiến bộ trong bộ cảm biến hình ảnh, truyền hình kỹ thuật số, cơ sở dữ liệu hình ảnh, video, đa phương tiện và hệ thống, và với sự gia tăng của máy in màu, hiển thị hình ảnh màu sắc, các thiết bị DVD, và đặc biệt là máy ảnh kỹ thuật số và hình ảnh kích hoạt điện tử tiêu dùng, xử lý ảnh màu dường như đã trở thành trọng tâm chính của hội nghiên cứu xử lý ảnh. 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. Từ đó, em đã chọn đề tài “Tìm hiểu phƣơng pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu” 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 đối với ảnh đa cấp xám và ảnh màu, 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. Sau một thời gian tìm hiểu về đề tài, ngoài phần mở đầu và kết luận, kết cấu tài liệu báo cáo bao gồm 5 chương với các nội dung cụ thể như sau: Sinh viên: Đặng Thị Thương – Lớp CT1101
  7. 7 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 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 cho ảnh đa cấp xám 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 cơ bản trong phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai và vài phương pháp nâng cao như Canny, Wavelet. Chƣơng III: Các phƣơng pháp phát hiện biên cho ảnh màu Trong chương này đề cập đến phương pháp phát hiện biên vector Gra- dient, vector Field, Chƣơng IV: Phƣơng pháp phát hiện biên theo Wavelet Tìm hiểu về biến đổi Wavelet, từ đó tìm hiểu phương pháp phát hiện biên DWT Chƣơng V: Cài đặt thử nghiêm và 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ý. Sinh viên Đặng Thị Thương Sinh viên: Đặng Thị Thương – Lớp CT1101
  8. 8 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 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 là gì ? 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. Cùng với 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. Nhờ thế mà xử lý ảnh từng bước đó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. Xử lý ảnh thông thường gồm 3 bước: Kết luận Ảnh đầu vào Xử lý ảnh Ảnh tốt hơn Hình 1.1: Quá trình xử lý ảnh. – Bước 1: Nhập một hình ảnh với một máy quét quang học hoặc trực tiếp thông qua nghệ thuật chụp ảnh số. – Bước 2: Thao tác hoặc phân tích các hình ảnh bằng một cách nào đó. Giai đoạn này có thể bao gồm kỹ thuật nâng cao chất lượng hình ảnh và nén dữ liệu, hoặc hình ảnh có thể được phân tích để tìm ra các hình dáng mà mắt người không thể thấy được. Ví dụ: các nhà khí tượng học sử dụng xử lý ảnh để phân tích các ảnh vệ tinh. – Bước 3: Kết quả đầu ra - hình ảnh có thể bị thay đổi bằng cách này hay cách khác, nó có thể là một ảnh “tốt hơn” (Ví dụ: ảnh mờ được xử lý để nhìn rõ hơn) hoặc một kết luận (Ví dụ: phân tích ảnh để trích chọn các đặc trưng vân tay hay ảnh một tai nạn giao thông phác họa hiện trường tại nạn). 1.1.2 Các quá trình cơ bản trong hệ thống xử lý ảnh Một ảnh đầu vào cần thông qua rất nhiều bước khác nhau để có được một ảnh đầu ra mong muốn. Các quá trình cơ bản của một hệ thống xử lý ảnh được thể hiện thông qua sơ đồ dưới đây: Sinh viên: Đặng Thị Thương – Lớp CT1101
  9. 9 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Nhận Thu nhận ảnh Tiền xử Phân đoạn Trích chọn dạng (Scanner, lý ảnh đặc điểm Camera,Sensor) Hình 1.2: Các bước cơ bản trong một quá trình xử lý ảnh 1.1.2.1 Thu nhận ảnh Để thực hiện được quá trình đầu tiên trong hệ thống xử lý ảnh, ta cần sử dụng các thiết bị thu nhận ảnh để chuyển các thông tin dưới dạng hình ảnh thành các cấu trúc lưu trữ được trong máy tính và được hiển thị ra màn hình, máy in, Ảnh có thể thu nhận từ vệ tinh qua các bộ cảm ứng, qua camera, máy chụp ảnh đơn sắc (màu), hay các tranh, ảnh được quét trên máy quét ảnh. Nếu ảnh thu nhận được chưa phải là dạng số hóa ta phải chuyển đổi hay số hóa ảnh trước khi chuyển sang giai đoạn tiếp theo. 1.1.2.2 Tiền xử lý Sau khi được thu nhận bởi các thiết bị thu nhận ảnh, ảnh sẽ được cải thiện về độ tương phản, nhiễu, bởi các kỹ thuật xử lý ảnh để làm ảnh tốt hơn theo mục đích sử dụng nhằm phục vụ cho quá trình xử lý tiếp theo. Một số tiến trình trong quá trình tiền xử lý là: − Điều chỉnh độ chiếu sáng: khắc phục hậu quả của sự chiếu sáng không đồng đều. − Khử nhiễu: Nhiễu được chia làm 2 loại cơ bản là nhiễu hệ thống và nhiễu ngẫu nhiên. Trong đó, nhiễu hệ thống là nhiễu có quy luật có thể khử bằng các phép biến đổi Fourier và loại bỏ các đỉnh điểm. Đối với nhiễu ngẫu nhiên – vết bẩn không rõ nguyên nhân thì được khắc phục bằng các phép lọc (lọc trung bình, lọc trung vị, ). − Hiệu chỉnh mức xám: có thể tăng hay giảm số mức xám nhằm khắc phục tính không đồng bộ gây nên từ hiệu ứng của thiết bị thu nhận hình ảnh hoặc độ tương phản giữa các vùng ảnh. − Chuẩn hóa độ lớn, hình dạng và màu sắc. − Nắn chỉnh hình học: ảnh thu nhận thường bị biến dạng do các thiết bị quang học và điện từ, để khắc phục điều này người ta sử dụng các phép chiếu đươc xây dựng trên tập các điểm điều khiển. 1.1.2.3 Phân đoạn ảnh Phân đoạn ảnh là một quá trình thao tác ở mức thấp trong toàn bộ hệ thống xử lý ảnh. Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và đồng nhất với nhau hay nói cách khác là xác định các biên của các vùng ảnh đó. Phân đoạn ảnh là chia ảnh thành các vùng không trùng lắp, mỗi vùng gồm 1 nhóm pixel liên thông và đồng nhất theo 1 tiêu chí nào đó. Ví dụ: đồng Sinh viên: Đặng Thị Thương – Lớp CT1101
  10. 10 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu nhất về màu sắc, mức xám, kết cấu, độ sâu của các layer, Sau khi phân đoạn mỗi pixel chỉ thuộc về một dùng duy nhất. Để đánh giá chất lượng của quá trình phân đoạn là rất khó, vì vậy cần phải xác định rõ mục tiêu của quá trình phân đoạn là gì? Ví dụ: để nhận dạng chữ (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 gửi thành các từ, các chữ, các số (các vạch) riêng biệt để nhận dạng. Kết quả của quá trình 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 Trích chọn đặc điểm Dựa trên các thông tin thu nhận được qua quá trình phân đoạn, kết hợp với các kỹ thuật xử lý, thủ tục phân tích dữ liệu để đưa ra các đặc điểm đặc trưng, đối tượng ảnh cũng như các thông tin cần thiết trong quá trình xử lý. Nhờ đó việc nhận dạng các đối tượng ảnh chính xác hơn, 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 tùy theo mục đích nhận dạng trong hệ thống xử lý ảnh. Sau đây là một vài đặc điểm của ảnh: − Đặ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) v.v Sinh viên: Đặng Thị Thương – Lớp CT1101
  11. 11 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 1.1.2.5 Nhận dạng Nhận dạng ảnh là quá trình cuối cùng của hệ thống xử lý ảnh - quá trình liên quan đến các mô tả đối tượng mà người ta muốn đặc tả nó. Quá trình này thường đi sau quá trính trích chọn đặc điểm trong hệ thống xử lý ảnh. Có 2 kiểu nhận dạng ảnh cơ bản: − Nhận dạng theo tham số (mô tả tham số). − Nhận dạng theo cấu trúc (mô tả theo cấu trúc). Hiện nay, người ta đã áp dụng kỹ thuật nhận dạng khá thành công với nhiều đối tượng khác nhau như: nhận dạng ảnh vân tay, khuôn mặt, nhận dạng chữ (chữ cái, chữ số, chữ có dấu), nhận dạng chữ in (đánh máy) phục vụ cho việc tự động hóa quá trình đọc tài liệu, tăng tốc độ và chất lượng nhận thông tin từ máy tính. Ngoài ra kỹ thuật nhận dạng dựa vào kỹ thuật mạng nơ ron đang được áp dụng và cho kết quả khả quan. 1.1.3 Một số vấn đề cơ bản trong xử lý ảnh 1.1.3.1 Ảnh và điểm ảnh Hình 1.3 Biểu diễn ảnh với điểm ảnh (Ví dụ này cho thấy một hình ảnh với một phần mở rộng rất nhiều, trong đó các điểm ảnh riêng lẻ được kết xuất như hình vuông nhỏ và có thể dễ dàng được nhìn thấy.) Ảnh trong thực tế là ảnh liên tục về không gian và giá trị độ sáng. Để xử lý ảnh người ta phải tiến hành số hóa, quá trình số hóa là quá trình biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lượng hóa thành phần giá trị (rời rạc hóa biên độ giá trị) mà về nguyên tắc mắt người không phân biệt được 2 điểm kề nhau. Trong quá trình này người ta sử dụng khái niệm PEL: Picture Element mà ta quen gọi (viết tắt) là Pixel – phần tử ảnh (điểm ảnh). Mỗi pixel gồm một cặp tọa độ (x, y) (trong khuôn khổ ảnh 2 chiều) với độ xám hoặc màu nhất định Từ khái niệm điểm ảnh, ta có thể định nghĩa ảnh là tập hợp hữu hạn các điểm ảnh, thường được biểu diễn bằng một mảng hai chiều I(n,m) với n là số Sinh viên: Đặng Thị Thương – Lớp CT1101
  12. 12 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu hàng, m là số cột. Ta ký hiệu P(x,y) – 1 phần tử trong ma trận là một điểm ảnh tại vị trí (x,y). Số lượng điểm ảnh trên mỗi hàng hoặc các hàng xác định độ phân giải của ảnh. 1.1.3.2 Độ phân giải của ảnh a) Ảnh với độ phân giải 512 x 320 b) Ảnh với độ phân giải 64 x 40 Hình 1.4 Biểu diễn ảnh với độ phân giải Độ 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 (512 và 320 ở hình a) trong không gian hai chiều. 1.1.3.3 Mức xám của ảnh và phân loại ảnh Mỗi Pixel (điểm ảnh) có hai đặc trưng cơ bản là vị trí (x, y) của điểm ảnh và mức xám của nó. Mức xám (Gray level) là kết quả của sự mã hóa thương ứng một cường độ sáng của mỗi điểm ảnh với một giá trị số (giá trị nguyên dương) - kết quả của quá trình lượng hóa. Các thang giá trị mức xám thường dùng là 16, 32, 64, 128 hay 256 mức. Mã hóa 256 mức là phổ dụng nhất do lý do kỹ thuật. Vì 28 = 256 (tức là từ 0 255) nên với 256 mức, mỗi pixel sẽ được mã hóa bởi 1 byte (8 bit). Từ định nghĩa mức xám ta phân loại ảnh theo giá trị mức xám của nó: * Ảnh nhị phân: Giá trị mức xám của tất cả điểm ảnh chỉ nhận giá trị 1 hoặc 0: − 1: biểu diễn đối tượng ảnh và được gọi là điểm đen. − 0: biểu diễn ảnh nền (phông ảnh), được gọi là điểm trắng Như vậy mỗi điểm ảnh trong ảnh nhị phân được biểu diễn bởi 1 bit. * Ảnh xám: Giá trị nằm trong khoảng từ 0 255, như vậy mỗi điểm ảnh trong ảnh xám được biểu diễn bởi 1 byte. Ảnh có nhiều mức xám được gọi là ảnh đa cấp xám. Ta có thể chuyển đổi từ ảnh đa mức xám về ảnh nhị phân theo công thức: Sinh viên: Đặng Thị Thương – Lớp CT1101
  13. 13 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Y (m, n) = 1 nếu X (m, n) ≥ θ với θ là ngưỡng tự chọn 0 nếu X (m, n) < θ * Ảnh màu: Ảnh màu theo lý thuyết của Thomas là ảnh tổ hợp từ 3 màu cơ bản được thu nhận trên các dải băng tần khác nhau: + Đỏ – RED (R) + Lục – GREEN (G) + Lam – BLUE (B) Với ảnh màu, cách biểu diễn cũng tương tự như với ảnh đen trắng, chỉ khác là tại mỗi phần tử của ma trận biểu diễn cho ba màu riêng rẽ gồm: đỏ, lục và lam. Để lưu trữ ảnh màu người ta có thể lưu trữ từng màu riêng biệt, mỗi màu lưu trữ như một ảnh đa cấp xám, mỗi mức xám của ảnh sẽ được biểu diễn bởi 3 thành phần: R, G, B (mỗi thành phần được biểu diễn bởi 1 byte). Do đó, không gian nhớ dành cho một ảnh màu lớn gấp 3 lần một ảnh đa cấp xám cùng kích cỡ. Ta có thể chuyển đổi ảnh màu về ảnh đa mức xám theo công thức: G = 0.299R + 0.587G + 0.114B (ảnh hưởng của màu đến mức xám giảm dần từ G, R đến B) hoặc: G = 0.333R + 0.333G + 0.333B (Coi ảnh hưởng của R, G, B là như nhau) Như vậy để xử lý ảnh màu ta phải xử lý trên 3 ảnh xám R, G, B của nó và kết hợp lại sẽ có kết quả như mong muốn. 1.1.3.4 Quan hệ giữa các điểm ảnh a, Các lân cận của điểm ảnh (Image Neighbors) Giả sử ta có điểm ảnh P tại tọa độ (x,y), khi đó P(x,y) có 2 điểm lân cận đứng và 2 điểm lân cận ngang: (x+1,y), (x-1,y), (x,y+1), (x,y-1). Một tập các điểm như vậy được gọi là tập 4 điểm lân cận của P và được ký hiệu là N4(P) {(x+1,y); (x-1,y); (x,y+1); (x,y-1)} = N4(P) Trong đó 1 là giá trị logic. Ngoài ra điểm ảnh P còn có các lân cận chéo ND(P) {(x+1, y+1); (x+1, y-1); (x-1, y+1; (x-1 ,y-1)} = ND(P) Sinh viên: Đặng Thị Thương – Lớp CT1101
  14. 14 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu (x,y-1) (x-1,y-1) (x+1,y-1) (x-1,y) (x+1,y) P(x,y) (x,y+1) (x+1,y+1) (x,y+1) Hình 1.5: Lân cận các điểm ảnh của P(x,y) ta có tập kết hợp N8(P) = N4(P) + ND(P) là tập hợp 8 lân cận của điểm ảnh P. Chú ý: Nếu P(x,y) nằm ở biên (mép) ảnh, một số điểm lân cận 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à một 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 : 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 khi và chỉ khi: + q thuộc N4(p) hoặc + q thuộc ND(p) và {N4(p) ∩ N4(q)} = Ø Ví dụ: cho tập V= {1, 2} Sinh viên: Đặng Thị Thương – Lớp CT1101
  15. 15 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 0 1 1 0 1 1 0 1 1 0 2 0 0 2 0 0 2 0 0 0 1 0 0 1 0 0 1 Liên kết 4 Liên kết 8 Liên kết m c, Đo khoảng cách giữa các điểm ảnh Cho các điểm ảnh p, q và z với tọa độ (x, y), (s, t), (u, v) tương ứng, gọi D là hàm khoảng cách giữa hai điểm ảnh p va q. Khi đó hàm khoảng cách D (Distance) có tính chất sau: 1. D(p, q) ≥ 0 (Với D(p, q) = 0 khi và chỉ khi p = q) 2. D(p, q) = D( q, p) 3. D(p, z) ≤ D(p, q) + D(q, z) Ngoài ra còn có các biện pháp đo khoảng cách giữa các điểm ảnh khác: * Khoảng cách O-clit (Euclidean): khoảng cách O-clit giữa 2 điểm ảnh p và q được định nghĩa như sau: 2 2 1/2 De(p,q) = [(x - s) + (y - t) ] * 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 | * Khoảng cách bàn cờ D8(p, q): là khoảng cách được xác định như sau: D8(p,q) = max (| x - s | , | y - t |) 1.2 Nâng cao chất lƣợng ảnh và toán tử không gian Thông thường ảnh thu nhận có nhiễu cần phải loại bỏ nhiễu hay ảnh không sắc nét bị mờ hoặc cần làm rõ các chi tiết như các đườ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 biên (ứng với tần số cao), người ta dùng các bộ lọc thông cao, lọc Laplace Sinh viên: Đặng Thị Thương – Lớp CT1101
  16. 16 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Để hiểu rõ hơn các kỹ thuật áp dụng, cần phải phân biệt các loại nhiễu can thiệp trong quá trình xử lý ảnh. Trên thực tế tồn tại khá nhiều loại nhiễu như sự thay đổi độ nhạy của cảm biến, sự biến đổi của môi trường, sai số của quá trình lượng tử hóa, sai số của kênh truyền ; tuy nhiên người ta thường xem xét 3 loại nhiễu chính và phổ biến là: nhiễu cộng, nhiễu nhân và nhiễu xung: − Nhiễu cộng (Additive noise): thường phân bố khắp ảnh và được biểu diễn bởi: Y = X + n − Nhiễu nhân: cũng thường phân bố khắp ảnh và được biểu diễn bởi: Y = X * n Chú ý: với Y: ảnh quan sát, X: ảnh gốc và n là nhiễu. − Nhiễu xung (Impulse noise): là một loại nhiễu khá đặc biệt có thể sinh ra bởi nhiều lý do khác nhau chẳng hạn: lỗi truyền tín hiệu, lỗi bộ nhớ, hay lỗi định thời trong quá trình lượng tử hóa. Nhiễu này 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). 1.2.1.1 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á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,1) 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 v(m,n) = a(k,l)y(m k,n l) N (k,1) w Với: y(m,n): ảnh đầu vào v(m,n): ảnh đầu ra a(k,l): là trọng số lọc 1 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: Sinh viên: Đặng Thị Thương – Lớp CT1101
  17. 17 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 1 1 1 1 H = 1 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: 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. 1.2.1.2 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 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 2 Hb = b b b (b 2)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] Sinh viên: Đặng Thị Thương – Lớp CT1101
  18. 18 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 2 trong đó η[m,n] là nhiễu cộng có phương sai σ n. Như vậy, theo cách tính lọc trung bình ta có: 1 Y[m,n] = X qs (m k,n l) m,n Nw k,l w 2 1 n hay Y[m,n] = X qs (m k,n l) Nw k,l w Nw Như vậy, nhiễu cộng trong ảnh đã giảm đi Nw lần. 1.2.1.3 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 gồm ảnh gốc nhân với hệ số nhiễu. Gọi X (m,n) là ảnh thu được, X(m,n) là ảnh gốc và η(m,n) là nhiễu, ta có: X(m,n) = X (m,n) * η(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). 1.2.2.1 Lọc trung vị Khái niệm trung vị được viết bởi công thức: v(m,n) = Trungvi(y(m-k, n-l) với (k, l) thuộc 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. Ví dụ: Nếu y(m) = {2, 3, 8, 4, 2} và cửa sổ W = (-1, 0, 1) thì ảnh kết quả thu được sau lọc trung vị là v(m) = {2, 3, 4, 4, 2}. do đó: v[0] = 2 v[3] = Trungvi(8, 4, 2) = 4 v[1] = Trungvi(2, 3, 8) = 3 v[4] = 2 v[2] = Trungvi(3, 8, 4) = 4 Sinh viên: Đặng Thị Thương – Lớp CT1101
  19. 19 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu * 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 được thể hiện: 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 bộ 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. 1.2.2.2 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: (w) khi u(m,n) - (w) Y(m,n) = u(m,n) 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 giả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 thì bộ lọc thông cao HHP(m,n) có thể được định nghĩa: HHP(m,n) = δ(m,n) − HLP(m,n) Và bộ lọc giải thông được định nghĩa: HHP(m,n) = HL1(m,n) − HL2(m,n) 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 giải thông có hiệu quả làm nổi biên. 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: Sinh viên: Đặng Thị Thương – Lớp CT1101
  20. 20 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 1 1 1 0 1 0 1 2 1 1 9 1 1 5 1 2 5 2 1 1 1 0 1 0 1 2 1 (1) (2) (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 1.3.1.1 Một số khái niệm về biên Cho tới nay chưa có định nghĩa chính xác về biên và mỗi định nghĩa được sử dụng trong một số trường hợp nhất định. Biên có thể được tạo ra bởi bóng tối, kết cấu hình học Biên cũng có thể được định nghĩa là không liên tục ở cường độ hình ảnh do sự thay đổi trong cấu trúc hình ảnh. Biên trong một hình ảnh thường xảy ra với độ phân giải hoặc quy mô khác nhau và đại diện cho quá trình chuyển đổi của mức xám khác nhau, hay mức độ gradient. Tuy nhiên, nhìn chung biên có thể được định nghĩa như sau: Điểm biên: một điểm ảnh được coi là điểm 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. Đường biên (đường bao của ảnh - boundary) của đối tượng: được tạo thành bởi một tập các điểm biên liên tiếp. 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 2 thành phần: − Độ lớn của Gradient. − Hướng của biên với góc φ, lệch so với hướng của Gradient ψ một góc -900. Mô hình biểu diễn đường biên: theo toán học, điểm ảnh có sự biến đổi mức xám u(x) một cách đột ngột theo hình dưới: Sinh viên: Đặng Thị Thương – Lớp CT1101
  21. 21 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu u u u x x x a, Đường biên lý tưởng b, Đường biên bậc thang c, Đường biên thực Hình 1.6: Đường bao của ảnh 1.3.1.2 Các kiểu biên cơ bản a, 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 này càng lớn thì càng dễ dàng nhận ra biên. Một biên được coi là biên lý tưởng khi 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. b, Biên bậc thang (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 biên đượ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ỹ thuật số hóa 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. c, Biên thực Trên thực tế, ảnh thường có biên không lý tưởng, có thể do các nguyên nhân sau: − Hình dạng không sắc nét. − Nhiễu: 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ế. 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: Sinh viên: Đặng Thị Thương – Lớp CT1101
  22. 22 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu − 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. Sinh viên: Đặng Thị Thương – Lớp CT1101
  23. 23 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu CHƢƠNG II: PHƢƠNG PHÁP PHÁT HIỆN BIÊN CHO ẢNH ĐA MỨC XÁM 2.1 Giới thiệu Một biên trong một hình ảnh nói chung có thể được định nghĩa như là đường bao của ảnh hoặc đường viền ngăn cách khu vực ảnh liền kề có đặc điểm tương đối khác biệt theo một số tính năng quan tâm, một trong số đó là độ đo về sự thay đổi đột ngột về cấp xám. Biên có thông tin quan trọng góp phần hướng tới phân tích và giải thích thông tin hình ảnh (nhận dạng). Các giai đoạn của phát hiện biên là làm mịn hay nâng cao chất lượng ảnh (quá trình loại bỏ nhiễu) và phát hiện biên. Có nhiều phương pháp để phát hiện biên cơ bản, nhưng hầu hết trong số đó có thể chia thành hai loại: * Phƣơng pháp phát hiện biên trực tiếp: tìm biên dựa vào sự biến thiên về giá trị độ sáng (cấp xám) của ảnh. Chủ yếu dựa vào kỹ thuật lấy đạo hàm. Ở phương pháp này ta có thể nhóm thành 2 loại: − Phương pháp Gradient: chúng ta tính toán ước lượng độ lớn gradient bằng cách sử dụng bộ lọc làm mịn và sử dụng dự đoán tính toán để xác định vị trí của biên. Nói cách khác phương pháp Gradient là phương pháp dò biên cục bộ bằng cách tìm kiếm cực đại và cực tiểu khi lấy đạo hàm bậc nhất của ảnh. − Phương pháp Laplace: chúng ta lấy đạo hàm bậc hai của các tín hiệu và biên độ đạo hàm là cực đại khi đạo hàm bậc hai bằng 0. Trong ngắn hạn, phương pháp Laplace tìm kiếm toán tử chéo không tại đạo hàm bậc hai của ảnh để tìm biên. * Phƣơng pháp phát hiện biên gián tiếp: Nếu bằng cách nào đó ta phân được ảnh thành các vùng thì ranh giới giữa các vùng đó gọi là biên. Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu nhau vì dò biên để thực hiện phân lớp đối tượng mà khi đã phân lớp xong nghĩa là đã phân vùng được ảnh và ngược lại, khi đã phân vùng ảnh đã được phân lớp thành các đối tượng, do đó có thể phát hiện được biên. Ngoài ra còn các phương pháp nâng cao khác như phương pháp Canny, Wavelet 2.2 Quy trình phát hiện biên Ảnh đầu vào Lọc nhiễu Làm nổi Định vị biên Liên kết & Ảnh kết quả biên trích chọn Hình 2.1: Quy trình phát hiện biên Sinh viên: Đặng Thị Thương – Lớp CT1101
  24. 24 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Bước 1: Lọc nhiễu do ảnh ghi vào thường có nhiễu 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 (cần loại bỏ biên giả) Bước 4: Liên kết và trích chọn biên 2.3 Phƣơng pháp phát hiện biên cơ bản 2.3.1 Phƣơng pháp phát hiện biên Gradient Phương pháp Gradient là phương pháp dò biên cục bộ bằng cách tìm kiếm cực đại và cực tiểu khi lấy đạo hàm bậc nhất của ảnh trong không gian hai chiều. Theo định nghĩa, Gradient là một vector có các thành phần biểu thị tốc độ thay đổi giá trị của điểm ảnh: f x, y f (x dx, y) f (x, y) x x dx f x, y f (x, y dy) f (x, y) y x dx Trong đó dx, dy là khoảng cách giữa 2 điểm lân cận theo hướng x và y tương ứng. Trong những hình ảnh rời rạc, ta có thể xem xét dx, dy về số lượng điểm ảnh giữa hai điểm. Thực tế ta chọn dy = dx = 1 (khoảng cách điểm ảnh) là điểm mà tại đó tọa độ điểm ảnh là (i, j), do đó: x f (i 1, j) f (i, j) y f (i, j 1) f (i, j) Do tính chất phức tạp trong tính toán khi áp dụng phương pháp Gradient trong xử lý ảnh, 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). Nếu định nghĩa g1, g2 là Gradient theo hai hướng x, y tướng ứng thì biên độ g(m,n) tại điểm (m,n) được tính: 2 2 g(m,n) g1 (m,n) g2 (m,n) A0 r (m,n) artg(g2 (m,n)) Để giảm độ phức tạp tính toán, A0 được tính gần đúng như sau: A0 g1(m,n) g2(m,n) 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 (Roberts, Sobel, Prewitt, ). Sinh viên: Đặng Thị Thương – Lớp CT1101
  25. 25 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu * Thuật toán: − Với mỗi điểm ảnh I(x,y) tính: 2 2 Grad(I(x, y)) (I(x, y) H1) (I(x, y) H2 ) − Phân ngưỡng: 1 if I(x, y) I(x, y) 0 if I(x, y) 2.3.1.1 Toán tử Robert – Phƣơng pháp phát hiện biên Robert Lý do chính để sử dụng toán tử Robert là nó rất tính toán rất nhanh. Chỉ có bốn điểm ảnh đầu vào cần phải được kiểm tra để xác định giá trị của mỗi điểm ảnh đầu ra, và chỉ phép trừ và phép cộng được sử dụng trong tính toán. Trong phép cộng không có tập tham số nào. Nhược điểm chính của toán tử Robert là sử dụng một mặt nạ nhỏ, và rất nhạy cảm với nhiễu. Nó cũng tạo ra phản hồi rất yếu với biên thực, trừ khi các biên này rất sắc nét. Toán tử Robert bao gồm một cặp mặt nạ nhân chập 2 x 2 là Hx và Hy , những mặt nạ này được thiết kế có thể đáp ứng tối đa để biên hoạt động theo hai hướng -450 và +450: 0 1 1 0 H H x 1 0 y 0 1 Hướng của gradient 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ý không tuyến tính nào sau đây: 2 2 f (i, j) f1(i, j) f2 (i, j) f (i, j) max f1(i, j), f2(i, j) f (i, j) f1(i, j) f2(i, j) Trong đó: f1(i,j) và f2(i,j) là đáp ứng rút ra từ mẫu Gx và Gy Hướng của đường biên θ(i,j) tính theo phương nằm ngang, có thể rút ra bởi: f (i, j) (i, j) tan 1 2 4 f1(i, j) Sinh viên: Đặng Thị Thương – Lớp CT1101
  26. 26 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Các phần tử trong mặt nạ gọi là các 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): f (i, j) f (i, j 1) f (i 1, j) f (i, j) f (i 1, j 1) 2.3.1.2 Toán tử Sobel - Phƣơng pháp phát hiện biên Sobel Ở đây chúng ta sử dụng hai mặt nạ nhân chập 3 * 3 theo hướng x, y với hình ảnh đa mức xám. 1 0 1 1 2 1 H x 2 0 2 H y 0 0 0 1 0 1 1 2 1 Hướng của gradient * Thuật toán: + Bước 1: tính I(x,y) ⊗ Hx = I1 và I(x,y) ⊗ Hy = I2 + Bước 2: Tính | I1 | +| I2 | = IS + Bước 3: Hiệu chỉnh I(x,y) = Is ≥ θ ? 1 : 0 2.3.1.3 Toán tử Prewitt - Phƣơng pháp phát hiện biên Prewitt Toán tử Prewitt làm việc giống với cách làm của toán tử Sobel, nhưng sử dụng mặt nạ nhân chập khác so với toán tử Sobel. Mặt nạ này cho kết quả giống như Sobel và cùng hướng x, y: 1 0 1 1 1 1 H x 1 0 1 H y 0 0 0 1 0 1 1 1 1 Hướng của gradient * Thuật toán: Các bước tính toán tương tự như Sobel 2.3.2 Phƣơng pháp 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 định nghĩa như sau: Sinh viên: Đặng Thị Thương – Lớp CT1101
  27. 27 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 2 f 2 f 2 f x2 y2 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 hay dùng: 0 1 0 1 1 1 1 2 1 H1 1 4 1 H2 1 8 1 H3 2 4 2 0 1 0 1 1 1 1 2 1 * Ghi chú: Mặt nạ H1 còn cải biên bằng việc lấy giá trị ở tâm bằng 8 thay vì giá trị 4. Để thấy rõ việc xấp xỉ đạo hàm riêng bậc 2 trong không gian 2 chiều với mặt nạ H1 làm ví dụ, ta có thể tính gần đúng như sau: 2 f 2 f (x, y) f (x 1, y) f (x 1, y) x2 2 f 2 f (x, y) f (x, y 1) f (x, y 1) y2 2 f 2 f 2 f 4 f (x, y) f (x 1, y) f (x, y 1) f (x 1, y) f (x, y 1) x2 y2 Kỹ thuật theo toán tử Laplace tạo đường biên mảnh (có độ rộng 1 pixel). Nhược điểm của kỹ thuật này rất nhạy với nhiễu, do vậy đường biên thu được thường kém ổn định. Để 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 (Laplace of Gauss) để giảm nhiễu cho ảnh (làm trơn ảnh). * Zero – crossing và toán tử Laplace: Biên được nhận dạng bằng việc tìm các giao điểm không (chéo – không) trong đạo hàm bậc hai của toán tử Laplace. Bộ dò “chéo-không” tìm những nơi mà giá trị chỉ toán tử Laplace đi qua điểm 0 trong toán tử Laplace của một ảnh. * Phƣơng pháp Laplace of Gauss (LoG): Phương pháp này bao gồm 2 bước: − Bước 1: Làm trơn ảnh với bộ lọc Gauss (lọc nhiễu). (Nhân chập ảnh gốc với kích thước N x M với toán tử LoG kích thước M2) − Bước 2: Tìm điểm “chéo-không”. (Áp dụng bộ lọc Laplace) Quá trình thực hiện: Bước 1: Làm trơn ảnh (lọc nhiễu) với bộ lọc Gauss Để giảm bớt nhiễu cho ảnh, ta tiến hành làm trơn ảnh bằng bộ lọc Gauss. Sinh viên: Đặng Thị Thương – Lớp CT1101
  28. 28 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu * Hàm Gauss: − Trong 1D x2 g(x) e 2 2 Đạo hàm bậc nhất của Gauss: x2 x2 1 2 x 2 g'(x) 2xe 2 e 2 2 2 2 Đạo hàm bậc hai của Gauss: 2 2 x x 1 2 2 g''(x) ( 3 )e − Trong 2D x2 y2 1 2 g(x, y) e 2 2 2 2 2 2 x y 1 x y 2 log 1 e 2 4 2 2 trong đó: σ là ngưỡng chuẩn, thể hiện chiều rộng của việc phân phối Gauss. Vùng phân bố thể hiện chất lượng làm mịn nhiễu được thực hiện, và được kiểm soát bằng cách biến đổi σ. Việc làm trơn ảnh được thực hiện bằng cách tiến hành nhân chập ảnh với bộ lọc Gauss. ILap = I⊗ g(x,y) = g(x,y)⊗ I Như vậy để thực hiện bước 1: Ta tiến hành nhân chập ảnh cần xử lý với bộ lọc Gauss giống như cách thức nhân chập 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 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 biên 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 chập ảnh kết quả ở bước 1 với một mặt nạ nhân chập được tính toán từ phương pháp Laplace. Sinh viên: Đặng Thị Thương – Lớp CT1101
  29. 29 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 2I 2I 2I Lap Lap Lap x2 y2 2 2 2 I Lap (g * ) ( g)* 2 2 2 2 x y 1 x y 2 2 g 2 e 2 2 3 2 2 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 ILap (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 chập của Laplace. * Thuật toán: - Với mỗi điểm ảnh I(x,y) tính I(x,y) ⊗ H = ILap 2 - Lấy | ILap |= Δ ILap - Hiệu chỉnh I(x,y) = ILap ≥ θ ? 1 : 0 2.4 Phƣơng pháp phát hiện biên nâng cao 2.4.1 Phƣơng pháp phát hiện biên Canny 2.4.1.1 Giới thiệu Mục đích của việc phát hiện biên nói chung là giảm thiểu đáng kể số lượng dữ liệu trong một hình ảnh, trong khi các đặc tính cấu trúc vẫn được giữ để sử dụng cho việc xử lý hình ảnh hơn nữa. Có rất nhiều phương pháp phát hiện biên đã được đề cập ở trên nhưng phương pháp Canny – được phát triển bởi John F. Canny (JFC) vào năm 1986, là một trong những công cụ xử lý hình ảnh thông dụng nhất. Mặc dù nó khá là cũ, song đã trở thành một trong những phương pháp phát hiện biên tiêu chuẩn và vẫn được sử dụng trong nghiên cứu. Mục tiêu (ràng buộc) của JFC để phát triển thuật toán đó là tối ưu những vấn đề liên quan đến các tiêu chuẩn sau: − Phát hiện: Xác suất phát hiện những điểm biên thực sự phải là cực đại hóa, trong khi xác suất lỗi phát hiện những điểm không phải biên cần được giảm thiểu. Điều này tương ứng với tối đa hóa tỷ lệ báo hiệu nhiễu. − Cục bộ hóa: Các biên phát hiện nên càng gần biên thực càng tốt. Có nghĩa là độ chênh lệch cấp xám giữa các điểm trên cùng một biên càng nhỏ càng tốt. − Số lượng trả lời – hiệu suất: biên không được nhận ra nhiều, trong khi chỉ có một biên tồn tại giảm số lượng biên được phát hiện không được nhận ra. 2.4.1.2 Thuật toán phƣơng pháp phát hiện biên Canny a) Các bƣớc thực hiện Sinh viên: Đặng Thị Thương – Lớp CT1101
  30. 30 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Thuật toán được tiến hành qua 5 bước riêng biệt sau: - Bước 1: Giảm nhiễu: làm trơn ảnh để loại bỏ nhiễu bằng cách nhân chập ảnh với bộ lọc Gauss. - Bước 2: Tìm gradient: Tính toán góc và chiều dài của gradient. Biên nên được đánh dấu nơi mà gradient của ảnh có chiều dài lớn. - Bước 3: Thực hiện “Non-maximum suppression”: Chỉ cực đại cục bộ những điểm được đánh dấu là biên (có mức xám cao). - Bước 4: Sử dụng ngưỡng đôi: Những biên tiềm năng được xác định bởi ngưỡng cao và ngưỡng thấp. b) Miêu tả các bƣớc thực hiện * Bước 1: Giảm nhiễu Đây là điều không thể tránh khỏi vì tất cả các hình ảnh chụp từ máy quay sẽ chứa một số nhiễu. Để ngăn nhầm lẫn nhiễu với các biên, nhiễu phải được giảm bớt. Do đó ảnh trước tiên được làm mịn bằng cách áp dụng một bộ lọc Gauss. Cách thức tiến hành giống như ở Laplace of Gauss. Nhân của bộ lọc Gauss với độ lệch chuẩn σ = 1,4 được thể hiện trong phương trình sau (ở đây ta sử dụng một bộ lọc 5 x 5): 2 4 5 4 2 4 9 12 9 4 1 S 5 12 15 12 5 159 4 9 12 9 4 2 4 5 4 2 * Bước 2: Tìm Gradient Các thuật toán Canny về cơ bản tìm thấy các biên nơi mà cường độ mức xám của hình ảnh thay đổi nhiều nhất. Những vùng này được tìm thấy bằng cách xác định gradient của ảnh. Gradient tại mỗi điểm ảnh trong ảnh được làm mịn được xác định bằng cách áp dụng những phướng pháp dựa theo toán tử Sobel. Bước đầu tiên là đạo hàm các kết quả ở bước 1 theo hướng x và y với mặt nạ 3x3: 1 0 1 1 2 1 H x 2 0 2 H y 0 0 0 1 0 1 1 2 1 Các biên độ gradient (còn được gọi là những cường độ biên) sau đó có thể được xác định như là một thước đo khoảng cách Euclide bằng cách áp dụng luật của Pythagoras như trong phương trình sau: 2 2 S' Sx S y Sinh viên: Đặng Thị Thương – Lớp CT1101
  31. 31 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Đôi khi nó được đơn giản hóa bằng cách áp dụng thước đo khoảng cách Manhattan để giảm bớt sự phức tạp tính toán: S' Sx S y trong đó Sx và Sy là gradient theo 2 hướng x và y tương ứng và hướng của biên θ như sau: S tan 1 y Sx Ảnh S’ tìm được là kết quả của bước thứ 2. * Bước 3: Tiến hành “Non-maximum suppression” Tức là loại bỏ một số biên 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ứ tính hướng của đường biên θ được tính ở bước 2). Giả sử với điểm biên đang xét tại vị trí P(x, y), ta có 8 điểm biên lân cận điểm biên này: y 112,5o 67,5o (x,y-1) (x-1,y-1) (x+1,y-1) 157,5o 22,5o (x-1,y) (x+1,y) x P(x,y) -157,5o - 22,5o (x,y+1) (x,y+1) (x+1,y+1) - 112,5o - 67,5o Hình 2.2: Hình mô tả các điểm biên lân cận của P 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.5o hoặc θ > 157.5o thì đặt giá trị của θ = 00 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: Sinh viên: Đặng Thị Thương – Lớp CT1101
  32. 32 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Giá trị θ Phƣơng hƣớng Điểm ảnh θ ≤ 22,50 hoặc θ > 157,50 θ = 00 (x − 1, y); (x + 1, y) 22,50 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). 2.4.2 Phƣơng pháp phát hiện biên Wavelet Phát hiện biên là 1 bước quan trọng trong nhận dạng, phân đoạn ảnh và phân tích cảnh. Các phương pháp tiếp cận để phát hiện biên ko đạt trước nhiễu trong hình ảnh và có thể gây ra các vấn đề trong nhiều ứng dụng. Nhưng nhiễu bị giảm rất hiệu quả bởi phương pháp lọc wavelet mà không làm giảm đáng kể độ phân giải hình ảnh. Không giống như phát hiện biên canny trong đó bước đầu tiên là làm mịn ảnh bằng phương pháp lọc Gaussian để giảm tác động của nhiễu Sinh viên: Đặng Thị Thương – Lớp CT1101
  33. 33 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu và bước tiếp theo là xác định biên. Trong Wavelet hai bước này được kết hợp thành một bước và do đó kỹ thuật dựa trên wavelet tính toán hiệu quả hơn. Đó là thực nghiệm đã chứng minh rằng phương pháp phát hiện biên dựa trên Wavelet cho kết quả tốt hơn so với kỹ thuật truyền thống với các ảnh nhiễu. Trong các chương tiếp theo sẽ giải thích rõ hơn về phương pháp này. Sinh viên: Đặng Thị Thương – Lớp CT1101
  34. 34 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu CHƢƠNG III: PHƢƠNG PHÁP PHÁT HIỆN BIÊN CHO ẢNH MÀU 3.1 Cơ sở phát hiện biên ảnh màu Màu sắc là một tính năng quan trọng mô tả nội dung bên trong một cảnh hình ảnh, và nó được cho là một thuộc tính có độ tin cậy cần được sử dụng để phát hiện biên. Các giả thuyết chính được sử dụng trong việc phát hiện biên màu là có một sự thay đổi trong sắc độ hay cường độ của điểm ảnh ở các đường biên của các đối tượng. Do đó, phát hiện đường biên có thể được thực hiện bằng cách tìm kiếm điểm gián đoạn đột ngột trong tính năng màu. Những vấn đề thực hiện chính liên quan đến bộ dò biên là khả năng chính xác trích xuất các biên, độ bền của nhiễu, và độ phức tạp tính toán. Một bộ dò biên tối ưu nên giải quyết các vấn đề sau đây: − Nhận diện: không một biên ảnh nào có thể bỏ qua, và biên không được tạo sẵn không được phát hiện. − Cục bộ hóa: biên nên được cục bộ hoá, có nghĩa là khoảng cách giữa các biên thực và biên đã phát hiện nên được giảm thiểu. − Độ nhạy: một bộ dò biên tối ưu chỉ nên có một đáp ứng với một biên duy nhất Trong chụp ảnh xám đen trắng, biên thường được định nghĩa như là những điểm gián đoạn cường độ sắc nét (mức xám), hay biên vật lý thường trùng với những nơi chiếu sáng mạnh và thay đổi sự phản chiếu. Định nghĩa của một biên trong ảnh màu có nhiều khó khăn hơn. Trong trường hợp ảnh màu, đại diện trong không gian màu ba chiều (3-D), biên có thể được định nghĩa là không liên tục trong lĩnh vực đại diện cho ảnh vector màu. Bằng cách này, biên chia các hình ảnh trong khoảng màu sắc khác nhau, và sự biến thiên về màu sắc đã được kể đến. Các phương pháp đơn giản để phát hiện biên màu được dựa trên phần mở rộng của các toán tử đơn sắc. Những kỹ thuật này được áp dụng cho ba kênh màu độc lập, thực hiện phát hiện biên xám trên mỗi kênh màu. Các kết quả này sau đó được kết hợp để cung cấp một sơ đồ biên duy nhất. Nói chung, để phát hiện được biên ảnh màu, các kỹ thuật dựa trên biên độ được mở rộng bằng cách lấy biên độ tối đa của gradient, tổng trọng số của chúng, các gốc nghĩa là ô của tổng bình phương biên độ của các sơ đồ biên, hoặc bằng cách thực hiện các phép biến đổi riêng lẻ kết quả đầu ra. 3.2 Mô hình ba màu Để xác định màu sắc một cách định lượng ta xuất phát từ điểm 3 màu (tức là mỗi màu đều được tạo ra bởi 3 màu cơ bản). Sinh viên: Đặng Thị Thương – Lớp CT1101
  35. 35 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Mô hình 3 mầu trở nên rõ rệt ở trong mô hình trộn mầu. Sự trộn mầu cộng diễn ra khi xuất hiện nhiều kích thích khác nhau về mầu, chúng đều được thể hiện qua một thành phần mầu cơ bản nào đó để hình thành mầu mới. Do không có tập hợp 3 mầu cơ bản nào mà từ đó có thể tạo ra tất cả các mầu nên Uỷ ban quốc tế về chiếu sáng CIE đã đưa ra mô hình trong đó mỗi mầu được đặc trưng bằng đường cong phân bố năng lượng của chúng. Tiêu chuẩn của CIE ("Commission Internationale d'Eclairage") về các bước sóng như sau: Hình 3.1: Các màu quang phổ theo tiêu chuẩn CIE trong đó x – đỏ (λx = 700 nm), y – lục (λy = 546,1 nm), z – lam (λz = 435,8 nm) là 3 thành phần của 1 màu nào đó trong các màu cơ bản của CIE. Khi đó các thành phần màu x, y, z được tính như sau trong bản màu CIE 2D: x y z x y z 1 x y x y z x y z x y z * Mô hình màu RGB (Red – Green - Blue): Lục (0,1,0) Vàng (1,1,0) Trắng (1,1,1) Xanh tím (0,1,1) Đen (0,0,0) Đỏ (1,0,0) Lam (0,0,1) Đỏ tươi (1,0,1) Hình 3.2: Biểu diễn mô hình màu RGB trên trục tọa độ Sinh viên: Đặng Thị Thương – Lớp CT1101
  36. 36 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Theo Thomas Young (1801) ảnh được tổ hợp từ 3 màu cơ bản red, green, blue; từng đôi sẽ cho ra 3 màu thứ cấp yellow (vàng), cyan (lục lam) và magenta (đỏ lila). Màu trắng thu được khi kết hợp cả 3 màu cơ bản. Sự thay đổi cường độ của các màu thành phần sẽ tạo được giá trị mày bất kỳ trong phổ màu. Ta có: C = rR + gG + bB trong đó: C : màu hay kết quả của ánh sáng kết hợp. (r, g, b) : các tọa độ màu trong [0,1], cường độ của ánh sáng chiếu hay bộ ba giá trị kích thích RGB. (R, G, B) : các màu chính red, green, blue. * Mô hình màu CMY (Cyan – Megenta – Yellow): Đỏ tươi (0,1,0) Lam (1,1,0) Đen (1,1,1) Đỏ (0,1,1) Trắng (0,0,0) Xanh tím (1,0,0) Vàng (0,0,1) Lục (1,0,1) Hình 3.3: Biểu diễn mô hình màu CMY trên trục tọa độ Mô hình màu CMY hiển thị ánh sáng và màu sắc phản xạ từ mực in. Nói cách khác, dùng để xuất thông tin mầu ra các thiết bị như máy in. Để mô tả ảnh màu ba màu sẽ được tách ra và in chồng lên nhau. Sự chuyển đổi giữa 2 hệ RGB và CMY: C 1 R Color = cC + mM + yY M 1 G Y 1 B * Mô hình màu YIQ: Mô hình màu YIQ là mô hình màu được ứng dụng trong truyền hình màu băng tần rộng tại Mỹ, do đó nó có mối quan hệ chặt chẽ với màn hình đồ họa raster. Sinh viên: Đặng Thị Thương – Lớp CT1101
  37. 37 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu YIQ là sự biến đổi tương ứng của tín hiệu RGB nhằm đạt được một hiệu suất truyền phát tốt hơn và giữ nguyên tính tương thích với ti vi đen trắng thế hệ trước. Tín hiệu truyền sử dụng trong hệ thống NTSC (National Television System Commitee). Sự biến đổi RGB thành YIQ được xác định theo công thức: Y 0.299 0.587 0.114 R I 0.596 0.275 0.321 * G Q 0.212 0.523 0.311 B 3.3 Các phƣơng pháp phát hiện biên ảnh màu Như ta đã biết ảnh màu tổ hợp từ 3 màu cơ bản được thu nhận trên băng giải tần khác nhau và để lưu trữ ảnh màu ta có thể lưu trữ từng màu riêng biệt, mỗi màu lưu trữ như một ảnh đa cấp xám. Vì vậy để phát hiện biên ảnh màu ta có thể dùng phương pháp đơn giản nhất là: − Bước 1: Chuyển đổi ảnh màu thành ảnh đa mức xám theo công thức: G = 0.299*R + 0.587*G + 0.114*B Hay: G = (R + G + B) / 3 − Bước 2: Dùng các phương pháp phát hiện biên cho ảnh đa mức xám để tìm biên. Ngoài ra ta cũng có thể dùng các phương pháp sau: 3.3.1 Toán tử Vector Gradient Phương pháp thường dùng để xấp xỉ các đạo hàm là sai số giữa các pixel trong các lân cận nhỏ trong một ảnh. Gọi z là giá trị pixel trong một lân cận kích thước 3 x 3. Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8 Z9 Một xấp xỉ của đạo hàm riêng phần theo x (phương dọc) tại tâm điểm của vùng (z5) được cho bởi độ chênh lệch: Gx = (z7 + 2z8 + z9) – (z1+ 2z2 + z3) Tương tự đạo hàm theo phương y được xấp xỉ bởi độ chênh lệch Gx = (z3 + 2z6 + z9) – (z1+ 2z4 + z7) Các con số này được tính dễ dàng tại mọi điểm trong ảnh bằng phép nhân chập ảnh lần lượt với từng mặt nạ nhân chập (các mặt nạ Sobel, Prewitt). Sau đó xấp xỉ của đáp ứng gradient ảnh thu được bằng cách cộng hai trị tuyệt đối của hai Sinh viên: Đặng Thị Thương – Lớp CT1101
  38. 38 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu ảnh được chập. Ở chương trước Gradient được tính toán theo cách được mô tả là một trong những phương pháp dùng để tách biên ảnh đa mức xám, nhưng ở chương này ta quan tâm tới việc tính gradient trong không gian màu RGB. Tuy nhiên phương pháp này có thể ứng dụng được trong không gian 2D nhưng không mở rộng được cho không gian có chiều lớn hơn. Cách duy nhất để sử dụng nó đối với các ảnh RGB là tính gradient của mỗi thành phần màu sau đó kết hợp các kết quả. Do đó Vector gradient (biên độ và hướng) được định nghĩa: cR (x, y) R(x, y) c(x, y) cG (x, y) G(x, y) cB (x, y) B(x, y) Sau đây là một trong những cách mà khái niệm građient được mở rộng với các hàm vector. Hàm vô hướng f(x, y) gradient là một vector mà nó chỉ hướng của tỷ lệ thay đổi cực đại tại tọa độ (x,y). Lấy r, g, b là các vector đơn vị theo các trục R, G, B của không gian màu RGB và định nghĩa các vector: R G B u r g b x x x R G B v r g b y y y Đặt các số gxx, gxy, gyy được định nghĩa như sau: R 2 G 2 B 2 g u u uT u xx x x x 2 2 2 T R G B g v v v v yy y y y R R G G B B g u v uT v xy x y x y x y Chú ý: R, G, B và các giá trị g là các hàm của x và y. Chú ý này được thể hiện trong Di Zenzo[1986] nói rằng hướng của tỉ lệ thay đổi cực đại của c (x,y) là một hàm (x,y): 1 2g x, y tan 1 xy 2 gxx g yy và giá trị của tỷ lệ thay đổi (biên độ của gradient) theo các hướng được cho bởi các phần tử của: Sinh viên: Đặng Thị Thương – Lớp CT1101
  39. 39 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 1 1/ 2 F x, y g g g g cos2 2g sin 2 2 xx yy xx yy xy Chú ý: θ(x,y) và Fθ(x,y) là các ảnh có cùng kích cỡ với ảnh đầu vào. Các phần tử θ(x,y) là các góc tại mỗi điểm gradient được tính và Fθ(x,y) là ảnh gradient. -1 Vì tan = tan(α ± π) nếu θ0 là một nghiệm của phương trình tan θ0 = ± π/2 Fθ(x,y) = Fθ+π(x,y) F cần được tính chỉ với các giá trị của θ trong nửa khoảng [0, π). Sự thật là phương trình tan-1 cho 2 giá trị lệch nhau 900 nghĩa là phương trình này nghiệm đúng với mỗi cặp (x,y) có hướng vuông góc nhau. Dọc theo một trong những hướng này F là cực đại, và nó sẽ là cực tiểu nếu theo hướng còn lại. kết quả nhận được bằng cách chọn giá trị lớn nhất tại mỗi điểm. * Thuật toán: - Input: Ảnh RGB - OutPut: ảnh đã tách biên. - Các bước thực hiện: + Tính đạo hàm x, y của 3 thành phần ảnh với mặt nạ được chọn. + Tính các tham số vector gradient gxx, gyy, gxy θ1, θ2 + Tính F x, y max F x, y ,F x, y và chuẩn hóa trong khoảng 1 2 [0,1] + So sánh với ngưỡng,lấy giá trị lớn nhất tại mỗi điểm được ảnh tách biên 3.3.2 Phƣơng pháp Vector Field Sự khác biệt giữa hai màu giống nhau tại vị trí χ1 và χ2 của vector Field được gọi là sự tương phản cục bộ, được cho bởi x x 1 x 2 . Khi khoảng cách giữa hai vector hướng về 0, sự khác biệt trở thành : 2 x dx j 1 d j j 2 2 2 2 T 2 x x d 1 g11 g12 d 1 dx * d k d l gkl d k d l k 1 l 1 k l k 1 l 1 d 2 g 21 g 22 d 2 x x 3 x j x j gkl k l j 1 k l Sinh viên: Đặng Thị Thương – Lớp CT1101
  40. 40 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Đối với một vector đơn vị n = (cos θ, sin θ), dx2(n) cho thấy tỷ lệ thay đổi của hình ảnh theo hướng n: dx2 = E cos2 θ + 2F cos θ sin θ + G sin2 θ = (E + G+ H cos 2θ + 2Fsin 2θ)/2 với: E = g11 ; F = g12 − g21 ; G = g22 ; H = g11 − g22 Các giá trị riêng tương ứng và các vector đặc trưng là: 1 E G H 2 4F2 2 n cos ,sin với: . 2 1 2F arctan 2 H 2 Hai đáp số tương ứng với cực đại và cực tiểu của dx , và θ+, θ− định nghĩa theo hai hướng: cùng một trong số x đó họ đạt tỷ lệ biến đổi cực đại của nó, cùng một số khác đạt đến mức cực tiểu của nó. Thay vì sử dụng hàm lượng giác, các Vector đặc trưng n = [n1, n2] có thể được tính bằng cách sử dụng vector υ = [H, 2F], với tính chất: υ = λ+ − λ− Sau đó: n (1 b)/ 2,sign F (1 b)/ 2 với b = H / || υ || Cường độ của một biên trong trường hợp giá trị vector được miêu tả λ+ bởi sự khác biệt giữa các cực trị: (E G)/ 2 H2 4F2 3.3.3 Bộ dò biên Vector Order-Statistic Toán tử dựa trên Order-Statistic đóng vai trò quan trọng trong việc xử lý ảnh và đã được sử dụng rộng rãi trong xử lý ảnh đơn sắc và ảnh màu. Các loại bộ dò biên dựa trên Order-Statistic được xây dựng như là một sự kết hợp tuyến tính của các mẫu vector tới cửa sổ xử lý. Tập các hệ số khác nhau của sự kết hợp tuyến tính tạo ra bộ dò biên khác nhau về hiệu suất và hiệu quả. Toán tử phát hiện biên đơn giản nhất dựa trên Order-Statistic là bộ dò vector vùng (VRD – vector range detector).Toán tử này xác định độ lệch giữa trung bình vector cấp thấp nhất với vector cấp cao nhất. Cho các vector hình ảnh trong một của sổ W ký hiệu xi , i = [1,n] khi đó: VRD = ρ(x1, xn) Tốc độ và hiệu suất tính toán của công thức trên đạt yêu cầu trong trường hợp ảnh không bị ảnh hưởng bởi nhiễu. Trong môi trường nhiễu, các xung có mặt trong ảnh được phát hiện sai biên. Để làm giảm bớt nhược điểm này, các biện pháp tán sắc được biết như là ước lượng chắc chắn trước nhiễu có thể được áp dụng. Sinh viên: Đặng Thị Thương – Lớp CT1101
  41. 41 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Bộ dò vector tán sắc (VDD – vector dispersion detectior) được định nghĩa: n với j =[j,n] VDD j j x j trong đó ψj là hệ trọng số. VRD là một trường hợp đặc biệt của VDD nếu: ψ1 = − 1, ψn = 1 và ψj = [2, n – 1 ] Định nghĩa này có thể được khái quát bằng cách sử dụng một tập hợp các hệ số k và kết hợp các kết quả độ lớn vector là một cách mong đợi. Ví dụ, các bộ dò vector tán sắc tổng quát (GVDD – generalized vector dispersion detector) sử dụng một toán tử min làm giảm thiểu ảnh hưởng của xung nhiễu: n GVDD min jl xl với j = [1,k], k là tham số của bộ dò. j l 1 Cụ thể, bộ dò biên màu có thể thu được từ GVDD bằng cách chọn tập hợp các hệ số ψjl. Một thành viên đặc biệt của họ GVDD là bộ dò vector tán sắc tối thiểu (MVDD – minimin vector dispersion detector), được định nghĩa như sau: MVDD min x(n j 1) , x( ) với j = [1,k] và α < n j Trong đó: – xˆ( ) là trung bình cộng của các vector được sắp xếp từ α đầu tiên (αVMF) – k, α kiểm soát việc điều hòa giữa tính toán phức tạp và hiệu quả ngăn chặn nhiễu. Các vectơ thứ bậc cao có thể sẽ đại diện cho điểm ảnh bị xáo trộn bởi nhiễu, ấn định tham số j dẫn tới một bộ dò biên mạnh với nhiễu xung: * MVDD x(n k 1) , xˆ( ) k < n đó cũng là miễn nhiễm với ảnh hưởng của nhiễu Gaussian, do toán tử trung bình thực hiện trong . Một phác họa thay thế của toán tử GVDD dùng khái niệm lọc lân cận gần nhất tương ứng. Bộ dò vùng vector lân cận gần nhất (NNVRD – nearest-neighbor vector range detector) được định nghĩa như sau: n 1 R R NNVRD x , x , n j (n) j ( j) j ˆ j 1 n R n R n Với: ψj : hệ số hiệu chỉnh bù được xác định tương ứng. R(n) : giá trị trung bình số học của các khoảng cách gộp Rj với j = [1, n] Toán tử MVDD cũng có thể được kết hợp với toán tử NNVRD để cải thiện hiệu quả của nó khi có nhiễu xung. Bộ dò phân tán vector lân cận gần nhất Sinh viên: Đặng Thị Thương – Lớp CT1101
  42. 42 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu tối thiểu (NNMVDD – nearest-neighbor minimum vector dispersion detector) được định nghĩa như sau: n NNMVDD min x(n j 1) , l x(l) , for j 1,k k n j l 1 Sinh viên: Đặng Thị Thương – Lớp CT1101
  43. 43 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu CHƢƠNG IV: PHƢƠNG PHÁP PHÁT HIỆN BIÊN THEO WAVELET 4.1 Giới thiệu Phát hiện biên là 1 bước quan trọng trong nhận dạng, phân đoạn ảnh và phân tích cảnh. Các phương pháp tiếp cận để phát hiện biên ko đạt trước nhiễu trong hình ảnh và có thể gây ra các vấn đề trong nhiều ứng dụng. Nhưng nhiễu bị giảm rất hiệu quả bởi phương pháp lọc wavelet mà không làm giảm đáng kể độ phân giải hình ảnh. Không giống như phát hiện biên canny trong đó bước đầu tiên là làm mịn ảnh bằng bộ lọc Gauss để giảm tác động của nhiễu và bước tiếp theo là xác định biên. Trong Wavelet hai bước này được kết hợp thành một bước và do đó kỹ thuật dựa trên wavelet tính toán hiệu quả hơn. Đó là thực nghiệm đã chứng minh rằng phương pháp phát hiện biên dựa trên Wavelet cho kết quả tốt hơn so với kỹ thuật truyền thống với các ảnh nhiễu. Việc phân tích Wavelet là phân tích cục bộ và phù hợp cho việc phân tích tần suất thời gian. Trong kỹ thuật phát hiện biên Wavelet, biến đổi được sử dụng là biến đổi Wavelet rời rạc (DWT – Discrete Wavelet Transform) và bộ lọc là một trong những tìm kiếm cho cực đại địa phương trong 1 miền wavelet. Các biến đổi Wavelet cung cấp bộ phân tích đa tỉ lệ, có thể được áp dụng để phát hiện biên. Mallat và Zhong sử dụng cực đại địa phương giá trị tuyệt đối của các biến đổi wavelet để thực hiện phát hiện biên. Peytavin nghiên cứu phương pháp phát hiện biên nhiều hướng và nhiều độ phân giải bằng cách sử dụng một wavelet, đó là lấy đạo hàm thứ nhất của hàm làm mịn. Barlaud sử dụng biến đổi wavelet song trực giao (biorthogonal wavelet transform) để phát hiện biên. Một sở hữu đáng kể của các biến đổi wavelet là khả năng mô tả đặc điểm các quy luật địa phương của các hàm. Đối với một hình ảnh f (x, y), các biên của nó tương ứng với điểm kỳ dị của f (x, y), và do đó có liên quan đến các cực đại địa phương của mô đun biến đổi wavelet. Do đó, biến đổi wavelet là một phương pháp hiệu quả để phát hiện biên. Biến đổi wavelet hơi tương tự với biến đổi Fourier ngắn hạn (Short Time Fourier Transform – STFT) ngoại trừ cửa sổ không cố định như trong STFT. Việc biến đổi wavelet linh hoạt hơn và nó có thể có bất cứ hàm lựa chọn nào, có thể được co lại và giãn ra để phân tích các tín hiệu. Các Wavelet có thể được hiểu là các làn sóng nhỏ trừu tượng thể hiện trong một giá trị trung bình số không. Các biến đổi wavelet ánh xạ hàm thời gian vào một hàm hai chiều của a và b. Các tham số a được gọi là thang tỉ lệ và nó tỉ lệ một hàm bằng cách nén hoặc kéo dài nó. Các tham số b được gọi là biến đổi của hàm Wavelet dọc theo trục thời gian. Sinh viên: Đặng Thị Thương – Lớp CT1101
  44. 44 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Hàm Wavelet ψ(t) được viết như sau: 1 t b a t b (4.1) a a trong đó: a : là hệ số tỉ lệ. b : là biến đổi dọc theo trục thời gian t. 1 : hệ số được chuẩn hóa. a 4.2 Biến đổi Wavelet liên lục (The Continuous Wavelet Transform – CWT) Trong biến đổi wavelet liên tục, một hàm ψ (“psi”) được sử dụng để tạo ra một họ các wavelet ψ(at + b), với a, b là các số thực và tham số a làm giãn nở các hàm ψ và b dịch nó. Lưu ý rằng từ “liên tục” đề cập đến biến đổi chứ ko phải wavelet. Các biến đổi wavelet liên tục biến một tín hiệu s(t) vào trong một hàm với hai biến số (tỉ lệ và thời gian) như trong phương trình: c a,b s(t) (at b)dt (4.2) Với ψ là wavelet gốc và c là hệ số của biến đổi wavelet. Trong bất kỳ ứng dụng ảnh, mã hóa hoàn thiện tái tạo là quan trọng nhất. Ngay cả sau khi xử lý ảnh các ảnh được tái tạo sẽ chỉ được một xấp xỉ của ảnh gốc. Nếu chuyển đổi không phải là khả nghịch nó có thể được cho là đã biến đổi các mô hình khác nhau xử lý giống hệt nhau. Định lý 1: cho s(t) L2 (R) và CWT của s(t), liên quan đến ψ(t), ta có: 1 t b CWT a,b s(t) ( )dt (4.3) a a Nếu ψ(t) là vậy, mà biến đổi này là khả nghịch thì: 1 1 t b 1 s(t) CWT(a,b) ( ) 2 dadb (4.4) c a 0 a a a Trong đó cψ là một hằng số chỉ phụ thuộc vào ψ(t) và a dương. Liên tục có giá trị: ( ) 2 c d (4.5) 0 Từ đó đặt ra một điều kiện thỏa mãn ψ(t). Để cψ < ∞, ψ(t) phải thỏa mãn: ( ) ,for any (4.6) Và ψ(0) = 0, có nghĩa là (t)dt 0 . Sinh viên: Đặng Thị Thương – Lớp CT1101
  45. 45 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Định lý này khẳng định việc biến đổi một chiều tín hiệu s(t) thành miền wavelet hai chiều của (a,b) là nghịch nếu việc biến đổi một đẳng cự lên một hằng số cψ. 4.3 MRA – Multi-resolution Analysis MRA là sự phân hoạch một tín hiệu s(t) thành các thành phần của tỉ lệ khác nhau 2-m, trong đó m là một số nguyên. Liên kết với mỗi tỉ lệ là một không gian con Vm. Các không gian con là các hàm thời gian, đáp ứng các điều kiện sau đây: 1.) Liên tiếp được lồng nhau. Tức là cho tất cả j. V j V j 1 2 0 V2 V1 V0 V 1 V 2 V 3 L (R) Nếu hàm s(t) trong Vj, thì s(2t) trong Vj-1 và ngược lại. 2.) Sự tồn tại của hàm tỉ lệ trực giao. Có sự tồn tại của một hàm tỉ lệ còn được gọi là wavelet cha, (t) V0 sao cho tập: m 2 m mn(t) 2 2 t n : n interger (4.7) là một trực giao tiêu chuẩn trải rộng trên Vm. Các hợp của không gian này là hẹp, tức là cho tất cả f trong L2 (R) 0 lim f Pj f 2 0 (4.8) j L 0 trong đó Pj là phép chiếu trực giao lên Vj 3.) Hàm cơ sở được định nghĩa bởi hàm sai phân 2 tỉ lệ. 0n (t) kéo dài V0 và 1n (t) kéo dài V-1 và V-1 bao gồm V0, 00(t) (t) là một tổ hợp tuyến tính của 1n (t) 2 2t n , nghĩa là: p 1 (t) 2 g(l) 2t l (4.9) l 0 trong đó g(l) là hệ số kết hợp. 4.) Giao điểm của các không gian là giảm tới hàm NULL. 0 lim Pj f 2 0 (4.10) j L 5.) Tồn tại một hàm V0 sao cho họ (. k),k Z là cơ sở Riesz của V0 . Sinh viên: Đặng Thị Thương – Lớp CT1101
  46. 46 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 4.4 Xây dựng một Wavelet Phương trình tỉ lệ 2 được cho bởi: x k hk 1,k x k hk 2 2x k (4.11) hk , 1,k g(x) V Giả sử 1 và g x k gk 2 2x k (4.12) k với gk ( 1) h1 k k g x k ( 1) h1 k 1,k x (413) j 2 j Ta định nghĩa: g jk (x) 2 g(2 x k) (4.14) vì vậy 0k , 0l 0 cho tất cả số nguyên k và l. Định nghĩa W0 là không gian mở rộng bởi g0k , trong đó cho thấy W0 là phần bù trực giao của V0 trong V1. V1 V0 W0 Tương tự cho Wj là không gian mở rộng bởi gjk , trong đó cho thấy Wj là phần bù trực giao của Vj trong Vj+1. Vj V0 W0 W1 Wj 1 2 Vì thế, gjk là cơ sở trực giao cho L (R). Chúng cũng là trực giao. Do đó chứng minh rằng ψ(x) = g(x) là một Wavelet 4.5 Phân hoạch và tái thiết wavelet Xét cj, k như là hệ số wavelet cho c j,k , j,k (x) j,k (x)dx (4.15) Chúng ta có thể sử dụng các ký hiệu trên cho bất kỳ hàm ƒ mà chúng ta quan tâm c j,k f , j,k f (x) j,k (x)dx (4.16) tương tự d j,k f , j,k f (x) j,k (x)dx (4.17) Giả sử chúng ta có hệ số cấp cao cj, k cho một hàm f đưa ra, chúng ta thu được các hệ số cấp độ thấp hơn, chi tiết. c j 1,k hl 2kc j,l (4.18) l d j 1,k gl 2kc j,l (4.19) l Nhắc lại cấu trúc của không gian MRA, xét hệ số theo cách tương tự: Sinh viên: Đặng Thị Thương – Lớp CT1101
  47. 47 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Quá trình trên được gọi là downsamling. Các hệ số downsampled sẽ chính là một nửa đại lượng các hệ số trước đó. Ta có thể viết: c j,k j,k x c j 1,k j 1,k x d j 1,k j 1,k x (4.20) k k k nếu chúng ta tiếp tục với chuỗi MRA như trên, chúng ta có thể thấy rằng j 1 c j,k j,k x c j0,k j0,k x d j,k j,k x (4.21) k k j j0 k Phương trình trên là diễn giải của biến đổi wavelet rời rạc (DWT) Tái thiết wavelet rất tương tự như sự phân hoạch wavelet. Chúng ta sử dụng mô hình chuỗi MRA để upsample các hệ số. Trong tái thiết chúng ta xét các hệ số mức độ thấp hơn, hệ số chi tiết và kết hợp chúng để có được hệ số mức độ cao hơn. Mỗi lần chúng ta thực hiện bổ sung các hệ số số lượng là gấp đôi số lượng các hệ số của hệ sô mức độ thấp trước đó. 4.6 Biến đổi Wavelet rời rạc (DWT – Discrete Wavelet Transform ) Không giống như biến đổi Fourier, DWT không phải là một đối tượng duy nhất. Khái niệm về DWT lần đầu tiên được giới thiệu bởi Stromberg từ Littlewood-Paley phân tách các toán tử một chức năng.Hai chiều DWT giảm từ sơ đồ kim tự tháp Laplace của Burt và Adelson như trong hình sau: Hình 4.1: Sơ đồ kim tự tháp Laplace phát triển bởi Burt và Adelson Sinh viên: Đặng Thị Thương – Lớp CT1101
  48. 48 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Nếu hàm ngày càng mở rộng là một dãy các con số, như các mẫu của một hàm liên tục f (x), các hệ số kết quả được gọi là biến đổi Wavelet rời rạc (DWT) của f (x). DWT biến đổi một tín hiệu thời gian rời rạc trên một phép biểu diễn Wavelet rời rạc. Chúng ta không tính toán DWT về ma trận do vấn đề lưu trữ, thay vì vậy chúng ta sử dụng bộ lọc để tính toán DWT. Cho một dãy a = { , a-1, a0, a1, } và hai bộ lọc xung h và g. Chúng ta định nghĩa phép nhân chập như sau: (Ha)k hl 2k ak l (Ga)k gl 2k ak l trong đó H và G tương ứng với một bước của DWT (lên hoặc xuống). Trong phân tách, hàm được nhân chập lần lượt với hai bộ lọc H (thông thấp) và G (thông cao). Mỗi hàm kết quả bị mất đi bởi việc loại bỏ một trong hai mẫu. Tín hiệu thông cao bị loại bỏ, và ta lặp lại với tín hiệu thông thấp. Tái giả thiết, chúng ta khôi phục lại mẫu bằng cách chèn 0 giữa mỗi mẫu, sau đó chúng ~ ~ ta nhân chập với các bộ lọc liên hợp H và G , thêm các hàm kết quả và nhân kết quả với 2. Chúng ta lặp lại cho đến tỉ lệ nhỏ nhất. Giải thuật 2D dựa trên những biến số riêng biệt để ưu tiên x và hướng. Hàm tỉ lệ được xác định như sau: x, y x y Tín hiệu chi tiết được lấy từ 3 Wavelet: * Wavelet dọc: 1 x, y x y * Wavelet ngang: 2 x, y x y * Wavelet chéo: 3 x, y x y Sinh viên: Đặng Thị Thương – Lớp CT1101
  49. 49 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu H.D f(2) j = 2 Horizontal Details V. D D.D j = 1 Horizontal Details j = 2 j = 2 j = 0 Diagonal Vertical Details Details j = 1 j = 1 Vertical Details Diagonal Details j = 0 j = 0 Hình 4.2: DWT của hai chiều tín hiệu 4.7 Phƣơng pháp phát hiện biên DWT Cường độ thay đổi đáng kể trong một hình ảnh thường xảy ra ở độ phân giải và tỉ lệ có trong không gian khác nhau. Bộ dò biên thông thường lựa chọn một mặt nạ không gian đặc biệt, phát hiện các biên ở độ phân giải cụ thể. Bộ dò biên với mặt nạ nhỏ nhạy cảm với nhiễu và tạo ra các biên giả. Ngược lại, với một mặt nạ lớn lại tương đối mạnh trước nhiễu, nhưng làm biến dạng các biên và có thể không phát hiện một số chi tiết tốt hơn. Vì vậy rất khó khăn để phát hiện các biên với một mặt nạ biên không gian duy nhất. Việc bảo toàn biên loại bỏ nhiễu mượn chính nó cho một quy trình dựa trên Wavelet để phát hiện biên. Các biên trong một tín hiệu cho phép tăng tới đỉnh cao vượt qua kết quả đầu ra của bộ lọc hoặc các băng con cụ thể tại các vị trí phù hợp. Đây là một đặc tính của DWT. Nói một cách khác, biên làm gia tăng đỉnh trên nhiều mức của các chi tiết tại các giá trị tọa độ mà di chuyển sang trái bằng một một nửa yếu tố tại mọi quá trình chuyển đổi từ một tỉ lệ tốt hơn tới một tỉ lệ thô hơn. Các biên mạnh, cao hơn các đỉnh trong DWT này. Do đó, một biên nào đó có thể được tìm thấy từ các biến đổi wavelet của đỉnh xác định tại các vị trí phù hợp. Các biến đổi wavelet của f (x) với tỉ lệ s và vị trí x, được tính liên quan tới wavelet ψa(x) được định nghĩa bởi: Sinh viên: Đặng Thị Thương – Lớp CT1101
  50. 50 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu a a Ws f (x) f s (x) Biến đổi wavelet với ψb(x): b b Ws f (x) f s (x) trong đó: ψ(x) là hàm Wavelet tại vị trí x. a, b : 2 số thực tùy ý Sau khi lấy đạo hàm ta được: d W a f (x) s ( f )(x) s dx s 2 b 2 d Ws f (x) s ( f s )(x) dx2 a b Các biến đổi wavelet Ws f (x) và Ws f (x) tương ứng với đạo hàm bậc nhất và đạo hàm bậc hai của dấu hiệu được làm min trong s. Hàm làm mịn 2-D được định nghĩa như bất cứ hàm θ(x,y) nào có tích phân qua x và y bằng 1 và đồng qui từ 0 tới ∞. Ảnh f(x,y) được làm mịn ở các tỉ lệ s khác nhau bằng việc nhân chập với θ(x,y). Vector gradient tính được cho bởi f s x, y . Biên được định nghĩa là các điểm (x0, y0) mà mô đun của vectơ gradient là cực đại về hướng. Chúng ta định nghĩa hai hàm wavelet như sau: x, y 1 x, y x x, y 2 x, y y 1 1 1 x y 2 1 2 x y 2 2 với: s x, y , ; s x, y , và f(x,y) = L (R ) s2 s s s2 s s Các biến đổi Wavelet được định nghĩa: 1 1 s f x f s x, y 2 2 s f x f s x, y Vậy ta có: 1 f x, y s 2 s f s x, y s f x, y 1 Do đó các điểm biên có thể được xác định từ các thành phần Ws f (x) và 2 Ws f (x) của biến đổi wavelet. Sinh viên: Đặng Thị Thương – Lớp CT1101
  51. 51 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu CHƢƠNG V: CÀI ĐẶT THỬ NGHIỆM VÀ NHẬN XÉT ĐÁNH GIÁ CÁC PHƢƠNG PHÁP 4.1 So sánh các phƣơng pháp phát hiện biên (Gradient. Laplace, Canny) a) Ảnh gốc b) Gradient (ngưỡng 20) c) Sobel (ngưỡng 128) d) Prewitt (ngưỡng 128) Sinh viên: Đặng Thị Thương – Lớp CT1101
  52. 52 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu e) Laplace (ngưỡng 50) f) Canny (ngưỡng 20) Hình 5.1: Biên ảnh theo Gradient, Laplace, Canny. Để so sánh sự khác nhau giữa các phương pháp ta sử dụng kết quả của phương pháp Sobel, Laplace và Canny. Từ kết quả thu được ở các hình trên ta có thể thấy, khi phát hiện biên, các biên không quan trọng nên được loại bỏ. - 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ỏ. - 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 chéo 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 Sup- pression” 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 biên không cần quan tâm đi. 4.2 Cài đặt thử nghiệm chƣơng trình Wavelet Transform Trong chương trình, em xin trình bày quá trình thực hiện biến đổi Wavelet: – Ảnh đầu vào: *.bmp, *.jpg, *.jpeg, *.png, *.tif, *.tiff. – Ảnh đầu ra: Ảnh đã tìm được biên. – Các bước thực hiện: Sinh viên: Đặng Thị Thương – Lớp CT1101
  53. 53 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Bƣớc 1: Mở hình ảnh và chuyển đổi (Transform DWT2D RGB Transform) ảnh với tỉ lệ 1, 2 hoặc 3. Có thể thêm vào các ngưỡng để loại bỏ nhiễu. Dưới đây, bộ lọc daub1 được chọn với 1 quy mô chuyển đổi mà không cần loại nhiễu: Hình 5.2: Biến đổi ảnh với tỉ lệ 1 và bộ lọc daub1. Sinh viên: Đặng Thị Thương – Lớp CT1101
  54. 54 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Ảnh biến đổi (co lại) sau khi chọn tỉ lệ 1 và bộ lọc daub1: Hình 5.3: DWT hai chiều tín hiệu. Sinh viên: Đặng Thị Thương – Lớp CT1101
  55. 55 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu Bƣớc 2: Loại bỏ thành phần tần số thấp (Transform Denoise) Hình 5.4: Loại bỏ thành phần tần số thấp. Hàm tương ứng trong lớp BaseDWT2D: void BaseDWT2D::remove_LLband() { if (m_status <= 0) return; unsigned int width = m_width / (unsigned int)(pow(2.0f, (float)getJ())); unsigned int height = m_height / (unsigned int)(pow(2.0f, (float)getJ())); Sinh viên: Đặng Thị Thương – Lớp CT1101
  56. 56 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu for (unsigned int y = 0; y < height; y++) for (unsigned int x = 0; x < width; x++) spec2d[y][x] = 0; } Bƣớc 3: Tái thiết lại hình ảnh (giãn ảnh với tỉ lệ 1). (Transform DWT2D RGB synth) Hình 5.5: Ảnh biến đổi sau khi xây dựng lại Bƣớc 4: Làm nổi biên (Abs values) bằng cách từ đi 128 từ ảnh và tính giá trị tuyệt đối: if (mr && mg && mb) { for (int i = 0; i < width * height; i++) { mr[i] = abs((int)mr[i] - 128); Sinh viên: Đặng Thị Thương – Lớp CT1101
  57. 57 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu mg[i] = abs((int)mg[i] - 128); mb[i] = abs((int)mb[i] - 128); } setRGB(m_clone, mr, mg, mb); } Hình 5.6: Ảnh sau khi được làm nổi biên. Bƣớc 5: Khuếch đại biên. (Transform->Contrast stretch) Ảnh nhận đc đã nổi được biên, tuy nhiên biên còn chưa rõ ràng. Vì vậy ta trải dài độ tương phản – bình thường hóa ảnh vào phạm vi 0 255, nhưng có thể có 1 vài điểm ảnh ở giới hạn trên của phạm vi đó do vậy không thực sự cải thiện được tình hình. Sự lựa chọn tốt hơn là bình thường hóa phi tuyến tính giống như tỉ lệ logarit, nhưng ở đây, ta chỉ cần nhân các dữ liệu điểm ảnh bằng một số giá trị và có được biên rõ hơn. Đối với tỉ lệ biến đổi 1, ta nhân với 7 hoạt động tốt và không vượt khỏi giới hạn 255 cho phần lớn các điểm ảnh. Nhưng với tỉ lệ 2 hoặc 3 ta có thể giảm số lượng nhân. void normalize(unsigned char* data, unsigned int size, float a, float b) { Sinh viên: Đặng Thị Thương – Lớp CT1101
  58. 58 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu float min = (float)data[0]; float max = (float)data[0]; for (unsigned int i = 0; i max) max = data[i]; } for (unsigned int i = 0; i 255.0f) val = 255.0f; data[i] = (unsigned char)val; } } Hình 5.7: Biên ảnh sau khi được khuếch đại. Sinh viên: Đặng Thị Thương – Lớp CT1101
  59. 59 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu 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. Sinh viên: Đặng Thị Thương – Lớp CT1101
  60. 60 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu KẾT LUẬN Trong quá trình tìm hiể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, em đã 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 tìm hiểu em 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, 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 tìm hiể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 tìm hiể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 tìm hiể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 tìm hiể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 Sinh viên: Đặng Thị Thương – Lớp CT1101
  61. 61 Tìm hiểu phương pháp phát hiện biên cho ảnh đa cấp xám và ảnh màu TÀI LIỆU THAM KHẢO: Tiếng Việt: [1]. Ts. Đỗ Năng Toàn & Ts. Phạm Việt Bình – “Giáo trình môn học Xử lý ảnh” – Đại Học Thái Nguyên – 2007. [2]. Lương Mạnh Bá & Nguyễn Thanh Thủy – “Nhập môn Xử lý ảnh số” – Nxb Khoa học và Kỹ thuật. [3]. Nguyễn Quang Sơn – “Nghiên cứu một số phương pháp phát hiện biên” – Luận văn thạc sĩ CNTT – Đại học Thái Nguyên. Một số địa chỉ khác trên internet . Tiếng Anh: [4]. John Canny − “A computational approach to edge detection” − Pattern Analysis and Machine Intelligence, IEEE Transactions on., PAMI-8(6):679–698, Nov. 1986 [5]. O. Rebecca Vincent & Olusegun Folorunso − “A Descriptive Algorithm for Sobel Image Edge Detection” – Processings of Informing Science & IT Education Conference (InSITE) 2009 [6]. + Keyword: Canny Edge Detection 09gr820 March 23, 2009 [7]. Rastislav Lukac, Konstantinos N. Plataniotis – “Color Image Processing Methods and Applications” (2007) – University of Toronto; Toronto, Ontario, Canada – CRC Press, Taylor & Francis Group [8]. Plataniotis, Konstantinos N. – "Comprehensive Analysis of Edge Detection in Color Image Processing" (1999) – Electrical and Computer Engineering Publications and Research. Paper 1 – [9]. Jun Li – “A Wavelet Approach to Edge Detection” (2003) – Master of Science (Mathematics & Statistics), Sam Houston State University. Huntsville, Texas. [10]. Chaganti, Venkata RaviKiran – “Edge Detection of Noisy Images Using 2- D Discrete Wavelet Transform” (2005) – Master of Science(Electrical & Computer Engineering), The Florida State University. [11]. + Keyword: Edge Detection in Images with Wavelet Transform Sinh viên: Đặng Thị Thương – Lớp CT1101