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.

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

But I need this:

Any way this can be solved?

This is the first image without the axes if you want to give it a try:

Answer 1

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:

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:

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):

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 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()