Skip to main content
SpringerLink
Log in

Efficient extraction of clustering-based feature signatures using GPU architectures

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Notes

  1. The superpixel representation [1] is popular in the computer vision domain to decrease time complexity of image processing algorithms.

  2. 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.

  3. E.g., NVIDIA SMP architectures hold 32 cores (Fermi [31]) or 192 cores (Kepler [32]).

  4. The lockstep execution is also called Single Instruction Multiple Threads (SIMT) model.

  5. Which is also equal to 4(r i g h t−l e f t)(b o t t o m−t o p).

  6. Value 0 to items being filtered and value 1 to items being kept.

  7. 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

  1. 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

    Article  Google Scholar 

  2. Bay H, Ess A, Tuytelaars T, Gool LJV (2008) Speeded-up robust features (SURF). Comp Vision Image Underst (CVIU) 110(3):346–359

    Article  Google Scholar 

  3. 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

    Google Scholar 

  4. 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

  5. Canny J (1986) A computational approach to edge detection. IEEE Trans Pattern Anal Mach Intell 6:679–698

    Article  Google Scholar 

  6. Chávez E, Navarro G, Baeza-Yates R, Marroquín JL (2001) Searching in metric spaces. ACM Comput Surv 33(3):273–321

    Article  Google Scholar 

  7. 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

  8. 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

    Article  Google Scholar 

  9. Dehne F, Noltemeier H (1987) Voronoi trees and clustering problems. Information Systems 12(2):171–175

    Article  Google Scholar 

  10. 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

  11. Fung J (2005) Computer vision on the GPU. GPU Gems 2:649–666

    Google Scholar 

  12. Gotlieb CC, Kreyszig HE (1990) Texture descriptors based on co-occurrence matrices. Comput Vis Graph Image Proc 51(1):70–86

    Article  Google Scholar 

  13. Hartigan JA, Wong MA (1979) Algorithm AS 136: a k-means clustering algorithm. Appl Stat :100–108

  14. 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

  15. 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

  16. Huttenlocher DP, Klanderman GA, Kl GA, Rucklidge WJ (1993) Comparing images using the Hausdorff distance. IEEE Trans Pattern Anal Mach Intell 15:850–863

    Article  Google Scholar 

  17. Khronos OpenCL – The open standard for parallel programming of heterogeneous systems., http://www.khronos.org/opencl/

  18. Kozak S (2013) Efficiency and security in similarity cloud services. PVLDB 6 (12):1450–1455

    Google Scholar 

  19. Krulis M, Falt Z, Bednarek D, Yaghob J (2012) Task scheduling in hybrid CPU-GPU Systems. In: ITAT, pp 17–24

  20. 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

  21. 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

    Article  Google Scholar 

  22. 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

    Article  Google Scholar 

  23. Li X, Fang Z (1989) Parallel clustering algorithms. Parallel Comput 11 (3):275–290

    Article  MathSciNet  MATH  Google Scholar 

  24. 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

  25. 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

  26. 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

    Google Scholar 

  27. Lowe DG (2004) Distinctive image features from scale-invariant keypoints. Int J Comput Vis 60(2):91–110

    Article  Google Scholar 

  28. 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

  29. 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

    Article  Google Scholar 

  30. MPEG-7. (2002) Multimedia content description interfaces. Part 3: visual. ISO/IEC 15938-3:2002

    Google Scholar 

  31. NVIDIA Fermi GPU Architecture http://www.nvidia.com/object/fermi-architecture.html

  32. NVIDIA Kepler GPU Architecture http://www.nvidia.com/object/nvidia-kepler.html.

  33. 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

  34. 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

  35. Parker JR (2010) Algorithms for image processing and computer vision. Wiley Publishing

  36. 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

  37. Profimedia Image database. http://www.profimedia.cz/

  38. 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

  39. Rubner Y, Tomasi C (2001) Perceptual metrics for image database navigation. Kluwer Academic Publishers, Norwell

    Book  MATH  Google Scholar 

  40. Shalom S, Dash M, Tue M (2008) Efficient k-means clustering using accelerated graphics processors. Data Warehousing and Knowledge Discovery :166–175

  41. Tkalcic M, Tasic JF (2003) Colour spaces: perceptual, historical and applicational background, vol 1. IEEE

  42. van de Sande KEA, Gevers T, Snoek CGM (2011) Empowering visual categorization with the gpu. Trans Multi 13(1):60–70

    Article  Google Scholar 

  43. 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

    Article  Google Scholar 

  44. 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

  45. Zezula P, Amato G, Dohnal V, Batko M (2006) Similarity search: the metric space approach, volume 32 of advances in database systems. Springer

Download references

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

  1. SIRET Research group, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám. 25, 11800, Prague, Czech Republic

    Martin Kruliš, Jakub Lokoč & Tomáš Skopal

Authors
  1. Martin Kruliš
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jakub Lokoč
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tomáš Skopal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Kruliš.

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-015-2726-y

Keywords

Search

Navigation