Method of deriving wordshapes for subsequent comparison

• US 5,640,466 A
• Filed: 05/13/1994
• Issued: 06/17/1997
• Est. Priority Date: 11/19/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Hopcroft, Michael J., Huttenlocher, Daniel P.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/242,692
• Time in Patent Office: 1,131 Days
• Field of Search: 382/16, 382/9, 382/10, 382/20, 382/21, 382/22, 382/25, 382/29, 382/177, 382/181, 382/190, 382/197, 382/198, 382/199, 382/203, 382/204, 382/174
• US Class Current: 382/177
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/182 by coding the contour of the pattern
• CPC Class Codes: G06V 30/184 by analysing segments intersecting the pattern

Abstract

A method for reducing an image of a character or word string to one or more one dimensional signals, including the steps of determining page orientation, isolating character strings from adjacent character strings, establishing a set of references with respect to which measurements about the character string may be made, and deriving a plurality of measurements with respect to the references in terms of a single variable signal, from which information about the symbol string may be derived.

Claims

1. A method for processing image signals including symbol strings represented therein in order to generate a word shape signal representing the symbol string shape, from which a word shape processor may derive information about a symbol string in the image, including the steps of:

a) isolating in a set of image signals discrete symbol string, wherein symbols strings are made up of a plurality of discrete symbols, and image signals representing said symbol string distinguish symbol-to-symbol spacing from symbol string-to-symbol string spacing;

b) identifying a first reference in said set of image signals with respect to the symbol string;

c) deriving a set of single independent variable measurements about at least a portion of the periphery of the symbol string with respect to the spatial relationship of the symbol string to the reference, said measurements together forming the word shape signal.

2. The method as described in claim 1 wherein the reference is a line through the symbol string.

3. The method as described in claim 1 wherein a second reference is established external to the symbol string.

4. The method as described in claim 3 wherein the first reference is a line through the symbol string.

5. The method as described in claim 4 where the measurements are distances extending perpendicularly from the second reference to one of the symbol string or the first reference, which is closer along a perpendicular measurement line.

6. The method as described in claim 5 wherein a set of points is identified defining an outer edge of the symbol string image, and the set of measurements are distances from the second reference to each member of the set of points.

7. The method as described in claim 1 wherein the measurements are distances from the reference to a set of points defining an outer edge of the symbol string.

8. A method for processing image signals including symbol strings encoded therein in order to generate a word shape signal, representing the symbol string shape, from which a word shape processor may derive information about a symbol string in the image, including the steps of:

within a set of image signals, determining orientation of a symbol string therewithin;

isolating within the image signals a discrete symbol string in the image by differentiating between spatially adjacent symbol strings, wherein symbols strings are made up of a plurality of discrete symbols, and image signals representing said symbol string distinguish symbol-to-symbol spacing from symbol string-to-symbol string spacing;

in the image signals, establishing a first reference in the image signals, external to the discrete symbol string;

defining a second reference line parallel to, and extending through, the symbol string;

deriving a set of distance measurements for each of a set of line segments from one of the symbol string and the reference line, to the first reference, and

producing a wordshape signal as a function of said measurements.

9. The method as described in claim 8, wherein the first reference includes an upper boundary line, parallel to the orientation of the symbol string, defining an upper limit of the symbol string image.

10. The method as described in claim 9, wherein the first reference includes a lower boundary line, parallel to the orientation of the symbol string, defining a lower limit of the symbol string image.

11. The method as described in claim 8, wherein the first reference includes a lower boundary line, parallel to the orientation of the symbol string, defining a lower limit of the symbol string image.

12. The method as described in claim 8, wherein the reference line has a thickness, to provide distinct upper and lower reference edges, to which distance measurement may be derived.

13. The method as described in claim 8, wherein the reference line has a thickness, defined by upper and lower reference edges, approximately one third of an x-height, determined for the symbol string, and defined with the lower edge spaced one third of the determined x-height from a lower limit of the symbol string image.

