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
\begin{equation}
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)
\end{equation}
which can be minimized by the
min-cut max-flow graph cut algorithm
Unary and Binary Terms
\begin{equation}
\Theta_p(S^{V}_i) = \left\{
\begin{array}{lcr}
0, & \textrm{distance}(p,S^U_i) < d \\
\infty, & \textrm{ otherwise} \\
\end{array}
\right.
\end{equation}
\begin{equation} \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. ,
\end{equation}
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
- Add Missing Segments
Do this with minimal
interaction, producing an updated segmentation
\tilde{S}^V_i
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{equation}
\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}
\end{equation}
Removal Algorithm
Addition Input
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
\begin{equation}
\Theta_p(\tilde{S}^V_{n+1}) = \left\{
\begin{array}{lcr}
0, & \| p - c \| \leq d \\
\infty, & \textrm{ otherwise} \\
\end{array}
\right.
\end{equation}
\begin{equation}
\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.
\end{equation}
Addition Algorithm
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
Parameter Estimation Visual Example
Performance
Effort
Time
- 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
