Tricky filling holes in an image
Question: I need to fill holes in images using python. This is the image with objects
that I managed to get - they are really edges of objects I want, so I need to
fill them. [![enter image description
here](http://i.stack.imgur.com/IpauJ.png)](http://i.stack.imgur.com/IpauJ.png)

It seemed very straightforward using `ndimage.binary_fill_holes(A)`, but the
problem is that it produces this (manually filled with red colour):

[![enter image description
here](http://i.stack.imgur.com/koNd2.png)](http://i.stack.imgur.com/koNd2.png)

But I need this:

[![enter image description
here](http://i.stack.imgur.com/kO9x0.png)](http://i.stack.imgur.com/kO9x0.png)

Any way this can be solved?

This is the first image without the axes if you want to give it a try:
[![enter image description
here](http://i.stack.imgur.com/9JiQB.png)](http://i.stack.imgur.com/9JiQB.png)


Answer: I think I have found a solution. It is a little bit lengthy since I ran out of
time, but maybe it helps. I have coded if for this problem only, but it should
be easy to generalize it for many images.

Some naming conventions first:

  * I define "first level regions" as compact regions which are enclosed by the backround. Such first level regions may consist of different subregions.
  * A first level region which consists of more than one subregion is called a critical region.

My basic idea is to compare the lengths of the contours of two subregions
which are part of one critical region. However, **I do not compare their
complete contour length, but only the segment which is close to the
background**. The one with the shorter contour segment close to the background
is considered a hole.

I'll start with the result images first.

Some overview of what we are talking about, vizualizing the naming conventions
above:

[![enter image description
here](http://i.stack.imgur.com/DLwtM.png)](http://i.stack.imgur.com/DLwtM.png)

The two subregions of the critical region. The two border segments of each of
the regions which are close to the background are marked in different colours
(very thin, blue and dark red, but visible). These segments are obviously not
perfect ("thin" areas cause errors), but sufficient to compare their length:

[![enter image description
here](http://i.stack.imgur.com/9QfrG.png)](http://i.stack.imgur.com/9QfrG.png)

The final result. In case that you want to have the hole "closed", let me
know, you just have to assign the original black contours to the regions
instead of to the background ([EDIT] I have included three marked lines of
code which assign the borders to the regions, as you wished):

[![enter image description
here](http://i.stack.imgur.com/aBSVN.png)](http://i.stack.imgur.com/aBSVN.png)

Code is attached here. I have used the OpenCV contour function which is pretty
straigthforward, and some masking techniques. The code is legthy due to its
visualizations, sorry for its limited readability, but there seems to be no
two line solution to this problem.

Some final remarks: I first tried to do a matching of contours using sets of
points, which would avoid loops and allow the use of set.intersection to
determine the two contour segments close to the background, but since your
black lines are rather thick, the contours are sligthly mismatched. I tried
skeletonization of contours, but that opened another can of worms, so I worked
with a dump approach doing a loop and calculation distance between contour
points. There may be a nicer way to do that part, but it works.

I also considered using the [Shapely](https://pypi.python.org/pypi/Shapely
"Shapely") module, there might be ways gaining some advantage from it, but I
did not find any, so I dropped it again.

    
    
    import numpy as np
    import scipy.ndimage as ndimage
    from matplotlib import pyplot as plt
    import cv2
    
    
    img= ndimage.imread('image.png')
    
    # Label digfferentz original regions
    labels, n_regions = ndimage.label(img) 
    print "Original number of regions found: ", n_regions
    # count the number of pixels in each region
    ulabels, sizes = np.unique(labels, return_counts=True)
    print sizes
    
    # Delete all regions with size < 2 and relabel
    mask_size = sizes < 2
    remove_pixel = mask_size[labels]
    labels[remove_pixel] = 0
    labels, n_regions = ndimage.label(labels) #,s)
    print "Number of regions found (region size >1): ", n_regions
    # count the number of pixels in each region
    ulabels, sizes = np.unique(labels, return_counts=True)
    print ulabels
    print sizes
    
    
    # Determine large "first level" regions
    first_level_regions=np.where(labels ==1, 0, 1)
    labeled_first_level_regions, n_fl_regions = ndimage.label(first_level_regions)
    print "Number of first level regions found: ", n_fl_regions
    
    
    # Plot regions and first level regions
    fig = plt.figure()
    a=fig.add_subplot(2,3,1)
    a.set_title('All regions')
    plt.imshow(labels, cmap='Paired', vmin=0, vmax=n_regions)
    plt.xticks([]), plt.yticks([]), plt.colorbar()
    a=fig.add_subplot(2,3,2)
    a.set_title('First level regions')
    plt.imshow(labeled_first_level_regions,  cmap='Paired', vmin=0, vmax=n_fl_regions)
    plt.xticks([]), plt.yticks([]), plt.colorbar()
    
    
    for region_label in range(1,n_fl_regions):
        mask= labeled_first_level_regions!=region_label
        result = np.copy(labels)
        result[mask]=0    
        subregions = np.unique(result).tolist()[1:]
        print region_label, ": ", subregions
    
        if len(subregions) >1:
            print "   Element 4 is a critical element: ",  region_label
            print "   Subregions: ", subregions
    
            #Critical first level region
            crit_first_level_region=np.ones(labels.shape)
            crit_first_level_region[mask]=0
    
            a=fig.add_subplot(2,3,4)
            a.set_title('Crit. first level region')
            plt.imshow(crit_first_level_region, cmap='Paired', vmin=0, vmax=n_regions)
            plt.xticks([]), plt.yticks([])
    
            #Critical Region Contour
            im = np.array(crit_first_level_region * 255, dtype = np.uint8)
            _, contours0, hierarchy = cv2.findContours( im.copy(), cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
            crit_reg_contour = [contours0[0].flatten().tolist()[i:i+2] for i in range(0, len(contours0[0].flatten().tolist()), 2)]
            print crit_reg_contour
            print len(crit_reg_contour)
    
    
    
            #First Subregion
            mask2= labels!=subregions[1] 
            first_subreg=np.ones(labels.shape)
            first_subreg[mask2]=0
    
            a=fig.add_subplot(2,3,5)
            a.set_title('First subregion: '+str(subregions[0]))
            plt.imshow(first_subreg, cmap='Paired', vmin=0, vmax=n_regions)
            plt.xticks([]), plt.yticks([])        
    
            #First Subregion Contour
            im = np.array(first_subreg * 255, dtype = np.uint8)
            _, contours0, hierarchy = cv2.findContours( im.copy(), cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
            first_sub_contour = [contours0[0].flatten().tolist()[i:i+2] for i in range(0, len(contours0[0].flatten().tolist()), 2)]
            print first_sub_contour
            print len(first_sub_contour)
    
    
    
    
            #Second Subregion
            mask3= labels!=subregions[0]
            second_subreg=np.ones(labels.shape)
            second_subreg[mask3]=0
    
            a=fig.add_subplot(2,3,6)
            a.set_title('Second subregion: '+str(subregions[1]))
            plt.imshow(second_subreg, cmap='Paired', vmin=0, vmax=n_regions)
            plt.xticks([]), plt.yticks([])      
    
            #Second Subregion Contour
            im = np.array(second_subreg * 255, dtype = np.uint8)
            _, contours0, hierarchy = cv2.findContours( im.copy(), cv2.RETR_TREE, cv2.CHAIN_APPROX_NONE)
            second_sub_contour = [contours0[0].flatten().tolist()[i:i+2] for i in range(0, len(contours0[0].flatten().tolist()), 2)]
            print second_sub_contour
            print len(second_sub_contour)   
    
    
            maxdist=6
            print "Points in first subregion close to first level contour:"
            close_1=[]
            for p1 in first_sub_contour:
                for p2 in crit_reg_contour:
                    if (abs(p1[0]-p2[0])+abs(p1[1]-p2[1]))<maxdist:
                        close_1.append(p1)
                        break
    
            print close_1
            print len(close_1)
    
            print "Points in second subregion close to first level contour:"
            close_2=[]
            for p1 in second_sub_contour:
                for p2 in crit_reg_contour:
                    if (abs(p1[0]-p2[0])+abs(p1[1]-p2[1]))<maxdist:
                        close_2.append(p1)
                        break
    
            print close_2
            print len(close_2)      
    
    
            for p in close_1:
                result[p[1],p[0]]=1
    
            for p in close_2:
                result[p[1],p[0]]=2
    
    
            if len(close_1)>len(close_2):
                print "first subregion is considered a hole:", subregions[0]
                hole=subregions[0]
            else:            
                print "second subregion is considered a hole:", subregions[1]
                hole=subregions[1]
    
    
            #Plot Critical region with subregions
            a=fig.add_subplot(2,3,3)
            a.set_title('Critical first level region with subregions')
            plt.imshow(result, cmap='Paired', vmin=0, vmax=n_regions)
            plt.xticks([]), plt.yticks([])
    
            result2=result.copy()
    
    
    #Plot result
    fig2 = plt.figure()
    a=fig2.add_subplot(1,1,1)
    a.set_title('Critical first level region with subregions and bordering contour segments')
    plt.imshow(result2, cmap='flag', vmin=0, vmax=n_regions)
    plt.xticks([]), plt.yticks([])
    
    
    #Plot result
    mask_hole=np.where(labels ==hole, True, False)
    labels[mask_hole]=1
    labels=np.where(labels > 1, 2, 1)
    
    # [Edit] Next two lines include black borders into final result
    mask_borders=np.where(img ==0, True, False)
    labels[mask_borders]=2
    
    
    fig3 = plt.figure()
    a=fig3.add_subplot(1,1,1)
    a.set_title('Final result')
    plt.imshow(labels, cmap='flag', vmin=0, vmax=n_regions)
    plt.xticks([]), plt.yticks([])
    
    
    plt.show()
    

