1
2 /* ----------------------------------------------------------------------
3 * Project: CMSIS DSP Library
4 * Title: arm_dtw_path_f32.c
5 * Description: Warping path
6 *
7 * $Date: 23 April 2021
8 * $Revision: V1.9.0
9 *
10 * Target Processor: Cortex-M and Cortex-A cores
11 * -------------------------------------------------------------------- */
12 /*
13 * Copyright (C) 2010-2022 ARM Limited or its affiliates. All rights reserved.
14 *
15 * SPDX-License-Identifier: Apache-2.0
16 *
17 * Licensed under the Apache License, Version 2.0 (the License); you may
18 * not use this file except in compliance with the License.
19 * You may obtain a copy of the License at
20 *
21 * www.apache.org/licenses/LICENSE-2.0
22 *
23 * Unless required by applicable law or agreed to in writing, software
24 * distributed under the License is distributed on an AS IS BASIS, WITHOUT
25 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
26 * See the License for the specific language governing permissions and
27 * limitations under the License.
28 */
29
30 #include "dsp/distance_functions.h"
31 #include <limits.h>
32 #include <math.h>
33
34 #define E(MAT,R,C) \
35 (*((MAT)->pData + (MAT)->numCols*(R) + (C)))
36
37
38
39 /**
40 @addtogroup DTW
41 @{
42 */
43
44
45 /**
46 * @brief Mapping between query and template
47 * @param[in] pDTW Cost matrix (Query rows * Template columns)
48 * @param[out] pPath Warping path in cost matrix 2*(nb rows + nb columns)
49 * @param[out] pathLength Length of path in number of points
50 * @return none
51 *
52 * @par Warping path
53 *
54 * The warping path has length which is at most
55 * 2*(query length + template length) in float.
56 * 2 because it is a list of coordinates :
57 * (query index, template index) coordinate.
58 *
59 * The buffer pPath must be big enough to contain
60 * the warping path.
61 *
62 * pathLength is the number of points in
63 * the returned path. The resturned path
64 * may be smaller than query + template.
65 *
66 */
arm_dtw_path_f32(const arm_matrix_instance_f32 * pDTW,int16_t * pPath,uint32_t * pathLength)67 void arm_dtw_path_f32(const arm_matrix_instance_f32 *pDTW,
68 int16_t *pPath,
69 uint32_t *pathLength)
70 {
71 int q,t;
72 float32_t temp;
73
74 *pathLength = 0;
75 q=pDTW->numRows-1;
76 t=pDTW->numCols-1;
77 while((q>0) || (t>0))
78 {
79 int p=-1;
80 float32_t current=F32_MAX;
81
82 if (q>0)
83 {
84 temp = E(pDTW,q-1,t);
85 if (temp<current)
86 {
87 current=temp;
88 p=2;
89 }
90 }
91
92 if (t>0)
93 {
94 temp = E(pDTW,q,t-1);
95 if (temp<current)
96 {
97 current=temp;
98 p=0;
99 }
100 }
101
102 if ((q>0) && (t>0))
103 {
104 temp = E(pDTW,q-1,t-1);
105 if (temp<current)
106 {
107 current=temp;
108 p=1;
109 }
110 }
111
112
113
114
115
116
117
118 pPath[2 * (*pathLength)] = q;
119 pPath[2 * (*pathLength) + 1] = t;
120
121 *pathLength = *pathLength + 1;
122
123 switch(p)
124 {
125 case 0:
126 t = t-1;
127 break;
128 case 1:
129 t=t-1;
130 q=q-1;
131 break;
132 case 2:
133 q=q-1;
134 break;
135 }
136
137 }
138
139 pPath[2 * (*pathLength)] = 0;
140 pPath[2 * (*pathLength) + 1] = 0;
141 *pathLength = *pathLength + 1;
142
143 /* Reverse the path */
144 int16_t *fh,*sh;
145 fh = pPath;
146 sh = pPath + 2* (*pathLength)-2;
147 int halfLength = (*pathLength)>>1;
148 for(int i = 0; i< halfLength; i++)
149 {
150 temp = fh[0];
151 fh[0] = sh[0];
152 sh[0] = temp;
153
154 temp = fh[1];
155 fh[1] = sh[1];
156 sh[1] = temp;
157
158 fh += 2;
159 sh -= 2;
160 }
161 }
162
163 /**
164 * @} end of DTW group
165 */
166
167