====== 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]]
 
<WRAP round download>
Start by downloading the [[https://cw.fel.cvut.cz/wiki/_media/courses/b4m33dzo/labs/dzo2022_07_segment_student.zip|template]] of the assignment.

Use ''segment.m'' to check your solution.
</WRAP>

===== 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]]

<note important>
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.
</note>