Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 4: Tìm kiếm DL ĐPT P2: Dữ liệu ảnh - Nguyễn Thị Oanh

Nội dung text: Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 4: Tìm kiếm DL ĐPT P2: Dữ liệu ảnh - Nguyễn Thị Oanh

1. Nội dung  Tổng quan  Biểu diễn ảnh – trích chọn đặc trưng – Đặc trưng toàn cục: Shape – texture - color – Đặc trưng cục bộ:  Phân đoạn (segmentation)  Key points (characters points)  Đánh chỉ mục (chỉ số hóa) (indexing)  Đối sánh ảnh: tương tự, không gian 2
2. Ảnh và lưu trữ x y x = 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 y = 41 210 209 204 202 197 247 143 71 64 80 84 54 54 57 58 42 206 196 203 197 195 210 207 56 63 58 53 53 61 62 51 43 201 207 192 201 198 213 156 69 65 57 55 52 53 60 50 44 216 206 211 193 202 207 208 57 69 60 55 77 49 62 61 45 221 206 211 194 196 197 220 56 63 60 55 46 97 58 106 46 209 214 224 199 194 193 204 173 64 60 59 51 62 56 48 47 204 212 213 208 191 190 191 214 60 62 66 76 51 49 55 48 214 215 215 207 208 180 172 188 69 72 55 49 56 52 56 49 209 205 214 205 204 196 187 196 86 62 66 87 57 60 48 50 208 209 205 203 202 186 174 185 149 71 63 55 55 45 56 51 207 210 211 199 217 194 183 177 209 90 62 64 52 93 52 52 208 205 209 209 197 194 183 187 187 239 58 68 61 51 56 53 204 206 203 209 195 203 188 185 183 221 75 61 58 60 60 54 200 203 199 236 188 197 183 190 183 196 122 63 58 64 66 55 205 210 202 203 199 197 196 181 173 186 105 62 57 64 63 4 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel).
3. Phân loại ảnh  Ảnh tự nhiên: ảnh thu nhận từ các thiết bị – camera, microscope, tomography, infrared, satellite,  Ảnh nhân tạo: tạo ra từ các phần mềm chuyên biệt – Đồ họa máy tính (computer graphics), thực tại ảo (virtual reality) Ảnh tự nhiên ảnh nhân tạo Ảnh nhân tạo 6
4. Ảnh màu trong hệ tọa độ RGB Bên cạnh hệ tọa độ màu RGB ta còn có các hệ tọa độ màu khác 8 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel).
5. CSDL ảnh ( ): General database  General database : Photo collection, Internet – Nội dung đa dạng, không đồng nhất – Biểu diễn dựa trên các đặc trưng chung (shape, color, texture, ) – Vùng ứng dụng rộng 10
6. Tìm kiếm ảnh  Tìm các bức hình của « Steve Jobs » ?  Đây là bức hình của ai ? / Đây là cái gì ? / Bức hình này chụp ở đâu ? What ? Where ? Who ? 12
7. Kiểu truy vấn: từ khóa  Hạn chế: – Từ khóa được lấy từ:  Văn bản xung quanh ảnh (Google Image, Google Video)  Đánh dấu thủ công giá thành cao – Nhập nhằng: chọn từ khóa thế nào ?  Tính chủ quan của người đánh dấu keyword-image  Phụ thuộc ngôn ngữ  Phụ thuộc ngữ cảnh 14
8. Kiểu truy vấn: dựa trên nội dung 16 roc.inria.fr/imedia/index.php?option=com_content&view=article&id=95&Itemid=60
9. Kiểu truy vấn: dựa trên nội dung  Vấn đề: – Nội dung đa dạng – Khối lượng dữ liệu cần xử lý lớn và thường trùng lặp: Numeric gap – Vấn đề về ngữ nghĩa: Semantic gap  VD: làm thế nào để biết 1 người đang vui /buồn 18
10. CBIR – các bước chính  Trích chọn đặc trưng (Biểu diễn ảnh):  Đánh chỉ mục để tăng hiệu năng tìm kiếm (xem chương 3)  Lựa chọn thước đo độ tương tự ? 20
11. Biểu diễn ảnh – trích chọn đặc trưng  Đặc trưng toàn cục: – Màu sắc, hình dáng, kết cấu,  Đặc trưng cục bộ:  Phân vùng  Key points (characters points)  Đặc trưng riêng: tùy thuộc vào từng ứng dụng cụ thể  Nhận dạng vân tay: minuties (các điểm đầu, điểm rẽ nhánh)  Nhận dạng mặt: EigenFaces, 22
12. Đặc trưng màu sắc  Histogram: 1 đặc trưng màu sắc – Thể hiện sự phân bố màu sắc trên ảnh  Cách tính: – Lấy mẫu màu của ảnh. VD, ảnh màu 24 bit : 8 x 8 x8 màu (bin) – Tính số điểm ảnh tương ứng với mỗi màu chuẩn hóa: chia cho số điểm ảnh H h1, h2 , , hn , hi 0,1,hi 1 i 24
13. Ưu điểm của phân bố màu  Không phụ thuộc/ ít phụ thuộc vào một số các biến đổi hình học: – Phép quay – Phép tịnh tiến – zoom 26
14. Vấn đề gặp phải với phân bố màu – Ảnh hưởng của nền: d(I1,I2) ? d(I1, I3) I3 I1 I2 – Phụ thuộc cách biểu diễn màu (không gian màu), phụ thuộc thiết bị, 28
15. Đặc trưng kết cấu ( ) 30
16. Đặc trưng kết cấu ( )  Kết cấu có thể mô tả dựa trên – Phân tích thống kê  Tham số tính từ biểu đồ phân bố màu (histogram)  Phân tích ma trận đồng xuất hiện (Co-occurrence matric) Đặc trưng Haralick – Phân tích trên miền tần số  Biến đổi Fourrier  Biến đổi Gabor, – Mô hình 32
17. Đặc trưng kết cấu( )  Một số đặc trưng tính từ ma trận đồng xuất hiện: – Năng lượng: 2 CMd (i, j) i j (i j)2 CM (i, j) – Độ tương phản:  d i j – Entropy CMd (i, j)log(CMd (i, j)) i j 34
18. Ví dụ: chuỗi mã hóa Freeman 36
19. Đặc trưng cục bộ  Mục đích:  Tìm các vùng/ các đối tượng tương tự  Truy vấn bộ phận (partial query) Tìm những bức ảnh có chưa bông hoa hướng dương  Giải pháp: Source: Slides of Valérie Goudet-Brunet  Mô tả cục bộ các vùng 38  Thêm mối liên hệ về không gian
20. Biểu diễn ảnh – phân đoạn ảnh 40
21. Phân đoạn ảnh  Dựa trên: – Sự không liên tục: các biên (edge, contour)  Sự thay đổi về giá trị ở biên giữa các vùng – Sự đồng nhất: tương ứng cho các vùng  Cùng màu sắc, kết cấu,  Một biên khép kín 1 vùng 42
22. Phân đoạn bằng ngưỡng  Phương pháp đơn giản và thường được sử dụng cho phân đoạn các đối tượng trong ảnh  Ý tưởng chính: – IF value(pixel) >= threshold THEN value(pixel) = 1 – IF value(pixel) < threshold THEN value(pixel) = 0 Ảnh nhị phân  Không thuộc vào cách tiếp cận vùng – Dựa trên điểm ảnh thường cần thêm các phép xử lý sau khi phân đoạn 44
23. Ngưỡng dựa trên phân bố 1 if f(x,y) T g(,) x y  0 if f(x,y) T  Ngưỡng: toàn cục – Phù hợp cho môi trường ổn định trong ứng dụng công nghiệp 46
24. Vấn đề với ngưỡng toàn cục  Thay đổi về ánh sáng 48
25. Ví dụ với ngưỡng cục bộ 50
26. Đa ngưỡng  Sử dụng n ngưỡng n+1 vùng:  IF value(pixel) = threshold_1 && value(pixel) = threshold_n THEN value(pixel) = n  Vấn đề chính: số ngưỡng xác định thế nào ? 52
27. Giải thuật K-means  Một phương pháp để phân đoạn ảnh thành nhiều vùng (K vùng) – Các điểm được phân vào K nhóm (clusters) – Tâm của nhóm: giá trị trung bình của tất cả các phần tử trong nhóm  Số lớp (K) biết trước và cố định  Dựa trên điểm ảnh, không tính đến phân bố điểm ảnh trong không gian 54
28. Giải thuật K-means ( ) 56 Source : Christelle Scharff, Pace Univ. www.csis.pace.edu/~scharff/DMIFI/cluster9.ppt
29. Phân đoạn dựa trên điểm ảnh  Lưu ý: – Phân đoạn chỉ dựa trên giá trị điểm ảnh (cường độ sáng, màu sắc, ) – Không tính đến mối tương quan vị trí trong không gian (2D) của điểm ảnh Các vùng thu được có thể không liên thông Xử lý: Xóa bỏ các điểm ảnh rời rạc 58
30. Split-and-Merge (Chia và hợp)  Bước 1: Chia – Chia đệ quy các vùng không đồng nhất theo một tiêu chuẩn nào đó (phương sai, max,min) thành các vùng nhỏ hơn – Chia một vùng thành 4 vùng con – Tính chất của vùng con được tính toán  Bước 2: Hợp – Gộp các vùng đồng nhất lân cận nhau theo một tiêu chuẩn nào đó 60
31. Split-and-Merge ( ): Chia Đồng nhất được tính dựa trên phương sai hoặc chênh lệch giữa max và min Đầu vào 1 2 3 62 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt
32. Region growing (Phát triển vùng)  Ý tưởng: – Giải thuật bắt đầu với 1 điểm ảnh và lựa chọn các điểm ảnh lân cận để gộp lại theo tiêu chuẩn nào đó: phương sai nhỏ, – Điểm ảnh khởi tạo được gọi là hạt giống/nhân – Vùng sẽ được phát triển từ hạt giống – Các hiểu biết về ảnh cần phân đoạn được sử dụng để lựa chọn hạt giống tốt 64
33. Phát triển vùng với nhiều hạt giống 66 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt
34. Lưu ý:  Không có thuật toán tối ưu cho bài toán phân đoạn  Không có thuật toán chung cho tất cả các bài toán tùy thuộc ứng dụng  Nếu có thể tránh tránh bài toán phân đoạn  Nên thực hiện các phép tiền xử lý để phân đoạn đạt hiệu quả  Xác định rõ mục đích của phân đoạn:  các phần ta muốn nhìn thấy trong ảnh  Kết quả phân đoạn dùng để làm gì tăng hiệu quả  Đánh giá kết quả của bài toán phân đoạn là khó và 68 không khách quan
35. Phân đoạn: hạn chế  1 vùng có thể không chứa 1đối tượng Source : [Malik 2001]. 70
36. Cách tiếp cận Gestalt  Dựa trên nghiên cứu về cách quan sát của con người  Thông tin ngữ cảnh xung quanh: quan trọng 72
37. Đặc trưng cục bộ: các điểm đặc trưng  Trích chọn các điểm đặc trưng – Ảnh mức xám : Moravec (1977), Harris et Stephens (1988), Harris (1996), Susan (Smith et Brady, 1997), SIFT (1999), – Ảnh màu: Kitchen et Rosenfeld color (1998), Harris color (1998)  Xác định mô tả/đặc trưng trong vùng lân cận của điểm đặc trưng – SIFT(1999), SURF, GLOH,  Đo độ tương tự giữa tập các đặc trưng tại các điểm 74
38. SIFT Keypoint Detector 76 Source: Distinctive Image Features from Scale-Invariant Keypoints – IJCV 2004
39. SIFT Keypoint Descriptor 78 Source: Distinctive Image Features from Scale-Invariant Keypoints – IJCV 2004
40. Đối sánh 80
41. Đối sánh ( ) : đặc trưng cục bộ  Đặc trưng cục bộ: ảnh phân đoạn hoặc điểm đặc trưng – So sánh kết hợp (IRM (Intergrated Regions Matching), EMD (Earth Mover’s Distance), chiến lược bỏ phiếu ) dựa trên khoảng cách từng cặp vector tương ứng với các vùng/các điểm trên 2 ảnh – Ảnh sử dụng « khái niệm » sử dụng độ đo tương tự giữa các « khái niệm » 82 IRM:
42. Đối sánh ( ): khoảng cách IRM  Ảnh I1: biểu diễn bởi tập các vùng R1 = {r1, r2, , rm}  Ảnh I2: biểu diễn bởi tập các vùng R2 = {r’1, r’2, , r’n} – ri, r’j: đặc trưng của các vùng i, j tương ứng dIRM (I1,I2 ) d(R1,R2 ) si, jd(ri ,r' j ) i, j – si,j: ý nghĩa của ghép cặp ri và r’j s p – Tầm quan trọng của vùng i trong ảnh I1:  i, j i j 84 Source:
43. Đối sánh ( ): khoảng cách EMD 86
44. Bỏ phiếu 88 Source: Modified from slides of Valérie Gouet-Brunet
45. Truy vấn với ràng buộc không gian  I: đối tượng O1, O2  Truy vấn với ràng buộc thời gian: – O1 ở phía trên/ bên trái / phía đông bắc/ của O2 ? – O1 , O2 có giao nhau không ? – 90
46. Ràng buộc không gian: 2-D  Có thể thực hiện dựa trên phép chiếu lên x, y  Sử dụng tổ hợp các phép toán quan hệ trên không gian 1D  VD: – O1 ở bên trái của O2 nếu: hoặc B(O1[x], O2[x]) hoặc M(O1[x], O2[x]) – O1 ở phía Nam của O2 nếu: B(O1[y], O2[y]) và  hoặc D(O1[x], O2[x]) hoặc D(O2[x], O1[x])  hoặc S(O1[x], O2[x]) hoặc S(O2[x], O1[x])  hoặc F(O1[x], O2[x]) hoặc F(O2[x], O1[x])  hoặc EQ(O1[x], O2[x]) 92