Fast and Accurate Handwritten Character Recognition Using Approximate Nearest Neighbours Search on Large Databases

摘要

In this work, fast approximate nearest neighbours search algorithms are shown to provide high accuracies, similar to those of exact nearest neighbour search, at a fraction of the computational cost in an OCR task. Recent studies have shown the power of k-nearest neighbour classifiers (k-nn) using large databases, for character recognition. In those works, the error rate is found to decrease consistently as the size of the database increases. Unfortunately, a large database implies large search times if an exhaustive search algorithm is used. This is often cited as a major problem that limits the practical value of the k-nearest neighbours classification method. The error rates and search times presented in this paper prove, however, that k-nn can be a practical technique for a character recognition task.