Indexing Multimedia Data with an Extension of Binary Tree -- Image Search by Content --

Year 2018, Volume: 1 Issue: 1, 47 - 55, 20.12.2018

Kouahla Zineddine , Ferrag Mohamed Amine Anjum Adeel

Abstract

Searching for similar images in a data collection, based on a query image, is a fundamental problem for many applications that use large amounts of complex data. Image research by content and on a large scale is a current challenge for large image database research and management. Various information can be extracted such as colour, shape and texture, etc. A characteristic represents only a part of the image property, which makes it necessary to combine all this information to improve the efficiency of these systems. This paper aims to propose a new indexing structure that allows to organize as much information as possible about the images in a binary tree in order to improve the search time, and to propose an algorithm for index construction and a search algorithm for kNN type queries. The concept of containers at the sheet level was used to improve the complexity of algorithms. Experiments on real data sets were conducted to determine its performance.

Keywords

Metric Space, Tree, Large Scale, Image, Intrinsic Dimension

References

• Baldonado, M., Chang, C.C.K., Gravano, L., Paepcke, A.: The stanford digital library metadata architecture. International Journal on Digital Libraries 1(2), 108–121 (1997)
• Berchtold, S., Böhm, C., Kriegal, H.P.: The pyramid-technique: towards Breaking the curse of dimensionality. In: ACM SIGMOD Record. vol. 27, pp. 142–153. ACM (1998)
• Böhm, C., Berchtold, S., Keim, D.A.: Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Computing Surveys (CSUR) 33(3), 322–373 (2001)
• Bruce, K.B., Cardelli, L., Pierce, B.C.: Comparing object encodings. In: International Symposium on Theoretical Aspects of Computer Software. pp. 41–438. Springer (1997)
• Ciaccia, P., Patella, M.: Bulk loading the m-tree. In: Proceedings of the 9th Australasian Database Conference (ADC’98). pp. 15–26. Citeseer (1998)
• Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., et al.: The qbic system. IEEE computer28(9), 23–32 (1995)
• Frankel, C., Swain, M.J., Athitsos, V.: Webseer: An image search engine for the world wide web (1996)
• Guttman, A.: R-trees: a dynamic index structure for spatial searching, vol. 14. ACM (1984)
• Hoseinitabatabaei, S.A., Fathy, Y., Barnaghi, P.M., Wang, C., Tafazolli, R.: A novel indexing method for scalable iot source lookup. IEEE Internet of ThingsJournal 5(3), 2037–2054 (2018). https://doi.org/10.1109/JIOT.2018.2821264, https://doi.org/10.1109/JIOT.2018.2821264
• Jabeen S, Mehmood Z, M.T.S.T.R.A.M.M.: An effective content-based image retrieval technique for image visuals representation based on the bag-of-visual-words model. PLoS ONE (13) (2018)
• Katayama, N., Satoh, S.: The sr-tree: An index structure for high-dimensional nearest neighbor queries. In: ACM Sigmod Record. vol. 26, pp. 369–380. ACM(1997)
• Niblack, C.W., Barber, R., Equitz, W., Flickner, M.D., Glasman, E.H., Petkovic, D., Yanker, P., Faloutsos, C., Taubin, G.: Qbic project: querying images by content, using color, texture, and shape. In: Storage and retrieval for image and video databases. vol. 1908, pp. 173–188. International Society for Optics and Photonics (1993)
• Ogle, V.E., Stonebraker, M.: Chabot: Retrieval from a relational database of images. Computer 28(9), 40–48 (1995)
• Ogle, V.E., Stonebraker, M.: Chabot: Retrieval from a relational database of images. Computer 28(9), 40–48 (1995)
• Pentland, A., Picard, R.W., Sclaroff, S.: Photobook: Content-based manipulation of image databases. International journal of computer vision 18(3), 23–254 (1996)
• Satyanarayanan, M., Gibbons, P.B., Mummert, L., Pillai, P., Simoens, P., Sukthankar, R.: Cloudlet-based just-in-time indexing of iot video. In:2017 Global Internet of Things Summit (GIoTS). pp. 1–8 (June 2017). https://doi.org/10.1109/GIOTS.2017.8016212
• Smith, J.R., Chang, S.F.: Visualseek: a fully automated content-based image query system. In: ACM multimedia. vol. 96, pp. 87–98. Citeseer (1996)
• Srihari, R.K.: Automatic indexing and content-based retrieval of captioned images. Computer 28(9), 49–56 (1995)
• Weber, R., Schek, H.J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: VLDB. vol. 98, pp.194–205 (1998)
• Yang, Y., Zheng, Z., Bian, K., Song, L., Han, Z.: Real-time profiling of finegrained air quality index distribution using UAV sensing. IEEE Internet ofThings Journal 5(1), 186–198 (2018). https://doi.org/10.1109/JIOT.2017.2777820, https://doi.org/10.1109/JIOT.2017.2777820