9

Is there an algorithm that would perform well in terms of filling holes like those on the sample image? Dilation doesn't work well, cause before I eventually manage to connect ends of those curves, the curves get really thick. I'd like to avoid thickening the lines. Thank you for any help.

enter image description here

Yes, there can be just any letter or shape in the image with holes like those.

5
  • 2
    What about dilation with an erode afterwards. en.wikipedia.org/wiki/Closing_%28morphology%29.
    – Steffen
    Oct 27, 2014 at 11:26
  • 1
    If holes are smaller than gaps between objects you could first cluster segments to objects, which will make hole filling much easier (dilate for each object separately for example). Otherwise read about "Gestalt psychology"
    – Micka
    Oct 27, 2014 at 11:46
  • Have you considered using the Hough Transform to finish the completion of the lines? OpenCV does have the Hough Transform as part of the API: docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_lines/…
    – rayryeng
    Oct 27, 2014 at 17:08
  • There are not only lines though.
    – user107986
    Oct 27, 2014 at 17:43
  • 1
    @user107986 - No, of course not, but you can use the Hough transform to try and connect discontinuous regions together. FWIW, Mark Setchell has a very good algorithm (below) that is more or less what I would have thought of too.
    – rayryeng
    Oct 27, 2014 at 19:36

5 Answers 5

7

Another, simpler way, that will probably translate better into OpenCV as it uses convolution rather than sequential Perl/C code.

Basically set all the black pixels to value 10, and all the white pixels to value 0, then convolve the image with the following 3x3 kernel:

1  1  1
1  10 1
1  1  1

Now, a black pixel in the middle of the kernel will give 100 (10x10) and any other black pixel in the neighbourhood will give 10 (10x1). So if we want points that have a central black pixel with just one single adjacent black pixel, it will have a value of 110 (100+10). So let's colour all pixels that have the value 110 in with red. That gives this command:

convert EsmKh.png -colorspace gray -fill gray\(10\) -opaque black -fill gray\(0\) -opaque white -morphology convolve '3x3: 1,1,1 1,10,1 1,1,1' -fill red -opaque gray\(110\) out.png

with the resulting image (you may need to zoom in on gaps to see the red):

enter image description here

If you want a list of the red pixels, replace the output filename with txt: and search like this:

convert EsmKh.png -colorspace gray -fill rgb\(10,10,10\) -opaque black -fill rgb\(0,0,0\) -opaque white -morphology convolve '3x3: 1,1,1 1,10,1 1,1,1' txt: | grep "110,110,110"

which gives:

86,55: (110,110,110)  #6E6E6E  grey43
459,55: (110,110,110)  #6E6E6E  grey43
83,56: (110,110,110)  #6E6E6E  grey43
507,59: (110,110,110)  #6E6E6E  grey43
451,64: (110,110,110)  #6E6E6E  grey43
82,65: (110,110,110)  #6E6E6E  grey43
134,68: (110,110,110)  #6E6E6E  grey43
519,75: (110,110,110)  #6E6E6E  grey43
245,81: (110,110,110)  #6E6E6E  grey43
80,83: (110,110,110)  #6E6E6E  grey43
246,83: (110,110,110)  #6E6E6E  grey43
269,84: (110,110,110)  #6E6E6E  grey43
288,85: (110,110,110)  #6E6E6E  grey43
315,87: (110,110,110)  #6E6E6E  grey43
325,87: (110,110,110)  #6E6E6E  grey43
422,104: (110,110,110)  #6E6E6E  grey43
131,116: (110,110,110)  #6E6E6E  grey43
524,116: (110,110,110)  #6E6E6E  grey43
514,117: (110,110,110)  #6E6E6E  grey43
122,118: (110,110,110)  #6E6E6E  grey43
245,122: (110,110,110)  #6E6E6E  grey43
76,125: (110,110,110)  #6E6E6E  grey43
456,128: (110,110,110)  #6E6E6E  grey43
447,129: (110,110,110)  #6E6E6E  grey43
245,131: (110,110,110)  #6E6E6E  grey43
355,135: (110,110,110)  #6E6E6E  grey43
80,146: (110,110,110)  #6E6E6E  grey43
139,151: (110,110,110)  #6E6E6E  grey43
80,156: (110,110,110)  #6E6E6E  grey43
354,157: (110,110,110)  #6E6E6E  grey43
144,160: (110,110,110)  #6E6E6E  grey43
245,173: (110,110,110)  #6E6E6E  grey43
246,183: (110,110,110)  #6E6E6E  grey43
76,191: (110,110,110)  #6E6E6E  grey43
82,197: (110,110,110)  #6E6E6E  grey43
126,200: (110,110,110)  #6E6E6E  grey43
117,201: (110,110,110)  #6E6E6E  grey43
245,204: (110,110,110)  #6E6E6E  grey43
248,206: (110,110,110)  #6E6E6E  grey43
297,209: (110,110,110)  #6E6E6E  grey43
309,210: (110,110,110)  #6E6E6E  grey43

