Thạc Sĩ Tra cứu ảnh dựa trên nội dung với phản hồi liên quan sử dụng mô hình học trên đồ thị 

2

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 Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 3
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

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 4
MỘT SỐ TỪ VIẾT TẮT

STT Từ viết tắt Mô tả
1 CBIR Content-Based Image Retrieval
2 EM Expectation Maximization
3 PCA Principal Component Analysis
4 RF Relevance Feedback
5 RGB Red-Green-Blue
6 SVM Support Vector Machine
7 TSVM Transductive Support Vector Machine
Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 5
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. Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 6
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
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 hoặc 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

Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 7
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 véc-tơ 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.
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.
1.2.1 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 hoặc 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 hoặc bán tự động. Một hoặc nhiều đặc trưng có thể được
sử dụng trong ứng dụ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 Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 8
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 hoặc 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). Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 9
1.2.1.4 Đặc trưng vị trí không gian
Các vùng hoặc đố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 Đánh chỉ 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 hoặc 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 Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 10
đố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 hoặc nội dung trực quan. Truy vấn bởi
khái niệm là tra cứu ảnh theo mô tả khái niệm liên quan với từng ảnh trong 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 hoặc cung cấp một ảnh ví dụ từ những ảnh với độ tương tự đặc trưng
trực quan sẽ được trích chọn từ cơ sở dữ liệu. Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 11
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 hoặc 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 đại diện 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 phải 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, hoặc 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. Tra cứu ảnh với phản hồi liên quan sử dụng mô hình học trên đồ thị
Phạm Anh Toàn – CT1501 12
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 hoặc vị trí không gian của các yếu tố hình ảnh. Điển