2.Efficient Implementation of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit
R.Rubinstein,M.Zibulevsky and M.Elad,Computer science dep,Technion, Isarel Institute of technology, 2008
The goal of K-SVD algorithm is to improve the initial dictionary to achieve sparser representation of the signals by solving the optimization problem. It involves two steps: the signals are sparse coded given the current dictionary estimate thus producing sparse representation matrix. The second step involves updating the dictionary atoms for the sparse representation. The dictionary atoms are updated one at a time, thereby the target function for each atom is optimized individually while the rest is fixed. Batch-OMP is suited for sparse coding of large sets of signals over a single dictionary, and it combines the techniques for OMP acceleration with a new contribution to allow its use with error-driven signal processing tasks.
Advantage is that single iteration is enough to provide close results for the full computation.
Software: http://www.cs.technion.ac.il/~ronrubin/archive.html
Advantage is that single iteration is enough to provide close results for the full computation.
Software: http://www.cs.technion.ac.il/~ronrubin/archive.html
Results for MATLAB code
This demo reads an image, adds random Gaussian noise, and denoises the image
using K-SVD denoising. The function displays the original, noisy, and denoised
images, and shows the resulting trained dictionary.
Available test images:
1. barbara.png
2. boat.png
3. house.png
4. lena.png
5. peppers.png
Image to denoise (1-5): 4
Generating noisy image...
Performing K-SVD denoising...
KSVD training...
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 1 / 20 complete, mean atomnum = 0.8616
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 2 / 20 complete, mean atomnum = 0.7914
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 3 / 20 complete, mean atomnum = 0.7436
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 4 / 20 complete, mean atomnum = 0.7164
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 5 / 20 complete, mean atomnum = 0.6972
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 6 / 20 complete, mean atomnum = 0.6671
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 7 / 20 complete, mean atomnum = 0.6443
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 8 / 20 complete, mean atomnum = 0.6252
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 9 / 20 complete, mean atomnum = 0.6119
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 10 / 20 complete, mean atomnum = 0.6032
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 11 / 20 complete, mean atomnum = 0.5966
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 12 / 20 complete, mean atomnum = 0.5893
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 13 / 20 complete, mean atomnum = 0.5839
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 14 / 20 complete, mean atomnum = 0.5794
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 15 / 20 complete, mean atomnum = 0.5753
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 16 / 20 complete, mean atomnum = 0.573
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 17 / 20 complete, mean atomnum = 0.5703
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 18 / 20 complete, mean atomnum = 0.5666
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 19 / 20 complete, mean atomnum = 0.5645
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 20 / 20 complete, mean atomnum = 0.5632
OMP denoising...
ompdenoise: iteration 255025 / 255025, estimated remaining time: 00:00:00.00
using K-SVD denoising. The function displays the original, noisy, and denoised
images, and shows the resulting trained dictionary.
Available test images:
1. barbara.png
2. boat.png
3. house.png
4. lena.png
5. peppers.png
Image to denoise (1-5): 4
Generating noisy image...
Performing K-SVD denoising...
KSVD training...
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 1 / 20 complete, mean atomnum = 0.8616
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 2 / 20 complete, mean atomnum = 0.7914
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 3 / 20 complete, mean atomnum = 0.7436
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 4 / 20 complete, mean atomnum = 0.7164
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 5 / 20 complete, mean atomnum = 0.6972
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 6 / 20 complete, mean atomnum = 0.6671
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 7 / 20 complete, mean atomnum = 0.6443
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 8 / 20 complete, mean atomnum = 0.6252
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 9 / 20 complete, mean atomnum = 0.6119
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 10 / 20 complete, mean atomnum = 0.6032
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 11 / 20 complete, mean atomnum = 0.5966
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 12 / 20 complete, mean atomnum = 0.5893
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 13 / 20 complete, mean atomnum = 0.5839
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 14 / 20 complete, mean atomnum = 0.5794
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 15 / 20 complete, mean atomnum = 0.5753
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 16 / 20 complete, mean atomnum = 0.573
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 17 / 20 complete, mean atomnum = 0.5703
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 18 / 20 complete, mean atomnum = 0.5666
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 19 / 20 complete, mean atomnum = 0.5645
omp: signal 40000 / 40000
updating atoms: iteration 256/256
Iteration 20 / 20 complete, mean atomnum = 0.5632
OMP denoising...
ompdenoise: iteration 255025 / 255025, estimated remaining time: 00:00:00.00