Connected Components Labeling
Implement a Connected Components Labeling algorithm to identify and label distinct regions in a binary image. The task involves processing a 2D array of pixels, where each pixel has a value of either 0 or 1, and assigning a unique integer label to each connected component.
The concept of connected components is crucial in Image Segmentation, as it enables the separation of objects or regions of interest within an image. In this context, two pixels are considered connected if they are adjacent to each other, either horizontally or vertically, and have the same intensity value. The 4-connectivity criterion is used, which means that two pixels are connected if they share an edge.
Return a label matrix with the same dimensions as the input image, together with the number of components found. Background pixels (value 0) get label 0. Components are numbered in the order their first pixel appears when the image is read row by row, top to bottom and left to right within each row. Formally:
This technique is widely used in medical imaging for tumor segmentation.
Example
image = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
([[1, 0, 2], [0, 0, 0], [3, 0, 4]], 4)
- The input
imageis a binary grid whose 1s sit only in the four corners. - Under 4-connectivity a pixel only touches the pixels directly above, below, left and right of it. Every corner 1 has only 0s as edge-neighbours (the middle row and middle column are all 0), so each corner is a component of size one. Diagonal contact would not count anyway.
- Numbering follows reading order: row 0 gives the top-left corner label and the top-right corner label ; row 1 has no 1s; row 2 gives the bottom-left corner and the bottom-right corner .
- Every 0 keeps label 0, so the labeled image is
[[1, 0, 2], [0, 0, 0], [3, 0, 4]]and the count is , the largest label used. - Notice that if row 1 column 0 were also 1, the left column would form one vertical component spanning rows 0–2. The labels would then be and the count .
Constraints
- image is a 2D binary list (0 or 1)
- Use 4-connectivity (up, down, left, right)
- Labels start at 1 and increment
- Return tuple (labeled_image, count)