Tra cứu ảnh dựa trên khoảng cách và bài toán tối ưu Pareto

ĐẠ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