Exercise 5: Blob Finding

Objectives

• to implement a linear ADT with a linked data structure
• to understand the relationship between stacks and recursion

Introduction

A common task in image processing is blob detection. A blob is an area of an image with a common feature (for example brightness, color, or texture) that is different from the surrounding area of an image. An astronomer may segment an astrophotograph into non-black blobs against the black background of space and then compute the total brightness of each blob to track variable stars. A medical practitioner may want to segment an image of someone's skin into areas of different color in order to track changes in moles that may indicate skin cancer. The algorithm controlling a self-driving car may need to segment an image into areas of similar features in order to track the movement of other road users.

The simplest version of blob finding is to find all pixels connected to a starting point by a path of adjacent pixels of the same color. This can be done with a recursive algorithm:

• if the pixel is the same color as the starting pixel
  • mark the pixel as visited
  • for each adjacent pixel that is in bounds
    • recursively find the pixels connected to that adjacent pixel

Assignment

The program in /c/cs223/hw5/Optional and /c/cs223/hw5/Required implements and tests the blob-finding algorithm from above, with "adjacent" defined as "directly above, below, to the left, or to the right". The given code includes a test driver that allows one to construct an ASCII art image and then find the blob in the image at a given starting pixel.

The blob-finding algorithm is implemented recursively in the image module and returns the number of pixels in the blob it finds. For example, in the image below, the blob containing the pixel at row 2, column 2 (numbering starting from (0,0) in the upper left corner) has size 17.

..........
.@@@......
.@@@......
...@@@@...
.@@@..@@..
......@@..
..........
..........
..........
..........
  

The recursive implementation is limited by the system stack: for a blob in which the farthest pixel from the starting point is millions of pixels away, the recursive solution requires a call tree millions of calls deep, and will run out of space on the system stack. Fortunately, we can simulate recursion using a stack ADT, and since the elements on our stack will be allocated on the heap, we will not run out of room nearly so soon.

Code

Modify the image_blob_size function to use the stack ADT implemented in the stack module. This function should create a stack and push the starting point onto the stack. Then, as long as the stack isn't empty, pop the top location off the stack and if it the same color as the starting point was then increment a counter, change the color of the popped location, store the location on a list so the color can be restored later, and push all valid neighbors onto the stack. When the stack is empty, reset the color of every location in the list, destroy the stack and list, and return the final value in the counter.

The given stack module uses a fixed-length array. Modify it so that the stack elements are stored in a linked list and so stack_push and stack_pop run in $O(1)$ time. Make sure to update stack_destroy to free any elements that remain on the stack. You will also have to define _stack and node structs. The _stack struct should contain a pointer to the head node and the node struct should contain an element and a pointer to the next node to implement a singly linked list.

The stack_push function should create a new node, copy the new element into that node, link the new node to the current head of the stack, and set the new node to be the new head.

The stack_pop function should copy the element in the current head node, set the head node to the the second node, and free the old head node. Be careful not to lose a pointer to the old head node before you free it.

The stack_destroy function should iterate through the remaining nodes, free-ing each one. Be careful about the order in which you free and move to the next node.

The stack module is tested independently of the blob-finding algorithm by the simple unit tests in the executable Unit that is built from stack.c and stack_unit.c.

Examples and Output

The test driver takes command-line arguments to determine the height and width of the image, a sequence of rectangles to draw on the image specified by their starting row, starting column, height, width, and character, and the starting row and column of the blob to find. The output of the test driver is the size of the blob and, if the last command-line argument is p, the image. All output goes to standard output.

(base) [jrg94@cricket code]$ ./Blob 10 10 1 1 2 3 '@' 3 3 1 4 '@' 4 6 2 2 '@' 4 1 1 3 '@' 2 2 p
17
..........
.@@@......
.@@@......
...@@@@...
.@@@..@@..
......@@..
..........
..........
..........
..........

Submissions

Submit your modified image.c and stack.c files, any other files you created, and your makefile with the Blob executable as the default target and the Unit executable as an additional target as assignment number 5. You need not submit the other given files, and your makefile should assume they have been copied into the current directory rather than that they are in their original locations.