# SSNet: Learning Mid-Level Image Representation Using Salient Superpixel Network
## 3 The Proposed Method for Image Representation
### Saliency Region Detection
#### 3.1.1 Measuring the Gestalt Grouping Connectedness  
(1) Minimum bottleneck distance transform  
Inspired by the fact that the human visual system tends to perceive objects that are similar, close, or connected without abrupt directional changes as a perceptual, we have proposed the smoothest path to represent the relation between image pixels based on the similarity, local proximity, and global continuity of the Gestalt grouping principle, that is  
\[P_{s}(A,B)=\underset{p\subset P_{A,B}}{min}\left\{\underset{p\in[h]\
eq[h+1] \in p}{max}\left\{w_{p[h]p[h+1]}\right\}\right\} \tag{1}\]  
where \(P_{A,B}\) denotes the set of all paths linking node \(A\) and node \(B\) on the \(k\)-nearest neighbor graph, \(p[h]\) is the \(h\)th node on the path \(p\) from node \(A\) to node \(B\), and the largest edge weight on each path \(p\) is defined as the bottleneck to limit the performance of that path. The smoothest path \(P_{s}\) between \(A\) and \(B\) signifies the path that minimizes the largest edge weight of all the paths \(P_{A,B}\). In addition, it has been proven that the path between two nodes in a minimum spanning tree (MST) of a graph is one of the smoothest paths for that pair of nodes. From the perspective of distance transform, we call the metric defined in Equation (1) the minimum bottleneck distance to emphasize the features represented by the smoothest path. Given a distance metric \(g(\pi)\), the distance transform of a node \(v\) is defined as  
\[D(v)=\underset{\pi\in\Pi_{S\
eq}}{min}g(\pi). \tag{2}\]\(\Pi_{S,v}\) is the set of all paths between \(v\) and a seed in \(S,\ \pi=\{\pi(1),\pi(2),\ldots,\pi(k)\}\) is a path belonging to \(\Pi_{S,v}\), and \(g(\pi)\) denotes each kind of distance metric following the properties of symmetry and non-negativity. In Equation (1), \(g(\pi)\) becomes  
\[g(\pi)=max_{i=1}^{k-1}\big{|}I(\pi(i+1))-I(\pi(i))\big{|}. \tag{3}\]  
Furthermore, the calculation of the minimum bottleneck distance between a pair of nodes can be achieved by finding the largest edge weight of the path on the MST. 1. Two-stage traversal on the MST  
In [53], [PERSON] et al. applies the MST instead of the whole graph to approximately calculate the geodesic distance and minimum barrier distance in linear time. Similar to that, we propose a fast implement of the minimum bottleneck distance with the use of the bottom-up traversal and top-down traversal. Given a set of seed nodes \(S\), for each node \(s\in S\), its corresponding distance value is set to 0. For other nodes, their distance values are set to \(\infty\), as shown in Figure 4a. For the bottom-up pass, we start from the leaf nodes and update the distance values of their parent nodes with  
\[D\big{(}v_{p}\big{)}=min\big{\{}D\big{(}v_{p}\big{)},g\big{(}\pi_{v_{q}}\cup v _{p}\big{)}\big{\}} \tag{4}\]  
where \(v_{p}\) is the parent node of the visited \(v_{q}\), \(\pi_{v_{q}}\) is the current optimal path that connects \(v_{q}\) and its nearest seed node, and \(\pi_{v_{q}}\cup v_{p}\) means that the path \(\pi_{v_{q}}\) walks one step further to arrive at node \(v_{p}\). This process does not end until it reaches the root node. Figure 4b demonstrates an example of the bottom-up pass. For the top-down pass, we start from the root node. Figure 4c demonstrates an example of the top-down pass. For each node \(v_{q}\), we update its distance value from the parent node. That is,  
\[D\big{(}v_{q}\big{)}=min\big{\{}D\big{(}v_{q}\big{)},g\big{(}\pi_{v_{p}}\cup v _{q}\big{)}\big{\}}. \tag{5}\]  
As shown in Figure 4, we should track the maximum value of each node. When we visit a newly added node, two comparison operations are required for either the bottom-up or top-down traversal. Specifically, one comparison is for recording the largest edge weight of the path, and the other comparison is used to determine whether the current distance is smaller than the new one. If it is smaller, the corresponding distance value remains unchanged; otherwise, we update the value with the current one.