Abstract
Similarity search and content-based retrieval have become widely used in multimedia database systems that often manage huge data collections. Unfortunately, many effective content-based similarity models cannot be fully utilized for larger datasets, as they are computationally demanding and require massive parallel processing for both feature extraction and query evaluation tasks. In this work, we address the performance issues of effective similarity models based on feature signatures, where we focus on fast feature extraction from image thumbnails using affordable hardware. More specifically, we propose a multi-GPU implementation that increases the extraction speed by two orders of magnitude with respect to a single-threaded CPU implementation. Since the extraction algorithm is not directly parallelizable, we propose a modification of the algorithm embracing the SIMT execution model. We have experimentally verified that our GPU extractor can be successfully used to index large image datasets comprising millions of images. In order to obtain optimal extraction parameters, we employed the GPU extractor in an extensive empirical investigation of the parameter space. The experimental results are discussed from the perspectives of both performance and similarity precision.
Similar content being viewed by others
Notes
The superpixel representation [1] is popular in the computer vision domain to decrease time complexity of image processing algorithms.
Note that SIFT descriptors could be used to form a feature signature, as feature signature stands for a general ”container” for any set of local features (or their representatives). See the definition of feature signature later in Section 4.
The lockstep execution is also called Single Instruction Multiple Threads (SIMT) model.
Which is also equal to 4(r i g h t−l e f t)(b o t t o m−t o p).
Value 0 to items being filtered and value 1 to items being kept.
We have used traditional statistical notation EX and Var(X) to emphasize that we are denoting a mean value and a standard variance respectively.
References
Achanta R, Shaji A, Smith K, Lucchi A, Fua P, Süsstrunk S (2012) Slic superpixels compared to state-of-the-art superpixel methods. IEEE Trans Pattern Anal Mach Intell 34(11):2274–2282
Bay H, Ess A, Tuytelaars T, Gool LJV (2008) Speeded-up robust features (SURF). Comp Vision Image Underst (CVIU) 110(3):346–359
Beecks C, Kirchhoff S, Seidl T (2013) Signature matching distance for content-based image retrieval. In: Proceedings of ACM International Conference on Multimedia Retrieval (ICMR 2013). ACM, Dallas, pp 41–48
Beecks C, Uysal M, Seidl T (2010) Signature quadratic form distance. In: Proceedings of the ACM international conference on image and video retrieval. ACM, pp 438–445
Canny J (1986) A computational approach to edge detection. IEEE Trans Pattern Anal Mach Intell 6:679–698
Chávez E, Navarro G, Baeza-Yates R, Marroquín JL (2001) Searching in metric spaces. ACM Comput Surv 33(3):273–321
Colantoni P, Boukala N, Da Rugna J (2003) Fast and accurate color image processing using 3d graphics cards. In: 8th International fall workshop-vision modeling and visualization 2003, Proceedings November 19–21, 2003, München, pp 383–390
Datta R, Joshi D, Li J, Wang JZ (2008) Image retrieval: Ideas, influences, and trends of the new age. ACM Comput Surv (CSUR) 40(2):5
Dehne F, Noltemeier H (1987) Voronoi trees and clustering problems. Information Systems 12(2):171–175
Farivar R, Rebolledo D, Chan E, Campbell R (2008) A parallel implementation of k-means clustering on GPUs. In: Proceedings of international conference on parallel and distributed processing techniques and applications (PDPTA), pp 340–345
Fung J (2005) Computer vision on the GPU. GPU Gems 2:649–666
Gotlieb CC, Kreyszig HE (1990) Texture descriptors based on co-occurrence matrices. Comput Vis Graph Image Proc 51(1):70–86
Hartigan JA, Wong MA (1979) Algorithm AS 136: a k-means clustering algorithm. Appl Stat :100–108
Heymann S, Muller K, Smolic A, Frohlich B, Wiegand T (2007) SIFT implementation and optimization for general-purpose GPU. In: Proceedings of the International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, p 144
Hong-Tao B, Li-li H, Dan-tong O, Zhan-shan L, He L (2009) K-means on commodity GPUs with CUDA. In: WRI world congress on computer science and information engineering, 2009, vol 3. IEEE, pp 651–655
Huttenlocher DP, Klanderman GA, Kl GA, Rucklidge WJ (1993) Comparing images using the Hausdorff distance. IEEE Trans Pattern Anal Mach Intell 15:850–863
Khronos OpenCL – The open standard for parallel programming of heterogeneous systems., http://www.khronos.org/opencl/
Kozak S (2013) Efficiency and security in similarity cloud services. PVLDB 6 (12):1450–1455
Krulis M, Falt Z, Bednarek D, Yaghob J (2012) Task scheduling in hybrid CPU-GPU Systems. In: ITAT, pp 17–24
Krulis M, Lokoc J, Skopal T (2013) Efficient extraction of feature signatures using multi-GPU architecture. In: Advances in multimedia modeling, 19th international conference, MMM, pp 446–456
Krulis M, Skopal T, Lokoc J, Beecks C (2012) Combining CPU and GPU architectures for fast similarity search. Distributed and Parallel Databases 30 (3–4):179–207
Li P, Wang M, Cheng J, Xu C, Lu H (2013) Spectral hashing with semantically consistent graph for image indexing. IEEE Trans Multimed 15(1):141–152
Li X, Fang Z (1989) Parallel clustering algorithms. Parallel Comput 11 (3):275–290
Lokoč J, Blažek A, Skopal T (2014) Signature-based video browser. In: Gurrin C, Hopfgartner F, Hurst W, Johansen H, Lee H, OConnor N (eds) MultiMedia modeling, volume 8326 of Lecture Notes in Computer Science. Springer International Publishing, pp 415–418
Lokoč J, Grošup T, Skopal T (2012) Image exploration using online feature extraction and reranking. In: Proceedings of the 2nd ACM international conference on multimedia retrieval, vol 66. ACM
Lokoč J, Novák D, Batko M, Skopal T (2012) Visual image search: feature signatures or/and global descriptors. In: Proceedings of the 5th international conference on similarity search and applications, SISAP’12. Springer, Berlin, pp 177–191
Lowe DG (2004) Distinctive image features from scale-invariant keypoints. Int J Comput Vis 60(2):91–110
Luo Y, Duraiswami R (2008) Canny edge detection on NVIDIA CUDA. In: Computer vision and pattern recognition workshops, 2008. IEEE Computer Society Conference on CVPRW’08. IEEE, pp 1–8
McLaren K (1976) XIII The Development of the CIE 1976 (L ∗ a ∗ b ∗) Uniform Colour Space and Colour-difference Formula. J Soc Dye Colour 92(9):338–341
MPEG-7. (2002) Multimedia content description interfaces. Part 3: visual. ISO/IEC 15938-3:2002
NVIDIA Fermi GPU Architecture http://www.nvidia.com/object/fermi-architecture.html
NVIDIA Kepler GPU Architecture http://www.nvidia.com/object/nvidia-kepler.html.
Ogawa K, Ito Y, Nakano K (2010) Efficient canny edge detection using a gpu. In: 2010 First International Conference on Networking and Computing (ICNC). IEEE, pp 279–280
Park B, Lee K, Lee S (2006) A new similarity measure for random signatures: perceptually modified hausdorff distance. In: Blanc-Talon J, Philips W, Popescu D, Scheunders P (eds) Advanced concepts for intelligent vision systems, volume 4179 of Lecture Notes in Computer Science. Springer, Berlin, pp 990–1001
Parker JR (2010) Algorithms for image processing and computer vision. Wiley Publishing
Pelleg D, Moore A (1999) Accelerating exact k-means algorithms with geometric reasoning. In: Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 277–281
Profimedia Image database. http://www.profimedia.cz/
Roodt Y, Visser W, Clarke W (2007) Image processing on the GPU: implementing the canny edge detection algorithm. In: Symposium Pattern Recognition Association of South Africa
Rubner Y, Tomasi C (2001) Perceptual metrics for image database navigation. Kluwer Academic Publishers, Norwell
Shalom S, Dash M, Tue M (2008) Efficient k-means clustering using accelerated graphics processors. Data Warehousing and Knowledge Discovery :166–175
Tkalcic M, Tasic JF (2003) Colour spaces: perceptual, historical and applicational background, vol 1. IEEE
van de Sande KEA, Gevers T, Snoek CGM (2011) Empowering visual categorization with the gpu. Trans Multi 13(1):60–70
Wang M, Ni B, Hua X-S, Chua T-S (2012) Assistive tagging: a survey of multimedia tagging with human-computer joint exploration. ACM Comput Surv 44 (4):25:1–25:24
Zechner M, Granitzer M (2009) Accelerating k-means on the graphics processor via CUDA. In: Intensive applications and services, 2009. First International Conference on INTENSIVE’09. IEEE, pp 7–15
Zezula P, Amato G, Dohnal V, Batko M (2006) Similarity search: the metric space approach, volume 32 of advances in database systems. Springer
Acknowledgments
This research has been supported by Czech Science Foundation (GAČR) projects P103/14/14292P, P202/12/P297, and P202/11/0968.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is an extended version of a previous paper by Kruliš et al. [20], which was presented as a work in progress report. We have completed our solution and present the final version in full detail. Furthermore, we have included detailed description of feature extraction process and extensive experimental data, which could help with the selection of optimal parameter configuration for the extractor. The main objective of this paper is to provide full experience and guidelines for anyone, who would adopt this approach on an application level.
Rights and permissions
About this article
Cite this article
Kruliš, M., Lokoč, J. & Skopal, T. Efficient extraction of clustering-based feature signatures using GPU architectures. Multimed Tools Appl 75, 8071–8103 (2016). https://doi.org/10.1007/s11042-015-2726-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11042-015-2726-y