# Object-Based Time-Constrained Dynamic Time Warping Classification of Crops Using Sentinel-2
## 2 Materials and Methods
### Dynamic Time Warping  
#### 2.3.1 Theoretical Background  
By combining time warping with distance measurements between elements of sequences, DTW is a nonlinear warping algorithm that decomposes a complex global optimization problem into local optimization problems using dynamic programming principle [23]. DTW has the advantage of time flexibility and was proven to achieve better results than the Euclidean distance measure for MODIS NDVI time series clustering [63]. Euclidean distance is a time-rigid method of comparing two sequences where each element of a sequence is compared with its associated element from the other sequence. DTW, on the other hand, is a time-flexible method that considers the temporal distortions of the time series (Figure 6), which can be associated with amplitude scaling or translation, time scaling or translation, shape changes, or noise in the data [64].  
The DTW algorithm works as follows. Suppose we have two sequences, \(A=(a_{1}\),..., \(a_{S})\) and \(B=(b_{1}\),..., \(b_{T})\) of length \(S\) and \(T\) respectively. Let \(\delta\) be a distance between coordinates of sequences and m[S,T] a cost matrix. For single-band DTW, where each element of the sequence is a one-dimensional vector, we used \(\delta\) as the squared Euclidean distance, in accordance with previous studies (Equation (1)) [11; 65]. For multi-band DTW, where each element of the sequence is a multi-dimensional vector, we used a 5-dimensional \(\delta\) in the computation of DTW. This is preferable to computing DTW individual for every dimension and then merge the results and gives a single alignment of the two multi-dimensional sequences compared. Using a multi-dimensional \(\delta\) in computing DTW is recommended for remote sensing applications, where the dimensions are correlated phenomena [11]. For multi-band DTW we used the Euclidean distance to compare the elements of time series, as in Equation (2).  
\[\delta\big{(}a_{i},\ b_{j}\big{)}\ =\big{(}a_{i}-b_{j}\big{)}^{2}, \tag{1}\]  
where \(a_{i}\) and \(b_{j}\) are elements of one-dimensional sequences \(A\) and \(B\).  
\[\delta\big{(}a_{i},\ b_{j}\big{)}\ =\ \sqrt{\sum_{f=1}^{F}\big{(}a_{if}-b_{jf} \big{)}^{2}}, \tag{2}\]  
where \(a_{if}\) and \(b_{jf}\) are elements of the feature \(f\) of multi-dimensional sequences \(A\) and \(B\), with \(F\) number of features.  
Computing the alignment and comparison of the two sequences can be done recursively using Equation (3). Briefly, the computation of the entire DTW matrix starts by generating the first column and the first row, then the matrix is computed from left to right and from top to bottom, for each element being required the minimum between the upper, left, and the diagonal elements of the matrix [11]. In the end, the last element of the matrix from the bottom right indicates the degree of dissimilarity  
Figure 6: Comparison between two sequences: (**a**) while Euclidean distance is time-rigid, (**b**) the dynamic time warping (DTW) is time-flexible in dealing with possible time distortion between the sequences. This flexibility is desirable for crop mapping, to deal with the intra-class phenological discrepancies caused by different environmental conditions.  
between the two compared sequences, i.e., phenological temporal patterns. The smaller the DTW dissimilarity between two sequences, the similar are the two compared sequences.  
\[D\Big{(}A_{i},\ B_{j}\Big{)}=\delta\Big{(}a_{i},\ b_{j}\Big{)}+min\left\{\begin{array} []{l}\Big{(}A_{i-1},B_{j-1}\Big{)}\\ \Big{(}A_{i-1},\ B_{j}\Big{)}\\ \Big{(}A_{i},\ B_{j-1}\Big{)}\end{array}\right. \tag{3}\]  
where \(\Big{(}A_{i-1},B_{j-1}\Big{)}\), \(\Big{(}A_{i-1},\ B_{j}\Big{)}\), and \(\Big{(}A_{i},\ B_{j-1}\Big{)}\) are the upper left, upper and left neighboring elements of the \(\Big{(}A_{i},\ B_{j}\Big{)}\) element of the DTW matrix.