Method for comparing word shapes

• US 5,687,253 A
• Filed: 10/11/1994
• Issued: 11/11/1997
• Est. Priority Date: 11/19/1991
• Status: Expired due to Fees

• 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): CHANG, JON CARLTON
• Application Number:
  US08/320,775
• Time in Patent Office: 1,127 Days
• Field of Search: 382/22, 382/25, 382/10, 382/13, 382/26, 382/40, 382/57, 382/61, 382/21, 382/1, 382/9, 382/177, 382/200, 382/203, 382/229, 382/266
• US Class Current: 382/177
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

A method for determining the relative equivalency or match between two or more character strings represented in an array of image data, including the steps of determining page orientation, isolating character strings from adjacent character strings, and establishing a set of boundaries or reference lines about the character strings. Subsequently, the boundaries are used to represent the character string images as word shape contours or signals which are generated from the imaginal data within the boundaries. The word shape contours are then compared using one of the described comparison methods to determine the relative equivalency or similarity of the contours.

Claims

1. A method of determining the equivalency of a plurality of symbol strings which form word objects within data defining an image to determine a relative measure of the similarity between the symbol strings, comprising the steps of:

detecting a first discrete symbol string in the data defining the image, thereby isolating a word object represented by the first symbol string;

deriving a first contour signal representative of a shape of the first symbol string;

measuring a characteristic dimension for the first symbol string;

detecting a second discrete symbol string in the data defining the image, thereby isolating a word object represented by the second symbol string;

deriving a second contour signal representative of a shape of the second symbol string;

measuring the characteristic dimension for the second symbol string;

calculating a scaling ratio by dividing the characteristic dimension for the first symbol string by the characteristic dimension for the second symbol string;

scaling, in two-dimensions, the second contour signal in accordance with the scaling ratio, to produce a new second contour signal for subsequent comparison to the first contour signal

determining a difference signal representative of the difference between the first and second contour signals over a range in which both signals are defined; and

evaluating the difference signal over a portion of the defined range to arrive at a difference measure indicative of the relative similarity between the first and second strings.

2. The method of claim 1 further including the step of determining, in response to the difference measure, whether the first and second symbol strings are equivalent.

3. The method of claim 2 wherein the step of determining whether the first and second symbol strings are equivalent, includes the steps of:

comparing the difference measure to a predetermined threshold level; and

if the difference measure is less than the threshold level, determining that the first and second contour signals are likely to have been generated from word shapes representing identical symbol strings.

4. The method of claim 2 wherein the step of determining whether the first and second symbol strings are equivalent, includes the steps of:

comparing the difference measure with additional difference measures generated during similar comparisons of other word shapes within the array of image data; and

selecting a smallest difference measure value as being indicative of contours which are likely to have been generated from word shapes representing identical symbol strings.

5. The method of claim 1 wherein the steps of deriving a contour signal representative of the shape of the symbol string include the step of normalizing the derived contour signals in accordance with a common height dimension measured from the symbol string.

6. The method of claim 5 wherein the step of normalizing the derived contour signals in accordance with a common height dimension further includes the steps of:

measuring an x-height for the symbol string;

measuring the ascender height for the symbol string as the distance by which symbols having ascending portions protrude above the x-height;

calculating an ascender normalization ratio by dividing a predetermined ascender factor by the sum of the x-height and the ascender height; and

normalizing an upper contour signal by applying the ascender normalization ratio for those regions of the contour which represent symbols having ascenders exceeding the x-height.

7. The method of claim 5 wherein the step of normalizing the derived contour signals in accordance with a common height dimension further includes the steps of:

measuring an x-height for the symbol string;

measuring the descender height for the symbol string as the distance by which symbols having descenders protrude below a baseline determined for the symbol string;

calculating a descender normalization ratio by dividing a predetermined descender factor by the sum of the x-height and the descender height; and

normalizing a bottom contour signal by applying the descender normalization ratio for those regions of the contour which represent portions of symbols having descenders below the baseline.

8. The method of claim 1 wherein the step of determining a difference signal further includes the steps of:

finding a center of gravity for an arc formed by the first contour;

finding a center of gravity for an arc formed by the second contour;

aligning the centers of gravity for the first and second contours to determine a relative shift therebetween;

identifying, at the extremities of the contours, non-overlapping regions of the contours having only one contour defined therein;

defining, within the non-overlapping regions, the difference signal as the difference between the contour signal defined therein and a predetermined constant value; and

defining, within an overlapping region, where both contours are defined, the difference signal as the difference between the contour signals defined therein.

9. The method of claim 1 where the first and second contour signals, f(x) and g(x), respectively, are both one-dimensional signals based upon a single independent variable, x, wherein the step of determining a difference signal, d(x) representative of the difference between the first and second signals, includes the step of:

(a) evaluating the value of the first contour signal, f(x₁), where x₁ lies within the domain x_a through x_b ;

(b) evaluating the value of the second contour signal, g(x₂), where x₂ lies within the domain x_c through x_d ;

(c) calculating a difference value representative of the difference between the value of the first contour signal and the value of the second contour signal;

(d) storing the difference value;

(e) repeating steps (b) through (d) until signal g(x₂) has been evaluated at all points x₂ lying within the domain x_c through x_d ;

(f) setting the value of the difference signal at location x₁, d(x₁), equal to the the smallest stored difference value; and

(g) repeating steps (a) through (f) for all values of x₁ lying within the domain x_a through x_b, thereby defining difference signal d(x) over the domain x_a through x_b.

12. The method of claim 1 where the first and second contour signals, f(x) and g(x) respectively, are both one-dimensional signals based upon a single independent variable, x, and wherein the step of determining a difference signal representative of the difference between the first and second signals, includes the steps of:

(a) evaluating the value of the first contour signal, f(x_m), where x_m lies within the domain x_a through x_b ;

(b) evaluating the value of the second contour signal, g(x_n), where x_n lies within a subset of the domain x_c through x_d ;

(c) evaluating a difference signal, d(f(x_m),g(x_n)), representative of the difference between the value of the first contour signal and the value of the second contour signal, to determine a difference value;

(d) weighting the difference value in accordance with one or more predefined weighting factors, the selection of which is determined by the relationship between the single independent variable values x_m and x_n ;

(e) storing, in a unique memory location (m,n), the weighted difference value so as to form an array of difference values;

(f) repeating steps (b) through (e) until signal g(x_n) has been evaluated at all points x_n lying within the subset of the domain x_c through x_d ;

(g) repeating steps (a) through (f) for all values of x_m lying within the domain x_a through x_b, thereby defining the difference signal, d(f(x_m),g(x_n)), over the domain x_a through x_b ;

(h) systematically traversing the array of stored difference values, by beginning at array position (x_a,x_c), and finishing at position (x_b,x_d), while accumulating the stored difference values of all array locations along a traversal path therebetween; and

(i) repeating step (h) for all possible traversal paths, wherein the path resulting in the smallest accumulated difference value is an optimized traversal path, the accumulated value of which is a measure of the difference between the contour signals.

13. The method of claim 12 wherein the step of systematically traversing the array of stored difference values further comprises the step of constraining the relative slope of any segment of the traversal path, by limiting the set of possible array locations to which the traversal path may proceed.

14. The method of claim 12 wherein the step of evaluating the value of the second contour signal, g(x_n), where x_n lies within a subset of the domain x_c through x_d further includes the step of determining, as a function of the value of x_m and the ratio x_b /x_d, a subset of values for x_n.

15. The method of claim 12 wherein the step of evaluating the difference signal includes the steps of:

(a) calculating the value of a difference measure used to represent the relative difference between f(x_m)and g(x_n); and

(b) determining whether f(x_m) is greater than g(x_n), and if so,

multiplying the value determined in step (a) by a predetermined hill-to-valley ratio to form a product which is returned as the difference signal, otherwise returning the calculated value as the difference signal.

16. The method of claim 15 wherein the step of calculating the value of a difference measure includes subtracting g(x_n) from f(x_m) to determine the difference, and then squaring the difference.

10. The method of claim 10 wherein the step of calculating a difference value representative of the difference between the value of the first contour signal and the value of the second contour signal includes the steps of:

(a) calculating the value of a difference measure used to represent the relative difference between f(x₁) and g(x₂); and

(b) determining whether f(x₁) is greater than g(x₂), and if so,

multiplying the value determined in step (a) by a predetermined hill-to-valley ratio to form a product which is returned as the difference signal, otherwise returning the calculated value as the difference signal.

11. The method of claim 10 wherein the step of calculating the value of a difference measure includes subtracting g(x₂) from f(x₁) to determine the difference, and then squaring the difference.

17. An apparatus for determining the equivalency of a plurality of strings of symbols which form word objects within data defining an image to determine a relative measure of the similarity between the symbol strings, comprising:

isolation means for detecting first and second discrete symbol strings within the data defining the image and isolating the discrete symbol strings into word objects represented by the strings;

means for deriving a first contour signal representative of a shape of the first symbol string and a second contour signal representative of a shape of the second symbol string wherein the means for deriving contour signals includes

measurement means for determining the magnitude of a dimension common to all symbols of a symbol string, said measurement means operating on both the first and second symbol strings to produce both a first common dimension measurement and a second common dimension measurement,

means for scaling one of the contour signals, in proportion to the ratio of the first common dimension measurement with respect to the second common dimension measurement;

means for determining a difference signal representative of the difference between a magnitude of the first contour signal and a magnitude of the second contour signal over a defined range; and

arithmetic processing means for evaluating the difference signal over a portion of the defined range to arrive at a difference measure indicative of the relative similarity between the first and second string.

18. The apparatus of claim 17 further including decision means for determining, in response to the difference signal, whether the first and second symbol strings are equivalent.

19. The apparatus of claim 17 wherein the means for deriving contour signals representative of the shapes of the symbol strings comprises:

measurement means for determining a x-height of a string comprising one or more symbols;

means, employing said measurement means, for determining the x-height of the first discrete symbol string;

means, employing said measurement means, for determining the x-height of the second discrete symbol string; and

normalization means for altering the magnitudes of the first and second contour signals for those portions of the contours extending above the x-height level, in proportion to the ratio of the first symbol string x-height and the second symbol string x-height.

20. The apparatus of claim 17, where the first and second contour signals are one-dimensional signals characterized by arcs, and wherein the means for determining a difference signal comprises:

means for locating a center-of-gravity for each of the arcs defined by the first contour signal and the second contour signal;

contour shifting means for aligning the centers of gravity of the first and second contours to determine a relative shift therebetween; and

means for defining the difference signal as, the difference between the first and second contour signals in an overlapping region where both contours are defined, the difference between the first contour signal and a predetermined constant value in the non-overlapping region where only the first contour is defined, and the difference between the second contour signal and the predetermined constant value in the non-overlapping region where only the second contour is defined.

21. The apparatus of claim 17 where the first and second contour signals, f(x) and g(x), respectively, are both one-dimensional signals based upon a single independent variable, x, and wherein the means for determining a difference signal representative of the difference between the first and second signals, further includes:

signal evaluating means for determining the value of the first contour signal, f(x₁), where x₁ lies within the domain x_a through x_b ;

signal evaluating means for determining the value of the second contour signal, g(x₂), where x₂ lies within the domain x_c through x_d ;

means for producing the square of the difference between the value of the first contour signal, f(x₁), and the value of the second contour signal,g(x₂), thereby representing the difference as a positive difference value;

memory for storing the difference value;

control means for controlling the selection of the values of x₁ and x₂ which are to be evaluated and the operation of the squaring means, thereby controlling the evaluation and subsequent storage of the difference values for all possible combinations of x₁ and x₂ ;

means for selecting the smallest difference value calculated for each unique x₁ value; and

means for producing, from the selected smallest difference values, a difference signal representing the difference between the first and second contour signals.

22. The apparatus of claim 21 wherein the means for producing the square of the difference includes:

subtraction means for calculating the value of the relative difference between f(x₁) and g(x₂);

means for determining whether f(x₁) is greater than g(x₂), and if so, multiplying the relative difference by a predetermined hill-to-valley ratio to produce a weighted relative difference; and

arithmetic means for producing the square of the weighted relative difference.

23. The apparatus of claim 17 where the first and second contour signals, f(x) and g(x), respectively, are both one-dimensional signals based upon a single independent variable, x, and wherein the means for determining a difference signal representative of the difference between the first and second signals, further includes:

signal evaluating means for determining the value of the first contour signal, f(x_m), where x_m lies within the domain x_a through x_b ;

signal evaluating means for determining the value of the second contour signal, g(x_n), where x_n lies within the domain x_c through x_d ;

means for evaluating a difference signal, d(f(x_m),g(x_n)), representative of the difference between the value of the first contour signal and the value of the second contour signal, to determine a difference value;

means for selectively weighting the difference value determined by the difference signal, whereby magnitude of the weighting is determined by the relationship between the single independent variable values x_m and x_n, so that the weighted difference value reflects a relative warping of the contours required to achieve alignment of x_m and x_n ;

memory for storing the weighted difference value in an array of weighted difference values;

control means for controlling selection of the values of x_m and x_n which are to be evaluated by the evaluating means, the selective weighting means, and memory access, thereby controlling the evaluation, weighting, and subsequent storage of the weighted difference values for all possible combinations of x_m and x_n ;

means, responsive to the weighted difference values stored in the memory array, for accumulating a total difference value while systematically traversing the array, wherein the accumulating means includes the capability to determine an optimal array traversal path which will result in the minimization of the total difference value, said total difference value being a measure of the difference between the contour signals.

24. The apparatus of claim 23 wherein the means for accumulating the total difference value while systematically traversing the array further includes means for constraining the relative slope of any segment of the traversal path, by limiting the set of possible array locations to which the traversal path may proceed.

25. The apparatus of claim 23 wherein the signal evaluating means for determining the value of the second contour signal, g(x_n), includes means for limiting, as a function of the value of x_m and the ratio x_b /x_d, the domain of values, x_n, over which g(x_n) is evaluated, to a subset of those values, whereby the control means controls selection of those values in response to the limitation means.

26. A method for comparing a first string of symbols which form a word object within data defining a first image with a second string of symbols which form a word object within data defining a second image to determine a relative measure of the similarity between the first and second strings of symbols, comprising the steps of:

detecting a first discrete symbol string in the data defining the first image, thereby isolating a word object represented by the first symbol string;

deriving a first contour signal representative of a shape of the first symbol string;

detecting a second discrete symbol string in the data defining the second image, thereby isolating a word object represented by the second symbol string;

deriving a second contour signal representative of a shape of the second symbol string;

determining a difference signal representative of the difference between the first contour signal and the second contour signals over a range in which both signals are defined, wherein the step of determining a difference signal further includes the steps of

finding a center of gravity for an arc formed by the first contour,

finding a center of gravity for an arc formed by the second contour,

aligning the centers of gravity for the first and second contours to determine a relative shift therebetween,

identifying, at the extremities of the contours, non-overlapping regions of the contours having only one contour defined therein,

defining, within a non-overlapping region, the difference signal as the difference between the contour signal defined therein and a predetermined constant value, and

defining, within the overlapping region where both contours are defined, the difference signal as the difference between the contour signals defined therein; and

evaluating the difference signal over a portion of the defined range to arrive at a difference measure indicative of the relative similarity between the first and second strings.

27. The method of claim 26 including the step of determining, in response to the difference measure, whether the first and second symbol strings are equivalent.