14. The method as described in claim 8, wherein a reference line is established having a thickness defined by upper and lower reference edges approximately one third of an x-height, determined for the symbol string, and defined with the upper reference edge spaced one third of the determined x-height from the upper limit of the symbol string image.

15. The method as described in claim 8, wherein the line between the symbol string or the second reference line, and the first reference is perpendicular to the orientation of the symbol string.

16. The method as described in claim 8, wherein for an image defined by an array of pixels having a resolution of N pixels per unit length, the set of measurements derived has an equal resolution.

17. The method as described in claim 8, and including the step of deriving a second set of distance measurements, equal to the difference between the distance from the first reference to the second reference line, and the first set of distance measurements.

18. A method for processing image signals including symbol strings represented therein in order to generate a word shape signal, from which a word shape processor may derive information about a symbol string in the image, including the steps of:

determining orientation of a symbol string within an image;

isolating in a set of image signals a discrete symbol string in the set of image signals by differentiating between adjacent symbol strings, wherein symbols strings are made up of a plurality of discrete symbols, and image signals representing said symbol string distinguish symbol-to-symbol spacing from symbol string-to-symbol string spacing;

defining a reference line in said image parallel to, and extending through, the symbol string;

defining a set of points along an outer edge of the symbol string;

deriving a set of distance measurements for each of a set of line segments between the reference line, and symbol string outer edge points defined, said measurements together forming the word shape signal.

19. The method as described in claim 18, wherein the reference line has a thickness, to provide distinct upper and lower reference edges, to which distance measurement may be derived.

20. The method as described in claim 18, wherein the reference line has a thickness, defined by upper and lower reference edges, approximately one third of an x-height, determined for the symbol string, and defined with the lower edge spaced one third of the determined x-height from a lower limit of the symbol string image.

21. The method as described in claim 18, wherein a reference line is established having a thickness defined by upper and lower reference edges approximately one third of an x-height, determined for the symbol string, and defined with the upper reference edge spaced one third of the determined x-height from the upper limit of the symbol string image.

22. A method for processing image signals including symbol strings represented therein in order to generate a word shape signal from an image of text, from which a word shape processor may derive information about a discrete symbol string therein, including the steps of:

a) detecting the orientation of text within a set of image signals;

b) determining within the text image signals, upper and lower limits of any lines of text;

c) operating on the text image signals to distinguish between inter-symbol spacing and inter-string spacing;

d) using said determined upper and lower limits of any lines of text, and said distinguished inter-string spacing, to define at least a first reference at least partially enclosing a discrete symbol string, wherein symbols strings are made up of a plurality of discrete symbols, and image signals representing said symbol string distinguish inter-symbol spacing from inter-string spacing;

e) establishing a reference line with respect to the symbol string and the orientation of the text, said reference parallel to the text orientation and through the symbol string image;

f) making a set of distance measurements for each of a set of line segments between the reference, and one of the enclosing reference and a periphery of the symbols string, said measurements together forming the word shape signal.

23. The method as described in claim 22, wherein the enclosing reference includes an upper boundary line, parallel to the orientation of the text, defining an upper limit of the symbol string.

24. The method as described in claim 23, wherein the enclosing reference includes a lower boundary line, parallel to the orientation of the text, defining a lower limit of the symbol string.

25. The method as described in claim 22, wherein the enclosing reference includes an lower boundary line, parallel to the orientation of the text, defining an lower limit of the symbol string.

26. The method as described in claim 22, wherein the reference line has a thickness, to provide distinct upper and lower reference edges, to which distance measurement may be made.

27. The method as described in claim 22, wherein the reference line has a thickness, to provide distinct upper and lower reference edges, to which distance measurement may be derived.

28. The method as described in claim 22, wherein the second reference line has a thickness, defined by upper and lower reference edges, approximately one third of an x-height, determined for the symbol string by the determined upper and lower limits of any lines of text, and defined with the lower edge spaced one third of the determined x-height from a lower limit of the symbol string image.

