# Image Interpolation using Sparse Matrix Representation

DOI : 10.17577/IJERTV4IS020434

Text Only Version

#### Image Interpolation using Sparse Matrix Representation

Ms. V. Dhanalakshmi

PG Scholar

Computer Science and Engineering Sri Ramakrishna Institute of Technology

Coimbatore-641010, India

Dr. K. Sankaranarayanan

Computer Science and Engineering Sri Ramakrishna Institute of Technology

Coimbatore- 641010, India

Abstract Super Resolution is the process of transforming a low resolution image into a high resolution image. Image Interpolation is a technique which is used in super resolution which is used to find the missing pixels in the given image. Adaptive algorithm is used in this paper to interpolate the missing pixels. In this work an image with noise and blur is taken and processed to achieve high resolution image. Image is represented as sparse matrix. Sparse matrix needs special algorithms and data structures to implement it. In this, work an image is divided into overlapping patches and each patch is processed to remove the noise and blur and the pixels are processed and the optimal pixel value is taken from the dictionary. The dictionary is updated K-SVD (K means clustering singular value decomposition) algorithm. Thus the robustness of the image is achieved by increasing the weights of the pixels which results in better resolution of the image.

KeywordsSuper Resolution, Sparse Matrix, K-SVD.

1. Types of Interpolation Algorithms

Interpolation algorithm can be grouped into two categories such as Adaptive interpolation algorithm and Non-Adaptive interpolation algorithm.

2. Sparse Matrix

Sparse matrix is a special way of representing the image in a matrix format. In sparse matrix, most of the elements are zero. This reduces the unwanted processing of the pixel values. In this processing of the specific patch in an image is easy because it processes the pixel values only which need updating/ alteration.

Sparse matrix needs a special data structures and algorithms to store the images. Generally a matrix can be stored in a two dimensional array. The storage of an m Ã— n matrix consumes more memory when compared to storing sparse matrix.

3. Storing a Sparse Matrix

Matrix is stored as a two dimensional array. Each entry in the array represents an element aij in the matrix .The format

1. INTRODUCTION

1. Image Processing

Image processing is a domain where an image is given as the input and output may be a processed image or the parameters related to that image. Image processing is one form of Signal processing and it encompasses the fundamental theory, applications and algorithms and the implementations by means of heuristics, sparse, linguistics and modelling. It helps to process the image under various metrics and produces the output to the users.

2. Interpolation

Interpolation is a process of estimating the values of pixels at the unknown points by processing the pixels at the known value. A common approach used for implementing interpolation is by dividing the image into overlapping patches and to treat each patches based on the natural image patches. Applications of Interpolation includes processing of image and video data, digital camera- color interpolation scheme(CCD sensor), printers, internet and web browsers, flat panel imaging, medical science data and videophone.

of storing the sparse matrix can be divided into two groups such as

1. Those support efficient modification such as

Dictionary of keys (DOK), List of lists (LIL) and Co- ordinate list (COO).

2. Those support efficient access and matrix operations such as Compressed sparse row (CSR) and Compressed sparse column (CSC).

2. LITERATURE SURVEY

Several papers have been published in the development of image interpolation and various aspects of it are taken into consideration according to the perspective of the author. Some of the papers have been discussed here.

Collaborative filtering developed by [1] is a special procedure developed to deal with 3D groups. Due to the similarity between the grouped fragments, the transform can achieve a highly sparse representation of the true signal so that the noise can be separated by shrinkage and also retains the original features of an individual element.

Nonlocal means (NLM) algorithm developed by [1] to achieve the super resolution reconstruction of an image which was development on the inspiration made in video denoising.

1. Introduction

3. EXISTING SYSTEM

Nonlocal Block Matching 3D filter developed by [2] which is used to suppress the ringing and reconstruct missing datas.

The implementation of soft decision interpolation scheme developed by [3] that estimates the missing pixels. The new interpolation approach preserves the spatial coherences of the images better than the existing methodologies used. Edges and textures are well preserved and the ringing artifacts are greatly reduced. Soft decision adaptive algorithm (SAI) is proposed in this work and this work is used with the natural integration of piecewise 2D autoregression modelling and block estimation achieves super resolution.

An algorithm for solving image inverse problems was framed by [4] with piecewise linear estimations. The framework is based on the Gaussian mixture models which are estimated via a posteriori expectation maximum algorithm. The proposed algorithm is suggested to improve the sparse estimation and yields the results faster than the traditional sparse representations. This algorithm yields better results when used for deblurring.

