baouyen2210
New Member
LINK TẢI LUẬN VĂN MIỄN PHÍ CHO AE KET-NOI
1. Nội dung vμ c ̧c yau cầu cần giải quyết trong nhiệm vụ đề tμi tốt nghiệp a. Nội dung:
- Tổng quan về Tra cứu ảnh dựa trên nội dung với phản hồi liên quan
- Tổng quan về mô hình học trên đồ thị.
- Ứng dụng học trên đồ thị cho bài toán tra cứu ảnh.
- Cài đặt chƣơng trình thử nghiệm.
b. C Yêu cầu cần giải quyết
- Hiểu quy trình của một hệ thống tra cứu ảnh dựa trên nội dung, các phƣơng pháp cơ bản trong tra cứu ảnh dựa trên nội dung.
- Hiểu đƣợc một số mô hình học dựa trên đồ thị và áp dụng cho cải thiện hiệu quả tra cứu.
- Cài đặt chƣơng trình thử nghiệm
MỤC LỤC
MỘT SỐ TỪ VIẾT TẮT ................................................................................ 4
MỞ ĐẦU .......................................................................................................... 5
CHƢƠNG 1: Tổng quan về tra cứu ảnh dựa trên nội dung với phản hồi liên quan ........................................................................................... 6
1.1 Khái niệm tra cứu ảnh dựa trên nội dung ............................................. 6
1.2 Những thành phần của một hệ thống tra cứu ảnh dựa trên nội dung.... 6
1.2.1 Các đặc trƣng hình ảnh mức thấp ................................................. 7
1.2.2 Đánh chỉ số.................................................................................... 9
1.2.3 Tƣơng tác ngƣời dùng ................................................................. 10
1.3 Khoảng cách ngữ nghĩa ...................................................................... 12
1.4 Kỹ thuật phản hồi liên quan trong CBIR ............................................ 13
1.4.1 Khái niệm phản hồi liên quan ..................................................... 13
1.4.2 Kiến trúc tổng quan của hệ thống CBIR với phản hồi liên quan 14
1.4.3 Các phƣơng pháp tiếp cận phản hồi liên quan ............................ 17
1.4.4 Những thách thức trong phản hồi liên quan................................ 19
1.5 Các lĩnh vực ứng dụng của tra cứu ảnh dựa trên nội dung ................. 20 CHƢƠNG 2: Mô hình học bán giám sát dựa trên đồ thị ..................... 22
2.1 Khái niệm học máy ............................................................................. 22
2.2 Học bán giám sát................................................................................. 24
2.3 Học bán giám sát dựa trên đồ thị ........................................................ 27
2.3.1 Thuật toán lan truyền nhãn.......................................................... 27
2.3.2 Xây dựng đồ thị........................................................................... 30
2.3.3 Trƣờng ngẫu nhiên Gauss và hàm điều hòa................................ 30
2.4 Kết hợp học bán giám sát với học chủ động (Active Learning)......... 35
2.5 Học siêu tham số của đồ thị (Graph Hyperparameter Learning)........ 39
2.5.1 Phƣơng pháp tối đa Evidence ..................................................... 39
2.5.2 Phƣơng pháp tối thiểu Entropy ................................................... 39
CHƢƠNG 3: Áp dụng cài đặt thử nghiệm............................................. 41
3.1 Cài đặt ................................................................................................. 41 Phạm Anh Toàn – CT1501 2
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
3.1.1 Nền tảng và ngôn ngữ lập trình................................................... 41
3.1.2 Các thƣ viện sử dụng................................................................... 41
3.1.3 Cơ sở dữ liệu ............................................................................... 41
3.2 Giao diện và các chức năng chính của chƣơng trình .......................... 42
3.2.1 Giao diện chính ........................................................................... 42
3.2.2 Các chức năng chính của chƣơng trình.......................................42
3.3 Một số kết quả thực nghiệm................................................................ 44
3.3.1 Kết quả thực nghiệm số 1............................................................ 44
3.3.2 Kết quả thực nghiệm số 2............................................................ 46
KẾT LUẬN .................................................................................................... 52 TÀI LIỆU THAM KHẢO ............................................................................ 53
Phạm Anh Toàn – CT1501 3
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
STT
1 2 3 4 5 6 7
Từ viết tắt
CBIR EM PCA RF RGB SVM
MỘT SỐ TỪ VIẾT TẮT Mô tả
Content-Based Image Retrieval
Expectation Maximization
Principal Component Analysis
Relevance Feedback
Red-Green-Blue
Support Vector Machine
TSVM
Transductive Support Vector Machine
Phạm Anh Toàn – CT1501
4
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
MỞ ĐẦU
Với sự phát triển của Internet cũng nhƣ các thiết bị ghi và lƣu trữ ảnh, kích thƣớc của các tập ảnh số đƣợc gia tăng một cách nhanh chóng. Hiệu quả của các công cụ tìm kiếm, tra cứu ảnh đƣợc yêu cầu từ rất nhiều lĩnh vực khác nhau bao gồm : trinh sát, thời trang, phòng chống tội phạm, xuất bản, kiến trúc, y tế v.v... Cùng chung mục đích này, rất nhiều các hệ thống tra cứu ảnh đã đƣợc phát triển. Có hai nền tảng là : dựa trên văn bản (text-based) và dựa trên nội dung (content-based).
Các phƣơng pháp tiếp cận dựa trên văn bản đƣợc sử dụng từ những năm 1970. Trong đó các ảnh đƣợc chú thích bởi các mô tả văn bản một cách thủ công, sau đó đƣợc sử dụng bởi các hệ thống quản lý cơ sở dữ liệu để thực hiện việc tra cứu ảnh. Có hai nhƣợc điểm cho quá trình tra cứu ảnh dựa trên văn bản. Đầu tiên là yêu cầu về mức lao động đáng kể của con ngƣời cho việc chú thích thủ công. Thứ hai là vấn đề chú thích không chính xác do nhận thức chủ quan của con ngƣời. Để khắc phục hai nhƣợc điểm trên của hệ thống tra cứu ảnh dựa trên văn bản, khái niệm tra cứu ảnh dựa trên nội dung đƣợc giới thiệu vào đầu những năm 1980.
Đồ án trình bày kỹ thuật tra cứu ảnh dựa trên nội dung sử dụng phản hồi có liên quan với mô hình học dựa trên đồ thị, Đồ án bao gồm có 3 phần :
Chƣơng 1 : Tổng quan về hệ thống tra cứu ảnh dựa trên nội dung với phản hồi liên quan.
Chƣơng 2 : Mô hình học bán giám sát dựa trên đồ thị.
Chƣơng 3 : Áp dụng cài đặt chƣơng trình và một số kết quả thực nghiệm.
Phạm Anh Toàn – CT1501 5
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
CHƢƠNG 1:
1.1 Khái niệm tra cứu ảnh dựa trên nội dung
Một hệ thống CBIR đƣợc dùng để tìm kiếm các ảnh số trong một cơ sở dữ liệu lớn và tra cứu những ảnh liên quan dựa trên nội dung thực tế của nó. Nội dung có thể ở dạng các đặc trƣng mức thấp hay bất kỳ thông tin nào có đƣợc từ hình ảnh. Trong CBIR, hình ảnh đƣợc trích chọn các đặc trƣng mức thấp một cách tự động để biểu diễn nội dung trực quan, sau đó hệ thống sử dụng các véc-tơ đặc trƣng để đánh giá độ tƣơng tự giữa các ảnh.
1.2 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 [5]. 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.
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 dung
Tổng quan về tra cứu ảnh
dựa trên nội dung với phản hồi liên quan
Phạm Anh Toàn – CT1501 6
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.2.1
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 hay 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 véc-tơ hay 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.
Lập chỉ mục cho các véc-tơ để nâng hiệu quả tra cứu. Trả lại kết quả tra cứu cho ngƣời dùng.
Các đặc trƣng hình ảnh mức thấp
Các đặc trƣng của ảnh bao gồm các đặc tính cơ bản và các đặc tính ngữ nghĩa/logic. Các đặc tính cơ bản đó là: màu sắc (color), hình dạng (shape), kết cấu (texture), vị trí không gian (spatial location). Chúng có thể đƣợc trích xuất tự động hay bán tự động. Đặc tính 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, các đặc tính logic đƣợc trích chọn bằng tay hay bán tự động. Một hay nhiều đặc trƣng có thể đƣợc sử dụng trong ứng công cụ thể.
1.2.1.1 Đặc trƣng màu sắc
Đặc trƣng màu sắc là một trong những đặc trƣng đƣợc sử dụng phổ biến trong tra cứu ảnh. Màu sắc đƣợc định nghĩa trên một không gian màu. Có rất nhiều không gian màu đã đƣợc xây dựng sẵn, chúng thƣờng đƣợc dùng cho các ứng dụng khác nhau. Những không gian màu gần gũi hơn với nhận thức của con ngƣời và đƣợc sử dụng rộng rãi trong CBIR bao gồm RGB, LAB, LUV, HSV, HSL ... Vào năm 1999, Gevers và cộng sự đã quan tâm đến các đối tƣợng lấy từ các điểm quan sát khác nhau và sự chiếu sáng. Theo kết quả, một tập các điểm bất biến đặc trƣng màu đã đƣợc tính toán. Các bất biến màu đƣợc xây dựng trên cơ sở hue, cặp hue-hue, và ba đặc trƣng màu đƣợc tính
Phạm Anh Toàn – CT1501 7
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
toán từ các mô hình đối xứng. Các đặc trƣng màu sắc mặc dù mô tả màu sắc rất hiệu quả nhƣng không trực tiếp liên quan đến các ngữ nghĩa mức cao.
1.2.1.2 Đặc trƣng kết cấu
Kết cấu không đƣợc định nghĩa đầy đủ nhƣ là đặc trƣng màu sắc, vì thế mà một số hệ thống không sử dụng đặc trƣng kết cấu. Tuy nhiên, kết cấu cung cấp các thông tin quan trọng trong việc phân loại ảnh, vì nó mô tả nội dung của nhiều ảnh thực nhƣ là: vỏ trái cây, mây, cây, gạch ... Do đó, kết cấu là một đặc trƣng quan trọng trong việc định nghĩa ngữ nghĩa mức cao cho mục đích tra cứu ảnh [5]. Các đặc trƣng kết cấu thƣờng đƣợc sử dụng trong hệ thống tra cứu ảnh bao gồm các đặc trƣng phổ, chẳng hạn nhƣ các đặc trƣng đƣợc bao gồm sử dụng lọc Gabor hay biến đổi wavelet, thống kê đặc trƣng kết cấu trong các cách đo độ thống kê cục bộ, nhƣ sáu đặc trƣng kết cấu Tamura, và đặc trƣng wold đƣợc đề xuất bởi Liu và các cộng sự vào năm 1996.
1.2.1.3 Đặc trƣng hình dạng
Hình dạng là một khái niệm đƣợc định nghĩa khá tốt. Đặc trƣng hình dạng của các ứng dụng nói chung bao gồm: tỷ lệ aspect, tuần hoàn, mô tả Fourier, bất biến thời điểm, phân đoạn đƣờng bao liên tiếp [8], v.v.. Đặc trƣng hình dạng là đặc trƣng ảnh quan trọng, mặc dù chúng chƣa đƣợc sử dụng rộng rãi trong CBIR nhƣ là đặc trƣng màu và đặc trƣng kết cấu [5]. Đặc trƣng hình dạng đã thể hiện tính hữu ích trong nhiều miền ảnh đặc biệt nhƣ là các đối tƣợng nhân tạo. Ảnh màu đƣợc sử dụng phổ biến trong nhiều tài liệu, tuy nhiên lại khó khăn để áp dụng đặc trƣng hình dạng so với màu sắc và kết cấu do sự thiếu chính xác của phân đoạn. Mặc dù gặp khó khăn, đặc trƣng hình dạng vẫn đƣợc sử dụng trong một số hệ thống và cho thấy tiềm năng trong RBIR (Region-based image retrieval).
Phạm Anh Toàn – CT1501 8
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.2.1.4 Đặc trƣng vị trí không gian
Các vùng hay đối tƣợng với thuộc tính màu sắc và kết cấu tƣơng tự có thể đƣợc nhận ra một cách dễ dàng bởi ràng buộc không gian [5]. Ví dụ “bầu trời” và “biển” có thể có cùng đặc trƣng về màu sắc và kết cấu nhƣng lại có vị trí không gian trong ảnh khác nhau. Bầu trời thƣờng xuất hiện ở phía trên của ảnh trong khi biển thƣờng nằm ở dƣới cùng. Đặc trƣng không gian thƣờng đƣợc định nghĩa một cách đơn giản nhƣ là “trên, dƣới” tùy theo vị trí các vùng trong ảnh.
Mối quan hệ không gian tƣơng đối là quan trọng hơn vị trí không gian tuyệt đối. 2D-string và một số biến thể của nó là cấu trúc chung phổ biến để biểu diễn mối quan hệ về phƣơng hƣớng giữa các đối tƣợng nhƣ là “trái/phải”, “trên/dƣới”.
1.2.2 Đánhchỉsố
Một vấn đề quan trọng khác trong tra cứu ảnh dựa trên nội dung là đánh chỉ số và tìm kiếm nhanh ảnh dựa trên đặc trƣng trực quan. Bởi vì, các véc-tơ đặc trƣng của ảnh có xu hƣớng có số chiều cao và do đó nó không thích hợp cho các cấu trúc đánh chỉ số truyền thống. Việc giảm số chiều thƣờng xuyên đƣợc sử dụng trƣớc khi lên kế hoạch đánh chỉ số.
Một trong những công nghệ đƣợc sử dụng phổ biến cho việc giảm số chiều là phân tích thành phần chính PCA [5]. 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 véc-tơ đặc trƣng hình dạng có 20 chiều thành hai hay ba chiều. Ngoài công nghệ 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. Mặc dù, biến đổi KL có một số thuộc tính hữu dụng nhƣ khả năng xác định vị trí hầu hết không gian con quan trọng, các thuộc tính đặc trƣng mà quan trọng
Phạm Anh Toàn – CT1501 9
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
đối với việc xác định mô hình tƣơng tự có thể bị phá huỷ trong suốt quá trình giảm các chiều mù. Ngoài hai công nghệ 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.
Sau khi đã giảm số chiều thì dữ liệu đa chiều đƣợc đánh chỉ số. Có nhiều phƣơng pháp tiếp cận bao gồm : R-tree, linear quad-trees, K-d-B tree, grid files ... Hầu hết các phƣơng pháp này cho hiệu quả hợp lý với không gian có số chiều nhỏ.
1.2.3 Tƣơng tác ngƣời dùng
Đối với tra cứu ảnh dựa trên nội dung, ngƣời dùng tƣơng tác với các hệ thống tra cứu là rất quan trọng khi các hình thức và thay đổi linh hoạt của truy vấn chỉ có thể thu đƣợc bằng cách liên hệ với ngƣời sử dụng trong các thủ tục tra cứu. Giao diện ngƣời dùng trong các hệ thống tra cứu hình ảnh thông thƣờng bao gồm phần xây dựng truy vấn và phần trình bày kết quả.
1.2.3.1 Xác định truy vấn
Để xác định những loại hình ảnh ngƣời sử dụng muốn lấy từ cơ sở dữ liệu thì có thể thực hiện bằng nhiều cách. Và những cách thông thƣờng nhất đƣợc sử dụng là: duyệt qua, 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 là phƣơng pháp duyệt qua toàn bộ cơ sở dữ liệu theo danh mục các ảnh. Với mục đích này, ảnh trong cơ sở dữ liệu đƣợc phân loại thành nhiều mục khác nhau theo ngữ nghĩa hay 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 cơ sở dữ liệu [5].
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 hay 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ừ cơ sở dữ liệu.
Phạm Anh Toàn – CT1501 10
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Truy vấn bằng cách phác thảo cho phép ngƣời sử dụng vẽ một bức phác họa một hình ảnh với một công cụ chỉnh sửa đồ họa cung cấp bởi hệ thống tra cứu hay bằng một số phần mềm khác. Truy vấn có thể đƣợc hình thành bằng cách vẽ một số đối tƣợng có tính chất nhất định nhƣ màu sắc, kết cấu, hình dạng, kích thƣớc và vị trí. Trong hầu hết các trƣờng hợp, một bản phác thảo thô là đủ, các truy vấn có thể đƣợc chọn lọc dựa trên kết quả tra cứu.
Truy vấn bằng ví dụ cho phép ngƣời sử dụng xây dựng một truy vấn bằng cách cung cấp một hình ảnh ví dụ. Hệ thống chuyển đổi hình ảnh ví dụ thành một thay mặt các đặc trƣng nội bộ. Sau đó những hình ảnh đƣợc lƣu trữ trong cơ sở dữ liệu với các đặc trƣng tƣơng tự đƣợc tìm kiếm. Truy vấn bằng ví dụ có thể đƣợc phân chia thành truy vấn bằng ví dụ bên ngoài, nếu hình ảnh truy vấn không có trong cơ sở dữ liệu, và truy vấn bằng ví dụ bên trong, nếu ngƣợc lại. Đối với truy vấn bằng hình ảnh bên trong, tất cả các mối quan hệ giữa các hình ảnh có thể đƣợc tính toán trƣớc. Ƣu điểm chính của truy vấn bằng ví dụ là ngƣời dùng không cần cung cấp một mô tả rõ ràng về mục tiêu, nó đƣợc tính toán bởi hệ thống. Nó phù hợp cho các ứng dụng mà mục tiêu là một hình ảnh của cùng một đối tƣợng, hay thiết lập các đối tƣợng theo các điều kiện xem khác nhau. Hầu hết các hệ thống hiện tại cung cấp các truy vấn hình thức này.
Truy vấn bằng một nhóm ví dụ cho phép ngƣời dùng lựa chọn nhiều hình ảnh. Sau đó hệ thống sẽ tìm những hình ảnh phù hợp nhất với đặc điểm chung của nhóm các ví dụ. Bằng cách này, một mục tiêu có thể đƣợc xác định chính xác hơn bằng cách xác định các biến thể đặc trƣng liên quan và loại bỏ các biến thể không thích hợp trong các truy vấn. Ngoài ra, các thuộc tính của nhóm có thể đƣợc chọn lọc bằng cách thêm những mẫu dƣơng. Nhiều hệ thống phát triển gần đây cung cấp truy vấn bằng cả mẫu dƣơng và mẫu âm.
Phạm Anh Toàn – CT1501 11
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.2.3.2 Phản hồi liên quan
Khái niệm phản hồi liên quan đã đƣợc giới thiệu trong tra cứu ảnh dựa trên nội dung từ khái niệm tra cứu thông tin dựa trên văn bản vào năm 1998 và sau đó đã trở thành một kỹ thuật phổ biến cho CBIR để giảm khoảng cách ngữ nghĩa. Nói chung, phản hồi liên quan nhằm mục đích cải thiện hiệu năng tra cứu với sự tham gia điều chỉnh của ngƣời dùng trên kết quả tra cứu.
1.3 Khoảng cách ngữ nghĩa
Trở ngại lớn trong tra cứu ảnh trên nội dung đó là khoảng cách ngữ nghĩa. Con ngƣời có xu hƣớng sử dụng các khái niệm mức cao ví dụ nhƣ từ khóa, mô tả bằng văn bản để diễn tả các hình ảnh và đo sự tƣơng tự giữa chúng. Trong khi đó việc trích chọn đặc trƣng một cách tự động sử dụng các kỹ thuật thị giác máy hầu hết là các đặc trƣng mức thấp (màu sắc, kết cấu, hình dạng, bố cục không gian...). Nói chung không có một mối liên hệ trực tiếp nào giữa các khái niệm mức cao và đặc trƣng mức thấp.
Mặc dù đã có rất nhiều thuật toán phức tạp đƣợc thiết kế để mô tả các đặc trƣng về màu sắc, hình dạng, kết cấu, tuy nhiên những thuật toán này vẫn không thể mô tả đầy đủ ngữ nghĩa của hình ảnh và có nhiều hạn chế khi làm việc với một cơ sở dữ liệu lớn [2]. Thí nghiệm rộng rãi trên hệ thống CBIR cho thấy các nội dung mức thấp thƣờng không mô tả đƣợc các khái niệm ngữ nghĩa mức cao trong suy nghĩ của ngƣời sử dụng [3]. Do đó, hiệu suất của CBIR vẫn còn xa sự mong đợi của ngƣời dùng.
Trong [1] Eakins đã đề cập tới ba cấp độ truy vấn trong CBIR :
Cấp độ 1 : Tra cứu bằng các đặc trƣng nguyên thủy nhƣ màu sắc, kết cấu, hình dạng hay vị trí không gian của các yếu tố hình ảnh. Điển hình là các truy vấn bằng ví dụ, „tìm ảnh giống nhƣ thế này‟
Phạm Anh Toàn – CT1501 12
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Cấp độ 2 : Tra cứu các đối tƣợng có dạng xác định bởi các đặc trƣng gốc và một mức độ suy luận logic. Ví dụ „tìm ảnh một bông hoa‟.
Cấp độ 3 : Tra cứu bằng các thuộc tính trừu tƣợng liên quan tới một lƣợng đáng kể ý nghĩa mức cao về mục đích của đối tƣợng hay miêu tả cảnh vật. Điều này bao gồm tra cứu các sự kiện đƣợc đặt tên, các hình ảnh có ý nghĩa về cảm xúc và tinh thần... Ví dụ „tìm hình ảnh một đám đông vui vẻ‟.
Cấp độ 2 và 3 đều ứng với việc tra cứu ngữ nghĩa của hình ảnh. Khoảng giữa cấp độ 1 và cấp độ 2 cũng giống khoảng cách ngữ nghĩa. Cụ thể hơn, sự khác biệt giữa giới hạn khả năng mô tả của đặc trƣng hình ảnh mức thấp và sự phong phú về ngữ nghĩa của ngƣời dùng đƣợc gọi là “khoảng cách ngữ nghĩa”.
Để nâng cao hiệu xuất trong CBIR đòi hỏi cần có các phƣơng pháp giảm khoảng cách này. Một trong các phƣơng pháp đó là phản hồi liên quan.
1.4 Kỹ thuật phản hồi liên quan trong CBIR 1.4.1 Khái niệm phản hồi liên quan
Nhận thức của con ngƣời về độ tƣơng tự của hình ảnh là chủ quan, ngữ nghĩa, và phụ thuộc vào từng nhiệm vụ cụ thể. Mặc dù phƣơng pháp dựa trên nội dung hứa hẹn một hƣớng đi triển vọng cho tra cứu ảnh, nói chung các kết quả tra cứu dựa trên những điểm tƣơng đồng của các đặc trƣng trực quan thuần túy là không nhất thiết có ý nghĩa về nhận thức và ngữ nghĩa. Ngoài ra, mỗi loại đặc trƣng trực quan có xu hƣớng chỉ nắm bắt một khía cạnh của thuộc tính hình ảnh và nó thƣờng khó khăn cho ngƣời sử dụng để xác định rõ những khía cạnh khác nhau đƣợc kết hợp. Để 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. Ý
Phạm Anh Toàn – CT1501 13
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
tƣởng chính là sử dụng các mẫu dƣơ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) hay 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 để tinh chỉnh các truy vấn và/hay điều chỉnh các biện pháp tƣơng tự.
1.4.2 Kiến trúc tổng quan của hệ thống CBIR với phản hồi liên quan Hình 3-1 cho thấy mô hình tổng quát của một hệ thống tra cứu ảnh từ cơ
sở dữ liệu sử dụng phản hồi liên quan
Hình 1-2 : Mô hình tổng quát hệ thống tra cứu ảnh sử dụng 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.
Phạm Anh Toàn – CT1501 14
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
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, và 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” 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 dù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 2-1 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.
1.4.2.1 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, và do đó hệ thống sẽ trở nên nhanh hơn và hiệu quả trong CBIR. Khi đặc trƣng đƣợc trích chọn, chúng sẽ đƣợc lƣu trữ trong cơ sở dữ 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à vấn đề 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ể đƣợc 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 và hình dạng.
Phạm Anh Toàn – CT1501 15
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Đặ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, v.v... Ƣ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 trƣng đƣợc 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ể đƣợc tính toán trên các kết quả của phân đoạn ảnh 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 nguyên bản, đƣờng tròn, đƣờng nét, texel (các phần tử tập trung ở một khu vực kết cấu), hay các đặc trƣng cục bộ khác, hình dạng của đƣờng nét, v.v...
Phạm Anh Toàn – CT1501 16
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.4.2.2 Đo độ tƣơng tự
Trong độ đo tƣơng tự, véc-tơ đặc trƣng của ảnh truy vấn và véc-tơ đặ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. Vào năm 2003, Manesh và các cộng sự đã đề xuất phƣơng pháp đo độ tƣơng tự cho việc đối sánh chi tiết các độ đo khác nhau nhƣ: Manhattan, weighted mean-variance, Euclidean, Chebychev, Mahanobis, v.v... cho tra cứu kết cấu ảnh với đánh giá thực nghiệm. Họ nhận thấy rằng số liệu khoảng cách Canberra and Bray-Curtis thực hiện tốt hơn các số liệu khoảng cách khác.
1.4.2.3 Phản hồi từ ngƣời dùng
Sau khi có kết quả tra cứu, ngƣời dùng cung cấp phản hồi về các kết quả liên quan hay không liên quan. Nếu kết quả chƣa đƣợc chấp nhận thì vòng lặp phản hồi sẽ đƣợc lặp lại nhiều lần cho đến khi ngƣời dùng hài lòng.
1.4.3 Các phƣơng pháp tiếp cận phản hồi liên quan
Trong phƣơng pháp tiếp cận dựa trên thông tin phản hồi liên quan, một hệ thống CBIR học từ thông tin phản hồi đƣợc cung cấp bởi ngƣời sử dụng. Học trong hệ thống CBIR đƣợc phân loại thành học ngắn hạn và học dài hạn. Chọn lọc truy vấn sử dụng thông tin phản hồi liên quan đã đạt đƣợc nhiều sự chú ý trong nghiên cứu và phát triển của các hệ thống CBIR. Hầu hết các nghiên cứu đã tập trung vào điều chỉnh truy vấn trong mỗi phiên tra cứu. Điều này thƣờng đƣợc gọi là học trong nội bộ truy vấn hay học ngắn hạn. Ngƣợc lại, liên truy vấn, còn đƣợc gọi là học dài hạn là chiến lƣợc cố gắng để phân tích mối quan hệ giữa các phiên tra cứu hiện tại và quá khứ.
1.4.3.1 Phƣơng pháp học ngắn hạn
Trong học ngắn hạn, chỉ những phản hồi của phiên tìm kiếm hiện tại
đƣợc sử dụng cho thuật toán học, và các đặc trƣng ảnh là nguồn dữ liệu chính.
Phạm Anh Toàn – CT1501 17
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Thách thức chính trong phƣơng pháp này là tìm sự kết hợp tốt nhất các đặc trƣng biểu diễn truy vấn của ngƣời dùng. Ví dụ một bộ các đặc trƣng tối ƣu sẽ bao gồm những đặc trƣng mà có thể bắt lấy sự tƣơng tự giữa các mẫu dƣơng hay những đặc trƣng mà có thể phân biệt các mẫu dƣơng và mẫu âm. Do đó nhiều thuật toán học máy cổ điển đƣợc sử dụng trong học ngắn hạn nhƣ là SVMs, mô hình học Bayes, boosting và đánh trọng số đặc trƣng, phân tích sự khác biệt v.v.. Tuy nhiên, cách tiếp cận học ngắn hạn là nhiệm vụ rất khó bởi vì trƣớc hết kích thƣớc của dữ liệu huấn luyện là nhỏ hơn nhiều so với độ dài không gian đặc trƣng, thứ hai là có quá nhiều sự mất cân bằng giữa phản hồi của những ngƣời dùng khác nhau. Và cuối cùng quá trình học là trực tuyến sẽ đòi hỏi nhiều thời gian thực hơn.
1.4.3.2 Phƣơng pháp học dài hạn
Phƣơng pháp học dài hạn có thể đạt đƣợc độ chính xác tra cứu tốt hơn so với các kỹ thuật RF truyền thống. Có thể sử dụng học tập dài hạn để vƣợt qua những khó khăn nhƣ không có khả năng nắm những ngữ nghĩa hiếm hoi và mất cân bằng giữa các ví dụ phản hồi, và thiếu cơ chế bộ nhớ v.v.. Trên thực tế, khái niệm học dài hạn trong CBIR đƣợc thông qua từ công việc của lọc cộng tác. Phƣơng pháp học dài hạn sử dụng các thông tin phản hồi thu thập đƣợc từ trƣớc. Nó là một quá trình tích lũy cho việc thu thập thông tin phản hồi nhanh chóng và đƣợc lƣu trữ trong các hình thức của ma trận. Một ma trận lƣu trữ các nhãn đƣợc cung cấp bởi ngƣời dùng cho mỗi hình ảnh trong mỗi lần lặp. Thông thƣờng kích thƣớc của ma trận lịch sử tìm kiếm là lớn, mô hình thống kê và các phƣơng pháp nhƣ phân tích thành phần chính và phân tích ngữ nghĩa tiềm ẩn rất phổ biến trong các phƣơng pháp học tập dài hạn. Tuy nhiên, có những vấn đề trong phƣơng pháp học tập dài hạn.
Những hạn chế của phƣơng pháp học dài hạn :
Trƣớc hết đây là phƣơng pháp thể hiện sự không phù hợp với những ứng dụng mà hình ảnh thƣờng xuyên đƣợc thêm vào hay gỡ bỏ. Một
Phạm Anh Toàn – CT1501 18
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.4.4
cách tiếp cận tốt hơn là sử dụng mô hình véc-tơ đặc trƣng và phân tích mối quan hệ liên truy vấn.
Thứ hai, là sự thƣa thớt của thông tin phản hồi đƣợc ghi lại. Chất lƣợng học dài hạn phụ thuộc rất nhiều vào số lƣợng ngƣời dùng đăng nhập mà hệ thống lƣu trữ. Do thiếu các tƣơng tác và cơ sở dữ liệu lớn, nó không phải là dễ dàng để thu thập thông tin đăng nhập một cách đầy đủ.
Cuối cùng, vấn đề khác là hầu hết các giải pháp học dài hạn chỉ giới thiệu các kiến thức ngữ nghĩa đƣợc ghi nhớ cho ngƣời sử dụng nhƣng thiếu khả năng học tập để đoán ngữ nghĩa ẩn trong các mẫu ngữ nghĩa thu đƣợc.
Những thách thức trong phản hồi liên quan
Kỹ thuật phản hồi liên quan đã đạt đƣợc nhiều tiến bộ vƣợt bậc từ khi nó đƣợc giới thiệu vào năm 2007 bởi Liu và các cộng sự. Các phƣơng pháp mới luôn đƣợc đƣa ra để khắc phục những nhƣợc điểm tồn tại trong nó. Tuy nhiên, với những nhƣợc điểm nguyên thủy của kỹ thuật phản hồi liên quan trong CBIR thì đến nay vẫn còn phải đƣợc các nhà khoa học nghiên cứu thêm. Các hạn chế trong phản hồi liên quan của hệ thống CBIR nhƣ sau:
Không thể trích chọn ngữ nghĩa mức cao: Hầu hết các kỹ thuật RF trong CBIR sẽ rất khó để trích chọn ngữ nghĩa mức cao của ảnh khi chỉ có đặc trƣng mức thấp đƣợc sử dụng trong RF. Tuy nhiên, cách này vẫn hoạt động tốt trong việc tra cứu thông tin văn bản. Bởi vì, việc tra cứu vẫn đƣợc dựa trên từ khoá chứ không phải trên các đặc trƣng mức thấp.
Sự khan hiếm và mất cân bằng các mẫu phản hồi: Mỗi ngƣời dùng đều không muốn thao tác nhiều hơn số lần lặp phản hồi để có đƣợc kết quả tốt nhất. Vì vậy, số lƣợng mẫu phản hồi gắn nhãn có đƣợc từ ngƣời dùng trong một phiên RF là khá nhỏ so với chiều không gian đặc trƣng.
Phạm Anh Toàn – CT1501 19
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Do đó, đối với dữ liệu huấn luyện nhỏ thì hầu hết các thuật toán máy học không thể cho ra kết quả chính xác. Hơn nữa, số lƣợng mẫu có nhãn tiêu cực thƣờng lớn hơn số lƣợng mẫu có nhãn tích cực. Các dữ liệu huấn luyện mất cân đối luôn luôn làm cho việc học phân lớp ít đáng tin cậy hơn. Vì thế, đối với các mẫu dữ liệu huấn luyện nhỏ mà đặc biệt là các mẫu tích cực thì hiển nhiên sẽ làm giảm độ chính xác của RF.
Xử lý thời gian thực: Quá trình học trong RF là trực tuyến và do đó mọi vòng lặp phản hồi bao gồm cả huấn luyện và kiểm tra đều phải thực hiện. Vì thế mà hệ thống sẽ tốn rất nhiều thời gian để xử lý. Có một cách hợp lý để giải quyết vấn đề này là sử dụng phƣơng pháp biểu diễn ảnh và cấu trúc lƣu trữ nhƣ là một cấu trúc cây phân cấp, v.v...
1.5 Các lĩnh vực ứng dụng của tra cứu ảnh dựa trên nội dung
Ứng dụng của tra cứu ảnh dựa trên nội dung có rất nhiều trong đời sống xã hội, phục vụ cho nhiều mục đích khác nhau, nhằm xác nhận, tra cứu thông tin. Nhờ đó mà giảm bớt công việc của con ngƣời, nâng cao hiệu suất làm việc, ví dụ nhƣ: Album ảnh số của ngƣời dùng, ảnh y khoa, bảo tàng ảnh, tìm kiếm nhãn hiệu, mô tả nội dung video, truy tìm ảnh tội phạm, hệ thống tự nhận biết điều khiển luồng giao thông... Một vài hệ thống lớn thay mặt cho các lĩnh vực bao gồm :
Hệ thống truy vấn ảnh theo nội dung (Query By Image Content) đƣợc nghiên cứu và phát triển bởi nhóm nghiên cứu Visual Media Management thuộc công ty IBM, đây là một hệ thống tra cứu ảnh thƣơng mại đƣợc phát triển từ rất sớm. Hiện nay, hệ thống này hỗ trợ một vài đo độ tƣơng tự cho ảnh nhƣ: trung bình màu sắc, lƣợc đồ màu sắc và kết cấu. Công nghệ sử dụng trong hệ thống bao gồm 2 phần chính là: đánh chỉ số và tìm kiếm. Hơn nữa, hệ thống này còn cung cấp vài cách tiếp cận truy vấn theo đơn đặc trƣng, đa đặc trƣng và đa giai đoạn.
Phạm Anh Toàn – CT1501 20
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Hệ thống Visual SEEK tại trƣờng đại học Columbia. Hệ thống cho phép ngƣời dùng nhập vào truy vấn, sử dụng các đặc trƣng mức thấp của hình ảnh nhƣ: màu sắc, bố cục không gian và kết cấu. Các đặc trƣng đó đƣợc mô tả theo màu sắc và biến đổi Wavelet dựa trên đặc trƣng kết cấu.
Hệ thống NeTra sử dụng các đặc trƣng của ảnh: Màu sắc, hình dạng, kết cấu, vị trí không gian.
Ngoài ra, còn một số hệ thống khác nhƣ: Virage system, Stanford SIMPLICity system, NEC PicHunter system, v.v...
Phạm Anh Toàn – CT1501 21
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
CHƢƠNG 2: Mô hình học bán giám sát dựa trên đồ thị
Một trở ngại lớn trong CBIR đó là khoảng cách ngữ nghĩa giữa các đặc trƣng mức thấp và các khái niệm bậc cao. Để giảm khoảng cách này, phản hồi liên quan đã đƣợc giới thiệu cho CBIR . Hiện nay, rất nhiều nghiên cứu bắt đầu xem xét phản hồi liên quan là một vấn đề phân loại hay học tập. Ngƣời dùng đƣa vào các mẫu dƣơng hay mẫu âm, hệ thống sẽ học tập từ những ví dụ đó để phân chia tất cả dữ liệu thành hai nhóm liên quan hay không liên quan. Vì vậy đã có rất nhiều đề án học máy cổ điển có thể áp dụng cho phản hồi liên quan.
2.1 Khái niệm học máy
Học máy là một lĩnh vực nhỏ trong ngành khoa học máy tính, đƣợc phát triển từ những nghiên cứu về nhận dạng mẫu và lý thuyết học tập tính toán (computational learning theory) trong trí tuệ nhân tạo.
Học máy tìm hiểu và xây dựng các thuật toán để có thể học tập và đƣa ra quyết định trên tập dữ liệu (học từ dữ liệu). Các thuật toán này hoạt động bằng cách xây dựng một mô hình từ ví dụ đầu vào để đƣa ra các đoán và quyết định, chứ không phải là làm theo chỉ dẫn của một chƣơng trình cố định.
Học máy có liên quan chặt chẽ và thƣờng trùng với thống kê tính toán số liệu; một lĩnh vực chuyên về dự đoán. Nó có mối quan hệ mạnh mẽ với tối ƣu hóa, trong đó cung cấp các phƣơng pháp, lý thuyết và ứng dụng của lĩnh vực này. Học máy đƣợc sử dụng trong một loạt các nhiệm vụ tính toán thiết kế và lập trình mà rõ ràng các thuật toán dựa trên nguyên tắc là không khả thi. Ví dụ bao gồm các ứng dụng lọc thƣ rác, nhận dạng ký tự quang học (OCR), công cụ tìm kiếm và thị giác máy tính. Học máy đôi khi đƣợc lồng việc khai thác dữ liệu, mặc dù đó là lĩnh vực tập trung nhiều hơn vào phân tích dữ liệu. Học máy và nhận dạng mẫu "có thể đƣợc xem nhƣ là hai mặt của cùng một lĩnh vực."
Phạm Anh Toàn – CT1501 22
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Nhiệm vụ học máy thƣờng đƣợc chia làm 3 loại chính :
Học không giám sát : Hệ thống học quan sát một tập các mục chƣa gán nhãn, mục đích là để tổ chức các mục này. Nhiệm vụ học bao gồm phân chia các nhóm mục vào các cụm, xác định một outliner để quyết định nếu một mục mới là khác biệt đáng kể so với các mục trƣớc, giảm số chiều ánh xạ vào một không gian ít chiều mà vẫn giữ đƣợc các thuộc tính nhất định của tập dữ liệu.
Học có giám sát : Hệ thống học quan sát một tập huấn luyện đƣợc gán nhãn bao gồm các cặp (đặc trƣng, nhãn), đƣợc ký hiệu . Mục tiêu là đoán nhãn y cho bất kỳ đầu vào mới có đặc trƣng x. Một công việc học có giám sát đƣợc gọi là hồi quy
nếu y Є R, và là phân loại khi y lấy giá trị trên một tập rời rạc.
Học tăng cƣờng : Hệ thống học liên tục quan sát trong môi trƣờng x, thể hiện một hành động a và nhận lại một phần thƣởng r, mục tiêu là chọn các hành động để làm tối đa phần thƣởng trong tƣơng lai.
Một cách phân loại theo nhiệm vụ của học máy phát sinh khi xem xét kết quả đầu ra mong muốn của một hệ thống học máy :
Trong phân loại, đầu vào đƣợc chia thành hai hay nhiều nhóm, “ngƣời học” phải tạo ra một mô hình để gán dữ liệu đầu vào chƣa biết vào một hay nhiều nhóm đó. Điều này thƣờng giải quyết bằng việc có giám sát. Lọc thƣ rác là một ví dụ phân loại, trong đó đầu vào là các thông điệp email và đầu ra là “spam” hay “không spam”.
Trong hồi quy cũng là một vấn đề có giám sát, kết quả đầu ra thƣờng là liên tục hơn là rời rạc.
Phạm Anh Toàn – CT1501 23
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Trong phân cụm, một tập hợp đầu vào đƣợc chia nhóm. Khác với phân loại, các nhóm này là chƣa đƣợc biết trƣớc. Đây thƣờng là nhiệm vụ của học không giám sát.
Ƣớc tính mật độ tìm phân phối của đầu vào trên một không gian.
Giảm thiểu số chiều, đơn giản hóa dữ liệu đầu vào bằng cách ánh xạ chúng đến một không gian ít chiều hơn. Mô hình hóa chủ đề là một vấn đề liên quan, khi chƣơng trình đƣợc đƣa một danh sách các tài liệu bằng ngôn ngữ con ngƣời và nhiệm vụ là tìm ra các tài liệu có cùng một chủ đề.
2.2 Học bán giám sát
Trong tài liệu này học máy tập chung vào nhiệm vụ phân loại, theo truyền thống là một nhiệm vụ của học có giám sát. Để huấn luyện một bộ phân loại cần một tập huấn luyện đƣợc gán nhãn. Tuy nhiên việc gán nhãn thƣờng là khó, đắt và chậm để thu thập, bởi vì nó có thể đòi hỏi một bộ chú thích có kinh nghiệm của con ngƣời. Ví dụ :
Giám sát bằng hình ảnh : Việc gán nhãn ngƣời một cách thủ công trong một lƣợng lớn các hình ảnh từ camera giám sát là rất tốn thời gian.
Nhận dạng giọng nói : Việc viết lại chính xác một giọng nói ở mức âm tiết là hết sức tốn thời gian (400xRT) và yêu cầu chuyên gia trong ngôn ngữ học.
Phân loại văn bản : Lọc thƣ rác, phân loại tin nhắn, gợi ý các bài viết trên Internet, rất nhiều công việc cần ngƣời dùng gán nhãn cho văn bản ví dụ nhƣ “thích” hay “không thích”. Phải đọc và gán nhãn hàng ngàn tài liệu sẽ làm nản chí ngƣời dùng.
Phân tích cú pháp : Để huấn luyện một bộ phân tích cú pháp tốt cần những cặp mẫu câu và cây phân tích cú pháp, việc này đòi hỏi rất nhiều
Phạm Anh Toàn – CT1501 24
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
thời gian để xây dựng bởi những nhà ngôn ngữ học. Các chuyên gia phải mất vài năm để xây dựng các cây phân tích cú pháp cho vài nghìn mẫu câu.
Mặt khác, các dữ liệu không có nhãn thƣờng xuyên có sẵn với số lƣợng lớn và rất dễ thu thập. Các camera quan sát có thể chạy 24 giờ/ngày, các giọng đọc có thể đƣợc ghi âm, các văn bản có thể lấy đƣợc trên Internet, các mẫu câu thì có ở khắp nơi ... Với cách phân loại truyền thống gặp vấn đề là không thể sử dụng các dữ liệu chƣa có nhãn để huấn luyện bộ phân loại.
Câu hỏi đƣợc đặt ra là : Cho một tập tƣơng đối nhỏ dữ liệu đƣợc gán nhãn và một lƣợng lớn dữ liệu chƣa gán nhãn , có cách nào để sử dụng cả hai cho việc phân loại? Khái niệm “học bán giám sát” đƣợc ra đời từ thực tế là các dữ liệu đƣợc sử dụng là giữa học có giám sát và học không giám sát. Học bán giám sát sử dụng cả dữ liệu đã gán nhãn và dữ liệu chƣa gán nhãn cho mục đích học tập. Học bán giám sát hứa hẹn độ chính xác cao và lỗ lực chú thích thấp nhất.
Chúng ta có cả một chuỗi các ý tƣởng thú vị về cách học tập trên cả hai dữ liệu gán nhãn và không gán nhãn. Đây là một lĩnh vực đƣợc phát triển một cách nhanh chóng, trong phần này xin trình bày một cách sơ lƣợc về lịch sử của học bán giám sát.
Thời gian đầu, việc học bán giám sát giả định rằng có 2 lớp, mỗi lớp có một phân bố Gauss. Giả định dữ liệu đầy đủ lấy đƣợc từ một mô hình hỗn hợp. Với một lƣợng lớn các dữ liệu chƣa gán nhãn. các thành phần của mô hình hỗn hợp có thể đƣợc xác định với thuật toán Expectation Maximization. Chỉ cần một ví dụ có nhãn cho mỗi thành phần để xác định đầy đủ mô hình hỗn hợp. Mô hình này đã áp dụng thành công cho việc phân loại văn bản.
KẾT LUẬN
Sau một thời gian tìm hiểu và nghiên cứu đề tài này, em đã đạt đƣợc một số kết quả sau:
Tìm hiểu đƣợc cấu trúc của một hệ thống tra cứu ảnh dựa trên nội dung.
Tìm hiểu đƣợc một số phƣơng pháp làm giảm khoảng cách ngữ nghĩa trong tra cứu ảnh dựa trên nội dung.
Tìm hiểu phƣơng pháp phản hồi liên quan trong tra cứu ảnh.
Tìm hiểu về một số phƣơng pháp học máy đặc biệt là học bán giám sát dựa trên mô hình đồ thị.
Xây dựng đƣợc chƣơng trình thử nghiệm áp dụng phƣơng pháp phản hồi liên quan sử dụng học bán giám sát trên đồ thị cho tra cứu ảnh dựa trên nội dung.
Tuy nhiên đồ án vẫn còn tồn tại một số vấn đề :
Phần chƣơng trình cài đặt tính toán còn chậm do cài đặt trong môi trƣờng MS Visual Studio, khả năng của phần cứng có hạn chế.
Phần cài đặt học siêu tham số chƣa cho hiệu quả. Do độ phức tạp tính toán về thời gian của việc tính toán gradient là .
Để nâng cao độ chính xác trong tra cứu ảnh cần tiếp tục nghiên cứu về mô hình học bán giám sát.
Em rất mong nhận đƣợc sự đóng góp ý kiến từ các Thầy Cô và các bạn để em có thêm kiến thức và kinh nghiệm tiếp tục hoàn thiện nội dung nghiên cứu trong đề tài. Em xin chân thành cảm ơn!
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
1. Nội dung vμ c ̧c yau cầu cần giải quyết trong nhiệm vụ đề tμi tốt nghiệp a. Nội dung:
- Tổng quan về Tra cứu ảnh dựa trên nội dung với phản hồi liên quan
- Tổng quan về mô hình học trên đồ thị.
- Ứng dụng học trên đồ thị cho bài toán tra cứu ảnh.
- Cài đặt chƣơng trình thử nghiệm.
b. C Yêu cầu cần giải quyết
- Hiểu quy trình của một hệ thống tra cứu ảnh dựa trên nội dung, các phƣơng pháp cơ bản trong tra cứu ảnh dựa trên nội dung.
- Hiểu đƣợc một số mô hình học dựa trên đồ thị và áp dụng cho cải thiện hiệu quả tra cứu.
- Cài đặt chƣơng trình thử nghiệm
MỤC LỤC
MỘT SỐ TỪ VIẾT TẮT ................................................................................ 4
MỞ ĐẦU .......................................................................................................... 5
CHƢƠNG 1: Tổng quan về tra cứu ảnh dựa trên nội dung với phản hồi liên quan ........................................................................................... 6
1.1 Khái niệm tra cứu ảnh dựa trên nội dung ............................................. 6
1.2 Những thành phần của một hệ thống tra cứu ảnh dựa trên nội dung.... 6
1.2.1 Các đặc trƣng hình ảnh mức thấp ................................................. 7
1.2.2 Đánh chỉ số.................................................................................... 9
1.2.3 Tƣơng tác ngƣời dùng ................................................................. 10
1.3 Khoảng cách ngữ nghĩa ...................................................................... 12
1.4 Kỹ thuật phản hồi liên quan trong CBIR ............................................ 13
1.4.1 Khái niệm phản hồi liên quan ..................................................... 13
1.4.2 Kiến trúc tổng quan của hệ thống CBIR với phản hồi liên quan 14
1.4.3 Các phƣơng pháp tiếp cận phản hồi liên quan ............................ 17
1.4.4 Những thách thức trong phản hồi liên quan................................ 19
1.5 Các lĩnh vực ứng dụng của tra cứu ảnh dựa trên nội dung ................. 20 CHƢƠNG 2: Mô hình học bán giám sát dựa trên đồ thị ..................... 22
2.1 Khái niệm học máy ............................................................................. 22
2.2 Học bán giám sát................................................................................. 24
2.3 Học bán giám sát dựa trên đồ thị ........................................................ 27
2.3.1 Thuật toán lan truyền nhãn.......................................................... 27
2.3.2 Xây dựng đồ thị........................................................................... 30
2.3.3 Trƣờng ngẫu nhiên Gauss và hàm điều hòa................................ 30
2.4 Kết hợp học bán giám sát với học chủ động (Active Learning)......... 35
2.5 Học siêu tham số của đồ thị (Graph Hyperparameter Learning)........ 39
2.5.1 Phƣơng pháp tối đa Evidence ..................................................... 39
2.5.2 Phƣơng pháp tối thiểu Entropy ................................................... 39
CHƢƠNG 3: Áp dụng cài đặt thử nghiệm............................................. 41
3.1 Cài đặt ................................................................................................. 41 Phạm Anh Toàn – CT1501 2
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
3.1.1 Nền tảng và ngôn ngữ lập trình................................................... 41
3.1.2 Các thƣ viện sử dụng................................................................... 41
3.1.3 Cơ sở dữ liệu ............................................................................... 41
3.2 Giao diện và các chức năng chính của chƣơng trình .......................... 42
3.2.1 Giao diện chính ........................................................................... 42
3.2.2 Các chức năng chính của chƣơng trình.......................................42
3.3 Một số kết quả thực nghiệm................................................................ 44
3.3.1 Kết quả thực nghiệm số 1............................................................ 44
3.3.2 Kết quả thực nghiệm số 2............................................................ 46
KẾT LUẬN .................................................................................................... 52 TÀI LIỆU THAM KHẢO ............................................................................ 53
Phạm Anh Toàn – CT1501 3
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
STT
1 2 3 4 5 6 7
Từ viết tắt
CBIR EM PCA RF RGB SVM
MỘT SỐ TỪ VIẾT TẮT Mô tả
Content-Based Image Retrieval
Expectation Maximization
Principal Component Analysis
Relevance Feedback
Red-Green-Blue
Support Vector Machine
TSVM
Transductive Support Vector Machine
Phạm Anh Toàn – CT1501
4
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
MỞ ĐẦU
Với sự phát triển của Internet cũng nhƣ các thiết bị ghi và lƣu trữ ảnh, kích thƣớc của các tập ảnh số đƣợc gia tăng một cách nhanh chóng. Hiệu quả của các công cụ tìm kiếm, tra cứu ảnh đƣợc yêu cầu từ rất nhiều lĩnh vực khác nhau bao gồm : trinh sát, thời trang, phòng chống tội phạm, xuất bản, kiến trúc, y tế v.v... Cùng chung mục đích này, rất nhiều các hệ thống tra cứu ảnh đã đƣợc phát triển. Có hai nền tảng là : dựa trên văn bản (text-based) và dựa trên nội dung (content-based).
Các phƣơng pháp tiếp cận dựa trên văn bản đƣợc sử dụng từ những năm 1970. Trong đó các ảnh đƣợc chú thích bởi các mô tả văn bản một cách thủ công, sau đó đƣợc sử dụng bởi các hệ thống quản lý cơ sở dữ liệu để thực hiện việc tra cứu ảnh. Có hai nhƣợc điểm cho quá trình tra cứu ảnh dựa trên văn bản. Đầu tiên là yêu cầu về mức lao động đáng kể của con ngƣời cho việc chú thích thủ công. Thứ hai là vấn đề chú thích không chính xác do nhận thức chủ quan của con ngƣời. Để khắc phục hai nhƣợc điểm trên của hệ thống tra cứu ảnh dựa trên văn bản, khái niệm tra cứu ảnh dựa trên nội dung đƣợc giới thiệu vào đầu những năm 1980.
Đồ án trình bày kỹ thuật tra cứu ảnh dựa trên nội dung sử dụng phản hồi có liên quan với mô hình học dựa trên đồ thị, Đồ án bao gồm có 3 phần :
Chƣơng 1 : Tổng quan về hệ thống tra cứu ảnh dựa trên nội dung với phản hồi liên quan.
Chƣơng 2 : Mô hình học bán giám sát dựa trên đồ thị.
Chƣơng 3 : Áp dụng cài đặt chƣơng trình và một số kết quả thực nghiệm.
Phạm Anh Toàn – CT1501 5
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
CHƢƠNG 1:
1.1 Khái niệm tra cứu ảnh dựa trên nội dung
Một hệ thống CBIR đƣợc dùng để tìm kiếm các ảnh số trong một cơ sở dữ liệu lớn và tra cứu những ảnh liên quan dựa trên nội dung thực tế của nó. Nội dung có thể ở dạng các đặc trƣng mức thấp hay bất kỳ thông tin nào có đƣợc từ hình ảnh. Trong CBIR, hình ảnh đƣợc trích chọn các đặc trƣng mức thấp một cách tự động để biểu diễn nội dung trực quan, sau đó hệ thống sử dụng các véc-tơ đặc trƣng để đánh giá độ tƣơng tự giữa các ảnh.
1.2 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 [5]. 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.
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 dung
Tổng quan về tra cứu ảnh
dựa trên nội dung với phản hồi liên quan
Phạm Anh Toàn – CT1501 6
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.2.1
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 hay 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 véc-tơ hay 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.
Lập chỉ mục cho các véc-tơ để nâng hiệu quả tra cứu. Trả lại kết quả tra cứu cho ngƣời dùng.
Các đặc trƣng hình ảnh mức thấp
Các đặc trƣng của ảnh bao gồm các đặc tính cơ bản và các đặc tính ngữ nghĩa/logic. Các đặc tính cơ bản đó là: màu sắc (color), hình dạng (shape), kết cấu (texture), vị trí không gian (spatial location). Chúng có thể đƣợc trích xuất tự động hay bán tự động. Đặc tính 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, các đặc tính logic đƣợc trích chọn bằng tay hay bán tự động. Một hay nhiều đặc trƣng có thể đƣợc sử dụng trong ứng công cụ thể.
1.2.1.1 Đặc trƣng màu sắc
Đặc trƣng màu sắc là một trong những đặc trƣng đƣợc sử dụng phổ biến trong tra cứu ảnh. Màu sắc đƣợc định nghĩa trên một không gian màu. Có rất nhiều không gian màu đã đƣợc xây dựng sẵn, chúng thƣờng đƣợc dùng cho các ứng dụng khác nhau. Những không gian màu gần gũi hơn với nhận thức của con ngƣời và đƣợc sử dụng rộng rãi trong CBIR bao gồm RGB, LAB, LUV, HSV, HSL ... Vào năm 1999, Gevers và cộng sự đã quan tâm đến các đối tƣợng lấy từ các điểm quan sát khác nhau và sự chiếu sáng. Theo kết quả, một tập các điểm bất biến đặc trƣng màu đã đƣợc tính toán. Các bất biến màu đƣợc xây dựng trên cơ sở hue, cặp hue-hue, và ba đặc trƣng màu đƣợc tính
Phạm Anh Toàn – CT1501 7
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
toán từ các mô hình đối xứng. Các đặc trƣng màu sắc mặc dù mô tả màu sắc rất hiệu quả nhƣng không trực tiếp liên quan đến các ngữ nghĩa mức cao.
1.2.1.2 Đặc trƣng kết cấu
Kết cấu không đƣợc định nghĩa đầy đủ nhƣ là đặc trƣng màu sắc, vì thế mà một số hệ thống không sử dụng đặc trƣng kết cấu. Tuy nhiên, kết cấu cung cấp các thông tin quan trọng trong việc phân loại ảnh, vì nó mô tả nội dung của nhiều ảnh thực nhƣ là: vỏ trái cây, mây, cây, gạch ... Do đó, kết cấu là một đặc trƣng quan trọng trong việc định nghĩa ngữ nghĩa mức cao cho mục đích tra cứu ảnh [5]. Các đặc trƣng kết cấu thƣờng đƣợc sử dụng trong hệ thống tra cứu ảnh bao gồm các đặc trƣng phổ, chẳng hạn nhƣ các đặc trƣng đƣợc bao gồm sử dụng lọc Gabor hay biến đổi wavelet, thống kê đặc trƣng kết cấu trong các cách đo độ thống kê cục bộ, nhƣ sáu đặc trƣng kết cấu Tamura, và đặc trƣng wold đƣợc đề xuất bởi Liu và các cộng sự vào năm 1996.
1.2.1.3 Đặc trƣng hình dạng
Hình dạng là một khái niệm đƣợc định nghĩa khá tốt. Đặc trƣng hình dạng của các ứng dụng nói chung bao gồm: tỷ lệ aspect, tuần hoàn, mô tả Fourier, bất biến thời điểm, phân đoạn đƣờng bao liên tiếp [8], v.v.. Đặc trƣng hình dạng là đặc trƣng ảnh quan trọng, mặc dù chúng chƣa đƣợc sử dụng rộng rãi trong CBIR nhƣ là đặc trƣng màu và đặc trƣng kết cấu [5]. Đặc trƣng hình dạng đã thể hiện tính hữu ích trong nhiều miền ảnh đặc biệt nhƣ là các đối tƣợng nhân tạo. Ảnh màu đƣợc sử dụng phổ biến trong nhiều tài liệu, tuy nhiên lại khó khăn để áp dụng đặc trƣng hình dạng so với màu sắc và kết cấu do sự thiếu chính xác của phân đoạn. Mặc dù gặp khó khăn, đặc trƣng hình dạng vẫn đƣợc sử dụng trong một số hệ thống và cho thấy tiềm năng trong RBIR (Region-based image retrieval).
Phạm Anh Toàn – CT1501 8
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.2.1.4 Đặc trƣng vị trí không gian
Các vùng hay đối tƣợng với thuộc tính màu sắc và kết cấu tƣơng tự có thể đƣợc nhận ra một cách dễ dàng bởi ràng buộc không gian [5]. Ví dụ “bầu trời” và “biển” có thể có cùng đặc trƣng về màu sắc và kết cấu nhƣng lại có vị trí không gian trong ảnh khác nhau. Bầu trời thƣờng xuất hiện ở phía trên của ảnh trong khi biển thƣờng nằm ở dƣới cùng. Đặc trƣng không gian thƣờng đƣợc định nghĩa một cách đơn giản nhƣ là “trên, dƣới” tùy theo vị trí các vùng trong ảnh.
Mối quan hệ không gian tƣơng đối là quan trọng hơn vị trí không gian tuyệt đối. 2D-string và một số biến thể của nó là cấu trúc chung phổ biến để biểu diễn mối quan hệ về phƣơng hƣớng giữa các đối tƣợng nhƣ là “trái/phải”, “trên/dƣới”.
1.2.2 Đánhchỉsố
Một vấn đề quan trọng khác trong tra cứu ảnh dựa trên nội dung là đánh chỉ số và tìm kiếm nhanh ảnh dựa trên đặc trƣng trực quan. Bởi vì, các véc-tơ đặc trƣng của ảnh có xu hƣớng có số chiều cao và do đó nó không thích hợp cho các cấu trúc đánh chỉ số truyền thống. Việc giảm số chiều thƣờng xuyên đƣợc sử dụng trƣớc khi lên kế hoạch đánh chỉ số.
Một trong những công nghệ đƣợc sử dụng phổ biến cho việc giảm số chiều là phân tích thành phần chính PCA [5]. 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 véc-tơ đặc trƣng hình dạng có 20 chiều thành hai hay ba chiều. Ngoài công nghệ 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. Mặc dù, biến đổi KL có một số thuộc tính hữu dụng nhƣ khả năng xác định vị trí hầu hết không gian con quan trọng, các thuộc tính đặc trƣng mà quan trọng
Phạm Anh Toàn – CT1501 9
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
đối với việc xác định mô hình tƣơng tự có thể bị phá huỷ trong suốt quá trình giảm các chiều mù. Ngoài hai công nghệ 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.
Sau khi đã giảm số chiều thì dữ liệu đa chiều đƣợc đánh chỉ số. Có nhiều phƣơng pháp tiếp cận bao gồm : R-tree, linear quad-trees, K-d-B tree, grid files ... Hầu hết các phƣơng pháp này cho hiệu quả hợp lý với không gian có số chiều nhỏ.
1.2.3 Tƣơng tác ngƣời dùng
Đối với tra cứu ảnh dựa trên nội dung, ngƣời dùng tƣơng tác với các hệ thống tra cứu là rất quan trọng khi các hình thức và thay đổi linh hoạt của truy vấn chỉ có thể thu đƣợc bằng cách liên hệ với ngƣời sử dụng trong các thủ tục tra cứu. Giao diện ngƣời dùng trong các hệ thống tra cứu hình ảnh thông thƣờng bao gồm phần xây dựng truy vấn và phần trình bày kết quả.
1.2.3.1 Xác định truy vấn
Để xác định những loại hình ảnh ngƣời sử dụng muốn lấy từ cơ sở dữ liệu thì có thể thực hiện bằng nhiều cách. Và những cách thông thƣờng nhất đƣợc sử dụng là: duyệt qua, 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 là phƣơng pháp duyệt qua toàn bộ cơ sở dữ liệu theo danh mục các ảnh. Với mục đích này, ảnh trong cơ sở dữ liệu đƣợc phân loại thành nhiều mục khác nhau theo ngữ nghĩa hay 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 cơ sở dữ liệu [5].
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 hay 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ừ cơ sở dữ liệu.
Phạm Anh Toàn – CT1501 10
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Truy vấn bằng cách phác thảo cho phép ngƣời sử dụng vẽ một bức phác họa một hình ảnh với một công cụ chỉnh sửa đồ họa cung cấp bởi hệ thống tra cứu hay bằng một số phần mềm khác. Truy vấn có thể đƣợc hình thành bằng cách vẽ một số đối tƣợng có tính chất nhất định nhƣ màu sắc, kết cấu, hình dạng, kích thƣớc và vị trí. Trong hầu hết các trƣờng hợp, một bản phác thảo thô là đủ, các truy vấn có thể đƣợc chọn lọc dựa trên kết quả tra cứu.
Truy vấn bằng ví dụ cho phép ngƣời sử dụng xây dựng một truy vấn bằng cách cung cấp một hình ảnh ví dụ. Hệ thống chuyển đổi hình ảnh ví dụ thành một thay mặt các đặc trƣng nội bộ. Sau đó những hình ảnh đƣợc lƣu trữ trong cơ sở dữ liệu với các đặc trƣng tƣơng tự đƣợc tìm kiếm. Truy vấn bằng ví dụ có thể đƣợc phân chia thành truy vấn bằng ví dụ bên ngoài, nếu hình ảnh truy vấn không có trong cơ sở dữ liệu, và truy vấn bằng ví dụ bên trong, nếu ngƣợc lại. Đối với truy vấn bằng hình ảnh bên trong, tất cả các mối quan hệ giữa các hình ảnh có thể đƣợc tính toán trƣớc. Ƣu điểm chính của truy vấn bằng ví dụ là ngƣời dùng không cần cung cấp một mô tả rõ ràng về mục tiêu, nó đƣợc tính toán bởi hệ thống. Nó phù hợp cho các ứng dụng mà mục tiêu là một hình ảnh của cùng một đối tƣợng, hay thiết lập các đối tƣợng theo các điều kiện xem khác nhau. Hầu hết các hệ thống hiện tại cung cấp các truy vấn hình thức này.
Truy vấn bằng một nhóm ví dụ cho phép ngƣời dùng lựa chọn nhiều hình ảnh. Sau đó hệ thống sẽ tìm những hình ảnh phù hợp nhất với đặc điểm chung của nhóm các ví dụ. Bằng cách này, một mục tiêu có thể đƣợc xác định chính xác hơn bằng cách xác định các biến thể đặc trƣng liên quan và loại bỏ các biến thể không thích hợp trong các truy vấn. Ngoài ra, các thuộc tính của nhóm có thể đƣợc chọn lọc bằng cách thêm những mẫu dƣơng. Nhiều hệ thống phát triển gần đây cung cấp truy vấn bằng cả mẫu dƣơng và mẫu âm.
Phạm Anh Toàn – CT1501 11
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.2.3.2 Phản hồi liên quan
Khái niệm phản hồi liên quan đã đƣợc giới thiệu trong tra cứu ảnh dựa trên nội dung từ khái niệm tra cứu thông tin dựa trên văn bản vào năm 1998 và sau đó đã trở thành một kỹ thuật phổ biến cho CBIR để giảm khoảng cách ngữ nghĩa. Nói chung, phản hồi liên quan nhằm mục đích cải thiện hiệu năng tra cứu với sự tham gia điều chỉnh của ngƣời dùng trên kết quả tra cứu.
1.3 Khoảng cách ngữ nghĩa
Trở ngại lớn trong tra cứu ảnh trên nội dung đó là khoảng cách ngữ nghĩa. Con ngƣời có xu hƣớng sử dụng các khái niệm mức cao ví dụ nhƣ từ khóa, mô tả bằng văn bản để diễn tả các hình ảnh và đo sự tƣơng tự giữa chúng. Trong khi đó việc trích chọn đặc trƣng một cách tự động sử dụng các kỹ thuật thị giác máy hầu hết là các đặc trƣng mức thấp (màu sắc, kết cấu, hình dạng, bố cục không gian...). Nói chung không có một mối liên hệ trực tiếp nào giữa các khái niệm mức cao và đặc trƣng mức thấp.
Mặc dù đã có rất nhiều thuật toán phức tạp đƣợc thiết kế để mô tả các đặc trƣng về màu sắc, hình dạng, kết cấu, tuy nhiên những thuật toán này vẫn không thể mô tả đầy đủ ngữ nghĩa của hình ảnh và có nhiều hạn chế khi làm việc với một cơ sở dữ liệu lớn [2]. Thí nghiệm rộng rãi trên hệ thống CBIR cho thấy các nội dung mức thấp thƣờng không mô tả đƣợc các khái niệm ngữ nghĩa mức cao trong suy nghĩ của ngƣời sử dụng [3]. Do đó, hiệu suất của CBIR vẫn còn xa sự mong đợi của ngƣời dùng.
Trong [1] Eakins đã đề cập tới ba cấp độ truy vấn trong CBIR :
Cấp độ 1 : Tra cứu bằng các đặc trƣng nguyên thủy nhƣ màu sắc, kết cấu, hình dạng hay vị trí không gian của các yếu tố hình ảnh. Điển hình là các truy vấn bằng ví dụ, „tìm ảnh giống nhƣ thế này‟
Phạm Anh Toàn – CT1501 12
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Cấp độ 2 : Tra cứu các đối tƣợng có dạng xác định bởi các đặc trƣng gốc và một mức độ suy luận logic. Ví dụ „tìm ảnh một bông hoa‟.
Cấp độ 3 : Tra cứu bằng các thuộc tính trừu tƣợng liên quan tới một lƣợng đáng kể ý nghĩa mức cao về mục đích của đối tƣợng hay miêu tả cảnh vật. Điều này bao gồm tra cứu các sự kiện đƣợc đặt tên, các hình ảnh có ý nghĩa về cảm xúc và tinh thần... Ví dụ „tìm hình ảnh một đám đông vui vẻ‟.
Cấp độ 2 và 3 đều ứng với việc tra cứu ngữ nghĩa của hình ảnh. Khoảng giữa cấp độ 1 và cấp độ 2 cũng giống khoảng cách ngữ nghĩa. Cụ thể hơn, sự khác biệt giữa giới hạn khả năng mô tả của đặc trƣng hình ảnh mức thấp và sự phong phú về ngữ nghĩa của ngƣời dùng đƣợc gọi là “khoảng cách ngữ nghĩa”.
Để nâng cao hiệu xuất trong CBIR đòi hỏi cần có các phƣơng pháp giảm khoảng cách này. Một trong các phƣơng pháp đó là phản hồi liên quan.
1.4 Kỹ thuật phản hồi liên quan trong CBIR 1.4.1 Khái niệm phản hồi liên quan
Nhận thức của con ngƣời về độ tƣơng tự của hình ảnh là chủ quan, ngữ nghĩa, và phụ thuộc vào từng nhiệm vụ cụ thể. Mặc dù phƣơng pháp dựa trên nội dung hứa hẹn một hƣớng đi triển vọng cho tra cứu ảnh, nói chung các kết quả tra cứu dựa trên những điểm tƣơng đồng của các đặc trƣng trực quan thuần túy là không nhất thiết có ý nghĩa về nhận thức và ngữ nghĩa. Ngoài ra, mỗi loại đặc trƣng trực quan có xu hƣớng chỉ nắm bắt một khía cạnh của thuộc tính hình ảnh và nó thƣờng khó khăn cho ngƣời sử dụng để xác định rõ những khía cạnh khác nhau đƣợc kết hợp. Để 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. Ý
Phạm Anh Toàn – CT1501 13
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
tƣởng chính là sử dụng các mẫu dƣơ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) hay 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 để tinh chỉnh các truy vấn và/hay điều chỉnh các biện pháp tƣơng tự.
1.4.2 Kiến trúc tổng quan của hệ thống CBIR với phản hồi liên quan Hình 3-1 cho thấy mô hình tổng quát của một hệ thống tra cứu ảnh từ cơ
sở dữ liệu sử dụng phản hồi liên quan
Hình 1-2 : Mô hình tổng quát hệ thống tra cứu ảnh sử dụng 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.
Phạm Anh Toàn – CT1501 14
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
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, và 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” 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 dù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 2-1 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.
1.4.2.1 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, và do đó hệ thống sẽ trở nên nhanh hơn và hiệu quả trong CBIR. Khi đặc trƣng đƣợc trích chọn, chúng sẽ đƣợc lƣu trữ trong cơ sở dữ 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à vấn đề 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ể đƣợc 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 và hình dạng.
Phạm Anh Toàn – CT1501 15
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Đặ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, v.v... Ƣ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 trƣng đƣợc 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ể đƣợc tính toán trên các kết quả của phân đoạn ảnh 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 nguyên bản, đƣờng tròn, đƣờng nét, texel (các phần tử tập trung ở một khu vực kết cấu), hay các đặc trƣng cục bộ khác, hình dạng của đƣờng nét, v.v...
Phạm Anh Toàn – CT1501 16
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.4.2.2 Đo độ tƣơng tự
Trong độ đo tƣơng tự, véc-tơ đặc trƣng của ảnh truy vấn và véc-tơ đặ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. Vào năm 2003, Manesh và các cộng sự đã đề xuất phƣơng pháp đo độ tƣơng tự cho việc đối sánh chi tiết các độ đo khác nhau nhƣ: Manhattan, weighted mean-variance, Euclidean, Chebychev, Mahanobis, v.v... cho tra cứu kết cấu ảnh với đánh giá thực nghiệm. Họ nhận thấy rằng số liệu khoảng cách Canberra and Bray-Curtis thực hiện tốt hơn các số liệu khoảng cách khác.
1.4.2.3 Phản hồi từ ngƣời dùng
Sau khi có kết quả tra cứu, ngƣời dùng cung cấp phản hồi về các kết quả liên quan hay không liên quan. Nếu kết quả chƣa đƣợc chấp nhận thì vòng lặp phản hồi sẽ đƣợc lặp lại nhiều lần cho đến khi ngƣời dùng hài lòng.
1.4.3 Các phƣơng pháp tiếp cận phản hồi liên quan
Trong phƣơng pháp tiếp cận dựa trên thông tin phản hồi liên quan, một hệ thống CBIR học từ thông tin phản hồi đƣợc cung cấp bởi ngƣời sử dụng. Học trong hệ thống CBIR đƣợc phân loại thành học ngắn hạn và học dài hạn. Chọn lọc truy vấn sử dụng thông tin phản hồi liên quan đã đạt đƣợc nhiều sự chú ý trong nghiên cứu và phát triển của các hệ thống CBIR. Hầu hết các nghiên cứu đã tập trung vào điều chỉnh truy vấn trong mỗi phiên tra cứu. Điều này thƣờng đƣợc gọi là học trong nội bộ truy vấn hay học ngắn hạn. Ngƣợc lại, liên truy vấn, còn đƣợc gọi là học dài hạn là chiến lƣợc cố gắng để phân tích mối quan hệ giữa các phiên tra cứu hiện tại và quá khứ.
1.4.3.1 Phƣơng pháp học ngắn hạn
Trong học ngắn hạn, chỉ những phản hồi của phiên tìm kiếm hiện tại
đƣợc sử dụng cho thuật toán học, và các đặc trƣng ảnh là nguồn dữ liệu chính.
Phạm Anh Toàn – CT1501 17
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Thách thức chính trong phƣơng pháp này là tìm sự kết hợp tốt nhất các đặc trƣng biểu diễn truy vấn của ngƣời dùng. Ví dụ một bộ các đặc trƣng tối ƣu sẽ bao gồm những đặc trƣng mà có thể bắt lấy sự tƣơng tự giữa các mẫu dƣơng hay những đặc trƣng mà có thể phân biệt các mẫu dƣơng và mẫu âm. Do đó nhiều thuật toán học máy cổ điển đƣợc sử dụng trong học ngắn hạn nhƣ là SVMs, mô hình học Bayes, boosting và đánh trọng số đặc trƣng, phân tích sự khác biệt v.v.. Tuy nhiên, cách tiếp cận học ngắn hạn là nhiệm vụ rất khó bởi vì trƣớc hết kích thƣớc của dữ liệu huấn luyện là nhỏ hơn nhiều so với độ dài không gian đặc trƣng, thứ hai là có quá nhiều sự mất cân bằng giữa phản hồi của những ngƣời dùng khác nhau. Và cuối cùng quá trình học là trực tuyến sẽ đòi hỏi nhiều thời gian thực hơn.
1.4.3.2 Phƣơng pháp học dài hạn
Phƣơng pháp học dài hạn có thể đạt đƣợc độ chính xác tra cứu tốt hơn so với các kỹ thuật RF truyền thống. Có thể sử dụng học tập dài hạn để vƣợt qua những khó khăn nhƣ không có khả năng nắm những ngữ nghĩa hiếm hoi và mất cân bằng giữa các ví dụ phản hồi, và thiếu cơ chế bộ nhớ v.v.. Trên thực tế, khái niệm học dài hạn trong CBIR đƣợc thông qua từ công việc của lọc cộng tác. Phƣơng pháp học dài hạn sử dụng các thông tin phản hồi thu thập đƣợc từ trƣớc. Nó là một quá trình tích lũy cho việc thu thập thông tin phản hồi nhanh chóng và đƣợc lƣu trữ trong các hình thức của ma trận. Một ma trận lƣu trữ các nhãn đƣợc cung cấp bởi ngƣời dùng cho mỗi hình ảnh trong mỗi lần lặp. Thông thƣờng kích thƣớc của ma trận lịch sử tìm kiếm là lớn, mô hình thống kê và các phƣơng pháp nhƣ phân tích thành phần chính và phân tích ngữ nghĩa tiềm ẩn rất phổ biến trong các phƣơng pháp học tập dài hạn. Tuy nhiên, có những vấn đề trong phƣơng pháp học tập dài hạn.
Những hạn chế của phƣơng pháp học dài hạn :
Trƣớc hết đây là phƣơng pháp thể hiện sự không phù hợp với những ứng dụng mà hình ảnh thƣờng xuyên đƣợc thêm vào hay gỡ bỏ. Một
Phạm Anh Toàn – CT1501 18
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
1.4.4
cách tiếp cận tốt hơn là sử dụng mô hình véc-tơ đặc trƣng và phân tích mối quan hệ liên truy vấn.
Thứ hai, là sự thƣa thớt của thông tin phản hồi đƣợc ghi lại. Chất lƣợng học dài hạn phụ thuộc rất nhiều vào số lƣợng ngƣời dùng đăng nhập mà hệ thống lƣu trữ. Do thiếu các tƣơng tác và cơ sở dữ liệu lớn, nó không phải là dễ dàng để thu thập thông tin đăng nhập một cách đầy đủ.
Cuối cùng, vấn đề khác là hầu hết các giải pháp học dài hạn chỉ giới thiệu các kiến thức ngữ nghĩa đƣợc ghi nhớ cho ngƣời sử dụng nhƣng thiếu khả năng học tập để đoán ngữ nghĩa ẩn trong các mẫu ngữ nghĩa thu đƣợc.
Những thách thức trong phản hồi liên quan
Kỹ thuật phản hồi liên quan đã đạt đƣợc nhiều tiến bộ vƣợt bậc từ khi nó đƣợc giới thiệu vào năm 2007 bởi Liu và các cộng sự. Các phƣơng pháp mới luôn đƣợc đƣa ra để khắc phục những nhƣợc điểm tồn tại trong nó. Tuy nhiên, với những nhƣợc điểm nguyên thủy của kỹ thuật phản hồi liên quan trong CBIR thì đến nay vẫn còn phải đƣợc các nhà khoa học nghiên cứu thêm. Các hạn chế trong phản hồi liên quan của hệ thống CBIR nhƣ sau:
Không thể trích chọn ngữ nghĩa mức cao: Hầu hết các kỹ thuật RF trong CBIR sẽ rất khó để trích chọn ngữ nghĩa mức cao của ảnh khi chỉ có đặc trƣng mức thấp đƣợc sử dụng trong RF. Tuy nhiên, cách này vẫn hoạt động tốt trong việc tra cứu thông tin văn bản. Bởi vì, việc tra cứu vẫn đƣợc dựa trên từ khoá chứ không phải trên các đặc trƣng mức thấp.
Sự khan hiếm và mất cân bằng các mẫu phản hồi: Mỗi ngƣời dùng đều không muốn thao tác nhiều hơn số lần lặp phản hồi để có đƣợc kết quả tốt nhất. Vì vậy, số lƣợng mẫu phản hồi gắn nhãn có đƣợc từ ngƣời dùng trong một phiên RF là khá nhỏ so với chiều không gian đặc trƣng.
Phạm Anh Toàn – CT1501 19
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Do đó, đối với dữ liệu huấn luyện nhỏ thì hầu hết các thuật toán máy học không thể cho ra kết quả chính xác. Hơn nữa, số lƣợng mẫu có nhãn tiêu cực thƣờng lớn hơn số lƣợng mẫu có nhãn tích cực. Các dữ liệu huấn luyện mất cân đối luôn luôn làm cho việc học phân lớp ít đáng tin cậy hơn. Vì thế, đối với các mẫu dữ liệu huấn luyện nhỏ mà đặc biệt là các mẫu tích cực thì hiển nhiên sẽ làm giảm độ chính xác của RF.
Xử lý thời gian thực: Quá trình học trong RF là trực tuyến và do đó mọi vòng lặp phản hồi bao gồm cả huấn luyện và kiểm tra đều phải thực hiện. Vì thế mà hệ thống sẽ tốn rất nhiều thời gian để xử lý. Có một cách hợp lý để giải quyết vấn đề này là sử dụng phƣơng pháp biểu diễn ảnh và cấu trúc lƣu trữ nhƣ là một cấu trúc cây phân cấp, v.v...
1.5 Các lĩnh vực ứng dụng của tra cứu ảnh dựa trên nội dung
Ứng dụng của tra cứu ảnh dựa trên nội dung có rất nhiều trong đời sống xã hội, phục vụ cho nhiều mục đích khác nhau, nhằm xác nhận, tra cứu thông tin. Nhờ đó mà giảm bớt công việc của con ngƣời, nâng cao hiệu suất làm việc, ví dụ nhƣ: Album ảnh số của ngƣời dùng, ảnh y khoa, bảo tàng ảnh, tìm kiếm nhãn hiệu, mô tả nội dung video, truy tìm ảnh tội phạm, hệ thống tự nhận biết điều khiển luồng giao thông... Một vài hệ thống lớn thay mặt cho các lĩnh vực bao gồm :
Hệ thống truy vấn ảnh theo nội dung (Query By Image Content) đƣợc nghiên cứu và phát triển bởi nhóm nghiên cứu Visual Media Management thuộc công ty IBM, đây là một hệ thống tra cứu ảnh thƣơng mại đƣợc phát triển từ rất sớm. Hiện nay, hệ thống này hỗ trợ một vài đo độ tƣơng tự cho ảnh nhƣ: trung bình màu sắc, lƣợc đồ màu sắc và kết cấu. Công nghệ sử dụng trong hệ thống bao gồm 2 phần chính là: đánh chỉ số và tìm kiếm. Hơn nữa, hệ thống này còn cung cấp vài cách tiếp cận truy vấn theo đơn đặc trƣng, đa đặc trƣng và đa giai đoạn.
Phạm Anh Toàn – CT1501 20
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Hệ thống Visual SEEK tại trƣờng đại học Columbia. Hệ thống cho phép ngƣời dùng nhập vào truy vấn, sử dụng các đặc trƣng mức thấp của hình ảnh nhƣ: màu sắc, bố cục không gian và kết cấu. Các đặc trƣng đó đƣợc mô tả theo màu sắc và biến đổi Wavelet dựa trên đặc trƣng kết cấu.
Hệ thống NeTra sử dụng các đặc trƣng của ảnh: Màu sắc, hình dạng, kết cấu, vị trí không gian.
Ngoài ra, còn một số hệ thống khác nhƣ: Virage system, Stanford SIMPLICity system, NEC PicHunter system, v.v...
Phạm Anh Toàn – CT1501 21
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
CHƢƠNG 2: Mô hình học bán giám sát dựa trên đồ thị
Một trở ngại lớn trong CBIR đó là khoảng cách ngữ nghĩa giữa các đặc trƣng mức thấp và các khái niệm bậc cao. Để giảm khoảng cách này, phản hồi liên quan đã đƣợc giới thiệu cho CBIR . Hiện nay, rất nhiều nghiên cứu bắt đầu xem xét phản hồi liên quan là một vấn đề phân loại hay học tập. Ngƣời dùng đƣa vào các mẫu dƣơng hay mẫu âm, hệ thống sẽ học tập từ những ví dụ đó để phân chia tất cả dữ liệu thành hai nhóm liên quan hay không liên quan. Vì vậy đã có rất nhiều đề án học máy cổ điển có thể áp dụng cho phản hồi liên quan.
2.1 Khái niệm học máy
Học máy là một lĩnh vực nhỏ trong ngành khoa học máy tính, đƣợc phát triển từ những nghiên cứu về nhận dạng mẫu và lý thuyết học tập tính toán (computational learning theory) trong trí tuệ nhân tạo.
Học máy tìm hiểu và xây dựng các thuật toán để có thể học tập và đƣa ra quyết định trên tập dữ liệu (học từ dữ liệu). Các thuật toán này hoạt động bằng cách xây dựng một mô hình từ ví dụ đầu vào để đƣa ra các đoán và quyết định, chứ không phải là làm theo chỉ dẫn của một chƣơng trình cố định.
Học máy có liên quan chặt chẽ và thƣờng trùng với thống kê tính toán số liệu; một lĩnh vực chuyên về dự đoán. Nó có mối quan hệ mạnh mẽ với tối ƣu hóa, trong đó cung cấp các phƣơng pháp, lý thuyết và ứng dụng của lĩnh vực này. Học máy đƣợc sử dụng trong một loạt các nhiệm vụ tính toán thiết kế và lập trình mà rõ ràng các thuật toán dựa trên nguyên tắc là không khả thi. Ví dụ bao gồm các ứng dụng lọc thƣ rác, nhận dạng ký tự quang học (OCR), công cụ tìm kiếm và thị giác máy tính. Học máy đôi khi đƣợc lồng việc khai thác dữ liệu, mặc dù đó là lĩnh vực tập trung nhiều hơn vào phân tích dữ liệu. Học máy và nhận dạng mẫu "có thể đƣợc xem nhƣ là hai mặt của cùng một lĩnh vực."
Phạm Anh Toàn – CT1501 22
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Nhiệm vụ học máy thƣờng đƣợc chia làm 3 loại chính :
Học không giám sát : Hệ thống học quan sát một tập các mục chƣa gán nhãn, mục đích là để tổ chức các mục này. Nhiệm vụ học bao gồm phân chia các nhóm mục vào các cụm, xác định một outliner để quyết định nếu một mục mới là khác biệt đáng kể so với các mục trƣớc, giảm số chiều ánh xạ vào một không gian ít chiều mà vẫn giữ đƣợc các thuộc tính nhất định của tập dữ liệu.
Học có giám sát : Hệ thống học quan sát một tập huấn luyện đƣợc gán nhãn bao gồm các cặp (đặc trƣng, nhãn), đƣợc ký hiệu . Mục tiêu là đoán nhãn y cho bất kỳ đầu vào mới có đặc trƣng x. Một công việc học có giám sát đƣợc gọi là hồi quy
nếu y Є R, và là phân loại khi y lấy giá trị trên một tập rời rạc.
Học tăng cƣờng : Hệ thống học liên tục quan sát trong môi trƣờng x, thể hiện một hành động a và nhận lại một phần thƣởng r, mục tiêu là chọn các hành động để làm tối đa phần thƣởng trong tƣơng lai.
Một cách phân loại theo nhiệm vụ của học máy phát sinh khi xem xét kết quả đầu ra mong muốn của một hệ thống học máy :
Trong phân loại, đầu vào đƣợc chia thành hai hay nhiều nhóm, “ngƣời học” phải tạo ra một mô hình để gán dữ liệu đầu vào chƣa biết vào một hay nhiều nhóm đó. Điều này thƣờng giải quyết bằng việc có giám sát. Lọc thƣ rác là một ví dụ phân loại, trong đó đầu vào là các thông điệp email và đầu ra là “spam” hay “không spam”.
Trong hồi quy cũng là một vấn đề có giám sát, kết quả đầu ra thƣờng là liên tục hơn là rời rạc.
Phạm Anh Toàn – CT1501 23
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Trong phân cụm, một tập hợp đầu vào đƣợc chia nhóm. Khác với phân loại, các nhóm này là chƣa đƣợc biết trƣớc. Đây thƣờng là nhiệm vụ của học không giám sát.
Ƣớc tính mật độ tìm phân phối của đầu vào trên một không gian.
Giảm thiểu số chiều, đơn giản hóa dữ liệu đầu vào bằng cách ánh xạ chúng đến một không gian ít chiều hơn. Mô hình hóa chủ đề là một vấn đề liên quan, khi chƣơng trình đƣợc đƣa một danh sách các tài liệu bằng ngôn ngữ con ngƣời và nhiệm vụ là tìm ra các tài liệu có cùng một chủ đề.
2.2 Học bán giám sát
Trong tài liệu này học máy tập chung vào nhiệm vụ phân loại, theo truyền thống là một nhiệm vụ của học có giám sát. Để huấn luyện một bộ phân loại cần một tập huấn luyện đƣợc gán nhãn. Tuy nhiên việc gán nhãn thƣờng là khó, đắt và chậm để thu thập, bởi vì nó có thể đòi hỏi một bộ chú thích có kinh nghiệm của con ngƣời. Ví dụ :
Giám sát bằng hình ảnh : Việc gán nhãn ngƣời một cách thủ công trong một lƣợng lớn các hình ảnh từ camera giám sát là rất tốn thời gian.
Nhận dạng giọng nói : Việc viết lại chính xác một giọng nói ở mức âm tiết là hết sức tốn thời gian (400xRT) và yêu cầu chuyên gia trong ngôn ngữ học.
Phân loại văn bản : Lọc thƣ rác, phân loại tin nhắn, gợi ý các bài viết trên Internet, rất nhiều công việc cần ngƣời dùng gán nhãn cho văn bản ví dụ nhƣ “thích” hay “không thích”. Phải đọc và gán nhãn hàng ngàn tài liệu sẽ làm nản chí ngƣời dùng.
Phân tích cú pháp : Để huấn luyện một bộ phân tích cú pháp tốt cần những cặp mẫu câu và cây phân tích cú pháp, việc này đòi hỏi rất nhiều
Phạm Anh Toàn – CT1501 24
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
thời gian để xây dựng bởi những nhà ngôn ngữ học. Các chuyên gia phải mất vài năm để xây dựng các cây phân tích cú pháp cho vài nghìn mẫu câu.
Mặt khác, các dữ liệu không có nhãn thƣờng xuyên có sẵn với số lƣợng lớn và rất dễ thu thập. Các camera quan sát có thể chạy 24 giờ/ngày, các giọng đọc có thể đƣợc ghi âm, các văn bản có thể lấy đƣợc trên Internet, các mẫu câu thì có ở khắp nơi ... Với cách phân loại truyền thống gặp vấn đề là không thể sử dụng các dữ liệu chƣa có nhãn để huấn luyện bộ phân loại.
Câu hỏi đƣợc đặt ra là : Cho một tập tƣơng đối nhỏ dữ liệu đƣợc gán nhãn và một lƣợng lớn dữ liệu chƣa gán nhãn , có cách nào để sử dụng cả hai cho việc phân loại? Khái niệm “học bán giám sát” đƣợc ra đời từ thực tế là các dữ liệu đƣợc sử dụng là giữa học có giám sát và học không giám sát. Học bán giám sát sử dụng cả dữ liệu đã gán nhãn và dữ liệu chƣa gán nhãn cho mục đích học tập. Học bán giám sát hứa hẹn độ chính xác cao và lỗ lực chú thích thấp nhất.
Chúng ta có cả một chuỗi các ý tƣởng thú vị về cách học tập trên cả hai dữ liệu gán nhãn và không gán nhãn. Đây là một lĩnh vực đƣợc phát triển một cách nhanh chóng, trong phần này xin trình bày một cách sơ lƣợc về lịch sử của học bán giám sát.
Thời gian đầu, việc học bán giám sát giả định rằng có 2 lớp, mỗi lớp có một phân bố Gauss. Giả định dữ liệu đầy đủ lấy đƣợc từ một mô hình hỗn hợp. Với một lƣợng lớn các dữ liệu chƣa gán nhãn. các thành phần của mô hình hỗn hợp có thể đƣợc xác định với thuật toán Expectation Maximization. Chỉ cần một ví dụ có nhãn cho mỗi thành phần để xác định đầy đủ mô hình hỗn hợp. Mô hình này đã áp dụng thành công cho việc phân loại văn bản.
KẾT LUẬN
Sau một thời gian tìm hiểu và nghiên cứu đề tài này, em đã đạt đƣợc một số kết quả sau:
Tìm hiểu đƣợc cấu trúc của một hệ thống tra cứu ảnh dựa trên nội dung.
Tìm hiểu đƣợc một số phƣơng pháp làm giảm khoảng cách ngữ nghĩa trong tra cứu ảnh dựa trên nội dung.
Tìm hiểu phƣơng pháp phản hồi liên quan trong tra cứu ảnh.
Tìm hiểu về một số phƣơng pháp học máy đặc biệt là học bán giám sát dựa trên mô hình đồ thị.
Xây dựng đƣợc chƣơng trình thử nghiệm áp dụng phƣơng pháp phản hồi liên quan sử dụng học bán giám sát trên đồ thị cho tra cứu ảnh dựa trên nội dung.
Tuy nhiên đồ án vẫn còn tồn tại một số vấn đề :
Phần chƣơng trình cài đặt tính toán còn chậm do cài đặt trong môi trƣờng MS Visual Studio, khả năng của phần cứng có hạn chế.
Phần cài đặt học siêu tham số chƣa cho hiệu quả. Do độ phức tạp tính toán về thời gian của việc tính toán gradient là .
Để nâng cao độ chính xác trong tra cứu ảnh cần tiếp tục nghiên cứu về mô hình học bán giám sát.
Em rất mong nhận đƣợc sự đóng góp ý kiến từ các Thầy Cô và các bạn để em có thêm kiến thức và kinh nghiệm tiếp tục hoàn thiện nội dung nghiên cứu trong đề tài. Em xin chân thành cảm ơn!
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: