Image processing using distance as a function of direction

• US 5,245,674 A
• Filed: 07/30/1991
• Issued: 09/14/1993
• Est. Priority Date: 07/30/1991
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Cass, Todd A., Huttenlocher, Daniel P., Wayner, Peter C.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/737,957
• Time in Patent Office: 777 Days
• Field of Search: 382/18, 382/20, 382/21, 382/22, 382/39, 382/68, 382/16
• US Class Current: 382/200
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/146 Aligning or centring of the image pick-up or image-field

Abstract

Characteristics of images such as skew of lines of text or dominant typeface of characters are detected by producing distance data. Distance data is produced for each of a number of starting pixels within an image. Each starting pixel meets a criterion, such as an edge pixel or a pixel inside a connected component. Each starting pixel'"'"'s distance data indicates the distance in each of a number of directions from the starting pixel to another pixel at which the image meets another criterion. For example, to detect skew of lines of text, the distance data can indicate distance from a starting pixel at an edge across white pixels to another edge. To detect dominant typeface, the distance data can indicate distance from a starting pixel at an edge or inside a connected component across black pixels to another edge. The separating angle between adjacent directions can be small enough to detect features of an appropriate size at an appropriate distance, such as features of character size at the average intercharacter spacing. The distances at each direction from all the starting pixels can be averaged to obtain a combined distance at each direction. A sufficient number of starting pixels can be used so that the combined distance is approximately the same as if every pixel in the image were a starting pixel. The combined distances at all the directions form a profile.

Claims

1. A method of performing image processing on an image that includes a plurality of locations;

the method comprising a plurality of choosing acts, each choosing act choosing a starting location;

the plurality of choosing acts together choosing a set of starting locations that includes more than one of the locations in the plurality of locations;

the method comprising, for each of the starting locations in the set, a plurality of distance obtaining acts, each distance obtaining act for a respective one of a plurality of directions;

each direction'"'"'s respective distance obtaining act obtaining respective distance data with respect to the starting location in the set;

the direction'"'"'s distance data indicating a distance in the direction from the starting location in the set to a respective other location at which the image meets a criterion;

the method further comprising an act of combining the respective distance data for each direction for all of the starting locations in the set to obtain combined distance data for each direction;

the plurality of choosing acts together choosing the set of starting locations so that the combined distance data for each direction indicate, for the image, distance in the direction to a location at which the image meets the criterion.

2. The method of claim 1 in which each of the plurality of locations is a pixel.

3. The method of claim 1 in which each distance obtaining act for each starting location in the set comprises:

starting at the starting location in the image; and

for each of a sequence of locations along a line extending from the starting location in the direction through the image, obtaining respective length data indicating length from the starting location to the location along the line;

the sequence including the respective other location at which the image meets the criterion;

the respective length data of the respective other location being the direction'"'"'s distance data.

4. The method of claim 3 in which each of the plurality of locations is a pixel and the criterion is an edge.

5. The method of claim 4 in which the respective other location at which the image meets the criterion is a black pixel separated from the starting location by white pixels;

the distance data indicating length across the white pixels between the starting location and the respective other location at which the image meets the criterion.

6. The method of claim 4 in which the respective other location at which the image meets the criterion is a white pixel separated from the starting location by black pixels;

the distance data indicating length across the black pixels between the starting location and the respective other location at which the image meets the criterion.

7. The method of claim 1 in which the plurality of directions includes adjacent first and second directions separated by a separating angle, the separating angle being small enough that the first direction'"'"'s distance data and the second direction'"'"'s distance data for each of the starting locations indicate whether the image contains a blob subtending the first and second directions within a limiting distance from the starting location.

8. The method of claim 7 in which the image has an outer dimensions and the limiting distance is equal to the outer dimension.

9. The method of claim 7 in which each of the plurality of directions is separated from each adjacent direction by an angle approximately equal to the separating angle.

10. The method of claim 7 in which the image includes blobs that form text that includes characters, adjacent ones of the characters being separated by intercharacter distances;

the limiting distance being approximately equal to an average of the intercharacter distances so that the first direction'"'"'s distance data and the second direction'"'"'s distance data for each of the starting locations indicate whether the image contains a character subtending the first and second directions within the limiting distance from the starting location.

11. The method of claim 1 in which the act of combining comprises obtaining an average of the distances indicated by the respective distance data for each direction for all of the starting locations in the set.

12. The method of claim 1 in which the plurality of choosing acts together choose the set of starting locations so that the set includes a smaller number of locations than the image.

