Recognition via Sparse Representation: Robustness, Occlusion and Feature Selection

This technical report combines two commonly-themed submissions to ICCV 2007. The two papers reconsider several fundamental problems in recognition from the perspective of sparsity. The representation sought by recognition systems is inherently sparse, since the test image should ideally be interpreted only in terms of training images of the same object. Our algorithms exploit this sparsity, classifying a test image based on a sparse representation in terms of the training images, computed via l1-minimization. The first of the two papers investigates the implications of this framework for feature selection. We show that, in agreement with the theory of compressive sensing, if sparsity is properly enforced, the choice of features is no longer critical. What is critical is that the number of features is sufficient and that the sparse representation is properly found. In this context, highly accurate recognition is possible using severely down sampled images or even randomly generated features! The second paper shows how robust recognition in the presence of occlusion can also be cast as a sparse representation problem. Here, our algorithm represents the test image as a sparse linear combination of the training images, plus a sparse error due to occlusion. The representation is efficiently and effectively computed by l1-minimization. We investigate the implications of this framework for the engineering of recognition systems showing how to predict how much occlusion the algorithm can tolerate, and how to choose the training data to maximize robustness.NSF / CAREER IIS-0347456, CRS-EHS-0509151, and CCF-TF-051495ONR / YIP N00014-05-1-063Ope