Finding Number of Objects in Image

Question

I wrote a program that, given a 2D array representing pixels in a birds eye view image, it returns the number of Objects in the image.

Pixels that are connected in the up, down, left, and right directions are a single object.

Example:

grid = [
    [0, 0, 0, 1, 0],
    [0, 1, 1, 0, 1], 
    [0, 0, 1, 1, 1],
    [1, 1, 0, 1, 0],
    [1, 1, 0, 0, 0],
]

The grid above visualized:

we see 3 separate objects, A, B, and C

| | | |A| |
| |B|B| |B|
| | |B|B|B|
|C|C| |B| |
|C|C| | | |

Algorithm is expected to return the count, in this case, 3.

My approach was the following:

1. for each pixel in the image, if it is marked as 1 and it is unvisited I would increase the connected component counter and perform initial DFS from this "source" pixel/vertex.
2. Inside the DFS call on pixel 1 "source pixel/vertex" of object 1, I would mark as visited, and get the list of adjacent vertices (representation defined above). Then recursively traverse all unvisited, making sure to mark as visited either with a 2D array of booleans, or possibly, marking pixel as -1 for visited to save space... I think that may also work.
3. I would then only increment the object counter, on each initial DFS call on a "source" pixel, aka, the first pixel encountered of an object, which will be any pixels that were not visited by previous traversals (if not reached by other traversals it means these pixels were disconnected and therefore a new object)
4. return the instance variable counter which now holds the number of objects (number of different connected components)

Implementation:

from typing import List, Tuple

class ConnectedPixels:
    def __init__(self, image: List[List[int]]) -> None: 
        # number of objects counter
        self.connected_components = 0
        
        ## visited array
        self.visited =  [[False for c in range(len(image[0]))] for r in range(len(image))]

     
        length = len(image)
        width = len(image[0])
        
        
    
        # for all pixels in image
        for i in range(0, length):
            for j in range(0, width):
                ij_pixel = image[i][j]
                
                # If pixel is an object, or part of an object (aka set to 1) AND has not been visited yet
                if ij_pixel ==  1 and self.visited[i][j] == False:
                    # increase object count and perform DFS on first pixel of object
                    self.connected_components += 1
                    self.DFS(image ,i , j)
        
    def DFS(self, image: List[List[int]], row: int, col: int) -> None:

        ## mark pixel as visited
        self.visited[row][col] = True
        
        ## find all contiguous pixels to pixel [row][col]  aka (row, col)
        adjacent_pixels = self.adj_vert(image, row, col)
    
        for adjacent_px in adjacent_pixels:
            # find row and col of adjacent pixel
            row_adj_px = adjacent_px[0]
            col_adj_px = adjacent_px[1]
            
            # if adjacent pixel is not visited and is marked as a 1 in the image aka, it has is an object, or part of one
            if self.visited[row_adj_px][col_adj_px] == False and image[row_adj_px][col_adj_px] == 1:
                # perform DFS on the pixel
                self.DFS(image, row_adj_px, col_adj_px)
        
    
    ## TODO: VERY UGLY, CAN THIS BE IMPROVED?
    #aka get cardinal neighboors (top, down, left, right)
    def adj_vert(self,image: List[List[int]], row: int, col: int) -> List[Tuple[int, int]]:
        adjs = []
        
        width = len(image[0])
        length = len(image)
        
        
        right_most_pixel = width - 1
        bottom_most_pixel = length - 1
        
        # top left corner
        if row == 0 and col == 0:
            adjs.append((1, 0))
            adjs.append((0, 1))
        # top right corner
        elif row == 0 and col == right_most_pixel:
            adjs.append((0, right_most_pixel - 1))
            adjs.append((1, right_most_pixel))
        # bottom left 
        elif row == bottom_most_pixel and col == 0:
            adjs.append((bottom_most_pixel - 1, 0))
            adjs.append((bottom_most_pixel, 1))
        # bottom right
        elif row == bottom_most_pixel and col == right_most_pixel:
            adjs.append((bottom_most_pixel, right_most_pixel - 1))
            adjs.append((bottom_most_pixel - 1, right_most_pixel))
        
        #top border, if pixel is at the top border (excluding the corners)
        elif row == 0 and col > 0 and col < right_most_pixel:
            adjs.append((1, col))
            adjs.append((0, col - 1))
            adjs.append((0, col + 1))
            
        # bottom border, if pixel is at the bottom border (excluding the corners)
        elif row == bottom_most_pixel and col > 0 and col < right_most_pixel:
            adjs.append((bottom_most_pixel - 1, col))
            adjs.append((bottom_most_pixel, col - 1))
            adjs.append((bottom_most_pixel, col + 1))
            
        # left border, if pixel is at the left border (excluding the corners)
        elif col == 0 and row > 0 and row < bottom_most_pixel:
            adjs.append((row - 1, 0))
            adjs.append((row + 1, 0))
            adjs.append((row , 1))
        
        # right border, if pixel is at the right border (excluding the corners)
        elif col == right_most_pixel and row > 0 and row < bottom_most_pixel:
            adjs.append((row - 1, right_most_pixel))
            adjs.append((row + 1, right_most_pixel))
            adjs.append((row, col - 1)) 
        # pixel is in the middle region    
        else:
            adjs.append((row - 1, col))
            adjs.append((row + 1, col))
            adjs.append((row, col + 1))
            adjs.append((row, col - 1))

            
           
        return adjs
        
        

