Implementation and Testing of Image Segmentation Algorithm

1. Problem Statement:

The goal of this assignment is to implement and test an image segmentation algorithm that combines ideas from the classic “split merge” algorithm and the “gradient watershed” algorithm.

In particular, your program will use the gradient watershed algorithm to partition the input into a collection of small regions with the boundaries of these regions aligned with the edges of objects in an image. The gradient watershed algorithm typically over segments the image. To correct this, your program should use the merging phase from the split merge algorithm to combine adjacent watershed regions together until a small number of visually sensible regions remain.

Your final task is to create three output images: 1) an image where pixels in each region contain the region number, 2) an image where the pixels in each region contain the average intensity value of the region, and 3) a black/white image that shows the boundaries of each of the regions.

2. Design:

The “gradient watershed” algorithm is implemented as part of the “libim” library that you have already used. This method takes an im_float image in, performs Gaussian smoothing to remove noise, and calculates gradient watershed regions using the classic “rainfall simulation” method. The output of this method is two images, one with each pixel marked with their region number, and another with each pixel containing the average intensity of each region. See the program “menu.cpp” for an example on how to call the Watershed method.

In order to implement region merging, you will need to create some data structure that records which regions are adjacent to each other, and initialize this by scanning image from top-to-bottom and left-to-right to find the transitions from one region to the next (when Image.Data2D[y][x] has different value than Image.Data2D[y][x+1] or Image.Data2D[y+1][x]). During the merging phase, you will need to keep track of which regions have merged with each other. One way to do this is with a “set” representation that supports the “union/find” operations.

3. Implementation:

You will be starting with a C++ library of image processing and computer vision code called “libim” that is available on the class website. To compile this code, go to the src directory and type “make”. This will compile the “libim” library, the “jpeg” library, and 10 sample programs in the “programs” directory.
 

Once you have done this, you can go into the “programs” directory, and look at the “menu.cpp” program to see how the Watershed method is called. You can then create your “segment.cpp” program modeled after your “find_lines.cpp” program and edit the Makefile so you can compile using “make”.

4. Testing:

Test your program to check that it operates correctly for all of the requirements listed above. To start, use an input image with one object on a contrasting background (so segmentation is trivial). Once this is working, try a variety of other input images to see how many good regions you can find. What does your program perform compared to the gradient watershed algorithm? Save your testing output for submission on the program due date.

5. Documentation:

When you have completed your program, write a short report (2-3 pages long) describing what the objectives were, what you did, and the status of the program. Include your C++ code, and sample input/output images to illustrate how the code works. Does your code work properly for all test cases? Are there any known problem