# Retrieval of Similar Evolution Patterns from Satellite Image Time Series +
## 2 Materials and Methods
### Dynamic Time Warping (DTW)  
The first step in retrieving spatio-temporal patterns that are similar to a given query is to measure the degree of similarity between the query sequence and the rest of the sequences. This can be achieved through Dynamic Time Warping, which has been widely used in many applications related to speech recognition [5] and DNA analysis [6]. The method is usually applied to find the optimal alignment path between two sequences, \(U_{1}^{T}=(\mathbf{u}_{1},\ldots,\mathbf{u}_{T})\) and \(V_{1}^{T^{\prime}}=(\mathbf{v}_{1},\ldots,\mathbf{v}_{T^{\prime}})\), which may have different lengths (i.e., \(T\
eq T^{\prime}\)) [17]. This is a frequently met situation in SITS analysis due to technological artifacts or cloud cluttering problems that may occur in images captured by optical remote sensing sensors. Mathematically, the DTW distance measure between two sequences, \(U_{1}^{i}=(\mathbf{u}_{1},\ldots,\mathbf{u}_{i})\) and \(V_{1}^{j}=(\mathbf{v}_{1},\ldots,\mathbf{v}_{j})\), can be recurrently defined as  
\[D_{i,j}=\delta(\mathbf{u}_{i},\mathbf{v}_{j})+\text{min}(D_{i-1,j-1},D_{i-1,j},D_{i,j-1}) \tag{1}\]  
where \(\delta\) is the Euclidean distance between two current elements \(\mathbf{u}_{i}\) and \(\mathbf{v}_{j}\) of the sequences, \(D_{k,l}\) is the partial similarity score between \(U_{1}^{k}\) and \(V_{1}^{j}\) for any \(k\leq T\) and \(l\leq T^{\prime}\). As can be observed from the above equation, the optimization problem aims at finding the best alignment between subsequences of \(U_{1}^{T}\) and \(V_{1}^{T^{\prime}}\). In the above formulation, the following initial conditions are considered:  
\[D_{1,1} =\delta(\mathbf{u}_{1},\mathbf{v}_{1}) \tag{2}\] \[D_{1,j} =\sum_{p=1}^{j}\delta(\mathbf{u}_{1},\mathbf{v}_{p})\] (3) \[D_{i,1} =\sum_{q=1}^{i}\delta(\mathbf{u}_{q}.\mathbf{v}_{1}). \tag{4}\]  
Figure 2: The flowchart of the proposed retrieval of similar patterns in SITS. The overall DTW similarity between \(U_{1}^{T}\) and \(V_{1}^{T^{\prime}}\) is given by the score \(D_{T,T^{\prime}}\). Computing the overall score is equivalent to determining the elements of a \(T\times T^{\prime}\) distance matrix where the element on row \(i\) and column \(j\) is \(D_{i,j}\). The recurrence relation used in the computation of the DTW similarity score implies the computation of a \(T\times T^{\prime}\) matrix, whose elements are the distances \(D_{i,j}\) (\(1\leq i\leq T\), \(1\leq j\leq T^{\prime}\)). Each distance \(D_{i,j}\) uses the smallest value between the closest previous neighbors in the matrix. The DTW matrix is computed from left to right and top to bottom. The last element \(D_{T,T^{\prime}}\) represents the overall DTW score of similarity, whilst the path that is followed to compute the score of similarity provides the optimal alignment. An example of DTW-based optimal alignment together with the DTW distance matrix \(D\) is shown in Table 1 for two sequences of one-dimensional elements. In this example, we considered that \(\delta\) is the difference in absolute values of the elements. The element on the lower-right of the matrix is the total score of the similarity between the two sequences. If the similarity scores are computed between spatio-temporal sequences in a multispectral SITS, the sequences are formed by the vector elements \(\mathbf{u}_{i}\) and \(\mathbf{v}_{j}\) whose dimensions are given by the number of frequency bands used by the remote sensing sensors. Let us denote by \(c\) the number of spectral bands. Then, \(\delta\) is the Euclidean distance between two vector elements in a space with \(c\) dimensions:  
\[\delta(\mathbf{u}_{i},\mathbf{v}_{j})=\sqrt{\sum_{k=1}^{c}(u_{i,k}-v_{j,k})^{2}} \tag{5}\]  
where \(\mathbf{u}_{i}=[u_{i,1},\ldots,u_{i,c}]^{T}\) and \(\mathbf{v}_{j}=[v_{j,1},\ldots,v_{j,c}]^{T}\). The DTW similarity score is computed between the query provided by the user and each spatio-temporal sequence in the SITS.