29. The method as described in claim 22, wherein a reference line is established having a thickness defined by upper and lower reference edges approximately one third of an x-height, determined for the symbol string by the determined upper and lower limits of any lines of text, and defined with the upper reference edge spaced one third of the determined x-height from the upper limit of the symbol string image.

30. The method as described in claim 22, wherein the line between the symbol string image or the reference line, and the enclosing reference is perpendicular to the orientation of the symbol string.

31. The method as described in claim 22, wherein for an image defined by an array of pixels having a resolution of N pixels per unit length, the set of measurements derived has an equal resolution.

32. The method as described in claim 22 and including the step of deriving a second set of distance measurements, equal to the difference between the distance from the enclosing reference to the reference line, and the first set of distance measurements.

33. A method for processing image signals including symbol strings represented therein in order to generate a signal representative of the shape of a symbol string in an array of image signals comprising the steps of:

a) identifying in a set of image signals a distinct symbol string in the array of image data, wherein symbols strings are made up of a plurality of discrete symbols, and image signals representing said symbol string distinguish symbol-to-symbol spacing from symbol string-to-symbol string spacing;

b) identifying a reference with respect to which the shape signal will be derived for the symbol string;

c) representing the periphery of the identified symbol string as a closed curve; and

d) for a selected portion of said closed curve, representing said selected portion as a word shape signal f(t) derived with respect to said reference.

34. A method for processing image signals including symbol strings represented therein in order to generate a word shape signal representative of the shape of a symbol string in an array of image signals from which a word shape processor may derive information about the symbol string, comprising the steps of:

a) about a selected symbol string in a set of image signals, represented by the signal I(x,y), defining a closed boundary uniquely enclosing said selected symbol string in the array of image signals;

b) deriving from signal I(x,y) the edge signal E(x,y) representing the edges of I(x,y) detected within the closed boundary;

c) augmenting with additional data I(x,y), such that E(x,y) is a signal E'"'"'(x,y) defined at every sampling point over a range of signals;

d) representing a portion of E'"'"'(x,y) as a signal f(t), where f(t) is a single independent variable representation of at least a portion of the shape of said selected symbol string forming the word shape signal.

35. Apparatus for generating a word shape signal representative of the shape of a string of symbols in an image, from which a word shape processor may derive information about the string, comprising:

means for generating a set of image signals representative of a visually perceptible image upon printing or displaying, said image including strings of symbols, wherein strings of symbols include a plurality of discrete symbols, and image signals representing said strings distinguish inter-symbol spacing from inter-string spacing;

a first memory storing image signals received from the image signal generating means for subsequent processing;

a signal processor operably connected to said first memory to receive signals stored therein, operating in a preprogrammed mode on said image signals to isolate a set of string image signals in the set of image signals;

said signal processor operating in a preprogrammed mode on said isolated string image signals to derive a set of single independent variable measurements about at least a portion of the periphery of the string with respect to a spatial relationship of the string with a reference in the image;

said signal processor using said set of single independent variable measurements to form a word shape signal as a function thereof; and

said signal processor storing the wordshape signals to a second memory, storing the wordshape signal.

36. The apparatus as described in claim 35 wherein the reference is a line through each symbol forming the string.

37. The apparatus as described in claim 35 wherein a second reference is established in the image external to the string.

38. The apparatus as described in claim 37 wherein the first reference is a line through each symbol forming the string.

39. The apparatus as described in claim 38 where the measurements are distances extending perpendicularly from the second reference to one of the string or the first reference, whichever is closer along a perpendicular measurement line.

40. The apparatus as described in claim 39 wherein a set of points determined as a function of a resolution of the image signal generating means is identified defining an outer edge of the symbol string image, and the set of measurements are distances from the second reference to each member of the set of points.

41. The apparatus as described in claim 35 wherein the measurements are distances from the reference to a set of points determined as a function of a resolution of the image signal generating means defining an outer edge of the symbol string image.