A Multi-stroke Dynamic Time Warping Distance Based on A* Optimization

摘要

Dynamic Time Warping (DTW) is a famous distance to compare two mono-stroke symbols. It obeys the boundary and continuity constraints. The extension to multi-stroke symbols raises specific problems. A naïve solution is to convert the multi-stroke symbol into a single one by a direct concatenation respecting the handwriting order. However, people may write a symbol with different stroke orders and different stroke directions. Applying a brute force method by searching all the possible directions and orders leads to prohibitive calculation times. To reduce the searching complexity, we propose the DTW-A* algorithm that keeps the continuity constraint during each partial matching. This DTW-A* distance achieves the best recognition rate and the best stability in cross-validation when comparing three distances (DTW-A*, DTW, Modified Hausdorff Distance) on a flowchart dataset which mainly contains multi-stroke symbols.