Tài liệu Xây dựng hệ thống truy vấn ảnh tương tự theo nội dung dựa trên cấu trúc cây r tree

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÀ RỊA-VŨNG TÀU BÁO CÁO ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG XÂY DỰNG HỆ TRUY VẤN ẢNH TƯƠNG TỰ THEO NỘI DUNG DỰA TRÊN CẤU TRÚC CÂY R-TREE Chủ nhiệm đề tài: Nguyễn Anh Tuấn Giáo viên hướng dẫn: ThS Lê Thị Vĩnh Thanh BÀ RỊA-VŨNG TÀU, 2020 THÔNG TIN ĐỀ TÀI Tên đề tài: Xây dựng hệ truy vấn ảnh tương tự theo nội dung dựa trên cấu trúc cây RTree. Mã đề tài: SV2020-189 Thời gian nghiên cứu: Từ 02-2020 đến 10-2020. Chủ nhiệm: - Họ và tên: NGUYỄN ANH TUẤN - Đơn vị công tác: Lớp DH18LT, Khoa CNKT-NNCNC - Mã số sinh viên: 18033747 - Điện thoại: 0333326585 - Email: [email protected] Các thành viên tham gia: 1. Nguyễn Anh Tuấn, sinh viên lớp DH18LT (MSSV: 18033747) 2. ThS Lê Thị Vĩnh Thanh, giảng viên Khoa Công nghệ Kỹ thuật – Nông nghiệp Công nghệ cao. Nội dung chính: Hình ảnh mang một thông điệp truyền tải ý nghĩa có tính xã hội rất cao. Không những thế, nó giúp mọi người cập nhật thông tin và giữ liên lạc với nhau. Với dữ liệu hình ảnh phát triển mỗi ngày, nhu cầu chia sẻ và tìm kiếm ảnh của chúng ta rất lớn vì những lợi ích mà hình ảnh mang lại trong các lĩnh vực ứng dụng. Chính vì vậy, chúng tôi đã nghiên cứu và xây dựng mô hình cho bài toán truy vấn ảnh tương tự. Điều này giúp cải thiện khả năng tìm kiếm và truy xuất ảnh trong kho ảnh ngày càng mở rộng của chúng ta. Để thực hiện, chúng tôi đã xây dựng và phát triển mô hình tìm kiếm ảnh dựa trên cây cấu trúc cây R-Tree; thuật toán về tạo cây; thuật toán duyệt và tìm kiếm. Vận dụng kiến thức tích lũy và sự hướng dẫn, hỗ trợ từ Giảng viên hướng dẫn, chúng tôi kế thừa và cải tiến cấu trúc dữ liệu cây R-Tree, các tính chất và phân bố dữ liệu lên cây để đảm bảo hiệu quả của hệ truy vấn ảnh tương tự theo nội dung. LỜI NÓI ĐẦU Ngày nay, trong cuộc cách mạng công nghiệp 4.0 và sự bùng nổ của các ngành Công nghệ thông tin, điện tử… Đã làm cho đời sống con người ngày càng được nâng cao. Trong đó, Trí tuệ nhân tạo, đang ngày càng chứng tỏ được giá trị của mình khi có những ứng dụng vào nhiều lĩnh vực trong đời sống hàng ngày và đem lại kết quả vượt trội. Trí tuệ nhân tạo có rất nhiều ứng dụng và cách triển khai. Nhưng nổi bật trong số đó là giải quyết bài toán tìm kiếm ảnh tương tự. Đó là khi chúng ta đưa ra một hình ảnh và mong muốn tìm được những hình ảnh khác có tính chất tương đồng. Nó có thể ứng dụng vào nhiều lĩnh vực như: trong Y khoa để chẩn đoán bệnh, trong thực phẩm để phát hiện hàng thật/giả/kém chất lượng, trong nông nghiệp để phát hiện sâu bệnh, các bài toán điểm danh bằng nhận diện khuôn mặt… Là một sinh viên thuộc Khoa CNKT-NNCNC của Trường Đại học Bà Rịa-Vũng Tàu, việc nghiên cứu và áp dụng những gì đã học vào đời sống thực tiễn là một điều rất cần thiết trong bối cảnh con người làm chủ công nghệ hiện nay. Để góp phần tạo nên nền tảng và đam mê trong việc học tập và nghiên cứu về Trí tuệ nhân tạo, em đã lựa chọn nghiên cứu về bài toán “XÂY DỰNG HỆ TRUY VẤN ẢNH TƯƠNG TỰ THEO NỘI DUNG DỰA TRÊN CẤU TRÚC CÂY R-TREE” với sự hướng dẫn của ThS Lê Thị Vĩnh Thanh (Giảng viên Khoa CNKT-NNCNC). Trong quá trình thực hiện, có nhiều khó khăn vấp phải, điều này kích thích sinh viên khả năng tư duy logic và sáng tạo để tìm ra phương án tối ưu, đồng thời chủ động tìm hiểu, học hỏi từ những người đi trước những gì bản thân còn thiếu. Tuy nhiên với những hạn chế về kinh nghiệm thực tế, nên không thể tránh khỏi những sai sót. Do đó em rất mong nhận được những góp ý của Quý Thầy/Cô và các bạn sinh viên để em có thể hoàn thiện hơn nữa mục tiêu của mình. MỤC LỤC CHƯƠNG I. MỞ ĐẦU ..................................................................................................1 1.1. Đặt vấn đề .............................................................................................................1 1.2. Phương pháp nghiên cứu.......................................................................................1 1.3. Tính cấp thiết của đề tài ........................................................................................2 1.4. Mục tiêu, nhiệm vụ và giới hạn của phần mềm ....................................................3 CHƯƠNG II. TỔNG QUAN BÀI TOÁN TÌM KIẾM ẢNH THEO NỘI DUNG ..5 2.1. Giới thiệu...............................................................................................................5 2.2. Tra cứu ảnh dựa vào văn bản ................................................................................5 2.3. Tra cứu ảnh dựa vào nội dung...............................................................................7 2.4. Trích xuất đặc trưng ảnh .......................................................................................8 2.5. Độ đo tương đồng giữa 2 vector đặc trưng ...........................................................9 2.6. Thuật toán gom cụm K-Means............................................................................10 CHƯƠNG III. HỆ TRA CỨU ẢNH DỰA TRÊN CẤU TRÚC CÂY R-TREE ....11 3.1. Các khái niệm cơ bản về cây R-Tree [20]...........................................................11 3.1.1. Giới thiệu .....................................................................................................11 3.1.2. Cây R-Tree nguyên thủy .............................................................................11 3.1.3. R-Tree trong dữ liệu không gian .................................................................13 3.1.4. R-Tree trong dữ liệu đa phương tiện ...........................................................14 3.1.5. R-Tree trong kho dữ liệu (Data Warehousing) và khai phá dữ liệu (Data Mining) ..................................................................................................................15 3.1.6. Kết hợp các kỹ thuật khai phá dữ liệu vào cây R-Tree ứng dụng cho bài toán truy vấn ảnh. ..................................................................................................15 3.2. Một phương pháp cải tiến cho bài toán tìm kiếm ảnh dựa trên cây R-Tree .......17 3.2.1. Cấu trúc cây RG-Tree ..................................................................................17 3.2.2. Một cải tiến cấu trúc cây RG-Tree ..............................................................20 3.3. Cài đặt cấu trúc cây KNN_R-Tree ......................................................................23 3.4. Các thuật toán xử lý trên cây KNN_R-Tree .......................................................24 3.4.1. Thuật toán chèn một phần tử vào cây KNN_R-Tree...................................24 3.4.2. Thuật toán cập nhật tâm cụm ......................................................................26 3.4.3. Thuật toán Tìm kiếm ảnh tương tự trên cây KNN_R-Tree .........................27 3.5. Kết quả thực nghiệm ...........................................................................................29 3.5.1. Cài đặt thực nghiệm.....................................................................................29 3.5.2. Các giao diện thực nghiệm ..........................................................................30 3.5.3. Phân tích kết quả thực nghiệm ....................................................................33 CHƯƠNG IV. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .......................................37 4.1. Những mặt đã làm được ......................................................................................37 4.2. Những mặt tồn tại................................................................................................37 4.3. Hướng phát triển .................................................................................................37 4.4. Kết luận ...............................................................................................................38 TÀI LIỆU THAM KHẢO...........................................................................................39 DANH MỤC HÌNH ẢNH Hình 1. Minh họa tìm kiếm ảnh tương tự theo văn bản ..................................................6 Hình 2. Minh họa tìm kiếm ảnh dựa trên nội dung .........................................................7 Hình 3. Mô tả vùng không gian lưu trữ và các dữ liệu bên trong nó ............................12 Hình 4. Cây R-Tree tương ứng ......................................................................................12 Hình 5. Minh họa độ đo giảm sự sai biệt trong KNN_R-Tree ......................................21 Hình 6. Internal (In) Node .............................................................................................23 Hình 7. Leaf Node .........................................................................................................23 Hình 8. Cây KNN_R-Tree .............................................................................................24 Hình 9. Mô tả ảnh gốc và các phân vùng của nó...........................................................27 Hình 10. Mô hình truy vấn ảnh .....................................................................................28 Hình 11. Giao diện thiết lập các thông số để thực hiện việc tạo cây KNN_R-Tree .....30 Hình 12. Giao diện đọc dữ liệu các vector từ DataSet và tiền xử lý .............................31 Hình 13. Giao diện thêm các vector từ DataSet vào cây KNN_R-Tree ........................31 Hình 14. Giao diện tìm kiếm ảnh tương tự dựa trên cây KNN_R-Tree. .......................32 Hình 15. Giao diện xuất kết quả thực nghiệm với DataSet ...........................................32 Hình 16. Giao diện kết quả tìm kiếm ảnh tương tự .......................................................33 Hình 17. Giá trị trung bình của Precision, Recall, F-measure của tập dữ liệu ImageCLEF ...................................................................................................................34 DANH MỤC TỪ VIẾT TẮT CBIR Content-based Image Retrieval CNN Convolution Neural Network DCC Dynamical Clustering Center DIS Distributed Information Systems DNN Deep Neural Network GEMINI Generic Multimedia Indexing GIS Geographic Information System KNN K - Nearest Neighbors LBS Location Based Service RG-Tree Region Growth Tree SOM Self-Organizing Maps TBIR Text-based Image Retrieval VLSI Very Large Scale Integrated DANH MỤC BẢNG BIỂU Bảng 1. Các giá trị ngưỡng áp dụng cho chương trình thực nghiệm ………. 33 Bảng 2. Hiệu suất truy vấn ảnh của phương pháp đề xuất trên tập ảnh ImageCLEF…………………………………………………………………. 34 Bảng 3. Hiệu suất truy vấn ảnh trung bình trên tập ảnh ImageCLEF ……… 36 Bảng 4. So sánh độ chính xác giữa các phương pháp trên bộ dữ liệu ImageCLEF.………………………………………………………………….36 CHƯƠNG I. MỞ ĐẦU 1.1. Đặt vấn đề Một vấn đề quan trọng cần phải được nghiên cứu trong hệ thống này đó là sử dụng các khối dữ liệu số lớn, đặc biệt là dữ liệu về ảnh số (image). Nhu cầu sử dụng để phân tích và mô tả cho ngữ nghĩa hình ảnh trên thế giới và Việt Nam tăng cao. Theo đó, dữ liệu số trên toàn cầu đã được gia tăng không ngừng và đạt đến một khối lượng khổng lồ dẫn đến bài toán khai phá dữ liệu và tra cứu thông tin cần phải được giải quyết. Theo IDC (International Data Corporation), dữ liệu toàn cầu năm 2012, 2013 đạt được 2.8 zettabytes và 4.4 zettabytes; ước tính đến cuối năm 2020 dữ liệu toàn cầu gấp 300 lần so với năm 2005, tức là tăng từ 130 exabytes lên đến 40,000 exabytes (40 nghìn tỷ gigabytes = 40 zettabytes), trong đó dữ liệu được tạo ra từ các thiết bị mobile chiếm 27%; đến năm 2025, dữ liệu toàn cầu khoảng 163 zettabytes - tăng gấp 10 lần so với năm 2017 [8]. Mặt khác, dữ liệu đa phương tiện (văn bản, hình ảnh, âm thanh và video) đã được phát triển nhanh chóng trên nhiều hệ thống khác nhau, như điện thoại thông minh, hệ thống mô phỏng đối tượng 2D, 3D, WWW, và các thiết bị viễn thông... Ảnh số đã trở nên thân thuộc với cuộc sống của con người và được ứng dụng trong nhiều hệ thống tra cứu thông tin đa phương tiện như Hệ thống thông tin bệnh viện (Hospital Information System), Hệ thống thông tin địa lý (Geographic Information System), Hệ thống thư viện số (Digital Library System), ứng dụng y sinh, phân tích hình ảnh trong thực phẩm, phân tích các loại động thực vật, trong giáo dục đào tạo, giải trí… [10, 13]. 1.2. Phương pháp nghiên cứu Tổng hợp lý thuyết của các công trình nghiên cứu liên quan và phương pháp thực nghiệm. Dữ liệu và thông tin khoa học được thu thập và tổng hợp từ các bài báo, tạp chí khoa học chuyên ngành của các Trường Đại học trong nước và ngoài nước, qua sự trao đổi, định hướng của Thầy/Cô hướng dẫn trong lĩnh vực nghiên cứu. Việc tổng hợp lý thuyết, chúng tôi lựa chọn cách tiếp cận thông tin đã được áp dụng thành công, thử nghiệm và phân tích trên cơ sở khách quan để đưa ra nhận định, kết luận phù hợp cho đề tài. 1 Thực nghiệm là phương pháp đưa ra chứng minh về kết quả tìm kiếm cũng như mức độ khả thi của nghiên cứu. Đây là phương pháp khá quan trọng tạo quyết định tính khả thi của đề tài. 1.3. Tính cấp thiết của đề tài Theo WordStream, năm 2019, mỗi ngày có 8.95 triệu ảnh, video được chia sẻ trên Instagram và cho đến nay có hơn 40 tỷ hình ảnh. Theo thống kê của Google, khoảng 93 triệu ảnh được tạo ra mỗi ngày kể từ 2014; theo như tổ chức Gigaom, năm 2017, một người trung bình tạo ra 630 ảnh trên điện thoại; cũng theo tổ chức Mylio, năm 2017, mỗi năm một người tạo ra ít nhất 1000 ảnh, mỗi năm tạo ra ít nhất 1 nghìn tỷ hình ảnh… Năm 2015, tổng số hình ảnh toàn cầu đạt 3.2 nghìn tỷ; năm 2016, có 3.5 triệu hình ảnh được chia sẻ trong mỗi phút và có 2.5 nghìn tỷ hình ảnh được chia sẻ và lưu trữ trực tuyến. Trong năm 2017, thế giới đã tạo ra 1.2 nghìn tỷ hình ảnh và tổng số ảnh toàn cầu đến năm 2017 là 4.7 nghìn tỷ; trong đó, các hình ảnh được tạo ra từ thiết bị moblie là 90% [2, 6, 7]. Kích thước cũng như số lượng ảnh ngày càng được gia tăng nên cần phải có nhiều hệ thống xử lý phức tạp nhằm đáp ứng yêu cầu của người dùng. Vì vậy, cần phải có các hệ thống truy vấn ảnh số tự động trên các thiết bị cũng như trong các hệ thống đa phương tiện. Việc tra cứu ảnh để tìm ra tập ảnh tương tự và trích xuất ngữ nghĩa hình ảnh là một bài toán quan trọng trong các hệ thống đa phương tiện và phù hợp với xu thế của xã hội hiện đại. Bài toán khai phá dữ liệu và tra cứu các thông tin liên quan đến hình ảnh phải được quan tâm giải quyết; việc phân loại và tra cứu ngữ nghĩa là một trong những bài toán quan trọng của nhiều hệ thống đa phương tiện [5]. Nhiều hệ truy vấn ảnh theo ngữ nghĩa đã được công bố và ứng dụng trong nhiều lĩnh vực khác nhau như: truy vấn hình ảnh dựa trên đặc trưng ngữ nghĩa mức cao và áp dụng cho ảnh y khoa [9], truy vấn ảnh y khoa sử dụng mạng nơ-ron tích chập CNN (Convolutional Neural Network) [4], ứng dụng ngữ nghĩa hình ảnh trong hệ thống thông tin phân tán DIS (Distributed Information Systems) [1], hệ truy vấn ảnh y khoa theo nội dung M-CBIR (Medical Content-based Image Retrieval) dựa trên cấu trúc vân ảnh và các thông tin hình ảnh trên ontology [11]… Trong mỗi lĩnh vực khác nhau, hệ thống đa phương tiện cần phải trích xuất ngữ nghĩa của các đối tượng nhằm mô tả các nội dung. Bài toán tìm kiếm ảnh theo ngữ nghĩa được thực hiện bằng cách trích xuất đặc trưng hình ảnh tạo ra ngữ nghĩa; sau đó tra cứu 2 các hình ảnh liên quan theo ngữ nghĩa thị giác và trích xuất các thông tin mô tả nội dung hình ảnh [3, 12, 14]. Vấn đề đầu tiên của hệ truy vấn theo ngữ nghĩa là trích xuất thông tin thị giác và chuyển thành ngữ nghĩa mô tả nội dung cho hình ảnh; vấn đề thứ hai là đó là mô tả thông tin ngữ nghĩa và tìm kiếm các hình ảnh liên quan [13]. Trong bối cảnh “Cách mạng công nghiệp 4.0” và tương lai, thế giới đang ngày càng ứng dụng mạnh mẽ Trí tuệ nhân tạo vào đời sống để đem lại những trải nghiệm tuyệt vời nhất, mang tính “nhân tạo” hơn là lập trình máy móc. Giúp xử lý những vấn đề phức tạp – có tính ứng dụng cao. Bài toán tìm kiếm ảnh tương tự theo đó lại ngày càng phát triển do ứng dụng của nó rất đa dạng trong đời sống. Từ giải trí cho đến học tập, cải thiện sức khoẻ, đảm bảo an ninh, phát triển kinh tế…Khi nắm bắt được xu thế đó, ta có thể tạo ra những ứng dụng giúp ích rất nhiều cho con người. 1.4. Mục tiêu, nhiệm vụ và giới hạn của phần mềm Mục tiêu chung của đề tài nghiên cứu là xây dựng một mô hình tra cứu, phương pháp tìm kiếm ảnh tương tự theo nội dung hình ảnh dựa theo cấu trúc cây R-Tree. Mục tiêu cụ thể: • Xây dựng mô hình cho bài toán tìm kiếm ảnh tương tự theo nội dung dựa trên cấu trúc cây R-Tree. • Nghiên cứu thuật toán xây dựng cây, thuật toán tìm kiếm ảnh tương tự và phương pháp trích xuất đặc trưng hình ảnh vào bài toán tìm kiếm ảnh nhằm mục đích cải thiện kết quả tìm kiếm. • Xây dựng ứng dụng thực nghiệm dựa trên bộ ảnh ImageCLEF. Nghiên cứu được thực hiện trên các nội dung: • Nghiên cứu cấu trúc dữ liệu lưu trữ đặc trưng hình ảnh và phân cụm dữ liệu trên mô hình cây R-Tree. • Phân tích, vận dụng kỹ thuật, chuẩn hóa trong quá trình rút trích đặc trưng hình ảnh. • Nghiên cứu thuật toán xây dựng cây R-Tree. • Áp dụng thuật toán tìm kiếm trên cây nhằm tìm kiếm ảnh tương tự theo nội dung. • Thực nghiệm kết quả tra cứu trên bộ ảnh dữ liệu ImageCLEF với 20.000 ảnh được chia thành 276 phân lớp. 3 Đối tượng nghiên cứu: Phạm vi nghiên cứu bao gồm các thuật toán máy học, cấu trúc dữ liệu cây và thực nghiệm trên bộ ảnh ImageCLEF với 20.000 ảnh và 276 phân lớp. • Thuật toán gom cụm K-Means. • Cấu trúc dữ liệu cây phân cụm R-Tree và các thuật toán xây dựng cây. • Phương pháp rút trích xuất đặc trưng hình ảnh thành véc-tơ. • Dữ liệu ảnh, tập dữ liệu ImageCLEF (20.000 ảnh và 276 phân lớp). • Độ đo tương tự Euclide giữa hai véc-tơ. • Bài toán tìm kiếm ảnh tương tự theo nội dung. • Xây dựng thực nghiệm dựa trên ngôn ngữ lập trình C#. 4 CHƯƠNG II. TỔNG QUAN BÀI TOÁN TÌM KIẾM ẢNH THEO NỘI DUNG 2.1. Giới thiệu Trong thập niên vừa qua, một kho dữ liệu ảnh khổng lồ đang được chia sẻ rộng rãi trên Word Wide Web. Các nhà khoa học trên thế giới đã nghiên cứu rất nhiều các phương pháp truy vấn hình ảnh với mục đích nâng cao hiệu quả và tính chính xác của tìm kiếm ảnh. Các kỹ thuật tìm kiếm hình ảnh thường được sử dụng chủ yếu dựa trên các từ khóa [15]. Những kỹ thuật này sử dụng danh sách từ khóa để mô tả nội dung thông tin, hệ thống tìm kiếm dựa trên từ khoá khớp với tìm kiếm văn bản của người dùng để mô tả văn bản của hình ảnh và trả lại tất cả các hình ảnh có mô tả phù hợp. Tuy nhiên, các nhà nghiên cứu đã chỉ ra một số hạn chế của kỹ thuật này, như tính chủ quan của các mô tả (metadata), sự mơ hồ của ngôn ngữ tự nhiên, có thể các kết quả trả lại có chứa hình ảnh không liên quan khi mô tả không chính xác… Chính vì thế, các nhà khoa học đã nghiên cứu các hệ thống tìm kiếm hình ảnh dựa trên nội dung CBIR (ContentBased Image Retrieval), sử dụng các tính năng trực quan cấp thấp như màu sắc, kết cấu, hình dạng và vị trí,… được trích xuất từ các điểm ảnh vào chỉ mục và tìm kiếm các hình ảnh sử dụng các kỹ thuật xử lý và phân tích hình ảnh [16, 17]. Việc tìm kiếm hình ảnh dựa trên nội dung (CBIR) đã được nghiên cứu trong nhiều năm tập trung vào việc trích xuất và so sánh các tính năng từ các hình ảnh [18, 19]. Các tính năng được tự động trích ra từ các điểm ảnh bằng cách sử dụng màu sắc chiếm ưu thế, kết cấu hoặc hình dạng chi phối (tức là kỹ thuật này tập trung vào các tính năng trực quan của hình ảnh) và được sử dụng trong các biện pháp tương tự đã được lựa chọn cụ thể để lấy các hình ảnh tương tự. Tìm kiếm ảnh là tra cứu các hình ảnh liên quan từ một tập dữ liệu hình ảnh. Tìm kiếm ảnh theo nội dung gồm một tập các kỹ thuật để tìm kiếm các hình ảnh liên quan từ tập dữ liệu hình ảnh, dựa trên trích xuất các đặc trưng của hình ảnh như màu sắc, cấu trúc, hình dạng, vị trí… 2.2. Tra cứu ảnh dựa vào văn bản Trước khi ra đời Tìm kiếm ảnh dựa vào nội dung, việc tìm kiếm hình ảnh có thể dựa vào Chú thích (văn bản) của ảnh, được cộng đồng gán nhãn. Với việc hình ảnh được 5 gán nhãn tuỳ ý từ cộng đồng, việc dựa vào nhãn đó để tra cứu ảnh gây nhiều khó khăn vì độ chính xác không cao và thật khó để tin tưởng. Ngày nay, việc sử dụng ngày càng nhiều công nghệ đa phương tiện, các thiết bị điện tử được trang bị máy ảnh kỹ thuật số và hàng tỷ bức ảnh được tải lên trên phương tiện truyền thông xã hội dẫn đến sự tăng trưởng theo cấp số nhân của cơ sở dữ liệu hình ảnh kỹ thuật số. Truy xuất hình ảnh dựa trên văn bản (TBIR / Text-Based Image Retrieval) là kỹ thuật truy xuất sớm nhất và phổ biến nhất. Phương pháp TBIR dựa trên giả định rằng tất cả các hình ảnh đều được chú thích. Tuy nhiên, giả định này không được áp dụng cho các cơ sở dữ liệu hình ảnh kỹ thuật số lớn, nơi người dùng tải lên các tệp của riêng họ mà không cần thêm tên hoặc nhãn cụ thể. Một giải pháp tự nhiên để khắc phục nhược điểm này là ghi nhãn thủ công của hình ảnh. Tuy nhiên, giải pháp này đại diện cho một công việc tẻ nhạt cho bộ sưu tập hình ảnh nhỏ và không thực tế cho cơ sở dữ liệu lớn. Một nhược điểm khác của phương pháp TBIR là khoảng cách ngữ nghĩa giữa truy vấn văn bản người dùng và thuộc tính hình ảnh của hình ảnh [18, 19]. Hình 1. Minh họa tìm kiếm ảnh tương tự theo văn bản Hầu hết hệ thống tìm kiếm dựa trên văn bản đều yêu cầu các dữ liệu được chú thích bằng tay, việc tìm kiếm được thực hiện dựa trên mô tả văn bản của dữ liệu đa phương tiện do người dùng cung cấp. Tìm kiếm được thông qua việc kết hợp các tìm kiếm của người dùng và chú thích từ khoá TBIR. Hệ thống tìm kiếm dựa trên văn bản sử dụng các đặc trưng trực quan cấp thấp như màu sắc, kết cấu, hình dạng và vị trí… để lấy dữ liệu, cụ thể là tìm kiếm ảnh. Các đặc trưng cấp thấp này được trích xuất từ hình ảnh tự động. Google và Bing đều sử dụng các kỹ thuật tìm kiếm dựa trên từ khoá; Cách tiếp cận này nhanh và hiệu quả. 6 Dữ liệu được mô tả bởi một tập hợp các từ khóa hoặc siêu văn bản được cung cấp bởi người dùng => phụ thuộc vào tính chủ quan của người dùng. Kết quả trả về của truy vấn có thể chứa các dữ liệu không liên quan. Vì vậy, bất lợi chính của hệ thống tìm kiếm dữ liệu đa phương tiện dựa trên văn bản là nó có thể trả lại các dữ liệu dự phòng hoặc không liên quan trong kết quả. Kết quả trả về chỉ là những dữ liệu đơn giản. 2.3. Tra cứu ảnh dựa vào nội dung Truy xuất hình ảnh dựa trên nội dung (CBIR / Content-Based Image Retrieval) là một các tiếp cận mới để lấy các hình ảnh liên quan một cách hiệu quả. Các kỹ thuật CBIR có khuynh hướng truy xuất các hình ảnh tương tự trực quan với một hình ảnh truy vấn nhất định. Đối với hệ thống CBIR điển hình, người dùng cung cấp cho hệ thống hình ảnh dưới dạng truy vấn và tìm kiếm hình ảnh có liên quan. Quá trình truy xuất này mã hóa và lập chỉ mục các hình ảnh bằng các tính năng hình ảnh của chúng và các hình ảnh được trả về được chọn dựa trên sự giống nhau của các tính năng hình ảnh của chúng với các hình ảnh đại diện cho truy vấn. Do đó, hiệu suất truy xuất phụ thuộc vào sự lựa chọn của các tính năng trực quan cấp thấp [19]. Tra cứu ảnh dựa vào nội dung ra đời nhằm khắc phục nhược điểm của Tra cứu ảnh dựa trên văn bản. Nó phân tích ảnh nguồn (hình ảnh được đưa vào để tìm kiếm tập tương tự) thành các đặc trưng và sử dụng thuật toán để so sánh độ tương đồng với tập các ảnh sẵn có. Các đặc trưng có thể kể đến như màu sắc, độ sâu, kết cấu, hình dạng, các đối tượng trong ảnh… Bằng việc phân tích và so sánh đặc trưng như vậy, độ chính xác trong truy vấn được nâng cao và đáng tin cậy hơn so với phương pháp dựa trên văn bản. Hình 2. Minh họa tìm kiếm ảnh dựa trên nội dung Tập trung vào việc trích xuất và so sánh các đặc trưng từ các hình ảnh, văn bản, âm thanh... Các đặc trưng của dữ liệu thường được trích xuất từ các đặc trưng cấp thấp (màu 7 sắc, hình dạng, âm sắc...). Các nhà nghiên cứu trong thập kỷ qua đã chứng minh tính hiệu quả và tính chính xác của các kỹ thuật dựa trên CBIR. 2.4. Trích xuất đặc trưng ảnh Đặc trưng màu sắc: Màu sắc là một đặc trưng nổi bật và được sử dụng phổ biến nhất trong tìm kiếm ảnh theo nội dung. Mỗi một điểm ảnh (thông tin màu sắc) có thể được biểu diễn như một điểm trong không gian màu sắc ba chiều. Các không gian màu sắc thường dùng là: RGB, Munsell, CIE, HSV. Tìm kiếm ảnh theo màu sắc tiến hành tính toán biểu đồ màu cho mỗi ảnh để xác định tỉ trọng các điểm ảnh của ảnh mà chứa các giá trị đặc biệt (màu sắc). Các nghiên cứu gần đây đang cố gắng phân vùng ảnh theo các màu sắc khác nhau và tìm mỗi quan hệ giữa các vùng này. Để gia tăng độ chính xác khi đối sánh hình ảnh qua đặc trưng cấp thấp, các màu sắc chủ đạo của hình ảnh được trích xuất. Đối với đặc trưng màu sắc, mỗi điểm ảnh được gom cụm theo dãy màu Newton (Red, Green, Blue, Yellow, Orange, Purple). Vì vậy, mỗi điểm ảnh là một véctơ dữ liệu trong không gian RGB và thực hiện gom cụm theo thuật toán K-Means dựa trên sáu cụm màu Newton. Đặc trưng kết cấu: Trích xuất nội dung ảnh theo kết cấu nhằm tìm ra mô hình trực quan của ảnh và cách thức chúng được xác định trong không gian. Kết cấu được biểu diễn bởi các texel mà sau đó được đặt vào một số các tập phụ thuộc vào số kết cấu được phát hiện trong ảnh. Các tập này không chỉ xác định các kết cấu mà còn chỉ rõ vị trí các kết cấu trong ảnh. Việc xác định các kết cấu đặc biệt trong ảnh đạt được chủ yếu bằng cách mô hình các kết cấu như những biến thể cấp độ xám 2 chiều. Đặc trưng hình dạng: Hình dạng của một ảnh hay một vùng là một đặc trưng quan trong trong việc xác định và phân biệt ảnh trong nhận dạng mẫu. Mục tiêu chính của biểu diễn hình dạng trong nhận dạng mẫu là đo thuộc tính hình học của một đối tượng được dùng trong phân lớp, so sánh và nhận dạng đối tượng. Trong bộ dữ liệu hình ảnh của bộ ImageCLEF, mỗi ảnh sẽ được phân tích thành một vector đặc trưng gồm 27 thuộc tính, được phân thành các nhóm bao gồm: ▪ Đặc trưng vùng: diện tích, chiều rộng và chiều cao. ▪ Đặc trưng vị trí: giá trị trung bình và độ lệch chuẩn theo trục x và trục y. ▪ Đặc trưng về hình dạng (shape): boundary/area, convexity. ▪ Đặc trưng màu sắc trong không gian RGB và CIE-Lab: trung bình, độ lệch chuẩn và độ nghiêng. 8 1. Diện tích vùng (số pixel/tổng số pixel của hình ảnh) 2. Chiều rộng: số pixel theo chiều rộng của vùng/số pixel của chiều rộng ảnh 3. Chiều cao: số pixel theo chiều cao của vùng/số pixel của chiều cao ảnh 4. Giá trị trung bình theo trục x: giá trị trung bình theo trục x của các pixel trong vùng 5. Độ lệch chuẩn theo trục x 6. Giá trị trung bình theo trục y: giá trị trung bình theo trục y của các pixel trong vùng 7. Độ lệch chuẩn theo trục y 8. Chu vi/diện tích 9. Convexity: số pixel phần lõm của vùng/tổng số pixel của vùng 10. Trung bình theo màu R (RGB) 11. Độ lệch chuẩn theo màu R (RGB) 12. Độ nghiêng theo màu R (RGB) 13. Trung bình theo màu G (RGB) 14. Độ lệch chuẩn theo màu G (RGB) 15. Độ nghiêng theo màu G (RGB) 16. Trung bình theo màu B (RGB) 17. Độ lệch chuẩn theo màu B (RGB) 18. Độ nghiêng theo màu B (RGB) 19. Trung bình theo màu L (CIE-Lab) 20. Độ lệch chuẩn theo màu L (CIE-Lab) 21. Độ nghiêng theo màu L (CIE-Lab) 22. Trung bình theo màu a (CIE-Lab) 23. Độ lệch chuẩn theo màu a (CIE-Lab) 24. Độ nghiêng theo màu a (CIE-Lab) 25. Trung bình theo màu b (CIE-Lab) 26. Độ lệch chuẩn theo màu b (CIE-Lab) 27. Độ nghiêng theo màu b (CIE-Lab) 2.5. Độ đo tương đồng giữa 2 vector đặc trưng Nghiên cứu này sử dụng phương pháp tính độ đo tương đồng giữa 2 vector đặc trưng dựa vào Khoảng cách Euclide. Theo định nghĩa về khoảng cách Euclidean (Euclidean Distance): “Khoảng cách giữa 2 điểm là chiều dài của đường thẳng nối 9 chúng”. Trong mặt phẳng, khoảng cách giữa 2 điểm (x1, y1) và (x2, y2) được cho bởi định lý Pythagorean như sau: 𝑑 = √(𝑥2 − 𝑥1 )2 + (𝑦2 − 𝑦1 )2  Ta có công thức tổng quát cho khoảng cách Euclide giữa 2 vector đặc trưng: v1: vector thứ nhất v2: vector thứ hai 2 d (v1, v2) = √∑27 𝑖=1(𝑣1𝑖 − 𝑣2𝑖 ) 2.6. Thuật toán gom cụm K-Means K-Means là thuật toán rất quan trọng và được sử dụng phổ biến trong kỹ thuật phân cụm. Tư tưởng chính của thuật toán K-Means là tìm cách phân nhóm các đối tượng (objects) đã cho vào K cụm (K là số các cụm được xác định trước, K nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm nhóm (centroid) là nhỏ nhất. Thuật toán K-Means thực hiện qua các bước chính sau: 1. Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại diện bằng các tâm của cụm. 2. Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng khoảng cách Euclidean) 3. Nhóm các đối tượng vào nhóm gần nhất 4. Xác định lại tâm mới cho các nhóm 5. Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối tượng Thuật toán K-Means có ưu điểm là đơn giản, dễ hiểu và cài đặt. Tuy nhiên, một số hạn chế của K-Means là hiệu quả của thuật toán phụ thuộc vào việc chọn số nhóm K (phải xác định trước) và chi phí cho thực hiện vòng lặp tính toán khoảng cách lớn khi số cụm K và dữ liệu phân cụm lớn. . 10 CHƯƠNG III. HỆ TRA CỨU ẢNH DỰA TRÊN CẤU TRÚC CÂY R-TREE 3.1. Các khái niệm cơ bản về cây R-Tree [20] 3.1.1. Giới thiệu Quản lý dữ liệu không gian đã là một lĩnh vực hoạt động nghiên cứu chuyên sâu trong hơn ba thập kỷ qua. Để hỗ trợ các đối tượng không gian trong hệ thống cơ sở dữ liệu, cần xem xét một số vấn đề bao gồm mô hình dữ liệu không gian, cơ chế lập chỉ mục, xử lý truy vấn hiệu quả và mô hình chi phí. Một trong những phương pháp truy xuất có ảnh hưởng nhất trong lĩnh vực này là cấu trúc cây R-Tree được Guttman đề xuất vào năm 1984 là một giải pháp hiệu quả để lập chỉ mục các đối tượng không gian trong các ứng dụng thiết kế VLSI (Very Large Scale Integrated). Kể từ đó, một số biến thể của cấu trúc R-Tree đã được đề xuất để truy xuất hiệu quả hơn và xử lý các đối tượng trong không gian đa chiều. Theo sự phát triển này, các phương pháp truy xuất mới đã được đề xuất, đánh giá, so sánh và cài đặt. Một trong những phương pháp này là sử dụng cấu trúc cây RTree. Cấu trúc này được ứng dụng nhằm mục đích xử lý dữ liệu hình học, chẳng hạn như điểm, đoạn thẳng, bề mặt, khối lượng và thể tích cong trong không gian [1]. Cây RTree được xử lý theo cách tương tự như cây B- Tree. Cây R-Tree dành cho cơ sở dữ liệu không gian, cây B-Tree được dùng cho các kiểu dữ liệu chữ và số. Cây R-Tree được sử dụng rất rộng rãi trong các ứng dụng để xử lý dữ liệu đa chiều. Ngày nay, cơ sở dữ liệu không gian và hệ thống thông tin địa lý được nghiên cứu rộng rãi; Cơ sở dữ liệu đa phương tiện có thể xử lý các loại dữ liệu mới như hình ảnh, giọng nói, âm thanh, hoặc video, đang được thiết kế và phát triển. Các ứng dụng này đã sử dụng cây R-Tree để lưu trữ và truy xuất dữ liệu. Các ứng dụng dựa trên cây R-Tree bao gồm cơ sở dữ liệu không gian, cơ sở dữ liệu hình ảnh và video. 3.1.2. Cây R-Tree nguyên thủy Cây R-Tree là một cấu trúc dữ liệu dùng để phân vùng dữ liệu thành các khối có thể lồng nhau hoặc chồng lên nhau, được giới thiệu bởi Guttman vào năm 1984 [1]. Cây R-Tree là cây đa nhánh cân bằng và dữ liệu được lưu tại các nút lá (leafNode). Mỗi nút trong (inNode) là một vùng không gian hình chữ nhật hoặc đa giác chứa các vùng không 11 gian con bên trong nó và chứa các liên kết trỏ đến các nút con. Mỗi nút trên cây có số phần tử tối thiểu là m và số phần tử tối đa là M. Mỗi nút lá là một vùng không gian chứa các liên kết trỏ đến các đối tượng dữ liệu. Mỗi nút lá phân chia dữ liệu thành một cụm trong không gian k-chiều. Hình 3. Mô tả vùng không gian lưu trữ và các dữ liệu bên trong nó Hình 4. Cây R-Tree tương ứng R-Tree là một cấu trúc dữ liệu cây được sử dụng để lưu trữ các chỉ mục dữ liệu không gian một cách hiệu quả. R-Tree rất hữu ích cho việc truy vấn và lưu trữ dữ liệu không gian. Một số ứng dụng thực tế được đề cập dưới đây: ▪ Lập chỉ mục thông tin đa chiều. ▪ Xử lý tọa độ không gian địa lý. ▪ Thực hiện bản đồ ảo. ▪ Xử lý dữ liệu trò chơi. Các tính chất của cây R-Tree: ▪ Bao gồm một gốc duy nhất (rootNode), tập các nút trong (inNodes) và tập các nút lá (leafNodes). ▪ Root chứa con trỏ đến vùng lớn nhất trong miền không gian. ▪ Các nút cha chứa các con trỏ tới các nút con trong đó vùng của các nút con nằm bên trong vùng của các nút cha. ▪ Các nút lá chứa dữ liệu các đối tượng. ▪ Vùng giới hạn tối thiểu là vùng nhỏ nhất chứa đối tượng đang xem xét. Cây R ban đầu có hai nhược điểm quan trọng: 12