====== 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.
{{:courses:b4m33dzo:labs:07_segment_lazybursh.jpg?600|}}
The theory behind the labs can be found in the lectures:
* [[https://dcgi.fel.cvut.cz/home/sykorad/dzo/slides/dzo-l11.pdf|L11 - Image Segmentation 1]]
* [[https://dcgi.fel.cvut.cz/home/sykorad/dzo/slides/dzo-l12.pdf|L12 - Image Segmentation 2]]
and also in the original paper:
* [[https://dcgi.fel.cvut.cz/home/sykorad/lazybrush.html|LazyBrush: Flexible Painting Tool for Hand-drawn Cartoons]]
Start by downloading the [[https://cw.fel.cvut.cz/wiki/_media/courses/b4m33dzo/labs/dzo2023_07_segment_student.zip|template]] of the assignment.
Use ''segment.m'' to check your solution.
===== Build directed graph =====
**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:
{{:courses:b4m33dzo:labs:07_segment_graph.png?300|}}
===== Solve for maximum flow and paint the input drawing =====
**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 [[https://www.csd.uwo.ca/~yboykov/Papers/pami04.pdf|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:
* [[https://cw.fel.cvut.cz/wiki/_media/courses/b4m33dzo/labs/07_segment_output.png|Final painted image]]
When you are done, upload the complete zip archive containing your implementation to BRUTE:
* ''segment.m''
as well as your final output image generated in tasks 2.
Keep the files in the root of the zip archive (zip directly the files, NOT a folder containing the files). The evaluation system searches for the files just in the root of zip archive.
The points will be assigned manually by TA after the deadline.