Research of Multi-focus Image Fusion Algorithm Based on Sparse Representation and Orthogonal Matching Pursuit - Advances in Image and Graphics Technologies - page 59

This essay raises orthogonal matching pursuit algorithm to solve formula 2 and
then to realize the reconstruction of the signal. Orthogonal matching pursuit algorithm
is the improvement of matching pursuit algorithm which is an intuitive iterative
greedy algorithm for the minimizing model to solve, whose basic idea is to give a
more complete dictionary database and make the signal approach gradually shown.
During the process of each approach, orthogonal matching pursuit algorithm screens
atoms through orthogonal matching. It is a greedy algorithm that tends to find out the
most relevant atom to the residual signal of D in each iteration, solve the
corresponding value of x , and finally update the residual signal. The algorithm
flowchart is as shown in figure 1:



Initializing x ,

0
x =0.



Initializing the residual signal,

0 0

r =− = y xy .

{ }



Initializing the support set of x , ʴ

0

= Support x

0

= ˆ .

Iterative process ( k is the current iterative time):
 Finding the most relevant column to

1 r −

in D : j

*

= arg max D (:, j ) ' ∗ r −

k 1

j

{ }

 Updating support set:

ʴʴ −

k

=

k 1

 j

*

2
2

{ }

 Solving

x

k

: min yD − x

k

, subject to Suppo r tx

k

= ʴ

k

. k

x

 Updating the residual signal r

k

: r

k

=− y r

k

.

2
2

 Convergence condition: if

r

k

< ʵ , stop.

Fig. 1. OMP Algorithm Flowchart

One can obtain the over-complete dictionary in the algorithm by using over-
complete DCT dictionary or K-SVD dictionary learning algorithm. The K-SVD
dictionary learning algorithm is based on singular value decomposition for sparse
representation proposed by Mallat in 2006. Its algorithm is as the followings: firstly
initialize a dictionary D , and solve the sparse coefficient X by sparse representation
algorithm; then remain the position of non-zero values in solved sparse coefficient X ,
to calculate the new D and X by SVD (singular value decomposition). The following
mathematical formula can be described:
(

)



2

()

2

argmin Xi (:, ) ʻ+− DDX , subject to Di :, = 1 (3)

DX ,

i F

0 2

2.2 Algorithm Implementation

Image Sparse Representation. In the specific process of algorithm implementation,
one needs to divide an image of WH when

using sparse representation for image processing. That means that the image can be
overlapped with the upper-left corner of a small window to be nn

× into overlapping image blocks of nn ×

in itself when
taking the first image block; then the small window moves one pixel to the right, and
the second image block can be received. Until it can't move to the right, the small

×