Homework Assignment #1

Segmentation: livewire, graph-cuts, K-means


This homework has three parts covering standard image segmentation techniques based on graph algorithms (shortest paths, minimum graph cuts) and basic clustering methods (K-means). The first two are used for segmentation boundary regularization, while the last can be used for color quantization or superpixels. Generalization of these methods are routinely used in more advanced applications of computer vision. Thus, hands-on experience that you obtain while working on this assignment should aid in better understanding some later material in this course.

The students are strongly encouraged to work in python notebook environment (Jupiter/Anaconda/Python 2.7), which was already demonstrated in class. This environment is convenient for prototyping techniques for image analysis due to many visualization and plotting options, wide support for array handling and image processing libraries. Installation instructions for Anaconda (Python 2.7) as well as PyMaxflow library needed for part II of the assignment are given here. NOTE: we tested the interface functions used in this assignment under Anaconda versions 4.2.0 (the latest) and 2.4.1 (older version provided in the instructions). But relatively recent Anaconda 4.1.1 has some bugs. In case you already installed Anaconda, check its specific version. If it is 4.1.1 you should uninstall it (from the system/apps menu) and install either the latest Anaconda 4.2.0 or older version 2.4.1. In any case, use Anaconda - Python 2.7.

Besides the libraries above, the students should use several files provided specifically for this homework inside hw1.zip. It includes "starter" notebooks for Jupiter/Anaconda giving good initial point for each part of the assignemnt. These notebooks come integrated with the necessary GUI interfaces handling low-level evens (mouse-down, mouse-move, button-down, etc) for interactive segmentation (e.g. entering seeds) as well as visulaizization of images and the results (e.g. contours or segmentation masks). Such GUI functions are implemented in a separate file (asg1.py) containing the code for the "presenters" objects (e.g. LiveWirePresenter, GraphCutsPresenter). This file should be kept in the same directory where you have your notebook files. We also provide a sample notebook (MyRegionGrowing.ipynb) containing fully implemented Region Growing segmentation tool. This notebook can be used as an example. It also uses a specialized "RegionGrowingPresenter" implemented in "asg1.py".

It is expected that in each notebook (for parts I, II, or III below) you will use/create multiple "cells" corresponding to different specific tasks/experiemnts. For example, one "code" cell may contain a class implementation. Separate "code" cells can create and use object(s) of this and other classes to demonstrate experimental results on different images or with different values of parameters. The corresponding results should be in the figures below each "code" cell. If needed/required, the visual results can be discussed in separate "markdown" cells right below each figure. Keep the experiemnts in your notebook well-organizied. Presentatation clarity and good organization of your notebooks will be evaluated/marked.

When preparing your notebooks for submission, you should test each notebook after restarting the python kernel in Jupiter (Kernel->Restart). Then, run the cells consequtively and make sure that they work correctly in this order. When saving your notebook before submission, the cell numbers on the left margin of the notebook should be 1,2,3,4,... from top to bottom. When testing your code I can re-run the cells of your notebook only in this specific order. Also, save your notebook after each (interactive) figure cell is in the state showing the exact result that you want to demonstrate (e.g. for specific seeds) and that you might be discussing in a markdown cell right below the figure. Besides these tested notebook files, you should also save and submit their "html" versions (File->Download as->HTML), which also contain the "current" state of your figures.

Note that the assignment mentions some "optional" tasks. As all other required tasks, the optional tasks should be implemented in separate cells. Conclusive figures/experiments with specific points discussed in "markdown" cells (below) can yield bonus points.

Specific Tasks

What to submit, where to submit, and when to submit

Submit one file hw1_your_name.zip containing three notebooks (MyLiveWire.ipynb, MyGraphCuts.ipynb, MyKmeans.ipynb) and their html copies generated as explained above (MyLiveWire.html, MyGraphCuts.html, MyKmeans.html). Your notebooks should include cells with your python code, figures, and explanations/discussions. Your code cells should include "code comments" (e.g. description of function interfaces/parameters, etc). All files with images used in your notebook should be placed in "images" subdirectory next to your notebook files (such images should be loaded to your notebooks using paths like "images/file_name.bmp"). When ready to submit your work, zip the notebook files, their html versions, and the subdirectory "images" into your submission file hw1_your_name.zip.

The corresponding file (.zip) should be submitted electronically via OWL. The notebook (code and comments) should be your independent effort.

All files should be submitted to OWL before 11:55pm on the due date (Oct.18). Do not wait until the last moment. A rush just before 11:55pm will not be accepted as a valid excuse.