Xem mẫu
- 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ế
2
Trường Đại học Công nghiệp Thực phẩm TP.HCM
3
Trườ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.
- 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ả.
- 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 < n là số cluster
chúng ta muốn phân chia.
Chúng ta cần tìm các center
Chọn ngẫu nhiên k điểm bất kì làm điểm trung tâm:
Bước 2: Phân cụm dữ liệu dựa trên điểm trung tâm:
Nhóm mỗi điểm dữ liệu ảnh vào 1 cụm có điểm trung tâm gần nhất với nó. Sử dụng độ đo tương tự Euclid để
tìm khoảng cách gần nhất đến tâm cụm, lúc này:
Nếu các cụm sau khi phân cụm không thay đổi so với trước khi phân cụm thì giải thuật dừng lại
Bước 3: Cập nhật trung tâm:
Với mỗi cụm sau khi gom lại, ta cập nhập lại điểm trung tâm của chúng bằng cách lấy trung bình cộng
∑
| |
Sau khi cập nhật trung tâm, quay lại bước 2 cho đến hết các dữ liệu ảnh cần gom cụm. Các hình ảnh được lưu
trữ theo cấu trúc của cây gom cụm C-Tree
3.3. Cây C-Tree (Cluster tree)
Cây phân cụm C-Tree (Cluster Tree) [12] là một cây phân cụm tăng trưởng, tập hợp các phần tử (các nút). Mỗi
nút của C-Tree gồm n phần tử là dữ liệu ảnh tương đương. Mỗi hình ảnh được cấp 1 định danh là các cặp phần tử
, 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
- 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
- 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
- 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.
- 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
- 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.
- 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.
nguon tai.lieu . vn
