Bài giảng Xử lý ảnh (Bản mới nhất)

pdf 70 trang ngocly 200
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý ảnh (Bản mới nhất)", để 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:

  • pdfbai_giang_xu_ly_anh_ban_moi_nhat.pdf

Nội dung text: Bài giảng Xử lý ảnh (Bản mới nhất)

  1. 1 TRƢỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN BÀI GIẢNG XỬ LÝ ẢNH TÊN HỌC PHẦN : XỬ LÝ ẢNH MÃ HỌC PHẦN : 17411 TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN HẢI PHÒNG - 2011 .
  2. 2 MỤC LỤC Chƣơng I: Tổng quan về xử lý ảnh số 7 1.1. Xử lý ảnh số là gì? 7 1.2. Nguồn gốc của xử lý ảnh số 7 1.3. Các ứng dụng của xử lý ảnh số 7 1.4. Các bước cơ bản trong xử lý ảnh số 8 1.5. Các thành phần của một hệ thống xử lý ảnh 11 Chƣơng II: Các kiến thức cơ bản về ảnh số 14 2.1. Cảm nhận thị giác 14 2.2. Lấy mẫu và lượng tử hóa ảnh 14 2.3. Mối quan hệ giữa các điểm ảnh 16 Chƣơng III: Nâng cao chất lƣợng ảnh trong miền không gian 19 3.1. Các phép biến đổi mức xám cơ bản 19 3.2. Xử lý histogram 20 3.3. Nâng cao chất lượng ảnh sử dụng các toán tử số học/logic 21 3.4. Bộ lọc trong miền không gian 25 3.5. Các bộ lọc làm mượt ảnh trong miền không gian 29 3.6. Các bộ lọc làm sắc nét ảnh trong miền không gian 31 Chƣơng IV: Nâng cao chất lƣợng ảnh trong miền tần số 34 4.1. Phép biến đổi Fourier và miền tần số 34 4.2. Các bộ lọc làm mượt ảnh trong miền tần số 37 4.3. Các bộ lọc làm sắc nét ảnh trong miền tần số 38 Chƣơng V: Nén ảnh 40 5.1. Các kiến thức cơ bản 40 5.2. Nén ảnh không mất thông tin 42 5.3. Nén ảnh có mất thông tin 45 Chƣơng VI: Xử lý hình thái ảnh 50 6.1. Phép giãn ảnh và phép co ảnh nhị phân 50 6.2. Phép mở ảnh và phép đóng ảnh nhị phân 51 6.3. Một số thuật toán hình thái cơ bản trên ảnh nhị phân 51 6.4. Xử lý hình thái ảnh xám 53 Chƣơng VII: Phân đoạn ảnh 59 7.1. Phát hiện tính không liên tục 59
  3. 3 7.2. Phân đoạn ảnh dựa vào các vùng ảnh con 60 Một số đề thi mẫu 64
  4. 4 Tên học phần: Nhận dạng và xử lý ảnh Loại học phần: 2 Bộ môn phụ trách giảng dạy: Hệ thống Thông tin Khoa phụ trách: CNTT. Mã học phần: 17411 Tổng số TC: 4 Tổng số tiết Lý thuyết Thực hành/Seminar Tự học Bài tập lớn Đồ án môn học 75 45 30 0 không không Học phần học trƣớc: Không yêu cầu. Học phần tiên quyết: Không yêu cầu. Học phần song song: Không yêu cầu. Mục tiêu của học phần: Cung cấp các kiến thức về lĩnh vực xử lý ảnh số; Giúp cho sinh viên nắm được các kỹ thuật xử lý ảnh cơ bản. Nội dung chủ yếu: Các kiến thức cơ bản về ảnh số; Các kỹ thuật nâng cao chất lượng ảnh; Các thuật toán xử lý hình thái; Các kỹ thuật phân đoạn ảnh; Các thuật toán nén ảnh và chuẩn ảnh nén. Nội dung chi tiết: PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH BT KT Chƣơng I: Tổng quan về xử lý ảnh số 5 3 2 1.1. Xử lý ảnh số là gì? 1.2. Nguồn gốc của xử lý ảnh số 1.3. Các ứng dụng của xử lý ảnh số 1.4. Các bước cơ bản trong xử lý ảnh số 1.5. Các thành phần của một hệ thống xử lý ảnh Chƣơng II: Các kiến thức cơ bản về ảnh số 5 3 2 2.1. Cảm nhận thị giác 2.2. Lấy mẫu và lượng tử hóa ảnh 2.3. Mối quan hệ giữa các điểm ảnh Chƣơng III: Nâng cao chất lƣợng ảnh trong miền không gian 15 9 6 3.1. Các phép biến đổi mức xám cơ bản 3.2. Xử lý histogram 3.3. Nâng cao chất lượng ảnh sử dụng các toán tử số học/logic 3.4. Bộ lọc trong miền không gian 3.5. Các bộ lọc làm mượt ảnh trong miền không gian 3.6. Các bộ lọc làm sắc nét ảnh trong miền không gian Chƣơng IV: Nâng cao chất lƣợng ảnh trong miền tần số 15 9 6
  5. 5 PHÂN PHỐI SỐ TIẾT TÊN CHƢƠNG MỤC TS LT TH BT KT 4.1. Phép biến đổi Fourier và miền tần số 4.2. Các bộ lọc làm mượt ảnh trong miền tần số 4.3. Các bộ lọc làm sắc nét ảnh trong miền tần số Chƣơng V: Nén ảnh 15 7 6 2 5.1. Các kiến thức cơ bản 5.2. Nén ảnh không mất thông tin 5.3. Nén ảnh có mất thông tin Chƣơng VI: Xử lý hình thái ảnh 10 6 4 6.1. Phép giãn ảnh và phép co ảnh nhị phân 6.2. Phép mở ảnh và phép đóng ảnh nhị phân 6.3. Một số thuật toán hình thái cơ bản trên ảnh nhị phân 6.4. Xử lý hình thái ảnh xám Chƣơng VII: Phân đoạn ảnh 10 4 4 2 7.1. Phát hiện tính không liên tục 7.2. Phân đoạn ảnh dựa vào các vùng ảnh con Nhiệm vụ của sinh viên: Tham dự các buổi học lý thuyết và thực hành, làm các bài tập được giao, làm các bài thi giữa học phần và bài thi kết thúc học phần theo đúng quy định. Tài liệu học tập: 1. Lương Mạnh Bá, Nguy n Thanh Thủy, h h , Nhà xuất bản Khoa học và Kỹ thuật Hà Nội, 2003. 2. V Đức Khánh, i h h, Nhà xuất bản Thống kê, 2003. 3. Rafael C. Conzalez & Richard E. Woods, Digital Image Processing, 2nd edition, Pearson Education, 2004. Hình thức và tiêu chuẩn đánh giá sinh viên: - Hình thức thi: thi viết. - Tiêu chuẩn đánh giá sinh viên: căn cứ vào sự tham gia học tập của sinh viên trong các buổi học lý thuyết và thực hành, kết quả làm các bài tập được giao, kết quả của các bài thi giữa học phần và bài thi kết thúc học phần. Thang điểm: Thang điểm chữ A, B, C, D, F. Điểm đánh giá học phần: Z = 0,3X + 0,7Y.
  6. 6 Bài giảng này là tài liệu chính thức và thống nhất của Bộ môn Hệ thống Thông tin, Khoa Công nghệ Thông tin và được dùng để giảng dạy cho sinh viên. Ngày phê duyệt: / / Trƣởng Bộ môn
  7. 7 CHƢƠNG I: TỔNG QUAN VỀ XỬ LÝ ẢNH SỐ 1.1. Xử lý ảnh số là gì? Xử lý ảnh là một lĩnh vực mang tính khoa học và công nghệ. Nó là một ngành khoa học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ phát triển của nó rất nhanh, kích thích các trung tâm nghiên cứu, ứng dụng, đặc biệt là máy tính chuyên dụng riêng cho nó. Xử lý ảnh được đưa vào giảng dạy ở bậc đại học ở nước ta khoảng chục năm nay. Nó là môn học liên quan đến nhiều lĩnh vực và cần nhiều kiến thức cơ sở khác. Đầu tiên phải kể đến Xử lý tín hiệu số là một môn học hết sức cơ bản cho xử lý tín hiệu chung, các khái niệm về tích chập, các biến đổi Fourier, biến đổi Laplace, các bộ lọc hữu hạn Thứ hai, các công cụ toán như Đại số tuyến tính, Sác xuất, thống kê. Một số kiến thứ cần thiết như Trí tuệ nhân tao, Mạng nơ ron nhân tạo cũng được đề cập trong quá trình phân tích và nhận dạng ảnh. 1.2. Nguồn gốc của xử lý ảnh số Ứng dụng đầu tiên được biết đến là nâng cao chất lượng ảnh báo được truyền qua cáp từ Luân đôn đến New York từ những năm 1920. Vấn đề nâng cao chất lượng ảnh có liên quan tới phân bố mức sáng và độ phân giải của ảnh. Việc nâng cao chất lượng ảnh được phát triển vào khoảng những năm 1955. Điều này có thể giải thích được vì sau thế chiến thứ hai, máy tính phát triển nhanh tạo điều kiện cho quá trình xử lý ảnh sô thuận lợi. Năm 1964, máy tính đã có khả năng xử lý và nâng cao chất lượng ảnh từ mặt trăng và vệ tinh Ranger 7 của Mỹ bao gồm: làm nổi đường biên, lưu ảnh. Từ năm 1964 đến nay, các phương tiện xử lý, nâng cao chất lượng, nhận dạng ảnh phát triển không ngừng. Các phương pháp tri thức nhân tạo như mạng nơ ron nhân tạo, các thuật toán xử lý hiện đại và cải tiến, các công cụ nén ảnh ngày càng được áp dụng rộng rãi và thu nhiều kết quả khả quan. 1.3. Các ứng dụng của xử lý ảnh số Biến đổi ảnh (Image Transform) Trong xử lý ảnh do số điểm ảnh lớn các tính toán nhiều (độ phức tạp tính toán cao) đòi hỏi dung lượng bộ nhớ lớn, thời gian tính toán lâu. Các phương pháp khoa học kinh điển áp dụng cho xử lý ảnh hầu hết khó khả thi. Người ta sử dụng các phép toán tương đương hoặc biến đổi sang miền xử lý khác để d tính toán. Sau khi xử lý d dàng hơn được thực hiện, dùng biến đổi ngược để đưa về miền xác định ban đầu, các biến đổi thường gặp trong xử lý ảnh gồm: - Biến đổi Fourier, Cosin, Sin - Biến đổi (mô tả) ảnh bằng tích chập, tích Kronecker (theo xử lý số tín hiệu [3]) - Các biến đổi khác như KL (Karhumen Loeve), Hadamard Một số các công cụ sác xuất thông kê cũng được sử dụng trong xử lý ảnh. Do khuôn khổ tài liệu hướng dẫn có hạn, sinh viên đọc thêm các tài liệu để nắm được các phương pháp biến đổi và một số phương pháp khác được nêu ở đây.
  8. 8 Nén ảnh Ảnh dù ở dạng nào vẫn chiếm không gian nhớ rất lớn. Khi mô tả ảnh người ta đã đưa kỹ thuật nén ảnh vào. Các giai đoạn nén ảnh có thể chia ra thế hệ 1, thế hệ 2. Hiện nay, các chuẩn MPEG được dùng với ảnh đang phát huy hiệu quả 1.4. Các bƣớc cơ bản trong xử lý ảnh số Các phương pháp xử lý ảnh bắt đầu từ các ứng dụng chính: nâng cao chất lượng ảnh và phân tích ảnh. Để d tưởng tượng, xét các bước cần thiết trong xử lý ảnh. Đầu tiên, ảnh tự nhiên từ thế giới ngoài được thu nhận qua các thiết bị thu (như Camera, máy chụp ảnh). Trước đây, ảnh thu qua Camera là các ảnh tương tự (loại Camera ống kiểu CCIR). Gần đây, với sự phát triển của công nghệ, ảnh màu hoặc đen trắng được lấy ra từ Camera, sau đó nó được chuyển trực tiếp thành ảnh số tạo thuận lợi cho xử lý tiếp theo. (Máy ảnh số hiện nay là một thí dụ gần gũi). Mặt khác, ảnh cũng có thể tiếp nhận từ vệ tinh; có thể quét từ ảnh chụp bằng máy quét ảnh. Hình 1.1 dưới đây mô tả các bước cơ bản trong xử lý ảnh. Sơ đồ này bao gồm các thành phần sau: a) Phần thu nhận ảnh (Image Acquisition) Ảnh có thể nhận qua camera màu hoặc đen trắng. Thường ảnh nhận qua camera là ảnh tương tự (loại camera ống chuẩn CCIR với tần số 1/25, mỗi ảnh 25 dòng), cũng có loại camera đã số hoá (như loại CCD – Change Coupled Device) là loại photodiot tạo cường độ sáng tại mỗi điểm ảnh. Camera thường dùng là loại quét dòng ; ảnh tạo ra có dạng hai chiều. Chất lượng một ảnh thu nhận được phụ thuộc vào thiết bị thu, vào môi trường (ánh sáng, phong cảnh) b) Tiền xử lý (Image Processing) Sau bộ thu nhận, ảnh có thể nhi u độ tương phản thấp nên cần đưa vào bộ tiền xử lý để nâng cao chất lượng. Chức năng chính của bộ tiền xử lý là lọc nhi u, nâng độ tương phản để làm ảnh r hơn, nét hơn. c) Phân đoạn (Segmentation) hay phân vùng ảnh Phân vùng ảnh là tách một ảnh đầu vào thành các vùng thành phần để 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
  9. 9 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ụ thuộc rất nhiều vào công đoạn này. d) Biểu diễn ảnh (Image Representation) Đầ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 election) 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. e) Nhận dạng và nội suy ảnh (Image Recognition and Interpretation) 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 họ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 loai ảnh 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 f) Cơ sở tri thức (Knowledge Base) Như đã nói ở trên, ả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. Trong tài liệu, chương 6 về nhận dạng ảnh có nêu một vài ví dụ về cách sử dụng các cơ sở tri thức đó. g) Mô tả (biểu diễn ảnh) Từ Hình 1.1, ả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 đặc điểm của ảnh được gọi là các đặc trưng ảnh
  10. 10 (Image Features) như: biên ảnh (Boundary), vùng ảnh (Region). Một số phương pháp biểu di n thường dùng: • Biểu di n bằng mã chạy (Run-Length Code) • Biểu di n bằng mã xích (Chaine -Code) • Biểu di n bằng mã tứ phân (Quad-Tree Code) 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. Một vùng ảnh R có thể mã hoá đơn giản nhờ một ma trận nhị phân: - U( , ) = 1 ếu (m, n) thuộc R - U( m, ) = 0 ếu (m, n) không thuộc R Trong đó: U(m, n) là hàm mô tả mức xám ảnh tại tọa độ (m, n). Với cách biểu di n trên, một vùng ảnh được mô tả bằng một tập các chuỗi số 0 hoặc 1. Giả sử chúng ta mô tả ảnh nhị phân của một vùng ảnh được thể hiện theo toạ độ (x, y) theo các chiều và đặc tả chỉ đối với giá trị “1” khi đó dạng mô tả có thể là: (x, y)r; trong đó (x, y) là toạ độ, r là số lượng các bit có giá trị “1” liên tục theo chiều ngang hoặc dọc. 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. Một đường bất kỳ được chia thành các đoạn nhỏ. Nối các điểm chia, ta có các đoạn thẳng kế tiếp được gán hướng cho đoạn thẳng đó tạo thành một dây xích gồm các đoạn. Các hướng có thể chọn 4, 8, 12, 24, mỗi hướng được mã hoá theo số thập phân hoặc số nhị phân thành mã của hướng. Biểu diễn bằng mã tứ phân Phương pháp mã tứ phân được dùng để mã hoá cho vùng ảnh. Vùng ảnh đầu tiên được chia làm bốn phần thường là bằng nhau. Nếu mỗi vùng đã đồng nhất (chứa toàn điểm đen (1) hay trắng (0)), thì gán cho vùng đó một mã và không chia tiếp. Các vùng không đồng nhất được chia tiếp làm bốn phần theo thủ tục trên cho đến khi tất cả các vùng đều đồng nhất. Các mã phân chia thành các vùng con tạo thành một cây phân chia các vùng đồng nhất. Trên đây là các thành phần cơ bản trong các khâu xử lý ảnh. Trong thực tế, các quá trình sử dụng ảnh số không nhất thiết phải qua hết các khâu đó tùy theo đặc điểm ứng dụng. Hình 1.2 cho sơ đồ phân tích và xử lý ảnh và lưu đồ thông tin giữa các khối một cách khá đầy đủ. Ảnh sau khi được số hóa được nén, lưu lại để truyền cho các hệ thống khác sử dụng hoặc để xử lý tiếp theo. Mặt khác, ảnh sau khi số hóa có thể bỏ qua công đoạn nâng cao chất lượng (khi ảnh đủ chất lượng theo một yêu cầu nào đó) để chuyển tới khâu phân đ ạn hoặc bỏ tiếp khâu hâ đ ạn chuyển trực tiếp tới khâu ích chọ đặc trưng. Hình 1.2 cũng chia các nhánh song song như: nâng cao chất lượng ảnh có hai nhánh phân biệt: nâng cao chất lượng ảnh (tăng độ sáng, độ tương phản, lọc nhi u) hoặc khôi phục ảnh (hồi phục lại ảnh thật khi ảnh nhận được bị méo) v.v
  11. 11 1.5. Các thành phần của một hệ thống xử lý ảnh Theo quan điểm của quy trình xử lý, chúng ta đã thể hiện các khối cơ bản trên Hình 1.1, các khối chi tiết và luồng thông tin trên Hình 1.2. Theo quan điểm của hệ th ng xử lý trên máy tính số, hệ thống gồm các đầu đo (thu nhận ảnh); bộ số hóa ; máy tính số; Bộ hiển thị; Bộ nhớ. Các thành phần này không nhắc lại ở đây (đọc thêm giáo trình cấu trúc máy tính). Một hệ thống xử lý ảnh cơ bản có thể gồm: máy tính cá nhân kèm theo vỉ mạch chuyểnđổi đồ hoạ VGA hoặc SVGA, đĩa chứa các ảnh dùng để kiểm tra các thuật toán và một màn hìnhcó hỗ trợ VGA hoặc SVGA. Nếu điều kiện cho phép, nên có một hệ thống như Hình 1.4. bao gồm một máy tính PC kèm theo thiết bị xử lý ảnh. Nối với cổng vào của thiết bị thu nhận ảnh là mộtvideo camera, và cổng ra nối với một màn hình. Thực tế, phần lớn các nghiên cứu của chúng tađược đưa ra trên ảnh mức xám (ảnh đen trắng). Bởi vậy, hệ thống sẽ bao gồm một thiết bị xử lýảnh đen trắng và một màn hình đen trắng. Ảnh mức xám được áp dụng trong nhiều lĩnh vực như sinh vật học hoặc trong công nghiệp. Thực tế chỉ ra rằng bất kỳ ứng dụng nào trên ảnh, mức xám cũng ứng dụng được trên ảnhmàu. Với lý do đó, hệ thống ban đầu nên chỉ bao gồm cấc thiết bị thu nhận và hiển thị ảnh đen trắng. Với ảnh
  12. 12 màu, nên sử dụng một hệ thống mới như Hình 1.3, trừ trường hợp bạn cần mộtcamera TV màu và một màn hình đa tần số (ví dụ như NEC MultiSync, Sony Multiscan, hoặc Mitsubishi Diamond Scan) để hiển thị ảnh màu. Nếu khả năng hạn chế, có thể dùng PC kèm theo vỉ mạch VGA và màn hình VGA, để dựng ảnh được. CÂU HỎI ÔN TẬP 1. Trình bày các thành phần và lưu đồ thông tin giữa các khối trong quá trình xử lý ảnh. 2. Nêu khái niệm và định nghĩa điểm ảnh. 3. Thế nào là độ phân giải ảnh, cho ví dụ? 4. Trình bày định nghĩa mức xám, cho ví dụ. 5. Nêu quan hệ giữa các điểm ảnh. 6. Trình bày về khoảng cách đo và phân loại khoảng cách giữa các điểm ảnh. 7. Nêu ý nghĩa của các phép biến đổi ảnh, liệt kê một số phép biến đổi và cho ví dụ.
  13. 13 CHƢƠNG II: CÁC KIẾN THỨC CƠ BẢN VỀ ẢNH SỐ 2.1. Cảm nhận thị giác Thị giác máy tính là ảnh máy tính trong đó việc ứng dụng không dành cho thị giác người. Một trong những chủ đề chính trong lĩnh vực thị giác máy tính đó là phân tích ảnh. Phân tích ảnh bao hàm việc xem xét dữ liệu ảnh để giải quyết d dàng một bài toán thị giác. Quá trình phân tích ảnh bao hàm hai vấn đề khác: trích chọn đặc trưng và phân lớp mẫu. Trích chọn đặc trưng là quá trình xử lí thông tin ảnh thu được ở mức cao như là thông tin về độ nhọn hay màu, Phân lớp mẫu là hoạt động lấy thông tin ở mức cao này và từ đó xác định các đối tượng nằm trong ảnh. Có nhiều ứng dụng của thị giác máy tính như: Trong các hệ thống sản xuất, thị giác máy tính thường được sử dụng trong việc điều khiển chất lượng. Trong nhiều lĩnh vực khác nhau trong cộng đồng y tế, mà ở đó chắc chắn các kiểu ứng dụng sẽ tiếp tục được phát triển. Các ví dụ hiện nay về các hệ thống y tế đang được phát triển bao gồm: các hệ thống chẩn đoán các khối u da tự động, các hệ thống trợ giúp giải phẩu thần kinh khi phẫu thuật não bộ, và các hệ thống test bệnh án tự động. Lĩnh vực an ninh và pháp luật cũng là một lĩnh vực hứa hẹn cho việc phát triển các hệ thống thị giác máy tính, với các ứng dụng từ nhận dạng tự động vân tay cho đến phân tích DNA. Các hệ thống an ninh nhận dạng người thông qua việc scan v ng mạc mắt, scan khuôn mặt, và các đường tĩnh mạch ở tay đã được phát triển. Chương trình không gian U.S. và BQP, với việc phát triển các khả năng thị giác cho rô bốt đang được nghiên cứu và phát triển. Các ứng dụng từ xe cộ tự chủ cho đến bắt bám mục tiêu và nhận dạng. Các vệ tinh theo quĩ đạo trái đất thu thập những dung lượng lớn dữ liệu ảnh hàng ngày, và các ảnh này sẽ tự động được scan để hỗ trợ việc lập bản đồ, dự báo thời tiết, và giúp chúng ta hiểu được những thay đổi đang xảy trên hành tinh chúng ta. 2.2. Lấy mẫu và lƣợng tử hóa ảnh Giới thiệu Một ảnh g(x, y) ghi được từ Camera là ảnh liên tục tạo nên mặt phẳng hai chiều. Ảnh cần chuyển sang dạng thích hợp để xử lí bằng máy tính. Phương pháp biến đổi một ảnh (hay một hàm)liên tục trong không gian cũng như theo giá trị thành dạng số rời rạc được gọi là số hoá ảnh. Việcbiến đổi này có thể gồm hai bước: Bước 1: Đo giá trị trên các khoảng không gian gọi là lấy mẫu Bước 2: Ánh xạ cường độ (hoặc giá trị) đo được thành một số hữu hạn các mức rời rạc gọilà lượng tử hoá.
  14. 14 Lấy mẫu Lấy mẫu là một quá trình, qua đó ảnh được tạo nên trên một vùng có tính liên tục được chuyển thành các giá trị rời rạc theo tọa độ nguyên. Quá trình này gồm 2 lựa chọn: - Một là: khoảng lấy mẫu. - Hai là: cách thể hiện dạng mẫu. Lựa chọn thứ nhất được đảm bảo nhờ lý thuyết lấy mẫu của Shannon. Lựa chọn thứ hai liên quan đến độ đo (Metric) được dùng trong miền rời rạc. Khoảng lấy mẫu (Sampling Interval) Ảnh lấy mẫu có thể được mô tả như việc lựa chọn một tập các vị trí lấy mẫu trong không gian hai chiều liên tục. Đầu tiên mô tả qua quá trình lấy mẫu một chiều với việc sử dụng hàm delta: Tiếp theo chúng ta định nghĩa hàm răng lược với các khoảng Δx như sau: với r là số nguyên, Δx : khoảng lấy mẫu Như vậy, hàm răng lược là chuỗi các xung răng lược từ (-∞ đến +∞). Giả sử hàm một chiều g(x) được mô tả (gần đúng) bằng g(r Δx ) tức là: Khi đó tín hiệu lấy mẫu được mô hình hoá hoặc tương đương Trong thực tế, r không thể tính được trong khoảng vô hạn (từ − ∞ đến + ∞ ) mà là một số lượng NΔx mẫu lớn cụ thể. Như vậy, để đơn giản có thể nói hàm liên tục g(x) có thể biểu di ntrên một miền với độ dài NΔx mẫu thành chuỗi như sau: Chú ý 1: Khoảng lấy mẫu (Sampling Interval) Δx là một tham số cần phải được chọn đủ nhỏ, thích hợp, nếu không tín hiệu thật không thể khôi phục lại được từ tín hiệu lấy mẫu.
  15. 15 Chú ý 2: Từ lý thuyết về xử lý tín hiệu số [5], (2-6) là tích chập trong miền không gian x. Mặt khác (2-6) tương đương với tích chập trong miền tần số ω tức là biến đổi Fourier của gs(x) là Gs(ωs). trong đó ωx là giá trị tần số ứng với giái trị x trong miền không gian. Điều kiện khôi phục ảnh lấy mẫu về ảnh thật được phát biểu từ định lý lẫy mẫu của Shannon. Lƣợng tử hóa Lượng tử hoá là một quá trình lượng hoá tín hiệu thật dùng chung cho các loại xử lý tín hiệu trên cơ sở máy tính. Vấn đề này đã được nghiên cứu kỹ lưỡng và có nhiều lời giải lý thuyết dưới nhiều giả định của các nhà nghiên cứu như Panter và Dite (1951), Max (1960), Panter (1965). Các giá trị lấy mẫu Z là một tập các số thực từ giá trị Zmin đến lớn nhất Zmax. Mỗi một số trong các giá trị mẫu Z cần phải biến đổi thành một tập hữu hạn số bit để máy tính lưu trữ hoặc xử lý. Định nghĩa: Lượng tử hoá là ánh xạ từ các số thực mô tả giá trị lấy mẫu thành một giải hữu hạn các số thực. Nói cách khác, đó là quá trình số hoá biên độ. Giả sử Z là một giá trị lấy mẫu (số thực) tại vị trí nào đó của mặt phẳng ảnh, và Z i <=Z’<=Z a và giả sử chúng ta muốn lượng hoá giá trị đó thành một trong các mức rời rạc: 1, 2, tương ứng với Z i đến Zmax (Hình 2.3). Khi đó, quá trình lượng hoá có thể thực hiện bằng cách chia toàn bộ miền vào (Zmax - Zmin) thành L khoảng, mỗi khoảng là Δl và khoảng thứ I được đặt tại điểm giữa các khoảng liền kề li. họ các giá trị z được thực hiện và mô tả bằng li theo quá trình trên đây, khi đó sai số của quá trình lấy mẫu có thể được xác định theo : 2.3. Mối 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)
  16. 16 trong đó: số 1 là giá trị logic; N4(p) tập 4 điểm lân cận của p. - 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 la 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 : 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. +. q huộc N4( ) h ặc +. q huộc NP(p) c) Đo khoảng cách giữa các điểm ảnh. Định nghĩa: 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( ,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( ,z) ≤ D( ,q) + D(q,z); z à ộ đ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:
  17. 17 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ị (City- Block Distance) 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. Ví dụ: Màn hình CGA 12” (12”*2,54cm = 30,48cm=304,8mm) độ phân giải 320*200; tỷ lệ 4/3 (Chiều dài/Chiều rộng). Theo định lý Pitago về tam giác vuông, đường chéo sẽ lấy tỷ lệ 5 phần (5/4/3: đường chéo/chiều dài/chiều rộng màn hình); khi đó độ dài thật là (305/244/183) chiều rộng màn hình 183mm ứng với màn hình CGA 200 điểm ảnh theo chiều dọc. Như vậy, khoảng cách điểm ảnh lân cận của CGA 12” là ≈ 1mm. Khoảng cách D8(p, q) còn gọi là khoảng cách bàn cờ (Chess-Board Distance) giữa điểm ảnh p, q được xác định như sau: D8(p,q) = max (| x-s | , | y-t |) CÂU HỎI ÔN TẬP 1. Tại sao phải số hóa ảnh? Trình bày cách biểu di n ảnh số trên máy tính? 2. Lấy mẫu là gì? Lượng tử là gì? Khoảng lấy mẫu là gì? Cho ví dụ minh họa? 3. Trình bày các mối quan hệ giữa các điểm ảnh?
  18. 18 CHƢƠNG III: NÂNG CAO CHẤT LƢỢNG ẢNH TRONG MIỀN KHÔNG GIAN 3.1. Các phép biến đổi mức xám cơ bản Nâng cao chất lượng là bước cần thiết trong xử lý ảnh nhằm hoàn thiện một số đặc tính của ảnh. Nâng cao chất lượng ảnh gồm hai công đoạn khác nhau: tăng cường ảnh và khôi phục ảnh. Tăng cường ảnh nhằm hoàn thiện các đặc tính của ảnh như : - Lọc nhi u, hay làm trơn ảnh, - Tăng độ tương phản, điều chỉnh mức xám của ảnh, - Làm nổi biên ảnh. Các thuật toán triển khai việc nâng cao chất lượng ảnh hầu hết dựa trên các kỹ thuật trong miền điểm, không gian và tần số. Toán tử điểm là phép biến đổi đối với từng điểm ảnh đang xét, không liên quan đến các điểm lân cận khác, trong khi đó, toán tử không gian sử dụng các điểm lân cận để quy chiếu tới điểm ảnh đang xét. Một số phép biến đổi có tính toán phức tạp được chuyển sang miền tần số để thực hiện, kết quả cuối cùng được chuyển trở lại miền không gian nhờ các biến đổi ngược. Khái niệm về toán tử điểm: Xử lý điểm ảnh thực chất là biến đổi giá trị một điểm ảnh dựa vào giá trị của chính nó mà không hề dựa vào các điểm ảnh khác. Có hai cách tiệm cận với phương pháp này. Cách thứ nhất dùng một hàm biến đổi thích hợp với mục đích hoặc yêu cầu đặt ra để biến đổi giá trị mức xám của điểm ảnh sang một giá trị mức xám khác. Cách thứ hai là dùng lược đồ mức xám (Gray Histogram). Về mặt toán học, toán tử điểm là một ánh xạ từ giá trị cường độ ánh sáng u(m, n) tại toạ độ (m, n) sang giá tri cường độ ánh sáng khác v(m, n) thông qua hàm f(.), tức là: Nói một cách khác, toán tử điểm là toán tử không bộ nhớ, ở đó một mức xác u ∈ [ 0 , N ] được ánh xạ sang một mức xám v ∈ [ 0 , N ] : v = f ( u ) . Ứng dụng chính của các toán tử điểm là biến đổi độ tương phản của ảnh. Ánh xạ f khác nhau tùy theo các ứng dụng. Các dạng toán tử điểm được giới thiệu cụ thể như sau: Tăng độ tương phản Các cấp độ α ,β ,γ xác định độ tương phản tương đối. L là số mức xám cực đại Tách nhiễu và phân ngưỡng
  19. 19 Trong đó a = b =t gọi là phân ngưỡng. Biến đổi âm bản. Cắt theo mức Trích chọn bit. 3.2. Xử lý histogram a) Lý thuyết Lược đồ mức xám của một ảnh, từ nay về sau ta qui ước gọi là lược đồ xám, là một hàm cung cấp tần suất xuất hiện của mỗi mức xám (grey level). Lược đồ xám được biểu di n trong một hệ toạ độ vuông góc x,y. Trong hệ toạ độ này, trục hoành biểu di n số mức xám từ 0 đến N, N là số mức xám (256 mức trong trường hợp chúng ta xét). Trục tung biểu di n số điểm ảnh cho một mức xám (số điểm ảnh có cùng mức xám). Cũng có thể biểu di n khác một chút: trục tung là tỷ lệ số điểm ảnh có cùng mức xám trên tổng số điểm ảnh. Số điểm ảnh Số điểm ảnh Mức xám Mức xám a) ảnh đậm b) ảnh nhạt Lược đồ xám cung cấp rất nhiều thông tin về phân bố mức xám của ảnh. Theo thuật ngữ của xử lý ảnh gọi là tính động của ảnh. Tính động của ảnh cho phép phân tích trong khoảng nào đó phân bố phần lớn các mức xám của ảnh: ảnh rất sáng hay ảnh rất đậm. Nếu ảnh sáng, lược đồ xám nằm bên phải (mức xám cao), còn ảnh đậm luợc đồ xám nằm bên trái(mức xám thấp). Theo định nghĩa của lược đồ xám, việc xây dựng nó là khá đơn giản. Thuật toán xây dựng lược đồ xám có thể mô tả như sau:
  20. 20 Bắt đầu H là bảng chứa lược đồ xám (là vec tơ có N phần tử) a. Khởi tạo bảng Đặt tất cả các phần tử của bảng là 0 b. Tạo bảng Với mỗi điểm ảnh I(x,y) tính H[I(x,y)] = H[I(x,y)] + 1 c. Tính giá trị Max của bảng H. Sau đó hiện bảng trong khoảng từ 0 đến Max. Kết thúc Lược đồ xám là một công cụ hữu hiệu dùng trong nhiều công đoạn của xử lý ảnh như tăng cường ảnh ( xem chương Bốn). Dưới đây ta xem xét một số biến đổi lược đồ xám hay dùng. b) Biến đổi lƣợc đồ mức xám Trong tăng cường ảnh, cỏc thao tỏc chủ yếu dựa vào ph n tớch lược đồ xỏm. Trước tiờn ta xột bảng tra LUT(Look Up Table). Bảng tra LUT là một bảng chứa biến đổi một mức xỏm i sang mức xỏm j như đó núi trong phần a. Một cách toán học, LUT được định nghĩa như sau: - Cho GI là tập các mức xám ban đầu GI = {0, 1, , NI} - Cho GF là tập các mức xám kết quả GF = {0, 1, , NF} để cho tiện ta cho NI = NF = 255. - f là ánh xạ từ GI vào GF: gi Gi sẽ  gf GF mà gf = f(gi) Với mỗi giá trị của mức xám ban đầu ứng với một giá trị kết quả. Việc chuyển đổi một mức xám ban đầu về một mức xám kết quả tương ứng có thể d dàng thực hiện được nhờ một bảng tra. Khi đã xây dựng được bảng, việc sử dụng bảng là khá đơn giản. Người ta xem xét mức xám của mỗi điểm ảnh, nhờ bảng tra tính được mức xám kết quả. Gọi là bảng tra. 3.3. Nâng cao chất lƣợng ảnh sử dụng các toán tử số học/logic Có hai nhóm thao tác đại số áp dụng lên ảnh là: số học và logic. Các thao tác số học có: cộng, trừ, chia, và nhân còn các thao tác logic gồm: AND, OR, và NOT. Các thao tác này được thực hiện trên hai ảnh ngoại trừ thao tác NOT chỉ cần một ảnh, và được thực hiện trên cơ sở pixel-pixel. Để áp dụng các thao tác số học lên 2 ảnh, ta thao tác theo các pixel tương ứng. Chẳng hạn, để cộng hai ảnh I1 và I2 tao ra ảnh I3 ta có I (r,c) I (r,c) I (r,c) 1 2 3 3 4 7 6 6 6 3 6 4 6 7 6 9 10 13 I 3 4 5 ;I 4 2 6 ;I 3 4 4 2 5 6 7 6 11 1 2 3 2 4 6 3 5 5 2 3 4 5 6 5 5 9 11 Phép cộng được sử dụng để kết hợp thông tin trong hai ảnh. Các ứng dụng nó gồm phát triển các thuật toán khôi phục ảnh để mô hình hoá nhi u cộng, và tạo các hiệu ứng đặc biệt như là
  21. 21 morphing ảnh trong các ảnh chuyển động (Hình 2.2-5). Chú ý rằng phép morphing ảnh đúng có thể đòi hỏi sử dụng đến các phép biến đổi hình học (xem phần 3.5), để sắp thẳng hai ảnh. Morphing ảnh cũng được sử dụng trong thao tác dựa trên thời gian, do đó một dung lượng cân xứng tăng lên trong ảnh thứ hai thường được sử dụng để cộng vào trong ảnh thứ nhất khi quá thời gian. Hình 2.2-5. Cộng ảnh Trừ hai ảnh thường được sử dụng để phát hiện chuyển động. Xét trường hợp khi không có gì thay đổi trong một cảnh cả; ảnh kết quả từ việc trừ hai ảnh thu nhận được liên tiếp sẽ là một ảnh màu đen toàn 0. Nếu có cái gì đó chuyển động trong cảnh, thì phép trừ ảnh sẽ tạo ra các giá trị khác 0 tại các vị trí có chuyển động. Hình 2.2-6 minh hoạ việc sử dụng phép trừ ảnh để phát hiện chuyển động.
  22. 22 Hình 2.2-6. Trừ ảnh Việc nhân và chia ảnh được sử dụng để điều chỉnh về cường độ sáng của ảnh. Một ảnh thông thường chứa một số không đổi lớn hơn 1. Việc nhân và chia ảnh thường được sử dụng để điều chỉnh độ sáng của ảnh. Một ảnh thông thường chứa các số không đổi lớn hơn 1. Việc nhân các giá trị pixel với số lớn hơn 1 thì làm cho ảnh sáng lên, còn chia cho số lớn hơn 1 thì làm tối ảnh đi. Điều chỉnh độ sáng thường được sử dụng như là một bước tiền xử lý trong nâng cao ảnh và được thể hiện như trong hình 2.2-7.
  23. 23 Hình 2.2-7. Nhân và chia ảnh Các thao tác logic AND, OR, và NOT tạo nên một tập hoàn chỉnh, nghĩa là các thao tác logic khác (XOR, NOR, NAND) đều có thể sinh ra được bằng cách tổ hợp các thao tác cơ sở trên. Chúng thao tác dưới dạng bit-wise trên dữ liệu pixel. Các thao tác logic AND và OR được sử dụng để tổ hợp thông tin trong hai ảnh. Việc này có thể thực hiện cho các hiệu ứng cụ thể, nhưng một ứng dụng có ý nghĩa hơn cho phân tích ảnh là thực hiện một toán tử mặt nạ. Sử dụng AND và OR làm phương pháp đơn giản để trích chọn ROI từ một ảnh, nếu các phương pháp đồ hoạ phức tạp hơn không sẳn có. Chẳng hạn, một mặt nạ hình vuông màu trắng (toàn 1) dùng cho phép AND với một ảnh sẽ chỉ cho phần ảnh mà trùng với hình vuông này xuất hiện ở ảnh đầu ra với nền phần còn lại đen, một mặt nạ hình vuông màu đen (toàn 0) dùng cho phép OR với một ảnh sẽ chỉ cho phần ảnh mà trùng với hình vuông này xuất hiện ở ảnh đầu ra với nền phần còn lại trắng. Quá trình này được gọi là masking ảnh, và hình2.2-8 minh hoạ các kết quả của các thao tác này.
  24. 24 Toán tử NOT tạo ra đối của ảnh gốc, bằng cách nghịch đảo mỗi bit trong giá trị pixel, và được thể hiện trên hình 2.2-9. Hình 2.2-9. Ảnh bù 3.4. Bộ lọc trong miền không gian Lọc không gian thông thường được thực hiện để khử nhi u hoặc thực hiện một số kiểu nâng cao ảnh. Các thao tác này được gọi là lọc không gian để phân biệt chúng với lọc tần số, sẽ được trình bày trong phần 2.5. Có ba kiểu lọc được trình bày ở đây là: - Lọc trung bình. - Lọc trung vị. - Lọc nâng cao.
  25. 25 Hai kiểu lọc đầu tiên chủ yếu được sử dụng để che đậy hoặc khử nhi u, mặc dù chúng cũng có thể được sử dụng cho các ứng dụng cụ thể khác. Chẳng hạn, một bộ lọc trung bình làm cho ảnh "mịn hơn" như hình 2.2-10. Các bộ lọc nâng cao thường để làm sáng các cạnh và các chi tiết nằm trong ảnh. Hình 2.2-10. Lọc trung bình Nhiều bộ lọc không gian được thực hiện thông qua phép cuộn. Bởi vì thao tác mặt nạ cuộn cung cấp kết quả là tổng trọng số của các giá trị của một pixel và các láng giềng của nó, nên được gọi là là một bộ lọc tuyến tính. Một khía cạnh thú vị của các mặt nạ cuộn là hiệu ứng tổng thể có thể dự đoán được dựa trên mẫu của chúng. Chẳng hạn, nếu các hệ số của mặt nạ có tổng bằng 1, thì độ sáng trung bình của ảnh sẽ được giữ nguyên. Nếu tổng các hệ số bằng 0, thì độ sáng trung bình sẽ mất đi và trả về một ảnh tối. Hơn nữa, nếu các hệ số có cả âm và dương, thì mặt nạ là một bộ lọc trả về chỉ thông tin cạnh, còn nếu các hệ số đều dương, thì nó là một bộ lọc làm mờ (blur) ảnh the image. Lọc trung bình: Các bộ lọc trung bình thao tác trên các nhóm pixel địa phương được gọi là vùng láng giềng và thay thế pixel trung tâm bởi trung bình của các pixel trong cùng láng giềng đó. Việc thay thế này được thực hiện bằng một mặt nạ cuộn chẳng hạn như mặt nạ 3x3 sau đây: 1/ 9 1/ 9 1/ 9 1/ 9 1/ 9 1/ 9 1/ 9 1/ 9 1/ 9 Chú ý rằng các hệ số trong mặt nạ này có tổng bằng 1, nên độ sáng ảnh giữ nguyên, và các hệ số đều dương nên nó có khuynh hướng làm nhoè ảnh. Cũng có các bộ lọc trung bình khác phức tạp hơn được thiết kế dùng cho các kiểu nhi u cụ thể. Chúng sẽ được trình bày trong chương 3. Lọc trung vị: Lọc trung vị là lọc phi tuyến. Một phép lọc phi tuyến là một kết quả không thể thu được từ một tổng trọng số của các pixel láng giềng, như đã thực hiện với mặt nạ cuộn. Tuy nhiên lọc trung vị cũng thực hiện trên cùng một vùng láng giềng địa phương. Sau khi đã định nghĩa kích thước
  26. 26 vùng láng giềng, pixel trung tâm được thay bằng trung vị tức là giá trị chính giữa của tất cả các giá trị láng giềng. VÍ DỤ Cho trước một cùng láng giềng 3x3: 5 3 3 5 4 4 6 5 255 Trước hết ta sắp xếp các giá trị này từ bé đến lớn (3,3,4,4,5,5,5,6, 7) và chọn giá trị chính giữa, trường hợp này là 5. Giá trị 5 này tiếp đó được đặt vào vị trí trung tâm. Một bộ lọc trung vị có thể sử dụng một vùng láng giềng có kích thước bất kì, nhưng phổ biến là các kích thước 3x3, 5x5 và 7x7. Chú ý rằng ảnh đầu ra phải được ghi vào một ảnh riêng (bộ đệm). Hình 2.2-11 minh hoạ việc sử dụng bộ lọc trung vị để khử nhi u. Hình 2.2-11. Lọc trung vị Bộ lọc nâng cao: Các bộ lọc nâng cao được xét ở đây có các bộ lọc kiểu laplacian-type và lọc sai phân (difference filter). Các kiểu bộ lọc này có khuynh hướng để đưa ra, hoặc nâng cao các chi tiết trong ảnh. Hai mặt nạ cuộn sử dụng cho các bộ lọc kiểu laplacian là 0 -1 0 1 - 2 1 1 5 -1 2 5 - 2 0 1 0 1 2 1 Các bộ lọc kiểu laplacian sẽ nâng cao được các chi tiết đều theo mọi hướng. Còn các bộ lọc sai phân sẽ nâng cao các chi tiết theo hướng xác định theo mặt nạ đã chọn. Có 4 mặt nạ cuộn lọc sai phân, tương ứng với theo các hướng dọc, ngang và hướng theo hai đường chéo: 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 -1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 -1 -1 0 0
  27. 27 Các kết quả của việc áp dụng các bộ lọc này được thể hiện trên hình 2.2-12. Hình 2.2-12. Các bộ lọc nâng cao 3.5. Các bộ lọc làm mƣợt ảnh trong miền không gian 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 bị, giả trung vị, lọc ngoài (Outlier).
  28. 28 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: Nếu trong kỹ thuật lọc trên, ta dùng các trọng số như nhau, phương trình trên sẽ trở thành: với : y(m, n): ảnh đầu vào, v(m, n): ảnh đầu ra, a(k, l) : là cửa sổ lọc. 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: 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ử đầu vào biểu di n bởi ma trận I: Ảnh số thu được bởi lọc trung bình Y=H⊗ I có dạng:
  29. 29 Một bộ lọc trung bình không gian khác cũng hay được sử dụng. Phương trình của bộ lọc đó có dạng: Ở đây, nhân chập H có kích thuớc 2x2 và mỗi điểm ảnh kết quả có giá trị bằng trung bình cộng của nó với trung bình cộng của 4 lân cận gần nhất. 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.Về nguyên lý của bộ lọc thông thấp giống như đã trình bày trên. Trong kỹ thuật này người ta hay dùng một số nhân chập có dạng sau: Ta d dàng nhận thấy khi b =1, Hb chính là nhân chập Ht1 (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 lại phương trình thu nhận ảnh dưới dạng: Trong đó η[ , ] là nhi u cộng có phương sai σ2 . Như vậy, theo cách tính của lọc trung bình ta có: Như vậy, nhi u cộng trong ảnh đã giảm đi Nw lần. c. Lọc đồng hình 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 một hệ số nhi u. Gọi X (m, n) là ảnh thu được, X(m, n) là ảnh gốc và η( , ) là nhi u, như vậy: 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: 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ũ.
  30. 30 3.6. Các bộ lọc làm sắc nét ảnh trong miền không gian Mục đích chính của lọc nét là làm sắc nét các chi tiết nổi bật trong ảnh hoặc làm nổi chi tiết bị nhòe. Làm nét ảnh được dùng trong những ứng dụng như in ấn điện tử, y học, máy kiểm tra sản phẩm trong công nghiệp, phát hiện mục tiêu quân sự. Cơ sở của lọc thông cao không gian Hình dạng của đáp ứng xung được sử dụng trong lọc thông cao (làm nét ảnh) không gian chỉ ra rằng lọc này cần có các hệ số gần tâm dương và các hệ số ngoại vi âm. Với mặt nạ 3 x 3 ta có thể sử dụng hệ số dương ở tâm, còn các hệ số khác âm. Chẳng hạn xét mặt nạ Laplace làm nét ảnh: Chú ý rằng tổng các hệ số bằng 0. Do đó khi mặt nạ di chuyển trên vùng có mức xám hằng hay thay đổi chậm, thì giá trị xuất ra sẽ bằng không hoặc rất nhỏ. Kết quả này phù hợp với lọc tương ứng miền tần số. Hơn nữa lọc này loại bỏ các thành phần có tần số thấp, do đó đưa đến giá trị trung bình của các mức xám tiến về không và vì vậy giảm độ tương phản tổng thể trong ảnh. Việc giá trị trung bình giảm về không khiến cho ảnh có một vài giá trị xám âm. Vì chúng ta chỉ xét các mức xám dương, nên kết quả của lọc thông cao cần được co giản hoặc cắt bỏ để kết quả cuối cùng thuộc khoảng [0,L-1]. Chú ý rằng việc lấy giá trị tuyệt dối của ảnh được lọc thông cao không phải là giải pháp tốt vì các giá trị có mức xám âm lớn sẽ xuất hiện sáng lên trong ảnh. 3.6.1. Lọc có khuếch đại tần số cao. Một ảnh lọc thông cao không gian có thể xem như là hiệu giưa ảnh gốc và ảnh qua lọc thông thấp, tức là: g(x,y) := f(x,y) – fsm(x,y), trong đó fsm(x,y) là ảnh được làm trơn của f(x,y) qua lọc thông thấp. D dàng kiểm tra ảnh ra g(x,y) nhận được bằng cách tính đáp ứng của ảnh f(x,y) với mặt nạ Laplace trên. Bằng cách nhân ảnh gốc với hệ số khuếch đại A, ta có cải biên là lọc co khuếch đại tần số cao: G(x,y) := Af(x,y) – lọc thông thấp = (A-1)f(x,y) + lọc thông cao. Nói cách khác, ảnh g(x,y) nhận được từ f(x,y) bằng cách tính đáp ứng tại mọi điểm với mặt nạ
  31. 31 Trong đó w=9A-1. Với A=1 ta có kết quả lọc thông cao tiêu chuẩn. Với A>1 ta có phần của ảnh gốc được cộng thêm kết quả của lọc thông cao mà phục hồi các thành phần lọc thông thấp bị mất trong phép toán lọc thông cao. Kết quả cuối cùng ta có một ảnh gần với ảnh gốc, với cấp độ làm nổi đường biên tương đối tùy theo hệ số khuếch đại A. Nói chung việc trừ một ảnh bị nhòe từ ảnh gốc gọi là mặt nạ không nét. Đây là một trong những phương pháp cơ bản được sử dụng trong công nghệ in ấn và xuất bản. Tương tự như lọc thông thấp, trong lọc thông cao ta có thể sử dụng các mặt nạ với kích thước lớn hơn. Chẳng hạn, mặt nạ 7x7 có giá trị tại tâm bằng 48, còn các giá trị khác bằng -1 và các hệ số được chuẩn hóa với hệ số bằng 1/49. Tuy nhiên, trong thực thế các mặt nạ kích thước lớn hơn 3x3 hiếm khi sử dụng. CÂU HỎI ÔN TẬP 1. Trình bày về bộ lọc trong miền không gian (spatial filtering), lọc tuyến tính (linear Filtering) và cách xử lý bộ lọc trong miền không gian (Spatial Filtering Process). 2. Khái niệm về mặt nạ? Cách sử dụng mặt nạ trong xử lý ảnh? 3. Làm sắc nét một vùng ảnh. 4. Làm mượt một vùng ảnh cho trước. 5. Trình bày về bộ lọc Median Filters.
  32. 32 CHƢƠNG IV: NÂNG CAO CHẤT LƢỢNG ẢNH TRONG MIỀN TẦN SỐ 4.1. Phép biến đổi Fourier và miền tần số Biến đổi Fourrier cho một tín hiệu có thể hình dung như sau: x(t) TF X(f) Miền thời gian Miền tần số Biến đổi Fourrier cho một tín hiệu một chiều gồm một cặp biến đổi: - Biến đổi thuận: chuyển sự biểu di n từ không gian thực sang không gian tần số (phổ và pha). Các thành phần tần số này được gọi là các biểu di n trong không gian Fourrier của tín hiệu. - Biến đổi ngược: chuyển đổi sự biểu di n của đối tượng từ không gian Fourrier sang không gian thực. a) Không gian một chiều Cho một hàm f(x) liên tục. Biến đổi Fourrier của f(x), kí hiệu F(u), u biểu di n tần số không gian, được định nghĩa: F u f() x e 2 ixu dx () trong đó: f(x): biểu di n biên độ tín hiệu e-2 ixu : biểu di n pha. Biến đổi ngược của F(u) cho f(x) được định nghĩa: f x F() u e2 ixu du () b) Không gian hai chiều Cho f(x,y) hàm biểu di n ảnh liên tục trong không gian 2 chiều, cặp biến đổi Fourier cho f(x,y) được định nghĩa: Fuv ,(,) fxye 2 i ( xu yv ) dxdy - Biến đổi thuận () u,v biểu di n tần số không gian. fxy ,(,) Fuve2 i ( xu yv ) dudv - Biến đổi ngược () 4.1.1. Biến đổi Fourrier rời rạc - DFT
  33. 33 Biến đổi DFT được phát triển dựa trên biến đổi Fourrier cho ảnh số. ở đây, ta dùng tổng thay cho tích phân. Biến đổi DFT tính các giá trị của biến đổi Fourrier cho một tập các giá trị trong không gian tần số được cách đều. a) DFT cho tín hiệu một chiều Khai triển Fourrier rời rạc DFT cho một dãy {u(n), n = 0, 1, , N-1} định nghĩa bởi: N 1 kn. v k  u() n WN n 0 với k =0, 1, , N-1 () với WN = e-j2 /N N 1 1 kn. u n  v( k ). WN và biến đổi ngược N k 0 WN-kn , k=0, 1, , N-1 () Thực tế trong xử lý ảnh người ta hay dùng DFT đơn vị: N 1 1 kn. v k  u( n ). WN N n 0 , k=0, 1, , N-1 () N 1 1 kn. u n  v( k ). WN N k 0 , k=0, 1, , N-1 () b) DFT cho tín hiệu hai chiều (ảnh số) DFT hai chiều của một ảnh M x N : {u(m,n) } là một biến đổi tách được và được định nghĩa: NN 11 km l. n v k, l  u ( m , n ). WNN . W mn 00 0 ≤ l, k ≤ N-1 () và biến đổi ngược: NN 11 1 k m l n u m, n 2  v ( k , l ) . WNN . W N kl 00 0 ≤ m, n ≤ N-1 () Cặp DFT đơn vị hai chiều được định nghĩa: NN 11 1 k m l n v k, l  u ( m , n ). WNN . W N mn 00 0 ≤ l, k ≤ N-1 () NN 11 1 k m l n u m, n  v ( k , l ). WNN . W N kl 00 0 ≤ m, n ≤ N-1 () Viết lại công thức 3.27 và 3.28, ta có: NN 11 1 k m l n v k, l  u ( m , n ). WN N mn 00 0 ≤ l, k ≤ N-1 () NN 11 1 k m l n u m, n  v ( k , l ). WN N kl 00 0 ≤ m, n ≤ N-1 () ở đây, WN(km+ln) là ma trận ảnh cơ sở.
  34. 34 Với ej = cos( ) +jsin( ) (công thức Ơle). Do vậy: j2 km ln 2 km ln 2 km ln km ln N WN e cos j sin NN . Như vậy, các hàm cơ sở trong ma trận ảnh cơ sở của biến đổi Fourier là các hàm cosine và hàm sine. Theo tính toán trên, ta thấy biến đổi Fourrier biểu di n ảnh trong không gian mới theo các hàm sine và cosine. 4.1.2. Một số tính chất và áp dụng a) Tính chất - Đối xứng và đơn vị FT = F, F-1 = F* - Chu kỳ v(k + N, l + N) = v(k,l)  k, l () u(k + N, l + N) = u(k,l)  k, l () - Phổ Fourier mẫu hoá U m, n 0 m , n N 1 U m, n 0 if not 22kl U,,, DFT u m n v k l  U , khi đó: NN với 12 là biến đổi Fourier của u(m,n). - Biến đổi nhanh: Vì DFT hai chiều là tách được, do đó biến đổi V = FUF tương đương với DFT đơn vị 1 chiều 2N. - Liên hiệp đối xứng: DFT và DFT đơn vị của một ảnh thực có tính đối xứng liên hợp: NNNN * v k,, l v k l 2 2 2 2 víi 0 l N/2-1 () v k,, l v* N k N l hay víi 0 k,l N/2-1 () b)Thuật toán biến đổi nhanh -FFT(Fast Fourrier Transform) - Trường hợp 1 chiều N 1 1 kn. v k  u n . WN Từ công thức N n 0 với k=0, 1, ,N-1, ta nhận thấy: Nhận xét: + Với mỗi giá trị k ta cần N phép nhân và N phép cộng. + Để tính N giá trị của v(k) ta cần N2 phép nhân.
  35. 35 Để tính toán một cách hiệu quả , người ta dùng thuật toán tính nhanh gọi là FFT với độ phức tạp tính toán là O(Nlog2N). Thuật toán tính nhanh có thể tóm tắt như sau: - giả sử N = 2n N - giả sử WN là nghiệm thứ N của đơn vị: WN = e-2j /N và M = 2 ta có: 2 M 1 1  v(k) = 2 M n 0 u(n)W2Mnk - Khai triển công thức trên ta được: M 1 M 1 1  1  v(k) =( M n 0 u(2n)W2M2nk + M n 0 u(2n+1)W2M(2n+1)k )/2 () v× W2M2nk = W 2Mnk, do đó: 1 v(k) = 2 [uchẵn(n) + ulẻ(n)] Chú ý rằng v(k) với k = [0, M-1] là một DFT trên M = N/2. Thực chất thuật toán FFT là dùng nguyên tắc chia đôi và tính chu kỳ để tính DFT. Với k = [0, M-1] ta dùng công thức 3.37; với k = [M, 2M-1] ta dùng phép trừ trongcông thức 3.37. Có thể dùng thuật toán này có sửa đổi một chút để tính DFT ngược. Bạn đọc coi như một bài tập. - Trường hợp 2 chiều Do DFT 2 chiều là tách được nên từ công thức (3.29), ta có: N 1 N 1 1 km WN u(m,n) v(k,l) = N m 0 n 0 WNln () Từ công thức 3.38, ta có cách tính DFT hai chiều như sau: - Tính DFT 1 chiều với mỗi giá trị của x (theo cột) - Tính DFT 1 chiều theo hướng ngược lại (theo hàng) với giá trị thu được ở trên. 4.2. Các bộ lọc làm mƣợt ảnh trong miền tần số - Lọc thông thấp Các đường biên và nhi u trong ảnh tập trung nhiều vào phần tần số cao của phép biến đổi Fourier của nó. Do đó, để làm trơn ảnh bằng phương pháp miền tần số ta có thể loại bỏ các thành phần tần số cao trong biến đổi Fourier của ảnh Nhắc lại là: Trong đó F(u,v) là biến đổi Fourier của ảnh được làm trơn. Vấn đề là lựa chọn một hàm lọc H(u,v) sao cho đạt được G(u,v) bằng cách làm suy giảm các thành phần có tần số cao của F(u,v). Biến đổi Fourier ngược G(u,v) ta có ảnh được làm trơn g(x,y). Vì các thành phần tần số cao bị loại bỏ, và
  36. 36 thông tin trong vùng tần số thấp được cho qua, nên phương pháp này gọi là lọc thông thấp (lowpass filtering). Dưới đây là một vài hàm lọc thường dùng. 4.2.1. Lọc lý tƣởng Lọc thông thấp 2D lý tưởng, viết tắt ILHF, có hàm lọc Trong đó D0 > 0 là hằng số cho trước, gọi là ngưỡng hay tần số cắt, và Là khoảng cách từ gốc tọa độ (0,0) đến điểm (u,v). Thuật ngữ lý tưởng biểu thị tất cả các thành phần tần số nằm trong hình tròn bán kính D0 được giữ nguyên, trong khi tất cả các tần số ngoài đường tròn hoàn toàn bị suy giảm. Chú ý rằng, trong chương này các hàm lọc đối xứng qua gốc. Điều này dựa trên giả thiết gốc của phép biến đổi Fourier đặt tại tâm của hình vuông N x N trong miền tần số. Tần số cắt D0 được chọn tùy theo chúng ta muốn giữ lại bao nhiêu phần trăm của phổ công suất toàn phần. Trong đó P(u,v) là phổ công suất. Số phần trăm giữ lại β và giá trị D0 liên hệ với nhau bởi: 4.2.2 Lọc Butterworth Lọc thông thấp Butterworth bậc n có hàm lọc Hay cải biên 4.3. Các bộ lọc làm sắc nét ảnh trong miền tần số - Lọc thông cao. Ta biết rằng, ảnh có thể bị nhòe do làm suy giảm các thành phần tần số cao trong biến đổi Fourier của nó. Vì các phần tử biên và những cho thay đổi đột ngột khác trong mức xám tương ứng các thành phần tần số cao, việc làm nét ảnh có thể thực hiện trong miền tần số bằng phương pháp
  37. 37 lọc thông cao (highpass filtering): làm suy giảm các thành phần tần số thấp nhưng không phá hủy thông tin tần số cao trong biến đổi Fourier. 4.3.1. Lọc lý tƣởng. Lọc thông cao 2D lý tưởng, viết tắt ILHF, có hàm lọc Trong đó D0 > 0 4.3.2 Lọc Butterworth Lọc thông cao Butterworth bậc n có hàm lọc Hay cải biên CÂU HỎI ÔN TẬP 1. So sánh sự giống và khác nhau của nâng cao chất lượng ảnh trong miền không gian và miền tần số. 2. Trình bày các bộ lọc làm mượt ảnh trong miền tần số? 3. Trình bày các bộ lọc làm sắc nét ảnh trong miền tần số?
  38. 38 CHƢƠNG V: NÉN ẢNH 5.1. Các kiến thức cơ bản a) Nén dữ liệu (Data Compression) Nén dữ liệu nhằm làm giảm lượng thông tin “dư thừa” trong dữ liệu gốc và do vậy, lượng thông tin thu được sau khi nén thường nhỏ hơn dữ liệu gốc rất nhiều. Với dữ liệu ảnh, kết quả thường là 10:1. Một số phương pháp còn cho kết quả cao hơn. Theo kết quả nghiên cứu được công bố gần đây tại Viện Kỹ thuật Georfie, kỹ thuật nén fratal cho tỉ số nén là 30 trên 1 Ngoài thuật ngữ “ é dữ liệu”, do bản chất của kỹ thuật này nó còn có một số tên gọi khác như : giảm độ dư thừa, mã hóa ảnh gốc. Từ hơn hai thập kỷ nay, có rất nhiều kỹ thuật nén đã được công bố trên các tài liệu về nén và các phần mềm nén dữ liệu đã xuất hiện ngày càng nhiều trên thương trường. Tuy nhiên, chưa có phương pháp nén nào được coi là phương pháp vạn năng (Universal) vì nó phụ thuộc vào nhiều yếu tố và bản chất của dữ liệu gốc. Trong chương này, chúng ta không thể hy vọng xem xét tất cả các phương pháp nén. Hơn thế nữa, các kỹ thuật nén dữ liệu chung đã được trình bày trong nhiều tài liệu chuyên ngành. Ở đây, chúng ta chỉ đề cập các phương pháp nén có đặc thù riêng cho dữ liệu ảnh. Tỷ lệ nén (Compression Rate) Tỷ lệ nén là một trong các đặc trưng quan trọng nhất của mọi phương pháp nén. Tuy nhiên, về cách đánh giá và các kết quả công bố trong các tài liệu cũng cần quan tâm xem xét. Nhìn chung, người ta định nghĩa tỷ lệ cơ bản của phương pháp nén. Nhiều khi tỷ lệ nén cao cũng chưa thể nói phương pháp đó hiệu quả hơn các phương pháp khác, vì còn các chi phí như thời gian, không gian và thậm chí cả độ phức tạp tính toán nữa. Thí dụ như nén phục vụ trong truyền dữ liệu: vấn đề đặt ra là hiệu quả nén có tương hợp với đường truyền không. Cũng cần phân biệt dữ liệu với nén băng truyền. Mục đích chính của nén là giảm lượng thông tin dư thừa và dẫn tới giảm kích thước dữ liệu. Tuy vậy, đôi khi quá trình nén cũng làm giảm băng truyền tín hiệu số hóa thấp hơn so với truyền tín hiệu tương tự. b) Các loại dư thừa dữ liệu Như trên đã nói, nén nhằm mục đích giảm kích thước dữ liệu bằng cách loại bỏ dư thừa dữ liệu. Việc xác định bản chất các kiểu dư thừa dữ liệu rất có ích cho việc xây dựng các phương pháp nén dữ liệu khác nhau. Nói một cách khác, các phương pháp nén dữ liệu khác nhau là do sửdụng các kiểu dư thừa khác nhau. Người ta coi có 4 kiểu dư thừa chính : - Sự phân bố ký tự : Trong một dãy ký tự,có một số ký tự có tần suất xuất hiện nhiều hơn so với các dãy khác. Do vậy, ta có thể mã hóa dữ liệu một cách cô đọng hơn. Các dãy ký tự có tần suất cao được thay bởi
  39. 39 một từ mã nhị phân với số bít nhỏ; ngược lại các dãy có tần suất xuất hiện thấp sẽ được mã hóa bởi từ mã có nhiều bít hơn. Đây chính là bản chất của phương pháp mã hóa từ hóa Huffman. - Sự lặp lại của các ký tự : Kỹ thuật nén dùng trong trường hợp này là thay dãy lặp đó bởi dãy mới gồm hai thành phần: số lần lặp và kí hiệu dùng để mã. Phương pháp mã hóa kiểu này có tên là mã hóa loạt dài RLC (Run Length Coding). - Những mẫu sử dụng tần suất: Có thể có dãy ký hiệu nào đó xuất hiện với tần suất tương đối cao. Do vây, có thể mã hóa bởi ít bít hơn. Đây là cơ sở của phương pháp mã hóa kiểu từ điển do Lempel-Ziv đưa ra và có cải tiến vào năm 1977, 1978 và do đó có tên gọi là phương pháp nén LZ77,LZ78. Năm 1984, Tery Welch đã cải tiến hiệu quả hơn và đặt tên là LZW (Lempel-Ziv-Welch). - Độ dư thừa vị trí: Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được ký hiệu (giá trị) xuất hiện tại một vị trí, đồng thời có thể đoán trước sự xuất hiện của các giá trị ở các vị trí khác nhau một cách phù hợp. Chằng hạn, ảnh biểu di n trong một lưới hai chiều, một số điểm ở hàng dọc trong một khối dữ liệu lại xuất hiện trong cùng vị trí ở các hàng khác nhau. Do vậy, thay vì lưu trữ dữ liệu, ta chỉ cần lưu trữ vị trí hàng và cột. Phương pháp nén dựa trên sự dư thừa này gọi là phương pháp mãhóa dự đoán. c) Phân loại phƣơng pháp nén Có nhiều cách phân loại các phương pháp nén khác nhau. Cách thứ nhất dựa vào nguyênlý nén. Cách này phân các phương pháp nén thành hai họ lớn: - Nén chính xác hay nén không mất thông tin: họ này bao gồm các phương pháp nén màsau khi giải nén ta thu được chính xác dữ liệu gốc. - Nén có mất thông tin: họ này bao gồm các phương pháp mà sau khi giải nén ta khôngthu được dữ liệu như bản gốc. Phương pháp này lợi dụng tính chất của mắt người, chấp nhận mộtsố vặn xoắn trong ảnh khi khôi phục lại. Tất nhiên, các phương pháp này chỉ có hiệu quả khi màđộ vặn xoắn chấp nhận được bằng mắt thường hay với dung sai nào đấy. Cách phân loại thứ hai dựa vào cách thức thực hiện nén. Theo cách này, người ta cũng phân thành hai họ: - Phương pháp không gian (Spatial Data Compression): Các phương pháp thuộc họ này thực hiện nén bằng các tác động trực tiếp lên việc lấy mẫu của ảnh trong miền không gian. - Phương pháp sử dụng biến đổi (Transform Coding): gồm các phương pháp tác động lên sự biến đổi của ảnh gốc mà không tác động trực tiếp như họ trên. Có một cách phân loại khác nữa, cách phân loại thứ ba, dựa vào triết lý của sự mã hóa. Cách này cũng phân các phương pháp nén thành hai họ: - Các phương pháp nén thế hệ thứ nhất: Gồm các phương pháp mà mức độ tính toán là đơn giản, thí dụ việc lấy mẫu, gán từ mã,.v.v.
  40. 40 - Các phương pháp nén thế hệ thứ hai: dựa vào độ bão hòa của tỷ lệ nén. 5.2. Nén ảnh không mất thông tin a) Phƣơng pháp mã hóa loạt dài Phương pháp mã hóa loạt dài lúc đầu được phát triển dành cho ảnh số 2 mức: mức đen (1), và mức trắng (0) như các văn bản trên nền trắng, trang in, các bản vẽ kỹ thuật. Nguyên tắc của phương pháp là phát hiện một loạt các bít lặp lại, thí dụ như một loạt các bít 0 nằm giữa hai bít 1, hay ngược lại, một loạt bít 1 nằm giữa hai bít 0. Phương pháp này chỉ có hiệu quả khi chiều dài dãy lặp lớn hơn một ngưỡng nào đó. Dãy các bít lặp gọi là loạt hay mạch (run). Tiếp theo, thay thế chuỗi đó bởi một chuỗi mới gồm 2 thông tin: chiều dài chuỗi và bít lặp (ký tự lặp). Như vậy, chuỗi thay thế sẽ có chiều dài ngắn hơn chuỗi cần thay. Cần lưu ý rằng, đối với ảnh, chiều dài của chuỗi lặp có thể lớn hơn 255. Nếu ta dùng 1 byte để mã hóa thí sẽ không đủ. Giải pháp được dùng là tách các chuỗi đó thành hai chuỗi: một chuỗi có chiều dài 255, chuỗi kia là số bít còn lại. Phương pháp RLC được sử dụng trong việc mã hóa lưu trữ các ảnh Bitmap theo dạng PCX, BMP. Phương pháp RLC có thể chia thành 2 phương pháp nhỏ: phương pháp dùng chiều dài tứ mã cố định và phương pháp thích nghi như kiểu mã Huffman. Giả sử các mạch gồm M bits. Để tiện trình bày, đặt M = 2m – 1. Như vậy mạch cũ được thay bởi mạch mới gồm m bits. Với cách thức này, mọi mạch đều được mã hóa bởi từ mã có cùng độ dài. Người ta cũng tính được, với M = 15, p = 0,9, ta sẽ có m = 4 và tỷ số nén là 1,95. Với chiều dài cố định, việc cài đặt thuật toán là đơn giản. Tuy nhiên, tỷ lệ nén sẽ không tốt bằng chiều dài biến đổi hay gọi là mã RLC thích nghi. b) Phƣơng pháp mã hóa Huffman Nguyên tắc Phương pháp mã hóa Huffman là phương pháp dựa vào mô hình thông kê. Dựa vào dữ liệu gốc, người ta tính tần suất xuất hiện của các ký tự. Việc tính tần suất được thực hiện bởi cách duyệt tuần tự tệp gốc từ đầu đến cuối. Việc xử lý ở đây tính theo bit. Trong phương pháp này người ta gán cho các ký tự có tần suất cao một từ mã ngắn, các ký tự có tần suất thấp từ mã dài. Nói một cách khác, các ký tự có tần suất càng cao được gán mã càng ngắn và ngược lại. R rang với cách thức này, ta đã làm giảm chiều dài trung bình của từ mã hóa bằng cách dùng chiều dài biến đổi. Tuy nhiên, trong một số tình huống khi tần suất là rất thấp, ta có thể không được lợi một chút nào, thậm chí còn bị thiệt một ít bit. Thuật toán Thuật toán bao gồm 2 bước chính:
  41. 41 - Giai đoạn thứ nhất: tính tần suất của các ký tự trong dữ liệu gốc: duyệt tệp gốc một cách tuần tự từ đầu đến cuối để xây dựng bảng mã. Tiếp sau đó là sắp xếp lại bảng mã theo thứ tự tần suất giảm dần. - Giai đoạn thứ hai: mã hóa: duyệt bảng tần suất từ cuối lên đầu để thực hiện ghép 2 phần tử có tần suất xuất hiện thấp nhất thành một phần tử duy nhất. Phần tử này có tần suất bằng tổng 2 tần suất thành phần. Tiến hành cập nhật lại bảng và đương nhiên loại bỏ 2 phần tử đã xét. Quá trình được lặp lại cho đến khi bảng chỉ có một phần tử. Quá trình này gọi là quá trình tạo cây mã Huffman vì việc tập hợp được tiến hành nhờ một cây nhị phân 2 nhánh. Phần tử có tần suất thấp ở bên phải, phần tử kia ở bên trái. Với cách tạo cây này, tất cả các bit dữ liệu/ký tự là nút lá; các nút trong là các nút tổng hợp. Sau khi cây đã tạo xong, người ta tiến hành gán mã cho các nút lá. Việc mã hóa rất đơn giản: mỗi lần xuống bên phải ta thêm 1 bit “1” vào từ mã; mỗi lần xuống bên trái ta thêm một bit “0”. Tất nhiên có thể làm ngược lại, chỉ có giá trên mã thay đổi còn tổng chiều dài là không đổi. Cũng chính do lý do này mà cây có tên gọi là cây mã Huffman như trên đã gọi. Quá trình giải nén tiến hành theo chiều ngược lại khá đơn giản. Người ta cũng phải dựa vào bảng mã tạo ra trong giai đoạn nén (bảng này được giữ lại trong cấu trúc của tệp nén cùng với dữ liệu nén). Thí dụ, với một tệp dữ liệu mà tần suất các ký tự cho bởi. c) Phƣơng pháp LZW Mở đầu Khái niệm nén từ điển được Jacob Lempel và Abraham Ziv đưa ra lần đầu tiên vào năm 1997, sau đó phát triển thành một họ giải thuật nén từ điển LZ. Năm 1984, Terry Welch đã cải tiến giải thuật LZ thành một giải thuật mới hiệu quả hơn và đặt tên là LZW. Phương pháp nén từ điển dựa trên việc xây dựng từ điển lưu các chuỗi ký tự có tần suất lặp lại cao và thay thế bằng từ mã tương ứng mỗi khi gặp lại chúng. Giải thuật LZW hay hơn các giải thuật trước nó ở kỹ thuật tổ chức từ điển cho phép nâng cao tỉ lệ nén. Giải thuật nén LZW được sử dụng cho tất cả các loại file nhị phân. Nó thường được dung để nén các loại văn bản, ảnh đen trắng, ảnh màu, ảnh đa mức xám và là chuẩn nén cho các dạng ảnh GIF và TIFF. Mức độ hiệu quả của LZW không phụ thuộc vào số bít màu của ảnh. Phƣơng pháp Giải thuật nén LZW xây dựng một từ điển lưu các mẫu có tần suất xuất hiện cao trong ảnh. Từ điển là tập hợp những cặp ừ vựng và ghĩa của nó. Trong đó, ừ vựng sẽ là các từ mã được sắp xếp theo thứ tự nhất định. ghĩa là một chuỗi con trong dữ liệu ảnh. Từ điển được xây dựng đồng thời với quá trình đọc dữ liệu. Sự có mặt của một chuỗi con trong từ điển khẳng định rằng chuỗi đó đã từng xuất hiện trong phần dữ liệu đã đọc. Thuật toán liên tục “tra cứu” và cập nhật từ điển sau mỗi lần đọc một ký tự ở dữ liệu đầu vào.
  42. 42 Do kích thước bộ nhớ không phải vô hạn và để đảm bảo tốc độ tìm kiếm, từ điển chỉ giới hạn 4096 ở phần tử dùng để lưu lớn nhất là 4096 giá trị của các từ mã. Như vậy độ dài lớn nhất của từ mã là 12 bits (4096 = 212). Cấu trúc từ điển như sau: + 256 từ mã đầu tiên theo thứ tự từ 0 255 chữa các số nguyên từ 0 255. Đây là mã của 256 kí tự cơ bản trong bảng mã ASCII. + Từ mã thứ 256 chứa một mã đặc biệt là “mã xóa” (CC – Clear Code). Mục đích việc dùng mã xóa nhằm khắc phục tình trạng số mẫu lặp trong ảnh lớn hơn 4096. Khi đó một ảnh được quan niệm là nhiều mảnh ảnh, và từ điển là một bộ từ điển gồm nhiều từ điển con. Cứ hết một mảnh ảnh người ta lại gửi một mã xóa để báo hiệu kết thúc mảnh ảnh cũ, bắt đầu mảnh ảnh mới đồng thời khởi tạo lại từ điển cho mảnh ảnh mới. Mã xóa có giá trị là 256. + Từ mã thứ 257 chứa mã kết thúc thông tin (EOI – End Of Information). Mã này có giá trị là 257. Như chúng ta đã biết, một file ảnh GIF có thể chứa nhiểu ảnh. Mỗi một ảnh sẽ được mã hóa riêng. Chương trình giải mã sẽ lặp đi lặp lại thao tác giải mã từng ảnh cho đến khi gặp mã kết thúc thông tin thì dừng lại. + Các từ mã còn lại (từ 258 đến 4095) chứa các mẫu thương lặp lại trong ảnh. 512 phần tử đầu tiên của từ điển biểu di n bằng 9 bit. Các từ mã từ 512 đến 1023 biểu di n bởi 10 bit, từ 1024 đến 2047 biểu di n bởi 11 bit và từ 2048 đến 4095 biểu di n bởi 12 bit. Ví dụ minh họa cơ chế nén của LZW Cho chuỗi đầu vào là “ABCBCABCABCD” (Mã ASCII của A là 65, B là 66, C là 67) Từ điển ban đầu gồm 256 kí tự cơ bản.
  43. 43 5.3. Nén ảnh có mất thông tin Tuy bản chất của các phương pháp nén dựa vào biến đổi rất khác với các phương pháp đã trình bày ở trên, song theo phân loại nén, nó vẫn được xếp vào vào họ thứ nhất. Vì có các đặc thù riêng nên chúng ta xếp trong phần này. a) Nguyên tắc chung Các phương pháp mã hóa dựa vào biến đổi làm giảm lượng thông tin dư thừa không tác động lên miền không gian của ảnh số mà tác động lên miền biến đổi. Các biến đổi được dùng ở đây là các biến đổi tuyến tính như: biến đổi KL, biến đổi Fourrier, biến đổi Hadamard, Sin, Cosin vv Vì ảnh số thường có kích thước rất lớn, nên trong cài đặt người ta thường chia ảnh thành các khối chữ nhật nhỏ. Thực tế, người ta dùng khối vuông kích thước cỡ 16x16. sau đó biến đổi từng khối một cách độc lập. Chúng ta đã biết, dạng chung của biến đổi tuyến tính 2 chiều là: - x(k,1) là tín hiệu vào - a(m,n,k,1) là các hệ số của biến đổi – là phần tử của ma trận biến đổi A. Ma trận này gọi là nhân của biến đổi. Cách xác định các hệ số này là phụ thuộc vào từng loại biến đổi sử dụng. Đối với phần lớn các biến đổi 2 chiều, nhân có tính đối xứng và tách được : A[m,n,k,1] = A’[ ,k] A’’[ ,1]
  44. 44 Nếu biến đổi là KL thì các hệ số đó chính là các phần tử của véctơ riêng. b) Thuật toán mã hóa dùng biến đổi 2 chiều Các phương pháp mã hóa dùng biến đổi 2 chiều thường có 4 bước sau: B1. Chia nh thành kh i - Ảnh được chia thành các khối nhỏ kích thước k x 1 và biến đổi các khối đó một cách độc lập để thu được các khối Vi, i=0,1, ,B với B = MxN/(k x1). B2. c định phân ph i bit cho từng kh i - Thường các hệ số hiệp biến của các biến đổi là khác nhau. Mỗi hệ số yêu cầu lượng hóa với một số lượng bit khác nhau. B3. Thiết kế bộ lượng hóa - Với phần lớn các biết đổi, các hệ số v(0, 0) là không âm. Các hệ số còn lại có trung bình 0. Để tính các hệ số, ta có thể dùng phân bố Gauss hay Laplace. Các hệ số được mã hóa bởi số bit khác nhau, thường từ 1 đến 8 bit. Do vậy cần thiết kế 8 bộ lượng hóa. Để d cài đặt, tín hiệu vào v1 (k, l) được chuẩn hóa để có dạng: Trước khi thiết kế bộ lượng hóa, người ta tìm cách loại bỏ một số hệ số không cần thiết. B4. Mã hóa - Tín hiệu đầu vào của bộ lượng hóa sẽ được mã hóa trên các từ bit để truyền đi hay lưu trữ lại. Quá trình mã hóa dựa vào biến đổi có thể được tóm tắt trên hinh 7.4 - Nếu ta chọn phép biến đổi KL, cho phương pháp sẽ có một số nhược điểm: khối lượng tính toán sẽ rất lớn vì phải tính ma trận hiệp biến, tiếp sau là phải giải phương trình tìm trị riêng và véctơ riêng để xác định các hệ số. Vì lý do này, trên thực tế người ta thích dùng các biến đổi khác như Hadamard, Haar, Sin và Cosin. Trong số biến đổi này, biến đổi Cosin thường hay được dùng nhiều hơn. c) Mã hóa dùng biến đổi Cosin và chuẩn JPEG
  45. 45 * Phép biến đổi Cosin một chiều - Phép biến đổi Cosin rời rạc (DCT) được Ahmed đưa ra vào năm 1974. Kể từ đó đến nay nó được ứng dụng rất rộng rãi trong nhiều phương pháp mã hóa ảnh khác nhau nhờ hiệu suất gần như tối ưu của nó đối với các ảnh có độ tương quan cao giữa các điểm ảnh lân cận. Biến đổi Cosin rời rạc được sử dụng trong chuẩn ảnh nén JPEG và định dạng phim MPEG. Phé biế đổi C i ộ chiều Phép biến đổi Cosin rời rạc một chiều đƣợc định nghĩa bởi: Khi dãy đầu vào x(n) là thực thì dãy các hệ số X(k) cũng là số thực. Tính toán trên trường số thực giảm đi một nửa thời gian so với biến đổi Fourier. Để đạt được tốc độ biến đổi thỏa mãn yêu cầu của các ứng dụng thực tế, người ta đã cải tiến kĩ thuật tính toán và đưa ra nhiều thuật toán biến đổi nhanh Cosine. Một trong những thuật toán đó được giới thiệu dưới đây. * Phép biến đổi Cosin nhanh Phép biến đổi Cosin nhanh viết tắt là FCT (Fast Cosine Transform), dựa vào ý tưởng đưa bài toán ban đầu về tổ hợp các bài toán biến đổi FCT trên các dãy con. Việc tiến hành biến đổi trên các dãy con sẽ đơn giản hơn rất nhiều so với dãy gốc. Vì thế, người ta tiếp tục phân nhỏ dãy tín hiệu cho đến khi chỉ còn một phần tử. Giải thuật biến đổi Cosin nhanh không thực hiện trực tiếp trên dãy tín hiệu đầu vào x(n) mà thực hiện trên dãy ’( ) là một hoán vị của x(n). Giả thiết số điểm cần tính FCT là lũy thừa của 2: N=2M. Dữ liệu đầu vào sẽ được sắp xếp lại như sau: Như vậy, nửa đầu dãy ’( ) là các phần tử chỉ số chẵn của x(n) xếp theo chiều tăng dần của chỉ số. Nửa sau của ’( ) là các phần tử chỉ số lẻ của x(n) xếp theo chiều giảm dần của chỉ số. Thay vào công thức Cosin rời rạc ta được: Rút gọn biểu thức:
  46. 46 Chia X(k) ra làm hai dãy, một dãy bao hàm các chỉ số chẵn, còn dãy kia gồm các chỉ số lẻ. Phần chỉ số chẵn Có thể chuyển về dạng: Thuật toán biến đổi nhanh Cosin có thể mô tả bằng các bước sau: i Bước 1: Tí h dãy hệ C j. Xác định số tầng M = log2 N Tầng hiện thời m=1 Bước 2: ếu ≤ M hực hiệ bước 5. ếu kh g kế húc. (Chưa hết các khối trong một tầng) Bước 3: Kh i hiệ hời k = 0. Bước 4: ếu k<2 -1 Thực hiệ bước 5. ếu kh g hực hiệ bước 6. (Chưa hết các khối trong một tầng) Bước 5: Tí h (i) g kh i he c g hức ổ g qu Tă g k ê 1. Quay về bước 4. Bước 6: Tă g ê 1. Quay về bước 2 (Chuyển đến tầng tiếp theo) Khác với biến đổi Fourier nhanh, trong biến đổi Cosin, x(n) không phải đầu vào trực tiếp và X(k) không phải là đầu ra trực tiếp. CÂU HỎI ÔN TẬP 1.Trình bày khái niệm nén dữ liệu? Tỷ lệ nén dữ liệu? Các loại dư thừa dữ liệu? 2. Trình bày các phương pháp nén ảnh không mất thông tin? 3. Trình bày các phương pháp nén ảnh có mất thông tin?
  47. 47 CHƢƠNG VI: XƢ LÝ HÌNH THÁI ẢNH 6.1. Phép giãn ảnh và phép co ảnh nhị phân Với ảnh nhị phân, mức xám chỉ có 2 giá trị là 0 hay 1. Do vậy, ta coi một phần tử ảnh như một phần tử lô gíc và có thể áp dụng các toán tử hình học (morphology operators) dựa trên khái niệm biến đổi hình học của một ảnh bởi một phần tử cấu trúc (structural element). Phần tử cấu trúc là một mặt nạ dạng bất kỳ mà các phần tử của nó tạo nên một mô-típ. Người ta tiến hành rê mặt nạ đi khắp ảnh và tính giá trị điểm ảnh bởi các điểm lân cận với mô-típ của mặt nạ theo cách lấy hội hay lấy tuyển. Hình dưới đây , chỉ ra một phần tử cấu trúc và cách lấy hội hay tuyển: 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 a) Phần tử cấu trúc b) một vùng ảnh 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 c) Tuyển d) Hội Hình 4.16. Cải thiện ảnh nhị phân Dựa vào nguyên tắc trên, ngƣòi ta sử dụng 2 kỹ thuật: dãn ảnh (dilatation) và co ảnh (erosion). Dãn ảnh nhằm loại bỏ điểm đen bị vây bởi các điểm trắng. Trong kỹ thuật này, một cửa sổ N+1 x N+1 được rê đi khắp ảnh và thực hiện đối sánh một pixel của ảnh với (N+1)2 -1 điểm lân cận (không tính điểm ở tâm). Phép đối sánh ở đây thực hiện bởi phép tuyển lôgíc. Thuật toán biến đổi được tóm tắt như sau: For all pixels I(x,y) do Begin . Tính FOR(x,y) {tính or lô gíc } - if FOR(x,y) then ImaOut(x,y) < 1 else ImaOut(x,y) <- ImaIn(x,y) End
  48. 48 6.2. Phép mở ảnh và phép đóng ảnh nhị phân Co ảnh là thao tác đối ngẫu của giãn ảnh nhằm loại bỏ điểm trắng bị vây bởi các điểm đen. Trong kỹ thuật này, một cửa sổ (N+1) x (N+1) được rê đi khắp ảnh và thực hiện sánh một pixel của ảnh với (N+1)2 -1 điểm lân cận. Sánh ở đây thực hiện bởi phép hội lôgíc. Thuật toán biến đổi được tóm tắt như sau: For all pixels I(x,y) do Begin . Tính FAND(x,y) {Tính và lô gíc} - if FAND(x,y) then ImaOut(x,y) < 1 else ImaOut(x,y) <- ImaIn(x,y) End Á dụ g: Ngưòi ta thường vận dụng kỹ thuật này cho các ảnh nhị phân như vân tay, chữ viết. Để không làm ảnh hưởng đến kích thước của đối tượng trong ảnh, người ta tiến hành n lần dãn và n lần co. 6.3. Một số thuật toán hình thái cơ bản trên ảnh nhị phân Khuyếch đại và nội suy ảnh Có nhiều ứng dụng cần thiết phải phóng đại một vùng của ảnh. Có nghĩa là lấy một vùng của ảnh đã cho và cho hiện lên như một ảnh lớn. Có 2 phương pháp được dùng là lặp (Replication) và nội suy tuyến tính (linear interpolation). Phƣơng pháp lặp Người ta lấy một vùng của ảnh kích thước M x N và quét theo hàng. Mỗi điểm ảnh nằm trên đường quét sẽ được lặp lại 1 lần và hàng quét cũng được lặp lại 1 lần nữa. Như vậy ta sẽ thu được ảnh với kích thước 2N x 2N. Điều này tương đương với chèn thêm một hàng 0 và một cột 0 rồi chập với mặt nạ H. 1 1 H 1 1 Kết quả thu được v(m,n) = u(k,l) với k = [m/2] và l = [n/2] (4-13) Ở đây phép toán [.] là phép toán lấy phần nguyên của một số. Hình dưới đây minh hoạ nội suy theo phương pháp lặp:
  49. 49 1 3 2 1 0 3 0 2 0 ChÌn hµng ChËp 4 5 6 0 0 0 0 0 0 H 0, 4 0 5 0 6 0 Cét 0 0 0 0 0 0 0 1 1 3 3 2 2 1 1 3 3 2 2 4 4 5 5 6 6 4 4 5 5 6 6 Hình 4-15 Khuếch đại bởi lặp 2 x 2 Phƣơng pháp nội suy tuyến tính Trước tiên, hàng được đặt vào giữa các điểm ảnh theo hàng. Tiếp sau, mỗi điểm ảnh dọc theo cột được nội suy theo đường thẳng. Thí dụ với khuếch đại 2x2, nội suy tuyến tính theo hàng sẽ tính theo công thức: v1(m,n) = u(m,n) v1(m,2n+1) = u(m,n) + u(m,n+1) (4-14) với 0 m M-1, 0 n N-1 và nội suy tuyến tính của kết quả trên theo cột: v1(2m,n) = v1(m,n) v1(2m+1,n) = v1(m,n) + v1(m+1,n) (4-15) với 0 m M-1, 0 n N-1. Nếu dùng mặt nạ: 1 1 1 4 2 4 1 1 H 1 2 2 1 1 1 4 2 4 ta cũng thu được kết quả trên. Nội suy với bậc cao hơn cũng có thể áp dụng cách trên. Thí dụ, nội suy với bậc p (p nguyên), ta chèn p hàng các số 0 , rồi p cộtcác số 0. Cuối cùng, tiến hành nhân chập p lần ảnh với mặt nạ H ở trên [1]. 6.4. Xử lý hình thái ảnh xám
  50. 50 Thông thường, trong phân tích ảnh, ta muốn nghiên cứu tỉ mỉ một vùng cụ thể trong ảnh, ta gọi là vùng quan tâm (Region of Interest-ROI). Để làm điều đó, ta cần các thao tác chỉnh sửa các toạ độ không gian của ảnh, và chúng được xếp vào loại các thao tác hình học ảnh. Các thao tác hình học ảnh trình bày ở đây bao gồm: cắt xén, zoom, phóng to (enlarge), thu nhỏ (shrink), tịnh tiến, và quay. Quá trình cắt xén ảnh là quá trình chọn ra một phần nhỏ của ảnh, một ảnh con, và cắt nó ra khỏi phần còn lại của ảnh. Sau khi ta đã cắt xén ra một ảnh con từ ảnh gốc, ta có thể zoom to nó bằng cách phóng to nó. Quá trình zoom này có thể được thực hiện theo một số cách thức khác nhau, nhưng thông thường là được thực hiện ở xử lý bậc 0 hoặc bậc nhất (zero- or first-order hold ). Một xử lý bậc 0 được thực hiện bằng cách lặp lại các giá trị pixel trước đó, do đó tạo ra một hiệu ứng khối (block). Để mở rộng kích thước ảnh bằng xử lý bậc nhất, ta cần thực hiện một phép nội suy tuyến tính giữa các pixel kề nhau. Trên 2.2-1 là kết quả so sánh giữa hai phương pháp này lên ảnh. Hình 2.2-1. Các phương pháp Zoom Bậc 0: Việc thực thi xử lý bậc 0 là r ràng trong khi xử lý bậc nhất phức tạp hơn. Cách d
  51. 51 dàng nhất là tìm giá trị trung bình giữa hai pixel và sử dụng nó làm giá trị cho pixel xen vào giữa; ta có thể làm điều này cho các hàng trước (sau đó đến các cột), như sau: 8 4 8 8 6 4 6 8 4 8 4 4 6 8 6 4 8 2 8 8 5 2 5 8 Hai pixel đầu tiên trong hàng thứ nhất được lấy trung bình (8 + 4)/2 = 6, và số này được chèn vào giữa hai pixel này. Công việc này được lặp lại cho tất cả các cặp pixel trong mỗi hàng. Tiếp theo ta thực hiện cho các cột với cùng cách thức, ta được: 8 6 4 6 8 6 6 6 6 6 4 6 8 6 4 6 5.5 5 5.5 6 8 5 2 5 8 Phương pháp này cho phép mở rộng được một ảnh kích thước N x N thành ảnh có kích thước (2N - 1) x (2N - 1). Bậc 1: Một phương pháp khác (xử lý bậc nhất) cho phép thu được cùng kết quả trên là một quá trình toán học được gọi là phép cuộn. Với phương pháp cuộn dùng mở rộng ảnh, có hai bước cần tiến hành mở rộng ảnh bằng cách chèn thêm các hàng và các cột toàn 0 vào giữa các hàng và cột hiện có và thực hiện phép cuộn. Thực hiện bước 1 – mở rộng ảnh bằng chèn thêm 0 như sau: 0 0 0 0 0 0 0 0 3 0 5 0 0 7 0 0 0 0 0 0 0 0 2 0 7 0 0 6 3 5 7 0 0 0 0 0 0 0 2 7 6 0 3 0 4 0 0 9 3 4 9 0 0 0 0 0 0 0 Tiếp theo để thực hiện bước 2, ta sử dụng một mặt nạ cuộn, nó sẽ được trượt lên toàn bộ ảnh đã mở rộng, và thực hiện một phép toán số học đơn giản tại mỗi vị trí của pixel. Mặt nạ cuộn cho phép xử lý bậc nhất được chọn là:
  52. 52 1 1 1 4 2 4 1 1 1 2 2 1 1 1 4 2 4 Quá trình cuộn thực hiện bằng cách chồng mặt nạ lên ảnh, nhân các cặp giá trị trùng khớp lên nhau, và cộng tất cả lại. Điều này tương đương với việc tìm tích vô hướng của véc tơ mặt nạ với ảnh con ngay phía dưới. Chẳng hạn, nếu ta đặt mặt nạ lên góc trái trên của ảnh, ta thu được tính toán (thể hiện ở đây là theo thứ tự từ trái qua phải, và từ trên xuống dưới): 1 1 1 4 2 4 1 1 1 0 0 0 2 2 0 3 0 1 1 1 0 0 0 nhân vô hướng véc tơ 4 2 4 = 1 1 1 1 1 1 1 1 0 0 0 0 1 3 0 0 0 0 3 = 4 2 4 2 2 4 2 4 Chú ý rằng, giá trị hiện có của ảnh vẫn chưa thay đổi. Bước tiếp theo là ta trượt mặt nạ sang phải một pixel và lặp lại quá trình tính toán như trên, ta có: 0 0 0 3 0 5 0 0 0 * = 1 1 1 1 1 1 1 1 0 0 0 3 1 0 5 0 0 0 4 = 4 2 4 2 2 4 2 4 Chú ý rằng, ở đây toán tử cuộn đã thực hiện một phép lấy trung bình 2 pixel láng giềng. Quá trình này tiếp tục cho đến cuối hàng, mỗi lần đặt kết quả tính toán được vào vị trí tương ứng với tâm của mặt nạ. Khi kết thúc một hàng, mặt nạ được trượt xuống và về đầu hàng tiếp theo và quá trình lặp lại theo từng hàng cho đến thủ tục thực hiện xong cho toàn bộ ảnh; quá trình trượt, nhân, lấy tổng trên được gọi là phép cuộn (xem hình 2.2-2). Chú ý rằng ảnh đầu ra phải được đặt trong một mảng ảnh riêng khác, gọi là bộ đệm, do đó để cho các giá trị hiện có không bị ghi đè trong quá trình cuộn. Nếu ta gọi mặt nạ cuộnlà M(r, c) và ảnh là I(r, c), thì phương trình cuộn được cho bởi:
  53. 53   I(r x,c y)M (x, y) x y Tịnh tiến và quay ảnh: Hai thao tác đáng chú ý khác trong hình học ảnh ROI là tịnh tiến và quay. Quá trình tịnh tiến có thể được thực hiện với các phương trình sau: r' r r0 c' c c0 trong đó r’ và c’ là các toạ độ mới, r và c là các toạ độ ban đầu, và r0 và c0 là các khoảng cách cần dịch chuyển (tịnh tiến) ảnh. Quá trình quay cần sử dụng các phương trình sau: rˆ r cos csin cˆ r sin ccos trong đó rˆ,cˆ là các toạ độ mới, r và c là các toạ độ ban đầu,  là góc quay.  được định nghĩa theo chiều quay kim đồng hồ tính từ trục hoành trong ảnh mà gốc toạ độ nằm ở góc trái trên. Cả hai quá trình quay và tịnh tiến có thể được tổ hợp vào thành cùng một phương trình như sau: rˆ (r r0 )cos (c c0 )sin ˆ c (r r0 )sin (c c0 )cos với r' và c' là các toạ độ mới, r, c, r0, c0 và  như đã định nghĩa ở trên. Có một số khó khăn thực tế khi áp dụng trực tiếp các phương trình trên. Khi tịnh tiến, sẽ làm gì với không gian “thừa”. Nếu ta dịch chuyển mọi thứ trên hàng đi xuống, thì ta sẽ đặt cái gì vào hàng trên cùng? Có hai tuỳ chọn cơ bản: tô đầy hàng trên cùng với một giá trị không đổi, thường là đen (0) hoặc trắng (255), hoặc quấn lại bằng cách dịch hàng dưới đáy lên trên cùng, như hình Hình 2.2-3. Phép quay cũng tương tự, như hình 2.2-4a minh hoạ ảnh có thể được quay rotated off "screen" (mặt phẳng ảnh). Mặc dù điều này có thể cố định lại bằng cách tịnh tiến trở lại tâm (Hình 2.2-4b, c), nhưng ta vẫn có những không gian thừa ở các góc. Ta có thể tô đầy không gian này bằng hằng số, hoặc cắt ra phần trung tâm là phần hình chữ nhật của ảnh rồi mở rộng ra kích thước ảnh ban đầu.
  54. 54 Hình 2.2-3. Tịnh tiến Hình 2.2-4. Phép quay CÂU HỎI ÔN TẬP 1. Trình bày phép giãn ảnh. Cho ví dụ? Nhận xét kết quả? 2. Trình bày phép co ảnh. Cho ví dụ? Nhận xét kết quả? 3. Trình bày phép mở ảnh? Cho ví dụ? Nhận xét kết quả? 4. Trình bày phép đóng ảnh? Cho ví dụ? Nhận xét kết quả?
  55. 55 CHƢƠNG VII: PHÂN ĐOẠN ẢNH 7.1. Phát hiện tính không liên tục Phân vùng ảnh là bước then chốt trong xử lý ảnh. Giai đoạn này nhằm phân tích ảnh thành những thành phần có cùng tính chất nào đó dựa theo biên hay các vùng liên thông. Tiêu chuẩn để xác định các vùng liên thông có thể là cùng mức xám, cùng màu hay cùng độ nhám Trước hết cần làm r khái niệm "vùng ảnh" (Segment) và đặc điểm vật lý của vùng. Vùng ảnh là một chi tiết, một thực thể trông toàn cảnh. Nó là một tập hợp các điểm có cùng hoặc gần cùng một tính chất nào đó : mức xám, mức màu, độ nhám Vùng ảnh là một trong hai thuộc tính của ảnh. Nói đến vùng ảnh là nói đến tính chất bề mặt. Đường bao quanh một vùng ảnh (Boundary) là biên ảnh. Các điểm trong một vùng ảnh có độ biến thiên giá trị mức xám tương đối đồng đều hay tính kết cấu tương đồng. Dựa vào đặc tính vật lý của ảnh, người ta có nhiều kỹ thuật phân vùng : phân vùng dựa theo miền liên thông gọi là phân vùng dựa theo miền đồng nhất hay miền kề ; phân vùng dựa vào biên gọi là phân vùng biên. Ngoài ra còn có các kỹ thuật phân vùng khác dựa vào biên độ, phân vùng dựa theo kết cấu. a) Phân vùng ảnh theo ngƣỡng biên độ Các đặc tính đơn giản, cần thiết nhất của ảnh là biên độ và các tính chất vật lý như : độ tương phản, độ truyền sáng, màu sắc hoặc đáp ứng phổ. Như vậy, có thể dùng ngưỡng biên độ để phân vùng khi biên độ đủ lớn đặc trưng cho ảnh. Thí dụ, biên độ trong bộ cảm biến ảnh hồng ngoại có thể phản ánh vùng có nhiệt độ thấp hay vùng có nhiệt độ cao. Kỹ thuật phân ngưỡng theo biên độ rất có lợi đối với ảnh nhị phân như văn bản in, đồ họa, ảnh màu hay ảnh X-quang. Việc chọn ngưỡng rất quan trọng. Nó bao gồm các bước : - Xem xét lược đồ xám của ảnh để xác định các đỉnh và các khe. Nếu ảnh có dạng rắn lượn (nhiều đỉnh và khe), các khe có thể dùng để chọn ngưỡng. - Chọn ngưỡng t sao cho một phần xác định trước η của toàn bộ số mẫu là thấp hơn t. - Điều chỉnh ngƣỡng dựa trên lƣợc đồ xám của các điểm lân cận. - Chọn ngưỡng theo lược đồ xám của những điểm thỏa mãn tiêu chuẩn chọn. Thí dụ, với ảnh có độ tương phản thấp, lược đồ của những điểm có biên độ Laplace g(m,n) lớn hơn giá trị t định trước (sao cho từ 5% đến 10% số điểm ảnh với Gradient lớn nhất sẽ coi như biên) sẽ cho phép xác định các đặc tính ảnh lưỡng cực tốt hơn ảnh gốc. - Khi có mô hình phân lớp xác suất, việc xác định ngưỡng dựa vào tiêu chuẩn xác suất nhằm cực tiểu xác suất sai số hoặc dựa vào một số tính chất khác của luật Bayes. 7.2. Phân đoạn ảnh dựa vào các vùng ảnh con
  56. 56 Kỹ thuật phân vùng ảnh thành các miền đồng nhất dựa vào các tính chất quan trọng nào đó của miền ảnh. Việc lựa chọn các tính chất của miền sẽ xác định tiêu chuẩn phân vùng. Tính đồng nhất của một miền ảnh là điểm chủ yếu xác định tính hiệu quả của việc phân vùng. Các tiêu chuẩn hay được dùng là sự thuần nhất về mức xám, màu sắc đối với ảnh màu, kết cấu sợi và chuyển động. Các phương pháp phân vùng ảnh theo miền đồng nhất thường áp dụng là : - Phương pháp tách cây tứ phân - Phương pháp cục bộ - Phương pháp tổng hợp a) Phƣơng pháp tách cây tứ phân Về nguyên tắc, phương pháp này kiểm tra tính đúng đắn của tiêu chuẩn đề ra một cách tổng thể trên miền lớn của ảnh. Nếu tiêu chuẩn được thỏa mãn, việc phân đoạn coi như kết thúc. Trong trường hợp ngược lại, chia miền đang xét thành 4 miền nhỏ hơn. Với mỗi miền nhỏ, áp dụng một cách đệ quy phương pháp trên cho đến khi tất cả các miền đều thỏa mãn điều kiện. Phƣơng pháp này có thể mô tả bằng thuật toán sau : Procedure PhanDoan(Mien) Begin If iề đa g é kh g hỏa The Begin Chia iề đa g é hà h 4 iề : Z1, Z2, Z3, Z4 For i=1 to 4 do PhanDoan (Zi) End Else exit End Tiêu chuẩn xét miền đồng nhất ở đây có thể dựa vào mức xám. Ngoài ra, có thể dựa vào độ lệch chuẩn hay độ chênh giữa giá trị mức xám lớn nhất và giá trị mức xám nhỏ nhất. Giả sử Max và Min là giá trị mức xám lớn nhất và nhỏ nhất trong miền đang xét. Nếu : |Max – Min| < T (ngưỡng) ta coi miền đang xét là đồng nhất. Trường hợp ngược lại, miền đang xét không là miền đồng nhất và sẽ được chia làm 4 phần. Thuật toán kiểm tra tiêu chuẩn dựa vào độ chênh lệch max, min được viết : Function Examin_Criteria(I, N1, M1, N2, M2, T) /* i hiế h có i đa 255 ức . ( 1, M1), ( 2, M2) à ọa độ điể đầu và điể cu i của iề ; T à gưỡ g. */ Begin 1. Max=0 ; Min=255
  57. 57 2. For i = N1 to N2 do If I[i,j] < Min Then Min=I[i,j] ; If I[i,j]<Max Then Max=I[i,j] ; 3. If ABS(Max–Min)<T Then Examin_Criteria=0 Else Examin_Criteria=1 ; End Nếu hàm trả về giá trị 0, có nghĩa vùng đang xét là đồng nhất, nếu không thì không đồng nhất. Trong giải thuật trên, khi miền là đồng nhất cần tính lại giá trị trung bình và cập nhật lại ảnh đầu ra. Giá trị trung bình được tính bởi : Tổ g gi ị ức / ổ g điể h g vù g Thuật toán này tạo nên một cây mà mỗi nút cha có 4 nút con ở mọi mức trừ mức ngoài cùng. Vì thế, cây này có tên là cây tứ phân. Cây cho ta hình ảnh r nét về cấu trúc phân cấp của các vùng tương ứng với tiêu chuẩn. Một vùng thỏa mãn điều kiện sẽ tạo nên một nút lá; nếu không nó sẽ tạo nên một nút trong và có 4 nút con tương ứng. Tiếp tục như vậy cho đến khi phân chia xong để đạt các vùng đồng nhất. b) Phƣơng pháp cục bộ Ý tưởng của phương pháp là xét ảnh từ các miền nhỏ nhất rồi nối chúng lại nếu thỏa mãn tiêu chuẩn để được một miền đồng nhất lớn hơn. Tiếp tục với các miền thu được cho đến khi không thể nối thêm được nữa. Số miền còn lại cho ta kết quả phân đoạn. Như vậy, miền nhỏ nhất của bước xuất phát là điểm ảnh. Phương pháp này hoàn toàn ngược với phương pháp tách. Song điều quan trọng ở đây là nguyên lý nối 2 vùng. Việc nối 2 vùng được thực hiện theo nguyên tắc sau : - Hai vùng phải đáp ứng tiêu chuẩn, thí dụ như cùng màu hay cùng mức xám. - Hai vùng phải kế cận nhau. Khái niệm kế cận: trong xử lý ảnh, người ta dùng khái niệm liên thông để xác định tính chất kế cận. Có hai khái niệm về liên thông là 4 liên thông và 8 liên thông. Với 4 liên thông một điểm ảnh I(x,y) sẽ có 4 kế cận theo 2 hướng x và y ; trong khi đó với 8 liên thông, điểm I(x,y) sẽ có 4 liên thông theo 2 hướng x, y và 4 liên thông khác theo hướng chéo 450
  58. 58 Dựa theo nguyên lý của phương pháp nối, ta có 2 thuật toán : - Thuật toán tô màu (Blob Coloring) : sử dụng khái niệm 4 liên thông, dùng một cửa sổ di chuyển trên ảnh để so sánh với tiêu chuẩn nối. - Thuật toán đệ quy cực bộ: sử dụng phương pháp tìm kiếm trong một cây để làm tăng kích thước vùng. c) Phƣơng pháp tổng hợp Hai phương pháp nối (hợp) và tách đều có nhược điểm. Phương pháp tách sẽ tạo nên một cấu trúc phân cấp và thiết lập mối quan hệ giữa các vùng. Tuy nhiên, nó thực hiện việc chia quá chi tiết. Phương pháp hợp cho phép làm giảm số miền liên thông xuống tối thiểu, nhưng cấu trúc hàng ngang dàn trải, không cho ta thấy r mối liên hệ giữa các miền. Vì nhược điểm này, người ta nghĩ đến phối hợp cả 2 phương pháp. Trước tiên, dung phương pháp tách để tạo nên cây tứ phân, phân đoạn theo hướng từ gốc đến lá. Tiếp theo, tiến hành duyệt cây theo chiều ngược lại và hợp các vùng có cùng tiêu chuẩn. Với phương pháp này ta thu được một cấu trúc ảnh với các miền liên thông có kích thước tối đa. Giải thuật tách hợp gồm một số bƣớc chính sau: 1. Kiể a iêu chuẩ đồ g hấ . a) Nếu không thỏa mãn tiêu chuẩn đồng nhất và số điểm trong một vùng nhiều hơn 1, tách vùng ảnh làm 4 miền (trên, dưới, phải, trái) bằng cách đệ quy. Nếu kết quả tách xong và không tách được nữa chuyển sang bước 2. b) Nếu tiêu chuẩn đồng nhất thỏa mãn thì tiến hành hợp vùng và cập nhật lại giá trị trung bình của vùng cho vùng này. 2. Hợ vù g Kiểm tra 4 lân cận như đã nêu trên. Có thể có nhiều vùng thỏa mãn. Khi đó, chọn vùng tối ưu nhất rồi tiến hành hợp. CÂU HỎI ÔN TẬP CHƢƠNG 7 1. Thế nào là vùng ảnh ? Mục đích của phân vùng ảnh là gì ? 2. Thế nào là phân vùng ảnh theo ngưỡng biên độ ? Cho ví dụ ? 3. Thế nào là phân vùng ảnh theo miền đồng nhất ? Cho ví dụ ?
  59. 59 4. Trình bày phương pháp tách cây tứ phân để phân vùng ảnh ? 5. Trình bày phương pháp hợp để phân vùng ảnh ?
  60. 60 MỘT SỐ ĐỀ THI MẪU
  61. 61 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN ĐỀ THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: 2010- 2011 1 Thời gian: 75 phút Câu 1: (2 điểm) (Chọn 4 câu bất kỳ) - Tại sao cần phải xử lý ảnh số. Ứng dụng của xử lý ảnh. Cho ví dụ? - Nêu cách biểu di n ảnh số trên máy tính? - Số hóa ảnh là gì? Tại sao cần phải số hóa ảnh? - Khái niệm về mặt nạ? Cách sử dụng mặt nạ trong xử lý ảnh? - Nêu khái niệm về mức xám (Gray – level). Cho ví dụ? - Nêu khái niệm về dải xám của một ảnh số? Cho ví dụ? Câu 2: (4 điểm) (Chọn 4 câu bất kỳ) - Trình bày hiểu biết của bạn về bộ lọc làm sắc nét trong miền không gian? - Trình bày hiểu biết của bạn về phép xử lý hình thái: đóng ảnh nhị phân. Ứng dụng trong thực tế? - Trình bày về bộ lọc Median Filters? - Nhận xét sự giống và khác nhau giữa 2 cách sử ly Histogram: Histogram Equalization và Histogram Matching? - Trình bày phương pháp mã hóa theo thuật toán Shanno-Fano? - Trình bày phương pháp mã hóa theo thuật toán Huffman? - Trình bày phép giãn ảnh. Cho ví dụ? Nhận xét kết quả? - Trình bày phép co ảnh. Cho ví dụ? Nhận xét kết quả? Câu 3: (2 điểm) Xử lý làm bằng histogram (Histogram Equalization) cho vùng ảnh sau: Cho ảnh số: 2 3 3 2 4 2 4 3 3 2 3 5 2 4 2 4 Gray Scale [0 7] Vẽ biểu đồ minh họa histogram trước và sau xử lý của vùng ảnh đã cho. Câu 4: (2 điểm) Cho vùng ảnh sau: Mặt nạ kích thước 3x3 2 3 5 3 1 1 1 5 9 3 4 1 8 1 9 1 2 9 1 1 1 3 3 12 8 Thực hiện làm mượt vùng ảnh đã cho với bộ lọc trung bình.
  62. 62 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN ĐỀ THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: 2010- 2011 2 Thời gian: 75 phút Câu 1: (2 điểm) (Chọn 4 câu bất kỳ) - Tại sao cần phải xử lý ảnh số. Ứng dụng của xử lý ảnh. Cho ví dụ? - Nêu cách biểu di n ảnh số trên máy tính? - Số hóa ảnh là gì? Tại sao cần phải số hóa ảnh? - Khái niệm về mặt nạ? Cách sử dụng mặt nạ trong xử lý ảnh? - Nêu khái niệm về mức xám (Gray – level). Cho ví dụ? - Nêu khái niệm về dải xám của một ảnh số? Cho ví dụ? Câu 2: (4 điểm) (Chọn 4 câu bất kỳ) - Trình bày hiểu biết của bạn về bộ lọc làm sắc nét trong miền không gian? - Trình bày hiểu biết của bạn về phép xử lý hình thái: đóng ảnh nhị phân. Ứng dụng trong thực tế? - Trình bày về bộ lọc Median Filters? - Nhận xét sự giống và khác nhau giữa 2 cách sử ly Histogram: Histogram Equalization và Histogram Matching? - Trình bày phương pháp mã hóa theo thuật toán Shanno-Fano? - Trình bày phương pháp mã hóa theo thuật toán Huffman? - Trình bày phép giãn ảnh. Cho ví dụ? Nhận xét kết quả? - Trình bày phép co ảnh. Cho ví dụ? Nhận xét kết quả? Câu 3: (2 điểm) Xử lý làm bằng histogram (Histogram Equalization) cho vùng ảnh sau: Cho ảnh số: 5 3 3 2 4 2 4 3 5 3 5 8 2 4 5 4 Gray Scale [0 9] Vẽ biểu đồ minh họa histogram trước và sau xử lý của vùng ảnh đã cho. Câu 4: (2 điểm) Cho vùng ảnh sau: Mặt nạ kích thước 3x3 2 3 5 5 1 1 1 5 5 3 8 1 -8 1 9 3 2 5 1 1 1 3 6 3 9 Thực hiện làm sắc nét vùng ảnh với bộ lọc đã cho (Laplacian Filter)
  63. 63 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN ĐỀ THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: 2010- 2011 3 Thời gian: 75 phút Câu 1: (2 điểm) (Chọn 4 câu bất kỳ) - Tại sao cần phải xử lý ảnh số. Ứng dụng của xử lý ảnh. Cho ví dụ? - Nêu cách biểu di n ảnh số trên máy tính? - Số hóa ảnh là gì? Tại sao cần phải số hóa ảnh? - Khái niệm về mặt nạ? Cách sử dụng mặt nạ trong xử lý ảnh? - Nêu khái niệm về mức xám (Gray – level). Cho ví dụ? - Nêu khái niệm về dải xám của một ảnh số? Cho ví dụ? Câu 2: (4 điểm) (Chọn 4 câu bất kỳ) - Trình bày hiểu biết của bạn về bộ lọc làm sắc nét trong miền không gian? - Trình bày hiểu biết của bạn về phép xử lý hình thái: đóng ảnh nhị phân. Ứng dụng trong thực tế? - Trình bày về bộ lọc Median Filters? - Nhận xét sự giống và khác nhau giữa 2 cách sử ly Histogram: Histogram Equalization và Histogram Matching? - Trình bày phương pháp mã hóa theo thuật toán Shanno-Fano? - Trình bày phương pháp mã hóa theo thuật toán Huffman? - Trình bày phép giãn ảnh. Cho ví dụ? Nhận xét kết quả? - Trình bày phép co ảnh. Cho ví dụ? Nhận xét kết quả? Câu 3: (2 điểm) Xử lý làm bằng histogram (Histogram Equalization) cho vùng ảnh sau: Cho ảnh số: 5 5 3 5 4 5 4 3 3 5 3 5 5 4 5 4 Gray Scale [0 8] Vẽ biểu đồ minh họa histogram trước và sau xử lý của vùng ảnh đã cho. Câu 4: (2 điểm) Cho vùng ảnh sau: Mặt nạ kích thước 3x3 2 3 5 5 1 2 1 5 9 3 8 2 4 2 9 1 2 4 1 2 1 3 3 12 9 Thực hiện làm mượt vùng ảnh đã cho với bộ lọc trung bình.
  64. 64 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN ĐỀ THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: 2010 - 2011 4 Thời gian: 75 phút Câu 1: (2 điểm) (Chọn 4 câu bất kỳ) - Tại sao cần phải xử lý ảnh số. Ứng dụng của xử lý ảnh. Cho ví dụ? - Nêu cách biểu di n ảnh số trên máy tính? - Số hóa ảnh là gì? Tại sao cần phải số hóa ảnh? - Khái niệm về mặt nạ? Cách sử dụng mặt nạ trong xử lý ảnh? - Nêu khái niệm về mức xám (Gray – level). Cho ví dụ? - Nêu khái niệm về dải xám của một ảnh số? Cho ví dụ? Câu 2: (4 điểm) (Chọn 4 câu bất kỳ) - Trình bày hiểu biết của bạn về bộ lọc làm sắc nét trong miền không gian? - Trình bày hiểu biết của bạn về phép xử lý hình thái: đóng ảnh nhị phân. Ứng dụng trong thực tế? - Trình bày về bộ lọc Median Filters? - Nhận xét sự giống và khác nhau giữa 2 cách sử ly Histogram: Histogram Equalization và Histogram Matching? - Trình bày phương pháp mã hóa theo thuật toán Shanno-Fano? - Trình bày phương pháp mã hóa theo thuật toán Huffman? - Trình bày phép giãn ảnh. Cho ví dụ? Nhận xét kết quả? - Trình bày phép co ảnh. Cho ví dụ? Nhận xét kết quả? Câu 3: (2 điểm) Xử lý làm bằng histogram (Histogram Equalization) cho vùng ảnh sau: Cho ảnh số: 3 3 3 4 4 3 4 3 3 5 3 5 3 4 5 5 Gray Scale [0 9] Vẽ biểu đồ minh họa histogram trước và sau xử lý của vùng ảnh đã cho. Câu 4: (2 điểm) Cho vùng ảnh sau: Mặt nạ kích thước 3x3 2 3 5 5 1 1 1 5 7 3 8 1 -8 1 9 9 9 4 1 1 1 3 3 6 9 Thực hiện làm sắc nét vùng ảnh với bộ lọc đã cho (Laplacian Filter)
  65. 65 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN ĐỀ THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: 2010 - 2011 5 Thời gian: 75 phút Câu 1: (2 điểm) (Chọn 4 câu bất kỳ) - Tại sao cần phải xử lý ảnh số. Ứng dụng của xử lý ảnh. Cho ví dụ? - Nêu cách biểu di n ảnh số trên máy tính? - Số hóa ảnh là gì? Tại sao cần phải số hóa ảnh? - Khái niệm về mặt nạ? Cách sử dụng mặt nạ trong xử lý ảnh? - Nêu khái niệm về mức xám (Gray – level). Cho ví dụ? - Nêu khái niệm về dải xám của một ảnh số? Cho ví dụ? Câu 2: (4 điểm) (Chọn 4 câu bất kỳ) - Trình bày hiểu biết của bạn về bộ lọc làm sắc nét trong miền không gian? - Trình bày hiểu biết của bạn về phép xử lý hình thái: đóng ảnh nhị phân. Ứng dụng trong thực tế? - Trình bày về bộ lọc Median Filters? - Nhận xét sự giống và khác nhau giữa 2 cách sử ly Histogram: Histogram Equalization và Histogram Matching? - Trình bày phương pháp mã hóa theo thuật toán Shanno-Fano? - Trình bày phương pháp mã hóa theo thuật toán Huffman? - Trình bày phép giãn ảnh. Cho ví dụ? Nhận xét kết quả? - Trình bày phép co ảnh. Cho ví dụ? Nhận xét kết quả? Câu 3: (2 điểm) Xử lý làm bằng histogram (Histogram Equalization) cho vùng ảnh sau:: Cho ảnh số: 5 3 3 5 4 5 4 3 3 3 3 5 4 4 5 4 Gray Scale [0 9] Vẽ biểu đồ minh họa histogram trước và sau xử lý của vùng ảnh đã cho. Câu 4: (2 điểm) Cho vùng ảnh sau: Mặt nạ kích thước 3x3 2 3 5 5 2 1 2 5 9 3 8 1 4 1 9 1 2 4 2 1 2 3 3 12 9 Thực hiện làm mượt vùng ảnh đã cho với bộ lọc trung bình.
  66. 66 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: x x x Thời gian: 75 phút Câu 1: (2 điểm) Trình bày hiểu biết của bạn về các phép biến đổi mức xám của ảnh: theo hàm logarit, theo hàm mũ? Câu 2: (2 điểm) - Trình bày hiểu biết của bạn về bộ lọc trung bình (bộ lọc làm mượt tuyến tính trong miền không gian)? - Trình bày hiểu biết của bạn về bộ cực đại (bộ lọc làm mượt phi tuyến trong miền không gian)? Câu 3: (2 điểm) a) Phép trừ ảnh thường được sử dụng trong các ứng dụng công nghiệp để phát hiện các thành phần còn thiếu trong sản xuất sản phẩm. Cách làm là lưu trữ một ảnh “chuẩn” của một sản phẩm được sản xuất đúng đắn; ảnh này sau đó được thực hiện phép trừ từ các ảnh của các sản phẩm khác được sản xuất. Trong trường hợp lý tưởng, kết quả của phép trừ sẽ bằng 0 nếu các sản phẩm được sản xuất đúng đắn. Kết quả đối với các sản phẩm bị thiếu thành phần sẽ khác không tại những vùng tương ứng với thành phần còn thiếu. The bạ , điều kiệ à cầ có để c ch à ày có hể hực hiệ được g hực hế? i i hích? b) Trong một ứng dụng, người ta sử dụng mặt nạ của bộ lọc trung bình để giảm nhi u trên ảnh ban đầu. Sau đó người ta sử dụng mặt nạ Laplacian để nâng cao chất lượng của các chi tiết nhỏ trong ảnh. ếu a đ gược hứ ự của c c ha c ày h kế qu có được giữ guyê hay kh g? i i hích? Câu 4: (2 điểm) Cho ảnh số: Mặt nạ kích thước 3x3: 0 2 6 4 1 2 1 3 5 1 7 1/16 2 4 2 1 7 3 6 1 2 1 2 6 5 4 Thực hiện làm mượt ảnh sử dụng bộ lọc trung bình có trọng số với mặt nạ trên. Câu 5: (2 điểm) Cho ảnh nhị phân: Phần tử cấu trúc: 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 Thực hiện phép đóng ảnh nhị phân với phần tử cấu trúc trên.
  67. 67 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: x x x Thời gian: 75 phút Câu 1: (2 điểm) Trình bày hiểu biết của bạn về các phép biến đổi: tạo âm bản ảnh, tăng độ tương phản ảnh? Câu 2: (2 điểm) a. Trình bày hiểu biết của bạn về bộ lọc trung vị (bộ lọc làm mượt phi tuyến trong miền không gian)? b. Trình bày hiểu biết của bạn về bộ lọc làm sắc nét trong miền không gian? Câu 3: (2 điểm) a. Phép trừ ảnh thường được sử dụng trong các ứng dụng công nghiệp để phát hiện các thành phần còn thiếu trong sản xuất sản phẩm. Cách làm là lưu trữ một ảnh “chuẩn” của một sản phẩm được sản xuất đúng đắn; ảnh này sau đó được thực hiện phép trừ từ các ảnh của các sản phẩm khác được sản xuất. Trong trường hợp lý tưởng, kết quả của phép trừ sẽ bằng 0 nếu các sản phẩm được sản xuất đúng đắn. Kết quả đối với các sản phẩm bị thiếu thành phần sẽ khác không tại những vùng tương ứng với thành phần còn thiếu. The bạ , điều kiệ à cầ có để c ch à ày có hể hực hiệ được g hực hế? i i hích? b. Trong một ứng dụng, người ta sử dụng mặt nạ của bộ lọc trung bình để giảm nhi u trên ảnh ban đầu. Sau đó người ta sử dụng mặt nạ Laplacian để nâng cao chất lượng của các chi tiết nhỏ trong ảnh. ếu a đ gược hứ ự của c c ha c ày h kế qu có được giữ guyê hay kh g? i i hích? Câu 4: (2 điểm) Cho ảnh số: Mặt nạ kích thước 3x3: 0 2 6 4 1 1 1 3 5 1 7 1/9 1 1 1 1 7 3 6 1 1 1 2 6 5 4 Thực hiện làm mượt ảnh sử dụng bộ lọc trung bình không có trọng số với mặt nạ trên. Câu 5: (2 điểm) Cho ảnh nhị phân: Phần tử cấu trúc: 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 Thực hiện phép mở ảnh nhị phân với phần tử cấu trúc trên.
  68. 68 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: x x x Thời gian: 75 phút Câu 1: (2 điểm) a) Trình bày hiểu biết của bạn về quá trình số hoá ảnh? b) Trình bày hiểu biết của bạn về các điểm lân cận của điểm ảnh? Câu 2: (2 điểm) a. Trình bày hiểu biết của bạn về phép xử lý hình thái: giãn ảnh nhị phân? b. Trình bày hiểu biết của bạn về kỹ thuật phân đoạn ảnh: phát hiện đường thẳng? Câu 3: (2 điểm) a. Phép trừ ảnh thường được sử dụng trong các ứng dụng công nghiệp để phát hiện các thành phần còn thiếu trong sản xuất sản phẩm. Cách làm là lưu trữ một ảnh “chuẩn” của một sản phẩm được sản xuất đúng đắn; ảnh này sau đó được thực hiện phép trừ từ các ảnh của các sản phẩm khác được sản xuất. Trong trường hợp lý tưởng, kết quả của phép trừ sẽ bằng 0 nếu các sản phẩm được sản xuất đúng đắn. Kết quả đối với các sản phẩm bị thiếu thành phần sẽ khác không tại những vùng tương ứng với thành phần còn thiếu. The bạ , điều kiệ à cầ có để c ch à ày có hể hực hiệ được g hực hế? i i hích? b. Trong một ứng dụng, người ta sử dụng mặt nạ của bộ lọc trung bình để giảm nhi u trên ảnh ban đầu. Sau đó người ta sử dụng mặt nạ Laplacian để nâng cao chất lượng của các chi tiết nhỏ trong ảnh. ếu a đ gược hứ ự của c c ha c ày h kế qu có được giữ guyê hay kh g? i i hích? Câu 4: (2 điểm) Cho ảnh số: Mặt nạ kích thước 3x3: 0 2 6 4 0 1 0 3 5 1 7 1/6 1 2 1 1 7 3 6 0 1 0 2 6 5 4 Thực hiện làm mượt ảnh sử dụng bộ lọc trung bình có trọng số với mặt nạ trên. Câu 5: (2 điểm) Cho ảnh nhị phân: Phần tử cấu trúc: 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 Thực hiện phép đóng ảnh nhị phân với phần tử cấu trúc trên.
  69. 69 Trƣờng Đại Học Hàng Hải Việt Nam Khoa Công nghệ Thông tin BỘ MÔN HỆ THỐNG THÔNG TIN THI KẾT THÚC HỌC PHẦN Tên học phần: NHẬN DẠNG & XỬ LÝ ẢNH Đề thi số: Ký duyệt đề: Năm học: x x x Thời gian: 75 phút Câu 1: (2 điểm) Trình bày hiểu biết của bạn về phép trừ ảnh và phép trung bình ảnh? Câu 2: (2 điểm) a. Trình bày hiểu biết của bạn về phép xử lý hình thái: đóng ảnh nhị phân? b. Trình bày hiểu biết của bạn về kỹ thuật phân đoạn ảnh: phát hiện điểm phân biệt Câu 3: (2 điểm) a. Phép trừ ảnh thường được sử dụng trong các ứng dụng công nghiệp để phát hiện các thành phần còn thiếu trong sản xuất sản phẩm. Cách làm là lưu trữ một ảnh “chuẩn” của một sản phẩm được sản xuất đúng đắn; ảnh này sau đó được thực hiện phép trừ từ các ảnh của các sản phẩm khác được sản xuất. Trong trường hợp lý tưởng, kết quả của phép trừ sẽ bằng 0 nếu các sản phẩm được sản xuất đúng đắn. Kết quả đối với các sản phẩm bị thiếu thành phần sẽ khác không tại những vùng tương ứng với thành phần còn thiếu. The bạ , điều kiệ à cầ có để c ch à ày có hể hực hiệ được g hực hế? i i hích? b. Trong một ứng dụng, người ta sử dụng mặt nạ của bộ lọc trung bình để giảm nhi u trên ảnh ban đầu. Sau đó người ta sử dụng mặt nạ Laplacian để nâng cao chất lượng của các chi tiết nhỏ trong ảnh. ếu a đ gược hứ ự của c c ha c ày h kế qu có được giữ guyê hay kh g? i i hích? Câu 4: (2 điểm) Cho ảnh số: Mặt nạ kích thước 3x3: 0 2 6 4 1 1 1 3 5 1 7 1 1 1 1 7 3 6 1 1 1 2 6 5 4 Thực hiện làm mượt ảnh sử dụng bộ lọc trung vị với mặt nạ trên. Câu 5: (2 điểm) Cho ảnh nhị phân: Phần tử cấu trúc: 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 Thực hiện phép mở ảnh nhị phân với phần tử cấu trúc trên.