# Complementary Segmentation of Primary Video Objects with Reversible Flows
## 4 Efficient Temporal Propagation with Neighborhood Reversible Flow
### Neighborhood Reversible Flow  
The proposed neighborhood reversible flow (NRF) propagates information along reliable correspondences established among several key frames of the video, thus preventing errors from accumulating quickly and involving larger temporal windows for more effective context exploitation. Instead of pixel-level correspondence, NRF operates on superpixels to achieve region-level matching and higher computational efficiency.  
Given a video \(\mathbb{V}=\{\mathcal{I}_{u}\}_{u=1}^{K}\), we first apply the SLIC algorithm [67] to divide a frame \(\mathcal{I}_{u}\) into \(N_{u}\) superpixels, denoted as \(\{\mathcal{O}_{ui}\}\). For each superpixel, we compute its average RGB, Lab and HSV colors as well as the horizontal and vertical positions. These features are then normalized into the same dynamic range \([0,1]\).  
Based on the features, we need to address two fundamental problems: (1) how to measure the correspondence between a superpixel \(\mathcal{O}_{ui}\) from the frame \(\mathcal{I}_{u}\) and a superpixel \(\mathcal{O}_{vj}\) from the frame \(\mathcal{I}_{v}\), and (2) which frames should be referred to for a given frame? Inspired by the concept of neighborhood reversibility in image search [68], we can compute the pair-wise \(\ell 1\) distances between \(\{\mathcal{O}_{ui}\}_{i=1}^{N_{u}}\) and \(\{\mathcal{O}_{vj}\}_{j=1}^{N_{v}}\). After that, we denote the \(k\)-nearest neighbors of \(\mathcal{O}_{ui}\) in the frame \(\mathcal{I}_{v}\) as \(\mathcal{N}_{k}(\mathcal{O}_{ui}|\mathcal{I}_{v})\). As a consequence, two superpixels \(\mathcal{O}_{ui}\) and \(\mathcal{O}_{vj}\) are \(k\)-neighborhood reversible if they reside in the list of \(k\)-nearest neighbors of each other. That is,  
\[\mathcal{O}_{ui}\in\mathcal{N}_{k}(\mathcal{O}_{vj}|\mathcal{I}_{u})\;\;\text{ and}\;\;\mathcal{O}_{vj}\in\mathcal{N}_{k}(\mathcal{O}_{ui}|\mathcal{I}_{v}). \tag{6}\]From (6), we find that the smaller the \(k\), the more tightly two superpixels are temporally correlated. Therefore, the correspondence between \(\mathcal{O}_{ui}\) and \(\mathcal{O}_{vj}\) can be measured as  
\[s_{ui,vj}=\left\{\begin{aligned} &\exp(-2k/k_{0}),&& \text{if }k\leq k_{0}\\ & 0,&&\text{otherwise}\end{aligned}\right. \tag{7}\]  
where \(k_{0}\) is a constant to suppress weak flow, and \(k\) is a variable. A small \(k_{0}\) will build sparse correspondences between \(\mathcal{I}_{u}\) and \(\mathcal{I}_{v}\) (e.g., \(k_{0}=1\)), while a large \(k_{0}\) will cause dense correspondences. In this study, we empirically set \(k_{0}=15\) and represent the flow between \(\mathcal{I}_{u}\) and \(\mathcal{I}_{v}\) with a matrix \(\mathbf{F}_{uv}\in\mathbb{R}^{N_{u}\times N_{v}}\), in which the component at \((i,j)\) equals \(f_{ui,vj}\). Note that we further normalize \(\mathbf{F}_{uv}\) so that each row sums up to 1. Considering the highly redundant visual content between adjacent frames, for each video frame \(\mathcal{I}_{u}\), we pick up its adjacent keyframes \(\{\mathcal{I}_{i}|t\in\mathbb{T}_{u}\}\) to ensure sufficient variation in content and depict reliable temporal correspondences. In this paper, we refer to the interval \(d_{k}\) of annotated video frames, which usually contain the most critical information of the whole video, to determine the interval of adjacent keyframes. Later, we estimate the flow matrixes between a frame \(\mathcal{I}_{u}\) and the frames \(\{\mathcal{I}_{t}|t\in\mathbb{T}_{u}\}\), where \(\mathbb{T}_{u}\) can be empirically set to \(\{u-2\times d_{k},u-d_{k},u+d_{k},u+2\times d_{k}\}\).