# Fine-Grained Action Recognition by Motion Saliency and Mid-Level Patches
## 3 Mid-Level Patch Mining Based on Motion Saliency
### Object Proposal Generation by the Idea of the Huffman Algorithm
However, only adjacent regions can be merged, which means that only the similarity between adjacent regions needs to be calculated. If the average number of neighborhoods of each region is \(n^{\prime}\), the number of pairs to be calculated is \(n\times n^{\prime}\). In most cases, \(n^{\prime}\ll n\) can greatly mitigate the computation costs. Furthermore, a new non-terminal node in each iteration only affects the surrounding regions so that only information about these adjacent nodes needs to be updated. The variables involved in the algorithm are as follows. \(i\) and \(j\) are the numbers of two adjacent regions, respectively. \(A_{i}\) denotes the set of object proposals adjacent to region \(p_{i}\), and \(D_{i}\) represents the properties of \(p_{i}\), i.e., the region size, the color, and the motion saliency. \(P_{i,j}\) denotes the similarity between the object proposal \(p_{i}\) and \(p_{j}\), where \(p_{j}\in A_{i}\), and vice versa. For each step of the region merging, two regions with the highest similarity in all adjacent region pairs are selected where the similarity is related to \(D\). The object proposal generation algorithm is shown in Algorithm 1. Figure 5 shows the object proposal extraction results of our algorithm and the Selective Search algorithm [22]. It can be seen from the figure that the two algorithms can effectively extract the interaction regions. Both of them first partition the image into candidate regions, and then merge these regions with a Huffman-like algorithm. However, our algorithm generates the candidate regions based on the motion saliency that has a natural advantage in action recognition. Most object proposals segmented by the two algorithms are the same, but the regions in this paper are more accurate. For example, the motion information of the regions are stronger and the static objects are basically excluded. Take the action \"wash hands\" in Figure 5 as an example, the object \"knife\" is irrelevant to the action. In the first image in Figure 5b, the object \"knife\" is regarded as background by motion region segmentation with the proposed method. In the first image in Figure 5c, the object \"knife\" is extracted as an object proposal with the Selective Search [22]. Furthermore, this object will still be  
regarded as foreground even with traditional background segmentation methods [51] because the object \"knife\" does not belong to the background. ```
1: Initialization: The segmentation threshold is calculated according to the motion saliency map, and initial motion saliency regions in the foreground image are \(P^{0}=\{p_{1}^{0},p_{2}^{0},\cdots,p_{n}^{0}\}\);
2:\(\forall p_{i}^{0}\in P^{0}\), compute \(D_{i}\) and \(A_{i}\);
3: Compute the similarity between adjacent regions, \(PS=\left\{P_{i,j}|\forall p_{i}\in P^{0}\text{ and }p_{j}\in A_{i}\text{ and }i>j\right\}\);
4:\(k=0\); \(m=n\); \(regionset=P^{0}\); // \(m\) is the number of the current object proposals;
5:while\(\left(len\left(P^{k}\right)>1\right)\) & \(\left(\text{ }if\text{ exist }A_{i}!=\emptyset,p_{i}^{k}\in P^{k}\right)\)do
6:\(k=k+1\);
7:\(m=m+1\);
8:\(P_{i,j}=\max\left(PS\right)\);
9:\(P^{k}=\left(P^{k-1}\cup\{p_{m}\}\right)-\left\{p_{i}^{k-1},p_{j}^{k-1}\right\}\);
10: compute \(D_{m}\) according to \(D_{i}\) and \(D_{j}\);
11:\(A_{m}=A_{i}\cup A_{j}-\left\{p_{i}^{k-1},p_{j}^{k-1}\right\}\);
12:\(\forall p_{v}^{k-1}\in A_{m}\), \(A_{v}=\left(A_{v}\cup\{p_{m}\}\right)-\left\{p_{i}^{k-1},p_{j}^{k-1}\right\}\);
13:\(PS=\left(PS\cup\{P_{m,o}|p_{o}\in A_{m}\}\right)-\left\{P_{u,v}|u,v=i\,orj\}\right\);
14:endwhile
```  
**Algorithm 1** Object proposal generation algorithm. Figure 5: Results of object proposal extraction of our algorithm and Selective Search. The red boxes represent the object proposals. The action categories of these three groups of images are “wash hands”, “put in bowl”, and “peel”.