Bài giảng Xử lý ảnh - Chương 1: Giới thiệu chung - Hoàng Văn Hiệp

Nội dung text: Bài giảng Xử lý ảnh - Chương 1: Giới thiệu chung - Hoàng Văn Hiệp

1. 8/24/2011 Xử lý ảnh Hoàng Văn Hiệp Bộ môn Kỹ thuật máy tính Viện Công nghệ thông tin và Truyền thông Email: [email protected] Mục đích Cung cấp các kiến thức cơ bản về xử lý ảnh số Cung cấp các kỹ năng cần thiết giúp sinh viên có thể viết được các ứng dụng xử lý ảnh . Matlab . C++, C# 1
2. 8/24/2011 Yêu cầu Các kiến thức toán học . Matrix và vector . Xác suất thống kê Các kiến thức về xử lý tín hiệu Kỹ năng lập trình . Matlab . C, C++, C# Tài liệu tham khảo  Books . Digital Image Processing, by: R. C. Gonzalez and R. E. Woods, 3rd Ed., 2008, Prentice Hall . Digital image processing using Matlab by Gonzalez  Journals . IEEE Trans. on Image Processing . IEEE Transactions on Pattern Analysis and Machine Intelligence  Conferences . ICIP . ICIAP . CVPR . ICPR . ICCP . ICCV 2
3. 8/24/2011 Đánh giá Thi: 70 % Bài tập lớn: 30 % . Đề tài: Tuần thứ 4, 5 . Bảo vệ BTL: Tuần 15 . Chia nhóm thực hiện: (2 người – 3 người) Nội dung Chương 1. Giới thiệu chung Chương 2. Thu nhận & số hóa ảnh Chương 3. Cải thiện & phục hồi ảnh Chương 4. Phát hiện tách biên, phân vùng ảnh Chương 5. Trích chọn các đặc trưng trong ảnh Chương 6. Nén ảnh Chương 7. Lập trình xử lý ảnh bằng Matlab và C 3
4. 8/24/2011 Chương 1. Giới thiệu chung Khái niệm xử lý ảnh Các vấn đề của xử lý ảnh Giới thiệu một số ứng dụng của xử lý ảnh Matrix và vector Một số khái niệm cơ bản Khái niệm xử lý ảnh Khái niệm ảnh Khái niệm ảnh số Phân biệt ảnh tĩnh, ảnh động Khái niệm xử lý ảnh 4
5. 8/24/2011 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 được bằng mắt và hệ thống thần kinh thị giác Biểu diễn ảnh về mặt toán học: o F(x, y): trong đó x, y là tọa độ không gian 2 chiều và f là độ lớn của độ chói (ảnh đơn sắc), màu (đối với ảnh màu) o Chú ý: x, y biến thiên liên tục và f cũng liên tục Khái niệm ảnh số Ảnh số là ảnh thu được từ ảnh liên tục bằng phép lấy mẫu và lượng tử hóa y Gray level x pixel Original picture Digital image f(x, y) I[i, j] or I[x, y] 5
6. 8/24/2011 Khái niệm ảnh số (tiếp) Khái niệm ảnh số (tiếp) Một ảnh số thường được biểu diễn như một ma trận các điểm ảnh Trong đó mỗi điểm ảnh có thể được biểu diễn bằng . 1 bit (ảnh nhị phân) . 8 bit (ảnh đa mức xám) . 16, 24 bit (ảnh màu) Ảnh được biểu diễn ảnh dưới dạng ma trận các điểm ảnh gọi là ảnh bitmap 6
7. 8/24/2011 Khái niệm ảnh số (tiếp) Một cách biểu diễn khác của ảnh số là dưới dạng vector (ảnh vector) . Không biểu diễn ảnh dưới dạng ma trận các điểm ảnh mà hướng đến đối tượng trong ảnh . Thường bao gồm các thành phần cơ bản như hình tròn, đường thẳng Circle(100, 20, 20) Line(xa1, ya1, xa2, ya2) Line(xb1, yb1, xb2, yb2) Line(xc1, yc1, xc2, yc2) Line(xd1, yd1, xd2, yd2) Ảnh bitmap vs ảnh vector  Bitmap  Vector  Biểu diễn các hình phức  Biểu diễn các hình đơn tạp hơn giản  Tính toán chậm  Tính toán nhanh  Hạn chế khi zoom, các  Đuôi file: *.EPS, *.AI, phép biến hình *CDR, or *.DWG.  Đuôi file: BMP, JPG 7
8. 8/24/2011 Phân biệt giữa ảnh tĩnh và chuỗi ảnh động (chuỗi ảnh) Khái niệm xử lý ảnh Nâng cao chất lượng hình ảnh theo một tiêu chí nào đó (Cảm nhận của con người) Phân tích ảnh để thu được các thông tin đặc trưng giúp cho việc phân loại, nhận biết ảnh. Hiểu ảnh đầu vào để có những mô tả về ảnh ở mức cao hơn, sâu hơn. 8
9. 8/24/2011 Lịch sử về xử lý ảnh Bắt nguồn từ hai ứng dụng: nâng cao chất lượng thông tin hình ảnh và xử lý số liệu cho máy tính Ứng dụng đầu tiên là việc truyền thông tin ảnh báo giữa London và New York vào năm 1920 qua cáp Bartlane. Mã hóa dữ liệu ảnh  khôi phục ảnh Thời gian truyền ảnh: Từ 1 tuần  3 tiếng 17 Lịch sử về xử lý ảnh Ảnh số được tạo ra vào năm 1921 từ băng mã hóa của một máy in điện tín. (McFarlane) Ảnh số được tạo ra vào năm 1922 từ card đục lỗ sau 2 lần truyền qua Đại Tây Dương. Một vài lỗi có thể nhìn thấy được. 18 9
10. 8/24/2011 Lịch sử về xử lý ảnh Ảnh 15 cấp độ xám được truyền từ Luân Đôn đến New York, năm 1929. (McFarlane) Hệ thống đầu tiên có khả năng mã hóa hình ảnh với mức xám là 5 và tăng lên 15 vào năm 1929 Trong khoảng thời gian này, người ta chỉ nói đến ảnh số, chứ chưa đề cập gì đến xử lý ảnh số, vì một lý do đơn giản: máy tính chưa có. 19 Lịch sử về xử lý ảnh Năm 1964, ảnh mặt trăng được đưa về trái đất thông qua các máy chụp của tàu Ranger 7 của Jet Propulsion Laboratory (Pasadena, California) để cho máy tính xử lý: Chỉnh méo. Ảnh đầu tiên của mặt trăng được chụp bởi tàu vũ trụ Mỹ Ranger 7, vào 9 giờ 09 phút sáng ngày 31/7/1964 (nguồn: NASA) 20 10
11. 8/24/2011 Lịch sử về xử lý ảnh Song song với các ứng dụng trong khám phá không gian, các kỹ thuật xử lý ảnh cũng đã bắt đầu vào cuối những năm 1960 và đầu những năm 1970 trong y học, theo dõi tài nguyên trái đất và thiên văn học. Đến nay xử lý ảnh đã có một bước tiến dài trong nhiều ngành khoa học, từ những ứng dụng đơn giản đến phức tạp. 21 Mô hình hệ thống xử lý ảnh Nhìn từ phía người dùng 11
12. 8/24/2011 Mô hình hệ thống xử lý ảnh Các giai đoạn trong xử lý ảnh Lưu trữ Camera Thu nhận Phân tích Đối sánh Số hóa ảnh ảnh Nhận dạng Sensor Hệ quyết định Lưu trữ Mô hình hệ thống xử lý ảnh Thiết bị cảm biến thu Lượng tử hóa, nén ảnh nhận ảnh Image Acquisition Nâng cao chất lượng ảnh (độ tương phản, nhiễu, ) Discretization/Digitization Phân đoạn ảnh: phân tách Quantization các đối tượng trong ảnh Compression Image enhancement Biểu diễn (gán nhãn) ảnh dựa vào đặc and restoration trưng ảnh Image Segmentation Nhận dạng, giải thích Feature Selection Rút trích những đặc trưng của ảnh Image Representation Image Interpretation 12
13. 8/24/2011 Các cấp độ trong xử lý ảnh Level 0: Image acquisition (thu nhận ảnh, lấy mẫu, lượng tử hóa, nén) Level 1: Image to Image (tăng cường ảnh, khôi phục ảnh, phân đoạn ảnh) Level 2: Image to parameter (trích chọn đặc trưng: feature extraction, feature selection) Level 3: Parameter to decision (recognition, interpretation) Mô hình hệ thống xử lý ảnh Những vấn đề cần giải quyết (cần học) Preprocessing – low level High-level IP Image Image Image Enhancement Restoration Segmentation Image Image Image Acquisition Compression Coding Representation & Description Morphological Wavelet Recognition & Image Processing Analysis Interpretation Knowledge Base 13
14. 8/24/2011 Các vấn đề của xử lý ảnh Thu nhận ảnh, số hóa ảnh (image aquisition) . Hệ thống chụp ảnh, tín hiệu ảnh . Hệ thống số hóa ảnh: Các phương pháp lấy mẫu, lượng tử hóa Cải thiện ảnh, khôi phục ảnh, lọc nhiễu (tiền xử lý – image pre-processing) . Các phép xử lý điểm ảnh . Các phép xử lý trên miền không gian . Các phép xử lý trên miền tần số Các vấn đề của xử lý ảnh Phân tích ảnh . Trích chọn đặc trưng (feature extraction) . Biểu diễn, mô tả ảnh (image representation, image description) . Phân lớp ảnh (image classification) . Nhận dạng ảnh (image recognition) . Mã hóa, nén ảnh . Các phương pháp nén ảnh, các chuẩn nén ảnh Truyền thông ảnh 14
15. 8/24/2011 Xử lý ảnh và các lĩnh vực liên quan Phân biệt một số khái niệm  Image formation: . object in image out (level 0)  Image processing (level 0, 1) . Image in image out  Image analysis (level 1, 2) . Image in features out Computer vision (level 2, 3) . Image in interpretation out  Computer graphic . Number in image out  Visualization . Image in representation out 15
16. 8/24/2011 Các ứng dụng của xử lý ảnh Xử lý ảnh vệ tinh, ảnh viễn thám Thiên văn, nghiên cứu không gian, vũ trụ Thăm dò địa chất Lĩnh vực y tế Robot, tự động hóa Giám sát, phát hiện chuyển động  Image và video retrieval Các ứng dụng của xử lý ảnh Bức xạ phổ điện từ của ánh sáng 16
17. 8/24/2011 Các ứng dụng của xử lý ảnh  Ảnh Gamma 33 Các ứng dụng của xử lý ảnh a b  Ảnh Gamma c d Ảnh phóng xạ (a) Quét bộ xương (b) Chụp PET (Positron Emission Tomography) Ảnh thiên văn (c) Chùm sao thiên nga Ảnh phản ứng hạt nhân (d) Sự bức xạ tia Gamma từ lò phản ứng 34 17
18. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh tia X (ảnh X-Quang) Hệ thống máy chụp ảnh X-Quang 35 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh tia X (ảnh X-Quang) Ảnh -X Quang chụp lồng ngực Ảnh -X Quang chụp hàm mặt 36 18
19. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh tia X (ảnh X-Quang) Hệ thống máy chụp ảnh cắt lớp CT 37 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh tia X Ảnh chụp cắt lớp CT 38 19
20. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp) a c  Ảnh trong dải cực tím d (a) Trùng bình thường (b) Trùng bệnh than (c) Chùm sao thiên nga 39 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh hồng ngoại Ảnh hồng ngoại Ảnh hồng ngoại 40 chụp đầu con mèo chụp đầu con chó 20
21. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh hồng ngoại Ảnh hồng ngoại chụp bề mặt trái đất. Những nơi có ánh sáng mạnh là những nơi có nguồn nhiệt lớn. 41 Các ứng dụng của xử lý ảnh (tiếp)  Ảnh hồng ngoại Ảnh hồng ngoại chụp không gian trên bề mặt trái đất. Ảnh này cho biết lượng hơi nước tích tụ trong không gian, phục vụ cho việc dự báo thời tiết. 42 21
22. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp) Trong vùng ánh sáng nhìn thấy . Cải thiện ảnh Các ứng dụng của xử lý ảnh (tiếp) Giảm nhiễu 22
23. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp) Các ứng dụng của xử lý ảnh (tiếp) 23
24. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp) Các ứng dụng của xử lý ảnh (tiếp) 24
25. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp) Các ứng dụng của xử lý ảnh (tiếp) Nhận dạng chữ viết 25
26. 8/24/2011 Các ứng dụng của xử lý ảnh (tiếp) Các ứng dụng của xử lý ảnh (tiếp) 26
27. 8/24/2011 Giới thiệu một số hệ thống retrieval Google image similarity IMARS . MediaMill . crossbrowser.php . Demo1 . Demo2 CuVid . Video summarization Matrix và vector Các phép xử lý ảnh thực chất là các phép tính toán trên các ma trận và các vectors  review lại một số khái niệm trong toán học về matrix và vector 27
28. 8/24/2011 Một số khái niệm Khái niệm ma trận: m: dòng, n cột A là vuông (square) nếu m = n A là ma trận đường chéo (diagonal): nếu các phần tử không nằm trên đường chéo = 0, có ít nhất một phần tử trên đường chéo ≠ 0 A là ma trận đơn vị (identity - I): nếu diagonal và các phần tử trên đường chéo đều = 1 Một số khái niệm (tiếp)  푡 푒 = á ℎầ푛 푡ử 푡 ê푛 đườ푛𝑔 ℎé표 ℎí푛ℎ Ma trận chuyển vị (transpose): dòng cột, cột dòng, ký hiệu: Ma trận vuông A đối xứng (symetric) nếu A = Ma trận nghịch đảo (Inverse): X là inverse của A nếu: XA = I và AX = I 28
29. 8/24/2011 Một số khái niệm (tiếp) Vector cột (column vector) là ma trận mx1 Vector hàng (row vector) là ma trận 1xm Các phép tính trong ma trận A, B cùng kích thước m x n . C = A + B C kích thước m x n và 푖푗 = 푖푗 + 푖푗 . D = A – B D kích thước m x n và 푖푗 = 푖푗 - 푖푗 A(m, n); B(n, q) . C = AB C kích thước m x q và 29
30. 8/24/2011 Các phép tính trong ma trận Cho 2 vector a, b cùng kích thước . Tích vô hướng 2 vector (inner product – dot product) được định nghĩa như sau Không gian vector (vector spaces) Không gian vector được định nghĩa là một tập vector V và thỏa mãn các điều kiện sau đây . Điều kiện A o 1. x + y = y + x với mọi vector x và y trong không gian o 2. x + (y + z) = (x + y) + z o 3. Tồn tại duy nhất vector 0: x + 0 = 0 + x = 0 o 4. x + (-x) = (-x) + x = 0 30
31. 8/24/2011 Vector spaces (tếp) Điều kiện B . 1. c(dx) = (cd)x với mọi số c, d và vector x . 2. (c + d)x = cx + dx . 3. c(x + y) = cx + cy Điều kiện C . 1x = x Vector spaces (tiếp) Tổ hợp tuyến tính (linear combination) của các vectors: 푣1, 푣2, , 푣푛 Vetor v gọi là phụ thuộc tuyến tính (linearly dependent) của các vectors 푣1, 푣2, , 푣푛 nếu v có thể viết là tổ hợp tuyến tính của tập vector này. Ngược lại v là độc lập tuyến tính của tập vector trên (linearly independent) 31
32. 8/24/2011 Vector spaces (tiếp) Tập vector cơ sở (basis vector set) trong không gian V cho phép tạo ra vector v bất kỳ trong không gian . Ví dụ: không gian vector 푅3, vector . Có thể được tạo bằng tổ hợp tuyến tính của 3 vectors cơ sở: Chuẩn của vector (vector norm) Vector norm của vector x : ký hiệu cần thỏa mãn các điều kiện sau Công thức tính chuẩn của vector có nhiều, công thức hay dùng: 2-norm (khoảng cách Euclidean) 32
33. 8/24/2011 Quan hệ giữa 2 vector Cosin Suy ra cách tính khác của tích vô hướng (inner product) 2 vector gọi là trực giao (orthogonal) với nhau nếu và chỉ nếu tích vô hướng = 0 2 vector gọi là trực chuẩn (orthonormal) nếu . Chúng trực giao . Norm của mỗi vector = 1 Quan hệ giữa các vectors Tập các vector là trực giao nếu mọi cặp 2 vector trực giao từng đôi một Tập các vector là trực chuẩn nếu mọi cặp 2 vector trực chuẩn từng đôi một 33
34. 8/24/2011 Tính chất của vector trực giao Nếu là tập vector trực giao hoặc trực chuẩn, thì vector v bất kỳ có thể được biểu diễn bằng tổ hợp tuyến tính của các vector trực giao trên Trị riêng – vector riêng (Eigen values - eigenvectors) Cho ma trận vuông M, nếu tồn tại một số và vector e sao cho: Thì: gọi là trị riêng của ma trận M e: là vector riêng ứng với trị riêng 34
35. 8/24/2011 Eigenvalues và eigenvectors (tiếp) Công thức tính: Dựa trên biểu thức Trong đó: det là định thức Ví dụ: Tìm trị riêng, vector riêng của ma trận sau: Eigenvalues và eigenvectors (tiếp) Giải: Suy ra: λ = 1 and λ = 3 Với λ = 3, tìm vector riêng tương ứng x = y, 35
36. 8/24/2011 . Tính chất của eigenvalues và eigenvectors Ma trận vuông A (m x m) có m eigenvalues phân biệt thì m eigenvectors tương ứng sẽ trực giao với nhau M là ma trận vuông đối xứng, A là ma trận có các hàng là các vector riêng của ma trận M thì (nếu ma trận vuông đối xứng thì các vector riêng sẽ trực chuẩn - orthonormal) Tính chất của eigenvalues và eigenvectors M là ma trận vuông đối xứng, A là ma trận có các hàng là các vector riêng của ma trận M. . D là ma trận đường chéo, với các phần tử trên đường chéo là các trị riêng (eigenvalues) của ma trận M 36
37. 8/24/2011 . Tính chất của eigenvalues và eigenvectors A là ma trận vuông Một số khái niệm cơ bản Điểm ảnh (pixel) Độ phân giải (resolution) Mức xám (gray scale) Lân cận (neighbors) Liên thông (conectivity) 37
38. 8/24/2011 Một số khái niệm cơ bản (tiếp) Pixel: Picture element là đơn vị nhỏ nhất cấu tạo nên ảnh số . Mỗi pixel có tọa độ (x,y) và giá trị cường độ sáng hoặc màu sắc tại điểm đó Độ phân giải của ảnh: Số pixel có trong ảnh để tạo nên bức ảnh đó . Thường ghi dưới dạng: m x n o m: số pixel trên chiều rộng ảnh o n: số pixel trên chiều cao ảnh . Độ phân giải càng cao, ảnh càng sắc nét Một số khái niệm cơ bản (tiếp) Độ phân giải (resolution) a b c d e f (a) 1024 1024 (b) 512 512 (c) 256 256 (d) 128 128 (e) 64 64 (f) 32 32 38
39. 8/24/2011 Một số khái niệm cơ bản (tiếp) Mức xám (gray) . Mức xám là kết quả của việc mã hoá ứng với một cường độ sáng của mỗi điểm ảnh với một giá trị số. Thông thường ảnh được mã hoá dưới dạng 16, 32, 64 hay 256 mức. . Ví dụ: tại điểm ảnh tọa độ (20, 40) có mức xám là 60, tại điểm ảnh tọa độ (30, 40) có mức xám là 23, Một số khái niệm cơ bản (tiếp) Lân cận (neighbours) . Một điểm ảnh p tại tọa độ (x, y) có x o 4 lân cận ngang - dọc của p: Ký hiệu là N4(p) x p x (x+1,y), (x-1,y), (x,y+1), (x,y-1) x o 4 lân cận chéo của p: Ký hiệu là ND(p) x x (x+1,y+1), (x+1,y-1), (x-1,y+1), (x-1,y-1) p o 8 lân cận của p: Ký hiệu N8(p) x x là sự kết hợp của N4(p) và ND(p) (x+1,y), (x-1,y), (x,y+1), (x,y-1), x x x (x+1,y+1), (x+1,y-1), (x-1,y+1), (x-1,y-1) x p x x x x 39
40. 8/24/2011 Một số khái niệm cơ bản (tiếp) Liên thông: Các điểm trong ảnh gọi là liên thông với nhau nếu . Là lân cận của nhau . Và có cùng giá trị mức xám 40