Overlapping area hyperspheres for kernel-based similarity method | Pattern Analysis and Applications Skip to main content
Springer Nature Link
Log in

Overlapping area hyperspheres for kernel-based similarity method

  • Short Paper
  • Published:
Pattern Analysis and Applications Aims and scope Submit manuscript

Abstract

Measuring similarity between sets of objects is a key step in a wide areas of machine learning. Popular examples include general classification framework and numerous applications in computer vision. In this paper, we propose a kernel-based similarity method which is inspired from an interesting biological behavior of trees and induced mathematically by formulating it as a quadratic optimization problem in a reproducing kernel Hilbert space (RKHS). The proposed method is compared to the maximum mean discrepancy, a recent and challenging kernel similarity method. We conduct and present several numerical experiments on synthetic data as well as real-word image data. The proposed method yields favorable performances in terms of classification performances in the context of supervised classification tasks on the challenging Caltech101 dataset and other datasets such as USPS and ETH80. Furthermore, the efficiency of the proposed method in the context of image segmentation through unsupervised clustering of superpixels has been also asserted.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

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
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

References

  1. Ackermann N (2005) A cauchy-schwarz type inequality for bilinear integrals on positive measures. Proc Am Math Soc 133(9):2647–2656

    Article  MATH  MathSciNet  Google Scholar 

  2. Atallah MJ (1983) A linear time algorithm for the hausdorff distance between convex polygons. Inf Process Lett 17:207–209

    Article  MATH  MathSciNet  Google Scholar 

  3. Bartha P (2010) By parallel reasoning. Oxford University Press, Oxford

    Book  Google Scholar 

  4. Bdoiu M, Clarkson KL (2008) Optimal core-sets for balls. Comput Geom 40(1):14–22

    Article  MATH  MathSciNet  Google Scholar 

  5. Belongie S, Malik J, Puzicha J (2002) Shape matching and object recognition using shape contexts. IEEE Trans Pattern Anal Mach Intell 24:509–522

    Article  Google Scholar 

  6. Berg AC, Malik J (2001) Geometric blur for template matching. In: IEEE conference on computer vision and pattern recognition, pp 607–614

  7. Borgwardt KM, Gretton A, Rasch MJ, Kriegel H-P, Schölkopf B, Smola A (2007) A kernel method for the two sample problem. Adv Neural Inf Process Syst 19:513–520

    Google Scholar 

  8. Carli A, Castellani U, Bicego M, Murino V (2010) Dissimilarity-based representation for local parts. In: International workshop on cognitive information processing (CIP), pp 299–303

  9. Cevikalp H (2010) Semi-supervised distance metric learning by quadratic programming. In: International conference on pattern recognition, pp 3352–3355

  10. Chang C-C, Lin C-J (2011) LIBSVM: a library for support vector machines. ACM Trans Intell Syst Technol 2:1–27

    Article  Google Scholar 

  11. Chen P, Fan RE, Lin C (2005) Training support vector machines via smo-type decomposition methods. In: International conference on algorithmic learning theory

  12. Cheplygina V, Tax DMJ, Loog M (2015) On classification with bags, groups and sets. Pattern Recogn Lett 59(1):11–17

    Article  Google Scholar 

  13. Coen MH, Ansari M, Fillmore N (2011) Learning from spatial overlap. In: AAAI conference on artificial intelligence, 2011

  14. Comaniciu D, Meer P (2002) Mean shift: a robust approach toward feature space analysis. IEEE Trans Pattern Anal Mach Intell 24(5):603–619

    Article  Google Scholar 

  15. Crosland MP (1978) Gay-Lussac: scientist and bourgeois. Cambridge University Press, Cambridge

    Book  Google Scholar 

  16. Delos V, Teissandier D (2015) Minkowski sum of polytopes defined by their vertices. J Appl Math Phys 3(1):62–67

    Article  Google Scholar 

  17. Diu M, Gangeh M, Kamel MS (2013) Unsupervised visual changepoint detection using maximum mean discrepancy. In: Image analysis and recognition, 2013

  18. Diu M (2013) Image analysis applications of the maximum mean discrepancy distance measure, PhD thesis, University of Waterloo, 2013

  19. Doménech JL, Gil-Pérez D, Gras-Martí A, Guisasola J, Martínez-Torregrosa J, Salinas J, Trumper R, Valdés P, Vilches A (2007) Teaching of energy issues: a debate proposal for a global reorientation. Sci Educ 16(1):43–64

    Article  Google Scholar 

  20. Dueck D, Frey BJ (2007) Non-metric affinity propagation for unsupervised image categorization. In: International conference on computer vision, 2007, pp 1–8

  21. Farid H, Simoncelli EP (2004) Differentiation of discrete multidimensional signals. IEEE Trans Image Process 13(4):496–508

    Article  MathSciNet  Google Scholar 

  22. Galego R, Ferreira R, Bernardino A, Grossmann E, Gaspar J (2013) Topological auto-calibration of central imaging sensors. In: Pattern recognition and image analysis, 2013, pp 476–483

  23. Geng B, Tao D, Xu C (2011) Daml: Domain adaptation metric learning. IEEE Trans Image Process 20(10):2980–2989

    Article  MATH  MathSciNet  Google Scholar 

  24. Gönen M, Alpaydın E (2011) Multiple kernel learning algorithms. J Mach Learn Res 12:2211–2268

    MATH  MathSciNet  Google Scholar 

  25. Goodrich B, Albrecht D, Tischer P (2009) Algorithms for the computation of reduced Convex Hulls. In: Australasian joint conference on advances in artificial intelligence,

  26. Grauman K, Darrell T (2007) The pyramid match kernel: efficient learning with sets of features. J Mach Learn Res 8:725–760

    MATH  Google Scholar 

  27. Gretton A, Borgwardt KM, Rasch MJ, Schölkopf B, Smola A (2012) A kernel two-sample test. J Mach Learn Res 13:723–773

    MATH  MathSciNet  Google Scholar 

  28. Hafiz AM, Bhat GM (2014) Handwritten digit recognition using slope detail features. Int J Comput Appl 93(5):14–19

    Google Scholar 

  29. Hans A (2009) In resonance with nature: holistic healing for plants and land. Floris Books, Edinburgh

    Google Scholar 

  30. Hull JJ (1994) A database for handwritten text recognition research. IEEE Trans Pattern Anal Mach Intell 16(5):550–554

    Article  Google Scholar 

  31. Jacobs DW, Weinshall D, Gdalyahu Y (2000) Classification with nonmetric distances: image retrieval and class representation. IEEE Trans Pattern Anal Mach Intell 22(6):583–600

    Article  Google Scholar 

  32. Jones WP, Furnas GW (1987) Pictures of relevance: a geometric analysis of similarity measures. J Am Soc Inf Sci 38(6):420–442

    Article  Google Scholar 

  33. Kim B, Pineau J (2013) Maximum mean discrepancy imitation learning. Robot Sci Syst

  34. Kinnunen T, Li H (2010) An overview of text-independent speaker recognition: from features to supervectors. Speech Commun 52(1):12–40

    Article  Google Scholar 

  35. Klippel A, Weaver C (2008) Analyzing behavioral similarity measures in linguistic and non-linguistic conceptualization of spatial information and the question of individual differences. In: Workshop on information semantics and its implications for geographical analysis

  36. Kondor R, Jebara T (2003) A kernel between sets of vectors. In: International conference on machine learning

  37. Kumar P, Mitchell JSB, Yildirim EA (2003) Approximate minimum enclosing balls in high dimensions using core-sets. J Exp Alg 8:1

    MATH  MathSciNet  Google Scholar 

  38. Lazebnik S, Schmid C, Ponce J (2006) Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. In: IEEE conference on computer vision and pattern recognition

  39. Leibe, B, Schiele B (2003) Analyzing appearance and contour based methods for object categorization. In: IEEE conference on computer vision and pattern recognition

  40. Li S (2011) Concise formulas for the area and volume of a hyperspherical cap. Asian J Math Stat 4(1):66–70

    Article  MathSciNet  Google Scholar 

  41. Lin YY, Liu TL (2011) Multiple kernel learning for dimensionality reduction. IEEE Trans Pattern Anal Mach Intell 33:1–14

    Article  Google Scholar 

  42. Linnett JW (1942) The relation between potential energy and interatomic distance in some diatomic molecules. Trans Faraday Soc 38:1–9

    Article  Google Scholar 

  43. Liu H, Ding X (2005) Handwritten character recognition using gradient feature and quadratic classifier with multiple discrimination schemes. In: International conference on document analysis and recognition, pp 19–23

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

    Article  Google Scholar 

  45. P. M (2011) Coherence and diversity, http://www.petermerry.org/blog/2011/coherence-and-diversity/

  46. Martin D, Fowlkes C, Malik J Tal D (2001) A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: International conference on computer vision

  47. Mira J, Sandoval F (1995) From natural to artificial neural computation. In: International workshop on artificial neural networks

  48. Misra G, Golshan B, Terzi E (2012) A framework for evaluating the smoothness of data-mining results. In: Joint European conference on machine learning and knowledge discovery in databases

  49. Moon TK (1996) Similarity methods in signal processing. IEEE Trans Signal Process 44(4):827–833

    Article  Google Scholar 

  50. MOSEK A (2008) The MOSEK optimization toolbox for MATLAB manual, http://ww.mosek.com/

  51. Muandet K, Fukumizu K, Dinuzzo F, Schölkopf B (2012) Learning from distributions via support measure machines. In: Advances in neural information processing systems, pp 10–18

  52. Müller A (1997) Integral probability metrics and their generating classes of functions. Adv Appl Probab 29:429–443

    Article  MATH  MathSciNet  Google Scholar 

  53. Pekalska E, Duin RPW (2001) Automatic pattern recognition by similarity representations - a novel approach. Electron Lett 37:159–160

    Article  Google Scholar 

  54. Piciarelli C, Micheloni C, Foresti GL (2008) Trajectory-based anomalous event detection. IEEE Trans Circuits Syst Video Technol 18(11):1544–1554

    Article  Google Scholar 

  55. Plat JC (1998) Fast training of support vector machines using sequential minimal optimization. J Mach Learn Res 1889–1918

  56. Rolle K (2015) Heat and mass transfer. Cengage Learning, Ohio, USA

  57. Schneider R (2013) Convex bodies: The Brunn–Minkowski theory. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  58. Schölkopf, B (2001) The kernel trick for distances. In Advances in neural information processing systems

  59. Sebe N, Tian Q, Lew MS, Huang TS (2008) Guest editorial: Similarity matching in computer vision and multimedia. Comput Vis Image Underst 110(3):309–311

    Article  Google Scholar 

  60. Seidenari L, Serra G, Bagdanov AD, Del Bimbo A (2014) Local pyramidal descriptors for image recognition. IEEE Trans Pattern Anal Mach Intell 36(5):1033–1040

    Article  Google Scholar 

  61. Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22(8):888–905

    Article  Google Scholar 

  62. Simonovits M (2003) How to compute the volume in high dimension? Math Progr 97(1):337–374

    Article  MATH  MathSciNet  Google Scholar 

  63. Slimene A, Zagrouba E (2013) Kernel maximum mean discrepancy for region merging approach. In: Computer analysis of images and patterns, pp 475–482

  64. Stark M, Schiele B (2007) How good are local features for classes of geometric objects. In: IEEE international conference on computer vision

  65. Sun S (2013) A survey of multi-view machine learning. Neural Comput Appl 23(7–8):2031–2038

    Article  Google Scholar 

  66. Tax DMJ, Duin RPW (2004) Support vector data description. Mach Learn 54(1):45–66

    Article  MATH  Google Scholar 

  67. Torki M, Elgammal A (2010) Putting local features on a manifold. In: IEEE conference on computer vision and pattern recognition (CVPR), pp 1743–1750

  68. Wang B, Sung KK, Ng TK (2002) The localized consistency principle for image matching under non-uniform illumination variation and affine distortion. In: European Conference on Computer Vision, pp 205–219

  69. Wang J, Sang N, Wang Z, Gao C (2016) Similarity learning with top-heavy ranking loss for person re-identification. IEEE Signal Process Lett 23(1):84–88

    Article  Google Scholar 

  70. Weibel C (2007) Minkowski sums of polytopes: combinatorics and computation, PhD thesis, Lcole polytechnique fdrale de Lausanne (EPFL)

  71. Williams C, Seeger M (2001) Using the Nystrom method to speed up kernel machines. In: Advances in Neural Information Processing Systems, pp 682–688

  72. Xiong H, Chen XW (2006) Kernel-based distance metric learning for microarray data classification. BMC Bioinformatics 7(1):299

    Article  MathSciNet  Google Scholar 

  73. Z H, Berg AC, Maire M, Malik J (2006) SVM-KNN: discriminative nearest neighbor classification for visual category recognition. In: IEEE conference on computer vision and pattern recognition, pp 2126–2136

  74. Zhu X, Suk HI, Shen D (2014) Matrix-similarity based loss function and feature selection for Alzheimer’s disease diagnosis. In: IEEE conference on computer vision and pattern recognition, pp 3089–3096

Download references

Author information

Authors and Affiliations

  1. Laboratoire LIMTIC, LR16ES06, Institut Supérieur d’Informatique, Université de Tunis El Manar, 2080, Ariana, Tunisia

    Alya Slimene & Ezzeddine Zagrouba

Authors
  1. Alya Slimene
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Ezzeddine Zagrouba
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Alya Slimene.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Slimene, A., Zagrouba, E. Overlapping area hyperspheres for kernel-based similarity method. Pattern Anal Applic 20, 1227–1243 (2017). https://doi.org/10.1007/s10044-017-0604-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10044-017-0604-0

Keywords