28. The method of claim 27 wherein the step of determining whether the first and second symbol strings are equivalent, includes the step of:

comparing the difference measure to a predetermined threshold level; and

if the difference measure is less than the threshold level, determining that the first and second contour signals are likely to have been generated from word shapes representing identical symbol strings.

29. The method of claim 27 wherein the step of determining whether the first and second symbol strings are equivalent, includes the steps of:

comparing the difference measure with additional difference measures generated during similar comparisons of other word shapes within the array of image data; and

selecting a smallest difference measure value as being indicative of contours which are likely to have been generated from word shapes representing identical symbol strings.

30. The method of claim 26 where the first and second contour signals, f(x) and g(x), respectively, are both one-dimensional signals based on a single independent variable, x, wherein the step of determining a difference signal, d(x) representative of the difference between the first and second signals, includes the step of:

(a) evaluating the value of the first contour signal, f(x₁), where x₁ lies within the domain x_a through x_b ;

(b) evaluating the value of the second contour signal, g(x₂), where x₂ lies within the domain x_c through x_d ;

(c) calculating a difference value representative of the difference between the value of the first contour signal and the value of the second contour signal;

(d) storing the difference value;

(e) repeating steps (b) through (d) until signal g(x₂) has been evaluated at all points x₂ lying within the domain x_c through x_d ;

(f) setting the value of the difference signal at location x₁, d(x₁), equal to the the smallest stored difference value; and

(g) repeating steps (a) through (f) for all values of x₁ lying within the domain x_a through x_b, thereby defining difference signal d(x) over the domain x_a through x_b.

31. The method of claim 26 where the first and second contour signals, f(x) and g(x) are both one-dimensional signals based on a single independent variable, x, and wherein the step of determining a difference value representative of the difference between the first and second signals, includes the step of:

(a) evaluating the value of the first contour signal, f(x_m), where x_m lies within the domain x_a through x_b ;

(b) evaluating the value of the second contour signal, g(x_n), where x_n lies within a subset of the domain x_c through x_d ;

(c) evaluating a difference signal, d(f(x_m),g(x_n)), representative of the difference between the value of the first contour signal and the value of the second contour signal, to determine a difference value;

(d) weighting the difference value in accordance with one or more predefined weighting factors, the selection of which is determined by the relationship between the single independent variable values x_m and x_n ;

(e) storing, in a unique memory location (m,n), the weighted difference value so as to form an array of difference values;

(f) repeating steps (b) through (e) until signal g(x_n) has been evaluated at all points x_n lying within the subset of the domain x_c through x_d ;

(g) repeating steps (a) through (f) for all values of x_m lying within the domain x_a through x_b, thereby defining the difference signal, d(f(x_m), g(x_n)), over the domain x_a through x_b ;

(h) systematically traversing the array of stored difference values, by beginning at array position (x_a,x_c), and finishing at position (x₁,x_d), while accumulating the stored difference values of all array locations along a traversal path therebetween; and

(i) repeating step (h) for all possible traversal paths, wherein the path resulting in the smallest accumulated difference value is an optimized traversal path, the accumulated value of which is a measure of the difference between the contour signals.

32. The method of claim 31 wherein the step of systematically traversing the array of stored difference values further comprises the step of constraining the relative slope of any segment of the traversal path, by limiting the set of possible array locations to which the traversal path may proceed.

33. The method of claim 31 wherein the step of evaluating the value of the second contour signal, g(x_n), where x_n lies within a subset of the domain x_c through x_d further includes the step of determining, as a function of the value of x_m and the ratio x_b /x_d, a subset of values for x_n.

34. The method of claim 31 wherein the step of evaluating the difference signal includes the steps of:

(a) calculating the value of a difference measure used to represent the relative difference between f(x_m) and g(x_n); and

(b) determining whether f(x_m) is greater than g(x_n), and if so, multiplying the value determined in step (a) by a predetermined hill-to-valley ratio to form a product which is returned as the difference signal, otherwise returning the calculated value as the difference signal.

