Introduction

Firstly image inpainting is nothing new. It is a technique for object removal from images and image restoration. Any area in the image that you mark should be replaced by neighboring pixels or block of pixels in such a way that the overall image looks homogeneous.

However some of the papers presented in this direction, presents the problem in more complicated ways than they should have been. I have searched through internet for some suitable Inpainting technique written in C#. But I could not manage to find one. So I am writing this simple yet effective inpainting technique. It is written completely in C# code. We have not used any external libraries or functionality. So the code may be rough and unoptimized. But you can get an overview of Inpainting technique none the less.

Background

Bertalmio had proposed the first known inpainting technique using laplacian diffusion. There are several other methods like FOE, Exemplar based method proposed by Criminasi and so on. Basically image inpainting techniques are divided into two categories: Structure Inpainting and Texture Inpainting.

A structure is a pattern where all the pixels are of same color for example the image of clear sky or a building wall. A texture is however a pattern created by set of pixels where pixels in the blocks have different colors but overall blocks represents a definitive pattern. For example an image of our hear or tiles of the floor.

Using the code

In this work we will try to implement a simple image inpainting technique which performs both structure as well as texture inpainting based on LBP based texture representation and measurements.

Figure 1: Impainting Problem in General

Observe this figure. Consider that the central pixel needs to be inpainted. How will you do it? You can not fill it with gree or blue color. A human perspective would be to paint it with red color block.

How did you perceived the idea? It is quite simple . You looked around the other pixels in the neighbours and you determined the most frequently appearing pixel and you suggest the same for inpainting.

So from human perspective we can simplify the inpainting problem as:

1) Find the set of pixels to be inpainted. Let us assume image Im be the image of the same size as the original image Is but having 1's at every pixel positions which needs to be filled and 0's other wise.

2) Loop through every pixel in Im and check if current pixel is 1, if so the pixel in the same position in original image needs to be filled. Define a block of Size N. Observe the first image. Here block size is one. Because there are one pixel at every possible direction from the central pixel.

3) Retrieve a subimage of size (2N+1)*(2N +1) from Is by gathering pixels from all neighbourhood of the pixel to be inpainted. Leave out the defective or inpaint pixel(The centre one).

Now any of these pixels can replace the centre pixel. But the question is which one? So replace one pixel and check homogeneity. Homogeneity can be calculated as mean color distance of all the neighbours from centre when centre is replaced with any of the pixels from the neighbours.

So Let us first See how to Generate the mask

  Bitmap ObtainMask(Bitmap Src)
        {

            //1.  Take a local image bmp which we will use for mark scanning
            Bitmap bmp = (Bitmap)Src.Clone();
            int NumRow = pictureBox1.Height;
            int numCol = pictureBox1.Width;
            //2. Mask image is initially an image of the same size of source
            Bitmap mask = new Bitmap(pictureBox1.Width, pictureBox1.Height);// GRAY is the resultant matrix 
            //3. We will define a structuring element of size bnd for dilating the mask
            // You can obtain this mask thickening variable from user. but 3 is standard for 256x256 images
            int bnd=3;
            //4. Loop through the rows and columns of images
            for (int i = 0; i < NumRow; i++)
            {
                for (int j = 0; j < numCol; j++)
                {
                    Color c = bmp.GetPixel(j, i);// Extract the color of a pixel 
                    int rd = c.R; int gr = c.G; int bl = c.B;// extract the red,green, blue components from the color.
                    // Note that you had painted the region with red. But image is resized, which is resampling
                    // in resizing process, the color tend to get changed. so we will look for more redish pixels rater than red.
                    //you can also update this by picking the mask color through mouse click.
                    if ((rd > 220) && (gr < 80) && (bl < 80))
                    {
                        Color c2 = Color.FromArgb(255, 255, 255);
                        //5. set the marked pixel od Is as white in Im
                        mask.SetPixel(j, i, c2);

                        //6. Perform dilation( extending the mask area to nullify edge effect
                        for (int ib = i - bnd; ib < i + bnd; ib++)
                        {
                            for (int jb = j - bnd; jb < j + bnd; jb++)
                            {
                                try
                                {
                                    // see we are making the boundary of pixels also white
                                    mask.SetPixel(jb, ib, c2);
                                }
                                catch (Exception ex)
                                {
                                }
                            }
                        }
                    }
                    else
                    {
                        //7. all other pixels are black
                        Color c2 = Color.FromArgb(0, 0, 0);
                        mask.SetPixel(j, i, c2);
                        try
                        {

                        }
                        catch (Exception ex)
                        {
                        }
                    }
                }
            }
            return mask;
        }

