Nâng cao hiệu quả truy vấn hình ảnh theo ngữ nghĩa trên cây phân cụm c-tree

Nội dung text: Nâng cao hiệu quả truy vấn hình ảnh theo ngữ nghĩa trên cây phân cụm c-tree

1. Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018 DOI: 10.15625/vap.2018.00049 NÂNG CAO HIỆU QUẢ TRUY VẤN HÌNH ẢNH THEO NGỮ NGHĨA TRÊN CÂY PHÂN CỤM C-Tree Nguyễn Thị Uyên Nhi1,3, Văn Thế Thành2, Lê Mạnh Thạnh1 1 Trường Đại học Khoa học, Đại học Huế 2Trường Đại học Công nghiệp Thực phẩm TP.HCM 3Trường Đại học Sài Gòn ntunhi@sgu.edu.vn, vanthethanh@gmail.com, lmthanh@hueuni.edu.vn TÓM TẮT: Dữ liệu hình ảnh đang gia tăng nhanh chóng trong các hệ thống đa phương tiện gây khó khăn trong việc tìm kiếm thông tin hình ảnh. Trong bài báo này, chúng tôi xây dựng mô hình truy vấn ảnh theo ngữ nghĩa nhằm nâng cao hiệu quả tìm kiếm ảnh tương tự. Để thực hiện mô hình này, chúng tôi sử dụng phương pháp K-means nhằm phân cụm đặc trưng thị giác của hình ảnh, đề xuất khoảng cách độ đo tương tự theo ngữ nghĩa giữa hai hình ảnh dựa trên đặc trưng thị giác cấp thấp, tạo ra véctơ từ thị giác cho hình ảnh, xây dựng cấu trúc cây phân cụm C-tree nhằm lưu trữ và nâng cao hiệu quả tìm kiếm hình ảnh tương tự; từ đó, chúng tôi trích xuất ngữ nghĩa của các hình ảnh tương tự dựa trên véctơ từ thị giác đã được tạo ra. Nhằm minh chứng tính hiệu quả của các đề xuất, chúng tôi xây dựng ứng dụng và đánh giá kết quả thực nghiệm trên bộ dữ liệu ảnh ImageCLEF gồm 20,000 hình ảnh. Từ khóa: Sematic-based images retrieval, similarity measure, C-Tree, K-mean. I. 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 [1]. 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 (Content-Based 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 [2, 3]. 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 [4, 5]. 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ự. 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, tuy nhiên, CBIR vẫn thiếu sự hiểu biết về phân tích ngữ nghĩa của hình ảnh, tạo nên khoảng cách về ngữ nghĩa của hình ảnh [6]. Ví dụ: nếu người dùng muốn tìm kiếm hình ảnh, hệ thống CBIR sẽ không thể ánh xạ ý tưởng con người vào tính năng hình ảnh (tức là tạo khoảng cách về ngữ nghĩa giữa các tính năng hình ảnh ở mức thấp và các khái niệm cấp cao của con người). Do đó, phân tích ngữ nghĩa cần được kết hợp trong việc tìm kiếm hình ảnh dựa trên nội dung để thu hẹp khoảng cách ngữ nghĩa này. Để giải quyết vấn đề này, đã có nhiều phương pháp kết hợp giữa nội dung hình ảnh và các khía cạnh ngữ nghĩa. Tìm kiếm hình ảnh dựa trên ngữ nghĩa là một phương pháp hữu ích để chuyển từ tìm kiếm dựa trên từ khóa, nội dung sang việc thu thập hình ảnh theo khái niệm. Các hình ảnh chú thích ngữ nghĩa có thể được tạo ra theo cách thủ công hoặc tự động và chúng có thể khác nhau trong các hình thức biểu diễn và các cách xây dựng các mối quan hệ giữa các khái niệm, nhưng tất cả chúng đều là một đặc tả rõ ràng của một khái niệm hóa. Trong bài báo này, chúng tôi đề xuất xây dựng cấu trúc cây phân cụm C-tree nhằm lưu trữ hình ảnh và nâng cao hiệu quả tìm kiếm hình ảnh tương tự, trích xuất ngữ nghĩa của các hình ảnh tương tự dựa trên véctơ từ thị giác đã được tạo ra, xây dựng mô hình truy vấn hình ảnh dựa trên cây phân cụm C-tree và ứng dụng dựa trên mô hình đã nghiên cứu. Phần còn lại của bài viết này được tổ chức như sau. Phần II trình bày tổng quan các nghiên cứu có liên quan, động lực và mục tiêu của chúng tôi. Phần III nêu các khái niệm, các kỹ thuật và cấu trúc dữ liệu của truy vấn hình ảnh theo ngữ nghĩa. Phần IV là các thuật toán để truy vấn hình ảnh dựa trên cây C-Tree. Phần V ứng dụng thực nghiệm và thảo luận. Cuối cùng, chúng tôi kết luận bài báo này bằng cách tóm tắt đề xuất của chúng tôi và trình bày một số quan điểm nghiên cứu trong tương lai.
2. Nguyễn Thị Uyên Nhi, Văn Thế Thành, Lê Mạnh Thạnh 371 II. CÁC NGHIÊN CỨU LIÊN QUAN, ĐỘNG LỰC VÀ MỤC TIÊU Hiện nay, có nhiều công cụ và công trình nghiên cứu khác nhau liên quan đến việc xây dựng hệ tìm kiếm ảnh nhằm cải tiến hiệu quả tìm kiếm ảnh để đáp ứng nhu cầu của người dùng ngày càng tốt hơn. Một loạt các công trình đã được các nhà khoa học tiến hành nghiên cứu nhằm làm giảm khoảng cách ngữ nghĩa, nâng cao hiệu quả truy vấn hình ảnh. Trong phần này, chúng tôi trình bày tổng quan về một số phương pháp tiếp cận hiện tại. Sau đó, đề ra động lực và mục tiêu nghiên cứu của chúng tôi về hệ thống thu hồi hình ảnh kết hợp thông tin ngữ nghĩa. 2.1. Các công trình nghiên cứu liên quan Một số phương pháp khai thác siêu dữ liệu để thu thập hình ảnh đã được đề xuất. Mục đích của các cách tiếp cận này là chuyển đổi siêu dữ liệu thành một định dạng có thể sử dụng một cách tự nhiên cho các vấn đề tìm kiếm hình ảnh. Việc sử dụng thuật ngữ mang tính ngữ nghĩa để cung cấp mô tả cấp cao về nội dung hình ảnh được Camille Kurtz và cộng sự nghiên cứu [7], cho phép lấy ra các hình ảnh tương tự dựa trên các chú thích ảnh semantic cấp cao. Nhóm nghiên cứu đưa ra một khuôn khổ thu hồi hình ảnh dựa trên các tính năng ngữ nghĩa dựa trên hai chiến lược chính: (1) dự đoán các thuật ngữ mô tả nội dung hình ảnh từ các quy trình đa chiều Riesz và (2) tìm kiếm các hình ảnh tương tự bằng cách đánh giá sự tương đồng giữa các chú thích, xem xét cả hai mối quan hệ về hình ảnh. Các kỹ thuật được sử dụng như: bước học tập của cách tiếp cận này phụ thuộc vào SVMs tuyến tính, được sử dụng để xây dựng các chữ ký bằng hình ảnh trong không gian đặc trưng này. Mức độ liên quan của kết quả tìm kiếm được đánh giá bằng cách sử dụng hai giao thức: đánh giá tương đối so với tiêu chuẩn tham chiếu không giống nhau được xác định cho mỗi cặp hình ảnh trên bộ dữ liệu 25 số liệu và đánh giá liên quan đến chẩn đoán của các ảnh đã tải về trên bộ dữ liệu 72 hình ảnh. Nhóm nghiên cứu Yang, Ming Dong và Farshad Fotouhi [8] đề xuất một mô hình xử lý ngôn ngữ tự nhiên để thu thập hình ảnh, kết hợp các thông tin ngữ nghĩa được cung cấp bởi WordNet, một hệ thống tham chiếu trực tuyến và các tính năng trực quan cấp thấp. Hệ thống thứ bậc ngữ nghĩa của từ nghĩa từ WordNet được sử dụng để tăng cường mối liên hệ giữa các hình ảnh và mô tả nguyên bản của một khái niệm. Thuật toán chọn từ khoá thống kê được thực hiện giúp chọn các từ khoá đại diện nhất để chú thích những hình ảnh của khái niệm này. Kết quả thực nghiệm trên bộ ảnh Corel CD với 2500 hình ảnh phong cảnh, cho thấy phương pháp tiếp cận này có thể cải thiện đáng kể độ chính xác của tìm kiếm. Các kết quả cũng cho thấy tiềm năng cao của cách tiếp cận trong việc cung cấp cơ sở ngữ nghĩa để tìm kiếm cho các dữ liệu hình ảnh. Các nghiên cứu trên đều chỉ ra rằng, việc phân tích và tìm kiếm hình ảnh đang trở thành một lĩnh vực nghiên cứu rất nóng hổi và cấp thiết hiện nay. Những nghiên cứu về tìm kiếm ảnh theo ngữ nghĩa, mà cụ thể là tìm kiếm ảnh kết hợp ngữ nghĩa cho ra kết quả vô cùng khả thi khi hiệu suất tìm kiếm nhanh chóng và chính xác hơn mong đợi. Nghiên cứu tìm kiếm ảnh dựa vào ngữ nghĩa còn rất nhiều khía cạnh mà các nhà nghiên cứu chưa khám phá hết, cần đi sâu để tìm hiểu và thực nghiệm, từ đó đưa ra được các đánh giá, so sánh giữa các phương pháp với nhau. Đây là một định hướng nghiên cứu phù hợp với xu thế nghiên cứu chung của thế giới, mang tính cấp thiết cao và có khả năng ứng dụng hiệu quả trong thực tiễn. 2.2. Động lực và mục tiêu nghiên cứu: Động lực nghiên cứu của chúng tôi là nâng cao hiệu quả tìm kiếm hình ảnh theo nội dung với tiếp cận ngữ nghĩa, nhằm đáp ứng yêu cầu của người dùng bằng cách cải tiến quá trình thu hồi hình ảnh dựa trên tri thức hình ảnh và ngữ nghĩa cấp cao. Chúng tôi đề xuất một hệ thống có hai mục tiêu chính. Một mặt, hệ thống cho phép xây dựng mô hình tìm kiếm hình ảnh theo ngữ nghĩa, nhằm nâng cao hiệu quả tìm kiếm. Mặt khác, chúng tôi xây dựng cấu trúc cây phân cụm C- tree nhằm lưu trữ và nâng cao hiệu quả tìm kiếm hình ảnh tương tự. Các tính năng cấp thấp mô tả các nội dung của vùng hình ảnh, trong khi các tính năng cấp cao mô tả nội dung ngữ nghĩa ngầm liên quan đến vùng hình ảnh. Chúng tôi đề xuất một hệ thống tìm kiếm hình ảnh thông qua nội dung theo hướng ngữ nghĩa. Tìm theo nội dung ở đây có nghĩa là mỗi ảnh sẽ được trích xuất các đặc trưng, các hình ảnh được gán chú thích dựa trên nội dung của ảnh, được gom cụm và lưu trữ trên một cây C-tree. III. CÁC KHÁI NIỆM, KỸ THUẬT VÀ CẤU TRÚC DỮ LIỆU TRUY VẤN ẢNH THEO NGỮ NGHĨA Trong phần này, chúng tôi đưa ra các cơ sở lý thuyết về lập chú thích cho hình ảnh, thu hồi hình ảnh với ngữ nghĩa, các kỹ thuật về phân cụm K-means, định nghĩa cây phân cụm C-Tree và truy vấn hình ảnh trên cây C-Tree. 3.1. Chú thích và trích xuất ngữ nghĩa cho hình ảnh Quá trình lập chú thích được chia thành hai phần, phân tích khái niệm và quá trình chuyển đổi, trong đó trước đây chiết xuất thông tin từ các tài liệu và sau đó tạo ra mô tả phù hợp với mô tả. Lập chú thích cho hình ảnh cần phải mô tả được các hình ảnh đó bằng các metadata [9]. Mô tả của một hình ảnh bao gồm các thông tin được tìm thấy bằng cách phân tích hình ảnh đó. Các thành phần trong một mô tả, các mô tả, được thu thập trong một cấu trúc theo mô tả.
3. 372 NÂNG CAO HIỆU QUẢ TRUY VẤN HÌNH ẢNH THEO NGỮ NGHĨA TRÊN CÂY PHÂN CỤM C-Tree Lập chú thích có thể được thực hiện bằng tay hoặc tự động và theo cách thức được kiểm soát hoặc không kiểm soát [10]. Trong lập chú thích bằng tay, các chuyên gia chỉ định mô tả, trong khi lập chú thích tự động được thực hiện bởi máy tính. Chú thích không kiểm soát được đề cập đến quá trình lập chú thích mà không có giới hạn về biểu mẫu và nội dung của các bộ mô tả, trong khi lập chú thích kiểm soát hạn chế việc mô tả các tài liệu với một số lượng thông tin được xác định trước, ví dụ: một bộ từ khóa, từ đồng nghĩa, 3.2. Thuật toán phân cụm K-means Với một tập dữ liệu ảnh, ta cần phải gom cụm các dữ liệu ảnh có tính chất tượng tự nhau vào các cụm khác nhau chưa biết trước. Các dữ liệu có thể coi là các điểm trong không gian và khoảng cách giữa các điểm có thể được coi là thông số mức độ giống nhau của chúng 2 điểm càng gần nhau thì chúng càng giống nhau [11]. Về cơ bản giải thuật K-means được thực hiện như sau: Đầu vào: Tập các hình ảnh và số lượng cluster cần tìm K Đầu ra: Các center M và label vector cho từng điểm dữ liệu Y. Bước 1: Khởi tạo Giả sử có n điểm dữ liệu là gồm n điểm dữ liệu, có d chiều và k , với f là véctơ đặc tính của hình ảnh, p là đường dẫn của hình ảnh đến link file của hình ảnh đó. Cây C-Tree là cây tăng trưởng tự cân bằng. Cây được xây dựng từ nút lá, tự tách nút khi đạt giới hạn nút và ảnh được tách tạo thành nút khác khi nằm ngoài độ đo được xác định của nút. Mỗi nút lá của C-Tree là một cụm riêng biệt, bao gồm n phần tử là dữ liệu ảnh tương đương. Mỗi nút lá có đường dẫn đến nút cha chứa nó. Mỗi hình ảnh khi được gom cụm vào nút lá, cần xác định độ đo tương tự để đo khoảng cách của các vecto đặc trưng của nút đó. Khi nút lá với cụm có p dữ liệu ảnh với p ≥ n, cây C-tree sẽ tách cụm, cập nhật lại tâm cụm, sử dụng độ đo khoảng cách tương tự Euclid để tìm cụm mới. Đồng thời, cập nhật tâm cụm ở nút trong chứa các nút con đó. Mỗi nút bên trong của C-tree là tâm cụm của các nút con, mỗi nút trong có ít nhất hai con và nhiều nhất là m con. Mỗi nút trong cần có đường dẫn đến nút cha chứa nó và đến các nút con. Mỗi cây có một nút duy nhất gọi là nút góc, nút gốc của cây chứa ít nhất hai cặp phần tử và nhiều nhất là N cặp phần tử . Mỗi nút gốc chỉ có đường dẫn đến các nút trong của nó. Bậc của nút lá được gán bằng 0. Bậc của mỗi nút bên trong cây nhỏ hơn nhãn của cha mẹ. Với mỗi hình ảnh sẽ được ch n vào sẽ được trích xuất đặc trưng, sử dụng độ đo tương tự Euclid để cho hình ảnh vào nút lá phù hợp. Khi nút lá đầy (số lượng hình ảnh lớn hơn n hình ảnh mặc định ban đầu) thì quá trình tách nút sẽ được thực hiện và cây C-tree sẽ tăng trưởng chiều cao theo hướng đi về gốc của cây. Nút trong của cây C-Tree chính
4. Nguyễn Thị Uyên Nhi, Văn Thế Thành, Lê Mạnh Thạnh 373 là tâm của tất cả các cụm ở nút lá, mỗi khi nút lá tách cụm, nút trong tiến hành cập nhật tâm cụm. Mỗi nút trong của cây C-tree sẽ ưu tiên nhận các hình ảnh có độ tương tự cao. Hình 1. Cây phân cụm tăng trưởng C-Tree 3.4. Khoảng cách Euclid Khoảng cách Euclid của một điểm P trong không gian n chiều đến gốc tọa độ được tính bằng căn bậc hai của tổng bình phương các tọa độ thành phần: √ Với hai điểm P và Q, ta có khoảng cách Euclid giữa chúng như sau √ Trong không gian ba chiều Euclid, khoảng cách giữa hai điểm (x1, y1, z1) và (x2, y2, z2) là √ Một cách tổng quát, khoảng cách giữa 2 điểm x, y trong không gian Euclid R với n chiều được tính như sau: | | √∑ | | IV. TRUY VẤN HÌNH ẢNH DỰA TRÊN CÂY C-TREE 4.1. Cấu trúc dữ liệu lưu trữ cây Cây được tạo ra bằng cách thêm vào các ảnh, sau đó gom cụm các ảnh ở nút lá. Các ảnh được tổ chức như sau: Lable: mã ảnh đồng thời là tên lưu trữ ảnh (int) File: chứa đường dẫn tới ảnh trong bộ ảnh (string) Parent: nút chứa ảnh (nút) Rep: số lượng vùng ảnh có trong 1 ảnh (double) Coord: mảng chứa vùng ảnh (double []) Các nút được thể hiện cho một thành phần của cây được xây dựng. Có ba loại nút: Nút gốc, nút trong và nút lá. Mỗi nút được tổ chức và lưu trữ bao gồm: Lable: nhãn của nút, nút gốc Root bằng -1 (int) Center []: là tâm của nút, bao gồm tất cả các đặc trưng của nút con (double). Coord []: là tâm của nút, bao gồm các đặc trung giống nhau của các nút con (double). Distance: Độ đo tương tự tính khoảng cách để một ảnh có thể chứa trong lá, nút (double) Bac: bậc của nút trong cây (nút lá bằng 0, root mang bậc cao nhất) (int). Parent: nút cha của nút đang xét (root không có cha) (Nút) Rep: tổng số lượng đặc trưng của nút(int) Child []: mảng chứa lable của các nút con (child [] bằng null nếu nút đó là nút lá) (Nút). Arg []: mảng chứa các lable là mã ảnh (Arg [] bằng null khi nút là root hoặc nút nhánh) (double) 4.2. Thuật toán xây dựng cây Input: Tập dữ liệu hình ảnh được chú thích, được rút trích đặc trưng Output: Cây phân cụm C-tree tăng trưởng, tự cân bằng
5. 374 NÂNG CAO HIỆU QUẢ TRUY VẤN HÌNH ẢNH THEO NGỮ NGHĨA TRÊN CÂY PHÂN CỤM C-Tree B1: Khởi tạo Khởi tạo mảng Img [] với kiểu lưu trữ Image chứa tất cả các ảnh. Khởi tạo cây (tree) ban đầu với root (kiểu lưu trữ Nút) và Leaf (Kiểu lưu trữ Nút) Khởi tạo đọ đo tương tự Distance (xác định để một ảnh có thể vào một nút lá) B2: Lưu tất cả các hình ảnh chứa Img [] vào cây. B2.1: Nếu khoảng cách từ ảnh (đang xét) tới tâm Center của 1 nút lá bất kì bé hơn độ đo Distance: Thêm mã ảnh là mảng Arg [] của nút lá. Nếu số lượng ảnh tại nút lá lớn hơn m=15, hình ảnh nào có Distance xa tâm cụm hơn, sẽ được tách thành nút lá mới. Cập nhật tâm cụm Center nút cha của nút đang xét. Ngược lại, nếu khoảng cách từ ảnh (đang xét) tới tâm Center của 1 nút lá bất kì không lớn hơn Distance: chuyển sang bước B2.2 B2.2: Tìm kiếm một nút nhánh trong cây từ nút nhánh có bậc từ 2 trở đi Tìm được một nút nhánh có khoảng cách từ ảnh (đang xét) tới tâm Coord của 1 nút bất kì lớn hơn Distance Khởi tạo nút lá từ nút đang xét chứa ảnh. Cập nhật tâm cụm của nút cha chứa nút lá vừa được thêm vào B2.3: Ngược lại, Không tìm được nút nhánh có khoảng cách từ ảnh (đang xét) tới tâm Coord của 1 nút bất kì không lớn hơn Distance: Khởi tạo nút lá mới chứa ảnh. Tạo nút cha chứa nút lá. Thêm nút lá và nút cha của nó vừa mới tạo vào cây. B3: Duyệt ảnh Duyệt lại tất cả các ảnh (Sử dụng cờ Flag) Nếu Khoảng cách từ ảnh đến nút chứa ảnh nhỏ hơn giới hạn Limit_Tree  tìm kiếm Nút mới cho ảnh  cập nhật lại cây  gán cờ Flag: Nếu cờ Flag bằng True, quay lại B3; Nếu cờ Flag bằng False quay lại B2 4.3. Truy vấn hình ảnh dựa trên cây C-Tree: Quá trình truy vấn hình ảnh sẽ tìm ra các véctơ đặc trưng tương tự của hình ảnh dựa trên việc duyệt cây C-tree. Sau khi tìm ra các đặc trưng hình ảnh, dựa vào đường dẫn của các hình ảnh sẽ tìm ra cụ thể các hình ảnh tương tự với hình ảnh truy vấn, cùng với các chú thích ngữ nghĩa cho hình ảnh đó. Bài toán được đặt ra là cần thực hiện là tìm ra các véctơ đặc trưng tương tự của hình ảnh và các đường dẫn đến các hình ảnh đó, quá trình truy vấn này được thực hiện theo thuật toán đề xuất như sau: Input: các véctơ đặc trưng hình ảnh và cây C-Tree Output: Tập các hình ảnh tương tự và chú thích ngữ nghĩa của từng hình ảnh đó Tìm kiếm từ lá của cây. Duyệt từng lá trong cây, chọn toàn bộ ảnh trong lá có khoảng cách từ tâm center của lá đến véctơ đặc trưng của ảnh đang xét là nằm trong độ đo quy định. Xuất ra các hình ảnh tương tự, cùng các chú thích ngữ nghĩa cho từng hình ảnh V. ỨNG DỤNG THỰC NGHIỆM VÀ THẢO LUẬN 5.1. Mô hình truy vấn hình ảnh Dựa trên cơ sở lý thuyết và các thuật toán đã đề nghị ở trên, chúng tôi xây dựng mô hình tìm kiếm ảnh theo ngữ nghĩa trên cây phân cụm C-Tree. Mô hình truy vấn ảnh bao gồm hai pha: pha thứ nhất gọi là pha tiền xử lý, thực hiện chuyển đổi các hình ảnh chú thích thành các hình ảnh tương tự được gom cụm và sắp xếp trên cây C-Tree. Pha thứ hai là pha thực hiện quá trình truy vấn, khi có một hình ảnh được đưa vào, sẽ được truy vấn trên cây phân cụm C-tree để tìm ra các hình ảnh tương tự, đồng thời trích xuất ngữ nghĩa cho các hình ảnh đó. Pha 1: Tiền xử lý Bộ hình ảnh có chú thích được rút trích các véctơ đặc trưng
6. Nguyễn Thị Uyên Nhi, Văn Thế Thành, Lê Mạnh Thạnh 375 Thực hiện thuật toán K-means với độ đo tương tự được đề xuất Euclid để gom cụm các hình ảnh tương tự Sắp xếp các hình ảnh trên cây phân cụm C-tree với các túi từ tại các nút lá Tiếp tục ch n thêm hình ảnh cho đến hết bộ dữ liệu đầu vào để hoàn thành cây C-tree Pha tiền xử lý dừng lại khi tất cả các ảnh đầu vào được gom cụm, sắp xếp trên cây gom cụm C-tree Pha 2: Truy vấn ảnh Với mỗi hình ảnh đầu vào cần truy vấn sẽ được phân đoạn để rút trích véctơ đặc trưng. Đây là quá trình để tạo ra chỉ mục truy vấn Thực hiện truy vấn hình ảnh đầu vào trên cây C-tree. Hình ảnh tương tự được tìm kiếm tại nút lá của cây phân cụm thông qua độ đo Euclid Kiểm tra túi từ tại nút lá với véctơ từ thị giác của hình ảnh để cho ra các hình ảnh tương tự Giải thích ngữ nghĩa bằng file .xml. Hình 2. Mô hình tìm kiếm ảnh theo ngữ nghĩa trên cây C-tree 5.2. Ứng dụng thực nghiệm Trong thực nghiệm của bài báo, chúng tôi sử dụng bộ dữ liệu ImageCLEF, bao gồm 20.000 hình ảnh, được lưu trữ thành 40 bộ nhỏ. Mục tiêu của ImageCLEF là: Truy vấn thông tin (văn bản, hình ảnh, âm thanh, đa phương tiện, phương tiện truyền thông xã hội, dữ liệu cảm biến, v.v.); Học máy, học sâu; Khai phá dữ liệu; Xử lý ngôn ngữ tự nhiên; Xử lý hình ảnh và video; Thị giác máy tính Bộ ảnh ImageCLEF được tổ chức như sau: Tập các hình ảnh gốc và tập các hình ảnh được phân vùng File chứa các véctơ đặc trưng của từng vùng theo từng ảnh. Các véctơ đặc trưng được lưu thành các mảng có 29 chiều, trong đó giá trị đầu tiên và giá trị cuối là nhãn của hình ảnh File chứa các nhãn của hình ảnh, bao gồm thứ tự vùng và tham chiếu đến ngữ nghĩa của vùng hình ảnh trong file vecto từ thị giác. Vecto từ thị giác chứa các ngữ nghĩa được đánh dấu theo số thứ tự. Chúng tôi dùng 35 bộ ảnh nhỏ để huấn luyện trong pha tiền xử lý, và 5 bộ ảnh sẽ được sử dụng để thử nghiệm tính chính xác trong truy vấn hình ảnh của ứng dụng thực nghiệm trong pha truy vấn hình ảnh. Mỗi hình ảnh được trích xuất các véctơ đặc trưng, thực hiện phương pháp phân cụm dựa trên độ đo Euclid để gom cụm các hình ảnh có đặc trưng tương tự trên cây C-Tree.
7. 376 NÂNG CAO HIỆU QUẢ TRUY VẤN HÌNH ẢNH THEO NGỮ NGHĨA TRÊN CÂY PHÂN CỤM C-Tree Hình 3. Giao diện tạo cây C-Tree 5.3. Kết quả thực nghiệm Thực hiện truy vấn hình ảnh từ các hình ảnh trong bộ dữ liệu thử của ImageCLEF. 1000 1 52 child-boy 1000 2 59 Cloth Véctơ 1000 3 124 hat đặc trưng 1000 4 88 face-of-person 1000 5 264 wall (a) (b) (c) Hình 4. Hình ảnh truy vấn (a) Hình ảnh cần tìm kiếm; (b) Hình ảnh được phần vùng; (c) Chú thích các vùng của hình ảnh Hình 5. Kết quả truy vấn ảnh
8. Nguyễn Thị Uyên Nhi, Văn Thế Thành, Lê Mạnh Thạnh 377 5.4. Thảo luận về kết quả ứng dụng thực nghiệm Quá trình thực nghiệm sẽ truy vấn hình ảnh trên bộ dữ liệu mẫu ImageCLEF bao gồm 20,000 hình ảnh khác nhau. Với mỗi hình ảnh truy vấn sẽ được trích lọc đặc trưng trên dữ liệu ảnh và tìm ra các hình ảnh có độ tương tự nhiều nhất với hình ảnh truy vấn, từ đó đối sánh với danh mục chủ đề hình ảnh nhằm đánh giá độ chính xác của phương pháp. Thực nghiệm cho thấy, hình ảnh tương tự tìm được có tính chính xác cao với hình ảnh truy vấn. Các véctơ đặc trưng được rút trích từ hình ảnh truy vấn có độ tương đồng cao với các hình ảnh tương tự được truy xuất. Trong thực nghiệm của chúng tôi, đều đưa ra hình ảnh là khuôn mặt của bé trai, đội mũ, mang đồ ấm Các hình ảnh được phân cụm trên cây C-tree giúp cho thời gian tìm kiếm nhanh và độ chính xác cao, do đường đi của quá trình tìm kiếm theo tâm của các nút theo chủ đề. (a) (b) Hình 6. (a) Thời gian tạo cây C-Tree (ms); (b) Thời gian truy vấn hình ảnh trên cây C-Tree (ms) IV. KẾT LUẬN Trong bài báo, chúng tôi đã đề xuất khoảng cách độ đo tương tự Euclid theo ngữ nghĩa giữa hai hình ảnh dựa trên đặc trưng thị giác cấp thấp, tạo ra véctơ từ thị giác hình ảnh, đồng thời xây dựng cấu trúc cây phân cụm C-tree nhằm lưu trữ và nâng cao hiệu quả tìm kiếm hình ảnh tương tự, trích xuất ngữ nghĩa của các hình ảnh tương tự dựa trên véctơ từ thị giác đã được tạo ra. Từ đó, chúng tôi xây dựng được mô hình tìm kiếm ảnh theo ngữ nghĩa dựa trên cây phân cụm C-tree và xây dựng ứng dụng, đánh giá thực nghiệm trên bộ dữ liệu ảnh ImageCLEF. Trong hướng phát triển tương lai, chúng tôi xây dựng một hệ truy vấn dữ liệu dựa trên các cấu trúc dữ liệu và thuật toán đã đề xuất, nhằm so sánh và đánh giá với các phương pháp được công bố gần đây. Đồng thời cải tiến thuật toán xây dựng cây C-tree và truy vấn hình ảnh để nâng cao hiệu quả tìm kiếm. TÀI LIỆU THAM KHẢO [1] Yihun Alemu, Jong-bin Koh, Muhammed Ikram and Dong-Kyoo Kim. “Image Retrieval in Multimedia Databases: A Survey”. 2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IEEE, 2009. [2] D. C. Pedronette, J. Almeida (201z4), R. S. Torres. “A scalable re-ranking method for content-based image retrieval”. Information Sciences, Volume 265, 1 May 2014, Pages 91-104 [3] Benavent, Joan, et al “Experiences at ImageCLEF 2010 using CBIR and TBIR Mixing Information Approaches”. CLEF (Notebook Papers/LABs/Workshops). 2010. [4] Daniel Carlos Guimarães Pedronette, Jurandy Almeida, Ricardo da S. Torres. “A scalable re-ranking method for content-based image retrieval”. Information Sciences, Volume 265, 1 May 2014, Pages 91-104 [5] Hong Ying Yang, Yong Wei Li, Wei Yi Li, Xiang Yang Wang, Fang Yu Yang. “Content-based image retrieval using local visual attention feature”. Journal of Visual Communication and Image Representation, Volume 25, Issue 6, August 2014, Pages 1308-1323. [6] Smeulders AWM, Worring M, Santini S, Gupta A, Jain R. “Content-based image retrieval at the end of the early years”. IEEE Trans Pattern Anal Mach Intell 22(12):1349-1380, 2000 [7] Kurtz Camille, et al “On combining image-based and ontological semantic dissimilarities for medical image retrieval applications”. Medical image analysis 18.7 (2014): 1082-1100. [8] Yihun Alemu, Jong-bin Koh, Muhammed Ikram and Dong-Kyoo Kim. “Image Retrieval in Multimedia Databases: A Survey”. 2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IEEE, 2009.
9. 378 NÂNG CAO HIỆU QUẢ TRUY VẤN HÌNH ẢNH THEO NGỮ NGHĨA TRÊN CÂY PHÂN CỤM C-Tree [9] James, Nicolas, Konstantin Todorov, and Céline Hudelot. “Ontology matching for the semantic annotation of images”. Fuzzy Systems (FUZZ), 2010 IEEE International Conference on. IEEE, 2010. [10] A. Olfa, et al (2017). “Pattern graph-based image retrieval system combining semantic and visual features”. Multimedia Tools and Applications: 1-30. [11] Slamet, Cepy, Ali Rahman, Muhammad Ali Ramdhani, and Wahyudin Darmalaksana. “Clustering the Verses of the Holy Qur'an using K-Means Algorithm”. Asian Journal of Information Technology 15, no. 24 (2016): 5159- 5162. [12] Velmani, Ramasamy, and Balakrishnan Kaarthick. “An efficient cluster-tree based data collection scheme for large mobile wireless sensor networks”. IEEE sensors journal 15.4 (2015): 2377-2390. IMPROVE EFFICIENCY IMAGE RETRIEVAL IN SEMATIC APPROACH ON C-Tree Nguyen Thi Uyen Nhi, Van The Thanh, Le Manh Thanh ABSTRACT: Image data is growing rapidly in multimedia systems, making it difficult to find image information. In this article, we build a semantic image query model to improve the efficiency of similar image retrieval. In order to implement this model, we propose K-means method for clustering visual features of the image, including: determining the center of clusters based on the method of moving to the data region dense, suggesting a semantically similar measure of distance between two images based on low-level visual features, generating visual vector word for images, constructing a C-tree clustering tree structure for storage and improve the efficiency of the same image search; From there, we extracted the semantics of similar images based on the visual vector word that was generated.