Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Pattern Analysis and Applications
Published in: Pattern Analysis and Applications 3/2018

22-01-2018 | Industrial and Commercial Application

On the definition of shape parts: a dominant sets approach

Authors: Foteini Fotopoulou, George Economou

Published in: Pattern Analysis and Applications | Issue 3/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In the present paper, a novel graph-based approach to the shape decomposition problem is addressed. The shape is appropriately transformed into a visibility graph enriched with local neighborhood information. A two-step diffusion process is then applied to the visibility graph that efficiently enhances the information provided, thus leading to a more robust and meaningful graph construction. Inspired by the notion of a clique as a strict cluster definition, the dominant sets algorithm is invoked, slightly modified to comport with the specific problem of defining shape parts. The cluster cohesiveness and a node participation vector are two important outputs of the proposed graph partitioning method. Opposed to most of the existing techniques, the final number of the clusters is determined automatically, by estimating the cluster cohesiveness on a random network generation process. Experimental results on several shape databases show the effectiveness of our framework for graph-based shape decomposition.
previous article Accurate image segmentation using Gaussian mixture model with saliency map
next article Correction to: Detection and classification of vehicles from omnidirectional videos using multiple silhouettes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
In an undirected graph, a clique is a subset of its vertices such that every two vertices in the subset are connected by an edge.
 
