Task 085: Segmentation of Profile Pictures

The challenge is to design and implement an algorithm that can segment an input image into two sets: the background and an object. The user interactively roughly defines which areas of the image belong to which category, and the algorithm then tries its best to separate these components.

Segmentation

Overview

The template application 085segmentation from the repository grcis serves as the basis of this project. This is a ready to use application in which it is possible to load an input image, and then to interactively draw a rough segmentation mask on it by using two colours: the object is indicated by drawing with the left mouse button in red, while the background is specified by drawing with the right mouse button in blue. After pressing the button Recompute, the function Segmentation.DoSegmentation() is called: this function has access to the source image as well as the mask that has been drawn on the image. The task of this method is to split the image pixels into two groups, the background and the object, and the result is stored as a 1-bit (B / W) image.

Interface

Load image - reads a new input image. The user-defined mask is cleared.
Reset - reinitialises (deletes) any previously drawn mask. Pressing the Backspace key has the same effect.
Load mask - loads a previously saved mask (background / object)
Save mask - saves the current mask (background / object) to a PNG file
Pen - pen thickness for drawing the masks (from 1.0 to 5.0 pixels)
White - choice of outside color for the segmentation. Default: white are white
Recompute - start the segmentation process. The result is shown in the right part of the window
Save result - save the result as PNG file

Technical details

Your implementation will be located inside the class Segmentation. This class is used, among other things, as a data container that stores the interactively drawn mask mask as a 8-bit bitmap with a palette. The indices 0-2 have a specific meaning: COL_BACKGROUND .. transparent background color COL_EXTERIOR .. outside of the object (background) .. COL_INTERIOR inside of the object.

Theoretically, you can also modify the code for the interactive drawing of the masks: but you probably do not want to change anything there. Functionality is provided for the following GUI events: MouseDown(), MouseUp(), MouseMove() a KeyPressed(). If you do change anything there, pleases remember that you must return true if the corresponding GUI element has to be redrawn (invalidation).
The drawing function DrawTrace() draws a dot-shaped area in the input mask. The function accepts a floating point line thickness value from 5.0 to 5.0 pixels.

The main parameters of the function Segmentation.DoSegmentation() are:

Bitmap sourceImage - input image
bool whiteExterior - positive value indicates that we want to draw the background in white (this does not affect the internal logic of the segmentation)

The function uses an internally stored mask mask from which one can read values via GetPixel() (red color indicates the object, blue the background).

The return value is a segmented image in Bitmap format, which should have a bit depth of 1 (pixel format Format1bppIndexed).

In several places, the template application uses fast memory access via Bitmap.LockBits. This is necessary for the pixel formats Format8bppIndexed and Format1bppIndexed. This way, the project demonstrates working with indexed color formats. Please note (and respect) the need to write the resulting 1-bit image via a bit buffer (int buffer) and the need to align each horizontal line on an integral number of bytes!

Segmentation algorithm

We suggest the efficient and elegant method of segmentation based on finding a minimum cut in a graph. A planar graph consists of the image pixels (connected via their 4 neighbours), and the source and sink are sets of pixels marked interactively by the user. Edge evaluation depends on the colour differences of neighbouring pixels - the smaller the difference, the greater the weight of the potential edge.

Literature about various segmentation algorithms

What to hand in

You have to send us the file Segmentation.cs .
In the first line, put your name in a comment
If you are using images to drive the input, and if you have achieved a nice result with a particular input image, you can also send us that image. But please watch the size of the mail attachment, and use some web upload service if it is too large (Dropbox, GoogleDrive, uloz.to),

Also, when submitting the file, please make sure that it includes meaningful comments that describe the algorithm you chose: how you chose it, or where you found information on it (literature, Wikipedia, ...). Do odevzdaného zdrojáku připište podrobnější komentář o původu vašeho algoritmu: zda jste ho sami vymysleli, zda jste se inspirovali literaturou, apod.

Deadline

Hand in until: 13. 12. 2015

Points

Basis: 8 points, bonus up to 8 points. Implementations of any form of graph cut will at least receive 10 points overall.

Project

Visual Studio project: 085segmentation.

Source file

Modify and hand in the source file: Segmentation.cs
As a comment in the first line, please include your name!

Data

Your algorithm should work on any input image. For test purposes, you can use images from the repository directory data, and also the images profile00.jpg, profile01.jpg, profile02.jpg, profile03.jpg, profile04.jpg. For reasons of testing efficiency, you might want to reduce the resolution of these: but this is up to you, and in no way mandatory.