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.

In order to better visualize the lines, we use the following set of code snippet:

# visualize list on top of original file
I = np.dstack([im, im, im])
for path in path_list:
	color = [randint(0,1), randint(0,1), randint(0,1)]
	for tup in path:
		I[tup[0], tup[1], :] = color
plt.imshow(I, interpolation='nearest')
plt.pause(0)
plt.draw()