Feature extraction technique for use in a pattern recognition system

• US 4,700,400 A
• Filed: 10/10/1985
• Issued: 10/13/1987
• Est. Priority Date: 10/10/1985
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: The Palantir Corp. (Microsoft Corporation)
• Inventors: Ross, David J.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/786,037
• Time in Patent Office: 733 Days
• Field of Search: 382/18, 382/27, 382/56, 382/16, 382/28, 382/47
• US Class Current: 382/205
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

A method is provided for forming feature vectors representing the pixels contained in a pattern desired to be recognized, and reference patterns. One part of the feature vector is representative of the pixels contained in the pattern itself, while not requiring a very large feature vector which exactly defines each pixel of the pattern. One embodiment of this invention provides that another part of the feature vector, consisting of one or more bytes of the feature vector, defines the aspect ratio of the pattern. In one embodiment, each byte of the feature vector representing the pixels contained in the character represents the relative ratio of black pixels to total pixels in a specific area of the character; other functions relating input matrix and output feature vector information can be used. In one embodiment of this invention, those areas of the character which are defined by the feature vector together cover the entire character, providing a feature vector describing what might loosely be thought as a "blurred" version of the pattern.

Claims

1. The method of creating an output feature vector array of height P and width Q representing an input pattern, comprising the steps of:

obtaining said input pattern in the form of an input array of height N and width M;

forming an intermediate array having a height NP and width MQ;

using the information contained in said input array to provide data for said intermediate array; and

using the information contained in said intermediate array to provide data for said output feature vector array.

2. The method of claim 1 wherein said step of using the information contained in said input array to provide data for said intermediate array comprises the step of entering each element in said input array into said intermediate array Q times in the horizontal direction and P times in the vertical direction.

3. A method for extracting features of a pattern consisting of pixel data comprising the steps of:

fetching a pattern image containing a plurality of elements;

creating a blurred pattern image by applying a transformation to said pattern image comprising the steps of;

creating an intermediate array consisting of said elements of said pattern image each written P times vertically and Q times horizontally; and

creating an output array containing one or more elements of a feature vector, said output array having horizontal dimension Q and vertical dimension P, said output array consisting of the elements of said intermediate array summed in groups of N vertical elements and M horizontal elements, where N is the height of said pattern image in pixels and M is the width of the pattern image in pixels.

10. The method as in claims 3, 4, 5, 8 or 9 wherein elements of said output array represent portions of said pattern image which are equally spaced across the width of said pattern image.

11. The method as in claims 3, 4, 5, 8 or 9 wherein elements of said output array represent portions of said pattern image which are evenly spaced along the height of said pattern image.

12. The method as in claim 10 wherein said equal spacing across the width of said pattern image divides said pattern image horizontally into five equal parts.

13. The method as in claim 11 wherein said equal spacing along the height of said pattern image divides said pattern image vertically into eight equal parts.

14. The method of claims 3, 4, 5, 8 or 9 wherein said pattern image consists of binary data.

15. The method of claims 3, 4, 5, 8 or 9 wherein said pattern image represents a character.

16. The method as in claims 3, 4, 5, 8 or 9 wherein said elements of said pattern image represent grey level of pixels.

17. The method of claims 3, 4, 5, 8 or 9 wherein additional features, not related to said transformation are used as additional elements of said feature vector.

18. The method of claim 17 wherein said additional features relate to the aspect ratio of said pattern image.

19. The method of claim 18 wherein said features which relate to the said aspect ratio of said pattern image are proportional to square-root (M/N), where M is the width in pixels of said original pattern image and N is the height in pixels of said pattern image.

20. The method of claim 19 wherein said proportion is ##EQU5## where KKHEIGHT is the number of vertical elements in said feature vector.

21. The method of claims 3, 4, 5, 8 or 9 wherein selected elements of said feature vector are normalized.

22. The method of claim 21 wherein said selected elements are said elements from said transformation.

23. The method of claim 22 wherein said normalization causes said selected elements of said feature vector to be insensitive to the height or width of said pattern image.

24. The method of claim 21 wherein the norm of said selected elements of said feature vector is 256.

27. The method as in claims 3 or 4 wherein elements of said intermediate array represent said regions of said pattern image which are evenly spaced across the width of said pattern image.

28. The method as in claims 3 or 4 wherein said elements of said intermediate array represent regions of said pattern image which are evenly spaced along the height of said pattern image.

29. The method as in claim 10 wherein said even spacing across the width of said pattern image divides said pattern image horizontally into five equal parts.

30. The method as in claim 12 wherein said even spacing along the height of said pattern image divides said pattern image vertically into eight equal parts.

