Recursive Path Searching Algorithm

In this project, we implemented a recursive path finding algorithm. We detail it below (found in findpath.py):

find_path function

Our find_path function takes in a grayscale image, and will traverse from bottom-left corner to the right, using a double for loop:

[rowMax, colMax] = img_gray.shape
for r in xrange(rowMax-2, 1, -1):
   for c in xrange(2, colMax-2, 1):
      # some code here...

Inside the loop, we will attempt to find the first instance of a white pixel. This will act as our start point for a single path. We will then call a search function, which is outlined as follows:

search function

This recursive function has the following definition: def search(search_list, img, r, c).

• search_list is the list (in-order) of (row, col) that pertain to one path. This will be accumulated in the recursion
• img is the numpy array that represents our grayscale image
• r is the current row value
• c is the current column value

Inside the function, we perform the following:

1. Generate a 3x3 pixel matrix, with (r, c) as the center.
2. Find the appropriate (new_r, new_c) by examining the neighboring white pixels near (r, c).
3. Clearing the current 3x3 pixel matrix area on the img; this prevents us from circular searching
4. Appending (new_r, new_c) to our search_list
5. Recursively calling search(search_list, img, new_r, new_c) and returning that result

Our stopping condition is as follows:

# stopping condition: offsets are zero OR goes out of bound
if ((r_offset == 0 and c_offset == 0) or (new_r >= rowMax - 1) or (new_c >= colMax - 1)):
   return search_list

calling find_path

In order to ensure that we find all paths in the skeletonization. We run find_path continuously until it returns an empty list of paths, which indicate there are no more paths left to be found.