On the design of a sparsifying dictionary for compressive image feature extraction

On the Design of a Sparsifying Dictionary for Compressive Image Feature Extraction Marco Trevisi, Ricardo Carmona-Galán, Jorge Fernández-Berni, Ángel Rodríguez-Vázquez Instituto de Microelectrónica de Sevilla (IMSE-CNM) CSIC-Universidad de Sevilla, Spain. E-mail: {trevisi, rcarmona, berni, angel}@imse-cnm.csic.es Abstract— Compressive sensing is an alternative to Nyquistrate sampling when the signal to be acquired is known to be sparse or compressible. A sparse signal has a small number of nonzero components compared to its total length. This property can either exist either in the sampling domain, i. e. time or space, or with respect to a transform basis. There is a parallel between representing a signal in a compressed domain and feature extraction. In both cases, there is an effort to reduce the amount of resources required to describe a large set of data. A given feature is often represented by a set of parameters, which only acquire a relevant value in a few points in the image plane. Although there are some works reported on feature extraction from compressed samples, none of them considers the implementation of the feature extractor as a part of the sensor itself. Our approach is to introduce a sparsifying dictionary, feasibly implementable at the focal plane, which describes the image in terms of features. This allows a standard reconstruction algorithm to directly recover the interesting image features, discarding the irrelevant information. In order to validate the approach, we have integrated a Harris-Stephens corner detector into the compressive sampling process. We have evaluated the accuracy of the reconstructed corners compared to applying the detector to a reconstructed image. Keywords—compressive sampling; image feature extraction; sparse representation; I. INTRODUCTION Compressive sensing is a theoretical framework that provides the support for the reconstruction of undersampled signals. If the original signal can be sparsely represented in some domain, like natural images [1], then it is possible to recover it from a much smaller number of samples than that indicated by Nyquist-Shannon theorem. Therefore, if ܺ is a collection of either spatial or temporal samples of a signal, a set of measurements ܻ can be obtained through: ܻൌȰܺ (1) where Ȱ is the so-called measurement matrix. If signal ܺ can be sparsely represented by coefficients ߙ in a different base, we can rewrite Eq. (1) as: ܻൌȰȲߙ (2) where Ȳ is the sparsifying dictionary. The key requirement for achieving a successful reconstruction, i. e. approximating ܺ given the much smaller set ܻ, is the sparsity of the input signal. The way in which the samples of the original signal are linearly combined to from the compressed samples is encoded into the measurement matrix. In other words, matrix Ȱ contains the compressive strategy. On the other side, the sparsifying dictionary Ȳ transforms the original signal into a sparse version, referred to a transform basis. The inverse problem defined by Eq. (1) is undetermined as long as the elements in ܻ are fewer than those in ܺ. Although underdetermined problems are considered ill-posed, as there is no univocal solution to them, compressive sensing theory can lead to a unique solution by the means of convex optimization. The condition for this to be achieved is that the product of Ȱ and Ȳ holds the restricted isometry property (RIP) [2]. In this paper, we are evaluating the incorporation of feature extraction right at the sparsifying dictionary. The initial hypothesis is that if the relevant information is contained in a small number of pixels, i. e. those where a particular feature scores a noticeable value, the reconstruction of the features of an image can be realized on a smaller number of compressed samples than the reconstruction of the original image. This will seamlessly integrate feature extraction with the process of sampling and eliminating the need further processing after reconstruction. There are some examples in literature of dedicated image sensors implementing compressive sampling [3] [4], but they are mainly concerned with the generation of the samples at the focal plane. Concerning compressive feature detection, work on the characteristics of the measurement matrix has been reported to provide good results in detecting features [5]. Other studies concentrate in the propagation of properties from the original image to the compressed samples [6] [7]. Others apply the concept of compressive sampling at higher cognitive tasks, like object classification, by focusing on the reconstruction [8] [9]. To the best of our knowledge there are no previous attempts to generate compressed samples in a way that image features can be directly extracted with a standard reconstruction algorithm. II. DESIGN OF THE SPARSIFYING DICTIONARY Representing a signal in a transform basis involves the choice of a dictionary. In a sparse representation, most of the information contained in the signal is represented by only a few coefficients in the transform domain. The sparsifying dictionary contains a set of elements that are employed to represent each signal by means of linear combinations. When this approach is applied to image sensing, the dictionaries employed are usually based on the wavelet and cosine 978-1-5090-0246-7/15/$31.00 ©2015 IEEE 689 transforms, as they are the most suitable for image compression [10]. Knowledge regarding the kind of image to be sampled or regarding the content that one might be looking for can be used to create a sparsifying dictionary. The choice of dictionary that extracts features does not aim to represent a compressed form of the whole informational content of the sampled image. It rather focuses on the features of interest so that a standard reconstruction algorithm can process and recover only the relevant information contained in the image. In principle, we suppose that adjusting the sparsifying dictionary in order to reconstruct only a given set of features will reduce the amount of information that a reconstruction problem must handle. This will lead to faster reconstruction time, and the need of a smaller number of compressed samples. The sparsifying dictionary can be seen as a mask applied at the focal plane of a dedicated sensor implementing a compressive sensing strategy. To demonstrate this statement we have employed the Harris-Stephens corner detection algorithm [11]. This method is based on the comparison of an image patch with their neighboring overlapping patches, in terms of the sum of squared differences: ܧሺ݅ǡ݆ሻൌσݓሺݑǡݒሻȁܫሺݑ൅݅ǡݒ൅݆ሻെܫሺݑǡݒሻȁଶ ௨ǡ௩  (3) where ݓሺݑǡݒሻ are the weights over the window where the image intensity is evaluated, ܫሺݑǡݒሻ are the image intensity values in this window and ܫሺݑ൅݅ǡݒ൅݆ሻ are the image intensity values on a window that is shifted ݅ pixels in the vertical direction and ݆pixels in the horizontal. Usually, the ሺ݅ǡ݆ሻ pairs in which the difference is evaluated are: ሺͳǡͲሻ, ሺെͳǡͲሻ,ሺͲǡͳሻ and ሺͲǡെͳሻ. This means that a flat region will render small differences in all directions, an edge will render a small change in on direction and a noticeable large one in the other, and a corner yields large changes in both directions. Eq. (3) can be approximated by using Taylor expansion, and then written in a matrix form: ܧሺ݅ǡ݆ሻൌ൤݆݅൨ܣሾ݆݅ ሿ (4) where ܣ contains the products of the derivatives evaluated at the central pixel of the window ݓሺݑǡݒሻ. If a circularly weighted window is employed to have an isotropic response: ܣൌቈܫ௜ଶܫ௜ܫ௝ ܫ௜ܫ௝ܫ௝ଶ቉ (5) where ܫ௜ and ܫ௝are the partial derivatives of the image intensity in the ݅ and ݆directions, respectively. Hence, the presence of a corner is reported by two large eigenvalues of matrix ܣ. The response of every pixel can be defined as: ܴൌሺܣሻെ݇ሾሺܣሻሿଶ(6) where ݇ is employed to tune the sensitivity to changes of the algorithm. Usual values are in the ͲǤͲͶǦͲǤͳͷ range. In order to evaluate this response we need to compute the partial derivatives of the image intensity at every single pixel, what can be done with the help of the following masks: ݀௜ൌ൥െͳ െͳ െͳ ͲͲͲ ͳͳͳ ൩݀௝ൌ൥െͳ Ͳ ͳ െͳ Ͳ ͳ െͳ Ͳ ͳ൩ (7) which represent the partial derivatives in the vertical and horizontal directions. Therefore: ܫ௜ൌܫכ݀௜ and ܫ௝ൌܫכ݀௝(8) In order to test the procedure with an implementation of the NESTA algorithm [12], we have to convert images of size ܯൈܰ into column vectors of size ܰൈͳ . We will do that by rearranging image columns into one single column. Therefore the first ܯ components of the column-vector image ܫ௖ are the first column of the matrix image ܫ. The next ܯ components are the second column, and so on. By defining these ܯൈܯ matrices: ͲͳͲͲͲ ͲͲͲ ͳͲͳͲͲ ͲͲͲ ͲͳͲͳͲ ͲͲͲ ͲͲͳͲͳ ͲͲͲ ͲͲͲͳͲ ͲͲͲ ͲͲͲͲͲ ͲͳͲ ͲͲͲͲͲ ͳͲͳ ͲͲͲͲͲ ͲͳͲ   ªº «» − «» «» − «» − «» «» − «» =«» «» «» «» − «» − «» «» «» ¬¼ " " " " " #####%### " " " (9) and: ͳͳͲͲͲ ͲͲͲ ͳͳͳͲͲ ͲͲͲ ͲͳͳͳͲ ͲͲͲ ͲͲͳͳͳ ͲͲͲ ͲͲͲͳͳ ͲͲͲ ͲͲͲͲͲ ͳͳͲ ͲͲͲͲͲ ͳͳͳ ͲͲͲͲͲ Ͳͳͳ   ªº «» «» «» «» «» «» «» =«» «» «» «» «» «» «» «» ¬¼ " " " " " #####%### " " " (10) we can write these ܯܰൈܯܰ matrices: 690           ª « « « « « « =« « « « « « « ¬ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ " " " " ####%# " " "           ª « − « «− « − « =« « « « « « « ¬ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ " " " " ####% " " where each Ͳ is a ܯൈܯ matrix of zeros, and can be written as a matrix product: ܫ ௜௖ ൌܦ ௜ ܫ ௖ and ܫ ௝௖ ൌܦ ௝ These matrices, ܦ ௜ and ܦ ௝ can be employe d dictionary, Ȳ, as they hold the RIP when m measurement matrix Ȱ. We can therefo r computation of the partial derivatives of th e right at the sampling point. Then, we can algorithm to reconstruct directly the derivati v rendering the image and then computing the d e III. F EATURE R ECONSTRUCTION AND E In order to analyze the benefits of usi n masks ܦ ௜ and ܦ ௝ to recover a set of corners fr o sampled image we have devised an experime n grayscale picture of Lena (Fig. 1(a)). In ord e ground truth, Harris corners have been d e original image (Fig. 1(b)). As an illustratio n images that we will be obtaining, Fig. 1 reconstruction of the original Lena image compressed samples — b eing 4096 the total n of the original image. Fig. 1(d) shows the rec o directly from 1024 compressed samples obtained using the sparsifying dictionaries derivative masks. In order to evaluate the re s into account the distance between the origin a ones obtained by the different methods. We average distance given by: ݀ҧൌ ଵ ே σ ௣೔א௉బ ௣ೕא௉೐ ฮ݌ ௜ െ݌ ௝ ே ௜ୀଵ     º » » » » » » » » » » » » » ¼ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ ## (11)     º » » » » » » » » » −» » » ¼ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ Ͳ ͲͲ ## (12) therefore Eq. (8) ܫ ௖ (13) d as a sparsifying m ultiplied to the r e introduce the e image intensity use the NESTA v es instead of the e rivatives. E VALUATION n g the derivative o m a compressedn t using a 64 × 64 e r to establish the e tected over the n of the type of (c) displays the by using 1024 n umber of pixels o nstructed corners that have been that contain the s ults we will take a l corners and the have defined an ฮ (14) where ݌ ௜ one of the ܰ corners belo n of corners extracted from the origi n truth. The contribution to the aver a closest ݌ ௝ , a corner belonging to th e We will be counting the number o negatives as well. (a) (c) Fig. 1. (a) Original 64 × 64 image; (b) G detected over the original image; (c) H reconstructed image; (d) Corners directly ex t We have tested the extraction o reconstruction for different number s Fig. 2 we can see how the average d corners decays with the numbe r appreciated also that direct reconstr u accurate than performing Harris reconstructed image (red crosses), e compressed samples. Fig. 2. Average distance vs. number of sa m n ging to ܲ ଴ , which is the set n al image, i. e. the ground a ge distance is given by the e set of estimated points ܲ ௘ . o f false positives and false (b) (d) G round truth, i. e. Harris corners H arris corners detected over the t rated from compressed samples. o f Harris corners by direct s of compressed samples. In d istance to the ground-truth r of samples. It can be u ction (blue circles) is more corner detection over the e specially for a small set of m ples. 691 This information would be incomplete u n account the number of false positives and While the direct reconstruction of Harris c perform better than extracting Harris corne r reconstructed image, if it were to produce m o would be overall worse. Hence, Fig. 3 p lots th e negatives, i. e. corners that were present in image but are missing in the reconstructed number of compressed samples. The number o is slightly smaller for the direct reconstructio n the number of false positives, i. e. corners th a ground-truth image but are present in the reco n vs. the number of compressed samples agai n false positives is also slightly smaller reconstruction. In fact, even though the grap h cluttered, direct reconstruction of the derivati v image leads to an average of 11% less false n less false positives. We can conclude that not of the corners is more accurately determine d derivative masks as sparsifying dictionaries, also leads to better overall results by decreasi n false positives and false negatives. Fig. 3. False negatives vs. number of samples Fig. 4. False positives vs. number of samples n less we take into false negatives. c orners seems to r s on the already o re false results it e number of false the ground-truth version, vs. the o f false negatives n . Fig. 4 displays a t were not in the n structed version, n . The number of for the direct h ics are somehow v es of the original egatives and 8 % only the location d when using the but this method n g the number of The downside of applying this locate Harris-Stephens corners, necessary. Fortunately, this sends t h reconstruction side, alleviating the w IV. C ONCLUSI O Image description based on inserted into the compressive sen s successfully generated a set of c which features can be directly reco n recreate the original image first. A featureb ased description are muc h p ixels of the image, the number of c required for feature extraction un d going to be smaller. Experimental e by simulation. The direct reconstru c a set of compressed samples gene r as sparsifying dictionaries yields b characteristics of generic a set of fe a sparsifying dictionary would be the A CKNOWLED G This work has been funded b y through projects TEC2012-38921 - Region Development Fund, ERD F 430000 MINECO and IPC-20111 0 b y Junta de Andalucía through pro j and by the Office of Naval Rese N000141410355. R EFERENC [1] J. Romberg. “Imaging via Compr e Processing Magazine, Vol. 25, No. 2, p [2] R. G. Baraniuk, V. Cevher, M. B. W for Dimensionality Reduction and Perspective”. Proc. of the IEEE, Vol. 9 [3] V. Majidzadeh et al. “A (256x256 ) /Compressor Based on Real-Time InP Int. Symp. on Circuits and Systems (IS C [4] Y. Oike, A. El Gamal. “CMOS Im a ADC and Programmable Compressed State Circuits, Vol. 48, No. 1, pp. 318 - [5] A. Elenyan, K. Kose, A. Cetin. “ I Compressive Sensing”. I mage Pr o Challenges 5, pp. 177-184, Springer. 2 [6] M. Davenport, et al. “The Smashed Fil t and Target Recognition”. Proc. SPIE , 6498, pp. 64980H , San Jose, Californ i [7] B. Gardiner. Compressive Image Fe Folding. Master thesis. Massachusetts I [8] P. Nagesh and B. Li. “A Com p Expression-Invariant Face Recognitio n Vision and Pattern Recognition, pp. 15 [9] L. Liu, P. Fieguth. “Texture Classific a Canadian Conf. Comp. and Robot Visi o [10] M. Antonini, M. Barlaud, P. Mathie u Using Wavelet Transform”. I EEE Tr a Vol. 1, No. 2, pp. 205-220, Apr. 1992. [11] C. Harris, M. Stephens, “A Combin e P roc. of the 4th Alvey Vision Conferen c [12] S. Becker, J. Bobin, E. Candès. “N E Order Method for Sparse Recovery” No. 1, pp. 1–39. Jan 2011. method is that, to actually the two derivatives are h e computational load to the w ork at the sensor plane. O NS features can be naturally s ing framework. We have c ompressed samples from n structed, without having to A s the relevant points in a h fewer than the number of c ompressed samples that are d er a targeted accuracy is e vidence has been obtained c tion of Harris corners from r ated with derivative masks e tter results. The study the a tures to be translated into a subject of further research. G MENT y the Spanish Government - C02 MINECO (European F /FEDER), IPT-2011-162509 CDTI (ERDF/FEDER), ect TIC 2338-2013 CEICE arch (USA) through grant E S e ssive Sampling”. IEEE signal p p. 15-20. March, 2008. W akin. “Lo w -Dimensional Models Signal Recovery: A Geometric 9 8, No. 6, pp. 959-971, Jun 2010. ) Pixel 76.7mW CMOS Imager P ixel Compressive Sensing”. IEEE C AS), pp. 2956-2959, May 2010. ge Senso r With Per-Column Ȉǻ Sensing”. IEEE Journal of Solid- - 328, Jan. 2013. I mage Feature Extraction Using o cessing and Commun i cations 2 014. t er for Compressive Classification Computational Imaging V, Vol. i a, January 2007. e ature Extraction by Means of I nstitute of Tech. June 2012. p ressive Sensing Approach for n ”. IEEE Conference on Computer 18-1525, June 2009. a tion using Compressed Sensing”. o n (CRV), pp. 71-78 June 2010. u , I. Daubechies. “Image Coding a nsactions on Image Processing, e d Corner and Edge Detectio n ”. c e, pp. 147-151, 1988. E STA: a Fast and Accurate First- . SIAM J. Imaging Sci., Vol. 4, 692