One of the simplest form of similarity measure is calculate difference as sum of R,G,B difference of the pixels. But as we defined, a texture may contain pixels of different colors in a definitive way. If you check colors, it is plain and simple structure inpainting. So we will go a step further to define a texture pattern using Local binary pattern. Further this texture representation is extracted from Gray scale image. So we need to convert the image to gray scale first.

Here is the algorithm for LBP:

1) Define a window size W

2) Scan every pixel in an image, extract its WxW neighbourhood.

3) Check if a Neighbour pixel color > Center, if so put 1 in the matrix else 0

4) thus we get an array of '1' s and '0's . Convert this to binary and subsequently binary needs to be converted to decimal and must replace the center pixel. Remember bigger the value of W, larger will be number. for example for W=4, you will get a binary number of 16 bits. But gray scale image can contain only 8 bit colors. Therefore once entire image's LBP is extracted, it is to be normalized.

5) Normalization is performed as ( Image containing local binary pattern)*255/(maximum value in the image)

Important thing is if you take W=1, resultant image will be fine edge detected image. So you can alternatively use this theory to extract edges from images.

Bitmap LBP(Bitmap srcBmp,int R)
        {
            // We want to get LBP image from srcBmp and window R
            Bitmap bmp = srcBmp;
            //1. Extract rows and columns from srcImage . Note Source image is Gray scale Converted Image
            int NumRow = srcBmp.Height;
            int numCol = srcBmp.Width;
            Bitmap lbp = new Bitmap(numCol, NumRow);
            Bitmap GRAY = new Bitmap(pictureBox1.Width, pictureBox1.Height);// GRAY is the resultant matrix 
            double[,] MAT = new double[numCol, NumRow];
            double max = 0.0;
            //2. Loop through Pixels
            for (int i = 0; i < NumRow; i++)
            {
                for (int j = 0; j < numCol; j++)
                {
                  //  Color c1=Color.FromArgb(0,0,0);
                    MAT[j, i] = 0;
                    //lbp.SetPixel(j, i,c1) ;
                    
                    
                    //define boundary condition, other wise say if you are looking at pixel (0,0), it does not have any suitable neighbors
                    if ((i > R) && (j > R) && (i < (NumRow - R)) && (j < (numCol - R)))
                    {
                        // we want to store binary values in a List
                        List<int> vals = new List<int>();
                        try
                        {
                            for (int i1 = i - R; i1 < (i + R); i1++)
                            {
                                for (int j1 = j - R; j1 < (j + R); j1++)
                                {
                                    int acPixel = srcBmp.GetPixel(j, i).R;
                                    int nbrPixel = srcBmp.GetPixel(j1, i1).R;
                                    // 3. This is the main Logic of LBP
                                    if (nbrPixel > acPixel)
                                    {
                                        vals.Add(1);
                                    }
                                    else
                                    {
                                        vals.Add(0);
                                    }
                                }
                            }
                        }
                        catch (Exception ex)
                        {
                        }
                        //4. Once we have a list of 1's and 0's , convert the list to decimal
                        // Also for normalization purpose calculate Max value
                        double d1 = Bin2Dec(vals);
                        MAT[j, i] = d1;
                        if (d1 > max)
                        {
                            max = d1;
                        }
                        }
                    
                    //////////////////
                    
                    
                }
            }
            //5. Normalize LBP matrix MAT an obtain LBP image lbp
            lbp = NormalizeLbpMatrix(MAT, lbp, max);
            return lbp;
        }

The normalization code goes as bellow.

 Bitmap NormalizeLbpMatrix(double[,]Mat,Bitmap lbp,double max)
        {
            int NumRow = lbp.Height;
            int numCol = lbp.Width;
            for (int i = 0; i < NumRow; i++)
            {
                for (int j = 0; j < numCol; j++)
                {
                    // see the Normalization process of dividing pixel by max value and multiplying with 255
                    double d = Mat[j, i] / max;
                    int v = (int)(d * 255);
                    Color c = Color.FromArgb(v, v, v);
                    lbp.SetPixel(j, i, c);
                }
            }
            return lbp;
        }

Right than, We have a Source image Is, a LBP image Ib and mask image Im.

