Review of Image Reconstruction by Interpolation Techniques

Review of Image Reconstruction by Interpolation Techniques

Ajit Kadam

Department of Electronics and Tele- Communication Engineering

Dr. Babasaheb Ambedkar Technological University, Lonere.

Lonere, India

Prof. S. V. Khobragade Department of Electronics and Tele- Communication Engineering

Dr. Babasaheb Ambedkar Technological University, Lonere.

Lonere, India

Dr. S. L. Nalbalwar

Department of Electronics and Tele- Communication Engineering

Dr. Babasaheb Ambedkar Technological University, Lonere.

Lonere, India

Abstract- image interpolation is very interesting areaof research in image processing which consists of various processing tasks such as compression, restoration, denoising, enhancement. Reconstruction quality of any image interpolation algorithm depends on its ability to adapt changing pixel structures across image. Interpolation is method of creating new data points from set of available or known data points which helps in analyzing exact details of images which is required in many applications such as medical imaging. By interpolation methods many artifacts in low resolution image such as blurring, ringing can be removed.

1. INTRODUCTION

   Image interpolation is very important task in medical imaging,remote sensing, digital photographs and satellite

2. INTERPOLATION TECHNIQUES

   A.BI-Cubic Interpolation

   This interpolation technique is extension of cubic interpolation used for obtaining high resolution (HR) image from low resolution (LR) counterpart or resampling of discrete data .This can be accomplished by using Lagranges polynomial or cubic splines or cubic interpolation algorithm.

   Interpolation function meet sampled data at sample points

   i.e. if A is sampled function and B is interpolation function,, we can write B(sk)=A (sk) where sk is sample points.If the sample points are equally apart from each other, we can write interpolation function as

   imaging where analysis require conversion from LR image to HR image to study minute details. So many image

   B(s)=

   C u

   k

   interpolation techniques were developed. In this work, we are going to review five image interpolation methods such as Bi-cubic interpolation,New edge directed interpolation(NEDI), interpolation via directional filtering and data fusion(DSDF, soft decision and adaptive 2-d autoregressive model(SAI), nonlocal autoregressive model(NARM). Bi-cubic interpolation method is simplest is having lower complexity among all but

   cannot reconstruct edge hence produces artifacts. NEDI improves visual quality of image by reconstructing edges however in case of multiple intersect it produces speckle interpolation noise. DSDF method reduces this speckle interpolation noise using minimum mean square error method when edge direction learned from LR image is not reliable. SAI method reduces most of visual defects associated with above methods. NARM method efficiently uses non-local neighboring pixels to construct HR image from LR counterpart.

   Where h is increment in samples equally apart from each other and sk are sample points, u kernel for bi-cubic interpolation, Ck are coefficients which depends on sampled data. u helps in converting discrete data into continuous. This cubic interpolation is achieved by constraining kernel.

   Lets consider u is contains piecewise polynomials defined in interval (-2,2).we can divide this interval into subintervals as (-2,-1),(-1,0),(0,1),(1,2). So we can write kernel u as follows

   u(x)= P1 x3 + Q1 x2 + R1 x + S1 0<x<1

   = P2x3 + Q2 x2 +R2x + S21<x<2

   = 0x<2

   This kernel must assume values u(0)=1,u(n)=0 i.e. u(1)=u(2)=0 this gives us following equations for coeff.1=u(0)= S1

   0=u(1-)=P1 + Q1+ R1+ S1

   0=u(1+)=P2 + Q2+ R2+ S2

   0=u(2-)=8P2 +4 Q2+ 2R2+ S2

   If we select P2, the interpolation function B matches with the original function A. Let P2 =p and determine remaining coeff. In terms of p using Taylors series expansion.

   So the interpolation kernel in terms of p becomes as follows

   u(x)= (p+2) x3 (p+3) x2 + 10<x<1

   =px3 -5 p x2 + 8p x – 4p1<x<2

   =0 x<2

   This interpolation technique can reconstruct any second- degree polynomial; however this method of interpolation fails catch varying statistics around edges so produce blurred HR images. Computational complexity of bi-cubic algorithm is low.

   1. New Edge Directed Interpolation(NEDI)

      For an ideal step edge, image intensity evolves faster across the edge orientation than along the edge orientation. As edges are important in images, reconstructing the geometry of edges is paramount in image processing. In this method first covariance coefficients of LR image are obtained. Then HR covariance coefficientsare obtained from LR covariance coefficients using geometrical similarity among them. By considering image as stationary Gaussian process, we can obtain interpolation by minimum mean square error method (MMSE). This improves visual quality of pixel around edges but this also increases computational complexity to high extent as compared to linear methods of interpolation.so mixed approach was proposed to tackle above problem. Covariance based method was employed for pixels around edges only and for other parts linear interpolation methods were used.

      Consider Xi,jbe the LR image and Y2i,2j be the HR image such that Xi,j= Y2i,2j. If we want to obtain

      Y2i+1,2j+1 , we will have to interpolate Xi,j i.e. in turn we will have to interpolate Y2i,2j. The interpolation function is given as follows which contains four nearest neighbor in diagonal direction.

      reconstructed image is improved. Since this method requires big window to calculate covariance coefficients for each missing pixel, this may introduce artifacts in local structure which causes faulty calculation of covariance

   2. Edge-Guided Image Interpolation via Directional Filtering and Data Fusion (DSDF)

      In this method, missing pixel is interpolated in two mutually orthogonal directions. These two different observations of missing pixels are combined using local window. Finally the pixel is interpolated by fusing two directional observations using linear minimum mean square error estimation.

      Lets assume Ih and Ilare the HR and LR images respectively. We are considering that LR image is directly down sampled from HR image. Hence we can write

      Il(n,m)= Ih(2n-1,2m-1) ,1nN,1mM

      Where N= no. of pixel rows in LR image, M=no. of pixel columns in LR image

      Fig.(a)

      Black dots represent available pixels of LR image and white dots represents missing pixels in HR image.

      As human eye is sensitive to edges, it is important to decrease effect of artifacts while maintaining edge sharpness. Direction of edge is important information in interpolation; to use this we partition neighboring pixels of each missing pixel into two directional (observational) subsets which are orthogonal to each other. In this method we reconstruct HR image in two steps. In first,we reconstruct center pixels like Ih(2n,2m) surrounded by four known and four unknown pixels. In fig.(b),there are two orthogonal directions ,one along 450 and other along 1350.

      Y2i+1,2j+1= 1 1

      2+ 2 + ,2( +)

      If we want to reconstruct missing pixel Ih(2n,2m), consider

      =0 =0

      two directional observations as (2n,2m) and (2n,2m)

      45 135

      Where represents interpolation coefficients and given by

      = R-1

      Where R and represents high resolution covariance

      Important applications of this algorithm are resolution enhancement of gray scale image and reconstruction of color images from CCD samples in which visual quality of

      by linear interpolation methods. Let the observations are as follows

      45(2n, 2m) =Ih(2n,2m) + v45(2n,2m)

      135(2n, 2m)=Ih(2n,2m) + v135(2n,2m)

      Fig.(b)

      Where v45 and v135 represents noise along two mutually orthogonal directions. We can combine above two observations in matrix form as follows:

      Y=1.Ih +V

      Where Y,1,V all are 2×1 matrices as follows.

      Where , is random perturbation independent of location of samples. Effectiveness of PAR model depends on how model parameters (m, n) matches with local pixel structures.

      Fig.(a)

      Y= 45

      , 1=1, V= 45

      135

      1 135

      Now we have to calculate value of Ih from observation Y. this can be achieved by use of linear minimum mean square estimation as follows

      Ih = + cov(Ih,Y)(Var(Y))-1 (Y-E[Y])

      Where is mean, cov stands for covariance, Var stands for variance, E stands for mean or expectation.

   3. Image Interpolation by Adaptive 2-D Autoregressive Modeling and Soft-Decision Estimation (SAI)

      In this method, value of missing pixels is calculated in group instead of one at a time like in NEDI, DSDF. Interpolation means to increase inborn resolution of thee image.

      The reconstruction capacity of any image interpolation algorithm depends on ability to adapt nonstationarypixel across image.In this method, natural image is taken as piecewise 2-D autoregressive process. Model parameters are measured for each sample using sample statistics of local window. Sample set should be causal for estimation of current sample.

      In this method first step is define piecewise autoregressive model (PAR). Then apply PAR model to soft-decision estimation technique for adaptive interpolation (SAI).

      According to PAR model, image can be represented as X(i,j) = , (m,n) X(i+m,j+n) + ,

      Fig.(b)

      Fig.(c)

      Fig. (a) shows solid black spots which represents LR image pixels, missing circles represents HR image pixels which are to be calculated

      Let Ihand Ilbe the HR, LR image respectively. From Fig.(a)

      , we can say that LR image is obtained by down sampling HR image by factor of two. Let xi ,yi belongs to LR,HR image respectively.

      By using Fig.(b) we can write yi= 14 at (8) +

      Images	Bi- cubic	NEDI	DSDF	SAI	NARM
      Lena	33.91	33.76	33.89	34.68	35.01
      	0.914	0.9134	0.9122	0.9184	0.9238
      	0.9872	0.9868	0.9867	0.9882	0.9893
      house	32.15	31.67	32.57	32.84	33.52
      	0.8772	0.8743	0.8775	0.8778	0.8841
      	0.9404	0.9434	0.9478	0.9496	0.9567
      leaves	26.85	26.23	27.22	28.72	29.76
      	0.9365	0.9403	0.9433	0.9575	0.9661
      	0.9259	0.9429	0.9478	0.9591	0.9674
      camera man	25.36	25.42	25.67	25.88	25.94
      	0.8639	0.8626	0.867	0.8709	0.8781
      	0.9041	0.9059	0.9143	0.9177	0.9231
      girl	33.83	33.85	33.79	34.13	34.46
      	0.8533	0.857	0.852	0.8588	0.8658
      	0.9416	0.9412	0.9395	0.9444	0.9434
      starfish	30.22	29.36	30.07	30.76	31.72
      	0.9169	0.8987	0.9118	0.9207	0.9299
      	0.9522	0.9458	0.9541	0.9577	0.9648

      With above model we can interpolate n missing pixels in given window by least squares block estimation with parameters at. similarly PAR model can be written by using parameters bt as follows

      yi= 14 bt(4) +

      while model parameters at equation

      and bt

      are using following

      =argminb 14 (4) 2

      Similarly for model parameters of at.

      This algorithm gives better results in terms of PSNR as compared to previous methods such ass bi- cubic,NEDI,DSDF.

   4. Sparse Representation Based Image Interpolation with Nonlocal Autoregressive Modeling (NARM)

   In this method, low resolution image (LR) is considered as down-sampled version of high resolution image (HR) after blurring. If we consider blurring kernel ass Dirac- delta function, this method becomes less effective as it fails to constrain local image structure. Soin this method we are adding nonlocal similarity of image into conventional sparse representation models(SRM). According to compressive sensing theory, dictionary should be less

   =arg

   (y-DS 2 +

   " +

   coherent with sampling matrix. So this newly proposed

   2

   2

   =1

   1

   algorithm (NARM) produces best result so far in terms of

   PSNR as well as SSIM, FSIM.

   General super-resolution algorithm can be modeled as y = DHx + v ,where y is observed(LR) image after blurring in original(HR) image x, v is additive noise, D is down- sampling factor, H is Dirac-delta function i.e. identity matrix. For reconstructing image x from observed image y can be through iterative back projection algorithm but it produces noisy image so regularization terms were added in that. Sparse representation model assumes that image x is sparse in some domain spanned by dictionary i.e. x . Here most of coefficients in are zero. Using 1 minimization model, SRM based model can be written as follows

   =1 ( ) 2 )

   By using variable splitting method, above problem can be solved by dividing it into smaller problems.

3. COMPARISON BETWEEN DIFFERENT INTERPOLATION TECHNIQUES

   So far we have discussed five interpolation techniques such as bi-cubic,NEDI, DSDF, SAI and NARM.

   Among all above, NARM gives best results in terms of PSNR,SSIM,FSIM as compared to others when applied on test images. Test images are Lena , house, girl, leaves, camera man, starfish as follows

   2

   =arg (y-DH 2 + 1 ).

   Once coding vector is obtained, x can be calculated with help of dictionary. In autoregressive modeling, given pixel is represented as linear combination of its local neighbors. While in NARM , nonlocal neighbors are taken into consideration and missing pixel is assumed to be equal to weighted sum off its nonlocal neighbors, hence equation for coding coefficients written as

   Lena Girl

   Starfish house

   Leaves camera man

   When BI-cubic, NEDI,DSDF,SAI,NARM methodsare applied to the above test images,we get results as shown in table.

   REFERENCES

   1. R. G. Keys, Cubic convolution interpolation for digital image process-ing, IEEE Trans. Acoust., Speech, Signal Process. , vol. 29, no. 6,pp. 11531160, Dec. 1981.

   2. X. Li and M. T. Orchard, New edge-directed interpolation, IEEE Trans. Image Process., vol. 10, no. 10, pp. 15211527, Oct. 2001.

   3. L. Zhang and X. Wu, An edge guided image interpolation algorithm via directional filtering and data fusion, IEEE Trans. Image Process. , vol. 15, no. 8, pp. 22262238, Aug. 2006.

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

   5. E. J. Candes and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Process. Mag. , vol. 25, no. 2, pp. 2130,

      Mar. 2008

   6. W. Dong, L. Zhang, R. Lukac and G. Shi , Sparse Representation Based Image Interpolation With Nonlocal Autoregressive Modeling,IEEE Trans. Image processing, vol. 22, no. 4, april 2013.

4. CONCLUSION

In this paper we have seen five different interpolation methods .Bi-cubic interpolation is having relatively lower complexity than others but it cannot reconstruct edges which creates artifacts such as ringing. Hence new method such as NEDI was developed which can reconstruct edges so that visual quality is good . SAI method eliminates most of visual defects associated with other methods.In SAI, estimation of model parameters assume that spatial co- relation between HR,LR pixels is same but if this assumption is wrong, this method produces some false edges or textures. NARM method uses non-local self- similarity between image patches or pixels to develop reconstruction algorithm which gives better results than other method.