ĐẠ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 THU HẰNG
TRA CỨU ẢNH DỰA TRÊN KHOẢNG CÁCH
VÀ BÀI TOÁN TỐI ƯU PARETO
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2020
ĐẠ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 THU HẰNG
TRA CỨU ẢNH DỰA TRÊN KHOẢNG CÁCH
VÀ BÀI TOÁN TỐI ƯU PARETO
Chuyên ngành: Khoa học máy tính
Mã số: 8 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: PGS.TS. NGÔ QUỐC TẠO
THÁI NGUYÊN - 2020
i
LỜI CAM ĐOAN
Tên tôi là: Nguyễn Thu Hằng
Lớp: CK17B
Khóa học: 2018-2020
Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 8 48 01 01
Cơ sở đào tạo: Trường Đại học Công nghệ thông tin và Truyền Thông -
Đại học Thái Nguyên
Người hướng dẫn khoa học: PGS.TS Ngô Quốc Tạo
Tôi xin cam đoan toàn bộ nội dung trình bày trong luận văn này là kết quả tìm hiểu và nghiên cứu của bản thân. Các số liệu, kết quả trình bày trong luận văn là hoàn toàn trung thực. Những tư liệu được sử dụng trong luận văn đều được tuân thủ theo luật sở hữu trí tuệ, có liệt kê rõ ràng các tài liệu tham khảo.
Tôi xin chịu hoàn toàn trách nhiệm với những nội dung viết trong luận
văn này!
Thái Nguyên, ngày 10 tháng 09 năm 2020 Tác giả luận văn Nguyễn Thu Hằng
ii
LỜI CẢM ƠN
Trong quá trình học tập và thực hiện luận văn, tôi đã nhận được sự hướng
dẫn tận tình của Thầy hướng dẫn khoa học PGS.TS Ngô Quốc Tạo - Viện Hàn
Lâm Khoa học và Công nghệ Việt Nam, là người thầy mà tôi muốn bày tỏ lòng
biết ơn sâu sắc nhất.
Luận văn sẽ không thể hoàn thành nếu không có các Thầy cô 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 mọi điều
kiện thuận lợi và giúp đỡ. Tôi xin bày tỏ sự cảm ơn chân thành với những sự
hỗ trợ và giúp đỡ này.
Xin cảm ơn các đề tài VAST01.07/19-20 và NVCC02.01/20-20
Xin chân thành cảm ơn Chủ tịch HĐQT, Ban giám hiệu và tập thể
Trường THPT Lương Thế Vinh - Cẩm Phả - Quảng Ninh đã tạo điều kiện thuận
lợi về mặt thời gian và tài chính để tôi hoàn thành luận văn này.
Cuối cùng tôi cảm ơn tất cả những sự giúp đỡ của gia đình, đồng nghiệp,
bạn bè đã động viên, đóng góp ý kiến, để tôi hoàn thành được luận văn này.
iii
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................. i
LỜI CẢM ƠN ................................................................................................... ii
DANH MỤC CHỮ VIẾT TẮT ........................................................................ v
KÍ HIỆU TOÁN HỌC ..................................................................................... vi
DANH MỤC HÌNH VẼ .................................................................................. vii
DANH MỤC BẢNG BIỂU ........................................................................... viii
MỞ ĐẦU ........................................................................................................... 1
Chương 1 TỔNG QUAN VỀ TRA CỨU ẢNH ............................................ 5
1.1. Giới thiệu về hệ thống tra cứu ảnh .......................................................... 5
1.1.1 Các thành phần của hệ thống CBIR .................................................. 5
1.1.2 Tra cứu ảnh theo nội dung sử dụng kỹ thuật máy học ...................... 9
1.2. Các đặc trưng của ảnh ........................................................................... 13
1.2.1 Đặc trưng màu ................................................................................. 13
1.2.2 Đặc trưng hình dạng ........................................................................ 14
1.2.3 Đặc trưng kết cấu............................................................................. 15
1.2.4 Liên hệ không gian ........................................................................... 15
1.3 Ứng dụng của tra cứu ảnh ...................................................................... 16
Chương 2 TRA CỨU ẢNH DỰA TRÊN TỐI ƯU ĐA MỤC TIÊU VỚI
KHOẢNG CÁCH ....................................................................................... 19
2.1. Giới thiệu bài toán ................................................................................. 19
2.1.1. Bài toán tra cứu ảnh theo nội dung ................................................ 19
2.1.2. Bài toán tra cứu ảnh theo nội dung sử dụng tối ưu Pareto ............ 20
2.2. Khoảng cách .......................................................................................... 20
2.2.1. Khoảng cách Minkowski ................................................................. 20
2.2.2. Khoảng cách lược đồ giao .............................................................. 21
2.2.3. Khoảng cách Canberra ................................................................... 21
iv
2.3. Đa mục tiêu theo khoảng cách .............................................................. 22
2.4. Tiếp cận giải bài toán tối ưu đa mục tiêu Pareto .................................. 22
2.4.1. Tối ưu đa mục tiêu Pareto .............................................................. 22
2.4.2. Rút gọn không gian tìm kiếm dựa vào tập Pareto .......................... 23
2.4.3. Nâng hiệu quả phân lớp ảnh ........................................................... 29
Chương 3 ỨNG DỤNG VÀ CHƯƠNG TRÌNH THỬ NGHIỆM ........... 37
3.1 Sơ đồ chương trình ................................................................................. 37
3.2 Cơ sở dữ liệu ảnh thử nghiệm ................................................................ 38
3.3 Phân tích thiết kế chương trình thử nghiệm ........................................... 40
3.3.1 Giao diện chương trình .................................................................... 40
3.3.2 Các bước thực hiện truy vấn ............................................................ 40
3.4. Đánh giá kết quả đạt được và so sánh với phương pháp khác .............. 45
3.4.1 Các phương pháp cơ sở ................................................................... 45
3.4.2 Phương pháp đánh giá ..................................................................... 45
KẾT LUẬN .................................................................................................... 56
TÀI LIỆU THAM KHẢO ............................................................................ 58
v
DANH MỤC CHỮ VIẾT TẮT
Từ Dạng đầy đủ Diễn giải viết tắt
CBIR Content-Based Image Retrieval Tra cứu ảnh dựa vào nội dung
HSV Hue, saturation, value Màu sắc, độ bão hòa, độ sáng
MARS Multimedia Analysis and Các hệ thống phân tích đa
Retrieval Systems phương tiện và tra cứu
QBIC Query By Image Content Truy vấn ảnh bởi nội dung
RF Relevance feedback Phản hồi liên quan
SVM Support vector machine Máy vector hỗ trợ
vi
KÍ HIỆU TOÁN HỌC
M Độ dài của một vector đặc trưng
N Kích thước của cơ sở dữ liệu
T Số bộ đặc trưng
t Chỉ số bộ đặc trưng
Q, Ii Ảnh truy vấn và ảnh thứ I trong cơ sở dữ liệu
Vector đặc trưng chuẩn hóa của ảnh thứ i
Vector đặc trưng chuẩn hóa ở bộ t của ảnh thứ i
Qt, It đặc trưng bộ t tương ứng của ảnh truy vấn Q và ảnh I bất kỳ
Đặc trưng chuẩn hóa ở bộ t của ảnh truy vấn
Khoảng cách theo bộ đặc trưng t của ảnh so với ảnh truy vấn
Khoảng cách ảnh so với ảnh truy vấn trên toàn bộ các đặc
trưng
top-k Tập gồm k ảnh có thứ hạng tương tự cao nhất đối với ảnh truy vấn
Tập ảnh có độ tương tự cao nhất theo đặc trưng toàn cục trong một tra cứu
Tập ảnh được xác nhận không liên quan ở phản hồi của người dùng
Tập ảnh được xác nhận liên quan ở phản hồi của người dùng
Tập ảnh có độ tương tự cao nhất theo đặc trưng ở bộ t trong một tra cứu
Tập ảnh có thứ hạng độ tương tự cao và thuộc tập trong một tra cứu
Tập ảnh chưa được tra cứu
vii
DANH MỤC HÌNH VẼ
Hình 3.1. Sơ đồ chương trình .......................................................................... 37
Hình 3.2. Các ảnh minh họa cho 10 thể loại trong tập ảnh Wang .................. 38
Hình 3.3. Hình ảnh giao diện chương trình thực nghiệm ............................... 40
Hình 3.4. Đưa một ảnh truy vấn vào hệ thống tra cứu đề xuất ....................... 41
Hình 3.5. Kết quả tra cứu khởi tạo của top-20 ................................................ 42
Hình 3 6. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ nhất ......... 43
Hình 3.7. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ hai ........... 43
Hình 3.8. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ ba ............. 44
Hình 3.9. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ tư ............. 44
Hình 3.10. Trung bình độ chính xác trên kết quả top-k của đề xuất Pareto-
AdaBoost trên ba tập dữ liệu Wang, Oxford Buiding, Caltech theo
năm vòng phản hồi liên quan. ......................................................... 49
Hình 3.11. Trung bình độ chính xác trên kết quả top-k của đề xuất Pareto-
SVM trên ba tập dữ liệu Wang, Oxford Building, Caltech theo năm
vòng phản hồi liên quan .................................................................. 51
Hình 3.12. So sánh độ chính xác trên các kết quả top-k của kỹ thuật đề xuất
Pareto-AdaBoost với các kỹ thuật cơ sở tren ba tập dữ liệu Wang,
Oxford Building, Caltech ................................................................ 53
Hình 3.13. So sánh độ chính xác trên các kết quả top-k của kỹ thuật đề xuất
Pareto-SVM với các kỹ thuật cơ sở trên ba tập dữ liệu Wang,
Oxford Building, Caltech ................................................................ 54
Hình 3.14. Đồ thị độ chính xác của các phương pháp Pareto-AdaBoost,
SVM, AdaBoost và MARS trên các tập dữ liệu Wang, Oxford
Building, Caltech ............................................................................ 54
Hình 3.15. Đồ thị độ chính xác của các phương pháp Pareto-SVM, SVM,
AdaBoost và MARS trên tập dữ liệu Wang, Oxford Building và
Caltech. ........................................................................................... 55
viii
DANH MỤC BẢNG BIỂU
Bảng 3.1. Các miêu tả ảnh và hàm khoảng cách sử dụng trong thực nghiệm 39
Bảng 3.2. Các tham số sử dụng trong thực nghiệm ........................................ 46
Bảng 3.3. Số ứng viên Pareto thep top – k đối với Wang (gồm 1000 ảnh) .... 47
Bảng 3.4. Số ứng viên Pareto theo top – k đối với Oxford Buiding (gồm 2560
ảnh) ............................................................................................. 48
Bảng 3.5. Số ứng viên Pareto theo top – k đối với Caltech (gồm 590 ảnh) ... 48
Bảng 3.6. Trung bình độ chính xác top - k kết quả của đề xuất Pareto-
AdaBoost trên năm vòng phản hồi liên quan đối với tập dữ
liệu Wang ................................................................................... 50
Bảng 3.7. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-
AdaBoost trên năm vòng phản hồi liên quan đối với tập dữ liệu
Oxford Buiding ........................................................................... 50
Bảng 3.8. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-
AdaBoost trên năm vòng phản hồi liên quan đối với tập dữ liệu
Caltech. ....................................................................................... 51
Bảng 3. 9. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-SVM
trên năm vòng phản hồi liên quan đối với tập dữ liệu Wang. .... 52
Bảng 3.10. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-SVM
trên năm vòng phản hồi liên quan đối với tập dữ liệu Oxford
Building ....................................................................................... 52
Bảng 3.11. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-SVM
trên năm vòng phản hồi liên quan đối với tập dữ liệu Caltech ... 53
1
MỞ ĐẦU
Những năm gần đây, với sự xuất hiện của Internet đã thay đổi hoàn toàn
cách thức chúng ta tìm kiếm thông tin. Ví dụ khi cần tìm kiếm, đơn giản chỉ
cần gõ một vài từ khóa vào máy tìm kiếm Google hay Bing, ngay lập lức có
được một danh sách tương đối chính xác các trang web có liên quan đến thông
tin cần tìm. Đối với hình ảnh, cũng đã có các hệ thống tương tự. Tra cứu ảnh
có thể được thực hiện dựa vào các mô tả ngắn của ảnh. Các ảnh có thể được mô
tả bởi một tập các thuộc tính độc lập nội dung (tên file,khuôn dạng, loại, kích
cỡ, tên tác giả, thiết bị thu nhận, ngày tạo và vị trí ổ đĩa) mà có thể được quản
lý thông qua hệ quản trị cơ sở dữ liệu truyền thống. Hạn chế chính của cách
tiếp cận này đó là các truy vấn bị giới hạn vào các thuộc tính hiện có của tệp
ảnh. Một cách tiếp cận thay thế là sử dụng các từ khóa hoặc các chú thích ảnh.
Trong cách tiếp cận này, trước tiên các ảnh được chú thích thủ công bằng các
từ khóa. Sau đó, các ảnh có thể được tra cứu bởi các chú thích tương ứng của
chúng. Cách tiếp cận này ít giới hạn hơn cách tiếp cận trước. Tuy nhiên, có ba
khó khăn chính với cách tiếp cận này, đó là yêu cầu số lượng lớn các nhân công
trong việc phát triển các chú thích, sự khác biệt trong giải thích nội dung ảnh,
và sự không nhất quán của cách gán từ khóa giữa những người thực hiện chú
thích khác nhau. Cách tiếp cận chú thích từ khóa này trở nên không khả thi khi
cỡ của các tập ảnh gia tăng nhanh chóng.
Để khắc phục các khó khăn của cách tiếp cận dựa vào chú thích, một
cách tiếp cận thay thế là tra cứu ảnh dựa vào nội dung đã được đề xuất từ đầu
những năm 1990. Với hệ thống này, bằng cách lấy một ảnh đầu vào từ người
dùng, hệ thống cố gắng tìm kiếm các ảnh giống nhất trong cơ sở dữ liệu rồi trả
lại cho người sử dụng. Về cơ bản, hệ thống hoạt động theo cách thức sau: Đầu
tiên ảnh đưa vào để tìm kiếm (hay gọi là ảnh truy vấn) và toàn bộ ảnh trong
2
CSDL được hệ thống sử dung các kĩ thuật trích rút nội dung của ảnh sang các
vector (đặc trưng của ảnh) bằng cách sử dụng các đặc trưng mức thấp (màu sắc,
hình dạng, kết cấu, vv). Hệ thống sẽ tính toán và đo khoảng cách giữa ảnh truy
vấn với từng ảnh trong CSDL. Cuối cùng, các ảnh có khoảng cách gần nhất với
ảnh truy vấn được hệ thống trả về. Điều này làm giảm đáng kể những khó khăn
của cách tiếp cận thuần túy dựa trên chú thích, bởi vì quá trình trích rút đặc
trưng có thể được thực hiện tự động. Kể từ khi ra đời, tra cứu ảnh dựa vào nội
dung đã thu hút sự quan tâm nghiên cứu rất lớn, phạm vi từ nghiên cứu tới
thương mại. Cho đến nay, một số hệ thống nguyên mẫu thực nghiệm và các sản
phẩm thương mại đã được đề xuất và xây dựng như QBIC, MARS.
Tuy CBIR có nhiều tiến bộ song người dùng vẫn gặp khó khăn trong
việc tìm kiếm thông tin liên quan từ tập dữ liệu ảnh lớn không đồng nhất về
mặt nội dung và ngữ nghĩa. Điều này dẫn đến kết quả tìm kiếm chưa được
như mong muốn. Thông tin mà máy tính hiểu nội dung ảnh thường là là các
giá trị điểm ảnh,vector đặc trưng được trích rút theo các thủ tục,... còn con
người hiểu về nội dung của ảnh thường là các khái niệm ngữ nghĩa. Do không
có sự tương quan một cách chính xác giữa nội dung mà máy tính có được
thông qua đặc trưng trực quan mức thấp dung mà con người hiểu thông qua
các khái niệm ngữ nghĩa mức cao dẫn đến khoảng trống ngữ nghĩa. Khoảng
trống ngữ nghĩa định nghĩa theo Smeulders và cộng sự như sau:
“Khoảng trống ngữ nghĩa là sự không tương đồng giữa thông tin ảnh,
được trích rút 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ể ”.
Khoảng trống ngữ nghĩa nằm giữa các đặc trưng trực quan mức thấp của
các ảnh và các ngữ nghĩa mức cao mong muốn dự định suy ra từ các đặc trưng
trực quan mức thấp. Các thực nghiệm trên các hệ thống CBIR chỉ ra rằng các
3
nội dung mức thấp thường thất bại trong mô tả các khái niệm ngữ nghĩa mức
cao của ảnh. Do đó, hiệu năng của tra cứu ảnh dựa vào nội dung vẫn còn xa so
với kỳ vọng của người dùng.
Để khắc phục được hạn chế ở trên, những năm gần đây các hướng nghiên
cứu tập trung đi tìm các phương pháp giảm khoảng trống ngữ nghĩa giữa đặc
trưng mức thấp và khái niệm mức cao.
Để thu hẹp được khoảng trống ngữ nghĩa, nâng cao hiệu quả tra cứu ảnh
theo nội dung cần sử dụng kết hợp đa đặc trưng để so sánh độ tương tự, đánh
chỉ số tra cứu. Việc sử dụng kết hợp đa đặc trưng để so sánh độ tương tự sẽ dẫn
đến đa khoảng cách do đó cần độ đo toàn cục như một kết hợp tối ưu tuyến tính
của các hàm khoảng cách thành phần. Trong luận văn này tôi xin đề cập đến
phương pháp “Tra cứu ảnh dựa trên khoảng cách và bài toán tối ưu pareto”,
nghiên cứu sử dụng cách tiếp cận tối ưu Pareto như một bài toán tiền xử lý dữ
liệu (rút gọn tập mẫu). Qua đó, không gian tìm kiếm trên tập độ đo khoảng cách
với truy vấn được thu gọn nhất của tập Pareto. Tập thu gọn này được sử dụng
như dữ liệu đầu vào giúp cho bộ máy phân lớp hoạt động hiệu quả hơn.
Nội dung luận văn gồm 3 chương
Chương 1: TỔNG QUAN VỀ TRA CỨU ẢNH
Chương này trình bày khái quát lý thuyết cơ bản về tra cứu ảnh dựatrên
nội dung, tìm hiểu một số đặc trưng ảnh, tìm hiểu một số ứng dụng và hệ thống
tra cứu ảnh sẵn có.
Chương 2: TRA CỨU ẢNH DỰA TRÊN TỐI ƯU ĐA MỤC TIÊU VỚI
KHOẢNG CÁCH
Chương 2 giới thiệu bài toán tra cứu ảnh theo nội dung và khoảng cách
thường dùng trong tra cứu ảnh, đa mục tiêu theo khoảng cách, đề xuất rút gọn
4
tập ứng viên nhằm giảm không gian tìm kiếm dựa vào tiếp cận tối ưu đa mục
tiêu Pareto.
Chương 3: ỨNG DỤNG VÀ CHƯƠNG TRÌNH THỬ NGHIỆM
Chương 3 đưa ra thiết kế của hệ thống đề xuất, cơ sở dữ liệu lựa chọn thử
nghiệm và đánh giá kết quả đạt được và so sánh với phương pháp khác.
5
Chương 1 TỔNG QUAN VỀ TRA CỨU ẢNH
1.1. Giới thiệu về hệ thống tra cứu ảnh
Từ hai thập kỉ qua, sự xuất hiện của Internet đã thay đổi hoàn toàn cách
thức chúng ta tìm kiếm thông tin. Ví dụ, khi làm việc với văn bản, ta chỉ cần
đơn giản gõ một vài từ khóa vào máy tìm kiếm Google hay Bing để ngay lập
lức có được một danh sách tương đối chính xác các trang web có liên quan. Ta
cũng có các hệ thống tương tự với ảnh. Với hệ thống này, bằng cách lấy một
ảnh đầu vào từ người sử dụng, hệ thống cố gắng tìm kiếm các ảnh giống nhất
trong dữ liệu, rồi trả lại cho người sử dụng. Một cách lý tưởng, sự giống nhau
ở đây được định nghĩa dựa trên sự giống nhau giữa các khái niệm được thể hiện
trong ảnh. Đây là hệ thống Tra cứu ảnh theo nội dung hay đơn giản là tra cứu
ảnh (“content-based image retrieval” viết tắt là CBIR). Các hệ thống này
thường trích rút các biểu diễn trực quan của ảnh và định nghĩa các hàm tìm
kiếm, đối sánh mối liên quan khi tra cứu dáp ứng yêu cầu người dùng. Lĩnh vực
này đã được cộng đồng nhiên cứu quan tâm trong những năm qua.
1.1.1 Các thành phần của hệ thống CBIR
Một hệ thống CBIR gồm các thành phần cơ bản mô tả trong sơ đồ Hình 1.1
Hình 1.1. Hệ thống tra cứu ảnh theo mội dung
6
Một hệ thống tra cứu ảnh có thể thực hiện qua nhiều công đoạn: nhập
ảnh truy vấn, nhập dữ liệu ảnh cho csdl, chuẩn hóa ảnh, trích chọn đặc trưng
của ảnh truy vấn và ảnh trong cơ sở dữ liệu, tính toán độ tương tự và cách hiển
thị kết quả lên màn hình… Tuy nhiên chúng ta có miêu tả khái quát một hệ
thống tra cứu ảnh thông qua những công đoạn chính sau:
Hình 1.2. Cấu trúc của hệ thống tra cứu ảnh theo nội dung
- Trích chọn đặc trưng: Các đặc trưng của hình ảnh bao gồm các đặc
trưng nguyên thủy và các đặc trưng ngữ nghĩa hoặc đặc trưng logic. Các đặc
trưng cơ bản đó là: màu sắc (color), kết cấu (texture), hình dạng (shape), vị trí
không gian (spatial location),… được định lượng trong tự nhiên, chúng có thể
được trích xuất tự động hoặc bán tự động. Đặc trưng logic cung cấp mô tả trừu
tượng của dữ liệu hình ảnh ở các cấp độ khác nhau. Thông thường, một hoặc
nhiều đặc trưng có thể được sử dụng trong từng ứng dụng cụ thể trên thực tế.
+ Trích chọn đặc trưng cho ảnh truy vấn: Ở công đoạn này ảnh truy vấn
ngay khi ảnh được nhập vào hệ thống sẽ xử lý để trích chọn đặc trưng theo đặc
trưng nhất định nào đó và phục vụ tính toán độ tương đồng sau đó đưa ra kết
quả, có thể nói công đoạn này sẽ được tính toán online.
7
+ Trích chọn đặc trưng ảnh trong cơ sở dữ liệu: Đây là công đoạn tính
toán đặc trưng cho ảnh trong cơ sở dữ liệu sinh ra cơ sở dữ liệu lưu trữ các đặc
trưng, công đoạn này thường sẽ được tính toán từ khi nhập ảnh vào cở sở dữ
liệu, hoặc tiến hành khi người dùng cho phép thực hiện hay nói cách khác nó
được tiến hành offline.
- Đo độ tương tự giữa các ảnh: Hệ thống CBIR dựa trên những đặc điểm
nguyên thủy để so sánh độ tương tự giữa ảnh truy vấn và tất cả các ảnh trong
CSDL. Mặc dù vậy sự tương tự hoặc sự khác nhau giữa các ảnh không chỉ xác
định theo một cách. Số lượng của ảnh tương tự sẽ thay đổi khi yêu cầu truy vấn
thay đổi. Chẳng hạn trong trường hợp hai hình ảnh, một là biển xanh mặt trời
mọc và trường hợp khác là núi xanh với mặt trời mọc.
Hình 1.3. Hình ảnh minh họa độ tương tự giữa 2 hình ảnh
Khi mặt trời được xem xét thì độ tương tự giữa hai ảnh này là cao nhưng
nếu đối tượng quan tâm là biển xanh thì độ tương tự giữa hai ảnh này là thấp.
Như vậy rất khó khăn để tìm ra phương pháp đo độ tương tự giữa hai hình ảnh
trên một cách chính xác đối với tất cả các kiểu yêu cầu của truy vấn. Hay nói
cách khác mỗi một phương pháp tra cứu sẽ có giới hạn của chính nó. Ví dụ rất
khó cho công nghệ tra cứu dựa trên màu sắc để tìm ra điểm khác nhau giữa một
ảnh là bầu trời màu xanh với một ảnh là mặt biển xanh. Vì vậy khi đánh giá
8
một phương pháp tra cứu ảnh dựa trên nội dung cần phải biết rằng hiệu quả của
công nghệ đó phụ thuộc vào kiểu yêu cầu tra cứu mà người dùng sử dụng.
- Đánh chỉ số: Đánh chỉ số là một công việc quan trọng trong tra cứu ảnh
dựa trên nội dung, nó giúp tìm kiếm nhanh ảnh dựa trên đặc trưng trực quan,
bởi vì các vector đặc trưng của ảnh có xu hướng, có số chiều cao và vì vậy nó
không thích hợp cho các cấu trúc đánh chỉ số truyền thống. Do đó trước khi lên
kế hoạch đánh chỉ số ta phải tìm cách làm giảm số chiều của các vector đặc
trưng. Khi đã giảm được số chiều thì dữ liệu đa chiều được đánh chỉ số.
- Tra cứu và hiển thị kết quả: Hiển thị kết quả vừa thu được cho người
dùng theo một giá trị ngưỡng tương tự nào đó.
- Phản hồi liên quan: Kĩ thuật phản hồi liên quan được sử dụng nhằm thu
hẹp “khoảng trống ngữ nghĩa” trong CBIR, cải thiện kết quả tra cứu thông qua
tương tác giữa người dùng và máy. Một kịch bản thông thường cho phản hồi
liên quan trong CBIR như sau:
Bước 1: Máy tính đưa ra các kết quả tra cứu khởi tạp (top-k)thôngqua
ảnh truy vấn.
Bước 2: Người dùng cung cấp đánh giá trên kết quả top-k, đánh giá theo
kiểu như “liên quan” hoặc “không liên quan” với nhận thức của chính người
dùng đó.
Bước 3: Máy học và thử lại. Lặp lại bước 2.
Các thành phần cơ bản của hệ thống CBIR:
- Cơ sở dữ liệu ảnh: Là cơ sở dữ liệu phục vụ lưu trữ ảnh. Có thể là trên
ổ cứng thường, cũng có thể là hệ quản trị cơ sở dữ liệu.
- Cơ sở dữ liệu đặc trưng: Các đặc trưng đã được trích chọn offline sẽ
được lưu trữ trong cơ sở dữ liệu như tệp tin matlab, bảng tính excel,…
9
Quá trình thực thi của hệ thống tra cứu ảnh:
+ Người dùng đưa ra truy vấn hoặc ảnh có sẵn.
+ Hệ thống đón nhận truy vấn hoặc ảnh, sau đó trích chọn các đặc trưng.
+ Hệ thống so sánh truy vấn hoặc ảnh với cơ sở dữ liệu đặc trưng đã có.
+ Hệ thống trả ra kết quả tra cứu.
Một hệ thống tra cứu ảnh cần đáp ứng được:
+ Nhu cầu sử dụng hình ảnh của người dùng và thông tin đi kèm ảnh.
+ Cách mô tả nội dung ảnh.
+ Trích chọn đặc trưng từ ảnh.
+ Lưu trữ cơ sở dữ liệu ảnh.
+ Truy vấn và lưu trữ hình ảnh tương tự.
+ Truy xuất hình ảnh trong cơ sở dữ liệu hiệu quả.
+ Giao diện thân thiện, phù hợp.
1.1.2 Tra cứu ảnh theo nội dung sử dụng kỹ thuật máy học
Các kỹ thuật học máy có hiệu năng tăng đáng kể đối với các hệ thống
CBIR như các kỹ thuật máy vector hỗ trợ (SVM), học tăng cường
(AdaBoost),… Một hạn chế là không có dữ liệu huấn luyện từ trước với mỗi
truy vấn cụ thể, dữ liệu huấn luyện chỉ có được sau khi người dùng phản hồi
với ảnh truy vấn được đưa vào bởi một người dùng. Bên cạnh dữ liệu huấn
luyện là tương đối ít và dữ liệu kiểm tra bị nhiễu do vấn đề khoảng trống ngữ
nghĩa.
Kỹ thuật AdaBoost
10
Kỹ thuật AdaBoost đã được áp dụng trong một số hệ thống CBIR nhằm
mục đích tăng cường các thuật toán học yếu, đòi hỏi dữ liệu được đánh trọng
số trước khi thực hiện thuật toán học ở mỗi lần lặp. Tuy nhiên, các kỹ thuật dựa
vào AdaBoost thường phân lớp chậm và cần nhiều lần lặp phản hồi.
Boosting là phương pháp cho phép cải thiện độ chính xác của bất kì thuật
toán học nào. Đây là một loại phương pháp tổ hợp, cho phép kết hợp các
𝐿 𝐹(𝑥) = ∑ 𝛼𝑖𝑓𝑖(𝑥) 𝑙=1
phương pháp phân lớp yếu thành một phân lớp mạnh hơn
trong đó 𝛼𝑖 xác định trọng số của bộ học yếu thứ l. Kỹ thuật Boosting
thực hiện lặp đi lặp lại, sao cho mỗi lần lặp l, phân lớp yếu đưa vào tổ hợp cho
tới khi đạt tiêu chuẩn dừng.
AdaBoost dẫn đến các biến thể boosting phổ biến hiện nay và đã trở
thành một trong những thuật toán học mạnh. Trong quá trình học, giữ phân bố
trọng số 𝐷𝑙(𝑖)trên các mẫu huấn luyện. Theo phân bố này, tại mỗi lần lặp
Boosting sẽ lựa chọn bộ học yếu và đưa them vào mô hình. Sau mỗi lần lặp l,
mẫu được đánh lại trọng số, dựa vào một hàm lỗi (loss function). Nhằm tập
trung vào các mẫu khó, bỏ qua các mẫu dễ. Giải thuật AdaBoost là thuật toán
học hiệu quả và phổ biến, do khá dễ dàng cài đặt, hầu như không cần thiết tới
tham số hiệu chỉnh. Trên thực tế chỉ có một tham số là số tối đa L lần lặp. Việc
thiết lập tham số rất quan trọng bởi vì thuật toán có thể có xu hướng overfit
(quá khớp) nếu thiết lập L lớn.
Kỹ thuật máy vector hỗ trợ (SVM)
Các kĩ thuật học máy và phản hồi liên quan được đề xuất nhằm hỗ trợ
hiệu chỉnh truy vấn. Hầu hết các kĩ thuật truyền thống đều đòi hỏi lượng lớn
11
mẫu dữ liệu huấn luyện và truy vấn khởi tạo với các mẫu tốt. Trong nhiều tình
huống ứng dụng thực tế các thuật toán học có thể làm việc ngay cả khi nghèo
dữ liệu huấn luyện và hạn chế thời gian huấn luyện.
Để giảm số lượng mẫu yêu cầu, các truy vấn quan tâm đến các kĩ thuật
học tích cực. Một trong những phương pháp như vậy là SVM, dựa vào phản
hồi liên quan khi phân lớp. Học tích cực có thể được mô hình hoá như sau: Cho
một cơ sở dữ liệu E chứa một tập con chưa gán nhãn U và một tập con X đã gán
nhãn. Phương pháp học gồm hai thành phần f và s. Thành phần f là một phân
lớp được huấn luyện trên tập dữ liệu đã gán nhãn X. Thành phần s là hàm lấy
mẫu đưa ra một tập gán nhãn hiện thời X, quyết định lựa chọn tập con 𝑢 ∈ 𝑈
chọn cho truy vẫn người dùng. Cách học tích cực này đưa đến một f mới, sau
mỗi lần lặp của phản hồi liên quan.
Kĩ thuật này có thể mô tả sau đây: Tập dữ liệu đầu vào/ra X, Y, tập huấn
luyện (x1, y1), (x2, y2),…, (xm, ym). Mục đích muốn học một hàm phân lớp 𝑦 =
𝑓(𝑥, 𝛽) trong đó 𝛽 là trọng số cần huấn luyện. Minh họa như hình 1.4.
Hình 1.4. Minh họa siêu phẳng
12
Ví dụ chọn mô hình từ các siêu phẳng, hàm phân lớp sẽ có dạng:
𝑓(𝑥, 𝜔, 𝑏) = 𝑠𝑖𝑔𝑛(𝜔𝑥 + 𝑏)
Tiêu chí của SVM là chọn siêu phẳng sao cho lề là cực đại và tối thiểu
hóa lỗi, dẫn tới đưa về giải bài toán tối ưu bậc 2. Đầu ra của bài toán tối ưu là
𝑚 𝜔 = ∑ 𝛼𝑖𝑥𝑖 𝑖=1
𝜔 và b, trong đó 𝜔 có dạng như sau:
Với tiêu chí lề cực đại, các 𝛼 được giải ra sẽ có rất ít giá trị khác 0. Các
mẫu dữ liệu trong tập huấn luyện X tương ứng với 𝛼𝑖 khác 0 được gọi là vector
tựa (Support vector).
SVM phỏng đoán kết quả tra cứu theo các mẫu huấn luyện. Dựa vào kết
quả tra cứu, người dùng lựa chọn các ảnh liên quan và không liên quan. Các
ảnh liên quan tạo thành tập mẫu dương và các ảnh không liên quan tạo thành
tập mẫu âm. Sauk hi học tập mẫu huấn luyện, bằng cách sử dụng SVM, bộ phân
lớp SVM f(x) sẽ dần điều chỉnh theo mục đích tra cứu của người dùng. Mỗi
ảnh Ii trong cơ sở dữ liệu, điểm số được tính toán theo score(Ii) = f(xi). Đây
chính là khoảng cách từ các ảnh tới siêu phẳng phân tách, score(Ii) lớn hơn
ngưỡng thì Ii sẽ gần khớp với ảnh truy vấn. Sắp xếp các điểm số của tất cả các
ảnh theo thứ tự giảm dần, thu được danh sách top-k . Khi đó ta thu được kết
quả tốt hơn và lần phản hồi tiếp theo lại được thực hiện. Lặp lại quá trình này
đến khi thỏa mãn yêu cầu người dùng.
Zhang và cộng sự đã mô tả quá trình trên bằng thuật toán 1.1. Trước tiên,
một phương pháp tra cứu truyền thống được thực hiện bằng cách đối sánh các
ảnh theo phương pháp thông thường, sắp xếp các ảnh theo độ đo khoảng cách
13
tăng dần với ảnh truy vấn. Kết quả trả về người dùng k ảnh đầu tiên của danh
sách đó, kí hiệu là NB.
Thuật toán 1.1 SVM dựa vào phản hồi liên quan
Đầu vào: Đánh dấu ảnh trên tập kết quả NB: tập liên quan 𝑁𝐵+ và tập
không liên quan 𝑁𝐵−
Đầu ra: Tập kết quả NB
1. Chuẩn bị cho SVM dữ liệu huấn luyện
(𝑥𝑖, 𝑦𝑖), 𝑦𝑖 = { +1 𝑛ế𝑢 𝑥𝑖 ∈ 𝑁𝐵+ −1 𝑛ế𝑢 𝑥𝑖 ∈ 𝑁𝐵−
2. Xây dựng hàm phân lớp sử dụng thuật toán SVM
𝑖
𝑓(𝑥) = ∑ 𝛼𝑖𝑦𝑖𝐾(𝑥𝑖, 𝑥) + 𝑏
(chú ý: theo đầu ra khoảng cách độ tương tự với truy vấn)
3. Tính toán điểm số cho mỗi ảnh Ii trong cơ sở dữ liệu 𝑠𝑐𝑜𝑟𝑒 (𝐼𝑖) =
𝑓(𝑥𝑖)
4. Sắp xếp các ảnh theo điểm số
1.2. Các đặc trưng của ảnh
Việc tra cứu theo nội dung dựa trên một số đặc trưng mức thấp của ảnh
Low-level features): Màu sắc (Colors), Hình dạng (Shapes), Kết cấu (Textures)
và Liên hệ không gian (Spatial relationship).
1.2.1 Đặc trưng màu
Đặc trưng màu là một trong những đặc trưng thị giác rộng nhất do quan
hệ chặt chẽ với các đối tượng ảnh, tiền cảnh và nền. Màu cũng là một đặc trưng
14
trực quan mạnh do nó không phụ thuộc vào trạng thái của các nội dung ảnh như
hướng, cỡ và góc. Các biểu diễn màu phổ biến là lược đồ màu, mô men màu,
tương quan màu và ma trận đồng hiện màu.
1.2.2 Đặc trưng hình dạng
Về cơ bản, đặc trưng hình dạng ảnh mang thông tin ngữ nghĩa và có thể
được phân thành hai loại:
- Dựa trên đường bao.
- Dựa trên vùng.
Phương pháp dựa trên đường bao trích rút các đặc trưng dựa trên đường
bao ngoài của vùng trong khi phương pháp dựa trên vùng trích rút các đặc trưng
dựa trên toàn bộ vùng. Các phương pháp tra cứu dựa vào hình dạng bị các vấn
đề liên quan đến các bất biến dịch chuyển, tỉ lệ, quay và ổn định với các thay
đổi nhỏ về hình dạng. Do đó, các mô tả hình dạng thường được trích rút và
được sử dụng với các đặc trưng khác như mầu và kết cấu và có xu hướng là
hiệu quả trong các ứng dụng cụ thể như các đối tượng nhân tạo.
Hình 1.5. Hình dạng đặc trưng
15
1.2.3 Đặc trưng kết cấu
Trong thị giác máy tính, không có định nghĩa chính xác về kết cấu ảnh,
nhưng nó có thể được xác định như tất cả những gì còn lại sau khi xem xét các
mầu và các hình, hoặc như một mô tả của cấu trúc ảnh, tính ngẫu nhiên
(randomness), hột (granulation), đường thẳng (linearity), độ nhám (roughness) và
tính đồng nhất (homogeneity). Kết cấu ảnh là một đặc trưng ảnh quan trọng để
mô tả các thuộc tính bề mặt của một đối tượng và mối quan hệ của nó với các
vùng xung quanh. Do các đặc trưng kết cấu được xuất hiện trong nhiều ảnh
thực, chúng rất quan trọng và có lợi ích trong các nhiệm vụ tra cứu ảnh và nhận
dạng mẫu. Tuy nhiên, độ phức tạp tính toán và độ chính xác tra cứu là những
nhược điểm chính của các hệ thống tra cứu ảnh dựa vào kết cấu.
Hình 1.6. Hình dạng kết cấu
1.2.4 Liên hệ không gian
Liên hệ không gian: Được dùng nhiều trong xử lý ảnh, để phân biệt
các đối tượng trong một ảnh. Có hai cách biểu diễn: theo đối tượng và theo
quan hệ.
16
Hình 1.7. Biểu diễn hình dạng qua mối liên hệ không gian
Độ tương tự giữa các ảnh truy vấn và cơ sở dữ liệu được tính toán trên
các vị trí không gian của các nội dung ảnh. Tuy nhiên, các biểu diễn không gian
dựa vào đồ thị có chi phí tính toán cao.
1.3 Ứng dụng của tra cứu ảnh
Ứng dụng của tra cứu ảnh có rất nhiều trong đời sống xã hội, phục vụ
cho nhiều mục đích khác nhau, nhằm xác nhận, tra cứu thông tin. Giảm bớt
công việc của con người nhằm tăng hiệu suất làm việc: Album ảnh số của người
dùng, ảnh y khoa, bảo tàng ảnh, tìm kiếm nhãn hiệu, mô tả nội dung MPEG-7,
ảnh tội phạm, hệ thống tự động nhận biết điều khiển giao thông,…
Sau đây là một vài hệ thống lớn đại diện cho các lĩnh vực đặc trưng:
- 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 tập đoàn IBM, đây là một hệ thống tra cứu ảnh thương mại được phát
triển từ rất sớm. Hiện nay, hệ thống này hỗ trợ một vài độ đo tương tự cho ảnh
17
như: trung bình màu sắc, lược đồ màu sắc, và kết cấu. Công nghệ sử dụng trong
hệ thống bao gồm 2 phần chính là: đánh chỉ số và tìm kiếm. Hơn nữa, hệ thống
này còn cung cấp vài cách tiếp cận truy vấn theo đơn đặc trưng, đa đặc trưng
và đa giai đoạn.
- Hệ thống Imatch: Hệ thống này cho phép người sử dụng tra cứu ảnh
bởi nội dung màu, hình dạng và kết cấu. Nó cung cấp một số phương pháp để
tra cứu ảnh tương tự: Màu tương tự, màu và hình dạng (Quick), màu và hình
dạng (Fuzzy) và sự phân bố màu. Màu tương tự truy vấn những ảnh tương tự
với ảnh mẫu dựa trên sự phân bố màu toàn cục.
+ Màu và hình dạng (Quick) tìm hình ảnh tương tự bởi việc kết hợp cả
hình dạng, kết cấu và màu.
+ Màu và hình dạng (Fuzzy) thực hiện thêm những bước xác định đối
tượng trong ảnh mẫu.
+ Phân bố màu cho phép người sử dụng vẽ ra sự phân bố màu hoặc xác
định tỷ lệ phần trăm của một màu trong hình ảnh mong muốn.
+ Imatch cũng cung cấp những đặc điểm khác nội dung để xác định ảnh:
ảnh nhị phân, ảnh co kích thước, lưu trữ trong những định dạng khác và những
ảnh có tên tương tự.
- Hệ thống Photobook: Hệ thống này được phát triển ở Massachusetts
Institute of Technology cho phép người sử dụng tra cứu ảnh dựa trên màu sắc,
kết cấu và hình dạng. Hệ thống này cung cấp một tập các thuật toán đối sánh
gồm: Euclidean, Mahalanobis, Vector space angle, Histogram, Fourier peak
và Wavelet tree distance như là những đơn vị đo khoảng cách. Trong hầu hết
các phiên bản, đã có thể định nghĩa những thuật toán đối sánh của họ. Hệ
thống như là một công cụ bán tự động và có thể sinh ra một mẫu truy vấn dựa
18
vào những ảnh mẫu được cung cấp bởi người sử dụng. Điều này cho phép
người sử dụng trực tiếp đưa những yêu cầu truy vấn của họ với những lĩnh
vực khác nhau, và mỗi lĩnh vực họ có thể thu được những mẫu truy vấn tối
ưu.
- Hệ thống VisualSEEK và WebSEEK: Cả hai hệ thống này đều được
phát triển tại Trường Đại học Colombia. VisualSEEK là hệ thống cơ sở dữ
liệu ảnh; nó cho phép người sử dụng tra cứu ảnh dựa trên màu sắc, không gian
miền và đặc điểm kết cấu. Tập màu và chuyển đổi wavelet dựa trên kết cấu
được sử dụng để thực hiện những đặc điểm này. Thêm vào đó VisualSEEK
còn cho phép người sử dụng tạo truy vấn bằng việc chỉ định vùng màu và
những không gian vị trí của chúng. WebSEEK là một catalog ảnh và là công
cụ tìm kiếm cho web. Hệ thống này cung cấp mẫu cho danh sách ảnh và video
trên trang web sử dụng kết hợp xử lý dựa trên text và phân tích dựa trên nội
dung.
- Hệ thống RetrievalWare: Hệ thống này được phát triển bởi tập đoàn
công nghệ Excalibur cho phép người sử dụng tra cứu ảnh bởi nội dung màu,
hình dạng, kết cấu, độ sáng, kết cấu màu và hệ số co. Người sử dụng có thể
điều chỉnh tỷ trọng của những đặc điểm này trong suốt quá trình tìm kiếm.
- 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, không gian.
- Ngoài ra còn một vài hệ thống khác như: Virage system, Stanford
SIMPLICity system, NEC PicHunter system,…
19
Chương 2 TRA CỨU ẢNH DỰA TRÊN TỐI ƯU ĐA MỤC TIÊU
VỚI KHOẢNG CÁCH
2.1. Giới thiệu bài toán
2.1.1. Bài toán tra cứu ảnh theo nội dung
Việc tìm kiếm ảnh theo nội dung là tính độ tương tự hoặc khoảng cách
ảnh. Cơ sở dữ liệu lưu ảnh mẫu bao gồm thông tin và nội dung ảnh nguyên gốc
do người sử dụng đưa vào. Dữ liệu trong CBIR được lấy trên cơ sở các nội
dung mà nó trích rút bằng cách sử dụng các kĩ thuật trích rút đặc trưng mức
thấp bên trong mỗi ảnh (màu sắc, hình dạng, kết cấu, vv…). Các hàm tìm kiếm
được xây dựng để tra cứu theo sự quan tâm. Bài toán này sử dụng kết hợp nhiều
biểu diễn đặc trưng được miêu tả. Trong xếp hạng các kết quả trả về cho người
dùng thông thường sử dụng khoảng cách toàn cục bằng kết hợp tuyến tính
khoảng cách cục bộ theo biểu diễn đặc trưng thành phần. Một ảnh được xếp thứ
hạng cao hơn nếu và chỉ nếu độ đo khoảng cách toàn cục là nhỏ hơn.
Ví dụ 2.1. Giả sử chúng ta có hai đặc trưng màu (C) và kết cấu (T). Độ
(𝑇)(𝑜1) = 0.3
(𝐶)(𝑜1) = 0.6, 𝐷𝑄 𝐷𝑄
(𝑇)(𝑜2) = 0.2
(𝐶)(𝑜2) = 0.5, 𝐷𝑄 𝐷𝑄
(𝑇)(𝑜3) = 0.35
(𝐶)(𝑜3) = 0.45, 𝐷𝑄 𝐷𝑄
đo khoảng cách của ba đối tượng o1, o2, o3 tương ứng với truy vấn Q là
Khoảng cách toàn cục áp dụng kết hợp tuyến tính độ đo khoảng cách
thành phần của các đặc trưng màu và kết cấu tương ứng là 𝐷𝑄(𝑜1) = 0.9,
𝐷𝑄(𝑜1) = 0.7, 𝐷𝑄(𝑜1) = 0.8. Dễ dàng xếp hạng độ đo khoảng cách là o2, o3,
o1. Khi không kết hợp tuyến tính độ đo khoảng cách toàn cục, xếp hạng dựa
vào độ đo khoảng cách thành phần chúng ta chỉ có thể xếp hạng được o1 và o2,
20
đối tượng o3 không thể so sánh được với hai đối tượng còn lại. Như vậy cách
xếp hạng sử dụng tổng toàn bộ độ đo khoảng cách của các thành phần trong kết
quả cuối cùng còn nhiều vấn đề cần xem xét và cải tiến.
2.1.2. Bài toán tra cứu ảnh theo nội dung sử dụng tối ưu Pareto
Các hệ thống CBIR sử dụng bộ máy phân lớp ít sử dụng cách tiếp cận
Pareto để giảm tập dữ liệu và đây chính là yếu tố quan trọng giúp cải thiện các
bộ máy phân lớp dữ liệu. Trong nghiên cứu này tôi sử dụng Pareto như một bài
toán tiền xử lý dữ liệu (rút gọn tập mẫu). Qua đó, không gian tìm kiếm trên tập
độ đo khoảng cách với truy vấn được thu gọn nhất của tập Pareto. Tập thu gọn
này được sử dụng như dữ liệu đầu vào giúp cho bộ máy phân lớp hoạt động
hiệu quả hơn.
2.2. Khoảng cách
Việc lựa chọn xác định loại độ đo khoảng cách mà sử dụng để so sánh
độ tương tự của từng cặp ảnh còn phụ thuộc vào cấu trúc của các véc tơ đặc
trưng mô tả chúng. Độ đo khoảng cách được áp dụng chỉ ra độ tương tự giữa
truy vấn và mỗi ảnh trong cơ sở dữ liệu. Để thu được tra cứu chính xác hơn và
hiệu năng tốt hơn, hệ thống CBIR nên tận dụng độ đo đối sánh tương tự hiệu
quả, mô tả và định lượng tốt các tương tự nhận thức.
Các độ đo khoảng cách có thể được sử dụng cho đối sánh tương tự trong
lĩnh vực CBIR như:
2.2.1. Khoảng cách Minkowski
Được sử dụng rộng rãi để đo sự tương tự trong các hệ thống CBIR. Với
hai ảnh X và Y được cho, được biểu diễn trong không gian dữ liệu bởi hai véc
tơ n chiều (𝑥1, 𝑥2, … , 𝑥𝑛) và (𝑦1, 𝑦2, … , 𝑦𝑛) tương ứng. Khoảng cách
Minkowski 𝐿𝑝 giữa X và Y, d(X,Y) được xác định như sau:
21
1 𝑟
𝑛 𝐷(𝑋, 𝑌) = (∑ |𝑥𝑖 − 𝑦𝑖|𝑟 𝑖=1
) (2.1)
Ở đây r là nhân tố chuẩn hóa cho khoảng cách Minkowski, và ≥ 1 . Khi
𝑟 = 1 công thức (1.1) biểu diễn khoảng cách Manhattan (hay khoảng cách 𝐿1)
và khi 𝑟 = 2 nó biểu diễn khoảng cách Euclid (khoảng cách 𝐿2) và 𝑟 = ∞ ta
1 ) 𝑟
có khoảng cách Chebyshev (tức 𝐿2) tương ứng:
(2.2)
(∑ |𝑥𝑖 − 𝑦𝑖|𝑟
𝑛 𝑖=1
𝐷(𝑋, 𝑌) = 𝑚𝑎𝑥𝑖∈{1..𝑛}|𝑥𝑖 − 𝑦𝑖| = lim 𝑟→∞
2.2.2. Khoảng cách lược đồ giao
Khoảng cách lược đồ giao (Histogram Interrsection -HI) cho tra cứu ảnh
là biểu diễn của L1 khi thực hiện phần so khớp. Khoảng cách lược đồ giao của
hai lược đồ n chiều X và Y được xác định như sau:
(2.3)
𝐷(𝑋, 𝑌) = 1 −
𝑛 ∑ min (𝑥,𝑦𝑖) 𝑖=0 𝑛 ∑ max (𝑥𝑖,𝑦𝑖) 𝑖=0
Các màu không được đưa ra trong các lược dồ sẽ không đóng góp giá trị
giao, do vậy các màu cơ sở không ảnh hưởng đến khoảng cách tổng thể. Trong
trường hợp hai lược đồ màu là như nhau giá trị giao là 1 và khoảng cách là 0.
2.2.3. Khoảng cách Canberra
Cho hai ảnh X và Y được biểu diễn trong không gian dữ liệu bởi hai véc
tơ n chiều (𝑥1, 𝑥2, … , 𝑥𝑛) và (𝑦1, 𝑦2, … , 𝑦𝑛). Khoảng cách Canberra là một biến thể chuẩn của khoảng cách Manhattan trong đó chênh lệch tuyệt đối giữa hai
véc tơ trong mỗi chiều được chia bởi tổng của các giá trị tuyệt đối của cả hai
véc tơ trong chiều này. Khoảng cách Canberra được xác định như sau:
𝑛 𝐷(𝑋, 𝑌) = ∑ 𝑖=1
|𝑥𝑖−𝑦𝑖| |𝑥𝑖|+|𝑦𝑖|
(2.4)
22
2.3. Đa mục tiêu theo khoảng cách
Trong tra cứu ảnh dựa vào nội dung các kiểu đặc trưng trực quan thường
được sử dụng là màu sắc, kết cấu và hình dạng. Một số biểu diễn cho kiểu đặc
trưng màu bao gồm bộ đặc trưng lược đồ màu và mô men màu, biểu diễn kiểu
đặc trưng kết cấu gồm một số bộ đặc trưng như Tamura và ma trận đồng mức.
Các hệ thống tra cứu ảnh dựa vào nội dung thường làm việc với kích
thước cơ sở dữ liệu ảnh lớn, các chủ đề phong phú nên thường lựa chọn tiếp
cận toàn cục để miêu tả ảnh. Bên cạnh đó việc sử dụng đa đặc trưng kết hợp
được thế mạnh của các bộ đặc trưng trong miêu tả nộ dung trực quan của ảnh.
Hạn chế của việc sử dụng đa đặc trưng là cần phải xác định được tầm quan
trọng của mỗi bộ đặc trưng trong miêu tả ảnh để gán trọng số phù hợp đối sánh
thông qua độ tương tự của các ảnh.
2.4. Tiếp cận giải bài toán tối ưu đa mục tiêu Pareto
2.4.1. Tối ưu đa mục tiêu Pareto
Tối ưu đa mục tiêu là bài toán có nhiều hơn một mục tiêu và các mục
tiêu có ràng buộc chặt chẽ với nhau, đôi khi xung đột nhau. Do đó trong bài
toán tối ưu đa mục tiêu không thể đạt được giá trị tốt nhất của tất cả các mục
tiêu cùng một lúc. Mục đích của tối ưu đa mục tiêu là sinh ra một danh sách
các lời giải gọi là tập Pareto
Tập Pareto là một tập con của tập các điểm khả thi các lời giải chứa tất
cả các điểm có ít nhất một mục tiêu tối ưu trong khi giữ nguyên mọi mục tiêu
khác. Các điểm đó được gọi là các điểm tối ưu Pareto.
Tiếp cận Pareto có thể thu gọn tập ứng viên trên không gian tổ hợp đặc
trưng, như rút gọn không gian tìm kiếm để cải thiện kết quả tra cứu về mặt dộ
chính xác của hệ thống CBIR.
23
2.4.2. Rút gọn không gian tìm kiếm dựa vào tập Pareto
Bài toán tối ưu trên miền không gian độ đo khoảng cách của truy vấn với
các mẫu trong cơ sở dữ ảnh phát biểu như sau:
Giả thiết {Ei | i = 1, 𝑁̅̅̅̅̅} là một cơ sở dữ liệu đặc trưng của ảnh, được trích
rút theo T bộ đặc trưng trong số các kiểu đặc trưng trực quan gồm màu sắc, kết
𝑡 (𝐼) là khoảng cách tương ứng của mỗi bộ đặc trưng giữa ảnh truy
cấu và hình dạng.
Gọi 𝐷𝑄
vấn Q và ảnh I, ∀𝑡 = 1, 𝑇. Mỗi ảnh 𝐼 ∈ 𝐸 có T giá trị khoảng cách thành phần
so với truy vấn Q tương ứng T bộ đặc trưng. Không gian tìm kiếm các ảnh I có
𝑇(𝐼)) |𝐼 ∈ 𝐸} (2.5)
độ tương tự so với ảnh truy vấn Q cụ thể được cho bởi:
1(𝐼), … , 𝐷𝑄
𝐸𝑄 = {(𝐼 , (𝐷𝑄
Tồn tại một ánh xạ 𝜋𝑄, là song ánh trong không gian tìm kiếm EQ, như là:
𝜋𝑄: EQ → E
𝑇(𝐼)) → 𝐼
1(𝐼), … , 𝐷𝑄
(2.6) (𝐼 , (𝐷𝑄
Để đơn giản, khi Q cố định, ta đặt 𝐼 ≡ 𝜋𝑄(𝐼) ∈ 𝐸 và𝐴 ≡ {𝜋𝑄(𝐼)/∀𝐼 ∈ 𝐴}
𝑡 (𝐼) nhỏ
Bài toán CBIR đơn giản nhất có thể diễn đạt như sau: Tìm tất cả các I
trong không gian tìm kiếm EQ mà thỏa mãn đồng thời các tiêu chí 𝐷𝑄
nhất (ở mức tương tự đặc trưng trực qun mức thấp) được xác định như sau:
𝑡 (𝐼), 𝑡 ∈ {1, . . , 𝑇} 𝑠𝑎𝑜 𝑐ℎ𝑜 𝐼 ∈ 𝐸
(2.7) min 𝐷𝑄 {
Bài toán phát biểu thông qua phương trình (2.7) ở trên không phải bài
toán tối ưu đa tiêu, vì các tiêu chí là các giá trị khoảng cách. Tìm ảnh I ∈ E
trongbài toán trên hỏi tất cả các tiêu chí được tối ưu đồng thời (nhỏ nhất) theo
24
𝑡 (𝐼) trong không gian nhiều tiêu chí EQ,ví dụ như tìm ảnh lí
mỗi tiêu chí 𝐷𝑄
tưởng I minh họa trong Hình 2.1.
Hình 2.1. Minh họa không gian tìm kiếm EQ
Ảnh lí tưởng Ilí tưởng ∈ EQ thỏa mãn đồng thời các tiêu chí là không tồn
tại. Lời giải của bài toán này dẫn tới tìm tập các lời giải thỏa hiệp trong số các
tiêu chí. Mỗi lời giải là tối ưu nếu không có lời giải khác trong EQ có khoảng
cách nhỏ hơn trên mọi tiêu chí Dt (Q, I ). Điều này có nghĩa rằng, ta cần tìm các
điểm theo trích rút Pareto front, đánh giá toàn toàn bộ tập các giá trị khoảng
cách (các tiêu chí) cho mọi điểm trong không gian tìm kiếm. Kĩ thuật Pareto
front đa mức sâu sử dụng trong không gian EQ.
25
Giống như bài toán tối ưu đa mục tiêu dụa vào việc tìm một tập của các
thỏa hiệp số các lời giải tiềm năng. Ta cần một định nghĩa mở rộng của quan
hệ trội. Một lời giải hiệu quả không trội hơn các lời giải khác trong mọi tiêu
chí. Nói một cách khác, nghĩa là không có khả năng tìm lời giải khác tốt hơn
đông thời các tiêu chí đối với một lời giải hiệu quả đang tồn tại.
Để tìm tập các đối tượng tối ưu trên miền không gian độ đo khoảng cách,
dựa trên quan hệ trội tìm tập tối ưu Pareto theo định nghĩa 2.1.
Định nghĩa 2.1. (Trội Pareto trên độ đo khoảng cách) Cho truy vấn Q,
xác định một quan hệ trội (ký hiệu là f) trên tập độ đo khoảng cách của hai ảnh
I1 và I2 như sau:
trội hơn hay bị làm trội bởi (ký hiệu ) nếu và chỉ nếu
Theo định nghĩa này, rõ ràng I1 và I2 trong không gian tìm kiếm EQ thỏa
mãn tính chất . Vì thế I1 là liên quan hơn I2 so với Q.
Ví dụ 2.2. Xét sự quan hệ của Ví dụ 2.1, bởi vì và
Mệnh đề 2.1. Cho và trong . Ta có:
(2.1.1) .
(2.1.2) , .
(2.1.3) , là
một phép kết nhập.
Tính chất (2.1.1) nghĩa là giữa hai ảnh chỉ tồn tại duy nhất một quan hệ.
Tính chất (2.1.2) cho biết quan hệ trội đảm bảo tính thứ tự. Tính chất (2.1.3)
26
đảm bảo nếu hai ảnh thỏa mãn quan hệ trội thì tính thứ tự được đảm bảo với
mọi hàm kết nhập (trung bình, trọng số, min, max,…).
Định nghĩa 2.2. (Pareto front) Cho , Pareto front của A (ký hiệu
) được định nghĩa như sau:
Ví dụ 2.3. (2.3.1) Xét sự quan hệ của Ví dụ 2.1, , bởi vì:
Tập thỏa mãn Định nghĩa 2.2 do và . Nghĩa là các điểm
thuộc tập không bị làm trội bởi bất kỳ điểm nào.
(2.3.2)
Hình 2.2. Mô tả Pareto front
Xét quan hệ trên ví dụ 2.1, từ Định nghĩa 2.2 ta thu được tập chứa tất cả
các điểm không bị làm trội bởi bất kì điểm nào, chúng được gọi là các điểm
thỏa hiệp. Tập này cũng có điểm số kết hợp tuyến tính là nhỏ hơn tập còn lại.
Hình 2.2 cho thấy một đường cong bao được các điểm thỏa hiệp được
hay chính là Pareto.
27
Định nghĩa 2.3. (Pareto front đa mức sâu)
2.3.1. Pareto front độ sâu thứ được định nghĩa như sau:
(i)
(ii)
2.3.2. Giá trị độ sâu:
Hình 2.3 minh họa hai mức sâu của không gian EQ. Độ sâu mức thứ hai
tìm được bằng cách loại bỏ mức thứ nhấ PF1
Hình 2.3. Minh họa hai mức độ sâu PF1 và PF2 của không gian EQ
Nhận xét 2.1.
Ví dụ 2.5. Xét sự quan hệ của Ví dụ 2.1:
28
Ví dụ 2.6. Xét sự quan hệ của Ví dụ 2.1
Nếu thì nghĩa là .
Một số tính chất quan trọng khác của Pareto front đa mức sâu được miêu
tả dưới đây:
Mệnh đề 2.3.
(2.3.1) .
Tính chất này cho biết bất kỳ một ảnh nào chỉ thuộc về một Pareto front duy nhất.
(2.3.2) và .
Tính chất này nghĩa là một không gian tìm kiếm chỉ có một giá trị tối đa
Pareto front và hợp của tất cả các Pareto front này chính bằng số ảnh trong
không gian đó.
(2.3.3) .
Tính chất này nghĩa là hai ảnh thuộc cùng một Pareto front thì không thể so
sánh với nhau (không ảnh nào trội hơn ảnh nào).
(2.3.4) Nếu thì tồn tại .
Tính chất này nghĩa là một ảnh thuộc về Pareto front mức sâu hơn thì luôn tồn
tại một ảnh khác nằm trong mức sâu thấp hơn trội hơn ảnh đó.
(2.3.5) Mục 2 của Định nghĩa 2.3 là hợp lệ. Nếu thì tồn tại duy
nhất để cho
Nghĩa là mỗi ảnh trong không gian tìm kiếm thì luôn thuộc một độ sâu duy nhất.
(2.3.6) .
29
Tính chất này cho biết một ảnh trội hơn ảnh khác thì độ sâu Pareto front của
nó sẽ thấp hơn.
(2.3.7)
(2.3.8)
Định lý 2.1 (Đường trội) Mọi điểm I trong không gian tìm kiếm EQ, luôn
tồn tại ít nhất depthQ(I) - 1 các điểm trong EQ là liên quan tốt hơn I theo các
đặc trưng mức thấp.
Định nghĩa 2.4. (Hợp Pareto) Cho và L là độ sâu của Pareto front,
hợp Pareto của tập con (ký hiệu ) được định nghĩa như sau:
Mệnh đề 2.4. .
Định nghĩa 2.5. (Bao của Pareto front) Cho và , bao của
Pareto front (ký hiệu ) được định nghĩa như sau
, (2.7)
Mệnh đề 2.5.
2.4.3. Nâng hiệu quả phân lớp ảnh
Thuật toán 2.1 PFDA ( Pareto đa mức sâu)
Đầu vào:
{𝐸𝑄𝑡/𝑡 = 1, 𝑇̅̅̅̅̅} 𝐸𝑄𝑡danh sách được sắp gồm m điểm, mỗi điểm có t
chiểu.
K Số điểm trong tập Pareto front đa mức độ sâu.
Đầu ra:
30
PointSet Tập kết quả chứa các điểm Pareto theo từng mức sâu
front
𝑇 = 0, 𝑎𝑀𝑎𝑥 = 0, 𝑑𝑒𝑝𝑡ℎ = 0
1. Khởi tạo:
𝐹𝑃 = ∅, 𝑃𝐹_𝑁𝑒𝑥𝑡 = ∅, {𝑎𝑇𝑢𝑝𝑙𝑒𝑀𝑎𝑥𝑡}𝑡=1
2. while #PointSet do 3. while ∄ Ii∈ PF mà for t = 1 to T do 4. 5. Lấy Ii ở trên cùng của danh sách 𝐸𝑄𝑡 mà chưa được kiểm tra 𝑡 (𝐼𝑖 ) then 6. if 𝑎𝑀𝑎𝑥 < 𝐷𝑄 𝑡 (𝐼𝑖); 7. 𝑎𝑀𝑎𝑥 = 𝐷𝑄 end if 8. isDominate = False 9. 10. while not(isDominate) (∃𝐼𝑖 ∈ 𝑃𝐹) chưa được so sánh với Ii do if 11. then 12. chuyển Ij từ PF vào PF_Next end if 13. if 14. then 15. isDominated = true 16. Chèn Ii vào PF_Next; 17. end if 18. end while 31 if not(isDominated) then 19. 20. Chèn Ii vào PF end if 21. aTupleMaxt =aMax; /* Đặt lại ngưỡng ở t */ 22. vào PointSet 23. Chọn các điểm Ii ∈ PF mà 24. end for 25. end while 26. if (PointSet < K) then 27. PF = PF_Next 28. PF_Next= ∅ 29. do for all Ii, Ij ∈ PF mà 30. thì chuyển Ij từ PF sang PF_Next 31. end for vào PointSet 32. Chọn các điểm Ii ∈ PF mà 33. end if 34. end while Trong thuật toán 2.1, một vector ngưỡng aTupleMax được thiết lập bằng số bộ đặc trưng, giá trị của mỗi chiều bằng giá trị tối đa của tất cả các điểm Pareto mà nó gặp trong vòng lặp. Kết thuc thuật toán, ta thu được một tập các điểm Pareto front đa mức sâu. Tập này chứa tất cả các diểm thỏa hiệp theo từng Pareto front nghĩa là không bị làm trội bởi bất kỳ điểm nào khác. Tập này chứa tất cả các điểm có độ đo khoảng cách toàn cục tối thiểu thu đ\ực bằng kết hợp 32 tuyến tình, cũng như các diểm có độ đo khoảng cách cục bộ nhỏ nhất trên mỗi mức Pareto front. Việc so sánh mức sâu depth với L nhằm mục đích khi chưa tìm đủ số điểm Pareto đa mức sâu PointSet thì tiếp tục thực hiện, ngược lại nếu số điểm PointSet đạt tới K thì thuật toán dừng. Thuật toán sử dụng các phép toán so sánh trên T danh sách. Dễ thấy độ phức tạp của thuật toán là O( N x T x K ) Để cải thiện những hạn chế của một số kĩ thuật phân lớp trong CBIR, sự kết hợp giữa các định nghĩa và các tính chất của Pareto trong một mô hình CBIR sử dụng kĩ thuật phân lớp của máy học gồm các pha như sau: 1. Tính độ tương tự: Mỗi ảnh I trong cơ sở dữ liệu được tính khoảng cách theo bộ đặc trưng và khoảng cách toàn cục với ảnh truy vấn Q. 𝑙
xây dựng ( theo Định nghĩa 2.3), kết quả ta thu được tập 𝑃𝐹𝐷𝑄 2. Xây dựng tập ứng viên Pareto: Tập ứng viên Pareto theo l mức sâu được 𝑙 được xếp 3. Xây dựng tập huấn luyện và tập kiểm tra: Trong lần tra cứu khởi tạo, khi chưa có dữ liệu huấn luyện, các ảnh trong tập ứng viên 𝑃𝐹𝐷𝑄 hạng theo độ đo khoảng cách toàn cục, có được tập kết quả top – k. Người dùng phản hồi trên tập top – k được hai tập 𝑁𝐵+ và 𝑁𝐵− tương ứng với ảnh “liên quan” và “không liê quan” với khái niệm của truy vấn. Cập nhật tập huấn luyện: {𝑁𝐵+, 𝑁𝐵−} = {(𝐼𝑖, 𝑦𝑖), … , (𝐼𝑚, 𝑦𝑚)}, trong đó mẫu huấn luyện 𝐼𝑖 ∈ (𝑁𝐵+ ∪
𝑁𝐵−), nhãn lớp 𝑦𝑖 ∈ 𝑌 = {−1,1} tương ứng “liên quan” và “không liên quan”,
m là kích cỡ tập huấn luyện. 𝑙 ). Tập kiểm tra: Đây là tập ứng viên Pareto hiện thời vừa thu được (tập 𝑃𝐹𝐷𝑄 33 4. Tìm hàm phân lớp: Phân lớp theo một kĩ thuật phân lớp với dữ liệu huấn luyện là tập ảnh phản hồi của người dùng, dữ liệu kiểm tra là tập ứng viên 𝑙 được xếp hạng theo giá trị dự báo hoặc giá trị Pareto vừa được xây dựng. 5. Tập kết quả: Tập 𝑃𝐹𝐷𝑄 lớp theo hàm phân lớp vừa thực hiện. Danh sách có thứ hạng dự báo cao nhất được trả về người dùng. Đây là kết quả top- k có các ảnh tương tự nhất với ảnh truy vấn. Người dùng phản hồi trên tập top – k: Tập 𝑁𝐵+ và tập 𝑁𝐵− được cập nhật them. Hiệu chỉnh trọng số và dịch chuyển truy vấn. 6. Kết quả cuối cùng: Đây là tập ảnh top – k khi người dùng thỏa mãn hoặc hết số lần định trước. Ngược lại quay lại quá trình trình từ bước 1 với truy vẫn mới thông qua dịch chuyển truy vấn. Thuật toán 2.2 PFCBIR được đề xuất làm việc trên không gian tìm kiếm trả về từ Thuật toán 2.1 cùng với một máy phân lớp được sử dụng trên dữ liệu Pareto front đa mức sâu này. Thuật toán 2.2 hoạt động theo mô hình gồm các pha như trên. Thuật toán 2.2 PFCBIR (Tra cứu sử dụng Pareto đa mức độ sâu) Đầu vào: E - Cơ sở dữ liệu đặc trưng l - số mức front (độ sâu) K - số điểm của tập là hợp các Pareto front đa mức sâu Đầu ra: Tập kết quả ảnh thỏa mãn /* Tra cứu khởi tạo */ 𝑙 ← 𝐸𝑄 /* Xây dưng tập ứng viên Pareto theo định nghĩa 2.3 sử 1: 𝐸𝑄 ← Tính độ tương tự với mỗi ảnh truy vấn Q 2: 𝑃𝐹𝐷𝑄 dụng thuật toán tìm ứng viên Pareto*/ 34 𝑙 /* Hiển thị top - k ảnh tương tự nhất với Q từ tập ứng viên 3: 𝑁𝐵 ← 𝑃𝐹𝐷𝑄 Pareto (theo độ tương tự mức thấp) */ 4: Tập huấn luyện: {𝑁𝐵+, 𝑁𝐵−} ← 𝑁𝐵 /* Tập huấn luyện được xây dựng từ lựa chọn của người dùng trên top - k kết quả */ /* Tra cứu sử dụng thông tin phản hồi */ 5: while người dùng chưa thỏa mãn do 6: 𝑄′ ← 𝑁𝐵+ /* Sử dụng kĩ thuật hiệu chỉnh truy vấn*/ 7: 𝐸𝑄′ ← Tính lại độ tương tự với mỗi ảnh truy vấn hiệu chỉnh Q’ /* Tính độ tương tự dựa vào kĩ thuật hiệu chỉnh trọng số*/ 𝑙 ← 𝐸𝑄′ /* Xây dựng tập ứng viên Pareto theo định nghĩa 2.3. Đây 8: 𝑃𝐹𝐷𝑄 là tập kiểm tra*/ 9: Xây dựng một hàm quyết định phân phân lớp SVM cho tập kiểm tra. 10: 𝑁𝐵 ← Tập kiểm tra /* Hiển thị top - k ảnh tương tự nhất với Q’ từ tập kiểm tra, được sắp xếp giảm dần theo giá trị dự báo của hàm phân lớp */ 11: Cập nhật tập huấn luyện: {𝑁𝐵+, 𝑁𝐵−} ← 𝑁𝐵 /* Tập huấn luyện được xây dựng từ lựa chọn của người dùng trên top - k kết quả */ 12: end while Thuật toán PFCBIR hoạt động như sau: - Tra cứu khởi tạo: 𝑁
𝑡 (𝐼𝑖)}
𝑖=1,𝑡=1,𝑇̅̅̅̅ , xây dựng từ + Dòng 1: Không gian tìm kiếm 𝐸𝑄 = {𝐼𝑖, 𝐷𝑄 tính độ đo khoảng cách theo bộ đặc trưng của mỗi ảnh với ảnh truy vấn. Mỗi 𝑡 (𝐼𝑖)} ảnh thứ i trong cơ sở dữ liệu ta có tập độ đo tương tự theo bộ đặc trưng 𝑡=1,𝑇̅̅̅̅ và độ đo tương tự kết hợp 𝐷𝑄(𝐼𝑖) so với ảnh truy vấn. {𝐷𝑄 35 + Dòng 2: Từ không gian tìm kiếm EQ, xây dựng tập ứng viên Pareto (Pareto front đa mức sâu) theo định nghĩa Pareto front đa mức sâu (Định nghĩa 2.3) sử dụng thuật toán 2.1 + Dòng 3: Sắp xếp các ảnh trong tập Pareto front đa mức sâu thu được (dòng 2) theo độ tương tự toàn bộ giảm dần, gọi tắt là tập NB (top – k tập ảnh có thứ hạng cao nhất). + Dòng 4: Xây dựng tập huấn luyện: Trên tập kết quả NB người dùng lựa chọn các ảnh theo đánh giá “liên quan” hoặc “không liên quan” với các khái 𝑇) hay 𝑦𝑖 = +1 hoặc -1. niệm của ảnh truy vấn. Các ảnh được chọn “liên quan” hoặc “không liên quan”
được hệ thống đưa vào tập 𝑁𝐵+ hoặc 𝑁𝐵− tương ứng. Tập huấn luyện là các
ảnh thuộc cả hai tập này, ảnh thuộc tập 𝑁𝐵+ được gán nhãn là +1, ảnh thuộc
tập 𝑁𝐵− đươc gán nhãn -1. Theo mô hình học xếp hạng, mỗi mẫu huấn luyện 1, … , 𝐼𝑖 gồm vec tơ đặc trưng 𝑥𝑖 và lớp 𝑦𝑖 tương ứng, trong trường hợp này 𝑥𝑖 =
(𝐼𝑖 Tra cứu sử dụng thông tin phản hồi: + Dòng 6: Sử dụng tập các ảnh liên quan thu được ở dòng 4 (𝑁𝐵+) để xây dựng truy vấn hiệu chỉnh. + Dòng 7: Tính lại độ tương tự của mỗi ảnh trong tập dữ liệu theo truy vấn hiệu chỉnh. Độ tương tự được tính dựa vào kĩ thuật hiệu chỉnh trọng số. + Dòng 8: Xây dựng ứng viên Pareto front đa mức sâu (Định nghĩa 2.3). Kĩ thuật này điều chỉnh tập ứng viên Pareto front đa mức sâu theo khái niệm của truy vấn vừa được hiệu chỉnh. Quá trình này lựa chọn được các ảnh từ học thông tin phản hồi của người dùng. Tập ứng viên Pareto front đa mức sâu luôn được điều chỉnh cho phù hợp với khái niệm của truy vấn, + Dòng 9: Xây dựng hàm quyết định phân lớp kiểu như SVM. AdaBoost, … sử dụng các thuật toán và kĩ thuật máy học có đầu vào là tập huấn luyện và tập kiểm tra. Đầu ra của hàm phân lớp là danh sách các điểm số tương ứng của các ảnh (giá trị dự báo lớp hoặc giá trị xếp hạng). 36 + Dòng 10: Xếp hạng: Lấy ra tập top – k có giá trị xếp hạng (dự báo) được sắp xếp theo thứ tự giảm dần, kí hiệu là tập NB. + Dòng 11: Cập nhật tập huấn luyện như dòng 4, có sự tăng cường sau mỗi lần phản hồi. Thông thường quá trình phản hồi của người dùng thường được thiết lập số lần lặp nhỏ hơn 10 (tương đương số ảnh tra cứu 20% đến 30% cơ sở dữ liệu). Dễ thấy, nếu số lần lặp là loop thì thuật toán có độ phức tạp là O(loop x N x T x K), trong đó K là số điểm Pareto, T là số bộ đặc trưng và N là số ảnh trong cơ sở dữ liệu. 37 Chương 3 ỨNG DỤNG VÀ CHƯƠNG TRÌNH THỬ NGHIỆM 3.1 Sơ đồ chương trình Hình 3.1. Sơ đồ chương trình Hệ thống gồm các bước sau: - Khởi tạo tra cứu: Đầu tiên tính độ tương tự của mỗi ảnh với ảnh truy vấn. Tiếp theo là xây dựng tập ứng viên Pareto đối với truy vấn, hiển thị top-k ảnh có độ tương tự nhất với truy vẫntừ tập ứng viên Pareto. - Người dung phản hồi trên tập top-k kết quả, tập huấn luyện thu được từ tập các ảnh mà người dung đánh giá, tập kiểm tra gồm các ảnh trong tập ứng viên Pareto. - Phân lớp tập kiểm tra bằng một máy phân lớp. 38 - Hiển thị tập top-k kết quả. Nếu kết quả chưa thỏa mãn, người dùng tiếp
tục phản hồi bằng các đánh giá. Các ảnh liên quan trong lần phản hồi này được
sử dụng để hiệu chỉnh truy vấn và hiệu chỉnh trọng số cho việc hiệu chỉnh độ
tương tự. Quá trình tiếp tục tìm tập ứng viên Pareto đối với truy vấn hiệu chỉnh. Đóng góp của luận văn trong hệ thống là xây dựng tập ứng viên Pareto
trên tập giá trị độ đo khoảng cách giữa các bộ đặc trưng của mỗi ảnh trong cơ
sở dữ liệu so với ảnh truy vấn. Tập ứng viên Pareto là tập có khả năng liên quan
cao nhất theo đặc trưng trực quan mức thấp và có kích cỡ nhỏ hơn so với toàn
bộ có sở dữ liệu. 3.2 Cơ sở dữ liệu ảnh thử nghiệm Luận văn sử dụng ba tập ảnh chuẩn được sử dụng phổ biến trong CBIR Tập ảnh Wang là tập con của tập Corel được sử dụng trong nhiều
nghiên cứu CBIR. Tập dữ liệu này có 1000 ảnh được phân thành mười lớp
theo các chủ đề đó là: Biển, Châu Phi, hoa hồng, ngựa, núi, thức ăn, xe buýt,
khủng long, lâu đài, voi. Mỗi lớp có 100 ảnh, tất cả các ảnh là ảnh mầu, định
dạng .jpg, kích thước mỗi ảnh là 384 pixel x 256 pixel. Đây là một lợi thế
lớn của cơ sở dữ liệu này bởi do được phân lớp nên có thể đánh giá kết quả
tra cứu một cách dễ dàng. Hình 3.1 minh họa một số ảnh mẫu trong tập dữ
liệu này. Hình 3.2. Các ảnh minh họa cho 10 thể loại trong tập ảnh Wang 39 Cơ sở dữ liệu này được sử dụng rộng rãi cho kiểm nghiệm các đặc trưng khác nhau bởi vì kích thước của cơ sở dữ liệu và tính khả dụng của thong tin lớp cho phép sự đánh giá hiệu năng. Tập Oxford Building bao gồm 5062 ảnh độ phân giải cao (1024x768) được lấy ra từ bộ sưu tập Flick. Đây là các địa danh cụ thể của Oxford. Tập ảnh này được chú thích thủ công tạo ra một cơ sở dữ liệu ảnh chuẩn đại diện cho 11 địa danh khác nhau. Mỗi địa danh có 5 truy vấn khác nhau được chọn, các ảnh được gán nhãn một trong bốn khả năng: (1) Good - ảnh đẹp, rõ ràng các đối tượng, tòa nhà; (2) OK – hơn 25% của đối tượng là nhìn thấy được; (3) Junk – ít hơn 25% của đối tượng nhìn thấy hoặc có một mức độ rất cao bị che lấp hoặc méo mó; (4) Absentn – đối tượng không được biểu diễn. Số lần xuất hiện của các địa danh khác nhau trong phạm vi 7 và 220 các ảnh Good và OK. Tập Caltech 101 bao gồm các ảnh theo 101 chủ đề, mỗi chủ đề có khoảng 40 đến 800 ảnh. Kích thước mỗi ảnh khoảng 300x200 điểm ảnh. Trong thực nghiệm luận văn trích rút các đặc trưng ảnh theo các đặc trưng màu sắc, kết cấu và hình dạng, toàn bộ gồm sáu đặc trưng mức thấp trong Bảng 3.1. Đây là những đặc trưng rất hay được sử dụng trong các nghiên cứu CBIR. Bảng 3. 1. Các miêu tả ảnh và hàm khoảng cách sử dụng trong thực nghiệm Miêu tả Kiểu đặc trưng Số chiều Hàm khoảng
cách Lược đồ HSV Màu 32 L1 Các mô men màu Màu 6 L2 Màu 64 L1 Lược đồ tự tương quan
màu Các phép lọc Gabor Kết cấu 48 L2 Các mô men Wavelet Kết cấu 40 L2 40 Gist Hình dạng 512 L2 Sau khi trích rút đặc trưng, mỗi chiều được chuẩn hóa vào phạm vi [0,1] bằng kĩ thuật chuẩn hóa đặc trưng. 3.3 Phân tích thiết kế chương trình thử nghiệm 3.3.1 Giao diện chương trình 1 2 3 Hình 3.3. Hình ảnh giao diện chương trình thực nghiệm - Vùng 1: Chọn, hiển thị ảnh truy vấn - Vùng 2: Lựa chọn phương pháp truy vấn - Vùng 3: Hiển thị hình ảnh để người dùng gán nhãn theo ngưỡng xác định đồng thời hiển thị kết quả trả về. 3.3.2 Các bước thực hiện truy vấn Các bước thực hiện truy vấn: Bước 1. Mở ảnh truy vấn 41 - Chọn ảnh truy vấn (lấy ảnh trong CSDL làm ảnh truy vấn) bằng cách chọn File -> Open trên Menu chức năng. - Chương trình tự động trích chọn đặc trưng ảnh truy vấn. - Hiển thị tên, ảnh truy vấn lên khung ảnh truy vấn. Hình 3.4. Đưa một ảnh truy vấn vào hệ thống tra cứu đề xuất Bước 2. Tra cứu ảnh - Với ảnh truy vấn đã chọn, từ giao diện chương chọn nút Retrival (thực hiện truy vấn), chương trình tính toán khoảng cách giữa ảnh truy vấn với tất cả các ảnh trong CSDL bằng hàm distance, sắp xếp theo thứ tự tăng dần của các khoảng cách đồng thời cập nhật chỉ số của các ảnh trong CSDL theo thứ tự khoảng cách đã sắp xếp, hiển thị 20 hình ảnh đầu tiên có khoảng cách nhỏ nhất. 42 Hình 3.5. Kết quả tra cứu khởi tạo của top-20 Bước 3. Phản hồi liên quan - Ảnh hiển thị trên giao diện ở vùng 3, nếu người dùng chưa hài lòng với kết quả truy vấn thì tiếp tục thực hiện việc kích chọn (gọi hàm selected) những ảnh có liên quan đến ảnh truy vấn (mẫu ảnh dương), số ảnh còn lại không được chọn tự động được hệ thống gán nhãn không liên quan (mẫu ảnh âm). - Người dùng chọn một trong 4 phương pháp tra cứu ảnh ở khung Select Feature sau đó chọn nút Relevance Feedback để thực hiện truy vấn ảnh. Hệ thống tự động tính toán tổng số (mẫu ảnh dương) người dùng gán nhãn sau các vòng lặp và tổng số (mẫu ảnh âm) hệ thống tự gán nhãn (các mẫu ảnh âm, ảnh dương được cộng dồn sau mỗi lần lặp). Các ảnh đã gán nhãn sau đó được sử dụng để huấn luyện mô hình phân lớp mới tìm ra giá trị quyết định của hàm 43 phân lớp, sắp xếp theo chiều giảm dần của giá trị quyết định và hiểu thị hình ảnh kết quả. - Quá trình này được lặp đi lặp lại cho đến khi người dùng hài lòng với kết quả tra cứu thì dừng. Hình 3. 6. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ nhất Hình 3. 7. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ hai 44 Hình 3. 8. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ ba Hình 3. 9. Kết quả tra cứu khởi tạo của top-20 vòng phản hồi thứ tư 45 3.4. Đánh giá kết quả đạt được và so sánh với phương pháp khác 3.4.1 Các phương pháp cơ sở Phương pháp đề xuất được so sánh với ba phương pháp tra cứu ảnh sử dụng phản hồi liên quan được xem là các phương pháp cơ sở - Nghiên cứu CBIR – SVM: Một phân lớp SVM được học từ dữ liệu huấn luyện của các ảnh liên quan và không liên quan, tập huấn luyện chỉ có được qua các lần đánh giá của người dùng. Thuật toán phân lớp SVM được thực hiện bởi LibSVM. Sử dụng tìm kiếm lưới để tìm các tham số tối ưu của C trong SVM và γ ttrong hàm nhân RBF (radian basis function). Nghiên cứu CBIR - AdaBoost: Đây là một tiếp cận AdaBoost có sử dụng thông tin phản hồi liên quan. Bộ phân lớp được cài đặt, trong đó số lần lặp được thiết lập là 50. Phương pháp tra cứu ảnh dựa vào nội dung này trong thực nghiệm được gọi tắt là phương pháp AdaBoost. Nghiên cứu trong MARS: Nghiên cứu này sử dụng kĩ thuật hiệu chỉnh trọng số và được cài đặt lại. 3.4.2 Phương pháp đánh giá Để đánh giá hiệu năng của hệ thống tra cứu, người ta có thể dựa trên các tiêu chí khác nhau. Trong khuôn khổ luận văn thực nghiệm chỉ đánh giá hiệu năng về mật độ chính xác tra cứu trong các kết quả top – k. Các phương pháp sử dụng các tập ảnh và truy vấn như nhau trên cùng một môi trường. Thực nghiệm được tiến hành mô phỏng tương tác phản hồi người dung với các phương pháp, nghĩa là các ảnh cùng chủ đề với các ảnh truy vấn được xem là liên quan và ngược lại. Số lượng các truy vấn trong mỗi tập dữ liệu miêu tả trong mục 3.2. Hai độ đo được thường xuyên sử dụng là độ chính xác và độ triệu hồi để đánh giá hiệu năng. Chủ đề ảnh của mỗi truy vấn được xem như mục tiêu tra cứu (khái niệm của ảnh truy vấn được xem như một chủ đề ảnh). Mỗi ảnh tương ứng với một 46 vector 702 chiều miêu tả trong bảng 3.1. Mục đích của các bộ học máy như SVM và AdaBoost là học một khái niệm đã cho qua đánh giá của người dung trong phản hồi liên quan. Trong quá trình này, mỗi vòng phản hồi liên quan có bộ học máy lựa chọn top – k các ảnh để hỏi người dùng cho gán nhãn “liên quan” hoặc “không liên quan” đối với khái niệm của ảnh truy vấn. Các bộ máy học sau đó sử dụng các ảnh được gán nhãn để tinh chỉnh cho phù hợp khái niệm của truy vấn. Kết thúc mỗi vòng phản hồi liên quan, hệ thống đưa ra kết quả top – k các ảnh có thứ hạng xếp hạng cao nhất từ tập ảnh theo khái niệm đã được học. Độ chính xác của mỗi vòng phản hồi liên quan là tỉ số chủ đề ảnh mục tiêu (chủ đề của ảnh truy vấn) trong số top – k và top – k kết quả. Trong quá trình phản hồi liên quan, người dùng lựa kích chọn để gán nhãn đối với ảnh liên quan và không chọn đối với ảnh không liên quan theo khái niệm của ảnh truy vấn. Hệ thống được xây dựng và biên dịch trên ngôn ngữ lập trình Matlap 2013, cơ sở dữ liệu SQL Server 2008, máy tính cá nhân sử dụng hệ điều hành Window 7 với cấu hình Core i5, 4GB Ram, HDD 500GB. Bảng 3. 2. Các tham số sử dụng trong thực nghiệm Phương pháp l NB (top – k) Số ảnh truy vấn Caltech Wang Oxford
Buiding 100 55 100 Đề xuất 10 20, 40, 60, 80, 100, 120,
140, 160, 180, 200 100 55 100 CBIR - SVM 10 20, 40, 60, 80, 100, 120,
140, 160, 180, 200 CBIR - AdaBoost 10 20, 40, 60, 80, 100, 120, 100 55 100 140, 160, 180, 200 MARS 100 55 100 10 20, 40, 60, 80, 100, 120,
140, 160, 180, 200 47 Bảng 3.2 là các tham số sử dụng chung cho các phương pháp. Kí hiệu l là số lần lặp, NB (top – k) là tập ảnh có thứ hạng dự báo (phân lớp) cao nhất trong một lần lặp được trả về bởi hệ thống. Trong nhiều nghiên cứu tập NB liên quan tới kích thước của tập thực nghiệm (thông thường từ 2% tới 5%). Bảng 3. 3. Số ứng viên Pareto thep top – k đối với Wang
(gồm 1000 ảnh) Top - k Số ứng viên Tỉ lệ số mẫu dữ liệu giảm 20 94% 60 40 92% 80 60 88% 120 80 84% 160 100 70% 300 120 64% 360 140 58% 420 160 46% 480 180 46% 540 200 40% 600 Bảng 3.3, bảng 3.4 và bảng 3.5 thiết lập số ứng viên theo top – k các ảnh kết quả trả về cho ba tập dữ liệu Wang, Oxford Buiding và Caltech. 48 Bảng 3. 4. Số ứng viên Pareto theo top – k đối với Oxford Buiding (gồm 2560 ảnh) Top - k Số ứng viên Tỉ lệ số mẫu dữ liệu giảm 20 98% 60 40 97% 80 60 95% 120 80 94% 160 100 88% 300 120 86% 360 140 84% 420 160 81% 480 180 79% 540 200 77% 600 Bảng 3. 5. Số ứng viên Pareto theo top – k đối với Caltech (gồm 590 ảnh) Top - k Số ứng viên Tỉ lệ số mẫu dữ liệu giảm 20 93% 40 40 80% 120 60 69% 80 59% 180
240 100 49% 300 120 39% 360 140 29% 420 160 19% 480 180 39% 360 200 32% 400 49 Để nâng cao hiệu năng độ chính xác, kĩ thuật hiệu chỉnh trọng số và dịch chuyển truy vấn được sử dụng, tập ứng viên Pareto kết hợp AdaBoost và kết hợp với SVM trên ba tập dữ liệu khác nhau. Độ chính xác của kĩ thuật đề xuất được xem xét sau mỗi vòng của phản hồi liên quan đến các top-k kết quả. Để chứng minh tính hiệu quả của độ chính xác, đề xuất sử dụng tập ứng viên Pareto đối với kĩ thuật phân lớp sử dụng SVM ký hiệu là Pareto-SVM và đề xuất sử dụng tập ứng viên Pareto với kĩ thuật phân lớp sử dụng AdaBoost ký hiệu là Pareto-AdaBoost. Hình 3.10 và các Bảng 3.6, 3.7, 3.8 cho biết trung bình độ chính xác theo top-k trên ba tập dữ liệu khác nhau của đề xuất Pareto-AdaBoost. Hình 3. 10. Trung bình độ chính xác trên kết quả top-k của đề xuất Pareto-AdaBoost trên ba tập dữ liệu Wang, Oxford Buiding, Caltech theo năm vòng phản hồi liên quan. 50 Bảng 3. 6. Trung bình độ chính xác top - k kết quả của đề xuất Pareto- Vòng 20 40 60 80 100 120 140 160 180 200 0.681 0.679 0.567 0.622 0.588 0.534 0.489 0.451 0.415 0.389 1 0.71 0.724 0.631 0.63 0.61 0.56 0.51 0.46 0.445 0.405 2 0.789 0.785 0.709 0.68 0.639 0.598 0.542 0.52 0.456 0.425 3 0.839 0.798 0.763 0.719 0.677 0.614 0.546 0.498 0.463 0.422 4 0.865 0.834 0.781 0.741 0.679 0.609 0.547 0.498 0.458 0.424 5 AdaBoost trên năm vòng phản hồi liên quan đối với tập dữ liệu Wang Bảng 3. 7. Trung bình độ chính xác top-k kết quả của đề xuất Pareto- AdaBoost trên năm vòng phản hồi liên quan đối với tập dữ liệu Vòng 20 40 60 80 100 120 140 160 180 200 0.246 0.331 0.345 0.312 0.284 0.264 0.248 0.235 0.224 0.217 1 0.297 0.356 0.365 0.34 0.311 0.29 0.277 0.264 0.254 0.246 2 0.371 0.418 0.385 0.353 0.326 0.298 0.278 0.266 0.259 0.247 3 0.411 0.461 0.414 0.366 0.332 0.303 0.285 0.274 0.262 0.248 4 0.442 0.48 0.418 0.365 0.338 0.309 0.285 0.273 0.265 0.246 5 Oxford Buiding 51 Bảng 3. 8. Trung bình độ chính xác top-k kết quả của đề xuất Pareto- Vòng 20 40 60 80 100 120 140 160 180 200 1 0.341 0.312 0.265 0.249 0.231 0.21 0.202 0.191 0.171 0.161 2 0.43 0.416 0.355 0.316 0.284 0.249 0.229 0.21 0.185 0.169 3 0.495 0.479 0.403 0.359 0.313 0.277 0.254 0.229 0.189 0.177 4 0.544 0.495 0.422 0.358 0.311 0.275 0.254 0.222 0.189 0.179 5 0.566 0.506 0.423 0.368 0.323 0.282 0.255 0.229 0.191 0.182 AdaBoost trên năm vòng phản hồi liên quan đối với tập dữ liệu Caltech. Hình 3.11 và các Bảng 3.9, 3.10, 3.11 cho biết trung bình độ chính xác theo top-k trên ba tập dữ liệu khác nhau của đề xuất Pareto-SVM. Hiệu năng của độ chính xác các kỹ thuật đề xuất sau mỗi vòng của phản hồi liên quan tang rõ rệt. Trên đồ thị ta cũng thấy hiệu năng của thuật toán giảm khi cỡ và độ phức tạp của tập dữ liệu tang lên. Kết quả tra cứu được xem xét không chỉ trên top một vài ảnh kết quả trả về có độ chính xác cao mà còn được xem xét một số lớn ảnh kết quả trả về. Độ phức tạp của dữ liệu cũng ảnh hưởng lớn đến kết quả tra cứu, như các tập dữ liệu Oxford Building, Caltech là các tập dữ liệu phức tạp, các chủ đề khó nhận dạng. Hình 3. 11. Trung bình độ chính xác trên kết quả top-k của đề xuất Pareto-SVM trên ba tập dữ liệu Wang, Oxford Building, Caltech theo năm vòng phản hồi liên quan 52 Hiệu năng độ chính xác của kỹ thuật đề xuất được so sánh với các kỹ thuật cơ sở trên các kết quả trả về (top-k) khác nhau. Các đề xuất sử dụng tập ứng viên Pareto, sau mỗi vòng phản hồi liên quan truy vấn được dịch chuyển và độ tương tự đước tính. Các kỹ thuật cơ sở như CBIR-SVM, CBIR-AdaBoost, MARS sử dụng toàn bộ các mẫu trong cơ sở dữ liệu để phân lớp. Bảng 3. 9. Trung bình độ chính xác top-k kết quả của đề xuất Pareto- Vòng 20 40 60 80 100 120 140 160 180 200 0.704 0.619 0.553 0.541 0.516 0.491 0.457 0.423 0.394 0.372 1 0.801 0.788 0.754 0.706 0.647 0.592 0.537 0.487 0.44 0.408 2 0.854 0.809 0.773 0.713 0.669 0.605 0.541 0.488 0.442 0.413 3 0.883 0.813 0.781 0.723 0.674 0.608 0.549 0.498 0.45 0.414 4 0.896 0.823 0.79 0.724 0.679 0.611 0.546 0.496 0.453 0.412 5 SVM trên năm vòng phản hồi liên quan đối với tập dữ liệu Wang. Bảng 3. 10. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-SVM trên năm vòng phản hồi liên quan đối với tập dữ liệu Vòng 20 40 60 80 100 120 140 160 180 200 0.222 0.292 0.313 0.283 0.265 0.248 0.235 0.231 0.221 0.211 1 0.312 0.353 0.369 0.341 0.313 0.29 0.277 0.26 0.249 0.24 2 0.378 0.401 0.383 0.359 0.341 0.311 0.288 0.276 0.262 0.248 3 0.411 0.418 0.389 0.37 0.343 0.313 0.296 0.277 0.263 0.248 4 0.436 0.428 0.385 0.371 0.348 0.315 0.296 0.281 0.266 0.249 5 Oxford Building 53 Bảng 3. 11. Trung bình độ chính xác top-k kết quả của đề xuất Pareto-SVM trên năm vòng phản hồi liên quan đối với tập dữ liệu Vòng 20 40 60 80 100 120 140 160 180 200 1 0.295 0.291 0.233 0.228 0.198 0.187 0.176 0.17 0.162 0.154 2 0.405 0.388 0.316 0.28 0.252 0.23 0.21 0.188 0.174 0.162 3 0.498 0.428 0.331 0.304 0.277 0.252 0.22 0.197 0.176 0.163 4 0.533 0.443 0.341 0.305 0.275 0.255 0.226 0.199 0.179 0.167 5 0.531 0.457 0.348 0.308 0.279 0.255 0.227 0.2 0.179 0.167 Caltech Các Hình 3.12, 3.13 so sánh hiệu năng độ chính xác của các kỹ thuậ đề xuất đối với các kỹ thuật cơ sở trên ba tập dữ liệu khác nhau. Ta có thể thấy rõ ràng các kỹ thuật đề xuất có hiệu năng về độ chính xác luôn cao hơn sau vòng phản hồi liên quan. Sau vòng phản hồi liên quan, truy vấn được dịch chuyển, độ tương tự được tính lại phù hợp hơn với khái niệm truy vấn, tập ứng viên Pareto cũng được điều chỉnh phù hợp hơn với chủ đề của ảnh truy vấn. Các kỹ thuật cơ sở hiệu năng độ chính xác thấp hơn do tập dữ liệu lớn và không được hiệu chỉnh độ tương tự cho phù hợp với khái niệm truy vấn. Hình 3. 12. So sánh độ chính xác trên các kết quả top-k của kỹ thuật
đề xuất Pareto-AdaBoost với các kỹ thuật cơ sở tren ba tập dữ liệu
Wang, Oxford Building, Caltech 54 Hình 3. 13. So sánh độ chính xác trên các kết quả top-k của kỹ thuật đề xuất Pareto-SVM với các kỹ thuật cơ sở trên ba tập dữ liệu Wang, Oxford Building, Caltech Thông thường trong các ứng dụng tra cứu, kết quả tra cứu thường hiển thị 20 ảnh liên quan nhất phù hợp với một màn hình hiển thị. Đề xuất cũng đã so sánh với các phương pháp cơ sở bao gồm: Tra cứu phân lớp ảnh sử dụng SVM và AdaBoost, tra cứu theo hiệu chỉnh trọng số (MARS). Trong thực nghiệm này 20 ảnh liên quan nhất được hiển thị trong cả sáu vòng của phản hồi liên quan. Hình 3.14 cho thấy đề xuất Pareto-AdaBoost đạt 90%, gần 50%, gần 60% đối với các tập dữ liệu Wang, Oxford Building và Caltech tương ứng. Hình 3. 14. Đồ thị độ chính xác của các phương pháp Pareto- AdaBoost, SVM, AdaBoost và MARS trên các tập dữ liệu Wang, Oxford Building, Caltech 55 Hình 3.15 cho thấy đề xuất Pareto-SVM đạt 90.08%, gần 42.7%, gần 56.2% đối với tập dữ liệu Wang, Oxford Building và Caltech tương ứng. Trong khi các phương pháp cơ sở, trên tập dữ liệu Wang, SVM và AdaBoost đạt tới 70.6% và 74.2%, MARS đạt 83.2%.Trên tập dữ liệu Oxford Building, CBIR- SVM và CBIR-AdaBoost đạt tới 22.9% và 27.8%, MARS đạt 40.1%. Trên tập dữ liệu Caltech, CBIR-SVM, CBIR-AdaBoost đạt tới 29.8% và 38.1%, MARS đạt 42.5%. Hình 3. 15. Đồ thị độ chính xác của các phương pháp Pareto- SVM, SVM, AdaBoost và MARS trên tập dữ liệu Wang, Oxford Building và Caltech. Hệ thống đề xuất được phát triển thành một ứng dụng tra cứu ảnh dựa vào nội dung hoàn chỉnh gồm hai pha: - Pha một (off-line): Pha này gồm các công cụ trích rút đặc trưng, chuẩn hóa đặc trưng và lưu trữ cơ sở dữ liệu đặc trưng để dùng cho quá trình tra cứu. - Pha hai (on-line): Người dùng đưa vào một ảnh truy vấn, ảnh truy vấn này được trích rút đặc trưng với phương pháp tương tự như đã làm ở pha một. Quá trình tra cứu khởi được thực hiện sau đó. Sau khi hiển thị tra cứu khởi tạo, người dùng tương tác với hệ thống qua việc lựa chọn các ảnh bằng cả khái niệm “liên quan” và “không liên quan” bằng việc lựa chọn đánh dấu bên dưới các ảnh tương ứng. 56 Trong khuôn khổ của luận văn này tác giả tập trung tìm hiểu, nghiên cứu một số nội dung cơ bản của CBIR. Các kết quả chính đạt được: - Đã nắm được một số phương pháp trích chọn đặc trưng hình ảnh, một số phương pháp phản hồi liên quan trong tra cứu ảnh dựa vào nội dung. - Trình bày được phương pháp tìm kiếm hình ảnh theo đặc trưng mầu sắc, kết cấu, hình dạng và phương pháp kết hợp các đặc trưng trên áp dụng trong tra cứu ảnh theo nội dung sử dụng SVM và phản hồi liên quan. - Đưa bài toán tra cứu ảnh sử dụng tổ hợp đặc trưng theo tiếp cận tối ưu Pareto bằng cách tìm tập ứng viên Pareto dựa vào các tiêu chí là khoảng cách theo thành phần đặc trưng. Tập này được sử dụng làm tập kiểm tra cho máy phân lớp. Luận văn đã xây dựng tính chất hình thức trên không gian tìm kiếm của ảnh truy vấn theo tiếp cận tối ưu Pareto. Các tính chất đã được khái quát hóa cho bài toán CBIR như Pareto front đa mức sâu, hợp Pareto theo độ sâu. Các thực nghiệm làm sáng tỏ tính chất rút gọn không gian tìm kiếm, có thể xem như sơ lọc trên cơ sở dữ liệu lớn và giảm được số mẫu dữ liệu, cải thiện độ chính xác phân lớp. - Luận văn xây dựng được chương trình thực nghiệm, thực hiện tìm kiếm ảnh sử dụng tổ hợp đặc trưng và rút gọn không gian tìm kiếm thông qua tìm tập ứng viên và áp dụng cho kĩ thuật học máy trong việc phân lớp ảnh theo truy vấn. Chương trình được chạy thực nghiệm trên 3 CSDL Wang, Oxford Building, Caltech và đã so sánh, đánh giá được hiệu năng thực hiện tìm kiếm ảnh của các phương pháp trên. 57 Hạn chế: - Tra cứu ảnh dựa vào nội dung vẫn còn nhiều vấn đề cần tiếp tục nghiên cứu. Trong giới hạn của một luận văn chưa giải quyết hết mọi vấn đề, luận văn chỉ giải quyết một phần trong các vấn đề rút gọn không gian tìm kiếm. - Đóng góp của luận văn vẫn còn hạn chế: Thực nghiệm trên các cơ sở dữ liệu chưa đủ lớn, chưa đánh giá hiệu năng về thời gian đối với các đề xuất. Trong các nghiên cứu tương lai sẽ tiếp tục nghiên cứu để bổ sung cho những hạn chế này. 58 Tiếng Việt [1] Nguyễn Thanh Thuỷ - Lương Mạnh Bá (1998), Nhập môn xử lý ảnh số, NXB Khoa học và kỹ thuật, Hà Nội. [2] Đỗ Năng Toàn - Phạm Việt Bình (2007), Xử lý ảnh. [3] Phạm Xuân Hinh (2016), Tra cứu ảnh dựa trên nội dung sử dụng nhiều đặc trưng và phản hồi liên quan, Luận văn thạc sĩ công nghệ thông tin, Trường ĐH Dân lập Hải Phòng. [4] Vũ Văn Hiệu (2017), Nghiên cứu một số kỹ thuật phân hạng trong tra cứu ảnh dựa vào nội dung, Luận án tiến sĩ toán học, Học viện Khoa học Công nghệ - Viện hàn lâm khoa học và công nghệ Việt Nam. [5] Vũ Văn Hiệu, Ngô Huy Hoàng, Ngô Quốc Tạo, Nguyễn Hữu Quỳnh (2016), “Một phương pháp mới chuẩn hoá dữ liệu và hiệu chỉnh trọng số cho tổ hợp đặc trưng trong tra cứu ảnh theo nội dung” , Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ thông tin và Truyền thông, Tập V-1 (Số 35). [6] Vũ Văn Hiệu, Nguyễn Trường Thắng, Nguyễn Hữu Quỳnh, Ngô Quốc Tạo (2016), “Tra cứu ảnh theo nội dung sử dụng tập Pareto và mô hình học thống kê CART”, Chuyên san các công trình nghiên cứu phát triển và ứng dụng CNTT-TT, tập V-2 (Số 36). Tiếng Anh [7] Analysis of distance metrics in content-based image retrieval using statistical quantized histogram texture features in the DCT domain, Journal of King Saud University - Computer and Information Sciences, www.ksu.edu.sa, 28/11/2012. 59 [8] Hiremath and Pujari (2007), Based Image Retrieval Using Color, Texture and Shape Features, Proceedings of the 15th International Conference on Advanced Computing and, Communications [9] Van-Hieu Vu, Truong-Thang Nguyen, Huu-Quynh Nguyen, Quoc-Tao Ngo (2016), “Content based image retrieval using multiple features and Pareto approach”, Journal of Compu-ter Science and Cybernetics, Vol 32 (No 2).KẾT LUẬN
TÀI LIỆU THAM KHẢO
