Tài liệu Nghiên cứu phương pháp tra cứu ảnh dựa trên phương pháp phân cụm đô thị

ĐẠI HỌC THÁI NGUYÊN TR¦êNG §¹I HäC C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG TRẦN THỊ HƯỜNG NGHIÊN CỨU PHƯƠNG PHÁP TRA CỨU ẢNH DỰA TRÊN PHƯƠNG PHÁP PHÂN CỤM ĐỒ THỊ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2020 ĐẠI HỌC THÁI NGUYÊN TR¦êNG §¹I HäC C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG TRẦN THỊ HƯỜNG NGHIÊN CỨU PHƯƠNG PHÁP TRA CỨU ẢNH DỰA TRÊN PHƯƠNG PHÁP PHÂN CỤM ĐỒ THỊ Chuyên ngành: Khoa học máy tính Mã số: 8 48 0101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Giáo viên hướng dẫn: PGS. TS. Ngô Quốc Tạo Thái Nguyên - 2020 i LỜI CẢM ƠN Luận văn này được hoàn thành tại Trường Đại học Công nghệ Thông tin và Truyền thông dưới sự hướng dẫn của PGS. TS. Ngô Quốc Tạo, sự hỗ trợ của các đề tài NVCC02.01/20-20 và VAST01.07/19-20. Tác giả xin bày tỏ lòng biết ơn tới các thầy cô giáo thuộc Trường Đại học Công nghệ Thông tin và Truyền thông, các thầy cô giáo thuộc Viện Công nghệ Thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện, giúp đỡ tác giả trong quá trình học tập và làm luận văn tại Trường. Đặc biệt tác giả xin bày tỏ lòng biết ơn tới PGS. TS. Ngô Quốc Tạo đã tận tình hướng dẫn và cung cấp nhiều tài liệu cần thiết, cám ơn TS. Ngô Trường Giang đã nhiệt tình hỗ trợ, để tác giả có thể hoàn thành luận văn đúng thời hạn. Xin chân thành cảm ơn anh chị em học viên cao học và bạn bè đồng nghiệp đã trao đổi, khích lệ tác giả trong quá trình học tập và làm luận văn tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên. Cuối cùng tác giả xin gửi lời cảm ơn đến gia đình, những người đã luôn bên cạnh, động viên và khuyến khích tôi trong quá trình thực hiện đề tài. Thái Nguyên, tháng 9 năm 2020 Học viên Trần Thị Hường ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn này do chính tôi thực hiện, dưới sự hướng dẫn khoa học của PGS. TS. Ngô Quốc Tạo, các kết quả lý thuyết được trình bày trong luận văn là sự tổng hợp từ các kết quả đã được công bố và có trích dẫn đầy đủ, kết quả của chương trình thực nghiệm trong luận văn này được tác giả thực hiện là hoàn toàn trung thực, nếu sai tôi hoàn toàn chịu trách nhiệm. Thái Nguyên, tháng 9 năm 2020 Học viên Trần Thị Hường iii MỤC LỤC LỜI CẢM ƠN ....................................................................................................................... i LỜI CAM ĐOAN ................................................................................................................ii DANH MỤC CÁC TỪ VIẾT TẮT................................................................................... v DANH MỤC CÁC HÌNH ................................................................................................ vii DANH MỤC BẢNG BIỂU.............................................................................................viii MỞ ĐẦU .............................................................................................................................. 1 1. Tính khoa học và cấp thiết của đề tài ....................................................................... 1 2. Đối tượng và phạm vi nghiên cứu của đề tài .......................................................... 2 3. Phương pháp luận nghiên cứu.............................................................................. 3 4. Nội dung và bố cục của luận văn......................................................................... 3 CHƯƠNG 1. TỔNG QUAN VỀ TRA CỨU ẢNH ..................................................... 4 1.1 Tra cứu ảnh dựa trên nội dung ........................................................................... 4 1.1.1 Khái niệm tra cứu ảnh ..................................................................................... 4 1.1.2 Kiến trúc của hệ thống CBIR .......................................................................... 5 1.2 Trích chọn đặc trưng trong tra cứu ảnh ............................................................ 9 1.2.1 Trích chọn đặc trưng màu ............................................................................... 9 1.2.2 Trích chọn đặc trưng kết cấu (texture) ........................................................12 1.2.3 Trích chọn đặc trưng hình dạng (shape) .....................................................17 1.3 Khoảng cách ngữ nghĩa trong tra cứu ảnh dựa trên nội dung...................... 20 1.3.1 Khoảng cách ngữ nghĩa.................................................................................20 1.3.2 Các phương pháp làm giảm khoảng cách ngữ nghĩa ................................21 1.4 Phản hồi liên quan trong tra cứu ảnh .............................................................. 22 1.4.1 Giới thiệu về phản hồi liên quan ..................................................................22 1.4.2 Các kỹ thuật phản hồi liên quan..................................................................23 1.5 Các lĩnh vực ứng dụng tra cứu ảnh ................................................................. 25 1.5.1 Một số ứng dụng cơ bản của tra cứu ảnh ...................................................25 1.5.2 Một số hệ thống tra cứu ảnh theo nội dung tiêu biểu ................................26 iv 1.6 Kết luận chương 1 ............................................................................................. 28 CHƯƠNG 2. TRA CỨU ẢNH DỰA TRÊN PHÂN CỤM ĐỒ THỊ ...................28 2.1 Phân cụm đồ thị ................................................................................................. 29 2.1.1 Giới thiệu đồ thị..............................................................................................29 2.1.2 Thuật toán phân cụm quang phổ ..................................................................33 2.1.3 Các thuật toán phân cụm phổ .......................................................................34 2.2 Phương pháp tra cứu ảnh sử dụng phân cụm phổ ......................................... 35 2.2.1 Phát biểu bài toán ..........................................................................................35 2.2.2 Phân tích và xây dựng mô hình ....................................................................37 2.2.3 Phân cụm phổ với phản hồi liên quan .........................................................37 2.3 Kết luận chương ................................................................................................ 42 CHƯƠNG 3. CHƯƠNG TRÌNH THỬ NGHIỆM..................................................44 3.1 Thiết kế mô hình thử nghiệm........................................................................... 44 3.1.1 Công cụ ............................................................................................................44 3.1.2 Chuẩn bị dữ liệu .............................................................................................46 3.2 Trích chọn đặc trưng ......................................................................................... 46 3.3 Độ đo tương tự................................................................................................... 47 3.4 Mô hình truy vấn .............................................................................................. 48 3.5 Một số kết quả đạt được và đánh giá .............................................................. 49 3.5.1 Tiêu chí đánh giá hiệu năng..........................................................................49 3.5.2 Đánh giá định tính .........................................................................................50 3.5.3 Đánh giá định lượng ......................................................................................52 3.6 Kết luận chương 3 ............................................................................................. 55 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 56 TÀI LIỆU THAM KHẢO ........................................................................................ 58 v DANH MỤC CÁC TỪ VIẾT TẮT Từ hoặc Từ tiếng Anh Từ tiếng Việt cụm từ CBIR Content-Based Image Retrieval Tra cứu ảnh dựa trên nội dung RF Relevance Feedback Phản hồi liên quan ST Semantic Template Định dạng ngữ nghĩa RGB Red-Green-Blue Ba màu cơ bản SVM Support Vector Machine May học vecto hỗ trợ SVT Semantic Visual Template Định dạng ngữ nghĩa thị giác KL Karhunen-Loeve Biến đổi Karhunen-Loeve CSDL Data base Cơ sở dữ liệu CCV Color Coherence Vector Véc tơ liên kết màu SIFT Scale Invariant Feature Transform Quy mô biến đổi tính năng SCRF Spectral Clustering in Relevant Thuật toán tra cứu ảnh hiệu quả sử Feedback dụng phân cụm phổ trong phản hồi liên quan QBIC Query By Image Content Truy vấn ảnh bởi nội dung PCA Principal Component Analysis Phương pháp phân tích thành phần chính vi vii DANH MỤC CÁC HÌNH Hình 1.1. Kiến trúc tổng quan về hệ thống tra cứu ảnh ..................................................5 Hình 1.2. Hình ảnh minh họa độ tương tự giữa 2 hình ảnh ...........................................6 Hình 1.3 Sơ đồ phản hồi liên quan. ...................................................................................8 Hình 1.4. Hình minh họa 2 ảnh có lược đồ giống nhau đến 70% nhưng khác nhau về ngữ nghĩa ................................................................................................... 10 Hình 1.5. Hình minh họa vector liên kết mầu ............................................................... 11 Hình 1.6. Cấu trúc vân của lá cây................................................................................... 14 Hình 1.7. Decompostion để tạo ra các frequency bands bởi biến đổi Wavelet ........ 16 Hình 1.8. Đường bao của ảnh ......................................................................................... 18 Hình 1.9. Đường biên của ảnh ........................................................................................ 19 Hình 1.10. Lược đồ hệ số góc của ảnh........................................................................... 19 Hình 1.11. Ảnh minh họa sự liên kết giữa các biên cạnh ............................................ 20 Hình 1.12. Lược đồ vector liên kết hệ số góc của ảnh................................................. 20 Hình 2.1. Ví dụ về mô hình đồ thị .................................................................................. 29 Hình 2.2. Phân lo ại đồ thị ................................................................................................ 30 Hình 2.3. Cấu trúc của phương pháp SCRF .................................................................. 37 Hình 2.4. Thuật toán CRISE [5] ..................................................................................... 40 Hình 2.5. Thuật toán SCRF [5] ....................................................................................... 42 Hình 3.1. Giao diện chương trình thực nghiệm ............................................................ 44 Hình 3.2. Chọn các điều kiện tra cứu ảnh ..................................................................... 45 Hình 3.3. Các ảnh minh họa cho 10 thể loại trong tập ảnh Wang.............................. 46 Hình 3.4. Mô hình truy vấn ............................................................................................. 49 Hình 3.5. Kết quả tra cứu khi chưa có phản hồi liên quan .......................................... 50 Hình 3.6. Kết quả tra cứu khi phản hồi liên quan với số cụm là 4 ............................. 51 Hình 3.7. Kết quả tra cứu khi phản hồi liên quan 4 lần với số cụm là 6 ................... 51 viii DANH MỤC BẢNG BIỂU Bảng 3.1. Các loại đặc trưng ........................................................................................... 47 Bảng 3.2. Kết quả đánh giá độ đo tương tự................................................................... 52 Bảng 3.3. Kết quả đánh giá khi sử dụng các đặc trưng khác nhau............................. 53 Bảng 3.4. Kết quả đánh giá độ chính xác với số lượng ảnh trả về khác nhau .......... 54 Bảng 3.5. Hiệu quả của thuật toán SCRF với các lần phản hồi liên quan................. 55 1 MỞ ĐẦU 1. Tính khoa học và cấp thiết của đề tài Trong những năm gần đây, cùng với sự phát triển ngày càng mạnh mẽ của khoa học kỹ thuật, xử lý ảnh là lĩnh vực nghiên cứu đang phát triển không ngừng bởi tính trực quan sinh động cũng như khả năng áp dụng vào thực tế lớn. Hiện xử lý ảnh đang giành được nhiều sự quan tâm của các nhà nghiên cứu trong và ngoài nước. Trong xử lý ảnh, tra cứu ảnh có thể nói là lĩnh vực đòi hỏi sự nghiên cứu tổng hợp: nghiên cứu xử lý ảnh để rút trích các đặc trưng, áp dụng các tính toán toán học cao cấp để xác định mức độ tương đồng giữa hai ảnh. Hơn nữa, cùng với sự phát triển của phần mềm và phần cứng, khối lượng ảnh phát triển không ngừng và ngày càng lớn. Một số lượng lớn các ảnh đang được sử dụng ở trong thư viện ảnh số và trên web. Vì vậy, nhu cầu tìm kiếm ảnh là một nhu cầu tất yếu. Hiện nay, tra cứu ảnh ứng dụng trong khá nhiều lĩnh vực như: quản lý biểu trưng (logo), nhận dạng đối tượng, nhận dạng mặt, ứng dụng trong y khoa, quân sự…[3] , [4] . Hệ thống tra cứu ảnh dựa trên phương pháp phân cụm là phương pháp đã được nhiều người nghiên cứu với nhiều cách tiếp cận khác nhau, do đó rất nhiều hệ thống tra cứu ảnh dựa trên phương pháp này [5] , [6] , [8] . Phân cụm là một trong những vấn đề cơ bản phổ biến trong các lĩnh vực nhận dạng mẫu, học máy và khai thác dữ liệu. Hiện tại, trên thực tế có rất nhiều thuật toán phân cụm được công bố. Tuy nhiên, do không tồn tại một thuật toán phân cụm duy nhất cho tất cả các loại bộ dữ liệu, những thuật toán phân cụm mới vẫn liên tục được đề xuất. Kết quả là, người dùng phải chọn thuật toán thích hợp nhất từ nhiều ứng viên để đạt được kết quả chính xác. Trong thực tế, việc lựa chọn thuật toán phân cụm dữ liệu phù hợp là rất khó khăn do người sử dụng thường không có một kiến thức tiên nghiệm về sự đa dạng và phức tạp của dữ liệu. Để phần nào giảm bớt nhược điểm trên, các thuật toán phân cụm dựa trên đồ thị được đề xuất do ưu điểm ở khả năng xử lý các bộ dữ liệu đa dạng và có cấu trúc. Bản chất của các thuật toán này là biểu diễn dữ liệu dựa trên đồ thị và phân cụm các thành phần theo các thuật toán thiết kế riêng [7] . 2 Đồ thị là những cấu trúc toán học được sử dụng để đại diện cho mối quan hệ giữa cặp đối tượng từ một tập hợp xác định. Đồ thị chứa đỉnh (đại diện cho các đối tượng) và các cạnh nối các đỉnh (đại diện cho mối quan hệ giữa các đối tượng cặp). Đây là phương pháp biểu diễn cấu trúc dữ liệu quan trọng được sử dụng trong rất nhiều lĩnh vực như khai thác dữ liệu, xử lý ngôn ngữ tự nhiên, tìm kiếm thông tin và khai thác thông tin. Trong phân cụm, sự tương đồng giữa các đối tượng được phân cụm có thể được diễn tả như một đồ thị có trọng số. Trong đó, các đối tượng là các đỉnh và sự tương đồng là trọng số của các cạnh. Trong bài toán tra cứu ảnh, các ảnh trong cơ sở dữ liệu được biểu diễn như là các đỉnh của đồ thị có trọng số. Phản hồi liên quan của người dùng được sử dụng để tạo ra các mẫu được gán nhãn. Những mẫu này sẽ được sử dụng để làm cơ sở tính toán khả năng lan truyền cho mỗi ảnh. Trong tiếp cận này, không chỉ sử dụng mối quan hệ từng cặp giữa ảnh truy vấn với các ảnh trong cơ sở dữ liệu mà nó còn khai thác cả mối quan hệ giữa tất cả các ảnh với nhau. Các ảnh liên quan với truy vấn được xem và gom cụm vào cùng nhóm, các ảnh còn lại là nhóm khác. Do vậy, hiệu quả tra cứu của chúng được cải thiện. Với những lý do trên, tác giả đã chọn đề tài “Nghiên cứu phương pháp tra cứu ảnh dựa trên phương pháp phân cụm đồ thị” làm đề tài nghiên cứu luận văn tốt nghiệp thạc sĩ chuyên ngành Khoa học máy tính. 2. Đối tượng và phạm vi nghiên cứu của đề tài  Đối tượng Nghiên cứu phương pháp tra cứu ảnh dựa trên phương pháp phân cụm đồ thị.  Phạm vi - Đề tài dừng ở mức áp dụng kỹ thuật phân cụm đồ thị vào bài toán tra c ứu ảnh. - Thử nghiệm trên cơ sở dữ liệu ảnh wang [14] ; đây là các tập dữ liệu được sử dụng rộng rãi trong các nghiên cứu lĩnh vực tra cứu ảnh. - Phân tích đánh giá kết quả việc sử dụng các bộ tham số khác nhau trong thuật toán. 3 3. Phương pháp luận nghiên cứu - Phương pháp nghiên cứu lý thuyết: Nghiên cứu tài liệu đã xuất bản, các bài báo trên tạp chí khoa học và các tài liệu trên mạng Internet có liên quan đến vấn đề đang nghiên cứu của các tác giả trong và ngoài nước. Từ đó chọn lọc theo ý tưởng của mình. - Phương pháp chuyên gia: Tích cực làm việc với giáo viên hướng dẫn và các chuyên gia trong lĩnh vực machine learning để luận văn đi đúng hướng và theo đúng kế hoạch đã định. - Phương pháp thực nghiệm: xây dựng chương trình cụ thể trên CSDL ảnh wang, core để thử nghiệm, phân tích, đánh giá kết quả việc sử dụng các bộ tham số khác nhau trong thuật toán. 4. Nội dung và bố cục của luận văn Ngoài phần mở đầu, kết luận và hướng phát triển, luận văn được bố cục thành ba chương chính như sau: - Chương 1. Tổng quan về tra cứu ảnh: Trong chương này, giới thiệu các vấn đề cơ bản của tra cứu ảnh bao gồm: tổng quan bài toán tra cứu ảnh, tra cứu ảnh dựa trên nội dung, trích chọn đặc trưng trong tra cứu ảnh, các phản hồi liên quan cũng như các lĩnh vực ứng dụng tra cứu ảnh. - Chương 2. Tra cứu ảnh dựa trên phân cụm đồ thị: Nội dung chính của chương tập trung làm rõ các kiến thức cơ bản về phân cụm đồ thị, đặc biệt là phương pháp phân cụm đồ thị quang phổ. Bên cạnh đó, nội dung chương 2 cũng nghiên cứu tổng hợp kiến thức về đề xuất áp dụng phương pháp tra cứu ảnh sử dụng phân cụm phổ trong phản hồi liên quan. - Chương 3: Xây dựng chương trình thử nghiệm: Ở chương này, luận văn tập trung vào việc mô tả bài toán, phân tích, xây dựng và thiết kế mô hình thử nghiệm đánh giá hiệu quả tra cứu ảnh trên CSDL ảnh Wang khi sử dụng các phương pháp trích chọn đặc trưng khác nhau, các độ đo khác nhau, số lượng ảnh trả về khác nhau cũng như khi áp dụng phân cụm đồ thị trong phản hồi liên quan. 4 CHƯƠNG 1 TỔNG QUAN VỀ TRA CỨU ẢNH Nội dung chương 1 tập trung tìm hiểu khái quát về tra cứu ảnh dựa trên nội dung bao gồm: Các phương pháp tra cứu ảnh truyền thống; một số phương pháp trích chọn đặc trưng ảnh; khoảng cách ngữ nghĩa và phương pháp làm giảm khoảng cách ngữ nghĩa sử dụng phản hồi liên quan. Đồng thời chương này cũng giới thiệu một số hệ thống CBIR lớn theo các lĩnh vực đã ứng dụng rộng rãi. 1.1 Tra cứu ảnh dựa trên nội dung 1.1.1 Khái niệm tra cứu ảnh Thuật ngữ “Tra cứu thông tin” được đưa ra vào năm 1952 và đã giành được sự quan tâm đặc biệt của hội các nhà nghiên cứu từ năm 1961. Chúng ta có thể dễ dàng mô tả một hệ thống đó như là một hệ thống lưu trữ và tra cứu thông tin. Vì vậy nó gồm một tập hợp các thành phần tương tác lẫn nhau, mỗi thành phần được thiết kế cho một chức năng riêng, có mục đích riêng và tất cả các thành phần này có quan hệ với nhau để đạt được mục đích là tìm kiếm thông tin trong một phạm vi nào đó [6] Thế giới đang chứng kiến một sự tiến hóa về lượng, sự sẵn có, độ phức tạp, sự đa dạng và sự quan trọng của các ảnh trong tất cả các lĩnh vực. Do đó, nhu cầu về các dịch vụ ảnh trở nên quan trọng hơn bao giờ hết. Các ảnh đóng một vai trò quan trọng trong một phạm vi rộng các ứng dụng và các lĩnh vực như giáo dục, chăm sóc y tế, dự báo thời tiết, nghiên cứu về tội phạm, quảng cáo, thiết kế nghệ thuật, web, phương tiện xã hội và giải trí [2] , [6] [9] . Tuy nhiên, phương tiện trực quan yêu cầu một lượng xử lý và lưu trữ đáng kể, cần có các phương pháp hiệu quả cao để đánh chỉ số, lưu trữ, phân tích và tra cứu thông tin trực quan từ các cơ sở dữ liệu ảnh. Do đó, tra cứu các ảnh nhanh, chính xác và hiệu quả cho tất cả các loại tập ảnh trở thành một trong những nhiệm vụ thách thức nhất. Cách tiếp cận ban đầu cho tra cứu ảnh là dựa vào văn bản, trong đó các ảnh được đánh chỉ số bằng các từ khóa, chủ đề hoặc mã phân loại. Các từ khóa, chủ đề hoặc mã phân loại này được sử dụng trong quá trình tra cứu. Tuy nhiên, với cơ sở dữ liệu ảnh lớn và tăng lên nhanh chóng, các khó khăn phải đối mặt của cách tiếp cận tra 5 cứu dựa vào văn bản ngày càng trở nên nghiêm trọng hơn. Bên cạnh đó, quá trình này tốn nhiều nhân lực và thời gian, từ khóa lại mang tính chủ quan và không duy nhất, những người khác nhau có các nhận thức khác nhau về cùng một ảnh. Để khắc phục các vấn đề này, các nội dung của ảnh (gồm mầu, kết cấu và hình dạng) được trích rút tự động từ bản thân các ảnh đã được sử dụng cho tra cứu ảnh. Phương pháp này được gọi là tra cứu ảnh dựa vào nội dung (CBIR - contentbased image retrieval). CBIR cho phép loại đi các khó khăn của tra cứu dựa vào văn bản trong các cơ sở dữ liệu ảnh lớn và hệ thống CBIR cung cấp các kết quả chính xác hơn. 1.1.2 Kiến trúc của hệ thống CBIR Phản hồi thích hợp Người sử dụng Tạo truy vấn Cơ sở Dữ liệu ảnh Mô tả Nội dung Trực quan Mô tả Nội dung Các Vector Đặc trưng Đánh giá độ tương tự Cơ sở Dữ liệu Đặc trưng Tra cứu và Đánh chỉ số Đầu ra Kết quảtra cứu Hình 1.1. Kiến trúc tổng quan về hệ thống tra cứu ảnh 1.1.2.1 Trích chọn đặc trưng Các đặc trưng của hình ảnh bao gồm các đặc trưng nguyên thủy và các đặc trưng ngữ nghĩa hoặc đặc trưng logic. Các đặc trưng cơ bản đó là: màu sắc (color), kết cấu (texture), hình dạng (shape), vị trí không gian (spatial location),… được định lượng trong tự nhiên, chúng có thể được trích xuất tự động hoặc bán tự động. Đặc trưng logic cung cấp mô tả trừu tượng của dữ liệu hình ảnh ở các cấp độ khác nhau. Thông thường, một hoặc nhiều đặc trưng có thể được sử dụng trong từng ứng dụng cụ thể trên thực tế. 6 1.1.2.2 Đo độ tương tự giữa các ảnh Hệ thống CBIR dựa trên những đặc điểm nguyên thủy để so sánh độ tương tự giữa ảnh truy vấn và tất cả các ảnh trong CSDL. Mặc dù vậy sự tương tự hoặc sự khác nhau giữa các ảnh không chỉ xác định theo một cách. Số lượng của ảnh tương tự sẽ thay đổi khi yêu cầu truy vấn thay đổi. Chẳng hạn trong trường hợp hai hình ảnh, một là biển xanh mặt trời mọc và trường hợp khác là núi xanh với mặt trời mọc. Hình 1.2. Hình ảnh minh họa độ tương tự giữa 2 hình ảnh Khi mặt trời được xem xét thì độ tương tự giữa hai ảnh này là cao nhưng nếu đối tượng quan tâm là biển xanh thì độ tương tự giữa hai ảnh này là thấp. Như vậy rất khó khăn để tìm ra phương pháp đo độ tương tự giữa hai hình ảnh trên một cách chính xác đối với tất cả các kiểu yêu cầu của truy vấn. Hay nói cách khác mỗi một phương pháp tra cứu sẽ có giới hạn của chính nó. Ví dụ rất khó cho công nghệ tra cứu dựa trên màu sắc để tìm ra điểm khác nhau giữa một ảnh là bầu trời màu xanh với một ảnh là mặt biển xanh. Vì vậy khi đánh giá một phương pháp tra cứu ảnh dựa trên nội dung cần phải biết rằng hiệu quả của công nghệ đó phụ thuộc vào kiểu yêu cầu tra cứu mà người dùng sử dụng. 1.1.2.3 Đánh chỉ số Đánh chỉ số là một công việc quan trọng trong tra cứu ảnh dựa trên nội dung, nó giúp tìm kiếm nhanh ảnh dựa trên đặc trưng trực quan, bởi vì các vector đặc trưng của ảnh có xu hướng, có số chiều cao và vì vậy nó không thích hợp cho các cấu trúc đánh chỉ số truyền thống. Do đó trước khi lên kế hoạch đánh chỉ số ta phải tìm cách làm giảm số chiều của các vector đặc trưng. 7 Có nhiều phương pháp làm giảm số chiều của vector đặc trưng, một trong những công nghệ được sử dụng phổ biến là phân tích thành phần chính PCA. Nó là một công nghệ tối ưu trong việc ánh xạ tuyến tính dữ liệu đầu vào một không gian toạ độ, các trục được thẳng hàng để phản ánh các biến thể lớn nhất trong dữ liệu. Hệ thống QBIC sử dụng PCA để làm giảm số chiều của vector đặc trưng hình dạng từ nhiều chiều thành hai hoặc ba chiều. Ngoài phương pháp PCA ra, nhiều nhà nghiên cứu còn sử dụng biến đổi KL để làm giảm số chiều trong không gian đặc trưng. Ngoài hai phương pháp biến đổi PCA và KL, thì mạng nơ ron cũng là công cụ hữu ích cho việc giảm số chiều đặc trưng. Khi đã giảm được số chiều thì dữ liệu đa chiều được đánh chỉ số. Có nhiều phương pháp đánh chỉ số bao gồm : K-D-B tree, R-tree, linear quadtrees,... các phương pháp này đều cho hiệu quả hợp lý với không gian có số chiều nhỏ. 1.1.2.4 Giao diện truy vấn Để biểu diễn ảnh tra cứu từ CSDL cho người dùng thì có rất nhiều cách. Và những cách thông thường nhất được sử dụng là: Duyệt qua mục; truy vấn bởi khái niệm; truy vấn bởi bản phác thảo và truy vấn bởi ví dụ,... - Duyệt qua mục là phương pháp duyệt qua toàn bộ CSDL theo danh mục các ảnh. Mục đích của phương pháp này là ảnh trong CSDL được phân loại thành nhiều mục khác nhau theo ngữ nghĩa hoặc nội dung trực quan. - Truy vấn bởi khái niệm là tra cứu ảnh theo mô tả khái niệm liên quan với từng ảnh trong CSDL. - Truy vấn bởi bản phác thảo và truy vấn bởi ví dụ là vẽ ra một bản phác thảo hoặc cung cấp một ảnh ví dụ từ những ảnh với độ tương tự đặc trưng trực quan sẽ được trích chọn từ CSDL. Trong số các phương pháp trên thì phương pháp thì truy vấn bởi bản phác thảo hoặc bởi ví dụ là phương pháp quan trọng và khó khăn nhất. Phần lớn các nghiên cứu tra cứu ảnh dựa trên nội dung tập trung đi sâu vào phương pháp này. 8 1.1.2.5 Phản hồi liên quan Phản hồi liên quan (RF - Relevance Feedback) 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 tương tác. Phản hồi liên quan được sử dụng rộng rãi trong các hệ thống tra cứu thông tin. Mục đích của nó là 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 tra cứu ảnh dựa vào nội dung [5] . Ảnh truy vấn Truy vấn Kết quả tra cứu ảnh khởi tạo Phản hồi Các mẫu được gán nhãn (các ảnh liên quan không) Các tham số điều chỉnh Các kết quả tra cứu Phản hồi Hình 1.3 Sơ đồ phản hồi liên quan. Hình 1.3 chỉ ra cơ chế hoạt động của phản hồi liên quan trong tra cứu ảnh dựa vào nội dung. Khi có kết quả tra cứu khởi tạo, người dùng chọn các ảnh liên quan trong danh sách kết quả này để làm các mẫu có nhãn (dương hay âm). Dựa trên tập mẫu huấn luyện này, một thuật toán máy học được thực hiện để điều chỉnh các tham số. Dựa trên các tham số vừa được học, tra cứu ảnh sẽ tiếp tục được thực hiện. Quá trình được lặp lại cho đến khi người dùng thỏa mãn. 9 1.2 Trích chọn đặc trưng trong tra cứu ảnh Các đặc trưng cơ trưng bản của hình ảnh bao gồm: màu sắc (color), kết cấu (texture), hình dạng (shape), vị trí không gian (spatial location),… được định lượng trong tự nhiên, chúng có thể được trích xuất tự động hoặc bán tự động. Dưới đây sẽ giới thiệu một số phương pháp trích chọn đặc trưng hình ảnh. 1.2.1 Trích chọn đặc trưng màu Hình ảnh bao gồm một mảng các điểm ảnh (pixel), và mỗi pixel thể hiện một màu sắc [2] . Có nhiều không gian màu được sử dụng để tính toán các giá trị màu của pixel như: không gian chuẩn RGB, không gian trực giác HSV... Các đặc trưng được lưu giữ dưới dạng các vector biểu diễn cho các thông tin mô tả nội dung ảnh. Lược đồ màu (Histogram) là đại lượng đặc trưng cho phân bố màu cục bộ của ảnh. Được định lượng: H ( I D , Ci )  m( I D , Ci ) n( I D ) (1.1) Trong đó Ci là màu của điểm ảnh, n( I D ) là tổng số điểm ảnh trong ảnh, m( I D , Ci ) biểu diễn số điểm ảnh có giá trị màu Ci . H là lược đồ màu của ảnh. Độ đo tính tương tự về màu sắc giữa lược đồ màu của ảnh truy vấn H ( I Q ) và lược đồ màu của ảnh trong CSDL ảnh H ( I D ) được định nghĩa: M DH ( I Q , I D )   min( H ( I j 1 Q , j ), H ( I D , j )) (1.2) M  H (I j 1 D , j) Công thức (1.2) cho ta thấy, tính tương tự về màu sắc được tính bằng phần giao của 2 lược đồ màu ảnh truy vấn H(IQ) và ảnh trong cơ sở dữ liệu ảnh H(ID). Kết quả sẽ là một lược đồ màu thể hiện độ giống nhau giữa 2 ảnh trên. Tuy nhiên vì lược đồ màu chỉ thể hiện tính phân bố màu toàn cục của ảnh mà không xét đến tính phân bố cục bộ của điểm ảnh nên có thể có 2 ảnh trông rất khác nhau nhưng lại có cùng lược đồ màu. 10 Hình 1.4. Hình minh họa 2 ảnh có lược đồ giống nhau đến 70% nhưng khác nhau về ngữ nghĩa Để khắc phục được tình trạng này, chúng ta dùng phân hoạch lưới ô vuông trên ảnh. Lược đồ màu của ảnh là không duy nhất. 1.2.1.1 Vector liên kết màu Vector liên kết màu (CCV) là lược đồ tinh chế lược đồ màu, chia mỗi ô màu (bin) thành 2 nhóm điểm ảnh: Nhóm liên kết màu (coherence pixels) và nhóm không liên kết màu (non-coherence pixels). Một pixel trong 1 ô màu (bin) được gọi là điểm liên kết màu (coherent) nếu nó thuộc vùng gồm các màu tương tự với kích thước lớn (thường bằng khoảng 1% kích thước ảnh). Với mỗi ô màu (bin) giả sử số điểm liên kết màu là α và số điểm không liên kết màu là β thì vector liên kết màu được xác định: VC  1 , 1  , 1 , 1  ,...,  n ,  n   , n là số ô màu (bin) Trong tìm kiếm ảnh với việc sử dụng đặc trưng vectơ liên kết màu sẽ giúp ta tránh được tình trạng hai ảnh có cùng lược đồ màu nhưng khác nhau hoàn toàn về ngữ nghĩa. Ngoài ra vector liên kết màu còn giúp giải quyết khuyết điểm về tính không duy nhất của lược đồ màu đối với ảnh. Hai ảnh có thể có chung lược đồ màu nhưng khác nhau hoàn toàn, đây là khuyết điểm của lược đồ màu. Nhưng với truy vấn theo đặc trưng vector liên kết màu thì nó sẽ giải quyết được khuyết điểm không duy nhất này