ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN VĂN TOÀN
NGHIÊN CỨU PHƯƠNG PHÁP TRA CỨU ẢNH
SỬ DỤNG PHÂN CỤM GIA TĂNG
VỚI PHẢN HỒI LIÊN QUAN
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN, 2018
i
LỜI CẢM ƠN
Luận văn này được hoàn thành với sự hướng dẫn tận tình của PGS.TS
Nguyễn Hữu Quỳnh – Khoa Công nghệ thông tin - Đại học Điện lực. Trước tiên
tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới PGS.TS Nguyễn Hữu Quỳnh
người đã tận tình hướng dẫn, động viên giúp đỡ tôi trong suốt thời gian thực hiện
luận văn. Tôi cũng xin chân thành cảm ơn các thầy cô trong trường Đại học Công
Nghệ thông tin và Truyền thông – Đại học Thái Nguyên, tạo điều kiện thuận lợi
cho tôi hoàn thành tốt khóa học.
Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học
CHK15A đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh
nghiệm học tập, công tác trong suốt khoá học.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc đến gia đình, người thân, bạn bè đã
động viên, khuyến khích và hỗ trợ cần thiết để tôi hoàn thành luận văn này.
Mặc dù rất cố gắng, song luận văn này không thể tránh khỏi những thiếu sót,
kính mong được sự chỉ dẫn của các quý thầy cô và các bạn.
Thái Nguyên, ngày 2 tháng 5 năm 2018
Người viết
Nguyễn Văn Toàn
ii
LỜI CAM ĐOAN
Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là
trung thực và không trùng lặp với các đề tài khác. Tôi cũng xin cam đoan rằng
mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin
trích dẫn trong luận văn đã được chỉ rõ nguồn gốc.
Thái Nguyên, ngày 2 tháng 5 năm 2018
Người cam đoan
Nguyễn Văn Toàn
iii
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................ i
LỜI CAM ĐOAN ................................................................................................. iii
MỤC LỤC ............................................................................................................ iv
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ....................................... vi
DANH MỤC CÁC BẢNG BIỂU ....................................................................... vii
DANH MỤC CÁC HÌNH .................................................................................. viii
MỞ ĐẦU ............................................................................................................... 1
CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG VỚI PHẢN HỒI LIÊN QUAN ..................................................................................... 4
1.1. Tổng quan về tra cứu ảnh dựa vào nội dung .............................................. 4 1.1.1. Vấn đề tra cứu ảnh dựa vào nội dung ................................................. 4 1.2. Tra cứu ảnh sử dụng phản hồi liên quan .................................................. 14 1.3. Vấn đề phân cụm[1] ................................................................................. 16 1.3.1. Thuật toán K-Means. ......................................................................... 20 1.3.2. Phân cụm phân cấp ........................................................................... 21 1.3.3. Phân cụm dựa vào mật độ ................................................................. 23 1.3.4. Phân cụm dựa vào mô hình ............................................................... 23 1.3.5. Phân cụm dựa vào đồ thị ................................................................... 26 1.4. Tiểu kết chương 1. ................................................................................... 26 CHƯƠNG 2: PHƯƠNG PHÁP TRA CỨU ẢNH VỚI PHẢN HỒI LIÊN QUAN SỬ DỤNG PHÂN CỤM GIA TĂNG ................................................................. 27
2.1. Tra cứu ảnh với ngữ nghĩa mức cao ........................................................ 27 2.1.1. Giới thiệu về tra cứu ảnh với ngữ nghĩa mức cao ............................. 27 2.1.2. Khoảng cách ngữ nghĩa ..................................................................... 28 2.1.3. Phản hồi liên quan ............................................................................. 29 2.2. Tra cứu ảnh với phản hồi liên quan ......................................................... 31 2.3. Kỹ thuật phân tích phân biệt tuyến tính (LDA-Linear Discriminant Analysis) .......................................................................................................... 32
iv
2.3.1. Định nghĩa về LDA ........................................................................... 32
2.3.2 Tính toán phương sai between-class (𝑺𝑩) ......................................... 32
2.3.3 Tính phương sai within-class (𝑺𝒘) .................................................... 34 2.3.4 Xây dựng không gian thấp chiều ....................................................... 36 2.3.5. Sơ đồ phương pháp tra cứu ảnh sử dụng phân cụm gia tăng trong phản hồi liên quan ................................................................................................ 37 2.4. Tiểu kết chương 2..................................................................................... 39 CHƯƠNG 3: CHƯƠNG TRÌNH THỬ NGHIỆM ............................................. 40
3.1. Giới thiệu bài toán tra cứu ảnh dựa vào nội dung .................................... 40 3.2. Môi trường thực nghiệm. ......................................................................... 41 3.2.1. Cơ sở dữ liệu ảnh. ............................................................................. 42 3.2.2. Vec-tơ đặc trưng ................................................................................ 43 3.2.3. Tập tin cậy nền .................................................................................. 44 3.2.4. Cấu hình đề xuất thiết bị chạy thực nghiệm ..................................... 44 3.3. Đánh giá kết quả thực nghiệm. ................................................................ 44 3.3.1. Chiến lược mô phỏng phản hồi liên quan. ........................................ 44 3.3.2. Kết quả đánh giá................................................................................ 45 3.4. Giao diện hệ thống ................................................................................... 47 3.5. Tiểu kết chương 3. ................................................................................... 51 KẾT LUẬN ......................................................................................................... 52
TÀI LIỆU THAM KHẢO ................................................................................... 53
v
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Từ viết tắt Diễn giải
Tra cứu ảnh dựa vào nội dung. CBIR
Tra cứu ảnh dựa vào vùng RBIR
CSDL Cơ sở dữ liệu
Mẫu vùng cấu tạo CRT
Earth Mover Distance EMD
Lược đồ đối sánh vùng tích hợp IRM
Hàm khoảng cách động một phần DPF
MRMD Khoảng cách đa tạp đa phân giải
RF Phản hồi liên quan
vi
DANH MỤC CÁC BẢNG BIỂU
Bảng 3.1. Bảng phân bố tập ảnh Corel................................................................ 42
Bảng 3.2. Các loại đặc trưng. .............................................................................. 43
Bảng 3.3. Bảng cấu hình đề xuất thiết bị chạy thực nghiệm. ............................. 44
Bảng 3.4. Bảng kết quả của các phương pháp .................................................... 46
vii
DANH MỤC CÁC HÌNH
Hình 1.1. Kiến trúc tổng quan của hệ thống tra cứu ảnh dựa vào nội dung. ........ 5
Hình 1.2. Không gian màu RGB. .......................................................................... 8
Hình 1.3. Không gian màu HSV. .......................................................................... 9
Hình 1.4. Lược đồ của một hệ thống CBIR với RF. ........................................... 16
Hình 1.5. Các tập dữ liệu và các cụm ................................................................. 17
Hình 1.6. Các tập dữ liệu không thích hợp với K-Means. .................................. 21
Hình 1.7 Phân cụm phân cấp tập dữ liệu D={a,b,c,d,e} ..................................... 22
Hình 2.1. Dịch chuyển điểm truy vấn. ................................................................ 29
Hình 2.2. Hình dạng lồi (đa điểm). ..................................................................... 30
Hình 2.3. Hình dạng lõm (đa điểm). ................................................................... 30
Hình 2.4. Tra cứu ảnh dựa vào nội dung với phản hồi liên quan. ...................... 31
Hình 2.5. Các bước được trực quan hóa để tính một không gian con chiều thấp hơn của kỹ thuật LDA. ........................................................................................ 33
Hình 2.6. Sơ đồ tra cứu ảnh sử dụng phân cụm gia tăng. ................................... 38
Hình 3.1. Mô hình tổng quát của hệ thống .......................................................... 41
Hình 3.2. Biểu đồ so sánh kết quả thực nghiệm ................................................. 46
Hình 3.3. Giao diện chính của hệ thống. ............................................................. 47
Hình 3.4. Chọn tập dữ liệu ảnh / đặc trưng ......................................................... 48
Hình 3.5. Chọn ảnh truy vấn khởi tạo. ................................................................ 48
Hình 3.6. Tra cứu với truy vấn khởi tạo 84003, 84004, 84008 thuộc lớp 840. .. 48
Hình 3.7. Kết quả phân cụm tập huấn luyện. ...................................................... 49
Hình 3.8. Công cụ tra cứu và phân cụm LDA. ................................................... 49
Hình 3.9. Kết quả tra cứu phản hồi liên quan. .................................................... 50
Hình 3.10. Kết quả phân cụm gia tăng. ............................................................... 50
Hình 3.11. Kết quả tra cứu sau khi sử dụng phân cụm gia tăng. ........................ 51
viii
MỞ ĐẦU
Tra cứu ảnh dựa vào nội dung (CBIR-Content Based Image Retrieval) đã
nhận được nhiều sự quan tâm trong thập kỷ qua, do nhu cầu xử lý hiệu quả lượng
dữ liệu đa phương tiện khổng lồ và tăng nhanh chóng. Nhiều hệ thống CBIR đã
được phát triển, gồm QBIC, Photobook, MARS, VisualSEEK, SIMPLIcity và
những hệ thống khác. Trong một hệ thống CBIR tiêu biểu, các đặc trưng ảnh trực
quan mức thấp (tức là màu, kết cấu và hình dạng) được trích rút tự động cho mục
tiêu đánh chỉ số và mô tả ảnh. Để tìm kiếm các ảnh mong muốn, người dùng đưa
một ảnh làm mẫu và hệ thống trả lại một tập các ảnh tương tự dựa vào các đặc
trưng được trích rút.
Là một vấn đề quan trọng trong CBIR, độ đo tương tự lượng hóa sự giống
nhau về nội dung giữa từng cặp ảnh. Phụ thuộc vào kiểu đặc trưng được trích rút
mà chúng ta lựa chọn độ đo tương tự thích hợp. Tất cả các kỹ thuật tra cứu ảnh
dựa vào nội dung hiện nay đều thừa nhận thông tin tương hỗ giữa độ đo tương tự
ảnh và ngữ nghĩa của ảnh. Bằng nhiều cách khác nhau, độ đo tương tự cố gắng
nắm được một khía cạnh nào đó của nội dung ảnh, đó là ngữ nghĩa kế thừa từ độ
tương tự hay đặc trưng mức thấp. Tuy nhiên, ngữ nghĩa kế thừa từ độ tương tự
nhiều khi không giống với khái niệm mức cao được truyền tải bởi một ảnh (ngữ
nghĩa của ảnh). Đó chính là khoảng cách ngữ nghĩa, nó phản ánh sự khác biệt giữa
năng lực mô tả hạn chế của đặc trưng trực quan mức thấp và khái niệm mức cao.
Các kỹ thuật trong việc rút ngắn “khoảng cách ngữ nghĩa” gồm có 5 loại chính:
(1) sử dụng bản thể đối tượng để xác định các khái niệm mức cao, (2) sử dụng
các công cụ học máy để kết hợp các đặc trưng mức thấp với các khái niệm truy
vấn, (3) đưa phản hồi liên quan vào lặp tra cứu cho học ý định của người dùng,
(4) sinh ra mẫu ngữ nghĩa để hỗ trợ tra cứu ảnh mức cao, (5) Cách sử dụng cả nội
dung trực quan của các ảnh và thông tin văn bản thu được từ Web cho tra cứu ảnh
trên Web.
1
Từ những nhận định trên và được sự gợi ý của giáo viên hướng dẫn, tôi quyết
định chọn đề tài: “Nghiên cứu phương pháp tra cứu ảnh sử dụng phân cụm
gia tăng với phản hồi liên quan”. Đề tài sẽ kết hợp hai hướng tiếp cận (2) và (3),
đưa phản hồi liên quan của người dùng vào quá trình tra cứu và sử dụng phương
pháp phân cụm gia tăng để phân cụm tập ảnh phản hồi nhằm biểu diễn nhu cầu
thông tin người dùng hiệu quả.
Phản hồi liên quan là một quá trình trực tuyến mà cố gắng học mục đích của
người dùng trong quá trình tra cứu, là một công cụ mạnh được sử dụng truyền
thống trong các hệ thống tra cứu thông tin. Nó được giới thiệu đối với CBIR
khoảng đầu những năm 1990, với mục đích mang người dùng vào lặp tra cứu để
giảm khoảng cách ngữ nghĩa giữa những gì mà truy vấn biểu diễn và những gì
người dùng nghĩ. Bằng việc tiếp tục học thông qua tương tác với các người dùng
cuối, phản hồi liên quan đã được chỉ ra là cung cấp cải tiến hiệu năng đáng kể
trong các hệ thống CBIR.
Phân cụm là một phương pháp học không giám sát để tạo thành các nhóm
hay các cụm dữ liệu. Lý thuyết phân cụm giả thuyết rằng “các đối tượng gần nhau
có xu hướng liên quan tới cùng một yêu cầu”. Đã có nhiều thuật toán thực hiện
việc phân cụm như: K-mean, K-medoid, EM…Tuy nhiên, các thuật toán này
thường được gọi là phân cụm ngoại tuyến (off-line), tức là, các thuật toán này
thực hiện phân cụm trên toàn bộ cơ sở dữ liệu ảnh đã có sẵn (gồm rất nhiều ảnh),
mỗi khi có ảnh mới bổ sung vào, quá trình lại phải phân cụm lại từ đầu. Các thuật
toán ngoại tuyến không phù hợp trong các trường hợp đòi hỏi trực tuyến (on-line),
chẳng hạn, trường hợp mà áp dụng trên một tập ảnh nhỏ (là kết quả của một lần
thực hiện tra cứu) nhưng đòi hỏi phân cụm ngay lập tức trong khi vẫn còn nhiều
ảnh cần được bổ sung và phân cụm tiếp theo không cần phải tiến hành với dữ liệu
đã được phân cụm trước đó. Thuật toán mà đáp ứng trường hợp trực tuyến này
phải có tính chất “gia tăng” hay gọi là phân cụm gia tăng.
2
Nhiệm vụ chính của luận văn là nắm vững kiến thức tổng quan của lĩnh vực
xử lý ảnh, đi sâu nghiên cứu lĩnh vực tra cứu ảnh dựa vào nội dung, tìm hiểu một
số thuật toán học không giám sát, nghiên cứu thuật toán phân cụm gia tăng và đưa
vào hệ thống tra cứu ảnh dựa vào nội dung. Cài đặt chương trình thử nghiệm đánh
giá, so sánh hiệu quả của hệ thống tra cứu ảnh dựa vào nội dung sử dụng phân
cụm phổ với một số hệ thống tra cứu ảnh điển hình khác.
Bố cục luận văn:
Chương 1: Tổng quan về tra cứu ảnh dựa vào nội dung với phản hồi liên quan
Chương 2: Phương pháp tra cứu ảnh với phản hồi liên quan sử dụng phân cụm
gia tăng.
Chương 3: Chương trình thử nghiệm.
3
CHƯƠNG 1: TỔNG QUAN VỀ TRA CỨU ẢNH DỰA VÀO NỘI DUNG
VỚI PHẢN HỒI LIÊN QUAN
1.1. Tổng quan về tra cứu ảnh dựa vào nội dung
1.1.1. Vấn đề tra cứu ảnh dựa vào nội dung
Tra cứu ảnh dựa vào nội dung là việc áp dụng kỹ thuật thị giác máy tính vào vấn đề tìm kiếm hình ảnh, tức là vấn đề tìm kiếm hình ảnh kỹ thuật số trong các cơ sở dữ liệu (lớn). Tra cứu ảnh dựa vào nội dung sử dụng những nội dung thị giác như màu sắc, hình dạng, kết cấu, không gian để biểu diễn ảnh. Các nội dung thị giác của ảnh được trích rút và mô tả bằng các véc tơ đặc trưng đa chiều có dạng véc tơ đặc trưng của cơ sở dữ liệu. Khởi đầu cho việc tra cứu ảnh, người dùng cung cấp một ảnh mẫu cho hệ thống tra cứu. Hệ thống này sẽ chuyển đổi những ảnh mẫu này thành các véc tơ đặc trưng và so sánh với khoảng cách/độ tương tự của các véc tơ đặc trưng của những ảnh trong cơ sở dữ liệu để tính toán và đưa ra kết quả là bức ảnh có độ tương tự cao nhất.
Hệ thống tra cứu ảnh dựa vào nội dung
1.1.1.1. Các chức năng của hệ thống tra cứu ảnh dựa vào nội dung
Một hệ thống tra cứu ảnh dựa vào nội dung (CBIR – Content Based Image
Retrieval) có các chức năng chính như sau:
1) Trích rút đặc trưng và biểu diễn các nội dung của các nguồn được phân tích theo cách thích hợp cho so sánh các truy vấn sử dụng (không gian của nguồn thông tin được biến đổi thành không gian đặc trưng cho mục tiêu so sánh nhanh trong bước tiếp theo). Bước này thông thường cần rất nhiều thời gian do nó phải xử lý lần lượt tất cả thông tin nguồn (các ảnh) trong cơ sở dữ liệu. Tuy nhiên, bước này được thực hiện chỉ một lần và có thể được thực hiện ngoại tuyến.
2) Phân tích truy vấn của người sử dụng và biểu diễn chúng dưới dạng thích hợp để đối sánh với cơ sở dữ liệu nguồn. Bước này là tương tự với bước trước, nhưng chỉ áp dụng với ảnh cần truy vấn.
3) Thực hiện so sánh các truy vấn tìm kiếm với thông tin có trong cơ sở dữ liệu được lưu trữ để tra cứu thông tin liên quan theo một cách hiệu quả. Bước này
4
được thực hiện trực tuyến và yêu cầu là phải đáp ứng rất nhanh. Các kỹ thuật đánh chỉ số hiện đại có thể được sử dụng để tổ chức lại không gian đặc trưng nhằm tăng tốc quá trình đối sánh.
4) Thực hiện các điều chỉnh cần thiết trong hệ thống (thường là điều chỉnh các tham số trong máy đối sánh) dựa trên phản hồi từ người sử dụng và/hoặc các ảnh được tra cứu.
Thực hiện ngoại tuyến
1.1.1.2. Một số hệ thống CBIR tiêu biểu
Cơ sở dữ liệu đặc trưng Cơ sở dữ liệu ảnh
Đ á n h c h ỉ s ố
So sánh độ tương tự
T r í c h r ú t đ ặ c t r ư n g
Người dùng Đầu ra
Véc tơ đặc trưng Tạo truy vấn Các kết quả tra cứu
Phản hồi liên quan
Hình 1.1. Kiến trúc tổng quan của hệ thống tra cứu ảnh dựa vào nội dung.
Một hệ thống CBIR sẽ thực hiện truy vấn ảnh dựa trên việc tự động rút trích các thông tin đặc trưng hình ảnh như: màu sắc, kết cấu, hình dạng, vị trí. Các nhà nghiên cứu đã đưa ra nhiều phương pháp với những cách tiếp cận khác nhau; do đó rất nhiều hệ thống truy vấn ảnh dựa trên nội dung đã ra đời như: QBIC, BlobWorld, VisualSEEk, MARS, Photobook, Virage, Netra, SIMPLIcity, NEC PicHunter… Dưới đây xin điểm qua một số hệ thống CBIR tiêu biểu.
5
1) Hệ thống QBIC
Hệ thống truy vấn ảnh theo nội dung QBIC (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, là hệ thống tra cứu ảnh thương mại được phát triển từ rất sớm. Người dùng xây dựng một phác thảo, vẽ ra và lựa chọn màu cùng kết cấu dựa theo ảnh truy vấn.
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 đánh chỉ số và tìm kiếm. Hiện nay 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.
2) Hệ thống Blobwold
Hệ thống Blobwold do khoa Khoa học máy tính, Đại học California, Berkeley nghiên cứu và phát triển. Các đặc tính được sử dụng cho truy vấn là màu sắc, kết cấu, vị trí và hình dạng của vùng và nền. Màu sắc được mô tả bởi biểu đồ 218 bin màu kết hợp trong không gian Lab. Kết cấu được thể hiện bằng sự tương phản và không đẳng hướng trên vùng như không gian 2D (độ tương phản, độ tương phản x tính không đẳng hướng). Hình dạng được thể hiện bằng (xấp xỉ) vùng, độ lệch tâm và định hướng.
3) Hệ thống VisualSEEk
Hệ thống VisualSEEk được xây dựng bởi Trung tâm nghiên cứu viễn thông thuộc trường đại học Columbia, New York. Đây là hệ thống truy vấn dựa vào các đặc trưng trực quan của ảnh, sử dụng không gian 166 màu HSV. Sự tương đồng giữa hai ảnh được xác định theo sự tương đồng của các vùng trong ảnh. 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.
4) Hệ thống Netra
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 trong các vùng ảnh được phân đoạn để tìm kiếm và tra cứu các
6
vùng tương tự từ cơ sở dữ liệu. Các đặc trưng nghiên cứu chính của hệ thống Netra là phân tích kết cấu dựa trên lọc Gabor, xây dựng từ điển ảnh dựa trên mạng neural và phân đoạn vùng dựa vào luồng biên.
Trích rút đặc trưng
Trích rút đặc trưng ảnh mức thấp là cơ sở của các hệ thống CBIR. Trích rút đặc trưng bao gồm trích rút thông tin có nghĩa của ảnh, làm giảm dung lượng lưu trữ, do đó hệ thống sẽ nhanh và hiệu quả hơn trong CBIR.
1.1.1.3. Đặc trưng màu sắc
Đặc trưng màu sắc được sử dụng rộng rãi nhất trong tra cứu ảnh. Một vài phương pháp tra cứu ảnh dựa trên cơ sở sự tương tự về màu sắc đã được mô tả trong các tài liệu nhưng các ý tưởng cơ bản là giống nhau. Mỗi hình ảnh được thêm vào bộ sưu tập được phân tích và tính toán biểu đồ màu để thấy tỷ lệ điểm ảnh của mỗi màu trong một ảnh. Biểu đồ màu của mỗi ảnh sau đó được lưu trữ trong cơ sở dữ liệu để khi tìm kiếm, người dùng có thể xác định tỷ lệ mong muốn của mỗi màu hoặc gửi một ảnh mẫu mà đã được tính toán biểu đồ màu. Dù bằng cách nào đi chăng nữa thì quá trình tra cứu sau đó là lấy ra những bức ảnh mà có biểu đồ màu tương ứng gần nhất với ảnh truy vấn.
1) Không gian màu
- Không gian màu RGB (Red – Green – Blue)
Không gian màu RGB được sử dụng nhiều nhất cho đồ họa máy tính, mô tả màu sắc bằng 3 thành phần chính là R (Red) – G (Green) và B (Blue). Không gian này được xem như một khối lập phương 3 chiều với màu Red là trục x, màu Green là trục y, và màu Blue là trục z. Mỗi màu trong không gian này được xác định bởi 3 thành phần R, G, B. Ứng với các tổ hợp khác nhau của 3 màu này sẽ cho ta một màu mới.
Không gian màu RGB được sử dụng rộng rãi trong việc biểu diễn ảnh, gồm 3 thành phần màu là đỏ, xanh lục, xanh lam. Chúng được gọi là bộ cộng sơ cấp vì một màu khác trong không gian RGB được tạo ra bằng cách thêm chúng.
7
Hình 1.2. Không gian màu RGB.
- Không gian màu CIE
Không gian màu CIE L*a*b và CIE L*u*v là không gian độc lập và được xem như đồng bộ. Chúng chứa độ sáng hoặc thành phần nhẹ sáng (L) và hai thành phần màu a và b hoặc u và v. Có thể chuyển từ không gian màu RGB thành không gian CIEL*a*b và CIE L*u*v.
- Không gian màu HSV
Không gian màu HSV (HSL hoặc HSB) được sử dụng rộng rãi trong đồ họa máy tính và miêu tả màu một cách trực quan hơn. Ba thành phần màu có màu sắc, độ bão hòa (nhẹ sáng) và giá trị (độ sáng). Không gian RGB cũng có thể được chuyển thành không gian HSV bằng công thức đơn giản.
Không gian màu thành phần sử dụng trục màu thành phần (R-G, 2B-R-G, R+G+B). Cách thể hiện này có lợi thế trong việc cô lập thông tin về độ sáng ở trục thứ ba. Hai trục màu đầu tiên bất biến với sự thay đổi cường độ sáng và tối, có thể giảm việc lấy mẫu khi con người nhạy cảm với độ sáng hơn.
8
Hình 1.3. Không gian màu HSV.
2) Lược đồ màu
Lược đồ màu được xác định bằng một tập các bin, trong đó mỗi bin biểu thị xác suất của các pixel trong ảnh. Một lược đồ màu H của một ảnh đã cho được xác định bởi véc tơ:
H={H[0], H[1], H[2], ..., H[i],... H[N]}
Ở đây i biểu diễn một màu trong lược đồ màu và tương ứng với một khối con trong không gian màu RGB, H[i] là số các pixel có màu i trong ảnh và N là số các bin trong lược đồ màu.
1.1.1.4. Đặc trưng kết cấu
Kết cấu là một mô tả vùng trợ giúp tốt trong quá trình tra cứu. Kết cấu không có khả năng tìm ra các ảnh tương tự, nhưng nó có thể được sử dụng để phân lớp các ảnh kết cấu từ các ảnh không kết cấu và sau đó được kết hợp với các thuộc tính đặc trưng khác như màu để làm cho tra cứu hiệu quả hơn. Kết cấu là một thuộc tính quan trọng khác của ảnh. Những kết cấu đa dạng đã được xem xét trong các mẫu nhận dạng và tầm nhìn máy tính. Phương pháp đại diện cấu trúc được phân thành hai loại: cấu trúc và thống kê. Phương pháp cấu trúc gồm có hoạt động
9
hình thái và đồ thị kề. Phương pháp thống kê gồm: quang phổ Fourier, ma trận đồng xuất hiện, phân tích bộ phận chính thay đổi bất biến, tính năng Tamura, phân hủy Wold, trường ngẫu nhiên Markov, mô hình fractal và bộ lọc đa phân giải.
1.1.1.5. Đặc trưng hình dạng
Hình dạng được xem như là một đặc trưng quan trọng trong mô tả các đối tượng nổi bật trong ảnh và có thể giúp phân biệt giữa hai ảnh. Các đặc trưng hình dạng của ứng dụng nói chung gồm aspect ratio, circularity, Fourier descriptors, moment invariants, consecutive boundary segments.
Đặc trưng hình dạng của đối tượng hoặc vùng đã được sử dụng nhiều trong hệ thống tra cứu ảnh dựa vào nội dung. So với đặc tính màu sắc và kết cấu thì hình dạng thường được mô tả sau khi ảnh được phân đoạn thành các vùng hoặc các đối tượng. Khi mà việc phân đoạn ảnh rất khó để đạt được độ chính xác và mạnh mẽ thì việc sử dụng đặc tính hình dạng trong tra cứu ảnh đã được giới hạn trong các ứng dụng đặc biệt nơi mà các đối tượng hoặc các vùng đã có sẵn. Mô tả hình dạng có thể dựa vào biên hoặc dựa vào vùng. Đặc tính hình dạng tốt với đối tượng là bất biến với xoay, dịch chuyển và mở rộng.
1.1.1.6. Vị trí không gian
Bên cạnh kết cấu và màu, vị trí không gian cũng là hữu ích trong phân lớp vùng. Chẳng hạn, “bầu trời” và “biển” có thể có các đặc trưng kết cấu và màu tương tự, nhưng vị trí không gian của chúng là khác nhau với “bầu trời” thường xuất hiện ở trên đỉnh của ảnh, trong khi biển ở dưới.
Vị trí không gian thường được xác định đơn giản như “trên, dưới, đỉnh” theo vị trí của vùng trong một ảnh. Trọng tâm vùng và hình chữ nhật bao tối thiểu của nó được sử dụng để cung cấp thông tin vị trí không gian. Tâm không gian của một vùng được sử dụng để biểu diễn vị trí không gian của nó.
Quan hệ không gian tương đối là quan trọng hơn vị trí không gian tuyệt đối trong các đặc trưng ngữ nghĩa. Xâu 2-D và các biến thể của nó là cấu trúc phổ biến nhất được sử dụng để biểu diễn các quan hệ hướng giữa các đối tượng như “trái/phải”, “dưới/trên”. Tuy nhiên, chỉ một mình quan hệ hướng không đủ để biểu
10
diễn nội dung ngữ nghĩa của các ảnh khi bỏ qua quan hệ topo. Để hỗ trợ tốt hơn cho tra cứu ảnh dựa vào ngữ nghĩa, một thuật toán mô hình ngữ cảnh không gian được trình bày mà xem xét sáu quan hệ không gian giữa cắc cặp vùng: trái, phải, trên, dưới, tiếp xúc và trước. Một phương pháp thú vị được đề xuất bởi Smith và cộng sự. Hệ thống sử dụng một mẫu vùng cấu tạo (CRT) để xác định sự sắp xếp không gian của các vùng và mỗi lớp ngữ nghĩa được đặc trưng bởi các CRT thu được từ một tập các ảnh mẫu.
Độ đo tương tự
Hệ thống tra cứu ảnh dựa vào nội dung tính toán độ tương tự trực quan giữa ảnh truy vấn và ảnh trong cơ sở dữ liệu. Khi đó, kết quả tra cứu không chỉ là một ảnh mà gồm một danh sách ảnh được xếp hạng theo độ tương tự với ảnh truy vấn. Có nhiều phương pháp đo độ tương tự đã được phát triển trong tra cứu ảnh những năm gần đây. Các phương pháp đo khoảng cách/độ tương tự khác nhau ảnh hưởng đáng kể tới hiệu suất tra cứu.
Trong các hệ thống tra cứu ảnh CBIR dựa vào vùng (RBIR), độ tương tự ảnh được đo ở hai mức. Đầu tiên là mức vùng. Tức là đo khoảng cách giữa hai vùng dựa trên các đặc trưng mức thấp của chúng. Thứ hai là mức ảnh. Tức là đo độ tương tự toàn bộ của hai ảnh mà có thể chứa số các vùng khác nhau.
Hầu hết các nhà nghiên cứu sử dụng độ đo kiểu Minkowski để xác định khoảng vùng. Giả sử chúng ta có hai vùng biểu diễn bởi hai véc tơ p chiều (x1, x2,…xp), (y1, y2,…yp) tương ứng. Độ đo Minkowski được xác định như sau:
1/𝑟 )
𝑝 𝑑(𝑋, 𝑌) = (∑ |𝑥𝑖 − 𝑦𝑖| 𝑖=1
(1.1)
Cụ thể, khi r bằng 2, nó là khoảng cách Euclidean nổi tiếng (khoảng cách
L2). Khi r là 1, nó là khoảng cách Manhattan (khoảng cách L1).
Một phiên bản biến thể được sử dụng thường xuyên là hàm khoảng cách Minkowski có trọng số mà đưa trọng số vào để nhận biết các đặc trưng quan trọng.
1/𝑟 )
𝑝 𝑑(𝑋, 𝑌) = (∑ 𝑤𝑖|𝑥𝑖 − 𝑦𝑖|𝑟 𝑖=1
(1.2)
Ở đây wi, i=1,…,p là trọng số được áp dụng vào các đặc trưng khác nhau.
11
Các khoảng cách khác cũng được sử dụng trong tra cứu ảnh, như khoảng cách Canberra, khoảng cách angular, hệ số Czekanowski, tích trong, hệ số dice, hệ số cosine và hệ số Jaccard.
Độ tương tự toàn thể của hai ảnh là khó hơn để đo. Về cơ bản có hai cách:
Đối sánh mộ t- một: Nghĩa là mỗi vùng trong ảnh truy vấn chỉ được phép đối sánh một vùng trong ảnh mục tiêu và ngược lại. Như trong [8], mỗi vùng truy vấn của ảnh truy vấn được kết hợp với một vùng đối sánh tốt nhất trong ảnh mục tiêu. Sau đó độ tương tự toàn bộ được xác định bằng tổng có trọng số của độ tương tự giữa mỗi vùng truy vấn trong ảnh truy vấn và đối sánh tốt nhất của nó trong ảnh mục tiêu, trong khi trọng số liên quan đến cỡ vùng.
Đối sánh nhiều - nhiều: Có nghĩa là mỗi vùng trong ảnh truy vấn được phép đối sánh nhiều hơn một vùng trong ảnh mục tiêu và ngược lại. Một phương pháp được sử dụng phổ biến là khoảng cách EMD (Earth Mover Distance). EMD là một độ đo linh hoạt và tổng quát. Nó đo chi phí cực tiểu được yêu cầu để biến đổi một phân bố sang một phân bố khác dựa vào bài toán giao vận truyền thống từ tối ưu tuyến tính, theo đó các thuật toán hiệu quả là sẵn có. EMD đối sánh tương tự nhận thức tốt và có thể được áp dụng đối với các biểu diễn của các phân bố có độ dài thay đổi, vì thế nó thích hợp cho đo độ tương tự ảnh trong hệ thống RBIR.
Li và cộng sự đề xuất một lược đồ đối sánh vùng tích hợp (IRM) mà cho phép đối sánh một vùng của một ảnh với một số vùng của ảnh khác và do đó giảm sự ảnh hưởng của phân đoạn thiếu chính xác. Trong định nghĩa này, một đối sánh giữa hai vùng bất kỳ được gán với một điểm quan trọng. Điều này tạo ta một ma trận quan trọng giữa hai tập vùng (một tập là của ảnh truy vấn, tập còn lại là của ảnh mục tiêu). Độ tương tự toàn thể của hai ảnh được xác định dựa vào ma trận quan trọng trong một cách tương tự với EMD.
Dù độ đo Minkowski được sử dụng rộng rãi trong các hệ thống hiện nay để đo khoảng cách vùng, các thực nghiệm mở rộng chỉ ra rằng nó không hiệu quả trong mô hình độ tương tự nhận thức. Cách đo độ tương tự nhận thức vẫn là một câu hỏi lớn chưa có đáp án. Có một số nghiên cứu đã thực hiện trong nỗ nực để giải quyết vấn đề này. Chẳng hạn, trong [4], một hàm khoảng cách động một phần
12
(DPF) được xác định, nó giảm chiều của các véc tơ đặc trưng bằng việc chọn động một lượng nhỏ của các chiều. Cho𝛿𝑖 = |𝑥𝑖 − 𝑦𝑖|, 𝑖 = 1, . . 𝑝các tác giả xác định∆𝑚= {𝑚 𝑐á𝑐 𝛿 𝑛ℎỏ 𝑛ℎấ𝑡 𝑡𝑟𝑜𝑛𝑔 (𝛿1, … , 𝛿𝑝). Sau đó DPF được xác định bằng
1/𝑟 )
𝑟 𝑑(𝑚, 𝑟) = (∑ 𝛿𝑖
𝛿𝑖
(1.3)
Có hai tham số được điều chỉnh m và r. Các kết quả thực nghiệm ban đầu minh chứng rằng DPF có thể cung cấp các kết quả tra cứu chính xác hơn độ đo Minkowski. Tuy nhiên, giá trị m là phụ thuộc dữ liệu, điều này làm cho thuật toán không linh hoạt. Ngoài ra, để được sử dụng rộng rãi trong các hệ thống tra cứu ảnh, nghiên cứu xa hơn được yêu cầu để xác thực hiệu năng của nó trong các ứng dụng khác nhau.
Trong [9], một khoảng cách nhận thức cho độ đo tương tự hình dạng được trình bày. Mỗi hình dạng được đặc trưng với một tập các dấu hiệu. Một khoảng cách độ đo giữa các dấu hiệu được xác định đầu tiên sau đó một khoảng cách không độ đo được xác định bằng tập khoảng cách dấu hiệu để đo độ tương tự hình. Phương pháp có thể được mở rộng sang RBIR bằng việc coi các vùng ảnh như các dấu hiệu.
Vasconcelos và Lippman đã đề xuất một khoảng cách đa tạp đa phân giải (MRMD) cho nhận dạng khuôn mặt. Trong MRMD, hai ảnh được đối sánh được xem là đa tạp và khoảng cách giữa hai ảnh là một cực tiểu sai số của biến đổi một đa tạp sang một đa tạp khác. Để giảm tính toán, các ảnh được đưa vào phân tích đa phân giải. Đo khoảng cách là thích hợp cho các ứng dụng gióng hàng ảnh như nhận dạng khuôn mặt và phát hiện cảnh video.
Trong [3], đo độ tương tự giữa các loại đặc trưng ảnh khác nhau được xem như một quyết định đa mức xử lý. Các ảnh trong cơ sở dữ liệu được biểu diễn bởi một số các bộ mô tả kết cấu và màu MPEG-7, các bộ mô tả này được đưa sang một khuôn khổ hợp nhất quyết định phân cấp sử dụng logic mờ. Ưu điểm của độ đo tương tự này là các loại đặc trưng ảnh khác nhau có thể được kết hợp thành một đặc trưng tích hợp. Trong nghiên cứu sau đó, các tác giả đã mở rộng khuôn
13
khổ hợp nhất quyết định thành khuôn khổ học có giám sát với phản hồi liên quan từ người dùng [2].
1.2. Tra cứu ảnh sử dụng phản hồi liên quan
Tra cứu ảnh dựa vào nội dung đã thu hút nhiều sự quan tâm nghiên cứu và đã đạt được nhiều thành tựu, tuy nhiên, các nỗ lực nghiên cứu này vẫn chưa theo kịp sự phát triển của tra cứu thông tin (văn bản). Có hai lý do cho sự không hiệu quả của các hệ thống này là:
- Thứ nhất là: Khoảng trống giữa các đặc trưng mức thấp và các khái niệm mức cao (khoảng cách ngữ nghĩa). Vấn đề xuất phát từ thực tế là các đặc trưng như màu, kết cấu, và hình dạng không chuyển tải ý nghĩa của ảnh; do đó, nhiều độ đo tương tự trực quan được sử dụng trong quá trình tra cứu như các lược đồ màu hoặc các mô tả Fourier là chưa đủ bởi vì các biểu diễn đặc trưng này không nhất thiết phải phù hợp với ngữ nghĩa được gán cho ảnh nào đó của người dùng.
- Thứ 2 là: Sự nhận thức chủ quan của con người: hai người khác nhau hoặc thậm chí cùng một người trong các hoàn cảnh khác nhau có thể có các giải thích khác nhau về cùng nội dung trực quan ảnh. Sự nhận thức chủ quan của con người tồn tại ở các mức khác nhau: một người có thể quan tâm nhiều hơn đến đặc trưng màu của ảnh, trong khi người khác có thể đưa ra nhiều sự liên quan đến đặc trưng kết cấu; thậm chí nếu cả hai cùng quan tâm đến đặc trưng kết cấu, cách họ cảm nhận về độ tương tự của kết cấu có thể rất khác nhau.
Để giải quyết các hạn chế của CBIR, một kỹ thuật được gọi là phản hồi liên quan được giới thiệu, trong đó người và máy tính tương tác nhiều lần với nhau để cải tiến các truy vấn mức cao đối với các biểu diễn dựa trên các đặc trưng ảnh mức thấp. Kỹ thuật đã được áp dụng thành công tương đối lâu trong tra cứu tài liệu, nhưng mới được quan tâm nhiều trong cộng đồng CBIR. Những lý do cho điều này là do các vấn đề nhận thức chủ quan của con người, khoảng cách ngữ nghĩa, và cũng do thực tế không giống như các tài liệu văn bản, đánh giá một ảnh và quyết định một ảnh là liên quan hay không cũng không phải là gánh nặng đối với người dùng. Điều này tạo cho quá trình phản hồi liên quan hợp lý và nhanh hơn. Tuy nhiên, thực tế chủ yếu góp phần làm cho phản hồi liên quan là chủ đề
14
nghiên cứu tích cực nhất trong CBIR là do độ chính xác của các máy tìm kiếm CBIR nói chung rất thấp.
Phản hồi liên quan trong CBIR là quá trình điều chỉnh động một truy vấn đã có sử dụng thông tin phản hồi từ người dùng về sự liên quan của các ảnh được tra cứu từ trước sao cho truy vấn được điều chỉnh xấp xỉ tốt nhất đối với nhu cầu của người dùng. Mục tiêu của một quá trình như thế là thu được truy vấn mức cao của người dùng và nhận thức chủ quan bằng việc tương tác với anh/chị ấy và điều chỉnh tự động các trọng số dựa trên phản hồi được cung cấp. Một ngữ cảnh trong hệ thống phản hồi liên quan (Relevance Feedback - RF) là:
Bước 1: Người dùng đưa ra một ảnh mẫu truy vấn và/hoặc từ khóa mô tả đối
đối với hệ thống.
Bước 2: Hệ thống cung cấp các kết quả tra cứu khởi tạo dựa trên các độ đo
tương tự nào đó đã được xác định trước.
Bước 3: Người dùng đánh dấu các ảnh được tra cứu bằng việc đánh giá chúng
có liên quan đến truy vấn hay không.
Bước 4: Dựa trên thông tin phản hồi bởi người dùng, hệ thống điều chỉnh truy vấn và tra cứu một danh sách mới các ảnh cho người dùng. Thuật toán lặp lại Bước 3.
Hình 1.4 chỉ ra một lược đồ đơn giản của một hệ thống CBIR với RF.
15
Lặp phản hồi Truy vấn người dùng khởi tạo (ảnh mẫu hoặc từ khóa)
Các kết quả tra cứu
Phản hồi người dùng
Cơ sở dữ liệu ảnh Các mẫu được gán nhãn (các ảnh liên quan hay không)
Học (điều chỉnh các tham số truy vấn)
Các kết quả tra cứu cuối cùng
Hình 1.4. Lược đồ của một hệ thống CBIR với RF.
1.3. Vấn đề phân cụm.
Khái niệm phân cụm
Phân cụm (clustering/cluster analysic) là quá trình phân chia tập đối tượng dữ liệu thành các cụm (cluster), sao cho các đối tượng trong cùng một cụm là tương tự với nhau, các đối tượng trong các cụm khác nhau thì không tương tự với nhau. Khác với phân lớp là học có giám sát (học từ tập ví dụ gắn nhãn), phân cụm là một vấn đề của học không giám sát (học từ tập ví dụ không gắn nhãn).
Phân cụm vốn dĩ là một hoạt động quan trọng trong tư duy nhận thức của con người. Từ lâu phân cụm đã được thực hiện trong nhiều ngành khoa học như sinh học, y học, địa lý, tâm lý học... Hiện nay phân cụm được ứng dụng trong nhiều lĩnh vực như: khai khoáng dữ liệu (data mining), tra cứu thông tin (information retrieval), nhận dạng mẫu (pettern recognition), xử lý hình ảnh (image processing), thị giác máy tính (computer vision), marketing...
16
Hình 1.5 biểu diễn ba tập dữ liệu trong không gian 2 chiều. Hầu hết ai quan sát cũng cho rằng, tập dữ liệu hình 1.5a có 3 cụm, hình 1.5b có 2 cụm, hình 1.5c có 2 cụm, được chỉ ra (bằng khoanh vùng) trong các hình 1.5a, 1.5b và 1.5c tương ứng. Trong hình 1.5c, các điểm nằm ngoài 2 vùng được khoanh không thuộc cụm nào cả, chúng được xem như các dữ liệu nhiễu (ngoại lai). Thế nhưng nếu hỏi, lý do nào bạn cho rằng các tập dữ liệu đó có các cụm như thế, có lẽ chúng ta sẽ rất lúng túng đưa ra câu trả lời. Sẽ không có một định nghĩa chính xác (về mặt toán học) về cụm thích hợp cho cả ba tập dữ liệu hình 1.5, để dựa vào định nghĩa đó chúng ta xác định được các cụm như đã được chỉ ra.
(a) (b) (c)
Hình 1.5. Các tập dữ liệu và các cụm
Chúng ta sẽ hiểu rõ hơn về khái niệm cụm, nếu chúng ta mô tả cụm bởi hai đặc trưng: sự gắn kết bên trong (cohesion/compactness) giữa các đối tượng trong cùng một cụm, và sự cô lập bên ngoài hay sự tách biệt (separation) giữa các cụm. Theo hai đặc trưng này, với việc xác định ý nghĩa cụ thể cho sự gắn kết bên trong một cụm và sự tách biệt giữa các cụm, chúng ta có thể đưa ra một mô tả chính xác hơn về cụm. Có nhiều cách xác định sự gắn kết giữa các đối tượng trong cùng một cụm, và sự tách biệt giữa các cụm, và do đó có nhiều cách quan niệm về cụm.
17
Với một tập dữ liệu đã cho, chúng ta không biết trước cấu trúc của tập dữ liệu đó (mục tiêu của phân cụm chính là để phát hiện ra cấu trúc của tập dữ liệu), chúng ta không biết tập đó có cụm hay không? có mấy cụm? sự gắn kết nào tạo ra cụm? làm thế nào để tìm ra các cụm vốn có của tập dữ liệu đó? Đã có rất nhiều thuật toán phân cụm được đề xuất. Nhiều thuật toán phân cụm đòi hỏi số cụm là đã biết, tức là số cụm là tham biến của thuật toán. Có thuật toán lại cần các tham biến khác. Có tập dữ liệu chứa các cụm hình cầu, hình elipsoid hoặc là tập lồi; nhưng cũng có tập chứa các cụm như các đám mây hình dáng đa dạng, và “độ đậm đặc” của các đám mây cũng khác nhau, làm thế nào tìm ra các cụm như thế? Trong thực tế, tập dữ liệu có thể chứa một số rất lớn dữ liệu, có thể là tập điểm trong không gian chiều cao; đòi hỏi thuật toán phải hiệu quả kể cả trong các trường hợp đó. Có thể nói phân cụm là một vấn đề thách thức!
Sau đây chúng ta đưa ra một số định nghĩa và ký hiệu cần thiết. Mỗi đối tượng biểu diễn bởi một vector đặc trưng M thành phần X = (x1,…,xM), trong đó xi là giá trị của đặc trưng thứ i, các xi có thể là số thực hoặc rời rạc. Chúng ta sẽ giả sử tập dữ liệu gồm N dữ liệu:
D = {x1,…,xn,…,xN}, trong đó Xn= (xn1,…,xnM)
Một (cách) phân cụm của D là một họ C các tập con không rỗng Ck của D:
C={C1,…,Ck,...,CK}. Trong đó, K là số cụm (1 = 1 , với mọi n 0≤ukn≤1 và Độ đo tương tự trong phân cụm Khi chúng ta được cho tập dữ liệu, nếu định phân cụm tập dữ liệu đó, chúng
ta cần khai thác các thông tin từ tập dữ liệu đó. Một chỉ số có thể rút ra từ tập dữ
liệu đó và đóng vai trò quan trọng cho sự phân cụm là độ đo tương tự. Trong mục
này ta sẽ đưa ra cách xác định độ đo tương tự giữa hai đối tượng dữ liệu Xi và Xj,
hay ngắn gọn, độ đo tương tự giữa hai đối tượng i và j. Đối lập với độ đo tương
tự (similarity) là độ đo không tương tự (dissimilarity). Ký hiệu s(i,j) và dis(i,j) là
độ đo tương tự và không tương tự giữa hai đối tượng i và j tương ứng. Độ đo
tương tự (không tương tự) cần phải là một số không âm và đối xứng, tức là s(i,j)
= s(j,i) (dis(i,j) = dis(j,i)). Độ đo tương tự (không tương tự) giữa hai đối tượng
càng lớn thì chúng được xem là càng tương tự (càng không tương tự) với nhau.
Giả thiết mỗi dữ liệu là một vector gồm M thành phần X = (x1,…,xM), thành phần
xi là giá trị của thuộc tính thứ i của đối tượng, một thuộc tính có thể là biến liên
tục (nhận các giá trị thực), chẳng hạn thuộc tính chiều cao, cân nặng; có thể là
biến rời rạc (chỉ nhận một số hữu hạn giá trị), chẳng hạn thuộc tính màu sắc của
đối tượng; trường hợp riêng của biến rời rạc là biến nhị phân (chỉ nhận một trong
hai giá trị), chẳng hạn các thuộc tính giới tính, có bệnh, hút thuốc. Dữ liệu nhị
phân (rời rạc, liên tục) được hiểu là dữ liệu mà tất cả các thành phần của nó đều
là các giá trị nhị phân (rời rạc, liên tục). Một số phương pháp phân cụm Cho đến nay, các nhà nghiên cứu đã đề xuất một số đối tượng lớn các thuật
toán phân cụm. Mục này sẽ trình bày một số thuật toán phân cụm quan trọng nhất
từ cổ điển đến hiện đại. Các thuật toán được sắp xếp thành các nhóm theo phương
pháp phân cụm: phân cụm phân hoạch (partitioning clustering/optimization
clustering), phân cụm phân cấp (hierarchical clustering), phân cụm dựa vào mật
độ (density-based clustering), phân cụm dựa vào mô hình (model-based
clustering), và phân cụm dựa vào đồ thị (graph-based clustering). Không như
trong phân lớp, việc đánh giá tính xác thực (valiadation) của phân cụm là phức
tạp hơn nhiều. 1.3.1. Thuật toán K-Means. Thuật toán phân cụm K-Means ra đời cách đây hơn 40 năm
(MacQueen,1967), nhưng vẫn còn là một trong các thuật toán phân cụm quan
trọng nhất, được sử dụng rộng rãi trong nhiều lĩnh vực. Ý tưởng của K-Means là
tìm phân hoạch cho cực tiểu hàm tiêu chuẩn (1.27) bằng kỹ thuật lặp như sau: xuất phát từ các tâm (k=1,…, K) được khởi tạo ban đầu, ta thực hiện phép lặp: nhất, sau đó tính gán mỗi dữ liệu Xn (n=1,…,N) vào cụm Ck mà Xn gần tâm lại tâm của các cụm Ck theo công thức (1.26). Thuật toán K-Means Khởi tạo các tâm cụm (k=1,…K); Lặp lại các bước sau cho tới khi các tâm cụm không thay đổi 1. Gán mỗi dữ liệu Xn (n=1,…, N) vào cụm Ck mà Xn gần tâm nhất; 2. Tính lại tâm (k=1,…, K) của các cụm Ck thu được từ bước 1; nhiên. Tâm Thuật toán lặp trên cho ra phân hoạch C là cực tiểu địa phương của hàm tiêu
chuẩn (1.27). Chứng minh điều đó bằng cách chỉ ra rằng, cả hai bước lặp đều làm
giảm giá trị hàm tiêu chuẩn. Đối với bước 1, hàm mục tiêu (1.27) giảm là hiển
của cụm Ck được tính theo công thức (1.26) trong bước 2 chính là giá trị mà tại đó nhỏ nhất, và vì vậy bước 2 cũng làm giảm giá trị hàm tiêu chuẩn. Độ phức tạp tính toán của thuật toán này là O(TKN), trong đó N là số
dữ liệu, K là số cụm, T là số lần lặp. Trong thực tế, số lần lặp T nói chung nhỏ
hơn số dữ liệu N. Kết quả chạy K-Means phụ thuộc vào các tâm được khởi tạo ban đầu. Đơn giản nhất, ta chọn (k=1,…, K) là K điểm khác nhau được lấy ngẫu nhiên trong tập dữ liệu D. Thuật toán K-Means thích hợp với các tập dữ liệu có các cụm dạng “hình
cầu” và tách biệt tốt, chẳng hạn tập dữ liệu trong hình 1.5a. Khi mà các cụm có
dạng “không hình cầu”, chẳng hạn 2 cụm trong hình 1.6a, hình 1.6b, hoặc mật độ trong các cụm rất khác nhau hoặc số dữ liệu trong các cụm rất khác nhau, trong
các hoàn cảnh đó, K-Means có thể cho ra phân cụm không sát thực tế. Thuật toán
K-Means cũng nhạy cảm với dữ liệu ngoại lai. Nhược điểm chính của K-Means và của các thuật toán phân cụm tối ưu khác
là cần phải biết trước số cụm K. Thuật toán K-Means cũng rất nhạy cảm với các
tâm cụm khởi tạo. Mặc dù có các hạn chế đó, nhưng K-Means là thuật toán rất
đơn giản, rất hiệu quả trong thực tế, và vì vậy K-Means vẫn là một trong các thuật
toán phân cụm quan trọng nhất. (a) (b) Hình 1.6. Các tập dữ liệu không thích hợp với K-Means. 1.3.2. Phân cụm phân cấp Các phương pháp phân cụm tối ưu (phân cụm phân hoạch) cho ra phân cụm
là một phân hoạch tối ưu theo một hàm tiêu chuẩn nào đó. Tuy nhiên, trong nhiều
hoàn cảnh, một cụm lại chứa các cụm con, các cụm con này lại chứa các cụm con
nhỏ hơn,… Điều đó dẫn đến cách tiếp cận phân cụm như sau. Quá trình phân cụm
tạo thành một dãy các mức. Đầu tiên (mức 1), mỗi điểm dữ liệu tạo thành một
cụm, và do đó ở mức 1 có N cụm (tập dữ liệu D có N điểm). Ở mức 2, ta chọn hai
cụm ở mức 1 gộp lại thành một cụm, và do đó mức 2 có N – 1 cụm. Cứ thế tiếp
tục, chọn hai cụm ở mức k – 1 gộp lại để tạo thành một cụm ở mức k. Số cụm ở
mức k là N – k + 1. Cuối cùng ở mức N, toàn bộ tập dữ liệu ở trong một cụm. Quá trình trên có thể biểu diễn dưới dạng cây như trong hình 1.7a, hoặc dưới dạng biểu
đồ Venn như trong hình 1.7b. Quá trình phân cụm trên được gọi là phân cụm phân
cấp gộp (agglomerative hierarchical cluster), đó là thủ tục bottom-up. Đối lập
với phân cụm phân cấp gộp là phân cụm phân cấp chia (divisive hierarchical
clustering). Đó là thủ tục top-down. Đầu tiên (ở mức 1), toàn bộ tập dữ liệu thuộc
cùng một cụm. Sau đó ở các mức tiếp theo ta chọn một cụm và chẻ nó ra thành
hai cụm. Cuối cùng ở mức N, ta thu được N cụm, mỗi cụm chứa đúng một dữ
liệu, như được chỉ ra hình 1.7a. (a) (b) Hình 1.7 Phân cụm phân cấp tập dữ liệu D={a,b,c,d,e} Phần lớn các thuật toán phân cụm phân cấp thuộc phạm trù phân cụm phân
cấp gộp. Mục này sẽ trình bày một vài thuật toán đó. Trước hết ta cần trả lời được
câu hỏi, ở mỗi bước làm thế nào chọn ra được hai cụm để gộp chúng thành một
cụm? Chúng ta sẽ xác định khoảng cách giữa hai cụm. Khi đã lựa chọn một
khoảng cách, thì hai cụm được chọn là hai cụm gần nhau nhất theo khoảng cách
đã chọn. Khoảng cách giữa hai cụm. Giả sử Ckvà Cl là hai cụm, và dis(X, X’) là độ
đo không tương tự giữa hai điểm X và X’. Sau đây là một số độ đo khoảng cách
thông dụng nhất. Dmin (Ck, Cl) = (1.4) Dmax (Ck, Cl) = (1.5) (1.6) Davg (Ck, Cl) = Trong đó Nk , Nl là số điểm dữ liệu của cụm Ck, Cl tương ứng. Với các dữ liệu liên tục, còn có thể sử dụng khoảng cách sau: (1.7) Dmin (Ck, Cl) = Trong đó, mk và mllà tâm của cụm Ck và Cltương ứng. 1.3.3. Phân cụm dựa vào mật độ Phương pháp phân cụm dựa vào mật độ (density-based clustering) xuất phát
từ quan niệm các cụm như là các vùng mật độ cao được tách bởi các vùng mật độ
thấp. Phân cụm dựa vào mật độ cho phép ta tìm ra các cụm có hình dạng bất kỳ
trong tập dữ liệu chiều cao và có chứa các điểm dữ liệu nhiễu (ngoại lai). Các
thuật toán phân cụm dựa vào mật độ đều có chung ý tưởng là, phát triển các vùng
mật độ cao để nhận được các cụm. Các thuật toán đó chứa đựng hai điểm chính:
Đánh giá mật độ của các điểm để tìm các điểm mật độ cao, và xác định sự kết nối
bởi mật độ giữa các điểm để tạo thành các cụm. Đánh giá mật độ được thực hiện
dựa vào hai cách tiếp cận: láng giềng gần nhất và đánh giá mật độ nhân. Sau đây
chúng ta trình bày hai thuật toán quan trọng trong số nhiều thuật toán phân cụm
dựa vào mật độ đã được đề xuất: DBSCAN và MEAN-SHIFT. Thuật toán
DBSCAN sử dụng cách đánh giá mật độ láng giềng gần nhất, còn MEAN-SHIFT
sử dụng cách đánh giá mật độ nhân. 1.3.4. Phân cụm dựa vào mô hình Phân cụm dựa vào mô hình (model-base clustering)xuất phát từ ý tưởng
cho rằng, mỗi cụm dữ liệu được sinh ra bởi một phân phối xác suất nào đó. Ta giả
sử tập dữ liệu D = {X1,…,XN} có K cụm: c1,…,cK, chúng ta xem rằng, cụm thứ k
(k = 1,…,K) được sinh ra bởi hàm mật độ xác suất pK(X/𝜃𝐾), trong đó 𝜃𝐾 là véctơ
tham biến của phân phối, và toàn bộ tập dữ liệu D được sinh ra bởi hàm mật độ 𝐾
𝐾=1 (1.8) 𝑝(𝑋) = ∑ 𝜋𝐾𝑝𝐾 (𝑋 ⁄ )
𝜃𝐾 𝐾
𝐾=1 Trong đó, 𝜋𝐾 là các hệ số sao cho 𝜋𝐾 ≥ 0 và ∑ 𝜋𝐾 𝐾 𝐾 = 1. Hàm mật độ
(1.53) được gọi là mật độ hỗn hợp (finite mixture density). Có thể xem mật độ
hỗn hợp như mô hình biến ẩn. Ta đưa vào các biến ẩn z nhận K giá trị là các nhãn
cụm c1,…,cK, nó nhận giá trị cK nếu dữ liệu thuộc cụm cK. Khi đó, mật độ sinh ra
tập dữ liệu có thể biểu diễn thành: 𝐾=1 𝐾=1 (1.9) 𝑝(𝑋) = ∑ 𝑃(𝑧 = 𝑐𝐾)𝑝(𝑋 𝑧⁄ = 𝑐𝐾) = ∑ 𝑃(𝑐𝐾)𝑝(𝑋 𝑐𝐾⁄ ) còn 𝑝𝐾(𝑋 Như vậy, 𝜋𝐾 = P(cK) = P(z = cK) là xác suất để một dữ liệu thuộc cụm cK;
𝑧⁄ = 𝑐𝐾) là phân phối xác suất của các dữ liệu 𝑐𝐾⁄ )= 𝑝(𝑋 ⁄ )= 𝑝(𝑋
𝜃𝐾 thuộc cụm cK, ta gọi là phân phối thành phần thứ k của phân phối hỗn hợp. Nếu
chúng ta biết mật độ hỗn hợp sinh ra tập dữ liệu, thì từ công thức Bayes ta có: 𝐾
𝐾=1 𝜋𝐾𝑝𝐾(𝑋 (1.10) 𝑐𝐾 𝑃( 𝑋⁄ ) = ∑ ⁄ )
𝜃𝐾
𝜋𝐾𝑝𝐾(𝑋 ⁄ )
𝜃𝐾 Đây là xác suất để dữ liệu X thuộc cụm cK. Ta đặt 𝑐𝐾 (1.11) 𝑝𝑘𝑛 = 𝑃 ( ⁄ ) (𝐾 = 1, … , 𝐾; 𝑛 = 1, … , 𝑁)
𝑋𝑛 Bởi vì pkn là xác suất để dữ liệu Xnthuộc cụm cK, do đó {pkn} xác định một phân cụm mềm của tập dữ liệu D. Khi các phân phối thành phần là phân phối Gaus, ta có mô hình hỗn hợp
Gaus. Giả sử phân phối thành phần thứ k là phân phối Gaus với kỳ vọng 𝜇𝑘 và ma
trận covariance Σ𝑘: N(X/𝜇𝑘, Σ𝑘), khi đó phân phối hỗn hợp Gaus có dạng: 𝐾
𝐾=1 𝑝(𝑋 𝜃⁄ ) = ∑ 𝜋𝐾 𝑁(𝑋 𝜇𝑘,⁄ Σ𝑘) (1.12) Trong đó, 𝜃 = (𝜋, 𝜇, Σ) với 𝜋 = (𝜋1, … , 𝜋𝑘); 𝜇 = (𝜇1, … , 𝜇𝐾); Σ = (Σ1, … , Σ𝐾) là tham biến của phân phối. Phân phối hỗn hợp Gaus
được phổ biến rộng rãi nhất cho mục đích phân cụm dữ liệu. Khi đã lựa chọn hỗn hợp Gaus, chúng ta cần đánh giá vectơ tham biến 𝜃 = (𝜋, 𝜇, Σ) từ tập dữ liệu. Có nhiều cách tiếp cận để đánh giá các tham biến của hỗn hợp Gaus, phổ biến nhất
vẫn là thuật toán EM. Thuật toán EM cho phân cụm
Inputs:Tập dữ liệu D = {X1,…,XN}; số cụm K;
Outputs: phân cụm mềm {pkn/K = 1,…,K; n = 1,…,N}
Khởi tạo các tham biến 𝜋 = (𝜋1, … , 𝜋𝑘); 𝜇 = (𝜇1, … , 𝜇𝐾); Σ = (Σ1, … , Σ𝐾); (Bước lặp) thực hiện hai bước sau cho tới khi hội tụ: Bước E: ∑ 𝜋𝐾 Σ𝑘) 𝜋𝐾𝑁(𝑋 𝜇𝑘,
Σ𝑘)
⁄
𝐾
⁄
𝐾=1 𝑁(𝑋 𝜇𝑘, (1.13) 𝑝𝑘𝑛 ← 𝑃(𝑐𝐾 𝑋⁄ , 𝜃) = (𝑘 = 1, … , 𝐾; 𝑛 = 1, … , 𝑁) Bước M: 𝑁
𝑛=1 (1.14) 𝑁𝐾 ← ∑ 𝑝𝑘𝑛 𝑁𝑘
𝑁 ∑ 𝑋𝑛 𝑁
𝑛=1 (1.15) (𝐾 = 1, … , 𝐾) 𝜋𝑘 ← 𝑝𝑘𝑛
𝑁𝑘 (1.16) (𝐾 = 1, … , 𝐾) 𝜇𝑘 ← 𝑁
𝑛=1 1
𝑁𝑘 ∑ (1.17) Σ𝑘 ← 𝑝𝑘𝑛 (𝑋𝑛 − 𝜇𝑘)′(𝑋𝑛 − 𝜇𝑘) (𝑘 = 1, … , 𝐾) Trong phân cụm dựa vào mô hình hỗn hợp Gaus, hình dạng và kích cỡ của các cụm phụ thuộc vào ma trận convariance Σ𝑘. Cũng như K-Means, nhượcđiểm lớn nhất của phân cụm dựa vào mô hình
hỗn hợp Gaus là ta cần biết trước số cụm K, và kết quả phụ thuộc vào việc khởi
tạo các tham biến ban đầu. Tuy nhiên, với phân cụm dựa vào mô hình hỗn hợp
Gaus thì việc lựa chọn số cụm K có thể quy về việc lựa chọn mô hình, và cụ thể
là sử dụng tiêu chuẩn thông tin Bayes BIC, ta sẽ chọn K cho BIC lớn nhất. Cũng
cần lưu ý rằng, ngoài mô hình hỗn hợp Gaus, một số mô hình hỗn hợp khác đã
được đề xuất. 1.3.5. Phân cụm dựa vào đồ thị Đã có nhiều công trình lý thuyết và nhiều thuật toán phân cụm theo phương pháp phân cụm dựa vào đồ thị (graph-based clustering). Phương pháp luận phân cụm dựa vào đồ thị: Giả sử chúng ta cần phân cụm tập dữ liệu D = {X1,…,XN}. Từ tập dữ liệu
này, chúng ta xây dựng ma trận tương tự S = (sij), ma trận vuông cấp N, trong đó
sij là độ đo tương tự giữa Xi và Xj. Đồ thị là mô hình toán học rất thích hợp để
biểu diễn tập dữ liệu D. Chúng ta sẽ biểu diễn tập dữ liệu D bởi đồ thị vô hướng
có trọng số G = (V, E, W), trong đó V là tập đỉnh của đồ thị, mỗi đỉnh biểu diễn
một dữ liệu, V = {1,…,N}, đỉnh n (n = 1,…,N) biểu diễn dữ liệu Xn, tập các cạnh
của đồ thị là E, mỗi cạnh (i,j) ∈ E có trọng số là wij, trọng số này là độ đo tương
tự sij, và W là ma trận các trọng số wij đó. Đồ thị G đó được gọi là đồ thị tương tự. 1.4. Tiểu kết chương 1. Trong chương này, luận văn đã trình bày nghiên cứu tổng quan về các
phương pháp tra cứu ảnh dựa vào nội dung đã được nghiên cứu và công bố trong
các công trình khác nhau trong nước và trên thế giới bao gồm phân đoạn ảnh, trích
rút đặc trưng, độ đo tương tự … Chương 1 cũng tập trung vào nghiên cứu tra cứu ảnh sử dụng phản hồi liên
quan và vấn đề phân cụm, trên cơ sở đó làm tiền đề cho các đề xuất được đề cập
đến trong chương 2 của luận văn với hy vọng nâng cao chất lượng tra cứu ảnh dựa
vào nội dung. CHƯƠNG 2: PHƯƠNG PHÁP TRA CỨU ẢNH VỚI PHẢN HỒI LIÊN QUAN SỬ DỤNG PHÂN CỤM GIA TĂNG 2.1. Tra cứu ảnh với ngữ nghĩa mức cao 2.1.1. Giới thiệu về tra cứu ảnh với ngữ nghĩa mức cao Thông tin trực quan đã trở thành một yếu tố quan trọng trong tất cả khía cạnh của xã hội. Dữ liệu trực quan lớn thu hút nhiều nhà nghiên cứu tập trung vào các vấn đè làm thế nào lưu trữ, truy cập, biểu diễn, mô tả, tra cứu nội dung của nó thật hiệu quả. Nghiên cứu trong tra cứu ảnh dựa vào ngữ nghĩa có liên quan tới các chủ đề như tri thức và hành vi của con người, đánh chỉ số và tra cứu trên dữ liệu phân tán, đánh chỉ số và tra cứu trên dữ liệu lớn, khai phá thông tin dựa vào đánh chỉ số, phương pháp tiếp cận máy học, giải thích ngữ nghĩa mức cao, tương tác giữa người và máy, nhận dạng đối tượng, phản hồi liên quan, mô hình ngữ nghĩa cho tra cứu, biểu diễn và mô tả ngữ nghĩa. Khoảng cách ngữ nghĩa giữa ngữ nghĩa thật và cảm quan nhận thức thu hút được nhiều nhà nghiên cứu.. Khoảng cách ngữ nghĩa định nghĩa theo Smeulders như sau: “Khoảng cách ngữ nghĩa là sự không tương đồng giữa thông tin ản được trích rút ra từ dữ liệu trực quan so với diễn giải về dữ liệu ảnh đó bởi người dùng trong tình huống cụ thể”. Tra cứu ảnh ngữ nghĩa cố gắng trích rút khái niệm nhận thức của người dùng bằng cách kết hợp các đặc trưng trực quan mức thấp theo một cách nào đó. Tìm kiếm ảnh liên quan ngữ nghĩa trong các hệ thống tra cứu ảnh dựa vào nội dung đề cập đến việc tìm kiếm các ảnh mà theo suy nghĩ của người dùng là có liên quan với nhau về mặt ngữ nghĩa chẳng hạn như các ảnh hoa hồng có màu vàng và màu đỏ là có liên quan ngữ nghĩa với nhau. Sự phát triển tích cực của các phương pháp tra cứu ảnh ngữ nghĩa được thực hiện nhằm rút ngắn khoảng cách ngữ nghĩa giữa đặc trưng trực quan mức thấp và mô tả ngữ nghĩa mức cao. Các kỹ thuật trong việc rút ngắn “khoảng cách ngữ nghĩa” gồm có 5 loại chính: (1) sử dụng bản thể đối tượng để xác định các khái niệm mức cao, (2) sử dụng các công cụ học máy để kết hợp các đặc trưng mức thấp với các khái niệm truy vấn, (3) đưa phản hồi liên quan vào lặp tra cứu cho học ý định của người dùng, (4) sinh ra mẫu ngữ nghĩa để hỗ trợ tra cứu ảnh mức cao, (5) Cách sử dụng cả nội dung trực quan của các ảnh và thông tin văn bản thu được từ Web cho tra cứu ảnh trên Web. 2.1.2. Khoảng cách ngữ nghĩa Thuật ngữ “khoảng trống ngữ nghĩa” được dùng để miêu tả sự khác nhau giữa hai mức miêu tả của một ảnh. Mức miêu tả đầu trong CBIR sử dụng các vector đặc trưng miêu tả đặc trưng mức thấp của ảnh (mầu sắc, kết cấu, hình dạng,…). Mức miêu tả thứ hai được thực hiện bởi con người sử dụng các khái niệm ngữ nghĩa mức cao khi tra cứu ảnh. Các kỹ thuật hiện đại để giảm khoảng cách ngữ nghĩa có thể phân loại theo nhiều cách khác nhau. Ví dụ, xem xét các ứng dụng, các kỹ thuật có thể phân chia thành các nhóm: tra cứu tác phẩm nghệ thuật, tra cứu hình ảnh phong cảnh , tra cứu ảnh web…Luận văn tập trung vào các kỹ thuật được sử dụng để lấy được ngữ nghĩa mức cao và chia thành 5 loại sau: (1) sử dụng bản thể đối tượng để định nghĩa khái niệm ngữ nghĩa (2) sử dụng phương pháp học có giám sát hoặc không giám sát để liên kết các đặc trưng mức thấp với khái niệm truy vấn. (3) Đưa RF vào vòng lặp để học nhu cầu của người dùng (4) Sinh ra ST để hỗ trợ tra cứu ngữ nghĩa mức cao (5) Sử dụng cả thông tin thu được từ Web và nội dung trực quan của ảnh đối với tra cứu ảnh Web. Rất nhiều hệ thống khai thác một hoặc nhiều kỹ thuật để thực hiện tra cứu ảnh dựa vào ngữ nghĩa mức cao. Ví dụ, (3) thường được kết hợp với (1), (2) hoặc (5), hoặc (5) thường được kết hợp với bốn kỹ thuật khác. 2.1.3. Phản hồi liên quan Phản hồi liên quan là một quá trình trực tuyến mà cố gắng học mục đích của người dùng trong quá trình và là một công cụ mạnh được sử dụng truyền thống trong các hệ thống tra cứu thông tin. Nó được giới thiệu đối với CBIR khoảng đầu những năm 1990, với mục đích mang người dùng vào lặp tra cứu để giảm khoảng cách ngữ nghĩa giữa những gì mà truy vấn biểu diễn và những gì người dùng nghĩ. Bằng việc tiếp tục học thông qua tương tác với các người dùng cuối, phản hồi liên quan đã được chỉ ra là cung cấp cải tiến hiệu năng đáng kể trong các hệ thống CBIR. Thực hiện phản hồi liên quan đề cập đến việc tính toán một hoặc nhiều điểm truy vấn mới trong không gian đặc trưng và thay đổi hàm khoảng cách. Hình 2.1. Dịch chuyển điểm truy vấn. Hình 2.2. Hình dạng lồi (đa điểm). Hình 2.3. Hình dạng lõm (đa điểm). 2.2. Tra cứu ảnh với phản hồi liên quan Một viễn cảnh tiêu biểu cho RF trong CBIR là như sau: (1) Hệ thống cung cấp các kết quả tra cứu khởi tạo thông qua truy vấn bởi mẫu, phác thảo,… (2) Người dùng đánh giá các kết quả trên là có liên quan đến ảnh truy vấn hay không và độ liên quan là bao nhiêu. (3) Thuật toán học máy được áp dụng để học phản hồi của người dùng. Sau đó quay về bước (2). (2)-(3) được lặp cho đến khi người dùng thỏa mãn với các kết quả. Hình 1 Lặp phản hồi Truy vấn người dùng khởi tạo
(ảnh mẫu hoặc từ khóa) Các kết quả tra cứu Phản hồi người dùng Cơ sở dữ
liệu ảnh Các mẫu được gán nhãn (các
ảnh liên quan hay không) Học (điều chỉnh các tham số
truy vấn) Các kết quả tra cứu cuối cùng chỉ ra một lược đồ đơn giản của một hệ thống CBIR với phản hồi liên quan. Hình 2.4. Tra cứu ảnh dựa vào nội dung với phản hồi liên quan. 2.3. Kỹ thuật phân tích phân biệt tuyến tính (LDA-Linear Discriminant
Analysis) 2.3.1. Định nghĩa về LDA Mục tiêu của kỹ thuật LDA là chiếu ma trận dữ liệu gốc lên không gian chiều
thấp hơn. Để đạt được mục tiêu này, ba bước cần được thực hiện. Bước đầu tiên
là tính sự tách biệt giữa các lớp (tức khoảng cách giữa các kỳ vọng của các lớp
khác nhau), được gọi là “phương sai between-class” hoặc “ma trận between-
class”. Bước thứ hai là tính khoảng cách giữa kỳ vọng và các mẫu của mỗi lớp,
được gọi là “phương sai within-class” hoặc “ma trận within-class”. Bước ba là
xây dựng không gian chiều thấp mà cực đại “phương sai between-class” và cực
tiểu “phương sai within-class”. Tiếp theo, luận văn giải thích ba bước này một
cách chi tiết và sau đó mô tả đầy đủ thuật toán LDA. Hình 1 và 2 được sử dụng
để trực quan các bước của kỹ thuật LDA. 2.3.2 Tính toán phương sai between-class (𝑺𝑩) 3
𝑖=1 . Phương sai between-class của lớp thứ i (𝑆𝐵𝑖) biểu diễn khoảng cách giữa kỳ
vọng của lớp thứ i (𝜇𝑖) và kỳ vọng trung bình (𝜇). Kỹ thuật LDA tìm một không
gian chiều thấp, được sử dụng để cực đại hóa phương sai between-class, hoặc cực
đại khoảng cách tách biệt giữa các lớp. Để giải thích phương sai between-class
hoặc ma trận between-class (𝑆𝐵) có thể được tính như thế nào, các giải thiết sau
đây được đưa ra. Ma trận dữ liệu gốc 𝑋 = {𝑥1, 𝑥2, … 𝑥𝑁}, ở đây 𝑥𝑖 biểu diễn mẫu
thứ i hoặc quan sát và N là tổng số các mẫu. Mỗi mẫu được biểu diễn bởi M đặc
trưng (𝑥𝑖 ∈ 𝑅𝑀). Nói cách khác, mỗi mẫu được biểu diễn bằng một điểm trong
không gian M chiều. Giả sử ma trận dữ liệu được phân hoạch thành c=3 lớp như
sau, 𝑋 = (𝜔1, 𝜔2, 𝜔3) như hình 2.5 bước A dưới đây. Mỗi lớp có 5 mẫu (tức
𝑛1 = 𝑛2 = 𝑛3 = 5), ở đây 𝑛𝑖 biểu diễn số các mẫu của lớp thứ i. Tổng số mẫu
(N) được tính như sau: 𝑁 = ∑ 𝑛𝑖 Để tính phương sai between-class (𝑆𝐵), khoảng cách tách biệt giữa các lớp khác nhau, được biểu thị bởi (𝑚𝑖 − 𝑚) sẽ được tính như sau: (𝑚𝑖 − 𝑚)2 = (𝑊𝑇𝜇𝑖 − 𝑊𝑇𝜇)2 = 𝑊𝑇(𝜇𝑖 − 𝜇)(𝜇𝑖 − 𝜇)𝑇𝑊 (1) Hình 2.5. Các bước được trực quan hóa để tính một không gian con chiều thấp
hơn của kỹ thuật LDA. Ở đây 𝑚𝑖 biểu diễn chiếu của kỳ vọng của lớp thứ i và nó được tính như sau,
𝑚𝑖 = 𝑊𝑇𝜇𝑖, ở đây 𝑚 là chiếu của tổng kỳ vọng của tất cả các lớp và nó được tính như sau 𝑚 = 𝑊𝑇𝜇, 𝑊 biểu diễn ma trận biến đổi của LDA, 𝜇𝑖(1 × 𝑀) biểu diễn
kỳ vọng của lớp thứ i và nó được tính như trong phương trình (2), và 𝜇(1 × 𝑀)
là tổng kỳ vọng của tất cả các lớp và nó có thể được tính như trong phương trình
(3). Hình 2.1 chỉ ra kỳ vọng của mỗi lớp và tổng kỳ vọng trong Bước (B) và (C)
tương ứng. 𝑥𝑖∈𝑤𝑗 1
𝑛𝑗 1 ∑ (2) 𝜇𝑗 = 𝑥𝑖 𝑖=1 = ∑ 𝑛𝑖
𝑁
∑ 𝑥𝑖 𝑐
𝑖=1 𝑁 𝑁 (3) 𝜇 = 𝜇𝑖 ở đây c biểu diễn tổng số các lớp (trong ví dụ c=3). Số hạng (𝜇𝑖 − 𝜇)(𝜇𝑖 − 𝜇)𝑇 trong phương trình (1) biểu diễn khoảng cách
tách biệt giữa kỳ vọng của lớp thứ i (𝜇𝑖) và tổng kỳ vọng (𝜇), hoặc đơn giản nó
biểu diễn phương sai between-class của lớp thứ i (𝑆𝐵𝑖). Thay thế 𝑆𝐵𝑖 trong phương
trình (1) như sau: (𝑚𝑖 − 𝑚)2 = 𝑊𝑇𝑆𝐵𝑖𝑊 (4) 𝑐
𝑖=1 . Hình Tổng phương sai between-class được tính như sau, 𝑆𝐵 = ∑ 𝑛𝑖𝑆𝐵𝑖
2.5 (bước D) chỉ ra đầu tiên ma trận between-class của lớp đầu tiên (𝑆𝐵1) được
tính như thế nào và sau đó ma trận tổng between-class (𝑆𝐵) được tính bằng cộng
tổng tất cả các ma trận between-class của tất cả các lớp như thế nào. 2.3.3 Tính phương sai within-class (𝑺𝒘) Phương sai within-class của lớp thứ i 𝑆𝑊𝑖 biểu diễn sự khác nhau giữa kỳ
vọng và các mẫu của lớp đó. Kỹ thuật LDA tìm kiếm một không gian chiều thấp,
được sử dụng để cực tiểu sự khác nhau giữa kỳ vọng được chiều (𝑚𝑖) và các mẫu
chiếu của mỗi lớp (𝑊𝑇𝑥𝑖), hoặc cực tiểu phương sai within-class. Phương sai
within-class (𝑆𝑊𝑖) được tính như trong phương trình (5). 𝑥𝑖∈𝑤𝑗,𝑗=1,..𝑐 ∑ (𝑊𝑇𝑥𝑖 − 𝑚𝑗)2 𝑥𝑖∈𝑤𝑗,𝑗=1,..𝑐 = ∑ (𝑊𝑇𝑥𝑖𝑗 − 𝑊𝑇𝜇𝑗)2 𝑥𝑖∈𝑤𝑗,𝑗=1,..𝑐 = ∑ 𝑊𝑇(𝑥𝑖𝑗 − 𝜇𝑗)2𝑊 𝑥𝑖∈𝑤𝑗,𝑗=1,..𝑐 = ∑ 𝑊𝑇(𝑥𝑖𝑗 − 𝜇𝑗)(𝑥𝑖𝑗 − 𝜇𝑗)𝑇𝑊 𝑥𝑖∈𝑤𝑗,𝑗=1,..𝑐 (5) = ∑ 𝑊𝑇𝑆𝑊𝑗𝑊 𝑇 ∗ 𝑑𝑗 = ∑ (𝑥𝑖𝑗 − 𝜇𝑗)(𝑥𝑖𝑗 − 𝜇𝑗)𝑇 𝑛𝑗
𝑖=1 Từ phương trình (5), phương sai within-class cho mỗi lớp có thể được tính 3 , ở đây 𝑥𝑖𝑗 biểu diễn mẫu
như sau, 𝑆𝑊𝑖 = 𝑑𝑗
thứ i trong lớp thứ j như được chỉ ra trong Hình 2.1 (bước E, F), và 𝑑𝑗 là dữ liệu
𝑛𝑗 − 𝜇𝑗. Hơn nữa, bước (F) trong
tâm của lớp thứ j, tức là 𝑑𝑗 = 𝜔𝑗 − 𝜇𝑗 = {𝑥𝑖}𝑖=1
Hình minh họa phương sai within-class của lớp thứ nhất (𝑆𝑊1) trong ví dụ được
tính như thế nào. Tổng phương sai within-class biểu diễn tổng tất cả các ma trận
within-class của tất cả các lớp (xem Hình 2.5 (bước F), và nó có thể được tính như
phương trình (6). 𝑖=1 𝑆𝑊 = ∑ 𝑆𝑊𝑖 ∑ (𝑥𝑖 − 𝜇1)(𝑥𝑖 − 𝜇1)𝑇
𝑥𝑖∈𝑤1 𝑥𝑖∈𝑤2 + ∑ (𝑥𝑖 − 𝜇2)(𝑥𝑖 − 𝜇2)𝑇 𝑥𝑖∈𝑤3 (6) + ∑ (𝑥𝑖 − 𝜇3)(𝑥𝑖 − 𝜇3)𝑇 2.3.4 Xây dựng không gian thấp chiều Sau khi tính toán phương sai between-class (𝑆𝐵) và phương sai within-class
(𝑆𝑊), ma trận biến đổi 𝑊 của kỹ thuật LDA có thể được tính như trong phương
trình (7), được gọi là tiểu chuẩncủa Fisher. Công thức này có thể được phát biểu
như trong phương trình (8). 𝑊𝑇𝑆𝐵𝑊
𝑊𝑇𝑆𝑊𝑊 (7) argmax
𝑊 −1𝑆𝐵, nếu 𝑆𝑊 khả nghịch. 𝑆𝐵𝑊 = 𝜆𝑆𝑊𝑊 (8) ở đây 𝜆 biểu diễn các giá trị riêng của ma trận biến đổi (𝑊). Nghiệm của bài
toán này có thể thu được bởi tính toán các giá trị riêng 𝜆 = {𝜆1, 𝜆2, … 𝜆𝑀} và các
véc tơ riêng 𝑉 = {𝑣1, 𝑣2, … 𝑣𝑀} của ma trận 𝑆𝑊 Các giá trị riêng là các giá trị vô hướng, trong khi các véc tơ riêng là các véc
tơ khác không, thỏa mãn phương trình (8) và cung cấp cho chúng ta thông tin về
không gian LDA. Các véc tơ riêng biểu diễn các hướng của không gian mới , và
các giá trị riêng tương ứng biểu diễn nhân tố tỉ lệ, độ dài hoặc độ lớn của các véc
tơ riêng. Bởi vậy, mỗi véc tơ riêng biểu diễn một trục của không gian LDA, và
giá trị riêng kết hợp biểu diễn độ mạnh của véc tơ riêng này. Độ mạng của véc tơ
riêng phản ánh khả năng phân biệt giữa các lớp của nó, tức là tăng phương sai
between-class, và giảm phương sai within-class của mỗi lớp; do đó đạt được mục
tiêu LDA. Bởi vậy, các véc tơ riêng với k giá trị riêng lớn nhất được sử dụng để
xây dựng một không gian thấp chiều (𝑉𝑘), trong khi các véc tơ riêng khác
({𝑣𝑘+1, 𝑣𝑘+2, . . 𝑣𝑀}) bị loại đi như được chỉ ra trong Hình 2.5 (Bước G). Hình 2.2 chỉ ra không gian chiều thấp hơn của kỹ thuật LDA, được tính toán
như trong Hình 2.5 (Bước G). Như được chỉ ra, chiều của ma trận dữ liệu gốc
(𝑋 ∈ 𝑅𝑁×𝑀) được giảm bằng việc chiếu nó lên không gian chiều thấp hơn của
LDA (𝑉𝑘 ∈ 𝑅𝑁×𝑘) được chú thích trong phương trình (9). Chiều của dữ liệu sau
khi chiếu là k; do đó, M-k đặc trưng bị bỏ qua hoặc xóa khỏi mỗi mẫu. Do đó,
mỗi mẫu 𝑥𝑖 được biểu diễn bằng một điểm trong không gian M chiều sẽ được biểu diễn trong một không gian k chiều bởi chiếu nó lên không gian chiều thấp hơn
(𝑉𝑘) như sau, 𝑦𝑖 = 𝑉𝑘𝑥𝑖 𝑌 = 𝑋 𝑉𝑘 (9) Để dự đoán một ảnh thuộc cụm nào, chúng ta tính ma trận hiệp phương sai 1 gộp chung C, tính theo công thức: 𝑔
∑ 𝑛𝑖
𝑖=1 𝑁 𝐶(𝑟, 𝑠) = 𝑐(𝑖)(𝑟, 𝑠) P là véc tơ xác suất tiền nghiệm 𝑃 = [𝑝1 … , 𝑝𝑔] 𝑇 với 𝑝𝑖 biểu diễn xác suất
tiền nghiệm của cụm i. Ở đây, do không biết xác suất tiền nghiệm nên chúng ta
lấy bằng số phần tử trong mỗi cụm chia cho tổng số phẩn tử: 𝑛𝑖
𝑁 𝑝𝑖 = 𝑇 − Đối tượng 𝑥𝑘 được gán vào cụm 𝑖 nếu hàm 𝑓𝑖 đạt cực đại. 𝑇 + ln(𝑝𝑖) 𝑓𝑖 = 𝜇(𝑖)𝐶−1𝑥𝑘 𝜇(𝑖)𝐶−1𝜇𝑖 1
2 2.3.5. Sơ đồ phương pháp tra cứu ảnh sử dụng phân cụm gia tăng trong phản
hồi liên quan Phương pháp tra cứu ảnh sử dụng phân cụm gia tăng được mô tả trên hình 2.6. Hình 2.6. Sơ đồ tra cứu ảnh sử dụng phân cụm gia tăng. Đầu tiên, người dùng cung cấp cho máy tìm kiếm k ảnh truy vấn. Máy tìm
kiếm thực hiện trích rút các đặc trưng của k ảnh truy vấn và đối sánh các đặc trưng
của mỗi trong k ảnh truy vấn với cơ sở dữ liệu ảnh để được k kết quả tra cứu. Gộp
k kết quả tra cứu để được một tập kết quả. Trên tập kết quả, người dùng đánh dấu
một số ảnh là liên quan hay không liên quan để được tập phản hồi. Nếu là lần tra
cứu khởi tạo, hệ thống phân các ảnh trong tập phản hồi t hành M cụm để có được
tập ví dụ huấn luyện. Do đây là lần tra cứu khởi tạo, gia tăng cụm sẽ lấy chính tập
huấn luyện làm đầu ra của thủ tục gia tăng cụm, tức là có M cụm và số ảnh trong
mỗi cụm chưa được gia tăng. Tiếp theo, mỗi trong M cụm sẽ tìm ra một ảnh đại diện cụm. Các ảnh đại
diện của các cụm sẽ là đầu vào của máy tìm kiếm. Máy tìm kiếm thực hiện việc
tìm kiếm để cho ra tạp kết quả tương ứng với M ảnh đại diện. Sau đó, người dùng phản hồi trên tập kết quả để được tập phản hồi. Do lần tra cứu này không phải là
lần tra cứu khởi tạo nên các ảnh phản hồi sẽ được chuyển cho thủ tục Gia tăng
cụm, tức là, mỗi ảnh phản hồi sẽ được phân vào một cụm nào đó theo thủ tục Gia
tăng cụm và kết quả của thủ tục gia tăng cụm là M cụm với số lượng của mỗi cụm
có thể được tăng lên. M cụm được cung cấp cho máy tìm kiếm. Quá trình này
được lặp đi lặp lại cho đến khi người dùng ngừng phản hồi và hệ thống cho ra một
tập kết quả cuối cùng. 2.4. Tiểu kết chương 2 Trong chương này, luận văn tập trung trình bày phương pháp phương pháp
tra cứu ảnh với phản hồi liên quan sử dụng phân cụm gia tăng. Phương pháp sử
dụng một phương pháp phân cụm gia tăng lên tập ảnh mà người dùng chọn để
hình thành lên truy vấn ở lần lặp sau, và ưu điểm của phương pháp phân cụm gia
tăng là ở lần lặp tra cứu sau các ảnh phản hồi sẽ được phân vào các cụm mà không
phải thực hiện phân cụm lại. Phương pháp tra cứu được các ảnh đa dạng mà không
phải đưa vào một truy vấn phức tạp, bên cạnh đó thời gian tra cứu nhanh. CHƯƠNG 3: CHƯƠNG TRÌNH THỬ NGHIỆM 3.1. Giới thiệu bài toán tra cứu ảnh dựa vào nội dung Tra cứu ảnh dựa vào nội dung là phương pháp giúp con người tiếp cận tập
dữ liệu ảnh lớn một cách có hiệu quả nhất, từ đó cung cấp nhiều thông tin cho
người dùng hơn là văn bản. Tuy nhiên, bước chuyển từ tra cứu văn bản với mô tả
ảnh sang sử dụng một ảnh truy vấn bộc lộ nhiều hạn chế bởi vì việc sử dụng một
ảnh truy vấn không thể biểu diễn được toàn bộ nhu cầu của người dùng. Một trong
những cách khắc phục hạn chế này là sử dụng đa truy vấn, nhu cầu của người
dùng sẽ được biểu diễn bởi nhiều ảnh truy vấn đầu vào. Từ đó thông tin được cung
cấp tốt hơn cho hệ thống CBIR, giúp đa dạng hơn kết quả trả về đối với truy vấn
khởi tạo, làm đầu vào cho pha phản hồi liên quan. Phản hồi liên quan được sử dụng để học thông tin từ người dùng sau truy vấn
khởi tạo, các phương pháp phân cụm được sử dụng để giảm độ phức tạp tính toán
thông qua gom nhóm các ảnh tương tự nhau về mặt ngữ nghĩa. Trọng tâm cụm
được sử dụng làm đầu vào cho pha tra cứu kế tiếp. Việc này lặp lại đến khi nào
đạt được mong muốn của người dùng. Đối với các phương pháp phân cụm truyền thống, độ phức tạp tính toán tăng
tỉ lệ thuận với số lượng tập ảnh phản hồi từ người dùng. Phân cụm gia tăng được
đề xuất nhằm hạn chế việc này, giúp tốc độ xử lý của các hệ thống CBIR tăng lên
mà không làm giảm chất lượng tra cứu ảnh dựa vào nội dung. Chiến lược tra cứu được chúng tôi đề xuất sử dụng trong luận văn này là kết
hợp tính đa dạng trong tra cứu ảnh sử dụng đa truy vấn và học thông tin từ người
dùng thông qua phản hồi liên quan với phân cụm gia tăng LDA. Hình 3.1 cho thấy
mô hình tổng quát của hệ thống. Hình 3.1. Mô hình tổng quát của hệ thống Trong đó, n ảnh truy vấn đầu vào Q1 đến Qn được cung cấp cho hệ thống, sử
dụng cùng phương pháp trích rút đặc trưng đối với tập cơ sở dữ liệu nhận được n
vec-tơ đặc trưng, là truy vấn khởi tạo cho máy tìm kiếm CBIR. Với mỗi truy vấn
đầu vào nhận được một tập kết quả trả về, các tập này sau đó được gộp lại để được
một tập kết quả SMerge duy nhất. Thông tin phản hồi từ người dùng hay các ảnh liên quan ngữ nghĩa được
cung cấp. Hệ thống sử dụng phân cụm LDA phân tập phản hồi thành m cụm, huấn
luyện LDA cho mỗi cụm và cung cấp lại đầu vào mới cho máy tìm kiếm là đại
diện của mỗi cụm. Ở lần lặp thứ hai, hệ thống không phân cụm lại mà sử dụng gia tăng cụm LDA đã được huấn luyện để gán nhãn cho các ảnh mới phản hồi. Quá trình phản hồi này có thể lặp lại nhiều lần cho đến khi đạt được mong muốn từ người dùng. 3.2. Môi trường thực nghiệm. Trong khuôn khổ luận văn, luận văn không đề cập đến hiệu năng của các
phương pháp trích rút đặc trưng, vì vậy, tập đặc trưng ảnh được xem là sẵn có cho
pha tra cứu tiếp theo. 3.2.1. Cơ sở dữ liệu ảnh. Cơ sở dữ liệu ảnh được sưu tầm là tập con của tập Corel được sử dụng rộng
rãi trong cộng đồng nghiên cứu lĩnh vực tra cứu ảnh dựa vào nội dung. Tập ảnh
này gồm 3400 ảnh đã được phân lớp theo ngữ nghĩa từ phía người dùng. Tập này
gồm 34 loại, mỗi loại có 100 ảnh, cụ thể được cung cấp trong bảng 3.1. Tất cả các
ảnh trong tập ảnh này có tính chất là đều chứa đối tượng tiền cảnh nổi bật. Cỡ của
các ảnh có max(chiều rộng, chiều cao)=384 và min(chiều rộng, chiều cao)=256. Bảng 3.1. Bảng phân bố tập ảnh Corel STT LỚP ẢNH SỐ LƯỢNG GHI CHÚ 1 290 100 2 700 100 3 750 100 4 770 100 5 840 100 6 1040 100 7 1050 100 8 1070 100 9 1080 100 10 1090 100 11 1100 100 12 1120 100 13 1340 100 14 1350 100 15 1680 100 16 2680 100 17 2890 100 18 3260 100 19 3510 100 20 3540 100 21 3910 100 22 4150 100 23 4470 100 24 4580 100 25 4990 100 26 5210 100 27 5350 100 28 5530 100 29 5810 100 30 5910 100 31 6440 100 32 6550 100 33 6610 100 6840 100 34 3.2.2. Vec-tơ đặc trưng Các đặc trưng được chia làm hai loại là: các đặc trưng màu và các đặc trưng kết cấu (xem Bảng 3.2 ở dưới). Bảng 3.2. Các loại đặc trưng. 3.2.3. Tập tin cậy nền Tập tin cậy nền Corel được sử dụng rộng rãi trong đánh giá CBIR, do đó
luận văn cũng sử dụng phân loại Corel làm tin cậy nền, tức là luận văn xem tất cả
các ảnh trong cùng loại Corel là liên quan. Tập tin cậy nền này gồm 4 cột (có tiêu
đề: ID ảnh truy vấn, Truy vấn khởi tạo Q0, ID ảnh và Sự liên quan) và gồm 3400
dòng (mỗi dòng là một véc tơ đặc trưng). 3.2.4. Cấu hình đề xuất thiết bị chạy thực nghiệm Để đảm bảo hệ thống vận hành thông suốt, luận văn cũng đề xuất cấu hình
tối thiểu đối với thiết bị chạy thực nghiệm. Bảng 3.3 cung cấp chi tiết thông tin
cấu hình tối thiểu của thiết bị chạy thực nghiệm. Bảng 3.3. Bảng cấu hình đề xuất thiết bị chạy thực nghiệm. 3.3.1. Chiến lược mô phỏng phản hồi liên quan. Để bắt chước hành vi của con người, luận văn thực hiện mô phỏng phản hồi
liên quan trong thử nghiệm. Đầu tiên, 05 ảnh truy vấn khởi tạo sẽ cung cấp cho
đầu vào tra cứu. Thông qua máy tìm kiếm phân hạng tập ảnh cơ sở dữ liệu đối với
mỗi ảnh truy vấn được 05 tập kết quả. 05 kết quả này sau đó được gộp lại thành
một tập kết quả trả về duy nhất. Tiếp theo chúng tôi mô phỏng tương tác người dùng bằng việc chọn các ảnh
liên quan (positive) từ kết quả tra cứu khởi tạo dựa vào tập tin cậy nền (ground
truth), những ảnh còn lại là những ảnh không liên quan (negative) trong 100 ảnh
đầu tiên của tập kết quả. Lý do lựa chọn 100 ảnh đầu tiên là bởi vì thông thường
người dùng chỉ xem trong từ 2 đến 3 màn hình (Mỗi màn hình có khoảng 50 ảnh) để phản hồi. Các ảnh phản hồi liên quan sau đó được phân cụm thành M cụm,
huấn luyện LDA được thực hiện trên các cụm. Hệ thống tính toán các điểm truy
vấn tối ưu với từng cụm, làm đầu vào cho máy tìm kiếm lần thứ hai. Các kết quả
phân hạng tập ảnh cơ sở dữ liệu được kết hợp lại. Mô phỏng tương tác người dùng
lại một lần nữa được sử dụng trên tập kết quả mới nhằm lấy ra các ảnh liên quan
thông qua tập tin cậy nền. Tuy nhiên, các ảnh được bổ sung thêm vào các cụm
trong tập dữ liệu huấn luyện trước đó thông qua phân cụm gia tăng. Lặp lại quá
trình tra cứu một lần nữa để lấy kết quả đánh giá. Chiến lược này được sử dụng để mô phỏng người dùng thực tế trong thực nghiệm của chúng tôi. 3.3.2. Kết quả đánh giá. Áp dụng chiến lược mô phỏng phản hồi liên quan được đề cập trong phần
3.3.1 của luận văn này với tập 3400 ảnh Corel và 2 lần mô phỏng phản hồi. Luận
văn sử dụng 3400 ảnh này lần lượt mỗi 05 ảnh trong một nhóm chính là đa truy
vấn để thực hiện đánh giá đối với hệ thống. Trong thực nghiệm luận văn chạy lần lượt với 3400 truy vấn, mỗi truy vấn
thực nghiệm 3 lần với số cụm khác nhau lần lượt là 2, 4 và 6 cụm để xem xét hiệu
quả khi số cụm tăng lên trên hệ thống. Các kết quả thực nghiệm được chỉ ra trong
Hình 3.2. Trục ngang chỉ ra số cụm (cụ thể là 2, 4 và 6 cụm). Trục đứng chỉ ra độ
chính xác. Các kết quả, độ chính xác trung bình của 3400 truy vấn, được thể hiện
bằng số liệu trong Bảng 3.4 và bằng đồ thị trong Hình 3.2 ở dưới. Độ chính xác là tỉ số giữa số các ảnh liên quan với ảnh truy vấn trong tập kết
quả trả về trên tổng số các ảnh trả về. Độ chính xác của phương pháp là trung bình
độ chính xác đối với 3400 ảnh truy vấn. Bảng 3.4. Bảng kết quả của các phương pháp 2 cụm 4 cụm 6 cụm Truyền
thống Lần 1 Lần 2 Lần 1 Lần 2 Lần 1 Lần 2 Đa
truy
vấn 20.33 28.14 31.73 29.43 33.50 30.32 36.14 23.13 Độ
chính
xác Í C
Á
X
H
N
H
C
Ộ
Đ 38
36
34
32
30
28
26
24
22
20 Truyền thống Đa truy vấn Lần 1 Lần 2 2 cụm 20.33 23.13 28.14 31.73 4 cụm 20.33 23.13 29.43 33.5 6 cụm 20.33 23.13 30.32 36.14 Biểu đồ so sánh kết quả thực nghiệm Hình 3.2. Biểu đồ so sánh kết quả thực nghiệm Luận văn có thể đưa ra các kết luận từ Hình 3.2. Độ chính xác của hệ thống
tra cứu ảnh sử dụng đa truy vấn đạt 23.13%, tốt hơn so với phương pháp tra cứu
truyền thống đạt 20.33%. Khi kết hợp sử dụng phản hồi liên quan với phân cụm
gia tăng, ở lần lặp thứ 1 độ chính xác dạt 28.14 đối với 2 cụm, 29.43 với 4 cụm
và 30.32 với 6 cụm; ở lần lặp thứ 2 độ chính xác đạt 31.73% với 2 cụm, 33.5%
với 4 cụm và 36.14% với 6 cụm. Điều này khẳng định rằng độ chính xác của hệ
thống tăng lên sau mỗi lần lặp phản hồi và tăng hơn khi số lượng cụm tăng. 3.4. Giao diện hệ thống Hình 3.3. Giao diện chính của hệ thống. Hình 3.3 cung cấp giao diện chính của hệ thống. Hệ thống được xây dựng tuần tự theo các bước của mô hình hệ thống cụ thể: Bước 1: Chọn tập dữ liệu ảnh / đặc trưng. Bước 2: Chọn truy vấn khởi tạo (Có thể chọn một hay nhiều truy vấn) Bước 3: Tra cứu khởi tạo (với pha tra cứu) và phản hồi lần 1 (sau khi tra cứu) Bước 4: Huấn luyện bằng cách chọn số lượng cụm và sử dụng phân cụm
LDA bước huấn luyện. Thông tin cụm của dữ liệu huấn luyện được hiển thị trong
mục Danh sách cụm. Bước 5: Tra cứu đối với dữ liệu huấn luyện và sử dụng phân cụm LDAvới
thông tin sau tra cứu. Thông tin sau phân cụm thích gia tăng được cập nhật vào
dữ liệu huấn luyện, hiển thị trong mục Danh sách cụm. Thanh trạng thái cho biết tình trạng hoạt động của các tiến trình trong hệ thống. Hình 3.4. Chọn tập dữ liệu ảnh / đặc trưng Tập dữ liệu đặc trưng đã được trích rút tương ứng với hệ thống tra cứu và
được lưu trong file dataset1.mat. Khi dữ liệu đã được đọc thành công, các công
cụ sẽ được kích hoạt cho phép người dùng sử dụng. Hình 3.5. Chọn ảnh truy vấn khởi tạo. Người dùng chọn ảnh truy vấn từ tập đặc trưng. Hình 3.5 các ảnh truy vấn được chọn là 84003, 84004 và 84008 thuộc lớp 840. Hình 3.6. Tra cứu với truy vấn khởi tạo 84003, 84004, 84008 thuộc lớp 840. Người dùng tiến hành tra cứu với truy vấn khởi tạo, tập kết quả trả về được
hiển thị với tên và ảnh đại diện của lớp tương ứng trong tập ảnh Corel. Ảnh tương
tự ngữ nghĩa với ảnh truy vấn là hình ảnh được khoanh màu đỏ. Hình 3.6 cung
cấp kết quả tra cứu đối với truy vấn khởi tạo hay phương pháp tra cứu truyền
thống. Mô phỏng chiến lược phản hồi liên quan thông qua tập tin cậy nền, các ảnh
tương tự ngữ nghĩa với ảnh truy vấn khởi tạo được đưa vào huấn luyện. Trên Hình
3.7 số lượng ảnh phản hồi là 25/100 ảnh đối với truy vấn 84003, 84004, 84008.
Người dùng chọn số lượng cụm, tiến hành phân cụm tập huấn luyện. Kết quả phân
cụm được hiển thị trong thanh “Danh sách cụm”. Hình 3.7 cung cấp kết quả phân
cụm tập huấn luyện của ảnh truy vấn 84003, 84004, 84008. Hình 3.7. Kết quả phân cụm tập huấn luyện. Sau khi phân cụm dữ liệu huấn luyện, có thể tiến hành tra cứu với dữ liệu huấn luyện. Hình 3.8. Công cụ tra cứu và phân cụm LDA. Hình 3.9. Kết quả tra cứu phản hồi liên quan. Hình 3.9 cung cấp kết quả tra cứu với 4 truy vấn tối ưu tương ứng với 4 cụm
của tập dữ liệu huấn luyện. Áp dụng chiến lược mô phỏng phản hồi với tập kết
quả trên với phương pháp phân cụm gia tăng nhận được kết quả như Hình 3.10. Hình 3.10. Kết quả phân cụm gia tăng. Hình 3.11 cung cấp kết quả tra cứu với tập huấn luyện mới. Hình 3.11. Kết quả tra cứu sau khi sử dụng phân cụm gia tăng. 3.5. Tiểu kết chương 3. Trong chương 3, luận văn đã phân tích thiết kế hệ thống và xây dựng theo mô hình tra cứu được đề xuất ở chương 2, đồng thời xây dựng tập ảnh thử nghiệm cho hệ thống. Một phương pháp đánh giá kết quả hệ thống và so sánh với một số hệ thống tra cứu khác tương tự cũng được trình bày trong chương này. Theo đó, hiệu quả tra cứu của hệ thống theo mô hình đề xuất cho hiệu quả tra cứu tốt hơn trên cùng một tập dữ liệu thử nghiệm. Đáp ứng được mục tiêu đặt ra ban đầu là nâng cao chất lượng tra cứu ảnh. KẾT LUẬN Các hệ thống tra cứu ảnh truyền thống có những hạn chế về độ chính xác thấp là do gặp vấn đề về khoảng cách ngữ nghĩa giữa mô tả ảnh bởi đặc trưng mức thấp và ngữ nghĩa của ảnh được cho người dùng. Để giải quyết hạn chế này có nhiều cách tiếp cận khác nhau và phản hồi liên quan là một cách tiếp cận hiệu quả. Các phương pháp theo cách tiếp cận phản hồi liên quan thường dựa vào tập ảnh phản hồi từ người dùng để tính toán lại ảnh truy vấn ảnh ở lần lặp sau. Quá trình lặp đi lặp lại cho đến khi người dùng thỏa mãn. Tuy nhiên, các phương pháp tra cứu ảnh sử dụng phản hồi liên quan hiện nay thường phân cụm lại tập ảnh phản hồi tại mỗi lần lặp dẫn đến tốn nhiều thời gian tra cứu. Để khắc phục hạn chế ở trên, cách tiếp cận đa điểm được đề xuất để có thế lấy được các ảnh liên quan ngữ nghĩa nằm rải rác trong không gian đặc trưng. Với cách tiếp cận này, chúng ta sẽ phân cụm các mẫu phản hồi của người dùng ở lần phản hồi đầu tiên bởi thuật toán phân cụm gia tăng LDA, ở các lần lặp sau ta sẽ gia tăng cụm chứ không thực hiện phân cụm lại tập mẫu phản hồi nữa. Luận văn đã thực hiện được các công việc sau: - Tìm hiểu được tổng quan về tra cứu ảnh dựa vào nội dung. - Tìm hiểu về phương pháp tra cứu ảnh với phản hồi liên quan sử dụng phân cụm gia tăng. - Tìm hiểu kỹ thuật phân tích phân biệt tuyến tính (LDA). - Xây dựng hệ thống tra cứu ảnh thử nghiệm sử dụng cụm gia tăng với phản hồi liên quan. Một số vấn đề cần được nghiên cứu tiếp trong tương lai: - Thử nghiệm và đánh giá kết quả phương pháp trên tập ảnh lớn và đa dạng hơn. TÀI LIỆU THAM KHẢO Tiếng Việt: [1] Đỗ Năng Toàn, Phạm Việt Bình (2007), Giáo trình xử lý ảnh, NXB ĐH Thái Nguyên. [2] Đinh Mạnh Tường (2016) ,Giáo trình Học máy, NXB Khoa học kỹ thuật. Tiếng Anh: [3]Moses Charikar, Chandra Chekuri,Tomás Feder, Rajeev Motwani, Incremental clustering and dynamic information retrieval, In:STOC '97 Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 626-635. [4] Jin, X., & French, J.C, (2005). "Improving Image Retrieval Effectiveness via Multiple Queries," Multimedia Tools and Applications, vol. 26, pp. 221-245. [5] J. Fournier, M. Cord, Long-term similarity learning in content-based image retrieval, in: Int. Conf. Image Processing (ICIP), 441{444, 2002. [6] Quynh Dao Thi Thuy, Quynh Nguyen Huu, Canh Phuong Van, Tao Ngo Quoc (2017), “An efficient semantic–Related image retrieval method”, Expert Systems With Applications, 72, 30-41. [7] Rocchio, J.J., (1971). Relevance feedback in information retrieval. In: Salton, G. (Ed.), The SMART Retrieval System—Experiments in Automatic Document Processing. Prentice Hall, Englewood Cliffs, NJ, pp. 313–323. [8] Ying Liua, Dengsheng Zhanga, Guojun Lua, Wei-Ying Ma, A survey of content-based image retrieval with high-level semantics, Pattern Recognition 40 (2007), pp. 262-282. [9] Alzu'bi, Ahmad; Amira, Abbes; Ramzan, Naeem (2015), Semantic
content based image retrieval: A comprehensive study, in: journal of visual
communication and image representation, Vol. 32, p. 20-54. [10] J.R. Smith, C.-S. Li, Decoding image semantics using composite region
templates, IEEE Workshop on Content-Based Access of Image and Video
Libraries (CBAIVL-98), June 1998, pp. 9–13. [11] W.K. Leow, S.Y. Lai, Scale and orientation-invariant texture matching
for image retrieval, in: M.K. Pietikainen (Ed.), Texture Analysis in Machine
Vision, World Scientific, Singapore, 2000. [12] T. Li, S. Zhu and M. Ogihara, Using discriminant analysis for multi-
class classification: An experimental investigation, Knowledge and Information
Systems 10(4) (2006).18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Các ảnh truy vấn
Máy tìm kiếm
Tập kết quả
Tập phản hồi
Yes
Có là tra cứu
khởi tạo?
Phân các ảnh
thành M cụm
No
Gia tăng cụm
Tập huấn luyện
38
39
40
41
42
Các loại đặc trưng
Tên đặc trưng
Độ dài
Lược đồ màu
ColorHsvHistogram64
64
Mô men màu
ColorLuvMoment123
9
Loại đặc trưng
màu
Gắn kết màu
ColorHsvCoherence64
128
CoarsnessVector
10
Kết cấu Tamura
Directionality
8
Loại đặc trưng
kết cấu
Kết cấu Wavelet
WaveletTwtTexture
104
Kết cấu MASAR
MRSAR
15
43
Chủng loại
STT
1
2
3
4
5
6
7
Intel Core i3
4Gb DDRIII
500Gb HDD
Intel HD Graphic
Windows 8 x64
Matlab 2016a x64
Số lượng
1
1
1
1
1
1
1
Loại TB
CHIP
RAM
HDD
VGA
SCREEN
OS
Matlab
3.3. Đánh giá kết quả thực nghiệm.
44
45
46
47
48
49
50
51
52
53
54
