Luận án Tìm kiếm ảnh dựa trên đồ thị chữ ký nhị phân

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC KHOA CÔNG NGHỆ THÔNG TIN CHUYÊN ĐỀ 01 Ngành: Khoa học máy tính Mã ngành: 62.48.01.01 NGHIÊN CỨU TRUY VẤN ẢNH DỰA TRÊN CHỮ KÝ NHỊ PHÂN VÀ CÂY S-Tree Học viên thực hiện: Văn Thế Thành Người hướng dẫn khoa học: PGS. TS. Lê Mạnh Thạnh Huế ĐẠI HỌC HUẾ TR ỜNG ĐẠI HỌC KHOA HỌC VĂN THẾ THÀNH TÌM KIẾM ẢNH DỰA TRÊN ĐỒ THỊ CHỮ KÝ NHỊ PHÂN LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HUẾ - NĂM 2017 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC VĂN THẾ THÀNH TÌM KIẾM ẢNH DỰA TRÊN ĐỒ THỊ CHỮ KÝ NHỊ PHÂN Chuyên ngành: Khoa học máy tính Mã ngành: 62.48.01.01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: PGS. TS Lê Mạnh Thạnh HUẾ - NĂM 2017 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Nội dung tham khảo từ các công trình khác đều được trích dẫn rõ ràng. Các kết quả viết chung với các tác giả khác đều được sự đồng ý trước khi đưa vào luận án. Các kết quả của luận án là trung thực và chưa được công bố trong các công trình khác ngoài các công trình của tác giả. Tác giả Văn Thế Thành i Lời cảm ơn Đầu tiên, em xin chân thành gửi lời cảm ơn Thầy PGS. TS Lê Mạnh Thạnh vì sự hướng dẫn tận tình và khoa học. Thầy đã dẫn dắt em đi từng bước trên con đường nghiên cứu khoa học; Thầy đã hướng dẫn tận tình về phương pháp nghiên cứu, phương pháp viết bài báo khoa học và phương pháp tổng hợp tri thức trong quá trình học tập, nghiên cứu. Em xin chân thành gửi lời cảm ơn đến Phòng Đào tạo Sau Đại học, Ban Giám hiệu của Trường Đại học Khoa học - Đại học Huế đã tạo điều kiện thuận lợi cho em trong suốt quá trình học tập và thực hiện luận án. Em xin chân thành gửi lời cảm ơn đến tập thể thầy cô giáo Khoa Công nghệ Thông tin, Trường Đại học Khoa học - Đại học Huế đã có những góp ý, giúp đỡ và động viên kịp thời trong quá trình học tập và nghiên cứu. Em xin chân thành gửi lời cảm ơn đến các Giáo sư Đại học Eötvös Loránd, Hungary và các phản biện ẩn danh đã có những đề nghị khoa học giá trị trong nội dung nghiên cứu. Tôi xin gửi lời cảm ơn đến các đồng nghiệp là cán bộ, giảng viên Trường Đại học Công nghiệp Thực phẩm Tp.HCM đã cổ vũ động viên và sát cánh bên tôi trong quá trình học tập và nghiên cứu. Tôi xin gửi lời cảm ơn đến tất cả bạn bè và những người xung quanh luôn chia sẻ, động viên trong những lúc khó khăn. Xin gửi lời cảm ơn đến người vợ thân yêu đã hỗ trợ và chu toàn trong cuộc sống hàng ngày để anh thực hiện quá trình học tập, nghiên cứu. Cuối cùng, con xin bày tỏ lòng biết ơn vô hạn đối với cha mẹ và gia đình đã luôn ủng hộ, giúp đỡ trong suốt quá trình thực hiện luận án. ii MỤC LỤC Lời cảm ơn ...................................................................................................................i DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT .........................................................iv DANH MỤC HÌNH ẢNH .......................................................................................... v DANH MỤC BẢNG BIỂU ..................................................................................... vii PHẦN MỞ ĐẦU ......................................................................................................... 1 Chương 1. Tổng quan về tìm kiếm ảnh theo nội dung dựa trên chữ ký nhị phân....... 5 1.1. Mở đầu .............................................................................................................. 5 1.2. Tổng quan các công trình nghiên cứu ............................................................... 5 1.3. Định hướng nghiên cứu .................................................................................. 12 1.4. Các đối tượng cơ sở ........................................................................................ 12 1.4.1. Tạo dải màu cơ sở .................................................................................... 12 1.4.2. Thực nghiệm về tạo dải màu cơ sở .......................................................... 13 1.4.3. Trích xuất lược đồ màu ............................................................................ 16 1.4.4. Trích xuất đặc trưng SIFT ........................................................................ 16 1.4.5. Thực nghiệm về trích xuất đặc trưng SIFT .............................................. 19 1.4.6. Trích xuất đối tượng đặc trưng................................................................. 19 1.4.7. Chữ ký nhị phân ....................................................................................... 22 1.4.8. Chữ ký nhị phân của hình ảnh.................................................................. 24 1.4.9. Các giá trị đánh giá hiệu suất ................................................................... 25 1.4.10. Môi trường thực nghiệm .......................................................................... 25 1.5. Tổng kết chương ............................................................................................. 27 Chương 2. Cải tiến phương pháp tìm kiếm ảnh dựa trên cây S-Tree ....................... 28 2.1. Giới thiệu ........................................................................................................ 28 2.2. Tạo chữ ký nhị phân của hình ảnh .................................................................. 30 2.2.1. Tạo chữ ký nhị phân dựa trên đặc trưng màu toàn cục ............................ 30 2.2.2. Tạo chữ ký nhị phân dựa trên đặc trưng màu cục bộ ............................... 32 2.3. Độ đo EMD ..................................................................................................... 32 2.3.1. Tổng quan về độ đo EMD ........................................................................ 32 2.3.2. Áp dụng độ đo EMD cho chữ ký nhị phân .............................................. 32 2.4. Độ đo Hamming áp dụng cho chữ ký nhị phân .............................................. 36 2.5. Cây S-Tree ...................................................................................................... 36 2.6. Cây Sig-Tree ................................................................................................... 37 2.6.1. Giới thiệu cây Sig-Tree ............................................................................ 37 2.6.2. Thiết kế cấu trúc dữ liệu cây Sig-Tree ..................................................... 37 iii 2.6.3. Phép tổ hợp các chữ ký trên cây Sig-Tree ................................................ 38 2.6.4. Phép tách một nút trên cây Sig-Tree ........................................................ 39 2.6.5. Phép loại bỏ chữ ký trên cây Sig-Tree ..................................................... 41 2.6.6. Phép chèn chữ ký trên cây Sig-Tree ......................................................... 42 2.6.7. Tìm kiếm trên cây Sig-Tree...................................................................... 43 2.7. Tìm kiếm ảnh dựa trên cây Sig-Tree............................................................... 44 2.7.1. Mô hình tìm kiếm ảnh dựa trên lược đồ màu toàn cục ............................ 44 2.7.2. Tìm kiếm ảnh dựa trên lược đồ màu cục bộ ............................................ 45 2.7.3. Các chương trình tìm kiếm ảnh dựa trên cây Sig-Tree ............................ 46 2.7.4. Thời gian tìm kiếm của các phương pháp theo thực nghiệm ................... 50 2.7.5. Đánh giá các phương pháp thực nghiệm .................................................. 50 2.8. Tổng kết chương ............................................................................................. 53 Chương 3. Đề xuất phương pháp tìm kiếm ảnh dựa trên đồ thị chữ ký.................... 54 3.1. Giới thiệu ........................................................................................................ 54 3.2. Chữ ký nhị phân của hình ảnh ........................................................................ 54 3.3. Độ đo tương tự ................................................................................................ 56 3.4. Tìm kiếm ảnh dựa trên gom cụm chữ ký nhị phân ......................................... 57 3.4.1. Gom cụm chữ ký nhị phân ....................................................................... 57 3.4.2. Thuật toán tìm kiếm ảnh dựa trên gom cụm chữ ký nhị phân ................. 60 3.4.3. Thực nghiệm tìm kiếm ảnh dựa trên gom cụm chữ ký nhị phân ............. 60 3.5. Xây dựng đồ thị S-kGraph .............................................................................. 68 3.5.1. Cấu trúc đồ thị S-kGraph.......................................................................... 68 3.5.2. Thuật toán tạo đồ thị S-kGraph ................................................................ 72 3.5.3. Thuật toán tìm kiếm ảnh trên đồ thị S-kGraph......................................... 74 3.5.4. Phân rã cụm trong đồ thị S-kGraph .......................................................... 75 3.5.5. Thực nghiệm tìm kiếm ảnh trên đồ thị S-kGraph .................................... 76 3.6. Xây dựng đồ thị S-kGraph dựa trên mạng Sig-SOM ...................................... 88 3.6.1. Xây dựng cấu trúc mạng Sig-SOM .......................................................... 88 3.6.2. Thuật toán huấn luyện mạng Sig-SOM .................................................... 91 3.6.3. Thuật toán tìm kiếm ảnh trên mạng Sig-SOM ......................................... 94 3.6.4. Thực nghiệm tìm kiếm ảnh trên mạng Sig-SOM ..................................... 95 3.7. Tổng kết chương ........................................................................................... 107 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................. 108 Danh mục các công trình của tác giả liên quan đến luận án ................................... 110 TÀI LIỆU THAM KHẢO ....................................................................................... 112 iv DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT Ký hiệu Diễn giải tiếng Anh Diễn giải tiếng Việt BSSF Bit-Slice Signature File Tập tin chữ ký phân mảnh CBIR Content-Based Image Retrieval Tìm kiếm ảnh theo nội dung CBMIR Content-Based Medical Image Retrieval Tìm kiếm ảnh y khoa theo nội dung CBSSF Compressed Bit-Sliced Signature File Tập tin chữ ký phân mảnh dạng nén DoG Difference of Gaussian Đạo hàm Gauss DWF Discrete Wavelet Frame Phép biến đổi DWF DWT Discrete Wavelet Transform Phép biến đổi Wavelet rời rạc EMD Earth Mover’s Distance Độ đo EMD IPT Image Processing Toolbox Công cụ xử lý ảnh trong Matlab JPEG Joint Photographic Experts Group Chuẩn nén ảnh JPEG KMCC K-Means with Connectivity Constraint Gom cụm K-mean miền liên thông LoG Laplace of Gaussian Phép biến đổi Laplace Gauss GIS Geographic Information System Hệ thống thông tin địa lý RBIR Region-Based Image Retrieval Tìm kiếm ảnh trên vùng cục bộ ROC Receiver Operating Characteristic Đồ thị đặc tính RF Relevance Feedback Phương pháp phản hồi liên quan SSF Sequential Signature File Tập tin chữ ký tuần tự SOM Self Organizing Map Bản đồ tự tổ chức SIFT Scale Invariant Features Transform Đặt trưng hình ảnh SIFT Sig-SOM Signature - Self Organizing Map Bản đồ chữ ký nhị phân Sig-Tree Signature - Tree Cây chữ ký Sig-Tree S-kGraph Signature -kGraph Đồ thị chữ ký gom cụm SG Signature Graph Đồ thị chữ ký S-Tree Signature Tree Cây chữ ký S-Tree SURF Speeded Up Robust Feature Đặc trưng hình ảnh SURF SVM Support Vector Machine Vec-tơ hỗ trợ SVM TBIR Text-Based Image Retrieval Tìm kiếm ảnh dựa trên văn bản WWW World Wide Web Mạng toàn cầu WWW v DANH MỤC HÌNH ẢNH Hình 1.1. Mô hình tổng quát cho tìm kiếm ảnh dựa trên chữ ký nhị phân ..................... 5 Hình 1.2. Kết quả tạo dải màu gồm: 32 màu, 64 màu, 128 màu, 256 màu .................. 15 Hình 1.3. Một số kết quả về trích xuất lược đồ màu của hình ảnh............................... 16 Hình 1.4. Một số kết quả về trích xuất đặc trưng SIFT ............................................... 19 Hình 1.5. Ví dụ ảnh được tách thành 7 11 khối........................................................ 20 Hình 1.6. Một số ví dụ về mặt nạ phân đoạn .............................................................. 22 Hình 1.7. Một số kết quả phân đoạn ảnh, gồm: ảnh gốc, mặt nạ và ảnh phân đoạn ..... 22 Hình 1.8. Mô tả chữ ký nhị phân của đối tượng dữ liệu .............................................. 23 Hình 1.9. Mô tả chữ ký nhị phân của hình ảnh ........................................................... 24 Hình 1.10. Độ phủ recall và độ chính xác precision ................................................... 25 Hình 2.1. Minh họa cấu trúc dữ liệu cây Sig-Tree ...................................................... 37 Hình 2.2. Minh họa một nút gốc và nút lá của cây Sig-Tree ....................................... 38 Hình 2.3. Mô hình tìm kiếm ảnh dựa trên lược đồ màu toàn cục ................................ 45 Hình 2.4. Mô hình tìm kiếm ảnh dựa trên đặc trưng cục bộ ........................................ 45 Hình 2.5. Một kết quả tìm kiếm của chương trình H-MPEG7..................................... 48 Hình 2.6. Một kết quả tìm kiếm của chương trình HR-MPEG7 .................................. 48 Hình 2.7. Một kết quả tìm kiếm của chương trình E-MPEG7 ..................................... 48 Hình 2.8. Một kết quả tìm kiếm của chương trình ER-MPEG7 .................................. 49 Hình 2.9. Một kết quả tìm kiếm của chương trình EP-64 ............................................ 49 Hình 2.10. Một kết quả tìm kiếm của chương trình EP-256 ........................................ 49 Hình 2.11. Thời gian tìm kiếm của các phương pháp trên tập ảnh COREL ................. 50 Hình 2.12. Thời gian tìm kiếm của các phương pháp trên tập ảnh WANG ................. 50 Hình 2.13. Thời gian tìm kiếm của các phương pháp trên tập ảnh ImgColl01............. 50 Hình 2.14. Hiệu suất tìm kiếm trên cây Sig-Tree của tập ảnh COREL ........................ 51 Hình 2.15. Hiệu suất tìm kiếm trên cây Sig-Tree của tập ảnh WANG ........................ 51 Hình 2.16. Hiệu suất tìm kiếm trên cây Sig-Tree của tập ảnh ImgColl01 .................... 51 Hình 3.1. Minh họa chữ ký nhị phân của đối tượng đặc trưng .................................... 55 Hình 3.2. Mô hình tìm kiếm ảnh dựa trên gom cụm chữ ký nhị phân ......................... 61 Hình 3.3. Một kết quả gom cụm trên tập ảnh COREL ................................................ 61 Hình 3.4. Dữ liệu một cụm sau khi phân hoạch trên tập ảnh COREL ......................... 61 Hình 3.5. Một kết quả tìm kiếm dựa trên gom cụm tập ảnh COREL .......................... 63 Hình 3.6. Thời gian tìm kiếm trung bình dựa trên gom cụm tập ảnh COREL ............. 63 Hình 3.7. Thời gian tìm kiếm trung bình dựa trên gom cụm tập ảnh WANG .............. 64 Hình 3.8. Thời gian tìm kiếm trung bình dựa trên gom cụm tập ảnh CBIRimages ...... 64 vi Hình 3.9. Hiệu suất tìm kiếm dựa trên gom cụm tập ảnh CBIRimages ....................... 64 Hình 3.10. Hiệu suất tìm kiếm dựa trên gom cụm tập ảnh COREL và WANG ........... 65 Hình 3.11. Minh họa đồ thị S-kGraph ........................................................................ 69 Hình 3.12. Minh họa quy tắc phân bố hình ảnh vào đồ thị S-kGraph .......................... 70 Hình 3.13. Minh họa một cụm lớn được phân rã thành nhiều cụm nhỏ ....................... 76 Hình 3.14. Mô hình tìm kiếm ảnh dựa trên đồ thị S-kGraph ....................................... 77 Hình 3.15. Một kết quả tìm kiếm trên đồ thị S-kGraph của tập ảnh MSRDI ............... 77 Hình 3.16. Thời gian tìm kiếm trên đồ thị S-kGraph của tập ảnh COREL .................. 78 Hình 3.17. Thời gian tìm kiếm trên đồ thị S-kGraph của tập ảnh WANG ................... 78 Hình 3.18. Thời gian tìm kiếm trên đồ thị S-kGraph của tập ảnh CBIRimages ........... 78 Hình 3.19. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh CBIRimages ........... 78 Hình 3.20. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh COREL và WANG . 79 Hình 3.21. Thời gian tìm kiếm trên đồ thị S-kGraph của tập ảnh MSRDI ................... 80 Hình 3.22. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh MSRDI ................... 80 Hình 3.23. Thời gian tìm kiếm trên đồ thị S-kGraph của tập ảnh ImageCLEF ............ 80 Hình 3.24. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh ImageCLEF ............ 81 Hình 3.25. Thời gian tìm kiếm trên đồ thị S-kGraph của tập ảnh ImgColl02 .............. 81 Hình 3.26. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh ImgColl02 ............... 82 Hình 3.27. Mô hình mạng Sig-SOM ........................................................................... 88 Hình 3.29. Mô hình tìm kiếm ảnh dựa trên mạng Sig-SOM ........................................ 95 Hình 3.30. Một kết quả tìm kiếm trên mạng Sig-SOM của tập ảnh MSRDI ................ 95 Hình 3.31. Thời gian tìm kiếm trên mạng Sig-SOM của tập ảnh COREL ................... 96 Hình 3.32. Thời gian tìm kiếm trên mạng Sig-SOM của tập ảnh CBIRimages............ 96 Hình 3.33. Thời gian tìm kiếm trên mạng Sig-SOM của tập ảnh WANG.................... 96 Hình 3.34. Hiệu suất tìm kiếm trên mạng Sig-SOM của tập ảnh CBIRimages ............ 96 Hình 3.35. Hiệu suất tìm kiếm trên mạng Sig-SOM của tập ảnh COREL và WANG .. 97 Hình 3.36. Thời gian tìm kiếm trên mạng Sig-SOM của tập ảnh MSRDI ................... 98 Hình 3.37. Hiệu suất tìm kiếm trên mạng Sig-SOM của tập ảnh MSRDI .................... 98 Hình 3.38. Thời gian tìm kiếm trên mạng Sig-SOM của tập ảnh ImageCLEF ............ 98 Hình 3.39. Hiệu suất tìm kiếm trên mạng Sig-SOM của tập ảnh ImageCLEF ............. 99 Hình 3.39. Thời gian tìm kiếm trên mạng Sig-SOM của tập ảnh ImgColl02 ............... 99 Hình 3.41. Hiệu suất tìm kiếm trên mạng Sig-SOM của tập ảnh ImgColl02 ............. 100 vii DANH MỤC BẢNG BIỂU Bảng 1.1. Một kết quả về gom cụm dải màu trên không gian * * *CIE-La b và RGB ........... 14 Bảng 1.2. Các tập dữ liệu ảnh được thực nghiệm trong luận án ........................................... 26 Bảng 2.1. Mô tả các chương trình tìm kiếm ảnh dựa trên cây Sig-Tree............................... 46 Bảng 2.2. Đánh giá hiệu suất giữa các phương pháp trên các tập dữ liệu ảnh .................... 52 Bảng 2.3. So sánh hiệu suất tìm kiếm giữa các phương pháp............................................... 52 Bảng 3.1. Hiệu suất tìm kiếm dựa trên gom cụm tập ảnh COREL ...................................... 66 Bảng 3.2. Hiệu suất tìm kiếm dựa trên gom cụm tập ảnh CBIRimages .............................. 66 Bảng 3.3. Hiệu suất tìm kiếm dựa trên gom cụm tập ảnh WANG ....................................... 66 Bảng 3.4. Hiệu suất tìm kiếm trung bình dựa trên gom cụm các tập ảnh ............................ 67 Bảng 3.5. So sánh độ chính xác tìm kiếm trên tập ảnh COREL ........................................... 67 Bảng 3.6. So sánh thời gian tìm kiếm trên tập ảnh COREL ................................................. 67 Bảng 3.7. So sánh hiệu suất tìm kiếm trên tập ảnh CBIRimages ......................................... 67 Bảng 3.8. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh COREL ............................ 83 Bảng 3.9. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh CBIRimages .................... 83 Bảng 3.10. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh WANG .......................... 83 Bảng 3.11. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh MSRDI .......................... 84 Bảng 3.12. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh ImageCLEF ................... 84 Bảng 3.13. Hiệu suất tìm kiếm trên đồ thị S-kGraph của tập ảnh ImgColl02 ..................... 85 Bảng 3.14. Hiệu suất tìm kiếm trên đồ thị S-kGrap