›
›

Bài giảng Xủ lý ảnh - Trần Quang Đức

pdf 209 trang hapham 90
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xủ lý ảnh - Trần Quang Đức", để 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_tran_quang_duc.pdf

Nội dung text: Bài giảng Xủ lý ảnh - Trần Quang Đức

  1. XỬ LÝ ẢNH Trần Quang Đức
  2. Thông tin giảng viên • Thông tin liên hệ ▫ Phòng B1-801 (2 pm - 3 pm – Thứ Ba Hàng Tuần) ▫ Bộ môn Truyền Thông và Mạng Máy Tính ▫ Viện Công Nghệ Thông Tin và Truyền Thông ▫ Đại học Bách Khoa Hà Nội ▫ E-mail: ductq@soict.hust.edu.vn ▫ Điện thoại: (+84) (4) 38682596
  3. Nội dung • Chương 1: Giới thiệu chung • Chương 2: Hình thành và biểu diễn ảnh • Chương 3: Thu nhận và số hóa ảnh • Chương 4: Cơ sở lý thuyết xử lý ảnh • Chương 5: Cải thiện và nâng cấp ảnh • Chương 6: Phát hiện và tách biên ảnh • Chương 7: Phân vùng ảnh • Chương 8: Xử lý ảnh nhị phân • Chương 9: Mã hóa và nén ảnh
  4. Tài liệu tham khảo • R.C. Gonzalez, and R. E. Woods, “Digital Image Processing,” vol. 2, Prentice Hall, 2002. • A. K. Jain, “Fundamentals of Digital Image Processing,” vol. 3, Englewood Cliffs, Prentice Hall, 1989. • L. M. Bá, N. T. Thủy, “Nhập môn xử lý ảnh,” Trường Đại học Bách Khoa Hà Nội, 2008. • R.C. Gonzalez, R. E. Woods, “Digital Image Processing using Matlab,”
  5. GIỚI THIỆU CHUNG Trần Quang Đức
  6. Các khái niệm • Ảnh: Thông tin về vật thể hay quang cảnh được chiếu sáng mà con người quan sát và cảm nhận bằng mắt và hệ thần kinh thị giác. • Đối tượng của xử lý ảnh là xử lý các ảnh tự nhiên, ảnh chụp, dữ liệu ảnh có nguồn gốc từ tín hiệu ảnh đặc trưng bởi biên độ và dải tần số. Có sự phân biệt giữa xử lý ảnh với đồ họa. • Hệ thống xử lý ảnh thu nhận khung cảnh hoặc ảnh ở đầu vào, thực hiện các phép xử lý để tạo ra một ảnh ở đầu ra thỏa mãn các yêu cầu về cảm thụ hoặc trích rút các đặc trưng của ảnh.
  7. Ảnh tĩnh và chuỗi ảnh • Ảnh tĩnh (Still Image): Biểu diễn bởi hàm độ chói của các biễn toạn độ trong mặt phẳng ảnh I(x,y). • Chuỗi ảnh (Sequence of Images): Hàm độ chói của các biến tọa độ mặt phẳng và biến thời gian I(x,y,t). x x t y y
  8. Ảnh tĩnh • Ảnh nhị phân: 1 bit/pixel • Ảnh xám: 8 bits/pixel • Ảnh màu: 16-24 bit/pixel • RGB, YUV, HSL, YCbCr Pixel (RGB)
  9. Chuỗi ảnh • Video: Chuỗi các ảnh (khung hình), quan hệ thời gian giữa các khung hình biểu diễn ảnh động. • Tấn số và Độ phân giải ▫ NTSC (525 dòng, 30 khung hình/giây) ▫ PAL (625 dòng, 25 khung hình/giây) ▫ SECAM (625 dòng, 25 khung hình/giây) ▫ Phim (24 khung hình/giây) ▫ HDTV (16:9, 720 dòng, 60 khung hình/giây) ▫ SVGA: 72 khung hình/giây, 1024x720 pixel
  10. Các ví dụ về ảnh số
  11. Hệ thống xử lý ảnh Khung cảnh, Miêu tả ảnh, Đối tượng Tín hiệu Dữ liệu Đối tượng ảnh Ảnh quang học Thiết bị ảnh ảnh Xử lý Đặc trưng ảnh cảm biến Số hóa ảnh phân tích Camera) Ảnh liên Ảnh số ảnh tục Nén, lưu trữ và truyền ảnh
  12. Các vấn đề của xử lý ảnh • Thu nhận ảnh, chụp ảnh và số hóa ảnh ▫ Hệ thống chụp ảnh và tín hiệu ảnh ▫ Hệ thống số hóa ảnh: Lấy mẫu,Lượng tử hóa • Phân tích ảnh và thị giác máy tính ▫ Cải thiện nâng cấp ảnh, sửa lỗi, khôi phục ảnh ▫ Phân tách đặc trưng: tách biên, phân vùng ảnh ▫ Biểu diễn và xử lý đặc trưng hình dạng đối tượng ảnh ▫ Nhận dạng đối tượng ảnh, phân tích cảnh và hiểu cảnh • Mã hóa, nén ảnh ▫ Các phương pháp nén và các chuẩn nén
  13. Ứng dụng của xử lý ảnh • Thông tin ảnh, truyền thông ảnh • Xử lý ảnh vệ tinh, viễn thám • Thiên văn, nghiên cứu không gian, vũ trụ • Người máy, tự động hóa • Máy thông minh, thị giác máy nhân tạo • Sinh học, y học • Giám sát kiểm soát, Quân sự
  14. Ứng dụng của xử lý chuỗi ảnh • Nén video, truyền thông video, truyền hình số • Giám sát theo dõi phát hiện chuyển động • Điểu khiển lưu lượng chuyển động • Người máy chuyển động • Quốc phòng an ninh • Y học, hóa học
  15. HÌNH THÀNH VÀ BIỂU DIỄN ẢNH Trần Quang Đức
  16. Ánh sáng và sóng điện từ Bước sóng λ Gamma-Ray X-Ray Ultraviolet Visible Infrared Microwaves Radio 10-3 nm 1nm 1000nm 1000 m
  17. Hệ thống thị giác
  18. Hệ thống thị giác • Tế bào que ▫ Có từ 75-150 triệu ▫ Rất nhạy cảm với ánh sáng ▫ Cảm nhận trên dải rộng ▫ Cung cấp khả năng nhìn đêm ▫ Cảm nhận độ chói ▫ Độ phân giải cao • Tế bào nón ▫ Có từ 6-7 triệu ▫ Tập trung chủ yếu tại điểm vàng tại trung tâm võng mạc ▫ Cảm nhận trên dài hẹp ▫ Ba loại tế bào cảm nhận màu xanh lam, xanh lục và đỏ
  19. Cảm nhận và biểu diễn màu • Độ chói (Radiance) ▫ Tổng năng lượng của chùm tia từ nguồn • Độ rọi (Luminance) ▫ Độ đo năng lượng ánh sáng thu thập được từ nguồn sáng ▫ Biến thiên theo khoảng cách từ nguồn sáng, bước sóng ▫ Không phụ thuộc vào môi trường ∞ L(x, y) = ∫ f (x, y, λ)V(λ)dλ 0 ▫ f(x,y,λ) Phân bố ánh sáng trong không gian ▫ V(λ) Hàm hiệu suất độ rọi tương đối của hệ thống thị giác
  20. Màu sắc • Cảm nhận màu sắc phụ thuộc vào phổ của ánh sáng. Ánh sáng nhìn thầy với dải phổ rất hẹp. Ánh sáng với tất cả các thành phần phổ nhìn thấy có năng lượng bằng nhau sẽ được cảm nhận là ánh sáng trắng. • Một màu có thể tạo nên bằng cách trộn 3 màu cơ bản tương đương với 3 dạng tế bào cảm nhận màu sắc (Đỏ, Lục, Lam). Phân biệt màu sắc dựa trên độ sáng, sắc độ và độ bão hòa.
  21. Độ sáng, sắc độ và độ bão hòa • Độ sáng (Brightness) ▫ Thuộc tính chủ quan, đặc trưng cho khả năng cảm nhận độ rọi ▫ Phụ thuộc vào độ rọi của môi trường xung quanh • Đặc trưng màu (Chrominance) ▫ Sắc độ (Hue) là thuộc tính liên quan đến bước sóng chủ yếu trong hỗn hợp của các bước sóng ánh sáng. Sắc độ đặc trưng cho màu sắc chủ đạo được cảm nhận. ▫ Độ bão hòa (Saturation) đặc trưng cho độ thuần khiết tương đối. Độ bão hòa phụ thuộc vào độ rộng của phổ ánh sáng và thể hiện lượng màu trắng được trộn với sắc độ. ▫ Sắc độ và độ bão hòa gọi là đặc trưng màu.
  22. Các mô hình màu HSV YCbCr (Y=0.5) RGB CMYK
  23. Các mô hình màu • Red, Green, Blue tại 3 trục nhận giá trị [0 255]. Mô hình RGB có thể biểu diễn hơn 16 triệu màu. Trong đó, R (255, 0, 0), G (0, 255, 0) và B (0, 0, 255). • CMYK (Cyan, Magenta, Yellow, Black) với C = 255-R, M = 255-G, và Y = 255-B. • YCbCr Y = 16+219(0.299R+0.587G+0.114B)/255 Cb = 128+224(-0.169R-0.331G+0.5B)/255 Cr = 128+224(0.5R-0.419G-0.081B)/255
  24. Biểu diễn ảnh số 9 7 1 1 1 2 2 1 Ảnh là một mảng hai chiều gồm M hàng và N cột với f(x,y) là giá trị 8 9 9 7 1 1 1 1 mức xám tại tọa độ (x,y). 7 5 195 7 2 3 1 1 8 6 5 6 3 1 2 3 N4(p), ND(p), N8(p) 9 7 6 9 1 2 2 1 Quan hệ 4-lân cận (4-adjacency) 5 8 7 9 1 1 2 1 Quan hệ 8-lân cận (8-adjacency) 8 9 8 9 1 2 1 2 Quan hệ m-lân cận (m-adjacency) 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1
  25. Độ sai khác 1 N −1 MSE E(| X Xˆ |2 ) • L2-norm error = ∑ i − i N i=0 1 N −1 • L -norm error MAD E(| X Xˆ |) 1 = ∑ i − i N i=0 • L -norm error ˆ ∞ MaxError = max E(| X i − X i |) i M 2 • PSNR PSNR =10 log 10 MSE
  26. THU NHẬN VÀ SỐ HÓA ẢNH Trần Quang Đức
  27. Hệ thống số hóa ảnh Thiết bị Lấy mẫu Lượng tử hóa cảm biến Thông lượng Tín hiệu Số liệu ánh sáng ảnh ảnh Thiết bị cảm biến: Charge Coupled Device >4000x4000 phần tử. Lấy mẫu được xây dựng dựa trên tỷ số Nyquist Lượng tử hóa: Lượng tử hóa Lloyd-Max
  28. Lấy mẫu • Ảnh với dải giới hạn (Band limited images): Một hàm f(x,y) gọi là giải giới hạn nếu khai triên Fourier F(u,v) của nó là 0 bên ngoài miền bao, cụ thể F(u,v) = 0 nếu |u|>u0 và |v|>v0. • Tỷ số Nyquist: Tần số lấy mẫu theo x và y tương đương hoặc lớn hơn 2 lần dải giới hạn u0 và v0 Δx 1 1 Δy ≥ 2u0 ≥ 2v Δx Δy 0
  29. Hiện tượng răng cưa
  30. Lượng tử hóa Lượng tử hóa đều Lượng tử hóa Lloyd-Max 011 tk: Mức quyết định 010 rk: Mức dựng lại 001 000 100 101 110 111
  31. Lượng tử hóa Lloyd-Max • u là một biến thực ngẫu nhiên với hàm mật độ liên tục p(u). Giá trị tk và rk của bộ lượng tử hóa L mức được xác định sao cho sai số trung bình bình phương là nhỏ nhất. tL 2 2 ε = Ε[u − ri ] = ∫ [u − ri ] p(u)du t1 L−1 ti+1 2 ε = ∑ ∫ [u − ri ] p(u)du i=1 ti
  32. Lượng tử hóa Lloyd-Max • Để tính rk, ta thực hiện đạo hàm cấp một theo tk và rk, và cho giá trị đạo hàm bằng 0. tk+1 2 2 2 u r p(u)du 0 (tk − rk−1) p(tk )− (tk − rk ) p(tk ) = 0 ∫ [ − k ] = tk • Từ đó, ta có tk+1 ∫ up(u)du rk + rk−1 tk tk = rk = 2 tk+1 ∫ p(u)du tk
  33. Lượng tử hóa đều • Lượng tử hóa đều là lý tưởng với hàm mật độ liên tục đều. Mức quyết định và mức khôi phục được tính như sau # 1 % a ≤ u ≤ b rk + rk−1 tk+1 + tk p(u) = $ b − a tk = rk = % 2 2 & 0 otherwise • Sai số lượng tử q q = rk − rk−1 = tk+1 − tk 12
  34. Thay đổi kích thước ảnh • Giảm kích thước ảnh ▫ Giảm số lượng mẫu có thể dẫn đến hiện tượng răng cưa nếu tần số lấy mẫu không thỏa mãn điều kiện của tỷ số Nyquist. ▫ Sử dụng bộ lọc thông thấp để loại bỏ những thành phần tần số cao (thành phần có tần số không thỏa mãn điều kiện về tỷ số Nyquist). Tuy nhiên sử dụng bộ lọc thông thấp có thể dẫn đến mờ ảnh. • Tăng kích thước ảnh ▫ Tăng kích thước ảnh bằng các phương pháp nội suy như Nearest Neighbor, Bilinear hoặc Bicubic.
  35. Tăng kích thước ảnh • Nearest Neighbor • Bilinear b F[m, n'] = (1− a)I[m, n]+ aI[m, n +1] a O[m', n'] = (1− b)F[m, n']+ bF[m +1, n'] • Bicubic F[m, n'] = −a(1− a)2 I[m, n −1]+ (1− 2a2 + a3 )I[m, n] +a(1+ a − a2 )I(m, n +1)− a2 (1− a)I[m, n + 2] O[m', n'] = −b(1− b)2 F[m −1, n']+ (1− 2b2 + b3 )F[m, n'] +b(1+ b − b2 )F(m +1, n')− b2 (1− b)F[m + 2, n']
  36. CƠ SỞ LÝ THUYẾT XỬ LÝ ẢNH Trần Quang Đức
  37. Tổng quan • Toán tử tuyến tính • Tích chập (2D Convolution) • Biến đổi Fourier (Fourier Transform) • Biến đổi KL (Karhunen-Loeve Transform) • Biến đổi Wavelet (Wavelet Transform)
  38. Toán tử tuyến tính • Xử lý điểm ảnh bằng ánh xạ biến đổi g(m, n) = T( f (m, n)), m ∈ [1, M ]vàn ∈ [1, N] • Hệ thống được gọi là tuyến tính khi và chỉ khi tổ hợp tuyến tính của hai tín hiệu đầu vào f1(m,n) và f2(m,n) tao nên tổ hợp tuyến tính của tín hiệu đầu ra g1(m,n) và g2(m,n). T(α1 f1(m, n)+α2 f2 (m, n)) = α1T( f1(m, n))+α2T( f2 (m, n)) = α1g1(m, n)+α2g2 (m, n)
  39. Tích chập • Tích chập - Trường hợp liên tục g(x, y) = f (x, y)*h(x, y) +∞ +∞ f ( , )h(x , y )d d = ∫ ∫ τ1 τ 2 −τ1 −τ 2 τ1 τ 2 τ1 =−∞ τ 2 =−∞ • Tích chập - Trường hợp rời rạc g[x, y] = f [x, y]*h[x, y] +∞ +∞ = ∑ ∑ f [n1, n2 ]h[x − n1, y − n2 ] n1=−∞ n2 =−∞
  40. Tích chập • Tính giao hoán f (x, y)* g(x, y) = g(x, y)* f (x, y) • Tính kết hợp f (x, y)*[g(x, y)*h(x, y)] = [ f (x, y)* g(x, y)]*h(x, y) • Tính phân phối f (x, y)*[g(x, y)+ h(x, y)] = [ f (x, y)* g(x, y)] + [ f (x, y)*h(x, y)]
  41. Biến đổi Fourier • Biến đổi Fourier rời rạc cho tín hiệu một chiều 1 M −1 M −1 F(u) = ∑ f (x)e−2πjux/ M f (x) = ∑ F(u)e2πjux/ M M x=0 u=0 e jθ = cosθ + jsinθ • Biến đổi Fourier rời rạc cho tín hiệu hai chiều 1 M −1N−1 F(u,v) = ∑∑ f (x, y)e−2πj(ux/ M +vy / N ) MN x=0 y=0 M −1N −1 f (x, y) = ∑∑ F(u,v)e2πj(ux/ M +vy / N ) u=0 v=0
  42. Biến đổi Fourier • Nếu f(x,y) chỉ chứa giá trị thực, thì phổ của f(x,y) sẽ đối xứng qua gốc tọa độ F(u, v) = F *(−u,−v) | F(u, v) |=| F(−u,−v) | • F(u,v) là hàm tuần hoàn với chu kỳ M và N F(u, v) = F(u + M, v) = F(u, v + N) = F(u + M, v + N) • Liên hệ với tích chập f (x, y)* g(x, y) ⇔ F(u,v)G(u,v) f (x, y)g(x, y) ⇔ F(u,v)*G(u,v)
  43. Biến đổi Fourier 2 2 1/2 abs[F(u)] = "!R (u)+ I (u)$# 2 P(u) = F(u) [ ] -M/2 M/2 M −1 " I(u) % φ(u) = tan $ ' #R(u)& abs[F(u − M / 2)] x ℑ$# f (x)(−1) &% -M/2 M/2 M
  44. Biến đổi Fourier (a) (b) (c) (a) Ảnh gốc f(x,y) (b) Biển đổi Fourier của f(x,y), F(u,v) (c) Biển đổi Fourier của (-1)x+yf(x,y), F(u-M/2,v-N/2) F(u − M / 2,v − N / 2) = ℑ[f (x, y)(−1)x+ y ]
  45. Biến đổi KL • Biến đổi KL được sử dụng trong các hệ thống nhận dạng hoặc nén ảnh. Nó cho phép giảm lượng thông tin dư thừa trong ảnh thông qua quá trình giảm tính tương quan giữa các điểm ảnh nằm lân cận nhau. Cho một khối ảnh gồm N điểm ảnh. Gọi x là véc tơ chứa giá trị của các điểm ảnh trên ! x % # 1 # # x2 # x = " & mx = Ε[x] # # # x # $ N '
  46. Biến đổi KL • Từ đó, ta có ma trận hiệp phương sai # T % # T % # T % Cx = Ε$(x − mx )(x − mx ) & = Ε$xx &− Ε$mxmx & • Giá trị ci,j của Cx thể hiện mối tương quan giữa hai điểm ảnh xi T và xj. Gọi U là ma trận của biến đổi tuyến tính y=U (x-mx) sao cho ma trận hiệp phương sai Cy là ma trận chéo. • Giả sử ui là véc tơ cơ sở của không gian biến đổi. Các phần tử của y có thể xác định như sau T yi = ui (x − mx )
  47. Biến đổi KL • Để giảm hoàn toàn tính tương quan giữa các điểm ảnh trong không gian biến đổi, U phải là ma trận trực giao UT U = I = UUT • Từ đó, có thể chứng minh được năng lượng của khối ảnh được bảo toàn trước và sau khi thực hiện biến đổi 2 y = yT y T T = (x − mx ) UU (x − mx ) 2 = x − mx
  48. Biến đổi KL • Do ma trận hiệp phương sai Cy là ma trận chéo ! $ λ1 0 0 # T % # T % # & Cy = Ε$(y − my )(y − my ) & = Ε$yy & # 0 λ 0 & 2 T T Cy = # % # & = Ε$U (x − mx )(x − mx ) U& # & 0 0 UTC U "# λN %& = x • Có thể thấy rằng CxU = UCy ⇒ Cxui = λiui
  49. Biến đổi KL • Trong biểu thức trên, ui là véc tơ riêng của Cx và λi là giá trị riêng tương ứng của ui. Véc tơ x có thể khôi phục dựa trên phép biến đổi T y = U (x − mx ) ⇒ x = Uy + mx • Quá trình nén ảnh chỉ lưu K (K<<N) phần tử đầu tiên của y. Véc tơ x ban đầu có thể được xấp xỉ như sau x! = Uy! + mx • Với T y! = [y1, y2, , yK , 0, , 0]
  50. Biến đổi KL • Trung bình bình phương của sai số được xác định bởi N $ 1 ' 1 2 (x x! )2 $ x x! ' Ε& ∑ i − i ) = Ε% − ( % N i=1 ( N 1 2 = Ε$ Uy − Uy! ' N % ( N 1 2 1 $ y y! ' 2 = Ε% − ( = ∑ λi N N i=K+1
  51. Biến đổi KL • Năng lượng của khối ảnh trước và sau khi biến đổi được bảo toàn. • Ma trận hiệp phương sai Cy là ma trận chéo. Do vậy các điểm ảnh trong không gian biến đổi không tương quan với nhau. Lượng thông tin dư thừa trong khối ảnh ban đầu bị giảm một cách tối đa. • Nén ảnh dựa trên biến đổi KL có tỷ lệ nén cao. Tuy nhiên việc tính toán véc tơ riêng và giá trị riêng tương ứng rất phức tạp với kích thước khối ảnh lớn. Biến đổi KL cũng phụ thuộc vào đặc trưng riêng của từng ảnh.
  52. Biến đổi Wavelet • Biến đổi Wavelet (Wavelet Transform) được sử dụng trong xử lý đa phân giải và nén ảnh JPEG2000. Biến đổi Wavelet dựa trên quá trình mã hóa dải tần con (sub-band coding). Low-pass Low-pass Analysis 2 2 Synthesis Filter Filter x(n) x!(n) High-pass High-pass Analysis 2 2 Synthesis Filter Filter h0(n): Low-pass Analysis Filter g0(n): Low-pass Synthesis Filter h1(n): High-pass Analysis Filter g1(n): High-pass Synthesis Filter
  53. Biến đổi Wavelet • Định nghĩa biến đổi Z: +∞ X(z) = ∑x(n)z−n −∞ • Giảm mẫu 2 lần trên miền thời gian 1 x (n) = x(2n) ⇔ X (z) = #X(z1/2 )+ X(−z1/2 )% down down 2$ & • Tăng mẫu 2 lần trên miền thời gian ! # x(n / 2) n = 0, 2, 4, 2 xup (n) = " ⇔ Xup (z) = X(z ) $# 0 Otherwise
  54. Biến đổi Wavelet • Giảm mẫu và tăng mẫu trên miên thời gian: 1 Xˆ(z) = [X(z)+ X(−z)] 2 • Quá trình mã hóa băng tần con có thể được minh họa như sau ˆ 1 X(z) = G0 (z)[H0 (z)X(z)+ H0 (−z)X(−z)] 2 1 + G1(z)[H1(z)X(z)+ H1(−z)X(−z)] 2 ˆ 1 X(z) = [H0 (z)G0 (z)+ H1(z)G1(z)] X(z) 2 1 + [H0 (−z)G0 (z)+ H1(−z)G1(z)] X(−z) 2
  55. Biến đổi Wavelet • Từ đó, ta có H0 (−z)G0 (z)+ H1(−z)G1(z) = 0 H0 (z)G0 (z)+ H1(z)G1(z) = 2 • Biểu diễn dưới dạng nhận ma trận ! H (z) H (−z) # ! G (z) G (z) #& 0 0 ' = ! 2 0 # " 0 1 $ H (z) H ( z) " $ "& 1 1 − $' • Quadrature mirror filters (QMF) H1(z) = H0 (−z) G0 (z) = H0 (z) G1(z) = −H0 (−z)
  56. CẢI THIỆN VÀ NÂNG CẤP ẢNH Trần Quang Đức
  57. Tổng quan Cải thiện và nâng cấp ảnh Toán tử Toán tử trên Toán tử trên điểm ảnh miền không gian trên miền tần số Ảnh âm bản Lọc trung bình Lọc thông thấp Biến đổi sử dụng hàm log Lọc trung bình trọng số Lọc thông cao Biến đổi sử dụng hàm mũ Lọc trung vị Lọc High-boost Dãn và co độ tương phản Lọc cực đại Laplace trên miền tần số Cắt theo mức Lọc cực tiểu Trích chọn bit Lọc sắc nét Cân bằng Histogram Lọc High-boost Histogram đặc trưng Trừ ảnh Trung bình ảnh
  58. TOÁN TỬ TRÊN ĐIỂM ẢNH Trần Quang Đức
  59. Phác họa nội dung Cải thiện và nâng cấp ảnh Toán tử Toán tử trên Toán tử trên điểm ảnh miền không gian trên miền tần số Ảnh âm bản Lọc trung bình Lọc thông thấp Biến đổi sử dụng hàm log Lọc trung bình trọng số Lọc thông cao Biến đổi sử dụng hàm mũ Lọc trung vị Lọc High-boost Dãn và co độ tương phản Lọc cực đại Laplace trên miền tần số Cắt theo mức Lọc cực tiểu Trích chọn bit Lọc sắc nét Cân bằng Histogram Lọc High-boost Histogram đặc trưng Trừ ảnh Trung bình ảnh
  60. Định nghĩa Histogram • Histogram (Lược đồ mức xám) biểu diễn bằng một hàm rời rạc h(rk)=nk, trong đó rk là mức xám thứ k và nk là số lượng điểm ảnh có mức xám rk. Thông thường histogram được tiêu chuẩn hóa bằng cách chia h(rk) cho n, với n=Σnk. 1000 900 800 700 600 500 400 300 200 100 0 0 50 100 150 200 250
  61. Ảnh âm bản g(m,n) = L −1− f (m,n)
  62. Biến đổi sử dụng hàm log (a) (b) (c) (a) Ảnh gốc f(x,y) (b) Biển đổi Fourier của f(x,y), F(u,v) (c) Biển đổi sử dụng hàm log (c=1) g(m,n) = clog[1+ f (m,n)] G(u,v) = clog[1+ F(u,v) ]
  63. Biến đổi sử dụng hàm mũ L-1 Gamma Correction γ=1/2.2 CRT Gamma γ=2.2 L-1 g(m,n) = cf (m,n) γ g(m,n) = cf (m,n)1/γ
  64. Dãn và co độ tương phản # % αr r 1, T(r) thực hiễn dãn độ tương phản.
  65. Dãn và co độ tương phản 1600 1400 1200 1000 800 600 400 200 0 0 50 100 150 200 250 1600 1400 1200 1000 800 600 400 200 0 0 50 100 150 200 250 a b Ảnh (b) thu được sau khi thực hiện tăng cường độ tương phản ảnh (a). Histogram của ảnh (a) và (b). Ảnh (a) có mức xám trong dải [74,224], ảnh (b) có mức xám trong dải [0,255].
  66. Cắt theo mức L-1 L-1 T(r) sH T(r) sH sL a b L-1 a b L-1 $" s a ≤ r ≤ b $" s a ≤ r ≤ b T(r) = # H T(r) = # H s Otherwise %$ L %$ r Otherwise
  67. Cắt theo mức a b c a) Ảnh gốc b) Cắt theo mức không nền với a=100 và b=200 c) Cặt theo mức có nền với a=100 và b=200
  68. Trích chọn bit b=7 Mỗi điểm ảnh được biểu diễn b=6 bằng 8 mặt phẳng bit từ 0 đến 7, xếp chồng lên nhau theo b=5 thứ tự từ cao xuống thấp. b=0 Những mặt phẳng bit phía trên tập trung phần lớn dữ liệu ý nghĩa của ảnh. Dữ liệu chi tiết ảnh tập trung ở những mặt phẳng bit phía dưới. Phân tích sử dụng phương pháp trích chọn bit cho phép xác định những mặt phẳng bit quan trọng và số lượng bit yêu cầu của quá trình lượng tử hóa.
  69. Trích chọn bit Minh họa 8 mặt phẳng bit. (a), (b), (c), (d), (e), (f), a b c d (g), (h) tương đương mặt phẳng bit từ 7 đến 0 e f g h
  70. Cân bằng Histogram • Giả sử r được chuẩn hóa 0≤r≤1, s=T(r) với T(r) là hàm một biến đơn điệu tăng và 0≤T(r) ≤1. Điều kiện trên đảm bảo sự -1 tồn tại của ánh xạ ngược của r=T (s) và 0≤s≤1. Nếu ps và pr là hàm mật độ 1 xác suất của hai biến s và r. Do số lượng điểm ảnh là không đổi, nên p (s)ds=p (r)dr. Giả s r s =T(r ) sử k k r s = T(r) = p (w)dw ∫ 0 r rk 1
  71. Cân bằng Histogram • Như vậy ds=pr(r)dr. Từ đó, ps(s)=1 với 0≤s≤1 và là hàm phân bố đều. Cân bằng histogram cho phép tạo ra histogram mới có phân bố đều. k k nk nj pr (rk ) = sk = T(rk ) = ∑ pr (rj ) = ∑ n j=1 j=1 n • Trên thực tế, giá trị mức xám mới được xác định như sau " % sk − min{sk } sk = round$ (L −1)' # max{sk }− min{sk } &
  72. Cân bằng Histogram 1000 a b 900 800 c d 700 (a) Ảnh gốc 600 500 (b) Histogram của ảnh gốc 400 (c) Ảnh với cân bằng Histogram 300 (d) Histogram của ảnh (c) 200 100 0 0 50 100 150 200 250 1200 1000 800 600 400 200 0 0 50 100 150 200 250
  73. Histogram đặc trưng • Phương pháp histogram đặc trưng được áp dụng để tạo ảnh đầu ra với histogram có hình dạng cho trước. Giả sử pr và pz là hàm mật độ xác suất của ảnh đầu vào và ảnh đầu ra. Gọi T(r) và G(z) là phép biến đổi sao cho r z s = T(r) = p (w)dw G(z) = p (t)dt = s ∫ 0 r ∫ 0 z • T(r) thực hiện cân bằng histogram của ảnh đầu vào, trong khi G(z) có thể xác định dựa trên pz. Từ đó, ta có s = T(r) = G(z) ⇒ z = G−1(T(r))
  74. Histogram đặc trưng 1) Xây dựng histogram của ảnh đầu vào 2) Thực hiện cân bằng histogram của ảnh đầu vào 3) Xác định G(z) dựa trên pz 4) Tìm giá trị zk nhỏ nhất ứng với sk sao cho [G(zk )− sk ] ≥ 0 5) Mỗi điểm ảnh có mức xám rk, tìm sk tương ứng (bước (2)). Từ sk có thể tìm zk dựa trên kết quả của bước (4).
  75. Trừ ảnh g(x, y) = f (x, y)− h(x, y) a b c d (a) f(x,y) (b) h(x,y) (c,d) g(x,y)=f(x,y)-h(x,y)
  76. Trung bình ảnh f (x, y) = g(x, y)+η(x, y) Trung bình ảnh được sử dụng giảm nhiễu bằng cách tăng tỷ lệ SNR. Ảnh (b) thu được K dựa trên trung bình ảnh. Lưu ý: nhiễu là 1 một quá trình ngẫu nhiên. g(x, y) = ∑gi (x, y) K i=1 " $ Ε#g(x, y)% = f (x, y) 1 σ = σ g(x,y) K η(x,y) a b
  77. TOÁN TỬ TRÊN MIỀN KHÔNG GIAN Trần Quang Đức
  78. Phác họa nội dung Cải thiện và nâng cấp ảnh Toán tử Toán tử trên Toán tử trên điểm ảnh miền không gian trên miền tần số Ảnh âm bản Lọc trung bình Lọc thông thấp Biến đổi sử dụng hàm log Lọc trung bình trọng số Lọc thông cao Biến đổi sử dụng hàm mũ Lọc trung vị Lọc High-boost Dãn và co độ tương phản Lọc cực đại Laplace trên miền tần số Cắt theo mức Lọc cực tiểu Trích chọn bit Lọc sắc nét Cân bằng Histogram Lọc High-boost Histogram đặc trưng Trừ ảnh Trung bình ảnh
  79. Nhiễu • Ảnh thường bị biến dạng do nhiễu ngẫu nhiên. Nhiễu xuất hiện trong quá trình thu nhận ảnh hoặc truyền tin. Các yếu tố môi trường, ví dụ điều kiện ánh sáng yếu, nhiệt độ của thiết bị cảm biến cũng ảnh hưởng đến sự xuất hiện của nhiễu. • Nhiễu có thể phụ thuộc hoặc độc lập với nội dung ảnh và thường được biểu diễn bằng các thuộc tính thống kê. Xử lý nhiễu phụ thuộc vào nội dung ảnh thường có độ phức tạp cao (ngoài chương trình). • Nhiễu có thể là nhiễu trắng, nhiễu Gauss, nhiễu đều, nhiễu xung hoặc nhiễu muối tiêu.
  80. Nhiễu lượng tử hóa • Nhiễu lượng tử hóa được tạo ra trong quá trình lượng tử hóa (sử dụng chuỗi nhị phân để xấp xỉ giá trị biên độ của tín hiệu thu nhận). Nhiễu lượng tử có thể xấp xỉ bởi phân bố đều nên còn được gọi là nhiễu đều. # 1 % a ≤ z ≤ b p(z) = $ b − a % & 0 Otherwise • Nhiễu lượng tử có đặc trưng sau 2 a + b 2 (b − a) µ = σ = 2 12
  81. Nhiễu trắng • Nhiễu trắng là nhiễu có phổ năng lượng không đổi. Nếu nhiễu có phổ năng lượng nhiều hơn ở một vài tấn số, nhiễu được gọi là nhiễu màu. Hàm tương quan của nhiễu trắng là Dirac’s delta. Do đó, nhiễu trắng không tương quan ở hai mẫu bất kỳ. imnoise(I,’localvar’, V)
  82. Nhiễu Gauss • Nhiễu Gauss là mô hình phổ biến để xấp xỉ nhiễu trong nhiều ứng dụng khác nhau. Mật độ phân bố xác suất của nhiễu là hàm Gauss, được đặc trưng bởi giá trị trung bình µ và phương sai σ2. 1 2 2 p(z) = e−(z−µ) /2σ 2πσ [µ −σ,µ +σ ] [µ − 2σ,µ + 2σ ] imnoise(I,’gaussian’,M,V)
  83. Nhiễu Poisson • Trong quá trình thu nhận, nếu số lượng lớn hạt photon tập trung vào một điểm, chúng sẽ tạo ra nhiễu tại điểm đó. Nhiễu được đặc trưng bởi hàm mật độ phân bố xác suất Poisson, nên được gọi là nhiễu Poisson. imnoise(I,’poisson’)
  84. Nhiễu muối tiêu • Nhiễu xung đặc trưng bởi một điểm ảnh có giá trị mức xám khác biệt lớn so với những điểm lân cận. Xung của nhiễu có thể âm hoặc dương. Xung nhiễu âm đại diện cho điểm ảnh đen (pepper), trong khi xung nhiễu dương đại diện cho điểm ảnh trắng (salt). Nhiễu muốn tiêu xuất hiệu khi ảnh bị bão hòa bởi nhiễu xung. imnoise(I,’salt & pepper’, 0.02)
  85. Lọc trung bình • Lọc trung bình ⎡1 1 1⎤ 1 ⎢1 1 1⎥ 9 ⎢ ⎥ ⎣⎢1 1 1⎦⎥ • Lọc thông thấp ⎡1 2 1⎤ ⎡1 b 1⎤ 1 1 ⎢2 4 2⎥ ⎢b b2 b⎥ 16 ⎢ ⎥ (b + 2)2 ⎢ ⎥ ⎣⎢1 2 1⎦⎥ ⎣⎢1 b 1⎦⎥
  86. Lọc trung bình a b c (a) Ảnh bị nhiễu muối tiêu (b) Lọc trung bình (c) Lọc thông thấp (Lọc trung bình trọng số)
  87. Lọc trung vị, cực tiểu và cực đại gˆ(x, y) = median{ f (m,n)} m,n∈W gˆ(x, y) = min{ f (m,n)} 8 89 8 8 m,n∈W 8 7 8 8 gˆ(x, y) = max{ f (m,n)} m,n∈W 7 7 8 8 0 0 0 8 89 8 8 7 8 8 8 8 8 W: 3x3, 5x5, 7x7 0 0 0 7 8 8 8 8 89 min max
  88. Minh họa lọc trung vị a b c (a) Ảnh bị nhiễu muối tiêu (b) Lọc trung vị cửa số 3x3 (c) Lọc trung vị cửa số 7x7
  89. Lọc sắc nét Đạo hàm bậc nhất Đạo hàm bậc hai ∂f ∂2 f = f (x +1)− f (x) 2 = f (x +1)+ f (x −1)− 2 f (x) ∂x ∂x 5 5 4 3 2 1 0 0 0 6 0 0 0 1 3 1 0 0 0 0 7 7 7 7 Đạo hàm bậc nhất 0 -1 -1 -1 -1 -1 0 0 6 -6 0 0 0 1 2 -2 -1 0 0 0 7 0 0 0 Đạo hàm bậc hai -1 0 0 0 0 1 0 0 6 -12 6 0 0 1 1 -4 1 1 0 0 7 -7 0 0
  90. Lọc sắc nét 2 2 2 ∂ f ∂ f ∇ f = + ∂x2 ∂y2 = f (x +1, y)+ f (x −1, y)+ f (x, y +1)+ f (x, y −1)− 4 f (x, y) " 0 1 0 % " 0 −1 0 % " −1 −1 −1 % " 1 1 1 % $ ' $ ' $ ' $ ' $ 1 −4 1 ' $ −1 4 −1 ' $ −1 8 −1 ' $ 1 −8 1 ' $ 0 1 0 ' $ 0 1 0 ' $ ' $ ' # & # − & # −1 −1 −1 & # 1 1 1 &
  91. Lọc sắc nét # 2 % f (x, y)− ∇ f (x, y) If center coefficient is negative g(x, y) = $ 2 &% f (x, y)+ ∇ f (x, y) If center coefficient is positive " 0 −1 0 % $ ' $ −1 5 −1 ' $ 0 1 0 ' # − & " −1 −1 −1 % $ ' $ −1 9 −1 ' $ ' # −1 −1 −1 &
  92. Lọc High-boost • Nguyên tắc cơ bản fhb (x, y) = Af (x, y)− f (x, y) = (A −1) f (x, y)− fs (x, y) " 0 −1 0 % $ ' $ −1 A + 4 −1 ' $ 0 1 0 ' # − & " −1 −1 −1 % $ ' $ −1 A +8 −1 ' $ ' # −1 −1 −1 &
  93. TOÁN TỬ TRÊN MIỀN TẦN SỐ Trần Quang Đức
  94. Phác họa nội dung Cải thiện và nâng cấp ảnh Toán tử Toán tử trên Toán tử trên điểm ảnh miền không gian trên miền tần số Ảnh âm bản Lọc trung bình Lọc thông thấp Biến đổi sử dụng hàm log Lọc trung bình trọng số Lọc thông cao Biến đổi sử dụng hàm mũ Lọc trung vị Lọc High-boost Dãn và co độ tương phản Lọc cực đại Laplace trên miền tần số Cắt theo mức Lọc cực tiểu Trích chọn bit Lọc sắc nét Cân bằng Histogram Lọc High-boost Histogram đặc trưng Trừ ảnh Trung bình ảnh
  95. Lọc trên miền tần số • Những thành phần tần số thấp đại diện cho dữ liệu ảnh tại những vùng trơn mịn, trong khi những thành phần tần số cao đại diện cho dữ liệu chi tiết ảnh như biên ảnh và nhiễu. • Lọc thông thấp chỉ cho những thành phần tần số thấp đi qua và loại bỏ những thành phần tần số cao. Vì vậy, ảnh sau khi lọc sẽ trơn mịn nhưng không được sắc nét bằng ảnh đầu vào. • Lọc thông cao chỉ cho những thành phần tần số cao đi qua và loại bỏ những thành phần tấn số thấp. Do đó, ảnh sau khi lọc sẽ có dải mức xám không đa dạng tại những vùng trơn mịn, nhưng sắc nét hơn so với ảnh đầu vào.
  96. Hệ thống lọc trên miền tần số Biến Đổi Biến Đổi Tiền Xử Lý H(u,v) Hậu Xử Lý Fourier Fourier Ngược f (x, y) g(x, y) • Liên hệ với tích chập f (x, y)* g(x, y) ⇔ F(u,v)G(u,v) f (x, y)g(x, y) ⇔ F(u,v)*G(u,v)
  97. Liên hệ với tích chập ⎡1 1 1⎤ 1 ⎢1 1 1⎥ 9 ⎢ ⎥ ⎣⎢1 1 1⎦⎥
  98. Lọc thông thấp lý tưởng $" 1 if D(u, v) ≤ D H(u,v) H(u, v) = # 0 0 if D(u, v) D 1 %$ > 0 " 2 2 $1/2 D(u, v) = #(u − M / 2) + (v − N / 2) % Do D(u) M −1 N −1 P P(u,v) T = ∑∑ u=0 v=0 " % α =100$∑∑P(u, v) / PT ' #u=0 v=0 &
  99. Lọc thông thấp lý tưởng a b (a) Ảnh gốc (b) Lọc thông thấp lý tưởng (c) Lọc thông thấp lý tưởng với D0=5, ,230 c
  100. Lọc thông thấp Butterworth a b c (a) Ảnh gốc 1 H(u, v) = (b) Lọc thông thấp lý tưởng với D0=5 2n 1+ (D(u, v) / D0 ) (c) Lọc thông thấp Butterworth với D0=5
  101. Lọc thông thấp Gauss a b c (a) Lọc thông thấp lý tưởng với D =15 0 2 −D (u,v)/ 2D0 (b) Lọc thông thấp Butterworth với D0=15 H(u,v) = e (c) Lọc thông thấp Gauss với D0=15
  102. Lọc thông cao " $ H hp (u,v) =1− Hlp (u,v) F(u, v)Hhp (u, v) = F(u, v)#1− Hlp (u, v)% F(u, v)Hhp (u, v) = F(u, v)− F(u, v)Hlp (u, v) fhp (x, y) = f (x, y)− flp (x, y) ⎡ 0 −1 0 ⎤ ⎢ 1 5 1⎥ ⎢− − ⎥ ⎣⎢ 0 −1 0 ⎦⎥
  103. Lọc thông cao • Lọc thông cao lý tưởng $" 0 if D(u, v) ≤ D H(u, v) = # 0 1 if D(u, v) D %$ > 0 • Lọc thông cao Butterworth 1 H(u, v) = 2n 1+ (D0 / D(u, v)) • Lọc thông cao Gauss 2 H(u, v) =1− e−D (u,v)/2D0
  104. Lọc thông cao (a) Lọc thông cao Gauss với D0=15 (b) Lọc thông cao Gauss với D0=30 (c) Lọc thông cao Gauss với D0=80
  105. Lọc High-boost fhb (x, y) = Af (x, y)− flp (x, y) " 0 −1 0 % $ ' f (x, y) (A 1) f (x, y) f (x, y) f (x, y) hb = − + − lp $ −1 A + 4 −1 ' $ 0 1 0 ' # − & fhb (x, y) = (A −1) f (x, y)+ fhp (x, y) Với A=1, ảnh đầu ra tương đương với ảnh sau lọc sắc nén. Nếu giá trị của A tăng, vai trò của fhp giảm dần. Giá trị A đủ lớn, fhb sẽ tương đương với ảnh đầu vào nhân với một hằng số. Từ đó ta có fhb (x, y) = (A −1) f (x, y)+ hhp (x, y)* f (x, y) Hhb (u, v) = (A −1)+ Hhp (u, v)
  106. Laplace trên miền tần số • Biến đổi Fourier của đạo hàm bậc hai 2 2 #∂ f (x, y) ∂ f (x, y)& 2 2 ℑ% + ( = ( ju) F(u, v)+ ( jv) F(u, v) $ ∂x2 ∂y2 ' • Toán tử Laplace trong miền tần số ∇2 f (x, y) ⇔ −[(u − M / 2)2 + (v − N / 2)2 ]F(u, v) • Ảnh sau lọc sắc nét g(x, y) = ℑ−1 {[1+ (u − M / 2)2 + (v − N / 2)2 ]F(u, v)}
  107. KHÔI PHỤC ẢNH Trần Quang Đức
  108. Hệ thống khôi phục ảnh g(x, y) f (x, y) h(x,y) + w(x,y) fˆ(x, y) η(x, y) G(u, v) = F(u, v)H(u, v)+ N(u, v) Fˆ(u, v) = G(u, v)W (u, v) Trong hệ thống trên, ta có f(x,y) là ảnh đầu vào, fˆ ( x , y ) là ảnh khôi phục tương ứng, h(x,y) là hàm suy hao và η(x,y) là nhiễu, xuất hiện trong quá trình thu nhận hoặc truyền ảnh. Khôi phục ảnh thông qua ước đoán hàm suy hao h(x,y) còn có tên khác là giải chập mù.
  109. Ước đoán hàm suy hao • Ước đoán dựa trên quan sát ảnh ước đoán hàm suy hao bằng thông tin thu nhận trực tiếp từ ảnh. Ví dụ, để khôi phục ảnh bị nhòe và nhiễu, người ta tiến hành quan sát một vùng ảnh có cấu trúc đơn giản với giả thiết vùng ảnh sau khi khôi phục có nhiễu không đáng kể. • Ước đoán dựa trên thực nghiệm sử dụng thiết bị tương tự như thiết bị thu nhận ảnh. Thực nghiệm được lặp lại nhiều lần với các thông số khác nhau cho đến khi ảnh khôi phục gần tương tự với ảnh đầu vào. • Ước đoán dựa trên mô hình hóa sử dụng mô hình toán học để ước đoán hàm suy hao.
  110. Minh họa về mô hình toán học • Ảnh bị nhỏe do chuyển động tương đối của vật thể so với thiết bị cảm ứng trong quá trình thu nhận. Giả thiết T là thời gian mở và đóng cửa trập, x0(t) và y0(t) là các thành phần chuyển động theo phương x và y. Với f(x,y) là ảnh đầu vào, ta có T g(x, y) = ∫ f (x − x0 (t), y − y0 (t))dt 0 • Thực hiện biến đổi Fourier biểu thức trên, T G(u, v) = ∫ F(u, v)e− j2π[ux0 (t)+vy0 (t)] dt 0
  111. Minh họa về mô hình toán học • Từ đó, hàm suy hao có thể viết như sau T H(u, v) = ∫ e− j2π[ux0 (t)+vy0 (t)] dt 0 • Do chuyển động đều y0(t)=bt/T và x0(t)=at/T , nên T H(u, v) = sin[π(ua + vb)]e jπ (ua+vb) π(ua + vb) • Ta có phương pháp lọc ngược với ảnh khôi phục có dạng G(u, v) Fˆ(u, v) = H(u, v)
  112. Lọc Weiner • Lọc Weiner tìm W(u,v) sao cho ảnh khôi phục có sai số trung bình bình phương nhỏ nhất so với ảnh đầu vào # ˆ %2 ε = Ε{$F(u, v)− F(u, v)& } 2 = Ε{[F(u, v)−W (u, v)(F(u, v)H(u, v)+ N(u, v))] } • Giả thiết nhiễu độc lập với tín hiệu, ta có 2 ε = [1−W(u, v)H(u, v)][1−W(u, v)H(u, v)] * Ε{[F(u, v)] } 2 +W(u, v)W *(u, v)Ε{[N(u, v)] }
  113. Lọc Weiner • Thực hiện đạo hàm và cho giá trị đạo hàm bằng 0, ta có 2 H * (u, v) 1 H(u, v) W (u, v) = 2 = 2 2 N(u, v) H(u, v) 2 N(u, v) H(u, v) + H(u, v) + F(u, v) F(u, v) • Chú ý rằng khi không có nhiễu, 2 N(u, v) 1 1 = = 0 ⇒ W (u, v) = F(u, v) SNR H(u, v)
  114. Minh họa lọc Weiner (a) Ảnh gốc (b) Ảnh bị nhòe (c) Khôi phục ảnh (b) (d) Ảnh bị nhòe và nhiễu (e) Khôi phục ảnh (d) (không nhiễu) (f) Khôi phục ảnh (d) (có nhiễu) a b c d e f
  115. PHÁT HIỆN VÀ TÁCH BIÊN ẢNH Trần Quang Đức
  116. Tổng quan • Biên ảnh là tập hợp của những điểm tại đó giá trị mức xám thay đổi cục bộ đột ngột • Sự biến thiên của một hàm liên tục được xác định thông qua đạo hàm. • Ảnh số là một hàm rời rạc với biến là tọa độ trong mặt phẳng ảnh. Sự biến thiên vì vậy phải xác định thông qua các đạo hàm rời rạc, gồm đạo hàm bậc nhất (Gradient) và đạo hàm bậc hai (Laplace).
  117. Đạo hàm bậc nhất • Gradient theo hai hướng ∂f ∂f G = Gy = x ∂x ∂y • Biên độ của gradient 1/2 ) 2 2 , #∂f & #∂f & # ∂f ∂f & mag(∇f ) = +% ( +% ( . mag(∇f ) = % + ( *+$∂x ' $∂y ' -. $ ∂x ∂y ' • Tính gradient rời rac Gx = f (x +1, y)− f (x, y) Gy = f (x, y +1)− f (x, y)
  118. Đạo hàm bậc nhất " 1 0 % " 0 1 % Toán tử Robert Gx = $ ' Gy = $ ' # 0 −1 & # −1 0 & " % " −1 0 1 % −1 −1 −1 $ ' $ ' G = 0 0 0 Toán tử Prewitt Gx = $ −1 0 1 ' y $ ' $ ' $ −1 0 1 ' # 1 1 1 & # & " −1 0 1 % " −1 −2 −1 % $ ' $ ' Toán tử Sobel Gx = $ −2 0 2 ' Gy = $ 0 0 0 ' $ −1 0 1 ' $ 1 2 1 ' # & # &
  119. Đạo hàm bậc nhất (a) Ảnh gốc (b) Toàn tử Robert (c) Toán tử Prewitt (d) Toán tử Sobel
  120. Đạo hàm bậc nhất • Toán tử Robert nhạy cảm với nhiễu và những biến thiên nhỏ ở biên vì sử dụng ít điểm lân cận để xấp xỉ đạo hàm bậc nhất. Toán tử Robert đáp ứng cực đại với biên tạo góc 45o. • Toán tử Prewitt và Sobel đáp ứng cực đại với biên ngang hoặc thẳng đứng. Bên cạnh tách biên toán tử Prewitt và Sobel còn có thể làm trơn nhiễu. " −1 0 1 % " 1 % $ ' $ ' G 1 0 1 1 " 1 0 1 % x = $ − ' = $ '# − & $ ' $ 1 ' # −1 0 1 & # &
  121. Đạo hàm bậc nhất • Toán tử la bàn (Kirsch) ▫ Ước lượng gradient của 8 hướng theo mặt nạ tổng chập ▫ Kết quả của tổng chập cực đại chỉ hướng của gradient " 5 5 5 % " −3 5 5 % " −3 −3 5 % " −3 −3 −3 % $ ' $ ' $ ' $ ' $ −3 0 −3 ' $ −3 0 5 ' $ −3 0 5 ' $ −3 0 5 ' $ ' $ ' $ ' $ ' # −3 −3 −3 & # −3 −3 −3 & # −3 −3 5 & # −3 5 5 & " −3 −3 −3 % " −3 −3 −3 % " 5 −3 −3 % " 5 5 −3 % $ ' $ ' $ ' $ ' $ −3 0 −3 ' $ 5 0 −3 ' $ 5 0 −3 ' $ 5 0 −3 ' $ ' $ ' $ ' $ ' # 5 5 5 & # 5 5 −3 & # 5 −3 −3 & # −3 −3 −3 &
  122. Đạo hàm bậc nhất (a) Ảnh gốc (b) Toàn tử Kirsch −1 "Gy % α = tan $ ' Toán tử Kirsch có thể tìm trực tiếp hướng của Gradient #Gx &
  123. Đạo hàm bậc hai 2 2 2 2 ∂ f ∂ f ∂ f ∇ f = + = f (x −1, y)+ f (x +1, y)− 2 f (x, y) ∂x2 ∂y2 ∂x2 ∂2 f = f (x, y −1)+ f (x, y +1)− 2 f (x, y) ∂y2 " 0 1 0 % " 0 −1 0 % " −1 −1 −1 % " 1 1 1 % $ ' $ ' $ ' $ ' $ 1 −4 1 ' $ −1 4 −1 ' $ −1 8 −1 ' $ 1 −8 1 ' $ 0 1 0 ' $ 0 1 0 ' $ ' $ ' # & # − & # −1 −1 −1 & # 1 1 1 &
  124. Đạo hàm bậc hai Toán tử Laplace nhạy cảm với nhiễu và không hỗ trợ tìm được hướng của đường biên. Toán tử Laplace được sử dụng để xác định vị trí của một điểm ảnh thuộc vùng tối hoặc vùng sáng của biên.
  125. Laplace of Gaussian r2 − 2 h(r) = −e 2σ với r2=x2+y2 và σ được gọi là độ lệch chuẩn r2 2 2 − 2 #r −σ & 2 ∇ h(r) = −% (e 2σ $ σ 4 ' ⎡ 0 0 −1 0 0 ⎤ ⎢ 0 1 2 1 0 ⎥ ⎢ − − − ⎥ ⎢−1 − 2 16 − 2 −1⎥ ⎢ ⎥ ⎢ 0 −1 − 2 −1 0 ⎥ ⎣⎢ 0 0 −1 0 0 ⎦⎥
  126. Phương pháp Canny 1) Lọc làm trơn nhiễu với mặt nạ Gauss (5x5) ! 2 4 5 4 2 $ # & r2 − # 4 9 12 9 4 & 2 1 h(r) = −e 2σ H = # 5 12 15 12 5 & 159 # 4 9 12 9 4 & # & "# 2 4 5 4 2 %& 2) Tính biên độ và hướng của gradient −1 "Gy % G = Gx + Gy α = tan $ ' #Gx &
  127. Phương pháp Canny 3) Xóa điểm biên không phải cực đại theo hướng gradient 4) Phân loại điểm biên (rõ, mờ, rất mờ) dựa theo ngưỡng 5) Kết nối các điểm biên mờ thuộc lân cận điểm biên rõ 2 3 5 4 6 2 3 5 4 6 2 3 5 4 6 6 5 18 18 16 6 5 18 18 16 6 5 18 18 16 5 11 4 3 2 5 11 4 3 2 5 11 4 3 2 16 4 4 4 3 16 4 4 4 3 16 4 4 4 3 5 4 3 2 12 5 4 3 2 12 5 4 3 2 12
  128. Phương pháp Canny a b c (a) Phương pháp Canny (b) Laplace of Gaussian (c) Toán tử Sobel
  129. PHÂN VÙNG ẢNH Trần Quang Đức
  130. Tổng quan • Một vùng ảnh là tập hợp của các điểm ảnh có cùng chung một hoặc nhiều thuộc tính về đối tượng trong ảnh. • Phân vùng ảnh là một trong những nhiệm vụ khó khăn nhất của xử lý ảnh. Trong một số trường hợp, người ta sử dụng các thiết bị đặc biệt, ví dụ máy chụp ảnh hồng ngoại để tăng hiệu quả của quá trình phân vùng. • Quá trình phân vùng dựa trên hai tính không liên tục và tính đồng nhất của điểm ảnh. Các phương pháp gồm phân vùng dựa trên biên ảnh, phân vùng dựa trên ngưỡng và phân vùng dựa trên miền ảnh.
  131. Phân vùng dựa trên biên ảnh • Biên ảnh là tập hợp của những điểm ảnh nằm trên ranh giới giữa hai vùng ảnh. Biên ảnh được xác định dựa trên các phương pháp đạo hàm bậc nhất (gradient) và đạo hàm bậc hai (laplace). • Tìm biên thông qua đạo hàm thường tạo ra biên không khép. Nhiễu cũng tạo ra các điểm biên giả, gây khó khăn cho quá trình phân vùng ảnh. • Kết nối các điểm biên có thể dựa trên các phương pháp xử lý cục bộ hoặc xử lý toàn cục sử dụng biến đổi Hough.
  132. Phương pháp xử lý cục bộ • Cho điểm biên (x0,y0), điểm ảnh (x,y) thuộc lân cận của (x0,y0) được kết nối với (x0,y0) nếu ∇f (x, y)− ∇f (x0, y0 ) ≤ E α(x, y)−α(x0, y0 ) ≤ A • Với E và A là các giá trị ngưỡng. Quá trình trên được lặp lại với tất cả các điểm ảnh. Các lân cận được xem xét thuộc mặt nạ kích thước 3x3 hoặc 5x5. • Kỹ thuật xử lý cục bộ không tính đến lịch sử tìm kiếm nên có thể tạo ra các điểm biên giả.
  133. Phương pháp xử lý toàn cục • Kỹ thuật xử lý toàn cục tìm đường thẳng xấp xỉ đi qua n điểm ảnh. Giả sử đường thẳng đi qua điểm ảnh (xi,yi) có dạng yi=axi+b, ta có thể viết b=yi-axi. Từ đó, đường thẳng được tìm kiếm trên mặt phẳng tham số ab. b bmin bmax amin (xi,yi) y=ax+b a amax (xjyj)
  134. Phân vùng dựa trên ngưỡng 1) Chọn giá trị khởi tạo T0 2) Chia vùng ảnh dựa theo T0 (G1 và G2) 3) Tính µ1 và µ2 tương ứng của G1 và G2 4) Tính ngưỡng mới T1 = (µ1 + µ2)/2 5) Lặp lại các bước 2-4 đến khi Ti-Ti-1 T g(x, y) = # %$ 0 If f (x, y) ≤ T T
  135. Phân vùng dựa trên hàm xác suất p(z) = P1 p1(z)+ P2 p2 (z) P1 + P2 =1 T T E1(T) = p2 (z)dz E2 (T) = p2 (z)dz ∫ ∫ T −∞ −∞ 2 (z−µi ) − 2 1 2σ i E(T) = P2E1(T)+ P1E2 (T) pi (z) = e 2πσ i 2 " % ∂E µ1 + µ2 σ P2 = 0 ⇒ P2 p1(T) = P1 p2 (T) T = + ln$ ' ∂T 2 µ1 − µ2 # P1 &
  136. Phương pháp cải thiện Histogram • Nhận xét: Ngưỡng thường được chọn dựa trên lược đồ mức xám. Do đó, cải thiện lược đồ mức xám có thể tăng hiệu quả của quá trình phân vùng. • Cải thiện lược đồ mức xám bằng cách chỉ xem xét những điểm ảnh nằm lân cận biên để giảm sự chênh lệch số lượng điểm ảnh giữa các vùng. • Nhắc lại: Đạo hàm bấc nhất (gradient) cho phép xác định biên ảnh trong khi đạo hàm bậc hai (laplace) xem xét một điểm ảnh thuộc vùng tối hay vùng sáng của biên.
  137. Phương pháp cải thiện Histogram $ 0 If ∇f < T & s(x, y) = % + If ∇f ≥ T and ∇2 f ≥ 0 & If f T and 2 f 0 '& − ∇ ≥ ∇ < • Điểm ảnh không thuộc biên ảnh hoặc lân cận của biên ảnh được ký hiệu 0. Điểm ảnh lân cận của biên ảnh thuộc vùng tối được ký hiệu +. Điểm ảnh lân cận của biên ảnh thuộc vùng sáng được ký hiệu -. • Biên ảnh tại những điểm có bước chuyển (-,+) hoặc (+,-).
  138. Phân vùng dựa trên miền ảnh • Vùng ảnh là tập hợp của các điểm ảnh có cùng chung một hoặc nhiều thuộc tính về đối tượng trong ảnh • Phân vùng ảnh là quá trình chia tập các điểm ảnh thành những tập con Ri thỏa mãn các điều kiện sau X = ∪Ri Ri ∩ R j = ∅ ∀i, j,i ≠ j P(Ri ) = TRUE P(Ri ∪ R j ) = FALSE Ri ≠ ∅
  139. Phương pháp gia tăng vùng • Phương pháp gia tăng vùng xét lân cận của những điểm ảnh hạt giống. Nếu chúng thỏa mãn điều kiện về độ tương đồng thì hợp lại thành một vùng. 9 9 1 1 1 2 2 1 f (x, y)− f (x0, y0 ) ≤ 2 8 9 9 8 1 1 1 1 7 9 9 8 1 2 1 1 Sử dụng quan hệ 4-lân cận 8 9 9 6 1 1 2 1 9 8 8 9 1 2 2 1 8 8 8 9 1 1 2 1 8 9 8 9 1 2 1 2
  140. Phương pháp chia và hợp vùng • Phương pháp chia và hợp vùng sử dụng phương pháp phân tách cây tứ phân để chia ảnh thành vùng nhỏ. Những vùng nhỏ lân cận được hợp lại nếu chúng thỏa mãn điều kiện về độ tương đồng. R R1 R2 R3 R4 R21 R22 R23 R24
  141. XỬ LÝ ĐA PHÂN GIẢI Trần Quang Đức
  142. Biển diễn đa phân giải Biển diễn đa phân giải biểu diễn chuỗi ảnh có độ phân giải giảm dần theo quy luật dựa trên cấu trúc tháp. Mức 0 1x1 Biểu diễn đa phân giải được ứng dụng trong Mức 1 phân vùng ảnh và nén ảnh. 2x2 Ảnh tại mức j kích thước 2jx2j, 0≤j≤J Dung lương lưu trữ J+1 mức Mức J 1 1 4 N 2 (1+ + + ) ≤ N 2 4 4 J 3 NxN
  143. Biểu diễn đa phân giải Analysis 2 Mức j-1 Filter 2 Synthesis Filter Mức j +- Mức j
  144. Biến đổi Haar • Biến đổi Haar có tính đối xứng và phân tách T=HFH. Để tạo ra H, ta định nghĩa số nguyên k, k=2p+q-1,với 0≤p≤n-1, q=0 hoặc 1 nếu p=0 và 1≤q≤2p nếu p≠0. 1 h (z) = h (z) = , z ∈ [0,1] 0 00 N $ 2 p/2 (q 1) / 2 p z (q 0, 5) / 2 p & − ≤ < − 1 & h (z) = % −2 p/2 (q − 0, 5) / 2 p ≤ z < q / 2 p pq N & 0 Otherwise, z ∈ [0,1] '&
  145. Biến đổi Haar Nếu N=4, giá trị k, p, q như sau k p q 1 " 1 1 % 0 0 0 H2 = $ ' 2 # 1 −1 & 1 0 1 2 1 1 3 1 2 " 1 1 1 1 % $ ' 1 $ 1 1 −1 −1 ' H ~ Bộ lọc phân tích QMF H = 2 4 4 $ 2 − 2 0 0 ' $ ' G (z) H (z) G (z) H ( z) 0 = 0 1 = − 0 − #$ 0 0 2 − 2 &'
  146. Biến đổi Wavelet rời rạc Giá trị của một hàm rời rạc có thể biểu diễn thành chuỗi các hệ số 1 1 Wϕ ( j0, k) = f [n]ϕ j ,k [n] W ( j, k) = f n ψ j,k n ∑ 0 ψ ∑ [ ] [ ] M n M n ∞ 1 1 f [n] = Wϕ ( j0, k)ϕ j ,k [n] + Wψ ( j, k)ψ j,k [n] M ∑ 0 M ∑∑ k j= j0 k M=2J, x=0,1,2, , M-1; j=0,1,2, , J-1 và k=0,1,2, ,2j-1. Ví dụ: f(0)=1, f(1)=4, f(2)=-3, f(3)=0
  147. Biến đổi Wavelet nhanh Trong biến đổi Wavelet nhanh, các hệ số có thể xác định như sau Wϕ ( j, k) = hϕ (−n)∗Wϕ ( j +1, n) Wψ ( j, k) = hψ (−n)∗Wψ ( j +1, n) với n=2k (k≥0) hφ(-n) 2 Wφ(j,n) W(j+1,n) h (-n) 2 W (j,n) ψ ψ
  148. Minh họa Ví dụ: f(0)=1, f(1)=4, f(2)=-3, f(3)=0 hφ(-n) 2 1 h (-n) 2 φ hψ(-n) 2 4 f [n] = [1, 4,−3, 0] h (-n) " 3 2, 3 2$ ψ 2 #− − %
  149. Biến đổi Wavelet nhanh 2 chiều hφ(-m) 2 LL hφ(-n) 2 hψ(-m) 2 LH f(m,n) HL hφ(-m) 2 hψ(-n) 2 HH hψ(-m) 2
  150. XỬ LÝ ẢNH NHỊ PHÂN Trần Quang Đức
  151. Khái niệm • Ảnh nhị phân gồm những điểm ảnh có giá trị 0 và 1. Giá trị 0 biểu diễn điểm ảnh thuộc đối tượng ảnh (điểm ảnh đen). Giá trị 1 biểu diễn điểm ảnh thuộc nền (điểm ảnh trắng). $" 1 If f (x, y) ≥ T g(x, y) = # %$ 0 If f (x, y) < T
  152. Lý thuyết tập hợp 2 • A là một tập hợp thuộc không gian Z . Một phần tử a=(a1,a2) thuộc A được ký hiệu a ∈ A • Tương tự, nếu phần tử a không thuộc A, ta ký hiệu a ∉ A • Nếu A không chứa một phần tử nào, A là tập rỗng A = ∅
  153. Lý thuyết tập hợp A là tập con của B A ⊆ B Hợp của hai tập hợp A và B C = A∪ B Giao của hai tập hợp A và B C = A∩ B Phần bù của tập hợp A c A = {w | w ∉ A} Hiệu của hai tập hợp A và B A − B = {w | w ∈ A, w ∉ B} Phản chiếu của tập hợp A ˆ A = {w | w = −a,∀a ∈ A} Dịch tập hợp A với z=(z ,z ) 1 2 (A)z = {c | c = a + z,∀a ∈ A}
  154. Lý thuyết tập hợp A B A∪ B A∩ B z1 z2 A − B (A)z Ac
  155. Toán tử Logic A B A AND B A XOR B NOT A A OR B [NOT A] AND B
  156. Toán tử hình thái • Toán tử hình thái là công cụ toán học để xử lý hình dạng trong ảnh. Toán tử hình thái sử dụng hướng tiếp cận lý thuyết tập hợp. • Toán tử hình thái bao gồm phép co (erosion), phép dãn (dilation), phép mở (opening), phép đóng (closing). • Toán tử hình thái được ứng dụng trong tách biên ảnh, lấp đầy vùng ảnh, tạo kết nỗi giữa các vùng ảnh hoặc làm xương ảnh.
  157. Phép dãn và phép co Phép dãn Phép co ⌢ A ⊕ B = {z | (B ) ∩ A ≠ ∅} A!B = {z | (B) ⊆ A} z z A ⊕ B A!B
  158. Phép mở Phép mở xóa bỏ những đoạn mảnh, loại bỏ nhiễu nhưng làm tăng số đoạn đứt gãy A ! B = (A ! B) ⊕B A!B A ! B
  159. Phép đóng Phép đóng có thể làm trơn biên ảnh và kết nỗi các vùng của cùng một đối tượng. A• B = (A ⊕ B)!B A!B A ! B
  160. Tách biên ảnh β(A)=A - (A!B)
  161. Lấp đầy vùng ảnh c Xk = (Xk−1 ⊕ B)∩ A , k =1, 2,3 Lặp quá trình trên đến khi Xk-1=Xk c B A A X0 X X 1 2 X7 X7 ∪ A
  162. Lấp đầy vùng ảnh Ảnh gốc Lấp đầy một vùng ảnh Lấp đầy vùng ảnh
  163. MÃ HÓA VÀ NÉN ẢNH Trần Quang Đức
  164. Dung lượng thông tin • Một trang văn bản: 2 KB. • Một ảnh màu (800x600x24): 1,4 MB • 30 phút âm thanh thoại số (8 kHz, 8 bits): 14 MB • 30 phút audio CD (44,1 kHz, 16 bits, stereo): 316 MB • 30 phút video (800x600x24, 25 khung hình/s): 64,8 GB
  165. Khái niệm • Nén dữ liệu ảnh: Biển đổi dòng thông tin ảnh thành từ mã nhằm giảm độ dư thừa thông tin. Các phương pháp nén khác nhau do định nghĩa các kiểu dư thừa thông tin khác nhau. • Các kiểu dư thừa thông tin gồm: sự phân bố mức xám (Mã Huffman), sự lặp lại của các mức xám (RLC), những mẫu sử dụng tần xuất cao (LZW) hoặc độ dư thừa vị trí (mã hóa dự đoán) • Tỷ lệ nén=1/r (%) trong đó r là kích thước dữ liệu gốc chia cho kích thước dữ liệu sau nén
  166. Phân loại phương pháp nén • Cách 1 (Dựa trên nguyên lý nén) ▫ Nén không mất mát thông tin ▫ Nén mất mát thông tin • Cách 2 (Dựa trên cách thức thực hiện nén) ▫ Phương pháp không gian ▫ Phương pháp dựa trên biến đổi • Cách 3 (Dựa trên triết lý mã hóa) ▫ Phương pháp nén thế hệ thứ nhất ▫ Phương pháp nén thế hệ thứ hai
  167. Mã loạt dài • Thay bằng việc truyền đi một chuỗi “0” hoặc “1”, có thể truyền độ dài của chuỗi. • Trong dữ liệu fax, 70%-80% không gian là các điểm ảnh có giá trị 0 (điểm ảnh trắng). Vì thế mã loạt dài hoạt động rất hiệu quả. Có thể thay thế độ dài chuỗi bằng một số nguyên có kích thước cố định. • Mã loạt dài tỏ ra kém hiệu quả nếu tần suất xuất hiện của giá trị 1 (điểm ảnh màu đen) tăng. • 11111111111000000000000011111 à 11,1,13,0,5,1
  168. Mã Huffman • Mã Huffman: Phương pháp nén dự trên mô hình thống kê xem xét sắc xuất phân bố của ký tự. Mô hình xác định sắc xuất có thể là mô hình tĩnh, thích nghi hoặc bán thích nghi (semi- adaptive). • Mô hình tĩnh được tích hợp sẵn trong thiết bị nén và thiết bị giải nén. • Mô hình bán thích nghi là mô hình cố định được xây dựng từ dữ liệu được nén. • Mô hình thích nghi thay đổi trong quá trình nén.
  169. Thuật toán cơ bản • Các ký tự có tần suất xuất hiện khác nhau. • Các ký tự chiếm không gian biểu diễn khác nhau. • Ký tự với độ dài từ mã nhị phân cố định trong bảng mã ASCII được thay bằng từ mã có độ dài thay đổi. • Từ mã ngắn được gán cho các ký tự với tần suất xuất hiện cao trong văn bản hoặc tập văn bản. • Bộ mã tạo ra có tính chất tiền tố.
  170. Thuật toán cơ bản 1) Quét văn bản để thống kê tần suất xuất hiện của các ký tự. 2) Xây dựng cây mã Huffman dựa trên thống kê tần suất. Mỗi ký tự được biểu diễn bằng một nút lá. Nút lá xa gốc được gán cho ký tự ít xuất hiện. 3) Từ mã biểu diễn ký tự được lấy thông qua đường dẫn từ gốc đến nút lá tương ứng. Nhánh rẽ trái và nhánh rẽ phải được ký hiệu bởi bit 0 và 1.
  171. Minh họa BCAACADBDCADAEEEABACDBACADCBADABEABEAAA (39) 0 1 A(15) (24) 0 1 (13) (11) 0 1 0 1 B(7) C(6) D(6) E(5)
  172. Mã số học • Chuỗi ký tự được gán bởi một từ mã số học duy nhất. Độ dài của từ mã tỷ lệ thuận với độ dài của chuỗi ký tự. Mã số học cần phải có bản tin đặc biệt để phân biệt giữa các từ mã. 1 0.2 0.08 0.072 0.0688 a4 a4 a4 a4 a4 0.06752 a3 a3 a3 a3 a3 a2 a2 a2 a2 a2 a1 a1 a1 a1 a1 0 0 0.04 0.056 0.0624
  173. Mã từ điển Lempel-Ziv • Mã từ điển xây dựng từ mã mới cho một chuỗi các từ mã. • Ví dụ: Bảng mã ASCII – mỗi từ mã có độ dài 8 bit, cho phép mã hóa 256 ký tự. • Mã từ điển mở rộng thư viện với từ mã có độ dài từ 9 đến 12 bit. Từ mã mới là chuỗi các từ mã đã xuất hiện. • Mã từ điển hoạt động không hiệu quả với văn bản gồm những chuỗi ký tự ngắn và khác nhau.
  174. Minh họa • Xét chuổi ký tự sau: ABCBCABCABCD Previous Input Output Symbol Index Previous Input Output Symbol Index Input Input NIL A NIL A A A B A AB 256 A B B AB 256 B C B BC 257 B C C BC 257 C B C CB 258 C 257 BC CB 258 B C BC 256 AB BCA 259 BC A BC BCA 259 AB C C ABC 260 A B C 260 ABC CA 261 AB C AB ABC 260 ABC D D ABCD 262 C A C CA 261 A B AB C ABC D ABC ABCD 262 D EOL D
  175. Minh họa • Mã từ điển được sử dụng trong nén ảnh graphic interchange format (GIF), tagged image file format (TIFF) và portable document format (PDF). Ảnh đa mức xám sử dụng 8 bit/ pixel. 39 39 126 126 39 39 126 126 39-39-126-126-256-258-260-259-257-126 39 39 126 126 39 39 126 126
  176. NÉN ẢNH FAX Trần Quang Đức
  177. Chuẩn nén • ITU-T Nhóm 1,2 ▫ Kỹ thuật điều chế: FM, AM, PM ▫ Màu trắng: 1300 Hz, 1500 Hz ▫ Màu đen: 2100 Hz, 2400 Hz • ITU-T Nhóm 3: mày fax được thiết kế hoạt động trong mạng PSTN (9600 baud). • ITU-T Nhóm 4: Mày fax được thiết kế hoạt động trong mạng ISDN (64K baud).
  178. ITU-T Nhóm 3 • Hướng quét: Trái sang phải, Trên xuống dưới • Độ rộng đường quét: 215 (255, 303) • Số lượng pixel trên một đường: 1728 (2048, 2432) • Mã hóa: RLC+MH (MMR - Nhóm 4, Tùy chọn nhóm 3) • Tỷ lệ nén: 5%-20% của kích thước ban đầu (đến 95%)
  179. Mã Huffman hiệu chỉnh • Loạt điểm ảnh trắng có độ dài 1664 được thay thế bằng từ mã ngắn 011000. • Mã Huffman được hiệu chỉnh để mã hóa những loạt điểm ảnh có độ dài là bội số của 64. • Độ dài của loạt điểm ảnh có thể biểu diễn bằng một từ mã hoặc một vài từ mã (trong trường hợp loạt quá dài).
  180. Mã Huffman hiệu chỉnh Run Length White Code Word Black Code Word 0 00110101 0000110111 1 000111 010 2 0111 11 3 1000 10 4 1011 011 5 1100 0011 61 00110010 000001011010 62 00110011 000001100110 63 00110100 000001100111
  181. Mã Huffman hiệu chỉnh Run Length White Code Word Black Code Word 64 11011 0000001111 128 10010 000011001000 192 010111 000011001001 256 0110111 000001011011 320 00110110 000000110011 384 0110111 000000110100 2432 000000011101 Same as white 2496 000000011110 Same as white 2560 000000011111 Same as white
  182. Mã Huffman hiệu chỉnh • Loạt gồm 5 điểm ảnh trắng được mã hóa 1100 • Loạt gồm 69 điểm ảnh trắng được mã hóa: 64+5 • Loạt gồm 64 điểm ảnh trắng được mã hóa: 64+0 • Loạt gồm 2561 điểm ảnh trắng được mã hóa: 2560+1 • Từ mã EOL: 000000000001
  183. Mã Huffman hiệu chỉnh • Không có loạt có độ dài 0. Tại sao vẫn có từ mã cho loạt gồm 0 điểm ảnh trắng và 0 điểm ảnh đen? • Thường một dòng quét có kích thước 8.5 inch tương đương 1728 điểm ảnh, tại sao vẫn có mã cho những loạt có độ dài 2561? • Loạt gồm 5 điểm ảnh đen có mã 0011, cũng là tiền tố của loạt gồm 61, 62 hoặc 63 điểm ảnh trắng. Giải thích lý do! • Tìm tỷ số nén của ảnh gồm các điểm ảnh đen và trắng nằm xen kẽ nhau.
  184. NÉN ẢNH JPEG Trần Quang Đức
  185. Giảm mẫu kênh màu
  186. Giảm mẫu kênh màu • 4:4:4 (1:1) ▫ Thiết bị quét phim cao cấp ▫ Điện ảnh • 4:2:2 (3:2) ▫ Đinh dạng video cao cấp • 4:1:1 (2:1) ▫ DVCPRO (ví dụ NTSC, PAL ) • 4:2:0 (2:1) ▫ MPEG, mã hóa video H.26X ▫ DVD, Blue-ray ▫ JPEG, MJPEG
  187. Chuẩn JPEG • JPEG là chuẩn nén ảnh, được phát triển bởi “Joint Photographic Experts Group”. • JPEG là định dạng thường được sử dụng trong lưu và truyền ảnh. • JPEG nén được trên cả ảnh màu và đen trắng • Tỷ lệ nén 1:10 nhưng không ảnh hưởng nhiều đến cảm nhận của mắt người.
  188. Chuẩn JPEG • JPEG là kỹ thuật nén mất mát thông tin dựa trên biến đổi 2D-DCT (Discrete Cosine Transform). ▫ Nhận định 1: Nội dung ảnh thay đổi tương đối chậm trên bề mặt của ảnh. ▫ Nhận định 2: Mắt người nhạy cảm hơi với những mất mát thuộc về thành phần tần số thấp. ▫ Nhận định 3: Mắt người cảm nhận tốt hơn sự thay đổi về độ chói so với màu sắc.
  189. Chuẩn JPEG 8×8 blocks Entropy Compressed Image FDCT Quantization Encoding Source Image Quant. Table Huffman Table 8×8 blocks Entropy IDCT Dequantization Decoding Source Image Quant. Table Huffman Table
  190. Biến đổi DCT • DCT biến đổi tín hiệu ảnh từ miền không gian sang miền tần số. Năng lượng ảnh tập chung chủ yếu ở các thành phần tần số thấp, nằm góc trên cùng bên trái của DCT. Các thành phần tần số cao thường có giá trị thấp trong biến đổi DCT nên có thể loại bỏ để tăng hiệu quả của quá trình nén. 4C C M−1 N−1 !π(2k +1)u$ !π(2l +1)v $ F(u, v) = k l ∑∑ f (x, y)cos# &cos# & MN k=0 l=0 " 2M % " 2N % ! ! # 1/ 2 If k = 0 # 1/ 2 If k = 0 Ck = " Cl = " $# 1 Otherwise $# 1 Otherwise
  191. Biến đổi DCT 52 55 61 66 70 61 64 73 -145 -30 -61 27 56 -20 -2 0 63 59 55 90 109 85 69 72 4 -22 -61 10 13 -7 -9 5 62 59 68 113 144 104 66 73 47 7 77 -25 -29 10 5 -6 63 58 71 122 154 106 70 69 DCT -49 12 34 -15 -10 6 2 2 67 61 68 104 126 88 68 70 12 -7 -13 -4 -2 2 -3 3 79 65 60 70 77 68 58 75 -8 3 2 -6 -2 1 4 2 85 71 64 59 55 61 65 83 -1 0 0 -2 -1 -3 4 -1 87 79 69 68 65 76 78 94 0 0 -1 -4 -1 0 1 2 • Thành phần DC (i.e., F(0,0)) và AC (i.e., F(u,v) (u,v≠0)) đều là số nguyên, có giá trị nằm trong khoảng từ -1024 đến 1023.
  192. Lượng tử hóa • Lượng tử hóa loại bỏ những thông tin thừa trong ảnh. Lượng tử hóa là nguyên nhân chủ yếu dẫn đến mất mát thông tin trong các kỹ thuật dựa trên biến đổi DCT. FQ(u,v)=Integer Round (F (u,v)/Q(u,v)) Quantization step size • Bước lượng tử hóa được chọn dựa trên cảm nhận của mắt người. Nó là hàm với các biến gồm đặc trưng ảnh, đặc trưng hiển thị và khoảng cách hiển thị. • Trong ứng dụng, bước lượng tử hóa thường được xác định dựa trên thực nghiệm.
  193. Lượng tử hóa 16 11 10 16 24 40 51 61 -26 -3 -6 2 2 -1 0 0 12 12 14 19 26 58 60 55 0 -2 -4 1 1 0 0 0 Tần số tăng dần 14 13 16 24 40 57 69 56 -3 1 5 -1 -1 0 0 0 14 17 22 29 51 87 80 62 -4 1 2 -1 0 0 0 0 18 22 37 56 68 109 103 77 1 0 0 0 0 0 0 0 24 35 55 64 81 104 113 92 0 0 0 0 0 0 0 0 49 64 78 87 103 121 120 101 0 0 0 0 0 0 0 0 72 92 95 98 112 100 103 99 0 0 0 0 0 0 0 0 • Những thành phần tần số cao thường có giá trị bằng 0 hoặc rất nhỏ (kể cả giá trị âm và giá trị dương) nên có thể được biểu diễn bằng một vài bit.
  194. Mã hóa Entropy DC DPCM Q Huffman F (u,v) coding 01101 AC RLC • Mã hóa Entropy là dạng đặc biệt của nén không mất mát thông tin. • Mã hóa Entropy gồm các bước sau: (1) sắp xếp các thành phần ảnh theo đường díc dắc; (2) mã hóa các thành phần ảnh bằng mã loạt dài (RLC) và Huffman.
  195. Đường díc dắc -26 -3 -6 2 2 -1 0 0 -26 -3 -6 2 2 -1 0 0 0 -2 -4 1 1 0 0 0 0 -2 -4 1 1 0 0 0 -3 1 5 -1 -1 0 0 0 -3 1 5 -1 -1 0 0 0 -4 1 2 -1 0 0 0 0 -4 1 2 -1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 • Tất cả các hệ số đều nằm trên đường díc dắc. Các thành phần tần số thấp (thường khác 0) được xếp trước các thành phần tần số cao.
  196. DPCM và Mã loạt dài • Các thành phần DC của các khối ảnh lân cận có tính tương quan cao. Vì vậy, mã hóa sự sai khác giữa các thành phần trên làm tăng tính hiệu quả của quá trình nén. DCi-1 DCi DIFF = DCi - DCi-1 • Mã loạt dài được sử dụng để mã hóa các thành phần AC
  197. DPCM và Mã loạt dài • Thành phần DC: +3 à (2),(3) -26 -3 -6 2 2 -1 0 0 • Thành phần AC: 0 -2 -4 1 1 0 0 0 ▫ (0,2) (-3) -3 1 5 -1 -1 0 0 0 ▫ (1,2) (-3) -4 1 2 -1 0 0 0 0 ▫ (0,2) (-2) ▫ (0,3) (-6) 1 0 0 0 0 0 0 0 ▫ (0,2) (2) 0 0 0 0 0 0 0 0 ▫ 0 0 0 0 0 0 0 0 ▫ (0,0) à EOB 0 0 0 0 0 0 0 0 • Các thành phần AC được mô tả bởi một cặp ký hiệu (loạt dài, kích thước) (biên độ). Loạt dài được tính bằng số lượng 0 giữa hai thành phần khác 0. Kích thước biểu diễn số lượng bit dùng để mã hóa giá trị biên độ.
  198. Mã Huffman • Thực hiện tăng hiệu quả nén bằng việc thay thế những chuỗi ký tự dài bằng những từ mã ngắn. • Độ dài của mỗi từ mã được xác định dựa trên tần suất xuất hiện của các ký tự. • JPEG cung cấp bảng mã Huffman chuẩn, nhưng bảng mã Huffman cũng có thể được định nghĩa riêng tùy thuộc vào ứng dụng và đặc trưng của các ảnh sử dụng trong ứng dụng.
  199. Mã Huffman Category Values Bits for the value 1 -1,1 0,1 2 -3,-2,2,3 00,01,10,11 3 -7,-6,-5,-4,4,5,6,7 000,001,010,011,100,101,110,111 4 -15, ,-8,8, ,15 0000, ,0111,1000, ,1111 5 -31, ,-16,16, 31 00000, ,01111,10000, ,11111 6 -63, ,-32,32, 63 000000, ,011111,100000, ,111111 7 -127, ,-64,64, ,127 0000000, ,0111111,1000000, ,1111111 8 -255, ,-128,128, ,255 9 -511, ,-256,256, ,511 10 -1023, ,-512,512, ,1023 11 -2047, ,-1024,1024, ,2047 Giá trị và số lượng bit cho mỗi giá trị
  200. Mã Huffman Run, category Code Length Codeword 0,0 4 1010 0,1 2 00 0,2 2 01 0,10 16 1111111110000011 1,1 4 1100 1,2 5 11011 15,10 16 1111111111111110 Bảng mã Huffman chuẩn cho các thành phần AC của kênh độ chói
  201. Mã Huffman Category Code Length Codeword 0 2 00 1 3 010 2 3 011 3 3 100 4 3 101 5 3 110 6 4 1110 7 5 11110 8 6 111110 9 7 1111110 10 8 11111110 11 9 111111110 Bảng mã chuẩn cho các thành phần DC của kênh độ chói
  202. Mã Huffman • Thành phần DC: +3 à (2),(3) • Từ mã của thành phần DC: 011 11 • Thành phần AC: (0,2) (-3), (1,2) (-3) EOB • Từ mã của thành phần AC: 01 00 11011 00 00
  203. Minh họa 1 2 3 1. Q = 100 - 83,2 bytes 2. Q = 50 - 15,1 bytes 3. Q = 25 - 9,5 bytes 4. Q = 10 - 4,7 bytes 5. Q = 5 - 1,5 bytes 4 5
  204. NÉN ẢNH JPEG2000 Trần Quang Đức
  205. Chuẩn nén khác? • Với tỷ lệ nén cao (ví dụ 0.25 bpp), méo của chuẩn JPEG là không thể chấp nhận. • JPEG có 44 cách thức, rất nhiều trong số đó không được sử dụng trong bộ mã hóa JPEG. • Chất lượng của ảnh giảm đi rõ rệt nếu xuất hiện lỗi trong quá trình truyền ảnh. • JPEG được tối ưu hóa cho ảnh tự nhiên những không phù hợp với ảnh đồ họa. • JPEG không áp dụng được cho ảnh nhị phân.
  206. Chuẩn JPEG2000 • Đặc trưng ▫ Biến đổi sóng con Wavelet ▫ Chất lượng tốt với tỷ lệ nén cao ▫ Nén ảnh nhị phân ▫ Nén mất mát và không mất mát thông tin ▫ Linh hoạt với lỗi trong quá trình truyền ▫ Có khả năng mở rộng ▫ Chọn vùng quan tâm ROI • Một vài ứng dụng ▫ Website ▫ Camera kỹ thuật số ▫ Ảnh y học ▫ Ảnh viễn thám
  207. Chuẩn JPEG2000 Lossless 5.2 bpp Lossy b Original image it s t r e a m 1.89 bpp
  208. Chuẩn JPEG2000 0.125 bpp JPEG vs. JPEG2000 0.25 bpp
  209. Chuẩn JPEG2000 • Nhược điểm ▫ Thiết bị mã hóa và giải mã phức tạp, thời gian tính toán lâu. ▫ Khi tỷ lệ nén khoảng 1:25, JPEG2000 so với JPEG có thể tạo ra ảnh nén ít bị chia ô nhưng giảm đang kể các chi tiết ảnh.