An algorithm called robust super resolution method [5] was used to transform a low resolution image into a high resolution by regularization method and with fixed parameters. The super resolution algorithm helps to produce the high resolution image from the set of noisy and blurred images.

Cubic convolution interpolation is a new technique developed by [6] for resampling the discrete data. With the

Super resolution is the process of reconstructing a high resolution (HR) image from an observed low resolution (LR). Typical applications include zoom in of still images in digital cameras, scaling up an image before printing, interpolating images to adapt their size to high resolution screens and conversion from low-definition video to high-resolution video.

As described in [9] image interpolation is a special case of single image super resolution where the LR image is assumed to be a decimated version of a HR image.

The general linear equation is

y Ax b

(1)

The value of the variable b is the amount of noise/ blur which is contained in the image. The value of b is assumed to be small and it is neglected. The simplest way to reconstruct x is by the linear interpolation. Many complex algorithms are used for this. One among them is Sparse land modelling.

Sparse land model assumes that each patch in an image can be well represented in the form of linear combinations of few elements (atom) from the dictionary set. The original image is considered to be generated from xi Di . D is the

dictionary which has the elements D Rnm .The

i

Rm is a sparse vector of co efficient.

1. Sparse Representations And Dictionary Learning

appropriate boundary conditions and constraints on the interpolation kernel, the order of the accuracy of the cubic interpolation can be set between the linear interpolation and

The recovery of

i from

xi can be obtained from

that of the cubic splines.

A number of image denoising lgorithms and also the

min

i

i

i 0

s.t D

i xi

2

(2)

Nonlocal means (NLM) described in [7] which addresses the

Where the notation

i 0

stands for the count of the

preservation of structure in the digital image. The nonlocal smoothing methods and the frequency domain filters helps to

nonzero entries in i and is an a-priori error threshold.

i i1

reduce the noise and the reconstruction of the main geographical configurations.

Adapting the dictionary D to a set of signals x N

result in

Clustering the signals was developed [8] by means of probabilistic subspace clustering where signals are represented by means of atoms and it is represented in matrix form and the subspace is estimated by means of maximum likelihood. This methodology yields better results when facial images, pictures and the synthetic data are taken as inputs

a sparser representation than the one which would be based on a pre-chosen dictionary. K-means singular value decomposition (K-SVD) dictionary learning algorithms adapt D to the signals by approximating the solutions to the minimization problem.

Among the papers published in super resolution of an

min

N

2

D,ii1

Di xi 2

(3)

image some papers have been discussed here. The techniques such as collaborative filtering, techniques for interpolation such as PAR, robust super resolution and the Interpolation techniques can be used to achieve high resolution image is are shown.

i s.ti Suppai Suppa

i

i

Where Suppa are the indices of the non-zero rows in

a

i

.This process is iterated several items performing pursuit

to update the dictionary. Since dictionary learning is limited in handling low dimensional signals, the treatment of an image is typically done by breaking the image into small over lapping patches, forcing it to comply with the sparse representation model as discussed by [9] K-SVD denoising algorithm which

divides the image overlapping patches is used. Then the algorithm performs iterations of sparse coding using

N

min

Di R x 2 s.t, y U x

(4)

Orthogonal Matching Pursuit (OMP) followed by dictionary update sequence.

The overlapping patches are processed and the similar patches are processed using OMP and the optimal value from the dictionary is taken and replaced with the missing pixel to achieve better resolution in as image.

2. Proposed Algorithm

1. First Stage

Single image interpolation can be viewed as the need to fill the missing pixels in the desired HR image. Those image patches are characterized by having sparse representations with respect to the learned dictionary and with known pixels in the image. The representations are approximated by a weighted variant of the Orthogonal Matching Pursuit (OMP) the dictionary D is updated using the weighted variant of the K-SVD. The output HR image is computed by solving the minimization equation.

L

i W

i1 i

x

by means of the above equation HR patches are averaged followed by the simple projection of the known pixels.

Simultaneous sparse coding (SOMP) method which forces similar patches to have similar decomposition in the chosen atoms. SOMP is variant of the OMP; it is iterative greedy algorithm that finds one atom at a time for the representation of group. Given a of similar patches and a dictionary, in the first iteration SOMP finds the atom that best fits the group of waited patches. In the next iterations, given the previously found atoms, it finds the next one that minimizes the sum of weighted atoms. SOMP is the modified pursuit which was described by [1].

