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 *
51 * @par Warping path
52 *
53 * The warping path has length which is at most
54 * 2*(query length + template length) in float.
55 * 2 because it is a list of coordinates :
56 * (query index, template index) coordinate.
57 *
58 * The buffer pPath must be big enough to contain
59 * the warping path.
60 *
61 * pathLength is the number of points in
62 * the returned path. The resturned path
63 * may be smaller than query + template.
64 *
65 */
arm_dtw_path_f32(const arm_matrix_instance_f32 * pDTW,int16_t * pPath,uint32_t * pathLength)66 ARM_DSP_ATTRIBUTE void arm_dtw_path_f32(const arm_matrix_instance_f32 *pDTW,
67 int16_t *pPath,
68 uint32_t *pathLength)
69 {
70 int q,t;
71 float32_t temp;
72
73 *pathLength = 0;
74 q=pDTW->numRows-1;
75 t=pDTW->numCols-1;
76 while((q>0) || (t>0))
77 {
78 int p=-1;
79 float32_t current=F32_MAX;
80
81 if (q>0)
82 {
83 temp = E(pDTW,q-1,t);
84 if (temp<current)
85 {
86 current=temp;
87 p=2;
88 }
89 }
90
91 if (t>0)
92 {
93 temp = E(pDTW,q,t-1);
94 if (temp<current)
95 {
96 current=temp;
97 p=0;
98 }
99 }
100
101 if ((q>0) && (t>0))
102 {
103 temp = E(pDTW,q-1,t-1);
104 if (temp<current)
105 {
106 current=temp;
107 p=1;
108 }
109 }
110
111
112
113
114
115
116
117 pPath[2 * (*pathLength)] = q;
118 pPath[2 * (*pathLength) + 1] = t;
119
120 *pathLength = *pathLength + 1;
121
122 switch(p)
123 {
124 case 0:
125 t = t-1;
126 break;
127 case 1:
128 t=t-1;
129 q=q-1;
130 break;
131 case 2:
132 q=q-1;
133 break;
134 }
135
136 }
137
138 pPath[2 * (*pathLength)] = 0;
139 pPath[2 * (*pathLength) + 1] = 0;
140 *pathLength = *pathLength + 1;
141
142 /* Reverse the path */
143 int16_t *fh,*sh;
144 int16_t itemp;
145 fh = pPath;
146 sh = pPath + 2* (*pathLength)-2;
147 int halfLength = (*pathLength)>>1;
148 for(int i = 0; i< halfLength; i++)
149 {
150 itemp = fh[0];
151 fh[0] = sh[0];
152 sh[0] = itemp;
153
154 itemp = fh[1];
155 fh[1] = sh[1];
156 sh[1] = itemp;
157
158 fh += 2;
159 sh -= 2;
160 }
161 }
162
163 /**
164 * @} end of DTW group
165 */
166
167
