Skip to main content

2015 | OriginalPaper | Buchkapitel

Spectral Shape Decomposition by Using a Constrained NMF Algorithm

verfasst von : Foteini Fotopoulou, Emmanouil Z. Psarakis

Erschienen in: Computer Vision - ACCV 2014 Workshops

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, the shape decomposition problem is addressed as a solution of an appropriately constrained Nonnegative Matrix Factorization Problem (NMF). Inspired from an idealization of the visibility matrix having a block diagonal form, special requirements while formulating the NMF problem are taken into account. Starting from a contaminated observation matrix, the objective is to reveal its low rank almost block diagonal form. Although the proposed technique is applied to shapes on the MPEG7 database, it can be extended to 3D objects. The preliminary results we have obtained are very promising.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
1
In our experiments for the implementation of the matrix completion techniques we have used the matlab codes from http://​perception.​csl.​illinois.​edu/​matrix-rank/​sample_​code.​html.
 
Literatur
1.
Zurück zum Zitat Ullman, S.: High-Level Vision: Object Recognition and Visual Cognition. MIT press, Cambridge (2000) Ullman, S.: High-Level Vision: Object Recognition and Visual Cognition. MIT press, Cambridge (2000)
2.
Zurück zum Zitat Wang, Y.X., Zhang, Y.J.: Nonnegative matrix factorization: a comprehensive review. IEEE Trans. Knowl. Data Eng. 25, 1336–1353 (2013)CrossRef Wang, Y.X., Zhang, Y.J.: Nonnegative matrix factorization: a comprehensive review. IEEE Trans. Knowl. Data Eng. 25, 1336–1353 (2013)CrossRef
3.
Zurück zum Zitat Fotopoulou, F., Psarakis, E.Z.: A visibility graph based shape decomposition technique. In: VISAPP (1), pp. 515–522 (2014) Fotopoulou, F., Psarakis, E.Z.: A visibility graph based shape decomposition technique. In: VISAPP (1), pp. 515–522 (2014)
4.
Zurück zum Zitat Singh, M., Seyranian, G.D., Hoffman, D.D.: Parsing silhouettes: the short-cut rule. Percept. Psychophys. 61, 636–660 (1999)CrossRef Singh, M., Seyranian, G.D., Hoffman, D.D.: Parsing silhouettes: the short-cut rule. Percept. Psychophys. 61, 636–660 (1999)CrossRef
5.
Zurück zum Zitat Hoffman, D.D., Richards, W.A.: Parts of recognition. Cognition 18, 65–96 (1984)CrossRef Hoffman, D.D., Richards, W.A.: Parts of recognition. Cognition 18, 65–96 (1984)CrossRef
6.
Zurück zum Zitat Latecki, L.J., Lakämper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vis. Image Underst. 73, 441–454 (1999)CrossRef Latecki, L.J., Lakämper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vis. Image Underst. 73, 441–454 (1999)CrossRef
7.
Zurück zum Zitat Walker, L.L., Malik, J.: Can convexity explain how humans segment objects into parts? J. Vis. 3, 503–503 (2003)CrossRef Walker, L.L., Malik, J.: Can convexity explain how humans segment objects into parts? J. Vis. 3, 503–503 (2003)CrossRef
8.
Zurück zum Zitat Lien, J.M., Amato, N.M.: Approximate convex decomposition of polygons. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 17–26. ACM (2004) Lien, J.M., Amato, N.M.: Approximate convex decomposition of polygons. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pp. 17–26. ACM (2004)
9.
Zurück zum Zitat Liu, H., Liu, W., Latecki, L.J.: Convex shape decomposition. In: 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 97–104. IEEE (2010) Liu, H., Liu, W., Latecki, L.J.: Convex shape decomposition. In: 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 97–104. IEEE (2010)
10.
Zurück zum Zitat Ren, Z., Yuan, J., Li, C., Liu, W.: Minimum near-convex decomposition for robust shape representation. In: 2011 IEEE International Conference on Computer Vision (ICCV), pp. 303–310. IEEE (2011) Ren, Z., Yuan, J., Li, C., Liu, W.: Minimum near-convex decomposition for robust shape representation. In: 2011 IEEE International Conference on Computer Vision (ICCV), pp. 303–310. IEEE (2011)
11.
Zurück zum Zitat Jiang, T., Dong, Z., Ma, C., Wang, Y.: Toward perception-based shape decomposition. In: Lee, K.M., Matsushita, Y., Rehg, J.M., Hu, Z. (eds.) ACCV 2012, Part II. LNCS, vol. 7725, pp. 188–201. Springer, Heidelberg (2013) CrossRef Jiang, T., Dong, Z., Ma, C., Wang, Y.: Toward perception-based shape decomposition. In: Lee, K.M., Matsushita, Y., Rehg, J.M., Hu, Z. (eds.) ACCV 2012, Part II. LNCS, vol. 7725, pp. 188–201. Springer, Heidelberg (2013) CrossRef
12.
Zurück zum Zitat Ma, C., Dong, Z., Jiang, T., Wang, Y., Gao, W.: A method of perceptual-based shape decomposition. In: IEEE International Conference on Computer Vision, ICCV 2013, Sydney, Australia, 1–8 December 2013, pp. 873–880 (2013) Ma, C., Dong, Z., Jiang, T., Wang, Y., Gao, W.: A method of perceptual-based shape decomposition. In: IEEE International Conference on Computer Vision, ICCV 2013, Sydney, Australia, 1–8 December 2013, pp. 873–880 (2013)
13.
Zurück zum Zitat Mi, X., DeCarlo, D.: Separating parts from 2d shapes using relatability. In: IEEE 11th International Conference on Computer Vision, 2007, ICCV 2007, pp. 1–8. IEEE (2007) Mi, X., DeCarlo, D.: Separating parts from 2d shapes using relatability. In: IEEE 11th International Conference on Computer Vision, 2007, ICCV 2007, pp. 1–8. IEEE (2007)
14.
Zurück zum Zitat De Goes, F., Goldenstein, S., Velho, L.: A hierarchical segmentation of articulated bodies. Comput. Graph. Forum 27, 1349–1356 (2008). Wiley Online LibraryCrossRef De Goes, F., Goldenstein, S., Velho, L.: A hierarchical segmentation of articulated bodies. Comput. Graph. Forum 27, 1349–1356 (2008). Wiley Online LibraryCrossRef
15.
Zurück zum Zitat Asafi, S., Goren, A., Cohen-Or, D.: Weak convex decomposition by lines-of-sight. Comput. Graph. Forum 32, 23–31 (2013). Wiley Online LibraryCrossRef Asafi, S., Goren, A., Cohen-Or, D.: Weak convex decomposition by lines-of-sight. Comput. Graph. Forum 32, 23–31 (2013). Wiley Online LibraryCrossRef
16.
Zurück zum Zitat Paatero, P., Tapper, U.: Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values. Environmetrics 5, 111–126 (1994)CrossRef Paatero, P., Tapper, U.: Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values. Environmetrics 5, 111–126 (1994)CrossRef
17.
Zurück zum Zitat Paatero, P.: Least squares formulation of robust non-negative factor analysis. Chemom. Intell. Lab. Syst. 37, 23–35 (1997)CrossRef Paatero, P.: Least squares formulation of robust non-negative factor analysis. Chemom. Intell. Lab. Syst. 37, 23–35 (1997)CrossRef
18.
Zurück zum Zitat Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: Leen, T.K., Dietterich, T.G., Tresp, V. (eds.) Advances in Neural Information Processing Systems, pp. 556–562. MIT Press, Cambridge (2000) Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: Leen, T.K., Dietterich, T.G., Tresp, V. (eds.) Advances in Neural Information Processing Systems, pp. 556–562. MIT Press, Cambridge (2000)
19.
Zurück zum Zitat Li, S.Z., Hou, X., Zhang, H., Cheng, Q.: Learning spatially localized, parts-based representation. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001, CVPR 2001, vol. 1, p. I-207. IEEE (2001) Li, S.Z., Hou, X., Zhang, H., Cheng, Q.: Learning spatially localized, parts-based representation. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2001, CVPR 2001, vol. 1, p. I-207. IEEE (2001)
20.
Zurück zum Zitat Ding, C., Li, T., Peng, W., Park, H.: Orthogonal nonnegative matrix tri-factorizations for clustering. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 126–135. ACM (2006) Ding, C., Li, T., Peng, W., Park, H.: Orthogonal nonnegative matrix tri-factorizations for clustering. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 126–135. ACM (2006)
21.
Zurück zum Zitat Ding, C.H., He, X., Simon, H.D.: On the equivalence of nonnegative matrix factorization and spectral clustering. In: SDM, vol. 5, pp. 606–610. SIAM (2005) Ding, C.H., He, X., Simon, H.D.: On the equivalence of nonnegative matrix factorization and spectral clustering. In: SDM, vol. 5, pp. 606–610. SIAM (2005)
22.
Zurück zum Zitat Lin, C.J.: On the convergence of multiplicative update algorithms for nonnegative matrix factorization. IEEE Trans. Neural Netw. 18, 1589–1596 (2007)CrossRef Lin, C.J.: On the convergence of multiplicative update algorithms for nonnegative matrix factorization. IEEE Trans. Neural Netw. 18, 1589–1596 (2007)CrossRef
23.
Zurück zum Zitat Mirzal, A.: A convergent algorithm for orthogonal nonnegative matrix factorization. J. Comput. Appl. Math. 260, 149–166 (2014)CrossRefMATHMathSciNet Mirzal, A.: A convergent algorithm for orthogonal nonnegative matrix factorization. J. Comput. Appl. Math. 260, 149–166 (2014)CrossRefMATHMathSciNet
24.
Zurück zum Zitat Boutsidis, C., Gallopoulos, E.: Svd based initialization: a head start for nonnegative matrix factorization. Pattern Recogn. 41, 1350–1362 (2008)CrossRefMATH Boutsidis, C., Gallopoulos, E.: Svd based initialization: a head start for nonnegative matrix factorization. Pattern Recogn. 41, 1350–1362 (2008)CrossRefMATH
25.
Zurück zum Zitat Candès, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM (JACM) 58, 11 (2011)CrossRef Candès, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM (JACM) 58, 11 (2011)CrossRef
26.
Zurück zum Zitat Latecki, L.J., Lakamper, R., Eckhardt, T.: Shape descriptors for non-rigid shapes with a single closed contour. In: IEEE Conference on Computer Vision and Pattern Recognition, 2000, Proceedings, vol. 1, pp. 424–429. IEEE (2000) Latecki, L.J., Lakamper, R., Eckhardt, T.: Shape descriptors for non-rigid shapes with a single closed contour. In: IEEE Conference on Computer Vision and Pattern Recognition, 2000, Proceedings, vol. 1, pp. 424–429. IEEE (2000)
27.
Zurück zum Zitat Gopalan, R., Turaga, P., Chellappa, R.: Articulation-invariant representation of non-planar shapes. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part III. LNCS, vol. 6313, pp. 286–299. Springer, Heidelberg (2010) CrossRef Gopalan, R., Turaga, P., Chellappa, R.: Articulation-invariant representation of non-planar shapes. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part III. LNCS, vol. 6313, pp. 286–299. Springer, Heidelberg (2010) CrossRef
28.
Zurück zum Zitat Lin, Z., Chen, M., Ma, Y.: The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices (2010). arXiv preprint arXiv:1009.5055 Lin, Z., Chen, M., Ma, Y.: The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices (2010). arXiv preprint arXiv:​1009.​5055
29.
Zurück zum Zitat Lin, Z., Ganesh, A., Wright, J., Wu, L., Chen, M., Ma, Y.: Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. Comput. Adv. MultiSens. Adapt. Process. (CAMSAP) 61 (2009) Lin, Z., Ganesh, A., Wright, J., Wu, L., Chen, M., Ma, Y.: Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. Comput. Adv. MultiSens. Adapt. Process. (CAMSAP) 61 (2009)
30.
Zurück zum Zitat Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)CrossRefMATHMathSciNet Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)CrossRefMATHMathSciNet
31.
Zurück zum Zitat Wright, J., Ganesh, A., Rao, S., Peng, Y., Ma, Y.: Robust principal component analysis: exact recovery of corrupted low-rank matrices by convex optimization. In: Proceedings of Neural Information Processing Systems, vol. 3 (2009) Wright, J., Ganesh, A., Rao, S., Peng, Y., Ma, Y.: Robust principal component analysis: exact recovery of corrupted low-rank matrices by convex optimization. In: Proceedings of Neural Information Processing Systems, vol. 3 (2009)
Metadaten
Titel
Spectral Shape Decomposition by Using a Constrained NMF Algorithm
verfasst von
Foteini Fotopoulou
Emmanouil Z. Psarakis
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-16634-6_3