Dictionary update is done by using the element wise- weighted variant of the K-SVD which given in equation (5)

N

N

N

arg min

D R x

N

2

D R x 2

D ,

a ,

i i 1

A

i i 1

:

i 1

i i 2

i 1 jS

Strong i

i j W

i , j

(5)

s . ts . t Suppa Supp i A sp i i r i

2. Second Stage

To generate a robust and reliable HR image by refining x est .From the approximated pixels from the first stage the weights are increased and thus the pixels with better quality are obtained. To obtain a reliable estimation, the use of self-similarities in the second stage is made more conservative than the first stage.

3. Performance Of Existing System With Proposed Algorithm

The proposed algorithm is checked for its efficiency and robustness with various other super resolution methodologies such as SAI, Non autoregressive modelling and the proposed algorithm has achieved better results. The weights are increased constantly in first and the second stage for the interpolation values L=2 and L=3.

Table 1 Comparison between the two stages of the proposed algorithm

 Images L=2 L=3 Genera l I stage II stage General I stage II stage Bears 28.42 25.25 28.57 25.35 25.71 25.71 Boat 29.44 29.62 30.18 26.15 26.72 26.84 Lena 34.29 34.06 34.87 30.60 31.04 31.21 Butterfl y 28.88 26.31 26.68 23.88 25.07 25.27

The table depicted above shows the results for the interpolation factors such as L=2 and L=3. The restoration of

elements from the basis set. Each patch xi

in the image is

the image is efficient in this proposed algorithm.

generated from the

xi Di

where

D Rnm

is a

1. Features

4. PROPOSED SYSTEM

dictionary composed of atoms. Hence, sparse based restorations algorithms seek a dictionary and sparse representations that bring the corrupted and the degraded patch to be as close as possible to the original one

Super resolution of an image is achieved by means of image interpolation through which the missing pixels can be estimated. The image is represented in the form of a matrix and the processing of the pixel values are made in order to achieve the super resolution. Sparse matrix implementation is made in order to reduce the memory and processing power.

The enhancement of the existing system is done by

.

1. Simultaneous Orthogonal Matching Pursuit

In the proposed system element-wise weighted variant of the Simultaneous Orthogonal Matching Pursuit(SOMP) given by [12] and the K-SVD described by [13]algorithms are implemented. The linear equation for this system is given as

processing the images which contains both noise and blur. From the noisy and blurred image the sparse representation of

y UL x v

(6)

the image is taken and processed to interpolate the missing pixels to achieve the HR image from the noisy image. The noisy and the blur image is processed and restored in relation to the single image interpolation where deblurring is followed by the interpolation. In these cases interpolation addresses the first stage. Several works leverage the assumption to solve the image restoration problems such as denoising which is suggested by [1] and [10], deblurring described by [2] and

1. and the super resolution f the images are done by [7] and

2. in these works they assume that each patch in the image can be well represented using a linear combination of the few

Here v represents the additive noise present in the system which is eliminated.

2. Dictionary Updation

The algorithms such as NAM suggested by [14],SAI and PAR given by [3] and the robust super resolution algorithm given by [5] which discusses the approaches for the denoising and the deblurring process, the joint weighted sparse coding is done as

N

N

N

arg min

D R x

N

2

D R x 2

D ,

a ,

i i 1

A

i i 1

:

i 1

i i 2

i 1 jS

Strong i

i j W

i , j

(7)

s . ts . t Suppa Supp i A sp i i r i

using a joint element-wise weighted SOMP algorithm. Within an HR patch the number of known pixels and their location varies according to its location in the image. For each patch of

x est ,a set up to k most similar strong patches to

x est is

sorted . The dictionary D is updated using the element wise weighted variant of the K-SVD.

3. Methodologies To Be Included

In the proposed system the work is proceeded in order to achieve a high resolution image. Image interpolation is done by means of Adaptive Non local algorithm described in [9]and the denoising and deblurring is done. The dictionary should be set in order to substitute in the missing pixel. The dictionary should be populated in order to substitute the optimal pixel in the existing methodologies decimated version of the image is taken to populate the dictionary. In the proposed work denoising is implemented by means of NLM filter as discussed in [14] and the signaling of the atoms is done periodically by means of considering different positions and angles of an image and by doing shearing, scaling, grey scale and the mirror image and the matrix values are computed, processed and stored in the dictionary. The optimal pixel value is taken by means of SOMP.

4. System Analysis