13. The method of claim 1, further comprising an act of storing each direction'"'"'s combined distance data in memory so that the direction'"'"'s combined distance data is accessible using direction data indicating the direction.

14. The method of claim 1 in which the image includes lines of characters at a skew;

the method further comprising an act of using the combined distance data of all the directions to obtain skew data indicating the skew.

15. The method of claim 1 in which the image includes characters having a dominant typeface;

the method further comprising an act of using the combined distance data of all the directions to obtain typeface data indicating the dominant typeface.

16. The method of claim 1 in which the combined distance data for all the directions form a profile of distance as a function of direction;

the method further comprising an act of comparing the profile formed by the combined distance data with a set of model profiles of distance as a function of direction.

17. The method of claim 1 in which the combined distance data for all the directions form a profile of distance as a function of direction;

the method further comprising an act of providing the profile formed by the combined distance data to a storage medium.

18. The method of claim 1 in which the combined distance data for all the directions form a profile of distance as a function of direction;

the method further comprising an act of providing the profile formed by the combined distance data to a transmission medium.

19. An image processing machine comprising:

memory;

the memory storing image data defining an image that includes a plurality of locations; and

a processor connected for accessing the memory;

the memory further storing instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, choosing a set of starting locations that includes more than one of the plurality of locations in the image;

the processor, in executing the instructions, using the image data to obtain, for each of a plurality of directions, respective distance data with respect to each of the starting locations in the set;

each direction'"'"'s distance data for each starting location indicating a distance in the direction from the starting location to a respective other location at which the image meets a criterion;

the processor, in executing the instructions, combining the respective distance data for each direction for all of the starting locations in the set to obtain combined distance data for each direction;

the processor choosing the set of starting locations so that the combined distance data for each direction indicate, for the image, distance in the direction to a location at which the image meets the criterion.

20. The machine of claim 19, in which the image data include, for each location in the image, a respective data item indicating a respective value;

the processor, in obtaining each direction'"'"'s respective distance data for each starting location, obtaining length data indicating a length along a line from the starting location in the direction;

the processor, in obtaining each direction'"'"'s respective distance data for each starting location, using the length data to access the respective data item of a second location at the indicated length in the direction from the starting location to determine whether the second location'"'"'s value meets the criterion.

21. The machine of claim 20 in which the processor, in obtaining each direction'"'"'s respective distance data for each starting location, stores the length data when the second location'"'"'s value meets the criterion;

the stored length data being the distance data for the direction.

22. The machine of claim 21 in which the processor stores the length data so that it can be accessed using direction data indicating the direction.

23. The machine of claim 19 in which the processor combines the respective distance data by obtaining an average of the distances indicated by the respective distance data for each direction for all of the starting locations.

24. The machine of claim 19 in which the processor comprises a plurality of processing units, the memory comprising respective local memory for each processing unit;

the image data including, for each location in the image, a respective data item indicating a respective value, each processing unit'"'"'s respective local memory being for storing the respective data item of a respective location in the image;

the processing units executing the instructions in parallel.

25. The machine of claim 19 in which the image includes lines of characters at a skew;

the processor, in executing the instructions, using the combined distance data to obtain skew data indicating the skew.

26. The machine of claim 19 in which the image includes characters having a dominant typeface;

the processor, in executing the instructions, using the combined distance data to obtain typeface data indicating the dominant typeface.

27. The machine of claim 19 in which the combined distance data for all the directions form a profile of distance as a function of direction;

the memory storing a set of model profiles of distance as a function of direction, the processor, in executing the instructions, comparing the profile formed by the combined distance data with the model profiles.

28. The machine of claim 27, further comprising input means for receiving data from sources outside the machine, the processor being connected for receiving data from the input means, the processor, in executing the instructions, receiving the set of model profiles and storing the set of model profiles in memory.

29. The machine of claim 28 in which the input means is for receiving data from a storage medium.

30. The machine of claim 28 in which the input means is for receiving data from a transmission medium.

31. The machine of claim 19 in which the combined distance data for all the directions form a profile of distance as a function of direction;

the machine further comprising output means for providing data to destinations outside the machine;

the processor being connected for providing data to the output means, the processor, in executing the instructions, providing the profile formed by the combined distance data to the output means.

32. The machine of claim 31 in which the output means is for providing data to a storage medium.

33. The machine of claim 31 in which the output means is for providing data to a transmission medium.