TWO TREE­FORMATION METHODS AND FAST PATTERN SEARCH USING NEAREST NEIGHBOR AND NEAREST­CENTROID MATCHING

Microsoft, Motorola, Siemens, Hitachi, NICI, IUF This paper describes tree­based classification of character images, comparing two methods of tree formation and two methods of matching: nearest neighbor and nearest centroid. The first method, Preprocess Using Relative Distances (PURD) is a tree­based reorganization of a flat list of patterns, designed to speed up nearest­ neighbor matching. The second method is a variant of agglomerative hierarchical clustering (HCLUS) which aims at finding a hierarchical structure of centroids in the pattern space. Results indicate that the PURD method is a very fast, effective and convenient method for the speedup of 1NN search, from which it is, however, difficult to derive usable character prototypes. HCLUS can be used to obtain very fast search with acceptable classification rate while providing character prototypes, however, at the cost of significant training efforts.