35. The method of claim 34 wherein the step of calculating the value of a difference measure includes subtracting g(x_n) from f(x_m) to determine the difference, and then squaring the difference.

36. A method for comparing a first string of symbols which form a word object within data defining an image with a known string of symbols which form a word object in order to determine a relative measure of the similarity between the first and known strings, comprising the steps of:

detecting a first discrete symbol string in the data defining the first image, thereby isolating a word object represented by the first string of symbols;

deriving a first contour signal representative of a shape of the first string of symbols;

deriving a second contour signal representative of a shape of the known string of symbols;

determining a difference signal representative of the difference between the first and second contour signals over a range in which both signals are defined;

wherein the step of determining a difference signal further includes the steps of

finding a center of gravity for an arc formed by the first contour,

finding a center of gravity for an arc formed by the second contour,

aligning the centers of gravity for the first and second contours to determine a relative shift therebetween,

identifying, at the extremities of the contours, non-overlapping regions of the contours having only one contour defined therein,

defining, within the non-overlapping regions, the difference signal as the difference between the contour signal defined therein and a predetermined constant value, and

defining, within the overlapping region where both contours are defined, the difference signal as the difference between the contour signals defined therein; and

evaluating the difference signal over a portion of the defined range to arrive at a difference measure indicative of the relative similarity between the first and second strings.

37. The method of claim 36 including the step of determining, in response to the difference measure, whether the first and known character strings are equivalent.

38. The method of claim 37 wherein the step of determining whether the first and known character strings are equivalent, includes the step of:

comparing the difference measure to a predetermined threshold level; and

if the difference measure is less than the threshold level, determining that the contours compared are likely to have been generated from word shapes representing identical character strings.

39. The method of claim 37 wherein the step of determining whether the first and known character strings are equivalent, includes the step of:

comparing the difference measure with additional difference measures generated during similar comparisons of other word shapes within the data defining the image; and

selecting the smallest difference measure values as being indicative of contours which are likely to have been generated from word shapes representing identical character strings.

40. A method for comparing a first string of symbols which form a word object within data defining an image with a known string of symbols which form a word object in order to to determine a relative measure of the similarity between the first and second strings, comprising the steps of:

(a) detecting a first discrete symbol string in the data defining the image, thereby isolating a word object represented by the first string of symbols;

(b) deriving a first contour signal f(x) representative of a shape of the first string of symbols, wherein the first contour signal f(x) is a one-dimensional signal based upon a single independent variable x;

(c) deriving a second contour signal g(x) representative of a shape of the known string of symbols, wherein the second contour signal g(x) is also a one-dimensional signal based upon the single independent variable x;

(d) determining a difference signal, d(x) representative of the difference between the first and second contour signals over a range in which both signals are defined, including the steps of;

(i) evaluating the value of the first contour signal, f(x₁), where single independent variable x₁ lies within the domain x_a through x_b ;

(ii) evaluating the value of the second contour signal, g(x₂), where single independent variable x₂ lies within the domain x_c through x_d ;

(iii) calculating a difference value representative of the difference between the value of the first contour signal and the value of the second contour signal;

(iv) storing the difference value;

v) repeating steps (ii) through (iv) until signal g(x₂) has been evaluated at all single independent variable points x₂ lying within the domain x_c through x_d ;

(vi) setting the value of the difference signal at location x₁, d(x₁), equal to the the smallest stored difference value;

(vii) repeating steps (i) through (vi) for all single independent variable points x₁ lying within the domain x_a through x_b, thereby defining difference signal d(x) over the domain x_a through x_b ; and

(e) evaluating the difference signal over a portion of the defined range to arrive at a difference measure indicative of the relative similarity between the first and second strings.

41. A method for comparing a first string of symbols which form a word object within data defining an image with a known string of symbols which form a word object in order to to determine a relative measure of the similarity between the first and second strings, comprising the steps of:

