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

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 ° Ii Vector đặc trưng chuẩn hóa của ảnh thứ i °t Ii 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ỳ ±t Qi Đặc trưng chuẩn hóa ở bộ t của ảnh truy vấn t t t DIDQIQ( i),,( i ) Khoảng cách theo bộ đặc trưng t của ảnh Ii so với ảnh truy vấn Q DIDQIQ( i),,( i ) 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 NB Tập ảnh có độ tương tự cao nhất theo đặc trưng toàn cục trong một tra cứu NB- Tập ảnh được xác nhận không liên quan ở phản hồi của người dùng NB+ Tập ảnh được xác nhận liên quan ở phản hồi của người dùng NBt Tập ảnh có độ tương tự cao nhất theo đặc trưng ở bộ t trong một tra cứu NB: Tập ảnh có thứ hạng độ tương tự cao và thuộc tập trong một tra cứu NB* 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 phương pháp phân lớp yếu thành một phân lớp mạnh hơn 퐿 퐹(푥) = ∑ 훼푖푓푖(푥) 푙=1 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à 휔 và b, trong đó 휔 có dạng như sau: 푚 휔 = ∑ 훼푖푥푖 푖=1 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