# Instance Hard Triplet Loss for In-video Person Re-identification
## 3 Our Approach
### Instance Hard Triplet Loss  
Person re-identification is a zero-shot problem, i.e., the IDs in the test set will not appear in the training set, and we need to distinguish different IDs without seeing any of them before. Therefore,  
Figure 2: Our ReID-Head network structure. Given an input image, a backbone network is utilized for feature extraction. The extracted feature maps are then reused for both person detection through the Single Shot Detector (SSD)-Head and feature embedding through the ReID-Head. ROIAlign [46] is applied on detected bounding boxes (red bounding boxes in the figure) to obtain the final ReID features. regarding each ID as a class and training a classification network to distinguish every training IDs may have inferior performance in testing. Therefore, metric learning methods are introduced to learn a good embedding in the feature space supervised by a specific metric. The most famous metric learning method is the triplet-based metric, which was first introduced in the face recognition area [55; 56]. A triplet is composed of an anchor sample, a positive sample, and a negative sample. The triplet loss force distance between the anchor and positive samples is smaller than the distance between the anchor and negative samples by a predefined margin, which can be formulated as follows:  
\[L_{tri}=\left[D(x_{a},x_{a}^{\prime})-D(x_{a},x_{p})+\alpha\right]_{+} \tag{1}\]  
where \(x_{a}\) and \(x_{a}^{\prime}\) are the features of two different samples of person \(a\), \(x_{p}\) is a feature of another person \(p\), \(\alpha\) is a margin constant, \([z]_{+}\) is \(\max(0,z)\) to guarantee the loss is non-negative, and \(D(\cdot)\) is a distance function between two features like the Euclidean distance. Triplet loss can pull positive pairs together and push negative pairs away in the feature space. However, how to generate a proper training triplet is still a problem because there is a large number of potential combinations. Batch hard triplet loss [14] generates triplets from the training batch by choosing the hardest negative and positive samples for each anchor sample as follows:  
\[L_{BHT}=\sum_{p=1}^{P}\sum_{k=1}^{K}\left[\max_{i=1..K}D(x_{p}^{k},x_{p}^{i})- \min_{ \begin{subarray}{c}n=1..P\\ j=1..K\\ n\
eq p\end{subarray} }D(x_{p}^{k},x_{n}^{j})+\alpha\right]_{+} \tag{2}\]  
where \(x_{p}^{k}\) is the \(p^{\text{th}}\) person's \(k^{\text{th}}\) sample; there are \(P\) persons in the batch, and each person has \(K\) samples. In this way, easy triplets that benefit the training a little are discarded, and hard triplets are mined. A visualization can be seen in Figure 3a. However, there are still two problems remain:  
1. Imbalance: As shown in Equation (2) and Figure 3a, there is an imbalance between positive and negative samples that only \(K\) positive pairs, but \(P\times(K-1)\) negative pairs are compared, resulting in a harder negative sample mining. Figure 3: Visualization of the distance matrix between every two samples in a mini-batch for (**a**) the Batch Hard Triplet (BHT) and (**b**) Instance Hard Triplet (IHT) loss. Here, \(P=3\) and \(K=4\). The maximum in each green colored area and the minimum in each yellow colored area are computed, then \(K\) triplets are generated by BHT loss, and one triplet is generated by IHT loss for each person. As we can see, IHT needs less computation. 2. Computation: This requires a huge computation overhead. For \(P\times K\) samples in a batch, it needs \(P\times K\) comparisons to generate triplets, leading to a computational complexity of \(\mathcal{O}(P^{2}K^{2})\). Unlike the motivation for batch hard triplet loss [14] to find the hardest positive and negative pairs in a batch, our motivation of instance hard triplet loss derives from the observation of persons in a video sequence. As shown in Figure 4, there are multiple persons in an image frame. If we want to identify each person in the subsequent frames, we should guarantee that the feature representations are similar among those frames across time.