Efficient word image retrieval using fast DTW distance
Authors:
- 1 August 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 876-880
Abstract
Dynamic time warping (DTW) is a popular distance measure used for recognition free document image retrieval. However, it has quadratic complexity and hence is computationally expensive for large scale word image retrieval. In this paper, we use a fast approximation to the DTW distance, which makes word retrieval efficient. For a pair of sequences, to compute their DTW distance, we need to find the optimal alignment from all the possible alignments. This is a computationally expensive operation. In this work, we learn a small set of global principal alignments from the training data and avoid the computation of alignments for query images. Thus, our proposed approximation is significantly faster compared to DTW distance, and gives 40 times speed up. We approximate the DTW distance as a sum of multiple weighted Eulidean distances which are known to be amenable to indexing and efficient retrieval. We show the speed up of proposed approximation on George Washington collection and multi-language datasets containing words from English and two Indian languages.Keywords
This publication has 9 references indexed in Scilit:
- Fast approximate dynamic warping kernels2015
- Document Retrieval with Unlimited Vocabulary2015
- Word spotting for historical documentsInternational Journal on Document Analysis and Recognition (IJDAR), 2006
- Dynamic time warping for isolated word recognition based on ordered graph searching techniques2005
- Two-dimensional pca: a new approach to appearance-based face representation and recognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Word image matching using dynamic time warping2003
- Video Google: a text retrieval approach to object matching in videos2003
- Aligning gene expression time series with time warping algorithmsBioinformatics, 2001
- Twenty years of document image analysis in PAMIIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000