Image Retrieval System Based on EMD Similarity Measure and S-Tree
This chapter approaches the binary signature for each image on the base of the percentage of the pixels in each color image and builds a similar measure between the images based on EMD (earth mover’s distance). Next, it aims to create S-tree in a similar
- PDF / 468,976 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 58 Downloads / 178 Views
Abstract This chapter approaches the binary signature for each image on the base of the percentage of the pixels in each color image and builds a similar measure between the images based on EMD (earth mover’s distance). Next, it aims to create S-tree in a similar measure EMD to store the image’s binary signatures to quickly query image signature data. Then, from a similar measure EMD and S-tree, it provides an image retrieval algorithm and CBIR (content-based image retrieval). Last but not least, based on this theory, it also presents an application and experimental assessment of the process of querying image on the database system over 10,000 images. Keywords CBIR • Image retrieval • EMD • S-tree • Signature • Signature tree
1 Introduction It is difficult to find images in a large database of digital images. There are two main approaches for querying the images: querying the images based on the keyword TBIR (text-based image retrieval) [1] and those based on the content CBIR (content-based image retrieval) [1, 2]. In recent years, there have been considerable researches regarding CBIR, such as the image retrieval system based on color histogram [1–4], the similarity of the
T.M. Le Hue University, Hue, Vietnam T.T. Van (*) Center for Information Technology, HoChiMinh City University of Food Industry, HoChiMinh City, Vietnam e-mail: [email protected] J. Juang and Y.-C. Huang (eds.), Intelligent Technologies and Engineering Systems, Lecture Notes in Electrical Engineering 234, DOI 10.1007/978-1-4614-6747-2_17, # Springer Science+Business Media New York 2013
139
140
T.M. Le and T.T. Van
images based on histogram and the texture [5], and using the EMD distance in image retrieval [6–8]. This chapter aims to create the binary signature of an image and describe the distribution of image’s colors by a bitstring with a given size. It also aims to query “similar images” in a large image database system efficiently. Additionally, two major targets are used to reduce the amount of storage space and speed up the query image on large database systems.
2 The Related Theory 2.1
S-Tree
S-tree [2, 9] is a tree with many branches that are balanced; each node of the S-tree contains a number of pairs hsig; nexti, where sig is a binary signature and next is a pointer to a child node. Each node root of the S-tree contains at least two pairs and at most M pairs hsig; nexti, all internal nodes in the S-tree at least m and at most M pairs hsig; nexti, 1 m M=2; the leaves of the S-tree contain the image’s binary signatures sig, along with a unique identifier oid for those images. The S-tree height for n signatures is at most h ¼ dlogm n 1e. The S-tree was built on the basis of inserting and splitting. When the node v is full, it will be split into two.
2.2
EMD Distance
Setting I as a set of suppliers, J as a set of consumers, and cij as the transportation cost from the supplier i 2 I toPthe P fij to P consumer j 2 J , we need to find out flows minimize the total cost cij fij with the constraints [10] fij 0; fij yj ;
Data Loading...
