DTW instead of Hausdorff Distance


DTW is normally applied to time series and similar 1D signals. However, the text contours are 2D and we weren't able to identify any 2D DTW function in the literature. There are two main problems in applying a 1D comparison method to a 2D feature.

  1. DTW assumes the feature is sorted. In histogram/projection features the signal is sorted naturally but in contours this is not the case. The components may be rotated a bit, hence their contours are not aligned. In such cases DTW fails to compare similar elements.

  2. The comparison of two coordinates can be done in more than one way. It's possible to use Euclidean, Manhattan or any other kind of distance metric and these should be tested.

The first problem is related about the lack of natural ordering in feature descriptors. We can solve this by sorting the contour points with a common criteria. Nevertheless as the circular positioning of the coordinates have no natural beginning, we also don't have a guarantee that a slight rotation of a component won't disturb the feature robustness.

The following algorithm is applied to overcome these problems.

  1. Points are sorted clockwise w.r.t to the center of a component.
  2. 20% of the points from the beginning are also repeated at the end of the sequence to alleviate the slight rotation problem.
  3. Each point is measured with another point using a robust metric. This is either Euclidean or Manhattan.

We used Cython to implement this algorithm and evaluated the performance in our Ottoman Lithography dataset.

Comments !