We will go to our main algorithm and modify third point in that algorithm as bellow.

1) Extract a pixel p at position (x,y) from mask, check if it '1'

if so , extract a subimage S from Ib around p over area (x-B:x+B,y-B:y+B) where B is Block Size.

compare each pixel of S with all other pixel of S. find pixel Ps for which difference is minimum. So pixel Ps is the pixel whose color needs to be put in p.

Map ps in Is, extract Is(ps) and put it in the place of Is(p). Continue this for entire image. You are done!

So Let us have a look at Inpaint function

void Inpaint()
        {
            //1. Obtain Mask
            Bitmap mask = (Bitmap)pictureBox4.Image;
            int NumRow = pictureBox1.Height;
            int numCol = pictureBox1.Width;
            //2. Define resultant image same as source region. As algo proceeds, we need to replace the marked blocks
            
            Rslt = (Bitmap)pictureBox1.Image;// GRAY is the resultant matrix 
            Bitmap src = (Bitmap)pictureBox3.Image;
            //3. Define the block for Inpainting purpose
            int Blk = int.Parse(textBox2.Text);
            for (int i = 0; i < NumRow; i++)
            {
                for (int j = 0; j < numCol; j++)
                {
                    Color c = mask.GetPixel(j, i);// Extract the color of a pixel from mask (p) 
                    int rd = c.R; int gr = c.G; int bl = c.B;// extract the red,green, blue components from the color.
                    int ti = -1, tj = -1;
                    double dst = 99999999999999.0;
                    //4. check if the pixel is white ( that means marked pixel in source)
                    if ((rd == 255) && (gr == 255) && (bl == 255))
                    {
                        //5. Generate the neighbors List
                        List<int[]> Nbrs = new List<int[]>();
                        for (int i1 = i - Blk; i1 < i + Blk; i1++)
                        {
                            for (int j1 = j; j1 < j + Blk; j1++)
                            {
                                try
                                {
                                    Color c1 = src.GetPixel(j1, i1);// Extract the color of a pixel from LBP image 
                                    int rd1 = c1.R; int gr1 = c1.G; int bl1 = c1.B;// extract the red,green, blue components from the color.
                                    Color c2 = mask.GetPixel(j1, i1);// Extract the color of a mask pixel 
                                    // remember list can not contain a pixel which also is within mask region
                                    int rd2 = c2.R; int gr2 = c2.G; int bl2 = c2.B;// extract the red,green, blue components from the color.
                                    // form the list with non marked pixel
                                    if ((rd2 == 0) && (gr2 == 0) && (bl2 == 0))
                                    {
                                        // add first pixel as it is, as there is nothing to compare for
                                        if (Nbrs.Count == 0)
                                        {
                                            Nbrs.Add(new int[] { i1, j1 });
                                        }
                                        else
                                        {
                                            double d = 0;
                                            //6. calculate mean distance of the current pixel with all neighbors
                                            for (int k = 0; k < Nbrs.Count; k++)
                                            {
                                                int[] pos = Nbrs[k];
                                                d = d + Math.Abs(Rslt.GetPixel(pos[1], pos[0]).R - rd2);
                                            }
                                            d = d / (double)Nbrs.Count;
                                            // 7. update ps value which will be used to replace p in original image
                                            if (d < dst)
                                            {
                                                dst = d;
                                                ti = i1;
                                                tj = j1;
                                            }
                                        }
                                    }
                                }
                                catch (Exception ex)
                                {
                                }
                            }
                        }
                        //8. replace p with ps in the actual image
                        Rslt.SetPixel(j, i, Rslt.GetPixel(tj, ti));
                        System.Threading.Thread.Sleep(10);
                    }
                    else
                    {
              
                    }
                }
            }


            s = "DONE";
        }

Note that inpaint process typically takes large time. Larger image size can really take hours to complete. So you need to call the function from a thread and periodically update the resultant picturebox display. It helps you to see that inpainting is happening.

This is how inpainting is performed in iterations

Points of Interest

Distance measure that I implemented here is simple. However a better result is obtainable if we change the distance measure. d=(Cnm+Cmn+1)/(Cmm+Cnn+1) where Cnm is the cost of nth pixel with respect to mth pixel in the inpainting would be a good choice. Your suggestions are welcome.

History

Version V1.0 published on 16-9-2012

Image Inpainting Technique using Local Binary Pattern based Texture Inpainting