Computational considerations

Representing objects by several local features involves a computational problem if the number of local features to represent one object is very large. The $k$-NN algorithm needs to compare every local feature of a test object with every local feature of every training object. This high computational cost is considerably reduced by using a fast approximate $k$-nearest neighbor search technique [9].

Figure 4: Examples of digits misclassified by the local feature approach, but correctly classified by the tangent distance classifier (first row, note the variation in line thickness and affine changes) and vice versa (second row, note the missing parts and clutter).