Image Segmentation

The two following labs deal with interactive image segmentation. More specifically the aim will be to implement LazyBrush algorithm that can be used for painting or adding depth to hand-drawn images and other applications. It uses maximum flow / minimal cut algorithm to find globally optimal solution.

The theory behind the labs can be found in the lectures:

• L11 - Image Segmentation 1
• L12 - Image Segmentation 2

and also in the original paper:

• LazyBrush: Flexible Painting Tool for Hand-drawn Cartoons

1a: Indexing arrays - 1.5 point

• Prepare an array id that assigns unique index to each pixel at coordinates (x, y).
• Prepare inverted arrays idx and idy that for given vertex index return x and y coordinates of the corresponding pixel.

1b: Setting up edges between terminals and pixels - 3 points

• Setup directed edges going from the source terminal to all pixels and from all pixels to the sink terminal.
• Set capacity of terminal edges according to scribbles stored in the input image scribbles.png.

1c: Setting up edges between neighbor pixels - 4 points

• Setup undirected edges between neighbor pixels (undirected edge = two directed edges in opposite direction with the same capacity).
• Set capacity of edges between neighbor pixels in proportion to the original pixel's intensity stored in the input image drawing.png.
• Use gamma correction to improve contrast between white and dark pixels (remember that edge capacity between pixels shouldn't be equal to zero).

1d: Building directed graph using built-in Matlab function digraph (already in template)

• Start with smaller dummy graphs and use built-in Matlab function plot to visualize them and check their correctness.

Resulting graph structure:

2: Find maximum flow / minimal cut in the built graph and extract the final labelling - 1.5 point

• Use built-in Matlab function maxflow that implements Boykov-Kolomogorv algorithm to find maximum flow in the built graph.
• Extract indices of pixels that were assigned to the sink terminal.
• Paint the input image drawing.png by multiplying original pixel intensity with predefined color at pixels which were assigned to the sink terminal.

Compare your result to the reference:

• Final painted image