Now you can process the list of red points, and for each one, find the nearest other red point and join them with a straight line - or do some curve fitting if you are feeling really keen. Of course, there may be some refining to do, and you may wish to set a maximum length of gap-filling line.

2
  • The problem with your solution is that it detects loose ends in letter "B" which we don't need to find a pair for.
    – user107986
    Nov 2, 2014 at 17:20
  • That was the idea of my fine-tuning suggestion at the end of my answer. Nov 2, 2014 at 18:16
5

I had a little try at this. It may need some tweaking but it is an idea. My algorithm is as follows:

Find all black pixels that have exactly 1 black neighbouring pixel, colour it red and put it on a list of pixels at ends.

Go through list of all red pixels, and find nearest other red pixel and draw straight line between the two.

By the way, I only implemented the first part - gotta leave something for the reader to do ;-)

#!/usr/bin/perl
use strict;
use warnings;
use Image::Magick;
use Data::Dumper;

my $im=Image::Magick->new();
$im->Read('EsmKh.png');

my ($width,$height)=$im->Get('width','height');
my $out=Image::Magick->new();
$out->Read('EsmKh.png');

my @pixels;
# Iterate over pixels
for my $y (0..($height-1)){
   for my $x (0..($width-1)){
      my (@pixel) = split(/,/, $im->Get("pixel[$x,$y]"));
      $pixels[$x][$y]=$pixel[0];
   }
}

# Find black pixels that have precisely 1 black neighbour
for my $y (1..($height-2)){
   for my $x (1..($width-2)){
      next if $pixels[$x][$y]!=0;
      my $neighbours=0;
      for(my $i=$x-1;$i<=$x+1;$i++){
         for(my $j=$y-1;$j<=$y+1;$j++){
            $neighbours++ if $pixels[$i][$j]==0;
         }
      }
      $neighbours--;    # Uncount ourself !
      if($neighbours==1){
         $out->Set("pixel[$x,$y]"=>'red');
      }
   }
}
$out->Write(filename=>'out.png');

Result

You will have to zoom right in to see the red pixels...

enter image description here

Zoomed Image

enter image description here

1

After you get the thickened image, you can recover your "thin" shape using skeletonization. I found an implementation of skeletonization here.

If you want avoid too much thickening (as it distorts the image and parts of the shape merge together), use mild erosion and skeletonization alternatively until you get the holes filled.

1

Here is another solution using OpenCV/Python.

Solution:

The solution is divided into 2 parts:

  1. Find loose ends in all shapes. These are the disconnected points.
  2. Among these points, connect those that are closest among them.

Part 1: Finding loose ends

I am using the Hit-or-Miss transform to find loose ends in each shape. It is a morphological operation that looks for certain patterns in a binary image. Though it is an extension of the common erosion and dilation operations, the hit-or-miss operates differently. While the kernels in erosion/dilation look for overlapping foreground pixels, the hit-or-miss kernels look for overlapping foreground and background pixels. To understand in depth please visit this page

Each point/pixel is surrounded by eight other points. Every loose end is a point that is connected only to one of those eight points. We design a kernel each, to capture all the 8 variations.

1. One variation that can occur is when the end pixel is between 2 other pixels like the following:

1 --> foreground pixel (white pixel)

0 --> background pixel (black pixel)

|1 1 1|
|0 1 0|
|0 0 0|

|0 0 1|
|0 1 1|
|0 0 1|

|0 0 0|
|0 1 0|
|1 1 1|

|1 0 0|
|1 1 0|
|1 0 0|

2. Another variation is when the end pixel is at the end of a diagonal; like the following:

|0 0 0|
|0 1 0|
|1 0 0|

|1 0 0|
|0 1 0|
|0 0 0|

|0 0 1|
|0 1 0|
|0 0 0|

|0 0 0|
|0 1 0|
|0 0 1|

Part 2: Connecting disconnected points based on distance

