How to count objects depending on their number of holes

Question

I’m processing an image with shapes, and I’m trying to count the objects that have 1 hole and those who have 2.

I found information about it, but it was in MATLAB Segment out those objects that have holes in it They used the Euler characteristic, I know that in Python exist the skimage library, but I can't use it.

There’s some code I found too, but I can’t understand it. http://www.cis.rit.edu/class/simg782/homework/hw3/hw3solutions.pdf Page 16.

PRO hw3 4,A,LA,LC,count
;Find all the holes
Ac=A EQ 0
LC=label region(Ac,/ALL)
;Construct an array with the holes filled in
Afill=(A GT 0) OR (LC GT 1)
;Display the arrays
sa=size(A,/dim)
window,/free,xsize=sa[0],ysize=sa[1]
tvlct,rr,gg,bb,/get
tek color
TV,Afill
window,/free,xsize=sa[0],ysize=sa[1]
TV,LC
;Count the objects with holes. First we
;find all the objects and then match up
;the object labels and the hole labels.
LA=label region(Afill)
window,/free,xsize=sa[0],ysize=sa[1]
TV,LA
ha=histogram(LA)
ia=where(ha ge 0)
print,format=’("Objects",3x,"Count",/,(i2,5x,i7))’,$
[transpose(ia),transpose(ha[ia])]
;Each element of ia corresponds to a filled
;object. Object k is labeled ia[k]. For each
;object that is not background,
;determine whether it has holes.
c=0
print
print,"k ia[k] N C"
For k=1,n elements(ia)-1 DO BEGIN
B=bytarr(sa[0],sa[1]); Make an array with one object
ik=Where(LA eq ia[k]); ;Fill in the object
IF MIN(ik) GE 0 THEN B[ik]=1
;Now see if any of the object pixels match the
;hole image LC. Counts if one or more holes.
IF MAX(B AND (LC GT 0)) GT 0 THEN c++
print,[k,ia[k],n elements(ik),c],format=’(I2,1x,I2,3x,I5,2x,I1)’
END
Print,’Number of objects with one or more holes=’,count
tvlct,rr,gg,bb
END
IDL> hw3 4,A,LA,LC,count

The idea is to count the objects that have 1 hole, and those that have 2, and highlight their edges.

"Number of objects with one hole: 2"

"Number of objects with two holes: 4"

Here is what I have, I did it with a simple cv2.HoughCircles:

Answer 1

Contour Hierarchy can be used to count objects depending their number of holes. Imagine that you have 100 empty of boxes of various sizes, from a big refrigerator box to a small jewelry box. You want to store all 100 boxes, so you put some of the boxes inside other larger boxes. You also want to be able to find the boxes later, so you keep a list of which box is inside of which box. Contours work the same way, and this list is called a hierarchy.

To find the contours and the hierarchy:

img = cv2.imread('/home/stephen/Desktop/test.png', 0)
_, contours, hierarchy = cv2.findContours(img,cv2.RETR_CCOMP,cv2.CHAIN_APPROX_SIMPLE)

Next, iterate through each contour to find if it has any contours inside it

max_num = np.amax(hierarchy) +1
for c, h in zip(contours, hierarchy[0]):
    # If there is at least one interior contour, find out how many there are
    if h[2] != -1:
        # Make sure it's not the 'zero' contour
        if h[0] == -1:
            num_interior_contours = max_num - h[2]
        else: num_interior_contours = h[0]-h[2]
    else: num_interior_contours = 0

Draw or count the number of contours that have another contour inside:

if num_interior_contours == 1:
    cv2.drawContours(img_color, [c], -1, (255,0,255), 2)
# Outline the contour in green if there are two holes.
if num_interior_contours == 2:
    cv2.drawContours(img_color, [c], -1, (0,255,0), 2)

Answer 2

