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)
{
Bitmap bmp = (Bitmap)Src.Clone();
int NumRow = pictureBox1.Height;
int numCol = pictureBox1.Width;
Bitmap mask = new Bitmap(pictureBox1.Width, pictureBox1.Height);
int bnd=3;
for (int i = 0; i < NumRow; i++)
{
for (int j = 0; j < numCol; j++)
{
Color c = bmp.GetPixel(j, i);
int rd = c.R; int gr = c.G; int bl = c.B;
if ((rd > 220) && (gr < 80) && (bl < 80))
{
Color c2 = Color.FromArgb(255, 255, 255);
mask.SetPixel(j, i, c2);
for (int ib = i - bnd; ib < i + bnd; ib++)
{
for (int jb = j - bnd; jb < j + bnd; jb++)
{
try
{
mask.SetPixel(jb, ib, c2);
}
catch (Exception ex)
{
}
}
}
}
else
{
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)
{
Bitmap bmp = srcBmp;
int NumRow = srcBmp.Height;
int numCol = srcBmp.Width;
Bitmap lbp = new Bitmap(numCol, NumRow);
Bitmap GRAY = new Bitmap(pictureBox1.Width, pictureBox1.Height);
double[,] MAT = new double[numCol, NumRow];
double max = 0.0;
for (int i = 0; i < NumRow; i++)
{
for (int j = 0; j < numCol; j++)
{
MAT[j, i] = 0;
if ((i > R) && (j > R) && (i < (NumRow - R)) && (j < (numCol - R)))
{
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;
if (nbrPixel > acPixel)
{
vals.Add(1);
}
else
{
vals.Add(0);
}
}
}
}
catch (Exception ex)
{
}
double d1 = Bin2Dec(vals);
MAT[j, i] = d1;
if (d1 > max)
{
max = d1;
}
}
}
}
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++)
{
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()
{
Bitmap mask = (Bitmap)pictureBox4.Image;
int NumRow = pictureBox1.Height;
int numCol = pictureBox1.Width;
Rslt = (Bitmap)pictureBox1.Image;
Bitmap src = (Bitmap)pictureBox3.Image;
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);
int rd = c.R; int gr = c.G; int bl = c.B;
int ti = -1, tj = -1;
double dst = 99999999999999.0;
if ((rd == 255) && (gr == 255) && (bl == 255))
{
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);
int rd1 = c1.R; int gr1 = c1.G; int bl1 = c1.B;
Color c2 = mask.GetPixel(j1, i1);
int rd2 = c2.R; int gr2 = c2.G; int bl2 = c2.B;
if ((rd2 == 0) && (gr2 == 0) && (bl2 == 0))
{
if (Nbrs.Count == 0)
{
Nbrs.Add(new int[] { i1, j1 });
}
else
{
double d = 0;
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;
if (d < dst)
{
dst = d;
ti = i1;
tj = j1;
}
}
}
}
catch (Exception ex)
{
}
}
}
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
gasshopper.iics is a group of like minded programmers and learners in codeproject. The basic objective is to keep in touch and be notified while a member contributes an article, to check out with technology and share what we know. We are the "students" of codeproject.
This group is managed by Rupam Das, an active author here. Other Notable members include Ranjan who extends his helping hands to invaluable number of authors in their articles and writes some great articles himself.
Rupam Das is mentor of Grasshopper Network,founder and CEO of Integrated Ideas Consultancy Services, a research consultancy firm in India. He has been part of projects in several technologies including Matlab, C#, Android, OpenCV, Drupal, Omnet++, legacy C, vb, gcc, NS-2, Arduino, Raspberry-PI. Off late he has made peace with the fact that he loves C# more than anything else but is still struck in legacy style of coding.
Rupam loves algorithm and prefers Image processing, Artificial Intelligence and Bio-medical Engineering over other technologies.
He is frustrated with his poor writing and "grammer" skills but happy that coding polishes these frustrations.