After finding all the loose ends, in this step we iterate each point and connect it with the one closest to it. The closest distance in this case is the Euclidean distance.

Code:

img = cv2.imread('broken_shapes.png')
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)

# inverse binary image
th = cv2.threshold(gray, 0, 255, cv2.THRESH_BINARY_INV + cv2.THRESH_OTSU)[1]

# skeletonize 
sk = cv2.ximgproc.thinning(th, None, 1)  

# Kernels for each of the 8 variations
k1 = np.array(([0, 0, 0], [-1, 1, -1], [-1, -1, -1]), dtype="int")
k2 = np.array(([0, -1, -1], [0, 1, -1], [0, -1, -1]), dtype="int")
k3 = np.array(([-1, -1, 0],  [-1, 1, 0], [-1, -1, 0]), dtype="int")
k4 = np.array(([-1, -1, -1], [-1, 1, -1], [0, 0, 0]), dtype="int")

k5 = np.array(([-1, -1, -1], [-1, 1, -1], [0, -1, -1]), dtype="int")
k6 = np.array(([-1, -1, -1], [-1, 1, -1], [-1, -1, 0]), dtype="int")
k7 = np.array(([-1, -1, 0], [-1, 1, -1], [-1, -1, -1]), dtype="int")
k8 = np.array(([0, -1, -1], [-1, 1, -1], [-1, -1, -1]), dtype="int")               

# hit-or-miss transform
o1 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k1)
o2 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k2)
o3 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k3)
o4 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k4)
out1 = o1 + o2 + o3 + o4

o5 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k5)
o6 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k6)
o7 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k7)
o8 = cv2.morphologyEx(sk, cv2.MORPH_HITMISS, k8)
out2 = o5 + o6 + o7 + o8

# contains all the loose end points
out = cv2.add(out1, out2)

# store the loose end points and draw them for visualization
pts = np.argwhere(out == 255)
loose_ends = img.copy()
for pt in pts:
    loose_ends = cv2.circle(loose_ends, (pt[1], pt[0]), 3, (0,255,0), -1)

# convert array of points to list of tuples
pts = list(map(tuple, pts))

final = img.copy()

# iterate every point in the list and draw a line between nearest point in the same list
for i, pt1 in enumerate(pts):
  min_dist = max(img.shape[:2])
  sub_pts = pts.copy()
  del sub_pts[i]
  pt_2 = None
  for pt2 in sub_pts:
    dist = int(np.linalg.norm(np.array(pt1) - np.array(pt2)))
    #print(dist)
    if dist < min_dist:
      min_dist = dist   
      pt_2 = pt2
  final = cv2.line(final, (pt1[1], pt1[0]), (pt_2[1], pt_2[0]), (0, 0, 255), thickness = 2)

Results:

Result of loose_ends:

enter image description here

Result of final:

enter image description here

0

This is an OpenCV, C++ implementation of Mark Setchell's algorithm. It is very straightforward, uses the same kernel and convolutes the input image via the cv::filter2D function. I've, optionally, inverted the input image so target pixels have a value of 255:

//Read input Image
cv::Mat inputImage = cv::imread( "C://opencvImages//blobs.png", cv::IMREAD_GRAYSCALE );

//Invert the image:
inputImage = 255 - inputImage;

//Threshold the image so that white pixels get a value of 0 and
//black pixels a value of 10:
cv::threshold( inputImage, inputImage, 128, 10, cv::THRESH_BINARY );

Now, setup the kernel and convolute the image, like this:

//Set up the end-point kernel:
cv::Mat kernel = ( cv::Mat_<int>(3, 3) <<
  1, 1, 1,
  1, 10, 1,
  1, 1, 1
);

//Convolute image with kernel:
cv::filter2D( inputImage, inputImage, -1 , kernel, cv::Point( -1, -1 ), 0, cv::BORDER_DEFAULT );

The direct result of the convolution is this, pixels at the end points now have a value of 110, which can be seen (barely) in this output:

Let's threshold these pixels and overlay them on the original image. This is the result (pixels in red):

Additionally, the skeleton of the image can be computed at the beginning. The skeleton has a normalized line-width of 1 pixel. The function is part of the Extended Image Processing module of OpenCV:

#include <opencv2/ximgproc.hpp>

//Compute the skeleton of the input:
cv::Mat skel;
int algorithmType = 1;
cv::ximgproc::thinning( inputImage, skel, algorithmType ); 

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.