Doubts/Question:

• The adj_vert methods to get the neighbors of a pixel is extremely ugly. Is there a cleaner way to the approach I took?
• I tested the above for some sample inputs and also stepped through the code, and so far so good, Is there a similar problem on Leetcode to test more thoroughly for correctness?
• Can I save on space by flipping each unvisited pixel marked as 1 to -1 on the same image
• I believe run time is proportinal to L x W of image, is there a way to make this more efficient?
• Any code design changes/ improvements that can be made?

Edit:

• Leetcode 200 can be used for test cases

For the function that finds the neighbors of a (row, col) of a matrix, My function was giving issues if the numbers of pixels in the image was less than a 3x3 because, for example, if image was a single pixel at (0,0), my code would say neighbors were (1,0) and (0, 1)

Better Solution:

   # get the vertical, and horizontal neighbors of cell (row, col)
    def  adj_vert(self, row:int, col:int):
        
          #these are the diferentials from the cell that we are trying to find neighbors of, (row, col)
        # if we were considering all 8 neighbors, we would also have [1, 1], [-1, -1] , [1, -1], [-1, 1] for all four diagonals
        directions = [[1, 0], [-1, 0], [0,1], [0, -1]]
        
        adjacent_vertices = []
        for dr, dc in directions:
            
            # adding the directions, to the cell we are finding the neighbors of, (row, col)
            r, c = row + dr, col + dc
            if r in range(self.total_rows) and c in range (self.total_cols):
                adjacent_vertices.append( (r, c) )
                
        return adjacent_vertices

Answer 1

The adj_vert method to get the neighbors of a pixel is extremely ugly. Is there a cleaner way to the approach I took?

Yes, checking 4 conditions is enough. For example:

if row > 0:
    adjs.append((row - 1, col))
if row + 1 < length:
    adjs.append((row + 1, col))
if col > 0:
    adjs.append((row, col - 1))
if col + 1 < width:
    adjs.append((row, col + 1))

Is there a similar problem on Leetcode to test more thoroughly for correctness?

I see from your edit that you found a similar problem.

Can I save on space by flipping each unvisited pixel marked as 1 to -1 on the same image?

Yes, however that would change the input. If changing the input is allowed you can "cancel" the images flipping the 1s to 0s, so that no additional logic (to handle -1s) is needed.

Any code design changes/ improvements that can be made?

• Input validation
• Docstrings
• Function instead of a class. A class seems inconvenient for this purpose. The constructor runs the algorithm directly and there is no method to get the result. The user needs to know that the attribute self.connected_components holds the result after creating the object. This is an unnecessary burden for the user, in my opinion, a function that returns directly the result would be enough.

Answer 2

Modifying the input

Before coding a solution that modifies the input, it's worth asking first "is it ok to modify the input". If there's nobody to answer that, it's good to document it in a docstring ("this solution modifies the input").

Alternatives to modifying the input

Your first solution builds a boolean matrix of the same dimensions as the input.

Another way is to use a set of tuples, where each tuple is a row-column coordinate pair.

Another way is to use a set of integers, where each element encodes a row-column coordinate pair using the formula: element = width * row + column.

Avoid repeated operations

The second variation of adj_vert recreates the directions list on every call. It would be better to create it in the constructor.

The first variation of adj_vert recomputes width and length on every call. It would be better to set these in the constructor.

Avoid creating lists in a loop

adj_vert creates a short-lived list (adjs) on every call. Allocating a new list repeatedly can be expensive, it would be better to refactor the code to avoid such repeated list creation.