# Minimum Barrier Distance-Based Object Descriptor for Visual Tracking
## 3 The Proposed Algorithm
### MBD-Based Patch Weighting  
The MBD is defined by the path cost function. It is the minimum value of the barrier strength of the path between two nodes in the path [14]. The difference between MBD and a common distance function is that the length of the path may remain constant during the growth of the path, until a new, stronger barrier is encountered on the path. The MBD calculates the distance value in a digital image effectively. MBD has many interesting theoretical properties. It has proven to be a potentially useful tool in image processing [44]. When considering the variation of the seed position and the introduction of noise, it is advantageous compared to fuzzy and geodesic distance [45]. In the graph \(G(V,E)\), we set \(a=\pi(0)\), \(c=\pi(k)\) where \(\pi(i)\) represents patch \(i\). Then, a path \(\pi=<\pi(0)\), \(\pi(1),...,\pi(k)>\) on the graph refers to a sequence of patches along \(a\) to \(c\), and this sequence contains any path \(<\pi(i-1),\pi(i)>\), where \(\pi(i)\) and \(\pi(i-1)\) are adjacent \(<\pi(i-1),\pi(i)>\in E\), \(i\in\{1,...,k\}\). We use \(\Pi_{s,c}\) to denote all the paths connecting the seeds to \(c\), and \(f(\pi)\) indicates the path cost on the path \(\pi\). Then, we calculate the distance \(D(c)\) for node \(c\) to the seeds and update the distance map with the following formula:  
\[D(b)=\min_{\pi\in\Pi_{s,c}}f(\pi). \tag{2}\]  
The definition of the function \(f\) depends on the image intensity and differs for different methods. In our work, to calculate the barrier distance, we use \(G(\pi(i))\) to denote the path cost connecting \(S\) to node \(i\) on graph \(G\), and the cost function of distance transform [46] is defined as:  
\[\beta_{G}(\pi)=\max_{i=0}^{k}G(\pi(i))-\min_{i=0}^{k}G(\pi(i)) \tag{3}\]  
where \(\beta_{G}(\pi)\) returns the MBD of path \(\pi\), which is the formula for the MBD transform. Similar to the raster scan algorithm used for the geodesic distance transform [46], we need to access each patch in the raster scan or reverse raster scan in order. In the raster scan method, the distance values are propagated by sequentially scanning the image in a predefined sequence. That is, each line is scanned, first from the upper left to the lower right, and then from the lower right to the upper left until convergence (see the illustration in Figure 3). For example, when visiting a node \(x\) in a raster scan order, for each nodein the mask area of the current node \(x\) as shown in Figure 3b, we compute the MBD \(\beta_{G}(\pi_{x}\cup b)\) of \(x\) according to Equation (4). \[\beta_{G}(\pi_{x}\cup b)=\max\{H(b),G(x)\}-\min\{L(b),G(x)\} \tag{4}\]  
where \(H(b)\) and \(L(b)\) represent the highest and lowest values on \(b\), respectively, which are used to ensure the highest and lowest values of the cost on the current path, and \(H\) and \(L\) are auxiliary maps. Given the image \(G\), the seed set \(S\) is set to 0, and \(D(x)\) is initialized to \(\infty\). \(D(x)\) refers to the path cost of MBD for each path from the node \(x\) to \(S\). Then, the distance map \(D\) and the auxiliary maps are updated in a raster scan pass and an inverse raster scan pass, until the number of iterations is \(k\). The MBD is updated when the value of path costs is greater than the current maximum or less than the current minimum in the path [46; 47]. \[D(x)=\min\{D(x),\beta_{G}(\pi_{x}\cup b)\} \tag{5}\]  
where \(\pi_{x}\) refers to the path from \(x\) to \(S\), \(b\) is the adjacent node of \(x\) and \(\pi_{x}\cup b\) represents the path from the node \(x\) to \(S\) and through the node \(b\). For example, a path connects the node \(b\) to the seed set \(S\), and the edge \(<b,x>\) is appended to the path \(\pi_{b}\) to form a new edge, which is denoted as \(\pi_{x}\cup b\), each adjacent node \(b\) of \(x\) is used to minimize \(x\) iteratively. If \(\beta_{G}(\pi_{x}\cup b)<D(x)\), update \(D(x)\) to \(\beta_{G}(\pi_{x}\cup b)\). Meanwhile, update \(H(x)\) to \(\max\{H(b),G(x)\}\), \(L(x)\) to \(\min\{L(b),G(x)\}\), and then, visit the next node.