Chương 1: Khái quát về CBIR và học trên đồ thị Chương này trình bày tổng quan tra cứu ảnh dựa trên nội dung; tra cứu ảnh dựa trên nội dung với phản hồi liên quan; các phương pháp học máy và học trên đồ thị gồm có các mô hình Học có giám sát (Supervised learning), Học không giám sát (Unsupervised learning), Học bán giám sát (Semn- Supervised learning). Chương 2: Tra cứu ảnh dựa trên xếp hạng đa tạp Tập trung tìm hiểu phương pháp học bán giám sát trên đồ thị qua thuật toán lan truyền nhãn. Đồng thời tập trung nghiên cứu phương pháp tra cứu ảnh dựa trên xếp hạng đa tạp và cải tiến phương pháp này khi áp dụng vào tra cứu đữ liệu ảnh có số lượng lớn. Chương 3: Thực nghiệm Cài đặt thử nghiệm chương trình tra cứu ảnh dựa trên nội dung theo mô hình học bán giám sát trên đồ thị qua thuật toán xếp hạng đa tạp (MR) và thuật toán xếp hạng đa tạp cải tiến (EMR).
So sánh hiệu năng của hai thuật toán này. xi CHUONG 1: KHAI QUAT VE CBIR VA HOC TREN DO THI 1.1 Tra cứu ảnh dựa trên nội dung với phản hồi liên quan 1.1 Giới thiệu Hệ thống tra cứu ảnh dựa trên nội dung (Content Based Image Retrieval - CBIR) là một công cụ mạnh vì nó tra cứu ảnh trong cơ sở dữ liệu ảnh bằng việc sử dụng dấu hiệu trực quan. Các hệ thống tra cứu ảnh dựa trên nội dung trích rút các đặc trưng từ bản thân các ảnh và tính toán độ đo tương tự giữa ảnh truy vấn và các ảnh cơ sở dữ liệu đựa trên các đặc trưng này. Tra cứu ảnh dựa trên nội dung trở nên rất phổ biến do nhu cầu tra cứu ảnh trong các cơ sở dữ liệu lớn tăng nhanh.
Bởi vì tốc độ và độ chính xác là quan trọng, việc tiếp tục phát triển các hệ thống tra cứu ảnh đảm bảo độ chính xác và có tốc độ nhanh là cần thiết. Tra cứu ảnh dựa trên nội dung ứng dụng vào vào rất nhiều công việc hữu ích như: tìm các ảnh phong cảnh trên Internet, điều tra hình sự dựa vào vân tay và dấu chân, chuẩn đoán bệnh trong y tế, sử dụng trong các hệ thống thông tin địa lý và viễn thám, sử dụng cho tra cứu các phần video như phim và trò chơi, các ứng dụng khác bao gồm bảo tàng trực tuyến, quảng cáo. Những thành phân của một hệ thống tra cứu ảnh dựa trên nội dung: Một hệ thống tra cứu ảnh đòi hỏi các thành phần như trong Hình 1-1. Trong đó có ba thành phần quan trọng nhất trong tra cứu ảnh dựa trên nội dung: trích chọn đặc trưng, đánh chỉ số và giao diện truy vấn cho người dùng.
Các bước tra cứu ảnh trong CBIR thường bao gôm : -_ Tiếp nhận truy vấn của người dùng (dưới dạng ảnh hoặc phác thảo). -_ Trích chọn đặc trưng của truy vấn và lưu trữ vào cơ sở dữ liệu đặc trưng như là một vector hoặc không gian đặc trưng. - So sánh độ tương tự giữa các đặc trưng trong cơ sở dữ liệu với nhau từng đôi một. - Lap chi mục cho các vector đê nâng hiệu quả tra cứu.
~_ Trả lại kết quả tra cứu cho người dùng. Trích chọn đặc trưng Tính toán độ đo Hiển thị Ảnh truy vấ An muy ven Ảnh truy vấn tương tự kết quả Cơ sở Dữ liệu Cơ sở Dữ liệu đặc trưng Trích chọn đặc trưng lộ Hình 1-1: Kiến trúc tổng quan về hệ thống tra cứu ảnh dựa trên nội dụng 1.2 Kiến trúc tong quan của hệ thống CBIR với phản hồi liên quan 1.1 Khái niệm phản hồi liên quan Phản hồi liên quan là một kỹ thuật sửa đổi truy vấn, nó bắt nguồn trong thông tin tra cứu và qua đó sẽ tập hợp lại những đặc trưng tra cứu chính xác từ phía người dùng bằng việc lặp đi lặp lại việc phản hồi, sau đó hệ thống sẽ lọc ra thông tin chính xác. Phản hồi liên quan có thê được coi là một mô hình tìm kiếm thay thế, bổ sung cho những mô hình khác như tìm kiếm dựa trên từ khóa. Trong trường hợp không có một khuôn khổ đáng tin cậy để mô hình hóa ngữ nghĩa ảnh mức cao và nhận thức chủ quan thì phản hồi liên quan sẽ là một phương thức để tìm hiểu các trường hợp cụ thể của ngữ nghĩa truy vấn.
Để giải quyết những vấn đề này, tương tác phản hôi liên quan, một kỹ thuật trong hệ thống tìm kiếm thông tin dựa trên văn bản truyền thống, đã đươc giới thiệu. Với phản hồi liên quan, có thê thiết lập liên kết giữa các khái niệm mức cao và đặc trưng mức thấp. Ý tưởng chính là sử dụng các mẫu đương và mẫu âm từ người sử dụng để cải thiện hiệu suất hệ thống. Đối với một truy vấn nhất định, đầu tiên hệ thống sẽ trả về một danh sách các hình ảnh đươc xếp theo một độ tương tự xác định trước.
Sau đó, người dùng đánh dấu những hình ảnh có liên quan đến truy vấn (mẫu dương) hoặc không có liên quan (mẫu âm). Hệ thống sẽ chọn lọc kết quả tra cứu dựa trên những phản hồi và trình bày một danh sách mới của hình ảnh cho người dùng. Do đó, vấn đề quan trọng trong phản hồi liên quan là làm thế nào đề kết hợp các mẫu dương và mẫu âm đề tỉnh chỉnh các truy vấn và/hoặc điều chỉnh các biện pháp tương tự.2 Kiến trúc tống quan của hệ thống CBIR với RF Phản hỏi liên quan Miêu tả nội dung Các vector trực quan đặc trưng Cơ sở Dữ liệu Miêu tả nội dung Ảnh trực quan Người dùng Ảnh truy vấn So sánh độ đo tương tự Cơ sở Dữ liệu Đặc trưng Sắp xếp các ảnh theo độ đo tương tự Đầu ra Các kết quả tra cứu Hình 1-2: Mô hình tổng quát hệ thống CBIR với phản hôi liên quan Ý tưởng chính của phản hồi liên quan là chuyền trách nhiệm tìm kiếm xây dựng truy vấn đúng từ người dùng sang hệ thống. Đề thực hiện điều này một cách đúng đắn, người dùng phải cung cấp cho hệ thống một số thông tin, để hệ thống có thể thực hiện tốt việc trả lời truy vấn ban đầu.
Việc tìm kiếm ảnh thường dựa trên sự tương tự hơn là so sánh chính xác, kết quả tra cứu sẽ được đưa ra cho người dùng. Sau đó, người dùng đưa ra các thông tin phản hồi trong một bản mẫu “Các quyết định liên quan” thể hiện thông qua kết quả tra cứu. “Quyết định liên quan” đánh giá kết quả dựa trên ba giá trị. Ba giá trị đó là: liên quan, không liên quan, và không quan tâm.
“Liên quan” nghĩa là ảnh có liên quan đến truy vấn của người dùng. “Không liên quan” có nghĩa là ảnh không có liên quan đến truy vấn người dùng. Còn “không quan tâm” 3 nghĩa là người dùng không cho biết bất kỳ điều gì về ảnh. Nếu phản hồi của người đùng là có liên quan, thì vòng lặp phản hồi sẽ tiếp tục hoạt động cho đến khi người dùng hài lòng với kết quả tra cứu.
Như Hình 1-2 mô tả cấu trúc của hệ thống phản hồi liên quan. Trong hệ thống đó có các khối chính là: cơ sở dữ liệu ảnh, trích chọn đặc trưng, đo độ tương tự, phản hồi từ người dùng và thuật toán phản hồi.3 Trích chọn đặc trưng Trích chọn đặc trưng liên quan đến việc trích chọn các thông tin có ý nghĩa từ ảnh. Vì vậy, nó làm giảm việc lưu trữ cần thiết, do đó hệ thống sẽ trở nên nhanh hơn và hiệu qua trong CBIR. Khi đặc trưng duoc trích chọn, chúng sẽ được lưu trữ trong cơ sở đữ liệu để sử dụng trong lần truy vấn sau này.
Mức độ mà một máy tính có thể trích chọn thông tin có ích từ ảnh là van dé then chốt nhất cho sự tiến bộ của hệ thống diễn giải hình ảnh thông minh. Một trong những ưu điểm lớn nhất của trích chọn đặc trưng là nó làm giảm đáng kể các thông tin (so với ảnh gốc) đề biểu diễn một ảnh cho việc hiểu nội dung của ảnh đó. Hiện nay đã có rất nhiều nghiên cứu lớn về các phương pháp tiếp cận khác nhau để phát hiện nhiều loại đặc trưng trong ảnh. Những đặc trưng nảy có thé duoc phân loại như là đặc trưng toàn cục và đặc trưng cục bộ.
Các đặc trưng phổ biến nhất mà được sử dụng là màu sắc, kết cấu va hinh dang. -_ Đặc trưng toàn cục: Đặc trưng toàn cục phải được tính toán trên toàn bộ ảnh. Ví dụ, mức độ màu xám trung bình, biểu đồ về cường độ hình dạng,. Ưu điểm của việc trích chọn toàn cục là tốc độ nhanh chóng trong cả trích chọn đặc trưng và tính toán độ tương tự.
Tuy nhiên, chúng có thể quá nhạy cảm với vị trí và do đó không xác định đươc các đặc tính trực quan quan trọng. Đề tăng cường sự vững mạnh trong biến đổi không gian, chúng ta có thể tìm hiểu trích chọn đặc trưng cục bộ. - Đặc trưng cục bộ: Trong đặc trưng toản cục, các đặc trung duoc tính toán trên toàn bộ ảnh. Tuy nhiên, đặc trưng toàn cục không thê nắm bắt tất cả các vùng ảnh có đặc điểm khác nhau.
Do đó, việc trích chọn các đặc trưng cục bộcủa ảnh là cần thiết. Các đặc trưng đó có thé duoc tính toán trên các kết quả của phân đoạn anh và thuật toán phát hiện biên. Vì thế, tất cả chúng đều dựa trên một phần của ảnh với một số tính chất đặc biệt. -_ Điểm nồi bật: Trong việc tính toán đặc trưng cục bộ, việc trích chọn đặc trưng ảnh bị giới hạn trong một tập nhỏ các điểm ảnh, đó là những điểm chú ý.
Tập các điểm chú ý đươc gọi là những điểm nỗi bật. Những điểm nồi bật là những điểm có dao động lớn trong đặc trưng của vùng lân cận điểm ảnh. Nhiều hệ thống CBIR trích chọn những điểm nổi bật. Năm 2004, Rouhollah và các cộng sự đã định nghĩa điểm nổi bật có mặt trong tra cứu ảnh dựa trên nội dung như là một nhiệm vụ của CBIR, nơi mà người dùng chỉ quan tâm đến một phần của ảnh và phần còn lại là không liên quan.
Ví dụ, chúng ta có thể tham khảo một số đặc trưng cục bộ như là ảnh gốc, đường tròn, đường nét, texel (các phần tử tập trung ở một khu vực kết cấu), hoặc các đặc trưng cục bộ khác, hình dạng của đường nét.4 Độ đo tương tự Trong độ đo tương tự, vector đặc trưng của ảnh truy vấn và vector đặc trưng của ảnh trong cơ sở dữ liệu được đối sánh bằng cách sử dụng một thước đo khoảng cách. Các hình ảnh được xếp hạng dựa trên giá trị khoảng cách.