{"id":1333,"date":"2015-06-17T11:44:25","date_gmt":"2015-06-17T15:44:25","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=1333"},"modified":"2019-11-01T11:42:05","modified_gmt":"2019-11-01T15:42:05","slug":"region-filling-and-laplaces-equation","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2015\/06\/17\/region-filling-and-laplaces-equation\/","title":{"rendered":"Region filling and Laplace’s equation"},"content":{"rendered":"

Today I want to show you how to use a linear system of 90,300 equations and 90,300 unknowns to get rid of a leaf.<\/p>

Earlier this month I told you<\/a> how the function roifill<\/tt> was recently renamed to regionfill<\/tt><\/a> to correct a functional design flaw. Now I want to follow up and talk about the algorithm underlying regionfill<\/tt>.<\/p>

This was one of my earliest algorithm projects at MathWorks. And it was my earliest lesson the power of sparse linear algebra in MATLAB. About 21 years ago, Clay Thompson, one of the two developers of version 1.0 of Image Processing Toolbox, commented to me one day that maybe we could \"erase\" objects in an image by treating it as a \"soap-film problem.\" (The other developer of that first toolbox version was Loren Shure<\/a>.)<\/p>

In other words, let's treat the pixel values surrounding the region we want to erase as heights of a closed loop of wire and then figure out the shape of a soap film bounded by that wire.<\/p>

That sounded plausible, so I looked into it. (The World Wide Web was barely a year old at the time, and there was nothing like the modern search engine, so I sought out information using what we used to call \"books.\")<\/p>

I found that, if you make some simplifying assumptions (such as no gravity), the soap film surface satisfies Laplace's equation:<\/p>

$$\\frac{\\delta^2 f}{\\delta x^2} + \\frac{\\delta^2 f}{\\delta y^2} = 0$$<\/p>

where the height of the wire loop around the region gives us the boundary conditions for the PDE.<\/p>

In a simple, discretized version of Laplace's equation, the value of every grid element in the interior of the region equals the average of its north, east, south, and west neighbors in the grid.<\/p>

Before I explore that idea further, though, let's look at some pictures to illustrate what we're trying to accomplish.<\/p>

Here is the \"trees\" image (in gray) with a region drawn around what looks like a small leaf.<\/p>

[X,map] = imread('trees.tif'<\/span>);\r\nI = im2double(ind2gray(X,map));\r\nimshow(I)\r\nx = [240 245 255 270 285 290 280 270 250 240];\r\ny = [155 165 170 173 172 166 161 155 153 155];\r\nhold on<\/span>\r\nplot(x,y,'y'<\/span>)\r\nhold off<\/span>\r\n<\/pre>\"\" 
Here's a zoomed-in view.<\/p>
axis([230 300 140 180])\r\n<\/pre>\"\" 
We are going to \"erase\" that leaf by filling in the pixels inside that region. The function poly2mask<\/tt> is useful for finding the set of pixels inside a polygonal region.<\/p>
mask = poly2mask(x,y,258,350);\r\nimshow(mask)\r\n<\/pre>\"\" 
Let's think about the gray-scale pixel values as heights and view the image as a surface.<\/p>
h = surf(I);\r\nh.EdgeColor = 'none'<\/span>;\r\nh.FaceColor = 'interp'<\/span>;\r\naxis ij<\/span>\r\nview(-10,80)\r\n<\/pre>\"\" 
Here's a close-up of the region we're interested in.<\/p>
xlim([230 300])\r\nylim([140 180])\r\n<\/pre>\"\" 
We can use the region mask computed above to \"cut out\" the part of the surface inside the region.<\/p>
h.FaceAlpha = 'interp'<\/span>;\r\nh.AlphaData = ~mask;\r\n<\/pre>\"\" 
A very simple approach to erasing the left would be to fill in the region with the mean value of pixels in the region. Here's how to do it. (I just love logical indexing with binary image masks!)<\/p>
J = I;\r\nJ(mask) = mean(I(mask));\r\nh.ZData = J;\r\nh.AlphaData = true(size(J));\r\n\r\ntitle('Region filled with mean value'<\/span>)\r\n<\/pre>\"\" 
imshow(J)\r\ntitle('Region filled with mean value'<\/span>)\r\n<\/pre>\"\" 
axis([230 300 140 180])\r\n<\/pre>\"\" 
Now let's work toward a solution based on Laplace's equation. I'm going to set up a linear system of equations, $Ax = b$, so that the solution gives me every pixel of the output image. I'll think of the pixels as being numbered in columnwise order from 1 to the total number of pixels. The trees image has 90,300 pixels, so this is going to be a 90,300 by 90,300 linear system! It's a good thing it'll be very sparse.<\/p>
For every pixel outside the masked region, the equation is simply the identity: output_pixel equals input_pixel.<\/p>
For every pixel inside the masked region, the pixel value should equal the average of the pixel values of its north, east, south, and west neighbors.<\/p>
First, number the pixels inside the masked region.<\/p>
u = find(mask);\r\n<\/pre>
Now number the pixels outside the region.<\/p>
w = find(~mask);\r\n<\/pre>
Using a technique I called \"neighbor indexing\" years ago<\/a>, we can find the north, east, and south, and west neighbors for all the pixels in the masked region this way:<\/p>
M = size(mask,1);\r\nu_north = u - 1;\r\nu_east = u + M;\r\nu_south = u + 1;\r\nu_west = u - M;\r\n<\/pre>
(Note: for the purpose of this blog post, I'm omitting code needed to handle the case where some mask pixels lie on the border of the image.)<\/p>
Next, construct a sparse matrix representing the linear system.<\/p>
v = ones(size(u));\r\nijv_mask = [...<\/span>\r\n    u  u         1.00*v\r\n    u  u_north  -0.25*v\r\n    u  u_east   -0.25*v\r\n    u  u_south  -0.25*v\r\n    u  u_west   -0.25*v ];\r\n\r\nijv_nonmask = [w  w  1.00*ones(size(w))];\r\n\r\nijv = [ijv_mask; ijv_nonmask];\r\nA = sparse(ijv(:,1),ijv(:,2),ijv(:,3));\r\n<\/pre>
What does the sparse linear system look like?<\/p>
spy(A)\r\n<\/pre>\"\" 
The right-hand vector, b<\/tt>, contains either the original pixel values (for pixels outside the mask) or 0 (for pixels inside the mask).<\/p>
b = I(:);\r\nb(mask(:)) = 0;\r\n<\/pre>
Finally we can solve the system!<\/p>
x = A\\b;\r\n<\/pre>
And then reshape the solution back into an image.<\/p>
J2 = reshape(x,size(I));\r\nimshow(J2)\r\n<\/pre>\"\" 
subplot(2,2,1)\r\nimshow(I)\r\naxis([230 300 140 180])\r\ntitle('Original'<\/span>)\r\n\r\nsubplot(2,2,2)\r\nimshow(J)\r\naxis([230 300 140 180])\r\ntitle('Region filled with mean'<\/span>)\r\n\r\nsubplot(2,2,3)\r\nimshow(J2)\r\naxis([230 300 140 180])\r\ntitle('Region filled using Laplace equation solution'<\/span>)\r\n<\/pre>\"\" 
Today, the process of filling image regions is often called \"inpainting.\" Many different inpainting algorithms have been published.<\/p>
I'll finish by confessing that I wrote an iterative solver for my first MATLAB implementation of this technique. When I showed my work to Cleve<\/a>, he said, \"Why don't you use sparse backslash?\"<\/p>
Oh! Lesson learned. Thanks, Cleve!<\/p>