(a) detecting a first discrete symbol string in the data defining the image, thereby isolating a word object represented by the first string of symbols;

(b) deriving a first contour signal f(x) representative of the shape of the first string of symbols, wherein the first contour signal f(x) is a one-dimensional signal based upon a single independent variable x;

(c) deriving a second contour signal g(x) representative of the shape of the known string of symbols, wherein the second contour signal g(x) is also a one-dimensional signal based upon the single independent variable x;

(d) determining a difference signal d(f(x),g(x)) representative of the difference between the first and second contour signals, including steps of;

(i) evaluating the value of the first contour signal, f(x_m), where x_m lies within the domain x_a through x_b, over which the first contour signal is defined;

(ii) evaluating the value of the second contour signal, g(x_n), where x_n lies within a subset of the domain x_c through x_d, over which the second contour signal is defined;

(iii) evaluating difference signal, d(f(x_m),g(x_n)), representative of the difference between the value of the first contour signal f(x_m) and the value of the second contour signal g(x_n), where both x_m and x_n lie within a range over which the first and second contours are defined, to determine a difference value;

(iv) weighting the difference value in accordance with a predefined weighting factor, the selection of which is determined by the relationship between the single independent variable values x_m and x_n ;

(v) storing, in a unique memory location (m,n), the weighted difference value;

(vi) repeating steps (ii) through (v) until signal g(x_n) has been evaluated at all points x_n lying within the subset of the domain x_c through x_d, so as to generate an array of stored difference values;

(vii) repeating steps (i) through (vi) for all values of x_m lying within the domain x_a through x_b, thereby evaluating the difference signal, d(f(x_m),g(x_n)), over the domain x_a through x_b ;

(viii) systematically traversing the array of stored difference values, by beginning at array position (x_a,x_c), and finishing at position (x_b,x_d), while accumulating the stored difference values of all array locations along a traversal path therebetween; and

(ix) repeating step (viii) for all possible traversal paths, wherein the path resulting in the smallest accumulated difference value is an optimized traversal path, the accumulated value of which is a measure of the difference between the contour signals, indicating the relative similarity between the first and second strings.

42. The method of claim 41 wherein the step of systematically traversing the array of stored difference values further comprises the step of constraining the relative slope of any segment of the traversal path, by limiting the set of possible array locations to which the traversal path may proceed.

43. The method of claim 41 wherein the step of evaluating the value of the second contour signal, g(x_n), where x_n lies within a subset of the domain x_c through x_d further includes the step of determining, as a function of the value of x_m and the ratio x_b /x_d, a subset of values for x_n.

44. The method of claim 41 wherein the step of evaluating the difference signal includes the steps of:

(a) calculating the value of a difference measure used to represent the relative difference between f(x_m) and g(x_n); and

(b) determining whether f(x_m) is greater than g(x_n), and if so, multiplying the value determined in step (a) by a predetermined hill-to-valley ratio to form a product which is returned as the difference signal, otherwise returning the calculated value as the difference signal.

45. The method of claim 44 wherein the step of calculating the value of a difference measure includes subtracting g(x_n) from f(x_m) to determine the difference, and then squaring the difference.

46. A method for determining the relevancy, defined by the number of common words appearing in both, of two printed text documents, said documents being represented as arrays of image data, comprising the steps of:

generating word shape contours for a plurality of symbol strings within a first array of image data representing a first document based upon a difference between distances separating adjacent symbols within the strings and distances separating adjacent symbol strings therein;

generating word shape contours for a plurality of symbol strings within a second array of image data representing a second document based upon a difference between distances separating adjacent symbols within the strings and distances separating adjacent symbol strings therein;

comparing all of the word shape contours of the first array with all of the word shape contours of the second array to produce difference measures for all pairs of word shape contours compared;

determining the number of word shape pairs having difference measures below a predetermined threshold; and

based upon said number, determining what proportion of the words contained in the two documents are similar, thereby producing an indication of the relevance of the two documents.