31. The method of claim 3, 4, or 9 wherein a weighted summation of said elements of said intermediate array is used to create said output array.

33. The method of claims 3, 4, or 9 wherein weighted summation of said elements of said pattern image is used to create said intermediate array.

4. A method for extracting features of a pattern consisting of pixel data comprising the steps of:

fetching a pattern image containing a plurality of elements;

creating a blurred pattern image by applying a transformation to said pattern image, comprising the steps of;

creating an intermediate array having a first dimension equal to the number of regions into which said pattern image is desired to be divided in said first dimension and having a second dimension equal to the number of pixels of said pattern image in said second dimension;

using counters to determine which pixel in said pattern image is to have its value added to which element of said intermediate array; and

using counters to determine which element in said intermediate array is to have its value added to which element of an output array containing a feature vector or part of a feature vector.

5. A method for extracting features of a pattern consisting of pixel data comprising the steps of:

fetching a pattern image including a plurality of elements arranged in a plurality of rows of pixels;

applying a transformation to said pixels to create a transformed input pattern; and

using said transformed input pattern to produce in an output array a feature vector, or part of a feature vector, for pattern recognition;

said transformation comprising the steps of;

generating first multiples of said pixels in a first expansion of said pattern image; and

generating second multiples of said pixels in a second expansion of said pattern; and

whereby said step of using said transformed input pattern comprises the steps of summing said first and second multiple pixels in equally sized groups, each of said sums of said first and second multiples of said pixels being a member of said feature vector.

6. A method as in claim 5 wherein the width and height of each of said groups is proportional to the width and height of said pattern image.

7. A method as in claim 6 wherein the number of pixels across the width of said pattern image divided by the number of pixels across the width of each said group is equal to the number of said groups across the width of said pattern image.

25. The method as in claims 5 or 8 wherein said step of summing is a weighted summation.

32. A method as in claim 6 wherein the number of pixels across the height of said pattern image divided by the number of pixels across the height of each said group is equal to the number of said groups across the height of said pattern image.

8. A method for extracting features of a pattern consisting of pixel data comprising the steps of:

fetching a pattern image including a plurality of elements arranged in a plurality of rows of pixels;

applying a transformation to said pixels to produce in an output array a feature vector, or part of a feature vector, for pattern recognition, said output array including a plurality of groups of elements representing corresponding rows of said output array, said transformation comprising the steps of;

summing the value of each pixel in a row of said pixels of said pattern image for a first predetermined number of times (Q) into an intermediate accumulator and advancing to the next one of said pixels in said row;

transferring the contents of said intermediate accumulator to an element of said output array and restoring said intermediate accumulator with the value of the next element of said output array after each of a second predetermined number of accumulating steps (M);

repeating said step of summing and said step of transferring for a third predetermined number of times (N) before advancing to the next group of elements of said output array; and

repeating said step of summing and said step of transferring for a fourth predetermined number of times (P) before advancing to the first element of the next row of said pixels,

wherein said first predetermined number is equal to the number of elements in a row of said output array;

wherein said second predetermined number if equal to the number of pixels in a row of said image pattern;

wherein said third predetermined number is equal to the number of rows in said output array; and

wherein said fourth predetermined number is equal to the number of rows of said image pattern.

26. The method as claimed in claims 8 or 9 wherein said first predetermined number is 5;

and wherein said third predetermined number is eight.

9. A method for extracting features of a pattern consisting of pixel data comprising the steps of:

fetching a pattern image including a plurality of elements arranged in a plurality of rows of pixels;

applying a transformation to said pixels to produce in an output array a feature vector, or part of a feature vector, for pattern recognition, said transformation comprising the steps of;

summing the value of each pixel in a row of said pixels of said pattern image for a first predetermined number of time (Q) into an intermediate accumulator and advancing to the next one of said pixels;

transferring the contents of said intermediate accumulator to an element of said intermediate array after each of a second predetermined number of summing steps (M);

advancing to the next row of said pixels and the next element of said output array when all pixels of a row of pixels is processed;

summing the value of each element in a column of said intermediate array for a third predetermined number of times (N) into an output accumulator and advancing to the next element of said intermediate array;

transferring the contents of said output accumulator to an element of said output array after each of a fourth predetermined number of summing steps (P); and

advancing to the next column of elements of said intermediate array and said elements of said output array when all elements of a column of said intermediate array are processed,

wherein said first predetermined number is equal to the number of elements in a row of said output array;

wherein said second predetermined number if equal to the number of pixels in a row of said image pattern;

wherein said third predetermined number is equal to the number of rows in said output array; and

wherein said fourth predetermined number is equal to the number of rows of said image pattern.