Chương 1 TỔNG QUAN VỀ TRA CỨU ẢNH 1. Giới thiệu về hệ thống tra cứu ảnh Từ hai thập kỉ qua, sự xuất hiện của Internet đã thay đổi hoàn toàn cách thức chúng ta tìm kiếm thông tin. Ví dụ, khi làm việc với văn bản, ta chỉ cần đơn giản gõ một vài từ khóa vào máy tìm kiếm Google hay Bing để ngay lập lức có được một danh sách tương đối chính xác các trang web có liên quan. Ta cũng có các hệ thống tương tự với ảnh.
Với hệ thống này, bằng cách lấy một ảnh đầu vào từ người sử dụng, hệ thống cố gắng tìm kiếm các ảnh giống nhất trong dữ liệu, rồi trả lại cho người sử dụng. Một cách lý tưởng, sự giống nhau ở đây được định nghĩa dựa trên sự giống nhau giữa các khái niệm được thể hiện trong ảnh. Đây là hệ thống Tra cứu ảnh theo nội dung hay đơn giản là tra cứu ảnh (“content-based image retrieval” viết tắt là CBIR). Các hệ thống này thường trích rút các biểu diễn trực quan của ảnh và định nghĩa các hàm tìm kiếm, đối sánh mối liên quan khi tra cứu dáp ứng yêu cầu người dùng.
Lĩnh vực này đã được cộng đồng nhiên cứu quan tâm trong những năm qua.1 Các thành phần của hệ thống CBIR Một hệ thống CBIR gồm các thành phần cơ bản mô tả trong sơ đồ Hình 1. Hệ thống tra cứu ảnh theo mội dung download by : skknchat@gmail.com 6 Một hệ thống tra cứu ảnh có thể thực hiện qua nhiều công đoạn: nhập ảnh truy vấn, nhập dữ liệu ảnh cho csdl, chuẩn hóa ảnh, trích chọn đặc trưng của ảnh truy vấn và ảnh trong cơ sở dữ liệu, tính toán độ tương tự và cách hiển thị kết quả lên màn hình… Tuy nhiên chúng ta có miêu tả khái quát một hệ thống tra cứu ảnh thông qua những công đoạn chính sau: Hình 1. Cấu trúc của hệ thống tra cứu ảnh theo nội dung - 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ế. + Trích chọn đặc trưng cho ảnh truy vấn: Ở công đoạn này ảnh truy vấn ngay khi ảnh được nhập vào hệ thống sẽ xử lý để trích chọn đặc trưng theo đặc trưng nhất định nào đó và phục vụ tính toán độ tương đồng sau đó đưa ra kết quả, có thể nói công đoạn này sẽ được tính toán online. download by : skknchat@gmail.com 7 + Trích chọn đặc trưng ảnh trong cơ sở dữ liệu: Đây là công đoạn tính toán đặc trưng cho ảnh trong cơ sở dữ liệu sinh ra cơ sở dữ liệu lưu trữ các đặc trưng, công đoạn này thường sẽ được tính toán từ khi nhập ảnh vào cở sở dữ liệu, hoặc tiến hành khi người dùng cho phép thực hiện hay nói cách khác nó được tiến hành offline.
- Đ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 ả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á download by : skknchat@gmail.com 8 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. - Đá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. Khi đã giảm được số chiều thì dữ liệu đa chiều được đánh chỉ số.
- Tra cứu và hiển thị kết quả: Hiển thị kết quả vừa thu được cho người dùng theo một giá trị ngưỡng tương tự nào đó. - Phản hồi liên quan: Kĩ thuật phản hồi liên quan được sử dụng nhằm thu hẹp “khoảng trống ngữ nghĩa” trong CBIR, cải thiện kết quả tra cứu thông qua tương tác giữa người dùng và máy. Một kịch bản thông thường cho phản hồi liên quan trong CBIR như sau: Bước 1: Máy tính đưa ra các kết quả tra cứu khởi tạp (top-k)thôngqua ảnh truy vấn. Bước 2: Người dùng cung cấp đánh giá trên kết quả top-k, đánh giá theo kiểu như “liên quan” hoặc “không liên quan” với nhận thức của chính người dùng đó.
Bước 3: Máy học và thử lại. Lặp lại bước 2. Các thành phần cơ bản của hệ thống CBIR: - Cơ sở dữ liệu ảnh: Là cơ sở dữ liệu phục vụ lưu trữ ảnh. Có thể là trên ổ cứng thường, cũng có thể là hệ quản trị cơ sở dữ liệu.
- Cơ sở dữ liệu đặc trưng: Các đặc trưng đã được trích chọn offline sẽ được lưu trữ trong cơ sở dữ liệu như tệp tin matlab, bảng tính excel,… download by : skknchat@gmail.com 9 Quá trình thực thi của hệ thống tra cứu ảnh: + Người dùng đưa ra truy vấn hoặc ảnh có sẵn. + Hệ thống đón nhận truy vấn hoặc ảnh, sau đó trích chọn các đặc trưng. + Hệ thống so sánh truy vấn hoặc ảnh với cơ sở dữ liệu đặc trưng đã có. + Hệ thống trả ra kết quả tra cứu.
Một hệ thống tra cứu ảnh cần đáp ứng được: + Nhu cầu sử dụng hình ảnh của người dùng và thông tin đi kèm ảnh. + Cách mô tả nội dung ảnh. + Trích chọn đặc trưng từ ảnh. + Lưu trữ cơ sở dữ liệu ảnh.
+ Truy vấn và lưu trữ hình ảnh tương tự. + Truy xuất hình ảnh trong cơ sở dữ liệu hiệu quả. + Giao diện thân thiện, phù hợp.2 Tra cứu ảnh theo nội dung sử dụng kỹ thuật máy học Các kỹ thuật học máy có hiệu năng tăng đáng kể đối với các hệ thống CBIR như các kỹ thuật máy vector hỗ trợ (SVM), học tăng cường (AdaBoost),… Một hạn chế là không có dữ liệu huấn luyện từ trước với mỗi truy vấn cụ thể, dữ liệu huấn luyện chỉ có được sau khi người dùng phản hồi với ảnh truy vấn được đưa vào bởi một người dùng. Bên cạnh dữ liệu huấn luyện là tương đối ít và dữ liệu kiểm tra bị nhiễu do vấn đề khoảng trống ngữ nghĩa.
Kỹ thuật AdaBoost download by : skknchat@gmail.com 10 Kỹ thuật AdaBoost đã được áp dụng trong một số hệ thống CBIR nhằm mục đích tăng cường các thuật toán học yếu, đòi hỏi dữ liệu được đánh trọng số trước khi thực hiện thuật toán học ở mỗi lần lặp. Tuy nhiên, các kỹ thuật dựa vào AdaBoost thường phân lớp chậm và cần nhiều lần lặp phản hồi. Boosting là phương pháp cho phép cải thiện độ chính xác của bất kì thuật toán học nào. Đây là một loại phương pháp tổ hợp, cho phép kết hợp các phương pháp phân lớp yếu thành một phân lớp mạnh hơn 𝐿 𝐹(𝑥) = ∑ 𝛼𝑖 𝑓𝑖 (𝑥) 𝑙=1 trong đó 𝛼𝑖 xác định trọng số của bộ học yếu thứ l.
Kỹ thuật Boosting thực hiện lặp đi lặp lại, sao cho mỗi lần lặp l, phân lớp yếu đưa vào tổ hợp cho tới khi đạt tiêu chuẩn dừng. AdaBoost dẫn đến các biến thể boosting phổ biến hiện nay và đã trở thành một trong những thuật toán học mạnh. Trong quá trình học, giữ phân bố trọng số 𝐷𝑙 (𝑖)trên các mẫu huấn luyện. Theo phân bố này, tại mỗi lần lặp Boosting sẽ lựa chọn bộ học yếu và đưa them vào mô hình.
Sau mỗi lần lặp l, mẫu được đánh lại trọng số, dựa vào một hàm lỗi (loss function). Nhằm tập trung vào các mẫu khó, bỏ qua các mẫu dễ. Giải thuật AdaBoost là thuật toán học hiệu quả và phổ biến, do khá dễ dàng cài đặt, hầu như không cần thiết tới tham số hiệu chỉnh. Trên thực tế chỉ có một tham số là số tối đa L lần lặp.
Việc thiết lập tham số rất quan trọng bởi vì thuật toán có thể có xu hướng overfit (quá khớp) nếu thiết lập L lớn. Kỹ thuật máy vector hỗ trợ (SVM) Các kĩ thuật học máy và phản hồi liên quan được đề xuất nhằm hỗ trợ hiệu chỉnh truy vấn. Hầu hết các kĩ thuật truyền thống đều đòi hỏi lượng lớn download by : skknchat@gmail.com 11 mẫu dữ liệu huấn luyện và truy vấn khởi tạo với các mẫu tốt. Trong nhiều tình huống ứng dụng thực tế các thuật toán học có thể làm việc ngay cả khi nghèo dữ liệu huấn luyện và hạn chế thời gian huấn luyện.
Để giảm số lượng mẫu yêu cầu, các truy vấn quan tâm đến các kĩ thuật học tích cực. Một trong những phương pháp như vậy là SVM, dựa vào phản hồi liên quan khi phân lớp. Học tích cực có thể được mô hình hoá như sau: Cho một cơ sở dữ liệu E chứa một tập con chưa gán nhãn U và một tập con X đã gán nhãn. Phương pháp học gồm hai thành phần f và s.
Thành phần f là một phân lớp được huấn luyện trên tập dữ liệu đã gán nhãn X. Thành phần s là hàm lấy mẫu đưa ra một tập gán nhãn hiện thời X, quyết định lựa chọn tập con 𝑢 ∈ 𝑈 chọn cho truy vẫn người dùng.