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

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