ppt - University of Patras, Computer Vision Group

Report
SPARSE REPRESENTATIONS
APPLICATIONS ON COMPUTER VISION AND PATTERN
RECOGNITION
Computer Vision Group
Electronics Laboratory
Physics Department
University of Patras
www.upcv.upatras.gr
www.ellab.physics.upatras.gr
November 2012
Ilias Theodorakopoulos
PhD Candidate
Περίληψη


Sparse Representation - Formulation
Sparse Coding
 Matching
Pursuits (MPs)
 Basis Pursuits (BPs)


Dictionary Learning
Applications
Sparse Representation
Formulation
D
 x

M in 

0
s .t . x  D 
Sparse Representation
Formulation
x  D
Dictionary Learning Problem
Sparse Coding Problem
Sparse Coding (1/2)
Matching Pursuits
 “Greedy” approaches. One dictionary element is selected
in each iteration
• Step 1: Find the element that best represents the input signal..
• Next Steps: Find the next element that best represents the input
signal among the rest of dictionary elements…
 The procedure is terminated when the representation error
becomes smaller than a threshold value OR the maximum
number of dictionary elements are selected
 Improved approaches: Orthogonal Matching Pursuit (OMP),
Optimized OMP (OOMP)
Sparse Coding (2/2)
Basis Pursuits
Instead of:
M in 

0
s .t . x  D 
Solve:
M in 

• Convex relaxation of the initial Sparse Representation
problem
• Can be efficiently solved using linear
programming
• When the solution of the initial problem is
sparse enough, solving the linear problem is a
good approximation
1
s .t . x  D
Dictionary Learning
X
D

M in
D ,A
DA  X
2
F
s .t .
A
 j, 
j
0
 L
Dictionary Learning
Different approaches
Dictionary
Initialization

Hard Competitive

Only the selected dictionary
atoms are updated

Sparse Coding
Bruckstein (‘04) ]
Using MP or BP approaches

Soft Competitive

Dictionary Update
KSVD [ Aharon, Elad &
All dictionary atoms are
updated based on a ranking

Sparse Coding Neural Gas
(SCNG) [ Labusch, Barth &
Martinetz (’09) ]
Applications
•
•
•
Image Processing
Computer Vision
Pattern Recognition
Image Restoration
20%
50%
80%
[M. Elad, Springer 2010]
Denoising
Source
Result 30.829dB
Dictionary
PSNR  22.1dB
Noisy image
[M. Elad, Springer 2010]
[J. Wright, Yi Ma, J. Mairal, G. Sapiro, T.S. Huang, Y.
Shuicheng, 2010]
Compression
Original
JPEG
JPEG
2000
PCA
K-SVD
15.81
13.89
10.66
6.60
14.67
12.41
9.44
5.49
15.30
12.57
10.27
6.36
550 bytes per
image
Bottom:
RMSE values
[O. Bryta, M. Elad, 2008]
Compressive Sensing
Reconstruction
based on classical
techniques
Reconstruction based
on simultaneous
learning of Sparse
dictionary and
Sensing Matrix
[J. Wright, Yi Ma, J. Mairal, G. Sapiro, T.S. Huang, Y. Shuicheng, 2010]
Face Recognition
[I. Theodorakopoulos, I. Rigas, G. Economou, S. Fotopoulos, 2011]
Classification
[J. Wright, A.Y. Yang, A. Ganesh, S.S. Sastry, Yi Ma, 2009]
Classification of Dissimilarity Data
[I. Theodorakopoulos, G. Economou, S. Fotopoulos, 2013]
Multi-Level Classification
[A. Castrodad, G. Sapiro, 2012]
L1Graph
•
•
Related to the Local Linear Reconstruction
Coefficients technique
The structure and the weights of the graph
are simultaneously generated
[S. Yan, H. Wang, 2009]
Applications:
 Spectral Clustering
 Label Propagation
L1 Graph – Label Propagation
[S. Yan, H. Wang, 2009]
Alternative Sparse-based Similarity Measures:
 Compute the sparse representation of each sample
using the C·D nearest samples as the dictionary
[H. Cheng, Z. Liu, J. Yang, 2009]
[S. Klenk, G. Heidemann, 2010]
Subspace Learning
Unsupervised
[L. Zhanga, P. Zhua, Q. Hub D. Zhanga, 2011]
Supervised
Joint Sparsity
Multiple Observations
[H.Zhang, N.M. Nasrabadi, mY. Zhang, T.S. Huang, 2011]
Joint Sparsity
Multiple Modalities
[X.T. Yuan, X. Liu, S. Yan, 2012]
References









O. Bryt and M. Elad, "Compression of facial images using the K-SVD algorithm," J. Vis. Comun. Image Represent., vol. 19, pp. 270-282, 2008.
A. Castrodad and G. Sapiro, "Sparse Modeling of Human Actions from Motion Imagery," International Journal of Computer Vision, vol. 100, pp. 1-15,
2012/10/01 2012.
J. M. Duarte-Carvajalino and G. Sapiro, "Learning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization,"
Image Processing, IEEE Transactions on, vol. 18, pp. 1395-1408, 2009.
M. Elad, Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing: Springer.
Z. Haichao, et al., "Multi-observation visual recognition via joint dynamic sparse representation," in Computer Vision (ICCV), 2011 IEEE International
Conference on, 2011, pp. 595-602.
C. Hong, et al., "Sparsity induced similarity measure for label propagation," in Computer Vision, 2009 IEEE 12th International Conference on, 2009,
pp. 317-324.
Z. Lei, et al., "A linear subspace learning approach via sparse coding," in Computer Vision (ICCV), 2011 IEEE International Conference on, 2011, pp.
755-761.
G. H. Sebastian Klenk, "A Sparse Coding Based Similarity Measure," DMIN 2009, pp. 512-516, 2009.
I. Theodorakopoulos, et al., "Face recognition via local sparse coding," in Computer Vision (ICCV), 2011 IEEE International Conference on, 2011, pp.
1647-1652.

E. G. Theodorakopoulos I., Fotopoulos S., "Classification of Dissimilarity Data via Sparse Representation," in ICPRAM 2013, 2013.

S. Y. a. H. Wang, "Semi-supervisedlearning by sparse representation," SIAM Int. Conf. Data Mining, pp. 792–801, 2009.



J. Wright, et al., "Robust Face Recognition via Sparse Representation," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 31, pp.
210-227, 2009.
J. Wright, et al., "Sparse Representation for Computer Vision and Pattern Recognition," Proceedings of the IEEE, vol. 98, pp. 1031-1044, 2010.
Y. Xiao-Tong and Y. Shuicheng, "Visual classification with multi-task joint sparse representation," in Computer Vision and Pattern Recognition (CVPR),
2010 IEEE Conference on, 2010, pp. 3493-3500.
Thank You
Questions

similar documents