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    }