A search technique for pattern recognition using relative distances

Abstract-A technique for creating and searching a tree of patterns using relative distances is presented. The search is conducted to find patterns which are nearest neighbors of a given test pattern. The structure of the tree is such that the search time is proportional to the distance hetween the test pattern and its nearest neighbor, which suggests the anomalous possibility that a larger tree, which can be expected on average to contain closer neighbors, can be searched faster than a smaller tree. The technique has been used to recognize OCR digit samples derived from NUT data at an accuracy rate of 97% using a tree of 7,000 patterns. Index Terms-Pattern recognltlon, optical character recognition, nearest neighbor, distance metric, branch and bound, NIST digit samples. I. INTRODLJCTI~N A technique for creating and searching a tree of patterns using relative distances is presented. The search is conducted to find patterns which are nearest neighbors of a given test pattern. The structure of the tree is such that the search time is proportional to the distance between the test pattern and its nearest neighbor, which suggests the anomalous possibility that a larger tree, which can be expected on average to contain closer neighbors, can be searched faster than a smaller tree. The technique has been used to recognize Optical Character Recognition (OCR) digit samples derived from National Institute of Standards and Technologies (NISI') data [I I ] at an accuracy rate of 97% using a tree of 7,000 patterns. The task of recognizing handwritten characters is an active area of research, especially in neural networks [4], [S], [lo]. This paper is an investigation of a how a particular memory-based, nearest neighbor search technique behaves when applied to a large number of patterns. As a nearest neighbor scheme, the search technique attempts to address problems encountered in dealing with many-dimensional objects 131, [51, [9], which in this case are represented by OCR patterns. The technique is intended to be applicable not only to character recognition, but to pattern recognition tasks in general. The paper is organized as follows: First, a description of the technique is presented, including the definition of distance, the insertion algorithm, and the search algorithm. The results of the NIST and other tests are then presented. Finally, a proposal is made for a device to improve the speed of searching. II. DESCRIPTION A. Distance Formula The distance between patterns Pl and P2 was chosen to be the city-block distance: where &(A, P2) = ilpl, -p2il (1) i=l N = number of pixel in the patterns pl , p2 = pixel values The city-block distance, which is the Hamming distance for binary pixel values, is possibly not the best choice; it was chosen for the Manuscrip