Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019
DOI: 10.15625/vap.2019.00061
TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN ĐỒ THỊ CỤM
Nguyễn Văn Thịnh1, Nguyễn Thị Định1, Văn Thế Thành2,*
1
Khoa Công nghệ Thông tin, Trường ĐH Công nghiệp Thực phẩm TP.HCM
2
Phòng Quản lý khoa học và Đào tạo Sau đại học, Trường ĐH Công nghiệp Thực phẩm TP.HCM
nvanthinh@gmail.com, nguyenthidinh.hcm@gmail.com,vanthethanh@gmail.com
TÓM TẮT: Bài toán truy vấn ảnh theo ngữ nghĩa SBIR (Semantic-Based Image Retrieval) được quan tâm trong những năm gần đây
vì hướng tiếp cận này có thể trích xuất ngữ nghĩa hình ảnh và khắc phục được nhược điểm của phương pháp truy vấn ảnh theo văn
bản TBIR (Text-Based Image Retrieval) cũng như theo nội dung CBIR (Content-Based Image Retrieval). Vì vậy, trong bài báo này,
chúng tôi đề xuất phương pháp truy vấn ảnh và trích xuất ngữ nghĩa bằng đồ thị đặc trưng thị giác của hình ảnh và đồ thị cụm. Để
thực hiện vấn đề này, phương pháp gom cụm đặc trưng thị giác hình ảnh được đề xuất nhằm tạo ra đồ thị cụm để từ đó trích xuất
ngữ nghĩa hình ảnh. Trước hết, chúng tôi đề xuất cấu trúc đồ thị mô tả hình ảnh và độ đo tương tự dựa trên đặc trưng thị giác cấp
thấp cùng với quan hệ không gian giữa các vùng trong ảnh. Sau đó, đồ thị cụm được tạo ra bằng phương pháp gom cụm các đồ thị
đặc trưng của hình ảnh trên cơ sở độ đo đã được đề xuất; đồng thời, chúng tôi xây dựng ontology mô tả ngữ nghĩa cho tập dữ liệu
ảnh và tạo ra câu truy vấn SPARQL dựa trên véctơ từ thị giác của hình ảnh nhằm thực hiện truy vấn trên ontology. Dựa trên cấu
trúc đồ thị cụm và ontology đã xây dựng, chúng tôi đề xuất thuật toán tra cứu và trích xuất ngữ nghĩa hình ảnh. Nhằm chứng minh
cơ sở lý thuyết đã đề xuất, thực nghiệm được xây dựng và đánh giá trên tập dữ liệu ảnh ImageCLEF; kết quả thực nghiệm được
đánh giá so với các phương pháp khác đã được công bố gần đây trên cùng tập dữ liệu. Từ kết quả thực nghiệm cho thấy phương
pháp đề xuất của chúng tôi là hiệu quả và có thể ứng dụng trong nhiều hệ thống dữ liệu đa phương tiện.
Từ khóa: SBIR, image retrieval, clustering, ontology, SPARQL.
I. GIỚI THIỆU
Trong những thập niên gần đây, tìm kiếm ảnh là một trong những chủ đề được nhiều nhà khoa học quan tâm
nghiên cứu. Có nhiều phương pháp tìm kiếm hình ảnh như tìm kiếm hình ảnh dựa trên các từ khoá TBIR (Text - Based
Image Retrieval) được giới thiệu từ những năm 1970, tìm kiếm hình ảnh dựa trên nội dung CBIR (Content - Based
Image Retrieval) được giới thiệu từ những năm 1980, tìm kiếm ảnh dựa trên ngữ nghĩa SBIR (Semantic - Based Image
Retrieval) là bài toán được quan tâm hiện nay [10]. Nhiều công trình nghiên cứu về tìm kiếm ảnh tương tự đã được
phát triển dựa trên đặc trưng cấp thấp như truy vấn ảnh dựa trên hình dạng (shape), màu sắc (color), cấu trúc (texture),
đối tượng đặc trưng (interest objects),… [17]. Để giải quyết bài toán tra cứu dữ liệu ảnh, đã có nhiều hệ thống tìm
kiếm ảnh được phát triển như QBIC, Photobook, Visual-Seek, MARS, El Nino, CIRES, PicSOM, PicHunter,
MIRROR, Virage, Netra, SIMPLITcity,…[15].
Mặt khác, 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ồ. 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 ảnh được chia sẻ trong mỗi phút và có 2,5
nghìn tỉ ảnh được chia sẻ và lưu trữ trực tuyến. Năm 2017, thế giới đã tạo ra 1,2 nghìn tỉ ảnh và tổng số ảnh toàn cầu
đến năm 2017 là 4,7 nghìn tỉ [8, 9]. Ảnh số đã được sử 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, hệ thống thông tin địa lý, thư viện số, ứng dụng y sinh, giáo dục đào tạo, giải trí,... [26].
Vì vậy, bài toán khai phá dữ liệu ảnh và tra cứu các thông tin liên quan đến hình ảnh cần được quan tâm giải quyết.
Tuy nhiên, nếu tìm kiếm ảnh dựa trên việc đối sánh trực tiếp thì tốn nhiều thời gian và bộ nhớ lưu trữ. Do đó,
chúng ta cần xây dựng phương pháp mô tả ảnh dưới dạng dữ liệu chỉ mục để tìm kiếm ảnh qua dữ liệu mô tả này. Hầu
hết các công trình tìm kiếm ảnh tương tự tập trung vào kỹ thuật trích chọn đặc trưng hình ảnh. Do đó, việc tạo ra các
cấu trúc dữ liệu lưu trữ đặc trưng hình ảnh nhằm tăng tốc độ tìm kiếm là một thách thức cho các bài toán tìm kiếm ảnh
tương tự. Ngoài ra, bài toán phân tích ngữ nghĩa hình ảnh và tìm kiếm tập hình ảnh tương đồng với ngữ nghĩa là một
trong những vấn đề cần giải quyết hiện nay. Một phương pháp giải quyết bài toán này là trích xuất ngữ nghĩa từ một
tập ngữ liệu cho trước và xây dựng các ontology mô tả nội dung hình ảnh. Trên cơ sở các ontology này, các hình ảnh
được truy vấn theo yêu cầu người dùng dưới dạng ngôn ngữ tự nhiên. Do đó, quy trình tìm kiếm hình ảnh theo hướng
tiếp cận ngữ nghĩa phải được xây dựng.
Trong bài báo này, chúng tôi xây dựng một phương pháp tìm kiếm ảnh tương tự trên cơ sở hướng tiếp cận theo
phân tích ngữ nghĩa của nội dung hình ảnh. Dữ liệu mô tả hình ảnh được xây dựng và lưu trữ trên đồ thị cụm đồng thời
các thuật toán cho quá trình tìm kiếm ảnh dựa trên đồ thị cụm được đề xuất. Mục tiêu của bài báo là xây dựng hệ truy
vấn ảnh theo ngữ nghĩa dựa trên đồ thị cụm nhằm tăng tốc độ tìm kiếm và đảm bảo được độ chính xác. Đóng góp của
bài báo gồm: (1) xây dựng đồ thị đặc trưng của hình ảnh; (2) đề xuất độ đo tương tự giữa hai đồ thị nhằm đánh giá độ
tương tự giữa các hình ảnh; (3) xây dựng cấu trúc đồ thị cụm nhằm tăng tốc độ tìm kiếm cũng như tra cứu ảnh; (4) đề
xuất các thuật toán về xây dựng đồ thị cụm cũng như thuật toán tìm kiếm hình ảnh và trích xuất ngữ nghĩa; (5) đề xuất
mô hình truy vấn ảnh tương tự và trích xuất ngữ nghĩa dựa trên các cơ sở lý thuyết và thuật toán đã xây dựng; (6) xây
dựng ứng thực nghiệm về mô hình truy vấn ảnh và trích xuất ngữ nghĩa trên bộ dữ liệu ImageCLEF.
* Corresponding author
- Nguyễn Văn Thịnh, Nguyễn Thị Định, Văn Thế Thành 477
Phần còn lại của bài báo được tổ chức như sau: Phần II. đề cập đến các công trình nghiên cứu liên quan nhằm
phân tích tính khả thi của phương pháp đề xuất; Phần III. xây dựng cấu trúc dữ liệu nhằm lưu trữ dữ liệu mô tả của hình
ảnh; độ đo tương tự, đồ thị đặc trưng và đồ thị cụm cũng được mô tả trong phần này; Phần IV. thực hiện phân tích ngữ
nghĩa của nội dung hình ảnh và tìm kiếm ảnh dựa trên véctơ từ, ontology và câu truy vấn SPARQL; mô hình tìm kiếm ảnh
và thực nghiệm được trình bày trong Phần V; kết luận và hướng phát triển được trình bày trong Phần VI.
II. CÁC CÔNG TRÌNH LIÊN QUAN
Nhiều công trình liên quan đến tìm kiếm ảnh đã được tiếp cận và công bố trong những năm gần đây. Phương
pháp gom cụm đã được ứng dụng trong nhiều hệ thống tìm kiếm ảnh như áp dụng thuật toán K-means để gom cụm đặc
trưng màu sắc hình ảnh [7]; tìm kiếm ảnh dự trên thuật toán K-means và chữ ký nhị phân của hình ảnh [21]; tìm kiếm
ảnh dựa trên thuật toán K-means và khoảng cách Mahalanobis giữa các véc-tơ màu sắc của các hình ảnh [4]; áp dụng
thuật toán K-means và dải màu MPEG7 cho việc gom cụm và tìm kiếm ảnh [11]; thực hiện gom cụm kết hợp đặc trưng
màu sắc, hình dạng và cấu trúc hình ảnh để tìm kiếm ảnh tương tự [18],… Ngoài ra, nhiều công trình nghiên cứu trích
xuất ngữ nghĩa hình ảnh và tìm kiếm ảnh tương tự cũng đã được giới thiệu trong những năm gần đây như: tìm kiếm
ảnh dựa trên túi từ thị giác [16], tra cứu ảnh dựa trên việc phân tích ngôn ngữ tự nhiên để tạo ra câu truy vấn SPARQL
[25], xây dựng công cụ I2T (Image to Text) nhằm tạo ra các RDF mô tả ngữ nghĩa hình ảnh [3],… Theo kết quả các
công trình đã công bố gần đây cho thấy phương pháp tìm kiếm ảnh theo tiếp cận ngữ nghĩa bằng kỹ thuật gom cụm là
khả thi và đạt kết quả tốt.
Năm 2003, kỹ thuật tạo cấu trúc đồ thị cụm dựa trên thuật toán K-mean được thực hiện bởi Hlaoui & Wang [1].
Năm 2013, phương pháp tìm kiếm ảnh tương tự bằng đồ thị dựa trên ngữ nghĩa giữa các hình ảnh của Zhao và công sự
[19]. Năm 2014, việc phân cụm tập dữ liệu hình ảnh dựa trên đặc điểm cấp thấp và xây dựng đồ thị cụm để áp dụng
trong CBIR được thực nghiệm bởi Yan, Liu, Wang, Zhang, & Zheng [27]. Năm 2015, một công trình nghiên cứu tìm
kiếm ảnh theo nội dung dựa trên cấu trúc dữ liệu đồ thị được xây dựng trên cơ sở đặc trưng cấp thấp của hình ảnh và áp
dụng trong truy vấn hình ảnh của Xu, Bu, Wang, & He [5],...
C.A. Hernández-Gracidas và cộng sự (2013) thực hiện nâng cao hiệu suất tìm kiếm ảnh dựa trên quan hệ không
gian giữa các vùng trong ảnh. Hình ảnh được biểu diễn bằng đồ thị khái niệm dựa trên đặc trưng quan hệ không gian,
pha tìm kiếm ảnh thực hiện đối sánh trên toàn bộ cơ sở dữ liệu ảnh và trả về top - k ảnh liên quan nhất dựa vào độ đo
[13]. Mô hình này không sử dụng đặc trưng cấp thấp biểu diễn nội dung của hình ảnh để tăng độ chính xác, bên cạnh
đó thời gian tra cứu ảnh chậm do phải so khớp tuyến tính trong toàn bộ cơ sở dữ liệu ảnh.
Năm 2014, Van T. T. và cộng sự đã giới thiệu một phương pháp tìm kiếm ảnh dựa trên chữ ký nhị phân và đồ thị
S-kGraph. Tuy nhiên, việc sử dụng các tính năng của màu sắc cho kết quả với độ chính xác chưa cao [24]. Năm 2016,
nhóm tác giả này đã thực hiện một phương pháp gom cụm chữ ký nhị phân của hình ảnh để tạo cấu trúc đồ thị cụm.
Phương pháp đã cải tiến thời gian tìm kiếm nhưng vẫn chưa tiếp cận bài toán tìm kiếm hình ảnh theo ngữ nghĩa [22].
Hakan Cevikalp và cộng sự (2017) thực hiện tra cứu ảnh dựa trên cấu trúc đồ thị và cây phân cấp nhị phân. Quá
trình huấn luyện được thực hiện theo phương pháp SVM (Support Vector Machines) dựa trên các đặc trưng cấp thấp
của hình ảnh [12]. Phương pháp đã thực nghiệm trên bộ ảnh ImageCLEF và so sánh tính hiệu quả với các phương pháp
khác. Tuy nhiên, phương pháp này chưa phân tích ngữ nghĩa của hình ảnh cũng như không xây dựng cấu trúc dữ liệu
nhằm tăng tốc độ tra cứu hình ảnh.
Van T. T. và cộng sự (2017) đề xuất hệ tìm kiếm ảnh theo nội dung dựa trên đồ thị cụm chữ ký nhị phân. Tác
giả thực hiện gom cụm chữ ký nhị phân mô tả đặc trưng thị giác cấp thấp của ảnh và tạo đồ thị cụm lưu trữ các chữ ký
nhị phân này nhằm nâng cao hiệu quả tìm kiếm ảnh. Phương pháp đã thực nghiệm trên nhiều bộ dữ liệu và so sánh tính
hiệu quả với nhiều phương pháp khác nhau [23]. Tuy nhiên, nhóm tác giả vẫn chưa trích xuất được ngữ nghĩa cho hình
ảnh và tìm kiếm dựa trên ngữ nghĩa này.
B. B. Z. Yao et al. (2010) giới thiệu công cụ I2T (Image to Text) nhằm tạo ra các RDF mô tả ngữ nghĩa hình
ảnh để từ đó người dùng có thể truy vấn thông qua ngữ nghĩa này. Đồ thị AoG (and-or Graph) được sử dụng để chuyển
đổi quan hệ của các thành phần trong hình ảnh trở thành ngữ nghĩa tự nhiên nhằm mô tả hình ảnh [28]. Đây là một hệ
thống tìm kiếm ngữ nghĩa của hình ảnh và giúp cho bài toán tra cứu ảnh theo tiếp cận ngữ nghĩa được hoàn thiện hơn.
Vijayarajan et al. (2016) thực hiện tra cứu ảnh dựa trên việc phân tích ngôn ngữ tự nhiên để tạo ra câu truy vấn
SPARQL nhằm tìm kiếm tập hình ảnh dựa trên RDF mô tả ảnh [25]. Quá trình tìm kiếm hình ảnh phụ thuộc vào việc
phân tích văn phạm của ngôn ngữ để tạo thành các từ khóa mô tả nội dung hình ảnh. Phương pháp này chưa thực hiện
phân lớp nội dung hình ảnh từ các đặc trưng màu sắc và đặc trưng không gian để tạo các từ khóa nhằm thực hiện tra
cứu; do đó chưa thực hiện quá trình tìm kiếm từ một hình ảnh truy vấn cho trước.
Safia Jabeen et al., (2018) xây dựng mô hình tìm kiếm ảnh dựa trên túi từ thị giác bằng cách gom cụm các đặc
trưng thị giác kết hợp với ngữ nghĩa của các bộ phân loại hình ảnh [20]. Tuy nhiên, việc gom cụm các đặc trưng thị
giác cấp thấp có thể tạo ra các cụm gồm các hình ảnh có nhiều ngữ nghĩa khác nhau dẫn đến việc tìm kiếm ngữ nghĩa
của hình ảnh truy vấn bị sai lệch. Do đó, phương pháp phân lớp ngữ nghĩa từ đặc trưng cấp thấp cần phải được áp dụng
và đồng thời chuyển đổi từ đặc trưng này trở thành ngữ nghĩa cho hình ảnh.
- 478 TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN ĐỒ THỊ CỤM
Từ các công trình đã công bố cho thấy bài toán tra cứu ảnh có nhiều sự quan tâm của các nhóm tác giả. Hơn nữa, việc
áp dụng đồ thị cụm để thực hiện tìm kiếm ảnh tương tự theo ngữ nghĩa là một hướng tiếp cận có tính khả thi và nhiều thách
thức [3]. Trên cơ sở kế thừa từ các công trình đã có và khắc phục những hạn chế của các phương pháp liên quan đã công bố,
đồng thời tạo ra một hệ truy vấn ảnh theo ngữ nghĩa nhằm nâng cao hiệu quả tìm kiếm, chúng tôi đề xuất một mô hình truy
vấn ảnh bằng cách tạo đồ thị kết hợp đặc trưng thị giác cấp thấp và quan hệ không gian của hình ảnh; sau đó gom cụm các đồ
thị đặc trưng thị giác nhằm nâng cao hiệu suất cho quá trình tìm kiếm ảnh tương tự. Vì vậy, hệ tra cứu ảnh tương tự dựa trên
đồ thị cụm được chúng tôi tiếp cận và thực hiện để từ đó nâng cao hiệu suất tìm kiếm ảnh.
III. ĐỒ THỊ ĐẶC TRƢNG THỊ GIÁC VÀ ĐỒ THỊ CỤM
A. Phân vùng ảnh và trích xuất đặc trưng
Mỗi hình ảnh trong tập dữ liệu được phân thành nhiều vùng khác nhau theo phương pháp của Hugo Jair
Escalante [14]. Hình 1 mô tả một ảnh gốc và 5 ảnh của các vùng thuộc về các lớp ảnh: ground, rock, cloud, sky-blue,
vegetation của ảnh 2966.jpg trong bộ dữ liệu ảnh ImageCLEF. Mỗi vùng được trích xuất một véctơ đặc trưng bao gồm
đặc trưng vùng: diện tích, chiều rộng và chiều cao; đặc trưng về 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; đặc trưng màu sắc trong không gian RGB và CIE-Lab [6].
Ảnh gốc và các ảnh phân vùng (2966.jpg)
B. Ma trận topo
Để nâng cao độ chính xác cho hệ thống tìm kiếm ảnh, chúng tôi đề xuất sử dụng mối quan hệ không gian giữa
các vùng trong ảnh kết hợp với đặc trưng thị giác của hình ảnh. Mối quan hệ không gian giữa hai vùng được định nghĩa
như sau:
Định nghĩa 1. Cho lần lượt là hai vùng của ảnh I. Hai vùng được gọi là kề nhau, ký hiệu ( ) ,
nếu giao điểm giữa chúng khác rỗng, ngược lại thì gọi là hai vùng tách rời, ký hiệu ( ) .
Từ tập đặc trưng vùng của một hình ảnh đã được trích xuất, ma trận topo tương ứng của hình ảnh được định
nghĩa như sau:
Định nghĩa 2. Cho là n vùng của ảnh I. Ma trận topo của ảnh I, ký hiệu , được nghĩa như sau:
( )
C. Đồ thị mô tả đặc trưng thị giác của hình ảnh
Sau khi trích xuất đặc trưng thị giác của vùng và quan hệ không gian giữa các vùng trong ảnh, chúng tôi tạo đồ
thị đặc trưng thị giác mô tả nội dung của hình ảnh, mỗi đồ thị tương ứng với một ảnh. Do đó, đồ thị đặc trưng thị giác
của hình ảnh được định nghĩa như sau:
Định nghĩa 3. Đồ thị đặc trưng thị giác là đồ thị vô hướng có trọng số , trong đó tập đỉnh , tập cạnh
được định nghĩa như sau:
( )
Với là vùng ảnh thứ trong vùng ảnh của ; , lần lượt là định danh và đặc trưng thị giác của vùng
ảnh thứ ; trọng số của mỗi cạnh là giá trị . Hình 2 minh họa đồ thị đặc trưng thị giác của ảnh
2966.jpg trong tập dữ liệu ảnh ImageCLEF.
Ảnh phân đoạn và đồ thị đặc trưng thị giác của ảnh 2966.jpg
- Nguyễn Văn Thịnh, Nguyễn Thị Định, Văn Thế Thành 479
D. Độ đo tương tự giữa hai đồ thị đặc trưng thị giác
Độ đo tương tự giữa hai hình ảnh là thành phần không thể thiếu khi thực hiện quá trình gom cụm và truy vấn
các hình ảnh tương tự. Mỗi hình ảnh được mô tả dưới dạng một đồ thị, do đó vấn đề đặt ra là xây dựng độ đo tương tự
giữa hai đồ thị để từ đó đánh giá độ tương tự giữa các hình ảnh. Dựa trên đồ thị đặc trưng của hình ảnh, chúng tôi định
nghĩa độ đo tương tự giữa các hình ảnh như sau:
Cho hai tập đỉnh có tập véctơ đặc tính của các đỉnh lần lượt là và
, với , lần lượt là số đỉnh của và .
Định nghĩa 4. Ma trận tương quan thị giác giữa hai tập đỉnh , được định nghĩa như sau:
| ( ) ( ) } (1)
Cho hai đồ thị , có tập véctơ đặc tính của các đỉnh lần lượt là và ,
với lần lượt là số đỉnh của đồ thị và . Độ đo tương tự được định nghĩa như sau:
Định nghĩa 5. Độ đo tương tự theo đặc trưng thị giác giữa hai đồ thị và là:
( ) (2)
Mệnh đề 1. Độ đo ( ) là một metric vì có các tính chất sau:
(1) Không âm: ( ) và ( )
(2) Đối xứng: ( ) ( )
(3) Bất đẳng thức tam giác: ( ) ( )
Chứng minh: Dễ dàng chứng minh được d ( ) thỏa ba tính chất như trên
Định nghĩa 6. Gọi và lần lượt là hai đỉnh của đồ thị và có nhỏ nhất. Khi đó, ta có
và lần lượt là tập véctơ đặc tính của tập đỉnh kề tương ứng với hai đỉnh và
, ký hiệu là và . Độ đo thị giác trung bình giữa hai tập đỉnh kề được định nghĩa như sau:
( ) (3)
Mệnh đề 2. Độ đo ( ) là một metric.
Chứng minh: Dễ dàng kiểm chứng ( ) là một metric.
Dựa trên công thức (2) và (3), độ đo tượng tự giữa 2 đồ thị được tính theo công thức (4) như sau:
( ) (4)
Mệnh đề 3. Độ đo ( ) là một metric.
Chứng minh: Dễ dàng chứng minh được ( ) là một metric.
E. Đồ thị cụm
1. Cấu trúc đồ thị cụm
Sau khi tạo đồ thị đặc trưng thị giác của hình ảnh và độ đo tương tự giữa hai hình ảnh. Chúng tôi đề xuất cấu
trúc đồ thị cụm và thuật toán gom cụm các đồ thị đặc trưng thị giác theo độ đo tương tự để tạo ra đồ thị cụm. Đồ thị
cụm nhằm mục đích tạo ra một mô hình khai phá dữ liệu phân cụm tự động cho các bộ dữ liệu véctơ đặc tính, đồng
thời cải tiến quá trình tìm kiếm ảnh tương tự. Quá trình tạo ra đồ thị cụm được dựa trên sự kết hợp giữa phương pháp
phân cụm phân hoạch và kỹ thuật học bán giám sát (semi-supervisor learning). Kết quả của việc tạo đồ thị là xây dựng
một mô hình để tìm kiếm nhanh các cụm phù hợp cho mỗi ảnh đầu vào.
Do đó chúng tôi đề xuất xây dựng cụm các đồ thị đặc trưng thị giác để mô tả mỗi quan hệ giữa các hình ảnh,
mỗi cụm bao gồm các đồ thị đặc trưng thị giác của các hình ảnh tương tự, trong đó có một phần tử đại diện là tâm cụm.
Định nghĩa 7. Cho là tập đồ thị đặc trưng của tập dữ liệu ảnh. Một cụm có tâm được định nghĩa như sau:
với là bán kính của cụm , , là độ đo tương tự giữa và theo công thức (4).
Ứng với mỗi đồ thị đặc trưng thị giác của ảnh cần phải phân bố vào các cụm. Do đó, cần phải có quy tắc phân
bố các đồ thị đặc trưng của ảnh vào các cụm. Quy tắc phân bố được định nghĩa như sau:
- 480 TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN ĐỒ THỊ CỤM
Định nghĩa 8. Cho là tập các cụm rời nhau. Gọi là đồ thị đặc trưng của ảnh cần phân bố vào tập
cụm , là tâm của cụm sao cho , với là tâm của cụm ,
n là số cụm ở thời điểm hiện hành. Có 3 trường hợp như sau:
(1) Nếu thì đồ thị đặc trưng được phân bố vào cụm .
(2) Nếu
(2.1) Nếu thì tạo cụm có tâm , bán kính [ ] và .
(2.2) Ngược lại ( ), thì phân bố đồ thị đặc trưng vào cụm và .
Theo quy tắc phân bố đồ thị đặc trưng của ảnh ở Định nghĩa 8, nếu các đồ thị đặc trưng được phân bố vào các
cụm thì phải đảm bảo được rằng mỗi đồ thị chắc chắn được phân bố trong các cụm. Hơn nữa, để tránh dư thừa dữ liệu
và kết quả tìm kiếm là nhất quán thì mỗi đồ thị đặc trưng chỉ được phân bố về một cụm duy nhất.
Định lý 1. Các đồ thị đặc trưng của ảnh đều được phân bố vào các cụm .
Chứng minh:
Gọi I là đồ thị đặc trưng của một ảnh bất kỳ, là tập cụm ở thời điểm hiện hành và
lần lượt là tâm của các cụm. Khi đó, ta luôn tìm được là tâm của cụm sao cho
min .
Áp dụng quy tắc phân bố đồ thị đặc trưng của ảnh ở Định nghĩa 8, ta có luôn thỏa mãn 1 trong 3
trường hợp trong quy tắc phân bố. Vì vậy, cho một đồ thị đặc trưng của ảnh bất kỳ, luôn đảm bảm đồ thị đó được phần
bố vào một cụm
Định lý 2. Mỗi đồ thị đặc trưng của ảnh chỉ được phân bố vào một cụm duy nhất trong tập
Chứng minh:
Gọi là một hình ảnh bất kỳ, giả sử là 2 cụm sao cho: và ( I ) (I ). Gọi lần lượt là 2
tâm cụm , ta có và ( ) . Do đó, ( ) .
Hơn nữa, theo Mệnh đề 3 thì là một metric nên ta có:
( ) ( ).
Mặc khác lần lượt là hai tâm cụm nên ( ) .
Suy ra: ( ) ( ) và ( ) . Vì vậy điều giả sử là vô lý.
Tức là mỗi vùng ảnh bất kỳ của ảnh chỉ được phân bổ vào một cụm duy nhất
Định nghĩa 9. Cho là tập các cụm rời nhau. Đồ thị cụm là đồ thị vô hướng có trọng số
, trong đó tập đỉnh , tập cạnh được định nghĩa như sau:
2. Thuật toán tạo đồ thị cụm
Trên cơ sở độ đo tương tự ở công thức (4) và quy tắc phân bố đồ thị đặc trưng của ảnh ở Định nghĩa 8. Chúng
tôi đề xuất thuật toán tạo đồ thị cụm các đồ thị đặc trưng của tập dữ liệu ảnh như sau:
Thuật toán CCG
Đầu vào: Tập đồ thị đặc trưng của tập dữ liệu ảnh ( ) và ngưỡng .
Đầu ra: Đồ thị cụm .
Function CCG(
Begin
E ;
For do
If ) then
; Khởi tạo cụm (đỉnh) ; ;
Else
Tìm tâm sao cho min ( ( ) )
If ) then
;
Else
If then
- Nguyễn Văn Thịnh, Nguyễn Thị Định, Văn Thế Thành 481
;
Else
[ ]; Khởi tạo cụm (đỉnh) ;
{( )| ( ) j i}
End If
End If
End If
Enf For
Return ;
End.
Mệnh đề 4. Độ phức tạp của Thuật toán CCG là , với là số đồ thị đặc trưng của tập dữ liệu ảnh.
Chứng minh:
Cho là số đồ thị đặc trưng của tập dữ liệu ảnh . Với mỗi ảnh, Thuật toán CCG thực hiện phép so sánh để
tìm tâm cụm gần nhất, với là số cụm ở thời điểm hiện hành. Do đó, số phép toán của Thuật toán CCG là ∑
∑ , với , là hằng số. Vì không đáng kể so với , do đó độ phức tạp của thuật toán này là
.
IV. TÌM KIẾM ẢNH DỰA TRÊN ĐỒ THỊ CỤM
A. Thuật toán trích xuất véctơ từ và tập ảnh tương tự
Từ đồ thị cụm đã tạo ở trên, chúng tôi đề xuất thuật toán trích xuất véctơ từ và tập ảnh tương tự làm cơ
sở cho việc trích xuất ngữ nghĩa hình ảnh. Với mỗi ảnh truy vấn, thuật toán thực hiện tìm kiếm tập ảnh tương tự và
trích xuất véctơ từ dựa trên tập ảnh tương tự này. Quá trình trích xuất véctơ từ và tập ảnh tương tự cần tìm ra cụm trong
đồ thị có độ tương tự gần với ảnh truy vấn nhất. Bên cạnh đó, cần tìm kiếm các hình ảnh tương tự tại các đỉnh
kề có khoảng cách nhỏ hơn ngưỡng cho trước. Sau đó trích xuất véctơ từ gồm các từ có tần suất xuất hiện lớn hơn
ngưỡng cho trước.
Thuật toán EVWV
Đầu vào: Đồ thị đặc trưng của ảnh truy vấn , đồ thị cụm giá trị ngưỡng và .
Đầu ra: Véctơ từ thị giác và tập ảnh tương tự .
Function EVWV(
Begin
;
Bước 1. Tìm cụm gần nhất
( ) min{ ( ) } , với là cụ có tâm là ;
Bước 2. Tìm cụm láng giềng
For do
If ( ) ) then End If
End For
Bước 3. Tìm tập ảnh tương tự
For do
End For
Bước 4. Tìm véctơ từ thị giác
For do
End For
For do
If freq then End If
End For
Return ;
End.
Mệnh đề 5. Độ phức tạp của Thuật toán EVWV là , với n là số từ trong véctơ từ của tập ảnh tương tự.
Chứng minh:
Gọi m là số đỉnh của đồ thị , là số từ trong véctơ từ của tập ảnh tương tự. Với mỗi ảnh cần tra cứu,
thuật toán duyệt tất cả các đỉnh của đồ thị để tìm ra cụm phù hợp và trích xuất tập ảnh tương tự. Sau đó, dựa
trên tập ảnh này, thuật toán trích xuất véctơ từ gồm các từ có tần suất xuất hiện theo ngưỡng . Do đó, số phép so sánh
- 482 TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN ĐỒ THỊ CỤM
của thuật toán là , với là hằng số. Vì lớn hơn , vì vậy độ phức tạp của Thuật toán EVWV là
B. Câu truy vấn SPARQL
Dựa trên véctơ từ đã được trích xuất bằng Thuật toán EVWV ở trên, câu truy vấn SPARQL được tạo ra để
thực hiện truy vấn trên ontology nhằm tìm ra tập ảnh tương tự và ngữ nghĩa hình ảnh.
C. Xây dựng ontology cho tập dữ liệu ảnh
Để thực thi câu truy vấn SPARQL, chúng tôi tạo một ontology miền mô tả ngữ nghĩa của tập dữ liệu ảnh. Trong
bài báo này, ontology miền được xây dựng sử dụng ngôn ngữ bộ ba RDF dạng Turtle dựa trên ngữ nghĩa trong tập dữ
liệu ảnh ImageCLEF, mỗi phân vùng của ảnh được thiết kế là một cá thể thuộc về một lớp đối tượng và được liên kết
đến ngữ nghĩa mô tả tương ứng. Hình 3 mô tả mô hình Ontology trực quan trong Protege.
Ontology của tập dữ liệu ImageCLEF trên Protege
V. THỰC NGHIỆM
A. Mô hình thực nghiệm
Mô hình hệ thống tìm kiếm ảnh theo ngữ nghĩa dựa trên ontology và đồ thị cụm
Mô hình thực nghiệm của hệ thống tìm kiếm ảnh theo nghữ nghĩa dựa trên đồ thị cụm được mô tả tại Hình 4.
Mô hình tìm kiếm ảnh gồm hai pha: tiền xử lý và tìm kiếm ảnh tương tự.
Pha tiền xử lý
Bước 1: tạo tập đồ thị từ tập véctơ đặc trưng thị giác của từng phân vùng của mỗi hình ảnh, mỗi đồ thị biểu diễn
một hình ảnh trong tập dữ liệu ảnh;
Bước 2: đánh giá độ tương tự giữa các đồ dựa trên độ đo tương tự đề xuất và tạo đồ thị cụm;
Bước 3: tạo ontology mô tả ngữ nghĩa cho tập dữ liệu ảnh.
- Nguyễn Văn Thịnh, Nguyễn Thị Định, Văn Thế Thành 483
Pha tìm kiếm ảnh tưởng tự
Bước 1: tạo đồ thị mô tả đặc trưng thị giác từ ảnh truy vấn và trích xuất véctơ từ thị giác theo tập ảnh tương tự
dựa trên đồ thị cụm;
Bước 2: tạo câu truy vấn SPARQL và thực hiện truy vấn trên Ontology để tìm ra tập URI và metadata của các
hình ảnh;
Bước 3: kết xuất các hình ảnh từ tập URI đã có và sắp xếp theo độ đo tương tự với ảnh truy vấn.
B. Kết quả thực nghiệm
Thực nghiệm được thực thi trên máy PC CPU Intel Core i5-7200U CPU @ 2.50GHz, 8.0GB RAM, hệ điều
hành Windows 10 Pro 64 bit. Pha tiền xử lý sử dụng ngôn ngữ lập trình Python phiên bản 3.6 và các gói thư viện
numpy, scipy.io, owlready2. Pha tìm kiếm ảnh sử dụng ngôn ngữ lập trình C# và .NET Framework 4.5. Các biểu đồ
được tạo ra bằng ngôn ngữ Matlab. Kết quả thực nghiệm được đánh giá trên bộ dữ liệu imageCLEF chứa 20,000 ảnh,
được chia thành 276 lớp và lưu trữ trong 41 thư mục (từ thư mục 0 đến thư mục 40); bộ dữ liệu của kích thước 1.64
GB. Để đánh giá hiệu quả của phương pháp, phần thực nghiệm được đánh giá các giá trị gồm: độ chính xác (precision),
độ phủ (recall) và độ đo dung hòa F-measure. Công thức tính các giá trị này như sau [2]:
Trong đó, relavant images là tập ảnh tương tự với ảnh truy vấn có trong tập dữ liệu ảnh, retrieved images là tập ảnh đã
tìm kiếm được. Các giá trị độ chính xác, độ phủ và độ do dung hòa được tính theo tỷ lệ và được quy đổi thành giá trị
trên đoạn [ ].
Precision-Recall và đường cong ROC của hệ thống trên tập dữ liệu ImageCLEF
Trung bình độ chính xác, độ phủ và độ dung hòa của hệ thống trên tập dữ liệu ImageCLEF
Trong thực nghiệm của bài báo này, chúng tôi chọn 7500 ảnh trong tập 20000 ảnh của tập dữ liệu ImageCLEF
- 484 TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN ĐỒ THỊ CỤM
để kiểm thử. Kết quả thực nghiệm của phương pháp chúng tôi đề xuất được mô tả tại Hình 5, Hình 6; hiệu suất của
phương pháp được trình bày trong Bảng 1; giá trị MAP của phương pháp đề xuất được so sánh với các phương pháp
khác trên cùng bộ dữ liệu ImageCLEF được mô tả trong Bảng 2. Hình 5 mô tả các đường cong Precision-Recall và
ROC, mỗi đường cong mô tả một bộ dữ liệu được truy vấn. Hình 6 mô tả giá trị Precision, Recall, F-measure trung
bình của 39 bộ ảnh trong tập dữ liệu ImageCLEF. Kết quả trong Bảng 2 cho thấy phương pháp đề xuất của chúng tôi
tương đối chính xác so với các hệ truy vấn ảnh theo ngữ nghĩa.
Bảng 1. Hiệu suất tìm kiếm ảnh của phương pháp được đề xuất trên bộ dữ liệu ImageCLEF
Tập Độ chính xác Độ phủ Độ đo dung hòa
Số ảnh Số cụm
ảnh trung bình trung bình trung bình
00-10 2500 6 0.694152 0.338917 0.455458
11-20 1551 7 0.646883 0.402911 0.496578
21-30 1235 8 0.644240 0.400223 0.493727
31-40 2217 6 0.729549 0.569591 0.639723
Bảng 2. So sánh độ chính xác giữa các phương pháp trên bộ dữ liệu ImageCLEF
Phƣơng pháp Mean Average Precision (MAP)
C.A. Hernández-Gracidas, 2013 [13] 0.5826
Hakan Cevikalp, 2017 [12] 0.4678
Vijayarajan, 2016 [25] 0.4618
Van T.T, 2017 [23] 0.7945
Phƣơng pháp đề xuất của chúng tôi 0.6787
Ứng dụng thực nghiệm của phương pháp đề xuất
Kết quả tìm kiếm ảnh của phương pháp đề xuất
VI. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
Bài báo đã xây dựng được phương pháp tìm kiếm ảnh theo ngữ nghĩa dựa trên đồ thị cụm bao gồm đồ thị đặc
trưng thị giác của hình ảnh. Trong bài báo này, chúng tôi đã đề xuất độ đo tương tự giữa hai hình ảnh và xây dựng cấu
trúc đồ thị cụm. Trên cơ sở lý thuyết đã được đề xuất, chúng tôi xây dựng hệ truy vấn ảnh theo ngữ nghĩa dựa trên nội
dung của hình ảnh. Kết quả thực nghiệm trên bộ dữ liệu ảnh ImageCLEF được đánh giá và so sánh với các công trình
khác trên cùng một tập dữ liệu ảnh đã cho thấy phương pháp đề xuất là hiệu quả. Vì vậy, phương pháp đề xuất của
chúng tôi có thể được sử dụng cho các hệ thống tra cứu dữ liệu đa phương tiện. Việc xây dựng đồ thị cụm dựa trên đồ
- Nguyễn Văn Thịnh, Nguyễn Thị Định, Văn Thế Thành 485
thị đặc trưng thị giác của hình ảnh đã tạo ra một cấu trúc tìm kiếm ảnh nhanh chóng. Từ đó, kết quả của quá trình tìm
kiếm ảnh có thể phân tích được ngữ nghĩa và tạo câu truy vấn SPARQL làm cơ sở thực hiện trích xuất mô tả ngữ nghĩa
trên ontology. Hướng phát triển tiếp theo của bài báo là phát triển phương pháp cụm dựa trên các kỹ thuật phân lớp
hình ảnh, nghĩa là có thể tạo ra một mô hình phân lớp để phân bố các hình ảnh thuộc về các cụm cho trước, đồng thời
xây dựng cấu trúc mở rộng các cụm dựa trên phương pháp phân lớp.
VII. LỜI CẢM ƠN
Nhóm tác giả chân thành cảm ơn Trường Đại học Công nghiệp Thực phẩm TP.HCM là nơi bảo trợ cho nghiên cứu
này. Chúng tôi trân trọng cám ơn nhóm nghiên cứu SBIR-HCM và Trường Đại học Sư phạm TP.HCM đã hỗ trợ về
chuyên môn và cơ sở vật chất giúp chúng tôi hoàn thành bài nghiên cứu này.
TÀI LIỆU THAM KHẢO
1. S. R. W. A. Hlaoui. "A graph clustering algorithm with applications to content-based image retrieval". in
Proceedings of the 2003 International Conference on Machine Learning and Cybernetics. 2003. Xi'an, China:
IEEE.
2. A. A. Ahmad Alzu’bi, Naeem Ramzan, "Semantic content-based image retrieval: A comprehensive study", Journal
of Visual Communication and Image Representation, vol. 32, no., pp. 20-54, 2015.
3. X. Y. B. B. Z. Yao, L. Lin, M.W. Lee, S. C. Zhu. "I2T: Image Parsing to Text Description". in Proceedings of the
IEEE. 2010. IEEE.
4. B. S. Banerjee M., Pal S. K., "A Clustering Approach to Image Retrieval Using Range Based Query and
Mahalanobis Distance". in In: Skowron A., Suraj Z. (eds) Rough Sets and Intelligent Systems - Professor Zdzisław
Pawlak in Memoriam. 2013. Springer, Berlin, Heidelberg.
5. J. B. Bin Xu, Chun Chen, Can Wang, Deng Cai, Xiaofei He, "EMR: A Scalable Graph-Based Ranking Model for
Content-Based Image Retrieval", IEEE Transactions on Knowledge and Data Engineering, vol. 7, no. 1, pp. 102-
114, 2015.
6. P. Carbonetto. Available from: http://www.cs.ubc.ca/~pcarbo/.
7. C. C. C. Chuen-Horng Lin, Hsin-Lun Lee, Jan-Ray Liao, "Fast K-means algorithm based on a level histogram for
image retrieval", Expert System with Application, vol. 41, no. 7, pp. 3276-3283, 2014.
8. Deloitte. 2018; Available from: https://www2.deloitte.com.
9. Deloitte, " Photo sharing: trillions and rising", Deloitte Touche Tohmatsu Limited, Deloitte Global, Tech. Rep.,
vol., no., 2016.
10. J. Y. Guang-HaiLiu, "Content-based image retrieval using color difference histogram", Pattern Recognition, vol.
46, no. 1, pp. 188-198, 2013.
11. M. M. H. R. Saboorian, Jamzad, M. Rabiee. "User adaptive clustering for large image databases". in 20th IEEE
International Conference on Pattern Recognition. 2010. Istanbul, Turkey: IEEE.
12. M. E. Hakan Cevikalp, Savas Ozkan, "Large-scale image retrieval using transductive support vector machines",
Computer Vision and Image Understanding, vol. 173, no., pp. 2-12, 2018.
13. C. A. Hernández-Gracidas, Sucar, L. E. & Montes-y-Gómez, "Improving image retrieval by using spatial
relations", Multimed Tools Application, vol. 62, no. 2, pp. 479-505, 2013.
14. C. A. H. Hugo Jair Escalante, Jesus A. Gonzalez, A. López- López, Manuel Montes, Eduardo F. Morales, L.
Enrique Sucar, Luis Villasenor, Michael Grubinger "The segmented and annotated IAPR TC-12 benchmark",
Computer Vision and Image Understanding, vol. 114, no. 4, pp. 419-428, 2010.
15. S. H. J. Hun-Woo Yoo, Dong-Sik Jang, Yoon-Kyoon Na, "Extraction of major object features using VQ clustering
for content-based image retrieval", Pattern Recognition, vol. 35, no. 5, pp. 1115-1126, 2002.
16. S. Jabeen, et al., "An effective content-based image retrieval technique for image visuals representation based on
the bag-of-visual-wordsmodel", PLoS ONE, vol. 13, no. 4, pp. 1-24, 2018.
17. P. S. Kim S., Kim M. "Central Object Extraction for Object-Based Image Retrieval". in International Conference
on Image and Video Retrieval. 2003. Berlin, Heidelberg: Springer, Berlin, Heidelberg.
18. S. M. N. Zakariya, Ali, R., Ahmad. "Combining visual features of an image at different precision value of
unsupervised content based image retrieval". in 2010 IEEE International Conference on Computational
Intelligence and Computing Research. 2011. Coimbatore, India: IEEE.
19. Y. D. Nan Zhao, Hongliang Bai, Lezi Wang, Chong Huang, Shusheng Cen, Jian Zhao. "A semantic graph-based
algorithm for image search reranking". in 2013 IEEE International Conference on Acoustics, Speech and Signal
Processing. 2013. IEEE.
- 486 TÌM KIẾM ẢNH THEO NGỮ NGHĨA DỰA TRÊN ĐỒ THỊ CỤM
20. Z. M. S. Jabeen, T. Mahmood, T. Saba, A. Rehman, M. T. Mahmood, "An effective content-based image retrieval
technique for image visuals representation based on the bag-of-visual-wordsmodel", PLoS ONE, vol. 13, no. 4,
pp. 1-24, 2018.
21. N. V. T. Thanh The Van, Thanh Manh Le, "The Method Proposal of Image Retrieval Based on K-Means
Algorithm", Advances in Intelligent Systems and Computing, vol. 746, no. 2, pp. 481-490, 2018.
22. T.M.L. Thanh The Van, "Content-Based Image Retrieval using A Signature Graph and A Self-Organizing Map",
International Journal of Applied Mathematics and Computer Science (AMCS), vol. 26, no. 2, pp. 423-438, 2016.
23. T. M. L. Thanh The Van, "Content-based image retrieval based on binary signatures cluster graph", Journal of
Knowledge Engineering, Expert System, vol. 35, no. 1, pp. 1-22, 2017.
24. T. M. L. Thanh The Van, "Image Retrieval Based on Binary Signature ang S-kGraph", Annales Univ. Sci.
Budapest, vol. 43, no., pp. 105-122, 2014.
25. M. D. V. Vijayarajan, P. Tejaswin, M. Lohani, "A generic framework for ontology‑ based information retrieval
and image retrieval in web data", Human-centric Computing and Information Sciences, vol. 6, no. 18, pp. 1-30,
2016.
26. X. C. Xiao Xie, Junpei Zhou, Nan Cao, Yingcai Wu, "A Semantic-based Method for Visualizing Large Image
Collections", IEEE Transactions on Visualization and Computer Graphics, vol., no., 2018.
27. G. L. Yan Yan, Sen Wang, Jian Zhang, Kai Zheng, "Graph-based clustering and ranking for diversified image
search", Multimedia Systems, vol. 23, no. 1, pp. 41-52, 2017.
28. B. B. Z. Yao, et al. "I2T: Image Parsing to Text Description". in Proceedings of the IEEE. 2010. IEEE.
SEMANTIC-BASED IMAGE RETRIEVAL BASED ON CLUSTER GRAPH
Nguyen Van Thinh, Nguyen Thi Dinh, Van The Thanh
ABSTRACT: The Semantic-Based Image Image (SBIR) problem is of interest in recent years because this approach can extract
image semantics and overcome the disadvantages of Text-Based Image Retrieval (TBIR) and Content-Based Image Retrieval (CBIR)
methods. Therefore, in this paper, we propose methods retrieval and extracting images semantics with a visual feature graph of
images and a cluster graph. To accomplish this problem, the visual feature graph clustering method is proposed to create the cluster
graph from which to extract image semantics. First of all, we propose a structure of image description graphs and similarity
measure based on low-level features along with spatial relationships among regions in the image. Then, cluster graphs were created
using a method of clustering the visual feature graphs of the images on the basis of the proposed similarity measure; At the same
time, we build the ontology that describes the semantics for the image dataset and create the SPARQL query rely on the visual word
vector to perform image retrieval on the ontology. Based on the built cluster graph and ontology, we propose an image retrieval and
semantic extraction algorithm. In order to illustrate the proposed theory, experiments were built and evaluated on ImageCLEF
dataset; Experimental results are evaluated compared to other recently published methods on the same dataset. From the
experimental results show that our proposed method is effective and can be applied in many multimedia data systems.
Keywords: SBIR, image retrieval, clustering, ontology, SPARQL.
nguon tai.lieu . vn
