# Interactive Grain Image Segmentation

### using Graph Cut Algorithms

Jarrell Waggoner$^1$ / @malloc47 / waggonej@email.sc.edu,
Youjie Zhou$^1$, Jeff Simmons$^2$, Ayman Salem$^3$, Marc De Graef$^4$, Song Wang$^1$

$^1$USC, $^2$AFOSR, $^3$MRi, $^4$CMU

### Interactive Segmentation?

• Contrast with fully-automatic segmentation
• Sparse number of user interactions as additional constraints or guidance in the segmentation process
• Other interactive segmentation methods use:
• Bounding boxes
• Coarse outlining of the desired boundary
• "Scribbling" foreground/background regions

### Our Approach

• Build on our previous propagation method
• Correct errors after every propagation with a single point (click) as the user-supplied interaction
• Reduce having to draw individual boundaries
 $U$ : Source image that is segmented $V$ : Target image that is not segmented $S^U, S^V$ : Segmentation of $U$ or $V$ respectivesly

### Propagation

• Obtain $S^V$ by propagating $S^U$ to $V$
• In our previous work, this was done by using an energy of the form

$$E( S^V ) = \sum_{p\in V}\Theta_p(S^V_i) + \sum_{\{p,q\}\in\mathcal{P}^V_n} \Phi_{pq}(S_i^V , S_j^V)$$

which can be minimized by the min-cut max-flow graph cut algorithm

### Unary and Binary Terms

$$\Theta_p(S^{V}_i) = \left\{ \begin{array}{lcr} 0, & \textrm{distance}(p,S^U_i) < d \\ \infty, & \textrm{ otherwise} \\ \end{array} \right.$$

$$\Phi_{pq}(S^V_i , S^V_j) = \left\{ \begin{array}{lcr} 0, & i = j \\ \infty, & \{ S^U_i, S^U_j \} \notin \mathcal{A}^U \\ g( p, q ), & \{ S^U_i, S^U_j \} \in \mathcal{A}^U \\ \end{array} \right. ,$$

### Limitations

• Minimizes a fixed set of segments: must use heuristics to determine where to add new segments
• Topology constraints may not allow the removal of some segments

# Goal:

Incorporate human interaction into the segmentation task to

• Remove Spurious Segments

Do this with minimal interaction, producing an updated segmentation $\tilde{S}^V_i$

# Removal

### Removal Input

We require only a single annotation (click) identifying a particular segment $S^V_k$ to be removed, which is done in two steps:

### Identify Local Region

Identify local region for removal $\mathcal{L} = \{\mathcal{A}^V\}_k \bigcup S^V_k$ where $\{\mathcal{A}^V\}_k$ is all the segments adjacent to the segment to be removed

### Update Energy Terms

Update the unary term to allow $S^V_k$ to be reassigned to its neighbors:
\begin{aligned} \forall p \in S^V_k ,& \quad \Theta_p(\tilde{S}^V_i) = \left\{ \begin{array}{lcr} 0, & S^V_i \in \{\mathcal{A}^V\}_k \\ \infty, & \textrm{ otherwise} \\ \end{array} \right. \\ \forall p \notin S^V_k ,& \quad \Theta_p(\tilde{S}^V_i) = \Theta_p(S^V_i) \end{aligned}

### Removal Algorithm

Require three inputs:

• Center point $c$ for new segment
• Seed radius $s$ around the center point which is completely contained within the desired grain
• Dilation radius $d$ around the center point which completely covers the desired grain

### Local Region

$\mathcal{L} \gets$ union of all segments that contain a seed pixel or dilation pixel

### Update Energy Terms

$$\Theta_p(\tilde{S}^V_{n+1}) = \left\{ \begin{array}{lcr} 0, & \| p - c \| \leq d \\ \infty, & \textrm{ otherwise} \\ \end{array} \right.$$ $$\Theta_p(\tilde{S}^V_i) = \left\{ \begin{array}{lcr} \infty, & \| p - c \| \leq s \textrm{ and } i \neq n+1 \\ \Theta_p(S^{V}_i), & \textrm{ otherwise.} \\ \end{array} \right.$$

# Parameter Estimation

### Parameter Estimation

• Estimate the $s$ and $d$ parameters in the addition step
• Do this by leveraging information about the center $c$ the user provided relative to the initial segment in which it resides:
• Increase $s$ by $\epsilon$ until it touches the boundary of its containing segment $S^V_b$
• Set $d$ to be $2\times s$

# Conclusion

• Augmented our previous propagation approach with an interactive component that increases performance
• We handle both segmentation addition and removal using minimal interaction
• Parameter estimation reduces the time and effort needed