Intrepid MathWorks application engineer Brett Shoelson recently got a user question that caught my attention. Consider an image containing text characters in outline form, such as this:
url = 'http://blogs.mathworks.com/steve/files/MathWorks-address-binary.png'; bw = imread(url); imshow(bw)
How can we fill in the text characters from their outlines without filling in the internal holes? If we just use imfill with the 'holes' option, you can see that it doesn't give us the desired result.
bw_filled = imfill(bw,'holes'); imshow(bw_filled) title('Original with holes filled')
When I saw this problem, I thought that some combination of imfill, imclearborder, and logical operators could possibly solve it.
You've already seen imfill. Here's how imclearborder works.
url_sample = 'http://blogs.mathworks.com/images/steve/168/aug31.png'; bw_sample = imread(url_sample); imshow(bw_sample) title('imclearborder demonstration - input image')
bw_sample_clearborder = imclearborder(bw_sample); imshow(bw_sample_clearborder) title('imclearborder demonstration - output image')
You can see that any connected component touching any image border has been removed.
Going back to our task, I'm going to proceed first by identifying the background pixels that are inside the text characters. Roughly speaking, I'll tackle this phase by working "from the outside in."
First, let's identify and remove the pixels that are external to the characters.
bw2 = ~bw; imshow(bw2) title('Complement of original image')
bw3 = imclearborder(bw2); imshow(bw3) title('External pixels removed from the foreground')
Now let's complement the image and clear the borders again.
bw4 = ~bw3; imshow(bw4) title('Complement of bw3')
bw5 = imclearborder(bw4); imshow(bw5) title('After second border-clearing')
If we fill the holes in the image bw5 above, and then take the exclusive-or of the result with bw5 we'll be left only with the internal hole pixels inside the characters.
bw6 = imfill(bw5,'holes'); bw7 = xor(bw6,bw5); imshow(bw7) title('Internal hole pixels')
We're almost there. We can now use bw6 to "fix up" the initial filled result, bw_filled, using an exclusive-or operation.
bw_final = xor(bw_filled,bw7); imshow(bw_final) title('Presto!')
Readers, how would you solve this problem? Brett and I think there might be a couple of other reasonable approaches. Let us know in the comments.
Get the MATLAB code
Published with MATLAB® R2016b
7 CommentsOldest to Newest
Without changing the algorithm, each imclearborder(bw) can be replaced by imfill(bw,[1 1]). I guess that this simple flood fill executes much faster than the imclearborder, which contains several operations (padarray, imerode, imreconstruct).
Interesting problem! I’d use bwboundaries:
bw_filled = imfill(bw,'holes'); [~,L,~,A] = bwboundaries(bw); [i,j] = find(A); I = ismember(j,i); bw_filled(ismember(L,i(I))) = false; imshow(bw_filled)
Best regards, Wolfgang
Pierre’s comment intrigued me, so I tested his idea out. In fact, imfill(bw,[1 1]) is faster than imclearborder(bw)–by about 2.5 times. BUT…a) they do not produce the same results; and b) both imclearborder(bw) runs on these images in about 5 milliseconds. (It’s pretty fast!)
It’s likely that the imfill(bw,[1 1]) could be used to replace imclearborder, but not without changing the algorithm.
On the other hand, Wolfgang’s algorithm runs about 4 times faster than yours, and looks good. (The results are not identical; your approach masks inner holes from the inside borders of the interior regions, while Wolfgang’s approach masks from the outer borders of the interior regions. Both look good–just different!)
Incidentally, for the record: the algorithm that I shared with the customer who first asked this question produces a result that is identical to Wolfgang’s. The code was very similar, but slightly different:
[B,L,N,A] = bwboundaries(bw, 8, 'holes'); %# exclude inner holes [r,~] = find(A(:,N+1:end)); %# find inner boundaries that enclose stuff [rr,~] = find(A(:,r)); %# stuff they enclose idx = setdiff(1:numel(B), [r(:);rr(:)]); %# exclude both bw_filled = ismember(L,idx); %# filled image
But Wolfgang’s algorithm runs a tiny bit slower:
fcn1 = @() Wolfgang(bw); out1 = feval(fcn1); fcn2 = @() Brett(bw); out2 = feval(fcn2); isequal(out1,out2) % YES! tWolfgang = timeit(fcn1) % 0.021 seconds tBrett = timeit(fcn2) % 0.017 seconds
Intrepid Brett—Thanks for reporting on your experiments!
Fun little puzzle. I thought of lots of ways. Here is the way I programmed up:
lettersAndHoles = imclearborder(~initialBinaryImage);
holesOnly = imclearborder(imfill(lettersAndHoles, [1,1]));
filledLetters = imfill(initialBinaryImage, ‘holes’) & ~holesOnly;