Kiến trúc hệ thống tìm kiếm ảnh
Bạn đang xem 20 trang mẫu của tài liệu "Kiến trúc hệ thống tìm kiếm ảnh", để 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:
- kien_truc_he_thong_tim_kiem_anh.ppt
Nội dung text: Kiến trúc hệ thống tìm kiếm ảnh
- Multimedia Database Image database Le Thi Lan MICA International Research Center MICA Multimedia, Information, Communication & Applications UMI 2954 Hanoi University of Technology 1 Dai Co Viet - Hanoi - Vietnam
- Nội dung ◼ Kiến trúc của hệ thống tìm kiếm ảnh theo nội dung ◼ Ảnh và biểu diễn ảnh ◼ Phân đoạn ảnh MICA 2010 2
- Kiến trúc hệ thống tìm kiếm ảnh Hiển thị kết quả Trích chọn Đối sánh đặc trưng Phân đoạn CSDL chỉ số Trích chọn Đánh chỉ số đặc trưng CSDL Phân đoạn MICA 2010 3
- Kiến trúc hệ thống tìm kiếm ảnh Hiển thị kết quả Trích chọn Đối sánh đặc trưng Phân đoạn CSDL chỉ số Trích chọn Đánh chỉ số đặc trưng CSDL Phân đoạn MICA 2010 4
- Kiến trúc hệ thống tìm kiếm ảnh Hiển thị kết quả Trích chọn Học và Đối sánh đặc trưngphân loại Phân đoạn CSDL chỉ số Trích chọn Học và Đánh chỉ số đặc trưng phân loại CSDL Phân đoạn MICA 2010 5
- Nội dung ◼ Kiến trúc của hệ thống tìm kiếm ảnh theo nội dung ◼ Ảnh và biểu diễn ảnh ◼ Phân đoạn ảnh ◼ Chiến lược đối sánh MICA 2010 6
- Ảnh và lưu trữ Mức xám - 8 bits: 0 - đen 255 - trắng 64 60 69 100 149 151 176 182 179 65 62 68 97 145 148 175 183 181 65 66 70 95 142 146 176 185 184 66 66 68 90 135 140 172 184 184 66 64 64 84 129 134 168 181 182 59 63 62 88 130 128 166 185 180 60 62 60 85 127 125 163 183 178 62 62 58 81 122 120 160 181 176 63 64 58 78 118 117 159 180 176 MICA 2010 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 7
- Ảnh và lưu trữ 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 MICA 2010 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 8
- Ảnh và lưu trữ ◼ Ảnh là tín hiệu 2D (x,y) ◼ Về mặt toán học: ◼ Ảnh là một ma trận biểu diễn tín hiệu ◼ Đối với người dùng: ◼ Ảnh chứa các thông tin về ngữ nghĩa MICA 2010 9
- Phân loại ảnh ◼ Ảnh tự nhiên – thu nhận từ các thiết bị ◼ camera, microscope, tomography, infrared, satellite, ◼ Ảnh nhân tạo – ◼ Đồ họa máy tính (computer graphics), thực tại ảo (virtual reality) MICA Ảnh tự nhiên ảnh nhân tạo Ảnh nhân tạo 2010 10
- Phân loại ảnh Ảnh mức xám Ảnh nhị phân Ảnh màu I(x,y) [0 255] I(x,y) {0 , 1} IR(x,y) IG(x,y) IB(x,y) MICA 2010 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 11
- Ả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 MICA 2010 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 12
- Nội dung ◼ Ảnh và biểu diễn ảnh ◼ Phân đoạn ảnh ◼ Tìm kiếm ảnh dựa vào nội dung MICA 2010 13
- Phân đoạn ảnh là gì? ◼ Phân đoạn ảnh cho phép chia một ảnh thành một (một số) vùng ◼ Các vùng tương ứng với các đối tượng trong ảnh ◼ Phân đoạn có liên quan đến nhận dạng ◼ Xác định đối tượng nào có ở trong ảnh? MICA 2010 14 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt
- Mục tiêu của phân đoạn ảnh ◼ Trích chọn các thành phần trong ảnh ◼ Ứng dụng cho các sử lý sau ◼ Phân tích nội dung của ảnh ◼ Các mặt nạ cho ảnh thường được xây dựng ◼ Một mặt nạ và một thành phần liên thông MICA 2010 Source : Pascal Bertolino, LIS, www.lis.inpg.fr/pages_perso/bertolino/ 15
- Lợi ích của mặt nạ phân đoạn ◼ Mặt nạ (vùng hoặc đối tượng) cho phép phân tích nội dung của ảnh dễ hơn ◼ Phân tích nội dung của từng vùng MICA 2010 16
- Phân đoạn ◼ Phân đoạn dựa vào: ◼ Sự không liên tụcc: tương ứng với các cạnh ◼ Thay đổi đột ngột, biên giữa các vùng ◼ Đồng nhất: tương ứng với các vùng ◼ Cùng màu sắc, kết cấu, mức xám, ◼ Phân đoạn nhằm chia một ảnh thành các vùng và/hoặc biên ◼ Một biên khép kín tương ứng với một vùng MICA 2010 17
- Phân đoạn ◼ Cách tiếp cận vùng (Region approach) ◼ Tìm các vùng đồng nhất trong ảnh ◼ Cách tiếp cận theo biên (Edge approach) ◼ Phát hiện sự không liên tục trong ảnh ◼ Cách kết hợp MICA 2010 18
- Cách tiếp cận kết hợp Một biên khép kín tuơng đương với 1 vùng MICA 2010 Source : Thomas Boudier, UPMC, www.snv.jussieu.fr/~wboudier/ens/cours_inb2/06_Segmentation.pdf 19
- Ngưỡng (Thresholding) MICA 2010 20
- Phân đoạn dựa trên ngưỡng ◼ Là 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 ◼ Không thuộc vào cách tiếp cận vùng ◼ Dựa trên điểm ảnh ◼ Thường sử dụng để xác định các vùng ◼ Cần một só thao tác xử lý thêm sau khi phân đoạn ◼ Ngưỡng ◼ Toàn cục: một ngưỡng cho toàn bộ ảnh ◼ Cục bộ: một ngưỡng cho 1 vùng của ảnh ◼ Thích nghi: ngưỡng được lựa chọn phù hợp với MICA từng ảnh hoặc từng vùng của ảnh 2010 21
- Phân đoạn dựa trên ngưỡng ◼ Ý tưởng chính: ◼ IF value(pixel) >= threshold THEN value(pixel) = 1 ◼ IF value(pixel) < threshold THEN value(pixel) = 0 ◼ Kết quả là ảnh nhị phân ◼ Có thể chọn n ngưỡng để chia ảnh thành n+1 lớp ◼ Vấn đề: Lựa chọn ngưỡng MICA 2010 22
- Ngưỡng dựa trên phân bố 1 if f(x,y) T g(,) x y = 0 if f(x,y) T MICA 2010 Source : 23
- Ngưỡng dựa trên phân bố ◼ Ngưỡng toàn cục ◼ Giá trị trung bình ◼ Môi trường ổn định ◼ Trong các ứng dụng công nghiệp MICA 2010 24
- Ngưỡng dựa trên phân bố ◼ Ưu điểm ◼ Đơn giản, nhanh ◼ Nhược điểm ◼ Biết trước số lớp ◼ Các vùng không phù hợp sẽ xuất hiện (không có ràng buộc về không gian) MICA 2010 25
- Đa ngưỡng ◼ n ngưỡng cho phép chia ảnh thành n+1 lớp: ◼ IF value(pixel) < threshold_1 ◼ THEN value(pixel) = 0 ◼ IF value(pixel) threshold_1 && value(pixel) < threshold_2 ◼ THEN value(pixel) = 1 ◼ ◼ IF value(pixel) threshold_n ◼ THEN value(pixel) = n ◼ Vấn đề: Cần bao nhiêu ngưỡng MICA 2010 26
- Đa ngưỡng dựa trên histogram 2 if f(x,y)>T2 g( x , y )= 1 if f(x,y) T21 f ( x , y ) T 0 if f(x,y) T1 MICA 2010 27
- Giá trị của ngưỡng ◼ Ngưỡng toàn cục ◼ Làm thế nào để xác định giá trị của T ? ◼ Bằng thử nghiệm ◼ Giá trị trung bình mức xám ◼ Giá trị trung bình giữa giá trị max và min ◼ Giá trị cho phép cân bằng các vùng của phân bố - xác định ngưỡng tự động MICA 2010 28
- Lựa chọn ngưỡng ◼ 2 phân bố cho ảnh và đối tượng (ví dụ phân bố Gaussian) ◼ Xác định lỗi trong lớp 1 và lớp 2 ◼ Tìm ngưỡng T để cho lỗi là bé nhất Class 1 Class 2 E 1 E2 MICA 2010 Source : www.iro.umontreal.ca/~dift2730/ T 29
- Ví dụ ◼ Giải thuật: ◼ Khởi tạo giá trị T (trung bình, điểm giữa, ) ◼ Xác định 2 nhóm điểm ảnh G1 nếu f(x,y) > T và G2 nếu f(x,y) T ◼ Tính trung bình về mức xám của G1 và G2 -> μ1 và μ2 ◼ Tính giá trị mới của T T = 1/2 (μ1 + μ2) ◼ Lặp lại cho đến khi T ổn định ◼ Các giải thuật khác (k-means). Không có giải thuật duy nhất cho tất cả các ứng dụng MICA 2010 30 30
- Ví dụ 2: Giải thuật Otsu (bài tập lớn) MICA 2010 31
- Các vấn đề đối với ngưỡng toàn cục ◼ Thay đổi về ánh sáng MICA 2010 32
- Các vấn đề đối với ngưỡng toàn cục ◼ Sử dụng ngưỡng cục bộ thích nghi MICA 2010 33
- Ví dụ về ngưỡng thích nghi ◼ Chia một ảnh thành các ảnh nhỏ và lựa chọn ngưỡng cho từng ảnh ◼ Xác định kích thước của ảnh nhỏ ◼ Trước khi chia, kiểm tra giá trị phương sai để xác định ảnh được chia có ít nhất 2 vùng ◼ Ví dụ: nếu variance<100 thì không xác định ngưỡng MICA 2010 34
- Ví dụ về ngưỡng thích nghi Tất cả 4 vùng ảnh trong 4 góc không cần xác định ngưỡng vì variance<100 MICA 2010 35
- Ví dụ về ngưỡng thích nghi MICA 2010 36
- Ví dụ về ngưỡng thích nghi MICA 2010 37
- Giải thuật K-means MICA 2010 38
- k-means ◼ Chia các điểm thành k nhóm (clusters) ◼ k là cố định và đã được xác định trước ◼ Xác định tâm của nhóm là giá trị trung bình của tất cả các phần tử trong nhóm MICA 2010 Source : Christelle Scharff, Pace Univ. www.csis.pace.edu/~scharff/DMIFI/cluster9.ppt 39
- k-means 4 bước: 1. Chia dữ liệu thành k tập không rỗng 2. Tính tâm của các nhóm 3. Đưa dữ liệu vào nhóm gần nhất 4. Quay lại bước 2 Giải thuật dừng khi tất cả các nhóm ổn định MICA 2010 Source : Christelle Scharff, Pace Univ. www.csis.pace.edu/~scharff/DMIFI/cluster9.ppt 40
- Ví dụ MICA 2010 Source : Christelle Scharff, Pace Univ. www.csis.pace.edu/~scharff/DMIFI/cluster9.ppt 41
- Phân đoạn sử dụng k-means Ảnh đầu vào K-means trên K-means trên ảnh mức xám ảnh màu Kmeans áp dụng trên mức xám hoặc màu MICA 2010Source : D.A. Forsyth and J. Ponce. Computer Vision : A Modern Approach. Prentice-Hall, 2002. 42
- Phân đoạn sử dụng k-means Ảnh đầu vào K-means trên màu K-means với 11 nhóm MICA 2010 43
- Tiếp theo K-means trên màu cho 11 nhóm MICA 2010 44 44
- Phân đoạn dựa trên điểm ảnh hay trên vùng ◼ Các phương pháp phân đoạn dựa trên ngưỡng chủ yếu dựa trên điểm ảnh ◼ Không đưa ra được các vùng liên thông ◼ Để xác định được các vùng ◼ Xóa các điểm ảnh rời rạc MICA 2010 45
- Phân đoạn dựa trên vùng Chia và hợp (Split-and-merge) MICA 2010 46 46
- Chia và hợp ◼ Chia (bước1) ◼ 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 ◼ Kết hợp (bước 2) ◼ Gộp các vùng đồng nhất lân cận nhau theo một tiêu chuẩn nào đó MICA 2010 47
- Bước chia ◼ Ảnh có thể biểu diễn thành 1 cây ◼ Nút gốc là toàn bộ ảnh ◼ Mỗi nút lá F được chia thành 4 phần nều F không đồng nhất ◼ 4 phần này sẽ trở thành lá của F ◼ Giải thuật tiếp tục cho đến khi không còn vùng không đồng nhất nào MICA 2010 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt 48
- Bước 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 MICA 2010 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt 49
- Bước kết hợp Cây tứ phân Nối các vùng đồng nhất lân cận MICA 2010 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt 50
- Ví dụ về phân đoạn chia-kết hợp MICA 2010 51
- Ví dụ về phân đoạn chia-kết hợp MICA 2010 Sử dụng nhiều ngưỡng xác định sự đồng nhất 52 52
- Phân đoạn dựa trên vùng Phát triển vùng (Region growing) MICA 2010 53
- Phát triển vù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 theo tiêu chuẩn: ◼ Phương sai nhỏ ◼ Mức xác dưới 1 ngưỡng ◼ Điểm ảnh khởi tạo được gọi là hạt giống ◼ 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 MICA 2010 54
- Phát triển vùng ◼ Bắt đầu từ một hạt giống và thêm các điểm ảnh lân cận theo một tiêu chuẩn ◼ Hạt giống được chọn thủ công hoặc tự động ◼ Ví dụ: tự động lựa chọn hạt giống trong vùng có độ đồng nhất cao Ảnh Hạt giống Phát triển vùng Vùng cuối cùng MICA 2010 Source : Jean-Christophe Baillie, ENSTA, uei.ensta.fr/baillie/assets/ES322%20-%20Segmentation.ppt55 55
- Phát triển vùng với nhiều «hạt giống» MICA 2010 56 56
- Phân đoạn dựa trên vùng Watershed MICA 2010 57 57
- Phân đoạn Watershed Xem ảnh như hình dạng 3D bằng cách sử dụng mức xám như chiều thứ 3 Ảnh 2D Mô hình trong 3D MICA 2010 Source : 58
- Phân đoạn Watershed Lật ngược để tạo các «hộc» MICA 2010 59
- Phân đoạn Watershed Đổ đầy nước vào các «hộc» MICA 2010 60
- Phân đoạn Watershed MICA 2010 61
- Phân đoạn Watershed MICA 2010 62
- Tiêu chuẩn, tham số ◼ Tất cả các giải thuật đều cần tiêu chuẩn, tham số ◼ Không có tham số chung, phải lựa chọn tùy vào ứng dụng Ngưỡng ◼ Giá trị cố định (hằng số) ◼ Giá trị tương đối (%, trung bình, ) ◼ Giá trị được tính toán bằng thuật toán MICA 2010 63
- Lời khuyên cho bài toán phân đoạn ◼ Bài toán phân đoạn hiện tại vẫn chưa được giải quyết hoàn chỉnh ◼ Không có phương pháp chung cho tất cả các ảnh ◼ Nếu ứng dụng cho phép tránh bài toán phân đoạn thì không thực hiện phân đoạn ◼ Các bước tiền xử lý, lựa chọn thiết bị, kiểm soát các điều kiện về ánh sáng, môi trường phù hợp cho phép phân đoạn thực hiện dễ và hiệu quả hơn MICA 2010 64
- Lời khuyên cho bài toán phân đoạn ◼ Đánh giá kết quả phân đoạn khó và không khách quan ◼ Xác định mục đích của phân đoạn: Các thành phần mà ta muốn nhìn thấy trong ảnh? ◼ Vùng toàn cục hay các chi tiết nhỏ? ◼ Xác định trước ứng dụng của kết quả phân đoạn ◼ Cho phép xác định mức độ chính xác MICA 2010 65
- Cách chúng ta quan sát 1 ảnh 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 MICA 2010 Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 66
- Hạn chế của phân đoạn Phân đoạn ảnh không cho phép tìm được tất cả cả đối tượng MICA 2010 67
- Phân đoạn và nhóm Ngày nay người ta ít nói về phân đoạn ảnh (chia 1 ảnh thành các vùng) mà nói nhiều đến nhóm điểm ảnh (nhóm các điểm ảnh tương tự nhau mà không quan tâm đến nội dung của vùng) Source : [Malik 2001]. MICA 2010 68
- Ví dụ MICA 2010 69 69
- Cách tiếp cận Gestalt MICA 2010 70
- Cách tiếp cận Gestalt ◼ Dựa trên nghiên cứu về quá trình quan sát của con người ◼ Các thông tin về ngữ cảnh xung quanh là quan trọng MICA 2010 71
- Cách tiếp cận Gestalt ◼ Các tiêu chuẩn nhóm: ◼ Proximity: các đối tượng gần nhau ◼ Similarity: các đối tượng giống nhau ◼ Common faith: các đối tượng có kiểu di chuyển giống nhau ◼ Common region: các đối tượng trong cùng 1 vùng ◼ Parallel: các đường song song ◼ Closing: các cung và đối tượng có hình dạng đóng ◼ Symmetry: các cung và đối tượng đối xứng ◼ Continuity: các cung và đối tượng kéo dài MICA 2010 72
- Cách tiếp cận Gestalt MICA 2010 73
- Cách tiếp cận Gestalt ◼ Các câu hỏi đặt ra trong cách tiếp cận Gestalk: ◼ Đặt các luật vào trong giải thuật? ◼ Làm thế nào để sinh các giả thuyết cho đối tượng? MICA 2010 74
- Nội dung ◼ Ảnh và cách lưu trữ ảnh ◼ Phân đoạn ảnh ◼ Các chiến lược đối sánh ảnh MICA 2010 75
- Chiến lược đối sánh ảnh Hiển thị kết quả Trích chọn Đối sánh đặc trưng Phân đoạn CSDL chỉ số Trích chọn Đánh chỉ số đặc trưng CSDL Phân đoạn MICA 2010 76
- Chiến lược đối sánh ảnh Điều kiện Chiến lược so sánh Ảnh không phân đoạn, So sánh dựa trên độ đo phù hợp vector đặc trưng toàn cục với đặc trưng Ảnh không phân đoạn, Chiến lược so sánh kết hợp (IRM, một số vector đặc trưng EMD, ) dựa trên khoảng cách cục bộ được tính (ví dụ từng cặp vector đặc trưng của các keypoints và đặc trưng điểm trên 2 ảnh SIFT) Ảnh phân đoạn, không Chiến lược so sánh kết hợp xác định concept, một hợp (IRM, EMD, ) dựa trên đoạn sử dụng vector khoảng cách từng cặp vector đặc trưng của các vùng trên 2 ảnh Ảnh có xác định concept Sử dụng độ đo tương tự giữa các concept MICA 2010 77
- Blobworld ◼ Truy vấn dạng “like-blob-1” MICA 2010 78
- IRM MICA 2010 Source: SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries 79
- EMD NM d( I12 , I ) min fij d ( R i , R j ) I1 : {(Ri, wi), i=1, N} ij==11 I : {(R , w ), j=1,M} 2 j j fij 0 D(I1, I2) =??? N fwij j i=1 D(R ,R ) i j M N ≠ M fwij i j=1 NMNM fij= min( w i , w j ) i=1 j = 1 i = 1 j = 1 NM * fij d(,) R i R j ij==11 dEMD (,) I12 I = NM * fij MICA ij==11 2010 80
- Kiến trúc hệ thống tìm kiếm ảnh Hiển thị kết quả Trích chọn Học và Đối sánh đặc trưngphân loại Phân đoạn CSDL chỉ số Trích chọn Học và Đánh chỉ số đặc trưng phân loại CSDL Phân đoạn MICA 2010 81
- MICA 2010 82