K-Means Clustering / Intelligent scissors algorithm for image segmentation

Part 1

K-Means Clustering

You need to implement a segmentation program based on K-means. The program assigns to each pixel in the image a unique label corresponding to its class. The figure below shows a sample color image that your program takes as input.

The requirements below intend to specify what is to be done, but not how it should be done. The student should consider various design decisions for constructing the segmentation program.

Figure 1: Color image

1. The program should give a brief greeting and announce its purpose

2. The program should prompt the user for its input. The input is as follows.

a. The name of the .pgm or .ppm file that contains the image to process

b. The image type: gray scale or color

c. The number of clusters in the image is given as an input

3. The program must allow the selection of the features to use for clustering. The features that must be included in your work are: color for ppm, gray scale intensity for pgm and location.

4. The program generates as output a color image where each color corresponds to a different cluster label.

5. Important program steps must be clearly described. Program code or tools used, developed by others, should be documented. The core of the segmentation part (i.e. K-means) must be your own code.

6. A document/ report must be submitted that shows the use of the program, the results, and some discussion of the results.

Resources

1. Example test data files will be provided.

Submission: report + program

You will submit 2 files: one containing your programming work (source code only) and one containing your report. For the electronic report of your results, you may use Word, PowerPoint, or other document processor to prepare the report. This report must have the following sections: 1) identification of person and assignment, 2) brief problem definition, 3) summary of choices made for the solution, 4) Segmentation results of 2 color and 2 gray scale images, 5) brief discussion of results. As a guideline, a well done report need only be 2 typed pages in addition to the pages showing the example results.

Deadline April 10th.

Part 2

The objective of this project is to implement and study the intelligent scissors algorithm for image segmentation.

Requirements

You need to implement a segmentation program based intelligent scissors. The program allows the use users to manually input seed and free points. The program then automatically generates the edges links. The figure below shows a sample gray scale image that your program takes as input.

The requirements below intend to specify what is to be done, but not how it should be done. The student should consider various design decisions for constructing the segmentation program.

Figure 1: input image

7. The program must allow the selection of seed and free points. The program displays the edge links. The process is repeated until the extraction of the complete object contour. (For reference you can see the video Lecture05-Part 2)

8. The program generates as output a binary image that contains the extracted contour. Bonus: Bonus points are awarded if you output a binary mask that contains the segmented object (See picture below)

Figure 2: Output mask

9. Important program steps must be clearly described. Program code or tools used, developed by others, should be documented. Code from previous assignments can be used. Libraries can be used to read/display/write image files, to select seed and free points, to perform convolution operations, and to find the shortest path for Dijkstra’s Algorithm. The rest of the work should be yours. It is forbidden to use an already built intelligent scissors function.

10. A document/ report must be submitted that shows the use of the program, the results, and some discussion of the results.

Resources

1. Example test data files will be provided.

Submission: report + program

You will submit 2 files: one containing your programming work (source code only) and one containing your report. For the electronic report of your results, you may use Word, PowerPoint, or other document processor to prepare the report. This report must have the following sections: 1) identification of person and assignment, 2) brief problem definition, 3) summary of choices made for the solution, 4) Segmentation results 5) brief discussion of results. As a guideline, a well done report need only be 4 typed pages in addition to the pages showing the example results. Section 3) should mention choices of algorithm(s) and reuse of outside code.

Deadline April 17th.