Tricky filling holes in an image
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 npimport scipy.ndimage as ndimagefrom matplotlib import pyplot as pltimport cv2img= ndimage.imread('image.png')# Label digfferentz original regionslabels, n_regions = ndimage.label(img) print "Original number of regions found: ", n_regions# count the number of pixels in each regionulabels, sizes = np.unique(labels, return_counts=True)print sizes# Delete all regions with size < 2 and relabelmask_size = sizes < 2remove_pixel = mask_size[labels]labels[remove_pixel] = 0labels, n_regions = ndimage.label(labels) #,s)print "Number of regions found (region size >1): ", n_regions# count the number of pixels in each regionulabels, sizes = np.unique(labels, return_counts=True)print ulabelsprint sizes# Determine large "first level" regionsfirst_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 regionsfig = 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 resultfig2 = 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 resultmask_hole=np.where(labels ==hole, True, False)labels[mask_hole]=1labels=np.where(labels > 1, 2, 1)# [Edit] Next two lines include black borders into final resultmask_borders=np.where(img ==0, True, False)labels[mask_borders]=2fig3 = 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()