001 package org.hackystat.projectbrowser.page.trajectory.dtw; 002 003 import java.awt.Point; 004 import java.text.DecimalFormat; 005 import java.text.NumberFormat; 006 import java.util.ArrayList; 007 import java.util.List; 008 009 import org.hackystat.projectbrowser.page.trajectory.dtw.step.AbstractStepFunction; 010 import org.hackystat.projectbrowser.page.trajectory.dtw.step.SymmetricStepFunction; 011 012 /** 013 * Envelope for the DTW transform. 014 * 015 * @author Pavel Senin. 016 * 017 */ 018 public class DTWAlignment { 019 020 private static final String POINT_DL = " "; 021 private static final String CR = "\n"; 022 private static final String SPACE = " "; 023 private double[][] query; 024 private double[][] template; 025 private double[][] distances; 026 private double[][] costMatrix; 027 private double postDTWDistance; 028 private List<Point> path; 029 030 NumberFormat decFormatter = new DecimalFormat("####0.00"); 031 NumberFormat warpFormatter = new DecimalFormat("##0.0"); 032 NumberFormat pathFormatter = new DecimalFormat("##0"); 033 private double[] template2query; 034 private double[] query2template; 035 private double[] template2queryCoords; 036 private double[] query2templateCoords; 037 private AbstractStepFunction stepFunction; 038 039 // private List<Point> alignmentPath; 040 041 /** 042 * Set the query time-series. 043 * 044 * @param query The query time series. 045 * @throws DTWException if error occures. 046 */ 047 public void setQuery(double[][] query) throws DTWException { 048 if (null == query) { 049 throw new DTWException("Attempt to set null as the query vector."); 050 } 051 else { 052 this.query = new double[query.length][query[0].length]; 053 for (int i = 0; i < query.length; i++) { 054 for (int j = 0; j < query[0].length; j++) { 055 this.query[i][j] = query[i][j]; 056 } 057 } 058 } 059 } 060 061 /** 062 * Set the template time-series. 063 * 064 * @param template The template time series. 065 * @throws DTWException if error occures. 066 */ 067 public void setTemplate(double[][] template) throws DTWException { 068 if (null == template) { 069 throw new DTWException("Attempt to set null as the query vector."); 070 } 071 else { 072 this.template = new double[template.length][template[0].length]; 073 for (int i = 0; i < template.length; i++) { 074 for (int j = 0; j < template[0].length; j++) { 075 this.template[i][j] = template[i][j]; 076 } 077 } 078 } 079 } 080 081 /** 082 * Set the step function. 083 * 084 * @param stepPattern the selected step function. 085 * @throws DTWException if unable to select a function (invalid name provided). 086 */ 087 public void setStepFunction(String stepPattern) throws DTWException { 088 if (SymmetricStepFunction.STEP_PATTERN_P0.equalsIgnoreCase(stepPattern) 089 || SymmetricStepFunction.STEP_PATTERN_P05.equalsIgnoreCase(stepPattern) 090 || SymmetricStepFunction.STEP_PATTERN_P1.equalsIgnoreCase(stepPattern) 091 || SymmetricStepFunction.STEP_PATTERN_P2.equalsIgnoreCase(stepPattern)) { 092 this.stepFunction = new SymmetricStepFunction(stepPattern); 093 } 094 else { 095 throw new DTWException("Unable to select the step function: " + stepPattern); 096 } 097 } 098 099 /** 100 * Set the local cost matrix. 101 * 102 * @param distances The local cost-matrix. 103 * @throws DTWException if error occures. 104 */ 105 public void setDistanceMatrix(double[][] distances) throws DTWException { 106 if (null == distances) { 107 throw new DTWException("Attempt to set null as the distances matrix."); 108 } 109 else { 110 this.distances = new double[distances.length][distances[0].length]; 111 for (int i = 0; i < distances.length; i++) { 112 for (int j = 0; j < distances[0].length; j++) { 113 this.distances[i][j] = distances[i][j]; 114 } 115 } 116 } 117 } 118 119 /** 120 * Set the DTW computed path. 121 * 122 * @param path The path. 123 */ 124 private void setPath(List<Point> path) { 125 this.path = path; 126 // calculate the warping template queries 127 this.template2query = new double[template.length]; 128 for (int i = 0; i < this.template.length; i++) { 129 // check for points 130 int sum = 0; 131 int count = 0; 132 for (Point p : path) { 133 if (p.x == i) { 134 sum = sum + p.y; 135 count++; 136 } 137 if (sum == 0) { 138 template2query[i] = 0; 139 } 140 else { 141 template2query[i] = Integer.valueOf(sum).doubleValue() 142 / Integer.valueOf(count).doubleValue(); 143 } 144 145 } 146 } 147 // get coordinates for this 148 this.template2queryCoords = new double[template2query.length]; 149 for (int i = 0; i < template2query.length; i++) { 150 double idx = template2query[i]; 151 if (Math.floor(idx) == idx) { 152 this.template2queryCoords[i] = template[Double.valueOf(template2query[i]).intValue()][0]; 153 } 154 else { 155 int idxBelow = Double.valueOf(Math.floor(idx)).intValue(); 156 int idxAbove = Double.valueOf(Math.ceil(idx)).intValue(); 157 double vBelow = template[idxBelow][0]; 158 double vAbove = template[idxAbove][0]; 159 this.template2queryCoords[i] = vBelow + (vAbove - vBelow) * Math.abs(idx - Math.floor(idx)); 160 } 161 } 162 163 // calculate the warping template queries 164 this.query2template = new double[query.length]; 165 for (int i = 0; i < this.query.length; i++) { 166 // check for points 167 int sum = 0; 168 int count = 0; 169 for (Point p : path) { 170 if (p.y == i) { 171 sum = sum + p.x; 172 count++; 173 } 174 if (sum == 0) { 175 query2template[i] = 0; 176 } 177 else { 178 query2template[i] = Integer.valueOf(sum).doubleValue() 179 / Integer.valueOf(count).doubleValue(); 180 } 181 } 182 } 183 // get coordinates for this 184 this.query2templateCoords = new double[query2template.length]; 185 for (int i = 0; i < query2template.length; i++) { 186 double idx = query2template[i]; 187 if (Math.floor(idx) == idx) { 188 this.query2templateCoords[i] = query[Double.valueOf(query2template[i]).intValue()][0]; 189 } 190 else { 191 int idxBelow = Double.valueOf(Math.floor(idx)).intValue(); 192 int idxAbove = Double.valueOf(Math.ceil(idx)).intValue(); 193 double vBelow = query[idxBelow][0]; 194 double vAbove = query[idxAbove][0]; 195 this.query2templateCoords[i] = vBelow + (vAbove - vBelow) * Math.abs(idx - Math.floor(idx)); 196 } 197 } 198 199 } 200 201 /** 202 * Performs the actual alignment. 203 */ 204 public void doAlignment() { 205 206 // [1.0] using DP build the COST matrix and the best path 207 this.costMatrix = this.stepFunction.getCostMatrix(this.distances); 208 209 // [2.0] get directions matrix 210 // TODO: directions 211 212 // [3.0] do the optimal alignment tracing path backward 213 List<Point> path = new ArrayList<Point>(); 214 int i = query.length - 1; 215 int j = template.length - 1; 216 int k = 1; 217 double distance = this.costMatrix[i][j]; 218 219 // the optimal path 220 path.add(new Point(i, j)); 221 while (i + j > 0) { 222 // if we hit the border -> go along the border 223 if (i == 0) { 224 j--; 225 } 226 else if (j == 0) { 227 i--; 228 } 229 else { 230 // or if we still have some space for search 231 double[] options = { this.costMatrix[i - 1][j - 1], this.costMatrix[i - 1][j], 232 this.costMatrix[i][j - 1] }; 233 double min = Math.min(options[0], Math.min(options[1], options[2])); 234 235 if (min == options[0]) { 236 i--; 237 j--; 238 } 239 else if (min == options[1]) { 240 i--; 241 } 242 else { 243 j--; 244 } 245 } 246 k++; 247 distance += this.costMatrix[i][j]; 248 path.add(new Point(i, j)); 249 } 250 251 this.postDTWDistance = distance; 252 253 this.setPath(path); 254 } 255 256 /** 257 * {@inheritDoc} 258 */ 259 public String toString() { 260 StringBuffer sb = new StringBuffer(1000); 261 262 sb.append("$template:" + CR); 263 for (int i = 0; i < template.length; i++) { 264 double[] point = template[i]; 265 for (int j = 0; j < point.length; j++) { 266 String fp = decFormatter.format(point[j]); 267 sb.append(SPACE.substring(fp.length()) + fp); 268 } 269 sb.append(POINT_DL); 270 } 271 sb.append(CR); 272 273 sb.append("$query:" + CR); 274 for (int i = 0; i < query.length; i++) { 275 double[] point = query[i]; 276 for (int j = 0; j < point.length; j++) { 277 String fp = decFormatter.format(point[j]); 278 sb.append(SPACE.substring(fp.length()) + fp); 279 } 280 sb.append(POINT_DL); 281 } 282 sb.append(CR); 283 284 sb.append("$distance matrix:" + CR); 285 for (int i = 0; i < distances.length; i++) { 286 for (int j = 0; j < distances[i].length; j++) { 287 sb.append(decFormatter.format(distances[i][j]) + POINT_DL); 288 } 289 sb.append(CR); 290 } 291 292 sb.append("$cumulative distance matrix:" + CR); 293 for (int i = 0; i < costMatrix.length; i++) { 294 for (int j = 0; j < costMatrix[i].length; j++) { 295 sb.append(decFormatter.format(costMatrix[i][j]) + POINT_DL); 296 } 297 sb.append(CR); 298 } 299 300 sb.append("$indeces:" + CR); 301 for (int i = 0; i < path.size(); i++) { 302 String fn = pathFormatter.format(path.get(i).x); 303 sb.append(SPACE.substring(fn.length()) + fn); 304 } 305 sb.append(CR); 306 for (int i = 0; i < path.size(); i++) { 307 String fn = pathFormatter.format(path.get(i).y); 308 sb.append(SPACE.substring(fn.length()) + fn); 309 } 310 sb.append(CR); 311 312 sb.append("$warping query, template=TRUE" + CR); 313 for (int i = 0; i < this.template2query.length; i++) { 314 String fn = warpFormatter.format(template2query[i]); 315 sb.append(SPACE.substring(fn.length()) + fn + " "); 316 } 317 sb.append(CR); 318 sb.append("$warping query, template=TRUE, coords" + CR); 319 for (int i = 0; i < this.template2queryCoords.length; i++) { 320 String fn = decFormatter.format(template2queryCoords[i]); 321 sb.append(SPACE.substring(fn.length()) + fn + " "); 322 } 323 sb.append(CR); 324 325 sb.append("$warping query, template=FALSE" + CR); 326 for (int i = 0; i < this.query2template.length; i++) { 327 String fn = warpFormatter.format(query2template[i]); 328 sb.append(SPACE.substring(fn.length()) + fn + " "); 329 } 330 sb.append(CR); 331 sb.append("$warping query, template=FALSE, coords" + CR); 332 for (int i = 0; i < this.query2templateCoords.length; i++) { 333 String fn = decFormatter.format(query2templateCoords[i]); 334 sb.append(SPACE.substring(fn.length()) + fn + " "); 335 } 336 sb.append(CR); 337 338 return sb.toString(); 339 } 340 341 /** 342 * Get the DTW path. 343 * 344 * @return The DTW path. 345 */ 346 public List<Point> getPath() { 347 return this.path; 348 } 349 350 /** 351 * Get the warping query. 352 * 353 * @return The warping query. 354 */ 355 public double[] getWarpingQuery() { 356 return this.query2templateCoords.clone(); 357 } 358 359 /** 360 * Get the post-alignment distance. 361 * 362 * @return the post-alignment distance. 363 */ 364 public double getPostDistnace() { 365 return this.postDTWDistance; 366 } 367 368 }