# 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.