Luận văn 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ị

á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 - content- based 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 Mô tả Các Vector Tạo truy vấn Nội dung Đặc trưng Trực quan Đánh giá độ tương tự Cơ sở Dữ liệu Mô tả Cơ sở Dữ liệu ảnh Đặc trưng Nội dung Tra cứu và Đánh chỉ số Kết quảtra cứu Đầu ra 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: m(,) IDi C HIC(,)Di (1.1) nI()D Trong đó Ci là màu của điểm ảnh, nI()D là tổng số điểm ảnh trong ảnh, m(,) IDi C biểu diễn số điểm ảnh có giá trị màu . 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 HI()Q và lược đồ màu của ảnh trong CSDL ảnh HI()D được định nghĩa: M  min(H ( IQD , j ), H ( I , j )) j1 DIIHQD(,)  M (1.2)  H(,) ID j j1 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 11 Hình 1.5. Hình minh họa vector liên kết mầu 1.2.1.2 Tương quan màu Như đã giới thiệu ở trên, lược đồ màu chỉ ghi nhận được sự phân bố màu trong ảnh mà không chứa các thông tin mối quan hệ về khoảng cách. Để khắc phục hạn chế đó, đặc trưng tương quan màu biểu diễn sự thay đổi mối quan hệ về không gian giữa các cặp màu theo khoảng cách. Cũng giống như đặc trưng vectơ liên kết màu, đặc trưng tương quan màu thể hiện mối quan hệ chặt chẽ về sự phân bố màu trong ảnh. Chính vì vậy nếu truy tìm ảnh sử dụng đặc trưng này cũng tránh được tình trạng mà đặc trưng lược đồ màu vấp phải. So sánh với lược đồ màu và vector gắn kết màu, tương quan màu cho...ng phân cụm phổ trong phản hồi liên quan (spectral clustering in relevant feedback - SCRF). Các kiến thức này báo gồm lý 29 thuyết chung về đồ thị, phương pháp phân cụm đồ thị quang phổ và các bước để ứng dụng phân cụm đồ thị quang phổ trong thuật toán SCRF. 2.1 Phân cụm đồ thị 2.1.1 Giới thiệu đồ thị 2.1.1.1 Một số khái niệm Đồ thị là một mô hình toán học gồm các đỉnh và các cạnh nối các đỉnh. Đồ thị được mô tả hình thức như sau: G = (V, E, W), với V là tập đỉnh, E  VV là tập cạnh và {W = (wij) i,j = 1, N} là tập các trọng số trên các cạnh của đồ thị. Giữa hai đỉnh vi và vj ∈ V có cạnh nối với nhau với trọng số wij > 0 nếu (vi, vj) ∈ E, ngược lại wij = 0, nghĩa là vi và vj ∈ V không có cạnh nối với nhau [7] . Hình 2.1. Ví dụ về mô hình đồ thị Hình 2.1 minh họa một số hình ảnh trong thực tế của đồ thị. Để phân loại đồ thị, ta có thể dựa vào đặc tính và số lượng của tập các cạnh E như sau: - G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v. - G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v (Hiển nhiên đơn đồ thị cũng là đa đồ thị). - G được gọi là đồ thị vô hướng (undirected graph) nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự. (u, v) ≡ (v, u). Trong trường hợp này W là ma trận đối xứng, nghĩa là wij = wji 30 - G được gọi là đồ thị có hướng (directed graph) nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u). Trong trường hợp này W là ma trận không đối xứng, nghĩa là wij ≠ wji. Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u). - Khi wij = 1 với mọi (vi, vj) ∈ E thì đồ thị G được gọi là đồ thị không có trọng số. Hình 2.2. Phân loại đồ thị Đồ thị thường được sử dụng để mô hình cho tập dữ liệu, trong đó các đỉnh biểu diễn cho các phần tử dữ liệu và trọng số trên các cạnh biểu diễn cho độ tương tự (khoảng cách) giữa các cặp dữ liệu. Bên cạnh việc xác định ngữ nghĩa của việc sử dụng các đỉnh, cạnh của đồ thị thì một vấn đề quan trọng nữa là việc tính độ tương tự (similarity) hoặc khoảng cách (distance) giữa các đỉnh để xây dựng đồ thị. Cách tính độ tương tự cũng có thể thay đổi và phụ thuộc vào các ứng dụng. Nhưng về nguyên tắc phải đảm bảo rằng, nếu hai 31 đỉnh có độ tương tự cao thì trong thực tế ứng dụng chúng phải gần nhau theo một nghĩa nào đó. Một số phương pháp mô hình đồ thị dữ liệu phổ biến: - Đồ thị 휺 láng giềng (휺 -neighborhood graph): đồ thị được xây dựng bằng cách kết nối những đỉnh mà khoảng cách từng cặp nhỏ hơn ε. Tương tự, đồ thị δ láng giềng (δ- neighborhood graph) là đồ thị được xây dựng bằng cách kết nối những đỉnh mà khoảng cách từng cặp lớn hơn δ. - Đồ thị 풌 láng giềng gần nhất (k-nearest neighbor graph): đồ thị được xây dựng bằng cách kết nối đỉnh vi với vj nếu vi là một trong số 푘 - láng giềng gần nhất của vj hoặc vj là một trong số 푘 - láng giềng gần nhất của vi. Nói một cách khác, để kết nối vi với vj nếu cả hai vi và vj là 푘 - láng giềng gần nhất của nhau. - Đồ thị liên thông mạnh: đồ thị được xây dựng bằng cách kết nối tất cả các đỉnh với các đỉnh khác với độ tương tự dương. 2.1.1.2 Độ đo trong phân cụm đồ thị dữ liệu Một câu hỏi đặt ra là một kỹ thuật (thuật toán) phân cụm đồ thị như thế nào được gọi là tốt, tối ưu? Để có câu trả lời chúng ta phải xác định được các tiêu chí, hay độ đo (measure) để đánh giá được một thuật toán phân cụm là tối ưu Phân cụm đồ thị là tìm cách xác định các đồ thị con liên thông mạnh (cụm) trong các đồ thị cho trước và mục tiêu cần đạt được là tối ưu hóa hàm đo chất lượng của kỹ thuật phân cụm đồ thị. Một số độ đo phổ biến được sử dụng để phân cụm như sau: 1. Mật độ của cụm (intra-cluster density): Mật độ của cụm Ci được xác định bằng tỷ số giữa tổng các trọng số của cạnh bên trong của Ci trên tổng các trọng số của đồ thị. w u C, v C uv Intra_ density C   ii (2.9) i w u, v E uv Mục tiêu là cực đại hóa tổng của các mật độ của tất cả các cụm: 32 K Maximize Intra_ density Ci  (3.0) i1 2. Mật độ giữa các cụm (inter-cluster density): Mật độ của cụm Ci và Cj được xác định bằng tỷ số giữa tổng các trọng số của cạnh nối giữa Ci và Cj trên tổng các trọng số của đồ thị. w u C, v C uv ij Inter_, density Cij C   (3.1) w u, v E uv Mục tiêu là cực tiểu hóa tổng của các mật độ giữa các cụm: KK1 Minimize Inter_, density Cij C  (3.2) i11 j  i  Nếu G được phân hoạch thành 2 cụm thì phân cụm C = (S, V\S) được gọi là lát cắt (cut) của đồ thị G với S  V. Giá trị của lát cắt bằng tổng các trọng số của các cạnh nối giữa hai cụm. cut S,V\ S  w    uv (3.3) u S,\ v V S 3. Lát cắt chuẩn (Normalized cut- Shi and Malik 2000): được xác định như sau: cut Cii,V\ C  ncut Cii,V\ C   (3.4) vol Ci  Trong đó, vol(Ci )  wuv .Mục tiêu là cực tiểu hóa tổng ncut() của tất cả cụm: uCi ,vV K Minimize ncut Cii,V\ C  (3.5) i1 4. Độ dẫn (Conductance- Kannan, 2000): được xác định như sau: w u S,\ v C S uv i ConductanceCi   min (3.6) SCS,\ i minvol S , vol Ci \ S Trong đó, . Mục tiêu là cực đại hóa độ dẫn, tức là vol(S)  wuv uS,vV Maximizemin1i K conductance C i  (3.7) 5. Độ đo đơn thể (modularity- Girvan và Newman, 2002) được xác định: 33 K 2 modularity Ci  e ii – aii , a eij (3.8) j1 Trong đó, eii là phân số của các cạnh trong cụm Ci, eij (i  j) là phân số của các cạnh nối đỉnh của cụm i sang cụm j. Độ đo đơn thể được thể hiện như sau: mật độ của cạnh hiện thời trong cụm 퐶푖 trừ đi giá trị kỳ vọng bên trong cụm Ci khi tất cả các đỉnh của đồ thị được kết nối theo các bậc đã được xác định. Độ đo đơn thể của phân cụm là tổng của độ đo đơn thể của các cụm. K Q  modularity(Ci ) (3.9) j1 Mục tiêu là cực đại hóa độ đo đơn thể của phân cụm Q. Hiện nay độ đo đơn thể của phân cụm được sử dụng khá hiệu quả trong nhiều ứng dụng khác nhau. 2.1.2 Thuật toán phân cụm quang phổ Thuật toán phân cụm quang phổ (Spectral Clustering Algorithm) là thuật toán phân cụm đồ thị dữ liệu quan trọng bởi lẽ, nó dựa vào cơ sở đại số tuyến tính, dễ cài đặt và rất hiệu quả. Giống như đối với các thuật toán phân cụm dữ liệu truyền thống, như thuật toán K-trung bình, công cụ được sử dụng chính trong thuật toán phân cụm quang phổ là ma trận Laplacian. Dựa vào các ma trận trên để định nghĩa độ tương tự hoặc khoảng cách giữa các đồ thị. Ma trận đồ thị Laplacian phi chuẩn [1] được ký hiệu là L, là ma trận biểu diễn cho đồ thị thông qua ma trận liền kề W và ma trận bậc D, được định nghĩa như sau: LDW  – (4.0) Các ma trận đồ thị Laplacian chuẩn được định nghĩa như sau: 1/2 1/2 Lsym  D LD (4.1) 1 LDLrw  (4.2) D là ma trận có đường chéo chính là các số dương, do vậy D-1/2 chính là ma trận có các phần tử trên đường chéo chính là căn bậc hai của các phần tử tương ứng của D. Tương tự, D-1 là ma trận nghịch đảo của D. 34 Lý thuyết đồ thị quang phổ (spectral graph theory) dựa vào ma trận Laplacian đã chỉ ra rằng một số cấu trúc cơ bản có thể có cùng tính chất Laplacian. Ma trận và các giá trị đặc trưng (eigenvectors) có thể được sử dụng để mô tả nhiều tính chất của đồ thị. Dựa vào lý thuyết đồ thị quang phổ, chúng ta chọn k (k < N) giá trị đặc trưng N nhỏ nhất X = e1, , ek (∀i = [1, .., k], ei ∈ R ) của ma trận Laplacian. Thay vì xét trong không gian N × N chiều, chúng ta chỉ cần xét N đối tượng trong không gian con k × k chiều. Hàng xi ∈ X sẽ biểu diễn cho vi ∈ V. Bằng cách đó chúng ta rút gọn được ánh xạ đồ thị G vào X, trong đó độ tương tự của hai đỉnh vi và vj được xác định là khoảng cách giữa hai giá trị đặc trưng tương ứng của chúng. Do vậy, chúng ta có thể đồng nhất ba ký hiệu: đối tượng i, vector xi và đỉnh vi là tương đương với nhau theo nghĩa biểu diễn cho cùng một thực thể dữ liệu 2.1.3 Các thuật toán phân cụm phổ 2.1.3.1 Thuật toán phân cụm quang phổ phi chuẩn Input: + Ma trận liền kề W ∈ Rn×n của đồ thị G = (V, E) + Ma trận bậc D của đồ thị G + Số cụm K Output: Các cụm C1, , CK 1. Tính ma trận Laplacian L = D – W 2. Tính K vector giá trị đặc trưng u1, , uK của L ứng với K giá trị đặc trưng nhỏ nhất n×K 3. Đặt U ∈ R là ma trận có các cột là các vector giá trị đặc trưng u1, , uK 4. for i = 1 to n do K 5. yi ∈ R là vector ứng với hàng thứ i của U 6. Gọi thuật toán K-means đối với các tâm cụm y1, , yK để phân V thành K cụm. 2.1.3.2 Thuật toán phân cụm quang phổ chuẩn hóa Input: + Ma trận liền kề W ∈ Rn×n của đồ thị G = (V, E) + Ma trận bậc D của đồ thị G + Số cụm K 35 Output: Các cụm C1, , CK -1/2 -1/2 1. Tính ma trận Laplacian chuẩn hóa Lsym = D LD 2. Tính K vector giá trị đặc trưng đầu u1, , uK của Lsym n×K 3. Đặt U ∈ R là ma trận có các cột là các vector giá trị đặc trưng u1, , uK 4. Tạo ra ma trận T ∈ Rn×K từ U bằng cách chuẩn hóa các hàng theo chuẩn 1 5. for i = 1 to n do K 6. yi ∈ R là vector ứng với hàng thứ i của T 7. Gọi thuật toán K-means đối với các tâm cụm y1, , yK để phân V thành K cụm. 2.2 Phương pháp tra cứu ảnh sử dụng phân cụm phổ 2.2.1 Phát biểu bài toán Tra cứu ảnh dựa vào nội dung đã 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, NeTra, PicHunter, Blobworld, 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. Đối với cách tiếp cận truy vấn bởi mẫu, một ảnh truy vấn đưa vào hệ thống sẽ được xử lý tương tự như ảnh cơ sở dữ liệu để sinh ra một véctơ thích hợp. Tra cứu tiếp theo được thực hiện bằng việc sinh ra một danh sách các ảnh được phân hạng theo thứ tự giảm dần của độ đo tương tự so với ảnh truy vấn. 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 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 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 các 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 36 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ách tiếp cận dựa vào phản hồi liên quan đối với tra cứu ảnh dựa vào nội dung là một lĩnh vực nghiên cứu tích cực trong mấy năm qua nhằm rút ngắn khoảng cách ngữ nghĩa. Hầu hết các hệ thống CBIR đã có biểu diễn các ảnh bằng các véctơ đặc trưng sử dụng các đặc trưng trực quan, trong đó hai véctơ được coi là gần nhau nếu hai ảnh tương ứng với hai véctơ đó sẽ tương tự nhau hơn. Khi các hệ thống CBIR đưa ra một tập các ảnh được xem là tương tự với một ảnh truy vấn đã cho, người dùng có thể lấy ra các ảnh liên quan nhất đối với truy vấn đã cho và hệ thống điều chỉnh lại truy vấn sử dụng các ảnh liên quan mà người dùng vừa chọn. Các kỹ thuật CBIR dựa vào phản hồi liên quan không yêu cầu người dùng cung cấp các truy vấn khởi tạo chính xác nhưng yêu cầu người dùng xây dựng truy vấn lý tưởng thông qua đánh giá các ảnh là liên quan hay không. Các cách tiếp cận đối với CBIR giả thiết rằng, về nguyên tắc các ảnh liên quan gần với ảnh truy vấn trong không gian đặc trưng nào đó. Tuy nhiên, sự tương tự giữa các ảnh mà con người nhận thức lại có sự khác biệt với khoảng cách giữa chúng trong không gian đặc trưng. Tức là, các ảnh liên quan về mặt ngữ nghĩa có thể nằm phân tán trong toàn bộ không gian đặc trưng và nằm rải rác ở một số cụm chứ không phải một cụm. Trong trường hợp này, các cách tiếp cận phản hồi liên quan truyền thống không làm việc tốt khi dịch chuyển tâm truy vấn. Thực hiện phản hồi liên quan đề cập đến việc tính toán một hoặc nhiều điểm truy vấn mới trong không gian đặc trưng và thay đổi hàm khoảng cách. Cách tiếp cận có hiệu quả là sử dụng một phương pháp phân cụm để tính toán các điểm truy vấn mới sử dụng các các kết quả truy vấn (các ảnh liên quan) dựa vào đánh giá phản hồi của người dùng. Chính vì vậy, trong phần này, luận văn sẽ trình bày việc áp dụng phương pháp tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan [5] [13] . 37 2.2.2 Phân tích và xây dựng mô hình Tập kết Véctơ đặc quả trưng So sánh Độ tượng Tập ảnh Phản hồi Tập ảnh tự tra cứu phản hồi Tập các véctơ đặc trưng Phân hạng Tra cứu Phân cụm đa điểm phổ Truy vấn Các cụm Tập ảnh đa điểm Tạo các ngữ nghĩa điểm Hình 2.3. Cấu trúc của phương pháp SCRF Phương pháp SCRF được mô tả bởi sơ đồ trên Hình 2.3. Quá trình tra cứu bắt đầu từ việc trích rút đặc trưng của ảnh truy vấn. Các đặc trưng của ảnh cơ sở dữ liệu thường được trích rút và lưu trữ thành tập các véctơ đặc trưng. Sử dụng các đặc trưng này với một độ đo tương tự đặc trưng, sự tương đồng giữa ảnh truy vấn và ảnh cơ sở dữ liệu được so sánh và phân hạng. Tiếp theo, một tập ảnh lân cận với ảnh truy vấn khởi tạo được trả về cho người dùng. Người dùng sẽ chọn những ảnh liên quan tới mong muốn của họ để hình thành lên tập ảnh phản hồi. Thuật toán phân cụm phổ sẽ được áp dụng lên tập ảnh phản hồi để hình thành lên các cụm liên quan ngữ nghĩa. Với mỗi cụm vừa tìm được, phương pháp SCRF sẽ thực hiện tìm đại diện cho mỗi cụm để hình thành truy vấn đa điểm đưa vào thực hiện tra cứu ở lần lặp sau. Quá trình được lặp lại cho đến khi người dùng ngừng phản hồi và phương pháp đưa ra tập kết quả. 2.2.3 Phân cụm phổ với phản hồi liên quan 2.2.3.1 Ý tưởng Tư tưởng chính của phương pháp phân cụm phổ với phản hồi liên quan là thay vì tìm một truy vấn trung tâm cho các mẫu tích cực mà người dùng chọn, phương pháp SCRF sẽ thực hiện phân cụm tập ảnh phản hồi của người dùng. Sau khi có được 38 các cụm ngữ nghĩa đó, SCRF sẽ tìm đại diện cho mỗi cụm. Mỗi đại diện đó được dùng để hình thành lên truy vấn đa điểm ở lần lặp tra cứu tiếp theo. Phương pháp SCRF sẽ tìm các ảnh tương tự với bất kỳ điểm nào hay đại diện nào của truy vấn đa điểm để trả về danh sách ảnh đa dạng nằm rải rác trong toàn bộ không gian đặc trưng. 2.2.3.2 Thuật toán phân cụm tập ảnh phản hồi từ người dùng Trong tập ảnh lân cận được trả về bởi truy vấn khởi tạo người dùng sẽ chọn n ảnh liên quan. Để khai thác thông tin tương tự giữa các ảnh trong tập ảnh phản hồi chúng ta gọi thuật toán phân cụm sử dụng k véctơ riêng (Clustering Relevant Images Set using Eigenvectors- CRISE) để hình thành lên các các cụm ngữ nghĩa. Mỗi ảnh được chọn để đại diện cho mỗi cụm phải là ảnh mà tương tự nhất với tất cả các ảnh trong cụm. Các đại diện của các cụm sẽ hình thành lên truy vấn đa điểm ở lần lặp tra cứu tiếp theo. Quá trình trên được lặp lại cho đến khi người dùng dừng phản hồi. Dưới một biểu diễn đồ thị, phân cụm có thể được phát biểu tự nhiên như một bài toán phân hoạch đồ thị. Ở đây, chúng ta sử dụng phương pháp sử dụng k véctơ riêng và tính trực tiếp phân hoạch k-way . So với phương pháp sử dụng một véctơ riêng tại một thời điểm và gọi đệ quy, phương pháp sử dụng k véctơ riêng được chỉ ra là tốt hơn về mặt thực hành. Nói chung, một phương pháp phân hoạch đồ thị cố gắng tổ chức các nút thành các nhóm sao cho độ tương tự trong phạm vi nhóm là cao, và/hoặc độ tương tự giữa các nhóm là thấp. Một đồ thị đã cho G=(V,E) với ma trận affinity A, một cách đơn giản để định lượng giá cho các nút phân hoạch thành hai tập rời nhau C1 và C2 (CC12   và CCV12) là tổng có trọng số của các cạnh mà kết nối hai tập. Đầu tiên, từ n điểm dữ liệu ảnh, phương pháp xây dựng ma trận affinity A 2 ssij 2 2 (4.3) aij e i  j,0 a ii   2 Ở đây tham số tỉ lệ  điều khiển mức độ áp lực aij giảm nhanh thế nào với khoảng cách giữa si và sj. Một giá trị aij giữa hai ảnh là “cao” nếu hai ảnh là rất tương tự. Xây dựng ma trận đường chéo D trong đó phần tử (i,i) là tổng hàng thứ i của ma Da trận A. D là một ma trận chéo với ii jn1,..., ij 39 Tính ma trận Laplace chuẩn hóa : L = D-1/2 A D-1/2 Tìm k véctơ riêng x1,x2,x1k lớn2 nhấtk của ma trận L, trong đó x1=(x11, x12, x13, , x1n), x2=(x21, x22, x23, , x2n), .xk=(xk1, xk2, xk3, , xkn) và xây dựng ma trận X = [x T ,x T ,,x T ] Є Rn x k Xây dựng ma trận Y từ X bằng việc chuẩn hóa mỗi dòng của X là chiều dài đơn vị của ma trận Y x Y  ij ij 1 (4.4) x2 2  j ij  Mỗi dòng của ma trận Y được xem như là một điểm trong không gian véctơ k k chiều. Đến đây, sẽ có n điểm trong không gian R , phân cụm (yi)i=1n trong không k gian R thành k cụm C1,C2,,Ck thông qua K-Means. Cuối cùng, gán điểm si tới cụm j nếu và chỉ nếu hàng thứ i của ma trận Y tương ứng với cụm j. Hình 2.4 mô tả thuật toán phân cụm sử dụng k véctơ riêng CRISE thực hiện việc phân cụm tập các ảnh liên quan mà người dùng chọn thành k cụm. Thuật toán CRISE Input: - Tập các ảnh SR{s1 , s 2 ,... sn }; s i * - Số cụm k; Output: k cụm: CCC12, ,... k ; Bước 1: Xây dựng ma trận affinity For i  1 to n do For j  1 to n do If ij a exp( ij 2 Else a0ij  Bước 2: Xây dựng ma trận đường chéo và ma trận Laplace L For i  1 to n do da ii jn1,..., ij L D1/2 AD 1/2 Bước 3 : Tìm k véctơ riêng lớn nhất x12, x ,..., xn của ma trận Laplace For i  1 to k do 40 xi Largest_eigen_vector(L) TTT X  x12, x ,..., xk Bước 4: Xây dựng ma trận Y từ X For i  1 to n do For j  1 to n do 1/2 y x/ x2 ij ijk ik  Y  y12, y ,... yk  Bước 5: Phân thành k cụm thông qua K-Means P  For i  1 to n do pyii P P pi K-Mean(P) Bước 6: Gán các si vào các cụm For i  1 to n do If pC ij ik1,..., Cj C j s i Return CCC12, ,..., k Hình 2.4. Thuật toán CRISE [5] 2.2.3.3 Tìm ảnh đại diện cho cụm Để thực hiện việc tra cứu ảnh hiệu quả, một ảnh đại diện thích hợp phải thu được cho mỗi cụm. Ở đây, một ảnh được chọn là đại diện cho một cụm phải là ảnh mà tương tự nhất với tất cả các ảnh trong cụm. Phát biểu này được minh họa bằng toán học như sau: Với một biểu diễn đồ thị của các ảnh được cho G=(V,E) với ma trận affinity A, cho tập các cụm ảnh là {C1, C2,, Ck} (tập các cụm này cũng này k cũng là một phân hoạch của V, tức là ( CCij   và ii1CV) thì ảnh đại diện của là arg max a j Ci  jC jt (4.5) i 41 Như vậy, với một cụm, ảnh đại diện là ảnh mà có tổng độ tương tự trong phạm vi cụm là cực đại. 2.2.3.4 Khoảng cách từ một ảnh đến truy vấn đa điểm Khác với các phương pháp tra cứu ảnh khác, phương pháp này sẽ hình thành lên truy vấn đa điểm MQ=(Q1, Q2,.. Qk) từ các đại diện của mỗi cụm. Khi đó, khoảng cách từ một ảnh đến truy vấn đa điểm MQ=(Q1, Q2,.. Qk) là cực tiểu của các khoảng cách có trọng số từ một ảnh đến mỗi Qj trong truy vấn đa điểm và được tính theo công thức : D( DIi , MQ ) min j1... k dist ( DI i , Q j ) (4.6) Trong công thức (4.6), dist(,) DIij Q với i=1, N, j=1, k là khoảng cách từ một ảnh DIi đến một điểm truy vấnQ j trong truy vấn đa điểm MQ. 2.2.3.5 Thuật toán tra cứu ảnh sử dụng phân cụm phổ trong phản hồi liên quan Hình 2.5 dưới đây mô tả Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi, có tên SCRF. Khi người dùng thực hiện truy vấn, phương pháp sẽ sử dụng thuật toán MQMRBR để tra cứu trên tập các ảnh cơ sở dữ liệu DI và cho kết quả là tập các ảnh S. Người dùng thực hiện việc chọn tập các ảnh liên quan E trong tập S thông qua hàm User_Choose_RelevanceImage(), phương pháp sẽ phân cụm tập E này thành k cụm thông qua thuật toán CRIES và tìm đại diện cho k cụm đó thông qua hàm Compute_Representative() và gán cho tập đại diện. Khoảng cách giữa ảnh cơ sở dữ liệu DIi và truy vấn đa điểm MQ được tính theo công thức (4.6). Quá trình này tiếp tục cho đến khi người dùng dừng việc chọn các ảnh liên quan. Thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan Input Tập N ảnh cơ sở dữ liệu DI Ảnh truy vấn Q Output Tập ảnh kết quả S’ 42 MQMRBR (DI, Q, S) // thực hiện trên tập ảnh DI với truy vấn Q để cho ra tập kết quả S Repeat E  User_Choose_Relevancelmage (S, n) // người dung chọn các ảnh liên quan từ tập S C  CRIES (E, k) // phân tập ảnh liên quan E thành k cụm RI  Compute_Representative (C, M) For I 1 to N do For j 1 to k do Tính disi theo công thức sau: disi = min j = 1k disij Sort (DI) // Sắp xếp các ảnh trong tập ảnh cơ sở dữ liệu DI theo thứ tự tăng dần của khoảng cách so với truy vấn đa điểm MQ. Return S’ // danh sách ảnh có khoảng cách nhỏ nhất với MQ Untill (User dừng phản hồi) Hình 2.5. Thuật toán SCRF [5] 2.3 Kết luận chương Nhằm tạo nâng cao hiệu quả tra cứu ảnh, qua tham khảo các tài liệu liên quan (đặc biệt là tài liệu [5]) học viên quyết định áp dụng thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan (SCRF) nhằm mục đích nâng cao chất lượng tra cứu ảnh. Thuật toán này nhằm giải quyết hai vấn đề chính đó là: (1) tìm các ảnh liên quan ngữ nghĩa nằm rải rác trong toàn bộ không gian đặc trưng với độ chính xác cao và (2) thời gian tra cứu không tăng theo số phản hồi của người dùng. Để giải quyết được hai vấn đề này, thuật toán đã tận dụng sự đánh giá của người dùng để hình thành tập ảnh liên quan và phân cụm chúng thành các cụm ngữ nghĩa nằm rải rác trong toàn bộ không gian đặc trưng và đại diện của mỗi cụm hình thành lên truy vấn đa điểm. Phương pháp sử dụng một thuật toán phân cụm phổ sử dụng k véctơ riêng (CRISE) có ưu điểm phân cụm các ảnh được kết nối với nhau nhưng không nhất thiết phải nhóm vào trong một đường bao lồi nên thực hiện tốt hơn các thuật toán phân cụm truyền thống. Từ đó có thể tra cứu được các ảnh nằm rải rác trong toàn bộ không gian đặc trưng và nâng cao độ chính xác. Hiệu quả của việc áp dụng thuật 43 toán sẽ được chứng minh trong việc xây dựng chương trình mô phỏng được trình bày chi tiết trong chương 3 của luận văn. 44 CHƯƠNG 3 CHƯƠNG TRÌNH THỬ NGHIỆM Trên cơ sở các kiến thức cơ bản đã được giới thiệu trong chương 1 và chương 2 của luận văn, nội dung chương 3 sẽ đi sâu vào mô tả việc xây dựng chương trình thử nghiệm để đánh giá ảnh hưởng của các phương pháp trích chọn đặc trưng, các phương pháp tính toán độ đo tương tự cũng như hiệu quả khi áp dụng thuật toán SCRF đến chất lượng tra cứu ảnh. 3.1 Thiết kế mô hình thử nghiệm 3.1.1 Công cụ Chương trình ứng dụng được xây dựng trên giao diện GUI của phần mềm Matlab 2019b. Sở dĩ học viên lựa chọn xây dựng phần mềm mô phỏng trên Matlab vì đây là phần mềm chuyên dụng cho tính toán số liệu dưới dạng ma trận và ảnh số cũng là một đối tượng. Ngoài ra, Matlab cũng tích hợp rất nhiều các công cụ hỗ trợ cho xử lý ảnh, phân cụm đồ thị. Các công bố về các phương pháp tra cứu ảnh cũng đa phần sử dụng Matlab nên rất tiện cho việc so sánh và đánh giá hiệu quả của các phương pháp. Hình 3.1. Giao diện chương trình thực nghiệm 45 Hình 3.1 mô tả giao diện của chương trình thực nghiệm. Chương trình gồm ba phần thiết lập điều kiện làm việc, chọn điều kiện tra cứu ảnh và hiển thị ảnh kết quả tra cứu. Phần thiết lập điều kiện cho phép người dùng lựa chọn thư mục chứa cơ sở dữ liệu ảnh, tạo các file lưu dữ liệu ảnh dưới dạng .mat để khi thực hiện chỉ cần nạp dữ liệu ảnh, chọn các điều kiện tra cứu và tiến hành tra cứu ảnh. Phần chọn các điều kiện tra cứu ảnh (Hình 3.2) cho phép người dùng chọn các đặc trưng dữ liệu ảnh theo nhu cầu. Các đặc trưng này bao gồm đặc trưng màu và đặc trưng kết cấu, được mô tả chi tiết trong mục 3.2. Ngoài ra, người dùng cũng có thể lựa chọn phương pháp xác định độ đo tương tự để từ đó đánh giá được phương pháp nào là phù hợp nhất đối với cơ sở dữ liệu ảnh tương ứng (các phương pháp này sẽ được trình bày chi tiết trong mục 3.3). Phần này cũng cho phép lựa chọn số ảnh được hiển thị khi tra cứu và số cụm khi sử dụng thuật toán tra cứu ảnh hiệu quả sử dụng phân cụm phổ trong phản hồi liên quan (SCRF). Hình 3.2. Chọn các điều kiện tra cứu ảnh Phần hiển thị ảnh kết quả tra cứu cho phép người dùng xem trực quan tối đa 20 ảnh kết quả đầu tiên khi thực hiện tra cứu với các điều kiện đã chọn trước. Trên giao diện này cũng cho phép người dùng phản hồi liên quan qua thao tác click chọn vào các hình ảnh mong muốn. 46 3.1.2 Chuẩn bị dữ liệu 3.1.2.1 Tập dữ liệu thử nghiệm Nhờ các chức năng thiết lập điều kiện làm việc, chương trình cho phép người dùng có thể làm việc với mọi loại cơ sở dữ liệu ảnh khác nhau. Tuy nhiên, trong khuôn khổ giới hạn của một luận văn thạc sĩ, tập dữ liệu được học viên sử dụng trong thử nghiệm là tập dữ liệu Wang bao gồm 1000 ảnh tự nhiên được tổ chức thành 10 thể loại khác nhau (10 lớp) [14] , [15] : Peoples, Beaches, Ancient architecture, Buses, Dinosaurs, Elephants, Flowers, Horses, Mountains, Foods. Mỗi lớp có 100 ảnh, tất cả các ảnh là ảnh mầu, định dạng .jpg, kích thước mỗi ảnh là 384 pixel x 256 pixel. Hình 3.3 minh họa một số ảnh mẫu trong tập dữ liệu này. Africa Beaches Ancient architecture Buses Dinosaurs Elephants Flowers Horses Mountains Foods Hình 3.3. Các ảnh minh họa cho 10 thể loại trong tập ảnh Wang 3.2 Trích chọn đặc trưng Các đặc trưng được chia làm hai loại là: các đặc trưng màu và các đặc trưng kết cấu (xem Bảng 3.1). Mỗi ảnh được sử dụng có thể được biểu biểu diễn tối đa bởi năm đặc trưng trực quan gồm ba đặc trưng màu và hai đặc trưng kết cấu. Trong trường hợp này, các véctơ đặc trưng tương ứng với mỗi kênh là một bảng hai chiều gồm 1000 dòng (mỗi dòng chứa một véctơ đặc trưng của ảnh) và 190 cột (độ dài tổng của một véctơ đặc trưng). Trong thực nghiệm, người sử dụng có thể lựa chọn một hoặc nhiều đặc trưng để từ đó kiểm tra được ảnh hưởng của các đặc trưng ảnh đến chất lượng của tra cứu ảnh. 47 Bảng 3.1. Các loại đặc trưng Các loại đặc trưng Tên đặc trưng Độ dài Lược đồ màu hsvHistogram 32 Loại đặc trưng Tương quan màu color auto correlogram 64 màu Gắn kết màu colorMoments 6 Loại đặc trưng Biến đổi wavelet waveletTransform 40 kết cấu gabor Wavelet gaborWavelet 48 3.3 Độ đo tương tự Khi các đặc trưng của hình ảnh cơ sở dữ liệu đầu vào được tạo thì người dùng có thể đưa ra một hình ảnh dưới dạng truy vấn để lấy các hình ảnh tương tự từ cơ sở dữ liệu. Vectơ đặc trưng của hình ảnh truy vấn được tính toán lại bằng cách sử dụng các chức năng được giải thích ở trên. Đo lường độ tương đồng là một vấn đề quan trọng khác trong CBIR, trong đó hình ảnh truy vấn được so sánh với các ảnh cơ sở dữ liệu khác để tìm sự giống nhau. Để tính toán sự giống nhau giữa hình ảnh truy vấn đầu vào và hình ảnh cơ sở dữ liệu, sự khác biệt giữa vectơ đối tượng hình ảnh truy vấn và vectơ đặc điểm hình ảnh cơ sở dữ liệu được tính bằng cách sử dụng các số liệu khoảng cách khác nhau. Sự khác biệt càng nhỏ thì hai hình ảnh càng giống nhau. Các thước đo khoảng cách được đánh giá để thử nghiệm trong luận văn là khoảng cách Euclidean, khoảng cách City block, khoảng cách Minkowski và khoảng cách Mahalanobis, khoảng cách L1, L2, cosine và Chebyshev. Khoảng cách Euclide được sử dụng rộng rãi nhất để đo độ tương tự trong tra cứu hình ảnh vì tính khả dụng và hiệu quả của nó. Nó đo khoảng cách giữa hai vectơ bằng cách tính căn bậc hai của tổng các chênh lệch tuyệt đối bình phương theo công thức: n 2 DIDE i i  (4.7) i1 Khoảng cách City block còn được gọi là khoảng cách Manhattan, chỉ thị độ mạnh so với các trường hợp ngoại lệ, được tính là theo công thức: 48 n DIDC i i (4.8) i1 Khoảng cách Minkowski có dạng tổng quát được xác định như sau: 1 n p  (4.9) DIDM i i i1 Khoảng cách Mahalanobis được tính theo công thức: D x T S1 x  (5.0) M h     Khoảng cách Chebyshev được tính theo công thức: DIDChebyshevmax i i  (5.1) i Khoảng cách L1 được tính theo công thức: n IDii DL1   (5.2) i1 1IDii Khoảng cách L2 được tính theo công thức: n 2 DIDL2  i i  (5.3) i1 3.4 Mô hình truy vấn Để bắt chước hành vi của con người, luận văn thực hiện mô phỏng phản hồi liên quan trong thử nghiệm. Đầu tiên, truy vấn khởi tạo sẽ được thực hiện để tạo ra kết quả truy vấn. Học viên mô phỏng tương tác người dùng bằng việc chọn n ảnh liên quan từ kết quả tra cứu khởi tạo dựa vào tập tin cậy nền (ground truth). Những ảnh liên quan từ lần lặp phản hồi đầu tiên sẽ được phân thành k cụm và thực hiện tìm đại diện cho k cụm này. Sau đó k đại diện được dùng để xây dựng truy đa điểm phục vụ cho tra cứu tiếp theo. Cuối cùng, những kết quả tra cứu được gộp lại để tạo ra một danh sách kết quả tổng hợp theo chiến lược truy vấn đa điểm tách rời. Phản hồi liên quan được thực hiện theo chiến lược chọn những ảnh liên quan đầu tiên (dựa vào tập tin cậy nền) trong danh sách kết quả. Trong chiến lược này, trường hợp xấu nhất là không có ảnh liên quan nào