Well you could always implement the Euler characteristic yourself. Steve Eddins has an excellent post about it in his MathWorks blog. In there he cites Robot Vision, Berthold K. P. Horn, MIT Press, 1989., where the original author (apparently, can't access the source) demonstrates an O(n) way to compute the (4-connected) Euler characteristic. Then Eddins demonstrates how you can perform the same operation on multi-label images, along with a MATLAB code example.

Here's my Numpy conversion of his code along with some OpenCV to implement that hole counting you wanted:

import numpy as np
import cv2

def EulerNumbers(L):
    '''
    For a label matrix L containing nonnegative integers, returns a vector e
    such that e[k-1] is the 4-connected Euler number of the binary image (L ==
    k), from k = 1 to max(L).

    Adapted from:
    https://blogs.mathworks.com/steve/2014/10/02/lots-and-lots-of-euler-numbers/
    Accessed on 5.4.2019.
    '''

    Lp = np.pad(L, ((1,0), (1,0)), 'constant')

    I_NW = Lp[ :-1,  :-1];
    I_N  = Lp[ :-1, 1:  ];
    I_W  = Lp[1:  ,  :-1];

    is_upstream_convexity = np.logical_and(L,(L != I_N));
    is_upstream_convexity = np.logical_and(is_upstream_convexity, (L != I_NW));
    is_upstream_convexity = np.logical_and(is_upstream_convexity,  (L != I_W));

    is_upstream_concavity = np.logical_and(L,(L != I_NW));
    is_upstream_concavity = np.logical_and(is_upstream_concavity, (L == I_N));
    is_upstream_concavity = np.logical_and(is_upstream_concavity, (L == I_W));

    upstream_convexity_labels = L[is_upstream_convexity];
    upstream_concavity_labels = L[is_upstream_concavity];

    total_upstream_convexities = np.bincount(upstream_convexity_labels)[1:] #Discard the zero bin, which is the background.
    total_upstream_concavities = np.bincount(upstream_concavity_labels)[1:]

    return total_upstream_convexities - total_upstream_concavities;


#Load the image
BwI = cv2.imread('BwI.png', cv2.IMREAD_GRAYSCALE)

#Label all the connected components
_, L = cv2.connectedComponents(BwI)

#Compute all the Euler numbers
e = EulerNumbers(L)

# All the regions with no holes will have an Euler number of 1. Regions with one hole
# will have an Euler number of 0. Two holes -> -1 etc. 

num_no_holes = np.sum(e==1)
num_single_hole = np.sum(e==0)
num_two_holes = np.sum(e==-1)
num_three_holes = np.sum(e==-2)
num_more_holes = np.sum(e<-2)

print('Number of objects without holes : %d'%num_no_holes)
print('Number of objects with single hole : %d'%num_single_hole)
print('Number of objects with two holes : %d'%num_two_holes)
print('Number of objects with three holes : %d'%num_three_holes)
print('Number of objects with more than three holes: %d'%num_more_holes)

## Example, colourcode all objects by their amount of holes

Euler2Numholes = lambda e : abs(e-1)

#Label each region by the number of holes it has + 1.
# +1 so the holeless ones won't dissappear.
L_holecounts = np.zeros(L.shape, dtype=np.int32)
for i in range(1, np.max(L)):
    L_holecounts[L == i] = Euler2Numholes(e[i-1])+1

#Spread the small range to [0,255]
plot_L = cv2.normalize(L_holecounts, None, 0, 255, cv2.NORM_MINMAX, dtype=cv2.CV_8UC1) 
#Note that this will break when there are more than 255 labels. The colormap only works with uint8.

#Colormap it
plot_L = cv2.applyColorMap(plot_L, cv2.COLORMAP_JET)

cv2.imshow('The objects colourcoded by their number of holes', plot_L)
cv2.waitKey(0)

Outputs :

Number of objects without holes : 21
Number of objects with single hole : 2
Number of objects with two holes : 4
Number of objects with three holes : 0
Number of objects with more than three holes: 0