Connected Components

Photogrammetry-1

To find objects in an image, we can use connected components. It works by utilizing 4 or 8 neighbourhood. It starts off by randomly selecting an unlabelled pixel, assigns an id to it and then continues finding unlabelled pixels in 4 or 8 neighbourhood assigning the same id to all of them. It keeps on finding new elements until all elements are found. Below is a function which performs connected component analysis using 4 or 8 neighbourhood. It takes as input a binary image and the neighbourhood while it provides as an output the number of elements in the binary image along with the connected image having all the elements labelled.

def connected_components(binary_img, neighborhood):
    
    connected_image = np.zeros(np.shape(binary_img))
    S = []
    K = 0
    for i in range(200):
        x_idx = random.choice(np.arange(np.shape(binary_img)[0]))
        y_idx = random.choice(np.arange(np.shape(binary_img)[1]))
    
        if connected_image[x_idx,y_idx] == 0 and binary_img[x_idx,y_idx] == 1:
            S.append([x_idx,y_idx])
            K = K + 1
            connected_image[x_idx,y_idx] = K
            
            for index in S:
                
                x_idx = index[0]
                y_idx = index[1]
                
                if neighborhood == 4:
            
                    if x_idx-1 >= 0:
                
                        if binary_img[x_idx-1,y_idx] == 1 and connected_image[x_idx-1,y_idx] == 0:
                    
                            connected_image[x_idx-1,y_idx] = K
                    
                            S.append([x_idx-1,y_idx])
                    
                    if x_idx+1 < np.shape(binary_img)[0]:
                
                        if binary_img[x_idx+1,y_idx] == 1 and connected_image[x_idx+1,y_idx] == 0:
                    
                            connected_image[x_idx+1,y_idx] = K
                    
                            S.append([x_idx+1,y_idx])
                    
                    if y_idx-1 >= 0:
                
                        if binary_img[x_idx,y_idx-1] == 1 and connected_image[x_idx,y_idx-1] == 0:
                    
                            connected_image[x_idx,y_idx-1] = K
                    
                            S.append([x_idx,y_idx-1])
                    
                    if y_idx+1 < np.shape(binary_img)[1]:
                
                        if binary_img[x_idx,y_idx+1] == 1 and connected_image[x_idx,y_idx+1] == 0:
                    
                            connected_image[x_idx,y_idx+1] = K
                                
                            S.append([x_idx,y_idx+1])
            
                if neighborhood == 8:
                    
                    if x_idx-1 >= 0 and y_idx+1 < np.shape(binary_img)[1]:
                        
                        if binary_img[x_idx-1,y_idx+1] == 1 and connected_image[x_idx-1,y_idx+1] == 0:
                            
                            connected_image[x_idx-1,y_idx+1] = K
                            
                            S.append([x_idx-1,y_idx+1])
                            
                    if x_idx+1 < np.shape(binary_img)[0] and y_idx+1 < np.shape(binary_img)[1]:
                        
                        if binary_img[x_idx+1,y_idx+1] == 1 and connected_image[x_idx+1,y_idx+1] == 0:
                            
                            connected_image[x_idx+1,y_idx+1] = K
                            
                            S.append([x_idx+1,y_idx+1])
                            
                    if x_idx-1 >= 0 and y_idx-1 >= 0:
                        
                        if binary_img[x_idx-1,y_idx-1] == 1 and connected_image[x_idx-1,y_idx-1] == 0:
                            
                            connected_image[x_idx-1,y_idx-1] = K
                            
                            S.append([x_idx-1,y_idx-1])
                            
                    if x_idx+1 < np.shape(binary_img)[0] and y_idx-1 >= 0:
                        
                        if binary_img[x_idx+1,y_idx-1] == 1 and connected_image[x_idx+1,y_idx-1] == 0:
                            
                            connected_image[x_idx+1,y_idx-1] = K
                            
                            S.append([x_idx+1,y_idx-1])
            
                    if x_idx-1 >= 0:
                
                        if binary_img[x_idx-1,y_idx] == 1 and connected_image[x_idx-1,y_idx] == 0:
                    
                            connected_image[x_idx-1,y_idx] = K
                    
                            S.append([x_idx-1,y_idx])
                    
                    if x_idx+1 < np.shape(binary_img)[0]:
                
                        if binary_img[x_idx+1,y_idx] == 1 and connected_image[x_idx+1,y_idx] == 0:
                    
                            connected_image[x_idx+1,y_idx] = K
                    
                            S.append([x_idx+1,y_idx])
                    
                    if y_idx-1 >= 0:
                
                        if binary_img[x_idx,y_idx-1] == 1 and connected_image[x_idx,y_idx-1] == 0:
                    
                            connected_image[x_idx,y_idx-1] = K
                    
                            S.append([x_idx,y_idx-1])
                    
                    if y_idx+1 < np.shape(binary_img)[1]:
                
                        if binary_img[x_idx,y_idx+1] == 1 and connected_image[x_idx,y_idx+1] == 0:
                    
                            connected_image[x_idx,y_idx+1] = K
                                
                            S.append([x_idx,y_idx+1])
            
                    
                    
    return K, connected_image    

That’s it for now, see you later.