In the construction of sparse matrix, first the matrix representation of an image is constructed and from that, sparse matrix is constructed. The matrix representation for an given image, grey scale and mirror image of an image, and the image from the random pixel input in order to populate the dictionary and to create the resulting image from the atoms.

Figure 4.1 Image to be represented in matrix

Figure 4.1 contains an image which is to be represented in matrix. Figure 4.2 contains the pixel values for the corresponding image using bitmap() and color(). For an image either whole portion of it can be represented in matrix form or values can be particular for a particular color.

Figure4.2 Matrix representation of an image

Figure4.3 Mirror image

In the above Figure 4.3 mirror image of an image is created to populate the dictionary and each pixel will be processed when any missing pixels in an image is to be filled up. Likewise grey scale of an image can be created and stored and also different scaling can be applied to an image to increase the dictionary size which will help to find the optimal pixel when the image is processed in overlapping patches.

Figure4.4 Image created from pixels.

In the Figure 4.4 From the processed pixels the image can be obtained and they are matched with the bitmap function and the image can be reconstructed.

5. CONCLUSIONS AND FUTURE WORK

In the proposed system the matrix representation of an image and also the ways through which the dictionary can be populated are done. The difference between the values between an noisy and blur image with that of image with no noise and blur is obtained. On these works the further works can be done and the algorithms will also be implemented. Based upon the results obtained from the previous chapters the following conclusions can be drawn:

Sparse matrix can be used for the processing of images efficiently. The dictionary can be dynamically updated by considering the decimated version of an image. Simultaneous Orthogonal Matching Pursuit can be used to find the optimal pixel from the image.

The work can be further extended in the following ways: The dictionary should be updated with n number of atoms for optimal pixel value retrieval. From the sparse matrix representation processing must be done. The algorithms to implement the simultaneous orthogonal matching pursuit should be done.

REFERENCES

1. Dabov K., Foi, V. Katkovnik A., and Egiazarian K.,(2007) Image denoising by sparse 3-D transform-domain collaborative ltering, IEEE Trans. Image Process., vol. 16, no. 8, pp. 20802095.

2. Danielyan A., Katkovnik V., and Egiazarian K., (2012)BM3D frames and variational image deblurring, IEEE Trans. Image Process., vol. 21, no. 4, pp. 17151728.

3. Zhang X., and Wu X.,(2008) Image interpolation by adaptive 2-D autoregressive modeling and soft-decision estimation, IEEE Trans. Image Process., vol. 17, no. 6, pp. 887896.

4. Gilboa G. and Osher S., (2007)Nonlocal linear image regularization and supervised segmentation, SIAM Multiscale Model. Simul., vol. 6, no. 2, pp. 595630.

5. Farsiu S., Robinson D., Elad M., and Milanfar P., (2013)Robust shift and add approach to superresolution, in Proc. SPIE Conf. Applications of Digital Signal and Image Processing.

6. Keys R., (1981)Cubic convolution interpolation for digital image processing, IEEE Trans. Acoust., Speech Signal Process., vol. 29, no. 6, pp. 11531160.

7. Bruckstein A.M., Donoho D.L., and Elad M., (2009)From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Rev., vol. 51, no. 1, pp. 348.

8. Alder A, Elad M, and Hel-Or Y,(2013) Probabilistic subspace clustering via sparse representations, IEEE Signal Process. Lett., vol. 20, no. 1, pp. 6366.

9. Yaniv Romano, Matan Protter, and Michael Elad,(2014) Fellow, IEEE. Single Image Interpolation via Adaptive Nonlocal Sparsity- Based Modeling.

10. Buades A, Coll B, and Morel J-M, (2005)A review of image denoising algorithms, with a new one, Multiscale Model., Simul., vol. 4, no. 2, pp. 490530.

11. Kindermann S., Osher S., and Jones P.W., (2005)Deblurring and denoising of images by nonlocal functionals, Multiscale Model., Simul., vol. 4, no. 4, pp. 10911115.

12. Tropp J. G., Gilbert A. C, and Strauss M. J,(2006) Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit, Signal Process., vol. 86, no. 3, pp. 572588.

13. Aharon M., Elad M., and Bruckstein A.,(2006) K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Trans. Signal Process., vol. 54, no. 11, pp. 43114322.

14. Protter M., Elad M., Takeda H., and Milanfar P.,(2009) Generalizing the nonlocal-means to super-resolution reconstruction, IEEE Trans. Image Process., vol. 18, no. 1, pp. 3651.