Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu phương pháp tra cứu ảnh sử dụng phân cụm gia tăng với phản hồi liên quan

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:62

Thêm vào BST

Báo xấu

37
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhiệm vụ chính của luận văn là nắm vững kiến thức tổng quan của lĩnh vực xử lý ảnh, đi sâu nghiên cứu lĩnh vực tra cứu ảnh dựa vào nội dung, tìm hiểu một số thuật toán học không giám sát, nghiên cứu thuật toán phân cụm gia tăng và đưa vào hệ thống tra cứu ảnh dựa vào nội dung. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu phương pháp tra cứu ảnh sử dụng phân cụm gia tăng với phản hồi liên quan

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN TOÀN NGHIÊN CỨU PHƯƠNG PHÁP TRA CỨU ẢNH SỬ DỤNG PHÂN CỤM GIA TĂNG VỚI PHẢN HỒI LIÊN QUAN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN, 2018 i
LỜI CẢM ƠN Luận văn này được hoàn thành với sự hướng dẫn tận tình của PGS.TS Nguyễn Hữu Quỳnh – Khoa Công nghệ thông tin - Đại học Điện lực. Trước tiên tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới PGS.TS Nguyễn Hữu Quỳnh người đã tận tình hướng dẫn, động viên giúp đỡ tôi trong suốt thời gian thực hiện luận văn. Tôi cũng xin chân thành cảm ơn các thầy cô trong trường Đại học Công Nghệ thông tin và Truyền thông – Đại học Thái Nguyên, tạo điều kiện thuận lợi cho tôi hoàn thành tốt khóa học. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học CHK15A đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác trong suốt khoá học. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, người thân, bạn bè đã động viên, khuyến khích và hỗ trợ cần thiết để tôi hoàn thành luận văn này. Mặc dù rất cố gắng, song luận văn này không thể tránh khỏi những thiếu sót, kính mong được sự chỉ dẫn của các quý thầy cô và các bạn. Thái Nguyên, ngày 2 tháng 5 năm 2018 Người viết Nguyễn Văn Toàn ii
LỜI CAM ĐOAN Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Thái Nguyên, ngày 2 tháng 5 năm 2018 Người cam đoan Nguyễn Văn Toàn iii
MỤC LỤC LỜI CẢM ƠN ........................................................................................................ i LỜI CAM ĐOAN................................................................................................. iii MỤC LỤC ............................................................................................................ iv DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT....................................... vi DANH MỤC CÁC BẢNG BIỂU ....................................................................... vii DANH MỤC CÁC HÌNH .................................................................................. viii MỞ ĐẦU ............................................................................................................... 1 CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG VỚI PHẢN HỒI LIÊN QUAN ..................................................................................... 4 1.1. Tổng quan về tra cứu ảnh dựa vào nội dung .............................................. 4 1.1.1. Vấn đề tra cứu ảnh dựa vào nội dung ................................................. 4 1.2. Tra cứu ảnh sử dụng phản hồi liên quan .................................................. 14 1.3. Vấn đề phân cụm[1] ................................................................................. 16 1.3.1. Thuật toán K-Means.......................................................................... 20 1.3.2. Phân cụm phân cấp ........................................................................... 21 1.3.3. Phân cụm dựa vào mật độ ................................................................. 23 1.3.4. Phân cụm dựa vào mô hình ............................................................... 23 1.3.5. Phân cụm dựa vào đồ thị ................................................................... 26 1.4. Tiểu kết chương 1. ................................................................................... 26 CHƯƠNG 2: PHƯƠNG PHÁP TRA CỨU ẢNH VỚI PHẢN HỒI LIÊN QUAN SỬ DỤNG PHÂN CỤM GIA TĂNG ................................................................. 27 2.1. Tra cứu ảnh với ngữ nghĩa mức cao ........................................................ 27 2.1.1. Giới thiệu về tra cứu ảnh với ngữ nghĩa mức cao............................. 27 2.1.2. Khoảng cách ngữ nghĩa..................................................................... 28 2.1.3. Phản hồi liên quan ............................................................................. 29 2.2. Tra cứu ảnh với phản hồi liên quan ......................................................... 31 2.3. Kỹ thuật phân tích phân biệt tuyến tính (LDA-Linear Discriminant Analysis).......................................................................................................... 32 iv
2.3.1. Định nghĩa về LDA ........................................................................... 32 2.3.2 Tính toán phương sai between-class (𝑺𝑩) ......................................... 32 2.3.3 Tính phương sai within-class (𝑺𝒘) .................................................... 34 2.3.4 Xây dựng không gian thấp chiều ....................................................... 36 2.3.5. Sơ đồ phương pháp tra cứu ảnh sử dụng phân cụm gia tăng trong phản hồi liên quan ................................................................................................ 37 2.4. Tiểu kết chương 2..................................................................................... 39 CHƯƠNG 3: CHƯƠNG TRÌNH THỬ NGHIỆM ............................................. 40 3.1. Giới thiệu bài toán tra cứu ảnh dựa vào nội dung .................................... 40 3.2. Môi trường thực nghiệm. ......................................................................... 41 3.2.1. Cơ sở dữ liệu ảnh. ............................................................................. 42 3.2.2. Vec-tơ đặc trưng................................................................................ 43 3.2.3. Tập tin cậy nền .................................................................................. 44 3.2.4. Cấu hình đề xuất thiết bị chạy thực nghiệm ..................................... 44 3.3. Đánh giá kết quả thực nghiệm. ................................................................ 44 3.3.1. Chiến lược mô phỏng phản hồi liên quan. ........................................ 44 3.3.2. Kết quả đánh giá................................................................................ 45 3.4. Giao diện hệ thống ................................................................................... 47 3.5. Tiểu kết chương 3. ................................................................................... 51 KẾT LUẬN ......................................................................................................... 52 TÀI LIỆU THAM KHẢO ................................................................................... 53 v
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Từ viết tắt Diễn giải CBIR Tra cứu ảnh dựa vào nội dung. RBIR Tra cứu ảnh dựa vào vùng CSDL Cơ sở dữ liệu CRT Mẫu vùng cấu tạo EMD Earth Mover Distance IRM Lược đồ đối sánh vùng tích hợp DPF Hàm khoảng cách động một phần MRMD Khoảng cách đa tạp đa phân giải RF Phản hồi liên quan vi
DANH MỤC CÁC BẢNG BIỂU Bảng 3.1. Bảng phân bố tập ảnh Corel................................................................ 42 Bảng 3.2. Các loại đặc trưng. .............................................................................. 43 Bảng 3.3. Bảng cấu hình đề xuất thiết bị chạy thực nghiệm. ............................. 44 Bảng 3.4. Bảng kết quả của các phương pháp .................................................... 46 vii
DANH MỤC CÁC HÌNH Hình 1.1. Kiến trúc tổng quan của hệ thống tra cứu ảnh dựa vào nội dung. ........ 5 Hình 1.2. Không gian màu RGB. .......................................................................... 8 Hình 1.3. Không gian màu HSV. .......................................................................... 9 Hình 1.4. Lược đồ của một hệ thống CBIR với RF. ........................................... 16 Hình 1.5. Các tập dữ liệu và các cụm ................................................................. 17 Hình 1.6. Các tập dữ liệu không thích hợp với K-Means. .................................. 21 Hình 1.7 Phân cụm phân cấp tập dữ liệu D={a,b,c,d,e} ..................................... 22 Hình 2.1. Dịch chuyển điểm truy vấn. ................................................................ 29 Hình 2.2. Hình dạng lồi (đa điểm). ..................................................................... 30 Hình 2.3. Hình dạng lõm (đa điểm). ................................................................... 30 Hình 2.4. Tra cứu ảnh dựa vào nội dung với phản hồi liên quan. ...................... 31 Hình 2.5. Các bước được trực quan hóa để tính một không gian con chiều thấp hơn của kỹ thuật LDA. ........................................................................................ 33 Hình 2.6. Sơ đồ tra cứu ảnh sử dụng phân cụm gia tăng. ................................... 38 Hình 3.1. Mô hình tổng quát của hệ thống.......................................................... 41 Hình 3.2. Biểu đồ so sánh kết quả thực nghiệm ................................................. 46 Hình 3.3. Giao diện chính của hệ thống. ............................................................. 47 Hình 3.4. Chọn tập dữ liệu ảnh / đặc trưng ......................................................... 48 Hình 3.5. Chọn ảnh truy vấn khởi tạo. ................................................................ 48 Hình 3.6. Tra cứu với truy vấn khởi tạo 84003, 84004, 84008 thuộc lớp 840. .. 48 Hình 3.7. Kết quả phân cụm tập huấn luyện. ...................................................... 49 Hình 3.8. Công cụ tra cứu và phân cụm LDA. ................................................... 49 Hình 3.9. Kết quả tra cứu phản hồi liên quan. .................................................... 50 Hình 3.10. Kết quả phân cụm gia tăng. ............................................................... 50 Hình 3.11. Kết quả tra cứu sau khi sử dụng phân cụm gia tăng. ........................ 51 viii
MỞ ĐẦU Tra cứu ảnh dựa vào nội dung (CBIR-Content Based Image Retrieval) đã nhận được nhiều sự quan tâm trong thập kỷ qua, do nhu cầu xử lý hiệu quả lượng dữ liệu đa phương tiện khổng lồ và tăng nhanh chóng. Nhiều hệ thống CBIR đã được phát triển, gồm QBIC, Photobook, MARS, VisualSEEK, SIMPLIcity và những hệ thống khác. Trong một hệ thống CBIR tiêu biểu, các đặc trưng ảnh trực quan mức thấp (tức là màu, kết cấu và hình dạng) được trích rút tự động cho mục tiêu đánh chỉ số và mô tả ảnh. Để tìm kiếm các ảnh mong muốn, người dùng đưa một ảnh làm mẫu và hệ thống trả lại một tập các ảnh tương tự dựa vào các đặc trưng được trích rút. Là một vấn đề quan trọng trong CBIR, độ đo tương tự lượng hóa sự giống nhau về nội dung giữa từng cặp ảnh. Phụ thuộc vào kiểu đặc trưng được trích rút mà chúng ta lựa chọn độ đo tương tự thích hợp. Tất cả các kỹ thuật tra cứu ảnh dựa vào nội dung hiện nay đều thừa nhận thông tin tương hỗ giữa độ đo tương tự ảnh và ngữ nghĩa của ảnh. Bằng nhiều cách khác nhau, độ đo tương tự cố gắng nắm được một khía cạnh nào đó của nội dung ảnh, đó là ngữ nghĩa kế thừa từ độ tương tự hay đặc trưng mức thấp. Tuy nhiên, ngữ nghĩa kế thừa từ độ tương tự nhiều khi không giống với khái niệm mức cao được truyền tải bởi một ảnh (ngữ nghĩa của ảnh). Đó chính là khoảng cách ngữ nghĩa, nó phản ánh sự khác biệt giữa năng lực mô tả hạn chế của đặc trưng trực quan mức thấp và khái niệm mức cao. Các kỹ thuật trong việc rút ngắn “khoảng cách ngữ nghĩa” gồm có 5 loại chính: (1) sử dụng bản thể đối tượng để xác định các khái niệm mức cao, (2) sử dụng các công cụ học máy để kết hợp các đặc trưng mức thấp với các khái niệm truy vấn, (3) đưa phản hồi liên quan vào lặp tra cứu cho học ý định của người dùng, (4) sinh ra mẫu ngữ nghĩa để hỗ trợ tra cứu ảnh mức cao, (5) Cách sử dụng cả nội dung trực quan của các ảnh và thông tin văn bản thu được từ Web cho tra cứu ảnh trên Web. 1
Từ những nhận định trên và được sự gợi ý của giáo viên hướng dẫn, tôi quyết định chọn đề tài: “Nghiên cứu phương pháp tra cứu ảnh sử dụng phân cụm gia tăng với phản hồi liên quan”. Đề tài sẽ kết hợp hai hướng tiếp cận (2) và (3), đưa phản hồi liên quan của người dùng vào quá trình tra cứu và sử dụng phương pháp phân cụm gia tăng để phân cụm tập ảnh phản hồi nhằm biểu diễn nhu cầu thông tin người dùng hiệu quả. Phản hồi liên quan là một quá trình trực tuyến mà cố gắng học mục đích của người dùng trong quá trình tra cứu, là một công cụ mạnh được sử dụng truyền thống trong các hệ thống tra cứu thông tin. Nó được giới thiệu đối với CBIR khoảng đầu những năm 1990, với mục đích mang người dùng vào lặp tra cứu để giảm khoảng cách ngữ nghĩa giữa những gì mà truy vấn biểu diễn và những gì người dùng nghĩ. Bằng việc tiếp tục học thông qua tương tác với các người dùng cuối, phản hồi liên quan đã được chỉ ra là cung cấp cải tiến hiệu năng đáng kể trong các hệ thống CBIR. Phân cụm là một phương pháp học không giám sát để tạo thành các nhóm hay các cụm dữ liệu. Lý thuyết phân cụm giả thuyết rằng “các đối tượng gần nhau có xu hướng liên quan tới cùng một yêu cầu”. Đã có nhiều thuật toán thực hiện việc phân cụm như: K-mean, K-medoid, EM…Tuy nhiên, các thuật toán này thường được gọi là phân cụm ngoại tuyến (off-line), tức là, các thuật toán này thực hiện phân cụm trên toàn bộ cơ sở dữ liệu ảnh đã có sẵn (gồm rất nhiều ảnh), mỗi khi có ảnh mới bổ sung vào, quá trình lại phải phân cụm lại từ đầu. Các thuật toán ngoại tuyến không phù hợp trong các trường hợp đòi hỏi trực tuyến (on-line), chẳng hạn, trường hợp mà áp dụng trên một tập ảnh nhỏ (là kết quả của một lần thực hiện tra cứu) nhưng đòi hỏi phân cụm ngay lập tức trong khi vẫn còn nhiều ảnh cần được bổ sung và phân cụm tiếp theo không cần phải tiến hành với dữ liệu đã được phân cụm trước đó. Thuật toán mà đáp ứng trường hợp trực tuyến này phải có tính chất “gia tăng” hay gọi là phân cụm gia tăng. 2
Nhiệm vụ chính của luận văn là nắm vững kiến thức tổng quan của lĩnh vực xử lý ảnh, đi sâu nghiên cứu lĩnh vực tra cứu ảnh dựa vào nội dung, tìm hiểu một số thuật toán học không giám sát, nghiên cứu thuật toán phân cụm gia tăng và đưa vào hệ thống tra cứu ảnh dựa vào nội dung. Cài đặt chương trình thử nghiệm đánh giá, so sánh hiệu quả của hệ thống tra cứu ảnh dựa vào nội dung sử dụng phân cụm phổ với một số hệ thống tra cứu ảnh điển hình khác. Bố cục luận văn: Chương 1: Tổng quan về tra cứu ảnh dựa vào nội dung với phản hồi liên quan Chương 2: Phương pháp tra cứu ảnh với phản hồi liên quan sử dụng phân cụm gia tăng. Chương 3: Chương trình thử nghiệm. 3
CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG VỚI PHẢN HỒI LIÊN QUAN 1.1. Tổng quan về tra cứu ảnh dựa vào nội dung 1.1.1. Vấn đề tra cứu ảnh dựa vào nội dung Tra cứu ảnh dựa vào nội dung là việc áp dụng kỹ thuật thị giác máy tính vào vấn đề tìm kiếm hình ảnh, tức là vấn đề tìm kiếm hình ảnh kỹ thuật số trong các cơ sở dữ liệu (lớn). Tra cứu ảnh dựa vào nội dung sử dụng những nội dung thị giác như màu sắc, hình dạng, kết cấu, không gian để biểu diễn ảnh. Các nội dung thị giác của ảnh được trích rút và mô tả bằng các véc tơ đặc trưng đa chiều có dạng véc tơ đặc trưng của cơ sở dữ liệu. Khởi đầu cho việc tra cứu ảnh, người dùng cung cấp một ảnh mẫu cho hệ thống tra cứu. Hệ thống này sẽ chuyển đổi những ảnh mẫu này thành các véc tơ đặc trưng và so sánh với khoảng cách/độ tương tự của các véc tơ đặc trưng của những ảnh trong cơ sở dữ liệu để tính toán và đưa ra kết quả là bức ảnh có độ tương tự cao nhất. Hệ thống tra cứu ảnh dựa vào nội dung 1.1.1.1. Các chức năng của hệ thống tra cứu ảnh dựa vào nội dung Một hệ thống tra cứu ảnh dựa vào nội dung (CBIR – Content Based Image Retrieval) có các chức năng chính như sau: 1) Trích rút đặc trưng và biểu diễn các nội dung của các nguồn được phân tích theo cách thích hợp cho so sánh các truy vấn sử dụng (không gian của nguồn thông tin được biến đổi thành không gian đặc trưng cho mục tiêu so sánh nhanh trong bước tiếp theo). Bước này thông thường cần rất nhiều thời gian do nó phải xử lý lần lượt tất cả thông tin nguồn (các ảnh) trong cơ sở dữ liệu. Tuy nhiên, bước này được thực hiện chỉ một lần và có thể được thực hiện ngoại tuyến. 2) Phân tích truy vấn của người sử dụng và biểu diễn chúng dưới dạng thích hợp để đối sánh với cơ sở dữ liệu nguồn. Bước này là tương tự với bước trước, nhưng chỉ áp dụng với ảnh cần truy vấn. 3) Thực hiện so sánh các truy vấn tìm kiếm với thông tin có trong cơ sở dữ liệu được lưu trữ để tra cứu thông tin liên quan theo một cách hiệu quả. Bước này 4
được thực hiện trực tuyến và yêu cầu là phải đáp ứng rất nhanh. Các kỹ thuật đánh chỉ số hiện đại có thể được sử dụng để tổ chức lại không gian đặc trưng nhằm tăng tốc quá trình đối sánh. 4) Thực hiện các điều chỉnh cần thiết trong hệ thống (thường là điều chỉnh các tham số trong máy đối sánh) dựa trên phản hồi từ người sử dụng và/hoặc các ảnh được tra cứu. 1.1.1.2. Một số hệ thống CBIR tiêu biểu Thực hiện ngoại tuyến Cơ sở dữ Cơ sở dữ liệu liệu ảnh đặc trưng Trích rút đặc trưng Đánh chỉ số So sánh độ tương tự Người dùng Tạo Véc tơ Các kết quả Đầu ra truy vấn đặc trưng tra cứu Phản hồi liên quan Hình 1.1. Kiến trúc tổng quan của hệ thống tra cứu ảnh dựa vào nội dung. Một hệ thống CBIR sẽ thực hiện truy vấn ảnh dựa trên việc tự động rút trích các thông tin đặc trưng hình ảnh như: màu sắc, kết cấu, hình dạng, vị trí. Các nhà nghiên cứu đã đưa ra nhiều phương pháp với những cách tiếp cận khác nhau; do đó rất nhiều hệ thống truy vấn ảnh dựa trên nội dung đã ra đời như: QBIC, BlobWorld, VisualSEEk, MARS, Photobook, Virage, Netra, SIMPLIcity, NEC PicHunter… Dưới đây xin điểm qua một số hệ thống CBIR tiêu biểu. 5
1) Hệ thống QBIC Hệ thống truy vấn ảnh theo nội dung QBIC (Query By Image Content) được nghiên cứu và phát triển bởi nhóm nghiên cứu Visual Media Management thuộc công ty IBM, là hệ thống tra cứu ảnh thương mại được phát triển từ rất sớm. Người dùng xây dựng một phác thảo, vẽ ra và lựa chọn màu cùng kết cấu dựa theo ảnh truy vấn. Hệ thống này hỗ trợ một vài độ đo tương tự cho ảnh như: trung bình màu sắc, lược đồ màu sắc và kết cấu. Công nghệ sử dụng trong hệ thống bao gồm đánh chỉ số và tìm kiếm. Hiện nay hệ thống này còn cung cấp vài cách tiếp cận truy vấn theo đơn đặc trưng, đa đặc trưng và đa giai đoạn. 2) Hệ thống Blobwold Hệ thống Blobwold do khoa Khoa học máy tính, Đại học California, Berkeley nghiên cứu và phát triển. Các đặc tính được sử dụng cho truy vấn là màu sắc, kết cấu, vị trí và hình dạng của vùng và nền. Màu sắc được mô tả bởi biểu đồ 218 bin màu kết hợp trong không gian Lab. Kết cấu được thể hiện bằng sự tương phản và không đẳng hướng trên vùng như không gian 2D (độ tương phản, độ tương phản x tính không đẳng hướng). Hình dạng được thể hiện bằng (xấp xỉ) vùng, độ lệch tâm và định hướng. 3) Hệ thống VisualSEEk Hệ thống VisualSEEk được xây dựng bởi Trung tâm nghiên cứu viễn thông thuộc trường đại học Columbia, New York. Đây là hệ thống truy vấn dựa vào các đặc trưng trực quan của ảnh, sử dụng không gian 166 màu HSV. Sự tương đồng giữa hai ảnh được xác định theo sự tương đồng của các vùng trong ảnh. Hệ thống cho phép người dùng nhập vào truy vấn, sử dụng các đặc trưng mức thấp của hình ảnh như: màu sắc, bố cục không gian và kết cấu. Các đặc trưng đó được mô tả theo màu sắc và biến đổi Wavelet dựa trên đặc trưng kết cấu. 4) Hệ thống Netra Hệ thống Netra sử dụng các đặc trưng của ảnh: màu sắc, hình dạng, kết cấu, vị trí không gian trong các vùng ảnh được phân đoạn để tìm kiếm và tra cứu các 6
vùng tương tự từ cơ sở dữ liệu. Các đặc trưng nghiên cứu chính của hệ thống Netra là phân tích kết cấu dựa trên lọc Gabor, xây dựng từ điển ảnh dựa trên mạng neural và phân đoạn vùng dựa vào luồng biên. Trích rút đặc trưng Trích rút đặc trưng ảnh mức thấp là cơ sở của các hệ thống CBIR. Trích rút đặc trưng bao gồm trích rút thông tin có nghĩa của ảnh, làm giảm dung lượng lưu trữ, do đó hệ thống sẽ nhanh và hiệu quả hơn trong CBIR. 1.1.1.3. Đặc trưng màu sắc Đặc trưng màu sắc được sử dụng rộng rãi nhất trong tra cứu ảnh. Một vài phương pháp tra cứu ảnh dựa trên cơ sở sự tương tự về màu sắc đã được mô tả trong các tài liệu nhưng các ý tưởng cơ bản là giống nhau. Mỗi hình ảnh được thêm vào bộ sưu tập được phân tích và tính toán biểu đồ màu để thấy tỷ lệ điểm ảnh của mỗi màu trong một ảnh. Biểu đồ màu của mỗi ảnh sau đó được lưu trữ trong cơ sở dữ liệu để khi tìm kiếm, người dùng có thể xác định tỷ lệ mong muốn của mỗi màu hoặc gửi một ảnh mẫu mà đã được tính toán biểu đồ màu. Dù bằng cách nào đi chăng nữa thì quá trình tra cứu sau đó là lấy ra những bức ảnh mà có biểu đồ màu tương ứng gần nhất với ảnh truy vấn. 1) Không gian màu - Không gian màu RGB (Red – Green – Blue) Không gian màu RGB được sử dụng nhiều nhất cho đồ họa máy tính, mô tả màu sắc bằng 3 thành phần chính là R (Red) – G (Green) và B (Blue). Không gian này được xem như một khối lập phương 3 chiều với màu Red là trục x, màu Green là trục y, và màu Blue là trục z. Mỗi màu trong không gian này được xác định bởi 3 thành phần R, G, B. Ứng với các tổ hợp khác nhau của 3 màu này sẽ cho ta một màu mới. Không gian màu RGB được sử dụng rộng rãi trong việc biểu diễn ảnh, gồm 3 thành phần màu là đỏ, xanh lục, xanh lam. Chúng được gọi là bộ cộng sơ cấp vì một màu khác trong không gian RGB được tạo ra bằng cách thêm chúng. 7
Hình 1.2. Không gian màu RGB. - Không gian màu CIE Không gian màu CIE L*a*b và CIE L*u*v là không gian độc lập và được xem như đồng bộ. Chúng chứa độ sáng hoặc thành phần nhẹ sáng (L) và hai thành phần màu a và b hoặc u và v. Có thể chuyển từ không gian màu RGB thành không gian CIEL*a*b và CIE L*u*v. - Không gian màu HSV Không gian màu HSV (HSL hoặc HSB) được sử dụng rộng rãi trong đồ họa máy tính và miêu tả màu một cách trực quan hơn. Ba thành phần màu có màu sắc, độ bão hòa (nhẹ sáng) và giá trị (độ sáng). Không gian RGB cũng có thể được chuyển thành không gian HSV bằng công thức đơn giản. Không gian màu thành phần sử dụng trục màu thành phần (R-G, 2B-R-G, R+G+B). Cách thể hiện này có lợi thế trong việc cô lập thông tin về độ sáng ở trục thứ ba. Hai trục màu đầu tiên bất biến với sự thay đổi cường độ sáng và tối, có thể giảm việc lấy mẫu khi con người nhạy cảm với độ sáng hơn. 8
Hình 1.3. Không gian màu HSV. 2) Lược đồ màu Lược đồ màu được xác định bằng một tập các bin, trong đó mỗi bin biểu thị xác suất của các pixel trong ảnh. Một lược đồ màu H của một ảnh đã cho được xác định bởi véc tơ: H={H[0], H[1], H[2], ..., H[i],... H[N]} Ở đây i biểu diễn một màu trong lược đồ màu và tương ứng với một khối con trong không gian màu RGB, H[i] là số các pixel có màu i trong ảnh và N là số các bin trong lược đồ màu. 1.1.1.4. Đặc trưng kết cấu Kết cấu là một mô tả vùng trợ giúp tốt trong quá trình tra cứu. Kết cấu không có khả năng tìm ra các ảnh tương tự, nhưng nó có thể được sử dụng để phân lớp các ảnh kết cấu từ các ảnh không kết cấu và sau đó được kết hợp với các thuộc tính đặc trưng khác như màu để làm cho tra cứu hiệu quả hơn. Kết cấu là một thuộc tính quan trọng khác của ảnh. Những kết cấu đa dạng đã được xem xét trong các mẫu nhận dạng và tầm nhìn máy tính. Phương pháp đại diện cấu trúc được phân thành hai loại: cấu trúc và thống kê. Phương pháp cấu trúc gồm có hoạt động 9
hình thái và đồ thị kề. Phương pháp thống kê gồm: quang phổ Fourier, ma trận đồng xuất hiện, phân tích bộ phận chính thay đổi bất biến, tính năng Tamura, phân hủy Wold, trường ngẫu nhiên Markov, mô hình fractal và bộ lọc đa phân giải. 1.1.1.5. Đặc trưng hình dạng Hình dạng được xem như là một đặc trưng quan trọng trong mô tả các đối tượng nổi bật trong ảnh và có thể giúp phân biệt giữa hai ảnh. Các đặc trưng hình dạng của ứng dụng nói chung gồm aspect ratio, circularity, Fourier descriptors, moment invariants, consecutive boundary segments. Đặc trưng hình dạng của đối tượng hoặc vùng đã được sử dụng nhiều trong hệ thống tra cứu ảnh dựa vào nội dung. So với đặc tính màu sắc và kết cấu thì hình dạng thường được mô tả sau khi ảnh được phân đoạn thành các vùng hoặc các đối tượng. Khi mà việc phân đoạn ảnh rất khó để đạt được độ chính xác và mạnh mẽ thì việc sử dụng đặc tính hình dạng trong tra cứu ảnh đã được giới hạn trong các ứng dụng đặc biệt nơi mà các đối tượng hoặc các vùng đã có sẵn. Mô tả hình dạng có thể dựa vào biên hoặc dựa vào vùng. Đặc tính hình dạng tốt với đối tượng là bất biến với xoay, dịch chuyển và mở rộng. 1.1.1.6. Vị trí không gian Bên cạnh kết cấu và màu, vị trí không gian cũng là hữu ích trong phân lớp vùng. Chẳng hạn, “bầu trời” và “biển” có thể có các đặc trưng kết cấu và màu tương tự, nhưng vị trí không gian của chúng là khác nhau với “bầu trời” thường xuất hiện ở trên đỉnh của ảnh, trong khi biển ở dưới. Vị trí không gian thường được xác định đơn giản như “trên, dưới, đỉnh” theo vị trí của vùng trong một ảnh. Trọng tâm vùng và hình chữ nhật bao tối thiểu của nó được sử dụng để cung cấp thông tin vị trí không gian. Tâm không gian của một vùng được sử dụng để biểu diễn vị trí không gian của nó. Quan hệ không gian tương đối là quan trọng hơn vị trí không gian tuyệt đối trong các đặc trưng ngữ nghĩa. Xâu 2-D và các biến thể của nó là cấu trúc phổ biến nhất được sử dụng để biểu diễn các quan hệ hướng giữa các đối tượng như “trái/phải”, “dưới/trên”. Tuy nhiên, chỉ một mình quan hệ hướng không đủ để biểu 10
diễn nội dung ngữ nghĩa của các ảnh khi bỏ qua quan hệ topo. Để hỗ trợ tốt hơn cho tra cứu ảnh dựa vào ngữ nghĩa, một thuật toán mô hình ngữ cảnh không gian được trình bày mà xem xét sáu quan hệ không gian giữa cắc cặp vùng: trái, phải, trên, dưới, tiếp xúc và trước. Một phương pháp thú vị được đề xuất bởi Smith và cộng sự. Hệ thống sử dụng một mẫu vùng cấu tạo (CRT) để xác định sự sắp xếp không gian của các vùng và mỗi lớp ngữ nghĩa được đặc trưng bởi các CRT thu được từ một tập các ảnh mẫu. Độ đo tương tự Hệ thống tra cứu ảnh dựa vào nội dung tính toán độ tương tự trực quan giữa ảnh truy vấn và ảnh trong cơ sở dữ liệu. Khi đó, kết quả tra cứu không chỉ là một ảnh mà gồm một danh sách ảnh được xếp hạng theo độ tương tự với ảnh truy vấn. Có nhiều phương pháp đo độ tương tự đã được phát triển trong tra cứu ảnh những năm gần đây. Các phương pháp đo khoảng cách/độ tương tự khác nhau ảnh hưởng đáng kể tới hiệu suất tra cứu. Trong các hệ thống tra cứu ảnh CBIR dựa vào vùng (RBIR), độ tương tự ảnh được đo ở hai mức. Đầu tiên là mức vùng. Tức là đo khoảng cách giữa hai vùng dựa trên các đặc trưng mức thấp của chúng. Thứ hai là mức ảnh. Tức là đo độ tương tự toàn bộ của hai ảnh mà có thể chứa số các vùng khác nhau. Hầu hết các nhà nghiên cứu sử dụng độ đo kiểu Minkowski để xác định khoảng vùng. Giả sử chúng ta có hai vùng biểu diễn bởi hai véc tơ p chiều (x1, x2,…xp), (y1, y2,…yp) tương ứng. Độ đo Minkowski được xác định như sau: 𝑝 1/𝑟 𝑑(𝑋, 𝑌) = (∑𝑖=1 |𝑥𝑖 − 𝑦𝑖 |) (1.1) Cụ thể, khi r bằng 2, nó là khoảng cách Euclidean nổi tiếng (khoảng cách L2). Khi r là 1, nó là khoảng cách Manhattan (khoảng cách L1). Một phiên bản biến thể được sử dụng thường xuyên là hàm khoảng cách Minkowski có trọng số mà đưa trọng số vào để nhận biết các đặc trưng quan trọng. 𝑝 1/𝑟 𝑑(𝑋, 𝑌) = (∑𝑖=1 𝑤𝑖 |𝑥𝑖 − 𝑦𝑖 |𝑟 ) (1.2) Ở đây wi, i=1,…,p là trọng số được áp dụng vào các đặc trưng khác nhau. 11
Các khoảng cách khác cũng được sử dụng trong tra cứu ảnh, như khoảng cách Canberra, khoảng cách angular, hệ số Czekanowski, tích trong, hệ số dice, hệ số cosine và hệ số Jaccard. Độ tương tự toàn thể của hai ảnh là khó hơn để đo. Về cơ bản có hai cách: Đối sánh mộ t- một: Nghĩa là mỗi vùng trong ảnh truy vấn chỉ được phép đối sánh một vùng trong ảnh mục tiêu và ngược lại. Như trong [8], mỗi vùng truy vấn của ảnh truy vấn được kết hợp với một vùng đối sánh tốt nhất trong ảnh mục tiêu. Sau đó độ tương tự toàn bộ được xác định bằng tổng có trọng số của độ tương tự giữa mỗi vùng truy vấn trong ảnh truy vấn và đối sánh tốt nhất của nó trong ảnh mục tiêu, trong khi trọng số liên quan đến cỡ vùng. Đối sánh nhiều - nhiều: Có nghĩa là mỗi vùng trong ảnh truy vấn được phép đối sánh nhiều hơn một vùng trong ảnh mục tiêu và ngược lại. Một phương pháp được sử dụng phổ biến là khoảng cách EMD (Earth Mover Distance). EMD là một độ đo linh hoạt và tổng quát. Nó đo chi phí cực tiểu được yêu cầu để biến đổi một phân bố sang một phân bố khác dựa vào bài toán giao vận truyền thống từ tối ưu tuyến tính, theo đó các thuật toán hiệu quả là sẵn có. EMD đối sánh tương tự nhận thức tốt và có thể được áp dụng đối với các biểu diễn của các phân bố có độ dài thay đổi, vì thế nó thích hợp cho đo độ tương tự ảnh trong hệ thống RBIR. Li và cộng sự đề xuất một lược đồ đối sánh vùng tích hợp (IRM) mà cho phép đối sánh một vùng của một ảnh với một số vùng của ảnh khác và do đó giảm sự ảnh hưởng của phân đoạn thiếu chính xác. Trong định nghĩa này, một đối sánh giữa hai vùng bất kỳ được gán với một điểm quan trọng. Điều này tạo ta một ma trận quan trọng giữa hai tập vùng (một tập là của ảnh truy vấn, tập còn lại là của ảnh mục tiêu). Độ tương tự toàn thể của hai ảnh được xác định dựa vào ma trận quan trọng trong một cách tương tự với EMD. Dù độ đo Minkowski được sử dụng rộng rãi trong các hệ thống hiện nay để đo khoảng cách vùng, các thực nghiệm mở rộng chỉ ra rằng nó không hiệu quả trong mô hình độ tương tự nhận thức. Cách đo độ tương tự nhận thức vẫn là một câu hỏi lớn chưa có đáp án. Có một số nghiên cứu đã thực hiện trong nỗ nực để giải quyết vấn đề này. Chẳng hạn, trong [4], một hàm khoảng cách động một phần 12