We study the problem of detecting and localizing objects in still, gray-scale images making use of the part-based representation provided by nonnegative matrix factorizations. Nonnegative matrix factorization represents an emerging example of subspace methods, which is able to extract interpretable parts from a set of template image objects and then to additively use them for describing individual objects. In this paper, we present a prototype system based on some nonnegative factorization algorithms, which differ in the additional properties added to the nonnegative representation of data, in order to investigate if any additional constraint produces better results in general object detection via nonnegative matrix factorizations. 1. Introduction The notion of low dimensional approximation has played a fundamental role in effectively and efficiently processing and conceptualizing huge amount of data stored in large sparse matrices. Particularly, subspace techniques, such as Singular Value Decomposition [1], Principal Component Analysis (PCA) [2], and Independent Component Analysis [3], represent a class of linear algebra methods largely adopted to analyze high dimensional dataset in order to discover latent structures by projecting it onto a low dimensional space. Generally, a subspace method is characterized by learning a set of base vectors from a set of suitable data templates. This vector spans a subspace which is able to capture the essential structure of the input data. Once the subspace has been found (during the off-line learning phase), the detection of a new sample can be accomplished (in the so-called on-line detection phase) by projecting it on the subspace and finding the nearest neighbor of templates projected onto this subspace. These methods have found efficient applications in several areas of information retrieval, computer vision, and pattern recognition, especially in the fields of face identification [4, 5], recognition of digits and characters [6, 7], and molecular pattern discovery [8, 9]. However, pertinent information stored in many data matrices are often nonnegative (examples are pixels in images, the probability of a particular topic appearing in a linguistic document, the amount of pollutant emitted by a factory, and so on [10–15]). During the analysis process, taking into account this nonnegativity constraint could bring some benefits in terms of interpretability and visualization of large scale data, while maintaining the physical feasibility more closely. Nevertheless, classical subspace methods describe data as a
References
[1]
G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, 3rd edition, 2001.
[2]
I. T. Jolliffe, Principal Component Analysis, Springer, 1986.
D. Guillamet and J. Vitriá, “Non-negative matrix factorization for face recognition,” Lecture Notes in Computer Science, vol. 2504, pp. 336–344, 2002.
[5]
X. Sun, Q. Zhang, and Z. Wang, “Face recognition based on NMF and SVM,” in Proceedings of the 2nd International Symposium on Electronic Commerce and Security, pp. 616–619, 2009.
[6]
D. Guillamet and J. Vitrià, “Evaluation of distance metrics for recognition based on non-negative matrix factorization,” Pattern Recognition Letters, vol. 24, no. 9-10, pp. 1599–1605, 2003.
[7]
W. Liu and N. Zheng, “Non-negative matrix factorization based methods for object recognition,” Pattern Recognition Letters, vol. 25, no. 8, pp. 893–897, 2004.
[8]
Y. Gao and G. Church, “Improving molecular cancer class discovery through sparse non-negative matrix factorization,” Bioinformatics, vol. 21, no. 21, pp. 3970–3975, 2005.
[9]
H. Kim and H. Park, “Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis,” Bioinformatics, vol. 23, no. 12, pp. 1495–1502, 2007.
[10]
P. Paatero and U. Tapper, “Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values,” Environmetrics, vol. 5, no. 2, pp. 111–126, 1994.
[11]
D. D. Lee and S. H. Seung, “Algorithms for non-negative matrix factorization,” in Proceedings of the Advances in Neural Information Processing Systems Conference, vol. 13, pp. 556–562, MIT Press, 2000.
[12]
M. Novak and R. Mammone, “Use of nonnegative matrix factorization for language model adaptation in a lecture transcription task,” in Proceedings of the IEEE International Conference Acoustic, Speech and Signal Processing, vol. 1, pp. 541–544, IEEE Computer Society, 2001.
[13]
M. Chu and R. J. Plemmons, “Nonnegative matrix factorization and applications,” IMAGE, Bulletin of the International Linear Algebra Society, vol. 34, pp. 2–7, 2005.
[14]
V. P. Pauca, J. Piper, and R. J. Plemmons, “Nonnegative matrix factorization for spectral data analysis,” Linear Algebra and Its Applications, vol. 416, no. 1, pp. 29–47, 2006.
[15]
Chen D. and Plemmons R., “Nonnegativity constraints in numerical analysis,” in Proceedings of the Symposium on the Birth of Numerical Analysis, pp. 541–544, World Scientific Press, 2008.
[16]
D. D. Lee and H. S. Seung, “Learning the parts of objects by non-negative matrix factorization,” Nature, vol. 401, no. 6755, pp. 788–791, 1999.
[17]
M. A. Turk and A. P. Pentland, “Face recognition using eigenfaces,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 586–591, 1991.
[18]
B. Schiele and J. L. Crowley, “Recognition without correspondence using multidimensional receptive field histograms,” International Journal of Computer Vision, vol. 36, no. 1, pp. 31–50, 2000.
[19]
I. Biederman, “Recognition-by-components: a theory of human image understanding,” Psychological Review, vol. 94, no. 2, pp. 115–147, 1987.
[20]
T. S. Lee, “Image representation using 2d gabor wavelets,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 10, pp. 959–971, 1996.
[21]
R. N. Strickland and H. I. Hahn, “Wavelet transform methods for object detection and recovery,” IEEE Transactions on Image Processing, vol. 6, no. 5, pp. 724–735, 1997.
[22]
P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. I511–I518, December 2001.
[23]
A. Mohan, C. Papageorgiou, and T. Poggio, “Example-based object detection in images by components,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 4, pp. 349–361, 2001.
[24]
S. Ullman, M. Vidal-Naquet, and E. Sali, “Visual features of intermediate complexity and their use in classification,” Nature Neuroscience, vol. 5, no. 7, pp. 682–687, 2002.
[25]
S. Agarwal, A. Awan, and D. Roth, “Learning to detect objects in images via a sparse, part-based representation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 11, pp. 1475–1490, 2004.
[26]
D. Donoho and V. Stodden, “When does non-negative matrix factorization give a correct decomposition into parts?” in Proceedings of the Neural Information Processing Systems, vol. 16, pp. 1141–1149, 2003.
[27]
B. J. Shastri and M. D. Levine, “Face recognition using localized features based on non-negative sparse coding,” Machine Vision and Applications, vol. 18, no. 2, pp. 107–122, 2007.
[28]
S. Z. Li, X. Hou, H. Zhang, and Q. S. Cheng, “Learning spatially localized, parts-based representation,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 207–212, IEEE Computer Society, 2001.
[29]
I. Buciu and I. Pitas, “A new sparse image representation algorithm applied to facial expression recognition,” in Proceedings of the 14th IEEE Signal Processing Society Workshop of the Machine Learning for Signal Processing, pp. 539–548, October 2004.
[30]
I. Buciu, “Learning sparse non-negative features for object recognition,” in Proceedings of the IEEE 3rd International Conference on Intelligent Computer Communication and Processing (ICCP '07), pp. 73–79, September 2007.
[31]
P. O. Hoyer, “Non-negative matrix factorization with sparseness constraints,” Journal of Machine Learning Research, vol. 5, pp. 1457–1469, 2004.
[32]
D. Soukup and I. Bajla, “Robust object recognition under partial occlusions using NMF,” Computational Intelligence and Neuroscience, vol. 2008, Article ID 857453, 14 pages, 2008.
[33]
A. Berman and R. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, 1979.
[34]
M. T. Chu, F. Diele, R. Plemmons, and S. Ragni, “Optimality, computation and interpretation of nonnegative matrix factorizations,” Tech. Rep., NCSU, 2005.
[35]
M. T. Chu and M. M. Lin, “Low-dimensional polytope approximation and its applications to nonnegative matrix factorization,” SIAM Journal on Scientific Computing, vol. 30, no. 3, pp. 1131–1155, 2007.
[36]
C.-J. Lin, “Projected gradient methods for nonnegative matrix factorization,” Neural Computation, vol. 19, no. 10, pp. 2756–2779, 2007.
[37]
C. Ding, T. Li, W. Peng, and H. Park, “Orthogonal nonnegative matrix tri-factorizations for clustering,” in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '06), pp. 126–135, August 2006.
[38]
S. Choi, “Algorithms for orthogonal nonnegative matrix factorization,” in Proceedings of the International Joint Conference on Neural Networks (IJCNN '08), pp. 1828–1832, June 2008.
[39]
N. Del Buono, “A penalty function for computing orthogonal non-negative matrix factorizations,” in Proceedings of the 9th International Conference on Intelligent Systems Design and Applications (ISDA '09), pp. 1001–1005, December 2009.
[40]
C. Ding, T. Li, and W. Peng, “Nonnegative matrix factorization and probabilistic latent semantic indexing: equivalence, chi-square statistic, and a hybrid method,” in Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference (AAAI '06), pp. 342–347, July 2006.
[41]
C. Ding, X. He, and H. D. Simon, “On the equivalence of nonnegative matrix factorization and spectral clustering,” in Proceedings of the SIAM Data Mining Conference, pp. 606–610, 2005.
[42]
K. Murphy, A. Torralba, D. Eaton, and W. Freeman, “Object detection and localization using local and global features,” Lecture Notes in Computer Science, vol. 4170, pp. 394–412, 2006.