Literature
1.
Marvaniya S, Gupta R, Mittal A (2015) Adaptive locally affine-invariant shape matching. Image Vis Comput
2.
Zhu SC, Yuille AL (1996) FORMS: a flexible object recognition and modelling system. Int J Comput Vis 20:187–212CrossRef
3.
de Berg M, Cheong O, van Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications, 3rd edn. Springer, BerlinCrossRefMATH
4.
Latecki LJ, Lakämper R (1999) Convexity rule for shape decomposition based on discrete contour evolution. Comput Vis Image Underst 73(3):441–454CrossRef
5.
Belkin M, Niyogi P (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput 16(6):1373–1396CrossRefMATH
6.
He XF, Niyogi P (2003) Locality preserving projections. In Advances in neural information processing systems (NIPS), vol 16
7.
Fotopoulou F, Psarakis EZ (2014) A visibility graph based shape decomposition technique. In: VISAPP, Lisbon, Portugal
8.
9.
Asa S, Goren A, Cohen-Or D (2013) Weak convex decomposition by lines-of-sight. Comput Graph Forum 32:23–31CrossRef
10.
Hagen L, Kahng A (1992) New spectral methods for ratio cut partitioning and clustering. IEEE Trans Comput Aided Des Integr Circuits Syst 11(9):1074–1085CrossRef
11.
Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22(8):888–905CrossRef
12.
Zahn CT (1971) Graph-theoretic methods for detecting and describing gestalt clusters. IEEE Trans Comput 20:68–86CrossRefMATH
13.
Auguston JG, Minker J (1970) An analysis of some graph theoretical clustering techniques. J ACM 17(4):571–588CrossRef
14.
Pavan M, Pellilio M (2007) Dominant sets and pairwise clustering. IEEE Trans Pattern Anal Mach Intell 29(1):167–172CrossRef
15.
Pavan M, Pellilio M (2003) A new graph-theoretic approach to clustering and segmentation. In: Computer vision and pattern recognition
16.
Wang C, Liu W, Lai Z, Wang H (2013) Perceptually friendly shape decomposition by resolving segmentation points with minimum cost. Vis Commun Image Represent 24(3):270–282CrossRef
17.
Lisa LJ, Morin G, Begault A, Chaine R, Abiva J, Hubert E, Hurdal M, Li M, Paniagua B, Tran G, Cani M-P (2015) Research in shape modeling. In: Identifying perceptually salient features on 2D shapes. Springer, Los Angeles, pp 129–153
18.
Siddiqi K, Kimia BB (1995) Parts of visual form: computational aspects. Pattern Anal Mach Intell 17(3):239–251CrossRef
19.
Singh M, Seyranian G, Hoffman D (1999) Parsing silhouettes: the short-cut rule. Percept Psychophys 61(4):636–660CrossRef
20.
Xiaofeng M, DeCarlo D (2007) Separating parts from 2D shapes using relatability. In: IEEE 11th international conference on computer vision, ICCV 2007
21.
Juengling R, Mitchell M (2007) Combinatorial shape decomposition. In: ISVC’07 proceedings of the 3rd international conference on advances in visual computing
22.
Lien J-M, Amato NM (2004) Approximate convex decomposition of polygons. In: Special issue on the 20th ACM symposium on computational geometry, vol 35, no 1–2, pp 100–123
23.
Liu H, Liu W, Latecki LJ (2010) Convex shape decomposition. In: CVPR
24.
Ren Z, Yuan J, Li C, Liu W (2011) Minimum near-convex decomposition for robust shape representation. In: ICCV
25.
Shapiro LG, Haralick RM (1979) Decomposition of two-dimensional shapes by graph-theoretic clustering. IEEE Trans Pattern Anal Mach Intell 1(1):10–20CrossRef
26.
Fotopoulou F, Psarakis EZ (2014) Spectral shape decomposition by using a constrained NMF algorithm. In: International ACCV workshop on feature and similarity learning for computer vision (FSLCV 2014), Singapore
27.
Ling H, Jacobs DW (2007) Shape classification using the inner-distance. IEEE Trans Pattern Anal Mach Intell 29(2):286–299CrossRef
28.
O’Neil PV (2011) Advanced engineering mathematics, 7th edn. Cengage Learning, BostonMATH
29.
30.
Raghavan VV, Yu CC (1981) A comparison of the stability characteristics of some graph theoretic clustering methods. IEEE Trans Pattern Anal Mach Intell 3:393–402CrossRefMATH
31.
32.
Sarkar S, Boyer KL (1998) Quantitative measures of change based on feature organization: eigenvalues and eigenvectors. CVIU 71(1):110–136
33.
Weibull JW (1995) Evolutionary game theory. MIT Press, CambridgeMATH
34.
35.
36.
Latecki LJ, Lakamper R, Eckhardt U (2000) Shape descriptors for non-rigid shapes with a single closed contour. In: CVPR
37.
Sebastian T, Klein P, Kimia B (2004) Recognition of shapes by editing their shock graphs. IEEE Trans PAMI 26(5):550–571CrossRef
38.
Gopalan R, Turaga P, Chellappa R (2010) Articulation-invariant representation of non-planar shapes. In: ECCV 2010
39.
Jiang T, Dong Z, Ma C, Wang Y (2012) Toward perception-based shape decomposition. In: ACCV
40.
41.
Erol A, Bebis G, Nicolescu M, Boyle RD, Twombly X (2007) Vision-based hand pose estimation: a review. Comput Vis Image Underst CVIU 108:52–73CrossRef
42.
Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev 69(2):026113
43.
Rand WM (1971) Objective criteria for the evaluations of clustering methods. Am Stat Assoc 66(336):846–850CrossRef
44.
Liu G, Xi Z, Lien JM (2014) Dual-space decomposition of 2D complex shapes. In: 2014 IEEE conference on computer vision and pattern recognition, Columbus, OH, USA
Metadata
Title
On the definition of shape parts: a dominant sets approach
Authors
Foteini Fotopoulou
George Economou
Publication date
22-01-2018
Publisher
Springer London
Published in
Pattern Analysis and Applications / Issue 3/2018
Print ISSN: 1433-7541
Electronic ISSN: 1433-755X
DOI
https://doi.org/10.1007/s10044-018-0679-2

Other articles of this Issue 3/2018

Pattern Analysis and Applications 3/2018 Go to the issue

Theoretical Advances

Kernelized inner product-based discriminant analysis for interval data

Theoretical Advances

A new linear discriminant analysis algorithm based on L1-norm maximization and locality preserving projection

Survey

A novel active contour model driven by J-divergence entropy for SAR river image segmentation

Original Article

BMOG: boosted Gaussian Mixture Model with controlled complexity for background subtraction

Original Article

A deep learning approach for the forensic evaluation of sexual assault

Short Paper

A multi-biometric iris recognition system based on a deep learning approach

Premium Partner

    Image Credits